Thread: creating a sorted list

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

    creating a sorted list

    I want to take my current prorgam and take the structure and create a sorted list.

    When a user enters a name and age i want to put that at the head then the next time a name and age is added i want to sort the list by name and age, hence the layout of my structure:
    Code:
    struct node 
    {
        char *name;
        int  age;
        struct node *nextName;
        struct node *nextAge;
    };
    I'm having trouble understanding how to create the list. I know i need a pointer to act as the root of the list. i'm just very confused on how to implement this.

    As for the sorting i figure i'll just use the return value of stringcmp() to sort the names.

    here is my original program where the information is successfully stored and can be found and when the remove function is called it finds the correct record.

    BELOW the first hunk of code is my program re-written to incorporate a sorted list.
    i was wondering if someone could tell me if i'm on the right track with the pointers adn so on. I'm just having a hard time understanding lists.

    Thanks in advance, ALain

    ps. there's a bunch of little things missing such as free() the memory, that will come when i have completed the hard stuff.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_LEN 250
    
    struct node 
    {
        char *name;
        int  age;
        struct node *nextName;
        struct node *nextAge;
    };
    
    typedef struct node NODE;
    
    int drain_stdin()
    {
        int c;
    
        while((c = getchar()) != '\n' && c != EOF );
    
        return c;
    }
     
    void addStruct(NODE *root, NODE *ptr)
    {
        root = NULL;
        ptr = NULL;
     
        if (drain_stdin() != EOF)
        {
            printf("Enter name: ");
            fgets(ptr->name, MAX_LEN + 1, stdin);
    
            printf("Enter age: ");
            scanf("%d", &ptr->age);
        }
        else
        {
            printf("An Error Has Occured\n");
        }
    
    }
    
    void removeStruct(NODE *root, NODE *ptr)
    {
        char nameRemove[MAX_LEN + 1];
    
        root = NULL;
        ptr = NULL;
        
        if (drain_stdin() != EOF )
        {
            printf("Enter Name Of Desired Record To Be Removed: ");
            fgets(nameRemove, MAX_LEN + 1, stdin);
    
            if(strcmp(nameRemove, ptr->name) == 0)
            {
                printf("Found The Record\n");
            }
            else
            {
                printf("There Is No Record With That Name\n");
            }
            
        }
        else
        {
            printf("An Error Has Occured\n");
        }
    }
    
    void printName(NODE *root, NODE *ptr)
    {
        root = NULL;
        ptr = NULL;
    
        printf("%s %d\n", ptr->name, ptr->age);
    }
    
    void printAge(NODE *root, NODE *ptr)
    {
        root = NULL;
        ptr = NULL;
    
        printf("%s %d\n", ptr->name, ptr->age);
    }
    
    
    void progExit(NODE *root, NODE *ptr)
    {
    
    }
    
    
    int main() 
    {
        int choice;
    
        NODE *root, *ptr;
    
        ptr = malloc(sizeof(NODE));
        ptr->name = malloc(sizeof(char)*MAX_LEN);
    
        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)
            {
                addStruct(root, ptr);
            }
            else if(choice == 2)
            {
                removeStruct(root, ptr);
            }
    
            else if(choice == 3)
            {
                printName(root, ptr);
            }
            else if(choice == 4)
            {
                printAge(root, ptr);
            }
            else if(choice == 5)
            {
                progExit(root, ptr);
            }   
            else
            {
                return 0;
            }
            
        }while(choice != 5);    
    
        return 0;
    }
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_LEN 250
    
    struct node 
    {
        char *name;
        int  age;
        struct node *nextName;
        struct node *nextAge;
    };
    
    typedef struct node NODE;
    
    int drain_stdin()
    {
        int c;
    
        while((c = getchar()) != '\n' && c != EOF );
    
        return c;
    }
     
    void addStruct(NODE *root, NODE *ptr)
    {
        root = NULL;
        ptr = NULL;
     
        if (drain_stdin() != EOF)
        {
            printf("Enter name: ");
            fgets(ptr->name, MAX_LEN + 1, stdin);
    
            printf("Enter age: ");
            scanf("%d", &ptr->age);
        }
        else
        {
            printf("An Error Has Occured\n");
        }
    
    }
    
    void removeStruct(NODE *root, NODE *ptr)
    {
        char nameRemove[MAX_LEN + 1];
    
        root = NULL;
        ptr = NULL;
        
        if (drain_stdin() != EOF )
        {
            printf("Enter Name Of Desired Record To Be Removed: ");
            fgets(nameRemove, MAX_LEN + 1, stdin);
    
            if(strcmp(nameRemove, ptr->name) == 0)
            {
                printf("Found The Record\n");
            }
            else
            {
                printf("There Is No Record With That Name\n");
            }
            
        }
        else
        {
            printf("An Error Has Occured\n");
        }
    }
    
    void printName(NODE *root, NODE *ptr)
    {
        root = NULL;
        ptr = NULL;
    
        printf("%s %d\n", ptr->name, ptr->age);
    }
    
    void printAge(NODE *root, NODE *ptr)
    {
        root = NULL;
        ptr = NULL;
    
        printf("%s %d\n", ptr->name, ptr->age);
    }
    
    
    void progExit(NODE *root, NODE *ptr)
    {
    
    }
    
    
    int main() 
    {
        int choice;
    
        NODE *root, *ptr;
    
        ptr = malloc(sizeof(NODE));
        ptr->name = malloc(sizeof(char)*MAX_LEN);
    
        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)
            {
                addStruct(root, ptr);
            }
            else if(choice == 2)
            {
                removeStruct(root, ptr);
            }
    
            else if(choice == 3)
            {
                printName(root, ptr);
            }
            else if(choice == 4)
            {
                printAge(root, ptr);
            }
            else if(choice == 5)
            {
                progExit(root, ptr);
            }   
            else
            {
                return 0;
            }
            
        }while(choice != 5);    
    
        return 0;
    }
    Thanks again, ALain

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    A typical structure in a list will have two things:

    1) Whatever Data you want to store
    2) Linkage Information to the next entry (and previous entry if a double linked list)

    Your structure has your data (name and age... well, a pointer to a name, and an age) and linkage information, but you need to fix the linkage information.

    Here is a picture of what you have. Your structure has two pointers, and neither of them is pointing to the right thing.

    What you want is one pointer, and it should point to the next "node", not the next name or next age.

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

  3. #3
    Registered User
    Join Date
    Mar 2008
    Location
    Toronto
    Posts
    11
    Hey thanks for the sweet diagram, i've actually re-written my program to now what i think makes sense. i've been drawing diagram after diagram but i can't wrap my head around this without using a next pointer.

    i've done a list before with a simple structure:
    Code:
    struct data 
    {
        int place;
        struct data *next;
    };
    
    for(i=0; i<5; i++) 
        {
            temp = malloc(sizeof(datatype));
            temp->place = i;
            temp->next = root;
            root = temp;
        }
    aswell as a doubly linked list:
    Code:
    struct data 
    {
        int number;
        struct data *next;
        struct data *prev;
    };
    
    datatype * addElement(int value, datatype *root) 
    {
        datatype *temp;
        /* allocate structure and store value */
    
        temp = malloc(sizeof(datatype));
    
        temp->number = value;
        temp->next = root;
    
        if(root != NULL)
        {
            root->prev = temp;
        }
    
        temp->prev = NULL;
        
        return(temp);
    }
    my problem is that i cannot add a next pointer in my current program. i have to deal with *nextName and *nextAge only. i just honestly can't seem to wrap my head around this!

    Thanks for the feedback, ALain

    here's my updated code...(i have a feeling though that i'm creating two seperate lists, the commented section)

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_LEN 250
    
    struct node 
    {
        char *name;
        int  age;
        struct node *nextName;
        struct node *nextAge;
    };
    
    typedef struct node NODE;
    
    int drain_stdin()
    {
        int c;
    
        while((c = getchar()) != '\n' && c != EOF);
    
        return c;
    }
     
    void addStruct(NODE *root)
    {
        NODE *temp;
        temp = NULL;
    
        temp = malloc(sizeof(NODE));
        temp->name = malloc(sizeof(char)*MAX_LEN + 1);
    
        
        if (drain_stdin() != EOF)
        {
            printf("Enter name: ");
            fgets(temp->name, MAX_LEN + 1, stdin);
    
            printf("Enter age: ");
            scanf("%d", &temp->age);
            /*
            temp = root;
            temp->nextName = root;
            root = temp;
    
            temp = root;
            temp->nextAge = root;
            root = temp;*/
        }
        else
        {
            printf("An Error Has Occured\n");
        }
    }
    
    void removeStruct(NODE *root)
    {
        NODE *temp;
        temp = NULL;
    
        temp = malloc(sizeof(NODE));
        temp->name = malloc(sizeof(char)*MAX_LEN + 1);
    
        char nameRemove[MAX_LEN + 1];
       
        if (drain_stdin() != EOF )
        {
            printf("Enter Name Of Desired Record To Be Removed: ");
            fgets(nameRemove, MAX_LEN + 1, stdin);
    
            if(strcmp(nameRemove, temp->name) == 0)
            {
                printf("Found The Record\n");
            }
            else
            {
                printf("There Is No Record With That Name\n");
            }
            
        }
        else
        {
            printf("An Error Has Occured\n");
        }
    }
    
    void printName(NODE *root)
    {
        NODE *temp;
        temp = NULL;
    
        temp = malloc(sizeof(NODE));
        temp->name = malloc(sizeof(char)*MAX_LEN + 1);
        
        temp = root;
        
        while (temp != NULL) 
        {
            printf("%s %d\n", temp->name, temp->age);
            temp = temp->nextName;
        }
    }
    
    void printAge(NODE *root)
    {
        NODE *temp;
        temp = NULL;
    
        temp = malloc(sizeof(NODE));
        temp->name = malloc(sizeof(char)*MAX_LEN + 1);
    
        temp = root;
        
        while (temp != NULL) 
        {
            printf("%s %d\n", temp->name, temp->age);
            temp = temp->nextAge;
        }
    }
    
    
    void freeProg(NODE *root)
    {
       
    }
    
    
    int main() 
    {
        int choice;
    
        NODE *root;
    
        root = 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)
            {
                addStruct(root);
            }
            else if(choice == 2)
            {
                removeStruct(root);
            }
    
            else if(choice == 3)
            {
                printName(root);
            }
            else if(choice == 4)
            {
                printAge(root);
            }
            else if(choice == 5)
            {
                freeProg(root);
            }   
            else
            {
                return 0;
            }
            
        }while(choice != 5);    
    
        return 0;
    }

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Here's a working list. Study it to see how they work.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct myllist
    {
    	int data;
    	struct myllist * link;
    } myllist;
    
    myllist * addNode (int newData,  myllist * pNode);
    myllist * insertNode (int newData,  myllist * pNode);
    myllist * removeNode (int key , myllist *list);
    void printList (myllist *list);
    
    int main (int argc, const char * argv[]) 
    {
    
    	//setup nodes
    	myllist * pNode = NULL ;  // This variable holds the head of the list.
    	   	   
    	pNode = addNode(4, pNode);
    	(void)  addNode(5, pNode);
    	(void)  addNode(8, pNode);
    
    	printf("\nPrinting initial list:\n");
    	printList(pNode);
    
    	pNode = insertNode(6, pNode) ; 
    		
    	//print list
    	printf("\nPrinting list after add of 6:\n");
    	printList(pNode); 
    		
    	//do stuff to list
          
    	pNode = removeNode(6, pNode) ;
    	pNode = removeNode(5, pNode) ;
    	pNode = addNode(18, pNode);
    	pNode = removeNode(4, pNode) ; 
    	pNode = removeNode(8, pNode) ; 
    	
    	//print new list
    	printf("\nPrinting final list:\n");
    	printList(pNode);
           
    	return 0 ; 
    }
    
    myllist * addNode (int newData, myllist * head) 
    {
    	printf("Adding key = &#37;d\n", newData ); 
    
    	// Initialize new entry.  It goes on the end of the list. 
    	myllist * newone = (myllist *) malloc(sizeof(*head));  // Get a new list entry
    	newone->data = newData ; 
    	newone->link = NULL ; 
    	
    	// insert it at the front of no other yet. 
    	if (head == NULL) { 
    		head = newone ; 
    		head->data = newData ; 
    		head->link = NULL ; 
    	}
    	else {   // Get to the end of the list.
    		myllist * temp = head ; 
    		// Get to the end of the list. 
    		while (temp->link != NULL) { 
    			temp = temp->link ;      // get foward pointer. 
    		}
    		temp->link = newone ;    // Chain the new entry. 
    	}
    	return head ; 
    }
    
    myllist * insertNode (int newData, myllist * head) {
    
    	// Initialize new entry.  It goes somewhere in the list. 
    	myllist * newone = (myllist *) malloc(sizeof(*head));  // Get a new list entry
    	newone->data = newData ; 
    	newone->link = NULL ; 
    	
    	if (head == NULL) return newone ;   // Done if the first one 
    	
    	myllist * temp = head, * previous = NULL ;
    	 
    	// Find where to insert the new element.  
    	// Loop through the list and find an entry to insert it before. 
    	while (1) {
    		if (temp->data < newData) {
    			previous = temp ; 
    			temp = temp->link ;      // get foward pointer. 
    			continue ; 
    		}
    		// Insert it after the prevous entry.
    		newone->link = temp ;   // Make the new element point to the "right" element
    		// Make the "left" element (the previous element) point to the new element  
    		if (previous != NULL) previous->link = newone ;  
    		else head = newone ;  // new head 
    		break ; 
    	}	
    	return head ;   // return the updated list  
    }
           
    myllist * removeNode (int key, myllist *list){  //remove the list entry assocaited with key 
    	myllist * previous = NULL, * head = list ;
        printf("Removing key = %d\n", key ); 
    	while (list != NULL) { 
    
    		if (list->data == key) { 
    			if ( previous != NULL ) previous->link = list->link ;   // Fix forward pointer to skip this entry 
    			else head = list->link ;                                // Remove the first entry 
    			free(list) ; // free the entry 
    			break ; 
    		} 
    		else { 
    			previous = list ; 
    			list = list->link ; 
    		} 
    	}
    	printf("Remove: Printing resultant list\n");
    	printList(head);
    	return head ; 
    } 
    
    void printList (myllist *list) {
    	if (list == NULL) { 
    		printf("List is empty.\n") ; 
    		return ; 
    	}
    	while(list != NULL) { 
    		printf("%d ", list->data) ;
    		list = list->link;
    	}
    	printf("\n") ; 
    }
    Last edited by Dino; 03-20-2008 at 01:17 AM.
    Mainframe assembler programmer by trade. C coder when I can.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. deleting a node in linked list
    By BoneXXX in forum C Programming
    Replies: 18
    Last Post: 12-17-2007, 12:30 PM
  3. Recursion Revisited again, and again!
    By clegs in forum C++ Programming
    Replies: 93
    Last Post: 12-08-2007, 08:02 PM
  4. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM