Thread: Sorted Linked List with multiple heads.

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

    Sorted Linked List with multiple heads.

    Hi there i've been tinkering with this program for a while and think i have it figured out, but i'm getting some segmentation faults and memory issues.

    Here are my issues, if i understoud them i'd fix them but to be honest i've been experimenting with this code alot and it's whooping my butt haha

    1. When i select option 1. i can enter new info, and print it out. BUT if i choose option 1 again to add another entry to the list i get a seg fault.

    2. When i select option 2 to remove an entry i type the name and it finds it and removes it then gives me a seg fault.

    3. When i add a struct then search for a record that's not there when i print the struct back out it says the list is empty?

    can someone go over my code and let me know if it makes any sense at all, i've found this problem very hard to solve solely using *nextName and *nextAge.

    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 * listInput(NODE *new)
    {
    
        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);
        }
        else
        {
            printf("An Error Has Occured\n");
        }
        return new;
    }
    
    NODE * insertNameNode(NODE *new, NODE *head1)
    {
        NODE *temp;
        NODE *prev;
    
        new->nextName = NULL;
        
        if (head1 == NULL)
        {
            return new;     
        }
    
        temp = head1;
        prev = NULL; 
        
        while(1) 
        {
    
    	    if (strcmp(temp->name, new->name) < 0) 
            {
    		    prev = temp; 
    		    temp = temp->nextName;      
    		    continue; 
    	    }
            else if(strcmp(temp->name, new->name) >= 0) 
            {
    	        new->nextName = temp;   	
                
    	        if (prev != NULL)
                {
                    prev->nextName = new;  
                }
    	        else
                {
                    head1 = new;  
    	            break; 
                }
            }
        }
        return (head1);    
    }
    
    NODE * insertAgeNode(NODE *new, NODE *head2)
    {
        NODE *temp;
        NODE *prev;
    
        new->nextAge = NULL;
    
        if (head2 == NULL)
        {
            return new;     
        }
    
        temp = head2;
        prev = NULL; 
        
        while(1) 
        {
    
    	    if (temp->age < new->age) 
            {
    		    prev = temp; 
    		    temp = temp->nextAge;      
    		    continue; 
    	    }
            else if(temp->age >= new->age) 
            {
    	        new->nextAge = temp;   	
                
    	        if (prev != NULL)
                {
                    prev->nextAge = new;  
                }
    	        else
                {
                    head2 = new;  
    	            break; 
                }
            }
        }
        return(head2);
    }
    
    NODE * removeNameStruct(NODE *head1, char *nameRemove)
    {
        NODE *prev;
        NODE *root;    
    
        prev = NULL;
        root = head1;    
       
        if (drain_stdin() != EOF )
        {
            printf("Enter Name Of Desired Record To Be Removed: ");
            fgets(nameRemove, MAX_LEN + 1, stdin);
    
            while (head1 != NULL) 
            { 
                if(strcmp(nameRemove, root->name) == 0)
                {
                    printf("Found The Record\n");
    
                    if (prev != NULL)
                    {
                        prev->nextName = head1->nextName;
                    }
                    else
                    {
                        root = head1->nextName; 
                    }
                    free(head1);
                    break;
                } 
                else 
                {
                    printf("Record NOT Found\n");
         		    prev = head1; 
    			    head1 = head1->nextName;
    		    }
            }
        }
        else
        {
            printf("An Error Has Occured\n");
        } 
        return (head1);
    }
    
    NODE * removeAgeStruct(NODE *head2, char *nameRemove)
    {
    
        NODE *prev;
        NODE *root;
    
        prev = NULL;   
        root = head2;    
    
        while (head2 != NULL) 
        { 
            if(strcmp(nameRemove, root->name) == 0)
            {
                printf("Found The Record\n");
    
                if (prev != NULL)
                {
                    prev->nextAge = head2->nextAge;
                }
                else
                {
                    root = head2->nextAge;
                }
                free(head2);
                break;
            } 
            else 
            {
                printf("Record NOT Found\n");
                prev = head2;
                head2 = head2->nextAge;
    	    }
        }
        return (head2);
    }
    
    void printName(NODE *head1, NODE *head2)
    {
        if (head1 == NULL) 
        { 
    		printf("List is empty.\n") ; 
    		return; 
    	}
        else
        {    
            while (head1 != NULL) 
            {
                printf("%s %d\n", head1->name, head2->age);
                head1 = head1->nextName;
            }
        }
    }
    
    void printAge(NODE *head1, NODE *head2)
    {
        if (head2 == NULL) 
        { 
    		printf("List is empty.\n") ; 
    		return ; 
    	}
        else
        {    
            while (head2 != NULL) 
            {
                printf("%s %d\n", head2->name, head2->age);
                head2 = head2->nextAge;
            }
        }
    }
    
    
    void freeProg(NODE *head1, NODE *head2)
    {
        while(head1 != NULL && head2 != NULL)
        {
            free(head1->name);    
            free(head1);
            free(head2->name);    
            free(head2);
        }     
    }
    
    
    int main(void) 
    {
        int choice, count;
        char nameRemove[MAX_LEN + 1];
    
        choice = 0;
        count = 0;
    
        NODE *new;
        NODE *head1;
        NODE *head2;
        
        new = NULL;
        head1 = NULL;
        head2 = 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)
            {
                new = listInput(new);
                head1 = insertNameNode(new, head1);
                head2 = insertAgeNode(new, head2);
            }
            else if(choice == 2)
            {
                head1 = removeNameStruct(head1, nameRemove);
                head2 = removeAgeStruct(head2, nameRemove);
            }
    
            else if(choice == 3)
            {
                printName(head1, head2);
            }
            else if(choice == 4)
            {
                printAge(head1, head2);
            }
            else if(choice == 5)
            {
                freeProg(head1, head2);
            }   
            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
    See the changes in red. (This is the first bug I saw - I didn't test for any more.)
    Code:
    NODE * insertNameNode(NODE *new, NODE *head1)
    {
        NODE *temp;
        NODE *prev;
    
        new->nextName = NULL;
        
        if (head1 == NULL)
        {
            return new;     
        }
    
        temp = head1;
        prev = NULL; 
        
        while(1) 
        {
    
    	    if (strcmp(temp->name, new->name) < 0) 
            {
    		    prev = temp; 
    		    temp = temp->nextName;      
    		    continue; 
    	    }
            else  // if(strcmp(temp->name, new->name) >= 0)  - not a bug - you just don't need it  
            {
    	        new->nextName = temp;   	
                
    	        if (prev != NULL)
                {
                    prev->nextName = new;  
                }
    	        else
                {
                    head1 = new;  
                }
                break;  
            }
        }
        return (head1);    
    }
    Mainframe assembler programmer by trade. C coder when I can.

  3. #3
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,058
    i've found this problem very hard to solve solely using *nextName and *nextAge.
    Maybe a basic working example of how these structures are used can be of some help..

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    #define MAX_LEN 250
    
    struct node {
        char *name;
        int  age;
        struct node *nextName;
        struct node *nextAge;
    }NODE;
    
    struct node *namestart, *namelast, *info;
    struct node *agestart, *agelast;
    
    void StoreNameRecord( struct node  *i,  /* new element */
                    struct node  **start, /* first element */
                    struct node  **last /* last element */
                    )
    {
        struct node *old, *p;
        p = *start; /* start at top of list */
        if(*last == NULL) /* first element in list */
        {
            i->nextName = NULL;
            *last = i;
            *start = i;
            return;
        }
        old = NULL;
        while(p)
        {
            if(stricmp(p->name, i->name) < 0) 
            {
                old = p;
                p = p->nextName;
            }
            else
            {
                if(old)
                {
                    old ->nextName = i;
                    i->nextName = p;
                    return;
                }
                i->nextName = p; /* new first element */
                *start = i;
                return;
            }
        }
        (*last)->nextName = i;
        i->nextName = NULL;
        *last = i;
    }
    
    void StoreAgeRecord( struct node  *i,  /* new element */
                    struct node  **start, /* first element */
                    struct node  **last /* last element */
                    )
    {
        struct node *old, *p;
        p = *start; /* start at top of list */
        if(*last == NULL) /* first element in list */
        {
            i->nextAge = NULL;
            *last = i;
            *start = i;
            return;
        }
        old = NULL;
        while(p)
        {
            if(p->age < i->age)  
            {
                old = p;
                p = p->nextAge;
            }
            else
            {
                if(old)
                {
                    old ->nextAge = i;
                    i->nextAge = p;
                    return;
                }
                i->nextAge = p; /* new first element */
                *start = i;
                return;
            }
        }
        (*last)->nextAge = i;
        i->nextAge = NULL;
        *last = i;
    }
    
    int main(void)
    {
        int iIndex, iAge[] = { 23, 10, 45, 16, 99, 14, 34};
        char *pNames[] =  {"Richard", "Deborah", "Bob", "Alice", "Fred", "Theodore", "Charlie"}; 
    
        namestart = namelast = info = NULL;
        agestart = agelast  = NULL;
        for(iIndex = 0; iIndex < sizeof(iAge) / sizeof(int); iIndex++)
        {
            if((info = (struct node *) malloc(sizeof(NODE))) == NULL)
                return -1; // Out of memory
            if((info->name = (char *) malloc(MAX_LEN * sizeof(char))) == NULL)
                return -1;
            strcpy(info->name, pNames[iIndex]);
            info->age = iAge[iIndex];
            if((info->nextName = (struct node *) malloc(sizeof(NODE))) == NULL)
                return -1; // Out of memory
            if((info->nextAge = (struct node *) malloc(sizeof(NODE))) == NULL)
                return -1; // Out of memory
            if((info->nextName->name = (char *) malloc(MAX_LEN * sizeof(char))) == NULL)
                return -1;
            if((info->nextAge->name = (char *) malloc(MAX_LEN * sizeof(char))) == NULL)
                return -1;        
            StoreNameRecord(info, &namestart, &namelast);
            StoreAgeRecord(info, &agestart, &agelast);
        }
        printf("\nPrint sorted by names\n\n");
        info = namestart;
        while(info) // Beginning to End
        {
            printf("%-20s %d\n",info->name, info->age);
            info = info->nextName;
        }
        printf("\nPrint sorted by age\n\n");
        info = agestart;
        while(info) // Beginning to End
        {
            printf("%-20s %d\n",info->name, info->age);
            info = info->nextAge;
        }   
        return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 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. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM