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-06 φ(-_-)

[]はじめての 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 00:09 ブログ開設おめでとうございます!

アクセス数を上げるために当コミュニティサイトに登録しませんか?
http://profile.zmapple.com/cgi-bin/profile.cgi
より多くのひとに貴方のブログを見てもらえます。

参加するにはこちらからが便利です
http://profile.zmapple.com/cgi-bin/profile.cgi?mode=edit&title=Dokusyo%2Dnissi%20Bessitu&address=http%3A%2F%2Fd%2Ehatena%2Ene%2Ejp%2Fsekiyo%2F


お問い合わせはコチラから
http://profile.zmapple.com/cgi-bin/fmail/cmfmail.cgi

 | 

[シラノの新聞]

[枇杷と柿]

[馬葉礼 談話]

[My Links]

[Network Archives]


[かうんた→ 526097]