linked list sorting

**ronenk** · 12-14-2004

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.

**quzah** · 12-14-2004

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.

**ronenk** · 12-14-2004

quzah, what does Node *instance get as a parameter?
also, please explain things more slowly for newbe's like me...

**quzah** · 12-14-2004

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.

**itsme86** · 12-14-2004

Originally Posted by ronenk

what does Node *instance get as a parameter?

It would get a Node *

**ronenk** · 12-14-2004

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?

**itsme86** · 12-14-2004

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?

**quzah** · 12-14-2004

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.

Thread: linked list sorting

Thread Tools

Search Thread

Display

linked list sorting

Similar Threads

single linked list to double linked list (help)

singly linked to doubly linked

Please Help - Problem with Compilers

Linked list with two class types within template.

singly linked list