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