Lista jednokierunkowa

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

 

Przykład

while p <> nil do
begin
  …
  p := p^.next;
end;

Zadanie 1

program slist_test1;

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

  slistElrecord
    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.

 

Author: ZSE

Admnistrator serwisu. Nauczyciel przedmiotów informatycznych

Share This Post On

Submit a Comment

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *