C++ Programming Exercise: Implement a complete OrderedList class to store a list
ID: 3570508 • Letter: C
Question
C++ Programming Exercise:
Implement a complete OrderedList class to store a list of integers in ascending order. Implement it in two different ways: 1) using a statically allocated array as the underlying data structure, 2) using a linked list as the underlying data structure. If necessary, provide default constructor, copy constructor, destructor and operator=(). Provide member functions for int count(int value), bool insert(int value), int removeAll(int value), bool getMin(int& theMin), bool getMax(int& theMax), bool removeMin(), bool removeMax(), int getLength() and operator<<(), operator>>(). The bool return values for insert(), getMin() etc. are used to indicate whether or not the operation was successful. For example, if an array is the underlying data structure then you can
Explanation / Answer
Array Implementation
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
class OrderedArray
{
protected:
const static int MAX_SIZE = 10000;
static int array[MAX_SIZE];
int n_length;
public:
OrderedArray()
{
n_length = 0;
}
int count( int value)
{
int count = 0;
for(int i=0; i < n_length ; i++)
if(array[i] == value)
count++;
return count;
}
bool insert( int value)
{
int j;
if( n_length == MAX_SIZE)
return false;
array[n_length] = value;
j = n_length;
while (j > 0 && array[j] < array[j-1])
{
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
j--;
}
n_length++;
return true;
}
int removeAll( int value)
{
int count = 0;
if( n_length == 0 )
return 0;
else
{
int i, j = 0;
for (i = 0; i < n_length; i++) {
if (array[i] != value) {
array[j]=array[i];
j++;
}
else
count++;
}
n_length = j;
}
return count;
}
bool getMin( int &theMin)
{
if( n_length == 0 )
return false;
theMin = array[0];
for( int i=1; i < n_length ; i++)
if( array[i] < theMin)
theMin = array[i];
return true;
}
bool getMax( int &theMax)
{
if( n_length == 0)
return false;
theMax = array[0];
for( int i=1; i < n_length; i++)
if( array[i] > theMax)
theMax = array[i];
return true;
}
bool removeMin()
{
int min = 0;
if( n_length ==0 || getMin( min ))
return false;
int count = removeAll( min);
n_length-= count;
return true;
}
bool removeMax()
{
int max = 0;
if( n_length ==0 || getMax( max ))
return false;
int count = removeAll( max);
n_length-= count;
return true;
}
int getLength()
{
return n_length;
}
friend istream& operator>> ( istream& is, OrderedArray& list );
friend ostream& operator<< (ostream& os,OrderedArray& list );
};
istream& operator>> ( istream& is, OrderedArray& list )
{
if(list.n_length == list.MAX_SIZE)
return is;
int i;
is >> i;
list.insert(i);
return is;
}
ostream& operator<< (ostream& os,OrderedArray& list )
{
if(list.n_length == 0)
return os;
int i;
os<<endl<<list.array[0];
for(i=1;i<list.n_length;i++)
{
os<<" , "<<list.array[i];
}
return os;
}
Linked List Implementation
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
class node
{
public:
int data;
node *next;
node(int d,node *n=0)
{
data=d;
next=n;
}
}*head;
class OrderedList
{
node *temp,*head,*prev;
int n_length;
public:
OrderedList()
{
n_length = 0;
head = NULL;
temp = NULL;
prev = NULL;
}
int count( int value)
{
int count = 0;
for(temp = head;temp!=NULL;temp=temp->next)
if(temp->data == value)
count++;
return count;
}
bool insert( int value)
{
if(head==0 || (head->data > value))
{
head=new node(value,head);
}
else
{
temp=head;
while(temp->next!=0 && temp->next->data <= value)
{
temp=temp->next;
}
temp->next=new node(value,temp->next);
}
n_length++;
return true;
}
int removeAll( int value)
{
int count = 0;
if( n_length == 0 )
return 0;
else
{
prev = NULL;
temp = head;
for(;temp!=NULL && temp->data<value;prev = temp,temp=temp->next);
if(temp!=NULL)
{
if(prev == NULL)
while(head!=NULL && head->data == value)
{
temp = head;
head = head->next;
free(temp);
count++;
}
else
{
while(temp!=NULL && temp->data == value)
{
temp = temp->next;
count++;
}
prev->next = temp;
}
}
n_length -= count;
}
return count;
}
bool getMin( int &theMin)
{
if( n_length == 0 )
return false;
theMin = head->data;
for( temp = head; temp!=NULL;temp=temp->next)
if( temp->data < theMin)
theMin = temp->data;
return true;
}
bool getMax( int &theMax)
{
if( n_length == 0)
return false;
theMax = head->data;
for( temp = head; temp!=NULL;temp=temp->next)
if( temp->data > theMax)
theMax = temp->data;
return true;
}
bool removeMin()
{
int min = 0;
if( n_length ==0 || getMin( min ))
return false;
int count = removeAll( min);
n_length-= count;
return true;
}
bool removeMax()
{
int max = 0;
if( n_length ==0 || getMax( max ))
return false;
int count = removeAll( max);
n_length-= count;
return true;
}
int getLength()
{
return n_length;
}
int* toArray()
{
int *p;
p=new int[n_length];
int i;
temp=head;
for(i=0;i<n_length;i++,temp=temp->next)
{
p[i]=temp->data;
}
return p;
}
friend istream& operator>> ( istream& is, OrderedList& list );
friend ostream& operator<< (ostream& os,OrderedList& list );
};
istream& operator>> ( istream& is, OrderedList& list )
{
int i;
is >> i;
list.insert(i);
return is;
}
ostream& operator<<(ostream& os,OrderedList& list )
{
if(head == 0)
return os;
node* temp=list.head;
os<<endl;
while(temp!=NULL)
{
os<<" -> "<<temp->data;
}
return os;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.