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

一、实验目的二、实验内容和要求三、源代码1)顺序表的代码2)单链表的代码四、测试结果1)顺序表的测试结果2)单链表的测试结果五、心得体会实验一线性表的基本操作及其应用一、实验目的1、帮助读者复习C++语言程序设计中的知识。2、熟悉线性表的逻辑结构。3、熟悉线性表的基本运算在两种存储结构上的实现。4、掌握顺序表的存储结构形式及其描述和基本运算的实现。5、熟练掌握动态链表结构及有关算法的设计二、实验内容题目一：顺序表的基本操作[问题描述]实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。[基本要求]（1）依次从键盘读入数据，建立带头结点的顺序表；（2）输出顺序表中的数据元素（3）求顺序表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。（6）根据算法，将两个有序的顺序表合并成一个有序顺序表。[测试数据]由学生任意指定。题目二：单链表的基本操作[问题描述]实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。[基本要求]2（1）依次从键盘读入数据，建立带头结点的单链表；（2）输出单链表中的数据元素（3）求单链表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。（6）根据算法，将两个有序的单链表合并成一个有序单链表。[测试数据]由学生任意指定。三、源代码(一)顺序表的基本操作#includeiostreamusingnamespacestd;#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;typedefintElemType;#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{//结构体ElemType*elem;intlength;intlistsize;}SqList;SqListLx;StatusInitList_Sq(SqList&L)//分配空间{L.elem=newElemType[LIST_INIT_SIZE];if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;3}StatusListInsert(SqList&L,inti,ElemTypee)//插入新元素{int*q,*p;ElemType*newbase;if(i1||iL.length+1)returnERROR;if(L.length=L.listsize){newbase=newElemType[L.listsize+LISTINCREMENT];if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}StatusListlength(SqListL)//长度{int*p=L.elem;//判断线形表是否存在while(p){return(L.length);}}StatusGetElem(SqListL,inti,ElemType&e)//取元素{if(i1||iL.length)returnERROR;else{e=L.elem[i-1];returne;}}voidMergeList(SqListLa,SqListLb,SqList&Lc)//合并{ElemTypeai,bj;InitList_Sq(Lc);4inti=1,j=1,k=0;intLa_len,Lb_len;La_len=Listlength(La);Lb_len=Listlength(Lb);while((i=La_len)&&(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);}}voidshow(SqListL,inti)//显示{intj;ElemTypek;cout顺序表显示如下:endl;for(j=0;ji-1;j++){k=L.elem[j];coutk-;}if(j==i-1&&i0){k=L.elem[j];coutk;}coutendl;}voidcreate(SqList&L,intn)//输入元素{inte;for(inti=0;in;i++)5{cine;L.elem[i]=e;L.length=i+1;}}StatusListDelete_Sq(SqList&L,inti,ElemType&e)//删除{ElemType*p,*q;if(i1||iL.length)returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p=q;++p)*(p-1)=*p;--L.length;returnOK;}StatusListxiugei(SqList&L,inti,ElemType&e)//修改{if(i1||iL.length)returnERROR;else{L.elem[i-1]=e;returnOK;}}voidshuru(SqList&L1)//顺序表的创建{inta;InitList_Sq(L1);cout请输入顺序表的长度：;cina;cout请输入顺序表的元素(共a个)endl;create(L1,a);show(L1,a);}voidchaxun(SqList&L1)//取第i个位置的元素{intj;ElemTypee1;cout请选择所要取出元素的位置:;6cinj;while(j0||jListlength(L1)){cout输入有误，请重新输入endl;cout请选择所要取出元素的位置:;cinj;}GetElem(L1,j,e1);cout取出的元素为:e1endl;}voidxiugai(SqList&L1)//修改第i个位置的元素{inta;intj;ElemTypee1;a=L1.length;cout请选择所要修改元素的位置:;cinj;while(j0||jListlength(L1)){cout输入有误，请重新输入endl;cout请选择所要修改元素的位置:;cinj;}cout要修改成的元素:;cine1;Listxiugei(L1,j,e1);cout修改后的顺序表数据:endl;show(L1,a);}voidshanchu(SqList&L1)//删除顺序表里的元素{inta;intj;ElemTypee1;a=L1.length;cout请选择所要删除元素的位置:;cinj;while(j0||jListlength(L1)){cout输入有误，请重新输入endl;cout请选择所要删除元素的位置:;cinj;}7ListDelete_Sq(L1,j,e1);cout修改后的顺序表数据:endl;show(L1,a-1);}voidcharu(SqList&L1)//插入元素到顺序表里{inta;intj;ElemTypee1;a=L1.length;cout请选择所要插入元素的位置:;cinj;while(j0||jListlength(L1)){cout输入有误，请重新输入endl;cout请选择所要插入元素的位置:;cinj;}cout要插入的元素:;cine1;ListInsert(L1,j,e1);cout修改后的顺序表数据:endl;show(L1,a+1);}voidhebing(SqList&L3)//合并两个顺序表{SqListL1,L2;inta,b;InitList_Sq(L1);InitList_Sq(L2);cout请输入第一个有序表的长度：;cina;cout请输入第一个有序表的元素(共a个)endl;create(L1,a);show(L1,a);cout请输入第二个有序表的长度：;cinb;cout请输入第二个有序表的元素(共b个)endl;create(L2,b);show(L2,b);MergeList(L1,L2,L3);cout合并后的有序表如下：;show(L3,a+b);8}voidmain()//主菜单{intchoice;for(;;){cout顺序表的基本操作endl;cout1.顺序表的创建endl;cout2.顺序表的显示endl;cout3.顺序表的长度endl;cout4.取第i个位置的元素endl;cout5.修改第i个位置的元素endl;cout6.插入元素到顺序表里endl;cout7.删除顺序表里的元素endl;cout8.合并两个顺序表endl;cout9.退出系统endl;cout请选择：;cinchoice;switch(choice){case1:shuru(Lx);break;case2:show(Lx,Lx.length);break;case3:cout顺序表的长度:Listlength(Lx)endl;break;case4:chaxun(Lx);break;case5:xiugai(Lx);break;case6:charu(Lx);break;case7:shanchu(Lx);break;case8:hebing(Lx);break;case9:cout退出系统!endl;exit(0);break;default:cout输入有误，请重新选择endl;break;}}}(二)单链表的基本操作#includeiostreamusingnamespacestd;9#definetrue1#definefalse0#defineok1#defineerror0#defineoverflow-2typedefintStatus;typedefintElemType;typedefstructLNode//存储结构{ElemTypedata;structLNode*next;}LNode,*LinkList;voidCreateList(LinkList&L,intn)//尾插法创建单链表{LinkListp;L=newLNode;L-next=NULL;//建立一个带头结点的单链表LinkListq=L;//使q指向表尾for(inti=1;i=n;i++){p=newLNode;cinp-data;p-next=NULL;q-next=p;q=p;}}StatusGetElem(LinkListL,inti,ElemType&e)//取第i个元素{LinkListp=L-next;intj=1;while(p&&ji){p=p-next;++j;}if(!p||ji)returnerror;//第i个元素不存在e=p-data;returnok