图的遍历数据结构课程设计.doc

徐俊 用C语言解决图的遍历的问题 第页 共14页 长沙理工大学用C语言解决图的遍历课程设计报告徐俊 学 院 计算机与通信工程 专 业 计算机科学与技术 班 级 计算机08-03 学 号 200850080307 学生姓名 徐俊 指导教师 湛新霞 课程成绩 完成日期 2010年6月23日课程设计成绩评定学 院 计算机与通信工程学院 专 业 计算机科学与技术 班 级 计算机08-03 学 号 200850080307 学生姓名 徐俊 指导教师 湛新霞 完成日期 2010.6.23 指导教师对学生在课程设计中的评价评分项目优良中及格不及格课程设计中的创造性成果学生掌握课程内容的程度课程设计完成情况课程设计动手能力文字表达学习态度规范要求课程设计论文的质量指导教师对课程设计的评定意见综合成绩 指导教师签字 2010年6月25日 用C语言解决图的遍历的问题 学生姓名：徐俊 指导老师：湛新霞摘 要 本课程设计主要目的在于更深一步的了解图的遍历的问题，图的DFS,BFS的递归和非递归算法的实现，用有向图和无向图分别实现图的遍历，广度优先遍历和深度优先遍历的实现，用邻接矩阵和邻接表等多种结构存储存储图。在课程设计中，程序设计设计语言采用Visual C，程序运行平台为Windows 98/2000/XP。在程序设计中我主要是解决的是给出一个图如何用多种方法完成图的遍历的问题，也包括如何创建一个图，深度优先遍历和广度优先遍历一个图，递归和非递归的方法实现图的遍历。程序最终通过调试运行，初步实现了设计目标。关键词 程序设计；数据结构；有向图；无向图；存储结构；邻接矩阵；递归算法一 引 言数据结构是一门专业基础课，它对学习者的的要求很明确：学会分析、研究计算机加工的数据结构的特性，以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。其次，该课程的学习过程也是复杂程序设计的训练过程，要求学习者编写的程序结构或设计的程序结构体清楚、正确、易读，符合软件工程的规范。图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。就本课程设计而言应用图论的知识讨论如何在计算机上实现图的遍历的操作，主要解决图的遍历的几种方法的实现。本设计采用目前最通用的程序设计语言之一C语言作为数据结构和算法的描述语言。二 设计目的与任务2.1课程设计的目的 进一步的了解图的遍历的问题，图的DFS,BFS的递归和非递归算法的实现，用有向图和无向图来实现图的遍历，用邻接矩阵和邻接表的存储方式存储图。初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题。训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风。提高综合运用所学的理论知识和方法独立分析和解决问题的能力。2.2 课程设计的任务问题描述：从键盘上输入一个图的基本信息（图用邻矩阵表示）。图的DFS,BFS的递归和非递归算法的实现;用有向图实现图的遍历；用无向图实现图的遍历；用邻接矩阵存储图；用邻接表存储图。课题要求：首先输入图的结点数； 依次输入图的各条边（数据之间用空格隔开）；输出的形式：按用户选择的遍历方法给出遍历顺序，各字符间用-分隔； 程序所能达到的功能：能够按要求输出所要的结果。三 设计方案和实施3.1 总体设计采用邻接矩阵作为图的存储结构。程序中主要用到以下抽象数据类型：抽象数据类型的定义typedef struct char *vexs; /顶点向量 int arcsMAX_VEXMAX_VEX; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数 Graph;基本操作CreateUDN(Graph &G)操作结果：用邻接矩阵创建带权无向网图。DFS(Graph G,int k)操作结果：对已存在的图进行深度优先遍历。BFS(Graph G)操作结果：对已存在的图进行广度优先遍历。choose(Graph G)操作结果：对将要实现的操作步骤进行选择。程序包含两个模块主程序模块，其中主函数为int main输入信息；根据输入要求进行选择操作和输出；输出结果； 选择操作模块实现具体选择的对应操作及输出操作。 两模块之间的简单调用关系如图1所示。主函数模块选择操作模块 递归调用图1 模块调用图3.2 详细设计各个函数之间的调用关系如图2所示。主函数创建无向网图函数数据输入选择操作模块深度优先遍历退出程序广度优先遍历数据输出程序结束数据输出图2 函数调用关系图函数设计程序设计中主要包括下列函数用邻接矩阵创建一个图：void CreateUDN(Graph &G) 用邻接矩阵创建一个带权无向网图; 输入顶点数和弧数; 输入各个顶点及各条弧;递归方法实现图的遍历：void DFS(Graph G, int k)用递归的方法访问图中的结点;对图进行深度优先遍历;非递归方法实现图的遍历：void BFS(Graph G) 用队列辅助访问图中的结点;对图进行广度优先遍历;选择输出需要的遍历方法：void choose(Graph G)给出程序运行的选项;对相应的输入选项调用相应的函数以执行操作;3.3 程序调试与体会通过这次课程设计，我受益颇多：首先，上课时听的理论知识，似乎很容易接受，以及各种算法都能够比较轻松的理解，但是在真正的运用过程中，并不能把理论知道很好的和实践结合起来。感觉自己有点眼高手低，有些知识点的应用只有在实践中才能慢慢体会，在平时做实验时，总感到有些无从下手。因此，在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握，自如运用。其次，通过这次课程设计，对我的逻辑思维能力是一个很大的锻炼，再有，它还加强了我的系统思考问题的能力，在编程方面，我开始从整体的角度来考虑问题了，而不再像以前一样的，胡乱动手。也就是因为先前的这种编程习惯，使得我在课程设计过程中浪费了不少的时间，尝到了教训。通过这次课程设计，我学习了很多平时很少关注的知识点，比如循环链，递归的应用，也增强了自己的实践能力和编写程序的能力。图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。用邻接矩阵作为图的数据存储结构很好地解决了图的结构难点， 借助于邻接矩阵容易判定任意两个顶点之间是否有边(或弧)相连，并容易求得各个顶点的度。该程序通俗易懂且实用性强，并且该程序清单详细具体、全面、具有很强的可读性；系统整体上比较完美，可以从键盘获取输入元素，并且可以根据用户输入进行选择性地输出；整体输出画面效果整洁、大方。3.4 运行结果（截图）程序运行如图3所示：图3 输入图的顶点数和弧数 图4 输入各个顶点和各条弧 图5 选择图的遍历方式四 致 谢首先，我要感谢学校给我提供了此次课程设计的机会，能让同学们在一起学习与研究，让我有机会对所学的理论知识进行实践。其次，在论文的写作过程中，也得到了许多同学的宝贵建议，同时还得到许多学长的支持和帮助，在此一并致以诚挚的谢意。最后，我还要特别感谢我们的辅导老师湛新霞老师，在她的精心辅导和帮助下，我的设计才得以顺利完成。对她为我们的设计所提出的宝贵意见表示忠心的感谢！参考文献 1 谭浩强. C程序设计第三版. 北京:清华大学出版社,2005 2罗宇等. 数据结构M . 北京:北京邮电大学出版社, 2003 3严藯敏. 数据结构C语言版. 北京:清华大学出版社, 1997 附录：源程序清单/ 程序名称：TUDEBIANLI.C/ 程序功能：采用递归和非递归算法，有向图和无向图，邻接矩阵和邻接表等多种结构存储实现图的遍历。/ 程序作者：徐俊/ 最后修改日期：2010-7-7#includestdio.h#includestdlib.h#define INFINITY 32767 #define MAX_VEX 20 /最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) /队列长度 bool *visited;/访问标志数组 int z=1; /图的邻接矩阵存储结构 typedef struct char *vexs; /顶点向量 int arcsMAX_VEXMAX_VEX; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数 Graph; class Queue /队列类 public: void InitQueue() base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_SIZE; void DeQueue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; int *base; int front; int rear; ; int Locate(Graph G,char c) /图G中查找元素c的位置for(int i=0;iG.vexnum;i+) if(G.vexsi=c) return i; return -1; void CreateUDN(Graph &G) /创建无向网int i,j,w,s1,s2; char a,b,c,temp; printf(输入顶点数和弧数:); scanf(%d%d,&G.vexnum,&G.arcnum); temp=getchar(); /接收回车 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配顶点数目 printf(输入%d个顶点.n,G.vexnum); for(i=0;iG.vexnum;i+) /初始化顶点 scanf(%c,&G.vexsi); temp=getchar(); /接收回车 for(i=0;iG.vexnum;i+) /初始化邻接矩阵 for(j=0;jG.vexnum;j+) G.arcsij=INFINITY; printf(输入%d条弧.n,G.arcnum); for(i=0;i=0 & kG.vexnum) /k合理 for(int i=0;i=0 & i=0 & jG.vexnum) /i,j合理 for(int k=j+1;kG.vexnum;k+) if(G.arcsik!=INFINITY) return k; return -1; /深度优先遍历 void DFS(Graph G,int k) int i; if(k=-1) /第一次执行DFS时,k为-1 for(i=0;i %c,G.vexsk); +z;/访问第k个顶点 if(z-1)%G.vexnum=0) z=1;for(i=FirstVex(G,k);i=0;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); /对k的尚未访问的邻接顶点i递归调用DFS /广度优先遍历 void BFS(Graph G) int k; Queue Q; /辅助队列Q Q.InitQueue(); for(int i=0;i=0;w=NextVex(G,k,w) if(!visitedw) /w为k的尚未访问的邻接顶点 visitedw=true; printf(- %c ,G.vexsw); Q.EnQueue(w); printf(n 请继续选择:n); void choose(Graph G)/对输入选项调用相应的函数执行操作int i,m; visited=(bool *)malloc(G.vexnum*sizeof(bool);scanf(%d,&m);switch(m)case 1: printf(广度优先遍历: ); for(i=0;iG.vexnum;i+) visitedi=false; BFS(G); choose(G); printf(n);break;case 2:printf(深度优先遍历: ); for(i=0;iG.vexnum;i+) visitedi=false; DFS(G,-1); p