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

内蒙古科技大学课程设计论文内蒙古科技大学本科生课程设计论文题 目：c+课程设计 -图的遍历学生姓名：学 号：专 业：计算机09级班 级：（2）班指导教师： 2011年6月13日2011年6月24日内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目图的遍历指导教师时间2011-6-23一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。图的遍历以数组表示法或邻接表表示图，在此基础上实现对图的遍历。要求设计类（或类模板）来描述图，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 输入图、输出图v 求图中顶点v的第一个邻接点v 求图中顶点v的下一个邻接点v 深度优先遍历图v 广度优先遍历图 并设计主函数测试该类（或类模板）。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （c语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用c/c+描述），李建学 等 编著，清华大学出版社 2007.23.数据结构:用面向对象方法与c+语言描述，殷人昆 主编，清华大学出版社 2007.6一、前言 1.1课程设计的目的与意义41.2对课程设计功能的需求分析4二、算法思想5三、数据结构5四、模块划分6node* creategraph()/建立邻接表，完成无向图的输入void depthfirstsearch(node *list)/深度优先搜索void breadthfirstsearth(node *list)/广度优先搜索void pathsearth(node *list)/路径搜索void adjacencylistdelete(node *list)/释放邻接表的空间adjacencylistdelete(list);/释放邻接表空间五、系统的概要设计1、系统功能模块图9六、源程序10七、程序的调试分析以及测试结果1、程序的调试测试结果20八、附录1、附录一心得212、参考文献22一、前言1.1课程设计的目的与意义上学期我们对数据结构这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求我们掌握数据结构中的各方面知识，还要求我们具备一定的c+语言基础和编程能力。通过实践我们掌握数据结构中的知识。对于图的遍历这一课题来说，所要求我们掌握的数据结构知识主要有：图的存储结构、队列的基本运算实现、图的深度优先遍历算法实现、图的广度优先遍历算法实现。对于我们学生来讲，此次课程设计是为了让我们训练自己的实际设计能力，通过设计实践，去真正获得此项目管理和团队协作等方面的基本训练和工作经验。通过课程设计的一系列训练，我们能提高如何综合运用所学知识解决实际问题的能力，以及获得此项目管理和团队协作等等众多方面的具体经验，增强对相关课程具体内容的理解和掌握能力，培养对整体课程知识综合运用和融会贯通能力。1.2对课程设计功能的需求分析图的遍历并不需要是一个过于复杂的工作环境，一般来说：最合适的才是最好的。软件设计必须符合我们使用实际情况的需要。根据要求，图的遍历主要功能如下： 1、用户可以随时建立一个有向图或无向图；2、用户可以根据自己的需要，对图进行深度遍历或广度遍历；3、用户可以根据自己的需要对图进行修改；4、在整个程序中,用户可以不断的按照不同的方式对图进行遍历,若不继续,用户也可以随时跳出程序,同时,如果用户输入的序号错误,程序会提示用户重新输入序号;二、算法思想本课题本人所采用的是邻接表的方式存储图，实现图的深度、广度两种遍历，并将每种遍历结果输出来。并且能寻找路径。2.1.1图的邻接矩阵的建立 对任意给定的图（顶点数和边数自定），根据邻接表的存储结构建立图的邻接表。2.1.2 图的遍历的实现 邻接表是图的一种链式存储结构，在邻接表中，对图中的每一个顶点建立一个单链表，通常以顺序结构存储，以便随机访问任意一顶点。图的深度遍历，假设初始状态是图中所有顶点都未曾被访问，则深度优先遍历可从图中的某个顶点v出发，访问此顶点，依次从v的未被访问的邻接点出发深度优先遍历图，直至图中和v有路径想通的顶点都被访问到；若此时图中尚有未被访问的节点，则另选图中一个未被访问的顶点做起始点，直至所有节点都被访问。图的广度优先遍历，是以v为起始点，由近及远，依次访问和v有路径相通且路径长度为1、2、的顶点。三、数据结构#define t true#define f false#includestruct node/定义一个结构作为节点类型 int data; bool sign;/标志位,用来标示是否遍历过 node *next;四、模块划分 node* creategraph()/建立邻接表，完成无向图的输入;0410213243输入节点数动态分配节点数组内存边边表4.1邻接表的建立void depthfirstsearch(node *list)/深度优先搜索void depthfirstsearch(node *list)cink;ai=klistk.sign=t;i+listk.sign=t k=p-data; 真p=p-next; i+ 非零 零if(listk.sign!=f)结束程序图4.2 深度优先遍历流程图void breadthfirstsearth(node *list)/广度优先搜索breadthfirstsearthth 搜索起始节点cink; listk.sign=t; p=listam.next; 真 if(listk.sign=f)r+; 标记p=p-next;i+程序结束for(int i=1;i=n;i+)/恢复原邻接表 listi.sign=f;表4.3图的广度遍历void pathsearth(node *list)/路径搜索void adjacencylistdelete(node *list)/释放邻接表的空间adjacencylistdelete(list);/释放邻接表空间五、系统的概要设计main() /*包含一些调用和控制语句*/进入菜单选择用户登录图信息的录入路径收索广度优先遍历图深度优先遍历图 退出程序 图5.1系统功能模块图六、部分源程序#define t true#define f false#includestruct node/定义一个结构作为节点类型 int data; bool sign;/标志位,用来标示是否遍历过 node *next;node* creategraph()/建立邻接表，完成无向图的输入 int l,m,n; bool g; coutn; node *adjacencylist=new noden+1;/动态分配节点数组内存 adjacencylist0.data=n;/0地址存放的为节点数 adjacencylist0.next=null; for(int i=1;i=n;i+)/给各顶点域赋初值 adjacencylisti.data=0; adjacencylisti.next=null; adjacencylisti.sign=f;/表示未遍历 cout请依次输入各条边的始点和尾点:（以0表示结束）l; if(l!=0)/判断输入边是否结束 g=t; while(g=t) cinm; if(l0)&(l0)&(mdata=m; p-next=null; if(adjacencylistl.next=null)/为每个节点创建邻接链表 adjacencylistl.next=p; else top=adjacencylistl.next; while(top-next!=null) top=top-next; top-next=p; adjacencylistl.data+;/统计邻接点的个数 q=(node *)new(node);/分配边的另一个顶点内存 q-data=l; q-next=null; if(adjacencylistm.next=null)/构建邻接表 adjacencylistm.next=q; else top=adjacencylistm.next; while(top-next!=null) top=top-next; top-next=q; adjacencylistm.data+;/统计邻接点的个数 else cout边l-m输入错误！l; if(l=0)/边的输入结束 g=f; return adjacencylist;/返回邻接表;void depthfirstsearch(node *list)/深度优先搜索 int m,n=list0.data,k,*a=new intn;/设置一个数组用于存放节点 node *p; cout采用深度优先搜索：endl; coutk; for(int i=0;idata; p=p-next; if(listk.sign=f) break; m+; if(listk.sign!=f)/判断是否是p=null跳出while循环的 if(im)/无节点可回溯 cout该图为非连通图!endl; break; else k=ai-m; /回溯 for(i=1;i=n;i+)/恢复原邻接表 listi.sign=f; cout深度优先搜索遍历顺序为:; for(i=0;in;i+)/输出遍历结果 coutai ; coutendl; delete a;/释放动态数组内存;void breadthfirstsearth(node *list)/广度优先搜索 int m,r,k,n=list0.data,*a=new intn+1;/设置数组存放节点 node *p; cout采用广度优先搜索：endl; coutk; a0=n; a1=k; listk.sign=t;/标识遍历的第一个节点 m=0; r=1; while(m!=r) m+; p=listam.next; while(p!=null) k=p-data; if(listk.sign=f) r+; ar=k;/遍历到的节点存入数组 listk.sign=t;/标识已经遍历过的节点 p=p-next; for(int i=1;i=n;i+)/恢复原邻接表 listi.sign=f; cout广度优先搜索遍历顺序为: ; for(i=1;i=n;i+)/输出遍历 coutai ; coutendl; delete a;/释放动态数组内存;void pathsearth(node *list)/路径搜索 int *a,c,d,m,k,n=list0.data; coutk; coutc; coutd; d=d+1; if(dn) cout不存在这样的简单路径！endl; else a=new intd;/动态分配数组内存存放路径上的节点 for(int i=0;id;i+) ai=0; a0=k; node *p; int x; lista0.sign=t; i=1; while(ad-1!=c) while(idata; if(i=d-1&m=a0&a0=c)/路径存在且为回路 cout该路径为一条回路！next; if(p=null) ai=0; i-;/由此节点往下的路径不存在,回溯 listai.sign=f; /还原标识符 if(i=0)/无法回溯,路径不存在,跳出循环 cout不存在这样的简单路径！=0) listai.sign=f;/还原标识符 if(ad-1=c)/判断路径是否找到并输出 cout从节点k到节点c的一条路径为：; for(i=0;id-1;i+)/输出路径 coutai ; coutad-1endl; delete a; for(int i=1;i=n;i+)/恢复原邻接表 listi.sign=f; ;void adjacencylistdelete(node *list)/释放邻接表的空间 node *p,*q; int n=list0.data; for(int i=1;inext; delete p;/释放链表节点空间 p=q; delete list;/释放邻接表空间;void main() node *list; list=creategraph();/以邻接表的形式建立一个无向图 char a,b; cout请选择遍历方法：（d:深度优先搜索;b:广度优先搜索）; for(int i=1;ia; switch(a) case d: case d: depthfirstsearch(list); coutb; if(b=y)|(b=y) breadthfirstsearth(list); break; case b: case b: breadthfirstsearth(list); coutb; if(b=y)|(b=y) depthfirstsearch(list); break; default: cout输入错误！请重新输入！endl; i-; while(1) couta; if(a=y)|(a=y) pathsearth(list); else if(a=n)|(a=n) break; else cout输入错误！endl; adjacencylistdelete(list);/释放邻接表空间七、程序的调试分析以及测试结果7.1程序的调试分析程序的调试是一个很重要的方面，本题目有个创建邻接表函数这是个基础，如果这里出了差错当然后面的模块也就无法进行了。所以在调试程序的时候，我是先进行了对创建邻接表的函数进行调试。再确保无误的情况下在进行了后面模块的调试，在调试中间经常会出现一些小问题，这是我会经常的采用“隔离”的方法进行逐步的排查。最后还得对整个程序进行总体的调试，不断完善一些细节方面，并对输入的参数进行多方面的改变，以确保程序的正确性。在整个程序运行无误的基础上，在尽力对一些函数进行优化，加强程序的可读性，方便性。经过这次课程设计让我收获了不少东西，只要有以下几个方面。1）对于基于c+语言的数据结构，c+语言的掌握情况是能否学好这么课程的一个重要因素，所以在进行课程设计的时候又对c+语言进行了部分复习。2）在调试过程中懂得了，学习的严谨性，特别对于编程题目。“差之毫厘，谬之千里”。当然这也不仅仅在学习方面，生活中也是样。3）在这个项目中也提醒了自己在平时除了自己的专业知识外应该积累更多的知识，技能。只有这样在进行各项事情的过程中才能更加顺利。4）“理论联系实践”，实践是建立在学习的基础之上，而又在其中不断的学习的过程。平时上课听讲觉得容易接受，淡然无味，但在实现算法的时候才发现原来一切并非如此。数据结构这门课程比较抽象而且如果自己只是看看书的话根本就不能够学好的，而且数据结构这门课程也应用的非常广泛，特别是在计算机许多语言中都能够看到数据结构的思想。八、附录5.1、课程设计心得体会 心得体会 通过这近一个星期的数据结构课程设计实践，我学到了很多东西。本次课程设计对我来说正是一个提高自己能力的机会，我好好的抓住机会，努力做好每一步，完善每一步。自己的c语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：1.必须牢固掌握基础