Algorytmy i struktury danych - 04. Listy.pdf - Grafika komputerowa - pmtg

Algorytmy i Struktury danych, wer. C/C++, Lekcja 4: Listy

Strona 1

Lekcja 4: Listy

Wst ħ p

Ta lekcja zaczyna si ħ powtórk Ģ rozdziału o wska Ņ nikach - tego z podr ħ cznika Programowania. Tam pełnił on rol ħ ostatniego rozdziału

ko ı cz Ģ cego wiedz ħ o j ħ zyku. Tutaj został rozszerzony o tablice dynamiczne i jest wst ħ pem do zrozumienia nowej struktury danych -

listy dynamicznej, czyli takiej, która tworzy si ħ i znika w trakcie działania programu. I zarazem dopasowuje si ħ długo Ļ ci Ģ do potrzeb

u Ň ytkownika.

To jedna z najwa Ň niejszych lekcji w tym podr ħ czniku. By ę mo Ň e nie zrozumiecie jej od razu. Nie przejmujcie si ħ . To normalne. Trzeba

czasem par ħ razy powróci ę do pocz Ģ tku, by "zaskoczy ę " i zrozumie ę , jak porusza ę po listach. Trzeba wykona ę testy ko ı cowe i

rozwi Ģ za ę sporo zada ı . I wtedy powiecie - przecie Ň to takie proste... I wtedy dopiero b ħ dziecie mogli zacz Ģę chodzi ę po drzewach :) -

ju Ň zaraz, w nast ħ pnej lekcji.

Wska Ņ niki i zmienne dynamiczne

Wiecie ju Ň , jak definiowa ę zmienne ró Ň nych typów, wiecie jak s Ģ przechowywane w pami ħ ci komputera, czyli macie pełne podstawy

ku temu, aby troch ħ bli Ň ej pozna ę bardziej zaawansowane mechanizmy pozwalaj Ģ ce na Ļ wiadome zarz Ģ dzanie zawarto Ļ ci Ģ pami ħ ci

komputera przez programist ħ .

Lecz najpierw kilka słów wyja Ļ nienia, po co jest to Wam potrzebne. Dost ħ pem programów do pami ħ ci steruje system operacyjny. Tutaj

zastosujemy pewne uproszczenie: w momencie uruchomienia programu system operacyjny przydziela pami ħę (proces przydzielania

pami ħ ci nazywa ę b ħ dziemy alokacj Ģ ) :

na kod programu (czyli list ħ rozkazów dla procesora)

na zmienne statyczne, czyli te definiowane w sposób ju Ň Wam znany:

int i; // potrzebne 4 bajty - tyle zajmuje liczba całkowita

char zn; // potrzebny 1 bajt - znak jest dla komputera liczb Ģ przypisan Ģ mu w kodzie ASCII

int t[10][10]; //potrzebne 10x10x4 = 400 bajtów, itd

Je Ň eli pami ħ ci na te zmienne nam zabraknie - program po prostu si ħ nie uruchomi. Pami ħę przydzielona na zmienne statyczne na

pocz Ģ tku działania programu pozostaje przez nie zaj ħ ta a Ň do ko ı ca jego pracy - i nic nie mo Ň emy z tym zrobi ę . Nakłada to na

programist ħ powa Ň ne ograniczenia - ju Ň w momencie pisania programu musimy przewidzie ę maksymalne zapotrzebowanie na pami ħę .

Załó Ň my wi ħ c na przykład, Ň e w tablicy umieszczamy rekordy zawieraj Ģ ce dane osobowe naszych znajomych. Poniewa Ň nie mamy

Ň adnej mo Ň liwo Ļ ci zmiany rozmiaru tablicy statycznej podczas pracy programu, ju Ň w trakcie jego tworzenia musimy wiedzie ę , ilu

maksymalnie znajomych mie ę mo Ň emy. Oczywicie to ograniczenie mo Ň na obej Ļę , podaj Ģ c za ka Ň dym razem absurdalnie wysokie

warto Ļ ci, tak aby na przykład tablica zawierała milion elementów. System operacyjny musi nam wtedy przydzieli ę pami ħę na milion

rekordów, co przy zało Ň eniu, Ň e jeden z nich zajmuje (jak chcieliby Ļ my pami ħ ta ę zdj ħ cie - cho ę by małe) 10 kB, daje nam 10 000 000

kB, czyli prawie 10 GB. Je Ļ li macie komputer o takiej pami ħ ci, to mo Ň ecie próbowa ę :-).

To mo Ň e nie był najm Ģ drzejszy przykład, ale pami ħ tajmy, Ň e nie tylko nasz program pracuje na komputerze. Tworzenie zmiennych

statycznych o maksymalnym mo Ň liwym rozmiarze nie jest wi ħ c Ň adnym rozwi Ģ zaniem - jest nieeleganckie, nieefektywne i samolubne -

odbieramy w ten sposób "przestrze ı Ň yciow Ģ " dla innych, równolegle pracuj Ģ cych programów.

Warto Ļę zmiennej i wska Ņ nik do niej

Aby unikn Ģę wszelkich ogranicze ı wymienionych powy Ň ej, wymy Ļ lono zmienne dynamiczne . Zamiast na pocz Ģ tku, podczas

uruchamiania programu, alokowa ę pami ħę "z zapasem", mo Ň na poprosi ę system o przydzielenie nam pami ħ ci na tak Ģ zmienn Ģ

dokładnie w tym momencie, w którym nam to b ħ dzie potrzebne. Kiedy sko ı czymy z niej korzysta ę , zawiadomimy o tym system i

pami ħę do tej pory przez nas zaj ħ ta zostanie mu zwrócona do ponownego wykorzystania, b Ģ d Ņ to przez nas, b Ģ d Ņ przez inny program.

Je Ň eli za ŇĢ damy dost ħ pu do wi ħ kszej ilo Ļ ci pami ħ ci, ni Ň jest w dyspozycji systemu - zawiadomi on nas o tym i pami ħ ci nie przydzieli.

Programista musi wi ħ c po ka Ň dym ŇĢ daniu alokacji sprawdzi ę , czy dostał to, co chciał - i zareagowa ę odpowiednio w przypadku

niepowodzenia.

Zmienne dynamiczne s Ģ to zmienne tworzone odpowiednim poleceniem podczas wykonywania programu i istniej Ģ ce a Ň do ich

jawnego skasowania.

http://iair.mchtr.pw.edu.pl/~bputz/aisd_cpp/druk.php?id=27

2008-03-21 00:08:48

Algorytmy i Struktury danych, wer. C/C++, Lekcja 4: Listy

Strona 2

To jawne kasowanie zmiennych dynamicznych jest bardzo istotne - je Ļ li tego nie zrobimy, pami ħę na te zmienne pozostanie

zarezerwowana nawet po zamkni ħ ciu programu. W ten sposób b ħ dzie nast ħ pował tzw. wyciek pami ħ ci ; przy ka Ň dym kolejnym

uruchomieniu programu b ħ d Ģ zajmowane nast ħ pne obszary pami ħ ci i w ko ı cu szybko mo Ň e jej zabrakn Ģę . Nie zapominajcie wi ħ c o

usuwaniu zmiennych dynamicznych w programie, jak tylko przestan Ģ byc potrzebne, i nie liczcie na to, Ň e kompilator za Was to zrobi

(cho ę bywaj Ģ takie j ħ zyki i sytuacje, Ň e to robi).

Do zmiennych dynamicznych najcz ħĻ ciej mamy dost ħ p poprzez ich adres, nazywany powszechnie wska Ņ nikiem . Wska Ņ nik jest

specjalnym

typem

zmiennej, w

której przechowywany jest

...

adres

innej

zmiennej, czyli

adres

pocz Ģ tku

obszaru

pami ħ ci

przydzielonego na zapami ħ tanie naszych danych.

Odnosz Ģ c to do przykładu z lekcji 0: odpowiednikiem wska Ņ nika b ħ dzie szufladka, do której mo Ň ecie wło Ň y ę numer innej

szufladki. Czyli niezbyt rozgarni ħ ty człowieczek mo Ň e poprosi ę swojego nadzorc ħ (system operacyjny), aby przydzielił mu

dodatkowe szufladki, a numer pierwszej z nich umie Ļ cił w wyznaczonej szufladce - wska Ņ niku.

A wi ħ c do danych w pami ħ ci mo Ň emy odwoływa ę si ħ nie tylko przez zwykłe nazwy (wtedy s Ģ to zmienne statyczne, powoływane w

programie lub podprogramie w momencie ich deklaracji), ale równie Ň przez adresy (wska Ņ niki) do nich. Odnosi si ħ to w równym

stopniu do zmiennych dynamicznych jak i statycznych. My w tym podr ħ czniku b ħ dziemy wykorzystywali wska Ņ niki głównie w celu

pracy ze zmiennymi dynamicznymi, lecz pami ħ tajcie - sposób odwoływania si ħ do zmiennej nie jest równowa Ň ny sposobowi tworzenia

zmiennej.

Wska Ņ nik wskazuj Ģ cy jak ĢĻ dan Ģ w pami ħ ci ilustruje si ħ zwykle nast ħ puj Ģ co:

Zmienna wsk_i jest w tym przykładzie wska Ņ nikiem - wskazuje na jak ĢĻ dan Ģ w pami ħ ci.

Nazwy wska Ņ ników mog Ģ by ę zupełnie dowolne, tak jak dowolne mog Ģ by ę nazwy wszystkich innych zmiennych. Załó Ň my wi ħ c, Ň e

wsk_i jest wska Ņ nikiem do danych całkowitych (wskazuje na adres przechowuj Ģ cy zmienn Ģ typu int). Je Ļ li chcemy wpisa ę liczb ħ 20

pod zmienn Ģ wskazywan Ģ przez wsk_i, zapisujemy to z u Ň yciem gwiazdki * stoj Ģ cego po lewej stronie wska Ņ nika ( operator

wyłuskania ).

*wsk_i = 20;

i czytamy tak: pod zmienn Ģ wskazywan Ģ przez wsk_i podstaw liczb ħ 20.

Analogicznie zapisujemy i czytamy:

*adres = 3.8; //pod zmienn Ģ wskazywan Ģ przez adres podstaw warto ę 3.8

cout << *adres; //wydrukuj zmienn Ģ wskazywan Ģ przez adres

W taki wła Ļ nie sposób musicie czyta ę wszystkie nazwy, które po lewej stronie maj Ģ symbol * .

Na zmiennych dynamicznych mo Ň na wykonywa ę te same operacje, co na zmiennych statycznych - tylko trzeba si ħ do nich inaczej

odwoływa ę . Porównajcie podstawienie pod zwykł Ģ zmienn Ģ statyczn Ģ i ( pod

zmienn Ģ i podstaw

liczb ħ 12 ) i pod

zmienn Ģ

dynamiczn Ģ wsk_i ( pod zmienn Ģ wskazywan Ģ przez wsk_i podstaw liczb ħ 20 ):

Powtórzmy raz jeszcze:

http://iair.mchtr.pw.edu.pl/~bputz/aisd_cpp/druk.php?id=27

2008-03-21 00:08:48

Algorytmy i Struktury danych, wer. C/C++, Lekcja 4: Listy

Strona 3

Zmienne statyczne s Ģ tworzone w momencie uruchamiania programu i istniej Ģ do ko ı ca jego pracy. Zmienne dynamiczne

tworzone i usuwane s Ģ w trakcie pracy programu poprzez wywoływanie odpowiednich polece ı . Do zmiennych statycznych

zwykle odwołujemy si ħ przez ich nazw ħ , do zmiennych dynamicznych zwykle odwołujemy si ħ przez wska Ņ nik.

Podkre Ļ lamy słowo zwykle - poniewa Ň w C++ mo Ň na si ħ odwoływa ę do dowolnego typu zmiennych w dowolny sposób. Poniewa Ň

C++ wywodzi si ħ z j ħ zyka C, który przewidziany był tak Ň e do programowania sprz ħ tu (a wi ħ c na stosunkowo niskim poziomie), cały

mechanizm wska Ņ ników i operacji bezpo Ļ rednio na pami ħ ci jest w C++ silnie rozwini ħ ty. My jednak na ogół ograniczymy si ħ do

zastosowa ı podstawowych - mo Ň liwych do wykonania tak Ň e w innych j ħ zykach programowania.

Zmienne dynamiczne mog Ģ by ę ró Ň nych typów, tak jak wszystkie inne zmienne. Na rysunku poni Ň szym mo Ň ecie zobaczy ę du Ň o

ró Ň nych zmiennych dynamicznych, najrozmaitszych typów, wraz z ich wska Ņ nikami. Zmienne dynamiczne mog Ģ by ę dowolnie

rozrzucone w pami ħ ci komputera.

Powinni Ļ cie w tym miejscu od razu zapyta ę : a sk Ģ d b ħ dzie wiadomo, co wskazuj Ģ te ró Ň ne wska Ņ niki? . Rzeczywi Ļ cie - je Ļ li u Ň ywamy

zmiennej i , najpierw j Ģ deklarujemy. Wi ħ c Ň eby skorzysta ę ze zmiennej dynamicznej, musimy najpierw zadeklarowa ę wska Ņ nik do tej

zmiennej (zauwa Ň cie, Ň e wska Ņ nik tak naprawd ħ te Ň jest zmienn Ģ , i to do tego statyczn Ģ - w niej zapami ħ tany jest adres zmiennej

dynamicznej). Deklaracje wska Ņ ników równie Ň oznacza si ħ poprzez gwiazdk ħ - równie Ň po lewej stronie nazwy zmiennej. Piszemy

wi ħ c tak:

int *wsk_i;

i czytamy: zmienna wsk_i jest wska Ņ nikiem do zmiennej typu int. Je Ļ li jednak wska Ņ nik wskazuje struktur ħ , to wcze Ļ niej trzeba j Ģ

zdefiniowa ę . Ogólnie deklaracja wska Ņ nika ma posta ę :

typ_zmiennej_wskazywanej * nazwa_wska Ņ nika ;

W przypadku j ħ zyka C++, jak zd ĢŇ yli Ļ cie ju Ň zauwa Ň y ę - tablice traktowane s Ģ w inny sposób ni Ň pozostałe typy zmiennych. Zazwyczaj

(w wi ħ kszo Ļ ci przypadków) zmienna typu tablicowego jest równowa Ň na zmiennej zawieraj Ģ cej wska Ņ nik do pierwszego elementu.

int A[10];

to A mo Ň e by ę traktowane jako wska Ņ nik do zmiennej typu int . Mo Ň e by ę traktowane - co oznacza, Ň e mo Ň e by ę u Ň ywane zamiennie z

wska Ņ nikiem. To dlatego w niektórych przykładach przedstawionych we

wcze Ļ niejszych lekcjach przekazywali Ļ my tablic ħ do

podprogramu jako wska Ņ nik.

Teraz ju Ň powinnicie umie ę zadeklarowa ę ró Ň ne wska Ņ niki z naszego obrazka:

struct auta

{

string marka;

int rocznik;

double cena;

};

int *wsk_i;

http://iair.mchtr.pw.edu.pl/~bputz/aisd_cpp/druk.php?id=27

2008-03-21 00:08:48

Algorytmy i Struktury danych, wer. C/C++, Lekcja 4: Listy

Strona 4

double *adres, *wsk_re;

string *a;

char *ad_zn;

int *wsk_tab;

auta *ad_auta;

Wska Ņ nik do zmiennej jest adresem pierwszego z bajtów, w których jest ta zmienna przechowywana. A wi ħ c wska Ņ nik na

zmienn Ģ typu int to adres pierwszego z 4 bajtów, gdzie ta zmienna jest pami ħ tana; wska Ņ nik na ła ı cuch o 50 znakach to znowu

adres pierwszego z nich, itd.

Tworzenie i usuwanie zmiennych dynamicznych

Mogliby Ļ cie w tym miejscu uzna ę , Ň e skoro umiecie wska Ņ nik zadeklarowa ę i odwoła ę si ħ do zmiennej przez niego wskazywanej, to

mo Ň ecie ju Ň działa ę na zmiennych dynamicznych, czyli na przykład:

...

struct auta

{

string marka;

int rocznik;

double cena;

};

...

int main( int argc, char *argv[])

{

...

int *wsk_i;

char *ad_zn;

auta *ad_auta;

...

*wsk_i = 20;

*ad_zn = 'A' ;

(*ad_auta).cena = 35000;

...

return 0;

}

Niestety to jeszcze nie koniec. Wiecie ju Ň przecie Ň , Ň e zmienne dynamiczne to takie zmienne, które mog Ģ w trakcie pracy programu

pojawia ę si ħ i znika ę . Musimy wi ħ c im to pojawianie si ħ i znikanie umo Ň liwi ę . Zatem potrzebne b ħ d Ģ dwie instrukcje:

instrukcja, która powołuje do Ň ycia zmienn Ģ dynamiczn Ģ - przydziela jej pami ħę i zapami ħ tuje jej adres;

instrukcja, która odbiera pami ħę zarezerwowan Ģ na zmienn Ģ dynamiczn Ģ i kasuje jej adres.

Takie dwie instrukcje dost ħ pne s Ģ w ka Ň dym zaawansowanym j ħ zyku programowania, który pozwala na u Ň ywanie zmiennych

dynamicznych. W C++ s Ģ to odpowiednio new i delete . Tak wi ħ c:

polecenie new nazwa_typu przydziela pami ħę na zmienn Ģ dynamiczn Ģ takiego typu, jaki wskazuje nazwa_typu . Adres

przydzielonej pami ħ ci jest zwracany jako wynik. Je Ň eli alokacja (przydział pami ħ ci) si ħ nie powiedzie, np. pami ħ ci ju Ň nie

wystarczy, zostanie wstawiony adres zerowy, oznaczany w C++ poprzez NULL . Fachowo rzecz ujmuj Ģ c - new nie jest

poleceniem, tylko operatorem o nast ħ puj Ģ cej składni wywołania:

zmienna_wska Ņ nikowa = new nazwa_typu ;

polecenie delete zmienna_wska Ņ nikowa odbiera pami ħę zarezerwowan Ģ na zmienn Ģ dynamiczn Ģ umieszczon Ģ pod

adresem pami ħ tanym w zmienna_wskaznikowa . Składnia wywołania tego operatora ma posta ę :

delete zmienna_wska Ņ nikowa ;

http://iair.mchtr.pw.edu.pl/~bputz/aisd_cpp/druk.php?id=27

2008-03-21 00:08:48

Algorytmy i Struktury danych, wer. C/C++, Lekcja 4: Listy

Strona 5

Oba operatory maj Ģ specjaln Ģ posta ę w przypadku alokacji i zwalniania tablic. C++ pozwala alokowa ę bezpo Ļ rednio jedynie tablice

jednowymiarowe (wektory). Aby zaalokowa ę tablic ħ jednowymiarow Ģ , wykorzystujemy operator new w nast ħ puj Ģ cej postaci:

zmienna_wska Ņ nikowa = new nazwa_typu_elementów [ rozmiar ];

Tablic ħ jednowymiarow Ģ usuwamy za Ļ z pami ħ ci za pomoc Ģ operatora delete wywoływanego nast ħ puj Ģ co:

delete [] zmienna_wska Ņ nikowa ;

Jak poradzi ę sobie z tablicami o wi ħ kszej liczbie wymiarów - o tym troch ħ ni Ň ej.

I jescze uwaga odno Ļ nie odwoływania si ħ do pól zmiennych strukturalnych (rekordowych) dost ħ pnych przez wska Ņ nik. Poniewa Ň

operator wyłuskania * ma ni Ň szy priorytet ni Ň operator . wykorzystywany do odwoływania si ħ do pól rekordów, zapis:

*ad_auta.cena = 35000;

jest nieprawidłowy - bo w ten sposób próbujemy si ħ dosta ę do pami ħ ci, której adres jest umieszczony w polu cena struktury - a to nie

jest wska Ņ nik, tylko zwykła liczba. Wi ħ c prawidłowo powinni Ļ my zapisa ę :

(*ad_auta).cena = 35000;

Jest tak Ň e inna metoda. W przypadku wska Ņ ników mo Ň na zast Ģ pi ę operator kropki jego specjaln Ģ postaci Ģ -> . Tak wi ħ c je Ļ li ad_

auta jest wska Ņ nikiem na struktur ħ , to mo Ň emy równowa Ň nie do powy Ň szego zapisu napisa ę :

ad_auta->cena = 35000;

I taki wła Ļ nie zapis b ħ dziemy wykorzystywali.

Powró ę my wi ħ c

naszych

przykładów. Przed

pierwszym

wykorzystaniem

zmiennej

wskazywanej

przez wsk_i ,

musimy

zarezerwowa ę dla niej miejsce w pami ħ ci:

wsk_i = new int ;

Je Ļ li pami ħę zostanie przydzielona, w zmiennej wsk_i znajdzie si ħ adres tej zmiennej.

Nast ħ pnie mo Ň emy zacz Ģę korzystanie ze zmiennej:

*wsk_i = 20;

cout << "Wartosc wskazywana powiekszona o 5 " << (*wsk_i)+5 << endl;

Na koniec pozostaje nam zwolnienie pami ħ ci (posprz Ģ tanie po sobie).

delete wsk_i;

Cały program mógłby wygl Ģ da ę wi ħ c tak:

...

int *wsk_i;

wsk_i = new int ;

*wsk_i = 20;

cout << "Wartosc wskazywana powiekszona o 5 " << (*wsk_i)+5 << endl;

delete wsk_i;

...

W tym miejscu mogliby Ļ cie powiedzie ę , Ň e nie bardzo widzicie sens pisania w ten sposób, skoro zastosowanie wska Ņ ników nie daje

praktycznie Ň adnej nowej funkcjonalno Ļ ci. W nast ħ pnym segmencie tej lekcji zobaczycie, Ň e jednak pozwalaj Ģ one tworzy ę zupełnie

nowe struktury danych. Ale ju Ň za chwil ħ poka Ň emy Wam nowy rodzaj tablic, który zawdzi ħ czamy wska Ņ nikom.

Teraz jeszcze program, który jest schowany - ju Ň tylko dla ciekawskich:

http://iair.mchtr.pw.edu.pl/~bputz/aisd_cpp/druk.php?id=27

2008-03-21 00:08:48

Algorytmy i struktury danych - 04. Listy.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: