Powrót do wiedza

Struktury danych i algorytmy w programowaniu

Algorytmy i struktury danych są jedną z podstawowych rzeczy, jakie powinien poznać programista. Należą one do elementarnej wiedzy, dzięki której powstają konkretne operacje i zadania, jakie ma wykonać maszyna.   Algorytmy i struktury danych to obszerny dział, od którego z...

Algorytmy i struktury danych są jedną z podstawowych rzeczy, jakie powinien poznać programista. Należą one do elementarnej wiedzy, dzięki której powstają konkretne operacje i zadania, jakie ma wykonać maszyna.

 

Algorytmy i struktury danych to obszerny dział, od którego z pewnością warto zacząć zacząć naukę programowania, który pozwala poznać zasady funkcjonowania programów.

Algorytmy i struktury danych

Czym są struktury danych? Struktury danych to zaawansowane pojemniki na dane, które pomagają gromadzić i układać je w odpowiedni sposób mimo ich różnorodności. Struktury danych także dopasowują się rozmiarem do wielkości danych, są obecne w wielu algorytmach i pozwalają na rozwiązywanie wielu kluczowych zagadnień obliczeniowych. Na strukturach danych operują algorytmy.

Rodzaje struktur danych

Struktury danych dzielimy na:

  • Rekord - jest najprostszą strukturą danych, najczęściej wykorzystuje się ją do prezentowania informacji tylko o jednym obiekcie. W trakcie działania algorytmu rekord nie zmienia ani rozmiaru, ani struktury. Jest to statyczna struktura danych.
  • Tablica - w odróżnieniu od rekordu, tablica pozwala na przechowywanie większej ilości informacji. Jest to uporządkowany zbiór danych tego samego typu. Wyróżniamy tablice statyczne, w których rozmiar ustalony jest z góry oraz tablice dynamiczne, które mogą się zmieniać w trakcie działania algorytmu. 
  • Lista - podobnie jak tablica, lista wykorzystywana jest do przechowywania większej ilości danych. Przypomina ona łańcuszek, który z łatwością obrazuje poszczególne dane. Znając położenie jej początku, z łatwością możemy dodawać do niej kolejne elementy. Wyróżnia się dwa rodzaje listy:
    • Lista wskaźnikowa (ang. LinkedList) - każdy element listy musi mieć dodaną nową wartość, jaką jest wskaźnik.
    • Lista tablicowa (ang. ArrayList) - implementacja listy tablicowej opiera się na wprowadzeniu tablicy. Wyposażona jest ona w dodatkowe funkcje, np. usuwanie lub dodawanie poszczególnych elementów. Wyróżniamy trzy rodzaje listy tablicowej:
      • lista jednokierunkowa - każdy element zawiera referencję do następnego lub poprzedniego komponentu na liście,
      • lista dwukierunkowa - każdy element zawiera referencję zarówno do kolejnego, jak i poprzedniego komponentu w liście. Umożliwia to poruszanie się po liście w górę i w dół,
      • lista cykliczna - pierwszy element powiązany jest z ostatnim, a ostatni z pierwszym. W ten sposób powstaje zamknięty cykl, po którym można się poruszać wokoło. Lista cykliczna nie ma wskaźnika początkowego ani końcowego.
  • Stos - znany także jako kolejka LIFO (ang. Last In, First Out), co oznacza ostatni na wejściu, pierwszy na wyjściu. Wykorzystywany podczas przeprowadzania operacji od najnowszych danych. Podstawowymi operacji w stosie są push, czyli dodanie obiektu na wierzch stosu oraz pop odpowiadające ściągnięciu jednego elementu i zwróceniu jego zawartości.
  • Kolejka - znana także jako FIFO (ang. First In, First Out), co oznacza pierwszy na wejściu, pierwszy na wyjściu. Przetwarzanie danych odbywa się od elementów, które pojawiły się jako pierwsze. Ten rodzaj struktury danych działa jak typowa kolejka np. w sklepie, gdzie każdy dodany element obsługiwany jest na końcu.
  • Drzewo - struktura danych odpowiadająca drzewu matematycznemu. Ukazuje ona hierarchię danych w sposób naturalny i do tego celu najczęściej jest wykorzystywana. Stosowanie drzew ponadto ułatwia oraz przyspiesza wyszukiwanie konkretnych danych i przeprowadzanie na nich operacji, np. wyliczanie wszystkich elementów drzewa, dodawanie nowych w konkretnym miejscu czy ich usuwanie.

Czym są algorytmy?

Co to jest algorytm? Definicyjnie algorytm jest skończonym ciągiem znaków jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. W prostych słowach algorytm to przepis na rozwiązanie jakiegoś problemu lub osiągnięcie jakiegoś celu. Algorytmy są więc podstawą programowania. Maszyna, aby wykonać działanie, potrzebuje jasno określonej instrukcji, zapisanej krok po kroku.

Zobacz również:Czym jest algorytmika?

Analiza algorytmów

Czym zajmuje się analiza algorytmów? Przede wszystkim porównywaniem ich pod względem nakładów obliczeniowych niezbędnych do uzyskania rozwiązania. Dokonując porównania pomiędzy dwoma programami, należy zbadać:

  • liczbę wykonywanych operacji,
  • czas ich wykonania,
  • obciążenie dla podzespołów,
  • wydajność.
Udostępnij