======Dynamiczne zarządzanie pamięcią i operacje na plikach======

//Writing in C or C%%++%% is like running a chain saw with all the safety guards removed//

<WRAP center round info 60%>
Do ukończenia tego laboratorium wymagana jest znajomość wskaźników i referencji z C. Jeżeli ktoś nie czuje się w tym temacie na siłach, w laboratorium [[.:wskazniki|Wskaźniki i referencje]] przygotowane zostało krótkie przypomnienie najważniejszych informacji.
</WRAP>


===== Dynamiczne zarządzanie pamięcią =====
Często zdarza się, że nie jesteśmy w stanie z góry przewidzieć ile pamięci będzie potrzebował nasz program do poprawnego działania. Na przykład w prostym kalkulatorze macierzowym nie można z góry ustalić wymiarów tablicy przechowującej macierz ani z góry ustalić ile takich tablic-macierzy będzie występować w równaniu!

Jedynym rozwiązaniem jest tworzenie nowych macierzy o ustalonych wymiarach podczas działania programu.

====Wskaźniki i alokacja pamięci====
Wraz z dynamiczną alokacją pamięci idą w parze wskaźniki. Pamięć zawsze alokowana jest pod jakimś adresem. A zmienne przechowujące adres i pozwalające się dostać do danych w niej przechowywanych, to właśnie wskaźniki.
===Operator new ===
Operator **new** jest ekwiwalentem znanej z C funkcji //malloc// ale dużo potężniejszym. Wynikiem zwracanym przez operator **new** jest wskaźnik do zaalokowanej pamięci

Przykład dynamicznego tworzenia zmiennych:<code cpp>#include <iostream>
using namespace std;

int main(void){
   char* ptr = new char;    //Stworzy zmienną typu char
   int* tab = new int[10];  //Stworzy tablicę typu int o rozmiarze 10

   // NIEPOPRAWNIE!!!
   int** tab2d = new int[10][10];
}</code>
===Operator delete ===
Operator **delete** działa podobnie jak funkcja //free// znana z C. Pamięć w momencie kiedy nie jest już wykorzystywana przez program powinna być zwolniona.
Przykład dynamicznego tworzenia i usuwania zmiennych:<code cpp>#include <iostream>
using namespace std;

int main(void){
   char* ptr = new char;    //Stworzy zmienną typu char
   int* tab = new int[10];  //Stworzy tablicę typu int o rozmiarze 10

   // Tutaj znajdują się operacje na zmiennych

   delete ptr;
   delete [] tab;

   // NIEPOPRAWNIE!!
   // Jeśli tab2d jest poprawnie zaalokowaną tablica dwuwymiarową
   // nie można zwolnić pamięci w następujący sposób
   delete [][] tab2d;
}</code>

===== Operacje na plikach =====
Operacje na plikach wykonywane są w C++ przy użyciu strumieni - analogicznie jak operacja czytania z klawiatury i wypisywania na ekran.

Należy pamiętać o tym, że każdy plik, który został otwarty, powinien zostać również zamknięty, kiedy korzystanie z niego nie jest już potrzebne.
====Biblioteka fstream====
Obiekty strumieni służące do odczytu i zapisu do pliku znajdują się w pliku nagłówkowym //<fstream>//. Biblioteka ta zawiera dwa obiekty strumieni analogiczne do obiektów //cin// i //cout//: 
  * //ifstream// - służący do odczytu z pliku (//input-file-stream//)
  * //ofstream// - służący do zapisu do pliku (//output-file-stream//).
====Czytanie z pliku====
Przykład wczytywania pliku wyraz po wyrazie:<code cpp>
#include <iostream>
#include <fstream>
using namespace std;

int main(void){
  ifstream myfile("file.txt");
  char word[64];

  if(!myfile)
    cout << "Nie można otworzyć pliku!" << endl;

  while(myfile >> word)
    cout << word;
  
  myfile.close();
  return 0;
}
</code>
Przykład wczytywania pliku linia po linii:<code cpp>
#include <iostream>
#include <fstream>
using namespace std;

int main(void){
  ifstream myfile("file.txt");
  char line[256];

  if(!myfile)
    cout << "Nie można otworzyć pliku!" << endl;

  while(!myfile.eof()){
    myfile.getline(line,256);
    cout << line;
  }
  
  myfile.close();
  return 0;
}
</code>

====Zapisywanie do pliku====
Przykład **dopisywania** do pliku:<code cpp>#include <iostream>
#include <fstream>
using namespace std;

int main () {

  // Aby zrozumieć zapis: ios_base::in | ios_base::app
  // Zobacz kolejny podrozdział
  ofstream myfile ("file.txt", ios_base::in | ios_base::app);

  if(!myfile)
    cout << "Nie można otworzyć pliku!" << endl;

  myfile << "Tekst zapisany w pliku" << endl;

  myfile.close();

  return 0;
}
</code>


====Otwieranie pliku w różnych trybach====
Plik można otworzyć w 6 różnych trybach; kombinacje trybów też są możliwe.

^Wartość flagi^Znaczenie^
|ios_base::app|(append) Ustawia wskaźnik pozycji strumienia na samym końcu strumienia. Służy do dopisywania do pliku.|
|ios_base::ate|(at end) Ustawia wskaźnik pozycji strumienia na samym końcu pliku.|
|ios_base::binary|(binary) Traktuje strumień jako strumień binarny a nie tekstowy|
|ios_base::in|(input) Umożliwia zapis do pliku|
|ios_base::out|(output) Umożliwia odczyt z liku|
|ios_base::trunc|(truncate) Jeśli otwierany pli posiadał jakąś zawartość, jest ona pomijana i wskaźnik pozycji w strumieniu jest ustawiany na początku pliku.|

Otwieranie strumienia //ifstream// z opcją //ios_base::out// mija się z celem. Do strumieni, które mają służyć zarówno zapisowi jak i odczytowi, stosuje się ogólną postać strumienia o nazwie //fstream//.
<code cpp>
  fstream file("file.txt", ios_base::in | ios_base::out | ios_base:app);
</code>
====== Ć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ę 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}}
  - **[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 w pierwszej kolejności wczyta od użytkownika rozmiar tablicy, stworzy dynamicznie tablicę o podanych wymiarach, następnie uzupełni ją losowymi liczbami całkowitymi i znajdzie te liczby w tablicy, których iloczyn da największą liczbę. **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!  
  - [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] Minimalne drzewo rozpinające:**

  * 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)
  * 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}}
  * Graf z rysunku powyżej może zostać opisany za pomocą dwuwymiarowej tablicy:

^ ^   	A	^B	^C	^D	^E	^F	^G^
^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//)

====== Do przygotowania na kolejne zajęcia======
Zapoznać się z materiałem o [[http://home.agh.edu.pl/~gjn/dydaktyka/UGLX/node10.html | Makefile]].