《数据结构实验报告图的遍历》由会员分享，可在线阅读，更多相关《数据结构实验报告图的遍历（18页珍藏版）》请在金锄头文库上搜索。
1、第 3 小组实验报告1 数据结构试验报告实验四 图的存储及应用实验题目：图的遍历问题专业班级：计科系1405班组长：张纪远（ 2014100518 ）组员：周振军（ 2014100551 ）朱新祥（ 2014100552 ）梁丽蓉（ 2014100526 ）段慧娟（ 2014100512 ）2016年 6 月 1 日第 3 小组实验报告2 实验报告实验类型 _综合设计 _实验室 _软件实验室三 _ 一、 实验题目 图的存储及应用 二、 实验目的和要求1掌握图的存储思想及其存储实现2掌握图的深度、广度优先遍历算法思想及其程序实现3掌握图的常见应用算法的思想及其程序实现三、 需求分析1问题描述使用
2、菜单实现图的相关算法, 如键盘输入以下结点数据：太原、成都、 北京、上海、天津、大连、河北，建立一个有向图或无向图（自定）的邻接表并输出该邻接表；在图的邻接表的基础上计算各顶点的度，并输出；以有向图的邻接表为基础实现输出它的拓扑排序序列；采用邻接表存储实现无向图的深度优先遍历；采用邻接表存储实现无向图的广度优先遍历；采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法2. 设计分析调用菜单项，分别调用相应的子函数。注意顶点存储地名，使用字符数组来实现。3. 结构类型定义typedef char vextype10;/*顶点数据类型 */ typedef int edgetype;/*边数据
3、类型 */ typedef struct vextype vexMAXSIZE; edgetype arcMAXSIZEMAXSIZE; int vexnum,arcnum; Mgraph; typedef struct node int adjvex; struct node *nextEdgeNode; typedef struct node vextype vex; EdgeNode * firstedge;VexNode; typedef struct VexNode adjvexMAXSIZE; 第 3 小组实验报告3 int n,e;ALGraph; 四、 概要设计为了实现上述程序
4、功能，代码如下：#include #include #include typedef struct node/边表结点int adj;/边表结点数据域struct node *next; node; typedef struct vnode/顶点表结点char name20; node *fnext; vnode,AList20; typedef struct AList List;/邻接表int v,e;/顶点树和边数*Graph; / 建立无向邻接表Graph CreatDG() Graph G; int i,j,k; node *s; G=malloc(20*sizeof(vnode);
5、 printf(“请输入图的顶点数和边数(空格隔开 ) ：“); scanf(“%d%d“,/读入顶点数和边数for(i=0;iv;i+) printf(“请输入图中第 %d元素： “,i+1); scanf(“%s“,G-Listi.name);/读入顶点信息第 3 小组实验报告4 G-Listi.fnext=NULL;/边表置为空表 for(k=0;ke;k+) printf(“请请输入第 %d条边的两顶点序号( 空格隔开 ) ：“,k+1); scanf(“%d%d“,/读入边（ Vi,Vj ）的顶点对序号; s=(node *)malloc(sizeof(node);/生成边表结点s-
6、adj=j; s-next=G-Listi.fnext; G-Listi.fnext=s;/将新结点 *s 插入顶点Vi 的边表头部s=(node *)malloc(sizeof(node); s-adj=i;/邻接点序号为i s-next=G-Listj.fnext; G-Listj.fnext=s;/ 将新结点 *s 插入顶点 Vj 的边表头部 return G; / 有向邻接图Graph CreatAG() Graph G; int i,j,k; node *q; G=malloc(20*sizeof(vnode); printf(“请输入图的顶点数和边数【空格隔开】：“); scanf
7、(“%d%d“, for (i=0;iv;i+) printf(“请输入图中第 %d元素： “,i+1); scanf(“%s“, /读入顶点信息G-Listi.fnext=NULL; for (k=0;ke;k+) printf(“请请输入第 %d边的两顶点序号【空格隔开】：“,k+1); scanf(“%d%d“, 第 3 小组实验报告5 q=(node *)malloc(sizeof(node); /生成新边表结点s q-adj=j; /邻接点序号为j q-next=G-Listi.fnext; G-Listi.fnext=q; return G; / 输出图的邻接表void Print
8、(Graph G) int i; node *p; printf(“t=邻接表 =n“); for(i=0;iv;i+) p=G-Listi.fnext; printf(“%d | %3s“,i,G-Listi.name); while(p) printf(“-%3s“,G-Listp-adj.name); printf(“-%d“,p-adj); p=p-next; printf(“n“); typedef struct char vex20; Lists20; typedef struct Lists l; int edge2020;/邻接矩阵int v1,e1;/顶点数和弧数AGraph
9、; typedef struct 第 3 小组实验报告6 int data; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */ int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */ ClosEdge20; /* 用普里姆算法求最小生成树时的辅助数组 */ void CreateAN(AGraph *G1) /* 构造邻接矩阵结构的图G */ int i,j,k,w; printf(“请输入图的顶点数和边数（空格隔开）：“); scanf(“%d%d“,/读入顶点数和边数for(i=1;iv1;i+) printf(“请输入图 %d号元素： “,
10、i); scanf(“%s“,/读入顶点信息 for(i=1;iv1;i+)/初始化邻接矩阵for(j=1;jv1;j+) G1-edgeij = 9; for(k=1;ke1;k+) printf(“请输入两顶点及边的权值（空格隔开）：“); scanf(“%d%d%d“, G1-edgeij=w; G1-edgeji=w; void PrintAN(AGraph *G1) int i,j; printf(“t=邻接矩阵 =n“); for(i=1;iv1;i+) for(j=1;jv1;j+) printf(“%3d“,G1-edgeij); printf(“n“); / 输出各顶点的度数
11、第 3 小组实验报告7 void Du(Graph G) int i,j; node *p; printf(“nn“); for(i=0;iv;i+) p=G-Listi.fnext; printf(“顶点 %2s的度为： “,G-Listi.name); j=0; while(p) j+; p=p-next; printf(“%dn“,j); / 栈typedef struct stack int x; struct stack *next; stack; int push(stack *s,int i) stack *p; p=(stack *)malloc(sizeof(stack);
12、p-x=i; p-next=s-next; s-next=p; return 1; int pop(stack *s,int j) stack *p=s-next;/保存栈顶指针j=p-x; s-next=p-next; /将栈顶元素摘下第 3 小组实验报告8 free(p);/释放栈顶空间return j; / 拓扑排序void Topo(Graph G,stack *s) int i,k, count; int j=0; int indegree20=0; node *p; for(i=0;iv;i+) p=G-Listi.fnext; while(p!=NULL) indegreep-a
13、dj+; p=p-next; for(i=0;iv;i+) if(indegreei=0) push(s,i); count=0; while(s-next!=NULL) i=pop(s,j); printf(“%2s “,G-Listi.name); +count; for(p=G-Listi.fnext;p!=NULL;p=p-next) k=p-adj; if(!(-indegreek) push(s,k); if(countv) printf(“有回路 !“); 第 3 小组实验报告9 void DFS(Graph G,int i,int flag) node *p; printf(“
14、%2s “,G-Listi.name); flagi=1; p=G-Listi.fnext; while(p) if(!flagp-adj) DFS(G,p-adj,flag); p=p-next; / 深度优先遍历void DFSTravel(Graph G) int i; int flag20;/标志数组for(i=0;iv;i+) flagi=0; for(i=0;iv;i+) if(!flagi) DFS(G,i,flag); / 建立队列typedef struct int *elem; int front, rear; *Queue; / 队列初始化void InitQueue(Q
15、ueue Q) Q-elem=(int *)malloc(20*sizeof(int); if(!Q-elem) exit(0); Q-front=Q-rear=0; 第 3 小组实验报告10 / 入队void Enter(Queue Q, int e) if(Q-rear + 1)%20!= Q-front) Q-elemQ-rear =e; else printf(“队列满 !n“); Q-rear=(Q-rear+1)%20; / 出队void Leave(Queue Q, int e) if(Q-rear != Q-front) e=Q-elemQ-front; else printf(“队列空 !n“); Q-front=(Q-front+1)%20; / 广度优先遍历vo
