数据结构实验指导书(20xx级)

《数据结构》

实验指导书

高级语言、数据结构与算法课程组

绍兴文理学院教务处

二零一三年二月版

数据结构实验步骤、规范的要求与建议 ---------------------------------- 2

数据结构实验时间安排 --------------------------------------------------- 3

数据结构实验报告示例 --------------------------------------------------- 4

实验一、大整数加法------------------------------------------------------ 10

实验二、栈序列匹配 ----------------------------------------------------- 14

实验三、二叉排序树 ----------------------------------------------------- 17

实验四、最小生成树 ----------------------------------------------------- 21

附录：VC有关操作的提示 ----------------------------------------------- 27

数据结构实验步骤、规范的要求与建议

从以往教学实验的经验来看，在初学阶段严格按实验步骤的要求去做，有助于养成良好的程序编制风格，培养严谨、科学、高效的工作方式。经常发现很多学生抱怨说，化了两个小时才找出一个错误，甚至一无所获。他们不明白造成这种情况的原因，正是他们自己。有的学生不屑于按实验步骤去做，甚至对于实验步骤的要求看都不看一遍，认为那是浪费时间，这是极其有害的。有的学生甚至主要是抄袭别人的，以应付检查，这是学习上的堕落，是很危险的！

实验题目配合课程的进度，请同学们务必自己独立完成。为了锻炼自己的应用各种不同的数据结构的能力，尽可能的多做一些题目是非常必要的。在完成各种不同题目的过程中，加深对数据结构的理解和把握，提高编程和实践能力，从而帮助你在更高的角度解决各种应用问题。

按实验步骤进行实验，不但可以培养科学化的工作作风，而且还能有效地避免错误，提高实验效率，达到实验目的。具体的要求如下：

1、问题分析与系统的结构设计：

充分地分析和理解问题本身，弄清要求作什么，限制条件是什么。按照以数据结构和功能模块为中心的原则划分模块，即定义数据结构及其在这些结构之上的操作，使得对数据结构的存取通过这些操作加以实现。在这个过程中，要考虑系统结构清晰、合理、简单并且易于调试。最后写出每个子程序(过程或函数)的规格说明，列出它们之间的调用关系，可以使用调用关系图表示则更加清晰，这样便完成了系统结构设计。

2、详细设计和编码

详细设计的目的是对子程序(过程或函数)的进一步求精。可以用IF、WHILE等伪代码等自然语言写出算法的框架，以避免陷入细节。在编码时，可以对详细设计的结果进一步求精，用高级语言表示出来。也可以直接用高级语言来描述算法。

程序的每一行最好不超过60个字符。每个子程序(或过程、函数)通常不要太长，以不超过40行为宜。子程序(或过程、函数)包含的程序行数太多，易于造成理解的困难。控制循环和判断等语句的连续嵌套的深度。程序的目的性必须明确。对每一段程序完成的作用，除非常明显的除外，尽可能加以注释。这会对程序的调试提供很多方便。另外，根据情况可以设立若干调试点，即输出若干信息，用于验证和你的设想是否一致。

3、上机调试程序

自底向上，先调试底层模块，再调试上层模块。最后，整个程序进行联调。调试正确后将源程序和运行结果加以输出。

4、实验报告的书写

(1) 需求分析

问题描述，求解的问题是什么。包括实验的任务、输入、输出、功能、测试数据等。

(2) 概要设计

设计思想：存储结构、主要的算法思想。

设计表示：主程序、子程序(过程或函数)的规格说明，通过调用关系图表示它们之间的调用关系。

(3) 详细设计

数据类型。

主程序和其他模块的算法或算法框架。

(4) 调试分析

问题是如何解决的，讨论与分析、改进设想、经验与体会、时空复杂度等。至少写三点。

(5) 测试结果

列出你的测试结果，包括输入的测试数据和输出的结果。测试数据应该完整和严格，必要时用多组数据进行测试。

(6) 用户手册：

使用说明。即说明你的程序在什么环境下运行，怎么运行等。

(7) 附录

源程序文件名，实验结束时源程序的电子稿要归档。

数据结构与算法实验时间安排(32学时)

数据结构与算法实验时间安排(16学时)

数据结构实验报告示例

约瑟夫环

一、需求分析

1、实验任务是用循环单链表(不带头结点)来实现约瑟夫环。循环单链表的结点结构中包含环内代表人的编号和密码。

2、对于输入的人数(n)和n个密码，建立不带头结点的单循环链表。

3、对于密码m，从相对的第一个人开始报到第m个人，输出相对于开始报数的第m个人的信息。

4、输出过程及输出完n个人的信息，即实现了约瑟夫环的功能。

5、测试数据

m的初值设为6；

(1) 对于n=7，7个人的密码依次为：3，1，7，2，4，8，4进行测试。

(2) 对于从键盘输入的n和n个人的密码进行测试。

二、概要设计

1、数据类型

(1) n个人的编号和密码的数据元素结构

typedef struct // 用于接收数据的输入

{int num;

int m;

}data;

(2) 单向循环链表结点结构

typedef struct node

{ int num;

int m;

node *next;

}node,*link;

2、算法思想

(1) 输入n个人的密码，分别和依次按1到n的编号，输入到一个结构体数组，以便为建立单循环链表作数据准备；

(2) 根据结构体数组中的数据，建立单循环链表；

(3) 由得到的单向循环链表，根据约瑟夫问题的要求，构造约瑟夫函数，该函数中设置2个指针p和 q，p指向当前报数的结点，q指向p结点后面的结点，开始时，q应指向单向循环链表的最后一个结点。对于出列的人(结点)，在该函数中输出其编号。该函数被主函数调用。

(4) 在主函数中设置结构体数组，调用输入模块，把输入的n个人的密码和依次按1到n的编号，存储到一个结构体数组，然后调用建立有n个结点构成的单向循环链表的函数，最后调用约瑟夫函数，实现约瑟夫问题的求解。

3、各子模块

(1) 输入数据模块

该模块中输入n及n个人的编号和密码，依次存储于data类型的结构体数组；

(2) 建立单循环链表模块

该模块中根据结构数组中的数据，建立不带头结点的单循环链表，其结点中的数据是人的编号和密码；

(3) 约瑟夫问题求解模块

该模块中根据单向循环链表，从第一个人(结点)开始报数，报到密码m时(初始密码m可为6)该(人)结点出列，并输出相应的信息和得到新的密码，为下一次报数做准备，直至每个人(结点)全部出列，输出的信息即为约瑟夫问题的求解。

4、主模块及与子模块的调用关系

(1) 主模块

设置data类型的结构体数组和有关变量，然后依次调用输入数据模块、建立单循环链表模块和约瑟夫问题求解模块。

(2) 各模块之间的调用关系

主程序模块

输入数据模块建立单循环链表模块约瑟夫问题求解模块

三、详细设计

1、数据结构

typedef struct

{int num;

int m;

}data;

typedef struct node

{int num;

int m;

struct node *next;

}node,*link;

2、输入数据模块(用源代码也可以，但以伪代码比较好,下同)

void inputdata(int n，data man[])

{

输入n；

for i=0 to n-1

{

输入密码m;

man_i.num←i+1;

man_i.d←m;

}

3、建立单循环链表模块

void createlinklist(int n, data man[],link &l)

{

link l,p,q;

l←new node;

l->num=←man₀.num;

l->m←man₀.m;

q=l;

for i=1 to n-1

{

p=←new node;

p->num=←man_i.num;

p->m←man_i.m;

q->next←p;

q←p;

}

q->next←l;

}

4、约瑟夫问题求解模块

void joseph(link l,int n)

{

link q,p,s;

m=6;

q←l->next;

while(q->next≠l) q←q->next;

p←l;

for i=0 to n-1 // 重复n次

{

for j=1 to m-1 // 找第m个人

{

q←p;

p←p->next;

}

s←p;

q->next←p->next;

p←p->next;

output s->num;

m←s->m;

delete s;

}

5、主程序模块

void main()

{

link l; int n;

data man[100];

input n;

inputdata(n，man);

createlinklist(n,man,l);

joseph(l,n);

}

四、调试分析

1、由于建立的是带头结点的单循环链表，导致输出的结果许多是错的，删除头结点，即建立的是不带头结点的单循环链表解决。

2、由于开始时没有指针指向要开始报数结点后的指针，导致当开始密码是1时不能删除第一个结点，出现输出乱的现象，经检查发现该错误，采用在joseph函数的开始就扫描单循环链表，使指针其指向单循环链表的最后一个结点，以便需要时能删除第一个结点，也就是说，在数结点时后面要跟一个指针，以便当数到要删除那个结点时，通过对后面跟着的指针所指结点的操作能删除数到的结点，这样就解决了这个问题。这一点也提醒我们，单恋表中的操作，要删除结点，必须有指向其“前驱”结点的指针，否则是不能删除要删除的结点的。

3、由于先删除了结点空间，没有把被删结点中的密码保存，出现得到的密码不是被删结点的密码，而是被删结点下一个结点的密码，导致输出的信息不正确，修改成在删除结点空间前先保存其密码而解决。

4、算法的时间复杂度

设约瑟夫问题中的人数为n,则建立单链表的时间复杂度是Ο(n)，约瑟夫问题的求解模块中，要n次出列人，而每次出列人要走m个结点，设密码的平均值为m，则约瑟夫问题求解模块的时间复杂度为Ο(n×m)。

所以算法的时间复杂度为○(n)。

五、测试结果

第一组：

Input

3 1 7 2 4 8 4

Output

6 1 4 7 2 3

第二组：

Input

5 2 9 6 8 3 11 4 7 10

Output

6 9 7 2 4 5 3 1 8 10

测试通过。

六、用户使用说明

1、本程序的运行环境为windows操作系统下命令执行方式，执行文件为：exp1.exe；也可在VC集成环境下执行。

2、运行程序后输入人数n后，按提示依次输入n个密码即可。输出的是约瑟夫问题的求解过程中出列人的编号。见下图。

七、附录

源程序文件名清单：exp1.cpp。实验结束后上交。

实验一、大整数加法

一、问题描述

给定两个非负整数A和B, 计算出A+B的值。整数A和B的位数可能超过整数类型数据能存储的范围。要求计算并输出A+B的值。

二、基本要求

1、正确输入两个大整数；

2 利用两个单链表存储结构存储两个大整数；

3 对存储于单链表的两个大整数，根据数据加法的要求，通过对链表的操作，使两个大整数的和存储于单链表，并考虑尽量使用原单链表存储空间；

4 输出两个大整数的和，即输出和单链表中的内容。

三、测试数据

第一组

99999999999999999999

第二组

12345678987654321

9876543212345678987654321

第三组

88888888888888888888888888888888

6666666666666666666666666666666666666666

四、实现提示

1、算法思路

(1) 正确输入两个整数，由于其整数位数可能超过整数数据类型可以存储的范围，所以要用字符串的数据类型来接受输入的两个整数。可以在主函数里完成。

(2) 对于存储在字符串里的整数，依次根据字符串中从高位到低位的数值位，可以用前插法建立单链表的方法，将整数存储于带头结点的单链表中(每个结点存放一位数字，也可存放多位数字，前者简单一点。本指导按前者的处理方法描述)，这时，从单链表的第一个结点到尾结点依次是从个位到最高位的整数，以便相加运算。

也可依次根据字符串中从低位(字符串的右端)到高位(字符串的左端)的数值位，用后插法建立单链表的方法，将整数存储于带头结点的单链表中。

也可依次根据字符串中从高位(字符串的左端)的数值位到低位(字符串的右端)的数值位，用后插法建立单链表的方法，将整数存储于带头结点的单链表中，这时，从单链表的第一个结点到尾结点依次是从最高位到个位的整数，然后再逆置这个单链表，使从单链表的第一个结点到尾结点依次是从个位到最高位的整数。

以上过程可用一个函数完成。

(3) 对两个从单链表的第一个结点到尾结点依次是从个位到最高位存储的两个整数，从第一个结点开始，依次扫描到长度短的单链表的尾结点，每次把扫描到的两个结点中的数值及前面相加留下的进位相加，把和的个位存储到长度长的单链表对应的结点中，同时记录进位；然后把可能有的进位依次与长单链表还未相加过的结点依次相加，若到最后一个结点相加后仍有进位，则要新增加一个结点，以存放进位。至此，两个整数的和已经存储在原来长的单链表中了。

这个过程可以一个函数完成。

(4) 对于已经存储好的和的单链表，其第一个结点到尾结点依次是和的个位到最高位，要对该单链表进行逆置，这个过程可用以函数完成。然后可将其单链表中结点的值输出，这也可用一函数完成。

(5) 在主函数中要设置相关的数据结构，以存放两个整数和单链表，输入两个整数后，依次可调用单链表初始化模块、建立单链表模块、两个整数相加模块、单链表逆置模块和输出单链表中结点的值的模块。中间可确定好较长整数所对应的单链表指针，以供两个整数相加模块使用。

2、数据结构

存放输入的整数可用string类型字符串，也可用char类型一维字符数组。

存放整数的单链表中的结点结构可以是：

typedef struct node

{ int data;

node *next;

}*linklist;

3、基本操作

(1) 构造一个空的带头结点的单链表l，用单链表中每个结点的数据域存放每一个整数位。

initlist(linklist &l)

{

}

该函数可在主函数中调用。

(2) 依次根据存放整数的字符串s1中从高位到低位的数值位，前插法建立带表头结点的单链表。

createlist_f(linklist l,string s1)

{

for(s1中的每一个数字字符)

转化成数值；

存于结点并连接到单链表的头部；

}

该函数可在主函数中调用。

(3) 单链表逆置。以便把单链表转换成所需要的从第一个结点到尾结点依次是从最高位到个位整数(要相反顺序也一样)。

inverse(linklist l)

{

…

}

该函数可在主函数或相关函数中调用。

(4) 输出单链表中的元素值。

print(linklist l)

{

…

}

该函数可在主函数中调用。

(5) 整数相加。其中l1、l2是存放两个整数的单链表，l是较长整数的单链表。

add(linklist l1,linklist l2,linklist l)

{

指针指向存放较长整数单链表的第一个结点；

指针指向两个整数单链表的第一个结点；

while(指向两个整数单链表均不空)

{

计算两个整数单链中的数值和进位的和；

记录进位；

把和的个位存储于较长整数单链表的结点；

各指针均向后移动一个结点；

}

while(有进位且较长整数单链表不空)

{

计算较长整数单链表中的数值和进位的和；

记录进位；

把和的个位存储于较长整数单链表的结点；

指向较长整数单链表的结点指针向后移动一个结点；

}

if(还有进位)

{

较长整数单链表增加结点，存放最后的进位。

}

该函数可在主函数中调用。

4、主程序

main()

{

…

输入两个整数；

调用相关模块，将单链表初始化后将两个整数存储于单链表；

确定较长整数的单链表；

调用整数相加模块进行整数相加；

调用链表逆置模块对单链表的数位进行逆置；

调用输出模块输出和单链表；

}

五、测试与输出结果

Sample Input

12345678987654321

9876543212345678987654321

88888888888888888888888888888888

6666666666666666666666666666666666666666

Sample Output

9876543224691357975308642

6666666755555555555555555555555555555554

实验二、栈序列匹配

一、问题描述

对于给出的入栈序列和出栈序列，判断这两个序列是否相容。即能否利用栈操作将入栈序列转换为出栈序列。

二、基本要求

入栈序列和出栈序列均为字符型数据，由键盘输入，其长度不超过10个字符。若入栈序列和出栈序列相容(即能利用栈操作将入栈序列转换为出栈序列)，则输出yes，否则输出no。在判断栈序列的匹配过程中，输出入栈、出栈的过程和栈中的元素。

三、测试数据

输入数据的第一行为一个正整数T, 表示测试数据的组数。然后是T组测试数据。每组测试数据的输入是在同一行中用一个空格分隔的两个字符串(其长度均不超过10)，依次表示入栈序列和出栈序列。

输出格式为每入栈(或)出栈一次输出一行：push(或pop):c stack:栈顶到栈底的序列，其中c为入栈(或)出栈的字符，最后一行个根据入栈序列和出栈序列是否匹配输出yes或no，匹配则输出yes，否则输出no(参见Sample Output)。

四、实现提示

1、算法思路

设置链式栈或顺序栈s，作为入栈序列的栈空间，设置top为其栈顶指针(或下标)。

对入栈序列从第一个元素开始考虑入栈，在依次扫描出栈序列元素的过程中进行如下的处理：

若栈空且入栈序列有未入栈的元素，则当前入栈序列中的元素入栈，并输出相应的信息；

若栈不空且栈顶的元素为出栈序列的当前元素，则栈顶元素出栈，并输出相应的信息，否则，若入栈序列有未入栈的元素，则当前入栈序列中的元素入栈，并输出相应的信息；否则可以确定输入的入栈序列和出栈序列不相容(即不匹配)。

最后判断：若入栈序列和出栈序列均已扫描完且栈为空，则可以确定输入的入栈序列和出栈序列相容(即匹配)。

2、数据结构

typedef struct node // 链式栈s中的结点结构

{char data;

struct node *next;

}StackNode,*LinkStack;

3、基本操作

LinkStack push(LinkStack top,char e) // 入栈操作，e为栈中元素类型

LinkStack pop(LinkStack top, char *e) // 出栈操作,e为指向栈中元素的指针类型，为的使其值在函数外面可用

void list(LinkStack top) // 显示栈中元素

int judge(string str1,string str2) // 判断是否匹配主模块，str1和str2为入栈序列和出栈序列

{ 栈初始化；从出栈序列的第一个元素开始；

while(出栈序列还未扫描完)

{ if(栈空且入栈序列有未入栈的元素)

当前入栈序列中的元素入栈，并输出相应的信息；

if(若栈不空且栈顶的元素为出栈序列的当前元素)

栈顶元素出栈，并输出相应的信息，

else if(若入栈序列有未入栈的元素)

当前入栈序列中的元素入栈，并输出相应的信息；

else 确定输入的入栈序列和出栈序列不相容(即不匹配)。

}

if(若入栈序列和出栈序列均已扫描完且栈为空)

确定输入的入栈序列和出栈序列相容(即匹配)。

else 确定输入的入栈序列和出栈序列不相容(即不匹配)。

}

4、主程序

int main()

{ 输入入栈序列和出栈序列；

调用判断是否匹配主模块judge()；

根据其返回的值输出yes或no。

}

五、测试与输出结果

第一组：

输入：ABCDEF DCEFAB

输出：

push:A stack:A

push:B stack:BA

push:C stack:CBA

push:D stack:DCBA

pop:D stack:CBA

pop:C stack:BA

push:E stack:EBA

pop:E stack:BA

push:F stack:FBA

pop:F stack:BA

第二组：

输入：ABCDEF ACEDBF

输出：

push:A stack:A

pop:A stack:

push:B stack:B

push:C stack:CB

pop:C stack:B

push:D stack:DB

push:E stack:EDB

pop:E stack:DB

pop:D stack:B

pop:B stack:

push:F stack:F

pop:F stack:

yes

实验三、二叉排序树

一、问题描述

输入一个整数关键字序列L，生成一棵用链式存储结构存储的二叉排序树，对该二叉排序树能进行查找和插入结点的操作，并对该二叉排序树中结点的关键字按递增和递减顺序输出。

二、基本要求

输入数据的第一行为一个正整数T, 表示测试数据的组数。然后是T组测试数据。每组测试数据的第一行输入正整数n(5≤n≤20)，第二行输入n个整数，要求依次完成以下工作：
(1) 以这n个整数生成(建立)一棵用链式存储结构存储的二叉排序树；
(2) 按递增顺序输出该二叉排序树中的整数(关键字)；
(3) 输入一个整数key，对该二叉排序树进行查找，若在该二叉排序树中存在这个整数key，则输出find，否则输出not find。
(4) 输入一个整数key，若该二叉排序树中不存在这个整数key，则将key插入到该二叉排序树中，使插入后仍为原性质的二叉排序树；否则不必插入；
(5) 在(4)的基础上，按递减顺序输出该二叉排序树中的整数(关键字)。

三、测试数据

输入数据的第一行为一个正整数T, 表示测试数据的组数。然后是T组测试数据。每组测试数据的第一行输入正整数n(5≤n≤20)，第二行输入n个整数，第三和第四行均输入整数key。

每组输出的第一行为按递增顺序输出该二叉排序树中的整数(关键字)，每两个整数之间一个空格；第二行为find或not find；第三行为按递减顺序输出该二叉排序树中的整数(关键字)。

第一组：

10 79 6 81 43 75 26 69

第二组：

94 22 25 24 20 42 39 71 53 57

四、实现提示

1、算法思路

(1) 首先要建立二叉排序树。我们要建立的二叉排序树，其关键字要求是各不相同的，则对于输入的关键字(整数)序列中的每一个整数，要在正在建立的二叉排序树中去查找是否已经存在该整数，不存在时，由查找模块(其算法思路后述)返回要增加(插入)结点位置的双亲结点，根据要建立的二叉排序树的性质(左小右大)，当要增加的整数比双亲结点的整数小的话就插(挂)到其左孩子的位置，否则插(挂)到其右孩子的位置。这样重复，直到输入结束(输入的整数为-1)，这样，二叉排序树就建好了。

(2) 查找算法是从二叉排序树的根结点开始，根据要查找的整数，若比其当前二叉排序树结点中的整数小就进入其左孩子所在的左子树中继续搜索，否则进入其右左孩子所在的右子树中继续搜索，这过程中，每进入子树前，保存当前结点(指针)，以便带回要增加(插入)结点的双亲结点。搜索直至找到要查找的整数，用一指针带回；或搜索直至叶子结点的下方，找不到要查找的整数而使空指针带回，以便判断要查找的整数是否找到。

(3) 按递增顺序输出该二叉排序树中的整数(关键字)，可直接用某种二叉树的遍历算法实现；按递减顺序输出该二叉排序树中的整数(关键字)，只要对某种二叉树的遍历算法稍作修改即可。

(4) 插入算法思路和建立二叉排序树时增加一个整数的思路是一样的。

2、数据结构

typedef struct node // 二叉排序树中的结点结构

{int data; // 整数(关键字)数据域

struct node *lchild,*rchild; // 指向左右孩子的指针

}nodeb,*bitree;

3、基本操作

(1) 查找算法

void searchbst(bitree t,bitree *f,bitree *p,int key)

{ // 在二叉排序树t中查找整数为key的结点，若找到，则p指向该结点，否则p为空。f 为

//指向双亲结点的

while(t不空且t中的整数不是要找的整数key)

{ 用f记录当前结点；

if(要找的整数key小于t中的整数)

t进入其左孩子所在的左子树；

else t进入其右孩子所在的右子树；

}

(2) 建立二叉排序树算法

bitree createbintree(int n) /* 建立有n个整数的二叉排序树，其二叉排序树t，用函数值返回树根*/

{ 置t为空树；

while(n次)

{ 输入整数；

查找该整数；

if(该整数在当前的二叉排序树中不存在)

{ 申请结点；

对该结点赋以该整数；

该结点的左右指针赋空值；

根据查找的结果，把该结点挂到某结点的左孩子或右孩子位置

// 注意当二叉排序树还是空树时情况的处理

}

返回建好的二叉排序树t；

}

(3) 插入(增加)整数算法

int insertbst(bitree *t,int key) /* 在二叉排序树t中插入整数key的结点，是否插入成功用函数值返回 */

{ 在二叉排序树t中查找整数key；

if(整数key在二叉排序树t中不存在)

{ 申请结点；

对该结点赋以该整数；

该结点的左右指针赋空值；

根据查找的结果，把该结点挂到某结点的左孩子或右孩子位置

// 注意当二叉排序树还是空树时情况的处理

}

else 插入不成功；

}

4、主程序

int main()

{

重复m组：

调用createbintree()算法建立二叉排序树t；

调用某种二叉树遍历算法按递增顺序输出该二叉排序树中的整数(关键字)；

输入要查找的整数，调用searchbst()算法查找要查找的整数；

根据查找的结果输出相应的信息；

输入要插入的整数，调用insertbst()算法将整数插入到二叉排序树中；

根据插入的结果输出相应的信息；

调用稍作修改的某种二叉树遍历算法按递减顺序输出该二叉排序树中的整数(关键字)；

}

五、测试与输出结果

第一组：

Sample Input

10 79 6 81 43 75 26 69

Sample Output

6 10 26 43 69 75 79 81

find

81 79 75 69 43 26 10 6

第二组：

Sample Input

94 22 25 24 20 42 39 71 53 57

Sample Output

20 22 24 25 39 42 53 57 71 94

not find

94 71 57 53 42 39 25 24 22 20 1

实验四、最小生成树

一、问题描述

给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法生成最小生成树，并计算得到的最小生成树的代价。要求显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。表示城市间距离网要求至少6个城市，8条边。

二、基本要求

从键盘输入n个顶点和m条边(6≤n≤15，n-1≤m≤20)，建立图的邻接表(邻接矩阵也可)存储图，然后输出该邻接表(邻接矩阵)，用Prim(或Kruskal)算法求出其最小生成树，输出最小生成树中的城市、城市间的道路及距离和最小生成树的代价。输入输出的形式可参见“五、测试与输出结果”。

三、测试数据

用下图所示的图建立邻接矩阵进行测试。

四、实现提示

1、算法思路

(1) 首先要建立图的邻接表，这部分的算法思路见《高级语言课程设计指导书》中的图的存储这一设计中的指导。有关对应的操作均给出了指导(这里略)。只是这里输入边的同时还要输入这条边上所带的权值，并存储好，这只是在邻接链表的结点中增加了一个数据域(weight)。并设定要求最小生成树的图为无向连通图，图中有n(n≥2)个顶点。

(2) 在邻接表方式存储图的基础上，用Prim算法生成最小生成树的主模块分以下两个部分：

第一部分(初始化)：

① 设计结构体数组，其元素有两个成员，一个是存放图中顶点的前驱顶点的序号(下标)；另一个是存放图中顶点到正在生成的最小生成树(中顶点)的最短距离；

② 对结构体数组中存放图中顶点到正在生成的最小生成树(中顶点)的最短距离初始均置为无穷大(可用一大正数)；

③ 在图中任取一起始顶点k(可选取存储的第一个顶点)作为正在生成的最小生成树的第一个顶点，然后扫描该顶点所对应的邻接链表中的每一个顶点，把k作为该顶点的前驱顶点；把该顶点中的权值作为该顶点到正在生成的最小生成树的最短距离。

④ 把顶点k做上已在正在生成的最小生成树中的记号(可置其到正在生成的最小生成树的最短距离为0，因为顶点间的距离不可能为0)

第二部分(用Prim算法思想求出最小生成树)：

除初始顶点已在正在生成的最小生成树中外，对于其余的n-1个顶点，重复下面的n-1步，每一步选取和正在生成的最小生成树中相连接的一个顶点和一条边加入到正在生成的最小生成树中：

① 找。找和正在生成的最小生成树连接的距离最短的一个顶点u。这个过程可以从余下的顶点到正在生成的最小生成树的最短距离中去找；

② 输出。依次输出顶点u的前驱顶点、u的前驱顶点到u 的距离和顶点u，累加好u的前驱顶点到u 的距离。这就是要输出的最小生成树中的一条边，并设置该顶点u和相应的边已连接在正在生成的最小生成树中；

③ 调整。随着顶点u和相应的边已连接在正在生成的最小生成树中，其他还不在正在生成的最小生成树中的顶点到正在生成的最小生成树(中的顶点)的最短距离可能变小，这样就需要对这些顶点到正在生成的最小生成树的最短距离进行可能的调整。这个过程可以与刚连接到正在生成的最小生成树的顶点u连接的顶点中去比较和调整。

第三部分(输出最小生成树的代价)：

输出生成的最小生成树中每条边上权值的累加值，即为所要求的最小生成树的代价。

2、数据结构

#define infinity 1000 // 设置权值的无穷大

typedef struct linknode // 邻接链表中的结点结构

{int adjvex; // 邻接的顶点的序号(下标)

int weight; // 邻接顶点间的距离(权值)

struct linknode *nextarc; // 指向下一个邻接顶点的指针

}lnode,*link;

typedef struct haednode // 邻接表表头数组中的元素结构

{char data; // 顶点元素

link firstarc; // 顶点元素所指向邻接结点所构成的邻接链表的指针

}hnode,*adj;

Struct // 用Prim算法生成最小生成树的主模块分中用到的结构体数组

{ int adjvex; // 存放图中顶点的前驱顶点的序号(下标)；

int lowcost; // 存放图中顶点到正在生成的最小生成树(中顶点)的最短距离；

}closedge[20];

3、基本操作

int locatevex(adj adjlist,char ch,int n) // 同高级语言课程设计中的图的存储

{ // 在有n个顶点的表头数组adjlist中查找字符ch所代表的顶点在表头数组的序号(下标)

}

link locateedge(adj adjlist,int i,int j) 同高级语言课程设计中的图的存储

{ // 从表头数组adjlist中序号i所对应的邻接链表中查找是否有对应序号j所对应的边

}

adj inputnode(int *n) // 输入n个顶点，同高级语言课程设计中的图的存储

{ 申请表头数组空间；;

输入一顶点v；

while(v不是结束标记)

{ if(v在表头数组中不存在)

v加入到表头数组中；

else // 可不做处理

输出相应信息；

输入一顶点v；

}

返回表头数组；

}

void createadjlist(adj adjlist,int n) // 在有n个顶点的表头数组adjlist中输入边，

{ // 建立图的邻接表，和高级语言课程设计中的图

// 的存储基本相同

输入边所在的顶点对；

while(顶点对不是结束标记)

{ if(顶点对存在且边不重复)

{ 申请两个邻接链表中结点的空间；

在结点中分别存入边所代表的两个顶点在表头数组中的序号(下标)；

在表头数组的序号(下标)所对应的两个邻接链表的前面插入这两条边；

}

else // 可不做处理

对于不符合要求的输入，对应输出不符合要求的情况；

输入边所在的顶点对；

}

void list(adj ht,int n) // 和高级语言课程设计中的图的存储基本相同

{ // 输出图的邻接表

// 可用V-->U(权值)的方式输出边

}

void minispantree_prim(adj ht,int n) // 主模块。用Prim算法生成最小生成树

{ // ht为图的邻接表的表头数组，n为图中的顶点数

struct

{ int adjvex;

int lowcost;

}closedge[20];

对n个顶点到正在生成的最小生成树(中顶点)的最短距离closedge[i].lowcost初始均置为无穷大infinity;

任取一起始顶点k(可选取存储的第一个顶点)作为正在生成的最小生成树的第一个顶点；

p指向顶点k所对应的邻接链表；

while(p不空)

{ p所指顶点的前驱顶点置为k；

p所指顶点到正在生成的最小生成树的最短距离置为p所指顶点的权值；

p指向下一个顶点；

}

置顶点k为已在正在生成的最小生成树中的标志；// 可把对应的最短距离置为0

for(余下的n-1个顶点)

{ 置min为无穷大infinity； // 在正在生成的最小生成树外的顶点中找距离正在

for(图中的所有顶点j) // 生成的最小生成树最短的顶点

if(顶点j的最短距离小于min且顶点j不在正在生成的最小生成树中)

{ min取顶点j的最短距离；

用k记录顶点j；

}

用适当的格式输输出顶点k的前驱顶点、k的前驱顶点到k 的距离和顶点k；// 输出

用sum累加好k的前驱顶点到k 的距离；

置顶点k为已在正在生成的最小生成树中的标志；

p指向顶点k所对应的邻接链表； // 调整

while(p不空)

{ if(p所指顶点的权值小于p所指顶点到正在生成的最小生成树的最短距离)

{ p所指顶点的前驱顶点置为k；

p所指顶点到正在生成的最小生成树的最短距离置为p所指顶点的权值；

}

p指向下一个顶点；

}

输出生成的最小生成树中每条边上权值的累加值sum；

}

4、主程序

int main()

{ 调用inputnode()函数，输入图中的顶点，用ht得到邻接表表头数组，返回顶点的个数n；

调用createadjlist()函数，建立图的邻接表；

调用list()函数，显示邻接表；

调用minispantree_prim()函数，用Prim算法生成最小生成树并输出相应的信息；

}

五、测试与输出结果

顶点输入：

NO 1: A

NO 2: B

NO 3: C

NO 4: D

NO 5: E

NO 6: F

NO 7: G

NO 8: H

NO 9: *

边输入：input u v w

A B 11

A C 13

B C 5

B D 2

B E 9

C D 8

C H 4

D E 7

D F 12

D G 5

D H 14

E F 10

F G 2

G H 6

* * 0

adjlist:

NO 1: A-->C(13)-->B(11)

NO 2: B-->E(9)-->D(2)-->C(5)-->A(11)

NO 3: C-->H(4)-->D(8)-->B(5)-->A(13)

NO 4: D-->H(14)-->G(5)-->F(12)-->E(7)-->C(8)-->B(2)

NO 5: E-->F(10)-->D(7)-->B(9)

NO 6: F-->G(2)-->E(10)-->D(12)

NO 7: G-->H(6)-->F(2)-->D(5)

NO 8: H-->G(6)-->D(14)-->C(4)

minispantree:

A-- 11 -->B

B-- 2 -->D

B-- 5 -->C

C-- 4 -->H

D-- 5 -->G

G-- 2 -->F

D-- 7 -->E

total lowcost: 36

VC有关操作的提示

1、有关屏幕操作提示

(1) 文本屏幕用默认的25行80列，其左上角的坐标为(1,1)。

(2) 使用彩色文本要用到如下函数：

void setColor(unsigned short ForeColor=4,unsigned short BackGroundColor=0)

{HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);

SetConsoleTextAttribute(hCon,ForeColor|BackGroundColor*16);

};

(3) 清屏语句可用system函数，调用方式为：void system(“cls”);

(4) 设置字符的背景颜色和前景颜色可用setColor函数，调用方式为：

void setColor(color); color：0～255。

编程序对这256种颜色(前景和背景色)的输出如下：

具体color 值对应颜色的前景和背景色如下：

(5) 屏幕上光标定位用到如下函数：

void gotoxy(int x, int y)

{COORD c;

c.X=x-1; c.Y=y-1;

SetConsoleCursorPosition (GetStdHandle(STD_OUTPUT_HANDLE),c);

}

(6) 屏幕上光标定位可用gotoxy函数，调用方式为：void gotoxy(int col,int row), 注意行列不是习惯顺序。

以上函数的使用均需头文件windows.h的支持。

在光标定位处显示输出同样可用printf函数。

2、有关随机数操作提示

(1) 随机函数的使用需要先执行如下的初始化随机数种子函数，只要执行一次即可。

srand((unsigned)time(NULL));

(2) 需要产生随机数可用rand函数, 调用方式为：int rand(),返回的是0～32767中的一个整数。

以上函数的使用需头文件stdlib.h和time.h的支持。

3、有关接收单个字符的操作提示

接收单个字符可用函数getch()和getche()函数，其调用格式为：

int getch(void); 和 int getche(void);

其中，getch()函数不回显输入的字符；而getche()函数回显输入的字符。

输出单个字符可用函数putch()函数，其调用格式为：

int putch(char ch);

以上函数的使用均需头文件conio.h的支持。

相关推荐

数据结构实验指导书(20xx级)

专栏推荐