使用鏈表進行插入排序

-1

（1）您將只實現插入排序，（2）您將使用鏈表來存儲長整數，而不是使用數組進行存儲。因此，您的排序必須在鏈接列表上執行。使用鏈表進行插入排序

我的代碼如下。

Node *Insertion_Sort(Node *sublist) { 
//Initialize`enter code here` 
Node *dummy_node = malloc(sizeof(Node)); 
dummy_node->next = NULL; 

Node *prev_node = sublist; 
Node *curr_node = sublist->next; 

Node *head = prev_node; 

Node *temp_node = malloc(sizeof(Node)); 
while(curr_node->next != NULL){ 
    if (prev_node->value < curr_node->value) { 
     //advance the pointers 
     prev_node = curr_node; 
     if (curr_node != NULL) { 
      curr_node = curr_node->next; 
      printf("Advancing prev=%ld curr=%ld\n", prev_node->value, curr_node->value); 
     } 
     else 
     { 
      break; 
     } 
    } 
    else 
    { 
     //swap 
     temp_node = curr_node; 
     prev_node->next = curr_node->next; 
     curr_node->next = prev_node; 
     // Advance 
     prev_node = curr_node; 
     curr_node = curr_node->next; 
     head = prev_node; 
    } 
} 
//curr_node->next = NULL; 

return head; 
}

但它只是部分工作。有誰能夠幫助我？

來源

2014-02-28 user3295123

定義「它只是部分工作」。 – dornhege

就像@dornhege說的那樣，你當前的輸出是什麼？你認爲問題領域是什麼？一些額外的信息使得回答您的問題變得更容易。 –

你在這個排序例程中分配*任何*是值得懷疑的。你使用'malloc（）'在C++程序中執行它是非常有問題的。我沒有記得插入任何東西 - 除了交換以外，要求對臨時存儲進行排序，並且由於您使用的是鏈接列表，因此您應該交換的唯一東西是指針值，而不是節點。 – WhozCraig

您不應該爲節點分配任何空間。 Wiki鏈接爲Insertion sort。你可能應該使用第二僞代碼示例（其中一部分我進行排序之前，而你通過刪除和插入節點插入排序部分）：

for i ← 1 to length(A) 
    x ← A[i] 
    j ← i 
    while j > 0 and A[j-1] > x 
     A[j] ← A[j-1] 
     j ← j - 1 
    A[j] ← x

更換內部while循環只需掃描A [i]需要插入的位置。注意，如果A [i]大於所有排序列表，那麼內部循環不會迭代，j == i，並且A [i]不需要移動（所以只需繼續外部循環）。

來源

2014-02-28 21:19:54 rcgldr

使用鏈表進行插入排序

回答

相關問題