今回は循環リストを見ていきます。循環リストは、リストの末尾の要素の次には、 先頭の要素があるという構造です。他の特徴は線形リストと同じです。概念図は次のようになります。
見ての通り、末尾の要素から先頭の要素への線が増えただけで、他は線形リストと同じです。
では、Ｃ言語で表現してみましょう。
#include <stdio.h>
#include <stdlib.h>
struct LIST
{
int data; /* 具体的なデータ */
struct LIST* next; /* 次の要素へのポインタ */
};
struct LIST head; /* リストの先頭要素（ダミー） */
/* プロトタイプ宣言 */
void addlist(void);
void deletelist(void);
void showlist(void);
int main(void)
{
char command;
head.next = &head; /* リストは循環しているので、先頭の次は先頭 */
do
{
puts( "コマンドを入力して下さい" );
puts( "循環リストに要素を追加：a" );
puts( "循環リストから要素を削除：b" );
puts( "循環リストの内容を表示：c" );
puts( "終了：q" );
scanf( "%c", &command );
switch( command )
{
case 'a': /* 追加 */
addlist();
break;
case 'b': /* 削除 */
deletelist();
break;
case 'c': /* 表示 */
showlist();
break;
case 'q': /* 終了 */
break;
default: /* 無効 */
puts( "コマンドが正しくありません" );
break;
}
puts( "" );
fflush( stdin );
}while( command != 'q' );
return 0;
}
/* 循環リストに要素を追加する */
void addlist(void)
{
struct LIST* p, *q, *newcell;
int data;
puts( "追加する要素の値を入力して下さい" );
scanf( "%d", &data );
p = head.next; /* 先頭要素の次の要素のアドレス */
q = &head; /* 直前の要素を記憶しておく */
if( p != NULL ) /* リストは空ではないか */
{
while( p != &head ) /* 先頭要素に戻ってきたら循環したことになるので終了 */
{
q = p; /* 直前の要素を記憶しておく */
p = p->next; /* 次の要素へ進む */
}
}
/* 新しく追加する要素のためのメモリ領域を確保する */
newcell = malloc( sizeof(struct LIST) );
if( newcell == NULL )
{
puts( "メモリ不足" );
return;
}
newcell->data = data; /* 新しい要素のデータを設定 */
newcell->next = p; /* 新しい要素の次の要素へのアドレスを設定 */
q->next = newcell; /* 新しい要素の直前の要素のnextに、新しい要素のアドレスを設定 */
}
/* 循環リストから要素を削除する */
void deletelist(void)
{
struct LIST *p, *q;
int data;
puts( "削除する要素の値を入力して下さい" );
scanf( "%d", &data );
p = head.next; /* 先頭要素の次の要素のアドレス */
q = &head; /* 直前の要素を記憶しておく */
if( p != NULL ) /* リストは空ではないか */
{
while(p != &head && data != p->data)
{
q = p; /* 削除位置の直前の要素のnextを後で設定するために、
削除位置の直前の要素のアドレスを記憶しておく */
p = p->next; /* 次の要素へ進む */
}
}
if( p == &head ) /* 一致する値がないままリストの末尾まで来た */
{
puts( "指定された要素はリスト内に存在しません" );
}
else
{
q->next = p->next; /* 削除する要素の直前の要素のnextポインタを再設定 */
free( p ); /* 要素はmallocで確保されているのでfreeで解放する */
}
}
/* 循環リストの内容を表示する */
void showlist(void)
{
struct LIST *p;
for( p=head.next; p!=&head; p=p->next )
{
printf( "%d\n", p->data );
}
}
|
前章の線形リストのときと同じような形に統一しました。
線形リストのときと違うのは、リストの要素を辿る方法だけです。線形リストなら、最後の要素のnextポインタは NULLになっていたので、NULLが見つかるまで辿っていけばリストの末尾まで辿ることができました。しかし、循環リスト では、「最後の要素」という考え方ができません。先頭に戻ってきてしまうからです。そのため、普通にnextポインタ を辿り続けると、いつまでたっても終了しません。この部分さえ克服できれば循環リストは実現できます。
線形リストのときと同様に、実際にはデータを持たないダミーの要素（head）を用意します。要素を辿るときには、 nextが示すアドレスとheadのアドレスとが一致したかどうかを調べれば、循環してきたかどうかが分かります。head 自体にはデータがないので、最初に見る要素はhead.nextとすれば、いきなりp == &headという条件に引っかかること はありません。
上の例では、headというダミーの要素を使いました。この方法を取ると、要素を辿るのは比較的簡単になりますが、 headのデータ部分は完全に無駄な領域になってしまいます。ここを無駄にしないために、リスト内の全ての要素に共通 な何らかのデータをheadに隠し持っておくという方法も使えます。
headを使わずに循環リストを作ることも可能です。その場合、要素を辿るときに、どこから辿り始めたのかを記憶 しておき、その位置まで循環して戻ってきたら辿るのをやめるようにします。
なお、headを使わない場合には、リストが空のときの表現にはNULLを使うことになります。リストが空のときに リストを辿ることはできないので、空かどうか調べる必要があります。リストを辿る際には、最初に空かどうか調べ、 さらに辿り終わる条件をループで確認することになります。この部分で条件式が２つ登場するのが、headを使う方法 と比べて少しだけ厄介なところでしょう。
ソースは示しません。前章の線形リストと、今回のheadを使う例を理解できれば、head を使わない書き方は分かるはずです。