Od czasu wynalezienia komputerów ludzie używają terminu „ Dane ' w odniesieniu do Informacji o komputerze, przesyłanych lub przechowywanych. Istnieją jednak dane, które istnieją również w typach zamówień. Danymi mogą być liczby lub teksty zapisane na kartce papieru, w formie bitów i bajtów przechowywanych w pamięci urządzeń elektronicznych lub fakty przechowywane w umyśle danej osoby. Gdy świat zaczął się modernizować, dane te stały się istotnym aspektem codziennego życia każdego człowieka, a różne wdrożenia umożliwiły ich przechowywanie w inny sposób.

Dane to zbiór faktów i liczb lub zbiór wartości lub wartości o określonym formacie, który odnosi się do pojedynczego zestawu wartości pozycji. Elementy danych są następnie klasyfikowane w podelementy, które stanowią grupę elementów, które nie są znane jako prosta pierwotna forma elementu.

Rozważmy przykład, w którym nazwisko pracownika można podzielić na trzy podelementy: pierwszy, środkowy i ostatni. Jednakże identyfikator przypisany pracownikowi będzie zazwyczaj traktowany jako pojedynczy element.

Rysunek 1: Reprezentacja elementów danych

W powyższym przykładzie elementy takie jak identyfikator, wiek, płeć, pierwsze, średnie, ostatnie, ulica, miejscowość itp. są elementarnymi elementami danych. Natomiast nazwa i adres są elementami danych grupowych.

Co to jest struktura danych?

Struktura danych jest gałęzią informatyki. Badanie struktury danych pozwala nam zrozumieć organizację danych i zarządzanie przepływem danych w celu zwiększenia wydajności dowolnego procesu lub programu. Struktura danych to szczególny sposób przechowywania i organizowania danych w pamięci komputera, dzięki czemu można je łatwo odzyskać i efektywnie wykorzystać w przyszłości, jeśli zajdzie taka potrzeba. Danymi można zarządzać na różne sposoby, na przykład logiczny lub matematyczny model określonej organizacji danych nazywany jest strukturą danych.

Zakres konkretnego modelu danych zależy od dwóch czynników:

1. Po pierwsze, należy go wczytać do struktury na tyle, aby odzwierciedlał określoną korelację danych z obiektem ze świata rzeczywistego.
2. Po drugie, tworzenie powinno być na tyle proste, aby w razie potrzeby można było dostosować się do wydajnego przetwarzania danych.

Przykładami struktur danych są tablice, listy połączone, stosy, kolejki, drzewa itp. Struktury danych są szeroko stosowane w niemal każdym aspekcie informatyki, tj. w projektowaniu kompilatorów, systemach operacyjnych, grafice, sztucznej inteligencji i wielu innych.

Struktury danych stanowią główną część wielu algorytmów informatycznych, ponieważ umożliwiają programistom efektywne zarządzanie danymi. Odgrywa kluczową rolę w poprawie wydajności programu lub oprogramowania, ponieważ głównym celem oprogramowania jest jak najszybsze przechowywanie i odzyskiwanie danych użytkownika.

w wyrażeniu regularnym Java

Podstawowe terminologie związane ze strukturami danych

Struktury danych są elementami składowymi dowolnego oprogramowania lub programu. Wybór odpowiedniej struktury danych dla programu jest niezwykle trudnym zadaniem dla programisty.

Poniżej przedstawiono kilka podstawowych terminologii używanych w przypadku struktur danych:

Dane:Dane możemy zdefiniować jako wartość elementarną lub zbiór wartości. Na przykład imię i nazwisko Pracownika oraz jego numer identyfikacyjny są danymi związanymi z Pracownikiem.Elementy danych:Pojedyncza jednostka wartości nazywana jest elementem danych.Elementy grupowe:Elementy danych posiadające podrzędne elementy danych nazywane są elementami grupowymi. Na przykład imię i nazwisko pracownika może składać się z imienia, drugiego imienia i nazwiska.Przedmioty podstawowe:Elementy danych, których nie można podzielić na podelementy, nazywane są elementami elementarnymi. Na przykład identyfikator pracownika.Podmiot i atrybut:Klasa pewnych obiektów jest reprezentowana przez Byt. Składa się z różnych atrybutów. Każdy atrybut symbolizuje specyficzną właściwość tej jednostki. Na przykład,

Podmioty o podobnych atrybutach tworzą Zestaw jednostek . Każdy atrybut zestawu jednostek ma zakres wartości, czyli zbiór wszystkich możliwych wartości, które można przypisać do konkretnego atrybutu.

Termin „informacja” jest czasami używany w odniesieniu do danych posiadających określone atrybuty danych znaczących lub przetworzonych.

Pole:Pojedyncza elementarna jednostka informacji symbolizująca Atrybut Bytu nazywana jest Polem.Nagrywać:Zbiór różnych elementów danych nazywany jest rekordem. Na przykład, jeśli mówimy o podmiocie pracownika, wówczas jego nazwę, identyfikator, adres i stanowisko można pogrupować w celu utworzenia rekordu pracownika.Plik:Zbiór różnych rekordów jednego typu jest nazywany plikiem. Na przykład, jeśli jest 100 pracowników, w powiązanym pliku będzie 25 rekordów zawierających dane o każdym pracowniku.

Zrozumienie potrzeby struktur danych

Ponieważ aplikacje stają się coraz bardziej złożone, a ilość danych rośnie z każdym dniem, co może prowadzić do problemów z wyszukiwaniem danych, szybkością przetwarzania, obsługą wielu żądań i wieloma innymi. Struktury danych obsługują różne metody efektywnego organizowania, zarządzania i przechowywania danych. Za pomocą struktur danych możemy łatwo przeglądać elementy danych. Struktury danych zapewniają wydajność, możliwość ponownego użycia i abstrakcję.

Dlaczego powinniśmy uczyć się struktur danych?

1. Struktury danych i algorytmy to dwa kluczowe aspekty informatyki.
2. Struktury danych pozwalają nam organizować i przechowywać dane, natomiast algorytmy pozwalają nam w znaczący sposób je przetwarzać.
3. Nauka struktur danych i algorytmów pomoże nam stać się lepszymi programistami.
4. Będziemy mogli pisać kod, który będzie bardziej efektywny i niezawodny.
5. Będziemy także mogli szybciej i skuteczniej rozwiązywać problemy.

Zrozumienie celów struktur danych

Struktury danych spełniają dwa uzupełniające się cele:

Poprawność:Struktury danych są zaprojektowane tak, aby działać poprawnie dla wszystkich rodzajów danych wejściowych w oparciu o interesującą nas dziedzinę. Krótko mówiąc, poprawność stanowi główny cel Struktury Danych, który zawsze zależy od problemów, które Struktura Danych ma rozwiązać.Efektywność:Struktury danych również wymagają wydajności. Powinien przetwarzać dane szybko, bez wykorzystywania wielu zasobów komputera, takich jak przestrzeń pamięci. W stanie czasu rzeczywistego wydajność struktury danych jest kluczowym czynnikiem decydującym o sukcesie i porażce procesu.

Zrozumienie niektórych kluczowych cech struktur danych

Niektóre z istotnych cech struktur danych to:

Krzepkość:Ogólnie rzecz biorąc, celem wszystkich programistów komputerowych jest tworzenie oprogramowania, które zapewnia prawidłowe wyniki dla każdego możliwego wejścia, wraz z wydajnym wykonaniem na wszystkich platformach sprzętowych. Tego typu solidne oprogramowanie musi zarządzać zarówno prawidłowymi, jak i nieprawidłowymi danymi wejściowymi.Zdolność adaptacji:Tworzenie aplikacji, takich jak przeglądarki internetowe, edytory tekstu i wyszukiwarka internetowa, obejmuje ogromne systemy oprogramowania, które wymagają prawidłowego i wydajnego działania lub wykonywania przez wiele lat. Co więcej, oprogramowanie ewoluuje pod wpływem pojawiających się technologii lub stale zmieniających się warunków rynkowych.Możliwość ponownego użycia:Funkcje takie jak możliwość ponownego użycia i możliwość adaptacji idą w parze. Wiadomo, że programista potrzebuje wielu zasobów, aby zbudować dowolne oprogramowanie, co czyni go kosztownym przedsięwzięciem. Jeśli jednak oprogramowanie zostanie opracowane w sposób umożliwiający ponowne użycie i adaptację, będzie można je zastosować w większości przyszłych zastosowań. Zatem wykonując wysokiej jakości struktury danych, możliwe jest zbudowanie oprogramowania wielokrotnego użytku, które wydaje się być opłacalne i oszczędzające czas.

Klasyfikacja struktur danych

Struktura danych zapewnia uporządkowany zestaw zmiennych powiązanych ze sobą na różne sposoby. Stanowi podstawę narzędzia programistycznego, które oznacza relacje między elementami danych i umożliwia programistom efektywne przetwarzanie danych.

Struktury danych możemy podzielić na dwie kategorie:

1. Pierwotna struktura danych
2. Nieprymitywna struktura danych

Poniższy rysunek przedstawia różne klasyfikacje struktur danych.

Rysunek 2: Klasyfikacje struktur danych

Prymitywne struktury danych

Prymitywne struktury danychto struktury danych składające się z liczb i pojawiających się znaków wbudowany w programy.
1. Tymi strukturami danych można manipulować lub obsługiwać je bezpośrednio za pomocą instrukcji na poziomie maszyny.
2. Podstawowe typy danych, takie jak Liczba całkowita, zmiennoprzecinkowa, znakowa , I Wartość logiczna należą do prymitywnych struktur danych.
3. Te typy danych są również nazywane Proste typy danych , ponieważ zawierają znaki, których nie można dalej dzielić

Nieprymitywne struktury danych

Nieprymitywne struktury danychto te struktury danych wywodzące się z prymitywnych struktur danych.
1. Tymi strukturami danych nie można manipulować ani nimi sterować bezpośrednio za pomocą instrukcji na poziomie maszyny.
2. Te struktury danych skupiają się na tworzeniu zestawu elementów danych, czyli albo jednorodny (ten sam typ danych) lub heterogeniczny (różne typy danych).
3. W oparciu o strukturę i układ danych możemy podzielić te struktury danych na dwie podkategorie -
   1. Liniowe struktury danych
   2. Nieliniowe struktury danych

Liniowe struktury danych

Struktura danych, która zachowuje liniowe połączenie między elementami danych, nazywana jest liniową strukturą danych. Uporządkowanie danych odbywa się liniowo, gdzie każdy element składa się z następników i poprzedników, z wyjątkiem pierwszego i ostatniego elementu danych. Niekoniecznie jest to jednak prawdą w przypadku pamięci, gdyż układ nie może być sekwencyjny.

W oparciu o alokację pamięci liniowe struktury danych dzieli się dalej na dwa typy:

Statyczne struktury danych:Struktury danych o stałym rozmiarze nazywane są statycznymi strukturami danych. Pamięć dla tych struktur danych jest przydzielana w czasie kompilatora i użytkownik nie może zmienić ich rozmiaru po skompilowaniu; jednakże dane w nich zapisane mogą zostać zmienione.
The Szyk jest najlepszym przykładem statycznej struktury danych, ponieważ mają stały rozmiar, a jej dane można później modyfikować.Dynamiczne struktury danych:Struktury danych o rozmiarze dynamicznym nazywane są dynamicznymi strukturami danych. Pamięć tych struktur danych jest przydzielana w czasie wykonywania, a ich rozmiar zmienia się w czasie wykonywania kodu. Co więcej, użytkownik może zmienić rozmiar, a także elementy danych przechowywanych w tych strukturach danych w czasie wykonywania kodu.
Połączone listy, stosy , I Ogony są typowymi przykładami dynamicznych struktur danych

Rodzaje liniowych struktur danych

Poniżej znajduje się lista liniowych struktur danych, których zwykle używamy:

1. Tablice

Jakiś Szyk to struktura danych używana do gromadzenia wielu elementów danych tego samego typu w jedną zmienną. Zamiast przechowywać wiele wartości tego samego typu danych w oddzielnych nazwach zmiennych, moglibyśmy przechowywać je wszystkie razem w jednej zmiennej. To stwierdzenie nie oznacza, że ​​będziemy musieli zjednoczyć wszystkie wartości tego samego typu danych w dowolnym programie w jedną tablicę tego typu danych. Często jednak zdarza się, że określone zmienne tego samego typu danych są ze sobą powiązane w sposób odpowiedni dla tablicy.

Tablica to lista elementów, gdzie każdy element ma swoje unikalne miejsce na liście. Elementy danych tablicy mają tę samą nazwę zmiennej; jednakże każdy z nich ma inny numer indeksu zwany indeksem dolnym. Dostęp do dowolnego elementu danych z listy możemy uzyskać za pomocą jego lokalizacji na liście. Zatem kluczową cechą tablic, którą należy zrozumieć, jest to, że dane są przechowywane w sąsiadujących lokalizacjach pamięci, co umożliwia użytkownikom przeglądanie elementów danych tablicy przy użyciu ich odpowiednich indeksów.

Rysunek 3. Tablica

css pogrubione

Tablice można podzielić na różne typy:

Tablica jednowymiarowa:Tablica zawierająca tylko jeden wiersz elementów danych nazywana jest tablicą jednowymiarową. Jest przechowywany w rosnącej lokalizacji przechowywania.Tablica dwuwymiarowa:Tablica składająca się z wielu wierszy i kolumn elementów danych nazywana jest tablicą dwuwymiarową. Nazywa się ją także matrycą.Tablica wielowymiarowa:Możemy zdefiniować tablicę wielowymiarową jako tablicę tablic. Tablice wielowymiarowe nie są ograniczone do dwóch indeksów ani dwóch wymiarów, ponieważ mogą zawierać dowolną liczbę indeksów w zależności od potrzeb.

Niektóre zastosowania tablicy:

1. Możemy przechowywać listę elementów danych należących do tego samego typu danych.
2. Tablica działa jako pamięć pomocnicza dla innych struktur danych.
3. Tablica pomaga również przechowywać elementy danych drzewa binarnego o stałej liczbie.
4. Array pełni także funkcję magazynu macierzy.

2. Połączone listy

A Połączona lista to kolejny przykład liniowej struktury danych używanej do dynamicznego przechowywania zbioru elementów danych. Elementy danych w tej strukturze danych są reprezentowane przez węzły połączone za pomocą łączy lub wskaźników. Każdy węzeł zawiera dwa pola, pole informacyjne składa się z danych rzeczywistych, natomiast pole wskaźnikowe składa się z adresów kolejnych węzłów na liście. Wskaźnik ostatniego węzła połączonej listy składa się ze wskaźnika zerowego, ponieważ nie wskazuje na nic. W przeciwieństwie do tablic użytkownik może dynamicznie dostosowywać rozmiar połączonej listy zgodnie z wymaganiami.

Rysunek 4. Połączona lista

Listy połączone można podzielić na różne typy:

Lista pojedynczo połączona:Lista pojedynczo połączona jest najpopularniejszym typem listy połączonej. Każdy węzeł ma dane i pole wskaźnikowe zawierające adres do następnego węzła.Lista podwójnie połączona:Lista podwójnie połączona składa się z pola informacyjnego i dwóch pól wskaźnikowych. Pole informacyjne zawiera dane. Pierwsze pole wskaźnikowe zawiera adres poprzedniego węzła, natomiast kolejne pole wskaźnikowe zawiera odniesienie do następnego węzła. Dzięki temu możemy poruszać się w obu kierunkach (do tyłu i do przodu).Okrągła lista połączona:Lista połączona cyklicznie jest podobna do listy pojedynczo połączonej. Jedyną kluczową różnicą jest to, że ostatni węzeł zawiera adres pierwszego węzła, tworząc okrągłą pętlę na Circular Linked List.

Niektóre zastosowania list połączonych:

1. Listy połączone pomagają nam implementować stosy, kolejki, drzewa binarne i wykresy o predefiniowanym rozmiarze.
2. Możemy również zaimplementować funkcję systemu operacyjnego do dynamicznego zarządzania pamięcią.
3. Listy połączone umożliwiają także implementację wielomianów w operacjach matematycznych.
4. Możemy używać Circular Linked List do implementowania systemów operacyjnych lub funkcji aplikacji, które wykonują zadania okrężnie.
5. Okrągła lista połączona jest również pomocna w pokazie slajdów, w którym użytkownik musi wrócić do pierwszego slajdu po zaprezentowaniu ostatniego slajdu.
6. Lista podwójnie połączona służy do implementowania przycisków „do przodu” i „do tyłu” w przeglądarce, umożliwiających poruszanie się do przodu i do tyłu na otwartych stronach witryny internetowej.

3. Stosy

A Stos jest liniową strukturą danych zgodną z LIFO (Last In, First Out), która umożliwia operacje takie jak wstawianie i usuwanie z jednego końca stosu, tj. z góry. Stosy można implementować za pomocą pamięci ciągłej, tablicy i pamięci nieciągłej, listy połączonej. Prawdziwymi przykładami stosów są stosy książek, talia kart, stosy pieniędzy i wiele innych.

Rysunek 5. Prawdziwy przykład stosu

Powyższy rysunek przedstawia rzeczywisty przykład stosu, w którym operacje są wykonywane tylko z jednego końca, np. wstawianie i usuwanie nowych książek ze szczytu stosu. Oznacza to, że wstawianie i usuwanie na stosie może być wykonane tylko z góry stosu. W danym momencie możemy uzyskać dostęp tylko do szczytów Stosu.

Podstawowe operacje na stosie są następujące:

Naciskać:Operację wstawienia nowego elementu do stosu nazywa się operacją wypychania.Muzyka pop:Operację usuwania lub usuwania elementów ze stosu nazywa się operacją Pop.

Rysunek 6. Stos

przykłady programów w Pythonie

Niektóre zastosowania stosów:

1. Stos jest używany jako struktura tymczasowego przechowywania dla operacji rekurencyjnych.
2. Stos jest również wykorzystywany jako struktura pamięci pomocniczej dla wywołań funkcji, operacji zagnieżdżonych i funkcji odroczonych/przełożonych.
3. Możemy zarządzać wywołaniami funkcji za pomocą stosów.
4. Stosy są również wykorzystywane do oceny wyrażeń arytmetycznych w różnych językach programowania.
5. Stosy są również pomocne w konwertowaniu wyrażeń infiksowych na wyrażenia postfiksowe.
6. Stosy pozwalają nam sprawdzić składnię wyrażenia w środowisku programistycznym.
7. Możemy dopasować nawiasy za pomocą stosów.
8. Do odwrócenia ciągu można użyć stosów.
9. Stosy są pomocne w rozwiązywaniu problemów w oparciu o cofanie się.
10. Możemy używać stosów w przeszukiwaniu w głąb wykresu i przechodzenia przez drzewo.
11. Stosy są również używane w funkcjach systemu operacyjnego.
12. Stosy są także używane w funkcjach COFNIJ i PONOWNIE w edycji.

4. Ogony

A Kolejka to liniowa struktura danych podobna do stosu z pewnymi ograniczeniami dotyczącymi wstawiania i usuwania elementów. Wstawianie elementu do kolejki odbywa się na jednym końcu, a usuwanie na drugim lub przeciwległym końcu. Możemy zatem stwierdzić, że struktura danych kolejki jest zgodna z zasadą FIFO (pierwsze weszło, pierwsze wyszło), aby manipulować elementami danych. Implementację kolejek można wykonać za pomocą tablic, list połączonych lub stosów. Niektóre z rzeczywistych przykładów kolejek to kolejka przy kasie biletowej, schody ruchome, myjnia samochodowa i wiele innych.

Rysunek 7. Przykład kolejki z życia wzięty

Powyższy obraz to realistyczna ilustracja kasy biletowej do kina, która może pomóc nam zrozumieć kolejkę, w której klient, który przychodzi pierwszy, jest zawsze obsługiwany jako pierwszy. Klient, który przyjdzie ostatni, niewątpliwie zostanie obsłużony jako ostatni. Oba końce kolejki są otwarte i mogą wykonywać różne operacje. Innym przykładem jest linia food court, w której klient jest wstawiany od tyłu, a usuwany od przodu, po wykonaniu usługi, o którą prosił.

Poniżej przedstawiono podstawowe operacje kolejki:

Kolejka:Wstawienie lub dodanie niektórych elementów danych do kolejki nazywa się kolejkowaniem. Wstawianie elementu zawsze odbywa się za pomocą tylnego wskaźnika.Usuń z kolejki:Usuwanie lub usuwanie elementów danych z kolejki nazywane jest usuwaniem z kolejki. Usuwanie elementu zawsze odbywa się za pomocą przedniego wskaźnika.

Cyfra 8. Kolejka

Niektóre zastosowania kolejek:

1. Kolejki są zwykle używane w operacji wyszukiwania wszerz na wykresach.
2. Kolejki są również używane w operacjach Harmonogramu zadań w systemach operacyjnych, np. kolejka bufora klawiatury do przechowywania klawiszy naciśniętych przez użytkowników oraz kolejka bufora drukowania do przechowywania dokumentów wydrukowanych przez drukarkę.
3. Kolejki są odpowiedzialne za planowanie procesora, planowanie zadań i planowanie dysku.
4. Kolejki priorytetowe są wykorzystywane podczas operacji pobierania plików w przeglądarce.
5. Kolejki służą także do przesyłania danych pomiędzy urządzeniami peryferyjnymi a procesorem.
6. Kolejki są również odpowiedzialne za obsługę przerwań generowanych przez aplikacje użytkownika dla procesora.

Nieliniowe struktury danych

Nieliniowe struktury danych to struktury danych, w których elementy danych nie są ułożone w kolejności. W tym przypadku wstawianie i usuwanie danych nie jest możliwe w sposób liniowy. Istnieje hierarchiczna relacja pomiędzy poszczególnymi elementami danych.

Rodzaje nieliniowych struktur danych

Poniżej znajduje się lista nieliniowych struktur danych, których zwykle używamy:

1. Drzewa

Drzewo to nieliniowa struktura danych i hierarchia zawierająca zbiór węzłów, w którym każdy węzeł drzewa przechowuje wartość i listę odniesień do innych węzłów („dzieci”).

Struktura danych drzewa to wyspecjalizowana metoda porządkowania i gromadzenia danych w komputerze w celu efektywniejszego ich wykorzystania. Zawiera węzeł centralny, węzły konstrukcyjne i podwęzły połączone krawędziami. Można również powiedzieć, że struktura danych drzewa składa się z połączonych korzeni, gałęzi i liści.

Rysunek 9. Drzewo

Drzewa można podzielić na różne typy:

Drzewo binarne:Strukturę danych drzewa, w której każdy węzeł nadrzędny może mieć co najwyżej dwoje dzieci, nazywa się drzewem binarnym.Drzewo wyszukiwania binarnego:Drzewo wyszukiwania binarnego to struktura danych drzewa, w której możemy łatwo przechowywać posortowaną listę liczb.Drzewo AVL:Drzewo AVL to samobalansujące się binarne drzewo wyszukiwania, w którym każdy węzeł przechowuje dodatkowe informacje zwane współczynnikiem równowagi, którego wartość wynosi -1, 0 lub +1.Drzewo B:B-Drzewo to specjalny rodzaj samobalansującego drzewa wyszukiwania binarnego, w którym każdy węzeł składa się z wielu kluczy i może mieć więcej niż dwoje dzieci.

Niektóre zastosowania drzew:

drzewo avl

1. Drzewa wdrażają struktury hierarchiczne w systemach komputerowych, takich jak katalogi i systemy plików.
2. Drzewa służą także do realizacji struktury nawigacyjnej serwisu WWW.
3. Możemy wygenerować kod podobny do kodu Huffmana za pomocą drzew.
4. Drzewa są również pomocne w podejmowaniu decyzji w aplikacjach do gier.
5. Drzewa są odpowiedzialne za implementację kolejek priorytetowych dla funkcji planowania systemu operacyjnego w oparciu o priorytety.
6. Drzewa są również odpowiedzialne za analizowanie wyrażeń i instrukcji w kompilatorach różnych języków programowania.
7. Możemy używać drzew do przechowywania kluczy danych do indeksowania dla systemu zarządzania bazami danych (DBMS).
8. Spanning Trees pozwala nam kierować decyzjami w sieciach komputerowych i komunikacyjnych.
9. Drzewa są również wykorzystywane w algorytmie wyszukiwania ścieżek wdrażanym w zastosowaniach sztucznej inteligencji (AI), robotyce i grach wideo.

2. Wykresy

Wykres to kolejny przykład nieliniowej struktury danych zawierającej skończoną liczbę węzłów lub wierzchołków i łączących je krawędzi. Wykresy są wykorzystywane do rozwiązywania problemów świata rzeczywistego, w którym oznaczają obszar problemowy jako sieć, taką jak sieci społecznościowe, sieci obwodów i sieci telefoniczne. Na przykład węzły lub wierzchołki Grafu mogą reprezentować pojedynczego użytkownika w sieci telefonicznej, podczas gdy krawędzie reprezentują połączenie między nimi za pośrednictwem telefonu.

Strukturę danych Graph, G, uważa się za strukturę matematyczną składającą się ze zbioru wierzchołków V i zbioru krawędzi E, jak pokazano poniżej:

G = (V, E)

Rysunek 10. Wykres

Powyższy rysunek przedstawia graf mający siedem wierzchołków A, B, C, D, E, F, G i dziesięć krawędzi [A, B], [A, C], [B, C], [B, D], [B, E], [C, D], [D, E], [D, F], [E, F] i [E, G].

W zależności od położenia wierzchołków i krawędzi grafy można podzielić na różne typy:

Wykres zerowy:Graf z pustym zestawem krawędzi nazywany jest grafem zerowym.Trywialny wykres:Graf mający tylko jeden wierzchołek nazywany jest grafem trywialnym.Prosty wykres:Wykres niezawierający pętli własnych ani wielu krawędzi nazywany jest wykresem prostym.Wiele wykresów:Graf nazywamy wielokrotnym, jeśli składa się z wielu krawędzi, ale nie zawiera pętli własnych.Pseudowykres:Wykres zawierający pętle własne i wiele krawędzi nazywany jest pseudografem.Wykres nieskierowany:Wykres składający się z nieskierowanych krawędzi nazywany jest grafem niekierowanym.Kierowany wykres:Wykres składający się z skierowanych krawędzi pomiędzy wierzchołkami nazywany jest grafem skierowanym.Połączony wykres:Graf posiadający co najmniej jedną ścieżkę pomiędzy każdą parą wierzchołków nazywany jest grafem połączonym.Odłączony wykres:Graf, w którym nie istnieje żadna ścieżka pomiędzy co najmniej jedną parą wierzchołków, nazywany jest grafem rozłączonym.Zwykły wykres:Graf, w którym wszystkie wierzchołki mają ten sam stopień, nazywany jest grafem regularnym.Pełny wykres:Graf, w którym wszystkie wierzchołki mają krawędzie pomiędzy każdą parą wierzchołków, nazywany jest grafem pełnym.Wykres cyklu:Graf nazywa się cyklem, jeśli ma co najmniej trzy wierzchołki i krawędzie tworzące cykl.Wykres cykliczny:Graf nazywamy cyklicznym wtedy i tylko wtedy, gdy istnieje co najmniej jeden cykl.Wykres acykliczny:Wykres mający zero cykli nazywany jest grafem acyklicznym.Skończony wykres:Graf o skończonej liczbie wierzchołków i krawędzi nazywany jest grafem skończonym.Nieskończony wykres:Wykres z nieskończoną liczbą wierzchołków i krawędzi nazywany jest grafem nieskończonym.Wykres dwudzielny:Graf, w którym wierzchołki można podzielić na niezależne zbiory A i B, a wszystkie wierzchołki zbioru A powinny być połączone tylko z wierzchołkami występującymi w zbiorze B z pewnymi krawędziami, nazywany jest grafem dwudzielnym.Wykres planarny:Graf nazywamy planarnym, jeśli możemy go narysować w jednej płaszczyźnie z dwiema krawędziami przecinającymi się.Wykres Eulera:Graf nazywa się Eulerem wtedy i tylko wtedy, gdy wszystkie wierzchołki są parzystymi stopniami.Wykres Hamiltona:Spójny wykres składający się z obwodu hamiltonowskiego nazywany jest grafem hamiltonowskim.

Niektóre zastosowania wykresów:

przypisy do przecen

1. Wykresy pomagają nam przedstawiać trasy i sieci w zastosowaniach związanych z transportem, podróżami i komunikacją.
2. Wykresy służą do wyświetlania tras w systemie GPS.
3. Wykresy pomagają nam również przedstawić wzajemne połączenia w sieciach społecznościowych i innych aplikacjach sieciowych.
4. Wykresy są wykorzystywane w aplikacjach mapujących.
5. Wykresy odpowiadają za reprezentację preferencji użytkownika w aplikacjach e-commerce.
6. Wykresy są również wykorzystywane w sieciach użyteczności publicznej w celu identyfikacji problemów, jakie stwarzają korporacje lokalne lub miejskie.
7. Wykresy pomagają także zarządzać wykorzystaniem i dostępnością zasobów w organizacji.
8. Wykresy są również wykorzystywane do tworzenia map łączy dokumentów w witrynach internetowych w celu przedstawienia powiązań między stronami za pomocą hiperłączy.
9. Wykresy są również wykorzystywane w ruchach robotów i sieciach neuronowych.

Podstawowe operacje na strukturach danych

W poniższej sekcji omówimy różne typy operacji, które możemy wykonać w celu manipulowania danymi w każdej strukturze danych:

Przejście:Przechodzenie przez strukturę danych oznacza dostęp do każdego elementu danych dokładnie raz, aby można było nim administrować. Na przykład przechodzenie jest wymagane podczas drukowania nazwisk wszystkich pracowników w dziale.Szukaj:Wyszukiwanie to kolejna operacja na strukturze danych, która oznacza znalezienie lokalizacji jednego lub większej liczby elementów danych spełniających określone ograniczenia. Taki element danych może, ale nie musi, występować w danym zestawie elementów danych. Na przykład możemy użyć operacji wyszukiwania, aby znaleźć nazwiska wszystkich pracowników, którzy mają staż pracy dłuższy niż 5 lat.Wprowadzenie:Wstawienie oznacza wstawienie lub dodanie nowych elementów danych do zbioru. Na przykład możemy użyć operacji wstawiania, aby dodać dane nowego pracownika, którego firma niedawno zatrudniła.Usunięcie:Usunięcie oznacza usunięcie lub usunięcie określonego elementu danych z podanej listy elementów danych. Na przykład możemy użyć operacji usuwania, aby usunąć nazwisko pracownika, który odszedł z pracy.Sortowanie:Sortowanie oznacza uporządkowanie elementów danych w kolejności rosnącej lub malejącej, w zależności od typu aplikacji. Na przykład możemy użyć operacji sortowania, aby uporządkować nazwiska pracowników w dziale w porządku alfabetycznym lub oszacować trzech najlepszych pracowników w miesiącu, układając wyniki pracowników w kolejności malejącej i wyodrębniając szczegółowe informacje o trzech najlepszych.Łączyć:Scalanie oznacza połączenie elementów danych z dwóch posortowanych list w celu utworzenia jednej listy posortowanych elementów danych.Tworzyć:Tworzenie to operacja służąca do rezerwowania pamięci dla elementów danych programu. Możemy wykonać tę operację za pomocą instrukcji deklaracji. Tworzenie struktury danych może odbywać się podczas:
1. Czas kompilacji
2. Czas działania
   Na przykład malloc() funkcja jest używana w języku C do tworzenia struktury danych.
Wybór:Selekcja oznacza wybranie konkretnych danych z dostępnych. Możemy wybrać dowolne dane, określając warunki wewnątrz pętli.Aktualizacja:Operacja Aktualizacja pozwala na aktualizację lub modyfikację danych w strukturze danych. Możemy także zaktualizować dowolne dane, określając pewne warunki wewnątrz pętli, na przykład operację Selection.Rozdzielać:Operacja Splitting pozwala na podzielenie danych na różne podczęści, skracając całkowity czas realizacji procesu.

Zrozumienie abstrakcyjnego typu danych

Zgodnie z Narodowy Instytut Standardów i Technologii (NIST) , struktura danych to układ informacji, zazwyczaj w pamięci, zapewniający lepszą wydajność algorytmu. Struktury danych obejmują połączone listy, stosy, kolejki, drzewa i słowniki. Mogą to być również jednostki teoretyczne, takie jak imię i nazwisko oraz adres osoby.

Z powyższej definicji wynika, że ​​operacje na strukturze danych obejmują:

1. Wysoki poziom abstrakcji, np. dodawanie lub usuwanie pozycji z listy.
2. Wyszukiwanie i sortowanie elementu na liście.
3. Dostęp do elementu o najwyższym priorytecie na liście.

Ilekroć struktura danych wykonuje takie operacje, nazywa się to Abstrakcyjny typ danych (ADT) .

Możemy go zdefiniować jako zbiór elementów danych wraz z operacjami na danych. Termin „abstrakcyjny” odnosi się do faktu, że dane i zdefiniowane na nich podstawowe operacje są badane niezależnie od ich implementacji. Obejmuje to, co możemy zrobić z danymi, a nie jak możemy to zrobić.

Implementacja ADI zawiera strukturę pamięci w celu przechowywania elementów danych i algorytmów dla podstawowych operacji. Wszystkie struktury danych, takie jak tablica, lista połączona, kolejka, stos itp., są przykładami ADT.

Zrozumienie zalet stosowania ADT

W prawdziwym świecie programy ewoluują w wyniku nowych ograniczeń lub wymagań, więc modyfikacja programu zazwyczaj wymaga zmiany w jednej lub wielu strukturach danych. Załóżmy na przykład, że chcemy wstawić nowe pole do rekordu pracownika, aby śledzić więcej szczegółów na temat każdego pracownika. W takim przypadku możemy poprawić wydajność programu, zastępując tablicę strukturą Linked. W takiej sytuacji przepisywanie każdej procedury wykorzystującej zmodyfikowaną strukturę jest niewłaściwe. Dlatego lepszą alternatywą jest oddzielenie struktury danych od informacji o jej implementacji. Na tej zasadzie opiera się użycie abstrakcyjnych typów danych (ADT).

Niektóre zastosowania struktur danych

Poniżej przedstawiono niektóre zastosowania struktur danych:

1. Struktury danych pomagają w organizacji danych w pamięci komputera.
2. Struktury danych pomagają również w reprezentowaniu informacji w bazach danych.
3. Data Structures pozwala na implementację algorytmów przeszukiwania danych (np. wyszukiwarka).
4. Możemy używać struktur danych do implementowania algorytmów manipulacji danymi (na przykład edytory tekstu).
5. Możemy również zaimplementować algorytmy do analizy danych przy użyciu struktur danych (na przykład eksploratorów danych).
6. Struktury danych obsługują algorytmy generowania danych (na przykład generator liczb losowych).
7. Struktury danych obsługują również algorytmy kompresji i dekompresji danych (na przykład narzędzie zip).
8. Możemy również używać struktur danych do implementowania algorytmów szyfrowania i deszyfrowania danych (na przykład system bezpieczeństwa).
9. Za pomocą Data Structures możemy zbudować oprogramowanie zarządzające plikami i katalogami (na przykład menedżer plików).
10. Możemy również opracować oprogramowanie, które może renderować grafikę przy użyciu struktur danych. (Na przykład przeglądarka internetowa lub oprogramowanie do renderowania 3D).

Oprócz nich, jak wspomniano wcześniej, istnieje wiele innych zastosowań struktur danych, które mogą pomóc nam w zbudowaniu dowolnego oprogramowania.