Thread: Create a doubly linked list and a print backwards function.

  1. #1
    Registered User
    Join Date
    Dec 2010
    Posts
    3

    Question Create a doubly linked list and a print backwards function.

    I have to create a doubly linked list and a print backwards function. I have the following code. Can someone please help me out here!? Under case 1 if u comment out reverse ( headPtr ) the program will run fine and you can see everything working. But I still need it to print backwards. Thank you in advance.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    /* self-referential structure */
    	struct listNode {   
    	   char data;
    	   struct listNode *nextPtr; 
    	   struct listNode *prevPtr; 
    	};
    
    typedef struct listNode listNode;
    typedef listNode *listNodePtr;
    
    /* function prototypes */
    	void printQueue( listNodePtr currentPtr );
    	int isEmpty( listNodePtr headPtr );
    	char dequeue( listNodePtr *headPtr, listNodePtr *tailPtr );
    	void enqueue( listNodePtr *headPtr, listNodePtr *tailPtr, 
    	   char value );
    	void instructions( void );
    
    /* function main begins program execution */
    int main( void )
    { 
       listNodePtr headPtr = NULL; /* initialize headPtr */
       listNodePtr tailPtr = NULL; /* initialize tailPtr */
       int choice; /* user's menu choice */
       char item; /* char input by user */
    
       instructions(); /* display the menu */
       printf( "? " );
       scanf( "%d", &choice );
    
       /* while user does not enter 3 */
       while ( choice != 3 ) { 
    
          switch( choice ) { 
             /* enqueue value */
             case 1:
                printf( "Enter a character: " );
                scanf( "\n%c", &item );
                enqueue( &headPtr, &tailPtr, item );
                printQueue( headPtr );
                reverse( headPtr );
                break;
             /* dequeue value */
             case 2:
                /* if queue is not empty */
                if ( !isEmpty( headPtr ) ) { 
                   item = dequeue( &headPtr, &tailPtr );
                   printf( "%c has been dequeued.\n", item );
                } /* end if */
    
                printQueue( headPtr );
                break;
             default:
                printf( "Invalid choice.\n\n" );
                instructions();
                break;
          } /* end switch */
    
          printf( "? " );
          scanf( "%d", &choice );
       } /* end while */
    
       printf( "End of run.\n" );
       return 0; /* indicates successful termination */
    } /* end main */
    
    /* display program instructions to user */
    void instructions( void )
    { 
       printf ( "Enter your choice:\n"
               "   1 to add an item to the queue\n"
               "   2 to remove an item from the queue\n"
               "   3 to end\n" );
    } /* end function instructions */
    
    /* insert a node a queue tail */
    void enqueue( listNodePtr *headPtr, listNodePtr *tailPtr, 
       char value )
    { 
       listNodePtr newPtr; /* pointer to new node */
    
       newPtr = malloc( sizeof( listNode ) );
    
       if ( newPtr != NULL ) { /* is space available */ 
          newPtr->data = value;
          newPtr->nextPtr = NULL;
    
          /* if empty, insert node at head */
          if ( isEmpty( *headPtr ) ) {
             *headPtr = newPtr;
          } /* end if */
          else {
             ( *tailPtr )->nextPtr = newPtr;
          } /* end else */
    
          *tailPtr = newPtr;
       } /* end if */
       else {
          printf( "%c not inserted. No memory available.\n", value );
       } /* end else */
    } /* end function enqueue */
    
    /* remove node from queue head */
    char dequeue( listNodePtr *headPtr, listNodePtr *tailPtr )
    { 
       char value; /* node value */
       listNodePtr tempPtr; /* temporary node pointer */
    
       value = ( *headPtr )->data;
       tempPtr = *headPtr;
       *headPtr = ( *headPtr )->nextPtr;
    
       /* if queue is empty */
       if ( *headPtr == NULL ) {
          *tailPtr = NULL;
       } /* end if */
    
       free( tempPtr );
       return value;
    } /* end function dequeue */
    
    /* Return 1 if the list is empty, 0 otherwise */
    int isEmpty( listNodePtr headPtr )
    { 
       return headPtr == NULL;
    } /* end function isEmpty */
    
    /* Print the queue */
    void printQueue( listNodePtr currentPtr )
    { 
       /* if queue is empty */
       if ( currentPtr == NULL ) {
          printf( "Queue is empty.\n\n" );
       } /* end if */
       else { 
          printf( "The queue is:\n" );
    
          /* while not end of queue */
          while ( currentPtr != NULL ) { 
             printf( "%c --> ", currentPtr->data );
             currentPtr = currentPtr->nextPtr;
          } /* end while */
    
          printf( "NULL\n\n" );
       } /* end else */
    } /* end function printQueue */
    
    void reverse( listNodePtr currentPtr)  
    {  
       struct listNode *temp = NULL;   
    
    	 /* if queue is empty */
       if ( currentPtr == NULL ) {
          printf( "Queue is empty.\n\n" );
       } /* end if */
       else { 
          printf( "The queue backwards is:\n" );
         /* swap next and prevPtr for all listNodes of  
           doubly linked list */ 
         while (currentPtr !=  NULL)  
         {  
    	    temp = currentPtr->prevPtr;  
    		currentPtr->prevPtr = currentPtr->nextPtr;  
    		currentPtr->nextPtr = temp;  
    		currentPtr = currentPtr->prevPtr;
            printf( "%c --> ", currentPtr->data);  
         }        
       }
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    To print reverse, you start at tailPtr and do current = current->prevPtr

    You don't need to reorder the entire list.
    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.

  3. #3
    Registered User
    Join Date
    Dec 2010
    Posts
    3
    Can you show me what the code would look like please? Also do you know why I get an erro when I put reverse( headptr ) under case 1?

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Yes, it looks like printQueue() with a search and replace.
    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.

  5. #5
    Registered User
    Join Date
    Dec 2010
    Posts
    3
    Thank you very much for your help so far, so do you mean all I do is copy the printQueue code, replace nextPtr with prevPtr and that's it?

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Have you tried it yet?
    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.

Popular pages Recent additions subscribe to a feed