Surprise! linked list program help...

This is a discussion on Surprise! linked list program help... within the C Programming forums, part of the General Programming Boards category; Code: #include <stdio.h> #include <stdlib.h> struct listNode { char data; struct listNode *nextPtr; }; typedef struct listNode LISTNODE; typedef LISTNODE ...

  1. #1
    Registered User
    Join Date
    Mar 2006
    Location
    Honolulu, HI/United States
    Posts
    12

    Surprise! linked list program help...

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct listNode {
        char data;
        struct listNode *nextPtr;
    };
    
    typedef struct listNode LISTNODE;
    typedef LISTNODE *LISTNODEPTR;
    
    void insert(LISTNODEPTR *, char);
    char delete_me(LISTNODEPTR *, char);
    int isEmpty(LISTNODEPTR);
    void printList(LISTNODEPTR);
    void instructions(void);
    
    int main(int argc, char* argv[])
    {
        LISTNODEPTR startPtr = NULL;
    
        int choice;
        char item;
    
        instructions(); /*display the menu*/
        printf("? ");
        scanf("%d", &choice);
    
        while (choice != 3) {
            switch (choice) {
            case 1:
                printf("Enter a character ");
                scanf("\n%c", &item);
                insert(&startPtr, item);
                printList(startPtr);
                break;
            case 2:
                if (!isEmpty(startPtr)) {
                    printf("Enter character to be deleted: ");
                    scanf("\n%c", &item);
                    if (delete_me(&startPtr, item)) {
                        printf("%c deleted.\n", item);
                        printList(startPtr);
                    }
                    else
                        printf("%c not found. \n\n", item);
                }
                else
                    printf("List is empty.\n\n");
                break;
            default:
                printf("Invalid choice.\n\n");
                instructions();
                break;
            }
            printf("? ");
            scanf("%d", &choice);
        }
        printf("End of run.\n");
    
        return 0;
    }
    
    /*Print the instructions*/
    void instructions(void)
    {
        printf("Enter your choice:\n"
            "   1 to insert an element into the list.\n"
            "   2 to delete an element from the list.\n"
            "   3 to end.\n");
    }
    
    /*Insert a new value into the list in sorted order*/
    void insert(LISTNODEPTR *sPtr, char value)
    {
        LISTNODEPTR newPtr, previousPtr, currentPtr;
        newPtr = (LISTNODEPTR)malloc(sizeof(LISTNODE));
        if (newPtr != NULL) {
            newPtr->data = value;
            newPtr->nextPtr = NULL;
    
            previousPtr = NULL;
            currentPtr = *sPtr;
            
            while (currentPtr != NULL && value > currentPtr->data) {
                previousPtr = currentPtr;  /*walk to...*/
                currentPtr = currentPtr->nextPtr;/*...next node*/
            }
    
            if (previousPtr == NULL) {
                newPtr->nextPtr = *sPtr;
                *sPtr = newPtr;
            }
            else {
                previousPtr->nextPtr = newPtr;
                newPtr->nextPtr = currentPtr;
            }
        }
        else
            printf("%c not inserted. No memory available.\n", value);
    }
    It's from a textbook I'm using to learn C. The 3 different lines I bolded are where my questions lay. The startPtr is a pointer variable that points to the listNode structure. How come the insert and delete functions use the (&) and the printList function does not? I figured since startPtr is a pointer then the (&) would cause the function to use the address of the pointer variable for insert and delete and without it the printList would receive the address of what the pointer variable points to.

    Thanks for help ahead of time!

  2. #2
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,069
    This is because the insert and delete_me functions are looking for a pointer to a pointer (though it can be hard to tell because this programmers typedef masks the second pointer) the printList function only expects a pointer. Since startPtr is a pointer, you'd pass the value of it to printList and the address of it to the other two functions.

    The reason he's doing this is because the insert and delete_me functions edit the arguement that's passed, while the print function just outputs it without changing anything.
    Sent from my iPadŽ

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    9
    Greetings fellow programmer.

    You give a variable to another function by reference by sending the adress.

    This means you can change the value of the variable in the other funciton and NOT change a copy of it...

    You have not included the printf function but you probably send it by value because the value is not changed in the printf function. And if it is changed, the original value has not changed.

    Get it? If you do not understand this, don't blame yourself, I'm not exactly an expert in explaining things.

    Greets!
    Last edited by Wezel; 03-17-2006 at 03:35 AM.

  4. #4
    Registered User
    Join Date
    Mar 2006
    Location
    Honolulu, HI/United States
    Posts
    12
    Thx SlyMaelstrom, did not catch that in the declarations of the functions and the earlier typedef. Not good at putting 2 and 2 together sometimes.

  5. #5
    Registered User
    Join Date
    Feb 2006
    Posts
    155
    if u have understood all that,
    spysmily1 can u now explain me why exactly u need to have a double pointer,whydid the author not use just a pointer?

  6. #6
    Registered User
    Join Date
    Mar 2006
    Location
    Honolulu, HI/United States
    Posts
    12
    I'm not for sure why they use a double pointer and not a pointer. That's the kinda thing that's been giving me a hard time with this lesson on linked list.

    I'm reviewing the code now that I have my eyes open to the double pointer parameter.

  7. #7
    Registered User
    Join Date
    Mar 2006
    Location
    Honolulu, HI/United States
    Posts
    12
    If you or anyone has a clue as to the double pointer I would be very grateful to any replies as to the answer to this question. In fact if someone would like to break down the line by line in the function insert as to what is going on as I am continuously losing my train of thought trying to break this down myself. I can pick out what is happening up until currentPtr=*sPtr; is this assigning the the address that is held by sPtr to currentPtr since sPtr is a pointer to another pointer of struct listNode and the * dereferences it.

  8. #8
    Registered User
    Join Date
    Feb 2006
    Posts
    155
    first a link list is a chain of nodes,and each node is identified by its address.

    *sptr is the address of the first node.(can u get this?)

    >currentptr =*sptr

    so currentptr gets the value of the address of the first node here.

  9. #9
    Registered User
    Join Date
    Feb 2006
    Posts
    155
    void insert(LISTNODEPTR *sPtr, char value)
    {
    LISTNODEPTR newPtr, previousPtr, currentPtr;
    newPtr = (LISTNODEPTR)malloc(sizeof(LISTNODE));
    if (newPtr != NULL) {
    newPtr->data = value;
    newPtr->nextPtr = NULL;

    previousPtr = NULL;



    currentPtr = *sPtr;
    >currentptr gets the address of the first node.




    while (currentPtr != NULL && value > currentPtr->data) {
    previousPtr = currentPtr; /*walk to...*/
    currentPtr = currentPtr->nextPtr;/*...next node*/
    }
    >goes to the last node




    if (previousPtr == NULL) {
    >if the while loop failed,that means that *sPtr is NULL.
    there was no previous node.



    newPtr->nextPtr = *sPtr;
    >newPtr->nextPTr=NULL,since this is the first node ,there is no next node.



    *sPtr = newPtr;
    >sPtr is reassigned to point to newPtr,or now newPtr becomes the first node
    this was why the double pointer was needed.(why?)
    }


    and so on.

    Code:
     

  10. #10
    Registered User
    Join Date
    Mar 2006
    Location
    Honolulu, HI/United States
    Posts
    12
    thx again as you have helped me a great deal with a problem I was having so much trouble with.

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, 02:19 PM
  2. Adding directory/file names to a linked list
    By thoseion in forum C Programming
    Replies: 13
    Last Post: 12-08-2006, 12:13 PM
  3. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 06:47 PM
  4. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21