- ベストアンサー
アルゴリズム 木構造のパス表示
下記のような入力データを出力データのように出力させたいのですが。 アルゴリズムを教えて頂けませんでしょうか? 言語は特定の言語でなくても構いません。 日本語で雰囲気が解ればそれに越したことはありません。 もし、特定の言語で記述頂ける場合、 (言語依存の特殊な表記方法を避けて頂けるとたすかります(知識が浅いため)。 但し言語依存の関数等は引数と戻り値の説明を入れていただけたら可です。 (勘違いしそうなので) トリッキーな書き方を避けべたな平書きでお決まりの処理部分は関数 で省略みたいな感じだとありがたいです(見やすいため)。 ※元データ生成データ共に、見た目のままのテキストデータです。 //入力データ例(階層等やパターンは決まって無いことが前提) 親 ├子1 ├子2 │├孫1 │└孫2 ├子3 │ └孫3 │ ├ひ孫1 │ └ひ孫2 └子4 //ここまで //出力データ 親\子1 親\子2 親\子2\孫1 親\子2\孫2 親\子3 親\子3\孫3 親\子3\孫3ひ孫1 親\子3\孫3ひ孫2 親\子4
- akaginoyama
- お礼率88% (635/715)
- その他(プログラミング・開発)
- 回答数5
- ありがとう数5
- みんなの回答 (5)
- 専門家の回答
質問者が選んだベストアンサー
同じようなプログラムを組んだことがあります。 一見複雑そうに見えますが、分かってしまえば非常に簡単です。 階層構造を保持する配列を用意しておきます。(以下、path[x]とします。) 各行を読み込んだ時の、行頭の階層を表す「├、│、└、スペース」の数をn、階層名をsとすると ・path[n] にsを代入 ・path[0]~path[n]を、間に\を挟んで出力 します。 以上です。 例えば、質問者さんの例だと、 n=0 s="親" →path[0]に"親"を代入、path[0]を出力→"親" n=1 s="子1" →path[1]に"子1"を代入、path[0]~path[1]を出力→"親\子1" n=1 s="子2" →path[1]に"子2"を代入、path[0]~path[1]を出力→"親\子2" n=2 s="孫1" →path[2]に"孫1"を代入、path[0]~path[2]を出力→"親\子2\孫1" n=2 s="孫2" →path[2]に"孫2"を代入、path[0]~path[2]を出力→"親\子2\孫2" n=1 s="子3" →path[1]に"子3"を代入、path[0]~path[1]を出力→"親\子3" n=2 s="孫3" →path[2]に"孫3"を代入、path[0]~path[2]を出力→"親\子3\孫3" n=3 s="ひ孫1" →path[3]に"ひ孫1"を代入、path[0]~path[3]を出力→"親\子3\孫3\ひ孫1" n=3 s="ひ孫2" →path[3]に"ひ孫2"を代入、path[0]~path[3]を出力→"親\子3\孫3\ひ孫2" n=1 s="子4" →path[1]に"子4"を代入、path[0]~path[1]を出力→"親\子4" となります。 ただし、以上の記述は行頭の「├、│、└、スペースの数」に間違いがない、というのが前提です。 実際には、質問者さんの例では、孫3・ひ孫1のスペースの数がおかしいので、そのままでは使えません。 これが「質問するときの記入ミス」なら、上述のアルゴリズムで問題ありませんが、 元のデータもその通りだったのだとすると、かなり難しくなります。
その他の回答 (4)
- kmee
- ベストアンサー率55% (1857/3366)
すみません。良く読んだら、入力ファイルだったんですね。 「内部で木構造になっているデータ」の出力と勘違いしてました。 単に変換するなら、#4さんの方法がよいと思います。 注意点は、「階層が不明」「文字列の保存」の2点です。 言語によっては、伸び縮みする配列を扱いずらいものがあります(C言語とか) あとは > パターンは決まって無い というのが不明です。一定の約束事がなければ、入力データの解析が困難です。 すでに指摘があるように「ひ孫2」が他の規則から逸脱していますが、これも「孫3」の子である、と判断させようとすれば、例外的に判定する必要があります。
お礼
色々と説明不足ですみません。 参考になりました。 結果的にはNo.4さんの回答を採用させていただきました。 解決ありがとうございました。
補足
一部、誤りがありがみつかりましたので修正です。 //ここから データを反復 N=対象の階層数 S=対象 P[N]=対象 (N+1)回 //修正箇所 結果に(P[回数-1]&"\")を配列追加//修正箇所 //ここまで 以上解決とさせていただきます。
- dscripty
- ベストアンサー率51% (166/325)
[ANo.2] さんの回答を具体的にかくと、こんなかんじ。 人のデータ構造 [ - 名前 - 子供たち(人のリスト) - 親(人へのリンク) - 先祖の名前リストの最後に本人の名前を加えて返す関数() { 親がいないとき → 「本人の名前」をかえす。 親がいるとき → 「[親(人へのリンク)].先祖の名前リストの最後に本人の名前を加えて返す関数() + "\" + 名前」をかえす。 } ] (1) 処理対象を「親」に設定。 (2) 処理対象に対して以下を実行。 「先祖の名前リストの最後に本人の名前を加えて返す関数()」を出力。 「処理対象の子供たち(人のリスト)」の中の人を順番に処理対象にして (2) を実行。子供たちいないときはなにもしない。 おわり。
お礼
教えていただいた方法をヒントに 日本語プログラミングで作成してみました。 出力にあたり不要文字列の削除やデータの若干の整形が必要ですが、 解りやすくするために問題の主要部分だけ抽出してます。 //ここから //反復はforeachのこと データを反復 N=対象の階層数 //対象とは繰り返しのイテレータのこと S=対象 P[N]=対象 Pを反復 結果に(対象&"\")を配列追加 結果を表示。 //ここまで こんな単純なアルゴリズムで書けるなんて目からうろこです。 ありがとうございました。
補足
インデントの記述ミスがあり修正です。 //ここから //反復はforeachのこと データを反復 N=対象の階層数 //対象とは繰り返しのイテレータのこと S=対象 P[N]=対象 Pを反復 //インデントが崩れてました 結果に(対象&"\")を配列追加 結果を表示。 //ここまで
- kmee
- ベストアンサー率55% (1857/3366)
再帰呼び出しが可能な言語なら、再帰呼び出しを使うのが常套手段でしょう。 自分から下の木の表示すべてに 「ルート\1階層目\2階層目...\自分の上」 を追加すればいいわけです。 あとは、言語や目的に合せて ・「自分の上」までの情報を下に伝えて、「自分」で出力 にするか ・「一覧表」を返して、出力は呼び出し側にまかせる にするか
お礼
回答ありがとうございます。 以前、自身でも再帰処理で同じような処理を書いたのですが・・・。 思い出せませんでした。 今回は、時間が無かったので No4さんの方法を採用させていただくことにしました。 再帰処理は慣れておくと便利なので、また時間があるときにでも 勉強のために再帰処理で書いてみたいと思います。
- hitomura
- ベストアンサー率48% (325/664)
以下の2点の補足お願いします。 > │ └孫3 > │ ├ひ孫1 > │ └ひ孫2 の部分ですが、 (1) 半角空白が消えてしまうため全角空白への置き換えを行っているのか、それとも最初から全角空白なのかお教えください。 (2) ひ孫1とひ孫2とで空白の個数が違いますが、それで間違いありませんか。
お礼
編集の際に使ったスペースのミス問題です。 スペースはこの際問題でないので外してみました。 親 ├子1 ├子2 │├孫1 │└孫2 ├子3 │├孫3 │└孫4 └子4
関連するQ&A
- アルゴリズムでわからない問題があります。(C言語)
問題1:探索アルゴリズムであるハッシュ法について正しいものを選べ。 (1)ハッシュ関数の出力によりデータを格納した配列の先頭から順番に調べる. (2) 入力データを,ハッシュ関数の出力により求めた格納場所に基づいて,あらかじめ木構造に格納しておく. (4) 入力データを格納した配列を繰り返し2つに分割し,それぞれを順番に調べていく. (3) 入力データから格納場所の位置に変換する関数(ハッシュ関数)の出力により,データの探索場所を決定する。 (5) 入力データを,ハッシュ関数の出力により求めた格納場所に基づいて,あらかじめヒープに格納しておく 問題2:探索アルゴリズムであるハッシュ法について正しくないものを選べ。 (1)入力データはハッシュ値で決められる場所に格納される. (2) ハッシュ関数には,異なる入力の値に対し異なる値を出力することが求められる. (3) ハッシュ関数の時間計算量は,入力データのサイズに比例する. (4) データの格納場所が大きい方が効率がよい. (5) 一般に2分探索法より高速に動作する. どなたかアルゴリズムに詳しい方回答お願いします
- 締切済み
- C・C++・C#
- データ構造とアルゴリズム
学校の課題なのですが、試験の得点順(降順)に学生番号と得点を表示することができるシステムを行っています。 仕様は下記の通りです。 外部仕様 1.試験の得点順(降順)に学生番号と得点を表示 2.機能メニュー(1:追加、2:削除、3:表示、1~3以外:終了)で操作できる 3.機能メニューの1:追加を選択すると、キーボードから学生番号と得点を入力することができる 4.機能メニューの2:削除を選択すると、キーボードから入力した学生番号のデータを削除することができる。 5.機能メニューの3:表示を選択すると、入力されているデータが、得点順に表示される 内部仕様 1. 使用言語はC言語とする 2. ダミーノードを使わない順方向リスト構造とする 3. リストのノードは構造体を使用する 4. リストのノードが常に得点の降順で並ぶように追加する 5. 入力データ型は、機能メニューを選択するための数字と得点は整数型、学生番号は文字列型とする 6. 先頭のノードのポインタを格納する変数名はheadとする 7. 全体の処理の流れは図1のとおりとし、【テンプレート・プログラム】の必要箇所に必要な機能を追加して完成させるものとする。テンプレート・プログラムで使用されている変数名は、そのまま使用すること。 8. 機能メニューは、関数名:menu()で表示する。menu()の仮引数は無し、戻り値は、キーボードから入力されたメニュー番号(整数)とする。 9. 機能メニューの1:追加では、関数名:insert()において先頭ノードから最後尾ノードに向けて順にキーボードから入力した得点と大小関係を比較し、得点の降順で並ぶように挿入位置を決めるためのアルゴリズムを考えて、新たなノードをリストに挿入する。関数名:insert()、仮引数:無し、戻り値:無し。なお、新しく追加するノードのポインタアドレスは変数pを使用する。追加する場所を探すために参照するノードのポインタアドレスは変数p2を使用する。 10. 機能メニューの2:削除では、関数名:del()においてキーボードから削除する学生番号を入力し、該当するノードを削除する。学生番号が見つからない場合は何もしない。関数名:del()、仮引数:無し、戻り値:無し。なお、文字列の比較には、strcmp()関数を使用する。 11. 機能メニューの3:表示では、関数名:disp()において先頭のノードから学生番号と得点を表示する。関数名:disp()、仮引数:無し、戻り値:無し。 この、追加機能のinsert、削除機能のdel、dispをどのように記述すればいいのかが分かりません。 分かる方宜しくお願いいたします。
- 締切済み
- 大学・短大
- データ構造とアルゴリズムの問題が分かりません。
データ構造とアルゴリズムの問題が分かりません。 以下の問題で悩んでいます。 索引は書籍中の単語が書籍の何ページ目に出現するかを表す。もちろん、索引に含まれるある単語が複数のページに出現する場合や、索引に含まれる複数の単語が同一のページに出現する場合もある。 この索引で対象とする単語は、その書籍の中で重要な意味をもつものとして、また、特定の単語はたかだか数ページにのみ出現すると仮定する。 (1)単方向リストを用いてこのようなデータ構造を実現する場合、C言語ではどのように宣言をすれば適切か、struct宣言を用いて示しなさい。 (2)単方向リストを用いてデータ構造の場合、特定の単語が何ページ目に現れるか探すにはどのようなアルゴリズムを適用すれば適切か、探索に必要な時間計算量とともに示しなさい。 (3)二分探索木を用いてこのようなデータ構造を実現する場合、C言語ではどのように宣言をすれば適切か、struct宣言を用いて示しなさい。 (4)二分探索木を用いたデータ構の場合、特定の単語が何ページ目に現れるか探すにはどのようなアルゴリズムを適用すれば適切か、探索に必要な時間計算量とともに示しなさい。 (5)二分探索木を用いたデータ構の場合、アルファベット順の索引を出力するたねには、どのような整列アルゴリズムを適用すれば適切か、整列に必要な時間計算量とともに示しなさい。 テストに類題を出すと先生はおっしゃってたので、どうしてもすぐに回答が必要です。先生にも質問したのですが、テストに類題を出すから教えられない。自力で頑張れと言われ困っています。 どなたか御助力よろしくお願いいたします。
- 締切済み
- 科学
- アルゴリズムについて
大学の授業の課題のアルゴリズムについてなのですが、内容的に頭がついて行けず、一切分かりません。問題内容は、最小値を求めるアルゴリズム(必要な箇所を修正して下さい)です。 どなたか詳しい方いらっしゃいますでしょうか? よろしくお願いいたします。 M = -9999 データX入力 while X ≠ 9999 Y M < X N M = X データX入力 Mを出力
- 締切済み
- 情報処理技術者
- アルゴリズム開発における留意点
新製品のアルゴリズム開発をされている方などにお聞きしたいのですが、アルゴリズムを開発する際の留意点というか、どのようなことに気を使って開発をされているのか、教えていただけませんでしょうか(特定言語を想定しないとか、ユーザ数の依存性も考慮するとかといった類のものです)。 また、そのような「アルゴリズム開発のいろは」のような指南書がありましたら、ご紹介ください(既存アルゴリズムそのものの解説書ではありません)。 あまりうまくお伝えできずにすみませんが、よろしくお願いします。
- 締切済み
- その他([技術者向] コンピューター)
- アルゴリズムについて
現在アルゴリズム基礎を勉強しているのですが、初心者なので、まったく意味が分かりません。ちなみに文章からフローチャートにする部分が分かりません。 どうしたらいいのでしょうか?皆さん教えてください。お願いします。 *ちなみに今悩んでる例題です。 「1件分の売り上げデーターとして品名、単価、数量を入力し、金額を求めて、入力データーとともに出力する処理を、入力データがなくなるまで繰り返すフローチャートを作成しなさい。
- ベストアンサー
- その他([技術者向] コンピューター)
- プログラマにとって「アルゴリズム」や「データ構造」の知識は必須ですか?
最近の、いわゆるパッケージソフトウェアや、Webアプリケーションの開発においては、 必要なコンポーネントをインポートして部品を組み立てていくイメージで コードを書いていくというのが主流だと思います。 ほとんどのプログラミング言語には、すでに便利な関数やパッケージが用意されており、「アルゴリズム」や「データ構造」といった知識はあまり必要になりません。 例えば、データをソートしたい場合、クイックソートなどで自分で実装しなくても、すでにソート関数が用意されているので、その関数を使用すれば良いわけです。 そのような環境においても、プログラマにとって「アルゴリズム」や「データ構造」の知識はやはり必須ですか? 時々、 ・「優先順位付き待ち行列」くらいは、スラスラ実装できなければ、プログラマとしては半人前 ・「離散数学」をしっかり理解していないと、プログラマとしては致命的 などという話も聞くのですが、皆さんの意見を聞かせてください。
- ベストアンサー
- Java
- フォルダ階層をHTMLTable化するアルゴリズム
お世話になります。 指定されたルートフォルダの中の階層すべてを、 添え付け画像の様な HTMLのテーブルに変換して出力したいのですが、 そのアルゴリズムを教えてください。 各フォルダでは階層数がバラバラのため、テーブル 横のtdタグの数がバラバラになり、空白セル(図中のくろいセル)が 残ってしまいますが、これはそのまま気にしないで構いません。 言語は、できればC#,C,Java,php等でお願いします。 何卒宜しくお願いいたします。
- ベストアンサー
- その他(プログラミング・開発)
- C言語のソースを入力してアルゴリズムを出力したい
C言語のソースを入力するとそのアルゴリズムを出力してくれるソフトがあると聞いたことがあるのですが、どなたかそのソフトが売っているサイトをご存じないでしょうか? 出来れば安いものを希望します。
- 締切済み
- C・C++・C#
- 構造体の問題で・・・
どなたか以下のC言語-構造体の問題を教えていただけないでしょうか? 問題 構造体 data_t に年齢[int型]の一つのメンバをもつ構造体 info_t を追加し、以下の関数を使用して、平均年齢を出力するプログラムを作成。 [条件] ・年齢は、input関数を使用し、標準入力で設定するものとする。 ・年齢は1~99までの範囲とし、範囲外の年齢が入力された場合はエラー出力しプログラムを終了する。 ・平均年齢の小数点以下は切り捨てる。 [出力例] 社員番号を入力して下さい-> ★15を入力 氏名を入力して下さい-> ★suzukiを入力 年齢を入力して下さい-> ★28を入力 社員番号を入力して下さい-> ★20を入力 氏名を入力して下さい-> ★satouを入力 年齢を入力して下さい-> ★52を入力 社員番号を入力して下さい-> ★25を入力 氏名を入力して下さい-> ★tanakaを入力 年齢を入力して下さい-> ★17を入力 社員番号 氏名 年齢 15 suzuki 28 20 satou 52 25 tanaka 17 [関数] int avetage(struct data _t*); 意味 : 3人分の平均年齢を計算する関数 引数 : data_t配列ポインタ 戻り値: 平均年齢を返却 void output(struct data_t*,int); 意味 : data_t配列に設定された年齢を含むデータ及び、平均年齢を出力する関数。 引数 : data_t配列ポインタ、平均年齢。 ----------------------------- 問題は以上なのですが、どなたか教えていただけないでしょうか? できれば解説が少しでもあれば助かるのですが(><) よろしくお願いします。
- 締切済み
- C・C++・C#
お礼
教えていただいた方法をヒントに 日本語プログラミングで作成してみました。 出力にあたり不要文字列の削除やデータの若干の整形が必要ですが、 解りやすくするために問題の主要部分だけ抽出してます。 //ここから //反復はforeachのこと データを反復 N=対象の階層数 //対象とは繰り返しのイテレータのこと S=対象 P[N]=対象 Pを反復 結果に(対象&"\")を配列追加 結果を表示。 //ここまで こんな単純なアルゴリズムで書けるなんて目からうろこです。 ありがとうございました。
補足
書き忘れました。 対象の階層数は 該当記号の個数をカウントする関数です。