当前位置：文档之家› 最小生成树问题,图形输出最小生成树

最小生成树问题,图形输出最小生成树

数据结构课程设计

系别电子信息系

专业计算机科学与技术

班级学号

姓名

指导教师

成绩

2012年7 月12日

1 需求分析 (2)

2 概要设计 (2)

2. 1抽象数据类型定义 (2)

2 . 2模块划分 (3)

3 详细设计 (4)

3. 1数据类型的定义 (4)

3. 2主要模块的算法描述 (6)

4 调试分析 (10)

5 用户手册 (10)

6 测试结果 (11)

7 附录(源程序清单） (13)

参考文献 (20)

一、需求分析

1.要在n个城市之间建设通信网络，只需要架设n-1条线路即可，而要以最低的经济代价建设这个通信网，就需要在这个网中求最小生成树。

(1)利用克鲁斯卡尔算法求网的最小生成树。

(2)实现教科书 6.5 节中定义的抽象数据类型 MFSet 。以此表示构造生成树过程中的连通分量。

(3)输入顶点个数，输入顶点序号（用整型数据[0，1，2，……，100]表示），输入定点之间的边的权值（整型数据）。系统构造无向图，并求解最小生成树。

(4)以图形和文本两种形式输出最小生成树。

2.程序执行的命令包括：

(1)随机生成一个图；

(2)输入图坐标信息；

(3)以文本形式输出最小生成树；

(4)以图形形式输出最小生成树；

(5)以图形形式输出构造的图；

(6)结束。

3.测试数据

(1)用户输入需要构造的图形顶点个数，假设顶点个数为4；

(2)C语言函数随机生成的图形，顶点分别为a,b,c,d,权值分别为：

ab=75,ac=99,ad=80,bc=33,bd=93,cd=19；

(3)最小生成树边的权值分别为:ab=75,bc=33,cd=19;

(4)结束。

二、概要设计

1. 图的抽象数据类型定义

ADT Gragh{

数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：

R＝{VR}

VR＝{| v,w∈V且P(v,w)，表示从v到w的弧，

谓词P(v,w)定义了弧的意义或信息 }

基本操作P：

CreateGraph(&G，V，VR)；

初始条件：V是图的顶点集，VR是图中弧的集合。

操作结果：按V和VR的定义构造图G。

DestroyGragh(&G)；

初始条件：图G存在。

操作结果：销毁图G。

GetVex(G，v)；

初始条件：图G存在，v是G中某个顶点。

操作结果：返回v的值。

FirstAdjvex(G,v)；

初始条件：图G存在，v是G中某个顶点。

操作结果：返回v的第一个邻接顶点，则返回“空”。

NextAdjVex(G,v,w)；

初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。

操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的

最后一个邻接点，则返回“空”。

DFSTraverse(G,Visit())；

初始条件：图G存在，Visit是顶点的应用函数。

操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用

函数Visit一次且仅一次。一旦visit()失败，则操作失败。 BFSTraverse(G，Visit())；

初始条件：图G存在，Visit是顶点的应用函数。

操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用

函数Visit一次且仅一次。一旦visit()失败，则操作失败。

}ADT Graph

2.MFSet的抽象数据类型定义

ADT MFSet{

数据对象：若设S是MFSet型的集合，则它由n（n）0）个子集Si

（I=1，2，```,n）构成，每个子集的成员都是子界 [-maxnumber..maxnumber]内的整数；

数据关系：S1∪S2∪…∪S3=S Si S(i=1,2,…,n)

基本操作：

Initial(&S,n,x1,x2,…,xn)；

操作结果：初始化操作。构造一个有n个子集(每个子集只含有单个

成员xi)构成的集合S。

Find(S,x)；

初始条件：S是已存在的集合，x是S中某个子集的成员。

操作结果：查找函数。确定S中x所属子集Si。

Merge(&S，i，j)；

初始条件：Si和Sj中的两个互不相交的非空集合。

操作结果：归并操作。将Si和Sj中的一个并入另一个中。

}ADTMFSet；

3. 本程序包含的模块：

(1)主程序模块：

void main()

{ 初始化；

界面提示输入图的相关信息；

do{

接受命令；

处理命令；

}while("命令"!="退出")

}

(2)图单元模块——实现图的抽象数据类型

(3)MFSet函数单元模块——实现MFSet的抽象数据类型

(4)顶点单元模块——定义图的顶点结构及顶点之间的权值

4. 各模块之间的调用关系如下：

三、详细设计

1. 图的存储表示

struct {

int MinPower[30][30];

int flag;//划分子集的方法，给符合最小生成树要求的权值做一个标记}StrCity[30];

typedef struct{

int ordinate;//纵坐标

int abscissa;//横坐标

}Coordinate;

int power[30][30];//各个顶点之间的权值

int CityNum;//顶点（城市）个数

char City[30];//城市（顶点）名称

int minPower = 100;//初始化最小路径为0

int V isited[30][30];//看是否为已经访问过的两个城市是为1，否为0

2.克鲁斯卡尔算法的伪代码

int FindMin(){

int minPower = 100;

for(int i = 0 ;i

for(int j = i+1;j

if(minPower >=power[i][j] && V isited[i][j] !=1 && i!=j){

minPower = power[i][j];

a = i;

b = j;

}

V isited[a][b] = 1;

return minPower;

}

void evaluate(){ //把符合要求的权值放到数组MinPower[][]当中

//int flag[30][30];//划分子集的方法，给符合最小生成树要求的权值做一个标记

for(int i = 0;i

int MinP = FindMin();

if(StrCity[a].flag==0 && StrCity[b].flag == 0){ //两个顶点都没有访问过StrCity[i].MinPower[a][b]=MinP;//给符合最小生成树条件的顶点做一个标记

StrCity[a].flag =i+1;

StrCity[b].flag =StrCity[a].flag;

}

else if(StrCity[a].flag==0 && StrCity[b].flag != 0)//a,b中其中a没有被访问过

{

StrCity[i].MinPower[a][b]=MinP;

//把a放到b所在的组

StrCity[a].flag = StrCity[b].flag;

}

else if(StrCity[a].flag!=0 && StrCity[b].flag == 0)//a,b中其中b没有被访问过

{

StrCity[i].MinPower[a][b]=MinP;

//把b放到a所在的组

StrCity[b].flag = StrCity[a].flag;

}

else//a,b两个顶点都被访问过了

{

if(StrCity[a].flag != StrCity[b].flag)//a,b都被发访问过,但是他们的标记不一样

{

StrCity[i].MinPower[a][b]=MinP;

for(int si = 0;si

{

if(StrCity[si].flag == StrCity[a].flag)

StrCity[si].flag = StrCity[b].flag;

}

else//a,b两点都被访问过而且是属于同一组

{

i--;

}

3. 文本输出最小生成树

void Print(){

cout<<"最小生成树如下："<

for(int si=0;si

for(int i=0;i

for(int j=0;j

if(StrCity[si].MinPower[i][j]>0){

cout<

间的权值为"<

}

4. 图形输出构造的图（即所建造的城市）伪代码

void CreatGraph(){//构造图形形式的无向图

int m,n;

int i,j;

for(i=0;i

if(m<=500 && n<=400){

cout<<"为第"<

cin>>m>>n;

cout<

ZB[i].abscissa=m;

ZB[i].ordinate=n;

}

for(i=0;i

cout<<"第"<

}

initgraph(500, 400); //界面大小横坐标最大500，纵坐标最大400

for(i=0;i

circle(ZB[i].abscissa,ZB[i].ordinate,4);

outtextxy(ZB[i].abscissa,ZB[i].ordinate,City[i]);

}

for(i=0;i

for(j=0;j

if(power[i][j])

line(ZB[i].abscissa,ZB[i].ordinate,ZB[j].abscissa,ZB[j].ordinate);

}

getch();

closegraph(); }

5. 图形输出最小生成树的伪代码

void minTree(){

int m,n;

int i,j;

for(i=0;i

if(m<=500 && n<=400){

cout<<"为第"<

cin>>m>>n;

cout<

ZB[i].abscissa=m;

ZB[i].ordinate=n;

}

for(i=0;i

cout<<"第"<

}

initgraph(500, 400); //界面大小横坐标最大500，纵坐标最大400

for(i=0;i

circle(ZB[i].abscissa,ZB[i].ordinate,4);

outtextxy(ZB[i].abscissa,ZB[i].ordinate,City[i]);

}

for(int si=0;si

{

for(i=0;i

{

for(j=0;j

{

if(StrCity[si].MinPower[i][j]>0)

{

line(ZB[i].abscissa,ZB[i].ordinate,ZB[j].abscissa,ZB[j].ordinate);

}

getch();

closegraph(); //关闭图形模式

}

6. 主函数的伪代码

void main(){

cout<<"输入你要建设通信网络城市的个数(不大于30)：";

cin>>CityNum;

if(CityNum>30){

cout<<"你输入的数据不符合规则"<

exit(0);

}

cout<<"随机构造的城市："<

InitCity(CityNum);//初始化城市的权值

CityMC(CityNum);//初始化城市的名称

evaluate();

int ch;

do{

cout<

cout<<"1、以文本形式输出最小生成树\n";

cout<<"2、以图形方式输出最小生成树\n";

cout<<"3、以图形方式输出图\n";

cout<<"0、退出程序\n";

cout<<"请输入命令0-3\n";

cin>>ch;

switch(ch){

case 1:

Print();break;

case 2:

minTree();break;

case 3:

CreatGraph();break;

case 0:

exit(0);break;

}

}while(ch>=0&&ch<=3);

}

7. 其他函数

void InitCity(int CSGS) //产生100以内的随机数初始化权值

{

::srand((unsigned)time(NULL));

char ch = 'a';

for(int k = 0 ;k

{

cout<

}

cout<

ch = 'a';

for(int i = 0; i

{

cout<

for(int j = 0;j

{

if(i == j)

{

power[i][j] = 0;

cout<

} //自己到自己的权值为0

else

{

while(power[i][j] ==0)

{

power[i][j] = ::rand()%100;//随机产生一个两位数

power[j][i] = power[i][j];

}

int num;

if(i

{

num = power[i][j];

}

else

{

num = power[j][i];

}

cout<

}

cout<

}

void CityMC(int CSGS)//初始化城市的名称

{

char ch = 'a';

for(int k = 0 ;k

{

City[k] = ch;

}

8. 函数调用关系图

四、调试分析

1.在写程序时遇到很多有关专业名词的C语言编译，没有完全套用书上的固

有解释，而是按照自己有限的英语词汇的理解去编译的。

2.Kruskal算法需对e条边按权值进行排序，其时间复杂度为O(e*log e) 在边比较多的

时候，e接近于n方，可知Kruskal比较适合于边比较少稀疏图的计算。

3.在dos窗口在图形输出的需要用到EasyX,学习了一点，对这个有了些了解。

4.在边比较多的时候，e接近于n方，可知Kruskal比较适合于边比较少稀疏图的计算。

五、用户手册

1.打开可执行程序，即vC环境下，,参照用户选择界面提示即可使用本程序

2.进入演示程序后即显示用户界面

3.接受其他命令后即执行相应运算和显示相应结果。

六、测试结果

七、附录

源程序：

#include

using namespace std;

int power[30][30];//各个顶点之间的权值

int CityNum;//顶点（城市）个数

char City[30];//城市（顶点）名称

int minPower = 100;//初始化最小路径为0

int V isited[30][30];//看是否为已经访问过的两个城市是为1，否为0 struct {

int MinPower[30][30];

int flag;//划分子集的方法，给符合最小生成树要求的权值做一个标记}StrCity[30];

typedef struct{

int ordinate;//纵坐标

int abscissa;//横坐标

char City;//城市名字

}Coordinate;

Coordinate ZB[30];

int a,b;//保存在FindMin()函数中找到符合最小生成树要求的两个顶点void InitCity(int);

void CreatGraph(){//构造图形形式的无向图

int m,n;

int i,j;

for(i=0;i

if(m<=500 && n<=400){

cout<<"为第"<

cin>>m>>n;

cout<

ZB[i].abscissa=m;

ZB[i].ordinate=n;

}

for(i=0;i

cout<<"第"<

}

initgraph(500, 400); //界面大小横坐标最大500，纵坐标最大400

for(i=0;i

circle(ZB[i].abscissa,ZB[i].ordinate,4);

outtextxy(ZB[i].abscissa,ZB[i].ordinate,City[i]);

}

for(i=0;i

for(j=0;j

if(power[i][j])

line(ZB[i].abscissa,ZB[i].ordinate,ZB[j].abscissa,ZB[j].ordinate);

}

getch();

closegraph(); //关闭图形模式

}

void minTree(){

int m,n;

int i,j;

for(i=0;i

if(m<=500 && n<=400){

cout<<"为第"<

cin>>m>>n;

cout<

ZB[i].abscissa=m;

ZB[i].ordinate=n;

}

for(i=0;i

cout<<"第"<

}

initgraph(500, 400); //界面大小横坐标最大500，纵坐标最大400

for(i=0;i

circle(ZB[i].abscissa,ZB[i].ordinate,4);

outtextxy(ZB[i].abscissa,ZB[i].ordinate,City[i]);

}

for(int si=0;si

for(i=0;i

for(j=0;j

if(StrCity[si].MinPower[i][j]>0){

line(ZB[i].abscissa,ZB[i].ordinate,ZB[j].abscissa,ZB[j].ordinate);

}//if

}//for

}

getch();

closegraph(); //关闭图形模式

}

void Print(){

cout<<"最小生成树如下："<

for(int si=0;si

for(int i=0;i

for(int j=0;j

if(StrCity[si].MinPower[i][j]>0){

cout<

之间的权值为"<

}//if

}//for

}//Print

void CityMC(int CSGS){//初始化城市名称

char ch = 'a';

for(int k = 0 ;k

City[k] = ch;

}//for

}

int FindMin() { //找到权值最小的的两个城市，并返回权值大小

int minPower = 100;

for(int i = 0 ;i

for(int j = i+1;j

if(minPower >=power[i][j] && V isited[i][j] !=1 && i!=j){

minPower = power[i][j];

a = i;

b = j;

}//if

}//for

}

Visited[a][b] = 1;

return minPower;

}

void evaluate(){ //把符合要求的权值放到数组MinPower[][ ]当中

int flag[30][30];//划分子集的方法，给符合最小生成树要求的权值做一个标记

for(int i = 0;i

int MinP = FindMin();

if(StrCity[a].flag==0 && StrCity[b].flag == 0){ //两个顶点都没有访问过

StrCity[i].MinPower[a][b]=MinP;//给符合最小生成树条件的顶点做一个标记

StrCity[a].flag =i+1;

StrCity[b].flag =StrCity[a].flag;

}

else if(StrCity[a].flag==0 && StrCity[b].flag != 0){ //a,b中其中a没有被访问过StrCity[i].MinPower[a][b]=MinP;//把a放到b所在的组

StrCity[a].flag = StrCity[b].flag;

}

else if(StrCity[a].flag!=0 && StrCity[b].flag == 0){ //a,b中其中b没有被访问过StrCity[i].MinPower[a][b]=MinP;

//把b放到a所在的组

StrCity[b].flag = StrCity[a].flag;

}

else{ //a,b两个顶点都被访问过了

if(StrCity[a].flag != StrCity[b].flag){ //a,b都被发访问过,但是他们的标记不一样StrCity[i].MinPower[a][b]=MinP;

for(int si = 0;si

if(StrCity[si].flag == StrCity[a].flag)

StrCity[si].flag = StrCity[b].flag;

}

else{ //a,b两点都被访问过而且是属于同一组

i--;

}

void InitCity(int CSGS){ //产生100以内的随机数初始化权值

::srand((unsigned)time(NULL));

char ch = 'a';

for(int k = 0 ;k

cout<

}

cout<

ch = 'a';

for(int i = 0; i

cout<

for(int j = 0;j

if(i == j){

power[i][j] = 0;

cout<

} //自己到自己的权值为0

else{

while(power[i][j] ==0){

power[i][j] = ::rand()%100;//随机产生一个两位数

power[j][i] = power[i][j];

}

int num;

if(i

num = power[i][j];

}

else{

num = power[j][i];

}

cout<

}

cout<

}

void main(){

cout<<"输入你要建设通信网络城市的个数(不大于30)：";

cin>>CityNum;

if(CityNum>30){

cout<<"你输入的数据不符合规则"<

exit(0);

}

数据结构课程设计图的遍历和生成树求解

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 6014389 题目: 图的遍历和生成树求解实现年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日完成时间: 2012 年 12 月 26 日课程设计成绩：指导教师签名：年月日

目录摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26)

摘要《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：计算机；图；算法。

创建一个二叉树并输出三种遍历结果

实验报告课程名称数据结构实验项目实验三--创建一个二叉树并输出三种遍历结果系别■计算机学院 _________________ 专业_______________ 班级/学号_____________ 学生姓名___________ 实验日期— 成绩______________________________ 指导教师

实验题目：实验三创建一个二叉树并输出三种遍历结果实验目的 1）掌握二叉树存储结构； 2）掌握并实现二叉树遍历的递归算法和非递归算法; 3）理解树及森林对二叉树的转换; 4）理解二叉树的应用一哈夫曼编码及WPL计算。实验内容 1）以广义表或遍历序列形式创建一个二叉树，存储结构自选； 2）输出先序、中序、后序遍历序列； 3）二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。题目可替换上述前两项实验内容）设计与编码 1）程序结构基本设计框架（提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、框图等来表示） 2）本实验用到的理论知识遍历二叉树，递归和非递归的方法（应用型

(提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法) 3) 具体算法设计 1) 首先，定义二叉树的存储结构为二叉链表存储，每个元素的数据类型Elemtype,定义一棵二叉树，只需定义其根指针。 2) 然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一个特殊的字符(本算法为“ #”),表示左孩子或者右孩子为空。 3) 下一步,创建利用递归方法先序遍历二叉树的函数,函数为 PreOrderTreeQ,创建非递归方法中序遍历二叉树的函数，函数为 InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的函数，函数为LaOrderTree()。 (提示：该部分主要是利用C、C++ 等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述) 4) 编码 #include #include #include typedef char DataType; #define MaxSize 100 typedef struct Node { DataType data; struct Node *lchild; struct Node *rchild; } *BiTree,BitNode;

最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)

算法设计与分析课程设计报告学院计算机科学与技术专业计算机科学与技术年级2011 姓名XXX 学号 2013年5 月19 日

题目：最小生成树问题的算法实现及复杂度分析摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。

图的遍历和生成树求解实现_课程设计报告

中北大学数据结构课程设计说明书 2011年12月19日

1设计目的：《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 2设计内容和要求设计内容： (1)采用合适的存储结构来创建图，并实现图的遍历；（2）计算图的最小生成树，求联通分量设计要求：（1）先任意创建一个图；（2) 图的DFS,BFS的递归和非递归算法的实现（3) 最小生成树（两个算法）的实现，求连通分量的实现（4) 要求用邻接矩阵、邻接表、十字链表多种结构存储实现 3．本设计所采用的数据结构：本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。 4.1 详细设计思想这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和

二叉树的基本参数计算

/*二叉树的基本参数计算*/ #include #include #define MaxSize 20 typedef int ElemType; #define OK 1 typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; //建立二叉树（按先序序列生成二叉树,#表示空节点） void CreateBiTree(BiTree *T) { char ch; scanf("%c",&ch); getchar();/*回车键（每次输入一个字符后，需敲回车键）*/ if(ch=='#') { printf("不产生子树。\n"); *T=NULL; } else { if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))) { printf("分配空间失败"); return; }//生成一个新节点 (*T)->data = ch; printf("产生左右子树。\n"); CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } } //交换左右子树产生新的树t返回到主函数 BiTNode *swap(BiTree T) { BiTree t,t1,t2; if(T==NULL) t=NULL; else {

t=(BiTNode*)malloc(sizeof(BiTNode)); t->data=T->data; t1=swap(T->lchild); //交换左右子树 t2=swap(T->rchild); t->lchild=t2; t->rchild=t1; } return(t); } //求树的叶子结点数 int leafs(BiTree T) { int num1,num2; if(T==NULL) return 0; else if(T->lchild==NULL&&T->rchild==NULL) return 1; else { num1=leafs(T->lchild); num2=leafs(T->rchild); return (num1+num2); } } //求二叉树的深度 int Depth(BiTNode *T) { int dep1,dep2; if(T==NULL) return(0); else { dep1=Depth(T->lchild); dep2=Depth(T->rchild); if(dep1>dep2) return(dep1+1); else return(dep2+1); } } //按广义表形式输出二叉树 void Disptree(BiTNode *T)

二叉树的遍历源代码(C语言)

二叉树就是每个结点最多有两个子树的树形存储结构，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被且只被访问一次。程序的流程图如下：程序代码如下： #include #include #include #include typedef char ElemType; struct BTreeNode{ ElemType data; BTreeNode*left; BTreeNode*right; }; void InitBTree(BTreeNode*& BT){ //初始化二叉树 BT=NULL; } void CreateBTree(BTreeNode*& BT,char*a){ //根据广义表表示的二叉树建立对应

的存储结构 const int MaxSize=10; BTreeNode*s[MaxSize]; int top=-1; BT=NULL; BTreeNode*p; int k; int i=0; while(a[i]){ switch(a[i]){ case ' ': break; case '(': if(top==MaxSize-1){ printf("栈的空间太小，请增加MaxSize的值\n"); exit(1); } top++; s[top]=p; k=1; break; case ')': if(top==-1){ printf("二叉树广义表字符串错！\n"); exit(1); } top--; break; case ',': k=2; break; default: p=new BTreeNode; p->data=a[i]; p->left=p->right=NULL; if(BT==NULL) BT=p; else{ if(k==1) s[top]->left=p; else s[top]->right=p; } }

数据结构课程设计-图的遍历和生成树的求解实现说明书

******************* 实践教学 ******************* 兰州理工大学计算机与通信学院 2012年春季学期算法与数据结构课程设计题目：图的遍历和生成树的求解实现专业班级：计算机科学与技术姓名：*** 学号：1234567 指导教师：**** 成绩：

目录摘要 (3) 前言 (4) 正文 (5) 1.问题描述： (5) 2.采用类C语言定义相关的数据类型 (5) 3．各模块流程图及伪码算法 (6) 4．函数的调用关系图 (8) 5．调试分析 (9) 1.调试中遇到的问题及对问题的解决方法 (9) 2.算法的时间复杂度和空间复杂度 (9) 6.测试结果 (10) 参考文献 (14)

图是一种复杂的非线性数据结构，一个图G（Grah）由两个集合V和E 构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历基本思路是假设从图中某顶点U出发，在访问了顶点U之后依次访问U的各个未访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先的基本思路是从某个顶点出发，访问此顶点，然后依次从V的未被访问的领接点出发深度优先检索土。直至图中所有顶点都被访问到。PRIM算法—KRUSKAL算法；可以对图形进行最小生成树的求解。主要问题是：（1）当给出一个表达式时，如何创建图所表达的树，即相应的逻辑结构和存储结构？（2）表达式建立好以后，如何求出其遍历？深度优先和广度优先遍历。（3）计算它的最小生成树？主要是prim算法和kruscal算法两种形式。

二叉树

问题A : 复原二叉树时间限制：1 秒内存限制：32 兆特殊判题：否提交：2 解决：2 题目描述小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。输入格式输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。输出对于每组输入，输出对应的二叉树的后续遍历结果。样例输入 DBACEGF ABCDEFG BCAD CBAD 样例输出 ACBFGED CDAB

问题B : 二叉树时间限制：1 秒内存限制：32 兆特殊判题：否提交：2 解决：2 题目描述如上所示，由正整数1，2，3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树中共有4个结点。输入格式

输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。输出对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。样例输入 3 7 142 6574 2 754 0 0 样例输出 3 63 498 问题C : 二叉树遍历时间限制：1 秒内存限制：32 兆特殊判题：否提交：2 解决：2 题目描述二叉树的前序、中序、后序遍历的定义：

最小生成树算法分析

最小生成树算法分析一、生成树的概念若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。二、求图的最小生成树算法严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。

例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100） e（边数）以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。 [输出] n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 [举例] 下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。 [问题分析] 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。 1、用Prim算法求最小生成树的思想如下： ①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； ②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S； ③重复下列操作，直到选取了n-1条边：选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)；将顶点Y加入集合S，边（X，Y）加入集合TE； ④得到最小生成树T =（S，TE）

数据结构课程设计之图的遍历和生成树求解

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 2011.6.20 指导教师:

2010—2011年度第 2 学期一、需求分析 1.问题描述：图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。 2.基本功能 1) 先任意创建一个图； 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树（两个算法）的实现，求连通分量的实现 4) 要求用邻接矩阵、邻接表等多种结构存储实现 3.输入输出

输入数据类型为整型和字符型，输出为整型和字符二、概要设计 1.设计思路： a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。 b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。 c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。 d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。 e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计： ADT Queue{ 数据对象：D={a i | a i ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| a i-1 ,a i ∈D,i=1,2,3,……，n} 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 QueueEmpty(Q) 初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。 EnQueue(&Q,e) 初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q,e) 初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue