Thread: help! Placement of nodes in a Linked List

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    13

    Exclamation help! Placement of nodes in a Linked List

    hey everyone I am creating a program that creates a linked list and the program has to have a menu to let the user 1.add to the beginning of the list. 2. add to the end of the list. 3. delete a particular character from the list 4. prints the list and 5. exits. I have the whole structure of the program done but I cannot get the adding to the beginning or the end of the list part down. No matter what you do if there is already an "A" or a "C" in the list, if you add "B" it will put the character right in between the "A" and the "C". Please help!
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    /* self-referential structure */
    struct listNode {
    	char data; /* each listnode contains a character */
    	struct listNode *nextPtr;
    };
    	
    typedef struct listNode ListNode ;
    typedef ListNode *ListNodePtr;
    	
    /* prototypes */
    void insertbegin( ListNodePtr *sPtr, char value );
    void insertend( 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; /* init no nodes */
    	int choice;						  /* user's choice */
    	char item;						  /* char entered by user */
    	
    	instructions(); /* display menu */
    	printf("? ");
    	scanf( "%d", &choice );
    	
    	/* loop while user doesn't choose 5 (quit) */
    	while ( choice != 5){
    	
    		switch ( choice ) {
    		
    			case 1:
    				printf( "Enter a character: ");
    				scanf( "\n%c", &item );
    				insertbegin( &startPtr, item ); /* add item to beginning of list */
    				break;
    
    			case 2:
    				printf( "Enter a character: ");
    				scanf( "\n%c", &item );
    				insertend( &startPtr, item ); /* add item  to end of list */
    				break;
    				
    			case 3:
    				/* 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 ) ) {/* delete item from list */
    						printf( "%c deleted.\n", item );
    					}
    					else {
    						printf("%c not found.\n\n", item );
    						}
    					}
    					else {
    						printf("List is empty.\n\n" );
    					}
    				
    				break;
    			
    			case 4:
    				printList( startPtr); /* print list */
    				break;
    			
    			default:
    				printf( "Invalid Choice.\n\n"); 
    				instructions();
    				break;
    				
    			} /* end switch */
    			
    			printf("? ");
    			scanf( "%d", &choice );
    		} /* end while */
    		
    		printf( "End of run.\n" );
    
    return 0;
    
    }
    
    /* display program instructions to user */
    void instructions( void )
    {
    	printf( "Enter your choice:\n"
    		"   1 to insert an element into the beginning of the list.\n"
    		"   2 to insert an element into the end of the list.\n"
    		"   3 to delete an element from the list.\n"
    		"   4 to print the list.\n"
    		"   5 to quit.\n");
    }
    /***************************************************************************/
    void insertbegin( ListNodePtr *sPtr, char value )	/* Insert a new value into the list in sorted order */
    {
    	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;
    			currentPtr = currentPtr->nextPtr;
    		} /* 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 */
    } 
    /***************************************************************************/
    void insertend( ListNodePtr *sPtr, char value )	/* Insert a new value into the list in sorted order */
    {
    	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;
    			currentPtr = currentPtr->nextPtr;
    		} /* 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 */
    } 
    
    /***************************************************************************/
    /* Delete a list element */
    char delete( ListNodePtr *sPtr, char value )
    {
    	ListNodePtr previousPtr;
    	ListNodePtr currentPtr;
    	ListNodePtr tempPtr;
    	
    	/* delete first node */
    	if ( value == ( *sPtr )->data ) {
    		tempPtr = *sPtr;
    		*sPtr =( *sPtr )->nextPtr;
    		free( tempPtr );
    		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;
    			currentPtr = currentPtr->nextPtr;
    		} /* end while */
    		
    		/*delete node at currentPtr */
    		if ( currentPtr != NULL )  {
    			tempPtr = currentPtr;
    			previousPtr->nextPtr = currentPtr->nextPtr;
    			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;
    }
    /***************************************************************************/
    /* Print the list */
    void printList( ListNodePtr currentPtr )
    {
    
    	/* if list is empty */
    	if ( currentPtr == NULL ) {
    		printf("List is empty.\n\n");
    	}
    	else {
    		printf( "The list is:\n" );
    		
    		/* while not the end of the list */
    		while ( currentPtr != NULL ) {
    			printf( "%c ", currentPtr->data );
    			currentPtr = currentPtr->nextPtr;
    		}
    		
    		printf( "\n\n");
    	}
    	
    } /* end function printList */
    thank you!

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Wow. You're not quite getting the idea of a linked list, though.
    The idea is that you have pointers to every node. Not some "normal" node placed on the stack they you're reassigning.
    I don't get the idea with insertbegin and insertend if you're just going to sort the list anyway.

    First error:
    Code:
    		previousPtr - *sPtr;
    In delete.
    Illegal since you're dereferencing sPtr. Even so, you're not reassigning it, so it's useless. Even if not illegal, it will probably not do what you intend.
    previousPtr is not even a pointer, so that's even more weirdness. Perhaps you intended to do =?

    Code:
    	if ( value == ( *sPtr )->data ) {
    In delete, you are dereferencing the pointer AND using ->. sPtr is not **, so that's kinda illegal. Stupid C allows this kind of crap
    Last edited by Elysia; 12-10-2007 at 03:37 AM.
    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.

  3. #3
    Registered User
    Join Date
    Dec 2007
    Posts
    13
    so what does that mean for the code, the delete function works fine its just adding to the beginning and the end im having trouble with

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Code:
    void insertbegin( ListNodePtr *sPtr, char value )	/* Insert a new value into the list in sorted order */
    <sings> One of these things is not like the others... </sings>
    Although I do congratulate you on having code that matches your comments.
    If you want to insert at the beginning of the list, why walk the list to find the correct place to put it? Just put it right there.
    Same for end; just go until you can't go any more, then put a new entry in the list.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Given that inserting an item into a list in order is always more work than simply placing it at either end, you obviously copied the insertion routine from elsewhere and don't understand it.
    Try to understand how the insert routine works. It has everything you need for inserting at either end.
    Last edited by iMalc; 12-11-2007 at 11:21 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by lostmyshadow View Post
    so what does that mean for the code, the delete function works fine its just adding to the beginning and the end im having trouble with
    Your code is flawed. Most likely you're just no giving the right scenario to execute that flawed code, but when it does, be sure it will crash!
    * and -> both DEREFERENCES the pointer (eg accesses the value stored at the address), so in essence you're doing in twice. And what happens if you try to dereference a value that is not a pointer? Exactly. Crash!
    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.

  7. #7
    Registered User
    Join Date
    Dec 2007
    Posts
    13
    here is the correct solution:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct
    {
      char code[25];		// course code
      }course_t;
    
    typedef struct node_s
    {
      course_t item;	// data
      struct node_s *next;	// pointer to the next node
    } node_t;
    
    // Pointer to a node:
    typedef node_t* nodeptr;
    
    /*function prototypes*/
    nodeptr getnode(void);
    void add_begin(nodeptr *head, course_t item);
    void add_end(nodeptr *head, course_t item );
    int del_data(nodeptr *head, char course_code[]);
    void instructions (void);
    void PrintList (nodeptr * ptr);
    		
    /*************************************************************************************/
    void instructions (void) 
    {
    	printf("Enter you choice:\n"
    		"	1 - to insert an element into the beginning of the list\n"
    		"	1 - to insert an element into the beginning of the list\n"
    		"	1 - to delete an element you specify\n"
    		"	1 - to print the list\n"
    		"	1 - exit\n");
    }
    //----------------------------------------------------------
    // Getting a new node: allocates memory for a new node
    //----------------------------------------------------------
    nodeptr getnode(void)
    {
      nodeptr ptr;
    
      ptr = (node_t*) malloc(sizeof(node_t));	// Allocate memory
      return(ptr);			// Return pointer to allocated memory
    } // end getnode
    
    //----------------------------------------------------------
    // Adding a node to the beginning of a list.
    //----------------------------------------------------------
    void add_begin(nodeptr *head,	// head of the list
                   course_t item)	// data of the list
    {
      nodeptr newptr;	// pointer for a new node
    
      newptr = getnode();	// get a new node
      newptr->item = item;	// store data into new node
      newptr->next = *head;	// newnode will point to whatever head was pointing
      *head = newptr;	// new node will be the head
    } // end add_begin
    
    //----------------------------------------------------------
    // Adding a node to the end of a list:
    //----------------------------------------------------------
    void add_end(nodeptr *head,	// head of the list
                 course_t item )	// data of the list
    {
      nodeptr newptr, ptr;
    
      newptr = getnode();	// Get a new node
      newptr->item = item;	// Store data into new node
      newptr->next = NULL;	// Set next of new node to NULL
    
      if (*head == NULL)
      {			// Linked list was empty
        *head = newptr;	// add to beginning
      }
      else
      {			// Linked List was not empty. Find last node.
        ptr = *head;		// point to beginning of list
        while(ptr->next != NULL)	// while it is not the last node,
        { ptr = ptr->next; }	// pass to the next node
        ptr->next = newptr;		// old last node is followed by new node
      }
    
    } // end add_end
    
    
    //----------------------------------------------------------
    // Delete a node with a given data 
    // Returns 1 if a deletion is performed, 0 if no deletion is performed.
    //----------------------------------------------------------
    int del_data(nodeptr *head,		// head of the list
                   char course_code[])	// course code to be deleted
    {
      nodeptr ptr,			// Ptr to current node
              prevptr = NULL;	// Ptr to previous node
      int  ret_val = 0;		// Value to be returned.
    
      if(*head != NULL)		// If list is not empty, then:
      {
        ptr = *head;			// point to beginning of list
        // Traverse list while data not found and not end of list
        while(strcmp(course_code, ptr->item.code) != 0 &&
              ptr->next != NULL)	
        {
          prevptr = ptr;		// Store pointer to previous node
          ptr = ptr->next;		// Pass to the next node
        }
    
        // Check if data is found:
        if(strcmp(course_code, ptr->item.code) == 0)
        {
          ret_val = 1;
          if(ptr == *head)
          { // If found node is the first node, then:
            del_begin(head);		// Delete the first node
          }
          else
          { // Now, prevptr points to prev. node, and ptr points to found node
            prevptr->next = ptr->next;	// Set next of previous node
            free(ptr);			// Free the deleted node
          }
        }
      }
      return (ret_val);
    } // end del_data
    /*************************************************************************************/			
    void PrintList (nodeptr * ptr) {
    
    	if (ptr == NULL) {
    		printf("List is empty!\n");
    		}
    	else {
    		while (ptr != NULL) {
    			printf("%d\t", ptr -> item);
    			ptr = ptr -> *next;
    		}	/* end while */
    	printf("\n");
    	} /* end else */
    }
    /*************************************************************************************/
    int main(void) {
    
    	nodeptr startPtr = NULL;
    	int choice;
    	char item;
    	
    	instructions (); /*display menu*/
    	printf("? ");
    	scanf("%d" , &choice );
    	
    	/* loop while user does not choose 5 */
    	while ( choice != 5 ) {
    	
    		switch ( choice ) {
    			
    			case 1:
    				printf( "Enter a character: ");
    				scanf( "\n%c", &item );
    				add_begin( &startPtr, item ); /* insert item into list */
    				break;
    
    			case 2:
    				printf( "Enter a character: ");
    				scanf( "\n%c", &item );
    				add_end( &startPtr, item ); /* insert item into list */
    				break;
    				
    			case 3:
    				printf( "Enter a character: ");
    				scanf( "\n%c", &item );
    				add_begin( &startPtr, item ); /* insert item into list */
    				break;
    			
    			case 4:
    				printf( "Enter a character: ");
    				scanf( "\n%c", &item );
    				add_begin( &startPtr, item ); /* insert item into list */
    				break;
    			
    			case 5:
    				printf( "Enter a character: ");
    				scanf( "\n%c", &item );
    				add_begin( &startPtr, item ); /* insert item into list */
    				break;
    
    return 0;
    								}/*end switch*/
    					}/* end while */
    } /* end main */

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  3. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 05:20 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM