构成可以使n个城市连接的最小生成树
构成可以使n个城市连接的最小生成树
题目: 构成可以使n个城市连接的最小生成树
姓名: 熊彬
100912042 学号:
专业: 电子信息工程班级: 电信1021 指导教师: 梁英
讲师职称:
计算机与电子工程学院
2012年1月
课程设计(实习)评审表
学号 100912042 姓名熊彬学院电子信息工程
专业班级电信1021 题目构成可以是n个城市连接的最小生成树
评
审
意
见
评审成绩
指导教师签名职称评审时间年月日
1
课程设计(实习)作品验收表题目构成可以使n个城市连接的最小生成树姓名熊彬参与人员班级电信1021
学号 100912042
设计任务与要求:
作品完成情况:
验收情况:
验收教师签名:___________
年月日
2
目录
一(需求分
析 ..................................................................... . (4)
1.1 设计的任务...................................................................... . (4)
1.2 程序所能达到的功能...................................................................... (4)
1.3 程序执行命令...................................................................... ........................... 4 二(概要设
计 ..................................................................... . (5)
2.1 抽象数据类型结构体数组的定义: (5)
2.2 程序模块...................................................................... .. (6)
2.3流程图...................................................................... ........................................ 6 三(详细设
计 ..................................................................... . (7)
3.1 数据类型定义...................................................................... (7)
3.2 程序主要模块...................................................................... ........................... 7 四(调试分析和测试结
果 (9)
4.1 调试分析...................................................................... .. (9)
4.2测试结果...................................................................... .................................. 10 五(总
结 ..................................................................... ................... 11 六(参考文
献 ..................................................................... ........... 11 七(致
谢 ..................................................................... ................... 12 八(附
录 ..................................................................... . (12)
3
构造可以使N个城市连接的最小生成树一(需求分析
1.1 设计的任务
给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 1.2 程序所能达到的功能
1.2.1 城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。
1.2.2 显示出城市间道路网的邻接矩阵。
1.2.3 最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。
1.3 程序执行命令
输入城市数、道路数?输入城市名?输入道路信息?执行Kruskal 算法?执行Prim 算法?输出最小生成树
4
二(概要设计
2.1 抽象数据类型结构体数组的定义:
#ifndef ADJACENCYMATRIXED //防止该头文件被重复引用 #define ADJACENCYMATRIXED //而引起的数据重复定义
#define INFINITY 32767 //最大值?
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef int VRType; //权值，即边的值 typedef char InfoType; //附加信息的类型，后面使用时会定义成一个指
针
typedef char VertexType[MAX_VERTEX_NUM]; //顶点类型
typedef enum {DG=1, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，
无向网}
typedef struct ArcCell {
VRType adj; //VRType 是顶点关系类型。对无权图，用 1 或 0 表示相
邻否;对带权图，则为权值类型。
InfoType* info; //该弧关系信息的指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum, arcnum; //图的当前顶点数和弧数
GraphKind kind; //图的种类标志
}MGraph;
typedef struct //普里姆算法辅助数组的定义 {
VertexType adjvex;
VRType lowcost;
}closedge[MAX_VERTEX_NUM];
#endif //结束if
5
2.2 程序模块
MGraph G; //网 G，唯一的全局变量 int main(int argc, char * argv[]); //主函数
Status LocateVex(MGraph G, VertexType v); //判断城市 v 在网 G 中的位置 Status CreateUDN(MGraph &G); //创建网 G 的邻接矩阵 void
DisplayNet(MGraph G); //以邻接矩阵的形式显示网 G void
MiniSpanTree_KRUSKAL(MGraph G); //最小生成树的 Kruskal 算法 void MiniSpanTree_PRIM(MGraph G, VertexType u); //最小生成树的 Prim 算法Status Minimum(closedge closeEdge, int n); //Prim 算法中求下一个城市的函数 void DeleteInfo(MGraph &G); //释放堆内存上动态申请的空间 2.3流程图创建用邻接矩阵表示的城市道路网
输入城市数G.vexnum、
道路数G.arcnum
输入城市名G.vexs[i]
输入表示道路的两个城市及道路值
G.arcs[i][j].adj
返回 OK
2.3.1创建邻接矩阵的流程图(N-S图)
6
Prim算法
化辅助数组closeEdge
for (i=1; i 求下一个城市k = Minimum(closeEdge, G.vexnum) 输出找到的道路 标记城市，避免重复 输出总耗费 图2.3.2Prim算法流程图(N-S图) 三(详细设计 3.1 数据类型定义 为了用邻接矩阵表示图 G ，先是定义二维数组的每一个元素含道路值然后在图的定义中定义一个此二维数组的结构成员。并且在图中还定义一个用来存放城市的一维数组及int 型的城市数级道路数。 用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。这样就建立起了一个城市到城市之间的道路网。 3.2 程序主要模块 说明:该程序共含5个模块，本人负责其中2个模块构造: 3.2.1 初始化图G ***************LocateVex(MGraph G, VertexType v)**************** 7 Status LocateVex(MGraph G, VertexType v); { while (strcmp(G.vexs[i], v)) {i++;} 返回 i; } **************** CreateUDN************************* { 输入城市数、道路数; for (i=0; i<城市数; ++i) 输入城市名; for (i=0; i<城市数; ++i) for(j=0; j<城市数; ++j) 初始化邻接矩阵:道路值= INFINITY; for (i=0; i<城市数; ++i) for(j=0; j<城市数; ++j) 输入两个城市表示道路，输入道路值; } 3.2.2PRIM算法 ************************** MiniSpanTree_PRIM********* void MiniSpanTree_PRIM(MGraph G, VertexType u) { 定义辅助数组:closedge closeEdge; 初始化:strcpy(closeEdge[j].adjvex, u); closeEdge[j].lowcost = G.arcs[k][j].adj; for (i=1; i { 在其余G.vexnum-1个城市中找到离辅助数组中标记的道路最小 8 值; 显示找到的道路; 标记新找到的城市; } } ********************** Minimum***************** Status Minimum(closedge closeEdge, int n) { 在辅助数组中找到道路值最小的道路的两点城市: if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost)) 返回该城市在 G 中的位置 } 四(调试分析和测试结果 4.1 调试分析 4.1.1邻接矩阵初始化 本函数的主要功能是对无向网进行邻接矩阵的初始化。构造这种具有n个顶点和e条边的无向网时，关键需要考虑其时间复杂度O(n^+e*n),其中对邻接矩阵 G.arcs的初始化花费了O(n^)的时间。 4.1.2 Prim 算法 Prim 算法的思路是逐步将城市纳入生成树中，这里面的关键步骤是要找到下 一个城市。于是通过讨教别人，写了Status Minimum(closedge closeEdge, int n) 函数，这样就可以在辅助数组中找到道路值最小的道路的两点城市了。 9 4.2测试结果 图4.2.1邻接矩阵初始化运行显示界面 图4.2.2Prim算法运行显示界面 10 五(总结 通过本周的课程设计，我们小组终于圆满完成了课程设计的任务，我也有不少收获。既巩固和加深了对数据结构的理解，认识到《数据结构》是计算机专业一门重要的专业技术基础课程，还提高了我综合运用本课程所学知识的能力。而且，并不是单纯的看看教材就能解决我们的实际问题，所以还要去查找各种我们所需要的资料，所以这次课程设计也培养了我选用参考书，查阅手册及文献资料的能力。要完成一个课程设计的课题并不是一次就能编译成功的，中间会出现很多的大问题小问题，改错是个很繁琐的问题。通过这次课程设计培养了我独立思考，深入研究，分析问题，解决问题的能力。 在以后的学习过程中我将要注意以下几点:1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 六(参考文献 [1].严蔚敏，吴伟民. 数据结构(C语言版). 清华大学出版社，2007 [2].谭浩强，张基温. C语言程序设计教程(第三版)北京:高等教育出版社，2006 [3].陈维新，林小茶. C++面向对象程序设计教程. 北京:清华大学出版社，2004 [4].苏仕华等.数据结构课程设计. 北京: 机械工业出版社，2005 11 七(致谢 感谢梁英老师对我们《数据结构》课程及其实验的悉心指导，正是因为老师在实验课上的指导，让我能够把书本上的知识化成自己的知识，并运用在编程的过程中。 感谢同学在我的设计过程中提出的宝贵意见，如果没有他们的帮助，我在设计过程中出现的一些错误可能无法迅速查出解决，你们的帮助为我节省了宝贵的时间。 衷心感谢～ 八(附录 //main #include #include #include #include #include "TypeDefine.h" #include "AdjacencyMatrix.h" #include "InitializeFunction.h" #include "MiniSpanTree_KRUSKAL.h" #include "MiniSpanTree_PRIM.h" #include "DisplayNet.h" #include "DeleteInfo.h" MGraph G; //全局变量G 12 int main(int argc, char * argv[]);//主函数 Status LocateVex(MGraph G, VertexType v);//判断城市 v 在网 G 中的位置 Status CreateUDN(MGraph &G);//创建网 G 的邻接矩阵 void DisplayNet(MGraph G);//以邻接矩阵的形式显示网 G void MiniSpanTree_KRUSKAL(MGraph G);//最小生成树的 Kruskal 算法 void MiniSpanTree_PRIM(MGraph G, VertexType u);//最小生成树的 Prim 算法Status Minimum(closedge closeEdge, int n);//Prim 算法中求下一个城市的函数 void DeleteInfo(MGraph &G);//释放堆内存上动态申请的空间int main(int argc, char * argv[]) { CreateGraph(G); DisplayNet(G); MiniSpanTree_KRUSKAL(G); MiniSpanTree_PRIM(G, G.vexs[0]); DeleteInfo(G); cout< system("pause"); return 0; } //intializeFunction.h Status CreateDG(MGraph &G){return 0;}; Status CreateDN(MGraph &G){return 0;}; Status CreateUDG(MGraph &G){return 0;}; Status CreateUDN(MGraph &G); Status LocateVex(MGraph G, VertexType v) { 13 //判断输入的顶点v在G中的位置。 //根据顶点的类型，可重载此函数。目前为char int i=0; while (strcmp(G.vexs[i], v)) {i++;} return i; } Status CreateGraph(MGraph &G) { //采用数组(邻接矩阵)表示法，构造图G. G.kind = UDN; //默认构造无向网 /* printf("+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf("|1:有向图 2:无向图 3:有向网 4:无向网\n"); printf("|请选择:[ ]\b\b"); scanf("%d", &G.kind); printf("+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");*/ switch (G.kind) { case DG: return CreateDG(G); //构造有向图G case DN: return CreateDN(G); //构造有向网G case UDG: return CreateUDG(G); //构造无向图G case UDN: return CreateUDN(G); //构造无向网G default : return ERROR; } }//CreateGraph Status CreateUDN(MGraph &G) { 14 //采用数组(邻接矩阵)表示法，构造图G. int i, j, k; VertexType v1, v2; VRType w; printf(" 构造可以使N个城市连接的最小生成树\n"); printf("请输入城市数、道路数(至少6个城市，10条道路):"); cin>>G.vexnum>>G.arcnum; for (i=0; i { printf("请输入第 %d 个城市名(共 %d 个):", i+1, G.vexnum); cin>>G.vexs[i]; } for (i=0; i { for (j=0; j { G.arcs[i][j].adj = INFINITY; // G.arcs[i][j].info = NULL; } } printf("请输入一条道路连接的两个城市名及权值:\n"); for (k=0; k { printf("共%3d条道路，第%3d条道路:", G.arcnum,k+1); cin>>v1>>v2>>w; //输入一条边依附的顶点及权值 15 i = LocateVex(G, v1); //确定v1、v2在G中的位置 j = LocateVex(G, v2); G.arcs[i][j].adj = w; //弧 G.arcs[j][i] = G.arcs[i][j]; //置 } return OK; }//CreateUDN //MiniSpan Tree PRIM.h Status Minimum(closedge closeEdge, int n) { int i, flag, minTemp = INFINITY; for (i=0; i { if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost)) { minTemp = closeEdge[i].lowcost; flag = i; } } return flag; } void MiniSpanTree_PRIM(MGraph G, VertexType u) { //用普里姆算法从第 u 个顶点出发构造网 G 的最小生成树 T，输出 T 的各条边。 16 //记录从顶点集 U 到 V-U 的代价最小的边的辅助数组定义见"AdjacencyMatrix.h" int i, j, k, totalCost=0; closedge closeEdge; k = LocateVex(G, u); for (j=0; j { if (j != k) { strcpy(closeEdge[j].adjvex, u); closeEdge[j].lowcost = G.arcs[k][j].adj; } } cout<<"\n\n+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\\\n"; cout<<"|用Prim算法求最小生成树的各条边依次为:\n-----"; closeEdge[k].lowcost = 0;//初始，U={u}; for (i=1; i { k = Minimum(closeEdge, G.vexnum); //求出 T 的下一个结点:第 k 顶点//此时 closeEdge[k].lowcost = MIN{closeEdge[vi].lowcost | closeEdge[vi].lowcost > 0, vi?V-U} cout<<'<'< totalCost += closeEdge[k].lowcost; closeEdge[k].lowcost = 0; //第 k 顶点并入 U 集 for (j=0; j { 17 if (G.arcs[k][j].adj < closeEdge[j].lowcost) //新顶点并入 U 后重新选择最小边 { strcpy(closeEdge[j].adjvex, G.vexs[k]); closeEdge[j].lowcost = G.arcs[k][j].adj; } } } cout<<"\n|总代价:"< cout<<"+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^/\n"; }//MiniSpanTree 18 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 二叉树遍历方法 1.中序遍历的投影法 如果给定一棵二叉树的图形形态，是否能根据此图快速地得出其中序遍历的序列？回答是肯定的。具体做法是：首先按照二叉树的标准绘制二叉树形态，即将所有左子树都严格绘于根结点的左边；将所有右子树都严格绘于根结点的右边。然后假设现在有一个光源从该二叉树的顶部投射下来，那么所有结点在地平线上一定会有相应的投影，从左至右顺序读出投影结点的数据即为该二叉树的中序遍历序列。如图11.10所示。 图示的中序遍历序列： D J G B H E A F I C 2.先序遍历的填空法 如果给定一棵二叉树的图形形态，可在图形基础上，采用填空法迅速写出该二叉树的先序遍历序列。具体做法是：我们知道，对于每个结点都由三个要素组成，即根结点，左子树、右子树；又已知先序遍历顺序是先访问根结点、然后访问左子树、访问右子树。那么，我们按层分别展开，逐层填空即可得到该二叉树的先序遍历序列。 图11.10 中序遍历投影法示意图 如图11.10 中的二叉树采用填空法的步骤如下： (1)根结点左子树右子树 A( )( ) (2)A （根结点（左子树）（右子树））（根结点（左子树）（右子树）） A B C (3)A(B(根结点（左）（右）)(根结点（左）（右）))（C(……)(……)） A B D 无 G E H 无 C F 无 (4)A B D G J E H C F I 此即为该二叉树的先序遍历序列。 注：后序遍历的序列亦可以此方法类推，请读者自己尝试。 3.利用遍历序列构造二叉树 如果已知一棵二叉树的先序遍历序列和中序遍历序列，则可以用这两个遍历序列构造一棵唯一的二叉树形态。我们知道任意一棵二叉树的先序遍历序列和中序遍历序列是唯一的，那么首先从给定的先序遍历序列入手，该先序序列的第一个元素一定是该二叉树的根；再分析这个根结点在中序遍历序列中的位置，中序遍历序列中根结点的左边即为左子树的全部元素，而根结点的右边即为右子树的全部元素；然后据此再将先序遍历序列除根结点以外的其余部分分为左、右子树两部分，并在这两部分中分别找出左、右子树的根结点。依此类推，即可得到完整的二叉树。例11.1 已知一棵二叉树的先序遍历和中序遍历序列分别为： 先序： A B C I D E F H G 中序： C I B E D A H F G 请构造这棵二叉树。 按前述分析，这棵二叉树的构造过程如图11.11所示 图11.11 二叉树的构造过程 树、森林与二叉树的转换(flash演示) 如前所述，树（或森林）的存储结构及其操作算法的实现，由于其“度”的不确定性而导致其存储结构不是较为复杂就是浪费空间，因而，定义在其存储结构上的算法也相应地较难兼顾全面。如果我们设定一定的规则，用二叉树来表示树和森林的话，就可以方便地解决树、森林的存储结构及其相关算法问题。 1.树、森林转换为二叉树 我们知道，一棵树中每个结点的孩子是无序的，而二叉树中各结点的孩子必须有左右之分。在此，为避免概念混淆，首先约定树中每个结点的孩子按从左至右的顺序升序编号，即将树中同一层上的兄弟分出大小。那么将一棵树转换成二叉树的方法是： （1）在树中同层兄弟间加一连线； （2）对树中每个结点仅保留其与长兄（左边第一个孩子）的连线，擦去其与其它孩子的连线； （3）以树（或子树）的根作为轴心，将所有的水平连线顺时针旋转45度，即可得到与该树完全等价的一棵二叉树。 用Prim算法构造最小生成树 班级：2010级计算机1班学号：2010131116 姓名：杨才一、实验目的 了解最小生成树的概念，掌握生成最小生成树的方法。 二、实验内容 建立一个含任意结点的无向连通网，并用Prim算法构造其最小生成树 三、实验要点及说明 如果无向连通图是一个网，则其所有生成树中必有一棵树的边的权值总和最小，这棵生成树为最小生成树。 Prim算法：在图G=（V，E）（V为顶点集，E为边集）中任选一顶点v0,令集合U={v0}为初态，在一个顶点在U中，另一顶点在V-U 中的所有边中找权值最小的边（u,v）（U∈ u,v∈ V-U），并将v加入到U中，同时将边（u,v）加入集合T中（T的初态为空集），这样不断地扩大U，直至U=V，则集合T中的边为所求最小生成树的边 四、算法思想与算法描述 1、邻接矩阵的数据类型的定义如下： typedef struct { int no; /*顶点编号*/ string name; /*顶点其他信息*/ } VertexType; /*顶点类型*/ typedef struct/*图的定义*/ { int edges[MAXV][MAXV]; /*邻接矩阵*/ int vexnum,arcnum; /*顶点数,弧数*/ VertexType vexs[MAXV]; /*存放顶点信息*/ }MGraph; 2、临时数组的存放的数据类型 struct { int closest; // U集中的顶点序号 int lowcost; // 边的权值 } closedge[MAXV]; int const INF=32767; /*INF表示∞*/ 3、prime算法实现：（原理见实验说明） void prime(MGraph g,int v) { int lowcost[MAXV]; int min; int closest[MAXV]; int i,j,k; for(i=0;i 榆林学院12届课程设计 《最小生成树问题》 课程设计说明书 学生姓名：赵佳 学号： 1412210112 院系：信息工程学院 专业：计算机科学与技术 班级：计14本1 指导教师： 答辩时间：年月日 最小生成树问题 一、问题陈述 最小生成树问题 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方 法。存储结构采用多种。求解算法多种。 二、需求分析 1.在n个城市之间建设网络，只需保证连通即可。 2.求城市之间最经济的架设方法。 3.采用多种存储结构，求解算法也采用多种。 三、概要设计 1、功能模块图 2、功能描述 （1) CreateUDG() 创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。 （2) Switch() 功能选择：给用户提示信息，让用户选择相应功能。 （3) Adjacency_Matrix() 建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。 （4) Adjacency_List() 建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。 （5) MiniSpanTree_KRSL() kruskal算法：利用kruskal算法求出图的最小生成树，即：城市之间最经济的连接方案。 （6) MiniSpanTree_PRIM() PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。 四、详细设计 本次课程设计采用两种存储结构以及两种求解算法。 1、两种存储结构的存储定义如下： typedef struct Arcell { double adj; }Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM]; //节点数组 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前节点数和弧数 }MGraph; typedef struct Pnode //用于普利姆算法 { char adjvex; //节点 double lowcost; //权值 }Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的 河北科技大学 课程设计报告 学生姓名：白云学号：Z110702301 专业班级：计算机113班 课程名称：数据结构课程设计 学年学期： 2 01 3—2 014学年第2学期指导教师：郑广 2014年6月 课程设计成绩评定表 目录 一、需求分析说明 (1) 1.1最小生成树总体功能要求 (1) 1.2基本功能 (1) 1.3 模块分析 (1) 二、概要设计说明 (1) 2.1设计思路 (1) 2.2模块调用图 (2) 2.3数据结构设计 (2) 2.3.1.抽象数据类型 (2) 2.3.2方法描述 (2) 三、详细设计说明 (3) 3.1主函数模块 (3) 3.2邻接表输出子模块 (3) 3.3邻接矩阵输出子模块 (3) 3.4创建邻接矩阵子模块 (3) 3.5创建邻接表子模块 (3) 3.6 Prim子模块 (3) 3.7 Kruscal子模块 (4) 四、调试分析 (4) 4.1实际完成情况说明 (4) 4.2 出现的问题及解决方案 (4) 4.3程序中可以改进的地方 (4) 六、课程设计总结 (7) 七、测试数据 (7) 八、参考书目 (7) 一、需求分析说明 1.1最小生成树总体功能要求 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 1.2基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 1.3 模块分析 主模块：用于生成界面和调用各个子模块。 Kruscal模块：以kruscal算法实现最小生成树。 Prim模块：以prim算法实现最小生成树。 邻接表模块：用邻接表方式存储图。 邻接表输出模块：输出邻接表。 邻接矩阵模块：用邻接矩阵方式存储图。 邻接矩阵模块：输出邻接矩阵。 二、概要设计说明 2.1设计思路 问题的解决分别采用普利姆算法以及克鲁斯卡尔算法。 1) 普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，以此类推，如果达到最后一个则返回上一个顶点。 2) 克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，以此类推，最终要有一个判断是否生成环，不生成则得到克鲁斯卡尔的最小生成树。 软件综合课程设计 最小生成树问题 学生成绩管理 二〇一四年六月 最小生成树问题 一、问题陈述 最小生成树问题 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 二、需求分析 1.在n个城市之间建设网络，只需保证连通即可。 2.求城市之间最经济的架设方法。 3.采用多种存储结构，求解算法也采用多种。 三、概要设计 1、功能模块图 2、功能描述 （1) CreateUDG() 创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。 （2) Switch() 功能选择：给用户提示信息，让用户选择相应功能。 （3) Adjacency_Matrix() 建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。 （4) Adjacency_List() 建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。 （5) MiniSpanTree_KRSL() kruskal算法：利用kruskal算法求出图的最小生成树，即：城市之间最经济的连接方案。 （6) MiniSpanTree_PRIM() PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。 四、详细设计 本次课程设计采用两种存储结构以及两种求解算法。 1、两种存储结构的存储定义如下： typedef struct Arcell { double adj; }Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM]; //节点数组 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前节点数和弧数 }MGraph; typedef struct Pnode //用于普利姆算法 { char adjvex; //节点 double lowcost; //权值 }Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct Knode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点 { char ch1; //节点1 char ch2; //节点2 double value;//权值 }Knode,Dgevalue[MAX_VERTEX_NUM]; 2、求解算法采用Prim算法和Kruskal算法。 （1）普里姆算法(Prim)算法 普里姆算法(Prim)算法是一种构造性算法，生成最小生成树的步骤如下：初始化U={v}。以v到其他顶点的所有边为候选边。 重复一下步骤(n-1)次，使得其他(n-1)个顶点被加入到U中。 ○1从候选边中挑选权值最小的边加入TE，设该边在V—U中的顶点是vk，将顶点vk加入到U中; ○2考察当前V—U中的所有顶点vj ，修改候选边：若(vk,vj)的权值小于原来和vj关联的候选边，则用(vk,vj)取代后者作为候选边。 数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析 1.问题描述： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={ 初始条件：图G存在。 操作结果：销毁图G。 LocateVex( G, u ) 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返 回其它信息。 GetVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。 PutVex( &G, v, value ) 初始条件：图G存在，v是G中某个顶点。 操作结果：对v赋值value。 FirstAdjVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点， 则返回“空”。 NextAdjVex( G, v, w ) 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的 最后一个邻接点，则返回“空”。 InsertVex( &G, v ) 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中增添新顶点v。 DeleteVex( &G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。 InsertArc( &G, v, w ) 课题二叉树的遍历 学习目标： 1、知识与技能 掌握二叉树三种遍历的遍历原则和方法 2、过程与方法 通过体验、分析、讲授和实践探究，学会遍历二叉树 3情感态度与价值观 （！）通过遍历学习，培养学生细致严谨的思维习惯 （2）促进学生对算法学习的热情，学习在平时生活中建模思想。 学情分析： 本学期高一学生刚刚学习完数学选修科目3《算法》，对数据流程有比较深刻的认知，具备探究树理论的基础。 重难点： 重点：二叉树特征； 难点：二叉树的遍历规则的实际使用。 教学过程： 活动一：一起游戏——汉诺塔 游戏介绍：汉诺塔是一款WP7平台上源于印度一个古老传说的益智类游戏。传说上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 游戏玩法：游戏里有三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。玩家需要做的是把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。 活动二：二叉树 1 特点：一棵由一个结点和两棵互不相交的分别称作根的左子树和右子树所组成的非空树，左右子树又同样都是二叉树。 遍历是对二叉树树的一种最基本的运算，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。 2 几种遍历 (1)前序遍历：中序遍历后序遍历 (2)遍历规则 活动三： 完成图5二叉树的前序遍历abcdeghi 图5 数据结构课程设计 目录 一. 设计目的.................................................................................................. 错误！未定义书签。 二. 设计内容 (1) 三．概要设计 (1) 1、功能模块图 (1) 2、各个模块详细的功能描述 (2) 四．详细设计 (3) 1．主函数和其他函数的伪码算法 (3) 2、主要函数的程序流程图 (7) 3、函数之间的调用关系图 (15) 五．测试数据及运行结果 (15) 1．正常测试数据及运行结果 (16) 2、非正常测试数据及运行结果 (17) 六．调试情况，设计技巧及体会 (18) 七．参考文献 (19) 八．附录：源代码 (19) 一. 设计目的 课程设计是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。能够在设计中逐步提高程序设计能力，培养科学的软件工作方法。而且通过数据结构课程设计能够在下述各方面得到锻炼： 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。 二. 设计内容 最小生成树问题: 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 三．概要设计 1、功能模块图 /*分别利用prim算法和kruskal算法实现求图的最小生成树*/ #include if(i==j) GA[i][j]=0; else GA[i][j]=MaxValue; printf("输入%d条无向带权边",e); for(k=0;k 目录 一．选题背景 (1) 二．问题描述 (1) 三．概要设计 (2) 3.1.创建二叉树 (2) 3.2.二叉树的非递归前序遍历示意图 (2) 3.3.二叉树的非递归中序遍历示意图 (2) 3.4.二叉树的后序非递归遍历示意图 (3) 四．详细设计 (3) 4.1创建二叉树 (3) 4.2二叉树的非递归前序遍历算法 (3) 4.3二叉树的非递归中序遍历算法 (4) 4.4二叉树的非递归后序遍历算法 (5) 五．测试数据与分析 (6) 六．源代码 (6) 总结 (10) 参考文献: (11) 一．选题背景 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。因此每个结点为 由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。可先用这三种遍历输出二叉树的结点。 然而所有递归算法都可以借助堆栈转换成为非递归算法。以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的非递归遍历。将输出结果与递归结果比较来检验正确性。。 二．问题描述 对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。 三．概要设计 3.1.创建二叉树 3.2.二叉树的非递归前序遍历示意图 图3.2二叉树前序遍历示意图3.3.二叉树的非递归中序遍历示意图 图3.3二叉树中序遍历示意图 最小生成树模型与实验 第六章 最小生成树模型与实验 树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都有很重要的应用。 §6.1树与树的性质 上章已讨论了图和树的简单基本性质。为使更清楚明了，现在使用实例来说明。 例6.1 已知有五个城市，要在它们之 间架设电话线，要求任何两个城市都可以互相 通话（允许通过其它城市），并且电话线的根 数最少。 用五个点54321,,,,v v v v v 代表五个城市，如果 在某两个城市之间架设电话线，则在相应的两个点之间联一条边，这样一个电话线网就可以用一个图来表示。为了任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图6.1的表达式满足要求的一个电话线网。 定义6.1 一个无圈的连通图称为树. 例6.2 某大学的组织机构如下所示: v 5v 4v 图 教务处 研究处 校行政办公室 研究生院 财务科 行政科 理工学院 人事学院 外语学院 …… 如果用图表示，该工厂的组织机构图就是一个树。上章给出了一些树的性质，为使能进一步研究这部分知识，先再列出常用一些树和生成树的性质。 树的性质： （1） 树必连通，但无回路（圈）； （2） n 个顶点的树必有1-n 条边； （3） 树中任意两点间，恰有一条初等链； （4） 树连通，但去掉任一条边，必变为不连通； （5） 树无回路（圈），但不相邻顶点连一条边，恰得一回路（圈）。 生成树与最小树 定义6.2 设图),(11E V G =是图},{E V G =的生成子图，如果1G 是一棵树，记),(1E V T =，则称T 是G 的一棵生成树。 定理6.1 图G 有生成树的充分必要条件是图G 的连通的。 数学物理文科 理校教学校长 最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次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） 数据结构程序设计报告 学院： 班级： 学号： 姓名： 实验名称：二叉树的建立与遍历 一、实验目的： 1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法； 3.掌握二叉树的先序、中序、后序的递归实现方法。 二、实验内容和要求： 创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。 三、叉树的建立与遍历代码如下： #include int front=0,rear=-1,counter=0;//初始队列中需要的变量front、rear和计数器counter char ch; printf("建立二叉树，请输入结点:（#表示虚节点,!表示结束)\n"); ch=getchar(); while(ch!='!') { if(ch!='#') { p=(TNODE *)malloc(sizeof(TNODE)); p->data=ch; p->lchild=NULL; p->rchild=NULL; rear++; queue[rear]=p;//把非#的元素入队 if(rear==0)//如果是第一个元素，则作为根节点 { root=p; counter++; } else { if(counter%2==1)//奇数时与其双亲的左子树连接 { queue[front]->lchild=p; } if(counter%2==0)//偶数时与其双亲的右子树连接 { queue[front]->rchild=p; 以邻接矩阵存储的图类型构造n个城市连接的最小生成树代码： #include scanf("%d" ,&(G->vexs[i])) ; /* 输入顶点信息，建立顶点表*/ } for (i=0 ;i 《数据结构课程设计》题目二：最小生成树的构建 学院：XXXXXXXXXXX 班级：XXXXXXXXXXX 学号：XXXXXXXXXXX 姓名：XXXXXXXXXXX 设计时间：XXXXXXXXXXX 目录： 1.需求分析--------------------------------------------- 1 2.课题设计内容--------------------------------------- 1 (1)课程设计基本流程------------------------------------------ 1 (2)详细设计说明------------------------------------------------1 (3)界面操作流程图：----------------------------------------- 2 (4)主要程序------------------------------------------------------3 (5)运行结果截图----------------------------------------------- 5 3.得意之处--------------------------------------------- 6 4.设计实践过程中的收获与体会------------------ 6 5.设计目前存在的问题------------------------------ 7 6.主要参考文献-------------------------------------- 7 一、需求分析 本课程主要是完成一个最小生成树的构建，要求用克鲁斯卡尔算法或者普利姆算法求网的最小生成树（此程序我用的是 普利姆算法），并输出各条边及他们的权值。要求用户在使用 时可以准确输入顶点及每个顶点的关系，运算出可以建立的关 系网，最后利用普利姆算法准确输出最短路径。 二、课程设计内容 1、课程设计基本流程： 关于此课程的设计，是从设计要求入手的。根据对知识的掌握程度，我选择了用普利姆算法进行设计。 根据实验要求，我定义了一个prims类，在类中定义一个私有成员函数和一个公有成员函数。定义相关变 量和相关函数，并完善程序。 2、详细设计说明： 首先在私有成员private中定义节点个数n、图中边的个数g，树的边的个数t，源节点s。定义二维数组 graph_edge[99][4]和tree_edge[99][4]，分别为图的边 和树的边。因为普利姆算法是把图分为两部分进行运算， 所以我定义了T1[50],t1为第一部分， T2[50],t2为第 二部分。在公有成员public中定义输入函数input()、 算法函数algorithm()、输出函数output()。 1 武 夷 学 院 课程设计报告 课程名称： 数据结构 设计题目： 最小生成树的应用 学生班级： 09计科2班 学生姓名： 蒋家权，陈相财，吴继伟，梁丽春 指导教师： 林丽惠 完成日期： 2011-1-19 课程设计项目研究报告 目录 一、问题分析和任务定义....................................................................................... - 1 - 二、实现本程序需要解决的问题如下................................................................... - 1 - 三、测试数据........................................................................................................... - 2 - 四、算法思想........................................................................................................... - 3 - 五、模块划分........................................................................................................... - 4 - 六、算法设计与分析............................................................................................... - 7 - 七、源程序............................................................................................................. - 11 - 八、测试数据......................................................................................................... - 14 - 九、课程设计项目进度表及任务分配表及任务分配表..................................... - 16 - 十、设计心得......................................................................................................... - 17 -十、参考书目......................................................................................................... - 18 - 构造可以使N个城市连接的最小生成树 专业：_________ 班级：_________ 姓名：_________ 学号：_________ 完成日期：_________ 【问题描述】 给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 【设计需求及分析】 1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义， 若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。 2、要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 3、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）。 【设计功能的实现】（用C或C++语言描述） #include int main(int argc, char * argv[]);//主函数 Status LocateVex(MGraph G, VertexType v);//判断城市v 在网G 中的位置Status CreateUDN(MGraph &G);//创建网G 的邻接矩阵 void DisplayNet(MGraph G);//以邻接矩阵的形式显示网G void MiniSpanTree_KRUSKAL(MGraph G);//最小生成树的Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);//最小生成树的Prim 算法Status Minimum(closedge closeEdge, int n);//Prim 算法中求下一个城市的函数void DeleteInfo(MGraph &G);//释放堆内存上动态申请的空间 int main(int argc, char * argv[]) { CreateGraph(G); DisplayNet(G); MiniSpanTree_KRUSKAL(G); MiniSpanTree_PRIM(G, G.vexs[0]); DeleteInfo(G); cout<数据结构-第六章-图-练习题及答案详细解析(精华版)
二叉树遍历方法技巧
用Prim算法构造最小生成树
最小生成树问题
最小生成树数据结构课程设计报告
最小生成树问题
最小生成树实验报告
二叉树的遍历教案
最小生成树问题课程设计报告
分别利用prim算法和kruskal算法实现求图的最小生成树
二叉树遍历课程设计心得【模版】
最小生成树模型与实验
最小生成树算法分析
二叉树遍历课程设计】汇编
以邻接矩阵存储的图类型构造n个城市连接的最小生成树
数据结构课程设计最小生成树的构建实验报告
数据结构课程设计报告(最小生成树完整版)
构造可以使N个城市连接的最小生成树