数据结构实验报告(共34页).doc

《数据结构实验报告(共34页).doc》由会员分享，可在线阅读，更多相关《数据结构实验报告(共34页).doc（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构实验报告姓名： 学号： 专业： 班 级： 指导教师： 实验时间： 实验地点： （实验题目）1. 实验内容和要求 实验一 顺序表实验实验要求1、顺序表结构定义，算法的实现以库文件方式实现，库文件名统一为seqList.h；2、实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求；3、程序有适当的注释。实验任务 编写算法实现下列问题的求解。求顺序表中第i个元素（函数），若不存在，报错。实验测试数据基本要求：第一组数据：顺序表长度n10，i分别为5，n，0，n+1，n+2第二组数据：顺序表长度n=0，i分别为0，2在第i个结点前插入值为x的结点。实验测

2、试数据基本要求：第一组数据：顺序表长度n10，x=100, i分别为5,n,n+1,0,1,n+2第二组数据：顺序表长度n=0，x=100，i=5删除顺序表中第i个元素结点。实验测试数据基本要求：第一组数据：顺序表长度n10，i分别为5,n,1,n+1,0 第二组数据：顺序表长度n=0， i=5在一个递增有序的顺序表L中插入一个值为x的元素，并保持其递增有序特性。实验测试数据基本要求：顺序表元素为 （10,20,30,40,50,60,70,80,90,100）,x分别为25，85，110和8将顺序表中的奇数项和偶数项结点分解开（元素值为奇数、偶数），分别放入新的顺序表中，然后原表和新表元素同

3、时输出到屏幕上，以便对照求解结果。实验测试数据基本要求：第一组数据：顺序表元素为 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60）第二组数据：顺序表元素为 （10,20,30,40,50,60,70,80,90,100）求两个递增有序顺序表L1和L2中的公共元素，放入新的顺序表L3中。实验测试数据基本要求： 第一组第一个顺序表元素为 （1，3，6，10，15，16，17，18，19，20）第二个顺序表元素为 （1，2，3，4，5，6，7，8，9，10，18，20，30）第二组第一个顺序表元素为 （1，3，6，10，15，16，17，18，19，20）第二个顺序表元素为

4、 （2，4，5，7，8，9，12，22）第三组第一个顺序表元素为 （）第二个顺序表元素为 （1，2，3，4，5，6，7，8，9，10） 实验二 单链表实验实验要求1、本次实验中的链表结构均为带头结点的单链表；2、链表结构定义，算法实现放入库文件“linkList.h”；3、运算和变量命名直观易懂，并有相应的注释。实验任务 编写算法实现下列问题的求解。求链表中第i个结点的指针（函数），若不存在，则返回NULL。实验测试数据基本要求：第一组数据：链表长度n10，i分别为5，n，0，n+1，n+2第二组数据：链表长度n=0，i分别为0，2在第i个结点前插入值为x的结点。实验测试数据基本要求：第一组数

5、据：链表长度n10，x=100, i分别为5,n,n+1,0,1,n+2第二组数据：链表长度n=0，x=100，i=5删除链表中第i个元素结点。实验测试数据基本要求：第一组数据：链表长度n10，i分别为5,n,1,n+1,0 第二组数据：链表长度n=0， i=5在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。实验测试数据基本要求：链表元素为 （10,20,30,40,50,60,70,80,90,100）,x分别为25，85，110和8将单链表中的奇数项和偶数项结点分解开（元素值为奇数、偶数），申请2个头结点，把分开的奇数项和偶数项分别链接到这2个头结点上，然后再将这两个新

6、链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。实验测试数据基本要求：第一组数据：链表元素为 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60）第二组数据：链表元素为 （10,20,30,40,50,60,70,80,90,100）求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。实验测试数据基本要求： 第一组第一个链表元素为 （1，3，6，10，15，16，17，18，19，20）第二个链表元素为 （1，2，3，4，5，6，7，8，9，10，18，20，30）第二组第一个链表元素为 （1，3，6，10，15，16，17，18，19，

7、20）第二个链表元素为 （2，4，5，7，8，9，12，22）第三组第一个链表元素为 （）第二个链表元素为 （1，2，3，4，5，6，7，8，9，10） 实验三 链栈实验实验要求1、本次实验中，链栈使用带头结点的单链表实现。2、链栈结构定义，算法实现全部放入库函数“linkStack.h”中；3、各运算和变量命名直观易懂，并有相应的注释。实验任务 编写算法实现下列问题的求解。初始化一个链栈。判断是否空栈。入栈第一组数据：10，13，5，8，20，55第二组数据：a, b, c, d, e, f, g取栈顶元素出栈将10进制数转换为16进制数第一组数据：4第二组数据：11第三组数据：254第四组

8、数据：1357 实验四 循环队列实验实验要求1、本次实验中，队列使用顺序结构循环队列；2、结构定义和运算实验放入库文件“seqQueue.h”中；3、各运算和变量命名直观易懂，并有相应的注释。实验任务 编写算法实现下列问题的求解。初始化一个队列。判断是否队空。判断是否队满。设队列最大长度：MaxLen=100第一组数据：入队n个元素，判断队满第二组数据：用循环方式将1到99，99个元素入队，判队满入队第一组数据：4，7，8，12，20，50第二组数据：a,b,c,d,f,g出队取队头元素求当前队列中元素个数编写算法实现初始化空循环队列；当键盘输入奇数时，此奇数入队；当键盘输入偶数时，队头出队；

9、当键盘输入0时，算法退出；每当键盘输入后，输出当前队列中的所有元素。2. 实验目的 实验一 顺序表实验1、理解线性表的顺序存储结构。2、熟练掌握顺序表的有关算法设计。3、根据具体问题的需要，设计出合理的表示数据的顺序结构，并设计相关算法。 实验二 单链表实验实验目的1、理解线性表的链式存储结构。2、熟练掌握单链表结构及有关算法的设计。3、根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。 实验三 链栈实验实验目的1、掌握栈的基本概念。2、掌握链栈的建立、入栈和出栈等方法。3、根据具体问题的需要，设计出合理的表示数据的结构，并设计相关算法。 实验四 循环队列实验 实验目的1、掌

10、握队列的基本概念。2、掌握循环队列的建立、入队和出队等方法。3、根据具体问题的需要，设计出合理的表示数据的结构，并设计相关算法。3. 数据结构设计采用带头结点的链表结构设计4. 算法设计 实验一 顺序表实验#include stdafx.h#include iostream.h#include seqList.hvoid GetElement(seqList L,int i,elementType x)if(getElement(L,i,x)coutL中第i个元素是：xendl;else cout输入序号超出顺序表L范围。endl;void main(int argc, char* argv)

11、 seqList L;int i;elementType x; initialList(&L); /初始化顺序表 CreateSeqList( L);cout请输入要查找的序号i;GetElement( L,i, x);#include stdafx.h#include iostream.h#include seqList.hvoid InsertData(seqList *L, elementType x, int m)int k,i;k=listInsert( L, x, m);if (k=0)cout表满endl;else if (k=1)cout插入序号错误endl;else cout

12、插入后的顺序表为endl;for(i=0;ilistLen;i+)coutdatai ;coutendl;void main (int argc, char* argv)seqList L; int m,i;elementType x; initialList(&L); CreateSeqList( L);cout请输入要插入的序号m; cout请输入插入的元素值x; cout插入前的顺序表为：endl; for(i=0;iL.listLen;i+)coutL.datai ;coutendl;InsertData(&L, x, m);#include stdafx.h#include iost

13、ream.h#include seqList.hvoid DeleteData(seqList *L,int m)int k,i;k=listDelete(L,m);if(k=0)cout空表endl;else if(k=1)cout删除的序号超出范围endl;else for(i=0;ilistLen;i+)coutdatai ;coutendl;void main(int argc, char* argv) seqList L;int m,i; initialList(&L); CreateSeqList( L);cout请输入删除的序号m;cout原顺序表为：endl;for(i=0;i

14、L.listLen;i+)coutL.datai ;coutendl;cout删除后的顺序表是：endl;DeleteData(&L, m); #includestdafx.h#includeiostream.h#includeseqList.hvoid OrderInsert(seqList &L,elementType x)int i=L.listLen-1;if(i=MaxLen-1) cout序号超出范围=0&L.dataix)L.datai+1=L.datai;i-;L.datai+1=x;L.listLen+;void main()seqList L;int i;elementTy

15、pe x;initialList(&L);CreateSeqList( L);cout原递增顺序表为endl;for(i=0;iL.listLen;i+)coutL.datai ;coutendl;cout请输入插入的元素x;OrderInsert(L,x); cout插入后的递增顺序表为：endl; for(i=0;iL.listLen;i+)coutL.datai ;coutendl;#includestdafx.h#includeiostream.h#includeseqList.hvoid SeperateData(seqList &L)seqList O,J;int i,m=0,n=

16、0;for(i=0;iL.listLen;i+)if(L.datai%2=0) O.datam+=L.datai;else J.datan+=L.datai;cout偶数值顺序表为endl;for(i=0;im;i+)coutO.datai ;coutendl; cout奇数值顺序表为endl; for(i=0;in;i+)coutJ.datai ;coutendl;void main()int i;seqList L;initialList(&L);CreateSeqList(L);cout原顺序表为endl;for(i=0;iL.listLen;i+)coutL.datai ;couten

17、dl;SeperateData(L);#includestdafx.h#includeiostream.h#includeseqList.hvoid PublicData(seqList &L1,seqList &L2,seqList &L3)int i1=0,i2=0,i3=0,i;while(i1L1.listLen&i2L2.datai2)i2+;elsei1+;L3.listLen=i3;for(i=0;iL3.listLen;i+)coutL3.datai ;coutendl;void main()int i;seqList L1,L2,L3;initialList(&L1);ini

18、tialList(&L2);initialList(&L3);cout请输入第一个递增顺序表的元素endl;CreateSeqList( L1);cout请输入第二个递增顺序表的元素endl; CreateSeqList( L2);cout第一个顺序表为：endl;for(i=0;iL1.listLen;i+)coutL1.datai ;coutendl; cout第二个顺序表为：endl;for(i=0;iL2.listLen;i+)coutL2.datai ;coutendl;cout公共元素为：endl;PublicData(L1,L2,L3); 实验二 单链表实验#includelin

19、kedList.hvoid main() node *L,*p; int i; initialList(*& L); createListR( *& L ); cout请输入要查找的元素节点序号i; p=getElement(L, i); cout第i个节点的指针 p=pendl; #includelinkedList.hvoid InsertData(node *L,elementType x, int i)node *p;bool Q; Q=listInsert( L, i, x ); if(Q=true) /打印链表 cout插入后的链表为：next; while(p) coutdata

20、next; coutendl; else cout插入位置 i不对endl; void main()node *L,*p;elementType x;int i; createListR( *& L ); cout原链表为：next; while(p) coutdatanext; coutendl; cout请输入要插入的元素值x;cout请输入要插入的位置i; InsertData(L, x, i);#includelinkedList.hvoid DeleteData(node *L,int i)node *p;bool Q=listDelete( L, i);if(Q=true)cout

21、删除后的链表为：next;while(p)coutdatanext;coutendl;else cout删除节点错误endl;void main() node *L,*p; int i; createListR( *& L ); cout原链表为：next;while(p)coutdatanext;coutendl;cout请输入要删除的节点序号：i; DeleteData(L,i);#includelinkedList.hvoid OrderInsert(node *L,elementType x)node *u,*p=L;while(p-next!=NULL&p-next-datanext

22、;if(p-next=NULL|p-next-datax)u=new node;/产生节点，此步骤不可少u-data=x;u-next=p-next;p-next=u;p=L-next;while(p!=NULL)coutdatanext;coutendl;void main() elementType x; node *p; node *L;createListR( *& L );cout输出原递增有序的链表next;while(p)coutdatanext;coutendl;cout输入插入的数字x;cout输出插入后的递增有序表endl;OrderInsert(L,x);#include

23、 linkedList.hvoid PrintList(node *L)node *p; p=L-next;while(p)coutdatanext;coutnext;while(p)if(p-data%2=0)u=new node;u-data=p-data;Ro-next=u;Ro=u;else t=new node;t-data=p-data;Rj-next=t;Rj=t;Ro-next=NULL;Rj-next=NULL; p=p-next; void main()node *L,*J,*O;cout创建一个链表endl; createListR( *& L ); cout所创建的链表

24、为endl; PrintList(L);SeperateData( L, *&J, *&O);cout奇数结点组成的链表为endl;PrintList(J);cout偶数结点组成的链表为endl;PrintList(O);#includelinkedList.hvoid PrintList(node *L)node *p; p=L-next;while(p)coutdatanext;coutnext;pb=B-next;while(pa!=NULL&pb!=NULL)if(pa-datadata)pa=pa-next;else if(pb-datapb-data)pb=pb-next;else

25、u=new node;u-data=pa-data;Rc-next=u;Rc=u;pa=pa-next;pb=pb-next;Rc-next=NULL;void main()node *A,*B,*C;cout创建第一个链表endl; createListR( *&A ); cout创建第二个链表endl; createListR( *&B); cout打印第一个链表:endl; PrintList(A); cout打印第二个链表endl; PrintList(B);PublicData(A,B,*&C);cout打印公共元素组成的链表endl;PrintList(*&C); 实验三 链栈实验

26、/ alltest.cpp : Defines the entry point for the console application./#include stdafx.h#include iostream.h#include linkStack.hint main(int argc, char* argv) node* H, *L, *P,*q; elementType y;initialstack(L);/初始化 if(stackEmpty(L) cout空栈endl; else cout栈不空endl; coutnext;/H为头指针coutnext;while(P)coutdatane

27、xt;coutnext=H;cout出栈后元素顺序为：;P=H;while(P)coutdatanext;coutdata;cout栈顶元素yendl; destroyList(L);return 0;/ Tentosixteen.cpp : Defines the entry point for the console application./#include stdafx.h#include iostream.h#include .linkStack.hint main(int argc, char* argv) node *p,*L,*H;initialstack(L);int M,x

28、;char a,b,c,d,e,f; coutM;Tentosixteen(&M,L); H=L-next; coutnext;while(p)coutdatanext;coutnext=H;coutdata; switch(x) case 97: coutA; break; case 98: coutB; break; case 99: coutC; break; case 100: coutD; break; case 101: coutE; break; case 102: coutF; break; default: coutnext;coutendl;destroyList(L);r

29、eturn 0; 实验四 循环队列实验-#include .stdafx.h#include .seqQueue.hint main(int argc, char* argv)seqQueue Q;elementType x;int i; cout1. 初始化顺序循环队列endl;initQueue(&Q);cout2. 判断空队列endl;if(queueEmpty(Q)cout当前队列空！endl;elsecout当前队列非空！endl;cout 3.循环入队endl;for(i=1;i=99;i+)enQueue(&Q, i); /循环入队/打印当前队列中元素，从头至尾cout当前队列中

30、元素（从头至尾）:;i=Q.front+1;while(i=Q.rear)coutQ.datai, ;i+;coutendl;cout4. 判队满endl;if(queueFull(Q)cout当前队满！endl;elsecout当前队列不满！endl;cout5. 取队头元素endl;queueFront(Q, x);cout当前队头元素: x=xendl;cout6. 出队（删除）endl;outQueue(&Q);/打印当前队列中元素，从头至尾cout出队后队列中元素（从头至尾）:endl;i=Q.front+1;while(i=Q.rear)coutQ.datai, ;i+;coute

31、ndl;cout7.判断当前队列中的元素个数endl;couti-1endl;return 0;#includeseqQueue.hvoid main() seqQueue Q;elementType x,y;int i; initQueue(&Q);/初始化空队列cout输入xx;while(x!=0)int n=x%2;if(n)enQueue(&Q, x);/当x是奇数时，入队if(n!=0) queueFront(Q, y);cout当前队头元素: y=yendl; /打印当前队列中元素，从头至尾cout出队后队列中元素（从头至尾）:endl;i=Q.front+1;while(i=Q.rear)coutQ.datai, ;i+;coutendl;/键盘继续输入cout输入xx;5. 运行和测试 实验一 顺序表实验 实验二 单链表实验 实验三 链栈实验 实验四 循环队列实验-6. 总结和心得 首先呢，先要感谢敬爱的张老师，说实话您是我在大学里遇到的不多的几个让我感到特别和蔼可亲的老师之一，您给我们上课时总是面带笑容，讲解内容也特别的细致，而且还会教给我们许多其他的东西，可以说我对数据结构这门课的兴趣很大程度是您给予我的。虽然您很少点名，但您可以翻看一下，每次点名我都到了。您的课我确实每次都来了，不是因为怕您点名，而是真的喜欢