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

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

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

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

２分探索木

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

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