The existing program currently prompts for input numbers and stores them on a li
ID: 3778783 • Letter: T
Question
The existing program currently prompts for input numbers and stores
them on a linked list. You need to do the following:
1. (10 points) Modify the body of function numberIsOnList() so that it
returns true if the number is on the list, or false otherwise.
You should not change code anywhere else.
2.(15 points) Modify the body of function removeDuplicates() so that it
removes the duplicates from the list, if any. I suggest you use
your function from step 1 to help you.
You should not change code anywhere else.
Follow your TAs instructions for submitting your program into Blackboard.
Before making the above changes, running the program CURRENTLY looks like
the following. Note that the output below DOES NOT correctly find a duplicate
number on the list, and it DOES NOT correctly eliminate duplicates:
CS 141 Fall 2016 in-lab final exam.
How many numbers will you use? 5
Please enter 5 integers: 2 7 5 3 2
List of numbers is: 2 3 5 7 2
Enter the number to look for: 7
7 was found on the list.
After removing duplicates, sorted list is now: 2 2 3 5 7
After implementing the requested changes, running the program would look like:
CS 141 Fall 2016 in-lab final exam.
How many numbers will you use? 5
Please enter 5 integers: 3 5 3 6 8
List of numbers is: 8 6 3 5 3
Enter the number to look for: 3
3 was found on the list.
After removing duplicates, sorted list is now: 3 5 6 8
And running the program again with different inputs would be:
CS 141 Fall 2016 in-lab final exam.
How many numbers will you use? 6
Please enter 6 integers: 8 5 8 4 2 5
List of numbers is: 5 2 4 8 5 8
Enter the number to look for: 3
3 was NOT on the list.
After removing duplicates, sorted list is now: 2 4 5 8
*/
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data; // The data being stored at the node
Node *pNext; // Pointer to the next node
};
//-----------------------------------------------------------------
// Traverse the list and display the data at each node
void displayList( const char *message, Node *pTemp)
{
cout << message;
while( pTemp != NULL) {
cout << pTemp->data << " ";
pTemp = pTemp->pNext;
}
cout << " ";
}//end displayList()
//-----------------------------------------------------------------
// Delete each node on the list
void deleteList( Node *pHead)
{
Node *pTemp; // extra node pointer
// Iterate through the list
while( pHead != NULL) {
// Keep track of node to be deleted
pTemp = pHead;
// Advance head pointer to the next node
pHead = pHead->pNext;
// Delete the old node
delete pTemp;
}
}//end deleteList()
//-----------------------------------------------------------------
// Swap two integer values. This is a utility function used by the
// insertInOrder() function below.
void swap( int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
//-----------------------------------------------------------------
// Create a new node containing the supplied number, and insert it in order
// into the list. The list head pointer could change.
void insertInOrder( Node * &pHead, int number)
{
// Create the node and store the number
Node *pNewNode = new Node;
pNewNode->data = number;
pNewNode->pNext = NULL;
Node *pTemp;
// Now connect the new node into the right spot in the list
// Check if list is empty
if( pHead == NULL) {
pHead = pNewNode;
}
// If there is a single element on the list
else if( pHead->pNext == NULL) {
// If the new number is less than the current head of the list
if( number < pHead->data) {
pNewNode->pNext = pHead;
pHead = pNewNode;
}
else {
// New number is >= the front of the list
pHead->pNext = pNewNode;
}
}
else {
// There is more than one node on the list
pTemp = pHead;
// Find the node that is before where the new node will go, or the end of the list
while( pTemp->pNext != NULL && pNewNode->data > pTemp->data) {
pTemp = pTemp->pNext;
}
// We're now either in the middle of the list, or at the end.
// The new node goes before or after the current node.
if( pNewNode->data < pTemp->data) {
// Add the new node *after* the current spot on the list
pNewNode->pNext = pTemp->pNext;
// Swap the data at pTemp and pNewNode
swap( pNewNode->data, pTemp->data);
}
// New node goes after current node
pTemp->pNext = pNewNode;
}
}// end insertNode()
//-----------------------------------------------------------------
// Prepend a new node with the given number, at the front of the list
void prependNode( Node *&pHead, int number)
{
// Get a new node
Node *pTemp = new Node;
// Store the values into the new node
pTemp->data = number;
pTemp->pNext = pHead;
// Make this new node the new front of the list
pHead = pTemp;
}//end prependNode()
//-----------------------------------------------------------------
// Sort a list. Do this by making a new list, traversing the old
// list one node at a time, inserting its value in order into the new list.
// Then delete the old list, and reset the original list head pointer
// to point to this newly created list.
void sortList( Node *&pOriginalList)
{
// Take each node one at a time and add it to a new, sorted list
// stored in pSortedList
Node *pSortedList = NULL; // front of list for new sorted list
Node *pTemp = pOriginalList; // make a copy of the front of the list
// Iterate through the list and handle values one at a time
while( pTemp!=NULL) {
// Add the current node data to the new list
insertInOrder( pSortedList, pTemp->data);
// advance the pointer on the unsorted list
pTemp = pTemp->pNext;
}
// delete the original list, since all its node values are now stored in order on pSortedList
deleteList( pOriginalList);
// Reset the pointer to the original list to be the new list containing the sorted elements
pOriginalList = pSortedList;
}//end sortList()
//----------------------- *** Part 2 *** --------------------------
// Prompt for numbers and place them on a linked list
void promptForNumbersAndPlaceThemOnALinkedList( Node *&pHead)
{
int howManyNumbers; // How many numbers to read in
int number; // Stores user input
cout << "How many numbers will you use? ";
cin >> howManyNumbers;
cout << "Please enter " << howManyNumbers << " integers: ";
for( int i=0; i<howManyNumbers; i++) {
cin >> number;
prependNode( pHead, number);
}
}//end promptForNumbersAndPlaceThemOnALinkedList()
//---------------------- *** Part 1 for 10 points *** -------------------------
// Return true if number is found on the list, else return false.
bool numberIsOnList( int numberToFind, Node *pHead)
{
// Add your code here for part 1. You should not change code anywhere else.
// ...
return false; // default
}//end numberIsOnList()
//----------------------- *** Part 2 for 15 points *** --------------------------
// Remove the duplicates from the list
void removeDuplicates( Node *&pHead)
{
// Add your code here for part 2. You should not change code anywhere else.
// ...
}//end removeDuplicates()
//------------------------------------------------------------------
// Set up list pointers and drive the rest of the program.
// You should not change any code in main().
int main()
{
Node *pHead = NULL; // head of linked list of numbers
int numberToFind; // Number to search for on linked list
cout << "CS 141 Fall 2016 in-lab final exam. ";
// Make list of numbers and display them.
promptForNumbersAndPlaceThemOnALinkedList( pHead);
displayList( "List of numbers is: ", pHead);
// Prompt for number to find, and see if it is on the linked list.
cout << "Enter the number to look for: ";
cin >> numberToFind;
if( numberIsOnList( numberToFind, pHead)) {
cout << numberToFind << " was found on the list. ";
}
else {
cout << numberToFind << " was NOT on the list. ";
}
// Remove list duplicates, then sort and again display the list
removeDuplicates( pHead);
sortList( pHead);
displayList( "After removing duplicates, sorted list is now: ", pHead);
return 0; // return value to keep C++ happy
}//end main()
Explanation / Answer
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data; // The data being stored at the node
Node *pNext; // Pointer to the next node
};
//-----------------------------------------------------------------
// Traverse the list and display the data at each node
void displayList( const char *message, Node *pTemp)
{
cout << message;
while( pTemp != NULL) {
cout << pTemp->data << " ";
pTemp = pTemp->pNext;
}
cout << " ";
}//end displayList()
//-----------------------------------------------------------------
// Delete each node on the list
void deleteList( Node *pHead)
{
Node *pTemp; // extra node pointer
// Iterate through the list
while( pHead != NULL) {
// Keep track of node to be deleted
pTemp = pHead;
// Advance head pointer to the next node
pHead = pHead->pNext;
// Delete the old node
delete pTemp;
}
}//end deleteList()
//-----------------------------------------------------------------
// Swap two integer values. This is a utility function used by the
// insertInOrder() function below.
void swap( int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
//-----------------------------------------------------------------
// Create a new node containing the supplied number, and insert it in order
// into the list. The list head pointer could change.
void insertInOrder( Node * &pHead, int number)
{
// Create the node and store the number
Node *pNewNode = new Node;
pNewNode->data = number;
pNewNode->pNext = NULL;
Node *pTemp;
// Now connect the new node into the right spot in the list
// Check if list is empty
if( pHead == NULL) {
pHead = pNewNode;
}
// If there is a single element on the list
else if( pHead->pNext == NULL) {
// If the new number is less than the current head of the list
if( number < pHead->data) {
pNewNode->pNext = pHead;
pHead = pNewNode;
}
else {
// New number is >= the front of the list
pHead->pNext = pNewNode;
}
}
else {
// There is more than one node on the list
pTemp = pHead;
// Find the node that is before where the new node will go, or the end of the list
while( pTemp->pNext != NULL && pNewNode->data > pTemp->data) {
pTemp = pTemp->pNext;
}
// We're now either in the middle of the list, or at the end.
// The new node goes before or after the current node.
if( pNewNode->data < pTemp->data) {
// Add the new node *after* the current spot on the list
pNewNode->pNext = pTemp->pNext;
// Swap the data at pTemp and pNewNode
swap( pNewNode->data, pTemp->data);
}
// New node goes after current node
pTemp->pNext = pNewNode;
}
}// end insertNode()
//-----------------------------------------------------------------
// Prepend a new node with the given number, at the front of the list
void prependNode( Node *&pHead, int number)
{
// Get a new node
Node *pTemp = new Node;
// Store the values into the new node
pTemp->data = number;
pTemp->pNext = pHead;
// Make this new node the new front of the list
pHead = pTemp;
}//end prependNode()
//-----------------------------------------------------------------
// Sort a list. Do this by making a new list, traversing the old
// list one node at a time, inserting its value in order into the new list.
// Then delete the old list, and reset the original list head pointer
// to point to this newly created list.
void sortList( Node *&pOriginalList)
{
// Take each node one at a time and add it to a new, sorted list
// stored in pSortedList
Node *pSortedList = NULL; // front of list for new sorted list
Node *pTemp = pOriginalList; // make a copy of the front of the list
// Iterate through the list and handle values one at a time
while( pTemp!=NULL) {
// Add the current node data to the new list
insertInOrder( pSortedList, pTemp->data);
// advance the pointer on the unsorted list
pTemp = pTemp->pNext;
}
// delete the original list, since all its node values are now stored in order on pSortedList
deleteList( pOriginalList);
// Reset the pointer to the original list to be the new list containing the sorted elements
pOriginalList = pSortedList;
}//end sortList()
//----------------------- *** Part 2 *** --------------------------
// Prompt for numbers and place them on a linked list
void promptForNumbersAndPlaceThemOnALinkedList( Node *&pHead)
{
int howManyNumbers; // How many numbers to read in
int number; // Stores user input
cout << "How many numbers will you use? ";
cin >> howManyNumbers;
cout << "Please enter " << howManyNumbers << " integers: ";
for( int i=0; i<howManyNumbers; i++) {
cin >> number;
prependNode( pHead, number);
}
}//end promptForNumbersAndPlaceThemOnALinkedList()
//---------------------- *** Part 1 for 10 points *** -------------------------
// Return true if number is found on the list, else return false.
bool numberIsOnList( int numberToFind, Node *pHead)
{
Node *pTemp=pHead;
bool f=false;
while( pTemp != NULL) {
if(pTemp->data == numberToFind)
{
f=true;
break;
}
pTemp = pTemp->pNext;
}
return f; // default
}//end numberIsOnList()
//----------------------- *** Part 2 for 15 points *** --------------------------
// Remove the duplicates from the list
void removeDuplicates( Node *&pHead)
{
Node *pTemp=pHead;
Node *t, *t2;
while( pTemp != NULL) {
t=pTemp->pNext;
if(t!=NULL && pTemp->data==t->data)
{
pTemp->pNext=t->pNext;
}
else
{
if(t!=NULL) t2=t->pNext;
while(t2!=NULL)
{
if(pTemp->data == t2->data)
{
t=t2->pNext;
}
else
t=t->pNext;
t2 = t2->pNext;
}
pTemp=pTemp->pNext;
}
}
}//end removeDuplicates()
//------------------------------------------------------------------
// Set up list pointers and drive the rest of the program.
// You should not change any code in main().
int main()
{
Node *pHead = NULL; // head of linked list of numbers
int numberToFind; // Number to search for on linked list
cout << "CS 141 Fall 2016 in-lab final exam. ";
// Make list of numbers and display them.
promptForNumbersAndPlaceThemOnALinkedList( pHead);
displayList( "List of numbers is: ", pHead);
// Prompt for number to find, and see if it is on the linked list.
cout << "Enter the number to look for: ";
cin >> numberToFind;
if( numberIsOnList( numberToFind, pHead)) {
cout << numberToFind << " was found on the list. ";
}
else {
cout << numberToFind << " was NOT on the list. ";
}
// Remove list duplicates, then sort and again display the list
removeDuplicates( pHead);
sortList( pHead);
displayList( "After removing duplicates, sorted list is now: ", pHead);
return 0; // return value to keep C++ happy
}//end main()
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.