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

Question

Ух ты, теперь я знаю, что не знаю. Лол.

У меня есть такая структура:

struct Medico{ 
int Id_Doctor;
int Estado;
char Nombre[60]; ////focus on this part of the structure, this is name.
char Clave_Acceso[20];
char Especialidad[40];
struct Medico *next;
};

И я хочу организовать структуру в зависимости от названия (в алфавитном порядке ...). Есть идеи, как решить эту проблему?

например

Albert Haynesworth
Bob Marley
Carl Johnson

Большое спасибо в продвинутом. :) (C, Unix)

Answer 1

Реализовать сортировку слиянием по связанному списку в C довольно просто:

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

struct node {
    struct node *next;
    char *data;
};

struct node *
divlist (struct node *n) {
    int i = 0;
    if (n) {
        struct node *tail, *n2 = n;
        while (1) {
            n2 = n2->next;
            if (!n2) break;
            if (i++ & 1) n = n->next;
        }
        tail = n->next;
        n->next = NULL;
        return tail;
    }
    return NULL;
}

struct node *
mergelists(struct node *a, struct node *b) {
    struct node *n;
    struct node **last = &n;
    if (!a) return b;
    if (!b) return a;

    while (1) {
        if (strcmp(a->data, b->data) > 1) {
            *last = b;
            last = &b->next;
            b = b->next;
            if (!b) {
                *last = a;
                break;
            }
        }
        else {
            *last = a;
            last = &a->next;
            a = a->next;
            if (!a) {
                *last = b;
                break;
            }
        }
    }
    return n;
}

struct node *
sortlist (struct node *n) {
    struct node *tail = divlist(n);
    if (!tail) return n;
    return mergelists(sortlist(n), sortlist(tail));
}

int main(int argc, char *argv[]) {
    int i;
    struct node *n1, *n = NULL;
    for (i = argc; --i >= 1;) {
        n1 = (struct node *)malloc(sizeof(*n1));
        n1->data = argv[i];
        n1->next = n;
        n = n1;
    }

    n1 = n = sortlist(n);

    while (n1) {
        printf("%s\n", n1->data);
        n1 = n1->next;
    }
    return 0;
}

Обратите внимание, что вам придется изменить этот код, чтобы использовать структуру данных и правильное сравнение!

Answer 2

C не может ни сортировать, ни поддерживать отсортированную структуру данных. Как и предполагали другие, вам нужно разобраться в этом самостоятельно. Я бы сделал это, когда вы создадите новый Medico, поскольку вставка в связанный список очень проста, и вы можете просто найти, где он находится, при итерации.

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

Если порядок списка не имеет значения, сохраняйте его в порядке.

Answer 3

Звучит так, будто вы хотите взглянуть на реализации быстрой сортировки или mergesort .Я полагаю, что реализация cstd lib qsort принимает массив, а не связанный список, поэтому вам может потребоваться реализовать свой собственный (хотя я вполне уверен, что вы могли бы найти легкодоступную реализацию на interwebz, если бы вы сделали быстрый поиск)

Answer 4

Если вы хотите отсортировать массив структур, вы можете использовать функцию qsort, см. man qsort. Требуется базовый адрес массива, количество элементов, размер элемента и функция сравнения:

int compare(const void *a, const void *b) {
    Medico *medA = (Medico*) a;
    Medico *medB = (Medico*) b;
    return /* compare medA and medB */;
}

Medico *medicos = /* initialize */;
qsort(medicos, numberOfMedicos, sizeof(Medico), compare);

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

Medico *medicos = calloc(sizeof(Medico), numberOfMedicos);
Medico *current = /* first record in your linked list */;
int i = 0;

assert(current);
do {
    medicos[i++] = *current;
    current = current->next;
} while (current);

// Here you can sort the array.

free(medicos);

Конечно, это зависит от количества записей и других переменных.

(My C немного ржавый, не стесняйтесь исправлять.)