Dokusyo-nissi Bessitu

<< 2005/07 >>
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

[Debian Memo] (for Woody)
[sekiyo HPへ]

[はじめてのC] C言語のページ (1)
[その 2] (2)
[その 3] ABC of C
[その 4] CPP World Tutorial (1) (by Prelude) linkrot
[その 5] The Standard C Library (Null)
[その 6] CPP World Tutorial (2) linkrot
[その 7] (3)
[その 8] (4)
[その 9] 作ってわかる Cプログラミング (1)
[その 10] (2)
[その 11] Arrays and Pointers in C
[その 12] Learning GNU C (1)
[その 13] (2)
[その 14] (3)
[その 15] (4)
[その 16] アドレスブック
[K & R 2nd] The C Programming Language (1)
[その 2] (2)
[その 3] (3)
[その 4] (4)
[その 5] (5)
[その 6] (6)

[my bookcase]

(サーチエンジンから 来られた方で 該当する
キーワードが 見つからないときには、上の
はてな検索窓から 再度検索してください ←
[日記] のほうを クリック)

 | 

2005-07-02 φ(-_-)

[]はじめての 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 !

 | 

[シラノの新聞]

[枇杷と柿]

[馬葉礼 談話]

[My Links]

[Network Archives]


[かうんた→ 530938]