数据结构--试验报告线性表的基本操作

1、一、实验目的二、实验内容和要求三、源代码1) 顺序表的代码2) 单链表的代码四、测试结果1) 顺序表的测试结果2) 单链表的测试结果五、心得体会实验一线性表的基本操作及其应用一、实验目的1、帮助读者复习C+祁言程序设计中的知识。2、熟悉线性表的逻辑结构。3、熟悉线性表的基本运算在两种存储结构上的实现。4、掌握顺序表的存储结构形式及其描述和基本运算的实现。5、熟练掌握动态链表结构及有关算法的设计二、实验内容题目一：顺序表的基本操作问题描述实现顺序表的建立、求长度，取元素、修改元素、插入、删除等 顺序表的基 本操作。基本要求(1) 依次从键盘读入数据，建立带头结点的 顺序表；(2) 输出顺序表中的

2、数据元素(3) 求顺序表的长度；(4) 根据指定条件能够取元素和修改元素；(5) 实现在指定位置插入和删除元素的功能。(6) 根据算法，将两个有序的顺序表合并成一个有序顺序表。测试数据由学生任意指定。题目二：单链表的基本操作问题描述实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等 单链表的基本操作基本要求(1) 依次从键盘读入数据，建立带头结点的单链表；(2) 输出单链表中的数据元素(3) 求单链表的长度；(4) 根据指定条件能够取元素和修改元素；(5) 实现在指定位置插入和删除元素的功能。(6) 根据算法，将两个有序的单链表合并成一个有序单链表测试数据由学生任意指定。三、源

3、代码(一)顺序表的基本操作#include<iostream>using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct /结构体ElemType *elem;int length;int listsize;SqList;SqList Lx;Sta

4、tus InitList_Sq(SqList &L)/分配空间 L.elem=new ElemTypeLIST_INIT_SIZE;if(!L.elem)exit(OVERFLOW);L.length =0;L.listsize=LIST_INIT_SIZE;return OK;25Status ListInsert(SqList &L,int i,ElemType e) / ( int *q,*p;ElemType *newbase;if(i<1 | i>L.length+1) return ERROR;if(L.length>=L.listsize)插入新

5、元素( newbase=new ElemTypeL.listsize+LISTINCREMENT;if(!newbase) exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;q=&(L.elemi-1);for (p=&(L.elemL.length-1);p>=q;-p)*(p+1)=*p;*q=e;+L.length;return OK;Status Listlength(SqList L)/( int *p=L.elem;/while(p)( return (L.length); Status GetEl

6、em(SqList L, int i,ElemType &e)/( if(i<1 | i>L.length)return ERROR;else( e=L.elemi-1;return e;void MergeList(SqList La,SqList Lb,SqList &Lc) /长度判断线形表是否存在取元素合并( ElemType ai,bj;InitList_Sq(Lc);int i=1,j=1,k=0;int La_len,Lb_len;La_len=Listlength(La);Lb_len=Listlength(Lb);while(i<=La_le

7、n)&&(j<=Lb_len)( GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj)( ListInsert(Lc,+k,ai);+i; else( ListInsert(Lc,+k,bj);+j; while(i<=La_len)( GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j<=Lb_len)( GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);显示输入元素void show(SqList L,int i)/( int j;ElemTyp

8、e k;cout<<"顺序表显示如下:"<<endl;for(j=0;j<i-1;j+)( k=L.elemj;cout<<k<<"->" if(j=i-1 && i>0)( k=L.elemj; cout<<k; cout<<endl;void create(SqList &L,int n)/ ( int e;for(int i=0;i<n;i+)( cin>>e;L.elemi=e;L.length=i+1; Statu

9、s ListDelete_Sq(SqList &L,int i,ElemType &e)/删除( ElemType *p, *q;if(i<1 | i>L.length) return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p<=q;+p) *(p-1)=*p;-L.length;return OK;Status Listxiugei(SqList &L,int i,ElemType &e)/修改( if(i<1 | i>L.length)return ER

10、ROR;else( L.elemi-1=e;return OK; void shuru(SqList &L1)/顺序表的创建( int a;InitList_Sq(L1);cout<<"请输入顺序表的长度："cin>>a;cout<<”请输入顺序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);void chaxun(SqList &L1)/取第i个位置的元素( int j;ElemType e1;cout<

11、<”请选择所要取出元素的位置:"cin>>j;while(j<0|j>Listlength(L1)( cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要取出元素的位置："；cin>>j; GetElem(L1,j,e1);cout<<"取出的元素为:"<<e1<<endl;void xiugai(SqList &L1)/修改第i个位置的元素( int a;int j; ElemTy

12、pe e1;a=L1.length;cout<<"请选择所要修改元素的位置:"cin>>j;while(j<0|j>Listlength(L1)( cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要修改元素的位置:"cin>>j; cout<<"要修改成的元素:"cin>>e1;Listxiugei(L1,j,e1);cout<<"修改后的顺序表数据:"

13、<<endl;show(L1,a);void shanchu(SqList &L1)/ 删除顺序表里的元素( int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要删除元素的位置:"cin>>j;while(j<0|j>Listlength(L1)( cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要删除元素的位置:"cin>>j; ListDelete_Sq(L1

14、,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a-1);void charu(SqList &L1)/插入元素到顺序表里 int a; int j; ElemType e1;a=L1.length;cout<<"请选择所要插入元素的位置:"cin>>j;while(j<0|j>Listlength(L1) cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要插入元素的

15、位置:"cin>>j; cout<<"要插入的元素:"cin>>e1;ListInsert(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a+1);void hebing(SqList &L3)/合并两个顺序表 SqList L1,L2;int a,b;InitList_Sq(L1); InitList_Sq(L2);cout<<"请输入第一个有序表的长度："cin>>a;cout<<

16、"请输入第一个有序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);cout<<"请输入第二个有序表的长度："cin>>b;cout<<"请输入第二个有序表的元素(共"<<b<<"个)"<<endl;create(L2,b);show(L2,b);MergeList(L1,L2,L3);cout<<"合并后的有序表如下：&q

17、uot;show(L3,a+b);void main()/主菜单( int choice;for(;)( cout<<"顺序表的基本操作"<<endl;cout<<"1.顺序表的创建"<<endl;cout<<"2.顺序表的显小"<<endl;cout<<"3.顺序表的长度"<<endl;cout<<"4.取第i个位置的兀素"<<endl;cout<<"5

18、.修改第i个位置的兀素"<<endl;cout<<"6.插入素到顺序表里"<<endl;cout<<"7.删除顺序表里的兀素"<<endl;cout<<"8.合并两个顺序表"<<endl;cout<<"9.退出系统"<<endl;cout<<" cin>>choice;请选择："；switch(choice)( case 1: shuru(Lx);brea

19、k;case 2: show(Lx,Lx.length);break;case 3: cout<<"顺序表的长度："<<Listlength(Lx)<<endl;break;case 4: chaxun(Lx);break;case 5: xiugai(Lx);break;case 6: charu(Lx);break;case 7: shanchu(Lx);break;case 8: hebing(Lx);break;case 9: cout<<"退出系统！"<<endl;exit(0);br

20、eak;default : cout<<"输入有误，请重新选择"<<endl;break; (二)单链表的基本操作#include<iostream>using namespace std;#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int Status;typedef int ElemType;typedef struct LNode /存储结构 ElemType data;struct LNode *next;LN

21、ode,*LinkList;void CreateList(LinkList &L,int n) /尾插法创建单链表 LinkList p;L=new LNode;L->next=NULL; /建立一个带头结点的单链表LinkList q=L; /使q指向表尾for(int i=1;i<=n;i+) p=new LNode;cin>>p->data;p->next=NULL;q->next=p;q=p; Status GetElem(LinkList L,int i,ElemType &e)/ 取第 i 个元素 LinkList p=L

22、->next;int j=1;while(p&&j<i) p=p->next;+j; if(!p|j>i) return error; /第 i 个元素不存在e=p->data;return ok;Status LinkInsert(LinkList &L,int i,ElemType e) /插入( LinkList p=L;int j=0;while(p&&j<i-1) ( p=p->next;+j;/寻找第i-1个结点if(!p|j>i-1)return error; /i小于1或者大于表长加1Lin

23、kList s=new LNode; /生成新结点s->data=e; s->next=p->next; / 插入 L 中 p->next=s;return ok;Status ListDelete(LinkList &L,int i,ElemType &e) /删除( LinkList p=L;LinkList q;int j=0;while(p->next&&j<i-1)(/寻找第i个结点，并令p指向其前驱p=p->next;+j;if(!(p->next)|j>i-1) return error; /删

24、除位置不合理q=p->next;p->next=q->next;/删除并释放结点e=q->data;delete(q);return ok;void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)(/合并两个顺序链表LinkList pa,pc,pb;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb)( if(pa->data<=pb->data)( pc->next=pa;pc=pa;pa=pa-&g

25、t;next; else( pc->next=pb;pc=pb;pb=pb->next; pc->next=pa?pa:pb;delete(Lb);void show(LinkList L)/显示( LinkList p;p=L->next;while(p)( cout<<p->data<<"->"p=p->next; cout<<endl;int Length(LinkList L,int i)/表长(i=0;LinkList p=L->next;while(p)(+i;p=p->n

26、ext; return i;/修改void xiugai(LinkList L)( int i,j=1;ElemType k;ElemType e,m;LinkList p=L->next;cout<<"请输入要修改的元素位置(0<i<length):"cin>>i;GetElem(L,i,e);cout<<"该位置的元素："<<e<<endl;cout<<"修改后的元素值:"cin>>k;while(p&&j<

27、i)( p=p->next;+j; m=p->data;p->data=k;cout<<"修改后的单链表显示如下:"<<endl;show(L);void hebing()/合并两个单链表( int a,b;LinkList La,Lb,Lc;cout<<"请输入第一个有序链表的长度:"<<endl;cin>>a;cout<<"请输入第一个有序链表的元素共("<<a<<"个)："<<endl

28、;CreateList(La,a);show(La);cout<<"请输入第二个有序链表的长度:"<<endl;cin>>b;cout<<"请输入第二个有序链表的元素共("<<b<<"个)："<<endl;CreateList(Lb,b);show (Lb);MergeList(La,Lb,Lc);cout<<"合并后的有序链表如下："<<endl;show(Lc);void main() /主函数( int

29、 select;int x;ElemType y;LinkList list;for(;)( cout<<"单链表的基本操作"<<endl;cout<<"1.单链表的创建"<<endl;cout<<"2.单链表的显小"<<endl;cout<<"3.单链表的长度"<<endl;cout<<"4.取第i个位置的兀素"<<endl;cout<<"5.修改第i个

30、位置的兀素"<<endl;cout<<"6.插入素到单链表里"<<endl;cout<<"7.删除单链表里的兀素"<<endl;cout<<"8.合并两个单链表"<<endl;cout<<"9.退出系统"<<endl;cout<<"请选择:"cin>>select;switch(select)( case 1:cout<<" 请输入单

31、链表的长度:"<<endl; cin>>x;cout<<" 请输入"<<x<<"个元素"<<endl;CreateList(list,x);break;case 2: cout<<"单链表显示如下:"<<endl;show(list);break;case 3: int s;cout<<"单链表的长度为:"<<Length(list,s)<<endl;break;case 4

32、: cout<<"请选择所要取出元素的位置:"cin>>x;while(x<0|x>Length(list,s)( cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要取出元素的位置："；cin>>x; GetElem(list,x,y);cout<<" 该位置的元素为："<<y<<endl;break;case 5: xiugai(list); break;case 6:

33、cout<<"请选择要插入的位置："cin>>x;while(x<0|x>Length(list,s)( cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要插入元素的位置:"cin>>x; cout<<"要插入的元素值:"cin>>y;LinkInsert( list,x,y);cout<<"插入后单链表显示如下:"<<endl;show(l

34、ist);break;case 7: cout<<"请选择要删除的位置:"cin>>x;while(x<0|x>Length(list,s)( cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要删除元素的位置:"cin>>x; ListDelete(list,x,y);cout<<"要删除的元素值:"<<y<<endl;cout<<"删除后的单链表显示

35、如下:"<<endl;show(list);break;case 8: hebing();break;case 9: exit(0);break;default : cout<<"输入有误，请重新输入"<<endl;break;四、测试结果1）顺序表的测试结果I ' E:c+'zuoye 3 De bugS.exe'顺序表的基本操作 痛序定酌剖建2 顺序表的显示3 痂岸表的长詹4. 取第土个位置的元素5. 修改集土个位置的元素 6 -庙入兀素到顺序典里 人删除JI页序表里的元素并两个顺序表9 退出系统请选

36、匡1请输汨1页序表的长度：3请输入JI页序表的元素唾共3个 顺序表显示如下= 2->7->4' E:c+zu oy e 3Deb u g3.exe顺序表的基本操作 L顺岸装的创建2- 顺序表的显亦3顶J镂的长度4 .取第i个仓置的元素 匚修改第土个位置的元素 八括J-,元素到顺序表里 L删除顺序美里前元素 含并两个侦序表孔退出系统请选择：2_顺序表显示如下】2->7->4EH ' E:' c + +，,izuaye，3Debug'i3 exe*"E:c+zuoye3Debug3.exe'顺序表的基本操作i撷启亲由初建2页

37、斥表的显小3-IW表的长唐4 .取新个健由藉5 .修改第个佥置航素6 .指入元素到顺序表里 ? .州除顺序表里的元素 & 合并两个life9 退出系统请选 3际序表的长度：3 顺序表的基本操作 1页序羌由创建2 .顺序表的显示3 顺序表的长度4 取第i个位置的元素 S.修改第i个位置的元素 4插入元素到顺序表里 ?删除顺序表里的元素8- 合并两个顺序表9- 退出系统请选择：4请选择所要取出元素的位置M jiiAW误清重请*徭所要取出元素的位置：i 阿!出的元素为没raw : E：lo +z li Oy3 Deb l. g3 exe : 豉 *E:c+ + zu oye3Debug3.

38、exe'顺序表的基本操作 L顺序表的创建顺序表的基本操作2|页序衷的史示 3页序表的长度4- 取第土个也置的元素 A修改第i个位置的元素 J插人元素到顺序表里 刀御除顺序表里的元素 耽合并两个II质序表 如退出系统请'选才圣：S请选择所裳修改元素的位置:6 入看误，请羞新输A.倚在探所要修改元素的位置门要修改成的元素戏修改后的题序表数据： 顺序表豆小.如卞=2->7->21 顺庄羞的创建2.顺序表的显示3 -II页岸矣的长唐74 取第土个位置的元素5- 修改第土个位置的元素6 插入元素到顺序表里7- 删陆顺序表里的元素8 - 习1诲i" I、顺序表 私履出

39、系统请选择？ 6请选择所要插入元素的位置$ 入有误,请重崭毓入请选择所要插入元素的位置：3 要插入的元素山 修改后的哽序表数据： 顺序表显小如下：2->7->4->2霞 *E:c - +zuoye3 ,：）ebug3.exe<L顶序表蹦建2撷序表仙显不3撷础成4.取新个应置的元素5彻即置的元素6 岳入元甚顺晨里?.删除顺序表里的元雷8 .合并两倾蕨 魂出系统懿骼?青选翩WI除藤觥置用 翘新酬除元御应备 质藉显点吓：7->4->2C；h' E:c+zuoye3Debug3 exe'顺序表的创建2 .顷序轰的显不3 .顺序表的长度4取第件位置的元

40、素9 修改第土个位置的元素 &.O 元素到顺序表里 2删除顺序表里的元素 8、合打两个顺序表 、.-孔退出系统请选择；8请输入第一个有序表的长度，3 格输入第一个有序表的元素共3个顺序表显ZE如下:情输入第二个有序表的长度：2 请输入第二个有序表的元素共2个）顺序关显示如下:恰井后的有序表如下*顺序表显小如下，2->3->4- >5->5,E:c+Vuoye3Debug3.exe, jkey to continueii 选出 I mlfV />皿"E:c + -zuoye3Debug3.exe":请选S： 23崎入看误,请重祈选徭 顺序

41、表的基本操作。顺序表的创建2 -顺序表的显不3-顺序表的长度4 ,刷第i个位置的元素5- 修改第i个俊置的元素6- 插入元素到顺序表里 巳删除顺序遴的元素 耽合并两个顺序表9-退出系统请选择E 顺序耒腱棒作L财袖蟾2撷序表的显示3嘛的长度4 .醵i个血置航素5.修瓣i忧胃航重6着人福顺序魏7刑鼬牒里航素8 .合并两个癖宾9 .趾就顺序表的基本操作 i.顺序表的创逢 挪序表的显示3- 顺序表的长度4 .取第i个位置的元素5 .修改第i个位置的元素6- 插入元素到顺序表里 7 删除顺序装里的元素6 合并两个顺序表 9-退出系统2）单链表的测试结果EB E： > - .e 116-bi.g 加

42、，SB *E：c* - zu oy elD ebugl, exe*一 _ L单链表的创建2 单链表的显示3 单捶表的长唐L取第土个位置的元素 八修改爹土个位置的元素 6 .寤入亓需到单链美里 ，删除单格表里的元素R.合并两个单格表 私退出系统请选择U着输入单链表的长辱请输入4个元素单概表的基本操作L单销表的创建2 单销表的显示3 单链表的长度七成第1个位置的元素5 .修改第i个位置的元素6 .插入元素到单槌表里7 .删除单格表里的元素 矶合并两个单销表9 .退也系统请选择没单链表显示如下：13 4 6EB *E:c+zuoyelDebugl.gxg*' E：c+ +zuoylDebug

43、l exe'堕概表的基本操作 单链表的创建2 单链表的显示3 .单链表的槌4 取第i个位置的元素 八修改第i个位置的元素 6 .播人元素到单槌表里 ?海除单格表里的元素 旗合并两个单槌表9 .退出系统请选择：4请选择所萼取出元素的位置糖 璐入者误，请重霸输入 请选择所要取出元素的位置壮 该位萱的元羞方3单链表的基本操作 L里格表的创建2 .里格表的显示3 .里格表的长度4.取第i个位置的元素5 .修改第i个位置的元素6 插入元素到里链表里 ?删除单链表里的元素 矿合并两个单链表9 退出系统请选择：3单链表的长度正CL E:c+ zu oye 1'., Debu gl. exe''E:c+zuoyelDebugl.exeT单链表的基本操作L单链表的创建2, 单链表的显示3, 单链表的长度4-吨第i个位置的元素 成修改第土个位置的元素 6插入元素到单销表里 %删除单链表里的元素 8 ,合并两个单链表一9,退出系统，青选择冷_ 、请输X要修改的元素位置i<length) :3 我位置的元素再修改后的元素值福 核改后的单销表显示如下：单链表的基本操作L单槌表的创建八单槌表的显示3 单链表的长度4 取第即位置的元素 匚修改第土个位置的元奏6 插入元素到单链