1、 数数 据据 结结 构构 课课 程程 设设 计计 说说 明明 书书 学生姓名学生姓名: 学学 号：号： 学学 院院: 软件学院软件学院 专专 业业: 软件工程 题题 目目: 图的遍历和生成树求解实现 成成绩绩 指 导 教指 导 教 师师 2013 年 1 月 17 日 1 设计目的设计目的(小标题黑体五号字小标题黑体五号字) 数据结构课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨 论其在计算机中的存储表示， 以及在其上进行各种运算时的实现算法， 并对算法的效率进行 简单的分析和讨论。进行数据结构课程设计要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和
2、设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科 学的工作方法和作风。 2 设计内容和要求设计内容和要求 设计内容： (1) 采用合适的存储结构来创建图，并实现图的遍历； （2）计算图的最小生成树，求联通分量 设计要求： （1）先任意创建一个图； （2) 图的 DFS,BFS 的递归和非递归算法的实现 （3) 最小生成树（两个算法）的实现，求连通分量的实现 （4) 要求用邻接矩阵、邻接表、十字链表多种结构存储实现 3 3本
3、设计所采用的数据结构本设计所采用的数据结构 (1) 选择合适的数据结构，并定义数据结构的结构体； (2) 根据程序所要完成的基本要求和程序实现提示，设计出完整的算法； (3) 按格式要求写出课程设计说明书。 4功能模块详细设计 4.1 详细设计思想（个人负责模块的 NS 流程图） int adjvex,lowcost,lowcostmax,prevexmax; int i,j,k,min; i=2; i=n; lowcosti=g1i; prevexi=1; i+; lowcosti=0; j=2; j=n; lowcostimin prevexj=k; j+; int acrvisitedm
4、ax，pre,bak,weight, i=0,j,k=0; i=G.vexnum j=i; j=G.vexnum G.arcsij.adj!=int_max N Y edgsk.pre=i;edgsk.bak=j; edgsk.weight=G.arcsij.adj;k =k+1; j=j+1; i=i+1; int x,y,m,n,buf,edf; i=0; i=gra.arcnum arcvisitedi=0; i=i+1; j=0; j=G.arcnum m=int_max; i=0; i=G.arcnum edgi.weightm N Y m=edgsi.weight;x=edgsi.
5、pre;y=edgsi.bak;n=i; i=i+1; buf=find(acrvisited,x); edf=find(acrvisited,y); edgsn.weight=int_max; buf!=edf N Y acrvisitedbuf=edf; 输出（x，y）m； j=j+1; 4.2 核心代码（个人负责模块代码） /-最小生成树的普利姆算法- typedef struct int adjvex; int lowcost; closedge; int MiniSpanTree_PRIM(int gmax,int n) int lowcostmax,prevexmax; /lowcost存储当前集合分别到剩余结点的最小权 值 /prevex存储最短路径的前一个结点 int i,j,k,min; for(i=2;i=n;i+) /n 个顶点，n-1 条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 lowcost1=0; /标志顶点 1 加入 U 集合 for(i=2;i=n;i+) /形成 n-1 条边的生成树 min=inf; k=0; for(j=2;j=n;j+) /寻找满足边的一个顶点在 U,另一个顶点在 V 的最小边 if(lowcostjmin) k=j; cout“(“prevex
