ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

データ構造の雑記

いや~、データ構造って色々ありますよね。

私も、だいたい知っているというのは多いのですが、どれもなんとなくでして、

ちゃんと使いこなしていると言えるのは配列ぐらいでした。


ただ、最近はスタック、キュー、連結リストを学習したんですよ。


放送大学という大学兼テレビ局が、データ構造を教えてくれる番組をやっていて、それで学習しました。


放送大学という大学がありまして、なんとテレビ局を持っていて、タダで授業を放送してくれるんですよ。

詳しい説明はしませんが。

普通はBSのチャンネルなんですが、関東地区だと地上波の12chでやっています。

関東地区の人はご存じの方も多いんじゃないでしょうかね。


嬉しい事に、放送大学では今年度から情報コースというものが出来て、情報の授業がけっこう増えました。


その中で、「データ構造とアルゴリズム」という授業(番組)が始まったのです。

この授業では、1回1時間、全15回にわたって、前半は色んなデータ構造、後半はアルゴリズム(ソート、探索等の定番アルゴリズム)の解説をしています。


始まったとき、それを録画したにもかかわらず、長いこと放置していたのですが、最近、見始めました。

そうでもないか…?


現在、第5回まで見たのですが、

第1回がC言語の機能の簡単な解説。

第2回 … 配列
第3回 … スタック、キュー、優先度付きキュー、両端キュー
第4回 … 片方向連結リスト、双方向連結リスト、循環リスト
第5回 … ツリー、バイナリーツリー、全バイナリーツリーと完全バイナリーツリー、バイナリーサーチツリー

という内容でした。

この授業で、スタック、キュー、連結リストを学習したわけです。

バイナリーツリーとかいうより、二分木、二分探索木と言ってもらったほうが分かりやすいのですが…。
(タイトルだけ見たとき、バイナリデータを保存する木だと思ってしまった)




いやぁ、データ構造の実装を覚えるのは面倒なら後でいいと思うのですが、
.NET Frameworkなどで提供されているデータ構造を、とりあえず覚えて使えるようになる。

使う能力はC#であっても問われると思うんですよ。


色々なデータ構造を知っていれば、開発の場において、苦労して既存のデータ構造もどきを作る必要もなくなりますし、

メモリ消費量や処理速度に応じて最適なものを選ぶ能力も付きます。

C#もさすがに、データ構造は選んでくれませんので。


というわけで、データ構造を覚えて使うことぐらいは出来るようにならなきゃな、と思っています。


データ構造の学習は、放送大学の例の授業「データ構造とプログラミング」でやっていこうと思います。

まだ見ていない回の、第6回はバイナリーサーチツリーの応用ですね。

第5回ではバイナリーサーチツリーの定義だけしか説明しなかったので、
第6回ではその用途について説明するんだと思います。




ところで第5回をみて一つ疑問があるのですが、子孫サブツリーの違いはどこなんでしょうかね。


あるノードの子、孫、さらにもっと下のノードを全て含めて子孫。

あるノードに属していて、それだけでツリーとしての構造を持っているノードたちをサブツリー。

んーっと、どういうことでしょうか…。


A( B( D( F, G), E( H, I) ), C)

というツリーがあるときに、Bの子孫は、D,F,G,E,H,I。

Bのサブツリーは、Dをルートとするツリーと、Eをルートとするツリー。

と考えていいのかな。


つまり、子孫というのは、ツリーの構造を無視して、あるノードの下にあるノード全てのことを指していて、


サブツリーは、あるノードに属している子をルートノードとみなし、その下まで全部、一つのツリーとしてみなしたとき、

その一つ一つのツリーのことを、サブツリーと言っているんじゃないかなと。


ですから、あるノードのサブツリーの数は、ノードの子の数と同じ、ということじゃないでしょうかね。


うむ、多分そうですね。




最後に余談ですが、.NETのSystem.Generic.Collections.List<T>って連結リストじゃないんですね…。

配列にデータを格納していって、足りなくなったら自動で確保してくれるだけのものだそうで…。


連結リストはLinkedListという名前であるそうです。

ずっとListが連結リストだと思っていたのに…。


.NETで提供されるデータ構造については、ufcpp.netでC++ STLとの比較表として書いてあります。

コレクション概要 (アルゴリズムとデータ構造)
http://ufcpp.net/study/algorithm/collection.html




いや~、久しぶりに記事書きましたね。
しかも長文ですね。

データ構造は大事ですから、覚えたほうがいいんですよね。

頑張るぞ!お~!

tag:

コメント

No title

ダウンロードリンクを変更しておきました。
すいません。

  • 2013/08/30(金) 23:41:03 |
  • URL |
  • funcHM #-
  • [ 編集 ]

Re: funcHM

すいません、返信遅れました。
ダウンロードしてみます。

あの、このくらい、わざわざコメントしてこないでいいですよ…。

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/294-33464bc2
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。