[Muzika] 

ANDI Peng: Mirë se vini në javën e 6 të seksionit. Ne devijuar nga standardin tonë kohë seksion i martën pasdite në këtë të bukur dielën në mëngjes. Faleminderit për të gjithë që u bashkua me mua sot, por seriozisht, një raund të duartrokitje. 

Kjo është një përpjekje shumë e madhe. Unë pothuajse nuk e bëni edhe atë deri në kohë, por ajo ishte në rregull. Kështu që unë e di se të gjithë ju e kanë bërë vetëm atë në quiz. Para së gjithash, të mirëpritur për anën rrokullisje e që. 

Së dyti, ne do të flasim për këtë. Ne do të flasim për quiz. Ne do të flasim rreth asaj se si ju jeni duke bërë në klasë. Ju do të jetë mirë. Kam kuize tuaja për ju në fund të ketu, kështu që nëse ju djema duan të marrin një vështrim në atë, krejtësisht gjobë. 

Në mënyrë të shpejtë para se të filloni, Rendi i ditës për sot është si vijon. Siç mund ta shikoni, ne jemi qitjes në thelb i shpejtë përmes një bandë e tërë e strukturat e të dhënave me të vërtetë, me të vërtetë, me të vërtetë shpejt. Pra, si e tillë, ajo nuk do të jetë sot super interaktive. Ajo do të jetë vetëm unë lloj i bërtasin gjërat që ju, dhe në qoftë se unë të ngatërruar ju, në qoftë se unë jam duke shkuar shumë shpejt, let me know. Ata janë të dhënat e vetëm të ndryshme struktura, dhe si pjesë i pset tuaj për këtë Javën e ardhshme, ju do të të kërkohet që të zbatojë njërin prej tyre, ndoshta dy, porsi dy prej tyre në pset tuaj. OK, kështu që unë jam vetëm duke shkuar për të të fillojë me disa njoftime. Ne do të shkoj për oxhaqet dhe rradhë më shumë në Thellësia se ajo që ne e bëmë para quiz. Ne do të shkojnë mbi të lidhura lista përsëri, edhe një herë, më në thellësi se çfarë kemi pasur para quiz. Dhe pastaj ne do të flasim për hash tavolina, pemë dhe të përpiqet, të cilat janë të gjitha mjaft të nevojshme për pset tuaj. Dhe pastaj ne do të shkoj për disa këshilla të dobishme për pset5. 

OK, kështu që quiz 0. Mesatarja ishte 58%. Ajo ishte shumë e ulët, dhe kështu ju djema të gjithë bëri shumë, shumë mirë në përputhje me atë. 

Pretty much, rregull e pranoj është në qoftë se ju jeni brenda një devijim standard prej mesatares veçanërisht pasi ne jemi në një më pak Seksioni i qetë, ju jeni plotësisht në rregull. Ju jeni në rrugën e duhur. Jeta eshte e mire. 

Unë e di se është e frikshme të mendosh se Kam marrë si një 40% në këtë quiz. Unë do të dështojë këtë klasë. Unë ju premtoj, ju nuk jeni do të dështojë klasën. Ju jeni krejtësisht në rregull. 

Për ata prej jush që mori përsipër mesatarja, mbresëlënëse, mbresëlënëse, si, bëhet seriozisht mirë. Unë kam ato me mua. Ndjehen të lirë për të ardhur të marrë ato ne fund te seksionit. Më lejoni të di nëse keni ndonjë çështje, pyetje me ta. Në qoftë se ne shtoni deri rezultatin tuaj gabim, le të na njohin. 

OK, kështu që pset5, kjo është një të vërtetë Javën e pazakontë për Yale në kuptimin që pset jonë është për shkak Të mërkurën në mesditë, duke përfshirë ditë me vonesë, kështu që është e vërtetë teorikisht shkak të martën në mesditë. Ndoshta askush nuk e përfundoi në martën në mesditë. Kjo është krejtësisht në rregull. Ne do të kemi orarin e punës sonte si edhe natën e së hënës. Dhe të gjitha seksionet e kësaj jave do të në fakt të shndërrohet në punëtori, kështu që të ndjehen të lirë për të pop në çdo seksion ju dëshironi, dhe ata do të jenë lloj i mini-pset punëtori për ndihmë në këtë. Pra, si i tillë, ky është i vetmi seksion ku ne jemi mësuar materiale. Të gjitha pjesët e tjera do të jenë duke u fokusuar vetëm në ndihmën për pset. Po? 

Audienca: Ku janë orarit të punës? 

ANDI Peng: Orari i punës tonight-- oh, pyetje e mirë. Unë mendoj orarit të punës Tonight janë në Teal ose në Commons. Nëse ju shikoni në internet CS50 dhe ju shkoni të orarit të punës, duhet të ketë një orar që ju ku të gjithë prej tyre janë të tregon. 

Unë e di as sonte ose nesër është Teal, dhe unë mendoj se ne mund të kemi commons për natën tjetër. Nuk jam i sigurt. Pyetje e mirë. Kontrolloni në CS50. 

Ftohtë, ndonjë pyetje lidhur me Orari për të ardhshëm si tri ditë? Unë premtoj ju djema si David tha, kjo është në krye të kodrës. Ju djema janë pothuajse atje. Vetëm tre ditë më shumë. Get atje, dhe pastaj ne do të të gjithë të vijnë poshtë. Ne do të kemi një pushim të bukur CS-free. Ne do të kthehen. Ne do të zhyten në web programimit dhe zhvillimit, gjëra që janë shumë të fun krahasim disa prej psets tjera. Dhe kjo do të jetë dridhura, dhe ne do të kemi shumë argëtim. Ne do të kemi më shumë karamele. Na vjen keq për karamele. Kam harruar karamele. Ishte një mëngjes i përafërt. Pra, ju djema jeni gati atje, dhe unë jam me të vërtetë krenar për ju djema. 

OK, kështu oxhaqet. Kush dashur pyetje në lidhje me Jack dhe veshja e tij në quiz? Asnje? OK, kjo është në rregull. 

Pra, në thelb si ju mund të foto Jack, ky djalë këtu, i pëlqen për të marrë veshje nga maja e pirg, dhe ai e vë atë mbi rafte pasi ai është bërë. Pra, në këtë mënyrë, ai kurrë nuk duket të jetë marrë në pjesën e poshtme të rafte në rrobat e tij. Pra, ky lloj i përshkruan struktura dhënat themelore se si një pirg është zbatuar. 

Në thelb, të mendojnë për një rafte si çdo pirg e objekteve ku ju vënë gjërat mbi krye, dhe atëherë ju pop ato jashtë nga maja. Pra LIFO është akronim ne si të use-- fundit në, parë jashtë. Dhe në mënyrë të kaluar në në majën e rafte është i pari që vjen jashtë. Dhe kështu dy termat ne si për të shok me të cilat janë quajtur shtytje dhe pop. Kur ju shtyjnë diçka mbi rafte, dhe ju pop atë back up. 

Dhe kështu që unë mendoj se kjo është lloj i një koncept abstrakt për ato prej jush që duan të shohin si një zbatimi aktual i kësaj në botën reale. Sa prej jush kanë shkruar një ese ndoshta si një orë para se të ishte për shkak, dhe ju fshirë aksidentalisht një i madh copë e saj, si rastësisht? Dhe pastaj çfarë të kontrollit të bëjë ne e përdorim për ta vënë atë përsëri? Kontrolli-Z, vërtet? Kontrolli-Z, kështu që shuma e kohës që Kontrolli-Z ka shpëtuar jetën time, ka shpëtuar ass tim, çdo herë që është zbatuar përmes një pirg. 

Në thelb të gjitha informatat kjo është në dokumentin tuaj Word, ajo merr shtyrë dhe popped sipas dëshirës. Dhe kështu në thelb sa herë që ju fshini ndonjë gjë, ju pop atë back up. Dhe pastaj në qoftë se keni nevojë për atë përsëri në, ju shtyjnë atë, e cila është ajo që e bën Control-C. Dhe funksioni kështu Real Botërore i strukturës sa të thjeshtë e të dhënave mund të ndihmojë me jetën tuaj të përditshme. 

Pra, një struct është mënyra se ne fakt krijojnë një pirg. Ne shkruani përcaktojë e strukturës, dhe pastaj ne e quajmë atë rafte në fund. Dhe brenda rafte, ne kemi dy parametra që ne në thelb mund të manipulojnë, kështu që ne kemi char kapacitet strings yll. 

Të gjitha që ajo është duke bërë është duke krijuar një rrjet që ne mund të ruajë çdo gjë që ju doni të cilat ne mund të përcaktojë kapacitetin e tij. Kapaciteti është vetëm sasia max e Artikuj ne mund të vënë në këtë grup. Madhësia int është counter që mban gjurmët e sa shumë sende janë aktualisht në rafte. Pra, atëherë ne mund të mbajnë gjurmët e, A, edhe sa i madh rafte aktuale është, dhe, B, se sa e atij rafte mbushëm sepse ne nuk duam të fryhen mbi atë që kapaciteti ynë është. 

Kështu për shembull, kjo bukuroshe Pyetja ishte në quiz tuaj. Në thelb si nuk kemi shtytje mbi majën e një pirg. Shumë e thjeshtë. Nëse ju shikoni në atë, ne do të ecin nëpër këtë. Në qoftë se [e padëgjueshme] size-- mos harroni, kur ju duan për të hyrë në ndonjë parametër brenda një struct, ju bëni emrin e struct.parameter. 

Në këtë rast, është s emri i rafte tonë. Ne duam për të hyrë në madhësinë e saj, kështu që ne bëjmë s.size. Pra, për aq kohë sa madhësia nuk është barabartë me kapacitetin ose për aq kohë pasi kjo është më pak se kapaciteti, ose do të punojë këtu. 

Ju doni të hyni brenda i rafte tuaj, kështu s.strings, dhe ju jeni duke shkuar për të vënë atë numër të ri që ju doni të futur në atje. Le të them vetëm ne do të duan të futur int n mbi rafte, ne mund të bëjmë s.strings, kllapa, s.size barabartë n. Sepse madhësia është ku ne aktualisht janë në rafte në qoftë se ne jemi duke shkuar për të nxitur ajo mbi, ne vetëm të hapur kudo që madhësia është, plotësia i tanishëm i rafte, dhe ne shtytje int n mbi atë. Dhe pastaj ne duam të sigurohemi që ne jemi gjithashtu bën rritjen madhësinë e n, kështu që ne mund të ruaj gjurmët e ne kemi shtuar një gjë shtesë për të rafte. Tani ne kemi një madhësi më të madhe. A ka kjo këtu kuptim për të gjithë, si logjikisht funksionon? Ajo ishte lloj i shpejtë. Audienca: A mund të shkoni mbi të s.stringss.strings [s.size] përsëri? ANDI Peng: Sigurisht, kështu që çfarë bën s.size aktualisht na jep? Audienca: Është madhësia e tanishme. ANDI Peng: Pikërisht, kështu që Indeksi i tanishëm se madhësia tonë është në, dhe kështu ne duam të vënë integer ri që ne duam të futur në s.size. A ka kjo kuptim? Sepse s.strings, të gjitha që është është emri i vektorit. Të gjitha ajo është është qasja e Grup brenda struct tonë, dhe kështu që në qoftë se ne duam të vendosni n në atë indeks, ne vetëm mund të përdorni atë duke përdorur kllapa s.size. Ftohtë. 

Të gjithë të drejtë, pop, unë pseudokod atë për ju djema, por koncepti të ngjashme. A ka kjo kuptim? Nëse madhësia është më i madh se zero, atëherë ju e di se ju doni për të marrë diçka jashtë sepse në qoftë se madhësia nuk është më i madh se zero, atëherë ju nuk kanë asgjë në rafte. 

Kështu që ju vetëm duan për të ekzekutuar ky kod, ajo vetëm mund të pop në qoftë se ka diçka të pop. Pra, në qoftë se madhësia është më i madh se 0, ne minus madhësia. Ne pakësim madhësinë dhe pastaj të kthehen çdo gjë që është brenda saj, sepse nga popping, ne duam të Qasje çdo gjë që është ruajtur në indeks të sipërme të pirg. Gjithçka kuptim? Në qoftë se kam bërë se ju djema të shkruar këtë jashtë, do të ju djema të jetë në gjendje për të shkruar atë? OK, ju djema mund të luajnë rreth me të. Nuk shqetësohet nëse ju nuk e bëni atë. Ne nuk kemi kohë për të kodon ajo që sot, sepse ne kemi mori një shumë prej këtyre strukturave për të shkuar nëpër, por në thelb pseudokod, shumë, shumë të ngjashme për të nxitur. Vetëm ndiqni përgjatë logjikës. Sigurohuni që ju jeni duke hyrë në të gjitha Tiparet e struct tuaj të saktë. Po? 

Audienca: Do këto slides dhe kjo gjë të jetë deri sot, ish? ANDI Peng: Gjithmonë, yep. Unë do të përpiqet për të vënë kjo lart si një orë pas. Unë do të email Davidin, edhe Davidi do të përpiqet të vënë atë si një orë pas kësaj. 

OK, kështu që atëherë ne shkojmë në këtë tjetrin Struktura e bukur e të dhënave të quajtur një radhë. Siç ju djema mund ta shikoni këtu, një radhë, për britanikët mes nesh, gjithë kjo është është një linjë. Pra, në kundërshtim me atë ju mendoni se një pirg është, një radhë është pikërisht ajo që logjikisht ju mendoni se është. Është mbajtur nga rregullat e FIFO, i cili është i pari në, First Out. Nëse ju jeni i pari një në linjë, ju jeni i pari që vjen jashtë vijës. 

Pra, ajo që ne si për të thirrur këtë është dequeueing dhe enqueueing. Në qoftë se ne duam të shtoni diçka në radhë tonë, ne enqueue. Në qoftë se ne duam të dequeue, ose të marrë diçka larg, ne dequeue. 

Pra, e njëjta ndjenjë se ne jemi lloj i duke krijuar elemente fikse-size që ne mund të ruajë të sigurt gjëra, por ne gjithashtu mund të të ndryshojë, ku ne jemi duke e vendosur Parametrat brenda tyre në bazë të çfarë lloji të Funksionalitetin ne duam. Pra oxhaqet, kemi dashur të fundit një, N të jenë të parë një jashtë. Radhë është që ne duam gjëja e parë për të të jetë gjëja e parë jashtë. 

Pra, struct tipit përcaktojnë, si ju mund të shihni, kjo është pak më ndryshe nga ajo që ishte rafte sepse jo vetëm që ne kemi për të mbajtur gjurmët e ku madhësia është aktualisht, ne gjithashtu duam të mbajnë gjurmët e kokës si dhe ku ne aktualisht janë. Kështu që unë mendoj se është më e lehtë në qoftë se unë të tërheqë këtë ide. Pra, le të imagjinojmë ne kemi marrë një radhë, kështu që le të thonë se koka është e drejtë këtu. Kreu i linjës, le të them vetëm se është aktualisht atje, dhe ne duam të futur diçka në radhë. Unë jam duke shkuar për të thirrur madhësinë thelb është e njëjta gjë si bisht, fundi i kudo radhë juaj është. Le të thonë se madhësia është e drejtë këtu. 

Pra, si e bën një feasibly futur diçka në një radhë? Çfarë Indeksi i duam për të vendosur ku ne duam të futur në. Nëse kjo është fillimi i juaj radhë dhe ky është fundi i tij ose madhësia e saj, ku nuk kemi dëshironi të shtoni objektin e ardhshme? 

Audienca: [padëgjueshme] ANDI Peng: Pikërisht, ju doni të shtoni kjo në varësi të keni shkruar atë. Ose kjo është bosh ose se është bosh. Pra, ju doni të shtoni atë ndoshta këtu, sepse në qoftë se madhësia is-- nëse këto janë të gjitha plot, ju doni të shtoni atë të drejtë këtu, apo jo? 

Dhe kështu kjo është, ndërsa shumë, shumë thjeshtë, jo mjaft gjithmonë e saktë për shkak të diferencës kryesore në mes të një radhë dhe një pirg është se radhë mund të në fakt të manipulohen në mënyrë që ndryshimet kokë në varësi se ku ju doni fillimi i cue tuaj për të filluar. Dhe si rezultat, bisht tuaj është gjithashtu do të ndryshojë. Dhe kështu që të marrë një sy në ky kod tani. Si ju djema janë pyetur edhe për të shkruani jashtë në quiz, enqueue. Ndoshta ne do të flasim përmes pse përgjigja ishte ajo që ishte. 

Unë nuk mund të përshtaten mjaft këtë linjë në një, por në thelb kjo pjesë e kodit duhet të jetë në një linjë. Shpenzojnë si 30 sekonda. Hidhni një sy, dhe të shohim pse kjo është mënyra se është. 

Shumë, struct shumë të ngjashme, shumë, shumë strukturë e ngjashme si të mëparshme rafte me përjashtim të ndoshta një linjë e kodit. Dhe se një linjë e kodit përcakton funksionalitetin. Dhe me të vërtetë dallon një radhë nga një pirg. 

Çdokush duan të marrin një goditje me thikë në shpjegimin pse ju keni mori këtë gjë e komplikuar këtu? Ne e shohim kthimin e tonë modulus mrekullueshme mik. Si ju djema do të vijë së shpejti për të njohur në programimin, pothuajse në çdo kohë keni nevojë për diçka për të përfunduar rreth çdo gjë, modulus do të jetë mënyra për të bërë atë. Pra duke e ditur se, ka njeri të dua në përpjekje për të shpjeguar këtë linjë të kodit? Po, të gjitha përgjigjet janë pranuar dhe i mirëpritur. Audienca: A jeni duke folur me mua? ANDI Peng: Po. Audienca: Oh, jo keq. ANDI Peng: OK, kështu që le të ecin nëpër këtë kod. Pra, kur ju jeni duke u përpjekur për të shtoni diçka mbi një radhë, në rastin e bukur që ndodh koka të jetë e drejtë këtu, kjo është shumë e lehtë për ne për të vetëm të shkojnë deri në fund futur diçka, apo jo? Por pika e tërë e një radhë është se kreu në fakt mund dinamike të ndryshojë në varësi të ku ne dëshironi fillimi i q tonë që të jetë, dhe si, bishti i tillë është gjithashtu do të ndryshojë. 

Dhe kështu që të imagjinojmë se kjo nuk ishte e radhë, por kjo ishte radhë. Le të thonë se koka është e drejtë këtu. Le të thonë radhë ynë dukej si kjo. Në qoftë se ne të kërkuar për të zhvendosur ku fillimi i linjës është, le të thonë se ne u zhvendos kokën në këtë mënyrë dhe madhësive këtu. 

Tani ne duam të shtoni diçka për këtë radhë, por si ju djema mund të shihni, kjo nuk është aq e thjeshtë sa që vetëm shtoni çdo gjë që është pas madhësinë sepse atëherë ne të drejtuar nga caqet e array tonë aktuale. Ku ne duam me të vërtetë të shtoni është këtu. Kjo është bukuria e një radhë është se për ne, vizualisht ajo duket si vija shkon si kjo, por kur ruhet në një strukturë të dhënave, ata japin atë si si një cikël. Ai lloj i përfundon rreth në pjesën e përparme të njëjtën mënyrë që një vijë të përfundojë mund të rreth në varësi të kudo që ju duam të fillimi i vijës të jetë. Dhe kështu që nëse marrim një shikoni poshtë këtu, le të thonë se ne të kërkuar për të krijuar një Funksioni i quajtur enqueue. Ne kemi kërkuar për të shtuar int n në atë q. Nëse q.size q-- ne do të thërrasë se të dhënat tona structure-- nëse queue.size jonë nuk ka barabartë me kapacitet ose nëse kjo është më pak se kapaciteti, q.strings është array brenda q tonë. Ne jemi duke shkuar për të vendosur që barabarte me q.heads, që është e drejtë këtu, plus q.size modulus nga kapaciteti, e cila Na përfundojë përsëri rreth këtu. 

Pra, në këtë shembull, indeksi e kokës është 1, e drejtë? Indeksi i madhësisë është 0, 1, 2, 3, 4. Pra, ne mund të bëjmë 1 plus 4 modulus nga kapaciteti ynë e cila është 5. Çfarë na jep? Çfarë është indeksi që vjen nga kjo? 

Audienca: 0. 

ANDI Peng: 0, e cila ndodh të jetë e drejtë këtu, dhe kështu ne duam të jetë në gjendje për të futur në të drejtë këtu. Dhe kështu që ky ekuacion këtu lloj i vetëm punon me çdo numër në varësi se ku tuaj kokë dhe madhësia e juaj janë. Nëse ju e dini se çfarë ata gjërat janë, ju e dini saktësisht ku ju doni të futur çdo gjë që është pas radhë tuaj. A ka që e bëjnë kuptim për të gjithë? 

Unë e di llojin e trurit ngacmues sidomos pasi kjo erdhi si pasojë e quiz tuaj. Por shpresojmë të gjithë tani mund të kuptojnë pse kjo zgjidhje apo kjo Funksioni është mënyra se është. Çdokush pak e paqartë në se? NE RREGULL. 

Dhe kështu që tani, në qoftë se ju donte të dequeue, kjo është ku kreu ynë do të jetë i ndryshueshëm sepse në qoftë se ne do të dequeue, ne nuk do të marrë jashtë në fund të q. Ne duam për të marrë jashtë në kokë, e drejtë? Pra, si rezultat, koka do të ndryshojë, dhe kjo është arsyeja pse kur ju enqueue, ju keni marrë për të mbajtur gjurmët e ku koka juaj dhe madhësia juaj duhet të jenë në gjendje për të futur në pozicionin e duhur. 

Dhe kështu që kur ju dequeue, Unë gjithashtu pseudokod atë. Ndjehen të lirë për në qoftë se ju doni në përpjekje për kodim këtë. Ju dëshironi për të lëvizur kokën, e drejtë? Në qoftë se unë të kërkuar për të dequeue, unë do të lëvizë kokën mbi. Kjo do të jetë koka. 

Dhe madhësia tonë aktuale do të zbres sepse ne nuk kanë katër elemente në rrjet. Ne kemi vetëm tre, dhe pastaj ne duam për të kthyer çdo gjë që ishte ruajtur brenda e kokës, sepse ne duam të marrin këtë Vlera e jashtë në mënyrë shumë të ngjashme me rafte. Vetëm ju jeni duke marrë nga një vend tjetër, dhe ju keni për të reassign treguesin tuaj në vend tjetër, si rezultat i kësaj. Logjikisht, të gjithë të ndjekin? I madh. 

OK, kështu që ne do të flasim pak më shumë në thellësi rreth listat e lidhura sepse ata do të jenë shumë, shumë të vlefshme për ju në rrjedhën e kësaj jave psets. Listat e lidhura, si ju djema mund të mbani mend, të gjithë ata janë janë nyje që janë nyjet e sigurt vlerat e të dy një vlerë dhe një akrep të cilat janë të lidhura bashkë nga këto pointers. Dhe kështu struct si ne krijojmë një nyje këtu është ne kanë int n, e cila është çfarëdo vlera në një dyqan apo string n apo çdo gjë që ju dëshironi të e quajti atë, ylli char n. Ylli nyje struct, që është tregues që ju dëshironi të keni në çdo nyje, ju jeni do të ketë atë Pika akrep drejt ardhshëm. Ju do të keni kokën nga një listë të lidhura që është do të tregojnë për pjesën tjetër të vlerat kështu me radhë dhe kështu me radhë deri sa ju përfundimisht të arritur në fund. Dhe kjo nyjë e fundit është vetëm do të mos ketë një akrep. Ajo do të tregojnë për null, dhe kjo është kur ju e dini që ju keni goditur fundi i listës suaj të lidhura është kur treguesin juaj e fundit nuk tregojnë për ndonjë gjë. 

Pra, ne jemi duke shkuar për të shkuar pak më në Thellësia në lidhje me se si do të ndoshta kërko një listë e lidhur. Mbani mend se çfarë janë disa nga meta e listave të lidhura vargjet një grup në lidhje me kërkimet. Një grup Ju mund të kërkoni binar, por pse nuk mund të bëni atë në një listë të lidhura? 

Audienca: Për shkak se ata janë të lidhur të gjithë, por ju nuk e mjaft e di ku [Padëgjueshme]. 

ANDI Peng: Po, pikërisht kështu që mos harroni se madhështia e një sërë ishte fakti se kemi pasur kujtesë e gjallë ku nëse kam kërkuar vlerën prej indeksit gjashtë, unë mund të them vetëm indeksi i gjashtë, më jep atë vlerë. Dhe kjo është për shkak se vargjeve janë të renditura në një hapësirë ​​puqur të kujtesës në një vend, ndërsa lloj i listave të lidhura janë rastësisht interspersed të gjithë rreth e rrotull, dhe e vetmja mënyrë ju mund të gjeni një të tillë është nëpërmjet një tregues që ju tregon adresa e ku se nyja tjetër është. 

Dhe kështu si rezultat, e vetmja mënyrë për për të kërkuar përmes një listë të lidhura është kërkimi lineare. Sepse unë nuk e di saktësisht se ku vlera 12 në lista e lidhur është, Më duhet të kaloj nëpër tërësinë e që lidhte një listë nga një nga koka deri në nyjen e parë, në nyjen e dytë, në nyjen e tretë, të gjithë rrugën poshtë derisa unë në fund të marrë ku se nyja Unë jam duke kërkuar për të është. Dhe kështu në këtë kuptim, kërko në një listë të lidhura është gjithmonë n. Është gjithmonë n. Është gjithmonë në kohë lineare. 

Dhe kështu kodi në të cilën ne zbatimin e kësaj, dhe kjo është pak i ri për ju djema Që ju djema nuk kam biseduar me të vërtetë në lidhje me, ose ndonjëherë pointers parë në se si të kërkuar nëpër pointers, kështu që ne do të ecin nëpër këtë shumë, shumë ngadalë. Pra kërko bool, e drejtë, le të imagjinojmë se ne duam për të krijuar një funksion të quajtur kërkim që jep true në qoftë se keni gjetur një vlerë brendësi të lidhur lista, dhe të kthehet false ndryshe. Lista yll Nyja është aktualisht vetëm akrep në pikën e parë në listën tuaj të lidhura. int n është vlera që ju jeni kërkim në atë listë. 

Pra yll nyje pointer barabartë listë. Kjo do të thotë që ne jemi vendosjen dhe krijimin e një akrep në atë nyje të parë brenda të listës. Çdokush me mua? Pra, në qoftë se ne ishim për të shkuar kthehen këtu, unë do të duhet nisur një tregues që tregon për kreu i çfarëdo që lista është. 

Dhe pastaj një herë ju merrni poshtë këtu, ndërsa tregues jo null barabartë, kështu që është lak në të cilën ne jemi të do të jetë më pas traversing pjesa tjetër e listës sonë sepse ajo ndodh kur akrep është e barabartë null? Ne e dimë se ne have-- 

Audienca: [padëgjueshme] 

ANDI Peng: Pikërisht, kështu që ne e dimë se ne kemi arritur në fund të listës, e drejtë? Nëse ju shkoni përsëri këtu, çdo nyjë duhet të vënë në një nyje dhe kështu me radhë e kështu me radhë derisa ju goditi përfundimisht bishti i listën tuaj të lidhura, e cila ka nje tregues që vetëm nuk pikë askund tjetër se jo. Dhe kështu që ju e dini se në thelb lista juaj ka ende lart deri akrep nuk barabartë null sepse një herë ajo është e barabartë null, ju e dini se nuk ka më shumë gjëra. 

Kështu që është lak në të cilën ne jemi do të ketë kërkimin aktuale. Dhe në qoftë se pointer-- e shihni ju se lloj i funksionit shigjetë? Pra, nëse pikat tregues për n, në qoftë se tregues në n barabartë barabartë n, kështu që do të thotë se në qoftë se tregues që ju jeni kërkuar për në fund të secilit Nyja është në fakt e barabartë me vlerën ju jeni duke kërkuar për të, atëherë ju duan të kthehen vërtetë. Pra, në thelb, në qoftë se ju jeni në një nyje që ka vlerën që ju po kërkoni, ju e dini se ju keni qenë gjendje për të kërkuar me sukses. 

Përndryshe, ju doni të vendosur treguesin tuaj në nyjen e ardhshëm. Kjo është ajo që linja këtu është duke bërë. Pointer barabartë me treguesin e ardhshëm. Të gjithë të shohin se si është duke punuar? 

Dhe në thelb ju do të jeni të vetëm përshkojnë tërësinë e listës, adaptimet treguesin tuaj çdo herë deri ju përfundimisht goditi në fund të listës. Dhe ju e dini se nuk ka më shumë nyje për të kërkuar nëpër, dhe pastaj ju mund të kthimit të rreme sepse ju e dini se, oh, mirë, në qoftë se unë kam qenë në gjendje për të kërkuar përmes tërësinë e listës. Në qoftë se në këtë shembull, nëse kam kërkuar për të kërkuar vlerën e 10, dhe unë të fillojë në krye, dhe Unë kërko të gjithë rrugën poshtë, dhe unë përfundimisht mori për këtë, të cilat një tregues që tregon null, Unë e di se, kar, unë mendoj 10 nuk është në kjo listë, sepse unë nuk mund të gjeni atë. Dhe Jam në fund të lista. Dhe në këtë rast ju e dini Unë jam duke shkuar për të kthehen rreme. 

Lejoni që të zhytem në për pak. Kjo do të jetë goxha i rëndësishëm për pset tuaj. Logjika e saj është shumë e thjeshtë, ndoshta sintaksore vetëm zbatimin e tij. Ju djema duan të bëjnë i sigurt që ju të kuptoni. Ftohtë. 

OK, kështu që si do të ishim futur nyje, e drejtë, në një listë, sepse mbaj mend çfarë janë çfarë e përfitimeve të paturit e një liste e lidhur kundrejt një grup në aspektin e magazinimit? 

Audienca: Kjo është dinamik, kështu që është e lehtë to-- 

ANDI Peng: Pikërisht, kështu që është dinamike, e cila do të thotë se ajo mund të zgjerohet dhe tkurret në varësi të nevojave të përdoruesit. Dhe kështu, në këtë kuptim, ne nuk kemi nevojë për të humbur kujtesën e panevojshme, sepse unë në qoftë se unë nuk e di se sa vlera që unë dua për të ruajtur, kjo nuk ka kuptim për mua për të krijuar një rrjet për shkak në qoftë se unë dua të ruajtur vlerat 10 dhe unë krijoj një grup prej 1000, që është një shumë e kujtesës tretur, të lëvruara. Kjo është arsyeja pse ne duam të përdorim një i lidhur Lista e të jetë në gjendje për të dinamike ndryshojë ose tkurret madhësinë tonë. 

Dhe kështu që e bën futje pak më e komplikuar. Që ne nuk mund rastësisht elemente të hyni mënyrë që ne do të një grup. Nëse unë dua të futur një element në indeksin e shtatë, Unë vetëm mund të futni atë në indeksin e shtatë. Në një listë të lidhura, nuk ka mjaft punë aq lehtë, dhe kështu që nëse ne të kërkuar për të futur ai këtu në listën e lidhur, vizualisht, kjo është shumë e lehtë për të parë. Ne vetëm duam të futur atë të drejtë atje, të drejtë në fillim të listës, menjëherë pas kokës. 

Por mënyra në të cilën ne duhet të reassign pointers është pak i ndërlikuar ose, logjikisht, kjo ka kuptim, por ju doni të bëni të sigurtë që ju të keni atë tërësisht poshtë për shkak se gjëja e fundit që ju doni është për të reassign një akrep mënyrë që ne jemi duke bërë këtu. Në qoftë se ju dereference treguesin nga koka në 1, pastaj të gjithë një e papritur Pjesa tjetër e listës suaj të lidhura është e humbur për shkak se ju nuk keni të vërtetë krijoi një gjë të përkohshme. Kjo është theksuar në 2. Nëse ju reassign treguesin, atëherë Pjesa tjetër e listës suaj është e humbur plotësisht. Pra, ju doni të jetë shumë, shumë të kujdesshëm këtu që së pari të caktojë akrep nga çdo gjë që doni të futur në kudo ju dëshironi, dhe pastaj ju mund dereference pjesën tjetër të listës suaj. 

Pra, kjo vlen për kudo ju jeni duke u përpjekur për të futur në. Nëse ju doni të futur në nivel kokë, në qoftë se ju doni të përgjigjem këtu, në qoftë se ju doni të futur në fundi, edhe, fundi unë mendoj se ju do të vetëm nuk kanë treguesin, por ju doni të bëni të sigurtë që ju nuk e bëni humb pjesën tjetër të listës suaj. Ju gjithmonë doni të bëni të sigurtë nyje tuaj të re është treguar ndaj çdo gjë që ju doni të futur në, dhe pastaj ju mund të shtoni në chaining. Gjithkush qartë? 

Kjo do të jetë një nga çështjet reale. Një nga çështjet më të mëdha ju jeni do të ketë në pset tuaj është se ju jeni do të përpiqen për të krijuar një listë e lidhur dhe gjëra insert por pastaj vetëm të humbasin Pjesa tjetër e listës suaj të lidhura. Dhe ju jeni do të jetë si, unë nuk e di pse kjo po ndodh? Dhe kjo është një dhimbje për të shkuar nëpërmjet dhe kërko të gjitha tuaj pointers. 

Dhe unë ju garantoj për këtë pset, shkrim dhe vizatim këto nyje jashtë do të jetë shumë, shumë e dobishme. Kështu që ju mund të mbani plotësisht gjurmët e ku të gjitha tua pointers janë, çfarë po ndodh gabuar, ku të gjitha nyjet tuaja janë, çfarë ju duhet të bëni për të hyrë ose futur apo fshij apo ndonjë prej tyre. Gjithkush mirë me atë? Ftohtë. 

Pra, nëse ne të kërkuar për të shikoni në kodin? Oh, unë nuk e di nëse ne mund të shihni the-- OK, kështu që në krye të gjitha ajo është një funksion insert i quajtur ku ne duam për të futur int n në listën e lidhur. Ne jemi duke shkuar për të ecin nëpër këtë. Kjo është një shumë e kodit, një shumë e sintaksës së re. Ne do të jetë në rregull. 

Pra, deri në krye, kurdoherë ne duam të krijojnë asgjë çfarë duhet të bëjmë, veçanërisht nëse ju duan që ajo të mos jetë i ruajtur në rafte por në tog? Ne do të shkojmë në një malloc, e drejtë? Pra, ne jemi duke shkuar për të krijuar një akrep. Nyje, akrep, është e barabartë e reja malloc madhësinë e një nyje sepse ne duam që nyje të krijohen. Ne duam sasinë e kujtesës që një nyje merr që të jepen për Krijimi i nyjen ri. 

Dhe pastaj ne jemi duke shkuar për të kontrolluar të të shohim nëse barabartë reja barabartë null. Mbani mend se çfarë kemi thënë? Çfarëdo që ju malloc, Çfarë duhet të ju gjithmonë bëni? Ju gjithmonë duhet të kontrolloni për të parë nëse janë apo jo kjo është null. 

Për shembull, në qoftë se operativ juaj sistemi ishte krejtësisht i plotë, në qoftë se keni pasur asnjë më shumë memorie në të gjithë dhe ju përpiqeni të malloc, ajo do të kthehet null për ju. Dhe kështu që nëse ju përpiqeni të përdorni atë kur ajo ishte duke treguar për null, ju nuk do të jeni në gjendje për të hyrë në këtë informacion. Dhe kështu si i tillë, ne të kërkuar për të bërë i sigurt se sa herë që ju jeni mallocing, ju jeni gjithmonë duke kontrolluar për të parë nëse se kujtesa dhënë për ju është i pavlefshëm. Dhe në qoftë se kjo nuk është, atëherë ne mund të lëvizin në me pjesën tjetër të kodit tonë. 

Pra, ne jemi duke shkuar për nisja nyjen e ri. Ne jemi duke shkuar për të bërë n e re është e barabartë me n. Dhe pastaj ne jemi duke shkuar për të bërë seri e re treguesin mbi re të null sepse tani për tani ne nuk e bëjmë duan asgjë që ajo të tregojnë për. Ne nuk kemi asnjë ide se ku mund ajo do të vënë ju, dhe pastaj në qoftë se ne duam të futur atë në krye, atëherë ne mund të reassign tregues në kokë. A të gjithë e ndjekin logjikën e ku kjo po ndodh? 

Të gjithë ne jemi duke bërë është duke krijuar një të ri nyje, vendosjen treguesin për të null, dhe pastaj reassigning ajo në kokë nëse ne e di se ne duam të futur atë në krye. Dhe pastaj kreu do të pikë ndaj kësaj nyje të re. Gjithkush në rregull me atë? 

Kështu që është një proces me dy faza. Ju keni marrë të caktojë parë çdo gjë që ju jeni duke krijuar. Bëje këtë tregues për referencë, dhe pastaj ju mund lloj i dereference në treguesin e parë dhe pikë atë drejt nyjen e ri. Kudo që ju dëshironi për të futur atë, se logjika do të mbajë e vërtetë. 

Kjo është lloj i si caktimin e variablave të përkohshme. Mbani mend, ju keni marrë për të siguruar që ju mos e humbni gjurmët e nëse ju jeni shkëmbejnë. Ju dëshironi të bëni të sigurtë që ju keni një variabël e përkohshme që lloj i mban gjurmët e ku ajo gjë është ruajtur në mënyrë që ju të mos e humb ndonjë vlerë në kursin e si messing rreth me të. 

OK, kështu që kodi do të jenë këtu. Ju djema hidhini një sy pas seksion. Ajo do të jetë atje. 

Kështu që unë mendoj se si e bën kjo ndryshojnë nëse ne të kërkuar për të futur në mes ose në fund? A ka dikush një ide se çfarë është pseudokod si referencë logjik që ne do të marrë në qoftë se ne të kërkuar për të futur atë në mes? Pra, nëse ne të kërkuar për të futur atë në nivel kokë, të gjithë ne bëjmë është të krijojë një nyje të re. Ne kemi vendosur treguesin e që nyje e re për çfarëdo kokë, dhe pastaj ne kemi vendosur kokën në nyjen e re, e drejtë? Nëse ne të kërkuar për të futur atë në mes e listës, çka do të duhet të bëjmë? 

Audienca: Ajo do të ende të jetë një proces i ngjashëm e si caktimin treguesin dhe pastaj caktimin se treguesin, por ne do të duhet për të gjetur atje. 

ANDI Peng: Pikërisht, kështu që pikërisht i njëjti proces përveç teje duhet për të gjetur se ku pikërisht ju duan që tregues të ri për të shkuar në, kështu që në qoftë se unë dua të futur në mes të lidhur list-- OK, le të themi se është lista jonë e lidhur. Në qoftë se ne duam të futur atë të drejtë këtu, ne jemi duke shkuar për të krijuar një nyje të re. Ne jemi duke shkuar për malloc. Ne jemi duke shkuar për të krijuar një nyje të re. Ne jemi duke shkuar për të caktojë tregues i kësaj nyje këtu. 

Por problemi që ndryshon nga ku koka është është se ne e dinim saktësisht ku koka është. Ajo ishte e drejtë në fillim, apo jo? Por këtu ne kemi marrë për të mbajtur nën e ku ne jemi futur atë në. Nëse ne jemi të futur tonë nyje këtu, ne kemi marrë për të siguruar që një mëparshme për këtë nyje është ai që reassigns treguesin. Pra, atëherë ju duhet të lloj ndiek dy gjëra. Në qoftë se ju mbani gjurmët e ku ky nyjeve aktualisht është futur në. Ju gjithashtu duhet të mbajnë gjurmët e ku nyja mëparshme që ju jeni duke kërkuar në ishte edhe atje. Gjithkush mirë me atë? NE RREGULL. 

Si për të futur në fund? Në qoftë se unë të kërkuar për të shtuar se here-- nëse kam kërkuar për të shtuar një nyje të re në fund të listës, Si mund të shkoj për të bërë atë? Audienca: Pra Aktualisht, vuri një e kaluar për të null. ANDI Peng: Po. Pikërisht, kështu që kjo aktualisht është theksuar të dini, dhe kështu që unë mendoj, në këtë kuptim, është e shumë e lehtë për të shtuar në fund të listës. Të gjithë ju duhet të bëni është vendosur atë barabartë me pavlefshme dhe pastaj bum. Ka të drejtë, shumë e lehtë. Shumë e thjeshtë. 

Shumë e ngjashme me kokë, por logjikisht ju dëshironi të bëni të sigurtë që hapat ju merrni në drejtim të bërë ndonjë të kësaj, ju jeni pas së bashku. Është shumë e lehtë për të, në mes e kodit tuaj, merrni të kapur deri në, oh, unë kam marrë kaq shumë pointers. Unë nuk e di se ku çdo gjë është duke treguar. Unë nuk e di edhe që nyje unë jam në. Çfarë po ndodh? 

Relax, të qetësuar, të marrë një frymë thellë. Draw jashtë listën tuaj lidhur. Nëse ju them, unë e di se ku saktësisht Unë kam nevojë për të futur këtë në dhe unë e di saktësisht se si të reassign tim pointers, shumë, shumë më e lehtë për foto out-- shumë, shumë më e lehtë që të mos merrni humbur në të mete të kodit tuaj. Gjithkush në rregull me atë? NE RREGULL. 

Kështu që unë mendoj një koncept që nuk e kemi me të vërtetë biseduar rreth më parë tani, dhe unë mendoj se ju ndoshta nuk do të hasni yet-- shumë kjo është lloj i një concept-- avancuar është se ne fakt kemi një të dhënave Struktura e quajti një listë e lidhur dyfish. Pra, si ju djema mund të shihni, të gjithë ne jemi duke bërë është duke krijuar një vlerë aktuale, një shtesë tregues në secilin nga nyjet tona që gjithashtu tregon për nyjen e mëparshëm. Pra, jo vetëm që ne kemi tonë nyjet tregojnë për një tjetër. Ata gjithashtu tregojnë për një mëparshme. Unë jam duke shkuar për të injorojë këto të dyja të drejtë tani. 

Pra, atëherë ju keni një zinxhir që mund të lëvizin dy mënyra, dhe pastaj kjo është pak më e lehtë për logjikisht ndjekin së bashku. Si këtu, në vend të mbajtja e, oh, unë duhet ta dini se kjo nyje është ajo që unë duhet të reassign, Unë vetëm mund të shkoni këtu dhe vetëm tërheq mëparshme. Atëherë unë e di saktësisht se ku që është, dhe pastaj ju nuk duhet të kaloj nëpër tërësia e listës së lidhur. Kjo është pak më e lehtë. 

Por, si i tillë, ju keni dyfish shuma e pointers, që është dyfishi i shumës e kujtesës. Kjo është një shumë e pointers të mbajnë gjurmët e. Kjo është pak më komplekse, por kjo është pak më shumë përdorues miqësore në varësi në atë që ju jeni duke u përpjekur për të kryer. 

Pra, ky lloj i të dhënave Struktura tërësisht ekziston, dhe struktura për të është shumë, shumë thjeshtë me përjashtim të të gjithë ju jeni të paturit është, në vend të vetëm një tregues për tjetër, edhe ju keni një tregues për paraardhëse. Kjo është e gjitha ndryshim ishte. Gjithkush mirë me atë? Ftohtë. 

Të gjithë të drejtë, kështu që tani unë jam i të vërtetë të shpenzojnë ndoshta si 15 deri në 20 minuta ose pjesën më të madhe e pjesa tjetër e kohës në seksionin duke folur për tabelat hash. Sa nga ju djema kanë lexuar spekulim pset5? Të gjithë të drejtë, të mirë. Kjo është më e lartë se 50% të normalisht. Eshte mire. 

Pra, si ju djema do të shihni, ju jeni sfidë në pset5 do të jetë për të zbatuar një fjalor ku ju ngarkesës mbi 140,000 fjalët që ne të ju jap dhe spell check ajo kundër të gjithë tekstin. Ne do të ju jap të rastit pjesë e letërsisë. Ne do të ju jap Odisea. Ne do të ju jap Iliada. Ne do të ju jap Austin Powers. 

Dhe sfida juaj do të jetë për të spell check çdo fjalë e vetme në të gjithë nga ato fjalorë në thelb me spell checker tonë. Dhe kështu ka disa pjesë i krijuar këtë pset, së pari ju duan të jenë të gjendje që në fakt ngarkesës të gjitha fjalët në tuaj fjalor, dhe pastaj ju duan të jenë në gjendje të spell check gjithë ata. Dhe kështu si i tillë, ju jeni do të kërkojë një strukturë e të dhënave që mund ta bëni këtë shpejt dhe në mënyrë efikase dhe dinamike. 

Kështu që unë mendoj e lehtë mënyrë për të bërë këtë, ju ndoshta do të krijojë një grup, e drejtë? Mënyra më e lehtë e magazinimit është që ju mund të krijojë një rrjet të 140,000 fjalëve dhe vetëm vendin e tyre të gjithë atje dhe pastaj kaloj atyre nga kërkimi binar ose me zgjedhje ose not-- vjen keq që është klasifikim. Ju mund të lloj ato dhe pastaj kaloj ato nga kërkimi binar ose kërko vetëm lineare dhe vetëm fjalët përfundimtare, por kjo merr një sasi të madhe të kujtesës, dhe kjo nuk është shumë efikas. 

Dhe kështu që ne jemi duke shkuar për të filluar duke folur për mënyrat e marrjes koha jonë running më efikase. Dhe qëllimi ynë është për të marrë kohë konstante ku kjo është pothuajse si vargjeve, ku ju keni qasje menjëhershëm. Në qoftë se unë të kërkuar për të kërkuar për ndonjë gjë, Unë dua të jem në gjendje të vetëm, bum, gjeni atë saktësisht, dhe të tërheqë atë jashtë. Dhe kështu një strukturë në të cilën ne do të jemi duke u bërë shumë afër të jetë në gjendje për të hyrë në konstante kohë, kjo Holy Grail në programimin e vazhdueshme kohë është quajtur një tabelë hash. Dhe kështu Davidi u përmend më parë [Padëgjueshme] pak në leksion, por ne jemi duke shkuar për të vërtetë pikiatë të thellë në këtë javë në një copë që është në lidhje si një tabelë hash punon. 

Pra, mënyra se si një hash Punimet tavolinë, për shembull, nëse kam kërkuar për të ruajtur një bandë e fjalëve, një bandë e fjalëve në gjuhën angleze, Unë teorikisht mund të vënë banane, mollë, kivi, mango, palë, dhe pjepër të gjitha në vetëm një grup. Ata mund të të gjitha përshtatet në dhe të gjeni. Ajo do të jetë lloj i një dhimbje të kërkoni përmes dhe aksesit, por mënyra më e lehtë për të bërë këtë është se ne mund të krijojë në fakt një strukturë quhet një tabelë hash ku ne të hash. Ne të drejtuar të gjithë çelësat tona me anë një funksion hash, një ekuacion, që kthen të gjithë në një lloj i një vlere që atëherë ne mund të ruajë mbi në thelb një koleksion të listës lidhur. 

Dhe kështu që këtu, në qoftë se ne të kërkuar për të ruajtur fjalë anglisht, ne mund potencialisht të vetëm, unë nuk e bëj e di, nga ana e të gjitha letrat e para në një lloj të një numri. Dhe kështu, për shembull, nëse kam kërkuar Një të jetë sinonim me apple-- ose me indeksin e 0, dhe B të jetë sinonim me 1, ne mund të kemi 26 të hyra që vetëm mund të ruajë të gjitha letrat e të alfabeti që ne do të fillojë me. Dhe pastaj ne mund të kemi Apple në indeksin e 0. Ne mund të kemi banane në indeksin e 1, pjepër në indeksin e 2, dhe kështu me radhë e kështu me radhë. Dhe kështu nëse kam kërkuar për të kërkuar tavolinë dhe qasja ime hash mollë, Unë e di mollë fillon me një A, dhe unë e di saktësisht se ajo duhet të jetë dhe hash Tabela në indeksin 0 sepse e funksionit të caktuar më parë. 

Kështu që unë nuk e di, ne jemi të një program përdorues ku ju do të jetë i ngarkuar me nuk arbitrarily-- në mënyrë arbitrare, me duke u përpjekur për të menduar mendoj se e ekuacioneve të mira të jetë në gjendje për të përhapur nga të gjitha vlerat e tua në mënyrë që ata mund të lehtë qasjen ajo më vonë me si një ekuacion se ju vetë, e di. Pra, në kuptimin, nëse kam kërkuar për të shkuar në mango, unë e di, oh, ajo fillon me m. Ajo duhet të jetë në indeksin e 12. Unë nuk kam për të kërkuar përmes asgjë. Unë e di exactly-- unë mund të shkoj vetëm për të indeksi i 12 dhe të tërheqë atë jashtë. 

Gjithkush qartë se si një Funksioni Tabela Hash punon? Kjo është lloj i vetëm një grup më të ndërlikuar. Kjo është e gjitha ajo është. NE RREGULL. 

Kështu që unë mendoj se kemi drejtuar në kjo çështje e asaj që ndodh në qoftë se ju keni gjëra të shumta që të ju japin të njëjtin indeks? Pra, thonë funksionin tonë, të gjithë atë bëri ishte marrë se shkronjën e parë dhe të kthehet kjo në një përkatës 0 deri 25 indeksi. Kjo është krejtësisht në rregull në qoftë se ju keni vetëm një e secilit. Por e dyta se të filloni duke pasur më shumë, ju jeni do të ketë atë që quhet një përplasje. 

Pra, nëse unë të përpiqet për të futur të varrosur në një hash Tabela që tashmë ka banane në të, çfarë do të ndodhë kur ju përpiqeni për të futur atë? Gjëra të këqija për shkak se banane ekziston brenda indeksit që ju doni të ruajtur atë në. Berry lloj është si, ah, çfarë të bëj? Unë nuk e di se ku të shkojnë. Si mund ta zgjidhur këtë? 

Dhe kështu ju djema lloj do të shih bëjmë këtë gjë e ndërlikuar ku ne mund të lloj të vërtetë të të krijojë listën e lidhur në vargjeve tona. Dhe kështu që mënyra më e lehtë për të menduar për këtë, gjithë tabelë hash është një grup i listave të lidhura. Dhe kështu, në këtë kuptim, ju keni ky grup i bukur i pointers, dhe pastaj secili akrep në që vlera, në këtë indeks, në fakt mund të tregojnë për gjëra të tjera. Dhe kështu që ju të keni të gjitha këto të ndara zinxhirët vijnë off e një grup të madh. 

Dhe kështu që këtu, në qoftë se unë donte të futur kokrra të kuqe, Unë e di, OK, unë jam duke shkuar për të dhëna ajo përmes funksionit tim hash. Unë do të përfundojnë me indeksin e 1, dhe pastaj unë do të jetë në gjendje të ketë vetëm një mesin e vogël e kësaj gjigant fjalor 140,000-fjalë. Dhe atëherë unë vetëm mund të shikoni me 1/26 e kësaj. 

Dhe kështu atëherë unë vetëm mund të futni kokrra të kuqe para ose pas banane në këtë rast? Pas, e drejtë? Dhe kështu që ju jeni do të duan të futur këtë nyje pas banane, dhe kështu ju jeni duke shkuar për të futur në bisht të kësaj liste lidhur. Unë jam duke shkuar për të shkuar mbrapa në këtë rrëshqitje të mëparshme, kështu që ju djema mund të shihni se funksion hash punon. 

Pra funksion hash është ky ekuacion se ju jeni drejtimin lloj kontributin tuaj nëpër të marrë çfarëdo Indeksi ju doni të caktojë atë drejt. Dhe kështu, në këtë shembull, të gjithë kemi dashur për të bërë është të marrë letrën e parë, të kthehet që në një indeks, atëherë ne mund të ruajë që në funksion tonë hash. Të gjithë ne jemi duke bërë këtu është se ne jemi konvertimin letrën e parë. Pra keykey [0] është vetëm shkronja e parë i çfarëdo string ne jemi të pasur, ne jemi duke kaluar në. Ne jemi konvertimin që të sipërme, dhe ne jemi duke zbritur nga uppercase A, kështu që të gjitha që po bën po na dhënë një numër në të cilën ne mund të hash vlerat tona mbi. 

Dhe pastaj ne jemi duke shkuar për kthehen hash SIZE modulus. Të jetë shumë, shumë të kujdesshëm sepse, teorikisht, këtu Vlera juaj hash mund të jetë i pafund. Ajo vetëm mund të shkoj në dhe mbi dhe. Kjo mund të jetë një të vërtetë, me të vërtetë me vlerë të madhe, por për shkak tryezën tuaj hash se keni krijuar vetëm ka 26 tregues, ju doni të bëni të sigurtë tuaj modulusing kështu që ju mos run-- kjo është e njëjtë gjë si queue-- tuaj kështu që ju nuk do të kandidojë jashtë fund të funksionit tuaj hash. 

Ju doni që të përfundojë atë rreth në të njëjtën mënyrë në [e padëgjueshme] kur keni pasur si një shumë, letër shumë të mëdha, ju nuk duan që të vetëm ik fund. E njëjta gjë këtu, ju doni të bëni të sigurtë kjo nuk do të ik fund nga ambalazhi rreth në majë të tabelës. Pra, kjo është vetëm një shumë Funksioni i thjeshtë hash. Të gjitha që bëra ishte marrë i pari Letra e çfarëdo input tonë ishte dhe të kthehet kjo në një indeks që ne mund të vënë në tryezën tonë hash. 

Po, dhe kështu siç kam thënë më parë, mënyrë që ne të zgjidhur goditjet në hash tonë tavolina janë të pasur, atë që ne e quajmë, chaining. Pra, nëse ju përpiqeni për të futur të shumta Fjalët që fillojnë me të njëjtën gjë, ju jeni do të ketë një vlerë të hash. Avocados dhe mollë, në qoftë se ju keni drejtuar atë nëpërmjet funksionit tonë hash, do të ju jap Numri i njëjtë, numri i 0. Dhe kështu mënyra se si të zgjidhur se është që ne mund në fakt lloj i lidhjen e tyre së bashku nëpërmjet listave të lidhura. 

Dhe kështu në këtë kuptim, ju djema mund të shihni lloj se si strukturat e të dhënave që ne kemi qenë ngritjen më parë si një lloj listën rrushi i lidhur të mund të vijnë së bashku në një. Dhe pastaj ju mund të krijoni shumë struktura më efektive të të dhënave që mund të trajtojë sasi më të mëdha të të dhëna, se dinamike resize në varësi mbi nevojat tuaja. Gjithkush qartë? Lloj Gjithkush i qartë mbi atë që ndodh këtu? 

Në qoftë se unë të kërkuar për të insert-- çfarë është një fruta që fillon me, unë nuk e di, B, përveç Berry, banane. 

Audienca: Blackberry. 

ANDI Peng: Blackberry, ferrë. Ku ferrë shkoni këtu? E pra, ne fakt nuk kemi të renditura sipas kjo, por teorikisht nëse kemi dashur të kemi këtë në rend alfabetik, ku duhet të BLACKBERRY shkoni? 

Audienca: [padëgjueshme] 

ANDI Peng: Pikërisht, pasi këtu, apo jo? Por, pasi ajo është shumë e vështirë për reorder-- unë mendoj se është deri në ju djema. Ju djema mund të krejtësisht të të zbatojë çdo gjë që ju dëshironi. Mënyra më efikase për të bërë këtë ndoshta do të jetë për të zgjidhur lidhur juaj lista në rend alfabetik, dhe kështu kur ju jeni futur gjëra, ju doni të jetë i sigurt për të futur ato në rend alfabetik në mënyrë që atëherë kur ju jeni duke u përpjekur për të kërkuar ato, ju nuk duhet të kaloj nëpër gjithçka. Ti e di saktësisht se ku ajo është, dhe është më e lehtë. 

Por në qoftë se ju lloj i kanë gjëra interspersed rastësisht, ju jeni ende do të ketë të kaloj nëpër atë anyways. Dhe kështu që në qoftë se unë të kërkuar për të vetëm futur ferrë këtu dhe kam kërkuar për të kërkuar për ajo, unë e di, oh, ferrë duhet të fillojë me indeksin e 1, kështu që unë e di menjëherë kërko vetëm në 1. Dhe atëherë unë mund të lloj kaloj listën e lidhur deri sa unë të shkoj në ferrë, dhe then-- vërtet? 

Audienca: Nëse ju jeni duke u përpjekur për të create-- Unë mendoj se si kjo është një hash shumë e thjeshtë funksion. Dhe në qoftë se kemi dashur të bëjmë shtresa të shumta të atij si, OK, ne duam të ndarë në si të gjitha letrat alfabetike dhe pastaj përsëri për të si një tjetër grup i letrave alfabetike brenda se, jemi duke si një hash Tabela brenda një tryezë hash, ose si një funksion brenda një funksion? Apo është that-- 

ANDI Peng: Pra hash tuaj function-- tryezën tuaj Hash mund të jetë aq i madh sa ju dëshironi që ajo të. Pra, në këtë kuptim, kam menduar ajo ishte shumë e lehtë, shumë thjeshtë për mua të bazuar vetëm lloj në shkronjat e fjalës së parë. Dhe kështu që nuk ka vetem 26 opsione. Unë mund të merrni vetëm 26 opsionet nga 0 në 25, sepse ata mund vetëm të fillojë nga A në Z., por nëse ju të kërkuar për të shtuar, ndoshta, më shumë kompleksitet ose më të shpejtë të drejtuar kohë për të tuaj tabelë hash, ju absolutisht mund të bëjë të gjitha llojet e gjërave. Ju mund të bëni tuaj Ekuacioni që ju jep më shumë shpërndarjes në tuaj fjalë, atëherë kur ju kërkoni, ajo do të jetë më i shpejtë. 

Është plotësisht deri në ju djema si ju doni për të zbatuar atë. Mendoni se si vetëm kova. Nëse do të doja që të ketë 26 kova, unë jam duke shkuar për të zgjidhur gjërat në ato kova. Por unë jam do të ketë një bandë e gjëra në çdo kovë, kështu që në qoftë se ju doni të bëni atë të shpejtë dhe më efikase, më lejoni të ketë njëqind kova. 

Por pastaj ju duhet të kuptoj se një mënyrë për të zgjidhur gjërat në mënyrë që ata janë të në kovë e duhur ata duhet të jenë në. Por, atëherë kur në fakt dëshironi të shikoni në atë kovë, kjo është një shumë më të shpejtë, sepse nuk ka më pak gjëra në çdo kovë. Dhe kështu, vërtet, kjo është në fakt mashtrim për ju djema në pset5 është se ju do të jetë sfiduar të vetëm të krijojë çdo gjë që është më efikas funksion ju mund të mendoni për të qenë gjendje për të ruajtur dhe kontrolluar këto vlera. 

Krejtësisht deri në ju djema megjithatë ju doni të bëni atë, por kjo është një pikë të vërtetë të mirë. Se lloj i logjikës ju duan të fillojnë të mendojnë për është, mirë, pse nuk e kam bërë më shumë kova. Dhe atëherë unë kam për të kërkuar pak gjëra, dhe pastaj ndoshta unë kanë një funksion të ndryshëm hash. 

Po, ka shumë mënyra për të bërë këtë pset, disa janë më të shpejtë se të tjerët. Unë jam tërësisht duke shkuar për të parë se sa shpejt ishte më e shpejtë ju djema do të të jetë në gjendje për të marrë funksionet tuaja në punë. OK, të gjithë në të mirë chaining dhe tavolina hash? Është në fakt si një shumë e thjeshtë koncept në qoftë se ju mendoni rreth saj. Të gjitha ajo është është e ndan çfarëdo inputet tuaja janë në kova, zgjidhja e tyre, dhe pastaj në kërkim liston se nuk është e lidhur me. 

Ftohtë. Në rregull, tani ne kemi një lloj të ndryshëm i strukturës së të dhënave që quhet një pemë. Le të shkojnë në dhe të flasim për përpiqet të cilat janë dukshëm të ndryshme, por në të njëjtën kategori. Në thelb, të gjithë një pemë është vend e organizimin e të dhënave në mënyrë lineare se një tabelë hash does-- ju e di, atë e mori një top dhe një fund dhe pastaj ju lloj i lidhin off e it-- një pemë ka një top të cilin ju e quani rrënjë, dhe pastaj ajo ka gjethe të gjithë rreth tij. 

Dhe kështu që të gjithë ju duhet këtu është vetëm nyja krye që tregon për nyjet e tjera, që pikat në më shumë nyje, dhe kështu me radhë e kështu me radhë. Dhe kështu që ju vetëm duhet degët ndarjen. Kjo është vetëm një mënyrë të ndryshme të organizimit të dhënave, dhe sepse ne e quajmë atë një pemë, ju djema just-- kjo është vetëm modeluar nga të duket si një pemë. Kjo është arsyeja pse ne e quajmë atë pemë. 

Tabelë Hash duket si një tryezë. Një pemë vetëm duket si një pemë. Të gjitha ajo është është një rast i veçantë mënyra e organizimit nyje në varësi të çfarë janë nevojat tuaja. 

Pra, ju keni një rrënjë dhe atëherë ju keni gjethe. Mënyra që ne mund veçanërisht Mendoni se ajo është një pemë binare, një pemë binare është vetëm një lloj specifik i një pemë ku çdo nyje vetëm pikë për të, në max, dy nyje tjera. Dhe kështu që këtu ju keni të dallueshme simetri në pemë tuaj që e bën më të lehtë për lloj të duken në çfarë vlerat jeni sepse atëherë ju kanë gjithmonë një majtas apo djathtas. Ka kurrë nuk është si një të tretën e majtë nga majtas ose i katërti nga e majta. Është vetëm ju keni një majtë dhe të drejtën dhe ju mund të kërkoni ose të atyre dyve. Dhe kështu që pse është kjo e dobishme? Mënyra se kjo është e dobishme është nëse ju jeni në kërkim për të kërkuar përmes vlerave, e drejtë? Në vend se zbatimin binare kërko në një rrjet gabim, nëse do të donit që të jetë në gjendje për të futur nyje dhe për të marrë larg nyjet në vullnetin dhe gjithashtu ruajnë kërkimin Kapacitetet e kërkimit binar. Pra, në këtë mënyrë, ne jemi lloj i tricking-- kujtohet kur ne tha se listat e lidhura nuk mund kërkimin binar? Ne jemi lloj i krijimit të një strukture të dhënave se truket që në pune. 

Dhe listat kështu për shkak se janë të lidhura lineare, ata vetëm lidhin njëri pas tjetrit. Ne mund të lloj të kenë lloj të ndryshme të pointers që tregojnë për nyjet e ndryshme që mund të na ndihmojë me kërkimin. Dhe kështu që këtu, në qoftë se unë të kërkuar për të kanë një pemë kërkimi binar, Unë e di se mes time nëse 55. Unë jam vetëm duke shkuar për të krijuar atë si mes time, si rrënjë e mia, dhe pastaj unë do të ketë Vlerat spin off e saj. 

Kështu që këtu, në qoftë se unë jam duke shkuar për të kërkuar për vlera e 66, unë mund të fillojnë në 55. Është 66 më të madh se 55? Po ajo është, kështu që unë e di unë mbesë kërkoni ni tregues i duhur i kësaj peme. Unë shkoj në 77. Rregull, është më pak se 66 ose më i madh se 77? Kjo është më pak se, kështu që ju e dini, oh, që duhet të jetë nyje majtas. 

Dhe kështu që këtu ne jemi lloj i ruajtjes të gjitha gjërat e mëdha për vargjeve, kështu si Resizing dinamike e objekteve, duke qenë në gjendje për të futur dhe fshini sipas dëshirës, pa pasur nevojë të shqetësuar në lidhje fikse Sasia e hapësirës. Ne ende ruajnë të gjithë këto gjëra të mrekullueshme ndërsa gjithashtu janë në gjendje për të ruajtur hyni dhe kërko kohën e kërkimit binar se ne kemi qenë vetëm parë gjendje për të marrë një frazë. 

Struktura e ftohtë të dhënave, lloj i komplekse për të zbatuar, nyjen. Siç mund ta shikoni, të gjithë atë është struct e nyjes është se ju keni një majtë dhe një akrep e drejtë. Kjo është e gjitha ajo është. Pra, në vend se vetëm që ka një x ose një paraardhëse. Ju keni një të majtë apo të drejtën, dhe pastaj ju mund të lloj i lidhin ato së bashku megjithatë kështu zgjedhin. 

OK, ne jemi të vërtetë do të marrë vetëm disa minuta. Pra, ne jemi duke shkuar për të shkuar përsëri këtu. Siç thashë më parë, Unë lloj i shpjegoi logjika prapa se si ne do të kërkoni përmes kësaj. Ne jemi duke shkuar për të provoni pseudocoding këtë për të parë në qoftë se ne mund të lloj të zbatohet e njëjta logjikë e kërkimit binar në një lloj të ndryshme të strukturës së të dhënave. Nëse ju djema doni të merrni si një çift minuta për vetëm mendojnë për këtë. NE RREGULL. Të gjithë të drejtë, unë jam duke shkuar për në fakt vetëm ju jap the-- jo, ne do të flasim për pseudokod parë. Pra, ka njeri të dua për të dhënë një goditje me thikë në atë gjëja e parë që ju doni të bëni kur ju jeni duke filluar nga jashtë në kërkim është? Nëse ne jemi duke kërkuar për vlera e 66, çfarë është gjëja e parë që ne duam të bëjmë nëse ne duam të binar të kërkuar këtë pemë? 

Audienca: Ju dëshironi të shikoni drejtë dhe do të shikojnë e majtë dhe të shohim [e padëgjueshme] numër i madh. 

ANDI Peng: Po, pikërisht. Pra, ju jeni do të shikojmë në rrënjë tuaj. Ka shumë mënyra që ju mund të telefononi ajo, njerëzit e tu nyja prind thonë. Më pëlqen të them rrënjë, sepse kjo është si rrënja e pemës. Ju jeni do të shikojmë në nyje tuaj rrënjë, dhe ju jeni shkuar për të parë është më i madh 66 se, ose më pak se 55. Dhe në qoftë se kjo është më e madhe se, mirë, kjo është e më e madhe se, ku do të dëshironi të shikoni? Ku duam të kërkoni tani, apo jo? Ne duam të kërkuar gjysma e drejta e kësaj peme. 

Pra, ne kemi, të përshtatshme, një tregues që tregon në të djathtë. Dhe kështu që atëherë ne mund të vënë rrënjë ynë i ri të jetë 77. Ne thjesht mund të shkoni kudo treguesi është vënë. E pra, oh, këtu ne jemi duke filluar në 77, dhe ne mund vetëm bëni këtë Recursively përsëri dhe përsëri. Në këtë mënyrë, ju lloj e kanë një funksion. Ju keni një mënyrë për të kërkuar që ju vetëm mund të përsërisë mbi dhe mbi dhe mbi, në varësi se ku ju doni të shikoni deri sa ju përfundimisht të shkoj në vlerën që ju jeni në kërkim për të. Ka kuptim? 

Unë jam gati për të treguar ju aktual kod, dhe kjo është një shumë të kodit. Nuk ka nevojë të trullos. Ne do të flasim nëpërmjet saj. 

Në fakt, nuk ka. Kjo ishte vetëm pseudokod. OK, kjo ishte vetëm pseudokod, i cili është një kompleks bit, por kjo është krejtësisht në rregull. Gjithkush pas së bashku këtu? Po të jetë rrënja është i pavlefshëm, kthimi false për shkak se mjetet e ju as nuk kanë asgjë atje. 

Nëse root n është vlera, kështu që nëse ajo ndodh të jetë një që ju jeni duke kërkuar në, atëherë ju jeni do të kthehen vërtetë sepse ju e dini se ju gjetur atë. Por nëse vlera është më e vogël se rrënja e n, ju jeni duke shkuar për të kërkuar të majtën fëmijë ose fletë të majtë, çdo gjë që ju doni të telefononi atë. Dhe në qoftë se vlera është më i madh se rrënjë, ju jeni duke shkuar për të kërkuar pemë të drejtë, atëherë vetëm të drejtuar funksionin përmes kërkoni përsëri. 

Dhe nëse rrënja është i pavlefshëm, se kjo do të thotë që ju keni arritur fundin? Kjo do të thotë ju nuk keni më shumë lë për të kërkuar, atëherë ju e dini, oh, unë mendoj se nuk është këtu sepse pasi unë e kam shikuar përmes të gjithë gjë dhe kjo nuk është këtu, ai thjesht nuk mund të jetë këtu. 

A ka që e bëjnë kuptim për të gjithë? Pra, kjo është si kërkim binar ruajtur aftësitë e listave të lidhura. Cool, dhe kështu lloji i dytë i strukturës së të dhënave që një vajzë mund të provoni zbatimin në pset tuaj, ju vetëm duhet të zgjedhin një metodë. Por ndoshta një metodë alternative për tabela hash është ajo që ne e quajmë një Trie. 

Të gjitha një Trie është është një lloj specifik i pemës që ka vlera që shkojnë për vlerat e tjera. Pra, në vend të paturit e një binar pemë në kuptimin që vetëm një gjë mund të tregojnë për dy, ju mund të keni pikë një gjë për të shumë, shumë gjëra. Ju në thelb kanë vargjeve brenda të cilave ju dyqan pointers që tregojnë për vargjeve të tjera. 

Kështu nyja se si ne do të përcaktojë një Trie është që ne duam të kemi një Boolean, c fjalë, e drejtë? Pra, nyja është Boolean si e vërtetë apo e rreme, para së gjithash në krye të se array, është kjo një fjalë? Së dyti, ju dëshironi të keni pointers për çfarëdo pjesa tjetër e tyre janë. Një kompleks pak, pak abstrakt, por Unë do të shpjegojë atë që të gjitha mjetet. 

Kështu që këtu, në krye, në qoftë se ju kanë një grup deklaruar tashmë, një nyje ku ju keni një Boolean Vlera e depozituara në pjesën e përparme që tregon se është kjo një fjalë? A nuk është kjo një fjalë? Dhe pastaj ju keni Pjesa tjetër e grup tuaj që në fakt ruan të gjitha mundësitë e asaj që mund të jetë. Kështu, për shembull, si në krye që ju keni gjëja e parë që thotë se e vërtetë ose false, po ose jo, kjo është një fjalë. 

Dhe pastaj ju keni 0 deri 26 letra që ju mund të ruajë. Në qoftë se unë të kërkuar për të kërkuar këtu për bat, unë shkoj në krye dhe unë shoh për B. unë gjej B në tim array, dhe kështu unë e di, në rregull, është B një fjalë? B nuk është një fjalë, kështu që në këtë mënyrë Unë duhet të mbaj në kërkim. Unë shkoj nga B, dhe unë shoh të tregues që tregon ndaj B dhe unë shoh një tjetër koleksion të informacionit, e njëjta strukturë që kemi pasur më parë. 

Dhe here-- oh, tjetër letër në [e padëgjueshme] është A. Pra, ne shikojmë në atë rrjet. Ne gjejmë vlerën e tetë, dhe pastaj ne sy për të parë, oh, hej, është se një fjalë, është B-A një fjalë? Kjo nuk është një fjalë. Ne kemi marrë për të mbajtur në kërkim. 

Dhe kështu atëherë ne shohim ku tregues i një pikë, dhe kjo tregon për një mënyrë tjetër në të cilat ne kemi më shumë vlerë të depozituara. Dhe në fund, ne të merrni të B-A-T, i cili është një fjalë. Dhe kështu që herën tjetër ju shikoni, ju do të jeni për të patur këtë kontroll e, po, ky funksion Boolean është e vërtetë. Dhe kështu në kuptimin që ne jemi lloj të paturit e një pemë me vargjeve. 

Pra, atëherë ju mund të lloj të kërkoni poshtë. Në vend se hashing një funksion dhe përcaktimin e vlerave nga lista e lidhur, ju mund të zbatojë vetëm një Trie që kërkon downwords. Me të vërtetë, të vërtetë të komplikuar gjëra. Nuk është e lehtë për të menduar rreth, sepse unë jam si pështyrë kaq shumë struktura të dhënave nga me ju, por bën të gjithë lloj i të kuptojnë se si logjika e kjo punon? 

OK, i ftohtë. Kështu B-A-T, dhe pastaj ju jeni duke shkuar për të kërkuar. Herën tjetër që ju jeni duke shkuar për të parë, oh, hej, kjo është e vërtetë, kështu unë e di se kjo duhet të jetë një fjalë. 

E njëjta gjë për kopshtin zoologjik. Kështu që këtu është gjë e drejtë tani, në qoftë se ne donte për të kërkuar për kopshtin zoologjik, tani, aktualisht zoo nuk është një fjalë në fjalorin tonë sepse, siç ju djema mund të shihni, Vendin e parë që ne kemi një Boolean kthimin e vërtetë është në fund të zoom. Ne kemi Z-O-O-M. 

Dhe kështu që këtu, ne nuk të vërtetë kanë fjala, kopsht zoologjik, në fjalorin tonë sepse kjo kuti kontrolloni nuk është i kontrolluar. Pra, kompjuteri nuk e di se kopshtit zoologjik është një fjalë sepse rruga që ne kemi ruajtur atë, vetëm një zoom këtu aktualisht ka një vlerë Boolean që është kthyer vërtetë. Pra, nëse ne duam të futur në Fjala, kopsht zoologjik, në fjalorin tonë, si do të shkojë për të bërë këtë? Çfarë duhet të bëjmë për të siguruar tonë kompjuter e di se Z-O-O është një fjalë dhe jo shprehja e parë është Z-O-O-M? 

Audienca: [padëgjueshme] 

ANDI Peng: Pikërisht, ne doni të bëni të sigurtë që ky këtu, që vlera Boolean është kontrolluar off se është e vërtetë. Z-O-O, atëherë ne jemi duke shkuar për të kontrolluar atë, kështu që ne e dimë saktësisht, hej, kopshtit zoologjik është një fjalë. Unë do të them të kompjuter se kjo është një fjalë aq se kur kontrollet kompjuterike, ajo e di se kopshtit zoologjik është një fjalë. 

Sepse mos harroni të gjitha këto të dhëna strukturave, është shumë e lehtë për ne për të thënë, oh, bat është një fjalë. Zoo është një fjalë. Zoom është një fjalë. Por kur ju jeni ndërtimin e saj, kompjuteri ka asnjë ide. 

Kështu që ju duhet të tregoni atë saktësisht në çfarë pike është kjo një fjalë? Në çfarë pike është kjo nuk është një fjalë? Dhe në atë pikë bëjë unë duhet të kërkoni gjëra, dhe në atë moment nuk kam nevojë të shkojnë tjetër? Gjithkush qartë se? Ftohtë. 

Dhe kështu pastaj vjen Problemi se si do të kemi shkoni në lidhje futur diçka që në fakt nuk është atje? Pra, le të thonë se vetëm ne duam të futur fjala, dush, në Trie tonë. Siç ju djema mund të shihni si aktualisht të gjithë ne kemi tani është B-A-T, dhe kjo strukturë e re e të dhënave atje kishte një pintë që vuri në dukje null sepse ne supozojmë se, oh, nuk ka asnjë fjalë pas B-A-T, pse nuk kemi nevojë për të mbajtur duke pasur gjërat pas kësaj T. 

Por problemi lind nëse ju bëjmë duan të kenë një fjalë që vjen pas T-së. Nëse keni dush, ju jeni do të duan një të drejtë H. Dhe kështu mënyrën se si ne jemi duke shkuar për të bërë këtë është ne jemi duke shkuar për të krijuar një nyje të veçantë. Ne nuk jemi të japë çfarëdo sasi e kujtesës për këtë grup të ri, dhe ne do të reassign pointers. 

Ne jemi duke shkuar për të caktojë H, Para së gjithash, kjo null, ne jemi duke shkuar për të hequr qafe. Ne do të kemi e poshtë pikë H. Nëse ne shohim një H, ne duam atë për të shkuar diku tjetër. 

Në këtu, atëherë ne mund të kontrolloni off po. Në qoftë se ne e goditi një H pas T, oh, atëherë ne e dimë se kjo është një fjalë. Boolean do të kthehen vërtetë. Gjithkush qartë se si ndodhi kjo? NE RREGULL. 

Pra, në thelb, të gjithë këto struktura të dhënave se ne kemi shkuar mbi sot, unë kam shkuar mbi ta me të vërtetë, me të vërtetë shpejt dhe jo në të shumë detaje, dhe kjo është në rregull. Pasi ju filloni messing me atë, ju do të jetë mbajtja e ku të gjitha pointers janë, çfarë po ndodh në tuaj strukturat e të dhënave, e të tjera. Ata do të jenë shumë të dobishme, dhe kjo e deri tek ju djema për të krejtësisht të kuptoj se si ju doni për të zbatuar gjëra. 

Dhe kështu pset4, i 5-- oh, kjo është e gabuar. Pset5 është misspellings. Siç kam thënë më parë, ju jeni duke shkuar për të, një herë përsëri, shkarko kodin burim nga ne. Nuk do të jetë tre kryesore gjëra që ju do të shkarkoni. Ju do shkarko fjalorë, kers, dhe tekste. 

Të gjitha këto gjëra janë të ose fjalorë të fjalëve që ne duam që ju të kontrolloni ose testi i informacionit që ne duam që ju të spell check. Dhe kështu fjalorë ne japim ju jeni duke shkuar për të ju jap fjalë aktuale që ne duam ju për të ruajtur disi në një mënyrë që është më efikas se një grup. Dhe pastaj tekstet janë do të jetë ajo që ne jemi duke kërkuar që të spell check për të siguruar të gjitha fjalët janë fjalë të vërteta. 

Dhe kështu tri blloqet e programe që ne do të ju jap quhen dictionary.c, dictionary.h dhe speller.c. Dhe kështu të gjithë dictionary.c nuk është çfarë jeni duke pyetur për të zbatuar. Ajo ngarkesa fjalë. Ajo magji kontrollon ato, dhe kjo e bën të sigurt se çdo gjë është futur siç duhet. 

diction.h është vetëm një skedar bibliotekë që deklaron të gjitha ato funksione. Dhe speller.c, ne jemi duke shkuar për të ju jap. Ju nuk keni nevojë për të ndryshuar ndonjë prej tij. Të gjitha speller.c nuk është marrë se, ngarkesa ajo, kontrollon shpejtësinë e tij, testet e reperit e si si shpejt ju jeni në gjendje të bëjë gjëra. 

Kjo është një Speller. Vetëm mos bela me të, por të bëjë i sigurt që ju të kuptoni se çfarë është bërë. Ne përdorim një funksion të quajtur getrusage se teston performancën e spell tuaj checker. Gjithë kjo nuk është në thelb të testuar koha e çdo gjë, në fjalorin tuaj, prandaj sigurohuni që ju të kuptoni atë. Të jenë të kujdesshëm për të mos bela me atë ose gjëra tjetër nuk do të kandidojë si duhet. 

Dhe pjesa më e madhe e kësaj sfide është për ju djema me të vërtetë të modifikuar dictionary.c. Ne jemi duke shkuar për të ju jap 140.000 fjalë në një fjalor. Ne jemi duke shkuar për të ju jap një tekst fotografi që ka këto fjalë, dhe ne duam që ju të jetë në gjendje për të organizuar ato në një tabelë hash apo Trie sepse kur ne ju kërkojmë të spell check-- imagjinoni nëse ju jeni magji duke kontrolluar si Odisea e Homerit. Është si këtë provë të madhe, e madhe. 

Paramendoni nëse çdo të vetme fjalë ju se të shikojë përmes një grup të 140,000 vlerave. Kjo do të marrë përgjithmonë për kompjuterin tuaj për të kandiduar. Kjo është arsyeja pse ne duam të organizojmë tonë të dhëna në strukturat më efikase të të dhënave si një tabelë Hash ose një Trie. Dhe pastaj ju djema mund të lloj e kur ju kërkoni qasje gjëra më lehtë dhe më shpejt. 

Dhe kështu të jenë të kujdesshëm për të zgjidhur goditjet. Ju jeni do të merrni një bandë e fjalët e këtij fillimi me A. Ju jeni do të merrni një fjalë bandë që fillojnë me B. Deri tek ju djema si ju doni për të zgjidhur atë. Ndoshta ka më shumë funksion efikas hash se vetëm shkronjës së parë të diçka, dhe kështu që është e deri tek ju djema të lloj bëni çfarë të doni. 

Ndoshta ju doni të shtoni të gjitha letrat së bashku. Ndoshta ju doni të pëlqen bërë gjëra të çuditshme në llogari numrin e shkronjave, cfaredo. Deri në ju djema si ju doni të bëni. Nëse ju doni të bëni një tabelë hash, në qoftë se ju dëshironi të provoni një Trie, krejtësisht e deri te ju. Unë do t'ju tregoj para kohe se Trie është zakonisht një pak më e vështirë vetëm për shkak se ka një shumë më shumë pointers për të mbajtur gjurmët e. Por krejtësisht e deri te ju djema. Kjo është shumë më efikase në shumicën e rasteve. Ju dëshironi që me të vërtetë të jetë në gjendje për të mbajtur gjurmët e të gjitha tuaj pointers. Ashtu si të bëjë të njëjtën gjë që unë isha bërë këtu. Kur ju jeni duke u përpjekur për të futur vlerëson në një tryezë të hash apo fshij, sigurohuni që ju jeni me të vërtetë mbajtja e ku çdo gjë është për shkak është e vërtetë e lehtë për të, nëse unë jam i duke u përpjekur për të futur si fjala, Andy. Le të them vetëm se është një Fjala e vërtetë, fjala, andy, në një listë gjigante e A fjalëve. 

Në qoftë se unë vetëm të ndodhë që të reassign një gabim akrep, Oops, atje shkon tërësinë e pjesa tjetër e listën time të lidhur. Tani vetëm Fjala e kam kanë është andy, dhe tani të gjitha fjalët e tjera në fjalor kanë qenë të humbur. Dhe kështu që ju doni të bëni të sigurtë që ju mbajnë gjurmët e të gjitha tuaj pointers ose tjetër ju jeni do të merrni probleme të mëdha në kodin tuaj. Draw gjërat me kujdes hap pas hapi. Kjo e bën atë një shumë më e lehtë të mendojnë për. 

Dhe së fundi, ju doni të jenë në gjendje të të testuar punën tuaj e programit tuaj në bordin e madhe. Në qoftë se ju djema të marrë një shikoni në CS50 tani, ne kemi atë që quhet bordi i madh. Kjo është fletë rezultati i më të shpejtë magji herë duke kontrolluar nëpër të gjitha CS50 tani, unë mendoj të lartë si 10 herë unë mendoj se tetë prej tyre janë të stafit. Ne me të vërtetë dua që ju djema për të na rrahur. 

Të gjithë ne ishin duke u përpjekur për të zbatuar kodi shpejtë të jetë e mundur. Ne duam që ju djema për të përpiqen për të sfiduar SHBA dhe të zbatojë më shpejt se të gjithë ne mund. Dhe kështu kjo është me të vërtetë hera e parë që ne jemi duke i kërkuar ju djema për të bërë një pset që ju mund të vërtetë të bëjë në çfarëdo metode ti deshiron. 

Unë gjithmonë them, kjo është më e ngjashme për një zgjidhje të vërtetë të jetës, e drejtë? Unë them, hej, kam nevojë për ju për të bërë këtë. Të ndërtuar një program që bën këtë për mua. Bëjë atë megjithatë ju dëshironi. Unë vetëm e di se unë dua të agjërojnë. Kjo është sfida juaj për këtë javë. Ju djema, ne jemi duke shkuar për të ju jap një detyrë. Ne jemi duke shkuar për të ju jap një sfidë. Dhe pastaj kjo e deri tek ju djema për të krejtësisht të vetëm të kuptoj se çfarë është më e shpejtë dhe më mënyrë efikase për të zbatuar këtë. Po? 

Audienca: A jemi të lejuar të nëse donte të hulumtimit mënyrat më të shpejtë për të bërë tavolina hash në internet, mund të bëjmë se dhe përmendin kodin e dikujt tjetër? ANDI Peng: Po, krejtësisht gjobë. Pra, nëse ju djema lexuar spekulim, ka një linjë në spekulim që thotë se ju djema janë krejtësisht të lirë për hulumtim hash funksionon mbi çfarë janë disa i funksioneve të shpejtë hash për të drejtuar gjërat deri sa kohë sa ju përmendin atë kod. Pra, disa njerëz kanë tashmë motive nga mënyra të shpejta i bërë damë magji, i shpejtë mënyra për ruajtjen e informacionit. Krejtësisht deri në ju djema, nëse ju duan të vetëm të marrë atë, e drejtë? Sigurohuni që ju jeni duke përmendur. Sfida këtu me të vërtetë se ne jemi duke u përpjekur për të provuar është duke u siguruar që ju të dini rrugën tuaj rreth pointers. Sa i përket zbatimit të funksioni aktual hash dhe vjen me si matematikë për të bërë këtë, ju djema mund të hulumtimit çfarëdo Metodat internet ju djema doni. Po? 

Audienca: A mund të përmendin vetëm duke përdorur [e padëgjueshme]? 

ANDI Peng: Po. Ju mund vetëm, në komentin tuaj, ju mund të citojmë si, oh, marrë nga yada, yada, yada, funksion hash. Çdokush keni ndonjë pyetje? Ne fakt breezed përmes seksionit sot. Unë do të jem këtu për përgjigjen pyetjeve si. 

Gjithashtu, siç thashë, zyra orë sonte dhe nesër. Spekulim këtë javë është në fakt super i lehtë dhe super të shkurtër për të lexuar. Unë do të sugjeroja duke marrë një vështrim, vetëm lexoni me tërësinë e saj. 

Dhe Zamyla fakt ju ecën me secilin nga funksionet ju keni nevojë për të zbatuar, dhe kështu që është shumë, shumë e qartë se si për të bërë gjithçka. Vetëm për t'u siguruar që ju jeni mbajtja e pointers. Kjo është një pset shumë sfiduese. 

Kjo nuk është sfiduese për shkak se si, oh, konceptet janë shumë më shumë e vështirë, ose ju duhet të mësojnë aq shumë sintaksë e re rruga që keni bërë për pset fundit. Kjo pset është e vështirë, sepse ka kaq shumë pointers, dhe atëherë është shumë, shumë e lehtë për një herë ju keni një bug në kodin tuaj të mos jetë në gjendje për të gjetur se ku bug është. 

Dhe kështu e plotë dhe besimi absolut në ju djemtë të jenë në gjendje të mundë tonë [e padëgjueshme] ekzistues. Unë në fakt nuk kanë ndonjë minierë të shkruar ende, por unë jam gati për të shkruar minave. Kështu, ndërsa ju jeni me shkrim juaji, unë do të jetë me shkrim imja. Unë do të përpiqet të bëjë imi më shpejt se sa tuajat. Ne do të shohim se kush e ka atë më të shpejtë. 

Dhe vërtet, unë do të shoh të gjithë ju djema këtu të martën. Unë do të kandidojë një lloj si një punëtori pset. Të gjitha seksionet e kësaj Javën punëtori pset, kështu që ju djema keni shumë mundësi për ndihmë, orarit të punës si gjithmonë, dhe unë me të vërtetë shohim përpara për të lexuar të gjithë kodit djemtë tuaj. Unë kam kuize deri këtu në qoftë se ju djema duan të vijnë të marrë ato. Kjo eshte e gjitha.