Ｃ言語関係掲示板過去ログ１０８３

過去ログ

No．１０８３　環状リストが、一方向の連結リストと比べて、優れている点

No.14209		連結リスト投稿者---シバケン(2004/05/24 23:52:29)
		環状リストが、一方向の連結リストと比べて、優れている点とは　一方向の時の、例外処理（先頭や末尾に挿入、削除するとき）がやらなくてよい　ことだと思いますが、違いますか？他に、優れている点はありますか？また、劣っている点とは、どんなことがありますか？よろしくお願いします。

No.14211		Re:連結リスト投稿者---norika(2004/05/25 00:20:38)
		環状リストも1方向じゃないの？

No.14219

Re:連結リスト
投稿者---NykR(2004/05/25 11:49:52)

>環状リストが、一方向の連結リストと比べて、
>優れている点とは
>　一方向の時の、例外処理（先頭や末尾に挿入、削除するとき）が
>やらなくてよい
>　ことだと思いますが、

環状でなくても先頭や末尾に挿入、削除するときと、それ以外とで処理を分ける必要はないです。

先頭の要素について処理を分けるのは、先頭の要素と他の要素とで名前が違うからです。
典型的にはこんな感じでしょうか。

＃末尾に要素を追加する処理なので、微妙に違いますが

if (head == NULL) {
    head = new_node;
} else {
    for (cursor = head; cursor->next != NULL; cursor = cursor->next)
        ;
    cursor->next = new_node;
}

同じ名前をつけることができれば同じ処理でいいはずです。ていうかできます。

ダミーノードを作ってheadも「別のノードの次の要素」にする
全部`cursor->next'になります(環状リストと同じですね)
「データ構造中で、ノードを指しているポインタ」へのポインタを反復子にする
全部`*cursor'になります
etc..

No.14233		Re:連結リスト投稿者---シバケン(2004/05/25 20:31:36)
		norika様、ありがとうございます。確かに、norika様のおっしゃる通りです。区別がしにくい表現になってしまい、すいません。

No.14234		Re:連結リスト投稿者---シバケン(2004/05/25 20:46:22)
		NykR様ありがとうございます。いい勉強ができました。もう一つご教授願いたいのですが、計算量の立場から見た時、環状リストが通常のリストより優れている点、劣っている点とは、どのようなことでしょうか。よろしくお願いします。

No.14242		Re:連結リスト投稿者---RAPT(2004/05/25 23:18:24)
		「通常のリスト」の定義は？。

No.14243		Re:連結リスト投稿者---シバケン(2004/05/25 23:28:09)
		RAPT様、レスありがとうございます。連結リストの事です。

No.14271		Re:連結リスト投稿者---RAPT(2004/05/26 22:24:10)
		>RAPT様、レスありがとうございます。 >連結リストの事です。まるで禅問答ですな。では「連結リスト」の定義は？ …あなたが勝手に思い込んでいる「あたりまえ」の事象について、その定義をあきらかにする必要があります。 NykRさんも指摘されているように、シバケンさんの発言には思い込みによる勝手な前提が暗示されており、それが明示されない限り、適切な回答をする事はできません。「リスト」だけでも、単方向・双方向・環状とありますが、環状リストも双方向リストの一種とも言える部分があります。ある目的実現のための手段（実現方法）についての評価は、その目的を明らかにしない以上、評価不可能です。

No.14275		Re:連結リスト投稿者---シバケン(2004/05/26 23:17:14)
		RAPT様、貴重なご指摘ありがとうございます。もう一度、本などで勉強しなおしてみます。お手数おかけしました。

No.14251		Re:連結リスト投稿者---NykR(2004/05/26 09:36:19)
		>計算量の立場から見た時、環状リストが通常のリストより >優れている点、劣っている点とは、どのようなことでしょうか。「環状リストには通常のリストより、計算量の立場から見て優れている点や劣っている点がある」ことが前提になっているようですが、なぜそう思うのか教えて頂けませんか？それに、私がそのような点があると主張しているわけでもないのに、「とは」といわれても困ります。計算量はデータ構造とは直接の関係はありません。計算量を決めるのはアルゴリズムです。データ構造は自分の使いたいアルゴリズムが可能かどうか(それだけではありませんが)によって決めるものであり、計算量とは間接的な関係しかないのです。＃二分探索木の全ノードをたどるのに必要な計算量はいくらかわかりますか？従って、計算量からデータ構造の優劣を決めることはできません。＃まあ、「hogeなことをやりたいときにはpoeなアルゴリズムが使えるからpiyopiyoなデータ構造が有利」という話はできます。でも最初のhoge位は質問の時点で決めておいてくれないと答える気になれません

No.14274		Re:連結リスト投稿者---シバケン(2004/05/26 22:59:26)
		>「環状リストには通常のリストより、計算量の立場から見て優れている点や劣っている点がある」ことが前提になっているようですが、なぜそう思うのか教えて頂けませんか自己中心的な質問になってしまい申し訳ありません。なぜ、このように思っと、申しますと、単なる私のおもいつきです。表現の仕方が不適切でした。 >それに、私がそのような点があると主張しているわけでもないのに、「とは」といわれても困ります。本当にすいません。 >＃二分探索木の全ノードをたどるのに必要な計算量はいくらかわかりますか？わかりません。まだ「木」という分野を学習しておりません。 NykR様、不快な思いをさせてしまい、申し訳ありませんでした。