数据结构上机实验8.doc

数据结构上机实验（八） 图 班级： 学号： 姓名： 上机时间： 地点： 一、实验目的 掌握图的各种存储结构，包括邻接矩阵和邻接表等。 掌握图的基本运算，包括创建图、输出图、深度优先遍历、广度优先遍历算法等。 二、实验内容 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()函数等等。#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;in;i++) //给邻接表中所有头结点的指针域置初值 G-adjlist[i].firstarc=NULL; for (i=0;in;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;in;i++) //g.edges[i][j]赋初值0 for (j=0;jn;j++) g.edges[i][j]=0; for (i=0;in;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;ig.vexnum;i++) { for (j=0;jg.vexnum;j++) if (g.edges[i][j]==INF) printf(%3s,∞);