
Data Structure

This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
A   set  is a collection of elements, without duplicates and without order.



Task

Show each of these set operations:

 Set creation
 Test m ∈ S -- "m is an element in set S"
 A ∪ B -- union; a set of all elements either in set A or in set B.
 A ∩ B -- intersection; a set of all elements in both set A and set B.
 A ∖ B -- difference; a set of all elements in set A, except those in set B.
 A ⊆ B -- subset; true if every element in set A is also in set B.
 A = B -- equality; true if every element of set A is in set B and vice versa.


As an option, show some other set operations.

(If A ⊆ B, but A ≠ B, then A is called a true or proper subset of B, written A ⊂ B or A ⊊ B.)

As another option, show how to modify a mutable set.



One might implement a set using an associative array (with set elements as array keys and some dummy value as the values).

One might also implement a set with a binary search tree, or with a hash table, or with an ordered array of binary bits (operated on with bit-wise binary operators).

The basic test, m ∈ S, is O(n) with a sequential list of elements, O(log n) with a balanced binary search tree, or (O(1) average-case, O(n) worst case) with a hash table.



See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


 
# Project : Set
 
arr = ["apple", "banana", "cherry", "date", "elderberry", "fig", "grape"]
for n = 1 to 25
     add(arr,"")
next 
seta = "1010101"
see "Set A: " + arrset(arr,seta) + nl
setb = "0111110"
see "Set B: " + arrset(arr,setb) + nl
elementm = "0000010"
see "Element M: " + arrset(arr,elementm) + nl
 
temp = arrsetinsec(elementm,seta)
if len(temp) > 0 
   see "M is an element of set A" + nl
else
   see "M is not an element of set A" + nl
ok
temp = arrsetinsec(elementm,setb)
if len(temp) > 0 
   see "M is an element of set B" + nl
else
   see "M is not an element of set B" + nl
ok
 
see "The union of A and B is: " 
see arrsetunion(seta,setb) + nl
see "The intersection of A and B is: "
see  arrsetinsec(seta,setb) + nl
see "The difference of A and B is: " 
see arrsetnot(seta,setb) + nl
 
flag = arrsetsub(seta,setb)
if flag = 1 
   see "Set A is a subset of set B" + nl
else
   see "Set A is not a subset of set B" + nl
ok
if seta = setb
   see "Set A is equal to set B" + nl
else
   see "Set A is not equal to set B" + nl
ok
 
func arrset(arr,set)
       o = ""
       for i = 1 to 7
            if set[i] = "1"
                o = o + arr[i] + ", "
            ok
       next
       return left(o,len(o)-2)
 
func arrsetunion(seta,setb)
       o = ""
       union = list(len(seta))
       for n = 1 to len(seta)
            if seta[n] = "1" or setb[n] = "1"
               union[n] = "1"
            else
               union[n] = "0"
            ok
       next
       for i = 1 to len(union)
            if union[i] = "1"
                o = o + arr[i] + ", "
            ok
       next
       return o
 
func arrsetinsec(setc,setd)
       o = ""
       union = list(len(setc))
       for n = 1 to len(setc)
            if setc[n] = "1" and setd[n] = "1"
               union[n] = "1"
            else
               union[n] = "0"
            ok
       next
       for i = 1 to len(union)
            if union[i] = "1"
                o = o + arr[i] + ", "
            ok
       next
       return o
 
func arrsetnot(seta,setb)
       o = ""
       union = list(len(seta))
       for n = 1 to len(seta)
            if seta[n] = "1" and setb[n] = "0"
               union[n] = "1"
            else
               union[n] = "0"
            ok
       next
       for i = 1 to len(union)
            if union[i] = "1"
                o = o + arr[i] + ", "
            ok
       next
       return o
 
func arrsetsub(setc,setd)
       flag = 1
       for n = 1 to len(setc)
            if setc[n] = "1" and setd[n] = "0"
               flag = 0
            ok
       next
       return flag
 