通过双向链接进行冒泡排序

Question

我正在使用 C 第 4 版中的 Kochans 编程学习 C。我在使用指针，我的练习是编写前一章中排序函数的指针版本。这是冒泡排序。我从一个更好的编码器那里获取了一些代码来创建一个双向链表（设置所有数字，就像在以前的问题中所做的那样似乎很乏味）。

在这种情况下，我正在交换价值。接下来，我将交换整个节点，但我无法让这个更简单的节点工作。我在排序函数之外测试了该算法，它起作用了，只是它没有完成工作。所以我在游戏中引入了一些 bool 变量，但它在到达第一个 "true" 结果时退出了循环，所以我创建了一个函数来测试列表是否排序。它进入了一个无限循环，但我不明白为什么。还有其他像我这样的问题，但都是针对C++，而不是C。

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

struct Node  {
    int data;
    struct Node* next;
    struct Node* prev;
};

struct Node* head; 

struct Node* GetNewNode(int x) {
    struct Node* newNode
        = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

void InsertAtHead(int x) {
    struct Node* newNode = GetNewNode(x);
    if(head == NULL) {
        head = newNode;
        return;
    }
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
}

void InsertatEnd(int x)
{
struct Node* temp = head;

struct Node* newNode = GetNewNode(x);
    if(head == NULL){
        head = newNode;
        return;
    }
    while(temp->next != NULL)
    temp = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
}

void Print() {
    struct Node* temp = head;
    printf("Forward: ");
    while(temp != NULL) {
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");
}

bool testSort(void)
{
    struct Node* temp = head;

    bool test = false;

    while(temp->next != NULL)
   {
       if (temp->data > temp->next->data){
            return false;
            }
    temp = temp->next;
    }
    return true;
}

void sortList(void)
{
   struct Node* temp = head;
   int temp2;
    bool sorted = false;

   while(sorted == false){
    while(temp->next != NULL)
   {
       if (temp->data > temp->next->data){
            temp2 = temp->next->data;
            temp->next->data = temp->data;
            temp->data = temp2;
            }
            temp = temp->next;
   }
        sorted = testSort();
}
}


int main(void)
{
    head = NULL;
    int x;
    int array[16] = {34, -5, 5, 0, 12, 100, 56, 22, 44, -3, -9, 12, 17, 22, 6, 11};
    int count;

    struct Node* temp;

    for(count = 0; count < 16; ++count)
            InsertatEnd(array[count]);

    sortList();
    Print();

    return 0;
}

提前致谢。

Answer 1

幸好我想通了。我不需要额外的功能来测试列表。我的问题是，已经设置为 head 的 temp 没有重新初始化以从头开始评估列表。为了确定这一点，我添加了一个 printf 语句来显示 temp->data 和 temp->next->data 的值，并意识到该算法只是驱动了几个数字，所以它并没有完全排序。修改后的代码如下。关键是循环中的 temp = head 语句从头开始重新初始化。

void sortList(void)
{
   struct Node* temp = head;
   int temp2;
    bool sorted = false;

   while(sorted == false){
    sorted = true;
    temp = head;
    while(temp->next != NULL)
   {
       if (temp->data > temp->next->data){

            temp2 = temp->next->data;
            temp->next->data = temp->data;
            temp->data = temp2;
            sorted = false;
            }
            temp = temp->next;
   }
}
}

通过双向链接进行冒泡排序

Bubble Sort through a doubly linkrd

c

bubble-sort

doubly-linked-list