C言語教室第19回 - 単方向リスト（回答提出）

2023年4月8日 09:12

こちらの記事の課題と演習の回答です。

課題
・リストの要素の数を返す関数を書きなさい。
・リストの最後に要素を追加する関数を書きなさい。
・リストの先頭の要素を削除する関数を書きなさい。
・n番目の要素を返す関数を書きなさい。

演習
・リストを配列にコピーする関数を書きなさい。
・配列からリストを作る関数を書きなさい。

プログラムには基本的なデータ構造がいくつかあります。スタックやキューなどが有名ですが、リスト構造もその一つです。今回はこの「リスト構造」に関する課題演習です。

「基本的なデータ構造」というのは、「汎用的なプログラムにできる」ということを意味します。この「汎用的」というのはプログラムにとっては永遠の課題のようなもので、「これでもか！」というくらい汎用的に作ったと思ってもなお、そこに収まりきらないケースにぶつかります。「より汎用的なプログラムがある」とすれば、それは間違いなく優れたプログラムと言える。

要するに・・・リストのプログラミングには腕がなるわけです(笑)。

特にこの「リスト構造」というのは、ポインタを使うといよいよ興味深いコードになります。今回は単方向のリストですが、双方向となるともっともっと面白い。経験を積んだプログラマーなら一度は書いたことがあるかもしれません。私も書いたことがあります。人が書いたリストプログラムのバグを改修したことも2度あります。そう。バグりやすい(笑)。

以下にコードを示しますが、このコードには改良の余地はまだまだあります。1回ポッキリの書き捨てではなくて改良に改良を重ねることで学ぶことも多い。職業プログラマーというのは、実は似たようなコードを何度も書いている。それで勉強することはたくさんある。「これじゃあ、改修しにくい」「ああ、こうしておけばよかった」と思うようなことが多々あります。そしてそれを次につなげる（と言いつつ忘れてしまうことも多いが）。

リスト構造というのはそういう諸々のことにうってつけの題材なわけです。

思わず熱くなりました。

では。
課題回答に進みましょう。

今回はリンク先記事のコードを一部流用させていただきました。

ただ、少し手を加えています。

Node*を戻り値にした
引数の「Node*」は変更しない。
戻り値を「Node*」にしてみました。

ですが・・・。
この『引数の「Node*」を変更しない』というのは是か非かが微妙で、関数を実装する上では悪くないんだけど、使う側からすると使いにくい。戻り値を取るのをよく忘れるんです。
関数を使用するユーザにとっては甚だ冷たい関数になってしまったかもしれません。

関数「print_list」　while を for に
関数「print_list」のループを「while」から「for」に変えてみました。
これは、単に好みの問題かもしれない。
どちらがいいのかを明確にするだけの理由は見いだせずにいます。

課題の回答ですが、個別に1つ1つコードを掲載しようと思ったんだけど、面倒くさいのでやめました(笑)。コードは全コードとテストコードをまとめて掲載します。それでもって全体がそれなりに長いので、ダウンロードファイルも付けました。

まずは個別に感想コメントなどを。

リストの要素の数を返す関数を書きなさい。

リストを作れば、当然のことながら、リストにいくつ要素が登録されているのか知りたくなるケースは多いですよね。ただ、リスト構造においてこれがなかなかやっかい。もう、数えるしかありません。

「追加する度にカウントしておけばいいんじゃね？」と思うかもしれませんが、ではそのカウンタをどこに置くかとなると困る。

全部のNodeにカウンタを持たせる
すると、追加する都度全部のNodeを更新しなければならない。全部のNode！　ちょっとどころか、あまりにも冗長にすぎる。

どこかにテーブルを一つ用意してカウントする
すると、全てのNodeがそのテーブルと結びつく。これが何を意味するのか。今の状態でNodeは極めて独立性が高い。リストAのヘッド、リストBのヘッド、・・・などと、幾種類ものリストを個別に作成することができます。でもカウンタを一つ用意してどのNodeもそのカウンタをカウントするとしたら・・・。そう。リストAの個数とリストBの個数の合計がカウントされてしまうのです。これにより、いともあっさりとNodeの独立性は失われます。個別のリストをじゃんじゃん作るということができなくなる。代償が大きすぎます。

結局のところ、数を知りたければ数えるしかありません。数えるためのコードはとても簡単なのだけど、1万も2万も、いや1億も2億もあるとすると・・・。地味に数えるのか・・・。と思うと、少々げんなりする。どれだけ時間がかかるんだろう・・・。

とにかく、数えました。

リストの最後に要素を追加する関数を書きなさい。

単方向リストの場合、リストの先頭はわかっても末尾がわかりません。リストを一つずつたどって、べったこを探すしかないんです。

なので探しました。

リストの先頭の要素を削除する関数を書きなさい。

リストの先頭！
これは、もう簡単！
先頭の人を取っ払って、２番目の人を覚えておけばよろしい。

n番目の要素を返す関数を書きなさい。

n番目！
べったこが誰かもわからないんですもん。
n番目なんか知りませんわよ。
数えます。

そして演習です。

リストを配列にコピーする関数を書きなさい。

1個ずつペタペタコピー。

配列からリストを作る関数を書きなさい。

1個ずつペタペタつなげる。

ではコードです！

#include <stdlib.h>

typedef struct node {
	int data;
	struct node* next;
} Node;

Node* prepend(Node* head, int data);
Node* append(Node* head, int data);
Node* free_head(Node* head);
Node* free_list(Node *head);
int get_count(const Node* head);
const Node* get_node(const Node* head, int index);
Node* get_tail_node(Node* head);
void print_array(const int a[], int count);
void print_list(const Node* head);
int to_array(const Node* head, int array[], int max_count);
Node* from_array(const int array[], const int count);

void test_append();
void test_free_head();
void test_get_count();
void test_get_node();
void test_get_tail_node();
void test_to_array();
void test_from_array();

//#####################################
Node* prepend(Node* head, int data) {
	Node* new_node = (Node*)malloc(sizeof(Node));
	new_node->data = data;
	new_node->next = head;
	return new_node;
}

//#####################################
// (2)リストの最後に要素を追加する関数を書きなさい。
Node* append(Node* head, int data) {
	if (head == NULL) {
		return prepend(head, data);
	}

	Node* new_node = (Node*)malloc(sizeof(Node));
	Node* tail_node = get_tail_node(head);
	new_node->data = data;
	new_node->next = tail_node->next;
	tail_node->next = new_node;
	return head;
}

//#####################################
// (3)リストの先頭の要素を削除する関数を書きなさい。
Node* free_head(Node* head) {
	if (head == NULL) {
		return head;
	}

	Node* new_head = head->next;
	free(head);
	return new_head;
}

//#####################################
Node* free_list(Node *head) {
	Node *current = head;
	while (current != NULL) {
		Node *next = current->next;
		free(current);
		current = next;
	}
	return NULL;
}

//#####################################
// (1)リストの要素の数を返す関数を書きなさい。
int get_count(const Node* head) {
	int count = 0;
	const Node* p;
	for (p = head; p != NULL; p = p->next) {
		count++;
	}
	return count;
}

//#####################################
// (4)n番目の要素を返す関数を書きなさい。
const Node* get_node(const Node* head, int index) {
	int count = 0;
	const Node* node = NULL;
	const Node* p;
	for (p = head; p != NULL; p = p->next) {
		count++;
		if (count == index) {
			node = p;
			break;
		}
	}
	return node;
}

//#####################################
Node* get_tail_node(Node* head) {
	Node* tail = head;
	Node* p;
	for (p = head; p != NULL; p = p->next) {
		tail = p;
	}
	return tail;
}

//#####################################
void print_array(const int a[], int count) {
	int i = 0;
	for (i = 0; i < count; ++i) {
		printf("%d ", a[i]);
	}
}

//#####################################
void print_list(const Node* head) {
	const Node* p;
	for (p = head; p != NULL; p = p->next) {
		printf("%d ", p->data);
	}
}

//#####################################
// ・リストを配列にコピーする関数を書きなさい。
int to_array(const Node* head, int array[], int max_count) {
	int i = 0;
	int count = 0;
	const Node* p = head;
	for (i = 0; i < max_count; ++i) {
		if (p == NULL)
		{
			break;
		}
		array[count] = p->data;
		count++;
		p = p->next;
	}
	return count;
}

//#####################################
// ・配列からリストを作る関数を書きなさい。
Node* from_array(const int array[], const int count) {
	Node* head = NULL;
	int i = 0;

	if(array == NULL) {
		return head;
	}

	for (i = 0; i < count; ++i) {
		head = append(head, array[i]);
	}
	return head;
}

//#####################################
void test_append() {
	Node* head = NULL;
	printf("head = NULL\n");
	printf("print_list (head) = ");
	print_list(head);
	printf("\n");
	printf("\n");

	printf("head = append(head, 1)\n");
	head = append(head, 1);
	printf("print_list (head) = ");
	print_list(head);
	printf("\n");
	printf("\n");

	printf("head = append(head, 2)\n");
	head = append(head, 2);
	printf("print_list (head) = ");
	print_list(head);
	printf("\n");
	printf("\n");

	printf("head = append(head, 3)\n");
	head = append(head, 3);
	printf("print_list (head) = ");
	print_list(head);
	printf("\n");
	printf("\n");

	printf("head = append(head, 4)\n");
	head = append(head, 4);
	printf("print_list (head) = ");
	print_list(head);
	printf("\n");
	printf("\n");
}

//#####################################
void test_free_head() {
	Node* head = NULL;
	head = append(head, 1);
	head = append(head, 2);
	head = append(head, 3);
	head = append(head, 4);
	printf("print_list = (head) ");
	print_list(head);
	printf("\n");
	printf("\n");

	printf("head = free_head(head)\n");
	head = free_head(head);
	printf("print_list = (head) ");
	print_list(head);
	printf("\n");
	printf("\n");

	printf("head = free_head(head)\n");
	head = free_head(head);
	printf("print_list = (head) ");
	print_list(head);
	printf("\n");
	printf("\n");

	printf("head = free_head(head)\n");
	head = free_head(head);
	printf("print_list = (head) ");
	print_list(head);
	printf("\n");
	printf("\n");

	printf("head = free_head(head)\n");
	head = free_head(head);
	printf("print_list = (head) ");
	print_list(head);
	printf("\n");
	printf("\n");

	printf("head = free_head(head)\n");
	head = free_head(head);
	printf("print_list = (head) ");
	print_list(head);
	printf("\n");
	printf("\n");
}

//#####################################
void test_from_array() {
	Node* head = NULL;
	int data[8] = {0, 1, 2, 3, 4, 5, 6, 7};
	printf("head = NULL\n");
	head = from_array(NULL, 8);
	printf("head = from_array(NULL, 8) = %p\n", head);
	printf("\n");
	printf("\n");

	printf("print_array (data) = ");
	print_array(data, 8);
	printf("\n");
	head = from_array(data, 8);
	printf("head = from_array(data, 8) = %p\n", head);
	printf("print_list (head) = ");
	print_list(head);
	printf("\n");
	printf("\n");
}

//#####################################
void test_get_count() {
	Node* head = NULL;
	int count;
	printf("head = NULL\n");
	count = get_count(head);
	printf("get_count(head) = %d\n", count);
	printf("\n");

	printf("append(head, 1)\n");
	head = append(head, 1);
	count = get_count(head);
	printf("get_count(head) = %d\n", count);
	printf("\n");

	printf("append(head, 2)\n");
	head = append(head, 2);
	count = get_count(head);
	printf("get_count(head) = %d\n", count);
	printf("\n");

	printf("append(head, 3)\n");
	head = append(head, 3);
	count = get_count(head);
	printf("get_count(head) = %d\n", count);
	printf("\n");

	printf("append(head, 4)\n");
	head = append(head, 4);
	count = get_count(head);
	printf("get_count(head) = %d\n", count);
	printf("\n");
}

//#####################################
void test_get_node() {
	Node* head = NULL;
	Node* node = NULL;
	const Node* const_node = NULL;

	printf("head = NULL\n");
	const_node = get_node(head, 2);
	printf("get_node(head, 2) = %p ", const_node);
	if (const_node != NULL) {
		printf("(%d)", const_node->data);
	}
	printf("\n");
	printf("\n");


	head = append(head, 1);
	printf("append(head, 1)\n");
		
	const_node = get_node(head, 2);
	printf("get_node(head, 2) = %p ", const_node);
	if (const_node != NULL) {
		printf("(%d)", const_node->data);
	}
	printf("\n");
	printf("\n");


	head = append(head, 2);
	printf("append(head, 2)\n");

	const_node = get_node(head, 2);
	printf("get_node(head, 2) = %p ", const_node);
	if (const_node != NULL) {
		printf("(%d)", const_node->data);
	}
	printf("\n");
	printf("\n");


	head = append(head, 3);
	printf("append(head, 3)\n");

	const_node = get_node(head, 2);
	printf("get_node(head, 2) = %p ", const_node);
	if (const_node != NULL) {
		printf("(%d)", const_node->data);
	}
	printf("\n");
	printf("\n");


	head = free_list(head);
}

//#####################################
void test_get_tail_node() {
	Node* head = NULL;
	Node* node = NULL;
	const Node* const_node = NULL;
	printf("head = NULL\n");

	node = get_tail_node(head);
	printf("get_tail_node(head) = %p ", node);
	if (node != NULL) {
		printf("(%d)", node->data);
	}
	printf("\n");
	printf("\n");

	head = append(head, 1);
	printf("append(head, 1)\n");

	node = get_tail_node(head);
	printf("get_tail_node(head) = %p ", node);
	if (node != NULL) {
		printf("(%d)", node->data);
	}
	printf("\n");
	printf("\n");


	head = append(head, 2);
	printf("append(head, 2)\n");

	node = get_tail_node(head);
	printf("get_tail_node(head) = %p ", node);
	if (node != NULL) {
		printf("(%d)", node->data);
	}
	printf("\n");
	printf("\n");
		

	head = free_list(head);
}

//#####################################
void test_to_array() {
	Node* head = NULL;
	int count;
	int data[8] = {0};
	printf("head = NULL\n");
	count = to_array(head, data, 8);
	printf("to_array(head, data, 8) = %d\n", count);
	printf("print_array (data) = ");
	print_array(data, 8);
	printf("\n");
	printf("\n");

	printf("append(head, 1)\n");
	head = append(head, 1);
	count = to_array(head, data, 8);
	printf("to_array(head, data, 8) = %d\n", count);
	printf("print_array (data) = ");
	print_array(data, 8);
	printf("\n");
	printf("\n");

	printf("append(head, 2)\n");
	head = append(head, 2);
	count = to_array(head, data, 8);
	printf("to_array(head, data, 8) = %d\n", count);
	printf("print_array (data) = ");
	print_array(data, 8);
	printf("\n");
	printf("\n");

	printf("append(head, 3)\n");
	head = append(head, 3);
	count = to_array(head, data, 8);
	printf("to_array(head, data, 8) = %d\n", count);
	printf("print_array (data) = ");
	print_array(data, 8);
	printf("\n");
	printf("\n");

	printf("append(head, 4)\n");
	printf("append(head, 5)\n");
	printf("append(head, 6)\n");
	printf("append(head, 7)\n");
	printf("append(head, 8)\n");
	printf("append(head, 9)\n");
	head = append(head, 4);
	head = append(head, 5);
	head = append(head, 6);
	head = append(head, 7);
	head = append(head, 8);
	head = append(head, 9);
	count = to_array(head, data, 8);
	printf("to_array(head, data, 8) = %d\n", count);
	printf("print_array (data) = ");
	print_array(data, 8);
	printf("\n");
	printf("\n");
}

int main() {
	printf("#####################################\n");
	test_append();

	printf("#####################################\n");
	test_free_head();

	printf("#####################################\n");
	test_get_count();

	printf("#####################################\n");
	test_get_node();

	printf("#####################################\n");
	test_get_tail_node();

	printf("#####################################\n");
	test_to_array();

	printf("#####################################\n");
	test_from_array();

	return 0;
}

そんでもって実行結果。

#####################################
head = NULL
print_list (head) =

head = append(head, 1)
print_list (head) = 1

head = append(head, 2)
print_list (head) = 1 2

head = append(head, 3)
print_list (head) = 1 2 3

head = append(head, 4)
print_list (head) = 1 2 3 4

#####################################
print_list = (head) 1 2 3 4

head = free_head(head)
print_list = (head) 2 3 4

head = free_head(head)
print_list = (head) 3 4

head = free_head(head)
print_list = (head) 4

head = free_head(head)
print_list = (head)

head = free_head(head)
print_list = (head)

#####################################
head = NULL
get_count(head) = 0

append(head, 1)
get_count(head) = 1

append(head, 2)
get_count(head) = 2

append(head, 3)
get_count(head) = 3

append(head, 4)
get_count(head) = 4

#####################################
head = NULL
get_node(head, 2) = 0x0

append(head, 1)
get_node(head, 2) = 0x0

append(head, 2)
get_node(head, 2) = 0xb400007a1b8d6530 (2)

append(head, 3)
get_node(head, 2) = 0xb400007a1b8d6530 (2)

#####################################
head = NULL
get_tail_node(head) = 0x0

append(head, 1)
get_tail_node(head) = 0xb400007a1b8d63f0 (1)

append(head, 2)
get_tail_node(head) = 0xb400007a1b8d6530 (2)

#####################################
head = NULL
to_array(head, data, 8) = 0
print_array (data) = 0 0 0 0 0 0 0 0

append(head, 1)
to_array(head, data, 8) = 1
print_array (data) = 1 0 0 0 0 0 0 0

append(head, 2)
to_array(head, data, 8) = 2
print_array (data) = 1 2 0 0 0 0 0 0

append(head, 3)
to_array(head, data, 8) = 3
print_array (data) = 1 2 3 0 0 0 0 0

append(head, 4)
append(head, 5)
append(head, 6)
append(head, 7)
append(head, 8)
append(head, 9)
to_array(head, data, 8) = 8
print_array (data) = 1 2 3 4 5 6 7 8

#####################################
head = NULL
head = from_array(NULL, 8) = 0x0


print_array (data) = 0 1 2 3 4 5 6 7
head = from_array(data, 8) = 0xb400007a1b8d6570
print_list (head) = 0 1 2 3 4 5 6 7

最後に！
ダウンロードファイルです。

ふぅ～。

この記事が気に入ったらサポートをしてみませんか？