Dokusyo-nissi Bessitu


2005-06-26 φ(-_-)

■ [lang]はじめての C

    「リンクリスト」
   
    リンクリストって何なのだろう ?
   
    リンクリストとは、要するに、それぞれの項目 - item - がその次を指し示してい
    る、そんな項目が集まったものなんです。
   
    |1| -> |2| -> |3| -> |4| -> |5| -> -
   
    そのシーケンスは、番兵 - sentinel - と呼ばれる特別の項目の値を最後尾にもっ
    ていて、多くの場合では、シンプルな null ポインタがそれになります。
   
    各々の項目はポインタを伴った構造体で、ポインタの示す先には同じ型の "next" 
    ポインタがあります。ポインタが、全体のどこにあるかを捜して知らせるのです。
   
    struct Item {
    	T data;
    	struct Item *next;
    };
   
    単純だけど、1つの方向に進む - travel - だけなら、これで十分です (first から
    始まって last で終わるような)。
   
    でも、行きすぎてから、その項目まで帰りたいときには、"prev" ポインタという別
    のポインタが必要になります。
   
    struct Item {
    	T data;
    	struct Item *prev;
    	struct Item *next;
    };
   
    この構造体を使うことで、前方にも後方にも進むことができる、項目のリストをつ
    くることができます。
   
    別の言い方だと、全体の中のそれぞれの項目が、どこにいても、手に入るわけです
    。
   
    簡単に示してみましょう。
   
    - <- |1| <- |2| <- |3| <- |4| <- |5| (prev)
    |1| -> |2| -> |3| -> |4| -> |5| -> - (next)
   
    まずい図ですが、もし読みとれるようでしたら、prev ポインタが next ポインタと
    同じ道のり - way - で動くことに注目してください。
   
    例えば、リストの最初の項目の前に番兵があるとすると、prev ポインタの最終点で
    それは現れてきます。
   
    リストの中のどれかの項目にアクセスする際には、間接参照 - derefering - が使
    えます。
   
    次の項目に行く  : item = item->next;
   
    前の項目へ帰る  : item = item->prev;
   
    次の次の項目へ  : item = item->next->next;
   
    元にも戻れる :p : item = item->next->prev;
   
    ループを用いるのも、たいていは簡単です。
   
    リストを渡っていく普通の表現法はこんな感じです。
   
    for (item = list; item != NULL; item = item->next) {
    	visit(item); /* visit does something with a single item */
    }
   
    とっても簡単で、それに、ちょうど C や C++ で、配列を渡っていくとき用いるも
    う 1つの別の表現法と同じようなことに気がつくでしょう。
   
    for (i = 0; i < size; i++) {
    	visit(array[i]);
    }
   

2005-06-29 φ(-_-)

■ [lang]はじめての C

    「リンクリスト 2」
   
    先に進む前に、番兵について少しだけ述べてみましょう。
   
    番兵には 3つの型があります。 null ポインタ、ダミーノード (特別な、中身のな
    い - invalid value - 項目で、番兵として使うことができます) それと循環リンク
    です。
   
    null ポインタ、それにダミーノードはとても簡単です。でも、循環リンクって何な
    んでしょう ?
   
    循環リンクでは、リストをリング型の構造体へと変えて、いつどこからでも、末尾
    を見つけ出して - get the end - 次の項目へと移ります。
   
    リストの各々の型での、ほんのわずかな、基本となる組み合わせ - basic
    conversation - は次のとおりです。シンプルに留めるために、ここでは (next ポ
    インタのみの) 線形リスト - single linked list - を使うことにします。
   
    末尾が null ポインタ▽
   
    初期化:
   
    list = NULL;
   
    item の後に n を挿入:
   
    if (item == NULL) {
    	list = n;
    	list->next = NULL;
    }
    else {
    	n->next = item->next;
    	item->next = n;
    }
   
    item の後を削除:
   
    save = item->next;
    item->next = item->next->next;
   
    移動:
   
    for (item = list; item != NULL; item = item->next)
   

2005-06-30 φ(-_-)

■ [lang]はじめての C

    「リンクリスト 3」
   
    先頭がダミーで、末尾が null ▽
   
    初期化：
   
    struct Item list;
    list->next = NULL;
   
    item の後に n を挿入:
   
    n->next = item->next;
    item->next = n;
   
    item の後を削除:
   
    save = item->next;
    item->next = item->next->next;
   
    移動:
   
    for (item = list->next; item != NULL; item = item->next)
   
    先頭も末尾もダミー▽
   
    初期化:
   
    struct Item list;
    struct Item sentinel;
    list->next = sentinel;
    sentinel->next = sentinel;
   
    item の後に n を挿入:
   
    n->next = item->next;
    item->next = n;
   
    item の後を削除:
   
    save = item->next;
    item->next = item->next->next;
   
    移動:
   
    for (item = list->next; item != sentinel; item = item->next)
   
    循環リスト▽
   
    初期化:
   
    list->next = list;
   
    item の後に n を挿入:
   
    n->next = item->next;
    item->next = n;
   
    item の後を削除:
   
    save = item->next;
    item->next = item->next->next;
   
    移動:
   
    item = list;
    do {
    	/* Work with item */
    	item = item->next;
    } while (item != head);
   
    すべてのリンクリストの組み合わせは、上で述べた組み合わせのどれかに従ってい
    ます。
   
    なのでこれら全部が理解できれば、初歩的なリストの進行コードをまちがえずに読
    みとれますし、より複雑なアルゴリズムのロジックの基礎を追いかけることもでき
    ます。
   
(注) do-while ループ

他の while や for ループと違って、ループ本体が実行された後で条件式が計算される
。

そのため、ループ本体は、少なくとも 1回は実行されることになる (KandR 2nd p77)。

(追記) 不注意によるミスを訂正。(7/4)


2005-07-02 φ(-_-)

■ [lang]はじめての C

    「リンクリスト 4」
   
    次に入る前に、大急ぎで、線形リストと双方向リストについてノートしてみましょ
    う。
   
    線形リストに項目を挿入するとき、2つのリンクつまり双方の next ポインタを書き
    換える必要があります。
   
    n->next = item->next; /* n の next ポインタにセット */
    item->next = n;       /* item の next ポインタにセット */
   
    しかし双方向リストの場合は、リンクの数を 2倍用意する必要がでてきます。
   
    双方向リストでは、仕事が 2倍になることを覚えておくと、助かることになります
    。
   
    n->prev = item;       /* n の prev ポインタ */
    n->next = item->next; /* n の next ポインタ */
    n->next->prev = n;    /* n の next->prev ポインタ */
    n->prev->next = n;    /* n の prev->next ポインタ */
   
    準備されたこれらの 4つのリンクだけで、項目は正しく挿入されるのです。
   
    ただし、リンクの中に番兵があると、問題が起こってきます。
   
    そこで、双方向リストのどこであっても、正しくノードを挿入するコードを書いて
    みましょう。
   
    n->prev = item;
    n->next = item->next;
    if (n->prev != NULL)
    	n->prev->next = n;
    if (n->next != NULL)
    	n->next->prev = n;
   
    すべてのリンクリストで、項目を挿入あるいは削除することができます。
   
    実際、この tutorial のために書いたごく小さなリストライブラリでは、関数が 4
    つ含まれているだけです。つまり、挿入と削除、それに先頭項目の検出と末尾項目
    の検出です。
   
    そのヘッダはこうなっています▽
   
    #ifndef PRELIST_H
    #define PRELIST_H
   
    typedef enum {BEFORE, AFTER} Direction;
    typedef struct element *Element;
    typedef struct element *List;
   
    struct element {
    	Element prev;
    	Element next;
    	int data;
    };
   
    Element first(Element iter);
    Element last(Element iter);
    List add(List list, Element iter, Element item, Direction dir);
    Lisr rem(List list, Element iter);
   
    #endif
   
(注 1) #ifndef は、defined 演算子を使った条件文のマクロを参照。

          http://d.hatena.ne.jp/sekiyo/20050221

また #ifndef で定義した NAME はヘッダファイル自体を指すので、上の例だと、
PRELIST_H はヘッダファイル名が prelist.h であることを (おそらく) 表している。

(注 2) enum は列挙子のこと。名前付きの定数の、集合の範囲の値をもつ型 (KandR 2nd
p266)。

typedef とともに用いる場合がある。

typedef enum {定数0, 定数1, ... } 列挙子名;

    シンプルでしょ ?
   
    先頭と末尾のポインタを保守 - maintain - しているコードでは、first と last
    の関数は、まず絶対使うことはありません !
   
    ここにそれを付け加えた理由はただ 1つ、たいていの場合 - 私もですが - 先頭と
    末尾の保守をナマケてしまうからです。
   
    しかし、この先頭と末尾を普段から使うことで、大きなリストにおいても、大きな
    パフォーマンスをヒットさせる - be a big performance hit - ことができるとい
    う、課題を知るようになります。
   
    でも、この tutorial では、リストは小さいでしょうから、パフォーマンスの問題
    は受け入れられる範囲になっています。
   
    On to the code !
   

2005-07-03 φ(-_-)

■ [lang]はじめての C

「リンクリスト 5」

ヘッダファイルに記されていた 4つの関数は、tutorial の最後にある List.c にそのコ
ードが書かれている (実際の関数は 4つじゃなくて 6つ)。

    #include <stdlib.h> /* free(), abort() に必要 */
    #include <assert.h> /* assert() に必要 */
    #include "List.h" /* prelist.h ではなかった ! */
   
    /* 次の 2つの関数はこのソースファイル内のみで使われる */
   
    static void ins_before(Element iter, Element item)
    {
    	assert(iter != NULL);
    	assert(item != NULL);

    	item->prev = iter->prev;
    	item->next = iter;
    	if (iter->prev != NULL)
    		item->prev->next = item;
    	iter->prev = item;
    }
   
    static void ins_after(Element iter, Element item)
    {
    	assert(iter != NULL);
    	assert(item != NULL);

    	item->prev = iter;
    	item->next = iter->next;
    	if (iter->next != NULL)
    		iter->next->prev = item;
    	iter->next = item;
    }
   
    Element first(Element iter)
    {
    	while (iter != NULL && iter->prev != NULL)
    		iter = iter->prev;
    	return iter;
    }
   
    Element last(Element iter)
    {
    	while (iter != NULL && iter->next != NULL)
    		iter = iter->next;
    	return iter;
    }
   
    List add(List list, Element iter, Element item, Direction dir)
    {
    	assert(item != NULL);

    	if (list == NULL) /* Empty list*/
    		list = item;
    	else {
    		if (iter == list && dir == BEFORE) /* before head */
    			ins_before(list, item);
    		list = item;
    		}
    		else {
    			if (dir == BEFORE) /* Before internal node */
    				ins_before(iter, item);
    			else /* After internal node */
    				ins_after(iter, item);
    		}
    	}
    	return list;
    }
   
    List rem(List list, Element iter)
    {
    	assert(list != NULL)
    	assert(iter != NULL)

    	if (iter->prev != NULL)
    		iter->prev->next = iter->next;
    	if (iter->next != NULL)
    		iter->next->prev = iter->prev;
    	if (iter == list)
    		list = iter->next;
    	free(iter);

    	return list;
    }
   
(注 1) assert - プログラムのバグを調べるときに使う関数 (KandR 2nd p320)。

assert ( 評価式 )

評価式が偽 (帰り値が 0) のときは、標準エラー出力でエラーメッセージをプリントす
る。

    Assertion failed: 評価式, file ソースファイル名, line 行番号

その後、abort を呼び出して異常終了。

(注 2) static - 関数を static と宣言すると、その名前はそれが宣言されたファイル
の外からは見えなくなる (KandR 2nd p101)。


2005-07-05 φ(-_-)

■ [lang]はじめての C

    「リンクリスト 6」
   
    リストを適当なところで逆順にできれば、ときとして、役にたつ使い方になります
    。
   
    線形リストを逆順にすることはとても簡単で、リストを渡っていって、元のリスト
    の前方から削除していき、新しいリストの前方へ挿入することで、リストを構築し
    ていきます。
   
    結果は、次のようなアルゴリズムになります。
   
    0:
    Old: 1 -> 2 -> 3 -> 4 -> -
    New: -
   
    1:
    Old: 2 -> 3 -> 4 -> -
    New: 1 -> -
   
    2:
    Old: 3 -> 4 -> -
    New: 2 -> 1 -> -
   
    3:
    Old: 4 -> -
    New: 3 -> 2 -> 1 -> -
   
    4:
    Old: -
    New: 4 -> 3 -> 2 -> 1 -> -
   
    このアルゴリズムの疑似コードを、想定して書くのはやさしいですね。
   
    sub reverse(list)
    hold
    done
    todo
   
    done = null
    todo = list
    while todo != null
    hold = todo->next
    todo->next = done
    done = todo
    todo = hold
    loop
   
    return done
    end sub
   
    また、双方向リストでは、prev ポインタも考えにいれておかないといけません。そ
    こで注意深く考えてみて、1行分だけこのアルゴリズムにつけ加えておきます。
   
    C および C++ での、双方向リストにおける逆順のためのソースは、次のとおりです
    。
   
    List reverse(List list)
    {
    	Element hold;
    	Element done;
    	Element todo;
   
    	done = NULL;
    	todo = list;
    	while (todo != NULL) {
    		hold = todo->next;
    		todo->next = done;
    		done = todo;
    		todo = hold;
    		done->prev = todo; /* Fix the prev link */
    	}
    	return done;
    }
   

2005-07-06 φ(-_-)

■ [lang]はじめての C

    「リンクリスト 7」
   
    初めてリンクリストを学んだときは、あるリストの一部を他に繋げる - splice -
    という発想自体がむずかしいものでした。
   
    それは想像もつかないような、長くて複雑なアルゴリズムに違いない、と考えてい
    ました。
   
    もちろん、繋ぐということが、単独の項目を挿入するのと、ほぼ正確に、同じよう
    に実現したときには、少しまごついてしまいましたが。
   
    線形リストでのつなぎ方はギコチなくって、実際敬遠されがちです。
   
    多くのアプリケーションで使われてる、双方向リストのつなぎ方のほうは、あっけ
    ないほどやさしいものです。
   
    ごく小さな list splice 関数はこんなかんじです▽
   
    List splice(List list, Element pos, Element first, Element last, Direction
    dir)
    {
    	assert(list != NULL);
    	assert(pos != NULL);
    	assert(first != NULL);
    	assert(last != NULL);
   
    	if (dir == BEFORE) {
    		first->prev = pos->prev;
    		last->next = pos;
    	}
    	else {
    		first->prev = pos;
    		last->next = pos->next;
    	}
    	if (first->prev != NULL)
    		first->prev->next = first;
    	if (last->next != NULL)
    		last->next->prev = last;
   
    	return list;
    }
   
    ここでは条件文は、リストに追加する際、その前または後のどちらに挿入するかを
    判断し、また null ポインタがある可能性についても考えてあります。
   
    例えば、リストの前方へ繋いでいくとすると、first->prev が null ですので、
    first->prev->next としてセットすると、null ポインタを参照することになって、
    たぶんセグメンテーション違反がおきてしまいます。
   
    チェック無しで、項目が前に挿入されると仮定すると、こんなかんじです▽
   
    List splice(List list, Element pos, Element first, Element last)
    {
    	first->prev = pos->prev;
    	last->next = pos;
    	first->prev->next = first;
    	last->next->prev = last;
   
    	return list
    }
   
    なぜ私がまごついたのかを、わかってくれましたか ?
   
 ごへんじ -> はっきりいってよくわかってません ...


2005-07-07 φ(-_-)

■ [lang]はじめての C

    「リンクリスト 8」
   
    リンクをソートするのは楽しい課題です。そこで基本的なソートの実装については
    、読者に残しておくことにしましょう。
   
    詳細なソートの説明をするつもりはありません。というのも、この tutorial がリ
    ンクリストについてのものだからです。ここでは、私の小さなリストライブラリに
    あるマージソートを取り上げてみます。
   
    (プログラムは省略)
   
    マージソートのアルゴリズムは、リンクリストであっても、変わりはありません。
    ですので、どんなアルゴリズムの本を開いても、そこにはこのコードそのままのや
    り方が見つかるでしょう。
   
    マージソートは、NlogN time での実行が保証され、また安定性に強い、よくできた
    汎用のソートアルゴリズムです。
   
    競争相手であるクイックソートやヒープソートでは、一番の決定的要素としての安
    定性を欠いているのです。
   
    リンクリストをソートする他の代わりとなるやり方は、初めのうちは、明らかでは
    ありません。しかし二分木 - binary tree - では、いつでもこのソートするという
    事実を活用します。
   
    単にリストを渡っていくのであれば、最初の項目を削除して、二分木に挿入します
    。このとき、規則に則って tree をたどっていき、新しいリストの末端へと挿入し
    ていくのです。
   
   
    人がやらせようとすることとは関係なく、たびたび、構造体の間での交換 - switch
    - が意味をもつことがあります。
   
    この続きは、次のトピックで ...
   
最後のところがよくわからない。誤訳かも ?

(追記) 一部訳文を訂正。


2005-07-09 φ(-_-)

■ [lang]はじめての C

    「リンクリスト 9」
   
    リストインデックスは、リンクリストや配列のための最善の方法です。
   
    リストでの挿入や削除、配列の検索が容易にできます。
   
    もちろん、リストインデックスを使って効率的に動かすコードを得るには、多くの
    役にたたないコードを除くこともそうですが、いくらか手間がかかります。しかし
    、それはとても役にたつものになります。
   
    リストインデックスの作成には、リストにどれだけの項目があるのかを知る必要が
    あります。
   
    そこで、項目のポインタに動的な - dynamic - 配列を割り当てて、各項目を新しい
    配列に加えながらリストをたどっていきます。
   
    簡単な実装コードの一例▽
   
    Element *make_index(List list, int *n)
    {
    	Element item;
    	Element *index:
    	int count;
   
    	count = 0;
    	for (item = list, item != NULL; item = item->next)
    		count++;
    	*n = count;
    	index = malloc(count * sizeof(*index));
    	count = 0;
    	for (item = list; item != NULL; item = item->next)
    		index[count++] = item;
   
    	return index;
    }
   
    注意する点は、リストの頻繁な変更によって、index が expensive なものになるこ
    とです。
   
    index の更新では、リストと malloc の呼び出しという 2つの traversal が求めら
    れます。
   
    それと、もし効率面ばかりに目がいき、定期的にリスト変更時の index の更新を行
    わなかったら、結局は、現在必要とするリストではなくて、古いほうのリストを
    index してしまうという問題が起こることになります。
   
    慎重にこのトリックは使用すること、ですね。
   

2005-07-12 φ(-_-)

■ [lang]はじめての C

    「リンクリスト 10」
   
    リンクリストで用いるテクニックには、おもしろくって役にたつものが、いくつか
    あります。
   
    1. 一致する項目を捜してその数をかぞえる▽
   
    int count(List list, int find)
    {
    	int cnt = 0;
    	while (list != NULL) {
    		if (list->data == find)
    			cnt++;
    		list = list->next;
    	}
    	return cnt;
    }
   
    2. リストの N番目の項目を見つけだす▽
   
    Element get_nth(List list, int index)
    {
    	int i;
    	for (i = 0; i < index; i++) {
    		list = list->next;
    	if (list == NULL)
    		return NULL;
    	}
    	return list;
    }
   
    3. 全リストの抹消
   
    これはトリッキーな仕組みで、次の項目に移動してからでないと、その項目を free
    できません。
   
    多くの人は次のやり方でうまくいく、とまちがって信じています。
   
    void destroy(List list)
    {
    	while (list != NULL) {
    		free(list);
    	list = list->next;
    	}
    }
   
    正しい方法では、ポインタの保存を用いることで、開放されたメモリにアクセスで
    きなくするのです▽
   
    void destroy(List list)
    {
    	Element save;
    	while (list != NULL) {
    		save = list->next;
    		free(list);
    		list = save;
    	}
    }
   
    4. ダブってる (項目を) 削除する▽
   
    void unique(List list)
    {
    	Element curr = list;
    	Element save;

    	/* Empty list */
    	if (curr == NULL)
    		return;
    	while (curr->next != NULL) {
    		if (curr->data == curr->next->data) {
    			save = curr->next->next;
    			free(curr->next);
    			curr->next = save;
    		}
    		else
    			curr = curr->next;
    	}
    }