スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[WP]no.004 二分木探索、クイックソート@HSP

木構造の作成をHSPでやるよ。

製作時間:暁のそわそわx5(30min)

木構造の例として二分木を挙げました。
二分木探索を生成し、中順序探索を行い、ソートします。いわゆる木構造を使ったクイックソートです。
HSPには参照型が無いので、インデックスを格納する配列変数を定義してそれっぽくします。

どうでもいいですが、初めて再帰関数を使わずに書いた、特に中順序探索は無計画だったので滅茶苦茶です。
ビットをシフトして、フラグを格納する領域を無理やり作る荒業とか。

クイックソート目当ての方は別のホームページを参照してください。

画像の埋め込み、もっと簡単にできないかな…fc2。
we20150625


#define NIL -1

#const DATAMAXNUM 100

dim tree_value,DATAMAXNUM
dim tree_left,DATAMAXNUM
dim tree_right,DATAMAXNUM
tree_root=NIL
tree_elemnum=0

repeat DATAMAXNUM
tree_left.cnt = NIL
tree_right.cnt= NIL
loop

randomize
dim tarray,20
repeat 20
tarray.cnt=rnd(10000)
loop

pos 0,0
repeat 20
mes strf("%5d",tarray.cnt)
loop
// -----------------------------------

// 木を作成しながらarrayの内容を格納
repeat 20
if (tree_root == NIL) {
tree_value.0 = tarray.cnt
tree_root=0
tree_elemnum++
continue
}
value=tarray.cnt
i=tree_root
repeat
if (value < tree_value.i) {
// 左の子を探索
if (tree_left.i == NIL){
// 要素の追加
tree_value.tree_elemnum=value
tree_left.i=tree_elemnum
tree_elemnum++
break
}
i=tree_left.i
continue
}else{
// 右の子を探索
if (tree_right.i == NIL){
// 要素の追加
tree_value.tree_elemnum=value
tree_right.i=tree_elemnum
tree_elemnum++
break
}
i=tree_right.i
//continue
}
loop
loop


pos 100,0
repeat 20
mes strf("%5d %2d %2d",tree_value.cnt,tree_left.cnt,tree_right.cnt)
loop

// -----------------------------------

// 木を辿り、ソートする。
dim result,100:resultidx=0
dim stack,100

stack.0 = tree_root<<2 // もう配列宣言したくないので領域をお借り
stackidx=0
repeat
if (stackidx<0) : break

i=(stack.stackidx)>>2
f=(stack.stackidx)&3
logmes ""+tree_value.i

if (tree_left.i != NIL && (f&1)==0){
// 左の子があるなら、辿る
stack.stackidx = stack.stackidx | 1
stackidx++
stack.stackidx = (tree_left.i)<<2
continue
}
if ((f&2)==0){
// 左の子は無いので要素を出力
result.resultidx=tree_value.i
resultidx++
if (tree_right.i !=NIL){
// 右の子があるなら、辿る
stack.stackidx = stack.stackidx | 2
stackidx++
stack.stackidx = (tree_right.i)<<2
continue
}
}
// どちらも無いので戻る
stackidx--

loop

pos 250,0
repeat 20
mes strf("%5d",result.cnt)
loop

stop


実行画面は、左がソート前、中央に木構造(心の眼で見れば木構造に見えます)、右がソート後です。

二分木探索の知識が必要です。

大体の流れは
1.木構造で用いる配列の初期化
2.整列前の配列の初期化
3.配列を二分木に格納
4.二分木を中順序探索し、結果を配列にアウトプット

説明だけ読んでもわからない内容です。上のプログラムを読むときの助けになれば。

通常、再帰を使えばとてもきれいに記述できるのですが、今回はあえて使わない方針。


1.木構造で用いる配列の初期化
 value,left,rightの3つ。left,rightは要素番号を格納します。
例えば、要素番号3のleftに4,rightに5が入っていた場合、左側の子の情報は要素番号4、右側の子の情報は要素番号5。
tree_rootはROOTを示す要素番号。このプログラムでは常に0。
tree_elemnumは木構造の要素の数。配列要素の割り当てにも使う。

2.整列前の配列の初期化
 randomize。

3.配列を二分木に格納
 valueが格納しようとしている値、i が「探索中の木の要素 が 格納された」 配列の要素 の要素番号。
辿れなくなったら、そこに格納します。

4.二分木を中順序探索し、結果を配列にアウトプット
 再帰は使わない、と言っておきながらstack使ってます。
スタックに格納している情報は、辿っている要素番号と左、右の子探索済みフラグ。
3つの情報を1つの整数型変数に格納するために、要素番号を2ビット左にシフトし、空いた2ビットにフラグを論理和。
 もし子を辿るならば、現在見ている要素の配列要素番号をスタックにpushし、視点を子の要素に移す。この時、該当するフラグをセットする。
 子をすべて辿り、親の要素に戻るには、スタックからpopする。
 スタックが負の値になる=空ならば、終了です。repeatではなく、while文で書くべきでしょう。


またもうちょっと説明文書き換えるかも。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : HSP3 アルゴリズムとデータ構造

コメントの投稿

非公開コメント

ブログ移転のお知らせ
ブログをshonen.hateblo.jpに移転します. 新規の記事はこちらに投稿します.
プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
635位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
94位
アクセスランキングを見る>>
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。