数据结构-无向图的操作-课程设计-实验报告.doc

数 据 结 构 课 程 设 计设计题目： 无向图的操作 学生姓名： 专业班级： 指导教师： 完成时间： 17课题名称无向图的操作院 系年级专业学 号姓 名成 绩课题设计目的与设计意义1、课题设计目的：一、熟悉图的两种常用的存储结构，邻接矩阵。 二、建立有向图，用邻接表存储结构存储。 三、在邻接表存储结构上实现深度优先遍历。2、课题设计意义：一、能够熟悉关于无向图邻接矩阵和无向图邻接表的输出建立等操作。 二、能够理解关于无向图的基本操作有何目的与意义。 三、将以上的理解加以运用与操作。指导教师：年 月 日目 录第一章 课程设计的目的与意义1第二章 课程设计的内容与要求12.1课程设计的内容12.1.1定义12.1.2操作22.2课程设计的要求2第三章 需求分析23.1原理23.2要求33.3系统总框架33.4运行环境33.5程序的输入（包含输入的数据格式和说明）43.6开发工具4第四章 算法与描述44.1图的深度优先遍历44.2具体过程应为4第五章 源程序5第六章 运行结果12第七章 结束语17第八章 参考文献18第一章 课程设计的目的与意义图是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，除根结点之外，每个结点都只能有一个双亲（前趋），但每个结点可以有零个或多个孩子（后继）。因此，层次关系是非线性的。但是，它在树的结点之间建立了一个层次结构；同层次上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根节点除外）。然而在土结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。邻接表(Adjacency List)是图的一种顺序存储与链式存储结合的存储方法，类似于树的孩子链表表示法。由于它只考虑非零元素,因而节省了零元素所占的存储空间。它对于无向图和有向图都适用。本学期我们学了很多图的存储结构，有邻接矩阵。邻接表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是吧图的边信息与链式存数相结合的存储方法。从空间性能上说，图越洗漱邻接表的空间效率也相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要第。本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现深度优先和广度优先遍历以及其链表结构的输出。通过实习巩固并提高我的C语言知识，并初步了解Visual C+的知识，提高编程能力与专业水平。第二章 课程设计的内容与要求2.1课程设计的内容2.1.1定义有向图与无向图：图是一种复杂的非线性结构。图G由两个集合V和E组成，记为G=（V，E），其中V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集。通常，也将图G的顶点集和边集分别记为V（G）和E（G）。E（G）可以是空集，若E（G）为空，则图G只有顶点而没有边。若图G中的每条边都是有方向的，则称G为有向图；若图G中的每条边都是没有方向的，则称G为无向图。邻接矩阵：邻接矩阵是表示定点之间相邻关系的矩阵。邻接表：对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个单链变，这个单链表就成为顶点vi的邻接表。2.1.2操作 熟悉掌握关于无向图邻接表和邻接矩阵的运用以及操作，包括：无向图邻接矩阵的建立、无向图邻接矩阵的输出、无向图邻接表的建立、无向图邻接表的输出、无向图邻接表的深度遍历、无向图邻接矩阵的深度遍历、无向图邻接表的广度遍历、无向图邻接矩阵的广度遍历。2.2课程设计的要求 一、能够熟悉关于无向图邻接矩阵和无向图邻接表的输出建立等操作。 二、能够理解关于无向图的基本操作有何目的与意义。 三、将以上的理解加以运用与操作。第三章 需求分析3.1原理本课题要求采取邻接表的存储结构。邻接表是一种链式的存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等。 所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号，建立图的邻接表。此时要分两种情况：有向图与无向图。对于无向图，一条边的两的个顶点，互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。同时将终点的单链表表头插入一边结点，即起点。对于有向图，只能向起点的单链表的表头插入一个边结点，即终点。但不能反过来。至于邻接表的输出，由于不了解C+中的绘图操作，故采用for语句输出各结点，并配合一些符号完成邻接表的输出当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点，而这些操作都需要图的深度优先及广度优先遍历为基础。本系统将构建一个图，图的结点存储的是int 型数据。运行本系统可对该图进行链式结构输出、深度优先及广度优先遍历。3.2要求 （1）建立基于邻接表的图 （2）对图进行遍历 （3）输出遍历结果3.3系统总框架系统的主要功能是用邻接表存储结构在图中对顶点进行插入、删除、修改操作，并对图进行深度优先及广度优先遍历。总框架如下并对图进行深度优先及广度优先遍历。总框架如下：需要对无向图邻接矩阵建立请按0需要对无向图邻接矩阵输出请按1需要对无向图邻接表建立请按2需要对无向图邻接表输出请按3需要对无向图邻接表的深度遍历请按4需要对无向图邻接矩阵的深度遍历请按5需要对无向图邻接表的广度遍历请按6需要对无向图邻接矩阵的广度遍历请按7邻接表与邻接矩阵的建立与输出图的深度及广度优先遍历推出系统3.4运行环境 （1）硬件：计算机486/64M以上 （2）操作系统： WIN9x 以上/WIN2000/WIN XP/WIN ME （3）相关软件：vistualC+3.5程序的输入（包含输入的数据格式和说明） （1）输入顶点数,及各顶点信息(数据格式为整形) （2）输入边数,及权值(数据格式为整形)3.6开发工具C+语言第四章 算法与描述4.1图的深度优先遍历 假设初始状态是图中所有顶点未曾被访问，深度优先遍历可以从图的初始点出发，访问初始点，然后依次从v未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时仍有顶点未被访问到，则从另一个未被访问的顶点出发，重复上述过程，直至所有点都被访问到为止。这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。而且在深度优先搜索函数中必须设一标志数组以标记结点是否被访问。4.2具体过程应为 先访问初始点Vi，并标志其已被访问。此时定义一指向边结点的指针p，并建立一个while（）循环，以指针所指对象不为空为控制条件，当Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。图的存储与遍历算法-数据结构一样，也是从初始点Vi出发开始访问，访问初始点，标志其已被访问，并将已访问过的初始点序号i入队。当队列非空时进行循环处理，删除队首元素，第一次执行时k的值为i，即front=(front+1)%MaxLength。然后取Vk邻接表的表头指针int k=qfront; edgenode* p=GLk。当边结点指针p不为空时，通过while（）循环，并以p是否为空为控制条件，依次搜索Vk的每一个结点。若Vj没有被访问过则进行处理。访问完后，将p指向p-next。其中的while循环部分的代码如下：while(p!=NULL)/依次搜索Vk的每一个结点int j=p-adjvex; /Vj为Vk的一个邻接点if(!visitedj) /若Vj没有被访问过则进行处理coutjnext;这样就可以访问所有结点，完成图的广度优先遍历。第五章 源程序#include#includetypedef int datatype;typedef char vextype;#define maxsize 64typedef struct pnodedatatype data;struct pnode *next;linklist;typedef structlinklist *front,*rear;linkqueue;linkqueue *q;typedef structchar vexsmaxsize;int arcsmaxsizemaxsize;int vexnum,arcnum;graph;graph *ga;typedef struct nodeint adjvex; struct node *next;edgenode;typedef structvextype topvex;edgenode *link;topnode;topnode gl20;void setnull(linkqueue *q)q-front=(linklist *)malloc(sizeof(linklist);q-front-next=NULL;q-rear=q-front;int empty(linkqueue *q)if(q-front=q-rear)return 1;elsereturn 0;void enqueue(linkqueue *q,datatype x)q-rear-next=(linklist *)malloc(sizeof(linklist);q-rear=q-rear-next;q-rear-data=x;q-rear-next=NULL;int dequeue(linkqueue *q)linkqueue *s;if(empty(q)printf(队为空!);return NULL;elses=q-front; q-front=q-front-next;free(s);return(q-front-data);void creat_juzhe(graph *ga)/无向图邻接矩阵的建立int i,j,k;getchar();printf(请输入%d个元素:,ga-vexnum);for(i=0;ivexnum;i+)scanf(%c,&ga-vexsi);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)ga-arcsij=0;printf(请输入邻接的俩个顶点的下标:n);for(k=0;karcnum;k+)scanf(%d%d,&i,&j);ga-arcsij=1;ga-arcsji=1;void print_juzhe(graph *ga)/无向图邻接矩阵的输出int i,j;printf(建立好后的无向图的邻接矩阵为:n);for(i=0;ivexnum;i+)printf(%ct,ga-vexsi);for(j=0;jvexnum;j+) printf(%dt,ga-arcsij);printf(nnn);void creat_ljbiao(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;void print_ljbiao(topnode gl,int n)/无向图邻接表的输出int i;edgenode *p;printf(建立后的无向图的邻接表为:n);for(i=0;iadjvex);p=p-next;printf(n);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;void DFS(graph *ga,int i)/无向图邻接矩阵的深度遍历int j,n;printf(%c,ga-vexsi);visitedi=1;for(j=0;jvexnum;j+)if(ga-arcsij=1)&(visitedj=0)DFS(ga,j);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;void BFS(graph *ga,int k)/无向图邻接矩阵的广度遍历int i,j; linkqueue Q;setnull(&Q);printf(%c,ga-vexsk);visited_jzk=1;enqueue(&Q,k);while(!empty(&Q)i=dequeue(&Q);for(j=0;jvexnum;j+)if(ga-arcsij=1)&(!visited_jzj)printf(%c,ga-vexsj);visited_jzj=1;enqueue(&Q,j);void main()int i=1,j,n,e;graph ga;topnode *gl;while(i) printf(n0:无向图邻接矩阵的建立n1:无向图邻接表的建立n2:邻接矩阵的输出n3:邻接表的输出n4:邻接矩阵的深度遍历n5:邻接表的深度遍历n6:邻接矩阵的广度遍历n7:邻接表的广度遍历n);scanf(%d,&i);switch(i)case 0:printf(请输入顶点数和边数:); scanf(%d%d,&ga.vexnum,&ga.arcnum); creat_juzhe(&ga); break;case 1:printf(请输入顶点数和边数:); scanf(%d%d,&n,&e); creat_ljbiao(&gl,n,e); break;case 2:print_juzhe(&ga); break;case 3:print_ljbiao(&gl,n); break;case 4:printf(请输入要遍历的起始位置:); scanf(%d,&j); printf(邻接矩阵深度遍历后的结果为:); DFS(&ga,j); break;case 5:printf(请输入要遍历的起始位置:); scanf(%d,&j); printf(邻接表深度遍历后的结果为:); DFSL(&gl,j); break;case 6:printf(请输入要遍历的起始位置:); scanf(%d,&j); printf(邻接矩阵广度遍历后的结果为:); BFS(&ga,j,n); break;case 7:printf(请输入要遍历的起始位置:); scanf(%d,&j); printf(邻接表广度遍历后的结果为:); BFSL(&gl,j