[TÓNLIST spila] 

ANDI Peng: Velkomin viku 6. kafla. Við víkja frá staðal okkar kafla tími þriðjudag Síðdegis að þessum fallega sunnudegi. Þakka þér fyrir alla þá sem gekk mér í dag, en alvarlega, a umferð lófaklapp. 

Það er ansi stór átak. Ég næstum ekki einu sinni gera það upp í tíma, en það var allt í lagi. Þannig að ég veit, að þér hafa bara gert það við próf. Fyrst af öllu, velkomið að bakhlið þess. 

Í öðru lagi, munum við tala um það. Við munum tala um spurningakeppni. Við munum tala um hvernig þú ert að gera í bekknum. Þú munt vera fínn. Ég hef Skyndipróf þínar fyrir þú í lok hér, þannig að ef þú krakkar vilja til að taka a líta á það, algerlega í lagi. 

Svo fljótt áður en við byrjum, sem Dagskrá í dag er sem hér segir. Eins og þú geta sjá, við erum grundvallaratriðum hraður hleypa gegnum a heild búnt af gögn uppbygging virkilega, virkilega, virkilega hratt. Svo eins og svo, það mun ekki vera frábær gagnvirk dag. Það verður bara að vera mér góður af hróp hlutir sem þú, og ef ég rugla þig, ef ég ætla of hratt, láttu mig vita. Þeir eru bara ýmsar upplýsingar mannvirki, og sem hluta af pset þinn fyrir þetta komandi viku, munt þú beðinn um að framkvæma einn af þeim, kannski tveir them-- tveimur þeirra í pset þinn. OK, þannig að ég ætla bara að fara að byrja með nokkrum tilkynningum. Við munum fara yfir stöflum og biðröðum fleiri í dýpt en það sem við gerðum áður spurningakeppni. Við munum fara yfir tengd lista aftur, enn og aftur, meira dýpi en það við höfðum áður en próf. Og þá munum við tala um kjötkássa töflur, tré og reynir, sem eru öll mjög nauðsynlegt fyrir pset þinn. Og þá munum við fara yfir nokkrar góðar ábendingar um pset5. 

OK, svo quiz 0. Að meðaltali var 58%. Það var mjög lágt, og svo þið öll gerði mjög vel í samræmi með það. 

Nánast, þumalputtaregla er ef þú ert innan staðalfrávik meðaltala sérstaklega þar sem við erum í minna notalega kafla, þú ert alveg fínn. Þú ert á réttri braut. Lífið er gott. 

Ég veit að það er skelfilegt að hugsa um að Ég fékk eins og 40% á þessu quiz. Ég ætla að mistakast þennan flokk. Ég lofa þér, þú ert ekki að fara að mistakast á bekknum. Þú ert algerlega fínn. 

Fyrir þá sem fékk yfir að meðaltali, áhrifamikill, áhrifamikill, eins, alvarlega vel gert. Ég hef þá með mér. Feel frjáls til að koma fá þá í lok kafla. Láttu mig vita ef þú hefur einhverjar mál, spurningum með þeim. Ef við bætum upp stig rangt, láttu okkur vita. 

OK, svo pset5, þetta er virkilega undarlegt viku Yale í skilningi að pset okkar er vegna Miðvikudagur á hádegi þ.mt seint daginn, svo það er í raun fræðilega vegna þriðjudagur á hádegi. Sennilega enginn lokið á þriðjudag á hádegi. Það er algerlega fínt. Við erum að fara að hafa skrifstofutíma kvöld og mánudagskvöld. Og allt dæmatímum þessa viku verður raun verið breytt í verkstæði, svo ekki hika við að skjóta í allir hluti sem þú vilt, og þeir 'vera eins konar mini-pset námskeið fyrir hjálp í því. Svo sem slík, þetta er eina kafla þar sem við erum að kenna efni. Öll aðrir hlutar verður áherslu eingöngu á hjálp fyrir pset. Já? 

Áhorfendur: Hvar eru viðtalstímar? 

ANDI Peng: Viðtalstími tonight-- ó, góð spurning. Ég held Viðtalstími kvöld eru í Teal eða Commons. Ef þú athugar netinu CS50 og þú ferð að skrifstofutíma, það ætti að vera áætlun sem segir þér þar sem allir af þeim eru. 

Ég veit heldur í kvöld eða á morgun er Teal, og ég held að við gætum þurft Commons í daginn. Ég er ekki viss. Góð spurning. Kíkja á CS50. 

Kaldur, einhverjar spurningar varðandi áætlun fyrir næsta eins þrjá daga? Ég lofa ykkur eins og Davíð sagði, þetta er efst á hæðinni. Þú krakkar eru næstum þar. Bara þrjár fleiri daga. Komast þangað, og þá munum við koma niður. Við munum hafa a ágætur CS-hlé. Við munum koma aftur. Við munum kafa í vefnum forritun og þróun, hlutir sem eru mjög skemmtileg í samanburði að sumir af the annar psets. Og það verður slappað, og við munum hafa hellingur af gaman. Við munum hafa meiri sælgæti. Því miður fyrir sælgæti. Ég gleymdi nammi. Það var gróft morgun. Svo þú krakkar eru næstum þar, og ég er mjög stoltur af ykkur. 

OK, svo stafla. Sem elskaði spurningunni um Jack og klæðin á spurningakeppni? Enginn? OK, það er fínt. 

Svo í raun eins og þú getur mynd Jack, þetta strákur hér, elskar að taka fatnað út af the toppur á stafla, og hann setur það aftur á stafla eftir að hann hefur gert. Svo á þennan hátt, aldrei hann virðist vera að fá til the botn af the stafla í fötum hans. Svo af þessu tagi lýsir undirstöðu gögn uppbygging um hvernig stafla er hrint í framkvæmd. 

Í meginatriðum, hugsa um stafla sem allir stafla hlutum þar sem þú setja hlutina á toppinn, og þá þú skjóta þá út úr að ofan. Svo er LIFO skammstöfun sem við eins og að use-- Síðasta inn, fyrst út. Og svo endast í til the toppur af the stakkur er sá fyrsti sem kemur út. Og svo tvö hugtök við eins og til að tengja með sem eru kallaðir ýta og popp. Þegar þú ýta eitthvað inn á stafla, og þú skjóta það aftur upp. 

Og svo ég held að þetta sé góður af abstrakt hugtak fyrir þá sem vilja sjá eins að Raunveruleg framkvæmd þessa í hinum raunverulega heimi. Hversu margir af þú hafa skrifað ritgerð kannski eins og klukkutíma áður en það var vegna, og þú óvart eytt a gríðarstór klumpur af því, eins og af tilviljun? Og þá hvað stjórn gera við notum til að setja það aftur? Control-Z, já? Control-Z, þannig að magn af sinnum að Control-Z hefur bjargað lífi mínu, hefur vistað í rassinn á mér, í hvert skipti sem er framkvæmd í gegnum reykháf. 

Raun allar upplýsingar það er á Word skjal, það fær ýtt og smella á vilja. Og svo í raun þegar þú eyða neitt, skjóta þig það aftur upp. Og svo ef þú þarft það aftur á, þér ýta því, sem er það sem Control-C er. Og svo raunverulegur veröld virka um hvernig einfalda gögn uppbygging getur hjálpað til með daglegu lífi þínu. 

Svo er struct leiðin sem við að búa til raunverulega stafla. Við slá skilgreina strúktúr, og þá við köllum það stafla neðst. Og innan stafla, höfum við tvær breytur að við getum í raun vinna, þannig að við höfum bleikju stjörnu strengi getu. 

Allt sem það er að gera er að skapa fjölbreytta sem við getum geymt hvað sem þú vilt sem við getum ákvarðað getu sína. Getu er bara max upphæð atriði sem við getum sett inn í þetta fylki. INT stærð er teljarinn sem heldur utan um hversu margir hlutir eru nú í stafla. Svo þá getum við fylgst með, A, bæði hvernig stór raunverulegt stafla er, og, B, hversu mikið af því stafla við fyllt vegna þess að við viljum ekki að flæða yfir það getu okkar er. 

Svo til dæmis, þetta yndislega Spurningin var á spurningakeppni þína. Í meginatriðum hvernig við ýta á the toppur af stafla. Frekar einfalt. Ef þú horfir á það, við munum ganga í gegnum þetta. Ef [inaudible] size-- muna, þegar þú langar að fá aðgang að þeim breytu innan strúktúr, þú gera nafn struct.parameter. 

Í þessu tilfelli, s is nafn stafla okkar. Við viljum fá aðgang að stærð af því, svo við gerum s.size. Svo lengi sem að stærð er ekki jafnt getu eða eins lengi eins og það er minna en getu, annaðhvort myndi vinna hér. 

Þú vilt fá aðgang að innan staflans þíns, svo s.strings, og þú ert að fara að setja þessi nýju númeri sem þú vilt setja inn þar. Við skulum bara segja að við munum vilja til setja int n á mánudaginn, við gætum gert s.strings, sviga, s.size jafngildir n. Vegna stærð er þar sem við nú eru í stafla ef við erum að fara að ýta það á, aðgang við bara hvar sem stærð er, er núverandi fylling stafla, og við ýta int n á það. Og þá viljum við tryggja að við erum líka að incrementing stærð n, svo við getum haldið utan um að við höfum bætt auka hlutur til stafla. Nú höfum við meiri stærð. Er þetta hér skynsamlegt að allir, hvernig er rökrétt það virkar? Það var eins konar fljótur. Áhorfendur: Getur þú ferð yfir að s.stringss.strings [s.size] aftur? ANDI Peng: Jú, svo hvað gerir s.size nú gefa okkur? Áhorfendur: Það er núverandi stærð. ANDI Peng: Einmitt, svo núverandi vísitala sem stærð okkar er, og þannig að við viljum setja nýja heiltölu sem við viljum að setja inn s.size. Er að skynsamleg? Vegna s.strings, allt sem er er nafn fylkisins. Allt það er er að fá aðgang að array innan strúktúr okkar, og svo ef við viljum setja n í vísitölunni, við getum bara nálgast það með sviga s.size. Cool. 

Allt í lagi, pop, ég sauðakóðanum það út fyrir ykkur, en svipað hugtak. Er að skynsamleg? Ef stærð er meiri en núll, þá þú veit að þú vilt að taka eitthvað út af því að ef stærð er ekki meiri en núll, þá hafa ekkert í stafla. 

Svo þú vilt aðeins að framkvæma þetta númer, getur það aðeins skjóta ef það er eitthvað að skjóta. Þannig að ef stærð er meiri en 0, við mínus stærð. Við lækka stærð og síðan aftur hvað er inni í honum því við pabbi, við viljum aðgangur hvað er geymt í vísitölu efst á stafla. Allt skynsamleg? Ef ég gerði ykkur skrifa þetta út, myndi þið vera fær um að skrifa það út? OK, þú krakkar geta spilað í kring með það. Engar áhyggjur ef þú færð ekki það. Við höfum ekki tíma til að kóða það út í dag vegna þess að við höfum fékk fullt af þessum stofnunum að fara í gegnum, en í raun sauðakóðanum, mjög, mjög svipað að ýta. Bara fylgja eftir rökfræði. Gakktu úr skugga um að þú ert að nálgast allar aðgerðir strúktúr þitt rétt. Já? 

Áhorfendur: Mun þessi skyggnur og þetta allt hlutur vera upp í dag-ish? ANDI Peng: Alltaf, jebb. Ég ætla að reyna að setja þetta upp eins og klukkutíma eftir. Ég sendum Davíð, Davíð mun reyna að setja það upp eins og klukkutíma eftir þetta. 

OK, svo þá erum við að fara inn í þetta annað yndisleg gögn uppbygging kallast biðröð. Eins og þú krakkar geta séð hér, biðröð fyrir Breta meðal okkur, allt það er er lína. Svo þvert á það þú heldur að stafla er, biðröð er nákvæmlega það rökrétt að þú heldur það er. Það er haldið í reglum FIFO, sem er fyrst inn, fyrst út. Ef þú ert fyrsta einn í línu, þú ert sá fyrsti sem kemur út á línu. 

Svo það sem við viljum kalla þetta er dequeueing og enqueueing. Ef við viljum bæta eitthvað að biðröð okkar, enqueue við. Ef við viljum að dequeue, eða taka eitthvað í burtu, dequeue við. 

Svo sama skilningi að við erum konar búa föstum stærð þætti sem við getur geymt víst hluti, en við getum líka breyta þar sem við erum að setja breytur inni í þeim byggt á hvaða tegund af virkni sem við viljum. Svo stafla, vildum við síðasta einn, N að vera sá fyrsti út. Biðröð er að við viljum það fyrsta í að vera the fyrstur hlutur út. 

Svo strúktúr-gerð skilgreina, eins og þú geta sjá, það er svolítið öðruvísi frá því að stafla var því ekki bara að við verðum að halda utan um þar sem stærð nú er, við viljum líka að halda utan um höfuðið sem og hvar sem við erum nú. Þannig að ég held að það er auðveldara ef ég teikna þetta upp. Svo skulum ímynda erum við biðröð, þannig að við skulum segja að hausinn er hérna. Yfirmaður línu, við skulum bara segja að það er nú það, og við viljum að setja eitthvað í biðröð. Ég ætla að hringja í stærð raun er það sama og hala, enda þar biðröð er. Við skulum bara segja stærð er hérna. 

Svo er hvernig einn álita setja eitthvað inn í biðröð? Hvað Vísitala viljum við setja þar sem við viljum að setja inn. Ef þetta er upphaf þinn biðröð og þetta er endir af það eða stærð þess, hvar við langar að bæta næsta hlut? 

Áhorfendur: [inaudible] ANDI Peng: Einmitt, þú vilt bæta við það fer eftir hefur þú skrifað það. Annað hvort er þetta auður eða er auður. Svo þú vilt bæta við það sennilega hér vegna þess að ef stærð is-- ef þetta eru allt fullt, þú vilt til að bæta við það hérna, ekki satt? 

Og svo er það, en mjög, mjög einfalt, ekki alveg alltaf rétt vegna þess að helsta mismun milli biðröð og stafla er að biðröð getur reyndar vera handleika þannig að höfuðið breytingarnar eftir því hvar þú vilt upphaf bending til að byrja. Og þar af leiðandi, hali þinn er líka að fara að breytast. Og svo kíkja á þetta númer núna. Eins og þú krakkar voru einnig beðnir um að skrifa út á spurningakeppni, enqueue. Kannski munum við tala um hvers vegna svarið var hvað það var. 

Ég gat ekki alveg passa þessa línu á einn, en í raun þetta stykki af kóða ætti að vera í einni línu. Eyddu eins og 30 sekúndur. Taka a líta, og sjá hvers vegna þetta er leiðin sem það er. 

Mjög, mjög svipað struct, mjög, mjög svipuð uppbygging og fyrri stafla nema kannski ein lína af kóða. Og að einni línu af kóða ákvarðar virkni. Og það aðgreindu í raun biðröð frá reykháf. 

Einhver vilja til að taka a stunga í að útskýra hvers vegna þú hefur fékk þetta flókið hlutur í hér? Við sjáum endurkomu okkar dásamlegt vinur stuðull. Eins og þú krakkar mun brátt koma að viðurkenna í forritun, nánast hvenær sem þú þarft eitthvað að vefja utan um neitt, stuðull er að fara að vera leið til að gera það. Svo að vita það, er einhver að vilja að reyna að útskýra þessi lína af kóða? Já, eru öll svör samþykkt og velkomin. Áhorfendur: Ertu að tala við mig? ANDI Peng: Já. Áhorfendur: Ó, nei því miður. ANDI Peng: OK, þannig að við skulum ganga í gegnum þennan kóða. Svo þegar þú ert að reyna að bæta eitthvað á biðröð, í yndislegu tilfelli sem yfirmaður gerist að vera hérna, það er mjög auðvelt fyrir okkur að fara bara til enda setja eitthvað, ekki satt? En allt lið af biðröð er að höfuð getur raunverulega virk breyta eftir því hvar við vilt byrja á Q til að vera, og eins og svo, skotti er líka að fara að breytast. 

Og svo ímynda sér að þetta var ekki biðröð, heldur var þetta biðröð. Skulum segja að höfuð er hérna. Skulum segja biðröð okkar leit svona út. Ef við vildum að skipta þar upphaf línu er, skulum segja að við færst höfuð með þessum hætti og stærðir hér. 

Nú viljum við bæta við eitthvað að þetta biðröð, en eins og þú krakkar geta sjá, það er ekki svo einfalt og að bara bæta hvað sem er eftir stærð því þá keyra út af mörk raunverulegum array okkar. Þar sem við viljum raunverulega bæta við er hér. Það er fegurð biðröð er að okkur, sjónrænt það lítur út eins og línan fer svona, en hún er geymd í gögn uppbygging, þeir gefa það eins og eins og hringrás. Það hula konar kring að framan á sama hátt að lína getur einnig sett um eftir hvar þú vilt upphafi línu til að vera. Og svo ef við tökum a líta niður hér, við skulum segja að við vildum að búa til virka kallast enqueue. Okkur langaði til að bæta við int n í þann q. Ef q.size q-- við munum kalla að gögn okkar structure-- ef queue.size okkar ekki jafnt getu eða ef það er minna en getu, q.strings er array innan q okkar. Við erum að fara að setja miðaður við q.heads, sem er hérna, auk q.size stuðull af afköstum, sem vefja okkur aftur hér. 

Svo í þessu dæmi, vísitölu höfuð er 1, ekki satt? Vísitala stærð er 0, 1, 2, 3, 4. Þannig að við getum gert 1 plús 4 stuðull af getu okkar sem er 5. Hvað þýðir það að gefa okkur? Hvað er vísitala sem kemur út úr þessu? 

Áhorfendur: 0. 

ANDI Peng: 0, sem gerist að vera hérna, og þannig að við viljum vera fær um til að setja inn hérna. Og svo þetta jöfnu hér góður af bara virkar með allar tölur eftir því hvar þinn höfuð og stærð þín eru. Ef þú veist hvað þeir hlutir eru, þú veist nákvæmlega hvar þú vilt setja hvað er eftir biðlista. Er að skynsamleg að allir? 

Ég veit svona heila beitu sérstaklega þar sem þetta kom í kjölfar spurningakeppni þína. En vonandi allir nú skil hvers vegna þessi lausn eða þetta virka er leiðin sem það er. Einhver alveg komið á hreint á það? OK. 

Og svo nú, ef þér vildi dequeue þetta er þar sem höfuð okkar væri að breytast því ef við vorum að dequeue, við ekki taka burt enda q. Við viljum taka burt the höfuð, ekki satt? Svo sem vegna, höfuð er að fara að breyta, og það er hvers vegna þegar þú enqueue, þú hefur fengið að halda utan um þar sem höfuð og stærð þinni eiga að vera fær um að setja í rétta stöðu. 

Og svo þegar þú dequeue, Ég sauðakóðanum það líka út. Feel frjáls til að ef þú vilt að reyna erfðaskrá þetta út. Þú vilt færa höfuð, ekki satt? Ef ég vildi dequeue, ég myndi færa höfuð yfir. Þetta myndi vera yfirmaður. 

Og núverandi stærð okkar myndi draga vegna þess að við ekki lengur hafa fjóra þætti í fylkinu. Við höfum aðeins þrjá, og þá viljum til að fara aftur hvað var geymt inni á höfði vegna þess að við viljum taka þetta gildi út svo mjög svipuð mánudaginn. Bara þú ert að taka frá öðrum stað, og þú þarft að endurúthluta bendilinn til mismunandi stað í kjölfarið. Rökrétt, allir fylgja? Great. 

OK, þannig að við erum að fara að tala aðeins meira dýpi um tengd listum vegna þess að þeir verða mjög, mjög mikilvæg fyrir þig í tengslum við þetta viku psets. Tengd listum, eins og þú krakkar man, allt sem þeir eru eru hnútar sem eru hnútar á tilteknum Gildi bæði gildi og bendi sem eru tengd saman af þeim ábendingum. Og svo struct um hvernig við að búa til hnút hér er við hafa int N, þar sem er hvað sem gildi í verslun eða streng n eða hvað sem þú vilt kalla það, bleikju stjörnu n. Struct hnút stjörnu, sem er bendillinn sem þú vilt hafa í hvern hnút, þú ert að fara að hafa það bendillinn lið til næst. Þú munt hafa höfuðið af tengda listanum sem er að fara að benda til the hvíla af gildi svo framvegis og svo framvegis þar til þú nærð að lokum enda. Og þetta síðasta hnúturinn bara að fara að ekki hafa músina. Það er að fara að benda á null, og það er þegar þú veist að þú hefur högg the enda tengist listanum er þegar síðustu bendillinn þinn ekki benda á neitt. 

Þannig að við erum að fara að fara aðeins meira í dýpt um hvernig maður myndi hugsanlega leita tengda lista. Muna hvað eru sumir af the göllum tengd listum vers á fjölbreytta um leitir. An array þú getur tvöfaldur leita, en af hverju getur þú ekki gert það í tengda listanum? 

Áhorfendur: Vegna þess að þeir eru allir tengdir, en þú ert ekki alveg hvar [Inaudible]. 

ANDI Peng: Já, einmitt svo muna að ljómi af fjölda var sú staðreynd að við þurftum handahófi aðgangur minni þar ef ég vildi verðmæti úr vísitölu sex, gæti ég bara segja vísitölu sex, gefa mér gildi. Og það er vegna fylki eru flokkuð í samfelldu rými minni á einum stað, en konar tengd listum eru af handahófi interspersed allt í kring, og eina leiðin sem þú getur fundið einn er með músina sem segir þér veffang þar sem næsta hnúturinn. 

Og svo þar af leiðandi eina leiðin að leita í gegnum tengda listanum er línuleg leit. Þar sem ég er ekki nákvæmlega hvar 12. gildi í tengda listanum er, Ég verð að fara yfir heild hins tengda listanum eitt af öðrum úr höfði til fyrsta hnút, til seinni hnút, til þriðja hnút, alla leið niður þar til ég fæ loksins að þar sem hnúturinn ég er að leita að er. Og svo í þessum skilningi, leita á tengda listanum er alltaf n. Það er alltaf n. Það er alltaf í línulegum tíma. 

Og svo kóðann sem við innleiða þetta, og þetta er svolítið nýtt fyrir ykkur þar sem þú krakkar hafa í raun ekki talað um eða alltaf séð ábendingum í hvernig á að leitað í ábendingum, þannig að við munum ganga í gegnum þetta mjög, mjög hægt. Svo bool leit, hægri, við skulum ímynda viljum til að búa til fall sem kallast Leita að skilar satt ef þú fundið gildi inni tengda lista, og það skilar ósatt annars. Hnútur stjörnu listi er nú bara bendillinn að fyrsta atriðinu í tengda listanum. INT n er gildið sem þú ert leita í þeim lista. 

Svo hnút stjörnu bendi jafngildir lista. Það þýðir að við erum að setja og skapa músina á þennan fyrsta hnút inni á listanum. Allir með mér? Þannig að ef við vorum að fara aftur hingað, hefði ég frumstilla bendi sem bendir til yfirmaður hvað þessi listi er. 

Og þá þegar þú færð niður hér, en bendi ekki jafn null, Svo er að lykkju þar sem við erum að fara að vera í kjölfarið fara yfir restin af listanum okkar vegna þess að það gerist þegar bendillinn jafngildir null? Við vitum að við have-- 

Áhorfendur: [inaudible] 

ANDI Peng: Einmitt, svo við vitum að við höfum náð enda listans, ekki satt? Ef þú ferð aftur hingað, hver hnútur skal vísa á annan hnút og svo framvegis og svo framvegis þar til þú högg að lokum skottið af tengda listanum þínum, sem hefur músina sem bara ekki benda hvar annar en nr. Og svo þú veist í rauninni að Listinn er enn þarna uppi þar bendi ekki jafn null því þegar það jafngildir null, þú veist að það er ekkert meira efni. 

Svo er að lykkja sem við erum fara að hafa raunverulegt leit. Og ef pointer-- sérðu þannig ör virka þar? Svo ef músina stig til n, ef bendillinn á n jafngildir jafngildir n, svo þýðir að að ef bendillinn að þú ert leita á í lok hvers hnútur er í raun er jafnhá og þú ert að leita að, þá þú vilt aftur satt. Svo í rauninni, ef þú ert á hnút sem hefur gildið sem þú ert að leita að, þú veist að þú hefur verið tekist að leita. 

Annars, þú vilt setja bendi til næsta hnút. Það er það sem þessi lína hér er að gera. Pointer jafngildir músina næst. Allir sjá hvernig það er að vinna? 

Og í raun að þú ert að fara að bara fara yfir í heild sinni á listanum, endurstilla bendilinn í hvert sinn þar til þú högg að lokum enda á listanum. Og þú veist að það eru engin fleiri hnútar að leita í gegnum, og þá er hægt að return false vegna þess að þú veist það, ó vel, ef ég hef getað til að leita gegnum heild á listanum. Ef í þessu dæmi, ef ég vildi að leita að verðmæti 10, og ég byrja á höfuðið, og Ég leita alla leið niður, og ég fékk að lokum að þetta, sem bendi sem bendir á núll, Ég veit það, vitleysa, ég held 10 er ekki í þessi listi því ég gat ekki fundið það. Og ég er í lok listanum. Og í því tilviki sem þú veist Ég ætla að fara aftur rangar. 

Láta það liggja í bleyti í fyrir smá. Þetta verður ansi mikilvægt fyrir pset þinn. Röksemdafærsla af því er mjög einfalt, kannski setningafræðilega bara útfæra hana. Þú krakkar vilja til að gera viss um að þú skiljir. Cool. 

OK, svo hvernig við viljum vera setja hnúta, hægri, í lista vegna þess að muna hvað eru það af þeim ávinningi að hafa tengdan lista á móti fylki í skilmálar af geymslu? 

Áhorfendur: Það er breytilegt, svo það er auðveldara to-- 

ANDI Peng: Einmitt, svo það er dynamic, sem þýðir að það er hægt að stækka og minnka eftir þörfum notandans. Og svo, í þessum skilningi, að við þurfum ekki að eyða óþarfa minni vegna þess að ég ef ég veit ekki hversu mörg gildi sem ég vil til að geyma, er það ekki skynsamleg fyrir mig að búa til array vegna þess ef ég vil að geyma 10 gildi og ég skapa fjölbreytta 1.000, sem er a einhver fjöldi af sóa minni, er úthlutað. Þess vegna viljum við nota tengdur lista til að vera fær um að virk breyta eða minnka stærð okkar. 

Og svo gerir það innsetningu dálítið flóknara. Þar sem við getum ekki af handahófi aðgang að þætti á þann hátt að við myndum af fjölda. Ef ég vil setja stak í sjöunda vísitölu, Ég get bara setja það í sjöunda vísitölunni. Á tengda listanum, er það ekki alveg vinna eins auðveldlega, og svo ef við vildum að setja einn hér í tengda listanum, sjónrænt, það er mjög auðvelt að sjá. Við viljum bara að setja það þarna, rétt í byrjun á listanum, rétt eftir höfði. 

En leiðin sem við höfum til að endurúthluta ábendingum er dálítið undinn eða, rökrétt, það er vit í, en þú vilt vera viss um að þú hafir það alveg niður vegna Það síðasta sem þú vilt er að endurúthluta músina sem Leiðin sem við erum að gera hér. Ef þú dereference á bendillinn frá höfuð til 1, þá allt í einu restin af tengda listanum er glatað vegna þess að þú ert í raun ekki skapað tímabundið neitt. Það er bent á 2. Ef þú endurúthluta músina, þá er restin af listanum þínum er algerlega glataður. Svo þú vilt vera mjög, mjög varkár hér fyrst framselja bendillinn frá hvað þú langar að setja inn þar sem þú vilt, og þá getur dereference the hvíla af listanum þínum. 

Svo gildir þetta fyrir þar þú ert að reyna að setja inn. Ef þú vilt setja á the höfuð, ef þú vilt svara hér, ef þú vilt setja á enda vel, enda I held þú vildi bara hafa ekki músina, en þú vilja til að ganga úr skugga um að þú ert ekki missa restina af listanum þínum. Þú vilt alltaf að ganga úr skugga um Ný hnút er að benda að hvað sem þú langar að setja inn, og þá er hægt að bæta við chaining á. Allir ljóst? 

Þetta er að fara að vera einn af raunverulegum vandamálum. Eitt af því sem helstu málefni þú ert að fara að hafa á pset þinn er að þú ert að fara að reyna að búa til tengda lista og setja inn það en þá bara missa restin af tengda listanum. Og þú ert að fara að vera eins og ég veit ekki hvers vegna þetta er að gerast? Og það er verk að fara í gegnum og leita að ábendingum þínum. 

Og ég tryggt þér á þessari pset, skrifa og teikna þessir hnútar út verður mjög, mjög gagnlegt. Svo þú getur alveg haldið utan af þar sem allir ábendingum eru, hvað er að gerast rangt, þar sem allir hnútar eru, það sem þú þarft að gera til að komast í eða setja inn eða eyða eða eitthvað af þeim. Allir góður með það? Cool. 

Þannig að ef við vildum að líta á kóðann? Oh, ég veit ekki hvort við getur séð the-- lagi, svo efst allt það er er fall heitir settu þar sem við viljum að setja int n í tengda listanum. Við erum að fara að ganga í gegnum þetta. Það er mikið af kóða, fullt af nýjum setningafræði. Við munum vera í lagi. 

Svo upp á toppinn, þegar við viljum búa til neitt hvað þurfum við að gera, sérstaklega ef þú vilja það að ekki að vera geymd á mánudaginn en í hrúgu? Við förum til malloc, ekki satt? Þannig að við erum að fara að búa til músina. Hnútur, músina, ný jafngildir malloc á stærð við hnút vegna þess að við viljum að hnúturinn að vera búin. Við viljum magn af minni sem hnúturinn tekur verður úthlutað fyrir stofnun nýjan hnút. 

Og þá erum við að fara að athuga að sjá hvort ný jafngildir jafngildir null. Mundu hvað ég sagði? Hvað sem þú malloc, hvað verður þú að gera alltaf? Þú verður alltaf að athuga að sjá hvort sem er null. 

Til dæmis, ef rekstur þinn Kerfið var alveg fullt, ef þú hefðir ekki meira minni í allt og þú reynir að malloc, það myndi skila null fyrir þig. Og svo ef þú reynir að nota það þegar það var að benda á núll, þú ert ekki að fara að geta að fá aðgang að upplýsingum. Og svo eins og svo vildum við gera viss um að þegar þú ert að mallocing, þú ert alltaf að stöðva til sjá ef að minni gefið er null. Og ef það er ekki, þá getum við flutt á við restina af kóða. 

Þannig að við erum að fara að frumstilla nýja hnút. Við erum að fara að gera nýja n jafngildir n. Og þá erum við að fara að gera setja nýja músina á ný að null því núna að við gerum ekki vilja eitthvað fyrir það að benda til. Við höfum ekki hugmynd um hvar það er að fara að setja þig, og þá ef við viljum setja það á höfuðið, þá getum við endurúthluta bendillinn að höfði. Er allir fylgja rökfræði hvar sem er að gerast? 

Allt sem við erum að gera er að búa til nýja hnút, setja músina á núll, og þá reassigning það að höfuð ef við vitum við viljum að setja hana á höfuðið. Og þá höfuð er að fara að benda til þess nýja hnút. Allir í lagi með það? 

Svo er það tveggja þrepa ferli. Þú hefur fengið að fyrst tengja hvað sem þú ert að skapa. Setja sem bendi á tilvísun, og þá getur konar dereference fyrsta bendillinn og benda í átt að nýju hnút. Þar sem þú vilt að setja það, sem rökfræði er að fara að halda satt. 

Það er góður af eins og að framselja tímabundin breytum. Mundu, þú hefur fengið að ganga úr skugga um að þú missir ekki utan um ef þú ert að skipta. Þú vilt tryggja að þú sért með tímabundin breyta þannig heldur utan um hvar þessi hlutur er geymt þannig að þú ekki missa allir gildi á námskeiðinu af eins og Messías í kring með það. 

OK, svo merkjamál vilja vera hér. Þið kíkið eftir kafla. Það mun vera þar. 

Svo ég giska á hvernig virkar þetta eru mismunandi ef við vildum að setja inn í miðju eða enda? Er einhver með hugmynd um hvað er að sauðakóðanum sem rökrétt tilvísun að við myndum gera ef við vildum að setja það í miðjunni? Þannig að ef við vildum að setja það á höfuð, allt sem við gerum er að búa til nýjan hnút. Við settum músina af því Ný hnút til hvað höfuð, og þá erum við sett höfuðið til nýjan hnút, ekki satt? Ef við vildum að setja það í miðju á listanum, hvað myndum við gera? 

Áhorfendur: Það myndi samt vera svipað ferli af eins framselja músina og þá framselja þessi músina, en við hefðum að finna þar. 

ANDI Peng: Einmitt, svo nákvæmlega sama aðferð nema þú að finna hvar nákvæmlega þú vil að ný bendillinn að fara inn, þannig að ef ég vil setja inn um miðja tengd list-- OK, skulum segja að það er tengd listi okkar. Ef við viljum að setja það hérna, við erum að fara að búa til nýjan hnút. Við erum að fara að malloc. Við erum að fara að búa til nýjan hnút. Við erum að fara að framselja bendi á þessa hnút hér. 

En vandamálið sem er mismunandi frá þar sem hausinn er er að við vissum nákvæmlega þar sem höfuðið. Það var rétt í fyrsta, ekki satt? En hér við verðum að halda utan þar sem við erum að setja það inn. Ef við erum að setja okkar hnút hér, höfum við fengið að ganga úr skugga um að einn fyrri þessari hnút er sá sem reassigns bendilinn. Svo þá verður þú að eins konar halda utan um tvennt. Ef þú halda utan um hvar þessi hnút nú er að setja inn. Þú þarft einnig að halda utan um hvar fyrri hnút sem þú ert að leita á var líka þar. Allir góður með það? OK. 

Hvernig um að setja inn í endanum? Ef ég vildi bæta því here-- ef ég vildi að bæta við nýjum hnút til loka lista, hvernig gæti ég farið um að gera það? Áhorfendur: Svo nú, benti síðasta manns til null. ANDI Peng: Já. Einmitt, svo þetta nú er bent á að vita, og svo ég giska, í þessum skilningi, það er mjög auðvelt að bæta við lok listanum. Allt sem þú þarft að gera er að setja það jafnt á núll og þá uppsveiflu. Þarna, mjög auðvelt. Mjög einfalt. 

Mjög svipað höfuð, en rökrétt þér vilja til að ganga úr skugga um að stíga þú tekur í átt að gera eitthvað af þessu, þú ert að elta eftir. Það er mjög auðvelt að, í miðju af kóðanum þínum, fá caught upp á, ó, ég hef fengið svo margar ábendingar. Ég veit ekki hvar eitthvað er að benda á. Ég veit ekki einu sinni hvaða hnút Ég er á. Hvað er í gangi? 

Slakaðu á, róa niður, taka djúpt andann. Draga út tengdan lista þinn. Ef þú segir, ég veit hvar nákvæmlega Ég þarf að setja þetta í og ég veit nákvæmlega hvernig á að endurúthluta minn ábendingum, miklu, miklu auðveldara að mynd out-- miklu, miklu auðveldara að ekki týnast í galla kóðann þinn. Allir í lagi með það? OK. 

Svo ég giska á hugmynd sem við höfum ekki virkilega talaði um áður en nú, og ég held að þú líklega verður ekki fundur mikið yet-- það er góður af háþróuðum concept-- er að við höfum í raun gögn uppbygging kallast tvöfalt tengda listanum. Svo eins og þú krakkar geta sjá, allt sem við erum að gera er að búa til raunveruleg gildi, auka bendillinn á hvert hnúta okkar sem einnig bendir á fyrri hnút. Svo ekki bara að við höfum okkar hnútar benda til the næstur einn. Þeir benda einnig á að fyrri einn. Ég ætla að hunsa þessar tvær núna. 

Svo er þá að hafa keðju sem getur flutt báða vegu, og þá er það svolítið auðveldara að rökrétt fylgja eftir. Út eins og hér, í stað þess að að halda utan um, ó, ég að vita að þetta hnúturinn sá að ég þarf að endurúthluta, Ég get bara farið hér og bara rífa fyrri. Þá veit ég nákvæmlega hvar sem er, og þá þurfa ekki að fara yfir heild á tengda listanum. Það er svolítið auðveldara. 

En eins og svo, þú þarft tvöfalt magn af ábendingum, það er tvöfalt magn af minni. Það er mikið af ábendingum að halda utan um. Það er dálítið flóknari, en það er aðeins meira notendavænt eftir eftir því hvað þú ert að reyna að ná. 

Þannig að þetta tegund af gögnum uppbygging er til algerlega, og uppbygging fyrir er mjög, mjög einfalt nema allt sem þú ert með er, í stað þess að bara bendi á næsta, þú hefur líka bendi fyrri. Það er allt munurinn var. Allir góður með það? Cool. 

Allt í lagi, svo nú er ég að virkilega eyða sennilega eins 15 til 20 mínútur eða lausu af the hvíla af the tími í kafla að tala um kjötkássa matskeið. Hversu margir af ykkur hef lesið pset5 sérstakur? Allt í lagi, gott. Það er hærra en 50% af venjulega. Það er allt í lagi. 

Svo eins og þú krakkar vilja sjá, þú ert áskorun í pset5 verður að innleiða orðabók þar sem þú hleður yfir 140.000 orð að við gefum þér og villuleit það gegn öllum textanum. Við munum gefa þér handahófi stykki af bókmenntum. Við munum gefa þér Odyssey. Við munum gefa þér Ilíonskviða. Við munum gefa þér Austin Powers. 

Og áskorun verður að leiðréttingar hvert einasta orð í öllum þessara orðabóka meginatriðum með afgreiðslumaður stafsetningu okkar. Og svo er það nokkur hlutar um að skapa þetta pset, fyrst þú vilt vera fær til raunverulega hlaða öll orð í þinn orðabók, og þá langar að vera fær um að villuleit þeim öllum. Og svo eins og svo, þú ert að fara að krefjast gögn uppbygging sem getur gert þetta hratt og duglegur og mjög virk. 

Þannig að ég býst auðveldasta leið til að gera þetta, þú myndi líklega búa til array, ekki satt? Auðveldasta leiðin til að geymsla er þér getur búið til fjölda 140.000 orðum og bara setja þá alla þar og þá fara yfir þá með tvöfaldur leit eða vali eða not-- fyrirgefðu, það er flokkun. Hægt er að raða þeim og þá fara yfir þær með tvöfaldur leit eða bara línuleg leit og bara endanlegar orð, en það tekur a gríðarstór magn af minni, og það er ekki mjög duglegur. 

Og svo við erum að fara að byrja að tala um leiðir til að gera okkar hlaupandi tíma skilvirkara. Og markmið okkar er að fá stöðug tími þar það er nánast eins og fylki, þar þú þarft tafarlaus aðgang. Ef ég vildi að leita að neinu, Mig langar að vera fær til réttlátur, Boom, finna það nákvæmlega, og draga það út. Og svo uppbyggingu þar sem við munum vera að verða mjög nálægt að vera fær um að fá aðgang að stöðug tími, þetta Gral í forritun stöðug Hvenær er kallað kjötkássa borð. Og svo David getið áður [Inaudible] svolítið í fyrirlestri, en við erum að fara að virkilega kafa í djúpum þessari viku á stykki sem er um hvernig kjötkássa borð virkar. 

Svo á þann hátt að kjötkássa Tafla Works, til dæmis, ef ég vildi geyma fullt af orðum, fullt af orðum í ensku, Ég gæti fræðilega sett banani, epli, rúsínur, mangó, par, og cantaloupe allt á bara fylki. Þeir gætu allt passa í og ​​vera finna. Það væri góður af a sársauki til að leitað og aðgengi, en auðveldara leiðin til að gera þetta er að við getum búið í raun uppbygging kallað kjötkássa borð þar sem við kjötkássa. Við að keyra alla lykla okkar í gegnum a kjötkássa virka, jafnan, sem snýr þeim öllum í einhvers konar gildi að þá getum við geymt á meginatriðum fjölbreytta tengda listanum. 

Og svo hér, ef við vildum að geyma ensk orð, við gátum hugsanlega bara, ég er ekki vita, snúa öllum fyrstu stafina í einhvers konar tölu. Og svo, til dæmis, ef ég vildi A að vera samheiti apple-- eða með vísitölu 0, og B að vera samheiti með 1, við getum haft 26 færslur sem getur bara geymt allar stafina í stafrófið sem við munum byrja með. Og þá getum við haft epli á vísitölu 0. Við getum haft banana í vísitölu 1, cantaloupe á vísitölu 2, og svo framvegis og svo framvegis. Og svona ef ég vildi til að leita kjötkássa borð og aðgangur epli minn, Ég veit epli byrjar með An A, og ég veit nákvæmlega að það verður að vera og kjötkássa borð á vísitölu 0 vegna fallsins áður úthlutað. 

Svo ég veit ekki, erum við notandi program þar þú munt vera innheimt með arbitrarily-- ekki geðþótta, við að reyna að hugsunarsamur hugsa um góða jöfnur til að vera fær um að dreifa út alla gildum á þann hátt sem þeir geta auðveldlega nálgast það seinna með eins jöfnu að þú, sjálfur, vita. Svo í þeim skilningi ef ég vildi fara í mangó, ég veit, ó, það byrjar með m. Það verður að vera á vísitölu 12. Ég þarf ekki að leita í gegnum neitt. Ég veit exactly-- ég gæti bara farið til Vísitala 12 og draga það út. 

Allir á hreinu hvernig virka kjötkássa borð vinnur? Það er góður af bara flóknari fylkisins. Það er allt það er. OK. 

Svo ég held að við að keyra inn þetta mál af því gerist ef þú ert með marga hluti sem gefa þér sömu vísitölu? Svo segja fallið, allt það gerði var að taka þessi fyrstu bréf og snúa það inn í a Viðkomandi 0 gegnum 25 vísitölunni. Það er algerlega í lagi ef þú hefur aðeins einn af hverjum. En seinni byrjað hafa meira, þú ert að fara að hafa það sem er kallað árekstur. 

Svo ef ég reyni að setja jarða í kjötkássa borð sem þegar hefur banani á það, hvað er að fara að gerast þegar þú reynir að setja það? Slæmur hlutur af því að banani þegar til innan vísitölunnar sem þú vilt geyma það í. Berry konar er eins, Ah, hvað á ég að gera? Ég veit ekki hvar á að fara. Hvernig get ég leysa þetta? 

Og svo þú krakkar vilja konar sjá við gerum þetta erfiður hlutur þar sem við getum konar raun búa tengda listanum í fylki okkar. Og svo auðveldasta leiðin að hugsa um þetta, allt kjötkássa borð er array tengdra listum. Og svo, í þeim skilningi, hefur þú Þessi fallega array af ábendingum, og þá hver bendi á að verðmæti, í þeirri vísitölu, geta í raun benda til annars. Og svo þú verður allt þetta aðskilið keðjur koma burt af einn stór fylking. 

Og svo hér, ef ég langaði að setja Berry, Ég veit, OK, ég ætla að inntak það í gegnum kjötkássa virka mína. Ég ætla að enda upp með vísitölu 1, og þá er ég að fara að vera fær um að hafa bara minni hlutmengi af þessu risastór 140.000-orð orðabók. Og þá get ég bara líta gegnum 1/26 af því. 

Og svo þá get ég bara að setja inn Berry annaðhvort fyrir eða eftir banani í þessu tilfelli? Eftir, ekki satt? Og svo þú ert að fara til að vilja setja þennan hnút eftir banana, og svo þú ert að fara að setja á skottið á þeim tengda listanum. Ég ætla að fara aftur þessari skyggnu, svo þú krakkar geta séð hvernig kjötkássa virka virkar. 

Svo er kjötkássa virka þessi jafna að þú ert að keyra svona hjálpina gegnum til að fá hvað sem vísitölunni þú vilt tengja hana að. Og svo, í þessu dæmi, vildi allt við að gera var að taka fyrsta stafinn, snúa það inn í vísitölu, þá erum við getur geymt það í kjötkássa virka okkar. Allt sem við erum að gera hér er að við erum umbreyta fyrsta stafinn. Svo keykey [0] er bara fyrsti stafurinn af hvaða band við erum með, við erum sem liggur í. Við erum að breyta því að efri og við erum að draga af hástafi A, þannig að allir sem er að gera er að gefa okkur ýmsar þar sem við getum kjötkássa gildi okkar á. 

Og þá erum við að fara að aftur kjötkássa stuðull stærð. Vera mjög, mjög varkár vegna þess, fræðilega, hér kjötkássa gildi þitt gæti verið óendanlegur. Það gæti bara farið á og á og á. Það gæti verið einhver mjög, mjög stór gildi, heldur vegna þess að kjötkássa töflunni að þú hefur búið til hefur aðeins 26 Vísitölur, þú vilt tryggja þinn modulusing svo að þú ekki run-- það er sama hlutur sem queue-- þinn svo að þú verðir ekki burt neðst kjötkássa virka. 

Þú vilt að vefja það til baka í kring á sama hátt í [inaudible] þegar þú hefðir eins og mjög, mjög stór bréf, þú vildi ekki sem að bara hlaupa burt enda. Sami hlutur hér, þú vilt tryggja það er ekki keyrt burt enda með umbúðir um til the toppur af the borð. Svo er þetta bara mjög einfalt kjötkássa virka. Allt sem gerði var að taka fyrsta bréf af hvaða inntak okkar var og snúa það inn í vísitölu sem við gætum sett inn kjötkássa borð okkar. 

Já, og svo eins og ég sagði áður, hvernig við að leysa árekstra í kjötkássa okkar borðum eru með, það sem við köllum, læsa. Þannig að ef þú reynir að setja margar orð sem byrja með það sama, þú ert að fara að hafa einn kjötkássa gildi. Avocados og epli, ef þú hefur keyra það í gegnum kjötkássa virka okkar, eru að fara að gefa þér Sama númer, fjöldi 0. Og svo hvernig við að leysa það er sem við getum í raun eins konar tengja þá saman í gegnum tengd listum. 

Og svo í þessum skilningi, þú krakkar geta séð svona um hvernig gögn uppbygging sem við höfum verið að setja áður eins og rúsínuís tengda listanum tagi af getur komið saman í eitt. Og þá er hægt að búa til langt skilvirkari gögn uppbygging sem ræður stærri magn af gögn, sem virk búa eftir á þörfum þínum. Allir ljóst? Allir konar skýr á hvað gerist hér? 

Ef ég vildi insert-- hvað er ávöxtur sem byrjar með, ég veit ekki, B, annað en berjum, banana. 

Áhorfendur: Blackberry. 

ANDI Peng: Blackberry, brómber. Hvar BlackBerry fara hér? Ja, reyndar höfum við ekki raðað þetta ennþá, en fræðilega ef við vildum hafa þetta í stafrófsröð, hvar ætti brómber fara? 

Áhorfendur: [inaudible] 

ANDI Peng: Einmitt, eftir hér, ekki satt? En þar sem það er mjög erfitt að reorder-- Ég giska á að það er allt að ykkur. Þú krakkar geta alveg framkvæma hvað sem þú vilt. The skilvirkari leið til að gera þetta kannski væri að raða tengd þína lista í stafrófsröð, og svo þegar þú ert setja hluti, sem þú vilt að vera viss um að setja þá í stafrófsröð þannig að þá þegar þú ert reyna að leita þá, þú þarft ekki að fara yfir allt. Þú veist nákvæmlega hvar það er, og það er auðveldara. 

En ef þú ert góður af það interspersed handahófi, þú ert enn að fara að hafa til að fara yfir það engu að síður. Og svo ef ég vildi bara setja BlackBerry hér og ég vildi til að leita að það, ég veit, ó, brómber verður að byrja með vísitölu 1, þannig að ég veit samstundis bara leita í 1. Og þá get ég svona fara yfir tengda listanum þar til ég fá að BlackBerry, og then-- já? 

Áhorfendur: Ef þú ert að reyna að create-- Ég held eins og þetta er mjög einfalt kjötkássa virka. Og ef við vildum gera mörg lög af þeim eins, OK, við viljum að skilja í eins og alla stafrófsröð bréfum og svo aftur að eins annan hóp af bókstöfum bréfum innan að, við erum að setja eins og kjötkássa borð innan kjötkássa borð, eða eins fall í falli? Eða er that-- 

ANDI Peng: Svo kjötkássa þinn function-- kjötkássa töflunni geta verið eins stór eins og þú vilt. Svo í þessum skilningi, ég hélt það var mjög auðvelt, mjög einfalt fyrir mig að bara svona miðað á stafina fyrsta orðið. Og svo er það bara 26 valkosti. Ég get bara 26 Options 0 til 25 vegna þess að þeir geta aðeins byrja frá A til Z. En ef þú vildir til að bæta við, kannski, meira flókið eða hraðar hlaupa tíma til þinn kjötkássa borð, þú algerlega getur gert alls konar hluti. Þú getur búið til þitt eigið Jafnan sem gefur þér meira dreifingu í þinn orð, svo þegar þú leitar, það er að fara að vera hraðari. 

Það er algjörlega undir ykkur hvernig þú vilt að framkvæma það. Hugsaðu um það eins og bara fötunum. Ef ég vildi hafa 26 fötunum, ég ætla að raða hlutum í þessum fötunum. En ég ætla að hafa fullt af efni í hverri fötu, þannig að ef þú vilt gera það hraðari og skilvirkari, láttu mig hafa hundrað fötunum. 

En þá verður þú að reikna út a leið til að raða hlutunum þannig að þeir eru í réttri fötu þeir ættu að vera í. En svo þegar þú í raun vilja til að líta á þessi fötu, það er mikið hraðar því það er minna efni í hverri fötu. Og svo, já, það er í raun bragð fyrir ykkur í pset5 er að þú munt vera áskorun að bara að búa hvað er skilvirkasta virka þú getur hugsa um að vera geta geymt og athuga þessi gildi. 

Algjörlega undir þér krakkar hvernig sem þú vilt gera það, en það er mjög góður punktur. Að hvers konar rökfræði þú langar að byrja að hugsa um er vel, af hverju get ég ekki gert fleiri fötur. Og þá verð ég að leita minna hluti, og þá kannski ég hafa mismunandi kjötkássa virka. 

Já, það er mikið af leiðir að gera þetta pset, sumir eru hraðar en aðrir. Ég er algerlega að fara að bara að sjá hvernig hratt var að festa þú krakkar vilja vera fær um að fá aðgerðir til að vinna. OK, allir gott á læsa og kjötkássa matskeið? Það er í raun eins og a mjög einfaldur hugmyndina ef þér finnst um það. Allt það er er aðskilnaður hvað inntak eru í fötunum, flokkun þeirra, og þá að leita að listi að það er í tengslum við. 

Cool. Allt í lagi, nú að við höfum mismunandi konar af gögn uppbygging sem er kallað tré. Við skulum fara á og tala um reynir sem eru greinilega mismunandi, en í sama flokki. Í meginatriðum, allt tré er staðinn skipuleggja gögn í línulega með að kjötkássa borð does-- þig veist, það er got a toppur og botn og þá tengja konar burt af it-- a tré hefur toppur sem þú kallar rót, og þá hefur það leyfi allt í kringum það. 

Og svo allt sem þú þarft hér er bara efst hnút sem bendir til annarra hnúður, að stig til fleiri hnúta, og svo framvegis og svo framvegis. Og svo þú verður bara skerandi útibú. Það er bara önnur leið til að skipuleggja gögn, og vegna þess að við köllum það tré, þið just-- það er bara byggð út til að líta út eins og tré. Þess vegna höfum við kalla það tré. 

Kjötkássa borð lítur út eins og borð. A tré lítur út eins og tré. Allt það er er sérstakt leið til að skipuleggja hnúta eftir því hvaða þarfir þínar eru. 

Þannig að þú hefur rót og þá verður þú fer. Leiðin sem við getum sérstaklega hugsa um það er tvöfaldur tré, tvöfaldur tré er bara ákveðin tegund af tré þar sem hver hnútur aðeins stig að, á max, tveir aðrir hnútar. Og svo hér hafa sérstakt Symmetry í tré sem gerir það auðveldara að eins konar líta á hvaða gildi þú ert því þá hafa alltaf vinstri eða hægri. Það er aldrei eins og vinstri þriðjung frá vinstri eða fjórða frá vinstri. Það er bara að þú ert með vinstri og hægri og þú getur leitað annað hvort af þessum tveimur. Og svo hvers vegna er þetta að gagni? Leiðin að þetta er gagnlegt er ef þú ert að leita að leita í gegnum gildi, ekki satt? Frekar en að innleiða tvöfaldur leita að villuboð fylki, ef þú vildir vera fær um að setja hnúta og taka í burtu hnúta að vild og einnig varðveita leit eiginleikar tvöfaldur leit. Svo á þennan hátt, við erum eins konar tricking-- man þegar við sagði tengd listum getur ekki tvöfaldur leit? Við erum konar skapa gögn uppbygging að bragðarefur sem í vinna. 

Og svo vegna þess að tengjast listar eru línuleg, þeir tengjast aðeins einn á eftir öðrum. Við getum konar hafa mismunandi tegund af ábendingum sem benda til mismunandi hnútar sem getur hjálpað okkur með leit. Og svo hér, ef ég vildi hafa tvíleitartré, Ég veit að miðja mína ef 55. Ég ætla bara að fara að búa til þessi eins miðja minn, sem rót mína, og þá er ég að fara að hafa gildi snúningur burt af því. 

Svo hér, ef ég ætla að leita að gildi 66, get ég byrjað á 55. Það er 66 meira en 55? Já það er, þannig að ég veit að ég Mus leita Ég n rétt bendi af þessu tré. Ég fer til 77. OK, er 66 minna en eða meiri en 77? Það er minna en, svo þú veist, ó, sem þarf að vera vinstri hnút. 

Og svo hér erum við að eins konar varðveita öllum mikill hlutur óður í fylki, svo eins dynamic resizing af hlutum, að vera fær um að setja og eyða að vild, án þess að þurfa að hafa áhyggjur óður í the fast pláss. Við varðveita enn allt þessir frábæra hluti en einnig að vera fær um að varðveita skrá þig inn og leita tíma tvöfaldur leit að við vorum aðeins áður fær til fá a setningu. 

Cool gögn uppbygging, góður af flókið að hrinda í framkvæmd, á hnút. Eins og þú geta sjá, allt það er struct hnútarins er að þú ert með vinstri og rétt bendi. Það er allt það er. Svo frekar en bara hafa X eða fyrri. Þú ert með vinstri eða hægri, og þá þú getur konar tengja þá saman en þú velur það. 

OK, við erum í raun að fara bara taka nokkrar mínútur. Þannig að við erum að fara að fara aftur hingað. Eins og ég sagði áður, Ég útskýrði konar The rökfræði á bak hvernig við myndi leita í gegnum þetta. Við ætlum að reyna pseudocoding þetta út til að sjá ef við getum konar beita Sama rökfræði tvöfaldur leit til annars konar gögn uppbygging. Ef þú krakkar vilja til að taka eins og a par mínútur til að hugsa bara um þetta. OK. Allt í lagi, ég ætla að reyndar bara gefa þér the-- nei, við munum tala um sauðakóðanum fyrst. Svo er einhver að vilja að gefa stunga á það The fyrstur hlutur þú vilt gera þegar þú ert að byrja út rannsakandi er? Ef við erum að leita að gildi 66, hvað er The fyrstur hlutur sem við viljum gera ef við viljum Tvíundarleit þetta tré? 

Áhorfendur: Þú vilt að líta til hægri og líta til vinstri og sjá [inaudible] meiri fjöldi. 

ANDI Peng: Já, einmitt. Svo þú ert að fara að horfa á rót þína. Það er hellingur af leiðum sem þú getur hringt í það, segja foreldri hnút þinn lýður. Ég segi rót vegna það er eins og rót trésins. Þú ert að fara að horfa á rót hnút, og þú ert fara að sjá er 66 meiri en eða minna en 55. Og ef það er meira en vel, það er meiri en þar viljum við líta út? Hvar viljum við leita nú, ekki satt? Við viljum leita að hægri helminginn af þessu tré. 

Þannig að við höfum, þægilegur, a músina sem bendir til hægri. Og svo þá getum við stillt Ný rót okkar til að vera 77. Við getum bara farið að þar bendillinn er að benda. Jæja, ó, hér erum við að byrja á 77, og við getum bara að gera þetta endurkvæmur aftur og aftur. Á þennan hátt, þú góður af hafa virka. Þú hafa a vegur til að leita að þér getur bara endurtaka aftur og aftur og aftur, eftir því hvar þú vilt að líta þar til þú færð að lokum að verðmæti sem þú ert að leita að. Meikar sens? 

Ég er að fara að sýna þér í raun númer og það er mikið af kóða. Engin þörf á að Freak út. Við munum tala um það. 

Reyndar ekki. Það var bara sauðakóðanum. OK, það var bara sauðakóðanum, sem er dálítið flókið, en það er alveg í lagi. Allir fylgja eftir hér? Ef rótin er null, aftur rangar því það þýðir að þú þarft ekki einu sinni neitt þar. 

Ef rót n er gildi, þannig að ef það gerist að vera sá sem þú ert að leita á, þá þú ert að fara að fara aftur satt vegna þess að þú veist að þú fannst það. En ef gildið er minna en rót n, þú ert að fara að leita á vinstri barn eða vinstri blaða, hvað sem þú vilt kalla það. Og ef gildið er hærra en rót, þú ert að fara að leita á rétta tré, þá bara að keyra aðgerðina gegnum leit aftur. 

Og ef rótin er null, sem að þýðir að þú hefur náð í lok? Það þýðir að þú þarft ekki meira meira lauf til að leita, þá þú veist, ó, ég giska á að það er ekki hér því eftir að ég hef horft í gegnum the heild hlutur og það er ekki hér, það bara gæti ekki verið hér. 

Er að skynsamleg að allir? Svo það er eins og tvöfaldur leit varðveita getu tengd listum. Cool, og svo önnur tegund gagnagrindarinnar þú krakkar geta reyna að innleiða á pset þinn, þú þarft bara að velja eina aðferð. En kannski aðra aðferð til að kjötkássa borð er það sem við köllum Trie. 

Allt a Trie er er ákveðin tegund af tré sem hefur gildi sem fara til annarra gilda. Svo í stað þess að hafa tvöfaldur tré í þeim skilningi að aðeins einn hlutur getur bent til tvo, getur þú eitt í marga marga hluti. Þú hefur í raun fylki inni sem þú geymir ábendingar sem benda á aðrar fylki. 

Svo hnúturinn hvernig við myndi skilgreina Trie er að við viljum hafa Boolean, c orð, ekki satt? Svo er hnúturinn Boolean eins satt eða ósatt, fyrst af öllu á höfuð sem array, er þetta orð? Í öðru lagi, þú vilt hafa ábendingum til hvað restin af þeim eru. A hluti flókið, dálítið ágrip, en Ég mun útskýra hvað það alla leið. 

Svo hér efst, ef þú hafa fylki lýst þegar, hnút þar sem þú ert með Boolean gildi sem geymt er að framan sem segir þér er þetta orð? Er þetta ekki orð? Og þá verður þú að restin af array þinn sem reyndar geymir allar möguleikar á því hvað það gæti verið. Svo, til dæmis, eins og efst sem þú þarft The fyrstur hlutur sem segir satt eða rangar, já eða nei, þetta er orð. 

Og þá verður þú 0 gegnum 26 stafina sem þú getur geymt. Ef ég vildi að leita hér fyrir kylfu, fer ég á toppinn og ég leita að B. Mér finnst B í mínu array, og þannig að ég veit, OK, er B orð? B er ekki orð, svo þannig Ég verð að halda áfram að leita. Ég fer frá B, og ég lít til músina sem B bendir til og ég sé annar fylking af upplýsingum, sama uppbygging sem við höfðum áður. 

Og here-- ó, næsta bréf í [inaudible] er A. Svo við lítum í því fylki. Við finnum áttunda gildi, og þá erum við að líta til að sjá, ó, hey, er að orði, er B-A orð? Það er ekki orð. Við verðum að halda að leita. 

Og svo þá við lítum til þar bendillinn af A stig, og það bendir til annars hátt í sem við höfum meira virði geymd. Og að lokum fáum við að B-A-T, sem er orð. Og svo næst þegar þú lítur, þú ert að fara að hafa þessi athugun á, já, þetta Boolean virka er satt. Og svo í þeim skilningi sem við erum góður um að hafa tré með fylki. 

Svo þá getur þú konar leita niður. Frekar en hass fall og Úthlutun gildi eftir tengda listanum, þú getur bara innleiða Trie sem leitar downwords. Virkilega, virkilega flókið efni. Ekki auðvelt að hugsa um vegna þess að ég er eins spúandi svo mörg gögn uppbygging út á þig, en ekki allir góður af skilja hvernig röksemdafærsla þetta virkar? 

OK, flott. Svo B-A-T, og þá þú ert að fara að leita. Í næsta skipti sem þú ert að fara að sjá, ó, hey, það er satt, þannig ég veit að þetta verður að vera orðið. 

Sama fyrir dýragarðinum. Svo hér er hlutur núna, ef við langaði til að leita að dýragarðinum, núna, nú dýragarðinum er ekki Bæta í orðabókina okkar vegna þess, eins og þú krakkar geta sjá, Fyrsti staðurinn sem við höfum Boolean return true er í lok zoom. Við höfum Z-O-O-M. 

Og svo hér, að við í raun ekki hafa orðið, dýragarðinum, orðabók okkar vegna þess að þetta kassann er ekki valinn. Þannig að tölvan er ekki veit að dýragarðinum er orð vegna þess að leiðin sem við höfum geyma það, bara zoom hér í raun hefur Boolean gildi sem hefur verið breytt satt. Svo ef við viljum setja orð, dýragarðinum, í orðabókina okkar, hvernig myndum við fara að gera það? Hvað höfum við að gera til að tryggja okkar tölva veit að Z-O-O er orð en ekki fyrsti orðið er Z-O-O-M? 

Áhorfendur: [inaudible] 

ANDI Peng: Einmitt, við vilja til að ganga úr skugga um að þetta hér, að Boolean gildi er köflóttur burt að það er satt. Z-O-O, þá erum við að fara að athuga það, þannig að við vitum nákvæmlega, hey, dýragarðinum er orð. Ég ætla að segja að tölva sem það er orð svo að þegar tölva eftirlit, það veit að dýragarðinum er orð. 

Vegna muna öll þessi gögn mannvirki, það er mjög auðvelt fyrir okkur að segja, ó, kylfu er orð. Zoo er orð. Zoom er orð. En þegar þú ert að byggja það, tölvan hefur ekki hugmynd. 

Svo þú ert að segja það nákvæmlega á hvaða tímapunkti er þetta orð? Á hvaða tímapunkti er það ekki orð? Og á hvaða stað gera I þurfa að leita hluti, og á hvaða tímapunkti þarf ég að fara næst? Allir ljóst af því? Cool. 

Og svo kemur þá vandamálið um hvernig myndum við fara um að setja eitthvað það er í raun ekki þar? Svo við skulum bara segja að við viljum að setja orðið, bað, í Trie okkar. Eins og þú krakkar geta séð eins nú allt sem við höfum nú er B-A-T, og þetta nýja gögn uppbygging það hafði matast sem benti null vegna þess að við gerum ráð fyrir sem, ó, það er ekki til orð eftir B-A-T, hvers vegna þurfum við að halda hafa það eftir að T. 

En vandamálið kemur ef við gerum þér langar að hafa orð sem kemur á eftir T er. Ef þú ert með bað, þú ert að fara að vilja til H rétt. Og svo hvernig við erum að fara að gera það er við erum að fara að búa til aðskilda hnút. Við erum ekki úthluta hvaða upphæð minni fyrir þetta nýja fylki, og við erum að fara að endurúthluta ábendingum. 

Við erum að fara að framselja H, Fyrst af öllu, þetta null, við erum að fara að losna við. Við erum að fara að hafa H-punkturinn niður. Ef við sjáum H, viljum við það að fara í eitthvað annað. 

Hér, getum við þá skrá sig já. Ef við högg H eftir T, ó, þá vitum við að þetta er orðið. The Boolean er að fara að skila satt. Allir skýrt hvernig það gerðist? OK. 

Svo í raun, ekki minna en þessi gögn uppbygging sem við höfum farið yfir í dag, hef ég farið yfir þá virkilega, virkilega hratt og ekki í of mikið smáatriði, og það er allt í lagi. Þegar þú byrjar að fíflast með það, verður þú að vera halda utan um hvar allar ábendingar eru, hvað er að gerast í þínu gögn uppbygging, et cetera. Þeir ætla að vera mjög gagnlegt, og það er komið að þér krakkar að algerlega reikna út hvernig þú vilt að framkvæma hlutina. 

Og svo pset4, af 5-- ó, sem er rangt. Pset5 er stafsetningarvillur. Eins og ég sagði áður, þú ert að fara að, þegar aftur, sækja kóðann frá okkur. Það er að fara að vera þrjár helstu hlutir sem þú verður að sækja. Þú munt sækja orðabækur, porto, og textar. 

Allir þessir hlutir eru eru annaðhvort orðabækur af orðum að við viljum að þú að athuga eða próf upplýsinga að við viljum að þú leiðréttingar. Og svo orðabækur við gefum þú ert að fara til að gefa þér raunverulegt orð sem við viljum þér að geyma einhvern veginn á þann hátt sem er skilvirkari en fylki. Og þá textarnir eru að fara að vera það sem við erum biðja þig að stafa athuga til að tryggja öll orð eru alvöru orð. 

Og svo þrjár blokkir af forrit sem við munum gefa þér eru kallaðir dictionary.c, dictionary.h og speller.c. Og svo er allt dictionary.c er það sem þú ert beðinn um að hrinda í framkvæmd. Það sækir orð. Það leiðréttingar Eftirlit þá, og það gerir viss að allt sitji rétt. 

diction.h er bara bókasafn skrá sem lýsir alla þá virka. Og speller.c, við erum að fara að gefa þér. Þú þarft ekki að breyta einhverju af því. Allt speller.c gerir er að taka það, hleðst það, tékka hraða henni, prófar viðmið um eins og hvernig fljótt þú ert fær um að gera hlutina. 

Það er Speller. Bara ekki skipta sér af því, en gera viss um að þú skiljir hvað það er að gera. Við notum virka heitir getrusage að próf árangur stafsetningu þína afgreiðslumaður. Allt það gerir er í grundvallaratriðum prófa tími allt í orðabókina þína, svo vertu viss um að þú skiljir það. Verið varkár að ekki skipta sér af því eða aðrir eru það ekki keyra almennilega. 

Og megnið af þessu verkefni er að þið virkilega breyta dictionary.c. Við erum að fara að gefa þér 140.000 orð í orðabókinni. Við erum að fara að gefa þér texta skrá sem er þessi orð, og við viljum að þú að vera fær um að skipuleggja þá í kjötkássa töflunni eða Trie vegna þess að þegar við biðjum þig að stafa check-- ímynda sér ef þú ert stafsetningu stöðva eins Ódysseifskviðu Hómers. Það er eins og þetta mikla, mikla próf. 

Ímyndaðu þér ef hvert einasta Bæta þú þurfti að leita gegnum fjölda 140.000 gildi. Það myndi taka að eilífu fyrir vélina þína til að keyra. Það er þess vegna viljum við að skipuleggja okkar gögn í skilvirkari gögn uppbygging svo sem kjötkássa töflunni eða Trie. Og þá þú krakkar geta konar um þegar þú leitar aðgang það auðveldara og hraðar. 

Og svo að gæta þess að leysa árekstra. Þú ert að fara að fá fullt af orðum sem byrja á A. Þú ert að fara að fá fullt orð að byrja með B. Upp til þín krakkar hvernig þú vilt að leysa það. Kannski er það meira duglegur kjötkássa virka en bara fyrsta stafinn í eitthvað, og svo er það undir þér komið krakkar að konar gera hvað sem þú vilt. 

Kannski þú vilt bæta við allir stafir saman. Kannski þú vilt eins gera undarlegt hluti til reikning fjölda bréfa, hvað sem er. Allt að ykkur hvernig þú vilt gera. Ef þú vilt gera kjötkássa borð, ef þú viljir Trie, algjörlega undir þér komið. Ég mun vara þig fyrirfram að við Trie er yfirleitt svolítið erfiðara bara vegna þess að það er mikið fleiri ábendingar til að halda utan um. En algerlega allt að ykkur. Það er mun skilvirkari í flestum tilvikum. Þú vilt virkilega að vera fær um að halda utan um öll ábendingum þínum. Eins gera það sama sem ég var að gera hér. Þegar þú ert að reyna að setja inn gildi í kjötkássa töflunni eða eyða, ganga úr skugga um að þú ert virkilega að halda utan af þar sem allt er vegna það er mjög auðvelt fyrir ef ég er reyna að setja eins og orðið, Andy. Segjum bara það er alvöru orð, orð, Andy, í risa listi af orðum. 

Ef ég gerist bara að endurúthluta bendi rangt, oops, það fer í heild sinni restin af tengda listanum mínum. Nú er bara orðið sem ég hafa er Andy, og nú alla aðra orð í orðabók hefur rofnað. Og svo þú vilt tryggja að þú halda utan um allar ábendingum þínum eða annað sem þú ert að fara að fá mikið vandamál í kóðann þinn. Draga það út vandlega skref fyrir skref. Það gerir það mun auðveldara að hugsa um. 

Og loks, þú vilja til vera fær til að prófa árangur af forritinu á stóra borð. Ef þið taka líta á CS50 núna, við höfum það sem er kallað stór borð. Það er leikskýrslu af the festa villuleit sinnum yfir alla CS50 núna, ég held að ofan eins og 10 oft ég held átta af þeim eru starfsmenn. Við viljum virkilega að þú krakkar að berja okkur. 

Allar okkar voru að reyna að hrinda í framkvæmd the festa kóða og mögulegt er. Við viljum að þú krakkar að reyna að skora okkur og framkvæma hraðar en okkur getur. Og svo er þetta virkilega í fyrsta skipti sem við erum biðja ykkur að gera pset sem þú getur í raun gert í hvaða aðferð þú vilt. 

Ég segi alltaf, þetta er meira í ætt til raunveruleikanum lausn, ekki satt? Ég segi, hey, þarf ég að gera þetta. Byggja upp forrit sem gerir þetta fyrir mig. Gera það hvernig sem þú vilt. Ég veit bara að ég vil að fasta. Það er áskorun fyrir þessa viku. Þú krakkar, við erum að fara að gefa þér verkefni. Við erum að fara að gefa þér áskorun. Og þá er komið að ykkur alveg bara reikna út hvað er fljótlegasta og Skilvirkasta leiðin til að framkvæma þetta. Já? 

Áhorfendur: Erum við leyft að ef vildi að rannsaka hraðar leiðir að gera kjötkássa matskeið á netinu, getum við gert sem og vitnað kóða einhvers annars? ANDI Peng: Já, algerlega í lagi. Svo ef þið lesið sérstakur, það er lína í sérstakur sem segir ykkur eru algerlega frjáls til rannsókna kjötkássa virka á hvaða ert sumir af hraðari kjötkássa virka til að keyra það í gegnum eins lengi sem þú vitnað þessi númer. Svo sumir hafa nú þegar mynstrağur út hratt leiðir um að gera afgreiðslukassa stafa, af hratt leiðir til að geyma upplýsingar. Algjörlega undir ykkur ef þig vil bara taka það, ekki satt? Gakktu úr skugga um að þú ert að vitna. Áskorunin hér mjög sem við erum að reyna að prófa er að tryggja að þú veist leið um ábendingum. Eins og langt eins og þú innleiða raunverulegt kjötkássa virka og koma upp með eins stærðfræði til að gera það, þú krakkar geta rannsóknir hvað aðferðir á netinu þú krakkar vilja. Já? 

Áhorfendur: Getum við vitna bara með því að nota [inaudible]? 

ANDI Peng: Já. Þú getur bara, í athugasemd, þú getur vitnað eins, ó, tekið úr Yada, blaðrið, BLA, kjötkássa virka. Einhver hefur einhverjar spurningar? Við breezed raun gegnum kafla í dag. Ég mun vera hérna til svara spurningum eins og heilbrigður. 

Einnig, eins og ég sagði, skrifstofa klst í kvöld og á morgun. The sérstakur í þessari viku er í raun frábær auðvelt og frábær stutt til að lesa. Ég myndi stinga upp á að taka a líta, bara Lesið heild af því. 

Og Zamyla gengur í raun þér í gegnum hvert af þeim störfum þú þarft að framkvæma, og svo er það mjög, mjög ljóst hvernig á að gera allt. Bara til að tryggja að þú ert halda utan um ábendingum. Þetta er mjög krefjandi pset. 

Það er ekki erfitt vegna þess eins, ó, eru hugtök svo miklu meira erfitt, eða þú þarft að læra svo mikið nýtt setningafræði leið sem þú gerðir fyrir síðustu pset. Þetta pset er erfitt vegna þess að það eru svo margir ábendingum, og þá er það mjög, mjög auðvelt að einu sinni þú ert með galla í kóðanum þínum ekki vera fær að finna hvar sem villan er. 

Og svo heill og mæli trú á þér krakkar að vera fær um að slá okkar [inaudible] stafsetning. Ég hef reyndar ekki allir skrifað mitt enn, en ég ætla að fara að skrifa mitt. Svo á meðan þú ert að skrifa þitt, ég ætla að skrifa mitt. Ég ætla að reyna að gera minn hraðar en þinn. Við munum sjá hver hefur hraðast einn. 

Og já, ég mun sjá öll þið hér á þriðjudag. Ég mun keyra eins konar eins og pset verkstæði. Allar dæmatímum þessa viku eru pset námskeið, svo þú krakkar hafa fullt af tækifærum um hjálp, viðtalstímar eins og alltaf, og ég hlakka til að lesa allt af kóðanum þínum krakkar. Ég hef Skyndipróf upp hér ef þú krakkar vilja til að koma fá þá. Það er allt og sumt.