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. Górna część tabelek określa typy dla list jednokierunkowych. Dolna część to deklaracje dla list dwukierunkowych.

Pascal

type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    Data: typ_danych;
  end;

type
  PDLel = ^DLel;
  DLel =  record
    next  : PDLel;
    prev  : PDLel;
    Data: typ_danych;
  end;

  DLvar = record
    head  : PDLel;
    tail  : PDLel;
    count : cardinal;
  end;

C++

struct SLel
{
  SLel * next;
  typ_danych data;
};

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

struct DLvar
{
  DLel * head, * tail;
  unsigned count;
};

Basic

Type SLel
  next As SLel Ptr
  data As typ_danych
End Type

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

Type DLvar
  head As DLel Ptr
  tail As DLel Ptr
  count As UInteger
End Type

SLel	:	typ elementu listy jednokierunkowej
DLel	:	typ elementu listy dwukierunkowej
DLvar	:	typ zmiennej obsługującej listę dwukierunkową, która 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

…
var head : PSLel;
…

…
var L : DLvar;
…

C++

…
SLel * head;
…

…
DLvar L;
…

Basic

…
Dim head As SLel Ptr
…

…
Dim L As DLvar
…

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

…
head := NIL;
…

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

C++

…
head = NULL;
…

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

Basic

…
head = 0
…

Sub l_init(ByRef L As DLvar)
  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.

W języku Python efektywne listy tworzymy za pomocą klas. Wbudowany typ list ([ ]) w rzeczywistości jest dynamiczną tablicą wskaźników zawierających adresy obszarów pamięci przechowujących właściwe dane. Prawdziwe listy tworzymy następująco (klasy elementów list oraz klasy list)

Python (dodatek)

# dla listy jednokierunkowej

# klasa elementu listy
class SLel:


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


# klasa listy
class SLvar:


    def __init__(self):
        self.head = None

# dla listy dwukierunkowej

# klasa elementu listy
class DLel:


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


# klasa listy
class DLvar:


    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

Gdy zostały zdefiniowane klasy, możemy je wykorzystać, do utworzenia list oraz ich elementów:

Python (dodatek)

# Lista jednokierunkowa-inicjalizacja
# Data: 30.04.2024
# (C)2024 mgr Jerzy Wałaszek
#--------------------------------------


# klasa elementu listy
class SLel:


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


# klasa listy
class SLvar:


    def __init__(self):
        self.head = None


# tworzymy zmienną listy jednokierunkowej
a = SLvar()

# wyświetlamy zawartość zmiennej listy
print("head =", a.head)
print()

# tworzymy element listy jednokierunkowej
x = SLel("ABC")

# wyświetlamy zawartość elementu
print("next =", x.next)
print("data =", x.data)

Wynik:

head = None

next = None
data = ABC

Python (dodatek)

# Lista dwukierunkowa-inicjalizacja
# Data: 30.04.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------------


# klasa elementu listy
class DLel:


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


# klasa listy dwukierunkowej
class DLvar:


    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0


# tworzymy zmienną listy dwukierunkowej
a = DLvar()

# wyświetlamy zawartość zmiennej listy
print("head  =", a.head)
print("tail  =", a.tail)
print("count =", a.count)
print()

# tworzymy element listy dwukierunkowej
x = DLel(3.1415)

# wyświetlamy zawartość elementu
print("next =", x.next)
print("prev =", x.prev)
print("data =", x.data)

Wynik:

head  = None
tail  = None
count = 0

next = None
prev = None
data = 3.1415

Klasa automatycznie inicjuje listę jako pustą (niezawierającą żadnego elementu), a element listy jako niepowiązany z innymi elementami listy. Więcej o obsłudze list znajdziesz w kolejnych rozdziałach.

Funkcja wewnętrzna __init__( ) jest konstruktorem i zostaje wywołana przy tworzeniu zmiennej klasy. Zmienną klasy tworzymy poprzez przypisanie:

zmienna = klasa(parametry)

Parametry są przekazywane do konstruktora klasy, gdzie służą do inicjalizacji atrybutów zmiennej.

do podrozdziału do 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