东北林业大学-数据结构实验指导书2023年级

数据构造实验指导书2计算机科学与技术专业目录TOC\o“1-2“\h\z\u\l“_TOC_250012“试验目的与要求 1\l“_TOC_250011“试验环境 1\l“_TOC_250010“试验一般步骤 1\l“_TOC_250009“试验时数 2\l“_TOC_250008“试验内容和要求 3\l“_TOC_250007“试验一 线性表的挨次存储构造 3\l“_TOC_250006“试验二 链式存储构造〔一〕单向链表的有关操作………………… 4\l“_TOC_250005“试验三 链式存储构造〔二〕双向链表的有关操作 5\l“_TOC_250004“试验四 栈和队列的有关操作 6\l“_TOC_250003“试验五 二叉树的常见操作 7\l“_TOC_250002“试验六 图的有关操作 8\l“_TOC_250001“试验七 查找的有关操作 9\l“_TOC_250000“试验八 排序的有关操作 10试验目的与要求从以往的教学事先实习的阅历来看，在初学阶段执行严格的实习步骤标准〔包括上机〕，机时利用率会大大提高，有助于养成良好的程序编制风格，培育严谨、科学、高效的工作方式。其害的。实习步骤标准不但可以培育科学化的工作作风，而且还能有效地避开错误。试验环境计算机的硬件配置PC计算机的软件配置DOS6.22Windows98、Windowsxp、Windows2023。CTurboCV3.0，VisualC++6.0。试验一般步骤⑴问题分析与系统的构造设计充分地分析和理解问题本身，弄清要求作什么，限制条件是什么。依据以数据构造为中心的原则划分模块，即定义数据构造及其在这些构造之上的操作，使得对数据构造的存合理、简洁并且易于调试。最终写出每个子程序〔过程或函数〕的规格说明，列出它们之间的调用关系，可以使用调用关系图表示则更加清楚，这样便完成了系统构造设计。⑵具体设计和编码具体设计的目的是对子程序〔过程或函数〕的进一步求精。用IF、WHILE以对具体设计的结果进一步求精，用高级语言表示出来。60〔或过程、函数〕通常不要太长，40〔或过程、函数〕包含的程序行数太多，易于造成理解的困难。掌握用，除格外明显的除外〔如：x=x+1;x1，没有什么意义〕，都应加以注释。这中的有关规定。⑶上机预备和静态检查①高级语言文本②生疏机器的用户手册，生疏常用的命令。自己先设计一些以供使用。④静态检查的规律。⑷上机调试程序后将源程序和运行结果加以列印输出。⑸实习报告的整理①需求及规格说明问题描述，求解的问题是什么。②设计：设计思想：存储构造、主要的算法思想。〔过程或函数〕的规格说明，通过调用关系图表示它们之间的调用关系。实现注释：具体设计表示：主要算法的框架。③用户手册：使用说明。等。⑤附录用英文描述。⑥试验报告要求：电子文档的形式进展书写。试验时数总试验时数不得少于16学时。试验内容和要求程中，对各种算法的时、空简单性的分析，将帮助您在更高的角度解决各种应用问题。〔1〕试验题目、班级、学号、；〔2〕简要的需求分析与概要设计；〔3〕具体的算法描述；〔4〕程序清单与运行结果；〔5〕收获与体会。试验一线性表的挨次存储构造一、试验学时：2学时挨次表的插入、删除及应用。三、目的要求：⑴把握挨次存储构造的特点。⑴输入一组整型元素序列，建立挨次表。四、试验内容：⑴输入一组整型元素序列，建立挨次表。⑵实现该挨次表的遍历。⑵实现该挨次表的遍历。1，0。1，0。⑸实现把该表中全部奇数排在偶数之前，即表的前面为奇数，后面为偶数。⑸实现把该表中全部奇数排在偶数之前，即表的前面为奇数，后面为偶数。⑹输入整型元素序列利用有序表插入算法建立一个有序表。6⑻编写一个主函数，调试上述算法。〔查找等〕五、试验说明：17⑵存储定义#defineMAXSIZE100 中元素的最大个数typedefint ElemType；//元素类型typedefstructlist{ElemTypeelem[MAXSIZE]；//静态线性表intlength； //表的实际长度}SqList；//挨次表的类型名六、留意问题：解不同的函数形参与实参的传递关系。试验二链式存储构造〔一〕单向链表的有关操作一、试验学时：２学时单向链表的插入、删除及应用。三、目的要求：⑴把握单向链表的存储特点及其实现。四、试验内容：⑴随机产生或键盘输入一组元素，建立一个带头结点的单向链表〔无序〕。⑵遍历单向链表。⑶把单向链表中元素逆置〔不允许申请的结点空间〕。⑷在单向链表中删除全部的偶数元素结点。立一个非递减有序单向链表。55全部为偶数〔尽量利用的存储空间〕。*⑼承受单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。⑽在主函数中设计一个简洁的菜单，分别调试上述算法。〔数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中〕五、试验说明：⑴类型定义#include<stdio.h>typedefint 元素类型typedef structLNode{ElemTypedata；structLNode*next；}LNode，*LinkList；六、留意问题：⑴重点理解链式存储的特点及指针的含义。⑵留意比较挨次存储与链式存储的各自特点。⑶留意比较带头结点、无头结点链表实现插入、删除算法时的区分。⑷单向链表的操作是数据构造的根底，肯定要留意对这局部的常见算法的理解。试验三链式存储构造〔二〕双向链表的有关操作一、试验学时：２学时双向链表的插入、删除及应用。三、目的要求：⑴把握双向链表的存储特点及其实现。四、试验内容：⑴利用尾插法建立一个双向链表。⑵遍历双向链表。⑶实现双向链表中删除一个指定元素。e10。⑹设元素为正整型，实现算法把全部奇数排列在偶数之前。五、双向链表的类型定义：typedef intElemType；//元素类型typedef structDuLNode{ ElemTypedata；structDuLNode*prior，*next；}DuLNode，*DuLinkList；六、留意问题：留意比较单向、双向链表的特点。试验四栈和队列的有关操作一、试验学时：２学时二、背景学问：入栈、出栈，入队、出队。三、目的要求：⑴把握栈、队列的思想及其存储实现。四、试验内容：⑴承受链式存储实现栈的初始化、入栈、出栈操作。⑵承受挨次存储实现栈的初始化、入栈、出栈操作。⑶承受链式存储实现队列的初始化、入队、出队操作。⑷承受挨次存储实现循环队列的初始化、入队、出队操作。⑸在主函数中设计一个简洁的菜单，分别测试上述算法。*⑹综合训练：①利用栈实现表达式求值算法。五、试验说明：1、32、4#defineMAX100//栈的最大值typedefstruct{ ElemType*base；inttop；}SqStack；#defineMAX100//队列的最大长度typedefstruct{ ElemType*base；intfront，rear；}SqQueue；六、留意问题：⑴重点理解栈、队列的算法思想，能够依据实际状况选择适宜的存储构造。6⑶栈、队列的算法是后续试验的根底〔广义表、树、图、查找、排序等〕。试验五二叉树的常见操作一、试验学时：２学时二叉树的存储、建立、遍历及其应用。三、目的要求：⑴把握二叉树的存储实现。⑵把握二叉树的遍历思想。四、试验内容：⑴输入字符序列，建立二叉链表。⑵中序遍历二叉树：递归算法。⑶中序遍历二叉树：非递归算法。〔最好也能实现先序，后序非递归算法〕⑷求二叉树的高度。⑸求二叉树的叶子个数。*⑹将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。*⑺建立中序线索二叉树，并实现中序遍历。⑻借助队列实现二叉树的层次遍历。⑼在主函数中设计一个简洁的菜单，分别调试上述算法。五、试验说明：//二叉链表存储#defineElemTypechar//元素类型typedefstructBiTNode{ ElemTypedata；structBiTNode*lchild，*rchild；}BiTNode，*BiTree；六、留意问题：⑴留意理解递归算法的执行步骤。⑵留意字符类型数据在输入时的处理。⑶重点理解如何利用栈构造实现非递归算法。试验六图的有关操作一、试验学时：２学时图的存储、遍历、及其应用。三、目的要求：⑴把握图的存储思想及其存储实现。⑵把握图的深度、广度优先遍历算法思想及其程序实现。四、试验内容：⑴键盘输入数据，建立一个有向图的邻接表。⑵输出该邻接表。*⑶建立一个无向图的十字链表。⑷在有向图的邻接表的根底上计算各顶点的度，并输出。⑸以有向图的邻接表为根底实现输出它的拓扑排序序列。*⑹承受邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。⑺承受邻接表存储实现无向图的深度优先非递归遍历。⑻承受邻接表存储实现无向图的广度优先遍历。*⑼PRIM*⑽推断无向图任意两个顶点间是否有路径，假设有输出路径上的顶点序列。⑾在主函数中设计一个简洁的菜单，分别调试上述算法。4250课程，每学期所开课程门数尽量均衡，课程的安排必需满足先修关系。五、试验说明：⑴类型定义〔邻接表存储〕#defineMAX_VERTEX_NUM8 typedefstructArcNode{ int adjvex；structArcNode*nextarc；intweight；//边的权}ArcNode； //表结点#defineVertexTypeint//顶点元素类型typedefstructVNode{intdegree，indegree；//顶点的度，入度VertexTypedata；ArcNode*firstarc；头结点*/，AdjList[MAX_VERTEX_NUM]；typedefstruct{AdjListvertices；intvexnum，arcnum；//顶点的实际数，边的实际数}ALGraph；⑵上述类型定义可以依据实际状况适当调整。六、留意问题：⑴留意理解各算法实现时所承受的存储构造。⑵留意区分正、逆邻接。试验七查找的有关操作一、试验学时：2学时挨次查找、树表查找、散列查找。三、目的要求：⑴把握折半查找算法的思想及程序实现。⑵把握二叉排序树、AVL的查找、建立。四、试验内容：⑴利用试验一建立有序表，承受折半查找实现某一的关键字的查找。指定关键字元素。*⑶建立ＡＶＬ树并实现删除某一指定关键字元素。〕，冲突处理方法分别为线性探测法、外拉链法实现散列表的建立〔利用插入算法实现〕。五、试验说明：⑴存储定义〔散列表的外拉链法〕#definen9typedefstructnode{intkey；structnode*next；}NODE；NODE*HashTable[9]；算法1、2、3可以参考挨次表，二叉链表的存储实现。⑵各种关键字数据输入可利用随机函数自动产生，以便节约上机时间。1seqlist.h2、3bintree.h4hash.h六、留意问题：⑴留意理解折半查找的适用条件〔链表能否实现折半查找？〕。⑵留意建立二叉排序树、散列表时一样元素的处理。⑶留意理解静态查找、动态查找概念。⑷比较各种查找算法的各自特点，能够依据实际状况选择适宜的查找方法。试验八排序的有关操作一、试验学时：２学时各种排序方法三、目的要求：⑴把握常见的排序算法的思想及其适用条件。四、试验内容：输入一组关键字序列分别实现以下排序：⑴实现简洁选择排序、直接插入排序和冒泡排序。⑵实现希尔排序算法。⑶实现快速排序算法。⑷实现堆排序算法。*⑸快速排序的