I am stuck on this particular question, Please try and modify the linked list ex
ID: 663487 • Letter: I
Question
I am stuck on this particular question, Please try and modify the linked list example given so that it is a doubly linked list. Prove that the program works properly by implementing a print backwards function.
Code must store in order.
You can redefine Node as:
struct listNode
{ char data;
struct listNode *nextPtr;
struct listNode *prevPtr;
};
Here is an example session of the program
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
The list is:
a --> NULL
The list in reverse is:
a --> NULL
? 1
Enter a character: z
The list is:
a --> z --> NULL
The list in reverse is:
z --> a --> NULL
? 1
Enter a character: n
The list is:
a --> n --> z --> NULL
The list in reverse is:
z --> n --> a --> NULL
? 1
Enter a character: d
The list is:
a --> d --> n --> z --> NULL
The list in reverse is:
z --> n --> d --> a --> NULL
? 2
Enter character to be deleted: x
x not found.
? 2
Enter character to be deleted: n
n deleted.
The list is:
a --> d --> z --> NULL
The list in reverse is:
z --> d --> a --> NULL
? 2
Enter character to be deleted: a
a deleted.
The list is:
d --> z --> NULL
The list in reverse is:
z --> d --> NULL
? 2
Enter character to be deleted: z
z deleted.
The list is:
d --> NULL
The list in reverse is:
d --> NULL
? 2
Enter character to be deleted: d
d deleted.
List is empty.
? 1
Enter a character: s
The list is:
s --> NULL
The list in reverse is:
s --> NULL
? 1
Enter a character: t
The list is:
s --> t --> NULL
The list in reverse is:
t --> s --> NULL
? 3
End of run.
Press any key
Here is the code that can be cut and pasted
#include
#include
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( " %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;
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 to end. " );
} /* 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. ", 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 '';
} /* 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 */
I am really stuck on this, any help would be appreciated.
Explanation / Answer
Answer:
The modified code is as follows,
#include<stdio.h>
#include<conio.h>
struct listNode
{ char data;
struct listNode *nextPtr;
struct listNode *prevPtr;
}; /* end structure listNode */
typedef struct listNode ListNode; /* synonym for struct listNode */
typedef ListNode *ListNodePtr; /* synonym for ListNode* */
/* prototypes */
void insert( ListNodePtr *sPtr, ListNodePtr *ePtr,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 */
ListNodePtr endPtr=NULL;
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( " %c", &item );
insert( &startPtr,&endPtr, 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;
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 to end. " );
} /* end function instructions */
/* Insert a new value into the list in sorted order */
void insert( ListNodePtr *sPtr,ListNodePtr *ePtr, 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 */
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 */
} /* end while */
/* insert new node at beginning of list */
if ( previousPtr == NULL ) {
newPtr->prevPtr=*sPtr;
newPtr->nextPtr = *sPtr;
*sPtr = newPtr;
*ePtr=newPtr;
} /* end if */
else { /* insert new node between previousPtr and currentPtr */
currentPtr=previousPtr->nextPtr;
previousPtr->nextPtr = newPtr;
newPtr->prevPtr=previousPtr;
newPtr->nextPtr = currentPtr;
currentPtr->prevPtr=newPtr;
} /* end else */
*ePtr=*sPtr;
while((*ePtr)->nextPtr!=NULL)
{
(*ePtr)=(*ePtr)->nextPtr;
}
} /* 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; /* 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;
currentPtr->nextPtr->prevPtr=currentPtr->prevPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
free( tempPtr );
return value;
} /* end if */
} /* end else */
return '';
} /* 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 )
{
ListNodePtr tempPtr;
/* 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 */
while(currentPtr!=NULL)
{
tempPtr=currentPtr->prevPtr;
currentPtr->prevPtr=currentPtr->nextPtr;
currentPtr->nextPtr=tempPtr;
currentPtr=currentPtr->prevPtr;
}
if(tempPtr!=NULL)
currentPtr=tempPtr->prevPtr;
printf("list in reversed order");
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 */
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.