超市选址问题源代码

(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{
if(sistant(G,v){
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;ifor(j=0;j{
G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;
}
for(i=0;iG.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;ifprintf(fp,"%d表示%s\n",i,G.vexs[i]);
fclose(fp);
//向屏幕输出一张标号与地名对照表
for(i=0;iprintf("%d表示%s\n",i,G.vexs[i]);
}
//该函数中调用另两个子模块：
/*求place数组中的记录在顶点向量中的坐标*/
int LocateVex(MGraph &G,char * place)
{
int i=0,n;
n=strlen(place);//数组长度
while(i{
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{
//求权值
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{
if(G.arcs[v0][v].adj.Adjsn+=G.arcs[v0][v].adj.Adjnum*G.arcs[v0][v].adj.Adjnum;
}
for(v=0;v{
if(G.arcs[v0][v].adj.Adjsm+=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{
printf("相对总权值为%f\n是以编号%d为起点到其余各单位总体最优的解：\n",sistant(G

,v),v);
}
}