リストの動き

KTN19 · #1

数値を入力し、その数値がリストの要素にあるかないか検索する。
要素としてある場合、数値はリストに代入せず、またリストにあるその数値も削除する。
要素としてない時、リストに代入する。　と言うプログラムを書きたいのだが、
リストの動きがわからず、申し訳ないのですがご教授お願いします。

求めたい実行結果
input = 3
[ 3 ]
input = 5
[ 5 3 ]
input = 3
[ 5 ]
input = 4
[ 4 5 ]
input = 4
[ 5 ]
input = ^d

自分のプログラム実行結果
input = 3
[ 3 ]
input = 5
[ 5 3 ]
input = 3
[ 5 ]
input = 4
[ 4 5 ]
input = 4
Error: p->next = NULL

以下プログラム

コード:

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

typedef struct list_node_s
{
	int val;
	struct list_node_s *next;
} list_node_t;

static list_node_t* insert_node(list_node_t *p, int val);
static void remove_node(list_node_t *p);

void list_print(list_node_t *list);
list_node_t* create_node(int val);
list_node_t* list_insert(list_node_t *list, int val);
list_node_t* list_find(list_node_t *list, int val);
list_node_t* list_insert_uniq(list_node_t *list, int val);
list_node_t* list_insert_delete_dup(list_node_t *list, int val);

int main(void)
{
	list_node_t *head_p = create_node(0); /* ヘッダ (ダミー) */
	
	for (;;) {
		int val;
		fprintf(stderr, "input = ");
		if (scanf("%d", &val)==EOF) { break; }
		list_insert_delete_dup(head_p,val);
		list_print(head_p);
	}
	list_delete(head_p); 
	
	free(head_p);
	return 0;
}

/* 値 val を保持する新しい節点を作成し, その節点へのポインタを返す */
list_node_t* create_node(int val)
{
	list_node_t *new_node;
	new_node = (list_node_t*) malloc(sizeof(list_node_t));
	if (new_node == NULL) {
		fprintf(stderr, "節点の割当てに失敗しました\n");
		exit(1);
	}
	new_node->val = val;
	new_node->next = NULL;
	return new_node;
}

/* n の指す節点の直後に, 値 val を保持する新しい節点を挿入し, 
その節点へのポインタを返す */
static list_node_t* insert_node(list_node_t *n, int val)
{
	list_node_t *new_node = create_node(val);
	new_node->next = n->next;
	n->next = new_node;
	 
	return new_node;
}

/* リストの内容を表示する */
void list_print(list_node_t *head_p)
{
	list_node_t *p;
	
	printf("[ ");
	for( p = head_p->next; p != NULL; p = p->next ){
		printf( " %d ", p->val );
	}
	printf(" ]\n");
}

/* p の指す節点の *直後* の節点を削除 */
static void remove_node(list_node_t *p)
{
	list_node_t *old = p->next;
	if (old==NULL) {
		fprintf(stderr, "Error: p->next = NULL\n");
		exit(1);
	}
	p->next = old->next;
	free(old);
	old = NULL;
}

/* ヘッダが head_p のリストの先頭に値 val (の節点) を挿入する */
list_node_t* list_insert(list_node_t* head_p, int val)
{
	list_node_t* p = insert_node(head_p,val);
	return p;
}

/* リスト中に値が val の節点を探す
   見つかればその節点のポインタを, なければ NULL を返す */
list_node_t* list_find(list_node_t *head_p, int val)
{
	list_node_t *p;
	
	for( p = head_p->next; p != NULL; p = p->next ){
		if(p->val == val){
			return p;
		}
	}
	return NULL;
}

/* 以下を編集したい */
list_node_t* list_insert_delete_dup(list_node_t* head_p, int val)
{
	list_node_t *p;
	list_node_t *q = NULL;
	
	p = list_find(head_p, val);
	if( p == NULL ){
		q = list_insert(head_p,val);
	}
	else{
        	remove_node(p+1);
		return NULL;
	}

	return q;
}

あんどーなつ · #2

多分上のプログラムはプログラムとしては見やすいほうなのでしょうが、読むより書くほうが簡単だったので書きました。関数の作り方（考え方？）が少し違います。

コード:

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

typedef struct node {
	int val;
	struct node *next;
} list;

list *get_empty() {
	return NULL;
}

void _print(list *lst) {
	if (lst != NULL) {
		printf("%d ", lst->val);
		_print(lst->next);
	}
}
void print(list *lst) {
	printf("[ ");
	_print(lst);
	printf("]\n");
}

list *find(list *lst, int val) {
	if (lst == NULL) return NULL;
	if (lst->val == val) return lst;
	return find(lst->next, val);
}

list *add(list *lst, int val) {
	list *newlst = malloc(sizeof(list));
	newlst->val = val;
	newlst->next = lst;
	return newlst;
}

// removeという関数はすでに存在
list *remove_node(list *lst, int val) {
	if (lst == NULL) return NULL;
	if (lst->val == val) {
		list *next = lst->next;
		free(lst);
		return remove_node(next, val);
	} else {
		lst->next = remove_node(lst->next, val);
		return lst;
	}
}

void remove_list(list *lst) {
	if (lst != NULL) {
		list *next = lst->next;
		free(lst);
		remove_list(next);
	}
}

/* デバッグの時に書いたmain
int main() {
	list *lst0 = get_empty();
	list *lst1 = add(lst0, 5);
	list *lst2 = add(lst1, 3);
	print(NULL);
	print(lst1);
	print(lst2);
	print(find(lst2, 5));
	print(find(lst2, 4));
	print(remove_node(lst2, 5));
	remove_list(lst2);
	return 0;
}
*/

int main() {
	list *lst = get_empty();
	while (1) {
		int val;
		printf("input = ");
		if (scanf("%d", &val) == EOF) break;
		if (find(lst, val) == NULL)
			lst = add(lst, val);
		else
			lst = remove_node(lst, val);
		print(lst);
	}
	remove_list(lst);
	return 0;
}

#3

KTN19 さんが書きました:以下プログラム

119行目で「配列の最後の要素の次」へのポインタを渡し、77行目でそれをデリファレンスしているので未定義動作が発生する、などの問題があるようですが、
最大の問題として、31行目で使用されているlist_deleteが宣言も定義もされていないため、コンパイルが通りません。
コンパイルが通らないので、(インタプリタなどの特殊な環境でなければ？)実行結果が得られるわけがありません。
本物の(提示された実行結果が得られる(可能性がある))プログラムを提示するか、
このプログラムでKTN19さんの環境では実行結果が得られるなら、その環境の情報を提示していただけますか？

#4

使う関数は全て適切に宣言や定義をし、未定義動作を起こさないとともに、
他の関数が「直後に挿入」「直後の要素を削除」なので、list_find関数も「その節点のポインタ」ではなく「直後が探したい値である節点のポインタ」を返すようにするとやりやすそうですね。

KTN19 · #5

ご指摘ありがとうございます。

みけCAT さんが書きました:list_find関数も「その節点のポインタ」ではなく「直後が探したい値である節点のポインタ」を返す

どうすれば、直後が接点のポインタに返せるのでしょうか？

以下プログラム

コード:

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

typedef struct list_node_s
{
	int val;
	struct list_node_s *next;
} list_node_t;

static list_node_t* insert_node(list_node_t *p, int val);
static void remove_node(list_node_t *p);

void list_print(list_node_t *list);
list_node_t* create_node(int val);
list_node_t* list_insert(list_node_t *list, int val);
list_node_t* list_find(list_node_t *list, int val);
list_node_t* list_insert_uniq(list_node_t *list, int val);
list_node_t* list_insert_delete_dup(list_node_t *list, int val);
void list_delete(list_node_t* head_p); // 挿入ミスです。

int main(void)
{
	list_node_t *head_p = create_node(0); /* ヘッダ (ダミー) */
	
	for (;;) {
		int val;
		fprintf(stderr, "input = ");
		if (scanf("%d", &val)==EOF) { break; }
		list_insert_delete_dup(head_p,val);
		list_print(head_p);
	}
	list_delete(head_p); 
	
	free(head_p);
	return 0;
}

/* 値 val を保持する新しい節点を作成し, その節点へのポインタを返す */
list_node_t* create_node(int val)
{
	list_node_t *new_node;
	new_node = (list_node_t*) malloc(sizeof(list_node_t));
	if (new_node == NULL) {
		fprintf(stderr, "節点の割当てに失敗しました\n");
		exit(1);
	}
	new_node->val = val;
	new_node->next = NULL;
	return new_node;
}

/* n の指す節点の直後に, 値 val を保持する新しい節点を挿入し, 
その節点へのポインタを返す */
static list_node_t* insert_node(list_node_t *n, int val)
{
	list_node_t *new_node = create_node(val);
	new_node->next = n->next;
	n->next = new_node;
	 
	return new_node;
}

/* リストの内容を表示する */
void list_print(list_node_t *head_p)
{
	list_node_t *p;
	
	printf("[ ");
	for( p = head_p->next; p != NULL; p = p->next ){
		printf( " %d ", p->val );
	}
	printf(" ]\n");
}

/* p の指す節点の *直後* の節点を削除 */
static void remove_node(list_node_t *p)
{
	list_node_t *old = p->next;
	if (old==NULL) {
		fprintf(stderr, "Error: p->next = NULL\n");
		exit(1);
	}
	p->next = old->next;
	free(old);
	old = NULL;
}

/* ヘッダが head_p のリストの先頭に値 val (の節点) を挿入する */
list_node_t* list_insert(list_node_t* head_p, int val)
{
	list_node_t* p = insert_node(head_p,val);
	return p;
}

/* リスト中に値が val の節点を探す
   見つかればその節点のポインタを, なければ NULL を返す */
list_node_t* list_find(list_node_t *head_p, int val)
{
	list_node_t *p;
	
	for( p = head_p->next; p != NULL; p = p->next ){
		if(p->val == val){
			return p;
		}
	}
	return NULL;
}

/* 以下を編集したい */
list_node_t* list_insert_delete_dup(list_node_t* head_p, int val)
{
	list_node_t *p;
	list_node_t *q = NULL;
	
	p = list_find(head_p, val);
	if( p == NULL ){
		q = list_insert(head_p,val);
	}
	else{
        	remove_node(p+1);
		return NULL;
	}

	return q;
}

/*  申し訳ありません、挿入し忘れていました。*/
void list_delete(list_node_t* head_p)
{
	list_node_t *p = head_p->next;
	while ( p!=NULL ) {
		list_node_t *next = p->next; 
		free(p);
		p = next;
	}
	head_p->next = NULL;
}

#6

KTN19 さんが書きました:どうすれば、直後が接点のポインタに返せるのでしょうか？

「直後が接点のポインタに返せる」(すいません、意味がよくわかりません)
ような未定義動作を起こさないプログラムを書き、コンパイルし、実行すればいいでしょう。

直後が探したい値である節点のポインタを返すためには、直後が探したい値である節点を見つけたらそのポインタを返すようにする、
すなわちlist_find関数内のp->val == valという条件をp->next->val == valにすればいいでしょう。
また、値をチェックする位置が変わるため、for文の初期化式と条件式の修正も必要です。

KTN19 · #7

早急な返信ありがとうございます。
返信の日本語足らずな部分大変失礼いたしました。

みけCAT さんが書きました:すなわちlist_find関数内のp->val == valという条件をp->next->val == valにすればいいでしょう。

とても分かりやすく、すぐに理解できました。

コード:

list_node_t* list_find(list_node_t *head_p, int val)
{
	list_node_t *p;
	
	for( p = head_p; p->next != NULL; p = p->next ){
		if(p->next->val == val){
			return p;
		}
	}
	return NULL;
}
list_node_t* list_insert_delete_dup(list_node_t* head_p, int val)
{
	list_node_t *p;
	list_node_t *q = NULL;
	
	p = list_find(head_p, val);
	if( p == NULL ){
		q = list_insert(head_p,val);
	}
	else{
		remove_node(p);
		return NULL;
	}
	return q;
}

		4月 2024
日	月	火	水	木	金	土
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

リストの動き

リストの動き

Re: リストの動き

Re: リストの動き

Re: リストの動き

Re: リストの動き

Re: リストの動き

Re: リストの動き