数据结构课程设计学校超市选址问题

数据结构课程设计中的“学校超市选址问题”是一个典型的优化问题，目标是确定超市的位置，使得所有单位到超市的总体距离最小，同时考虑到单位人员去超市的频度。在这个问题中，我们可以采用数据结构和算法的知识来解决。 我们要构建一个数据模型来描述这个问题。这里的数据模型是一个带权有向图，其中的顶点代表各个单位，边表示单位之间的距离，权值则是距离乘以单位人员去超市的频度。因此，每个单位不仅与超市有关，还与其他单位存在关系，这可以通过邻接矩阵来表示。在C语言中，可以定义一个`MGraph`结构体，包含顶点名`vexs`，邻接矩阵`arcs`，顶点数`vexnum`以及边数`arcnum`。 核心算法是Floyd算法，这是一种用于求解图中所有顶点对之间的最短路径的动态规划方法。它通过逐步考虑中间节点的方式，逐步完善最短路径信息。对于一个有向图G=(V, E, w)，Floyd算法通过迭代过程计算每一对顶点之间的最短路径。在每次迭代中，我们检查是否存在更短的路径，通过中间节点vk。如果找到了更短的路径，我们就更新最短路径信息。 程序的运行环境是Visual Studio C++6.0，可以在Windows Vista/2003/XP操作系统下运行。概要设计阶段，我们明确了Floyd算法的动态规划思想，将问题分解为求解每一对顶点之间的最短路径。在详细设计阶段，我们定义了输入和输出数据，包括单位名称、距离、频度和单位数量。接着，我们编写主程序，首先输入基本信息，然后建立邻接矩阵，调用Floyd算法更新最短路径信息。输出最短路径及超市的最佳选址。 在代码实现中，我们定义了必要的头文件和变量，如常量定义、类型定义等。`Mgraph`结构体包含了图的相关信息，如顶点名、邻接矩阵、距离、频率和顶点数。此外，还定义了输入和输出的函数，如创建图`CreMgraph()`，输出最短路径`PrintSP()`等。 通过运行这个程序，我们可以得到所有单位到其他单位的最短路径，以及超市最佳选址的依据，即具有最小总权值的那行的顶点，作为超市的位置。这种方法可以有效地解决学校超市选址问题，实现总体最优。在实际应用中，可能还需要考虑其他因素，如场地成本、交通便利性等，但在课程设计的范围内，我们主要关注距离和频度这两个关键指标。