实验指导基础手册.doc

《数据构造》

实验指引手册

计算机教研室
.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。
例如：“百度”用凯撒密码法加密后字符串变为“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学时。
三、实验内容
【基本规定】
编写一种程序，对于如下无向带权图，运用Prim算法输出从顶点0出发最小生成树。

实验16：图综合实验
一、实验目
1）熟悉图基本操作。
2）掌握求图最短途径算法。
3）加深对图理解，逐渐培养解决实际问题编程能力。
二、实验环境
装有Visual C＋＋6.0计算机。
本次实验共计4学时。
三、实验内容
【基本规定】
给定n个村庄之间交通图。若村庄i和j之间有路可通，则i和j用边连接，边上权值Wij表达这条道路长度。现打算在这n个村庄中选定一种村庄建一所医院。编写如下算法：
（1） 求出该医院应建在哪个村庄，才干使距离医院最远村庄到医院路程最短。
（2） 求出该医院应建在哪个村庄，能使其他所有村庄到医院途径总和最