ツリー構造の比較アルゴリズム

前へ 次へ
このQ&Aのポイント
  • ツリー構造の比較について教えてください。比較対象のディレクトリ構造の変更前と変更後を比較するプログラムを作成したいです。
  • ディレクトリの変更前と変更後の比較を行うプログラムを作成したいです。どのフォルダがどこへ行ったかを判別するアルゴリズムを教えてください。
  • ツリー構造（ディレクトリ構造）の変更前と変更後を比較するためのアルゴリズムを教えてください。１：１に対応しない場合や削除、追加などのパターンがある場合にも対応したプログラムを作成したいです。
回答を見る
  • ベストアンサー

ツリー構造の比較のアルゴリズムを教えてください

ディレクトリ構造の変更前と変更後の比較を行って、 どのフォルダがどこへ行ったかを判別するプログラムを作成したいのですが、どんなアルゴリズムにすればよいでしょうか？ 変更前と変更後でディレクトリは１：１に対応しません。ｎ：ｍや削除、追加など色んなパターンがあります。 ツリー構造（ディレクトリ構造）とは、以下のようなイメージのものです。 C:. ├─Acrobat │ ├─ActiveX │ ├─Browser │ ├─FileInfo │ ├─HowTo │ │ ├─ENU │ │ │ └─Images │ │ └─JPN │ │ └─Images │ ├─Javascripts

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

  • ベストアンサー
回答No.1

考えてみましたが何とも言えません。 取り敢えず回答カウントがゼロなので投稿させていただきます。 但し、これはあくまで個人的なアイデアやイメージである事を前提とします。 ☆ツリー構造はGUIコントロールでありマウスで操作するとコールバックされる事を前提(TreeGUIとします) ☆手順はコールバックがかかる度に変化したTreeGUIの状態からデータ構造を生成します ☆データ型 struct TreeData { string strDirectory;//ディレクトリの名前 "Actobat"など int nAction;//このディレクトリに対して行われた操作フラグの記録 //その他TreeDataを連結するポインタなど }; ☆page[?]//TreeData*をしまう為の配列 　page[0]//変更前 　page[1]//変更後 (1)以下のスタートの状態からTreeDataを生成してpage[0]に入れる ├─Acrobat │ ├─ActiveX │ ├─Browser │ ├─FileInfo │ ├─HowTo │ │ ├─ENU │ │ │ └─Images │ │ └─JPN │ │ └─Images │ ├─Javascripts (2)TreeGUIをマウスで突っついたりディレクトリ操作をする（コールバック発生）TreeGUIの状態かTreeDataを生成してpage[1]に入れる アルゴリズム等 　1:1やm:nの確認なら再帰等で操作してCTreeDataの連結数を数えて比較すれば出来ます 　oldCount = DoCount(page[0]) 　nowCount = DoCount(page[1]) 　 　ディレクトリの位置が違うがカウントは同じ 　if(oldCount == nowCount)//... 　あとはTreeDataの構造を操作しながらその都度処理していくしかなさそうです。当然ながらどのような操作を受けたディレクトリなのかを示すメンバデータも必要になります。 　また変更前と変更後の二つだけしか必要ない場合、TreeGUIに反応するたびpage[1]にTreeData生成しますが、一歩手前を検出する場合は変更以前のものが軌跡を残すように連鎖するので（アンドゥリドゥみたいになる）pageは動的に拡大されます(page[0] ～ page[n])。 　この設問に回答するのは実に困難であります。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. その他（プログラミング・開発）

関連するQ&A

  • 木構造（位相構造）を比較するアルゴリズムって？

    木構造（位相構造）を2つ用意し、根からたどって比較してゆき、 差分をとるようなプログラムを書こうと思っています。 しかしアルゴリズムがまったくわからないので質問させていただきます。 子ノードの順番が異なる場合も同じものと見なすような条件で、 末端にノードが追加された程度の差異がわかればよいです。 （鏡に映した構造や、子ノードがABCという順だったのを、ACBにしたような構造は同じものと見なしたいということです。） このようなアルゴリズムというのはあるのでしょうか？

  • 再帰構造のアルゴリズムで困っています。

    最近プログラミングを勉強し始めた者です。 教科書とWebを使って勉強しているのですが、なかなか厳しいです。 初歩的な質問であると思いますがお許しください。 フィボナッチ数列の８番目の数字を再帰構造を用いて表示させるプログラムを作りました。 Sub saikikouzou() n = 8 Cells(1, 1) = keisan(n) End Sub Function keisan(n) If n < 3 Then keisan = 1 Else keisan = keisan(n - 1) + keisan(n - 2) End If End Function 一般的にフィボナッチ数列と言われると「1.1.2.3.5.8.13.21」という数列であると理解しています。上記のプログラムもそのつもりで作成しました。 しかし今は「1.2.3.5.8.13.21.34」という数列の８番目を再帰構造を使って求めたいと考えています。 つまり、最初の数字を「1,1…」と始まるのではなく「1.2…」と始めたいのです。 私のプログラムだと、 If n < 3 Then keisan = 1 の部分で最初の数字が「1.1」と決めているため、良くないことは理解できましたが、どうすれば「1.2…」と始められるかが分かりません。 まだこの単元を消化しきっていないため、質問内容もままならない点がありますが、ご理解できましたら是非回答をよろしくお願いします。

  • データ構造とアルゴリズム

    学校の課題なのですが、試験の得点順（降順）に学生番号と得点を表示することができるシステムを行っています。 仕様は下記の通りです。 外部仕様 １．試験の得点順（降順）に学生番号と得点を表示 ２．機能メニュー（１：追加、２：削除、３：表示、１～３以外：終了）で操作できる ３．機能メニューの１：追加を選択すると、キーボードから学生番号と得点を入力することができる ４．機能メニューの２：削除を選択すると、キーボードから入力した学生番号のデータを削除することができる。 ５．機能メニューの３：表示を選択すると、入力されているデータが、得点順に表示される 内部仕様 １． 使用言語はC言語とする ２． ダミーノードを使わない順方向リスト構造とする ３． リストのノードは構造体を使用する ４． リストのノードが常に得点の降順で並ぶように追加する ５． 入力データ型は、機能メニューを選択するための数字と得点は整数型、学生番号は文字列型とする ６． 先頭のノードのポインタを格納する変数名はheadとする ７． 全体の処理の流れは図１のとおりとし、【テンプレート・プログラム】の必要箇所に必要な機能を追加して完成させるものとする。テンプレート・プログラムで使用されている変数名は、そのまま使用すること。 ８． 機能メニューは、関数名：menu()で表示する。menu()の仮引数は無し、戻り値は、キーボードから入力されたメニュー番号(整数)とする。 ９． 機能メニューの１：追加では、関数名：insert()において先頭ノードから最後尾ノードに向けて順にキーボードから入力した得点と大小関係を比較し、得点の降順で並ぶように挿入位置を決めるためのアルゴリズムを考えて、新たなノードをリストに挿入する。関数名：insert()、仮引数：無し、戻り値：無し。なお、新しく追加するノードのポインタアドレスは変数pを使用する。追加する場所を探すために参照するノードのポインタアドレスは変数p2を使用する。 １０． 機能メニューの２：削除では、関数名：del()においてキーボードから削除する学生番号を入力し、該当するノードを削除する。学生番号が見つからない場合は何もしない。関数名：del()、仮引数：無し、戻り値：無し。なお、文字列の比較には、strcmp()関数を使用する。 １１． 機能メニューの３：表示では、関数名：disp()において先頭のノードから学生番号と得点を表示する。関数名：disp()、仮引数：無し、戻り値：無し。 この、追加機能のinsert、削除機能のdel、dispをどのように記述すればいいのかが分かりません。 分かる方宜しくお願いいたします。

  • データ構造とアルゴリズム

    Ｃ言語の勉強をしているんですが最近はアルゴリズムについての勉強をしたくAmazon等で検索しています。 現在手持ちの本ではＣのプログラムの解説(書き方)が主でアルゴリズムについての解説がとてもすくないです。 やっぱりＣのソースがあったほうがいいのですが、詳しく解説(証明)している本が欲しいです。 お勧めの本がありましたら紹介してください。

  • データ構造とアルゴリズム

    途中の解き方も、あわせて教えて下さい。

  • インデックスのアルゴリズムとBツリー

    主キーじゃないカラムにインデックスを張るとき、 つまり、値が重複することがありうる場合に 利用されるBツリーは通常のBツリーと比較して、 どのように変更すればよいものでしょうか。 また、WHERE句内で * などを使用して検索するとき、 どのようにBツリー内を検索すれば効率的でしょうか。 データベースの実装に関する質問になりますが、 わかる方、よろしくお願いします。

  • ハッシュとツリー構造

    今学校でハッシュとツリー構造について勉強しています。 しかし、先生の言っていることがまったく意味が分かりません。 すいませんが、ハッシュとツリー構造について簡単でいいので教えてください。 お願いします。

  • テーブルのツリー構造の作り方

    MySQLで会員制サイト構築中です。 一般的なテーブル以外に、会員ひとりひとりの固有のテーブルを用意したいと思っています。 そのためツリー構造でテーブルをつくり、親テーブルの中に会員固有の子テーブルをで作り、そこにアクセスしようと思ってます。この場合SQL文はどんなんになるでしょうか? また、このやり方だと子テーブルの数が会員数に比例して増大してきますが、ホスティングサービスに設置するには問題がありますでしょうか? よろしくご指導お願い致します。

  • グラフ構造のアルゴリズムの問題です。

    グラフ構造のアルゴリズムの問題です。 頂点間の最短距離を求める問題ですが、どうすれば良いかわかりません......。ダイクストラ法などを使うのでしょうか？ 何のアルゴリズムを利用するのかという点と、解法の手順を解説していただけると幸いです。 以下、問題文です。 v1,v2,v3,..., v9,v10 の 10 個の頂点からなる重みつき無向グラフ G の全頂点間の最短距離を計算したい。こ こで dk(i,j) を頂点 vi から頂点 vj への「経由してよい頂点を v1,...,vk に限定した」最短距離とする。例えば, d3(i,j)は「経由してよい頂点が v1,v2,v3 に限定された」vi から vj への最短距離となる。 ただし,v1,...,vk までの頂点のみを経由するような vi から vj への経路がない場合は dk(i,j)を∞とする。 いま,「経由してよい頂点を v1～v6 に限定した」全頂点間の最短距離がそれぞれ d6(1,2)=3 d6(1,3)=12 d6(1,4)=∞ d6(1,5)=4 d6(1,6)=6 d6(1,7)=∞ d6(1,8)=4 d6(1,9)=8 d6(1,10)=9 d6(2,3)=5 d6(2,4)=∞ d6(2,5)=2 d6(2,6)=3 d6(2,7)=∞ d6(2,8)=1 d6(2,9)=6 d6(2,10)=3 d6(3,4)=∞ d6(3,5)=5 d6(3,6)=2 d6(3,7)=∞ d6(3,8)=6 d6(3,9)=9 d6(3,10)=5 d6(4,5)=∞ d6(4,6)=∞ d6(4,7)=2 d6(4,8)=∞ d6(4,9)=∞ d6(4,10)=4 d6(5,6)=5 d6(5,7)=∞ d6(5,8)=3 d6(5,9)=4 d6(5,10)=8 d6(6,7)=∞ d6(6,8)=4 d6(6,9)=9 d6(6,10)=3 d6(7,8)=3 d6(7,9)=∞ d6(7,10)=1 d6(8,9)=4 d6(8,10)=7 d6(9,10)=12 であった。この情報をもとに以下のそれぞれの値を求めよ。 (1)d7(1,10) (2)d7(4,8) (3)d7(4,10) (4)d8(1,10) (5)d8(4,5) お手数お欠けしますが、どうかよろしくお願い致します。

  • データ構造とアルゴリズムの違いについて教えて頂けないでしょうか。

    データ構造とアルゴリズムの違いについて教えて頂けないでしょうか。 データ構造とアルゴリズムについて学習しています。 （質問事項） ・データ構造とアルゴリズムの違いについて教えて頂けないでしょうか。 詳細に教えて頂けると大変助かります。 （私の現状） たとえば、データ構造は、単純なものでは、配列やコレクション、２分木などの構造で、アルゴリズムは２分木探索の実装方法だと思っています。 データ構造とアルゴリズムについては初心者です。 （現在、就職活動中で、これらを学ぶ必要がありご質問させて頂いています） どうか、皆様、教えて頂いた情報を最大限に活用させていただきますので、（皆様にとってはくだらない質問かもしれませんが…）どうぞよろしくお願いいたします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する