基本情報技術者　テクノロジ系　第9章 データ構造、アルゴリズム、プログラミング

[基本情報技術者試験](https://qiita.com/savaniased/items/d3f94da4f087e178cb69)
こちらより


内容がまとまったので

まとめて投稿しなおします。

# ①変数と配列
データの格納方法を【データ構造】といいます。


## データ型
データの種類のこと

* 整数型
* 少数型
* 文字型
* 論理型:　偽が真を表す

## 変数
数学で扱うものと一緒

変数にはデータを一つだけ格納することができます。

## レコード型の変数
構造体変数ともいいます。
複数の項目をもつ情報カードのような変数です。

例として

⚪️学生型の形式　⇦ 〜型の形式と呼称する

| 項目名 | 型 | 内容 |
|:-:|:-:|:-:|
|  id |整数型   |1000   |
|  name |文字型   | tanaka  |
|  sex | 文字型  | otoko  |

このように

形式を呼称して

格項目に情報を入れて行きます。

変数aに会員番号を格納するには

a.id ⇦ 10001

と表記します。

## 配列
棚や靴箱と行ったイメージ

一つの配列に同系統のデータが複数入っている訳です。

先頭要素を0か1とする場合があるので注意が必要です。

()などの括弧で要素番号を指定します。

例えば配列aの6番目の要素を指定する時

最初が1の時

a(6)

最初が0のとき

a(5)

とします。


## 二次元配列

基盤の目のようにマス目をもつ配列です。

例えば

配列名: 学生
行番号: 学生の名前
列番号: 数学の成績(他にも国語の成績など)

という風に取り出します。

# ②リスト,スタック,キュー
リスト: データとデータをリンクで接続して、順番にデータを取れるようにしたものです。
スタック: 直近から古い順にデータを遡ってデータを取り出したい時に使用します。
       のデータ構造ともいいます。後入れ先出し(LIFO)
キュー: データを格納した順に取り出したい時に使用


## リスト(線形リスト)
リストの構成データをリストの要素といいます。

特徴として

* レコード型の変数
* データをいれる項目
* 次の要素のアドレスをいれる項目
* 末尾の.nextにはNULLや-1がが入れられます。


## スタック
データを積み重ねて管理するイメージです。

用語として
* プッシュ(PUSH): データをいれる。
* ポップ(POP): データを取り出します。

後入れ先出しの法則です。

## キュー
データを行列入れて管理するイメージです。

* エンキュー(ENQUEUE　またはENQ): データを格納する
* デキュー(DEQUEUEm またはDEQ): データ取り出し

# ③木

木構造では、データを格納する部分を接点(ノード)といいます。
構造的にデフォルトされた木を逆さまにした構造になっています。

親: 上位階層にある節点
子: 下位階層にある節点
根: 最上位の節点
葉: 子を持たない節点


## 二分木と多分木

## 二分木
一番最初の根で、分かれているのは二つまでの構造

###  ヒープ
データを並べ替える用途

### 二分探索木
データを検索する用途


## 多分木
根の部分で3っ以上に分かれている構造

### B木
データを検索する用途に使用

全ての葉が同じ階層にある構造です。

## 完全二分木とヒープ
上位から順に、かつ、同じ階層で左から詰まっている
構造を完全二分木をいいます。

ヒープは更に完全二分木に置いて
親>子　または　子<親
の条件が全て成立している木です。

### ヒープの条件

* 完全二分木であること
* 親子間に一定の大小関係が成立していること

## 二分探索木の条件
下記の条件を満たしていることが条件です。

* 節点の値< (節点の右についている全ての子の値)
* (節点の左についている全ての子の値)< 節点の値

## 木の巡回
データを順番に見ていくことを巡回するといいます。

### 幅優先探索
同じ階層の節点を優先して巡回します。

上から順　かつ　左から順です。

### 深さ優先探索
下位層の節点を優先して巡回します。

根からすぐ下に下に潜って行って、突き当たったら
一つ上に戻り下に、全て見終わっってたら上に戻って同じく・・・
という方法です。

#### 先行順
行きがけ順に行います。

#### 中間順
一旦一番下を処理してから途中の節点を処理していく

#### 後行順
一番下を優先

# ④探索
アルゴリズム: 処理の手順
データを探すアルゴリズム: 線形探索、二分探索、ハッシュ法

## 時間計算量(オーダ)

データ数の増加に対する、処理時間の増加指標

### オーダ記法(O記法)
O(n)などと記述して、効率の良さを表します。
(n)は処理するデータの数を表します。

#### O(1)
データ数にかかわらず、処理時間が一定

#### O(log n)
データ数が２倍に増えても、手間が一回増えるだけ

#### O(n)
データ数が10倍だと処理時間も10倍になります。

#### O(nlog n)
データ数が10倍だと処理時間も30倍になります。

#### O(nc) (cは小文字)
データ数が10倍だと
処理時間は二乗で100倍になります。

## 探索アルゴリズム
左のオーダ記法は時間計算量を表します。

### 線形探索 O(n)
順番に一つずつ、値の比較をしていく

### 二分探索 O(logn)
データの整列が前提条件
データを前半と後半に分けて行います。

小さい順に並んていれば
中央値>目的値　であれば前半を
中央値<目的値　であれば後半を探します。

### ハッシュ法 O(1)
事前にハッシュ表に登録しておく必要がある。

ハッシュ関数を用いて
格納場所のアドレスを計算して、目的の値を探します。

## 線形探索
先頭要素から順に探します。

## 二分探索
データを昇順に整列させておく必要があります。

最小値と最大値の平均から中央値を算出する。

そこから前半と後半を分けて探索
仮に後半にあれば同様に分けて再探索

要は、中央値を求めて半分削って行って探索する方法です。

## ハッシュ法
データの格納場所を計算によって決める方法です。

### ハッシュ関数
データの格納場所を求める計算式

## ハッシュ法により衝突(コリジョン)
異なったキーに大して、同じハッシュが計算されること

### シノニム
後から、同じハッシュとして計算されたハッシュのこと
下記の方法で処理がされます。

* オープンアドレス法: 空き領域に格納
* チェーン法: 同じハッシュの値をリストで管理する方法

# ⑤整列
データを並べ替えるアルゴリズムについてです。

## 整列アルゴリズム
下記のようなものがあります。


### 交換法 O(n2)
隣同士を比較して
順序が逆であれば入れ替えます。

### 選択法 O(n2)
最大値、最小値を順じ取り出す。

### 挿入法 O(n2)
整列済み要素の適切な位置に
未整列要素を挿入する処理を繰り返します。

### クイックソート O(nlog n)
基準値よりも大きなグループと
小さいグループに分ける。
その後同様の処理を繰り返します。

二分法に近い形です。

### マージソート O(nlog n)
整列済みの二つの配列を併合することを
繰り返します。

配列データの2分の1を格納する作業領域が必要です。

### シェルソート　O(n 1.25)
挿入法の改良版

一定間隔ごとに整列し、感覚を徐々に狭めながら再度整列を繰り返します。

### ヒープソート O(nlog n)
ヒープの根を取り出して、ヒープを再構築することを繰り返します。