C - 使用双指针插入排序链表

Question

我正在尝试使用以下代码在 C 中创建一个排序链表，但在打印任何输入之前我遇到了段错误。我相信这是因为我正在检查 ((*link)->value < val)在我的 while 循环中，但在开始时，它是 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;
}

这是打印列表:

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在体内

• 您不需要转换 malloc() 的返回值在 C 中，它被认为适得其反，特别是如果您忘记包含 <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;
}