4

Добрый день,

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

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

  2. На основе первого задания, сделать сортировку вставками по 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 <stdio.h>
#include <stdlib.h>
#include <string.h>

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;
}
3
  • Я не понял: вам надо отсортировать уже существующий список, или вставлять новые элементы в список в соответствии с порядком сортировки? 27 ноя 2015 в 14:20
  • И почему у вас лист не присутствует в качестве параметра метода вставки? 27 ноя 2015 в 14:23
  • 1
    @Vlad from Moscow здравствуйте. Да, нужно отсортировать уже существующий список, созданный в первом задании. Потому, что я туповатый новичок?) Вы имеете в виду: element* insert_sorted(element *first, element *new_elem, *list) или?
    – 4lunas
    27 ноя 2015 в 14:30

1 ответ 1

1

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

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

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

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

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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 
1
  • Большое спасибо за вашу помощь и рекомендации. К сожалению, всё это: _имена, динамическая память - были обязательными условиями от преподавателей. Нам изначально даётся структура, на которой мы должны работать. Не только сама структура, порой, вызывает "восторг", но и "гениальный" комментарии, типа: "Т.к. 2 не является простым числом..." и т.д. Научиться от таких людей сложно чему либо, а предмет нужно засчитать. Поэтому ещё раз благодарю!
    – 4lunas
    27 ноя 2015 в 16:40

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.