Homework SourseData Structures using C Using the SortedList sorted arraybas
Data Structures using C++
Using the SortedList (sorted array-based list) class below:
#ifndef SORTEDLIST_H
#define SORTEDLIST_H
#include <iostream>
#include <cstdlib> // Needed for the exit function
using namespace std;
const int MAX_LENGTH = 100; // Maximum number of components
template <class ItemType> // You may also choose to use
// typedef statement
class SortedList
{
public:
// Constructor
SortedList();
// Post: Empty list has been created. length has been set to zero.
// Knowledge responsibilities
int getLength() const;
// Post: Returns the length of the list
bool isEmpty() const;
// Post: Returns true if list is empty; false otherwise
bool isFull() const;
// Post: Returns true if list is full; false otherwise
bool isInList(const ItemType& item) const;
// Post: Returns true if item is int the list; false otherwise
int binarySearch(const ItemType& item) const;
// Function to search the list for a given item using binary
// search algorithm.
// Post: If item is found, returns the index in the array where
// item is found; otherwise, return -1.
// Action Responsibilities
void resetList();
// Post: The list becomes empty. length has been set to zero.
void insert(const ItemType& item);
// Function to insert item to the list. However, first
// the list is searched to see whether the item to be inserted is
// already in the list.
// Pre: The list items are sorted in ascending order.
// Post: item is in the list and list items are sorted in ascending
// order. If item is added, length++; if the list is already full or
// item is already in the list, an appropriate message is displayed.
void remove(const ItemType& item);
// Function to remove item from the list.
// Pre: The list items are sorted in ascending order.
// Post: If item is found in the list, it is removed from the list
// and length is decremented by one. The list items remain sorted in
// ascending order.
// Overloaded [] operator declaration.
// This function returns a reference to the element in the
// array indexed by index.
ItemType& operator[](const int& index);
private:
ItemType list[MAX_LENGTH]; // array to hold the list elements
int length; // to store the length of the list
};
//**********************************************************
template <class ItemType>
SortedList<ItemType>::SortedList()
{
length = 0;
}
//**********************************************************
template <class ItemType>
int SortedList<ItemType>::getLength() const
{
return length;
}
//**********************************************************
template <class ItemType>
bool SortedList<ItemType>::isEmpty() const
{
return (length == 0);
}
//**********************************************************
template <class ItemType>
bool SortedList<ItemType>::isFull() const
{
return (length == MAX_LENGTH);
}
//**********************************************************
template <class ItemType>
bool SortedList<ItemType>::isInList(const ItemType& item) const
{
int loc;
loc = binarySearch(item);
if (loc != -1)
return true;
else
return false;
}
//**********************************************************
template <class ItemType>
int SortedList<ItemType>::binarySearch(const ItemType& item) const
{
int first = 0; // lower bound on list
int last = length - 1; // upper bound on list
int middle; // middle index
bool found = false;
while (last >= first && !found )
{
middle = (first + last ) / 2;
if (item < list[middle])
// item is not in list[middle..last]
last = middle - 1;
else if (item > list[middle])
// item is not in list[first..middle]
first = middle + 1;
else
// item == list[middle]
found = true;
}
if (found)
return middle;
else
return -1;
}
//**********************************************************
template <class ItemType>
void SortedList<ItemType>::resetList()
{
length = 0;
}
//**********************************************************
template <class ItemType>
void SortedList<ItemType>::insert(const ItemType& item)
{
int loc = length - 1; // the index for the inserted item
if (length == MAX_LENGTH) // check if the list is full
cout << \"Cannot insert in a full list.\" << endl;
else if (binarySearch(item) != -1) // check if item is in list
cout << \"The item is already in the list. \"
<< \"No duplicates are allowed.\" << endl;
else
{
// Search for insertion point beginning at the end. Items
// are compared and shifted until insertion place is found.
while (loc >= 0 && item < list[loc])
{
list[loc + 1] = list[loc];
loc--;
}
list[loc + 1] = item; // insert item
length++;
}
}
//*********************************************************
template <class ItemType>
void SortedList<ItemType>::remove(const ItemType& item)
{
int loc;
loc = binarySearch(item);
if (loc == -1) // check if item is in list
cout << \"The item is not in the list. \"
<< \"Cannot delete a non-existing item.\" << endl;
else
{
// Shift list[(loc+1)..length-1] up one position
for (int index = loc + 1; index < length; index++)
list[index - 1] = list[index];
length--;
}
}
//**********************************************************
template <class ItemType>
ItemType& SortedList<ItemType>::operator[](const int& index)
{
if (index < 0 || index >= length)
{
cout << \"ERROR: Index out of range.\ \";
exit(EXIT_FAILURE);
}
return list[index];
}
#endif
Write a client function mergeLists which merges two sorted lists into a third sorted list.
The preconditions of the function are:
list1 and list2 have been initialized and are sorted;
list1 and list2 do not have any items in common.
The postconditions are:
The result is a sorted list that contains all of the items from list1 and list2.
(a) Write the prototype for mergeLists.
(b) Write the function definition for mergeLists, using the SortedList class.
Solution
#include <iostream>
#include <list>
//Renamed the given header file to below
#include \"SortedList.h\"
using namespace std;
//function prototype
template <typename T>
list<T> mergeLists(SortedList<T> &, SortedList<T> &);
int main(){
//Sorted list 1
SortedList<int> list1;
list1.insert(7);
list1.insert(5);
list1.insert(3);
//Sorted list 2
SortedList<int> list2;
list2.insert(6);
list2.insert(4);
list2.insert(2);
list<int> lst = mergeLists(list1,list2);
for(list<int>::iterator it=lst.begin();it!=lst.end();it++){
cout<<*it<<\" \";
}
return 0;
}
//function definition
template<typename T>
list<T> mergeLists(SortedList<T> &list1,SortedList<T> &list2){
list<T> temp;
//Merge the two sorted lists
int i=0;
int j=0;
while(i<list1.getLength() && j<list2.getLength()){
if(list1.operator[](i)<=list2.operator[](j)){
temp.push_back(list1.operator[](i));
i++;
}
else{
temp.push_back(list2.operator[](j));
j++;
}
}
// Copy the remaining items of list1, if there are any
while(i<list1.getLength()){
temp.push_back(list1.operator[](i));
i++;
}
//Copy the remaining items of list2, if there are any
while(j<list2.getLength()){
temp.push_back(list2.operator[](j));
j++;
}
return temp;
}
