木構造について(;_;)

[むつみ]

プログラム初心者の学生です！(´；ω；｀)
木構造を用いて、複数の数列を表現したいのですが、いまいちプログラムの書き方が分かりません(;_;)

具体的には、
①１、２、３、５、６、８、１０
②１、３、４、６、７、９、１０
③１、４、５、６、８、９、１０
④１、５、６、９、１０

のような４つの数列を１を根とした木構造で表現したいです！
ソートする必要などはないです。
また、最終的に各数が木に何回含まれたかを数え上げられるようにもしたいです。

実際には各数列に含まれる数は無作為に決められ、数列の数も４つではなく、もっと沢山あります。

どなたか分かる方、教えてください！ヽ(；▽；)ノ

[むつみ]

プログラム初心者の学生です！(´；ω；｀)
木構造を用いて、複数の数列を表現したいのですが、いまいちプログラムの書き方が分かりません(;_;)

具体的には、
①１、２、３、５、６、８、１０
②１、３、４、６、７、９、１０
③１、４、５、６、８、９、１０
④１、５、６、９、１０

のような４つの数列を１を根とした木構造で表現したいです！
ソートする必要などはないです。
また、最終的に各数が木に何回含まれたかを数え上げられるようにもしたいです。

実際には各数列に含まれる数は無作為に決められ、数列の数も４つではなく、もっと沢山あります。
一つの親から３つ以上の子が存在する事もあるので、２分木ではなく、N分木となります。

どなたか分かる方、教えてください！ヽ(；▽；)ノ

[beatle]

木構造というと、節点と辺がある構造というのは知ってますか？
木構造を文字で書くのは結構厳しいのですが、下記のようなルールで書くことにしましょう
(左辺　値　右辺)
例えば、頂点の値が1で、左辺が2、右辺が3であるような木は
(2 1 3)
と書きます。また、頂点の値が1で、左辺には部分木がなく、右辺に「頂点が2で左辺が3で右辺が無い」ような部分木を持つような木は
(NIL 1 (3 2 NIL))
と書きます。

この書き方に習って、1から4を木構造で書いてみて下さい。

[むつみ]

返信ありがとうございます！
接点と辺があることは知っています(#^.^#)

(左辺　頂点　右辺)という構造で書いてしまうと、一つの頂点から三本以上辺が出ている場合はどのように表現すれば良いのでしょうか？
(T ^ T)

例えば
①１、２、４
②１、３、４
③１、４、５
のような場合、１の頂点から２、３、４へ３本の辺が出ることになりますよね？
そこが分かりません(><)

[beatle]

ああ、勝手に2分木だと仮定して話を進めてしまいましたね。
では、こういうルールに改良しましょうか。
「頂点は<>で囲む」
例えば1を頂点として、辺が3本ある木は
((a <b> c) (d e <f> g) <1> h)
と、こんな感じに。

例えば
①１、２、４
②１、３、４
③１、４、５
のような場合、１の頂点から２、３、４へ３本の辺が出ることになりますよね？

「３本の辺が出ることになりますよね？」と言われても僕には理解できませんので、是非今改良した書き方で書き表してみて下さい。

[むつみ]

ごめんなさい(><)
この数列だと初めから分木してしまうので、次のような数列に変えます！
(この数列では二分木になってしまいますが、一つの点から三本以上枝が出ることはあるので、その場合にも対応出来るプログラムを作りたいです。)

①１、２、３、５、６、
②１、２、４、６、７
③１、４、５、８、９
④１、４、５、７、１０

この数列をその書き方で表現すると、

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　((３〈２〉４)　〈１〉　(NIL〈４〉５))
/ \
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　/ \
　　　　　　　　　　　　　　　　　　　　((５〈３〉NIL)　〈２〉　(NIL〈４〉６))　　　　　　　　　((NIL)　〈４〉　(７〈５〉８))
　　　　　 /　 \ \
/ \ \
　　　　　　　　((６〈５〉NIL)　〈３〉　(NIL))　　　　　((NIL)　〈４〉　(NIL〈６〉７))　　　　　　　　　　((NIL〈７〉１０)　〈５〉　(NIL〈８〉９))
/ \ / \
　 / \ / \
　　　(〈６〉　〈５〉　(NIL))　　　　　　　　　　　　　　　　((NIL)　〈６〉　(〈７〉))　　　　　((NIL)　〈７〉　〈１０〉)　　　　　　((NIL)　〈８〉　(〈９〉))
/ \ / \
/ \ / \
　　　　　　(〈６〉)　　　　　　　　　　　　　　　　　　　　　　　　　　(〈７〉)　　　　　　　　　　　(〈１０〉)　　　　　　　　　　　　　　　　　　　(〈９〉)




になると思います！
どおでしょうか？








　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　

[beatle]

レイアウトが崩れまくってて見づらいです。
行間にある / \ とは何を表しているのでしょうか？辺ですか？
しかし辺を書かなくて良い記法を提案したはずですので、辺ではない何か違うものでしょうか。

((３〈２〉４)　〈１〉　(NIL〈４〉５))
だけで一つの木を表せていることに注意してくださいね。
この木は左右に(3 <2> 4)と(NIL <4> 5)という部分木を持ち、根が 1 であるような木を表しています。
辺を図示していませんが、実は根と左右の部分木の間に辺があるのです（当たり前ですが）。

この木を図にすると次のようになります。

コード:

    １
   ／＼
  ２  ４
 ／＼   ＼
３  ４   ５

もし木構造が大きくなりすぎて1行に書くと見づらくなるのでしたら、
(A <1> B)
A = (3 <2> 4)
B = (NIL <4> 5)
などとすればいいですね。（部分木に名前を付けるわけです）

さて、むつみさんの示していただいた図で、数列1～4には合計で20個しか数値が書いてないのに、どうして木構造には38個もの数値が登場するのでしょうか。
これがおそらくミソなので、詳しく教えて下さい。

[むつみ]

辺を表現する為に付けたのですが、ずれてしまっていて逆に見づらかったですね(＞人＜;)
ごめんなさい(＞人＜;)

なぜ数列は20個なのに、下の表現方法だと38個か？
という質問の答えですが、

一括りの括弧の中に数字が沢山あっても、実際そこには点は一つしか無く、
その点に対する接続情報を左右で表現していて、その次の括弧で前回の括弧の左右の点を表現している為表記上、数が重複してしまう為だと思います。

[beatle]

書きなおしてみました
(A <1> B)
A=( ( (6 <5> ) <3> ) <2> ( <4> ( <6> 7) ) )
B=( <4> ( ( <7> 10) <5> ( <8> 9) ) )
頂点に<>を付けるようにするとNILが要らないことに気がついたのでNILは書いていません。
これを見るとむつみさんのやりたいことが分かりました。
4つの数列が木の根から葉までの路に対応しているんですね。
数列の先頭から木に配置していって、要素が重複している間は新しい節点が増えず、初めて要素が異なる場所で路が分岐するようになっていますね。

ここで疑問です。
数列1ではi+1番目の要素を常にi番目の要素の左に配置しようとしていますね。
(A <1> B)
A=( ( (6 <5> ) <3> ) <2> ( <4> ( <6> 7) ) )
B=( <4> ( ( <7> 10) <5> ( <8> 9) ) )

しかし数列2の6, 7の要素は、その親の左がNILなのに、右に配置されています
(A <1> B)
A=( ( (6 <5> ) <3> ) <2> ( <4> ( <6> 7) ) )
B=( <4> ( ( <7> 10) <5> ( <8> 9) ) )
※「4」も右配置ですが、それは左に「3」が配置されているので右にする、と理解できます。

数列3, 4も同じく右側から配置するようになっています。
左右の優先度が異なるのは意図したことでしょうか。プログラムにするときには優先度を固定するほうが楽だと思いますよ。

[beatle]

さて、むつみさんはどのくらいプログラム初心者なのでしょうか。
C言語の基礎は分かるのでしょうか。

この掲示板では課題の丸投げはできませんので、むつみさんの分かる所までのソースコードをお示しください。
その上で、具体的に何処が分からないのか、ご質問ください。
（木構造というデータ構造をどうやってプログラムで表現するか分からない、など）

[むつみ]

回答ありがとうございます(^ ^)

その疑問についてですが、木構造を構築する上で紙に絵を描きながら考えたのですが、その時に根を中心に両側に等しい間隔で木が広がって行く様に絵を描いた為に根より左側の要素は左へ、根より右側の要素は右へ広がっていくようにする為にその様な書き方をしたのですが、確かにプログラム上では統一した方が分かりやすいというのは納得しました(^ ^)


プログラムは授業で基本的な事を習った程度です。
具体的にどこが分からないかというと、今回の例では具体的な数を与えているので一つの点から最大何本の枝が出るか分かるので良いのですが、実際扱っているプログラムは数列がランダムに与えられる為、一つの点から最大何本の枝が出るかはその都度変わってきます。
それをプログラム上でどのように実装すれば良いかという問題が1番の疑問です。


現時点で私が考えている木の作り方は、

まず一つ目の数列が与えられたら連結リストを使って数列を繋ぎます。
そして、二つ目の数列を読み込んだら、根に戻って一つ目の数列と比較していき、一つ目の数列に存在しない要素が出て来たらそこから枝分かれをさせていきます。

これを数列の個数の回数分続けていきます。
言葉では説明出来るのですが、いざプログラムで表すとなると分からなくなってしまいます。

アドバイスなどがあれば、教えて頂けると嬉しいです！

[かずま]

この数列だと初めから分木してしまうので、次のような数列に変えます！
(この数列では二分木になってしまいますが、一つの点から三本以上枝が出ることはあるので、その場合にも対応出来るプログラムを作りたいです。)

①１、２、３、５、６、
②１、２、４、６、７
③１、４、５、８、９
④１、４、５、７、１０

この数列をその書き方で表現すると、

3本以上枝があるのなら次のようにしたほうがいいんじゃないの？

コード:

1
+---2
|   +---3
|   |   +---5
|   |       +---6
|   +---4
|       +---6
|           +---7
+---4
    +---5
        +---8
        |   +---9
        +---7
            +---10

[むつみ]

ありがとうございます(^ ^)

次のようにとは、どのようにするという事でしょうか？
図は理解出来るのですが、三本以上の時にどうするという意味ですか？

[non]

まず一つ目の数列が与えられたら連結リストを使って数列を繋ぎます。
そして、二つ目の数列を読み込んだら、根に戻って一つ目の数列と比較していき、一つ目の数列に存在しない要素が出て来たらそこから枝分かれをさせていきます。

むつみさんのこの考え方を、絵で表したのが、かずまさんの図だと思いますよ。

まず、最初に構造体を定義してみましょう。
ところで、まだ解決じゃないでしょうに。

[beatle]

解決したのでしょうか？解決したらどのように解決したのかを示していただくことになっています。
（以下、解決してない前提で回答を続けます）

まず一つ目の数列が与えられたら連結リストを使って数列を繋ぎます。
そして、二つ目の数列を読み込んだら、根に戻って一つ目の数列と比較していき、一つ目の数列に存在しない要素が出て来たらそこから枝分かれをさせていきます。

なるほど。考え方としてはいいと思います。
連結リストの各要素が木構造の各節点に該当する構造ですね。
木構造を作るには連結リストを各節点に持たせ、部分木のリストとして使用すればOKです。

コード:

struct Element;
struct LinkedList { /* 線形リスト */
    struct Element* head;
};
struct TreeNode;
struct Element { /* 連結リストの要素 */
    struct TreeNode* value;
    struct Element* next;
};
struct TreeNode { /* 木の節点 */
    struct LinkedList children; /* この節点の部分木 */
    int value; /* 節点の値 */
    unsigned int count; /* 値の重複回数 */
};

こんな感じでしょうか。連結リストの実装（連結リストの初期化、要素の追加、要素の削除、要素の取得などの関数）の方法は省略しました。
この構造だと木の左側、右側という概念はなくなってしまいます。もしそれが重要なら
LinkedList leftChildren;
LinkedList rightChildren;
とかにすればいいでしょう。

[むつみ]

詳しい説明ありがとうございます(^ ^)

そのやり方だと、一つの点から三本以上の枝が出た場合にはどのように対処している事になるのでしょうか？
木構造における枝はプログラム上ではポインタに対応すると思うのですが一つの点から任意の個数だけポインタを使う方法が分かりません（ ｉ _ ｉ ）

おそらく、ポインタの意味が充分に理解出来ていない為だと思うのですが。
丁寧に説明してくださっているのにスミマセン（ ｉ _ ｉ ）

[beatle]

辺（枝）が何本であろうとも、節点（TreeNode）の連結リスト「children」に格納することができます。
僕の書いたプログラムではLinkedListが連結リストを表しています。
むつみさん自身が連結リストを使うと仰ったので、連結リストの実装方法をご存知だと思っていたのですが。

[むつみ]

すいません、なんとなくの知識で詳しくは知りません（ ｉ _ ｉ ）
でも本やネットで連結リストの仕組みを調べながら順を追って構築していけば出来るかもしれません！

ちなみに私の場合、読み込んだ数列を元に木を構築するだけなので、要素の削除は無いのではないかと考えているのですが、この認識は正しいでしょうか？

[むつみ]

それと、beatleさんが最後に書いて下さっていたcountという変数ですが、これは各数が木構造の中で何回用いられるかを数える為のものですよね？

この変数を用いて数を数える場合はどのようにインクリメントしていけば良いのでしょうか？

[beatle]

ええと、僕のおすすめのやり方は、まず連結リスト（とそのテストプログラム）だけを作ることです。
木構造はまだ考えないで、とにかく連結リストだけを作ります。
その際、malloc / freeの知識、構造体の知識など、幅広い知識が要求されるはずですので、連結リストの実装が終わる頃にはプログラミングの感覚が大分つかめるでしょう。

そうしたら、いよいよ木構造をやります。
連結リストの実装で培った経験があるので、それなりにプログラムしやすくなっていると思います。

この変数を用いて数を数える場合はどのようにインクリメントしていけば良いのでしょうか？

木構造に数列の要素を追加しようとしたけど、すでに木構造にその要素が有った、というときにインクリメントします。
また、新しく木構造に節点を追加したときに、その節点のcountを1に初期化します。

[むつみ]

なるほど、非常に分かりやすい説明ありがとうございます！(^ ^)
それでは私はまずは初めの数列をリストで表現することだけを考えれば良いという事ですよね？

それと、連結リストのテストプログラムとはランダムに数列を生成する本体のプログラムの事でしょうか？(^ ^)

それではインクリメントする際に配列を用意したりする必要はないという事ですか？(^ ^)

[beatle]

連結リストのプログラムは今のむつみさんのやりたいことと完全に切り離してもまったく問題ありません。
というより、いっそ切り離して、汎用的な連結リストの作り方を学んだほうが良いと思います。
例えば、何か独自に定義した構造体を要素とするような連結リストを作るとか。

テストプログラムというのは、作った連結リストのプログラムがきちんと動いているかを確認するためのプログラムのことです。
テストプログラムがランダムな動作をしてしまうと、結果が正しいかを判定し難いので、テストプログラムは確定的な動作をするようにします。
例えば、連結リストを生成するテストプログラム、生成した連結リストに5つの要素を追加するテストプログラム、5つの要素を追加したのち中間の要素を削除するテストプログラムなどです。

もちろん、「連結リストを生成するテストプログラム」では「本当に正しく生成できたか」を確認し、
「生成した連結リストに5つの要素を追加するテストプログラム」では「本当に5つの要素が正しく格納されているか」を確認します。
（生成しっぱなし、追加しっぱなしはダメってことです。それだとテストになりません）

とにかく、作った連結リストの機能が一通りきちんと完成しているかを確認できるプログラムを作ります。

[beatle]

ちなみに確認したいのですが、これは学校の課題かなにかでしょうか？期限があるものでしょうか？
もし期限が1週間くらいなら相当頑張らないと完成しないと思いますよ。

[むつみ]

分かりました、それでは連結リストを作るところからまず始めたいと思います！
作り終えたら確認してもらっても宜しいでしょうか？(＞人＜;)

課題のようなものです(＞人＜;)
なので、なるべく早く作ります！

[beatle]

作り終えたら確認してもらっても宜しいでしょうか？(＞人＜;)

はい、いいですよ。作り途中でも疑問があれば是非。
その時ちょうど僕が居るかは分かりませんが、質問の仕方を間違えなければみなさん丁寧に回答してくれるはずです。

質問する際には、このスレッドではなくて新規にスレッドを建てたほうが良いと思います。
もちろん、新スレッドにこのスレッドへのURLは記載してくださいね。
※スレッドのタイトルに顔文字などは入れないほうが良いと思いますし、もう少し具体的なタイトルの方がいいでしょうね。

連結リストは「線形リスト」や「リンクリスト」などとも呼びますので、検索の参考にしてください。
以下、連結リストについて参考になりそうなウェブページを書いておきます。
連結リスト - Wikipedia 図入りで連結リストが解説されています。
アルゴリズムとデータ構造編　第１０章　線形リスト C言語による連結リストの実装が書いてあります。

[フリオ]

(この数列では二分木になってしまいますが、一つの点から三本以上枝が出ることはあるので、その場合にも対応出来るプログラムを作りたいです。)

①１、２、３、５、６、
②１、２、４、６、７
③１、４、５、８、９
④１、４、５、７、１０

分岐の数に関係なく2分木で表現できるんじゃないでしょうか。

コード:

	1 - 2 - 3 - 5 - 6 - N
	|   |   |   |   |
	N   |   |   N   N
	    |   |
	    |   4 - 6 - 7 - N
	    |   |   |   |
	    |   N   N   N
	    |
	    4 - 5 - 8 - 9 - N
	    |   |   |   |
	    N   N   |   N
	            |
	            7 -10 - N
	            |   |
	            N   N

[むつみ]

beatleさん

ありがとうございます(^ ^)
なるべく早くプログラムを考えて載せます！

[むつみ]

フリオさん

確かに任意の多分木は二分木で表現出来るという話は聞いた事があるのですが、いまいち意味が分かりません（ ｉ _ ｉ ）

フリオさんが書いてくださった構造だと、1からつながっている点は2だけですよね？
でも実際は1には4もつながっているので、その書き方だと表現出来ていないように思えます。
もし、そうでないなら詳しく教えて頂けたら嬉しいです(^ ^)

[たいちう]

図の右向きの線は長男を、下向きの線は次弟を表します。
１からは２にしか線がありませんが、４は２の弟なので、１の子供は２と４です。
１の子供が３人いる場合は、４の次弟として追加します。

このルールによって、各ノードからは2本しか線がなくても、多分木を表現できます。
詳しくは「長子次弟構造」について調べて下さい。

[むつみ]

たいちうさん

なるほど、それでも出来そうですね(^ ^)
その場合、リストは片方向のみのリスト構造で実現出来ますか？
それとも双方向連結リストを使わなくてはいけないのでしょうか？

[たいちう]

フリオさんや私が紹介している方法では、リストは使いません。
二分木の応用です。

乱暴に言えば、リスト → 二分木 → 多分木の順に難しくなります。
beatleさんのアドバイス通り、まずはリストを作るのが先だと思います。
今まで書かれている範囲だと、むつみさんの作りたい物に双方向リストは必要ないでしょう。

[beatle]

2分木にするなら連結リストは使いませんよ。
各節点が「左の部分木へのポインタ」と「右の部分木へのポインタ」を持つだけです。
多分木の時は「部分木へのポインタのリスト」を持つようにして、このリストの実現に連結リストを使うんです。

[たいちう]

> 2分木にするなら連結リストは使いませんよ。

一応書いておきますが、リストを作れない人が二分木を作れるとも思えません。
ましてや二分木の応用的な使い方である長子次弟構造は。
そのような理由で、まず単純なリストを実装し、次に二分木を実装した後、
多分木に拡張するなり、長子次弟構造にするなり考えればよいと思います。

[むつみ]

それだは私が分かる範囲でのリストを書いてみます。

まず、点の番号と次のノードの情報を格納するする為に構造体を宣言します。

typedef struct tagLISTCELL{
struct tagLISTCELL *next;
int data;
}LISTCELL

LISTCELL Head={NULL,0};


//リストの初期化
void List_Init()
{
//NULLが終点なので
Head.next = NULL;
Head.data = 0;
}

//リストを先頭に追加
//param data :リストに入れる値
void List_AddHead(int data)
{



//新しいリストのポインタ
LISTCELL *New = NULL;

//メモリをリストのサイズ分確保
New = (LISTCELL*)malloc(sizeof(LISTCELL));

//確保されている時
if( New != NULL)
{
//リストを連結
//新しいリストのnextにHeadのnextを代入
//これで新しいリストのポインタの設定はOK
New->next = Head.next;

//headの次のポインタを、作成した新しいリストセルにする。
Head.next = New;

//連結が完了したのでデータを代入
New->data = data;

}
}

これで、先頭にノードを追加することが出来ると思います。
つまり、
①１、２、４、５
という数列の１の部分を追加出来たと思います。
次に２を追加する場合がよく分かりません。


補足
私が扱っている数列ですが、次のようなプログラムから来ています。(一部を抜粋しているでけなので、これだけではプログラムとしては成立しないかもしれませんが。)

私が現在扱っているプログラムは、ある組み合わせ回路に信号を送った時に多数あるパスの中で入力から出力までの間で最も時間がかかったパスが通った素子の番号を表示するようなプログラムです。

なので数列というのは、回路の中で最も伝播時間が長かったパス(今後CPと呼びます)が通った点の番号を順番に並べたものです。
この番号とは実際には素子を表します。

最終的に私がしたい事は、CPに含まれる点の番号がそれぞれ何回であったかを調べたいです。一回だけ信号を送ったときは各素子がCPに含まれる回数は高々１回なのですが、この試行を１０万回行うことを想定しているので、その中で各素子が何回含まれるかを知る必要があります。

現在のプログラムでも回数を数え上げることは出来るのですが、配列を用いて数え上げを行っています。(下のプログラムの【あ】の部分で実現)

配列を用いる事の欠点
→１０万回試行を行った際、CPに１回も含まれない素子が沢山存在する。
　　配列表現では、そのような素子に対しても配列を用意しなければいけないので、メモリがもったいない。

これが、今私が木構造を用いて数列を表現したい理由です。
専門的な話をしてしまって申し訳ありません。
少しでも詳しく状況を説明したほうが、アドバイスなど頂きやすいかと思って説明させて頂きました。



while(head != tail){
while(ptr -> startNode != dummySource){
max_ptr=node[ptr ->endNode].latEdge;
if(max_ptr -> next != NULL){
while(max_ptr != NULL){
max_point -> next = (maxPoint *)malloc(sizeof(maxPoint));
(max_point -> next) -> pre = max_point;
max_point = max_point -> next;
max_point -> num = i+1;
max_point -> edge = max_ptr -> edgeNo;
max_point -> pathlist = (unsigned long int *)malloc(600 * sizeof(unsigned long int));
memcpy(max_point -> pathlist,(max_point -> pre) -> pathlist,600);
// max_point -> pathlist = ptr -> endNode;
max_point -> pathlist = max_ptr -> edgeNo;
max_point -> edge = node[edge[max_ptr -> edgeNo].startNode].latEdge -> edgeNo;
max_ptr = max_ptr -> next;
}
tmp = tail;
(tail -> next) -> pre = tail -> pre;
(tail -> pre) -> next = tail -> next;
free(tmp);
tail = max_point;
i = max_point -> num;
ptr = &edge[max_point -> edge];
}
// max_point -> pathlist = ptr -> endNode;
// i++;
max_point -> pathlist = ptr -> num;
i++;
ptr = &edge[node[ptr -> startNode].latEdge -> edgeNo];
}
// max_point -> pathlist = ptr -> endNode;
// i++;
max_point -> pathlist = ptr -> num;
// i++;
// max_point -> pathlist = ptr -> startNode;
// printf("%ld",max_point -> pathlist);

【あ】 for(i=i;i>0;i--){
printf("%ld\t",max_point -> pathlist);
k=max_point -> pathlist;
frequency[k]=frequency[k]+1;
}
printf("%ld\n",max_point -> pathlist[0]);
k=max_point -> pathlist[0];
frequency[k]=frequency[k]+1;

tail = tail -> pre;
free(max_point);
max_point = tail;
i = tail -> num;
ptr = &edge[tail -> edge];
}

[むつみ]

私が扱う数列は最後尾へノードを追加していく必要があるので、
ノードを追加する際は常に着目しているノードが最後尾でなければいけないと思います。
それの仕方がよく分かりません。

[たいちう]

コードを貼り付けるときはタグを使ってください。
それと、コンパイル・実行できる最小限のものにしてくれると、
回答者の手間が減り、回答が得られやすいでしょう。
私は現段階ではソースコードを読む気になれず、具体的な回答はできません。
ただ、方針に間違いがある可能性がありますので、前提を確認させてください。


> CPに含まれる点の番号がそれぞれ何回であったかを調べたいです。

以下の入力に対して、それぞれの数字は何回と数えるのですか？

> ①１、２、３、５、６、
> ②１、２、４、６、７
> ③１、４、５、８、９
> ④１、４、５、７、１０

１は4回？1回？
２は2回？1回？
４は3回？2回？1回？

数え方によってはツリー構造にする必要がなかったり、
ツリー構造では実装に不向きだったりします。


> 配列表現では、そのような素子に対しても配列を用意しなければいけないので、
> メモリがもったいない。

素子の総数は最大でどの程度でしょうか？
仮に素子の総数が100万個で、1個当たり4バイトの整数型で数える場合、4MBのメモリが必要です。
今時のパソコンならば、全く気にしないで良い大きさです。
（スタックから取ろうとすると問題かもしれないが、データ構造を変えないでも対応可能）

データ構造の練習の為ならば止めませんが、本当に配列では不可能ですか？

[むつみ]

やっぱり見づらかったですよね、ごめんなさい！



以下の入力に対して、それぞれの数字は何回と数えるのですか？

> ①１、２、３、５、６、
> ②１、２、４、６、７
> ③１、４、５、８、９
> ④１、４、５、７、１０

１は4回？1回？　　　　　→４回
２は2回？1回？　　　　　→２回
４は3回？2回？1回？　→２回と数えます。

数え方によってはツリー構造にする必要がなかったり、
ツリー構造では実装に不向きだったりします。




> 配列表現では、そのような素子に対しても配列を用意しなければいけないので、
> メモリがもったいない。

素子の総数は最大でどの程度でしょうか？

仮に素子の総数が100万個で、1個当たり4バイトの整数型で数える場合、4MBのメモリが必要です。
今時のパソコンならば、全く気にしないで良い大きさです。
（スタックから取ろうとすると問題かもしれないが、データ構造を変えないでも対応可能）

データ構造の練習の為ならば止めませんが、本当に配列では不可能ですか？



→今試行している回路の中では最大のものでも１００万個は無いのですが、１００万個を超える回路にも対応出来るようなプロ　　グラムを作るという意味なのかもしれません。

あと、実行時間の違いも検討要因になっています。
　
例えば、１００万個の素子を持つ回路を扱う場合、配列だと１００万個の配列を用意する事になり、
　木構造だとCPに含まれる素子の数だけノードを用意する事になると思うのですが、
　もしCPに含まれる素子の数が１０分の１の１０万個だった場合、実行時間にはどのくらいの差が出るのでしょうか？

スタックはどのくらいの容量があるのですか？
また、スタックから取ってこない場合はどこから取ってきているのですか？
どっちから取ってくるかは決められるのですか？

[たいちう]

> １は4回？1回？　　　　　→４回
> ２は2回？1回？　　　　　→２回
> ４は3回？2回？1回？　→２回と数えます。

法則が判りません。間違ってないですか？
それとも、まだ説明していないルールがあるとか？
最低限のルールが判らないと、データ構造を選択できません。


> １００万個を超える回路にも対応出来るようなプログラムを作るという意味なのかもしれません。

課題にはツリー構造を使う、という制約があるということですか？
やはりプログラム作成の前提が判りません。


> もしCPに含まれる素子の数が１０分の１の１０万個だった場合、
> 実行時間にはどのくらいの差が出るのでしょうか？

これはプログラムの作り方やコンパイラや実行環境によりますので、
一概に言えません。配列の方が早い場合も十分考えられます。
100万個分の領域を最初に１回で取得するよりも、
１個分の領域を10万回取得する方が多分遅いでしょう。


> スタックはどのくらいの容量があるのですか？
> また、スタックから取ってこない場合はどこから取ってきているのですか？
> どっちから取ってくるかは決められるのですか？

環境依存です。むつみさんのお使いのコンパイラの設定によります。
ちなみに私の使っているVC++2008 EEでは1MBがデフォルト設定のようです。
1MBで足りない場合、スタックサイズを増やしたり、
mallocで領域を取得したりすることで対処できます。


実行時間やスタックサイズについての質問にも、一応回答しましたが、
話の本題ではないと思います。
少なくとも、もう少しプログラム作成の前提が判ってからです。

現段階で効率や拡張性の事まであれもこれも考えて、
完璧なプログラムを作り始めることは難しいですよ。
試作を繰り返してプログラムを良くしていってください。

[むつみ]

> ①１、２、３、５、６、
> ②１、２、４、６、７
> ③１、４、５、８、９
> ④１、４、５、７、１０

ごめんなさい、間違っていました！
１→４回
２→２回
３→１回
４→３回
５→３回
というふうになります。

[たいちう]

> ①１、２、３、５、６、
> ②１、２、４、６、７
> ③１、４、５、８、９
> ④１、４、５、７、１０

↑のような入力に対して、

> １→４回
> ２→２回
> ３→１回
> ４→３回
> ５→３回

↑のような出力をしたいだけならば、木構造は不要です。
配列を使ったプログラムは完成しているとのことですが、
それでどのような問題があるのでしょうか？

問題点が明確でないまま、スレが進んでしまっていますので、
話が噛み合わなくなっていると思います。
改めて、何が問題なのかを明確にしてもらえませんか？

ソースコードを添付する場合は、タグを使う事と回答者が実行できるプログラムを載せて下さい。
効率が問題ならば、現時点での実測時間や処理したデータ量、値の取りうる範囲等、
具体的にお願いします。

[むつみ]

配列を用いる事の問題点を具体的な例をあげて説明させていただきます。

C７５５２(回路の名前)を用いてCPを求めるという試行を１０万回行ったときに各素子が何回CPに含まれるかを調べます。
C７５５２は素子の数が１２２８８本あるので配列を１２２８８個用意します。
そして、CPに含まれた数列の各数と対応する配列の添字の中身をインクリメントしていきます。

例えば、(CP：１、３、５)という数列が与えられたら、hairetu[1],hairetu[3],hairetu[5]の中身を＋１します。
これを１０万回繰り返します。

しかし、１０万回の試行してみると１回以上CPに含まれた素子は１２２８８個中６７７個しかありません。
つまり、残りの１１６１１個の配列の中身は０のままです。

私が知りたいのはCPに１回以上含まれた素子がどれかという事だけですので、この１１６１１個の配列が無駄といえます。
これが問題点です。

[たいちう]

> 私が知りたいのはCPに１回以上含まれた素子がどれかという事だけですので、
> この１１６１１個の配列が無駄といえます。
> これが問題点です。

無駄があって何が困るのでしょうか？問題点とは思えません。
今書かれている前提だと、要素数12288の配列を用意するのが最もプログラムが単純です。
CPに含まれた回数を数える機能については、実行時間的にも最も早いでしょう。
木構造を導入する方が、よほど無駄と思います。


というのが、私の感想なのですが、練習の為や、本人の美意識の為に、
別の実装をしたいというならば、お手伝いします。
まず、C++が使える場合、多分一瞬で解決します。

【案１】
配列の替わりに、std::mapを使えばやりたいことができるでしょう。
C++を禁止するような制約がないならば、mapの部分だけでもC++に変更すれば解決です。
お使いのコンパイラは何ですか？大抵のCコンパイラがC++を扱えると聞いたことがあります。


以下はC言語しか使ってはいけない場合です。

【案２】
10万回の試行が終わってから、結果を別の配列にまとめるのはどうでしょうか？
試行が終わってから一回以上CPに含まれた素子数を数え、その数の配列をmallocで2つ作ります。
配列は素子IDと出現数用です。元の配列を探索し、0でなければ新しい配列にコピーします。

【案３】
単純なリストで素子の出現数を数えます。
数列『①１、２、３、５、６』を処理した後のリストの形は、次のようになります。

root -> (1, 1) -> (2, 1) -> (3, 1) -> (5, 1) -> (6, 1) -> null

その次に数列『②１、２、４、６、７』を処理すると、次のようになります。

root -> (1, 2) -> (2, 2) -> (3, 1) -> (5, 1) -> (6, 2) -> (4, 1) -> (7, 1) -> null

rootから順に素子IDを探し、見つかればインクリメント、見つからなければ末尾に追加です。


【案３】などは、配列で済むところをわざわざリストを使っている、という点で
私の感覚では無駄なものです。配列に比べて処理も遅いでしょう。
【案３】を発展させて処理を軽くすることもできますが、配列よりも軽くはなりません。

[むつみ]

沢山のアドバイスありがとうございます！
【案２】についてですが、【元の配列】とは回数が０回の素子の分の配列も用意してある配列の事ですよね？
その中から１回以上含まれた素子の番号と回数を、新しく作っ二つの配列にコピーした後に【元の配列】をフリーさせて無駄な配列を無くすといった考え方で正しいでしょうか？

[むつみ]

コンパイラはcygwinをつかっています！

[たいちう]

> 沢山のアドバイスありがとうございます！
> 【案２】についてですが、【元の配列】とは回数が０回の素子の分の配列も用意してある配列の事ですよね？
> その中から１回以上含まれた素子の番号と回数を、新しく作っ二つの配列にコピーした後に【元の配列】をフリーさせて無駄な配列を無くすといった考え方で正しいでしょうか？

その通りです。

[むつみ]

ありがとうございます。

今日大学の教授と話してきたのですが、各素子が何回CPに含まれたかだけでなく、試行回数の中でCP自体が何回使われたかを調べて欲しいと言われました。

つまり、

①１、２、４、５、８←同じ
②１、２、３、６、９
③１、２、４、５、８←同じ
④１、３、５、７、８
⑤１、３、６、７、８
⑥１、４、５、６、９

６回試行を行った時に上のような６個のCPが検出されたときに、
１、２、４、５、８→２回
１、２、３、６、９→１回
１、３、５、７、８→１回
１、３、６、７、８→１回
１、４、５、６、９→１回

というようにパス自体を数え上げるようにしてもらいたいそうです。
この場合、やはり木構造を構築しなければならないのでしょうか？

[たいちう]

> この場合、やはり木構造を構築しなければならないのでしょうか？

必須ではないでしょう。色々やり方があります。
しかし、多分木を使った実装が最も素直な実装だと思います。

[beatle]

あ、プログラムの勉強というより、もしかして実用のツールを作るという目的なのでしょうか。
いままで僕は、むつみさんはプログラムの勉強のために課題設定をしているのだと思っていました。
もちろん連結リストや木構造くらいぱぱっと書けるくらいの力を付けるに越したことはありませんが、その勉強のコストをかける価値があるのか考えるべきだと思います。

例えば、むつみさんは将来プログラマを目指しているわけではなくて、しかしプログラムが少しでも出来る人が研究室内にむつみさんしか居ないためツール作成依頼が来ているなら、
プログラミング力を磨くより、既成の連結リストや木構造などのライブラリを使ってパパっと完成させるほうが良いと思います。
既成のライブラリを使えばバグも減らせますし。
そうではなく、むつみさんがプログラマへの道を目指しているとかプログラミング力を鍛えたいとお思いなら、今までの方針を維持し、勉強したら良いと思います。

というようにパス自体を数え上げるようにしてもらいたいそうです。
この場合、やはり木構造を構築しなければならないのでしょうか？

連結リストだとこんな感じでしょうか。
単に「数列を保存するための連結リストとカウンタ変数」を値とした連結リストを書くだけです。

コード:

struct CPLinkedList; // CPの数列を表すための連結リスト
struct CPCountLinkedListElement { // CP重複カウント用連結リストの要素
    struct CPLinkedList* cp;
    unsigned int count;
    struct CPCountLinkedListElement* next;
};
struct CPCountLinkedList {// CP重複カウント用連結リスト
    struct CPCountLinkedListElement* head;
};

[たいちう]

C++ならば、数字をスペースで区切った文字列をキーにして、
std::mapを使うのが最も簡単な実装じゃないかな。

[たいちう]

> C++ならば、数字をスペースで区切った文字列をキーにして、
> std::mapを使うのが最も簡単な実装じゃないかな。

コード:

#include <iostream>
#include <sstream>
#include <vector>
#include <map>
#include <string>

using namespace std;

void check(map<string, int>& buf, int* data) {
	stringstream ss;
	while (*data)
		ss << *data++ << ' ';
	string key = ss.str();
	key = key.substr(0, key.size() - 1);
	buf[key]++;
}

int main() {
	int data[][128] = {
		{ 1, 2, 4, 5, 8 },
		{ 1, 2, 3, 6, 9 },
		{ 1, 2, 4, 5, 8 },
		{ 1, 3, 5, 7, 8 },
		{ 1, 3, 6, 7, 8 },
		{ 1, 4, 5, 6, 9 },
	};

	map<string, int> buf;
	for (int i = 0; i < sizeof(data) / sizeof(data[0]); i++)
		check(buf, data[i]);

	for (map<string, int>::const_iterator it = buf.begin(); it != buf.end(); it++)
		cout << it->first << " : " << it->second << endl;

	return 0;
}

大体こんな感じです。
cygwinならばg++でコンパイルできるそうですが、私は使ったことがありません。

[むつみ]

以前木構造の質問に対応してくださった方々、質問をしておきながら長い間放置してしまってすいませんでした。
ここ数カ月、病気を患ってしまいこの課題に手をつけることができませんでした。
ですが、体調も回復してきたので改めて木構造(多分木)を構築するという課題に取り組みたいと思います。

言語に関してなんですが、c++ではなく、c言語を用いて実装しなければいけません。

今度こそ、なんとかして完成させたいと思っているので、教えて頂ければとおもいます。
よろしくお願いします。