カーナビゲーションに必要なデータ構造

　カーナビゲーションでは、現在位置から目的地までの最短経路を探し出す処理を行ないます。
最短経路を探し出すには、経路情報を持つ地図が必要となります。経路情報としては様々な形式
のものが考えられますが、最短経路を決めるには、経路の分岐点、すなわち交差点の情報がなく
てはなりません。今回の実習では、交差点を扱うのに必要となる情報について説明し、それを
どのようにプログラム中で表現するかを説明します。

　最短経路探索のために交差点を扱う際に必要な情報として、以下のものが挙げられます。

交差点情報 ・交差点のID（識別番号） ・交差点名 ・位置座標 (x,y) ・平均待ち時間 ・交差道路数 ・隣接交差点ID

　ここで平均待ち時間は、最短経路を距離だけでなくかかる時間も考慮して求める際に必要となります。
交差道路数は、その交差点から何本道路が出ているかを表します。隣接交差点IDは、その交差点の隣にある
交差点で、交差道路数分だけ必要です。

　上記の交差点情報をプログラム中で表すにはどうすれば良いでしょうか？
まず一番始めに思いつくのは、それぞれの情報を別々の変数として表現する方法です。

交差点情報 ・交差点のID(識別番号) ・交差点名 ・位置座標(x,y) ・平均待ち時間 ・交差道路数 ・隣接交差点ID

必要となる変数 int id; char name[50]; double x, y; double wait; int points; int next[5]; /* 最大交差道路数が５ */

　扱う交差点が1つの時はこれでも良いかもしれません。しかし、多数の交差点を処理する場合には、
上に挙げた変数それぞれを何回も宣言する、あるいは、配列にする必要があります。それに加えて、
もし交差点情報の種類が増えた場合には、それに対応する変数の宣言を書き加えなければなりません。

　構造体を用いると、この問題を解決することができます。以前話した通り、構造体とは複数の変数を
まとめた新しい変数の種類（型）をつくり出すものです。上記の変数をまとめて「交差点情報」を表す型を
定義してしまえば、その型の変数を宣言するだけで交差点情報を楽に扱うことができます。

　　※ここで，「定義」と「宣言」という言葉がでてきましたが，よく混同するのでその意味を覚えてください．
　　　定義（definition）は「型を定義するが変数は作成しない」，宣言（declaration）は「変数を作成する」という意味です．


　テキストでは、交差点情報のための構造体"Crossing"を、次のように定義しています。

交差点情報 ・交差点のID(識別番号) ・位置座標(x,y) ・平均待ち時間 ・交差点名 ・交差道路数 ・隣接交差点ID

構造体"Crossing"　　　　　 typedef struct { int id; Position pos; double wait; char name[50]; int points; int next[5]; } Crossing;

　ここで注意して欲しいのは、位置情報も別の構造体"Position"により(x,y)を一つの"Position"型の変数
としてまとめられている、という点です。

構造体"Position"　　　　 typedef struct { double x, y; } Position;

　定義した構造体"Crossing"は、新しい種類の変数"Crossing型"として使うことができます。

Crossing型の変数crossの宣言とその使用例 Crossing cross; cross.id = 1; /* IDに1を設定 */ cross.pos.x = 10.5; /* (x,y)座標を設定 */ cross.pos.y = -128; scanf("%lf", &(cross.wait)); /* 待ち時間をキーボードから入力 */ scanf("%s", cross.name); /* 名前をキーボードから入力 */

　もちろん配列としても使用できます。

Crossing型の変数crossの配列宣言とその使用例 Crossing cross[100]; /* cross[0] 〜 cross[99]が作成される */　　 /* 0番目の要素cross[0]への値の代入 */ cross[0].id = 1; /* IDに1を設定 */ cross[0].pos.x = 10.5; /* (x,y)座標を設定 */ cross[0].pos.y = -128; scanf("%lf", &(cross[0].wait)); /* 待ち時間をキーボードから入力 */ scanf("%s", cross[0].name); /* 名前をキーボードから入力 */