
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


 
A$	= "apple cherry elderberry grape" 
B$	= "banana cherry date elderberry fig"
C$	= "apple cherry elderberry grape orange"
D$	= "apple cherry elderberry grape"
E$	= "apple cherry elderberry"
M$	= "banana"
 
print "A = ";A$
print "B = ";B$
print "C = ";C$
print "D = ";D$
print "E = ";E$
print "M = ";M$
 
if instr(A$,M$) = 0 then a$ = "not "
print "M is ";a$; "an element of Set A"
a$ = ""
if instr(B$,M$) = 0 then a$ = "not "
print "M is ";a$; "an element of Set B"
 
un$ = A$ + " "
for i = 1 to 5
 if instr(un$,word$(B$,i)) = 0 then un$ = un$ + word$(B$,i) + " "
next i
print "union(A,B) = ";un$
 
for i = 1 to 5
 if instr(A$,word$(B$,i)) <> 0 then ins$ = ins$ + word$(B$,i) + " "
next i
print "Intersection(A,B) = ";ins$
 
for i = 1 to 5
 if instr(B$,word$(A$,i)) = 0 then dif$ = dif$ + word$(A$,i) + " "
next i
print "Difference(A,B) = ";dif$
 
a = subs(A$,B$,"AB") 
a = subs(A$,C$,"AC")
a = subs(A$,D$,"AD")
a = subs(A$,E$,"AE")
 
a = eqs(A$,B$,"AB") 
a = eqs(A$,C$,"AC")
a = eqs(A$,D$,"AD")
a = eqs(A$,E$,"AE")
end
 
function subs(a$,b$,sets$)
 for i = 1 to 5
   if instr(b$,word$(a$,i)) <> 0 then subs = subs + 1
 next i
if subs = 4 then 
  print left$(sets$,1);" is a subset of ";right$(sets$,1)
else
  print left$(sets$,1);" is not a subset of ";right$(sets$,1)
end if
end function
 
function eqs(a$,b$,sets$)
for i = 1 to 5
 if word$(a$,i) <> "" then a = a + 1
 if word$(b$,i) <> "" then b = b + 1
 if instr(b$,word$(a$,i)) <> 0 then c = c + 1
next i
if (a = b) and (a = c) then 
  print left$(sets$,1);" is equal ";right$(sets$,1)
else
  print left$(sets$,1);" is not equal ";right$(sets$,1)
end if
end function