《数据结构图及其应用实验报告+代码例文》由会员分享，可在线阅读，更多相关《数据结构图及其应用实验报告+代码例文（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构图及其应用实验报告+代码 附件2： 北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 实验题目图及其应用实验时间 2022.5.10 一、实验目的、意义 （1）熟悉图的邻接矩阵（或邻接表）的表示方法； （2）掌握建立图的邻接矩阵（或邻接表）算法； （3）掌握图的基本运算，熟悉对图遍历算法； （4）加深对图的理解，逐步培养解决实际问题的编程能力 二、实验内容及要求 说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入
2、数据，预期输出并验证输出的结果，加深对有关算法的理解。 具体要求： （1）建立图的邻接矩阵（或邻接表）； （2）对其进行深度优先及广度优先遍历。 三、实验所涉及的知识点 1.创建一个图: CreateUDN(MGraph &G) 2.查找v顶点的第一个邻接点: FirstAdjVex(MGraph G,int v) 3. 查找基于v顶点的w邻接点的下一个邻接点: NextAdjVex(MGraph G,int v,int w) 4.图的矩阵输出: printArcs(MGraph G) 5:顶点定位: LocateVex(MGraph G,char v) 6. 访问顶点v输出: printAd
3、jVex(MGraph G,int v) 7. 深度优先遍历: DFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v) 8. 广度优先遍历BFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v) 9. DFS,从第v个顶点出发递归深度优先遍历图G: DFS(MGraph G,int v) 四、实验记录 1.对顶点的定位其数组下标，利用了找到之后用return立即返回，在当图顶点 多的情况下节省了搜索时间，程序如下 /对顶点v定位，返回该顶点在数组的下标索引，若找不到则返回-1 int Locate
4、Vex(MGraph G,char v) for (int i=0;inext = NULL; return OK; /插入元素到队尾 Status EnQueue(LinkQueue &Q,QElemType e) QueuePtr p = (QueuePtr)malloc(sizeof(QNode); if (!p) printf(n内存分配失败!); exit(OVERFLOW); p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; /队列判空 Status QueueEmpty(LinkQueue Q)
5、return Q.front = Q.rear; /销毁队列 Status DestroyQueue(LinkQueue &Q) while (Q.front) Q.rear = Q.front-next; free(Q.front); Q.front = Q.rear; return OK; /删除队头元素 Status DeQueue(LinkQueue &Q,QElemType &e) if (QueueEmpty(Q) printf(n队列为空！); return ERROR; QueuePtr p = Q.front-next; e = p-data; Q.front-next =
6、p-next; if(Q.rear=p) Q.rear = Q.front; free(p); return OK; /对顶点v定位，返回该顶点在数组的下标索引，若找不到则返回-1 int LocateVex(MGraph G,char v) for (int i=0;iMAX_VERTEX_NUM) printf(最大顶点为20，重新输入(如：4,3):); scanf(%d,%d,&G.vexnum,&G.arcnum); printf(n依次输入顶点向量值n); int i; for (i=0;i=0;w=NextAdjVex(G,v,w) if (!visitedw) DFS(G,w)
7、; /深度优先遍历 void DFSTraverse(MGraph G,Status (*Visit)(MGraph G,int v) /将函数复制给全局的函数指针变量，待调用DFS时使用 VisitFunc = Visit; int v; /将访问标记初始化为false for (v=0;v=0;w = NextAdjVex(G,u,w) if (!visitedw) visitedw =TRUE; Visit(G,w); EnQueue(Q,w); /销毁队列 DestroyQueue(Q); void main() printf(=图的创建及其应用=n); /创建一个图 MGraph G; CreateUDN(G); /用邻接矩阵输出图 printf(n图的邻接矩阵输出如下:n); printArcs(G); /深度优先遍历 printf(n深度优先遍历序列:n); DFSTraverse(G,printAdjVex); printf(n); /广度优先遍历 printf(n广度优先遍历序列:n); BFSTraverse(G,printAdjVex); printf(n);
