数据结构课程设计(共15页).docx

《数据结构课程设计(共15页).docx》由会员分享，可在线阅读，更多相关《数据结构课程设计(共15页).docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上目 录1 问题描述在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。2 需求分析1. 要在n个城市间建设通信网络，只需要架设n-1条线路即可，建立的最小生成树即能实现付出最低的经济代价。2. 程序利用的是克鲁斯卡尔算法或prim算法求网的最小生成树。3. 输出结果为文本形式的生成树和他们之间的权值。4. 演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。3 概要设计31抽象数据类型定义ADT Graph数据对象V：V是具有相同特性的数据元素的集

2、合，称为顶点集。数据关系R：R=VR VR=|v,wV且P(v,w)，表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息基本操作： CreateGraph( &G, V, VR ) 初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestroyGraph( &G ) 初始条件：图G存在。 操作结果：销毁图G。LocateVex( G, u ) 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。GetVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。PutV

3、ex( &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

4、 ) 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。InsertArc( &G, v, w ) 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中增添弧，若G是无向的，则还增添对称弧。DeleteArc( &G, v, w ) 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中删除弧，若G是无向的，则还删除对称弧。DFSTraverse( G, Visit() ) 初始条件：图G存在，Visit是顶点的应用函数。 操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。BFST

5、raverse( G, Visit() ) 初始条件：图G存在，Visit是顶点的应用函数。 操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。ADT Graph32模块划分本程序包括四个模块：（1）主程序模块int main(void)初始化；选择菜单；构造无向图；构造最小生成树；输出最小生成树（2）图模块实现图的抽象数据类型（3）prim算法模块（4）kruskal算法模块4 详细设计41数据类型的定义（1）图类型#define M 20#define MAX 20#define null 0#define MAX_V

6、ERTEX_NUM 20/ 最大顶点个数#define MAX_NAME 3 / 顶点字符串的最大长度+1 #define MAX_INFO 20 / 相关信息字符串的最大长度+1 #define INFINITY INT_MAX/ 用整型最大值代替typedef int VRType;typedef char InfoType;typedef char VertexTypeMAX_NAME;/ 邻接矩阵的数据结构typedef structVRType adj; / 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； / 对带权图，则为权值类型 InfoType *info; / 该弧

7、相关信息的指针(可无) ArcCell, adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 图的数据结构typedef structVertexType vexsMAX_VERTEX_NUM;/ 顶点向量adjMatrix arcs;/ 邻接矩阵int vexnum,/ 图的当前顶点数arcnum;/ 图的当前弧数 mGraph;/ 记录从顶点集U到V-U的代价最小的边的辅助数组定义typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;42主要模块的算法描述(1) 主函数int m

8、ain(void) /主函数 int i;scanf(%d,&i);switch(i) /*选择菜单*/case 1: 用prim算法求最小生成树 break;case 2: 用kruskal算法求最小生成树break;default:printf(tt输入错误！请重新输入！n);(2)用prim算法求最小生成树模块伪代码如下定义图的数据结构；图的构建； /*prim算法求最小生成树*/ 对I,j,k定义；记录从顶点集U到V-U的代价最小的边的辅助数组定义；把顶点信息的赋给k；辅助数组初始化；令最小代价初始化为0，closedgek.lowcost=0; / 初始,U=u；满足当循环变量i小于

9、图的当前节点数时循环；按照选取最小代价法则（即求closedge.lowcost的最小正值）选取当前节点的下一结点（第k顶点）；输出生成树的边；将第k顶点并入U集合； 满足循环变量j小于图的当前点数时循环；新顶点并入U集后重新选择最小边； (3)用kruskal算法求最小生成树模块伪代码如下图的构建并初始化 定义图的数据结构；申请节点空间(如果失败则返回信息)；创建图； /*kruskal算法求最小生成树*/对i,j,n,m, parentM,edge edgesM定义或初始化；满足当循环变量i小于图的当前节点数时循环；满足循环变量j=i+1小于图的当前点数时循环；if(第i个顶点于第j个顶点

10、相连) 把i赋给edgesk.begin； 把j赋给edgesk.end； 把i，j之间的权值赋给edgesk.weight； K+；/*对结构体edge进行初始化*/ 对图G边的权值进行排序sort(edges, G)； 当循环变量i小于当前弧度数时将0赋给parenti，初始化数组；当循环变量i小于当前弧度数时(此时第i条弧为最小的) 找第i条弧的起点和终点；并分别赋给你n，m； 当n，m不相等时把m赋给parentn；输出此时第i条弧的起点、终点、权值； 5 测试分析测试数据及结果如下：图一：prim算法求最小生成树结果图图二：kruskal算法求最小生成树结果图 从结果显示来看，结果也

11、与编程的理论一样，所以，此程序正确。6 课程设计总结数据结构是计算机专业的一门专业基础课，设计到计算机软、硬件等各方面的知识，如计算机硬件范围的存储装置和存取方法；计算机软件范围的数据的动态存储与管理，信息检索等。更重要的是，它能实现程序算法和实际高效的结合。图是上学期学习的一个比较复杂的知识点，它包含了丰富的内容。通过课程设计加深了我对图知识的认识，巩固了关于图的一些算法：建立邻接矩阵，Prim、Kruskal生成最小生成树算法。通过课程设计，有如下几点收获和体会：1.其实我在编程方面并不擅长，水平有限，在程序设计上存在不少缺陷，并且程序如何与实际项目相结合，还需进一步探索。尽管如此，经过了

12、这次图的最小生成树的实现的课程设计我从中学到了很多,不仅是对于一个成熟的程序的构思，还有算法的规范化、高效化，以及如何将算法合理的应用于工程项目中，这是一个关键的环节.还有就是程序设计和运行测试中遇到的问题该如何解决,从解决问题中我也学到了许多平时课本上所没有的知识.当然,能够实现图的关键路径我自己也感觉有一定的成就感。2.通过课程设计还提高了一点改错能力，对于一些常见问题加深了印象。每次课程设计都会有多多少少的收获，这些收获将成为以后学习中一笔不可或缺的财富。总结不足：在编写源程序代码的过程中对语言的运用还需要提高,应使写出来的程序更加简洁,易读懂,更加满足实际工作的需要.要想使做出来的程序

13、更好的利用还需根据实际需要在今后的运用中不断的改进和完善。在此我非常要感谢的是我的指导老师黄磊老师，感谢老师的细心认真的辅导，让我对数据结构这门课程有了更加深刻的认识和了解；我还要感谢父母，因为有了父母对我的热切关注，让我有了直面困难的勇气；我还要感谢我的同学们，每当我碰到一个难题的时候，他们也会热心的帮我想办法，也让我感受到团队合作的力量。参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰

14、数据结构M北京：中国铁道出版社，20035 谭浩强. C语言程序设计（第二版）M.北京：清华大学出版社，2003附录（源程序清单）#include#include#includemalloc.h #include #include #include #define M 20#define MAX 20#define null 0#define MAX_VERTEX_NUM 20/ 最大顶点个数#define MAX_NAME 3 / 顶点字符串的最大长度+1 #define MAX_INFO 20 / 相关信息字符串的最大长度+1 #define INFINITY INT_MAX/ 用整型最大

15、值代替typedef int VRType;typedef char InfoType;typedef char VertexTypeMAX_NAME;/ 邻接矩阵的数据结构typedef structVRType adj; / 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； / 对带权图，则为权值类型 InfoType *info; / 该弧相关信息的指针(可无) ArcCell, adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 图的数据结构typedef structVertexType vexsMAX_VERTEX_NUM;/ 顶点向量adjMa

16、trix arcs;/ 邻接矩阵int vexnum,/ 图的当前顶点数arcnum;/ 图的当前弧数 mGraph;/ 记录从顶点集U到V-U的代价最小的边的辅助数组定义typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;/ 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。int LocateVex(mGraph G,VertexType u)int i;for(i = 0; i G.vexnum; +i)if( strcmp(u, G.vexsi) = 0)return i;return -1;/

17、 采用数组(邻接矩阵)表示法,构造无向网G。int CreateAN(mGraph *G)int i,j,k,w,IncInfo;char sMAX_INFO,*info;VertexType va,vb;printf(请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0):(空格区分) );scanf(%d%d%d%*c,&(*G).vexnum,&(*G).arcnum,&IncInfo); printf(请输入%d个顶点的值(%d个字符):n,(*G).vexnum,MAX_NAME);for(i=0;i(*G).vexnum;+i) / 构造顶点向量 scanf(%s,(*G

18、).vexsi);for(i=0;i(*G).vexnum;+i) / 初始化邻接矩阵 for(j=0;j(*G).vexnum;+j)(*G).arcsij.adj=INFINITY; / 网初始化为无穷大 (*G).arcsij.info=NULL;printf(请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): n,(*G).arcnum);for(k=0;k(*G).arcnum;+k)scanf(%s%s%d%*c,va,vb,&w); / %*c吃掉回车符 i=LocateVex(*G,va);j=LocateVex(*G,vb);(*G).arcsij.adj=(*G).a

19、rcsji.adj=w; / 无向 if(IncInfo)printf(请输入该边的相关信息(%d个字符): ,MAX_INFO);gets(s);w=strlen(s);if(w)info=(char*)malloc(w+1)*sizeof(char);strcpy(info,s);(*G).arcsij.info=(*G).arcsji.info=info; / 无向 return 1;/ 求closedge.lowcost的最小正值int minimum(minside SZ,mGraph G)int i=0,j,k,min;while(!SZi.lowcost)i+;min=SZi.l

20、owcost; / 第一个不为0的值 k=i;for(j=i+1;j0)if(minSZj.lowcost)min=SZj.lowcost;k=j;return k;/ 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边void MiniSpanTree_PRIM(mGraph G,VertexType u)int i,j,k;minside closedge;k=LocateVex(G,u);for(j=0;jG.vexnum;+j) / 辅助数组初始化 if(j!=k)strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj

21、.adj;closedgek.lowcost=0; / 初始,U=u printf(最小代价生成树的各条边为:n);for(i=1;iG.vexnum;+i) / 选择其余G.vexnum-1个顶点 k=minimum(closedge,G); / 求出T的下一个结点：第K顶点 printf(%s-%s)n,closedgek.adjvex,G.vexsk); / 输出生成树的边 closedgek.lowcost=0; / 第K顶点并入U集 for(j=0;jG.vexnum;+j)if(G.arcskj.adjarcnum,&G-vexnum);for (i = 1; i vexnum;

22、i+)/初始化图for ( j = 1; j vexnum; j+)G-arcij.adj = G-arcji.adj = 0;for ( i = 1; i arcnum; i+)/输入边和权值printf(n请输入有边的2个顶点);scanf(%d %d,&n,&m);while(n G-vexnum | m G-vexnum)printf(输入的数字不符合要求 请重新输入:);scanf(%d%d,&n,&m);G-arcnm.adj = G-arcmn.adj = 1;getchar();printf(n请输入%d与%d之间的权值:, n, m);scanf(%d,&G-arcnm.we

23、ight);printf(邻接矩阵为:n);for ( i = 1; i vexnum; i+)for ( j = 1; j vexnum; j+)printf(%d ,G-arcij.adj);printf(n);void sort(edge edges,MGraph *G)/对权值进行排序int i, j;for ( i = 1; i arcnum; i+)for ( j = i + 1; j arcnum; j+)if (edgesi.weight edgesj.weight)Swapn(edges, i, j);printf(权排序之后的为:n);for (i = 1; i arcnu

24、m; i+)printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);void Swapn(edge *edges,int i, int j)/交换权值 以及头和尾int temp;temp = edgesi.begin;edgesi.begin = edgesj.begin;edgesj.begin = temp;temp = edgesi.end;edgesi.end = edgesj.end;edgesj.end = temp;temp = edgesi.weight;edgesi.weight = edgesj.weight;edges

25、j.weight = temp;void MiniSpanTree(MGraph *G)/生成最小生成树int i, j, n, m;int k = 1;int parentM;edge edgesM;for ( i = 1; i vexnum; i+)for (j = i + 1; j vexnum; j+)if (G-arcij.adj = 1)edgesk.begin = i;edgesk.end = j;edgesk.weight = G-arcij.weight;k+;sort(edges, G);for (i = 1; i arcnum; i+)parenti = 0;printf

26、(最小生成树为:n);for (i = 1; i arcnum; i+)/核心部分n = Find(parent, edgesi.begin);m = Find(parent, edgesi.end);if (n != m)parentn = m;printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);int Find(int *parent, int f)/找尾while ( parentf 0)f = parentf;return f;int main(void) /主函数 int i; printf( 数据结构课程设计n); print

27、f(专业班级：10计本n); printf(姓名：匡文彬n学号：n指导老师:黄磊nn); printf( 最小生成树的求法n); printf( _n); printf( | 1.用prim算法求最小生成树 |n); printf( | 2.用kruskal算法求最小生成树 |n); printf( |_ |n); printf( _请选择相应的菜单(1-2) :n);scanf(%d,&i);switch(i)case 1:mGraph G; CreateAN(&G); MiniSpanTree_PRIM(G,G.vexs0); system(pause); return 0; break;case 2:MGraph *G; G = (MGraph*)malloc(sizeof(MGraph); if (G = NULL) printf(memory allcation failed,goodbye); exit(1); CreatGraph(G); MiniSpanTree(G); system(pause); return 0;break;default:printf(tt输入错误！请重新输入！n);专心-专注-专业