《数据结构课程设计-超市选址》由会员分享，可在线阅读，更多相关《数据结构课程设计-超市选址（15页珍藏版）》请在金锄头文库上搜索。
1、课 程 设 计 任 务 书专专 业业计算机科学与技术计算机科学与技术班班 级级姓姓 名名设设 计计 起起 止止 日日 期期20152015 年年 5 5 月月 1 1 日日-205-205 年年 5 5 月月 7 7 日日设计题目：设计题目： 超市选址超市选址设计任务（主要技术参数）：设计任务（主要技术参数）：硬件环境：CPU：P4 2.8GHz 以上; 内存:256MB 以上；硬盘大小:80G 以上。软件环境：(1)操作系统：WINDOWS XP。(2)开发软件: VC+6.0 或 TC。实现功能：熟练掌握权值的计算和弗洛伊德算法，通过带权又向图和弗洛伊德算法求出最短路径，让我们更加了解、熟
2、悉数据结构中各种算法的运用与计算，并且学会如何去实现它，对我们的生活也增加了一些常识。指导教师评语：指导教师评语：成绩：成绩： 签字：签字：年年 月月 日日课程设计说明书 No. 1超市选址超市选址1. 课程设计目的课程设计目的通过对数据结构中权值的计算和弗洛伊德算法的学习，将其在课程设计中实现、表达出来，数据结构是计算机软件和计算机应用专业的核心课程之一，在众多的计算机系统软件和应用软件中都要用到各种数据结构。在数据结构中，在设计中可以处理数值计算问题 、选取合适数据结构、写出更有效的算法。计算机核心课程，程序=算法+数据结构，数据结构的重要性可见一斑。事实上，想要写出优美高效的代码，数据结
3、构的知识一定要有的，学习的过程中更重要的是去理解它的思想。2.设计方案论证设计方案论证 2.1 设计思路设计思路核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少)数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度)存储结构: typedef structstring vexsMAX_VERTEX_SIZE;int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE;int vexnum;/ ,arcnum;MGraph；核心算法: Floyd 算法(弗洛伊德算法-每一对顶点之间的最短路径) 输入数据: 各单位名称，距离，频度，单位个数输出数据: 所选单
4、位名称总体思路: 如果超市是要选在某个单位，那么先用 floyd 算法得出各顶点间的最短距离/最小权值。 假设顶点个数有 n 个，那么就得到 n*n 的一张表格，arcs(i,j)表示 i 单位到 j单位的最短距离/最小权值 ,这张表格中和最小的那一行(假设为第 t 行)，那么超市选在 t 单位处就是最优解。2.2 设计方法设计方法课程设计说明书 No. 2Floyd 算法利用动态规划思想，通过把问题分解为子问题来解决任意两点见的最短路径问题。设 G=(V, E, w)是一个带权有向图，其边 V=v1, v2, , vn。对于 kn，考虑其结点 V 的一个子集。对于 V 中任何两个结点 vi、
5、vj，考虑从 vi 到 vj 的中间结点都在 vk 中的所有路径，设该路径是其中最短的，并设它的路径长度为最短路径长度。如果结点 vk 不在从 vi 到 vj 的最短路径上，则；反之则可以把分为两段，其中一段从 vi 到 vk，另一段从 vk 到 vj，这样便得到表达式。上述讨论可以归纳为如下递归式：算法结构图，如图 1图图 1 算法结构图算法结构图2.3 详细设计详细设计开始Main（ ）输入基本信息建立邻接矩阵的存储结构GreatMgraph（Gh ）Floyd 算法Aij=INF,i!= j输出 i-j 的路径和路径长度输出超市的最佳地址：i结束Ni 到 j 不存在路 径YFloyed（
6、Gh ）课程设计说明书 No. 3让所有路径加上中间顶点 1，取 Aij与 Ai1+A1j中较小的值作Aij的新值，完成后得到 A(1),如此进行下去，当第 k 步完成后，A（k）ij表示从 i 到就且路径上的中间顶点的路径的序号小于或等于 k 的最短路径长度。当第 n-1 步完成后，得到 A（n-1） ，A（n-1）即所求结果。A（n-1）ij表示从 i 到 j 且路径上的中点顶点的序号小于或等于 n-1 的最短路径长度，即A(n-1)ij表示从 i 到 j 的最短路径长度。2.3.1 结构体的定义结构体的定义typedef structVextype vexsMAXVEXMAXVEX; /
7、单位名称（顶点信息） ；int adjMAXVEXMAXVEX;/单位之间的相通情况（是否有边） ；int disMAXVEXMAXVEX;/单位间距离（边的长度） ；int fMAXVEX;/各单位去超市的频率；int n;/顶点数和边数；int e;Mgraph;2.3.2 带权有向图求最短路径带权有向图求最短路径 floydfloyd 算法算法void Floyed(Mgraph *G) /带权有向图求最短路径 floyd 算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;in;i+) /
8、初始化 A和 path数组for(j=0;jn;j+) /置初值；Aij=G-disij;pathij=-1;课程设计说明书 No. 4counti=0;for(k=0;kn;k+) /k 代表运算步骤for(i=0;in;i+)for(j=0;jn;j+)if(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;elsecounti=1;for(i=0;in;i+)if(counti)fo
9、r(j=0;jn;j+)if(i!=j)Aii+=Aji;k=0;for(i=0;in;i+)if(counti)if(AkkAii)k=i;coutvexsk#include #include #include #include “malloc.h“#include #define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INF 32767const int MAXVEX=100;typedef char Vextype;typedef structVextype vexsMAXVE
10、XMAXVEX; /单位名称（顶点信息） ；int adjMAXVEXMAXVEX;/单位之间的相通情况（是否有边） ；int disMAXVEXMAXVEX;/单位间距离（边的长度） ；int fMAXVEX;/各单位去超市的频率；int n;/顶点数和边数；int e;Mgraph;void CreatMgraph(Mgraph *G) 课程设计说明书 No. 11int i,j,k;printf(“请输入单位个数:n“);scanf(“%d“,printf(“请输入单位间的路径数:n“);scanf(“%d“,printf(“请输入单位名称:n“);for(i=0;in;i+)print
11、f(“请输入第%d 个单位名称:n“,i);scanf(“%s“,for(i=0;in;i+) /结构体的初始化；for(j=0;jn;j+)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+)课程设计说明书 No. 12printf(“请输入第%d 个单位去超市
12、的相对频率:n“,k);scanf(“%d“,for(i=0;in;i+) /以距离和频率之积作为权值；for(j=0;jn;j+)G-disij*=G-fi; /最终权值非完全无向； if(G-adjij=0void 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
13、;kn;k+) /k 代表运算步骤for(i=0;in;i+)for(j=0;jn;j+)if(Aij(Aik+Akj) /从 i 经 j 到 k 的一条路径更短课程设计说明书 No. 13Aij=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;elsecounti=1;for(i=0;in;i+)if(counti)for(j=0;jn;j+)if(i!=j)Aii+=Aji;k=0;for(i=0;in;i+)if(counti)if(AkkAii)k=i;coutvexskendl;void main()Mgraph *Gh=NULL;Gh=(Mgraph *)malloc(sizeof(Mgraph);CreatMgraph(Gh);课程设计说明书 No. 15Floyed(Gh);system(“pause“);
