自分のための備忘録的なものとしてQiitaを書いていますが、これが誰かの助けになれば幸いです。
また、プログラミング初心者であるため、内容に誤りがあるかもしれないので、誤りがあれば指摘してください。
アルゴリズムとデータ構造
アルゴリズム
アルゴリズムとは処理の手順のことであり、問題解決の手段とも言えます。
アルゴリズムの三大処理
全てのアルゴリズムはこの3つの処理の組み合わせから構成されています。
- 順序処理
- 分岐処理
- 繰り返し処理
アルゴリズムの正当性と停止性
正当性と停止性はアルゴリズムがクリアしなくてはならない条件です。
正当性とは、アルゴリズムが与えられた課題に対して正しい結果をもたら差なければならないということです。
停止性とは、すべてのアルゴリズムは最終的に停止しなくてはならないということです。
処理が終わらないものは無限ループといわれて、アルゴリズムとは言えません。
データ構造
多くのデータを効率よく管理する仕組みのことです。
データをカテゴリごとに分類したり、系統立てたりします。
データ型
データ型とは、コンピュータで扱うデータのグループ分けです。
主なデータ型として以下のものがあります。
- 整数型
- 実数型
- 文字列型
- 論理型
データ構造
主なデータ構造として、以下のものがあります
| 種類 | データ構造 |
|---|---|
| 線形データ構造 | 配列 |
| リスト | |
| 連想記憶 | |
| スタックとキュー | |
| グラフデータ構造 | ツリー構造 |
| ヒープ構造 |
配列
同じ種類のデータを複数並べただけのデータ構造です。
リスト
同じ種類のデータを順序付けして並べた構造です。
順序付けには連続した整数値のインデックスを使用します。
要素へアクセスするには、インデックスを指定します。
連結リストとは、リストの中でも、要素が互いにリンクによって接続されているものです。
単方向リスト、循環リスト、双方向リストの3つがあります。
連想記憶
連想記憶は値をキー(Key)と結びつけて持ちます。
[Key(春)->Value(Spring),
Key(夏)->Value(Summer),
Key(秋)->Value(Autumn),
Key(冬)->Value(Winter),]
リストと似ていますが、要素をインデックスではなくキー(Key)で管理します。
数字で分類はできないけど、関連付けてまとめておきたいデータに最適です。
スタック
スタックでは、データを入れた順序と逆順に取り出すことができます
つまり、要素の挿入と削除がリストの先頭だけで行われるようなデータ構造です。
スタックにデータを入れることをプッシュと言い。取り出すことをポップと言います。
キュー
キューはスタックの逆で、データを入れた順に取り出すことができます。
つまり、最初に入れたデータが最初に取り出せます。
リングバッファというのは、キューの配列の先頭と末尾を結び付け、リングのような構造にしてキューの目盛りによる使用回数制限をなくしたものです。
ツリー
枝先にデータを持ち、そこからまた枝分かれしていく構造。
この構造の内、根元にあたる場所をルートと呼び、枝分かれ部分をノードと呼び、枝の部分をブランチと呼びます。
ヒープ
ツリー構造のうち、子供のノードが最大2つで、親のデータが2つの子のデータよりも小さくなるように作られたデータのことです。
ソートアルゴリズムの、ヒープソートでよく用いられます。