「二分木 9」 これまで 見てきた 二分木では、すべて、データ構造体の テキスト内で 定義が されています。 より 多くの 制御が 必要と なったとき、例えば、下に 動くだけでなく、双方向リストと 同じように、木の 上方にも 移動させたいことが あります。 …

[住基ネット] オープンロー(a)hatena で、山根さんが 青柳武彦氏の 論文を、やんわりと 批判している。 http://openlaw.g.hatena.ne.jp/s-yamane/20050710/p2 青柳氏には - ちょっと 大げさに いえば - 歴史的な 視点が 欠けていますね。 あちらの 論文を 引…

[判決文の公開] 「下級裁主要判決情報」という web page が あります。 地裁等が、自主的に 判決文を 公開した場合、リンクして 国民に 知らせるのが その 主旨の ようです。 http://courtdomino2.courts.go.jp/kshanrei.nsf/TOP 5月末の 金沢での 住基ネッ…

「二分木 8」 それぞれの 走査は、stack か queue の どちらかを 使うことで、再帰を 用いることなしに、実行させることが できます。 一つの やり方として 反復版で inorder 走査を 書いてみましょう ▽ void tree_walk(struct Node *tree) { struct Node *n…

「二分木 7」 構築したり、二分木から 要素を 削除する 基本的な 操作は 手に入れました。 また、木に 要素が あるかどうかを 調べる コードも あります。 さて、あると 考えたものが、実際に あるのかを、はっきり 確かめる 必要が ありますよね。 それは、…

「二分木 6」 さてと 二分木を つくる コードも できたし、同じように、木から ノードを 削除できれば、というのは いい 考えですね。 これは より こみいった 作業です。 というのも、当てはまる ノードを 見つけた後で、処理に 3つの ケースが あるからで…

ふと 思いたって、戴震*1 のことを google で 検索していて、子欲居さんの page を 見つけた。 ただし 2001年以後 更新が 止まってるようで、リンク先の page も 削除されているところが 多い。 http://members.at.infoseek.co.jp/sumicom/ ただし、その発言…

「二分木 5」 木 - tree - への 挿入は、上の 検索と ほぼそのまま 同じになります。ただ 一つ 違ってるのは、null ノードが 見つかったときに、失敗時に 要求された 返り値をもつ 新しい (ノードを) 1つ 挿入することです ▽ int tree_insert(struct Node **…

「二分木 4」 さて、ノードを 1つ つくるための コードを 書かないといけませんね。それには、新しい ノードが 二分木へと リンクできる 必要が あります。 初めに 注意することの 一つは、木には いくつかの 検索形式を 含む、多くの 操作方法が あるという…

「二分木 3」 二分木での 構造体を 定義した コードです ▽ struct Node { int data; struct Node *left; struct Node *right; }; 簡単に するため、この tutorial では ノードの値は 整数型に 決めておきます。こうすることで 例題の コードが 簡単に なるの…

はてなで、POST時の セッションID による チェック機能が 追加された ようす。 http://d.hatena.ne.jp/hatenadiary/20050715/1121427904 なんだか 今回も、アナウンスと 同時に 切り替えた みたいですね。暴走してる ? すでに、なんば りょうすけ さんによる…

「二分木 2」 木 - tree - は、木の それぞれの 要素を 必要としない どんな 操作でも、計算時間 - time complexity - が その木の高さ - height of tree - と 等しくなる という、もともとの 特性を もっています。 その結果、高さが 最適に 近ずくという …

「二分木」 二分探索法 - binary search - は、役にたつ 強力な アルゴリズムです。ただし、リストの中を 自在に 動ける - jump around - ように するための、二分探索法に 適した データ構造 - data structure - を 選択しておく、という 規制が あります。…

「リンクリスト 10」 リンクリストで 用いる テクニックには、おもしろくって 役にたつものが、いくつか あります。 1. 一致する 項目を 捜して その数を かぞえる ▽ int count(List list, int find) { int cnt = 0; while (list != NULL) { if (list->data …

「リンクリスト 9」 リストインデックスは、リンクリストや 配列のための 最善の 方法です。 リストでの 挿入や 削除、配列の 検索が 容易に できます。 もちろん、リストインデックスを 使って 効率的に 動かす コードを 得るには、多くの 役に たたない コ…

「リンクリスト 8」 リンクを ソートするのは 楽しい課題です。そこで 基本的な ソートの実装については、読者に 残しておくことにしましょう。 詳細な ソートの説明を するつもりは ありません。というのも、この tutorial が リンクリストについての もの…

「リンクリスト 7」 初めて リンクリストを 学んだときは、あるリストの 一部を 他に 繋げる - splice - という 発想自体が むずかしいものでした。 それは 想像も つかないような、長くて 複雑な アルゴリズムに 違いない、と 考えていました。 もちろん、…

「リンクリスト 6」 リストを 適当な ところで 逆順に できれば、ときとして、役にたつ 使い方に なります。 線形リストを 逆順に することは とても 簡単で、リストを 渡っていって、元のリストの 前方から 削除していき、新しいリストの 前方へ 挿入するこ…

土村さんの page が 更新されています。 ・ Vine Linux 3.1 の 設定 debian も そうだけど、vine を 2.6 から 3.1 に upgrade しないと、とは 思ってるんですが、なかなか フンギリが つかなくって ...

折原浩さんの page が 先月末から 始まっている。 http://www.geocities.jp/hirorihara/ (ここからは ひとりごとです) なんで マージナルマンの 論理の 組み立てに、トインビーが - 唐突に - でてきたのか わからなかったが、そうか ! ロシアの 啓蒙思想家の…

「リンクリスト 5」 ヘッダファイルに 記されていた 4つの 関数は、tutorial の 最後にある List.c に そのコードが 書かれている (実際の 関数は 4つ じゃなくて 6つ)。 #include /* free(), abort() に必要 */ #include /* assert() に必要 */ #include "L…

「リンクリスト 4」 次に 入る前に、大急ぎで、線形リストと 双方向リストについて ノートしてみましょう。 線形リストに 項目を 挿入するとき、2つの リンク つまり 双方の next ポインタを 書き換える 必要が あります。 n->next = item->next; /* n の ne…