By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,302 Members | 1,409 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,302 IT Pros & Developers. It's quick & easy.

AlphaSort for singly linked list

P: n/a
CR
I'm trying to alphabetically sort a linear linked list by both last name and
first name data portions. I can't figure out how to do this; I should be
able to do it no problem but I am really struggling with it - could someone
help me implement a simple algorithm well suited for my code implementation.
Any help would be greatly appreciated!

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

#define MAX_FIRST_CHARS 11
#define MAX_LAST_CHARS 16
#define HIREFILE Hirefile.dat
#define PAYFILE Payfile.dat
#define FIREFILE firefile.dat

typedef char string_f[MAX_FIRST_CHARS];
typedef char string_l[MAX_LAST_CHARS];

typedef struct // file data structure
{
string_f firstName;
string_l lastName;
char gender;
char rate;
int tenure;
float salary;
int rec;
} el_t;

//typedef struct node node_t;
typedef struct node *pointer_t;

struct node
{
el_t el; // data portion
pointer_t next;
};

typedef struct
{
pointer_t head;
pointer_t cur;
} list, target;

pointer_t MakeNode(el_t e);
void InitList(list *l_ptr);
FILE *InitFile(FILE *infile, const char *mode);
void ReadRec(FILE *infile_ptr, el_t *e_ptr, int *rec);
void InsertFirst(list *l_ptr, el_t e);
void InsertAfter(list *l_ptr, el_t e);
list AlphaSort(list *unsorted, list *sorted);
void DeleteAfter(list *l_ptr);
void Advance(list *l_ptr);
void ViewRec(list l_ptr);
void NodeError(void);

/* INITLIST */
void InitList(list *l_ptr)
{// InitList(&list);
l_ptr->head=NULL;
l_ptr->cur=l_ptr->head;
}

/* MAKENODE */
pointer_t MakeNode(el_t e)
{
pointer_t P = calloc(1, sizeof(struct node));
if(P==NULL)
{
printf("Error making node\n");
exit(1);
}else
{
P->el=e;
P->next=NULL;
}
return(P);
}
/* DELNODE */

/* INSERTFIRST */
void InsertFirst(list *l_ptr, el_t e)
{
pointer_t target=MakeNode(e);

target->next=l_ptr->head;
l_ptr->head=target;
}

/* INSERTAFTER */
void InsertAfter(list *l_ptr, el_t e)
{
pointer_t target;
target=MakeNode(e);
if(l_ptr->cur==NULL)
NodeError();
else
{
target->next=(l_ptr->cur)->next;
(l_ptr->cur)->next=target;
}
}
void DeleteAfter(list *l_ptr)
{
pointer_t tmp;

if(l_ptr->cur==NULL || (l_ptr->cur)->next==NULL)
NodeError();
else
{
tmp=(l_ptr->cur)->next;
(l_ptr->cur)->next=tmp->next;
free(tmp);
}
}

/* ADVANCE */
void Advance(list *l_ptr)
{
if(l_ptr->cur==NULL)
NodeError();
else
l_ptr->cur=(l_ptr->cur)->next;
}
/* NODEERROR */
void NodeError(void)
{
printf("ERROR: No node\n");
exit(1);
}
/* READREC */
void ReadRec(FILE *infile_ptr, el_t *e_ptr, int *rec)
{
char space;
char pause;

if(fscanf( infile_ptr, "%s %s %c %d %c %f", (e_ptr->firstName),
(e_ptr->lastName), &(e_ptr->gender), &(e_ptr->tenure), &(e_ptr->rate),
&(e_ptr->salary)))
{
e_ptr->rec=(++*rec);
//printf("%s %s %c %d %c %.2f\n", e_ptr->firstName,
e_ptr->lastName, e_ptr->gender, e_ptr->tenure, e_ptr->rate, e_ptr->salary);
}
/* end of while construction */
//scanf("%c", &pause);
}

void ViewRec(list L)
{
el_t e;

L.cur=L.head;

while(L.cur != NULL)
{
e = (L.cur)->el;
printf("|*****************************|\n");
printf("|RECORD NUM: %-17d|\n", L.cur->el.rec);
printf("|First Name: %-17s|\n", L.cur->el.firstName);
printf("|Last Name: %-17s|\n", L.cur->el.lastName);
printf("|Gender: %-17c|\n", L.cur->el.gender);
printf("|Tenure: %-17d|\n", L.cur->el.tenure);
printf("|Rate: %-17c|\n", L.cur->el.rate);
printf("|Salary: %-17.2f|\n", L.cur->el.salary);
printf("|*****************************|\n");
//printf("%s %s %c %d %c %.2f\n", L.cur->el.firstName,
L.cur->el.lastName, L.cur->el.gender, L.cur->el.tenure, L.cur->el.rate,
L.cur->el.salary);
Advance(&L);
}
}

/* CREATELIST */
void CreateList(list *l_ptr)
{
FILE *infile_ptr;
el_t e;
int i=0, rec=0;

InitList(l_ptr);
infile_ptr=InitFile("Payfile.dat", "r");
ReadRec(infile_ptr, &e, &rec);
InsertFirst(l_ptr, e);
l_ptr->cur=l_ptr->head;
while(!feof(infile_ptr))
{
++i;
ReadRec(infile_ptr, &e, &rec);
InsertAfter(l_ptr, e);
Advance(l_ptr);

}
fclose(infile_ptr);
}

/* VIEWLIST */
/* INITFILE */
FILE *InitFile(FILE *infile, const char *mode)
{
FILE *infile_ptr;

infile_ptr=fopen(infile, mode);

if(infile_ptr==NULL)
{
printf("ERROR: Cannot open file %s!\n", infile);
exit(1);
}
return infile_ptr;
}
void menu(void)
{
printf("Please make a numeric selection: \n");
printf("(1) View node data.\n");
printf("(2) Alphabetically sort (Last Name)\n");
printf("(3) Output Women on Payroll.\n");
printf("(4) Output 5 yr Weekly Employees.\n");
printf("(5) Give Raise.\n");
printf("(6) Who has had a Raise?\n");
printf("(7) Output number of Employees.\n");
printf("(8) Salaries.\n");
printf("(9) Update new employees.\n");
printf("(10) Remove fired employees.\n");
printf("(11) Sort list by name output salary.\n");
printf("Enter 0 to exit.\n");
}

void main(void)
{
el_t e;
list newlist;
list listsort;
list *unsorted;
list *sorted;

char pause;
int c_menu;

InitList(&listsort);
CreateList(&newlist);
/* not sure if I should use this idea
unsorted=&newlist;
sorted=&listsort;
*/
while(c_menu != 0)
{
menu();
scanf("%d", &c_menu);

switch(c_menu)
{
case 1 : {ViewRec(newlist); break;}
/* case 2 : {AlphaSort(unsorted, sorted); break;} */
default: printf("Enter a valid numeric choice!\n");
}
}
scanf("%c", &pause);
}

file data is in the format: first last gender tenure rate
salary
Nov 14 '05 #1
Share this Question
Share on Google+
1 Reply


P: n/a
CR wrote:

I'm trying to alphabetically sort a linear linked list by both
last name and first name data portions. I can't figure out how
to do this; I should be able to do it no problem but I am really
struggling with it - could someone help me implement a simple
algorithm well suited for my code implementation. Any help would
be greatly appreciated!

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


I am not going through such long code, especially when it contains
such non-standardisms as conio.h (which doesn't exist in standard
C) and "void main(void)". You should cut such examples down to a
minimum compilable module.

At any rate you can find, and study, the sorting of linear linked
lists by different criteria in wdfreq.c, which is found as a usage
example in hashlib.zip, which in turn may be found at:

<http://cbfalconer.home.att.net/download/>

You will find the only difference between the sorts is the
comparison function supplied. The example deliberately does
multiple sorts in order to illustrate stability of the mergesort
process.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #2

This discussion thread is closed

Replies have been disabled for this discussion.