データ構造/循環リスト - nkym_memo @ ウィキ

循環リスト(circular list)

• 連結リストにおいて最後がNULLでなく、任意のセルにつながっているもの 各要素はリング状に結合されている。
• 双方向リストと組み合わされて使用される。

循環リストの操作

• 要素を表すセル
  • next 次のセルへのポインタ
  • value セルの値(整数)
  • ptr 循環リストへのポインタ（NULLの場合循環リストは空）

struct CELL{
	struct CELL *next;　
	int value;　　　　　
}
struct CELL *ptr;

循環リストを順にたどる

ポインタを順にたどっていく途中で、ポインタの値が変数ptrと等しい ⇒１周して最初のセルに再び戻ってきたことを示す

struct CELL *ptr,*p;

if(ptr !=NULL){
	p = ptr;
	do{
		p = p->next;
	}while(p !=ptr);
}

リストの頭を用いた循環リスト

• リストの頭(list head) リストの先頭および末尾を示すセル

変数で定義すると、

struct CELL head;

となり、最初の要素へのポインタはhead.nextにセットされていることになる。

循環リストの表現法

• リストの頭を使う場合の注意点
  • リストを順に処理する場合、リストの頭をスキップする必要がある。 　⇒循環リストを回転させることができない
  • セルの共通な情報をリストの頭に格納することができる 　⇒複合したデータを構成するのに利用

struct CELL head,*p;

for(p = head.next; p != &head; p = p->next){
}

---

参考文献

• 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤嘉雪,ソフトバンククリエイティブ,1998)