プログラミング技法とデータ構造

循環リスト

連結リストでも，リスト末端がない構造がある．末尾のセルが最初のセルに連結されており，リストが循環しているタイプのものを「循環リスト」と呼ぶ．

LIST head; //循環リスト構築用で，最初のひとつ.構造体そのものとして宣言
head.next = &head;  //空のリストの場合nextは自分. 

循環リストをたどりながら処理する場合の基本形は次のとおりである．この基本形では，先頭のheadを特別扱いとし，headには値を書き込まずhead以下だけを使用する考えである．リストをたどり最後にheadに戻ってきたところで終了させる．値を格納しないheadのようなノードのことを「番兵」と呼ぶ．(リスト構造に限らず配列の最後に特殊な値を入れておくことなども一種の「番兵」である．)

LIST *p;
for(p = head.next; p!=&head; p=p->next)
{
  *pを使った処理
}

循環リストは，決められた数のデータを貯蔵する時などに使用することができる．例えば100個のデータを貯蔵するときには，100個のセルからなる循環リストを作成する．このリスト先頭から順にデータを格納していくと，100個以上のデータが存在する場合には，自動的に末尾から先頭に戻ってデータが書き込まれることとなりデータが先頭から上書きされることになる．これは常に最新の100個のデータを保存できている状態を保つことになる．このように，常に有限個の最新データを保持する目的の循環リストのことを特に「リングバッファ」とも呼ぶ．

リングバッファとして使用する場合には，headは意味を持たず，リング状に連結したリスト構造のどこが先頭か末尾かは意味をもたない．データを書き込む位置と読み出す位置だけが存在することとなる．次の例では，あらかじめバッファとして必要な量のリスト構造を作っておき，そこに読み書きするために，最初のデータ位置と最後のデータ位置を示すポインタを用意しておき，初期化しておく．

LIST *read; //読み出す位置を示すポインタ
LIST *write; //書き込む位置を示すポインタ

read = write = &head;  //初期状態ではどちらも便宜上設定した先頭

データを書き込むときには，書き込んだ後ポインタを一つ進める．しかし，進める先がもしも読み出し位置である場合，つまり，まだ読み出されいないデータがそこにある場合は，このリングバッファに全部データが書き込まれた状態であることを意味する．

実際にプログラムでは，その時に，そこで書き込みを行わずに，書き込みを待たせたり異常終了させなければならない．

write->data = 書き込むデータ;
if(write->next != read)
  write = write->next; 
else
  exit(EXIT_FAILURE); 
  //まだ読み出されていないデータを破壊しないように，データがあふれたところで異常終了
  //もしも書き込み位置の次が読み出し位置でなければ，位置を進める

データを読み出すときには，

if(read != write){
  読み込むデータ = read->data;
  read = read->next;
} 
else
  読み込むデータ　= エラーを示す値;

双方向リスト

前後二方向へ連結し，単純な連結リストのように最初から最後の方向にだけデータを検索するのではなく，必要に応じて前のデータにも戻れるように拡張されたものを双方向リストと呼ぶ．

typedef struct list2{
  struct list2 *prev;
  int data;
  struct list2 *next;
} LIST2;

双方リストは循環リストとして使用することが多い．

この双方向リストへの追加・削除は片方向リストの時の追加・削除と同様に可能であるが，双方向の二つのポインタとも接続しなおす必要がある点に注意を要する．

追加する場合には次のように行う．特定のセル位置を示すpがあったとして，pとその次のセルの間にnewを追加する場合の例である．

  LIST2 *p;   //この次に追加
  LIST2 *new; //新しいセル
  
  new = malloc(sizeof(LIST2));

  new->next = p->next; //新セルのnextは，今のpの次
  new->prev = p;       //pの後に追加するから，新セルの前はp
  p->next = new;       //pのnextをnewに変更
  new->next->prev = new; //次のセルのprevをnewに変更

削除する場合は次のようになる．

  LIST2 *p;   //この次に追加
  LIST2 *del; //削除用
  
  del=p->next;         //削除したいセル
  p->next = del->next;    //次の次へ
  del->next->prev = p;    //次のセルのprevをpに変更
  delete(del);

木構造

リスト構造とよく似ているが，接続関係を親子関係に見立てたもの木構造と呼ぶ．

一番根元ノードを木に例えてルート(根)と呼ぶ．また，次への接続がない末端のノードをリーフ(葉)と呼ぶ．

木構造は，次回紹介するように，探索問題のためのデータ構造に使用されることが多い．