ｃ言語 リスト ノード

Question

void insert(struct node *p, char x) {
    struct node *n;

    n = (struct node*)malloc(sizeof(struct node));

    n->element = x;
    n->next = p->next;
    p->next = n;
    

このコードで文字を追加（例:abc）すると返ってくる値がcbaとなってしまいます。例えば ./a.out abc　としたとき abc と返ってきてほしいです。値の返し方はリストの先頭から順に返していくやり方です。リストの先頭に追加してしまっているのが原因だと思うんですが、リストの末尾に追加する方法がいまいちよくわかりません。insert内を変えたいのですがどう変えたら良いのかわかりません。アドバイスを頂ければ幸いです。

Comments

[y_waiwai]

どこにどう返ってくる値なんでしょうか。
言ってることが意味不明です

[退会済みユーザー]

初学者なのでわかりにくくなってしまい申し訳ありません。解答になっているのかわかりませんが、例えば ./a.out abc　としたとき abc と返ってきてほしいのですが、このコードでは cba となって返ってきてしまいます。

[y_waiwai]

えーと、提示されてるコードはコンパイルできませんし、実行することはできません。
本当にこのコードだけで実行ファイルを作ってるんでしょうか？

[退会済みユーザー]

このコードは一部です。

[y_waiwai]

なら全部提示しましょうよ

[退会済みユーザー]

修正しました。

[kazuma-s]

修正するのなら、ソースコードの前後に ```C と ``` を付けてください。
行が全部左詰めになっているのを何とも思わないのですか？

[退会済みユーザー]

使い方がよくわかっていませんでした。すいません。

[kazuma-s]

質問のコードを改変してはいけません。逆順に表示される元のコードがないと、質問の趣旨が伝わりません。コードを修正したかったら追記してください。そうでないと、後からこの質問と回答を見た人が何のことか理解できません。元に戻してください。

Answer 1

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

struct node {
	char element;
	struct node *next;
};

void insert(struct node *p, char x)
{
	struct node *n = (struct node *)malloc(sizeof(struct node));
	if (n == NULL) abort();

	n->element = x;
	n->next = p->next;
	p->next = n;
}

void append(struct node *p, char x)
{
	if (p->next == NULL) {
		insert(p, x);
		return;
	}
	append(p->next, x);
}

int main(void)
{
	struct node *str = (struct node *)malloc(sizeof(struct node));
	if (str == NULL) abort();
	str->element = 'a';
	str->next = NULL;

	append(str, 'b');
	append(str, 'c');
	struct node *p = str;
	while (p != NULL) {
		printf("%c", p->element);
		p = p->next;
	}
	printf("\n");
	return 0;
}

【解説】

insertの実装自体は問題ありません(あえていえばmalloc失敗時のエラー処理が抜けているぐらい)。しかし、この関数は名前の通り「pの次に文字を挿入する」というものです。"a"に対して'b'を'a'の次に文字を挿入したら"ab"、"ab"に対して'c'を'a'の次に文字を挿入したら"acb"です。文字の先頭だけを指定しても最後に挿入されることはありません。

では、どうすれば良いのかというと、一番単純なのは最後の文字を探して、それに対してinsertよびだしすればいいと言うことです。一番最後の文字かどうかはp->nextがNULLかどうかで確認できます。もし、NULLであれば、最後なのでinsertを呼び出します。NULLでなかったら、pをp->nextにして再度確認すれば良いとなります。NULLになるまで確認はwhileでループを回しても良いですし、上のコードのように再帰関数にしてもいいでしょう(末尾再帰であるため適切に最適化されていればスタックオーバーフローはおきません)。

なお、最後の文字を探すのはO(n)の計算量が必要であり、文字列が長くなればなるほど遅くなります。O(1)で処理させたい場合は双方向循環連結リストにするなどの工夫が必要でしょう。

Answer 2

リストのある要素の前に追加する insert ではなく、
リストのある要素の後に追加する append を用意して、それを使えばよいのでは？

#include <stdio.h>
#include <stdlib.h>
struct node{
    char element;
    struct node *next;
};

struct node *initlist() {
    struct node *n;

    n = (struct node*)malloc(sizeof(struct node));
    n->next = NULL;
    return n;
}

struct node *append(struct node *p, char x) {       // ★
    struct node *n;     // ★
    n = (struct node*)malloc(sizeof(struct node));  // ★
    n->element = x;     // ★
    n->next = p->next;  // ★
    p->next = n;        // ★
    return n;           // ★
}

void printlist(struct node *p) {
    if(p->next == NULL) {
        putchar('\n');
    }else {
        p = p->next;
        putchar(p->element);
        printlist(p);
        // putchar(p->element);  // ★ 削除
    }
}

int main(int argc, char *argv[]) {
    struct node *list, *head, *tail;  // ★ tail を追加
    char *p;
    if (argc<2)
        exit(-1);

    tail = list = initlist();     // ★ tail を追加
    for (p = argv[1]; *p; p++)    // ★
        tail = append(tail, *p);  // ★ tail に追加。tail を更新

    printlist(list);
    // printf("\n");  // ★ 削除
    for (; list; ) {
        head = list;
        list = list->next;
        free(head);
    }
    return 0;
}

追記

void insert(struct node *p, char x) {
	while (p->next != NULL) p = p->next; // ★ 追加: 最後を見つける

    struct node *n;
    n = (struct node*)malloc(sizeof(struct node));
    n->element = x;
    n->next = p->next;
    p->next = n;
}

void printlist(struct node *p) {
    if(p->next == NULL) {
        putchar('\n');
    }else {
        p = p->next;
        putchar(p->element);
        printlist(p);
        // putchar(p->element);  // ★ 削除
    }
}

Comments

[退会済みユーザー]

解答ありがとうございます。ですが、あくまでもinsert内を変更して書きたいのですが、appendでなくても書けるのでしょうか?

[退会済みユーザー]

納得できました。お手数おかけしました。ありがとうございます。