数据结构实验报告10图的操作答案.doc

实 验 报 告 院（系）：信息科学与技术学院 课程名称：数据结构 日期： 班级 学号 实验室 专业 姓名 计算机号 实验名称 图的存储与基本操作 成绩评定 所用软件 V C或TC 教师签名 实 验 目 的 （1）掌握图的存储结构； （2）实现图的邻接矩阵存储。 （3）掌握图的遍历方法。 实 验 准 备 复习书上有关内容。 阅读实验内容1。 编出实验内容2、3的源程序。 实 验 内 容 二、设计算法对邻接表表示的无向网进行广度优先遍历。 #include stdio.h #include stdlib.h typedef int DataType;//将队列中元素的数据类型改为Person //循环队列的类型定义 #define QueueSize 100 //应根据具体情况定义该值 typedef struct { int front; //头指针，队非空时指向队头元素 int rear; //尾指针，队非空时指向队尾元素的下一位置 int count; //计数器，记录队中元素总数 DataType data[QueueSize]; } CirQueue; #define MaxVertexNum 100 //最大顶点数，应由用户定义 typedef char VertexType; //顶点类型应由用户定义 typedef struct node { //边表结点 int adjvex; //邻接点域 struct node *next; //链域 //若要表示边上的权，则应增加一个数据域 }EdgeNode; typedef struct vnode { //顶点表结点 VertexType vertex; //顶点域 EdgeNode *firstedge; //边表头指针 }VertexNode; typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型 typedef struct { AdjList adjlist; //邻接表 int n,e; //图中当前顶点数和边数 }ALGraph; //对于简单的应用，无须定义此类型，可直接使用AdjList类型 typedef enum{FALSE,TRUE} Boolean; //FALSE为0，TRUE为1 Boolean visited[MaxVertexNum]; //访问标志向量是全局量 void main() { void InitQueue(CirQueue *Q); int QueueEmpty(CirQueue *Q); int QueueFull(CirQueue *Q); void EnQueue(CirQueue *Q,DataType x); DataType DeQueue(CirQueue *Q); DataType QueueFront(CirQueue *Q); void CreateALGraph(ALGraph *G); void PrintALGraph(ALGraph *G); void BFS(ALGraph *G,int k); ALGraph G; CreateALGraph(G); PrintALGraph(G); printf(广度优先搜索结果：); BFS(G,0); printf(\n); } void CreateALGraph(ALGraph *G) { //建立无向图的邻接表表示 int i,j,k; EdgeNode *s; printf(请输出顶点数和边数：); scanf(%d%d,G-n,G-e); //读入顶点数和边数 printf(请输出顶点信息：); for(i=0;iG-n;i++){ //建立顶点表 while((G-adjlist[i].vertex=getchar())==\n); //读入顶点信息 G-adjlist[i].firstedge=NULL; //边表置为空表 } for(k=0;kG-e;k++){ //建立边表 printf(\n请输出第%d边的起点、终点：,k+1); scanf(%d%d,i,j); //读入边(vi,vj)的顶点对序号 s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点 s-adjvex=j; //邻接点序号为j s-next=G-adjlist[i].first