Быстрая сортировка двусвязного списка - C (СИ)
Формулировка задачи:
Уважаемые ! Продолжаются мое обучение, а с ним и появляются новые вопросы. Пытаюсь остортировать двусвязный список быстрой сортировка. Делаю по аналогии с пузырком и с быстрой сортировкой массива. Вот код:
Если выключить рекурсию, и все условия, код с перестановкой местами ячеек работает. Подозреваю что что то не так в логических условиях. Помогите , наведите на правильную мысль! Спасибо"
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct L { int value; char name[10]; struct L *next, *prev; } ListItem; static ListItem base,*current,*pos,*prev2,*next2,*current2,*current3; static int a,b,c,k,g,num; void print_pos(void); void creation_zero(void); void creation(void); void scan_creation(void); void swap_sort(void); void quicksort(ListItem*,ListItem*,ListItem*); void start_pointer_sort(void); int main(){ creation_zero(); do{ scan_creation(); if(pos->value==0){ free(pos); break; } creation(); } while(1); print_pos(); quicksort(current,current->next,current->prev); printf("\n\n"); print_pos(); return 0; } void print_pos(){/*Печать всего списка*/ pos=current->prev; while(pos!=&base){ printf("\nname=%s \ttall=%d\n",pos->name,pos->value); pos=pos->prev; }} void creation_zero(){/*Создать нулевое звено*/ current = &base; base.next = base.prev = &base; num=0; } void scan_creation(){/*Выделение памяти и запись значений*/ pos = (ListItem*)malloc(sizeof(ListItem)); printf("\nWhat is your name? \t"); scanf("%s",&pos->name); printf("\nHow tall are you? \t"); scanf("%d",&pos->value); } void creation(){/*Создание звена и определение его местоположения*/ pos->next = current->next; pos->prev = current; current->next->prev = pos; current->next = pos; num++; } void quicksort(ListItem *k,ListItem *first,ListItem *last){//быстрая сортировка(указатель на структуру, на начало списка,на конец списка) ListItem *i=first,*j=last; ListItem *first1=i->prev,*last1=j->next; int x=(first->value+last->value)/2; do { while (i->value < x) i=i->next; while (j->value > x) j=j->prev; if(i!=j) { if (i->value > j->value){ i->next->prev=j; i->prev->next=j; j->prev->next=i; j->next->prev=i; j->next=i->next; i->next=last1; i->prev=j->prev; j->prev=first1; i=j->next; j=i->prev; first1=i->prev; last1=j->next; } } } while (i!=j); if (last!=i) quicksort(k,i,last); if (first!=j) quicksort(k,first,j); }
Решение задачи: «Быстрая сортировка двусвязного списка»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include "llist.h" #define NAME_LENGTH (32) #define get_name(s) ( scanf("%31s", (s)) == 1 ) typedef struct DATA { char name[NAME_LENGTH]; int value; } data_t; void * copy_data(const void * dataTemplate) { void * ptr = malloc(sizeof(data_t)); assert(ptr); return memcpy(ptr, dataTemplate, sizeof(data_t)); } void destroy_data(void * dataPtr) { free(dataPtr); } void print_data(const void * ptr) { data_t * pData = (data_t*)ptr; printf("%3d\t%s\n", pData->value, pData->name); } int compare_data(const void * pA, const void * pB) { data_t * a = (data_t*)pA; data_t * b = (data_t*)pB; int ret = a->value - b->value; return ( ret ) ? ret : strcmp(a->name, b->name); } void print_help(void) { printf("1 - help\n" "2 - add value\n" "3 - delete value\n" "4 - dump list\n" "5 - sort list\n" "6 - find data\n" "7 - change data\n" "8 - list size\n" "0 - quit\n\n" ); } void flush_input(void) { char c; while ( scanf("%c", &c) == 1 && c != '\n' ) ; } int fill_data(data_t * pData) { memset(pData, 0, sizeof(data_t)); printf("Name: "); if ( ! get_name(pData->name) ) return -1; printf("Value: "); if ( scanf("%d", &(pData->value)) != 1 ) return -1; flush_input(); return 0; } int menu(void) { int ret; printf("[1 - help] > "); if ( scanf("%d", &ret) != 1 ) { flush_input(); return -1; } flush_input(); return ret; } int main(void) { int ret, done = 0; llist_t * list = llist_new(copy_data, destroy_data, compare_data); assert(list); while ( ! done ) { switch ( menu() ) { case 1: print_help(); break; case 2: { data_t data; ret = fill_data(&data); assert(ret == 0); ret = llist_add(list, &data); assert(ret == 0); printf("Ok\n"); break; } case 3: { data_t data; ret = fill_data(&data); assert(ret == 0); ret = llist_remove(list, &data); if ( ret ) printf("Not in list!\n"); else printf("Ok\n"); break; } case 4: llist_foreach(list, print_data); break; case 5: llist_sort(list, NULL); printf("Ok\n"); break; case 6: { data_t data; ret = fill_data(&data); assert(ret == 0); printf("%sound.\n", ( llist_contains(list, &data) ) ? "F" : "Not f"); break; } case 7: { data_t oldData, newData; printf("Old data\n"); ret = fill_data(&oldData); assert(ret == 0); printf("New data\n"); ret = fill_data(&newData); assert(ret == 0); ret = llist_update(list, &oldData, &newData); printf("%s\n", ( ret ) ? "Error!\n" : "Ok"); break; } case 8: printf("%d items in list.\n", llist_size(list)); break; case 0: done = 1; break; default: printf("Wrong choice!\n"); break; } } llist_del(list); return 0; }
Объяснение кода листинга программы
В данном коде реализована быстрая сортировка двусвязного списка.
Список представляет собой структуру данных llist_t
, которая содержит функции для работы с этим списком.
Код включает в себя следующие функции:
- copy_data - функция для копирования данных из одного указателя в другой.
- destroy_data - функция для освобождения памяти, выделенной под данные.
- print_data - функция для вывода данных на экран.
- compare_data - функция для сравнения двух элементов списка.
- print_help - функция для вывода на экран списка команд.
- flush_input - функция для очистки входного потока данных.
- fill_data - функция для заполнения структуры данных
data_t
. - menu - функция для вывода на экран списка команд и выбора команды пользователем.
- main - основная функция программы.
В основной функции программы происходит инициализация списка, заполнение его данными, выбор команды пользователем и выполнение этой команды.
После выполнения всех команд программа выводит сообщение
Ok
и завершается.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д