淮北师范大学数据结构图相关算法的课程设计.doc

淮北师范大学 数据结构课程设计 图的相关算法 ----无向图相关算法 学 院 计算机科学与技术 专 业 计算机科学与技术(师范) 学 号 20091201016 学 生 姓 名 *** 指导教师姓名 *** 2011年月 实现从文件中读入图的信息，能够根据信息建立有向图和无向图，并分别用邻接矩阵和邻接表存储。在此基础上，实现Prim、Kruskal、Dijkstra 程序应具有以下基本功能： 图的建立和存储:根据文件中的信息，建立图并采用合适结构存储：无向图的邻接矩阵和邻接表、有向图的邻接矩阵和邻接表。 分别实现Prim、Kruskal、DijkstraPrim、Kruskal、DijkstraPrim、Kruskal、Dijkstra 3、功能要求 1．不同的功能使用不同的函数实现块对个数调释对进释2．对系统进行功能模块分析、画出总流程图和各模块流程图。 3．用户接口要求使用方便、简洁明了、美观大方、格式统一。 4．通过应选项能进个应选项5．所有程序需调试过2、程序无向图相关算法的基本功能 本部分程序可以对图的相关信息：顶点、边以及顶点与边的指向关系建立无向图的邻接矩阵进行拓扑排序。 3、程序代码设计 1．文件保存函数（void getin_1()） 建立一个名为record_1.txt的文件保存数据，保存的数据包括顶点的个数、边的条数、顶点与边之间的关系。 2．文件载入函数（int getout_1()） 根据文件中保存的数据，从指定文件中按格式输入数据，并根据输入图的相关信息建立对应的无向图邻接矩阵。 3．邻接矩阵输出函数（void outmatrix();） 将根据相关信息建立的邻接矩阵打印出显示在屏幕上。 4．Prim算法函数（void MiniSpanTree_PRIM(char u))） 根据输入图的相关信息建立邻接矩阵运用Prim算法得出最小生成树并将所得最小生成树的结果打印出显示在屏幕上。 5．迪杰斯特拉算法函数（void Dijkstra(int v)） 根据输入图的相关信息建立邻接矩阵运用Dijkstra算法得出最短路径并将所得最短路径的结果打印出显示在屏幕上。 4、数据结构 typedef struct { char vexs[N]; int edges[N][N]; int n,e; //顶点数和边数 }MGraph; MGraph g; typedef struct { char adjvex; int lowcost; }minside; 三、程序调试： 主程序界面： 子程序（无向图相关算法）界面： 建立无向图的邻接矩阵： 运用Prim算法计算最小生成树： 5．运用Dijkstra算法计算最短路径： 四、结束语： 1、本人在程序设计中感想： 从学数据结构以来，有关数据结构的实验做得很少，现在做到图的相关算法，普里姆、克鲁斯卡尔、迪杰斯特拉、拓扑排序，平时感觉对这些算法都挺熟悉的，但要实现它们还真的不容易。 2、 感谢语： 这一周的收获与刘怀愚老师的辛勤付出是分不开的，刘老师总是很耐心的辅导我们，给我们讲程序一讲就是两节课，他不仅只是讲怎样写代码，还教我们怎样去分析，这让我学到不少，这种负责的态度让我们学得更有动力，衷心的感谢老师！ 五、相关程序源码： #includestdio.h #includestdlib.h #define N 9999 void main(); typedef struct {char vexs[N];int edges[N][N];int n,e;//顶点数和边数}MGraph; MGraph g; typedef struct{char adjvex;int lowcost;}minside; // 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 int LocateVex(char u){ int i;for(i = 0; i g.n; ++i)if( u==g.vexs[i])return i;return -1;} // 求closedge.lowcost的最小正值 int minimum(minside SZ[]) {int i=0,j,k,min;while(SZ[i].lowcost==0)i++;min=SZ[i].lowcost; //第一个不为0的值 k=i;for(j=i+1;jg.n;j++) if(SZ[j].lowcost0)if(minSZ[j].lowcost){min=SZ[j].lowcost;k=j;}return k;}