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

#データ構造とは
データを効果的に扱うために、一定の決まりで体系立てて格納する形式で、プログラムの処理の流れ（アルゴリズム）に大きく影響する。アルゴリズムに適したデータ構造を使用する必要がある。
データ構造はどのようなものがあり、どのような特徴があるのか、そしてどのアルゴリズムに適しているかを把握する必要がある。

* **配列**

「同じデータ型の塊」「複数の箱をひとつにまとめたもの」と言われる。
配列には添字があり、特定の箱を指定することが可能
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/616ac28d-fd33-2ccb-ffa7-c9ae6ae7fa5c.png)

配列名「a」の中に、数値型の複数のデータをいれることが可能。それぞれの箱を指定する場合、例えば最初の箱についてはa[0]と指定することで、その箱の中の値を取り出すことが可能
配列は通常繰り返し（for文、while文）と組み合わせて使われることが多い。
繰り返し回数を添字に指定すれば「配列の最初から一つずつ値をとって処理をする」ことができるから。
配列には添字があるため、ランダムでのデータ取得をすることが容易
配列の後ろにデータを追加することも高速にできます。逆に、配列の中間部分にデータを追加する場合は、以降の添字をすべて付け替える必要があるため、処理に時間がかかる

> メリット：添字による任意のアクセスが可能、配列末尾のデータ追加が高速
> デメリット：配列の中間部へのデータ追加は遅い。


* **構造体の配列**

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/3556b60b-6396-1013-d58b-a858f78d38c4.png)

**構造体とは**
配列は、同じデータ型の塊であるため、異なるデータ型を組み合わせて格納することはできない。
しかし、構造体を使用することで、異なるデータ型を格納することが

> メリット：異なるデータ型を１つの塊としてデータを格納できる
> デメリット：配列と組み合わせた場合、データ量が大きくなり、大量にメモリを消費する

* ツリー構造（木構造）

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/7762664f-3126-a3de-ac3a-23a225e57a64.png)

**ツリー構造とは**
ツリー構造（木構造）は、その名の通り木（tree)のような形状をしたデータ構造
階層を持つデータの集まりとなっており、大きなデータから目的のデータを見つけたい場合におすすめ

**二分探索木とは**
「左の子の値＜親の値＜右の子の値」というデータの持ち方が特徴
大量のデータから目的の値を探す場合、各階層の親の値と比較して２つある分岐のうちのどちらの木を探索していくかを選択するたびに、探索対象を全体の半分に絞り込んでいくことができるので効率的。
データを探索するには、まず準備段階で、データがソート（並び替え）されていなければなりません。また、処理の途中でデータが変化する場合、適宜ソートしなおす必要もあ流。

> メリット：大量のデータを効率よく扱いたい場合に有利
> デメリット：事前にデータをソートしておく必要がある

* **キュー**
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/2e40dea4-d386-0074-c7c1-da8a75dfaa9d.png)

データ構造というよりデータの扱い方の1つ
先入れ先出し（First In First Out：FIFO）のリスト構造でデータを保持
一般的にキューにデータを入れることをエンキュー、取り出すことをデキューと言う。


* **スタック**

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/985049b6-d387-ec6d-fe82-443349e366e2.png)

キューと反対の考え方
後入れ先出し（Last In First Out：LIFO）の構造でデータを保持
一般的にスタックにデータを入れることをプッシュ、取り出すことをポップという
物が積み上げられた状態
入れるときは上に積まれ、取り出すときも上から
Webブラウザの「戻る」ボタンやテキストエディタの「やり直し」といった、履歴をさかのぼる処理では、スタックが使われます。

* **ヒープ**

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/7b20c874-6fe5-4dc0-7f01-dde77942dc04.png)


二分探索木と同じくツリー構造
「子は親より常に大きいか等しい（または常に小さいか等しい）」というルールがある。
子が複数ある場合、子どうしの大小関係に制約はない。
ヒープは根に最大値または最小値がくる構成であるため、最大値や最小値を取得するのに適している。


https://products.sint.co.jp/topsic/blog/data-structure

#アルゴリズムとは
手順や問題解決の手段
複数のアルゴリズムを組み合わせたり、一部を改良したりしながら使用して、問題解決を実施する。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/a316a8cf-c5d3-77af-a30c-fee3eeb16d9d.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/31e85166-187d-1910-be67-378ef51f981a.png)

フローチャートで使われる主なダイアグラム
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/c692f038-653c-b9e0-9156-0834da7dab71.png)

「1～10の乱数を発生させ、その値が5以上ならその値の数だけ、"HelloWorld"という文字列を表示する」というプログラムのアルゴリズムを記述すると、以下のようになる。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/06b1d6a8-6410-a360-99ee-b268b8cf1516.png)

ある処理がアルゴリズムとなるためには、2つの重要な条件をクリアしなくてはいけない。それが、正当性と停止性。

* **正当性**

アルゴリズムは、与えられた課題に対して正しい結果をもたらさなければなりません。これを、アルゴリズムの正当性という。
ルゴリズムの正当性とは、指定された条件を満たす入力値が与えられたとき、必ず正しく動作する（正しい出力結果を得る）ことを保証することで示される
アルゴリズムの正当性を示す方法として、アサーションを用いる方法があります。アサーションとは、アルゴリズム（プログラム）の任意の位置で、その時点において、満たさなければならない条件が成立しているかどうかを判定すること。
アルゴリズムの正当性の上で、大事なのは、必ずアサーションが成立していること。
部分正当性と言います。これは、「プログラムがその位置で停止すれば、その時点での答えは正しい」ということを保証している。

* **停止性**
アルゴリズムは、最終的には必ず停止しなくてはなりません。アルゴリズムの停止性とは、いかなる条件の入力値が与えられても、有限時間内に必ず正しく停止することを保証することで示される。

アルゴリズムの停止性の証明には、反復処理の終了条件の判定に使用される変数などを見て、必ず有限回数の繰り返しで終了条件が成立するいことを証明する方法があります。永遠に繰り返され、処理が終わらない手順のことは、無限ループと呼ばれ、アルゴリズムとはなりえない。

![スクリーンショット 2021-05-03 15.30.30.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/b28fce29-980d-55ed-fb03-fa3253267922.png)


変数：アルゴリズムにおいて、データを扱う際、そのデータをメモリ上に保存しておく必要があります。その領域のこと。変数はデータを入れるための箱のようなもの。

![スクリーンショット 2021-05-03 15.54.11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542047/d2088183-4883-79f0-396e-b0b07ee01962.png)