sorted linked list

**budala** · 07-25-2009

ok, a new problem. inserting a node in a sorted list. I just give the struct and the sortedinput function, as everything works flawlessly.

the problem is in the special case when new is younger than the head node. it always prints as if it is older. if I enter:

Code:

a 10 b 20 c 5

it should print out

Code:

c 5 a 10 b 20

but instead it prints out

Code:

a 10 c 5 b 20

Code:

typedef struct node
	{
		int age;
		char name[10];
		struct node *next;
	} person;


void sortedinput(person **head)
{
	person *new = malloc(sizeof(person));
	person *temp = *head;
	char name[10];
	
	printf("\nEnter name: ");
	scanf("%s", name);
	strcpy(new->name, name);
	printf("Enter age: ");
	scanf("%d",&new->age);
	
	/*special case if list is empty*/
	if (*head == NULL)
	{
		*head = new;
		new->next = NULL;
	}
	else
	{
		/*special case when new is younger than temp(head)*/
		if (new->age < temp->age)
		{
			new->next = temp;
			temp = new;
		}
		else
		/*cases when new is older than temp(head)*/
		{
			while (temp->next != NULL && temp->next->age < new->age)
			{
				temp = temp->next;
			}
			new->next = temp->next;
			temp->next = new;
		}	
	}
}

**roaan** · 07-25-2009

i think

*head = new

instead of

temp = new

should solve the problem

**budala** · 07-25-2009

Unbelievable!!! Thanks man! (or woman) :-)

**roaan** · 07-25-2009

Its man :-)

**budala** · 07-28-2009

Ok, a new idea. Using the tested SortedInsert() to sort an existing list. My idea is that I start from the first node in the existing list and insert it using SortedInsert() into a new list. But it doesn't work. The SortedInsert() itself works but when I try using it with SortList() it doesn't.

Code:

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

/* DEFINE NODE*/
typedef struct node
	{
		int age;
		char name[10];
		struct node *next;
	} person;

/* DEFINE MENU*/
void Menu()
{
	printf("\n***\tMENU\t***\n");
	printf("\n 1.) Insert");
	printf("\n 2.) Print");
	printf("\n 3.) Sort");
	printf("\n 0.) EXIT");
	printf("\nChoose ---------> ");	
}

/* CREATE A NEW PERSON*/
person* CreatePerson()
{
	person *new = malloc(sizeof(person));
	char name[10];
	
	printf("\nEnter name: ");
	scanf("%s", name);
	strcpy(new->name, name);
	printf("Enter age: ");
	scanf("%d",&new->age);										 
	
	new->next = NULL;											 
	
	return(new);											 
}



/* INPUTING A NODE INTO THE LIST*/
void Insert(person **head)
{
	person *new = malloc(sizeof(person));
	char name[10];
	
	printf("\nEnter name: ");
	scanf("%s", name);
	strcpy(new-> name, name);
	printf("Enter age: ");
	scanf("%d",&new->age);
	
	if (*head == NULL)
	{
		*head = new;
		new->next = NULL;
	}
	else
	{
		new->next = *head;
		*head = new;
	}
}


/* PRINT LIST*/
void Print(person **head)
{
	person *temp = *head;
	int i = 1;
	
	printf("\n\tLIST CONTENTS\n\n");
	if (temp == NULL) printf("List is empty!!");
	else
	{
		while (temp != NULL)
		{
			printf("No: %d\tNAME: %s\tAGE: %d\n", i, temp->name, temp->age);
			temp = temp->next;
			i++;
		}
	}
	printf("\n");
}



/* SORTED INPUT*/
void SortedInsert(person **head, person **o)
{
	person *temp = *head;
	person	*new = *o;
	
	if (*head == NULL)
	{
		*head = new;
		new->next = NULL;
	}
	else
	{
		if (new->age < temp->age)
		{
			new->next = temp;
			*head = new;
		}
		else
		{
			while (temp->next != NULL && temp->next->age < new->age)
			{
				temp = temp->next;
			}
			new->next = temp->next;
			temp->next = new;
		}	
	}
}

/* SORT THE LIST*/
void SortList(person **head)
{
	person *head1 = NULL;
	person *current = *head;
	person *next;
	
	if (current == NULL) printf("List empty! Nothing to sort!");
	else
	{
		while (current != NULL)
		{
			next = current->next;
			SortedInsert(&head1,&current);
		}
	}
	printf("SORTED LIST:\n");
	Print(&head1);
}



/* MAIN*/
int main (int argc, const char * argv[]) 
{
	person *head = NULL;
	int choice;
	
	do
	{
		Menu();
		scanf("%d",&choice);
		switch (choice)
		{
			case 1:
				Insert(&head);
				break;
			case 2: 
				Print(&head);
				break;
			case 3:
				Sortlist(&head);
				break;
			default:
				printf("\nWRONG CHOICE");
		}
	} while (choice != 0);
	
	return 0;
}

**tabstop** · 07-28-2009

Did you intend to do

Code:

*head = head1;

inside SortList?

**budala** · 07-28-2009

I don't think so. Because the way I see it, if the original list is empty (head == NULL) then there is nothing to sort, but if not the sorted list should start empty and then add nodes as they come along from the original list.

or did I get you wrong?

**roaan** · 07-28-2009

First of all see whether this assignment is okay or not.

[insert]

Code:

while (current != NULL)
		{
			next = current->next;
			SortedInsert(&head1,&current);
		}

I dont think this loop will ever terminate because you are checking the condition with current but incrementing next everytime. This is an infinite loop.

**budala** · 07-28-2009

thanks roaan for pointing the neverending loop to me. I also changed some other things which I colored and now it works beautifully

Code:

/* SORTED INPUT*/
void SortedInsert(person **head, person *o)
{
	person *temp = *head;
	person	*new = o;
	
	if (*head == NULL)
	{
		*head = new;
		new->next = NULL;
	}
	else
	{
		if (new->age < temp->age)
		{
			new->next = temp;
			*head = new;
		}
		else
		{
			while (temp->next != NULL && temp->next->age < new->age)
			{
				temp = temp->next;
			}
			new->next = temp->next;
			temp->next = new;
		}	
	}
}

/* SORT THE LIST*/
void SortList(person **head)
{
	person *head1 = NULL;
	person *current = *head;
	person *next;
	
	if (current == NULL) printf("List empty! Nothing to sort!");
	else
	{
		while (current != NULL)
		{
			next = current->next;
			SortedInsert(&head1,current);
			current = next;
		}
	}
	printf("SORTED LIST:\n");
	Print(&head1);
}

**tabstop** · 07-28-2009

Originally Posted by budala

thanks roaan for pointing the neverending loop to me. I also changed some other things which I colored and now it works beautifully

Code:

/* SORTED INPUT*/
void SortedInsert(person **head, person *o)
{
	person *temp = *head;
	person	*new = o;
	
	if (*head == NULL)
	{
		*head = new;
		new->next = NULL;
	}
	else
	{
		if (new->age < temp->age)
		{
			new->next = temp;
			*head = new;
		}
		else
		{
			while (temp->next != NULL && temp->next->age < new->age)
			{
				temp = temp->next;
			}
			new->next = temp->next;
			temp->next = new;
		}	
	}
}

/* SORT THE LIST*/
void SortList(person **head)
{
	person *head1 = NULL;
	person *current = *head;
	person *next;
	
	if (current == NULL) printf("List empty! Nothing to sort!");
	else
	{
		while (current != NULL)
		{
			next = current->next;
			SortedInsert(&head1,current);
			current = next;
		}
	}
	printf("SORTED LIST:\n");
	Print(&head1);
}

And if you call SortList, and then Print, what happens?

**ಠ_ಠ** · 07-28-2009

Code:

next = current->next;
SortedInsert(&head1,current);
current = next;

Code:

SortedInsert(&head1,current);
current = current->next;

**budala** · 07-29-2009

oops, I seem to have forgotten one line of code. it goes just before

Code:

Print(&head1);

and it states

Code:

*head = head1;

this is what I get after running the program, so I think it's ok.

Code:

[Session started at 2009-07-29 11:34:17 +0200.]

***	MENU	***

 1.) Insert
 2.) Print
 3.) Sort
 0.) EXIT
Choose ---------> 1

Enter name: anna
Enter age: 20

	LIST CONTENTS

No: 1	NAME: anna	AGE: 20


***	MENU	***

 1.) Insert
 2.) Print
 3.) Sort
 0.) EXIT
Choose ---------> 1

Enter name: lisa
Enter age: 30

	LIST CONTENTS

No: 1	NAME: lisa	AGE: 30
No: 2	NAME: anna	AGE: 20


***	MENU	***

 1.) Insert
 2.) Print
 3.) Sort
 0.) EXIT
Choose ---------> 1

Enter name: john
Enter age: 10

	LIST CONTENTS

No: 1	NAME: john	AGE: 10
No: 2	NAME: lisa	AGE: 30
No: 3	NAME: anna	AGE: 20


***	MENU	***

 1.) Insert
 2.) Print
 3.) Sort
 0.) EXIT
Choose ---------> 3
SORTED LIST:

	LIST CONTENTS

No: 1	NAME: john	AGE: 10
No: 2	NAME: anna	AGE: 20
No: 3	NAME: lisa	AGE: 30


***	MENU	***

 1.) Insert
 2.) Print
 3.) Sort
 0.) EXIT
Choose ---------> 1

Enter name: frank
Enter age: 40

	LIST CONTENTS

No: 1	NAME: frank	AGE: 40
No: 2	NAME: john	AGE: 10
No: 3	NAME: anna	AGE: 20
No: 4	NAME: lisa	AGE: 30


***	MENU	***

 1.) Insert
 2.) Print
 3.) Sort
 0.) EXIT
Choose ---------> 3
SORTED LIST:

	LIST CONTENTS

No: 1	NAME: john	AGE: 10
No: 2	NAME: anna	AGE: 20
No: 3	NAME: lisa	AGE: 30
No: 4	NAME: frank	AGE: 40


***	MENU	***

 1.) Insert
 2.) Print
 3.) Sort
 0.) EXIT
Choose --------->

**slingerland3g** · 07-29-2009

You do not have to use strcmp. Just scan straight into your struct variable:

Code:

/*No need */
   strcpy(new-> name, name)

/*Use this */
    scanf ("%s", new->name);

Thread: sorted linked list

Thread Tools

Search Thread

Display

sorted linked list

sorting a list with a twist :)

Similar Threads

C++ Linked list program need help !!!

seg fault for linked list in another linked list--help!!

Linked List

problem with structures and linked list

singly linked list

Tags for this Thread