Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2026 mgr Jerzy Wałaszek

Reprezentacja zbiorów w tablicach

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Implementacja zbioru w tablicy dynamicznej

Zbiory można reprezentować zwykłą tablicą dynamiczną. Wymaga to jednak pewnych ustaleń.

Elementy są liczbami całkowitymi wypełniającymi spójnie przedział od vmin do vmax.

Na przykład dla vmin = -3 i vmax = 4 otrzymujemy następujące możliwe elementy: -3 -2 -1 0 1 2 3 4.

Tablica posiada tyle komórek, ile jest możliwych wartości w przedziale od vmin do vmax, czyli:

długość tablicy = vmax-vmin+1

W naszym przykładzie tablica musi posiadać 4-(-3)+1 = 8 komórek.

Elementy są reprezentowane w tablicy przez indeksy komórek. Ponieważ indeksy zaczynają się od wartości 0, musimy posiadać wzory przeliczeniowe pomiędzy wartością elementu v a indeksem komórki, która go reprezentuje:

indeks = v-vmin
v = indeks+vmin

Komórki tablicy przechowują informację o tym, czy dany element jest lub nie jest elementem zbioru reprezentowanego przez tablicę. Wystarczy, aby komórki były jednobajtowe. Umawiamy się, że wartość 0 oznacza brak elementu, a wartość 1 oznacza, że element jest w zbiorze.

Zbiór zawierający elementy -3 -2 1 i 4 będzie reprezentowany w naszym przykładzie następującą tablicą:

indeks zawartość element
0 1 -3
1 1 -2
2 0 -1
3 0 0
4 1 1
5 0 2
6 0 3
7 1 4

Implementacja zbiorów w tablicach dynamicznych jest opłacalna wtedy, gdy zakres wartości elementów jest względnie mały i spójny.

Zbiór jest zawsze reprezentowany przez strukturę Set zawierającą trzy pola:

vmin : dolna granica wartości elementów.
nmax : ostatni indeks komórki tablicy.
T : tablica elementów jednobajtowych o rozmiarze nmax+1.
Pascal
type
  Set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of byte;
  end;
C++
struct Set
{
  int vmin, nmax;
  char * T;
};
Basic
Type Set
  vmin As Integer
  nmax As Integer
  T As Byte Ptr
End Type
Python (dodatek) 
class Set:


    def __init__(self)
        self.vmin = 0
        self.nmax = 0
        self.t = []

Algorytmy operacji dla zbiorów reprezentowanych tablicami dynamicznymi

s_clear(A) – usuwa wszystkie elementy ze zbioru A. Zbiór A staje się zbiorem pustym.

Algorytm wypełnia tablicę A→T zerami, co w efekcie tworzy pusty zbiór.

Wejście:

A : referencja do struktury Set

Wyjście:

Pusty zbiór A

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax: ; zerujemy komórki tablicy
     wykonuj: A→T[i] ← 0
K02: Zakończ

s_create(A, vmin, vmax) – tworzy pusty zbiór A o odpowiednim rozmiarze

Algorytm wypełnia strukturę zbioru A, tworzy tablicę dynamiczną o wyliczonym rozmiarze vmax-vmin+1 i wypełnia ją zerami, co daje w efekcie pusty zbiór A.

Wejście:

A : referencja do struktury Set.
vmin : minimalna wartość elementu zbioru.
vmax : maksymalna wartość elementu zbioru.

Wyjście:

Pusty zbiór A.

Elementy pomocnicze:

s_clear(Z) : usuwa ze zbioru Z wszystkie elementy.

Lista kroków:

K01: Jeśli A→nmax > 0,
     to usuń tablicę A→T z pamięci
K02: A→vmin ← vmin ; wypełniamy strukturę Set
                   ; odpowiednimi wartościami
K03: A→nmax ← vmax-vmin ; wyznaczamy ostatni indeks
K04: Utwórz obszar dla A→nmax+1 komórek ; tworzymy tablicę dynamiczną
K05: A→T ← adres utworzonego obszaru
K06: s_clear(A) ; zerujemy komórki tablicy
K07: Zakończ

s_union(A, B, C) – zwraca sumę zbiorów A i B

Algorytm wykonuje bitową operację alternatywy na poszczególnych elementach tablic T zbiorów A i B, a wynik umieszcza w tablicy T zbioru C. Wszystkie trzy zbiory muszą posiadać ten sam zakres elementów.

Wejście:

A, B, C : referencja do struktur Set.

Wyjście:

Zbiór C zawiera sumę zbiorów A i B.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax,
     wykonuj: C→T[i] = suma bitowa A→T[i]
                       oraz B→T[i]
K02: Zakończ

s_intersection(A, B, C) – zwraca iloczyn zbiorów A i B

Algorytm wykonuje bitową operację koniunkcji na poszczególnych elementach tablic T zbiorów A i B, a wynik umieszcza w tablicy T zbioru C. Wszystkie trzy zbiory muszą posiadać ten sam zakres elementów.

Wejście:

A, B, C : referencja do struktur Set.

Wyjście:

Zbiór C zawiera iloczyn zbiorów A i B.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax:
     wykonuj: C→T[i] = iloczyn bitowy A→T[i]
                       oraz B→T[i]
K02: Zakończ

s_difference(A, B, C) – zwraca różnicę zbioru A i B

Algorytm wykonuje bitową operację koniunkcji z negacją na poszczególnych elementach tablic T zbiorów A i B, a wynik umieszcza w tablicy T zbioru C. Wszystkie trzy zbiory muszą posiadać ten sam zakres elementów.

Wejście:

A, B, C : referencja do struktur Set.

Wyjście:

Zbiór C zawiera różnicę zbiorów A i B.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax :
     wykonuj: C→T[i] = iloczyn bitowy A→T[i]
                         oraz negacji B→T[i]
K02: Zakończ

s_complement(A, C) – zwraca dopełnienie zbioru A

Algorytm wykonuje bitową operację negacji bitu 0 w poszczególnych elementach tablicy T zbioru A, a wynik umieszcza w tablicy T zbioru C. Oba zbiory muszą posiadać ten sam zakres elementów.

Wejście:

A, C : referencja do struktur Set.

Wyjście:

Zbiór C zawiera dopełnienie zbioru A.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax:
     wykonuj: C→T[i] = negacja bitu nr 0 w A→T[i]
K02: Zakończ

s_subset(A, B) – zwraca true, jeśli zbiór A jest podzbiorem zbioru B, inaczej zwraca false.

Algorytm przegląda tablicę A→T i dla komórek o wartości 1 sprawdza, czy odpowiadające im komórki B→T mają również wartość 1. Jeśli nie, to zbiór A nie jest podzbiorem B. W przeciwnym razie zbiór A jest podzbiorem B. Oba zbiory muszą posiadać ten sam zakres elementów.

Wejście:

A, B : referencja do struktur Set.

Wyjście:

true : zbiór A jest podzbiorem zbioru B.
false : zbiór A nie jest podzbiorem zbioru B.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax:
     wykonuj K02
K02:  Jeśli A→T[i] = 1 obrazek B→T[i] = 0, 
      to zakończ z wynikiem false
K03: Zakończ z wynikiem true

s_size(A) – zwraca liczbę elementów zawartych w zbiorze A

Algorytm sumuje poszczególne komórki tablicy A→T i zwraca tę sumę jako wynik. Ponieważ komórki przechowują tylko wartości 0 lub 1, to ich suma daje bezpośrednio liczbę elementów w zbiorze.

Wejście:

A : referencja do struktury Set.

Wyjście:

Liczba elementów w A.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.
s : suma komórek, s ∈ C.

Lista kroków:

K01: s ← 0 ; zerujemy sumę
K02: Dla i = 0, 1, …, A→nmax, ; sumujemy komórki
     wykonuj: s ← s+A→T[i]
K03: Zakończ z wynikiem s

s_empty(A) – zwraca true, jeśli zbiór A jest pusty, inaczej zwraca false

Algorytm oblicza liczbę elementów w zbiorze A. Jeśli jest równa zero, zwraca true, inaczej zwraca false.

Wejście:

A : referencja do struktury Set.

Wyjście:

true : zbiór A jest pusty.
false : zbiór A nie jest pusty.

Elementy pomocnicze:

s_size(Z) : zwraca liczbę elementów w zbiorze Z.

Lista kroków:

K01: Jeśli s_size(A) = 0, 
     to zakończ z wynikiem true
K02: Zakończ z wynikiem false

s_add(A, x) – dodaje element x do zbioru A.

Dodanie elementu do zbioru polega na ustawieniu na 1 reprezentującej go komórki w tablicy A→T.

Wejście:

A : referencja do struktury Set.
x : element do dodania do zbioru, x ∈ C.

Wyjście:

Zbiór A z dodanym elementem x.

Lista kroków:

K01: A→T[x-A→vmin] ← 1 ; komórkę reprezentującą element ustawiamy na 1
K02: Zakończ

s_remove(A, x) – usuwa element x ze zbioru A

Usunięcie elementu ze zbioru polega na ustawieniu na 0 reprezentującej go komórki w tablicy T.

Wejście:

A : referencja do struktury Set.
x : element do usunięcia ze zbioru, x ∈ C.

Wyjście:

Zbiór A z usuniętym elementem x.

Lista kroków:

K01: A→T[x-A→vmin] ← 0 ; komórkę reprezentującą element ustawiamy na 0
K02: Zakończ

s_isin(A, x) – zwraca true, jeśli element x jest w zbiorze A, inaczej zwraca false

Algorytm zwraca stan komórki tablicy, która odwzorowuje element x w zbiorze A.

Wejście:

A : referencja do struktury Set.
x : sprawdzany element, x ∈ C.

Wyjście:

true : element o wartości x jest w zbiorze A.
false : elementu o wartości x nie ma w zbiorze A.

Lista kroków:

K01: Jeśli A→T[x-A→vmin] = 1, ; sprawdzamy obecność elementu
     to zakończ z wynikiem true
K02: Zakończ z wynikiem false

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.
Program testuje wszystkie funkcje obsługi zbiorów opartych na tablicach dynamicznych. Wyjaśnienia wykonywanych operacji znajdują się w komentarzach wewnątrz programu.
Pascal
// Zbiory zaimplementowane
// w tablicach dynamicznych
// Data: 21.06.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program sets;

// Definicja struktury zbioru
type
  Set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of byte;
  end;

// Procedura usuwa wszystkie
// elementy ze zbioru
//--------------------------
procedure s_clear(var A : Set);
var
  i : integer;
begin
  for i := 0 to A.nmax do
    A.T[i] := 0; // Zerujemy tablicę
end;

// Procedura tworzy pusty zbiór
//-----------------------------
procedure s_create(var A : Set;
              vmin, vmax : integer);
begin
  // Wypełniamy strukturę A
  A.vmin := vmin;
  A.nmax := vmax-vmin;
  // Tworzymy tablicę dynamiczną na elementy
  SetLength(A.T, A.nmax+1);
  // Zbiór zerujemy
  s_clear(A);
end;

// Procedura oblicza sumę
// zbiorów A i B.
// Wynik umieszcza w zbiorze C
//----------------------------
procedure s_union(var A, B, C : Set);
var
  i : integer;
begin
  for i := 0 to A.nmax do
    C.T[i] := A.T[i] or B.T[i];
end;

// Procedura oblicza iloczyn
// zbiorów A i B.
// Wynik umieszcza w zbiorze C
//----------------------------
procedure s_intersection(var A, B, C : Set);
var
  i : integer;
begin
  for i := 0 to A.nmax do
    C.T[i] := A.T[i] and B.T[i];
end;

// Procedura oblicza różnicę
// zbiorów A i B.
// Wynik umieszcza w zbiorze C
//----------------------------
procedure s_difference(var A, B, C : Set);
var
  i : integer;
begin
  for i := 0 to A.nmax do
    C.T[i] := A.T[i] and not B.T[i];
end;

// Procedura oblicza dopełnienie
// zbioru A.
// Wynik umieszcza w zbiorze C
//------------------------------
procedure s_complement(var A, C : Set);
var
  i : integer;
begin
  for i := 0 to A.nmax do
    C.T[i] := 1 and not A.T[i];
end;

// Funkcja sprawdza, czy
// zbiór A jest podzbiorem zbioru B.
// true  - tak
// false - nie
//----------------------------------
function s_subset(var A, B : Set)
                           : boolean;
var
  i : integer;
begin
  for i := 0 to A.nmax do
    if(A.T[i] = 1) and (B.T[i] = 0) then
      Exit(false);
  s_subset := true;
end;

// Funkcja oblicza liczbę elementów
// w zbiorze A
//---------------------------------
function s_size(var A : Set)
                      : integer;
var
  i, s : integer;
begin
  // Zerujemy sumę
  s := 0;
  for i := 0 to A.nmax do
    // Sumujemy komórki
    s := s+A.T[i];
  s_size := s;
end;

// Funkcja sprawdza, czy
// zbiór jest pusty.
// true  - tak, zbiór jest pusty
// false - nie, zbiór nie jest pusty
//----------------------------------
function s_empty(var A : Set)
                       : boolean;
begin
  s_empty := s_size(A) = 0;
end;

// Procedura dodaje do zbioru element
//-----------------------------------
procedure s_add(var A : Set;
                    x : integer);
begin
  A.T[x-A.vmin] := 1;
end;

// Procedura usuwa ze zbioru element
//----------------------------------
procedure s_remove(var A : Set;
                       x : integer);
begin
  A.T[x-A.vmin] := 0;
end;

// Funkcja bada obecność
// elementu w zbiorze.
// true  - element jest w zbiorze
// false - elementu nie ma w zbiorze
//----------------------------------
function s_isin(var A : Set;
                    x : integer)
                      : boolean;
begin
  s_isin := A.T[x-A.vmin]=1;
end;

// Procedura wyświetla zawartość zbioru
//-------------------------------------
procedure s_print(var A : Set);
var
   i : integer;
begin
  for i := 0 to A.nmax do
    if A.T[i] = 1 then
      write(i+A.vmin:3);
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  A, B, C : Set;
  i, x    : integer;

begin
  randomize;
  // Inicjujemy zmienne dla kompilatora
  A.nmax := 0;
  B.nmax := 0;
  C.nmax := 0;
  // Tworzymy puste zbiory o zakresie
  // elementów od -5 do 20
  s_create(A, -5, 20);
  s_create(B, -5, 20);
  s_create(C, -5, 20);
  // Do zbioru A dodajemy 10 losowych elementów
  for i := 1 to 10 do
    s_add(A, -5+random(26));
  // Do zbioru B dodajemy 25 losowych elementów
  for i := 1 to 25 do
    s_add(B, -5+random(26));
  // Wyświetlamy je
  write('A =');
  s_print(A);
  writeln;
  writeln('SIZE OF A IS ', s_size(A));
  writeln;
  write('B =');
  s_print (B);
  writeln;
  writeln('SIZE OF B IS ', s_size(B));
  // Suma zbiorów
  writeln;
  write('UNION OF A AND B IS');
  s_union(A, B, C);
  s_print(C);
  writeln;
  writeln('SIZE OF UNION IS ', s_size(c));
  // Iloczyn zbiorów
  writeln;
  write('INTERSECTION OF A AND B IS');
  s_intersection(A, B, C);
  s_print(C);
  writeln;
  writeln('SIZE OF INTERSECTION IS ', s_size(C));
  // Różnica zbiorów
  writeln;
  write('DIFFERENCE OF A AND B IS');
  s_difference(A, B, C);
  s_print(C);
  writeln;
  writeln('SIZE OF DIFFERENCE IS ', s_size(C));
  // Dopełnienie zbioru
  writeln;
  write ('COMPLEMENT OF A IS');
  s_complement(A, C);
  s_print(C);
  writeln;
  writeln('SIZE OF COMPLEMENT IS ', s_size(C));
  // Podzbiór
  // Kopiujemy A do C
  s_union (A, A, C);
  // Usuwamy 7 elementów
  for i := 1 to 7 do
    s_remove(C, -5+random(26));
  writeln;
  write('IS');
  s_print(C);
  writeln(' SUBSET OF A?');
  writeln(s_subset(C, A));
  s_complement(B, C);
  // Usuwamy 12 elementów
  for i := 1 to 12 do
    s_remove(C, -5+random(26));
  writeln;
  write('IS');
  s_print(C);
  writeln(' SUBSET OF A?');
  writeln(s_subset(C, A));
  // Usuwanie
  writeln;
  write('FROM A WE REMOVE');
  for i := 1 to 5 do
  begin
    x := -5+random(26);
    write(x:3);
    s_remove(A, x);
  end;
  writeln;
  write('A =');
  s_print(A);
  writeln;
  writeln('SIZE OF A IS ', s_size(A));
  writeln;
  // Sprawdzamy obecność wybranych
  // elementów w B
  for i := 1 to 10 do
  begin
    x := -5+random(26);
    write('IS ELEMENT', x:3, ' IN SET B? ');
    if s_isin(B, x) then
      writeln('YES')
    else
      writeln('NO');
  end;
  writeln;
  // Test na zbiór pusty
  writeln('IS SET A EMPTY?');
  writeln(s_empty(A));
  writeln;
  writeln('IS INTERSECTION OF A AND COMPLEMENT OF A EMPTY?');
  s_complement(A, C);
  s_intersection(A, C, C);
  writeln(s_empty(C));
  writeln;
  // Usuwamy tablice dynamiczne w zbiorach
  SetLength(A.T, 0);
  SetLength(B.T, 0);
  SetLength(C.T, 0);
end.
C++
// Zbiory zaimplementowane
// w tablicach dynamicznych
// Data: 21.06.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

// Definicja struktury zbioru
struct Set
{
    int vmin, nmax;
    char * T;
};

// Procedura usuwa wszystkie
// elementy ze zbioru
//--------------------------
void s_clear(Set & A)
{
  for(int i = 0; i <= A.nmax; i++)
    A.T[i] = 0; // Zerujemy tablicę
}

// Procedura tworzy pusty zbiór
//-----------------------------
void s_create(Set & A,
              int vmin,
              int vmax)
{
  // Wypełniamy strukturę A
  A.vmin = vmin;
  A.nmax = vmax-vmin;
  // Tworzymy tablicę dynamiczną
  // na elementy zbioru
  A.T = new char [A.nmax+1];
  s_clear(A); // Zbiór zerujemy
}

// Procedura oblicza sumę
// zbiorów A i B.
// Wynik umieszcza w zbiorze C
//----------------------------
void s_union(Set & A,
             Set & B,
             Set & C)
{
  for(int i = 0; i <= A.nmax; i++)
    C.T[i] = A.T[i] | B.T[i];
}

// Procedura oblicza iloczyn
// zbiorów A i B.
// Wynik umieszcza w zbiorze C
//----------------------------
void s_intersection(Set & A,
                    Set & B,
                    Set & C)
{
  for(int i = 0; i <= A.nmax; i++)
    C.T[i] = A.T[i] & B.T[i];
}

// Procedura oblicza różnicę
// zbiorów A i B.
// Wynik umieszcza w zbiorze C
//----------------------------
void s_difference(Set & A,
                  Set & B,
                  Set & C)
{
  for(int i = 0; i <= A.nmax; i++)
    C.T[i] = A.T[i] & ~ B.T[i];
}

// Procedura oblicza dopełnienie
// zbioru A.
// Wynik umieszcza w zbiorze C
//------------------------------
void s_complement(Set & A,
                  Set & C)
{
  for(int i = 0; i <= A.nmax; i++)
    C.T[i] = 1 & ~ A.T[i];
}

// Funkcja sprawdza, czy zbiór A
// jest podzbiorem zbioru B.
// true  - tak
// false - nie
//------------------------------
bool s_subset(Set & A,
              Set & B)
{
  for(int i = 0; i <= A.nmax; i++)
    if(A.T[i] && ! B.T[i]) return false;
  return true;
}

// Funkcja oblicza liczbę elementów
// w zbiorze A
//---------------------------------
int s_size(Set & A)
{
  int s = 0;

  for(int i = 0; i <= A.nmax; i++)
    s += A.T[i];
  return s;
}

// Funkcja sprawdza, czy zbiór jest pusty.
// true  - tak, zbiór jest pusty
// false - nie, zbiór nie jest pusty
//----------------------------------------
bool s_empty(Set & A)
{
  return ! s_size(A);
}

// Procedura dodaje do zbioru element
//-----------------------------------
void s_add(Set & A, int x)
{
  A.T[x-A.vmin] = 1;
}

// Procedura usuwa ze zbioru element
//----------------------------------
void s_remove(Set & A, int x)
{
  A.T[x-A.vmin] = 0;
}

// Funkcja bada obecność elementu w zbiorze.
// true  - element jest w zbiorze
// false - elementu nie ma w zbiorze
//------------------------------------------
bool s_isin(Set & A, int x)
{
  return A.T[x-A.vmin];
}

// Procedura wyświetla zawartość zbioru
//-------------------------------------
void s_print(Set & A)
{
  for(int i = 0; i <= A.nmax; i++)
    if(A.T[i]) cout << setw(3) << i+A.vmin;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  Set A, B, C;
  int i, x;

  srand(time(NULL));
  // Tworzymy puste zbiory o zakresie
  // elementów od -5 do 20
  s_create(A, -5, 20);
  s_create(B, -5, 20);
  s_create(C, -5, 20);
  // Do zbioru A dodajemy 10 losowych elementów
  for(i = 0; i < 10; i++)
    s_add(A, -5+(rand() % 26));
  // Do zbioru B dodajemy 25 losowych elementów
  for(i = 0; i < 25; i++)
    s_add(B, -5+(rand() % 26));
  // Wyświetlamy je
  cout << "A =";
  s_print(A);
  cout << endl
       << "SIZE OF A IS " << s_size(A)
       << endl << endl
       << "B =";
  s_print (B);
  cout << endl
       << "SIZE OF B IS " << s_size(B)
       << endl << endl
  // Suma zbiorów
       << "UNION OF A AND B IS";
  s_union(A, B, C); s_print(C);
  cout << endl
       << "SIZE OF UNION IS " << s_size(C)
       << endl << endl
  // Iloczyn zbiorów
       << "INTERSECTION OF A AND B IS";
  s_intersection(A, B, C); s_print(C);
  cout << endl
       << "SIZE OF INTERSECTION IS " << s_size(C)
       << endl << endl
  // Różnica zbiorów
       << "DIFFERENCE OF A AND B IS";
  s_difference(A, B, C); s_print(C);
  cout << endl
       << "SIZE OF DIFFERENCE IS " << s_size(C)
       << endl << endl
  // Dopełnienie zbioru
       << "COMPLEMENT OF A IS";
  s_complement(A, C); s_print(C);
  cout << endl
       << "SIZE OF COMPLEMENT IS " << s_size(C)
       << endl << endl;
  // Podzbiór
  // Kopiujemy A do C
  s_union (A, A, C);
  // Usuwamy 7 elementów
  for(i = 0; i < 7; i++)
    s_remove(C, -5+(rand() % 26));
  cout << "IS"; s_print(C);
  cout << " SUBSET OF A?" << endl;
  if(s_subset(C, A))
    cout << "YES";
  else
    cout << "NO";
  s_complement(B, C);
  // Usuwamy 12 elementów
  for(int i = 0; i < 12; i++)
    s_remove (C, -5+(rand() % 26));
  cout << endl << endl << "IS"; s_print(C);
  cout << " SUBSET OF A?" << endl;
  if(s_subset(C, A))
    cout << "YES";
  else
    cout << "NO";
  // Usuwanie
  cout << endl << endl
       << "FROM A WE REMOVE";
  for(i = 0; i < 5; i++)
  {
    x = -5+(rand() % 26);
    cout << setw(3) << x;
    s_remove(A, x);
  }
  cout << endl << "A ="; s_print (A);
  cout << endl
       << "SIZE OF A IS " << s_size(A)
       << endl << endl;
  // Sprawdzamy obecność wybranych
  // elementów w B
  for(int i = 0; i < 10; i++)
  {
    x = -5+(rand() % 26);
    cout << "IS ELEMENT"
         << setw(3) << x
         << " IN SET B? ";
    if(s_isin(B, x))
      cout << "YES";
    else
      cout << "NO";
    cout << endl;
  }
  // Sprawdzenie testu na zbiór pusty
  cout << endl
       << "IS SET A EMPTY?" << endl;
  if(s_empty(A))
    cout << "YES";
  else
    cout << "NO";
  cout << endl << endl
       << "IS INTERSECTION OF A AND "
          "COMPLEMENT OF A EMPTY?"
       << endl;
  s_complement(A, C);
  s_intersection(A, C, C);
  if(s_empty(C))
    cout << "YES";
  else
    cout << "NO";
  cout << endl;
  // Usuwamy tablice dynamiczne w zbiorach
  delete [] A.T;
  delete [] B.T;
  delete [] C.T;
  return 0;
}
Basic
' Zbiory zaimplementowane
' w tablicach dynamicznych
' Data: 21.06.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Definicja struktury zbioru
Type Set
  vmin As Integer
  nmax As Integer
  T As Byte Ptr
End Type

' Procedura usuwa wszystkie
' elementy ze zbioru
'--------------------------
Sub s_clear(ByRef A As Set)
  Dim i As Integer
  For i = 0 To A.nmax
    A.T[i] = 0 ' Zerujemy tablicę
  Next
End Sub

' Procedura tworzy pusty zbiór
'-----------------------------
Sub s_create(ByRef A As Set, _
             ByVal vmin As Integer, _
             ByVal vmax As integer)
  A.vmin = vmin ' Wypełniamy strukturę A
  A.nmax = vmax-vmin
  ' Tworzymy tablicę dynamiczną na elementy
  A.T = New Byte [A.nmax+1]
  s_clear(A) ' Zbiór zerujemy
End Sub

' Procedura oblicza sumę zbiorów A i B.
' Wynik umieszcza w zbiorze C
'--------------------------------------
Sub s_union(ByRef A As Set, _
            ByRef B As Set, _
            ByRef C As Set)
  Dim i As Integer
  For i = 0 To A.nmax
    C.T[i] = A.T[i] Or B.T[i]
  Next
End Sub

' Procedura oblicza iloczyn zbiorów A i B.
' Wynik umieszcza w zbiorze C
'-----------------------------------------
Sub s_intersection(ByRef A As Set, _
                   ByRef B As Set, _
                   ByRef C As Set)
  Dim i As Integer
  For i = 0 To A.nmax
    C.T[i] = A.T[i] And B.T[i]
  Next
End Sub

' Procedura oblicza różnicę zbiorów A i B.
' Wynik umieszcza w zbiorze C
'-----------------------------------------
Sub s_difference(ByRef A As Set, _
                 ByRef B As Set, _
                 ByRef C As Set)
  Dim i As Integer
  For i = 0 To A.nmax
    C.T[i] = A.T[i] And Not B.T[i]
  Next
End Sub

' Procedura oblicza dopełnienie zbioru A.
' Wynik umieszcza w zbiorze C
'----------------------------------------
sub s_complement(ByRef A As Set, _
                 ByRef C As Set)
  Dim i As Integer
  For i = 0 To A.nmax
    C.T[i] = 1 And Not A.T[i]
  Next
End Sub

' Funkcja sprawdza, czy zbiór A
' jest podzbiorem zbioru B.
' 1-tak
' 0-nie
'------------------------------
Function s_subset(ByRef A As Set, _
                  ByRef B As Set) _
                          As Integer
  Dim i As Integer
  For i = 0 To A.nmax
    If (A.T[i] = 1) AndAlso _
       (B.T[i] = 0) Then Return 0
  Next
  return 1
End Function

' Funkcja oblicza liczbę elementów
' w zbiorze A
'---------------------------------
Function s_size(ByRef A As Set) _
                        As Integer
  Dim As Integer i, s = 0

  For i = 0 To A.nmax
    s += A.T[i]
  Next
  Return s
End Function

' Funkcja sprawdza, czy zbiór jest pusty.
' 1-tak, zbiór jest pusty
' 0-nie, zbiór nie jest pusty
'----------------------------------------
Function s_empty(ByRef A As Set) _
                         As Integer
  Return (s_size(A) = 0) And 1
End Function

' Procedura dodaje do zbioru element
'-----------------------------------
Sub s_add(ByRef A As Set, _
          ByVal x As Integer)
  A.T[x-A.vmin] = 1
End Sub

' Procedura usuwa ze zbioru element
'----------------------------------
sub s_remove(ByRef A As Set, _
             ByVal x As Integer)
  A.T[x-A.vmin] = 0
End Sub

' Funkcja bada obecność elementu w zbiorze.
' true  - element jest w zbiorze
' false - elementu nie ma w zbiorze
'------------------------------------------
Function s_isin(ByRef A As Set, _
                ByVal x As Integer) _
                        As Integer
  Return A.T[x-A.vmin]
End Function

' Procedura wyświetla zawartość zbioru
'-------------------------------------
Sub s_print(ByRef A As Set)
  Dim i As Integer
  For i = 0 to A.nmax
    If A.T[i] Then _
      Print Using "###";i+A.vmin;
  Next
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Set A, B, C
Dim As Integer i, x

Randomize
' Tworzymy puste zbiory
' o zakresie elementów od -5 do 20
s_create(A, -5, 20)
s_create(B, -5, 20)
s_create(C, -5, 20)
' Do zbioru A dodajemy
' 10 losowych elementów
For i = 1 To 10
  s_add(A, -5+Int(Rnd() * 26))
Next
' Do zbioru B dodajemy 25 losowych elementów
For i = 1 To 25
  s_add(B, -5+Int(Rnd() * 26))
Next
' Wyświetlamy je
Print "A =";: s_print (A): Print
Print "SIZE OF A IS "; s_size(A)
Print
Print "B =";: s_print (B): Print
Print "SIZE OF B IS "; s_size(B)
Print
' Suma zbiorów
Print "UNION OF A AND B IS";
s_union(A, B, C): s_print(C): Print
Print "SIZE OF UNION IS ";s_size(C)
Print
' Iloczyn zbiorów
Print "INTERSECTION OF A AND B IS";
s_intersection(A, B, C): s_print(C): Print
Print "SIZE OF INTERSECTION IS "; s_size(C)
Print
' Różnica zbiorów
Print "DIFFERENCE OF A AND B IS";
s_difference(A, B, C): s_print(C): Print
Print "SIZE OF DIFFERENCE IS "; s_size(C)
Print
' Dopełnienie zbioru
Print "COMPLEMENT OF A IS";
s_complement(A, C): s_print(C): Print
Print "SIZE OF COMPLEMENT IS "; s_size(C)
Print
' Podzbiór
s_union(A, A, C) ' Kopiujemy A do C
For i = 1 to 7 ' Usuwamy 7 elementów
  s_remove(C, -5+Int(Rnd() * 26))
Next
Print "IS";: s_print(C)
Print " SUBSET OF A?"
If s_subset(C, A) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
s_complement(B, C)
For i = 1 To 12 ' Usuwamy 12 elementów
  s_remove(C, -5+Int(Rnd() * 26))
Next
Print "IS";: s_print (C)
Print " SUBSET OF A?"
If s_subset(C, A) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
' Usuwanie
Print "FROM A WE REMOVE";
For i = 1 to 5
  x = -5+Int(Rnd() * 26)
  Print Using "###";x;
  s_remove(A, x)
Next
Print
Print "A =";: s_print(A): Print
Print "SIZE OF A IS"; s_size(A)
Print
' Sprawdzamy obecność wybranych
' elementów w B
For i = 1 To 10
  x = -5+Int(Rnd() * 26)
  Print Using "IS ELEMENT ### IN SET B? ";x;
  If s_isin(B, x) = 1 Then
    Print "YES"
  Else
    Print "NO"
  End If
Next
Print
' Sprawdzenie testu na zbiór pusty
Print "IS SET A EMPTY?"
If s_empty(A) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
Print "IS INTERSECTION OF A AND" + _
      " COMPLEMENT OF A EMPTY?"
s_complement(A, C)
s_intersection(A, C, C)
If s_empty(C) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
' Usuwamy tablice dynamiczne w zbiorach
Delete [] A.T
Delete [] B.T
Delete [] C.T
End
Python (dodatek) 
# Zbiory zaimplementowane
# w tablicach dynamicznych
# Data: 1.09.2024
# (c)2024 mgr Jerzy Wałaszek
#---------------------------

import random


# Definicja struktury zbioru
class Set:


    def __init__(self):
        self.vmin = 0
        self.nmax = 0
        self.t    = []


# Procedura usuwa wszystkie
# elementy ze zbioru
#--------------------------
def s_clear(a):
    for i in range(a.nmax+1):
        a.t[i] = 0


# Procedura tworzy pusty zbiór
#-----------------------------
def s_create(z, vmn, vmx):
    z.vmin = vmn # Wypełniamy strukturę z
    z.nmax = vmx-vmn
    # Tworzymy tablicę dynamiczną na elementy
    z.t = [0] * (z.nmax+1)


# Procedura oblicza sumę zbiorów A i B.
# Wynik umieszcza w zbiorze C.
#--------------------------------------
def s_union(a, b, c):
    for i in range(a.nmax+1):
        c.t[i] = a.t[i] | b.t[i]


# Procedura oblicza iloczyn zbiorów A i B.
# Wynik umieszcza w zbiorze C.
#-----------------------------------------
def s_intersection(a, b, c):
    for i in range(a.nmax+1):
        c.t[i] = a.t[i] & b.t[i]


# Procedura oblicza różnicę zbiorów A i B.
# Wynik umieszcza w zbiorze C.
#-----------------------------------------
def s_difference(a, b, c):
    for i in range(a.nmax+1):
        c.t[i] = a.t[i] & ~ b.t[i]


# Procedura oblicza dopełnienie zbioru a.
# Wynik umieszcza w zbiorze C.
#----------------------------------------
def s_complement(a, c):
    for i in range(a.nmax+1):
        c.t[i] = 1 & ~ a.t[i]


# Funkcja sprawdza, czy zbiór A
# jest podzbiorem zbioru B.
# True  - tak
# False - nie
#------------------------------
def s_subset(a,b):
    for i in range(a.nmax+1):
        if a.t[i] and not b.t[i]:
            return False
    return True


# Funkcja oblicza liczbę elementów
# w zbiorze A
#---------------------------------
def s_size(a):
    s = 0
    for i in range(a.nmax+1):
        s += a.t[i]
    return s


# Funkcja sprawdza, czy zbiór jest pusty.
# True  - tak, zbiór jest pusty
# False - nie, zbiór nie jest pusty
#----------------------------------------
def s_empty(a):
    return s_size(a) == 0


# Procedura dodaje do zbioru element
#-----------------------------------
def s_add(a, x):
    a.t[x-a.vmin] = 1


# Procedura usuwa ze zbioru element
#----------------------------------
def s_remove(a, x):
    a.t[x-a.vmin] = 0


# Funkcja bada obecność elementu w zbiorze.
# True  - element jest w zbiorze
# False - elementu nie ma w zbiorze
#------------------------------------------
def s_isin(a, x):
    return bool(a.t[x-a.vmin])


# Procedura wyświetla zawartość zbioru
#-------------------------------------
def s_print(a):
    for i in range(a.nmax+1):
        if a.t[i]:
            print("%3d" % (i+a.vmin),
                  end="")


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

a = Set()
b = Set()
c = Set()
# Tworzymy puste zbiory
# o zakresie elementów od -5 do 20
s_create(a, -5, 20)
s_create(b, -5, 20)
s_create(c, -5, 20)
# Do zbioru A dodajemy
# 10 losowych elementów
for i in range(10):
    s_add(a, random.randrange(-5, 21))
# Do zbioru B dodajemy 25 losowych elementów
for i in range(25):
    s_add(b, random.randrange(-5, 21))
# Wyświetlamy je
print("A =", end="")
s_print(a)
print()
print("SIZE OF A IS", s_size(a))
print()
print("B =", end="")
s_print(b)
print()
print("SIZE OF B IS", s_size(b))
print()
# Suma zbiorów
print("UNION OF A AND B IS", end="")
s_union(a, b, c)
s_print(c)
print()
print("SIZE OF UNION IS", s_size(c))
print()
# Iloczyn zbiorów
print("INTERSECTION OF A AND B IS", end="")
s_intersection(a, b, c)
s_print(c)
print()
print("SIZE OF INTERSECTION IS", s_size(c))
print()
# Różnica zbiorów
print("DIFFERENCE OF A AND B IS", end="")
s_difference(a, b, c)
s_print(c)
print()
print("SIZE OF DIFFERENCE IS", s_size(c))
print()
# Dopełnienie zbioru
print("COMPLEMENT OF A IS",end="")
s_complement(a, c)
s_print(c)
print()
print("SIZE OF COMPLEMENT IS", s_size(c))
print()
# Podzbiór
s_union(a, a, c) # Kopiujemy A do c
for i in range(7): # Usuwamy 7 elementów
    s_remove(c, random.randrange(-5, 21))
print("IS", end="")
s_print(c)
print(" SUBSET OF A?")
if s_subset(c, a):
    print("YES")
else:
    print("NO")
print()
s_complement(b, c)
for i in range(12): # Usuwamy 12 elementów
    s_remove(c, random.randrange(-5, 21))
print("IS", end="")
s_print(c)
print(" SUBSET OF A?")
if s_subset(c, a):
    print("YES")
else:
    print("NO")
print()
# Usuwanie
print("FROM A WE REMOVE", end="")
for i in range(5):
  x = random.randrange(-5, 21)
  print("%3d" % x, end="")
  s_remove(a, x)
print()
print("A =", end="")
s_print(a)
print()
print("SIZE OF A IS", s_size(a))
print()
# Sprawdzamy obecność wybranych
# elementów w B
for i in range(10):
    x = random.randrange(-5, 21)
    print("IS ELEMENT %3d IN SET B? " %\
          x, end="")
    if s_isin(b, x):
        print("YES")
    else:
        print("NO")
print()
# Sprawdzenie testu na zbiór pusty
print("IS SET A EMPTY?")
if s_empty(a):
    print("YES")
else:
    print("NO")
print()
print("IS INTERSECTION OF A AND COMPLEMENT OF A EMPTY?")
s_complement(a, c)
s_intersection(a, c, c)
if s_empty(c):
    print("YES")
else:
    print("NO")
print()
Wynik: 
A = -3  3  4  6 11 13 18
SIZE OF A IS 7

B = -5 -2 -1  0  1  2  5  7  8 11 12 17 18 19 20
SIZE OF B IS 15

UNION OF A AND B IS -5 -3 -2 -1  0  1  2  3  4  5  6  7  8 11 12 13 17 18 19 20
SIZE OF UNION IS 20

INTERSECTION OF A AND B IS 11 18
SIZE OF INTERSECTION IS 2

DIFFERENCE OF A AND B IS -3  3  4  6 13
SIZE OF DIFFERENCE IS 5

COMPLEMENT OF A IS -5 -4 -2 -1  0  1  2  5  7  8  9 10 12 14 15 16 17 19 20
SIZE OF COMPLEMENT IS 19

IS -3  4 13 18 SUBSET OF A?
YES

IS -4  3  6 13 15 16 SUBSET OF A?
NO

FROM A WE REMOVE 19 20  5  4  5
A = -3  3  6 11 13 18
SIZE OF A IS 6

IS ELEMENT -4 IN SET B? NO
IS ELEMENT 16 IN SET B? NO
IS ELEMENT  4 IN SET B? NO
IS ELEMENT 13 IN SET B? NO
IS ELEMENT  8 IN SET B? YES
IS ELEMENT  2 IN SET B? YES
IS ELEMENT  8 IN SET B? YES
IS ELEMENT -3 IN SET B? NO
IS ELEMENT 19 IN SET B? YES
IS ELEMENT  3 IN SET B? NO

IS SET A EMPTY?
NO

IS INTERSECTION OF A AND COMPLEMENT OF A EMPTY?
YES

do podrozdziału  do strony 

Implementacja zbioru w tablicy haszowanej

Zaletą przedstawionej powyżej implementacji zbioru w tablicy jest niewątpliwa prostota. Wada tego rozwiązania ujawnia się przy dużych przestrzeniach, gdzie elementy zbioru mogą przyjmować wartości z bardzo dużego przedziału. W takich przypadkach zawsze musimy tworzyć tablicę o rozmiarze przestrzeni zbioru. Jeśli maksymalna liczebność zbioru jest dużo mniejsza od liczebności samej przestrzeni, to zbiór możemy odwzorować w tablicy haszowanej. Na przykład, załóżmy, że chcemy w programie mieć struktury odwzorowujące zbiory, które będą przechowywały maksymalnie do 100 elementów, jednakże wartościami tych elementów mogą być liczby z zakresu od 1 do 4 miliardów. W opisanym powyżej rozwiązaniu należałoby utworzyć olbrzymią tablicę o rozmiarze 4GB, a wykorzystywać w niej jedynie 100 komórek – czyste marnotrawstwo pamięci (a gdybyśmy potrzebowali kilka takich struktur danych?).

Na szczęście problem rozwiązują tablice haszowane (ang. hash tables). W tablicy haszowanej element o wartości v znajduje się zwykle (bo nie zawsze, o czym napiszemy za chwilę) na pozycji h(v), gdzie h() jest tzw. funkcją mieszającą (ang. hash function). Funkcja ta wylicza dla wartości v pozycję w tablicy. Zwykle jest tak, że v może przyjmować duży zakres wartości, natomiast h(v) daje mały zakres wartości (np. od 1 do 100). Wynika z tego, że dla wielu wartości v  dostaniemy tę samą wartość h(v).

Zasada wstawiania elementu do tablicy haszowanej jest następująca:

Załóżmy, że chcemy operować elementami, które mogą przyjmować wartości od 1 do 1000. Wiemy, że nasze zbiory nie będą przechowywały naraz więcej niż 5 elementów. Utworzymy 5-cio elementową tablicę haszowaną i wypełnimy ją wstępnie wartościami 0, które oznaczają brak elementu (żaden element zbioru nie ma wartości 0). Niech naszą funkcją haszującą będzie (v mod 5). W zbiorze chcemy umieścić liczby 257, 323, 599, 672 i 924.

indeks element
0 0
1 0
2 0
3 0
4 0
→
indeks element
0 0
1 0
2 257
3 0
4 0
Najpierw wstawiamy do tablicy element 257.
Obliczamy hasz:
257 mod 5 = 2
Komórka o indeksie 2 jest wolna, umieszczamy
w niej nasz element
indeks element
0 0
1 0
2 257
3 0
4 0
→
indeks element
0 0
1 0
2 257
3 323
4 0
Bierzemy kolejny element. Liczymy hasz:
323 mod 5 = 3
Do komórki 3 wstawiamy 323.
indeks element
0 0
1 0
2 257
3 323
4 0
→
indeks element
0 0
1 0
2 257
3 323
4 599
Bierzemy kolejny element. Liczymy hasz:
599 mod 5 = 4
Do komórki 4 wstawiamy 599.
indeks element
0 0
1 0
2 257
3 323
4 599
→
indeks element
0 672
1 0
↓2↓ 257
↓3↓ 323
↓4↓ 599
Bierzemy kolejny element. Liczymy hasz:
672 mod 5 = 2
Jest problem, ponieważ w komórce 2 już jest
element 257. Sytuacja taka jest typowa dla tablic
haszowanych i nazywa się kolizją. Dopóki
w tablicy są wolne miejsca, nie ma tragedii.
Po prostu szukamy, idąc w górę lub w dół indeksów,
pierwszej wolnej komórki i w niej umieszczamy
nasz element. Załóżmy, że pójdziemy w górę
indeksów i, po osiągnięciu ostatniej komórki 4,
wrócimy na początek do komórki 0. Ta jest wolna
i w niej umieścimy nasz element 672.
indeks element
0 672
1 0
2 257
3 323
4 599
→
indeks element
↓0↓ 672
1 924
2 257
3 323
↓4↓ 599
Bierzemy ostatni element. Liczymy hasz:
924 mod 5 = 4
Tutaj znów mamy kolizję, ponieważ w komórce 4
jest już element 599. Postępujemy identycznie jak
w przypadku poprzednim. Idziemy w górę indeksów,
przewijamy indeksy do 0 i kontynuujemy
przeglądanie tablicy aż do komórki 1, która jest pusta.
Tam umieszczamy nasz element.
indeks element
0 672
1 924
2 257
3 323
4 599
    Tablica haszowana została zapełniona.
W rzeczywistości rozmiar tablicy przyjmuje się nieco
większy od spodziewanej liczebności zbioru.
Ten zapas może zmniejszać kolizję i przyspieszać
operację wyszukiwania wolnych komórek. Im mniej
kolizji, tym szybciej będą wykonywane operacje
na tablicy haszowanej.

Wyszukiwanie elementu v w tablicy haszowanej wygląda podobnie. Najpierw wyliczamy hasz h(v). Następnie sprawdzamy komórkę o indeksie równym h(v). Jeśli komórka jest pusta, to danego elementu nie ma w zbiorze. Jeśli komórka zawiera inną wartość od v, to niestety mamy kolizję. W takim przypadku przeglądamy kolejne komórki tablicy, idąc w górę indeksów aż do momentu, gdy natrafimy na poszukiwaną wartość v (wtedy kończymy z wynikiem pozytywnym) lub natrafimy na komórkę pustą albo wrócimy do komórki wyjściowej. W obu wypadkach oznacza to, że elementu v w zbiorze nie ma. Obecność pustych komórek przyspiesza operację sprawdzania przynależności elementu do zbioru.

Zbiór jest zawsze reprezentowany przez strukturę Set zawierającą pola:

vmin : dolna granica wartości elementów.
nmax : indeks ostatniej komórki tablicy haszowanej.
T : tablica haszowana o typie elementów takim, aby pomieścił elementy zbioru. Tablica zawiera nmax+1 elementów.
Pascal
type
  Set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of byte;
  end;
C++
struct Set
{
  int vmin, nmax;
  char * T;
};
Basic
Type Set
  vmin As Integer
  nmax As Integer
  T As Byte Ptr
End Type
Python (dodatek) 
class Set:


    def __init__(self)
        self.vmin = 0
        self.nmax = 0
        self.t = []

Elementy zbioru nie muszą być liczbami całkowitymi. Jedynie funkcja haszująca musi zwracać wartości całkowite w zakresie od 0 do nmax-1. To jedna z zalet tablic haszowanych.

Umawiamy się, że komórka jest pusta, jeśli zawiera wartość mniejszą od vmin.

Uwaga!
Przetwarzane zbiory muszą posiadać takie same parametry vmin i nmax.
Maksymalna liczebność zbioru powinna zawsze być mniejsza od nmax – to bardzo ważne.

Algorytmy operacji dla zbiorów reprezentowanych tablicami haszowanymi

s_find(A, x) – funkcja pomocnicza, wyszukuje w tablicy haszowanej A→T pozycję x.

Algorytm oblicza hasz wartości x i zapamiętuje go w zmiennej i. Następnie w pętli sprawdza zawartość komórki A→T[i]. Jeśli komórka jest pusta lub zawiera x, to zwraca jej indeks i kończy działanie. Jeśli nie, to zwiększa indeks i o 1. Gdy indeks będzie równy A→nmax, to jest zerowany. Następuje powrót na początek pętli i ponowne sprawdzenie warunków zakończenia. Algorytm zakłada, że w tablicy są puste komórki. Należy zatem zawsze przydzielać na zbiór nieco większą tablicę. W przeciwnym razie należałoby dodatkowo sprawdzać, czy pętla poszukująca nie powróciła do tej samej komórki – dzieje się tak tylko wtedy, gdy elementu x nie ma w tablicy, a tablica została całkowicie zapełniona.

Wejście:

A : referencja do struktury Set.
x : wartość poszukiwanego elementu.

Wyjście:

Pozycja elementu x w tablicy A→T.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.

Lista kroków:

K01: i ← (x-A→vmin) mod (A→nmax+1) ; obliczamy hasz
K02: Dopóki (A→T[i] ≠ x) obrazek (A→T[i] ≥ A→vmin), wykonuj:
     i ← (i+1) mod (A→nmax+1) ; szukamy komórki z x lub pustej
K03: Zakończ z wynikiem i ; znaleziony indeks zwracamy

s_add(A, x) – dodaje element x do zbioru A.

Algorytm znajduje komórkę w tablicy A→T odpowiadającą elementowi x i umieszcza go w niej.

Wejście:

A : referencja do struktury Set.
x : element do dodania do zbioru.

Wyjście:

Zbiór A z dodanym elementem x.

Elementy pomocnicze:

s_find(Z, x) : znajduje indeks odpowiadający wartości elementu x.

Lista kroków:

K01: A→T[s_find(A, x)] ← x ; umieszczamy element w zbiorze
K02: Zako b>

s_remove(A, x) – usuwa element x ze zbioru A

Algorytm znajduje komórkę w tablicy A→T odpowiadającą elementowi x i umieszcza w niej wartość A→vmin-1, co odpowiada pustej komórce

Wejście:

A : referencja do struktury Set.
x : element do dodania do zbioru.

Wyjście:

Zbiór A z usuniętym elementem x.

Elementy pomocnicze:

s_find(Z, x) : znajduje indeks odpowiadający wartości elementu x.

Lista kroków:

K01: A→T[s_find(A, x)] ← A→vmin-1 ; usuwamy element ze zbioru
K02: Zakończ

s_clear(A) – usuwa wszystkie elementy ze zbioru A. Zbiór A staje się zbiorem pustym.

Algorytm wypełnia tablicę A→T wartościami A→vmin-1. W ten sposób powstanie zbiór pusty.

Wejście:

A : referencja do struktury Set.

Wyjście:

Pusty zbiór A.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.
v : zawartość pustej komórki.

Lista kroków:

K01: v ← A→vmin-1
K02: Dla i = 0, 1, …, A→nmax: ; zerujemy komórki tablicy
     wykonuj A→T[i] ← v
K03: Zakończ

s_create(A, vmin, nmax) – tworzy pusty zbiór A o odpowiednim rozmiarze

Algorytm wypełnia strukturę zbioru A, tworzy tablicę dynamiczną o wyliczonym rozmiarze A→nmax i wypełnia ją wartością A→vmin-1, co daje w efekcie pusty zbiór A.

Wejście:

A : referencja do struktury Set.
vmin : minimalna wartość elementu zbioru.
nmax : maksymalna liczba elementów w zbiorze.

Wyjście:

Pusty zbiór A.

Elementy pomocnicze:

s_clear(Z) : usuwa ze zbioru Z wszystkie elementy.

Lista kroków:

K01: A→vmin ← A→vmin ; wypełniamy strukturę Set
                     ; odpowiednimi wartościami
K02: A→nmax ← A→nmax-1
K03: Utwórz obszar dla A→nmax+1 komórek ; tworzymy
                                        ; tablicę dynamiczną
K04: A→T ← adres utworzonego obszaru
K05: s_clear(A) ; tworzymy pusty zbiór
K06: Zakończ

s_union(A, B, C) – zwraca sumę zbiorów A i B

Algorytm umieszcza w zbiorze C wszystkie elementy zbiorów A i B.

Wejście:

A, B, C : referencje do struktur Set.

Wyjście:

Zbiór C zawiera sumę zbiorów A i B.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.
s_clear(Z) : tworzy pusty zbiór.
s_add(Z, x) : dodaje element x do zbioru Z.

Lista kroków:

K01: s_clear(C) ; upewniamy się, że zbiór C będzie pusty
K02: Dla i = 0, 1, …, A→nmax:
     wykonuj kroki K03…K4
K03:   Jeśli A→T[i] ≥ A→vmin, ; elementy zbioru A dodajemy do zbioru C
       to s_add(C, A→T[i])
K04:   Jeśli B→T[i] ≥ B→vmin, ; elementy zbioru B dodajemy do zbioru C
       to s_add(C, B→T[i])
K05: Zakończ

s_intersection(A, B, C) – zwraca iloczyn zbiorów A i B

Algorytm przeszukuje zbiór A. Dla każdego elementu znalezionego w tym zbiorze sprawdza, czy element ten również występuje w zbiorze B. Jeśli tak, to element jest dodawany do zbioru C.

Wejście:

A, B, C : referencje do struktur Set.

Wyjście:

Zbiór C zawiera iloczyn zbiorów A i B.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.
s_clear(Z) : tworzy pusty zbiór.
s_find(Z, x) : znajduje indeks elementu x w zbiorze Z.
s_add(Z, x) : dodaje element x do zbioru Z.

Lista kroków:

K01: s_clear(C) ; upewniamy się, że zbiór C będzie pusty
K02: Dla i = 0, 1, …, A→nmax, 
     wykonuj krok K03
K03:   Jeśli (A→T[i] ≥ A→vmin) obrazek
             (B→T[s_find(B, A→T[i])] = A→T[i]), 
       to s_add(C, A→T[i]) ; sprawdzamy, czy element z A jest w B.
                           ; Jeśli tak, to dodajemy go do C
K04: Zakończ

s_difference(A, B, C) – zwraca różnicę zbioru A i B

Algorytm przeszukuje zbiór A. Dla każdego znalezionego elementu sprawdza, czy znajduje się on w zbiorze B. Jeśli nie, to dodaje go do zbioru C.

Wejście:

A, B, C : referencje do struktur Set.

Wyjście:

Zbiór C zawiera różnicę zbiorów A i B.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.
s_clear(Z) : tworzy pusty zbiór.
s_find(Z, x) : znajduje indeks elementu x w zbiorze Z.
s_add(Z, x) : dodaje element x do zbioru Z.

Lista kroków:

K01: s_clear(C) ; upewniamy się, że zbiór C będzie pusty
K02: Dla i = 0, 1, …, A→nmax,
     wykonuj krok K03
K03:   Jeśli (A→T[i] ≥ A→vmin) obrazek
             (B→T[s_find(B, A→T[i])] ≠ A→T[i]), 
       to s_add(C, A→T[i]) ; sprawdzamy, czy element z A
       ; jest w B. Jeśli nie, to dodajemy go do C
K05: Zakończ

s_subset(A, B) – zwraca true, jeśli zbiór A jest podzbiorem zbioru B, inaczej zwraca false.

Algorytm przegląda zbiór A. Dla każdego znalezionego elementu sprawdza, czy występuje on w B. Jeśli nie, to kończy z wynikiem false. Gdy wszystkie elementy A będą w B, algorytm zwróci true.

Wejście:

A, B : referencja do struktur Set.

Wyjście:

true : zbiór A jest podzbiorem zbioru B.
false : zbiór A nie jest podzbiorem zbioru B.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.
s_find(Z, x) : znajduje indeks elementu x w zbiorze Z.

Lista kroków:

K01: Dla i = 0, 1, …, A→nmax,
     wykonuj krok K02
K02:   Jeśli (A→T[i] ≥ A→vmin) obrazek
             (B→T[s_find(B, A→T[i])] ≠ A→T[i]), 
       to zakończ z wynikiem false ; sprawdzamy, czy element z A jest w B.
       ; Jeśli nie, to kończymy z false
K03: Zakończ z wynikiem true

s_size(A) – zwraca liczbę elementów zawartych w zbiorze A

Algorytm zlicza elementy zbioru A i zwraca ich liczbę.

Wejście:

A : referencja do struktury Set.

Wyjście:

Liczba elementów w A.

Elementy pomocnicze:

i : indeksowanie komórek, i ∈ C.
c : licznik komórek, c ∈ C.

Lista kroków:

K01: c ← 0 ; zerujemy licznik
K02: Dla i = 0, 1, …, A→nmax,
     wykonuj:
       Jeśli A→T[i] ≥ A→vmin, ; zliczamy komórki z elementami
       to c ← c+1
K03: Zakończ z wynikiem c

s_empty(A) – zwraca true, jeśli zbiór A jest pusty, inaczej zwraca false

Algorytm oblicza liczbę elementów w zbiorze A. Jeśli jest równa zero, zwraca true, inaczej zwraca false.

Wejście:

A : referencja do struktury Set.

Wyjście:

true : zbiór A jest pusty.
false : zbiór A nie jest pusty.

Elementy pomocnicze:

s_size(Z) : zwraca liczbę elementów w zbiorze Z.

Lista kroków:

K01: Jeśli s_size(A) = 0, 
     to zakończ z wynikiem true
K02: Zakończ z wynikiem false

s_isin(A, x) – zwraca true, jeśli element x jest w zbiorze A, inaczej zwraca false

Algorytm wyszukuje w tablicy komórkę, w której powinna być wartość x. Jeśli jest tam, zwraca true, inaczej zwraca false.

Wejście:

A : referencja do struktury Set.
x : sprawdzany element, x ∈ C.

Wyjście:

true : element o wartości x jest w zbiorze A.
false : elementu o wartości x nie ma w zbiorze A.

Lista kroków:

K01: Jeśli A→T[s_find(A, x)] = x, ; sprawdzamy obecność elementu
     to zakończ z wynikiem true
K02: Zakończ z wynikiem false

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.
Program testuje wszystkie funkcje obsługi zbiorów opartych na dynamicznych tablicach haszowanych. Wyjaśnienie wykonywanych operacji znajduje się w komentarzach wewnątrz programu.
Pascal
// Zbiory zaimplementowane
// w tablicach haszowanych
// Data: 22.06.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program sets;

// Definicja struktury zbioru
type
  Set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of integer;
  end;

// Funkcja znajduje w tablicy
// haszowanej pozycję elementu x
//------------------------------
function s_find(var A : Set;
                    x : integer)
                      : integer;
var
  i : integer;
begin
  // Obliczamy hasz
  i := (x-A.vmin) mod (A.nmax + 1);
  // Szukamy x
  while (A.T[i] <> x) and
        (A.T[i] >= A.vmin) do
    i := (i+1) mod (A.nmax+1);
  // Zwracamy jego indeks
  s_find := i;
end;

// Procedura dodaje element
// x do zbioru A
//-------------------------
procedure s_add(var A : Set;
                    x : integer);
begin
  // Wstawiamy x do zbioru
  A.T[s_find(A, x)] := x;
end;

// Procedura usuwa element x
// ze zbioru
//--------------------------
procedure s_remove(var A : Set;
                       x : integer);
begin
  // Usuwamy x ze zbioru
  A.T[s_find(A, x)] := A.vmin-1;
end;

// Procedura usuwa wszystkie
// elementy ze zbioru
//--------------------------
procedure s_clear(var A : Set);
var
  i, v : integer;
begin
  // Obliczamy pusty element
  v := A.vmin-1;
  // Wypełniamy nim tablicę haszowaną
  for i := 0 to A.nmax do
    A.T[i] := v;
end;

// Procedura tworzy zbiór
//-----------------------
procedure s_create(var A : Set;
              vmin, nmax : integer);
begin
  // Wypełniamy strukturę danymi
  A.vmin := vmin;
  A.nmax := nmax-1;
  // Tworzymy dynamicznie
  // tablicę haszowaną
  SetLength(A.T, nmax);
  // Tworzymy zbiór pusty
  s_clear(A);
end;

// Procedura wyznacza w C
// sumę zbiorów A i B
//-----------------------
procedure s_union(var A, B, C : Set);
var
  i : integer;
begin
  // Zerujemy zbiór C
  s_clear(C);
  // Przeglądamy kolejne elementy
  for i := 0 to A.nmax do
  begin
    // Dodajemy do C elementy A
    if A.T[i] >= A.vmin then
      s_add(C, A.T[i]);
    // Dodajemy do C elementy B
    if B.T[i] >= B.vmin then
      s_add(C, B.T[i]);
  end;
end;

// Procedura wyznacza część wspólną
// zbiorów A i B
//---------------------------------
procedure s_intersection(var A, B, C : Set);
var
  i : integer;
begin
  // Zerujemy zbiór C
  s_clear(C);
  // Przeglądamy kolejne elementy A
  for i := 0 to A.nmax do
    if (A.T[i] >= A.vmin) and
       (B.T[s_find(B, A.T[i])] = A.T[i]) then
      // Jeśli element A jest w B,
      // dodajemy go do C
      s_add (C, A.T [i]);
end;

// Procedura wyznacza różnicę
// zbiorów A i B
//---------------------------
procedure s_difference(var A, B, C : Set);
var
  i : integer;
begin
  // Zerujemy zbiór C
  s_clear(C);
  // Przeglądamy kolejne elementy A
  for i := 0 to A.nmax do
    if (A.T[i] >= A.vmin) and
       (B.T[s_find(B, A.T[i])] <> A.T[i]) then
      // Jeśli element A nie jest w B,
      // dodajemy go do C
      s_add(C, A.T[i]);
end;

// Funkcja sprawdza, czy zbiór A jest
// podzbiorem zbioru B
// true  - tak, jest
// false - nie, nie jest
//-----------------------------------
function s_subset(var A, B : Set)
                           : boolean;
var
  i : integer;
begin
  // Przeglądamy kolejne elementy A
  for i := 0 to A.nmax do
    if (A.T[i] >= A.vmin) and
       (B.T[s_find(B, A.T[i])] <> A.T[i]) then
      // Jeśli elementu A nie ma w B,
      // kończymy z false
      Exit(false);
  s_subset := true;
end;

// Funkcja oblicza liczbę elementów w A
//-------------------------------------
function s_size(var A : Set)
                      : integer;
var
  i, c : integer;
begin
  // Zerujemy licznik
  c := 0;
  // Przechodzimy przez kolejne komórki
  for i := 0 to A.nmax do
    // Zliczamy komórki z elementami
    if A.T[i] >= A.vmin then inc(c);
  s_size := c;
end;

// Funkcja sprawdza, czy zbiór A jest pusty
// true  - tak, jest pusty
// false - nie, nie jest pusty
//-----------------------------------------
function s_empty(var A : Set) : boolean;
begin
  // Testujemy warunek
  s_empty := (s_size(A) = 0);
end;

// Funkcja bada, czy element x
// należy do zbioru A
// true  - tak, należy
// false - nie, nie należy
//-----------------------------
function s_isin(var A : Set;
                    x : integer)
                      : boolean;
begin
  // Testujemy warunek
  s_isin := (A.T[s_find(A, x)] = x);
end;

// Procedura wyświetla elementy zbioru A
//--------------------------------------
procedure s_print(var A : Set);
var
  i : integer;
begin
  for i := 0 to A.nmax do
    if A.T[i] >= A.vmin then
      write(A.T[i]:4);
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  A, B, C : Set;
  i, x    : integer;

begin
  randomize;
  // Inicjujemy zmienne
  A.nmax:= 0;
  B.nmax:= 0;
  c.nmax:= 0;
  // Tworzymy puste zbiory o zakresie elementów
  // od -20 i liczebności 30
  s_create(A, -20, 30);
  s_create(B, -20, 30);
  s_create(C, -20, 30);
  // Do zbioru A dodajemy 10 losowych elementów
  for i := 1 to 10 do
    s_add(A, -20+random(41));
  // Do zbioru B dodajemy 15 losowych elementów
  for i := 1 to 15 do
    s_add(B, -20+random(41));
  // Wyświetlamy je
  writeln('A:');
  s_print(A);
  writeln;
  writeln('SIZE OF A IS ', s_size(A));
  writeln;
  writeln('B:');
  s_print(B);
  writeln;
  writeln('SIZE OF B IS ', s_size(B));
  // Suma zbiorów
  writeln;
  writeln('UNION OF A AND B:');
  s_union(A, B, C);
  s_print(C);
  writeln;
  writeln('SIZE OF UNION IS ', s_size(C));
  // Iloczyn zbiorów
  writeln;
  writeln('INTERSECTION OF A AND B:');
  s_intersection(A, B, C);
  s_print(C);
  writeln;
  writeln('SIZE OF INTERSECTION IS ', s_size(C));
  // Różnica zbiorów
  writeln;
  writeln('DIFFERENCE OF A AND B:');
  s_difference(A, B, C);
  s_print(C);
  writeln;
  writeln('SIZE OF DIFFERENCE IS ', s_size(C));
  // Podzbiór
  s_union(A, A, C); // Kopiujemy A do C
  for i := 1 to 7 do // Usuwamy 7 elementów
    s_remove(C, -20+random(41));
  writeln;
  writeln('IS:');
  s_print(C);
  writeln(' SUBSET OF A?');
  writeln(s_subset(C, A));
  s_difference(B, A, C);
  // Usuwamy 12 elementów
  for i := 1 to 12 do
    s_remove(C, -20+random(41));
  writeln;
  writeln('IS:');
  s_print(C);
  writeln(' SUBSET OF A?');
  writeln(s_subset(C, A));
  // Usuwanie
  writeln;
  write('FROM A WE REMOVE');
  for i := 1 to 5 do
  begin
    x := -20+random(41);
    write(x:4);
    s_remove(A, x);
  end;
  writeln;
  writeln('A:');
  s_print(A);
  writeln;
  writeln('SIZE OF A IS ', s_size(A));
  writeln;
  // Sprawdzamy obecność wybranych
  // elementów w B
  for i := 1 to 10 do
  begin
    x := -20+random(41);
    write('IS ELEMENT', x:4, ' IN SET B? ');
    if s_isin(B, x) then
      writeln('YES')
    else
      writeln('NO');
  end;
  writeln;
  // Sprawdzenie testu na zbiór pusty
  writeln('IS SET A EMPTY?');
  writeln(s_empty(A));
  writeln;
  writeln('IS INTERSECTION OF A AND ' +
          'DIFFERENCE OF B AND A EMPTY?');
  s_difference(B, A, C);
  s_intersection(A, C, C);
  writeln(s_empty(C));
  writeln;
  // Usuwamy tablice dynamiczne w zbiorach
  SetLength(A.T, 0);
  SetLength(B.T, 0);
  SetLength(C.T, 0);
end.
C++
// Zbiory zaimplementowane
// w tablicach haszowanych
// Data: 22.06.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

// Definicja struktury zbioru
struct Set
{
  int vmin, nmax, *T;
};

// Funkcja znajduje w tablicy
// haszowanej pozycję elementu x
//------------------------------
int s_find(Set & A, int x)
{
  // Obliczamy hasz
  int i = (x-A.vmin) % (A.nmax+1);
  // Szukamy x
  while((A.T[i] != x) &&
        (A.T[i] >= A.vmin))
    i = (i+1) % (A.nmax+1);
  // Zwracamy jego indeks
  return i;
}

// Procedura dodaje element x
// do zbioru A
//---------------------------
void s_add(Set & A, int x)
{
  // Wstawiamy x do zbioru
  A.T[s_find(A, x)] = x;
}

// Procedura usuwa element x
// ze zbioru
//--------------------------
void s_remove(Set & A, int x)
{
  // Usuwamy x ze zbioru
  A.T[s_find(A, x)] = A.vmin-1;
}

// Procedura usuwa wszystkie
// elementy ze zbioru
//--------------------------
void s_clear(Set & A)
{
  // Obliczamy pusty element
  int v = A.vmin-1;
  for(int i = 0; i <= A.nmax; i++)
    // Wypełniamy nim tablicę haszowaną
    A.T[i] = v;
}

// Procedura tworzy zbiór
//-----------------------
void s_create(Set & A,
              int vmin,
              int nmax)
{
  // Wypełniamy strukturę danymi
  A.vmin = vmin;
  A.nmax = nmax-1;
  // Tworzymy dynamicznie
  // tablicę haszowaną
  A.T = new int [nmax];
  // Tworzymy zbiór pusty
  s_clear(A);
}

// Procedura wyznacza w C
// sumę zbiorów A i B
//------------------------
void s_union(Set & A,
             Set & B,
             Set & C)
{

  // Zerujemy zbiór C
  s_clear(C);
  // Przeglądamy kolejne elementy
  for(int i = 0; i <= A.nmax; i++)
  {
    if(A.T[i] >= A.vmin)
      // Dodajemy do C elementy A
      s_add(C, A.T[i]);
    if(B.T[i] >= B.vmin)
      // Dodajemy do C elementy B
      s_add(C, B.T[i]);
  }
}

// Procedura wyznacza część
// wspólną zbiorów A i B
//-------------------------
void s_intersection(Set & A,
                    Set & B,
                    Set & C)
{
  // Zerujemy zbiór C
  s_clear(C);
  // Przeglądamy kolejne elementy A
  for(int i = 0; i <= A.nmax; i++)
    if((A.T[i] >= A.vmin) &&
       (B.T[s_find(B, A.T[i])] == A.T[i]))
      // Jeśli element A jest w B,
      // dodajemy go do C
      s_add(C, A.T[i]);
}

// Procedura wyznacza różnicę
// zbiorów A i B
//---------------------------
void s_difference (Set & A,
                   Set & B,
                   Set & C)
{
  // Zerujemy zbiór C
  s_clear(C);
  // Przeglądamy kolejne elementy A
  for(int i = 0; i <= A.nmax; i++)
    if((A.T[i] >= A.vmin) &&
       (B.T[s_find(B, A.T[i])] != A.T[i]))
      // Jeśli element A nie jest w B,
      // dodajemy go do C
      s_add(C, A.T[i]);
}

// Funkcja sprawdza, czy zbiór A
// jest podzbiorem zbioru B
// true  - tak, jest
// false - nie, nie jest
//------------------------------
bool s_subset(Set & A,
              Set & B)
{
  // Przeglądamy kolejne elementy A
  for(int i = 0; i <= A.nmax; i++)
    if((A.T[i] >= A.vmin) &&
       (B.T[s_find(B, A.T[i])] != A.T[i]))
      // Jeśli elementu A nie ma w B,
      // kończymy z false
      return false;
  return true;
}

// Funkcja oblicza liczbę
// elementów w A
//-----------------------
int s_size(Set & A)
{
  // Zerujemy licznik
  int cnt = 0;
  // Przechodzimy przez kolejne komórki
  for(int i = 0; i <= A.nmax; i++)
    // Zliczamy komórki z elementami
    if(A.T[i] >= A.vmin) cnt++;
  return cnt;
}

// Funkcja sprawdza, czy zbiór A
// jest pusty
// true  - tak, jest pusty
// false - nie, nie jest pusty
//------------------------------
bool s_empty(Set A)
{
  // Testujemy warunek
  return !s_size(A);
}

// Funkcja bada, czy element x
// należy do zbioru A
// true  - tak, należy
// false - nie, nie należy
//----------------------------
bool s_isin(Set & A, int x)
{
  // Testujemy warunek
  return A.T[s_find(A, x)] == x;
}

// Procedura wyświetla elementy
// zbioru A
//-----------------------------
void s_print(Set A)
{
  for(int i = 0; i <= A.nmax; i++)
    if(A.T[i] >= A.vmin)
      cout << setw(4) << A.T[i];
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  Set A, B, C;
  int i, x;

  srand(time(NULL));
  // Tworzymy puste zbiory o zakresie
  // elementów od -20 i liczebności 30
  s_create(A, -20, 30);
  s_create(B, -20, 30);
  s_create(C, -20, 30);
  // Do zbioru A dodajemy 10
  // losowych elementów
  for(i = 0; i < 10; i++)
    s_add(A, -20+(rand() % 41));
  // Do zbioru B dodajemy 15
  // losowych elementów
  for(i = 0; i < 15; i++)
    s_add(B, -20+(rand() % 41));
  // Wyświetlamy je
  cout << "A:" << endl;
  s_print(A);
  cout << endl
       << "SIZE OF A IS " << s_size(A)
       << endl << endl << "B:" << endl;
  s_print(B);;
  cout << endl
       << "SIZE OF B IS " << s_size(B)
       << endl << endl
  // Suma zbiorów
       << "UNION OF A AND B:" << endl;
  s_union(A, B, C);
  s_print(C);
  cout << endl
       << "SIZE OF UNION IS " << s_size(C)
       << endl << endl
  // Iloczyn zbiorów
       << "INTERSECTION OF A AND B:"
       << endl;
  s_intersection(A, B, C);
  s_print(C);
  cout << endl
       << "SIZE OF INTERSECTION IS " << s_size(C)
       << endl << endl
  // Różnica zbiorów
       << "DIFFERENCE OF A AND B:" << endl;
  s_difference(A, B, C);
  s_print(C);
  cout << endl
       << "SIZE OF DIFFERENCE IS " << s_size(C)
       << endl << endl;
  // Podzbiór
  // Kopiujemy A do C
  s_union(A, A, C);
  // Usuwamy 7 elementów
  for(i = 0; i < 7; i++)
    s_remove(C, -20+(rand() % 41));
  cout << "IS:" << endl;
  s_print(C);
  cout << " SUBSET OF A?" << endl
       << (s_subset(C, A) ? "YES": "NO")
       << endl << endl;
  s_difference(B, A, C);
  // Usuwamy 12 elementów
  for(i = 0; i < 12; i++)
    s_remove(C, -20+(rand() % 41));
  cout << "IS:" << endl;
  s_print(C);
  cout << " SUBSET OF A?" << endl
       << (s_subset(C, A) ? "YES": "NO")
       << endl << endl
  // Usuwanie
       << "FROM A WE REMOVE";
  for(i = 0; i < 5; i++)
  {
    x = -20+(rand() % 41);
    cout << setw(4) << x;
    s_remove(A, x);
  }
  cout << endl << "A:" << endl;
  s_print(A);
  cout << endl
       << "SIZE OF A IS " << s_size(A)
       << endl << endl;
  // Sprawdzamy obecność
  // wybranych elementów w B
  for(i = 0; i < 10; i++)
  {
    x = -20+(rand() % 41);
    cout << "IS ELEMENT" << setw(4) << x
         << " IN SET B? "
         << (s_isin(B, x) ? "YES": "NO")
         << endl;
  }
  // Sprawdzenie testu na zbiór pusty
  cout << endl
       << "IS SET A EMPTY?" << endl
       << (s_empty(A) ? "YES": "NO")
       << endl << endl
       << "IS INTERSECTION OF A AND "
          "DIFFERENCE OF B AND A EMPTY?"
       << endl;
  s_difference(B, A, C);
  s_intersection(A, C, C);
  cout << (s_empty(C) ? "YES": "NO")
       << endl << endl;
  // Usuwamy tablice dynamiczne w zbiorach
  delete [] A.T;
  delete [] B.T;
  delete [] C.T;
  return 0;
}
Basic
' Zbiory zaimplementowane
' w tablicach haszowanych
' Data: 22.06.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Definicja struktury zbioru
Type Set
  vmin As Integer
  nmax As Integer
  T As Integer Ptr
End Type

' Funkcja znajduje w tablicy haszowanej
' pozycję elementu x
'-------------------------------------
Function s_find(ByRef A As Set, _
                ByVal x As Integer) _
                        As Integer
  Dim As Integer i
  ' Obliczamy hasz
  i = (x-A.vmin) Mod (A.nmax+1)
  ' Szukamy x
  while (A.T[i] <> x) AndAlso _
        (A.T[i] >= A.vmin)
    i = (i+1) Mod (A.nmax+1)
  Wend
  Return i ' Zwracamy jego indeks
End Function

' Procedura dodaje element x do zbioru A
'---------------------------------------
Sub s_add(ByRef A As Set, _
          ByVal x As Integer)
  ' Wstawiamy x do zbioru
  A.T[s_find(A, x)] = x
End Sub

' Procedura usuwa element x ze zbioru
'------------------------------------
Sub s_remove(ByRef A As Set, _
             ByVal x As Integer)
  ' Usuwamy x ze zbioru
  A.T[s_find(A, x)] = A.vmin-1
End Sub

' Procedura usuwa wszystkie
' elementy ze zbioru
'--------------------------
Sub s_clear(ByRef A As Set)
  ' Obliczamy pusty element
  Dim As Integer i, v = A.vmin-1
  For i = 0 To A.nmax
    ' Wypełniamy nim tablicę haszowaną
    A.T[i] = v
  Next
End Sub

' Procedura tworzy zbiór
'-----------------------
Sub s_create(ByRef A As Set, _
             ByVal vmin As Integer, _
             ByVal nmax As Integer)
  ' Wypełniamy strukturę danymi
  A.vmin = vmin
  A.nmax = nmax-1
  ' Tworzymy dynamicznie tablicę haszowaną
  A.T = New Integer [nmax]
  s_clear(A) ' Tworzymy zbiór pusty
End Sub

' Procedura wyznacza w C sumę zbiorów A i B
'------------------------------------------
Sub s_union(ByRef A As Set, _
            ByRef B As Set, _
            ByRef C As Set)
  Dim As Integer i

  s_clear(C) ' Zerujemy zbiór C
  ' Przeglądamy kolejne elementy
  For i = 0 To A.nmax
    ' Dodajemy do C elementy A
    If A.T[i] >= A.vmin Then _
      s_add(C, A.T[i])
    ' Dodajemy do C elementy B
    If B.T[i] >= B.vmin Then _
      s_add(C, B.T[i])
  Next
End Sub

' Procedura wyznacza część wspólną
' zbiorów A i B
'---------------------------------
Sub s_intersection(ByRef A As Set, _
                   ByRef B As Set, _
                   ByRef C As Set)
  Dim As Integer i
  s_clear(C) ' Zerujemy zbiór C
  ' Przeglądamy kolejne elementy A
  For i = 0 To A.nmax
    if (A.T[i] >= A.vmin) AndAlso _
       (B.T[s_find(B, A.T[i])] = A.T[i]) Then
      ' Jeśli element A jest w B,
      ' dodajemy go do C
      s_add(C, A.T[i])
    End If
  Next
End Sub

' Procedura wyznacza różnicę zbiorów A i B
'-----------------------------------------
Sub s_difference(ByRef A As Set, _
                 ByRef B As Set, _
                 ByRef C As Set)
  Dim As Integer i
  s_clear(C) ' Zerujemy zbiór C
  ' Przeglądamy kolejne elementy A
  For i = 0 To A.nmax
    if(A.T[i] >= A.vmin) AndAlso _
      (B.T[s_find(B, A.T[i])] <> A.T[i]) Then
      ' Jeśli element A nie jest w B,
      ' dodajemy go do C
      s_add(C, A.T[i])
    End If
  Next
End Sub

' Funkcja sprawdza, czy zbiór A
' jest podzbiorem zbioru B
' true  - tak, jest
' false - nie, nie jest
'------------------------------
Function s_subset(ByRef A As Set, _
                  ByRef B As Set) _
                          As Integer
  Dim As Integer i
  ' Przeglądamy kolejne elementy A
  For i = 0 To A.nmax
    if(A.T[i] >= A.vmin) AndAlso _
      (B.T[s_find(B, A.T[i])] <> A.T[i]) Then
      ' Jeśli elementu A nie ma w B,
      ' kończymy z false
      Return 0
    End If
  Next
  Return 1
End Function

' Funkcja oblicza liczbę elementów w A
'-------------------------------------
Function s_size(ByRef A As Set) _
                        As Integer
  ' Zerujemy licznik
  Dim As Integer i, cnt = 0
  ' Przechodzimy przez kolejne komórki
  For i = 0 To A.nmax
    ' Zliczamy komórki z elementami
    If A.T[i] >= A.vmin Then cnt += 1
  Next
  Return cnt
End Function

' Funkcja sprawdza, czy zbiór A jest pusty
' true  - tak, jest pusty
' false - nie, nie jest pusty
'-----------------------------------------
Function s_empty(ByRef A As Set) _
                         As Integer
  ' Testujemy warunek
  Return (s_size(A) = 0) And 1
End Function

' Funkcja bada, czy element x
' należy do zbioru A
' true  - tak, należy
' false - nie, nie należy
'----------------------------
Function s_isin(ByRef A As Set, _
                ByVal x As Integer) _
                        As Integer
  ' Testujemy warunek
  Return (A.T[s_find(A, x)] = x) And 1
End Function

' Procedura wyświetla elementy zbioru A
'--------------------------------------
Sub s_print(ByRef A As Set)
  Dim As Integer i
  For i = 0 To A.nmax
    If A.T[i] >= A.vmin Then _
      Print Using "####"; A.T[i];
  Next
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Set A, B, C
Dim As Integer i, x

Randomize

' Tworzymy puste zbiory
' o zakresie elementów
' od -20 i o liczebności 30
s_create(A, -20, 30)
s_create(B, -20, 30)
s_create(C, -20, 30)
' Do zbioru A dodajemy
' 10 losowych elementów
For i = 1 To 10
  s_add(A, -20+Int(rnd() * 41))
Next
' Do zbioru B dodajemy
' 15 losowych elementów
For i = 1 To 15
  s_add(B, -20+Int(rnd() * 41))
Next
' Wyświetlamy je
Print "A:"
s_print(A): Print
Print "SIZE OF A IS"; s_size(A)
Print
Print "B:"
s_print(B): Print
Print "SIZE OF B IS"; s_size(B)
Print
' Suma zbiorów
Print "UNION OF A AND B:"
s_union(A, B, C)
s_print(C): Print
Print "SIZE OF UNION IS"; s_size(C)
Print
' Iloczyn zbiorów
Print "INTERSECTION OF A AND B:"
s_intersection(A, B, C)
s_print(C): Print
Print "SIZE OF INTERSECTION IS"; s_size(C)
Print
' Różnica zbiorów
Print "DIFFERENCE OF A AND B:"
s_difference(A, B, C)
s_print(C): Print
Print "SIZE OF DIFFERENCE IS"; s_size(C)
Print
' Podzbiór
s_union(A, A, C) ' Kopiujemy A do C
For i = 1 To 7 ' Usuwamy 7 elementów
  s_remove(C, -20+Int(Rnd() * 41))
Next
Print "IS:";
s_print(C)
Print " SUBSET OF A?"
If s_subset(C, A) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
s_difference(B, A, C)
For i = 1 To 12 ' Usuwamy 12 elementów
  s_remove(C, -20+Int(Rnd() * 41))
Next
Print "IS:"
s_print(C)
Print " SUBSET OF A?"
If s_subset(C, A) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
' Usuwanie
Print "FROM A WE REMOVE";
For i = 1 To 5
  x = -20+Int(Rnd() * 41)
  Print Using "####"; x;
  s_remove(A, x)
Next
Print
Print "A:"
s_print(A): Print
Print "SIZE OF A IS"; s_size(A)
Print
' Sprawdzamy obecność wybranych
' elementów w B
For i = 1 To 10
  x = -20+Int(Rnd() * 41)
  Print Using "IS ELEMENT#### IN SET B? "; x;
  If s_isin(B, x) = 1 Then
  	 Print "YES"
  Else
  	 Print "NO"
  End If
Next
Print
' Sprawdzenie testu na zbiór pusty
Print "IS SET A EMPTY?"
If s_empty(A) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
Print "IS INTERSECTION OF A ";
Print "AND DIFFERENCE OF B AND A EMPTY?"
s_difference(B, A, C)
s_intersection(A, C, C)
If s_empty(C) = 1 Then
  Print "YES"
Else
  Print "NO"
End If
Print
' Usuwamy tablice dynamiczne w zbiorach
Delete [] A.T
Delete [] B.T
Delete [] C.T
End
Python (dodatek) 
# Zbiory zaimplementowane
# w tablicach haszowanych
# Data: 01.09.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

# Definicja klasy  zbioru
class Set:


    def __init__(self):
        self.vmin = 0
        self.nmax = 0
        self.t = []


# Funkcja znajduje w tablicy haszowanej
# pozycję elementu x
#--------------------------------------
def s_find(a, x):
    # Obliczamy hasz
    i = (x-a.vmin) % (a.nmax+1)
    # Szukamy x
    while (a.t[i] != x) and \
          (a.t[i] >= a.vmin):
        i = (i+1) % (a.nmax+1)
    return i # Zwracamy jego indeks


# Procedura dodaje element x do zbioru A
#---------------------------------------
def s_add(a, x):
    # Wstawiamy x do zbioru
    a.t[s_find(a, x)] = x


# Procedura usuwa element x ze zbioru
#------------------------------------
def s_remove(a,x):
    # Usuwamy x ze zbioru
    a.t[s_find(a, x)] = a.vmin-1


# Procedura usuwa wszystkie
# elementy ze zbioru
#--------------------------
def s_clear(a):
    # Obliczamy pusty element
    v = a.vmin-1
    for i in range(a.nmax+1):
        # Wypełniamy nim tablicę haszowaną
        a.t[i] = v


# Procedura tworzy zbiór
#-----------------------
def s_create(a, v, n):
    # Wypełniamy strukturę danymi
    a.vmin = v
    a.nmax = n-1
    # Tworzymy dynamicznie tablicę haszowaną
    a.t = [0] * n
    s_clear(a) # Tworzymy zbiór pusty


# Procedura wyznacza w C sumę zbiorów A i B
#------------------------------------------
def s_union(a, b, c):
    s_clear(c) # Zerujemy zbiór C
    # Przeglądamy kolejne elementy
    for i in range(a.nmax+1):
        # Dodajemy do C elementy A
        if a.t[i] >= a.vmin:
            s_add(c, a.t[i])
        # Dodajemy do C elementy B
        if b.t[i] >= b.vmin:
            s_add(c, b.t[i])


# Procedura wyznacza część wspólną
# zbiorów A i B
#---------------------------------
def s_intersection(a, b, c):
    s_clear(c) # Zerujemy zbiór C
    # Przeglądamy kolejne elementy A
    for i in range(a.nmax+1):
        if (a.t[i] >= a.vmin) and \
           (b.t[s_find(b, a.t[i])] == a.t[i]):
            # Jeśli element A jest w B,
            # dodajemy go do C
            s_add(c, a.t[i])


# Procedura wyznacza różnicę zbiorów A i B
#-----------------------------------------
def s_difference(a, b, c):
    s_clear(c) # Zerujemy zbiór C
    # Przeglądamy kolejne elementy A
    for i in range(a.nmax+1):
        if (a.t[i] >= a.vmin) and \
           (b.t[s_find(b, a.t[i])] != a.t[i]):
            # Jeśli element A nie jest w B,
            # dodajemy go do C
            s_add(c, a.t[i])


# Funkcja sprawdza, czy zbiór A
# jest podzbiorem zbioru B
# true  - tak, jest
# false - nie, nie jest
#------------------------------
def s_subset(a, b):
    # Przeglądamy kolejne elementy A
    for i in range(a.nmax+1):
        if (a.t[i] >= a.vmin) and \
           (b.t[s_find(b, a.t[i])] != a.t[i]):
            # Jeśli elementu A nie ma w B,
            # kończymy z false
            return False
    return True


# Funkcja oblicza liczbę elementów w A
#-------------------------------------
def s_size(a):
    # Zerujemy licznik
    cnt = 0
    # Przechodzimy przez kolejne komórki
    for i in range(a.nmax+1):
        # Zliczamy komórki z elementami
        if a.t[i] >= a.vmin: cnt += 1
    return cnt


# Funkcja sprawdza, czy zbiór A jest pusty
# true  - tak, jest pusty
# false - nie, nie jest pusty
#-----------------------------------------
def s_empty(a):
    # Testujemy warunek
    return not s_size(a)


# Funkcja bada, czy element x
# należy do zbioru A
# true  - tak, należy
# false - nie, nie należy
#----------------------------
def s_isin(a, x):
    # Testujemy warunek
    return a.t[s_find(a, x)] == x


# Procedura wyświetla elementy zbioru A
#--------------------------------------
def s_print(a):
    for i in range(a.nmax+1):
        if a.t[i] >= a.vmin:
            print("%4d" % a.t[i], end="")


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

a = Set()
b = Set()
c = Set()
# Tworzymy puste zbiory
# o zakresie elementów
# od -20 i o liczebności 30
s_create(a, -20, 30)
s_create(b, -20, 30)
s_create(c, -20, 30)
# Do zbioru A dodajemy
# 10 losowych elementów
for i in range(10):
    s_add(a, random.randrange(-20,21))
# Do zbioru B dodajemy
# 15 losowych elementów
for i in range(15):
    s_add(b, random.randrange(-20,21))
# Wyświetlamy je
print("A:")
s_print(a)
print()
print("SIZE OF A IS",s_size(a))
print()
print("B:")
s_print(b)
print()
print("SIZE OF B IS", s_size(b))
print()
# Suma zbiorów
print("UNION OF A AND B:")
s_union(a, b, c)
s_print(c)
print()
print("SIZE OF UNION IS", s_size(c))
print()
# Iloczyn zbiorów
print("INTERSECTION OF A AND B:")
s_intersection(a, b, c)
s_print(c)
print()
print("SIZE OF INTERSECTION IS", s_size(c))
print()
# Różnica zbiorów
print("DIFFERENCE OF A AND B:")
s_difference(a, b, c)
s_print(c)
print()
print("SIZE OF DIFFERENCE IS", s_size(c))
print()
# Podzbiór
s_union(a, a, c) # Kopiujemy A do C
for i in range(7): # Usuwamy 7 elementów
    s_remove(c, random.randrange(-20,21))
print("IS:",end="")
s_print(c)
print(" SUBSET OF A?")
if s_subset(c, a):
    print("YES")
else:
    print("NO")
print()
s_difference(b, a, c)
for i in range(12): # Usuwamy 12 elementów
    s_remove(c, random.randrange(-20,21))
print("IS:")
s_print(c)
print(" SUBSET OF A?")
if s_subset(c, a):
    print("YES")
else:
    print("NO")
print()
# Usuwanie
print("FROM A WE REMOVE", end="")
for i in range(5):
    x = random.randrange(-20,21)
    print("%4d" % x, end="")
    s_remove(a, x)
print()
print("A:")
s_print(a)
print()
print("SIZE OF A IS", s_size(a))
print()
# Sprawdzamy obecność wybranych
# elementów w B
for i in range(10):
    x = random.randrange(-20,21)
    print("IS ELEMENT%4d IN SET B? " % x, end="")
    if s_isin(b, x):
        print("YES")
    else:
        print("NO")
print()
# Sprawdzenie testu na zbiór pusty
print("IS SET A EMPTY?")
if s_empty(a):
  print("YES")
else:
  print("NO")
print()
print("IS INTERSECTION OF A AND " + \
      "DIFFERENCE OF B AND A EMPTY?")
s_difference(b, a, c)
s_intersection(a, c, c)
if s_empty(c):
  print("YES")
else:
  print("NO")
print()
Wynik: 
11 -15 -13 19 -6 -5 -3 0 1
SIZE OF A IS 9

B:
12 -17 17 -12 -9 -7 -5 -3 1 3 4 8
SIZE OF B IS 12

UNION OF A AND B:
11 12 -17 -15 -13 17 -12 19 -9 -7 -6 -5 -3 0 1 3 4 8
SIZE OF UNION IS 18

INTERSECTION OF A AND B:
-5 -3 1
SIZE OF INTERSECTION IS 3

DIFFERENCE OF A AND B:
11 -15 -13 19 -6 0
SIZE OF DIFFERENCE IS 6

IS:
11 -13 19 -6 -5 0 1 SUBSET OF A?
TRUE

IS:
 -17 17 -12 -9 -7 3 4 SUBSET OF A?
FALSE

FROM A WE REMOVE 2 17 -18 -12 12
A:
11 -15 -13 19 -6 -5 -3 0 1
SIZE OF A IS 9

IS ELEMENT 18 IN SET B? NO
IS ELEMENT -18 IN SET B? NO
IS ELEMENT 7 IN SET B? NO
IS ELEMENT -15 IN SET B? NO
IS ELEMENT 13 IN SET B? NO
IS ELEMENT 15 IN SET B? NO
IS ELEMENT -16 IN SET B? NO
IS ELEMENT -20 IN SET B? NO
IS ELEMENT -8 IN SET B? NO
IS ELEMENT 3 IN SET B? YES

IS SET A EMPTY?
FALSE

IS INTERSECTION OF A AND DIFFERENCE OF B AND A EMPTY?
TRUE

do podrozdziału  do strony 
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2026 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.