ホーム » 2004 » 10月 » 12

日別アーカイブ: 2004年10月12日

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

最近の投稿(電子情報)

アーカイブ

カテゴリー

そーじ

システム設計の時間に、学生さんが資料まとめとして各部屋に別れてくる。 プログラムコンテスト本戦参加の学生さんには、演習室の後かたづけを頼む。

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

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

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

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

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

2分探索木

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

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