顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。
顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素占用存储单元的长度。
#ifndef LIST_H #define LIST_H template <typename T> class List{ public: virtual void InitList()=0; //表初始化 virtual void DestoryList()=0; //销毁表 virtual int Length()=0; //求表长度 virtual const T & Get(int i)=0; //取表中元素 virtual int Locate(T & x)=0; //元素查找 virtual void Insert(int i,T & x)=0; //插入新元素 virtual T Delete(int i)=0; //删除元素 virtual bool Empty()=0; //判断表是否为空 virtual bool Full()=0; //判表是否满 }; #endif
#ifndef SEQLIST_H #define SEQLIST_H #include"List.h" #include<iostream> using namespace std;
template <typename T> class SeqList : public List<T>{ template <typename T> friend ostream & operator<<(ostream & os,const SeqList<T> & sl); public: SeqList(int m=20); SeqList(T ary[],int n,int max); ~SeqList(){ DestoryList(); delete [] ptr; } virtual void InitList(){curLen=0;} virtual void DestoryList(){curLen=-1;max=0;} virtual int Length(){return curLen;} virtual T Get(int i); //取表中元素 virtual int Locate(T & x); //元素查找 virtual void Insert(int i,T & x); //插入新元素 virtual T Delete(int i); //删除元素 virtual bool Empty(){return curLen==0;} //判断表是否为空 virtual bool Full(){return curLen==max;} //判表是否满 private: T * ptr; int curLen; int max; }; template <typename T> SeqList<T>::SeqList(int m){ max=m curLen=0; ptr=new T[max]; } template <typename T> SeqList<T>::SeqList(T ary[],int n,int max){ this->max=max; curLen=0; ptr=new T[max]; while(curLen<n){ ptr[curLen]=ary[curLen]; curLen++; } } template <typename T> T SeqList<T>::Get(int i){ if (i>=1 && i<=curLen) return ptr[i-1]; else throw "元素位置错误！"; } template <typename T> int SeqList<T>::Locate(T & x){ for (int i=0;i<curLen; i++) if (ptr[i]==x) return i+1; return 0; } template <typename T> void SeqList<T>::Insert(int i,T & x){ if(Full()) throw "顺序表已满！"; if(i<1 || i>=curLen+1) throw "插入位置错误！"; for(int j=curLen;j>=i;j--) ptr[j]=ptr[j-1]; ptr[i-1]=x; curLen++; } template <typename T> T SeqList<T>::Delete(int i){ T tmp; if(Empty()) throw "顺序表空！"; if(i<1 || i>=curLen) throw "删除位置错误！"; tmp=ptr[i-1]; for(int j=i-1;j<curLen-1;j++) ptr[j]=ptr[j+1]; curLen--; return tmp; } template <typename T> ostream & operator<<(ostream & os,const SeqList<T> & sl){ for(int i=0;i<sl.curLen;i++) os<<sl.ptr[i]<<", "; return os; } #endif
#include<iostream> #include"SeqList.h" using namespace std; int main(){ int ary[]={4,7,2,9,10,43,6},x=10,l; SeqList<int> myList(ary,7,10); cout<<myList<<endl; try{ myList.Insert(7,x); cout<<myList<<endl; }catch(char * s){ cout<<s<<endl; } try{ myList.Delete(40); cout<<myList<<endl; }catch(char * s){ cout<<s<<endl; } cout<<"请依次输入插入元素的位置和值：";cin>>l>>x; while(1){ try{ myList.Insert(l,x); cout<<myList<<endl; cout<<"请依次输入插入元素的位置和值：";cin>>l>>x; }catch(char * s){ cout<<s<<endl; break; } } cout<<myList<<endl;
return 0;
}
