Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Reprezentacja zbiorów na listach

SPIS TREŚCI
Tematy pomocnicze

Rozwiązanie

Do przechowywania elementów zbioru zostanie użyta lista jednokierunkowa. 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.
Zmienne pomocnicze:
p  –  wskaźnik elementów listy jednokierunkowej.

Lista kroków:

K02 p  ← A  
K03 Dopóki p  ≠ nil,
wykonuj
kroki 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.
Zmienne 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.
Zmienne 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 p  ← A  
K03 Dopóki p  ≠ nil,
wykonuj kroki 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: p  ← B teraz zajmiemy się listą B
K07: Dopóki p  ≠ nil,
wykonuj kroki 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.
Zmienne 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: p  ← A  
K03: Dopóki p  ≠ nil,
wykonuj kroki 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.
Zmienne 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: p  ← A  
K03: Dopóki p  ≠ nil,
wykonuj
kroki 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.
Zmienne 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: p  ← A będziemy przeglądać listę A
K02: Dopóki p  ≠ nil,
wykonuj kroki 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.
Zmienne pomocnicze:
p  –  wskaźnik elementów listy jednokierunkowej.
c  –  licznik elementów.

Lista kroków:

K01: p  ← A będziemy przeglądać listę A
K02: c  ← 0 zerujemy licznik
K03: Dopóki p  ≠ nil,
wykonuj kroki K03...K06
 
K04:     c  ← c  + 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.
Zmienne 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: p  ← A zapamiętujemy adres początku listy
K03: Jeśli ( pdata  ) ≠ x, to idź do kroku 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 ) obrazek ( ( 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.
Zmienne 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 kroki K03...K05 przechodzimy przez kolejne elementy listy
K03:     r  ← p 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  

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 listach jednokierunkowych. Wyjaśnienie wykonywanych operacji znajduje się w komentarzach wewnątrz programu.
Pascal
// 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.
C++
// 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;
}
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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

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

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

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