超市选址课程设计报告.docVIP

计算机科学与技术学院课程设计成绩单课程名称：数据结构课程设计 指导教师：李顺新姓名彭伟华性别男学号201113137131班级计科1103综合成绩成绩等级 程序运行情况（占总成绩20%）能正确运行 基本能正确运行 能运行但结果不完善（20分） （15分） （10分）程序功能的完善程度（占总成绩10%）完善 基本完善 不完善（10分） （8分） （5分）程序结构的合理性（占总成绩10%）合理 基本合理 不太合理（10分） （8分） （5分）对问题的答辩情况（占总成绩40%）概念正确有创新 能正确回答所有问题 基本能正确回答（40分） （35分） （30分）部分问题回答概念不清晰（20分）学生的工作态度与独立工作能力（占总成绩10%）工作态度认真能独立完成任务 工作态度认真但独立性较差（10分） （8分）工作态度基本认真但缺乏独立性（5分）设计报告的规范性（占总成绩10%） 符合规范 基本符合规范 规范性较差（10分） （8分） （5分）优秀：90分100分 良好：80分89分 中等：7079分 及格：6069分 不及格0分59分 武汉科技大学计算机科学与技术学院制表 计算机科学与技术学院课 程 设 计 报 告课程名称： 数据结构课程设计 专 业： 计算机科学与技术 班 级： 2011级03班 学 号： 201113137131 姓 名： 彭 伟 华 指导老师： 李 顺 新 2013年9月20日计算机科学与技术专业课程设计任务书设计题目小区便利店选址问题学生姓名彭伟华所在院系计算机科学与技术专业、班级计科1103主要内容：对于某一小区便利店，其他各栋楼到其的距离不同，同时各栋楼的居民数也各不相同，不考虑各居民去超市的频率，请为便利店选址，要求实现总体最优，方便更多的住户购物。 【提示】1）便利店无论选址何处，八栋楼的居民均可直接到达，即八栋楼与便利店均相邻，且距离为直线距离；2）八栋楼的居民人数为权重，应该方便大多数人，实现总体最优。学生应完成的工作：l 设计友好的用户界面l 数据设计合理，模块划分清晰l 程序能正确无错误地运行，提交完整源代码l 写出符合要求的课程设计报告书参考文献阅读：1 数据结构（C语言版） 严蔚敏 清华大学出版社.2 数据结构题集（C语言版） 严蔚敏 清华大学出版社.3 c语言程序设计 谭浩强 清华大学出版社. 4数据结构与算法分析 张铭 电子工业出版社 5 DATA STRUCTURE WITH C+ William Ford,William Topp 清华大学出版社工作计划：第1-2天：课题分析与总体设计第3-7天：程序设计，调度与测试第8-9天：设计总结，完成课程设计报告书第10天： 检查考核任务下达日期：2013 年 9 月 10 日任务完成日期：2013 年 9 月 20 日 学生（签名）： 便利店选址摘要：该课题是为小区内的某一便利店选址，要求实现总体最优，这是带权的最小生成树的问题，小区平面图采用邻接矩阵表示，设计小区的平面图是一有向网，边表示各单位到便利店的路径，边上的权值表示路径的长度。关键词：权 邻接矩阵 有向网1 引 言1.1课题背景便利店的选址问题是一个很复杂的决策过程，既需要定性分析，又需要定量计算。选址问题主要取决于店铺位置的地形特点及其周围的人口状况、城市设施状况、交通条件、地租成本和竞争环境等，正确的选址决策能在减少投资运行成本的同时提高经济效益。近几年，由于选址数据的愈加复杂以及计算机技术的迅速发展，人们开始利用计算机的强大计算能力对选址数据进行分析计算，从而决定最佳的选址方案。1.2课程设计目的数据结构是计算机学科实践性很强的一门核心课程。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C（C+）程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。1.3 课程设计任务对于某一小区便利店，其他各栋楼到其的距离不同，同时各栋楼的居民数也各不相同，不考虑各居民去超市的频率，请为便利店选址，要求实现总体最优，方便更多的住户购物。 【提示】1）便利店无论选址何处，八栋楼的居民均可直接到达，即八栋楼与便利店均相邻，且距离为直线距离；2）八栋楼的居民人数为权重，应该方便大多数人，实现总体最优。通过该题目的设计过程，可以加深理解图数据结构，掌握某些基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。1.4 系统开发平台1、题目：便利店选址2、开发工具： Microsoft Visual C+6.03、操作系统：Windows 72 系统结构分析2.1需求分析核心问题: 求最短路径(选址的要求就是便利店到各单位权值之和最少)数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*人数)存储结构: typedef struct string vexsMAX_VERTEX_SIZE; int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE; int vexnum;/ ,arcnum;MGraph; 核心算法: Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径) 输入数据: 单位个数、各单位地址、各单位人数输出数据: 便利店地址值总体思路:如果便利店所选地址为（x,y），那么先求出各单位到该地址的含参直线距离，在保证总体最优（权值最小）的情况下计算出便利店地址的精确值。 2.2方案选择 1）直角距离选址模型使总体最优的的便利店选址问题可表述为：minZ=CjQj（|X-Xa|+|Y-Ya|）可将问题分解成两个单独最小化问题：minZ= minZ1+ minZ2minZ1=minCjQj|X-Xa|minZ2=minCjQj|Y-Ya|2)欧式距离选址模型两点之间的欧式距离定义如下：Dj=(X-Xa)*(X-Xa)+(Y-Ya)*(Y-Ya)使总体最优的便利店选址问题可表述为：minZ=CjQj(X-Xa)* (X-Xa)+(Y-Ya)* (Y-Ya)分别求Z对Xa和Ya的偏导数，令所得方程等于零，求Xa和Ya的值：Xa=(CjQjXj/Dj)/ (CjQj/Dj)Ya=(CjQjYj/Dj)/ (CjQj/Dj)3)修正距离选址模型在方案2）所得结果的基础上，采用迭代法求解更精确的结果。Dj=k(X-Xa)* (X-Xa)+(Y-Ya)* (Y-Ya) minZ=kCjQj(X-Xa)* (X-Xa)+(Y-Ya)* (Y-Ya)由于本课题所给数据比较简单，通过综合比较分析，本课题决定采用方案1）。3 应用程序设计3.1流程图设计开始Main（）输入基本信息GreatMgraph（Gh）建立邻接矩阵的存储结构Floyd算法NYAij=INF,i!=ji到j不存在路径输出i-j的路径和路径长度Floyed（Gh）输出超市的最佳地址：i结束3.2源程序#include #include using namespace std; struct building double x; double y; double value; ; building bd1000; int n;/n栋楼 double minx,maxx,miny,maxy;/记录各栋楼的区域 double midx,mmidx,midy,mmidy; double result_x,result_y,sum = 100000;/最后结果 double dis(double x,double y)/计算距离 double sum= 0; for(int i = 0;i 0.01) while(maxy-miny)0.01) if(dis(midx,midy) dis(midx,mmidy) miny = midy; else maxy = mmidy; midy = (miny + maxy)/2; mmidy = (midy + maxy)/2; ; if(dis(midx,midy) dis(mmidx,midy) minx = midx; else maxx = mmidx; midx = (minx + maxx)/2; mmidx = (midx + maxx)/2; ; result_x = midx; result_y = midy; sum = dis(result_x,result_y); int main() coutn; coutn请输入各楼x y 权值endl; minx = maxx = miny = maxy = 0; for(int i = 0;i bdi.xbdi.ybdi.value; if(bdi.x maxx) maxx = bdi.x; if(bdi.y maxx) maxy = bdi.y; D_Divide(); coutn便利店选址坐标为:endl; coutx: result_x y: result_yendl; coutn最优解为: sumendl; return 0; 4 测试与结果通过测试可以发现程序设计中存在的很多问题，通过解决一个个的问题，可以更好的完善程序功能。4.1测试过程截图4.2调试分析（1）调试中遇到的问题及对问题的解决遇到的问题：在调试时发现，写入程序是产生的数据、函数定义不当、函数调用不当等问题。还有一些在输入数据时产生的输入值、输入范围不相匹配的错误。解决方法：对于前一问题，在程序调试中根据系统提示找到相应出错行。细心分析、多方求证，最终得到顺利解决。对于后一问题，可根据事先程序中写入的相关提示就可以解决，如无提示就返回相关实现的算法程序中查找。（2）算法的时间复杂度以及空间复杂度 时间复杂度为：O（n3）,空间复杂度为：O（1）5 总 结本次课程设计的题目是小区便利店的选址问题，要求实现总体最优。在编写程序的过程中遇到了许多的问题，在解决问题的同时对邻接矩阵，最小生成树，有向网等进一步加深了了解，强化了在上课学的知识，对自己提高很大,同时了解到自己专业基础知识的不足，所以我还要通过不断的学习，不断的充电自己。通过该题目的设计过程，初步掌握数据结构的基本理论和方法，及用C语言设计编写程序的技巧，提高了解决实际问题的能力。通过对本次课程设计的总结，我也有如下经验教训：1、程序代码工作开始之前，一定要首先进行需求的具体分析，只有对于需求有了全面客观的掌握，才能确定程序所应实现的功能，从而在以后的代