in Microsoft Visual Studio... This is a two week assignment. Modify the linked l
ID: 3853101 • Letter: I
Question
in Microsoft Visual Studio...
This is a two week assignment. Modify the linked list example in the book so that it is a doubly linked list. Prove that your program works properly by implementing a print backwards function. The book's code (6th edition) is at the end of the example output. You can just cut and paste it to get started. NOTE: this is a C program – if you compile it as C++ you cannot use delete as that is a reserved keyword. Also, since C++ is strongly typed, you must cast pointer allocations to the correct type.
You must understand the singly linked list code before you can start the doubly linked list code. Your code must store in order.
If you have problems with improperly assigned pointers
You can redefine Node as:
NOTE: I will be testing your code using the following sequence in this exact order – Insert b a z k g m
This tests the 4 basic cases. Insert/delete on an empty list, insert/delete at the beginning, insert/delete at the end, insert/delete at the end.
Example Program Session:
?1
Enter a character: a The list is:
a --> NULL
The list in reverse is: a --> NULL
?1
?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
?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 to continue . . .
Here is the code from the book which you can cut and paste:
/* 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 );
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 );
printf( "Enter a character: " );
scanf( " %c", &item );
insert( &startPtr, item ); /* insert item in list */ printList( startPtr );
break;
printf( "Enter character to be deleted: " ); scanf( " %c", &item );
/* if character is found, remove it */
if ( delete( &startPtr, item ) ) { /* remove item */
return 0; /* indicates successful termination */ } /* end main */
/* display program instructions to user */ void instructions( void )
{
/* 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 */
/* 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 */
*sPtr = newPtr;
} /* end if */
else { /* insert new node between previousPtr and currentPtr */
printf( "%c not inserted. No memory available. ", value ); } /* end else */
/* 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 */
tempPtr = *sPtr; /* hold onto node being removed */ *sPtr = ( *sPtr )->nextPtr; /* de-thread the node */ free( tempPtr ); /* free the de-threaded node */ return value;
/* 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 */
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr; free( tempPtr );
return value;
/* Return 1 if the list is empty, 0 otherwise */ int isEmpty( ListNodePtr sPtr )
{
/* Print the list */
void printList( ListNodePtr currentPtr ) {
printf( "%c --> ", currentPtr->data );
currentPtr = currentPtr->nextPtr; } /* end while */
} /* end function printList */
Explanation / Answer
void linkedList::remove(string s)
{
bool found = false;
node *curr = getTop(), *prev=NULL;
while(curr != NULL){
if(curr->name == s){
found = true;
if(prev == NULL){
node *temp = getTop();
setTop(curr->next);
delete(temp);
}
else{
prev->next = curr->next;
delete(curr);
}
}
if(!found){
prev = curr;
curr = curr->next;
}
else curr = NULL;
}
if(found)cout << "Deleted " << s << endl;
else cout << s << " Not Found "<< endl;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.