数据结构课程设计--图的遍历_第1页
数据结构课程设计--图的遍历_第2页
数据结构课程设计--图的遍历_第3页
数据结构课程设计--图的遍历_第4页
数据结构课程设计--图的遍历_第5页
已阅读5页,还剩7页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、精选优质文档-倾情为你奉上 1.引 言 数据结构是计算机科学与技术专业的一门核心专业基础课程,是一门理论性强、思维抽象、难度较大的课程。在软件工程专业的课程体系中起着承上启下的作用,学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。通过本门课程的学习,我们应该能透彻地理解各种数据对象的特点,学会数据的组织方法和实现方法,并进一步培养良好的程序设计能力和解决实际问题的能力。我认为学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题,我们应该能从中抽象出一个适当的数学模型,该数学模型在计算机内部用相应的数据结构来表示,然后设计一个解此数学模型的算法,再进行编程调试,最后

2、获得问题的解答。 图是一种非常重要的数据结构,在数据结构中也占着相当大的比重。这个学期的数据结构课程中,我们学习了很多图的存储结构,有邻接矩阵、邻接表、十字链表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中,是一种静态存储方法。图的邻接表存储结构是一种顺序存储与链式存储相结合的存储方法。从空间性能上说,图越稀疏邻接表的空间效率相应的越高。从时间性能上来说,邻接表在图的算法中时间代价较邻接矩阵要低。 本课程设计主要是实现使用邻接表存储结构存储一个图,并在所存储的图中实现深度优先和广度优先遍历以及其链表结构的输出。 2.需求分析2.1 原理

3、当图比较稀疏时,邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后,我们有时还需要对图进行一些操作,如需要添加一个顶点,修改一个顶点,或者删除一个顶点,而这些操作都需要一图的深度优先及广度优先遍历为基础。本系统将构建一个图,图的结点存储的是int型数据。运行本系统可对该图进行链式结构输出、深度优先及广度优先遍历。控制方法如下: 表2-1 控制键的功能 控制键 1 2 3 0 功能 输出链 表结构 深度优 先遍历 广度优 先遍历 退出2.2 要求(1)建立基于邻接表的图;(2)对图进行遍历;(3)输出遍历结果;2.3 运行环境 (1)WINDOWS 7系统

4、(2)C+ 编译环境2.4 开发工具C+语言 3.数据结构分析本课程设计是针对于图的,程序中采用邻接表进行数据存储。在计算机科学中,邻接表描述一种紧密相关的数据结构,用于表征图。在 邻接表的表示中,对于图中的每个顶点,我们将保存所有其它与之相连的顶点(即 “邻接表”)。 邻接表是一种顺序存储与链式存储相结合的存储方法,该存储方式在图比较稀疏是相对于图的邻接矩阵存储有明显优势。设计实现了图的邻接表结构输出、深度有新遍历和广度优先遍历操作的实现。邻接表的结构:(1) 、头结点结构firstarcdata Firstarc:结点的指针域(2) 、邻接点的结构nextarcadjvex Adjvex:

5、邻接点的数据域; Nextarc:邻接点的指针域,指向下一个邻接点;在该程序中,除了邻接表结构以外,还有到了一个mark数组,它是用来标记结点Vi是否被访问。若Vi被访问,则marki=1,否则为0;它是一个比较简单的一维数组。(注:在每次对图进行遍历之前mark都会被清零)图的深度优先访问:从图中每个顶点V出发,访问此顶点,然后依次从V的未访问邻接点出发深度优先遍历图,直至所有与V有通路的顶点被访问,否则选择另外未访问点作为起点,重复上述过程。图的广度优先遍历:从图中每个顶点V出发,访问此顶点,然后依次访问V的未访问邻接点,并保证先被访问的结点的邻接点先于后被访问的结点,直至所有与V有通路的

6、顶点被访问,否则选择另外未访问点作为起点,重复上述过程。 4.算法设计(1)首先,要定义头文件,在头文件中定义邻接点point、图的基本结点graph以及在广度优先搜索中会用到队列queue。具体如下:struct point int n; /邻接点的序号point *next; /指向下一条弧节点的地址;struct graphint data; /表接点的数据struct point *f; /结点的指针域,给出自该结点发出的第 一弧节点的地址;struct queueint elemd; /队列的容量int front; /front为首指针,指向第一个元素int rear; /rear

7、为最后一个元素,指向队尾元素的下一个位置q; 其次,在头文件中还需定义邻接表存储结构下图的抽象数据类型定义。 (2)编写源文件,进行图的初始化,首先要输入顶点信息,初始化顶点表,在输入点v的值时,同时构造v的邻接点。输入邻接点的序号,最后生成一个邻接点链表。子函数功能:1.void creatgraph(int m) /n表示节点的个数 构造图的链表结构,在此函数中要输入图结点的值,邻接点的序号。2.void print(struct graph a,int m) 将图a的链表结构打印出来,m为结点个数3.void dpv(struct graph a,int v) 对图进行深度优先遍历。先访

8、问指定的顶点v,从该顶点的未被访问的邻接点中选取一个顶点p,从p出发进行深度优先遍历。重复以上的步骤,直至图中所有和v有路径相通的顶点都被访问到。4.void wdv(struct graph a,int v,queue &Q) 从v点开始广度优先遍历a是连通图或是连通分量),先访问顶点v,依次访问v的各个未被访问的邻接点v1,v2,vk,分别从,v1,v2,vk出发依次访问它们未被访问的邻接点,并使“先被访问顶点的邻接点”先于“后被访问的顶点”被访问,直至图中所有与顶点v有路径相通的顶点都被访问到。5.void enqueue(queue &Q,int e) e入队列Q的队尾

9、。 6.void delqueue(queue &Q,int &e) 删除队列Q的对首元素。7.int queueempty(queue &Q) 判断队列Q是否为空。(3)编写主函数。用数组存放图结点。输入所要进行的操作的序号,并设置每次只能选择一种功能,调用相应的函数,输出相应的结果。4.2 主要模块的算法描述(1)、深度优先遍历算法,利用递归void dpv(graph a,vtxptr v0) /从点v开始进行深度访问 /a为连通图或非连通图的一个连通分量visit(v0); /访问v结点markv0=1; /标记为已访问 w=v0的第一个邻接点;while(当邻

10、接点w存在时1)if(w未访问)dpv(a,w);w=下一个邻接点;/dpv(2)、广度优先遍历算法,利用队列先入先出void wdv(graph a,vtxptr v)/从v点开始广度优先,a是连通图或是连通分量visit(v); /访问点vmarkv=1; /并标记为以访问 initqueue(Q);enqueue(Q,v);/v进队列while(!queueempty(Q)delqueue(Q,v1);w=v1的第一个邻接点;while(当邻接点w存在时)if(w为访问)visit(w); markw=1; enqueue(Q,w);w=下一个邻接点; /wdv4.3 函数调用图 5.程

11、序实现及测试5.1 创建工程并建立文件(1)启动Microsoft Visual C+ 6.0。(2)新建工程名为“课程设计” 的Win32控制台应用程序。(3)建立头文件“邻接表.cpp”,在其中定义图的创建函数creategraph()、深度优先遍历的函数dpv()、广度优先遍历的函数wdv()、输出函数print()以及main(),通过main()调用其他函数来实现对图的操作。5.2 测试及运行状况(1) 、创建用户所给图的存储结构,邻接表存储。主函数main()会调用函数creategraph ( );假如图为下示: V1(12) V2(45) V4(15)V3(37) V5(26)

12、 (2) 、在选项中选择1,进行显示图的链式结构的操作;(3) 、选择2进行深度优先遍历,并输出结果;(4) 、选择3进行广度优先遍历,并输出结果(5) 、选择0退出系统;(6) 、当用户选择的选项不存在时,系统会提示重新选择;(7) 、当进行遍历时,选择的初始结点不存在,系统会提醒重新输入开始结点以便继续遍历;上述就是对该系统的测试过程。 6. 心得体会在这次数据结构设计中遇到了很多实际性的问题,在实际设计中才发现,书本上理论性的东西与在实际运用中的还是有一定的出入的,所以有些问题要不断地更正以前的错误思维。通过这次设计,我知道编写程序既是一件艰苦的工作,又是一件愉快的事情。编程时如果遇到看

13、似简单但又无法解决的问题,很容易灰心丧气。此时切不可烦躁,一定要冷静的思考,认真的分析,其过程为:面对问题,接受问题,处理问题,解决问题。同时我懂得了学习的重要性,了解到理论知识与实践相结合的重要意义,学会了坚持、耐心和努力,这将为自己今后的学习和工作做出了最好的榜样。我觉得作为一名软件工程专业的学生,这次课程设计是很有意义的。更重要的是如何把自己平时所学的东西应用到实际中。虽然自己对于这门课懂的并不多,很多基础的东西都还没有很好的掌握,觉得很难,但是靠着学习和实践,我相信自己一定能做的更好。 7.结束语 经过几天的努力,黄天不负苦心人,我的课程设计终于完成了。本课程设计主要运用数据结构知识和C+程序设计完成了用邻接表存储结构实现对图的操作。该系统的主要功能为:图的链式结构输出、深度优先遍历、广度优先遍历。 在这次数据结构的课程设计中,曾遇到过一些问题,但是经过查找资料都已经得到解决,也正是因为这些问题引发的思考给我带了收获。所以我认为只要我们有耐心和信心,我们一定能解决问题。再次

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论