Lekcja 7
listy

Listy jednokierunkowe.

Lista jednokierunkowa to ciąg elementów (obiektów) w którym każdy element zawiera atrybut wartość oraz nast. Atrybut nast wskazuje na kolejny element w liście. Jeśli x wskazuje pewien element listy to jego wartość odczytujemy przez wartość[x], natomiast wartość następnego elementu listy odczytujemy przez wartość[nast[x]]. Jak widać w naszej notacji utożsamiamy zmienną obiektową i wskazanie na zmienną obiektową.

Listę reprezentujemy przez obiekt L, który zawiera atrybuty głowa i ogon wskazujące pierwszy i ostatni element listy.

Przyjmujemy zasadę że ostatni element listy ma wartość nil w atrybucie nast.

Zarówno lista jak i tablica służą do przechowywania elementów ... czym się więc różnią ?
 

tabela	lista
dostęp do elementu przez indeks, np można się łatwo dostać do środkowego elementu tabeli (co jest używane w "wyszukiwaniu binarnym")	dostęp do elementów przez wskazania; mając wsk na pewien element listy, mam bezpośredni dostęp tylko do następnego elementu listy
trudno wstawić nowy element w środek tabeli (trzeba przesuwać wiele elementów)	łatwo wstawić element do listy
tablica zabiera stałą ilość miejsca w pamięci komputera	ilość miejsca w pamięci zależy od liczby elementów listy (to jest bardziej ekonomiczne rozwiązanie)

Przykładowy kod wypisujący elementy listy L:

procedura WypiszElementy(L)
   x <- głowa[L]
   while x<>nil do
      pisz wartość[x]
      x <- nast[x]

.......................................................................................................

Zadanie 110
Zaimplementuj następujące operacje na listach jednokierunkowych:

1. Inicjuj(L)
2. WstawZa(L, x, nowy)
   wstawia element wskazywany przez nowy za elementem wskazywanym przez x
3. WstawPrzed(L, x, nowy)
4. Usun(L, x)
   usuwa z listy element wskazywany przez x
5. WstawOdGłowy(L, nowy)
6. WstawOdOgona(L, nowy)
7. WstawZachowującPorządek(L, nowy)
   zakładamy że wartości elementów listy są posortowane "<="; należy wstawić nowy element w takie miejsce aby lista nadal była posortowana "<="
8. PołączListy(L1, L2)
   dołącza listę L2 na koniec listy L1, przy czym lista L2 staje się listą pustą
9. ScalPosortowaneListy(L1, L2, L3)
   listy L1 i L2 są posortowane; procedura "scala" te listy (używając znanej procedury) i wynik umieszcza w L3; zakładamy że L3 jest początkowo pusta

Założenia dodatkowe i wskazówki: Zakładamy że parametry "listowe" czyli L, L1 itp są przekazywane przez zmienną, tj procedura może modyfikować ich atrybuty. Podczas wykonywania operacji na liście pamiętaj o tym że czasami trzeba modyfikować atrybuty L (np podczas usuwania pierwszego elementu listy).

Listy dwukierunkowe.

W liście dwukierunkowej element x listy ma bezpośredni dostęp do następnego i poprzedniego elementu listy poprzez atrybuty pop i nast ...

Przyjmujemy zasadę że pierwszy element ma nil w atrybucie pop, a ostatni element listy ma nil w atrybucie nast.

Zadanie 111
Zaimplementuj następujące operacje na listach dwukierunkowych:

1. Inicjuj(L)
2. WstawZa(L, x, nowy)
   wstawia element wskazywany przez nowy za elementem wskazywanym przez x
3. WstawPrzed(L, x, nowy)
4. Usun(L, x)
   usuwa z listy element wskazywany przez x

Listy dwukierunkowe z "wartownikiem".

Wygodnie jest programować operacje na listach dwukierunkowych jeśli wprowadzimy tzw wartownika ...

Pierwszy element listy to następnik wartownika; ostatni element listy to poprzednik wartownika; lista pusta składa się tylko z wartownika.

Zadanie 112
Zaimplementuj następujące operacje na listach dwukierunkowych z wartownikiem:

1. Inicjuj(L)
   nowy element tworzymy procedurą x=nowyElementListy()
2. WstawZa(L, x, nowy)
   wstawia element wskazywany przez nowy za elementem wskazywanym przez x
3. WstawPrzed(L, x, nowy)
4. Usun(L, x)
   usuwa z listy element wskazywany przez x