Вставить новый узел в начале Linked-List - PullRequest
Новая
       0

Вставить новый узел в начале Linked-List

3 голосов
/ 07 марта 2011

В простой реализации Linked List на 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

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

инструкции typedef в main (): 

typedef struct listNode ListNode;
typedef ListNode* ListNodePtr;

и функция insert () вызывается в main () следующим образом; 

insert( &startPtr, item);

инициализация startPointer в main (); 

ListNodePtr startPtr = NULL;

Ответы [ 2 ]

3 голосов
/ 07 марта 2011

Я думаю, что вы забыли дело.Помеченная вами строка будет вызываться, если

  • список пуст
  • символ меньше всех других символов в списке и должен быть вставлен в начало списка

Чтобы понять второй случай, взгляните на код, приведенный выше: 

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 и в итоге получили бы только один символ в списке и утечку памяти.

1 голос
/ 07 марта 2011

Вы передаете * sPtr функции.Если * sPtr указывает на узел в непустом списке, вы потеряете ссылку на список, если будете использовать NULL вместо * sPtr.Если * sPtr равен NULL, то поведение такое же.

Вы предлагаете: 

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

, но если * sPtr = Node1 и список: 

Node1->Node2->Node3

если вы хотите вставить перед Node1 и использовать вашу реализацию

, вы сделаете свой newPtr-> point равным NULL, а затем установите свой * sPtr = newPtr и потеряете свой первоначальный список

другой реализациидобавляет новый узел к старому списку.

...