Проблемы со связанными списками и указателями (C)

Question

Я пишу программу C для сортировки связанного списка в соответствии с наибольшими значениями. Я встретил проблему, когда программа просто зависала, когда программа достигла «prevPtr-> next = headPtr». Я хочу, чтобы prevPtr-> next приравнивался к headPtr, если сумма prevPtr больше суммы headPtr, однако программа просто висит там.

Функция compareNodes() используется для сравнения узлов, чтобы узнать, имеет ли newNode то же имя, что и любые другие структуры в связанном списке, а затем добавит сумму.

sortSimilarNodes() используется для сортировки узлов в соответствии с суммой каждой структуры.

структура здесь ниже:

struct purchase { 
     char name[30]; 
     double sum; 

     struct purchase * next; 
    } ; 

     LOG * compareNodes(LOG * headPtr, char * name, char * price){ 
     . 
     . 
     . 
      while (curPtr != NULL) { 
        if (strcmp(newNode->name, curPtr->name)==0) { 
         curPtr->sum += newNode->sum; 
         free(newNode); 
         similar = 1; 

         break; 

        } 
        //advance to next target 
        prevPtr = curPtr; 
        curPtr = curPtr->next; 
       } 
       /*if (curPtr == NULL){ 
        if(strcmp(newNode->name, prevPtr->name)==0){ 
         prevPtr->sum += newNode->sum; 
         free(newNode); 
         similar = 1; 
        } 
       }*/ 

       if (similar == 1){ 
        headPtr = sortSimilarNodes(curPtr, headPtr); 

       } 
       else{ 
        headPtr = sortNodes(newNode, headPtr); 
       } 

       return headPtr; 
    } 

    LOG * sortSimilarNodes(LOG * newPtr, LOG * headPtr){ 
     LOG * curPtr; 
     LOG * prevPtr; 

     if(headPtr->sum < newPtr->sum){ 

      newPtr->next = headPtr; 
      return newPtr; 
     } 

     prevPtr = headPtr; 
     curPtr = headPtr->next; 
     while (curPtr == NULL){ 

     } 
     while (curPtr != NULL){ 

      if(strcmp(curPtr->name, newPtr->name)==0){ 
       break; 
      } 
      prevPtr = curPtr; 
      curPtr = curPtr->next; 
     } 
     return headPtr; 

    } 

This is the output of the program. Спасибо!

Answer 1

Трудно сказать по вашему коду, потому что вы его не разместили, но у вас, похоже, есть неправильные представления о связанных списках. В частности:

• Нет необходимости в новых узлах, если вы не добавите новые узлы в список. Это также означает, что вы не вызываете malloc, за исключением добавления узлов. (Там нет в вашем коде нет malloc, но в вашей функции сравнения подозрительную free Сравнение не предполагает создание или уничтожение ничего,.. Это просто означает, что посмотреть, что уже есть)

• Следствием первой точкой является то, что в пустом списке не должно быть узлов, даже фиктивных узлов. Пустым списком является список, head - NULL. Убедитесь, что вы инициализируете все указатели головы перед созданием нового списка:

  LOG *head = NULL;  // empty list 
  

• При сортировке списка, порядок списка изменился и старый глава является недействительным. Вы обслуживаете, что, возвращая новую голову:

  head = sort(head); 
  

  Но это кажется излишним, и это также, кажется, подразумевает, что два указателя могут быть разными. Это не так, потому что старый указатель укажет немного в отсортированном списке, не обязательно во главе. Это, вероятно, лучше передать адрес головной указатель для того, чтобы избежать путаницы:

  sort(&head); 
  

Сортировка связанных списков может быть сложно. Одним из простых способов является сортировка выбора: найдите узел с наивысшим значением, удалите его из исходного списка и добавьте его в начало нового списка. Повторяйте, пока в исходном списке больше узлов.

Добавление нового узла n в передней части списка, приведенного на head легко:

n->next = head; 
head= n; 

Добавление нового узла в конце списка, который задается head немного сложнее:

LOG **p = &head; 

while (*p) p = &(*p)->next; 
*p = n; 
n->next = NULL; 

Здесь p является адресом указателя, который указывает на текущий узел, *p. После прохождения списка этот адрес является либо адресом узла head (когда список пуст), либо адресом указателя next узла-предшественника.

Вы могли бы достичь нечто подобное, сохраняя prev указатель, но решение указатель на указатель означает, что вы не должны рассматривать случаи, когда нет предыдущего узла, специально за счет некоторых дополнительных & и * операторы.

При том, что ваша сортировка рутина становится:

void sortByName(LOG **head) 
{ 
    LOG *sorted = NULL; 

    while (*head) { 
     LOG **p = head;  // auxiliary pointer to walk the list 
     LOG **max = head; // pointer to current maximum 
     LOG *n;    // maximum node 

     while (*p) { 
      if (strcmp((*p)->name, (*max)->name) > 0) max = p; 
      p = &(*p)->next; 
     } 

     n = *max; 
     *max = (*max)->next; 

     n->next = sorted; 
     sorted = n; 
    } 

    *head = sorted; 
} 

Если вы хотите отсортировать по сумме, изменить сравнение с:

  if ((*p)->sum > (*max)->sum) max = p; 

Вызвать функцию:

LOG *head = NULL; 

insert(&head, "apple", 2.3); 
insert(&head, "pear", 1.7); 
insert(&head, "strawberry", 2.2); 
insert(&head, "orange", 3.2); 
insert(&head, "plum", 2.1); 

sortByName(&head); 
print(head); 
destroy(&head); 

с insert, destroy и print развлечения ctions для полноты:

void insert(LOG **head, const char *name, double sum) 
{ 
    LOG *n = malloc(sizeof(*n)); 

    if (n) { 
     snprintf(n->name, sizeof(n->name), "%s", name); 
     n->sum = sum; 

     n->next = *head; 
     *head = n; 
    }  
} 

void destroy(LOG **head) 
{ 
    LOG *n = *head; 

    while (n) { 
     LOG *p = n; 

     n = n->next; 
     free(p); 
    } 

    *head = NULL; 
} 

void print(LOG *l) 
{ 
    while (l) { 
     printf("%s: %g\n", l->name, l->sum); 
     l = l->next; 
    } 

    puts(""); 
}