- ベストアンサー
リストや木についての質問
- みんなの回答 (4)
- 専門家の回答
質問者が選んだベストアンサー
質問に対する直截な回答ではありませんが。 「ポインタのつなぎ方」という理解も正しいのですが、より重要なのはどのような目的のためにそのような「ポインタのつなぎ方」がなされているかという点です。 リストは項目の追加削除並び替えが簡単に出来るという点がメリットです。 その反面、ランダムアクセスが出来ません。 n番目の項目にアクセスしようとしたら、そのたびに先頭からn番目まで1つずつリンクをたどって行く必要があります。 ランダムアクセスが頻繁に起きるプログラムでは到底リストは使えません。 リストはあくまで順次アクセスが基本です。 二分木は「ソートされたリスト」を実現するために使われます。 ソートされているためn番目の要素にアクセスするのはリストに比べ遥かに速いです(一番速いのは配列ですが)。 項目の追加削除も速いです。 ただ、ソートが前提ですから、ソート基準が定められないなら使いようがありません。 どのような用途にも使えるデータ構造は存在しませんから、用途に合わせ最適なデータ構造を選択するのもプログラマの役目です。 なお、C++だと標準ライブラリに一通りのデータ構造が用意されています。市販のライブラリを使わなくても大抵のことは出来ますよ。 ANSI/ISO C++準拠ならフリーのコンパイラでも使えるはずです。
その他の回答 (3)
- hpsk
- ベストアンサー率40% (48/119)
「データ構造」としてリストや木を説明する場合、 それらの概念と、それを実際にどうやって実現するかというのは分けて考えたほうがいいです。 リストというのは、 「各ノードが自分自身の値と次のノードへの参照を持っており、それらが一列につながったもの」 であり、Cの場合は構造体で実現することが多いだけです。 C言語の配列でも実現しようと思えばできます。 実際、二分木(木の一種)は配列で実現することも多いです。 余計混乱させてしまったらすみません。
お礼
解りやすい説明を有難う御座いました。 かなり参考になりました
- yamaichiro
- ベストアンサー率31% (77/243)
No.1の方のおっしゃる通りです。 特別な関数は必要ありませんが、要素にアクセス するための関数はいろいろと用意しないと、使い 辛くなります。 例えば、検索とか、N番目の要素とか、先頭から 順にアクセスするための関数などです。 もし、MicrosoftのMFCをお使いでしたら、CObArray やCObListの仕様などが参考になると思います。
お礼
そうなんですか・・ 有難う御座いました 後にコンパイラを購入し(フリーソフトを使っております) その方法を試みたいと思います
- VirtualT2
- ベストアンサー率58% (18/31)
おっしゃっている内容が、 「線形リスト」「ツリー」構造の事であるなら… こんな感じです。 回答としては、ポインタの繋ぎ方です。 構造体に 自分の前、自分の後ろ、自分の上、自分の下 と言うカンジにポインタを確保して繋いで行くんです。 例を揚げますと(双方向線形リスト) typedef struct _tag_NODE { _tag_NODE* mae; //自分の前(NULLなら先頭 _tag_NODE* usiro; // 自分の後ろ(NULLなら末尾 } NODE, *PNODE; てな、カンジに…
お礼
例を示してくださり有難う御座います 今後のプログラムにも役だてたいと思います
関連するQ&A
- 2分木と双方向線形リストを同時に実現する方法
ファイルに書かれている文字列を読み込み, (1)ソートしてファイル出力 (2)読み込んだ順と逆順にファイル出力 というプログラムを作成する場合, (1)は2分木のデータ構造を用いて実現したのですが,2分木のデータ構造をそのまま利用することで逆順に出力させることは可能でしょうか? 私は無理だと思うので,2分木に加えて双方向の線形リストになるようにポインタを設定する必要があると考えているのですが,もっと上手く実現するアルゴリズムはあるでしょうか? アドバイスを頂けるとありがたいです.
- ベストアンサー
- C・C++・C#
- スタック、キュー、リスト、2分木の使い道は?
主な定番データ構造として (1)スタック (2)キュー (3)リスト (4)2分木 これらのデータ構造がありますが、特に「スタック」と「キュー」は一体何に使えるのでしょうか? 「スタック」や「キュー」は使い道が思いつかないのですが、一体何に使えるのですか? データ構造である「スタック」「キュー」「リスト」「2分木」の使い道を教えてください。 よろしくお願いいたします。
- 締切済み
- その他([技術者向] コンピューター)
- C言語のメモリ領域確保
ポインタ変数ををmain関数で宣言し、関数test()にて必要分だけ領域確保してそのアドレスをmain関数のポインタ変数に渡して利用することは可能でしょうか。 (サイズのわからないテキストデータを、十分に大きな配列に入れるのではなく、関数でメモリを動的確保して無駄の無い配列に入れたい等) C言語ではやはり無理で、構造体のリストにするのが一番でしょうか。 初歩的なことで申し訳ありませんがどなたかお願いいたします。
- ベストアンサー
- C・C++・C#
- 単方向リストの解釈
多数のデータが単方向リスト構造で格納されている。このリスト構造には、先頭ポインタとは別に、末尾のデータを指し示す末尾ポインタがある。次の操作のうち、ポインタを参照する回数が最も多いものはどれか。 ア リストの先頭にデータを挿入する。 イ リストの先頭のデータを削除する。 ウ リストの末尾にデータを挿入する。 エ リストの末尾のデータを削除する。 (平成24年度春期 問7) 各選択肢の参照ポインタ数はいくつになるのでしょうか。 解説書によって必要なポインタ参照数が異なっていて、理解できずにいます。 とある解説書では、 ア 2回のポインタの参照が必要 イ 1回のポインタの参照が必要 ウ 2回のポインタの参照が必要 と記述してあり、またある解説書では ア 0回のポインタの参照が必要 イ 2回のポインタの参照が必要 ウ 1回のポインタの参照が必要 エ 3回のポインタの参照が必要 と記述されていました。 先頭から末尾の一つ手前のデータまで順にたどって参照する必要のあるエが一番ポインタを参照する回数が多そうだな、と想像はできるのですが、実際の参照回数までは理解の外です。。 ご教授お願いします。
- 締切済み
- 情報処理技術者
- Linked List(線形リスト)を使ったデータのソート
大学の、Cの課題で、困っています。 どこが違うのか教えていただけたら嬉しいです。 【課題】 1行に1つの数値データを、複数行入力すると、 このデータを1行ずつ読んでいって、それをひとつの構造体として保持し、 数値データの小さい順にリンクされるようなLinked Listとなるようにプログラムを作る。 入力したデータが数値だったら、Linked Listを先頭から巡り、それを挿入すべき場所を見つける。 そしてデータを格納するための構造体の領域をmalloc関数で確保し、そこにデータを入れ、実際にリストに挿入する。 読み込むべき入力データが無くなったら、最後にLinked Listで保持しているデータを1行ずつ書き出してみる。 【変な結果が出るプログラム】 #include<stdio.h> main() { int c, n, *nextp; void *malloc(size_t size); struct listdata{ int i; struct listdata *nextp; }; struct listdata *hajime; struct listdata *pointer; hajime = NULL; while ( ( c = getchar() ) != EOF ){ if ( '0' <= c && c <= '9' ){ n = n * 10 + ( n - '0' ); } pointer = ( struct listdata *) malloc ( sizeof (struct listdata) ); pointer -> i = n; hajime = pointer -> nextp; } printf ( "%d\n", nextp ); pointer = hajime; while ( pointer != NULL ){ printf ( " %d\n", pointer -> i ); pointer = pointer -> nextp; } } よろしくお願いします(>_<)
- ベストアンサー
- C・C++・C#
- C言語 list 構造体配列
どうしてもこの問題がわからないので教えてください! 下記の構造体タグ「seiseki」を使って,表に示すデータをもつ構造体配列「list」を作成する. 関数に構造体配列「list」のアドレスを渡す. 関数で構造体ポインタ「*list」を利用して,一番点 数の高い者(1名限定)を調べ,その名前を表示する. struct seiseki{ char name[30]; int score; name score }; 表 佐藤 80 鈴木 75 田中 95 高橋 90
- 締切済み
- その他(学問・教育)
- プログラミングの質問です
下記の構造体タグ「seiseki」を使って,表に示す データをもつ構造体配列「list」を作成する. 関数に構造体配列「list」のアドレスを渡す. 関数で構造体ポインタ「*list」を利用して,一番点 数の高い者(1名限定)を調べ,その名前を表示する. struct seiseki{ char name[30]; int score; }; name score 佐藤 80 鈴木 75 田中 95 高橋 90
- 締切済み
- C・C++・C#
- 双方向リストのソート方法について。
単刀直入に言いまして、双方向リストのデータを入れ替えるのではなくて、リスト前後を指すポインタの繋ぎ代えをして、ある一定条件に従ったリストへのソートをしたいと思っています。 リスト構造の前後にダミーを置いて……という方法は取りたくなく、出来るだけメモリを節約した方法が知りたいです。 また、そのリスト数は大体20個くらいで、1秒間に大体50~60回くらい呼ばれるモノです。 リストのデータ数は比較的大きい物です。 参考になる書籍とかでも構いませんので、是非とも教えて下さい。
- 締切済み
- C・C++・C#
お礼
なるほどw 大変参考になる回答をしていただいて 有難う御座いました