第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