数据结构实验报告.doc

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

1、!-实验一：约瑟夫问题1、实验目的1）掌握用VC6.0上机调试线性表的基本方法，2）掌握线性表的基本操作，如插入、删除、检索等在链式存储结构上的运算。2、实验环境（硬/软件要求）： Windows XP + VC6.03、实验内容约瑟夫问题的一种描述是：编号为1，2，n的n个人按顺时针方向围坐一圈，先从某个人从1开始报数，报到m的人出列，接着从出列的下一个人开始重新从1报数，数到m的人又出列，如此下去，直到所有人全部都出列为止。试设计一个程序，求出出列顺序。4、实验设计思想在实践约瑟夫问题时的关键是用两个指针把一个移动的，一个指向要删除的节点，另外要注意保留头指针。第一步是建立一个循环的单向链

2、表。第二步是运用指针遍历链表同时计数到第m个时将其删除。此时指针指向不变。其格式如下：output(struct Joseph *head) /输出出列情况int i,j=1;struct Joseph *p1,*p2;p1=p2=head; /p1 、p2都指向头指针for(i=1;inext; /从第M个人开始报数，所以p1指针依次后移，指向第m个人while(n0)for(i=1;inext; /开始报数 报到s前 p1 p2依次后移printf(第%d个出列的人是:%dn,j,p1-num);p2-next=p1-next; p1=p2-next; /此人出列，将p1-next赋给p2

3、-next，将p1所指向的结点删掉n-; /人数减少1j+; / 出列人数加15、程序清单/*运行环境VC*/#include #include#include #define LEN sizeof(struct Joseph)struct Joseph /定义josephint num;struct Joseph *next;int n,s,m;print(struct Joseph *head) /打印链对中的信息 struct Joseph *p; /p指针p=head; /将p指向头指针printf(%d个人的代号如下:n,n);doprintf(%d ,p-num);p=p-next

4、;while(p!=head); /依次输入每个人的代号printf(n);output(struct Joseph *head) /输出出列情况int i,j=1;struct Joseph *p1,*p2;p1=p2=head; /p1 p2都指向头指针for(i=1;inext; /从第M个人开始报数，所以p1指针依次后移，指向第m个人while(n0)for(i=1;inext; /开始报数，报到s前p1、p2依次后移printf(第%d个出列的人是:%dn,j,p1-num);p2-next=p1-next; p1=p2-next; /此人出列，将p1-next赋给p2-next，将

5、p1所指向的结点删掉n-; /人数减少1j+; / 出列人数加1struct Joseph *create() /建立链队列int i;struct Joseph *head;struct Joseph *p1,*p2;printf(请输入总人数(输入0退出程序):n);scanf(%d,&n);if(n=0)exit(0);/退出for(i=1;inum=i;if(i=1)head=p1;elsep2-next=p1;p2=p1;p2-next=head; /将整个链队构成一个环形print(head);printf(请输入从第几个人开始报数:n);scanf(%d,&m);printf(数

6、到第几个人出列:n);scanf(%d,&s);return head;main()struct Joseph *head;while(1)head=create();output(head);system(pause);system(cls);6、实验心得在约瑟夫问题中，着重训练的是链表的应用，尤其是链表中结点的删除、检索等。由于单向链表等线性表的操作基本思想是一致的，因此通过对单向链表的练习来加深对线性表的理解。在本实验中，需要解决的问题的重点是怎样找到要删除的结点。因此，我首先考虑解决这个问题，即应用循环语句来找到满足条件的结点，我选用了if循环语句。然后应用指针实现查找过程。在弄清出这

7、些之后，在建立一个单向链表即形成程序。在经过调试改正一些细节即可。在编辑的过程中，将所学的知识充分应用于实践，虽然遇到了一些问题，比如说不知从何下手，不过通过仔细考虑找出问题的关键和参考资料并逐步编辑出程序。从而注意到了一些细节问题，例如：头指针的问题、*p1,*p2之间在不同的函数中不同的关系的区分以及函数位置的前后和声明的关系等等。这些只有在真的去实践时才能意识到的小问题给我带来了很大的困惑。这次的实验让我重新熟悉了C+的编辑环境，为以后的实验奠定了基础。病人看病模拟程序1、实验目的1）掌握队列的定义；2）掌握队列基本操作的实现，并能用于解决实际问题。 2、实验内容编写一个程序,反映病人到

8、医院看病排队等医生的过程.在病人排除过程中,主要重复两件事:A：病人到达诊室,将病历本交给护士,排到等待队列中候诊.B：护士从等待队列中取出下一位病人的病历,该病人进入诊室就诊要求模拟病人等待就诊这一过程,程序采用菜单方式,其选项及功能说明如下:(a)排队: 输入排队病人的病历号,加入病人排队队列中(b)就诊: 病人排队队列中最前面的病人就诊,并将其从队列中删除(c)查看排队:从队首到队尾列出所有的排队病人的病历号(d)下班: 退出运行3、实验环境 Microsoft Visual C+ 6.04、实验设计思想病人看病，需要进行插入和出队程序。这与队列的操作顺序完全相同，具有先进先出的顺序，只

9、在对头进进行输出在对尾进行插入操作，故此问题可以用队列这种特殊的数据结构实现。在具体的实现过程中需要进行数据的插入即病人入队操作。在程序中实现数据的输出处理即病人就诊过程。其中还需设置一个实现对队列中数据的遍历操作函数以及一个退出函数即查看和下班。在设计时，首先应对相应的数据结构以及相应的对头指针进行定义，其具体格式为：typedef struct qnode int data; struct qnode *next; qnode; /链队结点类型typedef struct qnode *front,*rear; qutype; /链队类型再次，通过四个函数实现具体的操作，其定义格式如下：p

10、aidu(qutype *q );jiuzhen(qutype *q);chakan(qutype *q);xiaban(qutype *q);5、程序源代码及解释#include #include #include #define null 0typedef struct node int data; struct node *next; /连队节点定义Qnode, *Queuepre;typedef struct Qnode *front,*rear LQueue; /将对头指针和队尾指针定义为一个结构体void paidui(LQueue *Q) /实现数据节点的插入函数Qnode *p

11、;int num,m;coutm;for(int i=0;im;i+) /用循环语句实现一次插入多个节点coutnum; p=(Queuepre)malloc(sizeof(Qnode);/malloc()函数生成一个新节点 p-data=num;p-next=null;/ Q-rear-next=p;Q-rear=p;/将节点插入到队列中void jiuzhen(LQueue &Q)/出队函数的实现Queuepre q;int m;q=Q.front-next;/取出对头节点的值m=q-data;if(q=Q-rear)/判断队列中是否已经只有一个节点剩余coutm号病人就诊，已没有病人就诊

12、!;else /若还有多个节点直接输出数据元素 coutm号病人就诊front-next=q-next;free(q);void chakan(LQueue *Q)Queuepre p;coutfront-next; coutdatanext; coutdatanext!=null);/判断队列中的节点个数并实现指针的后移以逐个输出其值void xiaban(LQueue *Q)while(Q-front) Q-rear=Q-front-next; free(Q-front); Q-front=Q-rear;/ 摧毁整个队列即下班操作的实现void main()int sel,flag=1;

13、/定义一个选择字符和一个标志符LQueue *qu;Queuepre p;qu=(LQueue *)malloc(sizeof(LQueue);p=(Queuepre)malloc(sizeof(Qnode); /*创建空队*/qu-front=qu-rear=p;p-next=null;free(p);while(flag=1) /实现入队，出队，查看的多次操作coutsel; switch(sel) case 1: paidui(qu); break; case 2:jiuzhen(qu); break; case 3: chakan(qu);break; case 4: xiaban(q

14、u);flag=0; break; /执行此语句是改变标志符，一跳出本循环 6、实验心得本实验中应用的主要是队列的知识，重点是结点的插入。在主函数中创建一个菜单，使得进行操作的选择运用switch语句，此为复习上学期所学内容。在实践本实验的过程中，我没有遇到太大的问题，这得益于第一个实验。本实验与第一个实验的基本思想是一致的，不同的是表达方式。在进行队列的遍历，即查看排队时，我开始并不是很明白它的意图，但经过参考资料，终于发现原来是要清点人数，判断队列是否为空。通过本实验的学习，使我进一步认识到了栈与队列的区别，栈是“先进后出”，队列是“先进先出”，根据病人看病的特点，只能选择运用队列而不能运

15、用栈。在编辑程序时，运用了建立空对、队列初始化、入队和出队等队列的基本知识，使得我在课堂上所学得到了充分的应用，并进一步熟悉了队列的基础知识。同时，也使我发现要认真观察，只有充分理解了现实生活中的遇到的事情才能透彻的分析问题，提出解决问题的办法。二叉树的建立与遍历1、实验目的：1）掌握二叉树的二叉链表存储结构；2）掌握利用二叉树的先序遍历方法创建一个二叉树；3）掌握二叉树的先序、中序、后序遍历的递归实现方法；2、实验环境（硬/软件要求）：Windows XP + VC6.03、实验内容： 按先序次序输入二叉树中结点的值，（用*表示空），构造一棵二叉树；以递归算法实现二叉树的先序、中序、后序遍历

16、。注：采用二叉链表作为二叉树的存储结构。4、实验要求：1）编写创建二叉树的函数，函数名: createbitree。2）编写递归实现二叉树的中序、先序和后序遍历算法。函数名分别为：inorder,preorder,postorder。5、实验设计思想在本实验中需要建立一个二叉树和三个遍历函数，其中遍历函数需要用递归的算法，三个遍历函数基本一致。其格式为：void Preorder(BiTree T) /先序遍历函数if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); /递归 在建立二叉树时，要注意用二叉链表作为二叉树的

17、存储结构。其格式为：typedef struct createbitree char data; struct createbitree *lchild,*rchild; createbitree,*BiTree; 6、实验清单#include #include #define NULL 0 typedef struct createbitree char data; struct createbitree *lchild,*rchild; createbitree,*BiTree; BiTree Create(BiTree T) /树的建立函数char ch; ch=getchar(); i

18、f(ch=*) T=NULL; /输入*则为空else if(!(T=( createbitree *)malloc(sizeof(createbitree) printf(Error!); T-data=ch; /生成根结点T-lchild=Create(T-lchild); /生成左子树T-rchild=Create(T-rchild); /生成右子树 return T; void Preorder(BiTree T) /先序遍历函数if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); /递归 void inord

19、er(BiTree T) /中序遍历函数if(T) inorder(T-lchild); printf(%c,T-data); inorder(T-rchild); /递归 void postorder(BiTree T) /后序遍历函数if(T) postorder(T-lchild); postorder(T-rchild); /递归printf(%c,T-data); main() /主函数BiTree T; T=Create(T); Preorder(T); printf(n); inorder(T); printf(n); postorder(T); 7、实验心得本实验是这四个实验中

20、最简单的一个实验，包含的内容并不多，主要就是二叉树的建立及三种遍历方式，而三种遍历方式基本一致因此比较简单。我所不熟悉的是怎样用二叉链来作为二叉树的存储结构。经过翻看老师的课件，终于将顺序存储结构、二叉链存储结构和三叉链表存储结构之间的不同弄清楚，不再混淆。虽然思考起来内容不多，但是由于能力水平有限，有些东西还是不能很好的实现。通过本实验的练习，能够对二叉树的主要内容作一个比较深入的理解和记忆，同时掌握树中非常重要的一中树型结构。二叉树中最重要的为三种遍历，而且运用的递归比较多。递归的使用时要注意，初始时的状态以及如何使用递归，注意普遍性，思考时可以从普通的开始。数据结构的实验要达到的目的方法

21、是有很多种的，只有深入才会发现有很多的写法和其他程序达到的目的是一样的，一个实验肯定会经过多次运行，多次纠正错误，只有不断的改正才能真正的体会出它的意义。对于数据结构的学习多半靠在实践中摸索。内部排序1、实验目的：1）深刻理解排序的定义和各种排序方法的特点、并能灵活应用。2）掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。3）了解各种方法的排序过程及依据的原则，掌握各种排序方法的性能4、的分析方法。2、实验环境（硬/软件要求）：Windows XP +VC+6.03、实验内容：1、对于给定的某无序序列，分别用直接插入排序、快速排序、希尔排序、简单选择排序、等方法进行排序，并输出每种排序

22、下的各趟排序结果。4、实验要求：1、输入的无序序列为：26 5 37 1 61 11 59 15 48 192、出要求：对每种算法均需输出原始数据序列、每趟排序的中间结果序列和最后排好序的有序序列。3、实验中要求应用四种方法进行排序，其中包括直接插入排序、简单选择排序、快速排序和希尔排序。能灵活应用几种不同的方法进行计算机内部排序，了解其中的排序原理，并能根据具体情况选择最优的方法排序。5、程序源代码及解释#include #define LS(a,b) (a)(b) /比较，以简化代码#define MAXSIZE 50typedef int KeyType;typedef struct /

23、自定义数据结构 int key;RedType;typedef struct RedType rMAXSIZE+1; /定义一个RedType类型多大数组 int length;SqList;typedef SqList HeapType;int change=0; /用以记录在具体的排列中交换的次数*建立排序数组*int Create_Sq(SqList &L) int i,k,n; coutk; L.length=k; for(i=1;i=k;+i) /次循环用以数组中数据元素的输入 cout请输入第in; L.ri.key=n; return 1;*直接插入排序*void InsertS

24、ort(SqList &L) int i,j; coutendl; for(i=2;i=L.length;+i) if(LS(L.ri.key,L.ri-1.key) /第i个与第i-1个数进行比较若后面的一个比/前面的一个小 则进行一下操作 +change; /记录调换的次数 L.r0=L.ri; /哨兵记录的i 个数并与前面一个输调换 L.ri=L.ri-1; for(j=i-2;LS(L.r0.key,L.rj.key);-j) /第i 个数与前面I -2个数比/较并调换 L.rj+1=L.rj; L.rj+1=L.r0; cout经change次调换以后的序列为：; for(j=1;j

25、=L.length;j+) / cout L.rj.key; /输出中间调换的过程 coutendl; cout最终结果：endl; for(i=1;i=L.length;i+) cout L.ri.key; coutendl; change=0; /简单选择排序/void SelectSort(SqList &L) int l,i,j; coutendl; for(i=1;iL.length;+i) L.r0=L.ri; j=i+1; l=i; for(j;j=L.length;+j) /前面i-1个已经有序地i个与后面的比较找/出其中最小的与地i个交换 if(LL(L.r0.key,L.r

26、j.key) /第i个比地j个大需调换 l=j; L.r0=L.rj; if(l!=i) /若i不是后面书中最小的需调换 +change; L.rl=L.ri; L.ri=L.r0; cout经change次调换以后的序列为：; for(j=1;j=L.length;j+) cout L.rj.key; / 输出中间过程 coutendl; cout最终结果：endl; for(i=1;i=L.length;i+) cout L.ri.key; coutendl; change=0; *快速排序*int Partition(SqList &L,int low,int high)/交换顺序表L中

27、子表Llow high的记录 使枢轴记录到位，并返回其所在位置/此时它之前（后）的记录均不小(大)与它 int pivotkey; L.r0=L.rlow; pivotkey=L.rlow.key; /用第一个作为枢轴记录 while(lowhigh) /从表的两边交替的向中间扫描 while(low=pivotkey) -high; +change; L.rlow=L.rhigh; /将比枢轴小的交换到低端 cout经第change次调换以后的序列为：; for(int j=1;j=L.length;j+) cout L.rj.key; coutendl; while(lowhigh&L.r

28、low.key=pivotkey) +low; +change; L.rhigh=L.rlow; /将比枢轴大的交换到高端 cout经第 change次调换以后的序列为：; for(j=1;j=L.length;j+) cout L.rj.key; coutendl; L.rlow=L.r0; return low; / 返回枢轴的位置 void QSort(SqList &L,int low,int high) int pivotloc; if(lowhigh) pivotloc=Partition(L,low,high); /将Llow-high一分为二 QSort(L,low,pivot

29、loc-1); /对低端表递归排序，pivotloc是枢轴的位置 QSort(L,pivotloc+1,high);/ 对高端表进行递归排序 /希尔排序/void ShellInsert(SqList &L,int dk)/对顺序表进行一次希尔排序 增量为dk int i; int j; for(i=dk+1;i0&LS(L.r0.key,L.rj.key);j-=dk) +change; L.rj+dk=L.rj; / 记录后移 查找插入的位置 L.rj+dk=L.r0; /插入 cout依次调换以后的序列：; for(j=1;j=L.length;j+) cout L.rj.key; co

30、ut=0) +t;/计算dlta中应出入的数的个数 j-=2; j=L.length/2; for(k=0;kt;+k) if(j=0) j=1;/最后一趟排序的增量 dltak=j; j-=2; for(k=0;kt;+k) ShellInsert(L,dltak); cout最终结果：endl; for(k=1;k=L.length;k+) cout L.rk.key;coutendl;change=0; void main() int i; int dltaMAXSIZE; SqList L; Create_Sq(L); cout-待排序序列为-endl; for(i=1;i=L.len

31、gth;i+) cout L.ri.key;coutendl;cout-1.直接插入排序-endl; SqList L1=L; InsertSort(L1);cout-2.简单选择排序-endl; SqList L2=L; SelectSort(L2);cout-3.快速排序-endl; SqList L3=L; QuickSort(L3);cout-4.希尔排序-endl; SqList L4=L; ShellSort(L4,dlta); 6、实验感想 就我来说此次试验较以前的试验来说思考起来比较难，是参考资料所得。由于在编写的过程中主要是照抄书上的几种方法的代码，其中并没有多少自己的创意。

32、但使我对内部排序有了一个更深的理解，并提高了分析问题的能力。在实验中运用到了所有学的四种内部排序的方法，并且加强了对快速排序和希尔排序的理解和应用，并切实体验到了这两种排序方法较其他方法的优点。在实验中用了一个change变量对顺序表具体的调换次数进行了一个记录，在几种排序方法中明显感受到后面两种方法的时间和空间效率与前两种要好许多。因为对于前面的两种方法有比较多的接触，所以理解起来相对容易一些，但这两种方法的空间和时间效率并不理想。通过此次四个实验的综合练习，我总结出对自己有益处的三条经验：(1)实验前，要做好预习工作，阅读课本上的知识，从而初步找出自己的不足，再认真思考自己不懂的地方，自己

33、也能熟练掌握之前老师讲授过的的知识，便于编好程序。(2)在进实验室之前要将程序编好，至少要编出个大概，带着问题到实验室，抓紧时间问老师和同学，及时发现问题，解决问题，有效地完成应做的实验。 (3)自己平时要多看看书，并且多多使用下软件，熟悉了Microsoft Visual C+的环境，使自己为以后的数据结构实验做好准备。总之，对于前三个实验，我觉得自己是真正的掌握了，不像以前一知半解，使得自己加深了对数据结构的兴趣和自信。至于第四个，虽然是参考资料做出，但仍然加深了我对内部排序的理解。通过这次实验我从中也学到了不少知识。虽然都说“程序数据结构算法”，但我在学习运用数据结构编程之前，并没能深刻

34、体会到这一点，直到这次课设实践。我感受最深的一点是：以前用C+编程，只是注重如何编写函数能够完成所需要的功能，并没有一个更为明确的目标，只是凭单纯的意识和简单的语句来堆砌出一段程序，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，分清它们之间的区别，然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。我以前对递归算法一直很害怕，总是看不明白究竟这递归是怎么进行的。在这次实验中我终于克服了这一障碍，写出了递归算法，虽然是比较简单的一种，但仍然是一个突破。 总体来说，这几次的实验让我受益颇多，也对数据结构有了全新的认识。