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

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

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ę s_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
  s_set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of byte;
  end;
   C++
struct s_set
{
  int vmin, nmax;
  char * T;
};
   Basic
Type s_set
  vmin As Integer
  nmax As Integer
  T As Byte Ptr
End Type

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ę T zerami, co w efekcie tworzy pusty zbiór.

Wejście:

A  –  referencja do struktury s_set

Wyjście:

Pusty zbiór A
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC

Lista kroków:

K01: Dla i  = 0, 1, ..., A.nmax:
wykonuj
: A.T [ i  ] ← 0
zerujemy komórki tablicy
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 s_set
vmin  –  minimalna wartość elementu zbioru
vmax  –  maksymalna wartość elementu zbioru

Wyjście:

Pusty zbiór A
Zmienne pomocnicze:
s_clear ( Z  )  –  usuwa ze zbioru Z wszystkie elementy

Lista kroków:

K01: A.vmin  ← vmin wypełniamy strukturę s_set odpowiednimi wartościami
K02: A.nmax  ← vmax  - vmin wyznaczamy ostatni indeks
K03: Utwórz obszar dla nmax  + 1 komórek tworzymy tablicę dynamiczną
K04: A.T  ← adres utworzonego obszaru  
K05: s_clear ( A  ) zerujemy komórki tablicy
K06: 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 s_set

Wyjście:

Zbiór C zawiera sumę zbiorów A i B.
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC

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 s_set

Wyjście:

Zbiór C zawiera iloczyn zbiorów A i B.
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC

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 s_set

Wyjście:

Zbiór C zawiera różnicę zbiorów A i B.
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC

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 s_set

Wyjście:

Zbiór C zawiera dopełnienie zbioru A.
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC

Lista kroków:

K01: Dla i  = 0, 1, ..., A.nmax :
wykonuj:
    C.T [ i  ] = negacja bitu 0 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 s_set

Wyjście:

true  –  zbiór A  jest podzbiorem zbioru B
false  –  zbiór A  nie jest podzbiorem zbioru B
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC

Lista kroków:

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

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

Algorytm sumuje poszczególne komórki tablicy T i zwraca tę sumę jako wynik.

Wejście:

A  –  referencja do struktury s_set

Wyjście:

Liczba elementów w A
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC
s  –  suma komórek, sC

Lista kroków:

K01: s  ← 0 zerujemy sumę
K02: Dla i  = 0, 1, ..., A.nmax,
wykonuj
: s  ← s  + A.T [ i  ]
sumujemy komórki
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 s_set

Wyjście:

true  –  zbiór A  jest pusty
false  –  zbiór A  nie jest pusty
Zmienne 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 T.

Wejście:

A  –  referencja do struktury s_set
x  –  element do dodania do zbioru, xC

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 s_set
x  –  element do usunięcia ze zbioru, xC

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 s_set
x  –  sprawdzany element, xC

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,
to zakończ z wynikiem true
sprawdzamy obecność elementu
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śnienie wykonywanych operacji znajduje 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
  s_set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of byte;
  end;

// Procedura usuwa wszystkie elementy ze zbioru
//---------------------------------------------
procedure s_clear ( var A : s_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 : s_set; vmin, vmax : integer );
begin
  A.vmin := vmin;                 // Wypełniamy strukturę A
  A.nmax := vmax - vmin;
  SetLength ( A.T, A.nmax + 1 );      // Tworzymy tablicę dynamiczną na elementy
  s_clear ( A );                     // Zbiór zerujemy
end;

// Procedura oblicza sumę zbiorów A i B.
// Wynik umieszcza w zbiorze C
//--------------------------------------
procedure s_union ( var A, B, C : s_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 : s_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 : s_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 : s_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 : s_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 : s_set ) : integer;
var
  i, s : integer;
begin
  s := 0;                         // Zerujemy sumę
  for i := 0 to A.nmax do s := s + A.T [ i ]; // Sumujemy komórki
  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 : s_set ) : boolean;
begin
  s_empty := s_size ( A ) = 0;
end;

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

// Procedura usuwa ze zbioru element
//----------------------------------
procedure s_remove ( var A : s_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 : s_set; x : integer ) : boolean;
begin
  s_isin := A.T [ x - A.vmin ] + 1;
end;

// Procedura wyświetla zawartość zbioru
//-------------------------------------
procedure s_print ( var A : s_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 : s_set;
  i, x   : integer;

begin
  randomize;               // Inicjujemy generator pseudolosowy

  // 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 15 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

  s_union ( A, A, C );                 // Kopiujemy A do C
  for i := 1 to 7 do              // Usuwamy 7 elementów
    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 );
  for i := 1 to 12 do              // Usuwamy 12 elementów
    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;

  // Sprawdzenie testu 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 s_set
{
    int vmin, nmax;
    char * T;
};

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

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

// Procedura oblicza sumę zbiorów A i B.
// Wynik umieszcza w zbiorze C
//--------------------------------------
void s_union ( s_set & A, s_set & B, s_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 ( s_set & A, s_set & B, s_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 ( s_set & A, s_set & B, s_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 ( s_set & A, s_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 ( s_set & A, s_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 ( s_set & A )
{
  int s = 0;

  for( int i = 0; i <= A.nmax; i++ ) s = 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 ( s_set & A )
{
  return !s_size ( A );
}

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

// Procedura usuwa ze zbioru element
//----------------------------------
void s_remove ( s_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 ( s_set & A, int x )
{
  return A.T [ x - A.vmin ];
}

// Procedura wyświetla zawartość zbioru
//-------------------------------------
void s_print ( s_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( )
{
  s_set A, B, C;
  int i, x;

  srand ( time ( NULL ) );              // Inicjujemy generator pseudolosowy

  // 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 < 15; 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 << "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

  s_union ( A, A, C );              // Kopiujemy A do C
  for( i = 0; i < 7; i++ )          // Usuwamy 7 elementów
    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 );
  for( int i = 0; i < 12; i++ )     // Usuwamy 12 elementów
    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 << 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 s_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 s_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 s_set, ByVal vmin As Integer, ByVal vmax As integer )
  A.vmin = vmin                   ' Wypełniamy strukturę A
  A.nmax = vmax - vmin
  A.T = New Byte [ A.nmax + 1 ]   ' Tworzymy tablicę dynamiczną na elementy
  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 s_set, ByRef B As s_set, ByRef C As s_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 s_set, ByRef B As s_set, ByRef C As s_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 s_set, ByRef B As s_set, ByRef C As s_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 s_set, ByRef C As s_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 s_set, ByRef B As s_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 s_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 s_set ) As Integer
  Return ( s_size ( A ) = 0 ) And 1
End Function

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

' Procedura usuwa ze zbioru element
'----------------------------------
sub s_remove ( ByRef A As s_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 s_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 s_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 s_set A, B, C
Dim As Integer i, x

Randomize                         ' Inicjujemy generator pseudolosowy

' 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 15
  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
Wynik:
A = -3 -1  4  5  8 10 17 18 20
SIZE OF A IS 9

B = -2 -1  3  4  6  8 10 13 14 15 20
SIZE OF B IS 11

UNION OF A AND B IS -3 -2 -1  3  4  5  6  8 10 13 14 15 17 18 20
SIZE OF UNION IS 15

INTERSECTION OF A AND B IS -1  4  8 10 20
SIZE OF INTERSECTION IS 5

DIFFERENCE OF A AND B IS -3  5 17 18
SIZE OF DIFFERENCE IS 4

COMPLEMENT OF A IS -5 -4 -2  0  1  2  3  6  7  9 11 12 13 14 15 16 19
SIZE OF COMPLEMENT IS 17

IS -1  5  8 10 17 18 20 SUBSET OF A?
TRUE

IS -4 -3  2  5  7 11 16 19 SUBSET OF A?
FALSE

FROM A WE REMOVE 10 14  1  5 19
A = -3 -1  4  8 17 18 20
SIZE OF A IS 7

IS ELEMENT  0 IN SET B? NO
IS ELEMENT 12 IN SET B? NO
IS ELEMENT  9 IN SET B? NO
IS ELEMENT 14 IN SET B? YES
IS ELEMENT  0 IN SET B? NO
IS ELEMENT 18 IN SET B? NO
IS ELEMENT  5 IN SET B? NO
IS ELEMENT  8 IN SET B? YES
IS ELEMENT -2 IN SET B? YES
IS ELEMENT 14 IN SET B? YES

IS SET A EMPTY?
FALSE

IS INTERSECTION OF A AND COMPLEMENT OF A EMPTY?
TRUE
Na początek:  podrozdziału   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ę s_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
  s_set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of typ;
  end;
   C++
struct s_set
{
  int vmin, nmax;
  typ * T;
};
   Basic
Type s_set
  vmin As Integer
  nmax As Integer
  T As Typ Ptr
End Type

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 pozycję x.

Algorytm oblicza hasz wartości x  i zapamiętuje go w zmiennej i. Następnie w pętli sprawdza zawartość komórki 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 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 s_set
x  –  wartość poszukiwanego elementu

Wyjście:

Pozycja elementu x  w tablicy A.T.
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC

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 T odpowiadającą elementowi x i umieszcza go w niej.

Wejście:

A  –  referencja do struktury s_set
x  –  element do dodania do zbioru

Wyjście:

Zbiór A z dodanym elementem x.
Zmienne 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ńcz  

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

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

Wejście:

A  –  referencja do struktury s_set
x  –  element do dodania do zbioru

Wyjście:

Zbiór A z usuniętym elementem x.
Zmienne pomocnicze:
s_find ( Z, x )  –  znajduje indeks odpowiadający wartości elementu x

Lista kroków:

K01: A.T [ sfind ( 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ę T wartościami vmin - 1. W ten sposób powstanie zbiór pusty.

Wejście:

A  –  referencja do struktury s_set

Wyjście:

Pusty zbiór A
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC
v  –  zawartość pustej komórki

Lista kroków:

K01: v  ← A.vmin  - 1  
K02: Dla i  = 0, 1, ..., A.nmax :
wykonuj A.T [ i  ] ← v
zerujemy komórki tablicy
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 nmax  i wypełnia ją wartością vmin  - 1, co daje w efekcie pusty zbiór A.

Wejście:

A  –  referencja do struktury s_set
vmin  –  minimalna wartość elementu zbioru
nmax  –  maksymalna liczba elementów w zbiorze

Wyjście:

Pusty zbiór A
Zmienne pomocnicze:
s_clear ( Z  )  –  usuwa ze zbioru Z wszystkie elementy

Lista kroków:

K01: A.vmin  ← vmin wypełniamy strukturę s_set odpowiednimi wartościami
K02: A.nmax  ← nmax  - 1  
K03: Utwórz obszar dla 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  –  referencja do struktur s_set

Wyjście:

Zbiór C zawiera sumę zbiorów A i B.
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC
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,
    to s_add ( C, A.T [ i  ] )
elementy zbioru A dodajemy do zbioru C
K04:     Jeśli B.T [ i  ] ≥ B.vmin,
    to s_add ( C, B.T [ i  ] )
elementy zbioru B dodajemy do zbioru C
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  –  referencja do struktur s_set

Wyjście:

Zbiór C zawiera iloczyn zbiorów A i B.
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC
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  –  referencja do struktur s_set

Wyjście:

Zbiór C zawiera różnicę zbiorów A i B.
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC
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 s_set

Wyjście:

true  –  zbiór A jest podzbiorem zbioru B
false  –  zbiór A nie jest podzbiorem zbioru B
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC
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 s_set

Wyjście:

Liczba elementów w A
Zmienne pomocnicze:
i  –  indeksowanie komórek, iC
c  –  licznik komórek, cC

Lista kroków:

K01: c  ← 0 zerujemy licznik
K02: Dla i  = 0, 1, ..., A.nmax,
wykonuj:
    Jeśli A.T [ i  ] ≥ A.vmin,
    to  c  ← c + 1
zliczamy komórki z elementami
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 s_set

Wyjście:

true  –  zbiór A  jest pusty
false  –  zbiór A  nie jest pusty
Zmienne 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 s_set
x  –  sprawdzany element, xC

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,
to zakończ z wynikiem true
sprawdzamy obecność elementu
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
  s_set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of integer;
  end;

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

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

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

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

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

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

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

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

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

// Funkcja oblicza liczbę elementów w A
//-------------------------------------
function s_size ( var A : s_set ) : integer;
var
  i, c : integer;
begin
  c := 0;                         // Zerujemy licznik
  for i := 0 to A.nmax do         // Przechodzimy przez kolejne komórki
    if A.T [ i ] >= A.vmin then inc ( c ); // Zliczamy komórki z elementami
  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 : s_set ) : boolean;
begin
  s_empty := ( s_size ( A ) = 0 );     // Testujemy warunek
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 : s_set; x : integer ) : boolean;
begin
  s_isin := ( A.T [ s_find ( A, x ) ] = x ); // Testujemy warunek
end;

// Procedura wyświetla elementy zbioru A
//--------------------------------------
procedure s_print ( var A : s_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 : s_set;
  i, x   : integer;

begin
  randomize;                      // Inicjujemy generator pseudolosowy

  // 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 );
  for i := 1 to 12 do     // Usuwamy 12 elementów
    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 s_set
{
  int vmin, nmax, *T;
};

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

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

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

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

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

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

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

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

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

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

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

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

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

// Procedura wyświetla elementy zbioru A
//--------------------------------------
void s_print ( s_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( )
{
  s_set A, B, C;
  int i, x;

  srand ( time ( NULL ) );              // Inicjujemy generator pseudolosowy

  // 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

  s_union ( A, A, C );     // Kopiujemy A do C
  for( i = 0; i < 7; i++ ) // Usuwamy 7 elementów
    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 );
  for( i = 0; i < 12; i++ ) // Usuwamy 12 elementów
    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 s_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 s_set, ByVal x As Integer ) As Integer
  Dim As Integer i = ( x - A.vmin ) Mod ( A.nmax + 1 )  ' Obliczamy hasz
  while( A.T [ i ] <> x ) AndAlso ( A.T [ i ] >= A.vmin ) ' Szukamy x
    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 s_set, ByVal x As Integer )
  A.T [ s_find ( A, x ) ] = x            ' Wstawiamy x do zbioru
End Sub

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

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

' Procedura tworzy zbiór
'-----------------------
Sub s_create ( ByRef A As s_set, ByVal vmin As Integer, ByVal nmax As Integer )
  A.vmin = vmin                   ' Wypełniamy strukturę danymi
  A.nmax = nmax - 1
  A.T = New Integer [ nmax ]      ' Tworzymy dynamicznie tablicę haszowaną
  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 s_set, ByRef B As s_set, ByRef C As s_set )
  Dim As Integer i

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

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

' Procedura wyznacza różnicę zbiorów A i B
'-----------------------------------------------
Sub s_difference ( ByRef A As s_set, ByRef B As s_set, ByRef C As s_set )
  Dim As Integer i
  s_clear ( c )                   ' Zerujemy zbiór C
  For i = 0 To A.nmax             ' Przeglądamy kolejne elementy A
    if( A.T [ i ] >= A.vmin ) AndAlso ( B.T [ s_find ( B, A.T [ i ] ) ] <> A.T [ i ] ) Then
      s_add ( C, A.T [ i ] )      ' Jeśli element A nie jest w B, dodajemy go do C
    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 s_set, ByRef B As s_set ) As Integer
  Dim As Integer i
  For i = 0 To A.nmax             ' Przeglądamy kolejne elementy A
    if( A.T [ i ] >= A.vmin ) AndAlso ( B.T [ s_find ( B, A.T [ i ] ) ] <> A.T [ i ] ) Then
      Return 0                    ' Jeśli elementu A nie ma w B, kończymy z false
    End If
  Next
  Return 1
End Function

' Funkcja oblicza liczbę elementów w A
'-------------------------------------
Function s_size ( ByRef A As s_set ) As Integer
  Dim As Integer i, c = 0         ' Zerujemy licznik
  For i = 0 To A.nmax             ' Przechodzimy przez kolejne komórki
    If A.T [ i ] >= A.vmin Then c += 1 ' Zliczamy komórki z elementami
  Next
  Return c
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 s_set ) As Integer
  Return ( s_size ( A ) = 0 ) And 1    ' Testujemy warunek
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 s_set, ByVal x As Integer ) As Integer
  Return ( A.T [ s_find ( A, x ) ] = x ) And 1 ' Testujemy warunek
End Function

' Procedura wyświetla elementy zbioru A
'--------------------------------------
Sub s_print ( ByRef A As s_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 s_set A, B, C
Dim As Integer i, x

Randomize                         ' Inicjujemy generator pseudolosowy

' 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 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
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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 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.