David J. Malan: U redu. Dakle, dobro došli u prvi CS50 obdukcija za kviz. Mislili smo da bi inaugurirati ta tradicija i ove godine. A to će biti prilika šetati rješenja na kvizu. I mi ćemo ubrzati ili usporiti temelji o interesu onih koji ovdje. 

Dakle, vjerojatno ste ovdje jer ste zanima kako ste mogli imati ili trebao imati odgovore na neka od ovih problema. Pa zašto ne bismo pogledati u ovom poglavlju prvo? Dakle sve konce. To vam je dao tri različite verzije programa koji je, u konačnici, značilo da se niz od korisnika. Hoće li ili ne to je da je lijeva na vama je da odredite. 

I pitali smo u pitanju 0, Pretpostavljam da je verzija 1 je sastavio i pogubljen. Zašto bi program SegFault? Na prvi pogled, bilo koji sugestija zašto? Da. 

Ivanković: Pa Sjećam Vidjevši to u natrag primjer gledajući char * s, a vidim skeniranje S i vide jer je pointer, kako je to utjecalo na ono što skeniraju u? Je to je i adresa s? 

David J. Malan: OK. Dobro. Dakle, u konačnici, izvor bilo problema je vjerojatno ide na smanjenje u tu varijablu s.. I to je doista promjenjiva. Tip podataka te varijable char *, što znači da će sadržavati adresu karaktera. I u tome leži uvid. To će sadržavati adresu lik ili, općenitije, adresu prvog znaka u Cijeli blok znakova. 

No, kvaka je u tome što je skeniranje, svrha u život je dao adresu i dao format koda, kao što je% s, čitanje string u komad memorije na toj adresi. No, budući da ne postoji znak jednakosti pred da zarez na prvi linija koda, jer mi zapravo ne izdvojiti bilo memoriju s malloc, jer to zapravo nije dodijeliti niz neke veličine, sve što radite je čitanje korisnika Tipkovnica ulaz u neke potpuna Vrijednost smeća, koje je s po defaultu. Dakle, šanse su da ćete, ako SegFault da adresa ne samo tako dogoditi da se vrijednost koju možete, u stvari, pišite. Tako loše da ne dodijeli vaša memorijska postoji. 

Dakle, u pitanju 1, pitali smo, Pretpostavljam da je verzija 2 je sastavio i pogubljen. Zašto bi ovaj program SegFault? Dakle, ovo je manje kolicima. I tu je zapravo samo jedan očigledan način gdje možete izazvati SegFault ovdje. I ovo je tematska. Svaki put smo pomoću C u memoriji, što možete učiniti kako bi potaknuli SegFault s verzijom 2? 

Ivanković: Ako koristite taj ulaz u niz koji je dulje od 49 godina likovi. 

David J. Malan: Točno. Svaki put kad vidim nešto fiksne duljine kada je u pitanju niz, vaš radar treba otići da bi to moglo biti problematično ako ne provjeravaš Granice niz. I to je problem ovdje. Mi još uvijek koristite scanf. Mi još uvijek koristite% s, što znači pokušati čitati niz od korisnika. To će se pročitati u sekundi, što, u ovom trenutku, je učinkovito adresa komad memorije ili je to ekvivalent. To je naziv niza znakova za pamćenje. 

No, upravo to, ako ste pročitali niz to je više od 49 znakova, 49 jer vam je potrebno prostora za backslash 0, ti ćeš se prelijevati da tampon. I da možete dobiti sretan i biti u mogućnosti napisati 51. karakter, 52., 53.. No, u nekom trenutku, OS će reći, nema. To definitivno nije memorije ti si dopušteno dirati. A program će SegFault. 

Dakle tamo, heuristika trebalo biti Vrijeme imaš fiksnu duljinu, imate kako bi bili sigurni da ste checking duljinu bez obzira na to je li pokušavate čitati u nju. 

Ivanković: Pa kako riješiti taj, što bi moglo imali provjeru zapravo izjavu je duljina veća od ili ispod? 

David J. Malan: Apsolutno. Vi samo imate stanje koji kaže da, ako je - odnosno ne nužno znati unaprijed koliko znakova korisnik će se upisati, jer imate kokoši i jajetu. Ne dok ste ga pročitali u sa scanf Možete li shvatiti koliko je to. No, u tom trenutku, to je prekasno, jer ste ga već pročitali u neki blok memorije. Dakle, kao na stranu, CS50 knjižnica izbjegava ovo pitanje uopce, opoziv pomoću fgetc. A on glasi jedan lik u isto vrijeme, savjet-toeing zajedno, znajući da vam Ne može se preliti lik ako čitate jednu po jednu. 

Kvaka je u getstring opoziva je da moramo stalno iznova veličinu koji komad memorije, što je samo bol. To je puno linija Šifra za to. Tako Drugi pristup bio bi da se zapravo koristiti rođaka, pa kažemo, scanf. Postoje varijante puno njih Funkcije koje zapravo provjeriti duljina koliko znakova možda pročitati maksimalno. A ti bi mogao navesti, nemojte čitati više od 50 znakova. Dakle, da bi se drugi pristup, ali manje susretljivi većih ulaza. 

Dakle, pitanje 2 pita, pretpostavimo tu verziju 3 je preveden i izveden. Zašto bi taj program SegFault? Dakle, ovo je zapravo ista odgovoriti, iako je to izgleda malo ljubitelj. Mi smo pomoću malloc, koja se osjeća kao dajemo sebi više opcija. I onda smo oslobađajući da memorija na kraju. To je još uvijek samo 50 bajtova memorije. Tako smo i dalje mogli pokušati pročitati u 51, 52, 1000 bajta. To će SegFault za isti razlog. 

Ali postoji još jedan razlog previše. Što bi drugo moglo malloc povratak osim adresa komad memorije? To bi mogla vratiti null. I zato nećemo provjeravati da, mogli bismo nešto raditi glupo zbog još jednog razloga, a to je da mogli bismo se reći scanf, pročitajte korisnikov ulaz s tipkovnice u 0 položaj, AKA null. I to je, također, će definitivno izazvati SegFault. Tako je za kviz svrhe, što bi prihvatili bilo onih što su valjani razlog. Jedan je identičan. Jedan je malo suptilniji. 

Na kraju, s obzirom na programu je Korištenje memorije, koliko je to verziju 2 i Verzija 3 razlikuju? Dakle, za ono što je vrijedno, što smo vidjeli Naizgled beskrajna opskrba moguće odgovori na to. A među odgovorima, što smo bili nadali, ali smo prihvatili druge stvari, bio je neki spomena Činjenica da je verzija 2 koristi tzv stog. Verzija 3 koristi hrpu. I funkcionalno, to zapravo nije napraviti sve što je mnogo razlika. Na kraju dana, mi smo još uvijek samo dobivanje 50 bajtova memorije. 

No, to je bio jedan od mogućih odgovora koje smo gledali. No, vidjet ćete, kao što ste dobili svoje kvizove vratio iz TFS, da smo učinili prihvatiti i druge rasprave o njihovom i različita upotreba memorije, kao dobro. No, stog i hrpa bi bila jednostavan odgovor da ide sa. Ima li pitanja? Dajem vam Rob. 

ROB Bowden: Dakle Problem 4. To je onaj gdje ste morali ispuniti u broju bajtova od svih te različite vrste koriste. Dakle, prva stvar koju vidimo. Pretpostavimo 32-bitnu arhitekturu, ovako CS50 uređaja. Dakle, jedna od temeljnih stvari o 32-bitne arhitekture, koja nam govori točno koliko je velika kazaljka ide da se u arhitekturi. 

Dakle, odmah smo znali da je bilo pokazivač tip je 32-bita ili 4 bajta. Dakle, u potrazi za ovim stolom, čvora * je pokazivač tipa. To će biti 4 bajta. Struct node *, to je doslovno identičan čvor zvijezde. A kako će biti 4 bajta. String, tako da ne izgleda kao pokazivač još, ali typedef, Niz je samo char *, koji je pokazivač tipa. Tako da će biti 4 bajta. 

Dakle, ova tri su sve 4 bajta. Sada, čvor i student su malo složeniji. Tako gledajući čvor i studenta, vidimo čvora kao cijeli broj i pokazivač. A student dva pokazivače unutar nje. Tako barem našem slučaju, način da smo završili izračunavanje veličine ovaj struct samo zbrojiti sve to je unutar struct. 

Tako je za čvor, imamo cijeli broj, što je 4 bajta. Imamo pointer, što je 4 bajta. I tako jedan čvor ide da se do 8 bajta. Ai za studenta, imamo pokazivač da je 4 bajta i drugi pokazivač da je 4 bajta. Tako da će se to završiti gore bitak 8 bajta. Dakle čvor i student su 8 bajta. I to je troje sve 4 bajta. Pitanja o tome? Da. 

PUBLIKA: Je li to bilo 64-bitni arhitektura, bi to udvostručiti sve od njih? 

ROB Bowden: To ne bi udvostručiti sve njih. Dakle, 64-bitna arhitektura, što, opet, Promjene koje temeljna stvar koja pointer je sada 64 bita. Da. Dakle pointer je 8 bajtova. Dakle, to da su 4 bajta će biti 8 bajtova. Student, koji je bio dva naputke, dobro, sada će se biti 8 bajtova, 8 bajta. To će napraviti 16 bajtova. 

Ali čvor je još uvijek 4 bajta. Dakle, ovo pointer ide biti 8 bajtova. To je 4 bajta. Dakle čvor ide samo biti 12 bajta. Bilo koja druga pitanja o toj jednoj? Dakle, sljedeći, to su su HTTP statusni kodovi. A što je to opisao okolnosti pod kojima se oni mogu biti vraćen. jedan problem koji sam čuo neke studente imam je da su pokušali napraviti Pogreške se na kraju klijenta. Dakle, kada smo pokušati napraviti zahtjev na poslužitelj, nešto pođe krivu na našem kraju. No, općenito, ovi kodovi se vratio na poslužitelju. Na taj način želimo shvatiti što se događa krivo ili pravo na poslužitelju koji uzrokuje da se takve stvari se vratio. Pa zašto bi poslužitelju vraća status kod 200? Bilo misli? 

Da. Dakle, nešto o uspješno Zahtjev je prošao. I oni su u mogućnosti da se vrate što god tražio. Dakle, sve je bilo u redu. Što o 302 pronašao? Da. 

PUBLIKA: server je u potrazi za ono što ste tražili. No, to nije mogao pronaći. Tako postoji greška. 

ROB Bowden: Dakle server bio u potrazi za ono što ste htjeli. Dakle, samo gleda ovdje, 302 pronašao, to je bio u mogućnosti da ga pronaći. 

Ivanković: Žao mi je. Pronađeno znači da su učinili ga pronaći. Oprostite. 

ROB Bowden: Dakle 302 pronađena. Poslužitelj može pronaći ono što ste htjeli. 

PUBLIKA: Ali to ne prikazuje? 

ROB Bowden: razlika između to 302 i 200 da se zna što želite. No, to nije točno gdje ste htjeli pitati. Dakle, 302 je tipičan za preusmjeravanje. Tako da je zatražio stranicu. Ona zna, ah, želim da ti ovo vratiti. No, to je na drugi URL. Pa hej, što zapravo želi. 

David J. Malan: To je komad koji je rekao da mi je dao vama momci preusmjeravanje funkcija koja koristi funkciju zaglavlja koji je, pak, isprintati mjesto, debelog crijeva, a zatim URL na koji Želite li odbaciti korisnika. Iako niste vidjeli 302 izrijekom postoji, to je ono što PHP bi magično umetnuti kao zaglavlju govoreći upravo ono što Rob je rekao da - pronašao. Ali ide ovdje umjesto. 

ROB Bowden: OK. Pa što je s 403 zabranjeno? 

Ivanković: Mislim da je to server je u osnovi kaže da klijent Ne može, internetsku stranicu. 

ROB Bowden: Pa da. Pa, tipični odgovor smo bili Očekujemo nešto poput, datoteke nisu chmodded odgovarajući način. To je vjerojatno i pod kojim uvjetima ste ih vidjeli. No, tu je razlog da klijent mogao biti u krivu ovdje. Tu je zapravo drugi status code - 401. Dakle, to su vrlo slični. 

401 je neovlašteno. I 403 je zabranjeno. I tako neovlašteno ste isključivo dobiti ako niste prijavljeni No, prijavite moglo značiti da ste ovlašteni. Ali, ako ste već prijavljeni a vi još uvijek nemaju dozvolu, a zatim također možete dobiti zabranjen. Dakle, ako ste prijavljeni i nemaju dopuštenja, zabranjeno je i nešto što možete dobiti. 

David J. Malan: A mehanizam po koja ti problemi su obično riješiti na poslužitelju je kroz koju naredbu? Chmod, ako je, doista, dozvole izdati na datoteku ili mapu. 

ROB Bowden: Nakon 404 not found. Da. Dakle, za razliku od 302, gdje to nije točno gdje ste tražili, ali ga ne zna što želite, to, to je samo nemam pojma što želiš. A ti se ne traži nešto vrijedi. 418 Ja sam čajnik, a zatim 500 unutarnji poslužitelj. Pa zašto bi ti to? 

Dakle SegFault - Ja zapravo ne znam ocjenjivanja standard za to. No, ako je vaš PHP kod imala nešto krivo u tome, u teoriji, to bi moglo zapravo SegFault, u tom slučaju, ova 500 Interna pogreška poslužitelja, nešto nije u redu s vašeg poslužitelja konfiguracije. Ili postoji greška sintakse u PHP kodu. Ili se nešto loše događa. 

David J. Malan: Nismo vidjeli SegFault među nekoliko ljudi odgovore. I tehnički, to bi se moglo dogoditi. No, da bi se PHP, Program napisana od strane drugih ljudi, zapravo segfaulted, koja samo ako ti ljudi zeznuo i napisao buggy kod u njihov tumač bi Sam PHP SegFault. Pa čak i da 500 je kao SegFault u duhu, to je gotovo uvijek rezultat problema s konfiguracijom datoteke na web poslužitelju ili, kao što je Rob je rekao, Pogreška sintakse, kao i ti nisu zatvorili citat. Ili ste izgubili-zarez negdje. 

Ivanković: Pa za pset Shuttle, ja mislim kad sam to učinio nakon što sam kliknuo Preglednik, ali nije bilo ništa gore, ono što oni nazivaju bijela stranica. Ali, to je bilo zbog koda. Mislim da je JavaScript, zar ne? 

ROB Bowden: Da. 

PUBLIKA: Bi li to pogreška još uvijek dolaze? 

ROB Bowden: Pa što ne bi dobio ova pogreška, jer je sve s web poslužitelja perspektive bio je potpuno u redu. No, što je zatražio index.html. Tražili ste shuttle.js i service.js. I to je bio u mogućnosti uspješno vratiti svima vama od tih stvari - 200. OK. To je samo kada vaš preglednik pokušali interpretirati JavaScript kôd koji To je kao, čekaj, to nije vrijedi JavaScript pogreška. Bilo koja druga pitanja? U redu. 

David J. Malan: Zato sljedeći gore je broj 11. A 11 je najstrašnija za puno ljudi. Dakle, najvažnija stvar je imati na umu ovdje je da je to, zapravo, o Popis dvostruko povezani. No, to nije bio isti kao i prošle godine dvostruko povezani popis problema, koji nije vam dati upozorenje da Popis bi, u stvari, biti nerazvrstani. 

Dakle, činjenica da je popis bio nerazvrstani i činjenica da je ta riječ bila podcrtavanje tu je trebao prenijeti da je to zapravo pojednostavljenje onoga što bi inače bio veći problem i duži. Tako česta pogreška je ovdje bila da su stavili prošlogodišnji rješenje na vašem jedan pager i onda samo slijepo kopirati da dolje kao odgovor, što je u pravu odgovor na drugo pitanje slični u duhu. Ali suptilnosti ovdje su kako slijedi. 

Dakle, mi smo čvor proglasila i definirana na uobičajeni način ovdje. Onda smo definirali popis biti globalni pokazivač inicijalizira na nulu. Onda je očito, ima dvije funkcije imamo prototipove ovdje, insert i ukloniti. A onda ćemo imati neki uzorak kod ovdje radiš hrpu umecima. A onda ćemo vas zamoliti da ispunite Provedba umetkom u nastavku, kao Način na koji on umeće n u popis u stalnom vrijeme, također je naglasio, čak i ako je već prisutna. 

Tako je lijepo biti u mogućnosti da biste umetnuli u stalnom vrijeme je da to podrazumijeva da imate umetnuti novi čvor gdje? U prednjem. Tako se eliminira, srećom, barem jedan od predmeta koji su nekada zahtijevaju čak i više linija koda, kao što je to učinio prošle godine, a čak u razredu, kada smo Razgovarali kroz ovakve stvari s ljudima i sa nekim verbalno pseudo code. Dakle, u otopini ovdje, neka je preskočiti da da samo da imaju vizualni zaslon. 

Uočite da radimo sljedeće. I također primijetiti drugi pojednostavljenje je da čak i ako je to Već danas, pa to znači da čak i ako broj je već tamo, možete samo slijepo umetnite drugi prijepis. I to je, također, je trebao biti pojednostavljenje, tako da bi mogao usredotočiti na, uistinu, neke više intelektualno zanimljiv dio i a ne samo neke dodatne provjere pogrešaka s obzirom na ograničeno vrijeme. 

Dakle, u ovom otopine uzorka, možemo izdvojiti pokazivač na lijevoj ruci stranu ovdje na čvoru. Sada, shvatiti da pokazivač, kao Rob je rekao, tek 32 bita. A to zapravo ne sadrže adresa do vas dodijeliti adresu. I mi to učiniti na desnom rukom strana putem malloc. Poput dobrog građanina, možemo provjeriti da malloc nije, u stvari, nula, tako da ne slučajno stvoriti SegFault ovdje. I svaki put kad koristiti malloc u životu, te treba provjera za ništa, da ne bi imate suptilan bug. 

Onda smo započeti taj null strane dodjeljivanje n i natrag i naprijed. I u ovom slučaju ovdje, ja inicijaliziran natrag na nulu, jer je ovaj novi čvora će biti novi počevši od moje liste. Dakle, tu će biti ništa prije toga. I ja želim biti dodati Postojeći popis na novi čvor postavljanje pored jednak uvrstiti. Ali nisam učinio samo još. Dakle, ako sama Popis je već postojala, a je najmanje jedan čvor već u mjesto, ako je to popis ovdje i ubacim novi čvor ovdje, ja potrebno kako bi bili sigurni da je moj bivši čvor ukazuje unatrag na moj novi čvor, zbog toga je, opet, Popis dvostruko povezani. 

Tako ćemo napraviti ček zdravog razuma. Ako popis nije null, ako postoji već jedan ili više čvorova tamo, a zatim dodati da vrati referencu da se tako izrazim. A onda je posljednje što nam treba učiniti zapravo ažurirati globalni promjenjiva Popis sama ukazati na taj novi čvor. Da. 

Ivanković: U pokazivača strelica [Nečujan] jednako null, ne da nositi s popisa, jer Popis je null? 

David J. Malan: Nope. To je jednostavno mi se proaktivno Pazite, u smislu da, ako je to moja izvorni popis s možda nekim više čvorova ovamo i ja sam umetanjem mom novi čvor ovamo, tu se događa da se ništa više ovdje. I želim snimiti tu ideju postavljanjem prije null na novi čvor. A valjda, ako je moj broj je ispravan i ne postoji drugi način za umetanje čvorovi osim ove funkcije, vjerojatno, čak i ako je popis već ima jedan ili više čvorova u njemu, vjerojatno Popis, prvi čvor, bi natrag pokazivač sama null. 

Ivanković: I samo follow-up. Razlog stavite pokazivač naprijed jednaki Popis se praviš pokazivač Prije Popis po tome što je pokazujući do sljedećeg, pretpostavljam - Ja ne - samo popis? 

David J. Malan: Točno. I tako ćemo zapravo razmislite dva slučaja ovdje stvarno, iako Kako bi mi ćemo ih uzeti u obzir ne sasvim jednako kao i kod. No, na visokoj razini, ako to predstavlja popis, a to je 32-bitni pointer, najjednostavniji scenarij da je to null po defaultu. I pretpostavljam da želite umetnuti Broj 50 je bio prvi broj. Dakle, ja ću ići naprijed i dodijeliti čvora, koji će sadržavati tri područja - n, natrag i naprijed. 

Ja ću staviti broj 50 ovdje, jer će to biti n. To će biti sljedeći. A to će biti natrag. I tako što mi je činiti u tom slučaju? Pa, upravo sam učinio linije 1 ovdje. Pointer n dobiva n. Ja sam tada rekao, prethodnu trebao dobiti null. Dakle, ovo će biti null. Tada ću reći sljedeće će dobiti popis. 

I to samo ispadne dobro. To je null. I tako sam rekao, novi čvor je sljedeći Polje trebao dobiti bez obzira na to. Tako da dovede drugog null postoji. I onda zadnja stvar I nemojte se provjeriti ovdje. Ako popis nije jednak nuli, ali to je jednak nuli, pa smo preskočiti uopce. I tako sve što učiniti je popis dobiva pointer, koji su slikovito rezultira Slika kao što je to. Dakle, to je jedan scenarij. 

A onaj koji ste bili pitate o posebno je situacija kao što je ovaj, gdje smo već imate popis jedan čvor. I ako se vratim u izvorniku Problem izjavu, iduće ćemo se umetnite recimo je 34, samo za radi rasprave. Zato ću samo povoljno nacrtao ovamo. Upravo sam malloced. Pretpostavimo da provjeravam za null. 

Sada, ja ću započeti n biti 34. A to će biti n. To će biti sljedeći. A to će biti natrag. Idemo pobrinite nisam ovo unatrag. Prethodno je na prvom mjestu u definiciji. Dopustite mi da ovo popraviti. To je natrag. To je sljedeći. Iako su identični, Budimo dosljedni. 

Prethodni. To je sljedeći. Pa upravo sam malloced moje znanje, provjeriti za nulu, dodjeljuje 34 u čvor. Prethodna dobiva null. Tako da mi je to. Sljedeća dobiva popis. Dakle, popis je to. Dakle, to je isto sada kao crtanje ovo strelicu, tako da oni ukazuju na jedan u istom. A onda sam provjeru ako popis nije jednak nuli. I to ne ovaj put. Onda ću napraviti popis natrag dobiva pokazivač. 

Dakle, popis prethodnih dobiva PTR. Tako da to ima za posljedicu stavljanjem grafički strelica ovdje. I to je sve malo valovita, linije. A onda, na kraju, ja ažurirati popis ukazati na pokazivač. Pa sad to ukazuje na ovim tipom. A sada, idemo napraviti brzo duševne ček. 

Evo popisa, što je Globalna varijabla. Prvi čvor je, zapravo, 34, jer Ja pratim tu strelicu. I to je točno, jer želim umetnuti na početku popisa svi novi čvorovi. Njegov sljedeći polje vodi me na ovom tipu. Ako sam zadržati ide, sam pogodio pored null. Dakle, nema više popisa. Ako sam pogodio natrag, dobivam tamo gdje ja očekujem. 

Dakle, još uvijek postoje nekoliko naputke, Očito, za manipulaciju. No, činjenica da su rekli da ne to je u stalnom vrijeme vam znači samo imaju ograničen broj stvari ti si to dopušteno. A što je to broj? To bi mogao biti jedan korak. To bi moglo biti dva. To bi moglo biti 1.000 koraka. No, to je konačna, što znači da ne mogu su bilo kakve petlje događa ovdje, ne rekurzija, nema petlje. To jednostavno mora biti hard-kodirane linije koda kao što smo u ovom uzorku. 

Dakle, sljedeći problem 12 nas je zamolio da dovršiti provedbu otklanjaju dolje tako da uklanja n s popisa u linearnom vremenu. Dakle, imate još malo wiggle room sada. Možete pretpostaviti da je n, ako je prisutan na popisu, neće biti prisutan ne više od jednom. I to je također značilo da se kviz-based pojednostavljenje pretpostavka, pa da, ako vam je broj 50 negdje na popisu, ne znaš također morate brinuti o tome i dalje ponoviti, traže sve moguće Kopija od 50, što bi samo dopasti u neku minutia u ograničenom vremenu. 

Tako je s ukloniti, ovo je definitivno više izazovan i više Kod pisati. No, na prvi pogled, iskreno, to bi moglo izgleda neodoljiv i kao nešto ne postoji način na koji bi mogao imati smisliti na kvizu. No, ako se usredotočimo na pojedinim koracima, Nadamo se da će se iznenada štrajk se da je svaki od tih pojedinačnih koraka čini očiti smisao u retrospektivi. Tako ćemo pogledati. 

Dakle, prvo smo započeti pokazivač da se popis sama. Zato želim linearno vrijeme, to znači Ja ću imati neku petlju. I uobičajeni način ponoviti tijekom čvorova u popisu strukture ili bilo koje vrste strukture iterativno je da se kazaljka na prednjoj podataka Struktura i onda samo početak ažuriranja to i prošetati svoj put kroz strukturu podataka. Tako ću učiniti upravo to. 

Dok pointer, moja privremena varijabla, nije jednak nuli, neka je ići naprijed i provjeriti. Jesam li sretna? Je n polje u čvoru Ja sam trenutno gleda na jednak broj tražim? I ako je tako, neka je učiniti nešto. Sada, primijetiti ako se stanje okružuje cijeli Sljedeće linija koda. To je jedino što mi je stalo - pronalaženje broja u pitanje. Dakle, ne postoji drugi, što pojednostavljuje stvari konceptualno malo. 

Ali sada, shvatio sam, i možda ćete morati Samo je to shvatio, nakon razmišljanja to kroz malo, postoji zapravo dva slučaja ovdje. Jedno je mjesto gdje čvor je na početku popisa, što je malo neugodno, jer je to poseban slučaj, jer morate nositi uz ovu stvar, koja je samo anomalija. Svugdje drugdje u popisu, to je ista stvar. Tu je natrag čvor i pored čvora, prethodni čvor, pored čvora. No, ovaj tip je malo posebna ako je on na početku. 

Dakle, ako se kazaljka jednaka popis sama, pa ako sam na početku Popis i sam našao n, trebam učiniti nekoliko stvari. Jedan, moram promijeniti popis do ukazuju na sljedeće polje, 50 godina. Dakle, pretpostavimo da ja pokušavam ukloniti 34. Dakle, ovaj tip mora ići daleko u samo nekoliko trenutaka. 

Pa ću reći, popis dobiva pokazivač naprijed. Pa, ovo je kazaljka. Dalje se ukazuje ovamo. Dakle, to se mijenja ovaj strelicom pravo Sada se pokazuje na ovom tipu ovdje. Sada, ne zaboravite, mi smo privremena varijabla. Dakle, nismo siročad bilo čvorove, jer imam i ovaj tip u mom Provedba ukloniti. Pa sad, ako je i sam popis nije null, Moram popraviti nešto. 

Moram sada bi bili sigurni da je ovo strijela, koji je prethodno pokazuje 50-34, ovo mora da ode, jer ako ja pokušavam riješiti od 34, 50 je bolje ne zadrži bilo vrsta vratio se spominje kao strelica predložio. Pa upravo sam ovu liniju. Pa onda sam gotov. Taj slučaj je zapravo prilično jednostavan. Sjekao glavu popisa je relativno jednostavan. 

Nažalost, tu je ovo neugodno drugi blok. Pa sad, moram razmotriti slučaj gdje ima nešto u sredini. No, to nije previše strašna, osim za sintaksu kao što je ovaj. Dakle, ako ja nisam na početku Popis, ja sam negdje u sredini. I ovaj redak ovdje govori, start na bilo čvora ste na. Idi na prethodnu čvora sljedeće polje i ukazuju da se na pokazivač. 

Učinimo to slikovito. To je sve komplicirano. Dakle, ako ja imam prethodnog polja ovdje - učinimo to - naprijed stavke ovdje. Idem pojednostaviti moje naputke a nego privući hrpu stvari natrag i naprijed isprekrižane drugoga. I sad, recimo samo da je to 1, 2, 3 za dobrobit rasprave, pa čak i iako to ne u ravnini s Problem je u pitanju. 

Dakle, ovdje je moj popis povezani. Ja sam pokušava ukloniti dva u to Posebno verzija priče. Tako sam izmijenjena pokazivač se upućuju na ovaj tip. Dakle, ovo je PTR. On pokazuje ovdje. Taj je popis, koji postoji na globalnoj razini kao i prije. I on pokazuje ovdje, bez obzira što. I sad, ja pokušavam ukloniti dva. 

Dakle, ako se kazaljka pokazuje ovdje, ja sam će slijediti, očito, natrag pointer, što me stavlja na 1. Ja sam tada htio reći da će sljedeći polje, što me dovodi do više od toga boksati ovdje, ide na jednaka pokazivač naprijed. Dakle, ako je taj pokazivač, to je sljedeća. To znači da je ova strelica potrebe ukazati na ovim tipom. 

Pa što da je linija koda ima samo učinjeno je malo toga. A sada, to je izgleda kao korak u pravom smjeru. Mi u biti žele odrezati 2 out od sredine 1 do 3. Dakle, ima smisla da želimo Ruta ovaj pokazivač oko njega. Dakle, ovo next linija provjeru ako pokazivač Sljedeći nije NULL, postoji doista je netko s desne strane 2, to znači da moramo napraviti malo odrezati ovdje. 

Tako sam sada morati slijediti taj pokazivač i ažurirati prethodni pokazivač ovaj momak učiniti malo zaobilazno rješenje ovdje bit ovdje. I sada, vizualno je to lijepo. To je malo neuredan u da postoji nitko ne ukazuje na dvije više. 2 pokazuje u lijevo. A 2 pokazuje udesno. No, on može učiniti što god želi, jer je On je o tome da se oslobodi. I nije važno što te vrijednosti su više. 

Ono što je važno je da se preostali Dečki su usmjeravanje iznad i ispod njega. I doista, to je ono što ćemo učiniti. Mi smo slobodni pointer, što znači da ćemo reći operativnog sustava, vi ste dobrodošli povratiti to. I onda na kraju, možemo se vratiti. Inače implicitno, ako smo još nisu vratili, Moramo nastaviti tražiti. Dakle pointer jednako pokazivač naprijed samo znači kretati ovog momka ovdje. Pomicanje ovog momka ovdje. Pomicanje ovog momka ovdje ako, u stvari, nismo pronašli broj tražimo još. 

Pa iskreno, to izgleda posve neodoljiv, mislim, na prvi pogled, pogotovo ako ste se borili s tim u kvizu onda vidjeti nešto kao što je ovaj. A što se maziti na leđima. Pa, nema šanse da bih mogao imati smisliti da na kvizu. No ja bih rekao, možete ako break to dolje u to individualno slučajevima i samo prošetati kroz nju Pažljivo, iako, doduše, pod stresnim okolnostima. 

Srećom, slike izrađene sve sretniji. Ti bi mogao privući to u bilo koji broj načina. Vi ne morate učiniti isprekrižane stvar ovdje. Mogao bi to učiniti s ravno linije kao što je ovaj. No, suština ovog problema, u Općenito, bila je da shvatite da slika je na kraju ipak izgleda malo nešto poput ovoga, jer je konstantno vrijeme podrazumijeva da zadržite ometanje i ometanje i ometanje novi čvorovi na početku popisa. Ima li pitanja? Vjerojatno najzahtjevnija Sigurno pitanja kodiranje. 

Ivanković: Pa je popis sličan glavu u prethodnim primjerima. 

David J. Malan: Točno, točno. Samo drugi naziv Globalna varijabla. Svjetski što? 

ROB Bowden: OK. Dakle, ovo je jedan gdje se morao napisati odlomak. Neki ljudi pisao eseje za ovo pitanje. Ali vi samo trebate koristiti tih šest uvjete opisati što se događa kada pokušate kontaktirati facebook.com. Dakle, ja ću samo razgovarati kroz proces koristeći sve ove uvjete. Dakle, u našem pregledniku, mi tip facebook.com i pritisnite Enter. Dakle, naš preglednik će konstruirati HTTP zatražiti da će poslati kroz neki proces na Facebooku za Facebook odgovoriti na nas HTML svoje stranice. 

Dakle, što je proces koji HTTP zahtjev zapravo dobiva na Facebook? Tako je prvi, moramo prevesti Facebook.com. Tako je samo dao ime Facebook.com, gdje je zapravo HTTP zahtjev treba ići? Dakle, moramo prevesti Facebook.com za IP adresu, što je jedinstveno identificira ono što stroj mi zapravo želite poslati ovaj zahtjev. Vaše prijenosno računalo ima IP adresu. Bilo je spojen na internet ima IP adresu. 

Dakle, DNS, Domain Name System, koji je što će se nositi prijevod iz facebook.com na IP adresu koja što zapravo želite kontaktirati. Tako smo kontaktirati DNS servere recimo, ono što je facebook.com? Ona kaže, oh, to je IP adresa 190,212 nešto, nešto, nešto. U redu. Sada, ja znam što je za kavu Želim da se obratite. 

Pa onda vam poslati svoje HTTP zahtjev više na tom stroju. Pa kako se to dobiti na tom stroju? Pa, zahtjev odlazi iz usmjeritelju oscilacija. Zapamti primjer u razredu, gdje mi zapravo vidio put koji paketi uzeo kada smo pokušali komunicirati. Vidjeli smo da skok preko Atlantika Ocean je u jednom trenutku ili bilo što drugo. 

Tako posljednji termin port. Dakle, to je sada na vašem računalu. Možete imati više stvari trenutno komunikaciji s interneta. Dakle, ja mogu biti pokrenut, recimo, Skype. Možda ću imati internet preglednik otvoren. Možda imam nešto što torrenting datoteke. Dakle, sve ove stvari su komunikaciji s Internetu na neki način. 

Dakle, kada se računalo dobiva neke podatke s interneta, kako se to radi Znam što aplikacija zapravo želi podatke? Kako to znamo je li to posebno podaci namijenjeni torrenting primjenu, za razliku na web-preglednik? Dakle, to je svrha lukama u koje sve ove aplikacije imaju tvrdio priključka na vašem računalu. Dakle, vaš web preglednik, kaže, hej, Ja sam sluša na portu 1000. I vaš torrenting program govoreći, Ja sam sluša na portu 3000. I Skype kaže, ja sam koristeći port 4000. 

Dakle, kada ste dobili neke podatke koji pripada na jednu od tih aplikacija, podataka je obilježena koji port je to zapravo treba poslati zajedno. Dakle, to, kaže, oh, ja pripadam na port 1000. Znam onda moram proslijediti ovaj zajedno s mojim web pregledniku. Dakle, razlog je to relevantno ovdje je da web poslužitelji imaju tendenciju da slušati na portu 80. Dakle, kad sam kontaktirati Facebook.com, ja sam komunicira s nekim strojem. No, moram reći koji port koji Stroj želim komunicirati. I web poslužitelja imaju tendenciju da se sluša na portu 80. 

Ako su htjeli, mogli su ga postavili gore tako da se navodi kako je na portu 7000. A onda u web pregledniku, što sam mogao ručno upisati Facebook.com: 7000 slanje zahtjeva za priključak 7000 Facebook web poslužitelja. 

David J. Malan: I u ovom slučaju, čak i iako mi nije potrebno da se ljudi Spominjem to, u ovom slučaju, ono što luka će zahtjev zapravo ići? Pokušajte ponovno. Točno. Ne traži da, ali suptilnost da je tamo nitko posljednja. 

ROB Bowden: Dakle HTTPS, budući da je slušanje posebno za kodiran, to je na portu 4430. 

Publika: i e-mailove su 25, zar ne? 

David J. Malan: Izlazni e-mailove, 25, yep. 

ROB Bowden: Ja ne znam ni većina - sve donjih imaju tendenciju da se rezervirana za stvari. Mislim da je sve pod 1024 je rezerviran. 

Ivanković: Zašto ste rekli 3 bio pogrešan broj? 

ROB Bowden: Zato što je u IP adrese, ima četiri grupacije znamenki. I oni su od 0 do 255.. Tako da je zajednička 192.168.2.1 lokalna mreža IP adresa. Obavijest svima su manje od 255.. Dakle, kada sam počeo sa 300, da nikako ne može imati bio jedan od brojeva. 

David J. Malan: Ali to glupo clip od - bio je CSI, gdje su imali broj koji je bio prevelik za IP adresu. 

ROB Bowden: Bilo kakva pitanja o tome? Sljedeći, tako potpuna promjena topic, ali mi imamo tu PHP polje za kuće u quad. A imamo neuređen popis. I želimo ispisati svaku stavku popisa Samo sadrži naziv kuću. Tako imamo foreach petlju. Tako zapamtite, sintaksa je foreach Niz kao stavku u nizu. Dakle, kroz svaku iteraciju petlje, Kuća se događa da se na jednom od Vrijednosti unutrašnjost niza. 

Na prvoj iteraciji kući će biti Cabot House. Na drugoj iteraciji, kuća će biti Courier House i tako dalje. Dakle, za svaki quad kao kuće, mi smo Samo će ispisati - Također može imati odjek - stavku popisa, a potom ime doma parlamenta a zatim zatvorite stavku popisa. U vitičastim zagradama su opcija ovdje. 

I onda mi je također rekao u pitanje sama, ne zaboravite zatvoriti Popis bez rednih brojeva tag. Zato nam je potrebno za izlazak iz PHP modu kako bi to učinili. Ili smo mogli su odjekivali zatvoriti Popis bez rednih brojeva oznaku. 

David J. Malan: Isto tako u redu ovdje bi su koristiti staru školu Petlja s $ i = 0 0 i pomoću broji do shvatiti duljinu zrake. Totalno redu previše, samo Malo wordier. 

PUBLIKA: Dakle, ako ste bili će se [Nečujan], bi li to - I zaboraviti ono loop [nečujan] je. Biste li $ quad nosač sam? 

David J. Malan: Točno. Da, točno. 

ROB Bowden: Bilo što drugo? 

David J. Malan: U redu. Kompromisi. Tako je bilo trsovi odgovora moguće za svaki od njih. Mi stvarno su samo u potrazi za nešto uvjerljiviji za naglavce i downside. I broj 16 upita potvrđivanju korisnik ' Ulaz na strani klijenta, kao i sa JavaScript, umjesto na strani poslužitelja, kao što je s PHP. Dakle, ono što je naopako radi na strani klijenta? 

Pa, jedna od stvari koje mi se predloženim da se smanji latencije, jer vam ne morate zamarati kontaktiranja poslužitelja, što bi moglo potrajati nekoliko milisekundi ili čak par sekundi izbjegavanjem da se i samo potvrđivanju korisnika ulazni strani klijenta po pokreće on-predati rukovatelj a samo provjera, jesu li upisati nešto za ime? Jesu li nešto tipa u za e-mail adresu? Jesu li odabrati spavaonica s padajućem izborniku? 

Možete im dati trenutnu povratnu informaciju pomoću gigaherca računalo ili što su to zapravo na njihovom stolu. Dakle, to je samo bolje korisničko iskustvo obično. Ali downside rade na strani klijenta valjanosti, ako to učiniti, a da pritom radi server-side validacije je da većina svatko tko dolazi iz CS50 zna koje možete jednostavno poslati sve podatke koje želite na poslužitelj bilo koji broj načina. Iskreno, u većini bilo pregledniku, možete kliknite okolo u postavkama i samo isključite JavaScript, koji bi, Stoga, onemogućiti bilo kakav oblik valjanosti. 

No, možda ćete se sjetiti da je čak i sam učinio neke tajanstvene stvari u klasi pomoću telnet i zapravo pretvara da biti u preglednik slanjem get zahtjeva na poslužitelju. A to sigurno nije korištenja bilo JavaScript. To sam samo ja tipkati naredbe na tipkovnici. Pa stvarno, bilo programer roku dovoljno comfort s weba i HTTP mogao poslati god data on ili ona ne želi na poslužitelj bez odobrenja. A ako je vaš poslužitelj ne i pravopisa, jesu li mi dati ime, je to zapravo valjana email adresa, učinio oni izabrati spavaonica, možda ćete završiti do umetanja lažna ili samo prazno podataka u bazu podataka, što je vjerojatno ne će biti dobra stvar ako se što su pod pretpostavkom da je bio tamo. 

Dakle, ovo je neugodno stvarnost. No, općenito, na strani klijenta valjanosti je super. No, to znači dvostruko više posla. Iako postoje postoje razne biblioteke, JavaScript knjižnice za Primjerice, da bi to puno, mnogo manje od glavobolje. I vi možete ponovno neke od koda server-side, na strani klijenta. No, ne shvaćaju da je to obično dodatni rad. Da. 

Ivanković: Pa, ako smo upravo , rekao je manje siguran - 

David J. Malan: [smijeh] Uh. Oni su uvijek teže one da sude. 

ROB Bowden: To bi su prihvaćeni. 

David J. Malan: Što? 

ROB Bowden: Ja sam stvorio ovaj problem. To bi bio prihvaćen. 

David J. Malan: Da. 

PUBLIKA: Cool. 

ROB Bowden: Ali mi nije prihvatio za prvi - dobro, ono što smo tražili je nešto poput tebe ne moram komunicirati s poslužiteljem. Nismo prihvatiti samo brže. 

PUBLIKA: Što je s ne reload stranicu? 

ROB Bowden: Da. To je bio prihvaćen odgovor. 

David J. Malan: Bilo gdje smo se osjećali to je više nego vjerojatno nije vjerojatno da ste znali što ste bili govoreći, što je teška linija za crtanje ponekad. Korištenje popisa povezan umjesto od niza za održavanje razvrstani popis brojeva. Dakle upside često citiraju s povezani popisi, koji su motivirani svoju cjelinu uvod je dobiti dinamičnost. Oni mogu rasti. Oni mogu smanjiti. Dakle, ne morate skočiti kroz obruč to zapravo stvoriti više memorije s nizom. Ili ne morate samo kažu, žao, korisnik. Niz je ispunjen. Dakle, dinamičan rast na popisu. Downside iako povezanih popisima? 

Ivanković: To je linearno. Pretraživanje na povezanom popisu je linearna umjesto što se prijavite u. 

David J. Malan: Točno. Pretraživanje na popisu povezan je linearna, čak i ako je to riješeno, jer možete samo slijedite ove krušne mrvice, te upućuje, od početka popisa na kraju. Ne možete utjecati slučajni pristup i, dakle, binarno pretraživanje, čak i ako je razvrstani, da bi mogao učiniti s nizom. A tu je i još jedan trošak. Da. 

PUBLIKA: Memorija neučinkovita? 

David J. Malan: Da. Pa, ja ne bi nužno kažu neučinkovita. No, to se vas koštati više memorije, jer vam je potrebno 32 bita za svaki čvor za dodatne pointer, na Barem za popis na pojedinačno povezana. Sada, ako ste samo spremanje cijele brojeve dodajete pokazivač, koji je zapravo vrsta ne-beznačajan. To je udvostručenje količine memorije. No, u stvarnosti, ako ste spremanje povezani popis tvorevina, koje bi mogle imati 8 bajta, 16 bajtova, čak i više od toga, možda je manje od graničnog troška. No, to je ipak trošak. Dakle, bilo je onih koji bi mi bio u redu kao mane. 

18. Koristeći PHP umjesto C pisati Program naredbenog retka. Dakle, ovdje, to je često brži za korištenje jezik poput PHP ili Ruby i Python. Vi samo brzo otvaranje do uređivač teksta. Imate mnogo više funkcija dostupne za vas. PHP ima sudopera funkcija, dok je u C, što imaju vrlo, vrlo malo. Naime, dečki znaju na teži način da nemate hash tablice. Ne povezalo liste. Ako želite onima, morate implementirati ih sami. 

Dakle, jedan naopako PHP ili stvarno bilo tumačiti jezik je brzina s kojima možete napisati kod. No, minus, vidjeli smo to kada sam brzo tučeno gore misspeller Provedba je u predavanju koristeći PHP, je da je korištenje interpretativnom jeziku je obično sporiji. A vidjeli smo da je dokazivo s povećati u vremenu od 0,3 sekunde do 3 sekunde, zbog tumačenja koji se zapravo događa. 

Drugi naopako je da vam ne moraju sastaviti. Dakle, to je također ubrzava razvoj usput, jer nemate Dva koraka za pokretanje programa. Potrebno je samo jedno. I to je lijepo uvjerljiv kao dobro. Korištenje SQL baze podataka, umjesto CSV datoteka za pohranu podataka. Dakle, SQL baza podataka koristi se za pset7. CSV datoteke koje ne koriste mnogo. No, što to koristi neizravno u pset7 kao i razgovarajući s Yahoo financija. 

Ali CSV je baš kao i Excel datoteke, ali super jednostavna, gdje su stupci Samo nika zarezom unutar jednog na drugi način tekstualnu datoteku. I pomoću SQL baze podataka je malo više uvjerljiv. To je naglavačke, jer ste dobili stvari kao i odabir i umetanje i brisanje. A što se, po svoj prilici, kazala da je MySQL i druge baze podataka, kao što su Oracle, graditi za vas u memoriji, što znači tvoj odabir vjerojatno nije će biti linearan od vrha do dna. To zapravo će biti nešto kao binarni pretraživanje ili nešto slični u duhu. Dakle, oni su u pravilu brže. 

No, minus je da to je samo više posla. To je više truda. Morate razumjeti baze podataka. Morate ga postaviti. Trebaš poslužitelj za pokretanje da je baza podataka o. Morate razumjeti kako ga konfigurirati. Dakle, to su samo ovi vrste ustupaka. Dok CSV datoteku, možete stvoriti ga s gedit. A ti si dobar to ići. Nema složenosti izvan toga. 

Korištenje trie umjesto hash tablicu sa zasebnim ulančavanje za pohranu rječnik riječi podsjećaju od pset5. Dakle, pokušava naglavačke, u teoriji barem je ono? Stalno vrijeme, barem ako ste raspršivanja na svaki od pojedinačnih slova u riječi, kao ti možda za pset5. To bi moglo biti pet Skosan, šest sasjecka ako postoji pet ili šest slova u riječi. I to je jako dobro. A ako postoji gornja granica na tome dugo vaše riječi može biti, to je dapače asimptotski konstantna vrijeme. 

Dok hash tablicu s odvojenim ulančavanje, problem postoji s tim vrsta strukture podataka da obavljanje svojih algoritama obično ovisi o broju stvari Već u strukturu podataka. I to je definitivno slučaj s lanaca, pri čemu više stvari ste stavili u hash tablicu, više onih lanci idu, što znači da je u najgorem slučaj, što bi moglo biti u potrazi za je sve na kraju jednog tih lanaca, koji učinkovito devolves u nešto linearno. 

Sada, u praksi, to bi apsolutno biti slučaj da hash tablicu s lanci je brže nego što odgovara Provedba trie. No, to je zbog raznih razloga, među koji se pokušava koristiti puno memorije koja se, u stvari, spore stvari dolje, jer ne bi bilo lijepo Prednosti nešto što se zove caching, gdje se stvari koje su blizu jedna drugoj u memoriji može se pristupiti Često brže. A ponekad možete smisliti stvarno dobra funkcija ljestve. Čak i ako imate gubiti malo memorija, što bi se, doista, biti u stanju naći stvari brzo i ne tako loše kao linearno. 

Dakle, ukratko, nije bilo nužno s bilo koje od tih jedan ili čak dva određene stvari koje su tražili. Stvarno ništa uvjerljiv kao naopako i minus uglavnom uhvaćen naše oči. 

ROB Bowden: Pa za naopako, jesmo Ne prihvaćam na vlastitu "brži". Vi imao za reći nešto o tome. Čak i ako je rekao teoretski brži, znali smo da vrsta razumio da je 0 od 1. I hash tablicu, u teoriji, nije 0 od 1. Spominjući ništa o izvršavanja uglavnom imaš bodova. No, "brži", većina rješenja o velika ploča koje su pokušaja bila objektivno sporiji od rješenja da su hash tablice. Dakle brže i sama zapravo nije istina. 

David J. Malan: Dom de dom dom. Ja sam vjerojatno jedini koji shvaća to je kako da je trebao se izgovara, zar ne? 

ROB Bowden: Nisam imao zapravo pojma. 

David J. Malan: To je napravio smisla u mojoj glavi. 

ROB Bowden: Radim ovaj jedan. OK. Dakle, ovo je jedan gdje se morala povući Dijagram slično što možda vidjeli na prošlim ispitima. Tako ćemo samo gledati na to. Dakle iz HTML čvora, imamo dva djeca, glava i tijelo. Tako smo se grana - glavu i tijelo. Glava ima više oznaka. Dakle, imamo titulu. 

Sada, jedna je stvar puno ljudi Zaboravila je da su ti tekst čvorovi elementi unutar tog stabla. Dakle, ovdje mi se dogoditi da ih izvući što ovala kako bi ih se razlikovalo od njih vrste čvorova. No, obavijest i ovdje imamo krov, srednji i donji će završiti kao tekst čvorovi. Dakle, zaboravljajući one bio nešto zajedničke pogreške. 

Tijelo ima troje djece - ove tri divs. Dakle, div, div, div, a zatim tekst čvora djeca tih divs. To je uglavnom to za to pitanja. 

David J. Malan: I to je vrijedno napomenuti, iako mi ne razmišljati o njima detalji u vrijeme trošimo na JavaScript, da je nalog radi, u Činjenica, stvar je tehnički. Dakle, ako je glava u pitanju prije tijela u HTML, onda bi se trebao pojaviti na lijevo od tijela u stvarnom DOM. Taj njegov je, u cjelini, samo FYI, nešto što se zove kako bi dokument, u kojem to ne obzira. I ako se provodi parser, Program koji čita HTML u zgradi do stabla u memoriji, da budem iskren, to je vjerojatno ono što intuitivno svejedno - od vrha do dna, lijeva na desno. 

ROB Bowden: Pitanja o tome? Trebam li napraviti sljedeći? 

David J. Malan: Svakako. 

ROB Bowden: OK. Dakle, ovo je tampon prekoračenje Napad pitanje. Glavna stvar je da prepoznaju ovdje je, dobro, kako bi mogli protivnik trik ovaj program u izvršavanju proizvoljnog koda? Dakle argv1, prva naredbenog retka Argument za ovaj program, koji može biti proizvoljno dugo. Ali ovdje smo pomoću memcpy kopirati argv1, koja je ovdje bar. Mi smo to prolazi kao argument. I tako to traje na ime bara. 

Tako smo memcpying bar u ovoj tampon c. Koliko bajta su kopiramo? Pa ipak su mnogi bajtova bar se događa se koriste, dužinu tog argumenta. No, c je širok samo 12 bajtova. Dakle, ako mi tip naredbe argument je to je više od 12 bajtova, mi smo će se preliti ta Posebno tampon. Sada, kako bi mogli protivnik trik programirati u izvršavanju proizvoljnog koda? 

Dakle, ne zaboravite da je ovdje Glavni zove foo. I tako onda glavni pozivi Foo. Idemo nacrtali ovo. Dakle, mi imamo hrpu. A glavna ima stog okvir na dnu. U nekom trenutku, glavni pozivi Foo. Pa, odmah, glavni pozivi Foo. I tako Foo dobiva svoj stack okvir. 

Sada, u nekom trenutku, Foo će se vratiti. I otišao foo vraća, moramo znati na što linija koda unutar osnovnog mi su kako bi znali gdje trebamo nastaviti u glavnom. Mi možemo nazvati Foo iz cjeline hrpa različitih mjesta. Kako znamo gdje da se vrate? Pa, moramo spremiti tu negdje. 

Dakle, negdje u pravu ovdje, možemo pohraniti gdje smo trebali vratiti u jednom Foo vraća. A to je povratna adresa. Pa kako protivnik mogla iskoristiti to je činjenica da se to tampon c je pohranjena, neka je kažu, ovdje je c. Dakle, mi smo dobili za C12 bajtova. To je c. A to je Foo je stog prsten. Dakle, ako zlonamjerni korisnik unese više bajtova od 12 ili uđu naredbu linija argument da je više od 12 likovi, onda ćemo prelijevati ovu tampon. 

Možemo zadržati ide. I u nekom trenutku, možemo daleko dogurati dovoljno da počnemo prepisati ovu povratnu adresu. Dakle, nakon što smo prebrisati povratnu adresu, To znači da kad Foo vraća, Vraćamo se gdje god zlonamjerni korisnik to govori da se po bez obzira na vrijednost što je ušao, koji god likovi korisnik unio. I tako, ako zlonamjerni korisnik bude osobito pametan, on može imati ovo vratiti u negdje u printDef funkcija ili negdje u malloc funkcija, samo nigdje proizvoljna. 

No, čak i više pametan je, što ako on ima Korisnik se vratiti u pravu ovdje. I onda počnete izvršavanju to što je linija koda. Dakle, u tom trenutku, korisnik može unijeti što god želi u ovoj regiji. I on ima potpunu kontrolu preko svog programa. Pitanja o tome? Dakle, sljedeće pitanje je završena reimplementation foo tako da to više nije ranjiv. 

Dakle, postoji nekoliko načina mogao si to učinio. Mi još uvijek imamo samo c biti duljine 12. Moglo bi se promijenila ova kao dio svoje rješenje. Također, dodao je provjeriti kako bi sigurno bar nije bilo null. Iako vam ne treba da je za puni kredit. Tako smo provjeru prvi duljine od bara. Ako je veći od 12, a zatim ne zapravo napraviti kopiju. Dakle, to je jedan od načina kako to srediti. 

Drugi način je popravljajući je, umjesto ima C biti samo dužine 12, da ga biti duljine strlen (bar). Drugi način je popravljajući je to zapravo samo vratiti. Dakle, ako ste upravo stečen osloboditi od svih to, ako ste upravo izbrisati sve linija koda, što bi dobio u punom iznosu, od ove funkcije ne zapravo ostvariti ništa. To je kopiranje naredbenog retka Argument u neki niz u njezin lokalni okvir stack. I onda što se vraća. I sve što je ostvario je otišao. Dakle, povratak je bio dovoljan način dobivanja puni kredit. 

David J. Malan: Ne sasvim duh pitanje, ali prihvatljivo po spec. svejedno. 

ROB Bowden: Pitanja na bilo što od toga? Jedna stvar koju barem potreban da bi se kod sastavljanja. Dakle, iako je tehnički niste ranjiv ako vaš broj ne sastaviti, nismo prihvatili da. Nema pitanja? OK. 

David J. Malan: Želite li reći ovaj naslov? 

ROB Bowden: Ne. 

David J. Malan: Pa u tom jednom, ovaj je bilo dobre vijesti ili loše vijesti. To je doslovce isti problem kao prvi kviz. I to je gotovo isto Problem kao pset1. Ali, to je namjerno pojednostavljen kako bi se jednostavnije piramide, koji može biti riješiti s nešto jednostavnije iteracija. I zaista, ono što smo bili uzimajući u Ovdje nije bilo toliko logika, jer je vjerojatno, po ovom trenutku, ti si udobnije nego što su bili u tjedan jednom sa za petlje ili zašto petlje, ali stvarno se zafrkavati, osim da ti si malo ugodno Ideja da PHP nije riječ samo o tome što programiranje. To zaista može se koristiti kao jezik napisati naredbenog retka programa. 

I doista, to je ono što smo mi pokušavali skrenuti pozornost. To je PHP program naredbenog retka. Dakle C kod ovdje, a točne u C, nije točan za PHP. Ali kod stvarno je ista. Ako usporedimo rješenja za kviz 0 protiv kvizu 1, vidjet ćete da to je gotovo identična, osim za neki dolar znakove i za Odsutnost tipa podataka. Konkretno, ako pogledamo ovdje, vidjet ćete da smo ponoviti, u to slučaj, od 1. do 7. do. 

Mogli smo to učinili 0 indeksa. No, ponekad, mislim da je to samo psihički lakše razmišljati o stvarima od 1 do 7. Ako želite jedan blok, a zatim dva blokovi, zatim tri, a zatim dot, dot, dot sedam. Mi smo j inicijalizacije do 1 a zatim računajući na do i. I sve je ovdje inače identični. No, valja spomenuti su par stvari. Mi vam dati ove dvije linije, ovaj prvi jedan, goofily zove kao shebang za oštar prasak. I to samo specificira put, mape, u kojem program može biti utvrdili da želite koristiti interpretirati ovu sliku. 

I onda crta nakon toga, od Naravno, znači ući PHP način. A linija na samom dnu znači izlazak PHP način. I to radi, u cjelini, s tumačiti jezika. To je vrsta neugodno ako pišete Program u datoteci pod nazivom foo.php. I onda vaši korisnici imaju samo zapamtite, OK, pokrenuti ovaj program, ja morati upisati "php prostor foo.php." Vrsta neugodno ako ništa drugo. I to je također otkriva da je vaš program je napisan u PHP, što nije sve da osvjetljava za korisnika. 

Na taj način možete ukloniti. Php uopce sjećam iz predavanja. A što zapravo može učiniti. / Foo ako ste ga chmodded čineći ga izvršna. Dakle chmod + x Foo bi učinio to. A ako i dodati shebang ovdje. Ali zapravo, problem je bio uzimajući u ispis nešto ovako. Ne HTML, nema C-code sigurno, samo su neke PHP. Dakle Milo zatim se vratio u problemu 25. A u 25 godina, koju su dobili sljedeći Kostur broj, koji je bio prilično jednostavna web stranica. I sočan dio HTML-mudar je dolje Ovdje, gdje imamo unutar tijela oblik koji ima jedinstveni ID ulaza unutar kojih je dva ulaza, jedan s idejom ime, jedan s idejom gumb. 

Prvi je tip teksta, Drugi tipa podnose. I tako smo ti dali, zapravo, više sastojaka nego što je potrebno, samo tako da ste imali opcija s kojom kako riješiti ovaj problem. Vi ne strogo potrebno sve ove osobne iskaznice. Ali, to vam omogućuje da riješiti to na različite načine. A gore na vrhu, primijetiti da Cilj je bio da se aktiviraju prozor kao što je ovaj - Pozdrav, Milo! - poskočiti u pregledniku pomoću super jednostavna, ako nije ružna, funkcija oprezu. I tako, u konačnici, to se svodi konceptualno nekako sluša Tvrdnje o obliku strani klijenta , A ne na strani poslužitelja, nekako odgovarajući na tom podnesku od strane grabbing vrijednost koju korisnik upisali u na području ime, a zatim prikazivanje u tijelu upozorenja. 

Dakle, jedan od načina na koje možete učiniti je s jQuery, koji izgleda malo sintaktički zbunjujući na prvi pogled. To možete učiniti sa čistim DOM code - document.getelement po ID. Ali neka se pogledati na ovoj verziji. Imam par važno Prva linija. Dakle, mi smo tu liniju, što je identičan onome što ste mogli vidjeti u, vjerujem, form2.html iz razreda u tjednu 9.. I to samo govori, izvršiti Sljedeći kod kada Dokument je spreman. To je bitno samo zato što HTML-stranice se pročitati na vrh dno, s lijeva na desno. 

I zato, ako pokušate napraviti nešto u kodu se ovdje za nekog DOM Element, neki HTML tag, to je prema dolje Ovdje, radite to prerano, jer ovo nije ni je pročitao u memoriju. Tako rekavši ovu document.ready linija, mi tvrdimo, evo neki broj, browser. Ali ne izvrši to do cjelini Dokument je spreman, da je DOM Stablo postoji u memoriji. Ovo je jedna malo više jednostavno, ako sintaktički malo drugačiji, gdje govorim, grab HTML element čija je jedinstvena identifikator ulaza. To je ono što hash tag označava, jedinstveni ID. A onda sam se zovem. Podnose. 

Dakle. Slati ovdje je funkcija, inače poznat kao metoda, koja je unutar objekta na lijevoj ruci strana ima koji nisam istaknuti. Dakle, ako mislite inputa kao objekt u spomen - i doista je. To je čvor u stablu - . Dostaviti sredstva kada ovaj obrazac s ovaj ID podnosi, izvršiti Sljedeći kod. Ne zanima me što se ime Funkcija je sam izvršenja. Pa evo ja sam koristeći, kao i prije, što je pozvao funkciju lambda ili anonimna funkcija. To uopće nije intelektualno Zanimljivo, osim što nema ime, što je u redu ako ste samo sve će to nazvati jednom. A unutra sam zapravo nositi podnošenje obliku. Prvi put sam proglasiti varijablu nazvao vrijednost. A što je onda učinak ove istaknut dio ovdje sada? Što bi to trebalo učiniti u Visoka razina za mene? 

PUBLIKA: On dobiva vrijednost koju korisnik nije u HTML u nastavku. Ona dobiva taj ID, a zatim pronalazi vrijednost toga. 

David J. Malan: Točno. Ona zgrabi čvor, čiji je jedinstvena identifikator ime. Ona dobiva vrijednost u njemu, koji je, vjerojatno, ono što je korisnik upisali njega ili sebe. I onda se sprema da u varijabla zove vrijednost. Kao na stranu, što bi moglo imati i učinio malo drugačije. Totalno prihvatljivi radiš nešto Laž var vrijednost dobiva document.getElementById. I to je razlog zašto je malo zamorno ne koristiti jQuery. "Naziv". Vrijednost. Dakle, posve prihvatljivo. Različiti načini da to učinite. jQuery samo ima tendenciju da se malo više jezgrovit i definitivno više popularan među programerima. 

Sada radim malo zdravog razuma provjeriti, jer je u problemu izjava, izričito je rekao, ako se korisnik nije još upisali njegov ili njezin ime, ne pokazuju upozorenja. No, možete provjeriti za to, po samo provjera za prazan string za quote-završiti citat, ako postoji ništa zapravo postoji. No, ako to nije jednak quote-završiti citat, Želim pozvati upozorenja. I zanimljiv dio je da koristimo plus operatera, koji što radi u JavaScriptu? Spojite. Dakle, to je kao PHPs dot operatera. Sve ideje, malo drugačiji sintakse. A ja sam samo stvara niz koji ste vidjeli na zaslonu pucao - Pozdrav, tako i tako. 

A onda, i najmanji detalj je to. Zašto bih se vratiti lažno unutrašnjost od tih anonimnih funkcije? 

Ivanković: Nema vrijednost. Možete ga staviti u formi. To samo govori, ako vrijednost nije jednaka je prazno, onda to učinite. Bilo je prazan u tom podnesku. 

David J. Malan: OK. Oprezni. Ne postoji nitko drugi ovdje. A da je povratak lažno je izvan od, ako uvjeti. Dakle, ovo je istaknuo liniju, povratak false, izvršava bez obzira kada Obrazac se podnosi. Što povratku lažno unutar ovog događaj rukovatelj, kako se zove, događaj u pitanju se podnesak? 

PUBLIKA: Zato što događa samo jednom. 

David J. Malan: događa samo jednom. Nije dosta. Da? 

Ivanković: To sprječava obrazac iz podnošenje zadanom ponašanju, koji će napraviti stranicu reload. 

David J. Malan: Točno. Dakle, ja sam preopterećenja termina slati ovdje, jer ja govorim, forma je podnosi. No, kao što sugeriraju, to zapravo nije podnesen u pravom HTTP način. Nakon što kliknete Pošalji, jer naše onSubmit rukovatelj, mi smo presretanjem da je obrazac za slanje da se tako izrazim. Mi smo tada radili našu stvar s JavaScript kod. No, ja sam namjerno povratka lažna, zato što ne želim da se dogodi djelić sekunde kasnije je za cijelu obliku Sam se podnosi na webu poslužitelj s ključnim parova vrijednosti promjenom URL se dogoditi nešto slično q = mačke ili što god smo učinili, Na primjer, u razredu. Ne želim da se to dogodi, jer nema slušanje poslužitelja za to obrazac za prijavu. To je čisto radi u JavaScript kodu. I to je razlog zašto nisam ni action atribut na mojoj formi, jer sam ne namjeravaju da se to ikada ići na poslužitelju. 

Pa to je da je podnesen. No, mi smo presretanja tu formu podnesak i sprečavanje zadani ponašanje, koje je zapravo ići sve do poslužitelja. 

Ivanković: Pa imajući to na strani klijenta. 

David J. Malan: Držanje je na strani klijenta. Točno u pravu. Sljedeći je bio moj oh MySQL. 

ROB Bowden: OK. Dakle, ovo prvo pitanje je bilo općenito gruba za ljude. Iako mlađi su otišli bolje. Tako da su morali odabrati ispravnu podatke vrste za obje ove stupce. I jedno i drugo ima neke stvari o njima koje napraviti izbor teško. Dakle int nije bila valjana tipa za broj. Razlog je 12-znamenki računa broj, int nije dovoljno velik da bi pohraniti ukupne brojke. Tako vrijedi izbor bi bio veliki int, ako vam se dogoditi da znaju da. Drugi izbor je mogao biti Polje char duljine 12. Dakle, bilo je onih koji bi radili. Int ne bi. 

Sada, ravnoteža, prisjetite pset7. Stoga smo posebno koriste za decimale pohraniti vrijednost dionica ili - 

David J. Malan: Gotovina. 

ROB Bowden: Gotovina. Koristili smo decimale pohraniti količinu gotovina koju korisnik trenutno ima. Dakle, razlog zbog kojeg smo to je jer, ne zaboravite, pluta. Tu je s pomičnim zarezom u preciznosti. To se ne može precizno pohraniti novac Vrijednosti poput želimo ovdje. Dakle decimala je u stanju precizno trgovine nešto što se, kažu, dvije decimale. Zato ravnotežu, mi to želimo biti decimala i ne plutaju. 

David J. Malan: I također, previše, iako možda bi bilo pametno u drugom kontekstima razmišljati, možda je to je prilika za int. Ja ću samo pratiti stvari u penija. Budući da smo izričito pokazali zadani vrijednost kao 100,00, da znači to samo mogao biti int. I još jedna suptilnost previše s brojem bila je da nije bio namijenjen biti trik pitanje. No, podsjetimo da int u MySQL, kao što je u C, barem aparata, je 32-bitni. I iako ne očekujem da se znam točno koliko znamenaka koje znači, sjećam se da je najveći broj što može predstavljati potencijalno s 32-bitnom broj je otprilike ono? 

Koji broj mi uvijek reći? 2 do 32, što je ono što zlo? Ne morate znati točno. No, grubo je korisno u životu. To je otprilike 4 milijarde. Tako smo, rekao je da je nekoliko puta. Ja znam što sam rekao je da je nekoliko puta. I to je otprilike 4 milijarde. I to je dobro pravilo od oka znati. Ako imate 8 bita, 256 je magični broj. Ako imate 32 bita, 4 milijardi dati ili uzeti. Dakle, ako ste samo napiši 4000000000, vidjet ćete da je to manje od broja 12, što znači da to nije jasno Dovoljno izražajnost uhvatiti Broj 12 znamenki računa. 

ROB Bowden: OK. Tako su ostale one otišao bolje. Dakle, pretpostavimo da banka nameće 20 dolara mjesečne naknada za održavanje na svim računima. S kojim SQL upit bi banka oduzimamo 20 dolara od svakog računati, čak i ako to rezultira u nekim negativnim bilancama? Tako je u osnovi, tu su i četiri Glavne vrste upita - umetnite, odaberite, ažurirati i obrisati. Zato što mislimo da smo će se koristiti ovdje? Update. 

Tako ćemo pogledati. Dakle ovdje smo ažuriranje. Što stol su mi ažuriranja račune? Dakle ažuriranje račune. I onda sintakse, kaže, ono što na računima su mi ažuriranja? Pa, mi smo postavljanje ravnoteže jednak Trenutna vrijednost saldo umanjen za 20 godina. Dakle, to će se ažurirati sve retke računa, oduzimanjem 20 dolara iz ravnoteže. 

David J. Malan: česta pogreška ovdje, iako mi ponekad to oprostio, bio je zapravo PHP kod ovdje pozivanjem funkcije upita ili stavljanjem citati oko svega što ne trebaju biti tamo. 

ROB Bowden: Ne zaboravite da je MySQL zasebna jezika s PHP. Mi se dogoditi da se pisanje MySQL u PHP-u. I PHP zatim ga poslati više na MySQL poslužitelj. No, ne trebate PHP, kako bi se komunicirati s MySQL poslužitelj. 

David J. Malan: Točno. Tako da nema varijable s znakove dolara treba biti u tom kontekstu. To samo može učiniti sve matematike unutar same baze. 

ROB Bowden: OK. Dakle, sljedeći. Je li to sljedeći? Da. Dakle, s tim što SQL upit bi banka dohvatiti brojeva računa od njegovih Najbogatiji kupci, one s stanja veće od 1000? Dakle, što je od četiri glavne vrste ćemo ovdje? Odaberite. Dakle, želimo odabrati. Što želimo odabrati? Što stupac ne želimo odabrati? Mi posebno će htjeti za odabir broja. No, ako je rekao zvijezda, mi također prihvatio da. 

Dakle, odaberite broj s kojim stolom? Računi. I onda uvjet želimo? Gdje stanje veći od 1000. Također smo prihvatili veće od ili jednaka. Zadnji put. S kojim SQL upit bi banka u neposrednoj blizini, tj. izbrisati svaki račun koji ima ravnotežu 0 $? Dakle, što je četiri smo htjeti koristiti? Brisanje. Dakle, sintaksa za to? Brisanje iz koje tablice? Računi. A onda je uvjet kojeg želimo izbrisati - gdje je saldo jednak nuli. Dakle brisanje svih redova iz računa gdje je stanje nula. Pitanja na bilo koji od ovih? Želite li stati u red? 

David J. Malan: Red vodič. Dakle, u tom jednom, ti dali smo ponešto upoznati strukturu koja smo istraženo malo u klasi uz bok tvorevina, koja je data Struktura odnose u duhu. Razlika iako s red je da smo morali nekako sjetiti tko je na prednjem dijelu redu, u velikim dio, tako da smo mogli napraviti više Učinkovito korištenje memorije, barem Ako smo koristili niz. 

Jer podsjetimo, ako imamo niz, ako je, Na primjer, ovo je prednja strana red, ako mi se u redu ovdje, i onda netko dobiva u redu iza mene, iza mene, iza mene, i jedna osoba izlazi iz linije, što mogao, kao što smo vidjeli neke od naših ljudskih Volonteri u klasi, ima sve pomak na ovaj način. No, u cjelini, što svatko radi nešto što nije najbolje korištenje vremena u programu, jer to znači da je Algoritam se izvodi u ono asimptotičnu Trajanje? To je linearno. 

I osjećam se kao da je to glupo. Ako sljedeća osoba na redu je slijedeća Osoba koja bi trebala ići u store, ne svi imaju premjestiti zajedno. Samo neka ta osoba neće iščupati off , kada za to dođe vrijeme, na primjer. Tako možemo uštedjeti malo vremena tamo. I tako se to ipak, to znači da glava redu ili Pročelje red će progresivno kretati dublje i dublje u nizu i na kraju možda zapravo zaokrenuti ako smo pomoću Niz pohraniti narod u tom redu. Dakle, gotovo da možete sjetiti Niz podataka kao kružni struktura u tom smislu. 

Tako da na neki način moraju pratiti veličina njemu ili stvarno kraj njega a zatim gdje je to je početak. Dakle, predlažemo da se proglasi jedan takav red, poziv je q, samo jedno slovo. Onda ćemo predložiti da se prednji postavljene na nulu, a da je veličina biti postavljene na nulu. 

Dakle, upravo sada, nema ništa unutar tog reda. I molimo vas da ispunite Provedba enqueue u nastavku takav način da se funkcija dodaje n na Kraj q, a zatim se vraća true. Ali, ako je q puna ili negativna, Funkcija umjesto toga trebali vratiti false. A ti dali smo par pretpostavki. No, oni nisu stvarno funkcionalno relevantno, upravo to bool postoji, jer, tehnički, bool ne postoje u C, osim ako su sigurno datoteka zaglavlja. Tako da samo se uvjerite da bilo je to trik Pitanje vrsta stvar. 

Dakle u red, predložili smo u uzorku rješenja za provedbu kako slijedi. Jedan, prvo smo provjerili jednostavnost, low-viseće voće. Ako red je pun ili broj koji pokušavate umetnuti manja od nule, što smo rekli u specifikacija problema trebao ne smije dopustiti, jer mi samo želimo ne-negativne vrijednosti, onda ste trebali Samo povratak false odmah. Tako su neki relativno lako provjeru pogrešaka. Ako ipak želite dodati da je stvarna broj, što je morao učiniti malo razmišljanja ovdje. I ovo je mjesto gdje je malo neugodno psihički, jer morate shvatiti kako se nositi cjelina. 

No, klice od ideje da se ovdje je od interes nam je da obmatajuća često podrazumijeva modularna aritmetika i mod operator, posto strana, gdje možete otići iz veće vrijednosti natrag na nulu, a onda jedan i dva i tri, a zatim ponovno oko nule, jedan i dva i tri i tako dalje opet i opet. Dakle, način na koji se predlažu za to je da mi ne želimo da se indeks u Niz zove brojevi gdje naši prirodni brojevi leže. No, kako bi se tamo, prvo želim napraviti bez obzira na veličinu reda je, ali zatim dodati da što god Prednji dio popisa je. A učinak da je staviti nas na Pravo mjesto u redu i Ne pretpostavljaju da je prva osoba u redu je na početku, što je on ili ona je apsolutno može biti ako smo također su prebacuje svima. No, mi samo stvara posao za sebe, ako mi je uzeo da određeni put. 

Dakle, možemo ga zadržati relativno jednostavna. Mi ne moramo se sjetiti da smo upravo dodao int na red. I onda mi samo vrati istina. U međuvremenu, u dequeue, pitali smo što učiniti sljedeće. Provesti na takav način da se dequeues, koji je uklanja i vraća, Int na prednjoj red. Za uklanjanje int, dovoljno to zaboraviti. Vi ne morate nadjačati njegovu bit. Dakle, to je još uvijek zapravo tamo. Baš kao i podataka na tvrdom disku, mi smo samo ignorirajući činjenicu da je sada tu. A ako q je prazna, trebali bismo umjesto da se vrate negativan 1. Dakle, to se osjeća proizvoljna. Zašto vratiti negativan 1 umjesto da lažno? Da. 

PUBLIKA: Q je spremanje pozitivne vrijednosti. Budući da je samo pohraniti pozitivne vrijednosti u q, negativna je do pogreške. 

David J. Malan: OK, istina. Dakle, jer mi smo samo spremanje pozitivno vrijednosti ili nula, onda je u redu da se vratiti negativnu vrijednost kao stražar vrijednost, poseban simbol. Ali ste prepisivanjem povijesti postoji, jer je razlog što smo samo povratka ne-negativne vrijednosti je zato što želimo imaju Sentinel vrijednost. Dakle, konkretno, zašto ne samo povratak false u slučaju pogreške? Da. 

PUBLIKA: Vi ste uspjeli vratiti integer. 

David J. Malan: Točno. I ovo je mjesto gdje C dobiva prilično ograničavajući. Ako si rekao da ćeš da se vrate int, moraš da se vrate int. Ne možete dobiti fancy i početak povratka bool ili float ili string ili nešto slično. Sada je, u međuvremenu, JavaScript i PHP i neke druge jezike, u stvari, ste se vraćaju drugačije vrste vrijednosti. A to zapravo može biti korisno, gdje mogli vratiti pozitivne Ints, nula, Negativni Ints, ili lažna ili null čak i da označi pogrešku. Ali nemamo taj raznovrsnost u C. 

Tako je s dequeue, ono što smo predlaže učiniti je - 

ROB Bowden: Možete vratiti false. To je samo da je lažno je mljeveno meso definirati lažno na nulu. Dakle, ako ste se vratili lažna, vraÄ nulu. I nula je važeća stvar u našem redu, dok je negativna 1 nije li lažno se dogodilo da se negativna 1. No, da ne bi trebali ni moraju znati da. 

David J. Malan: To je zašto ja to nisam rekao. 

ROB Bowden: Ali to nije istina da se ne može vratiti false. 

David J. Malan: Svakako. Dakle dequeue, primijetit ćemo prihvatiti poništava kao svoj argument. A to je zato što nismo prolazi ništa u. Mi samo želimo ukloniti element na prednjem redu. Pa kako bismo mogli ići oko radiš ovo? Pa, prvo, idemo to učiniti brzo razum ček. Ako veličina reda je 0, postoji nema posla koji treba obaviti. Povratak negativna 1. Gotovo. Dakle, to je nekoliko redaka mog programa. Dakle, samo četiri linije ostaju. 

Dakle, ovdje se odlučim za opadanje veličina. I decrementing veličinu učinkovito znači da ja zaboravljam nešto što je tamo. Ali sam isto tako morati ažurirati gdje prednja od brojeva su. Pa za to, trebam učiniti dvije stvari. Ja najprije morate se sjetiti što je broj je na prednjem redu, jer moram vratiti tu stvar. Dakle, ja ne želim da se slučajno zaboravi o tome i onda ga prebrisati. Samo ću se sjetiti u int. 

I sada, želim ažurirati q.front biti q.front jedan. Dakle, ako je to bila prva osoba u linija, sada, ja želim plus 1 do ukazuju na sljedećoj osobi u redu. No, moram se nositi taj spustili. A ako je kapacitet globalna konstanta, da će mi dopustiti da se uvjerite kao što sam naglasiti da je to zadnja osoba u linija, rad po modulu će donijeti ja vratiti na nulu u Pročelje red. I to obrađuje okružujući ovdje. A onda sam nastaviti da se vrati n. 

Sada, strogo govoreći, nisam morati proglasiti n. Nisam ga morati zgrabiti i spremiti ga privremeno, budući da je vrijednost još uvijek tu. Pa sam samo mogao napraviti pravu aritmetiku za povratak bivšeg šefa u redu. No, samo sam osjetio da je to bilo jasnije zapravo zgrabite int, stavite ga u N, a zatim se vratiti da za Jasnoće ali nije strogo potrebno. Psst. Oni su svi izgovorljiv u mojoj glavi. 

ROB Bowden: Dakle, prvo pitanje je binarno stablo problema. Dakle, prvo pitanje je, da smo dao ti brojevi. I želimo da ih nekako umetnuti u tih čvorova, tako da je to vrijedi pretraživanje po binarnom stablu. Dakle, jedna stvar u vezi binary search drveće je da to nije upravo to stvar lijevo manje je i stvar Pravo je veća. To mora biti da je cijelo stablo lijevo je manje, a cijela stabla na desnoj strani je veći. 

Dakle, ako sam stavio 34 ovdje na vrhu, a zatim Stavio sam 20 ovdje, tako da je vrijedi toliko daleko, jer 34 do ovdje. 20 ide na lijevu stranu. Dakle, to je manje. Ali ja ne mogu onda staviti 59 ovdje, jer iako 59 je na desnoj strani od 20, to je još uvijek na lijevoj 34. Dakle, s tim na umu ograničenja, Najlakši način za rješavanje toga vjerojatno Problem je u tome da se samo kakve od tih brojeva - do 20, 34, 36, 52, 59, 106. A zatim ih umetnite s lijeva na desno. 

Dakle, 20 ide ovdje. 34 ide ovdje. 36 ide ovdje. 52, 59, 106. I što je također moglo shvatio s Neki priključivanja i realizirati, oh, čekaj, ja nemam dovoljno brojeve ispuniti to na ovamo. Dakle, trebam reshift ono što je moj Ruta note će biti. Ali primijetite da su u posljednja tri, ako čitate s lijeva na desno, što je u povećanje red. 

Tako sada, želimo izjaviti ono struct će biti za čvorovi u ovom stablu. Dakle, što nam je potrebno u binarnom stablu? Tako imamo vrijednost tipu int, pa su neki int vrijednost. Ne znam što mi se zove se u otopini - int n. Trebamo pokazivač lijevo dijete i pokazivač na pravo djeteta. Dakle, to će izgledati ovako. I to će zapravo izgledati prije nego kad si dvostruko povezana Popis stvari, tako da obavijest - Ja ću se morati pomaknuti sve put natrag do problema 11. 

Dakle primijetiti da izgleda identično to, osim samo mi se dogoditi da ih zovemo različita imena. Mi još uvijek imamo cijeli broj vrijednost i dva naputke. To je samo u tome što umjesto liječenja naputke što ukazuje na sljedeću stvar i natrag stvar, mi smo liječenje pokazivača ukazati na lijevom djeteta i pravo djeteta. OK. Dakle, to je naš struct node. I sada, jedina funkcija trebamo provoditi za to je poprijeko, koji želimo ići preko drveta, tisak iz vrijednosti stabla u cilju. 

Tako izgleda ovdje, mi bi htjeli ispisati od 20, 34, 36, 52, 59, i 106. Kako ćemo ostvariti to? Dakle, to je prilično slično. Ako ste vidjeli u prošlom ispitu je problem da ste htjeli isprintati cijela stabla sa zarezima između sve, što je zapravo još jednostavnije od toga. Dakle, ovdje je rješenje. To je znatno lakše ako ga rekurzivno učinio. Ja ne znam je li itko pokušao to učiniti iterativno. 

Ali prvo, mi imamo bazu slučaj. Što ako je korijen null? Onda mi samo ćemo se vratiti. Mi ne želimo ispisati ništa. Inače ćemo proći rekurzivno dolje. Ispisati cijelu lijevu podstablo. Dakle ispisati sve manje od moje trenutne vrijednosti. A onda ću ja ispisati. A onda ću recurse niz moje Cijeli pravo podstablo, tako da je sve veći od moje vrijednosti. A to će se ispisati iz svega u cilju. Pitanja o tome kako je to zapravo ostvaruje to? 

Ivanković: Imam pitanje Na [nečujan]. 

ROB Bowden: Dakle, jedan način približavanja bilo rekurzivna problem je da samo misle o tome da mi se morate misliti o svim kutak slučajevi. Dakle, smatramo da želimo ispisati cijelu ovu stablo. Dakle, svi ćemo se usredotočiti na je ovaj čvor - 36. U rekurzivni pozivi, možemo se pretvarati oni samo rade. Pa evo, ova rekurzivna poziva na poprijeko, možemo čak i bez razmišljanja o tome, samo poprijeko lijevi tri, zamislite da je već ispisuje 20 i 34 za nas. I onda, kada smo na kraju rekurzivno nazvati poprijeko na U redu, da će pravilno ispisati 52, 59, i 106 za nas. 

Dakle, s obzirom da se ova može ispisivati ​​20, 34, i drugi može ispisati 52, 59, 108, svi moramo biti u stanju učiniti je ispisati mi sami u sredini toga. Dakle ispisati sve pred sobom. Ispis sebe, tako da trenutni čvor za ispis 36, redovito printf, a zatim ispisati sve iza nas. 

David J. Malan: Ovo je mjesto gdje rekurzija dobiva stvarno lijepo. To je ovo nevjerojatna skok vjere, gdje ti i najsitnije malo rada. I onda neka netko drugo učiniti ostalo. A da je netko drugi je, ironično, ti. Dakle, za ozbiljne pčelica bodova, ako se pomaknete gore na pitanja - 

ROB Bowden: Na pitanja? 

David J. Malan: A dolje malo brojeve, zna li netko gdje je ti brojevi dolaze iz? 

ROB Bowden: Imam doslovno nema pojma. 

David J. Malan: Pojavljuju tijekom kviza. 

PUBLIKA: Jesu li isti brojevi? 

David J. Malan: Ti brojevi. Malo uskršnje jaje. Dakle, za one od vas gledati online na kući, ako nam možete reći putem e-maila na heads@CS50.net ono značenje od ove ponavljajući šest brojevi su tijekom kviza 1, mi ćemo vas tuš uz nevjerojatnu pozornost na finalu Predavanje i stres loptu. Nice, suptilna. 

ROB Bowden: Bilo Zadnja pitanja o svemu na kvizu?