第31回
データ構造(10)～構造体をポインタでつなぐ
技術コラム > 第31回 データ構造(10)～構造体をポインタでつなぐ > 複数の構造体をつなぐ

複数の構造体をつなぐ

malloc関数の確保するメモリ領域の場所は、そのときの状態によってまちまちです。そのため、配列のように複数の構造体型変数が連続して確保されるとは限りません。メモリ上に生成した複数の構造体を、連続して扱う手段が必要になります。

構造体のリンク構造

それぞれ異なる場所に確保された、同じ型の複数の構造体を連続して扱うためには、構造体の中に『つながり』を示すための仕掛けが必要になります。次の構造体を示すため、構造体の中に『自分自身と同じ型の構造体のありかを示すポインタ』を用意するのです。このような形の構造体を「自己参照型構造体」と呼びます。

struct _result {
  int id;
  int score;
  struct _result *next; ---- 次の構造体を示すポインタ
};

最初に先頭となる構造体のメモリを確保したら、それ以降に確保された構造体（のためのメモリ領域）の先頭ポインタを『1つ前の構造体のメンバ“next”に保持する』ようにします。

これで、ポインタをつたって次々とつながっていく「構造体のリンク構造」ができあがります。


TOP

間接メンバ参照演算子～->

自己参照型構造体をリンクしていった場合、個々の構造体はポインタによって示されます。ポインタで示される構造体のメンバは、『間接メンバ参照演算子』で参照することになります。

間接メンバ参照演算子は「->」という記号で、書式は以下のようになります。
<構造体型ポインタ変数名>-><メンバ名>

先に掲げた構造体“struct _result”のメモリを確保し、そのポインタを“p”に受け取った場合、メンバの“id”に「1」を、“score”に「80」を代入するなら、以下のようなソースを記述します。
p = malloc(sizeof(struct _result));
p->id = 1;
p->score = 80;

TOP

構造体をつなぐ

以上のことを踏まえて、構造体をポインタで次々につないでいく処理を書くと、リスト1のようになります。

result *p, *start;
として構造体型のポインタを2つ宣言しています。pは繰り返し処理の作業用、startは構造体をつないだリストの先頭を保持します。

続いて、forループで処理を10回繰り返します。ループの中では、1回目と2回目以降の繰り返しとで処理を切り替えます。

ループ1回目の処理では、malloc関数で生成した構造体へのポインタをpに代入し(1)、さらにその値をstartにも代入します(2)。これで、リンクの先頭がstartに保持されます。

2回目以降の繰り返し処理でもmalloc関数で構造体を生成しますが、そのポインタをpではなく『直前の繰り返しで生成された構造体へのポインタpのメンバnext（p->next）』へ代入します(3)。

この段階で、先に生成した構造体のメンバnextが、続いて生成した構造体を指し示している状態となります。

最後に、先に生成した構造体のメンバnext（次に生成した構造体のアドレスを保持）の値をpに代入します(4)。

これで、次の繰り返しでは、pが2番目に生成された構造体を示すようになります。そして(3)に戻り、3番目の構造体を生成して4番目の構造体（pで参照できる）のメンバnextにそのポインタを代入……と、処理が繰り返されます。

最後にforループを脱出したら、pは一番最後の構造体を示しているので、そこから先は存在しません。そこで、「これで終わり」ということを示すため、pのメンバnextにNULLを代入します(5)。

リスト1：10個の自己参照型構造体を生成してポインタでつないでいく処理
  /* 構造体型“result”を定義 */
  typedef struct _result{
    short int id;
    short int score;
    struct _result *next;
  } result;

  int i;    /* カウンタ */
  result *p, *start; /* 構造体型のポインタ */

  for (i=0; i<10; i++) {
    if (i == 0) {
      /* 1回目のループのみ -- 先頭の構造体を生成 */
      p = (result)malloc(sizeof(result)); ----------- (1)
      start = p; ------------------------------------ (2)
  } else {
    /* 2回目以降 -- 構造体へのポインタを next に保存 */
    p->next = (result)malloc(sizeof(result)); ------- (3)
    /* メンバ next の値を p に渡す */
    p = p->next; ------------------------------------ (4)
  }
        :
    メンバの初期化処理など
        :
  }
  p->next = NULL; ----------------------------------- (5)
        :

TOP

つながった構造体を次々と参照する

構造体型のポインタpにメンバnextの値を渡し、pが次に生成された構造体を次々に指し示すようにするところがミソです。

このような形でリンクされた構造体の形を「一方向リスト」（または「片方向リスト」）と呼びます。先頭から順にメンバnextの値をたどっていくことで、複数の構造体のメンバを参照できます。メンバnextがNULLであれば、それがリストの最後です。

例えば、リンクの先頭の構造体を示すポインタがpとすれば、以下のようなwhileループでリンクをたどっていけます。

まず(1)の箇所でwhileループの条件として「pがNULLでない間」を指定します。そしてループの最後では、pに現在参照している構造体のメンバnextを代入し、次の構造体を示すようにします。このときnextがNULLなら、ループの条件から外れるので繰り返し処理が終わります。

while (p != NULL) { -------- (1)
      :
  メンバを参照する処理
      :
  p = p->next; ------------- (2)
}

TOP

氏名と点数を構造他のリンクでつなぐ

これまでのことをまとめる意味で
「氏名と点数」を順に入力
そのデータを構造体のリンクに格納
リンクされた構造体をたどってデータを表示
という処理を作ってみます。サンプルなので、入力件数は5件に限定しています。

こういった処理は、実務的なプログラムではデータをファイルやデータベースから順次読み込んでいくことになります。それでは処理が複雑になるため、サンプルでは以下のようにして氏名と点数を配列で準備する形にしました。このように、配列は変数を宣言するときに{ }で囲んで要素を初期化できます。
char _name[5][16] = {"Taro","Hanako","Sayaka","Miki","Hiroshi"};
short int _score[5] = {50, 60, 70, 80, 30};

処理の流れは先に紹介した形をベースとしているので、コメントを読みながら動作の仕組みをたどってみてください。実行結果は以下のようになります。ソース中の配列を初期化している箇所を書き換えれば、異なる値で試すことができます。
C:\CLANG>exe\ex3101
ID      Name    Score
0001    Taro    50
0002    Hanako  60
0003    Sayaka  70
0004    Miki    80
0005    Hiroshi 30
C:\\CLANG>

リスト2：氏名と点数の配列を構造体のリンクに格納して表示するプログラム(ex3101.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 *next;
  } result;

  int i;              /* ループカウンタ */
  result *p, *start;  /* 構造体のポインタ */

  /* 元データを配列で準備 */
  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;  /* 先頭を保存 */
    } else {
      p->next = malloc(sizeof(result));
      p = p->next;
    }
    /* IDはカウンタ変数から生成 */
    p->id = (short int)i+1;
    /* 2項目を代入 */
    strcpy(p->name, _name[i]);
    p->score = _score[i];
    p->next = NULL;
  }

  /* 構造体のリンクをたどって先頭からメンバを表示 */
  printf("ID\tName\tScore\n");
  p = start;  /* ポインタを先頭に */
  while (p != NULL) {
    printf("%04d\t%s\t%d\n", p->id, p->name, p->score);
    p = p->next;
  }

  return (0);
}

TOP
NEXT PAGE >>

        

  

Copyright © MESCIUS inc.