Sorting Linked Lists

**DKING89** · 04-08-2008

I am currently enrolled in a C/C++ course at my given univeristy and was asked to program a linked list and sort it alphabetically and numerically in the following priority: the last name of an employee, the first name of an employee, the id number of an employee, and finally, the classification of an employee.

I have been successful with sorting by the last name of the employee, yet as I try to sort by first name, then id number, then classification, I received memory leaks and segmentation faults. After spending numerous hours on the issue, I must ask for help.

Selected Input:

Code:

* HIRE
Jeffries  Tom   449   Boss
Abrams   Melice  308 Manager
Jeffries   Tyrone   448    SalesPerson
Tyson  Kevin 483   Clerk
Edwards    Jaiki 397   SalesPerson
Edwards  Jaiki 392   SalesPerson
O'Neill   Mark 503  Clerk
* INITIAL SALARIES
397   4093.04
308  12019.77
503 2094.67
449   80493.97
483  13486.28
392   10493.02
448    14296.08
* PROMOTIONS
483   284.06   SalesPerson
503    194.92 SalesPerson
397 302.49     Manager
* TRANSFERS
449
397
* HIRE
Abernathy  John   521 Manager
Abernathy   John 302   SalesPerson
* INITIAL SALARIES
521  12840.62
302   2003.08
* END OF DATA

Constants:

Code:

//Included Libraries
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//Symbolic Constants
#define ARGSZ 2
#define ONE 1
#define SALARYARRYSZ 2
#define ZEROD 0.0
#define ZEROI 0

//Memory Structures
struct employeeNode
{
	char *firstName;
	char *lastName;
	int id;
	char *employeeClass;
	double salary[SALARYARRYSZ];
	struct employeeNode *nextNode;
};

//Function Prototypes
void cmdLineTest(int, char *[]);
void dataProcess(char [], char *, char *, char *, char *, char [], char [], char [], int *);
void fileOpen(FILE **, char *[]);
void insertNode(FILE *, struct employeeNode **, char []);
void memAlloc(char [], char [], char [], int , struct employeeNode **);
void memStore(char [], char [], char [], int , struct employeeNode **);
void printList(struct employeeNode *);
void read(FILE *, char []);
void readInitSal(FILE *, struct employeeNode **, char []);
void readPromotions(FILE *, struct employeeNode **, char []);
void readTransfers(FILE *, struct employeeNode **, char[]);

Driver:

Code:

#include "hw3Constants.c"

int main(int argc, char *argv[])
{
	char selection, readData[50];
	struct employeeNode *startPtr = NULL;
	FILE *inFile = NULL;
	printf("\n&#37;s %d %s %s %s %s %s %s%c\n\n",	"This is line number", __LINE__,
										"of the file", __FILE__,
										"which was\n compiled on", __DATE__,
										"at time", __TIME__, '.');
	cmdLineTest(argc, argv);
	fileOpen(&inFile, argv);
	read(inFile, readData);
	while (!feof(inFile))
	{
		if (readData[0] == '*')
		{
			selection = readData[2];
			switch (selection)
			{
				case 'H':   insertNode(inFile, &startPtr, readData);
							break;
				case 'I':	readInitSal(inFile, &startPtr, readData);
							break;
				case 'P':	readPromotions(inFile, &startPtr, readData);
							break;
				case 'T':	readTransfers(inFile, &startPtr, readData);
							break;
				default:	break;
			}
		}
	}
	printList(startPtr);
	return;
}

void cmdLineTest(int argc, char *argv[])
{
	if (argc == ARGSZ)
		printf("The argument supplied is %s\n\n", argv[ARGSZ-ONE]);
	else
	{
			if (argc >2)
			{
				printf("Too many arguments supplied. Exiting Program.\n");
				exit(1);
			}
			else
			{
				printf("One argument expected. Exiting Program\n");
				exit(1);
			}
	}
	return;
}


void dataProcess(char data[], char *fName, char *lName, char *id, char *cl, char tempLName[], char tempFName[], char tempClass[], int *tempID)
{
	lName = strtok(data, " ");	
	fName = strtok(NULL, " ");
	id = strtok(NULL, " ");
	cl = strtok(NULL, " ");
	strcpy(tempLName, lName);
	strcpy(tempFName, fName);
	strcpy(tempClass, cl);
	*tempID = atoi(id);
	return;
}

void fileOpen(FILE **inFilePtr, char *argv[])
{
	if(( *inFilePtr = fopen(argv[ARGSZ-ONE], "r")) == NULL)
	{
		printf("File Open Failed. EXITING PROGRAM.\n");
		exit(1);
	}
	return;	
}

void insertNode(FILE *inFile, struct employeeNode **startPtr, char readData[])
{
	
	int x=0, tempID=0;
	char *firstName=NULL, *lastName=NULL, *id=NULL, *cl=NULL;
	char tempClass[20], tempLName[20], tempFName[20];
	struct employeeNode *newPtr = NULL;
	struct employeeNode *previousPtr = NULL;
	struct employeeNode *currentPtr = NULL;	
	for(x=0; x<50; x++)
	{
		readData[x] = '\0';	
	}
	fgets(readData, 50, inFile);
	do
	{
			dataProcess(readData, firstName, lastName, id, cl, tempLName, tempFName, tempClass, &tempID);
			memAlloc(tempLName, tempFName, tempClass, tempID, &newPtr);
			if(newPtr != NULL)
			{
				memStore(tempLName, tempFName, tempClass, tempID, &newPtr);
				previousPtr = NULL;
				currentPtr = *startPtr;
				while( (currentPtr != NULL) && (strcmp(tempLName, currentPtr->lastName) > 0) )
				{
						previousPtr = currentPtr;
						currentPtr = currentPtr->nextNode;
				}
				if( (previousPtr == NULL) )
				{
					newPtr->nextNode = *startPtr;
					*startPtr = newPtr;
				}
				else
				{
					previousPtr->nextNode = newPtr;
					newPtr->nextNode = currentPtr;
				}
			}
			else
			{
				printf("No Memory Available.\n");
			}
		fgets(readData, 50, inFile);
	}while(readData[0] != '*');
	return;
}

void memAlloc(char lName[], char fName[], char eClass[], int tempID, struct employeeNode **newPtr)
{
	int firstNum, lastNum, classNum;
	*newPtr = calloc(ONE, sizeof(struct employeeNode));
	if (newPtr != NULL)
	{
		firstNum = strlen(fName);
		lastNum = strlen(lName);
		classNum = strlen(eClass);	
		lName[lastNum] = '\0';
		fName[firstNum] = '\0';
		eClass[classNum] = '\0';
		(**newPtr).firstName = calloc((firstNum+ONE), sizeof(char));
		(**newPtr).lastName = calloc((lastNum+ONE), sizeof(char));
		(**newPtr).employeeClass = calloc((classNum+ONE), sizeof(char));
	}
	else
	{
		printf("No Memory Available. Exiting Program");
		exit(1);	
	}
	return;	
}

void memStore(char lName[], char fName[], char eClass[], int id, struct employeeNode **newPtr)
{
	int x;
	strcpy( (**newPtr).firstName, fName);
	strcpy( (**newPtr).lastName, lName);
	for(x=0; x<50; x++)
	{
		if (eClass[x] == '\n')
		{
			eClass[x] = '\0';	
		}
	}
	strcpy( (**newPtr).employeeClass, eClass);
	(**newPtr).id = id;
	(**newPtr).nextNode = NULL;
	return;
}

void printList(struct employeeNode *currentPtr)
{
	int numEmployee=1;
	if (currentPtr == NULL)
	{
		printf("List is empty.\n\n");
	}
	else
	{
		printf("The Employees Are:\n");
		printf("\n"); 
		printf("\n");
		printf("----------------------------------------------------------------------------------------\n");
		while (currentPtr != NULL)
		{
			printf("%3d %X  %-10s%-10s %3d %-15s$%9.2f $%9.2f%13X\n", 
													numEmployee,
													currentPtr,
													currentPtr->firstName,
													currentPtr->lastName,
													currentPtr->id,
													currentPtr->employeeClass,
													currentPtr->salary[0],
													currentPtr->salary[1],
													currentPtr->nextNode);
			currentPtr = currentPtr->nextNode;
			numEmployee+=1;
		}
		printf("NULL\n\n");
	}
	return;
}

void read(FILE *inFile, char readData[50])
{
	fgets(readData, 50, inFile);
	return;
}

void readInitSal(FILE *inFile, struct employeeNode **searchPtr, char readData[])
{
	int idTrue=0, x=0;
	double salaryTrue=0.0;
	char *idStr = NULL, *salaryString = NULL;
	struct employeeNode *currentPtr;
	fgets(readData, 50, inFile);
	do
	{
		idStr = strtok(readData, " ");
		salaryString = strtok(NULL, " ");
		idTrue = atoi(idStr);
		salaryTrue = atof(salaryString);
		fgets(readData, 50, inFile);
		
		currentPtr = *searchPtr;
		while (currentPtr != NULL)
		{
			if ( (currentPtr->id) == idTrue)
			{
				currentPtr->salary[0] = salaryTrue;	
			}
			currentPtr = currentPtr->nextNode;
		}
	}while(readData[0] != '*');
	return;
}

void readPromotions(FILE *inFile, struct employeeNode **searchPtr, char readData[])
{
	int idTrue=0, x=0;
	double pSalaryTrue=0.00;
	char pClass[20]={'\0'}, *idStr=NULL, *pSalaryString=NULL, *pClassString=NULL;
	struct employeeNode *currentPtr;
	fgets(readData, 50, inFile);
	do
	{
		idStr = strtok(readData, " ");
		pSalaryString = strtok(NULL, " ");
		pClassString = strtok(NULL, " ");
		idTrue = atoi(idStr);
		pSalaryTrue = atof(pSalaryString);
		strcpy(pClass, pClassString);
		for (x=0; x<20; x++)
		{
			if (pClass[x] == '\n')
				pClass[x] = '\0';
		}
		currentPtr = *searchPtr;
		while (currentPtr != NULL)
		{
			if ((currentPtr->id) == idTrue)
			{
				currentPtr->salary[1] = pSalaryTrue;
				strcpy((currentPtr->employeeClass), pClass);
			}
			currentPtr = currentPtr->nextNode;
		}
		fgets(readData, 50, inFile);
	}while(readData[0] != '*');
	return;
}

void readTransfers(FILE *inFile, struct employeeNode **startPtr, char readData[])
{
	char idStr[10];
	int idTrue;	
	struct employeeNode *previousPtr = NULL;
	struct employeeNode *currentPtr = NULL;
	struct employeeNode *tempPtr = NULL;
	fgets(readData, 50, inFile);
	do
	{
		strcpy(idStr, readData);
		idTrue = atoi(idStr);
		if (idTrue == (*startPtr)->id)
		{
			tempPtr = *startPtr;
			*startPtr = (*startPtr)->nextNode;
			free(tempPtr);
			tempPtr = NULL;
		}
		else
		{
			previousPtr = *startPtr;
			currentPtr = (*startPtr)->nextNode;
			
			while ((currentPtr != NULL) && (currentPtr->id != idTrue))
			{
				previousPtr = currentPtr;
				currentPtr = currentPtr->nextNode;
			}
			
			if (currentPtr != NULL)
			{
				tempPtr = currentPtr;
				previousPtr->nextNode = currentPtr->nextNode;
				free(tempPtr);
			}
		}
		fgets(readData, 50, inFile);
	}while(readData[0] != '*');
	return;
}

Ouput is as Follows after Sorting By Last Name:

Code:

The Employees Are:


----------------------------------------------------------------------------------------
  1 11DF6250  John      Abernathy  302 SalesPerson    $  2003.08 $     0.00     11DF64D0
  2 11DF64D0  John      Abernathy  521 Manager        $ 12840.62 $     0.00     11DF62F0
  3 11DF62F0  Melice    Abrams     308 Manager        $ 12019.77 $     0.00     11DF6570
  4 11DF6570  Jaiki     Edwards    392 SalesPerson    $ 10493.02 $     0.00     11DF6390
  5 11DF6390  Tyrone    Jeffries   448 SalesPerson    $ 14296.08 $     0.00     11DF6610
  6 11DF6610  Mark      O'Neill    503 SalesPerson    $  2094.67 $   194.92     11DF6430
  7 11DF6430  Kevin     Tyson      483 SalesPerson    $ 13486.28 $   284.06            0
NULL

Thread: Sorting Linked Lists

Thread Tools

Search Thread

Display

Threaded View

Sorting Linked Lists

Similar Threads

sorting in linked lists

Linked Lists 101

Sorting Linked Lists (code not concept)

need help w/ linked lists

doubly linked lists