Teraz zastanawiamy się, jak wstawić węzeł (node) na środku naszej listy. Możemy przejrzeć listę, śledząc każdy element po kolei, porównując jego wartości, a także ostrożnie zmieniając wskaźniki next. David Malan czyni to bardziej realnym, używając „żywych” wolontariuszy.
Jakie są wady listy połączonej? W porównaniu z tablicami tracimy możliwość losowego dostępu… i możliwość wykorzystania efektywnego wyszukiwania binarnego. David pokazuje, jak to działa z listami połączonymi i wyjaśnia, jaki jest czas wyszukiwania w tej strukturze danych.
Wreszcie David zademonstruje ostatni przykład programu listy połączonej i dokładnie go wyjaśni.
Ten film jest kontynuacją wykładu Harvard CS50 z 5 tygodnia, poświęconego wskaźnikom i strukturom danych.
A co, jeśli nie będziemy dalej tworzyć jednowymiarowych struktur danych, takich jak tablice lub listy, które idą od lewej do prawej? Teraz nauczymy się nowych struktur danych, a pierwsze z nich nazywane są drzewami.
Drzewo jest trochę jak drzewo genealogiczne. Jest to hierarchiczna, dwuwymiarowa struktura z korzeniem, gałęziami i liśćmi.
Co by było, gdybyśmy stworzyli drzewo, które w pewnym sensie zbierze to, co najlepsze ze świata tablic i list połączonych? Możemy to zrobić i nazwać takie drzewo binarnym.
Dowiesz się również, jak zachować równowagę drzewa i jak używać go do wyszukiwania.
A co, jeśli istnieje struktura danych, która pozwala nam wstawić do niej węzeł (node) wykonując tylko jeden krok i również znaleźć coś wykonując jeden krok. Brzmi nieźle, jak coś w rodzaju Świętego Graala, prawda? Cóż, w jakiś sposób nim jest…
Jest znana jako tablica mieszająca (hash table) i… Oczywiście, są pewne pułapki.
Tablica mieszająca używa funkcji skrótu. Jest to bardzo szeroko stosowana struktura danych przeznaczona do różnych celów. Dowiemy się więc, jak działa, jak możemy z niej korzystać, a jak nie.
Jak prawidłowo utworzyć funkcję skrótu, unikając kolizji?
W ostatnim nagraniu wideo z wykładu z 5 tygodnia będziemy mówić o strukturze danych “trie” (drzewo trie). Trie wymawia się jak angielskie „try” i jest skrótem od angielskiego słowa „retrieval”.
Omówimy też konstrukcje wyższego poziomu, abstrakcyjne struktury danych, w których używamy naszych bloków konstrukcyjnych tablic, list połączonych, tablic mieszających i spróbujemy zaimplementować rozwiązanie jakiegoś problemu.
Na przykład jedną abstrakcyjną strukturą danych jest kolejka, w której chcemy mieć możliwość dodawania wartości i usuwania wartości na zasadzie first-in-first-out (FIFO). Aby dodać wartość, moglibyśmy umieścić ją w kolejce, a aby usunąć wartość, usunęlibyśmy ją z kolejki. Możemy dokonać implementacji za pomocą tablicy, której rozmiar zmieniamy, gdy dodajemy elementy, lub za pomocą listy połączonej, w której dodajemy wartości na końcu.
„Odwrotną” strukturą danych byłby stos (stack), w którym elementy ostatnio dodane (wypchnięte) są usuwane (wysuwane) jako pierwsze, na zasadzie last-in-first-out (LIFO). Nasza skrzynka odbiorcza to stos, w którym nasze najnowsze wiadomości e-mail znajdują się na górze.
Innym przykładem jest słownik, w którym możemy mapować klucze na wartości, lub ciągi znaków na wartości i możemy zaimplementować jeden do tablicy mieszającej, w której słowo zawiera inne informacje (takie jak jego definicja lub znaczenie).
GO TO FULL VERSION