The set class is used to represent sets of integers. It supports most of the sta
ID: 3800190 • Letter: T
Question
The set class is used to represent sets of integers. It supports most of the standard set operations.
class Set {
public:
//default constructor
Set();
//add element to set
void addElement (int element);
//remove element from set
void removeElement(int element);
//check for membership
bool isMember(int element);
//set union, modifies curremtn set
void Union (Set s);
//set difference modifiers current set
void diffeence (Set s);
//size of set
int size();
//get element i
int getElement (int i);
private:
//binary search for element, returns index
bool search(int element, int& index);
//set members
int elements[maxElements];
//next empty position in elements
int next;
};
void printSet(Set s);
void generateSample(int sample[], int n);
void run(int sample[], int n);
Overload the following operators the class Set:
bool opertor ==(const Set& s); //equality comparison
bool oprator !=(const Set& s); //inequality comparion
Set& operator + (int element); //add element operator
Set& operator + (const Set& s); // set union opreator
Set& operator - _int element); //remove element operator
Set& operator - (const Set& s); //aset difference operator
****************************************************************************************
Set data structure:
1. A set is a collection of objects need not to be in any particular order. Elements
* should not be repeated.
2. UNION: Combine two or more sets (here two sets)
3. INTERSECTION: Gathering common elements in both the sets together as a single set
4. DIFFERENCE: Forming a set with elements which are in first set and not in second
set
A-B= {x| for all x belongs to A but not in B}
***************************************************************************************
int main()
{
clock_t before;
clock_t after;
double result;
int i;
int n;
int sample[MaxElements];
cout << "Enter size of set: ";
cin >> n;
if (n >= MaxElements)
{
cout << "set size must be less than " << MaxElements << " ";
exit(1);
}
generateSample(sample, n);
before = clock();
for(i=0; i<100; i++)
{
run(sample, n);
}
after = clock();
result = static_cast<double>(after - before)/CLOCKS_PER_SEC;
result = static_cast<double>(after - before)/CLOCKS_PER_SEC;
cout << before << " " << after << " ";
cout << result << " ";
~ ~ ~ ~ ~ ~
return 0;
}
generateSample: Generate a set of value of a certain size. Produce an array that is used to initialize the sets in our experiment.
void generteSample (int sample[], int n)
{
int i;
int r;
Set s;
i=0;
while (i < n)
{
r = rand() %10000;
if(!s.isMember(r))
{
sample[i] = r;
i++;
}
}
}
Explanation / Answer
Here is the partly implemented methods for you:
#include <iostream>
#define MaxElements 20
using namespace std;
class Set {
public:
//default constructor
Set();
//add element to set
void addElement (int element);
//remove element from set
void removeElement(int element);
//check for membership
bool isMember(int element);
//set union, modifies curremtn set
void Union (Set s);
//set difference modifiers current set
void difference (Set s);
//size of set
int size();
//get element i
int getElement (int i);
private:
//binary search for element, returns index
bool search(int element, int& index);
//set members
int elements[MaxElements];
//next empty position in elements
int next;
};
void printSet(Set s);
void generateSample(int sample[], int n);
void run(int sample[], int n);
//Overload the following operators the class Set:
/* bool opertor ==(const Set& s); //equality comparison
bool oprator !=(const Set& s); //inequality comparion
Set& operator + (int element); //add element operator
Set& operator + (const Set& s); // set union opreator
Set& operator - (int element); //remove element operator
Set& operator - (const Set& s); //aset difference operator
*/
/****************************************************************************************
Set data structure:
1. A set is a collection of objects need not to be in any particular order. Elements
* should not be repeated.
2. UNION: Combine two or more sets (here two sets)
3. INTERSECTION: Gathering common elements in both the sets together as a single set
4. DIFFERENCE: Forming a set with elements which are in first set and not in second
set
A-B= {x| for all x belongs to A but not in B}
***************************************************************************************/
int main()
{
clock_t before;
clock_t after;
double result;
int i;
int n;
int sample[MaxElements];
cout << "Enter size of set: ";
cin >> n;
if (n >= MaxElements)
{
cout << "set size must be less than " << MaxElements << " ";
exit(1);
}
generateSample(sample, n);
before = clock();
for(i=0; i<100; i++)
{
run(sample, n);
}
after = clock();
result = static_cast<double>(after - before)/CLOCKS_PER_SEC;
result = static_cast<double>(after - before)/CLOCKS_PER_SEC;
cout << before << " " << after << " ";
cout << result << " ";
//~ ~ ~ ~ ~ ~
return 0;
}
//generateSample: Generate a set of value of a certain size. Produce an array that is used to initialize the sets in our experiment.
void generateSample (int sample[], int n)
{
int i;
int r;
Set s;
i=0;
while (i < n)
{
r = rand() %10000;
if(!s.isMember(r))
{
sample[i] = r;
i++;
}
}
}
void run(int sample[], int n)
{
for(int i = 0; i < n; i++)
cout<<sample[i]<<" ";
cout<<endl;
}
//default constructor
Set::Set()
{
next = 0;
}
//add element to set
void Set::addElement (int element)
{
bool found = false;
for(int i = 0; i < next; i++)
if(elements[i] == element)
{
found = true;
break;
}
if(!found)
{
elements[next] = element;
next++;
}
}
//remove element from set
void Set::removeElement(int element)
{
for(int i = 0; i < next; i++)
if(elements[i] == element)
{
for(int j = i; j < next-1; j++)
elements[j] = elements[j+1];
next--;
}
}
//check for membership
bool Set::isMember(int element)
{
for(int i = 0; i < next; i++)
if(elements[i] == element)
return true;
return false;
}
//set union, modifies curremtn set
void Set::Union (Set s)
{
for(int i = 0; i < s.size(); i++)
{
if(isMember(s.getElement(i)))
continue;
addElement(s.getElement(i));
}
}
//set difference modifiers current set
void Set::difference (Set s)
{
for(int i = 0; i < s.size(); i++)
{
if(isMember(s.getElement(i)))
removeElement(s.getElement(i));
}
}
//size of set
int Set::size()
{
return next;
}
//get element i
int Set::getElement (int i)
{
if(i < next)
return elements[i];
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.