Структура сортировки по именам (двухсвязный список)

Я пытаюсь отсортировать свою структуру на основе имен (в алфавитном порядке). Например, у меня есть такая структура:

struct person{
    char name[MAX];
    char num[MAX];
    char email[MAX];
    struct person *next;   
    struct person *previous;  
};

struct person *next, *first, *end;

и в моей основной функции:

int main()
{
 struct person p = {{0}}
 .
 .
 .
 switch(choice)
    {
    case 1 : 
        printf("Name   : "); scanf("%s", &p.name);
        printf("Num : "); scanf("%s", &p.num);
        printf("E-Mail   : "); scanf("%s", &p.email);
        input(p); //function to input data    
        break;
    case 2 : 
        sort(p); //function to sort the data
        break;
               }
}

И в моей функции-прототипе:

void sort(struct person p)
{
    struct person *ptr, *ptr2, *temp;

    ptr=first;
    ptr2=first;

    for (ptr= first; ptr!= NULL; ptr= ptr->next)
    {
        for (ptr2= ptr2->next; ptr2!= NULL; ptr2= ptr2->next)
        {
            if (strcmp(ptr->name, ptr2->name) > 0)
            {
                temp = ptr;
                ptr= ptr2;
                ptr2= temp;
            }
        }
    }

}

Итак, у меня есть функция-прототип, которая сортирует структуру на основе ее элемента, которым является имя. Я пробовал сортировать его по тому же принципу, что и сортировка пузырем, но у меня это не сработало. Указатель ptr указывает на первый узел в списке, а ptr2 указывает на второй узел. Мой алгоритм неверен? Кажется, я не могу понять, что не так. Основная проблема с сортировкой. Надеюсь, мой вопрос понятен.


c sorting pointers data-structures doubly-linked-list
person dboy    schedule 18.11.2013    source источник
comment
После сортировки у вас, вероятно, будет другой элемент в начале списка. Как вы узнаете, какой элемент является новым началом списка? Я не думаю, что вы узнаете с текущим кодом. Ваша функция сортировки, вероятно, не должна принимать прямой struct person p; скорее всего, это будет struct person **p или struct person &*p.   -  person Jonathan Leffler    schedule 18.11.2013

Ответы (2)


arrow_upward
1
arrow_downward

Внутренняя петля

    for (ptr2= ptr2->next; ptr2!= NULL; ptr2= ptr2->next)

должно быть

    for (ptr2= ptr->next; ptr2!= NULL; ptr2= ptr2->next)

(обратите внимание на ptr2 против ptr).

РЕДАКТИРОВАТЬ:

Перестановка указателей тоже не работает. Вы должны повторно связать элементы, для которых требуются вспомогательные переменные в циклах. При работе со ссылками можно сделать более элегантным (--> работа с заголовком списка):

static void swap(struct person **a, struct person **b)
{
    struct person       *tmp;

    if ((*a)->next)
        (*a)->next->prev = *b;

    if ((*b)->next)
        (*b)->next->prev = *a;

    tmp        = (*a)->prev;
    (*a)->prev = (*b)->prev;
    (*b)->prev = tmp;

    tmp        = (*a)->next;
    (*a)->next = (*b)->next;
    (*b)->next = tmp;

    tmp = *b;
    *b  = *a;
    *a  = tmp;
}

void foo()
{
    struct person **a;
    struct person *prev_a;

    for (a = &first; *a != NULL; a = &(prev_a->next)) {
        struct person **b;
        struct person *prev_b;

        prev_a = (*a)->prev;

        for (b = &(*a)->next; *b != NULL; b = &(prev_b->next)) {
            prev_b = (*b)->prev;

            if (strcmp((*a)->name, (*b)->name) > 0)
                swap(a, b);

            /* prev_b == NULL can not happen because inner loop is started
               in the middle of the list */
            prev_b = prev_b->next;
        }

        if (prev_a)
            prev_a = prev_a->next;
        else
            prev_a = first;
    }
}

РЕДАКТИРОВАТЬ:

Реализация ядра Linux, такого как связанные списки (с фиктивной головой, которая связана в начале и в конце списка), упрощает работу в методе подкачки, поскольку проверки нулевого указателя могут быть опущены. Например. список будет выглядеть

     ,------------> HEAD ------------\
    | +------------     <-----------\  \ 
    | |                              |  |
    | `-> elem_n --> ... --> elem_0 -`  |
     `---        <-- ... <--        <---'
person ensc    schedule 18.11.2013
comment
Вы могли бы прояснить это с некоторыми пояснениями; мне потребовалось больше второго взгляда, чтобы заметить разницу (инициализация из ptr->next вместо ptr2->next). Я также не уверен, что это единственная проблема. - person Jonathan Leffler; 18.11.2013

arrow_upward
0
arrow_downward

Не меняйте местами указатели, меняйте местами значения. Также нужно инициализировать пустые указатели на NULL, по умолчанию их нет.

person Igor Ševo    schedule 18.11.2013