リストや木についての質問

質問

リストや木等のデータ構造（？）は

ポインタのつなぎ方みたいな物なのでしょうか？？

それとも、それには何か特別な関数（メモリー確保を除く）が必要なのでしょうか？？

回答No.4

KoHal · ベストアンサー

質問に対する直截な回答ではありませんが。

「ポインタのつなぎ方」という理解も正しいのですが、より重要なのはどのような目的のためにそのような「ポインタのつなぎ方」がなされているかという点です。

リストは項目の追加削除並び替えが簡単に出来るという点がメリットです。
その反面、ランダムアクセスが出来ません。
ｎ番目の項目にアクセスしようとしたら、そのたびに先頭からｎ番目まで１つずつリンクをたどって行く必要があります。
ランダムアクセスが頻繁に起きるプログラムでは到底リストは使えません。
リストはあくまで順次アクセスが基本です。

二分木は「ソートされたリスト」を実現するために使われます。
ソートされているためｎ番目の要素にアクセスするのはリストに比べ遥かに速いです（一番速いのは配列ですが）。
項目の追加削除も速いです。
ただ、ソートが前提ですから、ソート基準が定められないなら使いようがありません。

どのような用途にも使えるデータ構造は存在しませんから、用途に合わせ最適なデータ構造を選択するのもプログラマの役目です。

なお、C++だと標準ライブラリに一通りのデータ構造が用意されています。市販のライブラリを使わなくても大抵のことは出来ますよ。
ANSI/ISO C++準拠ならフリーのコンパイラでも使えるはずです。

お礼

なるほどｗ

大変参考になる回答をしていただいて

有難う御座いました

回答No.3

hpsk

「データ構造」としてリストや木を説明する場合、
それらの概念と、それを実際にどうやって実現するかというのは分けて考えたほうがいいです。

リストというのは、
「各ノードが自分自身の値と次のノードへの参照を持っており、それらが一列につながったもの」
であり、Cの場合は構造体で実現することが多いだけです。
C言語の配列でも実現しようと思えばできます。

実際、二分木（木の一種）は配列で実現することも多いです。

余計混乱させてしまったらすみません。

お礼

解りやすい説明を有難う御座いました。

かなり参考になりました

回答No.2

yamaichiro

No.1の方のおっしゃる通りです。

特別な関数は必要ありませんが、要素にアクセス
するための関数はいろいろと用意しないと、使い
辛くなります。

例えば、検索とか、N番目の要素とか、先頭から
順にアクセスするための関数などです。

もし、MicrosoftのMFCをお使いでしたら、CObArray
やCObListの仕様などが参考になると思います。

お礼

そうなんですか・・

有難う御座いました

後にコンパイラを購入し（フリーソフトを使っております）

その方法を試みたいと思います

回答No.1

VirtualT2

おっしゃっている内容が、
「線形リスト」「ツリー」構造の事であるなら…

こんな感じです。

回答としては、ポインタの繋ぎ方です。

構造体に
自分の前、自分の後ろ、自分の上、自分の下
と言うカンジにポインタを確保して繋いで行くんです。

例を揚げますと(双方向線形リスト)
typedef struct _tag_NODE {
　_tag_NODE* mae; //自分の前(NULLなら先頭
　_tag_NODE* usiro; // 自分の後ろ(NULLなら末尾
} NODE, *PNODE;

てな、カンジに…

お礼

例を示してくださり有難う御座います

今後のプログラムにも役だてたいと思います