Понимание сортированного списка

Question

У меня возникли проблемы с пониманием упорядоченный связанный список в С.

У меня есть следующий код:

void create(ListNode **pStart, int input) 
{ 

    ListNode *pNew; 
    ListNode *pPrevious; 
    ListNode *pCurrent; 

    pNew = malloc(sizeof(ListNode)); 

    if (pNew != NULL) 
    { 

     pNew->data = input; 
     pNew->pNext = NULL; 

     pPrevious = NULL; 
     pCurrent = *pStart; 

     while (pCurrent != NULL && input > pCurrent->data) 
     { 
      pPrevious = pCurrent; 
      pCurrent = pCurrent->pNext; 
     } 

     if (pPrevious == NULL) 
     { 
      pNew->pNext = *pStart; 
      *pStart = pNew; 
     } 
     else 
     { 
      pPrevious->pNext = pNew; 
      pNew->pNext = pCurrent; 
     } 
    } 
    else 
    { 
     printf("%c not inserted. No memory available.\n", input); 
    } 
    } 

У меня проблемы только понять ту часть, где он говорит pCurrent = *pStart; Как ISN Технически это первый головной узел? Что представляет собой pCurrent = *pStart?

Answer 1

Вы должны различать 3 случая в то время, когда create называется:

• Список пуст значение
• input меньше или равен наименьшему существующему элементу -> он становится новым списка значение
• input больше, чем наименьший существующий элемент -> он вставляется в позиции, далее в списке

Чтобы найти позицию для вставки, код начинается с начала списка *pStart и продолжается до тех пор, пока не будет найдено положение вставки.

pNew представляет элемент, который вы хотите вставить, он не имеет никакого отношения к поиску положения вставки.

Answer 2

Ваш pNew не является первым головным узлом, на самом деле это последний головной узел, и если у вас есть только один узел после головы, это первый и последний головной узел.

С pCurrent = *pStart;, адреса памяти в переменнуюуказатель *pStart присваивается pCurrent, теперь так *pStart выглядит как голова вашего связанного списка, так pCurrent также указывает на голову связанного списка после pCurrent = *pStart; строка кода выполняется.

Answer 3

pNew добавлен в определенное место, поэтому список остается отсортированным. pCurrent - это узел, следующий за pNew, поэтому мы начинаем его с самого начала и ищем нужное место в цикле while.