合法的フライング

プログラミング演習の次の課題に手をつけた。

dijkstra法での最短経路アルゴリズム。


隣接リストにさらにあんなものやこんなものを連結させた。

０から組み上げた完全にオリジナルのグラフデータ構造。


コンパイラによってはmalloc()関数がNULLポインタを返したのに気づかないでNULLポインタに操作を加えると,皿に乗ったギョウザの皮が一斉に開くことがある。

さらにfopen()関数が失敗すると、まれに寄せ鍋が離れていくことがある。


確保していないメモリにアクセスしようとしてセグメンテーションエラーが発生した場合プログラムがクラッシュして、世界中のアジが開きになる可能性があるので注意しなければいけない。

#include <stdio.h>
#include <stdlib.h>
#include <tring.h>

#define F 10000

struct node{
  int code;
  char name[20];
  int rabel;
  unsigned fix:1;
  int *distance;
  int *link;
  int stanum;
  int root;
  int step;
}*data;

int N;

int datascan(void);
void showdata(int start);
void dijkstra(void);

int datascan(void)
{
  int i,j,buf1,buf2,dis,start;
  char buffer[20];
  long loc;
  FILE *fp;

  if((fp=fopen("saitan.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].fix=0;
    data[i].stanum=0;
    data[i].step=F;
  }
  if(fseek(fp,loc,SEEK_SET)){
    printf("シークエラー¥n");
    exit(1);
  }


  for(;;){
    fscanf(fp,"%d %d %d ",&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=(int *)malloc(sizeof(int)*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 %d ",&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：%d km¥n",data[start].name,data[n].name,data[n].rabel);
    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 dijkstra(void)
{
  int i,min=0;

  for(;;min=0){
    while(data[min].fix){
      min++;
      if(min==N)
        return ;
    }

    for(i=min+1;i<N;i++)
      if(!data[i].fix && data[min].rabel>data[i].rabel)
        min=i;
    data[min].fix++;
    for(i=0;i<data[min].stanum;i++){
      if(data[data[min].link[i]].fix && data[data[min].link[i]].step+1>data[min].step)
        data[min].step=data[data[min].link[i]].step+1;
      if(data[data[min].link[i]].fix && data[data[min].link[i]].rabel+data[min].distance[i]==data[min].rabel)
        data[min].root=data[min].link[i];
    }

    for(i=0;i<data[min].stanum;i++)
      if(data[data[min].link[i]].rabel>data[min].rabel+data[min].distance[i])
        data[data[min].link[i]].rabel=data[min].rabel+data[min].distance[i];
  }
}

int main(void)
{
  int i,start;

  start=datascan()-1;

  data[start].rabel=0;
  data[start].step=0;

  dijkstra();

  showdata(start);

  return 0;
}