2线性表0908140805王飞.doc

实验二：线性表的实现 一、实验要求： 创建出顺序表以及单链表。能够正确地在顺序表和单链表中插入数据，删除单链表及顺序表中的数据，并且完成表的遍历。在顺序表插入和删除时能够显示移动次数。 二、需求分析： 要求利用课堂上学习的知识完成以下功能1,生成顺序表，2,顺序表的插入，3,顺序表的删除，4,顺序表的遍历，5,生成单链表，6,单链表的插入，7,单链表的删除，8,单链表的遍历，9，退出 三、概要设计： 主要有一个虚基类linearlist，派生两个类：linkedlist（单链表）和seqlist（顺序表）。在单链表中，有储存数据的T类型变量data以及指向下一个结点的指针link；在顺序表中，有储存数据的T类型指针变量data、表征顺序表长度的整型变量maxSize以及指向顺序表末尾的整形指针last。单链表我用了struct来定义LinkNode类，主要有以下几个函数：构造函数、析构函数、void input（T）（进行单链表的输入）、virtual bool Insert（i，Tx）（进行单链表的插入）、bool Remove(int i, T x)（单链表的删除操作）、void output（T）（进行单链表的遍历）以及一些辅助完成功能的函数；顺序表中函数与单链表中类似。函数算法将在“调试与测试”中说明。最后，编写一个主函数对线性表进行功能的测试，用switch语句执行要求的各项任务，达到实验目的。 四、详细设计： //seqlist.h #ifndef seqlist_h #define seqlist_h #includeiostream.h #includestdlib.h #includelinearList.h const int defaultSize=100; templateclass T class SeqList:public LinearListT{ protected: T * data; int maxSize; int last; //void reSize(int newSize); public: SeqList(int sz=defaultSize); SeqList(SeqListTL); ~SeqList(){delete[] data;} int Size()const{return maxSize;} int Length()const{return last+1;} int Search(T x)const; int Locate(int i)const; //void reSize(int newSize); bool Insert(int i,Tx); bool Remove(int i); void input(); void output(); SeqListT operator=(SeqListTL); }; templateclass T SeqListT::SeqList(int sz) { if(sz0) { maxSize=sz;last=-1; data=new T[maxSize]; if(data==NULL) {cerr存储分配错误！endl;exit(1);} } } templateclass T SeqListT::SeqList(SeqListTL) { maxSize=L.Size();last=L.Length()-1; data=new T[maxSize]; if(data==NULL) {cerr存储分配错误！endl;exit(1);} for(int i=1;i=last+1;i++) data[i-1]=L.data[i]; } templateclass T int SeqListT::Search(Tx)const{ for(int i=0;i=last;i++) if(data[i]==x)return i+1; return 0; } templateclass T int SeqListT::Locate(int i)const{ if(i=1i=last+1)return i; else return 0; } templateclass T bool SeqListT::Insert(int i,T x) { if(last==maxSize-1) return false; if(i0||ilast+1) return false; for(int j=last;j=i;j--) data[j+1]=data[j]; data[i]=x;