Question: #ifndef ARRAY_LIST_TYPE #define ARRAY_LIST_TYPE #include #include using namespace std; //*********************************************************** // Author: D.S. Malik // // This class specifies the members to implement the basic
#ifndef ARRAY_LIST_TYPE
#define ARRAY_LIST_TYPE
#include
#include
using namespace std;
//***********************************************************
// Author: D.S. Malik
//
// This class specifies the members to implement the basic
// properties of array-based lists.
//***********************************************************
template
class arrayListType {
public:
const arrayListType & operator =
(const arrayListType & );
//Overloads the assignment operator
bool isEmpty() const;
//Function to determine whether the list is empty
//Postcondition: Returns true if the list is empty;
// otherwise, returns false.
bool isFull() const;
//Function to determine whether the list is full.
//Postcondition: Returns true if the list is full;
// otherwise, returns false.
int listSize() const;
//Function to determine the number of elements in the list
//Postcondition: Returns the value of length.
int maxListSize() const;
//Function to determine the size of the list.
//Postcondition: Returns the value of maxSize.
void print() const;
//Function to output the elements of the list
//Postcondition: Elements of the list are output on the
// standard output device.
bool isItemAtEqual(int location,const elemType & item) const;
//Function to determine whether the item is the same
//as the item in the list at the position specified by
//Postcondition: Returns true if list[location]
// is the same as the item; otherwise,
// returns false.
void insertAt(int location,const elemType & insertItem);
//Function to insert an item in the list at the
//position specified by location. The item to be inserted
//is passed as a parameter to the function.
//Postcondition: Starting at location, the elements of the
// list are shifted down, list[location] = insertItem;,
// and length++;. If the list is full or location is
// out of range, an appropriate message is displayed.
void insertEnd(const elemType & insertItem);
//Function to insert an item at the end of the list.
//The parameter insertItem specifies the item to be inserted.
//Postcondition: list[length] = insertItem; and length++;
// If the list is full, an appropriate message is
// displayed.
void removeAt(int location);
//Function to remove the item from the list at the
//position specified by location
//Postcondition: The list element at list[location] is removed
// and length is decremented by 1. If location is out of
// range, an appropriate message is displayed.
void retrieveAt(int location, elemType & retItem) const;
//Function to retrieve the element from the list at the
//position specified by location.
//Postcondition: retItem = list[location]
// If location is out of range, an appropriate message is
// displayed.
void replaceAt(int location,const elemType & repItem);
//Function to replace the elements in the list at the
//position specified by location. The item to be replaced
//is specified by the parameter repItem.
//Postcondition: list[location] = repItem
// If location is out of range, an appropriate message is
// displayed.
void clearList();
//Function to remove all the elements from the list.
//After this operation, the size of the list is zero.
//Postcondition: length = 0;
int seqSearch(const elemType & item) const;
//Function to search the list for a given item.
//Postcondition: If the item is found, returns the location
// in the array where the item is found; otherwise,
// returns -1.
void insert(const elemType & insertItem);
//Function to insert the item specified by the parameter
//insertItem at the end of the list. However, first the
//list is searched to see whether the item to be inserted
//is already in the list.
//Postcondition: list[length] = insertItem and length++
// If the item is already in the list or the list
// is full, an appropriate message is displayed.
void remove(const elemType & removeItem);
//Function to remove an item from the list. The parameter
//removeItem specifies the item to be removed.
//Postcondition: If removeItem is found in the list,
// it is removed from the list and length is
// decremented by one.
arrayListType(int size = 100);
//constructor
//Creates an array of the size specified by the
//parameter size. The default array size is 100.
//Postcondition: The list points to the array, length = 0,
// and maxSize = size
arrayListType(const arrayListType & otherList);
//copy constructor
~arrayListType();
//destructor
//Deallocates the memory occupied by the array.
protected:
elemType * list; //array to hold the list elements
int length; //to store the length of the list
int maxSize; //to store the maximum size of the list
};
template
bool arrayListType ::isEmpty() const {
return (length == 0);
}
template
bool arrayListType ::isFull() const {
return (length == maxSize);
}
template
int arrayListType ::listSize() const {
return length;
}
template
int arrayListType ::maxListSize() const {
return maxSize;
}
template
void arrayListType ::print() const {
for (int i = 0; i
cout
cout
}
template
bool arrayListType ::isItemAtEqual(int location, const elemType & item) const {
if (location = length){
cerr
"is out of range"
return false;
}
return (list[location] == item);
}
template
void arrayListType ::insertAt(int location,
const elemType & insertItem) {
if (location length)
cerr
"is out of range"
else if (length >= maxSize) //list is full
cerr
else {
for (int i = length; i > location; i--)
list[i] = list[i - 1]; //move the elements down
list[location] = insertItem; //insert the item at the
//specified position
length++; //increment the length
}
} //end insertAt
template
void arrayListType ::insertEnd(const elemType & insertItem) {
if (length >= maxSize) //the list is full
cerr
else {
list[length] = insertItem; //insert the item at the end
length++; //increment the length
}
} //end insertEnd
template
void arrayListType ::removeAt(int location) {
if (location = length)
cerr
"is out of range"
else {
for (int i = location; i
list[i] = list[i + 1];
length--;
}
} //end removeAt
template
void arrayListType ::retrieveAt(int location, elemType & retItem) const {
if (location = length)
cerr
"out of range."
else
retItem = list[location];
} //end retrieveAt
template
void arrayListType ::replaceAt(int location,
const elemType & repItem)
{
if (location = length)
cerr
"out of range."
else
list[location] = repItem;
} //end replaceAt
template
void arrayListType ::clearList() {
length = 0;
} //end clearList
template
arrayListType ::arrayListType(int size) {
if (size
cerr
"an array of size 100. "
maxSize = 100;
} else
maxSize = size;
length = 0;
list = new elemType[maxSize];
assert(list != NULL);
}
template
arrayListType ::~arrayListType() {
delete[] list;
}
template
arrayListType ::arrayListType(const arrayListType & otherList) {
maxSize = otherList.maxSize;
length = otherList.length;
list = new elemType[maxSize]; //create the array
assert(list != NULL); //terminate if unable to allocate
//memory space
for (int j = 0; j
list[j] = otherList.list[j];
} //end copy constructor
template
const arrayListType & arrayListType ::operator =
(const arrayListType & otherList) {
if (this != & otherList) //avoid self-assignment
{
delete[] list;
maxSize = otherList.maxSize;
length = otherList.length;
list = new elemType[maxSize]; //create the array
assert(list != NULL); //if unable to allocate memory
//space, terminate the program
for (int i = 0; i
list[i] = otherList.list[i];
}
return *this;
}
template
int arrayListType ::seqSearch(const elemType & item) const {
int loc;
bool found = false;
for (loc = 0; loc
if (list[loc] == item) {
found = true;
break;
}
if (found)
return loc;
else
return -1;
} //end seqSearch
template
void arrayListType ::insert(const elemType & insertItem) {
int loc;
if (length == 0) //list is empty
list[length++] = insertItem; //insert the item and
//increment the length
else if (length == maxSize)
cerr
else {
loc = seqSearch(insertItem);
if (loc == -1) //the item to be inserted
//does not exist in the list
list[length++] = insertItem;
else
cerr
"the list. No duplicates are allowed."
}
} //end insert
template
void arrayListType ::remove(const elemType & removeItem) {
int loc;
if (length == 0)
cerr
else {
loc = seqSearch(removeItem);
if (loc != -1)
removeAt(loc);
else
cout
endl;
}
} //end remove
#endif // ARRAY_LIST_TYPE
#ifndef H_UnorderedLinkedList
#define H_UnorderedLinkedList
#include"linkedListType.h"
//***********************************************************
// Author: D.S. Malik
//
// This class specifies the members to implement the basic
// properties of an unordered linked list. This class is
// derived from the class linkedListType.
//***********************************************************
template
class unorderedLinkedList : public linkedListType {
public:
bool search(const Type& searchItem) const;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is in the list,
// otherwise the value false is returned.
void insertfirst(const Type& newItem);
//Function to insert newItem at the beginning of the list.
//Postcondition: this->first points to the new list, newItem is
// inserted at the beginning of the list, this->last points to
// the this->last node, and this->count is incremented by 1.
//
void insertlast(const Type& newItem);
//Function to insert newItem at the end of the list.
//Postcondition: this->first points to the new list, newItem is
// inserted at the end of the list, this->last points to the
// this->last node, and this->count is incremented by 1.
void deleteNode(const Type& deleteItem);
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing deleteItem
// is deleted from the list. this->first points to the this->first
// node, this->last points to the this->last node of the updated
// list, and this->count is decremented by 1.
};
template
bool unorderedLinkedList ::
search(const Type& searchItem) const {
nodeType * current; //pointer to traverse the list
bool found = false;
current = this->first; //set current to point to the this->first
/ode in the list
while (current != NULL && !found) //search the list
if (current->info == searchItem) //searchItem is found
found = true;
else
current = current->link; //make current point to
//the next node
return found;
} //end search
template
void unorderedLinkedList ::insertfirst(const Type& newItem) {
nodeType * newNode; //pointer to create the new node
newNode = new nodeType ; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = this->first; //insert newNode before this->first
this->first = newNode; //make this->first point to the actual this->first node
this->count++; //increment this->count
if (this->last == NULL) //if the list was empty, newNode is also
//the this->last node in the list
this->last = newNode;
} //end insertthis->first
template
void unorderedLinkedList ::insertlast(const Type& newItem) {
nodeType * newNode; //pointer to create the new node
newNode = new nodeType ; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = NULL; //set the link field of newNode to NULL
if (this->first == NULL) //if the list is empty, newNode is
//both the this->first and this->last node
{
this->first = newNode;
this->last = newNode;
this->count++; //increment this->count
}
else //the list is not empty, insert newNode after this->last
{
this->last->link = newNode; //insert newNode after this->last
this->last = newNode; //make this->last point to the actual
//this->last node in the list
this->count++; //increment this->count
}
} //end insertthis->last
template
void unorderedLinkedList ::deleteNode(const Type& deleteItem) {
nodeType * current; //pointer to traverse the list
nodeType * trailCurrent; //pointer just before current
bool found;
if (this->first == NULL) //Case 1; the list is empty.
cout
endl;
else {
if (this->first->info == deleteItem) //Case 2
{
current = this->first;
this->first = this->first->link;
this->count--;
if (this->first == NULL) //the list has only one node
this->last = NULL;
delete current;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = this->first; //set trailCurrent to point
//to the this->first node
current = this->first->link; //set current to point to
//the second node
while (current != NULL && !found) {
if (current->info != deleteItem) {
trailCurrent = current;
current = current->link;
}
else
found = true;
} //end while
if (found) //Case 3; if found, delete the node
{
trailCurrent->link = current->link;
this->count--;
if (this->last == current) /ode to be deleted was the
//this->last node
this->last = trailCurrent; //update the value of this->last
delete current; //delete the node from the list
}
else
cout
"the list."
} //end else
} //end else
} //end deleteNode
#endif
#include //Line 1
#include //Line 2
#include
#include "arrayListType.h" //Line
using namespace std; //Line 4
int main() //Line 5
{
arrayListType L,L1,L2;
L.insertEnd(2);
L.insertEnd(1);
L.insertEnd(3);
L.insertEnd(4);
L.insertEnd(5);
L.insertEnd(3);
L.insertEnd(0);
cout
L.print();
incrementByConstant(L,3);
cout
L.print();
L.clearList();
L.insertEnd(2);
L.insertEnd(1);
L.insertEnd(3);
L.insertEnd(4);
L.insertEnd(5);
L.insertEnd(3);
L.insertEnd(0);
cout
L.print();
sortEach2(L,'a');
cout
L.print();
L.clearList();
L.insertEnd(2);
L.insertEnd(1);
L.insertEnd(3);
L.insertEnd(4);
L.insertEnd(5);
L.insertEnd(3);
L.insertEnd(0);
cout
L.print();
sortEach2(L,'d');
cout
L.print();
L.clearList();
L.insertEnd(2);
L.insertEnd(1);
L.insertEnd(3);
L.insertEnd(4);
L.insertEnd(5);
L.insertEnd(3);
L.insertEnd(0);
cout
L.print();
duplicateORremove(L,3);
cout
L.print();
L.clearList();
L.insertEnd(2);
L.insertEnd(1);
L.insertEnd(3);
L.insertEnd(4);
L.insertEnd(5);
L.insertEnd(3);
L.insertEnd(0);
cout
L.print();
split(L,3,L1,L2);
cout
L.print();
cout
L1.print();
cout
L2.print();
return 0;
}
#include
#include "unorderedLinkedList.h"
using namespace std;
int main()
{
unorderedLinkedList L,L1,L2;
L.insertlast(2);
L.insertlast(1);
L.insertlast(3);
L.insertlast(4);
L.insertlast(5);
L.insertlast(3);
L.insertlast(0);
cout
L.print();
L.incrementByConstant(3);
cout
L.print();
L.destroyList();
L.insertlast(2);
L.insertlast(1);
L.insertlast(3);
L.insertlast(4);
L.insertlast(5);
L.insertlast(3);
L.insertlast(0);
cout
L.print();
L.sortEach2('a');
cout
L.print();
L.destroyList();
L.insertlast(2);
L.insertlast(1);
L.insertlast(3);
L.insertlast(4);
L.insertlast(5);
L.insertlast(3);
L.insertlast(0);
cout
L.print();
L.sortEach2('d');
cout
L.print();
L.destroyList();
L.insertlast(2);
L.insertlast(1);
L.insertlast(3);
L.insertlast(4);
L.insertlast(5);
L.insertlast(3);
L.insertlast(0);
cout
L.print();
L.duplicateORremove(3);
cout
L.print();
L.destroyList();
L.insertlast(2);
L.insertlast(1);
L.insertlast(3);
L.insertlast(4);
L.insertlast(5);
L.insertlast(3);
L.insertlast(0);
cout
L.print();
L.split(3,L1,L2);
cout
L.print();
cout
L1.print();
cout
L2.print();
return 0;
}
#include //Line 1
#include //Line 2
#include
#include "arrayListType.h" //Line
using namespace std; //Line 4
int main() //Line 5
{
arrayListType L,L1,L2;
L.insertEnd(2);
L.insertEnd(1);
L.insertEnd(3);
L.insertEnd(4);
L.insertEnd(5);
L.insertEnd(3);
L.insertEnd(0);
cout
L.print();
L.incrementByConstant(3);
cout
L.print();
L.clearList();
L.insertEnd(2);
L.insertEnd(1);
L.insertEnd(3);
L.insertEnd(4);
L.insertEnd(5);
L.insertEnd(3);
L.insertEnd(0);
cout
L.print();
L.sortEach2('a');
cout
L.print();
L.clearList();
L.insertEnd(2);
L.insertEnd(1);
L.insertEnd(3);
L.insertEnd(4);
L.insertEnd(5);
L.insertEnd(3);
L.insertEnd(0);
cout
L.print();
L.sortEach2('d');
cout
L.print();
L.clearList();
L.insertEnd(2);
L.insertEnd(1);
L.insertEnd(3);
L.insertEnd(4);
L.insertEnd(5);
L.insertEnd(3);
L.insertEnd(0);
cout
L.print();
L.duplicateORremove(3);
cout
L.print();
L.clearList();
L.insertEnd(2);
L.insertEnd(1);
L.insertEnd(3);
L.insertEnd(4);
L.insertEnd(5);
L.insertEnd(3);
L.insertEnd(0);
cout
L.print();
L.split(3,L1,L2);
cout
L.print();
cout
L1.print();
cout
L2.print();
return 0;
}
#ifndef H_LinkedList
#define H_LinkedList
#include
using namespace std;
//***********************************************************
// Author: D.S. Malik
//
// This class specifies the members to implement the basic
// properties of a linked list. This is an abstract class.
// We cannot instantiate an object of this class.
//***********************************************************
template
struct nodeType {
Type info;
nodeType * link;
};
template
class linkedListType {
public:
const linkedListType & operator =
(const linkedListType &);
//Overload the assignment operator.
void initializeList();
//Initialize the list to an empty state.
//Postcondition: this->first = NULL, this->last = NULL, this->count = 0;
bool isEmptyList() const;
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty, otherwise
// it returns false.
void print() const;
//Function to output the data contained in each node.
//Postcondition: none
int length() const;
//Function to return the number of nodes in the list.
//Postcondition: The value of this->count is returned.
void destroyList();
//Function to delete all the nodes from the list.
//Postcondition: this->first = NULL, this->last = NULL, this->count = 0;
Type front() const;
//Function to return the this->first element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, the program terminates;
// otherwise, the this->first element of the list is returned.
Type back() const;
//Function to return the this->last element of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: If the list is empty, the program
// terminates; otherwise, the this->last
// element of the list is returned.
virtual bool search(const Type& searchItem) const = 0;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is in the list,
// otherwise the value false is returned.
virtual void insertfirst(const Type& newItem) = 0;
//Function to insert newItem at the beginning of the list.
//Postcondition: this->first points to the new list, newItem is
// inserted at the beginning of the list, this->last points to
// the this->last node in the list, and this->count is incremented by
// 1.
virtual void insertlast(const Type& newItem) = 0;
//Function to insert newItem at the end of the list.
//Postcondition: this->first points to the new list, newItem is
// inserted at the end of the list, this->last points to the
// this->last node in the list, and this->count is incremented by 1.
virtual void deleteNode(const Type& deleteItem) = 0;
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing deleteItem is
// deleted from the list. this->first points to the this->first node,
// this->last points to the this->last node of the updated list, and
// this->count is decremented by 1.
linkedListType();
//default constructor
//Initializes the list to an empty state.
//Postcondition: this->first = NULL, this->last = NULL, this->count = 0;
linkedListType(const linkedListType & otherList);
//copy constructor
~linkedListType();
//destructor
//Deletes all the nodes from the list.
//Postcondition: The list object is destroyed.
protected:
int count; //variable to store the number of list elements
nodeType * first; //pointer to the this->first node of the list
nodeType * last; //pointer to the this->last node of the list
private:
void copyList(const linkedListType & otherList);
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and assigned
// to this list.
};
template
bool linkedListType ::isEmptyList() const {
return (this->first == NULL);
}
template
linkedListType ::linkedListType() //default constructor
{
this->first = NULL;
this->last = NULL;
this->count = 0;
}
template
void linkedListType ::destroyList() {
nodeType * temp; //pointer to deallocate the memory
//occupied by the node
while (this->first != NULL) //while there are nodes in the list
{
temp = this->first; //set temp to the current node
this->first = this->first->link; //advance this->first to the next node
delete temp; //deallocate the memory occupied by temp
}
this->last = NULL; //initialize this->last to NULL; this->first has already
//been set to NULL by the while loop
this->count = 0;
}
template
void linkedListType ::initializeList() {
destroyList(); //if the list has any nodes, delete them
}
template
void linkedListType ::print() const {
nodeType * current; //pointer to traverse the list
current = this->first; //set current point to the this->first node
while (current != NULL) //while more data to print
{
cout info
Part 1: Starting from the arrayListType.h (attached with this assignment) and without using any of the predefined member functions, Write the required code to do the following: 1. Modify the arrayListType by adding a member function that increase each element in the list by a constant number that it takes as a parameter. This member function does not return any value. For example, if the list L contains the elements 2,1,3,4,5,3,0 and you call the member function as in L.incrementByConstant(3); The list content will then be changed to 5,4,6,7,8,6,3 2. Modify the arrayListType by adding a member function that checks every 2 consecutive elements and make them in ascending or descending order depending on a parameter value (letter 'a' means ascending and letter 'd' means descending). For example, if the list L contains the elements 2,1,3,4,5,3,0 and you call the member function as in L sortEach2{'a'); The list content will then be changed to 1,2,3,4,3,5,0 if the list L contains the elements 2,1,3,4,5,3,0 and you call the member function as in L.sortEach21'd'); The list content will then be changed to 2,1,4,3,5,3,0 3. Modify the arrayListType by adding a member function that duplicate each item that is greater than a value that is sent to the function as a parameter and remove the items that are smaller than the parameter, For example, if a list L contains the elements 2,1,3,4,5,3,0 and you call the member function as in L.duplicate Rremove(3) The list content will then be changed to 3,4,4,5,5,3 current = current->link;
}
cout
} //end print
template
int linkedListType ::length() const {
return this->count;
}
template
Type linkedListType ::front() const {
assert(this->first != NULL);
return this->first->info; //return the info of the this->first node
} //end front
template
Type linkedListType ::back() const {
assert(this->last != NULL);
return this->last->info; //return the info of the this->last node
} //end back
template
void linkedListType ::copyList(const linkedListType & otherList) {
nodeType * newNode; //pointer to create a node
nodeType * current; //pointer to traverse the list
if (this->first != NULL) //if the list is nonempty, make it empty
destroyList();
if (otherList.first == NULL) //otherList is empty
{
this->first = NULL;
this->last = NULL;
this->count = 0;
}
else {
current = otherList.first; //current points to the
//list to be copied
this->count = otherList.count;
//copy the this->first node
this->first = new nodeType ; //create the node
this->first->info = current->info; //copy the info
this->first->link = NULL; //set the link field of the node to NULL
this->last = this->first; //make this->last point to the this->first node
current = current->link; //make current point to the next
// node
//copy the remaining list
while (current != NULL) {
newNode = new nodeType ; //create a node
newNode->info = current->info; //copy the info
newNode->link = NULL; //set the link of newNode to NULL
this->last->link = newNode; //attach newNode after this->last
this->last = newNode; //make this->last point to the actual this->last
/ode
current = current->link; //make current point to the
/ext node
} //end while
} //end else
} //end copyList
template
linkedListType ::~linkedListType() //destructor
{
destroyList();
}
template
linkedListType ::linkedListType(const linkedListType & otherList) {
this->first = NULL;
copyList(otherList);
} //end copy constructor
//overload the assignment operator
template
const linkedListType & linkedListType ::operator =
(const linkedListType & otherList) {
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
} //end else
return *this;
}
#endif
Step by Step Solution
There are 3 Steps involved in it
1 Expert Approved Answer
Step: 1 Unlock
Question Has Been Solved by an Expert!
Get step-by-step solutions from verified subject matter experts
Step: 2 Unlock
Step: 3 Unlock
Study Help