数据结构实验一线性表的基本操作

1、天津农学院 13级软件工程1班 李光耀实验一 线性表的基本操作一、实验目的： 1掌握线性表的顺序和链式存储结构。2熟练地利用顺序和链式存储结构实现线性表的基本操作。 3能熟练地掌握顺序和链式存储结构中算法的实现。二、实验内容：第一部分：单链表1需求分析本演示程序用TC编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的

2、元素的值，查找操作后显示要查找元素的位置。 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作 测试数据：A 插入操作中依次输入11、22、33、44、55、66生成一个单链表B 查找操作中输入55返回这个元素在单链表中的位置C 输入要插入的位置为5，插入的元素为123；D 删除操作中输入44。 2概要设计（1）为了实现上述程序功能，需要定义单链表的抽象数据类型：ADT LinkList 数据对象：D=ai|aiIntegerSet,i=0,1,2,n,n0 数据关系：R=<ai,ai+1>|ai,ai+1 D基本操作：InitLinkList(&L

3、)操作结果：构造一个空的单链表L.InsLinkList(&L,pos,e)初始条件：单链表L已存在操作结果：将元素e插入到单链表L的pos位置DelLinkList(&L,pos,&e)初始条件：单链表L已存在操作结果：将单链表L中pos位置的元素删除，元素值置入e中返回LocLinkList(L,e)初始条件：单链表L依存在操作结果：单链表L中查找是否元素e，若存在，返回元素在表中的位置；若不存在，返回-1.Menu()操作结果：在屏幕上显示操作菜单（2）本程序包含7个函数： 主函数main() 初始化单链表函数InitLinkList() 显示操作菜单函数menu

4、() 显示单链表内容函数dispLinkList() 插入元素函数InsLinkList() 删除元素函数DelLinkList() 查找元素函数LocLinkList()InitLinkListInsLinkList各函数间关系如下：mainDelLinkListMenudispLinkListLocLinkList实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。1) 结点类型和指针类型typedef struct node int data;struct node *next;Node,*LinkListl;2) 单链表的基本操作为了方便

5、，在单链表中设头结点，其data域没有意义。bool InitLinkList(LinkList &L)（伪码算法）void DispLinkList(LinkList L)（伪码算法）void menu()（伪码算法）bool InsLinkList(LinkList &L,int pos,int e)（伪码算法）bool DelLinkList(LinkList &L,int pos,int &e)（伪码算法）int LocLinkList(LinkList L,int e)（伪码算法）3) 其他模块伪码算法4调式分析#include <iostrea

6、m>#include <iomanip>using namespace std;struct Nodeint data;Node *next;class LinkListpublic: LinkList(); LinkList(int a,int n); int getLength(); int Get(int i); int Locate(int x); void Insert (int i,int x); int Delete (int i); void PrintList(); void menus(); void InList();private: Node *fir

7、st;void LinkList:menus() cout<<"="<<endl;cout<<0<<"-"<<"退出程序"<<endl;cout<<1<<"-"<<"查看原始链表："<<endl;cout<<2<<"-"<<"查看链表长度："<<endl;cout<<3<&

8、lt;"-"<<"按位取出链表中的元素："<<endl;cout<<4<<"-"<<"按值取出链表中的元素："<<endl;cout<<5<<"-"<<"插入元素："<<endl;cout<<6<<"-"<<"删除元素："<<endl; cout<<"

9、;="<<endl;LinkList:LinkList() Node *first=new Node;first->next=NULL;LinkList:LinkList(int a,int n) Node *p=new Node;p=first; for(int i=0;i<n;i+) Node *s=new Node;s->data=ai; s->next=p->next;p->next=s; p=p->next; int LinkList:getLength()Node *p;int count=-1; p=first; w

10、hile(p!=NULL) p=p->next; count+; return count;int LinkList:Get(int i) Node *p;p=first->next;int count=1; while(p!=NULL&&count<i) p=p->next; count+; if(p=NULL)throw"位置" else return p->data;int LinkList:Locate(int x) Node *p;p=first->next;int count=1; while(p!=NULL)

11、 if(p->data=x) return count; p=p->next; count+; return 0;/按位查找void LinkList:Insert(int i,int x) Node*p;p=first;int count=0; while(p!=NULL&&count<i-1) p=p->next; count+; if(p=NULL) cout<<"超出范围" ; else Node *s=new Node;s->data=x; s->next=p->next;p->next=

12、s; /插入int LinkList:Delete(int i)Node *p;Node *q;int x; p=first;int count=0; while(p!=NULL&&count<i-1) p=p->next; count+; if(p=0|p->next=0) cout<<"位置"<<count; else q=p->next;x=q->data; p->next=q->next; delete q; return x; /删除void LinkList:PrintList()

13、Node*p; p=first->next; while(p!=NULL) cout<<setw(4)<<p->data; p=p->next;/遍历int main() int r,o;/o用来存储输入的r，r不能直接赋给LinkList（）； cout<<"请初始化链表，先请输入长度："<<endl; cin>>r;o=r; cout<<"再输入元素："<<endl; int ar; for(int q=0;q<r;q+) cin>>

14、;aq; LinkList B; LinkList b(a,o); int i,j,x,m; b.menus(); for(int j=0;j<=7;j+) cin>>j; switch(j) case 0:cout<<"退出程序"<<endl;break; case 1:cout<<"链表的元素为："b.PrintList();cout<<endl;break; case 2:cout<<"原始链表的长度为： "<<b.getLength()&

15、lt;<endl;break; case 3:cout<<"输入要取出元素的位置: " cin>>i;cout<<"取出的元素为："<<b.Get(i)<<endl;break; case 4:cout<<"输出查询的元素："cin>>x; cout<<"数为x的位置为: "<<b.Locate(x)<<endl;break; case 5:cout<<"输入要插入的位

16、置："cin>>i;cout<<endl; cout<<"输入要插入的数："cin>>x;cout<<endl; b.Insert(i,x);cout<<"插入后的链表为：" b.PrintList();cout<<endl;break; case 6:cout<<"删除前的链表为："b.PrintList();cout<<endl; cout<<"输入要删除的数的位置："cin>

17、>i;cout<<endl; cout<<"要删除的数为："<<b.Delete(i)<<endl; cout<<"删除后的链表：“”b.PrintList();cout<<endl;break; 5使用说明程序执行后显示=SELECT:在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。选择0：退出程序选择1：显示“查看原始链表” ，选择2：显示“查看链表长度 ”，选择3

18、：显示“按位取出链表中的元素” ，要求输入要查找元素的值，执行成功后返回元素在表中的位置选择4：显示“按值取出链表中的元素的位置” ，要求输入要查找元素的位置，执行成功后返回元素在表中的位置选择5：显示“插入元素” ，要求输入要插入的位置，执行成功后返回链表；选择6：显示“删除元素” ，要求输入要删除元素的值，执行成功后返回删除的元素。7测试结果（可以截图）1、建立单链表：2、输入1，查看原始链表3、查看链表的长度：输入2，结果显示如下：4按位取出链表中的元素：输入3，5、按值取出链表中元素的位置：6，插入元素：输入5，结果显示如下：7、删除元素：输入6，结果显示如下： 第二部分：顺序表2需求

19、分析本演示程序用TC编写，完成顺序表的生成，任意位置的插入、删除，以及确定某一元素在顺序表中的位置。 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数 输出的形式：在所有三种操作中都显示操作是否正确以及操作后顺序表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 程序所能达到的功能：完成顺表的生成（通过插入操作）、插入、删除、查找操作 测试数据：A 插入操作中依次输入11，22，33，44，55，66，77，88，99，生成一个顺序表。B 查找操作中依次输入11，

20、33，88返回这3个元素在顺序表中的位置C 删除操作中依次输入2，5，删除位于2和5的元素3概要设计SeqList数据对象：D=ai|aiIntegerSet,i=0,1,2,n,n0 数据关系：R=<ai,ai+1>|ai,ai+1 D基本操作：1.SeqList()length=0; 参构造函数，建立一个空的顺序表2.SeqList（int a,int n）;有参构造函数，建立一个长度为n的顺序表3.int Length()return length;求线性表的长度4.int Get(int i);按位查找，在线性表中查找第i个元素5.int Locate (int x);按值

21、查找，在线性表中查找值为x的元素符号6.void Insert (int i,int x);插入操作，在线性表中第i个位置插入值为x的元素7.int Delete (int i);删除操作，删除线性表的第i个元素8.void PrintList();遍历操作，按序号依次输出元素9，int Update (int i ,int m);4、调试运行#include<iostream>#include <iomanip>#define MaxSize 100using namespace std;class SeqList public: ()length=0; SeqLis

22、t(int a,int n); SeqList() int InitList(); int Length()return length; int Get(int i); int Locate(int x); void Insert(int i,int x); int Delete(int i); void PrintList();int Update(int i,int m); private: int dataMaxSize; int length; ; SeqList:SeqList(int a,int n) if(n>MaxSize)throw"参数非法" fo

23、r(int i=0;i<n;i+) datai=ai; length=n; int SeqList:InitList() int n; cin>>n; int an; cout<<"顺序表的长度为："<<n; if(n>MaxSize)throw"参数非法" for(int i=0;i<n;i+) cin>>ai; datai=ai; length+; cout<<"顺序表的元素为：" for(int i=0;i<n;i+) cout<<a

24、i<<" " int SeqList:Get(int i) if(i<1&&i>length)throw"查找位置非法" else return datai-1; int SeqList:Locate(int x) for(int i=0;i<length;i+) if(datai=x)return i+1; return 0; void SeqList:Insert(int i,int x) if(length>=MaxSize)throw"上溢" if(i<1|i>l

25、ength+1)throw"位置" for(int j=length;j>=i;j-) dataj=dataj-1; datai-1=x; length+; int SeqList:Update(int i,int m) if(i<1&&i>length)throw"查找位置非法" else return datai-1=m; int SeqList:Delete(int i) if(length=0)throw"下溢" if(i<1|i>length)throw"位置"

26、; int x=datai-1; for(int j=i;j<length;j+) dataj-1=dataj; length-; return x; void SeqList:PrintList() for(int i=0;i<length;i+) cout<<setw(4)<<datai; int main() SeqList b; b.InitList(); int i;int x;int m; for(int j=0;j<=7;j+) cin>>j; switch(j) case 0:cout<<"退出程序&q

27、uot;<<endl;break; case 1:cout<<"顺序表的长度为： "<<b.Length()<<endl;break; case 2:cout<<"顺序表的元素为："b.PrintList();cout<<endl;break; case 3:cout<<"输入要取出元素的位置: " cin>>i;cout<<"取出的元素为："<<b.Get(i)<<endl;brea

28、k; case 4:cout<<"输出查询的元素："cin>>x; cout<<"数为x的位置为: "<<b.Locate(x)<<endl;break; case 5:cout<<"输入要插入的位置："cin>>i;cout<<endl; cout<<"输入要插入的数："cin>>x;cout<<endl; b.Insert(i,x);cout<<"插入后的顺序

29、表为：" b.PrintList();cout<<endl;break; case 6:cout<<"输入要修改的位置："cin>>i;cout<<endl; cout<<"输入要修改的数："cin>>m;cout<<endl; cout<<"修改的元素为："<<b.Update(i,m)<<endl; cout<<"修改后的顺序表为："b.PrintList();cout<<endl;break; case 7:cout<<"删除前的