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;