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语言你都不肯,真懒
请超级无敌语言高手帮忙!!!
冰花纷乱飞满天,洋洋洒洒都是爱。冰心一片在玉壶,是我,洋溢其中都是情,知否。咋样,可否?
求高手帮忙写个C语言代码!!超级紧急!!
int main(){float base=360000;int year=1;float get=50000;while(1){base=base+base*0.04;get=get+get*0.02;if(get>base){printf("\\n%第%d年拿走%.2f, 余额:%.2f 已超过余额!",year+1,get,base);break;}base-=get;printf("\\n%第%d年拿走%.2f, 余额:%.2f",year+1,get,b...
求C 语言高手帮忙写下注释!俄罗斯方块的!大恩不言谢!!
首先,通常我们需要准备7种方块,4个方向的形状表,相当多的俄罗斯方块程序就是在开头写了这样一个很长的数组定义,有的光这个定义就直接超100行了,这个程序是怎么实现的呢?其实这个程序,同样是使用一个7*4*16的数组来保存这个形状表,但是,它没有直接初始化,见这个数组的定义:int sp[8][4] ...
那个高手帮忙写个C语言程序,求|a+b|的绝对值
<math.h> int main(){ int num1 = 0,num2 = 0,i = 0;printf("请输入2个整数,用空格分隔输入!\\n");scanf("%d d",&num1,&num2);i = fabs(num1 + num2);printf("这2个数和的绝对值为:%d",i);printf("\\n");return 0;} ...
C语言高手,帮帮忙
因为程序中的语句是顺序语句所以先执行st=st+i; 则st=75 因为要以字符型显示,所以A的ASCII码是65,那么大写字母的ASCII码规则是逐个增一,所以到75,就是字母K 然后在执行i=st%i,因为初值i=10,经过执行第一句后st=75,所以i=75%10 ,所以是5 (8) !(非) &&(且) ||(或)(9) 1...
C语言高手帮忙编个程序吧 急用!!!我们要做个单片机控制液位的系统...
cout << "stop work!" << endl; \/\/ 自己把这里的方法改成单片机的控制命令就OK了,我就不帮你写了 } else { controlWaterLevel();} } } bool controlWaterLevel() \/\/ PI算法自己有的话,可以把PI算法放进这个函数里面去就可以了 { int setWaterLevel,getWaterLevel;cout << "Set water'...
请C语言高手帮我编写几个小程序~(一定要用C++编写噢~)
第一个 void reverse_merge(List &A,List &B,List &C){ InitList(C);i=j=1; k=0;la_len=ListLength(A);lb_len=ListLength(B);while((i<=la_len)&&(j<=lb_len)){ GetElem(A,i,ai);GetElem(B,i,bi);if(ai<=bj){ ListInsert(C,++k,ai); ++i;} else ListInsert(C,...
求!语言高手!
英语 vagueness Reject ambiguity 阿拉伯语 ترفض الغموض غموض朝鲜语 애매모호 불량품 애매함德语 Unb...
求位C语言编程高手帮忙编程序?
void main() { SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch; InitStack(&Enter); \/*初始化车站*\/ InitStack(&Temp); \/*初始化让路的临时栈*\/ InitQueue(&Wait); \/*初始化通道*\/ while(1) { printf("\\n1.
写C语言程序 高手请进...跪求!!!
我感觉定义一个结构体还是比较好,把所有的属性都归为一个学生里面。下面是我写的程序,图片是运行的结果。include <stdio.h> struct ln { int sno; \/\/学号 float mascore;\/\/数学分 float enscore;\/\/英语分 float phscore;\/\/物理分 float sum; \/\/总分 float avg; \/\/平均分 }stude...
巫绍复方: 这是我们的一个实验,你可以参考一下 一、 需求分析 【问题描述】 设计一个校园导游程序,为来访的客人提供各种信息查询服务.【基本要求】 (1) 设计你所有学校的校园平面图,所含景点不少于10个.以图中顶点表示校内各景点,存放景点...
通城县17723423938: C语言高手帮忙写个最短路径程序!!!!!! - ?
巫绍复方: 可以用Dijkstra算法实现你的题目: http://www.360doc.com/content/10/1128/12/4823898_73098292.shtml 这里有一个和你的几乎一样的不过你这个程序在输入点和点的距离的时候比较麻烦了,因为是一个比较大的邻接矩阵.. void dijkstra(...
通城县17723423938: 怎么用c语言实现单源最短路径问题?要求是用Dijkstra算法,最好写出所有的代码 ,包括结构定义等等,对一 - ?
巫绍复方: C语言代码://清华大学出版社光盘的代码 void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D) { // 算法7.15// 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]// 及其带权长度D[v].// 若P[v][w]为TRUE,则w...
通城县17723423938: c语言数据结构 最短路径问题代码 - ?
巫绍复方: 直接看代码:#include <stdlib.h> #define MAXVEX 10 typedef struct graph{int n,e;//顶点数、边数char vexs[MAXVEX];//顶点数组int arcs[MAXVEX][MAXVEX];//邻接矩阵int kind;//类型:0有向图;1无向图;2有向网;3无向网 } MGraph...
通城县17723423938: 最小距离法的C语言程序 - ?
巫绍复方: 就你上面的问题我写了下 以下是代码通过编译了 输入2个城市比如输入2,3 输入的是城市间最短路径 以及路程. 如果城市的个数以及他们之间 的距离如果变了. 程序中给出参数也要修改. 你可以根据自己需要进行修改. #include<stdio.h> void ...
通城县17723423938: 给出坐标的几点之间的最短路径问题 用C语言解 求高手帮忙 - ?
巫绍复方: 最笨的枚举法,先算第一个点距离剩下点的最短路径,然后把第一点排除最外求剩下点最短,循环直到剩下两点. #include <stdio.h> #include <stdlib.h> #define N 10//返回最短距离的平方,两个点下标分别存在index1和index2中 //x为所有点x坐...
通城县17723423938: 迷宫最短路径(c语言编程) - ?
巫绍复方: 做出来了..花了一天时间..唉..下面是代码.. 如果看的麻烦的话..留个邮箱,我直接把程序文件发过去.. #include<stdio.h> #include<stdlib.h> #include<time.h> int** CreateTwoDimensionalArr(int a, int b)//动态创建二位数组.. { ...
通城县17723423938: 如何用C语言实现求迷宫的最短路径? - ?
巫绍复方: #include<stdio.h>#include<stdlib.h>#define M 8#define N 8#define Max 100 int mg[M+2][N+2]= //定义迷宫,0表示能走的块,1表示不能走,在外围加上一圈不能走的块 { {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,...
通城县17723423938: C语言最短路径问题 - ?
巫绍复方: int main() { int G[100][100] = {}; //一个记录图的邻接矩阵int a, b, w; //输入一共有7条边, 5个点int i, j, k; for(i = 1;i <= 5;i++) for(j = 1;j <= 5;j++) G[i][j] = 9999999; for(i = 1;i <= 7;i++) { scanf("%d %d %d", &a, &b, &w);//输入每条边的信息,a和...
通城县17723423938: 【c语言源代码】求最短路径,已确定起点终点和所有需要经过的点!!! - ?
巫绍复方: 你就用上面找到的确定任意两点的算法找最短路径,再重复所有可能的两点,这样记录路径,就可以找到最短路径的两点了