Inthis exercise, you will implement below question with classes.
You are encouraged to develop you code based on the sample code in “LinkedList_with_class.hpp”.
Don’t forgot to use the classes. This exercise is all about learning how to implement classes. If you don’t use classes you will get 0.
1. (
6
0%) Write a program to read the numbers from the text file “
numbers.txt
” into an unordered linked list. Then
do the following task
:
(1) Display the entire list with all the numbers.
(
2
) Delete all the negative numbers in the list.
(3) Display the new list after deletion.
(4) Ask the user to specify an index of the list, and delete the node by index. I.e. If the user types 2, delete the second node of the list. If the user types 3, delete the third node of the list.
(5) Display the new list after deletion.
(6) Ask the user to enter an index and a real number from the keyboard, and insert (not replace) the real number to the list at the position of the index. I.e. If the user types 3 and
99
.99, insert 99.99 at the third place of the list, and the original third node should become the fourth. (There is no partial credit for the bonus. You will get either 0 or 1.)
(7) Display the new list after insertion
Requirements
:
(1) You should write a function to delete the negative numbers in the list.
(2) You should write a function to delete the node by index. If the index is less than 1, or if the index is greater than the length of the list, your program should display an error message instead of deleting anything.
(3) You should write a function to insert a node by index. If the index is less than 1, your program should display an error message instead of inserting anything. If the index is greater than the length of the list, insert the node at the tail of the list.
(4) After you finish your program, compress all your files, including both CPP and HPP (recommended), into a single ZIP file and upload it to D2L.
(5) You do not have to use any class in this assignment.
Here is an example of how your program should look like:
The list has the following numbers:
1.2 2.5 3 -4.7 5.1 -6.9 7.4 8.6 9.3 -10 -11.2 12 -13.8 -14.2 15.9
The list after deleting negative numbers is:
1.2 2.5 3 5.1 7.4 8.6 9.3 12 15.9
Enter the index of the number you want to delete: (starting from 1)
2
The list after the deletion is:
1.2 3 5.1 7.4 8.6 9.3 12 15.9
Enter the index of the number you want to insert: (starting from 1)
6
Enter the number you want to insert:
99
The list after the insertion is:
1.2 3 5.1 7.4 8.6 99 9.3 12 15.9
intList.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkedList_with_class.cpp
LinkedList_with_class.cpp
// See Section “Linked List as an ADT” of Chapter 17 of DS Malik’s book.
#include
“LinkedList_with_class.hpp”
#include
<
fstream
>
#include
<
string
>
using
namespace
std
;
int
main
()
{
ifstream inputFile1
,
inputFile2
;
int
dataBuffer1
;
string dataBuffer2
;
unorderedLinkedList
<
int
>
myList1
;
unorderedLinkedList
<
string
>
myList2
;
inputFile1
.
open
(
“intList.txt”
);
while
(
!
inputFile1
.
eof
()
)
// stop the loop when it reaches the end of file
{
inputFile1
>>
dataBuffer1
;
myList1
.
insertLast
(
dataBuffer1
);
}
inputFile1
.
close
();
cout
<<
"The integer list:"
<<
endl
;
myList1
.
print
();
cout
<<
"Trying to delete 10 from the list..."
<<
endl
;
myList1
.
deleteNode
(
10
);
cout
<<
"The list after deletion is:"
<<
endl
;
myList1
.
print
();
inputFile2
.
open
(
"stringList.txt"
);
while
(
!
inputFile2
.
eof
()
)
// stop the loop when it reaches the end of file
{
getline
(
inputFile2
,
dataBuffer2
);
myList2
.
insertLast
(
dataBuffer2
);
}
inputFile2
.
close
();
cout
<<
endl
<<
"The string list:"
<<
endl
;
myList2
.
print
();
cout
<<
"Trying to delete \"Hello!\" from the list..."
<<
endl
;
myList2
.
deleteNode
(
"Hello!"
);
cout
<<
"The list after deletion is:"
<<
endl
;
myList2
.
print
();
return
0
;
}
LinkedList_with_class.hpp
// See Section "Linked List as an ADT" of Chapter 17 of DS Malik's book.
#include
#include
using namespace std;
//**** A single node **********************************************************************
template
struct nodeType // a single node
{
Type info;
nodeType
};
//**** Iterator ***************************************************************************
template
class linkedListIterator // an iterator is used to overload operators and process each node
{
public:
// constructors:
linkedListIterator();
linkedListIterator(nodeType
// operator overloading:
Type operator * ();
linkedListIterator
bool operator == (const linkedListIterator
bool operator != (const linkedListIterator
// a const function cannot modify the object on which it’s called
private:
nodeType
};
//**** member functions of the iterator: **************************************************
// copy constructor
template
linkedListIterator
{
current = ptr; // This is a literal for the null pointer.
}
// default constructor
template
linkedListIterator
{
current = NULL; // This is the null pointer.
}
template
Type linkedListIterator
{
// * is overloaded so it directly dereferences the pointer info
return current->info;
}
template
linkedListIterator
{
// ++ is overloaded so that it makes the current pointer pointing to the next node
current = current->link;
return * this;
}
template
bool linkedListIterator
{
// == is overloaded to check if the two operands point to the same node
return (current == right.current);
}
template
bool linkedListIterator
{
// != is overloaded to check if the two operands point to different nodes
return (current != right.current);
}
//**** Abstract class *********************************************************************
template
class linkedListType
{
public:
bool isEmpty() const; // Check if the list is empty
void destroyList(); // reset the list to empty
void intializeList(); // reset the list to empty
const linkedListType
// overload assignment operator for deep copy
void print() const; // print all nodes of the list
int length() const; // return the length of the list
Type front() const; // return the data of the first node
Type back() const; // return the data of the last node
// abstract class contains virtual function
// virtual functions are to be realized in the derived classes
// There are supposed to be 2 derived classes: ordered list and unordered list
virtual bool search (const Type& searchItem) const = 0;
virtual void insertFirst (const Type& newItem) = 0;
virtual void insertLast (const Type& newItem) = 0;
virtual void deleteNode (const Type& deleteItem) = 0;
// Iterators:
linkedListIterator
linkedListIterator
// constructors:
linkedListType(); // default
linkedListType(const linkedListType
// destructor:
~linkedListType();
protected:
// can only be used by this class and its children (derived classes)
int count; // length of the list
nodeType
nodeType
private:
// not to be used outside this class
void copyList(const linkedListType
// copy the list from source to the current (deep copy)
};
//**** Member functuions of the abstract class ********************************************
template
bool linkedListType
{
return (first == NULL); // if first is null, list is empty, return true
}
template
void linkedListType
{
nodeType
while (first != NULL)
{
temp = first;
first = first->link;
delete temp;
}
last = NULL;
count = 0;
}
template
void linkedListType
{
destroyList(); // reset the list to empty
}
template
void linkedListType
{
// DEEP COPY the data from otherList to this list
nodeType
* current;
if (first != NULL) // if the list is not empty, make it empty,
destroyList(); // so that the old list will be overwritten.
if (otherList.first == NULL)
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first;
count = otherList.count;
// copy the first node
first = new nodeType
first->info = current->info;
first->link = NULL;
last = first;
// copy the remaining list
// similar to the example “LinkedList.cpp”
current = current->link;
while (current != NULL)
{
// create and copy
newNode = new nodeType
newNode->info = current->info;
newNode->link = NULL;
// attach the new node to the last of the list:
last->link = newNode;
last = newNode;
// current pointer points to the next of the other list
current = current->link;
} // end while
} // end else
} // end function
template
const linkedListType
{
if (this != &otherList) // avoid self copy
{
copyList(otherList); // assignment operator calls the copy function
}
return * this;
}
template
void linkedListType
{
nodeType
current = first;
while (current != NULL)
{
cout << current->info << " ";
current = current->link;
}
cout << endl;
}
template
int linkedListType
{
return count;
}
template
Type linkedListType
{
assert(first != NULL); // terminate the program if first is null
return first->info;
}
template
Type linkedListType
{
assert(last != NULL); // terminate the program if first is null
return last->info;
}
// constructors:
template
linkedListType
{
first = NULL;
last = NULL;
count = 0;
}
// copy constructor with parameter
template
linkedListType
{
first = NULL;
copyList(otherList); // call the copy function
}
// destructor:
template
linkedListType
{
destroyList();
}
//**** Iterator functions: ****************************************************************
template
linkedListIterator
{
// call the copy constructor of the iterator
linkedListIterator
return temp;
}
template
linkedListIterator
{
// call the copy constructor of the iterator
linkedListIterator
return temp;
}
//**** Derived class – unordered linked list: *********************************************
template
class unorderedLinkedList: public linkedListType
{
public:
// realize the virtual functions:
bool search (const Type& searchItem) const;
void insertFirst (const Type& newItem);
void insertLast (const Type& newItem);
void deleteNode (const Type& deleteItem);
// no need to declare other members, because they are inherited.
};
//**** Member functuions of unordered linked list: ****************************************
template
bool unorderedLinkedList
{
// This function searches for a node that has the same data as searchItem
// If it’s found, return true. Otherwise, return false.
nodeType
bool found = false;
current = this->first;
while (current != NULL && !found)
{
if (current->info == searchItem)
found = true;
else
current = current->link;
}
return found;
}
template
void unorderedLinkedList
{
// insert a node at the head of the list
nodeType
newNode = new nodeType
newNode->info = newItem;
newNode->link = this->first;
this->first = newNode;
this->count++;
if (this->last == NULL) // if last node was null, the list was empty before the insertion
this->last = newNode; // then the list has one node after the insertion
}
template
void unorderedLinkedList
{
// insert a node at the tail of the list
nodeType
newNode = new nodeType
newNode->info = newItem;
newNode->link = NULL;
if (this->first == NULL) // insert to empty list
{
this->first = newNode;
this->last = newNode;
this->count++;
}
else
{
this->last->link = newNode;
this->last = newNode;
this->count++;
}
}
template
void unorderedLinkedList
{
// This function deletes the node that has the data deleteItem
nodeType
* trailCurrent; // remember p and q in the previous example
// “linkedList.cpp”?
// We use tailCurrent for p, current for q
// in this function.
bool found; // deleteItem must exists in the list before we can delete it
if (this->first == NULL) // Case 1: the list was empty
{
cout << "Cannot delete from an empty list." << endl;
}
else if (this->first->info == deleteItem) // Case 2: the first node
{ // is the one we want to delete.
current = this->first;
this->first = this->first->link; // make the second node the new first
this->count–;
if (this->first == NULL) // if the list had one node before deletion
{
this->last = NULL; // the list should become an empty list now
}
delete current; // free the memory space of the original first node
}
else // search for the value, if found (Case 3), delete it.
{
found = false;
// We can assume the first node isn’t the one we want to delete,
trailCurrent = this->first;
// so we start searching from the second node:
current = this->first->link;
// searching…
while (current != NULL && !found)
{
if (current->info != deleteItem)
{
// not this node. go to the next one
trailCurrent = current;
current = current->link;
}
else
{
found = true;
}
} // at the end of the loop, if found is true,
//current must point to the node that we want to delete.
if (found)
{
// delete the node by connecting its previous node
// to its next node:
trailCurrent->link = current->link;
this->count–;
if (this->last == current) // if the node to be deleted was the last node
this->last = trailCurrent; // we update the pointer of last
delete current; // free the memory space
}
else
{
cout << "The item that you wanted to delete does not exist "
<< "in the list." << endl;
}
}
}
stringList.txt
Hello!
How are you?
Lobster is on sale!
A horse weighs about 1500 lbs.
1.2
2.5
3
-4.7
5.1
-6.9
7.4
8.6
9.3
-10
-11.2
12
-13.8
-14.2
15.9