数据结构实验五实验报告

1、.数据结构实验报告实验五图子系统实验题目：图的遍历问题专业班级：网络工程 1002班组 长：王星 （30）组 员：郭坤铭 （43）张磊 （44）2012年 5月18日.实验报告实验类型_综合_实验室_软件实验室二_一、 实验题目图的遍历问题二、实验目的和要求1、掌握图的存储思想及其存储实现2、掌握图的深度、广度优先遍历算法思想及其程序实现3、掌握图的常见应用算法的思想及其程序实现三、需求分析本演示程序用c+6.0矩阵存储实现无向图的最小生成树的PRIM设计一个简单的菜单，分别调试上述算法。四、 概要设计为了实现上述程序功能，需要定义如下内容基本数据类型定义如下：typedef struct n

2、odeint 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 CreatAG() /有向邻接图void Print(Graph G)/输出图的邻接表void CreateAN(AGraph *G1) /构造邻接矩阵结构的图Gvoid Du(Graph G)void DFSTravel(Graph G)void BFSTravel(

3、Graph G)五、详细设计#include#include#includetypedef struct node/边表结点int adj;/边表结点数据域struct node *next;node;typedef struct vnode/顶点表结点char name20;node *fnext;vnode,AList20;typedef structAList List;/邻接表.int v,e;/顶点树和边数*Graph;/建立无向邻接表Graph CreatDG()Graph G;int i,j,k;node *s;G=malloc(20*sizeof(vnode);printf(请

4、输入图的顶点数和边数(空格隔开)：);scanf(%d%d,&G-v,&G-e);/读入顶点数和边数for(i=0;iv;i+)printf(请输入图中第%d元素：,i+1);scanf(%s,G-L);/读入顶点信息G-Listi.fnext=NULL;/边表置为空表for(k=0;ke;k+)printf(请请输入第 %d 条边的两顶点序号 (空格隔开)：,k+1);scanf(%d%d,&i,&j);/读入边（Vi,Vj）的顶点对序号;s=(node *)malloc(sizeof(node);/生成边表结点s-adj=j;s-next=G-Listi.fnext;G-

5、Listi.fnext=s;/将新结点*s插入顶点Vi的边表头部s=(node *)malloc(sizeof(node);s-adj=i;/邻接点序号为is-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(%d%d,&G-v,&G-e);.for (i=0;iv;i+)printf(请输入图中第%d元素：,i

6、+1);scanf(%s,&G-L); G-Listi.fnext=NULL;for (k=0;ke;k+)printf(请请输入第%dscanf(%d%d,&i,&j);q=(node *)malloc(sizeof(node); sq-adj=j;/邻接点序号为jq-next=G-Listi.fnext;G-Listi.fnext=q;return G;/输出图的邻接表void Print(Graph G)int i;node *p;printf(t=邻接表=n);for(i=0;iv;i+)p=G-Listi.fnext;printf(%d | %3s,i,G-List

7、);while(p)printf(-%3s,G-L);printf(-%d,p-adj);p=p-next;printf(n);typedef struct char vex20;Lists20;typedef structLists l;int edge2020;/邻接矩阵int v1,e1;/顶点数和弧数.AGraph;typedef structint data; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点*/intlowcost;/* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */ClosEdge20; /*用普里姆算法求最

8、小生成树时的辅助数组*/void CreateAN(AGraph *G1)/* 构造邻接矩阵结构的图G */int i,j,k,w;printf(请输入图的顶点数和边数（空格隔开）：);scanf(%d%d,&G1-v1,&G1-e1);/读入顶点数和边数for(i=1;iv1;i+)printf(请输入图%d号元素：,i);scanf(%s,&G1-li.vex);/读入顶点信息for(i=1;iv1;i+)/初始化邻接矩阵for(j=1;jv1;j+)G1-edgeij = 9;for(k=1;ke1;k+)printf(请输入两顶点及边的权值（空格隔开）：);scanf(%d%d%d,&

9、i,&j,&w);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);/输出各顶点的度数void Du(Graph G)int i,j;.node *p;printf(nn);for(i=0;iv;i+)p=G-Listi.fnext;printf(顶点%2s的度为：,G-L);j=0;while(p)j+;p=p-next;printf(%dn,j);/栈ty

10、pedef struct stackint x;struct stack *next;stack;int push(stack *s,int i)stack *p;p=(stack *)malloc(sizeof(stack);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;free(p);/释放栈顶空间return j;/拓扑排序void Topo(Graph G,stack *s)int i,k, count;int j=0;int

11、 indegree20=0;.node *p;for(i=0;iv;i+)p=G-Listi.fnext;while(p!=NULL)indegreep-adj+;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-L);+count;for(p=G-Listi.fnext;p!=NULL;p=p-next)k=p-adj;if(!(-indegreek)push(s,k);if(countv) printf(有回路!);void

12、 DFS(Graph G,int i,int flag)node *p;printf(%2s ,G-L);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 structint *elem;int front, rear;*Queue;

13、/队列初始化void InitQueue(Queue Q)Q-elem=(int *)malloc(20*sizeof(int);if(!Q-elem)exit(0);Q-front=Q-rear=0;/入队void Enter(Queue Q, int e)if(Q-rear + 1)%20!= Q-front)Q-elemQ-rear =e;elseprintf(队列满!n);Q-rear=(Q-rear+1)%20;/出队void Leave(Queue Q, int e)if(Q-rear != Q-front)e=Q-elemQ-front;elseprintf(队列空!n);Q-f

14、ront=(Q-front+1)%20;/广度优先遍历void BFSTravel(Graph G)Queue Q;.node *p;int i,j=0;int flag20;/标志数组Q=malloc(sizeof(20);InitQueue(Q);for(i=0;iv;i+)flagi=0;for(i=0;iv;i+)if(flagi=0)flagi=1;printf(%2s,G-L);Enter(Q,i);while(Q-front!=Q-rear)Leave(Q,j);/队头元素出队并置为jp=G-Listj.fnext;while(p!=NULL)if(flagp-

15、adj=0)printf(%2s ,G-L);flagp-adj=1;Enter(Q,p-adj);p=p-next;int minimum(ClosEdge cl,int vnum)int i;int w,p;w=1000;for(i=1;i=vnum;i+)if(cli.lowcost!=0&cli.lowcostw)w=cli.lowcost;p=i;return p;void Prim(AGraph *G1,int u)ClosEdge closedge;.int i,j,k;for(j=1;jv1;j+) /*辅助数组初始化*/if(j!=u)closedg

16、ej.data=u;closedgej.lowcost=G1-edgeuj;closedgeu.lowcost=0; /*初始，U=u */for(i=1;iv1;i+)k=minimum(closedge,G1-v1); /*求出生成树的下一个顶点*/printf(%d-%dn,closedgek.data,k); /* 输出生成树的边*/closedgek.lowcost=0; /*第k顶点并入U集*/for(j=1;jv1;j+)/* 新顶点并入U后，修改辅助数组*/if(G1-edgekjedgekj;/菜单列表void menu()printf(t* 图 的 遍 历 问 题*n);p

17、rintf(tt- 1. 建 立 无 向 邻 接 图-n);printf(tt- 2. 建 立 有 向 邻 接 图-n);printf(tt- 3. 建 立 无 向 邻 接 矩 阵-n);printf(tt- 4. 输 出 各 顶 点 的 度-n);printf(tt-n);5.拓扑排序printf(tt-n);6. 深 度 优 先 遍 历.printf(tt-n);7. 广 度 优 先 遍 历printf(tt- 8.prim 算 法 生 成 最 小 生 成 树-n);printf(tt-n);9-退出printf(t*n);/主函数void main()Graph G;AGraph G1;

18、int choice,u;stack *s=(stack *)malloc(sizeof(stack);s-next =NULL;while(1)menu();printf(请输入选择:);scanf(%d,&choice);switch(choice)case1:G=CreatDG();Print(G);printf(nn);break;case2:G=CreatAG();Print(G);printf(nn);break;case3:CreateAN(&G1);PrintAN(&G1);printf(nn);break;case4:Du(G);printf(nn);break;case5:printf(序:);Topo(G,s);printf(nn);break;case6:printf(历:);DFSTravel(G);printf(nn);break;case7:printf(拓扑排遍遍深度优优先先广度历:);BFSTravel(G);p