Jednym z rodzajów struktur danych, które są bezpośrednim ucieleśnieniem bytów matematycznych w informatyce, są zbiory. Operacje z nimi często leżą u podstaw różnych algorytmów. Różne języki programowania mają swoje własne sposoby opisywania zbiorów.
Niezbędny
- - środowisko rozwoju;
- - tłumacz z wybranego języka programowania.
Instrukcje
Krok 1
Opisz zestaw za pomocą języka programowania, jeśli jest dostępny. Na przykład w języku Pascal istnieje konstrukcja zestawu, która pozwala zadeklarować odpowiednie typy. To prawda, że objętość takich zestawów nie powinna przekraczać 256 elementów. Przykład deklaracji typu zestawu może wyglądać tak:
rodzaj
AZLitery = zbiór 'A'.. 'Z';
AllLetters = zestaw znaków;
Zmienne i stałe typów będących zestawami są deklarowane w zwykły sposób. W takim przypadku do inicjalizacji można użyć literałów zestawu. Na przykład:
stały
ZestawLiter1: Litery AZ = ['A', 'B', 'C'];
Krok 2
Wykorzystaj możliwości standardowych bibliotek lub modułów do opisania zestawów. Tak więc biblioteka szablonów C++, która powinna być dostarczona wraz z kompilatorem, zawiera szablon dla klasy kontenera zestawu, który implementuje funkcjonalność zestawów:
szablon <
klucz klasy, cechy klasowe = mniej, klasa Alokator = alokator
zestaw klas
Jak widać z listingu, argumentami szablonu zestawu są: typ danych elementów zestawu, typ obiektu funkcjonalnego określający kolejność elementów w zestawie oraz typ alokatora pamięci. W tym przypadku wymagany jest tylko pierwszy argument (podobnie jak dwa pozostałe, domyślnie używany jest standardowy predykat binarny less i standardowy alokator).
Krok 3
Zastosuj klasy lub szablony klas używane w tworzeniu frameworków, które implementują funkcjonalność pracy z zestawami, jeśli takie istnieją. Przykładem takiego narzędzia jest klasa szablonów QSet modułu QtCore biblioteki Qt. Jego możliwości są podobne do opisanego w poprzednim kroku kontenera zestawu STL.
Krok 4
Opisz zestaw własnymi środkami implementacyjnymi. Używaj flag bitowych, przechowywanych w tablicach o stałej długości, dla zestawów elementów prostych typów i małych rozmiarów. Zaimplementuj ustawioną klasę kontenera dla złożonych typów danych. Jako podstawę można przyjąć funkcjonalność tablic asocjacyjnych lub haszujących tablice asocjacyjne. To z kolei może być zbudowane na podstawie samobilansujących się drzew binarnych wyszukiwania (np. czerwono-czarne drzewa).
