Graphs and Set ADT's - UGH!
I'm in a class where we have to make a lab that does the following with a set ADT:
bool isEmpty()
int Size()
void Store(int item)
// Places the item in the set. Does not allow duplicates
void Delete (int item)
// Finds the item and if it exists
bool Exists(int item)
// returns true if the item exists
void Union(Set &otherSet, Set &union)
// Post Condition: “union” contains the items that are in either
// “this” set or “otherSet”.
void Intersection(Set &otherSet, Set &intersection)
// Post Condition: “intersection contains the items that are in both
// “this” set and “otherSet”
void Difference(Set &otherSet, Set &difference)
// Post Condition: “difference” contains the items in “this” set but
// not in “otherSet”.
void FillQueue(Queue &q )
// Post Condition: fills the queue with each item in the set so it can
// be traversed (sort of like an iterator)
We're not suppose to use 2 - Dimensional arrays. So what is the best data structure for this? Array? Linked List? Some sort of tree? I want to go with array, but can't decide.
Also, I have no idea what some difference, intersection, and union are doing. I need major help.
Thanks in advance.
bool isEmpty()
int Size()
void Store(int item)
// Places the item in the set. Does not allow duplicates
void Delete (int item)
// Finds the item and if it exists
bool Exists(int item)
// returns true if the item exists
void Union(Set &otherSet, Set &union)
// Post Condition: “union” contains the items that are in either
// “this” set or “otherSet”.
void Intersection(Set &otherSet, Set &intersection)
// Post Condition: “intersection contains the items that are in both
// “this” set and “otherSet”
void Difference(Set &otherSet, Set &difference)
// Post Condition: “difference” contains the items in “this” set but
// not in “otherSet”.
void FillQueue(Queue &q )
// Post Condition: fills the queue with each item in the set so it can
// be traversed (sort of like an iterator)
We're not suppose to use 2 - Dimensional arrays. So what is the best data structure for this? Array? Linked List? Some sort of tree? I want to go with array, but can't decide.
Also, I have no idea what some difference, intersection, and union are doing. I need major help.
Thanks in advance.
Ironically the STL already gives you the set<> template class which provides
some of the functions and several algorithms that provide the rest. set<> uses
a red-black tree (rb_tree) as its underlying container in order to meet the
complexity requirements defined by the C++ standard (mostly runtime efficiency
of operations like insert, find, remove).
The best data structure for you to use is one in which finds are fast, because
sets are usually used for faster lookups (as compared to vectors, lists, etc,
which require linear time).
Having said that, if you use an array or a linked list, you will require linear
time to find elements. If you use a tree, it will be logN. Therefore, of the
data structures you mentioned, tree is the best.
set difference: The difference of two sets S1 and S2 is the set containing those
elements in S1 that are not in S2. Note that set_difference( S1, S2 ) is not the
same as set_difference( S2, S1 ). (ie, think of it as integer subtraction:
A - B != B - A (unless A == B, in which case the same relation holds for sets).)
set intersection: The intersection of two sets S1 and S2 is the set containing
those elements that are in both S1 and S2. Note that set_intersection( S1, S2 )
is the same as set_intersection( S2, S1). (ie, think of it as a logical "and" of
the two sets, where we know that A and B == B and A, ie associative).
set union: The union of two sets S1 and S2 is the set containing all elements
from S1 and all elements from S2, without duplicates. For example, given
S1 = { 1, 2, 3, 5 } and S2 = { 0, 1, 2, 4 }, then S1 u S2 = { 0, 1, 2, 3, 4, 5 }.
One can also relate set unions in terms of intersections and differences. The
following formula holds, given two sets S1 and S2:
Union( S1, S2 ) = Difference( S1, S2 ) + Intersection( S1, S2 ) + Difference( S2, S1 )
where the "+" operator simply means to concatenate the sets.
some of the functions and several algorithms that provide the rest. set<> uses
a red-black tree (rb_tree) as its underlying container in order to meet the
complexity requirements defined by the C++ standard (mostly runtime efficiency
of operations like insert, find, remove).
The best data structure for you to use is one in which finds are fast, because
sets are usually used for faster lookups (as compared to vectors, lists, etc,
which require linear time).
Having said that, if you use an array or a linked list, you will require linear
time to find elements. If you use a tree, it will be logN. Therefore, of the
data structures you mentioned, tree is the best.
set difference: The difference of two sets S1 and S2 is the set containing those
elements in S1 that are not in S2. Note that set_difference( S1, S2 ) is not the
same as set_difference( S2, S1 ). (ie, think of it as integer subtraction:
A - B != B - A (unless A == B, in which case the same relation holds for sets).)
set intersection: The intersection of two sets S1 and S2 is the set containing
those elements that are in both S1 and S2. Note that set_intersection( S1, S2 )
is the same as set_intersection( S2, S1). (ie, think of it as a logical "and" of
the two sets, where we know that A and B == B and A, ie associative).
set union: The union of two sets S1 and S2 is the set containing all elements
from S1 and all elements from S2, without duplicates. For example, given
S1 = { 1, 2, 3, 5 } and S2 = { 0, 1, 2, 4 }, then S1 u S2 = { 0, 1, 2, 3, 4, 5 }.
One can also relate set unions in terms of intersections and differences. The
following formula holds, given two sets S1 and S2:
Union( S1, S2 ) = Difference( S1, S2 ) + Intersection( S1, S2 ) + Difference( S2, S1 )
where the "+" operator simply means to concatenate the sets.
Topic archived. No new replies allowed.