Języki programowania  część VII
Marcin Szpyrka
Katedra Automatyki
Akademia Górniczo-Hutnicza w Krakowie
2009/10
Marcin Szpyrka Języki programowania  część VII 1/32
Statyczne i dynamiczne struktury danych
Statyczna struktura danych:
Posiada z góry ustalony rozmiar (bez możliwości jego zmiany);
Jej deklaracja poprzedza uruchomienie głównej procedury programu;
Liczba zmiennych o typie statycznych musi być z góry znana;
Pamięć jest przydzielana na wstępie, a oddawana po zakończeniu programu.
Dynamiczna struktura danych:
Ilość wymaganej pamięci przez struktury danych nie musi być znana przed
uruchomieniem programu;
Przydział pamięci następuje dynamicznie w czasie realizacji odpowiedniej
części programu;
Po wykonaniu zadań struktury danych powinny być usunięte, a przydzielona
dynamicznie pamięć zwolniona;
Wadą struktur dynamicznych są złożone operacje dodawania i usuwania
elementów struktury.
Marcin Szpyrka Języki programowania  część VII 2/32
Model grafowy struktury danych
e
d1 d3 dn
d2
a)
e
d1 d3 dn
d2
b)
e
d1 d3 dn
d2
c)
Modele grafowe: a) lista jednokierunkowa, b) lista dwukierunkowa, c) lista cykliczna
jednokierunkowa
Marcin Szpyrka Języki programowania  część VII 3/32
Realizacja listy dwukierunkowej
data data data
NULL NULL
previous next previous next previous next
data data data
NULL NULL
previous next previous next previous next
Marcin Szpyrka Języki programowania  część VII 4/32
Lista dwukierunkowa  przykład
1 class List {
2 private:
3 class Node {
4 public:
5 int data;
6 Node
*previous, *next;
7 Node()
8 {
9 data = 0;
10 previous = next = NULL;
11 }
12 };
13
14 void addFirst(Node
*x);
15 void addMiddle(Node
*x);
16 void addLast(Node
*x);
17 void deleteFirst();
18 void deleteMiddle();
19 void deleteLast();
20
21 Node
*first, *last, *current;
Marcin Szpyrka Języki programowania  część VII 5/32
Lista dwukierunkowa  przykład
1 public:
2 List(){first = last = current = NULL; }
3 ~List();
4 void addElement(int x);
5 void deleteElement();
6
7 int getCurrent() { return current->data; }
8 int getFirst() { return first->data; }
9 int getLast() { return last->data; }
10 void atBeginning() { current = first; }
11 void behindEnd() { current = NULL; }
12
13 Node previousElement()
*
14 {
15 if(current != first) current = current->previous;
16 return current;
17 }
18
19 Node nextElement()
*
20 {
21 if(current != last) current = current->next;
22 return current;
23 }
24
25 void atNth(int n);
26 int size();
27 };
Marcin Szpyrka Języki programowania  część VII 6/32
Lista dwukierunkowa  przykład
1 void List::addElement(int x)
2 {
3 //wstawiamy zawsze przed wybranym węzłem
4 Node e;
*
5 e = new Node;
6 e->data = x;
7 // rozpoznajemy miejsce wstawiania i wybieramy odpowiednią
8 // funkcję do wstawienia elementu
9 if(current != NULL)
10 if(current != first) addMiddle(e);
11 else addFirst(e);
12 else addLast(e);
13 }
14
15 void List::addFirst(Node x)
*
16 {
17 x->next = current;
18 x->previous = NULL;
19 current->previous = x;
20 first = current = x;
21 }
Marcin Szpyrka Języki programowania  część VII 7/32
Lista dwukierunkowa  przykład
1 void List::addMiddle(Node x)
*
2 {
3 (current->previous)->next = x;
4 x->next = current;
5 x->previous = current->previous;
6 current->previous = x;
7 }
8
9 void List::addLast(Node x)
*
10 {
11 if(first == NULL)
12 first = last = x; //pusta lista
13 else
14 {
15 x->next = NULL;
16 x->previous = last;
17 last->next = x;
18 last = x;
19 }
20 } //current pozostaje NULL
Marcin Szpyrka Języki programowania  część VII 8/32
Lista dwukierunkowa  przykład
1 void List::deleteElement()
2 {
3 if(current == NULL) return;
4 // rozpoznajemy miejsce usuwania i wybieramy odpowiednią
5 // funkcję do usunięcia elementu
6 if(current == first) deleteFirst();
7 else
8 if(current == last) deleteLast();
9 else deleteMiddle();
10 }
11
12 void List::deleteFirst()
13 {
14 first = first->next;
15 first->previous = NULL;
16 delete current;
17 current = first;
18 }
Marcin Szpyrka Języki programowania  część VII 9/32
Lista dwukierunkowa  przykład
1 void List::deleteMiddle()
2 {
3 Node
*temp;
4 temp = current->previous;
5 temp->next = current->next;
6 (current->next)->previous = temp;
7 delete current;
8 current = temp;
9 }
10
11 void List::deleteLast()
12 {
13 Node
*temp;
14 temp = current->previous;
15 temp->next = NULL;
16 last = temp;
17 delete current;
18 current = NULL;
19 }
Marcin Szpyrka Języki programowania  część VII 10/32
Lista dwukierunkowa  przykład
1 List::~List()
2 {
3 // usuwamy wszystkie elementy listy
4 Node temp;
*
5 for(current = first; current; )
6 {
7 temp = current->next;
8 delete current;
9 current = temp;
10 }
11 }
12
13 void List::atNth(int n)
14 {
15 current = first;
16 for(int i = 1; i < n; ++i)
17 current = current->next;
18 }
Marcin Szpyrka Języki programowania  część VII 11/32
Lista dwukierunkowa  przykład
1 int List::size()
2 {
3 Node temp;
*
4 int i = 0;
5 if(first != NULL)
6 {
7 temp = first;
8 i = 1;
9 }
10 while(temp != last)
11 {
12 temp = temp->next;
13 ++i;
14 }
15 return i;
16 }
Marcin Szpyrka Języki programowania  część VII 12/32
Szablony klas
Szablony klas służą do generowania podobnych do siebie klas, różniących się
jedynie typem argumentu (typami argumentów), na których pracują, np. na
generowanie list dwukierunkowych dla różnych typów danych
przechowywanych w węzłach.
Klasy wygenerowane z tego samego szablonu są zupełnie od siebie niezależne.
Nazwy ich różnią się nazwami typów umieszczonych w nawiasie ostrokątnym,
np.:List,ListNazwa klasy szablonowej składa się z nazwy
szablonu i nazwy (nazw) parametru umieszczonej w nawiasie ostrokątnym.
Kompilator wykorzystuje szablon klasy do generowania klas szablonowych nie
tylko w przypadku, gdy deklarujemy obiekt takiej klasy. Jest tak również w
sytuacji, gdy:
 definiujemy wskaz
nik do pokazywania na obiekty takiej klasy;
 deklarujemy funkcję zawierającą nazwę klasy szablonowej;
 wykorzystujemy nazwę klasy szablonowej przy dziedziczeniu jako nazwę klasy
podstawowej;
Marcin Szpyrka Języki programowania  część VII 13/32
Kolekcje
Kolekcja (pojemnik) jest to obiekt, który jest zdolny do przechowywania
obiektów innej klasy i zarządzania nimi.
Kolekcje mogą być realizowane w dwóch wersjach. Kolekcja bezpośrednia
przechowuje kopie obiektów, które do niego wstawiamy (niezalecane dla
dużych obiektów), natomiast kolekcja pośrednia przechowuje wskaz
niki do
obiektów (nadaje się jednocześnie do przechowywania obiektów klasy
podstawowej jak i obiektów klas pochodnych).
Wybór wersji realizacji kolekcji zależy od konkretnego zastosowania. Dla
pojemnika pośredniego wydłuża się nieznacznie czas odstępu (w pierwszym
etapie dostajemy dopiero wskaz
nik), dla pojemnika bezpośredniego wymagana
jest większa ilość pamięci.
Marcin Szpyrka Języki programowania  część VII 14/32
Kolekcje w bibliotece standardowej
W bibliotece standardowej zdefiniowano szereg kolekcji tak, by zapewniały one
maksymalną swobodę w projektowaniu pojedynczej kolekcji, a równocześnie
udostępniały użytkownikom wspólny interfejs.
Kolekcje Opis
vector jednowymiarowa tablica elementów typu T
list podwójnie wiązana lista elementów typu T
deque kolejka o dwóch końcach z elementami typu T
queue kolejka elementów typu T
stack stos elementów typu T
map tablica asocjacyjna elementów typu T
set zbiór elementów typu T
bitset tablica elementów typu logicznego
Iteratory
Iteratory można traktować jak wskaz
niki do elementów kolekcji. Każda kolekcja
dostarcza typ o nazwie iterator do wskazywania elementów, a także typ
const_iterator do używania w sytuacji, gdy elementy nie muszą być modyfikowane.
Iteratorów można używać do nawigowania po kolekcji bez znajomości
rzeczywistego typu użytego do identyfikowania elementów.
Marcin Szpyrka Języki programowania  część VII 15/32
Typy kolekcji
Wektor
Kolekcja typu wektor jest to kolekcja przypominająca swoją strukturą tablicę
jednowymiarową. Istnieje swobodny, bezpośredni dostęp do dowolnego z
przechowywanych obiektów. Jeżeli chcemy przechowywać obiekty w określonej
kolejności, to czas zużyty na operację wpisania obiektu do (usunięcia obiektu z)
kolekcji jest liniowo zależny od miejsca, w które należy wstawić (z którego należy
usunąć) obiekt. Im bliżej początku, tym czas jest dłuższy.
Lista jednokierunkowa
Kolekcja typu lista jednokierunkowa jest kolekcją, której wewnętrzna struktura jest
zorganizowana na zasadzie listy jednokierunkowej. W liście jednokierunkowej
możemy wędrować wyłącznie w jedną stronę (wg. wskaz
ników). W porównaniu do
wektora nie ma bezpośredniego dostępu do poszczególnych elementów listy. Z
drugiej strony wstawianie elementów do listy jest bardzo proste niezależnie od
miejsca w którym umieszczany jest nowy element.
Marcin Szpyrka Języki programowania  część VII 16/32
Typy kolekcji
Lista dwukierunkowa
Kolekcja typu lista dwukierunkowa jest kolekcją, której wewnętrzna struktura jest
zorganizowana na zasadzie listy dwukierunkowej. Każdy obiekt zawiera wskaz
nik
do następnego i poprzedniego elementu na liście. W liście dwukierunkowej możemy
wędrować w obie strony. W porównaniu do wektora nie ma bezpośredniego dostępu
do poszczególnych elementów listy, natomiast wstawianie elementów do listy jest
bardzo proste niezależnie od miejsca w którym umieszczany jest nowy element.
Talia
Kolekcja typu talia jest kombinacją kolekcji typu wektor i lista. Kolekcja typu talia
rezerwuje bloki o ściśle określonej wielkości. Do takiego bloku wkłada się wiele
obiektów podobnie jak do wektora. Gdy cały blok zostaje zapełniony, rezerwowany
jest kolejny. Efektem takiego postępowania jest lista bloków. W kolekcji tej mamy
wygodny sposób poruszania się w obrębie pojedynczego bloku, oraz łatwość
dodawania do skrajnych bloków.
Marcin Szpyrka Języki programowania  część VII 17/32
Typy kolekcji
Stos
Kolekcja typu stos ma podobną strukturę wewnętrzną jak lista jednokierunkowa,
przy czym wstawianie i usuwanie elementu możliwe jest wyłącznie z wierzchołka
stosu. Stos można zrealizować również w oparciu o kolekcję typu wektor.
Kolejka
Kolekcja typu kolejka ma podobną strukturę wewnętrzną jak lista jednokierunkowa
przy czym w przeciwieństwie do stosu dodawanie obiektów możliwe jest tylko na
końcu kolejki, a usuwanie tylko na początku kolejki. Elementy z kolejki usuwane są
dokładnie w takiej samej kolejności jak były na niej umieszczane.
Marcin Szpyrka Języki programowania  część VII 18/32
Typy kolekcji
Zbiór
Kolekcja typu zbiór jest kolekcją sekwencyjną, w której obiekty ustawiane są w
ściśle ustalonym porządku (np. alfabetycznie), dzięki czemu można łatwo i szybko
wyszukać odpowiedni element. Kolekcja ta może być realizowana w oparciu o
strukturę listy.
Mapa
Kolekcja typu mapa jest kolekcją sekwencyjną, w którym przechowuje się pary
obiektów (jeżeli obiekty są tego samego typu, to mówimy o słowniku). Jeden z
elementów pary pełni rolę klucza według którego wstawiane są nowe węzły i według
którego wykonywane jest wyszukiwanie. Drugi element pary to przechowywane
dane.
Marcin Szpyrka Języki programowania  część VII 19/32
Kolekcja vector
Standardowy vector jest szablonem zdefiniowanym w przestrzeni nazwstdi
dostępnym po dołączeniu nagłówka.
Metoda Opis
begin() wskazuje na pierwszy element
end() wskazuje na element pierwszy za ostatnim
rbegin() wskazuje na pierwszy element w ciągu odwróconym
rend() wskazuje na element pierwszy za ostatnim w ciągu odwróconym
Wektor indeksuje się za pomocą metod operator[] i at(); operator[] zapewnia
niekontrolowany dostęp, podczas gdy at() wykonuje kontrolę zakresu i zgłasza
wyjątek out_of_range, gdy indeks wykracza poza zakres.
Metoda Opis
front() pierwszy element
back() ostatni element
[] indeksowanie, dostęp niekontrolowany (nie dla list)
at() indeksowanie, dostęp kontrolowany (nie dla list)
Marcin Szpyrka Języki programowania  część VII 20/32
Kolekcja vector
Kolekcja wektor dostarcza pełny zbiór konstruktorów, destruktor i operacje
kopiujące. Zmiana rozmiaru wektora jest możliwa, ale jest to operacja kosztowna,
zwykle początkowy rozmiar ustala się podczas tworzenia wektora.
vector v1(100);
vector v2(12); // pracuje kostr. domyślny
vector v3(12,nowy_typ(2));
Konstruktor kopiujący i operator przypisania powielają elementy wektora, dlatego
wektory powinny być przekazywane przez referencję.
Funkcje assign istnieją jako odpowiedniki wieloargumentowych konstruktorów.
Wykorzystuje się je, gdy potrzebna jest wartość domyślna lub zakres wartości.
Metoda Opis
operator= operator przypisania
assign(n,x) przypisz n kopii x
assign(first, last) przypisz z [first:last]
Przypisanie zmienia całkowicie elementy wektora. Są wymazywane wszystkie stare
elementy i wstawiane nowe. Po przypisaniu rozmiarem wektora jest liczba
przypisanych elementów.
Marcin Szpyrka Języki programowania  część VII 21/32
Kolekcja vector
Wektor można wykorzystać do implementacji stosu. Dostępne są dla niego operacje
charakterystyczne dla stosu. Operacje te można wykorzystać również do
przyrostowego konstruowania wektora.
Metoda Opis
push_back(x) wstaw na koniec
pop_back() usuń ostatni element
Dla wektora można używać metod charakterystycznych dla list.
Metoda Opis
insert(p,x) wstaw x przed p
insert(p,n,x) wstaw n kopii x przed p
insert(p,first,last) wstaw elementy z [first:last] przed p
erase(p) usuń element wskazywany przez p
erase(first,last) usuń [first:last]
clear() usuń wszystkie elementy
Marcin Szpyrka Języki programowania  część VII 22/32
Kolekcja vector
Metoda Opis
size() liczba elementów
empty() czy kolekcja jest pusta
capacity() pamięć przydzielona na wektor
reserve() przydziel pamięć na przyszłe rozszerzenie
resize() zmień rozmiar kolekcji
swap() zamień elementy dwóch kolekcji
==, !=, < operatory
Marcin Szpyrka Języki programowania  część VII 23/32
Kolekcja vector  przykład
1 #include
2 #include
3 #include
4 using namespace std;
5
6 int main(int argc, char
*argv[]) // stl-vector2.cpp
7 {
8 if (argc == 2)
9 {
10 vector v;
11 ifstream in(argv[1]);
12 string line;
13
14 while(getline(in, line)) v.push_back(line);
15
16 for(int i = 0; i < v.size(); i++)
17 cout << i << ": " << v[i] << endl;
18 }
19 else
20 cout << "Błędna liczba parametrów.\n";
21 }
Marcin Szpyrka Języki programowania  część VII 24/32
Sytuacje wyjątkowe
Z sytuacją wyjątkową mamy do czynienia wówczas, gdy z pewnych powodów (np.
brak pliku z danymi, nieprawidłowych danych itp.) nie jest możliwe wykonanie
określonej funkcji lub ciągu instrukcji. Aby uniknąć gwałtownego przerwania
wykonywania się programu można obsłużyć sytuację wyjątkową definiując
odpowiedni fragment kodu, który jest wykonywany przy zajściu określonej sytuacji
wyjątkowej.
W celu skorzystania z mechanizmu obsługi wyjątków należy:
 Określić kiedy zaczyna się obszar, gdzie spodziewane jest wystąpienie sytuacji
wyjątkowej (blok try).
 W odpowiednim momencie, gdy zajdzie sytuacja wyjątkowa, zasygnalizować ją
(instrukcja throw).
 Przygotować fragment kodu, który zajmie się reakcją na wykrytą sytuację
wyjątkową (blok catch).
Marcin Szpyrka Języki programowania  część VII 25/32
Sytuacje wyjątkowe
1 try {
2 // ...
3 throw (float);
4 // ...
5 throw (char);
6 // ...
7 throw (zadanie);
8 }
9 catch (float)
10 { ... }
11 catch (char)
12 { ... }
13 catch (zadanie)
14 { ... }
Możliwe jest zdefiniowanie kilku bloków catch, z których wybierany jest jeden w
zależności od tego jaka sytuacja wyjątkowa jest zgłaszana. Sekcje catch muszą
wystąpić bezpośrednio po sekcji try. W przypadku zgłoszenia wyjątku następuje
próba dopasowania typu zwróconego obiektu do kolejnych sekcji catch, w kolejności
w jakiej zostały one umieszczone. Jeśli dopasowanie się powiedzie, to pozostałe
sekcje catch są ignorowane. Kompilator kończy obsługę wyjątku po przeniesieniu
sterowania do odpowiedniej sekcji catch. Po wykonaniu instrukcji w niej zawartych
następuje przeniesienie sterowania poza ostatnią z sekcji catch.
Marcin Szpyrka Języki programowania  część VII 26/32
Dopasowanie sekcji do obsługi wyjątku
Informację o wystąpieniu sytuacji wyjątkowej można zgłosić na dwa sposoby, albo
wysyłając jedynie obiekt określonej klasy (mogą to być klasy definiowane przez
użytkownika) bez interesowania się jego wartością, albo przesyłając obiekt, którego
wartość ma istotne znaczenie na sposób obsługi wyjątków.
Dopasowanie argumentu wyjątku do właściwego argumentu oczekiwanego następuje
w oparciu o zasadę: Użyty będzie pierwszy blok catch, który się nada, kolejne
(nawet gdyby w lepiej pasowały) zostaną zignorowane. Dana procedura obsługi
nadaje się do obsługi danego typu wyjątku, gdy:
 typy argumentu rzucanego i oczekiwanego są takie same;
 typ argumentu oczekiwanego ma dodatkowo przydomek const;
 w instrukcji throw rzucamy obiekt jakiegoś typu, a blok catch oczekuje
referencji do tego obiektu;
 typ argumentu oczekiwanego jest publiczną klasą podstawową typu argumentu
rzucanego;
 obiekt rzucany przez instrukcję throw jest wskaz
nikiem do pewnego typu A, a
blok catch oczekuje wskaz
nika do typu B, i wskaz
nik do typu B może być
zamieniony na wskaz
nik do typu A z użyciem konwersji standardowych.
Marcin Szpyrka Języki programowania  część VII 27/32
Obsługa wyjątków  uwagi
Mechanizm obsługi wyjątków umożliwia alternatywny, w odniesieniu do instrukcji
return, powrót z funkcji. Instrukcja throw jest w pewnym sensie rodzajem instrukcji
return. W odniesieniu do return, instrukcja throw może zwracać wartości różnych
typów, podczas gdy return musi zwrócić wartość zgodnie z zadeklarowanym typem
wyniku funkcji. Ponadto instrukcja return powoduje przeniesienie sterowania do
miejsca, gdzie została wywołana funkcja, zaś instrukcja throw przenosi sterowanie
bezpowrotnie do innego obszaru pamięci, w którym obsługuje się sytuacje
wyjątkowe.
Mechanizm obsługi wyjątków przydaje się najczęściej wtedy, gdy muszą ze sobą
współpracować dwa odmienne fragmenty kodu, z których jeden potrafi wykryć
sytuację wyjątkową, ale nie potrafi sobie z nią poradzić, podczas, gdy drugi nie
potrafi wykryć sytuacji wyjątkowej, ale potrafi ją obsłużyć. Przykładem może być
współpraca funkcji bibliotecznej, z programem głównym.
Sekcje try mogą być w sobie zagnieżdżone. Jeżeli w bloku wewnętrznym zostanie
zgłoszony wyjątek, to w pierwszej kolejności nastąpi próba obsłużenia go przez
sekcje catch znajdujące się bezpośrednio po nim. Jeżeli nie uda się dopasować typu
zwróconego obiektu, do żadnej z sekcji catch, nastąpi próba dopasowania do sekcji
catch znajdujących się o jeden poziom wyżej itd. Kolejne wykonywane instrukcje
programu, to te które znajdują się poza ostatnią sekcją catch na tym poziomie, który
potrafił obsłużyć wyjątek.
Marcin Szpyrka Języki programowania  część VII 28/32
Obsługa wyjątków  przykład
1 class Stack { // stack4.h (stack4.cpp, stack4main.cpp)
2 protected:
3 int size;
4 int top;
5 float
*data;
6 public:
7 Stack();
8 Stack(int size);
9 Stack(const Stack &source);
10 Stack & operator=(const Stack &source);
11
12 ~Stack() { delete [] data; }
13
14 void push(float x);
15 float pop();
16
17 int currentSize() { return (top + 1); }
18
19 int getSize() { return size; }
20 };
Marcin Szpyrka Języki programowania  część VII 29/32
Obsługa wyjątków  przykład
1 void Stack::push(float x)
2 {
3 if(top < size - 1) data[++top] = x;
4 else throw (int) 1; // zgłoszenie wyjątku o wartości 1
5 }
6
7
8 float Stack::pop()
9 {
10 if(top >= 0) return data[top--];
11 else throw (int) 2;
12 }
Marcin Szpyrka Języki programowania  część VII 30/32
Obsługa wyjątków  przykład
1 Stack s(10); float i; int j;
2
3 try
4 {
5 while(!(in.eof()))
6 {
7 in >> i;
8 s.push(i);
9 }
10 }
11 catch(int x)
12 {
13 if(x == 1) cout << "Brak miejsca na stosie!!!\n";
14 }
15
16 cout << "Stan stosu: " << s.currentSize() << endl;
17 cout << "Ile obiektów usunąć ze stosu : ";
18 cin >> i;
19 try
20 {
21 for(j = 0; j < i; ++j) cout << s.pop() << endl;
22 }
23 catch(int x)
24 {
25 if(x == 2) cout << "Brak danych na stosie!!!\n";
26 }
Marcin Szpyrka Języki programowania  część VII 31/32
Metody przerywania wykonywania programu
W bibliotece cstdlib znajdują się funkcje umożliwiające drastyczne przerwanie
wykonywania programu.
void exit(int status);
Funkcja kończy wykonanie programu, ale przed zakończeniem zamykane są
wszystkie pliki i opróżniane bufory. Argument funkcji służy do opisania
powodu zakończenia programu (np. kod błędu). Wartość zero oznacza, że
program zakończył się  normalnie po wykonaniu wszystkich instrukcji.
void abort(void);
Funkcja podobnie jak wcześniejsza kończy wykonanie programu, przy czym
przerwanie jest brutalne, bez wykonywania dodatkowych operacji.
Przy wystąpieniu sytuacji wyjątkowej, jeżeli dany wyjątek nie zostanie złapany przez
żaden blok catch, zostaje wykonana specjalna funkcja void terminate(); W ciele tej
funkcji wywoływana jest funkcja abort.
Poza sytuacją, gdy wyrzucony wyjątek nie został złapany przez żaden blok catch,
instrukcja terminate jest wywoływana, gdy: wystąpił błąd wewnętrzny (np.
przesłanie napisu zamiast liczby), pojawienie się nowego wyjątku podczas gdy
kompilator przystępuje do odwikładnia stosu, wystąpienie kolejnego wyjątku, zanim
obsłużony został bieżący wyjątek.
Marcin Szpyrka Języki programowania  część VII 32/32