データ構造とアルゴリズム勉強会 #3

内容

・線形探索
・二分探索
・双方向連結リスト

線形探索

問題：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A&lang=jp
for文を回すだけなので省略します。

二分探索

計算量O(Nlog(2)N)のアルゴリズムです。
与えられた値と配列の中の値で一致するものがあるかを探しますが、その際配列が昇順に並んでいる場合、決め打ちができます。leftを左端、rightを右端、真ん中をmidとします。例えば以下のような感じです。

// 5が配列に含まれるか探したい
vector = [1, 3, 4, 5, 7]
=> left = 1, right = 7, mid = (1+7)/2 = 4

ここでmidが5以上か未満かを判定します。
midが５以上ならrightの値がmidになり、次の探索は左端からmidまでになります。
逆にmidが５未満ならそこをleftにし、それを繰り返すことで探索範囲を狭めていきます。そして探索の幅が1以下になった時、rightが探したい値となっています。

例えば上の例では1回目のサーチでmid = 4 < 5より、left = 4, right = 7です。
次にmid = (4+7)/2 = 5となり、mid = 5 >= 5だから、right = 5
right - left = 1より、探索の幅が1になったので終了、となります。

実装は以下のようになります。

bool binarySearch(vector<int> S, int key){
    int left = 0;
    int right = S.size()-1;
    int mid;

    while(right - left > 1){
        mid = (left+right)/2;
        if(S[mid] >= key) right = mid;
        else left = mid;
    }

    return S[right] == key;
}

双方向連結リスト

問題:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp
ここが一番重いのでメインで説明します。
まず、双方向連結リストの構造ですが、ポインタをキーに持っていて、キーを参照して値を見つけます。
そして構造体として前後の値のキーを持っているため、操作上は相互に繋がっているような構造になります。
イメージとしては ① ⇄ ② ⇄ ③ ⇄ … のようにキーを相互に参照できます。
これを実現する構造体をまず定義します。

struct Node{
    int key;
    Node *next, *prev;
};

Nodeは整数型のキー(実際の値)と、前後の値のポインタを持ちます。これによって相互に参照ができます。
問題の解説ではなく双方向連結リストの理解が目的なので、以下ではこれの基本的な操作の実装のみ解説していきます。

まず、基準となるところがないとリストは機能しないので、初期化を行います。

Node *nil;

void initialize(){
    nil = (Node *)malloc(sizeof(Node)); // malloc:メモリを確保,sizeof:Nodeを定義するのに必要なメモリを確保
    nil->next = nil; // (*nil).next = nil
    nil->prev = nil; // ->は参照？
}

グローバル変数としてNode *nilを定義し、次に初期化の関数を実装します。
(Node *)malloc(sizeof(Node))はNodeを格納するのに十分なメモリを確保しているというイメージで大丈夫です。詳しく理解する必要はありませんが、直接メモリを操作する関数なので危険ですし、あまり使う機会はないです。->はアロー演算子と呼ばれ、ここではnil.nextと同じです。構造体のポインタを参照するときにこれを用います。
ちょっと不思議ですが、この実装により前後に自身を持つリストができました。ここに要素をつなげていきます。

まず、nilが最初の要素なので、新たなデータはnilの次に入れることになります。
もともとnil ⇄ 1というリストがあったとしましょう。ここにxが入力されました。つまり、nil ⇄ x ⇄ 1とリストを更新したいのです。そのような実装は以下のようになります。

void insert(int key){
    Node *x = (Node *)malloc(sizeof(Node));
    x->key = key;

    x->next = nil->next; // nilの次が最初だから
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}

引数としてkeyを受け取ります。これはデータです。新たにxという名前のNode構造体のメモリを確保します。そしてそこに受け取った値を格納します。
ここでもう一度確認しますが、もともとnil ⇄ 1があり、nil ⇄ x ⇄ 1の矢印部分を4つの操作で完成させます。
x->next = nil->next: x → 1
nil->next->prev = x: x ← 1 (ここでx ⇄ 1が完成)
nil->next = x: nil → x
x->prev = nil: nil ← x(ここでnil ⇄ xが完成)
ということで、4つの操作によりxがリストに挿入されました。

次に、要素の探索を実装します。nilの次から順番に総当たりしていきます。

Node* listSearch(int key){
    Node *cur = nil->next;
    while(cur != nil && cur->key != key) cur = cur->next;
    // curがnilでなく、キーが見つからなければそこのキーを返し、見つかれば次のcurを返す
    return cur;
}

curはNodeです。最初はnil->nextがもつポインタを参照し、nilの次のNodeを格納します。そこからwhile文で引数をkeyに持つcurに当たるまで、順番に総当たりしていきます。そしてcur->keyと引数keyが一致したらその値を返します。

最後に、Nodeのもつ要素を消す関数を定義します。

// Nodeを消す
void deleteNode(Node *t){
    if(t == nil) return; // tがなければ何もしない
    //2つの操作でtの前とあとを相互に繋げる
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t); // メモリ解放
}

ここは比較的わかりやすいのですが、もともと1 ⇄ t ⇄ 2となっていたところを、ポインタの参照を1 ⇄ 2となるようにし、tが格納されていた部分のメモリ領域をfree(t)で解放することでtを消します。

以上で双方向連結リストの定義、データの追加・探索・削除ができるようになりました。基本的な考え方は以上となります。