Algorytmy - część trzecia kursu

Struktury danych

Nadszedł czas, abyśmy zapoznali się z trzema najprostszymi strukturami danych.

I. Czym są struktury danych?

Struktury danych są obiektami, które nie tylko przechowują informacje, ale pozwalają również wygodnie nimi manipulować. Do tej pory w zupełności wystarczały nam zmienne i tablice, jednak w miarę wgryzania się w algorytmikę szybko okaże się, że są one dalece niewystarczające nawet do dość prostych problemów.

II. Rozszerzenia pseudojęzyka

Najpierw jednak wprowadzimy do naszego pseudojęzyka nowe konstrukcje:

1. Struktury i obiekty

   Pojedyncze zmienne i tablice nie zawsze są wygodnym sposobem reprezentacji danych. Bardzo często opisujemy przedmioty, określając ich cechy, a korzystanie z wielkiego zbioru zmiennych znacznie utrudnia analizę problemów. Przykładowo możemy chcieć stworzyć program obsługujący wypożyczalnię samochodów. Oczywiście moglibyśmy stworzyć kilka tablic:

   model[1..n] rok_produkcji[1..n] przebieg[1..n] cena[1..n] 

   Każda tablica przechowuje informacje na temat jednej, wybranej cechy i-tego samochodu. Nie jest to jednak „naturalny” sposób przechowywania danych, gdyż w ten sposób sztucznie rozdzielamy cechy pojazdu, całkowicie tracąc koncepcję obiektu, jakim jest opisywany samochód. Wygodniej byłoby stworzyć nowy rodzaj struktury, w której zbierzemy wszystkie potrzebne informacje. Strukturę tą nazwiemy w naszym przykładzie: „Samochod” i opiszemy następująco:

   Samochod: 	model 	rok_produkcji 	przebieg 	cena 

   Stworzyliśmy nowy typ danych i możemy teraz swobodnie powoływać do życia konkretne obiekty pisząc:

   opel_astra - obiekt typu Samochod 

   Do elementów danej struktury odwołujemy się za pomocą operatora kropki, np.:

   opel_astra - obiekt typu Samochod  opel_astra.model = astra 		// Ustawiamy odpowiednie cechy opel_astra.rok_produkcji = 2000 WYPISZ(opel_astra.cena) 

   W rzeczywistych językach programowania struktury takie nazywane są np. rekordami (Pascal) lub klasami(C++,Java).

   W Pascalu:  type Samochod = record 	model : string; 	rok_produkcji : integer; 	przebieg : integer; 	cena : integer; end;  W C/C++:  class Samochod  { 	public: 		char* model; 		int rok_produkcji; 		int przebieg; 		int cena; }; 

   Choć w przykładzie w C/C++ posłużyliśmy się słowem kluczowym „class”, to w naszym pseudojęzyku wszystkie metody umieścimy poza strukturą jako funkcje.

2. Wskaźniki

   Wskaźniki są konstrukcjami znanymi chyba każdemu programiście. Pominiemy jednak szczegóły ich stosowania i postaramy się wprowadzić je w sposób dość „intuicyjny”.

   Ogólnie: wskaźnikami nazywamy zmienne, które nie przechowują żadnej wartości, a jedynie adres w pamięci obiektu, na który „wskazują” (mogą to być też inne wskaźniki).

   Oczywiście, tak jak w każdym języku programowania, musimy odróżnić dostęp do obiektu, na który wskazuje wskaźnik, od dostępu do samego wskaźnika (dokładniej: przechowywanego w nim adresu).

   q - wskaźnik u - dowolna zmienna  q := u 

   Powyższy zapis jest niejednoznaczny. Nie można odróżnić, czy chcemy ustawić wskaźnik „q” na zmienną „u”, czy też chcemy zmienić wartość zmiennej, na którą wskazuje „q”. Dlatego też, dostęp do obiektu, na który wskazuje dany wskaźnik, będziemy oznaczać gwiazdką umieszczoną przed nazwą wskaźnika. W ten sposób:

   Założenia: w - wskaźnik s - zmienna  w := s  // Teraz wskaźnik w wskazuje na obiekt s *w := 4 // Zmieniamy wartość obiektu wskazywanego przez w 	// (w tym przypadku zmiennej s) na 4 

   W prawdziwych językach programowania:

   W Pascalu:  w := @s; w^ := 4;  W C/C++:  w = &s; *s = 4; 

   Przyjmujemy również, że przypisanie:

   w,s - wskaźniki  w := s  

   oznacza: „Ustaw wskaźnik ›w‹ na ten sam obiekt, na który wskazuje wskaźnik ›s‹”. Jest do dość intuicyjne, jeśli będziemy pamiętać, że wskaźniki przechowują adres w pamięci zmiennej, na którą wskazują. Zatem w powyższym fragmencie kodu przepisujemy adres ze zmiennej „s” do zmiennej „w”.

   Często będziemy chcieli, aby wskaźnik nie wskazywał na żaden konkretny obiekt. Będziemy go wtedy ustawiać na specjalny obiekt NULL (tak jak w C/C++, albo na NIL w Pascalu), np.:

   w := NULL 

   Ciekawostka: W rzeczywistych językach kompilowanych do kodu maszynowego taki wskaźnik zostaje ustawiony na adres 0.

   Trzecią istotną cechą wskaźników jest możliwość powoływania do życia nowych obiektów już w trakcie działania programu. Służy do tego specjalna funkcja new, której parametrem jest nazwa typu obiektu, który chcemy utworzyć. Jeśli go nie podamy, to dostaniemy nową zmienną typu podstawowego:

   w - wskaźnik na dowolną zmienną s - wskaźnik do obiektu typu Samochod  w := new()  s := new(Samochod)  Odpowiedniki w językach programowania, np.:  Pascal:  new(w);  C/C++  w = new int; 

   Do usuwania nieużywanych obiektów z pamięci służy pseudofunkcja delete([nazwa zmiennej]).

   Ciekawostka: Języki takie jak Java i C# używają techniki o nazwie Garbage Collecting do samodzielnego odnajdowania i usuwania z pamięci nieużywanych obiektów. W chwili gdy program traci dostęp do danego obiektu (np. poprzez przestawienie wskaźnika, który na niego wskazywał) jest on oznaczany jako „do usunięcia”. Programista nie musi martwić się o zwalnianie pamięci, jednak ceną, jaką za to płaci, jest okresowe automatyczne „sprzątanie” sterty (np. w starszych implementacjach Javy dało się zauważyć w takim momencie wyraźne zwolnienie działania programu).