はじめに
インターン先でプログラミングを勉強中の文系学生。
「アルゴリズムを勉強したなら、ついででデータ構造も勉強しとき」
そんなついでで勉強できる量ではないと思うんですが…
データ構造とは
まぁ、まずはデータ構造の概要を知ろう。
アルゴリズムを勉強する際に使った一週間で身につくアルゴリズムとデータ構造には、
大量のデータを効率よく管理する仕組み
って書いてあったな。
でも、これ以上の説明はできないよね。
データは種類によって異なるけれど、それらをいかに運用するかが大切なんだよね。
認識としては、これで十分でしょ。
社員さんから教材として、データ構造を教えてもらえたことだし、詳しく見ていくか。
線形のデータ構造
リスト(配列)
まぁ、これは名前からでもわかるな。
データが順番に並べられたデータ構造だよね。
いつもPHPを使っているから、配列と同じような認識で良いのかな。
リストにはデータごとに順序番号(インデックス)が付けられているらしいけど、要するに添え字か。
勉強していくと、リストと配列は実際には違うらしい。
リストは要素の数やデータの形が自由だけれど、配列はそうはいかない。
具体的なイメージはつかめないけれど、覚えておいたほうが良いよね。
スタック
最後に入れたデータが最初に出ていくデータ構造。
テキストエディタとかの元に戻すとかに使われているみたい。
実家の新聞入れをイメージするのが適当かな。
あれは取り出すことはほとんどなかったけど、取り出すとなれば上からだよね。
つまり、後から入れたものから先にでていくということか。
データを挿入(重ねる)する操作はPush,
データを削除する(取り出す)操作はPop,
データの頂上(一番上)はTop,
データの底辺(一番下)はBottom
これは覚えておいたほうが良いね。
キュー
キューは先に入れたものから先に出てくる仕組みらしい。
料金所とかをイメージするのが良さそうだね。
連想配列(辞書、マップ)
連想配列は、キーと値を関連付けてデータを保持するデータ構造。
指定されたキーを入力されたときに、値を早く見つけ出せるようにしているのか。
学生番号とかに使われているのかね?
連結リスト
リストの要素が次のリストに繋がるリンクを持っているデータ構造。
リンクが次につながる1つだけなら単方向リスト,
リンクが前後の双方で持っているなら双方向リスト,
最後のリストが持っているリンクが最初のリストの物なら循環リスト
リストは順番にしかたどっていけないらしいけど、データの変更をする時は入れ替えたり、詰めたりするのが便利らしい。
たしかに後ろのリストや要素をずらす必要がないのは便利か。
リストの種類を詳しく見ていこう。
単方向リスト
それぞれの要素は1つのリンクを持ち、そのリンクは次のリストを示す。
最後のリンクに書かれるnullは終端を表す。
双方向リスト
それぞれの要素が前後の要素を示すリンクを持っているデータ構造。
先端と終端を繋げるリンクがあれば循環リスト。
循環リスト
単方向リストの最後に書かれるはずのnullが先頭のリンクになっているのが、循環リスト。
最後のリストになっても最初の留守とに戻っているため、環状に並んだデータ構造となる。
グラフデータ構造
ツリー
ノードをリンクさせて階層構造を表現したのがツリー。
ノードは0個以上の子ノードを持っており、子ノードを持つノードが親ノードと呼ばれるらしい。
ツリーの頂上にあるノードはルートノード。
子ノードを持たないノードはリーフノードと呼ばれるのか。
ツリーには順序木と無順序木の2種類があって、
順序木は親ノードと子ノードに順序、関連があるツリー。
無順序木は親ノード、子ノードに関連がなく、無造作に構成されたツリー。
バイナリーツリー(二分木)
各ノードが最大で2つの子ノードしか持たないツリー構造。
子ノードは、左の子ノード、右の子ノードとして区別されるようにできている。
1つしか子ノードがなくても、必ず右か左に配置される。
バイナリ―サーチツリー(二分探索木)
各ノードに値やデータを持たせて、探索を簡単にするバイナリーツリーのこと。
ノードの挿入に法則があり、ノードの値Xに対して、左に含まれるノードの値はXより小さく、右に含まれるノードの値はXより大きくなるというもの。
つまり、左のノード<ノードX<子ノード。
「値の小さいノードを左に置こう」という話ではなく、「値の大小でノードの位置を決めよう」というものか。
同じ値、データの挿入は許可されていないらしいけど、そういう法則があればそうなるか。。
バランスドツリー(平衡木)
ルートノード(一番上)からリーフノード(一番下)の距離(高さ)を等しくしたツリー。
距離を等しくすることで、探索にかかる計算量が少なくする目的。
探索の際、ルートノードからリーフノードに向かって検索が行われていく。
バイナリ―サーチツリーでは、片方にのみツリーが伸びることもあるらしい。
そうなれば、せっかくの法則も効率が悪くなっていくよね。
それらを解消するために考えられたのがバランスドツリー。
ノードが削除、挿入されるたびに、ツリーを再構築して、高さをバランスよく保つようになっている。
ヒープ
親ノードは子ノードよりも小さいか、等しいという条件を満たすツリー構造。または、親ノードは子ノードよりも大きいか、等しいツリー構造。
親子間のノードにはこのような制約があるけど、子ノード間にはないみたい。
単に「ヒープ」と呼ばれる場合、バイナリツリーとして構成されるバイナリヒープを指すことが多いらしい。
豆知識(?)として覚えておこう。
まとめ
今回はデータ構造を勉強しました!!
ツリーやノードってディレクトリとは違うのかね?
そこら辺を詳しく調べてみようっと。
参考資料
一週間で身につくアルゴリズムとデータ構造-http://sevendays-study.com/algorithm/pr-day3.html
データ構造-https://www.codereading.com/algo_and_ds/ds/