ホーム » スタッフ » 斉藤徹 » 循環リスト・双方向リスト

2007年9月
 1
2345678
9101112131415
16171819202122
23242526272829
30  

最新の投稿(電子情報)

アーカイブ

カテゴリー

循環リスト・双方向リスト

循環リスト

OS におけるプロセス待ち行列などは、最後のデータの次は先頭から再び巡回するといった 利用が多い。単純リストでも、末尾に NULL をいれずに、先頭のデータへのポインタを入れて 循環リストにすれば、『巡回』操作が簡単になる。

FIFO の様なデータでも、循環リストを使えば、書き込みポインタと読み出しポインタを 1つの変数で管理できるので便利。

双方向リスト

単純リストは、シーケンシャルアクセスしかできないので、『1つ前』でさえ困難。 テキストエディタでは、カーソル上下移動などの際に、『1つ前』の参照は多い。 双方向リストにすれば、1つ前参照も簡単になる。

双方向リストを使ったエディタでは、先頭行や末尾行の利用頻度も高い。 しかし先頭行ポインタと末尾行ポインタを別に管理するのは、面倒。 先頭行のセルと末尾行セルを循環リストにして『双方向循環リスト』にすれば、問題解決。

2分木

2分探索法の説明のあと、イメージ図で2分木を説明しただけ。 後期最初にもう一度説明が必要だろう。 循環リストのデータ挿入あたりを出題を匂わせる。 昨年度と比較すると、リストによる集合演算のネタを説明していない。 出題の前置きできちんと説明すれば、集合演算もテスト範囲には十分だろう….