文档库

最新最全的文档下载
当前位置:文档库 > 数据结构上机实验8

数据结构上机实验8

数据结构上机实验(八)图

班级:学号:姓名:

上机时间:地点:

一、实验目的

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.h

stdlib 头文件里包含了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.h

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

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

&表示引用传递。在函数参数表中,出现带&这个的形参,表示引用传递。2.程序实现(以下代码仅起参考作用)

(1)图的相关运算

#include

#include

#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;iadjlist[i].firstarc=NULL;

for (i=0;i

for (j=n-1;j>=0;j--)

if (g.edges[i][j]!=0) //邻接矩阵的当前元素不为0

{

p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点*p

p->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

for (j=0;j

g.edges[i][j]=0;

for (i=0;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

{

for (j=0;j

if (g.edges[i][j]==INF)

printf("%3s","∞");

else

printf("%3d",g.edges[i][j]);

printf("\n");

}

}

void DispAdj(ALGraph *G)

//输出邻接表G

{

int i;

ArcNode *p;

for (i=0;in;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

for (j=0;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

#include

#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;iadjlist[i].firstarc=NULL;

for (i=0;i

for (j=n-1;j>=0;j--)

if (g.edges[i][j]!=0) //邻接矩阵的当前元素不为0

{

p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点*p

p->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;in;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;in;i++)

visited[i]=0; //顶点访问标志均置成0

printf("%3d",v); //访问顶点v

visited[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); //访问w

visited[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;in;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]; //出队并赋给w

p=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

for (j=0;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.运行结果(包括程序如何使用,输入数据和输出结果)及分析四、实验体会