Zbiór (ang. set) składa się z elementów (dokładnej definicji nie podamy, bo nie jest nam potrzebna). Elementy mogą być liczbami lub dowolnymi innymi obiektami, które da się reprezentować za pomocą bitów w komputerze (znaki, teksty, obrazki, filmy, struktury…). My zajmiemy się głównie zbiorami liczbowymi, ponieważ inne zbiory da się łatwo odwzorować na zbiory liczbowe (np. nadając elementom numer zwany kluczem).

Zbiór pusty (ang. empty set) to zbiór, który nie zawiera żadnego elementu. Oznaczamy go symbolem Ø.

Zbiór skończony (ang. finite set) to zbiór, który zawiera skończoną liczbę elementów. Np. zbiorem skończonym jest zbiór liczb {1 2 3 }.

Zbiór nieskończony (ang. infinite set), to zbór, który nie jest skończony, czyli zawiera nieskończoną liczbę elementów. Zbiorami nieskończonymi są przykładowo zbiory liczb naturalnych, wymiernych, rzeczywistych, pierwszych, itp.

Przestrzeń (ang. space) jest zbiorem, który zawiera wszystkie możliwe elementy zbiorów. Na przykład umawiamy się, że nasze zbiory mogą zawierać liczby od 0 do 99. Zatem przestrzenią dla tych zbiorów będzie zbiór, który zawiera elementy {0, 1, 2, …, 98, 99}.

Podzbiór (ang. subset) jest zbiorem, który zawiera się w innym zbiorze. Mówimy, że zbiór A jest podzbiorem zbioru B, jeśli wszystkie elementy zbioru A są również elementami zbioru B. Relację tę zapisujemy matematycznie jako:

Mówimy, że zbiór A nie jest podzbiorem zbioru B, jeśli żaden element zbioru A nie jest elementem zbioru B. Zapisujemy to jako:

Dwa zbiory są równe, jeśli są nawzajem swoimi podzbiorami, czyli:

Zbiór pusty jest podzbiorem każdego zbioru:

Zapis:

oznacza, że element x należy do zbioru A (czyli jest w  zbiorze A).

Zapis:

oznacza, że element x nie należy do zbioru A (czyli nie ma go w zbiorze A).

Liczbę elementów zbioru A oznaczamy jako |A| i nazywamy mocą zbioru.

Sumą (ang. union) zbiorów A i B jest zbiór C, którego elementami są wszystkie elementy zbioru A i wszystkie elementy zbioru B (czyli każdy element zbioru A jest elementem zbioru C, każdy element zbioru B jest elementem zbioru C, każdy element zbioru C jest elementem zbioru A lub jest elementem zbioru B):

Iloczynem (ang. intersection) zbiorów A i B jest zbiór C, którego wszystkie elementy należą jednocześnie do zbioru A i do zbioru B:

Różnicą (ang. difference) zbiorów A i B jest zbiór C, którego wszystkie elementy należą do zbioru A, lecz żaden nie należy do zbioru B:

Dopełnienie (ang. complement) zbioru A do przestrzeni U jest zbiorem A' wszystkich możliwych elementów, których nie zawiera zbiór A:

Aby korzystać ze zbiorów tworzonych programach, musimy posiadać odpowiednią strukturę danych. Struktura ta powinna udostępniać następujący zestaw operacji (na początku nazw operacji dodaliśmy s_, aby uniknąć konfliktów nazw):

s_create(n)

s_union(A, B)

s_intersection(A, B)

s_difference(A, B)

s_complement(A)

s_subset(A, B)

s_empty(A)

s_size(A)

s_add(A, x)

s_remove(A, x)

s_isin(A, x)

s_clear(A)

Zbiór można zaimplementować w różnych strukturach danych. Najczęściej są to listy, tablice, mapy bitowe lub drzewa poszukiwań binarnych. Wybór odpowiedniej struktury ma na celu optymalizację powyższych operacji. W kolejnych artykułach przedstawiamy proste implementacje zbiorów w tych strukturach danych.