Sorting a linked list with structures in C
I tried to use the bubble sort method I learned in a program used to sort books that were inserted into a linked list. Ive tried replacing 2 nodes but it also caused nextptr to be replaced as well. I started this new feature called authsort, which does not reference members in the book structure. what do I need to change for this kind of work?
#include<stdlib.h>
#include <stdio.h>
#include<ctype.h>
#include<string.h>
struct book
{
char author[30];
char title[50];
char hold2[50];
char titleins[50];
char genre[15];
int rating;
int comma;
int titleshift;
int number;
};
struct listnode
{
struct book data;
struct listnode *nextptr;
};
typedef struct listnode LISTNODE;
typedef LISTNODE *LISTNODEPTR;
void insert(LISTNODEPTR *sptr, struct listnode data);
void authsort(LISTNODEPTR sptr, struct listnode data);
void freenodes(LISTNODEPTR currentptr);
int add_2 (count, i, j, index, tag);
void print_list(LISTNODEPTR, struct listnode book);
int main ()
{
LISTNODEPTR startptr = NULL;
struct listnode listnode;
struct book book;
int choice = 0;
char item;
int count = 0;
int index = 0;
int j = 0;
char * pch2;
char string[40];
char string2[40];
char * pch;
int i = 0;
while( choice != 2)
{
printf("What Would You Like To Do?\n");
printf("1.Add Books\n2.exit\n3:sort by author\n");
scanf("%d", &choice);
getchar();
switch(choice)
{
case 1:
printf("Enter your book title:");
gets(listnode.data.title);
for(i=0;i<100;i++)
{
listnode.data.title[i] = tolower(listnode.data.title[i]);
}
printf("Enter the author:");
if(listnode.data.title[0] == 't')
{
if(listnode.data.title[1] == 'h')
{
if(listnode.data.title[2] == 'e')
{
if(listnode.data.title[3] == ' ')
{
book.titleshift = 4;
pch = strtok(listnode.data.title, " ");
strcpy(string, pch);
pch2 = strtok(NULL, "");
book.comma = strlen(pch2);
strcpy(string2, pch2);
strncat(string2, string, 20);
strncpy(listnode.data.title, string2, 50);
}
}
}
}
if(listnode.data.title[0] == 'a')
{
if(listnode.data.title[1] == ' ')
{
book.titleshift = 2;
pch = strtok(listnode.data.title, " ");
strcpy(string, pch);
pch2 = strtok(NULL, "");
book.comma = strlen(pch2);
strcpy(string2, pch2);
strncat(string2, string, 20);
strncpy(listnode.data.title, string2, 50);
}
}
gets(listnode.data.author);
for(i=0;i<100;i++)
{
listnode.data.author[i] = tolower(listnode.data.author[i]);
}
printf("Enter the genre:");
gets(listnode.data.genre);
for(i=0;i<100;i++)
{
listnode.data.genre[i] = tolower(listnode.data.genre[i]);
}
printf("Enter the quality:");
scanf("%d", &listnode.data.rating);
printf("Enter the number of pages:");
scanf("%d", &listnode.data.number); // after scanning in from user, we insert and print the list
insert(&startptr, listnode);
print_list(startptr, listnode);
break;
case 2:
freenodes(startptr);
break;
case 3:
authsort(startptr, listnode);
print_list(startptr, listnode);
break;
}
}
return 0;
}
/*********************************FUNCTION*********************************/
void print_list(LISTNODEPTR currentptr, struct listnode book)
{
if (!currentptr)
printf("List is empty.\n\n");
else
{
printf("your list:\n");
while (currentptr)
{
if(currentptr->data.comma > 1)
{
printf("%-15s %-20s %-15s %-15d %-15d\n", currentptr->data.author, currentptr->data.title, currentptr->data.genre, currentptr->data.rating, currentptr->data.number);
currentptr = currentptr -> nextptr; // this will continue printing as long as there in a nextptr, or book
}
else if(currentptr->data.comma == 0)
{
printf("%-15s %-20s %-15s %-15d %-15d\n", currentptr->data.author, currentptr->data.title, currentptr->data.genre, currentptr->data.rating, currentptr->data.number);
currentptr = currentptr -> nextptr; // this will continue printing as long as there in a nextptr, or book
}
}
if(!currentptr)
{
printf("end of list\n\n");
}
}
}
/*********************FUNCTION******************/
void insert(LISTNODEPTR *sptr, struct listnode data)
{
LISTNODEPTR newptr, previousptr, currentptr;
newptr = malloc(sizeof(LISTNODE));
int i = 0;
if (newptr)
{
strcpy(newptr -> data.title,data.data.title);
//if(book.titleshift == 0)
//{
//strcpy(newptr -> title,book.title);
//}
// here the books are being copied into the current node
strcpy(newptr -> data.author, data.data.author);
strcpy(newptr -> data.genre, data.data.genre);
newptr -> data.rating= data.data.rating;
newptr -> data.number= data.data.number;
newptr -> nextptr = NULL;
previousptr = NULL;
currentptr = *sptr;
while (currentptr != NULL && strcmp(data.data.title, currentptr -> data.title)>0)
// this compares the titles to insert by author
{
previousptr = currentptr;
currentptr = currentptr -> nextptr;
}
if (previousptr == NULL)
{
newptr -> nextptr = *sptr;
*sptr = newptr;
}
else
{
previousptr -> nextptr = newptr;
newptr -> nextptr = currentptr;
}
}
else
{
printf("Not inserted.\n");
}
}
/*******************************FUNCTION***********************************/
/**************************FUNCTION*********************/
void freenodes(LISTNODEPTR currentptr)
{
LISTNODEPTR tempptr;
while(currentptr!=NULL)
{
tempptr=currentptr->nextptr;
free(currentptr);
currentptr=tempptr;
}
}
void authsort(LISTNODEPTR sptr, struct listnode data)
{
LISTNODEPTR nextptr;
LISTNODEPTR previousptr;
LISTNODEPTR currentptr;
LISTNODEPTR tempptr;
LISTNODEPTR trail;
int count = 0;
int j = 0;
while(sptr != NULL)
{
count++;
sptr = sptr -> nextptr;
}
for(j=0;j<count;j++)
{
currentptr = sptr;
while(currentptr->nextptr != NULL)
{
if(strcmp(currentptr ->data.author, currentptr->nextptr.data.author)>0)
{
tempptr = currentptr ->nextptr;
currentptr ->nextptr = currentptr ->nextptr->nextptr;
currentptr ->nextptr = currentptr;
if(currentptr == sptr)
sptr = trail = tempptr;
else
trail->nextptr = tempptr;
currentptr = tempptr;
}
trail = currentptr;
currentptr = currentptr->nextptr;
}
}
}
source to share
See, your ultimate goal should be for the linked list to be sorted. Now you are trying to sort two nodes, but you can even exchange their data.
It doesn't involve moving the pointer and makes your program much easier to parse and understand. Hope this gives you the correct solution!
Happy coding :)
source to share
There are some problems in the code:
- After you have defined the length,
sptr
-NULL
. From now on, you cannot do anything intelligent with your code, because you have lost the head pointer. - If you want to swap yourself and not just the data, you may need to update the head pointer. For now, you are just passing a pointer to the head, but if the calling code is to reflect the changes made to the head pointer, you must pass a pointer to a pointer to the head.
- When replacing a pointer, you must also update the pointer pointing to the current node, which is
sptr
either a member of thenextptr
previous node. - You are using too many temporary variables.
trail
never used, for example, and none of them are the second parameter to your function.
Eliminate these problems. First, we won't be using an account. Instead, we keep track of whether any nodes in the aisle need to be changed. If not, we're done because the list is sorted. Otherwise, we make another pass.
The problem of keeping track of the previous node has a neat solution involving passing a pointer to a head pointer as an argument: Iterating with a pointer to the current node pointer, which adds one level of indirection: the iteration pointer curr
now points to a pointer that points to the current node, which is either the original a head pointer passed from your calling function or a member nextptr
.
This solution does not make the head pointer a special case. This results in shorter code, but also strong syntax (*curr)
.
Here's a working implementation that replaces the nodes instead of the payload:
void authorsort(struct listnode **sptr)
{
int done = 0;
while (!done) {
struct listnode **curr = sptr;
done = 1;
while ((*curr)->nextptr != NULL) {
if (strcmp((*curr)->data.author,
(*curr)->next->data.author) > 0) {
struct listnode *temp = (*curr)->nextptr;
(*curr)->nextptr = temp->nextptr;
temp->nextptr = *curr;
*curr = temp;
done = 0;
}
curr = &(*curr)->nextptr;
}
}
}
(Exchange workload is simpler, but exchange of nodes is necessary if you have pointers to these nodes from the outside, for example, if a collection of books refers to books as pointers.)
source to share