データ構造とアルゴリズムについて〜データ構造編〜

・データ構造とアルゴリズムって言葉、よく聞く。

でも、そうは言っても一体何だろうか？

まずは言葉の意味

「データ構造」・・・そのままの意味。データの構造。データを色々な形にしておくことで、見つけやすくなったりする。身近な例で言えば、本棚に本を入れる時、大きさごとに入れるのか名前順で入れるのか、みたいな話に近い

「アルゴリズム」・・・何か問題を解決するときの手順。身近な例で言うと、料理の作り方みたいな話に近いかも。

たくさんの料理を一度に作る時に、食材を切って茹でる、また切ってから茹でる、という流れを繰り返すよりも全部切ってから一度に全て茹でた方が効率がいいよね。じゃあ、その効率ってどうやって比べるのさ？みたいな話。

なぜこの２つがセットなのか？
・データ構造とアルゴリズムはコンピュータのプログラムの効率に大きく影響する
・データ構造が決まればアルゴリズムは自然と決まることが多い
・アルゴリズムは前提とするデータ構造がある

つまり、アルゴリズムとデータ構造は切っても切れない関係なのである！

データ構造

代表的なものを挙げる

配列

配列とは、ひとことで言ってしまうとデータの並びのことです。
データを連続で格納していくデータ構造です。

要素数を持っていて、何番目！というのを指定して高速にアクセスできます。
しかし、最初に容量を決めてしまうために、後で追加などは難しいです。

データへのアクセスはO(1)で行え、検索にはO(n)かかります。
これは、アクセスはインデックスを用いて一発で行え、検索するには頭からお尻まで順番に参照していけば、最悪の計算量はnかかります。

その出し入れの仕方によって、以下の２つに分類されます。

スタック

スタックというのは、配列のうちで、後入れ先出しのものを指します。
箱で言ったら下が閉じていて上からしか出し入れできません。

キュー

一方でキューというのは、配列のうちさ後入れ後出しのものです。
一方通行のトンネルのようなものですね。

リスト

同じく連続したデータ構造で、「リスト」というものが存在します。

これは、配列のように全体のインデックスをつけるのではなくて、次のデータを場所を前のデータに付けておくことで参照させます。

このおかげで、データの追加が簡単に行なえます。
しかし配列に比べると、その分アクセスするのに時間がかかってしまうというデメリットが出てしまうんですね。

線形リストと双方向リストに分けることができ、線形リストの場合は頭から一方向にしか辿れないのですが、双方向リストにすれば前にたどることもできます。

ハッシュ

さて、次にハッシュについてです。
配列に関してですが、配列は要素に応じてデータにアクセスしました。

例えば、データが何番目！ならばそこにあるデータが取り出されます。
これを、データにアクセスするのに要素でなくて「キー」というものを使ったのがハッシュです。

あるデータがあったときに、それをハッシュ関数というに入れると、出力としてキー値が出てきます。
このキー値によってデータを格納する場所を決めるのです。
よくハッシュ関数として使われるのは剰余とかですね。
13で割った余りの数によってデータを格納する番地を決めたりします。

ところが、ここで問題になるのが、じゃあ、14と27はどうなるのか？という話です。
どちらも13で割った余りが1で、キー値が共通です。
キー値が重なることを衝突と呼びます。

これを解消するために以下の２つの方法があります。

クローズドハッシュ

クローズドハッシュ法は衝突が起きた時に、新しいキー値を求める方法です。
例えば「衝突が起きたら（データ+1）をハッシュ関数に入力した値をキー値にする」のようにすれば、上の例だと、27は(28+1)mod 13 = 2なので別の空いている場所に格納することができますね。

オープンハッシュ

一方で、オープンハッシュ法では、同じ番地にねじ込みます。
とはいえ、同じ場所に２つのデータは格納できないので、先程の「リスト」という構造と組み合わせます。
すでに格納されている13というデータの後ろに、27というデータへの参照をつけるわけです。
これをたどっていけばデータを見つけることができますね。

木

次に木構造についてです。

木構造はリストと少し似ています。
リストとの違いは

• 根があること
• 次のデータへの参照が１つでないこと

があります。
データに親子関係を付けます。

木には大きく「根」と「葉」のデータが存在します。

親子関係にはルール付がされており、例えば「親よりも大きければ右、そうでなければ左」というようにデータを格納していきます。

こうすることでデータの検索が容易になるのです。

まとめ

以上、簡単なデータ構造について書いていきました。

なるべく初心者の方にもわかりやすく解説することを目指しています。
今回はデータ構造でいっぱいになってしまいましたが、またアルゴリズム編も書いていきたいと思いますのでよろしくお願いします。