数据结构实验报告(图).doc

《数据结构实验报告(图).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期：12月13号12月20号专业班级：媒体161组别：无姓名：学号：实验报告内容验证性实验一、预习准备：实验目的：1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围；2、熟练掌握几种常见图的遍历方法及遍历算法；实验环境：Widows操作系统、VC6.0实验原理：1.定义：基本定义和术语图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(Vertex)的非空有限集E(G)是边(Edge)的有限集

2、合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的,）。邻接矩阵——表示顶点间相联关系的矩阵设G=(V,E)是有n³1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和邻接表实现：为图中每个顶点建立一个单链表，第i个单链表中的结点

3、表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）特点:无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。图的遍历从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n

4、2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e为无向图中边的数或有向图中弧的数。实验内容和要求：选用任一种图的存储结构，建立如下图所示的带权有向图：4050C10DB3020AE要求：1、建立边的条数为零的图；2、依次将图的边以及相应的权值插入，建立如上图所示的图，并将结点集合和权值集合输出；3、对所建立的图进行深度优先搜索或广度优先搜索，输出图的遍历序列；算法思想：首先，选定所使用的图的存储结构（邻接矩阵存储或邻接表存储），建立图的结构体定义。根据所选用的结构建立边条数为零的图，依次插入图的结点和图的各有向边

5、以及权值weight；再次，将图的结点集合以及权值集合输出，以验证所建立图的正确性；最后，调用图的遍历函数，实现图的深度优先遍历或广度优先遍历，并输出遍历序列。一、实验过程：程序流程图：实验中的关键语句：voidDepthFirstSearch(AdjList*adjlist){inti;int*visited;visited=(int*)malloc(sizeof(int)*adjlist->vexnum);for(i=0;ivexnum;i++)visited[i]=0;printf("深度优先搜索:");for(

6、i=0;ivexnum;i++){if(visited[i]==1)continue;VisitNext(adjlist,i,visited);}printf("");}voidBreadthFirstSearch(AdjList*adjlist){ArcNode*temp=NULL;intnth;VexQueue*vexqueue=NULL;inti;int*visited=NULL;visited=(int*)malloc(sizeof(int)*adjlist->vexnum);for(i=0;i

7、vexnum;i++)visited[i]=0;printf("广度优先搜索:");for(i=0;ivexnum;i++){if(visited[i]==1)continue;vexqueue=CreateQueue();Push(vexqueue,i);while(!IsEmpty(vexqueue)){Pop(vexqueue,&nth);if(visited[nth]==1)continue;visit(adjlist,nth,&visited);temp=adjlist->vertex[nth].head;w

8、hile(temp){Push(vexqueue,temp->adjvex-1);temp=temp->next;}}}printf("