Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > AlphaSort for singly linked list

Reply
Thread Tools

AlphaSort for singly linked list

 
 
CR
Guest
Posts: n/a
 
      12-15-2003
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("( 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


 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      12-15-2003
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 ((E-Mail Removed)) ((E-Mail Removed))
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reverse search in a singly-linked list RAJASEKHAR KONDABALA C Programming 20 02-27-2011 12:53 PM
pruning a linear singly linked list Anando C Programming 59 04-28-2006 11:12 AM
Delete node from singly linked list when header is not known Raj C++ 13 02-02-2006 06:21 AM
About Ordered singly linked list.. HS-MOON C++ 4 09-24-2004 02:26 PM
Stack & Singly Linked List Data Structures Patrick McCourt Java 2 05-24-2004 10:55 PM



Advertisments