C中的通用鏈接列表排序功能

Question

我想排序一個鏈接的節點列表。我遍歷列表中的每個節點，將它與當前頭進行比較，如果它「較大」，則交換。最後我再次用head->next。 我想讓函數返回新排序函數的「頭部」。

第一個問題是它似乎卡在第一個for循環中。

我哪裏出錯了？

struct Node{ 
    char firstName[50]; 
    char lastName[50]; 
    int age; 
    struct Node *next; 
}; 

struct Node * sortList(struct Node * head, 
    int(*cmp)(struct Node *, struct Node *)){ 
    printf("Entered Sorting Function\n"); 
    struct Node * target; 
    struct Node * p; 
    struct Node * first; 
    bool firstRun = TRUE; 
    target=head; 
    first=head; 
    for (p=head; p!=NULL; p=p->next) { 
     if ((*cmp)(p, target) == 1) 
      printf("Comparing %s with %s\n", p->firstName, target->firstName); 
      target = p; 
    } 
    if (head!=target) { 
     printf("swapping nodes"); 
     swapNodes(head, target); 
    } 
    if (firstRun==TRUE) { 
     first = head; 
     printf("setting very first to: %s\n", first->firstName); 
     firstRun = FALSE; 
    } 
    if (target->next != NULL) { 
     printf("recurring with %s\n", target->next->firstName); 
     sortList(target->next, cmp); 
    } 
    return first; 
} 

更新：

在第一循環的問題是缺少周圍的語句括號中if，如nemetroid在此answer指出 - 感謝，nemetroid。代碼應爲：

for (p=head; p!=NULL; p=p->next) { 
     if ((*cmp)(p, target) == 1) { 
      printf("Comparing %s with %s\n", p->firstName, target->firstName); 
      target = p; 
     } 
    } 

但是，排序仍然不起作用。還有什麼錯誤？

我發現我的swap不起作用，正如人們提到的。這是包含交換的更新代碼。

更新：我修復了交換，現在我只交換節點的內容。

void swapNodes(struct Node * nodeA, struct Node * nodeB) { 
    struct Node * tmp = malloc(sizeof(struct Node)); 
    strcpy(tmp->firstName, nodeA->firstName); 
    strcpy(tmp->lastName, nodeA->lastName); 
    tmp->age = nodeA->age; 

    strcpy(nodeA->firstName, nodeB->firstName); 
    strcpy(nodeA->lastName, nodeB->lastName); 
    nodeA->age = nodeB->age; 

    strcpy(nodeB->firstName, tmp->firstName); 
    strcpy(nodeB->firstName, tmp->firstName); 
    nodeB->age = tmp->age; 
} 

但排序是仍然沒有工作，這裏是我的排序當前代碼：

void sortList(struct Node * head, 
    int(*cmp)(struct Node *, struct Node *)){ 
     if (head==NULL || head->next==NULL) 
      return; 
     int length = listLength(head); 
     int i, j; 
     struct Node * p = head; 
     struct Node * q = p; 
     bool firstRun = TRUE; 
     for (i=0; i<length; i++) { 
      if (firstRun != TRUE) 
       p=p->next; 
      else if (firstRun == TRUE) 
       firstRun = FALSE; 
      for (j=i+1; j<length-1; j++) { 
       q = q->next; 
       if ((*cmp)(q, p) == 1) 
        swapNodes(p, q); 
      } 
     } 

} 

我固定它。在答案中發佈排序代碼。感謝大家的幫助。

Answer 1

這是我使用的代碼，它似乎工作到目前爲止。 注意：我們通過交換其內容來交換2個節點，而不處理它們指向下一個的元素。

void sortList(struct Node * head, 
    int(*cmp)(struct Node *, struct Node *)){ 
     if (head==NULL || head->next==NULL) 
      return; 
     int length = listLength(head); 
     int i, j; 
     struct Node * p = head; 
     struct Node * q = p; 
     struct Node * target = head; 
     bool firstRun = TRUE; 
     for (i=0; i<length; i++) { 
      q=p; 
      if (firstRun != TRUE) 
       p=p->next; 
      else if (firstRun == TRUE) 
       firstRun = FALSE; 
      target = p; 
      while (q->next != NULL) { 
       q = q->next; 
       if ((*cmp)(q, target) < 0) 
        target = q; 
      } 
      if (p!=target) 
       swapNodes(p, target); 
     } 
} 

Answer 2

由於if語句缺少大括號，因此只有printf("Comparing...是有條件的，因此您在for循環的每次迭代中都執行target = p。這可能不是你打算做的。

此外，你可能想要做first = target而不是head。儘管整個模塊都是可疑的，但它會在每個遞歸步驟中運行。