在链表中插入新节点

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; 

和函数insert（）在main（）中是这样调用的;

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 
} 

条件value > currentPtr->data是在第二种情况下真实的，所以你会在与线到达previousPtr == NULL和*sPtr != NULL（包含其初始值，指向列表的第一个节点的指针）。

在第一种情况下，*sPtr是NULL确实，在第二种情况下，你会错误地扔掉整个列表使用NULL当且仅一个列表中的字符和内存泄漏而告终。

Answer 2

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

你的建议：

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

但如果*特征码= Node1和名单是：

Node1->Node2->Node3 

，如果你想节点1之前插入并使用您的实现

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

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