专业课程设计论文图的遍历.doc

内蒙古科技大学本科生课程设计论文题 目：C+课程设计 -图遍历学生姓名：王刚学 号：专 业：计算机09级班 级：（2）班指引教师：丁雨 6月13日6月24日内蒙古科技大学课程设计任务书课程名称数据构造课程设计设计题目图遍历指引教师丁雨时间-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语言版）严蔚敏、吴伟民 主编 清华大学出版社 .112数据构造课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 .23.数据构造:用面向对象办法与C+语言描述，殷人昆 主编，清华大学出版社 .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.必要牢固掌握基本知识。由于C语言是大一所学知识，有所遗忘，且未掌握好上学期所学数据构造这门课，因此在实践之初感到棘手。不知如何下手，但在日后实习过程中自己通过看书和课外资料，并请教其她同窗，慢慢地对C语言和数据构造知识有所熟悉，这时才逐渐有了思路。因此，这次课程之后，我告诫自己：此后一定要牢固掌握好专业基本知识。2.必要培养严谨态度。自己在编程时经常由于某些类似于“少了分号”小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨事情，容不得马虎。因此在此后自己一定要培养严谨态度。我想这不但是对于程序设计，做任何事都应如此。3.这次课程设计也让我充分结识到数据构造这门课重要性。它给咱们一种思想和大纲，让咱们在编程时容易找到思路，不至于无章可循。同步它也有广泛实际应用。在实践过程中，我和成员分工合伙，敢于提出问题，解决难题，在实践中，我遇到了许多困难，但都一一克服了。最后我圆满完毕本次课程设计，学到了诸多东西。同步，程序还存在着某些缺陷，就是不能输出原图，存在某些局限性，但是我会继续努力思考，完善程序，做到最佳。 本次实验，教师对我指引是至关重要，在此我非常感谢教师，从她那我学到了诸多关于c语言知识，为后来学习打下了一定基本。 总来说，本次课程设计，不但我知识面有所提高，此外我综合素质也有所提高，例如说：团队精神、提问能力、思考能力等等。这次课程设计为我后来更好学习和使用c语言打下了基本。参照文献1数据构造 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 .112数据构造课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 .23.数据构造:用面向对象办法与C+语言描述，殷人昆 主编，清华大学出版社 .6