鏈接列表函數？

Question

所以我寫這個函數，使最小的節點在鏈表的末尾。到目前爲止，它的工作除了最後一個元素。如果鏈表被創建爲包含0〜9項的節點，則該函數之後的列表爲{1,2,3,4,5,6,7,8,0,9}，零不成爲結束。

任何想法爲什麼？

我的功能;

int connecting(linkk A) 
{ 
    linkk L = A; 
    for (int i = 0; i<sizeof(L);i++) 
    { 
     if (L->item < L->next->item) 
     { 
      int a = L->item; 
      L->item = L->next->item; 
      L->next->item = a; 
      L = L->next; 
     } 
     else{L=L->next;} 
    } 
    return 0; 
} 

Answer 1

讓我們先從什麼，我認爲你應該做的是不同的：

1. 你的函數的名稱爲connecting。鑑於你想要的功能的描述，這是而不是一個很好的名字。
2. 我可以從使用中推斷出linkk是一個typedef指針。在大多數情況下，隱藏指針並不是一個好主意。
3. 你的函數返回一個int。它總是0。爲什麼？這沒有任何意義。
4. 因爲linkk可能是一個指向節點的指針，並且您將頭指針按值（即它的副本）傳遞給該函數，所以無法處理列表頭部最小的情況。返回「新」頭指針，或將指針傳遞給頭指針以便能夠修改頭指針。
5. 您已經暗示您使用sizeof是完全錯誤的。 sizeof(L)會給你指針的大小（在char s），因此可能是8位在64位系統或4位在32位系統上。
6. 您並未更改節點，而是移動節點之間的值。如果它是你想要做的，這是可以的，但是你的算法的描述表明你想要移動節點。
7. 您的功能太多了，IMO。這可能很難分開，但更好的方法是分開查找/提取最小值並將其放在列表的末尾。
8. 您的修改比您原來想要的要多得多。考慮一個列表，如1, 2, 3, 0, 4。使用您的算法，該列表將更改爲2, 3, 1, 4, 0。這樣做不僅對性能不利，而且對於呼叫者來說也是非常令人驚訝的。當談到編程時，驚喜並不好！

所以，讓我們的希望良好的實施，分步實施：

struct node { 
    int item; 
    struct node * next; 
}; 

我假設你要移動的節點包含的最低值到列表的末尾，如您描述。爲了保持與原始代碼更接近，我也將這個函數保存爲一個函數，接收struct node * head指針，儘管我的觀點如上所述。讓我們先來看一下特殊/基本情況：移動空列表的最小元素以及單個元素列表是微不足道的：不做任何事情。

if (head == NULL || head->next == NULL) { 
    return head; 
} 

我返回列表的「新」頭允許調用者更新它自己的頭指針。（正如已經說過的，head只是調用者頭指針的副本，修改它在調用站點不會有任何影響）。

因爲我們在這裏處理單向鏈表，並且實現不應該在列表中不必要地迭代，所以我們應該記住我們以前訪問過的節點。否則，我們不能輕易從列表中提取一個節點：直接

struct node * follow, * point; 

follow遵循point後面。

最初，我們將該點放在列表的第二個節點（我們已經檢查了列表中至少有2個節點）。因此follow將指向頭：

point = head->next; 
follow = head; 

因爲我們想找到最低的項目，我們需要保持最小的已經搜索列表的一部分的軌道。我們用頭節點的值初始化它：

int currentMinimum = head->item; 

現在我們準備遍歷列表，以便找到包含最小值的節點。但是我們不僅需要找到包含最小值的節點，還需要找到它之前的節點和之後的節點，以便能夠輕鬆地提取它。所以，3個指針：

struct node * predecessor，* minimum，* successor;

我們設置currentMinimum到head小號的項目，我們也應該相應地設置指針：

predecessor = NULL; // Nothing preceding the head 
minimum = head; 
successor = head->next; 

現在讓我們重複，完全動點在列表中，直到它在最後脫落：

while (point != NULL) { 
    // to be continued 
    follow = point; 
    point = point->next; 
} 
// when we're here, follow will point to the last node 

在每次迭代中，我們需要檢查，如果發現比目前的最低較小的值，並最終記住的節點包含它：

if (point->item < currentMinimum) { 
    predecessor = follow; 
    minimum = point; 
    successor = point->next; 
    currentMinimum = point->item; 
} 

現在，當我們走出循環，下面的狀態應該達到：

• minimum指向包含最小的節點。
• follow指向列表的最後一個節點。
• 上面兩個可能是相同的，這是一個特例！
• predecessor仍然可能是NULL，這是另一種特殊情況！

首先考慮minimum = follow的特殊情況：在這種情況下，最小值已經在列表的末尾，所以贏利！否則，我們需要minimum「開刀」的節點淘汰之列，並追加到最後一個節點，指向follow：

if (follow != minimum) { 
    if (predecessor != NULL) { 
    predecessor->next = successor; // Cut out 
    minimum->next = NULL; // will be the last node 
    follow->next = minimum; // append at end 
    } else { 
    // to be continued 
    } 
} 

正如你所看到的，還有要考慮第二個特殊情況：如果predecessor仍然是NULL，那麼沒有項目小於head s項目。（因此，我們也可以測試minimum == head）因此，列表的第一個節點將移動到最後。我們需要通知來電者！

head = head->next; // Second node is now the first one, though this is not all we need to do, see further down! 
minimum->next = NULL; // Will be the last node 
follow->next = minimum; // Append at end 

由於分配給head不僅改變了功能參數（這是與該功能被稱爲指針的拷貝），我們需要返回（可能修改！）頭指針，給發話更新了自己的頭指針的能力：

return head; 

來電者將因此使用此功能，像這樣：

struct node * head = get_a_fancy_list(); 
head = move_minimum_to_end(head); // This is our function being called! 

最後，要考慮的：爲y你可以看到，移動節點（而不是項目）更復雜。我們需要修改至少2個指針才能實現我們想要的。相反：移動項目值需要對項目值進行兩次修改（並且迭代更容易）。因此，當指針分配比項目分配快時，移動節點而不是項目。由於項目是int這是而不是這裏的情況。

移動項目而不是包含項目的節點相當容易。首先，我們需要跟蹤最小的（價值以及節點）：

要迭代，我們再次將使用兩個指針。它可以用一個一個來完成，但代碼將是更具可讀性這樣：

struct node * point, * follow; 

我們開始用相同的初始狀態：

minimum = head; 
currentMinimum = head->item; 
follow = head; 
point = head->next; 

迭代類似於其他實施，是迭代步驟：

while (point != NULL) { 
    if (point->item < currentMinimum) { 
    minimum = point; 
    currentMinimum = point->item; 
    } 
    follow = point; 
    point = point->next; 
} 
// follow points to the last node now 

現在，做一樣的以前的實現，我們可以交換的最後一個節點的項目和最小的節點：

minimum->item = follow->item; 
follow->item = currentMinimum; // contains minimum->item 

有在檢查follow != minimum像以前的做法是沒有意義的：你可以這樣做，但交換節點的項目有自己的項目不會做任何傷害。 OTOH添加if將增加一個分支，因此可能會導致性能損失。

由於我們沒有更改列表結構（節點之間的鏈接），因此沒有更多需要考慮的事項。我們甚至不需要告訴來電者一個新的頭像，因爲它永遠不會有任何改變。出於風格的目的，我會添加它：

return head; 

好吧，這有點長，但希望它很容易理解！

Answer 2

試試這個功能

int connecting(linkk A) 
{ 
linkk L = A; 
    while(L->next!=NULL) 
    { 
    if (L->item < L->next->item) 
    { 
     int a = L->item; 
     L->item = L->next->item; 
     L->next->item = a; 

    } 

    L=L->next; 
    } 
    return 0; 
}