超市选址问题

C语言与数据结构课程设计报告学号2011013718姓名薛磊课程设计题目学校超市选址问题本课程设计共三人:薛磊，肖腾达，张萌2013年1月

1需求分析功能与数据需求：核心问题:求最短路径(选址的要求就是超市到各单位权值之和最少)数据模型（逻辑结构）:带权有向图(权值计算:距离*频度)存储结构:typedefstruct{ stringvexs[MAX_VERTEX_SIZE]; intarcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE]; intvexnum;//,arcnum;}MGraph;核心算法:Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径)输入数据:各单位名称，距离，频度，单位个数．输出数据:所选单位名称．总体思路:如果超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。假设顶点个数有n个，那么就得到n*n的一张表格，arcs(i,j)表示i单位到j单位的最短距离/最小权值,这张表格中和最小的那一行(假设为第t行)，那么超市选在t单位处就是最优解。界面需求该程序界面很简单，用户只需将各单位的基本信息输入就可以了，然后输出floyd算法跟各单位到超市的距离和路径，最后选出最优超市选址。（1）输入数据:各单位名称，距离，频度，单位个数．（2）输出数据:所选单位名称．1.3开发环境与运行需求程序运行于MicrosoftVisualC++6.0。2概要设计2.1主要数据结构本程序采用了带权有向图(权值计算:距离*频度)的存储结构typedefstruct{ Vextypevexs[MAXVEX][MAXVEX];//单位名称（顶点信息）； intadj[MAXVEX][MAXVEX]; //单位之间的相通情况（是否有边）； intdis[MAXVEX][MAXVEX]; //单位间距离（边的长度）； intf[MAXVEX]; //各单位去超市的频率； intn; //顶点数和边数； inte;}Mgraph;voidCreatMgraph(Mgraph*G)voidFloyed(Mgraph*G)//带权有向图求最短路径floyd算法2.2程序总体结构Floyd算法利用动态规划思想，通过把问题分解为子问题来解决任意两点见的最短路径问题。设G=(V,E,w)是一个带权有向图，其边V={v1,v2,…,vn}。对于k≤n，考虑其结点V的一个子集。对于V中任何两个结点vi、vj，考虑从vi到vj的中间结点都在vk中的所有路径，设是其中最短的，并设的路径长度为。如果结点vk不在从vi到vj的最短路径上，则；反之则可以把分为两段，其中一段从vi到vk，另一段从vk到vj，这样便得到表达式。上述讨论可以归纳为如下递归式：原问题转化为对每个i和j求，或者说求矩阵开始流程图开始MMain（）输入基本信息输入基本信息GreatMgraph（Gh）GreatMgraph（Gh）建立邻接矩阵的存储结构建立邻接矩阵的存储结构Floyd算法Floyd算法NNYA[i][j]==INF,i!=jYA[i][j]==INF,i!=ji到j不存在路径i到j不存在路径Floyed（Gh）Floyed（Gh）输出i->j的路径和路径长度输出i->j的路径和路径长度输出超市的最佳地址：i输出超市的最佳地址：i结束结束2.3各模块函数声明1.头文件和变量设定#include<string.h>#include<stdio.h>#include<stdlib.h>#include<time.h>#include"malloc.h"#include<iostream.h>#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1#defineINF32767constintMAXVEX=100;typedefcharVextype;2.结构体的定义typedefstruct3.变量的输入voidCreatMgraph(Mgraph*G)4.带权有向图求最短路径floyd算法voidFloyed(Mgraph*G)//带权有向图求最短路径floyd算法3详细设计3.1算法分析与设计第一步，让所有路径加上中间顶点1，取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的新值，完成后得到A(1),如此进行下去，当第k步完成后，A（k）[i][j]表示从i到就且路径上的中间顶点的路径的序号小于或等于k的最短路径长度。当第n-1步完成后，得到A（n-1），A（n-1）即所求结果。A（n-1）[i][j]表示从i到j且路径上的中点顶点的序号小于或等于n-1的最短路径长度，即A(n-1)[i][j]表示从i到j的最短路径长度。3.2主要程序段设计结构体和变量设定#include<string.h>#include<stdio.h>#include<stdlib.h>#include<time.h>#include"malloc.h"#include<iostream.h>#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1#defineINF32767constintMAXVEX=100;typedefcharVextype;结构体的定义typedefstruct{ Vextypevexs[MAXVEX][MAXVEX];//单位名称（顶点信息）； intadj[MAXVEX][MAXVEX]; //单位之间的相通情况（是否有边）； intdis[MAXVEX][MAXVEX]; //单位间距离（边的长度）； intf[MAXVEX]; //各单位去超市的频率； intn; //顶点数和边数； inte;}Mgraph;变量的输入voidCreatMgraph(Mgraph*G){ inti,j,k; printf("请输入单位个数:\n"); scanf("%d",&(G->n)); printf("请输入单位间的路径数:\n"); scanf("%d",&(G->e)); printf("请输入单位名称:\n"); for(i=0;i<G->n;i++) { printf("请输入第%d个单位名称:\n",i); scanf("%s",&G->vexs[i]); } for(i=0;i<G->n;i++) //结构体的初始化； for(j=0;j<G->n;j++) { G->adj[i][j]=0; G->dis[i][j]=0; G->f[i]=0; } for(k=0;k<G->e;k++) { printf("请输入相通的两单位(输入格式:i,j):\n"); scanf("%d,%d",&i,&j);//在距离上体现为无向； printf("请输入相同两个单位间的距离(格式：dis)：\n"); scanf("%d",&(G->dis[i][j])); G->adj[i][j]=1; G->adj[j][i]=1; G->dis[j][i]=G->dis[i][j]; } for(k=0;k<G->n;k++) { printf("请输入第%d个单位去超市的相对频率:\n",k); scanf("%d",&(G->f[k])); } for(i=0;i<G->n;i++) //以距离和频率之积作为权值； for(j=0;j<G->n;j++) { G->dis[i][j]*=G->f[i];//最终权值非完全无向； if(G->adj[i][j]==0&&i!=j) G->dis[i][j]=INF; }}带权有向图求最短路径floyd算法voidFloyed(Mgraph*G)//带权有向图求最短路径floyd算法{ intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX]; inti,j,k,pre; intcount[MAXVEX]; for(i=0;i<G->n;i++)//初始化A[][]和path[][]数组 for(j=0;j<G->n;j++)//置初值； { A[i][j]=G->dis[i][j]; path[i][j]=-1; count[i]=0; } for(k=0;k<G->n;k++)//k代表运算步骤 { for(i=0;i<G->n;i++) for(j=0;j<G->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; } } printf("Floyed算法求解如下:\n"); for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) { if(i!=j) { printf("%d->%d;",i,j); if(A[i][j]==INF) { if(i!=j) printf("不存在路径\n"); } else { printf("路径长度为:%d",A[i][j]); printf("路径为:%d*",i); pre=path[i][j]; while(pre!=-1) { printf("%d\n",pre); pre=path[pre][j]; } printf("%d",j); } } }//以下为选择总体最优过程，然后确址； for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) { if(A[i][j]==INF) count[i]=0; else count[i]=1; } for(i=0;i<G->n;i++) if(count[i]) { for(j=0;j<G->n;j++) if(i!=j)A[i][i]+=A[j][i]; } k=0; for(i=0;i<G->n;i++) { if(count[i]) if(A[k][k]>A[i][i]) k=i; } printf("超市的最佳地址为:"); printf("%s\n",G->vexs[k]);}主函数模块voidmain(){ Mgraph*Gh=NULL; Gh=(Mgraph*)malloc(sizeof(Mgraph)); CreatMgraph(Gh); Floyed(Gh);}4测试输入：输出5使用说明5.1应用程序功能的详细说明对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。用户只需将各单位的个数，路径数，各单位间距离和各单位去超市的频率输入即可，然后就可输出超市最佳选址。5.2应用程序运行环境要求MicorsoftVisualC++6.05.3输入数据类型、格式和内容限制数据类型主要是整型常量。格式要求：本系统中任何需要输入两个数据时，数据之间用“，”隔开。内容限制：请严格按照系统指定操作执行，不得输入系统规定以外的数据。6总结提高6.1课程设计总结经过42个课时的上机实验，数据结构课程设计终于完成了，对我来说这是一项很大而又很小的挑战，对已第一次设计的我来说，这是一个挑战，对我能力的挑战。它不仅检验了我的学习情况，也考验了我的意志力。但相比以后更加复杂的数据时又显得微不足道！通过一学期的学习，我知道数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。之前我们我们已经学习了C程序设计、离散数学等，以后还要学操作系统、编译原理、数据库原理、软件工程等。通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。

学以致用，这才是我的目标，课程设计给了我这个机会。数据结构是计算机科学与技术专业的一门核心专业基础课程，在我们专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。

通过数据结构课程实践，加上老师的全力指导，无论是理论知识，还是实践动手能力，我都有了不同程度上的提高。6.2开发中遇到的问题和解决方法第一次编写理论与实践相结合的程序，开始面对问题时不知如何下手，通过翻阅书籍与讨论慢慢的将问题转到书本再从书本转到实际问题。在拿到题目的时候首先要确定需要用到的程序算法，小组在根据需要求解的问题对算法逐一讨论和修改，程序可以运行。6.3对自己完成课设完成情况的评价编写程序总体良好，基本可以完成了各项预期操作，唯一不足的就是程序编写的过于繁杂，很多功能还不能灵活运用，这也反映出了我能力的不足，需要更加努力。6.4《C语言与数据结构课程设计》课程的意见与建议通过本课程的学习与实践，使学生掌握独立使用c语言编写程序的能力，掌握分析问题，设计程序和解决问题的能力。通过在本课程中从设计到完成程序的过程中，使学生更进一步系统地掌握《高级语言程序设计》课程的内容。附录：程序源代码#include<string.h>#include<stdio.h>#include<stdlib.h>#include<time.h>#include"malloc.h"#include<iostream.h>#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1#defineINF32767constintMAXVEX=100;typedefcharVextype;typedefstruct{Vextypevexs[MAXVEX][MAXVEX];//单位名称（顶点信息）；intadj[MAXVEX][MAXVEX];//单位之间的相通情况（是否有边）；intdis[MAXVEX][MAXVEX];//单位间距离（边的长度）；intf[MAXVEX]; //各单位去超市的频率；intn; //顶点数和边数；inte;}Mgraph;voidCreatMgraph(Mgraph*G){inti,j,k;printf("请输入单位个数:\n");scanf("%d",&(G->n));printf("请输入单位间的路径数:\n");scanf("%d",&(G->e));printf("请输入单位名称:\n");for(i=0;i<G->n;i++){ printf("请输入第%d个单位名称:\n",i);scanf("%s",&G->vexs[i]);}for(i=0;i<G->n;i++) //结构体的初始化；for(j=0;j<G->n;j++){G->adj[i][j]=0;G->dis[i][j]=0;G->f[i]=0;}for(k=0;k<G->e;k++){ printf("请输入相通的两单位(输入格式:i,j):\n");scanf("%d,%d",&i,&j);//在距离上体现为无向；printf("请输入相同两个单位间的距离(格式：dis)：\n");scanf("%d",&(G->dis[i][j]));G->adj[i][j]=1;G->adj[j][i]=1;G->dis[j][i]=G->dis[i][j];}for(k=0;k<G->n;k++){printf("请输入第%d个单位去超市的相对频率:\n",k);scanf("%d",&(G->f[k]));}for(i=0;i<G->n;i++) //以距离和频率之积作为权值；for(j=0;j<G->n;j++){G->dis[i][j]*=G->f[i];//最终权值非完全无向；if(G->adj[i][j]==0&&i!=j)G->dis[i][j]=INF;}}voidFloyed(Mgraph*G)//带权有向图求最短路径floyd算法{intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];inti,j,k,pre;intcount[MAXVEX];for(i=0;i<G->n;i++)//初始化A[][]和path[][]数组for(j=0;j<G->n;j++)//置初值；{A[i][j]=G->dis[i][j];path[i][j]=-1;co