Как поменять местами узлы связанного списка в алгоритме сортировки пузырьков? - PullRequest
Новая
       39

Как поменять местами узлы связанного списка в алгоритме сортировки пузырьков?

2 голосов
/ 21 апреля 2020

В C Я должен написать функцию пузырьковой сортировки, которая меняет местами узлы, а не значения в LinkedList, но я не могу выполнить sh. Вот код (Как вы видите, порядок не правильный): 

#include <stdio.h>
#include <malloc.h> // malloc, free
#include <stddef.h> // NULL

// defining 'int' as data_t
typedef int data_t;

typedef struct node_s {
    data_t data;
    struct node_s* next;
} node_t;

node_t** list_new() {
    node_t** list = malloc(sizeof **list);
    if (!list) return NULL;
    *list = NULL;
    return list;
}

void list_delete(node_t** list) {
    node_t *node, *next;
    for (node = *list; node; node = next) {
        next = node->next;
        free(node);
    }
}

node_t* list_push_front(node_t** list, data_t data) {
    node_t* node = malloc(sizeof(node_t));
    if (!node) return NULL;
    node->data = data;
    node->next = *list;
    return *list = node;
}

// IS EASY TO SWAP THE VALUES
/*
void swap(data_t* a, data_t* b) {
    data_t c = *a;
    *a = *b;
    *b = c;
}

void simple_bubble_sort(node_t** list) {
    for(node_t* i = *list; i; i = i->next)
        for(node_t* j = *list; j->next; j = j->next)
            if(j->data > j->next->data)
                swap(&(j->data), &(j->next->data));

}
*/
// MUCH LESS EASY TO SWAP THE NODES
void swap_node(node_t** prev_node_A, node_t** node_A, node_t** node_B) {
        node_t *last_node = (*node_B)->next;
        node_t *first_node = *node_A;
        node_t *second_node = *node_B;
        if (prev_node_A) {
            (*prev_node_A)->next = second_node;
            (*prev_node_A)->next->next = first_node;
            (*prev_node_A)->next->next->next = last_node;
        } else {
            (*node_A) = second_node;
            (*node_A)->next = first_node;
            (*node_A)->next->next = last_node;
        }
}

void simple_bubble_sort(node_t** list) {

    for(node_t* i = *list; i->next; i = i->next)
        for (node_t *j = *list; j->next->next; j = j->next) {
            if (j == *list) {
                if (j->data > j->next->data) {
                    *list = j->next;
                    swap_node(NULL, &j, &(j->next));
                }
            }
            else {
                if (j->next->data > j->next->next->data)
                    swap_node(&j, &(j->next), &(j->next->next));
            }
            //printf("%i,%i | %i, %i, %i, %i \n", i->data, j->data, (*list)->data, (*list)->next->data, (*list)->next->next->data, (*list)->next->next->next->data);
            //system("pause");
        }
}


int main() {
    // Create List
    node_t** list = list_new();
    if (!list)
        goto memory_allocation_failure;

    // Add values to List
    for(int i=0; i<10; i++)
        if (!list_push_front(list, i))
            goto memory_allocation_failure;

    // Print List
    for (node_t* node = *list; node != NULL; node = node->next)
        printf("%i\n", node->data);

    // Swap Test
    //swap_node(NULL, &(*list), &((*list)->next));
    //swap_node(&(*list), &((*list)->next), &((*list)->next->next));

    // Sort List
    printf("-- Bubble Sort --\n");
    simple_bubble_sort(list);

    // Print List
    for (node_t* node = *list; node != NULL; node = node->next)
        printf("%i\n", node->data);

    // Delete List
    list_delete(list);
    return 0;

    // Error Handler
    memory_allocation_failure:
        printf("Memory Allocation Failure");
        return 1;
}

1 Ответ

1 голос
/ 21 апреля 2020

Вот функция swap. 

 void swap( node_t **current )  
 {  
     node_t *tmp = ( *current )->next->next;  

     ( *current )->next->next = *current;  


     *current = ( *current )->next;  

     ( *current )->next->next = tmp;  
 }

А вот функция simple_bubble_sort

 void simple_bubble_sort( node_t **head )  
 {  
     if ( *head )  
     {  
         for ( node_t **first = head, *sorted = NULL, *last = sorted;  
               ( *first )->next != last;  
               last = sorted )  
         {  
             sorted = ( *first )->next; 
             for ( node_t **current = first; ( *current )->next != last; current = &( *current )->next )  
             {  
                 if ( ( *current )->next->data < ( *current )->data )  
                 {  
                     swap( current );  

                     sorted = ( *current )->next;  
                 }  
             }  
         }  
     }  
 }

Исследуйте их.

Обратите внимание на это заголовок <malloc.h> не является стандартным заголовком C. Вместо этого используйте заголовок <stdlib.h>.

Вам необходимо пересмотреть текущий код. Например, эта функция 

node_t** list_new() {
    node_t** list = malloc(sizeof **list);
    if (!list) return NULL;
    *list = NULL;
    return list;
}

не имеет смысла, ее следует удалить.

Вам нужно просто определить в main указатель, например 

node_t *head = NULL;

And передать его функциям, например, функции simple_bubble_sort, например 

simple_bubble_sort( &head );

, или функцию list_push_front следует определить как 

int list_push_front(node_t** list, data_t data) 
{
    node_t* node = malloc(sizeof(node_t));
    int success = node != NULL;

    if ( success )
    {
        node->data = data;
        node->next = *list;
        *list = node;
    }

    return success;;
}
...