//Date: 2003.03.26
//Author: AOU
//File: areDistinct5_p01.cpp
/* Project01 Assigned 2/3/2003, Due 2/10/2003
develop deleteAtPos, testDeleteAtPos,
purgeDupes, testPurgeDupes
Submit:
function testFunction
Function description yes yes
Examples yes no
Algorithm yes yes
Source code yes yes
Output from test cases (10) no yes
*/
///////////////////////////////////////////////////////////
// include files
///////////////////////////////////////////////////////////
#include <iostream.h>
#include <stdlib.h>
///////////////////////////////////////////////////////////
// prototypes
///////////////////////////////////////////////////////////
bool areDistinct(int a[], int n);
void populate(int a[], int &n);
void display(int a[], int n);
void testAreDistinct(void);
bool searchSeq(int a[], int n, int x);
void testSearchSeq(void);
bool deleteAtPos(int a[], int &n, int id);
void testDeleteAtPos(void);
void purgeDupes(int a[], int &n);
void testPurgeDupes(void);
///////////////////////////////////////////////////////////
// constants
///////////////////////////////////////////////////////////
const int MAX_COUNT = 10; //maximum size of array
const int MAX_VALUE = 5;
///////////////////////////////////////////////////////////
// main function
///////////////////////////////////////////////////////////
void main(void)
{
//testAreDistinct();
//testSearchSeq();
testDeleteAtPos();
testPurgeDupes();
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
/*
void purgeDupes2(int a[], int &n)
from first to last-1 value do the following
while there a matching value on the right side do the following
delete the matching value on the right side
advance to right
end loop
*/
void purgeDupes2(int a[], int &n)
{
}
///////////////////////////////////////////////////////////
// void purgeDupes(int a[], int &n)
///////////////////////////////////////////////////////////
/*
purgeDupes
Description:
This function deletes duplicate values from an array
Example:
before: a[] = {2, 3, 2, 4, 5, 3}, n = 6
a[] = {2, 3, 4, 5, 3}, n = 5
a[] = {2, 3, 4, 5}, n = 4
after: a[] = {2, 3, 4, 5}, n = 4
Algorithm0:
Handle special cases first
from second value to the last value do the following
if this value is in the left sublist then delete it
Algorithm1:
//Handle special cases first
if n=1 or n=0 then exit function
from second value to the last value do the following
if current value matches a value on the left then
delete the current value
else
advance to the next value
Algorithm2:
//Handle special cases first
if n=1 or n=0 then exit function
i = 1
while i less than or equal to n-1
//if current value matches a value on the left then
matchFound = false
for j=0 to i-1
if a[i] = a[j] then
matchFound = true
exit for loop
end for
if matchFound is true
delete the value at i (n is decreased by delete function)
else
i++
end while
Source Code:
void purgeDupes(int a[], int &n)
{
}
Output:
case#1:
before: a[] = {2, 3, 2, 4, 5, 3}, n = 6
after: a[] = {2, 3, 4, 5}, n = 4
*/
void purgeDupes(int a[], int &n)
{
//Handle special cases first
if (1==n || 0==n)
return;
int i = 1;
while (i <= n-1)
{
//if current value matches a value on the left then
bool matchFound = false;
for (int j=0; j<=i-1; j++)
{
if (a[i] == a[j])
{
matchFound = true;
break;
}
}
if (matchFound)
deleteAtPos(a,n,i);
else
i++;
}
}
///////////////////////////////////////////////////////////
// void testPurgeDupes(void)
///////////////////////////////////////////////////////////
void testPurgeDupes(void)
{
cout << "testPurgeDupes\n";
cout << "==============\n";
int a[MAX_COUNT];
int n;
for (int p=1; p <= 10; p++)
{
cout << "Case #" << p << endl;
populate(a, n);
cout << "Before call to testPurgeDupes\n";
display(a, n);
purgeDupes(a, n);
cout << "After call to testPurgeDupes\n";
display(a, n);
cout << "--------------------------------------\n";
}
}
///////////////////////////////////////////////////////////
// bool deleteAtPos(int a[], int &n, int id)
///////////////////////////////////////////////////////////
/*
deleteAtPos
Description:
This function deletes a value from an array given the
index of the value
Example:
before: a[] = {2, 3, 2, 4, 5, 3}, n = 6, id=2
after: a[] = {2, 3, 4, 5, 3}, n = 5, id=2
before: a[] = {20, 30, 20, 40, 50, 30}, n = 6, id=5
after: a[] = {20, 30, 20, 40, 50}, n = 5, id=5
Algorithm0:
Handle special cases first
Move values at id+1 to id
id+2 to id+1
id+3 to id+2
...
n-1 to n-2
Decrease value of n by 1
Algorithm1:
//Handle special cases first
if id < 0 or id>=n then
return false
//shift necessary values to left
for i=id to n-2 do the following
a[i] = a[i+1]
Decrease value of n by 1
return true
Output:
case#1:
before: a[] = {2, 3, 2, 4, 5, 3}, n = 6, id=2
after: a[] = {2, 3, 4, 5, 3}, n = 5, id=2
*/
bool deleteAtPos(int a[], int &n, int id)
{
//Handle special cases first
if ((id<0) || (id>=n))
return false;
for (int i=id; i<=n-2; i++)
a[i] = a[i+1];
n--;
return true;
}
///////////////////////////////////////////////////////////
// void testDeleteAtPos(void)
///////////////////////////////////////////////////////////
void testDeleteAtPos(void)
{
cout << "testDeleteAtPos\n";
cout << "===============\n";
int a[MAX_COUNT];
int n;
int id, tRand;
bool success;
for (int p=1; p <= 10; p++)
{
cout << "Case #" << p << endl;
populate(a, n);
cout << "Before call to deleteAtPos\n";
display(a, n);
//id = rand()%(MAX_COUNT)-1;
id = rand()%(n+1) - 1;
//id = rand()%(MAX_COUNT);
//id = rand()%n;
//10% id<0, 10% id>=n, 80% id is [0,n-1]
tRand = 1 + rand()%100;
if (tRand<=10)
id = -1;
else if (tRand>=91)
id = n;
else if (n!=0 && tRand>=11 && tRand<=90)
id = rand()%n;
else
id = -1;
cout << "Trying to delete value at " << id << endl;
success = deleteAtPos(a, n, id);
if (success)
cout << "deletion was successful\n";
else
cout << "deletion was NOT successful\n";
cout << "After call to deleteAtPos\n";
display(a, n);
cout << "--------------------------------------\n";
}
}
///////////////////////////////////////////////////////////
// void testSearchSeq(void)
///////////////////////////////////////////////////////////
void testSearchSeq(void)
{
cout << "testSearchSeq\n";
cout << "=============\n";
int a[MAX_COUNT];
int n;
int x;
for (int p=1; p <= 10; p++)
{
cout << "Case #" << p << endl;
populate(a, n);
display(a, n);
x = rand()%(MAX_VALUE+1);
if (searchSeq(a, n, x))
cout << x << " is in the Array\n";
else
cout << x << " is NOT in the Array\n";
cout << "--------------------------------------\n";
}
}
///////////////////////////////////////////////////////////
// bool searchSeq(int a[], int n, int x)
///////////////////////////////////////////////////////////
/*
Algorithm:
do the following for i=0 to n-1
if x = a[i] then
return true
next i
return false
*/
bool searchSeq(int a[], int n, int x)
{
for (int i=0; i<=n-1; i++)
if (x == a[i])
return true;
return false;
}
///////////////////////////////////////////////////////////
// void testAreDistinct(void)
///////////////////////////////////////////////////////////
void testAreDistinct(void)
{
cout << "testAreDistinct\n";
cout << "===============\n";
int a[MAX_COUNT];
int n;
for (int p=1; p <= 10; p++)
{
cout << "Case #" << p << endl;
populate(a, n);
display(a, n);
if (areDistinct(a, n))
cout << "Array has distinct values\n";
else
cout << "Array does not have distinct values\n";
cout << "--------------------------------------\n";
}
}
///////////////////////////////////////////////////////////
// bool areDistinct(int a[], int n)
///////////////////////////////////////////////////////////
/* A function to check if all the values are unique/distinct
Algorithm
if n <= 1 then
return true
else
do the following for i=1 to n-1
do the following for j=0 to i-1
if a[i] = a[j] then
return false
next j
next i
return true
*/
bool areDistinct(int a[], int n)
{
if (n <= 1)
return true;
else
{
for (int i=1; i<=n-1; i++)
if (searchSeq(a, i, a[i]))
return false;
/*
for (j=0; j<=i-1; j++)
if (a[i] == a[j])
return false;
*/
return true;
}
}
///////////////////////////////////////////////////////////
// void populate(int a[], int &n)
///////////////////////////////////////////////////////////
//A function to fill an array (a) with random values
/*
Algorithm
n = random number between 0 to MAX_COUNT
do the following for i=0 to n-1
a[i] = random number between 0 to MAX_VALUE
*/
void populate(int a[], int &n)
{
n = rand()%(MAX_COUNT+1);
for (int i=0; i<=n-1; i++)
a[i] = rand()%(MAX_VALUE+1);
}
///////////////////////////////////////////////////////////
// void display(int a[], int n)
///////////////////////////////////////////////////////////
void display(int a[], int n)
{
cout << "a[" << n << "]=";
for (int i=0; i<=n-1; i++)
cout << a[i] << ' ';
cout << endl;
}
///////////////////////////////////////////////////////////
// SAMPLE OUTPUT
///////////////////////////////////////////////////////////
/*
testDeleteAtPos
===============
Case #1
Before call to deleteAtPos
a[8]=5 4 4 5 4 0 0 4
Trying to delete value at -1
deletion was NOT successful
After call to deleteAtPos
a[8]=5 4 4 5 4 0 0 4
--------------------------------------
Case #2
Before call to deleteAtPos
a[7]=1 3 1 5 1 2 3
Trying to delete value at 7
deletion was NOT successful
After call to deleteAtPos
a[7]=1 3 1 5 1 2 3
--------------------------------------
Case #3
Before call to deleteAtPos
a[7]=2 3 4 4 3 2 2
Trying to delete value at 5
deletion was successful
After call to deleteAtPos
a[6]=2 3 4 4 3 2
--------------------------------------
Case #4
Before call to deleteAtPos
a[9]=0 3 4 5 1 1 0 5 3
Trying to delete value at 6
deletion was successful
After call to deleteAtPos
a[8]=0 3 4 5 1 1 5 3
--------------------------------------
Case #5
Before call to deleteAtPos
a[0]=
Trying to delete value at -1
deletion was NOT successful
After call to deleteAtPos
a[0]=
--------------------------------------
Case #6
Before call to deleteAtPos
a[5]=4 5 2 4 3
Trying to delete value at 3
deletion was successful
After call to deleteAtPos
a[4]=4 5 2 3
--------------------------------------
Case #7
Before call to deleteAtPos
a[6]=1 4 4 5 2 0
Trying to delete value at -1
deletion was NOT successful
After call to deleteAtPos
a[6]=1 4 4 5 2 0
--------------------------------------
Case #8
Before call to deleteAtPos
a[9]=2 4 4 2 3 2 3 4 2
Trying to delete value at -1
deletion was NOT successful
After call to deleteAtPos
a[9]=2 4 4 2 3 2 3 4 2
--------------------------------------
Case #9
Before call to deleteAtPos
a[6]=2 3 5 0 4 0
Trying to delete value at 2
deletion was successful
After call to deleteAtPos
a[5]=2 3 0 4 0
--------------------------------------
Case #10
Before call to deleteAtPos
a[5]=4 0 3 2 1
Trying to delete value at 3
deletion was successful
After call to deleteAtPos
a[4]=4 0 3 1
--------------------------------------
testPurgeDupes
==============
Case #1
Before call to testPurgeDupes
a[3]=3 5 3
After call to testPurgeDupes
a[2]=3 5
--------------------------------------
Case #2
Before call to testPurgeDupes
a[7]=1 0 0 0 3 2 5
After call to testPurgeDupes
a[5]=1 0 3 2 5
--------------------------------------
Case #3
Before call to testPurgeDupes
a[1]=5
After call to testPurgeDupes
a[1]=5
--------------------------------------
Case #4
Before call to testPurgeDupes
a[2]=2 4
After call to testPurgeDupes
a[2]=2 4
--------------------------------------
Case #5
Before call to testPurgeDupes
a[0]=
After call to testPurgeDupes
a[0]=
--------------------------------------
Case #6
Before call to testPurgeDupes
a[10]=5 3 3 0 4 0 5 0 5 5
After call to testPurgeDupes
a[4]=5 3 0 4
--------------------------------------
Case #7
Before call to testPurgeDupes
a[5]=4 5 4 2 4
After call to testPurgeDupes
a[3]=4 5 2
--------------------------------------
Case #8
Before call to testPurgeDupes
a[1]=4
After call to testPurgeDupes
a[1]=4
--------------------------------------
Case #9
Before call to testPurgeDupes
a[7]=4 3 5 1 3 1 5
After call to testPurgeDupes
a[4]=4 3 5 1
--------------------------------------
Case #10
Before call to testPurgeDupes
a[0]=
After call to testPurgeDupes
a[0]=
--------------------------------------
Press any key to continue
*/
|