Thread: linked lists problem

  1. #1
    Unregistered
    Guest

    linked lists problem

    I need help with my code:

    I have to read in a file into a linked list. It accepts 2 command line paramters, filename and field to sort. A file might look like this:

    1 Smith Jim 7.7
    3 Hypew Chris 8.6

    What i need help with:

    1. I need to print the file that is read in and print it off before it is sorted, but if i print it before it is sorted the file does not print in the order that it is originally in the file. I think it has something to with the initEmployee function. Can someone help me print the inital unsorted list.

    2. When i do sort the list and the name field is chosen, i need to find the name that is lowest in the alphabet numerically and place that on the top and leave the rest of the file in the same order eg

    unsorted:

    4 asd vvf 6.7
    5 ggh ggh 5.5
    7 ghkl fgksh 7.8
    6 edy dd 5.6

    sort list:

    6 edy dd 5.6
    4 asd vvf 6.7
    5 ggh ggh 5.5
    7 ghkl fgksh 7.8

    so i need to place the chosen item at the top and leave the rest of the file unchanged. My code bubble sorts the file.

    Can someone help me with these 2 issues


    here is my code:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define NAMESIZE 30
    #define NUMFIELD 4
    #define EMPNUM 1
    #define LNAME 2
    #define FNAME 3
    #define RATE 4
    
    struct employeeRecord
    {
       int employeeNum;
       char firstName[NAMESIZE], lastName[NAMESIZE];
       double hourRate;
       struct employeeRecord *nextEmp;
    };
    typedef struct employeeRecord employee;
    
    void sortEmployees(employee *startPtr, int field);
    void loadEmployees(char *filename, employee *start);
    void deleteEmployees(employee **startPtr);
    void initEmployees(employee **start);
    employee* createEmployee(int num, char *lastname, char *firstname, double rate);
    void printEmployees(employee *start);
    int decideToSwap(int field, employee *ptr2, employee *ptr3);
    
    int main(int argc, char *argv[])
    {
       int field;
       employee *start;
    
       /* Check command line arguments */
       if (argc != 3)
       {
          printf("\nERROR - Incorrect number of arguments\n");
          printf("Syntax : %s filename field\n", argv[0]);
          return 1;
       }
       if (strspn(argv[2], "0123456789") != strlen(argv[2]))
       {
          printf("\nERROR - Field must be an integer value in range 1 to %d\n", NUMFIELD);
          return 1;
       }
       field = atoi(argv[2]);
       if (field < 1 || field > NUMFIELD)
       {
          printf("\nERROR - Field must be an integer value in range 1 to %d\n", NUMFIELD);
          return 1;
       }
    
       /* run main program */
       initEmployees(&start);
       loadEmployees(argv[1], start); printEmployees (start);
       sortEmployees(start, field);
       printEmployees(start);
       deleteEmployees(&start);
    
       return 0;
    }
    
    void printEmployees(employee *start)
    {
       /* print the employee list */
    
       printf("\nNumber  Last Name            First Name           Rate\n");
       printf("-------+--------------------+--------------------+-----\n");
    
       start = start->nextEmp;
       while (start->employeeNum >= 0)
       {
          printf("%6d  %-20s %-20s %.2f\n", 
             start->employeeNum, start->lastName, 
             start->firstName, start->hourRate);
          start = start->nextEmp;
       }
       printf("\n");
    }
    
    void sortEmployees(employee *start, int field)
    {
       /* use bubble sort to sort the list in field order */
    
       int swaps;
       employee *ptr1, *ptr2, *ptr3;
    
       do
       {
          /* run bubble sort passes through list till no swaps done */
          ptr1 = start;
          ptr2 = start->nextEmp;
          ptr3 = ptr2->nextEmp;
          if (ptr3 == NULL) break;
          swaps = 0;
    
          while (ptr3->employeeNum >= 0)
          {
             /* run pass through list and do swaps if needed */
             if (decideToSwap(field, ptr2, ptr3))
             {
                ptr1->nextEmp = ptr3;
                ptr2->nextEmp = ptr3->nextEmp;
                ptr3->nextEmp = ptr2;
                ptr1 = ptr3;
                ptr3 = ptr2->nextEmp;
                swaps = 1;
             }
             else
             {
                ptr1 = ptr2;
                ptr2 = ptr3;
                ptr3 = ptr3->nextEmp;
             }
          } 
       }
       while (swaps);
    }
    
    int decideToSwap(int field, employee *ptr2, employee *ptr3)
    {
       /* decide if employees need to be swaped based upon given field */
    
       switch (field)
       {
          /* choose field to swap on */
          case EMPNUM:
             return (ptr2->employeeNum > ptr3->employeeNum);
          case LNAME:
             return (strcmp(ptr2->lastName, ptr3->lastName) > 0);
          case FNAME:
             return (strcmp(ptr2->firstName, ptr3->firstName) > 0);
          case RATE:
             return (ptr2->hourRate > ptr3->hourRate);
          default:
             printf("\nERROR - Invalid field in sorting\n");
             exit(1); 
       }
    }
    
    void loadEmployees(char *filename, employee *start)
    {
       /* load emplyee records and add to linked list */
    
       int num, status;
       char lastname[NAMESIZE], firstname[NAMESIZE];
       double rate;
       employee *temp;
       FILE *fin = fopen(filename, "r");
    
       if (fin == NULL)
       {
          printf("\nERROR - Unable to access %s\n", filename);
          exit(1);
       }
       
       /* read in records from file stream */
       while (!feof(fin))
       {
          status = fscanf(fin, "%d %s %s %lf", &num, lastname, firstname, &rate);
          if (status != 4)
          {
             /* faulty record, unless end of file */
             if (!feof(fin))
             {
                printf("\nERROR - Corrupted record in file\n");
                exit(1); 
             }
          }
          else
          {
             /* create employee and add to list */
             temp = createEmployee(num, lastname, firstname, rate);
             temp->nextEmp = start->nextEmp;
             start->nextEmp = temp;
          }
       }
     
       fclose(fin);
    }
    
    void deleteEmployees(employee **startPtr)
    {
       /* Delete all employee records in linked list */
       employee *temp;
    
       while (*startPtr != NULL)
       {
          temp = *startPtr;
          *startPtr = temp->nextEmp;
          free(temp);
       }
    }
    
    void initEmployees(employee **startPtr)
    {
       /* initialise the employee linked list with two dummy records */
    
       *startPtr = createEmployee(-1, " ", " ", 0.0);
       (*startPtr)->nextEmp = createEmployee(-2, " ", " ", 0.0);
    }
    
    employee* createEmployee(int num, char *lastname, char *firstname, double rate)
    {
       /* create and initialise new employee record */
    
       employee *temp = (employee*) malloc(sizeof(employee));
    
       if (temp == NULL)
       {
          printf("\nERROR - Unable to allocate memory for employee\n");
          exit(1);
       }
    
       strcpy(temp->lastName, lastname);
       strcpy(temp->firstName, firstname);
       temp->employeeNum = num;
       temp->hourRate = rate;
       temp->nextEmp = NULL;
    
       return temp;
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    The main problem seems to stem from the two 'guard' entries which initEmployees creates. These are not needed.

    An empty list is achieved simply by doing
    employee *start = NULL;

    The next step is the code which adds new elements to the list
    Code:
    employee* createEmployee ( employee* list, int num,
        char *lastname, char *firstname, double rate) {
        employee *temp = malloc( sizeof(employee) );
        if ( temp != NULL ) {
            temp->employeeNum = num;
            strcpy( temp->firstName, firstname );
            strcpy( temp->lastName, lastname );
            temp->hourRate = rate;
            temp->nextEmp = NULL;
            if ( list == NULL ) {
                /* list is currently empty, so the new node is the whole list */
                list = temp;
            } else {
                /* seek the end of the list and append the new node */
                employee *tail = head;
                while ( tail->nextEmp != NULL ) tail = tail->nextEmp;
                tail->nextEmp = temp;
            }
        }
        return list;
    }
    Basically, you pass this function the current list, and it returns the modified list.

    After that, the same loop for processing list elements can be used all over, without worrying about guard nodes
    Code:
    node = start;
    while ( node != NULL ) {
        /* do something with node */
        node = node->next;
    }
    Convince yourself that this does the right thing with an empty list (start==NULL), and a non-empty list (start != NULL).

    You will need to be extra careful in sortEmployees, to take care of the case when you swap the first element of the list.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question On Linked Lists
    By Zildjian in forum C Programming
    Replies: 8
    Last Post: 10-23-2003, 11:57 AM
  2. Linked Lists Integer addition ? HELP Please??
    By green_eel in forum C Programming
    Replies: 3
    Last Post: 03-12-2003, 04:36 PM
  3. Linked lists
    By sballew in forum C Programming
    Replies: 6
    Last Post: 10-24-2001, 08:52 PM
  4. I need some help on my linked lists app
    By valar_king in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2001, 08:36 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM