c言語 リスト構造の要素の追加

Question

c言語にてリスト構造に要素を追加するinsert関数を作りました。

nodeの前にｐを入れたいのですが、書き方が分かりません。

// nodeがpの次に来るように代入
の後に2行で書きたいのですがどなたかわかる方教えてください。

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

#define LEN 10

// 文字列１つとポインタの構造体
typedef struct node{
	char str[LEN];
	struct node* next;
} NODE;

// インサート関数
NODE* insert(char str[LEN], NODE* node){
	if(node != NULL){ // nodeが空でないなら
		if(strcmp(str, node->str) > 0){ // 「str」が「node->str」より後に来る文字列の場合
			insert(str, node->next); // 追加先をnode->nextにしてinsertを実行
		}else
			//挿入用ノードの生成
			NODE* p = (NODE*)malloc(sizeof(NODE));
			strcpy(p->str, str);

			// nodeがpの次に来るように代入
			 
			 
		}
	}else{
		node = (NODE*)malloc(sizeof(NODE));
		strcpy(node->str, str);
		node->next = NULL;
	}

	return node;
}

Comments

[jimbe]

>// nodeがpの次に来るように代入
>の後に2行で書きたい

なぜ2行なのでしょうか。

Answer 1

すでに解決済みですが、こんなのでできるのではないかと。

// インサート関数
NODE* insert(char str[LEN], NODE* node)
{
	if (node != NULL) {								// nodeが空でないなら
		if (strcmp(str, node->str) > 0) {			// 「str」が「node->str」より後に来る文字列の場合
			node->next = insert(str, node->next);	// 追加先をnode->nextにしてinsertを実行
		} else {
			//挿入用ノードの生成
			NODE* p = (NODE*)malloc(sizeof(NODE));
			strcpy(p->str, str);
			p->next = node;							// nodeがpの次に来るように代入
			node = p;
		}
	} else {
		node = (NODE*)malloc(sizeof(NODE));
		strcpy(node->str, str);
		node->next = NULL;
	}

	return node;
}

Answer 2

node の前に入れるのであれば node の前の node が分からないといけないはずですが、該当箇所ではそれが分からないのではないでしょうか。
(そもそもバグがあるようにも見えますが。)

---

2行とか再帰とか元のコードに拘り(縛り?)が無ければ、以下で動作しました。

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

#define LEN 10

// 文字列１つとポインタの構造体
typedef struct node {
  char str[LEN];
  struct node* next;
} NODE;

// インサート関数
NODE* insert(char str[LEN], NODE* root) {
  //printf("insert(%s,%p)\n", str, root);
  NODE *p = (NODE*)malloc(sizeof(NODE));
  strcpy(p->str, str);
  p->next = NULL;

  NODE dummy;
  dummy.next = root;
  NODE *prev = &dummy;

  for( ; prev->next!=NULL; prev=prev->next) {
    NODE *node = prev->next;
    //printf("strcmp(%s,%s)=%d\n", str, node->str, strcmp(str, node->str));
    if(strcmp(str, node->str) <= 0) {
      p->next = node;
      break;
    }
  }

  prev->next = p;
  return dummy.next;
}

void print(NODE *node) {
  for( ; node!=NULL; node=node->next) {
    printf("%s -> ", node->str);
  }
  printf("NULL\n");
}

int main(void) {
  NODE *root = NULL;
  print(root);
  
  root = insert("123", root);
  print(root);

  root = insert("abc", root);
  print(root);

  root = insert("ABC", root);
  print(root);

  root = insert("0", root);
  print(root);

  root = insert("xyz", root);
  print(root);
}

実行結果(piaza.io)

NULL
123 -> NULL
123 -> abc -> NULL
123 -> ABC -> abc -> NULL
0 -> 123 -> ABC -> abc -> NULL
0 -> 123 -> ABC -> abc -> xyz -> NULL

Answer 3

単方向リストなんだから とあるノードの前に挿入 は困難です。

とあるノードの ひとつ前のノード を特定できるのであれば、 そのノードの後ろに挿入(これは簡単)すればいい。
それができず、前に挿入したいなら 双方向リスト をオススメします。