实验指导手册.doc

《数据结构》

实验指导手册

计算机教研室
2023.6

1．实验教学的目的：通过实验，加深对算法与数据结构基本知识的理解，掌握数据结构的理论和设计技术及其使用，培养学生数据结构的设计、开发能力。
2．实验教学的规定：学生每次实验前必须根据实验指导手册，设计出实验方案（程序和实验环节）；在实验过程中规定独立进行程序调试和排错，必须学会使用在线帮助解决实验中碰到的问题，必须应用理论知识分析问题、解决问题。
3．实验内容：
实验1：VC6的使用
一、实验目的
理解和掌握如何使用Visual C＋＋6.0环境编写C/C＋＋程序。
二、实验环境
装有Visual C＋＋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）可以运用基本运算进行顺序表的操作。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计2学时。
三、实验内容
1、顺序表基本运算
实现顺序表的各种基本运算；并在此基础上设计一个主程序，完毕如下功能：
（1） 初始化顺序表L（元素类型为char型）
（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） 输出顺序表
（12） 释放顺序表

提醒：可以参考上课教材、实验教材的实验题2.1。

2、顺序表的应用（选做）
（1）设计通讯录（也可为其他应用）文献的存储格式和线性表的顺序存储结构
（2）设计在通讯录（也可为其他应用）中添加、删除、查找某个节点信息程序
（3）调试程序

实验3：单链表基本运算
一、实验目的
（1）掌握链表的概念；掌握单链表的各种基本运算的实现。
（2）可以运用基本运算进行单链表的操作。
（3）加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋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）加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计4学时。
三、实验内容
1、通讯录设计
设计一个班级同学的通讯录，规定如下：
ü 通讯录中每个同学的信息包含以下内容：学号（id）、姓名（name）、电话号码（tel）。假如需要更多其他信息，请自行添加。
ü 程序主菜单包含以下几个功能：
（1） 添加记录：通过键盘输入信息，添加一条通讯录记录。
（2） 删除记录：通过键盘输入学号，删除该学号的记录。
（3） 输出记录：输出通讯录所有记录。
（4） 按姓名查找：通过键盘输入姓名，输出该同学的所有信息。
（5） 保存记录：把通讯录中所有的记录保存到文献中。
（6） 清空记录：删除通讯录中的所有记录，并删除文献。
（7） 退出
提醒：
ü 程序启动时应判断是否存在记录文献，假如存在，则读取每条记录到链表中。
ü 用户选择并完毕主菜单某功能后，除了退出程序，应当返回主菜单。
ü 添加一条记录时，插入到链表的尾部。
ü 查找、删除记录时，假如该记录不存在，则应当输出不存在的提醒。
ü 添加记录、删除记录时不需要写文献。
ü 保存记录时，用覆盖写文献的方法。（或者先删除原文献，再保存所有记录信息）
ü 各个功能模块写成函数，由主函数调用。
选做：
ü 主菜单增长一个排序功能选项，可以按照学号从小到大进行排序。排序方法可以用冒泡排序或者插入排序。
实验5：链栈的基本操作
一、实验目的
1）熟悉栈的定义和栈的基本操作。
2）掌握链式存储栈的基本运算。
3）加深对栈数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计2学时。
三、实验内容
必做内容： 链栈的基本操作

编写栈的基本操作函数

1． 栈类型的定义，数据域使用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. 入栈：函数原型如下：
void PushLinkStack（LinkStack* &s , ElemType x）
其中函数参数s为栈指针，x为入栈的数据。

5. 出栈：函数原型如下：
int PopLinkStack (LinkStack* & s, ElemType &x)
其中函数参数s为栈指针，x为出栈的数据的引用；返回值为int型，1表达出栈成功，0表达出栈失败。

6．取栈顶元素：(栈保持不变)函数原型如下：
int GetLinkStackTop (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）加深对队列数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计2学时。
三、实验内容
队列的基本操作

队列的存储结构从顺序循环队列或者链队任选一种。

编写一个程序，实现队列的各种基本运算，并在此基础上设计一个主程序，完毕如下功能：
（1） 初始化队列q
（2） 判断q是否非空
（3） 依次进队元素a，b，c
（4） 出队一个元素，输出该元素
（5） 输出队列q的元素个数
（6） 依次进队列元素d，e，f
（7） 输出队列q的元素个数
（8） 输出出队序列
（9） 释放队列

实验7：栈和队列综合实验
一、实验目的
（1）可以运用栈和队列的基本运算进行相关操作。
（2）进一步熟悉文献的应用
（3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计4学时。
三、实验内容
以下两个实验任选一个。

1、 迷宫求解
设计一个迷宫求解程序，规定如下：
ü 以M × N表达长方阵表达迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
ü 能任意设定的迷宫
ü （选作）假如有通路，列出所有通路
提醒：
ü 以一个二维数组来表达迷宫，0和1分别表达迷宫中的通路和障碍，如下图迷宫数据为：

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

2、机场飞机起降的过程模拟
熟悉队列的各种基本运算，并在此基础上设计一个主程序，完毕如下功能：
ü 模拟一个机场飞机起降的过程
ü 机场仅有一条跑道，规定起飞与降落不能同时进行
ü 进场飞机若暂时没有跑道可用须在空中盘旋等候
ü 离场飞机若暂时没有跑道可用须在地面排队等候
ü 仅当空中无飞机等待降落时地面飞机方可起飞
ü 飞机的申请进场、降落、申请离场和起飞分别视为独立事件
ü 每个事件的发生占用一个时间单位。除降落和起飞外，各事件可以同时发生

提醒：
ü 设定一个待飞队列用于存放排队等候的航班信息
ü 设定一个待降落队列用于存放等待降落的航班信息
ü 飞机的申请进场、降落、申请离场和起飞可以通过航班事先设定的起飞时间、飞行时间长度或者降落时间信息来拟定，这些信息可以存放在一个文献中，程序运营时从文献中读出。
ü 航班当前状态可表达为：起飞，降落，申请进场，申请离场，空闲
ü 每个事件的发生占用一个时间单位可以自己约定，起飞，降落可以设定为30分钟

实验8：顺序串的基本操作
一、实验目的
1）熟悉串的定义和串的基本操作。
2）掌握顺序串的基本运算。
3）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计2学时。
三、实验内容
编写一个程序，实现顺序串的各种基本运算，并在此基础上设计一个主程序。具体如下：

编写栈的基本操作函数
顺序串类型定义如下所示：
typedef struct {
char ch[MAXSIZE];
int len;
} SeqString;
（1）串赋值 Assign(s,t)
n 将一个字符串常量赋给串s,即生成一个其值等于t的串s
（2）串复制 StrCopy(s,t)
n 将串t赋给串s
（3）计算串长度 StrLength(s)
n 返回串s中字符个数
（4）判断串相等StrEqual(s,t)
n 若两个串s与t相等则返回1；否则返回0。
（5）串连接 Concat(s,t)
n 返回由两个串s和t连接在一起形成的新串。
（6）求子串 SubStr(s,i,j)
n 返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。
（7）插入InsStr (s,i,t)
n 将串t插入到串s的第i(1≤i≤StrLength(s)+1)个字符中,即将t的第一个字符作为s的第i个字符,并返回产生的新串
（8）串删除 DelStr (s,i,j)
n 从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j的子串,并返回产生的新串。
（9）串替换 RepStr (s,s1,s2)
n 在串s中,将所有出现的子串s1均替换成s2。
（10）输出串DispStr(s)
n 输出串s的所有元素值
（11）判断串是否为空 IsEmpty(s)

编写主函数

调用上述函数实现下列操作：
（1） 建立串s=“abcdefghijklmn”，串s1=“xyz”，串t＝“hijk”
（2） 复制串t到t1，并输出t1的长度
（3） 在串s的第9个字符位置插入串s1而产生串s2，并输出s2
（4） 删除s第2个字符开始的5个字符而产生串s3，并输出s3
（5） 将串s第2个字符开始的3个字符替换成串s1而产生串s4，并输出s4
（6） 提取串s的第8个字符开始的4个字符而产生串s5，并输出s5
（7） 将串s1和串t连接起来而产生串s6，并输出s6
（8） 比较串s1和s5是否相等，输出结果

实验9：矩阵的基本操作
一、实验目的
1）熟悉数组、矩阵的定义和基本操作。
2）掌握对称矩阵、稀疏矩阵等特殊矩阵的存储方式和基本运算。
3）加深对数组、矩阵的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计2学时。
三、实验内容
以下两个实验任选一个。

1、实现稀疏矩阵的转置、求和
假设m×n的稀疏矩阵用三元组表达，编写一个程序实现如下功能：
（1） 生成如下两个稀疏矩阵的三元组a和b，并输出三元组表达。
1 0 3 0
0 1 0 0
0 0 1 0
0 0 1 0
3 0 0 0
0 4 0 0
0 0 1 0
0 0 0 2

提醒：程序中可以用int A[4][4]和B[4][4]二维数组表达原始矩阵A和B。
（2） 输出a的转置矩阵的三元组表达。
（3） 设c＝a＋b，输出c的三元组表达。

2、求对称矩阵之和、乘积
已知A和B为两个n×n阶的对称矩阵，编写一个程序实现：
（1） 将其下三角元素存储在一维数组a和b中，并输出。
1 1 2 4
1 2 3 5
2 3 4 6
4 5 6 7
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

提醒：程序中可以用int A[4][4]和B[4][4]二维数组表达原始矩阵A和B。
（2） 设C＝A＋B，以矩阵方式输出C。
（3） 设D＝A×B，以矩阵方式输出D。

实验10：字符串综合实验
一、实验目的
1）熟悉串的定义和串的基本操作。
2）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计4学时。
三、实验内容
以下两个实验任选一个。

1、凯撒加密算法
凯撒密码（caeser）是罗马扩张时期朱利斯•凯撒（Julius Caesar）发明的，用于加密通过信使传递的作战命令。它将字母表中的字母移动一定位置而实现加密。
他的原理很简朴，说到底就是字母与字母之间的替换。每一个字母按字母表顺序向后移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）加深对递归算法的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋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）加深二叉树的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计4学时。
三、实验内容
1、二叉树的基本操作
【问题描述】
现需要编写一套二叉树的操作函数，以便用户可以方便的运用这些函数来实现自己的应用。其中操作函数涉及：
1> 创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表达法的字符串*str生成相应的链式存储结构。
2> 输出二叉树DispBTNode(*b)：以括号表达法输出一棵二叉树。
3> 查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。
4> 求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,其高度等于左子树与右子树中的最大高度加l。
5> 求二叉树的结点个数NodesCount(BTNode *b)
6> 先序遍历的递归算法：void PreOrder(BTNode *b)
7> 中序遍历的递归算法：void InOrder(BTNode *b)
8> 后序遍历递归算法：void PostOrder(BTNode *b)
9> 层次遍历算法void LevelOrder(BTNode *b)

【基本规定】
实现以上9个函数。
主函数中实现以下功能：
创建下图中的树b
输出二叉树b
找到’H’节点，输出其左右孩子值
输出b的高度
输出b的节点个数
输出b的四种遍历顺序
A
B
D
C
E
H
J
K
L
M
N
F
G
I

【实验提醒】
数据结构的定义：
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data; /*数据元素*/
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 *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("输出二叉树:");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>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
int ltag,rtag; /*增长的线索标记*/
struct node *lchild;
struct node *rchild;
} TBTNode;
TBTNode *pre;
各个函数的定义：
void CreateTBTNode(TBTNode * &b,char *str)
void DispTBTNode(TBTNode *b)
void Thread(TBTNode *&p)
TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树*/
void ThInOrder(TBTNode *tb)

主函数的结构：
void main()
{
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）加深对哈夫曼树、哈夫曼编码的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计4学时。
三、实验内容
【问题描述】
运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传输时间，减少传输成本。但是，这规定发送端通过一个编码系统对数据进行编码，在接受端将传来的数据进行译码。试为这样的信息收发站写一个哈夫曼编码/译码系统。

【基本规定】
本系统应实现以下功能：（功能1～3必做，4为选做，请课后自行完毕）
（1） 初始化：字符集（字母a～z，空格）共27个字符，以及其权值。建立哈夫曼树。并建立各个字符的哈夫曼编码。
（2） 打印字符集的哈夫曼编码。
（3） 编码：从终端读入字符串，实现该字符串的编码。
（4） 译码：实现刚才生成的哈夫曼编码还原为字符串。（选做）

【已知条件】
（1）字符集的权值如下表：

【实验提醒】
数据结构的定义：
#define N 50 /*叶子结点数*/
#define M 2*N-1 /*树中结点总数*/
typedef struct
{
char data; /*结点值*/
int weight; /*权重*/
int parent; /*双亲结点*/
int lchild; /*左孩子结点*/
int rchild; /*右孩子结点*/
} HTNode;

typedef struct
{
char cd[N]; /*存放哈夫曼码*/
int start;
} HCode;

各个函数的定义：
void CreateHT(HTNode ht[],int n) /*创建哈夫曼树*/
void CreateHCode(HTNode ht[],HCode hcd[],int n) /*创建哈夫曼编码*/
void DispHCode(HTNode ht[],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();
DispHCode();
gets(s);
Encode();

实验14：图的存储和遍历
一、实验目的
1）熟悉图的基本操作。
2）掌握图的存储实现以及遍历操作。
3）加深对图的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.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 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

【提醒】
#include <stdio.h>
#include <malloc.h>
#define MAXV 100 /*最大顶点个数*/
#define INF 32767 /*INF表达∞*/
typedef int InfoType;
/*以下定义邻接矩阵类型*/
typedef struct
{ int no; /*顶点编号*/
InfoType info; /*顶点其他信息*/
} VertexType; /*顶点类型*/
typedef struct /*图的定义*/
{ int edges[MAXV][MAXV]; /*邻接矩阵*/
int vexnum,arcnum; /*顶点数，弧数*/
VertexType vexs[MAXV]; /*存放顶点信息*/
} MGraph; /*图的邻接矩阵类型*/
/*以下定义邻接表类型*/
typedef struct ANode /*弧的结点结构类型*/
{ int adjvex; /*该弧的终点位置*/
struct ANode *nextarc; /*指向下一条弧的指针*/
InfoType info; /*该弧的相关信息,这里用于存放权值*/
} ArcNode;
typedef int Vertex;
typedef struct Vnode /*邻接表头结点的类型*/
{ Vertex data; /*顶点信息*/
ArcNode *firstarc; /*指向第一条弧*/
} VNode;
typedef VNode AdjList[MAXV]; /*AdjList是邻接表类型*/
typedef struct
{ AdjList adjlist; /*邻接表*/
int n,e; /*图中顶点数n和边数e*/
} ALGraph; /*图的邻接表类型*/

int visited[MAXV]; /*全局数组*/
void 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 A[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");
}
void MatToList(MGraph g,ALGraph *&G)
/*将邻接矩阵g转换成邻接表G*/
{
/*输入代码*/
}
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）掌握运用Prim算法求图的最小生成树。
3）加深对图的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计2学时。
三、实验内容
【基本规定】
编写一个程序，对于如