next up previous
Next: About this document Up: ポインタと循環リスト Previous: ポインタの利用

循環リスト

一般に配列は,添字を用いて,何番目のデータでもすぐに参照できるという非常 に便利な特性を持っている.しかし,その順番が固定されており,順番を入れ替 えるとか途中の要素をひとつ抜き取る,という処理を行うためには,操作対象か ら後ろのデータをすべて移動してあげる必要がある.

figure103

これに対して,順番の入れ替えや抜き取り,新たなデータの挿入などを用意にす る手法として,リストというものが利用される.

リストとは,構造体を用いて,その中に次の順番のデータへのポインタを保持す ることによって,順番を管理する構造である.

このような構造を用いると,構造体中のポインタの値を適宜変更してあげるこ とによって,順番を自由に変更することが可能である.

例えば,図中の2番目の要素を一番最後にしたいときには,次の図のようにポイン タを差し替えてあげると,データ自体は一切動かさずに順番の変更が可能となる.

figure115

(4)
実際に変化しているのはどのポインタか確認せよ.

このようなリスト構造を単方向リストと呼ぶ.単方向リストでは,データ を前から順番に検索していくときには便利であるが,逆方向の検索ができないた め,逆向きにもポインタを持ってあげるリストが双方向リストである.

figure131

単方向リストの最後の構造のnextをNULLポインタにせずに,先頭の要素を 指すようにしたものが,循環リストであるgif.循環リストを用い ると,先頭を指すポインタを動かすだけで,全体の順番を変えることが可能と なる.

figure146

(5)
上の図で,*topと書かれているのが先頭の要素を指すポイン タであるが,これを左から2番目に変える(図中点線)と,リスト上の順番がどの ように変わるか,確認せよ.
(6)
図の一番右側のdata5data2data3の間に挿入 する場合の手順を考えよ.その後で,data3を削除する手順を考えよ.




2000年09月06日 (水) 18時26分54秒 JST