Czy każdy typ danych po prostu sprowadza się do węzłów ze wskaźnikami?

Tablica lub wektor to tylko sekwencja wartości. Z pewnością można je zaimplementować za pomocą połączonej listy. To tylko kilka węzłów ze wskaźnikami do następnego węzła.

Stosy i kolejki to dwa abstrakcyjne typy danych powszechnie nauczane na kursach CS wprowadzających. Gdzieś w klasie uczniowie często muszą implementować stosy i kolejki, używając połączonej listy jako podstawowej struktury danych, co oznacza, że ​​wróciliśmy do tego samego pomysłu „kolekcji węzłów”.

Kolejki priorytetowe można tworzyć za pomocą sterty. Stertę można traktować jako drzewo o minimalnej wartości u podstawy. Drzewa wszelkiego rodzaju, w tym BST, AVL, hałdy, można traktować jako zbiór węzłów połączonych krawędziami. Te węzły są ze sobą połączone, gdy jeden węzeł wskazuje inny.

Wygląda na to, że każda koncepcja danych może zawsze sprowadzać się do samych węzłów ze wskaźnikami do innego odpowiedniego węzła. Czy to prawda? Jeśli to takie proste, dlaczego podręczniki nie wyjaśniają, że dane to tylko kilka węzłów ze wskaźnikami? Jak przechodzimy od węzłów do kodu binarnego?

Cóż, w zasadzie do tego sprowadzają się wszystkie struktury danych. Dane z połączeniami. Wszystkie węzły są sztuczne - tak naprawdę nie istnieją fizycznie. Tu właśnie wchodzi część binarna. Powinieneś utworzyć kilka struktur danych w C ++ i sprawdzić, gdzie twoje obiekty lądują w pamięci. Dowiedz się, jak dane są ułożone w pamięci, może być bardzo interesujące.

Głównym powodem tak wielu różnych struktur jest to, że wszystkie one specjalizują się w tej czy innej rzeczy. Na przykład zazwyczaj iteracja przez wektor zamiast listy połączonej jest szybsza ze względu na sposób pobierania stron z pamięci. Połączona lista lepiej jest przechowywać większe typy, ponieważ wektory muszą przydzielić dodatkową przestrzeń dla nieużywanych miejsc (jest to wymagane przy projektowaniu wektora).

Na marginesie ciekawą strukturą danych, na którą warto spojrzeć, jest Tablica skrótów. Nie do końca jest zgodny z opisywanym systemem Nodes and Pointers.

TL; DR: Kontenery w zasadzie wszystkie węzły i wskaźniki, ale mają bardzo specyficzne zastosowania i są lepsze dla czegoś, a gorsze dla innych.

Wygląda na to, że każda koncepcja danych może zawsze sprowadzać się do samych węzłów ze wskaźnikami do innego odpowiedniego węzła.

Och, droga nie. Ranisz mnie.

Tak jak próbowałem wyjaśnić gdzie indziej („ Jaka jest różnica między drzewem wyszukiwania binarnego a stertą binarną? ”), Nawet w przypadku stałej struktury danych istnieje kilka poziomów do zrozumienia.

Podobnie jak wspomniana kolejka priorytetowa, jeśli chcesz jej tylko użyć, jest to abstrakcyjny typ danych. Używasz go, wiedząc, jakie obiekty przechowuje i jakie pytania możesz zadać. To więcej struktur danych jako worek przedmiotów. Na kolejnym poziomie jego słynna implementacja, binarna sterta, może być rozumiana jako drzewo binarne, ale ostatni poziom jest ze względów wydajnościowych implementowany jako tablica. Brak węzłów i wskaźników.

A także na przykład dla wykresów, które z pewnością wyglądają jak węzły i wskaźniki (krawędzie), masz dwie podstawowe reprezentacje, tablicę przylegania i listy przyległości. Nie wszystkie wskaźniki, jakie sobie wyobrażam.

Kiedy naprawdę próbujesz zrozumieć struktury danych, musisz przestudiować ich zalety i słabości. Czasami reprezentacja używa tablicy dla wydajności (zarówno przestrzeni, jak i czasu), czasem są wskaźniki (dla elastyczności). Dzieje się tak nawet wtedy, gdy masz dobre „standardowe” implementacje, takie jak C ++ STL, ponieważ tam również możesz czasami wybrać podstawowe reprezentacje. Zawsze istnieje kompromis.

Zróbmy analogię do matematyki. Rozważ następujące zdanie: „ jest funkcją ciągłą”. Funkcje są naprawdę zdefiniowane w kategoriach relacji, które są zdefiniowane w kategoriach zbiorów. Zbiór liczb rzeczywistych jest unikalnym kompletnym, całkowicie uporządkowanym polem: wszystkie te pojęcia mają definicje w prostszych terminach. Aby mówić o ciągłości, potrzebujesz koncepcji sąsiedztwa, która jest zdefiniowana w odniesieniu do topologii ... i tak dalej aż do aksjomatów ZFC.$f:\mathbb{R} \rightarrow \mathbb{R}$

Nikt nie oczekuje, że powiesz to wszystko, aby zdefiniować funkcję ciągłą, w przeciwnym razie nikt nie byłby w stanie wykonać żadnej pracy. Po prostu „ufamy”, że ktoś wykonał dla nas nudną pracę.

Każda struktura danych, o której możesz myśleć, sprowadza się do podstawowych obiektów, z którymi ma do czynienia bazowy model obliczeniowy, liczb całkowitych w niektórych rejestrach, jeśli używasz maszyny o swobodnym dostępie, lub symboli na niektórych taśmach, jeśli używasz maszyny Turinga.

Używamy abstrakcji, ponieważ uwalniają nasz umysł od błahych spraw, pozwalając nam mówić o bardziej złożonych problemach. Całkowicie uzasadnione jest po prostu „zaufanie”, że te struktury działają: przechodzenie do każdego szczegółu jest - o ile nie masz konkretnego powodu - bezowocnym ćwiczeniem, które nie dodaje nic do twojej argumentacji.

Oto kontrprzykład: w rachunku λ każdy typ danych sprowadza się do funkcji. Rachunek λ nie ma węzłów ani wskaźników, jedyne, co ma, to funkcje, dlatego wszystko musi być zaimplementowane za pomocą funkcji.

Oto przykład kodowania boolanów jako funkcji, napisanych w ECMAScript:

const T   = (thn, _  ) => thn,
      F   = (_  , els) => els,
      or  = (a  , b  ) => a(a, b),
      and = (a  , b  ) => a(b, a),
      not = a          => a(F, T),
      xor = (a  , b  ) => a(not(b), b),
      iff = (cnd, thn, els) => cnd(thn, els)();

A to lista wad:

const cons = (hd, tl) => which => which(hd, tl),
      first  = list => list(T),
      rest   = list => list(F);

Liczby naturalne mogą być implementowane jako funkcje iteratora.

Zestaw jest tym samym, co jego funkcja charakterystyczna (tj. containsMetoda).

Zauważ, że powyższe Church Encoding of Booleans jest tak naprawdę sposobem, w jaki warunkowe są implementowane w językach OO, takich jak Smalltalk, które nie mają booleanów, warunkowych lub pętli jako konstrukcji językowych i implementują je wyłącznie jako funkcję biblioteki. Przykład w Scali:

sealed abstract trait Boolean {
  def apply[T, U <: T, V <: T](thn: => U)(els: => V): T
  def ∧(other: => Boolean): Boolean
  def ∨(other: => Boolean): Boolean
  val ¬ : Boolean

  final val unary_! = ¬
  final def &(other: => Boolean) = ∧(other)
  final def |(other: => Boolean) = ∨(other)
}

case object True extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): U = thn
  override def ∧(other: => Boolean) = other
  override def ∨(other: => Boolean): this.type = this
  override final val ¬ = False
}

case object False extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): V = els
  override def ∧(other: => Boolean): this.type = this
  override def ∨(other: => Boolean) = other
  override final val ¬ = True
}

object BooleanExtension {
  import scala.language.implicitConversions
  implicit def boolean2Boolean(b: => scala.Boolean) = if (b) True else False
}

import BooleanExtension._

(2 < 3) { println("2 is less than 3") } { println("2 is greater than 3") }
// 2 is less than 3

Wiele (większość?) Struktur danych jest zbudowanych z węzłów i wskaźników. Tablice są kolejnym kluczowym elementem niektórych struktur danych.

Ostatecznie każda struktura danych to tylko kilka słów w pamięci lub kilka bitów. Liczy się ich struktura i sposób, w jaki interpretujemy i wykorzystujemy je.

Implementacja struktur danych zawsze sprowadza się do węzłów i wskaźników, tak.

Ale po co się tu zatrzymywać? Implementacja węzłów i wskaźników sprowadza się do bitów.

Implementacja bitów sprowadza się do sygnałów elektrycznych, przechowywania magnetycznego, być może kabli światłowodowych itp. (Jednym słowem, fizyka.)

To jest reductio ad absurdum stwierdzenia: „Wszystkie struktury danych sprowadzają się do węzłów i wskaźników”. To prawda, ale dotyczy tylko implementacji.

Chris Date bardzo dobrze rozróżnia implementację i model , choć jego esej jest skierowany w szczególności do baz danych.

Możemy pójść nieco dalej, jeśli zdamy sobie sprawę, że nie ma jednej linii podziału między modelem a implementacją. Jest to podobne (jeśli nie identyczne) do pojęcia „warstw abstrakcji”.

Na danej warstwie abstrakcji warstwy „pod” tobą (warstwy, na których budujesz) są zwykłymi „szczegółami implementacji” abstrakcji lub modelu, do którego się odnosisz.

Jednak same dolne warstwy abstrakcji mają szczegóły implementacji.

Jeśli czytasz instrukcję oprogramowania, dowiadujesz się o warstwie abstrakcji „prezentowanej” przez ten program, na której możesz budować własne abstrakcje (lub po prostu wykonywać czynności, takie jak wysyłanie wiadomości).

Jeśli poznasz szczegóły implementacji oprogramowania, dowiesz się, jak twórcy zbudowali abstrakcje, które zbudowali. „Szczegóły implementacji” mogą obejmować między innymi struktury danych i algorytmy.

Jednak nie uważa się, że pomiar napięcia jest częścią „szczegółów implementacji” jakiegokolwiek konkretnego oprogramowania, mimo że leży to u podstaw tego, jak „bity”, „bajty” i „pamięć” faktycznie działają na komputerze fizycznym.

Podsumowując, struktury danych są warstwą abstrakcji do wnioskowania o algorytmach i oprogramowaniu oraz ich implementacji. Fakt, że ta warstwa abstrakcji jest zbudowana na szczegółach implementacji niższego poziomu, takich jak węzły i wskaźniki, jest prawdziwy, ale nie ma znaczenia w warstwie abstrakcji.

Dużą częścią naprawdę zrozumienia systemu jest zrozumienie, w jaki sposób warstwy abstrakcji pasują do siebie. Dlatego ważne jest, aby zrozumieć, w jaki sposób wdrażane są struktury danych . Ale fakt, że są one wdrożone, nie oznacza, że ​​abstrakcja struktur danych nie istnieje.

Tablica lub wektor to tylko sekwencja wartości. Z pewnością można je zaimplementować za pomocą połączonej listy. To tylko kilka węzłów ze wskaźnikami do następnego węzła.

Macierz lub wektor można zaimplementować za pomocą połączonej listy, ale prawie nigdy nie powinno tak być.

$n$$n$$\Theta(n)$$\Theta(\log n)$$\Theta(1)$(tj. sekwencyjny blok pamięci o dostępie swobodnym). Ponadto na procesorze dostęp do rzeczywistej tablicy jest znacznie prostszy do wdrożenia i szybszy do wykonania, a przechowywanie zajmuje mniej pamięci, ponieważ nie trzeba marnować miejsca na wskaźniki między oddzielnymi węzłami.

$\Theta(n)$$\Theta(1)$$\Theta(1)$średnio kosztem co najwyżej stałego współczynnika dodatkowej pamięci, po prostu zaokrąglając rzeczywisty przydzielony rozmiar tablicy do np. najbliższej potęgi 2. Ale jeśli trzeba wykonać wiele wstawień i / lub usuwania elementy na środku listy, tablica fizyczna może nie być najlepszą implementacją struktury danych. Dość często jednak można wstawiać i usuwać wstawienia i operacje usuwania, które są tanie.

Jeśli nieco poszerzysz swój zakres, aby uwzględnić fizyczne przyległe tablice w swoim zestawie narzędzi, prawie wszystkie praktyczne struktury danych można rzeczywiście zaimplementować razem z tymi wraz z węzłami i wskaźnikami.

$\Theta(1)$operacja odwracania). W praktyce jednak funkcje te rzadko są wystarczająco przydatne, aby przezwyciężyć jego wady, które obejmują dodatkową złożoność implementacji i niezgodność ze standardowymi schematami usuwania śmieci .

Jeśli to takie proste, dlaczego podręczniki nie wyjaśniają, że dane to tylko kilka węzłów ze wskaźnikami?

Ponieważ nie to oznacza „dane”. Łączymy abstrakcyjne pomysły z implementacjami. „Dane” to bardzo abstrakcyjny pomysł: to tylko inna nazwa „informacji”. Kilka połączonych węzłów ze wskaźnikami (inaczej „struktura danych połączonych”) to znacznie bardziej konkretny pomysł: jest to szczególny sposób reprezentowania i organizowania informacji.

Niektóre abstrakcje danych nadają się bardzo dobrze do „powiązanych” implementacji. Nie ma wielu dobrych sposobów na wdrożenie rozgałęzienia całkowicie w pełni ogólnego drzewa bez użycia wyraźnych węzłów i wskaźników (lub pewnego izomorfizmu węzłów i wskaźników). Ale są też inne abstrakcje, których nigdy nie zaimplementowałbyś za pomocą węzłów i wskaźników. Przychodzą mi na myśl liczby zmiennoprzecinkowe.

Stosy i kolejki spadają gdzieś pomiędzy. Są chwile, kiedy sensowne jest wykonanie połączonej implementacji stosu. Są inne czasy, kiedy sensowniejsze jest użycie tablicy i pojedynczego „wskaźnika stosu”.