数据结构课程设计-图的遍历和构建(共22页).doc

精选优质文档-倾情为你奉上摘 要图（Graph）是一种复杂的非线性结构。图可以分为无向图、有向图。若将图的每条边都赋上一个权，则称这种带权图网络。在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加以限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。图有两种常用的存储表示方法：邻接矩阵表示法和邻接表表示法。在一个图中，邻接矩阵表示是唯一的，但邻接表表示不唯一。在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍历）及求图中顶点的度。当然对于图的广度优先遍历还利用了队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。这不仅让我们巩固了之前学的队列的基本操作，还懂得了将算法相互融合和运用。目 录第一章 课程设计目的本学期我们对数据结构这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计。数据结构是计算机软件和计算机应用专业的核心课程之一，在众多的计算机系统软件和应用软件中都要用到各种数据结构。这次课程设计不但要求学习者掌握数据结构中的各方面知识，还要求学习者具备一定的C语言基础和编程能力。具体说来，这次课程设计主要有两大方面目的：一是让学习者通过学习掌握数据结构中的知识。对于图的存储与遍历这一课题来说，所要求掌握的数据结构知识主要有：图的邻接矩阵存储、图的邻接表存储、队列的基本运算实现、邻接矩阵的算法实现、邻接表的算法实现、图的广度优先遍历算法实现、图的深度优先遍历算法实现。二是通过学习巩固并提高学习者的C语言知识，并初步了解Visual C+的知识，提高其编程能力与专业水平。第二章 课程设计内容和要求2.1课程设计内容该课题要求以邻接矩阵和邻接表的方式存储图，输出邻接矩阵和邻接表，并要求实现图的深度、广度两种遍历及顶点的度。2.1.1图的邻接矩阵的建立与输出 对任意输入顶点数和边数的图，若对无向图进行讨论，根据邻接矩阵的存储结构建立图的邻接矩阵并输出。要求输出的格式是矩阵形式，这样便于直观的了解。2.1.2图的邻接表的建立与输出对任意给定的图（顶点数和边数可以宏定义），若对无向图进行讨论，根据邻接表的存储结构建立图的邻接表并输出。2.1.3图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归算法来实现。当然，若存储图的表示不一样，进行两种遍历的方式也不一样。2.1.4 图的顶点的度 在图中，可以求顶点的度。在无向图用邻接矩阵表示，Vi顶点的度即是该矩阵第i行或第j列中非0元素的个数之和。若无向图用邻接表表示，顶点Vi的度则是第i个边表中的结点个数。2.2 运行环境该程序的运行环境为Windows xp系统，Microsoft Visual C+6.0版本。第三章 课程设计分析3.1图的存储 图的存储表示方法很多，但常用的是：图的矩阵表示和邻接表表示。至于在遇到问题具体选择哪一种表示法，主要取决于具体的应用和欲施加的操作。3.1.1 图的邻接矩阵存储表示本课题有邻接矩阵存储表示，邻接矩阵是表示顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：Ai,j=1：若（Vi，Vj）是E（G）中的边；Ai,j=0：若（Vi，Vj）不是E(G)中的边。用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表存储顶点信息。因此，我们就要进行定义数据类型。由于无向图的邻接矩阵是对称的，故采用压缩存储方式，仅存储上三角阵（不包括对角线上的元素）中的元素即可。显然，邻接矩阵表示法的空间杂度S（n）=O（n2）。开始进行类型定义，用输入的方式来控制图的顶点数和边数，并对邻接矩阵进行初始化，将G->arcsij=0，再从键盘上获得顶点信息，建立顶点表，在此同时G->arcsij=1，G->arcsji=1，最后输出邻接矩阵，用两层for循环语句来控制。3.1.2 图的邻接表存储表示 另外还有邻接表的存储表示。邻接表是一种链式的存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边。每个结点由2个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（next）指示下一条边的结点。所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数以及各条边的起点与终点序号，建立图的邻接表。对于无向图，一条边的两的个顶点，互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。同时将终点的单链表表头插入一边结点，即起点。对于邻接表的输出，采用for语句输出各结点。3.2 图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有的顶点各作一次访问。若给定的图是连通图，则从图中任一顶点出发顺着边可以访问到该图的所有顶点。图的遍历比树的遍历复杂得多，这是因为图中的任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又回到了顶点。为了避免重复访问同一个顶点必须记住每个顶点是否被访问过。为此，可设置一个布尔向量visitedn，它的初始值为0，一旦访问了顶点Vi，便将visitedi-1置为1。 根据搜索路径的方向不同，有两种常用的遍历图的方法：深度优先遍历和广度优先遍历。3.2.1 图的深度优先遍历假设给定图G的初态是所有顶点未曾被访问，在G中任选一顶点Vi为初始出发点，则深度优先遍历可定义如下：首先，访问出发点Vi，并将其标记为已访问过，然后，依次从Vi出发搜索Vi的每一个邻接点Vj，若Vj未曾访问过，则以Vj为新的出发点继续进行深度优先遍历。显然这是一个递归的过程，它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先遍历。在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。具体过程应为：先访问初始点Vi，并标志其已被访问。此时定义一指向边结点的指针p，并建立一个while（）循环，以指针所指对象不为空为控制条件，当Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先遍历了。 对图进行深度优先遍历时，按访问顶点的先后顺序所得到的顶点序列，称为该图的深度优先遍历序列，简称DFS序列。一个图的DFS序列不唯一，它与算法、图的存储结构以及初始出发点有关。在DFS算法中，当从Vi出发搜索时，是在邻接矩阵的第i行中从左至右选择下一个未曾访问的邻接点作为新的出发点，若这种邻接点多于一个，则选中的是序号较小的那一个。因为图的邻接矩阵表示是唯一的，故对于指定的初始出发点，有DFS算法所得的DFS序列是序列是唯一的。3.2.2 图的广度优先遍历广度优先搜索遍历类似于树的按层次遍历的过程。设图G中某顶点Vi出发，在访问了Vi之后访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尙有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以Vi为起始点，由近及远，依次访问和Vi有路径相通且路径长度为1，2，的顶点。所以要实现算法必须先建立一个元素类型为整型的空队列，并定义队首与队尾指针，同时也要定义一个标志数组以标记结点是否被访问。同样，也是从初始点出发开始访问，访问初始点，标志其已被访问，并将其入队。当队列非空时进行循环处理。当结点被访问时对其进行标志，并入队列。通过while（）循环，并以是否被访问为控制条件，访问所有结点，完成图的广度优先遍历。和定义图的DFS序列类似，我们可将广度优先遍历图所得到的顶点序列，定义为图的广度优先搜索遍历序列，简称BFS序列。一个图的BFS序列也是不唯一的，它与算法、图的存储结构以及初始出发点有关。3.3图的顶点的度若无向图用邻接矩阵表示，Vi顶点的度即是该矩阵第i行或第j列中非0元素的个数之和。若无向图用邻接表表示，Vi的度分为出度和入度。出度即是表结点的个数，入度即是逆邻接表的出度。第四章 算法（数据结构）描述4.1 图的存储结构的建立。4.1.1 定义邻接矩阵的定义类型typedef int datatype;typedef structchar vexsmax;int arcsmaxmax;int vexsnum,arcsnum; /* 顶点个数及边的个数 */graph;4.1.2定义邻接表的边结点类型以及邻接表类型typedef char vextype;typedef struct node int adjvex; /* 邻接点域 */ struct node *next; /* 链域 */enode; /* 边表结点 */typedef struct vextype vertex; /* 顶点信息 */ enode *link; /* 边表头指针 */vnode; /* 顶点表结点4.1.3初始化图的邻接矩阵for(i=0;i<G->vexsnum;i+)G->vexsi=getchar(); for(i=0;i<G->vexsnum;i+)for(j=0;j<G->vexsnum;j+)G->arcsij=0; 4.1.4 初始化图的邻接表需建立一个邻接表初始化函数对图的邻接表进行初始化。即建立一个所有边结点都为空的邻接表。for(i=0;i<n;i+) ai.vertex=getchar(); ai.link=NULL; /* 边表头指针初始化 */ 4.2 图的遍历4.2.1 深度优先遍历图具体过程应为：在深度优先遍历函数的参数中定义一个标志数组visited1n（邻接矩阵表示）和visited3n（邻接表表示），当某结点已被访问时visited1i=1或visited3i=1，未被访问时visited1i=0或visited3i=0。先访问初始点Vi，并标志其已被访问。若是邻接矩阵表示时将定义一指向边结点的指针p，并建立一个while（）循环，以指针所指对象不为空为控制条件，当Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先遍历了。深度优先遍历的相关代码在下面的源代码中给出。4.2.2 广度优先遍历图要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组visited2n（邻接矩阵表示）和visited4n（邻接表表示）和以标记结点是否被访问。同样，也是从初始点Vi出发开始访问，访问初始点，标志其已被访问，并将已访问过的初始点序号i入队。当队列非空时进行循环处理，删除队首元素，第一次执行时k的值为i，即front=(front+1)%maxsize。然后取Vk邻接表的表头指针int k=pfront; enode* p=ak。当边结点指针p不为空时，通过while（）循环，并以p是否为空为控制条件，依次搜索Vk的每一个结点。访问完后，将p指向p->next。这样就可以访问所有结点，完成图的广度优先遍历。广度优先遍历的相关代码在下面的源代码中给出。4.3 main函数在main函数中运用了菜单。用主菜单来控制是选择邻接矩阵的存储表示还是邻接表的存储表示，用子菜单来控制选择深度优先遍历还是广度优先遍历。4.4 图的大致流程表图的存储与遍历邻接矩阵表示法邻接表表示法深度优先遍历广度优先遍历深度优先遍历广度优先遍历各顶点的度各顶点的度第五章 源代码程序 图的存储与遍历#include<stdio.h>#include<malloc.h> #define max 6typedef int datatype;typedef structchar vexsmax;int arcsmaxmax;int vexsnum,arcsnum; /* 顶点个数及边的个数 */graph;void creatgraph(graph *G) /* 建立邻接矩阵的无向图 */int i,j,k,sum;printf("请输入顶点个数及边的个数：n");scanf("%d%d",&G->vexsnum,&G->arcsnum);printf("请读入顶点信息，建立顶点表：n");getchar();for(i=0;i<G->vexsnum;i+)G->vexsi=getchar(); for(i=0;i<G->vexsnum;i+)for(j=0;j<G->vexsnum;j+)G->arcsij=0; /* 邻接矩阵初始化 */printf("请输入相邻接的两边的顶点信息：n");for(k=0;k<G->arcsnum;k+)scanf("%d%d",&i,&j);G->arcsij=1;G->arcsji=1; /* 读入边（Vi,Vj） */printf("输出的邻接矩阵为：n");for(i=0;i<G->vexsnum;i+)printf("n");for(j=0;j<G->vexsnum;j+)printf("%3d",G->arcsij); /* 邻接矩阵的输出 */printf("n输出邻接矩阵Vi顶点的度为：n");for(i=0;i<G->vexsnum;i+)sum=0;for(j=0;j<G->vexsnum;j+)if(G->arcsij=1)sum+;printf("V%d的度为：%dn",i,sum); /* 各顶点的度 */#define n 4#define m 5typedef char vextype;typedef struct node int adjvex; /* 邻接点域 */ struct node *next; /* 链域 */enode; /* 边表结点 */typedef struct vextype vertex; /* 顶点信息 */ enode *link; /* 边表头指针 */vnode; /* 顶点表结点 */vnode an;void creatlist() /* 建立无向图的邻接表 */ int i,j,k,sum; enode *s; printf("请读入顶点信息，建立顶点表：n"); getchar(); for(i=0;i<n;i+) ai.vertex=getchar(); ai.link=NULL; /* 边表头指针初始化 */ printf("请输入相邻接的两边的顶点信息：n"); for(k=0;k<m;k+) scanf("%d%d",&i,&j); /* 读入边（Vi,Vj） */ s=(enode*)malloc(sizeof(enode); /* 生成邻接点序号为j的表结点*s */ s->adjvex=j; s->next=ai.link; ai.link=s; /* 将*s插入顶点Vi的边表头部 */ s=(enode*)malloc(sizeof(enode); /* 生成邻接点序号为i的边表结点*s */ s->adjvex=i; s->next=aj.link; aj.link=s; /* 将*s插入顶点Vj的边表头部 */ printf("输出的邻接表为：n"); for(i=0;i<m;i+) printf("n%c ",ai.vertex); s=ai.link; while(s) printf("%d->",s->adjvex); s=s->next; /* 邻接表的输出 */printf("输出邻接表Vi顶点的度为：n"); for(i=0;i<n;i+) s=ai.link; sum=0; while(s) sum+; s=s->next; printf("V%d的度为：%dn",i,sum); /* 各顶点的度 */int visited1max=0; /* 定义布尔向量visited1为全程量 */void dfs1(graph *G,int i) /* 从Vi+1出发深度优先搜索图G，G用邻接矩阵表示 */int j;printf("node:%cn",G->vexsi); /* 访问出发点Vi+1 */visited1i=1; /* 标记Vi+1已被访问 */for(j=0;j<G->vexsnum;j+) /* 依次搜索Vi+1的邻接点 */if(G->arcsij)&&(!visited1j)dfs1(G,j);/* 若Vi+1的邻接点Vi+1未曾访问过，则从Vi+1出发进行深度优先搜索 */#define maxsize 80typedef int datatype;typedef structdatatype datamaxsize;int front,rear;sequeue; /* 顺序队列的类型 */sequeue *p; /* p是顺序队列类型的指针 */void setnull() /* 置队列p为空对 */p->front=maxsize-1;p->rear=maxsize-1;int empty() /* 判别p是否为空 */if(p->front=p->rear)return 1;else return 0;int front() /* 取p的队头元素 */if(empty()printf("the sequeue is empty");return 0;else return p->data(p->front+1)%maxsize;int enqueue(int x) /* 将新元素x插入队列p的队尾 */if(p->rear+1)%maxsize=p->front)printf("the queue is full.");return 0;else p->rear=(p->rear+1)%maxsize;p->datap->rear=x;return x; int dequeue() /* 删除队列p的头元素，并返回该元素 */if(empty()printf("the sequeue is empty");return 0;elsep->front=(p->front+1)%maxsize;return (p->datap->front);int visited2max=0;void bfs1(graph *G,int k)/*从Vi+1出发广度优先搜索图G，G用邻接矩阵表示*/int i,j;setnull();printf("node:%cn",G->vexsk); /* 访问出发点Vk+1 */visited2k=1;enqueue(k);while(!empty() /* 队非空时执行 */i=dequeue();for(j=0;j<G->vexsnum;j+)if(G->arcsij)&&(!visited2j)printf("%cn",G->vexsj); /* 访问Vi+1的未曾访问的邻接点Vj+1 */visited2j=1;enqueue(j); /* 访问过的顶点入队 */int visited3n=0;void dfs2(int i) /* 从Vi+1出发深度优先遍历搜索图a，a图用邻接表表示*/enode *p;printf("node:%cn",ai.vertex);visited3i=1;p=ai.link; /* 取Vi+1的边表头指针 */while(p!=NULL) /* 依次搜索Vi+1的邻接点 */if(!visited3p->adjvex)dfs2(p->adjvex); /* 从Vi+1的未曾访问过的邻接点出发进行深度优先搜索 */p=p->next; /* 找Vi+1下一个邻接点 */int visited4n=0;void bfs2(int k) /* 从Vi+1出发广度优先搜索图a,a用邻接表表示 */int i;enode *p;setnull();printf("node:%cn",ak.vertex);visited4k=1;enqueue(k);while(!empty()i=dequeue();p=ai.link; /* 取Vi+1的边表头指针 */while(p!=NULL) /* 依次搜索Vi+1的邻接点 */if(!visited4p->adjvex) /* 访问Vi+1的未曾访问的邻接点 */printf("node:%cn",ap->adjvex.vertex);visited4p->adjvex=1;enqueue(p->adjvex); /* 访问过的顶点入队 */p=p->next; /* 找Vi+1的下一个邻接点 */void main()int i,j,x,y,z,s,t;graph a;int flag=0;p=(sequeue*)malloc(sizeof(sequeue);printf("=欢迎进入=n");while(1)printf("请选择输入n1为用邻接矩阵存储图n2为用邻接表存储图n0为退出：n"); scanf("%d",&x);switch(x)case 1:creatgraph(&a);while(flag=0) printf("请选择输入n1为邻接矩阵深度优先遍历n2为邻接矩阵广度优先遍历n0为返回继续选择图的存储：n"); scanf("%d",&y); switch(y) case 1:printf("请输入深度优先遍历的顶点：n"); scanf("%d",&i); dfs1(&a,i);break; case 2:printf("请输入广度优先遍历的顶点：n"); scanf("%d",&j); bfs1(&a,j);break; case 0:flag=1; break;case 2:creatlist();while(flag=0)printf("请选择输入n1为邻接表深度优先遍历n2为邻接表广度优先遍历n0为返回继续选择图的存储：n："); scanf("%d",& z); switch(z) case 1:printf("请输入深度优先遍历的顶点：n"); scanf("%d",&s); dfs2(s);break; case 2:printf("请输入广度优先遍历的顶点：n"); scanf("%d",&t); bfs2(t);break; case 0:flag=1; break;case 0:exit(0);第六章 测试结果由于学习之初对图的存储结构了解不是很清楚，所以在运行出了错误。首先在运行当中少了一句算法：在建立邻接表，输入顶点信息时，少了getchar()语句。因为程序本身没报错，但是在执行的过程中出现了错误的信息，而且总是在执行邻接表操作时出错。另外在宏定义时定义了m,n，但我还在main函数中定义了int类型的m,n，所以程序报错了，这让我懂得了宏定义的作用和意义。在小的细节上，偶尔打错单词，造成错误。 V0 V3例如我们运用右图（无向图）来执行操作的话 便可得到相应的结果： V1 V2 图a当我们选择从键盘上输入1时，程序执行的是用邻接矩阵存储图，相应的我们要从键盘了输入顶点个数及边的个数，如4，5。再读入顶点信息，如0123。根据提示信息再从键盘上输入相邻接的两边的顶点信息，如0，1；0，2；0，3；1，2；1，3。这样便可以得到所存储的邻接矩阵了，同时也输出了各个顶点的度。 图b在main函数中还有相应的子菜单，当我们在主菜单中选的是1用邻接矩阵存储时，子菜单中就有一系列算法：邻接矩阵深度优先遍历（图b）和广度优先遍历（图c）。 图c第七章 思想总结转眼，为期两周的数据结构课程设计学习即将结束。在这次学习中，自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：1、必须牢固掌握基础知识。由于C语言是大一所学知识，有所遗忘，且未掌握好这学期所学的数据结构这门课，所以在学习之初感到棘手。不知如何下手，但在后来的学习过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所熟悉。所以，这次学习之后，我告诫自己：今后一定要牢固掌握好专业基础知识。2、必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”、“单词打错”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计，做任何事都应如此。3、这次课程设计也让我充分认识到数据结构这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。总之，在这次学习中，自己的C语言以及数据结构知识得到提高，编程能力也得到了提高。第八章 参考文献1谭浩强 著 C程序设计（第三版）清华大学出版社 2杨路明 编著C语言程序设计教程北京邮电大学出版社 3范策 周世平 编著 算法与数据结构（c语言版）机械工业出版社 专心-专注-专业