数据结构线性表实验报告五篇.docx

数据结构线性表实验报告五篇第一篇：数据结构线性表实验报告实验报告课程名：数据结构实验名：线性表及其操作姓名：班级：学号：撰写时间：一实验目的与要求1.掌握线性表的实现2.掌握线性表的根本操作的实现二实验内容分别完成线性表的顺序表示及链式表示在两种表示上,分别实现一些线性表的操作,至少应该包括-在第i个位置插入一个元素-删除第i个元素-返回线性表长-返回第i个元素的值三实验结果与分析includeinclude/线性表链式表示structV声明一个结构体类型structVintvalue;structV*next;定义结构体变量;VoidPrintLink(structV*p)定义一个结构体指针While(P!=NULL)只要指针指向的变量不为NULL;就会一直循环链表指向下一个结构体(printf(u%dl,1,(*p).value);p=(*p).next;指针指向下一个结构体Printf("n);voidLink()structV*head;head=(structV*)malloc(sizeof(structV);开辟一个长度为size的内存(*head).value=-100;表头为-100(*head).next=NULL;Printf("-线性表链式表示n)；inti,n=10;structV*p=head;printf("10个数据:n);for(i=0;i(*p).next=(structV*)malloc(sizeof(structV);p=(*p).next;(*p).value=2*i;(*p).next=NULL;)PrintLink(head);调用PrimLink函数Printf("删除第四个数据:n");intk=4;p=head;for(i=l;ip=(*p).next;)structV*temp=(*p).next;/k表示插入和删除的位置(*p).next=(*temp).next;free(temp);PrintLink(head);printf(插入第十个数据:)；k=10;p=head;for(i=l;ip=(*p).next;)temp=(*p).next;(*p).next=(structV*)malloc(sizeof(structV)；(*(*p).next).value=-99;(*(*p).next).next=temp;PrintLink(head);/线性表顺序表示voidseql()inti,n=10,k=4;inta10;/输出数组元素Printf(线性表顺序表示n")；for(i=0;iai=i;printf(数组元素为:n);for(i=0;iPrintf(3d，ai);Printf(n);插入一个数组元素intm=n+lJ=L2;插入元素12intb20;for(i=0;iif(i(bi=ai;)elseif(i=k)bi=j;)elsebi=ai-l)Primf(输出插入一个元素的数组:);for(i=0;i(if(ici=aiJelseci=ai+l)Printf(输出删除一个元素的数组:n");for(i=0;iPrintf(数组元素为：n);for(i=l;i<=a0;i+)ai=i;for(i=0;i<2*a0;i+)printf(,%d",ai);printf("n);/在k位置插入一个元素for(i=a0;i>=k;i-)ai+l=ai;ak=-100;+a0;for(i=0;i<2*a0;i+)printf(,%dl",ai);printf(1,r");/-在kfor(i=0;i>k;i+)ai=ai+l;ak=-l;aO=n;a0;for(i=0;i<2*a0;i+)printf(',%d"zai);printf(,v");intmain(intargczchar*argv)seql();seq2();Link();return0;图1:实验结果截图实验分析：已在程序中按规定格式标注。第二篇：福州大学数据结构实验报告线性表数据结构原理实验报告学号：姓名：线性表一、问题描述L实现ADT表2.设表的Reverse运算将表中元素的次序反转。扩充用数组实现表的结构List,增加函数Reversed),将表L中元素的次序反转，并要求就地实现Reverse运算。二、算法描述从i=0开始，将表中第N个元素与N-i-1个元素调换即可三、核心代码voidReverseList(ListL)1.istitemtmp;inti;for(i=0;in/2;i+)tmp=L->tablei;L->tablei=L->tableL->n-l-i;L->tableL->n-l-i=tmp;四、运行结果第三篇：数据结构一实验报告线性表的根本操作(一)单链表的根本操作#includeusingnamespacestd;#definetrue1#definefalse0#defineok1#defineerror0#defineoverflow-2typedefintStatusjtypedefintEIemTypejtypedefstructLNode存储结构EIemTypedata;structLNode*next;LNode,*LinkList;voidCreateList(LinkList&LJntn)尾插法创立单链表LinkListp;L=newLNode;L->next=NULL;/建立一个带头结点的单链表1.inkListq=L;使q指向表尾StatusGetElem(LinkListLJntizElemType&e)取第i个元素LinkListp=L->next;intj=ljwhile(p8i8y7e%÷yfor(iti=l;i<=n;i+)p=newLNode;cin>>p->data;p->next=NULL;q->next=p;q=p;if(!pj>i)returnerror;第i个元素不存在e=p->data;returnok;StatusLinkInsert(LinkList&LJnti,日emTypee)/插入LinkListp=L;intj=O;while(p&&jnext;+j;寻找第i-1个结点if(!pj>i-l)returnerrori小于1或者大于表长加1LinkLists=newLNode;/生成新结点S->data=e;s->next=p->nextL中p->next=s;returnok;StatusListDelete(LinkList&L,intizElemType&e)删除LinkListP=LjLinkListq;intj=0;While(P->next&&jp=p->next;+j;if(!(p->next)Hj>i-l)returnerror;删除不合理q=p->next;p->next=q->next;删除并释放结点e=q->data;delete(q);returnok;voidMergeList(LinkListSiLazLinkList&Lb,LinkList&Lc)合并两个顺序链表1.inkListpa,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->next;elsepc->next=pb;pc=pb;pb=pb->next;)pc->next=pa?pa:pb;delete(Lb);voidshow(LinkListL)LinkListp;p=L->next;while(p)cout<data<p=p->next;cout<next;while(p)+i;显示表长3p=p->next;)returni;void×iugai(LinkListL)修改intij=l;EIemTyPek;ElemTypee,m;LinkLiStp=L->next;cout<>i;GetElem(L,i,e);CoUt<>k;WhiIe(P+j;m=p->data;p->data=k;cout<>a;cout<>b;cout<>select;switch(select)casel:cout<cin>>x;cout<CreateList(Iistx)Jbreakjcase2:cout<show(list);break;case3:ints;cout<>xjwhile(×<Ox>Length(listzs)coutox;GetEIem(IiSLx,y);CoUt<>x;WhiIe(X<Ox>Length(list,s)coutox;cout<>y;LinkInsert(list,xry)；cout<>x;while(x<O|x>Length(list,s)cout<>x;cout<ListDelete(listzxzy);break;case8:hebing();break;case9:exit(O);break;default:cout<四、测试结果D顺序表的测试结果82)单链表的测试结果五、心得体会当听到老师说写数据结构实验报告时，我有点惊讶，才学了不到一个月，就要写实验报告。记得去年学习C+时，学了一个学期，程序设计用了三周，才完成的，这个实验报告居然要一周完成两个设计，觉得很难。但是现在一周过去了，我也写完了，自我感觉良好。通过这次写实验报告，我深切的理解了这门课的本质。刚开始学这门课时,当时还不清楚这门课程的目的，现在，我真正的理解了：数据结构像是身体的骨骼，而C+是填充这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。数据结构是个框架，模型，抽象数据类型中列举了各种操作，而所用的C+语言，将各种操作描述出来构成算法。数据结构+算法=程序设计。在这次设计的过程中，我还遇到了，很多的问题。顺序表是按顺序存储的，用了一维数组来存储，又结合C+的程序设计，我又用了类，但是，在执行时出现了问题。后来问同学，指出我的错误，不过获益不少。我又重新整理思路，把顺序表的根本操作写好了。虽然走了很多弯路，但是让我认识到，一定要创新，大胆，不能按照旧的思路去干新的事情。单链表写起来简单多了，这个很快就搞定了。但是细节上出了问题。比方说，有些变量的重复定义，有些变量又没有定义，在调用函数，就直接复制过来，没有改参数通过修改，我深刻理解到：细节决定成败，在以后，不管做任何事情都要认真，细心。这次的实验报告，让我受益匪浅，不仅有知识方面的，还有生活和精神上的。总之，我会继续我的兴趣编程，相信在编程的过程中，能不断的提高自己。第四篇：数据结构线性表试验报告线性表上机实习1.实验目的(1)熟悉将算法转换为程序代码的过程。2了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。3熟练掌握顺序表的根本运算：查找、插入、删除等，掌握顺序表的随机存取特性。4了解线性表的链式存储结构，熟练掌握线性表的链式存储结构的C语言描述方法。5熟练掌握线性链表单链表的根本运算：查找、插入、删除等，能在实际应用中灵活选择适当的链表结构。2、实验要求1熟悉顺序表的插入、删除和查找。2熟悉单链表的插入、删除和查找。3、实验内容顺序表1抽象数据类型定义typedefstructTypeDatadatamaxsize;容量为maxsize的静态顺手表itn;顺序表中的实际元素个数JSeqList;静态顺序表的定义在本次实验中，首先建立一个空的静态顺序表，然后键盘输入数据存入表中，然后进入菜单项选择择界面，通过不同的数字输入，实现对顺序表，删除,插入，查找，显示等操作。2存储结构定义及算法思想在顺序表结构体的定义中，typedefintTypeData为整型，存储结构如下:for(n=0;ncout<cin>>Ldatan;顺序将数据存入顺序表)其他存储与此类似，都是直接赋值与数组的某一位插入版块子函数：voidinsert(SeqList&L)插入数据intazbzczk;cout<cin>>a>>b;if(b<=0b>(Ln+l)cout<k=L.datab-l;L.datab-l=a;c=L.n;L.n=Ln+1;while(c>b)1.datac=L.datac-l;c;通过循环，实现插入位置后的数据挨个往后移动一位)1.datab=k;)顺序表的插入与删除操作类似，在插入与删除后，都要循环调整后面数组的每一位元素，同时记录数据元素的长度的标示符也要跟着改变。显示操作是通过循环实现表中第一个元素到最后一个元素的输出，查找操作是直接取数组中的查找位输出。3实验结果与分析单链表(1)抽象数据类型定义typedefstructnodeDataTypedata;链表的数据类型structnode*link;链表的结点指针linknodelinklist;定义了结构体Iinklode和结构体指针IinkliSt在本次实验中，首先程序自己建立一个空的头结点，通过菜单的功能选择添加链表数据可自由添加链表的节点数及元素值。在菜单项选择择中，有添加链数据，插入链表数据，删除链表数据，查找链表数据和显示链表数据功能，选择不能的功能选择就能实现不同的操作。其中添加链表数据可反复批量输入链表数据。2存储结构定义及算法思想在单链表中，typedefintDataTypejDataTypedata;定义链表存储数据位整型。存储结构如下：while(p->link!=NULL)p=p->link;k+;首先找到单链表的最后结点如果是只有头结点的单链表那么直接跳过，以便后面接着输入数据for(inti=0;icout<开辟新的结点空间并转化为IinkIiSt指针型cin>>q->data;q->link=p->link;将前面一个结点的指向(及NULL)赋给新开辟的结点的指向p->link=q;将插入点前面一个结点指向新开辟的的结点p=q;将指明的最后一个一个结点向后移1位到最后一位，以便后面接着输入)删除结点子函数：voiddelate(linklist&1)删除单链表数据linklistp;intm,n,i=0;cout<cin>>m;P=I;将头结点赋给转移指针PWhile(P&&i查找删除结点的位置p=p->link;当在单链表中间已查到删除结点或P=NULL时跳出循环i+;if(p=NULL)当P=NULL跳出循环时,说明链表中没有该结点cout<)n=p->link->data;找到删除接结点将数据取出并显示出来找结点时是找的前一个结点cout<p->link=p->link->link;将删除结点的前后结点链接起来)链表的删除，插入操作是类似的，要考虑到参加或减少一个结点后，前后结点的链接关系，以及删除或插入的是最后一个结点时，新空间的开辟与结点收尾等问题。其中删除功能的一局部就是查找功能，显示功能也是从链表的头结点遍历至最后一个，依次输出。4实验结果与分析心得体会本次数据结构实习我收获颇丰，以前学过c语言与c+也有经常上机，但以往都是偏向于程序整体的算法设计，没有像这次的实习这样是着重在线性表，链表结构的算法设计上面。这次上机实习，让我更加熟练了结构体及结构体指针的用法，线性表的设计等等，同时在这次实习中，引用，指针，地址这三个的用法曾一度让我混淆，在查阅书籍后才得以解决，也希望老师在课堂上有时间时给我们详细讲解一下，指针，地址，引用三者的使用。附录：顺序表源代码：#includeusingnamespacestd;#definemaxsize50typedefintTypeDatajtypedefstructTypeDatadatamaxsize;intn;SeqList;voidmakeSeq(SeqList&L)/据intmznzkjcout<>mjfor(n=Ojn>Ldatan;)L.n=m;cout<输入线性表数输出线性表数据voidinsert(SeqList&L)插入数据intazbzczkjcout<>a>>b;if(b<=0|b>(L.n+l)cout<b)L.datac=L.datac-l;c-;Ldatab=k;)voiddelate(SeqList&L)删除数据intwei;cout<>wei;if(wei<lwei>Ln)cout<>a;if(a<=0a>(Ln)cout<cout<>xuanze;switch(xuanze)case1:insert(L);break;case2:delate(L);break;case3:find(L);break;case4:showSeq(L);break;default:break;单链表源代码：#includeusingnamespacestd;typedefintDataTypejtypedefstructnodeDataTypedata;structnode*link;linknode/linklist;linklistchushihua()linklist1.;L=(linklist)malloc(sizeof(linknode);L->link=NULLjcoutoaJinkIistp,q;p=I;WhiIe(P->link!=NULL)p=p->link;k+;for(inti=O;i>q->data;q->link=p->link;p->link=q;p=q;voidshow(linklistl)cout<link;while(p!=NULL)cout<data<link;)CoutomJinkIistp;p=l->link;while(p&&ilink;i+;if(!p)cout<data<linklistpzq;intmznzi=O;coutom>>n;p=l;while(p&&ilink;i+;if(p=NULL)cout<q=(linklist)malloc(sizeof(linknode);q->data=n;q->link=p->link;p->Iink=q;voiddelate(linklist&l)linklistp;intm,n,i=O;CoUt<>np=l;While(P&&ilink;i+;if(p=NULL)cout<link->data;cout<link=p->link->link;voidmain()linklistL;intselect;1.=chushihua();while(l)cout<>select;switch(select)case1:shuru(L);break;case2:insert(L);break;case3:delate(L);break;case4:find(L);break;case5:show(L);break;default:break;第五篇：数据结构实验报告二线性表的顺序存储实验报告二线性表的顺序存储班级：20：LOXXX姓名：HOOgLe学号：2010XXXX专业：XXXX一、实验目的：1掌握顺序表的根本操作的实现方法。2应用顺序表的根本算法实现集合A=AUB算法。(3应用顺序表的根本算法实现两有序顺序表的归并算法。二、实验内容：1、线性表顺序存储结构的根本操作算法实现要求采用类模板实现实现提示同时可参见教材p5822-p60页算法、ppt函数、类名称等可自定义，局部变量请加上学号后3位。库函数载和常量定义：代码#includeusingnamespacestd;constintMaxSize=100;(1顺序表存储结构的定义(类的声明)：代码tempIate定义模板类SeqListclassSeqListpublic:SeqLiSt();无参构造函数SeqList(datatypeazintn);有参构造函数SeqList();析构函数为空intLength();求线性表的长度datatypeGet(inti);按位查找，取线性表的第i个元素intLocate(datatypeitem);/查找元素itemvoidInsert(intldatatypeitem);/在第i个位置插入元素itemdatatypeDelete(inti);删除线性表的第i个元素voiddisplay。;遍历线性表，按序号依次输出各元素private:datatypedataMaxSize;存放数据元素的数组intIength;线性表的长度;2初始化顺序表算法实现不带参数的构造函数/*输入：无*前置条件：顺序表不存在*功能：构建一个顺序表*输出：无*后置条件：表长为0*/实现代码：templateSeqList:SeqList()Iength=O;)3顺序表的建立算法带参数的构造函数/*输入：顺序表信息的数组形式aJI页序表长度n/前置条件：顺序表不存* 功能：将数组a口中元素建为长度为n的顺序表*输出：无* 后置条件：构建一个顺序表V实现代码：templateSeqList:SeqList(datatypea,intn)if(n>Ma×Size)cout<datai=ai;length=n;在顺序表的第i个位置前插入元素e算法/*输入：插入元素e,插入位置i*前置条件：顺序表存在，i要合法* 功能：将元素e插入到顺序表中位置i处*输出：无* 后置条件：顺序表插入新元素，表长加1*/实现代码：templatevoidSeqList:Insert(inti,datatypeitem)intj;if(length>=MaxSize)cout<length+l)cout<=i;j)dataj=dataj-l;datai-l=item;length+;删除线性表中第i个元素算法/*输入：要删除元素位置i*前置条件：顺序表存在,i要合法* 功能：删除顺序表中位置为i的元素输出：无* 后置条件：顺序表册除了一个元素，表长减1*/实现代码：templatedatatypeSeqList:Delete(inti)intitemj;if(length=O)cout<length)cout<for(j=i；jdataj-l=dataj;注意数组下标从0记Iength-Jreturnitem;6遍历线性表元素算法/*输入：无* 前置条件：顺序表存在*功能：顺序表遍历*输出：输出所有元素*后置条件：无*/实现代码：templatevoidSeqList:display()if(length=0)cout<cout<7获得线性表长度算法/*输入：无* 前置条件：顺序表存在*功能：输出顺序表长度*输出：顺序表长度*后置条件：无*/实现代码：templateintSeqList:Length()returnLength;8在顺序线性表中查找e值，返回该元素的位序算法/*输入：查询元素值e/前置条件：顺序表存在* 功能：按值查找值的元素并输出位置*输出：查询元素的位置*后置条件：无V实现代码：templateintSeqList±ocate(datatypeitem)for(inti=0;i/T标为i的元素等于item,返回其序号i+1return0;查找失败9获得顺序线性表第i个元素的值/*输入：查询元素位置i*前置条件：顺序表存在，i要合法* 功能：按位查找位置为i的元素并输出值/输出：查询元素的值*后置条件：无*/实现代码：templatedatatypeSeqList:Get(inti)if(i<Oi>length)cout<10判表空算法/*输入：无*前置条件：无大功能：判表是否为空* 输出：为空返回1,不为空返回0*后置条件：无V实现代码：templateboolSeqList:Empty()if(length=0)return1;elsereturn0;(11)求直接前驱结点算法*输入：要查找的元素e,待存放前驱结点值el* 前置条件：无* 功能：查找该元素的所在位置，获得其前驱所在位置。*输出：返回其前驱结点的位序。*后置条件：el值为前驱结点的值V实现代码：templateintSeqList:Pre(datatypeitem)intk=Locate(item)-l;if(k>0)returnk;elsecout<return0;Q2)求直接后继结点算法*输入：要查找的元素e,待存放后继结点值el*前置条件：无* 功能：查找该元素的所在位置，获得其后继所在位置。*输出：返回其后继结点的位序。*后置条件：el值为后继结点的值V实现代码：templateintSeqList:Suc(datatypeitem)intk=Locate(item)+l;if(k>length)cout<returnk;上机实现以上根本操作，写出main。程序:voidmain()SeqListSeq;/创立if(Seq.Empty()cout<)Seq.Insert(lzl)jSeq.Insert(2,2)jSeq.Insert(3z3)jSeq.Insert(4f4)jSeq.Insert(5z5)；插入元素操作cout<cout<cout<cout<cout<SeqQeIete;删除元素cout<cout<cout<cout<cout<要求对每个算法都加以测试，判断是否正确；并测试不同类型数据的操作。粘贴测试数据及运行结果：2、用以上根本操作算法，实现A=AUB算法。利用函数模板实现/*输入：集合A,集合B*前置条件：无* 功能：实现A=AUB*输出：无* 后置条件：A中添加了B中的元素。/实现代码：templateSeqListSeqListzAdd(SeqList&item)if(item.Empty()return*this;elseintk=item.Length();intnum=this->Length();for(inti=l;i<=k;i+)for(intj=Ojif(dataj=item.Get(i)(break;)elseif(num-l=j&&datanum-l!=item.Get(i)(this->Insert(+numzitem.Get(i);)return*this;voidmain()SeqListAzB;cout<B.Insert(L2);B.Insert(2,6);B.Insert(3,l);B.Insert(4,8);B.Insert(5,9);插入集合B中元素A.Add(B);A.display();cout<3、对以上顺序表类中的根本操作算法适当加以补充，实现向一个有序的非递减的顺序表中插入数据元素e算法。/*输入：插入元素e*前置条件：Jll页序表已有序* 功能：将元素e插入到Jl访表中适当的位置，使顺序表依然有序*输出：无* 后置条件：有序顺序表插入了新元素，且表长加IoV实现代码：templatevoidSeqList:orderInsert(datatypeitem)intnum=this->Length();for(inti=0;iif(dataiitem)for(intk=num;k>i;k)datak=datak-l;datai+l=item;length+;break;)if(datai>item)(for(intk=num;k>i;k)datak=datak-l;datai=item;length+;break;voidmain()SeqListABAInSertQ,3);A.Insert(2,5);AJnSert(3,6)AInsert(4,8);A.Insert(5,10);插入顺序表cout<cout<cout<4、算法实现：LazLb为非递减的有序线性表,将其归并为Lc,该线性表仍有序未考虑相同时删除一重复值利用函数类板实现MergeList:/*输入：有序线性表La,有序线性表Lb*前置条件：Jl顺序表已有序*功能：将两线性表归并，不去掉相同元素*输出：返回一个新的有序线性表Lc*后置条件：无*/实现代码：templateSeqListSeqList:ElseAdd(SeqListSeqlzSeqListSeq2)intnum=Seq2.Length();for(inti=0;i<=num;i+)Seql.orderInsert(Seq2.Get(i)JreturnSeql;voidmai()SeqListLa,Lb,Lc;LaJnSert(L2);La.Insert(2,4);La.Insert(3,6);LaJnSert(4,8);S入Lacout<cout<cout<粘贴测试数据及运行结果：三、心得体会：含上机中所遇问题的解决方法，所使用到的编程技巧、创新点及编程的心得