Menu

Wprowadzenie do struktur danych w C ++

introduction data structures c

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Samouczek wprowadzający dotyczący struktur danych w języku C ++.

„Strukturę danych można zdefiniować jako zorganizowany zbiór danych, który pomaga programowi w efektywnym i szybkim dostępie do danych, tak aby cały program mógł funkcjonować w efektywny sposób. „

Wiemy, że w świecie programowania dane są centrum i wszystko kręci się wokół danych. Musimy wykonywać wszystkie operacje na danych, w tym przechowywanie, wyszukiwanie, sortowanie, porządkowanie i uzyskiwanie dostępu do danych w sposób wydajny i tylko wtedy nasz program może odnieść sukces.

=> Zobacz tutaj, aby poznać pełną listę samouczków języka C ++.

Wprowadzenie do struktur danych w C ++ (1)

Czego się nauczysz:

Przegląd

Musimy znaleźć najbardziej efektywny sposób przechowywania danych, który pomoże nam tworzyć dynamiczne rozwiązania. Struktura danych pomaga nam w budowaniu takich rozwiązań.

Organizując dane lub układając je w struktury, musimy upewnić się, że aranżacja reprezentuje niemal rzeczywisty obiekt. Po drugie, takie rozwiązanie powinno być na tyle proste, aby każdy miał do niego łatwy dostęp i mógł go przetworzyć w razie potrzeby.

W tej serii szczegółowo poznamy podstawową i zaawansowaną strukturę danych. Dowiemy się również szczegółowo o różnych technikach wyszukiwania i sortowania, które można wykonać na strukturach danych.

Po zapoznaniu się z tą serią samouczków czytelnik powinien dobrze zapoznać się z każdą strukturą danych i jej programowaniem.

Przyjrzyjmy się niektórym terminom, których używamy podczas pracy ze strukturami danych:

Na przykład,weź konkretnego ucznia. Uczeń może mieć następujące szczegóły przedstawione w formie graficznej.

Przykład - struktura danych

  • Dane: To podstawowa wartość. Na powyższym rysunku numer rolki ucznia może być danymi.
  • Pozycja grupowa: Jest to pozycja danych, która ma więcej niż jedną pozycję podrzędną. Na powyższym rysunku Student_name zawiera imię i nazwisko.
  • Rekord: Jest to zbiór danych. W powyższym przykładzie elementy danych, takie jak numer listy uczniów, imię i nazwisko, klasa, wiek, stopień itp., Tworzą razem rekord.
  • Jednostka: To klasa rekordów. Na powyższym schemacie uczeń jest bytem.
  • Atrybut lub pole: Właściwości jednostki nazywane są atrybutami, a każde pole reprezentuje atrybut.
  • Plik: Plik to zbiór rekordów. W powyższym przykładzie jednostka studencka może mieć tysiące rekordów. Zatem plik będzie zawierał wszystkie te rekordy.

Czytelnik powinien być świadomy wszystkich tych terminów, ponieważ używamy ich od czasu do czasu podczas korzystania z różnych struktur danych.

Struktury danych są głównym elementem składowym programu i jako programiści powinniśmy uważać, której struktury danych użyć. Dokładna struktura danych, która ma być zastosowana, jest najtrudniejszą decyzją, jeśli chodzi o programowanie.

Omówmy potrzebę struktury danych w programowaniu.

Potrzeba struktury danych w programowaniu

Wraz ze wzrostem ilości danych aplikacje stają się coraz bardziej złożone, stąd programiście trudniej jest zarządzać tymi danymi, a także oprogramowaniem.

Zwykle w dowolnym momencie aplikacja może napotkać następujące przeszkody:

# 1) Wyszukiwanie dużych ilości danych: Przy przetwarzaniu i przechowywaniu dużej ilości danych w dowolnym momencie nasz program może być zmuszony do przeszukania określonych danych. Jeśli dane są zbyt duże i nieprawidłowo zorganizowane, uzyskanie wymaganych danych zajmie dużo czasu.

Kiedy używamy struktur danych do przechowywania i organizowania danych, odzyskiwanie danych staje się szybsze i łatwiejsze.

# 2) Szybkość przetwarzania: Dezorganizacja danych może spowodować niską prędkość przetwarzania, ponieważ dużo czasu zostanie zmarnowane na pobieranie i uzyskiwanie dostępu do danych.

Jeśli podczas przechowywania odpowiednio uporządkujemy dane w strukturze danych, nie będziemy tracić czasu na takie czynności, jak ich pobieranie, organizowanie za każdym razem. Zamiast tego możemy skoncentrować się na przetwarzaniu danych w celu uzyskania pożądanego wyniku.

# 3) Wiele jednoczesnych żądań: W dzisiejszych czasach wiele aplikacji wymaga jednoczesnego żądania danych. Te żądania powinny być wydajnie przetwarzane, aby aplikacje działały płynnie.

Jeśli nasze dane są przechowywane losowo, nie będziemy w stanie przetwarzać wszystkich jednoczesnych żądań jednocześnie. Dlatego rozsądną decyzją jest uporządkowanie danych w odpowiedniej strukturze, aby zminimalizować czas przetwarzania równoległych żądań.

Klasyfikacja struktury danych

Struktury danych używane w C ++ można sklasyfikować w następujący sposób.

Klasyfikacja struktur danych

Struktura danych to sposób organizacji danych. Możemy więc klasyfikować struktury danych, jak pokazano, na prymitywne lub standardowe struktury danych oraz inne niż pierwotne lub zdefiniowane przez użytkownika struktury danych.

Widzieliśmy wszystkie typy danych obsługiwane w C ++. Ponieważ jest to również sposób organizowania danych, mówimy, że jest to standardowa struktura danych.

Pozostałe struktury danych nie są prymitywne i użytkownik musi je zdefiniować przed użyciem ich w programie. Te zdefiniowane przez użytkownika struktury danych są dalej klasyfikowane jako liniowe i nieliniowe struktury danych.

Liniowa struktura danych

Liniowe struktury danych mają wszystkie swoje elementy ułożone w sposób liniowy lub sekwencyjny. Każdy element w liniowej strukturze danych ma poprzednika (poprzedni element) i następcę (następny element)

Liniowe struktury danych są dalej podzielone na statyczne i dynamiczne struktury danych. Statyczne struktury danych mają zwykle stały rozmiar i po zadeklarowaniu ich rozmiaru w czasie kompilacji nie można go zmienić. Dynamiczne struktury danych mogą dynamicznie zmieniać swój rozmiar i dostosowywać się.

Najpopularniejszym przykładem liniowej statycznej struktury danych jest tablica.

Szyk

Tablica to sekwencyjna kolekcja elementów tego samego typu. Dostęp do każdego elementu tablicy można uzyskać za pomocą jego pozycji w tablicy zwanej indeksem lub indeksem tablicy. Nazwa tablicy wskazuje na pierwszy element tablicy.

szyk

Powyżej pokazana jest tablica „a” n elementów. Elementy są ponumerowane od 0 do n-1. Rozmiar tablicy (w tym przypadku n) jest również nazywany wymiarem tablicy. Jak pokazano na powyższym rysunku, nazwa tablicy wskazuje na pierwszy element tablicy.

Tablica jest najprostszą strukturą danych i jest wydajna, ponieważ do elementów można uzyskać dostęp bezpośrednio za pomocą indeksów dolnych. Jeśli chcemy uzyskać dostęp do trzeciego elementu tablicy, musimy po prostu powiedzieć a (2).

Ale dodanie lub usunięcie elementów tablicy jest trudne. Dlatego używamy tablic tylko w prostych aplikacjach lub w aplikacjach, w których dodawanie / usuwanie elementów nie jest wymagane.

Popularne liniowe dynamiczne struktury danych to połączone listy, stosy i kolejki.

Połączona lista

Lista połączona to zbiór węzłów. Każdy węzeł zawiera element danych i wskaźnik do następnego węzła. Węzły można dodawać i usuwać dynamicznie. Lista połączona może być listą połączoną pojedynczo, w której każdy węzeł ma wskaźnik tylko do następnego elementu. Dla ostatniego elementu następny wskaźnik jest ustawiony na null.

Na liście podwójnie połączonych każdy węzeł ma dwa wskaźniki, jeden do poprzedniego węzła, a drugi do następnego węzła. Dla pierwszego węzła poprzedni wskaźnik ma wartość null, a dla ostatniego węzła następny wskaźnik ma wartość null.

Połączona lista

Jak pokazano na powyższym rysunku, początek listy nazywany jest głową, a koniec listy połączonej nazywany jest końcem. Jak pokazano powyżej, każdy węzeł ma wskaźnik do następnego elementu. Możemy łatwo dodawać lub usuwać elementy, zmieniając wskaźnik na następny węzeł.

Stos

Stos to liniowa struktura danych, w której elementy można dodawać lub usuwać tylko z jednego końca znanego jako „Góra” stosu. W ten sposób stos wykazuje dostęp do pamięci typu LIFO (Last In, First Out).

Stos

Jak pokazano powyżej, elementy w stosie są zawsze dodawane na jednym końcu, a także usuwane z tego samego końca. Nazywa się to „górą” stosu. Po dodaniu elementu jest on wypychany w dół stosu, a góra stosu jest zwiększana o jedną pozycję.

Podobnie, gdy element jest usuwany, góra stosu jest zmniejszana. Kiedy stos jest pusty, jego wierzchołek jest ustawiany na -1. Istnieją dwie główne operacje „Push” i „Pop”, które są wykonywane na stosie.

Kolejka

Kolejka to kolejna liniowa struktura danych, w której elementy są dodawane na jednym końcu, zwanym „tylnym”, a usuwane z drugiego, zwanego „przednim”. Kolejka demonstruje FIFO (pierwsze weszło, pierwsze wyszło) typ metodologii dostępu do pamięci.

Kolejka

Powyższy schemat przedstawia kolejkę z tylnymi i przednimi końcami. Gdy kolejka jest pusta, tylne i przednie wskazówki pokrywają się ze sobą.

Nieliniowa struktura danych

W nieliniowych strukturach danych dane nie są ułożone sekwencyjnie, zamiast tego są ułożone w sposób nieliniowy. Elementy są połączone ze sobą w układzie nieliniowym.

Nieliniowe struktury danych to drzewa i wykresy.

narzędzia potrzebne do tworzenia stron internetowych

Drzewa

Drzewa są nieliniowymi wielopoziomowymi strukturami danych, które mają hierarchiczną zależność między elementami. Elementy drzewa nazywane są węzłami.

Węzeł na górze nazywany jest korzeniem drzewa. Katalog główny może mieć jeden lub więcej węzłów podrzędnych. Kolejne węzły mogą również mieć jeden lub więcej węzłów podrzędnych. Węzły, które nie mają węzłów potomnych, nazywane są węzłami liści.

Drzewa

Na powyższym diagramie pokazaliśmy drzewo z 6 węzłami. Z tych trzech węzłów są węzły-liście, jeden najwyższy jest węzłem głównym, a pozostałe są węzłami potomnymi. W zależności od liczby węzłów, węzłów potomnych itp. Lub relacji między węzłami mamy różne typy drzew.

Wykresy

Wykres to zbiór węzłów o nazwie wierzchołki połączone ze sobą za pomocą linków o nazwie Krawędzie . Grafy mogą mieć w sobie cykl, tj. Ten sam wierzchołek może być zarówno punktem początkowym, jak i końcowym określonej ścieżki. Drzewa nigdy nie mogą mieć cyklu.

Wykresy

Powyższy diagram jest wykresem nie skierowanym. Możemy również mieć skierowane wykresy, w których reprezentujemy krawędzie za pomocą skierowanych strzałek.

Operacje na strukturze danych

Wszystkie struktury danych wykonują różne operacje na swoich elementach.

Są one wspólne dla wszystkich struktur danych i są wymienione w następujący sposób:

  • Badawczy: Ta operacja jest wykonywana w celu wyszukania określonego elementu lub klucza. Najpopularniejsze algorytmy wyszukiwania to wyszukiwanie sekwencyjne / liniowe i wyszukiwanie binarne.
  • Sortowanie: Operacja sortowania polega na rozmieszczeniu elementów w strukturze danych w określonej kolejności rosnącej lub malejącej. Istnieją różne algorytmy sortowania, które są dostępne dla struktur danych. Najpopularniejsze z nich to: Szybkie sortowanie, sortowanie przez wybór, sortowanie przez scalanie itp.
  • Wprowadzenie: Operacja wstawiania polega na dodaniu elementu do struktury danych. To najważniejsza operacja iw wyniku dodania elementu układ zmienia się i musimy zadbać o to, aby struktura danych pozostała nienaruszona.
  • Usunięcie: Operacja usunięcia usuwa element ze struktury danych. Te same warunki, które należy wziąć pod uwagę przy wstawianiu, muszą być spełnione również w przypadku operacji usunięcia.
  • Przechodzenie: Mówimy, że przechodzimy przez strukturę danych, kiedy odwiedzamy każdy element w strukturze. Przechodzenie jest wymagane do wykonania określonych operacji na strukturze danych.

W naszych kolejnych tematach najpierw poznamy różne techniki wyszukiwania i sortowania, które należy wykonywać na strukturach danych.

Zalety struktury danych

  • Abstrakcja: Struktury danych są często implementowane jako abstrakcyjne typy danych. Użytkownicy mają dostęp tylko do zewnętrznego interfejsu, nie martwiąc się o podstawową implementację. W ten sposób struktura danych zapewnia warstwę abstrakcji.
  • Wydajność: Właściwa organizacja danych skutkuje wydajnym dostępem do danych, dzięki czemu programy są bardziej wydajne. Po drugie, możemy dobrać odpowiednią strukturę danych w zależności od naszych wymagań.
  • Możliwość ponownego użycia: Możemy ponownie wykorzystać zaprojektowane przez nas struktury danych. Można je również wkompilować w bibliotekę i rozesłać do klienta.

Wniosek

Na tym kończymy ten samouczek dotyczący wprowadzenia do struktur danych. W tym samouczku pokrótce przedstawiliśmy każdą ze struktur danych.

W naszych kolejnych samouczkach dowiemy się więcej o strukturach danych oraz różnych technikach wyszukiwania i sortowania.

=> Kliknij tutaj, aby zapoznać się z serią szkoleń Absolute C ++.

rekomendowane lektury

^