為鏈表實作冒泡排序的C代碼不起作用-有解無憂

我正在嘗試在鏈接串列上應用冒泡排序。為此，我已經實作了自己的串列，但是代碼不起作用，因為當列印所有鏈接串列值時，它以某種方式沒有列印任何值。

我正在撰寫代碼的課程要求我從頭開始撰寫所有內容。我寫了一個不能正常作業的冒泡排序函式，它以某種方式緩和了根，因此我無法列印鏈接串列的所有值。

我還嘗試列印字串“交換的值”以了解回圈運行了多少次，結果證明它正在運行它應該運行的次數。但是由于我無法從根目錄列印值而做了一些事情。

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdbool.h>

typedef struct Node
{
    int value;
    struct Node *next;
} Node;

Node *insert(Node *root, int val)
{
    Node *new = (Node *)malloc(sizeof(Node));
    new->value = val;
    new->next = NULL;
    if (root == NULL)
    {
        root = new;
        return root;
    }
    while (root->next != NULL)
    {
        root = root->next;
    }
    root->next = new;
    return NULL;
}

void swap(Node *n1, Node *n2)
{
    int temp = n1->value;
    n1->value = n2->value;
    n2->value = temp;
}

void print(Node *root)
{
    if (root == NULL)
        return;
    printf("%d ", root->value);
    print(root->next);
}

void bubbleSort(Node *root)
{
    bool toSwap = true;
    Node *trav = root;
    while (toSwap)
    {
        toSwap = false;
        while (trav != NULL)
        {
            if (trav->value > trav->next->value)
            {
                swap(trav, trav->next);
                printf("Values Swapped \n");
                toSwap = true;
            }

            trav = trav->next;
        }
    }
}

int main(void)
{
    Node *root = NULL;
    root = insert(root, 4);
    insert(root, 1);
    insert(root, 5);
    insert(root, 3);
    bubbleSort(root);
    print(root);
    return 0;
}

uj5u.com熱心網友回復：

您的代碼會及時運行O(n)，因為trav每次迭代都會向前移動，并且演算法會在 trav 到達串列末尾時終止。但是，冒泡排序是一種O(n^2)時間演算法。

您需要使用兩個指標。我們稱之為第二個指標trav_2。第一個指標 ( trav) 只是充當一個計數器，以確保第二個指標 ( trav_2) 遍歷串列執行必要的交換n時間。如果您用以下邏輯替換您的 while 回圈，它應該可以正常作業：

while (trav!=NULL)
{
    toSwap = false;
    Node *trav_2 = root;
    while (trav_2 != NULL && trav_2->next!=NULL)
    {
        if (trav_2->value > trav_2->next->value)
        {
            swap(trav_2, trav_2->next);
            printf("Values Swapped \n");
            toSwap = true;
        }

        trav_2 = trav_2->next;
    }
    trav = trav->next;
}

我還修復了您在代碼中遇到的一些指標取消參考錯誤（其他人提到的錯誤）。然而，修復它們是不夠的。邏輯也有問題。

uj5u.com熱心網友回復：

Harsh 已經修復了現有代碼。我將向您展示這是如何通過純指標雜耍而不是在節點之間交換資料來完成的。通常這就是本練習的目的。想象一下，每個節點中都有一個巨大的資料有效負載，這使得復制變得很突兀。如果您只是推擠指標以重新排列串列，則不必這樣做。

對于每個列舉，“最大”元素都會冒泡到最后。它從那里被修剪并推到新串列的頂部。當演算法完成時，將發生以下兩件事之一：

我們用完了節點。或者
由于 noswap 優化，我們提前退出了。

其中第一個是微不足道的。我們已經擁有所有節點并且它們已經排序。后者使事情變得復雜，因為我們仍然有兩個排序串列：一個是我們在推送構建排序結果時已經修剪的專案串列，另一個是我們檢測為已經排序并退出排序的剩余串列環形。幸運的是，由于我們跟蹤剩余源串列中最后一個節點指標的方式，它使鏈接它們變得容易，我們將得到最終結果。

最后，因為root可以改變，演算法要求從函式回傳新的根。反過來，這需要改變main. 這并不特定于上述演算法。無論如何，它都必須作為一個單獨但重要的錯誤修復來完成。

排序實作如下所示：

Node *bubbleSort(Node *root)
{
    Node *result = NULL;
    Node **pp;
    
    bool swapped = (root != NULL);
    while (swapped)
    {
        // reset swap state
        swapped = false;

        pp = &root;
        while (*pp && (*pp)->next)
        {
            // compare the two node values
            if ((*pp)->next->value < (*pp)->value)
            {
                Node *p = *pp;
                *pp = (*pp)->next;
                p->next = (*pp)->next;
                (*pp)->next = p;
                swapped = true;
            } 
            pp = &(*pp)->next;
        }

        // pp holds the address of the pointer pointing to 
        //  the last node in the source list. So, we...
        //  1. prune off the end node.
        //  2. terminate the source list
        //  3. push the pruned node on to the front of
        //     the result list where it belongs.
        Node *p = *pp;
        *pp = NULL;

        p->next = result;
        result = p;

        // TODO: fun thing here. print both lists (result and root)
    }

    // the above loop could have exited early, leaving root
    //  holding the sorted low half of the list. the *last*
    //  pointer in that list is addressed by pp, so we can 
    //  just link the rest of the list we already pruned to
    //  that end and we're done.
    *pp = result;
    return root;
}

變化main同樣如下：

int main(void)
{
    Node *root = insert(root, 4);
    insert(root, 1);
    insert(root, 5);
    insert(root, 3);

    root = bubbleSort(root);
    print(root);
    return 0;
}

最后，結果：

1 3 4 5

值得注意的是：冒泡排序已經夠可怕了。它非常適合幾乎所有的排序目的，尤其是對于鏈表，理想的排序機制是歸并排序。但是出于學術目的，它是一個有趣的練習，特別是如果你接受完全通過指標推擠來完成它的挑戰；不是基準交換。

一個有趣的觀點

修改代碼以執行以下操作：

生成序列 1...30 的隨機洗牌
如上所示進行排序，但在每次迭代后列印源串列和結果串列。

結果顯示了修剪、推送和最終修復是如何發生的。原始的洗牌串列是：

11 28 16 6 12 23 13 1 20 14 27 3 2 7 21 4 8 30 19 15 22 17 26 29 24 9

列印每個串列（剩余的源串列和我們正在構建的結果），結果如下所示：

root:   11 16 6 12 23 13 1 20 14 27 3 2 7 21 4 8 28 19 15 22 17 26 29 24 9 5 18 25 10 
result: 30 
root:   11 6 12 16 13 1 20 14 23 3 2 7 21 4 8 27 19 15 22 17 26 28 24 9 5 18 25 10 
result: 29 30 
root:   6 11 12 13 1 16 14 20 3 2 7 21 4 8 23 19 15 22 17 26 27 24 9 5 18 25 10 
result: 28 29 30 
root:   6 11 12 1 13 14 16 3 2 7 20 4 8 21 19 15 22 17 23 26 24 9 5 18 25 10 
result: 27 28 29 30 
root:   6 11 1 12 13 14 3 2 7 16 4 8 20 19 15 21 17 22 23 24 9 5 18 25 10 
result: 26 27 28 29 30 
root:   6 1 11 12 13 3 2 7 14 4 8 16 19 15 20 17 21 22 23 9 5 18 24 10 
result: 25 26 27 28 29 30 
root:   1 6 11 12 3 2 7 13 4 8 14 16 15 19 17 20 21 22 9 5 18 23 10 
result: 24 25 26 27 28 29 30 
root:   1 6 11 3 2 7 12 4 8 13 14 15 16 17 19 20 21 9 5 18 22 10 
result: 23 24 25 26 27 28 29 30 
root:   1 6 3 2 7 11 4 8 12 13 14 15 16 17 19 20 9 5 18 21 10 
result: 22 23 24 25 26 27 28 29 30 
root:   1 3 2 6 7 4 8 11 12 13 14 15 16 17 19 9 5 18 20 10 
result: 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 6 4 7 8 11 12 13 14 15 16 17 9 5 18 19 10 
result: 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 12 13 14 15 16 9 5 17 18 10 
result: 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 12 13 14 15 9 5 16 17 10 
result: 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 12 13 14 9 5 15 16 10 
result: 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 12 13 9 5 14 15 10 
result: 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 12 9 5 13 14 10 
result: 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 11 9 5 12 13 10 
result: 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 9 5 11 12 10 
result: 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 8 5 9 11 10 
result: 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 7 5 8 9 10 
result: 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 6 5 7 8 9 
result: 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 5 6 7 8 
result: 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
root:   1 2 3 4 5 6 7 
result: 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

最終結果如預期：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

uj5u.com熱心網友回復：

將您的內部 while 回圈更改為：

    while (trav != NULL && trav->next != NULL) {
      if (trav->value > trav->next->value) {
        printf("Swapping values %d %d\n", trav->value, trav->next->value);
        swap(trav, trav->next);        
        toSwap = true;
      }
    
      trav = trav->next;
    }

它更正了 NULL 指標取消參考。
您將通過清楚地顯示正在交換的內容來了解??它為什么不起作用。

話雖如此，您更應該做第二條評論中提到的事情。

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/425190.html

標籤：C 指针链表冒泡排序

上一篇：有沒有辦法將結構作為C中的指標來尊重？

下一篇：當物件是指標時多載==和!==