海南师范大学
课程设计报告书
题目： 学校超市选址问题
院 系： 海南师范大学计算机科学与教育技术系
专业班级： 计算机科学与技术专业（计本二班）
学 号： 200624101101
学生姓名： 杨振平
指导教师： 张学平
2008年 3 月 13 日
目录
1. 需求分析········································3
2. 概要设计········································3
3. 详细设计········································3
4. 调试分析········································9
5. 用户使用说明····································9
6. 测试结果········································9
7. 参考文献·······································15
1．需求分析
输入数据：
各单位编号；
各单位到超市的距离；
各单位人去超市的频度；
按照以上输入数据创建图；
为超市选址实现总体最优
1、该程序可以读取文件中相邻两地点的距离信息，在程序中用邻接矩阵构造一个有向网，并计算网中任意节点到其它节点的最短路径并输出。
2、在磁盘中新建一个文件存储两个地点的距离信息，要求先输入起点，以空格间隔，然后输入终点，再以空格间隔，然后输入这两个地点间的距离，如此法，依次输入各路径间的起点，终点和距离。
3、根据界面所给的提示信息首先输入保存交通网的文件名，然后输入要求哪一个节点到其它节点的最短路径。
4、程序运行后，在屏幕上将输出所求节点经过某些中转站到达它所能达到的节点及最短路径的值，并将各节点与其对应的编号保存到文件“编号与地名对照表”中，以便它用。
5、程序执行的命令包括：（1）求place数组中的记录在顶点向量中的坐标、（2）采用邻接矩阵存储结构，构造有向网
6.输出最优解。
2．概要设计
本程序主要采用带权图来实现超市选址实现总体最优的一些功能。
1.刚开始我们用频度(即人流量)X距离作为权值,算权值最小的,但当距离一定时,人流量大的反而不被选择
如果用距离/频度(即人流量)作为权值,比如一个离1M频度为1人的单位,和离100M频度为100人的单位就出现问题了
2.最后我们想还是人流量最重要了,但网上都说要用在main函数中通过子函数sistant()来求出各单位到超市的距离的平方和，之后求出距离平方和与人数的关系，最后算出相对的最短距离从而确定超市的最优地址。
基本操作：
CreatGraph(MGraph &G)
操作结果：采用邻接矩阵存储结构，构造有向网G
LocateVex(MGraph &G,char * place)
初始条件：用邻接矩阵存储的有向网G已存在
操作结果：返回place数组中的记录在顶点向量中的坐标
3．详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；可采用流程图 N – S 图或PAD图进行描述，画出函数和过程的调用关系图。
(1)元素类型：typedef int VRType;
typedef struct VRType
{
float Adj;
int Adjnum;
int Adjfrequency;
}VRType;//存储距离和频度作为权值，权值类型
typedef char * VertexType;
typedef char PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int * ShortPathTable;
（2）结点类型：typedef struct AreCell
{
VRType adj;//权值
InfoType * info;//附加信息
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;//邻接矩阵
int vexnum,arcnum;//顶点个数，弧的条数
}MGraph;
（3）主程序模块：
void main()
{
MGraph G;
int v,Adjcountminvexnum;//Adjcountmin记录当前总权值的最小值
double Adjcountmin;//Adjcountminvexnum记录当前总权值的最小值对应的起点顶点编号
PrintProMember();//输出程序编程组员
//从文本中输入数据并且创建图
CreatGraph(G);//创建带权有向图
//计算最优解
Adjcountmin=sistant(G,0);//第一轮计算以编号0为起点的相对最短路径的总权值，并将之作为当前相对总权值的最小值记录
for(v=1;v<G.vexnum;v++)//循环比较以所有编号为起点的的总权值，并且记录下相对总权值的最小值及对应的起点顶点编号
{
if(sistant(G,v)<Adjcountmin)
{
Adjcountmin=sistant(G,v);
Adjcountminvexnum=v;
}
}
//输出最优解
Print(G,v,Adjcountminvexnum,Adjcountmin);
system("pause");
}
（4）输出程序编程组员函数模块
void PrintProMember()
{
printf("************************************************************/n");
printf("* 海南师范大学 */n");
printf("* 计本二班 数据结构 课程设计 */n");
printf("* 小组成员:杨振平（组长）、唐田、章捷 */n");
printf("************************************************************/n");
}
（5）构造有向网的模块：
void CreatGraph(MGraph &G)
{
FILE *fp;
int i,j;
char filename[20],place1[10],place2[10],num[10],c;
//初始化邻接矩阵
G.vexnum=0;
G.arcnum=0;
for(i=0;i<MAX_VERTEX_NUM;i++)
for(j=0;j<MAX_VERTEX_NUM;j++)
{
G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;
}
for(i=0;i<MAX_VERTEX_NUM;i++)
G.vexs[i]=NULL;
printf("请输入保存交通网的文档名/n");
gets(filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("不能打开文件%s/n",filename);
exit(0);
}
c=fgetc(fp);
while(c!=EOF)
{
//逐个读取文件中的字符
while(c==' ' || c=='/n')
c=fgetc(fp);
i=0;
while(c!=' ' && c!='/n' && c!=EOF)
{
//将第一个地名保存在place1数组中
*(place1+i)=c;
c=fgetc(fp);
i++;
}
*(place1+i)='/0';//添加结束符
while(c==' ' || c=='/n')
c=fgetc(fp);
i=0;
while(c!=' ' && c!='/n' && c!=EOF)
{
//将第二个地名保存在place2数组中
*(place2+i)=c;
c=fgetc(fp);
i++;
}
*(place2+i)='/0';//添加结束符
while(c==' ' || c=='/n')
c=fgetc(fp);
i=0;
while(c!=' ' && c!='/n' && c!=EOF)
{
//将权值保存在num数组中
*(num+i)=c;
c=fgetc(fp);
i++;
}
*(num+i)='/0';//添加结束符
while(c==' ' || c=='/n')
c=fgetc(fp);
G.arcnum++;//边数加1
i=LocateVex(G,place1);//确定第一个地名在邻接矩阵中的位置
j=LocateVex(G,place2);//确定第二个地名在邻接矩阵中的位置
G.arcs[i][j].adj.Adjnum=Translation(num);
G.arcs[i][j].adj.Adjfrequency=Translationfrequency(frequency);
G.arcs[i][j].adj.Adj=(float)(Translation(num)*Translationfrequency(frequency));//构造邻接矩阵
}
fclose(fp);
if((fp=fopen("标号与地名对照表.txt","w"))==NULL)
{
printf("不能打开文件标号与地名对照表/n");
exit(0);
}
//打印一张标号与地名对照表
for(i=0;i<G.vexnum;i++)
fprintf(fp,"%d表示%s/n",i,G.vexs[i]);
fclose(fp);
//向屏幕输出一张标号与地名对照表
for(i=0;i<G.vexnum;i++)
printf("%d表示%s/n",i,G.vexs[i]);
}
//该函数中调用另两个子模块：
/*求place数组中的记录在顶点向量中的坐标*/
int LocateVex(MGraph &G,char * place)
{
int i=0,n;
n=strlen(place);//数组长度
while(i<MAX_VERTEX_NUM && G.vexs[i]!=NULL)
{
if(strcmp(G.vexs[i],place)==0)//找到了存放place数组中内容的顶点向量
return i;
i++;
}
if(i>=MAX_VERTEX_NUM)
{
//空间不足
printf("内存不足/n");
exit(0);
}
G.vexs[i]=(char *)malloc((n+1)*sizeof(char));//顶点向量中没有place中的记录，则建立新记录
strcpy(G.vexs[i],place);
G.vexnum++;//结点个数加1
return i;
}
/*将s数组中保存的权值转换成整型*/
int Translation(char *s)
{
int n,i,j,weight=0,a;
n=strlen(s);//字符串长度
for(i=0;i<n;i++)
{
//求权值
a=1;//系数
for(j=1;j<=n-1-i;j++)
a=a*10;
weight+=a*(s[i]-48);//权值
}
return weight;
}
（6）求各单位到超市v0的相对距离函数模块
float sistant(MGraph &G,int v0)//求出各单位到超市v0的相对距离
{
int v;
float sn=0,sm=0;//sn为各单位到超市v0的距离的平方和,sm为各单位到超市v0的距离和人流量的积的和
for(v=0;v<G.vexnum;v++)//v0到v有路径
{
if(G.arcs[v0][v].adj.Adj<INFINITY)
sn+=G.arcs[v0][v].adj.Adjnum*G.arcs[v0][v].adj.Adjnum;
}
for(v=0;v<G.vexnum;v++)//v0到v有路径
{
if(G.arcs[v0][v].adj.Adj<INFINITY)
sm+=G.arcs[v0][v].adj.Adj;
}
return sn/sm;//G.arcs[v0][v].adj.Adj=将相对距离sn/sm做为权值
}
（7）输出最优解函数模块
void Print(MGraph &G,int v,int Adjcountminvexnum,double Adjcountmin)
{
printf("最优相对总权值为%f/n是以编号%d为起点到其余各单位总体最优的解：/n",Adjcountmin,Adjcountminvexnum);
for(v=0;v<G.vexnum;v++)
{
printf("相对总权值为%f/n是以编号%d为起点到其余各单位总体最优的解：/n",sistant(G,v),v);
}
}
函数和过程的调用关系图如下：
|
main（）主函数 |
|
PrintProMember();//输出程序编程组员函数 |
|
CreatGraph(G);//创建带权有向图函数 |
|
sistant(G,v); //求各单位到超市v0的相对距离函数 |
|
Print(G,v,Adjcountminvexnum,Adjcountmin);//输出最优解函数 |
|
LocateVex(G,place);//求place数组中的记录在顶点向量中的坐标函数 |
|
Translation(s);//将num数组中保存的权值转换成整型函数 |
函数和过程的调用关系图
4．调试分析
内容包括：
a．调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；
1、当输入的地点编号到其于地点没有路径时，程序将输出运行结果。
2、当输入的图不是联通图时，当输入地点编号时，程序照常输出该地点到它所能到达地点的相对最短路径，即在同一个联通分量中的地点。
3、调试中的错误及解决办法文件输入问题调试过程中匹配问题的纠正和改进，各模块在共同数据结构下的整合，以及一些小错误如函数返回值匹配和权衡。
b．算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；
刚开始我们用最优解决算法采用Dijkstra算法计算相对的最短距离，后来我们为符合实际人流量占主要选取标准的原则，改变了算法例如：有三个点A，B，C。对应的人数是：pA,pB,pC.如果确定另一个点为D（未知的）。A，B，C三点到D的距离为：AD，BD，CD。那么k1=AD^2+BD^2+CD^2,k2=pA*AD+pB*BD+pC*CD,满足k1/k2值尽可能的小的地址即为所选。
选择路径规划算法的依据是希望算法的时间复杂性和空间复杂性较小，尤其是前者。从运筹学的学习中大家熟悉的Dijkstra算法是个常用的算法，它计算从一个节点到路网其它各节点的最短路径的时间复杂度是O（n3），表明算法运行时间与网络节点数n的立方成正比。
采用符合实际的新算法后，算法的时间复杂度是O（n2），表明算法运行时间与网络节点数n的平方成正比。不仅符合实际，而且算法的时间复杂度减少，程序的效率更高更好了。
c．经验和体会等。
通过一个多月的努力，我们终于设计并实现出一个既符合实际由相对高效的超市选址系统。这个过程中让我们体会到团队的精神和力量之所在，为以后发展走出了第一步，当算法发生变化时所要调整和修改模块以及相应数据结构的修改的策略以及框架，这次实验设计给我们学习的机会，又学了挺多知识和经验真高兴。
5．用户使用说明
说明如何使用你编写的程序，详细列出每一步的操作步骤。
（1）本程序的运行环境为VC6.0。
（2）进入演示程序后即显示提示信息：
请输入保存交通网的文档名：
（输入保存交通网的文档名，如graph.txt）
当将数据文件调入程序中，程序将通过算法的实现计算出相对最优的超市地址并将结果打印在屏幕上。
6．测试结果
列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。
//测试一
//测试人流量对超市选址的影响，即人流量多的优先选址
//输入数据存放在1.txt中，内容如下：（四个数据分别是起点、终点、距离、人//流量即频度）
A B 400 300
A D 400 300
A E 300 300
B A 400 300
B E 200 300
B F 200 400
B C 400 300
C B 400 300
C D 400 300
C F 300 400
D E 200 300
D F 200 400
D C 400 300
D A 400 300
E A 300 300
E D 200 300
E C 500 300
F B 200 400
F C 300 400
F D 200 400
//实际模型图如下：
//测试结果如下：
//结果显示是人流量大的F点被选做超市
//测试二
//测试距离相对长短对超市选址的影响，即距离相对短的优先选址
//输入数据存放在2.txt中，内容如下：（四个数据分别是起点、终点、距离、人//流量即频度）
A B 300 300
A D 300 300
A E 250 300
B A 300 300
B E 100 300
B F 200 300
B C 300 300
C B 300 300
C D 300 300
C F 150 300
D E 100 300
D F 200 300
D C 300 300
D A 300 300
E A 250 300
E D 100 300
E B 100 300
F B 200 300
F C 150 300
F D 200 300
//实际模型图如下：
//测试结果如下：
//结果显示是距离相对短的E点被选做超市
//测试三
//测试中心点符合实际
//输入数据存放在3.txt中，内容如下：（四个数据分别是起点、终点、距离、人//流量即频度）
A B 141 100
A C 141 100
A E 100 100
B A 141 100
B D 141 100
B E 100 100
C D 141 100
C A 141 100
C E 100 100
D B 141 100
D C 141 100
D E 100 100
E A 100 100
E B 100 100
E C 100 100
E D 100 100
//实际模型图如下：
//测试结果如下：
//结果显示中心点E是最优超市选址点
7．参考文献
列出参考的相关资料和书籍。
[1].李春葆 《C语言程序设计教程》 清华大学出版社
[2].严蔚敏、吴伟民 《数据结构（C语言版）》 清华大学出版社
