今日の朝の電気系二号館付近の光景
液化窒素タンクのシューという音とともに水蒸気が凝結してもくもくと…。
きっと、この隣接リストを使ったBellman-Fordアルゴリズムで誰かがヌルポインタに操作を加えたからプログラムがクラッシュしたんだろう。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define F 10000
struct node{
int code;
char name[20];
double rabel;
double *distance;
int *link;
int stanum;
int root;
int step;
}*data;
int N;
int datascan(void);
void showdata(int start);
void Bellman(void);
int datascan(void)
{
int i,j,buf1,buf2,start;
char buffer[20];
long loc;
FILE *fp;
double dis;
if((fp=fopen("kanji.txt","r"))==NULL){
printf("saitan.txt を開く際にエラーが発生しました。¥n");
exit(1);
}
for(i=0,j=1;j>0;i++)
fscanf(fp,"%d %20s",&j,buffer);
N=i-1;
loc=ftell(fp);
if(fseek(fp,0,SEEK_SET)){
printf("シークエラー¥n");
exit(1);
}
data=(struct node *)malloc(sizeof(struct node)*N);
if(!data){
printf("メモリの確保に失敗しました。¥n");
exit(1);
}
for(i=0;i<N;i++){
fscanf(fp,"%d %20s",&data[i].code,&data[i].name);
data[i].code--;
data[i].rabel=F;
data[i].stanum=0;
data[i].step=F;
}
if(fseek(fp,loc,SEEK_SET)){
printf("シークエラー¥n");
exit(1);
}
for(;;){
fscanf(fp,"%d %d %lf ",&buf1,&buf2,&dis);
if(!dis)
break;
data[buf1-1].stanum++;
data[buf2-1].stanum++;
}
for(i=0;i<N;i++){
data[i].link=(int *)malloc(sizeof(int)*data[i].stanum);
data[i].distance=(double *)malloc(sizeof(double)*data[i].stanum);
if(!data[i].link || !data[i].distance){
printf("メモリの確保に失敗しました。¥n");
exit(1);
}
data[i].stanum=0;
}
fscanf(fp,"%d ",&start);
if(fseek(fp,loc,SEEK_SET)){
printf("シークエラー¥n");
exit(1);
}
for(;;){
fscanf(fp,"%d %d %lf ",&buf1,&buf2,&dis);
if(!dis)
break;
data[buf1-1].link[data[buf1-1].stanum]=buf2-1;
data[buf1-1].distance[data[buf1-1].stanum]=dis;
data[buf1-1].stanum++;
data[buf2-1].link[data[buf2-1].stanum]=buf1-1;
data[buf2-1].distance[data[buf2-1].stanum]=dis;
data[buf2-1].stanum++;
}
if(fclose(fp)){
printf("ファイルを閉じる際にエラーが発生しました。¥n");
exit(1);
}
return start;
}
void showdata(int start)
{
char **buffer,name[20];
int i,r,n,j,k;
scanf("%d ",&j);
for(k=0;k<j;k++){
gets(name);
for(i=0;i<N;i++){
if(!strcmp(name,data[i].name)){
n=i;
r=n;
break;
}
}
if(i==N){
printf("一致する駅名がありません。¥n");
exit(1);
}
buffer=(char **)malloc(sizeof(char *)*(data[n].step+1));
if(!buffer){
printf("メモリの確保に失敗しました。¥n");
exit(1);
}
for(i=0;i<data[n].step+1;i++){
buffer[i]=(char *)malloc(20*sizeof(char));
if(!buffer[i]){
printf("メモリの確保に失敗しました。¥n");
exit(1);
}
}
printf("%sから%s：%.1lf km¥n",data[start].name,data[n].name,data[n].rabel/10);
strcpy(buffer[0],data[n].name);
for(i=1;i<data[n].step+1;i++){
strcpy(buffer[i],data[data[r].root].name);
r=data[data[r].root].code;
}
printf("path :");
for(i=data[n].step+1;i;i--)
printf("- %s ",buffer[i-1]);
printf("¥n");
for(i=0;i<data[n].step+1;i++)
free(buffer[i]);
free(buffer);
}
}
void Bellman(void)
{
int i,j,k;
for(i=0;i<N-2;i++)
for(j=0;j<N;j++)
for(k=0;k<data[j].stanum;k++)
if(data[j].rabel+data[j].distance[k]<data[data[j].link[k]].rabel){
data[data[j].link[k]].rabel=data[j].rabel+data[j].distance[k];
data[data[j].link[k]].root=data[j].code;
data[data[j].link[k]].step=data[j].step+1;
}
}
int main(void)
{
int i,start;
start=datascan()-1;
data[start].rabel=0.0;
data[start].step=0;
Bellman();
showdata(start);
return 0;
}
