Reprezentacja list w pamięci komputera


Tematy pokrewne
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

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:

 

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
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ą):

 

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

 

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

 



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.