Сортировка элементов (insertion sort) односвязного списка. си

#c #сортировка #указатели #список

Добрый день, 

Были заданы два задания: 


Создать односвязный список (список литературы);
На основе первого задания, сделать сортировку вставками по ISBN книг в порядке возрастания. 


Сам список отработал хорошо. Сортировку же реализовать не удаётся.
Вот наработки кода сортировки, есть ли хоть что-то близкое к истине?   

    element* insert_sorted(element *first, element *new_elem) {

    element *current = first;
    //element *insert = first;
    current = current->next; 
    element *temp;

    // element *next = first->next;
    // element *prev=NULL;
    // prev->next = first;

    // if(first==NULL){
    //     first = new_elem;
    // }
    while(current!=NULL){
        new_elem = first;
        while(new_elem!=current){
            if(new_elem->isbn > current->isbn){
                    temp = current->next;
                    current->next = new_elem;
                    new_elem->next = temp;

                    // first = next;
                    // temp = next;
            }
            else{
                new_elem = new_elem->next;
                    // end = next->next;
                    // next->next = new_elem;
                    // new_elem->next = end;

                    // prev = next;
                    // next = first->next;
            }
        }
        // else{
        //     prev = new_elem;
        //     new_elem = new_elem->next;
        // }
        // next = new_elem->next;
        // if (next == end){
        //     end = new_elem;
        }
    return first;
}


Код программы целиком: 

#include 
#include 
#include 

typedef struct _element element; 

typedef struct _list list;

struct _list {      
    element *first; 
    int count;      
};

struct _element
{
    char *title;
    char *author;
    int year;
    long long int isbn;
    element *next;
};

element* insert_sorted(element *first, element *new_elem) {
    /* HIER implementieren. */
    element *current = first;
    //element *insert = first;
    current = current->next; 
    element *temp;
    // element *next = first->next;
    // element *prev=NULL;
    // prev->next = first;

    // if(first==NULL){
    //     first = new_elem;
    // }
    while(current!=NULL){
        new_elem = first;
        while(new_elem!=current){
            if(new_elem->isbn > current->isbn){
                    temp = current->next;
                    current->next = new_elem;
                    new_elem->next = temp;

                    // first = next;
                    // temp = next;
            }
            else{
                new_elem = new_elem->next;
                    // end = next->next;
                    // next->next = new_elem;
                    // new_elem->next = end;

                    // prev = next;
                    // next = first->next;
            }
        }
        // else{
        //     prev = new_elem;
        //     new_elem = new_elem->next;
        // }
        // next = new_elem->next;
        // if (next == end){
        //     end = new_elem;
        }
    return first;
}

element *construct_element(char *title, char* author, int year, long long int isbn) {

    element *buch =  (element*) malloc (sizeof(element));
    buch->title = malloc(MAX_STR* sizeof(char));
    buch->author = malloc(MAX_STR* sizeof(char));
    strcpy(buch->title,title);
    strcpy(buch->author,author);
    buch->year = year;
    buch->isbn = isbn;
    buch->next = NULL;
    return buch;
}

void free_list(list *alist) {

    element* current;
    element* head = alist->first;

    free(alist);

    while((current = head) != NULL){
        head = head->next;

        free(current->title);
        free(current->author);
        free(current);
    }
}

void read_list(char* filename, list *alist) {
    element* new_elem;

    char title[MAX_STR];
    char author[MAX_STR];
    int year;
    long long int isbn;
    while(read_line(filename, title, author, &year, &isbn) == 0) {
        new_elem = construct_element(title, author, year, isbn);
        alist->first = insert_sorted(alist->first, new_elem);
        alist->count++;
    }
}

list* construct_list() {
    list *alist = malloc(sizeof(list));
    alist->first = NULL;
    alist->count = 0;
    return alist;
}

void print_list(list *alist) {
    printf("Meine Bibliothek\n================\n\n");
    int counter = 1;
    element *elem = alist->first;
    while (elem != NULL) {
        printf("Buch %d\n", counter);
        printf("\tTitel: %s\n", elem->title);
        printf("\tAutor: %s\n", elem->author);
        printf("\tJahr:  %d\n", elem->year);
        printf("\tISBN:  %lld\n", elem->isbn);
        elem = elem->next;
        counter++;
    }
}

int main() {
    list *alist = construct_list();
    read_list("buecherliste.txt", alist);
    print_list(alist);
    free_list(alist);
    return 0;
}

    

Ответы

Ответ 1

Вам не следует использовать имена, начинающиеся с подчеркивания, так как они зарезервированы
за реализацией стандартных библиотек.

Также совершенно нет никакой необходимости объявлять список в динамической памяти.

Ниже приведена демонстрационная программа, которая сортирует список по возрастанию
номеров ISBN. Надеюсь, она использует метод сортировки вставкой.:)

Для наглядности я упростил определения и убрал из программы все лишнее, что не требуется
конкретно для сортировки. Вам, естественно, потребуется нарастить "мясом" данный "скелет"
метода.

#include 
#include 
#include 

typedef struct element
{
    unsigned long long int isbn;
    struct element *next;
} element;

typedef struct list 
{      
    element *first; 
    int count;      
} list;


list construct_list() 
{
    list lst = { NULL, 0 };
    return lst;
}

void  push_front( list *lst, unsigned long long int isbn )
{
    element *item = malloc( sizeof( element ) );

    if ( item )
    {
        item->next = lst->first;
        item->isbn = isbn;

        lst->first = item;
    }
}

void print_list( const list *lst )
{
    for ( const element *current = lst->first; current; current = current->next )
    {
        printf( "%lld ", current->isbn );
    }
}

void sort_by_isbn( list *lst )
{
    if ( lst->first )
    {
        element *current = lst->first->next;
        lst->first->next = NULL;
        while ( current )
        {
            if ( current->isbn < lst->first->isbn )
            {
                element *tmp = current;
                current = current->next;
                tmp->next = lst->first;
                lst->first = tmp;
            }
            else
            {
                element *first = lst->first;
                while ( first->next && !( current->isbn < first->next->isbn ) )
                {
                    first = first->next;
                }

                element *tmp = current;
                current = current->next;
                tmp->next = first->next;
                first->next = tmp;
            }
        }
    }
}    

#define N   10
int main( void )
{
    list lst = construct_list();

    srand( ( unsigned int )time( NULL ) );

    for ( int i = 0; i < N; i++ ) push_front( &lst, rand() );

    print_list( &lst );
    printf( "\n" );

    sort_by_isbn( &lst );

    print_list( &lst );
    printf( "\n" );

    return 0;
}


Вывод программы может выглядеть следующим образом:

461971353 1686854524 262763134 1776774882 166562428 351823644 1662884659 155739745
669011733 1476766544 
155739745 166562428 262763134 351823644 461971353 669011733 1476766544 1662884659
1686854524 1776774882