资源描述
单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,回顾：,#define MAX_V_NUM 20,typedef struct ArcNode,int adjvex;,struct ArcNode *nextarc;,InfoType *info;, ArcNode;,1,typedef struct VNode,VertexType data;,ArcNode *firstarc;, VNode, AdjListMAX_VERTEX_NUM;,typedef struct ,AdjList vertices;,int vexnum,arcnum;,int kind;,ALGraph;,2,第10次课 图的存储和遍历,一、实验目的：,掌握图的存储结构（,邻接表,）。,理解,第,1,个邻接点，下一个邻接点和存储有关,。,掌握,深度优先遍历和广度优先遍历,的算法。,3,二、实验内容：,1.实现一个有向网的存储（邻接表），以图7.9（a）为逻辑结构进行测试。,2.在实现存储结构的基础上，实现深度优先和广度优先遍历算法,4,部分代码：,#include,#include,#include,#define TRUE 1,#define FALSE 0,#define ok 1,#define error 0,#define OVERFLOW -1,#define MAX_NAME 5,#define Maxqsize 100,typedef int status;,typedef char ElemTypeMAX_NAME;,5,typedef int InfoType;,#define MAX_VERTEX_NUM 20,typedef int GraphKind; /* 0:有向图,1:有向网,2:无向图,3:无向网 */,typedef struct ArcNode,int adjvex; /* 该弧所指向的顶点的位置*/,struct ArcNode *nextarc; /* 指向下一条弧的指针*/,InfoType info; /* 网的权值 */,ArcNode; /* 表结点*/,6,typedef struct,ElemType data; /* 顶点信息*/,ArcNode *firstarc;,/* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/,VNode,AdjListMAX_VERTEX_NUM; /* 头结点*/,typedef struct,AdjList vertices;,int vexnum,arcnum; /* 图的当前顶点数和弧数*/,GraphKind kind; /* 图的种类标志*/,ALGraph;,7,typedef struct /* 广度优先遍历需要的队列*/,int *base;,int front;,int rear;,SqQueue;,8,int LocateVex(ALGraph G,ElemType u);,status CreateGraph(ALGraph ,int FirstAdjVex(ALGraph G,int v);,int NextAdjVex(ALGraph G,int v,int w);,void ShowElem(char *v);,9,int visitedMAX_VERTEX_NUM;,/* 访问标志数组(全局量) */,void(*VisitFunc)(char* v); /* 函数变量(全局量) */,void DFS(ALGraph G,int v);,void DFSTraverse(ALGraph G,void(*Visit)(char*);,10,status InitQueue(SqQueue ,status Enqueue(SqQueue ,status Dequeue(SqQueue ,int Queueempty(SqQueue q);,void BFSTraverse(ALGraph G,void(*Visit)(char*);,11,main(),ALGraph G;,if(CreateGraph(G) printf(图存储结构创建成功！n);,printf(图的深度优先搜索序列是：);,DFSTraverse(G,ShowElem);,printf(图的广度优先搜索序列是：);,BFSTraverse(G,ShowElem);,return(1);,12,int LocateVex(ALGraph G,ElemType u),int i;,for(i=0;iG.vexnum;+i),if(strcmp(u,G.verticesi.data)=0) return i;,return -1;,13,status CreateGraph(ALGraph &G),FILE *fp;,int i,j,k; int w; /* 权值*/,ElemType va,vb;,ArcNode *p;,if(fp=fopen(data.txt,r)=NULL),printf(Cant open file!n);,return(error);,fscanf(fp,%dn,fscanf(fp,%dn,fscanf(fp,%dn,14,for(i=0;iG.vexnum;+i) /* 构造顶点向量*/,fscanf(fp,%sn,G.verticesi.data);,G.verticesi.firstarc=NULL;,15,for(k=0;kadjvex=j;,if(G.kind=1|G.kind=3) p-info=w; /* 网*/,else p-info=0;,p-nextarc=G.verticesi.firstarc; /* 插在表头*/,G.verticesi.firstarc=p;,if(G.kind=2),/* 无向图或网,产生第二个表结点*/,p=(ArcNode*)malloc(sizeof(ArcNode);,p-adjvex=i;,if(G.kind=3) p-info=w; /* 无向网*/,else p-info=0;,p-nextarc=G.verticesj.firstarc; /* 插在表头*/,G.verticesj.firstarc=p;,/*end of if*/,/*end of for*/,fclose(fp);,return(ok);,17,
展开阅读全文