数据结构实验指导手册(共34页)

1、算法(sun f)与数据结构实验(shyn)指导手册计算机教研室2008.6第 PAGE 45 页1实验教学的目的(md)：通过(tnggu)实验，加深对算法(sun f)与数据结构基本知识的理解，掌握数据结构的理论和设计技术及其使用，培养学生数据结构的设计、开发能力。2实验教学的要求：学生每次实验前必须根据实验指导手册，设计出实验方案（程序和实验步骤）；在实验过程中要求独立进行程序调试和排错，必须学会使用在线帮助解决实验中遇到的问题，必须应用理论知识分析问题、解决问题。3实验内容：实验1：VC6的使用一、实验目的理解和掌握如何使用Visual C6.0环境编写C/C程序。二、实验环境装有Vi

2、sual C6.0的计算机。本次实验共计4学时。三、实验内容1、熟悉VC6环境掌握如何创建控制台应用程序。掌握一些常用快捷键，例如编译F7，运行CtrlF5，调试运行F5，单步运行F10/F11，设置断点F9，格式化代码AltF8。2、掌握如何编译程序理解编译过程中的错误信息，并掌握如何排错。3、掌握如何调试程序掌握如何通过设置断点来单步调试程序，如何查看当前变量的值。4、实验(shyn)题：完成(wn chng)实验教材的实验题1.1、1.2、1.3。要求：实现该实验结果。通过该实验题，熟悉VC6环境下的程序编写、编译(biny)、调试。实验2：顺序表基本运算一、实验目的（1）掌握顺序表的各

3、种基本运算的实现。（2）能够利用基本运算进行顺序表的操作。二、实验环境装有Visual C6.0的计算机。本次实验共计2学时。三、实验内容1、顺序表基本运算实现顺序表的各种基本运算；并在此基础上设计一个主程序，完成如下功能：初始化顺序表L（元素类型为char型）依次采用尾插法插入a, b, c, d, e元素输出顺序表L输出顺序表L的长度判断顺序表L是否为空输出顺序表L的第3个元素输出元素a 的位置在第4个元素位置上插入f元素输出顺序表L删除顺序表L的第3个元素输出顺序表释放顺序表提示：可以参考上课教材、实验教材的实验题2.1。2、顺序(shnx)表的应用（选做）（1）设计通讯录（也可为其他应

4、用）文件(wnjin)的存储格式和线性表的顺序存储结构（2）设计(shj)在通讯录（也可为其他应用）中添加、删除、查找某个节点信息程序（3）调试程序实验3：单链表基本运算一、实验目的（1）掌握链表的概念；掌握单链表的各种基本运算的实现。（2）能够利用基本运算进行单链表的操作。（3）加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有Visual C6.0的计算机。本次实验共计2学时。三、实验内容实现单链表的各种基本运算；并在此基础上设计一个主程序，完成如下功能：（1）初始化单链表L（2）依次采用尾插法插入a, b, c, d, e元素（3）输出单链表L（4）输出单链表

5、L的长度（5）判断单链表L是否为空（6）输出单链表L的第3个元素（7）输出元素a 的位置（8）在第4个元素位置上插入f元素（9）输出单链表L（10）删除单链表L的第3个元素（11）输出单链表L（12）释放单链表L提示：可以参考上课教材、实验教材的实验题2.2。实验(shyn)4：单链表综合实验一、实验(shyn)目的（1）能够利用(lyng)单链表的基本运算进行单链表的相关操作。（2）掌握文件的应用（3）加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有Visual C6.0的计算机。本次实验共计4学时。三、实验内容1、通讯录设计设计一个班级同学的通讯录，要求如下：

6、通讯录中每个同学的信息包含以下内容：学号（id）、姓名（name）、电话号码（tel）。如果需要更多其他信息，请自行添加。程序主菜单包含以下几个功能：添加记录：通过键盘输入信息，添加一条通讯录记录。删除记录：通过键盘输入学号，删除该学号的记录。输出记录：输出通讯录全部记录。按姓名查找：通过键盘输入姓名，输出该同学的所有信息。保存记录：把通讯录中所有的记录保存到文件中。清空记录：删除通讯录中的全部记录，并删除文件。退出提示：程序启动时应判断是否存在记录文件，如果存在，则读取每条记录到链表中。用户选择并完成主菜单某功能后，除了退出程序，应该返回主菜单。添加一条记录时，插入到链表的尾部。查找、删除记

7、录时，如果该记录不存在，则应该输出不存在的提示。添加记录、删除记录时不需要写文件。保存记录时，用覆盖写文件的方法。（或者先删除(shnch)原文件，再保存全部记录信息）各个(gg)功能模块写成函数，由主函数调用。选做：主菜单增加一个排序(pi x)功能选项，可以按照学号从小到大进行排序。排序方法可以用冒泡排序或者插入排序。实验5：链栈的基本操作一、实验目的1）熟悉栈的定义和栈的基本操作。2）掌握链式存储栈的基本运算。3）加深对栈数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有Visual C6.0的计算机。本次实验共计2学时。三、实验内容必做内容： 链栈的基本操作编写栈的基本操

8、作函数栈类型的定义，数据域使用char型typedef char ElemType;typedef struct node ElemType data; struct node *next; LinkStack;2初始化空栈：函数原型如下： void InitLinkStack（ LinkStack * & s）其中函数参数为LinkStack * & 类型，表示指向创建的空栈的指针，并且用引用方式传入。3. 判断是否空栈：函数原型如下：int IsEmptyLinkStack（LinkStack *s ） 其中函数参数为栈指针；返回值为int型，1表示是空栈，0表示不是空栈。4. 入栈：函数

9、(hnsh)原型如下：void PushLinkStack（LinkStack* &s , ElemType x） 其中函数参数s为栈指针(zhzhn)，x为入栈的数据。 5. 出栈：函数原型(yunxng)如下：int PopLinkStack (LinkStack* & s, ElemType &x)其中函数参数s为栈指针，x为出栈的数据的引用；返回值为int型，1表示出栈成功，0表示出栈失败。6取栈顶元素：(栈保持不变)函数原型如下：int GetLinkStackTop (LinkStack* s, ElemType &x)其中函数参数s为栈指针，x存放栈顶元素值；返回值为int型，1

10、表示成功，0表示失败。编写主函数调用上述函数实现下列操作。1初始化空栈。2. 键盘输入字符，使得输入的字符依次入栈（结束符号自定，例如回车键(值为10)或#） 每插入一个元素，必须输出当时的栈顶元素(调用GetLinkStackTop函数)。 3判断链栈是否为空。输出判断结果。4调用出栈函数，打印出栈元素的值；反复此步骤，直至栈为空。5判断链栈是否为空。输出判断结果。6释放链栈。选做内容（一）：判断对称字符串设计一个算法，调用栈的基本运算，判断一个字符串是否为对称字符串。若是返回1；否则返回0。例如：“abcba”和“abba”都是对称字符串。实验(shyn)6：队列的基本操作一、实验(shy

11、n)目的1）熟悉队列(duli)的定义和队列的基本操作。2）掌握顺序循环队列和链式存储队列的基本运算。3）加深对队列数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有Visual C6.0的计算机。本次实验共计2学时。三、实验内容队列的基本操作队列的存储结构从顺序循环队列或者链队任选一种。编写一个程序，实现队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：初始化队列q判断q是否非空依次进队元素a，b，c出队一个元素，输出该元素输出队列q的元素个数依次进队列元素d，e，f输出队列q的元素个数输出出队序列释放队列实验7：栈和队列(duli)综合实验一、实验(shyn)目的

12、（1）能够利用栈和队列(duli)的基本运算进行相关操作。（2）进一步熟悉文件的应用（3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。二、实验环境装有Visual C6.0的计算机。本次实验共计4学时。三、实验内容以下两个实验任选一个。迷宫求解设计一个迷宫求解程序，要求如下：以M N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。能任意设定的迷宫（选作）如果有通路，列出所有通路提示：以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：1111111111100100010110010001011000011001101110000

13、110001000011010001001101110110111000000011111111111入口位置：1 1出口(ch ku)位置：8 8探索过程可采用如下(rxi)算法，设定当前位置的初值为入口位置；do 若当前(dngqin)位置可通，则将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东邻方块为新的当前位置； 否则， 若栈不空且栈顶位置尚有其他方向未经探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；/从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块出栈至栈空；w

14、hile (栈不空)；2、机场飞机起降的过程模拟熟悉队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：模拟一个机场飞机起降的过程机场仅有一条跑道，要求起飞与降落不能同时进行进场飞机若暂时没有跑道可用须在空中盘旋等候离场飞机若暂时没有跑道可用须在地面排队等候仅当空中无飞机等待降落时地面飞机方可起飞飞机的申请进场、降落、申请离场和起飞分别视为独立事件每个事件的发生占用一个时间单位。除降落和起飞外，各事件可以同时发生提示：设定一个待飞队列用于存放排队等候的航班信息设定一个待降落队列用于存放等待降落的航班信息飞机的申请进场、降落、申请离场和起飞可以通过航班事先设定的起飞时间、飞行时间长度或

15、者降落时间信息来确定，这些信息可以存放在一个文件中，程序运行时从文件中读出。航班当前状态可表示为：起飞，降落，申请进场，申请离场，空闲每个事件的发生占用一个时间单位可以自己约定(yudng)，起飞，降落可以设定为30分钟实验(shyn)8：顺序串的基本操作一、实验(shyn)目的1）熟悉串的定义和串的基本操作。2）掌握顺序串的基本运算。3）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。二、实验环境装有Visual C6.0的计算机。本次实验共计2学时。三、实验内容编写一个程序，实现顺序串的各种基本运算，并在此基础上设计一个主程序。具体如下：编写栈的基本操作函数顺序串类型定义如下所示：

16、typedef struct char chMAXSIZE; int len; 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(1iStrLength(s)个字符开始的、由连续j个字符组成的子串。（7）插入(c

17、h r)InsStr (s,i,t)将串t插入(ch r)到串s的第i(1iStrLength(s)+1)个字符中,即将(jjing)t的第一个字符作为s的第i个字符,并返回产生的新串（8）串删除 DelStr (s,i,j)从串s中删去从第i(1iStrLength(s)个字符开始的长度为j的子串,并返回产生的新串。（9）串替换 RepStr (s,s1,s2)在串s中,将所有出现的子串s1均替换成s2。（10）输出串DispStr(s)输出串s的所有元素值（11）判断串是否为空 IsEmpty(s)编写主函数调用上述函数实现下列操作：建立串s=“abcdefghijklmn”，串s1=“x

18、yz”，串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是否相等，输出结果实验(shyn)9：矩阵的基本操作一、实验(shyn)目的1）熟悉数组、矩阵(j zhn)的定义和基本操作。2）掌握对称矩阵、稀疏矩阵等特殊矩阵的存储方式和基本运算。3）加深对数组、矩阵的理解，逐步培养解决实际问题的编程能力。二、

19、实验环境装有Visual C6.0的计算机。本次实验共计2学时。三、实验内容以下两个实验任选一个。1、实现稀疏矩阵的转置、求和假设mn的稀疏矩阵用三元组表示，编写一个程序实现如下功能：生成如下两个稀疏矩阵的三元组a和b，并输出三元组表示。1 0 3 00 1 0 00 0 1 00 0 1 03 0 0 00 4 0 00 0 1 00 0 0 2提示：程序中可以用int A44和B44二维数组表示原始矩阵A和B。输出a的转置矩阵的三元组表示。设cab，输出c的三元组表示。2、求对称矩阵之和、乘积已知A和B为两个nn阶的对称矩阵，编写一个程序实现：将其下三角元素存储在一维数组a和b中，并输出。

20、1 1 2 41 2 3 52 3 4 64 5 6 71 1 1 11 1 1 11 1 1 11 1 1 1提示：程序中可以(ky)用int A44和B44二维数组表示原始矩阵A和B。设CAB，以矩阵方式(fngsh)输出C。设DAB，以矩阵方式(fngsh)输出D。实验10：字符串综合实验一、实验目的1）熟悉串的定义和串的基本操作。2）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。二、实验(shyn)环境装有Visual C6.0的计算机。本次(bn c)实验共计4学时。三、实验(shyn)内容以下两个实验任选一个。1、凯撒加密算法凯撒密码（caeser）是罗马扩张时期朱利斯凯

21、撒（Julius Caesar）创造的，用于加密通过信使传递的作战命令。它将字母表中的字母移动一定位置而实现加密。他的原理很简单，说到底就是字母与字母之间的替换。每一个字母按字母表顺序向后移3位，如a加密后变成d，b加密后变成e，x加密后变成a，y加密后变成b，z加密后变成c。例如：“baidu”用凯撒密码法加密后字符串变为“edlgx”。试写一个算法，将键盘输入的文本字符串（只包含az的字符）进行加密后输出。另写一个算法，将已加密后的字符串解密后输出。提示：如果有字符变量c加密后则a（c-a3）26采用顺序结构存储串，键盘输入字符串后保存到顺序串中；输出用顺序串的输出函数。2、求一个串中出现

22、的第一个最长重复子串采用顺序结构存储串，编写一个程序，求串s中出现的第一个最长重复子串的下标和长度。实验11：递归综合实验一、实验目的1）熟悉递归的定义和递归的算法设计。2）加深对递归算法的理解，逐步培养解决实际问题的编程能力。二、实验(shyn)环境装有Visual C6.0的计算机。本次(bn c)实验共计4学时。三、实验(shyn)内容以下两个实验任选一个。1、求解n皇后问题编写一个程序，求解皇后问题：在nn的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同对角线。要求：使用递归算法求解；皇后的个数n由用户输入，其值不能超过20。2、求解汉诺塔问题设有3个分别命名为X,Y和Z的

23、塔座,在塔座X上有n个直径各不相同,从小到大依次编号为1,2,n的盘片,现要求将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放,盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X,Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法。要求：使用递归算法求解；盘片的个数n由用户输入，其值不能超过12。实验12：二叉树的操作一、实验目的1）熟悉二叉树树的基本操作。2）掌握二叉树的实现以及实际应用。3）加深二叉树的理解，逐步培养解决实际问题的编程能力。二、实验(shyn)环境装有Visual C6.0的计算机。本次实验共计(n j)4学时。三、实验(sh

24、yn)内容1、二叉树的基本操作【问题描述】现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链式存储结构。输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,其高度等于左子树与右子树中的最大高度加l。求二叉树的结点个数NodesCount(BT

25、Node *b)先序遍历的递归算法：void PreOrder(BTNode *b) 中序遍历的递归算法：void InOrder(BTNode *b) 后序遍历递归算法：void PostOrder(BTNode *b) 层次遍历算法void LevelOrder(BTNode *b)【基本要求】实现以上9个函数。主函数中实现以下功能：创建下图中的树b输出二叉树b找到H节点，输出其左右孩子值输出b的高度输出b的节点个数输出b的四种遍历顺序ABDCEHJKLMNFGI【实验(shyn)提示】数据结构(sh j ji u)的定义：#include #include #define MaxSize

26、 100typedef char ElemType;typedef struct nodeElemType data;/*数据(shj)元素*/struct node *lchild;/*指向左孩子*/struct node *rchild;/*指向右孩子*/ BTNode;各个函数的定义：void CreateBTNode(BTNode *&b,char *str);BTNode *FindNode(BTNode *b,ElemType x);int BTNodeDepth(BTNode *b);void DispBTNode(BTNode *b);int NodesCount(BTNode

27、 *b);void PreOrder(BTNode *b);void InOrder(BTNode *b);void PostOrder(BTNode *b);void TravLevel(BTNode *b);主函数的结构：void main()BTNode *b,*p,*lp,*rp;char str=A(B(D,E(H(J,K(L,M(,N),C(F,G(,I);CreateBTNode(b,str); printf(n);printf(输出(shch)二叉树:);DispBTNode(b);printf(n);printf(H结点(ji din):);p=FindNode(b,H);i

28、f (p!=NULL)/此处输出p的左右(zuyu)孩子节点的值printf(n);printf(二叉树b的深度:%dn,BTNodeDepth(b);printf(二叉树b的结点个数:%dn,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( 层次遍历序列

29、:); printf(n);TravLevel(b); printf(n);2.2 二叉树的线索化【问题描述】编写一个程序，实现中序线索化二叉树，输出线索中序序列。【基本要求】用上图的二叉树b来验证你的程序。【实验提示】数据结构的定义：#include #include #define MaxSize 100typedef char ElemType;typedef struct node ElemType data;int ltag,rtag; /*增加的线索标记*/struct node *lchild;struct node *rchild; TBTNode;TBTNode *pre;各

30、个(gg)函数的定义：void CreateTBTNode(TBTNode * &b,char *str)void DispTBTNode(TBTNode *b)void Thread(TBTNode *&p)TBTNode *CreaThread(TBTNode *b) /*中序线索(xin su)化二叉树*/void ThInOrder(TBTNode *tb)主函数(hnsh)的结构：void main()TBTNode *b,*tb;CreateTBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf( 二叉树:);DispTBTNode(b)

31、;printf(n);tb=CreaThread(b);printf( 线索中序序列:);ThInOrder(tb);printf(n);3实验结果此处填写程序运行结果。4实验心得此处填写你的实验心得体会。实验13：哈夫曼编码一、实验目的1）熟悉哈夫曼树的基本操作。2）掌握(zhngw)哈夫曼编码(bin m)的实现以及实际应用。3）加深(jishn)对哈夫曼树、哈夫曼编码的理解，逐步培养解决实际问题的编程能力。二、实验环境装有Visual C6.0的计算机。本次实验共计4学时。三、实验内容【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求发

32、送端通过一个编码系统对数据进行编码，在接受端将传来的数据进行译码。试为这样的信息收发站写一个哈夫曼编码/译码系统。【基本要求】本系统应实现以下功能：（功能13必做，4为选做，请课后自行完成）初始化：字符集（字母az，空格）共27个字符，以及其权值。建立哈夫曼树。并建立各个字符的哈夫曼编码。打印字符集的哈夫曼编码。编码：从终端读入字符串，实现该字符串的编码。译码：实现刚才生成的哈夫曼编码还原为字符串。（选做）【已知条件】（1）字符集的权值如下表：【实验提示】数据结构的定义：#define N 50/*叶子结点数*/#define M 2*N-1/*树中结点总数*/typedef structch

33、ar data;/*结点(ji din)值*/int weight;/*权重(qun zhn)*/int parent;/*双亲(shungqn)结点*/int lchild;/*左孩子结点*/int rchild;/*右孩子结点*/ HTNode;typedef structchar cdN;/*存放哈夫曼码*/int start; HCode;各个函数的定义：void CreateHT(HTNode ht,int n)/*创建哈夫曼树*/void CreateHCode(HTNode ht,HCode hcd,int n)/*创建哈夫曼编码*/void DispHCode(HTNode h

34、t,HCode hcd,int n)/*显示各个字符的哈夫曼编码*/void Encode(char *s,HTNode ht,HCode hcd,int n) /*显示字符串s的哈夫曼编码*/主函数的结构：char str= ,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; /*字符集*/int fnum=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();D

35、ispHCode();gets(s);Encode();实验14：图的存储和遍历一、实验目的1）熟悉图的基本操作。2）掌握图的存储(cn ch)实现以及遍历操作。3）加深对图的理解(lji)，逐步培养解决实际问题的编程能力。二、实验(shyn)环境装有Visual C6.0的计算机。本次实验共计2学时。三、实验内容【基本要求】1、用邻接矩阵存储方式，表示下面的图，并输出。2、由上面的邻接矩阵产生邻接表，并输出。3、编程完成从顶点0开始的深度优先遍历和广度优先遍历。【输出结果】输出结果例子如下：有向图G的邻接矩阵: 0 5 0 7 0 0 0 0 4 0 0 0 8 0 0 0 0 9 0 0

36、5 0 0 6 0 0 0 5 0 0 3 0 0 0 1 0 图G的邻接矩阵转换成邻接表: 0: 1 3 1: 2 2: 0 5 3: 2 5 4: 3 5: 0 4从顶点0开始的DFS: 0 1 2 5 4 3从顶点0开始的BFS: 0 1 3 2 5 4【提示(tsh)】#include #include #defineMAXV 100/*最大顶点(dngdin)个数*/#define INF 32767 /*INF表示(biosh)*/typedef int InfoType;/*以下定义邻接矩阵类型*/typedef struct int no;/*顶点编号*/InfoType in

37、fo;/*顶点其他信息*/ VertexType;/*顶点类型*/typedef struct /*图的定义*/ int edgesMAXVMAXV; /*邻接矩阵*/ int vexnum,arcnum; /*顶点数，弧数*/VertexType vexsMAXV;/*存放顶点信息*/ MGraph;/*图的邻接矩阵类型*/*以下定义邻接表类型*/typedef struct ANode /*弧的结点结构类型*/int adjvex; /*该弧的终点位置*/ struct ANode *nextarc; /*指向下一条弧的指针*/ InfoType info; /*该弧的相关信息,这里用于存

38、放权值*/ ArcNode;typedef int Vertex;typedef struct Vnode /*邻接(ln ji)表头结点的类型*/Vertex data; /*顶点(dngdin)信息*/ ArcNode *firstarc; /*指向(zh xin)第一条弧*/ VNode;typedef VNode AdjListMAXV;/*AdjList是邻接表类型*/typedef struct AdjList adjlist; /*邻接表*/ int n,e; /*图中顶点数n和边数e*/ ALGraph; /*图的邻接表类型*/int visitedMAXV;/*全局数组*/v

39、oid MatToList(MGraph,ALGraph *&);/*邻接矩阵转为邻接表*/void DispMat(MGraph);/*输出邻接矩阵*/void DispAdj(ALGraph *);/*输出邻接表*/void DFS(ALGraph *G,int v);/*深度优先遍历*/void BFS(ALGraph *G,int v);/*广度优先遍历*/void main()int i,j;MGraph g;ALGraph *G;int AMAXV6=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,

40、0,1,0;g.vexnum=6;g.arcnum=10;for (i=0;ig.vexnum;i+)for (j=0;jg.vexnum;j+)g.edgesij=Aij;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(从顶点(dngdin)0开始的BFS:n);BFS(G

41、,0);printf(n);void MatToList(MGraph g,ALGraph *&G)/*将邻接(ln ji)矩阵g转换成邻接表G*/*输入(shr)代码*/void DispMat(MGraph g)/*输出邻接矩阵g*/*输入代码*/void DispAdj(ALGraph *G)/*输出邻接表G*/*输入代码*/void DFS(ALGraph *G,int v) /*输入代码*/void BFS(ALGraph *G,int v) /*输入代码*/实验15：Prim算法求最小生成树一、实验目的1）熟悉图的基本操作。2）掌握利用(lyng)Prim算法求图的最小生成树。3）

42、加深对图的理解，逐步培养(piyng)解决实际问题的编程能力。二、实验(shyn)环境装有Visual C6.0的计算机。本次实验共计2学时。三、实验内容【基本要求】编写一个程序，对于如下的无向带权图，利用Prim算法输出从顶点0出发的最小生成树。实验16：图综合实验一、实验目的1）熟悉图的基本操作。2）掌握求图的最短路径算法。3）加深对图的理解，逐步培养解决实际问题的编程能力。二、实验(shyn)环境装有Visual C6.0的计算机。本次实验共计(n j)4学时。三、实验(shyn)内容【基本要求】给定n个村庄之间的交通图。若村庄i和j之间有路可通，则i和j用边连接，边上的权值Wij表示这

43、条道路的长度。现打算在这n个村庄中选定一个村庄建一所医院。编写如下算法：求出该医院应建在哪个村庄，才能使距离医院最远的村庄到医院的路程最短。求出该医院应建在哪个村庄，能使其它所有村庄到医院的路径总和最短。【提示】对于问题（1），可以先求出每个村庄到其它所有村庄的最短路径，保存其最大值（表示假设医院建在该村庄，距离医院最远的村庄的路径长度）；然后在这些最大值中找出一个最小值。对于问题（2），可以先求出每个村庄到其它所有村庄的最短路径，保存其累加和（表示假设医院建在该村庄，其它所有村庄距离医院的路径总和）；然后在这些和中找出一个最小值。自己设定n个村庄的交通图。例如下图所示：实验17：线性查找一、

44、实验目的1）熟悉查找的基本操作。2）掌握线性查找（顺序(shnx)查找、二分查找）的实现。3）加深对查找的理解，逐步培养(piyng)解决实际问题的编程能力。二、实验(shyn)环境装有Visual C6.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中查找到元素R4:5第2次查找:在5,9中查找到元

45、素R7:8第3次查找:在8,9中查找到元素R8:9元素9的位置是8实验18：哈希查找一、实验目的1）熟悉查找的基本操作。2）掌握哈希查找的实现。3）加深对查找的理解，逐步培养解决实际问题的编程能力。二、实验(shyn)环境装有Visual C6.0的计算机。本次实验共计(n j)2学时。三、实验(shyn)内容【基本要求】编写一个程序，实现哈希表的相关运算，并在此基础上完成如下功能：建立16,74,60,43,54,90,46,31,29,88,77哈希表A0.12，哈希函数为H(k)=key%p，（p取13），并采用线性探查法解决冲突。在上述哈希表中查找关键字为29的记录。在上述哈希表中删除

46、关键字为77的记录，再将其插入。【输出结果】输出结果例子如下：哈希表地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表关键字: 77 54 16 43 31 29 46 60 74 88 90 搜索次数: 2 1 1 1 1 4 1 1 1 1 1 平均搜索长度ASL(11)=1.36364 ha6.key=29 删除关键字77 哈希表地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表关键字: 54 16 43 31 29 46 60 74 88 90 搜索次数: 1 1 1 1 4 1 1 1 1 1 平均搜索长度ASL(10)=1.3 未找到77

47、 插入关键字77 哈希表地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表关键字: 77 54 16 43 31 29 46 60 74 88 90 搜索次数: 2 1 1 1 1 4 1 1 1 1 1 平均搜索长度ASL(11)=1.36364实验19：查找综合实验一、实验目的1）熟悉查找的基本操作。2）掌握二叉排序树的基本运算。3）加深对查找的理解，逐步培养解决实际问题的编程能力。二、实验(shyn)环境装有Visual C6.0的计算机。本次(bn c)实验共计4学时。三、实验(shyn)内容1、统计字符串中字符出现的次数编写一个程序，由键盘输入一个字符串，统计该字符串中出现的字符及其次数。然后输出结果。要求用一个二叉树来保存处理结果，字符串中每个不同的字符用树的结点表示，结点应该包含四个域：该字符、该字符出现的次数、左子树指针、右子树指针；其中左子树的字符的ASCII码均小于该字符，右子树的字符的ASCII码均大于该字符。提示：从字符串中依次读取字符，在二叉树中查找该字符是否存在。如果存在，则该字符的出现次数加1；如果不存在，则按照二叉