Need help with linked list sorting function

Jaggid1x · 05-31-2009, 10:32 PM

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?

c.user · 06-01-2009, 01:15 AM

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

iMalc · 06-01-2009, 02:28 AM

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;

iMalc · 06-01-2009, 02:30 AM

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;

Jaggid1x · 06-02-2009, 01:45 AM

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.

c.user · 06-02-2009, 02:09 AM

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

Jaggid1x · 06-02-2009, 02:14 AM

Oh, I see now. I'll keep that in mind, seems like I'll have to make a habit of it for future use.

06-01-2009, 01:15 AM	#2
c.user 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
c.user is offline

06-01-2009, 02:28 AM	#3
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 2,476	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; You can do away with 'n' by testing if 'plat1' equals 'first' instead. Did you know that Insertion Sort for a list is easier to implement than Bubble Sort! I'll let you think about that much for now. __________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger
iMalc is offline

06-01-2009, 02:30 AM	#4
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 2,476	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
iMalc is offline

06-02-2009, 01:45 AM	#5
Jaggid1x 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.*
Jaggid1x is offline

06-02-2009, 02:09 AM	#6
c.user 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
c.user is offline

06-02-2009, 02:14 AM	#7
Jaggid1x 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.
Jaggid1x is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
In over my head	Shelnutt2	C Programming	1	07-08-2008 06:54 PM
Dikumud	maxorator	C++ Programming	1	10-01-2005 06:39 AM
compiler build error	KristTlove	C++ Programming	2	11-30-2003 10:16 AM
Interface Question	smog890	C Programming	11	06-03-2002 05:06 PM
List class	SilasP	C++ Programming	0	02-10-2002 05:20 PM