linked list sorting

This is a discussion on linked list sorting within the C Programming forums, part of the General Programming Boards category; My task is to write a code which builds a list of candidates entered from command line & sort them ...

  1. #1
    Registered User
    Join Date
    Jun 2004
    Posts
    123

    linked list sorting

    My task is to write a code which builds a list of candidates entered from command line & sort them alphabetically on the fly with linked list.
    The problem is if I put in the final loop
    if (CandidatesList)
    the program does not ever get to execute the function InsertAfter. It is InsertFirst all the way.
    on the other hand if I put
    if (CandidatesList->Next==NULL)
    The first value in list get the InsertFirst, then all following values are in the order of input entered to the list- last on in list- first entered & not alphabetically manner.


    Code:
    #include <stdio.h>
    #include <malloc.h>
    #include <string.h>
    
    typedef struct{
    	char FName[15];
    	char LName[20];
    	int ID;
    	int LearnYrs;
    	int ExperienceYrs;
    	int TheoreticalGrd;
    	int PracticalGrd;
    }CandidateDetails;
    typedef CandidateDetails Candidate;
    Candidate CurrentCandidate;
    
    struct LinkedList{
    	Candidate Data;
    	struct LinkedList *Next;
    };
    
    typedef struct LinkedList Node;
    typedef Node *PtrToNode;
    
    PtrToNode InitList()
    {
    	PtrToNode P;
    	P = (PtrToNode) malloc(sizeof(Node));
    	if (P == NULL)
    		 puts ("Out of memory! 1");
    	P->Next = NULL;
    	return P;
    }
    
    int IsEmptyList(PtrToNode list)
    {
    	return (list->Next == NULL);
    }
    
    PtrToNode getnode (void)
    {
    	PtrToNode p;
    	p=(PtrToNode)malloc(sizeof (struct LinkedList));
    	return p;
    }
    
    void InsertFirst(PtrToNode *list, Candidate name)
    {
    	PtrToNode TmpCell;
    	TmpCell=getnode();
    	if (TmpCell)
    	{
    		TmpCell->Data = name;
    		TmpCell->Next = *list;
    		*list = TmpCell;
    	}
    	else
    	{
    	 puts ("Out of memory! 2");
    	}
    }
    
    void InsertAfter(PtrToNode list, Candidate name)
    {
    	PtrToNode TmpCell;
    	if (list)
    	{
    		TmpCell=getnode();
    			if (TmpCell)
    			{
    				TmpCell->Data=name;
    				TmpCell->Next = list->Next;
    				list->Next=TmpCell;
    				list=TmpCell;
    			}
    		
    			else 
    			{
    				puts ("Error in InsertAfter");
    			}
    	}
    		else
    		{
    			puts ("Out of memory! 3");
    		}
    }
    
    
    			
    void PrintList (PtrToNode list)
    {
    	while (list)
    		{
    			printf ("%s %s", list->Data.FName, list->Data.LName);
    			list= list->Next;
    		}
    	printf ("\n");
    }
    
    
    int main (void)
    {
    
    	int i=0;
    	PtrToNode CandidatesList, p, q;
    	CandidatesList=InitList();
    	CurrentCandidate.ID=1;
    	
    		while (CurrentCandidate.ID !=0)
    		{
    			puts ("\nAll of the following details has to be of the same candidate");
    			puts ("\nPlease enter an ID number of one of the candidate");
    			flushall();
    			scanf ("%d", &CurrentCandidate.ID);
    			if (CurrentCandidate.ID==0)
    				break;
    			puts ("\nPlease enter the first name of the candidate");
    			flushall();
    			fgets (CurrentCandidate.FName, 15, stdin);
    			puts ("\nPlease enter the last name of the candidate");
    			flushall();
    			fgets (CurrentCandidate.LName, 20, stdin);
    
    				if (IsEmptyList (CandidatesList))
    		
    				   InsertFirst(&CandidatesList, CurrentCandidate);
    
    				else
    
    					{
    						p=CandidatesList;
    						while (p && strcmp(p->Data.LName, 
    						CurrentCandidate.LName)<0)
    							{
    								q=p;
    								p=p->Next;
    							 }
    					  InsertAfter(CandidatesList, CurrentCandidate);
    		   }
    
    
    			PrintList (CandidatesList);
    		}
    }
    help will be highly appreciated!

    TIA.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    typedef struct{
    	char FName[15];
    	char LName[20];
    	int ID;
    	int LearnYrs;
    	int ExperienceYrs;
    	int TheoreticalGrd;
    	int PracticalGrd;
    }CandidateDetails;
    typedef CandidateDetails Candidate;
    Just one question. Why?
    Actually two. Why do you have more than one insert function?
    Ok, three. Why don't you just use one function to insert whever you need to?
    Code:
    void insert( Node **list, Node *instance )
    {
        ptr = *list;
        if ptr->something comes after instance->something
            add pointer to the end of instance and make the list start now be instance
        else
            while ptr->next exists, and ptr->next->something it comes after instance->something
                move through the list
            insert instance after ptr but before ptr->next, if there is in fact a ptr->next
    }
    I'll leave that as an exersize to the reader, but that's ideally how you should be doing your insertion.

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    quzah, what does Node *instance get as a parameter?
    also, please explain things more slowly for newbe's like me...

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    1) You are typedef-ing your structure as two different things. There's no point in the second one. So just move that name, if you prefer it better, to where you have the first name:
    Code:
    typedef struct{
    	char FName[15];
    	char LName[20];
    	int ID;
    	int LearnYrs;
    	int ExperienceYrs;
    	int TheoreticalGrd;
    	int PracticalGrd;
    } Candidate;
    /* and delete the line that was here */
    2) "Node" is the generic term for an element in a list. In this case, "Node" would be a just like what you have it as, except I see that you're one of those wierd people who insist on typedef-ing pointers to their own type. So in your case you'd use:
    Code:
    void insert( PrtToNode *list, PtrToNode nodeToInsertIntoList )
    {
        ...stuff...
    }
    Given a list and a node to insert, you'd pass the address of the list itself, and the node to insert:
    Code:
    PtrToNode theWholeList;
    PtrToNode insertMe;
    
    insert( &theWholeList, insertMe );

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,164
    Quote Originally Posted by ronenk
    what does Node *instance get as a parameter?
    It would get a Node *
    If you understand what you're doing, you're not learning anything.

  6. #6
    Registered User
    Join Date
    Jun 2004
    Posts
    123
    so far- fair enough.

    Code:
    void insert( Node **list, Node *instance )
    {
    ptr = *list;
    if ptr->something comes after instance->something
    add pointer to the end of instance and make the list start now be instance
    else
    while ptr->next exists, and ptr->next->something it comes after instance->something
    move through the list
    insert instance after ptr but before ptr->next, if there is in fact a ptr->next
    }
    could you please pass over the function & its components?

  7. #7
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,164
    That pseudocode creates the list already sorted. So say you had a linked list made out of a simple struct like:
    Code:
    struct foo
    {
      int num;
      struct foo *next;
    };
    You could do something like this:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct foo
    {
      int num;
      struct foo *next;
    } FOO;
    
    FOO *new_node(void)
    {
      return malloc(sizeof(FOO));
    }
    
    void insert_node(FOO **list, FOO *node)
    {
      FOO *l, *lprev = NULL;
    
      for(l = *list;l;l = l->next)
      {
        if(l->num > node->num)
          break;
        lprev = l;
      }
    
      // prev will be NULL if the node should be inserted at the head of the list
      if(lprev)
      {
        node->next = lprev->next;
        lprev->next = node;
      }
      else
      {  // Make node the new head of the list
        node->next = *list;
        *list = node;
      }
    }
    
    int main(void)
    {
      int nums[10] = { 73, 24, 86, 1, 19, 92, 79, 36, 67, 64 };
      int i;
      FOO *list = NULL, *l;
    
      for(i = 0;i < 10;++i)
      {
        l = new_node();
        l->num = nums[i];
        insert_node(&list, l);
      }
    
      for(l = list;l;l = l->next)
        printf("%d\n", l->num);
    
      return 0;
    }
    itsme@dreams:~/C$ ./simplist
    1
    19
    24
    36
    64
    67
    73
    79
    86
    92
    You see how it inserts it already sorted?
    If you understand what you're doing, you're not learning anything.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by ronenk
    so far- fair enough.

    could you please pass over the function & its components?
    *smashes head on desk*
    *looks at calendar*
    *looks at next post*
    *smashes head on desk*
    *looks again at calendar*
    *Walks off muttering something about fish and fishing...*

    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 06:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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