Bubble Сортировать по двойным ссылкам - PullRequest
Новая
       47

Bubble Сортировать по двойным ссылкам

0 голосов
/ 10 апреля 2020

учусь C с программированием Кочана в C 4-е издание. Я нахожусь на указатели, и моя задача состоит в том, чтобы написать версию указателя функции сортировки из предыдущей главы. Это пузырьковая сортировка. Я написал немного кода от лучшего кодера для создания двусвязного списка (установка всех чисел, как это было в предыдущих задачах, показалась довольно утомительной).

В этом роде я меняю значение. Далее я поменяю местами все узлы, хотя я не могу заставить работать этот более простой. Я проверил алгоритм вне функции сортировки, и он работал, за исключением того, что он не завершил работу. Поэтому я добавил в игру некоторые переменные bool, но после достижения первого «истинного» результата он вышел из l oop, поэтому я создал функцию для проверки, отсортирован ли список или нет. Входит в бесконечное l oop, но я не понимаю почему. Есть и другие вопросы, как у меня, но все для 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;
}

Заранее спасибо.

1 Ответ

0 голосов
/ 12 апреля 2020

Welp Я смог понять это. Мне не нужна была дополнительная функция для проверки списка. Моя проблема заключалась в том, что temp, который был назначен на первое место, не инициализировал заново список для оценки списка с самого начала. Чтобы определить это, я добавил оператор printf для отображения значений temp-> data и temp-> next-> data и понял, что алгоритм обрабатывает только некоторые из чисел, поэтому он не является исчерпывающей сортировкой. Пересмотренный код ниже. Ключом была инструкция temp = head внутри l oop для повторной инициализации с самого начала. 

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;
   }
}
}
...