Ræðumaður 1: Allt í lagi, þannig að þetta er CS50 Þetta er endir viku fimm. Og muna að síðasta skipti sem við byrjaði að horfa á áhugamaður gögn mannvirki sem byrjaði að leysa vandamál, sem byrjaði að kynna ný vandamál, en lykillinn að þessu var svoleiðis þráðum sem við byrjaði að gera frá hnút að hnút. Þannig að þetta er auðvitað eintengdan lista. Og með því að ein tengd, Ég meina það er bara eitt þráður milli hvert þessara hnúður. Snýr út að þú getur gert áhugamaður hlutir eins og tvöfalt tengd listum þar sem þú ert með ör fara í báðar áttir, sem getur hjálpað með ákveðnum hagkvæmni. En þetta leyst vandann? Hvaða vandamál gerði þetta leysa? Af hverju höfum vér sama á mánudag? Hvers vegna, í orði, gerði við sama á mánudag? Hvað þýðir það að gera? 

Áhorfendur: Við getum virk búa það. 

Ræðumaður 1: Allt í lagi, þannig að við getum breytilega búa það. Vel gert bæði. Svo þú getur virk búa þetta gögn uppbygging, en fylki, muna, þú þarft að vita fyrirfram hversu mikið pláss þú vilt og ef þú þarft aðeins meira pláss, þú ert svona út af heppni. Þú þarft að búa til nýjan array. Þú þarft að færa alla þína gögn frá einum til annars, loksins frjáls gamla array ef þú getur, og síðan haldið áfram. Sem bara finnst mjög dýrt og mjög óhagkvæm, og reyndar getur það verið. En þetta er ekki allt gott. Við að greiða verð, það var einn af the fleiri augljós verði við greiða með því að nota tengdan lista? 

Áhorfendur: Við verðum að nota tvöfaldur pláss fyrir hvern og einn. Ræðumaður 1: Já, þannig að við þurfum að minnsta kosti tvisvar sinnum eins mikið pláss. Í raun, áttaði ég þessi mynd er jafnvel svolítið villandi, því að á CS50 IDE í fullt af nútíma tölvur, bendi eða netfang er ekki í raun fjögur bæti. Það er mjög oft þessir daga átta bytes, sem þýðir botninum ferhyrninga þar í raun og veru eru eins konar tvöfalt stór og það sem ég hef dregið, sem þýðir að þú ert að nota þrisvar sinnum mikið pláss eins og við gætum ella. Nú á sama tíma, við erum enn að tala bæti, ekki satt? Við erum ekki endilega að tala megabæti eða gígabæta, nema þessi gögn mannvirki fá stór. 

Og svo í dag erum við að byrja að fjalla hvernig við gætum kanna gögn skilvirkari ef í Staðreyndin gögn fær stærri. En við skulum reyna að canonicalize starfsemi fyrstu sem þú getur gert á þessum konar gögn uppbygging. Svo eitthvað eins tengdur listi styður almennt Rekstur eins eyða, setja, og leita. Og hvað ég meina með því? Það þýðir bara að yfirleitt, ef fólk er að nota tengdan lista, þeir eða einhver annar hefur innleitt virka eins Eyða, Bæta í, og leita, svo þú getur raunverulega gera eitthvað gagnlegt við gögn uppbygging. Svo skulum taka a fljótur líta hvernig við gætum framkvæma sumir póstnúmer fyrir tengda listanum sem hér segir. 

Svo er þetta bara sumir C kóða, ekki einu sinni heill forrit að ég mjög fljótt þeyttum upp. Það er ekki á netinu í dreifingu númer, vegna þess að það mun í raun ekki að keyra. En eftir að ég hef bara með athugasemd sagði, punktur punktur punktur eitthvað það, punktur punktur punktur, eitthvað þar. Og við skulum líta bara á hvað safaríkur hlutir eru. Svo á línu þremur, muna að þetta er nú við lagt lýsa hnút síðasta tíma, einn af þeim rétthyrnd hlutum. Það hefur int sem við munum kalla N, en við gátum kalla það nokkuð, og þá struct hnút stjarna heitir næst. Og bara til að vera ljóst, að annað lína, á línu sex, hvað er það? Hvað er það að gera fyrir okkur? Vegna þess að það lítur vissulega meira dulinn en venjulega breytum okkar. 

Áhorfendur: Það gerir það að færa yfir eitt. 

Ræðumaður 1: Það gerir það að færa yfir eitt. Og til að vera nákvæmari, það mun geyma heimilisfangið hnútarins sem er ætlað að vera merkingu við hliðina á henni, ekki satt? Svo það er ekki að fara að endilega fara neitt. Það er bara að fara að geyma verðmæti, sem er að fara að vera netfang einhvern annan hnút, og það er hvers vegna við höfum sagt struct hnút stjarna, stjarnan gefur til kynna bendi eða netfang. OK, svo nú ef þú ráð fyrir að við höfum þetta N boði fyrir okkur, og við skulum gera ráð fyrir að einhver annar hefur sett a heild búnt af heiltölur í tengda listanum. Og það tengist listi er benti á eftir einhverjum tímapunkti breytu sem heitir listi sem er samþykkt hér sem viðfang, hvernig get ég farið um línu 14 innleiða leit? Með öðrum orðum, ef ég er að innleiða virka sem tilgangur í lífinu er að taka int og svo á upphaf tengda listanum, sem er bendi á tengda listanum. Eins og fyrsta, sem ég held að Davíð var sjálfboðaliði okkar á mánudaginn, Hann var að benda á allt tengist lista, það er eins og við séum liggur David inn sem rök okkar hér. Hvernig eigum við að fara um að fara yfir þennan lista? Jæja, það kemur í ljós að jafnvel þótt ábendingum eru tiltölulega ný nú að okkur, við getum gert þetta tiltölulega einfaldur. 

Ég ætla að fara á undan og lýsa tímabundið breytu sem samkvæmt venju er bara að fara að vera kölluð músina, eða PTR, en þú gætir kalla það hvað sem þú vilt. Og ég ætla að frumstilla það til the byrjun af listanum. Svo þú getur konar hugsað þetta sem mér kennara um daginn, konar benda á einhvern meðal manna okkar sem sjálfboðaliða. Þannig að ég er tímabundið breytu sem er bara að benda á það sama að okkar tilviljun heitir Sjálfboðaliðinn David var einnig að benda á. Nú bendillinn er á meðan ekki null, vegna muna sem null er einhver sérstakur Sentinel gildi sem demarcates enda listans svo á meðan ég er ekki að benda á að jörð eins og á síðasta sjálfboðaliða okkar var, við skulum fara á undan og gera eftirfarandi. Ef pointer-- og nú vil ég svona að gera það sem við gerðum við nemanda structure-- ef bendillinn punktur næsta equals-- frekar, ef bendillinn punktur N jafngildir er jafn breytilega N, er rök sem hefur verið samþykkt í, þá vil ég að fara á undan og segja aftur satt. Ég hef fundið fjölda N inni af einn af hnúður tengda listanum mínum. En punktur ekki lengur virkar í þessu samhengi, vegna músina, PTR, er reyndar bendi, heimilisfang, við getum í raun frábærlega nota lokum stykki af setningafræði þannig bráðabirgða innsæi skilningi og í raun nota ör hér, sem þýðir að fara frá sem heimilisfang til tölunnar þar í. Svo það er mjög svipað í anda að punktur rekstraraðila, heldur vegna þess að bendillinn er ekki bendi og ekki raunverulegt struct sjálft, við notum bara ör. 

Þannig að ef núverandi hnút, að ég, tímabundið breyta, er að benda á er ekki N, hvað mig langar að gera? Jæja, með sjálfboðaliðum mínum sem við höfðum hér um daginn, ef fyrsti maðurinn minn er ekki sá sem ég vilja, og kannski er annað manna ekki það sem ég vil, og þriðja, ég þurfa að halda að hreyfa. Eins og hvernig get ég stíga í gegnum lista? Þegar við höfðum fylki, þér bara gerði eins og ég auk plús. En í þessu tilfelli, nægir það til að gera músina, fær, músina, næst. Með öðrum orðum er næsta sviði er eins og alla vinstri höndum að mönnum sjálfboðaliðarnir á mánudaginn voru með að benda á einhvern annan hnút. Þeir voru næst nágrannar þeirra. 

Þannig að ef ég vil stíga í gegnum þennan lista, Ég get ekki bara gera I plús plús lengur, Ég hef í staðinn að segja Ég, músina, er að fara að jafna hvað næsta reitur er, næsta reit er, næsta reitur er, Eftirfarandi allar þessar vinstri höndum sem við höfðum á sviðinu bendir sumum síðari gildi. Og ef ég fæ í gegnum að allt endurtekning, og að lokum, ég lenti null ekki hafa fann N enn, ég aftur bara rangt. Svo aftur, allt sem við erum að gera hér, eins og á myndinni í smá stund síðan, er að byrja með því að benda á að upphaf listanum væntanlega. Og þá er ég að athuga er, gildi Ég er að leita að jafn níu? Ef svo er, ég aftur satt og ég er búin. Ef ekki, ég uppfæra hönd mína, AKA músina, benda á milli næsta Arrow, og þá staðsetningu næsti Arrow er, og næsta. Ég er einfaldlega að ganga í gegnum þetta fylki. 

Svo aftur, sem er ekki sama? Eins og það sem er þetta þáttur í? Jæja, muna að við kynntum hugmyndin um stafla, sem er ágrip gögn slá svo miklu leyti sem það er ekki C hlutur, er það ekki CS50 hlutur, það er ágrip hugmynd, þessi hugmynd um stöflun hluti ofan á annan sem hægt er að hrinda í framkvæmd í bunches af mismunandi vegu. Og ein leið við lagt var með fylki, eða með tengda listanum. Og það kemur í ljós að canonically, a stafla styður að minnsta kosti tvær aðgerðir. Og suð orð eru ýta, til ýta eitthvað á mánudaginn, eins og nýtt bakkanum í matsalur, eða pop, sem þýðir að fjarlægja efsta bakki úr stafla í borðstofu sal, og þá kannski sumir aðrar aðgerðir eins og heilbrigður. Svo hvernig getum við skilgreina uppbyggingu sem við erum nú að kalla stafla? 

Jæja, höfum við öll nauðsynlegur setningafræði ráða okkar í C. Ég segi, gefa mér á skilgreiningu á a struct inni í stafla, Ég ætla að segja er fylki, á a allt fullt af tölum og þá stærð. Svo í öðrum orðum, ef ég vil að framkvæma þetta í kóða, láta mig fara og bara svona draga hvað þetta er að segja. Þannig að þetta er að segja, gefa mér uppbyggingu sem fékk fylki, og ég veit ekki hvað getu er, það er víst einhver fasti sem ég hef skilgreind annars staðar, og það er bara fínt. En geri ráð fyrir að það er bara einn, tveir, þrír, fjórir, fimm. Svo er 5 getu. Þessi þáttur inni minn uppbygging verður gestur númer. Og þá er ég þörf einn aðra breytilega virðist kallað stærð sem upphaflega ég ætla að kveða á um er frumstilla á núll. Ef það er ekkert í stafla, stærð er núll, og það er sorp gildi í tölum. Ég hef ekki hugmynd um hvað er þarna bara ennþá. 

Þannig að ef ég vil að ýta eitthvað á mánudaginn, býst ég kalla virka ýta, og Ég segi ýta 50, eins og númer 50, hvar á ég að leggja Ég draga það í þessu fylki? Það er fimm mismunandi mögulegar svör. Hvar vilt þú að ýta á númerið 50? Ef markmiðið hér, aftur, kalla virka ýta, fara í rifrildi 50, hvar á ég að setja það? Fimm possible-- 20% líkur að giska rétt. Já? 

Áhorfendur: Far rétt. 

Ræðumaður 1: Far rétt. Það er nú 25% líkur að giska rétt. Svo það væri í raun að vera í lagi. Samkvæmt venju, ég segi með fjölda, við myndum yfirleitt byrja á vinstri, en við gátum vissulega byrja á hægri. Svo spoiler hér væri ég líklega að fara að draga það á vinstri, rétt eins og í venjulegum array hvar Ég byrja að fara frá vinstri til hægri. En ef þú getur selbiti reiknað, fínn. Það er bara ekki hefðbundin. OK, ég þarf að gera eitt meira breyting þó. Nú þegar ég hef ýtt eitthvað á mánudaginn, hvað er næst? 

Allt í lagi, ég verð að hækka stærð. Svo láta mig fara á undan og bara uppfæra þetta, sem var núll. Og í staðinn, ég ætla að setja í gildi einum. Og nú ætla ég að ýta annað númer á mánudaginn, eins og 51. Jæja, ég verð að gera eitt breyting, sem er allt að stærð tvö. Og þá ætla ég að ýta einn meira númer á mánudaginn eins 61, nú þarf ég að uppfæra stærð eitt tími, og fá gildið 3 og stærð. Og nú ætla ég að hringja pop. Nú skjóta, samkvæmt venju, tekur ekki rök. Með stafla, allt benda á bakkanum samlíking er að þú þarft ekki svigrúm að fara að fá að bakka, getur allt sem þú gera er skjóta hæstur einn frá stafla, bara vegna þess. Það er það sem þessi gögn uppbygging gerir. 

Svo með því að að rökfræði ef ég segja pop, hvað kemur út? Svo 61. Svo hvað raunverulega er tölva að fara að gera í minni? Hvað er númerið mitt að gera? Hvað myndir þú leggja við breytt á skjánum? Hvað ætti að breyta? Sorry? Þannig að við að losna við 61. Svo ég get örugglega gert það. Og ég get að losna við 61. Og þá hvað annað breyting þarf að gerast? Stærð hefur sennilega að fara aftur til tveggja. Og svo er það allt í lagi. En bíddu í eina mínútu, stærð í smá stund síðan var þriggja. Gerum bara fljótur geðheilsu stöðva. Hvernig fengum við að vita að við vildi til að losna við 61? Þar sem við erum að pabbi. Og svo ég hef þetta annað eign stærð. 

Bíddu, ég er hugsa til baka til viku tvö þegar við byrjuðum að tala um fylki, þar sem þetta var staðsetningu núll, þetta var staðsetningu einn, þetta var staðsetningu tvö, þetta er staðsetning þrír, fjórir, það lítur út eins og tengsl milli stærðar og þáttur sem ég vil fjarlægja frá array virðist bara vera það? Stærð mínus einn. Og svo er það hvernig sem menn við vitum 61 kemur fyrst. Hvernig er tölvan að fara að vita? Þegar númerið þitt, þar sem þú sennilega langar að gera stærð mínus einn, Svo þrjár mínus einn er tveir, og það þýðir að við viljum losna við 61. Og þá getum við örugglega að uppfæra stærð þannig að stærð núna fer frá þremur til bara tveir. Og bara til að vera smámunasamur, ég ætla að leggja til að ég er búin, ekki satt? Þú lagt innsæi rétt ég ætti að losna við 61. En hafa ekki ég konar konar fengið losa af 61? Ég hef í raun gleymt að það er í raun og veru. Og hugsa til baka til PSET4, ef þú hefur lesið grein um réttar, PDF sem við höfðum þið lesið, eða þú verður að lesa í þessari viku fyrir PSET4. Muna að þetta er í raun germane að Í heild hugmynd um réttar tölva. Hvað tölva almennt gerir er hún gleymir bara hvar eitthvað er, en það er ekki að fara í og ​​eins reyna að klóra það út eða hunsa þessir bitar með núllum og sjálfur eða einhver önnur handahófi mynstur nema þú sjálfur að gera það vísvitandi. Svo innsæi þitt var lagi, við skulum losna við 61. En í raun og veru, þá höfum við ekki að standa í. Við þurfum bara að gleyma því að það er það með því að breyta stærð okkar. 

Nú er það vandamál með þessa stafla. Ef ég halda að þrýsta hluti á mánudaginn, það er augljóslega að fara að gerast í örfáum augnablikum tíma? Við erum að fara að keyra út af plássi. Og hvað gerum við? Við erum konar ruglaður. Þessi framkvæmd er ekki láta okkur búa array, vegna þess að nota þetta setningafræði, ef þú hugsa til baka til viku tvö, þegar þú hefur lýst stærð fylki, við höfum ekki séð á kerfi enn þar þú getur breytt stærð fylkisins. Og reyndar C er ekki að lögun. Ef þú segir að gefa mér fimm Nths, kalla þá tölur, það er allt sem þú ert að fara að fá það. Svo við gerum nú og með mánudeginum, hafa getu til að tjá lausn þurfum við bara að fínstilla skilgreiningu á mánudaginn okkar að ekki vera einhver harður-dulmáli array, en bara til að geyma ávarp. 

Nú hvers vegna er þetta? Nú höfum við bara að vera ánægð með sú staðreynd að þegar forritið mitt keyrir, Ég væntanlega fara til verður að spyrja manninn, hve mörg númer viltu geyma? Svo hefur inntak að koma frá einhvers staðar. En þegar ég veit að tala, þá ég get bara nota það virka að gefa mér klumpur af minni? Ég get notað malloc. Og ég get sagt hvaða fjölda bytes Ég vil aftur fyrir þessar Nths. Og allt sem ég hef að geyma í tölurnar breyta hér inni þessa strúktúr ætti að vera það? Það sem raunverulega fer í Tölurnar í þessari atburðarás? Já, bendi fyrst bæti þess klumpur af minni, eða nánar tiltekið, heimilisfangið af fyrsta af þeim bæti. Skiptir ekki máli ef það er einn bæti eða milljarð bytes, Ég þarf bara að hugsa um fyrst. Vegna þess að það malloc ábyrgðir og stýrikerfi ábyrgðir mínir er að klumpur af minni I fá, það er að fara að vera samfelldir. Það er ekki að fara að vera eyður. Svo ef ég hef beðið fyrir 50 bytes eða 1.000 bytes, þeir eru allir að fara að vera aftur til baka til baka. Og svo lengi sem ég man hversu stór, hvernig mikið ég bað um, allt sem ég þarf að vita er fyrsta netfang. 

Svo nú höfum við möguleika í kóða. Að vísu, það er að fara að taka okkur meiri tíma til að skrifa þetta upp, við gætum nú endurúthluta að minni með bara að geyma annað netfang þar ef við viljum stærri eða jafnvel minni klumpur af minni. Svo hér til vörumerkis burt. Nú fáum við kraft. Við höfum enn contiguousness ég segja. Vegna malloc mun gefa okkur Samhangandi klumpur af minni. En þetta er að fara til vera a sársauki í háls fyrir okkur, forritari, að í raun kóða upp. Það er bara meiri vinna. Við þurfum kóða ætt við það sem ég var lemja út bara í smá stund síðan. Mjög viðráðanleg, en það bætir flókið. Og svo verktaki tími, forritari tími er enn annar auðlind að við gætum þurft að eyða sumir tími til að fá nýja möguleika. Og svo auðvitað það er biðröð. Við munum ekki fara inn á þetta einn í miklum smáatriðum. En það er mjög svipað í anda. Ég gæti innleiða biðröð, og samsvarandi starfsemi þess, enqueue eða dequeue, eins bæta við eða fjarlægja, það er bara áhugamaður leið til að segja það, enqueue eða dequeue, eins og hér segir. Ég get bara gefa mér strúktúr sem aftur hefur fjölbreytta a tala er, sem aftur er með stærð, en hvers vegna þarf ég nú til að halda utan um framan biðröð? Ég þarf ekki að vita framan á stafla minni. Jæja, ef ég aftur fyrir a queue-- skulum bara erfitt kóða það sem hafa eins og fimm heiltölur í hér hugsanlega. Svo er þetta núll, einn, tveir, þrír, fjórir. Þetta er að fara að vera hringt aftur. Og þetta mun vera kallað stærð. 

Hvers vegna er það ekki nóg að hafa bara stærð? Jæja, við skulum ýta sömu tölur á. Svo ég pushed-- ég enqueued, eða ýtt. Nú ég enqueue 50, og þá 51, og þá 61, og punktur punktur punktur. Svo er það enqueue. Ég enqueued 50, þá 51, þá 61. Og það lítur út eins að stafla svona langt, nema ég þarf að gera eina breytingu. Ég þarf að uppfæra þessa stærð, svo ég fer frá núll til einn eða tvo til þrjá núna. Hvernig get ég dequeue? Hvað gerist með dequeue? Hverjir ættu að koma á þennan lista fyrst ef það er lína á Apple Store? Svo 50. Svo það er góður af trickier þessu sinni. En síðast þegar það var frábær auðvelt að bara gera stærð mínus einn, Ég fá til the endir af array minn raun þar sem tölur eru, fjarlægir það 61. En ég vil ekki að fjarlægja 61. Ég vil taka 50, sem var þar á 5:00 AM til að stilla upp fyrir Ný iPhone eða whatnot. Og svo til að losna við 50, ég getur ekki bara að gera þetta, ekki satt? Ég get strikað út 50. En við sögðum bara að við þurfa ekki að vera svo endaþarms eins að klóra út eða fela gögnin. Við getum bara gleyma hvar það er. 

En ef ég breyti stærð mína núna til að tveir, er þetta nægar upplýsingar að vita hvað er að gerast í biðröð mínum? Eiginlega ekki. Eins stærð minn er tveir, en hvar biðröð byrja, sérstaklega ef ég hef enn þessir sömu tölur í minni. 50, 51, 61. Þannig að ég þarf að muna nú þar sem framan er. Og svo eins og ég lagði upp það munum við hafa bara kallað NTH framan, sem upphaflega gildi ætti að hafa verið hvað? Zero, bara byrjunin á listanum. En nú auk þess að decrementing stærð við hækka bara að framan. Nú er hér annað vandamál. Svo þegar ég að halda áfram. Segjum þetta er fjöldi eins og 121, 124, og þá, dammit, Ég er út af plássi. En bíddu í eina mínútu, ég er ekki. Svo á þessum tímapunkti í sögunni, gera ráð fyrir að stærð er einn, tveir, þrjá, fjóra, þannig gera ráð fyrir að stærð er fjórir, að framan er eitt, svo 51 er að framan. Ég vil setja annað númer hér, en dammit, ég er út af plássi. En ég er í raun ekki, ekki satt? Hvar gæti ég setti nokkrar Umframvirði, eins 171? Já, ég gæti bara svona fara aftur þarna, ekki satt? Og þá kross út 50, eða bara skrifa það með 171. Og ef þú ert að spá í hvers vegna númer okkar fékk svo af handahófi, Þetta eru almennt tekin tölvu kenndar við Harvard eftir CS50. En það var gott hagræðingu, því nú er ég ekki að sóa pláss. Ég er enn að muna hversu stór þessi hlutur er alls. Það er fimm alls. Vegna þess að ég vil ekki að byrja að skrifa yfir 51. Svo nú er ég enn út af plássi, svo sama vandamál og áður. En þú getur séð hvernig nú í kóðanum þínum, þú sennilega að skrifa smá meira flókið að gera það gerast. Og í raun, hvað rekstraraðila í C sennilega leyfir þú gerir dularfullur þetta circularity? Já það Modulo rekstraraðila, sem prósent skilti. Svo hvað er góður af kaldur um biðröð, jafnvel þótt við höldum teikna fylki eins og þessir eins beinar línur, ef þú konar hugsa um þetta sem curving um eins og hring, þá bara innsæi það virkar eins konar andlega Ég hugsa svolítið meira eðlilega. Þú þarft samt að framkvæma að andleg fyrirmynd í kóða. Svo ekki það erfitt, lokum, að hrinda í framkvæmd, en við missa enn size-- frekar, getu til að búa, nema við gerum þetta. 

Við verðum að losna við fylki, við skipta um það með einu músina, og þá einhvers staðar í númerið mitt sem ég hef fengið a kalla það virka í raun að búa til array hringt? Malloc, eða einhver svipuð virka, nákvæmlega. Einhverjar spurningar um stöflum eða biðröðum. Já? Góð spurning. Hvað Modulo myndir þú nota hér. Svo almennt, þegar unga fólkið, myndir þú gera það með stærð á heild gögn uppbygging. Svo eitthvað eins fimm eða getu, ef það er stöðug, er sennilega að ræða. En bara að gera modulo fimm sennilega er ekki nóg, vegna þess að við þurfum að vita gerum við vefja um hér eða hér eða hér. Svo þú ert sennilega líka fara til að vilja fela stærð hlutur, eða framan breyta eins og heilbrigður. Svo það er bara þetta tiltölulega einföld stærðfræði tjáning, en Modulo væri lykillinn efnið. 

Svo stuttmynd ef þú vilt. Hreyfimynd að sumir Fólkinu á annan háskóla setja saman sem við höfum aðlagað fyrir þessari umræðu. Það felur í sér Jack læra á staðreyndir um biðraðir og tölfræði. 

FILM: Einu sinni, það var strákur sem heitir Jack. Þegar það kom að eignast vini, Jack hafði ekki lagni. Svo fór Jack að tala við Vinsælasta strákur hann vissi. Hann fór til Lou og spurði, hvað á ég að gera? Lou sá að vinur hans var mjög nauðir. Jæja, byrjaði hann, bara líta hvernig þú ert klæddur. Ekki þú hefur einhverjar föt með mismunandi útlit? Já, sagði Jack. Ég viss. Komið til mín og Ég skal sýna yður þær. Svo fóru þeir burt til Jack er. Og Jack sýndi Lou kassann þar sem hann hélt alla skyrtur hans, og buxurnar hans og sokkar hans. Lou sagði, ég sé að þú hefur allt fötin í hrúgu. Hví þú ekki að vera einhver aðrir einu sinni í stutta stund? 

Jack sagði, vel, þegar ég fjarlægja föt og sokka, Ég þvo þá og setja þá í burtu í reitinn. Þá kemur næsta morgun, og allt sem ég hoppa. Ég fer að kassanum og fá fötin mín burt the toppur. Lou áttaði fljótt vandamálið með Jack. Hann hélt föt, geisladiska, og bækur í stafla. Þegar hann kom fyrir eitthvað til að lesa eða til að klæðast, hann myndi velja efst bók eða nærföt. Svo þegar hann var búinn, hann myndi setja það strax aftur. Back það myndi fara, ofan á stafla. Ég veit lausnina, sagði triumphant Loud. Þú þarft að læra að byrja að nota biðröð. Lou tók föt Jack og hengdi þær í skápnum. Og þegar hann var að tæma kassi, hann kastaði bara það. 

Þá sagði hann, nú Jack, í lok daginn, setja fötin á vinstri þegar þú setur þá í burtu. Þá á morgun í morgun þegar þú sjá sólskin, fá fötin til hægri, frá enda línunnar. Sérðu ekki? sagði Lou. Það verður svo gaman. Þú munt vera allt einu sinni áður en þú ferð eitthvað tvisvar. Og með allt í biðröð í skápnum hans og hillu, Jack byrjaði að finna alveg viss um sjálfan sig. Allt þökk sé Lou og dásamlegt biðröð hans. Ræðumaður 1: Allt í lagi, það er yndisleg. Svo hvað hefur verið í raun að fara á undir hetta núna? Að við höfum ábendingum, sem við höfum malloc, að við höfum getu til að búa klumpur af minni fyrir okkur virk. Þannig að þetta er mynd sem við glittir bara um daginn. Við vildum ekki raunverulega búa á það, en þetta mynd hefur verið í gangi undir hetta vikum saman. Og svo stendur þetta, bara rétthyrningi sem við höfum dregið, minni tölvunnar. Og kannski tölvunni, eða CS50 ID, hefur gígabæti af minni eða vinnsluminni eða tveggja gígabæta eða fjögur. Það skiptir ekki máli. Stýrikerfið þitt Windows eða Mac OS eða Linux, í raun gerir program að hugsa að það hafi aðgang að heild minni tölvunnar, jafnvel þó að þú gætir verið að keyra mörg forrit í einu. Svo í raun, það er í raun að vinna. En það er góður af tálsýn gefið öll forrit. Svo ef þú hefðir tvo gigs af RAM, þetta er hvernig tölva gæti hugsa um það. 

Nú tilviljun, einn af þessum hlutir, einn af þessum hluta minni, er kallað stafla. Og raunar hvenær svona langt í að skrifa kóðann að þú hefur kallað virka, til dæmis helstu. Muna að hvenær sem ég hef minni teiknað tölvunnar, Ég teikna alltaf svona helmingur af ferhyrnings hér og nennir ekki að tala um hvað er hér að ofan. Vegna þess að þegar helstu heitir, kröfu I að þú færð þennan flís af minni sem fer niður hér. Og ef helstu kallað fall eins skipti, vel skipti fer hér. Og það kemur í ljós, það er þar sem það er að enda. Á eitthvað sem kallast a stafla inni minni tölvunnar. Nú í lok dagsins, þetta er bara fjallar. Það er eins og bæti núll, bæti einn, bæti 2 milljarða. En ef þér finnst um það eins og þetta rétthyrndum hlut, allt sem við erum að gera á hverjum Hvenær sem við köllum virka er layering nýja sneið af minni. Við erum að gefa að virka sneið eigin minni til þess að vinna með. 

Og muna nú að þetta er mikilvægt. Vegna þess að ef við höfum eitthvað eins og skipti og tvær staðbundnar breytur eins A og B og við breytt þessum gildum frá einum og tveimur til tveggja og einn, muna að þegar skipti skilar, það er eins og þetta sneið af minni er bara farið. Í raun og veru, það er samt það forensically. Og eitthvað er enn í raun þar. En eðli, það er eins þó að það er alveg horfin. Og svo helstu veit ekki eitthvað af vinnu sem var gert í því skipti virka, nema það er í raun liðin hjá þeim rök með músina eða með tilvísun. Nú er grundvallaratriði lausn að þessi vandamál með skipti er komið hlutina í því heimilisfang. En það kemur í ljós, of, það er verið að fara á fyrir ofan þann hluta rétthyrningsins allan þennan tíma er enn það er það meira minni upp. Og þegar þú virk úthluta minni, hvort sem það er inni GetString, sem við höfum verið að gera fyrir þig í CS50 bókasafn, eða ef þið kalla malloc og spyrja stýrikerfi fyrir klumpur af minni, það kemur ekki úr stafla. Það kemur frá öðru sæti í minni tölvunnar það er kallað að hrúga. Og það er ekki allir mismunandi. Það er sama RAM. Það er sama minni. Það er bara RAM sem er upp það í stað þess að hérna. 

Og svo hvað þýðir það? Jæja, ef tölvan þín hefur endanlegt magn af minni og stafla er að vaxa upp, svo að tala, og hrúga, samkvæmt þessari ör, er að vaxa niður. Með öðrum orðum, sérhver skipti sem þú hringja malloc, þú ert að fá sneið af minni að ofan, þá kannski litlu minni, þá smá lægri, í hvert skipti sem þú hringja malloc, hrúga, það notkun, er eins konar vaxandi, vaxandi nær og nær til hvers? Stafla. Svo þýðir þetta að virðast eins og góð hugmynd? Ég meina, ef það er ekki mjög skýr hvað annað sem þú getur gert ef þú aðeins hafa endanlegt magn af minni. En þetta er vissulega slæmt. Þessir tveir örvar eru á a hrun námskeið fyrir öðrum. 

Og það kemur í ljós að slæmur strákur, gott fólk sem eru sérstaklega góð með forritun, og reyna að hakk inn í tölvur, getur nýta þessa veruleika. Í raun, við skulum íhuga smá runu. Svo er þetta dæmi sem þú getur lesið um nánar á Wikipedia. Við munum benda þér á að grein ef forvitinn. En það er árás almennt þekktur sem yfirflæði að hefur verið til í eins lengi og menn hafa haft möguleika á að vinna minni tölvunnar, sérstaklega í C Þannig að þetta er mjög handahófskennt program, en við skulum lesa það frá grunni. Main í argc bleikju stjörnu argv. Svo það er forrit sem tekur stjórn lína rifrildi. Og allt main er virðist er kalla fall, kalla það F fyrir einfaldleika. Og það fer í hvað? Argv einn. Svo það fer í F hvað orðið er að notandinn slegið þegar beðið eftir að Nafnið forritsins yfirleitt. Svo mikið eins og Caesar eða Vigenère, sem þú might muna að gera við argv. 

Svo er það F? F tekur í streng sem eina röksemdafærslu sína, AKA bleikju stjörnu, sama hlutur, sem streng. Og það er kallað geðþótta bar í þessu dæmi. Og þá bleikju c 12, bara í skilmálum leikmaður er, hvað er bleikju c krappi 12 að gera fyrir okkur? Hvað er það gert? Úthlutun minni, sérstaklega 12 bytes fyrir 12 stafir. Nákvæmlega. Og þá síðustu línu, hrærið og afrita, hefur þú sennilega ekki séð. Þetta er band afrit virka sem tilgangur í lífinu er að afrita annað rifrildi sínu í fyrstu röksemd þess, en aðeins upp að ákveðinn fjölda bæti. Svo þriðja rök segir, hversu margir bæti ættir þú afrita? Lengd bar, hvað notandinn slegið inn. Og innihald bar, þessi band, eru afrita í minni benti á í C 

Svo virðist svona heimskur, og það er. Það er háttuð dæmi, en það er dæmigert af flokki vektor árás, leið að ráðast forrit. Allt er fínt og gott ef notandinn gerðir í orði sem er 11 stafir eða færri, auk sviga núll. Hvað ef notandinn slær í meira en 11 eða 12 eða 20 eða 50 stafir? Hvað er þetta forrit að gera? Hugsanlega seg kenna. Það er að fara að blindni afrita allt í bar upp að lengd þess, sem er bókstaflega allt í bar, í heimilisfang benti á C. En C hefur aðeins preemptively gefið 12 bæti. En það er engin frekari athuga. Það er engin ef aðstæður. Það er engin villuprófun hér. 

Og svo það sem þetta forrit er að fara að gera er bara í blindni afrita eitt til annars. Og svo ef við draga þetta sem mynd, hér er bara flís af minni. Svo eftir neðst, við hafa staðbundin breytu bar. Þannig að bendillinn sem er að fara að store-- frekar að heimamenn rök sem er að fara að geyma band bar. Og þá taka bara ofan það í stafla, því í hvert skipti sem þú spyrð fyrir minni á stafla, það fer svolítið ofan það á myndrænan, Takið eftir að við höfum fengið 12 bæti það. Efst til vinstri er einn C krappi núll og neðst til hægri er einn C krappi 11. Það er bara hvernig tölvur að fara að leggja það út. Svo bara innsæi, ef bar er meira en 12 stafir samtals, þ.mt sem sviga núll, hvar er 12 eða C krappi 12 að fara að fara? Eða öllu heldur þar er 12. eðli eða 13. eðli, hundraðasta eðli fara að enda á myndinni? Fyrir ofan eða neðan? 

Hægri, því jafnvel þótt stafla sjálft vex upp, Þegar þú hefur sett efni í það, það ástæðum er varða hönnun setur minni frá toppur til botn. Þannig að ef þú hefur fengið meira en 12 bæti, þú ert að fara að byrja að skrifa bar. Nú er það galla, en það er í raun ekki máli. En það er stór samningur, vegna þess að það er meira efni að fara á í minni. Svo hér er hvernig við gætum setja halló, að vera ljóst. Ef ég slóst í halló þegar beðið. H-E-L-L-O sviga núll, endar upp innan þessir 12 bytes, og við erum frábær öruggur. Allt er vel. En ef ég slá eitthvað lengur, hugsanlega er það að fara að skríða inn í bar rúm. En verri enn, það kemur út allan þennan tíma, jafnvel þó að við höfum aldrei talað um það, stafla er notað fyrir önnur efni. Það er ekki bara staðbundnar breytur. 

C er mjög lágt tungumál. Og það er tegund af leynilega notar stafla einnig að muna þegar aðgerð er kölluð, hvað heimilisfangið er af fyrri virka, svo það getur hoppað aftur til að virka. Svo þegar helstu símtöl skipta, meðal það ýtt á stafla eru ekki bara skiptasamninga staðværar breytur, eða rök hennar, einnig leynilega ýtt á mánudaginn eins fulltrúa með rauða sneið hér, er heimilisfang helstu líkamlega í minni tölvunnar, þannig að þegar skipti er gert, the tölva veit að ég þarf að fara aftur til main og klára framkvæmd helstu virka. Svo er þetta hættulegt núna, vegna þess að ef sem notandinn slær í vel meira en halló, þannig að inntak notanda clobbers eða birtist sem rauður kafla, rökrétt ef tölvan er bara að fara að blindni ráð að bæti í því rauða sneið eru heimilisfangið sem það ætti að fara aftur, hvað ef andstæðingurinn er sviði nógur eða heppin að setja röð af bytes það sem lítur út eins og heimilisfang, en það er veffang kóða að hann eða hún vill tölvuna að framkvæma í stað þess að main? 

Með öðrum orðum, ef það á notandi er að skrifa á að hvetja, er ekki bara eitthvað innocuous eins halló, en það er í raun númer sem er jafngilt til að eyða öllum skrám notanda? Eða email lykilorðinu sínu til mín? Eða byrja skógarhögg þeirra mínútum, ekki satt? There er a vegur, við skulum kveða dag, að þeir gætu slegið í ekki bara halló heimurinn eða nafn sitt, þeir gátu í raun fara í kóða, núll og sjálfur, að tölvan mistök fyrir bæði kóða og heimilisfang. Svo að vísu nokkuð abstrakt, ef notandinn slær í nógu andstæðinga kóða sem við munum alhæfa hér sem A. A er árás eða mótstöðumenn. Svo bara slæmt efni. Við sama um númera eða núll eða þau í dag, svo að þú endar skrifa yfir þessi rauða kafla, eftir því að röð bæti. O 835 C núll átta núll. Og nú eins og grein Wikipedia hér hefur lagt til, ef þú nú í raun að byrja merkingu bæti í Computer þíns minni, hvað Wikipedia grein er að leggja er það, hvað ef netfang þess efst í vinstra bæti er 80 C 0 3508. 

Með öðrum orðum, ef slæmur strákur er klár nóg með kóða hans að í raun setja númer hér að samsvarar heimilisfang kóða hann eða hún sprautað inn í tölvuna, þú getur bragð tölvuna í að gera neitt. Fjarlægi skrár, póst hlutir, sjúga upp í nefið umferð, bókstaflega nokkuð gæti verið sprautað inn í tölvuna. Og svo gnægð biðminni árás á kjarna þess er bara heimskur, heimskur vega þyngra af fjölda sem ekki hafa mörk hennar köflóttur. Og þetta er það sem er frábær hættulegt og samtímis frábær öflugur í C er að við örugglega hafa aðgang að einhvers staðar í minninu. Það er allt að okkur, forritari, sem skrifa upprunalega kóðann að athuga fjári lengd eitthvað fylki sem við erum notfæra. Svo til að vera skýr, það er festa? Ef við rúlla aftur á þessa kóða, ég ætti ekki bara að breyta lengd bar, hvað annars ætti ég að haka? Hvað annað ætti ég að gera til að koma í veg fyrir þessa árás algjörlega? Ég vil ekki að bara í blindni segja sem þú ættir að afrita eins mörg bæti eins og er lengd bar. Ég vil segja, afrita og margir bæti sem eru í bar upp í úthlutað minni, eða 12 hámarks. Þannig að ég þarf einhvers konar ef ástand sem gerir að athuga lengd bar, en ef það fer yfir 12, við bara harður kóða 12 sem hámarks mögulega fjarlægð. Annars svokallaða stuðpúða flæða árás getur gerst. Á the botn af þeim glærum, ef þú ert forvitinn að lesa meira er í raun upprunalega grein ef þú vilt kíkja. 

En nú, meðal verð greitt hér var inefficiencies. Svo það var fljótur lágt líta á það vandamál geta komið upp nú þegar við hafa aðgang að minni tölvunnar. En annað vandamál við þegar lenti á mánudag var bara óhagkvæmni af tengda listanum. Við erum aftur að línulegum tíma. Við höfum ekki lengur aðlægur array. Við höfum ekki handahófi aðgang. Við getum ekki notað ferningur krappi tákn. Við höfum bókstaflega að nota while lykkju eins og einn sem ég skrifaði áðan. En á mánudaginn, hélt að við getum skríða aftur inn í ríki skilvirkni ná eitthvað sem er lógaritmískum kannski, eða besta enn, kannski jafnvel eitthvað sem er svokallaða föstu tíma. Og hvernig getum við gert það með því að nota þessar nýju verkfæri, þessar tölur, þessar ábendingar, og þráður hluti af okkar eigin? Jæja, ætla að hér eru þetta fullt talna sem við viljum geyma í gögn uppbygging og leita vel. Við getum alveg til baka til viku tveir, kasta þeim inn í array, og leita þá nota tvöfaldur leit. Skipta og sigra. Og í raun þú skrifar Tvíundarleit í PSET3, þar sem þú innleitt þitt finna forrit. En þú veist hvað. Það er góður af a fleiri sniðug leið til að gera þetta. Það er lítið meira háþróuð og það kannski gerir okkur kleift að sjá hvers vegna tvöfaldur Leitin er svo miklu hraðar. Í fyrsta lagi skulum kynna hugmyndin um tré. Sem jafnvel þó í veruleika tré konar vaxa svona, í heimi tölva vísindi og þeir vaxa konar niður eins og ættartré, þar sem þú þarft Amma þín og afi eða mikill afi eða whatnot efst, patriarcha og kristin fjölskyldunni, bara einn svokallaða rót, hnút, hér fyrir neðan sem eru börn hans, neðan sem eru börn hans, eða afkomendur hennar almennt. Og einhver hangandi burt neðst í fjölskyldunni tré, auk þess að vera yngsti í fjölskyldunni, getur líka bara verið generically kallaði blöð trésins. 

Svo er þetta bara fullt orðum og skilgreiningum fyrir eitthvað sem kallast tré í tölvunni vísindi, líkt og ættartré. En það er áhugamaður lífum trjáa, einn sem er kallað tvöfaldur leita tré. Og þú getur konar stríða sundur hvað þetta gerir. Jæja, það er tvöfaldur í hvaða skilningi? Hvar er tvöfaldur koma héðan? Sorry? Það er ekki svo mikið annað hvort eða. Það er meira að hvert hnúður hefur engin meira en tvö börn, eins og við sjáum hér. Almennt tree-- og foreldrar þínir og ömmur getur haft eins marga krakka eða grandkids eins og þeir vilja í raun, og svo til dæmis þar sem við höfum þrjú börn af því að hægra hnút, en í tvíundartré, hnúturinn hefur núll, einn, eða tvö börn hámarks. Og það er gott eign, því ef það er lokað með tveimur, við erum að fara að vera fær um að fá smá log stöð tvö aðgerð að fara á hér að lokum. Þannig að við höfum eitthvað lógaritmískum. En meira um það í smá stund. Leita tré þýðir að tölurnar eru komið er fyrir þannig að vinstri barnsins gildi er meiri en rót. Og rétt barn hennar er stærri en rót. Með öðrum orðum, ef þú tekur eitthvað af hnúður, hringirnir í þessari mynd, og lítur á vinstri hennar barn og rétt barn hennar, fyrsta ætti að vera minna en, annað ætti að vera hærri en. Svo geðheilsan stöðva 55. Það sem eftir er barnið er 33. Það er minna en. 55, rétt barn hennar er 77. Það er meiri en. Og það er endurkvæma skilgreiningu. Við gætum athuga hver og einn þeirra hnúður og sama mynstur myndi halda. 

Svo er það gott í tvíleitartré, er sem einn, við getum framkvæma það með strúktúr, bara eins og þetta. Og jafnvel þó að við erum að henda hellingur af mannvirkja á þitt, þeir eru nokkuð innsæi nú vonandi. The setningafræði er enn yfirnáttúrulegt fyrir víst, en innihald hnút í þetta context-- og við höldum nota orðið hnút, hvort sem það er rétthyrningur á skjánum eða hring, það er bara sumir almenn gámur, í þessu tilfelli á tré, eins og einn við sáum, að við þurfum heiltala í hverjum tengipunkta og þá þarf ég tvær ábendingum bendir til vinstri barnið og hægri barn, í sömu röð. Svo það er hvernig við gætum framkvæma að í strúktúr. Og hvernig gæti ég framkvæma það í númerið? Jæja, við skulum taka a fljótur líta á pínulitlum dæmi. Það er ekki virk, en ég hef afrita og líma þessi uppbygging. Og ef virka minn fyrir tvöfaldur search tree er kallað leit, og þetta tekur tvær breytur, heil tala N og bendi til hnút, svo bendi á tré eða bendi á rót á tré, hvernig get ég fara að leita að N? Jæja, fyrst, því ég er að takast á við ábendingum, Ég ætla að gera geðheilsu stöðva. Ef tré jafngildir jafngildir null, er N í þessu tré eða ekki í þessu tré? Það getur ekki verið, ekki satt? Ef ég er framhjá null, það er ekkert þar. Ég gæti eins vel bara blindni segja return false. Ef þú gefur mér ekkert, ég get örugglega ekki finna allir tala N. Svo hvað gæti ég athuga nú? Ég ætla að segja vel annað ef N er minna en hvað er tré hnút sem ég hef verið afhent N gildi. Með öðrum orðum, ef númer ég að leita að, N, er minna en hnút að ég er að horfa á. Og hnúturinn Ég er að leita á er kallað tré, og muna frá fyrra dæmi að fá á verðmæti í músina, Ég nota arrow tákn. Þannig að ef n er minna en tré ör N, ég vil eðli fara eftir. Hvernig get ég tjáð leita eftir? Til að vera skýr, ef þetta er myndin sem um ræðir, og ég hef verið samþykkt að hæstur arrow sem er að benda niður. Það er tré bendi minn. Ég er að benda á rót trésins. Og ég er að leita td að fjöldi 44, geðþótta. Er 44 minna en eða meiri en 55 augljóslega? Svo er það minna en. Og svo þetta ef gildir ástand. Svo hugtök, hvað mig langar að leita næst ef ég er að leita að 44? Já? 

Einmitt, ég vil leita vinstri barn, eða vinstri undir-tré af þessari mynd. Og í raun, láta mig í gegnum myndin hérna fyrir aðeins augnablik, síðan Ég get ekki klóra þetta út. Ef ég byrja hér á 55, og Ég veit að verðmæti 44 Ég er að leita að er að vinstri, það er góður af eins rífa símaskrána í helmingur eða rífa tré í tvennt. Ég hef ekki lengur að hugsa um þetta allt helmingur trénu. Og enn, forvitinn í skilmálar af the uppbyggingu, þetta hérna að byrjar með 33, sem sjálfu sér er tvöfaldur leita tré. Ég sagði orðið endurkvæma áður vegna reyndar er þetta gagnagrind sem samkvæmt skilgreiningu er endurkvæma. Þú gætir hafa tré sem er þetta stór, en hver og einn barna sinna táknar tré bara lítið minni. Í stað þess að vera afa eða amma, nú er það bara mamma or-- Ég get ekki say-- ekki mamma eða pabbi, það væri undarlegt. Í stað þess að tvö börn þar væri eins og bróðir og bróðir. Ný kynslóð af ættartré. En byggingu, það er sama hugmynd. Og það kemur í ljós ég er með virka sem ég get leitað til tvöfaldur leit tré. Það er kallað leit. Ég leita að N í tré arrow vinstri Annars ef n er meiri en verðmæti sem ég er nú á. 55 í sögunni í smá stund síðan. Ég er með fall sem kallast Leita að ég get bara fara N þetta og undirmöppum leita sub-tré og bara aftur hvað sem svarið. Annað sem ég hef fengið nokkrar endanlega grunntilvikið hér. 

Hvað er það sem kemur síðas málið? Tree er annaðhvort null. Gildi er ég annaðhvort að leita að er minna en það eða hærra en það eða jafn það. Og ég gæti sagt jafn jöfn, en rökrétt er það jafngildir bara að segja annað hér. Svo satt er hvernig ég finn eitthvað. Svo vonandi er þetta enn meira sannfærandi dæmi en heimskur Sigma virka við gerðum nokkrar fyrirlestra aftur, þar sem það var bara eins auðvelt að nota lykkju að telja upp allar tölur frá einum við N. hér með gögn uppbygging sem sjálft er endurkvæmt skilgreint og endurkvæmt dregin, nú erum við hafa getu til að tjá okkur í kóða sem sjálft er endurkvæma. Þannig að þetta er nákvæmlega sama kóða hér. 

Svo hvað annað vandamál getum við leyst? Svo fljótur skref í burtu frá tré fyrir réttlátur a augnablik. Hér er sagt, þýska fána. Og það er greinilega Mynstur þessari fána. Og það er hellingur af fánar í heiminum sem eru eins einfalt og þetta í skilmálar af litum og mynstrum. En geri ráð fyrir að þetta er geymt sem GIF, eða JPEG, eða punktamynd, eða Ping, allir grafísku skráarsnið sem þú ert kunnug, sem sum hver við erum spila með í PSET4. Þetta virðist ekki þess virði að geyma svartur punkta, svartur pixla, svartur punkta, punktur, punktur, punktur, allt fullt af svartur punktar fyrir fyrsta scanline, eða röð, þá er allt fullt af sama, þá er allt fullt á sama, og þá allt fullt af rauðum punktum, rauður pixlar, rauður pixlar, þá heild fullt af gulum dílar, gult, ekki satt? 

Það er svo óhagkvæmni hér. Hvernig myndir þú innsæi þjappa þýska fána ef að innleiða það sem skrá? Eins hvaða upplýsingar við getum ekki nennir að geyma á diski til að minnka stærð okkar frá eins megabæti á kílóbæti, eitthvað minni? Þar liggur offramboð hér til að vera ljóst? Hvað getur þú gert? Já? Nákvæmlega. Hvers vegna ekki frekar en muna litur hverjum fjári pixla bara eins og þú ert að gera í PSET4 með punktamynd skrá snið, hví þú ekki tákna bara Lengst til vinstri dálkur dílar, til dæmis fullt af svörtum punktum, fullt af rauðu, og fullt af gulum, og þá bara einhvern veginn umrita Hugmyndin um að endurtaka þetta 100 sinnum eða endurtaka þetta 1.000 sinnum? Þar sem 100 eða 1000 er bara heiltala, svo þú er hægt að fá í burtu með aðeins einni tölu í stað þess að hundruð eða þúsundir viðbótarútgáfu pixlar. Og reyndar, það er hvernig við gæti þjappa þýska fána. Og Nú hvað um franska fána? Og smá einhvers konar andlegt æfing, sem merkja að þjappa meira á diski? Þýska flag eða French merkja, ef við tökum þessi nálgun? Þýska flag, vegna þess að það er meira lárétt offramboð. Og af ásettu ráði, margir grafísku skrá snið virka örugglega eins skanna línur lárétt. Þeir gætu unnið lóðrétt, bara mannkynið ákvað ár síðan að við munum almennt hugsa um hlutina röð fyrir röð í stað dálk eftir dálk. Svo reyndar ef þú varst að líta á skrá stærð þýska fána og frönsku merkja, svo lengi sem upplausn er það sama, sama breidd og hæð, þetta hér er að fara að vera stærri, vegna þess að þú að endurtaka þig þrisvar sinnum. Þú verður að gefa blár, endurtaka sjálfur, hvítur, endurtaka þig, rauður, endurtaka þig. Þú getur ekki bara farið allt leiðin til hægri. Og eins og til hliðar, til að gera hreinsa þjöppun er alls staðar, ef þau eru fjórir rammar frá video-- þú gæti muna að bíómynd eða vídeó er almennt eins 29 eða 30 rammar á sekúndu. Það er eins og lítið selbiti bók þar þig bara sjá mynd, mynd, mynd, mynd, mynd bara frábær fljótur svo það lítur út eins og leikarar á skjánum eru að flytja. Hér er Bumble Bee á toppur af fullt af blómum. Og þó það gæti verið eins konar erfitt að sjá við fyrstu sýn, það eina færa í þetta bíómynd er flugan. 

Hvað er heimsk um að geyma video uncompressed? Það er góður af a úrgangs til að geyma vídeó og fjórum næstum eins myndir sem mismunandi aðeins að því marki sem þar flugan er. Er hægt að henda flest af þeim upplýsingum og muna aðeins, til dæmis, fyrsta ramma og síðasta ramma, lykill rammar ef þú hefur heyrt orðið, og bara geyma í miðja þar sem bí er. Og þú þarft ekki að geyma öll bleiku, og bláa, og Græn gildi eins vel. Svo er þetta aðeins segja að þjöppun er alls staðar. Það er tækni sem við notum oft eða taka sem sjálfsögðum hlut þessa dagana. 

En hvernig gera þú þjappa texta? Hvernig gera þú fara óður þjappa texta? Jæja, hver persóna í Ascii er eitt bæti, eða átta bita. Og það er góður af heimsk, ekki satt? Vegna þess að þú skrifar líklega og E og ég og O og U mikið oftar en eins W eða Q eða Z, eftir því á hvaða tungumáli þú ert að skrifa örugglega. Og svo hvers vegna erum við að nota átta bitar fyrir hvert bréf, þar á meðal amk Vinsælast bréf, ekki satt? Hvers vegna ekki að nota færri bita fyrir Super vinsæll bréf, eins og E, það sem þú giska fyrst í Wheel of Fortune, og nota fleiri bita fyrir því minna vinsæll bréf? Hvers vegna? Vegna þess að við erum bara að fara að nota þá sjaldnar. 

Jæja, það kemur í ljós að það hefur verið reynt að gera þetta. Og ef þú manst frá bekk skóla eða menntaskóla, Morse kóða. Morse kóða hefur punkta og bandstrik sem hægt er að flutt um þráð sem hljóð eða merki um einhvers konar. En Morse kóða er frábær hreint. Það er góður af a tvöfaldur kerfi í að þú hafir punkta eða bandstrik. En ef þú sérð, til dæmis, tveir punktar. Eða ef þú heldur aftur til rekstraraðila sem fer eins og píp, píp, píp, píp, hitting smá gikkur sem sendir merki, ef þú, viðtakandinn fær tvo punktar, hvað skilaboð hefur þú fengið? Alveg handahófskennt. 

I? I? Eða hvað about-- eða ég? Kannski var það bara tvö til hægri E er? Svo er það þetta vandamál af decodability með Morse númer, þar nema maður að senda þér skilaboð reyndar þagnar svo þú getur raða á sjá eða heyra bil milli bókstafa, það er ekki nóg bara að senda straum af núllum og sjálfur, eða punkta og bandstrik, vegna þess að það er tvíræðni. E er einn punktur, þannig að ef þig sjá tvær punkta eða heyra tvær punkta, kannski er það tveimur E eða kannski er það einn I. Þannig að við þurfum að kerfi sem er a lítið meira snjall en það. Svo maður að nafni Huffman ár síðan kom upp með nákvæmlega þetta. Þannig að við erum bara að fara að taka a fljótur tillit hvernig tré eru germane að þessu. Segjum að þetta er einhver heimskur skilaboðin sem þú vilt senda, samanstendur af aðeins A, B, D C er s og E er, en það er mikið offramboð hér. Það er ekki ætlað að vera á ensku. Það er ekki dulkóðuð. Það er bara heimskulegt skilaboð með fullt af endurtekningu. Svo ef þú telur í raun út öllum A er, B er, C er, D's, og E er, hér er tíðni. 20% af bréfum eru A er 45% af bréfum eru E, og þrír aðrir tíðni. Við talin þar upp með höndunum og bara gerði stærðfræðina. 

Svo kemur í ljós að Huffman, sumir tími síðan, komust að því að, þú veist hvað, ef ég byrja að byggja tré eða skógur af trjám, ef þú vilt, eins og hér segir, ég get gert eftirfarandi. Ég ætla að gefa hnút við hvert af bréfum sem mér þykir vænt um og ég ætla að geyma inni hnút tíðni sem fleytitölu gildi, eða þú getur notað það sem N líka, en við verðum bara að nota fljóta hér. Og algrím sem hann lagði er að þú taka þetta skógur einum hnút tré, svo frábær stutt tré, og þú byrjar að tengja þá með Nýir, nýja foreldra, ef þú vilt. Og þú gerir þetta með því að velja tveir minnstu tíðni í einu. Svo ég tók 10% og 10%. Ég að búa til nýjan hnút. Og ég kalla nýja hnút 20%. 

Sem tveir hnútar ég sameinað næst? Það er svolítið óljós. Svo er nokkur horn tilvikum að það íhuga, en að halda nokkuð, Ég ætla að velja 20% - Ég hunsa nú börnin. Ég ætla að velja 20% og 15% og draga tvær nýjar brúnir. Og nú sem tveir hnútar ekki ég sameinað rökrétt? Hunsa öll börn, allar barnabörn, bara líta á rætur núna. Hvaða tveir hnútar á ég binda saman? Point tvö og 0.35. Svo láta mig draga tvær nýjar brúnir. Og þá hef ég aðeins fengið einn vinstri. Svo hér er tré. Og það er verið dregin vísvitandi að líta svona nokkuð, en eftir því að brúnir hafa Einnig hefur verið merkt núll og einn. Svo öll á vinstri brúnir eru núll geðþótta, en stöðugt. Allt rétt brúnir eru þau. 

Og svo hvað Hoffman lagt er, ef þú vilt að tákna B, frekar en að tákna fjölda 66 eins og ASCII sem er átta allt bits, þú veist hvað, bara geyma mynstur núll, núll, núll, núll, því það er leiðin frá trénu mínu, tré Mr Huffman er, að blaða frá rót. Ef þú vilt geyma a E, hins vegar ekki senda átta bita sem jafngilda E. Þess í stað senda hvaða mynstur bita? Einn. Og hvað er gott um þetta er að E er vinsælasta bréf, og þú ert að nota Stysta póstnúmer fyrir hana. Næsta Vinsælasta bréf lítur út eins og það var A. Og svo hversu margir bitar gerði hann leggja nota fyrir það? Núll, einn. 

Og vegna þess að það er hrint í framkvæmd eins og þetta tré, fyrir nú láta mig mæla fyrir það er engin tvíræðni eins og í Morse númer, því öll að bréf sem þér þykir vænt um eru í lok þessara brúnir. Svo er það bara einn umsókn um tré. Þetta is-- og ég veifa hönd mín á þetta hvernig þér might framkvæma þetta sem C byggingu. Við þurfum bara að sameina tákn, eins og bleikju, og tíðni í vinstri og hægri. En við skulum líta á tvo endanlegar dæmi sem þú munt fá alveg kunnugur eftir quiz núll í Heimadæmi fimm. 

Svo er það að gögn uppbygging þekktur sem kjötkássa töflunni. Og kjötkássa borð er góður af er kælt í að það hefur hópa. Og ætla það er fjórum fötunum hér, aðeins fjórum eyða rými. Hér er þilfari á spil, og hér er Club, Spade, club, demöntum, club, demöntum, club, demöntum, clubs-- svo er þetta handahófi. Hearts, hearts-- þannig að ég er bucketizing öllum aðföngum hér. Og a kjötkássa borð þarf að líta á hjálpina, og þá setja það í ákveðinn setja miðað við það sem þú sérð. Það er reiknirit. Og ég var með frábær einfalt sjón reiknirit. Það erfiðasta hluta sem var muna hvað myndirnar voru. Og þá er það fjórum samtals hluti. 

Nú stafla voru vaxandi, sem er vísvitandi hönnun hlutur hér. En hvað annað gæti ég gert? Svo í raun hér höfum við fullt af gamla skólanum exam bækur. Segjum sem svo að fullt af nemendur nöfn eru hér. Hér er stærri kjötkássa borð. Í stað þess að fjórum fötu, Ég hef, við skulum segja 26. Og við vildum ekki að fara að taka lán 26 hlutina frá utanaðkomandi [? Annenberg?], Svo hér er fimm að tákna A í gegnum Ö Og ef ég sjá nemandi hét byrjar A, Ég ætla að setja hans eða quiz hana þar. Ef einhver byrjar með C, þarna, A-- raun, vildi ekki gera það. B fer hérna. Svo ég hef fengið A og B og C. Og nú er hér annar nemandi. En ef þetta kjötkássa borð er útfærð með fjölda, Ég er góður af ruglaður á þessum tímapunkti, ekki satt? Ég þarf svona til að setja þetta einhversstaðar. 

Svo ein leið sem ég get leyst þetta er allt rétt, A er upptekinn, B er upptekinn, C er upptekinn. Ég ætla að setja hann í D. Svo á fyrst ég handahófi augnablik aðgangur að hvert fötunum fyrir nemendur. En nú er eins konar Devolved í eitthvað línuleg, því ef ég vil leita að einhverjum Hvaða nafn byrjar með, athuga ég hér. En ef þetta er ekki A nemandi Ég er að leita að, Ég hef konar að byrja að skoða í fötunum, því það sem ég gerði var svona línulega rannsaka gögn uppbygging. A heimskur leið til að segja bara að líta í fyrsta boði opnun, og setja sem plan B, ef svo má segja, eða áætlun D í þessu tilviki er gildi í þeim stað í staðinn. Þetta er bara þannig að ef þú hefur fékk 26 stöðum og enga nemendur með nafni Q eða Z, eða eitthvað svoleiðis að minnsta kosti að þú ert að nota plássið. 

En við höfum þegar séð meira snjall lausnir hér, ekki satt? Hvað myndir þú gera í staðinn ef þú ert með árekstri? Ef tveir menn hafa nafn A, hvað myndi hafa verið betri eða fleiri innsæi lausn en bara Setja þar sem D er ætlað að vera? Hvers vegna get ég ekki farið bara utan [? Annenberg?], eins malloc, annan hnút, setja það hér, og þá setja það nemandi hér. Þannig að ég hef í raun einhvers konar fylki, eða kannski meira glæsilegur og við erum farin að sjá tengda lista. 

Og svo er kjötkássa borð uppbygging sem gæti líta bara eins og þetta, en meira snjall, þú eitthvað sem kallast sérstakt chaining, þar a kjötkássa borð einfaldlega er fylki, sem hver um sem þættir er ekki tala, er sjálf tengd lista. Þannig að þú færð frábær fljótur aðgangur ákvörðun um hvar á að kjötkássa gildi þitt til. Líkt með spil td Ég gerði frábær fljótur ákvarðanir. Hearts fer hér, demöntum fer hér. Sama hér, A fer hér, D fer hér, B fer hér. Svo frábær fljótur uppflettinga og ef þú verður að hlaupa inn í tilfelli hvar þú hefur fengið árekstrar tveggja fólk með sama nafni, og þá þú byrjar bara að tengja þá saman. Og kannski þú halda þeim raðað stafrófsröð, kannski ekki. En að minnsta kosti nú höfum við kraft. Svo annars vegar höfum við frábær fljótur stöðug tími, og eins konar línulegum tíma ræða ef þessi tengd listum byrja að fá smá lengi. 

Svo af þessu tagi kjánalegt, geeky brandari árum. Á CS50 hakk-þon, þegar nemendur innrita sumir TF eða CA á hverju ári telur að það er fyndið að setja upp merki eins og þetta, þar sem það bara þýðir að ef nafnið þitt byrjar með A, fara þessa leið. Ef nafnið þitt byrjar með B, fara this-- OK, það er fyndið kannski seinna í önn. En það er önnur leið til að gera þetta líka. Koma aftur til að. 

Svo er það þessi uppbygging. Og þetta er síðasta vor uppbygging í dag, sem er eitthvað sem kallast Trie. T-R-I-E, sem af einhverjum ástæðum er stutt fyrir sókn, en það er kallað Trie. Svo er Trie annar áhugaverður amalgam af a einhver fjöldi af þessum hugmyndum. Það er tré, sem við höfum séð áður. Það er ekki tvöfaldur leita tré. Það er tré með hvaða fjölda barna, en hver börnunum í Trie er fylki. An array af stærð, segja, 26 eða kannski 27 ef þú vilt styðja hyphenated nöfn eða úrfellingarmerki í mannanöfnum. 

Og svo er þetta gögn uppbygging. Og ef þú horfir frá toppi til botn, eins og ef þú líta á the toppur hnút þar, M, er bendir til lengst til vinstri hlutur þarna, sem er síðan A, X, W, E, L, L. Þetta er bara gagnagrind sem geðþótta er að geyma nöfn fólks. Og Maxwell er geymt bara með eftirfarandi a leið array array til array. En hvað er ótrúlegt um að Trie er að, en tengda listanum og jafnvel fylki, sá besti sem við höfum nokkru sinni fengið er línuleg tími eða lógaritmískum tíma í að leita einhver upp. Í þessum gögnum uppbyggingu Trie, ef gögn uppbygging minn hefur eitt nafn í það og ég er að leita að Maxwell, ég er fara að finna hann ansi fljótt. Ég lít bara fyrir M-A-X-W-E-L-L. Ef þessi gögn uppbygging, hins vegar ef N er milljón, ef það er milljón nöfn í þessum gögnum uppbyggingu, Maxwell er enn að fara að vera aðgengilegar á eftir aðeins M-A-X-W-E-L-L skref. Og David-- D-A-V-I-D skref. Með öðrum orðum, með því að byggja gögn uppbygging sem er fékk allar þessar fylki, sem allt sjálfir styðja handahófi aðgang, Ég get byrjað að horfa upp fólksins nefna að nota tíma sem er í réttu hlutfalli við ekki að tala af hlutum í gögn uppbygging, eins milljón núverandi nöfn. Tíminn sem það tekur mig að finna M-A-X-W-E-L-L í þessari gögn uppbygging er í réttu hlutfalli ekki til Stærð gögn uppbygging, en að lengd nafn. Og raunhæft að nöfnum sem við erum að horfa upp ert aldrei að fara að vera brjálaður lengi. Kannski hefur einhver með 10 staf nafn, 20 staf nafn. Það er vissulega tímabundið, ekki satt? Það er mannleg á jörðinni sem hefur lengstu mögulegu nafn, en það nafn er fasti gildi lengd, ekki satt? Það breytist ekki í hvaða skilningi. Svo á þennan hátt, höfum við náð gögn uppbygging sem er stöðug tími líta upp. Það þýðir að taka nokkur skref eftir lengd inntak, en ekki tölu nafns í gögn uppbygging. Þannig að ef við tvöfalda fjölda nafna á næsta ári frá milljarð til tvo milljarða, niðurstaða Maxwell er að fara að taka nákvæmlega sama fjölda sjö skrefum að finna hann. Og svo við virðast hafa náð okkar Gral keyra tíma. 

Svo a par af fljótur tilkynningum. Quiz núll er að koma upp. Meira um það á heimasíðu námskeiðsins er á næstu dögum. Mánudagur lecture-- það er frí hér á Harvard á mánudaginn. Það er ekki í New Haven, þannig að við erum að taka í bekknum New Haven til fyrirlestur á mánudaginn. Allt verður tekið og streyma lifandi eins og venjulega, en við skulum enda í dag með 30 sekúndu bút kallast "Deep Thoughts" eftir Daven Farnham, sem var innblásin síðasta ári með laugardaginn "Deep Thoughts" Night Live er Jack Handy, sem ætti nú skynsamleg. 

FILM: Og nú, "Deep Hugsun "eftir Daven Farnham. Kjötkássa borð. 

Ræðumaður 1: Allt í lagi, þá er það núna. Við munum sjá þig í næstu viku. 

DOUG: Til að sjá það í aðgerð. Svo skulum taka a líta á það núna. Svo hér höfum við óflokkuðu fylki. 

IAN: Doug, getur þú farið á undan og endurræsa þetta fyrir einni sekúndu, vinsamlegast. Allt í lagi, myndavélar eru veltingur, svo aðgerð þegar þú ert tilbúin, Doug, OK? DOUG: Allt í lagi, þannig að það sem við höfum hér er Óflokkaður array. Og ég hef litað alla þá þætti rautt til að sýna að það er í raun, Óflokkaður. Svo muna að það fyrsta sem við gerum er við að raða vinstri helming fylkisins. Þá erum við að raða rétt helmingur fylkisins. Og ya-da, ya-da, ya-da, við sameina þær saman. Og við höfum alveg flokkað array. Svo er það hvernig Mergesort virkar. 

IAN: Whoa, hó, hó, skera, skera, skera, skera. Doug, þú getur ekki bara ya-da, ya-da, ya-da, leið gegnum sameiningu tagi. 

DOUG: Ég gerði bara. Það er fínt. Við ert góður til fara. Við skulum halda bara veltingur. Svo engu að síður, 

IAN: Þú þarft að útskýra það betur en það. Það er bara ekki nóg. DOUG: Ian, eigum við ekki þarf að fara aftur til einn. Það er fínt. Svo engu að síður, ef við höldum áfram með merge-- Ian, við erum í the miðja af kvikmynda. 

IAN: Ég veit. Og við getum ekki bara ya-da, ya-da, ya-da, í gegnum allt ferlið. Þú þarft að útskýra hvernig tvær hliðar að steypa saman. 

DOUG: En við höfum nú þegar útskýrði hvernig tveir sides-- 

IAN: Þú hefur bara sýnt þá a sameinast array. DOUG: Þeir vita the aðferð. Þeir eru í lagi. Við höfum farið yfir það tíu sinnum. 

IAN: Þú sleppt bara rétt yfir það. Við erum að fara aftur til einn, þú getur þú ekki ya-da, ya-da yfir það. Allt í lagi, aftur til einn. 

DOUG: Ég verð að fara aftur gegnum allar renna? Guð minn. Það er eins og í sjötta sinn, Ian. Það er fínt. 

IAN: Allt í lagi. Ertu tilbúin? Great. Aðgerð.