Algorytmy i Struktury Danych - Reprezentacja list w pamięci komputera

Tworząc zmienną typu lista, tworzymy w niej trzy pola: head, tail oraz count (obowiązkowe jest pole head, pozostałe usprawniają obsługę list, ale nie są konieczne – dla list jednokierunkowych specjalnie pominęliśmy tail oraz count ).

Zdefiniujmy podstawowe typy danych:

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

type
  PdlistEl = ^dlistEl;
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    data  : typ_danych;
  end;

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

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

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

Type dlistEl
  next As dlistEl Ptr
  prev As dlistEl Ptr
  data As typ_danych
End Type

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

Górna część tablicy określa typy dla list jednokierunkowych. Dolna część to deklaracje dla list dwukierunkowych.

slistEl	–	element listy jednokierunkowej
dlistEl	–	element listy dwukierunkowej
dlistVar	–	zmienna obsługująca listę dwukierunkową, jest strukturą o trzech polach: head – wskazuje pierwszy element listy tail – wskazuje ostatni element listy count – zawiera liczbę elementów przechowywanych na liście

Dla list jednokierunkowych nie ma potrzeby tworzenia osobnego typu dla zmiennej obsługującej listę – zmienna ta będzie przechowywać tylko adres pierwszego elementu listy. Zmienną obsługującą listę tworzymy następująco (u góry dla list jednokierunkowych z uproszczoną obsługą, u dołu dla list dwukierunkowych z pełną obsługą ):

Pascal	C++	Basic
... var head : PslistEl; ...	... slistEl * head; ...	... Dim head As slistEl Ptr ...
... var L : dlistVar; ...	... dlistVar L; ...	... Dim L As dlistVar ...

Po deklaracji zmiennej należy ją bezwzględnie zainicjować. W tym celu do wszystkich pól wpisujemy zera. Dla listy dwukierunkowej możemy stworzyć prostą procedurę inicjalizacji:

Pascal

C++

Basic

...
head := NIL;
...

...
head = NULL;
...

...
head = 0
...

procedure l_init ( var L : dlistVar );
begin
  L.head  := NIL;
  L.tail  := NIL;
  L.count := 0;  
end;

void l_init ( dlistVar & L )
{
  L.head = L.tail = NULL;
  L.count = 0;
}

Sub l_init ( ByRef L As dlistVar )
  L.head  = 0
  L.tail  = 0
  L.count = 0
End Sub

Otrzymujemy w ten sposób pustą listę (ang. empty list ), czyli listę, która nie zawiera żadnego elementu. Tak zainicjowana zmienna L jest gotowa do dalszego użycia w programach.

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.

Reprezentacja list w pamięci komputera

Struktura listy