OK, więc to jest DSA, prawda?

Absolutnie, czemu nie. Bądźmy szczerzy, DSA to coś, czego każdy trochę się boi studiować. DSA to jedna z takich rzeczy na studiach lub w jakiejkolwiek pracy technicznej, że bez tego przedmiotu tak naprawdę nic nie można zrobić. Każda rozmowa kwalifikacyjna, niezależnie od portfolio, o które się ubiegasz, wymaga dogłębnego poznania koncepcji DSA.

Jak sama nazwa wskazuje, chodzi o dane. Struktura danych pod każdym względem stanowi koncepcję całego tematu, a algorytmy to techniki, które opracowaliśmy w celu uproszczenia struktur danych.

Tak więc, teraz też jestem studentką drugiego roku i chcę zdobyć dobrze płatną pracę w branży technologicznej i na pewno boję się tego przedmiotu, a szczerze mówiąc, nie jest on nawet zbyt interesujący. Ten artykuł jest także dla mnie motywacją, aby wstać, pokochać ten temat (bo to tylko dane, a ja uwielbiam bawić się danymi) i spróbować go jak najlepiej wykorzystać. Artykuł będzie wglądem w moją wiedzę teoretyczną na temat DSA i zobaczymy, dokąd zaprowadzi nas ten temat w najbliższej przyszłości, gdy będę przygotowywał się do staży.

Dobrze zaprojektowana struktura danych i wydajny algorytm mogą zamienić obliczeniowy koszmar w płynne i eleganckie rozwiązanie.

Struktury danych i algorytmy można zaimplementować w dowolnym wybranym języku, Pythonie, Javie, C, C++ itp.

Czym właściwie jest struktura danych?

Krótka odpowiedź brzmi: „struktura danych” to specyficzny sposób organizowania danych w systemie w celu uzyskania dostępu i wykorzystania.

Długa odpowiedź brzmi: struktura danych to połączenie organizacji danych, zarządzania, wyszukiwania i przechowywania, zebrane w jeden format, który umożliwia skuteczny dostęp i modyfikację. Gromadzi wartości danych, wspólne relacje oraz mające zastosowanie funkcje lub operacje.

Oto przykład z prawdziwego świata. Jeśli pójdziesz do biblioteki i będziesz chciał znaleźć książkę o historii wojskowości XX wieku, przejdź do działu Historia. Stamtąd znajdziesz wyznaczony obszar przeznaczony na historię wojskowości, a następnie przejrzysz księgi, posortowane w porządku chronologicznym, aż znajdziesz XX wiek. Teraz potraktuj książki jako swoje dane, a metodę sortowania książek stosowaną przez bibliotekę jako strukturę danych i gotowe!

Struktury danych są niezbędne do zarządzania ogromnymi ilościami generowanych danych i są kluczowym czynnikiem zwiększającym wydajność algorytmów.

Typy struktury danych

Liniowa struktura danych

Nieliniowa struktura danych

Liniowe struktury danych

W liniowych strukturach danych elementy są ułożone sekwencyjnie, jeden po drugim. Ponieważ elementy są ułożone w określonej kolejności, są łatwe w realizacji.

1. Tablica

W tablicy elementy w pamięci są ułożone w pamięci ciągłej. Wszystkie elementy tablicy są tego samego typu. Rodzaj elementów, które można przechowywać w postaci tablic, zależy od języka programowania.

2. Stos

W strukturze danych stosu elementy przechowywane są zgodnie z zasadą LIFO. Oznacza to, że ostatni element przechowywany na stosie zostanie usunięty jako pierwszy.

Działa to podobnie jak stos talerzy, z którego ostatni talerz znajdujący się na stosie zostanie usunięty jako pierwszy.

3. Kolejka

W odróżnieniu od stosu, struktura danych kolejki działa w oparciu o zasadę FIFO, gdzie jako pierwszy zostanie usunięty pierwszy element umieszczony w kolejce.

Działa to na zasadzie kolejki osób przy kasie biletowej, gdzie pierwsza osoba w kolejce otrzyma bilet jako pierwsza.

4. Połączona lista

W strukturze danych listy połączonej elementy danych są połączone szeregiem węzłów. Każdy węzeł zawiera elementy danych i adres do następnego węzła.

Nieliniowe struktury danych

W przeciwieństwie do liniowych struktur danych, elementy w nieliniowych strukturach danych nie występują w żadnej kolejności. Zamiast tego są one ułożone w sposób hierarchiczny, w którym jeden element będzie połączony z jednym lub większą liczbą elementów.

Nieliniowe struktury danych są dalej podzielone na struktury danych oparte na wykresach i drzewach.

1. Wykres

W strukturze danych grafowych każdy węzeł nazywany jest wierzchołkiem i każdy wierzchołek jest połączony z innymi wierzchołkami poprzez krawędzie.

2. Struktura danych drzew

Podobnie jak graf, drzewo jest również zbiorem wierzchołków i krawędzi. Jednak w drzewiastej strukturze danych pomiędzy dwoma wierzchołkami może znajdować się tylko jedna krawędź.

Liniowe i nieliniowe struktury danych

Rodzaje wykresów

  • Wykres zerowy
  • Trywialny wykres
  • Wykres nieskierowany
  • Kierowany wykres
  • Połączony wykres
  • Odłączony wykres
  • Zwykły wykres
  • Kompletny wykres
  • Wykres cyklu
  • Wykres cykliczny
  • Wykres acykliczny
  • Skończony wykres
  • Nieskończony wykres
  • Wykres dwudzielny
  • Wykres planarny
  • Prosty wykres
  • Wielu wykres
  • Pseudowykres
  • Wykres Eulera
  • Wykres Hamiltona

Przechodzenie grafów w strukturze danych

Przechodzenie przez graf polega na odwiedzaniu lub aktualizowaniu każdego wierzchołka na wykresie. Kolejność, w jakiej odwiedzają wierzchołki, klasyfikuje przejścia. Istnieją dwa sposoby implementacji przechodzenia przez graf:

  1. Wyszukiwanie wszerz (BFS):jest to operacja przechodzenia, która przesuwa wykres w poziomie. Przechodzi przez wszystkie węzły na jednym poziomie, zanim przejdzie do następnego poziomu. Zaczyna się od korzenia wykresu i przechodzi przez wszystkie węzły na jednym poziomie głębokości, zanim przejdzie do następnego poziomu.
  2. Wyszukiwanie w głąb (DFS): to kolejna operacja przechodzenia, która przesuwa wykres w pionie. Rozpoczyna się od węzła głównego grafu i bada każdą gałąź w miarę możliwości przed cofnięciem się.

Następujące typy struktury danych w postaci drzewa:

  • Drzewo ogólne:

  • Drzewo wyszukiwania binarnego
  • Drzewo AVL
  • Czerwono-czarne drzewo
  • Odtwórz drzewo
  • Treap
  • Drzewo B
  • Minimalne drzewo rozpinające

Teraz poznajmy różne algorytmy.

Ale najpierw, czym są algorytmy w dziedzinie informatyki?

Algorytm to procedura używana do rozwiązywania problemu lub wykonywania obliczeń. Algorytmy działają jak dokładna lista instrukcji, które krok po kroku wykonują określone działania w procedurach opartych na sprzęcie lub oprogramowaniu.

Algorytmy są szeroko stosowane we wszystkich obszarach IT. W matematyce i informatyce algorytm zwykle odnosi się do małej procedury, która rozwiązuje powtarzający się problem. Algorytmy są również wykorzystywane jako specyfikacje przetwarzania danych i odgrywają główną rolę w zautomatyzowanych systemach.

Algorytm można wykorzystać do sortowania zestawów liczb lub do bardziej skomplikowanych zadań, takich jak polecanie treści użytkowników w mediach społecznościowych. Algorytmy zazwyczaj zaczynają się od początkowych danych wejściowych i instrukcji opisujących konkretne obliczenia. Po wykonaniu obliczeń proces generuje wynik.

Typy algorytmów:

Badawczy:

1) Wyszukiwanie binarne

2) Wyszukiwanie liniowe

3) Pierwsze wyszukiwanie w głębi

4) Wyszukiwanie wszerz

Sortowanie:

1) Sortowanie przez wstawianie

2) Sortowanie sterty

3) Sortowanie przez wybór

4) Sortowanie przez scalanie

5) Szybkie sortowanie

6) Liczenie sortowania

7) Sortowanie wiadro

8) Sortowanie bąbelkowe

9) Sortowanie radiacyjne

10) Sortowanie skorupowe

Wykresy:

1) Algorytm Kruskala

2) Algorytm Dijkstry

3) Algorytm Bellmana Forda

4) Algorytm Floyda Warshalla

5) Algorytm sortowania topologicznego

6) Algorytm wypełniania powodzią

7) Algorytm Prima

Tablice:

1) Algorytm Kadane’a

2) Algorytm wykrywania cykli Floyda

Drzewo:

1) Drzewo AA

2) Drzewo indeksowane binarnie lub drzewo Fenwicka

5) Drzewo sterty

Inni:

1) Algorytm kompresji kodu Huffmana

2) Algorytm Euklidesa

3) Algorytm mapy mieszającej

4) Programowanie dynamiczne

5) Chciwe algorytmy

6) Algorytmy dziel i zwyciężaj

Wniosek

W porządku, więc po pierwsze, w tym artykule nie przedstawiłem opisu każdej struktury danych i algorytmu. Można by napisać mnóstwo i tysiące innych rzeczy na temat DSA. Każdy algorytm ma swój własny zestaw matematyki i programowania, część analityczną, z wieloma notacjami, z pewnym zestawem bardzo powszechnych przykładów, z których jednym jest problem plecaka. Temat ten nazywa się DAA, czyli algorytmem projektowania i analizą, który integruje pewne podstawowe tematy, takie jak złożoność czasowa i przestrzenna, ale to temat na inny dzień. Załączam jednak listę dobrych pytań z punktu pośrednictwa pracy. Możesz to sprawdzić tutaj.



DSA autorstwa Shradha Didi i Amana Bhaiyi
DSA w 2,5 miesiąca DSA autorstwa Shradha Didi i Amana Bhaiyi Spotkaj się z nami na Youtube (Apna College) Jak rozwiązać ten arkusz? Idealny…docs.google.com



Celem artykułu było krótkie i szybkie zrozumienie, na czym polega DSA na poziomie podstawowym. W ten sposób rozpocznijmy naszą podróż ku sukcesowi w DSA, bądźmy dumni i zaufajmy mi, temu, który potrafi rozwiązywać złożone problemy DSA, to znaczy, to prawdziwy flex w świecie technologii.

Do następnego razu pracuj dalej, ucz się!!!