Wykorzystanie struktur w algorytmach

StrukturystrukturaStruktury to złożone typy danych umożliwiające przechowywanie informacji różnego typu. Znajdują wiele zastosowań w algorytmach, ponieważ pozwalają w prosty sposób opisać złożone obiekty.

Przeanalizujmy przykład użycia struktur. Załóżmy, że chcemy obliczyć i zapisać pola 100 trójkątów, mając podane długości ich podstaw oraz wysokości. W tym celu możemy oczywiście zainicjować trzy tablice, z których jedna będzie przechowywać wartości wysokości, druga podstawy, a trzecia pola. Takie rozwiązanie byłoby jednak nieczytelne i niepraktyczne. Lepszym podejściem będzie wykorzystanie struktur. Zapiszmy rozwiązanie tego problemu za pomocą pseudokodu.

Pierwszym krokiem jest stworzenie struktury, która składa się z trzech pólpolepól. Definiujemy je następująco:

struktura Trojkat {
	Podstawa: liczba zmiennoprzecinkowa
    Wysokosc: liczba zmiennoprzecinkowa
    Pole: liczba zmiennoprzecinkowa
}

Skoro trójkątów ma być 100, najlepszym rozwiązaniem jest stworzenie tablicy, która będzie przechowywać wszystkie struktury. Na potrzeby przykładu zakładamy, że w tablicy znajdują się elementy z wypełnionymi wartościami pól Podstawa oraz Wysokosc.

struktura Trojkat {
	Podstawa: liczba zmiennoprzecinkowa
    Wysokosc: liczba zmiennoprzecinkowa
    Pole: liczba zmiennoprzecinkowa
}

tablicaTrojkatow[100]: tablica elementów typu Trojkat

Potrzebujemy teraz pętli, która przeiteruje po tablicy i obliczy pole każdego trójkąta, a następnie zapisze wyniki w strukturze.

struktura Trojkat {
	Podstawa: liczba zmiennoprzecinkowa
    Wysokosc: liczba zmiennoprzecinkowa
    Pole: liczba zmiennoprzecinkowa
}

tablicaTrojkatow[100]: tablica elementów typu Trojkat

dla i = 0, 1, ..., długość(tablicaTrojkatow) - 1 wykonuj:
   

Następnie obliczymy pole każdego z trójkątów, których dane zapisane są w stworzonej wcześniej tablicy tablicaTrojkatow. Każdy element tej tablicy jest elementem typu Trojkat, a zatem jest strukturą przechowującą informacje o długości podstawy trójkąta i jego wysokości, a także mogącą przechowywać obliczone pole trójkąta.

Aby obliczyć pole trójkąta, potrzebujemy niezbędnych danych. Pobieramy je z elementu tablicy z danymi odpowiedniego trójkąta (przechowywanego w komórce tablicy wyznaczonej przez wartość iteratora pętli) za pomocą notacji z kropką. Składa się ona z identyfikatora obiektu i nazwy pola, w którym wartość jest przechowywana, oddzielonych kropką, np. Obiekt.Pole.

Obliczamy pole trójkąta, pobierając potrzebne wartości tablicaTrojkatow[i].Podstawa i tablicaTrojkatow[i].Wysokosc, mnożymy je przez siebie i dzielimy przez 2 zgodnie ze wzorem na pole trójkąta $(a\cdot h)÷2$. Wynik tego działania zapisujemy w polu tablicaTrojkatow[i].Pole.

struktura Trojkat {
	Podstawa: liczba zmiennoprzecinkowa
    Wysokosc: liczba zmiennoprzecinkowa
    Pole: liczba zmiennoprzecinkowa
}

tablicaTrojkatow[100]: tablica elementów typu Trojkat

dla i = 0, 1, ..., długość(tablicaTrojkatow) - 1 wykonuj:
  tablicaTrojkatow[i].Pole ← (tablicaTrojkatow[i].Podstawa * tablicaTrojkatow[i].Wysokosc) / 2

Porównajmy to rozwiązanie do wersji bez wykorzystania struktur. Użyjemy trzech tablic. Zainicjujmy je:

podstawy[100]
wysokosci[100]
pola[100]

Podobnie jak w przypadku przedstawionych wcześniej obliczeń z wykorzystaniem struktur, tak i tu zakładamy, że dane o długości podstaw i wysokości trójkątów są już zapisane w odpowiednich tablicach. Następnie potrzebna będzie pętla, która przeiteruje po tablicach. Zawierają one informacje o 100 trójkątach, dlatego instrukcja wewnętrzna pętli musi zostać wykonana 100 razy.

podstawy[100]
wysokosci[100]
pola[100]

dla i = 0, 1, 2, ..., długość(podstawy) - 1 wykonuj:
   

Każda wartość iteratora pętli wskazuje indeks komórek tablic zawierających dane opisujące jeden trójkąt. Chcąc obliczyć jego pole, pobieramy wartości z komórek tablic podstawy oraz wysokosci o tym samym indeksie. Następnie wartości te podstawiamy do wzoru na pole trójkąta, a wynik zapisujemy do tablicy pola do komórki o takim samym indeksie, jak komórki tablic, z których pobieraliśmy dane.

podstawy[100]
wysokosci[100]
pola[100]

dla i = 0, 1, 2, ..., długość(podstawy) - 1 wykonuj:
  pola[i] ← (podstawy[i] * wysokosci[i]) / 2

Pola wszystkich trójkątów są teraz dostępne w tablicy pola.

Redundancja

W omawianym przykładzie została zastosowana redundancja, mimo że w wielu e‑materiałach zjawisko to jest przedstawione jako niepożądane.

Zwróćmy uwagę, że nie ma potrzeby przechowywania w strukturze reprezentującej trójkąt informacji o jego polu, jeśli przechowujemy już wartości reprezentujące jego podstawę oraz wysokość. Jednak w wypadku bardziej złożonego programu, w którym np. chcielibyśmy wielokrotnie użyć pola trójkąta, musielibyśmy obliczyć jego wartość za każdym razem. To podejście jest w takiej sytuacji niepraktyczne – zwiększa złożoność obliczeniową programu.

Złym rozwiązaniem byłoby, gdybyśmy oprócz struktury reprezentującej trójkąt przechowywali również tablice reprezentujące podstawy, wysokości oraz pola trójkątów – taka redundancja jest niepożądana.

W wielu sytuacjach stosuje się redundancję – np. przechowując średnią arytmetyczną ocen, podczas gdy mamy wszystkie oceny ucznia. 

Słownik