Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:jimp2:2017:labs:pamiec-i-pliki [2017/03/01 21:48] mwp [Ćwiczenia] |
pl:dydaktyka:jimp2:2017:labs:pamiec-i-pliki [2019/06/27 15:50] (aktualna) |
}</code> | }</code> |
| |
| Niestety należy pamiętać o tym by zwolnić pamięć przydzieloną inaczej uzyskujemy wyciek pamięci i program w trakcie działania zaczyna zużywać coraz więcej pamięci operacyjnej mimo, że już jej i tak nigdy nie użyje! Sprawa też nie jest taka prosta, bo nie zawsze wiadomo, czy pewne elementy nie są już na pewno przez nikogo używane. |
| |
| === Brak wartości === |
| |
| W C%%++%%11 nie używamy już makra **NULL** zostało dodane specjalne słowo kluczowe reprezentujące pusty wskaźnik **nullptr** |
| |
| <code cpp> |
| int *v = nullptr; |
| delete v; |
| </code> |
| |
| |
| =====Ale jest nadzieja - zautomatyzowane zarządzanie pamięcią część pierwsza===== |
| |
| Jedną z możliwości automatycznego zarządzania pamięcią jest oddelegowanie tego zadania do kontenerów zdefiniowanych w bibliotece standardowej, |
| które automatycznie zwolnią pamięć jeśli przestanie ona być używana. |
| ==== Vector ==== |
| |
| Jednym z takich kontenerów jest tablica rozszerzalna [[http://en.cppreference.com/w/cpp/container/vector|vector]], zapoznać się z dokumentacją |
| uruchomić przykłady podane w dokumentacji przez **run code** i przyglądnąć się dokumentacji funkcji: |
| * emplace_back |
| * pop_back |
| * clear |
| Przenalizować poniższy kod: |
| <code cpp> |
| #include <iostream> |
| #include <vector> |
| |
| using std::cout; |
| using std::endl; |
| using std::vector; |
| |
| void PrintVector(const vector<int> &v) { |
| bool first = true; |
| for(auto n : v) { |
| if (!first) { |
| cout<< ", "; |
| } else { |
| first = false; |
| } |
| cout << n; |
| |
| } |
| cout<<endl; |
| } |
| |
| int main() |
| { |
| // Create a vector containing integers |
| vector<int> v = {7, 5, 16, 8}; |
| |
| cout << "initilized with 4 numbers"<<endl; |
| PrintVector(v); |
| |
| // Add two more integers to vector |
| v.emplace_back(25); |
| v.emplace_back(13); |
| cout << "after 2 more inserted"<<endl; |
| PrintVector(v); |
| |
| //copy of the value inside vector |
| for (auto n : v) { |
| ++n; |
| } |
| |
| cout << "BUT: after incrementation"<<endl; |
| PrintVector(v); |
| |
| //reference to the value inside vector, therefore one can change the value |
| for (auto &n : v) { |
| ++n; |
| } |
| cout << "and again... can you spot the difference?"<<endl; |
| PrintVector(v); |
| } |
| </code> |
| [[http://coliru.stacked-crooked.com/a/056089e192222291|Run code]] |
| |
| ==== Map ==== |
| |
| [[http://en.cppreference.com/w/cpp/container/map|Tablica asocjacyjna]], która pozwala zaadresować dowolny element innym typem, niekoniecznie tylko liczbą naturalną. |
| |
| <code cpp> |
| #include <iostream> |
| #include <map> |
| |
| using std::cout; |
| using std::endl; |
| using std::map; |
| |
| void PrintMap(const map<char,int> &v) { |
| bool first = true; |
| for(const auto &n : v) { |
| if (!first) { |
| cout<< ", "; |
| } else { |
| first = false; |
| } |
| cout << n.first << " -> " << n.second; |
| |
| } |
| cout<<endl; |
| } |
| |
| int main() |
| { |
| // Create a vector containing integers |
| map<char, int> v = {{'a',17}, {'c',-2}, {'g',67}, {'z',13}}; |
| |
| cout << "initilized with 4 numbers"<<endl; |
| PrintMap(v); |
| |
| // Add two more integers to vector |
| v.emplace('h',25); |
| v.emplace('$',13); |
| cout << "after 2 more inserted"<<endl; |
| PrintMap(v); |
| |
| //copy of the value inside vector |
| for (const auto &n : v) { |
| //Compilation error |
| //++n.second; |
| } |
| |
| cout << "BUT: after incrementation"<<endl; |
| PrintMap(v); |
| |
| //reference to the value inside vector, therefore one can change the value |
| for (auto &n : v) { |
| ++n.second; |
| } |
| cout << "and again... can you spot the difference?"<<endl; |
| PrintMap(v); |
| } |
| </code> |
| |
| [[http://coliru.stacked-crooked.com/a/4d32653f8fae33c3|Run code]] |
===== Operacje na plikach ===== | ===== Operacje na plikach ===== |
Operacje na plikach wykonywane są w C++ przy użyciu strumieni - analogicznie jak operacja czytania z klawiatury i wypisywania na ekran. | Operacje na plikach wykonywane są w C++ przy użyciu strumieni - analogicznie jak operacja czytania z klawiatury i wypisywania na ekran. |
====== Ćwiczenia ====== | ====== Ćwiczenia ====== |
- Zrefaktoryzować kod metod //factorial//, //reverse// i //is_palindrome// tak, żeby nawiązywały do konwencji, że nazwa funkcji jest pisana jako //NazwaFunkcjiCamelCase//, skorzystać z narzędzia do refaktoryzacji wbudowanego w CLion: najechać na metodę kursorem wybrać z menu Refactor->Rename... (SHIFT+F6). | - Zrefaktoryzować kod metod //factorial//, //reverse// i //is_palindrome// tak, żeby nawiązywały do konwencji, że nazwa funkcji jest pisana jako //NazwaFunkcjiCamelCase//, skorzystać z narzędzia do refaktoryzacji wbudowanego w CLion: najechać na metodę kursorem wybrać z menu Refactor->Rename... (SHIFT+F6). |
- [1 plus] W sekcji [[#wskazniki_i_alokacja_pamieci|Wskaźniki i alokacja pamięci]] zostało powiedziane, że **nie można** utworzyć tablicy wielowymiarowej prostym poleceniem //int * *tab = new int[10][10]//. Przeanalizuj rysunek poniżej i zastanów się dlaczego tak jest. Następnie napisz program który będzie pobierał od użytkownika wymiary tablicy i dynamicznie alokował pamięć dla niej. Napisz funkcję która będzie uzupełniała tablicę iloczynami wierszy i kolumn i osobną funkcję do wyświetlania tablicy. Czy można do tego wykorzystać funkcje napisane na poprzednich laboratoriach nie modyfikując ich? Pamiętaj o **poprawnym** zwolnieniu pamięci! {{.:pointers2pointers.png|Tablica wskaźników}}. Zadanie zostało podzielone na kroki: (step1,step2,...). Ukończenie pierwszego i drugiego kroku jest wymagane do zaliczenia ćwiczenia. | - [1 plus] W sekcji [[#wskazniki_i_alokacja_pamieci|Wskaźniki i alokacja pamięci]] zostało powiedziane, że **nie można** utworzyć tablicy wielowymiarowej prostym poleceniem //int * *tab = new int[10][10]//. Przeanalizuj rysunek poniżej i zastanów się dlaczego tak jest. Następnie napisz program który będzie pobierał od użytkownika wymiary tablicy i dynamicznie alokował pamięć dla niej. Napisz funkcję która będzie uzupełniała tablicę kolejnymi liczbami całkowitymi (tak jak na rysunku) i osobną funkcję do wyświetlania tablicy. Czy można do tego wykorzystać funkcje napisane na poprzednich laboratoriach nie modyfikując ich? Pamiętaj o **poprawnym** zwolnieniu pamięci! {{.:pointers2pointers.png|Tablica wskaźników}}. Zadanie zostało podzielone na kroki: (step1,step2,...). Ukończenie pierwszego i drugiego kroku jest wymagane do zaliczenia ćwiczenia. |
* Moduł: **array2d** | * Moduł: **array2d** |
* Pliki z implementacją: **Array2d.h/cpp** | * Pliki z implementacją: **Array2D.h/cpp** |
* Sygnatura metody: <code cpp>int **Array2D(int n_rows, int n_columns);</code> | * Sygnatura metody: <code cpp>int **Array2D(int n_rows, int n_columns); |
* Pliki nagłówkowe: <code cpp>#include <string></code> | void DeleteArray2D(int **array, int n_rows, int n_columns);</code> |
* Wskazówki: <code cpp>const char *characters = str.c_str(); //uzyskanie z obiektu string wskaźnika na poszczególne znaki | |
* W kroku nr 3 należy przeprowadzić refaktoryzację metody //Array2D// | * W kroku nr 3 należy przeprowadzić refaktoryzację metody //Array2D// |
size_t size = str.size(); //uzyskanie z obiektu string ilości znaków | |
//utworzenie nowego obiektu string na podstawie innego char*, char[], itp.. | |
return std::string(reversed_characters)</code> | |
* uruchomienie testów: ALT+SHIFT+F10 -> lab1_reverse_string_tests | * uruchomienie testów: ALT+SHIFT+F10 -> lab1_reverse_string_tests |
- **[2 punkty] Napisz program, który będzie implementować algorytm szyfrujący [[http://pl.wikipedia.org/wiki/Szachownica_Polibiusza|Polibiusza]]. Program powinien przyjmować trzy parametry: nazwę pliku wejściowego, nazwę pliku wyjściowego oraz 1 w przypadku gdy plik wejściowy ma zostać zaszyfrowany lub 0, gdy ma zostać odszyfrowany. Wynik szyfrowania/deszyfrowania powinien znaleźć się w pliku wyjściowym podanym jako parametr.\\ Przykład uruchomienia programu:**<code>./program plik-tekst.txt plik-szyfr.txt 1</code> | - **[2 punkty] Napisz program, który będzie implementować algorytm szyfrujący [[http://pl.wikipedia.org/wiki/Szachownica_Polibiusza|Polibiusza]]. Program powinien przyjmować trzy parametry: nazwę pliku wejściowego, nazwę pliku wyjściowego oraz 1 w przypadku gdy plik wejściowy ma zostać zaszyfrowany lub 0, gdy ma zostać odszyfrowany. Wynik szyfrowania/deszyfrowania powinien znaleźć się w pliku wyjściowym podanym jako parametr.\\ Przykład uruchomienia programu:**<code>./program plik-tekst.txt plik-szyfr.txt 1</code> |
- [2 plusy] Napisz program, który jest w stanie wyliczyć największy iloczyn n liczb z podanych na wejściu. **Uwaga** - Program ma mieć złożoność obliczeniową //O(n)// - innymi słowy, przegląda tablicę tylko raz - od początku do końca i zwraca wynik! Do zaliczenia zadania wystarczy, że program przejdzie pierwszy etap, tzn. n jest ustalone na 2 (maksymalny iloczyn dokładnie dwóch liczb) i wszystkie podane liczby są nieujemne. Kolejne etapy komplikują problem, są za dodatkowe plusy. | * Moduł: **polybius** |
| * Pliki z implementacją: **Polybius.h/cpp** |
| * Sygnatury metod: <code cpp>std::string PolybiusCrypt(std::string message); |
| std::string PolybiusDecrypt(std::string crypted);</code> |
| * Pliki nagłówkowe: <code cpp>#include <string></code> |
| - [2 plusy] Wykorzystując strukturę danych (struct) znaną jeszcze z języka C, należy zaimplementować listę jednokierunkową zdolną przechowywać liczby całkowite w swoich węzłach. **UWAGA**: jest to ćwiczenie tylko techniczne, w standardowej bibliotece istnieje [[http://en.cppreference.com/w/cpp/container/forward_list|forward_list]] zdolna przechowywać dowolny typ. |
| * Moduł: **simpleforwardlist** |
| * Pliki z implementacją: **SimpleForwardList.h/cpp** |
| * Sygnatury metod: <code cpp>ForwardList *CreateNode(int value); |
| void DestroyList(ForwardList *list);</code> |
| * Sygnatury metod z kroku drugiego i trzeciego: <code cpp>ForwardList *PushFront(ForwardList *list, int value); |
| void Append(ForwardList *list, ForwardList *tail);</code> |
| - [2 plusy + 2 punkty] Napisz program, który jest w stanie wyliczyć największy iloczyn k liczb z podanych n liczb na wejściu. **Uwaga** - Program ma mieć złożoność obliczeniową maksymalnie //O(n k)// - innymi słowy, przegląda tablicę tylko raz - od początku do końca i zwraca wynik (dla każdej napotkanej liczby może jednak wykonać k operacji) ! Do zaliczenia zadania wystarczy, że program przejdzie pierwszy etap, tzn. k jest ustalone na 2 (maksymalny iloczyn dokładnie dwóch liczb) i wszystkie podane liczby są nieujemne. Kolejne etapy komplikują problem, są za dodatkowe punkty. |
* Moduł: **greatestproduct** | * Moduł: **greatestproduct** |
* Pliki z implementacją: **GreatestProduct.h/cpp** | * Pliki z implementacją: **GreatestProduct.h/cpp** |
* Sygnatura metody: <code cpp>int GreatestProduct(const std::vector<int> &numbers, int n);</code> | * Sygnatura metody: <code cpp>int GreatestProduct(const std::vector<int> &numbers, int k);</code> |
* Pliki nagłówkowe: <code cpp>#include <vector></code> | * Pliki nagłówkowe: <code cpp>#include <vector></code> |
* Wskazówki: <code cpp>//po obiekcie vector można iterować w pętli for | * Wskazówki: <code cpp>//po obiekcie vector można iterować w pętli for |
</code> | </code> |
* W kroku nr 3 należy przeprowadzić refaktoryzację metody //Array2D// | * W kroku nr 3 należy przeprowadzić refaktoryzację metody //Array2D// |
- [3 plusy] [[http://projecteuler.net/index.php?section=problems&id=59|Łamanie hasła]] (lub wersja interaktywna z kilkoma test cases: [[https://www.hackerrank.com/contests/projecteuler/challenges/euler059]] | - **[3 punkty] [[http://projecteuler.net/index.php?section=problems&id=59|Łamanie hasła]] (lub wersja interaktywna z kilkoma test cases: [[https://www.hackerrank.com/contests/projecteuler/challenges/euler059]]. W przypadku testów zostanie podany kryptogram (zaszyfrowana wiadomość), w postaci tablicy znaków (std::vector<char>), długość klucza (w prostszej wersji można założyć, że będzie równa 3) i słownik zawierający około 100 najpopularniejszych wyrazów języka angielskiego [[http://www.talkenglish.com/vocabulary/top-2000-vocabulary.aspx|na podstawie]]** |
- **[3 punkty] Minimalne drzewo rozpinające:** | * Moduł: **xorcypherbreaker** |
| * Pliki z implementacją: **XorCypherBreaker.h/cpp** |
| * Sygnatura metody: <code cpp>std::string XorCypherBreaker(const std::vector<char> &cryptogram, |
| int key_length, |
| const std::vector<string> &dictionary);</code> |
| * Pliki nagłówkowe: <code cpp>#include <string> |
| #include <vector></code> |
| * Wskazówki: <code cpp>#include <algorithm> |
| using std::find; |
| using std::vector; |
| using std::string; |
| |
* Zadanie bazuje na problemie ze strony [[http://projecteuler.net/index.php?section=problems&id=107|Project Euler]], na której można sprawdzić poprawność rozwiązania wpisując w formularz wynik (albo można wrzucić kod na stronę [[https://www.hackerrank.com/contests/projecteuler/challenges/euler107|HackerRank]] i zrobić kilka testów) | vector<string> dictionary {"the","of"}; |
* Rozwiąż problem wyszukiwania [[http://pl.wikipedia.org/wiki/Minimalne_drzewo_rozpinaj%C4%85ce|minimalnego drzewa rozpinającego]] wykorzystując wybrany z poniższych algorytmów: | |
* [[http://pl.wikipedia.org/wiki/Algorytm_Kruskala|Algorytm Kruskala]] | |
* [[http://pl.wikipedia.org/wiki/Algorytm_Bor%C5%AFvki|Algorytm Borůvki]] | |
| |
* Poniższy nieskierowany graf ważony składa się z siedmiu wierzchołków i dwunastu krawędzi o całkowitej wadze równej 243. Wagą całkowitą grafu określana jest suma wag wszystkich krawędzi tego grafu. \\ {{.:graf.gif|Źródło: http://projecteuler.net}} | //THERE ARE BETTER WAYS TO LOOK FOR A WORD BUT IT WORKS |
* Graf z rysunku powyżej może zostać opisany za pomocą dwuwymiarowej tablicy: | if (find(dictionary.begin(),dictionary.end(),"of") != dictionary.end()) { |
| //FOUND! |
| } |
| |
^ ^ A ^B ^C ^D ^E ^F ^G^ | </code> |
^A| -| 16| 12| 21| -| -| -| | |
^B| 16| -| -| 17| 20| -| -| | |
^C| 12| -| -| 28| -| 31| -| | |
^D| 21| 17| 28| -| 18| 19| 23| | |
^E| -| 20| -| 18| -| -| 11| | |
^F| -| -| 31| 19| -| -| 27| | |
^G| -| -| -| 23| 11| 27| -| | |
| |
* Możliwe jest zoptymalizowanie grafu poprzez usunięcie niektórych krawędzi w taki sposób, aby wszystkie wierzchołki w danym grafie nadal pozowały połączone. Graf, który można uzyskać w ten sposób nazywany jest minimalnym drzewem rozpinającym: \\ {{.:spanning-tree.gif|Źródło: http://projecteuler.net}} | |
| |
* Wykorzystując {{.:network.txt|plik}} z tablicową reprezentacją pewnego grafu. Napisz program, który znajdzie minimalne drzewo rozpinające grafu, o najmniejszej możliwej wadze całkowitej. | |
| |
| |
* Modyfikacje w stosunku do oryginalnego zadania z http://projecteuler.net | |
- Załóż, że w pliku wejściowym pierwsza linijka to zawsze liczba określająca ilość wierzchołków grafu. | |
- Program powinien wyświetlać w konsoli oraz zapisywać do pliku minimalne drzewo rozpinające danego grafu w analogicznej konwencji jak w przypadku danych wejściowych | |
- Program powinien zwracać do systemu wartość oszczędności jaką osiągnięto (w zadaniu określanej jako //maximum saving//) | |