课程设计邻接表副本

1、摘 要 本课程设计主要实现用邻接表存储结构对图进行操作。在课程设计中，程序以邻接表对图进行存储，并利用数组、队列等结构加以辅助存储；最终实现图的建立，图的链表结构的输出，图的深度优先遍历及广度优先遍历。关键字: 图 邻接表 队列 遍历Abstract This curriculum design is designed to achieve operations of graph with adjacency table storage structure.In the curriculum design, the program is stored wiht the adjacency ta

2、ble, and be assisted by arrays, queue, and so on.Finally, to achieve the construction of a graph, output the list structure of the graph, depth-first traversal graph and breadth-first traversal graph.Keyword: Graph Adjacency list Queue Traversal 1.引 言本学期我们学习了很多图的存储结构，有邻接矩阵、邻接表、十字链表等。其中邻接矩阵和邻接表为图的主要存

3、储结构。图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中，是一种静态存储方法。图的邻接表存储结构是一种顺序存储与链式存储相结合的存储方法。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低。 本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现深度优先和广度优先遍历以及其链表结构的输出。 2.需求分析2.1 原理当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点，而这些

4、操作都需要一图的深度优先及广度优先遍历为基础。本系统将构建一个图，图的结点存储的是int型数据。运行本系统可对该图进行链式结构输出、深度优先及广度优先遍历。控制方法如下： 表2-1 控制键的功能 控制键 1 2 3 0 功能 输出链 表结构 深度优 先遍历 广度优 先遍历 退出2.2 要求（1）建立基于邻接表的图；（2）对图进行遍历；（3）输出遍历结果；2.3 运行环境 (1)WINDOWS 7系统 (2)C+ 编译环境2.4 开发工具 C+语言 3.数据结构分析本课程设计是针对于图的，程序中采用邻接表进行数据存储。邻接表是一种顺序存储与链式存储相结合的存储方法，该存储方式在图比较稀疏是相对于

5、图的邻接矩阵存储有明显优势。设计实现了图的邻接表结构输出、深度有新遍历和广度优先遍历操作的实现。 4.算法设计4.1 概要设计（1）首先，要定义头文件，在头文件中定义邻接点point、图的基本结点graph以及在广度优先搜索中会用到队列queue。具体如下：struct point int n; /邻接点的序号point *next; /指向下一条弧节点的地址;struct graphint data; /表接点的数据struct point *f; /结点的指针域，给出自该结点发出的第 一弧节点的地址;struct queueint elemd; /队列的容量int front; /fron

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

7、graph a,int v) 对图进行深度优先遍历。先访问指定的顶点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(

8、queue &Q,int e) e入队列Q的队尾。 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; /

9、标记为已访问 w=v0的第一个邻接点；while(当邻接点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);

10、w=下一个邻接点；/wdv4.3 函数调用图 5.程序实现及测试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）

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

12、一件艰苦的工作，又是一件愉快的事情。编程时如果遇到看似简单但又无法解决的问题，很容易灰心丧气。此时切不可烦躁，一定要冷静的思考，认真的分析，其过程为：面对问题，接受问题，处理问题，解决问题。同时我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样。我觉得作为一名软件工程专业的学生，这次课程设计是很有意义的。更重要的是如何把自己平时所学的东西应用到实际中。虽然自己对于这门课懂的并不多，很多基础的东西都还没有很好的掌握，觉得很难，但是靠着学习和实践，我相信自己一定能做的更好。 7.结束语 经过几天的努力，我的课程设计终于完成

13、了。本课程设计主要运用数据结构知识和C+程序设计完成了用邻接表存储结构实现对图的操作。该系统的主要功能为：图的链式结构输出、深度优先遍历、广度优先遍历。在这次数据结构的课程设计中，曾遇到过一些问题，但是经过查找资料都已经得到解决，所以我认为只要我们有耐心和信心，我们一定能解决问题。再次对给过我帮助的所有同学和各位指导老师表示忠心的感谢！参考文献1 严蔚敏、吴伟民著.数据结构（C语言版）.-北京清华大学出版社2 谭浩强著， C程序设计，-3版，-北京：清华大学出版社3 薛超英著.数据结构（第二版）用Pascal语言、C+语言对照描述算法. -武汉：华中科技大学出版社4 李陶深、赵文静著. 面向对

14、象程序设计与方法. -武汉：武汉理工大学出版社附录1 源程序#include<iostream.h>#define null 0struct pointint n;point *next; /指向下一条弧节点的地址;struct graphint data;struct point *f;const d=100;struct queueint elemd; /队列的容量int front; /front为首指针，指向第一个元素int rear; /rear为最后一个元素，指向队尾元素的下一个位置q;int mark100; /作为标记节点是否被访问struct graph g100

15、;void enqueue(queue &Q,int e);void delqueue(queue &Q,int &e);int queueempty(queue &Q);void creatgraph(int m) /n表示节点的个数/创建图，并用邻接链表来表示它struct point *p,*q;int x;for(int t=1;t<=m;t+) /首先建立邻接表结构 cout<<"请输入"<<t<<"节点的值： "cin>>gt.data; /输入结点的值ma

16、rkt=0; /标记结点为未访问cout<<"请输入"<<t<<"节点的邻接点个数： "cin>>x; /x为邻接点的个数if(x=0)gt.f=null;else for(int i=1;i<=x;i+)p=new point;cout<<"输入第"<<i<<"个邻接点的序号：" cin>>p->n; /输入邻接点的序号if(i=1) gt.f=p; q=p;else q->next=p; q=p;

17、q->next=null;/深度遍历void dpv(struct graph a,int v)/从点v开始进行深度访问struct point *p;cout<<"V"<<v<<"("<<av.data<<") "markv=1; /访问点v，并标记为以访问 p=av.f;while(p!=null)if(markp->n=0)dpv(a,p->n);p=p->next;/广度遍历void wdv(struct graph a,int v,queue

18、 &Q)/从v点开始广度方访问，（a是连通图或是连通分量）struct point *p;int v1; cout<<"V"<<v<<"("<<av.data<<") "markv=1; /访问点v，并标记为以访问enqueue(Q,v);/v进队列while(!queueempty(Q)delqueue(Q,v1);p=av1.f;while(p!=null)if(markp->n=0)cout<<"V"<<p-&g

19、t;n<<"("<<ap->n.data<<") "markp->n=1;enqueue(Q,p->n);p=p->next;/入队列void enqueue(queue &Q,int e)/e入队if(Q.rear+1)%d=Q.front) /对满cout<<"对列已经满!"else Q.elemQ.rear=e; /入对 Q.rear=(Q.rear+1)%d; /对尾指针后移/出对void delqueue(queue &Q,int &am

20、p;e)/对头删除e=Q.elemQ.front; /e出对Q.front=(Q.front+1)%d; /对首指针后移/判断对是否为空int queueempty(queue &Q) if(Q.rear=Q.front) /对空return 1;else return 0;/显示图的链式结构void print(struct graph a,int m)/将图g以链表的形式打印出来,m为结点个数struct point *p;for(int i=1;i<=m;i+)cout<<"V"<<i;p=ai.f;while(p!=null)c

21、out<<"->"cout<<"V"<<p->n;p=p->next;cout<<endl;void main()int s,r=5,v0;cout<<"请输入结点的个数："cin>>s; creatgraph(s); cout<<" * "<<endl; cout<<" * = *"<<endl; cout<<" * * #请选择功能#

22、 * *"<<endl; cout<<" * * 1.显示图的链式结构 * *"<<endl; cout<<" * * 2.深度优先遍历 * *"<<endl; cout<<" * * 3.广度优先遍历 * *"<<endl; cout<<" * * 0.退出系统 * *"<<endl; cout<<" * = *"<<endl; cout<<" * "<<endl; while(r) cout&l