数据结构超市选址、最短路径查询、地址信息查询-创新互联
- 设计河北师范大学的校园平面图，至少包括15个以上的地点，每两个地点间可以有不同的路，且路长可能不同。以图中顶点表示校内各地点，存放名称、代号、简介等信息；用边表示路径，存放路径长度等相关信息。
2．提供图中任意地点相关信息的查询。
提供图中任意地点的问路查询，即查询任意两个地点之间的一条最短路径。
学校要新建一间超市，请为超市选址，实现总体最优。注意要考虑各地点距离超市的远近，以及大家去超市的频度不同。
#include#include#define N 16 //图的顶点的数量
typedef struct place{char* name;//名称
int codename;//代号
char* introduction;//简介
double frequncy;//去超市的频率
}place,mall;//创建地点
//place---buildings
typedef struct path{int length;
char pathName[10];
int start;//开始节点的坐标
int finish;
int turn[N];
int index;
}path;
typedef struct Map{// place p[N+1];//顶点的类型
path arcs[N+1][N+1];//distance from one to another
int vernum,arcnum;
}Map;
//给图加入路径长度
void initMap(Map *mapp,int distance,int start,int finish){mapp->arcs[start][finish].length=distance;
mapp->arcs[finish][start].length=distance;
}
void initplace(place *p,int codename,char name[10],char introduction[100],double fre){p->name=name;
p->codename=codename;
p->introduction=introduction;
p->frequncy=fre;
}
void initfrequency(place *p,double e){p->frequncy=e;
}
void printMap(Map p){printf("the Adjacency matrix is as follows");
int i,j;
for(i=0;ifor(j=0;j//遍历以上的二维矩阵
if(p.arcs[i][j].length==-1){printf("#\t");
}else{printf("%d\t",p.arcs[i][j]);
}
}
printf("\n");
}
printf("The adjacency matrix is printed successfully\n");
printf("the num of paths in the map is %d \n",p.arcnum);
printf("the num of places in this map is %d\n",p.vernum);
}
// mappp.arcs[k][j]是最原始的邻接矩阵
void flody(Map mappp,int newmap[N][N])
{int k, i, j;
for (k = 1; k<= N; k++)//在n个结点中依次找中转站；
{for (i = 1; i<= N; i++)
{ for (j = 1; j<= N; j++)
{ newmap[i][j]=mappp.arcs[i][j].length;
if(mappp.arcs[i][k].length<1000&& mappp.arcs[k][j].length<1000){//如果中转点存在
if (mappp.arcs[i][j].length >mappp.arcs[i][k].length + mappp.arcs[k][j].length)//如果直接从i到j的距离大于从i到k再到j的距离，即找到一个合适的中转站，就更新地图；
{mappp.arcs[i][j].length = mappp.arcs[i][k].length + mappp.arcs[k][j].length;
newmap[i][j]=mappp.arcs[i][j].length;
}
}
}
}
}
//对角线元素是0
for (int i=1; i<=N; i++)
{for (int k=1; k<=N; k++)
{if (i==k)
{newmap[i][k]=0;
}
}
}
}
int main()
{//4-------4
double weigh;
double minpp;
int mallp;
int mall,dis,start4;
double w[N+1];
//4-----------4
//1-----------------1
int i,start,finish;
double j;
place placep[N+1];
//1----------------------1
int placenum;
//3-------------------3
int newmap[N][N];
int minp,minum,cnt,f;
int n;
int startp,finishp,turn; int pathp[N];
//1.设计平面图
//1.1创建地点的结点
//各个地点的信息组成的数组
//initplace(placep[1],1,'qizhi1','grilshome');initplace(placep[2],2,'qizhi2','girlshome');initplace(placep[3],3,'qizhi3','girlshome');
for(i=1;i<=N;i++){j=0.0;
initplace(&placep[i],i,"name","introduction",j);
}
Map mapp;
//邻接矩阵的初始化操作
for(start=1;start<=N;start++){for(finish=1;finish<=N;finish++){mapp.arcs[start][finish].length=-1;
}
}
for(i=1;i<=N;i++){for(j=1;j<=N;j++){initMap(&mapp,0x3f3f3f3f,i,j);
}
}
//1.2创建路径
initMap(&mapp,6,1,9);initMap( &mapp,7,9,15);initMap( &mapp,4,1,8);initMap(&mapp,1,7,8);initMap( &mapp,4,7,11);
initMap(&mapp,2,7,12);initMap(&mapp,6,1,6);initMap( &mapp,1,1,2);initMap(&mapp,3,2,3);initMap( &mapp,2,3,5);
initMap(&mapp,4,3,4);initMap( &mapp,2,5,13);initMap(&mapp,6,4,14);initMap(&mapp,4,4,10);initMap(&mapp,1,10,14);
initMap(&mapp,6,9,1);initMap( &mapp,7,15,9);initMap( &mapp,4,8,1);initMap(&mapp,1,8,7);initMap( &mapp,4,11,7);
initMap(&mapp,2,12,7);initMap(&mapp,6,6,1);initMap( &mapp,1,2,1);initMap(&mapp,3,3,2);initMap( &mapp,2,5,3);
initMap(&mapp,4,4,3);initMap( &mapp,2,13,5);initMap(&mapp,6,14,4);initMap(&mapp,4,10,4);initMap(&mapp,1,14,10);
initMap(&mapp,6,1,16);initMap(&mapp,6,16,1);
// 2.1 相关信息的查询操作
printf("现在进入查询,请输入想要查询的地址代号，(输入范围是%d~%d)\n",1,N);
scanf("%d",&placenum);
printf("您查询的地点代号是%d，名称是%s，简介是%s,去超市的频率是%f",placep[placenum].codename,placep[placenum].name,placep[placenum].introduction,placep[placenum].frequncy);
//3.1问路查询
printf("现在进入问路查询界面，请您按照2 4的形式输入起点和终点的地址代号 (输入范围是%d~%d)比如4 14\n",1,N);
//输入1、 2、 3 ~ N之类的代号
flody(mapp,newmap);
//存放最短路径
turn=0;
n=N;
while(n)
{pathp[n--]=0;}
scanf("%d %d",&startp,&finishp);
printf("从地点%d到地点%d的最短路径为%d\n",startp,finishp,newmap[startp][finishp]);
printf("路径如下所示：\n");
minp=100;//寻找最短路，先假设这条路径长度大，经过每一个点后更新长度，最后长度等于最短路
minum;
cnt=2;
f=startp;//f是已经确定的最短路经过的点，在f的邻接点中找到点minum，使得newmap[first][f]+map[f][minum]+newmap[minnum][last]=最短路
while(minp>=newmap[startp][finishp])
{for (i=1;i<=N;i++)
{if ((newmap[startp][f]+mapp.arcs[f][i].length+newmap[i][finishp])<=minp){minum=i;
minp=newmap[startp][f]+mapp.arcs[f][minum].length+newmap[minum][finishp];
}
}
f=minum;
pathp[cnt++]=minum;
if (minum==finishp){break;
}
}
printf("%d ",startp);
pathp[cnt]=finishp;
for(i=1; iif (pathp[i]!=pathp[i-1] && pathp[i]!=0)
{printf("%d ",pathp[i]);
}
}
printf("\n");
// printf("%d\n",mapp.arcs[startp][finishp].index);
// printf("%d\n",mapp.arcs[startp][finishp].turn[mapp.arcs[startp][finishp].index]);
// if(mapp.arcs[startp][finishp].turn[mapp.arcs[startp][finishp].index]!=0)//当有中转点的时候
// {// printf("%d-->",startp);
// for(int i=1; i// printf("%d",mapp.arcs[i][finishp].turn[mapp.arcs[i][finishp].index]);
// if( i<=mapp.arcs[startp][finishp].index ) printf("-->");
//
// }
// printf("%d",finishp);
// }
// else{// printf("%d-->%d",startp,finishp);
// }
// printf("\n");
//之前写的place placep[N+1];//各个地点的信息组成的数组
//4.1超市选址
initfrequency(&placep[6],0.9);
initfrequency(&placep[2],0.1);
for(mall=1;mall<=N;mall++){w[mall]=0;};
for(mall=1;mall<=N;mall++){weigh=0;//mall是新超市的所在建筑的代号
for(start4=1;start4<=N;start4++){dis=newmap[start4][mall];
if(start4==mall) dis=0;
weigh+=dis*placep[start4].frequncy;
// printf("%lf %d %d %lf\n",placep[start].frequncy,mall,dis,weigh);
}
w[mall]=weigh;
// printf("%lf\n",w[mall]);
}
mallp=1;
minpp=w[mallp];
for(int i=1;i<=N;i++){if(minpp>w[i]){minpp=w[i];
mallp=i;
}
}
printf("超市建在代号为%d的位置最好",mallp);
system("pause");
return 0;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文名称：数据结构超市选址、最短路径查询、地址信息查询-创新互联
文章起源：http://scyanting.com/article/dsehoo.html
