Operacje na listach jednokierunkowych


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
  Przejście przez listę
Liczba elementów listy
Dodawanie elementu na początku listy
Usuwanie elementów z początku listy
Dodawanie elementu na koniec listy
Usuwanie ostatniego elementu listy
Dodawanie nowego elementu przed wybranym elementem listy
Dodawanie nowego elementu za elementem wybranym
Usuwanie wybranego elementu listy
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 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

Lazarus Code::Blocks Free 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

 

Przejście przez listę

Przechodzenie listy – ma na celu przejście kolejno przez wszystkie elementy listy, począwszy od pierwszego, a skończywszy na ostatnim. Operacja ta jest częścią składową wielu innych operacji, gdzie algorytm musi coś wyszukać na liście. W przypadku listy jednokierunkowej możemy się po niej poruszać tylko w jednym kierunku: od początku do końca. Z uwagi na sposób powiązania ze sobą elementów listy, do jej przechodzenia potrzebna jest zmienna typu wskaźnik, która będzie wskazywała na kolejne elementy. Na początku algorytmu zmienna ta powinna wskazywać pierwszy element na liście. W pętli przetwarzamy element wskazywany przez tą zmienną, po czym za nową wartość zmiennej przyjmuje się adres następnego elementu listy. Adres ten jest przechowywany w polu next elementu bieżącego. Listę przechodzimy do momentu, aż zmienna wskazująca przyjmie wartość 0. Stanie się tak po wyjściu z ostatniego elementu listy, w którego polu next przechowywany jest adres 0.

 

Algorytm przechodzenia przez listę jednokierunkową

Wejście
p  –  wskazanie początku listy jednokierunkowej, czyli adres pierwszego elementu na liście
Wyjście:

Przejście przez wszystkie elementy listy

Lista kroków:
K01: Dopóki p ≠ nil, wykonuj kroki K02...K03 ; w pętli przechodzimy przez kolejne elementy listy
K02:     Przetwarzaj element wskazywany przez p  
K03:     p ← (pnext) ; w p umieść zawartość pola next elementu wskazywanego przez p
K04: Zakończ  

 

Lazarus Code::Blocks Free Basic
while p <> nil do
begin
  ...
  p := p^.next;
end;
while(p)
{
  ...
  p = p->next;
}
While p
  ...
  p = p->next
Wend

 

Liczba elementów listy

Problem liczby elementów listy rozwiązujemy za pomocą algorytmu przejścia przez listę. Tworzymy licznik, któremu na początku nadajemy wartość 0. Następnie przechodzimy kolejno przez wszystkie elementy na liście. Przy każdym mijanym elemencie zwiększamy licznik o 1. Po przejściu całej listy w liczniku będzie liczba elementów.

 

Algorytm wyznaczania liczby elementów na liście jednokierunkowej

Wejście
p  –  wskazanie listy jednokierunkowej
Wyjście:
c  –  liczba elementów
Lista kroków:
K01: c ← 0 ; zerujemy licznik
K02: Dopóki p ≠ nil, wykonuj kroki K03...K04 ; w pętli przechodzimy przez kolejne elementy listy
K03:     cc + 1 ; zwiększ licznik
K04:     p ← (pnext) ; w p umieść zawartość pola next elementu wskazywanego przez p
K05: Zakończ z wynikiem c ; koniec, wynik w c

 

Lazarus
function l_size(p : PslistEl) : cardinal;
var
  c : cardinal;
begin
  c := 0;       // zerujemy licznik

  while p <> nil do
  begin
    inc(c);     // zwiększamy licznik o 1
    p := p^.next;
  end;

  l_size := c;
end;
Code::Blocks
unsigned l_size(slistEl * p)
{
  unsigned c = 0; // zerujemy licznik

  while(p)
  {
    c++;     // zwiększamy licznik o 1
    p = p->next;
  }

  return c;
}
Free Basic
Function l_size(p As slistEl Ptr) As UInteger

  Dim c As UInteger

  c = 0         ' zerujemy licznik

  While p
    c += 1      ' zwiększamy licznik o 1
    p = p->next
  Wend

  l_size = c
End Function

 

Dodawanie elementu na początku listy

Załóżmy, iż mamy daną listę trójelementową. Naszym zadaniem jest dodanie nowego elementu na początku tej listy. Postępujemy wg następującego schematu:

Tworzymy dynamicznie w pamięci nowy element listy (na rysunku w kolorze zielonym). Wprowadzamy do niego dane dla pola data.

W polu next nowego elementu umieszczamy adres przechowywany przez zmienną head. W ten sposób następnikiem nowego elementu stanie się obecny pierwszy element listy.

W zmiennej head umieszczamy adres nowego elementu. Po tej operacji początkiem listy staje się nowo utworzony element.

 

Algorytm dołączania nowego elementu na początek listy jednokierunkowej

Wejście
head  –  zmienna wskazująca początek listy
v   wartość wprowadzana do elementu
Wyjście:

Lista z dołączonym na początku elementem o wartości v.

Dane pomocnicze:
p  –  wskazanie elementu listy
Lista kroków:
K01: Utwórz nowy element listy  
K02: p ← adres nowego elementu  
K03: (pdata) ← v ; umieszczamy dane w elemencie
K04: (pnext) ← head ; następnikiem będzie bieżący pierwszy element listy
K05: headp ; ustawiamy początek listy na nowy element
K06: Zakończ  

 

Uwaga:

Elementy są umieszczone na liście w kierunku odwrotnym do kolejności ich wstawiania – ostatnio wstawiony element jest pierwszym elementem listy. Taka struktura pozwala prosto realizować stos.

 

Lazarus
procedure l_push_front(var head : PslistEl; v : char);
var
  p : PslistEl;
begin
  new(p);           // tworzymy nowy element
  p^.data := v;     // inicjujemy element
  p^.next := head;
  head := p;
end;
Code::Blocks
void l_push_front(slistEl * & head, char v)
{
  slistEl * p = new slistEl;

  p->data = v;    // inicjujemy element
  p->next = head;
  head = p;
}
Free Basic
Sub l_push_front(ByRef head As slistEl Ptr, v As String)

  Dim p As slistEl Ptr

  p = new slistEl  ' tworzymy nowy element
  p->data = v      ' inicjujemy element
  p->next = head
  head = p
End Sub

 

Usuwanie elementu z początku listy

Jeśli lista jest pusta, to nic nie robimy.

Załóżmy, że mamy daną listę, z której początku należy usunąć element zaznaczony na rysunku kolorem czerwonym.

W zmiennej head umieszczamy zawartość pola next usuwanego elementu. W ten sposób początek listy rozpocznie się w następniku, a usuwany element zostanie wyłączony z listy.

Odłączony element usuwamy z pamięci.

Otrzymujemy listę bez pierwszego elementu.

 

Algorytm usuwania elementu z początku listy jednokierunkowej

Wejście
head  –  zmienna wskazująca początek listy
Wyjście:

Lista bez pierwszego elementu.

Dane pomocnicze:
p  –  wskazanie elementu listy
Lista kroków:
K01: p ← head ; zapamiętaj pierwszy element
K02 Jeśli p = nil, to zakończ ; zakończ, jeśli lista jest pusta
K03: head ← (pnext) ; początkiem listy będzie element następny
K04: Usuń z pamięci element wskazany przez p  
K05: Zakończ  

 

Lazarus
procedure l_pop_front(var head : PslistEl);
var
  p : PslistEl;
begin
  p := head;      // zapamiętujemy początek
  if p <> nil then
  begin
    head := p^.next; // nowy początek
    dispose(p);   // usuń element z pamięci
  end;
end;
Code::Blocks
void l_pop_front(slistEl * & head)
{
  slistEl * p;
  p = head;     // zapamiętujemy początek
  if(p)
  {
    head = p->next; // nowy początek
    delete p;    // usuń element z pamięci
  }
}
Free Basic
Sub l_pop_front(ByRef head As slistEl Ptr)

  Dim p As slistEl Ptr

  p = head       ' zapamiętujemy początek
  If p Then
    head = p->next  ' nowy początek
    Delete p     ' usuń element z pamięci
  End If
End Sub

 

Dla prostych zastosowań podane powyżej operacje dla list jednokierunkowych zwykle wystarczają. W dalszej części artykułu rozszerzamy tę listę o kolejne operacje.

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.

 

Poniższy program implementuje listę jednokierunkową. Elementy tej listy będą przechowywały znaki. Najpierw umieszczamy na liście kolejno litery A, B i C, następnie usuwamy z początku listy dwa elementy. Za każdym razem zawartość listy jest wyświetlana.

 

Lazarus
// Program testowy dla list jednokierunkowych
// Data: 11.02.2012
// (C)2012 mgr Jerzy Wałaszek
//-------------------------------------------

program slist_test1;

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

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

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function l_size(p : PslistEl) : cardinal;
var
  c : cardinal;
begin
  c := 0;
  while p <> nil do
  begin
    inc(c);
    p := p^.next;
  end;
  l_size := c;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure l_printl(p : PslistEl);
var
  i : cardinal;
begin
  writeln('Number of elements : ',l_size(p));
  i := 1;
  while p <> nil do
  begin
    writeln('Element #',i,'  data = ',p^.data);
    inc(i);
    p := p^.next;
  end;
  writeln;
end;

// Procedura dołączania na początek listy
//---------------------------------------
procedure l_push_front(var head : PslistEl; v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.data := v;
  p^.next := head;
  head := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure l_pop_front(var head : PslistEl);
var
  p : PslistEl;
begin
  p := head;
  if p <> nil then
  begin
    head := p^.next;
    dispose(p);
  end;
end;

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

var
  L : PslistEl;   // zawiera adres początku listy

begin
  L := nil;
  l_push_front(L,'A');
  l_push_front(L,'B');
  l_push_front(L,'C');
  l_printl(L);
  l_pop_front(L);
  l_pop_front(L);
  l_printl(L);
end.
Code::Blocks
// Program testowy dla list jednokierunkowych
// Data: 11.02.2012
// (C)2012 mgr Jerzy Wałaszek
//-------------------------------------------

#include <iostream>

using namespace std;

// Typ elementów listy
//--------------------
struct slistEl
{
  slistEl * next;
  char data;
};

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

  while(p)
  {
    c++;
    p = p->next;
  }
  return c;
}

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void l_printl(slistEl * p)
{
  unsigned i;

  cout << "Number of elements : " << l_size(p) << endl;

  for(i = 1; p; p = p->next)
    cout << "Element #" << i++ << "  data = " << p->data << endl;
  cout << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void l_push_front(slistEl * & head, char v)
{
  slistEl * p;

  p = new slistEl;
  p->data = v;
  p->next = head;
  head = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void l_pop_front(slistEl * & head)
{
  slistEl * p = head;

  if(p)
  {
    head = p->next;
    delete p;
  }
}

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

int main()
{
  slistEl * L = NULL;

  l_push_front(L,'A');
  l_push_front(L,'B');
  l_push_front(L,'C');
  l_printl(L);
  l_pop_front(L);
  l_pop_front(L);
  l_printl(L);

  return 0;
}
Free Basic
' Program testowy dla list jednokierunkowych
' Data: 11.02.2012
' (C)2012 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(p As slistEl Ptr) As UInteger

  Dim c As UInteger

  c = 0
  While p
    c += 1
    p = p->next
  Wend
  l_size = c
End Function

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub l_printl(p As slistEl Ptr)
  
  Dim i As UInteger
  
  Print "Number of elements : ";l_size(p)
  i = 1
  While p
    Print "Element #";i;"  data = ";p->data
    i += 1
    p = p->next
  Wend
  Print
End Sub

' Procedura dołączania na początek listy
'---------------------------------------
Sub l_push_front(ByRef head As slistEl Ptr, v As String)

  Dim p As slistEl Ptr

  p = new slistEl
  p->data = v
  p->next = head
  Head = p
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub l_pop_front(ByRef head As slistEl Ptr)

  Dim p As slistEl Ptr

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

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

Dim L As slistEl Ptr

L = 0

l_push_front(L,"A")
l_push_front(L,"B")
l_push_front(L,"C")
l_printl(L)

l_pop_front(L)
l_pop_front(L)
l_printl(L)

End
Wynik
Number of elements : 3
Element #1  data = C
Element #2  data = B
Element #3  data = A

Number of elements : 1
Element #1  data = A

 


Dodawanie elementu na koniec listy

    

Tworzymy nowy element. W polu next umieszczamy adres zero – ostatni element listy nie posiada następnika.

Jeśli lista jest pusta, to head zawiera adres zero. W takim przypadku adres nowego elementu umieszczamy w zmiennej head. Nowy element staje się jednocześnie pierwszym i ostatnim elementem listy.

Jeśli lista zawiera elementy, to przechodzimy do ostatniego z nich (za pomocą podanego wcześniej algorytmu przejścia).

W polu next ostatniego elementu umieszczamy adres nowego elementu. W ten sposób nowy element staje się częścią listy i jest umieszczony na jej końcu.

Lista zostaje wydłużona o nowy element.

 

Algorytm dołączania nowego elementu do końca listy jednokierunkowej

Wejście
head  –  zmienna wskazująca początek listy
v  – wartość umieszczana w elemencie listy
Wyjście:

Lista z dołączonym na końcu nowym elementem o wartości v

Dane pomocnicze:
p,e  –  wskazania elementu listy
Lista kroków:
K01: Utwórz nowy element  
K02: e ← adres nowego elementu  
K03: (enext) ← nil ; inicjujemy pola nowego elementu
K04: (edata) ← v  
K05; phead ; w p ustawiamy początek listy
K06: Jeśli p ≠ nil, to idź do K09 ; czy lista jest pusta?
K07: heade ; jeśli tak, to nowy element będzie pierwszym elementem listy
K08: Zakończ  
K09: Dopóki (pnext) ≠ nil, wykonuj p ← (pnext) ; inaczej przechodzimy do ostatniego elementu listy
K10: (pnext) ← e ; dołączamy nowy element za ostatnim na liście
K11: Zakończ  

 

Lazarus
procedure l_push_back(var head : PslistEl; v : char);
var
  p,e : PslistEl;
begin
  new(e);         // tworzymy nowy element
  e^.next := nil; // inicjujemy element
  e^.data := v;
  p := head;
  if p = nil then
    head := e
  else
  begin
    while p^.next <> nil do p := p^.next;
    p^.next := e;
  end;
end;
Code::Blocks
void l_push_back(slistEl * & head, char v)
{
  slistEl * p, * e;

  e = new slistEl;  // tworzymy nowy element
  e->next = NULL;   // inicjujemy element
  e->data = v;
  p = head;
  if(p)
  {
     while(p->next) p = p->next;
     p->next = e;
  }
  else head = e;
}
Free Basic
Sub l_push_back(ByRef head As slistEl Ptr, v As String)

  Dim As slistEl Ptr p,e

  e = New slistEl  ' tworzymy nowy element
  e->next = 0      ' inicjujemy element
  e->data = v
  p = head
  If p = 0 Then
    head = e
  Else
    While p->next
      p = p->next
    Wend
    p->next = e
  End If
End Sub

 

Usuwanie ostatniego elementu listy

Jeśli lista jest pusta, nic nie robimy. W przeciwnym razie sprawdzamy, czy lista zawiera tylko jeden element. Rozpoznamy to po tym, iż pole next pierwszego elementu zawiera adres zero.

Jeśli tak, to w zmiennej head umieszczamy adres zero. Spowoduje to odłączenie elementu od listy (oczywiście adres tego elementu musimy wcześniej zapamiętać, gdyż inaczej stracimy do niego dostęp!)..

Odłączony element usuwamy z listy. Lista pozostaje pusta. Kończymy.

Jeśli lista nie jest pusta, to naszym zadaniem staje się usunięcie ostatniego jej elementu, który zaznaczyliśmy na rysunku kolorem czerwonym. Przechodzimy na liście do przedostatniego elementu – przedostatni element rozpoznamy po tym, iż pole next jego następnika zawiera adres zero.

Usuwamy z pamięci element wskazywany przez pole next przedostatniego elementu listy.

W polu next elementu przedostatniego (który teraz staje się elementem ostatnim listy) umieszczamy adres zero. W ten sposób lista staje się krótsza o jeden element.

 

Algorytm usuwania elementu z końca listy jednokierunkowej

Wejście
head  –  zmienna wskazująca początek listy
Wyjście:

Lista z usuniętym ostatnim elementem

Dane pomocnicze:
p  –  wskazania elementu listy
Lista kroków:
K01: phead ; pobieramy do p adres początku listy
K02: Jeśli p = nil, to zakończ ; jeśli lista jest pusta, kończymy
K03: Jeśli (pnext) ≠ nil, to idź do K07 ; sprawdzamy, czy lista jest jednoelementowa
K04: Usuń z pamięci element wskazywany przez p  
K05; head ← nil ; lista jednoelementowa staje się listą pustą
K06: Zakończ  
K07: Dopóki ((pnext)→next) ≠ nil, wykonuj p ← (pnext) ; idziemy do przedostatniego elementu
K08: Usuń z pamięci element wskazywany przez (pnext) ; usuwamy następny element, czyli ostatni
K09: (pnext) ← nil ; przedostatni element nie ma już następnika
K10: Zakończ  

 

Lazarus
procedure l_pop_back(var head : PslistEl);
var
  p : PslistEl;
begin
  p := head;
  if p <> nil then
  begin
    if p^.next <> nil then
    begin
      while p^.next^.next <> nil do
        p := p^.next;
      dispose(p^.next);
      p^.next := nil;
    end
    else
    begin
      dispose(p);  // lista jednoelementowa
      head := nil; // staje się listą pustą
    end
  end;
end;
Code::Blocks
void l_pop_back(slistEl * & head)
{
  slistEl * p = head;
  if(p)
  {
    if(p->next)
    {
      while(p->next->next) p = p->next;
      delete p->next;
      p->next = NULL;
    }
    else
    {
      delete p;    // lista jednoelementowa
      head = NULL; // staje się listą pustą
    }
  }
}
Free Basic
Sub l_pop_back(ByRef head As slistEl Ptr)

  Dim p As slistEl Ptr

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

 

Dodawanie nowego elementu przed wybranym elementem listy

Jeśli wybranym elementem jest pierwszy element listy, to operacja sprowadza się do opisanej wcześniej operacji dodawania elementu na początku listy.

Załóżmy, że wybranym elementem nie jest pierwszy element na liście, lecz dowolny z następnych. Na rysunku zaznaczono go kolorem jasnoniebieskim.

Znajdujemy poprzednik elementu wybranego – listę przechodzimy dotąd, aż pole next przetwarzanego elementu będzie zawierało adres elementu wybranego. Poprzednik elementu wybranego zaznaczyliśmy kolorem żółtym.

Tworzymy dynamicznie nowy element (na rysunku zaznaczony kolorem zielonym) i jego adres umieszczamy w polu next poprzednika elementu wybranego. W ten sposób nowy element stanie się elementem następnym poprzednika. Lista chwilowo zostanie rozdzielona.

W polu next nowego elementu umieszczamy adres elementu wybranego. W ten sposób nowy element zostanie umieszczony na liście przed elementem wybranym.

 

Algorytm dołączania nowego elementu przed wybranym elementem listy jednokierunkowej

Wejście
head  –  zmienna wskazująca początek listy
e  – wskazanie elementu listy, przed którym ma zostać wstawiony nowy element
v  – dane dla nowego elementu
Wyjście:

Lista z nowym elementem wstawionym przed element wskazywany przez e.

Dane pomocnicze:
p  –  wskazania elementu listy
Lista kroków:
K01: phead ; pobieramy do p adres początku listy
K02: Jeśli pe, to idź do K05 ; sprawdzamy, czy e nie jest pierwszym elementem listy
K03: Wstaw nowy element na początku listy  
K04: Zakończ  
K05; Dopóki (pnext) ≠ e, wykonuj p ← (pnext) ; przechodzimy do elementu poprzedzającego e
K06: Utwórz nowy element  
K07: (pnext) ← adres nowego elementu ; nowy element wstawiamy za element poprzedzający
K08: ((pnext)→next) ← e ; inicjujemy nowy element
K09: ((pnext)→data) ← v  
K10: Zakończ  

 

Lazarus
procedure l_insert_before(var head : PslistEl; e : PslistEl; v : char);
var
  p : PslistEl;
begin
  p := head;
  if p = e then l_push_front(head,v)
  else
  begin
    while p^.next <> e do p := p^.next;
    new(p^.next);
    p^.next^.next := e;
    p^.next^.data := v;
  end;
end;
Code::Blocks
void l_insert_before(slistEl * & head, slistEl * e, char v)
{
  slistEl * p = head;

  if(p == e) l_push_front(head,v);
  else
  {
    while(p->next != e) p = p->next;
    p->next = new slistEl;
    p->next->next = e;
    p->next->data = v;
  }
}
Free Basic
Sub l_insert_before(ByRef head As slistEl Ptr, e As slistEl Ptr, v As String)

  Dim p As slistEl Ptr

  p = head
  If p = e Then
  	 l_push_front(head,v)
  Else
    While p->next <> e
      p = p->next
    Wend
    p->next = New slistEl
    p->next->next = e
    p->next->data = v
  End If
End Sub

 

Dodawanie nowego elementu za elementem wybranym

Zadanie mamy znacznie uproszczone w porównaniu z poprzednim. Załóżmy, że wybrany element jest dowolnym elementem listy, nieważne którym.

Tworzymy dynamicznie w pamięci nowy element.

W polu next nowego elementu umieszczamy zawartość pola next elementu wybranego. W ten sposób następnikiem nowego elementu będzie następnik elementu wybranego.

W polu next elementu wybranego umieszczamy adres nowego elementu. Nowy element zostaje umieszczony na liście za elementem wybranym.

 

Algorytm dołączania nowego elementu za wybranym elementem listy jednokierunkowej

Wejście
e  –  wskazanie elementu listy, za którym ma zostać wstawiony nowy element
v  – dane dla nowego elementu
Wyjście:

Lista z nowym elementem wstawionym za elementem wskazywanym przez e.

Dane pomocnicze:
p  –  wskazania elementu listy
Lista kroków:
K01: Utwórz nowy element  
K02: p ← adres nowego elementu  
K03: (pnext) ← (enext) ; następnym elementem za nowym będzie następny element za e
K04: (pdata) ← v  
K05; (enext) ← p ; nowy element wstawiamy za e
K06: Zakończ  

 

Lazarus
procedure l_insert_after(e : PslistEl; v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.next := e^.next;
  p^.data := v;
  e^.next := p;
end;
Code::Blocks
void l_insert_after(slistEl * e, char v)
{
  slistEl * p = new slistEl;

  p->next = e->next;
  p->data = v;
  e->next = p;
}
Free Basic
Sub l_insert_after(e As slistEl Ptr, v As String)

  Dim p As slistEl Ptr

  p = new slistEl
  p->next = e->next
  p->data = v
  e->next = p
End Sub

 

Usuwanie wybranego elementu listy

Jeśli wybranym do usunięcia elementem jest pierwszy na liście, to wykorzystujemy podany wcześniej algorytm usuwania pierwszego elementu listy.

Załóżmy, że usuwany element nie jest pierwszym elementem listy.

Skoro tak, to posiada on poprzedniki. Znajdujemy poprzednik wybranego elementu – na rysunku zaznaczyliśmy go na zielono.

W polu next poprzednika umieszczamy zawartość pola next usuwanego elementu. W ten sposób poprzednik będzie wskazywał na następnik wybranego elementu, a sam element wybrany znajdzie się poza listą.

Wybrany element można usunąć z pamięci.

 

Algorytm usuwania wybranego elementu listy jednokierunkowej

Wejście
head  –  zmienna wskazująca początek listy
e  – wskazanie elementu listy do usunięcia
Wyjście:

Lista bez elementu wskazywanego przez e.

Dane pomocnicze:
p  –  wskazania elementu listy
Lista kroków:
K01: Jeśli heade, to idź do K04 ; sprawdzamy, czy usuwany element jest pierwszym na liście
K02: Usuń pierwszy element listy ; jeśli tak, usuwamy go z listy
K03: Zakończ  
K04: phead ; w p ustawiamy początek listy
K05: Dopóki (pnext) ≠ e, wykonuj p ←  (pnext) ; w p ustawiamy adres elementu poprzedzającego e
K06: (pnext) ← (enext) ; odłączamy e od listy
K07: Usuń z pamięci element wskazywany przez e  
K08: Zakończ  

 

Lazarus
procedure l_remove(var head : PslistEl; e : PslistEl);
var
  p : PslistEl;
begin
  if head = e then l_pop_front(head)
  else
  begin
    p := head;
    while p^.next <> e do p := p^.next;
    p^.next := e^.next;
    dispose(e);
  end;
end;
Code::Blocks
void l_remove(slistEl * & head, slistEl * e)
{
  slistEl * p;

  if(head == e) l_pop_front(head);
  else
  {
    p = head;
    while(p->next != e) p = p->next;
    p->next = e->next;
    delete e;
  }
}
Free Basic
Sub l_remove(ByRef head As slistEl Ptr, e As slistEl Ptr)

  Dim p As slistEl Ptr

  If head = e Then
    l_pop_front(head)
  Else
    p = head
    While p->next <> e
      p = p->next
    Wend
    p->next = e->next
    Delete e
  End If
End Sub

 

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.

 

Poniższy program demonstruje opisane operacje na liście jednokierunkowej. Tworzy on listę kolejnych liter od A do G (7 elementów). Następnie wybiera element z literą D i wstawia przed nim + a za nim *. Na końcu z listy jest usuwany element D, pierwszy i ostatni. Po każdej operacji zawartość listy zostaje wyświetlona.

 

Lazarus
// Program testowy dla list jednokierunkowych
// Data: 7.02.2012
// (C)2012 mgr Jerzy Wałaszek
//-------------------------------------------

program slist_test2;

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

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

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function l_size(p : PslistEl) : cardinal;
var
  c : cardinal;
begin
  c := 0;       // zerujemy licznik
  while p <> nil do
  begin
    inc(c);     // zwiększamy licznik o 1
    p := p^.next;
  end;
  l_size := c;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure l_printl(p : PslistEl);
var
  i : integer;    // licznik elementów
begin
  writeln('Number of elements : ',l_size(p));

  i := 1;         // licznik ustawiamy na 1

  // W petli przechodzimy przez kolejne elementy listy
  // i wyświetlamy zawartość ich pola danych

  while p <> nil do
  begin
    writeln('Element #',i,'  data = ',p^.data);
    inc(i);       // Zwiększamy licznik elementów o 1
    p := p^.next; // Przechodzimy do następnego elementu listy
  end;
  writeln;        // Odstęp
end;

// Procedura dołączania na początek listy
//---------------------------------------
procedure l_push_front(var head : PslistEl; v : char);
var
  p : PslistEl;
begin
  new(p);          // tworzymy nowy element
  p^.data := v;    // inicjujemy element
  p^.next := head;
  head := p;
end;

// Procedura dołączania na koniec listy
//-------------------------------------
procedure l_push_back(var head : PslistEl; v : char);
var
  p,e : PslistEl;
begin
  new(e);         // tworzymy nowy element
  e^.next := nil; // inicjujemy element
  e^.data := v;
  p := head;
  if p = nil then
    head := e
  else
  begin
    while p^.next <> nil do p := p^.next;
    p^.next := e;
  end;
end;

// Procedura dołączania przed elementem e
//---------------------------------------
procedure l_insert_before(var head : PslistEl; e : PslistEl; v : char);
var
  p : PslistEl;
begin
  p := head;
  if p = e then l_push_front(head,v)
  else
  begin
    while p^.next <> e do p := p^.next;
    new(p^.next);
    p^.next^.next := e;
    p^.next^.data := v;
  end;
end;

// Procedura dołączania za elementem e
//------------------------------------
procedure l_insert_after(e : PslistEl; v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.next := e^.next;
  p^.data := v;
  e^.next := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure l_pop_front(var head : PslistEl);
var
  p : PslistEl;
begin
  p := head;         // zapamiętujemy początek
  if p <> nil then
  begin
    head := p^.next; // nowy początek
    dispose(p);      // usuń element z pamięci
  end;
end;

// Procedura usuwa ostatni element
//---------------------------------
procedure l_pop_back(var head : PslistEl);
var
  p : PslistEl;
begin
  p := head;
  if p <> nil then
  begin
    if p^.next <> nil then
    begin
      while p^.next^.next <> nil do
        p := p^.next;
      dispose(p^.next);
      p^.next := nil;
    end
    else
    begin
      dispose(p);   // lista jednoelementowa
      head := nil;  // staje się listą pustą
    end
  end;
end;

// Procedura usuwa wybrany element
//--------------------------------
procedure l_remove(var head : PslistEl; e : PslistEl);
var
  p : PslistEl;
begin
  if head = e then l_pop_front(head)
  else
  begin
    p := head;
    while p^.next <> e do p := p^.next;
    p^.next := e^.next;
    dispose(e);
  end;
end;

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

var
  L : PslistEl; // zawiera adres początku listy
  e : PslistEl; // do wskazywania elementów listy
  i : char;

begin
  L := nil;

  for i := 'A' to 'G' do l_push_back(L,i);
  l_printl(L);

  // Przechodzimy do elementu o wartości D

  e := L;

  for i := 'A' to 'C' do e := e^.next;

  // Przed elementem D umieszczamy +

  l_insert_before(L,e,'+');

  // Za elementem D umieszczamy *

  l_insert_after(e,'*');
  l_printl(L);

  // Usuwamy element D oraz element pierwszy i ostatni

  l_remove(L,e);
  l_pop_front(L);
  l_pop_back(L);
  l_printl(L);

end.
Code::Blocks
// Program testowy dla list jednokierunkowych
// Data: 11.02.2012
// (C)2012 mgr Jerzy Wałaszek
//-------------------------------------------

#include <iostream>

using namespace std;

// Typ elementów listy
//--------------------
struct slistEl
{
  slistEl * next;
  char data;
};

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

  while(p)
  {
    c++;     // zwiększamy licznik o 1
    p = p->next;
  }
  return c;
}

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void l_printl(slistEl * p)
{
  unsigned i;    // licznik elementów

  cout << "Number of elements : " << l_size(p) << endl;

  // W petli przechodzimy przez kolejne elementy listy
  // i wyświetlamy zawartość ich pola danych

  for(i = 1; p; p = p->next)
    cout << "Element #" << i++ << "  data = " << p->data << endl;
  cout << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void l_push_front(slistEl * & head, char v)
{
  slistEl * p;

  p = new slistEl;  // tworzymy nowy element
  p->data = v;      // inicjujemy element
  p->next = head;
  head = p;
}

// Procedura dołączania na koniec listy
//---------------------------------------
void l_push_back(slistEl * & head, char v)
{
  slistEl * p, * e;

  e = new slistEl;  // tworzymy nowy element
  e->next = NULL;   // inicjujemy element
  e->data = v;
  p = head;
  if(p)
  {
     while(p->next) p = p->next;
     p->next = e;
  }
  else head = e;
}

// Procedura dołączania przed elementem e
//---------------------------------------
void l_insert_before(slistEl * & head, slistEl * e, char v)
{
  slistEl * p = head;

  if(p == e) l_push_front(head,v);
  else
  {
    while(p->next != e) p = p->next;
    p->next = new slistEl;
    p->next->next = e;
    p->next->data = v;
  }
}

// Procedura dołączania za elementem e
//------------------------------------
void l_insert_after(slistEl * e, char v)
{
  slistEl * p = new slistEl;

  p->next = e->next;
  p->data = v;
  e->next = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void l_pop_front(slistEl * & head)
{
  slistEl * p = head; // zapamiętujemy początek

  if(p)
  {
    head = p->next;   // nowy początek
    delete p;         // usuń element z pamięci
  }
}

// Procedura usuwa ostatni element
//---------------------------------
void l_pop_back(slistEl * & head)
{
  slistEl * p = head; // zapamiętujemy początek

  if(p)
  {
    if(p->next)
    {
      while(p->next->next) p = p->next;
      delete p->next;
      p->next = NULL;
    }
    else
    {
      delete p;
      head = NULL;
    }
  }
}

// Procedura usuwa wybrany element
//--------------------------------
void l_remove(slistEl * & head, slistEl * e)
{
  slistEl * p;

  if(head == e) l_pop_front(head);
  else
  {
    p = head;
    while(p->next != e) p = p->next;
    p->next = e->next;
    delete e;
  }
}

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

int main()
{
  slistEl * L = NULL; // zawiera adres początku listy
  slistEl * e;        // do wskazywania elementów listy
  char i;

  for(i = 'A'; i <= 'G'; i++) l_push_back(L,i);
  l_printl(L);

  // Przechodzimy do elementu o wartości D

  e = L;

  for(i = 'A'; i <= 'C'; i++) e = e->next;

  // Przed elementem D umieszczamy +

  l_insert_before(L,e,'+');

  // Za elementem D umieszczamy *

  l_insert_after(e,'*');
  l_printl(L);

  // Usuwamy element D oraz element pierwszy i ostatni

  l_remove(L,e);
  l_pop_front(L);
  l_pop_back(L);
  l_printl(L);

  return 0;
}
Free Basic
' Program testowy dla list jednokierunkowych
' Data: 11.02.2012
' (C)2012 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(p As slistEl Ptr) As UInteger

  Dim c As UInteger

  c = 0         ' zerujemy licznik
  While p
    c += 1      ' zwiększamy licznik o 1
    p = p->next
  Wend
  l_size = c
End Function

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub l_printl(p As slistEl Ptr)
  
  Dim i As UInteger       ' licznik elementów
  
  Print "Number of elements : ";l_size(p)

  i = 1 ' licznik ustawiamy na 1

  ' W pętli przechodzimy przez kolejne elementy listy
  ' i wyświetlamy zawartość ich pola danych

  While p
    Print "Element #";i;"  data = ";p->data
    i += 1       ' zwiększamy licznik elementów o 1
    p = p->next  ' przechodzimy do następnego elementu listy
  Wend
  
  Print
End Sub

' Procedura dołączania na początek listy
'---------------------------------------
Sub l_push_front(ByRef head As slistEl Ptr, v As String)

  Dim p As slistEl Ptr

  p = new slistEl  ' tworzymy nowy element
  p->data = v      ' inicjujemy element
  p->next = head
  head = p
End Sub

' Procedura dołączania na koniec listy
'-------------------------------------
Sub l_push_back(ByRef head As slistEl Ptr, v As String)

  Dim As slistEl Ptr p,e

  e = New slistEl  ' tworzymy nowy element
  e->next = 0      ' inicjujemy element
  e->data = v
  p = head
  If p = 0 Then
    head = e
  Else
    While p->next
      p = p->next
    Wend
    p->next = e
  End If
End Sub

' Procedura dołączania przed elementem e
'---------------------------------------
Sub l_insert_before(ByRef head As slistEl Ptr, e As slistEl Ptr, v As String)

  Dim p As slistEl Ptr

  p = head
  If p = e Then
    l_push_front(head,v)
  Else
    While p->next <> e
      p = p->next
    Wend
    p->next = New slistEl
    p->next->next = e
    p->next->data = v
  End If
End Sub

' Procedura dołączania za elementem e
'------------------------------------
Sub l_insert_after(e As slistEl Ptr, v As String)

  Dim p As slistEl Ptr

  p = new slistEl
  p->next = e->next
  p->data = v
  e->next = p
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub l_pop_front(ByRef head As slistEl Ptr)

  Dim p As slistEl Ptr

  p = head      ' zapamiętujemy początek
  If p Then
    head = p->next  ' nowy początek
    Delete p     ' usuń element z pamięci
  End If
End Sub

' Procedura usuwa ostatni element
'--------------------------------
Sub l_pop_back(ByRef head As slistEl Ptr)

  Dim p As slistEl Ptr

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

' Procedura usuwa wybrany element
'--------------------------------
Sub l_remove(ByRef head As slistEl Ptr, e As slistEl Ptr)

  Dim p As slistEl Ptr

  If head = e Then
    l_pop_front(head)
  Else
    p = head
    While p->next <> e
      p = p->next
    Wend
    p->next = e->next
    Delete e
  End If
End Sub

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

Dim L As slistEl Ptr ' zawiera adres początku listy
Dim e As slistEl Ptr ' do wskazywania elementów listy  
Dim i As Integer

L = 0

For i = Asc("A") To Asc("G")
  l_push_back(L,Chr(i))
Next
l_printl(L)

' Przechodzimy do elementu o wartości D

e = L
For i = 1 To 3
  e = e->next
Next

' Przed elementem D umieszczamy +

l_insert_before(L,e,"+")

' Za elementem D umieszczamy *

l_insert_after(e,"*")
l_printl(L)

' Usuwamy element D oraz element pierwszy i ostatni

l_remove(L,e)
l_pop_front(L)
l_pop_back(L)
l_printl(L)

End
Wynik
Number of elements : 7
Element #1  data = A
Element #2  data = B
Element #3  data = C
Element #4  data = D
Element #5  data = E
Element #6  data = F
Element #7  data = G

Number of elements : 9
Element #1  data = A
Element #2  data = B
Element #3  data = C
Element #4  data = +
Element #5  data = D
Element #6  data = *
Element #7  data = E
Element #8  data = F
Element #9  data = G

Number of elements : 6
Element #1  data = B
Element #2  data = C
Element #3  data = +
Element #4  data = *
Element #5  data = E
Element #6  data = F

 

Wersja obiektowa

W dalszych rozdziałach będziemy używali list jako obiektów ze względu na wygodę programowania. Obiekt jest strukturą danych, która posiada pola danych oraz funkcje i procedury obsługujące te pola. Do funkcji i procedur obiektu odwołujemy się identycznie jak do pól struktury. Każdy z wybranych przez nas języków programowania, tj. Pascal, C++ i Basic, pozwala bezproblemowo tworzyć obiekty. Poniższy program jest obiektową wersją ostatniego programu.

 

Lazarus
// Obiekt listy jednokierunkowej
// Data: 12.02.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

program slist_object;

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

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

// Definicja typu obiektowego slist
//---------------------------------
  slist = object
    public
      head : PslistEl;  // początek listy

      constructor init;
      destructor destroy;
      function size : cardinal;
      procedure printl;
      procedure push_front(v : char);
      procedure push_back(v : char);
      procedure insert_before(e : PslistEl; v : char);
      procedure insert_after(e : PslistEl; v : char);
      procedure pop_front;
      procedure pop_back;
      procedure remove(e : PslistEl);
  end;

//---------------------
// Metody obiektu slist
//---------------------

// Konstruktor - inicjuje pole head
//---------------------------------
constructor slist.init;
begin
  head := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor slist.destroy;
begin
  while head <> nil do pop_front;
end;

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function slist.size : cardinal;
var
  c : cardinal;
  p : PslistEl;
begin
  c := 0;
  p := head;
  while p <> nil do
  begin
    inc(c);
    p := p^.next;
  end;
  size := c;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure slist.printl;
var
  i : integer;
  p : PslistEl;
begin
  writeln('Number of elements : ',size);
  p := head;
  i := 1;
  while p <> nil do
  begin
    writeln('Element #',i,'  data = ',p^.data);
    inc(i);
    p := p^.next;
  end;
  writeln;
end;

// Procedura dołączania na początek listy
//---------------------------------------
procedure slist.push_front(v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.next := head;
  p^.data := v;
  head    := p;
end;

// Procedura dołączania na koniec listy
//-------------------------------------
procedure slist.push_back(v : char);
var
  p,e : PslistEl;
begin
  new(e);
  e^.next := nil;
  e^.data := v;
  p := head;
  if p = nil then
    head := e
  else
  begin
    while p^.next <> nil do p := p^.next;
    p^.next := e;
  end;
end;

// Procedura dołączania przed elementem e
//---------------------------------------
procedure slist.insert_before(e : PslistEl; v : char);
var
  p : PslistEl;
begin
  p := head;
  if p = e then push_front(v)
  else
  begin
    while p^.next <> e do p := p^.next;
    new(p^.next);
    p^.next^.next := e;
    p^.next^.data := v;
  end;
end;

// Procedura dołączania za elementem e
//------------------------------------
procedure slist.insert_after(e : PslistEl; v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.next := e^.next;
  p^.data := v;
  e^.next := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure slist.pop_front;
var
  p : PslistEl;
begin
  p := head;
  if p <> nil then
  begin
    head := p^.next;
    dispose(p);
  end;
end;

// Procedura usuwa ostatni element
//---------------------------------
procedure slist.pop_back;
var
  p : PslistEl;
begin
  p := head;
  if p <> nil then
  begin
    if p^.next <> nil then
    begin
      while p^.next^.next <> nil do
        p := p^.next;
      dispose(p^.next);
      p^.next := nil;
    end
    else
    begin
      dispose(p);
      head := nil;
    end
  end;
end;

// Procedura usuwa wybrany element
//--------------------------------
procedure slist.remove(e : PslistEl);
var
  p : PslistEl;
begin
  if head = e then pop_front
  else
  begin
    p := head;
    while p^.next <> e do p := p^.next;
    p^.next := e^.next;
    dispose(e);
  end;
end;

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

var
  L : slist;    // obiekt listy jednokierunkowej
  e : PslistEl; // do wskazywania elementów listy
  i : char;

begin
  L.init;  // inicjujemy obiekt

  for i := 'A' to 'G' do L.push_back(i);
  L.printl;

  // Przechodzimy do elementu o wartości D

  e := L.head;

  for i := 'A' to 'C' do e := e^.next;

  // Przed elementem D umieszczamy +

  L.insert_before(e,'+');

  // Za elementem D umieszczamy *

  L.insert_after(e,'*');
  L.printl;

  // Usuwamy element D oraz element pierwszy i ostatni

  L.remove(e);
  L.pop_front;
  L.pop_back;
  L.printl;

  L.destroy;
end.
Code::Blocks
// Obiekt listy jednokierunkowej
// Data: 12.02.2012
// (C)2012 mgr Jerzy Wałaszek
//-------------------------------------------

#include <iostream>

using namespace std;

// Typ elementów listy
//--------------------
struct slistEl
{
  slistEl * next;
  char data;
};

// Definicja typu obiektowego slist
//---------------------------------
class slist
{
  public:
    slistEl * head;

    slist();  // konstruktor
    ~slist(); // destruktor
    unsigned size();
    void printl();
    void push_front(char v);
    void push_back(char v);
    void insert_before(slistEl * e, char v);
    void insert_after(slistEl * e, char v);
    void pop_front();
    void pop_back();
    void remove(slistEl * e);
};

// Konstruktor listy
//------------------
slist::slist()
{
  head = NULL;
}

// Destruktor listy
//-----------------
slist::~slist()
{
  while(head) pop_front();
}

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
unsigned slist::size()
{
  unsigned c = 0;
  slistEl * p = head;
  while(p)
  {
    c++;
    p = p->next;
  }
  return c;
}

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void slist::printl()
{
  unsigned i;
  slistEl * p = head;

  cout << "Number of elements : " << size() << endl;
  for(i = 1; p; p = p->next) cout << "Element #" << i++ << "  data = " << p->data << endl;
  cout << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void slist::push_front(char v)
{
  slistEl * p;

  p = new slistEl;
  p->next = head;
  p->data = v;
  head = p;
}

// Procedura dołączania na koniec listy
//---------------------------------------
void slist::push_back(char v)
{
  slistEl * p, * e;

  e = new slistEl;  // tworzymy nowy element
  e->next = NULL;   // inicjujemy element
  e->data = v;
  p = head;
  if(p)
  {
     while(p->next) p = p->next;
     p->next = e;
  }
  else head = e;
}

// Procedura dołączania przed elementem e
//---------------------------------------
void slist::insert_before(slistEl * e, char v)
{
  slistEl * p = head;

  if(p == e) push_front(v);
  else
  {
    while(p->next != e) p = p->next;
    p->next = new slistEl;
    p->next->next = e;
    p->next->data = v;
  }
}

// Procedura dołączania za elementem e
//------------------------------------
void slist::insert_after(slistEl * e, char v)
{
  slistEl * p = new slistEl;

  p->next = e->next;
  p->data = v;
  e->next = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void slist::pop_front()
{
  slistEl * p = head; // zapamiętujemy początek

  if(p)
  {
    head = p->next;   // nowy początek
    delete p;         // usuń element z pamięci
  }
}

// Procedura usuwa ostatni element
//---------------------------------
void slist::pop_back()
{
  slistEl * p = head; // zapamiętujemy początek

  if(p)
  {
    if(p->next)
    {
      while(p->next->next) p = p->next;
      delete p->next;
      p->next = NULL;
    }
    else
    {
      delete p;
      head = NULL;
    }
  }
}

// Procedura usuwa wybrany element
//--------------------------------
void slist::remove(slistEl * e)
{
  slistEl * p;

  if(head == e) pop_front();
  else
  {
    p = head;
    while(p->next != e) p = p->next;
    p->next = e->next;
    delete e;
  }
}

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

int main()
{
  slist L;     // zawiera adres początku listy
  slistEl * e; // do wskazywania elementów listy
  char i;

  for(i = 'A'; i <= 'G'; i++) L.push_back(i);
  L.printl();

  // Przechodzimy do elementu o wartości D

  e = L.head;

  for(i = 'A'; i <= 'C'; i++) e = e->next;

  // Przed elementem D umieszczamy +

  L.insert_before(e,'+');

  // Za elementem D umieszczamy *

  L.insert_after(e,'*');

  L.printl();

  // Usuwamy element D oraz element pierwszy i ostatni

  L.remove(e);
  L.pop_front();
  L.pop_back();
  L.printl();

  return 0;
}
Free Basic
' Program testowy dla list jednokierunkowych
' Data: 11.02.2012
' (C)2012 mgr Jerzy Wałaszek
'-------------------------------------------

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

' Typ obiektowy slist
'------------------------------
Type slist
  head As slistEl Ptr
  
  Declare Constructor()
  Declare Destructor()
  Declare Sub printl()
  Declare Function size() As UInteger
  Declare Sub push_front(v As String)
  Declare Sub push_back(v As String)
  Declare Sub insert_before(e As slistEl Ptr, v As String)
  Declare Sub insert_after(e As slistEl Ptr, v As String)
  Declare Sub pop_front()
  Declare Sub pop_back()
  Declare Sub remove(e As slistEl Ptr)
End Type

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

Dim L As slist       ' zawiera adres początku listy
Dim e As slistEl Ptr ' do wskazywania elementów listy  
Dim i As Integer


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

L.printl()

' Przechodzimy do elementu o wartości D

e = L.head
For i = 1 To 3
  e = e->next
Next

' Przed elementem D umieszczamy +

L.insert_before(e,"+")

' Za elementem D umieszczamy *

L.insert_after(e,"*")
L.printl()

' Usuwamy element D oraz element pierwszy i ostatni

L.remove(e)
L.pop_front()
L.pop_back()
L.printl()

End

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

' Destruktor listy
'-----------------
Destructor slist()
  While head
    pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub slist.printl()
  
  Dim i As UInteger
  Dim p As slistEl Ptr = head
  
  Print "Number of elements : ";size()
  i = 1
  While p
    Print "Element #";i;"  data = ";p->data
    i += 1
    p = p->next
  Wend
  Print
End Sub

' Funkcja oblicza liczbę elementów listy
'---------------------------------------
Function slist.size() As UInteger

  Dim c As UInteger
  Dim p As slistEl Ptr = head

  c = 0
  While p
    c += 1
    p = p->next
  Wend
  size = c
End Function

' Procedura dołączania na początek listy
'---------------------------------------
Sub slist.push_front(v As String)

  Dim p As slistEl Ptr

  p = new slistEl
  p->next = head
  p->data = v
  head = p
End Sub

' Procedura dołączania na koniec listy
'-------------------------------------
Sub slist.push_back(v As String)

  Dim As slistEl Ptr p,e

  e = New slistEl
  e->next = 0
  e->data = v
  p = head
  If p = 0 Then
    head = e
  Else
    While p->next
      p = p->next
    Wend
    p->next = e
  End If
End Sub

' Procedura dołączania przed elementem e
'---------------------------------------
Sub slist.insert_before(e As slistEl Ptr, v As String)

  Dim p As slistEl Ptr

  p = head
  If p = e Then
    push_front(v)
  Else
    While p->next <> e
      p = p->next
    Wend
    p->next = New slistEl
    p->next->next = e
    p->next->data = v
  End If
End Sub

' Procedura dołączania za elementem e
'------------------------------------
Sub slist.insert_after(e As slistEl Ptr, v As String)

  Dim p As slistEl Ptr

  p = new slistEl
  p->next = e->next
  p->data = v
  e->next = p
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub slist.pop_front()

  Dim p As slistEl Ptr

  p = head      ' zapamiętujemy początek
  If p Then
    head = p->next  ' nowy początek
    Delete p     ' usuń element z pamięci
  End If
End Sub

' Procedura usuwa ostatni element
'--------------------------------
Sub slist.pop_back()

  Dim p As slistEl Ptr

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

' Procedura usuwa wybrany element
'--------------------------------
Sub slist.remove(e As slistEl Ptr)

  Dim p As slistEl Ptr

  If head = e Then
    pop_front()
  Else
    p = head
    While p->next <> e
      p = p->next
    Wend
    p->next = e->next
    Delete e
  End If
End Sub

 



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.