David J. MALAN: Dobrze. Tak więc zapraszamy do pierwszego w historii CS50 pośmiertna na quiz. Myśleliśmy, że będziemy zainaugurować tradycja ta w tym roku. I będzie to okazja przejść przez rozwiązania quizu. A my przyspieszyć lub spowolnić w oparciu na interesie tych tutaj. 

Tak, jesteś prawdopodobnie dlatego, że jesteś tu zainteresowany jak można mieć lub powinien odpowiedzieć niektóre z tych problemów. Więc dlaczego nie spojrzeć w tej części pierwsze? Więc coraz sznurki. Ten dał ci trzy różne wersje programu, który był, ostatecznie, Oznaczało uzyskać ciąg od użytkownika. Czy nie jest tak, że był w lewo, aby was do ustalenia. 

I zapytaliśmy w pytaniu 0, Przypuszczam, że jest w wersji 1 opracowany i wykonany. Dlatego program może się wysypać? Na pierwszy rzut oka, wszelkie sugestie dlaczego? Tak. 

PUBLICZNOŚCI: Więc Pamiętam to w poprzedni przykład, patrząc na char * s, a widząc skanowanie si zobaczyć, bo to wskaźnik, jak nie wpływać na to, co skanowane? Czy to s lub adres s? 

David J. MALAN: OK. Dobry. Tak więc ostatecznie źródłem problemu jest prawdopodobnie w stanie zredukować do tej zmiennej s. I to jest rzeczywiście zmienna. Typ danych tej zmiennej jest char *, co oznacza, że ​​będzie zawierać adres charakter. I na tym polega wgląd. To będzie zawierać adres charakter lub, bardziej ogólnie, adres pierwszego znaku Cały blok znaków. 

Ale Połów jest, że s skanowania, cel w życie, jest podany adres i podane Kod formatu, jak% s, przeczytaj Ciąg do kawałka pamięci pod tym adresem. Ale ponieważ nie ma znaku równości przed że średnik na pierwszy linii kodu, ponieważ w rzeczywistości nie przydzielić dowolną pamięć malloc, ponieważ w rzeczywistości nie przydzielić tablicę jakiegoś rozmiaru, wszystko robisz czyta użytkownika klawiatura w niektórych kompletne wartość śmieci, które jest w s domyślnie. Więc kursy masz zamiar wysypać jeśli że adres nie tak się stało jest to wartość, która się da, w rzeczywistości, napisz do. Tak źle nie przeznaczyć pamięć nie. 

Więc w pytaniu 1, poprosiliśmy, Przypuszczam, że jest w wersji 2 opracowany i wykonany. Dlaczego ten program może się wysypać? Więc ten jest mniej błędów. I jest tylko jedna oczywisty sposób, gdzie można wywołać segfault tutaj. I to jest tematyczna. Za każdym razem używamy c w pamięci, co można zrobić, aby wywołać segfault w wersji 2? 

PUBLICZNOŚCI: Jeśli używasz tego wejścia w ciąg znaków, który jest dłuższy niż 49 znaków. 

David J. MALAN: Dokładnie. Za każdym razem można zobaczyć coś o stałej długości jeśli chodzi o tablicę, twój Radar powinien zgasnąć, że może to być problematyczne, jeśli nie sprawdzając Granice tablicy. I to jest problem. Wciąż za pomocą scanf. Wciąż za pomocą% s, co oznacza, spróbuj czytać ciąg od użytkownika. Że będzie czytać do s, która, W tym momencie jest skutecznie adres pamięci kawałka czy jest to równoważne. To jest nazwa tablicy znaków z pamięci. 

Ale dokładnie to, jeśli czytasz ciąg że jest dłuższy niż 49 znaków, 49 bo trzeba pokój dla backslash 0, idziesz do przepełnienia że bufor. I może będziesz miał szczęście i być w stanie napisz 51-sze charakter, 52-ga, 53-sze. Ale w pewnym momencie, OS powie, nie. To na pewno nie jest pamięć masz prawo dotykać. I program będzie się wysypać. 

Tak więc, gdy powinien być dowolny heurystyczne czas masz stałą długość, masz aby upewnić się, że sprawdzanie długości o cokolwiek to jest, że próbujesz czytać do niego. 

PUBLICZNOŚCI: Więc do rozwiązania, że ​​można mieli faktycznie sprawdzania oświadczenia Czy długość większą lub mniejsza niż? 

David J. MALAN: Absolutnie. Musisz tylko warunek , który mówi, jeśli - czy raczej nie koniecznie wiedzieć z góry, ile znaków użytkownik będzie wpisać, ponieważ masz kurczaka i jaj. Nie, dopóki nie przeczytać w ze scanf można dowiedzieć się, jak długo to jest. Ale w tym momencie, nie jest za późno, bo już ją przeczytać w jakiś blok pamięci. Tak na marginesie, unika biblioteki CS50 Ten problem w ogóle, przywróć za pomocą fgetc. I odczytuje jeden znak na raz, tip-toeing wzdłuż, wiedząc, że nie może przelewać razie charakter czytasz po jednym na raz. 

Połów z wycofaniem GetString jest że musimy stale re-size że fragment pamięci, który jest po prostu ból. To wiele linii Kod do tego celu. Więc inne podejście byłoby faktycznie korzysta kuzyna, więc powiem, scanf. Istnieją warianty wielu z nich Funkcje, które faktycznie sprawdź długość ile znaków można odczytać maksymalnie. I można określić, nie czytaj więcej niż 50 znaków. Tak, że będzie to kolejne podejście, ale mniej przychylne większych nakładów. 

Więc pytanie 2 pyta, przypuszczam, że wersja 3 jest kompilowany i wykonywany. Dlatego, że program może się wysypać? Więc ten jest rzeczywiście taki sam odpowiedzieć, mimo że wygląda trochę bardziej wyszukane. Używamy malloc, która czuje się jak dajemy sobie więcej opcji. A następnie, że mamy uwolnienie Pamięć na końcu. To wciąż zaledwie 50 bajtów pamięci. Więc może nadal próbować czytać w 51, 52, 1000 bajtów. To się wysypać na dokładnie z tego samego powodu. 

Ale jest też inny powód. Co jeszcze może malloc zwrot oprócz adres kawałkiem pamięci? Może to zwróci null. A ponieważ nie jesteśmy sprawdzanie że możemy robić coś głupi z innego powodu, co jest, że możemy opowiadać scanf, przeczytaj Wejście użytkownika z klawiatury do 0 lokalizacji, AKA zerowy. I to też na pewno wywołać segfault. Więc dla celów quiz, w my by zaakceptowali albo jako tych, ważny powód. Jednym z nich jest identyczna. Jednym z nich jest trochę bardziej dopracowany. 

Wreszcie, w odniesieniu do programu jest Korzystanie z pamięci, jak zrobić w wersji 2 i wersja 3 różnią? Więc na co warto, widzieliśmy nieskończoną dostaw możliwe Odpowiedzi na to. A wśród odpowiedzi ludzi, co my nadzieję, ale przyjęte inne rzeczy, była jakaś wzmianka o Fakt, że w wersji 2 korzysta tak zwany stos. Wersja 3 jest za pomocą sterty. I funkcjonalnie, to naprawdę nie ma uczynić wszystko, że wielkiej różnicy. Na koniec dnia, wciąż dopiero się 50 bajtów pamięci. 

Ale to był jeden z możliwych odpowiedzi że szukaliśmy na. Ale zobaczymy, jak masz swoje quizy z powrotem z TFS, że zrobiliśmy przyjąć inne dyskusje na ich odmienne zastosowania pamięci, jak również. Ale stosu i sterty byłoby Prosta odpowiedź, aby przejść z. Masz pytanie? Daję ci Rob. 

ROB BOWDEN: Więc problemem 4. To jest to, w którym trzeba było wypełnić liczby bajtów ze wszystkich Te różne typy używane. Tak więc pierwszą rzeczą, którą widzimy. Zakładają architekturę 32-bitową, jak tego urządzenia CS50. Tak więc jedną z podstawowych rzeczy na temat 32-bitowych, które mówi nam, dokładnie, jak duża będzie wskaźnik być w architekturze. 

Więc od razu wiemy, że każdy wskaźnik typ jest 32-bitowy lub 4 bajty. Tak więc, patrząc przy tym stole, węzeł * jest typ wskaźnika. Że będzie to 4 bajty. Węzeł struct *, to jest dosłownie identyczna gwiazda węzła. I tak, że będzie to 4 bajty. String, więc to nie wygląda pointer jeszcze, ale typedef, ciąg jest tylko char *, które jest typ wskaźnika. Tak, że będzie to 4 bajty. 

Więc te trzy są wszystkie 4 bajty. Teraz, węzeł i uczeń są nieco bardziej skomplikowana. Więc patrząc na węźle i ucznia, widzimy węzeł jako liczba całkowita i wskaźnik. A uczeń jest dwa wskaźniki w jej wnętrzu. Więc przynajmniej tutaj w naszym przypadku, sposób które kończy się obliczanie rozmiaru ta struktura jest po prostu dodać wszystko to jest wewnątrz struktury. 

Więc dla węzła, mamy liczbę całkowitą, który wynosi 4 bajty. Mamy wskaźnik, który jest 4 bajty. I tak jeden węzeł będzie do podjęcia 8 bajtów. I podobnie dla ucznia, mamy wskaźnik to 4 bajty i innym wskaźnik to 4 bajty. Tak, że będzie do końca się jest 8 bajtów. Więc węzeł i studentów jest 8 bajtów. I te trzy są wszystkie 4 bajty. Pytania na ten temat? Tak. 

PUBLICZNOŚCI: Czy to był 64-bitowy architektura, czy to podwoić wszystkie z nich? 

ROB BOWDEN: To nie byłoby podwoić wszystkie z nich. Tak więc 64-bitowa architektura, to, znowu, Zmiany, które podstawową rzeczą, która wskaźnik jest teraz 64 bity. Tak. Więc wskaźnik wynosi 8 bajtów. Więc to, że były 4 bajty będą 8 bajtów. Uczeń, który był dwa wskaźniki, No, teraz to się jest 8 bajtów 8 bajtów. To się dzieje, aby 16 bajtów. 

Jednak wciąż jest węzeł 4 bajty. Więc ten wskaźnik będzie się 8 bajtów. Jest to 4 bajty. Tak się dzieje tylko węzeł być 12 bajtów. Wszelkie inne pytania dotyczące tego jednego? Tak więc następna, są kody stanu HTTP. I trzeba było opisać okoliczności , zgodnie z którymi mogą one być zwrócone. jeden problem, że słyszałem jakieś studentów jest to, że starali się zrobić Błędy są na końcu klienta. Tak więc, gdy staramy się, aby wniosek do serwera, coś się porządku na naszym celu. Ale ogólnie, kody te są zwracane przez serwer. Dlatego chcemy, aby dowiedzieć się, co się dzieje źle lub w prawo na serwerze, powoduje, że te rzeczy, które mają być zwrócone. A może tak, dlaczego serwer powraca Kod statusu 200? Wszelkie myśli? 

Tak. Więc coś o pomyślnym Wniosek przeszedł. I są w stanie powrócić co prosiłeś. Tak więc wszystko było w porządku. Co o 302 znaleziono? Tak. 

PUBLICZNOŚCI: serwer szukał za to, co szukasz. Ale nie mógł go znaleźć. Więc jest błąd. 

ROB BOWDEN: serwer był więc patrząc na to, co chciał. Więc po prostu patrząc tu 302 znalezionych, było w stanie go znaleźć. 

PUBLICZNOŚCI: Przepraszam. Znaleziono oznacza, że ​​zrobili go znaleźć. Przepraszam. 

ROB BOWDEN: Tak 302 stwierdzone. Serwer jest w stanie znaleźć co chciałeś. 

PUBLICZNOŚCI: Ale to nie pokazujemy go? 

ROB BOWDEN: różnica między to 302 200 jest to, że wie, co chcesz. Ale to nie jest dokładnie tam, gdzie chciałeś zapytać. Więc 302 to typowy przekierowanie. Więc wniosek strony. Wie, oh, chcę to do ciebie wrócić. Jest to jednak w innym URL. Więc hej, rzeczywiście chcesz tego. 

David J. MALAN: To jest kawałek, który powiedział: że daliśmy wam przekierowanie Funkcja używana funkcję nagłówka To z kolei, drukowane lokalizację okrężnicy, a następnie adres URL, który chcesz odrzucić użytkownika. Nawet jeśli nie widziałeś 302 tam wyraźnie, że co PHP będzie magicznie wstawić jako nagłówek mówiąc dokładnie to, co powiedział, że Rob - znaleziono. Ale go tutaj zamiast. 

ROB BOWDEN: OK. Więc co o 403 zakazane? 

PUBLICZNOŚCI: Myślę, że to, że serwer jest w zasadzie powiedzieć, że klient Nie można przejść do strony startowej. 

ROB BOWDEN: Więc tak. Cóż, typowa odpowiedź byliśmy spodziewałem się czegoś podobnego, plików nie chmodded odpowiednio. To prawdopodobnie w jakich okolicznościach je zobaczył. Ale nie ma powodu, że klient może być winy tutaj. Jest rzeczywiście inny kod statusu - 401. Tak więc są one bardzo podobne. 

401 jest nieuprawnione. I 403 jest zabronione. I tak można wyłącznie nieuprawnione uzyskać, jeśli nie jesteś zalogowany Ale może oznaczać zalogowaniu które są upoważnione. Ale jeśli jesteś już zalogowany i nadal nie ma uprawnień, a następnie można również uzyskać zabronione. Tak więc, jeśli jesteś zalogowany i nie mają zgody, zabronione jest również coś, co możesz dostać. 

David J. MALAN: I przez mechanizm którym problemy te są zwykle rozwiązany na serwerze jest przez co polecenie? Chmod, jeśli jest, rzeczywiście, uprawnienia wydać na pliku lub katalogu. 

ROB BOWDEN: A 404 nie znaleziono. Tak. Tak więc w przeciwieństwie do 302, w którym nie było dokładnie to, w którym prosisz, ale wie, co chcesz, to po prostu ma nie wiem, co chcesz. I nie żądają coś ważne. 418 Jestem czajnik, a następnie 500 wewnętrzny serwer. Dlaczego więc może masz? 

Więc segfault - Właściwie nie wiem, zaszeregowanie Norma tego. Ale jeśli Twój kod PHP coś złego w tym, teoretycznie, może to faktycznie wysypać, w tym przypadku, to 500 wewnętrzny błąd serwera, coś jest nie tak z Twojego serwera konfiguracja. Lub jest błąd składni w kodzie PHP. Lub coś złego się dzieje. 

David J. MALAN: Widzieliśmy segfault Wśród odpowiedzi kilka osób. I technicznie, to może się zdarzyć. Ale to byłoby PHP, program napisane przez innych ludzi, w rzeczywistości segfaulted, które tylko wtedy, gdy te osoby wkręca się i napisał kod w buggy by ich tłumacz Samo PHP wysypać. Tak więc mimo, że 500 jest jak segfault w duchu, to prawie zawsze wynikiem emisji pliku konfiguracyjnego z serwera WWW lub, jak Rob powiedział, błąd składni, jak ty nie zamknąć cytatów. Lub zgubiłeś średnik gdzieś. 

PUBLICZNOŚCI: Tak dla pset Shuttle, ja że kiedy zrobiłem to raz kliknąłem Przeglądarka, ale nic nie wymyślił, co nazywa biała strona. Ale to było ze względu na kod. Myślę, że była obsługa JavaScript, prawda? 

ROB BOWDEN: Tak. 

PUBLICZNOŚCI: Czy ten błąd jeszcze wymyślić? 

ROB BOWDEN: Więc to nie dostał ten błąd, bo wszystko z punktu widzenia serwera WWW było całkowicie w porządku. Ale o index.html. Zażądano shuttle.js i service.js. I było w stanie z powodzeniem powrócić do was wszystkich z tych rzeczy - 200. OK. To tylko wtedy, gdy Twoja przeglądarka próbował interpretują kod JavaScript, który to jak, czekaj, to nie jest ważny błąd JavaScript. Wszelkie inne pytania? Dobrze. 

David J. MALAN: Więc następna up był numer 11. I 11 był najstraszniejszy dla wielu ludzi. Więc najważniejsze jest, aby pamiętać o to, że jest to w istocie o listy dwukierunkowe. Ale to nie był taki sam jak w zeszłym roku podwójnie związany lista problemu, która nie daje zastrzeżeniem, że Lista ta może, w rzeczywistości, być sortowane. 

Tak więc fakt, że lista była nieposortowane i fakt, że to słowo było podkreślony nie miał przekazać że jest to faktycznie uproszczenie , co w przeciwnym razie byłoby trudniejsze problemem i dłuższa. Tak częstym błędem tutaj było wyprowadzić zeszłoroczny rozwiązanie na jeden pager, a następnie po prostu ślepo kopiować że w dół jako odpowiedź, co jest w porządku odpowiedzieć na inne pytanie podobne w duchu. Ale tu subtelności był następujący. 

Tak jeden, mamy zgłoszone i węzła określono w zwykły sposób tutaj. Następnie zdefiniowano lista być globalne wskaźnik zerowane. Potem najwyraźniej, nie dwie funkcje mamy prototypy tutaj, wkładka i usunąć. A potem mamy przykładowy kod tutaj robi kilka wstawek. A następnie prosimy o wypełnienie Realizacja takich poniżej wkładki sposób, że wchodzi n na liście w stałym czasie, podkreślił również, nawet jeśli już obecny. 

Tak więc piękno jest w stanie włożyć W czasie stałym jest to, że wiąże że trzeba włożyć nowy węzeł, gdzie? Do przodu. Więc to eliminuje, na szczęście, przynajmniej jeden z przypadków, które wymagają używanych jeszcze więcej linii kodu, jak to miało w zeszłym roku, a nawet w klasie, kiedy rozmawiał przez tego typu rzeczy z ludzi, a niektóre werbalne pseudo kod. Więc w tutaj rozwiązania, niech pominąć się, że po prostu mają na Visual ekran. 

Zauważ, że robimy, co następuje. A także zauważyć inne uproszczenia , że nawet jeżeli jest obecna, więc oznacza to, nawet jeśli Numer jest już tam, można ślepo wstawić inny kopia. I tak też, miało być uproszczenia, tak aby można było skupić się na naprawdę, niektóre z bardziej ciekawe intelektualnie część i nie tylko niektóre dodatkowe sprawdzanie błędów z uwagi na ograniczony czas. 

Tak więc w tym roztworze próbki, możemy przydzielić Wskaźnik na lewej bok, żeby węzeł. Teraz, uświadomić sobie, że wskaźnik, jak Rob powiedział, jest tylko 32 bitów. I faktycznie nie zawierają adres, dopóki nie przypisać mu adres. I robimy to na prawej z boku przez malloc. Jak dobry obywatel, możemy sprawdzić, że się przydzielić nie jest w rzeczywistości pusty, tak że nie przypadkowo utworzyć segfault tutaj. I za każdym razem użyć malloc w życiu, należy sprawdzanie wartości null, bo masz subtelny błąd. 

Potem zainicjować że NULL przypisywania N i poprzedni i następny. I w tym przypadku tutaj, zainicjowany poprzednia wartość null, ponieważ ten nowy Węzeł będzie nowy początku mojej listy. Więc nie będzie nic przed nim. I chcę w zasadzie dołączania istniejącej listy do nowego węzła przez ustawienie obok równa listy się. Ale ja nie skończyłem jeszcze. Więc jeśli sama lista już istnieje, i była co najmniej jeden węzeł już na miejscu, jeżeli jest to lista tu i wstawić nowy węzeł tutaj, należy upewnić się, że mój dawny węzeł wskazuje w tył do mojego nowego węzła, ponieważ jest to znowu listy dwukierunkowe. 

Więc robimy sprawdzenie poprawności. Jeśli lista jest pusta, czy jest już jeden lub więcej węzłów w nim, a następnie dodać, że z powrotem odniesienie tak powiem. A potem bardzo Ostatnią rzeczą musimy zrobić, to faktycznie zaktualizować globalny Zmienna lista sam punkt do tego nowego węzła. Tak. 

PUBLICZNOŚCI: W strzałkę wskaźnika [Niesłyszalne] jest równa null, robi radzić sobie z listy, ponieważ lista jest pusta? 

David J. MALAN: Nie. To jest po prostu mnie jest aktywnie uważać, że jeśli to jest moja Oryginalna lista z może trochę więcej węzłów tu, a ja wkładając moje tu nowy węzeł, nie będzie za nic tutaj. I chcę, aby uchwycić ten pomysł ustawiając poprzedni do wartość null na nowym węźle. I prawdopodobnie, jeśli mój kod jest poprawny i nie ma innego sposobu, aby wstawić węzły inne niż tej funkcji, Prawdopodobnie, nawet jeśli lista ma już jeden lub więcej węzłów w tym, przypuszczalnie lista, pierwszy węzeł, musiałby poprzedni wskaźnik samego null. 

PUBLICZNOŚCI: I tylko obserwacji. Powodem umieścić wskaźnik next równi Lista jest robisz wskaźnik przed tym, że list to wskazuje do następnego, tak myślę - Ja nie - po prostu można znaleźć? 

David J. MALAN: Dokładnie. A więc niech faktycznie rozważyć dwa przypadki tutaj naprawdę, choć zamów będziemy je brać pod uwagę nie jest zupełnie taki sam jak kod. Jednak na wysokim poziomie, jeśli stanowi listy i jest to 32-bitowy wskaźnik, najprostszy scenariusz jest że to jest null domyślnie. I przypuśćmy, że chcesz wstawić Numer 50 był pierwszy numer. Więc mam zamiar iść do przodu i przeznaczyć Węzeł, który będzie zawierać trzy pola - n, poprzedni i następny. 

Mam zamiar umieścić numer 50 tutaj, ponieważ będzie to n. To będzie dalej. I będzie to poprzednie. A więc co mam zrobić w tym przypadku? Cóż, po prostu zrobić linię 1 tutaj. Wskaźnik n pobiera n. Ja wtedy mówiąc, poprzednie powinien dostać wartość null. Więc to będzie puste. Potem mam zamiar powiedzieć, następny będzie lista dostać. 

I to po prostu działa dobrze. To jest null. I tak mówię, jest następny nowy węzeł pole powinno dostać cokolwiek to jest. Tak, że stawia inną wartość null tam. A następnie ostatnia rzecz Mam to sprawdzić tutaj. Jeśli lista nie jest równe NULL, ale jest równa null, więc pominąć, że całkowicie. I tak wszystko, co robić dalej jest lista dostaje wskaźnik, który powoduje obrazowo obraz tak. Więc to jest jeden ze scenariuszy. 

I jeden, który pytał o konkretnie jest taka sytuacja, gdzie mamy już listę jednego węzła. I jeśli wrócę w oryginale Oświadczenie problemem, obok będziemy wstawić powiedzmy jest 34, tylko dla dobra dyskusji. Więc mam zamiar po prostu wygodnie narysować, że tutaj. Właśnie malloced. Załóżmy, że mam sprawdzanie null. 

Teraz mam zamiar zainicjować n być 34. I będzie to n. To będzie dalej. I będzie to poprzednie. Upewnijmy się, że nie zrobił uzyskać to do tyłu. Poprzedni jest na pierwszym w definicji. Pozwól mi to naprawić. To poprzedni. To jest następna. Mimo iż są identyczne Niech tak zgodne. 

Poprzedni. To jest następna. Tak właśnie malloced moją uwagę, sprawdzone na null, przypisane 34 do węzła. Poprzedni dostaje puste. Tak, że daje mi to. Następne dostaje list. Więc lista jest to. Tak, to jest to samo teraz, jak ten rysunek strzałka, dzięki czemu wskazują one na jednej W taki sam. , A następnie sprawdzenie, czy mam listy nie jest równa null. I to nie jest ten czas. Potem idę do zrobienia poprzedni dostaje wskaźnik. 

Więc listy poprzedni dostaje PTR. Tak więc to nie ma wpływu wprowadzenie graficzny strzałka tutaj. I to się trochę faliste linie. A potem, na koniec, zaktualizować listy punkt do wskaźnika. Więc teraz to wskazuje na tego faceta. A teraz zróbmy szybkie sprawdzenie poprawności. 

Oto lista, która jest zmienna globalna. Pierwszy węzeł jest rzeczywiście, 34, ponieważ Śledzę tę strzałkę. I to jest prawidłowe, bo chcę wstaw na początku listy wszystkie nowe węzły. Jego następne pole prowadzi mnie do tego faceta. Jeśli wracamy, uderzyłem obok jest null. Więc nie ma więcej lista. Jeśli uderzę poprzedni, mam tam, gdzie spodziewam. 

Więc jest jeszcze kilka wskazówek, oczywiście, do manipulowania. Ale fakt, że powiedziano nam, aby zrobić to w czasie stałym oznacza, że ​​tylko ma skończoną liczbę rzeczy masz prawo to zrobić. I co to jest numer? Może to być jeden krok. Może to być dwa. Może to być 1000 kroków. Ale to jest skończone, co oznacza, że ​​nie możesz nie każdy rodzaj pętli dzieje tutaj nie rekurencji, nie pętle. Po prostu musi być zakodowane linie kodu, jak mamy w tej próbce. 

Więc następnym problemem poprosił nas o 12 zakończyć realizację usuń poniżej w taki sposób, że usuwa n z listy w czasie liniowym. Więc trzeba trochę więcej manewru teraz. Możesz założyć, że n, jeśli występuje na liście, będzie obecny nie więcej niż jeden raz. I to też ma być oparte na quiz uproszczenia założenie, więc że jeśli znajdziesz gdzieś numer 50 w liście, nie musisz również musiał martwić się o dalsze iteracji, szuka każdego możliwego kopia z 50, które właśnie przechodzą w pewnym Minutia w ograniczonym czasie. 

Więc remove, ten był zdecydowanie trudniejsze i bardziej Kod napisać. Ale na pierwszy rzut oka, szczerze mówiąc, to może spójrz zdecydowaną i jak coś nie ma mowy, można mieć wymyślić na quiz. Ale jeśli skupimy się na poszczególnych etapach, miejmy nadzieję, że będzie się nagle strajku, że każdy z tych pojedynczych kroków sprawia oczywisty sens z perspektywy czasu. Warto więc przyjrzeć. 

Więc po pierwsze, możemy zainicjować wskaźnik się lista się. Bo chcę czas liniowy, to znaczy Zamierzam mieć jakieś pętli. I powszechnym sposobem iteracyjne nad węzłami w strukturze listy lub jakiejkolwiek struktury iteracyjnie ma mieć wskaźnik do przodu dane struktury, a następnie po prostu uruchomić aktualizację to i iść na swój sposób przez strukturę danych. Więc mam zamiar zrobić dokładnie to. 

, Podczas gdy wskaźnik, moja zmienna tymczasowa, nie jest równe NULL, niech idź i sprawdź. Czy mi się poszczęści? Pole jest w węźle n jestem obecnie patrząc równa Numer szukam? A jeśli tak, zróbmy coś. Teraz, to zauważyć, jeśli stan otacza cały Poniższe wiersze kodu. To jest jedyna rzecz, dbam o - znalezienie liczbę mowa. Więc nie ma innego, co upraszcza rzeczy koncepcyjnie trochę. 

Ale teraz, uświadomiłam sobie, i możesz mieć tylko sobie z tego sprawę po myśli to przez trochę, tam właściwie dwa przypadki tutaj. W jednej z nich znajduje się węzeł początku listy, która jest trochę irytujące, bo to specjalny przypadek, ponieważ mamy do czynienia z tym czymś, co jest tylko anomalii. Wszędzie w liście, to jest to samo. Jest poprzedni i następny węzeł węzeł, węzeł poprzedni, następny węzeł. Ale ten facet jest trochę specjalne czy on jest na początku. 

Więc jeśli wskaźnik wynosi listę sam, więc jeśli jestem na początku lista i znalazłem n, muszę zrobić kilka rzeczy. Jeden, muszę przejść do listy pkt do następnego pola, 50. Więc przypuszczam, że staram usunięcie 34. Więc ten facet ma iść wyjazd za chwilę. 

Więc mam zamiar powiedzieć, lista dostaje pointer następny. Cóż, to jest wskazówka. Następny wskazuje tutaj. Tak to się zmienia to strzałka w prawo teraz zwrócić się do tego faceta tutaj. Teraz pamiętam, mamy tymczasowa zmienna. Więc nie osierocony wszystkie węzły, bo ja też mam ten facet w moim Realizacja Usuń. Więc teraz, jeśli lista nie jest sam w sobie null Potrzebuję, aby naprawić coś małego. 

Muszę się teraz upewnić, że ta strzałka, którą uprzednio wskazując od 50 do 34, to musi odejść, bo jeśli staram się pozbyć z 34, 50, lepiej nie utrzymywać żadnych rodzaju powrotem odniesienie do niego jako strzałka sugeruje. Tak właśnie zrobiłem tę linię. Więc skończę. Sprawa jest rzeczywiście bardzo proste. Odcięcie głowy listy jest stosunkowo proste. 

Niestety, nie jest to irytujące inny blok. Więc teraz muszę zająć się sprawą gdzie jest coś w środku. Ale to nie jest zbyt straszne, z wyjątkiem dla składni takiego. Więc jeśli nie jestem na początku lista, jestem gdzieś w środku. I ta linia tutaj mówi, początek bez względu na węzeł jesteś. Przejdź do następnego pola poprzedniego węzła i wskazują, że na wskaźnik. 

Zróbmy to obrazowo. Że był już skomplikowane. Więc jeśli mam poprzednie pola tutaj - zróbmy to - Kolejne pola tutaj. Mam zamiar uprościć swoje wskaźniki, a niż wyciągnąć całą masę rzeczy przecinających tam iz powrotem nawzajem. A teraz, powiedzmy, to jest 1, 2, 3 ze względu na dyskusji, nawet jednak, że nie jest w jednej linii z problemem w kwestii. 

Więc oto moja lista powiązana. Staram się usunąć w tym dwa szczególności wersja historii. Tak już zaktualizowany wskaźnik być skierowane do tego faceta. Więc to jest PTR. To wskazuje tutaj. Jest to lista, która istnieje w skali globalnej, jak wcześniej. A on wskazuje tutaj nie wiem co. A teraz, staram się usunąć dwa. 

Więc jeśli wskaźnik wskazuje tutaj, że jestem będzie śledzić, jak widać, poprzedni wskaźnik, który mnie stawia na 1. Ja wtedy powiedzieć, że obok Pole, które przynosi mnie do tego pudełko tutaj, będzie równy wskaźnik obok. Więc jeśli ten wskaźnik, to jest obok. To oznacza, że ​​ta strzałka potrzeby zwrócić się do tego faceta. 

To co, że linia kodu ma tylko zrobione jest trochę tego. A teraz to wygląda jak krok w dobrym kierunku. My w zasadzie chcą ciach 2 z w środku 1 i 3. Więc to ma sens, że chcemy Trasa tego wskaźnika wokół niego. Więc to kolejny wiersz jest sprawdzenie, czy wskaźnik obok nie jest pusta, nie ma Rzeczywiście ktoś po prawej 2, co oznacza, że ​​musimy także zrobić trochę ciach tutaj. 

Więc teraz trzeba się do tego wskaźnika i aktualizuje poprzedni wskaźnik na ten facet zrobić trochę obejścia tutaj punkt tutaj. A teraz, wizualnie jest to miłe. To jest trochę brudny, że nie jest w nikt nie wskazując na 2 więcej. 2 jest skierowany w lewą stronę. I 2 jest skierowany w prawą stronę. Ale on może robić, co chce, bo on o to, aby się uwolnił. I nie ma znaczenia, co te wartości są już. 

Ważne jest to, że pozostałe Chłopaki są trasy powyżej i poniżej niego. I rzeczywiście, to jest to, co robić dalej. Mamy wolne wskaźnik, co oznacza, że ​​powie system operacyjny, zapraszamy odzyskać to. I wtedy wreszcie wracamy. Inny sposób dorozumiany, jeśli jeszcze nie wrócił, Musimy szukać dalej. Więc wskaźnik wynosi wskaźnik obok tylko Oznacza przenieść ten facet tutaj. Przenieś ten facet tutaj. Przenieś ten facet tutaj, jeśli w rzeczywistości, nie znaleźliśmy numer mamy jeszcze szuka. 

Tak szczerze mówiąc, wygląda na całkowicie przytłaczające, jak sądzę, w pierwszym spojrzenie, zwłaszcza jeśli z trudem z tym podczas quizu to zobaczyć coś takiego. I poklepać się po plecach. Cóż, nie ma sposobu, mogłem wymyślić, że w quizie. Ale jestem zdania, możesz, jeśli przerwa to w dół do tych indywidualnych przypadków i tylko przez nie przejść starannie, choć, co prawda, w ramach stresujących okolicznościach. 

Na szczęście, obraz wykonany wszystko szczęśliwszy. Można narysować to w dowolną liczbę sposobów. Nie musisz robić przecinających rzecz tutaj. Można to zrobić z prostej linie takie jak ten. Ale sedno tego problemu, w Ogólnie rzecz biorąc, było uświadomienie sobie, że obraz w końcu powinien wyglądać trochę coś takiego, bo Stała czasowa do zrozumienia, że ​​można zachować zakłócenia i zacinanie i zagłuszania nowe węzły na początek z wykazu. Masz pytanie? Prawdopodobnie najtrudniejszych na pewno pytania kodowania. 

PUBLICZNOŚCI: Tak jest podobna do listy uderzeniem w poprzednich przykładach. 

David J. MALAN: Dokładnie, dokładnie. Po prostu inna nazwa dla zmienna globalna. Na całym świecie, co? 

ROB BOWDEN: OK. Więc to jest ten, w którym miał napisać pkt. Niektórzy ludzie pisali eseje na to pytanie. Ale po prostu trzeba korzystać z tych sześciu warunki aby opisać to, co się dzieje, gdy spróbować skontaktować facebook.com. Więc ja po prostu porozmawiać przez proces wykorzystując wszystkie te warunki. Tak więc w naszej przeglądarce wpisujemy facebook.com i naciśnij klawisz Enter. Więc nasza przeglądarka będzie konstruować HTTP żądania, że ​​zamierza wysłać przez jakiś proces do Facebook dla Facebook w odpowiedzi na nas z HTML jej strony. 

Tak więc to, co jest procesem które żądania HTTP faktycznie dostaje na Facebook? Więc po pierwsze, musimy tłumaczyć Facebook.com. Więc po prostu podana nazwa Facebook.com, gdzie faktycznie robi żądania HTTP trzeba iść? Więc musimy tłumaczyć Facebook.com na adres IP, który jednoznacznie identyfikuje urządzenie faktycznie Aby wysłać żądanie. Twój laptop ma adres IP. Wszystko, co związane z internetem zawiera adres IP. 

Więc DNS, Domain Name System, który jest co się dzieje w obsłudze tłumaczenie z facebook.com do adresu IP, który rzeczywiście chcesz się skontaktować. Więc serwery DNS kontakt i powiedzmy, co jest facebook.com? Mówi, och, to adres IP 190,212 coś, coś, coś. Dobrze. Teraz wiem, co urządzenie Chcę skontaktować. 

Więc wtedy wysłać żądanie HTTP na tej maszynie. Więc jak to się do tej maszyny? Cóż, wniosek przechodzi od routera do routera odrzuconych. Pamiętaj przykład w klasie, w której rzeczywiście widział drogę, która pakiety trwało kiedy próbowaliśmy komunikować. Widzieliśmy to skok przez Atlantyk Ocean w jednym punkcie lub cokolwiek. 

Więc ostatni port termin. Więc to jest teraz na komputerze. Można mieć wiele rzeczy obecnie komunikować się z Internetem. Więc mogę być uruchomiony, powiedzmy, Skype. Może mam przeglądarka open. Może mam coś, co torrenting pliki. Tak więc wszystkie te rzeczy są komunikacji z Internet w jakiś sposób. 

Tak więc, gdy komputer odbiera pewne dane z internetu, jak to wiedzieć, co rzeczywiście aplikacji chce dane? Jak to jest wiedzieć, czy ten konkretny danych jest przeznaczona dla torrenting aplikacji, w przeciwieństwie z przeglądarki? Więc to jest cel, że porty w wszystkie te aplikacje mają twierdził, port w komputerze. Więc przeglądarka mówi, hej, Jestem nasłuchuje na porcie 1000. I program torrenting mówi: Jestem nasłuchuje na porcie 3000. I Skype mówi używam portu 4000. 

Tak więc, gdy pojawi się jakieś dane, które należy do jednej z tych aplikacji, danych jest oznaczony, który port jest faktycznie należy przesłać wraz z. Więc to mówi, och, ja należę do portu 1000. Wiem, że to ja potrzebuję do przekazania tego wraz z moim przeglądarki. Więc powód jest istotne tutaj jest to, że często serwery www nasłuchuje na porcie 80. Więc kiedy kontakt Facebook.com, jestem komunikuje się z jakimś urządzeniem. Ale muszę powiedzieć, który z tego portu Maszyna chcę się komunikować. I serwery internetowe wydają się być nasłuchuje na porcie 80. 

Jeśli chcieli, mogli go ustawić tak, że można znaleźć w na porcie 7000. A następnie w przeglądarce internetowej, mogłem ręcznie wpisać Facebook.com: 7000 do wysłać żądanie do portu 7000 z serwera internetowej Facebook jest. 

David J. MALAN: I w tym przypadku, nawet choć nie wymaga, aby ludzie Wspominam o tym, w tym przypadku, co Port że wniosek rzeczywiście iść do? Spróbuj ponownie. Dokładnie. Nie patrząc na to, ale subtelność że tam nie ostatni. 

ROB BOWDEN: Więc HTTPS, ponieważ jest to specjalnie do słuchania szyfrowane, to na porcie 4430. 

WIDOWNI: 25 i e-maile są, prawda? 

David J. MALAN: Wychodzące e-maile, 25, yep. 

ROB BOWDEN: Ja nawet nie wiem, większość - wszystkie dolnych bywają zarezerwowane dla rzeczy. Myślę, że wszystko pod 1024 jest zarezerwowane. 

PUBLICZNOŚCI: Dlaczego mówisz 3 był zły numer? 

ROB BOWDEN: Bo w adresie IP, tam cztery grupy cyfr. I są one od 0 do 255. 192.168.2.1 jest tak powszechne lokalny adres IP w sieci. Zauważ, wszystkie z nich są mniejsze niż 255. Tak więc, gdy zacząłem z 300, które nie mogła mieć jednym z numerów. 

David J. MALAN: Ale to głupie clip od - był to CSI, gdzie mieli numer, który był zbyt duży na adres IP. 

ROB BOWDEN: Wszelkie pytania na ten temat? Następny, więc całkowita zmiana temat, ale mamy za to tablicy PHP domy w quadzie. I mamy listę nieuporządkowaną. I chcemy wydrukować element listy zawierającym nazwę tylko dom. Mamy więc pętli foreach. Więc pamiętaj, że składnia jest foreach tablicy jako elementu w tablicy. Tak więc za pomocą każdej iteracji pętli dom zajmie się na jednym z wartości wewnątrz tablicy. 

Na pierwszej iteracji, domu będzie Cabot Dom. Na drugiej iteracji, dom będzie być Courier budynku i tak dalej. Więc dla każdego quad jako domu, jesteśmy po prostu się do drukowania - również mogło echem - element listy, a następnie w domu Nazwa a następnie zamknąć pozycję z listy. Nawiasy klamrowe są tu obowiązkowe. 

I wtedy też, w odpowiedzi na pytanie Sam, pamiętaj, aby zamknąć nieuporządkowana lista znaczników. Więc musimy wyjść z trybu PHP w tym celu. Lub że nie powtórzył zamknij Lista nieuporządkowana znacznik. 

David J. MALAN: tu także dobrze byłoby było użyć starej szkoły dla Pętla z $ i = 0 0 i liczy do korzystania dowiedzieć się długość promienia. Całkowicie zbyt dobrze, po prostu trochę wordier. 

PUBLICZNOŚCI: Więc jeśli jechaliśmy [Niesłyszalne], by to zrobić - I zapomnieć, co pętla [niesłyszalne] jest. Czy $ wspornik quad I? 

David J. MALAN: Dokładnie. Tak, dokładnie. 

ROB BOWDEN: Coś jeszcze? 

David J. MALAN: Dobrze. Kompromisy. Tak było kiści odpowiedzi możliwe dla każdej z nich. Byliśmy naprawdę tylko szukasz coś atrakcyjne dla wzrostu inflacji oraz minusem. I numer 16 zapytałem, weryfikacji użytkowników ' Wejście po stronie klienta, jak z JavaScript, zamiast po stronie serwera, jak w PHP. Więc co jest z góry robi po stronie klienta? 

Cóż, jedna z rzeczy, które proponowane jest że zmniejszenie opóźnienia, ponieważ nie muszą się martwić kontaktując serwer, który może potrwać kilka milisekundy lub nawet kilka sekund poprzez unikanie, że i tak zatwierdzanie użytkowników naliczonego po stronie klienta przez wywołania obsługi na przedłożenie i Sprawdzam, czy ich typ coś na imię? Oni wpisać coś w na adres e-mail? Oni wybrać akademiku z rozwijane menu? 

Możesz dać im natychmiastową informację zwrotną przy użyciu komputera gigaherca lub co mają to faktycznie na biurku. Więc to jest po prostu lepsza użytkownika doświadczyć typowo. Ale minusem robić po stronie klienta walidacji, jeśli robisz to bez również robi walidację po stronie serwera jest to, że Najbardziej ktoś wychodzi z CS50 wie , że można po prostu wysyłać dane, które chcesz do serwera dowolną liczbę sposobów. Szczerze mówiąc, w niemal każdej przeglądarce, można Kliknij wokół w ustawieniach i po prostu wyłączyć JavaScript, która, w związku z tym, należy wyłączyć wszelkie formy walidacji. 

Ale także może przypomnieć, że nawet ja zrobił kilka rzeczy tajemne klasy za pomocą telnet i faktycznie udaje być przeglądarka wysyłając get żądania do serwera. I to nie jest na pewno za pomocą dowolnego JavaScript. To tylko ja, wpisując polecenia na klawiaturze. Tak naprawdę, każdy programista w ciągu wystarczająco komfort z sieci i HTTP może wysłać cokolwiek danych on chce do serwera bez sprawdzania. A jeśli twój serwer nie jest również sprawdzenie, oni dają mi nazwę, jest to faktycznie ważny adres e-mail, nie oni wybrać akademiku, może skończyć Wkładanie fałszywe dane lub po prostu puste do bazy danych, która prawdopodobnie nie będzie dobrze, jeśli zakładając, że pan tam był. 

Więc to jest denerwujące rzeczywistość. Ale w ogóle, po stronie klienta walidacja jest świetna. Ale to oznacza dwa razy więcej pracy. Chociaż tam nie istnieją różne biblioteki, biblioteki skryptów JavaScript wystąpienie, które sprawiają, że to dużo, mniej bólu głowy. I można ponownie wykorzystać niektóre z kodem po stronie serwera, po stronie klienta. Ale zdają sobie sprawy, że jest to zazwyczaj dodatkowa praca. Tak. 

PUBLICZNOŚCI: Tak, jeśli tylko powiedział mniej bezpieczne - 

David J. MALAN: [śmieje się] Fuj. To są zawsze trudniejsze te, do orzekania. 

ROB BOWDEN: że zostały przyjęte. 

David J. MALAN: Co? 

ROB BOWDEN: Stworzyłem ten problem. , Które zostały przyjęte. 

David J. MALAN: Tak. 

PUBLICZNOŚCI: Cool. 

ROB BOWDEN: Ale my nie akceptujemy do pierwszej - dobrze, co szukaliśmy jest coś jak ty nie musisz komunikować się z serwerem. Nie akceptujemy tylko szybciej. 

PUBLICZNOŚCI: Co nie przeładować stronę? 

ROB BOWDEN: Tak. To było akceptowane odpowiedź. 

David J. MALAN: Wszystko gdzie czuliśmy to było bardziej prawdopodobne niż nie może że wiedział, co było mówiąc, co jest trudne linia do rysowania czasami. Korzystanie z połączonej listy zamiast tablicy, aby utrzymać sortowanie listy liczb całkowitych. Więc odwrotnie często powołują się związane Listy, które motywowane ich całość wprowadzenie było uzyskać dynamikę. Mogą rosnąć. Mogą one kurczyć. Więc nie trzeba skakać przez obręcze faktycznie utworzyć więcej pamięci z tablicą. Lub nie ma po prostu powiedzieć, przepraszam, użytkownik. Tablica jest wypełniona. Tak dynamiczny wzrost listy. Minusem jednak połączonych listach? 

PUBLICZNOŚCI: To jest liniowa. Wyszukiwanie w połączonej listy jest liniowa zamiast tego, co zalogowaniem 

David J. MALAN: Dokładnie. Wyszukiwanie w połączonej listy jest liniowy, nawet jeśli jest to sortowanie, ponieważ można tylko za te okruszki chleba, to Wskaźniki z początku listy do końca. Nie można wykorzystać swobodny dostęp i, w ten sposób, wyszukiwanie binarne, nawet jeśli jest to sortowane, że można zrobić z tablicą. I jest jeszcze inny koszt. Tak. 

PUBLICZNOŚCI: Pamięć nieskuteczne? 

David J. MALAN: Tak. Cóż, niekoniecznie powiedzieć nieefektywne. Ale to nie kosztuje więcej pamięci, bo trzeba 32 bity dla każdego węzeł dla dodatkowego wskaźnika, co przynajmniej dla pojedynczo połączonego listy. Teraz, jeśli tylko liczby całkowite i przechowywania dodajesz wskaźnik, że jest faktycznie niby nietrywialne. To podwojenie ilości pamięci. Ale w rzeczywistości, jeśli przechowywania powiązana lista strukturach, które mogą mieć 8 bajtów, 16 bajtów, a nawet więcej niż to, być może jest to mniej o marginalnym. Ale to jest koszt jednak. Więc jeden z tych nie mam było w porządku, jak downsides. 

18. Używanie PHP zamiast C napisać Program wiersza poleceń. Więc, jest to często korzystają z język jak PHP czy Ruby lub Python. Po prostu szybko otworzyć się w edytorze tekstu. Masz wiele więcej funkcji dostępne. PHP ma zlewozmywaka funkcji, natomiast w C, to bardzo, bardzo mało. W rzeczywistości, ludzie wiedzą na własnej skórze że nie masz tabel mieszania. Nie łączyli list. Jeśli chcesz te, trzeba wdrożyć je samodzielnie. 

Więc jeden plus z PHP, lub naprawdę każdy interpretowany język jest szybkość z którym można pisać kod. Ale minusem, widzieliśmy to, kiedy szybko przeniesiono na misspeller Wdrożenie w wykładzie z wykorzystaniem PHP, jest że stosując interpretować język jest wolniejsze. I widzieliśmy, że w sposób oczywisty z zwiększa się w czasie od 0,3 sekund do 3 sekund, z powodu interpretacji że faktycznie się dzieje. 

Kolejny górą był, że ci nie trzeba kompilować. Więc to także przyspiesza rozwój nawiasem mówiąc, bo nie mają dwa kroki do uruchomienia programu. Musisz tylko jeden. A więc to jest dość przekonujące, jak również. Korzystanie z bazy danych SQL, a nie CSV do przechowywania danych. Więc wykorzystywana jest baza danych SQL dla pset7. Pliki CSV można nie używać dużo. Ale używane to pośrednio, jak w pset7 dobrze rozmawiając z Yahoo Finance. 

Ale jest jak CSV do pliku programu Excel, ale bardzo prosty, w którym kolumny są tylko demarked przecinkami wewnątrz skądinąd pliku tekstowego. I korzystania z bazy danych SQL jest trochę bardziej przekonujące. To plus, bo można dostać rzeczy jak wybrać i wstawić i usunąć. I masz, indeksy, które przypuszczalnie MySQL oraz inne bazy danych, takie jak Oracle, zbudować dla Ciebie w pamięci, które oznacza, że ​​prawdopodobnie nie jest wybrać będzie liniowy od góry do dołu. To naprawdę będzie coś jak poszukiwania binarnego lub coś podobne w duchu. Więc są one na ogół szybciej. 

Jednak minusem jest to, że to jest po prostu więcej pracy. To więcej wysiłku. Musisz zrozumieć, bazy danych. Trzeba go ustawić. Trzeba, aby uruchomić serwer że baza danych. Musisz zrozumieć, jak go skonfigurować. To są właśnie te rodzaju kompromisy. Natomiast plik CSV, można utworzyć ją gedit. I jesteś dobry, aby przejść. Nie ma złożoność dalej. 

Korzystanie z TRIE zamiast tabeli mieszania z oddzielnym łańcuchowych do przechowywania Słownik słów przypominających z pset5. Więc próbuje odwrotnie, w teorii co najmniej, to co? Stały czas, co najmniej, jeśli jesteś mieszania na każdym z poszczególnych litery w słowa, jak ty może mieć dla pset5. To może być pięć, sześć hashe Sumy, czy jest pięć lub sześć litery w słowie. I to jest bardzo dobre. A jeśli nie ma górnej granicy, w jaki sposób długo twoje słowa może być, że jest rzeczywiście asymptotycznie Stała czasowa. 

Natomiast tabela hash z osobna łańcuchowym, problem jest z tym rodzaj struktury danych jest to, że wykonywanie swoich algorytmów zwykle zależy od wielu miejscach Już w strukturze danych. I to jest na pewno w przypadku sieci, w której można umieścić więcej rzeczy w tabeli mieszania, już ci Łańcuchy go, co oznacza, w najgorszym Sprawa, sprawa może być szukasz wszystko sposób na końcu jednej z tych łańcuchów, który skutecznie nakładanych na coś liniowego. 

Teraz, w praktyce może to absolutnie być tak, że z tabeli hash Łańcuchy jest większa niż odpowiadająca wdrożenie trie. Ale to z różnych powodów, między które próbuje wykorzystywać mnóstwo pamięci, która może, w rzeczywistości, powolne rzeczy w dół, bo nie dostaniesz ładne korzyści z czegoś, co nazywa buforowanie, gdzie rzeczy, które są blisko siebie w pamięci mogą być dostępne często szybciej. I czasami można wymyślić bardzo dobra funkcja skrótu. Nawet jeśli masz do stracenia trochę pamięci, to może rzeczywiście być w stanie znaleźć rzeczy szybko i nie tak źle, jak się liniowo. 

Tak w skrócie, nie było konieczności W każdej z tych jeden albo dwa konkretne rzeczy szukaliśmy. Naprawdę nic przekonujące jako pozytywnych i negatywnych ogólnie złapał nasze oko. 

ROB BOWDEN: Tak na plus, my nie przyjąć na swoim "szybciej". Ty miał powiedzieć coś na ten temat. Nawet jeśli powiedział teoretycznie szybszy, wiedzieliśmy, że niby rozumie że jest to 0 z 1. I tabeli mieszania, w teorii, Nie jest 0 o 1. Wspomnieć coś o czasie pracy generalnie mam Ci punkty. Ale "szybciej", większość rozwiązań na wielka płyta, które stara się obiektywnie wolniejszy od rozwiązań że były stoliki z cebulą. Więc szybciej w sobie Nie jest to prawda. 

David J. MALAN: Dom de dom dom. Jestem chyba jedynym, który zdaje sobie sprawę, to jak to ma wymawiać, prawda? 

ROB BOWDEN: Miałem naprawdę nie wiem. 

David J. MALAN: Wykonana sens w mojej głowie. 

ROB BOWDEN: robię to. OK. Więc to jest taki, w którym trzeba było wyciągnąć schemat podobny do ciebie może widziałem na ostatnich egzaminów. Więc po prostu patrzeć na to. Więc od węzła HTML, mamy dwa dzieci, głowy i ciała. Więc oddział - głowę i ciało. Głowica posiada tagu tytułu. Mamy więc tytuł. 

Teraz, jedna rzecz, wiele osób Zapomniałem, że te węzły tekstowe są elementy w tym drzewie. Więc tak się zwrócić je jak owale odróżnić je od tych rodzaje węzłów. Ale informacja także tu mamy góry, środkowy i dolny będzie w końcu jest węzły tekstowe. Więc był nieco zapominając tych wspólnej pomyłkę. 

Ciało ma trójkę dzieci - te trzy DIV. Więc div, div, div, a następnie tekst dzieci węzeł tych DIV. To dość dużo do tego pytania. 

David J. MALAN: A warto zauważyć, mimo że nie mieszkają na nich szczegóły w czasu spędzamy na Obsługę JavaScript w przeglądarce, że kolejność ma, w Fakt, sprawa technicznie. Więc jeśli szef jest przed ciałem w HTML, to powinno pojawić się pozostało z ciała w rzeczywistym DOM. Że jego jest, ogólnie rzecz biorąc, tylko do Twojej wiadomości, coś, co nazywa zamówienie dokument, w którym to ma znaczenie. A jeśli były wdrożenia parser, Program, który czyta HTML w budynku w górę drzewa w pamięci, aby być uczciwym, to jest prawdopodobnie to, co intuicyjnie nie tak - od góry do dołu, od lewej do prawej. 

ROB BOWDEN: Pytania na które? Należy zrobić następny? 

David J. MALAN: Jasne. 

ROB BOWDEN: OK. Więc to jest przepełnienie buforu Atak pytanie. Najważniejsze, aby rozpoznać tu jest, dobrze, jak przeciwnik może sztuczka program do wykonywania wybranego kodu? Więc argv1, pierwszy z linii poleceń argumentem do tego programu, który może być dowolnie długo. Ale tutaj używamy memcpy skopiować argv1, która tutaj jest bar. Przekazujemy go jako argumentu. I tak to trwa na pasku nazwy. 

Więc my memcpying bar w tym buforze C. Ile bajtów mamy kopiowania? Cóż jednak wiele dzieje się bar bajtów być używany, długość tego argumentu. Ale c jest tylko 12 bajtów szeroki. Jeśli więc wpisz w linii poleceń to jest więcej niż 12 bajtów, jesteśmy Ten będzie się przelewać szczególności bufor. Teraz, jak można oszukać przeciwnik zaprogramować na wykonanie dowolnego kodu? 

Więc pamiętaj, że tutaj Głównym dzwoni foo. I tak to główne połączenia foo. Miejmy wyciągnąć to. Więc mamy stos. I główny ma ramkę stosu na dole. W pewnym momencie, główne połączenia foo. Cóż, od razu, główne połączenia foo. I tak bla otrzymuje własne ramki stosu. 

Teraz, w pewnym momencie, bla zamierza powrócić. I poszedł powraca Foo, musimy wiedzieć, co co wiersz kodu wewnątrz głównej my były w celu poznania powinniśmy wznowić w głównym. Możemy wywołać foo od całości kilka różnych miejsc. Skąd mamy wiedzieć, gdzie się zwrócić? Cóż, musimy zapisać, że gdzieś. 

Więc gdzieś tu w prawo, możemy zapisać gdzie powinniśmy powrócić do raz powraca foo. I to jest adres zwrotny. Tak jak przeciwnik może wykorzystać tego jest to, że Bufor ten c jest zapisane, niech powiedzieć, tutaj jest c. Więc mamy 12 bajtów dla C. To jest c. I to jest pierścień stos Foo. Więc jeśli złośliwy użytkownik wpisze więcej bajtów niż 12 albo wpisać polecenie argument wiersza to dłużej niż 12 znaków, a następnie jedziemy do przepełnienie tego bufora. 

Możemy iść dalej. I w pewnym momencie, że daleko wystarczy, że zaczniemy nadpisywania ten adres zwrotny. Więc gdy tylko nadpisać adres powrotu, Oznacza to, że kiedy foo powraca, jesteśmy wszędzie tam, gdzie wraca do Złośliwy użytkownik mówi jej przez bez względu na wartość weszła, przez co znaków użytkownik wprowadził. I tak, jeśli użytkownik jest szkodliwy szczególnie mądry, to może on mieć powrócić do gdzieś w printDef Funkcja lub gdzieś w malloc funkcji, po prostu wszędzie arbitralne. 

Ale jeszcze bardziej sprytny, co oznacza, że ​​ma łatwy powrót do tutaj. A następnie rozpocząć wykonywanie je jako linii kodu. Więc w tym momencie, użytkownik może wprowadzić co chce w tym regionie. I ma pełną kontrolę nad swoim programem. Pytania na ten temat? Więc następne pytanie jest kompletny reimplementacja foo w taki sposób, że to już nie jest zagrożone. 

Więc jest kilka sposobów można tego zrobić. Mamy jeszcze c tylko jest długości 12. Można to zmieniły jako część rozwiązania. Dodaliśmy również sprawdzić, Nie był pewien bar zerowy. Chociaż nie trzeba że do pełnego kredytu. Więc sprawdzamy najpierw Długość ciąg bar. Jeśli jest to większa niż 12, a następnie faktycznie nie kopię. Więc to jest jeden sposób go naprawić. 

Innym sposobem mocowania to jest zamiast mając c tylko o długości 12, ma to być o długości strlen (bar). Innym sposobem jest mocowanie go faktycznie po prostu wrócić. Więc jeśli właśnie pozbyć wszystkich to, jeśli właśnie usunięte wszystkie linii kodu, możesz zdobyć pełny kredyt, od tej funkcji faktycznie nie osiągnąć niczego. To kopiowanie wiersza poleceń Argument do jakiejś tablicy w lokalna ramki stosu. I wtedy sprawa wraca. I cokolwiek to znakomity zniknął. Więc powrót był również wystarczający sposób pełny kredyt. 

David J. MALAN: Nie dość duch pytanie, ale do zaakceptowania za Spec jednak. 

ROB BOWDEN: Pytania na temat żadnej z tych rzeczy? Jedna rzecz, że co najmniej potrzebne są kompilacji kodu. Więc nawet jeśli nie są technicznie narażone, jeśli kod nie kompilacji, nie zaakceptować. Żadnych pytań? OK. 

David J. MALAN: Chcesz znaczy ten tytuł? 

ROB BOWDEN: Nie. 

David J. MALAN: Więc w tym jednym, to była albo dobra wiadomość czy zła wiadomość. To jest dosłownie sam problem jako pierwszy quiz. I jest to prawie to samo Problem jak pset1. Ale to było celowo uproszczone być prostsze piramidy, który może być rozwiązany nieco prostsze iteracji. A tak naprawdę, czego się w tutaj nie tyle logiki, bo prawdopodobnie przez to punkt, jesteś bardziej komfortowo niż było w tym tygodniu jeden z pętli lub dlaczego pętli, ale naprawdę drażnić siebie, że jesteś trochę wygodne z Pogląd, że PHP nie jest tylko o tym, co programowania. Można go rzeczywiście stosować jako język pisać programy linii poleceń. 

I rzeczywiście, to, co staraliśmy zwrócić uwagę. Jest to program PHP z linii poleceń. Więc kod C tutaj, podczas gdy prawidłowa w C, nie jest prawidłowy dla PHP. Jednakże kod jest rzeczywiście jest taka sama. Jeśli porównać rozwiązania Quiz 0 przeciw Quiz 1, przekonasz się, że jest prawie identyczne, z wyjątkiem niektóre znaki dolara i do Nieobecność typu. W szczególności, jeśli przyjrzymy się tutaj, zobaczysz, że iteracji, w tym przypadku, od 1 aż do 7. 

Mogliśmy zrobić to 0 indeks. Ale czasami myślę, że to po prostu psychicznie łatwiej myśleć o rzeczach od 1 do 7. Jeśli chcesz jeden blok, a następnie dwa bloki, a następnie trzy, a następnie kropka, kropka, kropka siedem. Mamy j inicjowany na 1 a następnie licząc na do i. I wszystko tu jest względami identyczne. Ale godne uwagi są Kilka rzeczy. Dajemy wam te dwie linie, to pierwszy jeden, goofily nazwany jako shebang do gwałtownego wybuchu. I to właśnie określa ścieżkę, folderu, w którym program może być okazało się, że chcesz użyć interpretować ten plik. 

A następnie linia po tym, z Oczywiście, oznacza wejście w tryb PHP. I linia na samym dole oznacza tryb wyjścia PHP. I działa w ogóle, z interpretowane języki. To trochę denerwujące, jeśli piszesz Program w pliku o nazwie foo.php. A następnie użytkownicy muszą tylko pamiętać, OK, aby uruchomić ten program, trzeba wpisać "kosmiczny php foo.php." Rodzaj irytujące, jeśli nic innego. I to również pokazuje, że program jest napisany w PHP, który nie jest wszystko że świetlnej dla użytkownika. 

Więc można usunąć. Całkowicie php pamiętam z wykładu. I rzeczywiście można zrobić. / Foo, jeśli masz chmodded go poprzez to wykonywalny. Więc chmod + x bla zrobiłby to. A jeśli dodać także shebang tutaj. Ale tak naprawdę, problem był już na drukując coś takiego. Nie HTML, nie ma na pewno kod C, tylko niektóre PHP. Więc Milo wrócił w błąd 25. I 25, to dano następujące Kod szkielet, który był dość prosta strona internetowa. I soczyste część HTML-mądry był w dół tu, gdzie mamy do wnętrza korpusu Formularz, który ma unikatowy identyfikator wejść wewnątrz której były dwa wejścia, jedno z pomysłem, jedna nazwa pomysł przycisku. 

Najpierw był tekst typ, drugi typ przedstawienia. I tak daliśmy ci, rzeczywiście, więcej składników, niż to konieczne, tak wy miał możliwości, z którymi rozwiązać ten problem. Nie muszą ściśle Wszystkie te ID. Ale to pozwala rozwiązać to na różne sposoby. I się w górę, zauważył, że celem było wywołanie okno jak ten - Witam, Milo! - pop-up w przeglądarce za pomocą bardzo proste, jeżeli nie brzydka, powiadomienie funkcję. I tak, w końcu, to sprowadza się koncepcyjnie jakoś nasłuchując Oświadczenia formularza po stronie klienta , A nie po stronie serwera, w jakiś odpowiadając na złożenie przez chwytając wartość wpisaną przez użytkownika w pola Nazwa, a następnie pokazujemy go w organizmie wpisu. 

Tak więc jednym ze sposobów można to zrobić, to z jQuery, która wygląda trochę składniowo kłopotliwy w pierwszej kolejności. Możesz to zrobić z czystego kodu DOM - document.getelement przez ID. Ale rzućmy okiem na tej wersji. Mam kilka ważnych Linie pierwszy. Tak jeden, mamy tę linię, która jest identyczne, co może widzieliście w, wierzę, form2.html z klasy w 9 tygodniu. I to jest po prostu mówiąc, wykonać Poniższy kod, gdy Dokument jest gotowy. To jest ważne, ponieważ tylko Strony HTML są czytane od góry do dolny, od lewej do prawej. 

A zatem, jeśli spróbujesz zrobić coś w kodzie tutaj do jakiegoś DOM Element, niektóre tag HTML, który znajduje się w dół tutaj, robisz to zbyt szybko, bo to nawet nie ma były wczytywane do pamięci. Więc mówiąc to document.ready linia, mówimy, Oto niektóre kodu, przeglądarka. Ale to nie do wykonania całości Dokument jest gotowy, to DOM drzewa istnieje w pamięci. Ten jest trochę bardziej proste, jeśli składniowo nieco inny, w którym mówię, grab Element HTML, którego unikalna Identyfikator jest wejść. To hash tag oznacza, unikatowy identyfikator. A potem dzwonię. Kliknij. 

Więc. Złożyć o to funkcja, w przeciwnym razie znana jako metoda, to wewnątrz obiektu, na lewym bok tam, że nie podkreślają. Więc jeśli uważasz, że wejść jako obiekt w pamięci - i rzeczywiście jest. Jest to węzeł w drzewie - . Przedstawienia środków, kiedy ta forma z identyfikator ten jest złożony, należy wykonać Poniższy kod. Nie obchodzi mnie to, co nazwa Funkcja jest mi wykonanie. Więc używam, tak jak poprzednio, co jest zwana funkcja lambda lub anonim funkcja. To nie jest w ogóle intelektualnie ciekawe, inne niż to ma nazwę, co jest w porządku, jeśli jesteś tylko kiedykolwiek będzie nazywać go raz. A w środku jest tak naprawdę obsłużyć Złożenie formularza. Ja najpierw zadeklarować zmienną zwana wartość. A potem to, co jest skutkiem tego podświetlona część tu teraz? Co to zrobić w wysoki poziom dla mnie? 

PUBLICZNOŚCI: To staje się, że wartość Użytkownik nie poniższy kod HTML. To staje się, że ID, a następnie wyszukuje wartość nim. 

David J. MALAN: Dokładnie. To chwyta węzeł, którego unikalna Identyfikator jest nazwa. Robi się w niej wartości, które jest, prawdopodobnie, co użytkownik wpisaniu go lub siebie. A następnie przechowuje, że w zmienną wartość. Tak na marginesie, może mieć także zrobić to trochę inaczej. Całkowicie do przyjęcia przez robienie czegoś var dostaje wartość kłamstwo document.getElementById. A to dlatego, że jest to mało nudne, aby nie używać jQuery. "Nazwa". Wartość. Tak całkowicie do przyjęcia. Różnych sposobów, aby to zrobić. jQuery tylko wydaje się być nieco bardziej zwięzłe i zdecydowanie bardziej popularne wśród programistów. 

Teraz robię się trochę normalności sprawdzić, bo w błąd oświadczenie, że wyraźnie powiedział, jeśli Użytkownik jeszcze nie wpisane jego lub jej Nazwa, nie wykazują alerty. Ale można sprawdzić, że po prostu sprawdzenie na pusty ciąg dla cytat-cytatu, jeśli istnieje nic faktycznie istnieje. Ale jeśli to nie jest równa cytatem-cytatu, Chcę zadzwonić alerty. I ciekawe jest to, że część używamy operatora plusa, który co robi w JavaScript? Złączyć. Tak to jest jak phps kropki. Sam pomysł, nieco inna składnia. A ja po prostu tworząc ciąg obejrzałeś na zrzucie ekranu - Witam, tak i tak. 

I wtedy jest to ostatni szczegół. Dlaczego return false wnętrze tej anonimowej funkcji? 

PUBLICZNOŚCI: Nie ma żadnej wartości. Można umieścić go w formie. To po prostu mówi, jeśli wartość nie jest równa się puste, to zrób to. Nie było puste w tym składania. 

David J. MALAN: OK. Ostrożny. Nie ma nikogo innego tutaj. I że fałszywa jest poza powrót o jeżeli warunki. Więc to podświetlony wiersz, return false, wykonywany bez względu na to, co po formularza. Co powrocie fałszywe wnętrze tego obsługi zdarzeń, jak to się nazywa, Wydarzenie, o którym mowa jest poddanie? 

PUBLICZNOŚCI: Ponieważ zdarza się tylko raz. 

David J. MALAN: dzieje tylko raz. Nie całkiem. Tak? 

PUBLICZNOŚCI: Zapobiega formularz z złożenie do domyślnego zachowania, które sprawiają, że odświeżyć stronę. 

David J. MALAN: Dokładnie. Więc jestem przeciążenia termin przedstawienia tutaj, bo mówię, forma jest składany. Ale jak to sugerują, że nie jest w rzeczywistości został złożony w prawdziwej drodze HTTP. Po kliknięciu przycisku Prześlij, ponieważ z naszych onSubmit obsługi, jesteśmy przechwytywania że złożenie formularza tak powiem. Mamy wtedy robi nasze rzeczy z kodem JavaScript. Ale ja celowo powrocie fałszywe, bo to, co nie chcę się stać Ułamek sekundy później jest dla całego formularza Sam należy składać w internecie Serwer z par wartości kluczowych poprzez zmianę Adres URL jest czymś q = koty lub co zrobiliśmy, na przykład w klasie. Nie chcę, żeby to się stało, bo nie ma do tego serwera słuchania Formularz zgłoszeniowy. Jest czysto zrobić w kodzie JavaScript. A to dlatego, że nie mają nawet przypisywać działanie na mojej postaci, bo nie zamierzam do tego, aby nigdy go na serwer. 

Więc to jest złożone. Ale mamy tę formę przechwytujące Składanie i zapobiegania domyślne Zachowanie to jest rzeczywiście przejść całą drogę do serwera. 

PUBLICZNOŚCI: Więc utrzymanie jej po stronie klienta. 

David J. MALAN: Prowadzenie to po stronie klienta. Dokładnie tak. Następna w kolejce była moja oh MySQL. 

ROB BOWDEN: OK. Więc to pierwsze pytanie było ogólnie szorstki dla ludzi. Choć późniejsze poszło lepiej. Więc trzeba było wybrać odpowiedni dane Typy na obu kolumnach. I obie z nich mają pewne rzeczy o nich, że dokonać wyboru trudne. Tak int nie ważne wpisać do liczby. Powodem jest konto 12-cyfrowy liczba, int nie jest wystarczająco duży, aby zapisać sumę cyfr. Tak ważny wybór byłby duży int jeśli zdarzy się, że. Innym wyborem może być pola char długości 12. Więc jeden z tych będzie pracował. Int nie. 

Teraz, równowaga, że ​​powrót do pset7. Więc specjalnie używane do dziesiętnych przechowywania wartości akcji lub - 

David J. MALAN: Gotówka. 

ROB BOWDEN: Gotówka. Użyliśmy dziesiętny przechowywać ilość pieniężne, które użytkownik ma obecnie. Więc powód, że to robimy bo pamiętam, pływa. Jest zmiennoprzecinkowych w precyzji. Nie można dokładnie przechowywać gotówkę Wartości takie jak chcemy tutaj. Więc po przecinku jest w stanie precyzyjnie sklep coś, powiedzmy, dwa miejsca po przecinku. Dlatego równowaga, chcemy go być po przecinku, a nie unosić. 

David J. MALAN: A także, też, choć może to być mądry w innych konteksty, aby myśleć, może to jest szansa na int. Ja po prostu śledzić rzeczy w groszach. Dlatego, że wyraźnie pokazał domyślne wartość jest 100.00, który Oznacza to może być po prostu int. I też z innego numeru subtelność było to, że nie miał być podchwytliwe pytanie. Ale przypominam, że int w MySQL, jak w C, co najmniej Urządzenie, jest 32-bitowy. I mimo, że nie spodziewam się dokładnie wiedzieć, ile cyfr, które środki, pamiętam, że największa liczba potencjalnie można reprezentować z liczbą 32-bitową jest mniej więcej to, co? 

Jaki numer zawsze mówimy? 2 do 32, co jest, co z grubsza? Nie musisz dokładnie wiedzieć. Ale z grubsza jest pomocne w życiu. To mniej więcej 4 mld. Więc powiedziałem, że już kilka razy. Wiem, że powiedział, że kilka razy. I to jest mniej więcej 4 mld. I to jest dobra zasada kciuka wiedzieć. Jeśli masz 8 bitów, 256 to magiczna liczba. Jeśli masz 32 bity, 4 mld mniej więcej. Więc jeśli tylko napisać 4000000000, zobaczysz, że jest to mniej cyfr niż 12, co oznacza, że ​​z pewnością nie jest wystarczy wyrazistość uchwycić 12-cyfrowy numer konta. 

ROB BOWDEN: OK. Więc gdy inne poszło lepiej. Więc załóżmy, że bank nakłada co miesiąc 20 dolarów Opłata za obsługę na wszystkich rachunkach. SQL kwerendy, co może bank odliczyć 20 dolarów od każdej liczby, nawet jeśli powoduje w niektórych negatywnych stanów? Więc w zasadzie, są cztery główne typy pytań - wstawić, wybierz, aktualizacji i usuwania. Więc co my myślimy, że jesteśmy zamiar użyć tutaj? Zaktualizować. 

Warto więc przyjrzeć. Więc tutaj mamy do aktualizacji. Co my aktualizacji tabeli konta? Więc aktualizacji konta. I wtedy składnia mówi, co na rachunkach mamy aktualizację? Cóż, mamy do ustawiania balansu równą Aktualna wartość salda minus 20. Więc to będzie zaktualizować wszystkie wiersze rachunków, odejmując 20 dolarów z równowagi. 

David J. MALAN: Częstym błędem tutaj, chociaż czasami to wybaczył, było rzeczywiście kod PHP tutaj wywołaniu funkcji kwerendy lub oddanie cytaty wokół wszystkiego, co nie trzeba tam być. 

ROB BOWDEN: Pamiętaj, że MySQL jest osobny język z PHP. Przyzwyczailiśmy się do pisania MySQL w PHP. I PHP jest następnie wysłanie go na serwer MySQL. Ale nie trzeba, aby PHP komunikować się z serwerem MySQL. 

David J. MALAN: Dokładnie. Więc nie ma zmienne z symbolem dolara powinna być w tym kontekście. To może po prostu zrobić wszystko z matematyki w samej bazy danych. 

ROB BOWDEN: OK. Więc następny. Czy to następny? Tak. Więc z tego, co SQL kwerenda może bank pobierać numery kont z jej najbogatszych klientów, tych z Salda większe niż 1000? Tak więc, który z czterech głównych typów będziemy chcieli tutaj? Wybierz. Więc chcemy wybrać. Czego chcemy się wybrać? Jakie kolumny chcemy wybrać? Będziemy konkretnie chcesz , aby wybrać numer. Ale jeśli mówi gwiazda, my Przyjmujemy również, że. 

Więc wybierz numer z jakim stole? Konta. A następnie stan chcemy? W przypadku, gdy saldo przekracza 1000. Przyjmujemy także większe niż lub równe. Ostatnia. SQL kwerendy, co może bank blisko, to znaczy usunąć wszystkie konta, które ma równowagę $ 0? Więc, który z czterech jesteśmy będzie chciał skorzystać? Usuń. Tak składnia, że? Usuń z jakiej tabeli? Konta. A następnie stan, w którym chcemy usunąć - gdzie równowaga jest równa zeru. Więc usunąć wszystkie wiersze z kont gdzie bilans jest zerowy. Pytania na każdy z nich? Chce stać w kolejce? 

David J. MALAN: Podręcznik kolejki. Więc w tym jednym, daliśmy wam dość zna strukturę, że badał nieco w klasie wraz z kodowanym, które to dane Struktura związana w duchu. Różnica jednak jest w kolejce że musieliśmy jakoś pamiętam kto był z przodu w kolejce, w dużych część tak, że mogliśmy zrobić więcej efektywne wykorzystanie pamięci, co najmniej jeśli byliśmy za pomocą tablicy. 

Ponieważ wycofanie, jeśli mamy tablicę, jeśli, na przykład, jest z przodu kolejki, jeśli dostanie się do kolejki tutaj, a potem ktoś dostaje w linii za mną, za mną, za mną, i jedna osoba wychodzi z linii, może, jak widzieliśmy niektóre z naszych ludzi wolontariuszy w klasie, wszyscy mają przesuwać w ten sposób. Ale w ogóle, że każdy robi coś nie jest najlepsze wykorzystanie czasu w programie, bo to znaczy, że Algorytm jest uruchomiony, w jaki asymptotycznej czas pracy? To jest liniowa. 

I czuję, że to głupie. Jeśli kolejna osoba w kolejce jest następny osoba, która ma przejść do sklep, nie mają poruszać się razem. Tylko niech ta osoba się wyrywałem kiedy przyjdzie czas, na przykład. Więc możemy zaoszczędzić trochę czasu tam. I tak to zrobić jednak, że środki że szef kolejki lub przód kolejki będzie stopniowego przesuwania się głębiej i głębiej do tablicy i ostatecznie może rzeczywiście owinąć wokół jeśli używamy tablica do przechowywania ludzi w tej kolejce. Więc można myśleć o prawie tablica danych w okrągłym Struktura w tym sensie. 

Więc jakoś trzeba śledzić rozmiar to czy naprawdę koniec tego a następnie, gdzie to jest początkiem. Więc proponuję zadeklarować jedna taka kolejka, wywołujący q to, tylko jedna litera. Następnie proponujemy, aby być z przodu ustawiany na zero, a wielkość być inicjowane na zero. 

Więc teraz nie ma nic wewnątrz tej kolejki. I prosimy, aby zakończyć Realizacja enqueue poniżej taki sposób, że funkcja dodaje się n koniec q, a następnie zwraca wartość true. Ale jeśli q jest pełna lub ujemny, Funkcja powinna zamiast return false. I daliśmy wam kilka założeń. Ale tak naprawdę nie są funkcjonalnie istotne, tylko że bool istnieje, ponieważ, technicznie, nie bool istnieją w C, chyba że zawierają pewien plik nagłówka. Tak, że po prostu upewnić się, że nie były to sztuczka Pytanie takie rzeczy. 

Więc enqueue, zaproponowaliśmy w próbce Roztwory do wykonania w sposób następujący. Jeden, najpierw sprawdzić, łatwość, owoce niskiej powieszenie. Jeśli kolejka jest pełna lub liczba, która próbujesz włożyć mniej od zera, w którym wspomniana Specyfikacja problemu należy Nie wolno, bo my tylko chcemy wartości nieujemne, to należy po prostu return false natychmiast. Więc niektóre stosunkowo łatwo sprawdzanie błędów. Jeśli jednak chcesz dodać, że rzeczywista numer, trzeba było zrobić trochę tu na myśli. I to, gdzie jest to trochę denerwujące psychicznie, bo trzeba dowiedzieć się, jak radzić sobie z zawijanym. 

Ale zalążek idei tutaj to z odsetki do nas jest to, że wraparound często oznacza arytmetyczny i modułowe mod operatora, strona procent, gdzie można iść z większej wartości do zera, a następnie jeden i dwa i trzy, a następnie powraca do zera jeden i dwa i trzy i tak dalej znowu i znowu. Więc sposób proponujemy ten sposób jest , że chcemy, aby indeks do gdzie macierz nazywa numery Nasze całkowite kłamać. Ale aby się tam dostać, najpierw chce zrobić niezależnie od wielkości kolejki jest tylko następnie dodać do tego, co Przód liście jest. A efekt to stawia nas w właściwej pozycji w kolejce i Nie zakładamy, że pierwsza osoba w kolejce ma miejsce na początku, który albo ona absolutnie może być, jeśli również przesunięcie wszystkich. Ale my tylko tworzenie pracy dla siebie, jeśli wzięliśmy że szczególnie droga. 

Więc możemy zachować to stosunkowo proste. Mamy pamiętać, że po prostu dodaje int do kolejki. A potem po prostu wrócić prawdziwe. Tymczasem w Dequeue, poprosiliśmy można wykonać następujące czynności. Wdrożyć w taki sposób, że dequeues, to usuwa i zwroty, Int. z przodu kolejki. Aby usunąć int wystarczy o tym zapomnieć. Nie trzeba zastąpić jej trochę. Więc to jest nadal faktycznie istnieje. Podobnie jak dane na dysku twardym, jesteśmy po prostu ignorując fakt, że to teraz jest. A jeśli q jest pusty, powinniśmy zamiast wrócić negatywny 1. Tak to czuje się arbitralne. Dlaczego powrót ujemne 1. zamiast fałsz? Tak. 

PUBLICZNOŚCI: P jest przechowywanie wartości dodatnie. Ponieważ tylko przechowywać wartości dodatnie w q, minusem jest błąd. 

David J. MALAN: OK, to prawda. Tak, ponieważ jesteśmy tylko przechowywania pozytywne wartości lub zera, to jest to w porządku, aby zwróci wartość ujemną, jako strażnik wartość, specjalny symbol. Ale jesteś przepisywanie historii tam, ponieważ powód, że jesteśmy tylko zwrotu wartości nieujemne to dlatego, że chcemy mają wartość wartownika. Tak dokładniej, dlaczego po prostu nie return false w przypadku błędów? Tak. 

PUBLICZNOŚCI: Ty nie powiodło się zwraca liczbę całkowitą. 

David J. MALAN: Dokładnie. I to, gdzie C dostaje dość ograniczający. Jeśli mówisz, że idziesz aby powrócić int, masz aby powrócić int. Nie można się kręci i rozpocząć powrót bool lub pływak lub ciąg lub coś w tym stylu. Teraz, w międzyczasie, PHP i JavaScript oraz inne języki może, w rzeczywistości, ty powrocie różne rodzaje wartości. , A w rzeczywistości może być użyteczne, tam gdzie można powrócić pozytywne wskazówki, zer, negatywne ints, lub false lub null, nawet oznaczać błąd. Ale nie mamy, że Wszechstronność w C. 

Więc z Dequeue, co Proponuję zrobić to - 

ROB BOWDEN: Możesz return false. Tyle, że nieprawdziwe jest hash define false do zera. Więc jeśli return false, Wracasz do zera. I zero to ważna rzecz w naszej kolejce, natomiast ujemne 1, jeśli nie jest fałszywe stało się ujemne 1. Jednak nie powinno się nawet musisz wiedzieć, że. 

David J. MALAN: To dlaczego nie powiedzieć. 

ROB BOWDEN: Ale to nie była prawda że nie można return false. 

David J. MALAN: Jasne. Więc Dequeue, zawiadomienia akceptujemy unieważnić jako argument. A to dlatego, że nie jesteśmy przechodząc nic w. Chcemy tylko, aby usunąć element na czele kolejki. Więc jak możemy to zabrać? Cóż, po pierwsze, zróbmy to szybkie sprawdzenie poprawności. Jeśli rozmiar kolejki wynosi 0, nie nie do zrobienia. Powrót ujemna 1. Gotowe. Więc to jest kilka linii mojego programu. Więc tylko cztery linie pozostają. 

Więc zdecyduję się zmniejszyć rozmiar. I skutecznie zmniejszanie rozmiaru Oznacza to, że ja zapominam coś tam jest. Ale mam też zaktualizować gdzie z przodu z numerami są. Tak, aby to zrobić, muszę zrobić dwie rzeczy. I najpierw trzeba sobie przypomnieć, co numer znajduje się w przedniej części kolejki ponieważ muszę wrócić tą rzecz. Więc nie chcę przypadkowo zapomnieć o tym, a następnie zastąpić ją. Idę do zapamiętania w int. 

A teraz chcę zaktualizować q.front być q.front 1. Więc jeśli jest to pierwsza osoba w linia, teraz, chcę zrobić plus 1 do wskazują na następnej osoby w kolejce. Ale mam do obsługi tego zawijanym. A jeśli pojemność jest globalna stała, że będzie pozwala mi się upewnić, jak wskazują na ostatniej osoby w Linia, operacja modulo przyniesie mnie z powrotem do zera z przodu kolejki. I że obsługuje Wraparound tutaj. A potem przystąpić do zwrotu n. 

Teraz, ściśle mówiąc, ja nie muszą zadeklarować n. Nie miałem chwycić go i przechowywać go czasowo, ponieważ wartość nadal. Więc może po prostu zrobić dobry arytmetyki powrót byłego szefa kolejki. Ale ja po prostu czułem, że było to bardziej oczywiste, rzeczywiście chwycić int, umieścić go w n, a następnie wrócić, że dla jasności, ale nie jest to konieczne. Psst. Oni wszyscy wymówienia w mojej głowie. 

ROB BOWDEN: Więc pierwsze pytanie jest drzewo binarne problemem. Więc pierwsze pytanie jest, że jesteśmy biorąc pod uwagę te liczby. I chcemy w jakiś sposób wstawić je do Te węzły, tak że jest ważne wyszukiwanie drzewo binarne. Więc jedna rzecz, aby pamiętać o drzewa wyszukiwań binarnych jest to, że nie jest to tylko, że coś się w lewo jest mniejszy i co do prawda jest większa. To musi być to, że całe drzewo do lewy jest mniej, a całe drzewo po prawej stronie jest większa. 

Więc jeśli mogę umieścić 34 tutaj na górze, a następnie Włożyłem 20 tutaj, więc to ważne, tak daleko, bo 34 się tutaj. 20 będzie w lewą stronę. Więc to jest mniej. Ale nie można wtedy umieścić tutaj 59, ponieważ mimo że fig. 59 po prawej stronie 20, to jeszcze po lewej 34. Więc z tego ograniczenia w umyśle, Prawdopodobnie najprostszym sposobem rozwiązania tego Problem jest tylko rodzaj z tych numerów - tak, 20, 34, 36, 52, 59, 106. A następnie włóż te od lewej do prawej. 

Więc 20 idzie tutaj. 34 idzie tutaj. 36 idzie tutaj. 52, 59, 106. A także może zorientowali się, z niektóre podłączając i realizacji, oh, czekaj, nie mam wystarczającej ilości numerów aby wypełnić to tutaj. Więc muszę reshift co moja uwaga trasa będzie. Jednak zauważyć, że w finałowej trójki, jeśli czytać od lewej do prawej, to jest w rosnące. 

Więc teraz, chcemy zadeklarować co struktura będzie dla węzły w tym drzewie. Więc co musimy w binarnym drzewie? Więc mamy wartość typu int, więc niektóre int wartość. Nie wiem, co nazywamy to w roztworze - int n. Musimy wskaźnik do lewego dziecka oraz wskaźnik do prawej dziecka. Tak to będzie wyglądać. I będzie to faktycznie wyglądać przed kiedy podwójnie związany Lista rzeczy, więc informacja - Będę musiał przejść wszystkie droga z powrotem do problemu 11. 

Więc zauważyć, że wygląda identycznie jak ta, chyba, że ​​akurat te nazywamy różne nazwy. Nadal mamy liczbę całkowitą wartość i dwa wskaźniki. Tyle, że zamiast leczenia wskazówek, jak wskazuje na następnej rzeczy i poprzedni rzeczą, traktujemy Wskaźniki wskazać na lewym dzieckiem oraz prawo dziecka. OK. Więc to jest nasz węzeł struct. A teraz tylko musimy funkcja wdrożenia tego jest trawers, który chcemy przejść przez drzewa, drukowania z wartościami drzewa w porządku. 

Więc patrząc tutaj, że chcemy wydrukować z 20, 34, 36, 52, 59 i 106. Jak możemy tego dokonać? Więc to jest bardzo podobne. Jeśli obejrzałeś egzaminu w przeszłości problem że chcesz wydrukować Całe drzewo między przecinkami wszystko, to faktycznie nawet łatwiejsze niż to. Więc tutaj jest rozwiązanie. Było to znacznie łatwiejsze jeśli nie to rekurencyjnie. Nie wiem, czy ktoś próbował to zrobić iteracyjnie. 

Ale po pierwsze, mamy sprawę podstawową. Co zrobić, jeśli korzeń jest null? Potem po prostu się do powrotu. Nie chcemy, aby wydrukować niczego. Jeszcze będziemy przemierzać rekurencyjnie w dół. Wydrukuj całą lewą poddrzewa. Więc drukować wszystko mniej od mojej aktualnej wartości. A potem mam zamiar wydrukować sobie. A potem mam zamiar rekursja dół moja Cała prawda poddrzewo, więc wszystko większa niż moja wartość. I to będzie drukować się, wszystko w porządku. Pytania na temat, jak to w rzeczywistości realizuje to? 

PUBLICZNOŚCI: Mam pytanie na [niesłyszalne]. 

ROB BOWDEN: Więc jeden sposób zbliża każdy rekurencyjne problemem jest po prostu, że o to jak trzeba myśleć o wszystkich przypadkach rożny. Więc uznać, że chcemy drukować całe to drzewo. Więc wszystko mamy zamiar skupić się na jest ten konkretny węzeł - 36. Wywołania rekurencyjne, udajemy ci, po prostu pracować. Więc, to wywołanie rekurencyjne trawers, że nawet bez myślenia o tym, po prostu przejazd w lewo trzy, wyobraź sobie, że już drukuje 20 i 34 dla nas. A potem, kiedy w końcu rekurencyjnie zadzwoń trawers na Dobrze, że będzie poprawnie wydrukować 52, 59, i 106 dla nas. 

Tak więc biorąc pod uwagę, że to może wydrukować 20, 34 i inne można drukować 52, 59, 108, wszystko, czego potrzebujesz, aby być w stanie to zrobić, to wydrukować Nas w środku tego. Więc drukować wszystko przed nami. Wydrukuj Nas, więc obecny węzeł druku 36, regularne printf, a następnie wydrukować wszystko po nas. 

David J. MALAN: To gdzie rekurencji robi się naprawdę piękne. To ten niesamowity skok wiary, gdzie ty najmniejszy kawałek pracy. A potem niech ktoś jeszcze zrobić resztę. I że ktoś inny jest, jak na ironię, ci. Tak poważnych punktów na ciastka, jeśli przewijania w górę na pytania - 

ROB BOWDEN: Na pytania? 

David J. MALAN: I trochę w dół numery, czy ktoś wie gdzie liczby te pochodzą z? 

ROB BOWDEN: Mam dosłownie nie wiem. 

David J. MALAN: Pojawiają się w całym quizie. 

PUBLICZNOŚCI: Czy są one takie same numery? 

David J. MALAN: Te liczby. Trochę jajko. Więc dla tych, oglądania online w domu, czy możesz nam powiedzieć, za pośrednictwem poczty elektronicznej do heads@CS50.net jakie znaczenie sześć z tych numerów są powtarzające całej Quiz 1, będziemy cię prysznic z niezwykłą dbałością w finale Wykład i piłka stres. Ładne, subtelne. 

Rob Bowden: Jakieś ostatnie pytania o wszystkim na quizie?