数据结构-试验指导书

1、数据结构实验指导书计算机专业实验中心编2020年5月25日数据结构上机实验内容和要求错误!未定义书签实验一、顺序表的实现及应用错误!未定义书签实验二、链表的实现及应用错误!未定义书签实验三、栈的实现及应用错误!未定义书签实验四、队列的实现及应用错误!未定义书签实验五、二叉树操作及应用错误!未定义书签实验六、图的遍历操作及应用错误!未定义书签实验七、查找算法的实现错误!未定义书签实验八、排序算法的实现错误!未定义书签数据结构上机实验内容和要求通过上机实验加深对课程内容的理解，增加感性认识，提高程序设计、开发及调试能力。本实验指导书适用于16学时数据结构实验课，实验项目具体内容如下：序号实验名称内

2、容提要每组人数实验时数实验要求实验类别分值(总100分)1顺序表的实现及应用掌握顺序表结构， 实现其插入、删除等算法。利用顺序表将两个启序线性表合并升-个有序表。12必做设计10分2链表的实现及应用掌握单链表结构， 实现其插入、删除、查找等算法。利用单链表将两个启序链表合并力-个后序链表。12必做设计10分3栈的实现及应用掌握栈的结构，将栈应用于表达式计算问题12必做设计15分4队列的实现及应用掌握队列的结构，将队列应用于模拟服务台前的排队现象问题12必做设计15分5二叉树操作及应用掌握二叉树的存储，实现三种遍历的递归算法、实现前序或中序的非递归遍历算法12必做设计15分6图的遍历操作及应用实

3、现图的存储、深度遍历和广度遍历算法12必做设计10分7查找算法的实现实现顺序表的二分查找算法12必做设计10分8排序算法的实现实现直接插入排序、快速排序等算法12必做设计15分实验报告要求请按照实验教师要求，按时提交实验报告电子版文件。实验报告格式可个性化定义，内容包括但不限于以下内容：1、题目、姓名、学号、班级(首页)2、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：(1)输入的形式和输出值的范围；(2)输出的形式；(3)程序所能达到的功能；(4)测试数据：包括正确的输入输出结果和错误的输入及输出结果。3、概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。

4、4、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。5、调试分析：(1)调试过程中所遇到的问题及解决方法；(2)算法的时空分析；(3)经验与体会。6、用户使用说明：说明如何使用你设计的程序，详细列出每序操作简单，可略去)7、测试结果：列出对于给定的输入所产生的输出结果。的增长所用算法的实际运行时间的变化)8、总结步操作步骤。(如果程(若有可能，测试随输入规模实验一、顺序表的实现及应用一、实验目的了解和掌握线性表的顺序存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性

5、能分析。二、实验要求给定一段程序代码，程序代码所完成的功能为：(1)建立一个线性表；(2)依次输入数据元素1,2,3,4,5,6,7,8,9,10;(3)删除数据元素5;(4)依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用顺序表。程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，修改后上机调试得到正确的运行结果。三、程序代码#include#defineMaxSize100typedefintDataType;typedefstructDataTypelistMaxSize;intsize;Seq

6、List;voidListInitiate(SeqList*L)/*初始化顺序表L*/L-size=0;/*定义初始数据元素个数*/intListLength(SeqListL)/*返回顺序表L的当前数据元素个数*/return;intListInsert(SeqList*L,inti,DataTypex)/*在顺序表L的位置i(0wisize=MaxSize）（printf（顺序表已满无法插入！n）;return0;elseif（iL-size）（printf（参数i不合法！n）;return0;else（正上述程序中的错误（必作）。2.编写合并函数，将两个有序线性表合并为一个有序表并在主函

7、数中加以测试（选作）3.完成实验报告的撰写。实验二、链表的实现及应用一、实验目的了解和掌握线性表的链式存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。二、实验要求给定一段程序代码，程序代码所完成的功能为：(1)建立一个线性表；(2)依次输入数据元素1,2,3,4,5,6,7,8,9,10;(3)删除数据元素5;(4)依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用单链表。程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的

8、代码仔细分析后，要求同学们修改错误的代码，上机调试并得到正确的运行结果。三、程序代码：#include/*该文件包含pringtf()等函数*/#include/*该文件包含exit()等函数*/#include/*该文件包含malloc()等函数*/typedefintDataType;/*定义DataType为int*/typedefstructNodeDataTypedata;structNode*next;SLNode;voidListInitiate(SLNode*head)/*初始化*/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/if(*head=(SLNode

9、*)malloc(sizeof(SLNode)=NULL)exit(1);(*head)-next=NULL;/*置链尾标t己NULL*/intListLength(SLNode*head)SLNode*p=head;/*p指向首元结点*/intsize=0;/*size初始为0*/while(p-next!=NULL)/*循环计数*/(p=p-next;size+;/*单链表的长度*/returnsize;intListInsert(SLNode*head,inti,DataTypex)/*在带头结点的单链表head的数据元素ai(0inext!=NULL&jnext;j+;if(j

10、!=i-1)(printf(插入位置参数错！);return0;/*生成新结点由指针q指示*/if(q=(SLNode*)malloc(sizeof(SLNode)=NULL)exit(1);q-data=x;正上述程序中的错误(必作)。2.编写合并函数，将两个有序的单链表合并成一个有序单链表(选作)3.完成实验报告的撰写。实验三、栈的实现及应用一、实验目的1.掌握栈的存储表示和实现2.掌握栈的基本操作实现。3.掌握栈在解决实际问题中的应用。二、实验要求问题描述：编写程序实现算术表达式的求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：4、从键盘上输入表达式。

11、5、分析该表达式是否合法。6、若上述处理过程中没有发现错误，则认为该表达式合法，计算并打印处理结果。三、主要功能函数参考程序中主要包含下面几个功能函数：voidinitstack()：初始化堆栈intMake_str():语法检查intpush_operate(intoperate):将操作码压入堆栈intpush_num(doublenum):将操作数压入堆栈intprocede(intoperate):处理操作码intchange_opnd(intoperate):将字符型操作码转换成优先级intpush_opnd(intoperate):将操作码压入堆栈intpop_opnd():将操作

12、码弹出堆栈intcaculate(intcur_opnd):简单计算+,-,*,/doublepop_num():弹出操作数四、实验任务认真阅读与理解实验内容的具体要求，参考教材相关章节，结合实验内容的要求，编写实验程序并上机调试与测试，完成实验报告的撰写。实验四、队列的实现及应用一、实验目的1.掌握队列的存储表示和实现。2.掌握队列的基本操作实现。3.掌握队列在解决实际问题中的应用。二、实验要求利用队列模拟服务台前的排队现象问题。问题描述：某银行有一个客户办理业务站，在单位时间内随机地有客户到达，设每位客户的业务办理时间是某个范围的随机值。设只有一个窗口，一位业务人员，要求程序模拟统计在设定

13、时间内，业务人员的总空闲时间和客户的平均等待时间。假定模拟数据已按客户到达的先后顺序依次存于某个文本数据文件中，对应每位客户有两个数据：到达时间和需要办理业务的时间。三、实验任务认真阅读与理解实验内容的具体要求，参考教材相关章节，结合实验内容的要求，编写实验程序并上机调试与测试，完成实验报告的撰写。实验五、二叉树操作及应用一、实验目的掌握二叉树的定义、结构特征，以及各种存储结构的特点及使用范围，各种遍历算法。掌握用指针类型描述、访问和处理二叉树的运算。掌握前序或中序的非递归遍历算法。、实验要求有如下二叉树:根程序代码给出了该二叉树的链式存储结构的建立、前序、中序、后序遍历的算法，同时也给出了查

14、询“奥否在二叉树里的代码。代码有三处错误，有标识，属于逻辑错误，对照书中的代码仔细分析后，请修改了在电脑里运行。#include#includetypedefcharDataType;typedefstructNode(DataTypedata;/*数据域*/structNode*leftChild;/*左子树指针*/structNode*rightChild;/*右子树指针*/BiTreeNode;/*结点的结构体定义*/*初始化创建二叉树的头结点*/voidInitiate(BiTreeNode*root)*root=(BiTreeNode*)malloc(sizeof(BiTreeNod

15、e);(*root)-leftChild=NULL;(*root)-rightChild=NULL;voidDestroy(BiTreeNode*root)if(*root)!=NULL&(*root)-leftChild!=NULL)Destroy(&(*root)-leftChild);if(*root)!=NULL&(*root)-rightChild!=NULL)Destroy(&(*root)-rightChild);free(*root);/*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/*原curr所指结点的左子树成为新插入结

16、点的左子树*/*若插入成功返回新插入结点的指针，否则返回空指针*/BiTreeNode*InsertLeftNode(BiTreeNode*curr,DataTypex)BiTreeNode*s,*t;if(curr=NULL)returnNULL;t=curr-leftChild;/*保存原curr所指结点的左子树指针*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode);s-data=x;s-leftChild=t;/*新插入结点的左子树为原curr的左子树*/s-rightChild=NULL;curr-leftChild=s;/*新结点成为curr的左子树

17、*/returncurr-leftChild;/*返回新插入结点的指针*/*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/*原curr所指结点的右子树成为新插入结点的右子树*/*若插入成功返回新插入结点的指针，否则返回空指针*/BiTreeNode*InsertRightNode(BiTreeNode*curr,DataTypex)(BiTreeNode*s,*t;if(curr=NULL)returnNULL;t=curr-rightChild;/*保存原curr所指结点的右子树指针*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode);s

18、-data=x;s-rightChild=t;/*新插入结点的右子树为原curr的右子树*/s-leftChild=NULL;curr-rightChild=s;/*新结点成为curr的右子树*/returncurr-rightChild;/*返回新插入结点的指针*/)voidPreOrder(BiTreeNode*t,voidvisit(DataTypeitem)正程序错误(必作)。2.编写二叉树的前序（或中序）的非递归遍历算法并进行测试（选作）3.完成实验报告的撰写。四、示例程序1.邻接矩阵作为存储结构的程序示例#includeV1#include#defineMaxVertexNum100ertex=a;irstedgeVNULL;iG-adjlisti.firstedge=s;irstedge;G-adjlistj.firstedge=s;ertex);irstedge;ertex);n-1中查找关键字为k的记录，成功时返回找到的记录,具体的算法如下所示：intSeqSearch(SeqListR,intn,KeyTypek)inti=0;while(i=n)return-1;else(pr