Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Reprezentacja list w pamięci komputera

SPIS TREŚCI

Struktura listy

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
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    data  : typ_danych;
  end;
type
  PdlistEl = ^dlistEl;
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    data  : typ_danych;
  end;

  dlistVar = record
    head  : PdlistEl;
    tail  : PdlistEl;
    count : cardinal;
  end;
C++
struct slistEl
{
  slistEl * next;
  typ_danych data;
};
struct dlistEl
{
  dlistEl * next, * prev;
  typ_danych data;
};

struct dlistVar
{
  dlistEl * head, * tail;
  unsigned count;
};
Basic
Type slistEl
  next As slistEl Ptr
  data As typ_danych
End Type
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
slistEl  :  typ elementu listy jednokierunkowej
dlistEl  :  typ elementu listy dwukierunkowej
dlistVar  :  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 : PslistEl;
…
…
var L : dlistVar;
…
C++
…
slistEl * head;
…
…
dlistVar L;
…
Basic
…
Dim head As slistEl Ptr
…
…
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
…
head := NIL;
…
procedure l_init(var L : dlistVar);
begin
  L.head  := NIL;
  L.tail  := NIL;
  L.count := 0; 
end;
C++
…
head = NULL;
…
void l_init(dlistVar & L)
{
  L.head = L.tail = NULL;
  L.count = 0;
}
Basic
…
head = 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.

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 slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy
class slistVar:
    def __init__(self):
        self.head = None
# dla listy dwukierunkowej

# klasa elementu listy
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy
class dlistVar:
    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 slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy
class slistVar:
    def __init__(self):
        self.head = None

# tworzymy zmienną listy jednokierunkowej

a = slistVar()

# wyświetlamy zawartość zmiennej listy

print("head =",a.head)
print()

# tworzymy element listy jednokierunkowej

x = slistEl("ABC")

# wyświetlamy zawartość elementu

print("next =",x.next)
print("data =",x.data)

# usuwanie

del a,x
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 dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
class dlistVar:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0
        
# tworzymy zmienną listy dwukierunkowej

a = dlistVar()

# wyświetlamy zawartość zmiennej listy

print("head  =",a.head)
print("tail  =",a.tail)
print("count =",a.count)
print()

# tworzymy element listy dwukierunkowej

x = dlistEl(3.1415)

# wyświetlamy zawartość elementu

print("next =",x.next)
print("prev =",x.prev)
print("data =",x.data)

# usuwanie

del a,x
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.


Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

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.