|
本人是某大学计算机的菜鸡，在数据结构上机课作业完成过程中，曾上网找了很多类似代码寻找思路，但是网上的代码太繁琐，而且都不是很好理解，因此在自己完成以后就写了这么一个博客，提供一种比较简单的程序代码，希望对那些还在数据结构中头痛的同学一点帮助。 问题描述：设计以校园导游程序，为来访的客人提供各种信息查询服务。
设计要求：
（1）设计自己所在学校的校园平面图（所含景点不少于十个），顶点信息包括名称、简介等，边的信息包括路径长度等。
（2）为来访的客人提供景点信息查询服务。
（3）为来访的客人提供从当前顶点出发前往景点的路线查询服务，包括最短路径及有可能的简单路径。 附图：
其实整个题目很简单，主要就是求最短路径的算法问题，在这里由于这个题需要输出所有路径，因此直接选取暴力枚举的方法，把所有的路径都给枚举出来，最后将最小的路径保存起来，最后单独进行输出就好：
if(b==w) { //如果找到终点则进行输出，否则继续查找
for(p=0;pa[p]);
}
printf("%d ",G->a[k]);
printf("路线总长：%dkm\n",sum);
if(summinrude){ //若当前路径总长小于最小值，则对最短路径进行更新
G->r=k;
G->minrude=sum;
for(p=0;pmin[p]=G->a[p];
}
}
return ;
}
else{
for(j=1;jarc[b][j]vexs[j].park==0){
k++;
G->a[k]=j;
sum+=G->arc[b][j];
G->vexs[j].park=1;
RudeGraph(G,j,w,k,sum); //通过递归对所有路径进行深度搜索
k--; //递归返回这一层后对顶点信息进行重新初始化
G->vexs[j].park=0;
sum-=G->arc[b][j];
}
}
}
值得注意的是，这段暴力枚举的代码使用了邻接矩阵的思想，从邻接矩阵的第一行第一个点对后面点的不断递归查找，返回上一层时候对顶点信息初始化为递归前的状态还是比较细节的。
完整代码如下：
#include
#include
#define M 5000 //假设两顶点之间没有路径,用5000来表示
typedef struct vexsinfo //存放顶点信息的结构体
{
int park; //访问的标志,park=0是未被访问过
int num; //景点的编号
char name[32]; //景点的名称
char introduction[256]; //景点的介绍
}vexsinfo;
typedef struct MGraph
{
int r; //记录最短路径访问过的景点数目
int minrude; //记录最短路径的长度
int min[50]; //记录最短路径经过的顶点信息
int a[50]; //记录路线的数组
vexsinfo vexs[50]; //存放顶点编号的数组，用vexsinfo结构体的变量vexsinfo定义，可以用
//该数组存放顶点信息
int arc[50][50]; //存放两点之间权值的邻接矩阵
int v,e; //定点数和边数
} MGraph;
MGraph* CreateGraph()
{
MGraph *G;
int i,j,k;
G=(MGraph*)malloc(sizeof(MGraph));
//初始化访问标志
for(i=0;ivexs[i].park=0;
}
//初始化顶点数目和路线数目
G->v=10;
G->e=13;
//给景点数组编号
for(i=1;iv;i++)
G->vexs[i].num=i;
for(j=1;jarc[1][2]=G->arc[2][1]=1;
G->arc[1][3]=G->arc[3][1]=3;
G->arc[1][10]=G->arc[10][1]=8;
G->arc[2][6]=G->arc[6][2]=2;
G->arc[4][3]=G->arc[3][4]=1;
G->arc[4][5]=G->arc[5][4]=1;
G->arc[9][5]=G->arc[5][9]=2;
G->arc[6][7]=G->arc[7][6]=1;
G->arc[7][8]=G->arc[8][7]=2;
G->arc[10][7]=G->arc[7][10]=3;
G->arc[8][9]=G->arc[9][8]=2;
G->arc[8][10]=G->arc[10][8]=2;
G->arc[9][10]=G->arc[10][9]=3;
//初始化顶点信息
strcpy(G->vexs[1].name ,"校 门");
strcpy(G->vexs[2].name ,"综合楼");
strcpy(G->vexs[3].name ,"科技馆");
strcpy(G->vexs[4].name ,"月牙湖");
strcpy(G->vexs[5].name ,"咖啡屋");
strcpy(G->vexs[6].name ,"篮球场");
strcpy(G->vexs[7].name ,"体育馆");
strcpy(G->vexs[8].name ,"图书馆");
strcpy(G->vexs[9].name ,"学生活动中心");
strcpy(G->vexs[10].name ,"三炷香");
strcpy(G->vexs[1].introduction ,"曾经是亚洲第一大校门，现因临沂大学重建以后成为亚洲队二大校门");
strcpy(G->vexs[2].introduction ,"老师和领导们办公的地方");
strcpy(G->vexs[3].introduction ,"里面有学校的校史馆，记录着杭电发展的历史");
strcpy(G->vexs[4].introduction ,"学校里面唯一的湖，旁边有一片草地，是情侣们经常出没的地方，里面有许多鸭子游来游去");
strcpy(G->vexs[5].introduction ,"咖啡屋是学生在运营的，里面每天都会有学生和老师在学习和娱乐");
strcpy(G->vexs[6].introduction ,"篮球热爱者的天堂，篮球比赛都在这里举办");
strcpy(G->vexs[7].introduction ,"很多明星来开演唱会时会在体育馆内进行，其次篮球比赛决赛、开学典礼等也会在体育馆举行");
strcpy(G->vexs[8].introduction ,"图书馆高12层，是杭电教学区内最高的建筑物，是热爱学习的同学们的圣地");
strcpy(G->vexs[9].introduction ,"社团活动和很多晚会举办的地方");
strcpy(G->vexs[10].introduction ,"位于学校教学区的正中央，是杭电的标志性建筑物之一");
return G;
}
void RudeGraph(MGraph *G,int b,int w,int k,int sum){
int p,j,n;
if(b==w) {
for(p=0;pa[p]);
}
printf("%d ",G->a[k]);
printf("路线总长：%dkm\n",sum);
if(summinrude){
G->r=k;
G->minrude=sum;
for(p=0;pmin[p]=G->a[p];
}
}
return ;
}
else{
for(j=1;jarc[b][j]vexs[j].park==0){
k++;
G->a[k]=j;
sum+=G->arc[b][j];
G->vexs[j].park=1;
RudeGraph(G,j,w,k,sum); //通过递归对所有路径进行深度搜索
k--; //递归返回这一层后对顶点信息进行重新初始化
G->vexs[j].park=0;
sum-=G->arc[b][j];
}
}
}
return ;
}
int main(void)
{
int c,i,p,k;
MGraph *T;
T=CreateGraph();
while(1){
printf("**********************************\n");
printf("欢迎来到******大学景点信息服务系统\n");
printf("1.景点信息查询\n");
printf("2.路线查询服务\n");
printf("3.退出\n");
printf("**********************************\n");
printf("请选择你要查询的功能：\n");
scanf("%d",&c);
if(c==1){
printf("**********************************\n");
printf("******大学共有如下十处景点：\n");
for(i=1;ivexs[i].num);
printf("%s: ",T->vexs[i].name);
printf("%s\n",T->vexs[i].introduction);
}
}
else if(c==2){
printf("**********************************\n");
printf("请输入当前景点编号和你想要去的景点编号：\n");
printf("（注：景点编号可在功能1内查询）\n");
int b,w;
//初始化访问标志
for(i=0;ivexs[i].park=0;
}
scanf("%d %d",&b,&w);
while(b10||w10){
printf("输入错误，请重新输入:\n");
scanf("%d %d",&b,&w);
}
if(b==w){
printf("您已经在此景点,请重新输入：\n");
scanf("%d %d",&b,&w);
}
else{
T->a[0]=b;
T->vexs[b].park=1;
printf("从景点%d到景点%d共有如下路径：\n",b,w);
RudeGraph(T,b,w,0,0);
printf("最短路径为：\n");
for(p=0;pr;p++){
printf("%d->",T->min[p]);
}
printf("%d ",T->min[T->r]);
printf("路线总长：%dkm\n",T->minrude);
T->minrude=100; //重新初始化最短路径长度
}
}
else if(c==3) break;
else printf("输入错误，请重新输入：\n");
}
printf("祝您生活愉快，再见^v^");
return 0;
}
下面提供Dijkstra算法的伪代码：
和深度搜索相比，Dijkstra的代码只是在算法和最后输出时有所不同，在顶点信息中多加了一个变量存储当前顶点的直接前驱节点，其它地方代码段上的注释应该足够明确，当然算法的思想还是需要看代码前提前掌握的。
typedef struct vexsinfo //顶点信息
{
int park; //访问的标志
int num; //景点的编号
int prenum; //记录当前顶点的前一个顶点编号
int quanzhi; //顶点的权值
char name[32]; //景点的名称
char introduction[256]; //景点的介绍
}vexsinfo;
typedef struct MGraph
{
vexsinfo vexs[50];//顶点表
int arc[50][50];//边表
int v,e;//定点数和边数
} MGraph;
void RudeGraph(MGraph *G,int b,int k){ //迪杰斯特拉求最短路径
int i,j,min,minu;
min=1000;
for(j=1;jarc[b][j]vexs[b].quanzhi+G->arc[b][j]vexs[j].quanzhi&&G->vexs[j].park==0){
G->vexs[j].prenum=b; //更新当前顶点的直接前驱节点
G->vexs[j].quanzhi=G->vexs[b].quanzhi+G->arc[b][j]; //对顶点的权值进行更新
}
}
G->vexs[b].park=1;
for(i=1;ivexs[i].quanzhivexs[i].park==0){
min=G->vexs[i].quanzhi;
minu=i;
}
}
k++;
if(kvexs[b].prenum=-1; //没有前驱结点将其设为-1
T->vexs[b].park=0;
T->vexs[b].quanzhi=0;
RudeGraph(T,b,1);
printf("从景点%d到景点%d最短路径为：\n",b,w);
b=w;
j=0;
while(T->vexs[b].prenum!=-1){ //从终点向前查找前驱节点并保存在数组里
a[j]=T->vexs[b].prenum;
b=T->vexs[b].prenum;
j++;
}
printf("最短路径为：\n");
for(i=j-1;i>=0;i--){ //对数组逆向输出，从而找到最短路径
printf("%d->",a[i]);
}
printf("%d\n",w);
printf("路径长度为：\n");
printf("%d\n",T->vexs[w].quanzhi);
————————————————————————————————————————————————————
放一个修改后的迪杰斯特拉的完整代码：
要用的话修改一下CreateGraph()中的G->v和G->e，把对应邻接矩阵改一改就可以了
#include
#include
#include
#define M 5000 //假设两顶点之间没有路径,用5000来表示
typedef struct vexsinfo //顶点信息
{
int park; //访问的标志
int num; //景点的编号
int prenum; //记录当前顶点的前一个顶点编号
int quanzhi; //顶点的权值
char name[32]; //景点的名称
char introduction[256]; //景点的介绍
}vexsinfo;
typedef struct MGraph
{
vexsinfo vexs[50];//顶点表
int arc[50][50];//边表
int v,e;//定点数和边数
} MGraph;
MGraph* CreateGraph()
{
MGraph *G;
int i,j,k;
G=(MGraph*)malloc(sizeof(MGraph));
//初始化访问标志
for(i=0;iv;i++){
G->vexs[i].park=0;
}
//初始化顶点数目
G->v=10;
//初始化边的数目
G->e=13;
//给景点数组编号
for(i=1;iv;i++)
G->vexs[i].num=i;
for(j=1;jv;j++)
for(k=1;kv;k++)
{
G->arc[j][k]=M;
}
//初始化矩阵,赋予每条边权值
G->arc[1][2]=G->arc[2][1]=1;
G->arc[1][3]=G->arc[3][1]=3;
G->arc[1][10]=G->arc[10][1]=8;
G->arc[2][6]=G->arc[6][2]=2;
G->arc[4][3]=G->arc[3][4]=1;
G->arc[4][5]=G->arc[5][4]=1;
G->arc[9][5]=G->arc[5][9]=2;
G->arc[6][7]=G->arc[7][6]=1;
G->arc[7][8]=G->arc[8][7]=2;
G->arc[10][7]=G->arc[7][10]=3;
G->arc[8][9]=G->arc[9][8]=2;
G->arc[8][10]=G->arc[10][8]=2;
G->arc[9][10]=G->arc[10][9]=3;
//初始化顶点信息
strcpy(G->vexs[1].name ,"校 门");
strcpy(G->vexs[2].name ,"综合楼");
strcpy(G->vexs[3].name ,"科技馆");
strcpy(G->vexs[4].name ,"月牙湖");
strcpy(G->vexs[5].name ,"咖啡屋");
strcpy(G->vexs[6].name ,"篮球场");
strcpy(G->vexs[7].name ,"体育馆");
strcpy(G->vexs[8].name ,"图书馆");
strcpy(G->vexs[9].name ,"学生活动中心");
strcpy(G->vexs[10].name ,"三炷香");
strcpy(G->vexs[1].introduction ,"曾经是亚洲第一大校门，现因临沂大学重建以后成为亚洲队二大校门");
strcpy(G->vexs[2].introduction ,"老师和领导们办公的地方");
strcpy(G->vexs[3].introduction ,"里面有学校的校史馆，记录着学校发展的历史");
strcpy(G->vexs[4].introduction ,"学校里面唯一的湖，旁边有一片草地，是情侣们经常出没的地方，里面有许多鸭子游来游去");
strcpy(G->vexs[5].introduction ,"咖啡屋是学生在运营的，里面每天都会有学生和老师在学习和娱乐");
strcpy(G->vexs[6].introduction ,"篮球热爱者的天堂，篮球比赛都在这里举办");
strcpy(G->vexs[7].introduction ,"很多明星来开演唱会时会在体育馆内进行，其次篮球比赛决赛、开学典礼等也会在体育馆举行");
strcpy(G->vexs[8].introduction ,"图书馆高12层，是教学区内最高的建筑物，是热爱学习的同学们的圣地");
strcpy(G->vexs[9].introduction ,"社团活动和很多晚会举办的地方");
strcpy(G->vexs[10].introduction ,"位于学校教学区的正中央，是学校的标志性建筑物之一");
return G;
}
void RudeGraph(MGraph *G,int b,int k){ //迪杰斯特拉求最短路径
int i,j,min,minu;
min=1000;
for(j=1;jv;j++){
if(G->arc[b][j]vexs[b].quanzhi+G->arc[b][j]vexs[j].quanzhi&&G->vexs[j].park==0){
G->vexs[j].prenum=b; //更新当前顶点的直接前驱节点
G->vexs[j].quanzhi=G->vexs[b].quanzhi+G->arc[b][j]; //对顶点的权值进行更新
}
}
G->vexs[b].park=1;
for(i=1;iv;i++){ //找到目前权值最小的点的编号存储minu
if(G->vexs[i].quanzhivexs[i].park==0){
min=G->vexs[i].quanzhi;
minu=i;
}
}
k++;
if(kv)
RudeGraph(G,minu,k); //对当前权值最小的点进行递归
else //有个记录前驱编号的还没用到，先求出最短路径再实现输出
return ;
}
int main(void)
{
int c,i,p,b,w,j;
int a[50];
MGraph *T;
T=CreateGraph();
while(1){
printf("**********************************\n");
printf("欢迎来到中山大学景点信息服务系统\n");
printf("1.景点信息查询\n");
printf("2.路线查询服务\n");
printf("3.退出\n");
printf("**********************************\n");
printf("请选择你要查询的功能：\n");
scanf("%d",&c);
if(c==1){
printf("**********************************\n");
printf("中山大学共有如下十处景点：\n");
for(i=1;iv;i++){
printf("%d.",T->vexs[i].num);
printf("%s: ",T->vexs[i].name);
printf("%s\n",T->vexs[i].introduction);
}
}
else if(c==2){
printf("**********************************\n");
printf("请输入当前景点编号和你想要去的景点编号：\n");
printf("（注：景点编号可在功能1内查询）\n");
int b,w;
//初始化访问标志
for(i=0;iv;i++){
T->vexs[i].park=0;
}
//初始化顶点权值
for(i=0;ivexs[i].quanzhi=5000;
}
scanf("%d %d",&b,&w);
while(bT->v||wT->v){
printf("输入错误，请重新输入起点和终点:\n");
scanf("%d %d",&b,&w);
}
if(b==w){
printf("您已经在此景点,请重新输入：\n");
scanf("%d %d",&b,&w);
}
else{
T->vexs[b].prenum=-1;
T->vexs[b].park=0;
T->vexs[b].quanzhi=0;
RudeGraph(T,b,1);
printf("从点%d到点%d最短路径为：\n",b,w);
b=w;
j=0;
while(T->vexs[b].prenum!=-1){
a[j]=T->vexs[b].prenum;
b=T->vexs[b].prenum;
j++;
}
printf("最短路径为：\n");
for(i=j-1;i>=0;i--){
printf("%d->",a[i]);
}
printf("%d\n",w);
printf("路径长度为：\n");
printf("%d\n",T->vexs[w].quanzhi);
}
}
else if(c==3) break;
else printf("输入错误，请重新输入：\n");
}
printf("祝您生活愉快，再见^v^");
return 0;
}
———————————————————————————————————————————————————
很多人加我讨论这段程序，总结几个问题吧：
不同编译器之间会有差距，有些人会显示缺少头文件，有些人的最短路径输出不了或者乱码......我是用codeblocks写的，如果大家遇到什么问题建议尝试一下codeblocks进行编译，
再次敲黑板，，，，，，很多人运行的时候可能会少什么头文件或者其他一些bug，建议你们下一个codeblocks试一下，因为我就是用那个IDE写的，不同IDE之间确实会有很大差异，，
如果还解决不了欢迎大家评论里一起交流。
-----------------------------------------------------------------------------------
|