图的存储结构与遍历 数据结构实验.docx

1、图的存储结构与遍历 数据结构实验实验报告June 112015姓名：陈斌 学号：E11314079 专业：13计算机科学与技术数据结构 第七次实验学号 E11314079 专业 计算机科学与技术 姓名 陈 斌 实验日期 2015.06.11 教师签字 成绩 实 验 报 告【实验名称】 图的存储结构与遍历 【实验目的】 (1) 掌握图的相关概念；(2) 掌握图的存储结构；(3) 掌握图的遍历算法并编程实现。【实验内容】编写一个程序，实现图的相关运算，并在此基础上设计一个主程序，完成如下功能：(1) 建立如教材图7.9所示的有向图G的邻接矩阵，并分别输出顶点表和邻接矩阵。(2) 由有向图G的邻接矩

2、阵产生邻接表，并依次输出每一顶点和其邻接表。(3) 再由（2）的邻接表产生对应的邻接矩阵，并输出该矩阵。(4) 在图G的邻接矩阵存储表示基础上，输出从顶点V1开始的深度优先遍历序列（递归算法）。(5) 在图G的邻接表存储表示基础上，输出从顶点V1开始的广度优先遍历序列。(6) 利用非递归算法重解任务（4）（选做）。 源代码：head.h: #include#include#include /malloc( )#include / INT ,MAX#include /EOF,NULL#include /atoi( )#include /eof( )#include /floor( ),ceil(

3、 ),abs( )#include /exit( )#include /cout,cin/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/OVERFLOW 在 math.h 中已定义为3typedef int Status;typedef int Boolean; / 布尔类型main.cpp:#includehead.h#define MAX_NAME 5 /* 顶点字符串的最大长度+1 */#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 *

4、/typedef int VRType;typedef int InfoType;typedef char VertexTypeMAX_NAME;#define INFINITY INT_MAX /* 用整型最大值代替 */#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */typedef enumDG,DN,AG,ANGraphKind; /* 有向图,有向网,无向图,无向网 */*图的数组(邻接矩阵)存储表示 */typedef struct VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否;对带权图，c则为权值类型 */ Inf

5、oType *info; /* 该弧相关信息的指针(可无) */ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; /* 顶点向量 */ AdjMatrix arcs; /* 邻接矩阵 */ int vexnum,arcnum; /* 图的当前顶点数和弧数 */ GraphKind kind; /* 图的种类标志 */MGraph;/*图的邻接表存储表示 */typedef struct ArcNode int adjvex; /* 该弧所指向的顶点的位置 */

6、struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType *info; /* 该弧相关信息的指针 */ArcNode; /* 表结点 */typedef struct VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */VNode,AdjListMAX_VERTEX_NUM; /* 头结点 */typedef struct AdjList vertices; int vexnum,arcnum; /* 图的当前顶点数和弧数 */ int kind;

7、/* 图的种类标志 */ALGraph;int LocateVex(MGraph G,VertexType u) /* 初始条件:图G存在,u和G中顶点有相同特征 */* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ for(int i=0;iG.vexnum;+i) if(strcmp(u,G.vexsi)=0) return i; return -1;Status CreateDG(MGraph &G) /* 采用数组(邻接矩阵)表示法,构造有向图G */ int i,j,k; VertexType va,vb; VRType w; coutG.vexnumG.a

8、rcnum; cout请输入G.vexnum个顶点的值(MAX_NAME个字符):n; for(i=0;iG.vexsi; for(i=0;iG.vexnum;+i) /* 初始化邻接矩阵 */ for(j=0;jG.vexnum;+j) G.arcsij.adj=INFINITY; /* 图 */ G.arcsij.info=NULL; cout请输入G.arcnum条弧的弧尾 弧头 权值(以空格作为间隔): n; for(k=0;kvavbw; i=LocateVex(G,va); j=LocateVex(G,vb); G.arcsij.adj=w; G.kind=DG; return O

9、K;void PrintAdjMatrix(MGraph G)/输出邻接矩阵 char ch=*; cout-endl; cout ; for(int i=0;iG.vexnum;+i) coutG.vexsi ; coutendl; for(i=0;iG.vexnum;+i) coutG.vexsi ; for(int j=0;jG.vexnum;+j) if(G.arcsij.adj=INFINITY) coutch ; else coutG.arcsij.adj ; coutendl; cout-endl;void display(MGraph G)/输出顶点表和邻接矩阵 cout-en

10、dl; cout顶点表:n; for(int i=0;iG.vexnum;i+) coutG.vexsi ; coutn-endl; coutn邻接矩阵(*代表无穷大):n; PrintAdjMatrix(G);void CreateMGtoDN(ALGraph &G2,MGraph &G) /由有向图G的邻接矩阵产生邻接表 ArcNode *p; G2.kind=G.kind; G2.vexnum=G.vexnum; G2.arcnum=G.arcnum; for(int i=0;iG2.vexnum;+i) /构造表头向量 strcpy(G2.verticesi.data,G.vexsi)

11、; G2.verticesi.firstarc=NULL;/初始化指针 for(i=0;iG2.vexnum;+i) for(int j=0;jadjvex=j; p-nextarc=G2.verticesi.firstarc; p-info=G.arcsij.info; G2.verticesi.firstarc=p; void PrintAdjList(ALGraph G)/输出邻接表 cout-endl; for(int i=0;iG.vexnum;i+) ArcNode *p=G.verticesi.firstarc; coutG.verticesi.data; while(p) co

12、utadjvex.data; p=p-nextarc; coutendl; cout-endl;void CreateDNtoMG(MGraph &G3,ALGraph &G2)/由邻接表产生对应的邻接矩阵 int i,j; ArcNode *p; G3.kind=GraphKind(G2.kind); G3.vexnum=G2.vexnum; G3.arcnum=G2.arcnum; for(i=0;iG3.vexnum;+i) strcpy(G3.vexsi,G2.verticesi.data); for(i=0;iadjvex.adj=1; p=p-nextarc; /while for

13、(j=0;jG3.vexnum;+j) if(G3.arcsij.adj!=1) G3.arcsij.adj=INFINITY; /forBoolean visitedMAX_VERTEX_NUM; /* 访问标志数组(全局量) */void (*VisitFunc)(char* v); /* 函数变量(全局量) */ 从第v个顶点出发递归地深度优先遍历图G。/* 查找第1个邻接点 */int FirstAdjVex(MGraph &G,int v) for(int m=0;mG.vexnum;+m) if(G.arcsvm.adj!=INFINITY) return m; return -1

14、;/* 查找下一个邻接点 */int NextAdjVex(MGraph &G,int v,int w) for(int j=w+1;jG.vexnum;j+) if (G.arcsvj.adj!=INFINITY) return j; return -1;void DFS(MGraph &G,int v)/从第v个顶点出发递归地深度优先遍历图G coutG.vexsv=0;w=NextAdjVex(G,v,w) / 访问第W个顶点 if(!visitedw)/对v的尚未访问的邻接点w递归调用DFS DFS(G,w);void visits(MGraph &G,int &v)/判断结点是否已经

15、访问过 v=-1; for(int i=0;iG.vexnum;i+) if(!visitedi) v=i;void DFSTraverse(MGraph G,int v) /对图G作深度优先遍历 for(int i=0;i=0 & v=S.stacksize) /* 栈满，追加存储空间 */ S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); /* 存储分配失败 */ S.top=S.base+S.stacksize; S.

16、stacksize+=STACKINCREMENT; *(S.top)+=e; return OK;Status Pop(SqStack &S,SElemType &e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if(S.top=S.base) return ERROR; e=*-S.top; return OK;void DFSTraverse2(MGraph G,int v) /对图G作深度优先遍历 (非递归算法) SqStack s; InitStack(s); for(int i=0;iG.vexnum;+i) visitedi=FALS

17、E;/ 访问标志数组初始化 Push(s,v); while(!StackEmpty(s)/ 对尚未访问的顶点调用DFS int flag=0; Pop(s,v); if(!visitedv) coutG.vexsv ; visitedv=TRUE; for(int j=0;j=0 & vnext=NULL; return OK;Status QueueEmpty(LinkQueue &Q) /* 若Q为空队列,则返回TRUE,否则返回FALSE */ if(Q.front=Q.rear) return TRUE; else return FALSE;Status EnQueue(LinkQu

18、eue &Q,QElemType e) /* 插入元素e为Q的新的队尾元素 */ QueuePtr p=(QueuePtr)malloc(sizeof(QNode); if(!p) /* 存储分配失败 */ exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;Status DeQueue(LinkQueue &Q,QElemType &e) /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */ QueuePtr p; if(Q.front=Q.rear) retur

19、n ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK;int LocateVex(ALGraph G,VertexType u) /* 初始条件: 图G存在,u和G中顶点有相同特征 */ /* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;i=G.vexnum|vadjvex; else return -1;int NextAdjVex(ALGraph G,VertexType v,V

20、ertexType w) /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */ /* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */ /* 若w是v的最后一个邻接点,则返回-1 */ ArcNode *p; int v1,w1; v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */ w1=LocateVex(G,w); /* w1为顶点w在图G中的序号 */ p=G.verticesv1.firstarc; while(p&p-adjvex!=w1) /* 指针p不空且所指表结点不是w */ p=p-nextarc; if(!p|!p-nextarc) /* 没找到w或w是最后一个邻接点 */ return -1; else /* p-adjvex=w */ return p-nextarc-adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */void BFSTraverse(ALGraph G,void(*Visit)(char*)/*按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。算法7.6 */ int v,u,w; VertexType u1,w1; LinkQueue Q; for(v=0;vG.vexnum;+v) visitedv=FALSE; /* 置初