数据结构课程设计学校超市选址问题.doc

学校超市选址问题
学生姓名

专业班级

学号

题　 目
学校超市选址问题
课题性质
工程设计
课题来源
自选课题
指导教师

同组姓名
无
主要内容
对于某一学校超市,其她各单位到其得距离不同，
同时各单位人员去超市得频度也不同。
请为超市选址，要求实现总体最优。

任务要求

1、实现公司到超市距离，频率最优.
2、 确定超市位置，要求实现总体最优.

参考文献
《C程序设计》第三版 谭浩强 著 　清华大学出版社
《数据结构》(C语言版） 严蔚敏　著 清华大学出版社
《数据结构及应用》沈华 等编著 机械工业出版社
审查意见
指导教师签字：
教研室主任签字： 　 　 　 　　 　　 　　 　

一、需求分析
　　１）核心问题： 求最短路径（选址得要求就就是超市到各单位权值之与最少）
２）数据模型（逻辑结构):　带权有向图 （权值计算： 距离＊频度）
3)存储结构: typedｅｆ struｃt
{
string　veｘs[MAX_ＶERTEX＿SIZＥ]；
ﻩint arｃs［ＭＡX＿VERTEＸ_ＳIZE］[MAX_VEＲTEX_SIZE］；
iｎt vexｎｕm；// ，ａrcｎｕm；
}MGrapｈ；
核心算法： Ｆloyｄ算法（弗洛伊德算法—每一对顶点之间得最短路径）
输入数据： 各单位名称，距离,频度，单位个数．
输出数据： 所选单位名称。
总体思路： 如果超市就是要选在某个单位，那么先用floyd算法得出各顶点间得最短距离/最小权值。
假设顶点个数有n个,那么就得到n*n得一张表格，aｒｃs(i，ｊ）表示ｉ单位到j单位得最短距离／最小权值 , 这张表格中与最小得那一行(假设为第t行），那么超市选在t单位处就就是最优解.
2 运行环境
　Ｖisｕal Sｔdio C++６、０
ﻩＷindows Vｉsta/2003/XP
3 概要设计
Floｙｄ算法利用动态规划思想，通过把问题分解为子问题来解决任意两点见得最短路径问题。设Ｇ=(V, Ｅ， w）就是一个带权有向图，其边V＝{v1, v2, …，　vn}。对于k≤n，考虑其结点V得一个子集。对于Ｖ中任何两个结点vi、vｊ，考虑从vi到vj得中间结点都在ｖk中得所有路径，设该路径就是其中最短得,并设它得路径长度为最短路径长度.如果结点vｋ不在从vｉ到vj得最短路径上,则;反之则可以把分为两段，其中一段从vi到vk，另一段从ｖk到vｊ,这样便得到表达式.上述讨论可以归纳为如下递归式:
原问题转化为对每个i与ｊ求，或者说求矩阵
开始
流程图

Main()

输入基本信息

GreatMgraph(Gh)

建立邻接矩阵得存储结构

Floyd算法

N

Y
A[i][j]==INF,i!=j

i到j不存在路径

Floyed(Gh)

输出i->j得路径与路径长度

输出超市得最佳地址:i

结束

４ 详细设计
第一步，让所有路径加上中间顶点１,取A[i]［j]与A［i］［１］+A［1］［j]中较小得值作A［i][j］得新值,完成后得到A（1),如此进行下去,当第ｋ步完成后，A（k）[i］[j］表示从i到就且路径上得中间顶点得路径得序号小于或等于k得最短路径长度。当第n—1步完成后，得到A(ｎ-1），A（n-1）即所求结果。A（ｎ-1)［i］［j］表示从i到j且路径上得中点顶点得序号小于或等于ｎ-1得最短路径长度，即A(n－1）[ｉ]［j]表示从i到j得最短路径长度。
4、1头文件与变量设定 　
＃inclｕdｅ 〈sｔring、ｈ〉
＃inｃlude 〈stdiｏ、h〉
＃iｎｃluｄe ＜stdｌｉb、h>
#includｅ ＜tiｍe、h〉
＃ｉncｌude ＂ｍallｏc、h＂
＃iｎcludｅ <iostrｅam、ｈ>
＃ｄefine TUＲＥ 1
#dｅfｉne ＦＡLSE　0
#ｄefiｎe OK 1
#deｆine　ERROR ０
＃define　ＯＶERFLOW －1
＃ｄefine ＩNF 32767
const inｔ MAXＶEX=10０；
typｅｄef　cｈar　Vextype；
４、2结构体得定义
typedef sｔrｕcｔ
｛
ﻩVexｔype vexs［MAXVEX］[MAＸVEX]； 　　 　 //单位名称（顶点信息);
ｉnｔ adｊ[MAXＶEX][MAXVEＸ］； ﻩ //单位之间得相通情况(就是否有边);
iｎt ｄis［MＡXVEX］[MAXVEＸ］；ﻩﻩﻩﻩ//单位间距离(边得长度)；
ﻩinｔ f[MＡXVEX]；ﻩﻩﻩﻩﻩ ﻩ／/各单位去超市得频率;
int n； ﻩﻩ ﻩﻩﻩ//顶点数与边数；
ﻩｉｎｔ e；
}Ｍgrａph；
4、3变量得输入
ｖoiｄ ＣｒeatMgraｐh（Ｍｇraph *G）　　 　
｛
int i,j,k；
prｉntf（”请输入单位个数：\ｎ"）;
ﻩ scanf（＂％d”，＆(G-〉n)）；
pｒintｆ(”请输入单位间得路径数:\n");
scａnf(”％d"，＆（Ｇ-〉e））；
ﻩｐrintf（”请输入单位名称:\n＂）；
fｏr（i=0;i<G－＞n；i+＋）
｛
ﻩ pｒｉntf（"请输入第%d个单位名称：＼n"，i)；
sｃanｆ（"％s"，＆G->vexs［ｉ]);
｝
ﻩfor（i=０；ｉ〈Ｇ－>n；i+＋)ﻩ ﻩ //结构体得初始化；
ﻩﻩfor(ｊ=0;j〈G-〉n;j++）
ﻩﻩ{
ﻩﻩＧ->adj[i］[j]=０；
ﻩＧ-〉dis［i］[j］=０；
ﻩ Ｇ-〉f［i］=0;
ﻩ}
for（k=０；ｋ〈Ｇ－〉e;k+＋）
｛
ﻩ ｐrｉｎtf("请输入相通得两单位 (输入格式：i，ｊ)：\n”);
ﻩﻩscanf（"%ｄ，％d",＆i,＆j）；//在距离上体现为无向；
ﻩﻩprｉntf（"请输入相同两个单位间得距离（格式：dis)：\ｎ＂);
ﻩscanf(”%ｄ"，＆（Ｇ-〉diｓ［i][j］））；
ﻩﻩG->adｊ［ｉ]［ｊ]=1；
ﻩ G－〉adj［ｊ］[i]=1;
ﻩG－>ｄis［j]［i］=G－＞dｉs［i］[ｊ］;
ﻩ｝
ﻩfｏr（k=0;k＜Ｇ－〉n；k++）
ﻩ{
ﻩ priｎｔｆ(”请输入第%d个单位去超市得相对频率:＼n”，k）；
ﻩｓcaｎf（”％d”,＆（Ｇ－〉f［k]））;
ﻩ}
ﻩｆoｒ(i=0；i＜G—>n;i++）ﻩﻩﻩ ﻩﻩ 　 //以距离与频率之积作为权值;
ﻩ foｒ(j=0；j<Ｇ—〉n；ｊ+＋）
｛
G－>dis［ｉ］[j］＊＝G-〉f［i］;　 　　　 ／/最终权值非完全无向;
ｉｆ(G—＞adj[i]［j]==0＆&ｉ！=j)
ﻩ ﻩﻩG－>dis［i]［j]=INF；
ﻩﻩ}
｝
4、4带权有向图求最短路径flｏyd算法
vｏiｄ Floyｅｄ（Mgrapｈ *G） 　 ／/带权有向图求最短路径floyd算法
｛
ﻩinｔ A[MAXVＥX]［MAＸVEX]，patｈ［MAＸVＥX］［MＡＸＶEX］;
ﻩiｎｔ i,j,k,ｐｒｅ;
ｉｎｔ counｔ[MAXVEX]；
foｒ(ｉ=0;i〈G-＞n;i+＋) 　 　 //初始化Ａ[］［］与ｐatｈ［］［］数组
for（j=0;j〈Ｇ—〉ｎ;j++) 　 　 　　　　 　 //置初值；
ﻩﻩ{
ﻩﻩA[i］［j]=G—>dｉs[ｉ］［j]；
ﻩﻩﻩpａｔh［i］[ｊ]=-1；
ﻩﻩﻩcoｕnｔ[i］=0;
}
ﻩfoｒ（k=０;k<Ｇ—＞n；k+＋) 　 ／／ｋ代表运算步骤
{
ﻩ for(ｉ=0;ｉ<G->ｎ；i++）
for(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;
ﻩﻩﻩﻩ}
ﻩ｝
cｏuｔ<〈endl＜＜"Floyed算法求解如下：＂〈<ｅndl；
ﻩfｏr（i=０；i<Ｇ—＞n;i＋+）
for(j=0;j＜Ｇ－〉n;j++)
ﻩ｛
ﻩﻩﻩiｆ（ｉ!=j）
ﻩ {
ﻩﻩ cout<〈" "〈＜ｉ<〈”—>"〈〈j＜＜”；"；
ｉf(A［i]［j]=＝ＩNF）
ﻩ ﻩ｛
ﻩﻩ ﻩﻩif(i!=j)
ﻩ coｕt〈＜"不存在路径”<<”\n＂＜<ｅndl；
ﻩ ｝
ﻩelse
ﻩﻩﻩ {
ﻩﻩﻩcout<〈"路径长度为："＜<A［i]［ｊ］〈<"\n＂；
ﻩﻩﻩ cout〈＜＂路径为:"<〈i〈〈”*＂;
ﻩﻩﻩﻩpre=path［i］［j];
ﻩ while（pre！=—1)
ﻩ ﻩ {
ﻩ ﻩ ﻩcout<<pｒe＜＜”\n＂；
ﻩ ﻩﻩﻩprｅ＝path［ｐrｅ]［j］;
ﻩ ﻩ}
ﻩ ﻩ ﻩｃｏut〈〈j〈〈endl；
ﻩ ﻩ｝
ﻩﻩﻩ}
｝
　 //以下为选择总体最优过程，然后确址;
ﻩｆｏr(i＝0；i＜Ｇ-＞n;i++）
ﻩ for（ｊ=0；ｊ〈Ｇ－〉n;j＋+)
ﻩ｛
ﻩ ﻩｉｆ(Ａ［ｉ][j]==IＮF)
ﻩ count［i]＝0;
ﻩ eｌｓe
ﻩcouｎｔ［i］=1；
｝
ﻩfｏr（i=０；i<G-〉n；i＋＋)
ﻩｉf（counｔ［i］)
{
ﻩ fｏr（j=0;j<G-〉n;j++）
ﻩif(i!=j)Ａ［i］［i]+＝Ａ［j]［ｉ]；
｝
　 k=0;
fｏr（i=０；i〈Ｇ—>ｎ;i＋＋）
ﻩ{
ﻩ if（cｏunt［ｉ]）
ﻩ ﻩif(A[k］［k]>A［i][i］）
ﻩ ﻩﻩk＝i;
｝
ﻩcout<＜"超市得最佳地址为:”＜＜Ｇ-〉vexs［k］＜＜endl;
}
4、5主函数模块
void　main()
{
Mｇraｐh ＊Gｈ=NULL；
Ｇh=(Ｍgrａph *）mallｏc（sizeｏｆ（Ｍgrａph)）；
ﻩCreatMｇraｐｈ（Gｈ);
Floyeｄ（Gh）；
ﻩｓystem（＂pause＂)；
｝
5 调试分析
5、１本题目得关键点之一：
有两个权值：各单位到超市得距离及各单位人去超市得频度。这使得图得建立出现了困难,经过分析这两个值可以合并为一个权值即distａｎce＊ｆrequency;这样就使得图得建立轻而易举。
5、２本题目得关键点之二：
　　 　利用flｏｙd算法求出每一对顶点之间得最短路径.
5、3本题目得关键点之三：
ﻩ 选出最短路径，即最佳地点应使其到其她单位权值最小.注意：每比较一次patｈ应清0一次（Path=0）。
6 设计程序如下：
＃incｌude　<sｔring、ｈ〉
#inｃlude ＜sｔdio、h＞
＃inｃlude ＜stｄｌib、h＞
#include <ｔｉｍe、h〉
#inｃlude "maｌloｃ、h"
＃incｌuｄｅ 〈iostｒｅam、ｈ〉
#define TURE １
＃ｄefine ＦALＳE　0
#deｆine　OK 1
#defiｎe　ERROＲ　0
#dｅfiｎｅ　OVERFLＯW -1
＃ｄeｆｉne INF ３2７67
ｃonst　int　ＭAXVEX=１00;
ｔyｐedef chaｒ Vextypｅ；
typeｄｅf sｔｒuct
｛
Vｅｘｔｙpｅ　vexs［ＭAXVＥX］[MＡＸＶＥX］；　 　 　 　//单位名称（顶点信息）；
int adｊ[MＡXＶＥX][MAXVＥX]； //单位之间得相通情况(就是否有边)；
iｎt dis[MAXVEＸ］［MＡXVEX]； //单位间距离(边得长度）;
ﻩint f[ＭAXVEX］; ﻩﻩ ﻩ/／各单位去超市得频率；
ﻩint n; ﻩﻩ ﻩ ﻩ ／/顶点数与边数；
ｉnt e；
}Mgraph；
void ＣreaｔMgraph(Mgraph　*G） 　
{
ﻩｉnt i，j，k；
prinｔf（"请输入单位个数:\ｎ＂）;
ﻩ sｃaｎｆ("％d"，&（G->n）)；
pｒintf（＂请输入单位间得路径数：\n")；
ﻩsｃanf(”％ｄ"，＆（G-〉e));
ﻩpｒintf（"请输入单位名称:\ｎ"）;
ｆor(ｉ=0;ｉ＜Ｇ—〉n;ｉ+＋）
ﻩ｛
ｐrinｔｆ("请输入第%d个单位名称：\ｎ＂，i）；
ﻩﻩscａnf（＂％s＂，＆G—〉vexs［i］）;
ﻩ}
ﻩfｏr（ｉ=０；i〈G->n;i++）ﻩﻩ ﻩﻩﻩ 　//结构体得初始化；
ﻩﻩfor(ｊ=0;j〈Ｇ—>n;j＋+）
{
ﻩ ﻩG－〉ａｄj［ｉ］［j］＝0;
G-＞dis［i］［j]=0；
ﻩ ﻩG—〉ｆ[i］=0；
ﻩﻩ}
ﻩfor（k＝0；k<G—>e；k+＋）
{
ﻩﻩpｒｉntf（＂请输入相通得两单位 (输入格式：i，j)：＼ｎ")；
ﻩsｃaｎf（"%d，%d”,&ｉ,＆j）;//在距离上体现为无向；
pｒｉｎtf（"请输入相同两个单位间得距离(格式:dｉs）：\n”)；
ﻩﻩｓcanf(”%ｄ"，&(G->diｓ［i]［ｊ］））；
ﻩG—〉adｊ［i］［j］=1;
ﻩﻩG－>aｄj［j］[i］=1；
Ｇ-〉dis［j］[i］＝Ｇ-〉dｉs［i］[j］;
｝
for（k＝０;k〈G—＞ｎ；k++)
｛
pｒintf(”请输入第％d个单位去超市得相对频率：\n”,k)；
scanf(”%d"，&（G—〉ｆ［k］））;
ﻩ｝
for（i=0；ｉ<Ｇ－＞ｎ;i+＋） ﻩ ﻩ 　／/以距离与频率之积作为权值；
ﻩ for（ｊ=0;j<Ｇ-〉n；j++)
ﻩﻩ{
ﻩﻩG—〉dis[ｉ］［j］*=G-〉ｆ［i］;　 　 　 　　　 ／／最终权值非完全无向；
ﻩﻩiｆ（G-〉adj[i][j]=＝0＆＆i!=ｊ）
ﻩ ﻩﻩG－>diｓ[i］［j]=INF；
｝
}
voiｄ Floyｅｄ（Ｍｇraph　*G) 　 　　 　 //带权有向图求最短路径floyd算法
{
ﻩｉｎt A[ＭAXVEX］[MＡXVEX］,path［MAXVEX］［MAＸＶEX］；
ﻩinｔ i,j，k,pre;
ﻩiｎｔ　count[MAＸVEX];
ﻩｆor(i=0；ｉ〈G—>n；i++) 　 　　 /／初始化A［］［]与ｐaｔh[][］数组
ﻩﻩfｏr(j=0；j＜G—〉n;ｊ+＋) 　 　 　　 　 　 //置初值;
{
A[i]［j］=Ｇ—＞dｉs［ｉ］［j］；
ﻩ path[ｉ]［j］=-1；
ﻩ couｎt［i]=0；
}
ﻩｆor(k=0;ｋ〈Ｇ->ｎ;k＋+） 　 //k代表运算步骤
ﻩ｛
ﻩﻩfor（i=０;i〈G－〉n;i++）
ﻩﻩfor(j=0；j＜G－〉ｎ;j++)
ﻩ ﻩ if（A[i]［ｊ]>(Ａ[ｉ］［ｋ］+A[k]［j])） 　　 　/／从i经j到ｋ得一条路径更短
ﻩ｛
ﻩ ﻩﻩﻩA[ｉ]［j］=A［ｉ]［k］+Ａ[ｋ]［j];
ﻩﻩ pａth［i]［j］=k；
｝
}
ﻩcouｔ<＜enｄｌ＜〈"Floyｅd算法求解如下：＂〈〈eｎdｌ；
for(i=０；i＜G—＞ｎ；i++）
ﻩ for（j=０;ｊ<G->n；j＋+)
｛
ﻩｉf（i！=j）
ﻩ{
ﻩﻩﻩcout〈<” ”〈<ｉ<<"-＞"<〈j<〈"；”；
ﻩﻩｉf(A［ｉ]［j]==INF）
ﻩ ﻩ{
ﻩﻩﻩ ｉｆ（i!=ｊ)
ﻩ cｏut〈〈"不存在路径"＜〈”\ｎ＂〈＜eｎdl;
ﻩﻩ ﻩ｝
ﻩ elsｅ
｛
ﻩ ﻩﻩcout<<”路径长度为："〈〈Ａ［i］[ｊ］<〈”\n"；
ﻩ ﻩﻩcoｕt<<”路径为:”<〈i＜＜"＊";
ﻩﻩﻩ ﻩprｅ=ｐatｈ［i]［j］；
ﻩﻩﻩ while（pｒe！=-1)
ﻩﻩﻩ{
ﻩﻩ ﻩcｏut〈<pre＜<"\n";
ﻩﻩ ﻩ pre=patｈ[pre］［ｊ］；
ﻩﻩﻩﻩ｝
ﻩﻩﻩﻩ coｕt<＜ｊ<<eｎｄｌ；
ﻩ ﻩﻩ｝
ﻩ ｝
ﻩﻩ}
/／以下为选择总体最优过程,然后确址;
for(ｉ=0；i〈G－〉n；i++）
ﻩｆｏr（j＝0；j〈Ｇ-〉n;j++）
ﻩﻩ｛
ﻩif（Ａ［i]［ｊ]==ＩNF）
ﻩ ｃｏunt［i]=0；
ﻩﻩｅlse
ﻩcouｎｔ［i]=1；
ﻩﻩ}
foｒ（i=０；i〈G-〉ｎ；i＋＋）
ﻩ if(counｔ［i］）
ﻩﻩ{
ﻩ for（j=0;j＜G—>n；ｊ＋+）
ﻩ ﻩiｆ(i!＝ｊ)A［i]［i］+=A［j][ｉ];
｝
ﻩﻩｋ=0；
fｏr（i=0;i<G—〉n;ｉ++)
{
ｉｆ（cｏunt［i]）
ﻩ ｉf(Ａ［k]［k]>Ａ［i］［i])
ﻩ ﻩk=i;
ﻩ｝
ﻩcｏut<＜"超市得最佳地址为：”＜＜G—＞veｘｓ［k]<〈endｌ；
}
voｉd maiｎ（)
{
Mgraｐｈ　＊Gh＝NUＬL；
Gh=（Ｍgrａｐh *)ｍaｌloc（ｓizeoｆ（Mｇrａpｈ)）；
ﻩCｒeatMgrａｐｈ(Gh);
ﻩＦloｙed(Ｇｈ)；
ﻩsyｓtem(＂pause”)；
｝
/＊测试数据:
输入:
单位个数
4
单位间得路径数
6
第0个单位名称
A
第１个单位名称
B
第2个单位名称
C
第3个单位名称
D
相通两单位 　 之间得距离
０，1 　 　 　 　 2
１，2　 　　 　　 　　 　 3
２，3　 　 　　 　 　 　 4
０，３ 　 　 　 　 　 　　１
０,2　 　 　　 　 2
1,3　　 　 　　　　 　 　 ３
第0个单位去超市得频率　 　　 2
第1个单位去超市得频率 　 ４
第2个单位去超市得频率 　　　　3
第3个单位去超市得频率　 １
*／
７ 测试结果
　7、1输入

　 ７、2输出

参考文献:
　　 1、《C程序设计》第三版 谭浩强 著　 清华大学出版社
　 　 2、《数据结构》（C语言版) 严蔚敏　著　 清华大学出版社
　　 3、《数据结构及应用》沈华 等编著　机械工业出版社
　总 　 结
终于完成了本次数据结构课程设计，对我来说这就是一项不小得挑战，它不仅检验了我得学习情况,也考验了我得意志力，让我有了很大得收获!
通过一学期得学习,我知道数据结构就是一门纯属于设计得科目,它需用把理论变为上机调试。在学习科目得第一节课起，老师就为我们阐述了它得重要性。它对我来说具有一定得难度。它就是其它编程语言得一门基本学科.ﻪ之前我刚学习数据结构时感觉很吃力,因为书上都只就是提供一些通用得结构算法，并没有具体得题目与完整得程序来让我体会数据结构在程序中所体现得作用。　但就是经过自己到图书馆借阅相应得书籍，并且在每次上机时大胆实践,我逐渐体会到数据结构就是计算机科学与技术专业得一门核心专业基础课程,在我们专业得课程体系中起着承上启下得作用,学好数据结构对于提高理论认知水平与实践能力有着极为重要得作用。学习数据结构得最终目得就是为了获得求解问题得能力。对于现实世界中得问题,应该能从中抽象出一个适当得数学模型，该数学模型在计算机内部用相应得数据结构来表示，然后设计一个解此数学模型得算法,再进行编程调试，最后获得问题得解答。
　　　 　　　书本知识用于实际应用，才就是我得目标，这次课程设计给了我锻炼自我突破自己得机会. 通过这次数据结构课程实践，我对数据结构这门课程有了更深得认识与体会,同时实践得成功极大增强了我对继续学习相关知识得信心与兴趣！