sorted linked list

This is a discussion on sorted linked list within the C Programming forums, part of the General Programming Boards category; ok, a new problem. inserting a node in a sorted list. I just give the struct and the sortedinput function, ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    74

    sorted linked list

    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;
    		}	
    	}
    }

  2. #2
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305
    i think

    *head = new

    instead of

    temp = new

    should solve the problem

  3. #3
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    Unbelievable!!! Thanks man! (or woman) :-)

  4. #4
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305
    Its man :-)

  5. #5
    Registered User
    Join Date
    Apr 2009
    Posts
    74

    sorting a list with a twist :)

    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;
    }

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Did you intend to do
    Code:
    *head = head1;
    inside SortList?

  7. #7
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    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?

  8. #8
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305
    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.

  9. #9
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    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);
    }

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by budala View Post
    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?

  11. #11
    Banned ಠ_ಠ's Avatar
    Join Date
    Mar 2009
    Posts
    687
    Code:
    next = current->next;
    SortedInsert(&head1,current);
    current = next;
    Code:
    SortedInsert(&head1,current);
    current = current->next;
    ╔╗╔══╦╗
    ║║║╔╗║║
    ║╚╣╚╝║╚╗
    ╚═╩══╩═╝

  12. #12
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    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 --------->

  13. #13
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    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);

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 11:03 AM
  2. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21