数据结构课程设计.docx

目 录1 问题描述12 需求分析13 概要设计131抽象数据类型定义132模块划分24 详细设计341数据类型的定义342主要模块的算法描述35 测试分析56 课程设计总结6参考文献7附录（源程序清单）81 问题描述在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。2 需求分析1. 要在n个城市间建设通信网络，只需要架设n-1条线路即可，建立的最小生成树即能实现付出最低的经济代价。2. 程序利用的是克鲁斯卡尔算法或prim算法求网的最小生成树。3. 输出结果为文本形式的生成树和他们之间的权值。4. 演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。3 概要设计31抽象数据类型定义ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系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的值。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 ) 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中增添弧，若G是无向的，则还增添对称弧。DeleteArc( &G, v, w ) 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中删除弧，若G是无向的，则还删除对称弧。DFSTraverse( G, Visit() ) 初始条件：图G存在，Visit是顶点的应用函数。 操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。BFSTraverse( 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_VERTEX_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; / 该弧相关信息的指针(可无) 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 main(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小于图的当前节点数时循环；按照选取最小代价法则（即求closedge.lowcost的最小正值）选取当前节点的下一结点（第k顶点）；输出生成树的边；将第k顶点并入U集合； 满足循环变量j小于图的当前点数时循环；新顶点并入U集后重新选择最小边； (3)用kruskal算法求最小生成树模块伪代码如下图的构建并初始化 定义图的数据结构；申请节点空间(如果失败则返回信息)；创建图； /*kruskal算法求最小生成树*/对i,j,n,m, parentM,edge edgesM定义或初始化；满足当循环变量i小于图的当前节点数时循环；满足循环变量j=i+1小于图的当前点数时循环；if(第i个顶点于第j个顶点相连) 把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算法求最小生成树结果图 从结果显示来看，结果也与编程的理论一样，所以，此程序正确。6 课程设计总结数据结构是计算机专业的一门专业基础课，设计到计算机软、硬件等各方面的知识，如计算机硬件范围的存储装置和存取方法；计算机软件范围的数据的动态存储与管理，信息检索等。更重要的是，它能实现程序算法和实际高效的结合。图是上学期学习的一个比较复杂的知识点，它包含了丰富的内容。通过课程设计加深了我对图知识的认识，巩固了关于图的一些算法：建立邻接矩阵，Prim、Kruskal生成最小生成树算法。通过课程设计，有如下几点收获和体会：1.其实我在编程方面并不擅长，水平有限，在程序设计上存在不少缺陷，并且程序如何与实际项目相结合，还需进一步探索。尽管如此，经过了这次图的最小生成树的实现的课程设计我从中学到了很多,不仅是对于一个成熟的程序的构思，还有算法的规范化、高效化，以及如何将算法合理的应用于工程项目中，这是一个关键的环节.还有就是程序设计和运行测试中遇到的问题该如何解决,从解决问题中我也学到了许多平时课本上所没有的知识.当然,能够实现图的关键路径我自己也感觉有一定的成就感。2.通过课程设计还提高了一点改错能力，对于一些常见问题加深了印象。每次课程设计都会有多多少少的收获，这些收获将成为以后学习中一笔不可或缺的财富。总结不足：在编写源程序代码的过程中对语言的运用还需要提高,应使写出来的程序更加简洁,易读懂,更加满足实际工作的需要.要想使做出来的程序更好的利用还需根据实际需要在今后的运用中不断的改进和完善。在此我非常要感谢的是我的指导老师黄磊老师，感谢老师的细心认真的辅导，让我对数据结构这门课程有了更加深刻的认识和了解；我还要感谢父母，因为有了父母对我的热切关注，让我有了直面困难的勇气；我还要感谢我的同学们，每当我碰到一个难题的时候，他们也会热心的帮我想办法，也让我感受到团队合作的力量。参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构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/ 用整型最大值代替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;/ 顶点向量adjMatrix 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;/ 采用数组(邻接矩阵)表示法,构造无向网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).vexsi);for(i=0;i(*G).vexnum;+i) / 初始化邻接矩阵 for(j=0;j(*G).vexnum;+j)(*G).arcsij.adj=INFINITY; / 网初始化为无穷大 (*G).=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).arcsji.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).=(*G).=info; / 无向 return 1;/ 求closedge.lowcost的最小正值int minimum(minside SZ,mGraph G)int i=0,j,k,min;while(!SZi.lowcost)i+;min=SZi.lowcost; / 第一个不为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.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; 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.weight);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 arcnum; 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;edgesj.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+)p