データ構造と探索アルゴリズム

データ構造と探索アルゴリズムは、データを効率よく格納し、目的のデータを見つけ出す仕組みと手順を扱う分野である。配列やポインタによるリスト、スタック、木構造、ハッシュ法などが代表的な対象であり、操作の回数や探索時間の見積もりが問われる。

配列とポインタによる実現

配列で実現したリストは、要素を連続した領域に格納する。そのため、添字がわかれば任意の要素を一定時間で参照できる。一方で、要素数の上限に合わせた領域をあらかじめ確保すると、実際の要素数が少ない場合に未使用の領域が生じる可能性がある。

ポインタで実現したリストは、各要素が次の要素を指す構造のため、要素の追加や削除を連続領域の移動なしに行える。その反面、目的の位置に到達するには先頭から順にたどる必要がある。単方向リストで末尾のデータを削除する場合、末尾の1つ前のデータを特定するために先頭から次のポインタを追う必要があり、たどる回数はデータ数に比例する。

スタックの出力順序

スタックは後入れ先出しの構造であり、データの挿入と取出しの組合せによって出力順序が変わる。3個のデータが入力順A、B、Cの順に与えられ、各データについて挿入と取出しを1回ずつ行う場合、出力順序は5通りである。

全順列の6通りがすべて得られるわけではない点が判断の鍵となる。入力の順序は固定されており、スタックに挿入する順番を入れ替えることはできないため、入力順を保った操作の範囲でのみ出力順序が決まる。

木構造の走査と再帰

再帰処理で木を走査するとき、どの子を先に処理するか、ノード自身の出力をいつ行うかによって出力順序が変わる。子を右、左の順に処理し、子の処理がすべて終わってからノード自身を出力する走査は、左右を逆にした後行順（後順）の走査である。