数据结构课程设计报告(图的遍历).docx
数据结构课程设计报告(图的遍历) 中南大学 课程设计报告 题目数据结构课程设计学生姓名 指导教师漆华妹 学院信息科学与工程学院专业班级 学号 完成时间2022年07月 目录 第一章、需求分析 (2) 第二章、概要设计 (2) 设定图的抽象数据类型 (2) 设定队列的抽象数据类型 (3) 本程序包含的功能模块 (3) 第三章、详细设计 (3) 顶点、边和图的类型 (6) 队列类型 (8) 主程序和其他伪码算法 (9) 第四章、调试分析 (9) 第五章、用户手册 (9) 第六章、测试结果 (10) 第七章、心得体会 (10) 附：源程序代码 (11) 图遍历的演示 题目:试设计一个程序,演示在连通的无向图上访问全部结点的操作 第一章、需求分析 1、以邻接多重表为存储结构； 2、实现连通和非连通的无向图的深度优先和广度优先遍历； 3、要求利用栈实现无向图的深度优先遍历； 4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集； 5、用凹入表打印生成树； 6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径； 6、本程序用C语言编写，在环境下通过。 第二章、概要设计 1、设定图的抽象数据类型: ADT Graph 数据对象V:V是具有相同特性的数据元素的集合,称为点集. 数据关系R: R=VR VR=(v,w)|v,w属于V,(v,w)表示v和w之间存在的路径 基本操作P: CreatGraph(&G,V,VR) 初始条件:V是图的顶点集,VR是图中弧的集合. 操作结果:按V和VR是定义构造图G. DestroyGraph(&G) 初始条件:图G存在 操作结果:销毁图G LocateVex(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 Graph 2、设定队列的抽象数据类型： ADT Queue 数据对象:D=ai|ai属于Elemset,i=1,2.,n,n>=0 数据关系:R1=|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,否则返回FLASE ADT Queue 3、本程序包含四个模块： 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)； ata); p->listi.fistedge=NULL; /*初始化指针*/ for(k=0;kedgenum;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;vvexnum;v+) visitedv=0; *访问标志数组初始化*/ DFS(p,n); /*对起始顶点调用DFS*/ for(v=1;vvexnum;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)； ata); 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;vvexnum;v+) visitedv=0; /*访问标志数组初始化*/ BFS(p,n); /*对起始顶点调用BFS*/ for(v=1;vvexnum;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");
