Thread: Need help with linked list sorting function

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    3

    Need help with linked list sorting function

    I'm at the limit of my sanity. The program I'm writing accepts the name, ssn, and other bits of information from a regular txt file, inserts it all into structs, and has (or would later have had) the ability to accept more info from the user.

    That's the background, and all of it works. The only issue I'm having is with why in holy hell my sorting function won't work.

    I've looked at other ways to sort link lists in C, but they all use a type of linked list different from the kind my instructor taught us. Mine is a kind that adds entries into the beginning of the list instead of the end. If you want to know exactly how, the addToList function has the details.

    My sorting uses three what-I-call "platforms" to move around the nodes connecting each struct to one another. I realize this way is immensely confusing, yet I am (or was) rather confident that the concept should have worked.

    If it's any help, through some testing using a printf, I found that my function seems to go into an infinite loop in the while control structure (not the do while), but I can't see why. Wouldn't my "platform" reach the NULL at SOME point?

    Here's the entire code, the function in question is at the bottom in bold, although anything directly related to it is bold as well:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    struct xrac {
        char name[16];
        char ssn[12];
        char gend;
        float assign;
        float quiz;
        float parti;
        float midT;
        float final;
        char grade;
        struct xrac * next;
    }temp;
    
    struct xrac * addToList (struct xrac * first, struct xrac add);
    void calcNumGrades (struct xrac * first);
    void printAllList (struct xrac * first);
    void printLList (struct xrac * first);
    void printAList (struct xrac * first);
    void printFList (struct xrac * first);
    struct xrac * sortList (struct xrac * first);
    
    void main ()
    {
        char cmd; int numGrade;
        FILE * infile = fopen("scores.txt", "r");
        struct xrac * first = NULL; struct xrac * plat1; struct xrac * plat2;
    
        while ( fscanf(infile, "%s %s %c %f %f %f %f %f", temp.name,
        temp.ssn, &temp.gend, &temp.assign, &temp.quiz, &temp.parti,
        &temp.midT, &temp.final ) != EOF){
            temp.name[15] = '\0';
            temp.ssn[11] = '\0';
            temp.grade = 'N';
    
            /*Link-List Test Prt1/two
            printf("Temp: %s %s %c %4.2f %4.2f %4.2f %4.2f %4.2f\n", temp.name,
            temp.ssn, temp.gend, temp.assign, temp.quiz, temp.parti, temp.midT, temp.final);*/
    
            first = addToList (first, temp);
            calcNumGrades (first);
    
            /*LinkList Test Prt2/two
            printf("Link-List: %s %s %c %4.2f %4.2f %4.2f %4.2f %4.2f\n", (*first).name,
            (*first).ssn, (*first).gend, (*first).assign, (*first).quiz,
            (*first).parti, (*first).midT, (*first).final);*/
        }
    
        printf("Menu: \n");
        printf("1. Print list of students.\n2. Print list of students with letter grade.\n");
        printf("3. Print list of those who made an A grade.\n4. Print list of those who made an F grade.\n");
        printf("5. Print list of students sorted by name.\n6. Add student to the class list.\n");
        printf("7. Delete student from class list.\n8. Show Menu again.\nX. Quit.\n");
    
        while ((cmd != 'X') && (cmd != 'x')){
            fflush(stdin);
            printf("\nEnter number: "); scanf("%c", &cmd);
            if(cmd == '1')
            {
                printf("\nAll students: \n");
                printAllList (first);
                printf("\n");
            }
            else if(cmd == '2')
            {
                printf("\nStudents with letter grade: \n");
                printLList (first);
                printf("\n");
            }
            else if(cmd == '3')
            {
                printf("\nStudents with an A grade: \n");
                printAList (first);
                printf("\n");
            }
            else if(cmd == '4')
            {
                printf("\nStudents with an F grade: \n");
                printFList (first);
                printf("\n");
            }
            else if(cmd == '5')
            {
               printf("\nStudents in alphabetical order: \n");
                first = sortList (first);
                printAllList (first);
                printf("\n");
            }
            else if(cmd == '6')
            {
                printf("\nEnter student's name, SSN, and grades. ");
                printf("\nIf student has no grades, enter 0's in their place: ");
            }
            else if(cmd == '7')
            {
                printf("\nEnter student's name: ");
            }
            else if(cmd == '8')
            {
                printf("Menu: \n");
                printf("1. Print list of students.\n2. Print list of students with letter grade.\n");
                printf("3. Print list of those who made an A grade.\n4. Print list of those who made an F grade.\n");
                printf("5. Print list of students sorted by name.\n6. Add student to the class list.\n");
                printf("7. Delete student from class list.\n8. Show Menu.\nX. Quit.\n");
            }
        }
        fclose(infile);
    
        /*printf("\n\n");
        system("PAUSE");*/
    }
    
    struct xrac * addToList (struct xrac * first, struct xrac add)
    {
        add.next = first;
        first = (struct xrac *) malloc (sizeof(struct xrac));
        (*first) = add;
    
        return first;
    }
    
    void calcNumGrades (struct xrac * first)
    {
        int numGrade = ((*first).assign * 0.40) + ((*first).quiz * 0.15) + ((*first).midT * 0.15)
                + ((*first).parti * 0.10) + ((*first).final * 0.20);
    
        if (numGrade >= 90)
            (*first).grade = 'A';
        else if (numGrade >= 80)
            (*first).grade = 'B';
        else if (numGrade >= 70)
            (*first).grade = 'C';
        else if (numGrade >= 60)
            (*first).grade = 'D';
        else if (numGrade < 60)
            (*first).grade = 'F';
        else if (numGrade == 0)
            (*first).grade = 'N';
    }
    
    void printAllList (struct xrac * first)
    {
        struct xrac * plat1;
    
        plat1 = first;
        while (plat1 != NULL){
            printf("%s\n", (*plat1).name);
            plat1 = (*plat1).next;
        }
    }
    
    void printLList (struct xrac * first)
    {
        struct xrac * plat1; int i = 0;
    
        plat1 = first;
        while (plat1 != NULL){
            if ((*plat1).grade != 'N')
            {
                printf("%s\n", (*plat1).name);
                i++;
            }
            plat1 = (*plat1).next;
        }
        if (i == 0)
            printf("No studentd have a letter grade.\n");
    }
    
    void printAList (struct xrac * first)
    {
        struct xrac * plat1; int i = 0;
    
        plat1 = first;
        while (plat1 != NULL){
            if ((*plat1).grade == 'A')
            {
                printf("%s\n", (*plat1).name);
                i++;
            }
            plat1 = (*plat1).next;
        }
        if (i == 0)
            printf("No students have an A grade.\n");
    }
    
    void printFList (struct xrac * first)
    {
        struct xrac * plat1; int i = 0;
    
        plat1 = first;
        while (plat1 != NULL){
            if ((*plat1).grade == 'F')
            {
                printf("%s\n", (*plat1).name);
                i++;
            }
            plat1 = (*plat1).next;
        }
        if (i == 0)
            printf("No students have an F grade.\n");
    }
    
    struct xrac * sortList (struct xrac * first)
    {
        struct xrac * plat1; struct xrac * plat2; struct xrac * plat3; struct xrac * safeFirst; int i, n = 0;
    
        first;
    
        do {
            i = 0; n = 0;
            plat1 = first; plat2 = (*plat1).next; plat3 = first;
            while (plat2 != NULL) {
                if ( strcmp((*plat1).name, (*plat2).name) == 1 )
                {
                    (*plat1).next = (*plat2).next;
                    (*plat2).next = plat1;
                    if (n == 0) /*Ensures code can only happen at the beginning of a new round of sorting.*/
                    {
                        first = plat2;
                        (*plat3).next = plat1;
                    }
                    else
                        (*plat3).next = plat2;
                    i++; /*Will increase if there has been a sorting.*/
                }
                else
                {
                    if (n != 0) /*Unnecessary if, but appropriate.*/
                        plat3 = plat1;
                    plat1 = plat2;
                }
                plat2 = (*plat1).next;
                n++;
            }
        } while (i != 0); /*Will continue until no sorting has occurred.*/
    
        return first;
    }
    Here is the information in the txt file:

    Oswald 333-3333-33 M 75 75 75 75 75
    Oscar 111-1111-11 M 100 100 100 100 100
    Lucy 222-2222-22 F 50 50 50 50 50
    Dan 555-5555-55 M 0 0 0 0 0
    Kenny 666-6666-66 M 0 0 0 0 0
    Alice 444-4444-44 F 85 85 85 85 85
    Satan 777-7777-77 M 0 0 0 0 0

    I'm sorry if I'm asking too much, and I really can't blame anyone for not wanting to try to figure out how the hell my sorting function would have actually worked. If anything, can anyone introduce me to a sorting function that would work with this type of linked list?
    Last edited by Jaggid1x; 05-31-2009 at 10:46 PM.

  2. #2
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    Code:
        (*first).name
    change it to

    Code:
        first->name
    then
    Code:
    fflush(stdin);
    don't use it, because undefined behavior

    Code:
    struct xrac * plat1; struct xrac * plat2; struct xrac * plat3; struct xrac * safeFirst;
    change it to

    Code:
        struct xrac *plat1,
                    *plat2,
                    *plat3,
                    *safeFirst;

    Code:
    strcmp((*plat1).name, (*plat2).name) == 1
    check it for greater or less or equal to zero (it can be less than -1 and greater than 1)

    ok
    Code:
        plat1 = first; plat2 = (*plat1).next; plat3 = first;
        
        ...
        
        (*plat1).next = (*plat2).next;
        (*plat2).next = plat1;
        
        if (n == 0) /*Ensures code can only happen at the beginning of a new round of sorting.*/
        {
            first = plat2;
            (*plat3).next = plat1;
        }
    in this moment you will loop first element to itself

    do you know, you can have a node with two pointers: first pointer to the data of the node and second pointer to the next node (and by sorting move only data-of-node pointers over the nodes without change links between the nodes) ?

    like
    Code:
    struct data {
        int one, two, three;
        char four, five, six;
    };
    
    struct node {
        struct data *data;
        struct node *next;
    };
    
    struct list {
        struct node *head, *tail;
        unsigned nelems;
     };
    when you have this, you don't need to change links between nodes and sort the data by moving data pointers

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Okay, looking at your Bubble Sort, I noticed a few things:
    • First off, it crashes when the list is empty, i.e. when passed NULL as the head of the list. An empty list occurs very often in practice.
    • safeFirst is unused.
    • What is the result of executing these three statements, and can you see how they would be executed in your function?
      Code:
      plat1 = first;
    • plat3 = first;
    • (*plat3).next = plat1;
  4. You can do away with 'n' by testing if 'plat1' equals 'first' instead.
  5. Did you know that Insertion Sort for a list is easier to implement than Bubble Sort!

  6. I'll let you think about that much for now.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger

Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  • #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Whoa, I should have previewed that. Code tags don't work so well inside a bullet list!
    The 3 lines are:
    Code:
    plat1 = first;
    plat3 = first;
    (*plat3).next = plat1;
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  • #5
    Registered User
    Join Date
    May 2009
    Posts
    3
    Thank you both for taking the time to look at my code and respond.

    @ c.user:
    I'm assuming that by telling me to change '(*first).name' to 'first->name' you're asking me to change the format I'm using for all instances of (*[pntr]).name, since I can't find a use of '(*first).name' anywhere in my code aside from a set of comments I used to hide away a test to see if my lists were being properly copied. If so, then why? I was told there was no difference between using either styles.

    @ iMalc:
    The first two ('plat1= first;' and 'plat3 = first:') are meant to return the two "platforms" to the beginning of the linked list so that they're ready for a second round of sorting. The third piece of code you mentioned ('(*plat3).next = plat1;')

    ...[minutes later]...

    Was part of the problem! I was trying to make sure that at the first sort of every round 'plat3' would be at the very beginning of the list alongside 'first' and connected to plat1, which at the time would be the next "platform" up, right after 'first,' plat3, and plat2, but I didn't realize that plat3 didn't change its location when I assigned plat2 to 'first', and was actually still with plat1 when I assigned it's own location to its next. (So stupid of me, and the codes in question were right next to each other...)

    ...Oh, so that's what c.user meant with "in this moment you will loop first element to itself". I wasn't sure what the "first element" was.

    Anyways, after noticing that, I realized that my plat3 wasn't moving alongside the other plats properly. It should be that as the plats moved forward, plat3 would be connected to plat1, and plat1 to plat2, but I never wrote the code to move plat3 up, and thus my plat3 wasn't connecting properly whenever a sort took place.

    So what it needed was to get rid of the '(*plat3).next' and have a 'plat3 = plat2' before the i++!

    Thank you both so much, my sort function works perfectly now.

    Also, after thinking about it for a minute, you're right iMalc, an insertion style sorting would have actually been much, MUCH easier.
    Last edited by Jaggid1x; 06-02-2009 at 02:15 AM.

  • #6
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    Jaggid1x,
    -> - is special operation for this
    the difference is
    Code:
    (*first).name
    Code:
    first->name
    first->next->name
    first->next->next->name
    in this case (*first). you are permitted (by one level) and must write same code with (*...) every time
    in substructures you can go through the substructures for get the deepest element, it is more comfortable to do by the arrows

  • #7
    Registered User
    Join Date
    May 2009
    Posts
    3
    Oh, I see now. I'll keep that in mind, seems like I'll have to make a habit of it for future use.

  • Popular pages Recent additions subscribe to a feed

    Similar Threads

    1. In over my head
      By Shelnutt2 in forum C Programming
      Replies: 1
      Last Post: 07-08-2008, 06:54 PM
    2. Dikumud
      By maxorator in forum C++ Programming
      Replies: 1
      Last Post: 10-01-2005, 06:39 AM
    3. compiler build error
      By KristTlove in forum C++ Programming
      Replies: 2
      Last Post: 11-30-2003, 10:16 AM
    4. Interface Question
      By smog890 in forum C Programming
      Replies: 11
      Last Post: 06-03-2002, 05:06 PM
    5. List class
      By SilasP in forum C++ Programming
      Replies: 0
      Last Post: 02-10-2002, 05:20 PM

    Tags for this Thread