//Date: 2003.03.28
//Author: AOU
//File: areDistinct6.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);
void purgeDupes2(int a[], int &n);
void testPurgeDupes2(void);
///////////////////////////////////////////////////////////
// constants
///////////////////////////////////////////////////////////
const int MAX_COUNT = 20; //maximum size of array
const int MAX_VALUE = 3;
///////////////////////////////////////////////////////////
// main function
///////////////////////////////////////////////////////////
void main(void)
{
//testAreDistinct();
//testSearchSeq();
//testDeleteAtPos();
//testPurgeDupes();
testPurgeDupes2();
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
/*
void purgeDupes2(int a[], int &n)
Algorithm0:
from first to last-1 value do the following
delete all the matching value on the right side
advance to right
end loop
Algorithm1:
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
Algorithm2:
from first to last-1 value do the following
do the following
matchFound=false
if there is a matching value on right then
matchFound = true
delete the matching value on the right side
until matchFound is false
advance to right
end loop
Algorithm3:
i=0
while i <= n-2 do the following
do the following
matchFound=false
if there is a matching value on right then
matchFound = true
delete the matching value on the right side
until matchFound is false
increase i by 1
end while
Algorithm4:
i=0
while i <=n-2 do the following
do the following
matchFound=false
j=i+1
while j<=n-1
if a[i] is equal to a[j] then
matchFound = true
delete a[j]
else
increase j by 1
end if
end while
until matchFound is false
increase i by 1
end while
*/
void purgeDupes2(int a[], int &n)
{
int i, j;
bool matchFound;
i=0;
while (i <= n-2)
{
do
{
matchFound=false;
j=i+1;
while (j<=n-1)
{
if (a[i] == a[j]) //[3, 1, 3, 3, 3]
{
cout << "Match found\n";
display(a, n);
cout << "j=" << j << endl;
matchFound = true;
deleteAtPos(a, n, j);
cout << "After delete\n";
display(a, n);
cout << "j=" << j << endl;
}
j++;
cout << "Outside the loop\n";
display(a, n);
cout << "j=" << j << endl;
}
}
while (matchFound);
i++;
}
}
///////////////////////////////////////////////////////////
// void testPurgeDupes2(void)
///////////////////////////////////////////////////////////
void testPurgeDupes2(void)
{
cout << "testPurgeDupes2\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 testPurgeDupes2\n";
display(a, n);
purgeDupes2(a, n);
cout << "After call to testPurgeDupes2\n";
display(a, n);
cout << "--------------------------------------\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
///////////////////////////////////////////////////////////
/*
--------------------------------------
Case #6
Before call to testPurgeDupes2
a[12]=1 1 0 1 3 0 2 0 0 2 0 3
Match found
a[12]=1 1 0 1 3 0 2 0 0 2 0 3
j=1
After delete
a[11]=1 0 1 3 0 2 0 0 2 0 3
j=1
Outside the loop
a[11]=1 0 1 3 0 2 0 0 2 0 3
j=2
Match found
a[11]=1 0 1 3 0 2 0 0 2 0 3
j=2
After delete
a[10]=1 0 3 0 2 0 0 2 0 3
j=2
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=3
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=4
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=5
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=6
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=7
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=8
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=9
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=10
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=2
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=3
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=4
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=5
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=6
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=7
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=8
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=9
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=10
Outside the loop
a[10]=1 0 3 0 2 0 0 2 0 3
j=3
Match found
a[10]=1 0 3 0 2 0 0 2 0 3
j=3
After delete
a[9]=1 0 3 2 0 0 2 0 3
j=3
Outside the loop
a[9]=1 0 3 2 0 0 2 0 3
j=4
Match found
a[9]=1 0 3 2 0 0 2 0 3
j=4
After delete
a[8]=1 0 3 2 0 2 0 3
j=4
Outside the loop
a[8]=1 0 3 2 0 2 0 3
j=5
Outside the loop
a[8]=1 0 3 2 0 2 0 3
j=6
Match found
a[8]=1 0 3 2 0 2 0 3
j=6
After delete
a[7]=1 0 3 2 0 2 3
j=6
Outside the loop
a[7]=1 0 3 2 0 2 3
j=7
Outside the loop
a[7]=1 0 3 2 0 2 3
j=3
Outside the loop
a[7]=1 0 3 2 0 2 3
j=4
Match found
a[7]=1 0 3 2 0 2 3
j=4
After delete
a[6]=1 0 3 2 2 3
j=4
Outside the loop
a[6]=1 0 3 2 2 3
j=5
Outside the loop
a[6]=1 0 3 2 2 3
j=6
Outside the loop
a[6]=1 0 3 2 2 3
j=3
Outside the loop
a[6]=1 0 3 2 2 3
j=4
Outside the loop
a[6]=1 0 3 2 2 3
j=5
Outside the loop
a[6]=1 0 3 2 2 3
j=6
Outside the loop
a[6]=1 0 3 2 2 3
j=4
Outside the loop
a[6]=1 0 3 2 2 3
j=5
Match found
a[6]=1 0 3 2 2 3
j=5
After delete
a[5]=1 0 3 2 2
j=5
Outside the loop
a[5]=1 0 3 2 2
j=6
Outside the loop
a[5]=1 0 3 2 2
j=4
Outside the loop
a[5]=1 0 3 2 2
j=5
Match found
a[5]=1 0 3 2 2
j=4
After delete
a[4]=1 0 3 2
j=4
Outside the loop
a[4]=1 0 3 2
j=5
After call to testPurgeDupes2
a[4]=1 0 3 2
--------------------------------------
Press any key to continue
*/
|