C言語において自己参照構造体とは、メンバに自分自身と同じ型の構造体へのポインタを持つ構造体のことです。メンバに持つのは構造体ではなく、構造体へのポインタであることに注意してください。
自己参照構造体の特長は、ポインタを介して同じ型の別の構造体へ次々にデータを繋いでいくデータチェーンを持つことができるということです。そのためリスト処理においてよく使用されます。
自己参照構造体とはメンバに自分自身と同じ型の構造体へのポインタを持つ構造体のことです。C言語での自己参照構造体について説明します。
C言語において自己参照構造体とは、メンバに自分自身と同じ型の構造体へのポインタを持つ構造体のことです。メンバに持つのは構造体ではなく、構造体へのポインタであることに注意してください。
自己参照構造体の特長は、ポインタを介して同じ型の別の構造体へ次々にデータを繋いでいくデータチェーンを持つことができるということです。そのためリスト処理においてよく使用されます。
例を見てみましょう。次のプログラムは、コマンドラインから引数としていくつかの数を受け取り昇順にソートして表示します。
#include <stdio.h>
#include <stdlib.h>
/* 入力データ用構造体 */
struct InputData
{
int value; /* 入力値 */
struct InputData *next; /* 次の入力データへのポインタ */
};
int main(int argc, char *argv[])
{
int i; /* カウンタ */
int n; /* 入力値 */
struct InputData *head = NULL; /* 先頭データへのポインタ */
struct InputData *tmp[2] = {NULL, NULL}; /* データをたどる時に使う */
struct InputData *p = NULL; /* メモリ確保の際に使うポインタ */
/* プログラムに渡された引数分ループする */
for (i=0;i<argc-1;i++) {
/* 引数を取得しintに変換 */
n = atoi(argv[i+1]);
/* メモリを取得 */
p = (struct InputData *)malloc(sizeof(struct InputData));
if (p == NULL) {
printf("error¥n");
exit(1);
}
p->value = n; /* 取得した値をセット */
/* 最初の引数の処理ならば */
if (i == 0) {
/* データチェインの先頭に設定する */
head = p;
head->next = NULL; /* 次のデータはなし */
continue; /* 次の引数の処理へ */
}
/* 最初の引数でなければ */
/* データチェインをたどり適切な位置に挿入する */
tmp[0] = NULL; /* 1つ前のデータ記憶用 */
tmp[1] = head; /* 比較対象のデータ用 */
while(1) {
/* 挿入したいデータの値がデータチェイン上の値以下なら */
if (n <= tmp[1]->value) {
/* 比較対象のデータの1つ前の位置に挿入 */
/* 1つ前がNULL,つまり先頭なら */
if (tmp[0] == NULL) {
/* 挿入データの次のデータは現在の先頭 */
p->next = head;
/* 先頭にデータを挿入 */
head = p;
} else {
/* 先頭でなければ */
/* 挿入データの次のデータは比較対象データ */
p->next = tmp[1];
/* 1つ前の位置にデータを挿入 */
tmp[0]->next = p;
}
break; /* 挿入処理終了,次の引数の処理へ */
}
/* 挿入したいデータの値がデータチェイン上の値未満なら */
/* 比較対象のデータを次のデータに更新 */
tmp[0] = tmp[1];
/* もし次のデータがないなら */
if (tmp[0]->next == NULL) {
/* 最後に挿入して */
p->next = NULL;
tmp[0]->next = p;
break; /* 挿入処理終了,次の引数の処理へ */
} else {
tmp[1] = tmp[0]->next;
}
}
}
/* データ表示処理 */
tmp[1] = head; /* 先頭データをセット */
/* データチェインの最後まで繰り返す */
while (tmp[1] != NULL) {
/* データを表示 */
printf("%d ", tmp[1]->value);
tmp[0] = tmp[1]; /* メモリ解放用にポインタを退避 */
tmp[1] = tmp[0]->next; /* 次のデータをセット */
free(tmp[0]); /* 表示し終わったデータのメモリを解放 */
}
printf("¥n");
return 0;
}
プログラムを順に説明します。
#include <stdio.h>
#include <stdlib.h>
標準ライブラリ用にヘッダをインクルードします。メモリを確保する関数malloc()を使用するのでstdlib.hが必要です。
/* 入力データ用構造体 */
struct InputData
{
int value; /* 入力値 */
struct InputData *next; /* 次の入力データへのポインタ */
};
これがコマンドラインよりプログラムの引数として入力されるデータを格納するための構造体の型です。valueに値が入り、nextには次のデータへのポインタが格納されます。nextは自分自身と同じ型の構造体へのポインタですので、この構造体は自己参照構造体ということになります。
int main(int argc, char *argv[])
{
int i; /* カウンタ */
int n; /* 入力値 */
struct InputData *head = NULL; /* 先頭データへのポインタ */
struct InputData *tmp[2] = {NULL, NULL}; /* データをたどる時に使う */
struct InputData *p = NULL; /* メモリ確保の際に使うポインタ */
main関数の先頭で各変数を宣言します。headがデータチェインの先頭データへのポインタです。tmp[]はデータチェインをたどる時に使用します。配列になっているのは1つ前のデータを保持しておく必要があるからです。pはmalloc関数でメモリを確保する時に一時的に使用するポインタです。
/* プログラムに渡された引数分ループする */
for (i=0;i<argc-1;i++) {
/* 引数を取得しintに変換 */
n = atoi(argv[i+1]);
/* メモリを取得 */
p = (struct InputData *)malloc(sizeof(struct InputData));
if (p == NULL) {
printf("error¥n");
exit(1);
}
p->value = n; /* 取得した値をセット */
/* 最初の引数の処理ならば */
if (i == 0) {
/* データチェインの先頭に設定する */
head = p;
head->next = NULL; /* 次のデータはなし */
continue; /* 次の引数の処理へ */
}
forループを使用して引数の個数分ループ処理を行います。まず、引数をint型に変換して取得します。その次にデータを格納するためのメモリを動的に取得します。そしてその中に取得した値をセットします。
最初の引数の場合はデータが1つしかないということですから、無条件にデータの先頭のポインタであるheadに先ほど取得したデータを指しているポインタpをセットします。また、次のデータはありませんから、nextにはNULLをセットします。そして、次の引数の処理へ進むためにcontinueします。
/* 最初の引数でなければ */
/* データチェインをたどり適切な位置に挿入する */
tmp[0] = NULL; /* 1つ前のデータ記憶用 */
tmp[1] = head; /* 比較対象のデータ用 */
while(1) {
/* 挿入したいデータの値がデータチェイン上の値以下なら */
if (n <= tmp[1]->value) {
/* 比較対象のデータの1つ前の位置に挿入 */
/* 1つ前がNULL,つまり先頭なら */
if (tmp[0] == NULL) {
/* 挿入データの次のデータは現在の先頭 */
p->next = head;
/* 先頭にデータを挿入 */
head = p;
} else {
/* 先頭でなければ */
/* 挿入データの次のデータは比較対象データ */
p->next = tmp[1];
/* 1つ前の位置にデータを挿入 */
tmp[0]->next = p;
}
break; /* 挿入処理終了,次の引数の処理へ */
}
ループ処理に入ります。データの並びは昇順ですので、比較対象の値と引数から取得した値を比較して、取得値が比較対象の値以下なら、比較対象のデータの1つ前に取得値のデータを挿入することになります。
挿入する場合、次の処理が2つに分かれます。1つはtmp[0]がNULL、すなわち挿入位置が先頭であった場合で、もう1つはそれ以外の場合です。挿入位置が先頭の場合はheadに挿入データのポインタをセットし、次のデータを指すnextには直前までheadに入っていたポインタをセットします。これで先頭位置にデータを挿入したことになります。
挿入する位置が先頭以外の場合、tmp[0]の次が挿入位置で、挿入データに続くデータは比較対象であったtmp[1]ですから、挿入データのnextにtmp[1]を格納し、tmp[0]のnextに挿入データを指すpを格納します。
挿入が終わったならば、次の引数の処理を行うためbreakし、whileループを抜けます。
/* 挿入したいデータの値がデータチェイン上の値未満なら */
/* 比較対象のデータを次のデータに更新 */
tmp[0] = tmp[1];
/* もし次のデータがないなら */
if (tmp[0]->next == NULL) {
/* 最後に挿入して */
p->next = NULL;
tmp[0]->next = p;
break; /* 挿入処理終了,次の引数の処理へ */
} else {
tmp[1] = tmp[0]->next;
}
}
}
取得値が比較対象の値を超えていた場合は、比較対象のデータをデータチェイン上の次のデータに更新します。次のデータはnextの中にポインタが格納されているのでそれを使用します。また、tmp[0]も更新しておきます。
もし、次のデータがNULLならば、データチェインの最後ということなので、NULLの代わりに取得データを指すpをセットしてbreakします。
/* データ表示処理 */
tmp[1] = head; /* 先頭データをセット */
/* データチェインの最後まで繰り返す */
while (tmp[1] != NULL) {
/* データを表示 */
printf("%d ", tmp[1]->value);
tmp[0] = tmp[1]; /* メモリ解放用にポインタを退避 */
tmp[1] = tmp[0]->next; /* 次のデータをセット */
free(tmp[0]); /* 表示し終わったデータのメモリを解放 */
}
printf("¥n");
return 0;
}
全ての引数分セットし終わったならば表示処理を行います。先頭データを指すheadをtmp[1]にセットしておいてループします。データ表示したらnextをたどって次のデータを取得します。表示し終わったデータはもう必要ないのでfree()を使用してメモリを解放します。malloc()で取得したメモリはfree()で解放する必要があります。