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

天津农学院 13级软件工程1班 李光耀实验一 线性表的基本操作一、实验目的： 1掌握线性表的顺序和链式存储结构。2熟练地利用顺序和链式存储结构实现线性表的基本操作。 3能熟练地掌握顺序和链式存储结构中算法的实现。二、实验内容：第一部分：单链表1需求分析本演示程序用TC编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作 测试数据：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 D基本操作：InitLinkList(&L)操作结果：构造一个空的单链表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() 显示单链表内容函数dispLinkList() 插入元素函数InsLinkList() 删除元素函数DelLinkList() 查找元素函数LocLinkList()InitLinkListInsLinkList各函数间关系如下：mainDelLinkListMenudispLinkListLocLinkList实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。1) 结点类型和指针类型typedef struct node int data;struct node *next;Node,*LinkListl;2) 单链表的基本操作为了方便，在单链表中设头结点，其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 #include 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 *first;void LinkList:menus() cout=endl;cout0-退出程序endl;cout1-查看原始链表：endl;cout2-查看链表长度：endl;cout3-按位取出链表中的元素：endl;cout4-按值取出链表中的元素：endl;cout5-插入元素：endl;cout6-删除元素：endl; cout=next=NULL;LinkList:LinkList(int a,int n) Node *p=new Node;p=first; for(int i=0;idata=ai; s-next=p-next;p-next=s; p=p-next; int LinkList:getLength()Node *p;int count=-1; p=first; while(p!=NULL) p=p-next; count+; return count;int LinkList:Get(int i) Node *p;p=first-next;int count=1; while(p!=NULL&countnext; 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) 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&countnext; count+; if(p=NULL) coutdata=x; s-next=p-next;p-next=s; /插入int LinkList:Delete(int i)Node *p;Node *q;int x; p=first;int count=0; while(p!=NULL&countnext; count+; if(p=0|p-next=0) cout位置next;x=q-data; p-next=q-next; delete q; return x; /删除void LinkList:PrintList()Node*p; p=first-next; while(p!=NULL) coutsetw(4)data; p=p-next;/遍历int main() int r,o;/o用来存储输入的r，r不能直接赋给LinkList（）； cout请初始化链表，先请输入长度：r;o=r; cout再输入元素：endl; int ar; for(int q=0;qaq; LinkList B; LinkList b(a,o); int i,j,x,m; b.menus(); for(int j=0;jj; switch(j) case 0:cout退出程序endl;break; case 1:cout链表的元素为：;b.PrintList();coutendl;break; case 2:cout原始链表的长度为： b.getLength()endl;break; case 3:couti;cout取出的元素为：b.Get(i)endl;break; case 4:coutx; cout数为x的位置为: b.Locate(x)endl;break; case 5:couti;coutendl; coutx;coutendl; b.Insert(i,x);cout插入后的链表为：; b.PrintList();coutendl;break; case 6:cout删除前的链表为：;b.PrintList();coutendl; couti;coutendl; cout要删除的数为：b.Delete(i)endl; cout删除后的链表：“”b.PrintList();coutendl;break; 5使用说明程序执行后显示=SELECT:在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。选择0：退出程序选择1：显示“查看原始链表” ，选择2：显示“查看链表长度 ”，选择3：显示“按位取出链表中的元素” ，要求输入要查找元素的值，执行成功后返回元素在表中的位置选择4：显示“按值取出链表中的元素的位置” ，要求输入要查找元素的位置，执行成功后返回元素在表中的位置选择5：显示“插入元素” ，要求输入要插入的位置，执行成功后返回链表；选择6：显示“删除元素” ，要求输入要删除元素的值，执行成功后返回删除的元素。7测试结果（可以截图）1、建立单链表：2、输入1，查看原始链表3、查看链表的长度：输入2，结果显示如下：4按位取出链表中的元素：输入3，5、按值取出链表中元素的位置：6，插入元素：输入5，结果显示如下：7、删除元素：输入6，结果显示如下： 第二部分：顺序表2需求分析本演示程序用TC编写，完成顺序表的生成，任意位置的插入、删除，以及确定某一元素在顺序表中的位置。 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数 输出的形式：在所有三种操作中都显示操作是否正确以及操作后顺序表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 程序所能达到的功能：完成顺表的生成（通过插入操作）、插入、删除、查找操作 测试数据：A 插入操作中依次输入11，22，33，44，55，66，77，88，99，生成一个顺序表。B 查找操作中依次输入11，33，88返回这3个元素在顺序表中的位置C 删除操作中依次输入2，5，删除位于2和5的元素3概要设计SeqList数据对象：D=ai|aiIntegerSet,i=0,1,2,n,n0 数据关系：R=|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);按值查找，在线性表中查找值为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#include #define MaxSize 100using namespace std;class SeqList public: ()length=0; SeqList(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(nMaxSize)throw参数非法; for(int i=0;in; int an; cout顺序表的长度为：MaxSize)throw参数非法; for(int i=0;iai; datai=ai; length+; cout顺序表的元素为：; for(int i=0;in;i+) coutai ; int SeqList:Get(int i) if(ilength)throw查找位置非法; else return datai-1; int SeqList:Locate(int x) for(int i=0;i=MaxSize)throw上溢; if(ilength+1)throw位置; for(int j=length;j=i;j-) dataj=dataj-1; datai-1=x; length+; int SeqList:Update(int i,int m) if(ilength)throw查找位置非法; else return datai-1=m; int SeqList:Delete(int i) if(length=0)throw下溢; if(ilength)throw位置; int x=datai-1; for(int j=i;jlength;j+) dataj-1=dataj; length-; return x; void SeqList:PrintList() for(int i=0;ilength;i+) coutsetw(4)datai; int main() SeqList b; b.InitList(); int i;int x;int m; for(int j=0;jj; switch(j) case 0:cout退出程序endl;break; case 1:cout顺序表的长度为： b.Length()endl;break; case 2:cout顺序表的元素为：;b.PrintList();coutendl;break; case 3:couti;cout取出的元素为：b.Get(i)endl;break; case 4:coutx; cout数为x的位置为: b.Locate(x)endl;break; case 5:couti;coutendl; coutx;coutendl; b.Insert(i,x);cout插入后的顺序表为：; b.PrintList();coutendl;break; case 6:couti;coutendl; coutm;coutendl; cout修改的元素为：b.Update(i,m)endl; cout修改后的顺序表为：;b.PrintList();coutendl;break; case 7:cout删除前的顺序表为：;b.PrintList();coutendl; couti;coutendl; cout要删除的数为：b.Delete(i)endl; cout删除后的顺序表为：;b.PrintList();c