//Date: 2003.02.03
//Author: AOU
//File: areDistinct4.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);
/* 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
*/
/*
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
Algorithm:
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
Source Code:
bool deleteAtPos(int a[], int &n, int id)
{
}
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
*/
/*
purgeDupes
Description:
This function deletes duplicate values from an array
Example:
before: a[] = {2, 3, 2, 4, 5, 3}, n = 6
before: a[] = {2, 3, 4, 5, 3}, n = 5
before: a[] = {2, 3, 4, 5}, n = 4
after: a[] = {2, 3, 4, 5}, n = 4
Algorithm:
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
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
*/
///////////////////////////////////////////////////////////
// constants
///////////////////////////////////////////////////////////
const int MAX_COUNT = 10; //maximum size of array
const int MAX_VALUE = 5;
///////////////////////////////////////////////////////////
// main function
///////////////////////////////////////////////////////////
void main(void)
{
//testAreDistinct();
//testSearchSeq();
}
///////////////////////////////////////////////////////////
// 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
///////////////////////////////////////////////////////////
/*
*/
|