Nodachisoft Nodachi Sword Icon
  
@あまじ✎ 2021年3月5日に更新

第2章47 リスト構造

イチからゲーム作りで覚えるC言語
第2章42 ポインタへのポインタ : PREV
NEXT : 第2章48 共用体(union)を使う :

概要

今まで配列を使って、大量のデータを扱ってきましたが、 配列を使う場合は、最初に決められたサイズから変更できないという欠点があります。

一度に大きく malloc 関数を使ってメモリサイズを確保したり、 realloc 関数を使ってメモリサイズを後から変更することもできますが、もっとも細かな構造体などの単位で柔軟にメモリを確保したり、開放したりする仕組みの一つに、リスト構造と呼ばれるデータが構造があります。

リスト構造といっても様々な種類のリスト構造がありますが、 今回は単方向線形リスト構造と呼ばれるリスト構造を実際に実装して動きを確認してきます。

リスト構造の要素

リスト構造は一般に、ノードと呼ばれるデータを格納する場所が、数珠繋ぎのようになって構成されます。

例えば、データA、データB、データC の3つのデータを持つリストは下のような構造となります。

リスト構造のイメージ

各ノードは、次の要素へのノードへのポインタを持っており、 ノードをたどっていくと、次の要素にたどり着くようなイメージです。

上の画像の例のように3つのデータ(ノード)をもつリストなら、ノードが3つ数珠つなぎのように繋がっており、 最後のノードは、後続のノードが存在しないため、「このノードでこのリストは終点です」ということを表すため、 次のノードへのポインタに目印として NULL を入れておきます。

もうちょっと具体的に、ゲームのキャラクタをノードとした時の構造体のイメージは 下のようになります。

 
ノード定義
// ノードの定義
struct nodeChar {
	// ノードが持つデータ
	char name[64];  // 名前
	int level;      // レベル
	int hitpoint;   // 体力

	// 次のノード
	struct nodeChar* nextNode;
};

この構造体(ノード) nodeChar は、自分自身の構造体へのポインタ(nextNode)を持っています。 このような構造体のことを「自己参照構造体」と呼びます。

今回はこの構造体をノードとして扱います。

このノードはキャラクタの名前、レベル、体力を持ちます。 そして、他にもノードが続いている場合、ノードのメンバであるポインタ変数 nextNode に 次のノードへのポインタが格納される、という仕組みです。

リストへのノードの追加、削除

リストへのノードの追加は下のようなイメージとなります。

一つのノードが存在する状態

リストにノードが一つ(追加前)

リストの最後のノードの、次のノードへのポインタに、新しく追加したいノードへのアドレスを代入します。

リストにノードを追加(追加後)

ではでは、リスト構造の実装例として、 キャラクタデータをノードのデータとしてもつリストを作り、 リストに3つのデータを追加してみます。

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

typedef struct nodeChar {
	char name[64];  // キャラクタの名前
	int level;      // レベル
	int hitpoint;   // 体力
	struct nodeChar *nextNode; // 次のノードへ
} node;

node *charactersList = NULL;    // リスト

// リスト characterList にノードを追加
void addlist(const node addnode) {
	// 追加するノードをヒープ領域にコピーして初期化
	node *copy = (node *)malloc(sizeof(node));
	memcpy(copy, &addnode, sizeof(addnode));
	copy->nextNode = NULL;	// リストの最後のノードなので次はなし(NULL)

	// ノードが 0 個の場合
	if (charactersList == NULL) {
		charactersList = copy;
		return;
	}

	// 最後のノードをリストの中から探索
	node* search = charactersList;
	while (search->nextNode != NULL) {
		search = search->nextNode;
	}

	// 最後のノードに追加
	search->nextNode = copy;
}

// リストの中身のノードを順番に表示
void printNode() {
	node *search = charactersList;
	while (search != NULL) {	// リストの最後(NULL)まで繰り返す
		printf("名前= %s , レベル=%d, 体力=%d\n"
			, search->name, search->level, search->hitpoint);
		search = search->nextNode; // 次のノードへ
	}
}

int main() {
	node firstNode = { "ぷらんく", 1, 10 };
	node secondNode = { "シャロッテ", 3, 36 };
	node thirdNode = { "ニンジン妖精", 1, 8 };
	addlist(firstNode);
	addlist(secondNode);
	addlist(thirdNode);
	printNode();
}

実行結果は下のようになります。

実行結果
名前= ぷらんく , レベル=1, 体力=10
名前= シャロッテ , レベル=3, 体力=36
名前= ニンジン妖精 , レベル=1, 体力=8

ノードをリストに追加する機能をもつ、addlist 関数について確認してみます。

 
list_add3.c
void addlist(const node addnode) {
	// 追加するノードをヒープ領域にコピーして初期化
	node *copy = (node *)malloc(sizeof(node));
	memcpy(copy, &addnode, sizeof(addnode));
	copy->nextNode = NULL;	// リストの最後のノードなので次はなし(NULL)

addlist は引数でリストに追加したいノードのデータを受け取ります。 ここで要注意ですが、受け取ったノードのデータ(変数addnode)をそのまま リストに追加すると思うように動作しません。

変数 addnode はメモリ上、スタック領域に確保されているため、 この addlist 関数が終了して return で呼び出し元に返った時点で、 この関数内で利用していた addnode のメモリはプログラム上、不要となったものとみなされるからです。

リストに追加するデータが残り続けるために、ヒープ領域に手動でメモリを確保し、 確保したメモリにaddnode のデータの中身をコピーしてあげる、という作業が必要になります。

17行目では、ヒープ領域に addnode の中身をコピーするためのメモリ領域を確保しています。 今回は node 一つ分を確保するため、 sizeof(node) としています。

18行目では、新しい関数 memcpy が登場しています。

この memcpy は指定したメモリアドレスから、指定したサイズ分を指定したメモリアドレスにコピーする機能をもちます

使い方は以下の通りです。

memcpy( コピー先のポインタ, コピー元のアドレス, コピーするサイズ )

これで、addnode をヒープ領域の copy というポインタ変数のアドレス先にコピーできました。

19行目では copy->nextNode に NULL を指定しています。 新しく追加するノードは、リストの末尾のノードなので、明示的に「次のノードはもうないです!最後のノードです!」という事がわかるように NULL を代入しています。

最後のノードの探索

リストの中の最後のノードを探す方法ですが、 リストの最初のノードが分かっている場合、 ノードの中の次のノード「nextNode」を確認していきます。

数珠繋ぎに、次のノードの次のノードの・・・という形で、 最後のノードにたどり着くまで繰り返します。

今回のコードでは下の部分です。

 
list_add3.c
	// 最後のノードをリストの中から探索
	node* search = charactersList;
	while (search->nextNode != NULL) {
		search = search->nextNode;
	}

28 行目で、目的のノード(今回はリストの最後のノード)を探すための 一時的なノード search を用意します。 このノードの探索はリストの先頭である charactersList からスタートします。

29~31行目で、今確認しているノードに含まれる nextNode が NULL(NULL ならリストの最後のノード) でない間、数珠繋ぎに次のノード(nextNode)への確認対象を移していく、という仕組みです。

リストの中身を表示

今回、このプログラムが正常に動作しているかを確認するため、 リストに含まれるノードの情報をすべて表示するための関数 printNode を用意しました。

 
list_add3.c
// リストの中身のノードを順番に表示
void printNode() {
	node *search = charactersList;
	while (search != NULL) {	// リストの最後(NULL)まで繰り返す
		printf("名前= %s , レベル=%d, 体力=%d\n"
			, search->name, search->level, search->hitpoint);
		search = search->nextNode; // 次のノードへ
	}
}

リストの先頭から順番に、繋がっているノードの中身を表示しています。 自分自身が NULL なら、リストのノードはおしまいですので、 while 文で search != NULL という条件でノードを探索しています。

リストのノードを削除

リストのノードを削除する場合、ヒープ領域に確保されたメモリを解放しなければなりませんので、 忘れずに free 関数を使って解放処理を行ってあげます。

例として、今回のプログラムでリストのノードをすべて解放する関数を下に載せておきます。

 
list_add3.c(追記)
// リストの全てのノードを削除しメモリを解放します
void clearList() {
	node* search = charactersList;
	node* clearNode;
    charactersList = NULL;
	while (search != NULL) {
		clearNode = search;
		search = search->nextNode;
		printf("名前「%s」のノードのメモリを開放します\n", clearNode->name );
		free(clearNode);
	}
}

リストの使用が終わったら、この関数を呼び出せば、 すべてのヒープ領域に確保されたノードのメモリが解放され削除されます。

リストによくある機能

リスト構造を扱う上でよくある機能として、下のような物があります。 今回は基本的なリスト構造の仕組みのみとして、下の各機能の実装については割愛いたします。

  • 先頭から n 番目の要素(ノード)のデータを取り出す
  • 条件に合致するノードの検索
  • リストの n 番目にノードを差し込み
  • リストの n 番目のノードを削除して詰める

単方向線形リストとその他のリスト構造

今回は「単方向線形リスト」構造というものについて確認しました。

名前に「単方向」とか、「線形」とか入っていますが、この意味について簡単に確認しておきます。

今回実装したリストで、ノードを探すときは、 先頭から数珠つなぎに、次のノード、またその次のノード・・・という風に一つ一つのノードを確認する方法でした。

このように、リストの先頭のノードから最後のノードの方へ、順番に確認していく一方通行の確認のみ可能ですので、「単方向」とか「片方向」のリストと呼ばれています。

また、「線形」という単語ですが、1本の鎖、一本の線のようにデータが連なっているので、線形と呼ばれます。

単方向線形リストでは、次のノードは分かりますが、前のノードへのポインタがないため、一つ前のノードを見ることが出来ませんでした。

例えば、ちょっと今回のノードの構造体を追加して、前のノードへのポインタも付ければ、「単方向線形リスト」ではなく、一つ前のノードを探索できる、「双方向線形リスト」が実現できます。

双方向リストの構造

双方向リストのノードのイメージを構造対に追加してみます。

 
双方向線形リストのノード定義
// ノードの定義
struct nodeChar {
	// ノードが持つデータ
	char name[64];  // 名前
	int level;      // レベル
	int hitpoint;   // 体力

	struct nodeChar* nextNode;	// 次のノード
    struct nodeChar* prevNode;  // 前のノード
};

双方向リストでキャラクタデータなどを管理したとき、 例えば、「対象のキャラクタの前後に追加されたキャラクタを確認する」等の処理が簡単にできて便利です。

他のプログラミオング言語(参考)

C言語以降のプログラミング言語では、 リスト構造のように頻繁に利用するデータ構造は 自分自身で実装せずとも、標準的な機能として使えるように最初から用意されていることが多いです。

ただし、ちょっと変わったデータ構造を扱う必要があるときなど、 基本的な動作の仕組みを把握していると、ぐっと設計や実装がしやすくなるので、 C言語で自分自身で実装してみるというのは、他の言語でプログラミングする際にも 知識として無駄にならないかと思います。

参考

イチからゲーム作りで覚えるC言語
第2章42 ポインタへのポインタ : PREV
NEXT : 第2章48 共用体(union)を使う :
 
 
送信しました!

コメント、ありがとうございます。

なんかエラーでした

ごめんなさい。エラーでうまく送信できませんでした。ご迷惑をおかけします。しばらくおいてから再度送信を試していただくか、以下から DM などでご連絡頂ければと思います。

Twitter:@NodachiSoft_jp
お名前:
 
連絡先:
 
メッセージ:
 
戻る
内容の確認!

以下の内容でコメントを送信します。よろしければ、「送信」を押してください。修正する場合は「戻る」を押してください

お名前:
 
連絡先:
 
メッセージ:
 
Roboto からの操作ではないという確認のため確認キーを入れてください。
確認キー=95
戻る
 / 
送信確認へ
コメント欄
コメント送信確認へ

関連ありそうな記事(5件)です!

第1章01 Visual Studio Community 2019 のインストール手順

#C11仕様#C言語#ゲームプログラミング✎ 2021-08-08
C言語でプログラミングをするために、無料で使える Visual Studio Community を使った開発環境を揃えていく手順や注意点をお話しています。
目次
第2章47 リスト構造
第2章47 リスト構造
概要
概要
リスト構造の要素
リスト構造の要素
リストへのノードの追加、削除
リストへのノードの追加、削除
最後のノードの探索
最後のノードの探索
リストの中身を表示
リストの中身を表示
リストのノードを削除
リストのノードを削除
リストによくある機能
リストによくある機能
単方向線形リストとその他のリスト構造
単方向線形リストとその他のリスト構造
他のプログラミオング言語(参考)
他のプログラミオング言語(参考)
参考
参考
Nodachisoft © 2021