C言語教室第21回 - 循環リスト（回答提出）

2023年4月24日 18:13

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

課題
番兵ノードを用い循環リストで実装した双方向リストを使って、以下のリスト処理を行う関数を書きなさい。
1. リストの先頭に要素を追加する。
2. リストの最後に要素を追加する。
3. リストの先頭の要素を削除する。
4. リストの最後の要素を削除する。

演習
1. リストに引き数で渡した値を持つノードのアドレスを返す関数を書きなさい。
2. リストに含まれるノードへのポインタと値を引き数とし、渡したノードの位置に渡した値のノードを挿入する関数を書きなさい。その結果、渡したノードは挿入したノードの次のノードとなります。
3. リストに含まれるノードへのポインタを渡して、そのノードをリストから削除する関数を書きなさい。なお番兵ノードを渡した場合は削除してはいけません。

今回はいよいよ、循環リストです。
先日の双方向リストにはNULL終端がありました。
循環リストにはその「終端」がありません。

「終端」というのは、プログラムのロジックにおいて、しばしば特異なものになります。結果、「if」文などの条件文が増える。コードは長くなるし不具合も出やすくなります。それに対して、その「NULL終端」を持たない循環リストは、コードを共通化しやすい。特異なコードを減らすことができます。

今回は出題でベースとなるコードが提示されておりましたので、それに肉付けするような形で回答します。

ただ、ベースコードを一部変更しました。

関数「create_node」

「next」「prev」が「NULL」で初期化されておりましたが、これを「node」で初期化するように変更しました。循環リストの場合は、「NULL」を持たない方がプログラムしやすいためです。

構造体「list」

メンバ変数を「top」から「anchor」に変更しました。番兵役の node です。
もう一つ、関数「create_node」を呼び出すことにしました。

さて、回答コードです。

が。
その前に。

循環リストの場合、nodeをつなげる、nodeを切り離すというコードは同じものになりやすい。
そのため、次のサブ関数を設けました。

// a の後ろに b をつなげる
void link_next(Node* a, Node* b);

// a の前に b をつなげる
void link_prev(Node* a, Node* b);

// a を切り離す
void unlink_node(Node* a);

関数「a を切り離す」のシンボルは「unlink」としたかったけど、C言語の標準関数とぶつかってしまった。C言語の場合はシンボルがグローバルなので、あまりシンプルなシンボルにすると標準関数や市販ライブラリなどとかぶりやすい。ですので、製品や開発元を示すような文字列をシンボルの先頭に置くことが多い。ただ、それをするとシンボルが長くなります。今回はプログラミングの演習ですのでそういうものは極力排除します。

以下、回答コードです。

例によってテストコードの方が長いのですが、面倒なのでまとめて掲載。

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

typedef struct node {
  int val;
  struct node* next;
  struct node* prev;
} Node;

typedef struct list {
  struct node* anchor;
} List;

Node* create_node(int val) {
  Node *node = (Node*)malloc(sizeof(Node));
  node->val = val;
  node->next = node;
  node->prev = node;
  return node;
}

void create_list(List* list) {
  list->anchor =  create_node(0);
}

void destroy_list(List* list) {
   Node *current = list->anchor->next;
   Node *next;
   while (current != list->anchor) {
        next = current->next;
        free(current);
        current = next;
    }
    free(list->anchor);
    list->anchor = NULL;
}

void print_list(List* list) {
  Node *current = list->anchor->next;
  while (current != list->anchor) {
    printf("%d ", current->val);
    current = current->next;
  }
  printf("\n");
}

void dump_list(List* list) {
#if _DEBUG
   	printf("list.anchor = \n%d %p %p %p\n", 
		list->anchor->val, list->anchor, 
		list->anchor->next, list->anchor->prev);
  	Node *current = list->anchor->next;
  	while (current != list->anchor) {
    	printf("%d %p %p %p\n", 
			current->val, current, 
			current->next, current->prev);
    	current = current->next;
  	}
#endif
}

//#######################################
// a の後ろに b をつなげる
void link_next(Node* a, Node* b) {
	Node* a_next = a->next;
	Node* b_tail = b->prev;
	b_tail->next = a_next;
	a_next->prev = b_tail;

	a->next = b;
	b->prev = a;
}

// a の前に b をつなげる
void link_prev(Node* a, Node* b) {
	Node* a_prev = a->prev;
	Node* b_tail = b->prev;
	a_prev->next = b;
	b->prev      = a_prev;

	b_tail->next = a;
	a->prev      = b_tail;
}

// a を切り離す
void unlink_node(Node* a) {
	Node* prev = a->prev;
	Node* next = a->next;

	prev->next = next;
	next->prev = prev;

	a->next = a;
	a->prev = a;
}

void destroy_node(Node* node) {
    free(node);
}

//#######################################
// 課題
// 1. リストの先頭に要素を追加する。
void add_top(List* list, int val) {
	Node* node = create_node(val);
	link_next(list->anchor, node);
}

// 2. リストの最後に要素を追加する。
void add_tail(List* list, int val) {
	Node* node = create_node(val);
	link_prev(list->anchor, node);
}

// 3. リストの先頭の要素を削除する。
void del_top(List* list) {
	Node* top = list->anchor->next;
	unlink_node(top);
	destroy_node(top);
}

// 4. リストの最後の要素を削除する。
void del_tail(List* list) {
	Node* tail = list->anchor->prev;
	unlink_node(tail);
	destroy_node(tail);
}


//#######################################
// 演習
// 1. リストに引き数で渡した値を持つノードのアドレスを返す関数を書きなさい。
Node* get_node_has_val(List* list, int val) {
	Node* node = NULL;
	Node* p = NULL;
	for (p = list->anchor->next; p != list->anchor; p = p->next) {
		if (p->val == val) {
			node = p;
			break;
		}
	}
	return node;
}

// 2. リストに含まれるノードへのポインタと値を引き数とし、渡したノードの位置に渡した値のノードを挿入する関数を書きなさい。その結果、渡したノードは挿入したノードの次のノードとなります。
void insert_val_at_node(List* list, Node* node, int val) {
	Node* new = create_node(val);
	link_prev(node, new);
}

// 3. リストに含まれるノードへのポインタを渡して、そのノードをリストから削除する関数を書きなさい。なお番兵ノードを渡した場合は削除してはいけません。
void delete_node(List* list, Node* node) {
	if (node == list->anchor) {
		return;
	}

	unlink_node(node);
	destroy_node(node);
}

//##############################################
// テストコード
//##############################################
void print_line_list(List* list) {
	printf("list = ");
	print_list(list);
}

void test_add_top() {
	printf("#######################################\n");
	List list = {0};
	create_list(&list);
	printf("create_list(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	add_top(&list, 1);
	printf("add_top(&list, 1);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	add_top(&list, 2);
	printf("add_top(&list, 2);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	add_top(&list, 3);
	printf("add_top(&list, 3);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	add_top(&list, 4);
	printf("add_top(&list, 4);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	add_top(&list, 5);
	printf("add_top(&list, 5);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");
}

void test_add_tail() {
	printf("#######################################\n");
	List list = {0};
	create_list(&list);
	printf("create_list(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	add_tail(&list, 1);
	printf("add_tail(&list, 1);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	add_tail(&list, 2);
	printf("add_tail(&list, 2);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	add_tail(&list, 3);
	printf("add_tail(&list, 3);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	add_tail(&list, 4);
	printf("add_tail(&list, 4);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	add_tail(&list, 5);
	printf("add_tail(&list, 5);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");
}

void test_del_top() {
	printf("#######################################\n");
	List list = {0};
	create_list(&list);
	add_tail(&list, 1);
	add_tail(&list, 2);
	add_tail(&list, 3);
	add_tail(&list, 4);
	add_tail(&list, 5);
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	del_top(&list);
	printf("del_top(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	del_top(&list);
	printf("del_top(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	del_top(&list);
	printf("del_top(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	del_top(&list);
	printf("del_top(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	del_top(&list);
	printf("del_top(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");
}

void test_del_tail() {
	printf("#######################################\n");
	List list = {0};
	create_list(&list);
	add_tail(&list, 1);
	add_tail(&list, 2);
	add_tail(&list, 3);
	add_tail(&list, 4);
	add_tail(&list, 5);
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	del_tail(&list);
	printf("del_tail(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	del_tail(&list);
	printf("del_tail(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	del_tail(&list);
	printf("del_tail(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	del_tail(&list);
	printf("del_tail(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	del_tail(&list);
	printf("del_tail(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	printf("\n");
}

//##############################################
void test_get_node_has_val_sub(List* list, int val) {
	Node* node;
	node = get_node_has_val(list, val);
	printf("node = get_node_has_val(list, %d); = %p", val, node);
	if (node == NULL) printf("(-)\n");
	else printf("(%d)\n", node->val);
}

//##############################################
void test_get_node_has_val() {
	printf("#######################################\n");
	List list = {0};
	create_list(&list);
	printf("create_list(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	test_get_node_has_val_sub(&list, 3);
	printf("\n");

	add_tail(&list, 1);
	printf("add_tail(&list, 1);\n");
	print_line_list(&list);
	dump_list(&list);
	test_get_node_has_val_sub(&list, 3);
	printf("\n");

	add_tail(&list, 2);
	printf("add_tail(&list, 2);\n");
	print_line_list(&list);
	dump_list(&list);
	test_get_node_has_val_sub(&list, 3);
	printf("\n");

	add_tail(&list, 3);
	printf("add_tail(&list, 3);\n");
	print_line_list(&list);
	dump_list(&list);
	test_get_node_has_val_sub(&list, 3);
	printf("\n");

	add_tail(&list, 4);
	printf("add_tail(&list, 4);\n");
	print_line_list(&list);
	dump_list(&list);
	test_get_node_has_val_sub(&list, 3);
	printf("\n");

	del_top(&list);
	printf("del_top(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	test_get_node_has_val_sub(&list, 3);
	printf("\n");

	del_top(&list);
	printf("del_top(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	test_get_node_has_val_sub(&list, 3);
	printf("\n");

	del_top(&list);
	printf("del_top(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	test_get_node_has_val_sub(&list, 3);
	printf("\n");

	del_top(&list);
	printf("del_top(&list);\n");
	print_line_list(&list);
	dump_list(&list);
	test_get_node_has_val_sub(&list, 3);
	printf("\n");
}

void test_insert_val_at_node() {
	printf("#######################################\n");
	List list = {0};
	create_list(&list);
	add_tail(&list, 10);
	add_tail(&list, 20);
	add_tail(&list, 30);
	add_tail(&list, 40);
	add_tail(&list, 50);
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	Node* node;
	node = get_node_has_val(&list, 10);
	printf("node = get_node_has_val(&list, 10); = %p\n", node);
	insert_val_at_node(&list, node, 9);
	printf("insert_val_at_node(&list, node, 9);\n");
	print_line_list(&list);
	printf("\n");

	node = get_node_has_val(&list, 20);
	printf("node = get_node_has_val(&list, 20); = %p\n", node);
	insert_val_at_node(&list, node, 19);
	printf("insert_val_at_node(&list, node, 19);\n");
	print_line_list(&list);
	printf("\n");

	node = get_node_has_val(&list, 30);
	printf("node = get_node_has_val(&list, 30); = %p\n", node);
	insert_val_at_node(&list, node, 29);
	printf("insert_val_at_node(&list, node, 29);\n");
	print_line_list(&list);
	printf("\n");

	node = get_node_has_val(&list, 40);
	printf("node = get_node_has_val(&list, 40); = %p\n", node);
	insert_val_at_node(&list, node, 39);
	printf("insert_val_at_node(&list, node, 39);\n");
	print_line_list(&list);
	printf("\n");

	node = get_node_has_val(&list, 50);
	printf("node = get_node_has_val(&list, 50); = %p\n", node);
	insert_val_at_node(&list, node, 49);
	printf("insert_val_at_node(&list, node, 49);\n");
	print_line_list(&list);
	printf("\n");

}

void test_delete_node() {
	printf("#######################################\n");
	List list = {0};
	create_list(&list);
	add_tail(&list, 10);
	add_tail(&list, 20);
	add_tail(&list, 30);
	add_tail(&list, 40);
	add_tail(&list, 50);
	print_line_list(&list);
	dump_list(&list);
	printf("\n");

	delete_node(&list, list.anchor);
	printf("delete_node(&list, list.anchor);\n");
	print_line_list(&list);
	printf("\n");

	Node* node;
	node = get_node_has_val(&list, 10);
	printf("node = get_node_has_val(&list, 10); = %p\n", node);
	delete_node(&list, node);
	printf("delete_node(&list, node);\n");
	print_line_list(&list);
	printf("\n");

	node = get_node_has_val(&list, 20);
	printf("node = get_node_has_val(&list, 20); = %p\n", node);
	delete_node(&list, node);
	printf("delete_node(&list, node);\n");
	print_line_list(&list);
	printf("\n");

	node = get_node_has_val(&list, 30);
	printf("node = get_node_has_val(&list, 30); = %p\n", node);
	delete_node(&list, node);
	printf("delete_node(&list, node);\n");
	print_line_list(&list);
	printf("\n");

	node = get_node_has_val(&list, 40);
	printf("node = get_node_has_val(&list, 40); = %p\n", node);
	delete_node(&list, node);
	printf("delete_node(&list, node);\n");
	print_line_list(&list);
	printf("\n");

	node = get_node_has_val(&list, 50);
	printf("node = get_node_has_val(&list, 50); = %p\n", node);
	delete_node(&list, node);
	printf("delete_node(&list, node);\n");
	print_line_list(&list);
	printf("\n");

}

int main() {
	test_add_top();
	test_add_tail();
	test_del_top();
	test_del_tail();
	test_get_node_has_val();
	test_insert_val_at_node();
	test_delete_node();
	return 0;
}

実行結果

#######################################
create_list(&list);
list = 

add_top(&list, 1);
list = 1 

add_top(&list, 2);
list = 2 1 

add_top(&list, 3);
list = 3 2 1 

add_top(&list, 4);
list = 4 3 2 1 

add_top(&list, 5);
list = 5 4 3 2 1 

#######################################
create_list(&list);
list = 

add_tail(&list, 1);
list = 1 

add_tail(&list, 2);
list = 1 2 

add_tail(&list, 3);
list = 1 2 3 

add_tail(&list, 4);
list = 1 2 3 4 

add_tail(&list, 5);
list = 1 2 3 4 5 

#######################################
list = 1 2 3 4 5 

del_top(&list);
list = 2 3 4 5 

del_top(&list);
list = 3 4 5 

del_top(&list);
list = 4 5 

del_top(&list);
list = 5 

del_top(&list);
list = 

#######################################
list = 1 2 3 4 5 

del_tail(&list);
list = 1 2 3 4 

del_tail(&list);
list = 1 2 3 

del_tail(&list);
list = 1 2 

del_tail(&list);
list = 1 

del_tail(&list);
list = 

#######################################
create_list(&list);
list = 
node = get_node_has_val(list, 3); = 0x0(-)

add_tail(&list, 1);
list = 1 
node = get_node_has_val(list, 3); = 0x0(-)

add_tail(&list, 2);
list = 1 2 
node = get_node_has_val(list, 3); = 0x0(-)

add_tail(&list, 3);
list = 1 2 3 
node = get_node_has_val(list, 3); = 0xb40000799d472700(3)

add_tail(&list, 4);
list = 1 2 3 4 
node = get_node_has_val(list, 3); = 0xb40000799d472700(3)

del_top(&list);
list = 2 3 4 
node = get_node_has_val(list, 3); = 0xb40000799d472700(3)

del_top(&list);
list = 3 4 
node = get_node_has_val(list, 3); = 0xb40000799d472700(3)

del_top(&list);
list = 4 
node = get_node_has_val(list, 3); = 0x0(-)

del_top(&list);
list = 
node = get_node_has_val(list, 3); = 0x0(-)

#######################################
list = 10 20 30 40 50 

node = get_node_has_val(&list, 10); = 0xb40000799d472700
insert_val_at_node(&list, node, 9);
list = 9 10 20 30 40 50 

node = get_node_has_val(&list, 20); = 0xb40000799d472820
insert_val_at_node(&list, node, 19);
list = 9 10 19 20 30 40 50 

node = get_node_has_val(&list, 30); = 0xb40000799d472760
insert_val_at_node(&list, node, 29);
list = 9 10 19 20 29 30 40 50 

node = get_node_has_val(&list, 40); = 0xb40000799d472580
insert_val_at_node(&list, node, 39);
list = 9 10 19 20 29 30 39 40 50 

node = get_node_has_val(&list, 50); = 0xb40000799d472160
insert_val_at_node(&list, node, 49);
list = 9 10 19 20 29 30 39 40 49 50 

#######################################
list = 10 20 30 40 50 

delete_node(&list, list.anchor);
list = 10 20 30 40 50 

node = get_node_has_val(&list, 10); = 0xb40000799d472610
delete_node(&list, node);
list = 20 30 40 50 

node = get_node_has_val(&list, 20); = 0xb40000799d472190
delete_node(&list, node);
list = 30 40 50 

node = get_node_has_val(&list, 30); = 0xb40000799d4723a0
delete_node(&list, node);
list = 40 50 

node = get_node_has_val(&list, 40); = 0xb40000799d4726a0
delete_node(&list, node);
list = 50 

node = get_node_has_val(&list, 50); = 0xb40000799d472040
delete_node(&list, node);
list =

ソースコードはこちらからダウンロードもできます。

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

C言語教室 第21回 - 循環リスト（回答提出）

C言語教室第21回 - 循環リスト（回答提出）