STEP 3.3 

<問題>

東京から名古屋向きに東海道本線の主要駅を辿る、以下のような路線図をコンピュータ上に表現したい。

┌─┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ │→│東 京│→│新横浜│→│熱 海│→│浜 松│→│名古屋│
└─┘ └───┘ └───┘ └───┘ └───┘ └───┘

適当なデータ構造を用いて、コンピュータ上に表現し、東京から名古屋までの駅を出力せよ。


実行例 (駅名を順に入力。アドレス、駅名、次のデータのアドレスを表示)

東京
新横浜
熱海
浜松
名古屋
(ここでcontrol z)

address = 9336008 station = 東京 next address= 9336020
address = 9336020 station = 新横浜 next address= 9336038
address = 9336038 station = 熱海 next address= 9336050
address = 9336050 station = 浜松 next address= 9336068
address = 9336068 station = 名古屋 next address= 0


新しい駅名を追加するときは、「熱海の後ろに、静岡」のような入力が考えられます。(今回は作っていません)


以下のプログラミング知識が必要。プロになる人は、避けられないので、時間をとってじっくり理解した方がよい。

コメント



解答例

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


// 駅のデータ リストのセル
typedef struct cell {
    char station[10];
    struct cell *next;
} CELL;


CELL *append(CELL *, char *); // 一番最後に、新しい駅名セルを付け足す関数
CELL *cell_alloc (void); // セル1つ分を確保。確保したアドレスを戻り値に
void printlist (CELL *); // 先頭ポインターから出力する関数

int main (void) {
    CELL *pt; // 先頭アドレス head
    char name[10]; // 入力される駅名。日本語で4文字まで。少ないか。

    pt = NULL; // 最初は何もないのでheadはNULL

    while (scanf ("%s", name) != EOF) { // Control Zを読み込むまで
       pt = append(pt, name); // 一番後ろに付け足していく。戻り値は先頭要素のアドレス
    }

    printlist(pt); // 先頭から順にプリントする

    return 0;
}

// 再帰的プログラム
CELL *append(CELL *pt, char *name) {
   CELL *newcell;

   if (pt == NULL) { // もし最後なら、新しいデータを付け足し
       newcell = cell_alloc();
       strcpy(newcell-> station, name);
       newcell -> next = NULL;
       return newcell;
   } else { // まだ最後じゃない。なら、次へ付け足せ
       pt -> next = append(pt -> next, name);
       return pt;
   }
}

// セルを1つ確保して、そのアドレスを戻り値に
CELL *cell_alloc (void) {
   return (CELL *) malloc(sizeof(CELL));
    // CELL構造体のメモリサイズを確保(allocate)し、そのアドレスを
}

// 順番にプリント 再帰を使っていないことに注意。もちろん、再帰でもかける。例題集13.3のprint_arrayとFreeDataに注目
void printlist (CELL *pt) {
   while (pt != NULL) {
      printf("address = %x station = %s  next address= %x \n", pt, pt -> station, pt -> next);
      pt = pt -> next;
   }
}