path[i][j]=-1;
count[i]=0;
}
for(k=0;k<G->n;k++)
{
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
{
if(G->dis[i][j]>G->dis[i][k]+G->dis[k][j])
{
G->dis[i][j]=G->dis[i][k]+G->dis[k][j];
1.1.2输入数据要求
数据文件格式举例：
第1行存储单位个数n，
之后n行逐一存储每个单位的编号、人数和名称，
之后一行存储边数m，
之后m行逐一存储与每条边相关两个单位的编号、单位间距离
具体数据如下：
6//6个单位
1 300建工学院//单位编号为1、人数300人、单位名称是建工学院
2 350经管学院
3 200生命学院
校园超市选址
学号
姓名
指导教师
2014年4月20号
1.校园超市选址…………………………………………………………………………………1
2.目录……………………………………………………………………………………………2
1.需求分析………………………………………………………………………………………3
1.1功能与数据需求………………………………………………………………………3
{
int adj[MAXVEX][MAXVEX];//单位之间的相通情况（是否有边）；
int dis[MAXVEX][MAXVEX];//单位间距离（边的长度）；
int f[MAXVEX];//各单位去超市的频率；
int n;//顶点数；
int e;//边数
dist vexs[MAXVEX];
}Mgraph;
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;
}
/*cout<<"各点到其他地点最大权值路程和："<<endl;
for(i=0;i<G->n;i++){
if(count[i]==1)
void Floyed(Mgraph *G) //求最短路径floyd算法
{
data *t=new data[school];
read_data(t);
dist *s=new dist[side];
read_dist(s);
int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];
data>>buffer; //读数据
school=c_int(buffer);//学院个数
for(int i=0;i<(school)*3+1;i++){
data>>buffer;
}
side=c_int(buffer);//边的个数
}
data.close();//关闭文件
}
void read_data(data temp[])
for(j=0;j<G->n;j++)
{
G->adj[i][j]=1;
if((i==dist_temp[k].pointx)&&(j==dist_temp[k].point_y))
{
G->dis[i][j]=dist_temp[k].dis;
}
if(G->dis[i][j]==0)
{
G->adj[i][j]=0;
if(i!=j)
{
cout<<" "<<i+1<<"->"<<j+1<<"："<<endl;
if(A[i][j]==INF)
{
if(i!=j)
cout<<"不存在路径"<<"\n"<<endl;
}
else
{
cout<<"距离:"<<G->dis[i][j]<<endl;
cout<<"路径:"<<i+1<<" ";
{
for(j=1;j<G->n;j++){
A[i][0]+=A[i][j];
G->dis[i][0]+=G->dis[i][j];
}
cout<<G->dis[i][0]<<endl;//到各点距离
}
}*/
cout<<"各点到其他点权值和："<<endl;
for(i=0;i<G->n;i++){
cout<<A[i][0]<<endl;//到各点权值
pre=path[i][j];
while(pre!=-1)
{
cout<<pre+1<<" ";
pre=path[pre][j];
}
cout<<j+1<<endl;
point_pre[i*school+j]=path[i][j];
cout<<"权值=距离*频率："<<A[i][j]<<endl;
}
}
}
for(int i=0;i<(school+1)*3-1;i++) //跳过学校单位信息
{
data>>buffer;
}
for(int j=0;j<side;j++) //读取路径相关信息
{
data>>buffer;
temp2[j].pointx=c_int(buffer);
data>>buffer;
A[i][j]=G->dis[i][j]*G->f[(i)%G->n];
path[i][j]=k;
}
}
}
cout<<endl<<"Floyed算法求解:"<<endl;//Floyed算法主要过程显示
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
{
point_pre[i*school+j]=-1;
}
G->adj[j][i]=G->adj[i][j];
G->dis[j][i]=G->dis[i][j];
}
}
for(int kk=0;kk<G->n;kk++) //构建邻接矩阵
{
for(int kkc=0;kkc<G->n;kkc++)
cout<<G->dis[kk][kkc]<<" ";
cout<<endl;
2.1主要数据结构
typedef struct//学院信息结构体
{
int number;
int count;
string name;
}data;
typedef struct //点及距离信息结构体
{
int pointx;
int point_y;
int dis;
}dist;
typedef struct
{ //读取学校单位的相关数据的函数
ifstream data(name);
data>>buffer;
for(int i=0;i<school;i++)
{
data>>buffer; //读数据
temp[i].number=c_int(buffer); //存入number成员
data>>buffer;
{
int i,j,k;
G->n=school;
G->e=side;
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<side;k++)
{
for(i=0;i<G->n;i++)
1.1.1基本要求…………………………………………………………………………3
1.1.2输入数据要求……………………………………………………………………3
1.1.3扩展要求…………………………………………………………………………3
1.2开发与运行环境需求…………………………………………………………………4
}
for(k=0;k<G->n;k++)
{
G->f[k]=data_temp[k].count;
}
for(i=0;i<G->n;i++)//以距离和频率之积作为权值；
for(j=0;j<G->n;j++)
{
if(G->adj[i][j]==0&&i!=j)
G->dis[i][j]=INF;
}
}
3.1.3Floyed算法函数
4.测试……………………………………………………………………………………………15
5.用户手册………………………………………………………………………………………16
6.总结提高………………………………………………………………………………………17
附录1：源程序完整代码
1.需求分析
用c/c++语言编写一个程序实现以下功能：某校园至少包括6个单位，各单位之间距离不同，请为超市选址，确定将超市放在哪个单位，才能使得总体最优。
2.2程序总体结构
3.详细设计
3.1主要函数设计
3.1.1文件的读取与信息转换
void fuction()//读取文档中学院个数与边的个数的函数
{
ifstream data(name);
if(!data){ //找不到文件报错；
cout<<"open error!"<<endl;
exit(1);
}
else{
int i,j,k,pre,number=0;
int weight_sum=0;
int count[MAXVEX];
for(i=0;i<G->n;i++) //初始化A[][]和path[][]数组
for(j=0;j<G->n;j++) //置初值；
{
A[i][j]=INF;
A[i][j]=G->dis[i][j]*G->f[(i)%G->n];
temp2[j].point_y=c_int(buffer);
data>>buffer;
temp2[j].dis=c_int(buffer);
}
data.close();
}
int c_int(char temp[])
{ //将char型转换为整形函数
int length=0;
int i=0;
do{ //计算数组的有效长度
temp[i].count=c_int(buffer); //存入count成员
data>>buffer;
temp[i].name=buffer; //存入name成员
}
data.close();
}
void read_dist(dist temp2[])
{ //读取路径的相关数据的函数
ifstream data(name);
1.1功能与数据需求
1.1.1基本要求
输入：以文件形式存储作为输入，包括单位个数、每个单位编号、每个单位人数、各个单位间距离。
输出（图形方式）：
1、显示校园各个单位分布图（标明单位人数、单位间距离）
2、问题答案（基本版本）：不考虑单位人数，只考虑距离，确定超市最佳选址（用不同颜色的边动态显示选择路径的过程），列表输出所选超市到各单位距离，并输出总和。
}
k=0;
for(i=0;i<G->n;i++){
if(count[i]){
if(G->dis[k][0]>G->dis[i][0]){
k=i;
}
}
}
int nd;
nd=G->dis[0][0];
for(i=0;i<G->n;i++)
{
if(G->dis[i][0]<nd)
{
nd=G->dis[i][0];
length++;
i++;
}while(temp[i]!=0);
int value=0;
for(int j=0;j<length;j++)
{
value+=(temp[j]-'0')*pow(10,length-j-1);
}
return value;
}
3.1.2构建邻接矩阵
void CreatMgraph(Mgraph *G,data data_temp[],dist dist_temp[]) //构建邻接矩阵
2.概要设计………………………………………………………………………………………4
2.1主要数据结构…………………………………………………………………………4
2.2程序总体结构…………………………………………………………………………5
3.详细设计………………………………………………………………………………………5
4 400外语学院
5 320计算机学院
6 500机械学院
11//十一条边
1 2 600//建工与经管间距离600米
1 3 500
1 4 200
2 3 330
2 5 520
2 6 430
3 4 360
3 5 340
3 6 370
4 5 230
46 700
1.1.3扩展要求
1.不考虑人数只考虑距离，分别用相邻矩阵、邻接表存储分别实现基本功能，并在报告中分析各自的优劣，说明你认为最合理的方案及理由；设计测试用例，做测试验证，分析结果产生的原因。
2.设计既考虑距离，又考虑单位人数的解决方案，并说明如此设计的优劣，列表输出所选超市到各单位带全距离，并输出总和；
1.2开发与运行环境需求
开发：Microsoft VC++ 6.0
运行环境：Microsoft VC++ 6.0或更高版本（需具备EasyX图形库），程序须使用多字节字符集。
2.概要设计
k=i;
}
}
final=k;
//cout<<"超市选址（以距离为wenku.baidu.com准）的最佳地址为:"<<t[k].name<<endl;
