内容发布更新时间 : 2024/6/3 19:50:20星期一 下面是文章的全部内容请认真阅读。

西南大学

实 验 报 告

《数据结构与算法》课程

2016-2017学年度第1学期

专业年级 2015级计算机与科学学院 软件学院

姓 名 吴玉洁

学 号 222015321081101

任课教师 何国斌

实验教师 何国斌

上机地点 25-0913

西南大学计算机与信息科学学院

1

《数据结构与算法》课程实验报告（三）

实验题目 实验时间 图 2016-12-23 一、 实验目的及要求 1. 理解并掌握图的两种存储结构，即邻接矩阵（数组）存储、邻接表存储； 2. 掌握图的遍历方法：深度优先搜索、广度优先搜索； 3. 理解拓扑排序、关键路径、最短路径，掌握迪杰斯特拉算法。 二、实验内容、过程和结果（实验主要内容的介绍、主要的操作步骤、程序代码和测试数据及实验结果） 实现图的建立及存储（邻接矩阵、邻接表、深度优先、广度优先） 拓扑排序 #include #include #define MAX 100 typedef char DataType; typedef int VectorRelationType; typedef char VectorType; /*-----------定义邻接矩阵-------------*/ typedef struct arcell{ VectorRelationType adj; //权值 DataType * data; //数据 }arcell, adjmatrix[MAX][MAX]; typedef struct MGraph{ VectorType vexs[MAX]; //顶点向量 adjmatrix arcs; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和边数 }MGraph; typedef struct ArcNode{ int adjvex; //邻接点在头结点数组中的位置(下标) struct ArcNode * nextarc; //指向下一个表结点 DataType * date; }ArcNode; /*----------------定义顶点结点-------------------*/ typedef struct VNode{ VectorType vexdata; ArcNode * firstarc; int count; }VNode, Adjlist[MAX]; /*-------------------定义邻接表---------------*/ typedef struct ALGraph{ Adjlist vexs; int vexnum, arcnum; }ALGraph; /*--------------确定v在邻接矩阵中位置--------------*/

2

int Locatevex(ALGraph * G, VectorType v){ int i; for(i = 0; i < G->vexnum; i++) if(G->vexs[i].vexdata == v) return (i); return -1; } int locatevexM(MGraph * G, VectorType v) { int i; for(i = 0; i < G->vexnum; i++) if(G->vexs[i] == v) return (i); return -1; } /*-----------------建立有向图的邻接矩阵-----------*/ void Create_MGraph(MGraph * G){ int i, j, k, w; VectorType u, v; printf(\创建有向图的邻接矩阵==============\\n\ printf(\请输入当前的顶点数和弧数(vex arc): \\n\ fflush(stdin); //清空输入缓冲区，确保不影响后面的数据读取 scanf(\ printf(\请输入%d个顶点，以回车分离 < vertex >: \\n\ for(i = 0; i < G->vexnum; i++) { fflush(stdin); scanf(\ } for(i = 0; i < G->vexnum; i++) { for(j = 0; j < G->vexnum; j++) { G->arcs[i][j].adj = 0; } } printf(\请输入%d个弧的顶点和权值 各弧以回车分离 < u v w >: \\n\ for(k = 0; k < G->arcnum; k++) { fflush(stdin); scanf(\ i = locatevexM(G, u); j = locatevexM(G, v); G->arcs[i][j].adj = w; } } /*-----------------打印有向图的邻接矩阵-----------*/ void Print_MGraph(MGraph * G) { int i, j; printf(\ printf(\邻接矩阵输出如下: \\n\ printf(\ for(i = 0; i < G->vexnum; i++) printf(\ printf(\ for(i = 0; i < G->vexnum; i++)

3