第三章　アルゴリズムとデータ構造

３．１　アルゴリズム入門
□アルゴリズム
アルゴリズム（algorithm）は、問題を解くための手順を定めたものである。
そのため、ある処理をどのような手順で実行するのかをはっきりと定義したものでなければならない。
一般的に、１つの問題に対してその問題を解くアルゴリズムは１つではない。
数あるアルゴリズムの中から、その問題に最適なアルゴリズムを選択することが、システムの効率を左右する非常に大きなポイントとなってくる。

□プログラム
アルゴリズムが決まっただけでは、その問題をコンピュータに解かせることはできない。
なぜならば、アルゴリズムは人間には理解できるが、コンピュータには、そのままの形では理解できないからである。
そこで、アルゴリズムをコンピュータが理解できる形に書き換えたものが必要となり、これがプログラムである。
アルゴリズムが問題をどのような手順で解くかという抽象的なものであるのに対し、プログラムはコンピュータをどのように動かして問題を解いていくか、といった具体的なものである。
プログラムは、Ｃ言語やＣＯＢＯＬなどといったプログラム言語を用いて記述される。

□流れ図
アルゴリズムを言葉の羅列で記述したのでは、非常にわかりづらいものになってしまう。
フローチャート（flow chart：流れ図）とは、記号を用いてアルゴリズムを図表化し、より簡潔に表現したものである。
フローチャートを用いると以下のような効果が期待できる。
（１）プログラム全体の構造や、相互間の関係が視覚的に容易に理解できる。
（２）処理の誤りや、条件の不明確な点などが見つけやすい。
（３）自分以外の人にアルゴリズムを説明するときに、他人でも理解しやすく便利である。
（４）プログラムを修正する場合、修正個所の絞り込みが容易で、かつ、その修正をすることによってプログラムのほかの部分にどのような影響があるのかが把握しやすい。

３．２　基本データ構造
□データ構造
データ構造とは、与えられた問題を解決するためのデータの表現方法である。
問題を解決するには、問題の本質を簡潔に表現し、しかも効率よく解く必要がある。
そのためには、それぞれの問題に応じて、最適な表現方法を選択することが重要となってくる。
データ構造には、基本的なものとして、リスト、スタック、待ち行列（キュー）、木構造などがある。

□配列
配列とは、同じ型のデータを一定の個数並べた形の構造で、データ構造の最も基本となるものである。
すべてのデータが同じ型であるために、特定のデータを参照する場合には添字を用いる。
配列の最も簡単な形である１次元配列が図３−１で、たとえば、データ１を参照したいときには添字を１に、データｎを参照したいときには、添字をｎにすればよい。
すなわち、配列名Ａを使っていい換えると、Ａ（１）＝データ１、Ａ（ｎ）＝データｎということになる。

□ポインタ
ポインタとは、日本語でいえば矢印のことである。
ポインタを使って各要素をつなぐことで、各要素間に論理的な順番をもたせる。
たとえば、図３−２のような要素を考える

図３−２の要素Ｂ、Ｃ、Ａの間には順番というものは存在しない。
この要素Ｂ、Ｃ、Ａに、Ａ→Ｂ→Ｃという順番をもたせるには、図３−３のように、各要素間を矢印で順番につなげばよい。
図３−３の各要素間の矢印のことをポインタとよぶ。
ポインタを先頭から矢印のさしている方向に、順番に終わりまでたどっていくことで、要素を論理的な順番で参照することができる。

□リスト
リストは、配列と同様にデータの並びを表現するための基本的な方法である。
リストは、図３−４のようにデータ値を格納するデータ部と、要素間の関係を示すポインタ部から構成されているのが特徴である。

たとえばポインタ部に、次の要素はどれであるかといった情報をもたせれば、このポインタをたどることによって各要素を論理的な順番でアクセスすることができる。
また、要素の挿入や削除は、ポインタをつなぎ換えるだけで行えるので、配列における同様の処理と比較すると、はるかに高速に行うことが可能である。
リストには、ポインタの形式によって線形リスト、双方向リスト、環状リストなどがあるが、ここでは最も基本的な線形リストについて、リストの参照、挿入、削除の方法を説明する。
線形リストとは、図３−５のようにポインタ部に１つのアドレスをもち、一方向につながっているリストのことである。

リストの挿入、削除はポインタをつなぎ換えるだけでよいので配列のそれと比較すると非常に効率がよい。
図３−５のＡ_２の削除方法を図３−６に、また、リストの挿入方法を図３−７に示す。

□スタック
スタックとは、最後に格納されたデータが最初に取り出されていく、というデータ構造であり、このことを後入れ先出し法（ＬＩＦＯ：Last In First Out）という。
スタックは、プログラミングのアルゴリズムとして非常に有効であることはいうまでもないが、ＯＳ（オペレーティングシステム）内の機能においてもしばしば用いられる重要なデータ構造である。
スタック構造では、前述したようにデータの格納のされ方、取り出され方に、一定の決まりがある。
データは常に上部から格納され、上部から取り出されていく。
つまり、先に格納したデータは下部に残り、後から格納したデータのほうが先に取り出されていくのである。
図３−８においてデータ３を取り出す作業は、まずデータ４を取り出してからでないと行えないのである。
スタックからデータを取り出すことをポップアップ（ＰＯＰ）といい、逆にデータを入れることをプッシュダウン（ＰＵＳＨ）という。
現在、スタックのどこまでにデータが入っているのかを管理するために図３−９のようなスタックポインタを用いる。
データを１件ポップアップしたときには、スタックポインタを−１し、逆にデータをプッシュダウンしたときには、スタックポインタを＋１すればよい。

□キュー
キューは待ち行列ともよばれ、先入れ先出し法（ＦＩＦＯ：First In First Out）、すなわち、先に格納したものから先に取り出すというデータ構造である。
キューの例としては、窓口の順番待ちの行列などがあげられる。

スタックでは、一方向のみでデータを取り出し、格納を行ったが、キューではデータの取出し側と格納側を分離する。
キューへデータを格納することをエンキューといい、格納すべきデータをキューのいちばん後ろに追加する。
逆に、キューからデータを取り出すことをデキューといい、キューに格納されているデータのいちばん先頭から取り出す。

□木
木構造は、各要素が２つ以上のポインタをもち、木の枝、木の葉のように枝分かれしているデータ構造である。
木構造は、階層構造を表現するのに適しており、数式の構造、プログラムのモジュール構成の表現方法としても用いられる。
木の基本構成を表したものが図３−１１である。
個々のデータを示す部分を節点（node）、木の中心となるいちばんはじめの節点を根（root）、根から見ていちばん末端の節点を葉（leaf）、節と節のつながりを示す関係を枝（arc）とよぶ。
木は親子関係に対応しており、上位にある節点を親とよび、枝分かれした下位の節点を子とよぶ。
また、木構造の中にある一部分のことを、部分木とよぶ。
なお、木の分岐数によって、２分木、Ｂ木などがある。
◇２分木
２分木は木構造の特殊な形で、各節点が０〜２個の枝をもつ木のことである。（図３−１２）。
この２分木上で、各節点が子の節点の値よりも大きい値を持っているものをヒープという。
◇Ｂ木（Balanced Tree）
多分木上で、各節点のバランスにある制約を定めたものに、Ｂ木がある。
補助記憶装置に大量のデータを蓄え、探索を行うのに適している。

□ハッシュ法
データを格納したり探索したりするのに、上記のリストや２分木は、アクセスに一定の手順をたどる必要がある。
そのため、データの参照順序によっては効率が悪いことがある。
ハッシュ法は、データの値から、格納場所を決める方法で、参照の順序に影響を受けることなくデータを高速にアクセスすることができる。
具体的には、データ（キー値）をある関数で変換し、格納する場所を直接決め、そこにデータを格納する。
この関数のことをハッシュ関数とよぶ。
検索する場合も、検索対象データからハッシュ関数を用いて、格納されている場所を求めて直接アクセスすることができる。
このようにハッシュ法は非常に有効な方法であるのだが、１つ問題がある。
それは、異なるデータであるにもかかわらず、ハッシュ関数で計算した値が同じになってしまうことがある、ということである。
このことを衝突とよぶ。
また、この衝突したデータのことを同義語（シノニム）とよぶ。
衝突に対する対応策としては、衝突したデータどうしをリストを用いてつなぎ、ハッシュ表にこのリストの先頭へのポインタをもたせて管理する連鎖法（チェーン法）と、データを直接ハッシュ表の中に格納してしまい、衝突したデータは、ある計算によって求められた、ハッシュ表の空いている部分に格納する開番地法（オープンアドレス法）がある。
図３−１３は、前者のチェーン法の表現方法である。
例として、従業員情報をチェーン法を用いて管理する場合を考えてみる。
各従業員には６けたの従業員番号が割り当てられており、ハッシュ関数として、引数（従業員番号）を９７で割ったときの余りを返すような関数ｈ（ｘ）を用いると仮定する。
ｈ（ｘ）＝ｘ　mod ９７
（Ａ mod BはＡをＢで割ったときの余りを返す）

上のような従業員番号に対してハッシュ関数ｈ（ｘ）を用いて、各従業員情報を格納する場所を求めてみると、

となる。
従業員番号「１１９２７３」「３３５２５８」の従業員の情報はそれぞれ２５、２６という値によって示される場所に格納されるので、ハッシュ関数ｈ（ｘ）によって、これらの従業員情報を一意に識別することが可能である。
しかし、従業員番号「２２７４９２」「５５０７９３」については、ハッシュ関数ｈ（ｘ）の戻り値がともに２７となってしまい、シノニムが発生する。
このような場合にチェーン法では、図３−１４のように衝突が発生したデータをリストで管理する。
これらの従業員情報を検索する場合には、まずハッシュ関数を用いてリストの先頭を見つけ、そこからリストを順番にたどって目的のデータを探していかなければならない。
このようにシノニムが発生してしまうと、目的のデータにたどり着くまでに複数回の比較が必要となってしまい、ハッシュ法のメリットが軽減してしまう。
できるだけシノニムが発生しないようなハッシュ関数を用意することが、効率を向上させる最大のポイントである。

□抽象データ型（ＡＤＴ：abstract data type）
前述のスタック構造を例にとって抽象データ型を説明する。
スタックとは、データを順番に積み上げていく形で格納し、取り出すときは積み上げられたデータのいちばん上から順番に取り出していくデータ構造であった。
このとき、プログラムはデータをスタックに積み上げたり取り出したりすることだけを考えていればよく、スタックを実現している配列の何番目にデータが格納されているのかは知る必要がない。
すなわち、データの格納（push）、データの取り出し（pop）を呼び出すプログラムは、これらの手続きを呼び出すだけでよく、その中で行っている配列の操作のたいへんさを知る必要がないのである。
このようにデータ構造（たとえばスタック）をプログラム中で定義し、それに対する操作をひとまとめ（たとえばpushやpop）にしておけば、プログラムは余計な心配をする必要がないのである。
このようなデータ構造と、それに対する操作（手続き）のまとまりを抽象データ型（ＡＤＴ）という。
このようなＡＤＴを用いることにより、次のような利点が生まれる。
（１）余計なことを気にする必要がなくなる（たとえば、pushするときの配列の添字の変更などは手続きpushに任せておけばよい）。
（２）定義したデータ構造を直接操作する部分が限定されるため、修正、変更が容易になる。
なお、基本的な抽象データ型には、リスト、スタック、キュー、木などがある。

□ポーランド記法（Poland Natation）
数式では、かっこを用いて計算の優先順位を決めている。
この表現方法は人間には理解しやすい形式だが、コンピュータにとっては必ずしも理解しやすい形式であるとは限らない。
ポーランド記法を用いると、かっこを使わずに数式の計算の優先順位を表すことができ、この記法は多くのコンパイラで利用されている。
（a+b）*cの数式をポーランド記法で表現すると、
*+abc
となる。
ポーランド記法で数式を表現するためには、演算子を２つの被演算子の前に置けばよい。
また、ポーランド記法に対して逆ポーランド記法というものも存在し、上記の例を逆ポーランド記法で表現すると、
ab+c*
となる。
逆ポーランド記法で数式を表現するためには、演算子を２つの被演算子のあとに置けばよい。
また、逆ポーランド記法は日本語の読み方とよく似ており、上記の逆ポーランド記法は「aとbを足してcを掛ける」と読むことができる。
また数式を木を用いて表現すると、ポーランド記法、逆ポーランド記法の表現を簡単に導き出すことができる。
数式を木を用いて表現するためには、
・葉には被演算子を割り当てる
・葉でない節点には演算子を割り当てる
ということにしたがって割り当てを行えばよい。
たとえば、（a-b）*（c+d）の数式を木を用いて表現すると次のようになる。
図中の部分木１は（a-b）を表しており、部分木２は（c+d）を表している。
根は、部分木１の数式と部分木２の数式を乗算することを表している。
この木をある規則にしたがってたどっていくことによって、さまざまな数式の表現が可能になる。
その規則には次のようなものがある。
・行きがけ順（先行順）
その節点を通るのが初めてであれば立ち寄る。
２回目以降は立ち寄らない。
・通りがけ順（中間順）
葉ならば立ち寄る。
葉でない節点ならば、そこを通るのが２回目であれば立ち寄る。
・帰りがけ順（後行順）
その節点を通るのが最後であれば立ち寄る。
これらの木のたどり方と、表現方法の対応は次のようになる。
行きがけ順→ポーランド記法
通りがけ順→元の数式（部分木ごとにかっこをつける必要有）
帰りがけ順→逆ポーランド記法
では、（a+b）*cをポーランド記法、逆ポーランド記法の表現にすると、どのようになるだろうか。
数式を木に割り当て、それを行きがけ順でたどればポーランド記法、帰りがけ順でたどれば逆ポーランド記法になるので、答えは次のようになる。

３．３　基本アルゴリズム
□整列（ソート）
整列（ソート）とは、データの並び換えのことである。
たとえば、数字データを小さいものから（昇順）並べ換えたり、あるいは、文字データをアルファベット順に並べ換えるといったアルゴリズムである。
整列は、探索と同様にコンピュータで行う最も基本的なアルゴリズムで、高速化が重要な課題となる。
整列の代表的なものとしては、セレクションソート（選択法）、バブルソート（交換法）、クイックソート、マージソートなどがある。

□セレクションソート（選択法）
セレクションソートは、最も簡単な整列アルゴリズムであるが、効率はよくない。
セレクションソートは、未整列部分の最大値（あるいは最小値）を探して未整列部分の左側のデータと直接交換する方法である。
まず、配列の中から最大値（あるいは最小値）を求め、配列の１番目の要素と交換する。
次に、配列の１番目の要素は整列済みなので、１番目の要素を除いて、配列の２番目以降の要素の中から最大値（あるいは最小値）を求め、配列の２番目の要素と交換する。
これと同様な処理を、配列の要素数がＮ個であるとすると、Ｎ−１番目の要素まで繰り返すことによって、Ｎ個のデータを降順（あるいは昇順）に整列することができる。
要素が５個の場合のセレクションソートの流れを、図３−１５に示す。

□バブルソート（交換法）
バブルソートは、セレクションソートと同様に基本的な整列アルゴリズムであり、効率はよくない。
バブルソートの基本的な走査方法は、隣接する２つの要素どうしを配列の端から順番に、整列しようとしている大小関係を満たしているかどうかを比較し、大小関係が逆であればそれらの２つの要素を交換していく。
これと同様の操作を、配列の要素数がＮ個であれば、Ｎ−１回繰り返すことによって配列の要素を整列させることができる。
図３−１６のように配列を縦に記述して、配列の要素の値が小さいものが、配列の添字の小さいほうに格納されるように交換（昇順に整列）すると、値の小さいものほど上に（軽い泡のように）浮かび上がってくるところから、バブルソート（泡立ち法）と名づけられた。
具体的な例として、ｎ個の要素を昇順に整列することを考える。
まず、ｎ番目（１番下）の要素から１番目（１番上）の要素まで順番に、隣接する２つの要素の大小関係を比較して、値の小さいものが添字の小さいほうに格納されるように交換していく。
この操作によって、配列の要素の中でいちばん小さい値（１番軽い値）が配列の１番目（１番上）に浮かび上がってくる。
次に、ｎ番目の要素から２番目の要素（１番目は整列済み）について同様の操作を行うと、次に小さい要素が配列の２番目に浮かび上がる。
同様の操作をn−１回繰り返すことによって、整列が完了する。
図３−１６に、配列の要素の数が４個の場合のバブルソートの操作例を示す。
図３−１６のような場合は、n-1回（４−１＝３）の操作で整列が完了した。
しかし、整列の要素の並び方によっては、n-1回の操作を行う必要がない場合がある。
整列が完了したあとで、残りの操作を繰り返すのは無駄なので、ある操作を行って１回も交換が発生しなかったら、整列処理を終了させるようなアルゴリズムのほうがより効率がよい。

□クイックソート
セレクションソート、バブルソートは配列の要素の最終的な位置（整列後の位置）を１つひとつ決めていたが、クイックソートの場合は、要素が最終的に格納される位置の決定はあとで行うことにして、全体を２分割する方法を用いている。
まず、配列の中から適当な値を１つ選択する（この値のことを基準値という）。
次の配列の要素を１つひとつ、この基準値と比較して、基準値以下の要素を配列の左側、基準値以上の値を配列の右側に集める。
この操作のことを分割という。
分割が終わったあとの状態は、図３−１７の分割後aのようになる。
分割操作後、２つの分割にそれぞれ分割操作を再帰的に適用すれば、全体の配列が完了する（分割後b）。

□マージソート
マージソートはクイックソートと並ぶ高速の整列アルゴリズムである。
しかし、このマージソートにも欠点がある。
それは、主記憶装置上で整列操作を行う場合、ほかの整列アルゴリズムよりも、より多くの記憶容量を必要とする点である。
このため、内部ソート（主記憶上での整列処理）のアルゴリズムとしては、あまり実用化はされていない。
しかし、外部ソート（磁気ディスク装置上での整列処理）のアルゴリズムとしては実用化されている。
マージソートの基本的な考え方は、マージを繰り返し行っていく過程で、整列していこうというものである。
図３−１８のような８個のデータを例にとって説明する。
８個のデータを全体としてみれば、５，８，４，７・・・、６，２と、まったく整列されていないが、１個１個のデータを独立してみれば、それらはすでに整列済みであると考えられる。
そこで、これらの整列済みのデータをマージすることによって、次に２個の整列済みのデータを得ることができる。
同様のことを行っていくと、２個の整列済みのデータどうしをマージすることによって、４個の整列済みのデータが得られ、４個の整列済みのデータどうしをマージすることによって８個の整列済みのデータが得られる。
これで、整列が完了するのである。
マージソートでは、データが２ⁿ個あれば、ｎ回マージを繰り返すことによって整列は完了する。
マージソートのアルゴリズムは、次の２つのステップから構成されている。
まず第１ステップは、データを２等分、２等分と分割していき、この作業をこれ以上分割できないというところまで続ける（図３−１９の第１段階）。
次の第２ステップとして、分割されたデータどうしを繰り返しマージしていき、この作業をすべてのデータがマージされるまで続ける。

□文字列探索
文字列探索とは、ある文字列（テキスト）の中に、特定の文字列（パターン）が存在するかどうかを探索するということである。
前述してきた探索というものは、ある配列の要素の中から、特定の１つの要素を探索するものであったのに対し、文字列探索は、特定の１文字を探索するのではなく、特定の文字列（パターン）を探索するという点が大きく異なる。
つまり、文字列探索では文字の並びということが非常に重要なポイントとなってくるのである。
文字列探索の基本的な考え方は、探索したいパターンを、テキストの最初から１文字ずつ後ろにずらしながら比較していくというものである。
パターンと１文字も異ならず、かつ文字の順番もパターンとまったく同じものが見つかって、はじめて探索できたことになる。

３．４　アルゴリズムの計算量
□計算量（手間、計算複雑度）
１つの問題にはいくつものアルゴリズムが考えられる。
アルゴリズムを評価するうえで重要なのは、結果を出すまでに計算時間がどれくらいかかるか、である。
これを、アルゴリズムの計算量（手間、計算複雑度）という。
ここで、よく試験にも出題される、逐次探索法と２分探索法の計算量を比較してみよう。
図３−２０のように、逐次探索法では、端から順番に探索していくため、データがｎ個あれば、ある値を探索するのに、平均して（n+1)/2回、最大でｎ回の比較が必要になる。
これに対して、２分探索法では、図３−２１のように探索対象範囲を２分していくので、ある値の探索に必要な比較回数は、平均で[log₂n]回、最大で[log₂n]＋１回となる（[x]はxを超えない最大の整数）。
この２つのアルゴリズムは、データ数が多くなればなるほど、２分探索法の効率のよさがわかる。

TOPへ　　第四章へ