《算法与数据结构》

实验指导手册

计算机教研室

2008.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分别表示迷宫中的通路和障碍，如下图迷宫数据为：

1111111111

1001000101

1001000101

1000011001

1011100001

1000100001

1010001001

1011101101

1100000001

1111111111

入口位置：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，并输出三元组表示。

提示：程序中可以用int A[4][4]和B[4][4]二维数组表示原始矩阵A和B。

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

（3）       设c＝a＋b，输出c的三元组表示。

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

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

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

提示：程序中可以用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的四种遍历顺序

【实验提示】

数据结构的定义：

#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开始的深度优先遍历和广度优先遍历。

【输出结果】

输出结果例子如下：

【提示】

#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）       求出该医院应建在哪个村庄，能使其它所有村庄到医院的路径总和最短。

【提示】

ü  对于问题（1），可以先求出每个村庄到其它所有村庄的最短路径，保存其最大值（表示假设医院建在该村庄，距离医院最远的村庄的路径长度）；然后在这些最大值中找出一个最小值。

ü  对于问题（2），可以先求出每个村庄到其它所有村庄的最短路径，保存其累加和（表示假设医院建在该村庄，其它所有村庄距离医院的路径总和）；然后在这些和中找出一个最小值。

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

实验17：线性查找

一、实验目的

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

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

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

二、实验环境

装有Visual C＋＋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的过程。

【输出结果】

输出结果例子如下：

实验18：哈希查找

一、实验目的

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

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

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

二、实验环境

装有Visual C＋＋6.0的计算机。

本次实验共计2学时。

三、实验内容

【基本要求】

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

（1）       建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0..12]，哈希函数为H(k)=key%p，（p取13），并采用线性探查法解决冲突。

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

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

【输出结果】

输出结果例子如下：

实验19：查找综合实验

一、实验目的

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

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

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

二、实验环境

装有Visual C＋＋6.0的计算机。

本次实验共计4学时。

三、实验内容

1、统计字符串中字符出现的次数

编写一个程序，由键盘输入一个字符串，统计该字符串中出现的字符及其次数。然后输出结果。要求用一个二叉树来保存处理结果，字符串中每个不同的字符用树的结点表示，结点应该包含四个域：该字符、该字符出现的次数、左子树指针、右子树指针；其中左子树的字符的ASCII码均小于该字符，右子树的字符的ASCII码均大于该字符。

提示：

ü  从字符串中依次读取字符，在二叉树中查找该字符是否存在。

ü  如果存在，则该字符的出现次数加1；如果不存在，则按照二叉排序树的要求插入该字符结点，同时设置出现次数为1。

ü  全部字符读完以后，调用二叉树的中序遍历，有序的输出每个字符及其出现的次数。

2、二叉排序树

【基本要求】

编写一个程序，实现二叉排序树的基本运算，并在此基础上完成如下功能：

（1）       由{4，9，0，1，8，6，3，5，2，7}创建一棵二叉排序树bt，并以括号表示法输出。

（2）       判断bt是否为一棵二叉排序树。

（3）       采用递归和非递归两种方法查找关键字为6的结点，并输出其查找路径。

（4）       分别删除bt中的关键字为4和5的结点，并输出删除后的二叉排序。

【输出结果】

输出结果例子如下：

实验20：内排序

一、实验目的

1）熟悉排序的基本操作。

2）掌握各种内排序的操作。

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

二、实验环境

装有Visual C＋＋6.0的计算机。

本次实验共计4学时。

三、实验内容

【基本要求】

a)         编写一个程序，实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。

b)        编写一个程序，实现冒泡排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。

c)         编写一个程序，实现快速排序算法，并输出{6,8,7,9,0,1,3,2,4,5}的排序过程。

d)        编写一个程序，实现直接选择排序算法，并输出{6,8,7,9,0,1,3,2,4,5}的排序过程。

e)         编写一个程序，实现堆排序算法，并输出{6,8,7,9,0,1,3,2,4,5}的排序过程。

【输出结果】

a）的输出结果例子如下：其他的输出结果类似，要求输出排序每一步骤的状态。

实验21：内排序综合实验

一、实验目的

1）熟悉排序的基本操作。

2）掌握各种内排序的操作。

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

二、实验环境

装有Visual C＋＋6.0的计算机。

本次实验共计4学时。

三、实验内容

某个二维数组存放了一系列的字符串，试利用排序的一些算法（如插入、冒泡、快速排序等）对这些字符串按照字典顺序进行排序。

例如：二维数组的字符串如下：

char  s[][20]={“while”，”if”，“else”，”do”，“for”，”switch”，“case”};