[MUZYKA GRY]
GŁOŚNIK 1: W porządku.
Każdy, witamy z powrotem do sekcji.
Mam nadzieję, że wszyscy są z powodzeniem odzyskane z quizu
z ostatniego tygodnia.
Wiem, że to trochę szalony czasami.
Jak mówiłem wcześniej, jeśli jesteś w odchyleniu standardowym
tak naprawdę nie martw się o to, zwłaszcza, do mniej wygodne sekcji.
To o tym, gdzie powinieneś być.
>> Jeśli tak wielka, to niesamowite.
Kudos do Ciebie.
A jeśli czujesz się jak trzeba trochę więcej pomocy, proszę
prosimy, aby osiągnąć z któregokolwiek z TF.
Wszyscy jesteśmy tutaj, aby pomóc.
>> Dlatego uczymy.
Dlatego jestem tutaj, w każdy poniedziałek dla Ciebie chłopaki i w biurze godziny w czwartki.
Więc prosimy o poinformowanie mnie jeśli martwisz się o nic
lub czy jest coś na quiz że chcesz naprawdę chcesz rozwiązać.
>> Więc dzisiaj jest porządek o strukturach danych.
Niektóre z nich są po prostu będzie tylko aby Państwo zapoznali się z nich.
Nie możesz kiedykolwiek realizacji je w tej klasie.
Część z nich będzie, jak do ortografii Pset.
>> Będziesz miał wybór między tabelami z cebulą i prób.
Tak więc będziemy na pewno będzie nad tymi.
To będzie na pewno więcej od rodzaju odcinka wysokim poziomie obecnie, chociaż
ponieważ istnieje wiele z nich, a jeśli udaliśmy się w szczegóły implementacji
na wszystkie z nich, nie będzie nawet dotrzeć powiązanych list
i może trochę tabel hash.
>> Tak więc pokrywa się ze mną.
Nie będziemy robić Kodowanie to tak dużo czasu.
Jeśli masz jakieś pytania na ten temat lub chcesz zobaczyć, że realizowane
lub spróbować samemu, Zdecydowanie polecam
będzie study.cs50.net, które ma przykłady wszystkich.
To będzie mieć moje PowerPoints z pouczeniem, że
mają tendencję do używania, a także odrobiny programowania ćwiczenia, szczególnie na rzeczy
jak i binarnych powiązanych list drzewa stosy i kije.
Więc trochę więcej wysoki poziom, który może być ładne dla was.
>> Więc z tym, będziemy zacząć.
A także, yes-- quizy.
Myślę, że większość z was, którzy są w moja sekcja ma swoje quizy,
ale ktoś przychodzi lub jakiegoś powodu nie, oni są tutaj z przodu.
>> Tak połączone list.
Wiem, że tego rodzaju wykracza do tyłu przed quizu.
To było tydzień przed że dowiedzieliśmy się o tym.
Ale w tym przypadku, będziemy po prostu iść trochę bardziej w głębi.
>> Dlaczego więc możemy wybrać powiązane listę ponad tablicy?
Co je wyróżnia?
Tak?
>> Publiczność: Możesz poszerzyć związane listy w porównaniu stałej wielkości tablicy w.
GŁOŚNIK 1: Prawo.
Tablica ma stały rozmiar, podczas gdy powiązane lista ma zmienną wielkość.
Tak więc, jeśli nie wiemy, w jaki sposób bardzo chcemy przechowywać,
powiązane lista daje nam wielki sposobem, aby to zrobić, ponieważ możemy tylko
dodać na inny węzeł i dodać na inny węzeł i dodać na innym węźle.
Ale co może być kompromis?
Czy ktoś pamięta ten kompromis między tablicami i powiązanych list?
MMHMM?
>> PUBLICZNOŚCI: Musisz przejść przez całą drogę
dzięki połączonej listy znaleźć element na liście.
W tablicy, można tylko znaleźć element.
>> GŁOŚNIK 1: Prawo.
Więc z arrays--
>> PUBLICZNOŚCI: [niesłyszalne].
>> GŁOŚNIK 1: Z tablic, mamy co nazywa dostępie swobodnym.
Oznacza to, że jeśli chcemy, co jest kiedykolwiek piąty punkt z listy
lub piąty punkt naszego tablica, możemy po prostu chwyć ją.
Jeśli jest to związane lista mamy iterację, prawda?
Więc dostęp element w tablica jest stała czasowa,
natomiast z listy związane byłoby najprawdopodobniej dlatego, że być może w czasie liniowym
Nasz elementem jest cały sposób, na końcu.
Musimy przeszukać wszystko.
Tak więc wszystkie te dane Jedziemy struktury
należy poświęcić trochę więcej czasu, jakie są plusy i negatywy.
Kiedy możemy chcieć użyć jednej nad innymi?
I to jest rodzaj większe rzeczy zabrać.
>> Tak więc mamy tutaj Definicja węzła.
To tak, jakby jeden z elementów naszej listy, prawda?
Więc wszyscy jesteśmy zaznajomieni z naszych strukturach typedef,
którą przeszedł w przeglądzie ostatni raz.
To było w zasadzie tylko tworzenie inny typ danych, które możemy wykorzystać.
>> I w tym przypadku, to jakiś węzeł które odbędzie się w pewną liczbę całkowitą.
A potem co druga część tutaj?
Każdy, kto?
>> PUBLICZNOŚCI: [niesłyszalne].
>> 1 głośnik: Tak.
Jest to wskaźnik do następnego węzła.
Tak to powinno rzeczywiście być tutaj.
Jest to wskaźnik typu węzeł do następnej rzeczy.
I to jest to, co oni obejmuje nasz węzeł.
Fajne.
>> W porządku, więc w poszukiwaniu, jak my tylko, że przed strony, jeśli jesteś
zamiar przeszukać, trzeba rzeczywiście iteracji
za pośrednictwem połączonej listy.
Więc jeśli szukamy liczby 9, chcielibyśmy rozpocząć na naszej głowie
i wskazuje nam na początku z naszej listy, prawda?
I możemy powiedzieć, OK, robi to węzeł zawierać numer 9?
Nie?
>> Wszystko w porządku, przejdź do następnego.
Śledź go.
Czy zawiera numer 9?
Nie.
Śledź następny.
>> Musimy więc rzeczywiście iteracji za pośrednictwem naszej listy.
Nie możemy po prostu przejść bezpośrednio do miejsca, gdzie 9 jest.
A jeśli faceci rzeczywiście chcesz zobaczyć jakąś pseudo-kodu tam w górę.
Mamy tu jakąś funkcję wyszukiwania że bierze in-- co trwa w?
Co o tym sądzisz?
Tak łatwe.
Co to jest?
PUBLICZNOŚCI: [niesłyszalne].
GŁOŚNIK 1: liczba szukamy.
Prawda?
A co będzie to odpowiadać?
Jest to wskaźnik do?
>> Publiczność: węzeł.
>> GŁOŚNIK 1: węzeł do listy że patrzymy, prawda?
Mamy więc niektóre węzły są wskaźnikiem tutaj.
Jest to punkt, który zamierza faktycznie iterację naszej liście.
Stawiamy to równa listy dlatego, że jest po prostu
Ustawienie jest równa początek naszej listy.
>> I choć nie jest to NULL, natomiast wciąż mamy rzeczy w naszej liście,
sprawdzić, czy, że węzeł ma liczba szukamy.
Return true.
W przeciwnym razie, należy zaktualizować go, prawda?
>> Jeśli to jest NULL, zakończymy pętli while i return false
bo to oznacza, że ​​nie znalazłem.
Czy wszyscy się, jak to działa?
OK.
>> Więc z wstawiania, to trzy różne sposoby.
Możesz poprzedzić można dołączyć i można wstawić do dobrane.
W tym przypadku mamy zamiar zrobić prepend.
Czy ktoś wie jak te, trzy przypadki mogą się różnić?
>> Więc poprzedzić oznacza, że ​​można umieścić to z przodu listy.
Tak, oznaczałoby to, że bez względu na co węzeł jest, bez względu na
co wartość, będziesz umieścić go tutaj z przodu, OK?
To będzie pierwszy element listy.
>> Jeśli go dodać, to będzie aby przejść do tyłu listy.
I wstawić do dobrane oznacza, że ​​jesteś zamiar umieścić w miejscu, w rzeczywistości
gdzie utrzymuje powiązana lista posortowana.
Ponownie, jak korzystać tych, a podczas korzystania z
im będzie się różnić w zależności od przypadku.
Jeśli tak nie jest konieczne być sortowane, poprzedzić ma tendencję
za co większość ludzi używać, ponieważ nie
przejść przez całą listę znaleźć koniec dodać go, prawda?
Możesz po prostu trzymać go tuż.
>> Więc przechodzimy wstawiania 1 teraz.
Więc jedna rzecz, że będę Bardzo polecam tego Pset
jest zwrócenie rzeczy, jak zawsze.
To bardzo ważne, aby uaktualnić Twoje wskaźniki w odpowiedniej kolejności
bo jeśli ich aktualizacji nieco z celem,
masz zamiar skończyć utraty części listy.
>> Tak na przykład w tym przypadku mamy mówi tylko głowę do punktu 1.
Jeśli po prostu zrobić bez zapisywania to jedno,
nie mamy pojęcia, co 1 powinien wskazywać teraz
bo straciliśmy co Szef wskazał.
Więc jedna rzecz do zapamiętania kiedy robisz prepend
jest, aby zapisać to, co punktów, głowa do pierwszego
następnie ich przekazania, a następnie zaktualizować co twój nowy węzeł powinien wskazywać.
W tym przypadku, jest to jeden ze sposobów, aby to zrobić.
>> Jeśli więc zrobiłem to w ten sposób gdzie po prostu przeniesiony głowę,
tracimy zasadzie NASZEGO Cała lista, prawda?
Jednym ze sposobów, aby to zrobić jest mieć jeden punkt do obok, a następnie mają głowy do 1 punktu.
Lub możesz zrobić coś w rodzaju czasowego składowania, które mówiłem o.
>> Ale przesunięcia your wskaźniki w odpowiedniej kolejności
będzie bardzo, bardzo ważne dla tego Pset.
W przeciwnym razie będziemy mieć hash stół lub spróbować, że to tylko będzie
tylko część z tych słów, że chcą, a następnie you're-- MMHMM?
Publiczność: Co było tymczasowe rzeczą przechowywania ty mówisz?
GŁOŚNIK 1: czasowego składowania.
Więc w zasadzie inny sposób można to zrobić
jest przechowywać głowę czymś, jak przechowywać zmienną tymczasową.
Przypisać go na 1 i następnie zaktualizować jeden punkt
do tego, co szef używane do wskazać.
W ten sposób jest oczywiście bardziej elegancki, bo Ciebie
nie potrzebują wartość czasową, ale tylko oferując inny sposób, aby to zrobić.
I rzeczywiście mają jakiś kod do tego.
Więc dla połączonej listy, możemy rzeczywiście mają jakiś kod.
Wstaw tu tak, to jest poprzedzenie.
Więc to wchodzi to w głowie.
>> Tak więc pierwszą rzeczą, musisz utworzyć nowy węzeł, oczywiście,
i sprawdzić, NULL.
Zawsze dobre.
A następnie należy przypisać wartości.
Jeśli chcesz utworzyć nowy węzeł, ty nie wiem co to jest wskazując na następny,
więc chcesz zainicjować go na NULL.
Jeśli to nie kończy się wskazując na coś innego, to dostaje przeniesiony i jest w porządku.
Jeśli jest to pierwsza rzecz, na liście, to musi
zwrócić NULL, ponieważ to koniec listy.
>> Tak więc, aby go wstawić, widzimy tu przypisujemy następną wartość naszego węzła
za co głowa, czyli to, co mieliśmy tutaj.
To, co właśnie zrobił.
A potem mamy przypisując głowę do punktu do naszego nowego węzła, bo pamiętam,
Jest jakiś nowy wskaźnik do węzła, i to jest dokładnie to, co jest głowa.
Dlatego właśnie my strzałki mają ten akcesor.
Cool?
MMHMM?
>> Publiczność: Czy mamy do zainicjować Następny NULL pierwszy,
lub możemy po prostu zainicjować go do głowy?
>> GŁOŚNIK 1: Nowa obok musi być NULL rozpocząć
bo nie wiem gdzie to będzie.
Ponadto, jest to rodzaj podobnie jak paradygmat.
Ustawić go równa NULL tylko do się, że wszystkie zasady są objęte
zanim zrobisz tak, że żadnej zmiany przeznaczenia jesteś zawsze gwarantuje, że będzie
być skierowane do określonej wartości w porównaniu do wartości jak śmieci.
Ponieważ, tak, możemy przypisać Następny automatycznie,
ale to bardziej jak dobra praktyka, aby go zainicjować
w ten sposób, a następnie przypisać.
>> OK, więc teraz podwójnie związane list.
Co mamy na myśli?
Czym różni się podwójnie związane list?
>> Tak więc w naszych połączonych list, możemy poruszać się tylko w jednym kierunku, tak?
Mamy tylko obok.
Możemy tylko iść do przodu.
>> Z podwójnie połączonej listy, możemy również przejść do tyłu.
Mamy więc nie tylko numer, który chcemy zapisać,
mamy gdzie wskazuje na następny i gdzie po prostu wziął.
Więc to pozwala niektóre lepsze przechodzenie.
>> Więc podwójnie związane węzły, bardzo podobne, prawda?
Jedyną różnicą jest to teraz mieć następny i poprzedni.
To jedyna różnica.
>> Więc gdybyśmy poprzedzić lub append-- mamy nie mają na to żadnego kodu do here--
ale jeśli było spróbować włożyć, ważne
jest konieczne, aby się, że jesteś przypisywanie
zarówno poprzedniego i Twoich Następny wskaźnik prawidłowo.
Tak więc w tym przypadku będzie nie tylko zainicjować następne,
zainicjować poprzednia.
Jeśli jesteśmy na czele listy, możemy nie tylko aby głowa równa nowa,
ale nasza nowa poprzednia powinna wskazują na głowie, prawda?
>> To jedyna różnica.
A jeśli chcesz więcej praktyki z tych z list, z powiązanych wkładania,
z usunięciem, z wkładką w liście z bukietem,
proszę sprawdzić study.cs50.net.
Istnieje kilka wielkich ćwiczeń.
Gorąco polecam je.
Szkoda, że ​​nie miał czasu, aby przejść przez nich ale jest wiele struktur danych
do przejść.
>> OK, więc tabele mieszania.
Jest to prawdopodobnie najbardziej przydatne nieco za Pset
tutaj, bo masz zamiar być realizacji jednego z nich, lub spróbować.
Bardzo lubię tabel mieszania.
Są bardzo fajne.
>> Więc w zasadzie to, co dzieje tabeli mieszania
jest wtedy, gdy naprawdę potrzebują szybkiego wstawianie, usuwanie i wyszukiwanie.
To są rzeczy, które jesteśmy priorytetów w tabeli mieszania.
Mogą one uzyskać bardzo duże, ale jak zobaczymy z prób,
są rzeczy, które są znacznie większe.
>> Ale w zasadzie, wszystkie hash Stół jest funkcja skrótu
które mówi, że aby umieścić każde wiadro swoich danych, każdego z elementów.
Prosty sposób myśleć o tabeli mieszania jest to, że to tylko wiadra rzeczy,
prawda?
Więc jeśli są rzeczy, przez sortowanie jak pierwszej litery ich nazwy,
to trochę jak tabeli mieszania.
>> Więc gdybym grupy wy jest na grupy, kto zaczyna się nazywa
z tutaj, lub kto ma urodziny w styczniu, lutym, marcu,
cokolwiek, to skutecznie tworzenia tabeli mieszania.
To jest po prostu tworzenie wiadra, że można sortować elementy w
tak, że można je znaleźć łatwiej.
Więc ten sposób, gdy trzeba znaleźć jeden z was,
Nie muszę szukać przez każdego z nazwami.
Mogę być jak, och, wiem, że Danielle urodziny in--
Publiczność: --April.
GŁOŚNIK 1: Kwiecień.
Więc patrzę w moim kwietnia wiadro, a przy odrobinie szczęścia,
ona będzie tylko jeden tam i mój czas był stały w tym sensie,
natomiast jeśli mam szukać przez całą masę ludzi,
to będzie znacznie dłużej.
Stoły są tak naprawdę tylko hash wiadra.
Łatwy sposób, aby myśleć o nich.
>> Więc bardzo ważne rzeczą tabeli mieszania jest funkcja skrótu.
Więc rzeczy, po prostu mówił o, jak Twoja pierwsza litera twojego imienia
lub twój miesiącu urodziny, są to pomysły, które
bardzo korelują z funkcji skrótu.
To tylko sposób na podejmowaniu decyzji, które wiadro jesteś elementem idzie do, OK?
Więc dla tego Pset można patrzeć prawie każda funkcja skrótu chcesz.
>> Nie muszą być własne.
Istnieje kilka naprawdę fajne te się tam, że nie wszystkie rodzaje szalony matematyki.
A jeśli chcesz, aby Państwa sprawdzania pisowni super szybki,
Zdecydowanie zajrzeć do jednego z nich.
>> Ale są też najprostsze, jak obliczeniowych
Suma słowy, jak każda litera ma swój numer.
Obliczyć sumę.
Który określa wiadro.
Mają również łatwe te, które są jak wszystko jest tutaj,
wszystkie B jest tutaj.
Każdy z tych.
>> Zasadniczo, to po prostu mówi, które indeks tablicy twój element powinien wchodzić.
Tylko decydując bucket-- to wszystko jest funkcja skrótu jest.
Więc tutaj mamy przykład, który jest tylko pierwsza litera napisu
że właśnie chodzi.
>> Więc masz jakiś skrót, który jest po prostu Pierwsza litera twojego smyczkowy minus A,
które daje pewne liczba z zakresu od 0 do 25.
A to, co chcesz zrobić, to upewnij się, że jest to
wielkość swojej hash table-- ile wiader istnieją.
Wiele z nich Funkcje mieszania, są one
będzie powrót wartości, które mogłoby znacznie powyżej liczby wiader
że rzeczywiście mają w tabeli mieszania,
tak trzeba zrobić pewny i mod ci.
W przeciwnym razie, to będzie powiedzieć, oh, powinno być w wiaderku 5000
ale masz tylko 30 Wiadra w swojej tabeli mieszania.
Oczywiście, wszyscy wiemy, że to będzie prowadzić do pewnych szalonych błędów.
Więc upewnij się, że przez mod Wielkość tabeli mieszania.
Fajne.
Więc kolizji.
Czy każdy dobry do tej pory?
MMHMM?
>> Publiczność: dlaczego to powrót taki ogromny wartość?
>> SPEAKER 1: W zależności od wykorzystywanego algorytmu że funkcja skrótu używa.
Niektóre z nich zrobi szalony mnożenie.
I to wszystko o uzyskanie nawet dystrybucji,
więc zrobić kilka naprawdę szalone rzeczy czasami.
To wszystko.
Coś jeszcze?
OK.
>> Więc kolizji.
Zasadniczo, jak powiedziałem wcześniej, w najlepszym przypadku,
każdy wiadro patrzę w to będzie mieć jedno,
więc nie muszę patrzeć na wszystko, prawda?
I czy wiesz, że tam jest i to Nie, i to jest to, czego naprawdę chcą.
Ale jeśli mamy dziesiątki tysięcy punkty danych i mniej niż tego numeru
wiader, będziemy mieć gdzie w końcu coś kolizji
będzie miał do końca się w wiadro, że ma już elementu.
>> Więc pytanie, co robimy w tej sprawie?
Co robimy?
Mamy już coś tam?
Czy po prostu ją wyrzucić?
>> Nie.
Musimy mieć obu.
Tak więc sposób, że zazwyczaj zrobić to co?
Jaka jest struktura danych po prostu mówił o?
Publiczność: Związany lista.
GŁOŚNIK 1: powiązana lista.
Więc teraz, zamiast każdego z tych wiadra tylko o jeden element,
to będzie zawierać listę połączoną elementy, które zostały zakodowane w nim.
OK, nie każdy rodzaj się ten pomysł?
Dlatego, że nie może mieć tablicę dlatego, że nie wiem, jak wiele rzeczy,
będą tam.
Powiązane lista pozwala nam mamy tylko dokładną liczbę, która
są zakodowane w tym wiadrze, prawda?
>> Więc jest liniowa próbkowania w zasadzie to idea--
to jest jeden sposób, aby radzić sobie z kolizji.
Co możesz zrobić, to jeśli w tym Sprawa, Jagoda był mieszany w 1
i już mamy coś tam, po prostu
nie poddawać się, aż można znaleźć puste miejsce.
To jest jeden sposób, aby sobie z tym poradzić.
Innym sposobem, aby obsługiwać jest to z tym, co po prostu
called-- związane lista nazywa łańcuchowym.
>> Więc jeśli ten pomysł działa tabela mieszania myślisz
jest znacznie większe niż ustawić dane lub jeśli
chcesz spróbować zminimalizować łańcuchowym dopóki nie jest to absolutnie konieczne.
Więc jedno jest liniowe Oczywiście oznacza sondowania
że swojej funkcji skrótu nie jest tak użyteczne
bo masz zamiar skończyć się przy użyciu Twoja funkcja skrótu, dotarcie do punktu,
LINEAR można sondować do jakieś miejsce, które jest dostępne.
Ale teraz, oczywiście, nic inny, że kończy się tam,
będziesz musiał szukać jeszcze bardziej w dół.
>> I o wiele więcej Wyszukiwarka, że ​​koszty
idzie do wprowadzania elementu w hash tabeli teraz, prawda?
A teraz, gdy idziesz i spróbować znaleźć Jagoda znowu będziesz go mieszania,
i powie, Och, spójrz w wiadrze 1,
i nie będzie w wiadrze 1, więc jesteś
będzie musiał przemierzać przez reszty z nich.
Więc to jest czasami przydatne, ale w większości przypadków
mamy zamiar powiedzieć, że Łańcuch jest to, co chcesz zrobić.
>> Więc rozmawialiśmy o tym wcześniej.
Mam trochę przed siebie.
Ale to jest w zasadzie łańcuchowym każde wiadro w tabeli mieszania
związane jest tylko lista.
>> Tak inny sposób, lub bardziej techniczne sposób, aby myśleć o tabeli mieszania
jest to, że jest to po prostu tablica połączonych list, który
kiedy piszesz słownika i starasz się go załadować,
myśląc o tym, jak szereg powiązanych list
będzie o wiele łatwiej , aby zainicjować.
>> Publiczność: Tak tabeli mieszania ma ustaloną wielkość,
jak [niesłyszalne] wiader?
>> GŁOŚNIK 1: Prawo.
Więc ma określoną liczbę wiadra, że ​​determine--
które faceci powinni zapraszam do zabawy.
To może być całkiem fajne aby zobaczyć, co się dzieje,
jak zmienić ilość segmentów.
Ale tak, to ma ustawić kilka wiader.
Co pozwala na dopasowanie się wiele elementów, jak trzeba
Jest to osobny łańcuchowym, gdzie Listy zostały połączone w każdym segmencie.
To oznacza, że ​​stolik hash będzie dokładnie rozmiar
że trzeba go będzie, prawda?
To cały punkt połączonych listach.
Fajne.
>> Więc wszyscy tam w porządku?
Dobrze.
Ach.
Co się stało?
Naprawdę teraz.
Zgadnij, ktoś mnie zabija.
>> OK, mamy zamiar iść do próbuje, które są trochę szalony.
Lubię tabel mieszania.
Myślę, że są naprawdę fajne.
Próby są fajne, też.
>> Więc czy ktoś pamięta, co próba jest?
Powinien Pan się krótko w wykładzie?
Pamiętasz rodzaju, jak to działa?
Publiczność: Ja tylko kiwając że poszedł nad nim.
GŁOŚNIK 1: Mamy udać się nad nim.
OK, tak naprawdę pójdzie ponad to, co jest teraz mówimy.
>> PUBLICZNOŚCI: To na drzewa pobierania.
>> 1 głośnik: Tak.
To drzewo pobierania.
Niesamowite.
Więc jedno uwagi jest to, że patrząc na pojedynczych znaków
tutaj, prawda?
>> Więc zanim z naszej funkcji skrótu, możemy patrzyli na słowa jako całości,
i teraz szukamy więcej w postaci, prawda?
Mamy więc tutaj i Maxwell Mendel.
Więc w zasadzie try-- sposób myślenia o to, że każdy poziom tutaj
jest tablicą liter.
Więc to jest twój węzeł główny tutaj, prawda?
Ten ma wszystkie znaki alfabet na początku każdego słowa.
>> A to, co chcesz zrobić, to powiedzmy, OK, mamy pewne słowo M.
Idziemy szukać Maxwell, więc idziemy do M. A M punktów, aby cały
druga tablica, gdzie każdy Słowo dopóki
Jest to słowo, które ma w drugim liście,
tak długo, jak to słowo, które ma B jako drugi list,
będzie miał wskaźnik będzie jakiś następny tablicy.
>> Nie ma chyba Słowo, które MP coś,
więc w pozycji P w tym tablicy, to po prostu być NULL.
To znaczy, w porządku, nie ma ani słowa który M następnie P, OK?
Jeśli więc myślimy o nim, każdego jeden z tych mniejszych rzeczy
jest w rzeczywistości jednym z nich duże tablice od A do Z.
Więc co może być jedną z rzeczy, że to rodzaj zwrotu spróbować?
>> Publiczność: dużo pamięci.
>> GŁOŚNIK 1: Jest mnóstwo pamięci, prawda?
Każdy z tych bloków tutaj reprezentuje 26 miejsc, 26 element tablicy.
Więc próbuje się niezwykle przestrzeń ciężkie.
>> Ale są one bardzo szybko.
Tak niesamowicie szybko, ale naprawdę przestrzeń nieefektywne.
Rodzaju muszą zrozumieć się, co chcesz.
Są to naprawdę fajne dla Pset, ale one zajmują dużo pamięci,
więc kompromis.
Tak?
>> Publiczność: Czy byłoby możliwe skonfigurować, a następnie spróbuj
skoro masz wszystko Dane w nim, że need--
Nie wiem, czy to miałoby sens.
Byłem pozbycie się wszystkich NULL znaków, ale wtedy
nie będzie w stanie indeksować them--
>> GŁOŚNIK 1: nadal są potrzebne.
>> Odbiorcy: - w taki sam sposób za każdym razem.
1 głośnik: Tak.
Musisz się NULL znaków pozwolić wiesz, czy tam nie ma ani słowa.
Ben nie masz coś chcesz?
OK.
W porządku, więc jedziemy iść trochę więcej
do szczegółów technicznych za spróbować pracy na przykładzie.
>> OK, więc to jest to samo.
Podczas gdy w połączonej listy, naszym głównym rodzaj of-- co to słowo chcę? -
jak budulcem był węzeł.
W próbie, mamy także węzeł, ale nie jest to zdefiniowane inaczej.
>> Więc mamy trochę bool, że reprezentuje, czy rzeczywiście słowa
istnieje w tej lokalizacji, a następnie mamy trochę tablicę here-- a raczej
jest to wskaźnik do Tablica z 27 znaków.
A to za, w tym przypadku jest 27-- Jestem pewien, że wszyscy z was są jak, poczekaj,
jest 26 liter w alfabecie.
Dlaczego mamy 27?
>> Tak więc w zależności od sposób realizacji tego,
jest to, że ze zbior pozwoliło na apostrofy.
Więc dlatego dodatkowy jeden.
Będziesz mieć również w niektórych przypadki terminatora null
jest ujęte jako jeden z znaków, że to jest dozwolone,
i to w jaki sposób sprawdzić, zobaczyć, czy to koniec słowa.
Jeśli jesteś zainteresowany, sprawdź Film Kevina na study.cs50,
jak Wikipedia ma kilka dobrych zasobów tam.
>> Ale mamy zamiar przejść po prostu rodzaj w jaki sposób można pracować przez try
Jeśli dostaniesz jeden.
Tak więc mamy tu bardzo proste, że jeden ma słowa "nietoperz" i "zoom" w nich.
I jak widzimy tutaj, to mało tu miejsca
bool, który reprezentuje naszą mówi: tak, to jest słowo.
I wtedy to ma nasze tablice znaków, prawda?
>> Więc mamy zamiar przejść przez znalezienie "bat" w tej próbie.
Tak rozpoczyna się na górze, prawda?
I wiemy, że b odpowiada drugi indeks, drugi element
w tej tablicy, gdyż b.
Więc ok drugi.
>> I mówi, OK, fajnie, że się przestrzegać obok tablicy, bo jeśli pamiętamy,
nie jest to, że każdy z nich faktycznie zawiera element.
Każda z tych tablic zawiera wskaźnik, prawda?
To ważne rozróżnienie zrobić.
>> Wiem, że to ma być: próbuje się naprawdę trudno dostać się na po raz pierwszy,
tak więc nawet jeżeli jest to drugim lub trzecim razem
i to jeszcze rodzaj z pozornie trudne,
Obiecuję, że jeśli się zegarek krótki jutro,
to prawdopodobnie zrobić dużo więcej sensu.
To zajmuje dużo do strawienia.
I jeszcze czasami jestem jak, czekaj, co jest spróbować?
Jak tego używać?
>> Mamy więc b, w tym przypadku, który jest nasz drugi wskaźnik.
Jeśli mieliśmy, powiedzmy, c lub d lub inny list
musimy map, że z powrotem do indeksu nasz wybór że odpowiada.
Więc bierzemy jak rchar i po prostu odjąć od mapować go do 0 do 25.
Wszyscy dobrze jak my map naszych bohaterów?
OK.
>> Więc idziemy do drugiego i my zobaczyć, że tak, to nie jest NULL.
Możemy przejść do tej następnej tablicy.
Więc idziemy do tej kolejnej tablicy tutaj.
>> I możemy powiedzieć, OK, teraz jesteśmy należy sprawdzić, czy jest tutaj.
Jest zerowy lub robi to rzeczywiście iść do przodu?
Więc rzeczywiście porusza przekazania w tej tablicy.
I możemy powiedzieć, OK, t jest nasz ostatni list.
Więc idziemy do t w indeksie.
A potem ruszyć do przodu ponieważ jest jeszcze jeden.
A ten mówi, w zasadzie, że tak, mówi, że nie jest to słowo here--
że jeśli się to Ścieżka, po przyjeździe,
na słowa, które wiemy, jest "bat".
Tak?
>> PUBLICZNOŚCI: Czy to, że mają standardowe w indeksie 0, a potem mieć na jeden rodzaj
lub mieć na końcu?
>> 1 głośnik: Nie
Więc jeśli spojrzymy na nasze Deklaracja tutaj, to bool,
więc własny element węzła.
Więc nie jest to część tablicy.
Fajne.
Więc kiedy skończymy nasze słowo i jesteśmy w tej tablicy, co chcemy zrobić
jest to czek na to słowo.
I w tym przypadku, to wrócić tak.
>> Więc na tej notatce, wiemy, że "zoo" - wiemy, jak ludzie, że "zoo" to słowo,
prawda?
Ale są tu by spróbować powiedzieć, nie, to nie.
A to znaczy, że dlatego, że nie oznaczono go jako słowa tutaj.
Mimo, że możemy przechodzić dzięki tej tablicy,
to próba powiedziałbym, że nie, z oo nie jest w słowniku
dlatego, że nie mają oznaczono go jako taki.
>> Więc jeden sposób that-- och, przepraszam, ten.
Tak więc w tym przypadku, "oo" nie jest słowo, ale to jest w naszej próbie.
Ale w tym jednym, że chcemy go wprowadzenia słowa "kąpiel", co się dzieje,
jest kierujemy through-- B, A, t.
Jesteśmy w tej tablicy, i idziemy szukać godz.
>> W tym przypadku, gdy spojrzeć na wskaźnik na h,
to wskazuje na NULL, OK?
Więc jeśli nie jest to wyraźnie wskazuje na inny tablicy
można zakładać, że wszystkie wskaźniki w tej tablicy wskazują na null.
Tak więc w tym przypadku h wskazuje null, więc nie możemy nic zrobić,
więc to również powrót fałszywe, "kąpiel" nie jest tutaj.
Więc teraz jesteśmy naprawdę zamiar przejść przez
jak byśmy rzeczywiście powiedzieć że "zoo" jest w naszej próbie.
Jak wstawić "zoo" w naszej próbie?
Tak więc w taki sam sposób, że rozpoczęła się z naszej listy, zaczynamy u podstaw.
W przypadku wątpliwości, zaczynają się Korzeń z tych rzeczy.
>> A my powiedzieć, OK, z.
z istnieje w tym, i to robi.
Więc jesteś w ruchu na następnym tablica, OK?
A następnie na następnego, powiedzieć, OK, nie o istnieje?
To nie.
To ponownie.
>> I tak na naszej następnej, już powiedzieliśmy, OK, "zoo" już istnieje tutaj.
Wszystko, co musimy zrobić, to ustawić to równe z prawdą, że nie ma tam ani słowa.
Jeśli wszystko się po nawet przed tym punkcie,
to słowo, tak po prostu ustawiony jest równa np.
Tak?
>> Publiczność: Tak to robi oznacza to, że "ba", to słowo również?
>> 1 głośnik: Nie
Więc w tym przypadku, "ba", że dostanie tu, by powiedzieć, jest to słowo,
i to nadal nie ma.
OK?
MMHMM?
>> Publiczność: Więc kiedy jest to Słowo i mówisz tak, to
zawierać będzie udać się do m?
>> GŁOŚNIK 1: Więc to ma with-- masz ładowania to w.
Mówisz "zoo" jest słowo.
Gdy idziesz do check-- jak, że chcesz powiedzieć,
oznacza "zoo" istnieje w tym słowniku?
Jesteś tylko będzie szukać "zoo" a następnie sprawdzić, czy jest to słowo.
Nigdy nie będziemy poruszać aż do m, ponieważ to nie jest
czego szukasz.
>> Jeśli więc rzeczywiście chciał dodać "kąpiel" w tej próbie,
chcemy zrobić to samo jak my z "zoo"
chyba że widzimy, że kiedy spróbować i dostać się do godziny, to nie istnieje.
Tak więc można myśleć o tym, jak stara aby dodać nowy węzeł w połączonej listy,
więc musimy dodać kolejny jedna z tych tablic, jak tak.
A potem, co robimy jest po prostu ustawić godzinę elementem tej tablicy wskazując na to.
>> A potem to, co chcemy zrobić tutaj?
Dodaj jest równe true bo to słowo.
Fajne.
Wiem.
Próby nie są najbardziej ekscytujące.
Zaufaj mi, wiem.
>> Więc jedna rzecz do zrealizowania z prób, Powiedziałem, że są bardzo skuteczne.
Więc oni widzieliśmy zajmują mnóstwo miejsca.
Oni rodzaj mylące.
Więc dlaczego kiedykolwiek użyć tych?
Korzystamy z nich, ponieważ są one niezwykle wydajne.
>> Więc jeśli kiedykolwiek patrzy się słowa, jesteś tylko
ograniczona jest przez długość słowa.
Więc jeśli szukasz Słowo to jest o długości od pięciu,
jesteś tylko kiedykolwiek będzie musiał wykonanie w większości pięciu porównań, OK?
Więc to sprawia, że ​​w zasadzie stała.
Jak wkładanie i odnośnika są w zasadzie stała czasowa.
>> Więc jeśli można kiedykolwiek coś w stałym czasie,
że jest tak dobry jak on.
Nie można się lepiej niż Stała czasowa dla tych rzeczy.
Tak, że jeden z ogromne plusy prób.
>> Ale jest dużo miejsca.
Więc niby zdecydować, co jest dla ciebie ważniejsze.
I na współczesnych komputerach, przestrzeń, która może trwać try
być może nie ma wpływu można, że ​​dużo, ale może
masz do czynienia z czymś, że ma wiele, wiele więcej rzeczy,
i spróbować po prostu nie jest to uzasadnione.
Tak?
>> Publiczność: Czekaj, więc masz 26 Litery w każdy jeden?
>> GŁOŚNIK 1: MMHMM.
Tak, masz 26.
Masz jakiś jest słowo, a następnie znacznik masz 26 wskaźników w każdego.
A oni point--
>> Grupa docelowa: I co 26, oni mają po 26?
>> 1 głośnik: Tak.
I dlatego, jak można zobaczyć, dość szybko powiększa.
Dobrze.
Więc mamy zamiar dostać się do drzew, które Czuję się jak jest łatwiejsze i prawdopodobnie
być miły mały wytchnienie z prób nie.
Więc mam nadzieję, że większość z was widziałem drzewo przed.
Nie jak dość te, które ja na zewnątrz
nie wiem, czy ktoś udał się na zewnątrz niedawno.
Poszedłem jabłko zbierając w ten weekend, i O mój Boże, to było piękne.
Nie wiedziałem, liści może wyglądać, że ładna.
>> Więc jest to tylko drzewo, prawda?
To tylko niektóre węzeł, i to wskazuje na kilka innych węzłów.
Jak widać tutaj, to jest rodzaju powracającym tematem.
Węzły skierowana jest rodzajem węzłów Istotą wielu struktur danych.
To po prostu zależy od tego, jak wskazać je wzajemnie
i jak przechodzić przez nich i jak
wkładać rzeczy, które określa ich różne cechy.
>> Więc po prostu trochę terminologii, którego użyłem wcześniej.
Więc to, co jest korzeniem na samym szczycie.
to gdzie zawsze zacząć.
Możesz myśleć o tym jako szef również.
Ale dla drzew, mamy tendencję do odnoszą się do niego jako administrator.
>> Wszystko na dole here-- w bardzo, bardzo bottom--
są uważane liście.
Więc to idzie w parze z Całe drzewo rzecz, prawda?
Liście na brzegach drzewa.
>> A potem mamy także kilka Terminy mówić o węzłach w stosunku
do siebie.
Mamy więc rodziców, dzieci i rodzeństwo.
Tak więc w tym przypadku, 3 Rodzic z 5, 6 i 7.
Więc to, co jest rodzic jeden krok wyżej, co masz
odnosząc się do, tak po prostu jak drzewo genealogiczne.
Miejmy nadzieję, że to wszystko jest trochę nieco bardziej intuicyjny niż stara.
>> Rodzeństwo są te, które mają sam rodzic, prawda?
Są na tym samym poziomie, tutaj.
A potem, jak ja mówiąc, dzieci są po prostu
co jest o krok niżej węzeł w pytaniu, OK?
Fajne.
Tak drzewo binarne.
Czy ktoś może zaryzykować na jednym z charakterystyka drzewa binarnego?
>> Publiczność: Max dwa liście.
>> GŁOŚNIK 1: Prawo.
Więc max dwóch liści.
Więc w tym jeden przed, mieliśmy ten jeden który miał trzy, ale w binarnym drzewie
masz maksymalnie dwóch dzieci na rodziców, prawda?
Jest jeszcze jedna ciekawa cecha.
Czy ktoś wie?
Drzewo binarne.
>> Więc binarne drzewo będzie mieć wszystko na the-- to nie jest sorted--
ale w posortowanej drzewa binarnego, wszystko na prawo
jest większa niż rodzic a wszystko z lewej
jest mniejsza niż rodzic.
I to jest quiz pytanie wcześniej, więc dobrze wiedzieć.
Więc ten sposób możemy określić, znowu mamy kolejny węzeł.
To wygląda bardzo podobnie do tego, co?
Podwójnie
>> Publiczność: Linked list
>> GŁOŚNIK 1: podwójne lista powiązana, prawda?
Jeśli więc zastąpić to z poprzednim i następnym,
to będzie podwójnie związany lista.
Jednak w tym przypadku, w rzeczywistości mają prawo i lewo i to wszystko.
W przeciwnym razie, jest to dokładnie to samo.
Mamy jeszcze element szukasz,
i po prostu mieć dwa wskaźniki będzie co będzie dalej.
Tak, tak, drzewo binarne wyszukiwania.
Jeśli zauważymy, wszystko na tutaj jest większa than--
czy wszystko od razu się tutaj
jest większa niż wszystko, tutaj jest mniejsza.
>> Więc gdybyśmy przeszukiwać, to powinien wyglądać bardzo blisko wyszukiwania binarnego
tutaj, prawda?
Chyba zamiast szukać na pół tablicy,
jesteśmy po prostu patrząc na obu lewo strona lub prawej stronie drzewa.
Tak robi się trochę prostsze, myślę.
>> Więc jeśli korzeń jest NULL, oczywiście to tylko fałszywe.
A jeśli to nie, oczywiście, że to prawda.
Jeśli jest mniej niż, szukamy lewego.
Jeśli jest większy niż, szukamy prawo.
Jest dokładnie tak, jak wyszukiwanie binarne, tylko inna struktura danych
że używamy.
Zamiast tablicy to tylko binarne drzewo.
>> OK, stosy.
A także, że wygląda jak my może mieć trochę czasu.
Jeśli to zrobimy, jestem szczęśliwy, aby przejść nad żadnym z tego ponownie.
OK, więc stosy.
Czy ktoś pamięta co stacks-- wszelkie cechy stosie?
>> OK, więc większość z nas, jak sądzę, jeść w restauracji halls--
tak samo jak nie może jak.
Ale oczywiście, można myśleć stos dosłownie jako stos tacek
lub stos rzeczy.
I co ważne, zdać sobie sprawę, że jest to
something-- charakterystyczne że nazywamy to by-- jest LIFO.
Czy ktoś wie, co to oznacza?
MMHMM?
>> PUBLICZNOŚCI: ostatnie weszło, pierwsze wyszło.
>> GŁOŚNIK 1: Prawo, trwać, pierwsze wyszło.
Więc jeśli wiemy, czy mamy do układania rzeczy się, najłatwiej złapać off--
i być może jedyną rzeczą, możemy chwycić się, czy nasz stos jest duży enough--
jest to, że górny element.
Więc co było umieścić na last-- jak widzimy tutaj,
co został zepchnięty Jest on najbardziej recently--
Będzie pierwszy rzeczą, która nam zasnąć, dobrze?
>> Tak więc to, co mamy tutaj jest inna struktura typedef.
To jest naprawdę tak jak Crash Course w strukturze danych,
tak jest dużo rzucone na was.
Wiem.
Więc kolejna struktura.
Yay dla struktur.
>> I w tym przypadku, jest to jakiś wskaźnik do tablicy, która ma pewne możliwości.
Więc to reprezentuje nasz stos tutaj, jak nasz rzeczywisty tablicy
że trzyma nasze elementy.
A potem mamy tutaj pewną wielkość.
>> I zazwyczaj, chcesz zachować utwór jak duży stos jest
bo to, co się dzieje, aby umożliwić można zrobić to, jeśli wiesz, rozmiar,
pozwala powiedzieć, OK, jestem w mocy?
Czy mogę dodać coś więcej?
I to też mówi, gdzie górna część swojego stosu
jest tak, że wiesz co może faktycznie zdjąć.
I to rzeczywiście będzie być trochę bardziej jasne tutaj.
>> Więc dla naciśnięciem, jednej rzeczy, jeśli Ciebie kiedykolwiek wdrożyć pchania,
jak mi tylko powiedzieć, twój Stos ma ograniczony rozmiar, prawda?
Nasza tablica miał jakieś zdolności.
Jest to tablica.
Jest stałym rozmiarze, więc musimy upewnić się, że nie jesteśmy oddanie więcej
na naszej tablicy, niż rzeczywiście mają miejsca na.
>> Więc podczas tworzenia push Funkcja, pierwszą rzeczą zrobić, to powiedzieć, OK,
mam miejsce w moim stosie?
Bo jeśli nie, przepraszam, Nie mogę zapisać element.
Jeśli to zrobię, to chcesz zapisać ono w górnej części komina, tak?
>> I dlatego mamy śledzić swojej wielkości.
Jeśli nie śledzić naszej wielkości, nie wiemy, gdzie go umieścić.
Nie wiemy, jak wiele rzeczy, Już są w naszej tablicy.
Jak oczywiście istnieją sposoby że może można to zrobić.
Można zainicjować wszystko NULL a następnie sprawdzić najnowsze NULL,
ale o wiele łatwiej jest to po prostu powiedzieć, OK, śledzić wielkości.
Jak wiem, że mam cztery elementy w mojej tablicy, więc następna rzecz
że stawiamy na, jesteśmy zamiar przechowywać w indeksie 4.
A następnie, oczywiście oznacza to, że pomyślnym pchnął coś
na swoim stosie, to chcą zwiększyć rozmiar
tak, że wiesz, gdzie jesteś tak że można wcisnąć więcej rzeczy.
>> Więc jeśli staramy się pop coś ze stosu,
co może być pierwszą rzeczą, że chcemy sprawdzić?
Starasz się wziąć coś się swojego stosu.
Czy jesteś pewien, że coś w stosie?
Nie.
Więc co możemy chcieć sprawdzić?
>> PUBLICZNOŚCI: [niesłyszalne].
GŁOŚNIK 1: Sprawdź rozmiar?
Rozmiar.
Dlatego chcemy, aby sprawdzić, czy nasza wielkość jest większa niż 0, OK?
A jeśli tak jest, to chcemy, aby zmniejszyć nasz rozmiar o 0 i wrócić tego.
Dlaczego?
>> W pierwszym my popychanie, że go popchnął
na wielkość i następnie zaktualizowane wielkości.
W tym przypadku mamy do zmniejszanie rozmiaru a następnie biorąc go, wyrywanie go
z naszej tablicy.
Dlaczego możemy zrobić?
Więc jeśli mam jedną rzecz na moim stosie, jaki byłby mój rozmiar w tym momencie?
1.
>> A gdzie jest elementem 1 przechowywane?
Na co wskaźnik?
Publiczność: 0.
GŁOŚNIK 1: 0.
Tak więc w tym przypadku zawsze trzeba zrobić sure--
zamiast wrócić wielkość minus 1, bo
wiemy, że nasz element ma będzie przechowywany w jeden mniej
co nasza wielkość jest to po prostu dba o niego.
Jest to nieco bardziej elegancki sposób.
A my po prostu zmniejszyć NASZEGO rozmiar, a następnie powrót rozmiar.
MMHMM?
>> Publiczność: Chyba po prostu w ogóle, dlaczego to struktura danych
być korzystne?
>> GŁOŚNIK 1: To zależy od kontekstu.
Tak więc dla niektórych z teorią jeśli pracujesz with-- OK,
pozwól mi sprawdzić, czy jest korzystne jeden jest to bardziej korzystne niż na zewnątrz
CS.
W stosy, za każdym razem trzeba śledzić coś,
jest ostatnio dodany jest, gdy masz zamiar użyć stosu.
>> I nie mogę myśleć o dobru Przykładem, że teraz.
Ale gdy ostatnie co jest najważniejsze dla ciebie,
to kiedy stos będzie przydatna.
Staram się, że jeśli nie jest dobry do tego.
Jeśli myślę o dobry przykład w następny 20 minut na pewno powiedzieć.
>> Ale ogólnie rzecz biorąc, czy jest coś, jak powiedziałem najbardziej, gdzie ostatnie
najważniejsze, że jest gdzie stos wchodzi w grę.
Podczas gdy kolejki są trochę odwrotnie.
I wszystkie małe psy.
Czy to nie wspaniałe, prawda?
Czuję, że powinienem Wystarczy króliczka wideo
w samym środku sekcja dla was
ponieważ jest to intensywny odcinek.
>> Więc kolejka.
Zasadniczo jest jak kolejka linii.
Chłopaki jestem pewien, że stosowanie tego codziennie, tak jak w naszych salach jadalnych.
Więc musimy iść w i dostać nasze tace, jestem
czy masz czekać w kolejce aby przesunąć lub dostać się do jedzenia.
>> Więc różnica tutaj jest to, że jest to FIFO.
Więc jeśli LIFO był ostatnio w pierwszy się, FIFO jest pierwszy, pierwsze wyszło.
Tak to jest, gdy cokolwiek umieścić na pierwszy jest najbardziej istotne.
Więc jeśli czekali w line-- można
Wyobraźcie sobie, że udał się do przejdź się nowy iPhone
i to, gdy stos Ostatnia osoba w kolejce dostał pierwszy,
ludzie zabijają się nawzajem.
>> Więc FIFO, wszyscy jesteśmy bardzo znane się w świecie rzeczywistym tutaj,
i to wszystko ma do czynienia z rzeczywiście rodzaj odtworzyć całą tę linię
i kolejkowanie strukturę.
Tak więc podczas gdy w stosie, mamy impuls i pop.
Z kolejce, mamy enqueue i usunie.
Więc w zasadzie oznacza enqueue umieścić go na plecy,
i usunie z niej środki podjąć off od przodu.
Więc nasza struktura danych jest trochę bardziej skomplikowane.
Mamy drugą rzeczą do śledzenia.
>> Więc bez głowy, to jest dokładnie stos, prawda?
To jest taka sama struktura postaci stosu.
Jedyne co teraz jest to inna mają tę głowę, co to, co myślisz
zamierza śledzić?
>> Publiczność: pierwszy.
>> GŁOŚNIK 1: Prawo, Pierwszą rzeczą, którą możemy umieścić w.
Szef naszej kolejki.
Kto jest pierwszy w kolejce.
W porządku, więc jeśli zrobimy Kolejkuj.
Ponownie, z dowolnym te struktury danych,
ponieważ mamy do czynienia z tablicy, musimy sprawdzić, czy mamy miejsca.
>> To jest trochę jak mi mówią wy, jeśli otworzysz plik,
trzeba sprawdzić, null.
W każdym z tych stosów i kolejki, trzeba
aby sprawdzić, czy nie ma miejsca, bo jesteśmy do czynienia ze stałą tablicy wielkości,
jak widzimy here-- 0, 1 wszystko do 5.
Więc co możemy zrobić w tym przypadku jest kontrola aby sprawdzić, czy mamy jeszcze miejsca.
Jest mniejsza niż rozmiar naszej mocy?
>> Jeśli tak, musimy przechowywać go w ogon i aktualizujemy naszą wielkość.
Więc co może być ogonem w tym przypadku?
To nie jest wyraźnie zapisana.
Jak będziemy przechowywać go?
Co ogon będzie?
>> Warto więc przejść przez ten przykład.
Więc to jest tablica wielkości 6, prawda?
I mamy teraz nasz rozmiar jest 5.
A kiedy go umieścić w, to będzie , aby przejść do piątego indeksu, prawda?
Więc przechowywać w ogonie.
>> Innym sposobem byłoby po prostu napisać ogon Tablica w naszym indeksie wielkości, prawda?
Jest to rozmiar 5.
Następna rzecz pójdzie do 5.
Cool?
OK.
To staje się nieco bardziej skomplikowana, kiedy zaczynamy bawić się z głową.
Tak?
>> Publiczność: Czy to oznacza, że ​​mamy byłby uznany tablicę
była długa i pięć elementów Następnie dodajemy na nią?
>> 1 głośnik: Nie
Tak więc w tym przypadku jest to stosu.
To być zadeklarowane jako tablica wielkości 6.
I w tym przypadku mamy Wystarczy jedno miejsce w lewo.
>> OK, więc jedno jest w tym przypadku, jeśli nasz szef jest na 0,
następnie po prostu je dodać w rozmiarze.
Ale robi się trochę trudniejsze bo rzeczywiście, oni
nie ma slajdów za to, więc idę
wyciągnąć jeden, bo to nie jest dość, że proste, gdy Ciebie
rozpocznie pozbyciu rzeczy.
Tak więc, podczas gdy w stos tylko kiedykolwiek
martwić się o to, co rozmiar jest podczas dodawania coś na,
w kolejce trzeba także dokonać pewność, że twoja głowa jest rozliczane,
bo fajna rzecz o kolejkach jest to, że jeśli nie jesteś w mocy,
rzeczywiście można uczynić go otaczają.
>> OK, więc jeden thing-- oh, to jest straszne kreda.
Jedną rzeczą do rozważenia jest.
Będziemy po prostu zrób pięć.
OK, więc mamy zamiar powiedzieć głowa jest tutaj.
Ten ma wartość 0, 1, 2, 3, 4.
>> Głowa tam, i proszę mieć rzeczy w nich.
I chcemy dodać coś, prawda?
Więc rzeczą, że musimy wiedzieć, jest to, że szef jest zawsze
będzie się poruszać w ten sposób i następnie zawrócić się, OK?
>> Więc ta kolejka ma miejsce, prawda?
Ma miejsce na początku rodzaju przeciwieństwo tego.
Więc to, co musimy zrobić, to my trzeba obliczyć ogon.
Jeśli wiesz, że Szef nie przeniósł, ogon
jest tylko w macierzy Wskaźnik wielkości.
>> Ale w rzeczywistości, jeśli używasz kolejkę, Twoja głowa jest prawdopodobnie aktualizowany.
Więc co trzeba zrobić, to właściwie obliczyć ogon.
Więc co możemy zrobić, to ta formuła tu, które mam zamiar dać wam
Chłopaki myśleć, i wtedy będziemy o tym rozmawiać.
Więc to jest pojemność.
>> Więc to będzie w rzeczywistości dać sposób to zrobić.
Ponieważ w tym przypadku co?
Nasz szef jest w stanie 1, nasz rozmiar wynosi 4.
Jeśli mod, który przez 5, otrzymujemy 0, czyli tam, gdzie powinniśmy wejście to.
>> Tak więc w następnym przypadku gdybyśmy mieli to zrobić,
powiedzieć, OK, niech usunie z niej coś.
Mamy z kolejki to.
Bierzemy się ten element, prawda?
>> A teraz nasza głowa jest skierowana tutaj, i chcemy dodać w innej rzeczy.
Jest to w zasadzie z powrotem z naszej linii, prawda?
Kolejki mogą owinąć się wokół tablicy.
To jedna z głównych różnic.
Stosy, nie możesz tego zrobić.
>> Z kolejki, można bo wszystko, co się liczy
jest to, że wiesz, co został ostatnio dodany.
Skoro wszystko ma być dodany w Ten kierunek w lewo, w tym przypadku,
a następnie owinąć wokół, można nadal wprowadzenie nowych elementów
w przedniej części tablicy bo to naprawdę nie jest
Przód tablicy już.
Można myśleć o początku Tablica jak gdzie twoja głowa jest w rzeczywistości.
>> Tak to jest, jak formuła obliczyć swój ogon.
Czy to ma sens?
OK.
OK, usunie z niej, a następnie macie 10 minut
zadać mi jakieś pytania wyjaśnienia chcesz, bo wiem, że jest szalony.
>> W porządku, więc w tym samym way-- Nie wiem, czy wy zauważyliście,
ale CS jest o wzory.
Rzeczy są bardzo samo, tylko z drobnymi ulepszeniami.
Tak samo tutaj.
Musimy sprawdzić, czy rzeczywiście coś w naszym kolejce, prawda?
Powiedzieć, OK, to nasz rozmiar większy niż 0?
Fajne.
>> Jeśli nie, to możemy przenieść naszą głowę, co jest to, co ja po prostu wykazać tutaj.
Aktualizujemy naszą głowę za jeden więcej.
A potem zmniejszać nasze Wielkość i powrócić element.
>> Jest o wiele bardziej konkretne Kod na study.cs50.net,
a ja bardzo polecam przez to, jeśli masz czas,
nawet jeśli jest to tylko pseudo-kod.
A jeśli chcecie rozmawiać przez że ze mną jeden na jednego, poinformuj mnie
wiem.
Byłbym szczęśliwy.
Struktury danych, jeśli wziąć CS 124, będziesz
wiem, że bardzo się struktury danych zabawy i to jest dopiero początek.
>> Tak wiem, że to trudne.
Jest OK.
Zmagamy.
I jeszcze zrobić.
Więc nie martw się zbytnio o tym.
>> Ale to jest w zasadzie your Crash Course w strukturach danych.
Wiem, że to dużo.
Czy jest coś, że chciałbym przejść jeszcze raz?
Wszystko, co chcemy rozmawiać przez?
Tak?
>> Publiczność: W tym przykładzie, więc nowy ogon jest na 0 nad tym?
1 głośnik: Tak.
Publiczność: OK.
Tak to przeżywa, że masz jeden plus 4 or--
>> GŁOŚNIK 1: Więc mówisz, gdy chcemy iść to zrobić jeszcze raz?
Publiczność: Tak.
Więc jeśli były zastanawianie out-- gdzie są uzyskanie informacji od ogona w tym?
>> 1 głośnik: Tak ogon był in-- zmieniłem to.
Tak więc w tym przypadku tutaj, to było Tablica patrzymy, OK?
Tak więc mamy co w 1, 2, 3 i 4.
Mamy więc nasza głowa jest równa 1 w ten punkt, a nasza wielkość jest równa 4
w tym miejscu, prawda?
>> Wszyscy zgadzają się, że to przypadek?
Więc robimy głowę plus rozmiar, który daje 5, a potem mod przez 5.
Dostajemy 0, który mówi nam, że 0 jest gdzie jest nasz ogon, gdzie mamy miejsca.
>> Publiczność: Co czapka?
>> GŁOŚNIK 1: pojemność.
Przepraszam.
Tak, że jest rozmiar macierzy.
Tak?
>> PUBLICZNOŚCI: [niesłyszalne] przed wracamy element?
>> GŁOŚNIK 1: Więc ruszamy głowy lub powrót moment?
Jeśli więc przenieść jeden, zmniejszyć rozmiar?
Trzymaj się.
I na pewno zapomniał drugiego.
Nic nie szkodzi.
Nie ma inny wzór.
Tak, co chcesz, aby powrócić głowa, a następnie przenieść go z powrotem.
>> Publiczność: OK, ponieważ w tym punktem, głowa była na 0,
a następnie chcesz powrócić indeksu 0, a następnie dokonać głową 1?
>> GŁOŚNIK 1: Prawo.
Myślę, że nie ma innego formuła trochę jak ten.
Nie mam go na szczycie mojej głowy, jak Nie chcę dać niewłaściwy.
Ale myślę, że to ważne, aby idealnie powiedzmy, OK, nie przechowuj element-- cokolwiek
Element HEAD is-- zmniejszyć swoje rozmiar, przesunąć głowę nad i powrót
co ten element jest.
To jest całkowicie poprawny.
OK.
Czuję, że to nie jest jak most-- nie jesteś
zamiar stąd wyjść jak, tak, wiem, że próbuje.
Mam wszystko.
To jest OK.
Obiecuję.
Ale struktury danych są czymś, zajmuje dużo czasu, aby się przyzwyczaić.
Prawdopodobnie jednym z najtrudniejszych rzeczy, myślę, że w toku.
>> Więc to na pewno ma powtarzanie i patrząc at-- I
tak naprawdę nie wiem, związane list aż zrobiłem zbyt wiele z nich,
w ten sam sposób, że nie naprawdę zrozumieć wskaźniki
aż musiałem nauczyć go dla dwóch lat i zrobić własne psets z nim.
To zajmuje dużo powtórzył i czasu.
I w końcu, będzie to rodzaj kliknij.
>> Ale w międzyczasie, jeśli masz rodzaj o wysoki poziom zrozumienia tego, co
to zrobić, ich plusy i cons-- który jest co
naprawdę mają tendencję do podkreślenia, w szczególności w trakcie intra.
Jak, dlaczego używamy spróbuj na tablicy?
Jak, jakie są pozytywy i negatywy każdego z tych?
>> I zrozumienia kompromisów pomiędzy każdą z tych struktur
to, co jest o wiele ważniejsze teraz.
Nie może być jeden szalony pytanie lub dwa to
zamiar poprosić pchania lub wdrożyć wdrożenie pop lub Kolejkuj i usunie.
Jednak dla większości, mającej tę wyższy poziom i więcej zrozumienia
z intuicyjne zrozumienie jest ważniejsze niż w rzeczywistości
możliwość jego realizacji.
>> Byłoby naprawdę super, jeśli was wszystkich może wyjść i przejść wdrożenia spróbować,
ale rozumiem, że nie koniecznie Najbardziej rozsądna rzecz teraz.
Ale można w Pset, jeśli chcesz się, a następnie dostaniesz praktyki,
i wtedy może będziesz naprawdę zrozumieć.
Tak?
>> Publiczność: OK, więc, które z nich są rozumie się, że do stosowania w zbior?
Czy muszę korzystać z jednego z nich?
1 głośnik: Tak.
Więc masz wybór.
Myślę, że w tym przypadku, możemy mówić o Pset trochę bitowym
bo prowadził przez nich.
Więc w Pset, masz Wybór prób lub tabel hash.
Niektórzy ludzie będą próbować i używać filtrów rozkwicie,
ale ci, technicznie nie są poprawne.
Ze względu na ich charakter probabilistyczny, dają fałszywe alarmy czasami.
Są fajne spojrzenie na, choć.
Polecamy zapoznanie w nich co najmniej.
Ale masz wybór między tabeli mieszania i spróbować.
I że będzie gdzie ładowany do słownika.
>> I musisz wybrać Twoja funkcja skrótu,
musisz wybrać ile Wiadra masz, i będzie się zmieniać.
Jak, jeśli masz więcej wiader, być może będzie to działać szybciej.
Ale może marnujesz dużo miejsca w ten sposób, choć.
Musisz zrozumieć.
MMHMM?
>> PUBLICZNOŚCI: Powiedziałeś wcześniej, że możemy korzystać z innych funkcji skrótu,
że nie mamy do stworzenie funkcji skrótu?
>> 1 głośnik: Tak, tak.
Więc dosłownie dla funkcji skrótu, jak google "funkcja skrótu"
i patrzeć na jakieś fajne te.
Nie oczekuje się, aby budować własne funkcje skrótu.
Ludzie spędzają Tezy o tych rzeczach.
>> Więc nie martw się o budowę własnego.
Znajdź jeden online, na początek.
Niektóre z nich trzeba trochę manipulować
aby upewnić się, że powrót dopasować typy i cokolwiek, więc na początku,
Polecam za pomocą czegoś bardzo proste, że może po prostu
skróty na pierwszą literę.
A potem, gdy już, że praca, wyposażone w chłodnicy funkcji skrótu.
MMHMM?
>> Publiczność: Czy spróbować się lub skuteczne, ale tylko trudniej, like--
>> GŁOŚNIK 1: Więc spróbować, myślę, jest trudne do wdrożenia intuicyjnie
ale jest bardzo szybki.
Jednak zajmuje więcej miejsca.
Ponownie, można zoptymalizować zarówno tych, w różne sposoby i istnieją sposoby to--
Odbiorcy: Jak mamy klasyfikowane w tej sprawie?
Czy matter--
>> GŁOŚNIK 1: Więc klasyfikowane normalny sposób.
Masz zamiar być klasyfikowane na projektowaniu.
Niezależnie od tego, robisz, chcesz upewnij się, że jest tak eleganckie, jak to może być
i tak skuteczne, jak to tylko możliwe.
Ale jeśli zdecydujesz się spróbować lub skrótu tabeli, o ile działa
jesteśmy z tego zadowoleni.
A jeśli używasz czegoś, skróty na pierwszą literę, to w porządku,
jak może jak design-mądry.
Mamy również osiągnięcia punkt w tej semester--
Nie wiem, czy Ciebie faceci noticed-- jeśli jesteś
stopnie Pset trochę spadnie ze względu na design i etażerka,
to perfekcyjnie.
Robi się do punktu, gdzie programy są coraz bardziej skomplikowane.
Jest więcej miejsca można poprawić.
>> Więc jest to zupełnie normalne.
To nie jest, że jesteś robi gorzej na Pset.
To tylko my jest trudniejsze od ciebie.
Więc każdy czuje go.
Właśnie klasyfikowane wszystkie psets.
Wiem, że każdy czuje się go.
>> Więc nie martwić się o to.
A jeśli masz jakiekolwiek pytania na temat wcześniejsze psets lub sposobów można poprawić,
Staram specyficzne i komentować miejsca, ale czasami jest to późno
i jestem zmęczony.
Czy są jakieś inne rzeczy o struktury danych?
Jestem pewien, że ludzie tak naprawdę nie chcę mówić o nich więcej,
ale jeśli nie, jestem szczęśliwy przejść nad nimi, jak również czegokolwiek
z tym ostatnim wykładzie tydzień w zeszłym tygodniu.
>> Wiem, że w zeszłym tygodniu było wszystko, ocena, więc możemy mieć pomijane jakiegoś przeglądu
z wykładu.
Wszelkie inne pytania mogę odpowiedzieć?
OK, wszystko w porządku.
No, chłopaki wyjść 15 minut przed czasem.
>> Mam nadzieję, że to było pół-pomocny przynajmniej, i widzę was w przyszłym tygodniu,
lub czwartek godziny pracy.
Czy wnioski o przekąski w przyszłym tygodniu, to co?
Bo zapomniałem cukierki dziś.
I przyniósł cukierki ostatni tydzień, ale było Columbus Day,
więc nie było jak sześć osób miał cztery torby cukierków do siebie.
Mogę przynieść Starbursts ponownie, jeśli chcesz.
Starbursts?
OK, brzmi dobrze.
Miłego dnia, chłopaki.