Code:
#include <stdio.h>
#include <stdlib.h>
/* self referential structure */
struct listNode {
char data; /* each listNode contains a character */
struct listNode *nextPtr; /* pointer to the 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, char value );
char delete( ListNodePtr *sPtr, char value );
int isEmpty( ListNodePtr sPtr );
void printList( ListNodePtr currentPtr );
void instructions( void );
void printBackwards (ListNodePtr currentPtr );
int main()
{
ListNodePtr startPtr = NULL; /* initially there are no nodes */
int choice; /* users 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 the list */
printList( startPtr );
printBackwards( 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 ) ) {
printf( "%c deleted.\n", item);
printList( startPtr );
printBackwards( 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; /* indicate sucessful 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 of instructions */
/* insert a new value into the list in sorted order */
void insert ( ListNodePtr *sPtr, char value)
{
ListNodePtr newPtr; /* pointer to a new node */
ListNodePtr previousPtr; /* pointer to previous node in list */
ListNodePtr currentPtr; /* pointer to current node on 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 */
newPtr->prevPtr = NULL;
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 */
/* add here , point up stream */
} /* end while */
/* insert new node at begining of list */
if ( previousPtr == NULL ) {
newPtr->nextPtr = *sPtr;
if(*sPtr != NULL)
(*sPtr)->prevPtr = newPtr;
*sPtr = newPtr;
} /* end if */
else { /* insert new node between previousPtr and currentPtr */
newPtr->prevPtr = previousPtr;
previousPtr->nextPtr = newPtr;
newPtr->nextPtr = currentPtr;
if (currentPtr != NULL)
currentPtr->prevPtr = 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 delete ( ListNodePtr *sPtr, char value )
{
ListNodePtr previousPtr; /* pointer to previous node on list */
ListNodePtr currentPtr; /* pointer to current node on list */
ListNodePtr tempPtr; /* temperary 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 correct location on 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 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( " The 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 */
void printBackwards ( ListNodePtr currentPtr )
{
ListNodePtr temp = NULL;
while ( currentPtr != NULL ) {
temp = currentPtr;
currentPtr = currentPtr->nextPtr;
}
printf( "\nThe list in reverse is:\n" );
printf( "NULL" );
currentPtr = temp;
while ( currentPtr != NULL) {
printf( " <-- %c", currentPtr->data );
currentPtr = currentPtr->prevPtr;
}
printf("\n\n");
}