《数据结构》实验指导手册

《数据结构》

实验指导手册

计算机教研室

2023.6

1.实验教学的目的：通过实验，加深对算法与数据结构基本知识的理解，掌握

数据结构的理论和设计技术及其使用，培养学生数据结构的设计、开发能力。

2.实验教学的规定：学生每次实验前必须根据实验指导手册，设计出实验方案

（程序和实验环节）；在实验过程中规定独立进行程序调试和排错，必须学会使

用在线帮助解决实验中碰到的问题，必须应用理论知识分析问题、解决问题。

3.实验内容：

实验1:VC6的使用

一、实验目的

理解和掌握如何使用VisualC++6.0环境编写C/C++程序。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计4学时。

三、实验内容

I.熟悉VC6环境

掌握如何创建控制台应用程序。

掌握一些常用快捷键，例如编译F7,运营Ctrl+F5,调试运

营F5,单步运营F10/F11,设立断点F9,格式化代码Alt+

F80

2.掌握如何编译程序

理解编译过程中的错误信息，并掌握如何排错。

3.掌握如何调试程序

掌握如何通过设立断点来单步调试程序，如何查看当前变量

的值。

4.实验题：

完毕实验教材的实验题1.1、1.2、1.3o规定:

实现该实验结果。通过该实验题，熟悉VC6

环境下的程序编写、编译、调试。

实验2:顺序表基本运算

一、实验目的

(1)掌握顺序表的各种基本运算的实现。

(2)可以运用基本运算进行顺序表的操作。

（2）设计在通讯录［也可为其他应用）中添加、删除、查找某个节点信息程序

（3）调试程序

实验3:单链表基本运算

一、实验目的

（1）掌握链表的概念；掌握单链表的各种基本运算的实现。

（2）可以运用基本运算进行单链表的操作。

（3）加深对链式存储数据结构的理解，逐步培养解决实际问

题的编程能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共订2学时。

三、实验内容

实现单链表的各种基本运算；并在此基础上设计一个主程序，完毕如下功能:

（1）初始化单链表L

（2）依次采用尾插法插入a,b,c,d,c元素

（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）、电话号码（⑶）。

假如需要更多其他信息，请自行添加。

（1）程序主菜单包含以下几个功能：

（2）添加记录：通过铤盘输入信息，添加一条通讯录记录。

（3）删除记录：通过键盘输入学号，删除该学号的记录。

（4）输出记录：输出通讯录所有记录。

（5）按姓名查找：通过键盘输入姓名，输出该同学的所有信息。

（6）保存记录：把通讯录中所有的记录保存到文献中。

（7）清空记录：删除通讯录中的所有记录，并删除文献。

（8）退出

提醒：

/程序启动时应判断是否存在记录文献，假如存在，则读取每条记录到链表中。

/用户选择并完毕主菜单某功能后，除了退出程序，应当返回主菜单。

/添加一条记录时，插入到链表的尾部。

/查找、删除记录时，假如该记录不存在，则应当输出不存在的提醒。

/添加记录、删除记录时不需要写文献。

保存记录时，用覆盖写文献的方法。（或者先删除原文献，再保存所有记录信息）

各个功能模块写成函数，由主函数调用。

选做:

主菜单增长一个排序功能选项，可以按照学

号从小到大进行排序。排序方法可以用冒泡

排序或者插入排序。

实验5:链栈的基本操作

一、实验目的

1）熟悉栈的定义和栈的基本操作。

2）掌握链式存储栈的基本运算。

3）加深对栈数据结构的理解，逐步培养解决实际问题的编程

能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计2学时。

三、实验内容

必做内容：链栈的基本操作

编写栈的基本操作函数

栈类型的定义，数据域使用char型

typedefcharElemType;

typedefstructnode{

ElcmTypcdata;

structnode*next;

}LinkStack;

2.初始化空栈：函数原型如F：

voidInitLinkStack(LinkStack*&s)

其中函数参数为LinkStack*&类型，表达指向创建的空栈的指针，并且用引用方式传入。

3.判断是否空栈：函数原型如下：

intIsEmptyLinkStack(LinkStack*s)

其中函数参数为栈指针；返回值为int型，1表达是空栈,0表达不是空栈。

4.入栈：函数原型如下：

voidPushLinkSlack(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型，I表达成功,0表达失败。

编写主函数

调用上述函数实现下列操作。

1.初始化空栈。

2.键盘输入字符，使得输入的字符依次入栈(结束符号自定，例如回车键(值为10)或乱

每插入一个元素，必须输出当时的栈顶元素（调用GctLinkStackTop函数）。

3.判断链栈是否为空。输出判断结果。

4.调用出栈函数，打印出栈元素的值；反复此环节，直至栈为空。

5.判断链栈是否为空。输出判断结果。

6.释放链栈。

选做内容（一）：判断对称字符串

设计一个算法，调用栈的基本运算，判断一个字符串是否为对称字符串。若是返回1;否则

返回Oo

例如：“abcba”和“abba”都是对称字符串。

实验6:队列的基本操作

一、实验目的

1）熟悉队列的定义和队列的基本操作。

2）掌握顺序循环队列和链式存储队列的基本运算。

3)加深对队列数据结构的理解，逐步培养解决实际问题的编

程能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计2学时。

三、实验内容

队列的基本操作

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

(1)编写一个程序，实现队列的各种基本运算，并在此基础上设计一个主程序，完毕如

下功能：

(2)初始化队列q

(3)判断q是否非空

(4)依次进队元素a,b,c

(5)出队一个元素，输山该元素

(6)输出队列q的元素个数

(7)依次进队列元素d,e,f

(8)输出队列q的元素个数

(9)输出出队序列

(10)样放队列

实验7:栈和队列综合实验

一、实验目的

（1）可以运用栈和队列的基本运算进行相关操作。

（2）进一步熟悉文献的应用

（3）加深队列和栈的数据结构理解，逐步培养解决实际问题

的编程能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计4学时。

三、实验内容

以下两个实验任选一个。

1、迷宫求解

,设计一个迷宫求解程序，规定如下：

/以XN表达长方阵表达迷宫，求出一条从入口到出口的通路，或得出没有通路的结

论。

/能任意设定的迷宫

(选作)假如有通路，列出所有通路

提醒：

以一个二维数组来表达迷宫，0和1分别表达迷宫中的通路和障碍，如下图迷宫数据

为：

/出口位置.：88

探索过程可采用如下算法，设定当前位置的初值为入口位置；

do{

若当前位置可通.

则{

将当前位置插入栈顶；

若该位置是出口位置，则结束；

否则切换当前位置的东邻方块为新的当前位置；

)

否则，

(

若栈不空且栈顶位置尚有其他方向未经探索，

则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块;

若栈不空但栈顶位置的四周均不可通,

则{删去栈顶位置：〃从途径中删去该通道块

若栈不空，则重新测试新的栈顶位置，

直至找到一个可通的相邻块出栈至栈空；

)

)

}while(栈不空)：

2.机场飞机起降的过程模拟

,熟悉队列的各种基本运算，并在此基础上设计一个主程序，完毕如下功能：

/模拟一个机场飞机起降的过程

,机场仅有一条跑道，规定起飞与降落不能同时进行

,进场飞机若暂时没有跑道可用须在空中盘旋等候

,离场飞机若暂时没有跑道可用须在地面排队等候

/仅当空中无飞机等待降落时地面飞机方可起飞

/飞机的申请进场、降落、申请离场和起飞分别视为独立事件

每个事件的发生占用一个时间单位。除降落和起飞外，各事件可以同时发生

提醒：

,设定一个待飞队列用于存放排队等候的航班信息

/设定一个待降落队列用于存放等待降落的航班信息

/匕机的申请进场、降落、申请离场和起匕可以通过航班事先设定的起飞时间、飞行时间

长度或者降落时间信息来拟定，这些信息可以存放在一个文献中，程序运营时从文献

中读出。

航班当前状态可表达为：起飞，降落，申请进场，申请离场，空闲

每个事件的发生占用一个时间单位可以自己约定，起飞，降落可以设定为30分钟

实验8:顺序串的基本操作

一、实验目的

1)熟悉串的定义和串的基本操作。

2)掌握顺序串的基本运算。

3)加深对串数据结构的理解，逐步培养解决实际问题的编程

能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计2学时。

三、实验内容

编写一个程序，实现顺序串的各种基本运算，并在此基础上设计一个主程序。具体如下：

编写栈的基本操作函数

顺序串类型定义如下所示：

typedefstruct{

charch[MAXSIZEl;

intlen;

}ScqString;

(1)串赋值Assign",t)

■将一个字符串常量赋给串s,即生成一个其值等于l的串s

(2)串复制StrCopy(s.t)

■将串t赋给串s

(3)计算串长度StrLength(s)

■返回串s中字符个数

(4)判断串相等SlrEqual(s,l)

■若两个串s与t相等则返回1；否则返回0。

(5)串连接Concat(s,t)

■返问由两个串s和t连接在一起形成的新串。

(6)求子串SubStr(s,ij)

■返回串s中从第i(lWiWStrLength(s))个字符开始的、由连续j个字符组成的

子串。

(7)插入InsSlr

■将串t插入到串s的第i(lWiWSlrLength(s)+l)个字符中，即将t的第一个字符

作为s的第i个字符，并返回产生的新串

(8)串删除DelStr(s,i,j)

■从串s中删去从第i(lWiWSlrLength(s))个字符开始的长度为j的子串，并返回

产生的新事。

(9)串替换RepStr(s,sl,s2)

■在串s中，将所有出现的子串si均替换成s2o

(10)输出串DispStris)

■输出串s的所有元素值

(11)判断串是否为空LEmpty(s)

编写主函数

（1）调用上述函数实现下列操作：

（2）建立串s="abcdefghijklmn”，串sl="xyz”,串t="hijk”

（3）复制串l到tl,并谕出11的长度

（4）在串s的第9个字符位置插入串si而产生串s2,并输出s2

（5）删除s第2个字符开始的5个字符而产生串s3,并输出s3

（6）将串s第2个字符开始的3个字符替换成串si而产生串s4,并输出s4

（7）提取串s的第8个字符开始的4个字符而产生串S5,并输出s5

（8）将串si和串t连接起来而产生串s6,并输出s6

比较串si和s5是否相等，输出结果

实验9:矩阵的基本操作

一、实验目的

1）熟悉数组、矩阵的定义和基本操作。

2）掌握对称矩阵、稀疏矩阵等特殊矩阵的存储方式和基本运算。

3）加深对数组、矩阵的理解，逐步培养解决实际问题的编程

能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计2学时。

三、实验内容

以下两个实验任选一个。

1.实现稀疏矩阵的转置、求和

假设mXn的稀疏矩阵用三元组表达，编写一个程序实现如下功能:

生成如下两个稀疏矩阵的三元组a和b,并输出三元组表达。

（1）提醒：程序中可以用intA[4][4]和B[4][4]二维数组表达原始矩阵A和B。

（2）输出a的转置矩阵的三元组表达。

设©=2+卜输出c的三元组表达。

2.求对称矩阵之和、乘积

已知A和B为两个nXn阶的对称矩阵，编写一个程序实现:

将其下三角元素存储在一维数组a和b中，并输出。

(1)提醒：程序中可以用intA[4H4]和B[4][4]二维数组表达原始矩阵A和B。

设C=A+B,以矩阵方式输出C。

设口=人乂8,以矩阵方式输出D。

实验10:字符串综合实验

一、实验目的

I)熟悉串的定义和串的基本操作。

2)加深对串数据结构的理解，逐步培养解决实际问题的编程

能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计4学时。

三、实验内容

以下两个实验任选一个。

I.凯撒加密算法

凯撒密码(caeser)是罗马扩张时期朱利斯•凯撒(JuliusCaesar)发明的，用于加密通过

信使传递的作战命令。它将字母表中的字母移动一定位置而实现加密。

他的原理很简朴，说到底就是字母与字母之间的替换。每一个字母按字母表顺序向后移3位,

如a加密后变成d,b加密后变成e,x加密后变成a,y加密后变成b,z加密后变成Co

例如：“baidu”用凯撒密码法加密后字符串变为“edlgx”。

试写一个算法，将键盘输入的文本字符串(只包含a〜z的字符)进行加密后输出。

另写一个算法，将己加密后的字符串解密后输出。

提醒：

/假如有字符变量c加密后则=匕，+%26

采用顺序结构存储串，键盘输入字符串后保存到顺序串中；

输出用顺序串的输出函数。

2.求一个串中出现的第一个最长反复子串

采用顺序结构存储串，编写一个程序，求

串s中出现的第一个最长反复子串的下标和

长度。

实验11:递归综合实验

一、实验目的

1）熟悉递归的定义和递归的算法设计。

2）加深对递归算法的理解，逐步培养解决实际问题的编程能

力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计4学时。

三、实验内容

以下两个实验任选一个。

1.求解n皇后问题

编写一个程序，求解皇后问题：在nxn的方格棋盘.上，放置n个皇后，规定每个皇后不同行、

不同列、不同对角线。

规定：使用递归算法求解；皇后的个数n由用户输入，其值不能超过20。

2.求解汉诺塔问题

设有3个分别命名为X,Y和Z的塔座，在塔座X上有n个直径各不相同，从小到大依

次编号为1,2，…,n的盘片，现规定将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放,

盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X,Y和Z中任一塔

座：任何时候都不能将一个较大的盘片放在较小的盘片卜.设计递归求解算法.

规定：使用递归算法求解；盘片的个数n由用户输入，其值不能超过12。

实验12:二叉树的操作

一、实验目的

D熟悉二叉树树的基本操作。

2）掌握二叉树的实现以及实际应用。

3）加深二叉树的理解，逐步培养解决实际问题的编程能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计4学时。

三、实验内容

I.二叉树的基本操作

【问题描述】

!＞现需要编写一套二叉树的操作函数，以便用户可以方便的运用这些函数来实现自

己的应用。其中操作函数涉及:

2＞创建二叉树CrcatcBTNode(*b,*str):根据二叉树括号表达法的字符串*str生成相应的

链式存储结构。

3＞输出二叉树DispBTNode(*b):以括号表达法输出一棵二叉树。

4＞查找结点FindNode(*b,x):在二叉树b中寻找data域值为x的结点，并返回指向该结

点的指针。

5＞求高度BTNodeDepth(*b):求二叉树b的高度。若二叉树为空，则其高度为0；否则,

其高度等于左子树与右子树中的最大高度加1。

6＞求二叉树的结点个数NodesCount(BTNode*b)

7＞先序遍历的递归算法:voidPrcOrdcr(BTNodc*b)

8＞中序遍历的递归算法:voidInOider(BTNode*b)

9＞后序遍历递归算法：voidPosiOrder(BTNode*b)

10＞层次遍历算法voidLevelOrder(BTNode*b)

【基本规定】

实现以上9个函数。

主函数中实现以下功能：

创建下图中的树b

输出二叉树b

找到'H'节点，输出其左右孩子值

输出b的高度

输出b的节点个数

输出b的四种遍历顺序

【实验提醒】

数据结构的定义：

#include<stdio.h>

#include<malloc.h>

#defineMaxSize100

typcdcfcharElcmTypc;

typedefstructnode

(

EleniTypedata;/*数据元素*/

structnode*IchiId;指向左孩了，

structnode*rchild;/*指向右孩子*/

}BTNode;

各个函数的定义：

voidCreateBTNode(BTNode*&b,char*str);

BTNode*FindNode(BTNode*b,ElemTypex);

intBTNodeDepth(BTNode*b);

voidDispBTNode(BTNode*b);

intNodesCount(BTNode*b);

voidPrcOrdcr(BTNodc*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(J)))";

CreateBTNode(b,str);

printf("\n");

printf("输出二叉树:"):DispBTNode(b);printf("\n")；

primf(”H结点:");

p=FindNode(b；H');

if(p!=NULL)

{

〃此处输出p的左右孩子节点的值

}

printf("\n");

printf("二叉树b的深度:％d\n”,BTNodcDcpth(b));

printf("二叉树b的结点个数:%d\n",NodesCount(b));

printf("\n");

printf("先序遍历序歹J:\rT);

printf("递归算法:");PreOrder(b);printf("W")；

printf("中序遍历序列:\n");

printf("递归算法:");InOrder(b);printf("\n");

printf("后序遍历序夕］:\n");

printf("递归算法:");PostOrder(b);p「intf("\n");

printfC层次遍历序列printf("\n");

TravLevel(b);printf("\n");

}

2.2二叉树的线索化

【问题描述】

编写一个程序，实现中序线索化二叉树，输出线索中序序列。

【基本规定】

用上图的一叉树b来验证你的程序。

【实验提醒】

数据结构的定义：

#include<stdio.h>

#includc<malloc.h>

#defineMaxSize100

typedefcharEleniType;

typedefstructnode

(

ElcmTypcdata;

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(TBTNodc*tb)

主函数的结构：

voidmain()

(

TBTNode*b,*tb;

CreateTBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,D))");

printf("-XW：")；DispTBTNodc(b);printf(',\n'');

(b=CreaThread(b);

printf("线索中序序歹J:");ThInOrder(tb);printf("\n");

3.实验结果

此处填写程序运营结果。

4.实验心得

此处填写你的实验心得体会。

实验13:哈夫曼编码

一、实验目的

D熟悉哈夫曼树的基本操作。

2）掌握哈夫曼编码的实现以及实际应用。

3）加深对哈夫曼树、哈夫曼编码的理解，逐步培养解决实际

问题的编程能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计4学时。

三、实验内容

【问题描述】

运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传输时间，减少传输成

本。但是，这规定发送端通过一个编码系统对数据进行编码，在接受端将传来的数据进行译

码。试为这样的信息收发站写一个哈夫曼编码/译码系统。

【基本规定】

(1)本系统应实现以下功能：(功能1〜3必做,4为选做，请课后自行完毕)

(2)初始化：字符集(字母a〜z,空格)共27个字符，以及其权值。建立哈夫曼

树。并建立各个字符的哈夫曼编码。

(3)打印字符集的哈夫曼编码.

(4)编码：从终端读入字符串，实现该字符串的编码。

译码：实现刚才生成的哈夫曼编码还原为字符串。(选做)

【已知条件】

(1)字符集的权值如下表:

字符ABCDEFGH1JKLM

186必13223210321154757153220

字符N0PQRSTUVWXYZ

________

族度5763151485180238181161

【实验提醒】

数据结构的定义：

#defineN50/*叶子结点数*/

#defineM2*N-1/*树中结点总数*/

typedcfstruct

chardata;/*结点值*/

intweight;/*权重*/

intparent;/*双亲结点*/

intIchild;/*左孩子结点*/

intrchild;/*右孩子结点*/

}HTNodc;

fypedefstmer

(

charcd[N];/*存放哈夫曼码*/

intstart;

}HCode;

各个函数的定义：

voidCreateHT(HTNodehtLJjntn)/*创建哈夫曼树*/

voidCrcatcHCodc(HTNodcht[],HCodchcd[]jntn)/*创建哈夫曼编码*/

voidDispHCode(HTNodeht[],HCodehcd[],intn)/*显示各个字符的哈夫曼编码可

voidEncode(char*s,HTNodehl[],HCodehcd[],intn)//显示字符串s的哈夫曼编码号

主函数的结构：

char

'o'/p'/q'/r'/s'/f/u'.'v'/w'/xVy'：/);/*字符集*/

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};/*字符集相应的权值*/

CreateHTO;

CreateHCode();

DispHCodc();

gcts(s);

Encode();

实验14:图的存储和遍历

一、实验目的

D熟悉图的基本操作。

2）掌握图的存储实现以及遍历操作。

3）加深对图的理解，逐步培养解决实际问题的编程能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计2学时。

三、实验内容

【基本规定】

1.用邻接矩阵存储方式，表达卜面的图，并输出。

2、由上面的邻接矩陇产生邻接表，并输出。

3.编程完毕从顶点0开始的深度优先遍历和广度优先遍历。

【输出结果】

输出结果例子如下:

有向图G的邻接矩阵：

050700

004000

800009

005006

000500

300010

图G的邻接矩阵转换成邻接表:

0:13

1:2

【提醒】

#include<stdio.h>

#includc<malloc.h>

#defineMAXV100/*最大顶点个数*/

#defineINF32767/*INF表达8*/

typedefintInfbType;

/*以卜.定义邻接矩阵类型*/

typedefstruct

{intno;/*顶点编号*/

InfbTypeinfb;/*顶点其他信息*/

}VcrtcxType;/*顶点类型可

typcdcfstruct产图的定义*/

{intcdgcs[MAXVJlMAXVJ;/*邻接矩阵*/

intvexnum.arcnuni;/*顶点数，弧数*/

VertexTypevexsfMAXV];/*存放顶点信息*/

)MGraph;/*图的邻接矩阵类型初

产以下定义邻接表类型列

typedefstructANode/*弧的结点结构类型*/

{intadjvex;/*该弧的终点位置*/

structANode*nextarc;/*指向下一条弧的指针*/

InfoTypcinfo;/*该弧的相关信息，这里用于存放权值*/

}ArcNode;

typedefintVertex;

typedefstructVnode/*邻接表头结点的类型*/

{Vertexdata;/*顶点信息*/

ArcNode*firstarc;/*指向第一条弧*/

}VNode;

typedefVNodeAdjList[MAXV];/*AdjList是邻接表类型*/

typedefstruct

{AdjListadjlist;/*邻接表*/

intn,e;/*图中顶点数n和边数e*/

}ALGraph;/*图的邻接表类型*/

intvisitedfMAXVl;/*全局数组*/

।*&）；/*邻接矩阵转为邻接表*/

voidDispMat(MGraph);六输出邻接矩阵，

voidDispAdj(ALGraph*);/*输出邻接表*/

voidDFS(ALGraph*Gintv);/*深度优先遍历*/

voidBFS(ALGraph*Gintv)；/*广度优先遍历号

voidmain()

(

inti.j;

MGraphg;

ALGraph*G;

intA[MAXV][6]={

{050,7,0.0},

(0,0,4,0A0},

(8,0,0,0,0,91,

{0,0,50,0,6},

(0,0,0,5,0.0},

{3,0,0,0J,0}};

g.vexnum=6;g.arcnum=1();

for(i=0;i<g.vexnum;i4-+)

for(j=0;j<g.vexnum;j+4-)

g.edges[i][j]=A[i][j];

printf("\n");

printf("有向图G的邻接矩阵:\n");

DispMat(g);

G=(ALGraph*)malIoc(sizeof(ALGraph));

printf（"图G的邻接矩阵转换成邻接表:\n"）;

MatToList(g.G);

DispAdj(G);

printf("\n");

printf("从顶点0开始的DFS:\n");

DFS(GO);

printf("\n");

printf("从顶点0开始的BFS:\n");

BFS(GO)；

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算法求最小生成树

一、实验目的

D熟悉图的基本操作。

2）掌握运用Prim算法求图的最小生成树。

3）加深对图的理解，逐步培养解决实际问题的编程能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计2学时。

三、实验内容

【基本规定】

编写一个程序，对于如下的无向带权图，运用Prim算法输出从顶点。出发的最小生成

树。

实验16:图综合实验

一、实验目的

D熟悉图的基本操作。

2）掌握求图的最短途径算法。

3）加深对图的理解，逐步培养解决实际问题的编程能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计4学时。

三、实验内容

【基本规定】

（1）给定n个村庄之间的交通图。若村庄i和j之间有路可通，则i和j用边连接，边上的

权值Wij表达这条道路的长度。现打算在这n个村庄中选定一个村庄建一所医院。

编写如下算法：

求出该医院应建在哪个村庄，才干使距离医院最远的村E到医院的路程最短。

求出该医院应建在哪个村庄，能使其它所有村庄到医院的途径总和最短。

【提醒】

,对于问题（1）,可以先求出每个村庄到其它所有村庄的最短途径，保存其最大值（表达

假设医院建在该村庄，距离•医院最远的村庄的途径长度）；然后在这些最大值中找出一

个最小值。

/对于问题（2）,可以先求出每个村庄到其它所有村庄的最短途径，保存其累加和（表达

假设医院建在该村庄，其它所有村庄距离医院的途径总和）：然后在这些和中找出一个

最小值。

自己设定n个村庄的交通图。例如下图所示:

5

0I

实验17:线性查找

一、实验目的

I）熟悉查找的基本操作。

2）掌握线性查找（顺序查找、二分查找）的实现。

3）加深对查找的理解，逐步培养解决实际问题的编程能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计2学时。

三、实验内容

I.顺序查找

编写一个程序，输出在顺序表中｛3,6,2,1（）,1,8,5,7,4,91中采用顺序查找的方法查找关键

字5的过程。

2.二分查找

【基本规定】

编写一个程序，输出在顺序表中｛1,2,3,4,5,6,7,8,9,10）中采用二分查找法查找关键字9的

过程。

【输出结果】

输出结果例子如下:

第1次查找:在[09中查找到元素R[4]:5

第2次查找:在[5,9]中查找到元素R[7]:8

第3次查找:在[8,9]中查找到元素R18]:9

元素9的位置是8

一、实验目的

1)熟悉查找的基本操作。

2)掌握哈希查找的实现。

3)加深对查找的理解，逐步培养解决实际问题的编程能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计2学时。

三、实验内容

【基本规定】

(1)编写一个程序，实现哈希表的相关运算，并在此基础上完毕如下功能：

(2)建立｛16,74,60,43,54,90,46,31,29,88,77｝哈希表A[0..⑵,哈希函数为H(k)=key%p,(p

取13),并采用线性探杳法解决冲突.

（3）在上述哈希表中查找关键字为29的记录。

在上述哈希表中删除关键字为77的记录，再将其插入。

【输出结果】

输出结果例子如下:

哈希表地址:023456789101112

哈希表关键字:7754164331294660748890

搜索次数:2111411

平均搜索长度ASL(11)=1.36364

ha[6].key=29

删除关键字77

哈希表地址:01234567891()1112

哈希表关键字:54164331294660748890

实验19:查找综合实验

一、实验目的

D熟悉查找的基本操作。

2）掌握二叉排序树的基本运算。

3）加深对查找的理解，逐步培养解决实际问题的编程能力。

二、实验环境

装有VisualC++6.0的计算机。

本次实验共计4学时。

三、实验内容

1.记录字符串中字符出现的次数

编写一个程序，由键盘输入一个字符串，记录该字符串中出现的字符及另一方面数。然后输

出结果。规定用一个二叉树来保存解决结果，字符串中每个不同的字符用树的结点表达，结

点应当包含四个域：该