Dynamiczne struktury danych w językach C++ i Python

Wszystkie treści na stronie ir.migra.pl są chronione prawami autorskimi. Więcej informacji znajdziesz tutaj.

Zapisy podstawy programowej 2024 realizowane w temacie:

I. Rozumienie, analizowanie i rozwiązywanie problemów.
Zakres rozszerzony. Uczeń spełnia wymagania określone dla zakresu podstawowego, a ponadto:

4. do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych;

II. Programowanie i rozwiązywanie problemów z wykorzystaniem komputera i innych urządzeń cyfrowych.
Zakres rozszerzony. Uczeń spełnia wymagania określone dla zakresu podstawowego, a ponadto:

1. projektuje i tworzy programy w procesie rozwiązywania problemów, wykorzystuje w programach dobrane do algorytmów struktury danych, w tym struktury dynamiczne i korzysta z dostępnych bibliotek dla tych struktur;
2. sprawnie posługuje się zintegrowanym środowiskiem programistycznym przy pisaniu, uruchamianiu i testowaniu programów;

I + II. Zakres rozszerzony. Uczeń spełnia wymagania określone dla zakresu podstawowego, a ponadto:

3. objaśnia, a także porównuje podstawowe metody i techniki algorytmiczne oraz struktury danych, wykorzystując przy tym przykłady problemów i algorytmów, w szczególności:
   g) struktury dynamiczne: stos, kolejka, lista (do realizacji algorytmu ONP),

Spis treści

1. Wskaźniki
2. Tworzenie zmiennych dynamicznych
   1. Tworzenie zmiennych dynamicznych w języku C++
   2. Zmienne dynamiczne a język Python
3. Tablica dynamiczna w języku C++
4. Lista jednokierunkowa
   1. Lista jednokierunkowa w języku C++
   2. Lista jednokierunkowa w języku Python
5. Stos i zastosowanie do realizacji ONP
   1. Operacje wykonywane na stosie w języku C++
   2. Operacje wykonywane na stosie w języku Python
6. Kolejka
   1. Tworzenie kolejki w języku C++
   2. Tworzenie kolejki w języku Python

1. Wskaźniki

Deklaracja zmiennych typu wskaźnikowego w języku C++ ma postać:

opis_typu *nazwa_zmiennej;

gdzie opis_typu oznacza typ wbudowany lub zdefiniowany przez programistę.

W języku Python nie występują zmienne typu wskaźnikowego. 

Przykład 1. Deklarowanie zmiennych typu wskaźnikowego w języku C++

int *adres1;
double *adres2;
char *adres3;

Zmienna adres1 jest wskaźnikiem wartości typu całkowitego, adres2 – wskaźnikiem wartości typu rzeczywistego, a adres3 – wartości typu znakowego. Wskaźniki te będą mogły wskazywać odpowiednio na zmienne (proste lub elementy tablic) wymienionych typów.

Uwaga: W języku C++ na zmiennych typu wskaźnikowego można wykonywać niektóre operacje arytmetyczne.

Przykład 2. Stosowanie zmiennej wskaźnikowej w języku C++

W programie zadeklarujemy zmienną wskaźnikową adres1 do przechowywania adresów zmiennych typu int.

Po utworzeniu tej zmiennej przypiszemy jej wartość, czyli adres istniejącej zmiennej liczba1 tego samego typu.

Uwagi:

• Instrukcja przypisania: adres1 = &liczba1; oznacza, że wskaźnik adres1 wskazuje na adres, pod którym znajduje się zmienna liczba1.
• Jeśli zmienna wskaźnikowa adres1 zawiera adres zmiennej liczba1, to *adres1 jest odwołaniem do zmiennej liczba1.

Rys. 1. Schemat pokazujący, czym jest wskaźnik

Ćwiczenie 1. Stosujemy zmienną wskaźnikową w języku C++

Otwórz plik TC9_p2_c1.cpp. Skompiluj program i uruchom. Wyjaśnij, dlaczego na ekranie monitora wyświetla się liczba 53.

Uwaga: W języku C++ można wyświetlić na ekranie wartość zmiennej wskaźnikowej, zapisując polecenie: cout << adres1;

2. Tworzenie zmiennych dynamicznych

2.1. Tworzenie zmiennych dynamicznych w języku C++

Dla każdej zdefiniowanej zmiennej rezerwowany jest fragment pamięci o określonym adresie i wielkości odpowiadającej danemu typowi danych. Zmienne te przechowują wartości określonego typu i istnieją przez cały czas wykonywania tej części programu, w której zostały zadeklarowane.

Zmienne, dla których pamięć jest przydzielana i zwalniana na żądanie, nazywamy zmiennymi dynamicznymi. Do takich zmiennych odwołujemy się za pomocą wskaźników.

Wiemy, że zmienna w programie komputerowym to nazwana część pamięci komputera. Pamięć ta przydzielana jest w czasie kompilacji lub automatycznie (bez konieczności stosowania dodatkowych instrukcji) podczas działania programu. W przykładzie 3. omówiliśmy wskaźniki, które przechowywały adres innej zmiennej (tej, na którą wskazywały).

Zmienne dynamiczne tworzone są w trakcie działania programu. Korzystając z operatora new, rezerwujemy w pamięci operacyjnej obszar niezbędny do przechowania wartości określonego typu i adres tego obszaru przypisujemy zmiennej wskaźnikowej.

Jeśli przydzielony fragment pamięci jest już niepotrzebny, zwalniamy go, używając operatora delete. Operatora delete możemy użyć tylko do pamięci przydzielonej za pomocą operatora new.

Nie wolno zwalniać ponownie raz zwolnionego obszaru pamięci, ponieważ może to prowadzić do bardzo różnych, często trudnych do zdiagnozowania, błędów wykonania programu.

nazwa_wskaźnika = new opis_typu;

Uwaga: Zmienną nazwa_wskaźnika należy zadeklarować przed jej pierwszym użyciem. Można również połączyć deklarację z użyciem operatora new:

opis_typu *nazwa_wskaźnika = new opis_typu;

Przykład 3. Tworzenie zmiennej dynamicznej w języku C++

W programie deklarujemy zmienną wskaźnikową dynZm do przechowywania adresów zmiennych typu int.

Następnie dynamicznie rezerwujemy obszar pamięci dla podanego typu – operatorem new. Zmiennej nadajemy wartość i wypisujemy ją na ekranie. Ostatecznie zwalniamy zarezerwowany obszar pamięci, używając operatora delete.

Ćwiczenie 2. Tworzymy zmienną dynamiczną

Otwórz plik TC9_p3_c2.cpp. Skompiluj go i uruchom. Objaśnij działanie programu.

2.2. Zmienne dynamiczne a język Python

W języku Python nie mówimy o zmiennych dynamicznych. Jest tak dlatego, że w istocie zmienna w języku Python jest nazwą przypisaną do obiektu przechowywanego w pamięci. Pamięć jest rezerwowana w momencie utworzenia tego obiektu. Jest to bardzo podobne do zmiennych typu wskaźnikowego w C++ i danych, na które wskazują, więc w tym rozumieniu wszystkie zmienne w języku Python są dynamiczne.

Zarządzanie pamięcią, a w szczególności i usuwanie z niej obiektów, gdy nie są już potrzebne, jest realizowane automatycznie przez mechanizm “zbierania śmieci” (ang. garbage collection). Jest on oparty między innymi na zliczaniu aktywnych referencji do danego obiektu, czyli nazw, które są w danej chwili aktywne. Gdy dla obiektu nie ma już aktywnych nazw (a więc nie ma zmiennych albo pól innych obiektów, które na niego wskazują) zostanie on usunięty.

3. Tablica dynamiczna w języku C++

Tablice, które do tej pory deklarowaliśmy, miały z góry zadeklarowaną liczbę elementów. Były to tablice statyczne. Przy rozwiązywaniu pewnych problemów algorytmicznych może się jednak okazać, że wielkość tablicy można określić dopiero podczas działania programu. Na etapie pisania kodu nie wiemy na przykład, ile liczb użytkownik wprowadzi.

W takiej sytuacji możemy skorzystać z tablic dynamicznych lub innej dynamicznej struktury danych.

nazwa_wskaźnika = new opis_typu[rozmiar];
delete [] nazwa_wskaźnika;

Uwaga: Zmienną nazwa_skaźnika należy zadeklarować przed jej pierwszym użyciem. Można również połączyć deklarację z użyciem operatora new:

opis_typu *nazwa_wskaźnika = new opis_typu;

Na przykład: double *elementy = new double [liczbaEl];

Elementom tablicy dynamicznej przypisujemy wartości w podobny sposób jak w przypadku tablicy statycznej, podobnie je też odczytujemy, z tym że nazwą tablicy dynamicznej jest nazwa wskaźnika, który na nią wskazuje (w języku C++ pojęcia tablicy i wskaźnika są często równoważne).

nazwa_wskaźnika[nr_elementu] = wartość; // przypisanie wartości
zmienna = nazwa_wskaźnika[nr_elementu]; // odczyt wartości

Przykład 4. Tworzenie tablicy dynamicznej w języku C++

Program zapisany w pliku TC9_p4_c3.cpp umożliwia wprowadzenie z klawiatury dowolnej liczby danych całkowitych i wczytanie ich do tablicy dynamicznej, a następnie wyszukanie spośród elementów tablicy liczb parzystych i wyświetlenie ich na ekranie monitora.

W programie została utworzona tablica dynamiczna liczby:

int *liczby = new int [liczbaSpr];

Program najpierw prosi użytkownika o podanie liczby danych, wśród których wyszuka liczby parzyste. Dla podanej liczby danych program rezerwuje dynamiczną tablicę o określonym rozmiarze. Następnie w pętli pobiera kolejne liczby i wypełnia nimi tablicę dynamiczną.

Kolejnym etapem jest przejrzenie podanych liczb i wyświetlenie na ekranie tylko tych, które są parzyste. Na samym końcu, gdy tablica nie jest już potrzebna, zwalniamy zajmowaną przez nią pamięć, stosując polecenie: delete [] liczby;.

Ćwiczenie 3. Analizujemy i modyfikujemy program tworzący tablice dynamiczne w języku C++

1. Otwórz plik TC9_p4_c3.cpp. Przenalizuj kod programu, korzystając z przykładu 4. Uruchom program i wykonaj go dla wybranych danych.
2. Zmodyfikuj program tak, aby wypisywał liczby podzielne przez 7. Dodaj także zabezpieczenie uniemożliwiające podanie ujemnej wielkości tablicy.

4. Lista jednokierunkowa

W przypadku listy (w odróżnieniu od tablicy dynamicznej) nie musimy określać, z ilu elementów ma się ona składać.

Do listy będziemy dołączali elementy wtedy, gdy będą potrzebne. Utworzenie listy jest możliwe dzięki zmiennym wskaźnikowym – kolejne elementy listy są ze sobą połączone za pomocą wskaźników.

W liście możemy przechowywać na przykład ciągi liczb.

Lista może być jednokierunkowa lub dwukierunkowa.

• W liście jednokierunkowej poruszamy się tylko w jednym kierunku: od początku do końca, mając dostęp za pomocą wskaźnika do elementu następnego.
• W liście dwukierunkowej poruszamy się w obydwu kierunkach, mając dostęp zarówno do elementu leżącego za danym elementem, jak i przed nim.

Omówimy listę jednokierunkową.

Rys. 2. Schemat pokazujący listę jednokierunkową

4.1. Lista jednokierunkowa w języku C++

W języku C++ elementy listy, zwane węzłami, są strukturami o dwóch polach: w jednym przechowywana jest wartość elementu listy, a w drugim – wskaźnik do następnego węzła. Każdy z węzłów przechowuje zatem wskaźnik do następnego elementu. Lista rozpoczyna się od elementu zwanego głową (HEAD), w którym przechowywany jest wskaźnik elementu początkowego listy. Lista kończy się wskaźnikiem pustym NULL (specjalna wartość określona w języku C++).

Przykład 5. Tworzenie listy jednokierunkowej w języku C++

Zmodyfikujemy program omówiony w przykładzie 4. Tym razem nie pytamy użytkownika, ile liczb chciałby sprawdzić, lecz dynamicznie dodajemy kolejne elementy do listy, dopóki użytkownik nie naciśnie klawisza Enter (bez wprowadzania liczby).

(Uwaga: Aby osiągnąć podobny efekt, używając tablicy dynamicznej zamiast listy, musielibyśmy przy podawaniu kolejnej liczby rezerwować nową, większą tablicę i przepisywać do niej zawartość istniejącej tablicy.)

W kodzie programu element_listy jest strukturą zawierającą wartość liczbową, którą chcemy przechować oraz wskaźnik na kolejny element listy. Tworzymy także zmienną globalną glowa, która przechowuje adres pierwszego elementu na liście.

Funkcja dodaj_do_listy() dodaje liczbę przekazaną jako parametr na koniec listy. Funkcja ta tworzy nowy element typu element_listy, ustawia dla niego wartość przechowywanej liczby oraz zeruje wskaźnik na następny element.

Należy zwrócić uwagę, że w przypadku gdy dodajemy węzeł do pustej listy, wystarczy zmiennej glowa przypisać adres nowo utworzonego węzła. Natomiast, gdy dodajemy węzeł do listy niepustej, tworzymy pomocniczy wskaźnik, który przesuwamy na ostatni element na liście i wskazujemy jego polem nastepny na nowo utworzony element.

Do przeglądania listy zawsze używamy pomocniczego wskaźnika, ponieważ gdybyśmy zmienili wartość zmiennej glowa, utracilibyśmy dostęp do wszystkich początkowych elementów na liście.

Analogicznej metody, ze wskaźnikiem do znajdowania końca listy, używamy do przeglądania elementów na liście podczas sprawdzania, czy liczby są parzyste.

Ćwiczenie 4. Analizujemy i modyfikujemy program tworzący listę jednokierunkową w języku C++

1. Otwórz plik TC9_p5_c4.cpp, w którym zapisano program z przykładu 5.
2. Zmodyfikuj program tak, aby funkcja dodaj_do_listy dodawała nowy element nie na koniec listy, a na jej początek.

4.2. Lista jednokierunkowa w języku Python

Listę jednokierunkową w języku Python możemy zaimplementować podobnie jak pokazano w punkcie 4.1. dla języka C++.

Przykład 6. Implementacja listy jednokierunkowej w języku Python.

Ćwiczenie 5. Analizujemy i modyfikujemy program tworzący listę jednokierunkową w języku Python

1. Otwórz plik TC9_p6_c5.py, w którym zapisano program z przykładu 6.
2. Zmodyfikuj program tak, aby funkcja dodaj_do_listy() dodawała nowy element nie na koniec listy, a na jej początek.
3. Dodaj funkcję zwracającą długość listy

W praktyce nie ma potrzeby implementować takiej listy jednokierunkowej, bo klasa list, będąca wbudowanym typem języka Python, pozwala na wygodniejsze realizowanie tej samej funkcjonalności.

Przykład 7. Analogiczne użycie wbudowanego typu list

Ćwiczenie 6. Analizujemy i modyfikujemy program tworzący listę jednokierunkową w języku Python

1. Otwórz plik TC9_p7_c6.py, w którym zapisano program z przykładu 7.
2. Zmień sposób dodawania do listy tak, aby element był dodawany na początek (użyj metody insert).
3. Dodaj sprawdzanie długości listy

5. Stos i zastosowanie do realizacji ONP

W informatyce często korzystamy ze struktury danych zwanej stosem (ang. stack). Na stosie możemy wykonać dwie operacje: położyć element na wierzchołku stosu lub zdjąć element leżący na wierzchołku stosu. Operacje te noszą w informatyce angielskie nazwy, odpowiednio Push i Pop. Stos jest wykorzystywany np. przy wywoływaniu procedur i funkcji.

Przy wywoływaniu funkcji adres aktualnie wykonywanej instrukcji jest kładziony na wierzchu stosu, po czym następuje skok do procedury lub funkcji. Po zakończeniu procedury lub funkcji ze stosu jest zdejmowany adres i procesor wykonuje skok pod ten adres, kontynuując w ten sposób wykonywanie głównego programu.

Rys. 3. Schemat pokazujący stos

5.1. Operacje wykonywane na stosie w języku C++

Przykład 8. Implementacja stosu z wykorzystaniem tablicy w języku C++

Uwagi: SP z ang. Stack Pointer – wskaźnik stosu.

W języku C++ zapis ++SP (tzw. preinkrementacja) oznacza zwiększenie wartości zmiennej SP o 1 przed odczytaniem jej wartości, a zapis SP-- (tzw. postdekrementacja) – zmniejszenie wartości zmiennej SP o 1 po odczytaniu jej wartości.

Ćwiczenie 7. Stosujemy stos w programie komputerowym w języku C++

1. Otwórz plik TC9_p8_c7. cpp.
2. Funkcja Pop() nie posiada zabezpieczeń przed przepełnieniem stosu lub próbą zdejmowania elementu z pustego stosu. Zdefiniuj funkcję logiczną stack_empty(), sprawdzającą, czy stos jest pusty.
3. Zmodyfikuj funkcje push() i pop(), tak by zabezpieczyć się przed przepełnieniem lub opróżnieniem stosu.
   Wskazówka: Funkcja logiczna powinna zwracać wartość typu logicznego bool w jezyku C++.).

5.2. Operacje wykonywane na stosie w języku Python

Przykład 9. Implementacja stosu w języku Python

W języku Python najłatwiej jest zaimplementować stos, korzystając z wbudowanego typu list. Zawiera on metody append, która odpowiada operacji push, oraz pop.

Ćwiczenie 8. Stosujemy stos w programie komputerowym w języku Python

1. Otwórz plik TC9_p9_c8.py.
2. W przypadku wywołania metody pop dla pustego stosu wykonanie zakończy się błędem. W jaki sposób sprawdzić, czy stos jest pusty?
3. Załóżmy, że chcemy ograniczyć wielkość stosu. Co należałoby w tym celu zrobić?

6. Kolejka

Kolejka (ang. queue) jest strukturą danych zbliżoną do stosu. O ile jednak w przypadku stosu dane dodajemy do wierzchołka stosu i stamtąd odczytujemy, o tyle w przypadku kolejki dane odczytujemy z początku kolejki a dodajemy – na końcu kolejki. Przypomina to kolejkę do kasy w sklepie: obsługiwany jest klient na początku kolejki, kolejni kupujący ustawiają się na końcu kolejki.

6.1. Tworzenie kolejki w języku C++

Do implementacji kolejki w języku C++, podobnie jak do implementacji stosu, wykorzystać można tablicę. Oprócz tablicy będziemy potrzebowali zmiennej przechowującej aktualną długość kolejki. Musimy również stworzyć funkcję przesuwającą kolejkę (poprzez przemieszczenie elementów tablicy).

Przykład 10. Implementacja kolejki z wykorzystaniem tablicy w języku C++

Ćwiczenie 9. Analizujemy program tworzący kolejkę w języku C++

1. Otwórz plik TC9_p10_c9.cpp.
2. Przenalizuj kod programu, korzystając z przykładu 10. Uruchom program i objaśnij otrzymane wyniki.

6.2. Tworzenie kolejki w języku Python

Kolejkę w języku Python najłatwiej zaimplementować w sposób bardzo podobny do stosu. Jedyną różnicą jest to, że wstawiamy element do kolejki, używając metody insert (podając 0 jako argument) zamiast metody append.

Przykład 11. Tworzenie kolejki w języku Python

kolejka = []

kolejka.insert(0, "a")
kolejka.insert(0, "b")
kolejka.insert(0, "c")
kolejka.insert(0, "d")

print(kolejka.pop())
print(kolejka.pop())
print(kolejka.pop())
print(kolejka.pop())

Ćwiczenie 10. Analizujemy programy

1. Otwórz pliki TC9_p10_c9.cpp i TC9_p11_c10.py.
2. Przeanalizuj rozwiązania i je porównaj.
3. Z czego wynika mniejsza złożoność rozwiązania w języku Python? Na przykład, dlaczego nie trzeba przesuwać wszystkich elementów kolejki?
4. Gdzie w implementacji w języku Python jest potocznie rozumiany „początek”, a gdzie „koniec” kolejki?
5. Jak w języku Python znaleźć aktualną długość kolejki i wypisać jej zawartość?

Zadania

1. Wyjaśnij, jakie zmienne zostały zadeklarowane w następujących instrukcjach:

double *nazwa;
double zmienna;

2. Otwórz plik TC9_p5_c4.cpp lub TC9_p6_c5.py. Zmodyfikuj program tak, aby funkcja dodaj_do_listy dodawała nowy element nie na koniec listy, lecz po n-tym elemencie listy.

Dla zainteresowanych
3. Korzystając z dodatkowej literatury, zapoznaj się z informacjami na temat listy dwukierunkowej. Przygotuj przykład zastosowania takiej listy.