Algorytmy i Struktury Danych - Operacje na listach cyklicznych jednokierunkowych

SPIS TREŚCI W KONSERWACJI

Tematy pomocnicze

Wbudowane generatory liczb pseudolosowych

Podrozdziały

Przejście przez listę
Liczba elementów listy
Dodawanie następnika punktu wejścia
Usuwanie następnika punktu wejścia
Wersja obiektowa

Uwaga:

Podane tutaj procedury obsługi list nie uwzględniają sytuacji błędnych – np. braku pamięci dla tworzonych elementów czy nieprawidłowych danych. Można je zatem stosować tylko wtedy, gdy jesteśmy w 100% pewni, że nie dojdzie do żadnych błędów. W przeciwnym razie należałoby zaimplementować obsługę wyjątków, a to jest temat na osobny artykuł.

Typ elementu listy

Cykliczna lista jednokierunkowa jest zwykłą listą jednokierunkową. Różnica polega jedynie na tym, iż pole next ostatniego elementu wskazuje na pierwszy element listy. Zmienna head wskazuje nie początek, lecz punkt wejścia do pierścienia, który tworzą elementy listy jednokierunkowej.

obrazek

Pascal	C++	Basic
type PslistEl = ^slistEl; slistEl = record next : PslistEl; data : typ_danych; end;	struct slistEl { slistEl * next; typ_danych data; };	Type slistEl next As slistEl Ptr data As typ_danych End Type

Lista cykliczna nigdy się nie kończy, gdyż ostatni element łączy się z pierwszym. Nie możemy więc przechodzić jej w taki sam sposób jak listę niecykliczną. Umówimy się, że zmienna head wskazuje początek takiej listy, który będziemy nazywali punktem wejścia (ang. entry point). Natomiast ostatnim elementem będzie ten, którego pole next wskazuje pierwszy element, czyli zawiera taki sam adres jak head. Pozwoli nam to przejść przez wszystkie elementy listy cyklicznej.

Algorytm przechodzenia przez listę cykliczną listę jednokierunkową

Wejście:

head

zmienna zawierająca adres punktu wejścia do listy cyklicznej

Wyjście:

Przejście przez wszystkie elementy listy od pierwszego do ostatniego

Dane pomocnicze:

wskazanie elementu listy

Lista kroków

K01:	p ← head	w p ustawiamy adres punktu wejscia
K02:	Jeśli p = nil, to zakończ	kończymy, jeśli lista jest pusta
K03:	Przetwarzaj element wskazywany przez p
K04:	p ← (p→next)	w p umieść zawartość pola next elementu wskazywanego przez p
K05:	Jeśli p ≠ head, to idź do kroku K03	w pętli przechodzimy przez kolejne elementy listy, aż wrócimy do punktu wejścia
K06:	Zakończ

Pascal

p := head;
if p <> nil then
  repeat
    …
    p := p^.next;
  until p = head;

C++

p = head;
if(p)
do
{
  …
  p = p->next;
} while(p != head);

Basic

p = head
if p Then
  Do
    …
    p = p->next
  Loop Until p = head
End If

Na początek: podrozdziału strony

Do obliczenia liczby elementów wykorzystujemy algorytm przejścia z licznikiem. Przed wejściem do pierścienia licznik zerujemy. Przechodzimy przez kolejne elementy, przy każdym zwiększamy licznik o 1. Po przejściu dookoła pierścienia w liczniku otrzymamy liczbę elementów listy.

Algorytm wyznaczania liczby elementów listy cyklicznej jednokierunkowej

Wejście:

head

zmienna zawierająca adres punktu wejścia do listy cyklicznej

Wyjście:

Liczba elementów listy

Dane pomocnicze:

p	:	wskazanie elementu listy
c	:	licznik elementów

Lista kroków:

K01:	c ← 0	zerujemy licznik
K02:	p ← head	w p ustawiamy adres pierwszego elementu
K03:	Jeśli p = nil, to idź do kroku K07	pomijamy obliczanie, jeśli lista jest pusta
K04:	c ← c + 1	dla każdego elementu zwiększamy licznik o 1
K05:	p ← (p→next)	p ustawiamy na następny element w pierścieniu
K06:	Jeśli p ≠ head, to idź do kroku K04	w pętli przechodzimy przez wszystkie elementy pierścienia
K07:	Zakończ z wynikiem c

Pascal

function l_size (head : PslistEl) : cardinal;
var
  c : cardinal;
  p : PslistEl;
begin
  c := 0;
  p := head;
  if p <> nil then
    repeat
      inc (c);
      p := p^.next;
    until p = head;
  l_size := c;
end;

C++

unsigned l_size (slistEl * head)
{
  unsigned  c = 0;
  slistEl * p = head;

  if(p)
  do
  {
    C++;
    p = p->next;
  } while(p != head);
  return c;
}

Basic

Function l_size (head As slistEl Ptr) As UInteger
  Dim c As UInteger
  Dim p As slistEl Ptr

  c = 0
  p = head

  If p Then
    Do
      c += 1
      p = p->next
    Loop Until p = head
  End If
  l_size = c
End Function

Na początek: podrozdziału strony

	Tworzymy element (na rysunku w kolorze zielonym) i umieszczamy w nim dane.
	Jeśli lista jest pusta (zmienna head zawiera adres zerowy), to pole next ustawiamy na adres nowego elementu (czyli element wskazuje sam siebie). Ten sam adres wprowadzamy do head. Wstawianie jest zakończone.
	Jeśli lista nie jest pusta, to w polu next nowego elementu umieszczamy zawartość pola next pierwszego elementu.
	W polu next pierwszego elementu oraz w zmiennej head umieszczamy adres nowego elementu. Nowy element zostaje wstawiony za punktem wejścia i staje się nowym punktem wejścia do pierścienia.

W tym algorytmie wstawiania zmienna head zawsze wskazuje ostatnio dodany do listy element. Następnik jest natomiast zawsze pierwszym z dodanych elementów. Taka prosta struktura pozwala tworzyć tzw. kolejki (ang. queue), czyli bufory przechowujące dane. W kolejce dane odczytujemy w tej samej kolejności, w której zostały wstawione. Tutaj wystarczy odczytywać następnik i usuwać go z listy.

Algorytm wstawiania następnika punktu wejścia do listy cyklicznej jednokierunkowej

Wejście:

head	:	zawiera adres elementu listy cyklicznej, który jest punktem wejścia
v	:	dane do umieszczenia w elemencie

Wyjście:

Nowy element wstawiony za punktem wejścia. Nowy element staje się nowym punktem wejścia.

Dane pomocnicze:

wskazanie elementu listy

Lista kroków:

K01:	Utwórz nowy element
K02:	p ← adres nowego elementu
K03:	(p→data) ← v	w nowym elemencie umieszczamy dane
K04:	Jeśli head ≠ nil, to idź do kroku K07	sprawdzamy, czy lista jest pusta
K05:	(p→next) ← p	jeśli tak, to nowy element jest swoim własnym następnikiem
K06:	Idź do kroku K09
K07	(p→next) ← (head→next)	następnikiem będzie następnik punktu wejścia
K08:	(head→next) ← p	następnikiem pierwszego elementu będzie nowy element
K09:	head ← p	przesuwamy punkt wejścia na wstawiony element
K10:	Zakończ

Pascal

procedure l_push (var head : PslistEl; v : char);
var
  p : PslistEl;
begin
  new (p);
  p^.data := v;
  if head = nil then p^.next := p
  else
  begin
    p^.next := head^.next;
    head^.next := p;
  end;
  head := p;
end;

C++

void l_push (slistEl * & head, char v)
{
  slistEl * p = new slistEl;

  p->data = v;
  if(head)
  {
    p->next = head->next;
    head->next = p;
  }
  else p->next = p;
  head = p;
}

Basic

Sub l_push (ByRef head As slistEl Ptr, v As String)
  Dim p As slistEl Ptr

  p = new slistEl
  p->data = v
  If head = 0 Then
    p->next = p
  Else
    p->next = head->next
    head->next = p
  End If
  head = p
End Sub

Na początek: podrozdziału strony

	Jeśli lista jest pusta (head zawiera adres zerowy), to nic nie usuwamy i kończymy algorytm.
	Znajdujemy następnik punktu wejścia (na rysunku oznaczony kolorem żółtym – zwróć uwagę, że w przypadku listy jednoelementowej następnik będzie tym samym elementem co punkt wejścia).
	W polu next punktu wejścia umieszczamy zawartość pola next następnika. W ten sposób pierścień listy cyklicznej będzie omijał następnik (o ile lista nie jest jednoelementowa!).
	Jeśli lista jest jednoelementowa (pole next następnika wskazuje na niego samego), to w head umieszczamy adres zerowy. Lista stanie się listą pustą.
	Usuwamy następnik.

Algorytm usuwania następnika punktu wejścia do listy cyklicznej jednokierunkowej

Wejście:

head

zawiera adres elementu listy cyklicznej, który jest punktem wejścia

Wyjście:

Lista z usuniętym następnikiem punktu wejścia

Dane pomocnicze:

wskazanie elementu listy

Lista kroków:

K01:	Jeśli head = 0, to zakończ	lista jest pusta i nie ma co z niej usuwać
K02:	p ← (head→next)	p będzie wskazywało następnik punktu wejścia
K03:	(head→next)← ( p→next)	następnikiem punktu wejścia będzie następnik następnika
K04:	Jeśli (p→next) = p, to head← nil	zerujemy head, jeśli lista jest jednoelementowa
K05	Usuń z pamięci element wskazywany przez p	usuwamy następnik
K06:	Zakończ

Pascal

procedure l_pop (var head : PslistEl);
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head^.next;
    head^.next := p^.next;
    if p^.next = p then head := nil;
    dispose (p);
  end;
end;

C++

void l_pop (slistEl * & head)
{
  if(head)
  {
    slistEl * p = head->next;
    head->next = p->next;
    if(p->next == p) head = NULL;
    delete p;
  }
}

Basic

Sub l_pop (ByRef head As slistEl Ptr)
  Dim p As slistEl Ptr

  If head Then
    p = head->next
    head->next = p->next
    If p->next = p Then head = 0
    Delete p
  End If
End Sub

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.

To jest program testowy, który działa następująco:

[] – tworzy pustą listę literek alfabetu
Na liście umieszcza kolejno literki od A do G, za każdym razem wyświetlając zawartość listy – zwróć uwagę na kolejność poszczególnych elementów w łańcuchu, pamiętaj, że za ostatnim elementem listy następuje bezpośrednio pierwszy element, co jest cechą listy cyklicznej.
Usuwa elementy listy aż do ich wyczerpania. Po każdym usunięciu wyświetlana jest zawartość listy – zwróć uwagę, że elementy znikają z listy w tej samej kolejności w jakiej się na niej pojawiały (cecha kolejki).

Na wydruku pierwsza liczba oznacza ilość elementów listy.

Pascal

// Program testowy dla list cyklicznych jednokierunkowych
// Data: 16.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-------------------------------------------------------

program cslist_test;

// Typ elementów listy
//--------------------
type
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : char;
  end;


// Oblicza liczbę elementów listy
//-------------------------------
function l_size (head : PslistEl) : cardinal;
var
  c : cardinal;
  p : PslistEl;
begin
  c := 0;
  p := head;
  if p <> nil then
    repeat
      inc (c);
      p := p^.next;
    until p = head;
  l_size := c;
end;


// Wyświetla kolejne elementy listy
//---------------------------------
procedure l_printl (head : PslistEl);
var
  p : PslistEl;
begin
  write (l_size (head):3, ' [');
  p := head;
  if p <> nil then
    repeat
      write (' ', p^.data);
      p := p^.next;
    until p = head;
  writeln('] ');
  writeln;
end;

// Wstawia nowy element
//---------------------
procedure l_push (var head : PslistEl; v : char);
var
  p : PslistEl;
begin
  new (p);
  p^.data := v;
  if head = nil then p^.next := p
  else
  begin
    p^.next := head^.next;
    head^.next := p;
  end;
  head := p;
end;


// Usuwa element z listy
//----------------------
procedure l_pop (var head : PslistEl);
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head^.next;
    head^.next := p^.next;
    if p^.next = p then head := nil;
    dispose (p);
  end;
end;

//---------------
// Program główny
//---------------

var
  head : PslistEl;
  i    : char;
begin
  head := nil;
  l_printl (head);
  for i := 'A' to 'G' do
  begin
    l_push (head, i);
    l_printl (head);
  end;
  while head <> nil do
  begin
    l_pop (head);
    l_printl (head);
  end;

end.

C++

// Program testowy dla list cyklicznych jednokierunkowych
// Data: 16.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-------------------------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

struct slistEl
{
  slistEl * next;
  char data;
};

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
unsigned l_size (slistEl * head)
{
  unsigned  c = 0;
  slistEl * p = head;

  if(p)
  do
  {
    C++;
    p = p->next;
  } while(p != head);
  return c;
}

// Wyświetla kolejne elementy listy
//---------------------------------
void l_printl (slistEl * head)
{
   slistEl * p;

  cout << setw (3) << l_size (head) << " [";
  p = head;
  if(p)
    do
    {
      cout << " " << p->data;
      p = p->next;
    } while(p != head);
  cout << "] \n\n";
}

// Wstawia nowy element
//---------------------
void l_push (slistEl * & head, char v)
{
  slistEl * p = new slistEl;

  p->data = v;
  if(head)
  {
    p->next = head->next;
    head->next = p;
  }
  else p->next = p;
  head = p;
}

// Usuwa element
//--------------
void l_pop (slistEl * & head)
{
  if(head)
  {
    slistEl * p = head->next;
    head->next = p->next;
    if(p->next == p) head = NULL;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  slistEl * head = NULL;
  char i;

  l_printl (head);
  for(i = 'A'; i <= 'G'; i++)
  {
    l_push (head, i);
    l_printl (head);
  }
  while(head)
  {
    l_pop (head);
    l_printl (head);
  }

  return 0;
}

Basic

' Program testowy dla list cyklicznych jednokierunkowych
' Data: 16.02.2012
' (C)2020 mgr Jerzy Wałaszek
'-------------------------------------------------------

' Typ elementów listy
'--------------------
Type slistEl
  next As slistEl Ptr
  data  As String * 1
End Type

' Funkcja oblicza liczbę elementów listy
'---------------------------------------
Function l_size (head As slistEl Ptr) As UInteger
  Dim c As UInteger
  Dim p As slistEl Ptr

  c = 0
  p = head

  If p Then
    Do
      c += 1
      p = p->next
    Loop Until p = head
  End If
  l_size = c
End Function

' Wyświetla kolejne elementy listy
'---------------------------------
Sub l_printl (head As slistEl Ptr)
  Dim p As slistEl Ptr

  Print Using "### [";l_size (head);
  p = head
  If p Then
    do
      Print " ";p->data;
      p = p->next
    Loop Until p = head
  End If
  Print "] "
  Print
End Sub

' Wstawia nowy element
'---------------------
Sub l_push (ByRef head As slistEl Ptr, v As String)
  Dim p As slistEl Ptr

  p = new slistEl
  p->data = v
  If head = 0 Then
    p->next = p
  Else
    p->next = head->next
    head->next = p
  End If
  head = p
End Sub

' Usuwa element
'--------------
Sub l_pop (ByRef head As slistEl Ptr)
  Dim p As slistEl Ptr

  If head Then
    p = head->next
    head->next = p->next
    If p->next = p Then head = 0
    Delete p
  End If
End Sub

'---------------
' Program główny
'---------------

Dim head As slistEl Ptr
Dim i As Integer

head = 0
l_printl (head)
For i = Asc ("A") To Asc ("G")
  l_push (head, Chr (i))
  l_printl (head)
Next

While head
  l_pop (head)
  l_printl (head)
Wend

End

Wynik:

0 []

1 [A]

2 [B A]

3 [C A B]

4 [D A B C]

5 [E A B C D]

6 [F A B C D E]

7 [G A B C D E F]

6 [G B C D E F]

5 [G C D E F]

4 [G D E F]

3 [G E F]

2 [G F]

1 [G ]

0 []

Na początek: podrozdziału strony

Poniższy program jest obiektową wersją ostatniego programu.

Pascal

// Obiekt listy cyklicznej jednokierunkowej
// Data: 16.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-------------------------------------------------------

program cslist_object;

// Typ elementów listy
//--------------------
type
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : char;
  end;

// Obiekt listy cyklicznej jednokierunkowej
//-----------------------------------------
  cslist = object
    public
      head : PslistEl;  // punkt wejścia do pierścienia

      constructor init;
      destructor  destroy;
      function    size : cardinal;
      procedure   printl;
      procedure   push (v : char);
      procedure   pop;
  end;

// Metody obiektu cslist
//----------------------

// Inicjuje obiekt
//----------------
constructor cslist.init;
begin
  head := nil;
end;

// Usuwa listę
//------------
destructor cslist.destroy;
begin
  while head <> nil do pop;
end;

// Oblicza liczbę elementów listy
//-------------------------------
function cslist.size : cardinal;
var
  c : cardinal;
  p : PslistEl;
begin
  c := 0;
  p := head;
  if p <> nil then
    repeat
      inc (c);
      p := p^.next;
    until p = head;
  size := c;
end;


// Wyświetla kolejne elementy listy
//---------------------------------
procedure cslist.printl;
var
  p : PslistEl;
begin
  write (size:3, ' [');
  p := head;
  if p <> nil then
    repeat
      write (' ', p^.data);
      p := p^.next;
    until p = head;
  writeln('] ');
  writeln;
end;

// Wstawia nowy element
//---------------------
procedure cslist.push (v : char);
var
  p : PslistEl;
begin
  new (p);
  p^.data := v;
  if head = nil then p^.next := p
  else
  begin
    p^.next := head^.next;
    head^.next := p;
  end;
  head := p;
end;

// Usuwa element z listy
//----------------------
procedure cslist.pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head^.next;
    head^.next := p^.next;
    if p^.next = p then head := nil;
    dispose (p);
  end;
end;

//---------------
// Program główny
//---------------

var
  L : cslist;
  i : char;
begin
  L.init;
  L.printl;
  for i := 'A' to 'G' do
  begin
    L.push (i);
    L.printl;
  end;
  while L.head <> nil do
  begin
    L.pop;
    L.printl;
  end;

end.

C++

// Obiekt listy cyklicznej jednokierunkowej
// Data: 16.02.2012
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

struct slistEl
{
  slistEl * next;
  char data;
};

// Definicja obiektu listy dwukierunkowej
//---------------------------------------
class cslist
{
  public:
    slistEl * head;  // punkt wejścia do listy

    cslist();        // konstruktor
    ~cslist();       // destruktor
    unsigned size();
    void     printl();
    void     push (char v);
    void     pop();
};

//-------------------------------------------------
// Metody obiektu listy cyklicznej jednokierunkowej
//-------------------------------------------------

// Inicjuje obiekt
//----------------
cslist::cslist()
{
  head = NULL;
}

// Usuwa listę z pamięci
//----------------------
cslist::~cslist()
{
  while(head) pop();
}

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
unsigned cslist::size()
{
  unsigned  c = 0;
  slistEl * p = head;

  if(p)
  do
  {
    C++;
    p = p->next;
  } while(p != head);
  return c;
}

// Wyświetla kolejne elementy listy
//---------------------------------
void cslist::printl()
{
   slistEl * p;

  cout << setw (3) << size() << " [";
  p = head;
  if(p)
    do
    {
      cout << " " << p->data;
      p = p->next;
    } while(p != head);
  cout << "] \n\n";
}

// Wstawia nowy element
//---------------------
void cslist::push (char v)
{
  slistEl * p = new slistEl;

  p->data = v;
  if(head)
  {
    p->next = head->next;
    head->next = p;
  }
  else p->next = p;
  head = p;
}

// Usuwa element
//--------------
void cslist::pop()
{
  if(head)
  {
    slistEl * p = head->next;
    head->next = p->next;
    if(p->next == p) head = NULL;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  cslist L;
  char i;

  L.printl();
  for(i = 'A'; i <= 'G'; i++)
  {
    L.push (i);
    L.printl();
  }
  while(L.head)
  {
    L.pop();
    L.printl();
  }

  return 0;
}

Basic

' Obiekt listy cyklicznej jednokierunkowej
' Data: 16.02.2012
' (C)2020 mgr Jerzy Wałaszek
'-------------------------------------------------------

' Typ elementów listy
'--------------------
Type slistEl
  next As slistEl Ptr
  data  As String * 1
End Type

' Typ obiektowy listy cyklicznej jednokierunkowej
'------------------------------------------------
Type cslist
  head As slistEl Ptr
 
  Declare Constructor()
  Declare Destructor()
  Declare Function size() As UInteger
  Declare Sub printl()
  Declare Sub push (v As String)
  Declare Sub pop()
End Type

'---------------
' Program główny
'---------------

Dim L As cslist
Dim i As Integer

L.printl()
For i = Asc ("A") To Asc ("G")
  L.push (Chr (i))
  L.printl()
Next

While L.head
  L.pop()
  L.printl()
Wend
End

' Konstruktor listy
'------------------
Constructor cslist()
  head  = 0
End Constructor

' Usuwa listę z pamięci
Destructor cslist()
  While head
  	 pop()
  Wend
End Destructor

' Funkcja oblicza liczbę elementów listy
'---------------------------------------
Function cslist.size() As UInteger
  Dim c As UInteger
  Dim p As slistEl Ptr

  c = 0
  p = head

  If p Then
    Do
      c += 1
      p = p->next
    Loop Until p = head
  End If
  size = c
End Function

' Wyświetla kolejne elementy listy
'---------------------------------
Sub cslist.printl()
  Dim p As slistEl Ptr

  Print Using "### [";size();
  p = head
  If p Then
    do
      Print " ";p->data;
      p = p->next
    Loop Until p = head
  End If
  Print "] "
  Print
End Sub

' Wstawia nowy element
'---------------------
Sub cslist.push (v As String)
  Dim p As slistEl Ptr

  p = new slistEl
  p->data = v
  If head = 0 Then
    p->next = p
  Else
    p->next = head->next
    head->next = p
  End If
  head = p
End Sub

' Usuwa element
'--------------
Sub cslist.pop()
  Dim p As slistEl Ptr

  If head Then
    p = head->next
    head->next = p->next
    If p->next = p Then head = 0
    Delete p
  End If
End Sub

Na początek: podrozdziału strony

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

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

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

Informacje dodatkowe.

Operacje na cyklicznych listach jednokierunkowych

Uwaga:

Typ elementu listy

Przejście przez listę

Algorytm przechodzenia przez listę cykliczną listę jednokierunkową

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków

Liczba elementów listy

Algorytm wyznaczania liczby elementów listy cyklicznej jednokierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków:

Dodawanie następnika punktu wejścia

Algorytm wstawiania następnika punktu wejścia do listy cyklicznej jednokierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków:

Usuwanie następnika punktu wejścia

Algorytm usuwania następnika punktu wejścia do listy cyklicznej jednokierunkowej

Wejście:

Wyjście:

Dane pomocnicze:

Lista kroków:

Przykładowe programy

Wersja obiektowa