Thread: simple structure/linked list question

  1. #1
    Hopeless
    Join Date
    Jul 2005
    Location
    Bay Area, CA
    Posts
    25

    simple structure/linked list question

    Hi,

    Just need a little clarification here. I am studying linked lists and structures in my class and had a general question for anyone that would be kind enough to help out Here is an example that is given in my book:

    Code:
    typedef int KEY_TYPE;  /* Application Dependant */
    
    typedef struct
    {
        KEY_TYPE key;    / * Other Data Fields */
        ...
        } DATA;
    
    typedef struct nodeTag
    {
        DATA                 data;
        struct nodeTag *link;
        } NODE;
    So here are my questions.

    1) What does application dependant mean? My guess is that what is put here depends on the application that I am trying to create, but I do not understand how or why this statement is there.

    2) Where the first structure is commented /* Other Data Fields */I can put any other data I want in this structure? For example, if I wanted to make a list of names and phone numbers that I can search, add to, delete from, and print, I can just make arrays to hold each piece of data within the structure "DATA"?

    3) Is the second structure just standard syntax or is it dependant on the specific program that I am trying to run?

    Ok guys, have at it. Thanks in advance for any help!!

    ~P

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I assume they're trying to use 'key' to determine what type of data this structure holds. Probably so they can read the first portion of a structure, read its 'key', and decide the real size or structure they should be using. Probably to try and either have multiple structure types in the same file, or something else along those lines.

    The general form of a linked list is this:
    Code:
    struct foo
    {
        struct foo *link;
        ...some data here...
    };
    Where the structure contains a pointer to its same type. This lets you link a series of them together. The data portion can be anything. Thus, you can make a linked list of integers, strings, other structures, whatever. It doesn't really matter. What makes a linked list is having a pointer to the same type of object that the structure itself is.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > What does application dependant mean?
    Pick whatever type you want to put into your linked lists.
    The list code itself doesn't care about the things you're storing, so it's just a way of marking in the code the difference between what is 'list' and what is 'data'.

    > I can put any other data I want in this structure?
    Yes.

    > Is the second structure just standard syntax
    Pretty much the standard way of representing a node of a linked list.
    struct nodeTag *link; is common to everything, the DATA is just one of several common ways of representing the data you want to store.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Hopeless
    Join Date
    Jul 2005
    Location
    Bay Area, CA
    Posts
    25
    Ok, so what I am getting from your two inputs is that the first statement does not really have to be there. It can to make things more readable, but does not actually have to be there? Hope that is correct.

    The first structure holds all my data. All the information I want to process.

    The second structure has a pointer that links all the different elements in the first structure together to form a "list".

    Does that sound somewhat correct, or am I still way off in left field on this?

    Thanks again,

    ~P

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Ok, so what I am getting from your two inputs is that the first statement does not really have to be there. It can to make things more readable, but does not actually have to be there?
    Correct. With the code
    Code:
    typedef int KEY_TYPE;
    KEY_TYPE becomes a synonym for int.

    The first structure holds all my data. All the information I want to process.
    Exactly, like ints, chars, and other structures.

    And the rest of your post is pretty accurate.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Hopeless
    Join Date
    Jul 2005
    Location
    Bay Area, CA
    Posts
    25
    KEY_TYPE becomes a synonym for int.
    Why would you ever want to do this? This sounds like it would just complicate things no? So I think.. best bet is to just leave that part out. Doesn't make any sense that they put this statement in the text book. oh well, maybe one of these days after I really get a grasp of what's going on here I can maybe understand why they do what they do in this book. ughh... hehe

  7. #7
    Destoryer of Worlds
    Join Date
    Jul 2005
    Posts
    17
    They covered linked lists before they coverd typedef ???


    dont sound like a very good book

  8. #8
    Hopeless
    Join Date
    Jul 2005
    Location
    Bay Area, CA
    Posts
    25
    dont sound like a very good book
    haha.. my thoughts exactly

  9. #9
    Hopeless
    Join Date
    Jul 2005
    Location
    Bay Area, CA
    Posts
    25
    so this is what I came up with for my homework assignment to create the structures.

    Code:
    typedef struct
    {
    	int key;
    	char first_name[81];
    	char last_name[81];
    	int areaCode;
    	int phoneNumber;
    } DATA;
    
    typedef struct nodeTag
    {
    	DATA		data;
    	struct nodeTag *link;
    } NODE;
    Does that look like the right syntax and everything for making a linked list for names/phone numbers?

  10. #10
    Hopeless
    Join Date
    Jul 2005
    Location
    Bay Area, CA
    Posts
    25
    Ok, I was looking for some programming examples online to help me out, and i stumbled accoss this one. And just for a disclaimer, I am not going to use this for my homework assignment. I just wanted to show you guys as a reference to some of my questions. Anyway, here goes...

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    enum {
        MAXLEN=255
    };
    
    typedef struct list {
        char name[MAXLEN];
        char address[MAXLEN];
        char phone[MAXLEN];
        struct list *next;
    } ADDRESS;
    
    void add_to_list (void);  /* Add a name to our address book */
    void delete_from_list (void);/* Delete a name from our book */
    void print_name (void);   /* Print an entry in the address book */
    void list_names (void);   /* List all the names in the book */
    void free_list (void);    /* Free all the linked list */
    
    ADDRESS *hol= NULL;  /* Head of our linked list of addresses - 
                            global variable*/
    
    int main()
    {
        char input[MAXLEN];   /* Input from the user */
    
    
        while (1) {
            printf ("(A)dd/(D)elete/(P)rint/(L)ist/(Q)uit\n");
            fgets (input, MAXLEN,stdin);
            switch (input[0]) {
                case ('a'):
                case ('A'):
                    add_to_list();
                    break;
                case ('d'):
                case ('D'):
                    delete_from_list();
                    break;
                case ('p'):
                case ('P'):
                    print_name();
                    break;
                case ('l'):
                case ('L'):
                    list_names();
                    break;
                case ('q'):
                case ('Q'):
                    free_list();
                    return (0);
                default:
                    printf ("Unknown command\n"); 
            }
        
        }
        return 0;
    }    
    
    void add_to_list (void) 
    /* Add a new name to our address book */
    {
        ADDRESS *new_name;
        
        new_name= malloc (sizeof (ADDRESS));
        if (new_name == NULL) {
            printf ("Out of memory!\n");
            exit (-1);
        }
        /* Get input for the new item */
        printf ("Name> ");
        fgets (new_name->name, MAXLEN, stdin);
        printf ("Address> ");
        fgets (new_name->address, MAXLEN, stdin);
        printf ("Tel> ");
        fgets (new_name->phone, MAXLEN, stdin);
        /* Chain the new item into the list */
        new_name->next= hol;
        hol= new_name;
    }    
    
    void delete_from_list (void)
    /* Remove a name from the address book */
    {
        ADDRESS *del_ptr;   /* Pointer to find name to delete */
        ADDRESS *prev_ptr;  /* Pointer to name BEFORE this name */
        char del_name[MAXLEN]; /* Name to delete */
        
        printf ("Name> ");
        fgets (del_name, MAXLEN, stdin);
        /* The first item in the list being deleted is a special case */
        if (hol == NULL) {
            printf ("No list to delete from\n");
            return;
        }
        /* If the first name is the correct one then move the head of list on to the next head of list */
        if (strcmp(hol->name, del_name) == 0) {
            del_ptr= hol;
            hol= hol->next;
            free(del_ptr);
            return; 
        }
        /* Otherwise loop round the list looking for the name */
        prev_ptr= hol;
        while (prev_ptr->next != NULL) {
            /* We've found the name so delete it */
            if (strcmp(prev_ptr->next->name,del_name) == 0) {
                del_ptr= prev_ptr->next;
                prev_ptr->next= del_ptr->next;
                free(del_ptr);
                return;
            }
            prev_ptr= prev_ptr->next;
        }
        printf ("Name not found!\n");
    }
    
    void print_name (void)
    /* Print a name from the list */
    
    {
        char name[MAXLEN];  /* Name to look for */
        ADDRESS *search_ptr; /* Pointer to search list for name */
        printf ("Name> ");
        fgets (name, MAXLEN, stdin);
        search_ptr= hol;
        while (search_ptr != NULL) {
            if (strcmp (search_ptr->name, name) == 0) {
                printf ("Address: %s", search_ptr->address);
                printf ("Tel: %s", search_ptr->phone);
                return;
            }
            search_ptr= search_ptr->next; /* Move to next item */
        }
        printf ("No such name\n");
    }
    
    void list_names (void)
    /* List all names in the book */
    {
        ADDRESS *tmp_ptr; /* Traverses list */
        printf ("All names in address book:\n");
        tmp_ptr= hol;
        while (tmp_ptr != NULL) {
            printf ("%s",tmp_ptr->name);
            tmp_ptr= tmp_ptr->next;
        }
    }
    
    void free_list (void)
    /* Free memory for list */
    {
        ADDRESS *del_ptr;  /* Pointer to part to delete */
        
        while (hol != NULL) {
           del_ptr= hol;  /* Store the head of list */
           hol= hol->next; /* Move on to the next bit */
           free(del_ptr);  /* Free the memory for the bit we just left */
        }
    }
    I don't see any refernece to NODES and what does this code

    Code:
    ADDRESS *hol= NULL;  /* Head of our linked list of addresses -
    mean?

    This example confused me more than anything I think... Any help is appreciated.

    Thanks,

    ~P

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well you don't really need 'key' in there. You also could just use a string for the phone number. You could even get rid of the 'data' structure entirely, and just do:
    Code:
    struct foo
    {
        struct foo *link;
        char first_name[81];
        char last_name[81];
        int areaCode;
        int phoneNumber;
    };
    If you like your phone number set up that way.

    But sure, what you have will work fine so long as you write the appropriate functions to fill it, and as long as you inderstand it. Go for it.


    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    They're using a global pointer to keep track of their list. The line you're not sure what it does is setting the list pointer to NULL, to indicate that it doesn't point to anything.

    A 'node' is just a term used for one item in a linked list. You don't have to call anything 'node'. People just use the term as a generic reference so people understand what they're talking about without having to say, "one object in my linked list" every time they refer to one.

    Quzah.
    Hope is the first step on the road to disappointment.

  13. #13
    Hopeless
    Join Date
    Jul 2005
    Location
    Bay Area, CA
    Posts
    25
    so what you are saying is that the person who wrote this code put the "NODE" or whatever we want to call it as a global pointer instead of putting it into the structure? In effect, he took the structure example that was in my book (top of the post):

    Code:
    typedef struct nodeTag
    {
        DATA                 data;
        struct nodeTag *link;
        } NODE;
    and declared it globally. omg omg.. if I just understood this, it is a miracle!! Thank you so much!!

  14. #14
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    What you've got above isn't an actual instance of a variable. You're defining (typedef) a structure as a data type called 'NODE'. So instead of having to type:
    Code:
    struct nodeTag *aPtr;
    struct nodeTag anInstance;
    ...when you want a pointer, or instance, you can instead do this:
    Code:
    NODE *aPtr;
    NODE anInstance;
    That's all you have above. You still haven't actually made any instance of said structure. What they're doing is declaring an instance of it globally:
    Code:
    ADDRESS *hol= NULL;
    And setting it to NULL. It would be as if you had done:
    Code:
    typedef struct nodeTag
    {
        ...all of your stuff...
    } NODE; /* here you're defining a type 'NODE',
               not creating an actual lnstance */
    
    NODE *aGlobalPointer; /* here you're actually making
                             an instance of a pointer */
    Except here I didn't bother setting it to NULL.


    Quzah.
    Hope is the first step on the road to disappointment.

  15. #15
    Hopeless
    Join Date
    Jul 2005
    Location
    Bay Area, CA
    Posts
    25
    awesome!! I got my assignment done and I could not have done it with out your help!! Thanks so much quzah and everyone else who gave input. I think I am finally getting an understanding of all this stuff.

    Thanks again,

    ~P

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 04:05 PM
  2. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. Simple list code
    By JimpsEd in forum C Programming
    Replies: 1
    Last Post: 05-24-2006, 02:01 PM
  5. linked list stack question
    By Drew in forum C++ Programming
    Replies: 2
    Last Post: 09-11-2003, 05:05 AM