Thread: Linked List - Print Backwards

  1. #1
    Registered User
    Join Date
    Jul 2012
    Posts
    1

    Linked List - Print Backwards

    Hi, for my class, I had to modify an example of a linked list from my text book so that it is a doubly linked list. Then I had to prove that myprogram works properly by implementing a print backwards function. Here is the example program from the book:

    Code:
    
    
    Code:
    /* Fig. 12.3: fig12_03.c
       Operating and maintaining a list */
    #include <stdio.h>
    #include <stdlib.h>
     
    /* self-referential structure */
    struct listNode {            
       char data; /* each listNode contains a character */
       struct listNode *nextPtr; /* pointer to next node*/ 
    }; /* end structure listNode */
     
    typedef struct listNode ListNode; /* synonym for struct listNode */
    typedef ListNode *ListNodePtr; /* synonym for ListNode* */
     
    /* prototypes */
    void insert( ListNodePtr *sPtr, char value );
    char delete( ListNodePtr *sPtr, char value );
    int isEmpty( ListNodePtr sPtr );
    void printList( ListNodePtr currentPtr );
    void instructions( void );
     
    int main( void )
    { 
       ListNodePtr startPtr = NULL; /* initially there are no nodes */
       int choice; /* user's choice */
       char item; /* char entered by user */
     
       instructions(); /* display the menu */
       printf( "? " );
       scanf( "%d", &choice );
     
       /* loop while user does not choose 3 */
       while ( choice != 3 ) { 
     
          switch ( choice ) { 
             case 1:
                printf( "Enter a character: " );
                scanf( "\n%c", &item );
                insert( &startPtr, item ); /* insert item in list */
                printList( startPtr );
                break;
             case 2:
                /* if list is not empty */
                if ( !isEmpty( startPtr ) ) { 
                   printf( "Enter character to be deleted: " );
                   scanf( "\n%c", &item );
     
                   /* if character is found, remove it */
                   if ( delete( &startPtr, item ) ) { /* remove item */
                      printf( "%c deleted.\n", item );
                      printList( startPtr );
                   } /* end if */
                   else {
                      printf( "%c not found.\n\n", item );
                   } /* end else */
                } /* end if */
                else {
                   printf( "List is empty.\n\n" );
                } /* end else */
     
                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 insert an element into the list.\n"
          "   2 to delete an element from the list.\n"
          "   3 to end.\n" );
    } /* end function instructions */
     
    /* Insert a new value into the list in sorted order */
    void insert( ListNodePtr *sPtr, char value )
    { 
       ListNodePtr newPtr; /* pointer to new node */
       ListNodePtr previousPtr; /* pointer to previous node in list */
       ListNodePtr currentPtr; /* pointer to current node in list */
     
       newPtr = malloc( sizeof( ListNode ) ); /* create node */
     
       if ( newPtr != NULL ) { /* is space available */
          newPtr->data = value; /* place value in node */
          newPtr->nextPtr = NULL; /* node does not link to another node */
     
          previousPtr = NULL;
          currentPtr = *sPtr;
     
          /* loop to find the correct location in the list */
          while ( currentPtr != NULL && value > currentPtr->data ) { 
             previousPtr = currentPtr; /* walk to ...   */
             currentPtr = currentPtr->nextPtr; /* ... next node */
          } /* end while */
     
          /* insert new node at beginning of list */
          if ( previousPtr == NULL ) { 
             newPtr->nextPtr = *sPtr;
             *sPtr = newPtr;
          } /* end if */
          else { /* insert new node between previousPtr and currentPtr */
             previousPtr->nextPtr = newPtr;
             newPtr->nextPtr = currentPtr;
          } /* end else */
       } /* end if */
       else {
          printf( "%c not inserted. No memory available.\n", value );
       } /* end else */
    } /* end function insert */
     
    /* Delete a list element */
    char delete( ListNodePtr *sPtr, char value )
    { 
       ListNodePtr previousPtr; /* pointer to previous node in list */
       ListNodePtr currentPtr; /* pointer to current node in list */
       ListNodePtr tempPtr; /* temporary node pointer */
     
       /* delete first node */
       if ( value == ( *sPtr )->data ) { 
          tempPtr = *sPtr; /* hold onto node being removed */
          *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
          free( tempPtr ); /* free the de-threaded node */
          return value;
       } /* end if */
       else { 
          previousPtr = *sPtr;
          currentPtr = ( *sPtr )->nextPtr;
     
          /* loop to find the correct location in the list */
          while ( currentPtr != NULL && currentPtr->data != value ) { 
             previousPtr = currentPtr; /* walk to ...   */
             currentPtr = currentPtr->nextPtr; /* ... next node */  
          } /* end while */
     
          /* delete node at currentPtr */
          if ( currentPtr != NULL ) { 
             tempPtr = currentPtr;
             previousPtr->nextPtr = currentPtr->nextPtr;
             free( tempPtr );
             return value;
          } /* end if */
       } /* end else */
     
       return '\0';
    } /* end function delete */
     
    /* Return 1 if the list is empty, 0 otherwise */
    int isEmpty( ListNodePtr sPtr )
    { 
       return sPtr == NULL;
    } /* end function isEmpty */
     
    /* Print the list */
    void printList( ListNodePtr currentPtr )
    { 
       /* if list is empty */
       if ( currentPtr == NULL ) {
          printf( "List is empty.\n\n" );
       } /* end if */
       else { 
          printf( "The list is:\n" );
     
          /* while not the end of the list */
          while ( currentPtr != NULL ) { 
             printf( "%c --> ", currentPtr->data );
             currentPtr = currentPtr->nextPtr;   
          } /* end while */
     
          printf( "NULL\n\n" );
       } /* end else */
    } /* end function printList */


    I have updated this code to make it a doubly linked list with a print backwards function, but I am not getting the correct output. I am having problems when with the list printing in reverse (the reverse list doesnt always print all the letters in the list) and also when I delete characters from the list. I noticed that when I delete letters (other than the last one entered), it holds a different character in place of the letter that was entered to be deleted.

    Here is my current code:

    Code:
    
    
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    struct listNode {
           char data;//each listNode contains a character
           struct listNode *nextPtr; //pointer to next node
           struct listNode *prevPtr; //pointer to previous node
           }; // end structure listNode
           
           typedef struct listNode ListNode; //synonym for struct listNode
           typedef ListNode *ListNodePtr; //synonym for ListNode
           
           /* prototypes */
           void insert( ListNodePtr *sPtr, ListNodePtr *tPtr, char value );
           char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value);
           int isEmpty( ListNodePtr sPtr);
           void printList( ListNodePtr currentPtr );
           void printBack( ListNodePtr currentPtr );
           void instructions(void );
    
    
    int main(int argc, char *argv[])
    {
        ListNodePtr startPtr=NULL; /* initially there are no nodes */
        ListNodePtr tailPtr=NULL;
        int choice; /* user's choice */
        char item; /* char entered by user */
        
        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, &tailPtr, item); /* insert item in list */
                                         printList(startPtr);
                                         printBack(tailPtr);
                                         break;
                                    case 2: /* delete an element */
                                         /* if list is no empty */
                                         if(!isEmpty(startPtr)){
                                                               printf("Enter a character to be deleted: ");
                                                               scanf("\n%c", &item);
                                                               /* if character is found remove it */
                                                               if(deletechar(&startPtr, &tailPtr, item)){ /* remove item */
                                                                                        printf("%c deleted.\n", item);
                                                                                        printList(startPtr);
                                                                                        printBack(tailPtr);
                                                                                        }/* end if */
                                                               else{
                                                                    printf("%c not found.\n\n", item);
                                                                    }/* end else */
                                                               }/* end if */
                                         else{
                                              printf("List is empty.\n\n");
                                              }/* end else */
                                              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*/
    
    
    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");
         }/* end function instructions */
         
         /* Insert a new value into the list in sorted order */
    void insert( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
         ListNodePtr newPtr; //pointer to new node
         ListNodePtr previousPtr; //pointer to previous node in list 
         ListNodePtr currentPtr; //point to current node in list
         
         newPtr = (ListNodePtr)malloc( sizeof( ListNode ) ); //create node
         
         
         if(newPtr!=NULL){ //is space available
              newPtr->data=value; //place value in node
              newPtr->nextPtr=NULL; //node does not link to another node
              previousPtr=NULL;
              currentPtr=*sPtr;
              newPtr->prevPtr=NULL;
                         
              //loop to find the correct location in the list 
              while(currentPtr !=NULL&&value > currentPtr->data){
                               previousPtr=currentPtr; /* walk to ... */
                               currentPtr=currentPtr->nextPtr; /* ... next node*/
              }//end while
              if(previousPtr==NULL){  // inserted at beginning of list
                newPtr->nextPtr=*sPtr;
                *sPtr=newPtr;
    
    
                *tPtr=newPtr;
              }//end if
                else{ //insert new node between previousPtr and currentPtr
                   
                     if(currentPtr!=NULL){ // inserted in the middle
    
    
                         previousPtr->nextPtr=newPtr;
                         newPtr->nextPtr=currentPtr;
    
    
                         currentPtr->prevPtr=newPtr;
                         newPtr->prevPtr=previousPtr;
                     }
                     else{//inserted at end of list
                         *tPtr=newPtr;
                          previousPtr->nextPtr=newPtr;
                          newPtr->prevPtr=previousPtr;
                     }
                } /* end else */
         } /* end if */
         else{
            printf("%c not inserted. no memory available.\n", value);
             }//end else
    }//end function insert
    
    
                 /* delete a list element */  
             char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
              
       ListNodePtr previousPtr; /* pointer to previous node in list */
       ListNodePtr currentPtr; /* pointer to current node in list */
       ListNodePtr tempPtr; /* temporary node pointer */
       
    
    
       if( *sPtr == NULL ){//checks to see if list is empty
           return '\0';
           }
           
       if((*sPtr)==(*tPtr)){//checks to see if start pointer and tail pointer are the same
          *tPtr=NULL;
       }
         
       
       
       /* delete first node */
       if ( value == ( *sPtr )->data)
          {/* Begin if loop */
          tempPtr = *sPtr; /* hold onto node being removed */
          *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
          
          free( tempPtr ); /* free the de-threaded node */
          
         // (*sPtr)->prevPtr = NULL
          return value;
      } /* end if */
    
    
       else { 
          previousPtr = *sPtr;
          currentPtr = ( *sPtr )->nextPtr;
    
    
          
          /* loop to find the correct location in the list */
          while ( currentPtr != NULL && currentPtr->data != value ) { 
             previousPtr = currentPtr; /* walk to ...   */
             currentPtr = currentPtr->nextPtr; /* ... next node */  
          } /* end while */
    
    
          /* delete node at currentPtr */
          if ( currentPtr != NULL ) {  
       tempPtr = currentPtr;
       previousPtr->nextPtr = currentPtr->nextPtr;
       
       free( tempPtr );
       return value;
    }/* end if */
      
             
    
    
          
    
    
       } /* end else */
    
    
       return '\0';
    } /* end function delete */
    
    
    
    
    
    
              
    /* Return 1 if the list is empty, 0 otherwise */
         int isEmpty(ListNodePtr sPtr){
             return sPtr==NULL;
             }/* end function isEmpty */
             
         void printList(ListNodePtr currentPtr){
              //if list is empty
              if(currentPtr==NULL){
                                   printf("List is empty.\n\n");
              }//end if
              else{
                   printf("the list is:\n");
                                    // while not the end of the list                           
                                   while(currentPtr !=NULL){
                                                    printf("%c --> ", currentPtr->data );
                                                    currentPtr=currentPtr->nextPtr;
                                   }//end while
                                                    printf("NULL\n\n");
              }
          }
          void printBack(ListNodePtr currentPtr){
              if(currentPtr==NULL){
                 printf("List is empty.\n\n");
              }
              else{
                 printf("the list in reverse is:\n");                   
                 while(currentPtr !=NULL){
                    printf("%c --> ", currentPtr->data );
                    currentPtr=currentPtr->prevPtr;
                 }
                 printf("NULL\n\n");
              }
              
          }


  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
    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
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    I read your updated code(the second one).I focused on the insert function.I noticed that if i input 's' everything is ok.I have one node with all the pointers point where they should be.Then i input 'a' .'a' is smaller than 's',so we are not going to insert the loop at line 102.As a result previousPtr points to NULL,so we are going to insert the if statement at line 106,which is correct.But then the new node,the one that holds the 'a' is going to be inserted at start of the list,which is also correct,but at line 110 you set the tPtr to the new node!As a result the tail pointer points at first node,but it should point to the second(the last) node.So when you try to print backwards the list,it will initiate printing from where the tail pointer points.The tail pointer now points not to the last node,so we have not the output we want.Got the point?

  4. #4
    Registered User
    Join Date
    Jul 2012
    Posts
    6
    Ok that makes sense...I updated my code, but now when I run my program, it crashes (stops working) after I enter a character...

    Here is the updated code

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    struct listNode {
           char data;//each listNode contains a character
           struct listNode *nextPtr; //pointer to next node
           struct listNode *prevPtr; //pointer to previous node
           }; // end structure listNode
           
    typedef struct listNode ListNode; //synonym for struct listNode
    typedef ListNode *ListNodePtr; //synonym for ListNode
           
    /* prototypes */
    void insert( ListNodePtr *sPtr, ListNodePtr *tPtr, char value );
    char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value);
    int isEmpty( ListNodePtr sPtr);
    void printList( ListNodePtr currentPtr );
    void printBack( ListNodePtr currentPtr );
    void instructions(void );
    
    
    
    
    int main(int argc, char *argv[])
    {
        ListNodePtr startPtr=NULL; /* initially there are no nodes */
        ListNodePtr tailPtr=NULL;
        int choice; /* user's choice (1, 2, or 3) */
        char item; /* character entered by user */
        
        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, &tailPtr, item); /* insert item in list */
                                         printList(startPtr);
                                         printBack(tailPtr);
                                         break;
                                    case 2: /* delete an element */
                                         if(!isEmpty(startPtr)){ /* check to see if list is empty */
                                                               printf("Enter a character to be deleted: ");
                                                               scanf("\n%c", &item);
                                                               /* if character is found remove it */
                                                               if(deletechar(&startPtr, &tailPtr, item)){ /* remove item */
                                                                                        printf("%c deleted.\n", item);
                                                                                        printList(startPtr);
                                                                                        printBack(tailPtr);
                                                                                        }/* end if */
                                                               else{
                                                                    printf("%c not found.\n\n", item);
                                                                    }/* end else */
                                                               }/* end if */
                                         else{
                                              printf("List is empty.\n\n");
                                              }/* end else */
                                              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*/
    
    
    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");
         }/* end function instructions */
         
         /* Insert a new value into the list in sorted order */
    void insert( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
         ListNodePtr newPtr; /* pointer to new node */
         ListNodePtr previousPtr; /* pointer to previous node */
         ListNodePtr currentPtr; /* point to current node in list */
         
         newPtr = (ListNodePtr)malloc( sizeof( ListNode ) ); /* create node */
         previousPtr = (ListNodePtr)malloc( sizeof( ListNode ) ); /* create node */
         currentPtr = (ListNodePtr)malloc( sizeof( ListNode ) ); /* create node */
         
         
         if(newPtr!=NULL){ /* is space available */
          printf("inside insert function - first if statement %c \n", value);   
          printf("*sPtr->data %c \n", *sPtr->data);  
              newPtr->data=value; /* place value in node */
              newPtr->nextPtr=NULL; /* node does not link to another node */
              newPtr->prevPtr=NULL;
              currentPtr=*sPtr;
              previousPtr=currentPtr->prevPtr;
         printf("inside insert function - first if statement %c \n", value);   
         printf("currentPtr->data %c \n", currentPtr->data);     
              /* loop to find the correct location in the list */
              while((currentPtr != NULL) && (value > currentPtr->data)){
                  printf("%c \n", value);
                  printf("%c \n", currentPtr->data);
                  previousPtr=currentPtr;
                  currentPtr=currentPtr->nextPtr; /* ... next node*/
              }//end while
              
              if(currentPtr->prevPtr == NULL){  /* inserted at beginning of list */
                currentPtr->prevPtr=newPtr;
                newPtr->nextPtr=currentPtr;
                *sPtr=newPtr;
         printf("inside insert function - insert at beginning %c \n", value);
              }/* end if */ 
              else {  /* insert new node before the currentPtr */
                  if(currentPtr->nextPtr!=NULL){ /* inserted in the middle */
                      currentPtr->prevPtr=newPtr;
                      previousPtr->nextPtr=newPtr;
                      newPtr->prevPtr=previousPtr;
                      newPtr->nextPtr=currentPtr;
                  }/* end if */
                  else{ /* inserted at end of list (currentPtr->nextPtr is NULL) */
                      currentPtr->nextPtr=newPtr;
                      newPtr->prevPtr=currentPtr;
                      *tPtr=newPtr;
                  } /*end else*/
              } /* end else */
         } /* end if */
         
         else{
            printf("%c not inserted. no memory available.\n", value);
         }/* end else */
    } /* end function insert */
    
    
    
    
    /* delete a list element */  
    char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
              
       ListNodePtr previousPtr; /* pointer to previous node in list */
       ListNodePtr currentPtr; /* pointer to current node in list */
       ListNodePtr tempPtr; /* temporary node pointer */
       
       
       if( *sPtr == NULL ){//checks to see if list is empty
           return '\0';
       } /* end if*/
           
       if((*sPtr)==(*tPtr)){//checks to see if start pointer and tail pointer are the same
          *tPtr=NULL;
       } /* end if */
       
       /* delete first node */
       if ( value == ( *sPtr )->data)
          {/* Begin if loop */
          tempPtr = *sPtr; /* hold onto node being removed */
          *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
          
          free( tempPtr ); /* free the de-threaded node */
          
         // (*sPtr)->prevPtr = NULL
          return value;
          } /* end if */
          
       else { 
          previousPtr = *sPtr;
          currentPtr = ( *sPtr )->nextPtr;
    
    
          /* loop to find the correct location in the list */
          while ( currentPtr != NULL && currentPtr->data != value ) { 
             previousPtr = currentPtr; /* walk to ...   */
             currentPtr = currentPtr->nextPtr; /* ... next node */  
          } /* end while */
          /* delete node at currentPtr */
          if ( currentPtr != NULL ) {  
             tempPtr = currentPtr;
             previousPtr->nextPtr = currentPtr->nextPtr;
             free( tempPtr );
             return value;
             }/* end if */
       } /* end else */
       return '\0';
    } /* end function delete */
    
    
    
    
    /* Return 1 (true) if the list is empty, 0 (false) otherwise */
         int isEmpty(ListNodePtr sPtr){
             if (sPtr == NULL)
             {
               return true; /* list IS empty */
             }
             return false; /* list is not empty */
         }/* end function isEmpty */
             
         void printList(ListNodePtr currentPtr){
              //if list is empty
              if(currentPtr==NULL){
              printf("List is empty.\n\n");
              }//end if
                     else{
                     printf("the list is:\n"); 
                               while(currentPtr !=NULL){ // while not the end of the list  
                               printf("%c --> ", currentPtr->data );
                               currentPtr=currentPtr->nextPtr;
                               }//end while
                               printf("NULL\n\n");
                      } /* end else */
          } /* end function printList */
          
          void printBack(ListNodePtr currentPtr){
              if(currentPtr==NULL){
                 printf("List is empty.\n\n");
              } /* end if */
              else{
                 printf("the list in reverse is:\n");                   
                 while(currentPtr !=NULL){
                    printf("%c --> ", currentPtr->data );
                    currentPtr=currentPtr->prevPtr;
                 } /* end else */
                 printf("NULL\n\n");
              }  /* end function printBack */  
    }

  5. #5
    Registered User
    Join Date
    Jun 2011
    Posts
    4,513
    Quote Originally Posted by pghpens91 View Post
    Ok that makes sense...I updated my code, but now when I run my program, it crashes (stops working) after I enter a character...

    Here is the updated code...
    Is there a reason you have more than one account? I'm guessing you accidentally responded with the wrong one.

  6. #6
    Registered User
    Join Date
    Jul 2012
    Posts
    6
    Quote Originally Posted by Matticus View Post
    Is there a reason you have more than one account? I'm guessing you accidentally responded with the wrong one.
    I couldn't remember my password for this account!

  7. #7
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    First I'm interested what compiler you use:
    Code:
    $ gcc -g -Wall -Wextra -o test test.c
    test.c: In function ‘main’:
    test.c:25:14: warning: unused parameter ‘argc’ [-Wunused-parameter]
    test.c:25:26: warning: unused parameter ‘argv’ [-Wunused-parameter]
    test.c: In function ‘insert’:
    test.c:96:40: error: request for member ‘data’ in something not a structure or union
    test.c: In function ‘isEmpty’:
    test.c:197:19: error: ‘true’ undeclared (first use in this function)
    test.c:197:19: note: each undeclared identifier is reported only once for each function it appears in
    test.c:199:17: error: ‘false’ undeclared (first use in this function)
    test.c:200:6: warning: control reaches end of non-void function [-Wreturn-type]
    After fixing this errors I could run your code.

    Quote Originally Posted by pghpens91 View Post
    I updated my code, but now when I run my program, it crashes (stops working) after I enter a character...
    I assume you mean after pressing '1' for inserting a character into the list, aren't you? (because you have an infinite loop when the user enters not a number for choice in the menu).

    Code:
    $ gdb ./test
    ...
    (gdb) r
    Starting program: ~/test 
    Enter your choice:
           1 to insert an element into the list.
           2 to delete an element from the list.
           3 to end.
    ? 1
    Enter a character: a
    inside insert function - first if statement a 
    
    Program received signal SIGSEGV, Segmentation fault.
    0x08048721 in insert (sPtr=0xbffff0d0, tPtr=0xbffff0d4, value=97 'a')
        at test.c:102
    102              previousPtr=currentPtr->prevPtr;
    gdb is a debugger (you should learn to use one) and it tells us that your program crashes at line 102:

    Code:
    previousPtr=currentPtr->prevPtr;
    Looks ok. currentPtr is a pointer to ListNode and should have a member prevPtr.
    But look at one line above:
    Code:
    currentPtr=*sPtr;
    Looks ok too, doesn't it? currentPtr is a pointer to ListNode and sPtr is a pointer to pointer to ListNode. Dereferencing sPtr before assigning it to currentPtr is correct. Now look at the declarations in main:
    Code:
    ListNodePtr startPtr=NULL; /* initially there are no nodes */
    You have entered the first character thus startPtr (= sPtr in your insert function) is NULL. In insert you try to get the prevPtr-member of currentPtr, but currentPtr is NULL!

    Now back to gdb:
    Code:
    Program received signal SIGSEGV, Segmentation fault.
    0x08048721 in insert (sPtr=0xbffff0d0, tPtr=0xbffff0d4, value=97 'a')
        at test.c:102
    102              previousPtr=currentPtr->prevPtr;
    (gdb) print currentPtr->prevPtr
    Cannot access memory at address 0x8
    (gdb) print currentPtr
    $1 = (ListNodePtr) 0x0
    Isn't debugging easy? :-)

    Bye, Andreas

  8. #8
    Registered User
    Join Date
    Jul 2012
    Posts
    6
    Thanks Andreas.

    It works when I enter my first character, but now crashes after I entered the second one!

    new code:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    struct listNode {
           char data;//each listNode contains a character
           struct listNode *nextPtr; //pointer to next node
           struct listNode *prevPtr; //pointer to previous node
           }; // end structure listNode
           
    typedef struct listNode ListNode; //synonym for struct listNode
    typedef ListNode *ListNodePtr; //synonym for ListNode
           
    /* prototypes */
    void insert( ListNodePtr *sPtr, ListNodePtr *tPtr, char value );
    char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value);
    int isEmpty( ListNodePtr sPtr);
    void printList( ListNodePtr currentPtr );
    void printBack( ListNodePtr currentPtr );
    void instructions(void );
    
    
    
    
    int main(int argc, char *argv[])
    {
        ListNodePtr startPtr=NULL; /* initially there are no nodes */
        ListNodePtr tailPtr=NULL;
        int choice; /* user's choice (1, 2, or 3) */
        char item; /* character entered by user */
        
        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, &tailPtr, item); /* insert item in list */
                                         printList(startPtr);
                                         printBack(tailPtr);
                                         break;
                                    case 2: /* delete an element */
                                         if(!isEmpty(startPtr)){ /* check to see if list is empty */
                                                      
                                                               printf("Enter a character to be deleted: ");
                                                               scanf("\n%c", &item);
                                                               /* if character is found remove it */
                                                               if(deletechar(&startPtr, &tailPtr, item)){ /* remove item */
                                                                                        printf("%c deleted.\n", item);
                                                                                        printList(startPtr);
                                                                                        printBack(tailPtr);
                                                                                        }/* end if */
                                                               else{
                                                                    printf("%c not found.\n\n", item);
                                                                    }/* end else */
                                                               }/* end if */
                                         else{
                                              printf("List is empty.\n\n");
                                              }/* end else */
                                              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*/
    
    
    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");
         }/* end function instructions */
         
         /* Insert a new value into the list in sorted order */
    void insert( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
         ListNodePtr newPtr; /* pointer to new node */
         ListNodePtr previousPtr; /* pointer to previous node */
         ListNodePtr currentPtr; /* point to current node in list */
               
         newPtr = (ListNodePtr)malloc( sizeof( ListNode ) ); /* create node */
    //     previousPtr = (ListNodePtr)malloc( sizeof( ListNode ) ); /* create node */
    //     currentPtr = (ListNodePtr)malloc( sizeof( ListNode ) ); /* create node */
              
         if (newPtr!=NULL){ /* is space available */
              newPtr->data=value; /* place value in node */
              newPtr->nextPtr=NULL; /* node does not link to another node */
              newPtr->prevPtr=NULL;
              currentPtr=*sPtr;
              previousPtr=NULL;
                    /* loop to find the correct location in the list */
              while((currentPtr != NULL) && (value > currentPtr->data)){
                       previousPtr=currentPtr;  
                       currentPtr=currentPtr->nextPtr; /* ... next node*/
              }//end while
       
              if (previousPtr == NULL){  /* inserted at beginning of list */
                  if (currentPtr != NULL) {
                      currentPtr->prevPtr=newPtr;
                  }
                  newPtr->nextPtr=currentPtr;
                  *sPtr=newPtr;
                  *tPtr=newPtr;
              }/* end if */ 
              else {
                   if (currentPtr->nextPtr != NULL) {/* insert in middle (before current) */
                      newPtr->prevPtr=previousPtr;
                      newPtr->nextPtr=currentPtr;
                      currentPtr->prevPtr=newPtr;
                      previousPtr->nextPtr=newPtr;
                   }/* end if */
                   else { /* inserted at end of list */
                        currentPtr->nextPtr=newPtr;
                        newPtr->prevPtr=currentPtr;
                        *tPtr=newPtr;
                   }
              } /* end else*/
          } /* end if */
         
         else{
            printf("%c not inserted. no memory available.\n", value);
         }/* end else */
    } /* end function insert */
    
    
    
    
    /* delete a list element */  
    char deletechar( ListNodePtr *sPtr, ListNodePtr *tPtr, char value){
              
       ListNodePtr previousPtr; /* pointer to previous node in list */
       ListNodePtr currentPtr; /* pointer to current node in list */
       ListNodePtr tempPtr; /* temporary node pointer */
       
       
       if( *sPtr == NULL ){//checks to see if list is empty
           return '\0';
       } /* end if*/
           
       if((*sPtr)==(*tPtr)){//checks to see if start pointer and tail pointer are the same
          *tPtr=NULL;
       } /* end if */
       
       /* delete first node */
       if ( value == ( *sPtr )->data)
          {/* Begin if loop */
          tempPtr = *sPtr; /* hold onto node being removed */
          *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */
          
          free( tempPtr ); /* free the de-threaded node */
          
         // (*sPtr)->prevPtr = NULL
          return value;
          } /* end if */
          
       else { 
          previousPtr = *sPtr;
          currentPtr = ( *sPtr )->nextPtr;
    
    
          /* loop to find the correct location in the list */
          while ( currentPtr != NULL && currentPtr->data != value ) { 
             previousPtr = currentPtr; /* walk to ...   */
             currentPtr = currentPtr->nextPtr; /* ... next node */  
          } /* end while */
          /* delete node at currentPtr */
          if ( currentPtr != NULL ) {  
             tempPtr = currentPtr;
             previousPtr->nextPtr = currentPtr->nextPtr;
             free( tempPtr );
             return value;
             }/* end if */
       } /* end else */
       return '\0';
    } /* end function delete */
    
    
    
    
    /* Return 1 (true) if the list is empty, 0 (false) otherwise */
         int isEmpty(ListNodePtr sPtr){
             if (sPtr == NULL)
             {
               return true; /* list IS empty */
             }
             return false; /* list is not empty */
         }/* end function isEmpty */
             
         void printList(ListNodePtr currentPtr){
              //if list is empty
              if(currentPtr==NULL){
              printf("List is empty.\n\n");
              }//end if
                     else{
                     printf("the list is:\n"); 
                               while(currentPtr !=NULL){ // while not the end of the list  
                               printf("%c --> ", currentPtr->data );
                               currentPtr=currentPtr->nextPtr;
                               }//end while
                               printf("NULL\n\n");
                      } /* end else */
          } /* end function printList */
          
          void printBack(ListNodePtr currentPtr){
              if(currentPtr==NULL){
                 printf("List is empty.\n\n");
              } /* end if */
              else{
                 printf("the list in reverse is:\n");                   
                 while(currentPtr !=NULL){
                    printf("%c --> ", currentPtr->data );
                    currentPtr=currentPtr->prevPtr;
                 } /* end else */
                 printf("NULL\n\n");
              }  /* end function printBack */  
    }

  9. #9
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by pghpens91 View Post
    It works when I enter my first character, but now crashes after I entered the second one!

    new code:
    First, true and false are still not declared in your code (function isEmpty). Either declare them or include the standard header "stdbool.h"

    Second, when do you consider learning to use a debugger? That's probably my last answer to your questions if you don't show some willingness to learn.

    You get the same error (dereferencing a NULL-pointer), when the ASCII value of your second character is bigger than the first. If I enter "a" then "b" the program crashes at line 115:
    Code:
    if (currentPtr->nextPtr != NULL) {/* insert in middle (before current) */
    The reason is that after this while-loop (line 101-104):
    Code:
    /* loop to find the correct location in the list */
    while((currentPtr != NULL) && (value > currentPtr->data)){
        previousPtr=currentPtr;  
        currentPtr=currentPtr->nextPtr; /* ... next node*/
    }//end while
    currentPtr is NULL. That's easy to detect if you single-step through your program.

    Next time you start a program begin with small steps and don't continue working on the next part until the current works.

    Bye, Andreas

  10. #10
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Instead of debugger that Andreas suggested(which of course is highly recommended),you can use printf function in spots into your code where you think something may be wrong.If this spots are ok,then try to get the printf function all over your project in order to check if every single step is ok.The main advantage of debugger is that it points out the exact location of where your program crashes.However with the printf function you can keep control of everything that is happening at every step you wish!

    For debugging function assert is also there for you,but i suggest not learning it now

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. print linked list problem
    By giannis1990 in forum C Programming
    Replies: 8
    Last Post: 05-29-2012, 11:14 AM
  2. Linked list printing out backwards
    By chickenlittle in forum C++ Programming
    Replies: 4
    Last Post: 09-13-2011, 07:41 AM
  3. Replies: 5
    Last Post: 12-11-2010, 12:21 AM
  4. Print backwards? Can someone please help me?
    By matthayzon89 in forum C Programming
    Replies: 11
    Last Post: 04-23-2010, 07:30 AM
  5. Linked List print out
    By axon in forum C++ Programming
    Replies: 6
    Last Post: 10-19-2003, 07:15 PM