校园选址第一阶段报告

  • 格式:docx
  • 大小:29.81 KB
  • 文档页数:2

数据结构第一阶段实验报告:校园选址
12072212
【问题描述】
某校园至少包括6个单位,各单位之间距离不同,请为超市选址,确定将超市放在哪个单位,才能使得总体最优。

【基本要求】
输入:以文件形式存储作为输入,包括单位个数、每个单位编号、每个单位人数、各个单位间距离。

输出(图形方式):
1、显示校园各个单位分布图(标明单位人数、单位间距离)
2、问题答案(基本版本):不考虑单位人数,只考虑距离,确定超市最佳选址(用不同颜色的边动态显示选择路径的过程),列表输出所选超市到各单位距离,并输出总和。

1.需求分析
核心问题: 求最短路径(要求超市到各建筑权值之和最少)
数据模型(逻辑结构): 带权有向图(权值计算: 距离*频度)
存储结构: typedefstruct
{
stringvexs[MAX_VERTEX_SIZE];
int arcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];
intvexnum;// ,arcnum;
}MGraph;
核心算法: Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径)
输入数据: 各单位名称,距离,频度,单位个数.
输出数据: 所选单位名称.
总体思路:如果超市是要选在某个单位,那么先用floyd算法得出各顶点间的最短距离/最小权值。

假设顶点个数有n个,那么就得到n*n的一张表格,arcs(i,j)表示
i单位到j单位的最短距离/最小权值, 这张表格中和最小的那一行(假设为
第t行),那么超市选在t单位处就是最优解。

2.总体设计图
3.功能分析
3.1输入功能
输入学校的单位总数;
输入学校各单位名称;
输入学校各单位学生去超市频度;
输入学校各单位间的距离(用矩阵表示)。

3.2求权值功能
求出将超市设在各个单位时,所得权值和,返回用数组存储。

3.3 求最优功能
选出最小权值和最优。

并将最优值和对应的选址储存在链表中,返回头指针。

3.4显示功能
图形显示最优选址的地点、总权数以及各单位到它的距离、各单位到超市频度。

4.数据结构
定义一个Mgraph结构体来存储图的基本信息,代码如下:
typedefstruct{
Vextypevexs[MAXVEX][MAXVEX]; //单位名称(顶点信息);
intadj[MAXVEX][MAXVEX]; //单位之间的相通情况;
int dis[MAXVEX][MAXVEX]; //单位间距离(边的长度);
int f[MAXVEX]; //各单位去超市的频率;
int n; //顶点数和边数;
int e;
}Mgraph;。