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

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Operacje na cyklicznych listach jednokierunkowych

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

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 wejściowych. Można je zatem stosować tylko wtedy, gdy jesteśmy w 100% pewni, że nie dojdzie do żadnych nieprawidłowości. W przeciwnym razie należałoby zaimplementować obsługę wyjątków, a to jest temat na osobny artykuł.

Typy dla list cyklicznych jedno-kierunkowych

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 
type
  PCSLel = ^CSLel;
  CSLel = record
    next  : PCSLel;
    data  : typ_danych;
  end;
C++ 
struct CSLel
{
  CSLel * next;
  typ_danych data;
};
Basic 
Type CSLel
  next As CSLel Ptr
  data As typ_danych
End Type
Python (dodatek) 
# klasa elementu listy cyklicznej
# jednokierunkowej
class CSLel:


    def __init__(self, data):
        self.next = None
        self.data = data

# klasa listy cyklicznej
# jednokierunkowej
class CSLvar:


    def __init__(self):
        self.head = None

Przejście przez listę

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:

p : wskazanie elementu listy.

Lista kroków

K01: p ← head ; w p ustawiamy adres punktu wejścia
K02: Jeśli p = nil, ; kończymy, jeśli lista jest pusta
     to zakończ
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, ; w pętli przechodzimy przez kolejne
     to idź do kroku K03 ; 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
…
Python (dodatek) 
# klasa elementu listy cyklicznej
# jednokierunkowej
class CSLel:


    def __init__(self, data):
        self.next = None
        self.data = data

# klasa listy cyklicznej
# jednokierunkowej
class CSLvar:


    def __init__(self):
        self.head = None
…
cl = CSLvar()
…
p = cl.head
if p:
    while True:
    … # przetwarzanie elementu
    p = p.next
    if p is cl.head: break
…

Na początek:  podrozdziału   strony 

Liczba elementów listy

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, ; pomijamy obliczanie, jeśli lista jest pusta
     to idź do kroku K07
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, ; w pętli przechodzimy przez wszystkie
     to idź do kroku K04 ; elementy pierścienia
K07: Zakończ z wynikiem c
Pascal
function l_len(head : PCSLel) : cardinal;
var
  c : cardinal;
  p : PCSLel;
begin
  c := 0;
  p := head;
  if p <> nil then
    repeat
      inc(c);
      p := p^.next;
    until p = head;
  l_len := c;
end;
C++
unsigned l_len(CSLel * head)
{
  unsigned  c = 0;
  CSLel * p = head;

  if(p)
    do
    {
      c++;
      p = p->next;
    } while(p != head);
  return c;
}
Basic
Function l_len(head As CSLel Ptr) _
               As UInteger
  Dim c As UInteger
  Dim p As CSLel Ptr

  c = 0
  p = head

  If p Then
    Do
      c += 1
      p = p->next
    Loop Until p = head
  End If
  l_len = c
End Function
Python (dodatek) 
# klasa elementu listy cyklicznej
# jednokierunkowej
class CSLel:


    def __init__(self, data):
        self.next = None
        self.data = data

# klasa listy cyklicznej
# jednokierunkowej
class CSLvar:


    def __init__(self):
        self.head = None

    # Zliczanie elementów
    def l_len(self):
        c = 0
        p = self.head
        if p:
            while True:
                c += 1
                p = p.next
                if self.head is p:
                    break
        return c

Na początek:  podrozdziału   strony 

Dodawanie następnika punktu wejścia

obrazek
Tworzymy element (na rysunku w kolorze zielonym) i umieszczamy w nim dane.
obrazek obrazek
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.
obrazek
Jeśli lista nie jest pusta, to w polu next nowego elementu umieszczamy zawartość pola next pierwszego elementu.
obrazek
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:

p : wskazanie elementu listy.

Lista kroków:

K01: p ← adres nowego elementu
K02: p→data ← v ; w nowym elemencie umieszczamy dane
K03: Jeśli head ≠ nil, ; sprawdzamy, czy lista jest pusta
     to idź do kroku K06
K04: p→next ← p ; jeśli tak, to nowy element jest
                ; swoim własnym następnikiem
K05: Idź do kroku K08
K06: p→next ← head→next ; następnikiem będzie następnik
                        ; punktu wejścia
K07: head→next ← p ; następnikiem pierwszego elementu
                   ; będzie nowy element
K08: head ← p ; przesuwamy punkt wejścia na wstawiony element
K09: Zakończ
Pascal
procedure l_push(var head : PCSLel;
                     v : char);
var
  p : PCSLel;
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(CSLel * & head, char v)
{
  CSLel * p = new CSLel;

  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 CSLel Ptr, _
                 v As String)
  Dim p As CSLel Ptr

  p = new CSLel
  p->data = v
  If head = 0 Then
    p->next = p
  Else
    p->next = head->next
    head->next = p
  End If
  head = p
End Sub
Python (dodatek) 
# klasa elementu listy cyklicznej
# jednokierunkowej
class CSLel:


    def __init__(self, data):
        self.next = None
        self.data = data
        
# klasa listy cyklicznej
# jednokierunkowej
class CSLvar:


    def __init__(self):
        self.head = None

    # wstawianie następnika
    def l_push(self, v):
        p = CSLel(v)
        if self.head:
            p.next = self.head.next
            self.head.next = p
        else:
            p.next = p
        self.head = p

Na początek:  podrozdziału   strony 

Usuwanie następnika punktu wejścia

obrazek
Jeśli lista jest pusta (head zawiera adres zerowy), to nic nie usuwamy i kończymy algorytm.
obrazek
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).
obrazek
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!).
obrazek
Jeśli lista jest jednoelementowa (pole next następnika wskazuje na niego samego), to w head umieszczamy adres zerowy. Lista stanie się listą pustą.
obrazek
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:

p : wskazanie elementu listy.

Lista kroków:

K01: Jeśli head = 0, ; lista jest pusta i nie ma
     to zakończ ; 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, ; zerujemy head, jeśli lista
     to head ← nil ; jest jednoelementowa
K05: Usuń element wskazywany przez p ; usuwamy następnik
K06: Zakończ
Pascal
procedure l_pop(var head : PCSLel);
var
  p : PCSLel;
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(CSLel * & head)
{
  if(head)
  {
    CSLel * p = head->next;
    head->next = p->next;
    if(p->next == p)
      head = NULL;
    delete p;
  }
}
Basic
Sub l_pop(ByRef head As CSLel Ptr)
  Dim p As CSLel Ptr

  If head Then
    p = head->next
    head->next = p->next
    If p->next = p Then _
      head = 0
    Delete p
  End If
End Sub
Python (dodatek) 
# klasa elementu listy cyklicznej
# jednokierunkowej
class CSLel:


    def __init__(self, data):
        self.next = None
        self.data = data


# klasa listy cyklicznej
# jednokierunkowej
class CSLvar:


    def __init__(self):
        self.head = None


    #usuwanie
    def l_pop(self):
        if self.head:
            p = self.head.next
            self.head.next = p.next
            if p.next is p:
                self.head = None
            p = None

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 ccslist_test;

// Typ elementów listy
//--------------------
type
  PCSLel = ^CSLel;

  CSLel =  record
    next  : PCSLel;
    data  : char;
  end;

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

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

// Wstawia nowy element
//---------------------
procedure l_push(var head : PCSLel;
                     v : char);
var
  p : PCSLel;
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 : PCSLel);
var
  p : PCSLel;
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 : PCSLel;
  i    : char;
begin
  head := nil;
  l_print(head);
  for i := 'A' to 'G' do
  begin
    l_push(head, i);
    l_print(head);
  end;
  while head <> nil do
  begin
    l_pop(head);
    l_print(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 CSLel
{
  CSLel * next;
  char data;
};

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

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

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

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

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

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

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

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

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

  l_print(head);
  for(i = 'A'; i <= 'G'; i++)
  {
    l_push(head, i);
    l_print(head);
  }
  while(head)
  {
    l_pop(head);
    l_print(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 CSLel
  next As CSLel Ptr
  data  As String * 1
End Type

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

  c = 0
  p = head

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

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

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

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

  p = new CSLel
  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 CSLel Ptr)
  Dim p As CSLel 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 CSLel Ptr
Dim i As Integer

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

While head
  l_pop(head)
  l_print(head)
Wend

End
Python (dodatek) 
# Program testowy dla list
# cyklicznych jednokierunkowych
# Data: 11.05.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------


# klasa elementu listy cyklicznej
# jednokierunkowej
class CSLel:


    def __init__(self, data):
        self.next = None
        self.data = data


# klasa listy cyklicznej
# jednokierunkowej
class CSLvar:


    # Konstruktor
    def __init__(self):
        self.head = None


    # destruktor
    def __del__(self):
        while self.head:
            self.l_pop()


    # zliczanie elementów
    def l_len(self):
        c = 0
        p = self.head
        if p:
            while True:
                c += 1
                p = p.next
                if self.head is p:
                    break
        return c


    # wyświetla elementy
    def l_print(self):
        print("%3d [ " % self.l_len(), end="")
        p = self.head
        if p:
            while True:
                print(p.data, end=" ")
                p = p.next
                if p is self.head:
                    break
        print("]")


    # wstawia element
    def l_push(self, v):
        p = CSLel(v)
        if self.head:
            p.next = self.head.next
            self.head.next = p
        else:
            p.next = p
        self.head = p


    # usuwa element
    def l_pop(self):
        if self.head:
            p = self.head.next
            self.head.next = p.next
            if p.next is p:
                self.head = None


#---------------
# Program główny
#---------------

cl = CSLvar()
cl.l_print()
for i in range(ord('A'), ord('G')+1):
    cl.l_push(chr(i))
    cl.l_print()
while cl.head:
    cl.l_pop()
    cl.l_print()
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 

Wersja obiektowa

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

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

program ccslist_object;

// Typ elementów listy
//--------------------
type
  PCSLel = ^CSLel;

  CSLel =  record
    next  : PCSLel;
    data  : char;
  end;

// Obiekt listy cyklicznej jednokierunkowej
//-----------------------------------------
  CSLvar = object
    public
      head : PCSLel;  // punkt wejścia
      constructor init;
      destructor  destroy;
      function    l_len : cardinal;
      procedure   l_print;
      procedure   l_push(v : char);
      procedure   l_pop;
  end;

// Metody obiektu CSLvar
//-------------------------

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

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

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


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

// Wstawia nowy element
//---------------------
procedure CSLvar.l_push(v : char);
var
  p : PCSLel;
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 CSLvar.l_pop;
var
  p : PCSLel;
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 : CSLvar;
  i : char;
begin
  L.init;
  L.l_print;
  for i := 'A' to 'G' do
  begin
    L.l_push(i);
    L.l_print;
  end;
  while L.head <> nil do
  begin
    L.l_pop;
    L.l_print;
  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 CSLel
{
  CSLel * next;
  char data;
};

// Definicja obiektu listy dwukierunkowej
//---------------------------------------
class CSLvar
{
  public:
    CSLel * head; // punkt wejścia
    CSLvar(); // konstruktor
    ~CSLvar(); // destruktor
    unsigned l_len();
    void     l_print();
    void     l_push(char v);
    void     l_pop();
};

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

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

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

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
unsigned CSLvar::l_len()
{
  unsigned  c = 0;
  CSLel * p = head;

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

// Wyświetla kolejne elementy listy
//---------------------------------
void CSLvar::l_print()
{
   CSLel * p;

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

// Wstawia nowy element
//---------------------
void CSLvar::l_push(char v)
{
  CSLel * p = new CSLel;

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

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

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

int main()
{
  CSLvar L;
  char i;

  L.l_print();
  for(i = 'A'; i <= 'G'; i++)
  {
    L.l_push(i);
    L.l_print();
  }
  while(L.head)
  {
    L.l_pop();
    L.l_print();
  }

  return 0;
}
Basic
' Obiekt listy cyklicznej jednokierunkowej
' Data: 16.02.2012
' (C)2020 mgr Jerzy Wałaszek
'----------------------------------------

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

' Typ obiektowy listy cyklicznej jednokierunkowej
'------------------------------------------------
Type CSLvar
  head As CSLel Ptr
 
  Declare Constructor()
  Declare Destructor()
  Declare Function l_len() As UInteger
  Declare Sub l_print()
  Declare Sub l_push(v As String)
  Declare Sub l_pop()
End Type

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

Dim L As CSLvar
Dim i As Integer

L.l_print()
For i = Asc ("A") To Asc ("G")
  L.l_push(Chr(i))
  L.l_print()
Next

While L.head
  L.l_pop()
  L.l_print()
Wend

End

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

' Usuwa listę z pamięci
Destructor CSLvar()
  While head
    l_pop()
  Wend
End Destructor

' Funkcja oblicza liczbę elementów listy
'---------------------------------------
Function CSLvar.l_len() As UInteger
  Dim c As UInteger
  Dim p As CSLel Ptr

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

' Wyświetla kolejne elementy listy
'---------------------------------
Sub CSLvar.l_print()
  Dim p As CSLel Ptr

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

' Wstawia nowy element
'---------------------
Sub CSLvar.l_push(v As String)
  Dim p As CSLel Ptr

  p = new CSLel
  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 CSLvar.l_pop()
  Dim p As CSLel 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 
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 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.