データ構造

要点と定義

データ構造は、データをどう並べ、関係付け、操作するかを定めた表現方法です。同じ情報でも構造によって、要素の探し方や追加・削除の手順が変わります。

隣接行列は、頂点数と同じ行数・列数を持ち、行列の成分で頂点間の辺の有無を表す方法です。頂点 u と v の間に無向辺があれば、u から v と v から u の両方を記録するため、成分 [u,v] と [v,u] はともに 1 になります。対角成分 [u,u] は自己ループを表す位置なので、自己ループがない場合は 0 です。無向グラフでは行列は対称になります。

二分探索木は、各節について左部分木の値がその節より小さく、右部分木の値が大きくなる二分木です。この規則は各部分木にも適用されます。したがって、根の左側・右側だけでなく、枝をたどるたびに大小関係を確かめます。

スタックは、最後に格納した値を先に取り出す LIFO の構造です。格納をプッシュ、取り出しをポップと呼びます。配列で「次に格納する位置」を stackPos とする表現では、プッシュ後に stackPos を 1 増やします。ポップでは stackPos を 1 減らしてから、その位置の値を取り出します。

単方向リストは、各要素が値と次の要素への参照を持つ構造です。配列で表す場合、値を格納する配列と、次の要素番号を格納する配列を対応させます。先頭から順にたどり、次の要素番号が未定義なら末尾です。配列上の番号順とリストの順番は一致するとは限りません。

適用条件と例

頂点 1 と 3 を結ぶ無向辺を隣接行列に反映するなら、[1,3] と [3,1] を 1 にします。[1,1] は頂点 1 の自己ループを示す位置であり、頂点 1 と 3 の辺の記録には使いません。隣接行列は頂点数の二乗に比例する領域を使いますが、二頂点間に辺があるかは成分を直接調べられます。

二分探索木で、根が 8、左の子が 3、その右の子が 5 なら、3 と 5 はどちらも 8 より小さく、5 は 3 より大きい必要があります。根との比較だけでなく、たどった部分木の規則も満たすかを確認します。値が重複しないという前提なら、左は小、右は大と判断できます。

容量 4 の配列スタックで stackPos が 3 なら、次のプッシュは位置 3 に格納し、成功後は 4 になります。ポップでは 2 に減らしてから位置 2 を取り出します。stackPos が容量を超える状態でプッシュすることや、空のスタックでポップすることを避けるには、操作前に満杯・空の条件を確認します。