《数据结构》实验报告.doc

数据结构（C语言版）实验报告 关宏新 089074114 计084班 图的创建与遍历.一、 实验目的1掌握图的含义；2 掌握用邻接矩阵和邻接表的方法描述图的存储结构；3 理解并掌握深度优先遍历和广度优先遍历的存储结构。二、 实验要求1 认真阅读和掌握本实验的参考程序。2 按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。3 保存程序的运行结果，并结合程序进行分析。三、 实验内容 以下参考程序是按邻接表的方法创建图，然后用深度优先遍历方法遍历图。请认真理解程序，然后实现图的广度优先遍历。四、程序流程图、算法及运行结果5-1#include stdio.h#define maxsize 1024 /*假定线性表的最大长度为1024*/#define n 100 /* 图的顶点最大个数 */typedef int datatype; /*假定线性表元素的类型为整型*/typedef char VEXTYPE; /* 顶点的数据类型 */typedef float ADJTYPE; /* 权值类型 */typedef struct VEXTYPE vexsn ; /* 顶点信息数组 */ ADJTYPE arcsnn ; /* 边权数组 */ int num ; /* 顶点的实际个数 */ GRAPH;/* 1.置空图 */void GraphInit(GRAPH *L) L-num=0;/* 2.求结点数 */int GraphVexs(GRAPH *L) return(L-num);/* 3.创建图 */void GraphCreate(GRAPH *L) int i,j; GraphInit(L); printf(请输入顶点数目：); scanf(%d,&L-num); printf(请输入各顶点的信息(单个符号）：); for(i=0;inum;i+) fflush(stdin); scanf(%c,&L-vexsi); printf(请输入边权矩阵的信息：); for(i=0;inum;i+) for(j=0;jnum;j+) scanf(%f,&L-arcsij); printf(图已经创建完毕！);/* 4.图的输出 */void GraphOut(GRAPH L) int i,j; printf(n图的顶点数目为：%d,L.num); printf(n图的各顶点的信息为：n); for(i=0;iL.num;i+) printf(%c ,L.vexsi); printf(n图的边权矩阵的信息为：n); for(i=0;iL.num;i+) for(j=0;jL.num;j+) printf(%6.2f ,L.arcsij); printf(n); printf(图已经输出完毕！);/* 5.图的深度周游 */void DFS(GRAPH g,int qidian,int mark)/* 从第qidian个点出发深度优先周游图g中能访问的各个顶点 */ int v1; markqidian=1; printf(%c ,g.vexsqidian); for(v1=0;v1g.num;v1+) if(g.arcsqidianv1!=0&markv1=0) DFS(g,v1,mark); /* 6.图的深度周游 */void GraphDFS(GRAPH g)/* 深度优先周游图g中能访问的各个顶点 */ int qidian,v,v1,markmaxsize; printf(n深度周游：); printf(n请输入起点的下标：); scanf(%d,&qidian); for(v=0;vg.num;v+) markv=0; for(v=qidian;vfront=0; sq-rear=0;int QueueIsEmpty(SEQQUEUE sq)/* 如果顺序循环队列sq为空，成功返回1，否则返回0 */ if (sq.rear=sq.front) return(1); else return(0); int QueueFront(SEQQUEUE sq,DATATYPE *e)/* 将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0 */ if(QueueIsEmpty(sq) printf(queue is empty!n);return 0; else *e=sq.data(sq.front); return 1;int QueueIn (SEQQUEUE *sq,DATATYPE x)/* 将元素x入队列sq的队尾，成功返回1，失败返回0 */ if (sq-front=(sq-rear+1)%maxsize) printf(queue is full!n); return 0; else sq-datasq-rear=x; sq-rear=(sq-rear+1)%maxsize; return(1); int QueueOut(SEQQUEUE *sq)/* 将队列sq队首元素出队列，成功返回1,失败返回0 */ if(QueueIsEmpty(*sq) printf(queue is empty!n); return 0; else sq-front=(sq-front+1)%maxsize; return 1; /* 7.图的广度周游 */void BFS(GRAPH g,int v,int mark)/* 从v出发广度优先周游图g中能访问的各个顶点 */ int v1,v2; SEQQUEUE q; QueueInit(&q); QueueIn(&q,v); markv=1; printf(%c ,g.vexsv); while(QueueIsEmpty(q)=0) QueueFront(q,&v1); QueueOut(&q); for(v2=0;v2g.num;v2+) if(g.arcsv1v2!=0&markv2=0) QueueIn(&q,v2); markv2=1; printf(%c ,g.vexsv2); /* 8.图的广度周游 */void GraphBFS(GRAPH g)/* 深度优先周游图g中能访问的各个顶点 */ int qidian,v,v1,markmaxsize; printf(n广度周游：); printf(n请输入起点的下标：); scanf(%d,&qidian); for(v=0;vg.num;v+) markv=0; for(v=qidian;vg.num+qidian;