按升序将值插入已排序的链表

Question

这个函数会要求用户输入一个整数，然后按升序插入到链表中。如果当前值已经存在，则不会插入。

typedef struct _listnode{
    int item;
    struct _listnode *next;
} ListNode;         

typedef struct _linkedlist{
    int size;
    ListNode *head;
} LinkedList;           

void insertSortedLinkedList(LinkedList *l)
{
    ListNode *cur = l->head;
    ListNode* newNode = malloc(sizeof(ListNode)); // create the node to be inserted
    int x;
    printf("please input an integer you want to add to the linked list:");
    scanf("%d", &x);
    newNode->item = x;
    newNode->next = NULL;

    if (l->head == NULL) // linkedlist is empty, inserting as first element
    {
        l->head = malloc(sizeof(ListNode));
        l->head->item = x;
        l->head->next = NULL;
        l->size++;
    }
    else
    {

        if (x < l->head->item) // data is smaller than first element, we will insert at first element and update head.
        {
            newNode->next = l->head;
            l->head = newNode;
            l->size++;
            return;
        }
        while (cur->next != NULL) // loop through the linkedlist
        {
            if (cur->next->item > x) // next element is bigger than data, we will insert it now.
            {
                if (cur->item != x) // if current element is not same as data, it must not have already existed.
                {
                    newNode->next = cur->next;
                    cur->next = newNode;
                    l->size++;
                    return;
                }
            }
            if (cur->next == NULL) // we have reached the last element and data is even greater than that. we will then insert it as last element.
            {
                cur->next = newNode;
                l->size++;
                return;
            }
            cur = cur->next;
        }
    }
}

不知何故，其中有一个错误。当我尝试插入以下内容时，我得到了这些结果。如果数据大于现有数据，它也不会插入。

Insert : 10
Result : 10
Insert : 5
Result : 5 10
Insert : 8
Result : 5 8 10
Insert : 10
Result : 5 8 10
Insert : 7
Result : 5 7 8 10
Insert : 9
Result : 5 7 8 9 10
Insert : 6 
Result : 5 6 7 8 9 10
Insert : 5
Result : 5 6 5 7 8 9 10 << why?

Answer 1

问题是您永远无法达到 if 条件，因为当 cur->next == NULL 您的循环中断时：

while (cur->next != NULL) // loop through the linkedlist
    ....
        if (cur->next == NULL) // we have reached the last element and data is even greater than that. we will then insert it as last element.
        {
           ...
        }
    ...
    }

相反，您应该使用 while(cur != NULL) 作为循环，并将 cur->next == NULL 设置为第一个 if 条件，这样 (cur->next->item 就不会在 [=15= 时使您的程序崩溃].

注意：在这种情况下，您的循环条件并不重要，因为 if (cur->next == NULL) 中的 return 将打破循环。唯一重要的是在执行 if-条件之前不要退出循环。

Answer 2

您在错误的地方测试相等性：您总是跳过第一个节点。您还需要改进分配方案：您为头节点分配了两次内存，如果整数已经在列表中，则忘记释放内存。

这是一个改进版本：

void insertSortedLinkedList(LinkedList *l)
{
    ListNode *cur, *newNode;
    int x;

    printf("please input an integer you want to add to the linked list:");
    if (scanf("%d", &x) != 1)
        return;

    newNode = malloc(sizeof(ListNode)); // create the node to be inserted
    newNode->item = x;
    newNode->next = NULL;

    if (l->head == NULL)
    {
        // linkedlist is empty, inserting as first element
        l->head = newNode;
        l->size++;
        return;
    }
    if (x < l->head->item)
    {
        // data is smaller than first element, we will insert at first element and update head.
        newNode->next = l->head;
        l->head = newNode;
        l->size++;
        return;
    }
    for (cur = l->head;; cur = cur->next) // loop through the linkedlist
    {
        if (cur->item == x)
        {
            // element already in the list
            free(newNode);
            return;
        }
        if (!cur->next || cur->next->item > x)
        {
            // next element is bigger than data or end of list, we will insert it now.
            newNode->next = cur->next;
            cur->next = newNode;
            l->size++;
            return;
        }
    }
}

可以使用指向 link:

的指针来缩短此代码

void insertSortedLinkedList(LinkedList *l)
{
    ListNode **curp, *cur, *newNode;
    int x;

    printf("please input an integer you want to add to the linked list:");
    if (scanf("%d", &x) != 1)
        return;

    for (curp = &l->head; (cur = *curp) != NULL; curp = &cur->next) {
        if (cur->item == x)
            return;
        if (cur->item > x)
            break;
    }
    // cur element is bigger than data or end of list, we will insert it now.
    newNode = malloc(sizeof(ListNode)); // create the node to be inserted
    newNode->item = x;
    newNode->next = cur;
    *curp = newNode;
    l->size++;
}

按升序将值插入已排序的链表

Insert value into sorted linked list in ascending order

c

linked-list