数据结构课程设计报告(图的遍历)(共16页).doc

精选优质文档-倾情为你奉上中南大学课程设计报告题 目 数据结构课程设计 学生姓名 指导教师 漆华妹 学 院 信息科学与工程学院 专业班级 学 号 完成时间 2011年07月 专心-专注-专业目 录图遍历的演示题目:试设计一个程序,演示在连通的无向图上访问全部结点的操作第一章、需求分析1、以邻接多重表为存储结构；2、实现连通和非连通的无向图的深度优先和广度优先遍历；3、要求利用栈实现无向图的深度优先遍历；4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集；5、用凹入表打印生成树；6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径；6、本程序用C语言编写，在C-Free3.5环境下通过。第二章、概要设计1、设定图的抽象数据类型:ADT Graph数据对象V:V是具有相同特性的数据元素的集合,称为点集.数据关系R:R=VRVR=(v,w)|v,w属于V,(v,w)表示v和w之间存在的路径基本操作P:CreatGraph(&G,V,VR)初始条件:V是图的顶点集,VR是图中弧的集合.操作结果:按V和VR是定义构造图G.DestroyGraph(&G)初始条件:图G存在操作结果:销毁图GLocateVex(G,u)初始条件: 图G存在,u和G中顶点有相同的特征操作结果:若图G中存在顶点u,则返回该顶点在图中的位置;否则返回其他信息GetVex(G,v)初始条件: 图G存在,v是G中顶点操作结果:返回v的值FirstAjvex(G,v)初始条件: 图G存在,v是G中顶点操作结果:返回v的第一个邻接顶点,若顶在图中没有邻接顶点,则返回为空NextAjvex(G,v,w)初始条件: 图G存在,v是G中顶点,w是v的邻接顶点操作结果:返回v的下一个邻接顶点,若w是v的最后一个邻接顶点,则返回空DeleteVexx(&G,v)初始条件: 图G存在,v是G中顶点操作结果:删除顶点v已经其相关的弧DFSTraverse(G,visit()初始条件: 图G存在,visit的顶点的应用函数操作结果: 对图进行深度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败BFSTraverse(G,visit()初始条件: 图G存在,visit的顶点的应用函数操作结果:对图进行广度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败ADT Graph2、设定队列的抽象数据类型：ADT Queue数据对象:D=ai|ai属于Elemset,i=1,2.,n,n>=0数据关系:R1=<ai-1,ai>|ai-1,ai属于D,i=1,2,n约定ai为端为队列头,an为队列尾基本操作:InitQueue(&Q)操作结果:构造一个空队列Q DestryoQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁，不再存在。EnQueue(&Q,e)初始条件:队列Q已经存在操作结果:插入元素e为Q的新的队尾元素DeQueue(&Q,&E)初始条件:Q为非空队列操作结果:删除Q的队尾元素,并用e返回其值QueueEmpty(Q)初始条件:队列已经存在操作结果:若队列为空,则返回TRUE,否则返回FLASEADT Queue3、本程序包含四个模块：1） 主程序模块void main ()手动构造一个图；进行深度优先遍历图；进行广度优先遍历图；2） 手动构造一个图-自己输入图的顶点和边生成一个图；3） 进行深度优先遍历图-打出遍历的结点序列和边集；4） 进行广度优先遍历图-打出遍历的结点序列和边集；第三章、详细设计1、 顶点,边和图类型#define MAX_INFO 10 /* 相关信息字符串的最大长度+1 */#define MAX_VERTEX_NUM 20 /* 图中顶点数的最大值*/int visitedMAX_VERTEX_NUM; /*全局变量，访问标志数组 */typedef char InfoType; /*相关信息类型*/typedef char VertexType; /* 字符类型 */typedef enumunvisited,visitedVisitIf;typedef struct EBox /*边结点类型*/ int mark; /*访问标记 */ int ivex,jvex; /*该边依附的两个顶点位置*/ struct EBox *ilink,*jlink; /*分别指向依附这两个顶点的下一条边 */EBox; typedef struct VexBox /*顶点结点类型*/ char dataMAX_LEN; EBox *fistedge; /*指向第一条依附该顶点的边*/ VexBox; typedef struct VexBox listMAX_VERTEX_NUM; int vexnum,edgenum; /*无向图当前顶点数和边数 */ AMLGraph; 图的基本操作如下：int LocateVex(AMLGraph G,VertexType u)；/ 查G和u有相同特征的顶点，若存在则返回该顶点在无向图中位置;否则返回-1。VertexType& GetVex(AMLGraph G,int v)；/以v返回邻接多重表中序号为i的顶点。int FirstAdjVex(AMLGraph G,VertexType v)；/返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1。int NextAdjVex(AMLGraph G,VertexType v,VertexType w)；/返回v的(相对于w的)下一个邻接顶点的序号若w是v的最后一个邻接点,则返回-1。void CreateGraph(AMLGraph &G)；/采用邻接多重表存储结构,构造无向图G。Status DeleteArc(AMLGraph &G,VertexType v,VertexType w)；/在G中删除边<v,w>。Status DeleteVex(AMLGraph &G,VertexType v)；/在G中删除顶点v及其相关的边。void DestroyGraph(AMLGraph &G)；/销毁一个图void Display(AMLGraph G)；/输出无向图的邻接多重表G。void DFSTraverse(AMLGraph G,VertexType start,int(*visit)(VertexType)；/从start顶点起,（利用栈非递归）深度优先遍历图G。void BFSTraverse(AMLGraph G,VertexType start,int(*Visit)(VertexType)；/从start顶点起,广度优先遍历图G。void MarkUnvizited(AMLGraph G)；/置边的访问标记为未被访问。其中部分操作的算法如下： void CreateGraph(AMLGraph *p) /*创建无向图 */ int i,j,k; EBox *q; printf("nttt请输入图的结点个数和边的个数:"); /*输入图的结点数和边数*/ scanf("%d,%d",&p->vexnum,&p->edgenum); for(i=1;i<=p->vexnum;i+) printf("nttt请输入结点%d的名称:",i);/*输入顶点数据信息*/ scanf("%s",p->listi.data); p->listi.fistedge=NULL; /*初始化指针*/ for(k=0;k<p->edgenum;k+) /*输入各边并构造多重链表*/ printf("nttt请输入互相有关联的两个结点:"); scanf("%d,%d",&i,&j); q=(EBox *)malloc(sizeof(EBox); q->mark=0; /*对边结点赋值*/ q->ivex=i; q->ilink=p->listi.fistedge; q->jvex=j; q->jlink=p->listj.fistedge; p->listi.fistedge=p->listj.fistedge=q; /*完成边在链头的插入*/ printf("n"); void DFS(AMLGraph *p, int v) /*对第v个顶点的深度优先遍历 */ int w; EBox *q; visitedv=1; /*标记已访问结点 */ printf("%s ",p->listv.data); for(q=p->listv.fistedge;q!=NULL;) if(q->ivex=v) w=q->jvex; q=q->jlink; else w=q->ivex; q=q->ilink; if(!visitedw) DFS(p,w); /*对尚未访问的点调用DFS*/ void DFSTraverse(AMLGraph *p,int n) /*深度优先遍历 */ int v; printf("nttt"); for(v=1;v<=p->vexnum;v+) visitedv=0; *访问标志数组初始化*/ DFS(p,n); /*对起始顶点调用DFS*/ for(v=1;v<=p->vexnum;v+) if(!visitedv) DFS(p,v); /*对尚未访问的顶点调用DFS*/ printf("n"); 2、队列类型typedef int QelemType；typedef struct QNode QElemType data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear; /* 队头、队尾指针 */LinkQueue;队列的基本操作如下：Status InitQueue(LinkQueue &Q)；/构造一个空队列Q。Status DestroyQueue(LinkQueue &Q)；/销毁队列Q(无论空否均可)。Status QueueEmpty(LinkQueue Q)；/若Q为空队列,则返回1,否则返回-1。Status EnQueue(LinkQueue &Q,QElemType e)；/插入元素e为Q的新的队尾元素。Status DeQueue(LinkQueue &Q,QElemType &e)；/若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回-1。其中部分操作的算法如下：void BFS(AMLGraph *p,int v) /*对第v个顶点进行广度优先遍历*/ int u,w; EBox *x; typedef struct queue int m; struct queue *next; Q; /*辅助队列Q*/ Q *head,*tail,*q; head=tail=(Q *)malloc(sizeof(Q); tail->next=NULL; visitedv=1; /*标记已访问结点 */ printf("%s ",p->listv.data); tail->m=v; /*v入队列 */ tail->next=(Q *)malloc(sizeof(Q); tail=tail->next; tail->next=NULL; while(head!=tail) q=head; head=head->next; u=q->m; /*对头元素出队并置为u*/ free(q); for(x=p->listu.fistedge;x!=NULL;) if(x->ivex=u) w=x->jvex;x=x->ilink; else w=x->ivex;x=x->jlink; if(!visitedw) visitedw=1; printf("%s ",p->listw.data); tail->m=w; /*w入队列*/ tail=tail->next=(Q *)malloc(sizeof(Q); tail->next=NULL; /*if*/ /*for */ /*while*/ /*BFS*/void BFSTraverse(AMLGraph *p,int n) printf("nttt"); /*广度优先遍历*/ int v; for(v=1;v<=p->vexnum;v+) visitedv=0; /*访问标志数组初始化*/ BFS(p,n); /*对起始顶点调用BFS*/ for(v=1;v<=p->vexnum;v+) if(!visitedv) BFS(p,v); printf("n"); /*对未访问顶点调用BFS*/3、主程序和其他伪码算法 void main ()显示菜单；输入功能选择键；switch(flag)case 1:手动构造一个图；case 2:进行深度优先遍历图；case 3:进行广度优先遍历图； case 4:退出程序；算法代码 main() /*主函数 */ int x,n; AMLGraph graph,*p; p=&graph; system("color 1f"); printf("ttt* 图的深度和广度优先遍历 *n"); printf("ttt* *n"); printf("ttt* *n"); printf("n"); while(1) printf("n"); printf("ttt 功能菜单 n"); printf("n"); printf("ttt*n");printf("ttt* 1.创建图 *n");printf("ttt* *n");printf("ttt* 2.深度优先遍历图 *n");printf("ttt* *n");printf("ttt* 3.广度优先遍历图 *n");printf("ttt* *n");printf("ttt* 4.退出系统 *n");printf("ttt* *n");printf("ttt*n");printf("nttt请输入选择的功能编号（1-4）："); scanf("%d",&n);if(n<0 | n>4)printf("nnttt你输入的功能号错误，请重新输入，按Enter键继续！");getchar();getchar(); continue;switch(n)case 1: system("color 3f"); CreateGraph(p);break;case 2: system("color 79"); printf("nttt请输入起始遍历结点:"); scanf("%d",&x); printf("nttt深度优先遍历结果为:"); printf("n"); DFSTraverse(p,x); printf("n"); break;case 3: system("color 2E"); printf("nttt请输入起始遍历结点:"); scanf("%d",&x); printf("nttt广度优先遍历结果为:"); printf("n"); BFSTraverse(p,x); printf("n"); break;case 4: printf("nnttt谢谢你的使用！nnn"); exit(0); /*switch */ /*while */ /*main */第四章、调试分析1、本程序以邻接多重表为存储结构。这个程序涉及到图的生成和图的深度以及广度遍历,文件的保存和读取，还有栈和队列的操作，另外还有森林的生成和打印，路径的寻找。2、本程序不仅可以进行连通无向图的遍历，还可以进行非连通图的遍历。为了方便显示和理解，现在暂且用一个大写字母表示一个顶点。边还可以附加信息，但为了方便操作，暂且不输入信息。已经先把图的相关信息保存在了文本文档里，所以要测试时直接从文件导入，可以减少用手输入的麻烦，同时也可以减少输入的错误。3、由于构造图时，后输入的边是插在先输入的边的前面。所以在输入边时，可以按字母从大到小的顺序输入。那么显示图的时候就可以按字母从小到大的顺序显示。4、程序定义了一个二倍顶点长的数组存放输入的边，以便程序可以把它保存到文件里。故耗费了一定的内存空间。 第五章、用户手册1、本程序的运行环境DOS操作系统，GTraverse.exe2、进入演示程序后即显示一个有功能选择的界面，如下：3、选择操作1：程序就提示分别输入无向图的顶点数，边数，边的信息，顶点和边的值：输入完成后，返回菜单。4、选择操作2：系统提示输入遍历图的起始点，程序运行后，首先显示深度优先遍历的访问结点序列。5、选择操作3：系统提示输入遍历图的起始点，程序运行后，首先显示广度优先遍历的访问结点序列。6、选择操作4：退出程序。第六章、测试结果1、数据可以任意输入,但是顶点数不要太多，不然占用太多内存，会导致死机。2、遍历一个连通的无向图，如遍历以下这个连通无向图：ABCD1)选择操作1，分别进行以下操作:请输入图的结点个数和边的个数:4,5请输入结点1的名称:A 请输入结点2的名称:B请输入结点3的名称:C请输入结点4的名称:D请输入互相有关联的两个结点:1,2请输入互相有关联的两个结点:1,3请输入互相有关联的两个结点:1,4请输入互相有关联的两个结点:2,4请输入互相有关联的两个结点:3,42) 选择操作2，输出图的信息如下：请输入起始遍历结点:1深度优先遍历结果为:A B D C3) 选择操作3，输出图的信息如下：请输入起始遍历结点:1广度优先遍历结果为:A B C D第七章、心得体会这道题的完成，花了一个星期时间，因为我一个多学期没接触C语言和数据结构首先我把基本功能完成后来逐步地增加了许多功能。把本来只能遍历连通图的功能上，改进为可以遍历非连通图。通过这道设计题,使我更深刻的理解数据结构及其重要作用,对数据结构有了一个新的认识,深刻的认识到数据结构对于我们学习计算机的重要性和其深远但是意义.同时,通过这次课程设计,也加强我的动手能力和思维能力,可以将自己所学的知识用于实践,这不仅对自己是一次锻炼机会,而且让自己有一种成就感和自豪感，觉得自己终于可以做出一点有用的东西了。不过,我觉得自己编写程序的一些思路算法和水平还非常有限。所以以后自己还得在C语言和其他语言上下苦功夫。附：源程序#include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 30 /*无向图最大顶点数*/ #define MAX_LEN 20 /*数据最大长度 */int visitedMAX_VERTEX_NUM; /*全局变量，访问标志数组 */ typedef struct EBox /*边结点类型*/ int mark; /*访问标记 */ int ivex,jvex; /*该边依附的两个顶点位置*/ struct EBox *ilink,*jlink; /*分别指向依附这两个顶点的下一条边 */EBox; typedef struct VexBox /*顶点结点类型*/ char dataMAX_LEN; EBox *fistedge; /*指向第一条依附该顶点的边*/ VexBox; typedef struct VexBox listMAX_VERTEX_NUM; int vexnum,edgenum; /*无向图当前顶点数和边数 */ AMLGraph; void CreateGraph(AMLGraph *p) /*创建无向图 */ int i,j,k; EBox *q; printf("nttt请输入图的结点个数和边的个数:"); /*输入图的结点数和边数*/ scanf("%d,%d",&p->vexnum,&p->edgenum); for(i=1;i<=p->vexnum;i+) printf("nttt请输入结点%d的名称:",i); /*输入顶点数据信息*/ scanf("%s",p->listi.data); p->listi.fistedge=NULL; /*初始化指针*/ for(k=0;k<p->edgenum;k+) /*输入各边并构造多重链表*/ printf("nttt请输入互相有关联的两个结点:"); scanf("%d,%d",&i,&j); q=(EBox *)malloc(sizeof(EBox); q->mark=0; /*对边结点赋值*/ q->ivex=i; q->ilink=p->listi.fistedge; q->jvex=j; q->jlink=p->listj.fistedge; p->listi.fistedge=p->listj.fistedge=q; /*完成边在链头的插入*/ printf("n"); void DFS(AMLGraph *p, int v) /*对第v个顶点的深度优先遍历 */ int w; EBox *q; visitedv=1; /*标记已访问结点 */ printf("%s ",p->listv.data); for(q=p->listv.fistedge;q!=NULL;) if(q->ivex=v) w=q->jvex; q=q->jlink; else w=q->ivex; q=q->ilink; if(!visitedw) DFS(p,w); /*对尚未访问的点调用DFS*/ void DFSTraverse(AMLGraph *p,int n) /*深度优先遍历 */ int v; printf("nttt"); for(v=1;v<=p->vexnum;v+) visitedv=0; /*访问标志数组初始化*/ DFS(p,n); /*对起始顶点调用DFS*/ for(v=1;v<=p->vexnum;v+) if(!visitedv) DFS(p,v); /*对尚未访问的顶点调用DFS*/ printf("n"); void BFS(AMLGraph *p,int v) /*对第v个顶点进行广度优先遍历*/ int u,w; EBox *x; typedef struct queue int m; struct queue *next; Q; /*辅助队列Q*/ Q *head,*tail,*q; head=tail=(Q *)malloc(sizeof(Q); tail->next=NULL; visitedv=1; /*标记已访问结点 */ printf("%s ",p->listv.data); tail->m=v; /*v入队列 */ tail->next=(Q *)malloc(sizeof(Q); tail=tail->next; tail->next=NULL; while(head!=tail) q=head; head=he