Сортировка выбором двунаправленного списка - C (СИ)

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

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

Добрый день Есть часть кода отвечающая за сортировку двунаправленного списка методов прямого включения по полю структуры size.
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;
Не могли бы вы помочь разобраться, как ее можно переписать для сортировки выбором? Сортировка выбором: Найти элемент с минимальным значением size вставить в первое место нового списка, найти следующий элемент с минимальынм значением вставить на 2 место и так далее.

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

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);
}

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

В данном коде реализована двунаправленная очередь с использованием связанного списка.

  1. Создаются структуры данных:
    • data_t - содержит данные о размере (growth) и имени (name)
    • node_t - содержит указатель на данные (data) и ссылку на следующий элемент (next)
    • list_t - содержит указатели на первый (first) и последний (last) элементы списка
  2. Реализованы функции для работы со списком:
    • 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
  3. В функции main создается экземпляр списка, заполняется данными, полученными от пользователя, сортируется и выводится на экран. После этого список освобождается от памяти.
  4. Ошибки памяти обрабатываются с помощью функции fprintf и exit.

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


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

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

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