K.Maebashi's BBS 削除ページ

>自分自身、リストの有用性自体をはっきりわかってないと思っています。 >せいぜい「線形リストなら、文字を打ち込んで行ってもチェーンのつなぎ換えで >ソートできて便利だな～」という程度の知識です。 リンクリストは、要素(サンプルの場合、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++では標準ライブラリで基本的なデータ構造は用意されているのですが、 データ構造の基本的な知識がないときちんとした理解ができないので プログラミングの知識と経験はこつこつと積み上げていくしかないと思っています。 仕事レベルですと、「基本」を押さえておくことが非常に重要になりますし。