2014 Data Structures and Algorithms


  • list13-1.c
#include <stdio.h>
 
#define        MAX_STATION        (10)
 
typedef struct TAG_STATION {
    char name[256];
    struct TAG_STATION *transitions[MAX_STATION]; /* 今回は1駅につき10駅までと制限 */
} STATION;
 
void init_station(STATION* station, char* name) {
    int i;
    for(i = 0; i < MAX_STATION; i++) {
        station->transitions[i] = NULL; /* 最初はどの駅とも繋がっていない */
    }
    strncpy(station->name, name, sizeof(station->name) - 1);
    station->name[sizeof(station->name) - 1] = '\0';
}
 
void add_station(STATION* station, STATION* transition) {
    int i;
    /* transitionsでまだ登録されていない場所を探す */
    for(i = 0; i < MAX_STATION; i++) {
        if(station->transitions[i] == NULL) {
            break;
        }
        /* 既に登録されているので、何もせずに終了する */
        if(station->transitions[i] == transition) {
            return;
        }
    }
    /* 10駅全て登録されていたら何もしない */
    if(i == MAX_STATION) {
        return;
    }
    /* 新しい乗り換え駅を登録する */
    station->transitions[i] = transition;
}
 
void print_station(STATION* station) {
    int i;
    printf("%s:", station->name);
    for(i = 0; i < MAX_STATION; i++) {
        if(station->transitions[i] == NULL) {
            break;
        }
        printf("→%s ", station->transitions[i]->name);
    }
    printf("\n");
}
 
int main(void) {
    int i;
    STATION station[6];
    init_station(&station[0], "鎌倉");
    init_station(&station[1], "藤沢");
    init_station(&station[2], "横浜");
    init_station(&station[3], "横須賀");
    init_station(&station[4], "茅ヶ崎");
    init_station(&station[5], "東京");
 
    /* 鎌倉 */
    add_station(&station[0], &station[3]);
    add_station(&station[0], &station[1]);
    add_station(&station[0], &station[2]);
    /* 藤沢 */
    add_station(&station[1], &station[0]);
    add_station(&station[1], &station[4]);
    add_station(&station[1], &station[2]);
    /* 横浜 */
    add_station(&station[2], &station[1]);
    add_station(&station[2], &station[0]);
    add_station(&station[2], &station[5]);
    /* 横須賀・茅ヶ崎・東京 */
    add_station(&station[3], &station[0]);
    add_station(&station[4], &station[1]);
    add_station(&station[5], &station[2]);
 
    /* グラフ構造を表示 */
    for(i = 0; i < 6; i++) {
        print_station(&station[i]);
    }
    return 0;
}



  • list13-2.c
#include <stdio.h>
 
#define        MAX_STATION        (10)
 
typedef struct TAG_STATION {
    char name[256];
    struct TAG_STATION *transitions[MAX_STATION]; /* 今回は1駅につき10駅までと制限 */
} STATION;
 
void init_station(STATION* station, char* name) {
    int i;
    for(i = 0; i < MAX_STATION; i++) {
        station->transitions[i] = NULL; /* 最初はどの駅とも繋がっていない */
    }
    strncpy(station->name, name, sizeof(station->name) - 1);
    station->name[sizeof(station->name) - 1] = '\0';
}
 
void add_station(STATION* station, STATION* transition) {
    int i;
    /* transitionsでまだ登録されていない場所を探す */
    for(i = 0; i < MAX_STATION; i++) {
        if(station->transitions[i] == NULL) {
            break;
        }
        /* 既に登録されているので、何もせずに終了する */
        if(station->transitions[i] == transition) {
            return;
        }
    }
    /* 10駅全て登録されていたら何もしない */
    if(i == MAX_STATION) {
        return;
    }
    /* 新しい乗り換え駅を登録する */
    station->transitions[i] = transition;
}
 
void print_station(STATION* station) {
    int i;
    printf("%s:", station->name);
    for(i = 0; i < MAX_STATION; i++) {
        if(station->transitions[i] == NULL) {
            break;
        }
        printf("→%s ", station->transitions[i]->name);
    }
    printf("\n");
}
 
int main(void) {
    int i;
    STATION station[6];
    init_station(&station[0], "鎌倉");
    init_station(&station[1], "藤沢");
    init_station(&station[2], "横浜");
    init_station(&station[3], "横須賀");
    init_station(&station[4], "茅ヶ崎");
    init_station(&station[5], "東京");
 
    /* 鎌倉 */
    add_station(&station[0], &station[3]);
    add_station(&station[0], &station[1]);
    /* 藤沢 */
    add_station(&station[1], &station[4]);
    add_station(&station[1], &station[2]);
    /* 横浜 */
    add_station(&station[2], &station[0]);
    add_station(&station[2], &station[5]);
    /* 横須賀・茅ヶ崎・東京 */
    add_station(&station[3], &station[0]);
    add_station(&station[4], &station[1]);
    add_station(&station[5], &station[2]);
 
    /* グラフ構造を表示 */
    for(i = 0; i < 6; i++) {
        print_station(&station[i]);
    }
    return 0;
}



コードを次のように変更してみよう。
  1. 辺の本数を出力してみよう。
#include <stdio.h>
 
#define        STATION_NUMBER        (6)
 
char* stations[] = {"鎌倉", "藤沢", "横浜", "横須賀", "茅ヶ崎", "東京"};
 
int adjacency_matrix[STATION_NUMBER][STATION_NUMBER] = {
  {0, 1, 1, 1, 0, 0},
  {1, 0, 1, 0, 1, 0},
  {1, 1, 0, 0, 0, 1},
  {1, 0, 0, 0, 0, 0},
  {0, 1, 0, 0, 0, 0},
  {0, 0, 1, 0, 0, 0}
};
 
int main(void) {
  int i, j;
  for(i = 0; i < STATION_NUMBER; i++) {
    for(j = 0; j < STATION_NUMBER; j++) {
      if(adjacency_matrix[i][j] == 1) {
        printf("%s -> %s\n", stations[i], stations[j]);
      }
    }
  }
  return 0;
}



コードを次のように変更してみよう。
  1. 辺の本数を出力してみよう。
#include <stdio.h>
 
#define        STATION_NUMBER        (6)
 
char* stations[] = {"鎌倉", "藤沢", "横浜", "横須賀", "茅ヶ崎", "東京"};
 
int adjacency_matrix[STATION_NUMBER][STATION_NUMBER] = {
  {0, 1, 0, 1, 0, 0},
  {0, 0, 1, 0, 1, 0},
  {1, 0, 0, 0, 0, 1},
  {1, 0, 0, 0, 0, 0},
  {0, 1, 0, 0, 0, 0},
  {0, 0, 1, 0, 0, 0}
};
 
int main(void) {
  int i, j;
  for(i = 0; i < STATION_NUMBER; i++) {
    for(j = 0; j < STATION_NUMBER; j++) {
      if(adjacency_matrix[i][j] == 1) {
        printf("%s -> %s\n", stations[i], stations[j]);
      }
    }
  }
  return 0;
}



#include <stdio.h>
 
#define        STATION_NUMBER        (6)
 
char* stations[] = {"横浜", "武蔵小杉", "品川", "渋谷", "新橋", "溜池山王"};
 
int adjacency_matrix[STATION_NUMBER][STATION_NUMBER] = {
  { 0, 12, 28,  0,  0,  0},
  {12,  0, 10, 13,  0,  0},
  {28, 10,  0, 11,  7,  0},
  { 0, 13, 11,  0,  0,  9},
  { 0,  0,  7,  0,  0,  4},
  { 0,  0,  0,  9,  4,  0}
};
 
int main(void) {
  int i, j;
  for(i = 0; i < STATION_NUMBER; i++) {
    for(j = 0; j < STATION_NUMBER; j++) {
      if(adjacency_matrix[i][j] > 0) {
        printf("%s -> %s(%d分)\n", stations[i], stations[j], adjacency_matrix[i][j]);
      }
    }
  }
  return 0;
}



コードを次のように書き換えてみよう。
  1. 最短ルートも分かるように書き変えてみよう。
  2. スタート地点の駅から他のすべての駅までの最短距離の平均を求めるように書き変えてみよう。
  3. 長崎電気軌道の下の図の範囲の路線で、どの駅をスタート地点とする場合に、他の電停までの最短距離の平均が最も短くなるか?
    • ふたつある公会堂前は、ひとつの同じ電停とみなす。ふたつある西浜町についても、同様にひとつとみなす。

chinden.png

#include <stdio.h>
 
#define        STATION_NUMBER        (6)
#define        START_STATION        (0)
 
char* stations[] = {"横浜", "武蔵小杉", "品川", "渋谷", "新橋", "溜池山王"};
 
int current_cost[STATION_NUMBER];
int fix[STATION_NUMBER];
 
int adjacency_matrix[STATION_NUMBER][STATION_NUMBER] = {
    { 0, 12, 28,  0,  0,  0},
    {12,  0, 10, 13,  0,  0},
    {28, 10,  0, 11,  7,  0},
    { 0, 13, 11,  0,  0,  9},
    { 0,  0,  7,  0,  0,  4},
    { 0,  0,  0,  9,  4,  0}
};
 
int main(void) {
    int i, min_station, min_time, new_time;
 
    /* 初期化する */
    for(i = 0; i < STATION_NUMBER; i++) {
        current_cost[i] = -1; /* 無限大 */
        fix[i] = 0;
    }
    current_cost[START_STATION] = 0; /* スタート地点(横浜)の所要時間を0とする */
 
    for(;;) {
        min_time = -1;
        for(i = 0; i < STATION_NUMBER; i++) {
            if(fix[i] == 0 && current_cost[i] != -1) {
                if(min_time == -1 || min_time > current_cost[i]) {
                    /* 確定しておらず、もっとも所要時間の小さい駅を調べる */
                    min_time = current_cost[i];
                    min_station = i;
                }
            }
        }
        if(min_time == -1) {
            /* すべての駅が確定したか、最小の所要時間が無限大だったので終了 */
            break;
        }
        /* 自分の駅から伸びているすべての駅の所要時間を調べる */
        for(i = 0; i < STATION_NUMBER; i++) {
            if(fix[i] == 0 && adjacency_matrix[min_station][i] > 0) {
                new_time = min_time + adjacency_matrix[min_station][i]; /* 自分の駅経由で移動する場合の必要時間 */
                if(current_cost[i] == -1 || current_cost[i] > new_time) {
                    /* 今登録されている時間よりも、この駅経由で移動した時間が速いので、新しい時間を登録する */
                    current_cost[i] = new_time;
                }
            }
        }
        /* 自分の駅を確定する */
        fix[min_station] = 1;
    }
 
    for(i = 0; i < STATION_NUMBER; i++) {
        printf("%s→%s:%d分\n", stations[START_STATION], stations[i], current_cost[i]);
    }
    return 0;
}