DAVID J. Malan: Allt í lagi. Svo velkomið að alltaf fyrst CS50 postmortem hafa próf. Við héldum að við myndum inaugurate þessi hefð á þessu ári. Og þetta mun vera tækifæri að ganga í gegnum lausnir á spurningakeppni. Og við munum flýta eða hægja undirstaða um vexti þeirra hér. 

Svo þú ert líklega hér vegna þess að þú ert áhuga á því hvernig þú gætir hafa eða ætti að hafa svarað nokkrum þessara vandamála. Svo hvers vegna eigum við ekki að líta á þessum kafla fyrst? Svo að fá strengi. Þetta gaf þér þrjár mismunandi útgáfur um forrit sem var að lokum, ætlaði að fá a band frá notanda. Hvort sem það gerði það var vinstri að þér að ákveða. 

Og við spurði í svari við spurningu 0, gera ráð fyrir að útgáfa 1 er safna saman og framkvæma. Hvers vegna kann forritið segfault? Við fyrstu sýn, einhverjar uppástungur á því hvers vegna? Já. 

Áhorfendur: Ég man að sjá þetta í fyrri dæmi um að horfa á char * s og sjá grannskoða af s og sjá því það er bendillinn, hvernig hafði áhrif á það sem þú skannaðar í? Er það er eða heimilisfang hans s? 

DAVID J. Malan: OK. Gott. Svo að lokum, the uppspretta af hvaða vandamál er væntanlega að fara að draga úr að þeirri breytu s. Og það er örugglega breytilegt. Gögnin gerð breytunni er char *, sem þýðir að það er að fara að innihalda veffang staf. Og þar liggur innsýn. Það er að fara að innihalda veffang eðli eða oftast á, að heimilisfang fyrsta staf í allt blokk stafi. 

En afla er að skanna s, tilgangur líf, er gefið upp netfang og gefið snið-, eins og% s, lesa streng í klumpur af minni á þetta netfang. Heldur vegna þess að það er engin jafnaðarmerki áður sem semíkommu á fyrsta lína af kóða, því við höfum ekki í raun úthluta allir minni með malloc, því það gerði í raun ekki úthluta fjölda einhverju stærð, allt þú ert að gera er að lesa notanda hljómborð inntak inn í sumir heill sorp gildi, sem er í s sjálfgefið. Svo líkurnar eru þú ert að fara að segfault ef að heimilisfang er ekki bara svo gerst að vera gildi sem þú getur, í raun, skrifaðu. Svo slæmt ekki að úthluta minni þar. 

Svo í spurningu 1, spurði við, gera ráð fyrir að útgáfa 2 er safna saman og framkvæma. Hvers vegna kann þetta forrit segfault? Svo er þetta eitt minna gallaðir. Og það er í raun aðeins eitt augljós leið þar sem þú getur kveikjan að segfault hér. Og þetta er þema. Hvenær við erum að nota c í minni, hvað gætir þú gert til að vekja segfault með útgáfu 2? 

Áhorfendur: Ef þú notar þessi inntak í streng sem er lengri en 49 stafir. 

DAVID J. Malan: Einmitt. Hvenær sem þú sérð eitthvað fastur lengd þegar það kemur að fjölda, þinn ratsjá ætti að fara burt að þetta gæti verið erfið ef þú ert ekki að haka við Mörk fylki. Og það er vandamálið hér. Við erum enn að nota scanf. Við erum enn að nota% s, sem þýðir að reyna að lesa streng frá notandanum. Það er að fara að lesa í s, sem, á þessum tímapunkti, er í raun að heimilisfang klumpur af minni eða það er jafngild. Það er nafnið fylki stafa af minni. 

En einmitt þessi, ef þú lest streng sem er lengri en 49 stafir, 49 vegna þess að þú þarft pláss fyrir sviga 0, þú ert að fara að flæða yfir sem Buffer. Og þú might fá heppinn og vera fær um að skrifa 51 staf, 52, 53. En á einhverjum tímapunkti OS er að fara að segja, nei. Þetta er örugglega ekki minni þú ert að fá að snerta. Og the program er að fara að segfault. 

Þannig að það er leitandi ætti að vera einhver þegar þú hefur fengið fasta lengd, hefur þú að ganga úr skugga um að þú ert að skoða lengd af hvað það er sem þú ert að reyna til að lesa inn í það. 

Áhorfendur: Svo til að leysa það, þú gætir hafa haft yfirlýsingu stöðva raun er lengd Greater eða minni en? 

DAVID J. Malan: Algjörlega. Þú verður bara með sjúkdóm sem segir, ef - eða öllu heldur þú þarf ekki endilega að vita fyrirfram hversu margir stafir sem notandinn er að fara að slá, því þú hefur kjúklingur og egg. Ekki fyrr en þú hefur lesið það með Scanf getur þú reikna út hversu lengi það er. En á þeim tímapunkti, það er of seint, vegna þess að þú hefur nú þegar lesið það í sumir blokk af minni. Svo sem innskot, the CS50 bókasafn forðast þetta mál að öllu leyti, muna með því að nota fgetc. Og það les einn staf í einu, ábending-toeing eftir, vitandi að þú getur ekki flæða yfir staf ef þú lesa eitt í einu. 

Aflann er með getstring muna er að við verðum að stöðugt aftur stærð að bútur af minni, sem er bara sársauki. Það er a einhver fjöldi af línum kóða til að gera það. Þannig aðra nálgun væri að raunverulega nota frænda, svo að tala, af Scanf. Það eru afbrigði af a einhver fjöldi af þessir aðgerðir sem raunverulega athuga lengd hversu margir stafir þú gætir lesið hámarks. Og þú gætir tilgreint, gera ekki lesið meira en 50 stafir. Svo sem myndi vera annar nálgun en minna greiðvikinn stærri aðföngum. 

Svo spurningu 2 spyr, gera ráð fyrir að útgáfa 3 er unnin og framkvæmd. Hvers vegna kann að program segfault? Svo er þetta eitt í raun það sama svara, jafnvel þó að það lítur svolítið áhugamaður. Við erum með malloc sem líður eins við erum að gefa okkur fleiri valkosti. Og þá erum við frjáls að minni í lokin. Það er samt bara 50 bæti af minni. Þannig að við gætum enn reyna að lesa í 51, 52, 1000 bæti. Það er að fara að segfault fyrir nákvæmlega sömu ástæðu. 

En það er önnur ástæða líka. Hvað annað gæti malloc aftur auki veffang klumpur af minni? Það gæti aftur null. Og vegna þess að við erum ekki að haka við að við gætum verið að gera eitthvað heimskur fyrir aðra ástæðu, sem er að við gætum verið að segja scanf, lesa inntak notandans af lyklaborði í 0 staðsetning, AKA null. Og það líka, verður örugglega kveikjan að segfault. Svo fyrir tilgangi spurningakeppni er, við myndum hafa samþykkt annaðhvort á þeim sem gild ástæða. Eitt er eins. Eitt er svolítið meira nuanced. 

Loksins, með tilliti til áætlunarinnar notkun minni, hvernig útgáfu 2 og útgáfa 3 mismunandi? Svo fyrir hvað það er þess virði, sáum við virðist endalaus framboð af mögulegt svör við þessu. Og meðal svörum fólks, það sem við vorum vonast eftir, en við samþykkt aðrar hlutir, var einhver minnst á staðreynd að útgáfa 2 er að nota svokallaða stafla. Útgáfa 3 er að nota hrúga. Og virkni, þetta er í raun ekki gera allt sem mikið af a mismunur. Í lok dagsins, erum við enn bara að fá 50 bæti af minni. 

En það var einn af mögulegum svörum að við vorum að horfa á. En þú munt sjá, eins og þú fá Skyndipróf baka frá TFS, sem við gerðum samþykkja aðrar umræður um þeirra ólíkum not af minni eins og heilbrigður. En stafla og hrúga hefði verið auðvelt svar við fara með. Einhverjar spurningar? Ég gef þér Rob. 

ROB BOWDEN: Svo vandamálið 4. Þetta er eitt þar sem þú þurfti að fylla í fjölda bæti út af öllum þessar mismunandi tegundir notaðar. Svo fyrsta sem við sjáum. Gera ráð fyrir 32-bita arkitektúr, svona CS50 tæki. Svo eitt af grundvallar hluti um 32-bita arkitektúr, sem segir okkur nákvæmlega hversu stór bendillinn er að fara að vera í arkitektúr. 

Það strax, við vitum að einhver bendi tegund er 32-bita eða 4 bæti. Svo að horfa á þetta borð, node * er bendi tegund. Það er að fara að vera 4 bæti. Struct node *, það er bókstaflega eins hnút stjörnu. Og svo það er að fara að vera 4 bæti. Band, svo það lítur ekki út eins og bendillinn enn, en typedef, A band er bara char * sem er bendillinn tegund. Svo það er að fara að vera 4 bæti. 

Svo þessir þrír eru allir 4 bæti. Nú, hnút og nemandi eru aðeins flóknara. Svo að horfa á hnút og nemandi, sjáum við hnút sem heiltala og músina. Og nemandi er tvær ábendingum inni af því. Svo að minnsta kosti fyrir okkar tilviki hér, hvernig að við á endanum að reikna stærð þetta struct er bara að bæta upp allt sem er inni í strúktúr. 

Svo fyrir hnút, höfum við heiltölu, sem er 4 bæti. Við höfum bendi, sem er 4 bæti. Og svo einn hnút er að fara að taka upp 8 bæti. Og tilsvarandi fyrir nemanda, þá erum við með bendillinn sem er 4 bæti og annað bendillinn sem er 4 bæti. Svo það er að fara að enda upp tilvera 8 bæti. Svo hnút og nemandi eru 8 bæti. Og þessir þrír eru allir 4 bæti. Spurningar um það? Já. 

Áhorfendur: Er það var 64-bita arkitektúr, vildi að tvöfaldur þá alla? 

ROB BOWDEN: Það væri ekki tvöfaldur þeim öllum. Svo 64-bita arkitektúr, það, aftur, breytingar sem grundvallaratriði hlutur að bendillinn er nú 64 bita. Já. Svo er bendillinn 8 bæti. Svo þessar sem voru 4 bæti eru að fara að vera 8 bæti. Nemandi, sem var tveggja ábendingum, Jæja, nú er það að fara að vera 8 bytes, 8 bæti. Það er að fara að gera 16 bæti. 

En hnúturinn er enn 4 bæti. Svo þetta bendi er að fara að vera 8 bæti. Þetta er 4 bæti. Svo hnút er bara að fara að vera 12 bæti. Aðrar spurningar í þetta? Þannig að næsta einn, þetta eru the HTTP kóða. Og þú þurftir að lýsa aðstæðum þar sem þessi gæti aftur til þín. Eitt vandamál sem ég heyrði sumir nemendur hafa er að þeir reyndu að gera villur vera á enda viðskiptavinarins. Svo þegar við reynum að gera beiðni til miðlara, eitthvað fer rangt á enda okkar. En yfirleitt eru þessir kóðar að koma aftur af þjóninum. Þannig að við viljum að reikna út hvað er að gerast rangt eða rétt á þjóninum sem veldur þetta að koma aftur. Svo hvers vegna gæti netþjóni skilar stöðukóði 200? Allir hugsun? 

Já. Svo eitthvað um með góðum árangri beiðnin fór í gegnum. Og þeir eru færir um að skila hvað sem þú baðst um. Þannig að allt var í lagi. Hvað um 302 fundust? Já. 

Áhorfendur: Miðlarinn var að leita fyrir það sem þú baðst um. En það gat ekki fundið hann. Þannig að það er villa. 

ROB BOWDEN: Svo þjóninum var leita að því sem þú vildir. Svo bara að leita hér, 302 fundust, það var fær til finna það. 

Áhorfendur: Fyrirgefðu. Fann þýðir að þeir gerðu finna það. Sorry. 

ROB BOWDEN: Svo 302 fundust. The framreiðslumaður er fær um að finna það sem þú vildir. 

Áhorfendur: En það er ekki að sýna það? 

ROB BOWDEN: Munurinn á milli þetta 302 og 200 er að það veit hvað þú vilt. En það er ekki nákvæmlega hvar þú vildi spyrja. Svo er 302 dæmigerður endurvísa. Svo þú beðið síðu. Það veit, ó, ég vil að skila þér þessu. En þetta er á aðra vefslóð. Svo hey, þú vilt í raun og veru þetta. 

DAVID J. Malan: Það er stykki sem sagði að við gáfum ykkur áframsenda fall sem notað haus virka sem aftur á móti, prentað út staðsetningu, ristill, og þá slóðin sem þú vilt hafna notanda. Jafnvel þó að þú hafir ekki séð 302 sérstaklega þar, það er það sem PHP myndi dularfullur setja sem haus segja nákvæmlega hvað Rob sagði það - fundust. En fara hér í staðinn. 

ROB BOWDEN: OK. Og hvað um 403 bannað? 

Áhorfendur: Ég held að það er þessi the framreiðslumaður er í rauninni að segja að viðskiptavinurinn getur ekki opnað heimasíðuna. 

ROB BOWDEN: Svo já. Jæja, dæmigerð svarið við vorum von er eitthvað eins og skrár eru ekki chmodded viðeigandi hátt. Það er líklega undir hvaða kringumstæðum þú sást þá. En það er ástæða þess að viðskiptavinurinn gæti verið að kenna hér. Það er reyndar annar stöðukóði - 401. Svo að þetta eru mjög svipuð. 

401 er óheimil. Og 403 er bannað. Og svo óviðkomandi að eingöngu fá ef þú ert ekki skráður inn En að skrá þig inn gæti þýtt að þú hefur heimild. En ef þú ert nú þegar skráður inn og þú enn hefur ekki leyfi, þá þú getur líka fengið bannað. Þannig að ef þú ert skráður inn og hafa ekki leyfi, bannað er einnig eitthvað sem þú getur fengið. 

DAVID J. Malan: Og Orsakir sem þessi vandamál eru oftast leyst á þjóninum er um hvaða stjórn? Chmod, ef það er, Reyndar leyfi gefa á skrá eða möppu. 

ROB BOWDEN: Þá 404 fannst ekki. Já. Svo ólíkt 302 þar sem það var ekki nákvæmlega þar sem þú ert að spyrja, en það veit hvað þú vilt, þetta, það hefur bara ekki hugmynd um hvað þú vilt. Og þú ert ekki að biðja eitthvað gildi. 418 Ég er katli og þá 500 innri miðlara. Svo hvers vegna gætir þú fengið það? 

Svo segfault - Ég reyndar veit ekki flokkunina staðall fyrir þetta. En ef PHP kóðann þinn hefði eitthvað rangt í það, í orði, gæti það reyndar segfault, í því tilviki, þetta 500 innri miðlara villa, eitthvað er athugavert við miðlara þíns stillingar. Eða það er Stílvilla í PHP kóðann þinn. Eða eitthvað slæmt er að gerast. 

DAVID J. Malan: Við vildum sjá segfault meðal svörum nokkurra fólks. Og tæknilega, gæti það gerst. En það væri PHP, the program skrifað af öðru fólki, í raun segfaulted, sem aðeins ef þessir menn ruglaður upp og skrifaði gallaðir kóða í túlkur þeirra myndi PHP sjálft segfault. Svo jafnvel þó 500 er eins og segfault í anda, það er næstum alltaf afleiðing af a skrá stillingar tölublað með vefþjóninum þínum eða, eins og Rob sagði, A Stílvilla, eins og þú ekki loka tilboð. Eða þú tapað semíkommu einhvers staðar. 

Áhorfendur: Svo fyrir Shuttle pset, ég hugsa þegar ég gerði það þegar ég smellti á vafra, en ekkert kom upp, hvað þeir kallast hvítt síðu. En það var vegna þess að kóða. Ég held það hafi JavaScript, ekki satt? 

ROB BOWDEN: Já. 

Áhorfendur: Vildi að villa enn koma upp? 

ROB BOWDEN: Svo þú myndi ekki hafa fengið þessi villa vegna þess að allt frá sjónarhóli Vefþjónninn er var alveg fínn. En þú baðst um index.html. Þú baðst shuttle.js og service.js. Og það var fær til giftusamlega aftur þér alla þá hluti - 200. OK. Það er aðeins þegar vafrinn þinn reyndi að túlka JavaScript kóða sem það er eins og, bíddu, þetta er ekki Gildir JavaScript villa. Aðrar spurningar? Allt í lagi. 

DAVID J. Malan: Svo næst upp var númer 11. Og 11 mest ógnvekjandi fyrir fullt af fólki. Svo er mikilvægast að hafa í huga hér var að þetta var reyndar um A tvöfalt tengda listanum. En þetta var ekki það sama og á síðasta ári tvöfalt tengda listanum vandamál, sem ekki gefa þér hellir sem listinn gæti í raun að vera óflokkað. 

Svo sú staðreynd að listinn var óflokkað og sú staðreynd að þessi orð voru undirstrikað að það var ætlað að flytja að þetta er í raun einföldun hvað sem annars hefði verið meira krefjandi vandamál og með lengri einn. Svo algeng mistök hér var að hafa sett lausn á síðasta ári á einn þinni Friðþjófur og þá bara í blindni afrita að niður sem svar, sem er rétt svara til mismunandi spurningu svipuð í anda. En næmi hér voru sem hér segir. 

Svo einn, við höfum hnút lýst og og skilgreint er í venjulegum hætti hér. Þá erum við skilgreint lista af að vera alþjóðlegt bendillinn frumstilla að null. Þá virðist, það er tvær aðgerðir við höfum fyrirmynd að hér, settu og fjarlægja. Og þá höfum við nokkur dæmi um kóða hér að gera fullt af innsetning. Og þá biðjum við þig um að ljúka framkvæmd insert neðan í svo hátt að það setur n inn á listann í föstu tíma, einnig undirstrikað, jafnvel þegar til staðar. 

Svo fegurð að vera fær um að setja í föstu tíma er að það felur í sér að þú þarft að setja nýja hnút þar? Í framan. Svo eyðir það, sem betur fer, að minnsta kosti einn af þeim tilvikum sem notuð eru til að krefjast jafnvel fleiri línur af kóða, eins og það gerði á síðasta ári og jafnvel í bekknum þegar við talaði í gegnum þessa tegund af hlutur með mönnum og með nokkrum munnleg gervi kóða. Svo í lausn hér, við skulum sleppa yfir til að bara að hafa Visual á á skjánum. 

Takið eftir að við erum að gera eftirfarandi. Og einnig taka aðra einföldun var að jafnvel ef það er þegar til staðar, þannig að þetta þýðir jafnvel þótt fjöldi er þar nú þegar, þú getur bara í blindni að setja annan afrit af því. Og það var líka ætlað að vera einföldun, svo að þú gætir leggja áherslu á, í raun, sumir af the fleiri intellectually áhugaverður hluti og ekki bara sumir viðbótar villuprófun Í ljósi þess takmarkaða tíma. 

Svo í þessu úrtaki lausn, úthluta við bendill á the vinstri-hönd hlið hér til hnút. Nú, átta sig á að músina, eins og Rob sagði, er aðeins 32 bita. Og það er í raun ekki innihalda veffang þar til þú tengja það á netfangið. Og það gerum við á hægri hönd hlið í gegnum malloc. Eins gott borgara, athugaðu að við að malloc er ekki, í raun, null, svo að við gerum ekki tilviljun búa A segfault hér. Og hvenær þú notar malloc í lífinu, þú skal stöðva fyrir engu, svo þú hafa a lúmskur galla. 

Þá erum frumstilla þessi null með framselja n og fyrri og næsta. Og í þessu tilfelli hér, ég frumstilla fyrri til engu, vegna þess að þetta nýja hnútur er að fara að vera nýr farin af listanum mínum. Þannig að það er að fara að vera ekkert fyrir það. Og ég vil í raun bæta við núverandi lista til nýjan hnút með setja næst jafnt lista sig. En ég er ekki búinn strax. Þannig að ef listinn sig þegar fyrir hendi, og það var að minnsta kosti einn hnút þegar í stað, ef þetta er listi hér og ég set inn nýjan hnút hér, ég þarf að ganga úr skugga um að fyrrverandi hnút mín bendir aftur til nýjan hnút minn, því þetta er, aftur, A tvöfalt tengda listanum. 

Svo við gerum geðheilsu stöðva. Ef listinn er ekki núll, ef það er þegar eitt eða fleiri hnútar þar, þá bæta við að baka tilvísun svo að segja. Og þá mjög síðasta sem við þurfum að gera er í raun að endurnýja á heimsvísu breytu lista sjálft að benda að þessi nýja hnút. Já. 

Áhorfendur: Í músina ör [Inaudible] jafngildir null, er sem takast á við listann vegna listinn er null? 

DAVID J. Malan: Nope. Það er einfaldlega mér að vera stanslaust varlega, þannig að ef það er mín upprunalega lista með kannski sumir fleiri hnútar hérna og ég er að setja minn nýr hnútur hérna, það er að fara að vera ekkert hérna. Og ég vil taka þessi hugmynd með því að setja fyrri til null á nýjan hnút. Og væntanlega, ef númerið mitt er rétt og það er engin önnur leið til að setja inn hnúður aðrar en þessa aðgerð, væntanlega, jafnvel þótt listinn hefur nú þegar eitt eða fleiri hnútar í henni, væntanlega Listi, fyrsta hnút, myndi hafa Fyrri bendi af engu sig. 

Áhorfendur: Og bara fylgt eftir. Ástæðan þú setur músina næstu Jafnt listi er að þú ert að gera bendilinn áður lista í að það er að benda til annars, held ég - Ég áttina - bara listum? 

DAVID J. Malan: Einmitt. Og svo skulum við íhuga í raun tvö mál hér í raun, jafnvel þótt röð við munum íhuga þá er ekki alveg það sama og númerið. En á háu stigi, ef þetta táknar lista og þetta er 32-bita músina, einfaldasta atburðarás er að þetta er núll sjálfgefið. Og hygg ég vil setja á númer 50 var fyrsta númerið. Þannig að ég ætla að fara á undan og úthluta hnút, sem er að fara að vera þremur sviðum - n, fyrri, og næsta. 

Ég ætla að setja númerið 50 hér, vegna þess að þetta mun vera n. Þetta verður næst. Og þetta mun vera síðasta. Og svo hvað á ég að gera í þessu tilfelli? Jæja, ég hef bara gert línu 1 hér. Pointer n fær n. Ég er þá að segja, fyrri ætti að fá null. Þannig að þetta er að fara að vera núll. Þá er ég að fara að segja næst er að fara að fá lista. 

Og þetta virkar bara vel. This er núll. Og svo ég er að segja, nýja hnút er næst sviði ætti að fá hvað sem þetta er. Svo setur að öðru null þar. Og þá the síðastur hlutur Ég er að athuga hér. Ef listinn er ekki jafnt og núll, en það er jafnt og núll, þannig að við sleppt því að að öllu leyti. Og svo allt sem ég gera næst er listi fær músina, sem pictorially leiðir mynd eins og þessi. Svo er það eitt dæmi. 

Og sá sem þú varst að biðja um sérstaklega er ástand eins og þetta, þar sem við höfum nú þegar einn hnút lista. Og ef ég fer aftur upp í upprunalega vandamál yfirlýsingu, næsta sem við munum setja segja er 34, bara til sakir umræðu. Þannig að ég ætla að bara þægilegur teiknað það hérna. Ég hef bara malloced. Skulum gera ráð ég að haka við null. 

Nú, ég ætla að frumstilla n til að vera 34. Og þetta mun vera n. Þetta verður næst. Og þetta mun vera síðasta. Við skulum vera viss um að ég gerði ekki fá þetta aftur á bak. Fyrri kemur fyrst í skilgreiningunni. Leyfðu mér að laga þetta. Þetta er fyrri. Þetta er næst. Jafnvel þó þessir sömu, skulum halda það stöðug. 

Fyrri. Þetta er næst. Svo ég hef bara malloced huga minn, merkt for null, úthlutað 34 í hnút. Fyrri fær null. Svo gefur það mér að. Næst fær lista. Svo listi er þetta. Svo er þetta sama núna og teikna þetta arrow, þannig að þeir benda til einn í sama. Og þá er ég að athuga hvort listinn er ekki jafnt null. Og það er ekki í þetta sinn. Þá er ég að fara að gera lista Fyrri fær músina. 

Svo baka einn fær PTR. Á sama tíma hefur það áhrif á að setja myndrænt ör hér. Og það er að fá smá bylgjaður, línurnar. Og þá loks, endurnýja ég lista til að benda á músina. Svo nú bendir þetta til þessa strákur. Og nú, við skulum gera a fljótur geðheilbrigði stöðva. 

Hér er listi, sem er alþjóðlegt breytu. Fyrsti hnúturinn er reyndar 34, því Ég er eftirfarandi þessi ör. Og það er rétt af því að ég vil að setja inn í upphafi listanum Allar nýjar hnúður. Næsta reit hans leiðir mig að þennan gaur. Ef ég halda áfram, högg ég næst er núll. Þannig að það er ekki meira lista. Ef ég högg fyrri, fæ ég aftur þar sem ég býst við. 

Þannig að það eru enn nokkrar ábendingar, augljóslega, að vinna. Heldur sú staðreynd að þú varst að segja að gera þetta í föstu tíma þýðir að þú aðeins hafa endanlegt ýmislegt þú ert að fá að gera. Og hvað er að tala? Það gæti verið eitt skref. Það gæti verið tvær. Það gæti verið 1000 skref. En það er tímabundið, sem þýðir að þú getur ekki hafa hvers konar lykkja gerast hér, engin endurkvæmni, engar lykkjur. Það er bara að vera harður-dulmáli línur af kóða sem við höfum í þessu úrtaki. 

Svo næsta vandamálið 12 bað okkur um að ljúka framkvæmd Fjarlægja hér að neðan á þann hátt að það fjarlægir n af lista í línulegum tíma. Svo þú hafa a lítill fleiri wiggle pláss núna. Þú getur gert ráð fyrir n, ef til staðar á listanum, verður að vera til staðar ekki meira en einu sinni. Og það líka er ætlað að vera quiz byggir einfalda forsendu, svo að ef þú finnur númer 50 einhvers staðar á listanum, þú ert ekki líka að hafa áhyggjur af að halda áfram að iterate, leita hvert mögulegt Afrit af 50, sem myndi bara flytjast í sumum minutia í takmarkaðan tíma. 

Svo með Fjarlægja, þetta var ákveðið meira krefjandi og meira kóða til að skrifa. En við fyrstu sýn, hreinskilnislega, gæti það líta yfirþyrmandi og eins og eitthvað það er engin leið að þú gætir hafa koma upp með á spurningakeppni. En ef við leggja áherslu á einstaka skrefum, vonandi mun það allt í einu slá þig um að hver þessara einstaklinga skref gerir augljóslega vit í hyggja. Þannig að við skulum taka a útlit. 

Svo fyrst, frumstilla við músina að vera listi sig. Vegna þess að ég vil línulegum tíma, sem þýðir að Ég ætla að hafa smá lykkju. Og algeng leið til iterate yfir hnúður á lista byggingu eða hvers konar af uppbyggingu iteratively er að taka bendi á the andlit af the gögn uppbyggingu og þá bara byrja að uppfæra það og ganga leið í gegnum þau gögn uppbygging. Þannig að ég ætla að gera nákvæmlega það. 

Þó músina, tímabundin breytu minn, er ekki jafn null, við skulum fara á undan og athuga. Gerði ég fá heppinn? Er n sviði í hnút Ég er nú horfa á jafnt við númer ég er að leita að? Og ef svo er, við skulum gera eitthvað. Nú, eftir því ef ástand umlykur öllu Eftirfarandi línur af kóða. Þetta er það eina sem mér þykir vænt um - finna fjölda sem um ræðir. Þannig að það er engin annar, sem einfaldar hlutirnir í eðli svolítið. 

En nú, áttaði ég, og þú gætir hafa Aðeins áttaði sig á þessu eftir að hugsa það í gegnum hluti, það er reyndar tvö mál hér. Einn er þar sem hnúturinn er á að upphafið af listanum, sem er smá pirrandi, því það er sérstakt tilfelli, vegna þess að þú þarft að takast á með þetta, sem er eina frávik. Annars staðar á listanum, það er sama. Það er fyrri hnút og næstu hnút, fyrri hnút, næsta hnút. En þessi strákur er svolítið sérstakt ef hann er í upphafi. 

Þannig að ef bendillinn jafngildir lista sjálft, þannig að ef ég er í upphafi listi og ég hef fundið n, ég þarf að gera nokkra hluti. Eitt þarf ég að breyta lista til benda í næsta svið, 50. Svo ætla að ég er að reyna að fjarlægja 34. Svo þessi strákur fékk að fara burtu í aðeins augnablik. 

Þannig að ég ætla að segja, listi fær músina næst. Jæja, þetta er bendillinn. Næst er að benda á hér. Þannig að þetta er að breytast þessa ör rétt nú til að benda á þennan gaur hérna. Nú, muna, höfum við tímabundið breytu. Svo við höfum ekki munaðarlaus nein hnúta, því ég hef líka þessa dagana að mínu framkvæmd fjarlægja. Svo nú, ef listi sjálft er ekki núll, Ég þarf að festa a lítill eitthvað. 

Ég þarf að gera nú viss um að þetta ör, sem er áður benda 50-34, þetta hefur fengið að fara í burtu, því ef ég er að reyna að losna af 34, 50 höfðu betur ekki halda einhverju konar aftur tilvísun í það sem arrow leiðbeinandi. Svo ég gerði bara þessa línu. Svo þá er ég búinn. Að málið er í raun frekar auðvelt. Chopping burt höfuð listanum er tiltölulega einfalt. 

Því miður, það er þetta pirrandi annars blokk. Svo nú verð ég að taka málið fyrir þar er eitthvað í miðjunni. En það er ekki of hræðilegur, nema fyrir setningafræði eins og this. Þannig að ef ég er ekki í upphafi að lista, ég er einhvers staðar í miðjunni. Og þessi lína hér er að segja, byrja á hvað hnút sem þú ert á. Fara á næsta reit fyrri hnúturinn er og benda að á músina. 

Skulum gera þetta pictorially. Það var að fá flókinn. Svo ef ég hef fyrri reiti hér - skulum gera þetta - næsta svæði hér. Ég ætla að einfalda ábendingum mínum fremur en draga a heild búnt af hlutir og til baka crisscrossing hvert annað. Og nú, við skulum bara segja að þetta er 1, 2, 3 fyrir sakir umræðu, jafnvel þó að ekki stilla upp með vandamálið sem um ræðir. 

Svo er hér tengdur minn listi. Ég er að reyna að fjarlægja tvö í þessu einkum útgáfa af sögunni. Svo ég hef uppfært bendi til vera að benda þessum gaur. Svo er þetta PTR. Hann er að benda hér. Þetta er listi, sem er til staðar heimsvísu eins og áður. Og hann er að benda hér, sama hvað. Og nú ætla ég að reyna að fjarlægja tvö. 

Þannig að ef bendillinn er að benda hér, ég er fara að fylgja, virðist, Fyrri músina, sem setur mig í 1. Ég ætla þá að fara að segja að næsta sviði, sem færir mig yfir til þessa kassi hér, er að fara að jafn músina næst. Þannig að ef þetta bendi, er þetta næst. Það þýðir að þetta arrow þörfum til að benda á þennan gaur. 

Svo hvað þessi lína af kóða er bara gert er a lítill hluti af þessu. Og nú, þetta er að leita eins og a skref í rétta átt. Við viljum fyrst og fremst að snip 2 út á miðju 1 og 3. Svo gerir það á tilfinninguna að við viljum Leiðin þetta bendi í kringum hana. Þannig að þetta næsta lína er að haka ef bendillinn næsta er ekki null, það er örugglega einhver til hægri á 2, það þýðir að við verðum einnig að gera smá snip hér. 

Þannig að ég þarf nú að fylgja þessari músina og uppfæra fyrri bendilinn þessi strákur að gera a lítill hluti af a Lausn hér haga hér. Og nú, sjónrænt er þetta ágætur. Það er svolítið sóðalegur á að það er enginn bendir á 2 lengur. 2 er bendir til vinstri. Og 2 er bendir til hægri. En hann getur gert hvað sem hann vill, því hann er að fara að fá frelsi. Og það skiptir ekki máli hvað sem gildin eru lengur. 

Hvað er mikilvægt er að eftir krakkar eru að venja ofan og fyrir neðan hann núna. Og reyndar, það er það sem við gerum næst. Við frjáls músina, sem þýðir að við segja að stýrikerfi, þú ert velkominn að endurheimta þetta. Og þá loks aftur við. Else óbeint, ef við hafa ekki skilað enn, við verðum að halda að leita. Svo bendi jafngildir músina næst bara þýðir færa þennan gaur hérna. Færa þennan gaur hérna. Færa þennan gaur hér ef í raun, við höfum ekki fundið númerið við erum að leita að enn. 

Svo satt, það lítur alveg yfirþyrmandi, held ég, í fyrstu litið, sérstaklega ef þú barátta með þetta á spurningakeppni þá sjá eitthvað eins og this. Og þú klappa þér á bakinu. Jæja, það er engin leið að ég gæti haft koma upp með það á prófinu. En ég myndi halda því fram, þú getur ef þú brýtur það niður í þessum einstaka tilvikum og bara ganga í gegnum það vandlega, að vísu, að vísu, undir streituvaldandi aðstæður. 

Sem betur fer, myndin gerð allt hamingjusamari. Þú gætir teiknað þetta í allir tala af lifnaðarhættir. Þú þarft ekki að gera crisscrossing hlutur hér. Þú getur gert það með beinum línur líkar þetta. En GIST af þessu vandamáli, í Almennt var að átta sig á því mynd í lokin ætti að líta svolítið eitthvað eins og þetta, vegna þess að föstu tíma í skyn að þú haldir jamming og jamming og jamming nýja hnúta í upphafi af listanum. Einhverjar spurningar? Sennilega mest krefjandi vissulega erfðaskrá spurningar. 

Áhorfendur: Svo er listi svipað höfuð í fyrri dæmum. 

DAVID J. Malan: Einmitt, einmitt. Bara annað nafn fyrir alþjóðlegt breytu. Heimsvísu hvað? 

ROB BOWDEN: OK. Þannig að þetta er eitt þar sem þú þurfti að skrifa málsgreinina. Sumir skrifaði ritgerðir fyrir þessa spurningu. En þú þarft bara að nota þessa sex hugtök til að lýsa því hvað gerist þegar þú reynir að hafa samband facebook.com. Svo ég verð bara að tala í gegnum ferlið nota alla þessa skilmála. Svo í vafranum okkar, slá við facebook.com og ýttu á Enter. Svo vafra okkar er að fara að reisa HTTP óskað eftir því að það er að fara að senda gegnum nokkur ferli til Facebook fyrir Facebook að svara okkur með HTML á síðu hennar. 

Svo er það ferli sem HTTP beiðni í raun fær til Facebook? Svo fyrst þurfum við að þýða Facebook.com. Svo bara gefið nafnið Facebook.com, þar raunverulega hjartarskinn HTTP beiðni þurfa að fara? Þannig að við þurfum að þýða Facebook.com til IP heimilisfang, sem einstaklega bent hvað vél við raunverulega langar að senda þessa beiðni til. Fartölvuna hefur IP tölu. Nokkuð tengd við internetið hefur IP tölu. 

Svo DNS, Domain Name System, sem er hvað er að fara að takast á við þýðingu frá facebook.com til IP heimilisfang sem þú vilt í raun að hafa samband. Þannig að við að hafa samband við DNS framreiðslumaður og segja, hvað er facebook.com? Það segir, ó, það er IP tölu 190,212 eitthvað, eitthvað, eitthvað. Allt í lagi. Nú, ég veit hvað vél Ég vil hafa samband. 

Svo þá senda HTTP beiðni þína yfir þessi vél. Svo hvernig hjartarskinn það fá að þessi vél? Jæja, beiðni fer frá leið til leið skoppar. Mundu dæmi í bekknum, þar sem við sáum í raun leiðina að pakka tók þegar við reyndum til samskipta. Við sáum það hoppa yfir Atlantshafið Haf á einum stað eða hvað. 

Svo síðasta tíma höfn. Svo er þetta nú á tölvunni þinni. Hægt er að hafa marga hluti eins samskiptum við internetið. Svo ég geti verið í gangi, td Skype. Ég gæti hafa a vefur flettitæki opinn. Ég gæti hafa eitthvað sem torrenting skrár. Svo öll þessi atriði eru samskiptum við internetið á einhvern hátt. 

Svo þegar tölvan þín fær nokkur gögn af internetinu, hvernig virkar það vita hvaða forrit í raun vill gögnin? Hvernig virkar það vita hvort þetta tiltekna gögn er ætlað fyrir torrenting umsókn öfugt til the vefur flettitæki? Þannig að þetta er tilgangur höfnum sem öll þessi forrit hafa krafa tengið á tölvunni þinni. Svo segir vefur flettitæki, hey, Ég er að hlusta á höfn 1000. Og torrenting program þinn er að segja, Ég er að hlusta á höfn 3000. Og Skype segir, ég er að nota port 4000. 

Svo þegar þú fá sumir gögn sem tilheyrir að einn af þessum forritum, gögn er merkt við hvaða höfn það í raun skal senda eftir á. Svo segir þetta, ó, tilheyra ég til höfn 1000. Ég veit þá þarf ég að senda þetta eftir að vafranum mínum. Svo það er ástæðan viðeigandi hér er þessi vefur framreiðslumaður tilhneigingu til hlusta á höfn 80. Svo þegar ég samband við Facebook.com, ég er samskipti með einhverjum vél. En ég þarf að segja hver tengi sem vél Mig langar að eiga samskipti við. Og vefur framreiðslumaður tilhneigingu til að vera hlusta á höfn 80. 

Ef þeir vildu, gætu þeir sett það upp svo lista það sem á höfn 7000. Og síðan í a vefur flettitæki, ég gat höndunum tegund Facebook.com: 7000 til senda beiðni til höfn 7000 af Facebook vefþjóni. 

DAVID J. Malan: Og í þessu tilfelli, jafnvel þó við höfum ekki krefjast þess að fólk nefna þessu, í þessu tilfelli, hvað tengi myndi beiðni raunverulega fara að? Reyndu aftur. Nákvæmlega. Ekki útlit fyrir það, en lipurðar það er það engu að síðustu. 

ROB BOWDEN: Svo HTTPS, þar sem það er hlusta sérstaklega fyrir dulkóðuð, það er á höfn 4430. 

Áhorfendur: Og póstur er 25, ekki satt? 

DAVID J. Malan: Outbound emails, 25, Já. 

ROB BOWDEN: Ég veit ekki einu sinni af the - öll neðri sjálfur tilhneigingu til að vera frátekið fyrir hlutum. Ég held að allt undir 1024 er frátekið. 

Áhorfendur: Hvers vegna sagðirðu 3 var rangt númer? 

ROB BOWDEN: Vegna þess að í IP heimilisfang, það er fjórum söfn tölustöfum. Og þeir eru 0-255. Svo er 192.168.2.1 algeng staðbundin net IP tölu. Taka eftir öllum af þeim eru minna en 255. Svo þegar ég byrjaði með 300, sem gæti ekki hugsanlega hafa verið einn af þeim tölum. 

DAVID J. Malan: En það kjánalegt myndband frá - var það CSI, þar sem þeir höfðu númer sem var of stór fyrir IP tölu. 

ROB BOWDEN: Einhverjar spurningar um þetta? Næsta einn, svo gjörbreyst atriði, en við höfum þetta PHP array fyrir hús í quad. Og við höfum óraðaðan lista. Og við viljum að prenta út hvert atriði á listanum bara innihalda nafn húsið. Þannig að við höfum framhandleggur lykkja. Svo man, setningafræði er framhandleggur array sem lið í array. Svo í gegnum hverja ítrun lykkju, Húsið er að fara að taka á einu af gildi innan fylkisins. 

Á fyrsta endurtekning, hús verður Cabot House. Á annarri endurtekning, hús mun vera Courier House og svo framvegis. Svo fyrir hvern quad heimilishundar, erum við bara að fara að prenta - þú einnig gætu hafa bergmálað - að atriði á listanum og síðan nafn hússins og svo loka atriðinu. The hrokkið axlabönd eru valfrjáls hér. 

Og þá ég sagði líka í spurningunni sjálft, muna að loka óraðaðan lista tag. Þannig að við þurfum að hætta PHP háttur í því skyni að gera þetta. Eða við gætum hafa bergmálað í loka upptalningu merkinu. 

DAVID J. Malan: Einnig fínn hér myndi hafa verið að nota gamla skóla fyrir lykkja með $ i = 0 0 og nota talningu til reikna út lengd geislans. Algerlega fínn líka, bara smá wordier. 

Áhorfendur: Svo ef þú ætlaðir að [Inaudible], myndir þú gera - Ég gleymi því, að lykkja [inaudible] er. Vilt þú $ quad krappi ég? 

DAVID J. Malan: Einmitt. Já, einmitt. 

ROB BOWDEN: Nokkuð fleira? 

DAVID J. Malan: Allt í lagi. Málamiðlanir. Þannig að það voru bunches af svörum mögulegt er fyrir hvert þessara. Við vorum í raun bara að leita að eitthvað sannfærandi fyrir tímann og hæðir. Og númer 16 spurði, sannprófa notendur ' inntak viðskiptavinur-hlið, eins og með JavaScript, í stað þess að framreiðslumaður-hlið, eins og með PHP. Svo er það sem kosti um gera client-megin? 

Jæja, einn af þeim hlutum sem við fyrirhuguð er að þú draga leynd, vegna þess að þú ekki að nenna að hafa samband við miðlara, sem gæti tekið nokkrar millisekúndur eða jafnvel í nokkrar sekúndur með því að forðast það og bara staðfesta notenda inntak viðskiptavinur hlið með kveiki á-leggja stjórnandinn og bara að skoða, gerðu þeir slá eitthvað í fyrir nafni? Gerðu þeir slá eitthvað í fyrir netfang? Did þeir velja dorm frá falla-dúnn matseðill? 

Þú getur gefið þeim tafarlaus viðbrögð nota gigahertz tölvuna eða hvað þeir hafa sem er raunverulega á borðinu sínu. Svo það er bara betra notandi upplifa yfirleitt. En hæðir af aðgerð client-megin löggilding, ef þú gerir það án þess að einnig gera framreiðslumaður-hlið löggilding er að mest einhver kemur út úr CS50 veit að þú getur bara senda gögn sem þú vilt að netþjóni allir tala af lifnaðarhættir. Frankly, í flestum hvaða vafra, getur þú smelltu kring í stillingum og bara slökkva á JavaScript, sem myndi, því, gera hvers konar löggilding. 

En einnig gæti muna að jafnvel ég gerði nokkrar Bogagöng hluti í flokki með Telnet og í raun að þykjast vera vafra með því að senda fá beiðnir til miðlara. Og það er vissulega ekki nota hvaða JavaScript. Það er bara ég að slá skipanir á lyklaborðinu. Svo í raun, allir forritari innan nóg þægindi með vefnum og HTTP gæti sent hvað gögn sem hann eða hún vill til a framreiðslumaður án löggilding. Og ef netþjóninn er ekki líka stöðva, gerðu þeir gefa mér nafn, er þetta í raun gilt netfang, gerði þeir velja dorm, þú might endir upp innsetning svikinn eða bara eyða gögnum inn í gagnagrunninn þinn, sem líklega er ekki að fara að vera gott ef þú varst miðað við það var þar. 

Þannig að þetta er pirrandi veruleika. En almennt, client-megin löggilding er mikill. En það þýðir tvöfalt eins mikið vinna. Þó að það eru í reynd ýmsir bókasöfn, JavaScript bókasöfnum fyrir dæmi, sem gerir þetta mikið, miklu minna af höfuðverk. Og þú getur endurnýtt sumir af the merkjamál framreiðslumaður-hlið, client-megin. En átta sig að það er yfirleitt frekari vinnu. Já. 

Áhorfendur: Svo ef við bara sagði ótryggari - 

DAVID J. Malan: [Hlær] Ugh. Þeir eru alltaf erfiðara sjálfur að dæma. 

ROB BOWDEN: sem myndi hefur verið tekið. 

DAVID J. Malan: Hvað? 

ROB BOWDEN: Ég bjó til þetta vandamál. Sem hefði verið samþykkt. 

DAVID J. Malan: Já. 

Áhorfendur: Cool. 

ROB BOWDEN: En við vildum ekki samþykkja í fyrsta sem - Jæja, það sem við vorum að leita að er eitthvað eins og þú þarft ekki að samskipti við þjóninn. Við vildum ekki taka bara hraðar. 

Áhorfendur: Hvað um ekki endurhlaða síðuna? 

ROB BOWDEN: Já. Sem var samþykkt svar. 

DAVID J. Malan: Nokkuð þar við fannst það var líklegra en ekki líklegt sem þú vissir hvað þú værir segja, sem er sterkur lína að draga stundum. Using a tengda listanum í staðinn af fjölda til að viðhalda raðað lista yfir heiltölur. Svo að kosti við vitnað oft með stiklum listum sem áhugasamir heild sinni kynning var þú færð kraft. Þeir geta vaxið. Þeir geta skreppa. Svo þú þarft ekki að hoppa í gegnum hindranir að í raun búa við meira minni með fjölda. Eða þú þarft ekki að bara segja, því miður, notandi. The array er fyllt. Svo dynamic vöxt á listanum. A hæðir þó tengdir listum? 

Áhorfendur: Það er línulegt. Leita á tengda listanum er línuleg í staðinn fyrir það sem þú skráir þig inn 

DAVID J. Malan: Einmitt. Leita á tengda listanum er línuleg, jafnvel ef það er raðað, vegna þess að þú getur aðeins fylgst með þessum mola brauð, þessir ábendingum, frá upphafi listanum til enda. Þú getur ekki skiptimynt handahófi aðgangur og, svona, Tvíundarleit, jafnvel ef það er raðað, að þú gætir gera með fylki. Og það er einnig annar kostnaður. Já. 

Áhorfendur: Minni óhagkvæmt? 

DAVID J. Malan: Já. Jæja, ég myndi ekki endilega segja óhagkvæmt. En það er kostnaður þú fleiri minni, vegna þess að þú þarft 32 bita fyrir hvert hnút fyrir frekari músina, að minnsta kosti fyrir stakar tengda listanum. Nú, ef þú ert aðeins að geyma heiltölur og þú ert að bæta á músina, það er í raun eins konar non-léttvæg. Það er tvöföldun the magn af minni. En í raun og veru, ef þú ætlar að geyma á tengdur listi yfir structs sem kunna að hafa 8 bytes, 16 bytes, jafnvel meira en það, kannski er það minna af jaðarkostnaður. En það er kostnaður engu að síður. Svo annað hvort þeirra myndi hef verið fínn eins og downsides. 

18. Using PHP í stað C til að skrifa stjórn-lína forrit. Svo hér, það er oft hraðari til að nota A tungumál eins og PHP eða Ruby eða Python. Þú bara fljótt að opna upp texta ritil. Þú átt marga fleiri aðgerðir í boði fyrir þig. PHP hefur eldhúsvaskinn af störfum, en í C, þú hafa mjög, mjög lítið. Í staðreynd, krakkar sem vita erfiðu leiðina að þú þarft ekki kjötkássa matskeið. Þú þarft ekki hafa tengt listum. Ef þú vilt þá þarftu að innleiða þá sjálfur. 

Svo einn kosti af PHP eða bara einhverju túlkað tungumál er rapidity sem hægt að skrifa kóðann. En ókostur, sáum við þetta þegar ég fljótt þeyttum upp misspeller framkvæmd í fyrirlestri með PHP, er að nota túlkað tungumál er yfirleitt hægari. Og við sáum að sannanlega með að aukning í tíma úr 0,3 sekúndum í 3 sekúndur, vegna túlkunar sem raunverulega gerist. 

Önnur kosti var að þú þarf ekki að safna saman. Svo flýtir það einnig upp þróun tilviljun, því að þú hefur ekki tvö skref til að keyra forrit. Þú ert bara einn. Og svo er það nokkuð áhrifaríkar og vel. Using a SQL gagnagrunn í stað þess að CSV skrá til að geyma gögn. Svo SQL gagnagrunnur er notað til pset7. CSV skrár sem þú did ekki nota mikið. En þú notaðir það óbeint í pset7 sem vel með því að tala við Yahoo Finance. 

En CSV er bara eins og Excel skrá en frábær einfalt, þar sem dálkarnir eru bara demarked með kommum inni sem að öðru leyti textaskrá. Og nota SQL gagnagrunn er aðeins meira sannfærandi. Það er kosti, vegna þess að þú færð hlutina eins að velja og setja inn og eyða. Og þú færð væntanlega vísitölur sem MySQL og aðra gagnagrunna, eins og Oracle, byggja fyrir þig í minni, sem þýðir velja þinn er sennilega ekki að fara að vera línuleg toppur til botn. Það er í raun að fara að vera eitthvað eins tvöfaldur leit eða eitthvað svipuð í anda. Svo þeir eru yfirleitt hraðar. 

En ókostur er að það er bara meiri vinna. Það er meira átak. Þú verður að skilja gagnagrunna. Þú þarft að setja það upp. Þú þarft miðlara til að keyra þessi gagnagrunnur á. Þú þarft að skilja hvernig á að stilla það. Svo að þetta eru bara þessir konar málamiðlanir. En a CSV skrá, þú getur búa hana með gedit. Og þú ert góður til fara. Það er engin flókið lengra. 

Using a trie í stað kjötkássa borð með sérstakri chaining að geyma orðabók yfir orð minnir af pset5. Svo reynir kosti, í orði að minnsta kosti, er það? Föstu tíma, að minnsta kosti ef þú ert hass á hverjum einstaklingsins bréf í orði, eins og þú gæti hafa fyrir pset5. Það gæti verið fimm kjötkássa, sex kjötkássa ef það er fimm eða sex bréf í orðinu. Og það er nokkuð gott. Og ef það er efri bundið um hvernig langur orð þín gæti verið, það er örugglega aðfellu föstu tíma. 

En a kjötkássa borð með aðskildum chaining, vandamálið þar með að konar gögn uppbygging er að árangur reiknirit þinn venjulega veltur á ýmislegt þegar í gögn uppbygging. Og það er örugglega raunin með keðjur, þar sem meira efni sem þú setur í kjötkássa töflunni lengur sem þeir keðjur fara, sem þýðir í versta tilfelli, að hlutur sem þú gætir verið að leita að er alla leið í enda annars af þeim keðjur, sem í raun devolves í eitthvað línuleg. 

Nú, í raun, gæti það alveg vera raunin að kjötkássa borð við keðjur er hraðari en samsvarandi trie framkvæmd. En það er af ýmsum ástæðum, meðal sem eru reynir að nota allt fullt af minni sem getur, í raun, hægur hlutur niður, vegna þess að þú færð ekki gott kostir eitthvað sem kallast flýtiminni, þar sem hlutirnir sem eru þétt saman í minni sem hægt er að nálgast oft hraðar. Og stundum er hægt að koma upp með mjög gott kjötkássa virka. Jafnvel ef þú verða að sóa smá minni, þú gætir reyndar að geta finna hluti hratt og ekki eins slæmt eins og línulega. 

Svo í stuttu máli, það var ekki endilega með einhverjum af þessum einum eða jafnvel tveimur ákveðin atriði sem við vorum að leita að. Raun nokkuð sannfærandi sem efri og hæðir almennt caught auga okkar. 

ROB BOWDEN: Svo fyrir tímann, við gerðum ekki taka á eigin spýtur "hraðar." Þú þurfti að segja eitthvað um það. Jafnvel ef þú sagt fræðilega hraðar, við vissum að þú konar skilið að það er 0 af 1. Og kjötkássa borð, í orði, er ekki 0 af 1. Minnast neitt um afturkreistingur almennt got þú stig. En "hraðar," mest af þeim lausnum á stór borð sem voru voru reynir hlutlægt hægari en lausnir sem voru kjötkássa matskeið. Svo hraðar í sjálfu sér er í raun ekki satt. 

DAVID J. Malan: Dom de Dom Dom. Ég er sennilega sá eini sem gerir sér grein fyrir það er hvernig það er ætlast til vera áberandi, ekki satt? 

ROB BOWDEN: Ég hafði reyndar ekki hugmynd. 

DAVID J. Malan: Það gerði vit í höfðinu á mér. 

ROB BOWDEN: ég er að gera þetta einn. OK. Svo er þetta það eina sem þú þurftir að draga Teikningin svipað og þú might hafa séð á undanförnum prófum. Svo skulum líta bara á þetta. Svo frá HTML hnút, höfum við tvær börn, höfuð og líkama. Svo við útibú - höfuð og líkama. Höfuðið hefur titil tag. Þannig að við höfum titil. 

Nú er einn hlutur a einhver fjöldi af fólki gleymdi er að þessi texti hnútar eru þætti innan þessa tré. Svo hér við skyldir til að draga þá sem ovals til að aðgreina það frá þessum tegundir tengipunkta. En tilkynning einnig hér höfum við toppinn, miðju og botn mun endir upp tilvera texti hnúður. Svo gleyma þeim var nokkuð af algeng mistök. 

Líkaminn hefur þrjú börn - þessir þrír divs. Svo div, div, div og þá texta hnút börn þeirra divs. Það er ansi mikið það fyrir að spurningum. 

DAVID J. Malan: Og það er athyglisvert, jafnvel þó við búa ekki á þessu upplýsingar í þeim tíma sem við eyða á JavaScript, að þess er, í staðreynd, sama tæknilega. Þannig að ef höfuðið kemur fyrir líkama í HTML, þá ætti það að birtast til vinstri á líkamanum í raun DOM. Að hans er, almennt, bara FYI, eitthvað sem kallast skjal röð, þar það skiptir máli. Og ef þú varst að innleiða flokka, forrit sem les HTML í byggingu upp tré í minni, að vera heiðarlegur, það er innsæi líklega það sem þú gera samt - toppur til botn, vinstri til hægri. 

ROB BOWDEN: Spurningar um það? Ætti ég að gera næsta einn? 

DAVID J. Malan: Jú. 

ROB BOWDEN: OK. Þannig að þetta er biðminni umframmagn árás spurning. The aðalæð hlutur að viðurkenna hér er, Jæja, hvernig gæti mótstöðumaður bragð þetta forrit í framkvæmd handahófskennt kóðann? Svo argv1, fyrsta stjórn lína rök til þessarar áætlunar, sem getur verið geðþótta lengi. En hér erum við að nota memcpy að afrita argv1, sem hér er bar. Við erum liggur það sem rök. Og svo það tekur á nafn bar. 

Þannig að við erum memcpying bar inn í þennan biðminni c. Hversu margir bæti erum við að afrita? Jæja þó margir bæti barnum gerist að vera með, lengd þeirrar röksemdar. En c er aðeins 12 bæti á breidd. Þannig að ef við slá a stjórn lína rifrildi sem er lengri en 12 bæti, erum við að fara að flæða yfir þetta Einkum Buffer. Nú, hvernig gæti mótstöðumaður bragð forrita inn framkvæmd handahófi kóða? 

Svo muna að hér Helsta er að kalla foo. Og svo þá helstu símtöl foo. Skulum draga þetta. Þannig að við höfum stafla okkar. Og helstu hefur stafla ramma neðst. Á einhverjum tímapunkti, foo helstu símtöl. Jæja, strax, foo helstu símtöl. Og svo foo fær eigin stakkur ramma þess. 

Nú, á einhverjum tímapunkti, foo er að fara að fara aftur. Og fór Sigur skilar, þurfum við að vita á hvaða línu af kóða inni helstu vér voru til þess að vita hvar við ættum að halda áfram í helstu. Við getum kallað foo frá heild fullt af mismunandi stöðum. Hvernig vitum við hvar á að snúa aftur? Jæja, við þurfum að geyma að einhvers staðar. 

Svo einhvers staðar ekki satt um hér geymum við þar sem við ættum að fara aftur til einu sinni Sigur skilar. Og þetta er aftur heimilisfang. Svo hvernig mótstöðumaður gæti nýta þetta er sú staðreynd að þetta biðminni c er geymd, við skulum segja, hér er c. Þannig að við höfum fengið 12 bytes fyrir c. Þetta er c. Og þetta er stafla hringur Foo er. Svo ef illgjarn notandi slær meira bæti en 12 eða þeir slá inn skipunina lína rifrildi sem er lengri en 12 stafir, þá erum við að fara að flæða þessa biðminni. 

Við getum haldið áfram. Og á einhverjum tímapunkti, förum við langt nóg að við byrjum að skrifa yfir þessa aftur heimilisfang. Svo þegar við skrifa yfir aftur heimilisfang, þetta þýðir að þegar foo skilar, erum við aftur að hvert sem illgjarn notandi er að segja það að eftir hvað virði það inn, með hvaða stafir sem notandinn slegið inn. Og svo ef illgjarn notandi er að vera sérstaklega snjall, getur hann hafa þetta aftur til einhvers staðar í printDef virka eða einhvers staðar í malloc virka, bara hvar handahófskennt. 

En jafnvel meira snjall er það ef hann hefur notandinn aftur að hérna. Og þá byrja framkvæmd þessar sem línur af kóða. Svo á þeim tímapunkti, sem notandinn getur slegið inn hvað sem hann vill í þessum heimshluta. Og hann hefur fulla stjórn yfir áætlun þína. Spurningar um það? Svo er næsta spurning lokið reimplementation af foo á þann hátt að það er ekki lengur viðkvæm. 

Svo there 'a par af leiðir þú gætir hafa gert þetta. Við höfum enn c aðeins vera af lengd 12. Þú gætir hafa breytt þessu sem hluti af lausn þína. Við bættum einnig Athugaðu að ganga viss barnum var ekki null. Þó að þú hafir ekki þörf að fyrir fullt kredit. Þannig að við erum að athuga fyrst band lengd bar. Ef það er stærra en 12, þá gera í raun ekki að gera afrit. Svo er það ein leið til að ákveða það. 

Önnur leið til að ákveða það er í stað þess að hafa c aðeins vera af lengd 12, hafa það vera af lengd strlen (bar). Önnur leið til að ákveða það er að í raun bara aftur. Þannig að ef þú hefðir bara fengið losa af öllum þetta, ef þú hefðir bara eytt öllu línur af kóða, myndir þú hafa fengið fullur trúnaður, þar sem þetta fall er í raun ekki náð neitt. Það er að afrita stjórn lína rök í einhvers array í sveitarfélaga stafla ramma þess. Og þá málið er aftur. Og hvað sem það leikinn er farinn. Svo aftur var einnig nægjanleg vegur af getting fullur trúnaður. 

DAVID J. Malan: Ekki alveg anda spurningin en ásættanlegt á að sérstakur engu að síður. 

ROB BOWDEN: Spurningar um eitthvað af því? The einn hlutur sem þú að minnsta kosti þarf að hafa söfnun kóðann. Svo jafnvel þótt tæknilega þú ert ekki viðkvæm ef númerið þitt er ekki safna saman, höfum vér ekki samþykkja það. Engin spurning? OK. 

DAVID J. Malan: Viltu að segja þennan titil? 

ROB BOWDEN: Nei 

DAVID J. Malan: Svo í þessu einn, þetta var annaðhvort góðar fréttir eða slæmar fréttir. Þetta er bókstaflega sama vandamál sem í fyrsta prófið. Og það er nánast sama vandamál sem pset1. En það var vísvitandi einfaldað til að vera einfaldari pýramída, eitt sem getur verið leyst með örlítið einfaldari endurtekning. Og í raun, það sem við vorum að fá á hér var ekki svo mikið rökfræði, því sennilega með þessum tímapunkti, þú ert öruggari en þú varst í viku einn með fyrir lykkjur eða hvers vegna lykkjur, en virkilega að stríða í sundur að þú ert a lítill ánægð með hugmynd að PHP er ekki bara um hvað forritun. Það geta raunverulega vera notaður eins og tungumál að skrifa á skipanalínu forrit. 

Og reyndar, það er það sem við vorum að reyna að vekja athygli þína. Þetta er a stjórn lína PHP forrit. Svo C kóða hér, en rétt í C, ekki leiðrétta fyrir PHP. En númerið er í raun sama. Ef þú bera saman lausnir fyrir Quiz 0 á móti Quiz 1, munt þú finna að það er nánast eins, nema fyrir sumir dollara merki og fyrir Án þess að gögn tegund. Einkum ef við lítum hér, þú munt sjá að við iterate, í þessu tilfelli, frá 1 upp í gegnum 7. 

Við hefðum getað gert það 0 vísitölunni. En stundum held ég að það er bara andlega auðveldara að hugsa um hluti 1-7. Ef þú vilt eina blokk, þá tvo blokkir, þá var þremur, þá punktur, punktur, punktur sjö. Við höfum J verið frumstilla að 1 og þá telja á allt að i. Og allt hérna er öðru leyti eins. En verður í huga eru a par af hlutur. Við gefa þér þessar tvær línur, þetta fyrsta einn, goofily nefndur sem klabbið fyrir beittum Bang. Og það bara skilgreinir leið, möppu, þar sem forrit getur verið komist að því að þú vilt nota að túlka þessa skrá. 

Og þá línu eftir það, af Auðvitað þýðir sláðu PHP háttur. Og línan á mjög botn þýðir hætta PHP háttur. Og þetta virkar, almennt, með túlka tungumál. Það er eins konar pirrandi ef þú skrifa program í skrá sem kallast foo.php. Og þá notendur hafa að bara muna, OK, til að keyra þetta forrit, ég að slá "PHP pláss foo.php." Góður pirrandi ef ekkert annað. Og það kemur einnig fram að kerfið þitt er skrifað í PHP, sem er ekki allur að lýsa upp fyrir notandann. 

Svo er hægt að fjarlægja. PHP öllu muna úr fyrirlestri. Og þú getur raunverulega gert. / Foo ef þú hefur chmodded það með því að gera það executable. Svo chmod A + x foo hefði gert það. Og ef þú bætir einnig klabbið hér. En í raun, var vandamálið að komast á prenta út eitthvað eins og this. No HTML, engin C-kóða vissulega, bara sumir PHP. Svo Milo þá aftur í vanda 25.. Og í 25, þú varst gefið eftirfarandi beinagrind númer, sem var laglegur einfaldur vefur blaðsíða. Og safaríkur hluti HTML-vitur var niður hér, þar sem við höfum inni í líkamanum form sem hefur einkvæmt kenni af aðföngum inni sem var tveggja inntak, einn með hugmynd um nafn, einn með hugmynd um hnappinn. 

Sú fyrsta var gerð texta, sem Annað af gerðinni leggja. Og svo við gáfum þér, reyndar, fleiri innihaldsefni en þú þörf, bara svo þú krakkar höfðu valkosti sem til að leysa þetta vandamál. Þú ert ekki aðeins þurft öll þessi auðkenni. En það er hægt að leysa það á mismunandi vegu. Og upp á toppinn, eftir því að markmiðið var að kveikja glugga eins og þetta - Halló, Milo! - að skjóta upp kollinum í vafranum með frábær einfalt, ef ekki ljótur, vakandi virka. Og svo, að lokum, þetta snýst um eðli að einhvern veginn að hlusta á greinargerðir formi client-megin , Ekki framreiðslumaður-hlið, einhvern veginn bregðast við þeirri uppgjöf grabbing gildi sem notandinn slegið í að nafninu sviði, og þá sýna það í meginmál viðvörun. 

Svo ein leið sem þú getur gert þetta er með jQuery, sem lítur svolítið setningafræðilega perplexing í fyrstu. Þú getur gert þetta með hreinu DOM kóða - document.getelement eftir ID. En við skulum kíkja á þessa útgáfu. ÉG hafa a par af mikilvæg línur fyrst. Svo einn, höfum við þessa línu, sem er eins og hvaða þú might hafa séð í, ég trúi, form2.html frá bekknum í viku 9. Og þetta er bara að segja, framkvæma Eftirfarandi númer þegar skjalið er tilbúið. Þetta vera mikilvægt einungis vegna HTML síður eru lesnar toppur til botn, vinstri til hægri. 

Og þess vegna, ef þú reynir að gera eitthvað í númerið upp hér að einhverju DOM þáttur, sumir HTML tag, sem er niður hér, þú ert að gera það of fljótt, vegna þess að þetta hefur ekki einu sinni verið lesin inn í minni. Svo með því að segja þetta document.ready lína, við erum að segja, hér er sumir númer, vafrinn. En ekki framkvæma þetta fyrr en í heild skjalið er tilbúið, það er DOM tré til í minni. Þetta er svolítið meira einfalt, ef setningafræðilega A svolítið öðruvísi, þar sem ég er að segja, grípa HTML þáttur sem einstakt kennimerki er inntak. Það er það sem kjötkássa tag táknar, einstaka ID. Og þá er ég að hringja. Senda. 

Svo. Leggja hér er fall, annars þekktur sem aðferð, sem er inni á hlut á vinstri hönd hlið þar sem ég vissi ekki hápunktur. Svo ef þú heldur af aðföngum sem andlag í minni - og raunar er það. Það er hnút í tré - . Leggja leið þegar þetta eyðublað með þetta auðkenni er lögð fram, framkvæma Eftirfarandi númer. Mér er alveg sama hvað nafnið á virka er ég að framkvæma. Svo hér er ég að nota, eins og áður, hvað er kallað lambda virka eða nafnlaus virka. Það er alls ekki intellectually áhugavert annað en það hefur ekkert nafn, sem er fínt ef þú ert aðeins alltaf að fara að kalla það einu sinni. Og þarna inni ég höndla í raun skil á forminu. Ég lýsi fyrst breytu kallað gildi. Og þá er hvaða áhrif þetta hápunktur hluti hérna núna? Hvað þýðir að gera á mikil fyrir mig? 

Áhorfendur: Það fær gildi sem notandi ekki í HTML neðan. Það fær að ID og þá finnur verðmæti þess. 

DAVID J. Malan: Einmitt. Það grípur hnút, sem einstakt heiti er nafn. Það fær gildi þar sem er væntanlega það sem notandinn slegið hann eða hún sjálf. Og þá geymir það að í breytu sem heitir gildi. Sem innskot, þú gætir hafa einnig gert þetta aðeins öðruvísi. Algerlega ásættanlegt með því að gera eitthvað lygi var gildi fær document.getElementById. Og þetta er hvers vegna það er lítið leiðinlegur að ekki nota jQuery. "Nafn". Gildi. Svo algerlega ásættanlegt. Mismunandi leiðir til að gera þetta. jQuery bara tilhneigingu til að vera svolítið meira gagnorðar og örugglega fleiri vinsæll meðal forritara. 

Nú, ég er að gera a hluti af a Sanity stöðva, vegna þess að í því vandamáli yfirlýsingu við sögðum skýrt, ef notandi hefur ekki enn slegið hans eða hennar nafn, ekki sýna áminningar. En þú geta stöðva fyrir það, bara með stöðva fyrir the tómur strengur fyrir a vitna-unquote ef það er ekkert í raun þar. En ef það er ekki jafn tilvísun-unquote, Ég vil kalla áminningar. Og áhugaverður hluti hér er að við erum að nota plús rekstraraðila, sem gerir hvað í JavaScript? Concatenate. Svo er það eins og phps punktur símafyrirtækinu. Sama hugmynd, örlítið mismunandi setningafræði. Og ég ætla bara að búa til band sem þú sást á skjánum skot - Halló, svo og svo. 

Og þá er síðasta smáatriðum þetta. Hví ég return false inni þessarar nafnlaus virka? 

Áhorfendur: Það er engin gildi. Þú setur það í formi. Það segir bara, ef gildið er ekki jafn autt, þá gera það. Það var autt í þeirri uppgjöf. 

DAVID J. Malan: OK. Varlega þó. Það er enginn annar hér. Og það aftur ósatt er utan af ef aðstæður. Þannig að þetta hápunktur línu, return false, keyrir sama hvað þegar mynd er lögð. Hvað þýðir aftur rangar inni í þessu atburður dýraþjálfari, eins og það er kallað, Atburðurinn sem um ræðir vera uppgjöf? 

Áhorfendur: Vegna þess að það gerist aðeins einu sinni. 

DAVID J. Malan: gerist aðeins einu sinni. Ekki alveg. Já? 

Áhorfendur: Það kemur í veg formið frá leggja fyrir sjálfgefna hegðun, sem myndi gera síðu Reload. 

DAVID J. Malan: Einmitt. Þannig að ég ætla villu hugtakið leggja hér, vegna þess að ég er að segja, formið er var lögð. En eins og þú stinga upp á, það er í raun ekki verið lögð í the sannur HTTP hátt. Þegar þú smellir á Senda, vegna okkar onSubmit dýraþjálfari, erum við hlerun að útfylling svo að segja. Við erum þá að gera hlutur okkar með JavaScript kóða. En ég er vísvitandi aftur rangar, því það sem ég vil ekki að gerast á sekúndubroti síðar er fyrir allt formi sér að vera lögð á netið framreiðslumaður með helstu gildi pör með því að breyta slóðin að vera eitthvað eins og Q = ketti eða hvað sem við gerðum, til dæmis, í tímum. Ég vil ekki að gerast, vegna þess að það er engin miðlara hlusta fyrir þessu útfylling. Það er eingöngu gert í JavaScript kóða. Og þess vegna er ég ekki einu sinni hafa aðgerð eigindi á mynd mína, því ég ekki ætla að þetta geti alltaf að fara til the framreiðslumaður. 

Svo það er verið lögð. En við erum að stöðvun þessi mynd uppgjöf og koma í veg fyrir sjálfgefið hegðun, sem er að í raun og veru fara alla leið til the framreiðslumaður. 

Áhorfendur: Svo halda það client-megin. 

DAVID J. Malan: Gæsla það client-megin. Nákvæmlega rétt. Næst upp var minn ó MySQL. 

ROB BOWDEN: OK. Þannig að þetta fyrsta spurningin var almennt gróft fyrir fólk. Þótt síðar sjálfur fór betur. Þannig að þú þurftir að velja rétt gögn gerðir fyrir báðum þessum dálkum. Og báðir þessir hafa sumir atriði um þá sem gera val erfitt. Svo Int var ekki gild slá fyrir fjölda. Ástæðan vera 12 stafa reikningur númer, int er ekki nógu stór til að geyma samtals tölustafir. Svo gilt val hefði verið stór int ef þú skyldir vita það. Annar kostur gæti verið char sviði lengd 12. Svo annað hvort þeirra hefði unnið. Int væri ekki. 

Nú, jafnvægi, hugsa til baka til pset7. Þannig að við sem nota sérstaklega aukastaf til geyma verðmæti hlutabréfa eða - 

DAVID J. Malan: Cash. 

ROB BOWDEN: Cash. Við notuðum við aukastaf til að geyma magn af reiðufé sem notandinn hefur nú. Svo ástæðan að við að gera sem er því, muna, fljóta. Það er fljótandi lið í nákvæmni. Það getur ekki nákvæmlega geyma reiðufé gildi eins og við viljum hér. Svo er hægt að nákvæmlega geyma aukastaf eitthvað til að segja, með tveimur aukastöfum. Þessi 'hvers vegna jafnvægi, viljum við það að vera aukastaf og ekki fljóta. 

DAVID J. Malan: Og einnig, líka, þó það gæti hafa verið snjall í öðrum aðstæður til að hugsa, kannski þetta er tækifæri fyrir int. Ég ætla bara að halda utan um hlutir í smáaurarnir. Þar sem við sýndi skýrt sjálfgefið gildi að vera 100,00, að þýðir það gæti bara verið int. Og annar lipurðar of með fjölda var að það var ekki ætlað að vera bragð spurning. En muna að int í MySQL, eins og í C, að minnsta kosti í því tæki, er 32-bita. Og jafnvel þótt við býstu ekki við vita nákvæmlega hversu margir tölustafir sem þýðir, man að mesti fjöldi þú getur táknað hugsanlega með 32-bita tala er u.þ.b. hvað? 

Hvað númer eigum við að segja alltaf? 2 til 32, sem er það u.þ.b.? Þú þarft ekki að vita nákvæmlega. En u.þ.b. er gagnlegt í lífinu. Það er um það bil 4 milljörðum. Þannig að við höfum sagt að nokkrum sinnum. Ég veit að ég hef sagt að nokkrum sinnum. Og það er um það bil 4 milljörðum. Og það er góð regla þumalfingur að vita. Ef þú ert með 8 bitar, 256 er galdur númer. Ef þú ert með 32 bita, 4 milljarðar gefa eða taka. Þannig að ef þú skrifar bara niður 4 milljarða, þú munt sjá að það er færri tölustafir en 12, sem þýðir að það er greinilega ekki nóg tjáningarkrafturinn að handtaka 12-stafa númer reiknings. 

ROB BOWDEN: OK. Svo hinar fór betur. Svo ætla að bankinn leggur $ 20 mánaðarlega viðhald gjald á alla reikninga. Með hvaða SQL fyrirspurn gat bankinn draga $ 20 frá hverjum telja, jafnvel þótt það afleiðing í sumum neikvæðum? Svo í grundvallaratriðum, það eru fjórir Helstu tegundir fyrirspurna - setja, velja, uppfæra og eyða. Svo hvað við höldum að við erum fara að nota hér? Uppfæra. 

Þannig að við skulum taka a útlit. Svo hér erum við að uppfæra. Hvaða borð erum við að uppfæra reikninga? Svo uppfæra reikninga. Og þá segir setningafræði, hvað í reikningum erum við að uppfæra? Jæja, erum við að setja jafnvægi sem svarar til þess Núvirði jafnvægi mínus 20. Þannig að þetta mun uppfæra allar raðir reikninga, draga $ 20 úr jafnvægi. 

DAVID J. Malan: Algeng mistök hér, jafnvel þótt við fyrirgaf stundum það, var að í raun hafa PHP kóðann hér hringja í fyrirspurn virka eða setja tilvitnanir í kringum allt sem þarf ekki að vera þar. 

ROB BOWDEN: Mundu að MySQL er sérstakt tungumál frá PHP. Við verður að vera að skrifa MySQL í PHP. Og PHP er síðan að senda það yfir á MySQL þjóninum. En þú þarft ekki PHP til að samskipti við MySQL þjóninum. 

DAVID J. Malan: Einmitt. Svo enginn breytur með dollara merki ætti að vera í þessu sambandi. Það getur bara gert allt í stærðfræði innan gagnagrunninum sig. 

ROB BOWDEN: OK. Þannig að næsta einn. Er þetta næsta einn? Já. Svo með hvaða SQL fyrirspurn gat bankinn sækja reikningsnúmer í sínum ríkustu viðskiptavinum, sem eru með innstæður meiri en 1000? Svo hver af fjórum helstu tegundir erum við að fara að vilja hér? Velja. Svo viljum við að velja. Hvað viljum við að velja? Hvað dálki viljum við velja? Við munum sérstaklega viljum til að velja númer. En ef þú segir stjörnu, við einnig viðurkennt að. 

Svo velja númer úr hvaða töflu? Reikninga. Og þá ástand sem við viljum? Hvar jafnvægi meiri en 1000. Við samþykkt einnig meiri en eða jafnt. Síðasta. Með hvaða SQL fyrirspurn gat bankinn loka, þ.e.a.s. eyða öllum reikning sem hefur jafnvægi af $ 0? Svo hver af fjórum erum við fara til að vilja nota? Eyða. Svo setningafræði fyrir það? Eyða úr hvaða töflu? Reikninga. Og þá ástand sem við viljum eyða - þar jafnvægi er jafn núlli. Svo eyða öllum raðir af reikningum þar sem jafnvægi er núll. Spurningar um eitthvað af þessu? Viltu að biðröð? 

DAVID J. Malan: Biðröð fylgja. Svo í þessu einn, við gáfum þér nokkuð þekki uppbyggingu sem við kannað hluti í bekknum við hlið structs, sem var gögn uppbyggingu sem í anda. Munurinn þó með biðröð er sem við þurftum að einhvern veginn að muna hver var á the andlit af the biðröð, í stórum hluti svo að við gætum gert meira skilvirka notkun minni, að minnsta kosti ef við værum að nota array. 

Vegna muna, ef við höfum fylki, ef, til dæmis, þetta er að framan biðröð, ef ég kem inn í biðröð hér, og þá fær einhver í línu aftan mig, á bak við mig, á bak við mig, og einn maður stíga út af lína, þú gat, eins og við sáum nokkrar af mönnum okkar sjálfboðaliða í bekknum, hafa allir vakt með þessum hætti. En almennt, hafa allir gert eitthvað er ekki best að nota tíma í forriti, því það þýðir þitt reiknirit er í gangi í hvaða asymptotic hlaupandi tíma? Það er línulegt. 

Og mér finnst eins og þessi er góður af heimskur. Ef næsti maður á línu er næstur Sá sem er ætlast til að fara inn í geyma, þeir gera ekki hafa allir til að færa saman. Bara láta þessi manneskja er að reyta burt þegar tíminn kemur, til dæmis. Svo við getum sparað smá tíma þar. Og svo til að gera það þó, sem þýðir að yfirmaður biðröð eða framan biðröð er að fara að smám færa dýpra og dýpra í fylkinu og að lokum gæti reyndar settir ef við erum að nota er array til að geyma fólk í þessari biðröð. Svo þú getur nánast hugsa um array sem hringlaga gögn uppbyggingu í þeim skilningi. 

Svo þú ert einhvern veginn að halda utan um stærð hennar eða raunverulega the endir af það og þá upphaf þess er þar. Þannig að við leggjum til að þú lýsa einn slíkur biðröð, starf það q, bara einn stafur. Þá erum við að leggja til að framan vera frumstilla að núlli og að stærð að frumstilla á núll. 

Svo núna, það er ekkert inni af því biðröð. Og við biðjum þig um að ljúka framkvæmd Velja slembið skinn neðan á svo hátt að fallið bætir n til lok q og þá skilar satt. En ef q er fullt eða neikvæð, sem fall ætti staðinn return false. Og gáfum þér nokkrar forsendur. En þeir eru ekki í raun virkni máli, bara að bool til, vegna þess, tæknilega, bool ekki hendi í C nema þú látir viss hausaskrár. Svo sem var bara viss um að það voru ekki er þetta bragð spurning tegund af hlutur. 

Svo Velja slembið skinn, lagt við í sýninu Lausnir til þess að framkvæma á eftirfarandi hátt. Einn, athuga við fyrst vellíðan, lágmark-hangandi ávextir. Ef biðröð er fullt eða það sem þú ert að reyna að setja inn er minna en núll, sem við sögðum í skilgreining á vandamálinu ætti ekki leyft, vegna þess að við viljum bara ekki neikvæð gildi, þá ættir þú að bara return false strax. Svo sumir tiltölulega auðvelt villuprófun. Ef þó þú vilt bæta við að raunverulegt númer, sem þú þurfti að gera smá hugsa hér. Og þetta er þar sem það er smá pirrandi andlega, vegna þess að þú þarft að reikna út hvernig á að höndla wraparound. 

En sýkill af þeirri hugmynd hér er að á áhugi fyrir okkur er að wraparound oft felur mát stærðfræði og unga fólkið Rekstraraðili, prósent hlið, þar sem þú getur farið úr stærri gildi aftur í núll og síðan einn og tveir og þrjú og svo aftur í kringum núll, einn og tveir og þrír og svo framvegis aftur og aftur. Svo er leiðin sem við leggja til að gera þetta að við viljum að kemba inn í array kallað tölur þar heiltölur okkar liggja. En til að komast þangað, viljum við fyrst að gera Hvað sem stærð biðröð er en þá bæta við að hvað sem framan á listanum er. Og áhrif sem er að setja okkur á rétta stöðu í biðröð og ekki gera ráð fyrir að fyrsti einstaklingurinn í línu er í upphafi, sem hann eða hún algerlega gæti verið ef við voru einnig færast alla. En við erum bara að búa vinnu fyrir okkur ef við tókum sem einkum slóð. 

Svo við getum haldið það tiltölulega einfalt. Við þurfum að muna að við bara bætt við int við biðröð. Og þá erum við aftur bara satt. Á sama tíma í dequeue, spurði við þú að gera eftirfarandi. Framkvæma það á þann hátt að það dequeues, sem er fjarlægir og skilar, int framan á biðröð. Til að fjarlægja int, nægir það að gleyma því. Þú þarft ekki að hunsa hluti þess. Svo það er enn raun þar. Rétt eins og gögn á disknum, við erum bara að hunsa þá staðreynd að það er nú það. Og ef q er tóm, við ættum stað aftur neikvæð 1. Svo finnst þetta handahófskennt. Hvers vegna skila Neikvæð 1 í stað þess að rangar? Já. 

Áhorfendur: Q er sögufrægur jákvæð gildi. Þar sem þú geyma aðeins jákvæð gildi í Q, neikvæð er villa. 

DAVID J. Malan: OK, satt. Svo vegna þess að við erum aðeins að geyma jákvæð gildi eða núll, þá er það í lagi að aftur neikvætt gildi sem Sentinel gildi, sérstakt tákn. En þú ert að endurskrifa sögu þar, því ástæðan að við erum aðeins aftur ekki neikvæð gildi er vegna þess að við viljum að hafa Sentinel gildi. Svo nánar tiltekið, hvers vegna ekki bara return false þegar um villur? Já. 

Áhorfendur: Þú hefur ekki að skila heiltölu. 

DAVID J. Malan: Einmitt. Og þetta er þar sem C fær laglegur şess. Ef þú ert að segja að þú ert að fara að skila int, hefur þú fengið að skila int. Þú getur ekki fá ímynda og byrja aftur A bool eða fljóta eða band eða eitthvað svoleiðis. Nú, á meðan, JavaScript og PHP og sum önnur tungumál getur í raun, hefur þú aftur öðruvísi gerðir af gildum. Og það getur raunverulega vera gagnlegur, þar þú gætir aftur jákvæð ints, núll, neikvæð ints eða rangar eða null jafnvel að signify villa. En við höfum ekki fjölhæfni í C. 

Svo með dequeue, hvað við leggja til að gera er - 

ROB BOWDEN: Hægt return false. Það er bara falskt er kjötkássa skilgreina ósatt á núll. Þannig að ef þú return false, þú ert aftur núll. Og núll er gild hlutur í biðröð okkar, en neikvæð 1 er ekki hvort falskur gerðist að vera neikvæð 1. En þú ættir ekki einu sinni þarf að vita það. 

DAVID J. Malan: Það er hvers vegna ég gerði ekki segja það. 

ROB BOWDEN: En það var ekki satt að þú getur ekki return false. 

DAVID J. Malan: Jú. Svo dequeue, taka við tökum ógilt sem röksemdafærslu sína. Og það er vegna þess að við erum ekki brottför neitt inn Við viljum bara að fjarlægja þáttur á the andlit af the biðröð. Svo hvernig gætum við farið að gera þetta? Jæja, fyrst skulum við gera þetta fljótur geðheilbrigði stöðva. Ef biðröð stærð er 0, þá er engin vinna til að gera. Aftur neikvæð 1. Lokið. Svo er það nokkrar línur af áætlun minni. Svo aðeins fjórum línum enn. 

Svo hér er ég að ákveða að lækka stærð. Og decrementing stærð raun þýðir að ég er að gleyma eitthvað er þar. En ég verð líka að uppfæra þar The andlit af the tölur eru. Svo til að gera það, ég þarf að gera tvennt. Ég þarf fyrst að muna hvað númerið er á the andlit af the biðröð, vegna þess að ég þarf að skila þeim neitt. Svo ég vil ekki að óvart gleyma um það og þá skrifa það. Ég ætla bara að fara að muna í int. 

Og nú vil ég að uppfæra q.front að q.front 1. Þannig að ef þetta væri fyrsta manneskjan í lína, nú, ég vil gera plús 1 til benda á næsta mann í línu. En ég verð að fara með það wraparound. Og ef rúmtak er alþjóðlegt fasti, það er að fara að leyfa mér að ganga úr skugga um eins og ég benda á mjög síðasta manneskja í lína, modulo aðgerð mun koma mig aftur í núll í framan biðröð. Og sem annast wraparound hér. Og þá er ég að halda áfram að koma aftur n. 

Nú, strangt, ég gerði ekki að lýsa n. Ég þurfti ekki að grípa það og geyma það tímabundið, vegna þess að gildi er enn þar. Svo ég gæti bara gert rétt tölur að skila fyrrum yfirmaður í biðröð. En ég fann bara að þetta væri skýrari til raunverulega grípa int, setja það í N, og síðan aftur að fyrir sakir skýrleika, en ekki bráðnauðsynlegar. Psst. Þeir eru allir pronounceable í höfðinu á mér. 

ROB BOWDEN: Svo fyrsta spurningin er tvöfaldur tré vandamál. Svo fyrsta spurningin er, við erum Miðað við þessar tölur. Og við viljum einhvern veginn setja þá inn þessir hnútar með þeim hætti að það er Gildir Tvíundarleit tré. Svo eitt að muna um tvíleitartré er að það er ekki bara að hlutur til vinstri er minna og hlutur til rétt er meiri. Það þarf að vera að allt tré til vinstri er minna, og allt tréð til hægri er meiri. 

Þannig að ef ég setti 34 hér að ofan, og þá Ég setti 20 hér, svo það er í gildi svo langt, því 34. upp hér. 20 er að fara til vinstri. Svo er það minna. En ég get ekki þá sett 59 hér, því jafnvel þó 59 er á hægri af 20, það er samt til vinstri á 34.. Svo með því að þvingun í huga, að Auðveldasta leiðin líklega að leysa þetta Vandamálið er bara að raða þessi númer - svo 20, 34, 36, 52, 59, 106. Og þá setja þær frá vinstri til hægri. 

Svo 20 fer hér. 34 fer hér. 36 fer hér. 52, 59, 106. Og þú líka gæti hafa mynstrağur út með sumir tengja í og ​​átta sig, ó, bíddu, ég hef ekki nóg tölur að fylla þetta í hérna. Þannig að ég þarf að reshift hvað minn leið ATH er að fara til vera. En eftir því að í síðustu þremur, ef þú lesa frá vinstri til hægri, það er í vaxandi röð. 

Svo nú viljum við að lýsa hvað strúktúr er að fara að vera fyrir hnúður í þessu tré. Svo hvað við þurfum í a tvöfaldur tré? Þannig að við höfum verðmæti tegund INT, svo nokkur INT gildi. Ég veit ekki hvað við kallað það er í lausn - int n. Við þurfum bendi á vinstri barnið og bendi á hægri barn. Svo það er að fara að líta svona út. Og það verður í raun að líta áður þegar gerði tvöfalt linked listi efni, svo tilkynning - Ég ætla að hafa til að fletta alla leiðin aftur niður á vanda 11.. 

Svo eftir það lítur út eins og þetta, nema við verður bara að kalla þetta mismunandi nöfn. Við höfum enn heiltölu gildi og tveir ábendingum. Það er bara að í stað þess að meðhöndla Ábendingum og benda á næsta hlutur og fyrri hlutur, við erum að meðhöndla ábendingum til að benda á vinstri barn og rétt barns. OK. Svo er það strúktúr hnút okkar. Og nú, eina hlutverk sem við þurfum að framkvæma fyrir þessu er Traverse, sem við viljum fara yfir tré, prentun út gildum trénu í röð. 

Svo að leita hér, myndum við vilja til að prenta út 20, 34, 36, 52, 59, og 106. Hvernig eigum við að ná því? Svo er það nokkuð svipað. Ef þú sást í síðasta prófið vandamálið að þú vildir að prenta út allt tré með kommum á milli allt, það var reyndar einu sinni auðveldara en það. Svo er hér lausnin. Þetta var verulega auðveldari ef þú gerðir það í undirmöppum. Ég veit ekki hvort einhver reyndi að gera það iteratively. 

En fyrst, höfum við grunntilvikið okkar. Hvað ef rótin er núll? Þá erum við bara að fara að fara aftur. Við viljum ekki að prenta neitt. Annað sem við erum að fara að fara yfir endurkvæmt niður. Prenta alla vinstri hluttré. Svo prenta allt minna en núverandi gildi mitt. Og þá ætla ég að prenta sjálfur. Og þá ætla ég að Kafa niður minn allt rétt subtree, svo allt meiri en gildi mitt. Og þetta er að fara að prenta út allt í röð. Spurningar um hvernig þetta í raun nær það? 

Áhorfendur: Ég er með spurningu á [inaudible]. 

ROB BOWDEN: Svo ein leið til að nálgast allir endurkvæma vandamál er bara að hugsa um það eins og þú ert að hugsa um alla horn tilvikum. Svo íhuga að við viljum prenta þetta allt tréð. Svo allt sem við erum að fara að einblína á er þetta tiltekna hnút - 36.. Endurkvæma símtöl, þykjast við þá bara vinna. Svo hér, þetta endurkvæma hringja til að Traverse, við án þess jafnvel að hugsa um það, bara fara yfir á vinstri þrír, ímynda sér að þegar prentar 20 og 34 fyrir okkur. Og svo þegar við endurkvæmt lokum kalla Traverse á rétt, sem mun rétt prenta 52, 59, og 106 fyrir okkur. 

Svo í ljósi þess að þetta er að prenta 20, 34, og hitt er hægt að prenta 52, 59, 108, allt sem við þurfum til að vera fær um að gera er að prenta okkur sjálf í miðju þess. Svo prenta út allt fyrir okkur. Prenta okkur sjálf, þannig að núverandi hnút Prenta 36, venjulegur printf, og þá prenta allt eftir okkur. 

DAVID J. Malan: Þetta er þar sem endurkvæmni fær virkilega fallegur. Það er þetta ótrúlega áræðni þar þú gerir tiniest hluti af vinnu. Og þá þú láta einhvern annars gera the hvíla. Og að einhver annar er, kaldhæðnislega, þú. Svo fyrir alvarlegum súkkulaðikökum stig, ef þú flettir upp á spurningum - 

ROB BOWDEN: Á spurningunum? 

DAVID J. Malan: Og niður smá til tölurnar, hjartarskinn einhver vita hvar þessar tölur koma frá? 

ROB BOWDEN: Ég hef bókstaflega ekki hugmynd. 

DAVID J. Malan: Þeir virðast um quiz. 

Áhorfendur: Eru þeir sömu tölur? 

DAVID J. Malan: Þær tölur. Smá páska egg. Svo fyrir þá að horfa á á netinu á heimili, ef þú getur sagt okkur með tölvupósti til heads@CS50.net hvað þýðingu Af þessum endurteknar sex tölur eru Allan Quiz 1, munum við fara í sturtu þig með ótrúlega athygli á það sem kemur síðas fyrirlestur og streitu boltanum. Nice, lúmskur. 

ROB Bowden: Allur Síðustu spurningarnar um neitt á spurningakeppni?