邻接矩阵、邻接表等存储结构的相关算法.doc

内蒙古科技大学信息工程学院计算机系数据结构与算法实验报告姓名学号1367159107班级实验日期第 14 周（星期二）12 月2 日第 7、8节项目号、实验名称5、图的存储结构算法实验要求（任课教师提供）1、 该实验要求掌握邻接矩阵、邻接表等存储结构的相关算法；2、验证性实验要求在实验前认真研读相关教材，作好充分的预习准备工作，写出实验预习报告；3、学生必须在规定时间内独立完成，对实验过程中出现的问题，要求尽量做到独立思考，独立解决；4、每次实验的结果必须经过教师认可后，实验方可结束；5、要求学生必须认真对待每一个实验，不得缺席、迟到、早退；6、要求实验中认真做好实验记录，实验后认真完成实验报告；实验内容（由学生填写）邻接矩阵的存储法主程序如下：#include #include #include #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20#define MAXQSIZE 10 /最大队列长度#define FALSE 0#define TRUE 1typedef int VRType;typedef int InfoType;typedef char VertexType;typedef int Status;typedef int QElemType;typedef struct QElemType *base; int front; int rear; SqQueue;typedef struct ArcCell VRType adj; InfoType *info; ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum, arcnum; MGraph;bool visitedMAX_VERTEX_NUM;Status (*VisitFunc)(int v);int w;void CreateGraph(MGraph &G); /邻接矩阵创建图void BFSTraverse(MGraph G, Status (*Visit)(int v);/邻接矩阵的广度遍历 void DFSTraverse(MGraph G, Status (*Visit)(int v);/邻接矩阵的深度遍历 void DFS(MGraph G, int v);Status printGraph(int v);int FirstAdjVex(MGraph G, int v);/返回图G中顶点v的第一个邻接点。若不存在邻接点，则返回0。int NextAdjVex(MGraph G, int v, int w);/返回图G中顶点v的邻接点中处于w之后的那个邻接点，若不存在这样的邻接点，则返回0。Status InitQueue(SqQueue &);Status EnQueue(SqQueue &, QElemType);Status DeQueue(SqQueue &, QElemType &);Status QueueEmpty(SqQueue);void main( void ) int i, j; MGraph G; /创建图的邻接矩阵 cout开始创建图的邻接矩阵.endl; CreateGraph(G); /邻接矩阵的广度遍历代码块 cout邻接矩阵的广度遍历.endl; for(i = 0; i G.vexnum; i+) for(j = 0; j G.vexnum; j+) coutG.arcsij.adj; coutt; coutendl; coutn遍历结果为:endl; BFSTraverse(G, printGraph); coutendl; /邻接矩阵的深度遍历 代码块 cout邻接矩阵的深度遍历.endl; for(i = 0; i G.vexnum; i+) for(j = 0; j G.vexnum; j+) coutG.arcsij.adj; coutt; coutn; coutn遍历结果为:endl; DFSTraverse(G, printGraph); void CreateGraph(MGraph &G) int weigh; int i, j = 0, k = 0; char hand, tide; coutG.vexnumG.arcnum; for(i = 0; i G.vexnum; i+) for(j = 0; j G.vexnum; j+) G.arcsij.adj = 88; coutendl; coutinput G.vexnum char for vexs(use -enter- to change):; for(i=0; i G.vexsi; coutendl; coutinput G.arcnum arc(char -enter- char -enter- weigh):endl; j = 0; k = 0; for(i=0; i G.arcnum; i+) coutihand; cintide; cinweigh; while (hand != G.vexsj) j+; while (tide != G.vexsk) k+; G.arcsjk.adj = weigh; G.arcskj.adj = weigh; j = 0; k = 0; coutendl; void BFSTraverse(MGraph G, Status (*Visit)(int v) SqQueue Q; QElemType u; InitQueue(Q); for(int v=0; v G.vexnum;+v) visitedv=FALSE; for(v=0; vG.vexnum;+v) if(!visitedv) visitedv=TRUE; Visit(v); EnQueue(Q, v); while(QueueEmpty(Q) DeQueue(Q, u); for(w = FirstAdjVex(G, u); w; w = NextAdjVex(G, u, w) if(! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); void DFSTraverse(MGraph G, Status (*Visit)(int v) int j; VisitFunc = Visit; for( j=0; jG.vexnum; j+) visitedj = 0; for(j=0; jG.vexnum; j+) if(!visitedj) DFS(G, j);void DFS(MGraph G, int v) visitedv=1; VisitFunc(v); for(w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w) if(!visitedw) DFS(G, w);int FirstAdjVex(MGraph G, int v) int j; for(j = 0; j G.vexnum; j+) if(G.arcsvj.adj != 88 & visitedj != 1) return j; return 0;int NextAdjVex(MGraph G, int v, int w) int j; for(j = 0; j G.vexnum; j+) if(G.arcsvj.adj != 88 & j != w & visitedj != 1) return j; return 0;Status printGraph(int v) printf(%ct, v + a); return 1;Status InitQueue(SqQueue & queue) queue.base = (QElemType *) malloc(MAXQSIZE * sizeof(QElemType); if (!queue.base) return FALSE; queue.front = queue.rear = 0; return TRUE;/ 函数名 : EnQueue/ 功能描述 : 插入元素到队列/ 参数 : SqQueue &queue/ 参数 : QElemType element/ 返回值 : Status/Status EnQueue(SqQueue &queue, QElemType element) /先判断是不是没满的队列 if (queue.rear + 1) % MAXQSIZE = queue.front) return FALSE; queue.basequeue.rear = element; queue.rear = (queue.rear + 1) % MAXQSIZE; return TRUE;/ 函数名 : DeQueue/ 功能描述 : 删除队列的头结点/ 参数 : SqQueue &queue/ 参数 : QElemType &element/ 返回值 : Status /Status DeQueue(SqQueue &queue, QElemType &element) /判断队列是不是空的 if (queue.front = queue.rear) return FALSE; element = queue.basequeue.front; queue.front = (queue.front + 1) % MAXQSIZE; return TRUE;Status QueueEmpty(SqQueue queue) if (queue.front = queue.rear) return FALSE; else return TRUE;运行结果如下:评语（由教师填写）说明：1、每个实验项目填写一份实验报告，电子版命名方式为