今日の記録 2020/6/19
仕事
ワイヤーフレーム作成に、 JUSTINMIND というものを使ってみている。
これで作ったものを見せた時に、「横幅が◯◯だったらどう見える?」と言われて実際に見せれなくて困り、こうなると結局インブラウザデザインするしかないのか……?と絶望したのだが、上記のソフトにはレスポンシブなデザインにも対応していた。
これを利用する場合、最初は相手にもこのソフトを導入してもらう必要があってきびしいかなと思ったのだが、画面共有で見せるという手段があった。今度これを使ってレスポンシブなものも作成してみる。
勉強した
みんなのデータ構造 - P125 問6-7 の準備
昨日問6-7を実装するには幅優先探索をする必要があることに気付いたので、 Erlang(というか関数型プログラミング全般)では、二分木の深さ優先探索をどのように実装すればよいか、ということを小一時間考えた。そして、引数のひとつをスタックとして利用すれば良いだけだ!とようやく気付いた。以下のように深さ優先探索を、 Erlang を使って末尾再帰で実装できた。
depth_first(Tree) ->
search_process_for_df([Tree], []).
search_process_for_df([], Visited) ->
lists:reverse(Visited);
% 子を持たないノードであれば探索したことにする
search_process_for_df([{V, nil, nil} | Rest], Visited) ->
search_process_for_df(Rest, [V|Visited]);
% 子を持つノードの場合、まずはその値を探索済みに入れ
% そして (nil でなければ)右の子を優先して両方の子を Stack に push する
% つまり左の子を優先して探索する
search_process_for_df([{V, Left, nil} | Rest], Visited) ->
search_process_for_df([Left | Rest], [V|Visited]);
search_process_for_df([{V, nil, Right} | Rest], Visited) ->
search_process_for_df([Right | Rest], [V, Visited]);
search_process_for_df([{V, Left, Right} | Rest], Visited) ->
search_process_for_df([Left, Right | Rest], [V|Visited]).
depth_first_test() ->
Tree1 = {1, nil, nil},
[1] = depth_first(Tree1),
Tree2 = {1, {2, nil, nil}, {3, nil, nil}},
[1, 2, 3] = depth_first(Tree2),
Tree3 = {1, {2, {3, nil, nil}, {4, nil, nil} }, {5, nil, nil}},
[1,2,3,4,5] = depth_first(Tree3).
明日はこれを応用して、 まずは in-order でのツリーへの訪問番号の付与実装を考えてみる。
この記事が気に入ったらサポートをしてみませんか?