C语言高手！！帮忙写个最短路径程序！！！！-
#include
#define M 5 /*行数*/
#define N 5 /*列数*/
#define MaxSize 100 /*栈最多元素个数*/
int mg[M+1][N+1]={ /*一个迷宫,其四周要加上均为1的外框*/
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};
struct
{
int i;int j;int di;
} Stack[MaxSize],Path[MaxSize]; /*定义栈和存放最短路径的数组*/
int top=-1; /*栈指针*/
int count=1; /*路径数计数*/
int minlen=MaxSize; /*最短路径长度*/
void mgpath() /*路径为:(1,1)->(M-2,N-2)*/
{
int i,j,di,find,k;
top++; /*进栈*/
Stack[top].i=1;
Stack[top].j=1;
Stack[top].di=-1;mg[1][1]=-1; /*初始结点进栈*/
while (top>-1) /*栈不空时循环*/
{
i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
if (i==M-1 && j==N-1) /*找到了出口,输出路径*/
{
printf("%4d: ",count++);
for (k=0;k<=top;k++)
{
printf("(%d,%d) ",Stack[k].i,Stack[k].j);
if ((k+1)%5==0) printf("
"); /*输出时每5个结点换一行*/
}
printf("
");
if (top+1<minlen) /*比较找最短路径*/
{
for (k=0;k<=top;k++)
Path[k]=Stack[k];
minlen=top+1;
}
mg[Stack[top].i][Stack[top].j]=0; /*让该位置变为其他路径可走结点*/
top--;
i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
}
find=0;
while (di<4 && find==0) /*找下一个可走结点*/
{ di++;
switch(di)
{
case 0:i=Stack[top].i-1;j=Stack[top].j;break;
case 1:i=Stack[top].i;j=Stack[top].j+1;break;
case 2:i=Stack[top].i+1;j=Stack[top].j;break;
case 3:i=Stack[top].i,j=Stack[top].j-1;break;
}
if (mg[i][j]==0) find=1;
}
if (find==1) /*找到了下一个可走结点*/
{ Stack[top].di=di; /*修改原栈顶元素的di值*/
top++;Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;/*下一个可走结点进栈*/
mg[i][j]=-1; /*避免重复走到该结点*/
}
else /*没有路径可走,则退栈*/
{
mg[Stack[top].i][Stack[top].j]=0; /*让该位置变为其他路径可走结点*/
top--;
}
}
printf("最短路径如下:
");
printf("长度: %d
",minlen);
printf("路径: ");
for (k=0;k<minlen;k++)
{
printf("(%d,%d) ",Path[k].i,Path[k].j);
if ((k+1)%5==0) printf("
"); /*输出时每5个结点换一行*/
}
printf("
");
}
void main()
{
printf("迷宫所有路径如下:
");
mgpath();
}
# include"stdio.h"
# include"conio.h"
#include
struct student
{
int num;
char name[10];
int score[5];
float average;
int rank;
}stud[31];
struct xuefen
{
int num;
char subject[20];
int xuefen;
}xf[5];
struct fenshuduan
{
char fanwei[10];
int kemu[5];
}fsd[5]=
{
{">=90",0,0,0,0,0},
{">=80",0,0,0,0,0},
{">=70",0,0,0,0,0},
{">=60",0,0,0,0,0},
{"<60",0,0,0,0,0}
};
float average1[5];
/*主菜单*/
int main()
{
char ch1;
do
{
system("cls");
//clrscr();
printf("
");
printf(" ************** C 语 程序设计上机实习 ****************
");
printf(" ---------------------------------------------------
");
printf(" 1 学生成绩管理
");
printf(" 2 解方程组
");
printf(" 3 破译密码
");
printf(" 4 退 出
");
printf(" 输入选择序号
");
while( (ch1=getchar(), ch1!='1'&& ch1!='2' &&ch1!='3'&&ch1!='4' ));
switch(ch1)
{
case '1' :
section1();
break;
case '2' :
section2();
break;
case '3' :
section3();
break;
case '4' :
exit(0);
}
}while(1);
return 0;
}
/*第1个2级菜单*/
section1()
{
char ch21;
do
{
system("cls");
//clrscr();
printf("
");
printf(" ************学 生 成 绩 管 理 系 统****************
");
printf(" ---------------------------------------------------
");
printf(" 1. 读入原始数据并显示 2. 计算平均分及名次
");
printf(" 3. 计算分数段人数 4. 输出课程平均分
");
printf(" 5. 统计不及格情况 6. 输出优秀学生
");
printf(" 7. 作分布图 8. 返回上级菜单
");
printf(" 输入选择序号
");
while((ch21=getchar(),ch21!='1'&&ch21!='2'&&ch21!='3'&&ch21!='4'&&ch21!='5'&&ch21!='6'&&ch21!='7'&&ch21!='8')) ;
switch(ch21)
{
case '1' :
function1_1();
break;
case '2' :
function1_2();
break;
case '3' :
function1_3();
break;
case '4' :
function1_4();
break;
case '5' :
function1_5();
break;
case '6' :
function1_6();
break;
//case '7':
//function1_7();
//break;
case '8' :
return(0);
}
}while(1);
}
//////////////////////////////////////////////////////////
/*第2个2级菜单*/
//////////////////////////////////////////////////////////
section2()
{
char ch22;
do
{
system("cls");
//clrscr();
printf("
");
printf(" ***************** 解线性方程组****************
");
printf(" -------------------------------------------------
");
printf(" 1. 解方程组
");
printf(" 2. 返回上级菜单
");
printf(" 输入选择序号
");
while( (ch22=getchar(), ch22!='1'&& ch22!='2'));
switch(ch22)
{
case '1' :
function2_1();
break;
case '2' :
return(0);
}
}while(1);
}
//////////////////////////////////////////////////////////
/*第3个2级菜单*/
//////////////////////////////////////////////////////////
section3()
{
char ch23;
do
{
system("cls");
//clrscr();
printf("
");
printf(" ***************** 作动画****************
");
printf(" -------------------------------------------------
");
printf(" 1. 破译密码
");
printf(" 2. 返回上级菜单
");
printf(" 输入选择序号
");
while( (ch23=getchar(), ch23!='1'&& ch23!='2') ) ;
switch(ch23)
{
case '1' :
function3_1();
break;
case '2' :
return(0);
}
}while(1);
}
function1_1()
{
char nn[300], mn[300];
FILE *fp, *fp1,*fp2 ,*fp3;
int i,j;
printf("加入读入原始数据并显示的程序内容
");
if((fp=fopen("D:\\1.txt","r"))==NULL)
{
printf ("cannot open 1.txt
");
exit(0);
}
if((fp1=fopen("D:\\2.txt","r"))==NULL)
{
printf ("cannot open 2.txt
");
exit(0);
}
if((fp2=fopen("D:\\c1.txt","w"))==NULL)
{
printf ("cannot open c1.txt
");
exit(0);
}
if((fp3=fopen("D:\\c2.txt","w"))==NULL)
{
printf ("cannot open c2.txt
");
exit(0);
}
fgets(nn,300,fp);
fgets(mn,300,fp1);
for(i=0;i<31;i++)
{
fscanf(fp,"%d %s",&stud[i].num,stud[i].name);
for(j=0;j<5;j++)
fscanf(fp,"%d",&stud[i].score[j]);
}
for(j=0;j<5;j++)
fscanf(fp1,"%d %s %d",&xf[j].num,&xf[j].subject,&xf[j].xuefen);
printf("序号 姓名 理论力学 线性代数 大学物理 机械制图 C语言设计
");
fprintf(fp2,"序号 姓名 理论力学 线性代数 大学物理 机械制图 C语言设计
");
for(i=0;i<31;i++)
{
fprintf(fp2,"%-2d %-8s",stud[i].num,stud[i].name);
printf("%-2d %-8s",stud[i].num,stud[i].name);
for(j=0;j<5;j++)
{
fprintf(fp2,"%-8d",stud[i].score[j]);
printf("%-8d",stud[i].score[j]);
}
printf("
");
fprintf (fp2,"
");
}
printf("
");
printf("编号 课程名称 课程学分
");
fprintf(fp3,"编号 课程名称 课程学分
");
for(j=0;j<5;j++)
{
printf("%-6d%-8s %-2d",xf[j].num,xf[j].subject,xf[j].xuefen);
fprintf(fp3,"%-6d%-8s %-2d",xf[j].num,xf[j].subject,xf[j].xuefen);
printf("
");
fprintf(fp3,"
");
}
fclose (fp);
fclose (fp1);
fclose (fp2);
fclose (fp3);
getch();
printf(" *********按Enter键继续**********
");
getchar();
getchar();
}
function1_2()
{
int i,j; char nn[300], mn[300];
float sum1,sum2,t;
FILE *fp,*fp1,*fp2;
printf("加入计算平均分及名次的程序内容
");
if ((fp=fopen("D:\\1.txt","r"))==NULL)
{
printf ("cannot open 1.txt
");
exit(0);
}
if ((fp1=fopen("D:\\2.txt","r"))==NULL)
{
printf ("cannot open 2.txt
");
exit(0);
}
if((fp2=fopen("D:\\mcb.txt","w+"))==NULL)
{
printf("cannot open mingcibiao.txt
");
exit(0);
}
fgets(nn,300,fp);
fgets(mn,300,fp1);
for(i=0;i<31;i++)
{
fscanf(fp,"%d %s",&stud[i].num,stud[i].name);
for(j=0;j<5;j++)
fscanf(fp,"%d",&stud[i].score[j]);
}
for(j=0;j<5;j++)
fscanf(fp1,"%d %s %d",&xf[j].num,&xf[j].subject,&xf[j].xuefen);
for(i=0;i<31;i++)
{
sum1=0,sum2=0 ;
for(j=0;j<5;j++)
{
sum1+=stud[i].score[j]*xf[j].xuefen;
sum2+=xf[j].xuefen;
}
stud[i].average=sum1/sum2;
stud[i].average=(int)(stud[i].average*10+0.5)/10.0;
}
for(i=0;i<31;i++)
{
stud[i].rank=1;
for(j=0;j<31;j++)
{
if(stud[i].average<stud[j].average)
stud[i].rank++;
}
}
fprintf(fp2," 序号 姓名 理论力学 线性代数 大学物理 机械制图 C语言设计 平均分 名次
");
printf( " 序号 姓名 理论力学 线性代数 大学物理 机械制图 C语言设计 平均分 名次
");
for(i=0;i<31;i++)
{
fprintf(fp2,"%-2d %-8s",stud[i].num,stud[i].name);
printf("%-2d %-8s",stud[i].num,stud[i].name);
for(j=0;j<5;j++)
{
fprintf(fp2,"%-8d",stud[i].score[j]);
printf("%-8d",stud[i].score[j]);
}
fprintf(fp2,"%-5.1f %-2d
",stud[i].average,stud[i].rank);
printf("%-5.1f %-2d
",stud[i].average,stud[i].rank);
}
fclose(fp);
fclose(fp1);
fclose(fp2);
getch();
printf(" *********按Enter键继续**********
");
getchar();
getchar();
}
function1_3()
{
char nn[300];
FILE *fp,*fp1 ;
int i,j;
printf("加入计算分数段人数程序内容
");
if ((fp=fopen("D:\\1.txt","r"))==NULL)
{
printf ("cannot open 1.txt
");
exit(0);
}
if((fp1=fopen("D:\\fdb.txt","w+"))==NULL)
{
printf("cannot open fdb.txt
");
exit(0);
}
fgets(nn,300,fp);
for(i=0;i<31;i++)
{
fscanf(fp,"%d %s",&stud[i].num,stud[i].name);
for(j=0;j<5;j++)
fscanf(fp,"%d",&stud[i].score[j]);
}
for(i=0;i<31;i++)
for(j=0;j<5;j++)
if(stud[i].score[j]>=90)
fsd[0].kemu[j]++;
else if(stud[i].score[j]>=80)
fsd[1].kemu[j]++;
else if(stud[i].score[j]>=70)
fsd[2].kemu[j]++;
else if(stud[i].score[j]>=60)
fsd[3].kemu[j]++;
else fsd[4].kemu[j]++;
fprintf(fp1,"范围 理论力学 线性代数 大学物理 机械制图 C语言设计
");
printf("范围 理论力学 线性代数 大学物理 机械制图 C语言设计
");
for(i=0;i<5;i++)
{
fprintf(fp1,"%4s",fsd[i].fanwei);
printf("%4s",fsd[i].fanwei);
for(j=0;j<5;j++)
{
fprintf(fp1,"%8d",fsd[i].kemu[j]);
printf("%8d",fsd[i].kemu[j]);
}
fprintf(fp1,"
");
printf("
");
}
fclose (fp);
fclose (fp1);
getch();
printf(" *********按Enter键继续**********
");
getchar();
getchar();
}
function1_4()
{
char nn[300];
FILE *fp,*fp1 ;
int i,j,sum;
printf("加入输出课程平均分程序内容
");
if ((fp=fopen("D:\\1.txt","r"))==NULL)
{
printf ("cannot open 1.txt
");
exit(0);
}
if((fp1=fopen("D:\\kcpjf.txt","w+"))==NULL)
{
printf("cannot open kcpjf.txt
");
exit(0);
}
fgets(nn,300,fp);
for(i=0;i<31;i++)
{
fscanf(fp,"%d %s",&stud[i].num,stud[i].name);
for(j=0;j<5;j++)
fscanf(fp,"%d",&stud[i].score[j]);
}
fprintf(fp1,"课程 理论力学 线性代数 大学物理 机械制图 C语言设计
平均分");
printf("课程 理论力学 线性代数 大学物理 机械制图 C语言设计
平均分");
for(j=0;j<5;j++)
{
sum=0;
for(i=0;i<31;i++)
{
sum+=stud[i].score[j];
average1[j]=sum/31.0;
average1[j]=(int)(average1[j]*10+0.5)/10.0;
}
fprintf(fp1,"%10.1f",average1[j]);
printf("%10.1f",average1[j]);
}
fprintf(fp1,"
");
printf("
");
fclose (fp);
fclose (fp1);
getch();
printf(" *********按Enter键继续**********
");
getchar();
getchar();
}
function1_5()
{
char nn[300], mn[300];
FILE *fp, *fp1,*fp2;
int i,j;
printf("加入统计不及格情况程序内容
");
if ((fp=fopen("D:\\1.txt","r"))==NULL)
{
printf ("cannot open 1.txt
");
exit(0);
}
if ((fp1=fopen("D:\\2.txt","r"))==NULL)
{
printf ("cannot open 2.txt
");
exit(0);
}
if ((fp2=fopen("D:\\bujige.txt","w"))==NULL)
{
printf ("cannot open bujige.txt
");
exit(0);
}
fgets(nn,300,fp);
fgets(mn,300,fp1);
for(i=0;i<31;i++)
{
fscanf(fp,"%d %s",&stud[i].num,stud[i].name);
for(j=0;j<5;j++)
fscanf(fp,"%d",&stud[i].score[j]); }
for(j=0;j<5;j++)
fscanf(fp1,"%d %s %d",&xf[j].num,&xf[j].subject,&xf[j].xuefen);
printf("序号 姓名 不及格课程名称 课程学分 成绩
");
fprintf(fp2,"序号 姓名 不及格课程名称 课程学分 成绩
");
for(i=0;i<31;i++)
{
for(j=0;j<5;j++)
if(stud[i].score[j]<60)
{
fprintf(fp2,"%d %s %s %d %d
",stud[i].num,stud[i].name,xf[j].subject,xf[j].xuefen,stud[i].score[j]);
printf("%d %s %s %d %d
",stud[i].num,stud[i].name,xf[j].subject,xf[j].xuefen,stud[i].score[j]);
}
}
fclose (fp);
fclose (fp1);
fclose (fp2);
getch();
printf(" *********按Enter键继续**********
");
getchar();
getchar();
}
function1_6()
{
int i,j,m,n;
char nn[300], mn[300];
float sum1,sum2,t;
FILE *fp,*fp1,*fp2;
printf("加入输出优秀学生程序内容
");
if ((fp=fopen("D:\\1.txt","r"))==NULL)
{
printf ("cannot open 1.txt
");
exit(0);
}
if ((fp1=fopen("D:\\2.txt","r"))==NULL)
{
printf ("cannot open 2.txt
");
exit(0);
}
if((fp2=fopen("D:\\youxiu.txt","w+"))==NULL)
{
printf("cannot open youxiu.txt
");
exit(0);
}
fgets(nn,300,fp);
fgets(mn,300,fp1);
for(i=0;i<31;i++)
{
fscanf(fp,"%d %s",&stud[i].num,stud[i].name);
for(j=0;j<5;j++)
fscanf(fp,"%d",&stud[i].score[j]);
}
for(j=0;j<5;j++)
fscanf(fp1,"%d %s %d",&xf[j].num,&xf[j].subject,&xf[j].xuefen);
for(i=0;i<31;i++)
{
sum1=0,sum2=0 ;
for(j=0;j<5;j++)
{
sum1+=stud[i].score[j]*xf[j].xuefen;
sum2+=xf[j].xuefen;
}
stud[i].average=sum1/sum2;
stud[i].average=(int)(stud[i].average*10+0.5)/10.0;
}
for(i=0;i<31;i++)
{
stud[i].rank=1;
for(j=0;j<31;j++)
{
if(stud[i].average<stud[j].average)
stud[i].rank++;
}
}
printf("序号 姓名 理论力学 线性代数 大学物理 机械制图 C语言设计 平均分 名次
");
fprintf(fp2,"序号 姓名 理论力学 线性代数 大学物理 机械制图 C语言设计 平均分 名次
");
for(i=0;i<31;i++)
{
m=0 ;
n=0;
for(j=0;j<5;j++)
{
if(stud[i].score[j]==100) m++;
if(stud[i].score[j]>=90) n++;
}
if(stud[i].average>=90||stud[i].rank=85&&(m>=1||n>=2)))
{
fprintf(fp2,"%d %s",stud[i].num,stud[i].name);
printf("%d %s",stud[i].num,stud[i].name);
for(j=0;j<5;j++)
{
fprintf(fp2," %d",stud[i].score[j]);
printf(" %d",stud[i].score[j]);
}
fprintf(fp2," %10.1f %d
",stud[i].average,stud[i].rank);
printf(" %10.1f %d
",stud[i].average,stud[i].rank);
}
}
fclose(fp);
fclose(fp1);
fclose(fp2);
getch();
printf(" *********按Enter键继续**********
");
getchar();
getchar();
}
function2_1()
{
double a[4][5]={{5,7,6,5,23},{7,10,8,7,32},{6,8,10,9,33},{5,7,9,10,31}};
int i,j;
system("cls");
//clrscr();
printf("输入的四阶线性方程组为：
");
printf(" %f A + %f B + %f C + %f D = %f
",a[0][0],a[0][1],a[0][2],a[0][3],a[0][4]);
printf(" %f A + %f B + %f C + %f D = %f
",a[1][0],a[1][1],a[1][2],a[1][3],a[1][4]);
printf(" %f A + %f B + %f C + %f D = %f
",a[2][0],a[2][1],a[2][2],a[2][3],a[2][4]);
printf(" %f A + %f B + %f C + %f D = %f
",a[3][0],a[3][1],a[3][2],a[3][3],a[3][4]);
////////////////////////////////////////////////////////
for(i=1;i<5;i++)
a[0][i]=a[0][i]/a[0][0];
a[0][0]=1;
for(i=1;i<5;i++)
a[1][i]=a[1][i]-a[0][i]*a[1][0];
a[1][0]=0;
for(i=1;i<5;i++)
a[2][i]=a[2][i]-a[0][i]*a[2][0];
a[2][0]=0;
for(i=1;i<5;i++)
a[3][i]=a[3][i]-a[0][i]*a[3][0];
a[3][0]=0;
/////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
for(i=2;i<5;i++)
a[1][i]=a[1][i]/a[1][1];
a[1][1]=1;
for(i=2;i<5;i++)
a[0][i]=a[0][i]-a[1][i]*a[0][1];
a[0][1]=0;
for(i=2;i<5;i++)
a[2][i]=a[2][i]-a[1][i]*a[2][1];
a[2][1]=0;
for(i=2;i<5;i++)
a[3][i]=a[3][i]-a[1][i]*a[3][1];
a[3][1]=0;
///////////////////////////////////////////////////////
/////////////////////////////////////////////////////
for(i=3;i<5;i++)
a[2][i]=a[2][i]/a[2][2];
a[2][2]=1;
for(i=3;i<5;i++)
a[0][i]=a[0][i]-a[2][i]*a[0][2];
a[0][2]=0;
for(i=3;i<5;i++)
a[1][i]=a[1][i]-a[2][i]*a[1][2];
a[1][2]=0;
for(i=3;i<5;i++)
a[3][i]=a[3][i]-a[2][i]*a[3][2];
a[3][2]=0;
///////////////////////////////////////////////
/////////////////////////////////////////////
for(i=4;i<5;i++)
a[3][i]=a[3][i]/a[3][3];
a[3][3]=1;
for(i=4;i<5;i++)
a[0][i]=a[0][i]-a[3][i]*a[0][3];
a[0][3]=0;
for(i=4;i<5;i++)
a[1][i]=a[1][i]-a[3][i]*a[1][3];
a[1][3]=0;
for(i=4;i<5;i++)
a[2][i]=a[2][i]-a[3][i]*a[2][3];
a[2][3]=0;
///////////////////////////////////////////////
printf("线性方程组的解为：
");
printf(" A=%10f
",a[0][4]);
printf(" B=%10f
",a[1][4]);
printf(" C=%10f
",a[2][4]);
printf(" D=%10f
",a[3][4]);
//////////////////////////////////////////////
printf("*********************************按Enter键继续********************************
");
getchar();
getchar();
}
function3_1()
{
FILE *fp,*fp1;
char str[100],str1[100]; int i,j,k,m1,n1,a,b,c,t;
if((fp=fopen("D:\\3.txt","r"))==NULL)
{
printf("can't open the30
");
exit(1);
}
if((fp1=fopen("D:\\c3.txt","w"))==NULL)
{
printf("can't open thec30
");
exit(1);
}
fgets(str,100,fp);
for(m1=101;m1<201;m1=m1+2)
{
k=sqrt(m1);
for(i=2;i<=k;i++)
if(m1%i==0) break;
if(i>k)
{
a=m1/100;b=(m1-a*100)/10;c=m1-a*100-b*10;n1=3;
for(j=0;j<100;j++)
if((str[j]>='A'&&str[j]='a'&&str[j]<='z'))
{
if(n1%3==0)
t=a ;
else if(n1%3==1)
t=b ;
else t=c ;
if((str[j]>='A'&&str[j]='A'&&(str[j]-t)='a'&&str[j]='a'&&(str[j]-t)<='z'))
{
str1[j]=str[j]-t;
n1++;
}
if((str[j]>='A'&&str[j]'Z')||(str[j]>='a'&&str[j]'z'))
{
str1[j]=str[j]-t+26;
n1++;
}
}
else
str1[j]=str[j];
printf("%d ",m1) ;
fprintf(fp1,"%d ",m1) ;
printf(" %s",str1) ;
fprintf(fp1," %s",str1) ;
}
printf("
");
}
getch();
printf(" *********按Enter键继续**********
");
getchar();
getchar();
}
说明：
1、编译环境：WindowsXP下的C-Free，C-Free类似于VC++6.0。
2、将1.txt,2.txt,3.txt这三个文本文件拷贝到D盘目录下，并在D盘目录下创建文本文件：c1.txt,c2,txt,c3.txt,mcb.txt
fdb.txt,kcpjf.txt,bujige.txt,youxiu.txt。
3、编译即可执行。
具体参考：在百度文库中输入“学生成绩管理系统”搜索，选择作者zmywly8866的文档，为全文档。
一、 需求分析
【问题描述】
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
【基本要求】
（1） 设计你所有学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
（2） 为来访客人提供图中任意景点相关信息的查询。
（3） 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
【测试数据】
由读者根据实际情况指定。
二、概要设计
本次实验中运用到的数据类型有：图，顶点，边结点
typedef struct edgenode
{
int adjvex; //临接点序号
int length; //道路长度
char name[20]; //景点名称
char info[100]; //景点详细信息
struct edgenode *next;
}edgenode, *Node ;
typedef struct
{
char data[20]; //存储景点的名称.
char str[100]; //具体的介绍此景点
struct edgenode *link; //指向下一个景点
}vexnode; //景点及其信息.
typedef struct Edge
{
int lengh; //边的权值，表示路径长度.
int ivex, jvex; //边的两端顶点号
struct Edge *next; //指向下一条边
} EdgeType; //边及其信息.
typedef struct
{
int num; //顶点编号
char data[20]; //顶点名称
} vertex;
typedef struct{
vertex vexs[MAX]; //顶点集合
int edges[MAX][MAX]; //邻接矩阵
}adjmax;
基本操作：
void fun();
//操作结果：功能说明并显示所有景点
void creatgraph(vexnode g[],int &n, EdgeType e[],adjmax &adj);
//操作结果：创建校园图
void travgraph(vexnode g[],int n,adjmax adj);
//初始条件：已知邻接表adj和顶点g及其数目n
//操作结果：查找指定景点信息
void Ppath(int path[][MAX],int i,int j,vexnode g[]);
//操作结果：寻找最短路径
void Dispath(int A[][MAX],int path[][MAX],int n,vexnode g[]);
//初始条件：已知顶点g和数目n及其权值
//操作结果：显示最短路径
void Floyd(adjmax adj,int n,vexnode g[]);
//初始条件：已知邻接表adj和顶点g
//操作结果：Floyd算法计算所有两个景点间最短路径
三、详细设计
1、---------main()---------
char choice;
int n = 0; / /景点数目
vexnode g[MAX]; //保存顶点及其信息
EdgeType e[MAXedg]; //保存边及其信息
adjmax adj; //保存边和定点
creatgraph(g,n,e,adj); //建立校园导游图
while(1)
{
do{
system("cls");
fun(); //功能说明
printf("请输入所要进行的操作：");
choice=getch();
printf("\n"); }while(choice!='s'&&choice!='S'&&choice!='v'&&choice!='V'&&choice!='Q'&&choice!='q');
switch(choice)
{
case('s'):
case('S'): Floyd(adj,n,g); //查找最短路径
break;
case('v'):
case('V'):travgraph(g,n,adj); //景点查询
break;
case('q'):
case('Q'):return; //结束程序
}
}
2、------- travgraph()---------
void travgraph(vexnode g[],int n,adjmax adj)
{
int i = 1,flag = 1,num; //num存储要查询的景点的序号
char ch;
edgenode *p;
printf("请输入您要查询的景点序号:\n");
scanf("%d",&num);
while(i <= n) //遍历邻接表
{
p = g[i].link;
if(i == num && flag == 1)
{
printf("此景点的名称是: %s\n",g[i].data);
printf("此景点的介绍是: %s\n",g[i].str);
printf("是否继续? Y/N");
ch=getch();
printf("\n");
if(ch == 'Y' || ch == 'y') //继续
{
flag = 1;
i = 1;
printf("请输入您要查询的景点序号:\n");
scanf("%d",&num);
getchar();
}
else
flag = 0; //不继续
}
else
i++;
}
}3、------- Floyd()---------
//Floyd算法计算所有两个景点间最短路径
void Floyd(adjmax adj,int n,vexnode g[])
{
int A[MAX][MAX],path[MAX][MAX]; //A是路径长度，path是路径。
int i,j,k;
for(i = 1; i <= n; i++) //初始化
for(j = 1; j <= n; j++)
{
A[i][j] = adj.edges[i][j]; //i j之间长度
if(i == j)
{
A[i][j] = 0;
}
path[i][j] = -1; //初始化
}
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
if(A[i][j] > (A[i][k] + A[k][j]))
{
A[i][j] = A[i][k]+A[k][j]; //修改最短路径长度值
path[i][j] = k; //将最短路径的节点号保存
}
}
Dispath(A,path,n,g); //用户输入，查找任意两个景点间的最短路径。
}
一、Dijkstra（效率O(n^2)）【这个不会的话，我有一个flash，可以发给你】
for(int k=1;k<=n-1;k++)
{
int p,min=INF;
for(int i=1;i<=n;i++)//找出非最优值的点的最小值
if(!v[i] && min>d[i])
{
min=dist[i];p=i;
}
if(min==INF)break;//无解或不连通
v[p]=1;
for(int i=1;i<=n;i++)
dist[i]<?=dist[p]+g[p][i];
}
cout<<d[n]<<endl;
二、SPFA（效率O(ke)k表示一个不大于2的常数，e表示边的条数）【目前认为是最快的！！】
head=tail=0;
memset(v,0,sizeof(v));
v[1]=q[++t]=1;//用循环队列来记录要更新的点
while(head!=tail)
{
int k=q[++(head%=n)];
v[k]=1;//用v数组标记是否入队
for(int i=1;i<=n;i++)
if(dist[i]>dist[k]+g[i][k])//dist[i]表示第i点到源点的距离，g[i][j]表示i到j的距离
{
dist[i]=dist[k]+g[i][k];
if(!v[i])//如果没入队，就入队
{
q[++(tail%=n)]=i;
v[i]=0;
}
}
}
三、floyed（效率O(n^3)，不过这个可以求出所有点与点之间的最短路）
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]<?=g[i][k]+g[k][j];
这个题目数据结构书上有答案，不过我忘了 ，留个爪印，我不得不说你几句，你自己书上现成的代码，组织一下变成C语言你都不肯，真懒