Сортировка двусвязного списка пузырьком - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Есть структура:
struct stud{
    char num[20];
    char tel[15];
    char name[20];
    int byear;
    int bday;
    int bmonth;
    int year;
    int yrs;
    int del;
    struct stud *next;
    struct stud *prev;
};
Есть нормально забитый двусвязный список. Надо отсортировать его по году рождения (byear). Где я неправ, что получается какой-то бред на выходе?
for (i = 0; i < amount; i++)
                while (ptr2->next != NULL)
                {
 
                    if (ptr1->byear > ptr2->byear)
                    {
                        ptr2->prev = ptr1->prev;
                        ptr1->prev = ptr2;
                        ptr1->next = ptr2->next;
                        ptr2->next = ptr1;
                        if (ptr1->next != NULL)
                            ptr1->next->prev = ptr1;
                        if (ptr2->prev != NULL)
                            ptr2->prev->next = ptr2;
                    }
                    ptr2 = ptr2->next->next;
                        ptr2 = ptr2->next;
                        ptr1 = ptr1->next;
                    }
amount - переменная, обозначающая количество элементов. ptr1 - элемент 1, 2, 3..., ptr2 - элемент 2, 3, 4... соответственно. Заранее спасибо за помощь.

Решение задачи: «Сортировка двусвязного списка пузырьком»

textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
 
typedef struct ELEM_
{
    struct ELEM_ *next;
    int value;
}ELEM;
 
typedef struct
{
    ELEM *cur, *head;
}LIST;
 
typedef int (*Pfun)( const void *, const void *);
 
int cmp( const void *a, const void *b )
{
    
    return *( (int * )a ) - *( ( int * )b );
}
 
 void Exchange( LIST *list )
 {
    ELEM *prev = list->head, *temp;
 
    if( list->cur != list->head )
 
         while( prev->next != list->cur )
                        prev = prev->next;
 
 
    temp = list->cur->next;
    list->cur->next = temp->next;
 
        temp->next = list->cur;
    if( list->cur == list->head )
        list->head = temp;
    else
        prev->next = temp;
 
 
 }
void BubbleSortList( LIST *list, Pfun fun )
{
    int flag = 1;
    if( !list->head )
            return;
    while ( flag )
        {
           flag = 0;
           list->cur = list->head;
           while( list->cur->next )
               if( fun( &list->cur->value, &list->cur->next->value) > 0)
                {
 
 
                    Exchange( list );
                    flag = 1;
 
                }
                else
                    list->cur = list->cur->next;
 
           }
 
 
list->cur = list->head;
}
int Push( LIST *list, int value )
    {
        ELEM *temp = (ELEM*)malloc( sizeof(ELEM) );
        if( !temp ) return 1;
        temp->value = value;
        if( !list->head )
 
            list->head = temp;
 
        else
        {
            list->cur = list->head;
            while( list->cur->next )
                    list->cur = list->cur->next;
 
            list->cur->next = temp;
        }
 
        temp->next = NULL;
        return 0;
    }
int Pop( LIST *list )
{
    list->cur = list->head;
    list->head = list->cur->next;
    int value = list->cur->value;
    free( list->cur );
    return value;
}
int main()
{
 
    LIST head;
    head.cur = head.head = NULL;
 
    int mass[] = { 5, -1, 4, 7, 2 , 2,-12,423,12,43, 0,3,1,45,-12,-123
    };
    for( int i = 0; i < sizeof(mass)/sizeof(mass[0] ); i++ )
        Push( &head, mass[i] );
    BubbleSortList( &head, cmp );
    for( int i = 0; i < sizeof(mass)/sizeof(mass[0] ); i++ )
            printf( "%d ", Pop( &head) );
    return 0;
}

Объяснение кода листинга программы

В данном коде реализуется сортировка двусвязного списка пузырьком. Список представляет собой связный список, состоящий из элементов типа ELEM. Каждый элемент списка содержит указатель на следующий элемент (next) и значение (value). Сортировка осуществляется с помощью функции BubbleSortList, которая принимает указатель на список и функцию сравнения. В данном случае используется функция cmp, которая сравнивает значения двух элементов и возвращает результат сравнения. В функции BubbleSortList используется цикл while, который продолжается до тех пор, пока в списке остаются элементы. На каждой итерации цикла выполняется проверка: если текущий элемент больше следующего, то они меняются местами с помощью функции Exchange. Флаг flag используется для контроля за каждой итерацией цикла. Если на какой-то итерации обмен не произошел, то это означает, что список уже отсортирован. Функция Push добавляет новый элемент в список. Если список пуст, то новый элемент становится головой списка. В противном случае новый элемент добавляется в конец списка. Функция Pop удаляет и возвращает последний элемент списка. После удаления элемента, указатель cur перемещается к предыдущему элементу списка. Если удаленный элемент был последним, то cur становится NULL. В функции main создается экземпляр списка head. Затем в список добавляются элементы из массива mass с помощью функции Push. После этого вызывается функция BubbleSortList для сортировки списка. Наконец, элементы списка последовательно удаляются с помощью функции Pop и выводятся на экран с помощью функции printf.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 4.455 из 5
Похожие ответы