ZSI.Techniki Programowania

Wykład 3
Janusz Jabłonowski


Wykorzystanie zmiennych dynamicznych - listy

"	Zaletą dynamicznych struktur danych jest ich elastyczność, potrafią zmieniać swój rozmiar w czasie działania programu.
"	Najpopularniejszą dynamiczną strukturą danych jest lista, czyli ciąg elementów, z których każdy (oprócz ostatniego) ma określony następny element. Mając dostęp do pierwszego elementu możemy dostać się do każdego elementu listy.
"	Listy można implementować na wiele sposobów, oto niektóre z nich:
-	tablica par: wartość elementu listy i indeks następnego elementu (tu z góry nakładamy ograniczenie na rozmiar listy),
-	rekord o dwu polach: wartość elementu listy i wskaźnik do następnego elementu,

Listy - implementacja wskaźnikowa
"	Deklaracja typu listowego:

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

"	Deklaracja zmiennych typu listowego:

var
	lista:	Tlista;
	
Uwaga: powyższa deklaracja nie tworzy żadnej listy, na razie mamy tylko niezainicjalizowany wskaźnik.

"	Przekazywanie list jako parametrów procedur/funkcji:

procedure RobiCośZListą(l: Tlista);
procedure RobiCośZListą(var l: Tlista);

Pierwszej postaci używamy wtedy, gdy nie chcemy modyfikować wskaźnika do pierwszego elementu listy (choć być może zupełnie zmienimy wszystkie pozostałe a ponadto zmienimy dane zapisane w pierwszym elemencie listy), drugiej wtedy gdy w wyniku działania procedury może się zmienić wskaźnik do pierwszego elementu listy.

"	Teraz pokażemy implementację następujących operacji na listach:
 	wstaw na początek listy,
 	wczytaj listę od użytkownika (odwracając kolejność elementów),
 	przejdź całą listę (modyfikacje: policz długość listy, wypisz listę),
 	skasuj całą listę,
 	wstaw na koniec listy (to można lepiej zrobić)
 	wczytaj listę od użytkownika (zachowując kolejność elementów),
 	usuń pierwszy element listy,
 	znajdź pierwszy element na liście o podanej wartości,
 	usuń wszystkie elementy o zadanej wartości.

  programy przykładowe