Question:
Good day,
Two tasks were assigned:
-
Create a singly linked list (bibliography);
-
Based on the first task, do the insertion sort by ISBN of books in ascending order.
The list itself worked well. Sorting cannot be implemented.
Here are the workings of the sorting code, is there anything close to the truth?
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;
}
Entire program code:
#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;
}
Answer:
You should not use names beginning with underscores, as they are reserved by the standard library implementation.
Also, there is absolutely no need to declare the list in heap.
Below is a demo program that sorts the list in ascending order by ISBN numbers. Hopefully it uses the insertion sort method. 🙂
For clarity, I simplified the definitions and removed from the program all unnecessary things that are not required specifically for sorting. You, of course, need to build up this "skeleton" of the method with "meat".
#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;
}
The program output might look like this:
461971353 1686854524 262763134 1776774882 166562428 351823644 1662884659 155739745 669011733 1476766544
155739745 166562428 262763134 351823644 461971353 669011733 1476766544 1662884659 1686854524 1776774882