ホーム » スタッフ » 斉藤徹 » 双方向リストと2分探索木

2004年10月
« 9月   11月 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最近の投稿(電子情報)

アーカイブ

カテゴリー

双方向リストと2分探索木

プログラムコンテスト参加者の多いクラスだし、 一昨日のコンテストの感想を何人かの学生さんに聞いてみる。 他高専の実力をみて、講義のレベルアップを期待する学生さんがいるか と思ったけど、 やはり期待だけだった。

双方向リストと応用テクニック

前回の講義の双方向リストの説明2回目。 前講義で説明した insert() の問題点として、 先頭と末尾への挿入に特別処理が必要な点を説明し、 対処法として番兵(sentinel)のテクニックを紹介する。

さらに、双方向リストでの番兵の定番として、 循環双方向リストへの応用を紹介する。

2分探索木

実際の世界では、双方向リストの出番は少ないし、次のネタに進む。 2分探索木の説明として、直観的に処理をイメージして欲しかったので、 0〜100までのデータを素早く探したいという前置き後、 すぐに2分木の具体例のイメージ図を書き、 『××のデータを探すのに要する比較回数は?』、 『△△のデータは、木のどこにつなげばいいか?』 と聞いてみる。どの学生さんも、左右の枝の定義を具体的に説明しなくても、 回数やら接続箇所は答えられるみたい。

この後、処理回数やオーダの話し、節と枝の用語などを説明し、 最後に構造体宣言を見せて、来週につなげる。