======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//
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.
===== 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:#include
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];
}
===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:#include
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;
}
===== 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 ////. 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:
#include
#include
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;
}
Przykład wczytywania pliku linia po linii:
#include
#include
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;
}
====Zapisywanie do pliku====
Przykład **dopisywania** do pliku:#include
#include
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;
}
====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//.
fstream file("file.txt", ios_base::in | ios_base::out | ios_base:app);
====== Ć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:**./program plik-tekst.txt plik-szyfr.txt 1
- [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]]
- **[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.
* 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]].