Algorytmy i Struktury Danych - Reprezentacja zbiorów w mapach bitowych

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:

b₂₅

b₂₄

b₂₃

b₂₂

b₂₁

b₂₀

b₁₉

b₁₈

b₁₇

b₁₆

b₁₅

b₁₄

b₁₃

b₁₂

b₁₁

b₁₀

b₉

b₈

b₇

b₆

b₅

b₄

b₃

b₂

b₁

b₀

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:

wartości v elementów zbioru są liczbami całkowitymi z przedziału od vmin do vmax.
element v zbioru jest odwzorowany bitem o numerze ( v - vmin).
element v jest w zbiorze, jeśli jego bit b_v-vmin = 1.
elementu v nie ma w zbiorze, jeśli jego bit b_v-vmin = 0.

b₂₅	b₂₄	b₂₃	b₂₂	b₂₁	b₂₀	b₁₉	b₁₈	b₁₇	b₁₆	b₁₅	b₁₄	b₁₃	b₁₂	b₁₁	b₁₀	b₉	b₈	b₇	b₆	b₅	b₄	b₃	b₂	b₁	b₀
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
b₃₁	b₃₀	b₂₉	b₂₈	b₂₇	b₂₆	b₂₅	b₂₄	b₂₃	b₂₂	b₂₁	b₂₀	b₁₉	b₁₈	b₁₇	b₁₆	b₁₅	b₁₄	b₁₃	b₁₂	b₁₁	b₁₀	b₉	b₈	b₇	b₆	b₅	b₄	b₃	b₂	b₁	b₀

W bajcie nr 3 wykorzystujemy tylko dwa bity: b₂₄ i b₂₅. 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

Pascal

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

C++

struct s_set
{
  int vmin, nmax;
  unsigned int * T;
};

Basic

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.

Zmienne pomocnicze:

b	:	numer bitu w mapie bitowej, b ∈ C
i	:	indeks elementu tablicy mapy bitowej, i ∈ C

Lista kroków:

K01:	b ← x - A.vmin	obliczamy numer bitu
K02:	i ← b 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.

Zmienne pomocnicze:

b	:	numer bitu w mapie bitowej, b ∈ C
i	:	indeks elementu tablicy mapy bitowej, i ∈ C

Lista kroków:

K01:	b ← x - A.vmin	obliczamy numer bitu
K02:	i ← b 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:

referencja do struktury s_set

Wyjście:

Pusty zbiór A

Zmienne pomocnicze:

indeksowanie komórek, i symbol

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

Zmienne pomocnicze:

s_clear (Z)

usuwa ze zbioru Z wszystkie elementy

Lista kroków:

K01:	A.vmin ← vmin	wypełniamy strukturę s_set odpowiednimi wartościami
K02:	A.nmax ← (vmax - vmin) 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.

Zmienne pomocnicze:

indeksowanie komórek, i ∈ C

Lista kroków:

K01:	Dla i = 0, 1, …, A.nmax: wykonuj krok 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.

Zmienne pomocnicze:

indeksowanie komórek, i ∈ C

Lista kroków:

K01:	Dla i = 0, 1, …, A.nmax: wykonuj krok 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.

Zmienne pomocnicze:

indeksowanie komórek, i ∈ C

Lista kroków:

K01:	Dla i = 0, 1, …, A.nmax: wykonuj krok 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

Zmienne pomocnicze:

indeksowanie komórek, i ∈ C

Lista kroków:

K01:	Dla i = 0, 1, …, A.nmax: wykonuj krok 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:

referencja do struktury s_set

Wyjście:

Liczba elementów w A

Zmienne pomocnicze:

i	:	indeksowanie komórek, i ∈ C
c	:	licznik komórek, c ∈ C
m	:	maska bitowa, m ∈ N

Lista kroków:

K01:	c ← 0	zerujemy licznik
K02:	Dla i = 0, 1, …, A.nmax, wykonuj kroki K03…K06	zliczamy komórki z elementami
K03:	m ← A.T [i]	zapamiętujemy w m bity komórki A.T [i]
K04:	Dopóki m > 0, wykonuj kroki K05…K06	pomijamy puste komórki
K05:	Jeśli (m and 1) = 1, to c ← c + 1	zliczamy bity o wartości 1
K06:	m ← m 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:

referencja do struktury s_set

Wyjście:

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

Zmienne pomocnicze:

i	:	indeksowanie komórek, i ∈ C
m	:	maska bitowa, m ∈ N

Lista kroków:

K01:	m ← A.T [0]	ustawiamy bity w masce
K02:	Dla i = 1, 2, …, A.nmax: wykonuj: m ← m or A.T [i]	; sumujemy bity
K03:	Jeśli m = 0, to 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

Zmienne pomocnicze:

numer bitu w mapie bitowej, b ∈ C

Lista kroków:

K01:	b ← x - 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

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program testuje wszystkie funkcje obsługi zbiorów opartych na bitmapach. Wyjaśnienie wykonywanych operacji znajduje się w komentarzach wewnątrz programu.

Pascal

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

C++

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

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

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

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

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Reprezentacja zbiorów w mapach bitowych

Rozwiązanie

Algorytmy operacji dla zbiorów reprezentowanych mapami bitowymi

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

Wejście:

Wyjście:

Zmienne pomocnicze:

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

Wejście:

Wyjście:

Zmienne pomocnicze:

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

Wejście:

Wyjście:

Zmienne pomocnicze:

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

Wejście:

Wyjście:

Zmienne pomocnicze:

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

Wejście:

Wyjście:

Zmienne pomocnicze:

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

Wejście:

Wyjście:

Zmienne pomocnicze:

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

Wejście:

Wyjście:

Zmienne pomocnicze:

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

Wejście:

Wyjście:

Zmienne pomocnicze:

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

Wejście:

Wyjście:

Zmienne pomocnicze:

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

Wejście:

Wyjście:

Zmienne pomocnicze:

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

Wejście:

Wyjście:

Zmienne pomocnicze:

Przykładowe programy