>> 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ð.