在C中添加和排序链表

Question

在我的作业中，我必须编写一个函数，该函数将指向"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("Whilen"); // 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;

Answer 1

在循环中

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

检查未初始化的CCD_ 1是否是（不是）CCD_。如果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 ??

但是，您将返回哪个指针？如果新项是列表中的第一个，则返回指向第一个节点的指针。如果您还想这样做，如果以后插入新项目，则需要保留原始ptr->next0（的副本）并返回。

Answer 2

while循环条件错误。您从未设置ptr->next，但您使用它来检查ptr->next!=NULL，这意味着headPtr=headPtr->next在循环中变为野生状态。因此，一旦设置了值，就应该设置：ptr->next=NULL。

你也可以把这些线拿出来放在顶部：

   ptr->value = newItem;
   ptr->next = headPtr;

试试这个：

LNode*  AddItem(LNode  *headPtr, int  newItem)
{
    auto    LNode   *ptr, *temp, *orghead;
    orghead = headPtr;
    int fl=0;
    ptr = malloc(sizeof(LNode));
    ptr->value = newItem;
    ptr->next = NULL;
    temp = ptr;
    if (headPtr == NULL)
        return ptr;
    else
        {
        while(headPtr != NULL && headPtr->value < newItem)
            {
            printf("Whilen");
            fl =1;
            temp = headPtr;
            headPtr = headPtr->next;
            }
        temp->next = ptr;
        ptr->next = headPtr;
        if(fl) return orghead;
        else return temp;
        }
}  // end of "AddItem"

Answer 3

while循环一直进行到链表的末尾，最后一个元素为null。因此，在while条件下，您正在取消引用一个空节点（headPtr），这样会导致分段错误。我认为你需要检查你的节点是否为空，如下所示：

while (headPtr != NULL && (headPtr->value > newItem || ptr->next != NULL))

Answer 4

从以上所有来看都是真的

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

您没有在While 内检查headPtr的空条件

此时

headPtr = headPtr->next;

headPtr->next可以为空，这会使您的程序崩溃

多一点

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;
    }

考虑到headPtr不是NULL，ptr现在指向某个malloc堆ptr->在这种情况下，下一个可能是也可能不是NULL

while (headPtr->value > newItem || ptr->next != NULL)

将是不可预测的

你可能需要多看一点你的逻辑

如果你喜欢，请参阅下面的伪逻辑

LNode* add_time(LNode *headptr , data){
    LNode   *ptr =  headptr, *temp;        
    temp = malloc(sizeof(LNode));
    if(!temp) 
      return ptr;
    temp->next = NULL;
    temp->value= data;
    if(ptr == NULL){ 
        /** There is no list**/
        ptr = temp;
        return ptr;
     }
    /* go to last node*/
    while(ptr->next)
        ptr = ptr->next;
    ptr->next = temp;
    return ptr;
}