DOUG LLOYD: Więc w CS50, omówiliśmy wiele różnych struktur danych, dobrze? Widzieliśmy tablic i związane Wykazy i tabele mieszania, i stara, stosy i kolejki. Będziemy również dowiedzieć się trochę o drzewach i hałd, ale tak naprawdę to wszystko po prostu skończyć się jako wariacje na temat. Tam naprawdę są te rodzaj czterech podstawowych idei że wszystko jeszcze może sprowadzać się do. Tablice, związane listy, hash tabele i próbuje. I tak jak powiedziałem, są wariacje na ich temat, ale jest to dość dużo się dzieje na podsumowanie wszystko, co mamy zamiar rozmawiać o w tej klasie pod względem C Ale jak to wszystko miarą się, prawda? Mówiliśmy o plusy i minusy każdego w oddzielnych filmy z nimi, ale jest wiele numerów wyrzucenie wokół. Istnieje wiele ogólnie myśli wyrzucenie wokół. Spróbujmy i konsolidacji to w jednym miejscu. Miejmy ważyć argumenty przeciwko minusy, i rozważyć których struktura danych może być właściwym danych Struktura dla danej sytuacji, niezależnie od rodzaju danych, które przechowujemy. Nie koniecznie zawsze trzeba korzystać z super szybkie wstawienie, usunięcie, i wyszukiwanie z trie Jeśli naprawdę nie dbają o wstawianie i usuwanie za dużo. Jeśli musisz po prostu szybko losowo dostęp, może tablica jest lepiej. Więc destylować, że. Porozmawiajmy o każdym z czterech główne rodzaje struktur danych że rozmawialiśmy o, i po prostu zobaczyć, kiedy mogą być dobre, a gdy nie mogą one być tak dobrze. Więc zacznijmy z tablicami. Więc wstawiania, że ​​trochę źle. 

Wstawiania na końcu tablicy jest OK, jeśli budujemy tablicę jak idziemy. Ale jeśli trzeba wstawić elementów w środku, że powrót do wstawienia sortowanie, jest wiele przesunięcia, aby dopasować element tam. I tak, jeśli chcemy, aby wstawić wszędzie, ale do końca tablicy, to chyba nie tak wielki. 

Podobnie, usunięcie, jeśli nie jesteśmy usunięcie z końca tablicy, Prawdopodobnie również nie tak wielki, jeśli nie chcemy zostawić puste luki, które zwykle nie mamy. Chcemy, aby usunąć element, a to rodzaj zrobić to ponownie przyjemny. I tak usuwanie elementów z tablica, również nie jest tak wielka. 

Lookup, choć, jest wielki. Mamy swobodny dostęp, Stała czasu wyszukiwania. My po prostu powiedzieć, siedem, i idziemy do tablicy relokacji siedem. Mówimy, 20, z podróży do Tablica przeniesienie 20. Nie mamy do iteracji po drugiej. To dość dobre. 

Tablice są stosunkowo łatwe do sortowania. Za każdym razem, rozmawialiśmy o sortowaniu Algorytm, takie jak wybór rodzaju, Sortowanie przez wstawianie, sortowanie bąbelkowe, scalanie rodzaju, zawsze stosowane tablice to zrobić, bo tablice są dość łatwe do sortowania, w porównaniu do struktury danych widzieliśmy do tej pory. 

Są także stosunkowo niewielka. Nie ma dużo dodatkowej przestrzeni. Po prostu uchylenie dokładnie tyle jak trzeba trzymać swoje dane, i to dość dużo. Więc oni są bardzo małe i skuteczne w ten sposób. Ale inny minusem, choć, jest to, że są one ustalone rozmiary. Musimy zadeklarować dokładnie jak duża chcemy, aby nasza tablica będzie, a my tylko jeden strzał na niego. Nie możemy rosną i kurczą się. 

Jeśli musimy powiększać lub zmniejszać go, że trzeba zadeklarować zupełnie nową tablicę, skopiować wszystkie elementy z pierwsza tablica w drugiej tablicy. A jeśli przeliczył, że czas, musimy zrobić to ponownie. Nie tak świetne. Więc tablice nie dają nam elastyczność mieć zmienną liczbę elementów. 

Z połączonej listy, wstawiania jest całkiem proste. My po prostu przykleić na przednią. Skreślenie jest również bardzo proste. Musimy znaleźć elementy. Które wiążą się wyszukiwanie. 

Ale po znalezieniu elementu szukasz, wszystko co musisz zrobić, to zmienić wskaźnik, ewentualnie dwa, jeśli masz związane list-- podwójnie związane lista, rather-- a następnie można po prostu zwolnić węzeł. Nie musisz się zmieniać wszystko wokół. Po prostu zmienić dwa wskaźniki, więc to dość szybko. 

Lookup jest złe, choć, tak? Aby nas znaleźć elementem w połączonej listy, pojedynczo lub podwójnie związany, musimy szukać go liniowym. Musimy zacząć od początku i przenieść się do końca, albo zaczynają się od ruchu końcowego na początku. Nie mamy już swobodny dostęp. Więc jeśli robimy wiele poszukiwań, może połączonej listy nie jest aż tak dobre dla nas. 

Są również bardzo trudne do sortowania, prawda? Tylko w ten sposób można Naprawdę sortować połączonej listy znajduje się rozwiązać to jak skonstruować go. Ale jeśli rozwiązać to jak ty skonstruowanie go, nie jesteś już co więcej szybkich wstawki. Nie jesteś tylko sklejaniu rzeczy na froncie. Musisz znaleźć właściwym miejscu, aby umieścić go, i wówczas wstawiania staje się niemal tak źle jak wstawianie do tablicy. Więc związane listy nie są tak wielka, do sortowania danych. 

Są także bardzo mały, rozmiar mądry. Podwójnie związany nieco listy większe niż pojedynczo związane listy, które są nieco większe niż tablic, ale to nie jest ogromna ilość niewykorzystanego miejsca. Więc jeśli przestrzeń jest na wagę złota, ale Nie bardzo intensywne premii, to może być to właściwa droga. 

Hash tabele. Wstawiania w tabeli mieszania jest dość oczywiste. Jest to proces dwuetapowy. Najpierw musimy uruchomić nasze dane przez funkcja skrótu, aby uzyskać kod skrótu, a następnie wstawić element do tablica mieszająca w tym miejscu kod skrótu. 

Wykreślenie, podobny do połączonej listy, jest łatwe po znalezieniu elementu. Musisz go najpierw znaleźć, ale wtedy, gdy go usunąć, po prostu trzeba wymieniać kilka wskazówek, jeśli używasz oddzielnego łańcuchowym. Jeśli używasz sondowania, lub jeśli nie jesteś za pomocą łączenia w ogóle w tabeli mieszania, Skreślenie jest rzeczywiście bardzo proste. Wszystko, co musisz zrobić, to obliczenia skrótu Dane, a następnie udać się do tego miejsca. I zakładając, że nie mają żadnych kolizji, będziesz w stanie bardzo szybko usunąć. 

Teraz, wyszukiwanie jest gdzie rzeczy trochę bardziej skomplikowane. To średnio lepiej niż związane list. Jeśli używasz łańcuchowym, nadal masz połączonej listy, co oznacza, że ​​wciąż mają wyszukiwarka szkodą połączonej listy. Ale dlatego, że przyjmowanie połączone lista i dzielenie go na 100 lub 1000 lub n elementów w tabeli hash, jesteś Listy są powiązane z jednym n-te wielkości. Oni wszyscy są znacznie mniejsze. Masz n związane list zamiast jednej połączonej listy rozmiarze n. 

I tak to w świecie rzeczywistym stała Czynnikiem, który na ogół nie mówić o złożoności go w czasie, czy rzeczywiście zrobić tutaj różnicę. Więc wyszukiwania jest wciąż liniowa szukaj jeśli używasz łańcuchowym, jednak długość listy jesteś przeszukiwania Jest bardzo, bardzo krótki w porównaniu. Ponownie, jeśli sortowanie jest Twój Naszym celem, hash stołu prawdopodobnie nie właściwa droga. Wystarczy użyć tablicę, jeśli sortowania jest naprawdę ważne dla Ciebie. 

I mogą uruchomić gama rozmiarów. Trudno powiedzieć, czy tablica mieszająca jest małe czy duże, bo to zależy od tego, jak duży tabeli mieszania jest. Jeśli tylko będzie przechowywanie pięć elementów w tabeli mieszania, i masz tabeli mieszania z 10.000 elementów w nim, jesteś prawdopodobnie tracić dużo przestrzeni. Kontrast jest ci mogą również mają bardzo kompaktowe tabel mieszania, ale mniejsza tabela hash dostaje, dłuższy każda z tych połączonych list wystąpią. I tak naprawdę nie ma sposobu, aby zdefiniować dokładnie rozmiar tabeli mieszania, ale to chyba bezpieczne powiedzieć, że jest na ogół będzie większe niż związane Lista przechowywania tych samych danych, ale mniejszą niż trie. 

I stara się czwarty z tych struktur że rozmawialiśmy o. Wstawianie do trie jest złożona. Istnieje wiele dynamicznych alokacji pamięci, szczególnie na początku jak zaczynasz budować. Ale to stała czasowa. To tylko element ludzki tutaj sprawia, że ​​trudne. Mając na spotkanie z pustego wskaźnika, malloc przestrzeń, tam, ewentualnie malloc przestrzeń stamtąd ponownie. Rodzaj czynnika zastraszania wskaźniki w dynamicznej alokacji pamięci jest przeszkodą, aby wyczyścić. Ale gdy już straciła gola, wprowadzenie faktycznie jest dość prosty, i to na pewno jest stała czasowa. 

Skreślenie jest łatwe. Wszystko, co musisz zrobić, to przejdź w dół Kilka wskazówek i bezpłatnym węzła, więc to całkiem nieźle. Lookup jest również dość szybko. Opiera się tylko na długość danych. Więc jeśli wszystkie dane jest pięć ciągi znaków, na przykład, jesteś przechowywania pięć ciągi znaków w twojej trie, to tylko pięć kroków do znaleźć to, czego szukasz. Pięć jest tylko czynnikiem stałym, więc znowu, wstawianie, usuwanie i wyszukiwanie tutaj są stałe w czasie, skutecznie. 

Inną rzeczą jest to, że trie jest faktycznie niby już klasyfikowane, prawda? Na podstawie tego, jak jesteśmy wstawianie elementów, przechodząc litera po literze Klucz lub cyfra po cyfrze klucza, zwykle, twój trie kończy się rodzaj klasyfikowane jak go zbudować. Tak naprawdę nie robi sensu myśleć o sortowaniu w ten sam sposób myślimy o to z tablicami lub powiązanych list, lub tabele mieszania. Ale w pewnym sensie, twój trie jest klasyfikowane jak przejść. 

Wadą Oczywiście, jest to, że trie szybko staje się ogromna. Z każdego punktu połączenia, to polubisz have-- jeśli klucz składa się z cyfr, masz 10 Inne miejsca można przejść, które Oznacza to, że każdy węzeł zawiera informacje o danych, które chcesz przechowywać na tym węźle, plus 10 wskaźników. Które na CS50 IDE, jest 80 bajtów. Więc to co najmniej 80 bajtów każdy węzeł, aby tworzyć, i że nawet nie licząc danych. A jeśli węzły są litery zamiast cyfr, teraz masz 26 wskazówek z każdego miejsca. I 26 razy 8 jest chyba 200 bajtów, czy coś takiego. I masz kapitału i lowercase-- można zobaczyć, gdzie mam zamiar z tym, prawda? Węzły mogą się naprawdę duży, a więc trie Sam, ogólnie rzecz biorąc, można uzyskać naprawdę duże, zbyt. Więc jeśli przestrzeń jest na wysokim premii w systemie, trie może nie być właściwym sposobem przejść, chociaż jego inne zalety wchodzą w grę. Jestem Doug Lloyd. To CS50.