气泡通过双向链接排序

Question

使用C第四版的Kochans编程学习C。我使用的是指针，我的练习是编写上一章中排序函数的指针版本。这是一种泡沫排序。我从一个更好的编码器中获取了一些代码来创建一个双向链接列表（像以前的问题一样设置所有数字似乎很繁琐）。

在这种情况下，我正在交换值。接下来，我将交换整个节点，尽管即时通讯无法使这个更简单的节点正常工作。我在sort函数之外测试了该算法，但该算法无法完成工作，但可以正常工作。因此，我将一些布尔变量引入了游戏，但是当达到第一个“ 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

很高兴我能弄清楚。我不需要额外的功能来测试列表。我的问题是，已设置为临时的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;
   }
}
}