Reprezentacja zbiorów w mapach bitowych


Tematy pokrewne
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
Mapa bitowa (ang. bitmap) jest ciągiem bitów. Poszczególne bity w mapie bitowej posiadają swoje numery. Umówmy się, że bity będziemy zawsze numerować od strony prawej do lewej. Numeracja rozpoczyna się od 0. Poniżej mamy mapę bitową zbudowaną z 26 bitów:

 

b25 b24 b23 b22 b21 b20 b19 b18 b17 b16 b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0

 

Każdy bit mapy może przyjąć wartość 0 lub 1.

Zbiór da się odwzorować mapą bitową. Stosujemy tutaj podobną umowę, jak przy tablicach:

b25 b24 b23 b22 b21 b20 b19 b18 b17 b16 b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0
0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1

 

Jeśli nasza mapa bitowa odwzorowuje zbiór elementów o wartościach od 0 do 25 (wartość elementu odpowiada numerowi bitu), to w zbiorze znajdują się elementy: 20, 19, 14, 5 i 0.

Z mapami bitowymi wiąże się pewien prosty problem. Otóż w tablicy mogliśmy się odwołać bezpośrednio do elementu zbioru za pomocą indeksu. Tutaj jest nieco gorzej (a może lepiej?), ponieważ bity mapy są przechowywane w komórkach pamięci grupami po 8:

 

bajt nr 3 bajt nr 2 bajt nr 1 bajt nr 0
b31 b30 b29 b28 b27 b26 b25 b24 b23 b22 b21 b20 b19 b18 b17 b16 b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0

 

W bajcie nr 3 wykorzystujemy tylko dwa bity: b24 i b25. Pozostałe nie należą do mapy bitowej, jednak i tak muszą być zarezerwowane w pamięci.

Umówmy się, że najmniejszą jednostką przydziału pamięci dla mapy bitowej będzie 4 bajty, czyli 32 bity. Taka organizacja jest podyktowana większą szybkością pracy na danych 32 bitowych niż na 8 bitowych we współczesnych mikroprocesorach (w jednym rozkazie procesor może naraz przetworzyć 32 bity, czyli 32 elementy zbioru!). Również dostęp do danych 32 bitowych jest szybszy w procesorach Pentium od dostępu do danych 8 bitowych. Zatem mapę bitową będziemy przechowywali w tablicy, której elementy są 32 bitowe.

Do określenia mapy bitowej będziemy potrzebowali dwóch wielkości całkowitych:

 

vmin  –  minimalna wartość elementu zbioru
vmax  –  maksymalna wartość elementu zbioru

 

Liczbę bitów obliczymy ze wzoru:

 

liczba_bitów = vmax - vmin + 1

 

Liczbę komórek 32 bitowych obliczymy ze wzoru:

 

n = ((liczba_bitów - 1) shr 5) + 1

 

Ta ostatnia informacja będzie potrzebna dla operacji blokowych na zbiorach (suma, iloczyn, różnica, podzbiór).

Aby znaleźć bit odpowiadający elementowi o wartości v, wykonujemy następujące operacje:

 

Najpierw przekształcamy wartość v na numer bitu:

 

numer_bitu = v - vmin

 

Teraz wyznaczamy indeks komórki tablicy, która zawiera dany bit (dzielenie jest całkowitoliczbowe):

 

indeks = numer_bitu shr 5

 

Na koniec obliczamy numer bitu w komórce (wydzielając młodsze 5 bitów):

 

nb = numer_bitu and 31

 

Jeśli mamy indeks komórki tablicy mapy bitowej oraz numer bitu nb wewnątrz tej komórki, to wartość elementu zbioru skojarzonego z tym bitem obliczymy następująco:

 

Obliczamy numer bitu w mapie bitowej:

 

numer_bitu = (indeks shl 5) or nb

 

Obliczamy wartość elementu zbioru:

 

v = numer_bitu + vmin

 

Powyższe wzory pozwalają nam obsługiwać pojedyncze elementy zbioru. Mając wartość elementu, potrafimy określić numer reprezentującego go bitu, a dalej położenie tego bitu w tablicy mapy bitowej. Również na odwrót, mając położenie bitu w tablicy, potrafimy określić element, który ten bit reprezentuje w zbiorze.

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

 

vmin dolna granica wartości elementów, vmin C
nmax ostatni indeks komórki tablicy, nmax C
T tablica elementów 32 bitowych o rozmiarze nmax + 1

 

Lazarus Code::Blocks Free Basic
type
  s_set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of cardinal;
  end;
struct s_set
{
  int vmin,nmax;
  unsigned int * T;
};
Type s_set
  vmin As Integer
  nmax As Integer
  T As UInteger Ptr
End Type

 

Poniżej przedstawiamy algorytmy podstawowych operacji dla zbioru zaimplementowanego mapą bitową.

 

Algorytmy operacji dla zbiorów reprezentowanych mapami bitowymi

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

 

Algorytm ustawia na 1 bit reprezentujący w mapie bitowej element zbioru o wartości v.

Wejście
A  –  referencja do struktury s_set
x  –  element do dodania do zbioru, x C
Wyjście:
Zbiór A z dodanym elementem x.
Elementy pomocnicze:
b  –  numer bitu w mapie bitowej, b C
i  –  indeks elementu tablicy mapy bitowej, i C
Lista kroków:
K01: bx - A.vmin ; obliczamy numer bitu
K02: ib shr 5 ; obliczamy indeks
K03: A.T[i] ← A.T[i] or (1 shl (b and 31)) ; ustawiamy bit na 1
K04: Zakończ  

 

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

Algorytm ustawia na 0 bit reprezentujący w mapie bitowej element zbioru o wartości v.

Wejście
A  –  referencja do struktury s_set
x  –  element do usunięcia ze zbioru, x C
Wyjście:
Zbiór A z usuniętym elementem x.
Elementy pomocnicze:
b  –  numer bitu w mapie bitowej, b C
i  –  indeks elementu tablicy mapy bitowej, i C
Lista kroków:
K01: bx - A.vmin ; obliczamy numer bitu
K02: ib shr 5 ; obliczamy indeks
K03: A.T[i] ← A.T[i] and not (1 shl (b and 31)) ; ustawiamy bit na 0
K04: Zakończ  
 

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

 

Algorytm wypełnia tablicę T zerami. 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
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 nmax i wypełnia ją wartością 0, co daje w efekcie pusty zbiór A.

Wejście
A  –  referencja do struktury s_set
vmin  –  minimalna wartość elementu zbioru, vmin C
vmax  –  maksymalna wartość elementu zbioru, vmax C
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.nmax ← (vmax - vmin) shr 5 ; obliczamy indeks ostatniego elementu tablicy
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. Wszystkie trzy zbiory muszą mieć ten sam rozmiar nmax.

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 K02  
K02:    C.T[i] ← A.T[i] or B.T[i] ; łączymy zbiory A i B w zbiór C
K03: Zakończ  

 

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

 

Algorytm tworzy w zbiorze C iloczyn zbiorów A i B. Wszystkie trzy zbiory muszą mieć ten sam rozmiar nmax.

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 K02  
K02:    C.T[i] ← A.T[i] and B.T[i] ; wyznaczamy w C część wspólną A i B
K03: Zakończ  

 

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

Algorytm tworzy w zbiorze C różnicę zbiorów A i B. Wszystkie trzy zbiory muszą mieć ten sam rozmiar nmax.

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 K02  
K02:    C.T[i] ← A.T[i] and not B.T[i] ; wyznaczamy w C różnicę A i B
K03: Zakończ  

 

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

Algorytm sprawdza, czy iloczyn logiczny A i B jest równy A. Jeśli tak, to zbiór B zawiera zbiór A. Oba zbiory A i B muszą posiadać ten sam rozmiar nmax.

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 K02  
K02:     Jeśli (A.T[i] and B.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
m  –  maska bitowa, m symbol N
Lista kroków:
K01: c ← 0 ; zerujemy licznik
K02: Dla i = 0,1,..., A.nmax, wykonuj: ; zliczamy komórki z elementami
K03:     mA.T[i] ; zapamiętujemy w m bity komórki A.T[i]
K04:     Dopóki m > 0, wykonuj K05...K06 ; pomijamy puste komórki
K05:         Jeśli (m and 1) = 1, to cc + 1 ; zliczamy bity o wartości 1
K06:         mm shr 1 ; przesuwamy bity o 1 pozycję w prawo
K07: Zakończ z wynikiem c  

 

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

 

Algorytm sumuje logicznie wszystkie komórki tablicy T. Jeśli suma 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:
i  –  indeksowanie komórek, i symbol C
m  –  maska bitowa, m symbol N
Lista kroków:
K01: mA.T[0] ; ustawiamy bity w masce
K02: Dla i = 1,2,...,A.nmax wykonuj:
    mm or A.T[i]

; sumujemy bity
K03: Jeśli m = 0, zakończ z wynikiem true
inaczej zakończ z wynikiem false
 

 

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

 

Algorytm wyszukuje bit, który reprezentuje w zbiorze wartość x. Jeśli bit ma stan 1, to zwraca true, w przeciwnym razie zwraca false.

Wejście
A  –  referencja do struktury s_set
x  –  element badany na obecność w zbiorze, x C
Wyjście:
true  –  element x jest w zbiorze A
false  –  elementu x nie ma w zbiorze A
Elementy pomocnicze:
b  –  numer bitu w mapie bitowej, b C
Lista kroków:
K01: bx - A.vmin ; obliczamy numer bitu
K02: Jeśli A.T[b shr 5] and (1 shl (b and 31)) > 0, to
    zakończ z wynikiem true
Inaczej zakończ z wynikiem false
; badamy stan bitu

 

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 bitmapach. Wyjaśnienie wykonywanych operacji znajduje się w komentarzach wewnątrz programu.

 

Lazarus
// Zbiory zaimplementowane w mapach bitowych
// Data   : 30.06.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------------------

program sets;

// Definicja struktury zbioru

type
  s_set =  record
    vmin  : integer;
    nmax  : integer;
    T     : array of cardinal;
  end;

// Procedura dodaje element x do zbioru A
//---------------------------------------
procedure s_add(var A : s_set; x : integer);
var
  b,i : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu
  i := b shr 5;                   // Obliczamy indeks
  A.T[i] := A.T[i] or (1 shl (b and 31)); // Ustawiamy bit na 1
end;

// Procedura usuwa element x ze zbioru
//------------------------------------
procedure s_remove(var A : s_set; x : integer);
var
  b,i : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu
  i := b shr 5;                   // Obliczamy indeks
  A.T[i] := A.T[i] and not (1 shl (b and 31)); // Ustawiamy bit na 0
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 zbiór
//-----------------------
procedure s_create(var A : s_set; vmin,vmax : integer);
begin
  A.vmin := vmin;                 // Wypełniamy strukturę danymi
  A.nmax := (vmax - vmin) shr 5;  // Indeks ostatniego elementu tablicy
  SetLength(A.T,A.nmax + 1);      // Tworzymy dynamicznie tablicę mapy bitowej
  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
  for i := 0 to A.nmax do  C.T[i] := A.T[i] or B.T[i];
end;

// Procedura wyznacza część wspólną zbiorów A i B
//-----------------------------------------------
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 wyznacza różnicę zbiorów A i B
//-----------------------------------------------
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;

// 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 tablicy
    if (A.T[i] and B.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;
  m   : cardinal;
begin
  c := 0;                         // Zerujemy licznik
  for i := 0 to A.nmax do         // Przechodzimy przez kolejne komórki
  begin
    m := A.T[i];                  // Pobieramy bity do m
    while m > 0 do                // Zliczamy bity równe 1
    begin
      if (m and 1) = 1 then inc(c);
      m := m shr 1;
    end;
  end;
  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;
var
  i : integer;
  m : cardinal;
begin
  m := A.T[0];                    // Pobieramy bity do m
  for i := 1 to A.nmax do
    m := m or A.T[i];             // Sumujemy logicznie bity
  s_empty := (m = 0);
end;

// Funkcja bada, czy element x należy do zbioru A
// true  - tak, należy
// false - nie, nie należy
//-----------------------------------------------
function s_isin(var A : s_set; x : integer) : boolean;
var
  b : integer;
begin
  b := x - A.vmin;                // Obliczamy numer bitu w mapie bitowej
  if A.T[b shr 5] and (1 shl (b and 31)) > 0 then Exit(true);
  s_isin := false;
end;

// Procedura wyświetla elementy zbioru A
//--------------------------------------
procedure s_print(var A : s_set);
var
  i,nb : integer;
  m : cardinal;
begin
  for i := 0 to A.nmax do
  begin
    nb := 0;
    m  := A.T[i];
    while m > 0 do
    begin
      if (m and 1) = 1 then write((i shl 5) + nb + A.vmin,' ');
      m := m shr 1;
      inc(nb);
    end
  end;
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 do 20

  s_create(A,-20,20);
  s_create(B,-20,20);
  s_create(C,-20,20);

  // 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,' ');
    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 mapach bitowych
// Data   : 1.07.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;
  unsigned int *T;
};

// Procedura dodaje element x do zbioru A
//---------------------------------------
void s_add(s_set & A, int x)
{
  int b = x - A.vmin;             // Obliczamy numer bitu
  int i = b >> 5;                 // Obliczamy indeks
  A.T[i] |= 1 << (b & 31);        // Ustawiamy bit na 1
}

// Procedura usuwa element x ze zbioru
//------------------------------------
void s_remove(s_set & A, int x)
{
  int b = x - A.vmin;             // Obliczamy numer bitu
  int i = b >> 5;                 // Obliczamy indeks
  A.T[i] &= ~(1 << (b & 31));     // Ustawiamy bit na 0
}

// 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 mapę bitową
}

// Procedura tworzy zbiór
//-----------------------
void s_create(s_set & A, int vmin, int vmax)
{
  A.vmin = vmin;                  // Wypełniamy strukturę danymi
  A.nmax = (vmax - vmin) >> 5;    // Indeks ostatniego elementu tablicy
  A.T = new unsigned int [A.nmax + 1];  // Tworzymy dynamicznie tablicę mapy bitowej
  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)
{
  for(int i = 0; i <= A.nmax; i++) C.T[i] = A.T[i] | B.T[i];
}

// Procedura wyznacza część wspólną zbiorów A i B
//-----------------------------------------------
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 wyznacza różnicę zbiorów A i B
//-----------------------------------------------
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];
}

// 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 tablicy
    if((A.T[i] & B.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
    for(unsigned int m = A.T[i]; m; m >>= 1)
      if((m & 1) == 1) c++;       // Zliczamy bity równe 1
  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)
{
  unsigned int m = A.T[0];        // Pobieramy bity do m
  for(int i = 1; i <= A.nmax; i++) m |= A.T[i]; // Sumujemy logicznie bity
  return (m == 0);
}

// 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)
{
  int b = x - A.vmin;             // Obliczamy numer bitu w mapie bitowej
  if(A.T[b >> 5] & (1 << (b & 31))) return true;
  return false;
}

// Procedura wyświetla elementy zbioru A
//--------------------------------------
void s_print(s_set A)
{
  int nb;
  unsigned int m;

  for(int i = 0; i <= A.nmax; i++)
    for(nb = 0,m = A.T[i]; m; m >>= 1,nb++)
      if(m & 1) cout << (i << 5) + nb + 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 -20 do 20 i liczebności 30

  s_create(A,-20,20);
  s_create(B,-20,20);
  s_create(C,-20,20);

  // 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 << 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 mapach bitowych
' Data   : 01.06.2014
' (C)2014 mgr Jerzy Wałaszek
'------------------------------------------

' Definicja struktury zbioru

Type s_set
  vmin As Integer
  nmax As Integer
  T As UInteger Ptr
End Type

' Procedura dodaje element x do zbioru A
'---------------------------------------
Sub s_add(ByRef A As s_set, ByVal x As Integer)
  Dim As Integer b,i

  b = x - A.vmin                  ' Obliczamy numer bitu
  i = b Shr 5                     ' Obliczamy indeks
  A.T[i] = A.T[i] or (1 Shl (b and 31)) ' Ustawiamy bit na 1
End Sub

' Procedura usuwa element x ze zbioru
'------------------------------------
Sub s_remove(ByRef A As s_set, ByVal x As Integer)
  Dim As Integer b,i

  b = x - A.vmin                  ' Obliczamy numer bitu
  i = b Shr 5                     ' Obliczamy indeks
  A.T[i] = A.T[i] And Not (1 Shl (b and 31)) ' Ustawiamy bit na 0
End Sub

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

' Procedura tworzy zbiór
'-----------------------
Sub s_create(ByRef A As s_set, ByVal vmin As Integer, ByVal vmax As Integer)
  A.vmin = vmin                   ' Wypełniamy strukturę danymi
  A.nmax = (vmax - vmin) shr 5    ' Indeks ostatniego elementu tablicy
  A.T = New UInteger [A.nmax + 1] ' Tworzymy dynamicznie tablicę mapy bitowej
  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

  For i = 0 To A.nmax
  	 C.T[i] = A.T[i] Or B.T[i]
  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

  For i = 0 To A.nmax
  	 C.T[i] = A.T[i] And B.T[i]
  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

  For i = 0 To A.nmax
  	 C.T[i] = A.T[i] And Not B.T[i]
  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
    If (A.T[i] And B.T[i]) <> A.T[i] Then Return 0 ' Jeśli elementu A nie ma w B, kończymy z false
  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
  Dim As UInteger m
  For i = 0 To A.nmax
    m = A.T[i]
    While m
      If (m And 1) = 1 Then c += 1 ' Zliczamy bity równe 1
      m shr= 1
    Wend
  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
  Dim As Integer i
  Dim As UInteger m = A.T[0]      ' Pobieramy bity do m
  For i = 1 To A.nmax
  	 m Or= A.T[i]                  ' Sumujemy logicznie bity
  Next
  If m = 0 Then Return 1
  Return 0
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
  Dim As Integer b = x - A.vmin   ' Obliczamy numer bitu w mapie bitowej
  If A.T[b Shr 5] And (1 Shl (b And 31)) Then Return 1
  Return 0
End Function

' Procedura wyświetla elementy zbioru A
'--------------------------------------
Sub s_print(ByRef A As s_set)
  Dim As Integer nb,i
  Dim As UInteger m

  For i = 0 To A.nmax
    nb = 0
    m = A.T[i]
    While m
      If (m And 1) = 1 Then Print Using "& ";(i Shl 5) + nb + A.vmin;
      m shr= 1
      nb += 1
    Wend
  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
-17 -15 -11 -7 -6 -3 -2 7 14 15
SIZE OF A IS 10

B:
-18 -17 -14 -13 -12 -9 -7 -5 -1 6 7 10 16 18
SIZE OF B IS 14

UNION OF A AND B:
-18 -17 -15 -14 -13 -12 -11 -9 -7 -6 -5 -3 -2 -1 6 7 10 14 15 16 18
SIZE OF UNION IS 21

INTERSECTION OF A AND B:
-17 -7 7
SIZE OF INTERSECTION IS 3

DIFFERENCE OF A AND B:
-15 -11 -6 -3 -2 14 15
SIZE OF DIFFERENCE IS 7

IS:
-17 -15 -11 -7 -6 -3 14 15 SUBSET OF A?
TRUE

IS:
-13 -9 -5 -1 6 16 18 SUBSET OF A?
FALSE

FROM A WE REMOVE 12 18 -8 -3 -14
A:
-17 -15 -11 -7 -6 -2 7 14 15
SIZE OF A IS 9

IS ELEMENT  -3 IN SET B? NO
IS ELEMENT  15 IN SET B? NO
IS ELEMENT  13 IN SET B? NO
IS ELEMENT -20 IN SET B? NO
IS ELEMENT  13 IN SET B? NO
IS ELEMENT  -7 IN SET B? YES
IS ELEMENT -17 IN SET B? YES
IS ELEMENT   5 IN SET B? NO
IS ELEMENT  19 IN SET B? NO
IS ELEMENT  11 IN SET B? NO

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