2线性表0908140805王飞

《2线性表0908140805王飞》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二：线性表的实现一、实验要求：创建出顺序表以及单链表。能够正确地在顺序表和单链表中插入数据，删除单链表及顺序表中的数据，并且完成表的遍历。在顺序表插入和删除时能够显示移动次数。二、需求分析：要求利用课堂上学习的知识完成以下功能1,生成顺序表，2,顺序表的插入，3,顺序表的删除，4,顺序表的遍历，5,生成单链表，6,单链表的插入，7,单链表的删除，8,单链表的遍历，9，退出三、概要设计：主要有一个虚基类linearlist，派生两个类：linkedlist（单链表）和seqlist（顺序表）。在单链表中，有储存

2、数据的T类型变量data以及指向下一个结点的指针link；在顺序表中，有储存数据的T类型指针变量data、表征顺序表长度的整型变量maxSize以及指向顺序表末尾的整形指针last。单链表我用了struct来定义LinkNode类，主要有以下几个函数：构造函数、析构函数、voidinput（T）（进行单链表的输入）、virtualboolInsert（i，Tx）（进行单链表的插入）、boolRemove(inti,T&x)（单链表的删除操作）、voidoutput（T）（进行单链表的遍历）以及一些辅助完成功能的函

3、数；顺序表中函数与单链表中类似。函数算法将在“调试与测试”中说明。最后，编写一个主函数对线性表进行功能的测试，用switch语句执行要求的各项任务，达到实验目的。四、详细设计：//seqlist.h#ifndefseqlist_h#defineseqlist_h#include#include#include"linearList.h"constintdefaultSize=100;templateclassSeqList:publicLinearLis

4、t{protected:T*data;intmaxSize;intlast;//voidreSize(intnewSize);public:SeqList(intsz=defaultSize);SeqList(SeqList&L);~SeqList(){delete[]data;}intSize()const{returnmaxSize;}intLength()const{returnlast+1;}intSearch(T&x)const;intLocate(inti)const;//voidreSi

5、ze(intnewSize);boolInsert(inti,T&x);boolRemove(inti);voidinput();voidoutput();SeqListoperator=(SeqList&L);};templateSeqList::SeqList(intsz){if(sz>0){maxSize=sz;last=-1;data=newT[maxSize];if(data==NULL){cerr<<"存储分配错误！"<

6、eSeqList::SeqList(SeqList&L){maxSize=L.Size();last=L.Length()-1;data=newT[maxSize];if(data==NULL){cerr<<"存储分配错误！"<intSeqList::Search(T&x)const{for(inti=0;i<=last;i++

7、)if(data[i]==x)returni+1;return0;}templateintSeqList::Locate(inti)const{if(i>=1&&i<=last+1)returni;elsereturn0;}templateboolSeqList::Insert(inti,T&x){if(last==maxSize-1)returnfalse;if(i<0

8、

9、i>last+1)returnfalse;for(intj=last;j>=i;j--)data

10、[j+1]=data[j];data[i]=x;last++;returntrue;}templateboolSeqList::Remove(inti){if(last==-1)returnfalse;if(i<0

11、

12、i>last+1)returnfalse;Tx=data[i-1];cout<