c - 如何将新节点插入空列表？

Question

我试图理解 Deitels 第 5 版 c 书中的这段代码。

如果我要在链表中插入一个新节点，为什么要设置 nextPtr = *sPtr。第一个节点不应该有一个 NULL 的 nextPtr 吗？

另外，*sPtr = newPtr 是什么意思？

struct listNode {
   char data;
   struct listNode *nextPtr;
 };


void insert(ListNodePtr *sPtr, char value)
{

ListNodePtr newPtr; /* pointer to a new node */
ListNodePtr previousPtr;  /* pointer to a previous a node in list */
ListNodePtr currentPtr;  /* pointer to current node in list */

newPtr = malloc(sizeof(ListNode));  /* create node */

if (newPtr != NULL){ /* is space available */
    newPtr->data = value;
    newPtr->nextPtr = NULL;

    previousPtr = NULL;
    currentPtr = *sPtr;

    while (currentPtr != NULL && value > currentPtr->data){
        previousPtr = currentPtr;
        currentPtr = currentPtr->nextPtr;
    }

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

}
}

Answer 1

第一个节点不应该将它的 nextPtr 设置为 NULL，那将是最后一个节点(毕竟你需要能够从第一个到第二个节点)。第一个节点的nextPtr 指向第二个节点，第二个节点有指向第三个节点的指针，依此类推。因此，当您在列表的开头插入时，您让新节点的 nextPtr 指向列表的旧开头，即 *sPtr。之后，通过执行 *sPtr=newPtr 将指向列表开头的指针设置为指向新节点。