Question
In: Computer Science
In C++ please modify the following program and add characters (char) and names (strings) to be...
In C++ please modify the following program and add characters (char) and names (strings) to be added to the linked list along with integers. The current demo program accepts only integer data, so you would ask the user to select the data type to be added to the linked list. The user should be given the following three choices:
(a) whole numbers
(b) single characters
(c) strings
Once the user makes a selection from the list above then your program should be able to process the data appropriately. This includes:
(a) insert
(b) print
(c) delete
(d) search
(e) copy
You will use the following existing code and modify it to process char and string data type.
Please upload .cpp file(s) along with screenshots of all solutions/screens. You can take a screenshot of your solutions by hitting PrintScreen button on your keyboard and then by pasting that image into a Word document.
Code:
//This program tests various operation of a linked list
//45 67 23 89 -999
#include
#include
using namespace std;
template
struct nodeType
{
Type info;
nodeType *link;
};
template
class circularLinkedList
{
public:
//Overloads the assignment operator.
const circularLinkedList& operator=(const circularLinkedList& otherList)
{
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
}//end else
return *this;
}
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL,
// count = 0
void initializeList()
{
destroyList();
}
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty; otherwise, returns false.
bool isEmptyList()
{
return (first == NULL);
}
void print() const
{
nodeType *current; //pointer to traverse the list
current = first->link;
while (current != first) //while more data to print
{
cout << current->info << " ";
current = current->link;
}
cout << first->info << " ";
}
//Function to return the number of nodes in the list.
//Postcondition: The value of count is returned.
int length()
{
return count;
}
//Function to delete all the nodes from the list.
//Postcondition: first = NULL, last = NULL,
// count = 0
void destroyList()
{
nodeType *temp;
nodeType *current = NULL;
if (first != NULL)
{
current = first->link;
first->link = NULL;
}
while (current != NULL)
{
temp = current;
current = current->link;
delete temp;
}
first = NULL; //initialize last to NULL; first has already
//been set to NULL by the while loop
count = 0;
}
//Function to return the first element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, then the program terminates; otherwise, the first element of the list is returned.
Type front()
{
assert(first != NULL);
return first->link->info; //return the info of the first node
}
//Function to return the last element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, then the program terminates; otherwise, the last element of the list is returned.
Type back()
{
assert(first != NULL);
return first->info; //return the info of the first node
}
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is found in the list; otherwise, it returns false.
bool search(const Type& searchItem)
{
nodeType *current; //pointer to traverse the list
bool found = false;
if (first != NULL)
{
current = first->link;
while (current != first && !found)
{
if (current->info >= searchItem)
found = true;
else
current = current->link;
found = (current->info == searchItem);
}
}
return found;
}
void insertNode(const Type& newitem)
{
nodeType *current; //pointer to traverse the list
nodeType *trailCurrent; //pointer just before current
nodeType *newNode; //pointer to create a node
bool found;
newNode = new nodeType; //create the node
newNode->info = newitem; //store newitem in the node
newNode->link = NULL; //set the link field of the node
//to NULL
if (first == NULL) //Case 1 e.g., 3
{
first = newNode;
first->link = newNode;
count++;
}
else
{
if (newitem >= first->info)//e.g., 25 > 3
{
newNode->link = first->link;
first->link = newNode;
first = newNode;
}
else
{
trailCurrent = first; //e.g., 1 < 3
current = first->link;
found = false;
while (current != first && !found)
if (current->info >= newitem)
found = true;
else
{
trailCurrent = current;
current = current->link;
}
trailCurrent->link = newNode;
newNode->link = current;
}
count++;
}//end else
}
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing deleteItem is deleted from the list, first points to the first
// node, and last points to the last node of the updated list.
void deleteNode(const Type& deleteItem)
{
nodeType *current; //pointer to traverse the list
nodeType *trailCurrent; //pointer just before current
bool found;
if (first == NULL) //Case 1; list is empty.
cout << "Can not delete from an empty list." << endl;
else
{
found = false;
trailCurrent = first;
current = first->link;
while (current != first && !found)
if (current->info >= deleteItem)
found = true;
else
{
trailCurrent = current;
current = current->link;
}
if (current == first)
{
if (first->info == deleteItem)
{
if (first == first->link)
first = NULL;
else
{
trailCurrent->link = current->link;
first = trailCurrent;
}
delete current;
count--;
}
else
cout << "The item to be deleted is not in the list." << endl;
}
else
if (current->info == deleteItem)
{
trailCurrent->link = current->link;
count--;
delete current;
}
else
cout << "Item to be deleted is not in the list." << endl;
} //end else
}
//Default constructor
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL,
// count = 0
circularLinkedList()
{
first = NULL;
count = 0;
}
//Copy constructor
circularLinkedList(const circularLinkedList& otherList)
{
first = NULL;
copyList(otherList);
}
//Destructor
//Deletes all the nodes from the list.
//Postcondition: The list object is destroyed.
~circularLinkedList()
{
destroyList();
}
protected:
int count; //variable to store the number of elements in the list
nodeType *first; //pointer to the first node of the list
nodeType *last; //pointer to the last node of the list
private:
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and assigned to this list.
void copyList(const circularLinkedList& otherList)
{
nodeType *newNode;
nodeType *current;
nodeType *tempFirst;
if (first != NULL)
destroyList();
if (otherList.first == NULL)
{
first = NULL;
count = 0;
}
else
{
current = otherList.first->link; //current points to the
//list to be copied
count = otherList.count;
//copy the first node
tempFirst = new nodeType; //create the node
tempFirst->info = current->info; //copy the info
last = tempFirst; //make last point to the
//first node
current = current->link; //make current point to the
//next node
//copy the remaining list
while (current != otherList.first)
{
newNode = new nodeType; //create a node
newNode->info = current->info;
last->link = newNode;
last = newNode;
current = current->link;
}//end while
if (tempFirst == last)
{
first = tempFirst;
first->link = first;
}
else
{
newNode = new nodeType; //create a node
newNode->info = current->info;
last->link = newNode;
first = newNode;
first->link = tempFirst;
}
}//end else
}
};
int main()
{
circularLinkedList list1, list2;
int num;
cout << "Enter number ending with -999" << endl;
cin >> num;
while (num != -999)
{
list1.insertNode(num);
cin >> num;
}
cout << endl;
cout << "List 1: ";
list1.print();
cout << endl;
cout << "Length List 1: " << list1.length() << endl;
cout << "Enter the number to be searched: ";
cin >> num;
cout << endl;
if (list1.search(num))
cout << num << " found in the list" << endl;
else
cout << num << " not in the list" << endl;
cout << "Enter the number to be deleted: ";
cin >> num;
cout << endl;
list1.deleteNode(num);
cout << "After deleting the node, "
<< "List 1: ";
list1.print();
cout << endl;
cout << "Length List 1: " << list1.length() << endl;
list2 = list1;
cout << "List 2: ";
list2.print();
cout << endl;
cout << "Length List 2: " << list2.length() << endl;
cout << "List 1: ";
list1.print();
cout << endl;
return 0;
}
Solutions
Expert Solution
#include <iostream>
using namespace std;
template <class Type>
struct nodeType
{
Type info;
nodeType *link;
};
template <class Type>
class circularLinkedList
{
public:
//Overloads the assignment operator.
const circularLinkedList& operator=(const circularLinkedList& otherList)
{
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
}//end else
return *this;
}
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL,
// count = 0
void initializeList()
{
destroyList();
}
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty; otherwise, returns false.
bool isEmptyList()
{
return (first == NULL);
}
void print() const
{
nodeType<Type> *current; //pointer to traverse the list
current = first->link;
while (current != first) //while more data to print
{
cout << current->info << " ";
current = current->link;
}
cout << first->info << " ";
}
//Function to return the number of nodes in the list.
//Postcondition: The value of count is returned.
int length()
{
return count;
}
//Function to delete all the nodes from the list.
//Postcondition: first = NULL, last = NULL,
// count = 0
void destroyList()
{
nodeType<Type> *temp;
nodeType<Type> *current = NULL;
if (first != NULL)
{
current = first->link;
first->link = NULL;
}
while (current != NULL)
{
temp = current;
current = current->link;
delete temp;
}
first = NULL; //initialize last to NULL; first has already
//been set to NULL by the while loop
count = 0;
}
//Function to return the first element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, then the program terminates; otherwise, the first element of the list is returned.
Type front()
{
assert(first != NULL);
return first->link->info; //return the info of the first node
}
//Function to return the last element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, then the program terminates; otherwise, the last element of the list is returned.
Type back()
{
assert(first != NULL);
return first->info; //return the info of the first node
}
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is found in the list; otherwise, it returns false.
bool search(const Type& searchItem)
{
nodeType<Type> *current; //pointer to traverse the list
bool found = false;
if (first != NULL)
{
current = first->link;
while (current != first && !found)
{
if (current->info >= searchItem)
found = true;
else
current = current->link;
found = (current->info == searchItem);
}
}
return found;
}
void insertNode(const Type& newitem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
nodeType<Type> *newNode; //pointer to create a node
bool found;
newNode = new nodeType<Type>; //create the node
newNode->info = newitem; //store newitem in the node
newNode->link = NULL; //set the link field of the node
//to NULL
if (first == NULL) //Case 1 e.g., 3
{
first = newNode;
first->link = newNode;
count++;
}
else
{
if (newitem >= first->info)//e.g., 25 > 3
{
newNode->link = first->link;
first->link = newNode;
first = newNode;
}
else
{
trailCurrent = first; //e.g., 1 < 3
current = first->link;
found = false;
while (current != first && !found)
if (current->info >= newitem)
found = true;
else
{
trailCurrent = current;
current = current->link;
}
trailCurrent->link = newNode;
newNode->link = current;
}
count++;
}//end else
}
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing deleteItem is deleted from the list, first points to the first
// node, and last points to the last node of the updated list.
void deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if (first == NULL) //Case 1; list is empty.
cout << "Can not delete from an empty list." << endl;
else
{
found = false;
trailCurrent = first;
current = first->link;
while (current != first && !found)
if (current->info >= deleteItem)
found = true;
else
{
trailCurrent = current;
current = current->link;
}
if (current == first)
{
if (first->info == deleteItem)
{
if (first == first->link)
first = NULL;
else
{
trailCurrent->link = current->link;
first = trailCurrent;
}
delete current;
count--;
}
else
cout << "The item to be deleted is not in the list." << endl;
}
else
if (current->info == deleteItem)
{
trailCurrent->link = current->link;
count--;
delete current;
}
else
cout << "Item to be deleted is not in the list." << endl;
} //end else
}
//Default constructor
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL,
// count = 0
circularLinkedList()
{
first = NULL;
count = 0;
}
//Copy constructor
circularLinkedList(const circularLinkedList& otherList)
{
first = NULL;
copyList(otherList);
}
//Destructor
//Deletes all the nodes from the list.
//Postcondition: The list object is destroyed.
~circularLinkedList()
{
destroyList();
}
protected:
int count; //variable to store the number of elements in the list
nodeType<Type> *first; //pointer to the first node of the list
nodeType<Type> *last; //pointer to the last node of the list
private:
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and assigned to this list.
void copyList(const circularLinkedList& otherList)
{
nodeType<Type> *newNode;
nodeType<Type> *current;
nodeType<Type> *tempFirst;
if (first != NULL)
destroyList();
if (otherList.first == NULL)
{
first = NULL;
count = 0;
}
else
{
current = otherList.first->link; //current points to the
//list to be copied
count = otherList.count;
//copy the first node
tempFirst = new nodeType<Type>; //create the node
tempFirst->info = current->info; //copy the info
last = tempFirst; //make last point to the //first node
current = current->link; //make current point to the //next node
//copy the remaining list
while (current != otherList.first)
{
newNode = new nodeType<Type>; //create a node
newNode->info = current->info;
last->link = newNode;
last = newNode;
current = current->link;
}//end while
if (tempFirst == last)
{
first = tempFirst;
first->link = first;
}
else
{
newNode = new nodeType<Type>; //create a node
newNode->info = current->info;
last->link = newNode;
first = newNode;
first->link = tempFirst;
}
}//end else
}
};
// function prototypes
void charLinkedList();
void intLinkedList();
void stringLinkedList();
int main() {
int type;
// input of data type for the linked list
cout<<"Enter the data type for the linked list : 1. whole numbers, 2. single characters 3. strings"<<endl;
cout<<"Choice (1-3) : ";
cin>>type;
// validate the choice
while(type < 1 || type > 3)
{
cout<<"Invalid type."<<endl;
cout<<"Choice (1-3) : ";
cin>>type;
}
// call the function corresponding to the data selected
if(type == 1)
intLinkedList();
else if(type == 2)
charLinkedList();
else
stringLinkedList();
return 0;
}
// function to simulate whole numbers linked list
void intLinkedList()
{
circularLinkedList<int> list1, list2;
int num;
cout << "Enter number ending with -999" << endl;
cin >> num;
while (num != -999)
{
list1.insertNode(num);
cin >> num;
}
cout << endl;
cout << "List 1: ";
list1.print();
cout << endl;
cout << "Length List 1: " << list1.length() << endl;
cout << "Enter the number to be searched: ";
cin >> num;
cout << endl;
if (list1.search(num))
cout << num << " found in the list" << endl;
else
cout << num << " not in the list" << endl;
cout << "Enter the number to be deleted: ";
cin >> num;
cout << endl;
list1.deleteNode(num);
cout << "After deleting the node, "
<< "List 1: ";
list1.print();
cout << endl;
cout << "Length List 1: " << list1.length() << endl;
list2 = list1;
cout << "List 2: ";
list2.print();
cout << endl;
cout << "Length List 2: " << list2.length() << endl;
cout << "List 1: ";
list1.print();
cout << endl;
}
// function to simulate character linked list
void charLinkedList()
{
circularLinkedList<char> list1, list2;
char num;
cout << "Enter character ending with q" << endl;
cin >> num;
while (num != 'q')
{
list1.insertNode(num);
cin >> num;
}
cout << endl;
cout << "List 1: ";
list1.print();
cout << endl;
cout << "Length List 1: " << list1.length() << endl;
cout << "Enter the character to be searched: ";
cin >> num;
cout << endl;
if (list1.search(num))
cout << num << " found in the list" << endl;
else
cout << num << " not in the list" << endl;
cout << "Enter the character to be deleted: ";
cin >> num;
cout << endl;
list1.deleteNode(num);
cout << "After deleting the node, "
<< "List 1: ";
list1.print();
cout << endl;
cout << "Length List 1: " << list1.length() << endl;
list2 = list1;
cout << "List 2: ";
list2.print();
cout << endl;
cout << "Length List 2: " << list2.length() << endl;
cout << "List 1: ";
list1.print();
cout << endl;
}
// function to simulate string linked list
void stringLinkedList()
{
circularLinkedList<string> list1, list2;
string num;
cout << "Enter string ending with quit" << endl;
cin >> num;
while (num == "quit")
{
list1.insertNode(num);
cin >> num;
}
cout << endl;
cout << "List 1: ";
list1.print();
cout << endl;
cout << "Length List 1: " << list1.length() << endl;
cout << "Enter the string to be searched: ";
cin >> num;
cout << endl;
if (list1.search(num))
cout << num << " found in the list" << endl;
else
cout << num << " not in the list" << endl;
cout << "Enter the string to be deleted: ";
cin >> num;
cout << endl;
list1.deleteNode(num);
cout << "After deleting the node, "
<< "List 1: ";
list1.print();
cout << endl;
cout << "Length List 1: " << list1.length() << endl;
list2 = list1;
cout << "List 2: ";
list2.print();
cout << endl;
cout << "Length List 2: " << list2.length() << endl;
cout << "List 1: ";
list1.print();
cout << endl;
}
venereology answered 1 year agoRelated Solutions
Translate the following C++ program to Pep/9 assembly language. const char chConst = '+'; char ch1;...
You are required to use C++ static or dynamic arrays of characters to store c-strings. You...
You are required to use C++ static or dynamic arrays of characters to store c-strings. You...
Write a program that uses Python List of strings to hold the five student names, a...
write this program in C++ Write a program that prompts a user for three characters. The...
Please code C# 10. Write a program that allows a user to input names and corresponding...
For this program you will implement the following utility functions to test mastery of C strings....
Modify the DetailedClockPane.java class in your detailed clock program, to add animation to this class. Be...
1) Here is a program in c++ that calculates a speeding ticket, modify the program to...
11.10 LAB: All permutations of names PLEASE ANSWER IN C++! Write a program that lists all...
- JAVA If a user inputs a specific number of rows, columns and sections for a rectangle...
- A stock costs $80 and pays a $4 dividend each year for three years. a) If...
- A solid cylinder, mass of 15 kg, is on a hill that is inclined at a...
- Discuss the difference between a)FAT, FAT32, NTFS, CDFS, etc., b)What make them diferent and why they...
- 2. Given the Instruction sets for Machine-1, Machine-2 and Machine-3, write programs to calculate: P= ((B×C)...
- Problem III. Suppose that, in a market of a certain good, there are firms that are...
- discusses the difference between public relations and advertising. Cite an organization or individual and give one...