>> [MUZYKI]
>> ANDI PENG: Witamy w tygodniu 6 sekcji.
Mamy odbiegała od naszych standardów Czas odcinek wtorek
po południu do tego pięknego niedzielnego poranka.
Dziękuję wszystkim, że dołączył do mnie dzisiaj, ale poważnie,
brawa.
>> To dość duży wysiłek.
I prawie nie nawet uczynić go się w czasie, ale to było OK.
Więc wiem, że wszyscy z was Właśnie dotarł do quizu.
Przede wszystkim zapraszamy do druga strona tego.
>> Po drugie, będziemy o tym rozmawiać.
Porozmawiamy o tym quizie.
Porozmawiamy o tym, jak robisz w klasie.
Wydobrzejesz.
Mam swoje quizy dla można w końcu tutaj,
więc jeśli chcecie wziąć Spójrz na niego, całkowicie w porządku.
>> Tak szybko, zanim zaczniemy, tym Porządek dzisiaj jest następująca.
Jak widać, jesteśmy w zasadzie szybkiego wypalania
przez całą masę struktur danych naprawdę, naprawdę, naprawdę szybko.
Tak więc jako takie, to nie będzie bardzo interaktywne dziś.
To będzie po prostu mnie rodzaj krzyku rzeczy, które wy, i gdybym mylić,
jeśli mam zbyt szybko, daj mi znać.
Są po prostu różne dane struktury, a także w ramach
Twojego pset dla tego Nadchodzący tydzień, będziesz
zostać poproszony do realizacji jednego z nich, być może dwa them-- dwóch z nich
w pset.
OK, więc jestem po prostu będzie rozpocząć z niektórych ogłoszeń.
Pojedziemy nad stosów i kolejek więcej w głębokość, niż to, co zrobiliśmy przed quizu.
Pojedziemy nad związane listy znowu, po raz kolejny,
bardziej dogłębnie niż to, co mieliśmy przed quizu.
A potem porozmawiamy o hash tabele, drzewa i stara, które
są bardzo potrzebne dla zbior.
A potem pójdziemy na niektóre pomocne wskazówki dla pset5.
>> OK, więc Quiz 0.
Średnia było 58%.
To było bardzo niskie, a więc wy wszyscy tak bardzo, bardzo dobrze, zgodnie
z tym.
>> Dość dużo, zasadą jest, jeśli jesteś w odchylenie standardowe średniej
zwłaszcza, że ​​jesteśmy w mniej Sekcja wygodne, jesteś całkowicie w porządku.
Jesteś na dobrej drodze.
Życie jest dobre.
>> Wiem, że to strach pomyśleć, że Dostałem jak 40% na tym quizie.
Idę na porażkę tej klasy.
Obiecuję ci, że nie jesteś będzie nie klasę.
Jesteś całkowicie w porządku.
>> Dla tych z Was, kto dostał się średnie, imponująca, imponujący,
jak poważnie dobrze zrobione.
Mam je ze mną.
Zapraszamy do się je na końcu sekcji.
Daj mi znać, jeśli masz jakiekolwiek problemy, pytania z nimi.
Jeśli dodać swój wynik źle, daj nam znać.
>> OK, więc pset5, to naprawdę dziwne tygodniu na Yale, w tym sensie,
że nasz zbior wynika Środę w południe w tym
pod koniec dnia, więc to faktycznie teoretycznie ze względu wtorek w południe.
Prawdopodobnie nikt nie skończył w wtorek w południe.
To jest całkowicie w porządku.
My będziemy mieć dyżury dziś w nocy, a także w poniedziałek wieczorem.
I wszystkie części w tym tygodniu rzeczywiście stać się warsztaty,
dlatego zachęcamy do pop dowolny odcinek chcesz,
i będą swego rodzaju mini-zbior warsztaty o pomoc w tej sprawie.
Tak więc, na przykład, jest to jedyny odcinek dokąd materiału nauczania.
Wszystkie pozostałe sekcje będą się skupiać wyłącznie na pomoc dla zbior.
Tak?
>> PUBLICZNOŚCI: Gdzie są godziny pracy?
>> ANDI PENG: Godziny pracy tonight-- och, dobre pytanie.
Myślę, że godziny pracy tonight są w Teal lub na Commons.
Jeśli zaznaczysz online, CS50 i udać się do godzin pracy biura,
nie powinno być harmonogram, że powie Ci, gdzie wszystkie z nich są.
>> Wiem, że albo dziś wieczorem lub jutro jest turkusowy,
i myślę, że możemy mieć commons do drugiej nocy.
Nie jestem pewny.
Dobre pytanie.
Sprawdź na CS50.
>> Cool, jakiekolwiek pytania dotyczące Plan na następny jak trzy dni?
Obiecuję lubicie Dawida powiedział, to jest szczyt wzgórza.
Jesteście prawie.
Zaledwie trzy dni więcej.
Się tam dostać, a potem my wszyscy zejść.
Będziemy mieć ładny CS-bezpłatny urlop.
Witam ponownie.
Będziemy nurkować w internecie programowanie i rozwój,
rzeczy, które są bardzo zabawne porównaniu do niektórych innych psets.
I to będzie zimno, a będziemy mieć mnóstwo zabawy.
Będziemy mieć więcej cukierków.
Niestety o cukierki.
Zapomniałem słodycze.
To był ciężki poranek.
Więc jesteście prawie na miejscu, i jestem bardzo dumny z was.
>> OK, więc stosy.
Kto kocha pytanie o Jacku i jego ubrania na quiz?
Nikt?
W porządku.
>> Więc zasadniczo, jak możesz obraz Jacka, ten facet tutaj,
kocha do podjęcia odzież z górnej części stosu
i stawia go z powrotem na stos po zrobił.
Tak więc w ten sposób, że nigdy wydaje się być coraz
na dnie układać w jego odzieży.
Więc tego rodzaju opisuje podstawowa struktura danych
od tego, jak stos jest realizowany.
>> Zasadniczo, myśleć o stos jak każdy stos obiektów
gdzie można umieścić rzeczy na wierzchu, a następnie pop je z góry.
Więc LIFO jest akronimem lubimy do use-- Ostatnio weszło, pierwsze wyszło.
I tak, aby mógł się w górnej części Stos jest pierwszym, który wychodzi.
I tak te dwa terminy chcemy skojarzyć
z tym nazywane są Push i pop.
Po naciśnięciu coś na stos, i włóż ją z powrotem.
>> A więc myślę, że jest to swego rodzaju pojęcie abstrakcyjne dla tych,
którzy chcą zobaczyć jak u faktyczna realizacja tego
w świecie rzeczywistym.
Jak wielu z was napisał esej Może jak godzinę wcześniej było to spowodowane,
i przypadkowo usunięte ogromne fragment o tym, jak przypadkowo?
I co wtedy kontrola zrobić używamy, aby umieścić go z powrotem?
Control-Z, tak?
Control-Z, więc ilość razy Control-Z, który uratował mi życie,
uratował mi tyłek, za każdym razem, , który jest realizowany przez komin.
>> Zasadniczo, cała informacja to w dokumencie programu Word,
robi popychany wpadł do woli.
I tak w istocie, kiedy tylko usuwać wszystko, pop go z powrotem.
A potem, jeśli potrzebujesz go ponownie, ciebie wciśnij go, co jest, co robi Control-C.
I funkcja więc prawdziwy świat od tego, jak proste struktury danych
może pomóc w codziennym życiu.
>> Więc struct jest sposób, faktycznie utworzyć stos.
Wpisujemy zdefiniować struct, a następnie nazywamy go układać na dnie.
Oraz w stosie mamy dwa parametry
że możemy w istocie manipulować, więc mamy char zdolności gwiazdowe łańcuchy.
>> Wszystko, co robi tworzy tablicę
że możemy przechowywać, co chcesz które możemy określić jego pojemność.
Pojemność jest tylko max ilość elementy możemy umieścić w tej tablicy.
int rozmiar jest licznik, który utrzymuje utwór o tym, jak wiele elementów są obecnie
w stos.
Tak więc możemy śledzić, A, zarówno jak duży stos jest rzeczywista,
i B, ile tego stosu wypełniliśmy, ponieważ nie chcemy
przepełnienie nad tym, co nasze możliwości są.
>> Tak na przykład, ten piękny Pytanie było na quiz.
Zasadniczo jak możemy popchnąć na górze stosu.
Całkiem proste.
Jeśli spojrzeć na to, przejdziemy przez to.
Jeśli [niesłyszalne] size-- Pamiętam, kiedy tylko
Aby uzyskać dostęp do dowolnego Parametr w struktury,
robisz nazwę struct.parameter.
>> W tym przypadku, s jest nazwa naszego stosu.
Chcemy, aby uzyskać dostęp do rozmiaru o tym, więc robimy s.size.
Tak długo, jak wielkość nie jest równa pojemności lub tak długo,
jak jest to mniej niż zdolności, albo będzie tu pracować.
>> Chcesz, aby uzyskać dostęp do wnętrza swojego stosu, więc s.strings,
i masz zamiar umieścić ten nowy numer które chcesz wstawić tam.
Powiedzmy, że będziemy chcieli włóż int n na stosie,
możemy zrobić s.strings, wsporniki, s.size równa n.
Ponieważ rozmiar jest gdzie obecnie są w stosie
jeśli mamy do pchania to on, po prostu dostęp
gdzie rozmiar, tym Obecna pełnia stosu,
i wcisnąć int n na nim.
A potem chcemy, aby upewnić się, że jesteśmy również zwiększając rozmiar n,
więc możemy śledzić mamy dodano dodatkowe rzeczy do stosu.
Teraz mamy większy rozmiar.
Czy to tutaj sensu wszyscy, jak logicznie to działa?
To był rodzaj szybkie.
PUBLICZNOŚCI: Czy można przejść z s.stringss.strings [s.size] ponownie?
ANDI PENG: Jasne, więc co robi s.size obecnie nam dać?
PUBLICZNOŚCI: To obecny rozmiar.
ANDI PENG: Dokładnie, tak bieżący wskaźnik, że nasza wielkość jest,
i tak chcemy umieścić nową liczbę całkowitą że chcemy wstawić do s.size.
Czy to ma sens?
Ponieważ s.strings, wszystko, Jest to nazwa tablicy.
Wszystko to ma dostęp do Tablica w ramach naszej struktury,
i tak, jeśli chcemy miejsce n do tego indeksu,
możemy po prostu do niego dostęp za pomocą wsporników s.size.
Chłodny.
>> Dobrze, pop, ja pseudocode go dla was, ale podobnej koncepcji.
Czy to ma sens?
Jeśli rozmiar jest większy od zera, to
wiem, że chcesz zrobić coś , bo jeśli rozmiar nie jest
większa niż zero, to nie mają nic stosie.
>> Więc chcesz tylko wykonanie ten kod, to może tylko
pop, czy jest coś do pop.
Tak więc, jeśli rozmiar jest większy od 0, to minus rozmiar.
Zmniejszamy rozmiar, a następnie powrót to, co jest w środku, bo
popping, chcemy dostępu, co jest przechowywane
indeksu wierzchu stosu.
Wszystko ma sens?
Gdybym cię faceci to pisać, to wy móc napisać go?
OK, chłopaki mogą bawić się z nim.
Nie martw się, jeśli nie rozumiesz.
Nie mamy czasu, aby zakodować to dzisiaj, bo mamy
ma dużo tych struktur przejść, ale zasadniczo
pseudokod, bardzo, bardzo podobne do pchania.
Wystarczy postępować zgodnie wzdłuż logiki.
Upewnij się, że masz dostęp do wszystkich cechy swojej struktury poprawnie.
Tak?
>> PUBLICZNOŚCI: Czy te slajdy i cała ta sprawa będzie się już dziś-owski?
ANDI PENG: Zawsze, yep.
Mam zamiar spróbować umieścić jak to się godzinę po.
Będę email Dawida, Dawid spróbuje umieścić go jak godzinę po tym.
>> OK, więc potem przenieść się do tego inne piękny struktura danych o nazwie kolejki.
Jak faceci widzą Tutaj, Kolejka, dla Brytyjczyków wśród nas,
wszystkim jest to linia.
Tak więc w przeciwieństwie do tego, co myślisz, że stos jest,
kolejka jest dokładnie to, co logicznie myślisz, że jest.
Jest w posiadaniu zasad FIFO, co jest pierwsze, pierwszy na wyjściu.
Jeśli jesteś pierwszy jedno w linii, jesteś
pierwszy, który wychodzi z linii.
>> Więc to, co chcemy nazwać jest dequeueing i skolejkowania.
Jeśli chcemy dodać coś do naszej kolejki, możemy enqueue.
Jeśli chcemy z kolejki, lub podjąć coś się, że z kolejki.
>> Tak samo poczucie, że jesteśmy trochę tworzenia elementów o stałym rozmiarze, że
może przechowywać pewne rzeczy, ale możemy również
zmienić dokąd umieszczania Parametry wewnątrz nich
na podstawie jakiego rodzaju funkcjonalność chcemy.
Więc stosy, chcieliśmy ostatni jeden, N, aby być pierwszym na zewnątrz.
Kolejka jest chcemy pierwszą rzeczą, się, by być pierwszą rzeczą, na zewnątrz.
>> Więc sama struktura typu określenie, jak widać,
to trochę inaczej od tego, co było stos
bo nie tylko mamy do utrzymania tor, gdzie rozmiar jest obecnie,
Chcemy również, aby śledzić głowy a także, gdzie obecnie są.
Więc myślę, że to jest łatwiejsze jeśli rysuję to.
Więc wyobraźmy sobie, że mamy kolejkę, więc powiedzmy, że głowa jest tutaj.
Szef linii, niech po prostu powiedzieć, że to obecnie istnieje,
i chcemy, aby wstawić coś do kolejki.
Mam zamiar zadzwonić rozmiar zasadniczo jest to samo, jak ogon,
koniec gdziekolwiek kolejka jest.
Powiedzmy, że rozmiar jest tutaj.
>> Więc w jaki sposób można realnie włożyć coś do kolejki?
Co indeksu chcemy umieścić gdzie chcemy wstawić.
Jeśli jest to początek twój kolejki i to jest już koniec
lub rozmiar to, gdzie się Aby dodać kolejny obiekt?
>> PUBLICZNOŚCI: [niesłyszalne]
ANDI PENG: Dokładnie, chcesz dodać to w zależności od ty ją napisał.
Albo to jest puste lub że jest pusty.
Więc chcesz go dodać prawdopodobnie tu, bo jeśli rozmiar jest--
jeśli te są pełne, chcesz je dodać tutaj, prawda?
>> I tak to jest, a bardzo, bardzo proste, nie do końca zawsze prawidłowe
ponieważ różnicą między kolejki i stosu
jest to, że kolejka może rzeczywiście być manipulowane
tak, że zmiany głowy w zależności od tego, gdzie chcesz
początek swojej zawołanie, aby rozpocząć.
I w rezultacie, twój ogon zamierza także zmienić.
I tak spojrzeć na Ten kod teraz.
Jak chłopaki zostali także poproszeni o Napisać na quiz, enqueue.
Może porozmawiamy za pośrednictwem dlaczego odpowiedź była, co to było.
>> I nie bardzo pasuje ten wiersz na jednym, ale zasadniczo ten fragment kodu
powinny być w jednej linii.
Spędź jak 30 sekund.
Rozejrzyj się i zobacz dlaczego w ten sposób, że jest.
>> Bardzo, bardzo podobna struktura, bardzo, bardzo Podobną strukturę jak poprzednie
stos z wyjątkiem być może jednej linii kodu.
I że zgodnie z kodem określa funkcjonalność.
I to naprawdę odróżnia kolejka ze stosu.
>> Każdy, kto chce wziąć ukłucie co tłumaczy, dlaczego masz
got to skomplikowane rzeczy w tutaj?
Widzimy powrót naszego wspaniały przyjaciel moduł.
Jak wy wkrótce się rozpoznać w programowaniu,
Prawie w każdej chwili trzeba coś owinąć wokół czegoś,
Moduł będzie sposobu, aby to zrobić.
Więc wiedząc, że nie każdy chce próba wyjaśnienia tej linii kodu?
Tak, wszystkie odpowiedzi są akceptowane i mile widziane.
PUBLICZNOŚCI: Mówisz do mnie?
ANDI PENG: Tak.
PUBLICZNOŚCI: Och, nie przepraszam.
ANDI PENG: OK, więc niech przejść przez ten kod.
Więc kiedy starasz się dodać coś na kolejce,
w pięknym przypadku, że szef dzieje być tutaj, to bardzo łatwo dla nas
po prostu iść do końca włóż coś, prawda?
Ale cały sens kolejce jest że głowa może rzeczywiście dynamicznie
zmienia się w zależności od tego, gdzie się chcą początek naszej q być,
i jako takie, ogona zamierza także zmienić.
>> A więc wyobraź sobie, że to nie było w kolejce, ale to była kolejka.
Powiedzmy, że szef jest tutaj.
Powiedzmy, że nasza kolejka wygląda tak.
Jeśli chcemy przesunąć, gdzie początek linii jest
powiedzmy, że przesunął głowę w ten sposób, a rozmiary tutaj.
>> Teraz chcemy, aby dodać coś do ta kolejka, ale jak chłopaki widzą,
to nie jest tak proste, jak tylko dodać to, co jest po rozmiarze
bo wtedy zabraknie Granice naszego rzeczywistego tablicy.
W przypadku, gdy chcemy naprawdę dodać tutaj.
To piękno kolejce jest to, że dla nas, wizualnie to
wygląda jak linia idzie tak, lecz gdy przechowywane w strukturze danych,
dają go jako niczym cyklu.
To rodzaj otacza się do przodu w taki sam sposób
że linia może zawinąć wokół zależności od Gdziekolwiek
Aby początku linii być.
I tak, jeśli bierzemy spojrzeć w dół tutaj, niech
powiedzieć, chcieliśmy stworzyć Funkcja o nazwie Kolejkuj.
Chcieliśmy, aby dodać int n do tego q.
Jeśli q.size q-- zadzwonimy, że nasze dane structure-- jeśli nasz queue.size nie
równa pojemności lub jeśli to mniej niż zdolności,
q.strings jest tablica w naszej q.
Mamy zamiar ustawić że równe q.heads,
która jest tutaj, a także q.size Moduł pojemnością, która
owinąć nas z powrotem tutaj.
>> Tak więc w tym przykładzie, wskaźnik głowy jest jeden, prawda?
Wskaźnik rozmiaru jest 0, 1, 2, 3, 4.
Tak więc możemy zrobić 1 plus 4 moduł od naszej zdolności, która jest 5.
Co nam to daje?
Co to jest wskaźnik, który wychodzi z tego?
>> PUBLICZNOŚCI: 0.
>> ANDI PENG: 0, co dzieje się tutaj,
i tak chcemy być w stanie wstawić do tutaj.
I tak to równanie o rodzaju po prostu współpracuje ze wszystkimi numerami
w zależności od gdzie głowy i twój rozmiar to.
Jeśli wiesz, co ci rzeczy, wiesz,
dokładnie tam, gdzie chcesz wstawić co jest po kolejce.
Czy to ma sens dla każdego?
>> Wiem, rodzaj mózgu Teaser zwłaszcza, że
przyszedł w następstwie quiz.
Ale mam nadzieję, że wszyscy teraz rozumiem,
Dlatego rozwiązanie to albo to Funkcja jest sposób, że jest.
Każdy, nieco niejasne na ten temat?
OK.
>> A więc teraz, jeśli chciał z kolejki, to
jest gdzie nasz szef będzie przesunięcie bo gdybyśmy z kolejki,
nie zdjąć końcówkę q.
Chcemy, aby zdjąć z głowy, prawda?
Tak więc, w rezultacie głowica będzie się zmieniać, i dlatego, gdy enqueue,
musisz śledzić gdzie twoja głowa i twój rozmiar
to, aby móc wstawić w prawidłowym położeniu.
>> I tak, gdy z kolejki, Ja również pseudokod go.
Zapraszam do jeśli chcesz próba kodowania to.
Chcesz przenieść głowy, prawda?
Gdybym chciał z kolejki, ja by przesunąć głowę nad.
Byłoby to szef.
>> A nasz obecny rozmiar będzie odejmowanie, bo już nie
cztery elementy w tablicy.
Mamy tylko trzy, a następnie chcemy do powrotu, co zostało zapisane w środku
głowy, ponieważ chcemy, aby wziąć to Wartość się więc bardzo podobna do stosu.
Tylko ty bierzesz z innego miejsca,
i trzeba przypisać wskaźnik do innego miejsca, w wyniku.
Logicznie rzecz biorąc, każdy naśladowania?
Wielki.
>> OK, więc mamy zamiar porozmawiać trochę więcej w głębokości około powiązanych list
bo oni będą bardzo, bardzo cenne dla Ciebie w trakcie tego tygodnia
psets.
Związane wymienia, jak wy pamiętam, wszystkie one są
są węzły, które są węzły pewne Wartości zarówno wartość i wskaźnik
które są połączone ze sobą przez te wskaźniki.
I tak, w jaki sposób struktura tworzymy węzeł tutaj jest to
mają int n, która jest co wartość w sklepie lub ciąg n
lub cokolwiek chcesz nazwać to, gwiazda char n.
Struct gwiazda węzeł, który jest wskaźnik które chcesz mieć w każdym węźle,
będziesz mieć, że wskaźnik do następnego punktu.
Będziesz miał głowę z połączonej listy, która jest
będzie wskazywać na resztę wartości tak dalej i tak dalej
aż w końcu dotrzeć do końca.
I ten ostatni węzeł jest po prostu będzie nie mieć wskaźnik.
To będzie wskazywać na null, i wtedy
wiesz, że hit koniec swojej połączonej listy
jest, gdy twoja ostatnia wskazówka nie wskazują na nic.
>> Tak więc mamy zamiar udać się nieco dalej w Głębokość w odniesieniu do, jak się będzie prawdopodobnie
szukaj połączonej listy.
Pamiętaj, co to tylko niektóre z Wady związane list
wersety tablicę dotyczące poszukiwań.
Tablica Możesz szukać binarny, ale dlaczego nie można zrobić, że w połączonej listy?
>> PUBLICZNOŚCI: Bo wszystkie są podłączone, ale nie bardzo wiem gdzie
[NIESŁYSZALNY].
>> ANDI PENG: Tak, dokładnie tak, pamiętam że blask tablicy
był fakt, że mieliśmy pamięć o dostępie swobodnym, gdzie
gdybym chciał wartości z indeksu sześć, mogę tylko powiedzieć, wskaźnik sześć,
daj mi tę wartość.
A to dlatego, że tablice są sortowane w ciągłym obszarze pamięci
w jednym miejscu, natomiast rodzaj powiązanych list
są przeplatane wokół losowo, i tylko w ten sposób można znaleźć
jest poprzez wskaźnik, który mówi, adres, gdzie, że w przyszłym węzeł jest.
>> I tak, w rezultacie jedyna droga aby przeglądać połączonej listy
jest przeszukiwanie liniowe.
Bo nie wiem dokładnie gdzie wartość 12 w połączonej listy jest,
Muszę przechodzić całość z tym związane jednej listy
jeden z głowicy do pierwszego węzła do drugiego węzła do trzeciego węzła,
w dół, aż w końcu się gdzie ten węzeł szukam jest.
I tak, w tym sensie, wyszukiwania w połączonej listy jest zawsze n.
To zawsze n.
To zawsze w czasie liniowym.
>> A więc kod, w którym realizujemy to, i to
jest nieco nowego dla was od czasu Chłopaki naprawdę nie rozmawialiśmy o czy kiedykolwiek
widziane wskazówki w jaki sposób przeszukiwać wskaźników,
więc będziemy iść przez Ten bardzo powoli.
Więc wyszukiwarka bool, w prawo, wyobraźmy sobie, że chcemy
aby utworzyć funkcję zwaną wyszukiwarka, która zwraca true
jeśli znalazłeś wartość wewnątrz powiązane listy i zwraca false w przeciwnym wypadku.
Lista gwiazda węzeł obecnie tylko wskaźnik
do pierwszej pozycji w swojej połączonej listy.
int n ma wartość, że jesteś szukając w tym wykazie.
>> Tak gwiazda węzła wskaźnik wynosi listę.
Oznacza, że ​​mamy do ustawiania i tworząc wskaźnik
do tego pierwszego węzła wewnątrz listy.
Wszyscy się ze mną?
Więc gdybyśmy go tu, musiałbym
zainicjowany wskaźnik wskazujący na szef cokolwiek to lista jest.
>> I wtedy, gdy pojawi się tutaj, podczas gdy wskaźnik nie równa null
tak, że ma pętlę, w którym są będzie następnie przejeżdżające
reszta naszej liście bo co dzieje się, gdy wskaźnik jest równy wartości null?
Wiemy, że have--
>> PUBLICZNOŚCI: [niesłyszalne]
>> ANDI PENG: Dokładnie, tak, wiemy, że dotarliśmy do końca listy, prawda?
Jeśli wrócisz tu, każdy węzeł powinien być skierowany do innego węzła
i tak dalej i tak dalej aż trafisz w końcu
ogon swojej połączonej listy, który posiada wskaźnik, który po prostu
nie wskazują miejscu innym niż no.
I tak w zasadzie wiemy, że Twoja lista wciąż się
dopóki wskaźnik nie równa null, bo raz, że jest równa null,
wiesz, że nie ma więcej rzeczy.
>> Więc to jest pętla, w której jesteśmy będzie mieć rzeczywisty wyszukiwanie.
A jeśli pointer-- widzisz tego rodzaju funkcji tam strzałki?
Więc jeśli wskaźnik do n punktów, jeśli wskaźnik przy n równa jest równa n,
to oznacza to, że w przypadku wskaźnik, że jesteś
szukając na końcu każdego węzeł jest faktycznie równa wartości
szukasz, a następnie Aby powrócić prawda.
Więc w zasadzie, jeśli jesteś na węźle ma wartość, że szukasz,
wiesz, że byłeś w stanie skutecznie szukać.
>> W przeciwnym razie, chcesz ustawić kursor do następnego węzła.
To właśnie ta linia tutaj robi.
Wskaźnik równy wskaźnik obok.
Każdy, zobaczyć, jak to działa?
>> I w zasadzie masz zamiar po prostu przechodzić całość listy,
resetowanie wskaźnika za każdym razem, aż w końcu trafić na koniec listy.
I wiesz, że nie ma więcej węzłów do przeszukiwania,
a następnie można return false bo wiesz, że, no, no,
jeśli udało mi się szukać przez całości listy.
Jeśli w tym przykładzie, gdybym chciał szukać wartości 10,
i zaczynają się od głowy, a Szukam w dół,
a ja w końcu dostałem się do tego, co wskaźnik, który wskazuje na null,
Wiem, że bzdura, chyba 10 nie jest w ta lista, bo nie mogłem go znaleźć.
A ja na koniec listy.
I w tym przypadku wiesz Idę do return false.
>> Niech to moczyć w na trochę.
To będzie dość ważne dla zbior.
Logika jest to bardzo proste, być może składniowo tylko jego realizacji.
Chcecie zrobić Upewnij się, że rozumiesz.
Chłodny.
>> OK, więc jak będziemy wstawianie węzłów, w prawo,
na listę, bo pamiętam, jakie są, co korzyści
posiadania połączonej listy versus tablica w zakresie przechowywania?
>> PUBLICZNOŚCI: To dynamiczne, więc łatwiej to--
>> ANDI PENG: Dokładnie, więc jest dynamiczne, co
Oznacza to, że może ona rozszerzać się i kurczyć w zależności od potrzeb użytkownika.
I tak, w tym sensie, że nie trzeba marnować niepotrzebnie miejsce w pamięci, bo
jeśli nie wiem, jak wiele wartości chcę do sklepu, to nie ma sensu dla mnie
utworzyć tablicę, ponieważ jeśli chcę przechowywać 10 wartości
i utworzyć tablicę 1000, to dużo zmarnowanego pamięci przydzielone.
Dlatego chcemy użyć powiązane Lista, aby być w stanie dynamicznie
zmienić lub zmniejszyć nasz rozmiar.
>> I tak, że umożliwia umieszczenie nieco bardziej skomplikowane.
Ponieważ nie możemy losowo dostęp elementy sposób, że my tablicy.
Jeśli chcę wstawić element w siódmym indeksu
Po prostu można go wstawić w siódmym indeksu.
Na połączonego liście, nie dość pracować równie łatwo,
i tak, jeśli chcemy, aby wstawić ten, tutaj, w połączonej listy,
wizualnie, to bardzo dobrze widoczne.
Chcemy tylko, aby wstawić go tam, na samym początku listy
tuż po głowie.
>> Ale sposób, w jaki musimy przypisać kursory jest nieco zawiłe
lub, logicznie, ma sens, ale chcesz się upewnić, że masz go
do końca, ponieważ ostatnią rzeczą, którą chcesz
jest przypisanie wskaźnika Sposób, w jaki robimy tutaj.
Jeśli dereference wskaźnik z głową na 1,
to wszystko nagle reszta twojej połączonej listy
jest stracone, ponieważ masz w rzeczywistości nie utworzony tymczasowy nic.
To się wskazał na 2.
Jeśli przypisanie wskaźnika, wówczas Reszta listy jest całkowicie stracone.
Więc chcesz być bardzo, bardzo ostrożny
najpierw przypisać wskaźnik z Cokolwiek
Aby wstawić do gdziekolwiek chcesz, a następnie
może dereference resztę listy.
>> Dotyczy to więc wszędzie tam, gdzie próbujesz wstawić do.
Jeśli chcesz wstawić u głowa, jeśli chcesz odpowiedzieć tutaj,
jeśli chcesz wstawić na koniec, dobrze, koniec I
Domyślam się, że po prostu nie mają wskaźnik, ale
Aby upewnić się, że nie stracić resztę listy.
Zawsze chcesz upewnić się, Twój nowy węzeł wskazuje
kierunku cokolwiek Aby wstawić do,
a następnie można dodać łączenia się.
Każdy, jasne?
>> To będzie jeden z rzeczywistych problemów.
Jednym z najbardziej istotnych kwestii będziesz mieć na swoim pset
jest to, że masz zamiar spróbować stworzyć połączonej listy i wstawić rzeczy
ale potem po prostu stracić reszta twojej połączonej listy.
I masz zamiar być jak, ja nie wiem dlaczego tak się dzieje?
I to jest ból przejść i wyszukiwanie wszystkich wskaźników.
>> I gwarantuje ci na tym pset, pisanie i rysowanie tych węzłów na
będzie bardzo, bardzo pomocne.
Więc można całkowicie śledzić gdzie wszystkie wskaźniki są,
co się dzieje nie tak, gdzie wszystkie węzły są,
co trzeba zrobić, aby uzyskać dostęp lub wstawić lub usunąć lub któregokolwiek z nich.
Wszyscy dobrze się z tym?
Chłodny.
>> Więc jeśli chcemy spojrzeć na kod?
Och, nie wiem, czy my widać the-- OK, więc
w górę jest to funkcja nazwany wstawić tam, gdzie chcemy
wstawić int n do połączonej listy.
Mamy zamiar przejść przez to.
To dużo kodu, dużo nowej składni.
Będziemy OK.
>> Tak więc u góry, w miarę chcemy stworzyć coś
Co musimy zrobić, zwłaszcza jeśli ma to nie być przechowywane na stosie
ale w kupie?
Idziemy do malloc, prawda?
Tak więc mamy zamiar utworzyć wskaźnik.
Węzłów, wskaźnik, nowe równi malloc rozmiar węzła
bo chcemy, że węzeł ma zostać utworzony.
Chcemy ilość Pamięć że węzeł zajmuje
do przydziału dla Stworzenie nowego węzła.
>> A potem mamy zamiar sprawdzić sprawdzić, czy nowe równi wynosi wartość null.
Pamiętaj, co powiedział?
Cokolwiek malloc, Co należy zawsze zrobić?
Należy zawsze sprawdzić, czy, że jest null.
>> Na przykład, jeśli twój operacyjny System był pełen,
gdybyś miał więcej pamięci na wszystkich i spróbować malloc,
to zwróci null dla Ciebie.
I tak, jeśli starają się go używać kiedy został skierowany na null,
nie będziemy w stanie aby uzyskać dostęp do tych informacji.
I tak, na przykład, chcieliśmy, aby pewność, że gdy jesteś mallocing,
zawsze jesteś sprawdzając, czy że pamięć podawany jest null.
A jeśli nie jest, to możemy przejść on z resztą naszego kodu.
>> Więc będziemy zainicjować nowy węzeł.
Mamy zamiar zrobić nowy n jest równa n.
A potem będziemy robić ustawić nowy wskaźnik na nowy
null bo teraz nie robimy chcę nic na to, aby wskazać.
Nie mamy pojęcia, gdzie to się do was,
a następnie, jeśli chcemy włóż ją na głowę,
wtedy możemy przypisać wskaźnik do głowy.
Czy wszyscy postępować zgodnie z logiką od tego, gdzie to się dzieje?
>> Wszystko robimy tworzy nowy węzeł, ustawiając kursor na null,
a następnie ponowne przypisanie go w głowę, czy my
Chcemy wiedzieć, włóż ją na głowę.
A następnie szef będzie wskazują na tego nowego węzła.
Każdy OK z tym?
>> Więc jest to proces dwuetapowy.
Musisz najpierw przypisać co tworzysz.
Ustaw ten wskaźnik na odniesienia, a następnie
może trochę dereference pierwszy wskaźnik
i skierować go do nowego węzła.
Wszędzie tam, gdzie chcesz go wstawić, że logika będzie prawdziwe.
>> To trochę jak przypisywanie zmienne tymczasowe.
Pamiętaj, że masz aby upewnić się, że Ciebie
nie stracić jeśli zamiana.
Chcesz, aby upewnić się, że masz tymczasowa zmienna tego typu utrzymuje
orientację, gdzie tego czegoś przechowywany jest tak, że
nie tracą żadnej wartości w toku lubią bawić się z nim.
>> OK, więc kod będzie tutaj.
Wy spojrzeć po sekcji.
Będzie tam być.
>> Więc myślę, w jaki sposób się różnić, jeśli chcemy
wstawić w środku lub na końcu?
Czy ktoś ma pomysł co to jest pseudokod jako logiczną odniesienia
że chcemy podjąć, jeśli chcieliśmy aby wstawić go w środku?
Więc jeśli chcemy wstawić go u głowa, wszystko co robimy jest stworzenie nowego węzła.
Ustawiamy kursor na które nowy węzeł do jakiegoś szefa,
a następnie ustawiamy głowicę do nowego węzła, prawda?
Jeśli chcemy, aby wstawić go w środku listy, co mamy robić?
>> PUBLICZNOŚCI: Byłoby jeszcze być podobny proces
jakby przypisanie wskaźnika oraz następnie przypisanie tego wskaźnika,
ale trzeba by tam odnaleźć.
>> ANDI PENG: Dokładnie, tak dokładnie, ten sam proces, z wyjątkiem ciebie
zlokalizować, gdzie dokładnie chce, że nowy wskaźnik, aby przejść do,
więc jeśli chcę wstawić do środek związany list-- OK,
powiedzmy, że nasza połączona lista.
Jeśli chcemy go wstawić tutaj, mamy zamiar utworzyć nowy węzeł.
Jedziemy do malloc.
Mamy zamiar stworzyć nowy węzeł.
Mamy zamiar przypisać wskaźnik tego węzła tutaj.
>> Jednak problem, który różni z którego głowa jest
jest to, że dokładnie wiedział, gdzie głowica jest.
To było tuż po pierwszym, prawda?
Ale tutaj mamy do śledzenia od tego, gdzie jesteśmy, wkładając ją do.
Jeśli wstawiasz nasze Węzeł tutaj, mamy
aby upewnić się, że jeden poprzednia do tego węzła
to ten, który przypisuje wskaźnik.
Więc trzeba trochę śledzić dwóch rzeczy.
Jeśli śledzić, gdzie to Węzeł obecnie jest wstawienie do.
Można również śledzić, gdzie poprzedni węzeł, który patrzysz
był również tam.
Wszyscy dobrze się z tym?
OK.
>> Jak o wstawienie do końca?
Gdybym chciał go dodać here-- gdybym chciał w celu dodania nowego węzła do końca listy
jak mogę się do tego zabrać?
PUBLICZNOŚCI: Więc Obecnie ostatni wskazał na null.
ANDI PENG: Tak.
Dokładnie, więc ten Aktualnie jest skierowany wiedzieć,
i tak myślę, że w tym sensie, że to bardzo łatwo dodać na końcu listy.
Wszystko co musisz zrobić, to ustawić równa null, a potem bum.
Właśnie tam, bardzo łatwe.
Bardzo prosta.
>> Bardzo podobny do głowy, ale logicznie ci
Aby upewnić się, że kroki podjąć w kierunku robi nic z tego,
jesteś po wzdłuż.
To bardzo proste, aby w środku Twój kod, złapany na,
Och, mam tak wiele wskazówek.
Nie wiem, gdzie coś wskazuje.
Ja nawet nie wiem, który węzeł jestem na.
Co się dzieje?
>> Spokojnie, uspokój się, weź głęboki oddech.
Narysuj swoje połączonej listy.
Jeśli powiesz, że wiem, gdzie dokładnie Muszę wstawić to do
i wiem dokładnie, jak przypisać mój wskaźniki, o wiele łatwiej wyobrazić
out-- o wiele łatwiej nie zgubić się w błędy w kodzie.
Każdy OK z tym?
OK.
>> Sądzę więc, że pojęcie to, że nie mają Przed naprawdę mówił o teraz,
i myślę, że was zapewne nie napotka wiele yet--
jest to rodzaj zaawansowanego concept-- jest to, że rzeczywiście mamy dane
Struktura nazywa się podwójnie połączonej listy.
Tak jak chłopaki widzą, wszystko co robimy jest tworzenie
rzeczywista wartość, dodatkowy Wskaźnik na każdym z naszych węzłów
który również wskazuje na poprzednim węzłem.
Więc nie tylko my mamy swoje Węzły wskazują na następną.
Wskazują one także do poprzedniego.
Mam zamiar ignorować te dwa właśnie teraz.
>> Więc masz łańcuch że może poruszać się w obu kierunkach,
i to jest to nieco łatwiejsze logicznie podążać.
Jak tutaj, zamiast śledzenie, oh,
wiedzieć, że węzeł jest ten, który mam do ich przekazania,
Mogę tylko iść tu i wystarczy pociągnąć poprzedni.
Wtedy wiem, gdzie dokładnie że jest, a potem
nie trzeba przemierzać Całość połączonej listy.
To trochę łatwiej.
>> Ale jako takie, masz podwójnie ilość wskaźników,
to podwójna ilość pamięci.
Jest wiele wskazówek, aby śledzić.
To trochę bardziej skomplikowane, ale to nieco bardziej przyjazny dla użytkownika w zależności
na co próbujesz osiągnąć.
>> Więc tego typu danych Struktura całkowicie istnieje,
a struktura jest bardzo proste, z wyjątkiem wszystkich masz to,
a nie tylko wskaźnik do następnego, masz również wskaźnik do poprzedniego.
To wszystko, różnica była.
Wszyscy dobrze się z tym?
Chłodny.
>> Dobrze, więc teraz jestem naprawdę spędzić prawdopodobnie
jak 15 do 20 minut lub luzem reszty czasu w sekcji
mówi o tabele z cebulą.
Ilu z was Przeczytałem pset5 specyfikację?
Dobra, dobra.
To wyższe niż 50% normalnie.
Jest ok.
>> Tak jak chłopaki będą widzieć, jesteś wyzwaniem w pset5
będzie realizacja słownika gdzie można załadować ponad 140.000 słów
że dajemy Tobie i sprawdzanie pisowni że wobec całego tekstu.
Damy Ci losowo fragmenty literatury.
Damy ci Odysei.
Damy Ci Iliady.
Damy Ci Austin Powers.
>> A twój wyzwaniem będzie Sprawdzanie pisowni
każde słowo w ogóle z tych słowników
zasadniczo z naszej sprawdzania pisowni.
I tak jest kilka części tworzenia tego pset,
Pierwszy chcesz być w stanie rzeczywiście załadować
wszystkie słowa w twoje Słownik, a następnie
Aby móc sprawdzanie pisowni wszystkich z nich.
I tak, na przykład, masz zamiar wymagać struktura danych, które mogą to zrobić szybko,
i skutecznie i dynamicznie.
>> Więc przypuszczam, że najprostszym sposobem, aby to zrobić,
prawdopodobnie utworzyć tablicę, prawda?
Najprostszym sposobem składowania jest ci może utworzyć tablicę 140.000 słów
i po prostu umieścić je wszystkie tam i następnie przemierzać je wyszukiwania binarnego
lub poprzez wybór lub not-- Przepraszam, że się sortowanie.
Można je posortować, a następnie przechodzić je przez poszukiwaniu binarnym lub wyszukiwanie tylko liniowego
i właśnie końcowe słowa, ale to zajmuje ogromną ilość pamięci,
i to nie jest bardzo wydajny.
>> I tak mamy zamiar zacząć rozmawiać o sposobach dokonywania
nasz czas pracy bardziej efektywne.
A naszym celem jest, aby Stała czasowa, gdzie
to prawie jak tablice, gdzie masz natychmiastowy dostęp.
Gdybym chciał szukać niczego, Chcę być w stanie po prostu,
boom, znaleźć go dokładnie i wyciągnij go.
I tak, w którym struktura będziemy stać bardzo blisko
aby móc przejść stałą czas, to Święty Graal
w programowaniu stałe Czas jest nazywany tabeli mieszania.
I tak Dawid wcześniej wspomniano, [Niesłyszalne] trochę w wykładzie,
ale będziemy naprawdę nurkowania w głębokim tym tygodniu
na kawałku, który jest w zakresie jak tabeli mieszania działa.
>> Więc ten sposób, że hash Prace tabeli, na przykład,
gdybym chciał przechowywać kilka słowy, kilka słów w języku angielskim,
Mógłbym teoretycznie umieścić banan, jabłko, kiwi, mango, pary,
i kantalupa wszystko na zaledwie tablicy.
Wszyscy mogli zmieścić się na nim i znaleźć.
To byłby rodzaj bólu przeszukiwania i dostępu,
ale łatwiej to sposobem jest że możemy stworzyć naprawdę struktura
nazywany tabeli mieszania gdzie hash.
Prowadzimy wszystkie nasze klucze przez funkcja skrótu, równanie,
które zamienia je wszystkie do jakieś wartości
które następnie możemy przechowywać na zasadniczo tablica połączonej listy.
>> I tak oto, jeśli chcemy do przechowywania angielskie słowa,
mogliśmy potencjalnie prostu, nie wiem wiem, włączyć wszystkie pierwsze litery
do jakiejś liczby.
I tak, na przykład, gdybym chciał A, która będzie synonimem apple--
lub indeks 0 i B synonimem 1,
może mamy 26 wpisy , że można po prostu zapisać
wszystkie litery alfabet, że zaczniemy.
I wtedy możemy mieć apple w indeksie 0.
Możemy mieć banana na indeksie 1, kantalupa w indeksie 2,
i tak dalej i tak dalej.
I tak, jeśli chciałem szukać moja tablica mieszająca i dostęp jabłko,
Wiem, jabłko zaczyna się A, a ja wiem dokładnie,
że to musi być i hash Stół o indeksie 0, ponieważ
funkcji uprzednio przydzielony.
>> Więc nie wiem, jesteśmy program użytkownika, gdzie
będziesz oskarżony o Nie arbitrarily-- arbitralnie,
z próby w zamyśleniu myśleć o dobrych równań
być w stanie rozprzestrzeniać z wszystkich wartości
W ten sposób można łatwo uzyskać dostęp to później się jak równania
że Ty sam wiesz.
Więc w tym sensie, czy chcę, aby przejść do mango, wiem, och, to zaczyna się od m.
Musi ona być na wskaźniku 12.
Nie mam przeszukać wszystko.
Wiem exactly-- może po prostu udać się do indeks 12 i wyciągnąć to.
>> Każdy jasne, w jaki sposób funkcji skrótu stołu działa?
To trochę tylko bardziej złożonej tablicy.
To wszystko to jest.
OK.
>> Sądzę więc, że natkniemy się na to kwestia tego, co
dzieje się, jeśli masz wiele rzeczy które daje ten sam indeks?
Tak mówią naszej funkcji, wszystko to nie było przyjąć, że pierwszy list
i kolei, że w 0 do 25 odpowiedni wskaźnik.
To jest całkowicie w porządku, jeśli masz tylko jedno z każdej.
Ale drugi zaczniesz posiadające więcej, jesteś
będzie mieć to, co się nazywa kolizji.
>> Więc jeśli próbuję wstawić pogrzebać w hash Stół, który ma już na nim banany,
co się stanie, gdy próby wstawienia, że?
Złe rzeczy, bo banan już istnieje w indeksie
które chcesz przechowywać go w.
Berry rodzaj jest jak, ach, co mam zrobić?
Nie wiem, gdzie się udać.
Jak mogę rozwiązać ten problem?
>> I tak chłopaki będzie rodzaj zobacz robimy to trudne rzeczy
gdzie możemy rodzaj rzeczywistości stworzenia połączonej listy w naszych tablic.
I tak najłatwiej myśleć o tym,
wszystkie tabeli mieszania jest szereg powiązanych list.
I tak, w tym sensie, trzeba ten piękny, tablica wskaźników,
a następnie każdy wskaźnik w że wartość tego wskaźnika,
może faktycznie wskazywać na inne rzeczy.
A więc masz wszystkie te oddzielne łańcuchy pochodzące od jednej dużej tablicy.
>> I tak oto, jeśli chciał włożyć jagody,
Wiem, OK, mam zamiar wejścia to przez mój funkcji skrótu.
Mam zamiar skończyć z indeksem 1, a potem będę mieć możliwość
tylko mniejszy podzbiór ten Słownik gigant 140.000 słów.
A potem mogę tylko patrzeć przez 1/26 całości tego.
>> A tak, to mogę po prostu włóż Jagoda przed lub po banana
w tym przypadku?
Po, prawda?
I tak będziesz chciał wstawić ten węzeł po banana,
i tak masz zamiar wstawić w ogonie tego połączonego listy.
Mam zamiar wrócić do tego poprzedniego slajdu,
więc chłopaki widzą, jak Funkcja mieszająca działa.
>> Tak więc funkcja skrótu jest to równanie że używasz rodzaju danych wejściowych
dzięki, aby niezależnie od indeksu chcesz przypisać go do.
A więc, w tym przykładzie, wszystkie chcieliśmy zrobić, to podjąć pierwszą literę,
z kolei, że w indeksie, to można zapisać, że w naszej funkcji skrótu.
Wszystko, co robimy, to my jesteśmy przekształcanie pierwszej list.
Więc keykey [0] jest tylko pierwsza litera bez względu na ciąg my mamy,
przekazujemy w.
Jesteśmy konwersji, że do górnej i jesteśmy odjęcie od dużej litery A,
więc wszystko, co robi daje nam szereg
w którym możemy na naszych wartości hash.
>> I wtedy będziemy powrócić hash ROZMIAR moduł sprężystości.
Bądź bardzo ostrożny ponieważ teoretycznie tutaj
Twoja wartość skrótu może być nieskończona.
To może po prostu iść dalej i dalej i dalej.
To może być jakiś naprawdę, bardzo duża wartość,
ale z powodu swojej tablicy mieszającej, że utworzeniu ma tylko 26 indeksów,
Aby upewnić się, że modulusing tak, że
nie run-- to jest to samo rzeczą jako queue--
tak, że nie uciekł Dno swojej funkcji skrótu.
>> Chcesz owinąć go wokół w ten sam sposób, w [niesłyszalne], gdy
trzeba było tak bardzo, bardzo duża litera, to
nie chce, że do po prostu uciekł się do końca.
Tak samo tutaj, chcesz się upewnić, nie uciekać się do końca przez owinięcie
dokoła górnej części tabeli.
Więc to jest po prostu bardzo prosta funkcja skrótu.
Wszystko, co zrobiłem było podjąć pierwsze List jakiegokolwiek naszego wejścia było
i kolei, że w indeksie, że możemy umieścić na naszej tablicy mieszającej.
>> Tak, i tak jak powiedziałem wcześniej, sposób, że rozwiązania kolizji
w naszym hash tabele mają, To, co nazywamy, łańcuchowym.
Więc jeśli próbujesz wstawić wiele Słowa zaczynające się od tej samej rzeczy,
będziesz mieć jedną wartość skrótu.
Awokado i jabłko, jeśli już uruchomić go za pośrednictwem naszego funkcji skrótu,
zamiar dać Ci sam numer, numer 0.
I tak, jak nam się rozwiązać to że może faktycznie rodzaj połączyć je
połączonych ze sobą za pomocą list.
>> A więc w tym sensie chłopaki widzą rodzaju
, jak struktury danych, które byliśmy wcześniej ustawienie
jak rodzynki związane lista rodzaju od zbierają się w jedno.
I wtedy można tworzyć o wiele bardziej efektywnych struktur danych
które mogą obsługiwać większe ilości Dane, które dynamicznie zmieniać rozmiar w zależności
od potrzeb.
Każdy, jasne?
Każdy rodzaj jasne na to, co się tutaj dzieje?
>> Gdybym chciał insert-- co to jest owoc, który zaczyna się, nie wiem,
B, inne niż jagody, banan.
>> PUBLICZNOŚCI: Blackberry.
>> ANDI PENG: Blackberry, jeżyna.
Gdzie blackberry go tutaj?
Cóż, faktycznie nie klasyfikowane to jeszcze, ale teoretycznie
jeśli chcemy mieć to w porządku alfabetycznym,
gdzie należy BlackBerry iść?
>> PUBLICZNOŚCI: [niesłyszalne]
>> ANDI PENG: Dokładnie, po tu, prawda?
Ale ponieważ jest to bardzo trudne do reorder-- Myślę, że to zależy od was.
Możecie całkowicie wdrożenia, co chcesz.
Bardziej efektywny sposób Może to robić
byłoby uporządkować swoją powiązane listy w kolejności alfabetycznej,
i tak, gdy jesteś wkładając rzeczy, chcesz
mieć pewność, aby je wstawić w porządku alfabetycznym
tak, że wtedy, gdy jesteś starając się je wyszukać,
nie trzeba przemierzać wszystko.
Wiesz dokładnie, gdzie jest, i jest to łatwiejsze.
>> Ale jeśli rodzaju mają wszystko przeplatane losowo,
że wciąż będziemy mieć przemierzać go i tak.
I tak, jeśli chciałem po prostu włóż blackberry tutaj
i chciałem szukać to, wiem, oh, jeżyna
musi zaczynać się od indeksu 1, więc wiedzieć, natychmiast wystarczy poszukać na 1.
A potem mogę rodzaj przemierzać połączonej listy
dopóki nie dostanę się do Blackberry, i then-- tak?
>> PUBLICZNOŚCI: Jeśli próbujesz create-- Myślę, że w ten sposób jest bardzo prosty hash
funkcjonować.
A jeśli chcemy zrobić wiele warstw, które lubią,
OK, chcemy rozdzielić na jak wszystkie litery alfabetu
a następnie ponownie do jak inny zestaw liter alfabetu w tym,
mamy wprowadzenie jak hash Stół w tabeli mieszania,
lub jak funkcja w funkcji?
Albo jest that--
>> ANDI PENG: Więc twój hash function-- swoją tabeli mieszania
może być tak duży, jak tego chcesz.
Więc w tym sensie, myślałem, to było bardzo proste, bardzo
proste dla mnie właśnie rodzaj oparty na litery pierwszego wyrazu.
A więc nie tylko 26 opcji.
Mogę tylko 26 opcji z 0 do 25, bo może tylko
Zaczynamy od A do Z. Ale Jeśli chciał dodać, być może, więcej złożoność
lub krótszy czas pracy na swoje tablica mieszająca, absolutnie
może robić różne rzeczy.
Możesz tworzyć własne Równanie, które daje
więcej dystrybucyjnej w słowa, a następnie podczas wyszukiwania,
to będzie szybciej.
>> Jest to całkowicie do was jak chcesz do realizacji tego.
Pomyśl o tym jak tylko wiadra.
Gdybym chciał mieć 26 wiader, jadę
uporządkować rzeczy w tych wiader.
Ale będę mieć kilka rzeczy w każdym segmencie,
więc jeśli chcesz to zrobić szybsze i bardziej wydajne,
daj mi sto wiader.
>> Ale wtedy trzeba wymyślić sposób uporządkować rzeczy tak, że są one
w odpowiednim wiadra powinny być.
Ale wtedy, kiedy rzeczywiście zajrzeć do tego wiadra,
to dużo szybciej, ponieważ nie ma mniej rzeczy w każdym segmencie.
I tak, tak, to jest rzeczywiście sztuczka dla was w pset5
jest to, że będziesz zadanie po prostu stworzyć
to, co jest najbardziej efektywnym Funkcja można myśleć być
w stanie przechowywać i sprawdzić te wartości.
>> Całkowicie się z wami jednak chcesz to zrobić,
ale to jest naprawdę dobry punkt.
Że rodzaj logiki można Aby zacząć myśleć o
jest dobrze, to dlaczego nie mogę zrobić więcej wiadra.
I wtedy trzeba szukać mniej rzeczy, a następnie może ja
mają inną funkcję skrótu.
>> Tak, istnieje wiele sposobów, aby to zrobić zbior, niektóre są szybsze niż innych.
Jestem całkowicie zamiar po prostu zobaczyć, jak szybka był najszybszy chłopaki będą
być w stanie dostać swoje funkcje do pracy.
OK, wszyscy dobrze na tworzenia łańcuchów i cebulą tabele?
To rzeczywiście jak bardzo prosta koncepcję, jeśli myślisz o tym.
Wszystko to jest oddzielenie co Twoje wejścia są w wiadrach,
ich sortowania, a następnie przeszukiwania wymienia, że ​​nie jest związany z.
>> Chłodny.
W porządku, teraz mamy inny rodzaj struktury danych, które nazywa się drzewo.
Idziemy dalej i mówić o próbach które są wyraźnie różne,
lecz w tej samej kategorii.
Zasadniczo wszystkie drzewa jest zamiast organizowania danych w sposób liniowy
że tabeli mieszania does-- was wiesz, to zrobiło się góra i dno
a następnie rodzaj odwołuje się od it-- się Drzewo ma wierzchołek, który nazywasz korzeń,
i to ma liści wszystko wokół niego.
>> A więc wszystko co musisz tutaj jest tylko górny węzeł
który wskazuje na inne węzły, że punkty dla większej liczby węzłów, i tak dalej, i tak dalej.
I tak po prostu ma oddziały dzielenie.
To jest po prostu inny sposób organizacji Dane, i dlatego, że nazywają to drzewo,
wy just-- to tylko modelowane się wyglądać jak drzewo.
Dlatego nazywamy go drzewa.
>> Tablica mieszająca wygląda na stole.
Drzewo po prostu wygląda jak drzewo.
Wszystko to jest oddzielny sposób organizacji węzłów
w zależności od jakie są Twoje potrzeby.
>> Więc masz korzenie i to masz liści.
Sposób, w jaki możemy w szczególności myśleć o tym, że jest to drzewo binarne,
binarne drzewo jest po prostu Specyficzny rodzaj drzewa
gdzie każdy węzeł tylko punkty do co maksymalnie dwa inne węzły.
I tak tutaj masz wyraźne Symetria w drzewie
które ułatwia rodzaj wyglądać na to, co ceni jesteś bo wtedy
mają zawsze w lewo lub w prawo.
Nigdy nie jest jak lewej trzecia z lewy lub jedną czwartą od lewej.
To jest po prostu masz w lewo i prawo i można wyszukiwać jedna z tych dwóch.
A więc dlaczego jest to przydatne?
Sposób, że jest to przydatna jest, jeśli szukasz
przeszukiwać wartości, prawda?
Zamiast wdrażania binarne szukaj w tablicy błędów,
jeśli chcesz być w stanie włożyć węzłów i zabrać węzły do ​​woli, a także
zachować wyszukiwanie możliwości wyszukiwania binarnego.
Więc w ten sposób, jesteśmy rodzaj tricking-- pamiętam kiedy
powiedział związane listy nie można wyszukać binarny?
Jesteśmy rodzaj tworzenia struktury danych , że triki, które do pracy.
>> I tak, ponieważ związane listy są liniowe, one jedynie połączyć jeden po drugim.
Możemy rodzaju mają inny rodzaj wskaźników
które wskazują na różnych węzłach które mogą nam pomóc w poszukiwaniach.
I tak oto, gdybym chciał mają wyszukiwarki binarne drzewo,
Wiem, że moim środku, czy 55.
Idę tylko do tworzenia, że w moim środku, jak mój korzeń,
i wtedy będę mieć Wartości wydzielenia z niego.
>> Więc tutaj, jeśli będę szukać wartość 66, można rozpocząć na 55.
To 66 większa niż 55?
Tak to jest, więc wiem, mus wyszukiwać i n prawo wskaźnik tego drzewa.
Idę do 77.
OK jest 66 mniejszy lub większy niż 77?
To mniej niż, więc wiesz, oh, który ma być lewym węzłem.
>> I tak oto mamy rodzaj zachowania wszystkich wspaniałych rzeczy o tablicach,
tak jak dynamiczne skalowanie obiektów, będąc
możliwość wstawiania i usuwania do woli, nie martwiąc się o stałe
Ilość miejsca.
Nadal zachowuje wszystkie te cudowne rzeczy
a jednocześnie jest w stanie zachować zalogować i wyszukać czas wyszukiwania binarnego
że byliśmy tylko wcześniej w stanie uzyskać zwrot.
>> Chłodny struktura danych, rodzaj trudne do wdrożenia, węzeł.
Jak widać, wszystko to Jest to struktura węzła
jest to, że masz w lewo oraz prawo wskaźnik.
To wszystko to jest.
Tak, a nie tylko o X lub poprzedniego.
Masz w lewo lub w prawo, a następnie można rodzaj połączenia ich
jednak tak zdecydujesz.
>> OK, jesteśmy naprawdę dzieje tylko potrwać kilka minut.
Tak więc mamy zamiar wrócić tutaj.
Jak powiedziałem wcześniej, I niby wyjaśnione
logika, jak będzie przeszukiwać tego.
Mamy zamiar spróbować pseudocoding to, aby zobaczyć
czy możemy rodzaj zastosować sama logika wyszukiwania binarnego
do innego rodzaju struktury danych.
Jeśli chcecie wziąć jak para minut, aby po prostu o tym myśleć.
OK.
W porządku, będę właściwie tylko dać ci nie the--,
porozmawiamy o Pseudokod pierwszy.
Więc czy ktoś chce dać ukłucie na to, co
Pierwszą rzeczą, którą chcesz zrobić, gdy zaczynasz się przeszukiwanie jest?
Jeśli szukamy wartość 66, co jest
Pierwszą rzeczą, którą chcesz zrobić, jeśli chcemy wyszukiwanie binarne to drzewo?
>> PUBLICZNOŚCI: Chcesz spojrzeć w prawo i spojrzeć w lewo i zobaczyć [niesłyszalne]
większa liczba.
>> ANDI PENG: Tak, dokładnie.
Więc masz zamiar spojrzeć na root.
Jest wiele sposobów, możesz dzwonić Opisz węzeł rodzic twoi ludzie mówią.
Chciałbym powiedzieć, korzeń, ponieważ to jak korzeń drzewa.
Będziesz patrzeć na węzeł główny, a ty jesteś
zobaczymy jest 66 większa lub mniejsza niż 55.
A jeśli to większe niż, dobrze, że jest większa niż, gdzie chcemy wyglądać?
Gdzie chcemy szukać teraz, prawda?
Chcemy, aby przeszukać Prawa połowa tego drzewa.
>> Mamy więc, Dogodnie, wskaźnik, który wskazuje na prawo.
A tak, to możemy ustawić nasz nowy root, aby 77.
Możemy po prostu iść tam, gdzie wskaźnik wskazuje.
No, no, tu zaczynamy na 77, a tylko możemy
to zrobić rekurencyjnie ponownie i ponownie.
W ten sposób, rodzaj of mają funkcję.
Masz sposób poszukiwania, które Ciebie może po prostu powtarzać w kółko,
w zależności od tego, gdzie chcesz wyglądać aż w końcu dostać się do wartości
że szukasz.
Ma sens?
>> Mam zamiar pokazać rzeczywisty Kod, i to dużo kodu.
Nie ma potrzeby panikować.
Porozmawiamy za jego pośrednictwem.
>> Właściwie nie.
To był tylko pseudokod.
OK, to był tylko pseudokod, która jest nieco skomplikowane,
ale to jest całkowicie w porządku.
Każdy, stosując się tutaj?
Jeśli korzeń jest null, powrót fałszywe bo to oznacza,
nawet nie ma nic tam.
>> Jeśli korzeń n jest wartością, więc jeśli dzieje się jednym patrzysz,
to masz zamiar wrócić prawda bo wiesz, że go znalazłeś.
Ale jeśli wartość jest mniejsza niż root n, jesteś
będzie szukał w lewo dziecko lub lewy liść,
cokolwiek chcesz to nazwać.
I jeśli wartość jest większa niż root masz zamiar szukać odpowiedniego drzewa,
Następnie wystarczy uruchomić funkcję poprzez wyszukiwanie ponownie.
>> A jeśli korzeń jest null, że Oznacza to, że już dobiega końca?
Oznacza to, że nie masz więcej więcej liści szukać,
to wiesz, oh, domyślam się, że nie jest tutaj
bo po Przejrzałem całość i nie jest tutaj,
to po prostu nie może być tutaj.
>> Czy to ma sens dla każdego?
Tak to jest jak binarnego wyszukiwania konserwujący Możliwości związane list.
Fajne, a więc drugi typ struktury danych, które facetów
Można spróbować realizacji na pset, trzeba tylko wybrać jedną metodę.
Ale być może metodą alternatywną do tabela mieszania jest to, co nazywamy TRIE.
>> Wszystko trie jest to specyficzny rodzaj drzewa, które
ma wartości, które go do innych wartości.
Zamiast mającego binarne drzewa w tym znaczeniu, że tylko jeden
co może wskazywać na dwa, można mieć Punkt jedno z wielu, wielu rzeczy.
Jesteś w istocie są tablice wewnątrz której można przechowywać
wskaźniki, które wskazują na inne tablice.
>> Więc węzeł, w jaki sposób by zdefiniować TRIE
to chcemy mieć Boolean, c słowo, prawda?
Więc węzeł jest logiczna jak prawdziwe lub fałszywe,
przede wszystkim, na czele że tablica, jest to słowo?
Po drugie, chcesz mieć wskaźniki do tego, co reszta z nich.
Kompleks nieco, nieco abstrakcyjne, ale Wyjaśnię, co to wszystko znaczy.
>> Więc tutaj, na górze, jeśli Ciebie mają tablicą już oświadczył,
węzeł, gdzie masz Boolean wartość przechowywana w przód
które mówi, jest to słowo?
Czy nie jest to słowo?
I wtedy masz Reszta swojej tablicy, która
rzeczywiście przechowuje wszystkie możliwości co to może być.
Tak więc, na przykład, takie jak na górze masz
pierwszą rzeczą, która mówi, prawda, czy fałszywe, tak lub nie, jest to słowo.
>> I wtedy masz 0 do 26 litery, które można przechowywać.
Gdybym chciał szukać tutaj dla nietoperza, idę na górę
i szukam B. Uważam B w moim tablica, i tak wiem, OK, to B słowem?
B nie jest słowem, tak więc Muszę utrzymać wyszukiwanie.
Idę z B, i nie mogę się do Wskaźnik że B wskazuje na
i widzę kolejną tablicę informacji, taką samą strukturę, że mieliśmy wcześniej.
>> I here-- oh, następna List w [niesłyszalne] jest A.
Więc patrzymy w tej tablicy.
Znajdziemy wartość ósmy, a potem patrzę, oh,
hej, jest to, że słowa, to B-A słowo?
To nie jest słowo.
Musimy szukać dalej.
>> I tak to patrzymy, gdzie wskaźnik z punktów,
i wskazuje na inny sposób w które mamy większą wartość przechowywana.
I w końcu, mamy do B-A-T, który jest słowem.
A więc następnym razem patrzysz, masz zamiar
mieć, że sprawdzenie, tak, Funkcja logiczna to jest prawda.
I tak, w tym sensie, że jesteśmy rodzajem posiadania drzewa z tablic.
>> Tak więc można rodzaj wyszukiwania w dół.
Zamiast mieszania funkcję i przypisanie wartości, połączonej listy,
można po prostu zaimplementować trie, która wyszukuje downwords.
Naprawdę, naprawdę skomplikowane rzeczy.
Nie łatwo myśleć o tym, bo jestem jak plucie tak wiele struktur danych z
na ciebie, ale nie każdy rodzaj zrozumieć, jak logika to działa?
>> Ok fajnie.
Tak więc B-A-T, a następnie masz zamiar szukać.
Następnym razem, gdy będziemy aby zobaczyć, ach, hej, to prawda,
więc wiem, że to musi być słowo.
>> To samo dla zoo.
Więc chodzi o to teraz, jeśli chciał szukać zoo, teraz,
Aktualnie zoo nie jest słowo w naszym słowniku
bo jak chłopaki widać, Pierwszym miejscem, które mamy Boolean
powrót prawda jest na końcu zoom.
Mamy Z-O-O-M.
>> I tak oto, nie mamy słowo, zoo, w naszym słowniku
bo to pole wyboru nie jest zaznaczone.
Tak więc komputer nie działa wiem, że zoo jest słowo
ponieważ sposób, że mamy zapisana tylko zoom tutaj
faktycznie ma wartość logiczną Okazało się, że były prawdziwe.
Więc jeśli chcemy wstawić Słowo, zoo, do naszego słownika,
jak byśmy się do tego zabrać?
Co mamy zrobić, aby upewnić się, że nasze komputerowy wie, że Z-O-O jest słowem
i nie pierwsze słowo jest Z-O-O-M?
>> PUBLICZNOŚCI: [niesłyszalne]
>> ANDI PENG: Dokładnie, mamy Aby upewnić się, że
tu, że wartość logiczna jest zaznaczać, że to prawda.
Z-O-O, a następnie jedziemy do sprawdzenia, że więc wiemy dokładnie, hej, zoo to słowo.
Mam zamiar powiedzieć komputer, że jest to słowo tak
że gdy kontroli komputerowych, wie, że zoo jest słowo.
>> Bo pamiętam, wszystkie te dane struktury, to jest bardzo łatwe do nas
powiedzieć, oh, bat to słowo.
Zoo to słowo.
Zoom to słowo.
Ale kiedy jej budowę, komputer nie ma pojęcia.
>> Więc trzeba go dokładnie powiedzieć, w jakim punkcie jest to słowo?
W którym momencie to nie to słowo?
A w jakim punkcie zrobić I musisz szukać rzeczy,
oraz w jakim punkcie muszę iść dalej?
Każdy z dala od tego?
Chłodny.
>> I tak potem przychodzi Problem, jak byśmy się
go o wstawienie czegoś że faktycznie nie istnieje?
Więc powiedzmy, że chcemy, aby wstawić słowo, wanna, do naszego trie.
Jak Możecie zobaczyć jak obecnie wszystko, co mamy teraz jest B-A-T,
a ta nowa struktura danych nie miał kufel, że
Wskazał na null, ponieważ zakładamy, że, och, nie ma słów, po B-A-T,
dlaczego musimy zachować o rzeczy po tym T.
>> Jednak problem pojawia się, jeśli prawda chcesz mieć słowo, które przychodzi po
T-tych.
Jeśli masz wannę, jesteś będzie chciał się prawo H.
I tak sposób mamy zamiar zrobić to zamierzamy utworzyć osobny węzeł.
Nie jesteśmy przeznaczyć niezależnie od ilości pamięci dla nowej tablicy,
i mamy zamiar zmienić przypisanie wskaźników.
>> Mamy zamiar przypisać H Przede wszystkim, to null
mamy zamiar pozbyć.
My będziemy mieć z dołu litera h.
Jeśli widzimy H, chcemy go iść gdzieś indziej.
>> W tym miejscu możemy następnie sprawdzić się tak.
Jeśli hit H po T, oh, czym wiemy, że jest to słowo.
Boolean ma zamiar powrócić prawda.
Każdy jasne, w jaki sposób to się stało?
OK.
>> Tak więc zasadniczo wszystkich te struktury danych
że posunęliśmy się dzisiaj, mam przeszedł na nich bardzo, bardzo szybko,
a nie w znacznie szczegół, i to jest OK.
Po rozpoczęciu brudząc z nim, będziesz
śledzenia, gdzie wszystkie wskaźniki są,
co się dzieje w twoim struktury danych, et cetera.
Będą bardzo przydatne, i to do Ciebie,
faceci całkowicie dowiedzieć się, jak chcesz realizować rzeczy.
>> I tak pset4, z 5-- och, że jest źle.
Pset5 to błędy ortograficzne.
Jak powiedziałem wcześniej, będziesz raz ponownie pobrać kod źródłowy z nas.
Nie będzie trzy główne rzeczy będziesz pobierania.
Będziesz ściągnąć słowniki, KERS i teksty.
>> Wszystkie te rzeczy są są albo słowniki wyrazów
że chcemy, aby sprawdzić lub test informacji
że chcemy, aby Sprawdzanie pisowni.
I tak słowniki dajemy idziesz
dać rzeczywiste słowa, które chcemy można jakoś zapisać w sposób, który jest
bardziej wydajny niż tablicy.
A potem teksty są będzie to, co jesteśmy
z prośbą o sprawdzanie pisowni, aby upewnić się, wszystkie słowa są prawdziwe słowa nie.
>> I tak trzy bloki programy, które podamy
nazywane są dictionary.c, dictionary.h i speller.c.
A więc wszystko dictionary.c nie jest co jesteś proszony do wdrożenia.
Ładuje słowa.
To zaklęcie sprawdza je, a to sprawia, że ​​pewna że wszystko jest prawidłowo włożona.
>> diction.h jest tylko plik biblioteki oświadcza, że ​​wszystkie te funkcje.
I speller.c, mamy zamiar dać.
Nie musisz zmodyfikować nic z tego.
Wszystko speller.c się, że nie jest, ładuje go, sprawdza prędkość nim,
testuje benchmark jak jak szybko jesteś w stanie zrobić wszystko.
>> Jest to ortografii.
Tylko nie zadzieraj z nim, ale upewnij się, się, że rozumiem, co robi.
Używamy funkcji nazywa getrusage, że testuje wydajność swojego czaru
szachownica.
Wszystko to nie jest po prostu przetestować czas wszystko w swoim słowniku,
więc upewnij się, że rozumiem.
Należy uważać, aby nie bałagan z nim lub else rzeczy nie będzie działał poprawnie.
>> A większość to wyzwanie jest dla wy naprawdę zmienić dictionary.c.
Mamy zamiar dać 140.000 słowa w słowniku.
Mamy zamiar dać tekst Plik, który ma te słowa,
i chcemy, aby być w stanie zorganizować je do tabeli mieszania lub trie
bo gdy prosimy o pisowni check-- wyobrazić, jeśli czar
sprawdzenie jak Odysei Homera.
To jak ten ogromny, ogromny testu.
>> Wyobraź sobie, że każdy Słowo trzeba było szukać
poprzez szereg 140.000 wartości.
To by wziąć na zawsze za urządzenie do pracy.
Dlatego chcemy zorganizować nasz danych do bardziej efektywnych struktur danych
takie jak tabeli mieszania lub trie.
A potem Możecie rodzaju od kiedy szukać dostępu
rzeczy łatwiej i szybciej.
>> A więc należy uważać, aby rozwiązać kolizji.
Masz zamiar dostać kilka od słów, które zaczynają A.
Masz zamiar dostać kilka słów które zaczynają B. Do Ciebie
Chłopaki, jak chcesz go rozwiązać.
Być może chodzi o coś więcej wydajna funkcja skrótu
niż tylko pierwszej litery coś, i tak, że to do ciebie
Chłopaki rodzaj robić, co chcesz.
>> Może chcesz dodać wszystkie litery razem.
Może chcesz lubię robić dziwne rzeczy aby uwzględnić liczbę liter,
cokolwiek.
Do was, jak chcesz zrobić.
Jeśli chcesz zrobić tabeli mieszania, jeśli Ciebie chcesz spróbować TRIE, całkowicie do Ciebie.
Będę cię ostrzec przed czasem, że trie jest zazwyczaj nieco trudniejsze
tylko dlatego, że jest tam wiele więcej wskazówek, aby śledzić.
Ale całkowicie do was.
Jest to o wiele bardziej wydajne w większości przypadków.
Naprawdę chcesz być w stanie utrzymać utwór z wszystkich wskaźników.
Jak zrobić to samo że robię tutaj.
Gdy próbujesz włożyć wartości w tabeli mieszania lub usunąć,
upewnij się, że jesteś Naprawdę śledzenie
gdzie wszystko jest, bo to naprawdę łatwe, jeśli jestem
starając się włożyć jak słowo, Andy.
Powiedzmy, że to prawdziwe słowo, słowo, andy,
w gigantyczne liście A słowa.
>> Gdybym akurat przypisać zły wskaźnik, oops,
nie idzie na całość reszta mojego połączonej listy.
Teraz tylko słowo, mają to Andy, a teraz
wszystkie inne słowa Słownik zostały utracone.
A więc chcesz, aby upewnić się, śledzić wszystkich wskaźników
albo masz zamiar dostać ogromne problemy w kodzie.
Narysuj rzeczy ostrożnie, krok po kroku.
To sprawia, że ​​dużo łatwiej jest myśleć.
>> I wreszcie, chcesz być w stanie przetestować wydajność programu
na wielkim pokładzie.
Jeśli faceci potrwać spojrzeć na CS50 teraz,
mamy to, co się nazywa wielka płyta.
Jest to arkusz wynik najszybciej sprawdzanie pisowni razy we wszystkich CS50
teraz, myślę, że na szczyt, jak 10 Czasy Myślę osiem z nich to pracownicy.
Naprawdę chcemy, żebyście nas pokonać.
>> Każdy z nas próbowali wdrożyć Kod najszybciej jak to możliwe.
Chcemy, żebyście próbować zakwestionować nas i realizować szybciej niż każdy z nas
mogą.
I tak to jest naprawdę pierwszy raz, że jesteśmy
prosząc was zrobić pset, że naprawdę można zrobić w dowolnym sposobem
Ty chcesz.
>> Zawsze mówię, to jest bardziej podobny do rozwiązania rzeczywistych, prawda?
Mówię, hej, musisz to zrobić.
Zbudować program, który robi to dla mnie.
Czy jednak chcesz.
Wiem tylko, że chcę, aby przewinąć.
To twój wyzwaniem na ten tydzień.
Chłopaki, jedziemy dać ci zadanie.
Mamy zamiar dać wyzwanie.
I wtedy to do was całkowicie po prostu dowiedzieć się,
co to najszybszy i najbardziej skutecznym sposobem wdrożenia tego.
Tak?
>> PUBLICZNOŚCI: Czy mamy prawo, jeśli chciał badać szybsze sposoby
zrobić tabele mieszania w Internecie, nie możemy zrobić że i cytować kod kogoś innego?
ANDI PENG: Tak, całkowicie w porządku.
Więc jeśli macie przeczytać Spec, jest linia
w specyfikacji, która mówi, że chłopaki są całkowicie wolne do badań hash
funkcje na jakie są z szybszych funkcje skrótu
uruchomić rzeczy w jak długo, jak cytować tego kodu.
Więc niektórzy ludzie mają już zorientowali się, szybkich sposobów
robi warcaby czarów, z szybko sposobów przechowywania informacji.
Całkowicie do was, jeśli was chcą tylko brać, prawda?
Upewnij się, że powołując się na.
Naprawdę Wyzwaniem że staramy się sprawdzić
jest upewnienie się, że wiesz, Twój sposób wokół wskaźników.
Jak najdalej realizacji rzeczywista funkcja skrótu
i wymyślanie jak matematyka to zrobić,
Chłopaki można badać niezależnie Metody Internecie chcecie.
Tak?
>> PUBLICZNOŚCI: Czy możemy przytoczyć tylko za pomocą [niesłyszalne]?
>> ANDI PENG: Tak.
Możesz po prostu, w swoim komentarzu, można przytoczyć jak, oh,
zaczerpnięte z bla, bla, bla, funkcja skrótu.
Ktoś ma jakieś pytania?
My faktycznie breezed poprzez dziś sekcji.
Będę się tu odpowiedzieć na pytania, jak również.
>> Ponadto, jak już mówiłem, biuro godziny dzisiaj wieczorem i jutro.
Spec w tym tygodniu jest rzeczywiście bardzo proste i bardzo krótkie, aby czytać.
Proponuję przyjrzeć, po prostu przeczytanie całości niego.
>> I Zamyla właściwie poprowadzi Cię przez każdy z funkcjami
należy wdrożyć, a więc jest to bardzo, bardzo jasne, jak zrobić wszystko.
Wystarczy upewnić się, że jesteś śledzenie wskaźników.
Jest to bardzo trudne zbior.
>> To nie jest trudne, bo jak, oh, pojęcia są o wiele bardziej
trudne, albo trzeba się uczyć tyle nowa składnia sposób
że zrobiłeś dla ostatniego pset.
Ten pset jest trudne, ponieważ istnieje tak wiele wskazówek,
i to jest to bardzo, bardzo łatwy w raz masz błąd w kodzie nie być w stanie
dowiedzieć się, gdzie, że błąd jest.
>> I tak zupełna wiara w Ciebie Chłopaki, aby móc pokonać naszą [niesłyszalne]
pisownia.
I rzeczywiście nie mają żadnej pisemnej kopalni jeszcze, ale mam zamiar napisać do mnie.
Więc kiedy piszesz Ciebie, będę pisać do mnie.
Mam zamiar spróbować zrobić Kopalnia szybciej niż twój.
Zobaczymy, kto ma najszybszą.
>> I tak, będę zobacz wszystkie Jesteś tu: wtorek, chłopaki.
Będę uruchomić coś w rodzaju takiego warsztatu pset.
Wszystkie części tego tydzień są warsztaty pset,
więc chłopaki mają wiele możliwości o pomoc, godziny pracy, jak zawsze,
i naprawdę czekamy na przeczytaniu wszystkich kodu twoich ludzi.
Mam quizy się tutaj, jeśli faceci chcą się dostać tych.
To wszystko.