实验指导手册

《数据结构》实验指导手册计算机教研室2023.61．实验教学的目的：通过实验，加深对算法与数据结构基本知识的理解，掌握数据结构的理论和设计技术及其使用，培养学生数据结构的设计、开发能力。2．实验教学的规定：学生每次实验前必须根据实验指导手册，设计出实验方案（程序和实验环节）；在实验过程中规定独立进行程序调试和排错，必须学会使用在线帮助解决实验中碰到的问题，必须应用理论知识分析问题、解决问题。3．实验内容：实验1：VC6的使用一、实验目的理解和掌握如何使用VisualC＋＋6.0环境编写C/C＋＋程序。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计4学时。三、实验内容1、熟悉VC6环境掌握如何创建控制台应用程序。掌握一些常用快捷键，例如编译F7，运营Ctrl＋F5，调试运营F5，单步运营F10/F11，设立断点F9，格式化代码Alt＋F8。2、掌握如何编译程序理解编译过程中的错误信息，并掌握如何排错。3、掌握如何调试程序掌握如何通过设立断点来单步调试程序，如何查看当前变量的值。4、实验题：完毕实验教材的实验题1.1、1.2、1.3。规定：实现该实验结果。通过该实验题，熟悉VC6环境下的程序编写、编译、调试。实验2：顺序表基本运算一、实验目的（1）掌握顺序表的各种基本运算的实现。（2）可以运用基本运算进行顺序表的操作。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计2学时。三、实验内容1、顺序表基本运算实现顺序表的各种基本运算；并在此基础上设计一个主程序，完毕如下功能：初始化顺序表L（元素类型为char型）依次采用尾插法插入a,b,c,d,e元素输出顺序表L输出顺序表L的长度判断顺序表L是否为空输出顺序表L的第3个元素输出元素’a’的位置在第4个元素位置上插入’f’元素输出顺序表L删除顺序表L的第3个元素输出顺序表释放顺序表提醒：可以参考上课教材、实验教材的实验题2.1。2、顺序表的应用（选做）（1）设计通讯录（也可为其他应用）文献的存储格式和线性表的顺序存储结构（2）设计在通讯录（也可为其他应用）中添加、删除、查找某个节点信息程序（3）调试程序实验3：单链表基本运算一、实验目的（1）掌握链表的概念；掌握单链表的各种基本运算的实现。（2）可以运用基本运算进行单链表的操作。（3）加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计2学时。三、实验内容实现单链表的各种基本运算；并在此基础上设计一个主程序，完毕如下功能：（1） 初始化单链表L（2） 依次采用尾插法插入a,b,c,d,e元素（3） 输出单链表L（4） 输出单链表L的长度（5） 判断单链表L是否为空（6） 输出单链表L的第3个元素（7） 输出元素’a’的位置（8） 在第4个元素位置上插入’f’元素（9） 输出单链表L（10） 删除单链表L的第3个元素（11） 输出单链表L（12） 释放单链表L提醒：可以参考上课教材、实验教材的实验题2.2。实验4：单链表综合实验一、实验目的（1）可以运用单链表的基本运算进行单链表的相关操作。（2）掌握文献的应用（3）加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计4学时。三、实验内容1、通讯录设计设计一个班级同学的通讯录，规定如下：通讯录中每个同学的信息包含以下内容：学号（id）、姓名（name）、电话号码（tel）。假如需要更多其他信息，请自行添加。程序主菜单包含以下几个功能：添加记录：通过键盘输入信息，添加一条通讯录记录。删除记录：通过键盘输入学号，删除该学号的记录。输出记录：输出通讯录所有记录。按姓名查找：通过键盘输入姓名，输出该同学的所有信息。保存记录：把通讯录中所有的记录保存到文献中。清空记录：删除通讯录中的所有记录，并删除文献。退出提醒：程序启动时应判断是否存在记录文献，假如存在，则读取每条记录到链表中。用户选择并完毕主菜单某功能后，除了退出程序，应当返回主菜单。添加一条记录时，插入到链表的尾部。查找、删除记录时，假如该记录不存在，则应当输出不存在的提醒。添加记录、删除记录时不需要写文献。保存记录时，用覆盖写文献的方法。（或者先删除原文献，再保存所有记录信息）各个功能模块写成函数，由主函数调用。选做：主菜单增长一个排序功能选项，可以按照学号从小到大进行排序。排序方法可以用冒泡排序或者插入排序。实验5：链栈的基本操作一、实验目的1）熟悉栈的定义和栈的基本操作。2）掌握链式存储栈的基本运算。3）加深对栈数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计2学时。三、实验内容必做内容：链栈的基本操作编写栈的基本操作函数栈类型的定义，数据域使用char型typedefcharElemType;typedefstructnode{ ElemTypedata; structnode*next;}LinkStack;2．初始化空栈：函数原型如下：voidInitLinkStack（LinkStack*&s）其中函数参数为LinkStack*&类型，表达指向创建的空栈的指针，并且用引用方式传入。3.判断是否空栈：函数原型如下：intIsEmptyLinkStack（LinkStack*s）其中函数参数为栈指针；返回值为int型，1表达是空栈，0表达不是空栈。4.入栈：函数原型如下：voidPushLinkStack（LinkStack*&s,ElemTypex）其中函数参数s为栈指针，x为入栈的数据。5.出栈：函数原型如下：intPopLinkStack(LinkStack*&s,ElemType&x)其中函数参数s为栈指针，x为出栈的数据的引用；返回值为int型，1表达出栈成功，0表达出栈失败。6．取栈顶元素：(栈保持不变)函数原型如下：intGetLinkStackTop(LinkStack*s,ElemType&x)其中函数参数s为栈指针，x存放栈顶元素值；返回值为int型，1表达成功，0表达失败。编写主函数调用上述函数实现下列操作。1．初始化空栈。2.键盘输入字符，使得输入的字符依次入栈（结束符号自定，例如回车键(值为10)或'#'）每插入一个元素，必须输出当时的栈顶元素(调用GetLinkStackTop函数)。3．判断链栈是否为空。输出判断结果。4．调用出栈函数，打印出栈元素的值；反复此环节，直至栈为空。5．判断链栈是否为空。输出判断结果。6．释放链栈。选做内容（一）：判断对称字符串设计一个算法，调用栈的基本运算，判断一个字符串是否为对称字符串。若是返回1；否则返回0。例如：“abcba”和“abba”都是对称字符串。实验6：队列的基本操作一、实验目的1）熟悉队列的定义和队列的基本操作。2）掌握顺序循环队列和链式存储队列的基本运算。3）加深对队列数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计2学时。三、实验内容队列的基本操作队列的存储结构从顺序循环队列或者链队任选一种。编写一个程序，实现队列的各种基本运算，并在此基础上设计一个主程序，完毕如下功能：初始化队列q判断q是否非空依次进队元素a，b，c出队一个元素，输出该元素输出队列q的元素个数依次进队列元素d，e，f输出队列q的元素个数输出出队序列释放队列实验7：栈和队列综合实验一、实验目的（1）可以运用栈和队列的基本运算进行相关操作。（2）进一步熟悉文献的应用（3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计4学时。三、实验内容以下两个实验任选一个。迷宫求解设计一个迷宫求解程序，规定如下：以M×N表达长方阵表达迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。能任意设定的迷宫（选作）假如有通路，列出所有通路提醒：以一个二维数组来表达迷宫，0和1分别表达迷宫中的通路和障碍，如下图迷宫数据为：入口位置：11出口位置：88探索过程可采用如下算法，设定当前位置的初值为入口位置；do{ 若当前位置可通， 则｛将当前位置插入栈顶； 若该位置是出口位置，则结束； 否则切换当前位置的东邻方块为新的当前位置；｝否则，｛ 若栈不空且栈顶位置尚有其他方向未经探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则｛删去栈顶位置；//从途径中删去该通道块若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块出栈至栈空； ｝｝｝while(栈不空)；2、机场飞机起降的过程模拟熟悉队列的各种基本运算，并在此基础上设计一个主程序，完毕如下功能：模拟一个机场飞机起降的过程机场仅有一条跑道，规定起飞与降落不能同时进行进场飞机若暂时没有跑道可用须在空中盘旋等候离场飞机若暂时没有跑道可用须在地面排队等候仅当空中无飞机等待降落时地面飞机方可起飞飞机的申请进场、降落、申请离场和起飞分别视为独立事件每个事件的发生占用一个时间单位。除降落和起飞外，各事件可以同时发生提醒：设定一个待飞队列用于存放排队等候的航班信息设定一个待降落队列用于存放等待降落的航班信息飞机的申请进场、降落、申请离场和起飞可以通过航班事先设定的起飞时间、飞行时间长度或者降落时间信息来拟定，这些信息可以存放在一个文献中，程序运营时从文献中读出。航班当前状态可表达为：起飞，降落，申请进场，申请离场，空闲每个事件的发生占用一个时间单位可以自己约定，起飞，降落可以设定为30分钟实验8：顺序串的基本操作一、实验目的1）熟悉串的定义和串的基本操作。2）掌握顺序串的基本运算。3）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计2学时。三、实验内容编写一个程序，实现顺序串的各种基本运算，并在此基础上设计一个主程序。具体如下：编写栈的基本操作函数顺序串类型定义如下所示：typedefstruct{charch[MAXSIZE];intlen;}SeqString;（1）串赋值Assign(s,t)将一个字符串常量赋给串s,即生成一个其值等于t的串s（2）串复制StrCopy(s,t)将串t赋给串s（3）计算串长度StrLength(s)返回串s中字符个数（4）判断串相等StrEqual(s,t)若两个串s与t相等则返回1；否则返回0。（5）串连接Concat(s,t)返回由两个串s和t连接在一起形成的新串。（6）求子串SubStr(s,i,j)返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。（7）插入InsStr(s,i,t)将串t插入到串s的第i(1≤i≤StrLength(s)+1)个字符中,即将t的第一个字符作为s的第i个字符,并返回产生的新串（8）串删除DelStr(s,i,j)从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j的子串,并返回产生的新串。（9）串替换RepStr(s,s1,s2)在串s中,将所有出现的子串s1均替换成s2。（10）输出串DispStr(s)输出串s的所有元素值（11）判断串是否为空IsEmpty(s)编写主函数调用上述函数实现下列操作：建立串s=“abcdefghijklmn”，串s1=“xyz”，串t＝“hijk”复制串t到t1，并输出t1的长度在串s的第9个字符位置插入串s1而产生串s2，并输出s2删除s第2个字符开始的5个字符而产生串s3，并输出s3将串s第2个字符开始的3个字符替换成串s1而产生串s4，并输出s4提取串s的第8个字符开始的4个字符而产生串s5，并输出s5将串s1和串t连接起来而产生串s6，并输出s6比较串s1和s5是否相等，输出结果实验9：矩阵的基本操作一、实验目的1）熟悉数组、矩阵的定义和基本操作。2）掌握对称矩阵、稀疏矩阵等特殊矩阵的存储方式和基本运算。3）加深对数组、矩阵的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计2学时。三、实验内容以下两个实验任选一个。1、实现稀疏矩阵的转置、求和假设m×n的稀疏矩阵用三元组表达，编写一个程序实现如下功能：生成如下两个稀疏矩阵的三元组a和b，并输出三元组表达。103010300100001000103000040000100002提醒：程序中可以用intA[4][4]和B[4][4]二维数组表达原始矩阵A和B。输出a的转置矩阵的三元组表达。设c＝a＋b，输出c的三元组表达。2、求对称矩阵之和、乘积已知A和B为两个n×n阶的对称矩阵，编写一个程序实现：将其下三角元素存储在一维数组a和b中，并输出。112411241235234645671111111111111111提醒：程序中可以用intA[4][4]和B[4][4]二维数组表达原始矩阵A和B。设C＝A＋B，以矩阵方式输出C。设D＝A×B，以矩阵方式输出D。实验10：字符串综合实验一、实验目的1）熟悉串的定义和串的基本操作。2）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计4学时。三、实验内容以下两个实验任选一个。1、凯撒加密算法凯撒密码（caeser）是罗马扩张时期朱利斯•凯撒（JuliusCaesar）发明的，用于加密通过信使传递的作战命令。它将字母表中的字母移动一定位置而实现加密。他的原理很简朴，说到底就是字母与字母之间的替换。每一个字母按字母表顺序向后移3位，如a加密后变成d，b加密后变成e，······x加密后变成a，y加密后变成b，z加密后变成c。例如：“baidu”用凯撒密码法加密后字符串变为“edlgx”。试写一个算法，将键盘输入的文本字符串（只包含a～z的字符）进行加密后输出。另写一个算法，将已加密后的字符串解密后输出。提醒：假如有字符变量c加密后则＝’a’＋（c-‘a’＋3）％26采用顺序结构存储串，键盘输入字符串后保存到顺序串中；输出用顺序串的输出函数。2、求一个串中出现的第一个最长反复子串 采用顺序结构存储串，编写一个程序，求串s中出现的第一个最长反复子串的下标和长度。实验11：递归综合实验一、实验目的1）熟悉递归的定义和递归的算法设计。2）加深对递归算法的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计4学时。三、实验内容以下两个实验任选一个。1、求解n皇后问题编写一个程序，求解皇后问题：在n×n的方格棋盘上，放置n个皇后，规定每个皇后不同行、不同列、不同对角线。 规定：使用递归算法求解；皇后的个数n由用户输入，其值不能超过20。2、求解汉诺塔问题 设有3个分别命名为X,Y和Z的塔座,在塔座X上有n个直径各不相同,从小到大依次编号为1,2,…,n的盘片,现规定将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放,盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X,Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法。规定：使用递归算法求解；盘片的个数n由用户输入，其值不能超过12。实验12：二叉树的操作一、实验目的1）熟悉二叉树树的基本操作。2）掌握二叉树的实现以及实际应用。3）加深二叉树的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计4学时。三、实验内容1、二叉树的基本操作【问题描述】 现需要编写一套二叉树的操作函数，以便用户可以方便的运用这些函数来实现自己的应用。其中操作函数涉及：创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表达法的字符串*str生成相应的链式存储结构。输出二叉树DispBTNode(*b)：以括号表达法输出一棵二叉树。查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,其高度等于左子树与右子树中的最大高度加l。求二叉树的结点个数NodesCount(BTNode*b) 先序遍历的递归算法：voidPreOrder(BTNode*b) 中序遍历的递归算法：voidInOrder(BTNode*b) 后序遍历递归算法：voidPostOrder(BTNode*b)层次遍历算法voidLevelOrder(BTNode*b)【基本规定】实现以上9个函数。主函数中实现以下功能：创建下图中的树b输出二叉树b找到’H’节点，输出其左右孩子值输出b的高度输出b的节点个数输出b的四种遍历顺序AABDCEHJKLMNFGI【实验提醒】数据结构的定义：#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ ElemTypedata; /*数据元素*/ structnode*lchild; /*指向左孩子*/ structnode*rchild; /*指向右孩子*/}BTNode;各个函数的定义：voidCreateBTNode(BTNode*&b,char*str);BTNode*FindNode(BTNode*b,ElemTypex);intBTNodeDepth(BTNode*b);voidDispBTNode(BTNode*b);intNodesCount(BTNode*b);voidPreOrder(BTNode*b);voidInOrder(BTNode*b);voidPostOrder(BTNode*b);voidTravLevel(BTNode*b);主函数的结构：voidmain(){ BTNode*b,*p,*lp,*rp;; charstr[]="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"; CreateBTNode(b,str); printf("\n"); printf("输出二叉树:");DispBTNode(b);printf("\n"); printf("'H'结点:"); p=FindNode(b,'H'); if(p!=NULL) { //此处输出p的左右孩子节点的值 } printf("\n"); printf("二叉树b的深度:%d\n",BTNodeDepth(b)); printf("二叉树b的结点个数:%d\n",NodesCount(b)); printf("\n"); printf("先序遍历序列:\n"); printf("递归算法:");PreOrder(b);printf("\n"); printf("中序遍历序列:\n"); printf("递归算法:");InOrder(b);printf("\n"); printf("后序遍历序列:\n"); printf("递归算法:");PostOrder(b);printf("\n");printf("层次遍历序列:");printf("\n"); TravLevel(b);printf("\n");}2.2二叉树的线索化【问题描述】编写一个程序，实现中序线索化二叉树，输出线索中序序列。【基本规定】用上图的二叉树b来验证你的程序。【实验提醒】数据结构的定义：#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ ElemTypedata; intltag,rtag;/*增长的线索标记*/ structnode*lchild; structnode*rchild;}TBTNode;TBTNode*pre;各个函数的定义：voidCreateTBTNode(TBTNode*&b,char*str)voidDispTBTNode(TBTNode*b)voidThread(TBTNode*&p)TBTNode*CreaThread(TBTNode*b)/*中序线索化二叉树*/voidThInOrder(TBTNode*tb)主函数的结构：voidmain(){ TBTNode*b,*tb; CreateTBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树:");DispTBTNode(b);printf("\n"); tb=CreaThread(b); printf("线索中序序列:");ThInOrder(tb);printf("\n");}3．实验结果此处填写程序运营结果。4．实验心得此处填写你的实验心得体会。实验13：哈夫曼编码一、实验目的1）熟悉哈夫曼树的基本操作。2）掌握哈夫曼编码的实现以及实际应用。3）加深对哈夫曼树、哈夫曼编码的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计4学时。三、实验内容【问题描述】 运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传输时间，减少传输成本。但是，这规定发送端通过一个编码系统对数据进行编码，在接受端将传来的数据进行译码。试为这样的信息收发站写一个哈夫曼编码/译码系统。【基本规定】本系统应实现以下功能：（功能1～3必做，4为选做，请课后自行完毕）初始化：字符集（字母a～z，空格）共27个字符，以及其权值。建立哈夫曼树。并建立各个字符的哈夫曼编码。打印字符集的哈夫曼编码。编码：从终端读入字符串，实现该字符串的编码。译码：实现刚才生成的哈夫曼编码还原为字符串。（选做）【已知条件】 （1）字符集的权值如下表：【实验提醒】数据结构的定义：#defineN50 /*叶子结点数*/#defineM2*N-1 /*树中结点总数*/typedefstruct{ chardata; /*结点值*/ intweight; /*权重*/ intparent; /*双亲结点*/ intlchild; /*左孩子结点*/ intrchild; /*右孩子结点*/}HTNode;typedefstruct{ charcd[N]; /*存放哈夫曼码*/ intstart;}HCode;各个函数的定义：voidCreateHT(HTNodeht[],intn) /*创建哈夫曼树*/voidCreateHCode(HTNodeht[],HCodehcd[],intn) /*创建哈夫曼编码*/voidDispHCode(HTNodeht[],HCodehcd[],intn) /*显示各个字符的哈夫曼编码*/voidEncode(char*s,HTNodeht[],HCodehcd[],intn)/*显示字符串s的哈夫曼编码*/主函数的结构： charstr[]={'','a','b','c','d','e','f','g','h','i','j','k','l','m','n', 'o','p','q','r','s','t','u','v','w','x','y','z'};/*字符集*/ intfnum[]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57, 63,15,1,48,51,80,23,8,18,1,16,1};/*字符集相应的权值*/ CreateHT(); CreateHCode(); DispHCode();gets(s); Encode();实验14：图的存储和遍历一、实验目的1）熟悉图的基本操作。2）掌握图的存储实现以及遍历操作。3）加深对图的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计2学时。三、实验内容【基本规定】1、用邻接矩阵存储方式，表达下面的图，并输出。2、由上面的邻接矩阵产生邻接表，并输出。3、编程完毕从顶点0开始的深度优先遍历和广度优先遍历。【输出结果】输出结果例子如下：有向图G的邻接矩阵:有向图G的邻接矩阵:050700004000800009005006000500300010图G的邻接矩阵转换成邻接表:0:131:22:053:254:35:04从顶点0开始的DFS:012543从顶点0开始的BFS:013254【提醒】#include<stdio.h>#include<malloc.h>#define MAXV100 /*最大顶点个数*/#defineINF32767/*INF表达∞*/typedefintInfoType;/*以下定义邻接矩阵类型*/typedefstruct{ intno; /*顶点编号*/ InfoTypeinfo; /*顶点其他信息*/}VertexType; /*顶点类型*/typedefstruct /*图的定义*/{ intedges[MAXV][MAXV]; /*邻接矩阵*/ intvexnum,arcnum; /*顶点数，弧数*/ VertexTypevexs[MAXV]; /*存放顶点信息*/}MGraph; /*图的邻接矩阵类型*//*以下定义邻接表类型*/typedefstructANode /*弧的结点结构类型*/{ intadjvex; /*该弧的终点位置*/ structANode*nextarc; /*指向下一条弧的指针*/ InfoTypeinfo; /*该弧的相关信息,这里用于存放权值*/}ArcNode;typedefintVertex;typedefstructVnode /*邻接表头结点的类型*/{ Vertexdata; /*顶点信息*/ArcNode*firstarc; /*指向第一条弧*/}VNode;typedefVNodeAdjList[MAXV]; /*AdjList是邻接表类型*/typedefstruct{ AdjListadjlist; /*邻接表*/intn,e; /*图中顶点数n和边数e*/}ALGraph; /*图的邻接表类型*/intvisited[MAXV]; /*全局数组*/voidMatToList(MGraph,ALGraph*&); /*邻接矩阵转为邻接表*/voidDispMat(MGraph); /*输出邻接矩阵*/voidDispAdj(ALGraph*); /*输出邻接表*/voidDFS(ALGraph*G,intv); /*深度优先遍历*/voidBFS(ALGraph*G,intv); /*广度优先遍历*/voidmain(){ inti,j; MGraphg; ALGraph*G; intA[MAXV][6]={ {0,5,0,7,0,0}, {0,0,4,0,0,0}, {8,0,0,0,0,9}, {0,0,5,0,0,6}, {0,0,0,5,0,0}, {3,0,0,0,1,0}}; g.vexnum=6;g.arcnum=10; for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) g.edges[i][j]=A[i][j]; printf("\n"); printf("有向图G的邻接矩阵:\n"); DispMat(g); G=(ALGraph*)malloc(sizeof(ALGraph)); printf("图G的邻接矩阵转换成邻接表:\n"); MatToList(g,G); DispAdj(G); printf("\n"); printf("从顶点0开始的DFS:\n"); DFS(G,0); printf("\n"); printf("从顶点0开始的BFS:\n"); BFS(G,0); printf("\n");}voidMatToList(MGraphg,ALGraph*&G)/*将邻接矩阵g转换成邻接表G*/{/*输入代码*/}voidDispMat(MGraphg)/*输出邻接矩阵g*/{/*输入代码*/}voidDispAdj(ALGraph*G)/*输出邻接表G*/{/*输入代码*/}voidDFS(ALGraph*G,intv){/*输入代码*/}voidBFS(ALGraph*G,intv){/*输入代码*/}实验15：Prim算法求最小生成树一、实验目的1）熟悉图的基本操作。2）掌握运用Prim算法求图的最小生成树。3）加深对图的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计2学时。三、实验内容【基本规定】编写一个程序，对于如下的无向带权图，运用Prim算法输出从顶点0出发的最小生成树。实验16：图综合实验一、实验目的1）熟悉图的基本操作。2）掌握求图的最短途径算法。3）加深对图的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计4学时。三、实验内容【基本规定】给定n个村庄之间的交通图。若村庄i和j之间有路可通，则i和j用边连接，边上的权值Wij表达这条道路的长度。现打算在这n个村庄中选定一个村庄建一所医院。编写如下算法：求出该医院应建在哪个村庄，才干使距离医院最远的村庄到医院的路程最短。求出该医院应建在哪个村庄，能使其它所有村庄到医院的途径总和最短。【提醒】对于问题（1），可以先求出每个村庄到其它所有村庄的最短途径，保存其最大值（表达假设医院建在该村庄，距离医院最远的村庄的途径长度）；然后在这些最大值中找出一个最小值。对于问题（2），可以先求出每个村庄到其它所有村庄的最短途径，保存其累加和（表达假设医院建在该村庄，其它所有村庄距离医院的途径总和）；然后在这些和中找出一个最小值。自己设定n个村庄的交通图。例如下图所示：实验17：线性查找一、实验目的1）熟悉查找的基本操作。2）掌握线性查找（顺序查找、二分查找）的实现。3）加深对查找的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计2学时。三、实验内容1、顺序查找编写一个程序，输出在顺序表中{3，6，2，10，1，8，5，7，4，9}中采用顺序查找的方法查找关键字5的过程。2、二分查找【基本规定】编写一个程序，输出在顺序表中{1，2，3，4，5，6，7，8，9，10}中采用二分查找法查找关键字9的过程。【输出结果】输出结果例子如下：第1次查找:在[0,9]中查找到元素R[4]:5第1次查找:在[0,9]中查找到元素R[4]:5第2次查找:在[5,9]中查找到元素R[7]:8第3次查找:在[8,9]中查找到元素R[8]:9元素9的位置是8实验18：哈希查找一、实验目的1）熟悉查找的基本操作。2）掌握哈希查找的实现。3）加深对查找的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计2学时。三、实验内容【基本规定】编写一个程序，实现哈希表的相关运算，并在此基础上完毕如下功能：建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0..12]，哈希函数为H(k)=key%p，（p取13），并采用线性探查法解决冲突。在上述哈希表中查找关键字为29的记录。在上述哈希表中删除关键字为77的记录，再将其插入。【输出结果】输出结果例子如下：哈希表地址:0123456789101112哈希表地址:0123456789101112哈希表关键字:7754164331294660748890搜索次数:21111411111平均搜索长度ASL(11)=1.36364ha[6].key=29删除关键字77哈希表地址:0123456789101112哈希表关键字:54164331294660748890搜索次数:1111411111平均搜索长度ASL(10)=1.3未找到77插入关键字77哈希表地址:0123456789101112哈希表关键字:7754164331294660748890搜索次数:21111411111平均搜索长度ASL(11)=1.36364实验19：查找综合实验一、实验目的1）熟悉查找的基本操作。2）掌握二叉排序树的基本运算。3）加深对查找的理解，逐步培养解决实际问题的编程能力。二、实验环境装有VisualC＋＋6.0的计算机。本次实验共计4学时。三、实验内容1、记录字符串中字符出现的次数编写一个程序，由键盘输入一个字符串，记录该字符串中出现的字符及另一方面数。然后输出结果。规定用一个二叉树来保存解决结果，字符串中每个不同的字符用树的结点表达，结点应当包含四个域：该字符、该字符出现的次数、左子树指针、右子树指针；其中左子树的字符的ASCII码均小于该字符，右子树的字符的ASCII码均大于该字符。提醒：从字符串中依次读取字符，在二叉树中查找该字符是否存在。假如存在，则该字符的出现次数加1；假如不存在，则按照二叉排序树的规定插入该字符结点，同时设立出现次数为1。所有字符读完以后，调用二叉树的中序遍历，有序的输出每个字符及其出现的次数。2、二叉排序树【基本规定】编写一个程序，实现二叉排序树的基本运算，并在此基础上完毕如下功能：由{4，9，0，1，8，6，3，5，2，7}创建一棵二叉排序树bt，并以括号表达法输出。判断bt是否为一棵二叉排序树。采用递归和非递归两种方法查找关键字为6的结点，并