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

武汉理工大学《数据结构》课程设计11.引言数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。在软件工程专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力。我认为学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，我们应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。图是一种非常重要的数据结构，在《数据结构》中也占着相当大的比重。这个学期的数据结构课程中，我们学习了很多图的存储结构，有邻接矩阵、邻接表、十字链表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中，是一种静态存储方法。图的邻接表存储结构是一种顺序存储与链式存储相结合的存储方法。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低。本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现深度优先和广度优先遍历以及其链表结构的输出。2.需求分析2.1原理当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点，而这些操作都需要一图的深度优先及广度优先遍历为基础。本系统将构建一个图，图的结点存储的是int型数据。运行本系统可对该图进行链式结构输出、深度优先及广度优先遍历。控制方法如下：表2-1控制键的功能控制键1230功能输出链表结构深度优先遍历广度优先遍历退出武汉理工大学《数据结构》课程设计22.2要求（1）建立基于邻接表的图；（2）对图进行遍历；（3）输出遍历结果；2.3运行环境(1)WINDOWS7系统(2)C++编译环境2.4开发工具C++语言3.数据结构分析本课程设计是针对于图的，程序中采用邻接表进行数据存储。在计算机科学中，邻接表描述一种紧密相关的数据结构，用于表征图。在邻接表的表示中，对于图中的每个顶点，我们将保存所有其它与之相连的顶点（即“邻接表”）。邻接表是一种顺序存储与链式存储相结合的存储方法，该存储方式在图比较稀疏是相对于图的邻接矩阵存储有明显优势。设计实现了图的邻接表结构输出、深度有新遍历和广度优先遍历操作的实现。邻接表的结构：（1）、头结点结构Firstarc：结点的指针域（2）、邻接点的结构Adjvex：邻接点的数据域；Nextarc：邻接点的指针域，指向下一个邻接点；在该程序中，除了邻接表结构以外，还有到了一个mark[]数组，它是用来标记结点Vi是否被访问。若Vi被访问，则mark[i]=1，否则为0；它是一个比较简单的一维数组。（注：在每次对图进行遍历之前mark[]都会被清零）图的深度优先访问：从图中每个顶点V出发，访问此顶点，然后依次从V的未访问邻接点出发深度优先遍历图，直至所有与V有通路的顶点被访问，否则选择另外未访问datafirstarcnextarcadjvex武汉理工大学《数据结构》课程设计3点作为起点，重复上述过程。图的广度优先遍历：从图中每个顶点V出发，访问此顶点，然后依次访问V的未访问邻接点，并保证先被访问的结点的邻接点先于后被访问的结点，直至所有与V有通路的顶点被访问，否则选择另外未访问点作为起点，重复上述过程。4.算法设计（1）首先，要定义头文件，在头文件中定义邻接点point、图的基本结点graph以及在广度优先搜索中会用到队列queue。具体如下：structpoint{intn;//邻接点的序号point*next;//指向下一条弧节点的地址};structgraph{intdata;//表接点的数据structpoint*f;//结点的指针域，给出自该结点发出的第一弧节点的地址};structqueue{intelem[d];//队列的容量intfront;//front为首指针，指向第一个元素intrear;//rear为最后一个元素，指向队尾元素的下一个位置}q;其次，在头文件中还需定义邻接表存储结构下图的抽象数据类型定义。（2）编写源文件，进行图的初始化，首先要输入顶点信息，初始化顶点表，在输入点v的值时，同时构造v的邻接点。输入邻接点的序号，最后生成一个邻接点链表。子函数功能：武汉理工大学《数据结构》课程设计41.voidcreatgraph(intm)//n表示节点的个数构造图的链表结构，在此函数中要输入图结点的值，邻接点的序号。2.voidprint(structgrapha[],intm)将图a的链表结构打印出来,m为结点个数3.voiddpv(structgrapha[],intv)对图进行深度优先遍历。先访问指定的顶点v，从该顶点的未被访问的邻接点中选取一个顶点p,从p出发进行深度优先遍历。重复以上的步骤，直至图中所有和v有路径相通的顶点都被访问到。4.voidwdv(structgrapha[],intv,queue&Q)从v点开始广度优先遍历a是连通图或是连通分量），先访问顶点v，依次访问v的各个未被访问的邻接点v1,v2,…,vk,分别从,v1,v2,…vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问的顶点”被访问，直至图中所有与顶点v有路径相通的顶点都被访问到。5.voidenqueue(queue&Q,inte)e入队列Q的队尾。6.voiddelqueue(queue&Q,int&e)删除队列Q的对首元素。7.intqueueempty(queue&Q)判断队列Q是否为空。（3）编写主函数。用数组存放图结点。输入所要进行的操作的序号，并设置每次只能选择一种功能，调用相应的函数，输出相应的结果。4.2主要模块的算法描述（1）、深度优先遍历算法，利用递归voiddpv(grapha[],vtxptrv0){//从点v开始进行深度访问//a为连通图或非连通图的一个连通分量visit（v0）；//访问v结点mark[v0]=1;//标记为已访问w=v0的第一个邻接点；while(当邻接点w存在时1){if(w未访问)武汉理工大学《数据结构》课程设计5dpv(a,w);w=下一个邻接点；}}//dpv（2）、广度优先遍历算法，利用队列先入先出voidwdv(grapha[],vtxptrv){//从v点开始广度优先，a是连通图或是连通分量visit（v）；//访问点vmark[v]=1;//并标记为以访问initqueue（Q)；enqueue(Q,v);//v进队列while(!queueempty(Q)){delqueue(Q,v1);w=v1的第一个邻接点；while(当邻接点w存在时){if(w为访问){visit（w）；mark[w]=1;enqueue(Q,w);}w=下一个邻接点；}}}//wdv4.3函数调用图武汉理工大学《数据结构》课程设计65.程序实现及测试5.1创建工程并建立文件（1）启动MicrosoftVisualC++6.0。（2）新建工程名为“课程设计”的Win32控制台应用程序。（3）建立头文件“邻接表.cpp”，在其中定义图的创建函数creategraph()、深度优先遍历的函数dpv()、广度优先遍历的函数wdv()、输出函数print（）以及main（），通过main（）调用其他函数来实现对图的操作。5.2测试及运行状况（1）、创建用户所给图的存储结构，邻接表存储。主函数main（）会调用函数creategraph()；假如图为下示：武汉理工大学《数据结构》课程设计7V1（12）V2（45）V4（15）V3（37）V5（26）（2）、在选项中选择1，进行显示图的链式结构的操作；武汉理工大学《数据结构》课程设计8（3）、选择2进行深度优先遍历，并输出结果；（4）、选择3进行广度优先遍历，并输出结果武汉理工大学《数据结构》课程设计9（5）、选择0退出系统；武汉理工大学《数据结构》课程设计10（6）、当用户选择的选项不存在时，系统会提示重新选择；（7）、当进行遍历时，选择的初始结点不存在，系统会提醒重新输入开始结点以便继续遍历；武汉理工大学《数据结构》课程设计11上述就是对该系统的测试过程。6.心得体会在这次数据结构设计中遇到了很多实际性的问题，在实际设计中才发现，书本上理论性的东西与在实际运用中的还是有一定的出入的，所以有些问题要不断地更正以前的错误思维。通过这次设计，我知道编写程序既是一件艰苦的工作，又是一件愉快的事情。编程时如果遇到看似简单但又无法解决的问题，很容易灰心丧气。此时切不可烦躁，一定要冷静的思考，认真的分析，其过程为：面对问题，接受问题，处理问题，解决问题。同时我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样。我觉得作为一名软件工程专业的学生，这次课程设计是很有意义的。更重要的是如何把自己平时所学的东西应用到实际中。虽然自己对于这门课懂的并不多，很多基础的东西都还没有很好的掌握，觉得很难，但是靠着学习和实践，我相信自己一定能做的更好。7.结束语经过几天的努力，黄天不负苦心人，我的课程设计终于完成了。本课程设计主要运用数据结构知识和C++程序设计完成了用邻接表存储结构实现对图的操作。该系统的主要功能为：图的链式结构输出、深度优先遍历、广度优先遍历。在这次数据结构的课程设计中，曾遇到过一些问题，但是经过查找资料都已经得到解决，也正是因为这些问题引发的思考给我带了收获。所以我认为只要我们有耐心和信心，我们一定能解决问题。再次对给过我帮助的所有同学和各位指导老师表示忠心的感谢！没有你们的帮助我想武汉理工大学《数据结构》课程设计12我是不能这么好的完成这项工作的。参考文献[1]严蔚敏、吴伟民著.数据结构（C语言版）.-北京清华大学出版社[2]谭浩强著，C程序设计，-3版，-北京：清华大学出版社[3]薛超英著.数据结构（第二版）—用Pascal语言、C++语言对照描述算法.-武汉：华中科技大学出版社[4]李陶深、赵文静著.面向对象程序设计与方法.-武汉：武汉理工大学出版社