Reprezentacja zbiorów na listach


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

Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych

Lista jednokierunkowa jest używana do przechowywania elementów zbioru. Na liście elementy są umieszczone w dowolnej kolejności. Każdy element może pojawić się na liście tylko jeden raz. Reprezentacja listowa oszczędza pamięć, jednak jest bardzo nieefektywna. Podajemy ją jedynie dla celów dydaktycznych.

 

Algorytmy operacji dla zbiorów reprezentowanych listami jednokierunkowymi

s_isin(A,x) – zwraca true, jeśli element o wartości x znajduje się na liście A. Inaczej zwraca false.

 

Algorytm przegląda listę A i jeśli znajdzie na niej element o wartości x, zwraca true. W przeciwnym razie zwraca false

Wejście
A  –  wskaźnik początku listy jednokierunkowej
x  –  wartość poszukiwanego elementu
Wyjście:
true  –  element x jest na liście A.
false  –  elementu x nie ma na liście A
Elementy pomocnicze:
p  –  wskaźnik elementów listy jednokierunkowej
Lista kroków:
K02 pA  
K03 Dopóki p ≠ nil wykonuj K04...K09 ; przeglądamy listę A
K04:     Jeśli (pdata) = x, to zakończ z wynikiem true ; jeśli trafimy na element o wartości x, kończymy
K05:     p ← (pnext) ; następny element listy A
K06: Zakończ z wynikiem false ; lista nie zawiera elementu o wartości x

 

s_add(A,x) – dodaje element x do listy A, jeśli jeszcze gol tam nie ma.
 

Algorytm najpierw sprawdza, czy lista A zawiera element x. Jeśli tak, to kończy działanie. Jeśli nie, to wstawia nowy element o wartości x na początku listy.

Wejście
A  –  referencja do wskaźnika początku listy jednokierunkowej
x  –  wartość dodawanego elementu
Wyjście:
Lista A z elementem o wartości x na początku, jeśli wcześniej elementu o takiej wartości na liście A nie było. W przeciwnym razie lista A nie jest modyfikowana.
Elementy pomocnicze:
p  –  wskaźnik elementów listy jednokierunkowej
s_isin(Z,x)  –  funkcja zwraca true, jeśli lista Z zawiera element o wartości x, inaczej zwraca false
Lista kroków:
K01: Jeśli s_isin(A,x) = true, to zakończ ; sprawdzamy, czy lista A zawiera x. Jeśli tak, kończymy
K02: Utwórz nowy element listy ; dodajemy element na początek listy A
K03: p ← adres nowego elementu  
K04: (pdata) ← x  
K05: (pnext) ← A  
K06: A ← p  
K07: Zakończ  
 

s_union(A,B,C) – zwraca listę zawierającą elementy list A i B. Elementy na liście wynikowej nie są dublowane.

 

Algorytm najpierw kopiuje do listy C wszystkie elementy listy A. Następnie przegląda kolejno elementy listy B i sprawdza, czy znajdują się one na liście A. Jeśli nie, to kopiuje te elementy do listy C. W efekcie lista C będzie zawierała wszystkie elementy A oraz wszystkie elementy B, które nie są równe elementom z A.

Wejście
A,B  –  wskaźniki początków list jednokierunkowych
C  –  referencja do wskaźnika początku listy jednokierunkowej. Wskaźnik C nie może wskazywać żadnej listy.
Wyjście:
Lista C zawiera elementy list A i B.
Elementy pomocnicze:
p  –  wskaźnik elementów listy jednokierunkowej
s_isin(Z,x)  –  funkcja zwraca true, jeśli lista Z zawiera element o wartości x, inaczej zwraca false
s_add(Z,x)  –  dodaje element x do listy Z, jeśli lista Z jeszcze nie zawiera elementu o wartości x.
Lista kroków:
K01: C ← nil ; tworzymy pustą listę wynikową
K02 pA  
K03 Dopóki p ≠ nil, wykonuj K04...K05 ; kopiujemy listę A do C
K04:     s_add(C,(pdata)) ; kopiujemy element z A do C
K05:     p ← (pnext) ; następny element listy A
K06: pB ; teraz zajmiemy się listą B
K07: Dopóki p ≠ nil, wykonuj K08...K09  
K08:     Jeśli s_isin(A,(pdata)) = false, to s_add(C,(pdata)) ; jeśli lista A nie zawiera elementu z B, to element z B kopiujemy do C
K09:     p ← (pnext) ; następny element listy B
K10: Zakończ  

 

s_intersection(A,B,C) – zwraca listę zawierającą elementy, które znajdują się jednocześnie na liście A i na liście B.
 

Algorytm przegląda kolejne elementy listy A i sprawdza, czy znajdują się one na liście B. Jeśli tak, to elementy są kopiowane do listy C. W efekcie lista C będzie zawierała wszystkie elementy listy A, które są równe elementom listy B.

Wejście
A,B  –  wskaźniki początków list jednokierunkowych
C  –  referencja do wskaźnika początku listy jednokierunkowej. Wskaźnik C nie może wskazywać żadnej listy.
Wyjście:
Lista C zawiera te elementy listy A, które są jednocześnie elementami listy B.
Elementy pomocnicze:
p  –  wskaźnik elementów listy jednokierunkowej
s_isin(Z,x)  –  funkcja zwraca true, jeśli lista Z zawiera element o wartości x, inaczej zwraca false
s_add(Z,x)  –  dodaje element x do listy Z, jeśli lista Z jeszcze nie zawiera elementu o wartości x.
Lista kroków:
K01: C ← nil ; tworzymy pustą listę wynikową
K02: pA  
K03: Dopóki p ≠ nil, wykonuj K04...K05 ; przeglądamy listę A
K04:     Jeśli s_isin(B,(pdata)) = true, to s_add(C,(pdata)) ; sprawdzamy, czy lista B zawiera element z A. Jeśli tak, kopiujemy
K05:     p ← (pnext) ; następny element listy A
K06: Zakończ  

 

s_difference(A,B,C) – zwraca listę zawierającą wszystkie elementy listy A, które nie są równe elementom listy B.
 

Algorytm przegląda kolejne elementy listy A i sprawdza, czy znajdują się one na liście B. Jeśli nie, to elementy są kopiowane do listy C. W efekcie lista C będzie zawierała wszystkie elementy listy A, które są różne od elementów listy B.

Wejście
A,B  –  wskaźniki początków list jednokierunkowych
C  –  referencja do wskaźnika początku listy jednokierunkowej. Wskaźnik C nie może wskazywać żadnej listy.
Wyjście:
Lista C zawierająca elementy listy A, które nie są elementami listy B.
Elementy pomocnicze:
p  –  wskaźnik elementów listy jednokierunkowej
s_isin(Z,x)  –  funkcja zwraca true, jeśli lista Z zawiera element o wartości x, inaczej zwraca false
s_add(Z,x)  –  dodaje element x do listy Z, jeśli lista Z jeszcze nie zawiera elementu o wartości x.
Lista kroków:
K01: C ← nil ; tworzymy pustą listę wynikową
K02: pA  
K03: Dopóki p ≠ nil, wykonuj K04...K05 ; przeglądamy listę A
K04:     Jeśli s_isin(B,(pdata)) = false, to s_add(C,(pdata)) ; jeśli lista B nie zawiera elementu z A, kopiujemy
K05:     p ← (pnext) ; następny element listy A
K06: Zakończ z wynikiem C  

 

s_subset(A,B) – zwraca true, jeśli lista B zawiera wszystkie elementy listy A,  inaczej zwraca false.

 

Algorytm przegląda kolejne elementy listy A i sprawdza, czy znajdują się one na liście B. Jeśli nie, to zwraca wartość false. W przeciwnym razie zwraca true.

Wejście
A,B  –  wskaźniki początków list jednokierunkowych
Wyjście:
true  –  lista B posiada wszystkie elementy listy A.
false  –  lista B nie posiada wszystkich elementów listy A
Elementy pomocnicze:
p  –  wskaźnik elementów listy jednokierunkowej
s_isin(Z,x)  –  funkcja zwraca true, jeśli lista Z zawiera element o wartości x, inaczej zwraca false
Lista kroków:
K01: pA ; będziemy przeglądać listę A
K02: Dopóki p ≠ nil, wykonuj K03...K04  
K03:     Jeśli s_isin(B,(pdata)) = false, to zakończ z wynikiem false ; sprawdzamy, czy lista B zawiera element z A. Jeśli nie, kończymy
K04:     p ← (pnext) ; następny element z listy A
K05: Zakończ z wynikiem true  
 

s_size(A) – zwraca liczbę elementów na liście A

 

Algorytm przechodzi przez listę A zliczając kolejne elementy.

Wejście
A  –  wskaźnik początku listy jednokierunkowej
Wyjście:
Liczba elementów na liście A
Elementy pomocnicze:
p  –  wskaźnik elementów listy jednokierunkowej
c  –  licznik elementów
Lista kroków:
K01: pA ; będziemy przeglądać listę A
K02: c ← 0 ; zerujemy licznik
K03: Dopóki p ≠ nil, wykonuj K03...K06  
K04:     cc + 1 ; zwiększamy licznik
K05:     p ← (pnext) ; następny element listy A
K06: Zakończ z wynikiem c  

 

s_remove(A,x) – usuwa element x z listy A, jeśli się tam znajduje

 

Algorytm sprawdza, czy lista jest pusta. Jeśli tak, to kończy. W przeciwnym razie sprawdza, czy poszukiwany element jest na początku listy. Jeśli tak, to go usuwa i modyfikuje odpowiednio wskazanie A. W przeciwnym razie szuka elementu na liście, utrzymując zawsze adres elementu poprzedzającego. Gdy znajdzie element, usuwa go z listy przez zmodyfikowanie elementu poprzedzającego, a następnie element usuwa z pamięci.

Wejście
A  –  referencja do wskaźnika początku listy jednokierunkowej
x  –  wartość usuwanego elementu
Wyjście:
Lista A z usuniętym elementem o wartości x.
Elementy pomocnicze:
p, r  –  wskaźniki elementów listy jednokierunkowej
Lista kroków:
K01: Jeśli A = nil, to zakończ ; lista jest pusta, kończymy
K02: pA ; zapamiętujemy adres początku listy
K03: Jeśli (pdata) ≠ x, to idź do K07 ; sprawdzamy, czy usuwany element jest pierwszym na liście
K04: A ← (pnext) ; element usuwamy z listy
K05: Usuń element wskazywany przez p ; i z pamięci
K06: Zakończ  
K07: Dopóki ((pnext) ≠ nil) ((pnextdata) ≠ x) wykonuj:
    p ← (pnext)
; szukamy na liście A następnika równego x
K08: Jeśli (pnext) = nil, to zakończ ; nie ma następnika równego x, kończymy
K09: r  ← (pnext) ; zapamiętujemy adres następnika
K10: (pnext) ← (rnext) ; następnik usuwamy z listy
K11: Usuń element wskazywany przez r ; i z pamięci
K12: Zakończ  

 

s_clear(A) – usuwa wszystkie elementy z listy A.
 

Algorytm usuwa kolejne elementy listy, aż lista stanie się pusta.

Wejście
A  –  referencja do wskaźnika początku listy jednokierunkowej
Wyjście:
Pusta lista A..
Elementy pomocnicze:
p, r  –  wskaźniki elementów listy jednokierunkowej
Lista kroków:
K01: p ← A ; ustawiamy p na początek listy A
K02: Dopóki p ≠ nil, wykonuj K03...K05 ; przechodzimy przez kolejne elementy listy
K03:     rp ; zapamiętujemy adres elementu
K04:     p ← (pnext) ; w p ustawiamy adres następnika
K05:     Usuń element wskazywany przez r  
K06: A ← nil ; lista A staje się pusta
K07: Zakończ  

 

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

 

Lazarus
// Zbiory zaimplementowane na listach jednokierunkowych
// Data   : 20.06.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------------

program sets;

// Definicja elementu listy jednokierunkowej
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;              // Następny element listy
    data : integer;               // Wartość elementu listy
  end;

// Definicje funkcji obsługi list jako zbiorów
//--------------------------------------------

// Funkcja sprawdza, czy x jest elementem zbioru A
// true  - jest
// false - nie jest
//------------------------------------------------
function s_isin(p : PslistEl; x : integer) : boolean;
begin
  while p <> nil do               // Przeglądamy kolejne elementy A
  begin
    if p^.data = x then Exit(true);
    p := p^.next;
  end;
  s_isin := false;
end;

// Procedura dodaje na początek zbioru A element x,
// jeśli zbiór A nie zawiera jeszcze takiego elementu.
//----------------------------------------------------
procedure s_add(var A : PslistEl; x : integer);
var
  p : PslistEl;
begin
  if not s_isin(A,x) then         // Jeśli elementu x nie ma w zbiorze A,
  begin                           // to go tam wstawiamy
    new(p);                       // Tworzymy nowy element listy
    p^.data := x;                 // Wprowadzamy do niego dane
    p^.next := A;                 // Umieszczamy go na początku zbioru
    A := p;
  end;
end;

// Procedura dokonuje połączenia zbiorów A i B. Wynik jest umieszczany w C
//------------------------------------------------------------------------
procedure s_union(A,B : PslistEl; var C : PslistEl);
var
  p : PslistEl;
begin

  C := nil;                       // Zerujemy zbiór wyjściowy

  p := A;                         // Zbiór A kopiujemy do C
  while p <> nil do
  begin
    s_add(C,p^.data);             // Kopiujemy element z A do C
    p := p^.next;                 // Następny element z A
  end;

  p := B;
  while p <> nil do
  begin
    if not s_isin(A,p^.data) then // Teraz będziemy kopiować do C te elementy z B,
      s_add(C,p^.data);           // których nie ma w A, aby ich nie zdublować
    p := p^.next;                 // Następny element z B
  end;
end;

// Procedura wyznacza część wspólną zbiorów A i B. Wynik w C
//----------------------------------------------------------
procedure s_intersection(p,B : PslistEl; var C : PslistEl);
begin
  C := nil;                       // Zerujemy zbiór C

  while p <> nil do               // Przeglądamy kolejne elementy zbioru A
  begin
    if s_isin(B,p^.data) then  s_add(C,p^.data);   // Jeśli element jest w B, kopiujemy
    p := p^.next;                 // Następny element z A
  end;
end;

// Procedura wyznacza różnicę zbiorów A i B. Wynik w C
//----------------------------------------------------------
procedure s_difference(p,B : PslistEl; var C : PslistEl);
begin
  C := nil;                       // Zerujemy zbiór C

  while p <> nil do               // Przeglądamy kolejne elementy zbioru A
  begin
    if not s_isin(B,p^.data) then  s_add(C,p^.data);   // Jeśli elementu nie ma w B, kopiujemy
    p := p^.next;                 // Następny element z A
  end;
end;

// Funkcja sprawdza, czy zbiór B zawiera podzbiór A
// true  - tak
// false - nie
//-------------------------------------------------
function s_subset(p,B : PslistEl) : boolean;
begin
  while p <> nil do               // Przeglądamy zbiór A
  begin
    if not s_isin(B,p^.data) then Exit(false); // Jeśli elementu z A nie ma w B, kończymy
    p := p^.next;                 // Następny element z A
  end;
  s_subset := true;               // Wszystkie elementy A są w B
end;

// Funkcja oblicza liczebność zbioru
//----------------------------------
function s_size(p : PslistEl) : integer;
var
  c : integer;
begin
  c := 0;                         // Zerujemy licznik
  while p <> nil do               // Przechodzimy przez elementy zbioru A
  begin
    inc(c);                       // Elementy zliczamy w c
    p := p^.next;                 // Następny element z A
  end;
  s_size := c;
end;

// Procedura usuwa element x ze zbioru
//------------------------------------
procedure s_remove(var A : PslistEl; x : integer);
var
  p,r : PslistEl;
begin
  if A <> nil then                // Zbiór nie może być pusty
  begin
    p := A;                       // Zapamiętujemy adres początku zbioru
    if p^.data = x then           // Jeśli usuwany element jest na początku,
    begin
      A := p^.next;               // to go usuwamy z listy
      dispose(p);                 // oraz z pamięci
    end
    else
    begin
      while (p^.next <> nil) and (p^.next^.data <> x) do
        p := p^.next;             // Szukamy elementu x
      if p^.next <> nil then      // Jeśli go znajdziemy, to
      begin
        r := p^.next;             // zapamiętujemy jego adres,
        p^.next := r^.next;       // usuwamy go z listy
        dispose(r);               // oraz z pamięci
      end;
    end;
  end;
end;

// Procedura usuwa zawartość zbioru
//---------------------------------
procedure s_clear(var A : PslistEl);
var
  p,r : PslistEl;
begin
  p := A;                         // Przechodzimy przez kolejne elementy zbioru A
  while p <> nil do
  begin
    r := p;                       // Zapamiętujemy adres bieżącego elementu
    p := p^.next;                 // p ustawiamy na następnik
    dispose(r);                   // Element usuwamy z pamięci
  end;
  A := nil;                       // Zbiór staje się pusty
end;

// Procedura wyświetla zawartość zbioru
//------------------------------------
procedure s_print(p : PslistEl);
begin
  while p <> nil do
  begin
    write(p^.data:3);
    p := p^.next;
  end;
end;

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

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

begin
  randomize;                      // Inicjujemy generator pseudolosowy
  A := nil;                       // Zerujemy zbiory
  B := nil;

  // Tworzymy dwa zbiory o przypadkowych elementach

  for i := 1 to 10 do s_add(A,random(20));
  for i := 1 to 15 do s_add(B,random(20));

  // 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));
  s_clear(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));
  s_clear(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));
  s_clear(C);

  // Podzbiór

  writeln;
  write('IS');
  s_print(A^.next^.next^.next);
  writeln(' SUBSET OF A?');
  writeln(s_subset(A^.next^.next^.next,A));

  writeln;
  write('IS');
  s_print(A^.next^.next^.next);
  writeln(' SUBSET OF B?');
  writeln(s_subset(A^.next^.next^.next,B));

  // Usuwanie

  writeln;
  write('FROM A WE REMOVE');
  for i := 1 to 4 do
  begin
    x := random(20);
    write(x:3);
    s_remove(A,x);
  end;
  writeln;
  write('A = '); s_print(A); writeln;
  writeln('SIZE OF A IS ',s_size(A));
  writeln;

  // Usuwamy wszystkie zbiory

  s_clear(A);
  s_clear(B);
  s_clear(C);

end.
Code::Blocks
// Zbiory zaimplementowane na listach jednokierunkowych
// Data   : 20.06.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------------------------------

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

using namespace std;

// Definicja elementu listy jednokierunkowej

struct slistEl
{
  slistEl * next;                 // Następny element listy
  int data;                       // Wartość elementu listy
};

// Definicje funkcji obsługi list jako zbiorów
//--------------------------------------------

// Funkcja sprawdza, czy x jest elementem zbioru A
// true  - jest
// false - nie jest
//------------------------------------------------
bool s_isin(slistEl * p, int x)
{
  while(p)                        // Przeglądamy kolejne elementy A
  {
    if(p->data == x) return true;
    p = p->next;
  }
  return false;
};

// Procedura dodaje na początek zbioru A element x,
// jeśli zbiór A nie zawiera jeszcze takiego elementu.
//----------------------------------------------------
void s_add(slistEl * & A, int x)
{
  slistEl * p;

  if(! s_isin(A,x))               // Jeśli elementu x nie ma w zbiorze A,
  {                               // to go tam wstawiamy
    p = new slistEl;              // Tworzymy nowy element listy
    p->data = x;                  // Wprowadzamy do niego dane
    p->next = A;                  // Umieszczamy go na początku zbioru
    A = p;
  }
}

// Procedura dokonuje połączenia zbiorów A i B. Wynik jest umieszczany w C
//------------------------------------------------------------------------
void s_union(slistEl * A, slistEl * B, slistEl * & C)
{
  slistEl * p;

  C = NULL;                       // Zerujemy zbiór wyjściowy

  for(p = A; p; p = p->next)      // Zbiór A kopiujemy do C
    s_add(C,p->data);             // Kopiujemy element z A do C

  for(p = B; p; p = p->next)
    if(! s_isin(A,p->data))       // Teraz będziemy kopiować do C te elementy z B,
      s_add(C,p->data);           // których nie ma w A, aby ich nie zdublować

}

// Procedura wyznacza część wspólną zbiorów A i B. Wynik w C
//----------------------------------------------------------
void s_intersection(slistEl * p, slistEl * B, slistEl * & C)
{
  C = NULL;                       // Zerujemy zbiór C

  while(p)                        // Przeglądamy kolejne elementy zbioru A
  {
    if(s_isin(B,p->data))  s_add(C,p->data); // Jeśli element jest w B, kopiujemy
    p = p->next;                  // Następny element z A
  }
}

// Procedura wyznacza różnicę zbiorów A i B. Wynik w C
//----------------------------------------------------------
void s_difference(slistEl * p, slistEl * B, slistEl * & C)
{
  C = NULL;                       // Zerujemy zbiór C

  while(p)                        // Przeglądamy kolejne elementy zbioru A
  {
    if(! s_isin(B,p->data))  s_add(C,p->data); // Jeśli elementu nie ma w B, kopiujemy
    p = p->next;                 // Następny element z A
  }
}

// Funkcja sprawdza, czy zbiór B zawiera podzbiór A
// true  - tak
// false - nie
//-------------------------------------------------
bool s_subset(slistEl * p, slistEl * B)
{
  while(p)                        // Przeglądamy zbiór A
  {
    if(! s_isin(B,p->data)) return false; // Jeśli elementu z A nie ma w B, kończymy
    p = p->next;                  // Następny element z A
  }
  return true;                    // Wszystkie elementy A są w B
}

// Funkcja oblicza liczebność zbioru
//----------------------------------
int s_size(slistEl * p)
{
  int c = 0;                      // Zerujemy licznik

  while(p)                        // Przechodzimy przez elementy zbioru A
  {
    c++;                          // Elementy zliczamy w c
    p = p->next;                  // Następny element z A
  }
  return c;
}

// Procedura usuwa element x ze zbioru
//------------------------------------
void s_remove(slistEl * & A, int x)
{
  slistEl * p, * r;

  if(A)                           // Zbiór nie może być pusty
  {
    p = A;                        // Zapamiętujemy adres początku zbioru
    if(p->data == x)              // Jeśli usuwany element jest na początku,
    {
      A = p->next;                // to go usuwamy z listy
      delete p;                   // oraz z pamięci
    }
    else
    {
      while(p->next && (p->next->data != x))
        p = p->next;              // Szukamy elementu x
      if(p->next)                 // Jeśli go znajdziemy, to
      {
        r = p->next;              // zapamiętujemy jego adres,
        p->next = r->next;        // usuwamy go z listy
        delete r;                 // oraz z pamięci
      }
    }
  }
}

// Procedura usuwa zawartość zbioru
//---------------------------------
void s_clear(slistEl *  & A)
{
  slistEl * p, *r;

  p = A;                          // Przechodzimy przez kolejne elementy zbioru A
  while(p)
  {
    r = p;                        // Zapamiętujemy adres bieżącego elementu
    p = p->next;                  // p ustawiamy na następnik
    delete r;                     // Element usuwamy z pamięci
  }
  A = NULL;                       // Zbiór staje się pusty
}

// Procedura wyświetla zawartość zbioru
//------------------------------------
void s_print(slistEl * p)
{
  while(p)
  {
    cout << setw(3) << p->data;
    p = p->next;
  }
}

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

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

  srand(time(NULL));              // Inicjujemy generator pseudolosowy
  A = B = NULL;                   // Zerujemy zbiory

  // Tworzymy dwa zbiory o przypadkowych elementach

  for(i = 0; i < 10; i++) s_add(A,rand() % 20);
  for(i = 0; i < 15; i++) s_add(B,rand() % 20);

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

  cout << "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;
  s_clear(C);

  // Iloczyn zbiorów

  cout << "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;
  s_clear(C);

  // Różnica zbiorów

  cout << "DIFFERENCE OF A AND B IS";
  s_difference(A,B,C);
  s_print(C);
  cout << endl << "SIZE OF DIFFERENCE IS " << s_size(C) << endl << endl;
  s_clear(C);

  // Podzbiór

  cout << "IS";
  s_print(A->next->next->next);
  cout << " SUBSET OF A?" << endl
       << (s_subset(A->next->next->next,A)?"TRUE":"FALSE") << endl << endl;

  cout << "IS";
  s_print(A->next->next->next);
  cout << " SUBSET OF B?" << endl
       << (s_subset(A->next->next->next,B)?"TRUE":"FALSE") << endl << endl;

  // Usuwanie

  cout << "FROM A WE REMOVE";
  for(i = 0; i < 4; i++)
  {
    x = rand() % 20;
    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;

  // Usuwamy wszystkie zbiory

  s_clear(A);
  s_clear(B);
  s_clear(C);

  return 0;
}
Free Basic
' Zbiory zaimplementowane na listach jednokierunkowych
' Data   : 20.06.2014
' (C)2014 mgr Jerzy Wałaszek
'----------------------------------------------------

' Definicja elementu listy jednokierunkowej

Type slistEl
  Next As slistEl Ptr             ' Następny element listy
  Data As Integer                 ' Wartość elementu listy
End Type

' Definicje funkcji obsługi list jako zbiorów
'--------------------------------------------

' Funkcja sprawdza, czy x jest elementem zbioru A
' true  - jest
' false - nie jest
'------------------------------------------------
Function s_isin(ByVal p As slistEl Ptr, ByVal x As integer) As Integer
  While p                         ' Przeglądamy kolejne elementy A
    If p->data = x Then Return 1
    p = p->Next
  Wend
  return 0
End Function

' Procedura dodaje na początek zbioru A element x,
' jeśli zbiór A nie zawiera jeszcze takiego elementu.
'----------------------------------------------------
Sub s_add(byref A As slistEl Ptr, byval x As Integer)
  
  Dim As slistEl Ptr p

  If s_isin(A,x) = 0 Then         ' Jeśli elementu x nie ma w zbiorze A, to go wstawiamy do C
    p = new slistEl               ' Tworzymy nowy element listy
    p->data = x                   ' Wprowadzamy do niego dane
    p->next = A                   ' Umieszczamy go na początku zbioru
    A = p
  End If
End Sub

' Procedura dokonuje połączenia zbiorów A i B. Wynik jest umieszczany w C
'------------------------------------------------------------------------
Sub s_union(ByVal A As slistEl Ptr, ByVal B As slistEl Ptr, ByRef C  As slistEl Ptr)

  Dim  As slistEl Ptr p

  C = 0                           ' Zerujemy zbiór wyjściowy

  p = A
  While p
    s_add(C,p->data)              ' Kopiujemy element z A do C
    p = p->Next                   ' Następny element z A
  Wend
  
  p = B
  While p
    If s_isin(A,p->data) = 0 Then s_add(C,p->data) ' kopiujemy element, którego nie ma w A
    p = p->Next                   ' Następny element z B
  Wend
End Sub

' Procedura wyznacza część wspólną zbiorów A i B. Wynik w C
'----------------------------------------------------------
Sub s_intersection(ByVal p As slistEl Ptr, ByVal B As slistEl Ptr, ByRef C  As slistEl Ptr)

  C = 0                           ' Zerujemy zbiór C

  While p                         ' Przeglądamy kolejne elementy zbioru A
    If s_isin(B,p->Data) = 1 Then s_add(C,p->data) ' Jeśli element jest w B, kopiujemy
    p = p->Next                   ' Następny element z A
  Wend
End Sub

' Procedura wyznacza różnicę zbiorów A i B. Wynik w C
'----------------------------------------------------------
Sub s_difference(ByVal p As slistEl Ptr, ByVal B As slistEl Ptr, ByRef C  As slistEl Ptr)

  C = 0                           ' Zerujemy zbiór C

  While p                         ' Przeglądamy kolejne elementy zbioru A
    If s_isin(B,p->data) = 0 Then  s_add(C,p->data) ' Jeśli elementu nie ma w B, kopiujemy
    p = p->Next                   ' Następny element z A
  Wend
End Sub

' Funkcja sprawdza, czy zbiór B zawiera podzbiór A
' 1 - tak
' 0 - nie
'-------------------------------------------------
Function s_subset(ByVal p As slistEl Ptr, byval B As slistEl Ptr) As Integer 

  while p                         ' Przeglądamy zbiór A
    If s_isin(B,p->data) = 0 Then Return 0 ' Jeśli elementu z A nie ma w B, kończymy
    p = p->Next                   ' Następny element z A
  Wend
  Return 1                        ' Wszystkie elementy A są w B
End Function

' Funkcja oblicza liczebność zbioru
'----------------------------------
Function s_size(ByVal p As slistEl Ptr) As Integer

  Dim As Integer c = 0            ' Zerujemy licznik

  While p                         ' Przechodzimy przez elementy zbioru A
    c += 1                        ' Elementy zliczamy w c
    p = p->Next                   ' Następny element z A
  Wend 
  Return c
End Function

' Procedura usuwa element x ze zbioru
'------------------------------------
Sub s_remove(byref A As slistEl Ptr, ByVal x As integer)

  Dim As slistEl Ptr p, r

  If A Then                       ' Zbiór nie może być pusty
    p = A                         ' Zapamiętujemy adres początku zbioru
    If p->data = x Then           ' Jeśli usuwany element jest na początku,
      A = p->Next                 ' to go usuwamy z listy
      delete p                    ' oraz z pamięci
    Else
      While (p->Next <> 0) AndAlso (p->next->data <> x)
        p = p->Next               ' Szukamy elementu x
      Wend
      If p->Next Then             ' Jeśli go znajdziemy, to
        r = p->Next               ' zapamiętujemy jego adres,
        p->next = r->Next         ' usuwamy go z listy
        delete r                  ' oraz z pamięci
      End If
    End If
  End If
End Sub

' Procedura usuwa zawartość zbioru
'---------------------------------
Sub s_clear(ByRef A As slistEl Ptr)

  Dim As slistEl Ptr p, r

  p = A                           ' Przechodzimy przez kolejne elementy zbioru A
  While p
    r = p                         ' Zapamiętujemy adres bieżącego elementu
    p = p->Next                   ' p ustawiamy na następnik
    delete r                      ' Element usuwamy z pamięci
  Wend
  A = 0                           ' Zbiór staje się pusty
End Sub

' Procedura wyświetla zawartość zbioru
'------------------------------------
Sub s_print(byval p As slistEl Ptr)

  While p
    Print Using "###";p->Data;
    p = p->Next
  Wend
End Sub

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

Dim As slistEl Ptr A, B, C
Dim As integer i, x

Randomize                         ' Inicjujemy generator pseudolosowy
A = 0: B = 0                      ' Zerujemy zbiory

' Tworzymy dwa zbiory o przypadkowych elementach

For i = 1 To 10: s_add(A,Int(Rnd() * 20)): Next
For i = 1 To 15: s_add(B,Int(Rnd() * 20)): 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
s_clear(C)

' 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
s_clear(C)

' 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
s_clear(C)

' Podzbiór

Print "IS";
s_print(A->next->next->next)
Print " SUBSET OF A?"
If s_subset(A->next->next->next,A) = 1 Then
  Print "TRUE"
Else 
  Print "False"
End If
Print

Print "IS";
s_print(A->next->next->next)
Print " SUBSET OF B?"
If s_subset(A->next->next->next,B) = 1 Then
  Print "TRUE"
Else
  Print "False"
End If
Print

' Usuwanie

Print "FROM A WE REMOVE";
For i = 1 To 4
  x = Int(Rnd() * 20)
  Print Using "###";x;
  s_remove(A,x)
Next
Print
Print "A =";: s_print(A): Print
Print "SIZE OF A IS"; s_size(A): Print

' Usuwamy wszystkie zbiory

s_clear(A)
s_clear(B)
s_clear(C)

End
Wynik
A =  1 10  8 13  6 12  7 16 17
SIZE OF A IS 9

B = 18  0  2 14  1 12  5 17  8 16
SIZE OF B IS 10

UNION OF A AND B IS  5 14  2  0 18 17 16  7 12  6 13  8 10  1
SIZE OF UNION IS 14

INTERSECTION OF A AND B IS 17 16 12  8  1
SIZE OF INTERSECTION IS 5

DIFFERENCE OF A AND B IS  7  6 13 10
SIZE OF DIFFERENCE IS 4

IS 13  6 12  7 16 17 SUBSET OF A?
TRUE

IS 13  6 12  7 16 17 SUBSET OF B?
FALSE

FROM A WE REMOVE  1 13  2 10
A =  8  6 12  7 16 17
SIZE OF A IS 6

 


   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