Bubble sort со связанным списком C

Question

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

#include "string.h"
#include "stdlib.h"
#include "stdio.h"

typedef struct s_file {
    char    *name;
    struct s_file     *next;
    struct s_file     *previous;
} t_file;

void swap_files(t_file *file, t_file *next)
{
    t_file *previous;

    previous = file->previous;
    if (previous)
        previous->next = next;
    file->next = next->next;
    file->previous = next;
    if (next->next)
        next->next->previous = file;
    next->next = file;
    next->previous = previous;
}

static t_file *sort_files(t_file *files)
{
    t_file *file;
    t_file *next;

    file = files;
    while ((next = file->next))
    {
        if (strcmp(file->name, next->name) > 0)
        {
            swap_files(file, next);
            if (!next->previous)
                files = next;
            file = files;
            continue;
        }
        file = file->next;
    }
    return (files);
}

void debug(t_file *files)
{
    while (files)
    {
        printf("=> %s\n", files->name);
        files = files->next;
    }
}

int main(void)
{
    t_file second;
    t_file first;
    t_file third;

    first.name = "Poire";
    first.previous = NULL;
    first.next = &second;

    second.name = "Banane";
    second.previous = &first;
    second.next = &third;

    third.name = "Fraise";
    third.previous = &second;
    third.next = NULL;

    first = *(sort_files(&first));
    debug(&first);
    return (0);
}

Answer 1

swap_files слишком сложно. Вполне достаточно просто поменять местами данные:

void swap_files(t_file *file, t_file *next)
{
    char *tmp = file->name;
    file->name = next->name;
    next->name = tmp;
}

И угадайте что? Это решило проблему.

В комментариях ниже было упомянуто два вопроса с этим решением, и я хотел бы их решить. Во-первых, этот код может быть менее эффективным, если имеется много полей данных, а во-вторых, есть вероятность, что вы забудете поле.

1. Маловероятно, что это будет узким местом, и, если это так, займитесь этим тогда, а не раньше. И когда есть только одно поле, этот код гораздо эффективнее. Утверждение против определенного метода, потому что было бы медленнее, если бы обстоятельства были другими, не является хорошим аргументом.

2. Забыть поле - веский аргумент против этого. У меня нет возражений там.

Решение обоих вышеперечисленных вопросов заключается в создании второй структуры данных, например:

struct data {
    char * name;
    int age;
    char * address;
    /* More fields */
}

struct s_file {
    struct data *data;
    struct s_file *next;
    struct s_file *previous;
}

Вы можете спорить за или против этого. В некотором смысле это не «похоже на C», но, с другой стороны, вы получаете хорошее разделение обязанностей.

Answer 2

Вы должны определенно не перезаписать first новым головным узлом списка, потому что при этом список будет поврежден. Просто определите указатель для его удержания:

    t_file *head = sort_files(&first);
    debug(head);

Также не используйте " для стандартных заголовочных файлов:

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

Наконец, даже с этими исправлениями ваш алгоритм сортировки пузырьков кажется неправильным: когда вы меняете узлы на file и next, вы должны вернуться к предыдущему узлу на тот случай, если узел next был меньше, чем предыдущий узел тоже.

Вот исправленная версия:

static t_file *sort_files(t_file *head) {
    t_file *file;
    t_file *next;

    file = head;
    while ((next = file->next) != NULL) {
        if (strcmp(file->name, next->name) > 0) {
            swap_files(file, next);    // swap the nodes linkage
            file = next;               // next is now before file
            if (file->previous) {
                file = file->previous; // backtrack to the previous node
            } else {
                head = file;           // save the new head of list
            }
        } else {
            file = file->next;
        }
    }
    return head;
}