数据结构-邻接表存储及遍历-课程设计-实验报告.doc

数 据 结 构 课 程 设 计设计题目： 邻接表存储及遍历 学生姓名： 专业班级： 指导教师： 完成时间： 课题名称 邻接表存储及遍历院 系年级专业学 号姓 名成 绩课题设计目的与设计意义1、课题设计目的：通过实习掌握数据结构中的知识。对于本课题所要求掌握的数据结构知识主要有：图的邻接表储存结构、邻接表的算法实现、图的广度优先搜索遍历、图的深度优先搜索遍历。2、课题设计意义：培养学生运用数据结构的基本知识解决实际编程中的数据结构设计和设计问题。 培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。指导教师：年 月 日数据结构（c语言版）课程设计报告目 录第一章 需求分析41.1 图41.2 邻接表的概念41.3邻接表的表示法4第二章 概要分析52.1 无向图52.2 有相图52.3 无向图52.4有向图5第三章 详细分析63.1 邻接表的建立63.2 邻接表的建立过程如下：63.2.1无向图邻接表的建立63.2.2 有向图邻接表的建立73.3 邻接表的输出过程如下：73.4 邻接表的遍历83.4.1 连通图的深度优先搜索遍历83.4.2 有向图的广度优先搜索遍历93.5 流程图103.5.1 主流程图103.5.2 无向图邻接表的流程图103.5.3 有向图邻接表的流程图12第四章 测试分析144.1 无向图144.1.1 主程序main()编写如下：144.1.2 运行步骤164.2 有向图18第五章 心得体会20第六章、参考文献20第一章 需求分析1.1 图 若图1.1中每一条边都是有方向的，则为有相图。 若图1.1中每一条边都是没有方向的，则为无向图。v2 图1.11.2 邻接表的概念 对于图1.1中的每个顶点vi，该方法把所有邻接于vi 的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表。1.3邻接表的表示法邻接表中每个表结点均有2个域，其一是邻接点域（adjvex），用以存放与vi相邻接的顶点vj的序号；其二是链域（next），用来将邻接表的所有表结点链在一起。并且为每个顶点vi的邻接表设置一个具有2个域的表头结点：一个是顶点域（vertex），用来存放顶点vi的信息；另一个是指针域（link），用于存入指向vi的邻接表中第一个表结点的头指针。 第二章 概要分析2.1 无向图无向图邻接表的建立，无向图邻接表的输出，无向图邻接表的深度优先搜索遍历，无向图邻接表的广度优先搜索遍历。2.2 有相图 有向图邻接表的建立，有向图邻接表的输出，有向图邻接表的深度优先搜索遍历，有向图邻接表的广度优先搜索遍历。2.3 无向图函数名称函数功能creat_ljbiao无向图邻接表的建立print_ljb无向图邻接表的输出DFSL无向图邻接表的深度遍历BFSL无向图邻接表的广度遍历2.4有向图函数名称函数功能creat_yljb有向图邻接表的建立print_ljb有向图邻接表的输出DFSL有向图邻接表的深度遍历BFSL有向图邻接表的广度遍历 第三章 详细分析3.1 邻接表的建立 邻接表是把所有邻接于vi的顶点vj链成一个单链表。其次还需要一个顺序表来储存顶点信息。其具体C语言代码如下： typedef struct node int adjvex;/*邻接点域*/ struct node *next;/*链域*/ edgenode;/*边表结点*/3.2 邻接表的建立过程如下： 3.2.1无向图邻接表的建立 void creat_ljb(topnode gl,int n,int e) /*无向图邻接表的建立*/ int i,j,k; edgenode *p; getchar(); printf(请输入%d个顶点的元素:,n); for(i=0;in;i+)/*读入顶点信息*/ scanf(%c,&gli.topvex)； gli.link=NULL; /*边表头指针初始化*/ printf(请输入要邻接的俩个顶点的下标:n); for(k=0;kadjvex=j; p-next=gli.link; gli.link=p; p=(edgenode *)malloc(sizeof(edgenode); p-adjvex=i; p-next=glj.link; glj.link=p; 3.2.2 有向图邻接表的建立 void creat_yljb(topnode gl,int n,int e)/*有向图邻接表的建立*/ int i,j,k; edgenode *p; getchar(); printf(请输入%d个顶点的元素:,n); for(i=0;in;i+) scanf(%c,&gli.topvex); gli.link=NULL; printf(请输入要邻接的俩个顶点的下标:n); for(k=0;kadjvex=j; p-next=gli.link; gli.link=p; 3.3 邻接表的输出过程如下： void print_ljb(topnode gl,int n)/*邻接表的输出*/ int i; edgenode *p; printf(建立后的邻接表为:n); for(i=0;iadjvex); p=p-next; printf(n); 3.4 邻接表的遍历 对于图的遍历，和树的遍历类似，也是从某个顶点出发，沿着搜索路径对图中所有顶点做一次访问。若给定的图是连通图，则从图中人一顶点出发顺着边可以访问到该图的所有顶点。又因为图中任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条路又反回到了该顶点。为避免重复访问同顶点，必须记住每个顶点是否被访问过。为此，我们已经在前面设置了向量int visitedvexnum=0来标示，他的初始值为0。3.4.1 连通图的深度优先搜索遍历 int visited_lj20=0; void DFSL(topnode gl,int i)/*邻接表的深度遍历*/ edgenode *p; printf(%c,gli.topvex); visited_lji=1; p=gli.link; while(p!=NULL) if(visited_ljp-adjvex=0) DFSL(gl,p-adjvex); p=p-next; int visited20=0;3.4.2 有向图的广度优先搜索遍历 int visited_ljb20=0; void BFSL(topnode gl,int k)/*邻接表的广度遍历*/ int i; edgenode *p; linkqueue Q; setnull(&Q); printf(%c,glk.topvex); visited_ljbk=1; enqueue(&Q,k); while(!empty(&Q) i=dequeue(&Q); p=gli.link; while(p!=NULL) if(!visited_ljbp-adjvex) printf(%c,glp-adjvex.topvex); visited_ljbp-adjvex=1; enqueue(&Q,p-adjvex); p=p-next; int visited_jz20=0;开始主菜单无向图操作有向图操作3.5 流程图 3.5.1 主流程图3.5.2 无向图邻接表的流程图 开始输出邻接表P输入顶点数和边数 n e输入n个顶点的元素输入相邻的两个顶点的下标否 是输出建立后邻接表 输入深度遍历起始位置P！=NULL否Visited-ljp-adjvex=0 是否是输出遍历结果输出建立后邻接表输入广度遍历起始位置!empty(&Q)否P!=NULL是否!visited-ljbp-adjvex是否是输出遍历结果结束3.5.3 有向图邻接表的流程图 开始 输入顶点数和边数 n e输入n个顶点的元素输入相邻的两个顶点的下标输出邻接表P否输出建立后邻接表是输入深度遍历起始位置P！=NULL否Visited-ljp-adjvex=0是否是输出遍历结果输出建立后邻接表输入广度遍历起始位置!empty(&Q)否是P!=NULL否是!visited-ljbp-adjvex否是输出遍历结果结束 第四章 测试分析运行环境：Microsoft Visual C+程序语言：C语言下面，我们来检验一下程序能否正确运行。4.1 无向图ba01顶点信息dc 序号 元素0a1b2 c3 3 4.1.1 主程序main()编写如下： void main() int i=1,j,n,e; int k=1,m=1,l=1,t=1; graph ga; topnode *gl; printf(ttt邻接表表示图及深广度优先遍历n); while(i) printf(n1:无向图n2:有向图n); scanf(%d,&i); switch(i) case 1:/无向图的基本运算 while(k) printf(n1:无向图邻接表的建立n2:无向图邻接表的输出n3:无向图邻接表的深度遍历n4:无向图邻接表的广度遍历n); scanf(%d,&k); switch(k) case 1:printf(请输入顶点数和边数:); scanf(%d%d,&n,&e); creat_ljb(&gl,n,e); break; case 2:print_ljb(&gl,n); break; case 3:printf(请输入要遍历的起始位置:); scanf(%d,&j); printf(邻接表深度遍历后的结果为:) DFSL(&gl,j); break; case 4:printf(请输入要遍历的起始位置:); scanf(%d,&j); printf(邻接表广度遍历后的结果为:); BFSL(&gl,j); break; printf(n0:结束n1:继续n); scanf(%d,&k); break; case 2:/有向图的基本运算 while(l) printf(n1:有向图邻接表的建立n2:有向图邻接表的输出n3:有向图邻接表的深度遍历n4:有向图邻接表的广度遍历n); scanf(%d,&l); switch(l) case 1:printf(请输入顶点数和边数:); scanf(%d%d,&n,&e); creat_yljb(&gl,n,e); break; case 2:print_ljb(&gl,n);break; case 3:printf(请输入要遍历的起始位置:); scanf(%d,&l); printf(邻接表深度遍历后的结果为:); DFSL(&gl,l);break; case 4:printf(请输入要遍历的起始位置:); scanf(%d,&l); printf(邻接表广度遍历后的结果为:); BFSL(&gl,l); break; printf(n0:结束n1:继续n); scanf(%d,&l); break; printf(n0:结束无向图的运算1:继续无向图的运算n); scanf(%d,&i); 4.1.2 运行步骤 1 无向图邻接表建立与输出 2 广度与深度遍历 4.2 有向图adcb 01 顶