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

循環リスト

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

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);

木構造

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

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

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

探索問題とは

配列や線形リスト，木構造などのデータ構造を使って蓄えられた情報の中から，必要な情報や条件(キー)と一致する情報を探し出すことが探索問題である．

例えば，次のように，氏名，住所，電話番号などの個人情報を蓄えるデータ要素を考える．データベースシステムなどの情報システムでは，このようなデータ要素の単位をレコードと呼ぶ．

  typedef struct record {
    int id;            //ID(検索キー)
    char name[40];     //氏名
    char address[80];  //住所
    char phone[12];    //電話番号
    int age;           //年齢
  } RECORD;       

このようなレコードが数千件，数万件蓄えられている配列データやデータベースから，目的となる人物のデータを取り出したり，例えば「年齢が20才以上の人物」，「住所が埼玉県」などの条件に一致するレコードを探し出すことが，探索問題である．

目的となる人物を探し出すためには，氏名だけでは，同姓同名の人が存在することがあるため，本人と別人を確認するために住所など他の項目も比較する必要が出てきてしまう．このため，一般的なデータベースシステムでは，通常はIDとして全データで重複のないことが保証される番号や記号を，別途割り当てておく．こうした検索用の項目(フィールドと呼ぶ)のことを「検索キー」と呼ぶ．

仮に，このようなデータが線形リストになっていた場合には，先頭から順にリストをたどって検索キーが一致するレコード(線形リストのノード)を探すことになる．数千件程度のデータならば，特に工夫をしなくとも，検索時間の長さは実用上問題にはならない．しかし，数万件を越えると高速化のための仕掛けやアルゴリズムの工夫が必要となる．例えばデータの五十音順に連結された線形リストに対して，「あ」「か」「さ」「た」「な」など各段の先頭位置へのポインタを用意しておければ，途中を飛ばして近い位置から探索を始められる．

次に，これらのアルゴリズムについて基本的なものを紹介する．

二分探索

二分探索(binary search)は，検索キーの大きさ順などでソート(整列)されている状態の配列データを前提とし，その中から効率よくキーが一致するデータを探し出すアルゴリズムである．

これは，例えば本の中から目的のページを探し出すときに，人間もよくやっている方法である．200ページの本があって，136ページを開きたかったとする．大抵の人は，まず真ん中くらいを適当に開けて，開いたページが目的の136ページよりも前か後ろか確認する．もしも後ろだったら，今度はそれより前の方でまた適当なページ(しかし，さっきの半分より確実にすくない1/4程度，半分の半分程度のページ)を開いてみる．そして目的のページとの前後関係を確認して，またさらに少ないページだけずらして開き，最終的に目的のページにたどり着く．

二分探索は，これを機械的に行う．最初にデータ配列のちょうど半分の位置の要素の検索キーを確認し，その前後関係から次は半分の半分，1/4のところを確認し，さらに1/8,1/16とずらしていきながら，最終的に目的の要素を探し出す．

これをC言語で書くと次のようになる．

 #define N 100;  //データの個数
 RECORD r[N];    //RECORD型が上記個数分，ID順番で整列しているとする
 int key;        //探したいキー

 int head; //探索範囲の先頭
 int tail; //探索範囲の最後
 int half; //真ん中
 head = 0;
 tail = N-1; //C言語で配列は0番からN-1番まで

 do {
   half = (head+tail)/2;
   if( r[half].id == key ){   //keyと一致したら探索終了
      printf(r[half]の中の必要な項目を表示); 
      exit(EXIT_SUCSESS);
   }
   else if( r[half].id < key )
      head = half+1;
   else
      tail = half-1;
 } while(head <= tail)
 exit(EXIT_FAILURE); //探索失敗(keyが見つからなかった)

木を使った探索

木を使った探索手法がある．必ず大小関係によって木の右か左の枝かに配置することで，後から効率的に目的の葉を探すことができる．