《学校超市选址问题[2].doc22》由会员分享，可在线阅读，更多相关《学校超市选址问题[2].doc22（11页珍藏版）》请在金锄头文库上搜索。
1、课程设计报告课程设计题目：学校超市选址 学生姓名学生姓名：杨婕杨婕 专专 业：软件工程业：软件工程 班班 级级：091115 学学 号：号：0911153009111530 指导教师指导教师：许志文志文2011 年年 6 月月 15 日日11 1 需求分析需求分析核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少)数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度)存储结构: typedef structstring vexsMAX_VERTEX_SIZE;int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE;int vexnum;/ ,arcnu
2、m;MGraph; 核心算法: Floyd 算法(弗洛伊德算法-每一对顶点之间的最短路径) 输入数据: 各单位名称，距离，频度，单位个数输出数据: 所选单位名称总体思路: 如果超市是要选在某个单位，那么先用 floyd 算法得出各顶点间的最短距离/最小权值。 假设顶点个数有 n 个，那么就得到 n*n 的一张表格，arcs(i,j)表示 i 单位到 j单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第 t 行)，那么超市选在 t 单位处就是最优解。2 2 运行环境运行环境Visual Stdio C+6.0Windows Vista/2003/XP3 3 概要设计概要设计Floy
3、d 算法利用动态规划思想，通过把问题分解为子问题来解决任意两点见的最短路径问题。设 G=(V, E, w)是一个带权有向图，其边 V=v1, v2, , vn。对于 kn，考虑其结点 V 的一个子集。对于 V 中任何两个结点 vi、vj，考虑从 vi 到 vj 的中间结点都在 vk 中的所有路径，设是其中最短的，并设的路径长度为。如果结点 vk 不在从 vi 到 vj 的最短路径上，则；反之则可以把分为两段，其中一段从 vi 到 vk，另一段从 vk 到 vj，这样便得到表达式。上述讨论2可以归纳为如下递归式：原问题转化为对每个 i 和 j 求，或者说求矩阵流程图4 4 详细设计详细设计第一步
4、，让所有路径加上中间顶点 1，取 Aij与 Ai1+A1j中较小的值作 Aij的新值，完成后得到 A(1),如此进行下去，当第 k 步完成后，开始Main（ ）输入基本信息建立邻接矩阵的存储结构GreatMgraph（Gh ）Floyd 算法Aij=INF,i!= j输出 i-j 的路径和路径长度输出超市的最佳地址：i结束Floyed（Gh ）Ni 到 j 不存在路 径Y3A（k）ij表示从 i 到就且路径上的中间顶点的路径的序号小于或等于 k 的最短路径长度。当第 n-1 步完成后，得到 A（n-1） ，A（n-1）即所求结果。A（n-1）ij表示从 i 到 j 且路径上的中点顶点的序号小于
5、或等于 n-1 的最短路径长度，即 A(n-1)ij表示从 i 到 j 的最短路径长度。#include #include #include #include “malloc.h“ #include #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define INF 32767 const int MAXVEX=100; typedef char Vextype; typedef struct Vextype vexsMAXVEXMAXVEX; /单位名称（顶点信息） ； int
6、 adjMAXVEXMAXVEX;/单位之间的相通情况（是否有边） ； int disMAXVEXMAXVEX;/单位间距离（边的长度） ； int fMAXVEX;/各单位去超市的频率； int n;/顶点数和边数； int e; Mgraph; #include void CreatMgraph(Mgraph *G) int i,j,k; printf(“请输入单位个数:n“); scanf(“%d“, printf(“请输入单位间的路径数:n“); scanf(“%d“, printf(“请输入单位名称:n“); for(i=0;in;i+) printf(“请输入第%d 个单位名称:n
7、“,i); scanf(“%s“, for(i=0;in;i+) /结构体的初始化； for(j=0;jn;j+)4 G-adjij=0; G-disij=0; G-fi=0; for(k=0;ke;k+) printf(“请输入相通的两单位 (输入格式:i,j):n“); scanf(“%d,%d“,/在距离上体现为无向； printf(“请输入相同两个单位间的距离(格式：dis)：n“); scanf(“%d“, G-adjij=1; G-adjji=1; G-disji=G-disij; for(k=0;kn;k+) printf(“请输入第%d 个单位去超市的相对频率:n“,k); s
8、canf(“%d“, for(i=0;in;i+) /以距离和频率之积作为权值； for(j=0;jn;j+) G-disij*=G-fi; /最终权值非完全无向； if(G-adjij=0 void Floyed(Mgraph *G) /带权有向图求最短路径 floyd 算法 int AMAXVEXMAXVEX,pathMAXVEXMAXVEX; int i,j,k,pre; int countMAXVEX; for(i=0;in;i+) /初始化 A和 path数组 for(j=0;jn;j+) /置初值； Aij=G-disij; pathij=-1; counti=0; for(k=0
9、;kn;k+) /k 代表运算步骤 for(i=0;in;i+) for(j=0;jn;j+)5if(Aij(Aik+Akj) /从 i 经 j 到 k 的一条路径更短 Aij=Aik+Akj; pathij=k; coutn;i+) for(j=0;jn;j+) if(i!=j) cout“n;i+) for(j=0;jn;j+) if(Aij=INF) counti=0; else counti=1; for(i=0;in;i+) if(counti) 6for(j=0;jn;j+) if(i!=j)Aii+=Aji; k=0; for(i=0;in;i+) if(counti) if(A
10、kkAii) k=i; coutvexskendl; void main() Mgraph *Gh=NULL; Gh=(Mgraph *)malloc(sizeof(Mgraph); CreatMgraph(Gh); Floyed(Gh); system(“pause“); /*测试数据：输入：单位个数4单位间的路径数6第 0 个单位名称a第 1 个单位名称b第 2 个单位名称c第 3 个单位名称d相通两单位 之间的距离0,1 3 1,2 2 2,3 2 0,3 3 0,2 4 1,3 1第 0 个单位去超市的频率 17第 1 个单位去超市的频率 2第 2 个单位去超市的频率 4第 3 个单位
11、去超市的频率 35 5 调试分析调试分析5.15.1 本题目的关键点之一：本题目的关键点之一：有两个权值：各单位到超市的距离及各单位人去超市的频度。这使得图的建立出现了困难，经过分析这两个值可以合并为一个权值即distance*frequency；这样就使得图的建立轻而易举。5.25.2 本题目的关键点之二：本题目的关键点之二：利用 floyd 算法求出每一对顶点之间的最短路径。5.35.3 本题目的关键点之三：本题目的关键点之三：选出最短路径，即最佳地点应使其到其他单位权值最小。注意：每比较一次 path 应清 0 一次（Path=0） 。6 6 测试结果测试结果6.16.1 输入输入86.
12、26.2 输出输出9总总 结结数据结构课程设计完成了，对我来说这是一项小小的挑战，它不仅检验了我的学习情况，也考验了我的意志力，收获非颇丰！通过一学期的学习，我知道数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。 学以致用，这才是我的目标，课程设计给了我这个机会。数据结构是计算机科学与技术专业的一门核心专业基础课程，在我们专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要10的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。 通过数据结构课程实践，加上老师的全力指导，无论是理论知识，还是实践动手能力，我都有了不同程度上的提高。
