在链表的开头插入新节点 [英] Insert new node at the beginning of Linked-List

问题描述

在第C一个简单的链表实现，我无法想出一个行中指定插入功能的（）。
这需要一个char，并加入到按字母顺序排列的链表。
该生产线是如何创建一个新的节点时，列表是空的。而且，由于会出现在名单上只有一个节点，该行应该像我的评论，我错了？

  / ********* *************** /无效插入（ListNodePtr *特征码，char值）{
ListNodePtr NEWPTR;
ListNodePtr previousPtr;
ListNodePtr currentPtr;NEWPTR =的malloc（sizeof的（ListNode））;如果（NEWPTR！= NULL）{//可用空间
    newPtr-＆GT;数据=值; //在节点上的价值
    newPtr-＆GT; nextPtr = NULL; //节点不会链接到另一个节点    previousPtr = NULL;
    currentPtr = *特征码; //间接的方式startPtr    而（currentPtr = NULL＆放大器;！＆安培;价值＆GT; currentPtr-＆GT;数据）{
        previousPtr = currentPtr; //步行至 ...
        currentPtr = currentPtr-＆GT; nextPtr; // ...下一个节点
    }    //在列表的开头插入新节点
    如果（previousPtr == NULL）{
        newPtr-＆GT; nextPtr = *特征码; /////////////////////////////////////////////// newPtr-＆GT ; nextPtr = NULL？
        *特征码= NEWPTR;
    }
    其他{//插入previousPtr和currentPtr之间的新节点
        previousPtr-＆GT; nextPtr = NEWPTR;
        newPtr-＆GT; nextPtr = currentPtr;
    }}
其他
    的printf（％C没有插入存储可用\\ n。，值）;
} //插入结束/ ******************* ****** /
 

在主）typedef的指令（有;

  typedef结构listNode ListNode;
的typedef ListNode * ListNodePtr;
 

和功能插件（）被调用在main（）这样的;

 插入（安培; startPtr，项目）;
 

startPointer在main（）的初始化;

  ListNodePtr startPtr = NULL;
 

解决方案

我想你忘记了一个案例。你标志着该生产线将被调用，如果

• 列表为空


• 的字符不是列表中的所有其他字符较小，并已在列表
的开头插入

要了解第二种情况，看看在code面前：

 而（currentPtr = NULL＆放大器;！＆安培;价值＆GT; currentPtr-＆GT;数据）{
    previousPtr = currentPtr; //步行至 ...
    currentPtr = currentPtr-＆GT; nextPtr; // ...下一个节点
}
 

状况价值＆GT; currentPtr-＆GT;数据是在第二种情况下真实的，所以你会在与 previousPtr == NULL 和<$线到达C $ C> *特征码！= NULL （包含其初始值，指针到列表中的第一个节点）。

在第一种情况下， *特征码是 NULL 事实上，在第二种情况下，你会错误地扔掉使用 NULL 键，只有一个列表中的字符和内存泄漏结束时，整个列表。

In a simple Linked List implementation on C, I couldn’t figure out a line of function named insert(). It takes a char and add to the linked list in alphabetical order. The line is about creating a new node when the list is empty. And since there will be only one node on the list, the line should be like I’ve commented, am I wrong?

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

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

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

the typedef instructions in main() are;

typedef struct listNode ListNode;
typedef ListNode* ListNodePtr;

and the function insert() is called in main() like this;

insert( &startPtr, item);

initialization of startPointer in main();

ListNodePtr startPtr = NULL;

解决方案

I think you forgot a case. The line you marked will be called if

• the list is empty
• the character is smaller than all other characters in the list and has to be inserted at the beginning of the list

To understand the second case, have a look at the code before:

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

The condition value > currentPtr->data is true in the second case, so you will arrive at the line with previousPtr == NULL and *sPtr != NULL (containing its initial value, the pointer to the first node of the list).

In the first case, *sPtr is NULL indeed, in the second case, you would incorrectly throw away the whole list when using NULL and end up with only one character in the list and a memory leak.

这篇关于在链表的开头插入新节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！