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

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

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;
}

---

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") ;
}

---