CS 201 - 11/11/14
Sets as a data structure
- could store in a dynamic array, linked list,
or in a hash table.
most often an application using sets needs multiple
set to be maintained.
a data item may need to know to which set it belongs.
to complicate matters, a data item may belong to
multiple sets
when two sets overlap, what is the best way to
represent that data?
A single data item may exist multiple times in
our "set space".
We may implement, a list of sets that each item
is a member of.
Each set normally allows the following operations
- isEmpty()
- add()
- remove()
- isMemberOf()
- access()
- update() ??? more an operation on the data item
and not on the set itself
- clear()
- listAll()
What operations might be performs on the entire set
or on multiple sets?
- union()
- intersection()
- setDifference()
- inverseOfASet()
- isSubSetOf()
- isSupersetOf()
Set intersection (Set a, Set b)
{
Set c;
clear (c);
forAll ( dataItem in a)
if ( memberOf( dataItem, b) == true)
add (dataItem, c);
return c;
}
The "Set" would be made up of multiple dataItems
of the same "type"
Sometimes we may need to implement a "partial set"
- particularly when we are working with
infinite sets (i.e. set of prime numbers)
- while partial may contain a list of data
items, they may also contain functions
that calculate a memberOf operation.
---------------------------------------------
Let us assume we have a linked list structure
that maintains a single list of data items.
struct Node
{
int data;
/* other data items */
struct Node* next;
}
A pointer to struct Node would be the head of the
list of data items, i.e:
struct Node* head;
How do we create a collection of lists?
- each list needs to be identifiable
We can create a linked list of "identifiable header
pointers"
struct SetData
{
char name[40];
struct Node* head;
struct SetData* nextSD;
};
typedef structSetData sdtype;
int main()
{
sdtype* setLists;