K.Maebashi's BBS

レスありがとうございます 返信遅くてすいませんでした。 自分自身、リストの有用性自体をはっきりわかってないと思っています。 せいぜい「線形リストなら、文字を打ち込んで行ってもチェーンのつなぎ換えで ソートできて便利だな～」という程度の知識です。 ところで >負け組一号さんのサンプルで、startという変数が重要になります。 >どこかで(例えば関数で)free処理をするのでしょうが、 >start変数は、listの先頭を表していますので、これさえあれば >listにつながっているデータは全てfreeできます。 >関数でfreeするなら、引数でstartを渡してあげればOKです で、free(start)してみたら、エラーになってしまい、ただ free(start->next)としたら通りました。 まぁ、free(start)が通らないのは、僕の理解不足からくる見当違いな事をしてるせい だと思いますが、free(start->next)としたとき、チェーンで繋がった先のNULLに至るまで にmalloc()で割り当てたそれぞれのメモリ領域も解放してくれるのかが僕の理解不足の 点です。free(start->next)したとき、next側のメモリだけ解放され、後に続く NULLまでのmalloc()で取った領域は動かされず、残ったままなら マスタングさんの言う >現在のlistのnextの情報を先にとっておきます。 >そして、現在のlistをfree()します。 >その処理を現在のカーソルがNULLになるまで繰り返します。 >つまり、nextがNULLになるまで繰り返すのです。 という方法になるのか。と納得を得たしだいです。 まだ、ちゃんと理解できてないと自分自身思いますので、まだまだ精進精進だと思って います。

>自分自身、リストの有用性自体をはっきりわかってないと思っています。 >せいぜい「線形リストなら、文字を打ち込んで行ってもチェーンのつなぎ換えで >ソートできて便利だな～」という程度の知識です。 リンクリストは、要素(サンプルの場合、list)を削除する処理が 配列に比べて早いというのが一般的に言われています。 ですので、要素の追加や削除を頻繁に行う場合は有用かもしれないですが、 実のところ、データ構造は配列が一番便利ですし、ツリーやキューなど の方が良いケースもありますので、リンクリストが有用な場面は少ない かもしれないです。 私は、Cで動的に要素を追加するのにリンクリストを使ってたり しましたが、C++ならvectorで動的な追加ができるので C++ならlist(リンクリスト)を使う場面は少ないかもしれません。 あとCでハッシュの実装をする場合は、リンクリストはよく使います。 また、ソートに関しては基本的にリンクリストより配列の方が早いと思います。 と言うのも、例えばクイックソートを使うならランダムアクセスが必要になるので そもそもリンクリストでは(クイックソートは)無理です。 ソートする必要があるなら、配列を使うべきだと思います。 >>関数でfreeするなら、引数でstartを渡してあげればOKです >で、free(start)してみたら、エラーになってしまい、ただ >free(start->next)としたら通りました。 >まぁ、free(start)が通らないのは、僕の理解不足からくる見当違いな事をしてるせい >だと思いますが、free(start->next)としたとき、チェーンで繋がった先のNULLに至るまで >にmalloc()で割り当てたそれぞれのメモリ領域も解放してくれるのかが僕の理解不足の >点です。free(start->next)したとき、next側のメモリだけ解放され、後に続く >NULLまでのmalloc()で取った領域は動かされず、残ったままなら これは私の言葉足らずでしたが、例えば、以下のような関数を作成してやれば OKです(テストしてないですが多分OKだと思います)。 void free_list(list *start) { list *curr, *temp; for (curr = start; curr != NULL;) { temp = curr->next; free(curr); curr = temp; } } で、呼び出し側は、free_list(start)とやれば良いので、 startという変数(の管理)が大事だと言った訳です。 >まだ、ちゃんと理解できてないと自分自身思いますので、まだまだ精進精進だと思って >います。 アルゴリズムとデータ構造は奥が深いですが、このぐらいはまだまだ入門です。 C言語でのアルゴリズムの専門的な本を購入されて読むことをお勧めします。 C++では標準ライブラリで基本的なデータ構造は用意されているのですが、 データ構造の基本的な知識がないときちんとした理解ができないので プログラミングの知識と経験はこつこつと積み上げていくしかないと思っています。 仕事レベルですと、「基本」を押さえておくことが非常に重要になりますし。

すいません。見落としてました。 free(start)はエラーになったということで、 startは、staをさしている訳で、エラーの原因はstaは 動的に確保されたオブジェクトではないからです。 774RRさんがおっしゃっていたようにstaは番兵ですね。 ですので、以下が正解です。 void free_list(list *start) { list *curr, *temp; for (curr = start->next; curr != NULL;) { temp = curr->next; free(curr); curr = temp; } } これで、以下のように呼び出せます。 free_list(start); 先ほどの例だと、以下のように呼び出さないといけません。 free_list(start->next); もしくは、 free_list(sta.next);

> >void free_list(list *start) { > list *curr, *temp; > > for (curr = start->next; curr != NULL;) { > temp = curr->next; > free(curr); > curr = temp; > } >} > >これで、以下のように呼び出せます。 >free_list(start); > >先ほどの例だと、以下のように呼び出さないといけません。 >free_list(start->next); >もしくは、 >free_list(sta.next); なるほど！！ ありがとうございます void free_list(list *start)の内容を見て、なっとくっす。 チェーンをたぐりよせてmalloc()で取った領域を開放を繰り返し NULLが来て、解放終わりって感じですね。 すっごいわかりました。本当にありがとうございました。

>なるほど！！ >ありがとうございます >void free_list(list *start)の内容を見て、なっとくっす。 >チェーンをたぐりよせてmalloc()で取った領域を開放を繰り返し >NULLが来て、解放終わりって感じですね。 >すっごいわかりました。本当にありがとうございました。 void free_list(list *start) { list *curr, *temp; for (curr = start->next; curr != NULL;) { temp = curr->next; free(curr); curr = temp; } start->next = NULL; } あとで気がついたのですが、最後の行 start->next = NULL; という一行も入れておいた方が良いです。 これをしておかないと、freeした後に間違えて staのnextの参照や書き込みを行った場合問題となります。 参照をしたタイミングではオブジェクトはなくても ポインタの値は残っていて(ダングリングポインタと言います) 不正なアクセスとなります。 これは、問題の原因があるところと問題の発生位置 (別のところでアクセスバイオレーションになったりする) がずれる可能性があるため、気づきにくいバグとなります。 ここら辺の知識はポインタ関係ですので、(ぱ)さんの 「C言語ポインタ完全制覇」はかなりお勧めです。 私もこの本に早く出会っていればもっと早くレベルアップ できたのにと思っています。 http://www.amazon.co.jp/exec/obidos/ASIN/4774111422/qid=1141917620/br=3-1/br_lfncs_b_1/249-0186723-6715515

話の腰を折りまくります。 >774RRさんがおっしゃっていたようにstaは番兵ですね。 リンクリストで番兵を使うというのが根底の発想として間違っている気がします。 >startは、staをさしている訳で、エラーの原因はstaは >動的に確保されたオブジェクトではないからです。 御意なのですが、だからといって最初を除外して free するというのも間違いと思う。 tree や環状リストで番兵を使ったりはしません。 １方向リンクリストでも使わないほうが自然でしょう。 もし仮に番兵を配置するならリンクリストの末尾に置くのが適切です。 先頭に置くなら番兵とは呼ばずにダミー要素と呼ぶべき。 そして、仮に番兵/ダミー要素を使うのであれば、その番兵/ダミーも malloc() でとっておくべきです。 [813] で書いたとおり auto な番兵/ダミーを用意するのは大きな間違いです。 マルチプルインスタンスを実現しようとして list* root1=create_list(...); list* root2=create_list(...); 等と直したくなった場合に破綻します。 んで、この程度の話は [813] で紹介した先にて述べられ済みなのですけど。

話の腰を揉んでみるテスト。ふにふに >リンクリストは、要素(サンプルの場合、list)を削除する処理が >配列に比べて早いというのが一般的に言われています。 リストを使う理由としては、配列だと削除された要素の後ろの要素を指すイテレータの扱いに困る、というのもありますね。 STLではそういうイテレータは無効になります。 >また、ソートに関しては基本的にリンクリストより配列の方が早いと思います。 >と言うのも、例えばクイックソートを使うならランダムアクセスが必要になるので >そもそもリンクリストでは(クイックソートは)無理です。 クイックソートは、アルゴリズムそのものにはランダムアクセスは不要です。 ただ、ピボットを選ぶときにランダムアクセスできないとワーストケースに対応できないので、その意味では配列の方が良いと言えるかもしれません。 実装はリンクリストの方がむしろ簡単だと思います。 void quick_sort(Node ** head_p) { if (*head_p != NULL && (*head_p)->next != NULL) { Node *p; Node *left = NULL, *right = NULL; Node **left_p = &left, **right_p = &right; for (p = (*head_p)->next; p != NULL; p = p->next) { if (p->value < (*head_p)->value) { *left_p = p; left_p = &(*left_p)->next; } else { *right_p = p; right_p = &(*right_p)->next; } } *left_p = *right_p = NULL; quick_sort(&left); quick_sort(&right); for (; *left_p != NULL; left_p = &(*left_p)->next) ; *left_p = *head_p, (*head_p)->next = right; *head_p = left; } } ＃ いや、ループが1重で済んでるし＜簡単

>>startは、staをさしている訳で、エラーの原因はstaは >>動的に確保されたオブジェクトではないからです。 >御意なのですが、だからといって最初を除外して free するというのも間違いと思う。 間違いではないと思います(逆に正解だとも言えません)。 ある意味どっちでも良いと思います。 サンプルの例ではauto変数であるstaがリンクリストの先頭な訳で、 これをそのまま(あるいはアドレスを)渡した方が分かりやすいと思った訳です。 free_list(sta.next);やfree_list(start->next);は分かりにくい気がします。 何でリンクリストの先頭(あるいはリンクリストそのものを表すもの)を 渡さないで、nextの要素を渡さないといけないのかという気がします。 確かに関数の汎用性を考えれば最初を除外するのは良くないと思います。 しかし、そういう次元の議論ではありません。 また、そもそもマルチプルインスタンスを考えた実装にはなっていないので マルチプルインスタンスに対応しようとすると破綻するのはしょうがないと 思います。 私ならlist(は名前を変えたい)の上にラッパーの構造体 (仮にllistとしましょう)を作成し、その中にlistの先頭を入れてあげます。 こうすれば、llistの中にダミーのstaも持たせることできますし、 どうにでも実装できます。free用の関数も以下で問題ないです。 free_llist(llist *head); マルチプルインスタンスだって当然できます。 問題は、どこまで実装を抽象化するかであり、今の負け組一号さんの 実装を踏襲するならば774RRさんのご指摘通り、問題点は多いです。 >リンクリストで番兵を使うというのが根底の発想として間違っている気がします。 また、これも間違っているとは断言できないと思います。 あくまで実装の問題で、実装を分かりやすくするために 番兵を入れるのであって、番兵を使うのが間違いではないと思います。 但し、負け組一号さんの番兵(ダミー？)の使い方が適切だとは 私も思っていません。

>クイックソートは、アルゴリズムそのものにはランダムアクセスは不要です。 >ただ、ピボットを選ぶときにランダムアクセスできないとワーストケースに対応できないので、その意味では配列の方が良いと言えるかもしれません。 >実装はリンクリストの方がむしろ簡単だと思います。 クイックソートがリンクリストで実装できるのは知りませんでしたが、 私はNykRさんの実装が難しくて理解できませんでした (いやみではありません。能力的な問題です)。 STLのsort()はランダムアクセスイテレータが必要ですが、 私のイメージは、listはクイックソートに対して、 実行効率の面で現実的ではないからできないのだと思っています。 実装が簡単だというのも重要だと思いますが、 (STLは)ライブラリなのであくまでもパフォーマンスが問題で、 やはりリンクリストでは配列と同等のパフォーマンスが でないのではないでしょうか？ NykRさんのサンプルの計算量はいまいち良く分かりませんでした。 クイックソートのアルゴリズムにランダムアクセスがなくても 実装可能だと言うのは了解しました。

勘違いがあったので訂正します。 >>ただ、ピボットを選ぶときにランダムアクセスできないとワーストケースに対応できないので、その意味では配列の方が良いと言えるかもしれません。 ピボットを選ぶのは関数呼び出し1回につき1度だけなので、頭から順にアクセスしていってもオーダーは変わりませんね。 という訳で「ワーストケースに対応できない」というのはこの意味では嘘でした。 >>実装はリンクリストの方がむしろ簡単だと思います。 > >クイックソートがリンクリストで実装できるのは知りませんでしたが、 >私はNykRさんの実装が難しくて理解できませんでした う、確かに難しかったかも知れません(書くのはともかく読むのは)。 　1.最初の要素をピボットにして、 　　残りの部分をピボット未満の要素のリスト(left)とピボット以上の要素のリスト(right)に分割する 　2.それぞれをソートする 　3.leftと最初の要素とrightをこの順に繋げる ということをやっています。 ＃ それぞれを関数化すべきでしたね。 ＃ ちなみに簡単だと思った理由は(ループが1重は冗談として)分割した後の領域の境界について考える必要がないからです >STLのsort()はランダムアクセスイテレータが必要ですが、 >私のイメージは、listはクイックソートに対して、 >実行効率の面で現実的ではないからできないのだと思っています。 >実装が簡単だというのも重要だと思いますが、 >(STLは)ライブラリなのであくまでもパフォーマンスが問題で、 >やはりリンクリストでは配列と同等のパフォーマンスが >でないのではないでしょうか？ まあ、クイックソートは最悪の場合 O(n^2) になってしまうわけで、 ランダムアクセスできないとどうしても、 それを避けるために書いたコードのせいで定数項が大きくなってしまいそうです。 ＃ gccのSTLの実装ではランダムアクセスイテレータにしかできないことばっかりやってたり リンクリストの場合はデータ構造を直接いじってマージソートしてしまった方が速いでしょうしね(std::listは実際にそうなっていますが)。 ＃ ちなみに上で説明した方法もデータ構造を直接いじっています ＃ ですから、std::sortでは同じことは出来ません >NykRさんのサンプルの計算量はいまいち良く分かりませんでした。 平均(のオーダー)は O(n log n) ですが最悪だと O(n^2)です。 ＃ リストの最も簡単で速いソート方法は配列にコピーしてqso(略

>う、確かに難しかったかも知れません(書くのはともかく読むのは)。 > >　1.最初の要素をピボットにして、 >　　残りの部分をピボット未満の要素のリスト(left)とピボット以上の要素のリスト(right)に分割する >　2.それぞれをソートする >　3.leftと最初の要素とrightをこの順に繋げる > >ということをやっています。 >＃ それぞれを関数化すべきでしたね。 >＃ ちなみに簡単だと思った理由は(ループが1重は冗談として)分割した後の領域の境界について考える必要がないからです 解説ありがとうございます。 簡単かどうかは置いといて、結局やっていることは アルゴリズム的には、配列と同様なことをやっているようですね。 但し、配列とリンクリストは要素へのアクセス方法(の実装)は 違いますが。 >まあ、クイックソートは最悪の場合 O(n^2) になってしまうわけで、 >ランダムアクセスできないとどうしても、 >それを避けるために書いたコードのせいで定数項が大きくなってしまいそうです。 >＃ gccのSTLの実装ではランダムアクセスイテレータにしかできないことばっかりやってたり > >リンクリストの場合はデータ構造を直接いじってマージソートしてしまった方が速いでしょうしね(std::listは実際にそうなっていますが)。 確かに、std::listは、ソート用の自前のメンバ関数を持っていましたね。 >＃ ちなみに上で説明した方法もデータ構造を直接いじっています >＃ ですから、std::sortでは同じことは出来ません > > >>NykRさんのサンプルの計算量はいまいち良く分かりませんでした。 > >平均(のオーダー)は O(n log n) ですが最悪だと O(n^2)です。 結局、std::listで、std::sortが使えないのは、実装がstd::listだけ 特殊扱いになってしまうのでできないということですね。 containerによって場合分けするなら、配列と同様な計算量で 実装できるから問題ない訳で、std::sortは、 汎用的な実装をしているというだけですね。 汎用的と言っても、配列(系)の実装を想定しているだけだと思いますが。 >＃ リストの最も簡単で速いソート方法は配列にコピーしてqso(略 配列へのコピー時間はなしにしても、list#sortよりも早いのですか？ qsoってqsort()のことですか？

>>＃ リストの最も簡単で速いソート方法は配列にコピーしてqso(略 > >配列へのコピー時間はなしにしても、list#sortよりも早いのですか？ >qsoってqsort()のことですか？ listのsortとアルゴリズムのsortやqsortなら後者の方が速いような気がしますが(気がするだけですが)、 その話ではないのです。紛らわしくてすみません。 連結リストを自分で実装した場合の話です。 ↓の最後の方法のことを言いたかったのです。 http://www.kouno.jp/home/c_faq/c13.html#10

>自分自身、リストの有用性自体をはっきりわかってないと思っています。 　crowbarのcrowbar.hを見ると、連結リストをかなり使っていますね。 http://kmaebashi.com/programmer/devlang/crowbar_src_0_4/S/6.html 　動的に追加される要素は、ランダムアクセスの必要がない限り、たいてい連結リストにしている、という感じです。 　途中への追加とかがなくても連結リストを使っているのは、単にrealloc()で配列を伸ばすのが面倒だとか、型Tの配列をrealloc()で伸ばすとTのポインタが変わってしまって誰かが指していたときに困るとか(Tへのポインタの配列にすればいいんだけど)、create.cでの解析木の構築はrealloc()できないMEM_storage_malloc()を使っているとか、事情はいろいろありますが、単なる私の「癖」のような気もしないでもないです。

>先頭に置くなら番兵とは呼ばずにダミー要素と呼ぶべき。 　私自身そう呼びますが(センス･オブ～ではダミーノードと呼んでいた)、774RRさん自身が「それとも最初に作ってる sta は番兵？」と書いておられるので、先頭のダミーノードを番兵と呼ぶ文化圏というのもありなのかなあ、と私は解釈しましたが。 >１方向リンクリストでも使わないほうが自然でしょう。 　私もそう思いますが、「センス・オブ～」でそう書いたところ査読してくださった方からの反論があり、多少表現を変更した、という経緯も (^^;

>listのsortとアルゴリズムのsortやqsortなら後者の方が速いような気がしますが(気がするだけですが)、 >その話ではないのです。紛らわしくてすみません。 >連結リストを自分で実装した場合の話です。 > >↓の最後の方法のことを言いたかったのです。 >http://www.kouno.jp/home/c_faq/c13.html#10 了解しました。 ありがとうございました。

>　私もそう思いますが、「センス・オブ～」でそう書いたところ査読して > くださった方からの反論があり、多少表現を変更した、という経緯も (^^; (^^; Cで単方向リストを書く場合、私も先頭のダミー要素は使いません。 リンクポインタへのポインタを使えば、不要になるからです。 でも、Lisp 文化圏あたりでは、ダミー要素も割と当たり前に使うんじゃ ないでしょうか？ というか、C と C++ 以外の（リンクポインタへの ポインタを使えない) 言語では、わりと使うことが多いような。 あと私は、Cでも双方向リストを書く場合には、ほとんどの場合、環状にして ダミー要素を使います。結構そういう人は多いと思うんですけど、そうでも ないですかねえ。 試しに Java の標準ライブラリ jdk-1_5_0-src-scsl/j2se/src/share/classes/java/util/LinkedList.java を確認してみましたが、やはりダミー要素を使っているようですよ。