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 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 <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];
}
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 <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;
}
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:
Czytanie z pliku
Przykład wczytywania pliku wyraz po wyrazie:
#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;
}
Przykład wczytywania pliku linia po linii:
#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;
}
Zapisywanie do pliku
Przykład dopisywania do pliku:
#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;
}
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
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!
[2 punkty] Napisz program, który będzie implementować algorytm szyfrujący 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 punkty] Minimalne drzewo rozpinające:
Zadanie bazuje na problemie ze strony
Project Euler, na której można sprawdzić poprawność rozwiązania wpisując w formularz wynik (albo można wrzucić kod na stronę
HackerRank i zrobić kilka testów)
-
| 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:
Wykorzystując
plik z tablicową reprezentacją pewnego grafu. Napisz program, który znajdzie minimalne drzewo rozpinające grafu, o najmniejszej możliwej wadze całkowitej.
-
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