Reprezentacja zbiorów w tablicach


Tematy pokrewne   Podrozdziały
Zbiory
Podstawowe pojęcia dotyczące zbiorów
Reprezentacja zbiorów na listach
Reprezentacja zbiorów w tablicach
Reprezentacja zbiorów w mapach bitowych
Reprezentacja zbiorów w drzewach binarnych

Podstawowe operacje na tablicach
Haszowanie
Operacje na listach jednokierunkowych
Haszowanie z wykorzystaniem list jednokierunkowych

  Implementacja zbioru w tablicy dynamicznej
Implementacja zbioru w tablicy haszowanej

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

 

Lazarus Code::Blocks Free Basic
type
  s_set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of byte;
  end;
struct s_set
{
  int vmin,nmax;
  char * T;
};
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
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol C
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
Elementy pomocnicze:
s_clear(Z)  –  usuwa ze zbioru Z wszystkie elementy
Lista kroków:
K01: A.vminvmin ; wypełniamy strukturę s_set odpowiednimi wartościami
K02: A.nmaxvmax - 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.
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol 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 s_set
Wyjście:
Zbiór C zawiera iloczyn zbiorów A i B.
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol 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 s_set
Wyjście:
Zbiór C zawiera różnicę zbiorów A i B.
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol 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 s_set
Wyjście:
Zbiór C zawiera dopełnienie zbioru A.
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol C
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
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol C
Lista kroków:
K01: Dla i = 0,1,...,A.nmax wykonuj:
    Jeśli (A.T[i] = 1) (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
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol C
s  –  suma komórek, s symbol C
Lista kroków:
K01: s ← 0 ; zerujemy sumę
K02: Dla i = 0,1,..., A.nmax wykonuj:
    ss + 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
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 T.

Wejście
A  –  referencja do struktury s_set
x  –  element do dodania do zbioru, x symbol 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 s_set
x  –  element do usunięcia ze zbioru, x symbol 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 s_set
x  –  sprawdzany element, x symbol 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, to zakończ z wynikiem true ; sprawdzamy obecność elementu
K02: Zakończ z wynikiem false  

 

Program

Ważne:

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.

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 

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

 

Lazarus Code::Blocks Free Basic
type
  s_set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of typ;
  end;
struct s_set
{
  int vmin,nmax;
  typ * T;
};
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.
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol C
Lista kroków:
K01: i ← (x - A.vmin) mod (A.nmax + 1) ; obliczamy hasz
K02: Dopóki (A.T[i] ≠ x) (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.
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ń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.
Elementy 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
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol C
v  –  zawartość pustej komórki
Lista kroków:
K01: vA.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
Elementy pomocnicze:
s_clear(Z)  –  usuwa ze zbioru Z wszystkie elementy
Lista kroków:
K01: A.vminvmin ; wypełniamy strukturę s_set odpowiednimi wartościami
K02: A.nmaxnmax - 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.
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol 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 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.
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol 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 K03  
K03:     Jeśli (A.T[i] A.vmin) (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.
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol 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 K03  
K03:     Jeśli (A.T[i] A.vmin) (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
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol C
s_find(Z,x)  –  znajduje indeks elementu x w zbiorze Z
Lista kroków:
K01: Dla i = 0,1,...,A.nmax, wykonuj K02  
K02:     Jeśli (A.T[i] A.vmin) (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
Elementy pomocnicze:
i  –  indeksowanie komórek, i symbol C
c  –  licznik komórek, c symbol C
Lista kroków:
K01: c ← 0 ; zerujemy licznik
K02: Dla i = 0,1,..., A.nmax, wykonuj:
    Jeśli A.T[i] A.vmin, to  cc + 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
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 s_set
x  –  sprawdzany element, x symbol 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, to zakończ z wynikiem true ; sprawdzamy obecność elementu
K02: Zakończ z wynikiem false  

 

Program

Ważne:

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.

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2018 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe