Thread: Sorted Linked List...What am i doing wrong!

  1. #1
    Registered User
    Join Date
    Mar 2008
    Location
    Toronto
    Posts
    11

    Sorted Linked List...What am i doing wrong!

    So i've slaved away some more at this and i don't understand where i'm going wrong.

    My program allows the user to enter a name and an age, multiple times to create the list.
    I then sort the list by name and by age with two different pointers.

    i have littered my code with printf's to check where the adding of users function is stopping.

    it makes sense where it stops after the first record is entered as it is the start of the list but when a second record is added the program stops at the exact same place in the function!

    i cannot for the life of me figure out why it's stopping, and not creating the list. It obviously has something to do with the, head == NULL, and i'm guessing my nextName and nextAge pointers. but i just don't know how to fix it.

    Here is my code, anyone got any ideas as to what might be going on?

    Thanks, ALain

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_LEN 250
    
    typedef struct node 
    {
        char *name;
        int  age;
        struct node *nextName;
        struct node *nextAge;
    }NODE;
    
    int drain_stdin()
    {
        int c;
    
        while((c = getchar()) != '\n' && c != EOF);
    
        return c;
    }
    
    NODE * insertNode(NODE *head)
    {
        NODE *new;
        NODE *temp;
        NODE *prev;
    
        new = malloc(sizeof(NODE));
    	new->name = malloc(sizeof(char)*MAX_LEN + 1);
        
        
        if (drain_stdin() != EOF)
        {
            printf("Enter name: ");
            fgets(new->name, MAX_LEN + 1, stdin);
    
            printf("Enter age: ");
            scanf("%d", &new->age);
    
    printf("1\n");
    
            new->nextName = NULL;
            new->nextAge = NULL;
    
    printf("2\n");
    
            if (head == NULL)
            {
    printf("3\n");
                return new;   /* -------------------PROGRAM STOPS HERE ---------------------*/
    printf("4\n");
            }
    
            temp = head;
            prev = NULL;
    printf("5\n");	 
    	    
    	    while(1) 
            {
    printf("6\n");
    		    if (strcmp(temp->name, new->name) < 0) 
                {
    printf("7\n");
    			    prev = temp; 
    			    temp = temp->nextName;      
    			    continue; 
    		    }
                else if(strcmp(temp->name, new->name) >= 0) 
                {
    printf("8\n");
    		        new->nextName = temp;   
    printf("9\n");		
                    
    		        if (prev != NULL)
                    {
    printf("10\n");
                        prev->nextName = new;  
                    }
    		        else
                    {
    printf("11\n");
                        head = new;  
    		            break; 
                    }
                }
    	    }
        }
        else
        {
    printf("12\n");
            printf("An Error Has Occured\n");
        }
    printf("13\n");
        return head;   
    }
    
    NODE * removeStruct(NODE *head)
    {
        NODE *prev;
        NODE *root;
    
        prev = NULL;
        root = head;
    
        char nameRemove[MAX_LEN + 1];
       
        if (drain_stdin() != EOF )
        {
            printf("Enter Name Of Desired Record To Be Removed: ");
            fgets(nameRemove, MAX_LEN + 1, stdin);
    
            while (head != NULL) 
            { 
                if(strcmp(nameRemove, root->name) == 0)
                {
                    printf("Found The Record\n");
                    if (prev != NULL)
                    {
                        prev->nextName = head->nextName;
                        prev->nextAge = head->nextAge; 
                    }
                    else
                    {
                        root = head->nextName; 
                        root = head->nextAge;
                    }
                    free(head);
                    break;
                } 
                else 
                {
         		    prev = head; 
    			    head = head->nextName;
                    head = head->nextAge; 
    		    }
            }
        }
        else
        {
            printf("An Error Has Occured\n");
        } 
        return head;
    }
    
    void printName(NODE *head)
    {
        if (head == NULL) 
        { 
    		printf("List is empty.\n") ; 
    		return ; 
    	}
        else
        {    
            while (head != NULL) 
            {
                printf("%s %d\n", head->name, head->age);
                head = head->nextName;
            }
        }
    }
    
    void printAge(NODE *head)
    {
        if (head == NULL) 
        { 
    		printf("List is empty.\n") ; 
    		return ; 
    	}
        else
        {    
            while (head != NULL) 
            {
                printf("%s %d\n", head->name, head->age);
                head = head->nextAge;
            }
        }
    }
    
    void freeProg(NODE *head)
    {
        free(head->name);    
        free(head);       
    }
    
    int main(void) 
    {
        int choice;
    
        NODE *head;
    
        head = NULL;
    
        do
        {
            printf("1. Add structure\n");
            printf("2. Remove structure\n");
            printf("3. Print names\n");    
            printf("4. Print ages\n");
            printf("5. Exit\n");
            scanf("%d", &choice);
    
            if(choice == 1)
            {
                insertNode(head);
            }
            else if(choice == 2)
            {
                removeStruct(head);
            }
    
            else if(choice == 3)
            {
                printName(head);
            }
            else if(choice == 4)
            {
                printAge(head);
            }
            else if(choice == 5)
            {
                freeProg(head);
            }   
            else
            {
                return 0;
            }
            
        }while(choice != 5);    
    
        return 0;
    }

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    As I was trying to tell you in the other thread, you need to fix your struct. Try this:
    Code:
    typedef struct node 
    {
        char *name;
        int  age;
        struct node *nextNode;
    }NODE;
    Change the struct, and then rework your code to only mess with the one forward pointer for your list.
    Mainframe assembler programmer by trade. C coder when I can.

  3. #3
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    your insertNode function returns head - but you ignore the returned value - so your head in the main is never updated
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  4. #4
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    On another thread I suggested using one link and sorting the list as needed. Apparently tho its for an assignment which needs to have two separate links in each struct, which are ordered. Its confusing, and I cant see many situations where it would be worth the headache, but thats what th op has to do.

  5. #5
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Quote Originally Posted by mike_g View Post
    On another thread I suggested using one link and sorting the list as needed. Apparently tho its for an assignment which needs to have two separate links in each struct, which are ordered. Its confusing, and I cant see many situations where it would be worth the headache, but thats what th op has to do.
    Well, that's just a stupid design and will be fraught with aggravation to maintain.
    Mainframe assembler programmer by trade. C coder when I can.

  6. #6
    Registered User
    Join Date
    Mar 2008
    Location
    Toronto
    Posts
    11
    yes i'm guilty of posting an assignment, and i agree it isn't the best way to do this but the prof really wanted to test our knowledge and apparently i've been tested haha i just can't seem to figure this out. i liked to consider myself a decent programmer as i have a 95&#37; in the course but this dual pointer without a definitive next node pointer is ruining me haha i fully undestand the assignment, drawn diagram after diagram but i just cant seem to implement the ideas.

    thanks for all the help so far it's cleared up alot about lists. i guess it's back to the salt mines slaving away at this haha hopefully i can figure it out.

    Thanks, ALain

  7. #7
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    If each nextAge and nextName are supposed to point to an Age field and a Name field, as their name implies, then there is no list.

    Therefore, what you want to have is a list that can be traversed (downward only) in either Age or Name order. Therefore, if it were me, I would rename the pointers to nextNodeByAge and nextNodeByName to make it clear to the reader that is your intent.

    Now, with that in mind, with each insert into the list, you have to run each list - once for Name chain and the next for Age chain.

    To make this easy on yourself, only work with one pointer chain at a name - either name or age, and get that working. Then, go back and add the additional code to maintain the second pointer chain as well. You'll need two heads to keep track of both lists, as the same node is not necessarily the same for both lists.

    Adam is 52
    Zed is 25.

    Age List: 25 -> 52
    Name List: Adam -> Zed

    Todd
    Last edited by Dino; 03-20-2008 at 03:13 PM.
    Mainframe assembler programmer by trade. C coder when I can.

  8. #8
    Registered User
    Join Date
    Mar 2008
    Location
    Toronto
    Posts
    11
    after each post by ppl i keep getting more and more discouraged haha as the ideas that are presented break some rule in the assignment.

    I've decided to post the assignment just to satisfy everyones curiosity as to how this is supposed to work, i don't expect code or anything from this i just want to clarify exactly what needs to be done so ppl can possibly understand my frustration haha

    Due Date: Due from March 17 to March 24, marked during advising hours. Late assignments will receive a grade of zero.

    The Problem
    It's possible to have multiple pointers in a linked list and sort the same structures differently using each set of pointers.

    For this assignment, create an ordered linked list where each structure contains two pointers. The pointers should order the list based on two different criteria, the name string and the age integer.

    The ordering of the structures is done entirely through pointers. The location of the structures in memory does not change.
    Method
    Use the following structure in your program.
    Code:
    struct node {
       char *name;
       int  age;
       struct node *nextName;
       struct node *nextAge;
    };
    When you add or remove a structure in the list you will need to update both sets of pointers.

    Each name and age pair should be stored in a single structure. Do not create multiple structures containing the same data and do not create two seperate lists. Both lists should remain sorted at all times.

    The program should print the following menu when it is started:

    1. Add structure
    2. Remove structure
    3. Print names
    4. Print ages
    5. Exit

    When Add structure is selected then ask the user for the name and age which will be stored in the structure.

    Enter name:
    Enter age:

    The name can contain blank spaces. Create a structure, store the name and age in it, and place the structure in the list so that it is sorted correctly by both name and age.

    When Remove structure is selected, ask the user for the name of the record to remove. Search through the list and remove the structure from the list. Update both sets of pointers so the list is correctly sorted after the structure has been removed. Don't forget to free the structure once it has been removed from the list.

    When Print names is chosen then print out the list sorted by name. You should be able to step through the list using the nextName pointers and print out each structure. Print both the name and age from one record on a single line.

    When Print age is selected then print out the records based on the age sorted list. This is the same as Print names but you traverse the age pointers.

    Exit should end the program. Free the structures before the program ends.

  9. #9
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    That's fine, and other than renaming the pointer fields, what I said will still fly. You'll still need two heads of lists though.

    You can do it! Do one at a time. It's easier that way.

    Todd
    Mainframe assembler programmer by trade. C coder when I can.

  10. #10
    Registered User
    Join Date
    Mar 2008
    Location
    Toronto
    Posts
    11
    thanks for the advice, i need to take a break though before my eyes fall out. I appreciate all the help.

    Thanks, ALain

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 03:19 PM
  2. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  3. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM