1) merge current list with a built in list A->G->H into single ordered list

I am having trouble creating this merge function basically the built in list which is A G H has to merge with the current list but the merge has to be in order. For example if the user enters 1 and enters two characters B and C the current list is B->C->NULL then the user chooses the fourth option to merge the built in list "A->G->H". The output should be A->B->C->G->H->NULL. Please put the function merge into the code below and provide sample output.

/* Fig. 12.3: fig12_03.c Operating and maintaining a list, which adds characters in alphabetical (ASCII) order */ #include #include

/* 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 );

void concat(ListNodePtr *sPtr);

int main() { ListNodePtr startPtr = NULL; /* initially there are no nodes */ int choice = 0; /* user's choice */ char item = 0; /* char entered by user */

instructions(); /* display the menu */ printf( "? " ); scanf( "%d", &choice );

/* loop while user does not choose 3 */ while ( choice != 5 ) {

switch ( choice ) {

case 1: printf( "Enter a character: " ); scanf( " %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( " %c", &item );

/* if character is found, remove it */ if ( delete( &startPtr, item ) ) { /* remove item */ printf( "%c deleted. ", item ); printList( startPtr ); } /* end if */ else { printf( "%c not found. ", item ); } /* end else */

} /* end if */ else { printf( "List is empty. " ); } /* end else */

break; case 3: concat( &startPtr); /* Concat DEF in list */ printList( startPtr ); break;

default: printf( "Invalid choice. " ); instructions(); break; } /* end switch */

printf( "? " ); scanf( "%d", &choice ); } /* end while */

printf( "End of run. " ); return 0; /* indicates successful termination */

} /* end main */

/* display program instructions to user */ void instructions( void ) { printf( "Enter your choice: " " 1 to insert an element into the list. " " 2 to delete an element from the list. " " 3 concatenate the built in list with D->E->F. 5 to end. "); } /* end function instructions */

void concat(ListNodePtr *sPtr){ ListNodePtr newPtr = malloc( sizeof( ListNode ) ); newPtr->nextPtr = NULL; ListNodePtr currentPtr = *sPtr; newPtr->nextPtr = NULL; while(currentPtr->nextPtr !=NULL) currentPtr = currentPtr->nextPtr; newPtr->data = 'D'; currentPtr->nextPtr = newPtr; currentPtr = currentPtr->nextPtr; newPtr = malloc( sizeof( ListNode ) ); newPtr->nextPtr = NULL; newPtr->data = 'E'; currentPtr->nextPtr = newPtr; currentPtr = currentPtr->nextPtr; newPtr = malloc( sizeof( ListNode ) ); newPtr->nextPtr = NULL; newPtr->data = 'F'; currentPtr->nextPtr = newPtr; }

/* Insert a new value into the list in sorted order */ void insert( ListNodePtr *sPtr, char value ) { ListNodePtr newPtr = NULL; /* pointer to new node */ ListNodePtr previousPtr = NULL; /* pointer to previous node in list */ ListNodePtr currentPtr = NULL; /* pointer to current node in list */

newPtr = malloc( sizeof( ListNode ) ); /* create node on heap */

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. ", value ); } /* end else */

} /* end function insert */

/* Delete a list element */ char delete( ListNodePtr *sPtr, char value ) { ListNodePtr previousPtr = NULL; /* pointer to previous node in list */ ListNodePtr currentPtr = NULL; /* pointer to current node in list */ ListNodePtr tempPtr = NULL; /* 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. " ); } /* end if */ else { printf( "The list is: " );

/* while not the end of the list */ while ( currentPtr != NULL ) { printf( "%c --> ", currentPtr->data ); currentPtr = currentPtr->nextPtr; } /* end while */

printf( "NULL " ); } /* end else */

} /* end function printList */