<問題>
東京から名古屋向きに東海道本線の主要駅を辿る、以下のような路線図をコンピュータ上に表現したい。
┌─┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │ │→│東 京│→│新横浜│→│熱 海│→│浜 松│→│名古屋│ └─┘ └───┘ └───┘ └───┘ └───┘ └───┘
適当なデータ構造を用いて、コンピュータ上に表現し、東京から名古屋までの駅を出力せよ。
実行例 (駅名を順に入力。アドレス、駅名、次のデータのアドレスを表示)
東京
新横浜
熱海
浜松
名古屋
(ここで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; } }