ZSI.Techniki Programowania

Wykład 4
Janusz Jabłonowski

Listy cd.

Lista posortowana

W realizacji list przedstawionej na poprzednim wykładzie nie zakładaliśmy niczego o danych przechowywanych w elementach listy. Często zdarza się tak, że na tych elementach jest określone pewne uporządkowanie: mając dwa elementy możemy powiedzieć, który jest mniejszy (dokładniej: mniejszy bądź równy), np. dla liczb mamy <=. Mając takie uporządkowanie możemy niektóre operacje wykonywać sprawniej. Na przykład szukając elementu na liście na której on nie występował, musieliśmy dotąd przejść ją do końca by się o tym przekonać. Gdybyśmy uporządkowali elementy listy niemalejąco, to po napotkaniu pierwszego elementu większego od szukanego moglibyśmy przerwać poszukiwania. Do implementacji list posortowanych wystarczy nam typ danych z poprzedniego wykładu:

type 
	TLista	=	^TEltListy;
	TEltListy	=	record
				dane:	TypDanych;
				nast:	TLista;
			end;

(Każda lista posortowana jest też listą.) Zobaczmy jak wyglądają operacje na listach posortowanych i porównajmy ich efektywność z operacjami na zwykłych listach. Zwróćmy uwagę na:
-	przerywanie wyszukiwania, gdy już wiadomo, że w liście nie ma szukanej wartości,
-	użycie krótkiego wyliczania wartości logicznych (opcja kompilatora {$B-}).

  programy przykładowe

Lista cykliczna

Używając tego samego typu co powyżej możemy zdefiniować jeszcze jeden rodzaj list: listę cykliczną. W liście cyklicznej ostatni element wskazuje znów na pierwszy. Jeśli będziemy pamiętać wskaźnik nie do pierwszego lecz do ostatniego elementu, to będziemy mieli szybki dostęp zarówno do początku jak i do końca listy.
  programy przykładowe

Lista z opisem

Jeszcze innym sposobem reprezentacji listy jest użycie do jej opisu zamiast jednego wskaźnika rekordu zawierającego bogatsze informacje o liście, np.:
-	wskaźnik na jej początek,
-	wskaźnik na jej koniec,
-	liczbę elementów listy (jej długość).

  programy przykładowe

Lista dwukierunkowa

Ostatnim wreszcie przykładem listy z tego wykładu jest lista dwukierunkowa. Jest potrzebna w sytuacjach, gdy potrzebujemy przesuwać się po liście także do tyłu. Poza tym mając listę dwukierunkową nie musimy w algorytmie usuwania pamiętać wskaźnika do poprzedniego elementu (bo jest zapamiętany w samym elemencie).

  programy przykładowe

Ułatwianie sobie życia z listami

Strażniki i atrapy

Ponieważ wstawianie/usuwanie pierwszego/ostatniego elementu listy zwykle różni się od tej samej operacji na środkowych elementach listy, można ułatwić sobie życie wstawiając do listy dodatkowy/dodatkowe sztuczne elementy na początku i końcu listy, zwane odpowiednio atrapą i strażnikiem.

Funkcja Twórz

Do każdego typu wskaźnikowego warto zdefiniować funkcję tworzącą pojedyncze elementy odpowiadającego mu typu bazowego. Taka funkcja jako parametry dostaje wartości wszystkich pól tworzonych zmiennych dynamicznych, a jako wynik daje wskaźnik do nowoutworzonej zmiennej dynamicznej. Zalety takiego podejścia to:
-	większa czytelność programów,
-	mniejsza możliwość popełnienia błędu.

Np. dla typu Tlista, zdefiniowalibyśmy następującą funkcję Twórz:

function Twórz(dane: TypDanych, nast: Tlista): Tlista;
var pom: Tlista;
begin
	new(pom);
	pom^.dane := dane;
	pom^.nast := nast;
	Twórz := pom;
end; {Twórz}

Mając taką funkcję można dużo prościej zapisać np. wstawianie na początek listy prostej:

procedure WstawNaPocz(var l: TLista; dane: TypDanych);
begin
	l := Twórz(dane, l);
end; {WstawNaPocz}

Równie łatwo można stworzyć przykładową, kilkuelementową listę:

	l := Twórz(1, Twórz(2, Twórz(3, Twórz(4, nil))));

Dużo informacji o listach można znaleźć w skrypcie (dostępnym w naszej bibliotece) "Pracownia Programowania I" pod redakcją M. Cichego i S. Szpakowicza (rozdział 7).