数据结构_图的数据结构_课程设计

数据结构课程设计本课程设计已调试通过，请放心使用。请到：道客巴巴或豆丁网充值购买word版，省打字，直接修改即可，价格较便宜，在这里百度较贵！搜索：数据结构_图的数据结构_课程设计

设计题目：图的遍历与存储

课题名称图的遍历与存储院系年级专业学号姓名成绩

课题设计目的与设计意义1、课题设计目的：(1).掌握对图的遍历和存储。(2).这次的课程设计在另一方面也培养了一种团队协作的精神，各个小组的成员之间可以相互给意见，相互帮助。2、课题设计意义：(1).通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才是真正的知识，才能提高自己的实际动手能力和独立思考的能力。(2).在设计的过程遇到了各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计，把以前所学过的知识重新温故，巩固了所学的知识。当然，这也让我对图的遍历和存储有了更为深刻的了解和应用。指导教师：

年月日

前言本课程设计涉及的主要内容是对图进行一些存储和遍历的操作，在课程设计中，系统开发平台为Windows2000，程序设计语言采用VisualC++，程序运行平台为Windows98/2000/XP。用邻接表存储结构和邻接矩阵存储结构在图中对图进行一些存储操作以及对图进行深度优先及广度优先遍历。程序通过调试运行，实现了设计的目标。本学期我们学了很多关于的图的存储结构，邻接矩阵，邻接表，还有十字链表等。其中邻接矩阵和邻接表为图的主要存储结构。对于邻接矩阵的存储结构来说，它是表示顶点之间相邻关系的矩阵，它是把图的边信息储存在一个矩阵中，是一种静态存储方法，值得注意的是，一个图的邻接矩阵的表示是唯一的，但是邻接表的表示却不一定是唯一的，这是因为邻接表表示中，各边表结点的链接次序取决于建立邻接表的算

法以及边的输入次序。对于邻接表的存储结构来说，这种表示法类似于树的孩子链表表示法，既储存顶点的信息，也储存相关边的信息，是一种链式存储和顺序存储相结合的存储方法。二者存储方法各有利弊，具体应用时，要根据图的稠密和稀疏程度以及问题需求进行选择。从空间上说，图越稀疏，邻接表的空间利用效率越高。从时间性能上说，邻接表在图的算法中时间代价较邻接矩阵要低。图是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学，计算机科学等领域中，图结构有着广泛的应用。因此本课程设计主要是实现使用邻接表和邻接矩阵存储结构存储一个图，以及对图实现深度优先遍历和广度优先遍历。当然，图也分为4种非线性结构，像无向图，无向网，有向图，有向网，这些图都可以分别进行遍历和存储。本程序主要是由C语言辅助完成，在VisualC++6.0平台实现的，我们大一的时

候学过C语言的，对C语言有着一定的熟练度，有因为有VisualC++6.0这个较好的平台，自己的电脑上也安装了这个系统软件，因此我使用了C语言进行了对图的操作。龚小雨2012年12月12日

目录第1章设计要求...................................................................................................................11.1设计的目的与意义...................................................................................................11.2问题描述...................................................................................................................11.3需求分析...................................................................................................................11.4算法思想...................................................................................................................2第2章概要设计...................................................................................................................32.1主界面设计...............................................................................................................32.2系统功能设计...........................................................................................................3第3章模块设计...................................................................................................................3

3.1系统功能模块图.......................................................................................................33.2程序流程图（以无向图为例）...............................................................................43.3图的两种存储结构...................................................................................................83.3.1邻接矩阵表示法............................................................................................83.3.2邻接表表示法................................................................................................83.4系统子程序及功能设计...........................................................................................9第4章详细设计...................................................................................................................94.1数据类型定义...........................................................................................................94.2系统主要子程序详细设计.....................................................................................10第5章测试分析...............................................................................................................135.1系统主界面入下图所示.........................................................................................135.2各子功能测试运行结果如下：.............................................................................13

第6章心得体会.................................................................................................................18第7章源程序（无向图）.................................................................................................19第8章用户手册...............................................................................................................27第9章参考文献...............................................................................................................27

1

第1章设计要求1.1设计的目的与意义1.1.1课题设计目的：(1).根据课堂讲授内容，学生做相应的自主练习，消化课堂所讲解的内容。通过过调试典型例题或习题积累调试C程序的经验，通过完成辅导教材中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力。(2).当然，通过对图的遍历和存储，我真真实实的对图的基本运算有了一些深刻的了解，我了解了遍历分为深度遍历和广度遍历，也了解图可以分为邻接表和邻接矩阵进行存储等等...(3).还有，这次的课程设计在另一方面也培养了一种团队协作的精神，各个小组的成员之间可以相互给意见，相互帮助，以便更好的完成老师给予的要求。1.1.2课题设计意义：

(1).通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才是真正的知识，才能提高自己的实际动手能力和独立思考的能力。(2).在设计的过程遇到了各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计，把以前所学过的知识重新温故，巩固了所学的知识。当然，这也让我对图的遍历和存储有了更为深刻的了解和应用。(3).我也觉得这是对自己能力的一种检测，毕竟学了一学期的数据结构和C语言，通过这次的课程设计，让我更好的对自己的编程和思想方面有了深刻的认识。1.2问题描述

设计一个对图进行遍历和存储的程序，为来访的客人提供对图操作的服务。1.3需求分析1.3.1运行环境硬件：计算机486/64M以上操作系统：WIN9x以上/WIN2000/WINXP/WINME相关软件：VistualC++6.01.3.2程序所实现的功能(1).在主函数中设置了一个菜单，通过菜单实现对无向图，无向网，有向图，有向网进行所需要的一些操作。

2

(2).在此程序中，有一些关于队列的函数，主要的是入队和出队两个函数，这是为了对邻接矩阵和邻接表进行广度优先遍历而服务的，通过让顶点入队和出队，以便得到对图进行广度优先遍历后的结果。(3).输入顶点的信息和边的数目，可以对无向图进行邻接矩阵和邻接表的建立和输出，以及对其进行深度优先遍历和广度优先遍历。(4).在键盘上输入顶点的信息和边的数目，可以对有向图进行邻接矩阵和邻接表的建立和输出，以及对其进行深度优先遍历和广度优先遍历。(5).由顶点的信息和边的数目，可以对无向网进行邻接矩阵的建立和输出，以及对其进行深度优先遍历和广度优先遍历。(6).输入顶点的信息和边的数目，可以对有向网进行邻接矩阵的建立和输出，以及对其进行深度优先遍历和广度优先遍历。(7).可以通过改变无向网，有向网的权值大小，可以实现对不同数据得到自己所需要

的结果。1.3.3程序的输入，包含输入的数据格式和说明(1).输入顶点数,及各顶点信息(数据格式为字符型)(2).输入边数,及权值(数据格式为字符型)1.3.4程序的输出，程序输出的形式(1).输出有向图的邻接表、邻接矩阵、深度优先遍历结果、广度优先遍历结果。(2).输出无向图的邻接表、邻接矩阵、深度优先遍历结果、广度优先遍历结果。(3).输出有向网的邻接矩阵、深度优先遍历结果、广度优先遍历结果。(4).输出无向网的邻接矩阵、深度优先遍历结果、广度优先遍历结果。1.4算法思想

本课题本人所采用的是邻接矩阵和邻接表的方式存储图，，实现图的深度、广度两种遍历，并将每种遍历结果输出来。1.4.1图的邻接矩阵和邻接表的建立对任意给定的图（顶点数和边数自定），根据邻接矩阵和邻接表的存储结构建立图的邻接矩阵和邻接表。1.4.2图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则可以采用递归算法来实现。

3

第2章概要设计2.1主界面设计为了实现对图进行遍历和存储，我设计了一个含有多个菜单项的主控菜单来控制各个函数实现各自的功能，方便用户使用本系统。

2.2系统功能设计为了实现对图的便利和存储，我设计了四个主要的功能菜单，每个菜单中又包含字菜单，以控制调用各个函数。依次读入图的顶点个数和边的个数。四个主功能菜单的描述如下。(1).无向图和无向网对于无向图，传入顶点的个数和边的个数，对它的邻接矩阵和邻接表建立，可以输出两种存储结构，对其进行深度遍历和广度遍历。对于无向网，只需要再输入它的权值，其余的操作时一样的。(2).有向图和有向网对于有向图，传入顶点的个数和边的个数，对它的邻接矩阵和邻接表建立，可以输出两种存储结构，对其进行深度遍历和广度遍历。对于有向网，只需要再输入它的

权值，但对邻接表则不需要输入权值。第3章模块设计3.1系统功能模块图总模块划分：

43.2程序流程图（以无向图为例）（1）邻接矩阵建立流程图(如图所示)（2）邻接表建立流程图(如图示)

用户登入信息输入菜单选择

无向网无向图有向网有向图邻接矩阵邻接矩阵邻接表邻接矩阵邻接表邻接矩阵

深度优先遍历图广度优先遍历图深度优先遍历图深度优先遍历图广度优先遍历图广度优先遍历图深度优先遍历广度优先遍历深度优先遍历广度优先遍历深度优先遍历广度优先遍历

5

(3)邻接矩阵输出流程图（如图所示）(4)邻接表输出流程图（如图所示）是否小于顶点数print_juzhe(graphga)输出顶点信息与

ga->arcs[i][j]结束yN

输入顶点个数creat_ljbiao(topnodegl[],intn,inte)输入两个顶点之间的关系建立一个空间个pp->adjvex=jp->next=gl[i].linkgl[i].link=p顶点信息输入creat_juzhe(graphga)顶点信息输入输入两个顶点之间的关系输入顶点个数ga->arcs[i][j]=1ga->arcs[i][j]=1

是否小于顶点数print_ljbiao(topnodegl[],intn)输出顶点的信息与gl[i].topvex结束yN

6

(5)邻接矩阵的深度优先遍历如图所示:输出ga->vexs[i]

ga->arcs[i][j]==1&&!visited[j]DFS(ga,i)j=0jvexnumj++visited[i]=1

结束程序

DFS(graphga,inti)

7

(6)邻接矩阵的广度优先遍历(如图所示)BFS(graphga,intk)setnull(&Q)输出ga->vexs[k]visited[i]=1

enqueue(&Q,k)!empty(&Q)i=dequeue(&Q)j=0

ga->vexs[i][j]==1&&!visited[j]输出ga->vexs[j]visited[j]=1enqueue(&Q,j)jvexnumj++结束程序

8

3.3图的两种存储结构3.3.1邻接矩阵表示法设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]。

（1）无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。（2）在有向图中,统计第i行1的个数可得顶点i的出度，统计第j行1的个数可得顶点j的入度。在无向图中,统计第i行(列)1的个数可得顶点i的出度和入度。3.3.2邻接表表示法

在无向图的邻接表中，顶点vi的度等于第i个链表中的结点数；在有向图的邻接表中，顶点vi的出度等于第i个链表中的结点数，求入度必须遍历整个邻接表，为便

9

于求vi的入度需建立有向图的逆邻接表（是以顶点vi为头的弧所建立的邻接表）。3.4系统子程序及功能设计本系统共设置了16个子程序，各子程序的函数及功能说明如下。（1）voidsetnull(linkqueueq)//建立一个空队列（2）intempty(linkqueueq)//判断队列是否为空（3）voidenqueue(linkqueueq,datatypex)//让元素入栈（4）intdequeue(linkqueueq)//让元素出栈（5）voidcreat_juzhe(graphga)//无向图邻接矩阵的建立

（6）voidprint_juzhe(graphga)//邻接矩阵的输出（7）voidcreat_ljbiao(topnodegl[],intn,inte)//无向图邻接表的建立（8）voidprint_ljbiao(topnodegl[],intn)//邻接表的输出（9）voidcreat_juzhew(graphga)//无向网邻接矩阵的建立（10）voidDFSL(topnodegl[],inti)//邻接表的深度遍历（11）voidDFS(graphga,inti)//邻接矩阵的深度遍历（12）voidBFSL(topnodegl[],intk)//邻接表的广度遍历（13）voidBFS(graphga,intk)//邻接矩阵的广度遍历（14）voidcreat_yjuzhe(graphga)//有向图邻接矩阵的建立（15）voidcreat_yljbiao(topnodegl[],intn,inte)//有向图邻接表的建立（16）voidcreat_ywjuzhe(graphga)//有向网邻接矩阵的建立

第4章详细设计4.1数据类型定义4.1.1无向图和有向图的定义typedefstruct{charvexs[maxsize];//邻接矩阵的顶点信息intarcs[maxsize][maxsize];//邻接矩阵边的信息intvexnum,arcnum;//邻接矩阵的顶点数和边数}graph;

10

graphga;typedefstructnode{intadjvex;//邻接点域structnodenext;//链域}edgenode;//边表结点typedefstruct{vextypetopvex;//顶点信息edgenodelink;//边表头指针}topnode;//顶点表结点topnodegl[20];

4.1.2链队列的定义typedefstructpnode{datatypedata;//定义链表的数据域structpnodenext;//定义链表的指针域}linklist;typedefstruct{linklistfront,rear;//用linklist类型定义队头和队尾}linkqueue;linkqueueq;//q是链队列指针4.1.3全局变量定义

#definemaxsize64//邻接矩阵的行或列的最大长度linkqueueq;//q是链队列指针intvexnum,arcnum;//邻接矩阵的顶点数和边数graphga;topnodegl[20];intvisited_lj[20]={0};intvisited[20]={0};intvisited_ljb[20]={0};intvisited_jz[20]={0};4.2系统主要子程序详细设计

4.2.1主程序函数

11

主函数，控制菜单的选择，调用工作区模块函数。voidmain(){printf("\n---------------------------欢迎使用图的遍历与存储-------------------------------\n");while(i){printf("\t\t\t菜单选择如下\n\n");printf("\t\t\t\t0:无向图\n");printf("\t\t\t\t1:无向网\n");printf("\t\t\t\t2:有向图\n");printf("\t\t\t\t3:有向网\n\n");

printf("\n--------------------------------------------------------------------------------\n");printf("请输入要进行的项目的序号:")scanf("%d",&i);}4.2.2用户工作区子程序主要工作函数，让用户对图进行相应的操作。（1）无向图的模块设计switch(k){case0:printf("请输入顶点数和边数:");scanf("%d%d",&ga.vexnum,&ga.arcnum);

creat_juzhe(&ga);break;case1:printf("请输入顶点数和边数:");scanf("%d%d",&n,&e);creat_ljbiao(&gl,n,e);break;case2:print_juzhe(&ga);break;case3:print_ljbiao(&gl,n);break;case4:printf("请输入要遍历的起始位置:");scanf("%d",&j);printf("邻接矩阵深度遍历后的结果为:");DFS(&ga,j);break;case5:printf("请输入要遍历的起始位置:");scanf("%d",&j);printf("邻接表深度遍历后的结果为:");DFSL(&gl,j);break;case6:printf("请输入要遍历的起始位置:");scanf("%d",&j);printf("邻接矩阵广度遍历后的结果为:");BFS(&ga,j);break;

12

case7:printf("请输入要遍历的起始位置:");scanf("%d",&j);printf("邻接表广度遍历后的结果为:");BFSL(&gl,j);break;}printf("\n\t\t\t\t0:结束\n\t\t\t\t1:继续\n");printf("请输入---0---或---1---:");scanf("%d",&k);4.2.3无向网的模块设计switch(m){case0:printf("请输入顶点数和边数:");scanf("%d%d",&ga.vexnum,&ga.arcnum);creat_juzhew(&ga);break;case1:print_juzhe(&ga);break;case2:printf("请输入要遍历的起始位置:");scanf("%d",&m);printf("邻接矩阵深度遍历后的结果为:");DFS(&ga,m);break;

case3:printf("请输入要遍历的起始位置:");scanf("%d",&m);printf("邻接矩阵广度遍历后的结果为:");BFS(&ga,m);break;}4.2.4有向图的模块设计switch(k){case0:printf("请输入顶点数和边数:");scanf("%d%d",&ga.vexnum,&ga.arcnum);creat_yjuzhe(&ga);break;case1:printf("请输入顶点数和边数:");scanf("%d%d",&n,&e);creat_yljbiao(&gl,n,e);break;case2:print_juzhe(&ga);break;

case3:print_ljbiao(&gl,n);break;case4:printf("请输入要遍历的起始位置:");scanf("%d",&l);printf("邻接矩阵深度遍历后的结果为:");DFS(&ga,l);break;case5:printf("请输入要遍历的起始位置:");scanf("%d",&l);printf("邻接表深度遍历后的结果为:");DFSL(&gl,l);break;case6:printf("请输入要遍历的起始位置:");scanf("%d",&l);printf("邻接矩阵广度遍历后的结果为:");BFS(&ga,l);break;case7:printf("请输入要遍历的起始位置:");scanf("%d",&l);printf("邻接表广度遍历后的结果为:");BFSL(&gl,l);break;4.2.5有向网的模块设计switch(m){

13

case0:printf("请输入顶点数和边数:");scanf("%d%d",&ga.vexnum,&ga.arcnum);creat_yjuzhew(&ga);break;case1:print_juzhe(&ga);break;case2:printf("请输入要遍历的起始位置:");scanf("%d",&t);printf("邻接矩阵深度遍历后的结果为:");DFS(&ga,t);break;case3:printf("请输入要遍历的起始位置:");scanf("%d",&t);printf("邻接矩阵广度遍历后的结果为:");BFS(&ga,t);break;}第5章测试分析5.1系统主界面入下图所示：

图1图的遍历与存储主菜单5.2各子功能测试运行结果如下：5.2.1无向图邻接矩阵的建立与输出首先，在主菜单中用户输入0，然后回车，结果如下图2所示。

图2项目选择接着，用户再输入0，并回车，之后再输入相应的信息，得到结果如下图3所示。

14

图3无向图邻接矩阵建立输入邻接的两个顶点的下标后，用户再输入2，回车，得到的结果如下图4所示。图4无向图邻接矩阵输出结果5.2.2无向图邻接矩阵的深度优先遍历和广度优先遍历在邻接矩阵建好后，用户输入4，回车后，再输入深度遍历的起始位置，如输入1，

得到的结果如下图5所示。图5深度优先遍历结果深度遍历后，输入6，回车后，再输入广度遍历的起始位置，如输入1，得到的结果如下图6所示。

图6广度优先遍历结果5.2.3无向图邻接表的建立和输出在主菜单选择无向图后，用户再输入1，回车后，再输入顶点信息和两个顶点间的关

15

系，得到的结果如下图7所示。图7无向图邻接表建立建好后，用户再输入3，回车后，得到的结果如下图8所示。

图8无向图邻接表输出5.2.4邻接表的深度遍历和广度遍历在邻接表建好后，用户可以输入5，回车后，再输入遍历的起始位置，如输入1，对其进行深度优先遍历，得到的结果如下图9所示。

图9深度优先遍历结果紧接着，用户再输入7，回车后，再输入遍历的起始位置，如输入0，对其进行广度优先遍历后，得到的结果如下图10所示。图10广度优先遍历结果

16

5.2.5无向网邻接矩阵的建立与输出首先，在主菜单中输入1，选择无向网后，用户再输入项目序号0，回车后，再输入顶点信息、边数以及相应的权值，得到的结果如下图11所示。

图11无向网邻接矩阵建立紧接着，用户再输入1，回车后，得到的结果如下图12所示。图12无向网邻接矩阵输出5.2.6有向图邻接矩阵的建立与输出

首先，在主菜单中输入2，选择有向图后，用户再输入项目序号0，回车后，再输入顶点信息和边数，得到的结果如下图13所示。

图13有向图邻接矩阵建立紧接着，用户再输入2，回车后，得到的结果如下图14所示。

17

图14有向图邻接矩阵输出5.2.7有向图邻接表的建立与输出在主菜单选择有向图后，用户再输入1，回车后，再输入顶点信息和两个顶点间的关系以及边数，得到的结果如下图15所示。

图15有向图邻接表建立紧接着，用户再输入3，回车后，得到的结果如下图16所示。图16有向图邻接表输出5.2.8有向网邻接矩阵的建立与输出

首先，在主菜单中输入3，选择有向网后，用户再输入项目序号0，回车后，再输入顶点信息、边数以及相应的权值，得到的结果如下图17所示。

18

图17有向网邻接矩阵建立紧接着，用户再输入1，回车后，得到的结果如下图18所示。图18有向网邻接矩阵输出

第6章心得体会通过这近一个星期的数据结构课程设计实践，我学到了很多东西。本次课程设计对我来说正是一个提高自己能力的机会，我好好的抓住机会，努力做好每一步，完善每一步。自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：（1）一定要会使用word。通过这次的课程设计，我发现自己对word真的很不了解，比如，对一些图形的组合，插入页码，生成目录等，我真的有点茫然了，当然，正是由于这次实践，让我懂得了使用word的重要性，这也会对自己以后写论文有影响，还有毕业后自己去工作也会产生很大的影响的。.（2）要善于去学习新知识。这次的课程设计，大体步骤跟数据库有较大联系，

因为自己对这方面还不是很了解，所以刚开始一点儿也没思路，但在后来的实践过程中自己通过看书和查课外资料，并请教老师和其他同学，这时才逐渐有了思路。所以，这次课程设计之后，我告诫自己：一定要善于去学习新知识。（3）必须培养严谨的态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的态度。我想这不仅是对于程

19

序设计，做任何事都应如此。（4）这次的课程设计让我充分认识到《数据结构》的重要性，它让我们对问题的分析有章可循，让我们知道了它在生活中应用的广泛性。在这次课程设计中，我们小组的成员在一起合作，思考，努力去解决一些困难。尽管，最后，我的课程设计写好了，但依然有很多不足的地方，我会以此为鉴，不断的去努力思考，做到最好。当然，在这次课程设计中，我非常感谢我的老师，她帮助我解决了许多困难，她耐心的教导我，让我对一些知识有了更好的掌握，为我以后的学习打下了坚实的基础。总的来说，通过这次的课程设计，我是收获颇多。一方面，我学会了许多新知识，有了一些经验；另一方面，我在团队合作方面也有了一定的加强，思考问题方面的能

力也有了一定地提升。我相信自己在日后的学习中会做的更好，成长更快。第7章源程序（无向图）#include#includetypedefintdatatype;//datatype可为任何类型，这里假设为inttypedefcharvextype;//顶点的数据类型，vextype可为任何类型，这里假设为char#definemaxsize64//邻接矩阵的行或列的最大长度typedefstructpnode

{datatypedata;//定义链表的数据域structpnodenext;//定义链表的指针域}linklist;typedefstruct{linklistfront,rear;//用linklist类型定义队头和队尾}linkqueue;linkqueueq;//q是链队列指针typedefstruct{charvexs[maxsize];//邻接矩阵的顶点信息

intarcs[maxsize][maxsize];//邻接矩阵边的信息

20

intvexnum,arcnum;//邻接矩阵的顶点数和边数}graph;graphga;typedefstructnode{intadjvex;//邻接点域structnodenext;//链域}edgenode;//边表结点typedefstruct{vextypetopvex;//顶点信息edgenodelink;//边表头指针

}topnode;//顶点表结点topnodegl[20];voidsetnull(linkqueueq)//建立一个空队列{q->front=(linklist)malloc(sizeof(linklist));q->front->next=NULL;q->rear=q->front;}intempty(linkqueueq)//判断队列是否为空{if(q->front==q->rear)return1;

elsereturn0;}voidenqueue(linkqueueq,datatypex)//让元素入栈{q->rear->next=(linklist)malloc(sizeof(linklist));q->rear=q->rear->next;q->rear->data=x;q->rear->next=NULL;}intdequeue(linkqueueq)//让元素出栈{

21

linkqueues;if(empty(q)){printf("队为空!");returnNULL;}else{s=q->front;q->front=q->front->next;free(s);return(q->front->data);

}}voidcreat_juzhe(graphga)//无向图邻接矩阵的建立{inti,j,k;getchar();printf("请输入%d个元素:",ga->vexnum);for(i=0;ivexnum;i++)scanf("%c",&ga->vexs[i]);for(i=0;ivexnum;i++)for(j=0;jvexnum;j++)ga->arcs[i][j]=0;

printf("请输入邻接的俩个顶点的下标:\n");for(k=0;karcnum;k++){scanf("%d%d",&i,&j);ga->arcs[i][j]=1;ga->arcs[j][i]=1;}}voidprint_juzhe(graphga)//邻接矩阵的输出{inti,j;printf("建立好后的邻接矩阵为:\n");

22

for(i=0;ivexnum;i++){printf("%c\t",ga->vexs[i]);for(j=0;jvexnum;j++)printf("%d\t",ga->arcs[i][j]);printf("\n");}}voidcreat_ljbiao(topnodegl[],intn,inte)//无向图邻接表的建立{inti,j,k;edgenodep;

getchar();printf("请输入%d个顶点的元素:",n);for(i=0;i
p->adjvex=j;p->next=gl[i].link;gl[i].link=p;p=(edgenode)malloc(sizeof(edgenode));p->adjvex=i;p->next=gl[j].link;gl[j].link=p;}}voidprint_ljbiao(topnodegl[],intn)//邻接表的输出{inti;

23

edgenodep;printf("建立后的邻接表为:\n");for(i=0;iadjvex);p=p->next;}printf("\n");

}}intvisited_lj[20]={0};voidDFSL(topnodegl[],inti)//邻接表的深度遍历{edgenodep;printf("%c",gl[i].topvex);visited_lj[i]=1;p=gl[i].link;while(p!=NULL){if(visited_lj[p->adjvex]==0)DFSL(gl,p->adjvex);

p=p->next;}}intvisited[20]={0};voidDFS(graphga,inti)//邻接矩阵的深度遍历{intj;printf("%c",ga->vexs[i]);visited[i]=1;for(j=0;jvexnum;j++)if((ga->arcs[i][j]!=0)&&(visited[j]==0))

24

DFS(ga,j);}intvisited_ljb[20]={0};voidBFSL(topnodegl[],intk)//邻接表的广度遍历{inti;edgenodep;linkqueueQ;setnull(&Q);printf("%c",gl[k].topvex);visited_ljb[k]=1;enqueue(&Q,k);

while(!empty(&Q)){i=dequeue(&Q);p=gl[i].link;while(p!=NULL){if(!visited_ljb[p->adjvex]){printf("%c",gl[p->adjvex].topvex);visited_ljb[p->adjvex]=1;enqueue(&Q,p->adjvex);}

p=p->next;}}}intvisited_jz[20]={0};voidBFS(graphga,intk)//邻接矩阵的广度遍历{inti,j;linkqueueQ;setnull(&Q);printf("%c",ga->vexs[k]);visited_jz[k]=1;

25

enqueue(&Q,k);while(!empty(&Q)){i=dequeue(&Q);for(j=0;jvexnum;j++)if((ga->arcs[i][j]!=0)&&(!visited_jz[j])){printf("%c",ga->vexs[j]);visited_jz[j]=1;enqueue(&Q,j);}}

}voidmain(){inti=1,j,n,e;intk=1,m=1,l=1,t=1;graphga;topnodegl;printf("\n---------------------------欢迎使用图的遍历与存储-------------------------------\n");while(i){printf("\t\t\t菜单选择如下\n\n");

printf("\t\t\t\t0:无向图\n");printf("\t\t\t\t1:无向网\n");printf("\t\t\t\t2:有向图\n");printf("\t\t\t\t3:有向网\n\n");printf("\n--------------------------------------------------------------------------------\n");printf("请输入要进行的项目的序号:");scanf("%d",&i);switch(i){case0://无向图的基本运算

26

while(k){printf("\n\t0:无向图邻接矩阵的建立\t\t\t1:无向图邻接表的建立\n\t2:邻接矩阵的输出\t\t\t3:邻接表的输出\n\t4:邻接矩阵的深度遍历\t\t\t5:邻接表的深度遍历\n\t6:邻接矩阵的广度遍历\t\t\t7:邻接表的广度遍历\n");printf("\n请输入要进行的项目的序号:");scanf("%d",&k);switch(k){case0:printf("请输入顶点数和边数:");scanf("%d%d",&ga.vexnum,&ga.arcnum);

creat_juzhe(&ga);break;case1:printf("请输入顶点数和边数:");scanf("%d%d",&n,&e);creat_ljbiao(&gl,n,e);break;case2:print_juzhe(&ga);break;case3:print_ljbiao(&gl,n);break;case4:printf("请输入要遍历的起始位置:");scanf("%d",&j);

printf("邻接矩阵深度遍历后的结果为:");DFS(&ga,j);break;case5:printf("请输入要遍历的起始位置:");scanf("%d",&j);printf("邻接表深度遍历后的结果为:");DFSL(&gl,j);break;case6:printf("请输入要遍历的起始位置:");scanf("%d",&j);printf("邻接矩阵广度遍历后的结果为:");BFS(&ga,j);

27

break;case7:printf("请输入要遍历的起始位置:");scanf("%d",&j);printf("邻接表广度遍历后的结果为:");BFSL(&gl,j);break;}printf("\n\t\t\t\t0:结束\n\t\t\t\t1:继续\n");printf("请输入---0---或---1---:");scanf("%d",&k);}

第8章用户手册1.本程序执行文件为：邻接图1.exe。2．进入本系统之后，随即显示系统主菜单界面。用户可在该界面下输入各子菜单前对应的数字并按回车，执行相应子菜单命令。3．进行图的遍历与存储，都要通过输入顶点的信息以及边数，两个顶点间的信息用空格隔开，请用户进入主界面后，按照相关提示进行相应的操作，这样方便用户得到自己需要的信息。第9章参考文献[1]严蔚敏，吴伟民.数据结构（c语言版）.北京：清华大学出版社.2009

[2]谭浩强.c语言程序设计教程.北京：高等教育出版社.2007[3]徐孝凯，贺桂英.数据结构（c语言描述）.北京：清华大学出版社.2004