Embedded Files
making-treeで、木構造を持つデータを作成するPerlスクリプトを作成しました...すると、
nodeの作成だけではなく、”削除”もしたい時ってあります。
親nodeが”削除”されると、子nodeも同時に削除されるっていうのが普通の感覚です。
そりゃそうですよね。
では、どうやって実現するか？ 段階を追って考えてみます。
木の構造解析
データを操作したいのであれば、ひとまずデータの構造について”知る”必要があります。
ここで”知る”という行為の主体は、”データを操作するプログラム”です。
※プログラマが”知る”のは当然として。
なので、”知る”ために、どうやって、木構造を解析するか？を考えてみます。
知りたい木の構造は、再帰構造を持つ⬇だから、
木の構造
node.木の深さを表す数字(0より始まる).兄弟番号(0より始まる)
{
hogehoge(<-nodeのメンバ)
node.木の深さを表す数字+1.兄弟番号(0より始まる)
{
hogehoge
}
node.木の深さを表す数字+1.兄弟番号+1
{
hogehoge
node.木の深さを表す数字+2.兄弟番号(0より始まる)
{
hogehoge
}
}
}
解析するにあたって、
作成するプログラムも再帰構造を持つプログラムにした方が、素直です。
解析の対象要素
nodeの名称、nodeが位置する深さ、node間の親子、兄弟関係を知りたいですね。
⬇のような木であれば、
ex. 深さ２の木、各ノードには、二つの子ノードがいる。
node.0.0
{
hogehoge
node.1.0
{
hogehoge
node.2.0
{
hogehoge
}
node.2.1
{
hogehoge
}
}
node.1.1
{
hogehoge
node.2.0
{
hogehoge
}
node.2.1
{
hogehoge
}
}
}
こういう感じ⬇で、木を解析出来たらいいなと思います。
node名の後ろにあるのは、木の深さレベル。closeとしてるのは、nodeの定義の終端を示す。
node.0.0, 0
node.1.0, 1
node.2.0, 2
close
node.2.1, 2
close
close
node.1.1, 1
node.2.0, 2
close
node.2.1, 2
close
close
close
作成するプログラムのアウトライン
先に書いたように、再帰的な構造を持つプログラムで解析した方が素直です。
ざっくり書くとこんな感じでしょうか。
"木を解析する関数”の定義
node名を含む一行と、木の深さを引数で取得
node名を取得し、標準出力へ出力
標準入力から、木情報を一行づつ読み取る
再帰の基底条件：
node終端を示す、"}"を検出した場合、
node終端を示す"close"を標準出力へ出力。そして、関数からリターン
読み取った一行に、node名が含まれている場合、
"木を解析する関数"をコール
その際に、与える引数は、
標準入力から読み取った木情報一行、木の深さ+1
以上、、、って感じです。
プログラム
上の動作を実現するPerlスクリプトを⬇に貼付けます。
下記の環境で動作してます。
Mac OS X 10.9
perl --version
This is perl 5, version 12, subversion 4 (v5.12.4) built for darwin-thread-multi-2level
$cat tree | perl bone-prune_tree.pl > bone
で、ファイルboneに、木構造を抽出した情報が出力されます。
treeは、木構造をもつデータファイル
さて。
つづく投稿で、nodeを削除します。
Page updated
Google Sites
Report abuse