数据结构课程设计-超市选址文库

《数据结构课程设计-超市选址文库》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、课程设计任务书专业计算机科学弓技术班级姓名设计起止日期2015年5月1日-205年5月7日设计题目：超市选址设计任务(主要技术参数)：硬件环境：CPU：P42.8GHz以上；内存:256MB以上；硬盘大小:80G以上。软件环境：(1)操作系统：WINDOWSXPO(2)开发软件：VC++6.0或TC。实现功育出熟练掌握权值的计算和弗洛伊德算法，通过带权又向图和弗洛伊德算法求出最短路径，让我们更加了解、熟悉数据结构中各种算法的运用与计算，并且学会如何去实现它，对我们的生活也增加了一些常识。指导教师评语：成绩：签字：年月日超市选址1.课程设计目的通过对数据结构中权值的计算和非

2、洛伊德算法的学习，将其在课程设计中实现、表达屮来，数据结构是计算机软件和计算机应用专业的核心课程之一，在众多的计算机系统软件不应用软件屮都要用到各种数据结构。在数据结构屮，在设计屮可以处理数值计算问题、选城合适数据结构、写出更有效的算法。计算机核心课程，程序二算法+数据结构，数据结构的重耍性可见一斑。事实上，想要写出优美高效的代码，数据结构的知识一定要冇的，学习的过程中更重要的是去理解它的思想。2•设计方案论证2.1设计思路核心问题：求最短路径（选址的要求就是超市到各单位权值Z和最少）数据模型（逻辑结构）：带权有向图（权值计算：距离*频度）存储结构:typedefstru

3、ct{stringvexs[MAX_VERTEX_SIZE];intarcs[MAX_VERTEX_S!ZE][MAX_VERTEX_S1ZE];intvexnum;//,arcnum;}MGraph；核心算法：Floyd算法（弗洛伊德算法-每一对顶点之间的最短路径）输入数据：各单位名称，距离，频度，单位个数.输出数据：所选单位名称.总体思路：如杲超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。假设顶点个数有n个，那么就得到n*n的一张表格，arcs（i,j）表示i单位到j单位的最短距离/最小权值，这张表格中和最小的那一行（假设为笫t行），那

4、么超市选在t单位处就是最优解。2.2设计方法Floyd算法利用动态规划思想，通过把问题分解为了问题來解决任意两点见的最短路径问题。设G=(V,E,w)是一个带权有向图，其边V二{vl,v2,…，vn}o对于k^n,考虑其结点V的一个子集。对于V屮任何两个结点vi、vj,考虑从vi到vj的中间结点都在vk中的所有路径，设该路径是其中最短的，并设它的路径长度为最短路径长度。如果结点Vk不在从vi到vj的最短路径上，贝I」；反Z则可以把分为两段，其中一段从Vi到vk,另一段从vk到vj,这样便得到表达式。上述讨论可以归纳为如下递归式：算法结构图，如图12.3详细设计让所有路径加

5、上中间顶点1,取A[i][j]与A[i][l]+A[l][j]中较小的值作A[i][j]的新值，完成后得到A(l),如此进行下去,当第k步完成后,A(k)[i][j]表示从i到就且路径上的屮间顶点的路径的序号小于或等于k的最短路径长度。当第n-1步完成后，得到A(n-1),A(n-1)即所求结果。A(nT)表示从i到j且路径上的屮点顶点的序号小于或等于n-1的最短路径长度，即A(n-l)[i][j]表示从i到j的最短路径长度。2.3.1结构体的定义typedefstruct{Vextypevexs[MAXVEX][MAXVEX];intadj[MAXVEX][MAXVEX

6、];边)；intdis[MAXVEX][MAXVEX];intf[MAXVEX];intn;inte;JMgraph;〃单位名称(顶点信息)；//单位之间的相通情况(是否冇〃单位间距离(边的长度)；〃各单位去超市的频率；〃顶点数和边数；2.3.2带权有向图求最短路径floyd算法voidFloyed(Mgraph*G)〃带权有向图求最短路径floyd算法intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];inti,j,k,pre;intcount[MAXVEX];for(i=0;in;i++)//初始化A[][]和path[][]数

7、组for(j=0;jn;j++)〃置初值；count)i]=0;}for(k=0;kn;k卄)//k代表运算步骤{for(i=0;in;i++)for(j=0;jn;j++)if(A[i][j]>(A[i][k]+A[k][j]))〃从i经j到k的一条路径更短{A[i][j]=A[i][k]+A[k]U];path[i][j]=k;}}cout«endl«'Tloyed算法求解如下:H«endl;for(i=0;in;i++)for(j=0;jn;j++){if(i!二j){co