数据结构课程设计-超市选址.docVIP

课 程 设 计 任 务 书 专 业 计算机科学与技术 班 级 姓 名 设 计 起 止 日 期 2015年5月1日-205年5月7日 设计题目： 超市选址 硬件环境： CPU：P4 2.8GHz以上; 内存:256MB以上；硬盘大小:80G以上。 软件环境： (1)操作系统：WINDOWS XP。 (2)开发软件: VC++6.0或TC 实现功能：熟练掌握权值的计算和弗洛伊德算法，通过带权又向图和弗洛伊德算法求出最短路径，让我们更加了解、熟悉数据结构中各种算法的运用与计算，并且学会如何去实现它，对我们的生活也增加了一些常识。 指导教师评语： 成绩： 签字： 年 月 日 超市选址 课程设计目的数据结构是计算机软件和计算机应用专业的核心课程之一，在众多的计算机系统软件和应用软件中都要用到各种数据结构处理数值计算问题 选取合适数据结构写出更有效的算法计算机核心课程，程序=算法+数据结构，数据结构的重要性可见一斑。事实上，想要写出优美高效的代码，数据结构的知识一定要有的，学习的过程中更重要的是去理解它的思想。2.1 设计思路 核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少) 数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度) 存储结构: typedef struct { string vexs[MAX_VERTEX_SIZE]; int arcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE]; int vexnum;// ,arcnum; }MGraph； 核心算法: Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径) 输入数据: 各单位名称，距离，频度，单位个数． 输出数据: 所选单位名称． 总体思路:　如果超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。 假设顶点个数有n个，那么就得到n*n的一张表格，arcs(i,j)表示i单位到j单位的最短距离/最小权值 ,这张表格中和最小的那一行(假设为第t行)，那么超市选在t单位处就是最优解。 2.2设计方法 1 图1 算法结构图 2.3详细设计 2.3.1结构体的定义 typedef struct { Vextype vexs[MAXVEX][MAXVEX]; //单位名称（顶点信息）； int adj[MAXVEX][MAXVEX]; //单位之间的相通情况（是否有边）； int dis[MAXVEX][MAXVEX]; //单位间距离（边的长度）； int f[MAXVEX]; //各单位去超市的频率； int n; //顶点数和边数； int e; }Mgraph;2.3.2带权有向图求最短路径floyd算法 void Floyed(Mgraph *G) //带权有向图求最短路径floyd算法 { int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX]; int i,j,k,pre; int count[MAXVEX]; for(i=0;iG-n;i++) //初始化A[][]和path[][]数组 for(j=0;jG-n;j++) //置初值； { A[i][j]=G-dis[i][j]; path[i][j]=-1; count[i]=0; } for(k=0;kG-n;k++) //k代表运算步骤 { for(i=0;iG-n;i++) for(j=0;jG-n;j++) if(A[i][j](A[i][k]+A[k][j])) //从i经j到k的一条路径更短 { A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; } } coutendlFloyed算法求解如下:endl; for(i=0;iG-n;i++) for(j=0;jG-n;j++) { if(i!=j) { cout i-j;; if(A[i][j]==INF) { if(i!=j) cout不存在路径\nendl; } else { cout路径长度为:A[i][j]\n; cout路径为:i*; pre=path[i][j];