Samouczek Data Structures (DS) zawiera podstawowe i zaawansowane koncepcje struktury danych. Nasz samouczek dotyczący struktury danych jest przeznaczony dla początkujących i profesjonalistów.

Struktura danych to sposób przechowywania i organizowania danych w celu umożliwienia ich efektywnego wykorzystania.

Nasz samouczek dotyczący struktury danych obejmuje wszystkie tematy dotyczące struktury danych, takie jak tablica, wskaźnik, struktura, lista połączona, stos, kolejka, wykres, wyszukiwanie, sortowanie, programy itp.

Co to jest struktura danych?

Nazwa struktury danych sama wskazuje na organizację danych w pamięci. Sposobów organizacji danych w pamięci jest wiele, gdyż widzieliśmy już jedną ze struktur danych, czyli tablicę w języku C. Tablica to zbiór elementów pamięci, w których dane zapisywane są sekwencyjnie, czyli jeden po drugim. Innymi słowy, możemy powiedzieć, że tablica przechowuje elementy w sposób ciągły. Ta organizacja danych odbywa się za pomocą tablicy struktur danych. Istnieją także inne sposoby porządkowania danych w pamięci. Przyjrzyjmy się różnym typom struktur danych.

Struktura danych nie jest jakimkolwiek językiem programowania, takim jak C, C++, Java itp. Jest to zestaw algorytmów, których możemy użyć w dowolnym języku programowania do strukturyzacji danych w pamięci.

Aby ustrukturyzować dane w pamięci, zaproponowano „n” algorytmów i wszystkie te algorytmy są znane jako abstrakcyjne typy danych. Te abstrakcyjne typy danych są zbiorem reguł.

Typy struktur danych

Istnieją dwa typy struktur danych:

np. kropka

• Pierwotna struktura danych
• Nieprymitywna struktura danych

Pierwotna struktura danych

Prymitywne struktury danych są prymitywnymi typami danych. Int, char, float, double i wskaźnik to prymitywne struktury danych, które mogą przechowywać pojedynczą wartość.

Nieprymitywna struktura danych

Nieprymitywne struktury danych dzielą się na dwa typy:

• Liniowa struktura danych
• Nieliniowa struktura danych

Liniowa struktura danych

Uporządkowanie danych w sposób sekwencyjny nazywa się liniową strukturą danych. Struktury danych używane w tym celu to tablice, lista połączona, stosy i kolejki. W tych strukturach danych jeden element jest połączony tylko z drugim elementem w formie liniowej.

Gdy jeden element jest połączony z liczbą „n” elementów, nazywa się to nieliniową strukturą danych. Najlepszym przykładem są drzewa i wykresy. W tym przypadku elementy rozmieszczone są losowo.

Powyższe struktury danych omówimy pokrótce w nadchodzących tematach. Teraz zobaczymy typowe operacje, które możemy wykonać na tych strukturach danych.

Struktury danych można również sklasyfikować jako:

Statyczna struktura danych:Jest to rodzaj struktury danych, w której rozmiar jest przydzielany w czasie kompilacji. Dlatego maksymalny rozmiar jest stały.Dynamiczna struktura danych:Jest to typ struktury danych, w której rozmiar jest przydzielany w czasie wykonywania. Dlatego maksymalny rozmiar jest elastyczny.

Główne operacje

Główne lub typowe operacje, które można wykonać na strukturach danych, to:

strony takie jak coomeet

Badawczy:Możemy wyszukać dowolny element w strukturze danych.Sortowanie:Elementy struktury danych możemy sortować rosnąco lub malejąco.Wprowadzenie:Nowy element możemy także wstawić do struktury danych.Aktualizacja:Możemy także zaktualizować element, czyli zastąpić go innym elementem.Usunięcie:Możemy również wykonać operację usuwania, aby usunąć element ze struktury danych.

Która struktura danych?

Struktura danych to sposób organizowania danych w celu umożliwienia ich efektywnego wykorzystania. Tutaj użyliśmy słowa efektywnie, zarówno jeśli chodzi o przestrzeń, jak i czas. Na przykład stos to ADT (abstrakcyjny typ danych), który do implementacji wykorzystuje tablice lub strukturę danych listy połączonej. Dlatego dochodzimy do wniosku, że potrzebujemy pewnej struktury danych, aby zaimplementować konkretny ADT.

ADT mówi Co ma zostać wykonane, a struktura danych o tym mówi Jak to jest do zrobienia. Innymi słowy, możemy powiedzieć, że ADT daje nam plan, podczas gdy struktura danych zapewnia część implementacyjną. Teraz pojawia się pytanie: w jaki sposób można dowiedzieć się, która struktura danych ma zostać użyta dla konkretnego ADT?.

Ponieważ w konkretnym ADT można zaimplementować różne struktury danych, ale różne implementacje są porównywane pod względem czasu i przestrzeni. Na przykład Stack ADT można zaimplementować zarówno za pomocą tablic, jak i połączonej listy. Załóżmy, że tablica zapewnia oszczędność czasu, podczas gdy połączona lista zapewnia oszczędność miejsca, więc zostanie wybrana ta, która najlepiej odpowiada wymaganiom bieżącego użytkownika.

Zalety struktur danych

Oto zalety struktury danych:

komentarz CSS

Efektywność:Jeśli wybór struktury danych do implementacji konkretnego ADT jest właściwy, czyni to program bardzo wydajnym pod względem czasu i przestrzeni.Możliwość ponownego użycia:Struktura danych zapewnia możliwość ponownego użycia, co oznacza, że ​​wiele programów klienckich może korzystać ze struktury danych.Abstrakcja:Struktura danych określona przez ADT zapewnia również poziom abstrakcji. Klient nie może zobaczyć wewnętrznego działania struktury danych, więc nie musi martwić się częścią implementacyjną. Klient widzi tylko interfejs.

Indeks struktur danych

Podstawy DS

• Wprowadzenie DS
• Analiza asymptotyczna DS
• Struktura DS

Układ DS

• Tablica 2D

Lista połączona DS

• Połączona lista
  • Wstawienie na początku
  • Wstawienie na końcu
  • Wstawienie po określonym węźle
  • Usuwanie na początku
  • Usuwanie na koniec
  • Usunięcie po określonym węźle
  • Przemierzanie
  • Badawczy
• Lista podwójnie połączona
  • Wstawienie na początku
  • Wstawienie na końcu
  • Wstawienie po określonym węźle
  • Usuwanie na początku
  • Usuwanie na koniec
  • Usunięcie węzła posiadającego podane dane
  • Przemierzanie
  • Badawczy
• Okrągła lista połączona
  • Wstawienie na początku
  • Wstawienie na końcu
  • Usuwanie na początku
  • Na koniec usunięcie
  • Przemierzanie
  • Badawczy
• Okrągła lista podwójna
  • Wstawienie na początku
  • Wstawienie na końcu
  • Usuwanie na początku
  • Na koniec usunięcie

Stos DS

• Implementacja tablicy
• Implementacja listy połączonej

Ogon DS

• Implementacja tablicy
• Implementacja listy połączonej
• Okrągła kolejka

Drzewo DS

• Drzewo
• Drzewo binarne
  • Zamów Travers w przedsprzedaży
  • Przejście w kolejności
  • Przejście po złożeniu zamówienia
• Drzewo wyszukiwania binarnego
  • Wyszukiwanie w BST
  • Wstawienie do BST
  • Usunięcie w BST
• Drzewo AVL
  • Wstawienie do drzewa AVL
    • Rotacja LL
    • Obrót LR
    • Obrót RL
    • Obrót RR
  • Usunięcie w drzewie AVL
• Drzewo B
• B+ Drzewo
• Czerwone Czarne Drzewo

Wykres DS

• Wykres DS
• Implementacja wykresu
• Algorytm BFS
• Algorytm DFS
• Drzewo rozpinające
  • Algorytm Prima
  • Algorytm Kruskala

Wyszukiwanie DS

• Wyszukiwanie liniowe
• Wyszukiwanie binarne

Sortowanie DS

• Sortowanie bąbelkowe
• Sortowanie wiadro
• Sortowanie grzebieniowe
• Sortowanie zliczające
• Sortowanie sterty
• Sortowanie przez wstawianie
• Sortowanie przez scalanie
• Szybkie sortowanie
• Sortuj Radix
• Sortowanie przez wybór
• Sortowanie powłoki
• Sortowanie bitoniczne
• Sortowanie koktajli
• Sortowanie cykliczne
• Tim Sort

Pytania do wywiadu

różnica między lisem a wilkiem

• Program do tworzenia i wyświetlania pojedynczo połączonej listy
• Program tworzący pojedynczo połączoną listę n węzłów i zliczający liczbę węzłów
• Program tworzący pojedynczo połączoną listę n węzłów i wyświetlający ją w odwrotnej kolejności
• Program usuwający nowy węzeł z początku pojedynczo połączonej listy
• Program usuwający nowy węzeł ze środka pojedynczo połączonej listy
• Program usuwający węzeł z końca pojedynczo połączonej listy
• Program sprawdzający, czy pojedynczo połączona lista jest palindromem
• Program znajdujący węzeł wartości maksymalnej i minimalnej na liście z pojedynczym łączem
• Program wstawiający nowy węzeł na środku pojedynczo połączonej listy
• Program wstawiający nowy węzeł na początku pojedynczo połączonej listy
• Program wstawiający nowy węzeł na końcu pojedynczo połączonej listy
• Program do usuwania zduplikowanych elementów z pojedynczo połączonej listy
• Program przeszukujący element na liście z pojedynczym łączem
• Program sortujący elementy listy pojedynczo połączonej
• Program do zamiany węzłów na pojedynczo połączonej liście bez zamiany danych
• Program zamieniający ostatni element listy pojedynczo połączonej z pierwszym

Programy z listami podwójnie połączonymi

• Program konwertujący dane drzewo binarne na listę podwójnie połączoną
• Program do tworzenia listy podwójnie połączonej z drzewa trójskładnikowego
• Program do utworzenia podwójnie połączonej listy N węzłów i zliczenia liczby węzłów
• Program do tworzenia podwójnie połączonej listy N węzłów i wyświetlania jej w odwrotnej kolejności
• Program do tworzenia i wyświetlania listy podwójnie połączonej
• Program do usuwania nowego węzła z początku listy podwójnie połączonej
• Program do usuwania nowego węzła z końca listy podwójnie połączonej
• Program do usuwania nowego węzła ze środka listy podwójnie połączonej
• Program do znajdowania węzła wartości maksymalnej i minimalnej na liście podwójnie połączonej
• Program wstawiający nowy węzeł na początku listy podwójnie połączonej
• Program wstawiający nowy węzeł na końcu listy podwójnie połączonej
• Program wstawiający nowy węzeł na środku listy podwójnie połączonej
• Program do usuwania zduplikowanych elementów z listy podwójnie połączonej
• Program do obracania listy podwójnie połączonej o N węzłów
• Program do wyszukiwania elementu na liście podwójnie połączonej
• Program do sortowania elementów listy podwójnie połączonej

Programy z cykliczną listą powiązaną

• Program do tworzenia kołowej połączonej listy N węzłów i policzenia liczby węzłów
• Program do tworzenia cyklicznej połączonej listy N węzłów i wyświetlania jej w odwrotnej kolejności
• Program do tworzenia i wyświetlania cyklicznej listy połączonej
• Program do usuwania nowego węzła z początku cyklicznej listy połączonej
• Program do usuwania nowego węzła z końca cyklicznej listy połączonej
• Program do usuwania nowego węzła ze środka okrągłej listy połączonej
• Program do znajdowania węzła wartości maksymalnej i minimalnej na liście połączonej kołowo
• Program wstawiający nowy węzeł na początku listy połączonej kołowo
• Program wstawiający nowy węzeł na końcu listy połączonej kołowo
• Program wstawiający nowy węzeł na środku okrągłej listy połączonej
• Program do usuwania zduplikowanych elementów z cyklicznej listy połączonej
• Program do wyszukiwania elementu na liście połączonej cyklicznie
• Program do sortowania elementów cyklicznej listy połączonej

Programy drzewne

• Program obliczający różnicę między sumą węzłów poziomu nieparzystego i parzystego drzewa binarnego
• Program do konstruowania drzewa wyszukiwania binarnego oraz wykonywania usuwania i przechodzenia w kolejności
• Program do konwersji drzewa binarnego na drzewo wyszukiwania binarnego
• Program określający, czy wszystkie liście znajdują się na tym samym poziomie
• Program sprawdzający, czy dwa drzewa są identyczne
• Program do znajdowania maksymalnej szerokości drzewa binarnego
• Program do znajdowania największego elementu w drzewie binarnym
• Program do znajdowania maksymalnej głębokości lub wysokości drzewa
• Program znajdujący węzły znajdujące się w największej odległości w drzewie binarnym
• Program do znajdowania najmniejszego elementu w drzewie binarnym
• Program obliczający sumę wszystkich węzłów drzewa binarnego
• Program do znajdowania całkowitej liczby możliwych drzew wyszukiwania binarnego za pomocą N kluczy
• Program do implementacji drzewa binarnego przy użyciu listy połączonej
• Program przeszukujący węzeł w drzewie binarnym

Warunek wstępny

Przed nauczeniem się struktury danych musisz posiadać podstawową wiedzę na temat C.

Publiczność

Nasz samouczek dotyczący struktury danych został zaprojektowany, aby pomóc początkującym i profesjonalistom.

Problem

Zapewniamy, że w tym samouczku dotyczącym struktury danych nie znajdziesz żadnego problemu. Jeśli jednak pojawi się jakiś błąd, prosimy o zamieszczenie go w formularzu kontaktowym.