キーワード辞典
かなり乱暴な自己参照構造体

登録日 13/05/22   更新日 13/06/09


自己参照構造体

自己参照構造体は、 メンバに自分自身と同じ型の構造体へのポインタを持つ構造体のこと。

構造体に限らず、配列を利用する場合は、 あらかじめ必要な領域を充分確保しておかなければならないが、 構造体のメンバで同じ型の構造体へつながるポインタを持っておき、 必要に応じてメモリ内で必要な領域を確保、解放することで、 柔軟にデータを扱うことが出来る。 ポインタによってつながれた各々のものをノードと呼ぶ。 ポインタが次のノードへつながるものだけならば一方向のリスト、 次のノードと手前のノードの2つを持つならば双方向のリストになる。 リストがJRの山手線の様に環状につながる場合もある。 rootとなるノードを頂点に、 右へと左への2つ(或いは右へ、左へ、親への3つ)のポインタを持つノードがつながるならば、 二分木構造になる。 長くなるので此処では今は詳しく書かないが、興味のある方は、調べるべし。

C言語って、「こういう書き方も出来る」とか「こういう考え方もある」とか、いっぱい有るので、 とりあえず、ざっくりと。


恐ろしく手抜きな一方向リストによる伝言板の例。
伝言の追加と表示をするだけ。 あくまでもサンプル例であり、あまりエラー処理をしていないので要注意。
右図は概念図。 黒い矢印はノードの追加処理の流れ、赤い矢印はノードの参照の流れを表している。 また、2つのX番地は、同じ番地であることを表す。

ノードを追加する際は、malloc で Dengonban のサイズのメモリをガバッと確保し、 各メンバのサイズで区切られた領域に、該当するデータを入れていく。

/* RynStructList2.c		2013.6.9 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NMOJISU 10				/* 名前の文字数 */
#define MMOJISU 80				/* 投稿の文字数 */

struct Dengonban{				/* 構造体 Dengonban の定義(仕様) */
	int    number;
	char   name[NMOJISU];
	char   dengon[MMOJISU];
	struct Dengonban *next;
};

/* いちいち struct Dengonban と書くのは面倒なので、*/
/* typedef で *DengonList というデータ型にする     */
typedef struct Dengonban *DengonList;

DengonList add_node(DengonList node);

void show_node(DengonList node);
void search_node(DengonList node);

int main()
{
	char cmd[10];
	DengonList node = NULL;			/* DengonList型のポインタ変数 node */

	while(1){
		printf("¥n");
		printf("add / show / search / exit  ? = ");
		fflush(stdin);
		fgets(cmd, sizeof(cmd), stdin);			/* コマンド入力           */
		if( strcmp(cmd,"add¥n")==0)				/* 改行も含めて判断 (^_^; */
			node = add_node(node);
		else if( strcmp(cmd,"show¥n")==0)
			show_node(node);
		else if( strcmp(cmd,"search¥n")==0)
			search_node(node);
		else if( strcmp(cmd,"exit¥n")==0)
			return;
		else
			printf("???¥n");
	}
}

DengonList add_node(DengonList node)
{
	int  number;
	char name[NMOJISU];
	char dengon[MMOJISU];
	DengonList newnode;			/* DengonList型のポインタ変数 newnode */

	printf("name ? = ");
	fflush(stdin);
	fgets(name, sizeof(name), stdin);		/* 名前を入力 */
	name[strlen(name) - 1] = '¥0';			/* 改行を消す */
	printf("dengon ? = ");
	fflush(stdin);
	fgets(dengon, sizeof(dengon), stdin);		/* 本文を入力 */
	dengon[strlen(dengon) - 1] = '¥0';
	newnode = malloc(sizeof *newnode);			/* ここで1件分のサイズを実際に確保 */
												/* その先頭アドレスが newnode       */
	if ( newnode == NULL ) return NULL;			/* 確保出来なかったら強制的に戻る   */
		if(node == NULL)						/* 1件目だったら         */
			newnode->number = 1;
		else									/* 2件目以降だったら     */
			newnode->number = node->number + 1;
		strcpy(newnode->name, name);				/* 名前と本文をリストへ       */
		strcpy(newnode->dengon, dengon);
		newnode->next = node;					/* つなげる */

		return newnode;							/* 新ノードのアドレスを返す */
}

void show_node(DengonList node)
{
	printf("---show start---¥n");
	while( node != NULL ){
		printf("[%d] %s:",node->number, node->name);
		printf(" %s¥n",node->dengon);
		node = node->next;
	}
	printf("----show end----¥n");
}

void search_node(DengonList node)
{
	char search_name[NMOJISU];

	printf("search name ? = ");
	fflush(stdin);
	fgets(search_name, sizeof(search_name), stdin);
	search_name[strlen(search_name) - 1] = '¥0';
	printf("---search start---¥n");
	while( node != NULL ){
		if( strcmp(search_name, node->name)==0){
			printf("[%d] %s:",node->number, node->name);
			printf(" %s¥n",node->dengon);
		}
		node = node->next;
	}
	printf("----search end----¥n");
}






[ 赤い玉の画像 ] 「キーワード辞典」の目次へ

[ 黒板消しとチョーク受けの画像 ]