>> 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?