# アルゴリズムとデータ構造A
要点→基本的には赤字の部分がでるって話だよ
## データ型
float: 単精度浮動小数点数型
double: 倍精度浮動小数点数型
### 文字の扱いについて
ASCIIコードで、Aは`65`
```c
char chr;
chr=65;
```
### 一時的な変換（cast）
```c
(float)i
```
### 型の格上げ
1 → 6の順番で型が格上げされていく。
1. int
2. unsigned int
3. long int
4. unsigned long int
5. float
6. double
## コンソールI/O
### フォーマット指定子
|||
|---|---|
|%c|char|
|%d|int|
|%ld|long int|
|%u|unsigned int|
|%f|float|
|%f|double|
## 関数
「**入力が与えられたとき、ある処理を実行し、出力を与える**」という一連の処理
## 配列とポインタ
```c
#include <stdio.h>
#include <stdlib.h>
int main(void){
int *p;
p = malloc(sizeof(int)*3);
}
```
## 構造体
```c
struct point { int x; int y; };
struct rectangle {
struct point p1; struct point p2;
};
```
### 構造体へのポインタ
```c
struct node {
int item;
struct node *next;
}
```
## プリプロセッサ
### typedef
```c
typedef struct node *link;
int main(void){
return 0;
}
```
### include
hello2.c
```c
#include "hello2.h"
```
hello2.h
```c
#define N 10
void hello(int x, int y);
```
`#include "hello2.h"`は現在の作業ディレクトリ内にある`hello2.h`を挿入する
## コマンドライン引数
```c
#include <stdio.h>
#include <stdlib.h> //atoiを使うために必要
int main(int argc, char *argv[]){
int n;
n = atoi(argv[1]);
rintf("n=%d\n", n);
return 0;
}
```
## 文字列
- 文字を表すデータ型として**char**がある
- **文字あるいは文字定数**は、単一引用符に囲まれた一文字によって表される（'a'みたいな）
- C言語によって最もよく使われる１次元配列→文字列
- 複数個の文字（char型変数）が並んだもの
- NULL文字('\0')で終了する文字配列
- 二重引用符でくくると文字列になる
### string.hとか
- gets(): 文字列をキーボードから入力する
- `char s[8]; gets(s);`
- strcpy(target, source): target <- sourceにコピー
- strcat(target, source): target + source, targetに代入される
- strcmp(s1, s2): s1とs2を比較
- strlen(文字列): 文字列の長さ
- sprintf(char *str, format, num,num,...): printfと同じだけど文字列strに書き込む
- `sprintf(str, "%d", num);`
## アルゴリズム
- 処理するデータ量・大きさ： **N**
- 使われる計算資源の大きさ： **f(N)**
- 多くの場合**実行時間**
- 平均実行時間（average-case)
- 最悪実行時間(worst-case)
- アルゴリズム解析とは、データ量**N**に対して、実行時間**f(N)**を求めること
- 実行時間は「**比較の回数**」と等しいと思っておくと幸せになれる
- 比較回数**(N-1)**回が大雑把な実行時間を決めてる
### 実行時間によったイメージ（早い順）
- O(1)
- プログラムのほとんどの命令がただ1回、ごく数回しか実行されない
- すべての命令がこの性質→実行時間は**一定**
- O(logN)
- Nが大きくなっても**ほんの少ししか増加しない**
- 大きい問題を解く際、いくつかの小問題に分割して解くときにでてくる
- ２分探索とか
- 対数の底は関係ない
- O(N)
- 実行時間が線形
- 各要素を1つずつ一定時間かけて処理
- N個の入力を処理（出力）するアルゴリズムにとっては**最適**
- O(NlogN)
- いくつかの部分問題に分割して各々を独立にとき、それらの解を合わせて元の問題の解を作る場合
- 分割統治法
- クイックソートとか
- **準線形**とかいうらしい
- O(N^2)
- 比較的、小さい値のNしか実用上扱えない
- 2重ループでデータ対を全処理するアルゴリズムとか
- N行N列の2行列の和とか
- O(N^3)
- データ3組を全処理する3重ループ
- N行N列の2行列の乗算
- O(2^N)
- 実用にたえない力ずくの方法
lgN = log_2 N
### 探索
#### 逐次探索
- 不成功探索では**N**個すべて調べる N=O(N)
- 成功探索では平均的に約**N/2**個の数を調べる N/2=O(N)
#### 逐次探索（改良版）
- 不成功探索の比較回数を小さくするには
- 最悪N個、平均ではＮ／２個を調べれば不成功探索と分かる
#### 2分探索
- **整列した**表の中央値と、探索する値を比較
## グラフ
- 頂点（node,節点）：対象の集合
- 枝（edge,辺）：2節点間の結びつき
#### 隣接行列によるグラフ表現
- int型配列adj[i][j]
- `adj[i][j] = 1`(節点iとjとの間に枝がある)
- `adj[i][j] = 0`（節点iとjとの間に枝がない）
## 連結リスト
削除のときだけ注意しようね！！（free()し忘れ）
```c
x = head->next;
t = x->next; x->next = t->next; free(t);
```
## 抽象データ型（ADT）
- **値の集合**とそれらの上での**演算の集合**
- **インターフェース**を通してだけアクセスされる（ヘッダファイル）
- **クライアント**：抽象データ型を用いるプログラム
- **インプリメンテーション（実装）**：データ型を記述するプログラム
### プッシュダウンスタック
- 後入れ先出し（LIFO）
- push,pop操作はともにO(1)
#### 後置記法（逆ポーランド記法, postfix）
- 5 * ( ( ( 9 + 8 ) * (4 * 6) ) + 7 )
- 5 9 8 + 4 6 * * 7 + *
```c
#include <stdio.h>
#include <string.h>
#include "Item.h"
#include "STACK.h"
int main(int argc, char *argv[])
{ char *a = argv[1]; int i, N = strlen(a);
STACKinit(N);
for (i = 0; i < N; i++)
{
if (a[i] == '+')
STACKpush(STACKpop()+STACKpop());
if (a[i] == '*')
STACKpush(STACKpop()*STACKpop());
if ((a[i] >= '0') && (a[i] <= '9'))
STACKpush(0);
while ((a[i] >= '0') && (a[i] <= '9'))
STACKpush(10*STACKpop() + (a[i++]-'0'));
}
printf("%d \n", STACKpop());
return 0;
}
```
### FIFOキュー
- 挿入（**put**）：O(1)
- 最古要素の削除（**get**）：O(1)
#### 配列による実装←こっちのほうが簡単
リングバッファってやつ。
```c
#include <stdlib.h>
#include "Item.h"
#include "QUEUE.h"
static Item *q;
static int N, head, tail;
void QUEUEinit(int maxN)
{ q = malloc((maxN+1)*sizeof(Item));
N = maxN+1; head = N; tail = 0; }
int QUEUEempty(void)
{ return head % N == tail; }
void QUEUEput(Item item)
{ q[tail++] = item; tail = tail % N; }
Item QUEUEget(void)
{ head = head % N; return q[head++]; }
```
#### リンクリストによる実装
```c
#include <stdlib.h>
#include "Item.h"
#include "QUEUE.h"
typedef struct QUEUEnode* link;
struct QUEUEnode { Item item; link next; };
static link head, tail;
void QUEUEinit(int maxN)
{ head = NULL; }
int QUEUEempty(void)
{ return head == NULL; }
Item QUEUEget(void)
{ Item item = head->item;
link t = head->next;
free(head); head = t;
return item;
}
link NEW(Item item, link next)
{ link x = malloc(sizeof *x);
x->item = item; x->next = next;
return x;
}
void QUEUEput(Item item)
{
if (head == NULL)
{ head = (tail = NEW(item, head)); return; }
tail->next = NEW(item, tail->next);
tail = tail->next;
}
```
### 順位キュー（優先順位キュー, priority queue）
- 次の基本操作を実行するデータ構造
- 新しい項目の挿入
- 最大キーをもつ項目の削除
```c
void PQinit(int);
int PQempty();
void PQinsert(Item);
Item PQdelmax();
```
#### ヒープ順
- 完全二分木を考える
- 各節点がその子(もしあれば)のどれよりもキーが 大きいか等しいということが成り立つとき
- 挿入: $O(N)$、削除: $O(logN)$
#### ヒープアルゴリズム
1. 修正を加える
2. ヒープ化を行う
- ボトムアップ
- トップダウン
#### ボトムアップ
#### トップダウン
#### ヒープを用いたPQ
```c
#include <stdlib.h>
#include "PQ.h"
void fixUp(Item a[], int k);
void fixDown(Item a[], int k, int N);
static Item *pq;
static int N;
void PQinit(int maxN){
pq = malloc((maxN+1)*sizeof(Item));
N=0;
}
int PQempty(){
return N == 0;
}
void PQinsert(Item v){
pq[++N] = v;
fixUp(pq, N); //ボトムアップのヒープ化
}
Item PQdelmax(){
exch(pq[1], pq[N]); //根と最後尾を交換
fixDown(pq, 1, N-1); //トップダウンヒープ化(N-1までの範囲で)
return pq[N--];
}
```
## 動的計画法
### 例
#### 編集距離
- 文字の類似度を示す。
- 二つの文字列が与えられたとき、片方の文字列を編集して、二つの文字列を同一にするために必要な最小の編集の回数。
- 編集の3操作
- 置換
- ATG -> A**G**G
- 削除
- **A**TG -> TG
- 挿入
- ATG -> ATG**A**
## 再帰
- 再帰関数/再帰プログラム
- 自分自身を用いて定義される関数/自分自身を呼び出す
- **終了条件**
- プログラムが自分自身を呼び出すのを終える条件
- 再帰アルゴリズム
- 与えられた問題を解くために、その問題と同じ形の規模の小さい問題を解くことを繰り返して解を得るアルゴリズム
### 階乗関数
#### 定義
$0!=1,$
$N \geq 1$のとき、 $N!=N\cdot (N-1)!$
#### 実装例
```c
int factorial(int N)
{
if(N==0) return 1;
return N*factorial(N-1);
}
```
### 分割統治
半分にどんどん分割して再帰的に求めるやり方。再帰の典型例。
```c
Item max(Item a[], int l, int r)
{
Item u, v;
int m = (l+r)/2;
if(l<m) u = max(a,l,m); else u = a[l]; //配列左半分最大値
if(m+1 < r) v = max(a,m+1,r); else v = a[r]; //配列右半分最大値
if(u>v) return u; else return v;
}
```
#### イメージ
```
区間(0,10)の最大値
(0,5)と(6,10)のうち大きい方
(0,2)と(3,5)のうち大きい方
(0,1)と(2,2)のうち大きい方
(0,0)と(1,1)のうち大きい方
(3,4)と(5,5)のうち大きい方
…
```
#### 呼び出し回数
- **大きさN**の問題に対して**2つの独立な（空でない）部分にわけて**それぞれを解く再帰関数は、**自分自身をN回よりも少ない回数**だけ再帰的に呼び出す
#### 実行時間
O(N): 線形時間
### ハノイの塔
- 3本の棒が立てられている
- N枚の皿がある
- すべての皿の大きさは異なる
- 棒に入る穴が空いている
- 皿はより大きな皿の上にしか置くことができない
- 今、1本の棒に、一番大きな皿（この皿をNとしよう）をそこにして、N枚の皿が上にいくほど小さくなるように重ねてある
- 重ねてある皿を、右隣の棒に移動する手順を表示する
- ただし、一度に１枚の皿を移動するのみ
- 自分よりも小さい皿の上に、皿を置いてはいけない
皿Nをdの方向に動かす
```c
void shift(int N, int d){
if(d==1)
printf("皿%dを右に動かす.\n", N);
else if(d==-1)
printf("皿%dを左に動かす.\n", N);
}
```
N枚の皿をdの方向に動かす
```c
void hanoi(int N, int d){
if(N==0) return;
hanoi(N-1, -d); //皿Nの上にある(N-1)枚の皿を左の棒に移動
shift(N, d); //皿Nを1つ右の棒に移動
hanoi(N-1, -d); //皿Nの上にある(N-1)枚の皿を1つ左の棒に移動
}
```
使うときは↓
```c
int main(void){
int N = 10;
hanoi(N, 1); //N枚の皿を右に動かす
return 0;
}
```
### フィボナッチ数
- $F_0 = 0$
- $F_1 = 1$
- $F_n = F_{n-1} + F_{n-2} \ (n \geq 2)$
#### トップダウン動的計画法
- 一度F(i)の値を計算したらこの値を保存しておく
- 適当に大きい数Mにおいて配列`knownF[M]`を用意する。
- knownF[i] = -1に初期化しておく
- F(i)が計算されたらknownF[i] = F(i)とする
- 二回目の計算はこの結果を利用する
- 動的計画法を使うと、再帰関数の実行時間は、**与えられた引数以下のすべての引数に対する関数評価**に必要な時間に等しいか、またはそれ以下に短縮できる
## 木構造
- 木（tree）
- **節点(node)**と枝(辺、edge)**の集合
- **節点**: 頂点ともよぶ。名前や他の情報を持つことがある。
- **枝**: 二つの節点を結ぶもの（関係）
- **経路(道,path)**: 互いに異なる節点の並び、並びの中で隣り合う節点が枝で結ばれているもの
- 木は無向グラフの一種
- **任意の2節点間の経路がちょうど一つあるのが木**
### 木の種類
- 自由木:
- 一般的な構造を持つ木
- 根付き木:
- 特定の一つの節点を**木の根(root)**として区別した木
- 根付きの任意の節点は、自分自身とその下にある節点からなる**部分木(subtree)**の根である
### 木の定義
面倒なので略
### 順序木
- 根付き木
- 各接点においてこの順序が定められている木
### M分木
- 各内部節点がちょうどM個の子を持つ順序木
- M分木において、しばしば外部節点をダミーとして加え子の数をちょうどMとする
### 2分木
- M分木でM=2のとき
- 子をもたない外部節点
- 子をちょうど2個もつ内部節点、内部節点の子は順序付けられていて、左の子と右の子と呼ばれる
#### 表現
```c
typedef struct node *link;
struct node {char item; link l, r;};
```
#### 数学的な性質
- **節点のレベル(level)**: 根からの距離(根からその節点までの道をあんす枝の個数)
- **木の高さ(height)**: 木の節点のレベルの中で最大のもの（つまり、根から最も遠い節点までの距離）
- **木の道長(path length)**: 木の節点のレベルの総和
- N個の内部節点
- N個の内部節点を持つ2分木の高さは少なくとも約$log_2N$であり、高々$N$である
- **2分木がバランスしている**:
- 内部節点が存在する一番下のレベルを除いて、レベルiに内部節点が$２^i$個ある
- **完全2分木**:
- バランスしている2分木で，一番下のレベルにある内部節点がそのレベルにある外部節点より全て左にあるもの
### 木の数学的定義
- **グラフ**:
- グラフは節点と枝の集合であり，枝は異なる節点の組を連結する
- **単純な道**: 1つの節点から出発して他の節点へ到達する 枝の列で，どの節点も1度しか現れないもの
- **連結**: 任意の節点の組の間に道が存在すること
- **閉路**: 最初と最後の節点を除くと単純な道
### 木の走査
#### 1. 先行順
根→左→右
（計算式でいう）いわゆるポーランド記法
#### 2. 中央順
左→根→右
（計算式でいう）いわゆる通常の記法
#### 3. 後行順
左→右→根
（計算式でいう）いわゆる逆ポーランド記法
#### 4. レベル順走査
#### 実装例
1. 純粋な再帰のみ（先行順）
```c
void traverse(link h)
{
if(h==NULL) return;
printf("visited node = %c\n", h->item);
traverse(h->l);
traverse(h->r);
}
```
2. スタックを用いた実装（先行順）
スタックを２つ用意し、片方には木や節点へのポインタ、片方は、もう片方に入っている要素が木なのか節点なのかという情報を0,1で保持。
```c
void traverse(link h){
STACKinit(max); STACKpush(h);
while(!STACKempty()){
h = STACKpop();
printf("visited_node = %c\n", h->item);
if(h->r != NULL) STACKpush(h->r); //右の木の根
if(h->l != NULL) STACKpush(h->l); //左の木の根
}
}
```
3. キューを用いたレベル順の実装（幅優先）
```c
void traverse(link h){
QUEUEinit(max); QUEUEput(h);
while(!QUEUEempty()) {
h = QUEUEget();
printf("visited_node = %c\n", h->item);
if(h->l != NULL) QUEUEput(h->l);
if(h->r != NULL) QUEUEput(h->r);
}
}
```
### 非順序木
- 非順序木は節点とそれに接続された根付き木の集合
- 一般に、2つの異なる順序木が同一の非順序木を表すかどうか、という問題(**木の同型性問題**)は解くのが難しい。
## ソート
- **安定** → 互いに等しいキーを持つ項目の相対順序が保持される
- **各要素の逆順数**
- ファイルの中のある要素に対して、その要素より左の要素であって、その要素より大きいものの数。
- **逆順数**
- ファイルの中で順序が逆に」なっている要素の対の個数を逆順数という
- **各要素の逆順数**の合計 = **逆順数**
### 選択整列法（選択ソート）
- 実行時間: $O(N^2)$（整列済み：$O(N^2)$）
- 比較回数: $\frac{N^2}{2}$回
- 交換回数: $N$回
### 挿入整列法（挿入ソート）
- 実行時間: $O(N^2)$（整列済み：$O(N)$）
- 比較回数: 平均$\frac{N^2}{4}$回、最悪2倍
- 半交換（移動）回数: 平均$\frac{N^2}{4}$回、最悪2倍
- **キーが既に順序どおりに並んでいたら**、あるいはほとんど順序どおりに並んでいたら、挿入整列法は速い
- **ある要素の逆順数は、動く距離と一致する。**
- 各要素の**逆順数が一定数以下**であるようなファイルに対して、比較と交換の回数が線形的
- **逆順数が一定値を超えるような要素の個数が一定数以下**であるようなファイルに対して、比較と交換の回数が線形的
### バブル整列法（バブルソート）
- 実行時間: $O(N^2)$（整列済み（改良したもの）：$O(N)$）
- 比較回数: $\frac{N^2}{2}$回
- 交換回数: $\frac{N^2}{2}$回
- ファイルが整列したときに終了するよう改良できる
- 大小順が狂っていないことを見つけた時点で終了
- すでに整列したファイルの場合: 比較，交換回数は$N-1$回
### シェルソート
- 実行時間: $N^\frac{3}{2}$
- 挿入整列法の拡張
- h-整列を繰り返す
- 互いにh要素分だけ離れた要素の集まりからなる部分ファイルを整列すること
- 最初hを大きく、JOJOにhを小さくし、最後にh=1として、h整列を繰り返す
- 例: 13 -> 4 -> 1
- **h=1のときは、単なる通常の整列法なので最後には整列される**
- **互いに素な複数のhに対してh-整列すると，逆順数が一定数以下になる**
### キー添字計数法（バケツソート）
- 実行時間: $O(N)$
- キーの値の範囲Mはファイルの大きさによらず一定という条件付き
- Mが大きいとカウンタのための領域肥大化→非現実的
### 添字整列
- データ項目を実際には整列せず，**添字配列**を整列することで間接的にデータ項目を整列 している
- 添字配列の代わりに、各データ項目へのポイ ンタの配列を用いても良い
うーんよくわからん。雰囲気で理解するしかない
### クイックソート
- 実行時間: $O(NlogN)$、最悪$O(N^2)$
- **安定ではない**
- クイックソートは，最悪の場合，**約$N^2/2$回の比較**を行う
- 配列の他に$O(NlogN)$**のスタックを使う**
#### 基本アルゴリズム
### マージソート
- 実行時間: 最悪$O(NlogN)$
- O(N)の作業領域が必要
- **安定**
- 実行時間は**入力によらない**
- データを**順次的**にアクセス
- リンクリストの整列に向く
#### 基本アルゴリズム
- 2つの整列したファイルを併せて（併合）1つの大きい整列したファイルを作っていく
- 2ウェイ結合を入力ファイルがなくなるまで繰り返す
- 2つの整列した入力ファイルから、それらを1つにまとめた整列したファイルを出力すること
- 2つの入力ファイルの**先頭にある要素**のうち、**小さい方の要素**を出力ファイルに移動する
#### トップダウン型マージソート
#### ボトムアップ型マージソート
### ヒープソート
[PQ](#順位キュー（優先順位キュー-priority-queue）)についてはここ
```c
void heapsort(Item a[], int l, int r){
int k, N = r-l+1;
Item* pq = a+l-1;
//ボトムアップヒープ化
for(k = N/2; k >= 1; k--)
fixDown(pq, k, N);
//下降整列
while(N>1){
exch(pq[1], pq[N]); //最大要素と最後尾を交換
fixDown(pq, 1, --N);
}
}
Sign in with Wallet
Connect another wallet