Thread: Understanding linked lists, structures, and pointers

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    182

    Understanding linked lists, structures, and pointers

    This program is a little lengthy but my question is with the main body and first function.

    1. This program has
    typedef ListNode *ListNodePtr;

    Does this mean any struct initialized with ListNodePtr will automatically be a pointer?



    2. Switch case 1 in the main body calls the insert function like so
    insert( &startPtr, item );

    startPtr was declared as type ListNodePtr. Assuming that startPtr is a pointer, why does the function call using the address operator. To get the address the ptr is located at?




    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    struct listNode {
    	char data;
    	struct listNode *nextPtr;
    };
    
    typedef struct listNode ListNode;
    typedef ListNode *ListNodePtr;
    /*  Does this mean any structure declared using ListNodePtr
        will automatically be a pointer without using the * cast?  */
    
    void insert( ListNodePtr *, char );
    char delete( ListNodePtr *, char );
    int isEmpty( ListNodePtr );
    void printList( ListNodePtr );
    void instructions( void );
    
    int main()
    {
    	ListNodePtr startPtr = NULL;
    	int choice;
    	char item;
    
    	instructions();
    	printf( "? " );
    	scanf( "%d", &choice );
    
    	while( choice != 3 ) {
    
    		switch( choice ) {
    			case 1:
    				printf( "Enter a character: " );
    				scanf( "\n%c", &item );
    				/*  startPtr is a pointer.  What does it mean to use the address operator on a pointer?  */
    				insert( &startPtr, item );
    				printList( startPtr );
    				break;
    
    			case 2:
    				if ( !isEmpty( startPtr ) ) {
    					printf( "Enter character to be deleted: " );
    					scanf( "\n%c", &item );
    
    					if ( delete( &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;
    }
    
    
    
    void instructions( void )
    {
    	printf( "Enter your choice:\n"
    		   "   1 to insert an element into the lsit.\n"
    		   "   2 to delete an element from the list.\n"
    		   "   3 to end.\n" );
    }
    
    
    void insert( ListNodePtr *sPtr, char value )
    {
    	ListNodePtr newPtr, previousPtr, currentPtr;
    
    	newPtr = malloc( sizeof( ListNode ) );
    
    	if ( newPtr != NULL ) {
    		newPtr->data = value;
    		newPtr->nextPtr = NULL;
    
    		previousPtr = NULL;
    		currentPtr = *sPtr;
    		/*  Is currentPtr pointing to the value at sPtr or the address of sPtr?  */
    
    		while ( currentPtr != NULL && value > currentPtr->data ) {
    			previousPtr = currentPtr;
    			currentPtr = currentPtr ->nextPtr;
    		}
    
    		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 );
    }
    
    
    char delete( ListNodePtr *sPtr, char value )
    {
    	ListNodePtr previousPtr, currentPtr, tempPtr;
    
    	if ( value == ( *sPtr )->data ) {
    		tempPtr = *sPtr;
    		*sPtr = ( *sPtr )->nextPtr;
    		free( tempPtr );
    		return value;
    	}
    	else {
    		previousPtr = *sPtr;
    		currentPtr = ( *sPtr )->nextPtr;
    
    		while ( currentPtr != NULL && currentPtr->data != value ) {
    			previousPtr = currentPtr;
    			currentPtr = currentPtr->nextPtr;
    		}
    
    		if ( currentPtr != NULL ) {
    			tempPtr = currentPtr;
    			previousPtr->nextPtr = currentPtr->nextPtr;
    			free( tempPtr );
    			return value;
    		}
    	}
    
    	return '\0';
    }
    
    
    int isEmpty( ListNodePtr sPtr )
    {
    	return sPtr == NULL;
    }
    
    
    void printList( ListNodePtr currentPtr )
    {
    	if ( currentPtr == NULL )
    		printf( "List is empty.\n\n" );
    	else {
    		printf( "The list is:\n" );
    
    		while ( currentPtr != NULL ) {
    			printf( "%c --> ", currentPtr->data );
    			currentPtr = currentPtr->nextPtr;
    		}
    
    		printf( "NULL\n\n" );
    	}
    }

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by yougene View Post
    This program is a little lengthy but my question is with the main body and first function.

    1. This program has
    typedef ListNode *ListNodePtr;

    Does this mean any struct initialized with ListNodePtr will automatically be a pointer?
    yes any variable defined to be of type ListNodePtr will be a pointer.
    Quote Originally Posted by yougene View Post
    2. Switch case 1 in the main body calls the insert function like so
    insert( &startPtr, item );

    startPtr was declared as type ListNodePtr. Assuming that startPtr is a pointer, why does the function call using the address operator. To get the address the ptr is located at?
    yes to get at the address of startPtr though imo there is no need for that.
    ofcourse to change it now means changing its prototype and its definition.

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    182
    Thanks.

    It's not my code. I think they wrote it that way to confuse you and make you think about it.

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by itCbitC View Post
    yes to get at the address of startPtr though imo there is no need for that.
    ofcourse to change it now means changing its prototype and its definition.
    Yes, there is, because the function works in such a way that it is required.
    Also, word of advice: do not use typedefs on pointers, because it obfuscated the code!
    Secondly, do not remove the names of parameters in the prototypes.
    http://apps.sourceforge.net/mediawik...arameter_names
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #5
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Code:
    void insert( ListNodePtr *sPtr, char value )
    {
    	ListNodePtr newPtr, previousPtr, currentPtr;
    
    	newPtr = malloc( sizeof( ListNode ) );
    
    	if ( newPtr != NULL ) {
    		newPtr->data = value;
    		newPtr->nextPtr = NULL;
    
    		previousPtr = NULL;
    		currentPtr = *sPtr;
    		/*  Is currentPtr pointing to the value at sPtr or the address of sPtr?  */
    Pointers have values, like every variable does, and the values are memory addresses. foo *bar; means *bar is a foo object.

    So if currentPtr is a ListNodePtr -- which we clearly see -- and *sPtr is a ListNodePtr, this is a pointer assignment.
    Code:
    currentPtr = *sPtr;
    currentPtr points to the same place *sPtr does because they both have the same value. If you then dereferenced currentPtr, you would get a ListNode object, which is like dereferencing *sPtr (like **sPtr).

    Whether typedefing is good or bad really depends on what you need to write, I guess, because it depends on what you associate with the type. FooPtr might be more descriptive to a person than asterisks but you may still need to write *bar for a dereference.

  6. #6
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    Ahh pointers......time for Binky!
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Structures, and pointers to structures
    By iloveitaly in forum C Programming
    Replies: 4
    Last Post: 03-30-2005, 06:31 PM
  2. Linked list probs
    By mouse163 in forum C++ Programming
    Replies: 5
    Last Post: 02-19-2005, 05:41 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Linked Lists & Pointers
    By fkheng in forum C Programming
    Replies: 4
    Last Post: 06-10-2003, 07:26 AM
  5. Freeing pointers in structures
    By jim50498 in forum C Programming
    Replies: 4
    Last Post: 03-08-2002, 12:53 PM