AlphaSort for singly linked list

Discussion in 'C Programming' started by CR, Dec 15, 2003.

  1. CR

    CR Guest

    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
     
    CR, Dec 15, 2003
    #1
    1. Advertising

  2. CR

    CBFalconer Guest

    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 () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Dec 15, 2003
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Patrick McCourt

    Stack & Singly Linked List Data Structures

    Patrick McCourt, May 24, 2004, in forum: Java
    Replies:
    2
    Views:
    932
    Kenneth P. Turvey
    May 24, 2004
  2. HS-MOON
    Replies:
    4
    Views:
    609
    Method Man
    Sep 24, 2004
  3. RAJASEKHAR KONDABALA

    Reverse search in a singly-linked list

    RAJASEKHAR KONDABALA, Dec 24, 2003, in forum: C Programming
    Replies:
    20
    Views:
    5,828
    saadbinsaulat
    Feb 27, 2011
  4. Anando

    pruning a linear singly linked list

    Anando, Apr 23, 2006, in forum: C Programming
    Replies:
    59
    Views:
    1,233
    Richard Bos
    Apr 28, 2006
  5. Raj
    Replies:
    13
    Views:
    1,617
Loading...

Share This Page