egzaminKokot

Question 1

Typ tablicowy, tworzenie własnych typów, struktury danych zawarte w bibliotece STL

Answer 1

Typ tablicowy
Tablica jest to kolekcja elementów tego samego typu umieszczona w pamięci w sposób nierozłączny (kolejne wartości są koło siebie w pamięci). Do poszczególnych wartości można się odwoływać indywidualnie używając odpowiedniego indeksu tablicy (wskaźnika na miejsce w pamięci). Bazowo tablice nie są zainicjowane. Oznacza to, że żaden element tablicy nie ma przypisanej konkretnej wartości. Do konkretnych wartości tablicy można się odwołać korzystając z podania odpowiedniej wartości liczbowej w kwadratowych nawiasach.

Tworzenie własnych typów danych
Programista może utworzyć następujące typy: klasa, struktura, unia
typ wyliczeniowy oraz typedef

klasa
Jest to typ, który prowadzi do programowania obiektowego (konkretnie abstrakcji). Może zawierać zmienne oraz metody, jak również dziedziczyć inne klasy. W klasach można zdefiniować zakresy dostępu co pozwala na hermetyzację metod i pól, oraz ukrycie przed użytkownikiem logiki, do której nie powinien mieć dostępu. Przechowywana jest na zarządzalnej stercie. Bazowo wszystko jest prywatne

struktura
Jest to typ użyteczny przy grupowaniu powiązanych ze sobą zmiennych. Tak jak klasa umożliwia przechowywanie zmiennych jak również metod oraz dziedziczenie. Instancja jest przechowywana na stosie. Bazowo wszystko jest publiczne

unia
Unia jest to typ w którym zmienne dzielą przypisane miejsce w pamięci. Jeżeli utworzymy typ union przechowujący dwie zmienne to zmiana jednej z nich zostanie odzwierciedlona w drugiej.

typ wyliczeniowy
Typ wyliczeniowy to typ, który pozwala na zwiększenie czytelności kodu. Pozwala na przypisanie nazw do stałych wartości liczbowych np. zamiast zmiennych stałch praca = 1 i przestuj = 0 można zdefiniować typ wyliczeniowy i tam uwzględnić te stany.

typedef
Celem typedef jest przypisanie nazw alternatywnych do istniejących typów, najczęściej tych, których standardowa deklaracja jest zbyt trudna lub może wprowadzić programistę w błąd.

typedef map<int, vector<int> > Kolejki;</int>

int f(const Kolejki& kolejka) {
…
}

int g() {
Kolejki kolejka;
int wynik = f(kolejka);
}

STL
Standard Template Library (w skrócie STL) jest standardową biblioteką szablonów, wchodzącą w skład podstawowych bibliotek C++.
queue — implementacja kolejki fifo,
stack — implementacja stosu
deque — implementacja listy dwukierunkowej,
priority_queue — implementacja kolejki priorytetowej,
vector — implementacja struktury podobnej do tablicy,
map — tablica asocjacyjna, której klucze nie powtarzają się,
multimap — tablica asocjacyjna, której klucze powtarzają się,
set — zbiór uporządkowany, którego elementy nie powtarzają się ,
multiset — zbiór uporządkowany, którego elementy powtarzają się ,
list — implementacja listy dwukierunkowej,
forward_list — implementacja listy jednokierunkowej.

Question 2

Polimorfizm i metody wirtualne, mechanizm RTTI, klasa abstrakcyjna w C++ (rtti - wskazać wady, może dopytać o interfejsy w C++)

Answer 2

Polimorfizm
Polimorfizm opiera się o metody wirtualne (poprzedzone słowem kluczowym virtual). Charakteryzuje się on tym, że metody wirtualne w klasie polimorficznej nie korzystają z typu statycznego (zdefiniowanego jako typ wskaźnika), a z typu dynamicznego, czyli zależnego od instancji. Zakładając, że klasa A i klasa B maja metode wirtualna

virtual void method(){
//methods body
}

oraz B dziedziczy po A, można utworzyć następujące wskaźniki:
ClassA* classA = new ClassB();
ClassB* classB = new ClassB();.

Wywołanie metody classA->method() da taki sam rezultat jak classB->method(), mimo że typy wskaźników są różne. Pominięcie słowa kluczowego virtual wywołałoby różne działanie funkcji, zależne od definicji w klasie A i klasie B. Wykorzystując metody wirtualne, należy pamiętać o wirtualnych destruktorach, które pozwolą na prawidłowe zwalnianie pamięci, dla klas dziedziczących.

Mechanizm RTTI
Mechanizm RTTI (ang. run-time type information) polega na wykorzystaniu znajomości typu danej klasy podczas wykonywania programu. Poza wykorzystaniem typeid(class_instance), która zwraca obiekt typu std::type_info, co pozwala na porównanie typów obiektów, mechanizm RTTI oferuje operator dynamic_cast<T*>(class_instance_pointer).

Wykorzystywanie dynamicznego rzutowania pozwala na rozpoznanie czy obiekt jest instancja klasy potomnej oraz transformacje na klasę bardziej specyficzna. Oznacza to, że rzutowanie klasy nadrzędnej na klasę podrzędna umożliwia wykonywanie jej metod.

Parametrem dynamic_cast<>() może być referencja lub wskaźnik na instancje klasy, rzutowanie na klasę wyżej w hierarchii spowoduje wyjątek (dla referencji) lub zwrócenie nullptr, co jak wspomniano, może posłużyć do rozpoznawania dynamicznego typu obiektów.

Minusami RTTI jest zwiększone wykorzystanie pamięci oraz spowolnienie wykonywania programu. Każda klasa, która wykorzystuje metody wirtualne ma dodatkowo przypisywaną informację RTTI (nazwa, oraz informacja o klasach bazowych - czyli informacje używane przy dynamicznym rzutowaniu). Gorsza wydajność wynika z tego, że przy wykorzystywaniu dynamicznego rzutowania trzeba każdorazowo znaleźć informacje o danej klasie w pliku generowanym przez mechanizm RTTI.

Klasy abstrakcyjne
Klasy abstrakcyjne to takie, których co najmniej jedna metoda jest zadeklarowana w następujący sposób:
virtual void method()= 0;
Wykorzystuje się je do projektowania interfejsów, gdyz klasy abstrakcyjne nie pozwalają na tworzenie obiektów, można jednakże używać ich do dziedziczenia. Klasa podrzędna klasy abstrakcyjnej powinna zawierać implementacje wspomnianych metod wirtualnych (ang. pure virtual).

Question 3

Sortowanie

Answer 3

Algorytmy sortowania klasyfikuje się względem czasowej złożoności obliczeniowej, a także stabilności.

Algorytmy stabilne nie zamieniają miejscami elementów o takim samym kluczu np. sortowanie listy
L = {0, 3, 50, 10, 2,−3, 500}
skutkuje lista posortowana
S = {−3, 0, 2, 3, 50, 500, 10}.

Popularne algorytmy sortowania:
* sortowanie przez wstawianie (złożoność O(n2); algorytm przegląda całą tablice; każdy poprawny element jest wstawiany we właściwym miejscu w kolejce wyjściowej; wymaga porównywania elementów w kolejce wyjściowej z pobranym elementem),

• sortowanie przez scalanie (złożoność O(nlogn); algorytm porównuje liczby parami; pary są scalane w większe ciągi; scalanie uwzględnia sortowanie),
• sortowanie przez wybieranie (złożoność O(n2); algorytm niestabilny; pobiera z ciągu liczb najmniejsza i wstawia na koniec kolejki wyjściowej),
• sortowanie Shella (złożoność zależy od odstępów; algorytm niestabilny; grupuje elementy ze zmniejszającym się krokiem np.
  k = {7, 5, 3, 1};
  sortowanie elementów w grupie odbywa się przez wstawianie np.
  z1 = {a1, a6, a11} = {3, 17, 2} ) {2, 3, 17}),
• sortowanie szybkie (złożoność O(nlogn); algorytm niestabilny; wybierany jest tzw. pivot – najczęściej jako ostatni element; od pivot’a podąża indeks powodując podział na zbiór wartości większych i mniejszych lub równych; pivot jest elementem pomiędzy tablicami; kroki są powtarzane dla mniejszych list; jeden element w liście kończy działanie algorytmu).