[Tónlist spila] Ræðumaður 1: Allt í lagi. Allir velkomnir aftur til kafla. Ég vona að þú allur ert tókst batna frá prófið frá síðustu viku. Ég veit að það er svolítið brjálaður stundum. Eins og ég var að segja áður, ef þú ert innan staðalfráviks, raun ekki hafa áhyggjur óður í það, sérstaklega fyrir minna þægilegt kafla. Það er um hvar þú ættir að vera. Ef þú gerðir vel, þá ógnvekjandi. Kudos til þín. Og ef þér finnst eins og þú þarft svolítið meira hjálp, vinsamlegast ekki hika við að ná út einhverju TFS. Við erum öll hér til að hjálpa. 

Þess vegna við kennum. Þess vegna er ég hér á hverjum mánudegi fyrir þig krakkar og á skrifstofutíma á fimmtudögum. Svo skaltu ekki hika við að láta mig vita Ef þú ert að hafa áhyggjur neitt eða ef það er eitthvað á spurningakeppni að þú vilt virkilega til að takast á við. 

Svo er dagskrá fyrir daginn í dag allt um uppbyggingu gagna. Sumir af þessir ert bara að fara að vera bara til að fá þig kynnt með þessum. Þú getur ekki alltaf framkvæma þá í þessum flokki. Sumir af þeim sem þú verður, eins og fyrir Speller pset þinn. 

Þú munt hafa val þitt milli hash borðum og reynir. Svo við munum örugglega vera að fara yfir þær. Það er að fara að vera ákveðið meira af tagi af háu stigi kafla í dag, þó, vegna þess að það er mikið af þeim, og ef fórum inn í framkvæmd smáatriði á öllum þessum, myndum við ekki jafnvel komast í gegnum tengd listum og kannski smá kjötkássa matskeið. 

Svo bera með mér. Við erum ekki að fara að vera að gera eins mikið kóðun þetta sinn. Ef þú hefur einhverjar spurningar um það eða ef þú vilt sjá það framkvæmda eða reyna það fyrir þig, Ég mæli með ákveðið fara að study.cs50.net sem hefur dæmi um allar þessar. Það verður PowerPoints mínar með skýringum sem við hafa tilhneigingu til að nota sem og sumir forritun æfingar, sérstaklega fyrir hluti eins tengd listum og tvöfaldur tré stafla og Cues. Svo lítið meira mikil, sem gæti verið gott fyrir ykkur. 

Svo með það, munum við byrja. Og einnig, yes-- Skyndipróf. Ég held að flest ykkar sem eru í kafla minn hefur Skyndipróf þínum, en einhver kemur inn eða sumir ástæða þú gera ekki, þeir eru hérna í framan. 

Svo tengd listum. Ég veit svona af fer til baka áður prófið. Það var viku fyrir að við lærðum um þetta. En í þessu tilfelli, við verðum bara fara svolítið meira í dýpt. 

Svo hvers vegna gætum við valið tengd lista yfir fjölda? Hvað aðgreinir þá? Já? 

Áhorfendur: Þú getur aukið tengdur lista móti fasta stærð fylki er. Ræðumaður 1: Hægri. An array hefur fasta stærð en a tengda listanum hefur breytilega stærð. Þannig að ef við vitum ekki hvernig mikið við viljum til að geyma, tengdur listi gefur okkur a mikill leiðin til að gera það vegna þess að við getum bara bæta við á annan hnút og bæta við á annar hnútur og bæta á annan hnút. En hvað gæti verið málamiðlun? Hefur einhver man málamiðlun milli fylki og tengist listum? Mmhmm? 

Áhorfendur: Þú þarft að fara í gegnum alla leið gegnum tengda listanum finna stak í lista. Í fylki, þú getur bara finna stak. 

Ræðumaður 1: Hægri. Svo með arrays-- 

Áhorfendur: [inaudible]. 

Ræðumaður 1: Með fylki, höfum við hvað heitir handahófi aðgang. Þýðir að ef við viljum það sem er alltaf fimmta lið af lista eða fimmta lið af okkar array, getum við bara grípa það. Ef það er tengda listanum, við höfum að iterate gegnum, ekki satt? Svo aðgang stak í fylki er fasti tími, en með tengda listanum það myndi líklegast vera línuleg tími því kannski þáttur okkar er alla leið á enda. Við verðum að leita í gegnum allt. Svo með öllum þessum gögnum mannvirki sem við ætlum til að eyða aðeins meiri tíma í, hvað eru plús-merkjum og neikvæður. Hvenær gætum við viljum nota einn yfir öðrum? Og það er góður af stærri hlutur að taka í burtu. 

Þannig að við höfum hér skilgreining á hnút. Það er eins og einn þáttur í tengda listanum okkar, ekki satt? Þannig að við erum öll kunnugur með typedef structs okkar, sem við fórum yfir í endurskoðun á síðasta tíma. Það var í rauninni bara að búa annars gögn tegund sem við gætum notað. 

Og í þessu tilfelli, er það sumir hnút sem mun halda einhverja heiltölu í. Og þá er það seinni hluti hér? Einhver? 

Áhorfendur: [inaudible]. 

Ræðumaður 1: Já. Það er bendi á næsta hnút. Þannig að þetta ætti í raun að vera hérna. Þetta er bendi af tegund hnút í næsta hlutur. Og það er það sem þeir nær hnút okkar. Cool. 

Allt í lagi, svo við leit, eins og við vorum bara að segja áður en hendi, ef þú ert að fara að leita í gegnum, þú þarft að raunverulega kunnugt gegnum tengda listanum þínum. Þannig að ef við erum að leita fyrir fjölda 9, myndum við byrja á höfði okkar og það bendir okkur á upphafi af tengda listanum okkar, ekki satt? Og við segjum, OK, er þetta hnút innihalda númer 9? Nei? 

Allt í lagi, fara til the næstur einn. Fylgja henni. Hefur það að geyma númer 9? No. Fylgdu næstu einn. 

Þannig að við höfum í raun og veru kunnugt gegnum tengda listanum okkar. Við getum ekki bara fara beint til þar 9 er. Og ef þú krakkar vilja í raun að sjá nokkrar gervi-númer þarna. Við höfum einhverja leit virka hér sem tekur in-- hvað tekur það inn? Hvað finnst þér? Svo auðvelt einn. Hvað er þetta? Áhorfendur: [inaudible]. Ræðumaður 1: Fjöldi við erum að leita að. Hægri? Og hvað myndi þetta samsvara? Það er bendi til? 

Áhorfendur: A hnútur. 

Ræðumaður 1: A hnútur á listann að við erum að horfa á, ekki satt? Þannig að við höfum sumir hnútar eru bendi hér. Þetta er lið sem er að fara til reyndar iterate gegnum listann okkar. Við setjum það jafnt að skrá því það er bara stilling það jafnt við byrja á tengda listanum okkar. 

Og meðan það er ekki NULL, en við höfum enn hluti á listanum okkar, athuga hvort þessi hnútur hefur fjöldi sem við erum að leita að. Return true. Annars, endurnýja það, ekki satt? 

Ef það er NULL, við hætta okkar meðan lykkja og return false því það þýðir að við höfum ekki fundið það. Þurfa allir fá hvernig það virkar? OK. 

Svo með innsetning, þú hafa þrjú mismunandi vegu. Þú getur prepend, getur þú bæta og þú getur sett inn í blandað. Í þessu tilviki, við erum fara að gera prepend. Hefur einhver veit hvernig þeim þrjú tilfelli verið mismunandi? 

Svo prepend þýðir að þú setur það framan á listanum þínum. Svo sem myndi þýða að það er sama hvaða hnút er, sama hvaða gildi er, ert þú að fara til að setja það hérna fyrir framan, OK? Það er að fara til vera the fyrstur þáttur í listanum þínum. 

Ef þú bæta það, það er að fara að fara á bak við listann. Og settu inn blandað þýðir að þú ert að fara að setja í raun í stað þar sem það heldur tengda listanum þínum raðað. Aftur, hvernig þú notar þá og þegar þú notar þá er breytilegt eftir þínu tilviki. Ef það þarf ekki að vera flokkaður, prepend tilhneigingu að vera það sem flestir nota vegna þess að þú ert ekki þarft að fara í gegnum allt listann að finna enda til að bæta það á, ekki satt? Þú getur bara halda það rétt í. 

Þannig að við munum fara í gegnum innsetningu 1 núna. Svo eitt sem ég ætla að mjög mæla á þessari pset er að draga það út, eins og alltaf. Það er mjög mikilvægt að þú uppfærir ábendingum þínum í réttri röð því ef þú uppfærir þá örlítið út af röð, þú ert að fara að enda tapa hluta listann. 

Svo til dæmis, í þessu tilfelli, við erum segja höfuðið bara benda til 1. Ef við gerum bara það án þess að vista þetta 1, við höfum ekki hugmynd um hvað 1 ætti að benda til nú vegna þess að við höfum misst það höfuð benti til. Svo eitt að muna þegar þú ert að gera a prepend er að bjarga því sem við höfuð benda til fyrsta, þá breyta henni, og þá uppfæra hvaða nýja hnút ætti benda á. Í þessu tilviki, þetta er ein leiðin til að gera það. 

Þannig að ef við hefðum gert það með þessum hætti þar sem við færður bara höfðinu, við missa grundvallaratriðum OKKAR öllum listanum, ekki satt? Ein leið til að gera það er að hafa 1 stig til næst, og þá hafa höfuð benda til 1. Eða þú getur gert góður af eins og tímabundin geymsla, sem ég talaði um. 

En reassigning ÞINN ábendingum í réttri röð er að fara að vera mjög, mjög mikilvægt fyrir þessa pset. Annars, þú ert að fara að hafa kjötkássa borð eða a reyna það er bara að fara að vera aðeins hluti af þeim orðum sem þú vilja og þá mmhmm you're--? Áhorfendur: Hvað var tímabundin geymsla sem þú varst að tala um? Ræðumaður 1: tímabundna geymslu. Svo í rauninni annað leiðin sem þú gætir gert þetta er geyma höfuð eitthvað, eins geyma það sem tímabundna breytu. Framselja það til 1 og uppfærðu síðan 1 til að benda til hvað höfuð notuð til að benda á. This vegur er augljóslega glæsilegur vegna þess að þú þurfa ekki tímabundið gildi, en bara bjóða aðra leið til að gera það. Og við gerum í raun hafa nokkur númer fyrir þetta. Svo fyrir tengda listanum, við raun hafa nokkur númer. Svo setja hér, þetta er prepending. Svo fer þetta það á höfuðið. 

Svo fyrsta sem þú þarft að búa til nýtt hnút þína, auðvitað, og athuga NÚLL. Alltaf gott. Og þá þú þarft að tengja gildin. Alltaf þegar þú býrð til nýja hnút, þú veit ekki hvað það er að vísa á næsta, svo þú vilt að frumstilla það að null. Ef það er á endanum sem bendir á eitthvað annars fær það færður og það er fínt. Ef það er það fyrsta sem á listanum, það þarf að benda á NÚLL því það er aftast í listanum. 

Svo þá á að setja það, sjáum við hér við eru framselja næsta gildi hnút okkar að vera hvað sem höfuð er, sem er það sem við höfðum hér. Það er það sem við gerðum rétt. Og svo við erum að framselja höfuð til lið á nýja hnút okkar, vegna muna, nýja er einhver bendi til hnút, og það er einmitt það sem höfuð er. Það er einmitt þess vegna sem við hafa þetta ör aukahlutir. Cool? Mmhmm? 

Áhorfendur: eigum við að frumstilla nýja Next til NULL fyrst, eða getum við frumstilla bara það að höfuð? 

Ræðumaður 1: New Næsta þarf að vera NULL til að byrja vegna þess að þú veist ekki þar sem það er að fara til vera. Einnig er þetta eins konar bara eins og fyrirmynd. Þú stillir það jafn NÚLL bara að gera viss um að allir bækistöðvar þínar falla áður en þú gerir einhverjar reassignment svo að þú ert alltaf að tryggja að það mun vera að benda á ákveðna gildi móti eins og sorp gildi. Vegna þess, já, við gefum nýtt næst sjálfkrafa, en það er meira bara eins og a gott að frumstilla hana á þann hátt og svo endurúthluta. 

OK, svo tvöfalt tengd listum núna. Hvað eigum við held? Hvað er öðruvísi við tvöfalt tengd listum? 

Svo í tengdum listum okkar, getum við aðeins fara í eina átt, ekki satt? Við höfum aðeins næst. Við getum aðeins farið fram. 

Með tvöfalt tengist lista, getum einnig færa aftur á bak. Þannig að við höfum ekki aðeins númer sem við viljum geyma, við höfum þar sem það bendir til næsta og þar sem við kom bara frá. Svo gerir þetta fyrir sumir betri traversal. 

Svo tvöfalt tengdra hnúður, mjög svipuð, ekki satt? Aðeins er munur nú við hafa næsta og fyrri. Það er eini munurinn. 

Þannig að ef við værum að prepend eða append-- við ekki hafa allir kóðann fyrir þetta upp here-- en ef þú varst að reyna að settu það skiptir mestu er sem þú þarft að gera viss um að þú ert að framselja bæði fyrri og þinn næsta bendi rétt. Svo í þessu tilfelli, þú vildi ekki aðeins frumstilla næst, þú frumstilla fyrri. Ef við erum í forsvari fyrir listann, við myndi ekki aðeins gera höfuð jafn ný, en ný fyrri okkar ætti benda til höfuðs, ekki satt? 

Það er eini munurinn. Og ef þú vilt meira starf með þessir með tengd listum, með því að setja, með eyða með innskoti inn Fjölbreyttir lista, Vinsamlegast kíkja study.cs50.net. There er a búnt af frábærum æfingum. Ég mæli þá. Ég vildi að við hefðum tíma til að fara í gegnum þá en það er a einhver fjöldi af gögn uppbygging að komast í gegnum. 

OK, svo kjötkássa matskeið. Þetta er sennilega mest gagnlegur hluti fyrir pset þína hér vegna þess að þú ert að fara til vera koma einhverjum af þessum, eða reyna. Mér finnst virkilega kjötkássa matskeið. Þeir eru ansi kaldur. 

Svo í grundvallaratriðum hvað gerist er kjötkássa borð er þegar við þurfum virkilega skjótur innsetning, eyðingu, og útlit. Þeir eru það sem við ert forgangsraða í kjötkássa töflunni. Þeir geta fengið nokkuð stór, En eins og við munum sjá með reynir, það eru hlutir sem eru miklu stærri. 

En í grundvallaratriðum, allir a kjötkássa tafla er a kjötkássa virka sem segir þér hvaða fötu til að setja hvert af gögnunum, hvert þætti þína í. Einföld leið til að hugsa um kjötkássa borð er að það er bara fötunum af hlutum, ekki satt? Svo þegar þú ert að flokka hluti eftir eins og fyrsta staf í nafni þeirra, það er góður af eins og a kjötkássa töflunni. 

Svo ef ég væri í hóp sem þú krakkar eru í hópa af hver heitir byrjar með A hérna, eða sá er afmæli er í janúar, febrúar, mars, hvað sem, sem er í raun skapa kjötkássa töflunni. Það er bara að búa fötunum sem þú flokkað þætti inn þannig að þú getur fundið þá auðveldara. Svo Þannig þegar ég þarf að finna einn af þér, Ég þarf ekki að leita gegnum hvert nöfn. Ég get verið eins og, ó, ég veit að Afmæli Danielle er in-- Áhorfendur: --April. Ræðumaður 1: apríl. Svo ég lít í apríl minn fötu, og með hvaða heppni, hún verður að vera sú eina þar og tími minn var stöðug í þeim skilningi, en ef ég þarf að leita gegnum allt fullt af fólki, það er að fara að taka mikið lengur. Svo kjötkássa matskeið eru raunverulega aðeins fötunum. Auðveld leið til að hugsa um þau. 

Svo mjög mikilvægur hlutur óður tæti tafla er kjötkássa virka. Svo það sem ég talaði bara um eins og Fyrsta bréf af fornafni eða mánuður afmæli, þetta eru hugmyndir sem virkilega samsvarað kjötkássa virka. Það er bara leið til að ákveða hvaða Bucket þú þáttur ert fer í, OK? Svo fyrir þetta pset, getur þú lítur upp laglegur mikill allir kjötkássa virka þú vilt. 

Þarf ekki að vera þinn eigin. There ert sumir raunverulega kaldur sjálfur út þar sem gera alls konar brjálaður stærðfræði. Og ef þú vilt að gera þinn Villupúki frábær fljótur, Ég myndi örugglega líta inn í einn af þeim. 

En það eru einnig einföld sjálfur, eins óendanlegur samtala orðum, eins hvert bréf hefur a tala. Reiknið summu. Sem ákvarðar fötu. Þeir hafa einnig auðvelt sjálfur sem eru bara eins og alla A er hér, öllum B er hér. Einhverjum þeirra. 

Grundvallaratriðum, segir það bara þér sem array vísitölu þáttur þinn ætti að fara inn. Bara ákveða bucket-- það er allt a kjötkássa virka er. Svo hér höfum við dæmi sem er bara fyrsti stafur strengsins að ég var bara að tala um. 

Svo þú hefur einhverja summu sem er bara Fyrsta bréf band mínus þinn A, sem mun gefa þér nokkra tala á milli 0 og 25. Og hvað sem þú vilt gera er ganga úr skugga um að þetta táknar stærð hash þínum table-- hversu margir fötunum eru. Með mörgum af þessum kjötkássa virka, þá eru þeir fara að vera aftur gildi sem gæti vera langt yfir fjölda fötunum að þú hefur í raun í kjötkássa töflunni, svo þú þarft að gera viss og unga fólkið af þeim. Annars er það að fara að segja, ó, ætti það að vera í fötu 5000 en þú hefur aðeins 30 fötunum í kjötkássa töflunni. Og auðvitað, við vitum öll að er að fara að leiða í sumum brjálaður villur. Svo að gæta þess að unga fólkið komi stærð kjötkássa töflunni. Cool. Svo árekstra. Er allir góður svo langt? Mmhmm? 

Áhorfendur: Hvers vegna vildi það skila svo svakalega gildi? 

Ræðumaður 1: fer eftir reiknirit að kjötkássa virka notar. Sumir þeirra vilja gera brjálaður margföldun. Og það er allt um að fá a jafnvel dreifingu, svo þeir gera sumir raunverulega brjálaður hlutir stundum. Það er allt. Nokkuð fleira? OK. 

Svo árekstra. Grundvallaratriðum, eins og ég sagði áðan, í besta falli, hvaða fötu ég lít inn er fara að hafa eitt, svo ég þurfi ekki að líta á alla, ekki satt? Ég annaðhvort veit að það er þarna eða það er ekki, og það er það sem við viljum í raun. En ef við höfum tugir þúsunda gögn stig og minna en að tala fötunum, við erum að fara að hafa árekstrar þar loksins eitthvað er að fara til verða að enda í fötu sem þegar hefur stak. 

Svo spurningin er, hvað eigum við að gera í því tilfelli? Hvað gerum við? Við höfum nú þegar eitthvað þarna? Gera við henda bara það út? 

No. Við verðum að halda þau bæði. Svo hátt að við yfirleitt gera það er það? Hvað er gögn uppbygging við ræddum bara um? Áhorfendur: tengda listanum. Ræðumaður 1: A tengda listanum. Svo nú, í stað þess að hver af þessum fötunum bara að hafa einn þáttur, það er að fara að innihalda tengda lista yfir þættir sem voru tætt í það. OK, er allir konar fá þessi hugmynd? Þar sem við gátum ekki haft fylki vegna þess að við vitum ekki hvernig margt eru að fara að vera þar. A tengda listanum leyfa okkur að hafa bara nákvæmlega númerið sem eru tætt í þá fötu, ekki satt? 

Svo línuleg leit er grundvallaratriðum þetta idea-- það er ein leið til að takast á við árekstur. Það sem þú getur gert er ef, í þessu tilfelli, Berry var tætt í 1 og við höfum nú þegar eitthvað þarna, þú bara halda að fara niður þar þú finnur tómt rifa. Það er ein leið til að höndla það. Hin leiðin til að höndla það er með það við bara called-- tengda listi er kallað chaining. 

Svo þessi hugmynd virkar ef kjötkássa borð þitt þú heldur er miklu stærri en gögn sett eða ef þú langar að prófa og lágmarka chaining þar til það er algerlega nauðsynlegt. Svo er eitt línuleg leit augljóslega þýðir að kjötkássa virka þinn er ekki alveg eins og gagnlegur vegna þess að þú ert að fara að enda með kjötkássa virka þinn, fá að punkti, þú Línuleg rannsaka niður sum staðar sem er í boði. En nú, að sjálfsögðu, nokkuð annað sem endar þar, þú ert að fara til verða að leita enn frekar niður. 

Og það er a einhver fjöldi fleiri leita kostnað sem fer í inputting stak í kjötkássa töflunni núna, ekki satt? Og nú þegar þú ferð og reyna að finna Berry aftur, þú ert að fara að kjötkássa það, og það er að fara að segja, Ó, líttu í fötu 1, og það er ekki að fara að vera í fötu 1, þannig að þú ert fara að hafa til að fara yfir gegnum the hvíla af þessir. Svo það er stundum gagnlegt, en í flestum tilvikum, við erum að fara að segja að chaining er það sem þú vilt gera. 

Þannig að við töluðum um þetta fyrr. Ég fékk smá á undan mér. En chaining er í rauninni að hverri fötu í kjötkássa töflunni er bara a tengda listanum. 

Svo önnur leið, eða meira tæknilega leið, að hugsa um kjötkássa borð er að það er bara array tengdra listum, sem þegar þú ert að skrifa orðabókina þína og þú ert að reyna að hlaða hana, hugsa um það sem array tengdra listum mun gera það mun auðveldara fyrir þig að frumstilla. 

Áhorfendur: Svo kjötkássa borð hefur fyrirfram ákveðinn stærð, eins [inaudible] fötunum? 

Ræðumaður 1: Hægri. Svo það hefur a setja fjölda fötunum sem þú determine-- sem þú krakkar ættu ekki hika við að leika sér við. Það getur verið ansi kaldur til að sjá hvað gerist eins og þú breyta fjölda fötunum. En já, það hefur a tiltekinn fjölda fötunum. Hvað gerir þú til að passa eins og margir þættir sem þú þarft er þetta sérstakt chaining þar þér hafa tengt lista í hverri fötu. Það þýðir kjötkássa töflunni verður nákvæmlega stærð að þú þarft það til að vera, ekki satt? Það er allt lið af tengd listum. Cool. 

Svo allir OK þarna? Allt í lagi. Ah. Hvað gerðist bara? Really núna. Giska einhver er að drepa mig. 

OK við erum að fara að fara inn í reynir, sem eru svolítið brjálaður. Mér líkar kjötkássa matskeið. Ég held að þeir séu virkilega flott. Tilraunir eru töff líka. 

Svo er einhver man hvað reyna er? Þú ættir að hafa farið yfir það stuttlega í fyrirlestri? Manstu konar hvernig það virkar? Áhorfendur: Ég er bara að nodding að við vildum fara yfir það. Ræðumaður 1: Við að fara yfir það. OK, við erum alveg að fara að fara yfir og það er nú það sem við erum að segja. 

Áhorfendur: Það er um sókn tré. 

Ræðumaður 1: Já. Það er sókn tré. Ógnvekjandi. Svo eitt að taka hér er að við eru að horfa á einstaka stafi hér, ekki satt? 

Svo áður með kjötkássa virka okkar, við varst að horfa á orð sem heild, og nú erum við að leita meira á persónum, ekki satt? Þannig að við höfum Maxwell hérna og Mendel. Svo í grundvallaratriðum a try-- a leið til að hugsa um þetta er að hvert stig hér er fylki af stöfum. Svo er þetta rót hnút þinn hér, ekki satt? Þetta hefur alla stafina í Alphabet fyrir byrjun hvers orðs. 

Og hvað sem þú vilt gera er segja, OK, við höfum sumir M orð. Við erum að fara að leita að Maxwell, svo við förum til M. og M bendir á heild hinn array þar sem hvert orð, svo lengi sem það er orð sem hefur sem annan staf, svo lengi sem það er orð sem hefur B sem annan staf, það mun hafa músina fara að einhverju næsta fylki. 

There er líklega ekki orð sem MP eitthvað, svo í P stöðu í þessu array, það vildi bara vera NULL. Það myndi segja, OK, það er ekkert orð sem hefur M fylgt eftir með P, OK? Þannig að ef við hugsum um það, hvert einn af þessum smærri hlutum er í raun einn af þessum stór fylki frá A til Z. Svo hvað gæti verið einn af þeim hlutum sem er eins konar endurgreiðslu á reyna? 

Áhorfendur: A einhver fjöldi af minni. 

Ræðumaður 1: Það er tonn af minni, ekki satt? Hver einn af þessum blokkum hér táknar 26 rými, 26 þátturinn array. Svo reynir fá ótrúlega rúm þungur. 

En þeir eru mjög hratt. Svo ótrúlega hratt en virkilega pláss óhagkvæm. Konar hafa að reikna út hver þú vilt. Þetta eru mjög flott fyrir pset þína, en þeir taka upp a einhver fjöldi af minni, svo þú viðskipti burt. Já? 

Áhorfendur: Væri hægt að setja upp a reyna og þá þegar þú hefur öll gögn í það að þú need-- Ég veit ekki hvort það væri skynsamleg. Ég var að fá losa af öllum NULL stafi, en þá að þú viljir ekki vera fær til vísitölu them-- 

Ræðumaður 1: Þú þarft enn þá. 

Áhorfendur: - á sama hátt í hvert skipti. Ræðumaður 1: Já. Þú þarft að Null stafi að láta þú veist ef það er ekki orð þarna. Ben hafðirðu eitthvað sem þú vilt? OK. Allt í lagi, þannig að við erum að fara að fara svolítið meira í tæknilegu smáatriði bak a reyna og vinna með dæmi. 

OK, þannig að þetta er það sama. En í tengda listanum, Main okkar góður of-- hvað er orð sem ég vil? - eins og að byggja blokk var hnút. Í reyna, höfum við einnig hnút, en það er skilgreint á annan hátt. 

Þannig að við höfum sumir bool sem táknar hvort orð raun staðar á þessum stað, og þá við höfum einhverja array here-- eða öllu heldur, þetta er bendi að array 27 stafi. Og þetta er fyrir, í þessu tilfelli, þetta 27-- Ég er viss um að allir af þú ert eins, bíddu, það eru 26 stafir í stafrófinu. Hvers vegna höfum við 27.? 

Svo eftir því sem vegur þú framkvæma þetta, Þetta er úr pset sem leyfð fyrir úrfellingarmerki. Svo er það hvers vegna auka einn. Þú munt einnig hafa í nokkrum tilvikum null Terminator er innifalinn eins og einn af stafir sem það er leyft að vera, og það er hvernig þeir athuga sjá hvort það er í lok orðsins. Ef þú hefur áhuga, kíkja Vídeó Kevin á study.cs50, sem og Wikipedia hefur nokkur góð úrræði þar. 

En við erum að fara að fara í gegnum bara góður um hvernig þú gætir vinna gegnum try Ef þú ert að gefa einn. Þannig að við höfum frábær einföld hér að Inniheldur orðin "kylfu" og "zoom" í þeim. Og eins og við sjáum hér, þetta litla pláss hér táknar bool okkar að segir, já, þetta er orðið. Og svo hefur þetta OKKAR fylki af stöfum, ekki satt? 

Þannig að við erum að fara að fara í gegnum finna "kylfu" í þessu reyna. Svo byrja efst, ekki satt? Og við vitum að b samsvarar annar stuðullinn, annað þáttur í þessu fylki, vegna þess og b. Svo um það bil sá seinni. 

Og það segir, OK, kaldur, fylgja því inn næsta array, því ef við muna, það er ekki að hver af þessum raun inniheldur frumefni. Hver einn af þessum fylki inniheldur bendi, ekki satt? Það er mikilvægt greinarmun að gera. 

Ég veit að þetta er að fara að be-- reynir eru mjög erfitt að fá á í fyrsta sinn, svo jafnvel ef þetta er annað eða þriðja sinn og það er samt góður að virðist erfitt, Ég lofa ef þú ferð horfa skamms aftur á morgun, það mun líklega gera mikið meira vit. Það tekur a einhver fjöldi til að melta. Ég samt stundum er eins, bíddu, hvað er að reyna? Hvernig nota ég þetta? 

Þannig að við höfum b í þessu tilfelli, sem er annar vísitölu okkar. Ef við hefðum td c eða d eða önnur bréf, við þurfum að kortleggja að baka til vísitölu af array okkar að það samsvarar. Svo við myndum taka eins rchar og við bara draga burt a að kortleggja það í 0-25. Allir gott hvernig við kortleggja eðli okkar? OK. 

Svo förum við í seinni og við sjá að, já, það er ekki að NÚLL. Við getum flutt á þessa næstu fylki. Svo við förum á þessa næstu array hér. 

Og við segjum, OK, nú erum við þarf að sjá hvort er hér. Er A null eða hefur það reyndar halda áfram? Svo í raun færist áfram í þessu fylki. Og við segjum, OK, t er síðasta bréfi. Svo förum við í t á vísitölunni. Og þá erum við að fara fram vegna þess að það er annað. Og þetta segir í rauninni að, já, það segir að það er orð here-- að ef þú fylgir þessum slóð, þú ert komin á orði, sem við vitum er "kylfu." Já? 

Áhorfendur: Er það staðall að hafa þessi sem vísitala 0 og síðan hafa eins konar á 1 eða að hafa í lok? 

Ræðumaður 1: No. Þannig að ef við lítum til baka á okkar yfirlýsing hér, er það a bool, svo það er eigin þáttur þess í hnút þínu. Svo það er ekki hluti af fylki. Cool. Svo þegar við klára orð okkar og við erum á þessu fylki, hvað við viljum gera er gera a stöðva fyrir er þetta orð. Og í þessu tilfelli, myndi það koma aftur já. 

Svo á að huga, við vitum að "dýragarðinum" - við vitum eins og menn að "dýragarðinum" er orð, ekki satt? En eru að reyna hér væri segja, nei, það er ekki. Og það myndi segja að vegna þess að við hafa ekki tilnefnt hana sem orð hér. Jafnvel þó að við getum fara gegnum til þessu fylki, þetta reyna myndi segja að, nei, Þykki er ekki í orðabókinni þinni vegna þess að við höfum ekki tilnefnd það sem slíkt. 

Svo ein leið til að gera that-- ó, fyrirgefðu, þetta einn. Þannig að í þessu tilfelli, "dýragarðinn" er ekki orð, en það er í tilraun okkar. En í þessu einn, segja við viljum það kynna orðið "bað", hvað gerist er að við fylgjum through-- b, a, t. Við erum í þessu fylki, og við förum að leita að h. 

Í þessu tilviki, þegar við líta á músina á h, það bendir til NÚLL, OK? Þannig nema það er sérstaklega bendir til annars fylking, þú ráð fyrir að allar ábendingar í þessu fylki eru að benda á núll. Þannig að í þessu tilfelli, H er að benda að núll þannig að við getum ekki gert neitt, svo það myndi einnig skila rangar, "bað" er ekki í hér. Svo nú erum við í raun að fara að fara í gegnum hvernig myndum við segja reyndar að "dýragarðinum" er í tilraun okkar. Hvernig eigum við að setja inn "dýragarðinum" í tilraun okkar? Svo á sama hátt sem við byrjuðum með tengda listanum okkar, byrjum við á rót. Hvenær í vafa, að byrja á rót af þessum hlutum. 

Og við munum segja, OK, Z. z er í þessu, og það gerir. Svo þú ert að flytja á næsta array þinn, OK? Og þá á næsta einn, við segjum, OK, er o til? Það gerir. Þetta aftur. 

Og svo á næsta einn okkar, höfum við sagt, OK, "dýragarðinum" er nú þegar hér. Allt sem við þurfum að gera er að setja þetta jafn satt að það er orðið þar. Ef þú hefðir fylgt allt að fyrir þann lið, það er orð, svo bara setja það jafn svo. Já? 

Áhorfendur: Svo gerir það meina að "BA" er orð líka? 

Ræðumaður 1: No. Svo í þessu tilfelli, "BA" við viljum fá hér er sagt er það orð, og það myndi samt vera ekki. OK? Mmhmm? 

Áhorfendur: Svo þegar þú er það orð og þú segir já, þá er það mun innihalda að fara til m? 

Ræðumaður 1: Svo hefur þetta að gera with-- þú ert að hlaða þetta í. Þú segir "dýragarðinum" er orð. Þegar þú ferð að check-- eins, segjum að þú vilt segja, þýðir "dýragarðinum" til í þessari orðabók? Þú ert bara að fara að leita að "dýragarðinum" og þá athuga hvort það er orð. Þú ert aldrei að fara að flytja gegnum til m því það er ekki hvað þú ert að leita að. 

Þannig að ef við vildum í raun að bæta "bað" í þessa reyna, við myndum gera það sama eins og við gerðum með "dýragarðinum" nema við myndum sjá að þegar við reyna að fá að h, er það ekki til. Svo er hægt að hugsa um þetta og að reyna að bæta við nýjum hnút í tengda listanum, þannig að við myndum þurfa að bæta við öðru einn af þessum fylki, eins og svo. Og þá það sem við gerum er að við setja bara h þáttur í þessu fylki sem bendir á þetta. 

Og þá hvað myndi við viljum gera hér? Setja jafn satt því það er orð. Cool. Ég veit. Reynir eru ekki mest spennandi. Treystu mér, ég veit. 

Svo eitt að átta sig með reynir, Ég sagði, að þeir eru mjög duglegur. Þannig að við höfum séð að þeir taka upp tonn af plássi. Þeir eru eins konar ruglingslegt. Svo hvers vegna ættum við að nota alltaf þessar? Við notum þessar því þeir eru ótrúlega duglegur. 

Svo ef þú ert alltaf að leita upp orði, þú ert eina afmarkast af lengd orðsins. Svo ef þú ert að leita að a orð sem er lengd fimm, þú ert bara alltaf að fara að hafa til að gera í mesta lagi fimm samanburð, OK? Svo gerir það það í grundvallaratriðum a fasti. Eins ísetningu og útlit eru í grundvallaratriðum stöðug skipti. 

Þannig að ef þú getur alltaf fengið eitthvað í föstu tíma, það er eins gott og það gerist. Þú getur ekki fá betri en fasti tími fyrir þessum hlutum. Svo er að ein af gríðarstór plús af reynir. 

En það er mikið af pláss. Svo þú ert góður af að ákveða hvað er meira mikilvægt fyrir þig. Og á tölvum í dag, rúm að reyna getur tekið upp kannski hefur ekki áhrif þú það mikið, en kannski þú ert að takast á við eitthvað sem hefur langt, langt fleiri hluti, og a reyna er bara ekki sanngjarnt. Já? 

Áhorfendur: Bíddu, þannig að þú hefur 26 bréf í hvert einasta einn? 

Ræðumaður 1: Mmhmm. Já, hefur þú 26. Þú hefur sum er orð merki og þá þú hefur 26 ábendingum í hverjum einum. Og þeir eru að point-- 

Áhorfendur: Og hverjum 26, gera þeir hafa hver 26? 

Ræðumaður 1: Já. Og þess vegna, eins og þú getur sjá, það stækkar ört. Allt í lagi. Þannig að við erum að fara að fá inn tré, sem Mér finnst eins og er auðveldara og mun sennilega vera a ágætur lítill reprieve frá reynir þar. Svo vonandi flest ykkar hafa séð tré áður. Ekki eins og nokkuð sjálfur utan, sem ég veit ekki hvort einhver fór úti nýlega. Ég fór epli tína um helgina, og ó nei, það var fallegt. Ég vissi ekki lauf gæti litið að nokkuð. 

Svo er þetta bara tré, ekki satt? Það er bara nokkrar hnútur, og það bendir til fullt af öðrum hnúður. Eins og þú sérð hér, þetta er konar endurteknar þema. Hnúður vísa á tengipunkta er góður af kjarninn í mörgum gögn mannvirki. Það veltur bara á því hvernig við hafa þá benda til hvers annars og hvernig við fara gegnum þá og hvernig við setja hluti sem ákvarðar mismunandi einkenni þeirra. 

Svo bara sumir hugtök, sem ég hef notað áður. Svo er rót hvað er á mjög toppur. það er þar sem við byrjum alltaf. Þú getur hugsað um það sem höfði einnig. En fyrir tré, við hafa tilhneigingu til að vísa til þess sem rót. 

Nokkuð neðst here-- á mjög, mjög bottom-- teljast lauf. Svo fer það ásamt heild tré hlutur, ekki satt? Leaves eru á brúnir tré. 

Og þá höfum við einnig nokkra hugtök til að tala um hnúta í tengslum til hvers annars. Þannig að við höfum foreldri, Börn og systkini. Þannig að í þessu tilfelli, 3 er foreldri 5, 6, og 7. Svo er foreldri hvað er eitt skref yfir hvað þú ert vísa til, svo bara eins ættartré. Vonandi, þetta er allt svolítið aðeins meira innsæi en reynir. 

Systkini eru allir sem hafa sama foreldri, ekki satt? Þeir eru á sama stigi hér. Og þá, eins og ég var segja, börn eru bara hvað er eitt skref fyrir neðan hnúturinn ræðir, OK? Cool. Svo tvöfaldur tré. Getur einhver greiningar áhættu giska á einn af eiginleika tvöfaldur tré? 

Áhorfendur: Max tvö laufblöð. 

Ræðumaður 1: Hægri. Svo max tveggja laufum. Svo í þessu einn áður, við höfðum þetta eitt sem átti þrjá, en í binary tré, þú hafa a max tveimur Börn á foreldri, ekki satt? There 'annar áhugavert eiginleika. Hefur einhver veit það? Tvöfaldur tré. 

Svo tvöfaldur tré mun hafa allt á the-- þetta er ekki sorted-- en í raðað tvöfaldur tré, allt á hægri er meiri en foreldri, og allt á vinstri er minna en foreldri. Og það hefur verið quiz spurning áður, svo gott að vita. Svo hvernig við skilgreinum þetta, aftur, höfum við annan hnút. Þetta lítur mjög svipað hvað? Tvöfalt 

Áhorfendur: Tengd listar 

Ræðumaður 1: A tvöfaldur tengda listanum, ekki satt? Þannig að ef við skipta þessu með fyrri og næsta, þetta myndi vera tvöfalt tengda listanum. En í þessu tilfelli, í raun við hafa vinstri og hægri og það er það. Annars er það nákvæmlega það sama. Við höfum enn þáttur þú ert að leita að, og þú verður bara tvær ábendingar fara til hvað er næst. Já, svo tvöfaldur leita tré. Ef við tökum eftir, allt á hérna er meiri than-- eða allt strax til hérna er meiri en, allt hér er minna en. 

Þannig að ef við værum að leita í gegnum, það ætti að líta mjög nálægt tvöfaldur leit hér, ekki satt? Nema í stað þess að leita á helmingi fylki, við erum bara að horfa á annaðhvort vinstra hlið eða hægri hlið af trénu. Svo það fær lítið einfaldara, held ég. 

Svo ef rót er NULL, augljóslega er það bara rangt. Og ef það er þarna, augljóslega það er satt. Ef það er minna en, leita við vinstri. Ef það er meira en, við leit rétt. Það er nákvæmlega eins og tvöfaldur leit, bara mismunandi gögn uppbygging að við erum að nota. Í stað þess fjölda, það er bara tvöfaldur tré. 

OK, stafla. Og einnig, það útlit eins og við gæti haft smá tíma. Ef við gerum það, ég er fús til að fara yfir eitthvað af þessu aftur. OK, svo stafla. Hefur einhver man hvað stacks-- aðra eiginleika reykháf? 

OK, svo af okkur, ég held, borða í borðstofu halls-- eins mikið og við getum ekki eins og til. En vitanlega er hægt að hugsa um stafla bókstaflega bara sem stafla af stæði eða stafla af hlutum. Og það sem er mikilvægt að átta sig á er að það er something-- einkennandi sem við köllum það by-- er LIFO. Hefur einhver veit hvað það stendur fyrir? Mmhmm? 

Áhorfendur: síðasta, fyrst út. 

Ræðumaður 1: Hægri, endast í, fyrst út. Þannig að ef við vitum, ef við erum að stöflun hlutina upp, auðveldasta hlutur til að grípa off-- og kannski það eina sem við getum grípa burt ef stafla okkar er stór enough-- er að ofan þáttur. Svo hvað var sett á last-- eins og við sjáum hér, hvað var ýtt á flestum recently-- er fara til vera the fyrstur hlutur sem við skjóta burt, OK? 

Svo er það sem við höfum hér annar typedef strúktúr. Þetta er í raun bara eins og a hrun námskeið í gögn uppbygging, þannig að það er a einhver fjöldi kastað á ykkur. Ég veit. Svo enn annar strúktúr. Yay fyrir mannvirki. 

Og í þessu tilfelli, er það sumir bendi til fjölda sem hefur einhverja getu. Svo táknar þetta stafla okkar hér, eins og raun array okkar sem eignarhlutur þætti okkar. Og svo hér höfum sumir stærð. 

Og venjulega, þú vilt halda utan um hversu stór stafla er vegna þess hvað það er að fara að leyfa þér að gera er ef þú veist stærð, það gerir þér kleift að segja, OK, ég á getu? Get ég bætt eitthvað meira? Og það segir þér einnig þar efst á stafla þinn er svo þú veist hvað þú geta í raun tekið burt. Og það er í raun að fara til vera svolítið skýrari hér. 

Svo fyrir ýta, einn hlutur, ef þú voru alltaf að framkvæma ýta, eins og ég var bara að segja, þín Stack hefur takmarkaðan stærð, ekki satt? Array okkar höfðu sumir getu. Það er óákveðinn greinir í ensku fylking. Það er fasta stærð, þannig að við þurfum að ganga úr skugga um að við erum ekki að setja meira í fylking okkar en við raun hafa pláss fyrir. 

Svo þegar þú ert að búa til ýta virka, fyrstur hlutur þú gera er að segja, OK, þarf ég pláss í stakkur minn? Vegna þess að ef ég er ekki, því miður, Ég get ekki geymt þáttur þinn. Ef ég geri, þá þú vilt geyma það efst á stafla, ekki satt? 

Og þetta er ástæða þess að við höfum að halda utan um stærð okkar. Ef við gerum ekki viðurværi rekja spor einhvers af stærð okkar, við vitum ekki hvar á að setja það. Við vitum ekki hvernig margt eru í fylking okkar þegar. Eins augljóslega eru leiðir sem kannski þú gætir gert það. Þú gætir frumstilla allt til NULL og þá stöðva fyrir nýjustu NÚLL, en mun auðveldara hlutur er bara að segja, OK, halda utan um stærð. Eins og ég veit að ég hef fjóra þætti fylkt mínum, þannig að næsta hlutur að við að setja á, erum við að fara að geyma í vísitölu 4. Og þá, að sjálfsögðu, þetta þýðir að þér hefur tekist að ýtt eitthvað á mánudaginn, þú vilja til að auka stærð þannig að þú veist hvar þú ert svo að þú getur ýta fleiri hluti á. 

Þannig að ef við erum að reyna að skjóta eitthvað af stafla, hvað gæti verið það fyrsta sem að við viljum athuga? Þú ert að reyna að taka eitthvað burt Stakkur þitt. Ertu viss er það eitthvað í Stakkur þitt? No. Svo hvað gæti við viljum að athuga? 

Áhorfendur: [inaudible]. Ræðumaður 1: Athugaðu að stærð? Size. Þannig að við viljum athuga hvort stærð okkar er meiri en 0, OK? Og ef það er, þá viljum við lækka stærð okkar um 0 og aftur það. Hvers vegna? 

Í þeirri fyrstu við vorum þrýsta, ýtt við það á stærð og svo uppfærð stærð. Í þessu tilfelli erum við decrementing stærð og þá að taka það burt, plokkun það frá array okkar. Hvers vegna gætum við gert það? Svo ef ég hef eitt á mánudaginn mitt, hvað væri stærð minn á þeim tímapunkti? 1. 

Og hvar er þáttur 1 geymdar? Á hvaða vísitölu? Áhorfendur: 0. Ræðumaður 1: 0. Þannig að í þessu tilfelli, við alltaf þarf að gera sure-- stað þess að skila stærð mínus 1, vegna þess að við vita að þátturinn okkar er að fara að geyma við 1 minna hvað stærð okkar er, þetta bara tekur sjá um það. Það er örlítið meira glæsilegur hátt. Og við lækka bara OKKAR stærð og síðan aftur stærð. Mmhmm? 

Áhorfendur: Ég giska bara almennt, hvers vegna vildi þessi gögn uppbygging verið gagnleg? 

Ræðumaður 1: Það veltur á samhengi þínu. Svo fyrir sumir af kenningunni, Ef þú ert að vinna with-- lagi, láttu mig sjá hvort það er til góðs einn það er gagnlegt að meira en utan CS. Með stafla, hvenær sem þú þarft að halda utan um eitthvað sem er nýlega bætt er þegar þú ert að fara til að vilja nota stafla. 

Og ég get ekki hugsað mér gott dæmi um það núna. En þegar nýjasta hlutur er mest mikilvægt að þú, það er þegar stafla er að fara til að vera gagnlegt. Ég er að reyna að hugsa ef það er gott ár fyrir þetta. Ef ég hugsa um góðu fordæmi í næstu 20 mínútur, mun ég örugglega segja þér. 

En í heild, ef það er eitthvað, eins og ég sagði flest, þar nýjustu er mikilvægast, það er þar stafla kemur inn í leik. En biðraðir eru konar hið gagnstæða. Og allir litlu hundar. Er þetta ekki frábært, ekki satt? Mér líður eins og ég ætti bara kanínu vídeó réttur í the miðja af kafla fyrir ykkur því þetta er mikil kafla. 

Svo biðröð. Í grundvallaratriðum er biðröð eins línu. Þú krakkar Ég er viss notkun þessa daglegur, Rétt eins og í veitingastöðum sölum okkar. Þannig að við verðum að fara í og fá stæði okkar, ég er viss um að þú þarft að bíða í línu að högg eða fá matinn þinn. 

Svo munurinn hér er að þetta er FIFO. Svo ef LIFO var síðast í, fyrst út, FIFO er fyrst inn fyrst út. Svo er þetta þar sem þú setur á fyrri er mikilvægasta þinn. Svo ef þú varst að bíða í line-- kanntu ímynda sér ef þú fórst í fara að fá nýja iPhone og það var stafla þar sem síðasta manneskja í línu fékk það fyrst, fólk myndi drepa hvert annað. 

Svo FIFO, erum við öll mjög kunnugur með í hinum raunverulega heimi hér, og það allt hefur að gera með raunverulega konar skemmtun þessa alla línuna og biðröð uppbyggingu. Svo þar með stafla, við höfum ýta og POP. Með biðröð, við höfum enqueue og dequeue. Svo enqueue grundvallaratriðum þýðir setja það á bak, og dequeue leið taka burt frá the andlit. Svo er gagnagrind okkar a svolítið flóknara. Við höfum annað hlutur til að halda utan um. 

Svo án þess að höfuð, þetta er einmitt a stakkur, ekki satt? Þetta er það sama uppbygging sem stafla. Það eina öðruvísi núna er að við hafa þetta höfuð, sem hvað þú telur er að fara að halda utan um? 

Áhorfendur: Sú fyrsta. 

Ræðumaður 1: rétt, fyrsta sem við setjum inn. Höfuð biðröð okkar. Sá er fyrst í röðinni. Allt í lagi, þannig að ef við gerum enqueue. Aftur, með einhverju þessi gögn uppbygging, þar sem við erum að fást við fjölda, þurfum við að athuga hvort við höfum pláss. 

Þetta er góður af eins og mig að segja þú krakkar, ef þú opnar skrá, þú þarft að athuga for null. Með einhverjum af þessum stafla og biðraðir, þú þarft til að sjá hvort það er rúm vegna þess að við erum takast með fasta stærð array, eins og við sjáum here-- 0, 1 allt upp að 5. Svo það sem við gerum í því tilfelli er að athuga til að sjá hvort við höfum enn pláss. Er stærð okkar minna en getu? 

Ef svo er, þurfum við að geyma það á hali og við uppfærum stærð okkar. Svo hvað gæti hali verið í þessu tilviki? Það er ekki beinlínis skrifað út. Hvernig ættum við að geyma það? Hvað myndi hala vera? 

Svo skulum ganga í gegnum þetta dæmi. Svo er þetta fylki af stærð 6, ekki satt? Og við höfum núna, stærð okkar er 5. Og þegar við setjum það í, það er að fara að fara í fimmta vísitölu, ekki satt? Svo vista í hali. 

Önnur leið til að skrifa hala myndi bara vera array okkar við vísitölu stærð, ekki satt? Þetta er stærð 5. Næsta sem er að fara að fara í 5. Cool? OK. Það gerist aðeins flóknara þegar við byrjum Messías með höfuð. Já? 

Áhorfendur: Þýðir það að við hefði lýst fylki sem var fimm frumefni og þá erum við að bæta á það? 

Ræðumaður 1: No. Svo í þessu tilfelli, þetta er stafla. Þetta myndi vera lýst sem fylki af stærð 6. Og í þessu tilfelli, við bara eitt pláss laust. 

OK, svo er eitt í þessu ræða, ef höfuð okkar er á 0, þá erum við bara að bæta það á stærð. En það fær smá trickier því í raun, þeir hafa ekki renna fyrir þetta, þannig að ég ætla að fara að draga einn því það er ekki alveg svo einfalt þegar þú byrjar að fá losa af hlutum. Svo þar með stafla þú bara alltaf hafa að hafa áhyggjur af hvað stærð er þegar þú ert að bæta eitthvað á, með biðröð þú þarft einnig að gera viss um að höfuðið er grein fyrir, vegna þess að kaldur hlutur óður biðraðir er að ef þú ert ekki á getu, þú geta raunverulega gera það hula í kring. 

OK, svo einn thing-- ó, þetta er hræðileg krít. Eitt sem þarf að íhuga er raunin. Við munum bara gera fimm. OK, þannig að við erum að fara að segja að höfuð er hér. Þetta er 0, 1, 2, 3, 4. 

Höfuðið er þarna, og vinsamlegast hafa hlutina í þeim. Og við viljum að bæta eitthvað í, ekki satt? Svo það sem við þurfum að vita er að hausinn er alltaf að fara að flytja með þessum hætti og þá loop back kring, OK? 

Þannig að þetta biðröð hefur pláss, satt? Það hefur pláss í upphafi, konar andstæðu þetta. Svo það sem við þurfum að gera er að við þarf að reikna skottið. Ef þú veist að þinn höfuð hefur ekki flutt, hali er bara array þinn á Vísitala stærð. 

En í raun og veru, ef þú ert að nota biðröð, höfuðið er líklega að uppfæra. Svo hvað þú þarft að gera er reyndar reikna hala. Svo það sem við gerum er þetta uppskrift hér, sem ég ætla að láta þig krakkar hugsa um, og þá munum við tala um það. Þannig að þetta er getu. 

Þannig að þetta mun í raun gefa þér leið til að gera það. Vegna þess að í þessu tilfelli, hvað? Höfuð okkar er á 1, stærð okkar er 4. Ef við unga fólkið sem um 5, fáum við 0, sem er þar sem við ættum inntak það. 

Svo þá í næsta tilfelli, Ef við vorum að gera þetta, við segjum, OK, við skulum dequeue eitthvað. Við dequeue þetta. Við tökum þessa frumefni, ekki satt? 

Og nú höfuð okkar er að benda hér, og við viljum bæta við í öðru lagi. Þetta er í grundvallaratriðum bak línu okkar, ekki satt? Biðraðir getur sett í kringum fylkisins. Það er eitt af helstu munur. Stafla, getur þú ekki gert þetta. 

Með biðraðir, þú getur vegna þess að allt sem skiptir máli er að þú veist hvað var síðast bætt við. Þar sem allt er að fara að bæta við í þessi leftward átt, í þessu tilfelli, og þá vefja í kring, þú getur áfram að setja í nýjum þætti á the andlit af the array því það er í raun ekki framan á array lengur. Þú getur hugsað um í byrjun þess array og hvar höfuðið í raun er. 

Svo er þetta uppskrift hvernig þú reiknar hala þínum. Er það er vit? OK. OK, dequeue, og þá þið hafið 10 mínútur að spyrja mig allir að skýra spurningar þú vilt, vegna þess að ég veit að það er brjálaður. 

Allt í lagi, svo í sama way-- Ég veit ekki hvort þið tekið eftir, en CS er allt um mynstrum. Hlutirnir eru ansi mikið sama, bara með pínulitlum klip. Svo sama hér. Við þurfum að athuga hvort við í raun hafa eitthvað í biðröð okkar, ekki satt? Segja, OK, er stærð okkar meiri en 0? Cool. 

Ef við gerum það, þá erum við að færa höfuð okkar, sem er það sem ég sýndi bara hér. Við uppfærslu höfuð okkar til að vera einn. Og þá erum við lækka okkar stærð og skila frumefni. 

Það er miklu meira steypu kóðann á study.cs50.net, og ég mæli með mjög fara gegnum það ef þú hefur tíma, jafnvel ef það er bara gervi-númer. Og ef þú krakkar vilja til að tala í gegnum að með mér einn á einn, vinsamlegast láttu mig vita. Ég væri fús til að. Gögn uppbygging, ef þú tekur CS 124, þú munt vita að gögn uppbygging fá mjög gaman og þetta er bara byrjunin. 

Svo ég veit að það er erfitt. Það er allt í lagi. Við baráttu. Ég geri enn. Svo ekki hafa áhyggjur of mikill óður í það. 

En það er í grundvallaratriðum ÞINN hrun námskeið í uppbyggingu gagna. Ég veit að það er mikið. Er eitthvað sem við langar að fara aftur? Eitthvað sem við viljum að tala í gegnum? Já? 

Áhorfendur: Fyrir þessi dæmi, svo nýja hali er á 0 yfir það? Ræðumaður 1: Já. Áhorfendur: OK. Svo þá að fara í gegnum, þú vilt hafa 1 plús 4 or-- 

Ræðumaður 1: Svo þú varst að segja, þegar við viljum fara að gera þetta aftur? Áhorfendur: Já. Svo ef þú varst vangaveltur out-- hvar eru þú reikna hala frá því? 

Ræðumaður 1: Svo hali var in-- ég breytti þessu. Svo í þessu dæmi hér, þetta var array við erum að horfa á, OK? Þannig að við höfum það í 1, 2, 3, og 4. Þannig að við höfum höfuð okkar er jafnt og 1 á þetta lið, og stærð okkar er jafnt og 4 á þessum tímapunkti, ekki satt? 

Þú öll sammála um að er að ræða? Svo við gerum höfuðið auk stærð, sem gefur okkur 5, og þá erum við unga fólkið um 5. Við fáum 0, sem segir okkur að 0 er hvar er skottið okkar, þar sem við höfum pláss. 

Áhorfendur: Hvað er a hettu? 

Ræðumaður 1: Getu. Sorry. Svo er að stærð array þinn. Já? 

Áhorfendur: [inaudible] áður við aftur þátturinn? 

Ræðumaður 1: Svo við færa höfuð eða skila augnablik? Þannig að ef við færa einn, lækka stærð? Bíddu. Ég gleymdi örugglega annað. Aldrei hugur. Það er ekki annað uppskrift. Já, myndir þú vilja til að fara aftur höfuð og þá færa það til baka. 

Áhorfendur: OK, því á þessum tímapunkti höfuð var á 0, og þá þú vilt að skila Vísitala 0 og þá gera höfuð 1? 

Ræðumaður 1: Hægri. Ég held að það er annar uppskrift konar svona. Ég hef það ekki á the toppur höfuð mitt eins Ég vil ekki að gefa þér röng einn. En ég held að það er í gildi fullkomlega að segja, OK, geyma þessa element-- hvað þáttur höfuð er is-- lækka þinn stærð, færa höfuðið yfir, og aftur hvað þessi þáttur er. Það er fullkomlega gild. OK. Mér finnst eins og þetta er ekki eins most-- þú ert ekki að fara að ganga út héðan eins, já, ég veit reynir. Ég fékk það allt. Það er allt í lagi. Ég lofa. En gögn uppbygging eru eitthvað sem það tekur a einhver fjöldi af tími til að venjast. Sennilega einn af the herða hlutir, held ég, í námskeiðinu. 

Svo það tekur örugglega endurtekning og útlit at-- I vissi ekki alveg vita tengd listum fyrr en ég gerði allt of mikið með þeim, á sama hátt og ég gerði ekki raunverulega skilja ábendingum þangað til ég hef þurft að kenna það í tvö ár og gera eigin psets mína með það. Það tekur a einhver fjöldi af reiteration og tíma. Og að lokum, mun það konar smella. 

En í millitíðinni, ef þú ert góður að víðtækri skilning á því hvað þessir gera, kostir þeirra og cons-- sem er hvað við hafa tilhneigingu í raun að leggja áherslu á, sérstaklega í innra námskeiði. Eins, hvers vegna ættum við að nota a reyna yfir fylki? Eins og, hvað eru jákvæður og filmur í hverjum þessara? 

Og skilja málamiðlanir á milli hvers þessara mannvirkja er það sem er miklu meira máli núna. Það kann að vera ein brjálaður spurning eða tvær sem er að fara að biðja þig um að innleiða ýta eða innleiða popp eða enqueue og dequeue. En að mestu leyti, að hafa það meiri skilning og fleiri af leiðandi skilja er meira máli en í raun og veru vera fær um að framkvæma það. 

Það myndi vera mjög ógnvekjandi ef ykkur gæti farið út og fara innleiða reyna, en við skiljum að það er ekki endilega mest sanngjarnt hlutur núna. En þú getur í pset þinn, ef þú vilt til, og þá munt þú fá starf, og þá kannski þú munt raunverulega skilja það. Já? 

Áhorfendur: OK, þannig hver sjálfur ert við ætlað að nota í pset? Þarf ég að nota einn af þeim? Ræðumaður 1: Já. Svo þú hefur val þitt. Ég giska í þessu tilfelli, við getum tala um pset svolítið vegna þess að ég hljóp í gegnum þetta. Svo í pset þinn, hefur þú ÞÍN val á reynir eða kjötkássa matskeið. Sumir vilja reyna og nota blóma síur, en þeir tæknilega eru ekki rétt. Vegna Probabilistic eðlis þeirra, þeir gefa rangar jákvæður stundum. Þeir eru flott líta inn, þó. Highly recommend leita á þá að minnsta kosti. En þú hefur val þitt milli kjötkássa borð og reyna. Og það er að fara að vera þar sem þú hleður í orðabókina þína. 

Og þú þarft að velja kjötkássa virka þinn, þú þarft að velja hversu margir fötunum sem þú hefur, og það er mismunandi. Eins ef þú ert með fleiri fötur, kannski það mun hlaupa hraðar. En kannski þú ert að sóa a mikið af pláss þannig, þó. Þú verður að reikna það út. Mmhmm? 

Áhorfendur: Þú sagðir áður að við getum notað aðrar aðgerðir kjötkássa, að við þurfum ekki að búa til kjötkássa virka? 

Ræðumaður 1: Já, rétt. Svo bókstaflega fyrir kjötkássa virka þinni, eins og Google "kjötkássa virka" og leita að einhverjum flottum sjálfur. Þú ert ekki gert ráð fyrir að byggja eigin kjötkássa þinn aðgerðir. Fólk eyða þeirra ritgerðir um þetta. 

Svo ekki hafa áhyggjur óður í að byggja eigin spýtur. Finna einn á netinu til að byrja með. Sumir af þeim sem þú þarft að vinna svolítið til að tryggja að tegundir aftur passa upp og whatnot, svo í upphafi, Ég myndi mæla með að nota eitthvað mjög auðvelt að kannski bara kjötkássa á fyrsta staf. Og þá þegar þú hefur þessi vinna, innlimun kælir kjötkássa virka. Mmhmm? 

Áhorfendur: Mundi reyna vera eða duglegur en bara erfiðara að, like-- 

Ræðumaður 1: Svo reyna, held ég, er innsæi erfitt að framkvæma en er mjög fljótur. Hins vegar tekur upp meira pláss. Aftur, getur þú bjartsýni bæði þeirra sem eru í mismunandi leiðir og það eru leiðir to-- Áhorfendur: Hvernig erum við farið á þetta? Er það matter-- 

Ræðumaður 1: Svo þú ert farið eðlilega leið. Þú ert að fara að vera farið á hönnun. Á þann hátt sem þú gerir, þú vilja til ganga úr skugga um það er eins glæsilegur og það getur verið og eins skilvirkt og það getur orðið. En ef þú velur a reyna eða tæti borð, svo lengi sem það virkar, við erum ánægð með það. Og ef þú notar eitthvað sem kjötkássa á fyrsta staf, það er fínn, eins og kannski eins og hönnun-vitur. Við erum líka orðin lið í þessu semester-- Ég veit ekki hvort þú krakkar noticed-- ef þú ert pset bekk lækka smá vegna hönnunar og whatnot, það er fullkomlega í lagi. Það er að fá til a benda hvar ÞÍN forrit eru að fá flóknari. Það eru fleiri staðir þú getur bætt á. 

Svo það er fullkomlega eðlilegt. Það er ekki það að þú sért gera verri á pset þinni. Það er bara að við erum að vera erfiðara á þig núna. Svo allir er tilfinning það. Ég farið bara öll psets þínum. Ég veit að allir er tilfinning það. 

Svo verið ekki áhyggjur af því. Og ef þú hefur einhverjar spurningar um fyrri psets eða leiðir sem þú getur bætt, Ég reyni og tjá sérstakar stöðum, en stundum er það of seint og ég fá þreyttur. Eru einhverjar aðrar hlutir um gögn uppbygging? Ég er viss um að þú krakkar gera ekki raunverulega langar að tala um þá lengur, en ef það eru, ég er fús til að fara yfir þeim, sem og nokkuð frá fyrirlestri á síðasta viku eða síðustu viku. 

Ég veit í síðustu viku var allt endurskoðun þannig við kann að hafa sleppt yfir nokkur endurskoðun frá fyrirlestrinum. Allar aðrar spurningar sem ég get svarað? OK, allt í lagi. Jæja, þú krakkar fá út 15 mínútur snemma. 

Ég vona að þetta var hálf-gagnlegt að minnsta kosti, og ég mun sjá ykkur í næstu viku, eða fimmtudagur skrifstofutíma. Eru beiðnir um snakk fyrir næstu viku, er það hlutur? Þar sem ég gleymdi nammi dag. Og ég leiddi nammi síðustu viku, en það var Columbus Day, þannig að það var eins og sex manns sem voru fjórir pokar af sælgæti til sín. Ég get koma Starbursts aftur ef þú vilt. Starbursts? OK, hljómar vel. Hafa a mikill dagur, krakkar.