• ベストアンサー

2分木と双方向線形リストを同時に実現する方法

ファイルに書かれている文字列を読み込み， (1)ソートしてファイル出力 (2)読み込んだ順と逆順にファイル出力 というプログラムを作成する場合， (1)は２分木のデータ構造を用いて実現したのですが，２分木のデータ構造をそのまま利用することで逆順に出力させることは可能でしょうか？ 私は無理だと思うので，２分木に加えて双方向の線形リストになるようにポインタを設定する必要があると考えているのですが，もっと上手く実現するアルゴリズムはあるでしょうか？ アドバイスを頂けるとありがたいです．

noname#95388
noname#95388

質問者が選んだベストアンサー

  • ベストアンサー
  • chie65535
  • ベストアンサー率43% (8522/19371)
回答No.6

＞(1)は２分木のデータ構造を用いて実現したのですが 「２分木」って、もしかして「Binary Tree」かな？ Binary Tree ソートについて http://www13.plala.or.jp/kmaeda/cs/treesort.htm だったとしたら、上記ページで説明されてる構造になってる筈だから、構造体に「１つ前に追加したノードへのポインタ」っていうメンバーを増やして、以下のようにすれば良い。 １．グローバル変数に「最も最近に追加したノードへのポインタ」を増やし、NULLで初期化する。 ２．１行読み込んで、新しいノードを作成したら「１つ前に追加したノードへのポインタ」のメンバーに「最も最近に追加したノードへのポインタ」を代入する。 ３．代入したら「最も最近に追加したノードへのポインタ」に「たった今作成したノードのポインタ」を代入する。 ・ソートしてファイル出力する場合 http://www13.plala.or.jp/kmaeda/cs/treesort.htm の「Print関数」を参照。 ・逆順にファイル出力する場合 すべてをツリーに挿入し終わったら「最も最近に追加したノードへのポインタ」から出力を始めて「１つ前に追加したノードへのポインタ」を辿って行き、NULLになったらやめる。

noname#95388
質問者

お礼

詳細な回答ありがとうございます．ポインタをグローバル変数を用いるのには気づきませんでした．これだと比較的プログラムが複雑にならなそうですね．

その他の回答 (5)

回答No.5

A) 行番号 と B) その一行 とを組にして保持します。 Bをキーにソートすれば(1)が、 Aをキーにソートすれば(2)が得られます。

noname#95388
質問者

お礼

簡潔なアルゴリズムですね．全然思いつきませんでした．こちらでも実装してみたいと思います．

  • asuncion
  • ベストアンサー率33% (2126/6288)
回答No.4

念のため、逆順に出力するだけなら、単方向のリスト構造でじゅうぶんです。 双方向を使う必要性はありません。

noname#95388
質問者

お礼

将来拡張することを考えて，双方向で作ろうと思いました．逆方向へのポインタだけでもいいですが，逆方向をつけるのに比べて順方向をつけるのは容易なので．

  • sakusaker7
  • ベストアンサー率62% (800/1280)
回答No.3

データ構造を生かして、とはあるけど、木のノードの構成をいじったらだめなんでしょうか? 木の本来のポインタとは別に線形リスト用のポインタを持たせておいて ノードの生成のときにつないでいきゃあいいと思うのですが。

noname#95388
質問者

お礼

そう思い実装してみたのですが，複雑なアルゴリズムになってしまったので．もっと簡潔にする方法があればと思ったのですが，地道にやるのがいいみたいですね．

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.2

そもそも「読み込んだ順と逆順に出力する」のは「読み込んだ順」が分からないと不可能だ. そのことに気づいているんだろうか. 「２分木のデータ構造を用いて実現した」っていうのも「どのようなデータを保持してどのように用いたのか」が書かれていないので, 「そのまま利用して逆順に出力する」ことは「不可能だと思うけどひょっとしたらできるかもしれない」としか言えない. 「２分木のデータ構造」と書いてるけど, 「読み込んですぐに二分探索木に挿入した」んではないかと推測してみる＞#1. (1) と (2) を逆の順序でやると小賢しいといわれて幸せかも.

noname#95388
質問者

お礼

やはり無理ですよね．線形リストを使いたいと思います．

回答No.1

>もっと上手く実現するアルゴリズムはあるでしょうか？ ソートに対して2分木を採用した理由は何でしょうか？ 2分木は親から複数の子に対してのノードをぶら下げていく方法ですから、ソートはかえって難しかったのでは？ （私個人にはツリー構造での実現方法というものは思いつきませんが……中点を最上位のノードとしても、その子のノードはどの位置を示すのかとか考えたくないですし） 双方向リストを使用した方が簡単ですよ。

noname#95388
質問者

お礼

２分木の既存のプログラムがあったので，それを応用して作ろうと思ったのと，探索などの機能を拡張する場合，２分木のほうが優れているという判断です． 純粋に双方向のポインタを付け加えようと思います．

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • 双方向リストのソート方法について。

    単刀直入に言いまして、双方向リストのデータを入れ替えるのではなくて、リスト前後を指すポインタの繋ぎ代えをして、ある一定条件に従ったリストへのソートをしたいと思っています。 リスト構造の前後にダミーを置いて……という方法は取りたくなく、出来るだけメモリを節約した方法が知りたいです。 また、そのリスト数は大体２０個くらいで、１秒間に大体５０～６０回くらい呼ばれるモノです。 リストのデータ数は比較的大きい物です。 参考になる書籍とかでも構いませんので、是非とも教えて下さい。

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

    リストや木等のデータ構造（？）は ポインタのつなぎ方みたいな物なのでしょうか？？ それとも、それには何か特別な関数（メモリー確保を除く）が必要なのでしょうか？？

  • スタック、キュー、リスト、2分木の使い道は？

    主な定番データ構造として (1)スタック (2)キュー (3)リスト (4)2分木 これらのデータ構造がありますが、特に「スタック」と「キュー」は一体何に使えるのでしょうか？ 「スタック」や「キュー」は使い道が思いつかないのですが、一体何に使えるのですか？ データ構造である「スタック」「キュー」「リスト」「2分木」の使い道を教えてください。 よろしくお願いいたします。

  • 単方向リストの解釈

    　多数のデータが単方向リスト構造で格納されている。このリスト構造には、先頭ポインタとは別に、末尾のデータを指し示す末尾ポインタがある。次の操作のうち、ポインタを参照する回数が最も多いものはどれか。 ア　リストの先頭にデータを挿入する。 イ　リストの先頭のデータを削除する。 ウ　リストの末尾にデータを挿入する。 エ　リストの末尾のデータを削除する。　　　　　（平成24年度春期　問７） 各選択肢の参照ポインタ数はいくつになるのでしょうか。 解説書によって必要なポインタ参照数が異なっていて、理解できずにいます。 とある解説書では、 ア　２回のポインタの参照が必要 イ　１回のポインタの参照が必要 ウ　２回のポインタの参照が必要 と記述してあり、またある解説書では ア　０回のポインタの参照が必要 イ　２回のポインタの参照が必要 ウ　１回のポインタの参照が必要 エ　３回のポインタの参照が必要 と記述されていました。 先頭から末尾の一つ手前のデータまで順にたどって参照する必要のあるエが一番ポインタを参照する回数が多そうだな、と想像はできるのですが、実際の参照回数までは理解の外です。。 ご教授お願いします。

  • 線形リストの高速ソート

    線形リストを最も高速でソートする方法は何でしょうか？ 必要であれば双方向リストにすることも可能ですが、できれば単方向で可能なのが知りたいです。 特許取得されている方法でもOKです。

  • 単方向リスト

    図は単方向リストを表している。“東京”がリストの先頭であり、そのポインタには次のデータのアドレスが入っている。また、“名古屋”はリストの最後であり，そのポインタには0が入っている。 先頭データへのポインタ 　　アドレス　　　データ　　　　ポインタ １０　　　　　　　　　　　　１０　　　　東京 　　　　　５０ 　　　　　　　　　　　　　　３０　　　　名古屋　　　　　０ 　　　　　　　　　　　　　　５０　　　　神奈川 　　　　９０ 　　　　　　　　　　　　　　７０　　　　長野　　　　　３０ 　　　　　　　　　　　　　　９０　　　　山梨　　　　　７０ 　　　　　　　　　　　　　　１５０　　　岐阜 アドレス150に置かれた“岐阜”を、“長野”と“名古屋”の 間に挿入する処理を答よという問題なんですが答えが アドレス、 　　　　データ部分 、　　　ポインタ １０　　　　　　　　　東京　　　　　　　50 ３０ 　　　　　　 　名古屋 　　　　　　　0 ５０　　　　　　　　神奈川　　　　　　　90 ７０　　　　　　　　　長野　　　　　　　150 ９０　　　　　　　　　山梨 　　　　　　　70 １５０　　　　　　　　岐阜　　　　　　　30 になるんですが解き方がわかりません。教えてください

  • 二分探索木の行きがけ順走査

    二分探索木の行きがけ順走査は、普通再起を使うと思います。 再起を使わず、しかも木以外のデータ構造を一切使わないでやることもできる聞いたのですが、具体的にはどうすればいいのでしょう。 木以外に何か使ってもいいのなら、 http://www.psg.cs.titech.ac.jp/pro1/11.pdf の『再起を使わないアルゴリズム』みたいにすれば良いことは調べてわかりました。 再起も使わないで出来るのであれば、自分でもJavaを使って書いてみようかと思っているのでカテゴリはJavaにしました。よろしくお願いします。

    • ベストアンサー
    • Java
  • データ構造とアルゴリズムの問題が分かりません。

    データ構造とアルゴリズムの問題が分かりません。 以下の問題で悩んでいます。 索引は書籍中の単語が書籍の何ページ目に出現するかを表す。もちろん、索引に含まれるある単語が複数のページに出現する場合や、索引に含まれる複数の単語が同一のページに出現する場合もある。 この索引で対象とする単語は、その書籍の中で重要な意味をもつものとして、また、特定の単語はたかだか数ページにのみ出現すると仮定する。 （1）単方向リストを用いてこのようなデータ構造を実現する場合、Ｃ言語ではどのように宣言をすれば適切か、struct宣言を用いて示しなさい。 （2）単方向リストを用いてデータ構造の場合、特定の単語が何ページ目に現れるか探すにはどのようなアルゴリズムを適用すれば適切か、探索に必要な時間計算量とともに示しなさい。 （3）二分探索木を用いてこのようなデータ構造を実現する場合、Ｃ言語ではどのように宣言をすれば適切か、struct宣言を用いて示しなさい。 （4）二分探索木を用いたデータ構の場合、特定の単語が何ページ目に現れるか探すにはどのようなアルゴリズムを適用すれば適切か、探索に必要な時間計算量とともに示しなさい。 （5）二分探索木を用いたデータ構の場合、アルファベット順の索引を出力するたねには、どのような整列アルゴリズムを適用すれば適切か、整列に必要な時間計算量とともに示しなさい。 テストに類題を出すと先生はおっしゃってたので、どうしてもすぐに回答が必要です。先生にも質問したのですが、テストに類題を出すから教えられない。自力で頑張れと言われ困っています。　どなたか御助力よろしくお願いいたします。

  • 線形リストのソートについて

    データ構造を線形リストとして、情報を管理するプログラムのソートについてです。 以下のプログラムはデータを入れ替えて、その後アドレスを入れ替えるようにしてソートを行っていますが、そうではなく線形リストなのでつなぎ替えるようにしてソートを行うプログラムを作成したいのですがわからないのでご教授をお願い致します。ソートは逐次決定で行ってます。 構造体の宣言として、nameとageとnextは氏名と年齢と次のポインタを指します。NAME_SORT、AGE_SORTはマクロです。 struct sortlist(struct PERSON *head) { int menu; struct PERSON person; /* 情報 */ struct PERSON move_person; /* 比較していく情報 */ struct PERSON work; /* 情報の一時的保存 */ struct PERSON temp; /* 作業用 */ struct PERSON temp_address; /* アドレス作業用 */ printf("ソート機能を選択："); printf("%d:氏名\n",NAME_SORT); printf("%d:年齢\n",AGE_SORT); /* 交換処理 */ for(person = head; person -> next != NULL; person -> person -> next) { work = person; /* 交換データの探索 */ for(move_person = person -> next; move_person != NULL; move_person -> next) { switch(menu) { case NAME_SORT: if(strcmp(work -> name, move_person -> name) > 0) { work = move_person; } break; case NAME_SORT: if(work -> age > move_person -> age) { work = move_person; } break; default: printf("機能以外が選択されました"); return head; } if(work != person) { /* 情報の交換 */ temp = *person; *person = *work; *work = temp; /* アドレスの交換 */; temp_address = employee -> next; person -> next = work -> next; work -> next = temp_address; } } } } printf(“ソート完了”); }

  • VBでリスト構造を実現するには？

    DTDとHTMLのパーサを作ろうと思い、データを解析して配列に入れようとしていたのですが、配列じゃなくてリスト構造で実現しろというお達しをうけて非常に困っています。 そもそもVBでリスト構造って実現できるんでしょうか？実現できるのであればその方法を教えていただきたいと思っています。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する