Сортировка двусвязного списка пузырьком - 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; };
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; }
Решение задачи: «Сортировка двусвязного списка пузырьком»
#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
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д