Zbiory rozłączne - implementacja listowa


Tematy pokrewne   Podrozdziały
Listy
Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Operacje na listach dwukierunkowych
Operacje na listach cyklicznych jednokierunkowych
Liniowe przeszukiwanie listy
Przeszukiwanie liniowe z wartownikiem listy dwukierunkowej
Wyszukiwanie największego/najmniejszego elementu listy
Zliczanie elementów listy
Usuwanie z listy duplikatów
Odwracanie listy jednokierunkowej
Podział listy jednokierunkowej na dwie listy
Scalanie dwóch list posortowanych
Sortowanie listy jednokierunkowej przez scalanie
Sortowanie przez wstawianie z wykorzystaniem listy jednokierunkowej
Sortowanie szybkie listy dwukierunkowej
Samoorganizujące się listy
Haszowanie z wykorzystaniem list jednokierunkowych
Zbiory rozłączne – implementacja listowa

Zbiory rozłączne – implementacja w tablicy
Zbiory rozłączne – implementacja za pomocą drzew

  Rozwiązanie nr 1
Rozwiązanie nr 2
Rozwiązanie nr 3

Problem

Stworzyć strukturę danych dla zbiorów rozłącznych.

 

 

Struktura zbiorów rozłącznych (ang. disjoint sets structure) pozwala przechowywać informację o przynależności elementów do różnych zbiorów. Dwa zbiory są rozłączne, jeśli nie posiadają wspólnych elementów. Problem identyfikacji podzbioru rozwiązujemy w ten sposób, iż w każdym rozłącznym zbiorze wybieramy jeden z elementów i traktujemy go jako reprezentanta tego podzbioru.

 

 

Wyobraźmy sobie, że mamy trzy rozłączne zbiory, które zawierają elementy:

 

{1,2,7}   {6,8,10}   {3,4}   {0,5,9,11}

 

W zbiorach tych wybieramy po jednym elemencie. W ten sposób określamy ich reprezentantów:

 

  7 reprezentuje {1,2,7}
10 reprezentuje {6,8,10}
  4 reprezentuje {3,4}
11 reprezentuje {0,5,9,11}

 

Określmy teraz trzy podstawowe operacje:

 

MakeSet(x)
Tworzy nowy, rozłączny zbiór, umieszcza w nim element x i czyni go reprezentantem tego zbioru. Element x nie może należeć do żadnego innego zbioru w tej kolekcji.

 

FindSet(x)

Zwraca reprezentanta zbioru, do którego należy element x. W naszym przykładzie Find-Set(9) = 11.

 

UnionSets(x,y)

Łączy w jeden zbiór zbiory, do których należą elementy x i y. Reprezentantem nowego zbioru staje się jeden z reprezentantów łączonych zbiorów. Zwykle przyjmuje się, że będzie to reprezentant zbioru bardziej licznego.

 

Strukturę zbiorów rozłącznych można w dosyć prosty sposób zrealizować za pomocą odpowiednio zmodyfikowanych list.

 

Rozwiązanie nr 1

Pierwsze rozwiązanie jest bardzo prymitywne, lecz łatwe do zrozumienia. Poszczególne zbiory będziemy realizować za pomocą list dwukierunkowych. Elementy zbiorów będą jednocześnie elementami list. Dostęp do tych list będzie się odbywał za pomocą ich elementów, a nie przy pomocy dodatkowych wskaźników head i tail, zatem adresy tych elementów muszą być w jakiś sposób pamiętane przez aplikację.

 

 

MakeSet(x)

Tworzy jednoelementową listę zawierającą x.

 

FindSet(x)

Przebiega listę z elementem x w kierunku jej początku i zwraca adres pierwszego elementu, czyli reprezentanta zbioru

 

UnionSets(x,y)

Łączy w jedną listę listy zawierające element x i y.

 

Algorytmy dla struktury zbiorów rozłącznych zrealizowanej za pomocą list dwukierunkowych – wersja 1

MakeSet(x)

Wejście
x   wskazanie elementu listy dwukierunkowej
Wyjście:

Utworzenie jednoelementowej listy z elementem x.

Lista kroków:
K01: (xnext) ← nil ;zerujemy pola następnika i poprzednika
K02: (xprev) ← nil  
K03: Zakończ  

 

FindSet(x)

Wejście
x   wskazanie elementu listy dwukierunkowej
Wyjście:

Wskazanie reprezentanta zbioru, do którego należy element x.

Elementy pomocnicze:
p    wskaźnik elementów listy dwukierunkowej
Lista kroków:
K01: px  
K02: Dopóki (pprev) ≠ nil, wykonuj p ← (pprev) ; idziemy w kierunku początku listy
K03: Zakończ z wynikiem p ; zwracamy adres początku listy, czyli adres reprezentanta

 

UnionSets(x,y)

Wejście
x,y   wskazanie elementów listy dwukierunkowej
Wyjście:

Łączy w jedną listę listy zawierające element x i y.

Elementy pomocnicze:
rx,ry,p    wskaźniki elementów listy dwukierunkowej
Lista kroków:
K01: rx ← FindSet(x) ; odnajdujemy reprezentanta zbioru z elementem x
K02: ry ← FindSet(y) ; odnajdujemy reprezentanta zbioru z elementem y
K03: Jeśli rx = ry, to zakończ ; kończymy, jeśli zbiory nie są rozłączne
K04: px  
K05: Dopóki (pnext) ≠ nil, wykonuj p ← (pnext) ; szukamy ostatniego elementu listy zawierającej x
K06: (pnext) ← ry ; początek listy z y dołączamy na koniec listy z x
K07: (ryprev) ← p  
K08: 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 tworzy 10 elementów, umieszcza je w zbiorach jednoelementowych, a następnie losuje 10 razy pary elementów. Dla wylosowanych elementów wykonywana jest operacja UnionSets, co powoduje połączenie zbiorów, które te elementy zawierają. Na końcu wypisana zostaje przynależność każdego elementu do określonego podzbioru, liczba podzbiorów oraz zawartość tych podzbiorów.

 

Lazarus
// Struktura zbiorów rozłącznych
// Data : 28.03.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------

const N = 10;                     // Liczba elementów

// Element listy dwukierunkowej
type
  PdlistEl = ^dlistEl;
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    data  : integer;
  end;

// Tworzy jednoelementową listę
//-----------------------------
procedure MakeSet(x : PdlistEl);
begin
  x^.next := nil;
  x^.prev := nil;
end;

// Zwraca pierwszy element listy
//------------------------------
function FindSet(x : PdlistEl) : PdlistEl;
var
  p : PdlistEl;
begin
  p := x;
  while p^.prev <> nil do p := p^.prev;
  FindSet := p;
end;

// Łączy dwie listy w jedną
//-------------------------
procedure UnionSets(x,y : PdlistEl);
var
  rx,ry,p : PdlistEl;
begin
  rx := FindSet(x);
  ry := FindSet(y);
  if rx <> ry then
  begin
    p := x;
    while p^.next <> nil do p := p^.next;
    p^.next  := ry;
    ry^.prev := p;
  end;
end;

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

var
  Z : array [0..N-1] of dlistEl;
  i,x,y,c : integer;
  p : PdlistEl;
begin
  Randomize;                 // Inicjujemy generator pseudolosowy

  for i := 0 to N - 1 do
  begin
    Z[i].data := i;          // Elementy numerujemy kolejno
    MakeSet(addr(Z[i]));     // i tworzymy z nich zbiory
  end;

  for i := 1 to N do
  begin
    x := random(N);          // Losujemy dwa elementy
    y := random(N);
    UnionSets(addr(Z[x]),addr(Z[y]));
  end;

  // Wypisujemy wyniki

  c := 0;
  for i := 0 to N - 1 do
  begin
    x := FindSet(addr(Z[i]))^.data;
    if x = i then inc(c);
    writeln(i,' is in set ',x);
  end;
  writeln;
  writeln('Numeber of sets = ',c);
  writeln;
  for i := 0 to N - 1 do
  begin
    p := FindSet(addr(Z[i]));
    if p^.data = i then
    begin
      write('Set ',i,' : ');
      while p <> nil do
      begin
        write(p^.data,' ');
        p := p^.next;
      end;
      writeln;
    end;
  end;
end.
Code::Blocks
// Struktura zbiorów rozłącznych
// Data : 28.03.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------

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

using namespace std;

const int N = 10;                 // Liczba elementów

// Element listy dwukierunkowej

struct dlistEl
{
  dlistEl *next,*prev;
  int data;
};

// Tworzy jednoelementową listę
//-----------------------------
void MakeSet(dlistEl *x)
{
  x->next = x->prev = NULL;
}

// Zwraca pierwszy element listy
//------------------------------
dlistEl * FindSet(dlistEl *x)
{
  dlistEl * p;

  for(p = x; p->prev; p = p->prev);

  return p;
}

// Łączy dwie listy w jedną
//-------------------------
void UnionSets(dlistEl *x, dlistEl *y)
{
  dlistEl *rx,*ry,*p;

  rx = FindSet(x);
  ry = FindSet(y);
  if(rx != ry)
  {
    for(p = x; p->next; p = p->next);
    p->next  = ry;
    ry->prev = p;
  }
}

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

int main()
{
  dlistEl Z[N],*p;
  int i,x,y,c;

  srand(time(NULL));              // Inicjujemy generator pseudolosowy

  for(i = 0; i < N; i++)
  {
    Z[i].data = i;               // Elementy numerujemy kolejno
    MakeSet(&Z[i]);              // i tworzymy z nich zbiory
  }

  for(i = 0; i < N; i++)
  {
    x = rand() % N;             // Losujemy dwa elementy
    y = rand() % N;
    UnionSets(&Z[x],&Z[y]);
  }

  // Wypisujemy wyniki

  c = 0;
  for(i = 0; i < N; i++)
  {
    x = FindSet(&Z[i])->data;
    if(x == i) c++;
    cout << i << " is in set " << x << endl;
  }
  cout << endl << "Numeber of sets = " << c << endl << endl;
  for(i = 0; i < N; i++)
  {
    p = FindSet(&Z[i]);
    if(p->data == i)
    {
      cout << "Set " << i << " : ";
      while(p)
      {
        cout << p->data << " ";
        p = p->next;
      }
      cout << endl;
    }
  }

  return 0;
}
Free Basic
' Struktura zbiorów rozłącznych
' Data : 28.03.2014
' (C)2014 mgr Jerzy Wałaszek
'----------------------------

const N = 10                      ' Liczba elementów

' Element listy dwukierunkowej

Type dlistEl
  Next As dlistEl Ptr
  prev As dlistEl Ptr
  Data As Integer
End Type

' Tworzy jednoelementową listę
'-----------------------------
Sub MakeSet(ByVal x As dlistEl Ptr)
  x->next = 0
  x->prev = 0
End Sub

' Zwraca pierwszy element listy
'------------------------------
Function FindSet(ByVal x As dlistEl Ptr) As dlistEl Ptr
  
  Dim As dlistEl Ptr p

  p = x
  While p->prev
    p = p->prev
  Wend

  Return p
  
End Function

' Łączy dwie listy w jedną
'-------------------------
Sub UnionSets(ByVal x As dlistEl Ptr, ByVal y As dlistEl Ptr)
  
  Dim As dlistEl Ptr rx,ry,p

  rx = FindSet(x)
  ry = FindSet(y)
  If rx <> ry Then
    p = x
    While p->Next
    	p = p->Next
    Wend
    p->next  = ry
    ry->prev = p
  End If
End Sub

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

Dim As dlistEl Z(0 To N-1)
Dim As dlistEl Ptr p
Dim As Integer i,x,y,c

Randomize                       ' Inicjujemy generator pseudolosowy

For i = 0 To N - 1
  Z(i).data = i                 ' Elementy numerujemy kolejno
  MakeSet(VarPtr(Z(i)))         ' i tworzymy z nich zbiory
Next

For i = 0 To N - 1
  x = Int(Rnd * N)              ' Losujemy dwa elementy
  y = Int(Rnd * N)
  UnionSets(VarPtr(Z(x)),VarPtr(Z(y)))
Next

' Wypisujemy wyniki

c = 0
For i = 0 To N - 1
  x = FindSet(VarPtr(Z(i)))->Data
  If x = i Then c += 1
  Print i;" is in set";x
Next
Print
Print "Numeber of sets =";c
Print
For i = 0 To N - 1
  p = FindSet(VarPtr(Z(i)))
  If p->data = i Then
    Print "Set";i;" :";
    While p
      Print p->Data;
      p = p->Next
    Wend
    Print
  End If
Next

End
Wynik
0 is in set 3
1 is in set 1
2 is in set 4
3 is in set 3
4 is in set 4
5 is in set 4
6 is in set 4
7 is in set 3
8 is in set 4
9 is in set 3

Numeber of sets = 3

Set 1 : 1
Set 3 : 3 0 7 9
Set 4 : 4 5 8 6 2

 

Rozwiązanie nr 2

Zmieniając nieznacznie budowę list, możemy znacząco przyspieszyć niektóre operacje wykonywane na strukturze zbiorów rozłącznych. Opisana wcześniej operacja FindSet ma złożoność klasy O(n), ponieważ musi przechodzić przez kolejne elementy listy aż do jej początku. Wadę tę możemy prosto wyeliminować, umieszczając w polu prev nie adres poprzedniego elementu, lecz adres początku listy. Teraz znalezienie reprezentanta będzie miało klasę złożoności O(1). Jednakże komplikuje to operację UnionSets, ponieważ w dołączanej na końcu liście należy zastąpić w każdym elemencie adres w polu prev nowym adresem reprezentanta zbioru.

 

 

Algorytmy dla struktury zbiorów rozłącznych zrealizowanej za pomocą list dwukierunkowych – wersja 2

MakeSet(x)

Wejście
x   wskazanie elementu listy dwukierunkowej
Wyjście:

Utworzenie jednoelementowej listy z elementem x.

Lista kroków:
K01: (xnext) ← nil ; pole następnika zerujemy
K02: (xprev) ← x ; pole poprzednika wskazuje reprezentanta, czyli x
K03: Zakończ  

 

FindSet(x)

Wejście
x   wskazanie elementu listy dwukierunkowej
Wyjście:

Wskazanie reprezentanta zbioru, do którego należy element x.

Lista kroków:
K01: Zakończ z wynikiem (xprev) ; zwracamy adres początku listy, czyli adres reprezentanta

 

UnionSets(x,y)

Wejście
x,y   wskazanie elementów listy dwukierunkowej
Wyjście:

Łączy w jedną listę listy zawierające element x i y.

Elementy pomocnicze:
rx,ry,p    wskaźniki elementów listy dwukierunkowej
Lista kroków:
K01: rx ← (xprev) ; odnajdujemy reprezentanta zbioru z elementem x
K02: ry ← (yprev) ; odnajdujemy reprezentanta zbioru z elementem y
K03: Jeśli rx = ry, to zakończ ; kończymy, jeśli zbiory nie są rozłączne
K04: px  
K05: Dopóki (pnext) ≠ nil, wykonuj p ← (pnext) ; szukamy ostatniego elementu listy zawierającej x
K06: (pnext) ← ry ; początek listy z y dołączamy na koniec listy z x
K07: (ryprev) ← p  
K08: p ← (pnext) ; przechodzimy do następnego elementu listy
K09: Jeśli p = nil, to zakończ ; koniec listy?
K10: (pprev) ← rx ; w dołączonej liście zastępujemy reprezentanta adresem rx
K11: Idź do K08  

 

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 tworzy 10 elementów, umieszcza je w zbiorach jednoelementowych, a następnie losuje 10 razy pary elementów. Dla wylosowanych elementów wykonywana jest operacja UnionSets, co powoduje połączenie zbiorów, które te elementy zawierają. Na końcu wypisana zostaje przynależność każdego elementu do określonego podzbioru, liczba podzbiorów oraz zawartość tych podzbiorów.

 

Lazarus
// Struktura zbiorów rozłącznych
// Data : 28.03.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------

const N = 10;                     // Liczba elementów

// Element listy dwukierunkowej
type
  PdlistEl = ^dlistEl;
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    data  : integer;
  end;

// Tworzy jednoelementową listę
//-----------------------------
procedure MakeSet(x : PdlistEl);
begin
  x^.next := nil;
  x^.prev := x;
end;

// Zwraca pierwszy element listy
//------------------------------
function FindSet(x : PdlistEl) : PdlistEl;
begin
  FindSet := x^.prev;
end;

// Łączy dwie listy w jedną
//-------------------------
procedure UnionSets(x,y : PdlistEl);
var
  rx,ry,p : PdlistEl;
begin
  rx := x^.prev;
  ry := y^.prev;
  if rx <> ry then
  begin
    p := x;
    while p^.next <> nil do p := p^.next;
    p^.next  := ry;
    ry^.prev := p;
    while true do
    begin
      p := p^.next;
      if p = nil then break;
      p^.prev := rx;
    end;
  end;
end;

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

var
  Z : array [0..N-1] of dlistEl;
  i,x,y,c : integer;
  p : PdlistEl;
begin
  Randomize;                 // Inicjujemy generator pseudolosowy

  for i := 0 to N - 1 do
  begin
    Z[i].data := i;          // Elementy numerujemy kolejno
    MakeSet(addr(Z[i]));     // i tworzymy z nich zbiory
  end;

  for i := 1 to 10 do
  begin
    x := random(N);          // Losujemy dwa elementy
    y := random(N);
    UnionSets(addr(Z[x]),addr(Z[y]));
  end;

  // Wypisujemy wyniki

  c := 0;
  for i := 0 to N - 1 do
  begin
    x := FindSet(addr(Z[i]))^.data;
    if x = i then inc(c);
    writeln(i,' is in set ',x);
  end;
  writeln;
  writeln('Numeber of sets = ',c);
  writeln;
  for i := 0 to N - 1 do
  begin
    p := FindSet(addr(Z[i]));
    if p^.data = i then
    begin
      write('Set ',i,' : ');
      while p <> nil do
      begin
        write(p^.data,' ');
        p := p^.next;
      end;
      writeln;
    end;
  end;
end.
Code::Blocks
// Struktura zbiorów rozłącznych
// Data : 28.03.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------

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

using namespace std;

const int N = 10;                 // Liczba elementów

// Element listy dwukierunkowej

struct dlistEl
{
  dlistEl *next,*prev;
  int data;
};

// Tworzy jednoelementową listę
//-----------------------------
void MakeSet(dlistEl *x)
{
  x->next = NULL;
  x->prev = x;
}

// Zwraca pierwszy element listy
//------------------------------
dlistEl * FindSet(dlistEl *x)
{
  return x->prev;
}

// Łączy dwie listy w jedną
//-------------------------
void UnionSets(dlistEl *x, dlistEl *y)
{
  dlistEl *rx,*ry,*p;

  rx = x->prev;
  ry = y->prev;
  if(rx != ry)
  {
    for(p = x; p->next; p = p->next);
    p->next  = ry;
    ry->prev = p;
    while((p = p->next)) p->prev = rx;
  }
}

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

int main()
{
  dlistEl Z[N],*p;
  int i,x,y,c;

  srand(time(NULL));              // Inicjujemy generator pseudolosowy

  for(i = 0; i < N; i++)
  {
    Z[i].data = i;               // Elementy numerujemy kolejno
    MakeSet(&Z[i]);              // i tworzymy z nich zbiory
  }

  for(i = 0; i < N; i++)
  {
    x = rand() % N;             // Losujemy dwa elementy
    y = rand() % N;
    UnionSets(&Z[x],&Z[y]);
  }

  // Wypisujemy wyniki

  c = 0;
  for(i = 0; i < N; i++)
  {
    x = FindSet(&Z[i])->data;
    if(x == i) c++;
    cout << i << " is in set " << x << endl;
  }
  cout << endl << "Numeber of sets = " << c << endl << endl;
  for(i = 0; i < N; i++)
  {
    p = FindSet(&Z[i]);
    if(p->data == i)
    {
      cout << "Set " << i << " : ";
      while(p)
      {
        cout << p->data << " ";
        p = p->next;
      }
      cout << endl;
    }
  }

  return 0;
}
Free Basic
' Struktura zbiorów rozłącznych
' Data : 28.03.2014
' (C)2014 mgr Jerzy Wałaszek
'----------------------------

const N = 10                      ' Liczba elementów

' Element listy dwukierunkowej

Type dlistEl
  Next As dlistEl Ptr
  prev As dlistEl Ptr
  Data As Integer
End Type

' Tworzy jednoelementową listę
'-----------------------------
Sub MakeSet(ByVal x As dlistEl Ptr)
  x->next = 0
  x->prev = x
End Sub

' Zwraca pierwszy element listy
'------------------------------
Function FindSet(ByVal x As dlistEl Ptr) As dlistEl Ptr
  
  Return x->prev
  
End Function

' Łączy dwie listy w jedną
'-------------------------
Sub UnionSets(ByVal x As dlistEl Ptr, ByVal y As dlistEl Ptr)
  
  Dim As dlistEl Ptr rx,ry,p

  rx = x->prev
  ry = y->prev
  If rx <> ry Then
    p = x
    While p->Next
    	p = p->Next
    Wend
    p->next  = ry
    ry->prev = p
    While 1
    	p = p->Next
    	If p = 0 Then Exit While
    	p->prev = rx
    Wend
  End If
End Sub

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

Dim As dlistEl Z(0 To N-1)
Dim As dlistEl Ptr p
Dim As Integer i,x,y,c

Randomize                       ' Inicjujemy generator pseudolosowy

For i = 0 To N - 1
  Z(i).data = i                 ' Elementy numerujemy kolejno
  MakeSet(VarPtr(Z(i)))         ' i tworzymy z nich zbiory
Next

For i = 0 To N - 1
  x = Int(Rnd * N)              ' Losujemy dwa elementy
  y = Int(Rnd * N)
  UnionSets(VarPtr(Z(x)),VarPtr(Z(y)))
Next

' Wypisujemy wyniki

c = 0
For i = 0 To N - 1
  x = FindSet(VarPtr(Z(i)))->Data
  If x = i Then c += 1
  Print i;" is in set";x
Next
Print
Print "Numeber of sets =";c
Print
For i = 0 To N - 1
  p = FindSet(VarPtr(Z(i)))
  If p->data = i Then
    Print "Set";i;" :";
    While p
      Print p->Data;
      p = p->Next
    Wend
    Print
  End If
Next

End
Wynik
0 is in set 3
1 is in set 1
2 is in set 4
3 is in set 3
4 is in set 4
5 is in set 4
6 is in set 4
7 is in set 3
8 is in set 4
9 is in set 3

Numeber of sets = 3

Set 1 : 1
Set 3 : 3 0 7 9
Set 4 : 4 5 8 6 2

 

Rozwiązanie nr 3

Kolejne ulepszenie ma na celu przyspieszenie operacji UnionSets. W tym celu zmieniamy budowę użytych list tak, aby każdy element wskazywał poprzez pole prev na strukturę dlistVar, w której przechowujemy adres początku listy (reprezentant zbioru), adres ostatniego elementu na liście oraz liczbę elementów listy. Operacja UnionSets korzysta z tych pól przy łączeniu list. Zawsze dołączana jest lista krótsza do dłuższej. Dzięki temu minimalizujemy liczbę uaktualnień elementów w dołączanej liście.

 

 

Algorytmy dla struktury zbiorów rozłącznych zrealizowanej za pomocą list dwukierunkowych – wersja 3

MakeSet(x)

Wejście
x   wskazanie elementu listy dwukierunkowej
Wyjście:

Utworzenie jednoelementowej listy z elementem x. Tworzona jest również struktura dlistVar.

Elementy pomocnicze:
p    wskaźnik struktury dlistVar
Lista kroków:
K01: Utwórz nową strukturę dlistVar i umieść jej adres w p  
K02: (phead) ← x ; początkiem listy jest x
K03: (ptail) ← x ; końcem listy jest też x
K04: (pcount) ← 1 ; lista zawiera 1 element
K05: (xnext) ← nil  
K06: (xprev) ← p ; pole prev wskazuje na strukturę dlistVar
K07: Zakończ  

 

FindSet(x)

Wejście
x   wskazanie elementu listy dwukierunkowej
Wyjście:

Wskazanie struktury dlistVar zbioru, do którego należy element x.

Lista kroków:
K01: Zakończ z wynikiem (xprevhead) ; zwracamy adres początku listy, czyli adres reprezentanta

 

UnionSets(x,y)

Wejście
x,y   wskazanie elementów listy dwukierunkowej
Wyjście:

Łączy w jedną listę listy zawierające element x i y.

Elementy pomocnicze:
rx,ry    wskaźniki struktur dlistVar
p   wskaźnik elementów listy dwukierunkowej
Lista kroków:
K01: rx ← (xprev) ; odnajdujemy struktury dlistVar dla listy z x
K02: ry ← (yprev) ; odnajdujemy struktury dlistVar dla listy z y
K03: Jeśli rx = ry, to zakończ ; kończymy, jeśli jest to ta sama lista
K04: Jeśli (rxcount) < (rycount), to rxry ; rx - lista główna, ry - lista dodawana
K05: (rxtailnext) ← (ry→head) ; listę ry dołączamy na koniec rx
K06: (rxtail) ← (rytail) ; koniec listy rx jest końcem listy ry
K07: (rxcount) ← (rxcount) + (rycount) ; obliczamy nową długość
K08: p ← (ryhead) ; przechodzimy przez listę ry i modyfikujemy pola prev
K09: while p <> nil  
K10:     (pprev) ← rx ; modyfikujemy pole prev elementów ry
K11:     p ← (pnext) ; idziemy do następnego elementu
K12: Usuń z pamięci ry ; usuwamy zbędną już strukturę dlistVar
K13: 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 tworzy 10 elementów, umieszcza je w zbiorach jednoelementowych, a następnie losuje 10 razy pary elementów. Dla wylosowanych elementów wykonywana jest operacja UnionSets, co powoduje połączenie zbiorów, które te elementy zawierają. Na końcu wypisana zostaje przynależność każdego elementu do określonego podzbioru, liczba podzbiorów oraz zawartość tych podzbiorów wraz z liczbą ich elementów.

 

Lazarus
// Struktura zbiorów rozłącznych
// Data : 29.03.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------

const N = 10;                     // Liczba elementów

// Elementy listy dwukierunkowej
type
  PdlistVar = ^dlistVar;
  PdlistEl = ^dlistEl;
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistVar;
    data  : integer;
  end;

  dlistVar = record
    head  : PdlistEl;
    tail  : PdlistEl;
    count : cardinal;
  end;

// Tworzy jednoelementową listę
//-----------------------------
procedure MakeSet(x : PdlistEl);
var
  p : PdlistVar;
begin
  new(p);                         // Tworzymy nową strukturę dlistVar
  p^.head  := x;                  // Inicjujemy jej pola
  p^.tail  := x;
  p^.count := 1;
  x^.next := nil;
  x^.prev := p;                   // Adres struktury dlistVar zapamiętujemy w x
end;

// Zwraca pierwszy element listy
//------------------------------
function FindSet(x : PdlistEl) : PdlistEl;
begin
  FindSet := x^.prev^.head;       // Zwracamy adres reprezentanta
end;

// Łączy dwie listy w jedną
//-------------------------
procedure UnionSets(x,y : PdlistEl);
var
  rx,ry : PdlistVar;
  p     : PdlistEl;
begin
  rx := x^.prev;                  // Zapamiętujemy adresy struktur dlistVar
  ry := y^.prev;
  if rx <> ry then                // Struktury muszą być różne
  begin
    if rx^.count < ry^.count then // Ustawiamy rx - lista dłuższa, ry - krótsza
    begin
      rx := ry;
      ry := x^.prev;
    end;
    rx^.tail^.next := ry^.head;   // Listę ry dołączamy na koniec listy rx
    rx^.tail := ry^.tail;         // Koniec listy rx będzie końcem listy ry
    inc(rx^.count,ry^.count);     // Modyfikujemy licznik elementów
    p := ry^.head;                // Na liście ry modyfikujemy pola prev
    while p <> nil do
    begin
      p^.prev := rx;              // Teraz będą wskazywały strukturę listy rx
      p := p^.next;               // Następny element na liście
    end;
    dispose(ry);                  // Usuwamy z pamięci zbędną strukturę dlistVar
  end;
end;

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

var
  Z : array [0..N-1] of dlistEl;
  i,x,y,c : integer;
  p : PdlistEl;
  r : PdlistVar;
begin
  Randomize;                 // Inicjujemy generator pseudolosowy

  for i := 0 to N - 1 do
  begin
    Z[i].data := i;          // Elementy numerujemy kolejno
    MakeSet(addr(Z[i]));     // i tworzymy z nich zbiory
  end;

  for i := 1 to 10 do
  begin
    x := random(N);          // Losujemy dwa elementy
    y := random(N);
    UnionSets(addr(Z[x]),addr(Z[y]));
  end;

  // Wypisujemy wyniki

  c := 0;
  for i := 0 to N - 1 do
  begin
    x := FindSet(addr(Z[i]))^.data;
    if x = i then inc(c);
    writeln(i,' is in set ',x);
  end;
  writeln;
  writeln('Numeber of sets = ',c);
  writeln;
  for i := 0 to N - 1 do
  begin
    p := FindSet(addr(Z[i]));
    if p^.data = i then
    begin
      write('Set ',i,' count = ',p^.prev^.count,' : ');
      while p <> nil do
      begin
        write(p^.data,' ');
        p := p^.next;
      end;
      writeln;
    end;
  end;

  // Usuwamy struktury dlistVar

  for i := 0 to N - 1 do
  begin
    r := Z[i].prev;               // Zapamiętujemy adres struktury dlistVar
    if r <> nil then              // Jeśli ta struktura istnieje,
    begin
      p := r^.head;               // to z listy usuwamy jej adres
      while p <> nil do
      begin
        p^.prev := nil;
        p := p^.next;
      end;
      dispose(r);                 // Usuwamy strukturę z pamięci
    end;
  end;
end.
Code::Blocks
// Struktura zbiorów rozłącznych
// Data : 29.03.2014
// (C)2014 mgr Jerzy Wałaszek
//----------------------------

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

using namespace std;

const int N = 10;                 // Liczba elementów

// Elementy listy dwukierunkowej

struct dlistEl
{
  struct dlistEl  *next;
  struct dlistVar *prev;
  int data;
};

struct dlistVar
{
  struct dlistEl *head;
  struct dlistEl *tail;
  unsigned count;
};

// Tworzy jednoelementową listę
//-----------------------------
void MakeSet(dlistEl *x)
{
  dlistVar *p;

  p = new dlistVar;               // Tworzymy nową strukturę dlistVar
  p->head  = x;                   // Inicjujemy jej pola
  p->tail  = x;
  p->count = 1;
  x->next  = NULL;
  x->prev  = p;                   // Adres struktury dlistVar zapamiętujemy w x
}

// Zwraca pierwszy element listy
//------------------------------
dlistEl * FindSet(dlistEl *x)
{
  return x->prev->head;           // Zwracamy adres reprezentanta
}

// Łączy dwie listy w jedną
//-------------------------
void UnionSets(dlistEl *x, dlistEl *y)
{
  dlistVar *rx,*ry;
  dlistEl *p;

  rx = x->prev;                   // Zapamiętujemy adresy struktur dlistVar
  ry = y->prev;
  if(rx != ry)                    // Struktury muszą być różne
  {
    if(rx->count < ry->count)     // Ustawiamy rx - lista dłuższa, ry - krótsza
    {
      rx = ry;
      ry = x->prev;
    }
    rx->tail->next = ry->head;    // Listę ry dołączamy na koniec listy rx
    rx->tail = ry->tail;          // Koniec listy rx będzie końcem listy ry
    rx->count += ry->count;       // Modyfikujemy licznik elementów

    for(p = ry->head; p; p = p->next) // Na liście ry modyfikujemy pola prev
      p->prev = rx;               // Teraz będą wskazywały strukturę listy rx

    delete ry;                    // Usuwamy z pamięci zbędną strukturę dlistVar
  }
}

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

int main()
{
  dlistEl Z[N],*p;
  int i,x,y,c;
  dlistVar *r;

  srand(time(NULL));              // Inicjujemy generator pseudolosowy

  for(i = 0; i < N; i++)
  {
    Z[i].data = i;                // Elementy numerujemy kolejno
    MakeSet(&Z[i]);               // i tworzymy z nich zbiory
  }

  for(i = 0; i < N; i++)
  {
    x = rand() % N;               // Losujemy dwa elementy
    y = rand() % N;
    UnionSets(&Z[x],&Z[y]);
  }

  // Wypisujemy wyniki

  c = 0;
  for(i = 0; i < N; i++)
  {
    x = FindSet(&Z[i])->data;
    if(x == i) c++;
    cout << i << " is in set " << x << endl;
  }
  cout << endl << "Numeber of sets = " << c << endl << endl;
  for(i = 0; i < N; i++)
  {
    p = FindSet(&Z[i]);
    if(p->data == i)
    {
      cout << "Set " << i << " count = " << p->prev->count << " : ";
      while(p)
      {
        cout << p->data << " ";
        p = p->next;
      }
      cout << endl;
    }
  }

  // Usuwamy struktury dlistVar

  for(i = 0; i < N; i++)
  {
    r = Z[i].prev;                // Zapamiętujemy adres struktury dlistVar
    if(r)                         // Jeśli ta struktura istnieje,
    {
      for(p = r->head; p; p = p->next)
        p->prev = NULL;           // to z listy usuwamy jej adres
      delete r;                   // Usuwamy strukturę z pamięci
    }
  }

  return 0;
}
Free Basic
' Struktura zbiorów rozłącznych
' Data : 29.03.2014
' (C)2014 mgr Jerzy Wałaszek
'----------------------------

const N = 10                      ' Liczba elementów

' Elementy listy dwukierunkowej

Type dlistVarFwd As dlistVar      ' Typ tymczasowy do rozwiązania referencji krzyżowej
Type dlistEl
  Next As dlistEl Ptr
  prev As dlistVarFwd Ptr         ' Referencja krzyżowa
  Data As Integer
End Type

Type dlistVar
  head As dlistEl Ptr
  tail  As dlistEl Ptr
  count As UInteger
End Type

' Tworzy jednoelementową listę
'-----------------------------
Sub MakeSet(ByVal x As dlistEl Ptr)
 
  Dim As dlistVar Ptr p

  p = new dlistVar                ' Tworzymy nową strukturę dlistVar
  p->head  = x                    ' Inicjujemy jej pola
  p->tail  = x
  p->count = 1
  x->next  = 0
  x->prev  = p                    ' Adres struktury dlistVar zapamiętujemy w x

End Sub

' Zwraca pierwszy element listy
'------------------------------
Function FindSet(byval x As dlistEl Ptr) As dlistEl Ptr
  return x->prev->head            ' Zwracamy adres reprezentanta
End Function

' Łączy dwie listy w jedną
'-------------------------
Sub UnionSets(ByVal x As dlistEl Ptr, ByVal y As dlistEl Ptr)
	
  Dim As dlistVar Ptr rx,ry
  Dim As dlistEl Ptr p

  rx = x->prev                    ' Zapamiętujemy adresy struktur dlistVar
  ry = y->prev
  If rx <> ry Then                ' Struktury muszą być różne
    If rx->count < ry->count Then ' Ustawiamy rx - lista dłuższa, ry - krótsza
      rx = ry
      ry = x->prev
    End If
    rx->tail->next = ry->head     ' Listę ry dołączamy na koniec listy rx
    rx->tail = ry->tail           ' Koniec listy rx będzie końcem listy ry
    rx->count += ry->count        ' Modyfikujemy licznik elementów

    p = ry->head                  ' Na liście ry modyfikujemy pola prev
    While p
      p->prev = rx                ' Teraz będą wskazywały strukturę listy rx
      p = p->Next
    Wend
    Delete ry                     ' Usuwamy z pamięci zbędną strukturę dlistVar
  End If
End Sub

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

Dim as dlistEl Z(0 To N - 1)
Dim As dlistEl Ptr p
Dim As Integer i,x,y,c
Dim As dlistVar Ptr r

Randomize                         ' Inicjujemy generator pseudolosowy

For i = 0 To N - 1
  Z(i).data = i                   ' Elementy numerujemy kolejno
  MakeSet(VarPtr(Z(i)))           ' i tworzymy z nich zbiory
Next

For i = 0 To N - 1
  x = Int(Rnd * N)                ' Losujemy dwa elementy
  y = Int(Rnd * N)
  UnionSets(VarPtr(Z(x)),VarPtr(Z(y)))
Next

' Wypisujemy wyniki

c = 0
For i = 0 To N - 1
  x = FindSet(VarPtr(Z(i)))->Data
  If x = i Then c += 1
  Print i;" is in set";x
Next
Print
Print "Numeber of sets =";c
Print
For i = 0 To N - 1
  p = FindSet(VarPtr(Z(i)))
  If p->data = i Then
    Print "Set";i;" count = ";p->prev->count;" :";
    While p
      Print p->data;
      p = p->Next
    Wend
    Print
  End If
Next

' Usuwamy struktury dlistVar

For i = 0 To N - 1
  r = Z(i).prev                   ' Zapamiętujemy adres struktury dlistVar
  If r Then                       ' Jeśli ta struktura istnieje,
    p = r->head
    While p
      p->prev = 0                 ' to z listy usuwamy jej adres
      p = p->Next                 ' Następny element listy
    Wend
    delete r                      ' Usuwamy strukturę z pamięci
  End If
Next

End
Wynik
0 is in set 9
1 is in set 1
2 is in set 2
3 is in set 9
4 is in set 1
5 is in set 9
6 is in set 9
7 is in set 7
8 is in set 9
9 is in set 9

Numeber of sets = 4

Set 1 count = 2 : 1 4
Set 2 count = 1 : 2
Set 7 count = 1 : 7
Set 9 count = 6 : 9 8 0 3 5 6

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



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

©2017 mgr Jerzy Wałaszek

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