Wybrane złożone struktury danych w językach C++ i Python – Informatyka

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

Uwaga: Zapoznaj się wcześniej z tematem C3 z podręcznika „Teraz bajty. Informatyka dla szkół ponadpodstawowych. Zakres podstawowy. Klasa II” lub z tematami 63 i 64 lub 75 i 76 z podręcznika „Informatyka 1-3. Podręcznik dla szkół ponadpodstawowych. Zakres podstawowy” oraz z tematem pt. „Przetwarzanie plików w językach C++ i Python” z Materiału edukacyjnego. Wykonaj zawarte tam ćwiczenia i zadania.

Zapisy podstawy programowej 2024 realizowane w temacie:

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

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:

projektuje i tworzy rozbudowane 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;

sprawnie posługuje się zintegrowanym środowiskiem programistycznym przy pisaniu, uruchamianiu i testowaniu programów;

Spis treści

Struktury w języku C++ i klasy danych w języku Python.
1. Typ strukturalny w języku C++.
2. Klasy danych w języku Python.
Typ słownikowy w języku Python.
Elementy bazy danych i ich odpowiedniki w językach programowania.

1. Struktury w języku C++ i klasy danych w języku Python

Na informatyce realizowanej w zakresie podstawowym poznaliśmy tablicowy typ danych w języku C++ i listy w języku Python. Tablice (listy) służą do przechowywania danych tego samego typu. Tymczasem bardzo często zdarza się, że na opis pojedynczego obiektu składają się dane różnych typów.

Poznaliśmy również typ plikowy, pozwalający na zapisywanie danych w pamięci masowej i ich odczytywanie (temat C3 z części II Materiału edukacyjnego).

W tym temacie omówimy typ strukturalny w języku C++ i klasy danych w języku Python, który umożliwiają zapisanie danych różnego typu w ramach jednej struktury (klasy), w sposób ułatwiający identyfikację tych danych.

Przykład 1. Opis obiektu składającego się z danych różnych typów

Dane opisujące Książkę:
      Autor (ciąg znaków),
      Tytuł (ciąg znaków),
      Wydawnictwo (ciąg znaków),
      Rok wydania (liczba całkowita),
      Cena (liczba rzeczywista).

1.1. Typ strukturalny w języku C++

Aby w programach można było przetwarzać dane różnego rodzaju, w języku C++ wprowadzono typ strukturalny.

Struktura w języku C++ to zbiór danych różnych typów.
Elementy struktury, tak jak w bazach danych, nazywamy polami. Każde pole posiada swoją unikatową nazwę i służy do przechowywania danych ustalonego typu.

Do tworzenia struktur w języku C++ służy słowo kluczowe struct, po którym w bloku (oznaczonym nawiasami klamrowymi) wymieniamy nazwy wszystkich pól rekordu wraz z ich typami. Jeżeli po słowie kluczowym struct podamy nazwę, to utworzymy w ten sposób nowy typ.

Przykład 2. Deklaracja typu rekordowego i strukturalnego TKsiazka i zmiennej Ksiazka typu TKsiazka

Ćwiczenie 1. Deklarujemy dane typu strukturalnego

Rozważ, jakie dane opisują ucznia szkoły. Zadeklaruj zawierający te dane typ strukturalny TUczen i zmienną Uczen typu TUczen.

Aby odwołać się do pojedynczego pola, podajemy nazwę zmiennej typu strukturalnego i nazwę pola struktury, oddzielone od siebie kropką.

Przykład 3. Wczytywanie danych do struktury, a następnie wyprowadzanie struktury w jednej linii (z formatowaniem)

Ćwiczenie 2. Analizujemy gotowy kod programu w języku C++

TC1_p3_c2.cpp Pobierz

Otwórz plik TC1_p3_c2.cpp. Uruchom program.
Przeanalizuj kod programu i objaśnij poszczególne wiersze kodu. Przetestuj program dla różnych danych.

W języku C++ elementami struktury mogą być także zmienne złożone, czyli tablice lub inne struktury.

Przykład 4. Struktura i tablica jako elementy struktury

Poza podstawowymi danymi o książce, dodatkowo w rekordzie pamiętana jest data ostatniego wypożyczenia danej książki z biblioteki oraz dane maksymalnie dziesięciu czytelników.

Odpowiednie odwołania do nowych pól w języku C++ będą miały postać:

Ksiazka.DataWypozyczenia.Rok
Ksiazka.DataWypozyczenia.Miesiac
Ksiazka.DataWypozyczenia.Dzien
Ksiazka.Czytelnicy[0]

Ćwiczenie 3. Uzupełniamy deklarację struktury

Uzupełnij deklarację struktury opisującego ucznia (z ćwiczenia 1.) o tablicę ocen.

Przykład 5. Struktura jako element tablicy czy pliku

Możliwa jest też sytuacja odwrotna, a więc struktura może być np. elementem tablicy czy pliku.

Rozważymy deklarację:

struct TKsiazkaBiblioteka[100];

Ćwiczenie 4. Odpowiadamy na pytanie dotyczące przykładu 5.

Odpowiedz na pytanie: Jaka będzie postać instrukcji wypisującej dane pierwszego czytelnika dziesiątej książki w bibliotece?

1.2. Klasy danych w języku Python

W języku Python najbliższym odpowiednikiem struktur stosowanych w języku C++ są klasy danych.

Klasa danych to specjalny rodzaj klas, których obiekty służą do przechowywania różnych, ale jednak powiązanych ze sobą danych.

W przykładzie 6. definiujemy klasę reprezentującą książkę.

Przykład 6. Stosowanie klasy danych w języku Python

W programie definiujemy klasę danych reprezentującą podstawowe informacje o książce, tworzymy instancję tej klasy i wyprowadzamy dane na ekran.

Wynikiem uruchomienia programu pokazanego w przykładzie 6. jest wypisane poniższego komunikatu na ekranie:

Ksiazka(autor='J. R. R. Tolkien', tytul='Hobbit', rok_wydania=2024, wydawnictwo='Wyimaginowane', cena=27.99)

Uwaga: Klasy danych są dostępne w języku Python od wersji 3.7 i automatycznie dodają odpowiednie metody na podstawie listy pól. We wcześniejszych wersjach należy samodzielnie zdefiniować zarówno pola jak i metody.

Instrukcja Ksiazka(...) tworzy obiekt naszej klasy, a argumenty podane w wywołaniu są zapisywane jako wartości pól zdefiniowanych w klasie w takiej samej kolejności. Zmienna książka przechowuje referencję do tego obiektu.

Odwołanie do pół obiektu odbywa się, podobnie jak w C++, poprzez kropkę i nazwę pola.

W ramach klasy zdefiniowaliśmy pola, a każdemu polu dodaliśmy również wskazówkę opisującą typ danych. Jest to jedynie wskazówka i możemy jej nie honorować np. jako cenę podając ciąg znaków:

ksiazka = Ksiazka('J. R. R. Tolkien', 'Hobbit', 2024, 'Wyimaginowane', '???')

Tworzenie obiektów może również wykorzystywać dane podane z klawiatury tak, jak pokazano w przykładzie 7.

Przykład 7. Tworzenie obiektu klasy danych na podstawie informacji wprowadzonych z klawiatury

Warto zauważyć, że wszystkie potrzebne informacje są podawane naraz przed wywołaniem Ksiazka(...).

Ćwiczenie 5. Analizujemy gotowy kod programu w języku Python

TC1_p7_c5_klasy.py Pobierz

Otwórz plik TC1_p7_c5_klasy.py. Uruchom program.
Przeanalizuj kod programu i objaśnij poszczególne wiersze kodu. Przetestuj program dla różnych danych.

2. Typ słownikowy w języku Python

Mając zdefiniowaną klasę reprezentującą książkę, możemy utworzyć namiastkę bazy danych jako listę obiektów typu Ksiazka. Aby wyszukiwać efektywnie w takiej liście możemy posłużyć się indeksem. Taki indeks w języku Python najłatwiej zaimplementować, używając słownika.

Na przykład indeks ułatwiający wyszukiwanie książek według autora jest przyporządkowaniem każdemu znanemu autorowi pozycji jego książek w bazie danych. Takie przyporządkowanie najłatwiej zrealizować jako słownik, gdzie kluczami są autorzy, a wartościami zbiory pozycji obiektów.

Przykład 8. Aktualizacja indeksu ułatwiającego wyszukiwanie po nazwie autora książki przy dodawaniu

Ćwiczenie 6. Stosujemy typ słownikowy w języku Python

TC1_p8_c6_slownik.py Pobierz

Otwórz plik TC1_p8_c6_slownik.py. Przeanalizuj dodawanie kolejnych wpisów o kolejnych książkach do biblioteki.

Uruchom program. Wytłumacz to, co wypisał na ekran.
Dodaj wprowadzanie danych o książkach z klawiatury
Co należałoby zrobić przy usuwaniu lub edycji wpisów?
Czy wyszukiwanie zadziała w przypadku pomyłek w wielkości liter lub literówek?
Czy słownik nadaje się do implementacji indeksu opartego na liczbach? Jak wyszukać wszystkie książki wydane np. po roku 2000?

3. Elementy bazy danych i ich odpowiedniki w językach programowania

Elementy bazy danych mają swoje odpowiedniki w językach programowania. Ich zestawienie przedstawiono w tabeli 1.

Element bazy danych	Implementacja w języku C++
pole	pole struktury
rekord	struktura
tabela	tablica struktur lub plik tekstowy albo binarny
indeks	tablica wartości całkowitych – indeksów pozycji tablicy

Tabela 1. Elementy baz danych i ich implementacja w języku C++

Przykład 9. Tworzenie bazy danych SOWy w język C++

Tworzenie bazy danych pokażemy na przykładzie tabeli Filmy dla bazy SOWy (temat B1 w części III Materiału edukacyjnego).

Ćwiczenie 7. Deklarujemy struktury danych do implementacji tabel bazy danych

Zadeklaruj w języku C++struktury danych niezbędne do implementacji pozostałych tabel systemu SOWy.

Zadania

Omów strukturalny typ danych w języku C++. Porównaj go z rekordem z tabeli bazy danych.
W jaki sposób deklaruje się dane typu strukturalnego w języku C++? Pokaż na przykładzie.
Czym są klasy danych w języku Python?
Do czego można wykorzystać typ słownikowy? Wyjaśnij na przykładzie.
Zadeklaruj strukturę w języku C++ lub klasę w języku Python, opisującą dane teleadresowe osoby. Rozważ, jakie informacje należy przechować w takiej strukturze lub klasie. Napisz program umożliwiający wprowadzanie takich danych (np. do tablicy struktur w języku C++ lub listy klas w języku Python) i ich wyszukiwanie według zadanego kryterium.