Сортировка выбором двунаправленного списка - C (СИ)
Формулировка задачи:
Добрый день
Есть часть кода отвечающая за сортировку двунаправленного списка методов прямого включения по полю структуры size.
Не могли бы вы помочь разобраться, как ее можно переписать для сортировки выбором?
Сортировка выбором: Найти элемент с минимальным значением size вставить в первое место нового списка, найти следующий элемент с минимальынм значением вставить на 2 место и так далее.
extern void insertion_sort(List_p list) { Lnode_p cur, proc; int state = 1; Data_p key; for (cur = list->head->next; cur != list->head; cur = cur->next) { key = cur->info; proc = cur->prev; while (state==1 && proc->info->size > key->size) { proc->next->info = proc->info; proc = proc->prev; if (proc->next == list->head) state = 0; } proc->next->info = key; state = 1; } }
typedef struct data { char *name; char *type; char *date; char *mod; unsigned size; unsigned treat; } Data; typedef struct data *Data_p; typedef struct list_node { struct data *info; struct list_node *next; struct list_node *prev; } Lnode; typedef struct list_node *Lnode_p;
Решение задачи: «Сортировка выбором двунаправленного списка»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct DATA { char * name; size_t growth; } data_t; data_t * new_data(const data_t * tmp) { data_t * data = malloc(sizeof(data_t)); if ( ! data ) return NULL; if ( ! ( data->name = strdup(tmp->name) ) ) { free(data); return NULL; } data->growth = tmp->growth; return data; } void del_data(data_t * data) { free(data->name); free(data); } typedef struct NODE { data_t * data; struct NODE * next; } node_t; node_t * new_node(const data_t * data) { node_t * node = malloc(sizeof(node_t)); if ( ! node ) return NULL; if ( ! ( node->data = new_data(data) ) ) { free(node); return NULL; } node->next = NULL; return node; } void del_node(node_t * node) { del_data(node->data); free(node); } typedef struct LIST { node_t * first; node_t * last; } list_t; list_t * new_list(void) { list_t * list = malloc(sizeof(list_t)); if ( ! list ) return NULL; list->first = NULL; list->last = NULL; return list; } void del_list(list_t * list) { while ( list->first ) { list->last = list->first->next; del_node(list->first); list->first = list->last; } } int add_data(list_t * list, const data_t * data) { node_t * node = new_node(data); if ( ! node ) return -1; if ( ! list->first ) list->first = node; else list->last->next = node; list->last = node; return 0; } void print_data(const list_t * list) { node_t * node; printf("Name Growth\n------------------------------\n"); for ( node = list->first; node != NULL; node = node->next ) printf("%-20s%u\n", node->data->name, node->data->growth); printf("\n"); } void swap_data(node_t * a, node_t * b) { data_t * tmp = a->data; a->data = b->data; b->data = tmp; } node_t * min_growth_node(node_t * first) { node_t * ret = first; while ( first = first->next ) { if ( ret->data->growth > first->data->growth ) ret = first; } return ret; } void sort_list(list_t * list) { node_t * ptr, * mingrowth; for ( ptr = list->first; ptr && ptr->next; ptr = ptr->next ) if ( ( mingrowth = min_growth_node(ptr) ) != ptr ) swap_data(ptr, mingrowth); } int main(void) { char buf[BUFSIZ]; data_t data; data.name = buf; list_t * list; if ( ! ( list = new_list() ) ) { fprintf(stderr, "Memory error!\n"); exit(1); } while ( printf("Name: ") && scanf("%s", data.name) == 1 && printf("Growth: ") && scanf("%u", &data.growth) == 1 ) { if ( add_data(list, &data) ) { fprintf(stderr, "Memory error!\n"); exit(1); } } printf("\nUnsorted:\n"); print_data(list); sort_list(list); printf("Sorted by growth ascendant:\n"); print_data(list); del_list(list); exit(0); }
Объяснение кода листинга программы
В данном коде реализована двунаправленная очередь с использованием связанного списка.
- Создаются структуры данных:
data_t
- содержит данные о размере (growth) и имени (name)node_t
- содержит указатель на данные (data
) и ссылку на следующий элемент (next
)list_t
- содержит указатели на первый (first
) и последний (last
) элементы списка
- Реализованы функции для работы со списком:
new_data
- создает новый экземпляр структурыdata_t
и копирует в него указанные данные. Если выделение памяти или копирование данных не удалось, функция возвращаетNULL
.del_data
- освобождает память, выделенную подdata_t
new_node
- создает новый экземпляр структурыnode_t
и заполняет его новыми данными изdata_t
. Если выделение памяти или заполнение структуры не удалось, функция возвращаетNULL
.del_node
- освобождает память, выделенную подnode_t
иdata_t
new_list
- создает новый экземпляр структурыlist_t
и заполняет его начальными значениямиdel_list
- освобождает память, выделенную подlist_t
и его элементыadd_data
- добавляет новый элемент в список. Если выделение памяти или добавление элемента не удалось, функция возвращает-1
print_data
- выводит данные из списка в форматеИмя Размер
swap_data
- меняет местами данные в двух узлах спискаmin_growth_node
- находит в списке узел с минимальным значениемgrowth
sort_list
- сортирует список по возрастанию значенияgrowth
- В функции
main
создается экземпляр списка, заполняется данными, полученными от пользователя, сортируется и выводится на экран. После этого список освобождается от памяти. - Ошибки памяти обрабатываются с помощью функции
fprintf
иexit
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д