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

Добрый день,
Были заданы два задания:
Создать односвязный список (список литературы); На основе первого задания, сделать сортировку вставками по 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
================

"); int counter = 1; element *elem = alist->first; while (elem != NULL) { printf("Buch %d
", counter); printf("\tTitel: %s
", elem->title); printf("\tAutor: %s
", elem->author); printf("\tJahr: %d
", elem->year); printf("\tISBN: %lld
", 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; }

Ответ

Вам не следует использовать имена, начинающиеся с подчеркивания, так как они зарезервированы за реализацией стандартных библиотек.
Также совершенно нет никакой необходимости объявлять список в динамической памяти.
Ниже приведена демонстрационная программа, которая сортирует список по возрастанию номеров 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( "
" );
sort_by_isbn( &lst );
print_list( &lst ); printf( "
" );
return 0; }
Вывод программы может выглядеть следующим образом:
461971353 1686854524 262763134 1776774882 166562428 351823644 1662884659 155739745 669011733 1476766544 155739745 166562428 262763134 351823644 461971353 669011733 1476766544 1662884659 1686854524 1776774882