c - 如何创建代码以按排序方式将整数插入链表？

Question

这是我作业的一部分。我必须将一个数字放入链接列表中。它必须是有序的，并且不能允许重复。

我尝试了以下代码，但总是出现段错误。

int insertSortedLL(LinkedList *ll, int item)
{
    ListNode *current;
    int index=0;
    int res;

    if (ll == NULL || ll->head->item >= item) 
    {
        res=insertNode(ll,0,item);
        return 0;
    } 
    else
    { 
        /* Locate the node before the point of insertion */
        current = ll->head; 
        while (current->next!=NULL)
        { 
            if(current->next->item==item){
                return -1;
            }
            else if(current->next->item < item){
                current = current->next;
                index++;
            }
            else{
                break;
            }
        } 
        res=insertNode(ll,index,item);
        return index;
    } 
}

我期望它返回一个值，该值是它存储的数字的索引，但它从未起作用。另外，int insertNode 是一个预制函数，用于在所选索引中插入数字，ListNode 用于定义节点。

Answer 1

您的代码中有几处错误。

1. 即使作为参数传递的链表为 NULL，您仍然会调用 insertNode(ll,0,item)。如果链表为 NULL，则 100% 的情况下都会导致段错误。

    if (ll == NULL || ll->head->item >= item) 
    {
        res=insertNode(ll,0,item);
        return 0;
    } 

逻辑有点奇怪。似乎您不希望列表中的项目重复，因为我从这个 if 语句 (if(current->next->item==item)) 中推断出来，但您不检查此条件适用于列表的第一项。

使用函数 insertNode 会降低代码的效率。 insertNode 将需要再次循环遍历列表以将新项目放在正确的位置。

编辑:这是一个肮脏的修复(与其他版本相比)，以便不允许列表中出现重复项。

ListNode* make_node(int item){
    ListNode * new = malloc(sizeof(ListNode));
    new->item = item;
    new->next = NULL;
    return new;
}

int insertSortedLL(LinkedList *ll, int item){
    ListNode *current;
    ListNode *new;
    ListNode *tmp;
    int index=0;

    if(ll == NULL)
        return -1;

    //If the list is empty
    if(ll->head == NULL){
        ll->head = make_node(item);
    }

    if(ll->head->item == item)
        return -1;

    if(ll->head->item > item){
        new = make_node(item);
        new->next = ll->head;
        ll->head = new;
        return 0;
    }

    /* General case */
    current = ll->head; 
    while (current != NULL){
        if(current->next == NULL){
            current->next = make_node(item);
            return index;
        }else if (current->next->item == item){
            return -1;
        }else if (current->next->item < item){
            current = current->next;
            index++;
        }else{
            new = make_node(item);
            tmp = current->next;
            new->next = tmp;
            current->next = new;
            return index;
        }
    }
    return -1;
}

编辑:这是允许重复的版本。

#include <stdlib.h>

int insertSortedLL(LinkedList *ll, int item){
    ListNode *current;
    ListNode *new;
    ListNode *tmp;
    int index=0;

    if(ll == NULL)
        return -1;

    new = malloc(sizeof(ListNode));
    new->item = item;
    new->next = NULL;

    //If the list is empty or the first item of ll is greater
    if(ll->head == NULL || ll->head->item >= item){
        new->next = ll->head;
        ll->head = new;
        return 0;
    }

    /* General case */
    current = ll->head; 
    while (current != NULL){
        if(current->next == NULL){
            current->next = new;
            return index;
        }else if (current->next->item < item){
            current = current->next;
            index++;
        }else{
            tmp = current->next;
            new->next = tmp;
            current->next = new;
            return index;
        }
    }
    return -1;
}

valgrind 是一个有用的工具，用于查找哪段代码生成段错误消息(并且可以执行更多操作，例如查找内存泄漏等)。

使用-g -Wall -Wextra编译代码，不要忽略编译器警告消息(即使它们看起来无害)，并使用valgrind运行程序。