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

AyumiKatayama

2023年4月13日 18:35

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

課題
・リストの最後に要素を追加する関数を書きなさい。
・リストの先頭の要素を削除する関数を書きなさい。
・n番目の要素を返す関数を書きなさい。
・要素の中に指定した値が含まれるかを返す関数を書きなさい。

前回、単方向リストを回答させて頂きました。
プログラミングにおけるリストの位置付けについてはそちらの方でクダクダしく(?)申し上げました(笑)。

さて！

次は双方向リストです。
右手で前の人と
左手で後ろの人と
手をつないでいるようなものです。

単方向リストにくらべると双方向リストは情報量が増えるのですが、その分実装はしやすい。単方向リストが出来上がってますから、それを双方向リストにアップデートすればよろしい。

ウロボロスの蛇のようにグルッと回せば・・・

『次回は、双方向リストの改良版である循環リストを取り上げます』

ん？

！！！

循環しないのか！
NULL終端！？

えーーー！

めんどくさい・・・(笑)

Segmentation faultを睨み付け、
無限ループをぼんやりと眺め、
これでもかというくらいNULLチェックを入れた末に、
ようやく出来上がりました。

引数の「Node」の大部分は「List」に変更。
「<stdbool.h>」を使ってみた。
コードの半分以上はテストコード。

プログラム

 #include  <stdlib.h> #include  <stdbool.h>

typedef struct _node {
	int data;
	struct _node* prev;
	struct _node* next;
} Node;

typedef struct _list {
  struct _node* pTop;
  struct _node* pTail;
} List;

List* prepend(List* head, int data);
List* append(List* head, int data);
List* free_head(List* head);
List* free_list(List *head);
int get_count(const List* head);
const Node* get_node(const List* head, int index);
Node* get_tail_node(List* head);
bool has_data(const List* head, int data);
void print_array(const int a[], int count);
void print_list(const List* head);
int to_array(const List* head, int array[], int max_count);
List* 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_has_data();
void test_to_array();
void test_from_array();

//#####################################
// リストの先頭に要素を追加する
List* prepend(List* _head, int data) {
	List* head = _head;
	if (head == NULL) {
		head = (List*)malloc(sizeof(List));
		head->pTop = NULL;
		head->pTail = NULL;
	}

	Node* now_top = head->pTop;
	Node* new_top = (Node*)malloc(sizeof(Node));
	new_top->data = data;
	new_top->next = now_top;
	new_top->prev = NULL;

	if (now_top != NULL) {
		now_top->prev = new_top;
	} else {
		head->pTail = new_top;
	}
	head->pTop = new_top;

	return head;
}

//#####################################
// リストの最後に要素を追加する
List* append(List* _head, int data) {
	List* head = _head;
	if (head == NULL) {
		head = (List*)malloc(sizeof(List));
		head->pTop = NULL;
		head->pTail = NULL;
	}

	Node* now_tail = head->pTail;
	Node* new_tail = (Node*)malloc(sizeof(Node));
	new_tail->data = data;
	new_tail->next = NULL;
	new_tail->prev = now_tail;

	if (now_tail != NULL) {
		now_tail->next = new_tail;
	} else {
		head->pTop = new_tail;
	}

	head->pTail = new_tail;

	return head;
}

//#####################################
// リストの先頭の要素を削除する
List* free_head(List* head) {
	if (head == NULL) {
		return head;
	}

	Node* free_node = head->pTop;
	if (free_node == NULL) {
		return head;
	}

	Node* next = free_node->next;
	if (next != NULL) {
		next->prev = free_node->prev;
	}

	head->pTop = next;
	if (head->pTop == NULL) {
		head->pTail = NULL;
	}

	free(free_node);
	return head;
}

//#####################################
// リストの全ての要素を削除する
List* free_list(List* head) {
	if (head == NULL) {
		return head;
	}

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

//#####################################
// リストの要素の数を返す
int get_count(const List* head) {
	if (head == NULL) {
		return 0;
	}

	int count = 0;
	const Node* p;
	for (p = head->pTop; p != NULL; p = p->next) {
		count++;
	}
	return count;
}

//#####################################
// n番目の要素を返す
const Node* get_node(const List* head, int index) {
	const Node* node = NULL;
	if (head == NULL) {
		return node;
	}

	int count = 0;
	const Node* p;
	for (p = head->pTop; p != NULL; p = p->next) {
		count++;
		if (count == index) {
			node = p;
			break;
		}
	}
	return node;
}

//#####################################
// 末尾の要素を返す
Node* get_tail_node(List* head) {
	if (head == NULL) {
		return NULL;
	}

	return head->pTail;
}

//#####################################
// 要素の中に指定した値が含まれるかを返す
bool has_data(const List* head, int data) {
	bool has = false;
	if (head == NULL) {
		return has;
	}

	const Node* p;
	for (p = head->pTop; p != NULL; p = p->next) {
		if (p->data == data) {
			has = true;
			break;
		}
	}
	return has;
}

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

void print_array_b(const char a[], int count) {
	int i = 0;
	for (i = 0; i < count; ++i) {
		printf("%02x ", (unsigned char)a[i]);
	}
}

//#####################################
void print_list(const List* head) {
	if (head == NULL) {
		return;
	}

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

//#####################################
void print_list_reverse(const List* head) {
	if (head == NULL) {
		return;
	}

	const Node* p;
	for (p = head->pTail; p != NULL; p = p->prev) {
		printf("%d ", p->data);
	}
}

//#####################################
// リストを配列にコピーする
int to_array(const List* head, int array[], int max_count) {
	int count = 0;
	if (head == NULL) {
		return count;
	}

	const Node* p = head->pTop;
	int i = 0;
	for (i = 0; i < max_count; ++i) {
		if (p == NULL)
		{
			break;
		}
		array[count] = p->data;
		count++;
		p = p->next;
	}
	return count;
}

//#####################################
// 配列からリストを作る関数を書きなさい。
List* from_array(const int array[], const int count) {
	List* head = (List*)malloc(sizeof(List));
	head->pTop = NULL;
	head->pTail = NULL;

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

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

//#####################################
void print_list_head(List* head) {
	printf("print_list         (head) = ");
	print_list(head);
	printf("\n");
	printf("print_list_reverse (head) = ");
	print_list_reverse(head);
	printf("\n");
}

//#####################################
//=================================
List* test_append_sub(List* head, int data) {
	printf("head = append(head, data)\n");
	head = append(head, data);
	print_list_head(head);
	printf("\n");
	return head;
}
//=================================
void test_append() {
	//-----------------------------
	List* head = NULL;
	printf("head = NULL\n");
	printf("head = append(head, 1)\n");
	head = append(head, 1);
	print_list_head(head);
	printf("\n");

	//-----------------------------
	head = test_append_sub(head, 2);
	head = test_append_sub(head, 3);
	head = test_append_sub(head, 4);

	//-----------------------------
	head = free_list(head);
}

//#####################################
//=================================
List* test_free_head_sub(List* head) {
	printf("head = free_head(head)\n");
	head = free_head(head);
	print_list_head(head);
	printf("\n");
	return head;
}
//=================================
void test_free_head() {
	//-----------------------------
	List* head = NULL;
	printf("head = NULL\n");
	printf("head = free_head(head)\n");
	head = free_head(head);
	print_list_head(head);
	printf("\n");

	//-----------------------------
	head = append(head, 1);
	head = append(head, 2);
	head = append(head, 3);
	head = append(head, 4);
	print_list_head(head);
	printf("\n");

	//-----------------------------
	head = test_free_head_sub(head);
	head = test_free_head_sub(head);
	head = test_free_head_sub(head);
	head = test_free_head_sub(head);
	head = test_free_head_sub(head);

	//-----------------------------
	head = free_list(head);
}

//#####################################
//=================================
List* test_get_count_append(List* head, int add_data) {
	printf("append(head, 1)\n");
	head = append(head, 1);

	int count;
	count = get_count(head);
	printf("get_count(head) = %d\n", count);
	printf("\n");
	return head;
}
//=================================
List* test_get_count_free(List* head) {
	printf("head = free_head(head)\n");
	head = free_head(head);

	int count;
	count = get_count(head);
	printf("get_count(head) = %d\n", count);
	printf("\n");
	return head;
}
//=================================
void test_get_count() {
	int count;

	//-----------------------------
	List* head = NULL;
	printf("head = NULL\n");
	count = get_count(head);
	printf("get_count(head) = %d\n", count);
	printf("\n");

	//-----------------------------
	head = test_get_count_append(head, 1);
	head = test_get_count_append(head, 2);
	head = test_get_count_append(head, 3);
	head = test_get_count_append(head, 4);

	//-----------------------------
	head = test_get_count_free(head);
	head = test_get_count_free(head);
	head = test_get_count_free(head);
	head = test_get_count_free(head);
	head = test_get_count_free(head);

	//-----------------------------
	head = free_list(head);
}

//#####################################
//=================================
List* test_get_node_append(List* head, int add_data, int index){
	head = append(head, add_data);
	printf("append(head, %d)\n", add_data);

	const Node* const_node = NULL;
	const_node = get_node(head, index);
	printf("get_node(head, index) = %p ", const_node);
	if (const_node != NULL) {
		printf("(%d)", const_node->data);
	}
	printf("\n");
	printf("\n");
	return head;
}
//=================================
List* test_get_node_free(List* head, int index) {
	printf("head = free_head(head)\n");
	head = free_head(head);

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

	return head;
}
//=================================
void test_get_node() {
	List* head = 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 = test_get_node_append(head, 1, 2);
	head = test_get_node_append(head, 2, 2);
	head = test_get_node_append(head, 3, 2);

	//-----------------------------
	head = test_get_node_free(head, 2);
	head = test_get_node_free(head, 2);
	head = test_get_node_free(head, 2);
	head = test_get_node_free(head, 2);
	head = test_get_node_free(head, 2);

	//-----------------------------
	head = free_list(head);
}

//#####################################
//=================================
List* test_get_tail_node_append(List* head, int add_data) {
	head = append(head, add_data);
	printf("append(head, %d)\n", add_data);

	Node* node = NULL;
	node = get_tail_node(head);
	printf("get_tail_node(head) = %p ", node);
	if (node != NULL) {
		printf("(%d)", node->data);
	}
	printf("\n");
	printf("\n");
	return head;
}
//=================================
List* test_get_tail_node_free(List* head) {
	printf("head = free_head(head)\n");
	head = free_head(head);

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

	return head;
}
//=================================
void test_get_tail_node() {
	List* head = NULL;
	Node* 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 = test_get_tail_node_append(head, 1);
	head = test_get_tail_node_append(head, 2);
	head = test_get_tail_node_append(head, 3);

	//-----------------------------
	head = test_get_tail_node_free(head);
	head = test_get_tail_node_free(head);
	head = test_get_tail_node_free(head);
	head = test_get_tail_node_free(head);
	head = free_head(head);
		
	//-----------------------------
	head = free_list(head);
}

//#####################################
//=================================
List* test_has_data_append(List* head, int add_data, int data){
	head = append(head, add_data);
	printf("append(head, %d)\n", add_data);

	bool has = false;
	has = has_data(head, data);
	printf("has_data(head, %d) = %d ", data, has);
	printf("\n");
	printf("\n");
	return head;
}
//=================================
List* test_has_data_free(List* head, int data) {
	printf("head = free_head(head)\n");
	head = free_head(head);

	bool has = false;
	has = has_data(head, data);
	printf("has_data(head, %d) = %d ", data, has);
	printf("\n");
	printf("\n");

	return head;
}
//=================================
void test_has_data() {
	List* head = NULL;
	bool has = false;

	//-----------------------------
	printf("head = NULL\n");
	has = has_data(head, 2);
	printf("has_data(head, 2) = %d ", has);
	printf("\n");
	printf("\n");

	//-----------------------------
	head = test_has_data_append(head, 1, 2);
	head = test_has_data_append(head, 2, 2);
	head = test_has_data_append(head, 3, 2);

	//-----------------------------
	head = test_has_data_free(head, 2);
	head = test_has_data_free(head, 2);
	head = test_has_data_free(head, 2);
	head = test_has_data_free(head, 2);

	//-----------------------------
	head = free_list(head);
}

//#####################################
//=================================
List* test_to_array_append(List* head, int add_data){
	int data[8] = {0};
	int count;
	printf("append(head, %d)\n", add_data);
	head = append(head, add_data);
	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");
	return head;
}
//=================================
List* test_to_array_free(List* head) {
	int data[8] = {0};
	int count;
	printf("head = free_head(head)\n");
	head = free_head(head);
	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");
	return head;
}

//=================================
void test_to_array() {
	//-----------------------------
	int data[8] = {0};
	int count;
	List* head = NULL;
	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");

	//-----------------------------
	head = test_to_array_append(head, 1);
	head = test_to_array_append(head, 2);
	head = test_to_array_append(head, 3);
	head = test_to_array_append(head, 4);
	head = test_to_array_append(head, 5);
	head = test_to_array_append(head, 6);
	head = test_to_array_append(head, 7);
	head = test_to_array_append(head, 8);
	head = test_to_array_append(head, 9);

	//-----------------------------
	head = test_to_array_free(head);
	head = test_to_array_free(head);
	head = test_to_array_free(head);
	head = test_to_array_free(head);
	head = test_to_array_free(head);
	head = test_to_array_free(head);
	head = test_to_array_free(head);
	head = test_to_array_free(head);
	head = test_to_array_free(head);
	head = test_to_array_free(head);

	//-----------------------------
	head = free_list(head);
}

//#####################################
void test_from_array() {
	int data[8] = {0, 1, 2, 3, 4, 5, 6, 7};

	//-----------------------------
	List* head = NULL;
	printf("head = NULL\n");
	head = from_array(NULL, 8);
	printf("head = from_array(NULL, 8) = %p\n", head);
	print_list_head(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);
	print_list_head(head);
	printf("\n");
	printf("\n");

	//-----------------------------
	head = free_list(head);
}

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_has_data();

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

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

	return 0;
}

実行結果

#####################################
head = NULL
head = append(head, 1)
print_list         (head) = 1 
print_list_reverse (head) = 1 

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

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

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

#####################################
head = NULL
head = free_head(head)
print_list         (head) = 
print_list_reverse (head) = 

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

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

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

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

head = free_head(head)
print_list         (head) = 
print_list_reverse (head) = 

head = free_head(head)
print_list         (head) = 
print_list_reverse (head) = 

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

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

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

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

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

head = free_head(head)
get_count(head) = 3

head = free_head(head)
get_count(head) = 2

head = free_head(head)
get_count(head) = 1

head = free_head(head)
get_count(head) = 0

head = free_head(head)
get_count(head) = 0

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

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

append(head, 2)
get_node(head, index) = 0xb400007047aa87f0 (2)

append(head, 3)
get_node(head, index) = 0xb400007047aa87f0 (2)

head = free_head(head)
get_node(head, index) = 0xb400007047aa8910 (3)

head = free_head(head)
get_node(head, index) = 0x0 

head = free_head(head)
get_node(head, index) = 0x0 

head = free_head(head)
get_node(head, index) = 0x0 

head = free_head(head)
get_node(head, index) = 0x0 

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

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

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

append(head, 3)
get_tail_node(head) = 0xb400007047aa82b0 (3)

head = free_head(head)
get_tail_node(head) = 0xb400007047aa82b0 (3)

head = free_head(head)
get_tail_node(head) = 0xb400007047aa82b0 (3)

head = free_head(head)
get_tail_node(head) = 0x0 

head = free_head(head)
get_tail_node(head) = 0x0 

#####################################
head = NULL
has_data(head, 2) = 0 

append(head, 1)
has_data(head, 2) = 0 

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

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

head = free_head(head)
has_data(head, 2) = 1 

head = free_head(head)
has_data(head, 2) = 0 

head = free_head(head)
has_data(head, 2) = 0 

head = free_head(head)
has_data(head, 2) = 0 

#####################################
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)
to_array(head, data, 8) = 4
print_array (data) = 1 2 3 4 0 0 0 0 

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

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

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

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

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

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

head = free_head(head)
to_array(head, data, 8) = 7
print_array (data) = 3 4 5 6 7 8 9 0 

head = free_head(head)
to_array(head, data, 8) = 6
print_array (data) = 4 5 6 7 8 9 0 0 

head = free_head(head)
to_array(head, data, 8) = 5
print_array (data) = 5 6 7 8 9 0 0 0 

head = free_head(head)
to_array(head, data, 8) = 4
print_array (data) = 6 7 8 9 0 0 0 0 

head = free_head(head)
to_array(head, data, 8) = 3
print_array (data) = 7 8 9 0 0 0 0 0 

head = free_head(head)
to_array(head, data, 8) = 2
print_array (data) = 8 9 0 0 0 0 0 0 

head = free_head(head)
to_array(head, data, 8) = 1
print_array (data) = 9 0 0 0 0 0 0 0 

head = free_head(head)
to_array(head, data, 8) = 0
print_array (data) = 0 0 0 0 0 0 0 0 

head = free_head(head)
to_array(head, data, 8) = 0
print_array (data) = 0 0 0 0 0 0 0 0 

#####################################
head = NULL
head = from_array(NULL, 8) = 0xb400007037aa1410
print_list         (head) = 
print_list_reverse (head) = 


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

ダウンロード

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

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

プログラム

実行結果

ダウンロード

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