用双指针插入已排序的链表

Question

我试图用以下代码在C中创建一个排序的链表，但在打印任何输入之前，我都得到了分段错误。我相信这是因为我在while循环中检查了((*link)->value < val)，但在开始时，它是NULL。我还尝试添加一个条件，如果在列表中没有元素，但没有工作。如果没有seg，我如何检查要添加的值是否更小?错吗?

struct NodeTag {
    int value;
    struct NodeTag *next;
};
typedef struct NodeTag Node;
typedef struct {
    Node *head;
    int length;
} List;
void insertSorted(List *list, int val) {
    Node **link = &(list->head);
    while (*link != NULL || (*link)->value < val) {
        //move node to correct place in list
        link = &((*link)->next);
    }
    //create new node
    Node *n = (Node *)malloc(sizeof(Node));
    n->value = val;
    //set next to null
    n->next = NULL;
    //insert new node
    *link = n;
}

printList:

void printList(List *list) {
    printf("%d elements :", list->length);
    for (Node *n = list->head; n; n = n->next)
        printf( " %d", n->value);
    printf( "n" );
}

输入:72 19 47 31 8 36 12 88 15 75 51 29

期望输出:8 12 15 19 29 31 36 47 51 72 75 88

Answer 1

你的代码中有一些问题:

• 您使用||代替&&。如果next成员是NULL，则您在列表的末尾，请在此处插入

• 参数名称为list，但在正文中使用link

• 你不需要在C中强制转换malloc()的返回值，它被认为是适得其反的，特别是如果你忘记包括<stdlib.h>。

• 你不测试分配失败

• 不将列表的其余部分链接到插入的节点。

• 函数应该返回一个指向插入节点的指针，给调用者一个检查内存分配失败的机会。

以下是更正后的版本:

#include <stdlib.h>
Node *insertSorted(List *list, int val) {
    Node **link = &list->head;
    while (*link != NULL && (*link)->value < val) {
        //skip this node
        link = &(*link)->next;
    }
    //create new node
    Node *n = malloc(sizeof(Node));
    if (n != NULL) {
        n->value = val;
        n->next = *link; // link the rest of the list
        *link = n;   //insert new node
    }
    return n;
}