//Date: 2003.02.19
//Author: AOU
//File: cArray07.cpp
/* Assignment #2
Date Assigned: 02/17/2003
Date Due: 02/24/2003
Add the following member/test functions to cArray06.cpp
(1) bool deleteAtPos(int id)
(2) void testDeleteAtPos(void)
(3) int purgeDupes(void)
(4) void testPurgeDupes(void)
*/
/*
Added the following member functions:
bool isSorted(void);
void testIsSorted(void);
*/
///////////////////////////////////////////////////////////
// include files
///////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
///////////////////////////////////////////////////////////
// constants
///////////////////////////////////////////////////////////
const int MAX_COUNT = 10; //maximum size of array
const int MAX_VALUE = 5;
const int UNDEFINED = -99;
///////////////////////////////////////////////////////////
// prototypes
///////////////////////////////////////////////////////////
void testSearchSeq(void);
void testAreDistinct(void);
void testConstructorR(void);
void testSortBubble(void);
void testDisplayAll(void);
void testIsSorted(void);
///////////////////////////////////////////////////////////
// class CArray
///////////////////////////////////////////////////////////
class CArray
{
private:
int m_a[MAX_COUNT];
int m_n;
public:
CArray(void);
CArray(int m);
void display(void) const;
void displayMultiple(int c) const;
void populate(void);
bool areDistinct(void) const;
bool searchSeq(int x) const;
CArray(char ch);
void sortBubble(void);
void displayAll(void) const;
bool isSorted(void);
};
///////////////////////////////////////////////////////////
// void main(void)
///////////////////////////////////////////////////////////
void main(void)
{
//srand(time(NULL));
srand(2);
// testSearchSeq();
// testAreDistinct();
// testConstructorR();
// testSortBubble();
// testDisplayAll();
testIsSorted();
}
///////////////////////////////////////////////////////////
// void testIsSorted(void)
///////////////////////////////////////////////////////////
void testIsSorted(void)
{
cout << "testIsSorted\n";
cout << "============\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray myArray('r');
myArray.display();
if (myArray.isSorted())
cout << "myArray is sorted\n";
else
cout << "myArray is NOT sorted\n";
myArray.sortBubble();
cout << "After sortBubble\n";
myArray.display();
if (myArray.isSorted())
cout << "myArray is sorted\n";
else
cout << "myArray is NOT sorted\n";
cout << "------------------------\n";
}
}
///////////////////////////////////////////////////////////
//bool CArray::isSorted(void)
///////////////////////////////////////////////////////////
/*
a[1,3,6] => true
a[3,3,1] => false
a[3,3,9] => true
Algorithm0:
if a[0] and a[1] out of order then return false
if a[1] and a[2] out of order then return false
if a[2] and a[3] out of order then return false
...
if a[n-2] and a[n-1] out of order then return false
return true
Algorithm1:
do the following for i= 0 to n-2
if a[i] and a[i+1] out of order then return false
end do
return true
*/
bool CArray::isSorted(void)
{
for (int i= 0; i<= m_n-2; i++)
if (m_a[i] > m_a[i+1])
return false;
return true;
}
///////////////////////////////////////////////////////////
// void testDisplayAll(void)
///////////////////////////////////////////////////////////
void testDisplayAll(void)
{
cout << "testDisplayAll\n";
cout << "==============\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray array1('r');
array1.display();
array1.displayAll();
}
}
///////////////////////////////////////////////////////////
// void CArray::displayAll(void) const
///////////////////////////////////////////////////////////
void CArray::displayAll(void) const
{
cout << "array[" << m_n << "]=";
for (int i=0; i<MAX_COUNT; i++)
cout << m_a[i] << ' ';
cout << endl;
}
///////////////////////////////////////////////////////////
// void testSortBubble(void)
///////////////////////////////////////////////////////////
void testSortBubble(void)
{
cout << "testSortBubble\n";
cout << "==============\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray array1('r');
array1.display();
array1.sortBubble();
cout << "After sortBubble\n";
array1.display();
}
}
///////////////////////////////////////////////////////////
// void CArray::sortBubble(void)
///////////////////////////////////////////////////////////
/*
Sorts array contets in increasing order
[2, 3, 1] => [1, 2, 3]
Algorithm:
Check for special cases
repeat
from left to right put values in order
while something changed
somethingChanged = true
while somethingChanged = true
somethingChanged = false
do the following for i=0 to n-2
if a[i] > a[i+1] then
switch a[i] and a[i+1]
somethingChanged = true
end if
end while
repeat
somethingChanged = false
do the following for i=0 to n-2
if a[i] > a[i+1] then
switch a[i] and a[i+1]
somethingChanged = true
end if
while something changed
*/
void CArray::sortBubble(void)
{
if (m_n <= 1)
return;
bool somethingChanged;
int i;
do
{
somethingChanged = false;
for (i=0; i<=m_n-2; i++)
{
if (m_a[i] > m_a[i+1])
{
int temp = m_a[i+1];
m_a[i+1] = m_a[i];
m_a[i] = temp;
somethingChanged = true;
}
}
} while (somethingChanged == true);
}
///////////////////////////////////////////////////////////
// void testConstructorR(void)
///////////////////////////////////////////////////////////
void testConstructorR(void)
{
cout << "testConstructorR\n";
cout << "================\n";
for (int i=1; i<=10; i++)
{
cout << "Case #" << i << endl;
CArray array1('r');
array1.display();
}
}
///////////////////////////////////////////////////////////
// CArray::CArray(char ch)
///////////////////////////////////////////////////////////
/*
A constructor fills array with values
depending on the value of parameter ch.
If ch is equal to 'r' then it fills the
array with random values which are
also random in count.
CArray array1('r');
gives: m_a[4,1,2], m_n=3
CArray array2('r');
gives: m_a[4,1,2,3,5,3], m_n=6
Algorithm:
m_n = random integer bet 0 and MAX_COUNT
do the following for i=0 to m_n-1
m_a[i] = random integer between 0 and MAX_VALUE
*/
CArray::CArray(char ch)
{
if (('r'==ch) || ('R'==ch))
{
m_n = rand()%(MAX_COUNT+1);
for (int i=0; i<=m_n-1; i++)
m_a[i] = rand()%(MAX_VALUE+1);
for (i=m_n; i<MAX_COUNT; i++)
m_a[i] = UNDEFINED;
}
else
m_n = 0;
}
///////////////////////////////////////////////////////////
// void testAreDistinct(void)
///////////////////////////////////////////////////////////
void testAreDistinct(void)
{
cout << "testAreDistinct\n";
cout << "===============\n";
for (int p=1; p <= 10; p++)
{
cout << "Case #" << p << endl;
int n = rand()%(MAX_COUNT+1);
CArray myArray(n);
myArray.display();
if (myArray.areDistinct())
cout << "Array has distinct values\n";
else
cout << "Array does not have distinct values\n";
cout << "--------------------------------------\n";
}
}
///////////////////////////////////////////////////////////
// bool CArray::areDistinct(void) const
///////////////////////////////////////////////////////////
bool CArray::areDistinct(void) const
{
if (m_n <= 1)
return true;
else
{
for (int i=1; i<=m_n-1; i++)
for (int j=0; j<=i-1; j++)
if (m_a[i] == m_a[j])
return false;
return true;
}
}
///////////////////////////////////////////////////////////
// void testSearchSeq(void)
///////////////////////////////////////////////////////////
void testSearchSeq(void)
{
cout << "testSearchSeq\n";
cout << "=============\n";
for (int p=1; p <= 10; p++)
{
cout << "Case #" << p << endl;
int n = rand()%(MAX_COUNT+1);
CArray myArray(n);
myArray.display();
int x;
x = rand()%(MAX_VALUE+1);
if (myArray.searchSeq(x))
cout << x << " is in the Array\n";
else
cout << x << " is NOT in the Array\n";
cout << "--------------------------------------\n";
}
}
///////////////////////////////////////////////////////////
// bool CArray::searchSeq(int x) const
///////////////////////////////////////////////////////////
bool CArray::searchSeq(int x) const
{
for (int i=0; i<=m_n-1; i++)
if (x == m_a[i])
return true;
return false;
}
///////////////////////////////////////////////////////////
// CArray::CArray(int m)
///////////////////////////////////////////////////////////
CArray::CArray(int m)
{
m_n = m;
for (int i=0; i<=m_n-1; i++)
m_a[i] = rand()%(MAX_VALUE+1);
for (i=m_n; i<MAX_COUNT; i++)
m_a[i] = UNDEFINED;
}
///////////////////////////////////////////////////////////
// void CArray::populate(void)
///////////////////////////////////////////////////////////
void CArray::populate(void)
{
m_n = rand()%(MAX_COUNT+1);
for (int i=0; i<=m_n-1; i++)
m_a[i] = rand()%(MAX_VALUE+1);
}
///////////////////////////////////////////////////////////
// void CArray::displayMultiple(int c)
///////////////////////////////////////////////////////////
void CArray::displayMultiple(int c) const
{
for (int i=1; i<=c; i++)
display();
};
///////////////////////////////////////////////////////////
// void CArray::display(void) const
///////////////////////////////////////////////////////////
void CArray::display(void) const
{
cout << "array[" << m_n << "]=";
for (int i=0; i<=m_n-1; i++)
cout << m_a[i] << ' ';
cout << endl;
}
///////////////////////////////////////////////////////////
// CArray::CArray(void)
///////////////////////////////////////////////////////////
CArray::CArray(void)
{
m_n=0;
for (int i=0; i<MAX_COUNT; i++)
m_a[i] = UNDEFINED;
cout << "Default constructor for CArray called\n";
}
///////////////////////////////////////////////////////////
// SAMPLE RUN
///////////////////////////////////////////////////////////
/*
testIsSorted
============
Case #1
array[1]=2
myArray is sorted
After sortBubble
array[1]=2
myArray is sorted
------------------------
Case #2
array[9]=5 0 0 4 1 1 4 1 1
myArray is NOT sorted
After sortBubble
array[9]=0 0 1 1 1 1 4 4 5
myArray is sorted
------------------------
Case #3
array[2]=0 5
myArray is sorted
After sortBubble
array[2]=0 5
myArray is sorted
------------------------
Case #4
array[9]=5 1 4 5 5 1 5 3 3
myArray is NOT sorted
After sortBubble
array[9]=1 1 3 3 4 5 5 5 5
myArray is sorted
------------------------
Case #5
array[10]=4 0 5 0 0 3 4 1 3 0
myArray is NOT sorted
After sortBubble
array[10]=0 0 0 0 1 3 3 4 4 5
myArray is sorted
------------------------
Case #6
array[3]=0 2 3
myArray is sorted
After sortBubble
array[3]=0 2 3
myArray is sorted
------------------------
Case #7
array[0]=
myArray is sorted
After sortBubble
array[0]=
myArray is sorted
------------------------
Case #8
array[1]=4
myArray is sorted
After sortBubble
array[1]=4
myArray is sorted
------------------------
Case #9
array[2]=5 2
myArray is NOT sorted
After sortBubble
array[2]=2 5
myArray is sorted
------------------------
Case #10
array[9]=3 1 2 0 0 3 4 2 5
myArray is NOT sorted
After sortBubble
array[9]=0 0 1 2 2 3 3 4 5
myArray is sorted
------------------------
Press any key to continue
*/
|