第32回
データ構造(11)~構造体を前後に移動できる双方向リンク

構造体の双方向リンク

前回紹介した一方向のリンクは、このように非常にシンプルで扱いも楽です。しかし、1つ大きな欠点があります。先頭から次々にリンクをたどっていくことはできても、前に戻ることができない──という点です。

前に戻るためのポインタ

「前に戻れない」理由は、構造体のメンバに『次の構造体へのポインタ』しか含んでいないためです。先頭方向にも戻れるようにするためには、メンバに『1つ前の構造体へのポインタ』を追加すればよいわけです。

  typedef struct _result{
    short int id;
    char name[16];
    short int score;
    struct _result *prev; -------- 1つ前を示すポインタ
    struct _result *next; -------- 次を示すポインタ
  } result;

先頭の構造体で1つ前を示すメンバ(*prev)と、最後の構造体の次を示すメンバ(*next)にはNULLを代入します。すると、複数の構造体が図1のようにつながります。

このような形を『構造体の双方向リンク』と呼びます。


前後に移動できるプログラム

前回と同じ氏名と成績(点数)を保持する構造体を、双方向リンクでつなぐプログラムを作ってみましょう。今度は、現在参照している構造体の前後を自在に移動できるので、プログラムは以下のような仕様にします。

[N]キーを押すと次のデータを表示
[B]キーを押すと1つ前のデータを表示
[Q]キーを押せばプログラムが終了
先頭データを表示しているときに[B]キーを押しても何もしない
最後のデータを表示しているときに[N]キーを押しても何もしない

リスト2:双方リンクで構造体を前後に移動できるようにしたプログラム(ex3202.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(void)
{
  /* 構造体 result を定義 */
  typedef struct _result{
    short int id;
    char name[16];
    short int score;
    struct _result *prev;
    struct _result *next;
  } result;

  int i;              /* ループカウンタ */
  result *p, *start;  /* 構造体のポインタ */
  char ans[4];    /* 入力用 */
  result *now;    /* 現在注目している構造体を示す */
  result *q;      /* メモリ解放用 */

  /* 元データを配列で準備 */
  char _name[5][16] = {"Taro","Hanako","Sayaka","Miki","Hiroshi"};
  short int _score[5] = {50, 60, 70, 80, 30};

  /* 配列の値を構造体のリンクに */
  for (i=0; i<5; i++) {
    if (i==0) {
      /* 先頭の構造体を生成 */
      p = malloc(sizeof(result));
      start = p;  /* 先頭を保存 */
      /* 先頭のみ1つ前にNULLを代入 */
      p->prev = NULL;
    } else {
      /* 次の構造体を生成 */
      p->next = malloc(sizeof(result));
      /* 次の1つ前=現在の構造体 */
      p->next->prev = p;
      /* 次の構造体に移動 */
      p = p->next;
    }
    /* IDはカウンタ変数から生成 */
    p->id = (short int)i+1;
    /* 2項目を代入 */
    strcpy(p->name, _name[i]);
    p->score = _score[i];
    p->next = NULL;
  }

  /* キー待ちのループ */
  now = start;
  printf("ID\tName\tScore\n");
  printf("%04d\t%s\t%d\n", now->id, now->name, now->score);

  printf("? ");
  gets(ans);
  while ((ans[0] != 'Q') && (ans[0] != 'q')) {
    switch (ans[0]) {
      case 'N' :
      case 'n' :
        if (now->next != NULL) {
        now = now->next;
        }
        break;
        case 'B' :
      case 'b' :
        if (now->prev != NULL) {
          now = now->prev;
        }
      defaulet : break;
    }
    printf("%04d\t%s\t%d\n", now->id, now->name, now->score);
    printf("? ");
    gets(ans);
  }

  /* 構造体のリンクをたどってメモリを解放する */
  p = start; -------- ポインタを先頭に位置付ける
  while (p != NULL) {
    q = p->next;  /* 次へのポインタを保存 */
    free(p);
    p = q;
  }

  return (0);
}

サンプルの実行結果

このプログラムの実行結果は、例えば以下のようにnなります。[N]または[B]キーを入力して、データの表示が前後に移動することを確かめてください。[Q]キーを入力するとプログラムは終了します。

配列の値を書き換えれば、異なるデータを表示することができるのは、前回のサンプルと同じです。

画面1:キーの入力でデータを前後に移動できるプログラム(ex3202.exe)の実行結果
0001    Taro    50
? n
0002    Hanako  60
? n
0003    Sayaka  70
? n
0004    Miki    80
? b
0003    Sayaka  70
? n
0004    Miki    80
? n
0005    Hiroshi 30
? n
0005    Hiroshi 30
? b
0004    Miki    80
? b
0003    Sayaka  70
? b
0002    Hanako  60
? b
0001    Taro    50
? b
0001    Taro    50
? b
0001    Taro    50
? n
0002    Hanako  60
? q