本文共 5117 字，大约阅读时间需要 17 分钟。
基类：
#ifndef LINEARLIST_H
#define LINEARLIST_H /* * FileName: LinearList.h *Creater:QianChenglong *Date:2011/10/18 *Comments: 线性表的抽象基类 */ template<typename T> class LinearList{ public: virtual int getLength() const=0;//求表长； virtual int find(const T& value)const=0;//根据值搜索位序； virtual void setData(int i,const T value) =0;//赋值； virtual T getData(int i) const=0;//取值； virtual bool insert(int i,T& x) =0;//插入； virtual bool remove(int i,T& value) =0;//删除； virtual bool isEmpty() const=0;//判断表空； virtual void output() const=0;//输出； }; #endif类定义：
#ifndef SEQLIST_H
#define SEQLIST_H #include<iostream> #include<cstdlib> #include"LinearList.h" template<typename T> class SeqList: public LinearList<T>{ private: T* data;//存放数组； int maxSize;//最大存储个数； int length;//当前已存表项数； static int initializedCapacity;//初始空间 void overflowProcess();//空间溢出时的处理 public: SeqList();//默认构造函数； SeqList(SeqList<T>& L);//复制构造函数； ~SeqList();//析构函数 int capacity() const;//返回容量； int getLength() const;//返回表长 int find(const T& x) const;//搜索x在表中的位置,成功返回位序，失败返回0； T getData(int i) const;//取序号为i的值(从1开始)； void setData(int i,const T value);//把逻辑位序为i的值置成value void PushBack(T& x); bool insert(int i,T& x);//插入:将x插入位序为i的位置,成功返回1，失败返回0； bool remove(int i,T& value);//删除位序为i的元素，value返回删除值,成功返回1，失败返回0； bool isEmpty() const;//判空 bool isFull() const;//判满 void sort();//排序，从小至大； SeqList<T>& operator=(SeqList<T>& L);//赋值； void output() const; template<T> friend std::ostream& operator<<(std::ostream& out,SeqList<T>& x);//函数模板作为类模板的友元函数的声明方式； }; #include"SeqList.cpp" #endif类实现：
#ifndef SEQLIST_CPP
#define SEQLIST_CPP #include<iostream> #include<cstdlib> #include"SeqList.h" /// template<typename T> int SeqList<T>::initializedCapacity=100;//模板的静态数据成员的定义 / template<typename T> std::ostream& operator<<(std::ostream& out,SeqList<T>& x){//重载<< int length=x.getLength(); for(int i=0;i!=length;++i) out<<x.getData(i+1)<<' '; out<<std::endl; return out; } / template< typename T> SeqList<T>::SeqList() :maxSize(initializedCapacity) {//默认构造函数 length=0; if(!(data=new T[maxSize])){//分配内存 std::cerr<<"内存分配失败\n"; exit(0); } } /// template< typename T> SeqList<T>::SeqList(SeqList<T>& L) { maxSize=L.Size(); length=L.Length(); if(!(data=new T[maxSize])) { std::cerr<<"存储分配错误！\n"; exit(1); } for(int i=0;i!=length;++i) data[i]=L.getData(i); } template< typename T> int SeqList<T>::find(const T& foundValue) const{//查找值为x的 int i; for(i=0;i!=length;++i){ if(data[i]==foundValue) break;//若找到则退出 } if(data[i]==foundValue) return i+1; else return 0; } / template<typename T> bool SeqList<T>::insert(int i,T& value){//将value插入到第i个位置，物理位序为i-1 if(isFull())//若空间已满 overflowProcess(); if(i<=0||i>=length+2)//若插入位置不位于[1,length+1],则插入位置不存在； return 0; for(int n=length-1;n!=i-2;--n)//从后向前，依次后移 data[n+1]=data[n]; data[i-1]=value; ++length; return 1; } template<typename T> bool SeqList<T>::remove(int i,T& value){//删除第i个值,用value返回被删除值，物理位序为i-1 if(isEmpty())//若表空，则失败 return 0; if(i<=0||i>=length)//若删除位置不存在，则失败 return 0; else{ value=data[i-1]; for(int n=i-1;n!=length;++n){//从前向后，依次前移 data[n]=data[n+1]; } --length; } } template<typename T> SeqList<T>& SeqList<T>::operator=(SeqList<T>& L){//赋值函数 maxSize=L.capacity(); length=L.length(); data=new T[maxSize]; for(int i=0;i!=length;++i) data[i]=L.getData(i); return *this; } template<typename T> void SeqList<T>::output() const{//输出表值 for(int i=0;i!=length;++i) std::cout<<data[i]<<' '; std::cout<<std::endl; } /// template<typename T> void SeqList<T>::sort(){//按值从小到大排序 int minSub; T term; for(int i=0;i!=length;++i) { minSub=i; for(int j=i+1;j!=length;++j){ if(data[minSub]>data[j]) minSub=j; } if(minSub!=i){ term=data[i];data[i]=data[minSub];data[minSub]=term; } } } / template<typename T> void SeqList<T>::PushBack(T& value){//将value插到表尾 if(isFull()) overflowProcess(); data[length]=value; ++length; } template<typename T> SeqList<T>::~SeqList(){//析构函数 delete [] data;//删除data所指向的内存 data=0;//指针置零 } /// template<typename T> int SeqList<T>::capacity() const{//返回 return maxSize; } // template<typename T> T SeqList<T>::getData(int i) const{//取逻辑位序为i的元素的值 return i>0&&i<=length?data[i-1]:NULL;//若失败返回NULL,有点问题 } /// template<typename T> void SeqList<T>::setData(int i,const T value){ if(i>0&&i<=length-1) data[i-1]=value; else std::cout<<"插入位置不存在。\n"; } / template<typename T> bool SeqList<T>::isEmpty() const{//判空 return length==0; } /// template<typename T> bool SeqList<T>::isFull() const{//判满 return length==maxSize; } / template<typename T> void SeqList<T>::overflowProcess(){//溢出处理 maxSize+=20;//空间再增加20 T* newData=new T[maxSize]; for(int i=0;i!=length;++i)//数据复制到新分配的内存 newData[i]=data[i]; delete [] data;//释放原空间 data=newData; } // template<typename T> int SeqList<T>::getLength() const{//返回表长 return length; } #endif功能测试：
#include<iostream>
#include"SeqList.h" int main() { SeqList<int> La; for(int i=1;i!=10;++i) La.insert(i,i); La.output(); std::cout<<La.capacity()<<std::endl <<La.getLength()<<std::endl <<La.find(3)<<std::endl; int x; La.remove(3,x); std::cout<<x<<std::endl; La.output(); int elem; while(std::cin>>elem) La.PushBack(elem); La.output(); La.sort(); La.output(); std::cout<<La; std::cin.clear(); return 0; }转载地址：http://nmgxi.baihongyu.com/