数据结构上机实验（八）图班级：学号：姓名：上机时间：地点：一、实验目的1.掌握图的各种存储结构，包括邻接矩阵和邻接表等。

2.掌握图的基本运算，包括创建图、输出图、深度优先遍历、广度优先遍历算法等。

二、实验内容1．实现图的相关运算，并在此基础上设计一个主程序完成如下功能：（以P234图8.26所示的有向图G为例）（1）建立如图8.26所示的有向图G的邻接矩阵并输出；（2）由有向图G的邻接矩阵产生邻接表并输出；（3）再由（2）的邻接表产生对应的邻接矩阵并输出。

2．实现图的遍历运算，并在此基础上设计一个主程序完成如下功能：（以P234图8.26所示的有向图G为例）（1）输出如图8.26所示的有向图G从顶点0开始的深度优先遍历序列（递归算法）；（2）输出如图8.26所示的有向图G从顶点0开始的深度优先遍历序列（非递归算法）；（3）输出如图8.26所示的有向图G从顶点0开始的广度优先遍历序列。

三、实验过程1．了解常用函数所在的头文件stdlib.hstdlib 头文件里包含了C语言的一些函数该文件包含了的C语言标准库函数的定义stdlib.h里面定义了五种类型、一些宏和通用工具函数。

类型例如size_t、wchar_t、div_t、ldiv_t和lldiv_t；宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX 和MB_CUR_MAX等等；常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、srand()、exit()等等。

具体的内容你自己可以打开编译器的include目录里面的stdlib.h头文件看看。

conio.hconio.h不是C标准库中的头文件。

conio是Console Input/Output（控制台输入输出）的简写，其中定义了通过控制台进行数据输入和数据输出的函数，主要是一些用户通过按键盘产生的对应操作，比如getch()函数等等。

&表示引用传递。

在函数参数表中，出现带&这个的形参，表示引用传递。

2．程序实现（以下代码仅起参考作用）（1）图的相关运算#include <stdio.h>#include <malloc.h>#include "graph.h"#define INF 32767 //INF表示∞void MatToList(MGraph g,ALGraph *&G)//将邻接矩阵g转换成邻接表G{int i,j,n=g.vexnum; //n为顶点数ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph));for (i=0;i<n;i++) //给邻接表中所有头结点的指针域置初值G->adjlist[i].firstarc=NULL;for (i=0;i<n;i++) //检查邻接矩阵中每个元素for (j=n-1;j>=0;j--)if (g.edges[i][j]!=0) //邻接矩阵的当前元素不为0{p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点*pp->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc; //将*p链到链表后G->adjlist[i].firstarc=p;}G->n=n;G->e=g.arcnum;}void ListToMat(ALGraph *G,MGraph &g)//将邻接表G转换成邻接矩阵g{int i,j,n=G->n;ArcNode *p;for (i=0;i<n;i++) //g.edges[i][j]赋初值0for (j=0;j<n;j++)g.edges[i][j]=0;for (i=0;i<n;i++){p=G->adjlist[i].firstarc;while (p!=NULL){g.edges[i][p->adjvex]=p->info;p=p->nextarc;}}g.vexnum=n;g.arcnum=G->e;}void DispMat(MGraph g)//输出邻接矩阵g{int i,j;for (i=0;i<g.vexnum;i++){for (j=0;j<g.vexnum;j++)if (g.edges[i][j]==INF)printf("%3s","∞");elseprintf("%3d",g.edges[i][j]);printf("\n");}}void DispAdj(ALGraph *G)//输出邻接表G{int i;ArcNode *p;for (i=0;i<G->n;i++){p=G->adjlist[i].firstarc;if (p!=NULL) printf("%3d: ",i);while (p!=NULL){printf("%3d",p->adjvex);p=p->nextarc;}printf("\n");}}void main(){int i,j;MGraph g,g1;ALGraph *G;int A[MAXV][6]={{0,5,0,7,0,0},{0,0,4,0,0,0},{8,0,0,0,0,9},{0,0,5,0,0,6},{0,0,0,5,0,0},{3,0,0,0,1,0}};g.vexnum=6;g.arcnum=10;for (i=0;i<g.vexnum;i++)for (j=0;j<g.vexnum;j++)g.edges[i][j]=A[i][j];printf("\n");printf(" 有向图G的邻接矩阵:\n");DispMat(g);G=(ALGraph *)malloc(sizeof(ALGraph));printf(" 图G的邻接矩阵转换成邻接表:\n");MatToList(g,G);DispAdj(G);printf(" 图G的邻接表转换成邻接邻阵:\n");ListToMat(G,g1);DispMat(g1);printf("\n");}（2）图的遍历运算#include <stdio.h>#include <malloc.h>#include "graph.h"int visited[MAXV]; //全局数组#define INF 32767 //INF表示∞void MatToList(MGraph g,ALGraph *&G)//将邻接矩阵g转换成邻接表G{int i,j,n=g.vexnum; //n为顶点数ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph));for (i=0;i<n;i++) //给邻接表中所有头结点的指针域置初值G->adjlist[i].firstarc=NULL;for (i=0;i<n;i++) //检查邻接矩阵中每个元素for (j=n-1;j>=0;j--)if (g.edges[i][j]!=0) //邻接矩阵的当前元素不为0{p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点*pp->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc; //将*p链到链表后G->adjlist[i].firstarc=p;}G->n=n;G->e=g.arcnum;}void DispAdj(ALGraph *G)//输出邻接表G{int i;ArcNode *p;for (i=0;i<G->n;i++){p=G->adjlist[i].firstarc;if (p!=NULL) printf("%3d: ",i);while (p!=NULL){printf("%3d",p->adjvex);p=p->nextarc;}printf("\n");}}void DFS(ALGraph *G,int v){ArcNode *p;visited[v]=1; //置已访问标记printf("%3d",v); //输出被访问顶点的编号p=G->adjlist[v].firstarc; //p指向顶点v的第一条弧的弧头结点while (p!=NULL){if (visited[p->adjvex]==0) //若p->adjvex顶点未访问,递归访问它DFS(G,p->adjvex);p=p->nextarc; //p指向顶点v的下一条弧的弧头结点}}void DFS1(ALGraph *G,int v) //非递归深度优先算法{ArcNode *p;ArcNode *St[MAXV];int top=-1,w,i;for (i=0;i<G->n;i++)visited[i]=0; //顶点访问标志均置成0printf("%3d",v); //访问顶点vvisited[v]=1;top++; //将顶点v的第一个相邻顶点进栈St[top]=G->adjlist[v].firstarc;while (top>-1) //栈不空循环{p=St[top]; top--; //出栈一个顶点作为当前顶点while (p!=NULL) //查找当前顶点的第一个未访问的顶点{w=p->adjvex;if (visited[w]==0){printf("%3d",w); //访问wvisited[w]=1;top++; //将顶点w的第一个顶点进栈St[top]=G->adjlist[w].firstarc;break; //退出循环}p=p->nextarc; //找下一个相邻顶点}}printf("\n");}void BFS(ALGraph *G,int v){ArcNode *p;int queue[MAXV],front=0,rear=0; //定义循环队列并初始化int visited[MAXV]; //定义存放结点的访问标志的数组int w,i;for (i=0;i<G->n;i++) visited[i]=0; //访问标志数组初始化printf("%3d",v); //输出被访问顶点的编号visited[v]=1; //置已访问标记rear=(rear+1)%MAXV;queue[rear]=v; //v进队while (front!=rear) //若队列不空时循环{front=(front+1)%MAXV;w=queue[front]; //出队并赋给wp=G->adjlist[w].firstarc; //找与顶点w邻接的第一个顶点while (p!=NULL){if (visited[p->adjvex]==0) //若当前邻接顶点未被访问{printf("%3d",p->adjvex); //访问相邻顶点visited[p->adjvex]=1; //置该顶点已被访问的标志rear=(rear+1)%MAXV; //该顶点进队queue[rear]=p->adjvex;}p=p->nextarc; //找下一个邻接顶点}}printf("\n");}void main(){int i,j;MGraph g;ALGraph *G;int A[MAXV][6]={{0,5,0,7,0,0},{0,0,4,0,0,0},{8,0,0,0,0,9},{0,0,5,0,0,6},{0,0,0,5,0,0},{3,0,0,0,1,0}};g.vexnum=6;g.arcnum=10;for (i=0;i<g.vexnum;i++)for (j=0;j<g.vexnum;j++)g.edges[i][j]=A[i][j];G=(ALGraph *)malloc(sizeof(ALGraph));MatToList(g,G); //图G的邻接矩阵转换成邻接表printf("图G的邻接表:\n");DispAdj(G);printf("从顶点0开始的DFS(递归算法):\n");DFS(G,0);printf("\n");printf("从顶点0开始的DFS(非递归算法):\n");DFS1(G,0);printf("从顶点0开始的BFS(递归算法):\n");BFS(G,0);printf("\n");}3．运行结果（包括程序如何使用，输入数据和输出结果）及分析四、实验体会。