在链表的开头插入新节点

Question

在 C 上的简单链表实现中，我无法找出一行名为 insert() 的函数。 它需要一个字符并按字母顺序添加到链接列表中。 该行是关于当列表为空时创建一个新节点。由于列表上只有一个节点，因此该行应该像我评论的那样，我错了吗？

/****************************************************/

void insert( ListNodePtr *sPtr, char value ){
ListNodePtr newPtr;    
ListNodePtr previousPtr;
ListNodePtr currentPtr;

newPtr = malloc( sizeof( ListNode) );

if( newPtr != NULL ){       //is space available
    newPtr->data = value;       //place value in node
    newPtr->nextPtr = NULL;      //node does not link to another node

    previousPtr = NULL;
    currentPtr = *sPtr;         //indirection to startPtr

    while( currentPtr != NULL && value > currentPtr->data ){
        previousPtr = currentPtr;               //walk to ...
        currentPtr = currentPtr->nextPtr;       //... next node
    }

    //insert new node at the beginning of the list
    if( previousPtr == NULL ){
        newPtr->nextPtr = *sPtr;            ///////////////////////////////////////////////  newPtr->nextPtr = NULL   ???
        *sPtr = newPtr;
    }
    else{           //insert new node between previousPtr and currentPtr
        previousPtr->nextPtr = newPtr;
        newPtr->nextPtr = currentPtr;
    }

}
else
    printf( "%c not inserted. No memory available.\n", value);
}//end-of insert

/*******************************************************/

main() 中的 typedef 指令是；

typedef struct listNode ListNode;
typedef ListNode* ListNodePtr;

在 main() 中调用函数 insert() ，如下所示；

insert( &startPtr, item);

main()中startPointer的初始化；

ListNodePtr startPtr = NULL;

Answer 1

我想你忘记了一个案例。 则将调用您标记的行，

• 如果列表为空，
• 该字符比列表中的所有其他字符都小，并且必须插入到列表的开头

要了解第二种情况，请看一下之前的代码

while( currentPtr != NULL && value > currentPtr->data ){
    previousPtr = currentPtr;               //walk to ...
    currentPtr = currentPtr->nextPtr;       //... next node
}

： <代码>值> currentPtr->data 在第二种情况下为 true，因此您将到达带有 previousPtr == NULL 和 *sPtr != NULL 的行（包含它的初始值，指向列表第一个节点的指针）。

在第一种情况下，*sPtr确实是NULL，在第二种情况下，当使用NULL并结束时，您会错误地丢弃整个列表列表中只有一个字符并且存在内存泄漏。

Answer 2

您正在将 *sPtr 传递给该函数。如果 *sPtr 指向非空列表中的节点，并且使用 NULL 而不是 *sPtr，您将丢失对该列表的引用。如果 *sPtr 为 NULL，则行为相同。

您建议：

if( previousPtr == NULL ){
        newPtr->nextPtr = NULL;
        *sPtr = newPtr;
    }

但如果 *sPtr = Node1 并且列表是：

Node1->Node2->Node3

如果您想在 Node1 之前插入并且使用您的实现，

您将使 newPtr->指向NULL
然后设置 *sPtr = newPtr 并丢失原始列表，

其他实现将新节点添加到旧列表中。