c - 在 C 中添加和排序链表

在我的作业中，我必须编写一个函数，该函数将指向“LNode”结构的指针和整数参数作为参数。然后，我不仅要将该整数添加到链表中，还要放置它，以便列表按正确的升序排列。我已经尝试了几种不同的尝试，这是我发布时的代码。

LNode*  AddItem(LNode  *headPtr, int  newItem)
{
    auto    LNode   *ptr = headPtr;

    ptr = malloc(sizeof(LNode));

    if (headPtr == NULL)
    {
        ptr->value = newItem;
        ptr->next = headPtr;
        return ptr;
    }
    else
    {

        while (headPtr->value > newItem || ptr->next != NULL)
        {
            printf("While\n"); // This is simply to let me know how many times the loop runs
            headPtr = headPtr->next;
        }
        ptr->value = newItem;
        ptr->next = headPtr;
        return ptr;
    }

}  // end of "AddItem"

当我运行它并尝试插入 5 然后插入 3 时，5 被插入，但是 while 循环运行一次，我得到一个段错误。

此外，我无法更改参数，因为它是该项目骨架代码的一部分。感谢任何能提供帮助的人。

如果它有帮助，这就是结构的样子

typedef struct  LNode
{
    int                 value;
    struct  LNode      *next;

} LNode;

最佳答案

在你的循环中

while (headPtr->value > newItem || ptr->next != NULL)
    {
    printf("While\n"); // This is simply to let me know how many times the loop runs
    headPtr = headPtr->next;

您检查未初始化的 ptr->next 是否是(不是) NULL 。这是不明智的，如果 ptr 的那部分中的位模式可能不是 NULL 指针的位模式，则可能会造成严重破坏，因为您在条件中有一个 ||，那么循环条件始终为真，并且您跑完了列表。
|| 无论如何都是错误的，你需要一个 && ，两个条件都必须成立，有些东西不是 NULL 并且值之间的关系必须成立。

并且，由于您希望列表按升序排列，因此您必须在列表中的值小于要插入的值时遍历列表。

但是您必须在指向的值变得与新值一样大或大于新值之前停止，因为您必须修改节点的 next 指针，然后才能插入新值。

if (headPtr->value >= newItem) {
    ptr->value = newItem;
    ptr->next = headPtr;
    return ptr;
}
while(headPtr->next != NULL && headPtr->next->value < newItem) {
    headPtr = headPtr->next;
}
// Now headPtr is the node behind which the new item is to be inserted
ptr->value = newItem;
ptr->next = headPtr->next;
headPtr->next = ptr;
return ??

但是你会返回什么指针呢？如果新 Item 是列表中的第一个，则返回指向第一个节点的指针。如果您还想在稍后插入新项目时这样做，则需要保留(副本)原始 headPtr 并返回该代码。

关于c - 在 C 中添加和排序链表，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10050336/