第六次数据结构上机实验报告

1、 第16页（共16页）一、调试成功程序及说明1、题目： 1. 图的深度优先和广度优先遍历；算法思想：在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。源程序：#include<stdio.h> #include<malloc.h> #define max 100 /最大顶点个数 typedef struct /以下定义临接矩阵类型 int num

2、ber; /顶点编号 int info; /顶点其他信息,边的权值 VertexType; /顶点类型 typedef struct /图的定义 int edgesmaxmax; /邻接矩阵 int n,e; /顶点数和弧数 VertexType vexsmax; /存放定点信息 MGraph; /图的邻接矩阵类型 /定义邻接表类型 typedef struct ANode /弧的结点结构类型 int adjvex; /弧的重点位置,就是放值的 struct ANode *nextarc; /指向下一条弧的指针 int info; /存放弧的信息（权值） ArcNode; typedef st

3、ruct Vnode int data; /邻接表头结点的的类型ArcNode *firstarc; /指向第一条弧 VNode; typedef VNode AdjListmax; /AdjList是邻接表类型，把大表变成几个小的连接到一起 typedef struct AdjList adjlist; /邻接表 int n,e; /图中顶点数和和边数ALGraph; /图的邻接表类型 int visitedmax; /全局数组用于判断后面节点是否被访问过 void DispMat(MGraph g) /输出邻接矩阵 int i,j; for(i=0;i<g.n;i+) for(j=0

4、;j<g.n;j+) if(g.edgesij=0) printf("0 "); else printf("%d ",g.edgesij); printf("n"); void MatToList(MGraph g,ALGraph *&G) /将邻接矩阵g转换为邻接表G int i,j; int n=g.n; /n为顶点数 ArcNode *p; /弧节点结构的类型 G=(ALGraph *)malloc(sizeof(ALGraph);for(i=0;i<n;i+) /给大的邻接表中所有头结点的指针域副初值 G-

5、>adjlisti.firstarc=NULL; for(i=0;i<n;i+) /检查邻接矩阵的每个元素 for(j=0;j<n;j+) if(g.edgesij!=0) p=(ArcNode *)malloc(sizeof(ArcNode); /新申请一个节点空间，就是后 面的一段段小的节点 p->adjvex=j; /这是小节点的放值的域，只要他的列值，链式表只要说明节点之间有关系就行，指终点位置 p->info=g.edgesij; /存放边的权值 p->nextarc=G->adjlisti.firstarc; /将*p连接到表后 G->

6、;adjlisti.firstarc=p; G->e=g.e; G->n=g.n; void DispAdj(ALGraph *G) /输出邻接表 int i; ArcNode *p; /弧的类型 for(i=0;i<G->n;i+) p=G->adjlisti.firstarc;if(p!=NULL) printf(" %d: ",i); /这是那个大链表的头 while(p!=NULL) /顺着那个头向下查看 printf(" %d ",p->adjvex); /输出弧的终点 p=p->nextarc; pr

7、intf("n"); void change(int visited,ALGraph *G) /给全局变量visited赋初值 int i; for(i=0;i<G->n;i+) visitedi=0; void ListToMat(ALGraph *G,MGraph g) /将邻接表转换为邻接矩阵的形式 int i,j; int n=G->n; ArcNode *p; for(i=0;i<n;i+)for(j=0;j<n;j+) g.edgesij=0; for(i=0;i<n;i+) p=G->adjlisti.firstarc

8、; while(p!=NULL) g.edgesip->adjvex=p->info; p=p->nextarc; g.n=n; g.e=G->e; void DFS(ALGraph *G,int v) /递归深度优先遍历 ArcNode *p; /change(visited,G); visitedv=1; /第一个点设为已被访问并输出，接着以他为主进行遍历 printf(" %d",v); p=G->adjlistv.firstarc; while(p!=NULL) if(visitedp->adjvex=0) DFS(G,p->

9、;adjvex); p=p->nextarc; void BFS(ALGraph *G,int v) /广度优先遍历，一个点先找和其有关的所有节点，在接着按步骤继续 ArcNode *p;int queuemax,front=0,rear=0; /定义循环队列并初始化 int visitedmax; int w,i; for(i=0;i<G->n;i+) visitedi=0;printf(" %d ",v); /把输入的第v个作为第一个广度遍历的节点，一直这样进行下去 visitedv=1; rear=(rear+1)%max; /要入队了 queuer

10、ear=v; /把v入队 while(front!=rear) /队列不为空的时候 front=(front+1)%max; /要出队了 w=queuefront; p=G->adjlistw.firstarc; /跟前面差不多开始查找与顶点w邻接的第一个顶点了while(p!=NULL) if(visitedp->adjvex=0) /就是当前节点未被访问 printf("%d ",p->adjvex);visitedp->adjvex=1; rear=(rear+1)%max; /又要入队了，马上要重复之前的操作了queuerear=p->

11、adjvex; p=p->nextarc; printf("n"); void main() int i,j;MGraph g;ALGraph *G; /没有定义过的邻接表类型加上* int Amax6; printf("请输入邻接矩阵：n"); for(i=0;i<6;i+) for(j=0;j<6;j+) scanf("%d",&Aij); g.n=6; g.e=10; for(i=0;i<g.n;i+) for(j=0;j<g.n;j+) g.edgesij=Aij; /这是给邻接矩阵赋值

12、printf("这是图的邻接矩阵的形式："); printf("n"); DispMat(g); /输出邻接矩阵的函数 G=(ALGraph *)malloc(sizeof(ALGraph); MatToList(g,G); printf("这是图的邻接表的形式："); printf("n"); DispAdj(G); printf("从顶点0开始的深度优先遍历：n"); DFS(G,0); printf("n"); printf("从顶点0开始的广度优先遍历：n&

13、quot;); BFS(G,0); printf("n"); 运行结果：2、题目：2拓扑排序；算法思想：(1) 选择一个入度为0的顶点并输出之；(2) 从网中删除此顶点及所有出边。循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。源程序：#include<iostream> using namespace std; #define maxsize 50 struct node int adjvex; node * next; ; struct graph int vexter; int in; node * f

14、irstedge; ; typedef struct int *base; int *top; int stacksize; sqstack; void initstack(sqstack &S) S.base=(int *)malloc(sizeof(int); S.top=S.base; S.stacksize=maxsize+1; void createadlist(graph inDegree,int n,int e)/创建邻接链表 int i,k,j; node * q; for(i=1;i<=n;i+) inDegreei.vexter=i; inDegreei.in

15、=0; inDegreei.firstedge=NULL; for(k=1;k<=e;k+) cout<<"依次输入每一条边(数字)：" cout<<"从" cin>>i; cout<<"邻接到" cin>>j; cout<<'/n' inDegreej.in+; q=(node *)malloc(sizeof(struct node); q->adjvex=j; q->next=inDegreei.firstedge; inDe

16、greei.firstedge=q; void TopoSort(graph inDegree,int n) int i,v,count=0; sqstack S; node * p; initstack(S); for(i=1;i<=n;i+) if(inDegreei.in=0) *S.top+=i; while(S.top!=S.base) v=*-S.top; cout<<v<<"/t" count+; p=inDegreev.firstedge; while(p!=NULL) inDegreep->adjvex.in-; if(inDegreep->adjvex.in=0) *S.top+=p->adjvex; p=p->next; cout<<endl; if(count<n) cout<<"有回路"<<endl; else cout<<