//Date: 2003.09.17
//File: NOB_List06_Project01.cpp
//Author: AOU
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
/*
project 01: 09/17/2003 - 09/24/2003
implement the following fnctions with
corresponding test functions:
bool deleteAtPos(int a[], int &n, int p);
int deleteDupes(int a[], int &n)
Submit the following (on paper and disk)
for each function:
5 description
5 examples (2)
5 algorithm
5 properly indented function
5 properly indented test function
5 properly labeled output
*/
/*
maintain an ordered list of integeres
*/
////////////////////////////////////////
//constants
////////////////////////////////////////
const int MAX_SIZE = 25;
const int TEST_COUNT = 19;
const int MAX_VALUE = 15;
const int UNDEFINED = -911;
////////////////////////////////////////
//prototypes
////////////////////////////////////////
void display(int a[], int n);
void initialize(int a[], int n);
bool insert(int a[], int &n, int x);
void swap(int &x, int &y);
bool isSorted(int a[], int n);
void shuffle(int a[], int n);
void testShuffle(void);
void populate(int a[], int n);
void sortBubble(int a[], int n);
void testSortBubble(void);
void testInsert(void);
bool deleteAtPos(int a[], int &n, int p);
void testDeleteAtPos(void);
int deleteDupes(int a[], int &n);
void testDeleteDupes(void);
////////////////////////////////////////
//main
////////////////////////////////////////
void main(void)
{
srand(time(NULL));
//testInsert();
//testShuffle();
//testSortBubble();
//testDeleteAtPos();
testDeleteDupes();
}
////////////////////////////////////////
//testDeleteDupes
////////////////////////////////////////
void testDeleteDupes(void)
{
cout << "+++++++++++++++\n";
cout << "testDeleteDupes\n";
cout << "+++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
int values[MAX_SIZE];
initialize(values, MAX_SIZE);
int n = rand()%(MAX_SIZE+1);
populate(values, n);
cout << "Original list\n";
display(values, n);
int result = deleteDupes(values, n);
cout << result << " deleted\n";
display(values, n);
cout << "*****************\n";
}
}
////////////////////////////////////////
//int deleteDupes(int a[], int &n)
////////////////////////////////////////
/*
Algorithm0:
do
find a duplicate and delete it
while duplicate found and deleted
Algorithm1:
do
p = -1
for i=0 to n-2
if a[i] = a[i+1] then
p = i+1
delete the value at position p
exit for
end if
end for
while p<>-1
*/
int deleteDupes(int a[], int &n)
{
int p, deleted=0;
do
{
p = -1;
for (int i=0; i<=n-2; i++)
if (a[i] == a[i+1])
{
p = i+1;
deleteAtPos(a, n, p);
deleted++;
break;
}
} while (p != -1);
return deleted;
}
////////////////////////////////////////
//testDeleteAtPos
////////////////////////////////////////
void testDeleteAtPos(void)
{
cout << "+++++++++++++++\n";
cout << "testDeleteAtPos\n";
cout << "+++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
int values[MAX_SIZE];
initialize(values, MAX_SIZE);
int n = rand()%(MAX_SIZE+1);
populate(values, n);
cout << "Original list\n";
display(values, n);
int p = rand()%(MAX_SIZE+1+10)-5;
cout << "About to delete value at position " << p << endl;
int result = deleteAtPos(values, n, p);
if (result)
cout << "delete was successful\n";
else
cout << "delete was NOT successful\n";
display(values, n);
cout << "*****************\n";
}
}
////////////////////////////////////////
//bool deleteAtPos(int a[], int &n, int p)
////////////////////////////////////////
/*
Algorithm0:
if p is out of range then return false
p is in range then
shift the values right to p to one position left
Algorithm1:
if p is out of range then
return false
else
for i=p to n-2 do the following
a[i] = a[i+1]
end for
a[n-1] = UNDEFINED
n--
return true
end if
*/
bool deleteAtPos(int a[], int &n, int p)
{
if (p<0 || p>=n)
return false;
else
{
for (int i=p; i<=n-2; i++)
a[i] = a[i+1];
a[n-1] = UNDEFINED;
n--;
return true;
}
}
////////////////////////////////////////
//testSortBubble
////////////////////////////////////////
void testSortBubble(void)
{
cout << "++++++++++++++\n";
cout << "testSortBubble\n";
cout << "++++++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
int values[MAX_SIZE];
initialize(values, MAX_SIZE);
int n = rand()%(MAX_SIZE+1);
populate(values, n);
cout << "Original list\n";
display(values, n);
shuffle(values, n);
cout << "After shuffle\n";
display(values, n);
cout << "After sortBubble\n";
sortBubble(values, n);
display(values, n);
cout << "*****************\n";
}
}
////////////////////////////////////////
//sortBubble
////////////////////////////////////////
/*
Description:
Puts the values in increasing order by using
the bubble sort method
Example:
[23, 13, 67, 12] => [12, 13, 23, 67]
Algorithm:
do
swaps = 0
from i=0 to n-2
if a[i] > a[i+1] then
swap (a[i], a[i+1])
swaps++
end if
end loop
until swps = 0
*/
void sortBubble(int a[], int n)
{
int swaps;
do
{
swaps = 0;
for (int i=0; i<=n-2; i++)
if (a[i] > a[i+1])
{
swap(a[i], a[i+1]);
swaps++;
}
} while (swaps!=0);
}
////////////////////////////////////////
//testShuffle
////////////////////////////////////////
void testShuffle(void)
{
cout << "+++++++++++\n";
cout << "testShuffle\n";
cout << "+++++++++++\n";
for (int c=1; c<=TEST_COUNT; c++)
{
int values[MAX_SIZE];
initialize(values, MAX_SIZE);
int n = rand()%(MAX_SIZE+1);
populate(values, n);
display(values, n);
shuffle(values, n);
cout << "After shuffle\n";
display(values, n);
cout << "*****************\n";
}
}
////////////////////////////////////////
//populate
////////////////////////////////////////
void populate(int a[], int n)
{
int m=0;
for (int i=1; i<=n; i++)
{
int x = rand()%(MAX_VALUE+1);
insert(a, m, x);
}
}
////////////////////////////////////////
//shuffle
////////////////////////////////////////
/*
Description:
Examples:
a[]={12, 14, 20, 21];
Algorithm:
do the following n*n time
pick a number in pick randomly between 0 and n-1
swap a[0] with a[pick]
*/
void shuffle(int a[], int n)
{
for (int i=1; i<=n*n; i++)
{
int pick = rand()%n;
swap (a[0], a[pick]);
}
}
////////////////////////////////////////
//isSorted
////////////////////////////////////////
/*
Description:
Examples:
Algorithm:
*/
bool isSorted(int a[], int n)
{
for (int i=0; i<=n-2; i++)
if (a[i] > a[i+1])
return false;
return true;
}
////////////////////////////////////////
////////////////////////////////////////
void swap(int &x, int &y)
{
if (x != y)
{
int temp = x;
x = y;
y = temp;
}
}
void testInsert(void)
{
int values[MAX_SIZE];
initialize(values, MAX_SIZE);
int n = 0;
for (int c=1; c<=TEST_COUNT; c++)
{
int x = rand()%(MAX_VALUE+1);
bool result = insert(values, n, x);
if (result == true)
cout << "Insertion of " << x << " was a success\n";
else
cout << "Insertion of " << x << " was NOT a success\n";
display(values, n);
if (isSorted(values, n) == true)
cout << "List is sorted\n";
else
cout << "List is NOT sorted\n";
int p1 = rand()%n;
int p2 = rand()%n;
swap(values[p1], values[p2]);
display(values, n);
if (isSorted(values, n) == true)
cout << "List is sorted\n";
else
cout << "List is NOT sorted\n";
swap(values[p1], values[p2]);
display(values, n);
cout << "***********************\n";
}
}
/*
insert x in a[]
Cases:
if n = 0 then ...
if n = MAX_SIZE then ...
if n > 0 then
a[n] = x
n++
for i=n-1 to 1 step -1
if a[i] >= a[i-1] then get out of the for loop/function
swap(a[i], a[i-1])
end for
end if
*/
bool insert(int a[], int &n, int x)
{
if (0 == n)
{
a[n] = x;
n++;
return true;
};
if (MAX_SIZE == n)
return false;
if (n > 0)
{
a[n] = x;
n++;
for (int i=n-1; i>=1; i--)
{
if (a[i] >= a[i-1]) return true;
swap(a[i], a[i-1]);
}
return true;
}
return false;
}
void initialize(int a[], int n)
{
for (int i=0; i<=n-1; i++)
a[i] = UNDEFINED;
}
void display(int a[], int n)
{
cout << "a[" << n << "]: ";
for (int i=0; i<=n-1; i++)
cout << a[i] << ' ';
cout << endl;
}
/*
SAMPLE RUN:
*/
|