[MUSIC Playing] DAVID Malan: Kjo është CS50. Dhe ky është edhe fillimi dhe end-- si literally-- pothuajse në fund nga java e gjashtë. 

Unë mendova se do të ndajnë një pak e një fakt fun. Unë e kam tërhequr këtë nga a Të dhënat SEMESTRI të kaluar caktuar. Ju mund të kujtojnë se ne ju kërkojmë të çdo Forma e vendosur p qoftë se ju keni shikuar në internet ose në qoftë se ju keni marrë pjesë në në person. Dhe këtu është të të dhënave. Pra, sot ishte shumë e parashikueshme. Por ne të kërkuar për të shpenzuar pak e kohës me ju gjithsesi. Dikush do të donte për hamendje pse kjo grafik është aq i dhëmbëzuar, lart poshtë, lart poshtë, kështu vazhdimisht? Çfarë të bëjë secili nga majat dhe troughs përfaqësojnë? 

Audienca: [padëgjueshme] DAVID Malan: Vërtet. Dhe më shumë amusingly, Zoti na ruajt, ne të mbajë një ligjëratë në një e premte Në fillim të semestrit, kjo është ajo që ne shohim të ndodhë. Pra sot, ne marrim pjesë në një grimë më shumë në lidhje me strukturat e të dhënave. Dhe për të ju jap më shumë një të ngurta Modeli mendor për problemet në pesë, e cila është tani jashtë. Gabim, ku, ne do të ju dorëzojë një skedar teksti disa 100,000 plus fjalë anglisht, dhe ju jeni do të ketë të kuptoj se si për të cleverly ngarkesës së tyre në kujtesë, në RAM, duke përdorur disa të dhëna Struktura e zgjedhjes suaj. 

Tani një strukturë e të dhënave të tilla mund të të jetë, por ndoshta nuk duhet të jetë, lista mjaft e thjeshtë të lidhur, të cilat ne kemi prezantuar për herë të fundit. Dhe një listë e lidhur kishin të paktën një avantazh mbi një rrjet. Çfarë është një avantazh i një listë e lidhur në mënyrë të diskutueshme? 

AUDIENCA: hyrjes. 

DAVID Malan: hyrjes. Çfarë doni të thoni me këtë? 

AUDIENCA: Anywhere bashku Lista [padëgjueshme]. 

DAVID Malan: Mirë. Kështu që ju mund të futni një element kudo që ju doni në mes të listës pa pasur nevojë për të riorganizimi asgjë, të cilat kemi konstatuar, në klasifikim tonë diskutimet, nuk është e domosdoshmërisht një gjë e mirë, për shkak se ajo merr kohë për të vërtetë të lëvizur të gjithë atyre njerëzve të majtë apo të djathtë. Dhe kështu me një listë të lidhur, ju mund të vetëm ndajë me malloc, një nyje të re, dhe pastaj update një çift të pointers-- dy, tre operacione max-- dhe ne jemi në gjendje për të çarë dikë në kudo në një listë. 

Çfarë tjetër ka qenë i favorshëm në lidhje me një listë të lidhura? Vërtet? 

Audienca: [padëgjueshme] DAVID Malan: Perfect. Perfect. Është e vërtetë dinamike. Dhe se ju nuk jeni duke kryer, më parë, në disa madhësi fikse copë e kujtesës, si ju do të keni tek me një grup, të përmbysur e cila është se ju mund të ndajë nyje vetëm në Kërkesa e duke përdorur vetëm sa më shumë hapësirë si ju duhet të vërtetë. Në kontrast me një rrjet, ju mund të aksidentalisht ndajë shumë pak. Dhe atëherë ajo është vetëm do të jetë një dhimbje në qafës për të rialokuar një koleksion të ri të madh, kopje gjithçka mbi, të lirë array vjetër, dhe më pas të shkojë në lidhje me biznesin tuaj. Ose më keq, ju mund të ndajë rrugën më shumë memorie se ju në të vërtetë nevojë, dhe kështu që ju jeni do të ketë një shumë të paktë populluar grup, kështu që të flasin. 

Pra, një listë e lidhur ju jep këto Përparësitë e dinamizëm dhe fleksibilitet me insertions dhe fshirje. Por, me siguri duhet të ketë një çmim të paguar. Në fakt, një nga temat hulumtohen në quiz zero Ishte një çift i tregtisë të humbura ne kemi parë deri tani. Pra, çfarë është çmimi i paguar ose dobësitë e një liste të lidhur? Po. 

AUDIENCA: Nuk ka qasje të rastit. 

DAVID Malan: Nuk ka qasje të rastit. Por kush kujdeset? Qasje të rastësishme nuk tingëllon bindëse. 

Audienca: [padëgjueshme] DAVID Malan: Pikërisht. Nëse ju dëshironi të keni a algorithm-- të caktuar dhe më lejoni të vërtetë të propozojë kërko binar në veçanti, të cilat është një që kam përdorur mjaft bit-- në qoftë se ju nuk keni qasje të rastit, ju nuk mund të bëni atë aritmetikë të thjeshtë i gjetur si elementin e mesme dhe hedhur të drejtë në të. Ju në vend të kësaj duhet të fillojë në fillim element dhe lineare kërko nga e majta në të djathtë në qoftë se ju doni të gjeni mesme apo ndonjë element tjetër. 

AUDIENCA: Kjo ndoshta merr shumë memorie. 

DAVID Malan: merr më shumë memorie. Ku është kjo shtesë kosto që vijnë nga në kujtesë? 

Audienca: [padëgjueshme] DAVID Malan: Pikërisht. Në këtë rast këtu, kemi pasur një listë e lidhur për integers, por ne jemi duke dyfishuar shuma e memories ne kemi nevojë për të ruajtur këto pointers. Tani pak e një punë e madhe si structs tuaj të merrni më të mëdha dhe ju jeni ruajtjen jo një numër, por ndoshta një student apo ndonjë objekt tjetër. Por pika me siguri mbetet. Dhe kështu që një numër i operacioneve në listat e lidhura quheshin ishin O i madh i n-- lineare. Gjëra të tilla si futje apo kërkim ose fshirjen në rast se një element ka ndodhur të jetë në fund të lista nëse është e renditura ose jo. 

Ndonjëherë ju mund të merrni me fat dhe në kufijtë aq më e ulët në këto operacione mund të jetë koha konstante në qoftë se ju jeni gjithmonë kërkuar në elementin e parë, për shembull. Por në fund të fundit, ne kemi premtuar për të arritur Grail shenjtë i strukturave të të dhënave, ose disa e saj përafrimi, nga mënyra e kohës konstante. Mund të gjejmë elemente apo të shtoni elemente ose hequr elementet nga një listë? Ne do të shohim shumë shpejt. Dhe kjo rezulton se një i mekanizmave ne jemi do të fillojnë të përdorin sot, Përdorimi vjetore në p vendosur pesë, është në të vërtetë shumë e njohur. Për shembull, në qoftë se kjo është një bandë librash provimit, secila prej të cilave ka një student e parë emrin dhe mbiemrin në të, dhe unë marr ato nga në fund të një provimit, dhe ata janë të gjithë mjaft të shumë në një mënyrë të rastit, dhe ne duam të shkojnë për klasifikim këto provime në mënyrë që sapo të vlerësohet kjo është vetëm një shumë më e lehtë dhe të më shpejt t'i dorëzojë ato nga mbrapa për studentët alfabetik. Çfarë do të jetë instinktet tuaja për një grumbull të provimeve si kjo? 

E pra, në qoftë se ju jeni si unë, ju mund të shihni se kjo është m, kështu që unë jam duke shkuar për lloj të vënë këtë në, nëse kjo është tabelë ime apo kat im ku Unë jam përhapjen gjëra out-- ose array tim really-- Unë mund të vënë të gjitha të znj në atje. Oh. Këtu është një A. Kështu që unë mund të vënë si mbi këtu. Oh. Këtu është një tjetër A. Unë jam duke shkuar për të vënë atë mbi këtu. Këtu është një Z. Këtu është një tjetër M. Dhe kështu Unë mund të fillojnë të bëjnë grumbujt si kjo. Dhe pastaj ndoshta unë do të shkoj më vonë dhe lloj shumë nitpicky-ly lloj grumbujt individuale. Por çështja është që unë do të shikojmë në kontributin që unë jam dorëzuar dhe unë do të bëjë disa llogaritur Vendimi bazohet në atë të dhëna. Nëse fillon me A, e vënë atë atje. Nëse fillon me Z, e vënë atë mbi atje, dhe çdo gjë në mes. 

Pra, kjo është një teknikë që është përgjithësisht i njohur si hashing-- H-A-S-H-- të cilat në përgjithësi do të thotë duke marrë si input dhe duke përdorur këtë të dhëna për të llogaritur një vlerë, përgjithësisht një numër, dhe që Numri është indeksi në ruajtje enë, si një rrjet. Pra, me fjalë të tjera, unë mund të ketë një funksion hash, siç po bëj unë në kokën time, se në qoftë se unë shoh se dikush është Emri i cili fillon me A, Unë jam duke shkuar për të hartë atë për të zero në kokën time. Dhe në qoftë se unë shoh dikë me Z, unë jam do të ndajë se për 25 në kokën time dhe pastaj të vënë atë në grumbull fundit më. 

Tani, në qoftë se ju mendoni për të mos truri im por një program C, çfarë numrat mund ju të mbështetet në për të arritur që të njëjtën rezultat? Me fjalë të tjera, në qoftë se ju kishte ASCII karakter A, si mund ta përcaktoni çfarë kovë për të vënë atë në? Ju ndoshta nuk duan të e vënë atë në kovë 65, e cila do të jetë si atje për asnjë arsye të mirë. Ku doni të vendosni një në terma të vlerës së saj ASCII? Ku doni të bëni të saj ASCII Vlera për të dalë me një kovë të zgjuar për ta vënë atë në? 

AUDIENCA: Minus A. 

DAVID Malan: Po. Pra, minus një ose minus veçanërisht 65 nëse është e a A. Kapitali Ose 98 nëse kjo është një Fjala a. Dhe kështu që do të na lejojë të, shumë thjesht dhe shumë arithmetically, vënë diçka në një kovë si kjo. Pra, ajo rezulton ne fakt bëjmë këtë si edhe me kuize. 

Kështu që ju mund të kujtohet qe rrethuar tuaj Emri i shokut të mësimdhënies në kopertinën. Dhe u organizuan emrat TF-së në këto kolona alfabetikisht, mirë, besoj se kjo apo jo, kur të gjithë 80 plus ne marrë së bashku natën tjetër të klasës, hapi i fundit në procesin tonë të notimit është të hash kuize në një të madhe Hapësira e katit në [e padëgjueshme] dhe të vënë kuize gjithëve out pikërisht në mënyrë të Grupit Punues-tat emrat në kopertinën, sepse atëherë kjo është një shumë më e lehtë për ne për të kërkuar nëpër atë duke përdorur lineare kërko apo ndonjë lloj zgjuarsi për një TF për të gjetur të tij ose kuize studentëve të saj. 

Pra, kjo ide e hashing që ju do të shihni është mjaft e fuqishme është në të vërtetë shumë e zakonshme dhe shumë intuitiv, ashtu si ndoshta ndajnë dhe Conquer ishte në javë zero. Unë përpara të shpejtë të hackathon nja dy vjet më parë. Kjo ishte Zamyla dhe një çift i nxënësit e tjerë përshëndetje stafi si ata erdhën. Dhe ne kishim një bandë e tërë e palosjes tavolina atje me emrin tags. Dhe ne kishim organizuar tags emrin me si As mbi atje dhe Zs atje. Dhe kështu një nga TFS shumë cleverly shkroi këtë si udhëzimet për ditë. Dhe në javën e 12 të këtij semestrit të gjitha ka kuptim të përsosur dhe të gjithë e dinte se çfarë të bëni. Por kurdo që ju keni queued në të njëjtën mënyrë, ju jeni zbatimin njëjtë nocioni i një hash. Pra, le të zyrtarizojë atë një pak. Këtu është një koleksion. Është tërhequr të jetë pak të gjerë vetëm të përshkruaj, me sy, që ne të mund të vënë strings në diçka si kjo. Dhe ky grup është në mënyrë të qartë i madhësisë 26 gjithsej. Dhe gjëja është quajtur tryezë në mënyrë arbitrare. Por kjo është vetëm interpretim një artisti e asaj që mund të jetë një tavolinë hash. 

Pra, një tabelë hash tani do të të jetë një strukturë e të dhënave të nivelit të lartë. Në fund të ditës ne jemi gati për të parë se ju mund të zbatojë një tabelë hash, e cila është shumë si vijë check-in në një hackathon shumë si kjo Tabela e përdorura për klasifikimin e librave provimit. Por një tabelë hash është lloj i këtij niveli të lartë koncept që mund të përdorin një rrjet nën individualitet ta zbatuar atë, ose ajo mund të përdorni një listë gjatësi, apo edhe ndoshta disa struktura të tjera të të dhënave. Dhe tani që është marrja theme-- disa prej këtyre përbërësve themelore si një grup dhe kjo ndërtesë bllokuar tani për një listë gjatësi dhe duke parë se çfarë tjetër që ne mund të ndërtojmë në krye të atyre që, si përbërësit në një recetë, duke e bërë gjithnjë e më shumë Rezultatet e interesante dhe të dobishme përfundimtare. 

Pra, me tabelë hash ne mund të zbatojë atë në kujtesën e në pikturë si kjo, por si mund të vërtetë të jetë i koduar up? E pra, ndoshta pasi thjesht është kjo. Nëse KAPACITETI në të gjitha shkronja kapitale, është vetëm disa constant-- për shembull 26, për 26 letrat e alphabet-- Unë mund të thërrasë tryezën time ndryshueshme, dhe unë mund të pretendojnë se unë jam duke shkuar për vënë yjet CHAR në atje, apo string. Pra, ajo është aq e thjeshtë si kjo në qoftë se ju duan për të zbatuar një tabelë hash. Dhe megjithatë, kjo është me të vërtetë vetëm një grup. Por përsëri, a hash Tabela tani është ajo që ne do të thërrisni një lloj abstrakte e të dhënave që është e drejtë lloj i një layering konceptuale në krye e diçka më shumë i zakonshëm tani doja një rrjet. 

Tani, si do të shkojmë për zgjidhjen e problemeve? E pra, më herët kam pasur luksin për të pasur hapësirë ​​të mjaftueshme tryezë këtu në mënyrë që unë mund të vënë kuize kudo kam kërkuar. Pra, si mund të shkoni këtu. Zs mund të shkoni këtu. Ms mund të shkoni këtu. Dhe pastaj kam pasur një hapësirë ​​shtesë. Por kjo është pak e një të drejte mashtrojnë tani sepse këtë tryezë, në qoftë se unë me të vërtetë menduar atë si një grup, është vetëm do të jenë të një madhësie të caktuar. 

Pra teknikisht, në qoftë se unë tërheq up quiz tjetër studentit dhe shikoni, oh, ky personi Emri i fillon me një A tepër, Unë lloj i dua të vënë atë atje. Por, sa më shpejt që kam vënë atë atje, në qoftë se kjo tabelë të vërtetë paraqet një rrjet, Unë jam duke shkuar të jetë mbizotërues apo të clobbering kushdo quiz këtë nxënës është. E drejtë? Nëse kjo është një grup, vetëm një gjë mund të shkojnë në secilën nga këto qeliza ose elemente. Dhe kështu që unë lloj i kanë të zgjedhë dhe të zgjedhin. 

Tani më parë I lloj mashtruar dhe e bëri këtë apo I vetëm lloji i bërë pirg ato sipër njëri tjetrin. Por kjo nuk do të fluturojnë në kodin. Pra, ku mund ta vënë Studenti i dytë emri i të cilit A është nëse të gjithë kam pasur është kjo hapësirë ​​tryezë në dispozicion? Dhe unë e kam përdorur tre lojëra elektronike dhe atë duket sikur ka vetëm disa të tjerë. Çfarë mund të bëni? Audienca: [padëgjueshme] DAVID Malan: Po. Ndoshta le vetëm ta mbani atë të thjeshtë. E drejtë? Ajo nuk përshtatet ku unë dua të vënë atë. Kështu që unë jam duke shkuar për të vënë atë teknikisht ku B do të shkojnë. Tani, natyrisht, unë jam duke filluar për të pikturuar veten në një qoshe. Nëse unë të marrë për një student emri i të cilit është në të vërtetë B, tani B do të të zhvendoset pak përpara, siç mund të ndodhë, yep, në qoftë se kjo është një B, tani ajo ka për të shkuar këtu. 

Dhe kështu që kjo shumë shpejt mund të bëhet problematike, por kjo është një teknikë që në fakt është referuar si linear probing, ku ju vetëm konsideroni tuaj array të jenë përgjatë vijës. Dhe ju vetëm lloji i hetuar apo inspektojë çdo element në dispozicion duke kërkuar për një vend në dispozicion. Dhe, sa më shpejt që ju të gjeni një, ju bie në atë pikë. 

Tani, çmimi u paguar tani për këtë zgjidhje është ajo? Ne kemi një rrjet të madhësisë fikse, dhe kur kam futur emra në të, të paktën në fillim, çfarë është koha drejtimin e futje për vënien e nxënësve " kuize në kova të drejtë? O Big për çfarë? 

AUDIENCA: n. DAVID Malan: Kam dëgjuar O e madhe e n. Nuk është e vërtetë. Por ne do të ngas përveç pse në vetëm një moment. Çfarë tjetër mund të jetë? 

Audienca: [padëgjueshme] DAVID Malan: Dhe më lejoni të bëjë atë me sy. Pra, mendoj që kjo është letër S. 

AUDIENCA: Kjo është një. DAVID Malan: Kjo është një. E drejtë? Ky është një grup, i cili do të thotë që ne kemi qasje të rastit. Dhe në qoftë se ne mendojmë për këtë zero dhe kjo si 25, dhe ne e kuptojmë se, oh, këtu është kontributi im S, Unë me siguri mund të konvertohet S, një karakter ASCII, për një numër korrespondues mes zero dhe 25 dhe pastaj menjëherë vënë atë aty ku i takon. 

Por natyrisht, sa më shpejt që unë të shkoj në personi i dytë i cili është emri është A ose B ose C përfundimisht, në qoftë se unë kam përdorur linear probing si zgjidhje e mia, koha drejtimin e futje në rastin më të keq është në të vërtetë do të zhvilloheshin në çfarë? Dhe unë e kam dëgjuar këtu saktë herët. Audienca: [padëgjueshme] DAVID Malan: Pra, kjo është me të vërtetë n herë ju keni një grup mjaft të madh të të dhënave. Pra, nga njëra anë, në qoftë se array juaj është mjaft e madhe dhe të dhënat e juaj është mjaft e rrallë, që ju merrni këtë kohë të bukur të vazhdueshme. Por, sa më shpejt që ju të filloni duke marrë elemente gjithnjë e më shumë, dhe vetëm statistikisht ju merrni më shumë njerëz me letër A si emri i tyre ose letra B, ajo mund të potencialisht bie në diçka më shumë lineare. Pra, jo mjaft të përsosur. Pra, mund të bëjmë më mirë? 

E pra, çfarë ishte tonë Zgjidhja më parë, kur ne duan që të ketë më shumë dinamizëm se diçka si një grup i lejuar? Audienca: [padëgjueshme] DAVID Malan: Çfarë kemi prezantuar? Po. Pra, një listë të lidhura. E pra, le të shohim se çfarë një i lidhur Lista mund të bëjë për ne vend. E pra, më lejoni të propozojë që ne të nxjerrë foto si më poshtë. Tani kjo është një tjetër foto nga një shembull nga një tekst tjetër, në të vërtetë, se është në të vërtetë duke përdorur një rrjet të madhësisë 31. Dhe kjo autor thjesht vendosi të hash strings nuk është e bazuar në emrat e personit, por në bazë të datëlindjet e tyre. Pavarësisht të muajit, ata i realizuar artistikisht në qoftë se ju jeni të lindur ditën e parë të muajit ose 31 të një muaji, autori do të hash bazuar në atë vlerë, në mënyrë që të përhapet emrat jashtë një grimë më shumë se vetëm 26 spote mund të lejojë. Dhe ndoshta kjo është një uniformë pak më shumë se sa do me shkronja alfabetike, sepse sigurisht nuk ka siguri më shumë njerëz në botë me emra që të fillojë me A se me siguri disa letra të tjera të alfabetit. Pra, ndoshta kjo është pak më e njëtrajtshme, duke supozuar një shpërndarje uniforme e foshnjave të gjithë një muaj. 

Por, sigurisht, kjo është ende e papërsosur. E drejtë? Ne jemi të paturit goditjet. Njerëzit të shumta në këtë Struktura e të dhënave janë ende duke pasur të njëjtën ditëlindjen paktën ju jeni pavarësisht nga muaji. Por çfarë i ka bërë autori? E pra, kjo duket sikur ne kemi një rrjet në anën e majtë tërhequr vertikalisht, por kjo është vetëm interpretim i një artisti. Nuk ka rëndësi se çfarë drejtimi të të nxjerrë një rrjet, është ende një grup. Çfarë është kjo një grup i duket? 

AUDIENCA: Lista Linked. 

DAVID Malan: Po. Ajo duket si ajo është një Grup i listës të lidhura. Pra, përsëri, në këtë pikë të lloj i përdorimit të këtyre strukturave të të dhënave tani si përbërësit për më shumë zgjidhje interesante, ju mund absolutisht të marrë një themelore, si një grup, dhe pastaj të marrë diçka më shumë interesante si një listë e lidhur dhe madje edhe të kombinuar ato në një edhe Struktura më interesante e të dhënave. Dhe në të vërtetë, kjo shumë do të të quhet një tabelë hash, ku array është me të vërtetë tabela hash, por kjo tabelë hash ka zinxhirët, në mënyrë që të flasin, që mund të rriten, ose tkurret bazuar në Numri i elementeve që ju doni të futur. 

Tani, në përputhje me rrethanat, çfarë është kohë running tani? Nëse unë dua të futur dikë ditëlindja e të cilit është October 31, ku bën ai ose ajo të shkojë? Dakord. Në fund fare, ku ai thotë se 31. Dhe kjo është e përsosur. Kjo ishte koha konstante. Por, çfarë nëse ne gjejmë dikë tjetër ditëlindja e të cilit është, le të shohim, Tetor, nëntor, 31 dhjetor? Ku është ai ose ajo do të shkojë? Të njëjtën gjë. Dy hap pse. Kjo është konstante edhe pse nuk është ajo? Dakord. Në këtë moment ajo është. Por në rastin e përgjithshëm, më shumë njerëz ne add, probabilistically, ne jemi duke shkuar të merrni më shumë dhe më shumë goditjet. 

Tani kjo është pak më të mirë, sepse teknikisht tani zinxhirët e mi mund të jetë në rastin më të keq se sa kohë? Nëse unë futur n njerëzit në këtë më Struktura e të dhënave të sofistikuar, n popull, në rastin më të keq ajo do të jetë n. Pse? 

AUDIENCA: Sepse nëse të gjithë ka të njëjtën ditëlindje, ata do të jetë një linjë. DAVID Malan: Perfect. Kjo mund të jetë pak e sajuar, por me të vërtetë në rastin më të keq, nëse të gjithë kanë të njëjtën ditëlindje, duke pasur parasysh inputet që ju keni, ju jeni do të ketë një zinxhir masivisht të gjatë. Dhe kështu, ju mund të telefononi atë një hash tryezë, por me të vërtetë kjo është vetëm një listë masive lidhur me një tërësi shumë hapësirë ​​tretur. Por në përgjithësi, në qoftë se ne supozojmë se të paktën ditëlindjet janë uniform-- dhe kjo ndoshta nuk është. Unë jam duke e bërë atë lart. Por në qoftë se ne supozojmë, për hir të diskutimit se ata janë, atëherë teorikisht, nëse ky është përfaqësimi vertikale e array, edhe atëherë shpresojmë se ju jeni do të merrni zinxhirët që janë, ju e dini, afërsisht të njëjtën gjatësi ku secili prej këto përfaqëson një ditë të muajit. 

Tani në qoftë se ka 31 ditë në muaj, do të thotë se në kohën time running vërtetë është O e madhe e n mbi 31, e cila ndihet më mirë se lineare. Por ajo ishte një nga tonë Angazhimet e disa javë më parë, kur ai erdhi për të shprehur koha drejtimin e një algoritmi? Vetëm vetëm shikoni në afat të lartë të rendit. E drejtë? 31 është definitivisht e dobishme. Por kjo është ende O i madh i n. Por një nga temat Problemi i vendosur pesë do të jetë për pranojmë se absolutisht, asymptotically, teorikisht kjo strukturë e të dhënave është më mirë se vetëm një listë masive të lidhura. Dhe me të vërtetë, në rastin më të keq, kjo tabela hash mund të bie në atë. 

Por në botën reale, me ne njerëzit se Macs vet ose PC apo çfarëdo dhe vrapojnë botën reale software në të dhënat e botës reale, të cilat algorithm po ju do të preferoni? Ai që merr hapa fund ose ai që merr n ndarë nga 31 hapa për të gjetur disa pjesë të të dhënave ose të kërkoni disa informacione? Unë do të thotë, absolutisht e 31 bën një ndryshim në botën reale. Ajo është 31 herë më të shpejtë. Dhe ne njerëzit janë sigurisht do të vlerësojmë atë. 

Pra, të kuptojnë dikotominë atje në mes të vërtetë duke folur për gjëra teorike dhe asymptotically cilat patjetër ka vlerë si ne kemi parë, por në botën e vërtetë, në qoftë se ju intereson vetëm duke e bërë të lumtur njerëzore për inputet e përgjithshme, ju mund shumë mirë të duan të pranojnë fakti se, po, kjo është linear, por kjo është 31 herë më shpejt se mund të jetë linear. Dhe më mirë akoma, ne nuk vetëm duhet të të bëjë diçka arbitrare si datëlindja, ne mund të shpenzojnë pak më shumë kohë dhe zgjuarsia dhe të mendojnë për atë që ne mund të bëjmë, dhënë emrin e një personi dhe ndoshta ditëlindja e tyre për të kombinuar ato përbërësit për të kuptoj se diçka kjo është me të vërtetë shumë uniforme dhe më pak i dhëmbëzuar, në mënyrë që të flasin se këtë foto aktualisht sugjeron se mund të jetë. Si mund të kemi zbatuar këtë në kodin? E pra, më lejoni të propozojë që ne vetëm të marrë hua disa sintaksë kemi përdorur nja dy herë deri tani. Dhe unë jam duke shkuar për të përcaktuar një nyje, e cila përsëri është një term i përgjithshëm për vetëm disa enë për disa strukturën e të dhënave. Unë jam duke shkuar për të propozojë që a string po ndodh në atje. Por ne jemi duke shkuar për të filluar të marrë ata trajnimi rrota off tani. 

Jo më shumë bibliotekë CS50 me të vërtetë, nëse ju dëshironi ta përdorin atë për finale tuaj Projekti, i cili është e mirë, por tani ne jemi duke shkuar për të tërhequr mbrapsht perde dhe thonë se kjo është vetëm një yll char. Pra, fjala nuk do të jetë emrin e personit në fjalë. Dhe tani kam një lidhje këtu për nyjen e ardhshëm në mënyrë që këto paraqesin secili prej nyjeve në zinxhirin, potencialisht, një listë të lidhura. 

Dhe tani se si mund ta deklaroj tabela hash vetë? Si mund ta shpjegojë këtë strukturë të tërë? E pra, me të vërtetë, ashtu si kam përdorur një akrep të vetëm të elementit të parë të një liste para, në mënyrë të ngjashme mund të them vetëm Unë vetëm nevojë për një bandë e pointers për të zbatuar këtë tabelë hash tërë. Unë jam duke shkuar të ketë një rrjet bëri thirrje tavolinë për tavolinë hash. Ajo do të jetë e kapacitetit madhësi. Kjo është sa elemente mund të përshtatet në të. Dhe secili prej këtyre elementeve në këtë array do të jetë një yll nyje. Pse? E pra, për këtë foto, ajo që unë jam zbatimin tabelën hash si efektive në fillim është vetëm ky grup që ne kemi tërhequr vertikalisht, secili prej shesheve të cilëve përfaqëson një tregues. Se ato që kanë godet përmes tyre janë vetëm null. Dhe ato që kanë shigjeta shkojnë në të djathtë janë pointers aktuale në nyjet aktuale, prandaj fillimin e një listë të lidhura. 

Kështu që këtu, atëherë, është se si ne mund zbatojnë një tabelë hash që zbaton chaining të veçantë. Tani mund të bëjmë më mirë? Të gjitha të drejtat I premtuar për herë të fundit që ne mund të arrijmë kohë konstante. Dhe unë lloj të dhënë Koha konstante këtu, por pastaj nuk e ka thënë me të vërtetë Koha konstante për shkak se ajo është ende e varur totalit Numri i elementeve ju jeni inputting në Struktura e të dhënave. Por mendoj ne e bëmë këtë. Më lejoni të kthehem në ekran gjatë këtu. Më lejoni gjithashtu projektojnë këtë deri këtu, qartë ekran, dhe mendoj se kam bërë këtë. Mendoj unë të kërkuar për të futur emrin Daven në në strukturën e të dhënave time. 

Kështu që unë dua për të futur një varg Daven në strukturën e të dhënave. Çka nëse unë nuk do të përdorë hash tryezë, por unë e përdorin diçka që është më shumë pemë-si si një pemë familjare, ku ju keni disa rrënjë në nyje të lartë dhe pastaj e lë që shkojnë poshtë dhe jashtë. Supozoni pastaj, që unë doni të futur Daven e në atë që është aktualisht një listë bosh. Unë jam duke shkuar për të bërë në vijim: Unë jam do të krijojë një nyje në këtë familje pemë-si strukturë e të dhënave që duket a pak si kjo, secila prej të cilave rectangles ka, le të themi, për tani 26 elemente në të. Dhe secili prej qelizave në këtë grup do për të përfaqësuar letër e alfabetit. 

Në mënyrë të veçantë, unë jam duke shkuar për të trajtuar kjo është A, pastaj B, pastaj C, atëherë D, kjo këtu. Pra, kjo do të në mënyrë efektive përfaqësojnë letër D. Por për të futur të gjithë Daven së emrin unë duhet të bëjë pak më shumë. Kështu që unë jam duke shkuar për të parë hash, kështu që të flasin. Unë jam duke shkuar për të parë në letrën e parë në Daven e cila është padyshim një D, dhe unë jam duke shkuar për të ndarë një nyje që duket si this-- një drejtkëndësh të madhe të madhe të mjaftueshme për të përshtaten të gjithë alfabetin. 

Tani D është bërë. Tani A. D-A-V-E-N është qëllimi. Deri tani ajo që unë jam duke shkuar për të bërë është kjo. Sapo kam filluar njoftim D nuk ka asnjë tregues atje. Kjo është vlera mbeturinave në këtë moment, ose unë mund të nisja atë të pavlefshëm. Por më lejoni të mbajë me kjo ide të ndërtimit të një pemë. Më lejoni të ndajë një tjetër një nga këto nyje që ka 26 elemente në të. 

Dhe ju e dini se çfarë? Nëse kjo është vetëm një nyje në kujtesë se I krijuar me malloc, duke përdorur një e strukturës si ne do të shohim së shpejti, Unë jam duke shkuar për të bërë this-- Unë jam duke shkuar për të nxjerrë një shigjetë nga gjë që përfaqësohet D poshtë në këtë nyje të re. Dhe tani, së pari e ardhshme Letra në emër të Daven së, V-- D-A-V-- Unë jam duke shkuar për të shkuar përpara dhe të nxjerrë një nyje si kjo, ku, të V elementet këtu, të cilat ne do të tërheqë për Uh instance--. Ne nuk do të tërheqë atje. Ajo do të shkoni këtu. 

Pastaj ne jemi duke shkuar për konsiderojnë këtë të jetë V. Dhe pastaj këtu poshtë ne jemi duke shkuar për të indeksit poshtë nga V në atë që ne do të konsiderojmë E. Dhe pastaj nga këtu ne jemi duke shkuar për shkoni të ketë një nga këto nyje këtu. Dhe tani ne kemi një pyetje për t'iu përgjigjur. Unë kam nevojë për një farë mënyre tregojnë se ne jemi në fund të vargut Daven. Kështu që unë vetëm mund të lënë atë null. 

Por, çfarë nëse kemi Daven e emri i plotë gjithashtu, e cila është, siç kemi thënë, Davenport? Pra, çfarë nëse Daven është në fakt një substring, një prefiks i një varg më të gjatë? Ne nuk mund vetëm të përhershme thonë se asgjë nuk është duke shkuar për të shkuar atje, sepse ne mund të kurrë të futur një fjalë si Davenport në këtë Struktura e të dhënave 

Pra, ajo që ne mund të bëjmë në vend është trajtojnë secili prej këtyre elementëve si ndoshta duke pasur dy elemente brenda prej tyre. Njëra është një akrep, me të vërtetë, si unë kam qenë duke bërë. Pra, secili prej këtyre kutive nuk është vetëm një qelizë. Por çfarë nëse top one-- një fund të do të jetë e pavlefshme, sepse nuk ka Davenport vetëm ende. Çfarë ndodh nëse një krye është një vlerë të veçantë? Dhe kjo do të jetë pak e vështirë për të nxjerrë të kësaj madhësie. Por mendoj se është vetëm një shenjë kontrolloni. Kontrolloni. D-A-V-E-N është një varg Në këtë strukturë të dhënave. 

Ndërkohë, në qoftë se kam pasur më shumë hapësirë këtu, unë mund të bëjë P-O-R-T, dhe unë mund të vënë kontroll në nyjen që ka letrën T në fund. Pra, kjo është një masivisht kompleks-looking strukturën e të dhënave. Dhe dorëshkrimit im me siguri nuk do të të ndihmojë. Por në qoftë se unë të kërkuar për të futur diçka tjetër, e konsiderojnë atë që ne do të bëjmë. Nëse ne të kërkuar për të vënë Davidin, ne do të ndjekin të njëjtën logjikë, D-A-V, por tani unë do të veçoja në tjetër element jo nga E, por nga I tek D. Pra, nuk do të jetë më shumë nyje në këtë pemë. Ne do të kemi thirrjes malloc më shumë. Por unë nuk dua të bëjë një rrëmujë të plotë të kësaj tabloje. Pra, le të shohim në një vend që është para-formuluara si ky me nuk dot, dot, pika, por vargjeve vetëm shkurtuar. Por secili prej nyjeve në këtë pemë këtu paraqet të njëjtën thing-- një grup Ray e madhësisë 26. 

Ose në qoftë se ne duam që të jenë të me të vërtetë e duhur tani, çfarë nëse emri i dikujt si një apostrof, le të supozojmë se çdo nyje të vërtetë ka si 27 indekseve në të, jo vetëm 26. Pra, kjo është tani do të jetë një e të dhënave Struktura e quajti një trie-- T-R-I-E. A trie, e cila është kinse historikisht një emër i zgjuar për një pemë që është e optimizuar për rikthim, e cila natyrisht, është shkruar me një I-E kështu që është trie. Por kjo është historia e trie. 

Pra, a është kjo trie të dhëna pemë-si Struktura si një pemë familjare që në fund të fundit sillet si kjo. Dhe këtu është vetëm një shembull i një tërë bandë e emrave të njerëzve të tjerë. Por pyetja tani në dorë është ajo që kemi kemi fituar duke futur ndoshta një më strukturë të komplikuar e të dhënave, dhe një, sinqerisht, që përdor një shumë të kujtesës. 

Sepse edhe pse, në këtë moment, unë jam vetëm përdorur D's tregues dhe Një dhe V dhe Es dhe Ns, Unë jam humbur një dreq e shumë të kujtesës. Por ku kam shpenzuar një burim, Unë synoj që të mund të fitojë përsëri një tjetër. Pra, në qoftë se unë jam duke shpenzuar më shumë hapësirë, çfarë është ndoshta shpresa? Se unë jam shpenzojnë më pak çfarë? AUDIENCA: pak kohë. DAVID Malan: Koha. Tani pse mund që të jetë? E pra, ajo që është shtënie kohë, në aspektin e O i madh tani, një emër si Daven ose Davenport apo David? Well, Daven ishte pesë hapa. Davenport do të jetë nëntë hapa, kështu që do të jetë një pak më shumë hapa. David do të jetë pesë hapa si. Pra, ato janë konkrete numrat, por me siguri ka një kufi i sipërm për Gjatësia e emrit të dikujt. Dhe me të vërtetë, në problemin grupe të pesë specifikim, ne jemi duke shkuar për të propozuar se kjo është diçka e kjo është karaktere 40-disa-rastësishëm. 

Realisht, askush nuk e ka një emër pafundësisht të gjatë, që do të thotë se gjatësia e një emrin ose gjatësia e një varg, ne mund kanë të sigurt shteti i Struktura është ndoshta çfarë? Kjo është konstante. E drejtë? Ajo mund të jetë një konstante e madhe si 40-diçka, por ajo është konstante. Dhe kjo nuk ka varësi nga sa Emrat e tjerë janë në këtë strukturë të dhënave. Me fjalë të tjera, në qoftë se unë kërkuar për të futur tani Colton ose Gabriel ose Rob a Zamyla ose Alison ose Belinda ose ndonjë emra të tjerë nga stafi në këto të dhëna struktura, është koha running i futur emra të tjerë do të jetë në të gjitha ndikuar nga sa shumë elemente të tjera janë në strukturën dhënave tashmë? Kjo nuk është. E drejtë? Sepse ne jemi duke përdorur në mënyrë efektive kjo multi-layer tabelë hash. Dhe koha drejtimin e ndonjë prej këtyre operacioneve është jo i varur nga numri i elemente që janë në strukturën dhënave ose që eventualisht do të jetë në strukturën dhënave, por në gjatësinë e atë mënyrë specifike? 

String qenit futur, e cila ka të bëjë kjo asymptotically konstante time-- O e madhe e një. Dhe sinqerisht, vetëm në bota reale, kjo thotë futur emrin Daven merr si pesë hapa, apo Davenport nëntë hapa, apo David pesë hapa. Kjo është goxha i mallkuar herë vogla running. Dhe, me të vërtetë, kjo është një shumë gjë e mirë, sidomos kur kjo nuk është e varur nga gjithsej Numri i elementeve ne atje. Pra, si mund të zbatojmë këtë lloj strukture në kodin? Kjo është pak më shumë komplekse, por ende është e vetëm një aplikim i blloqe themelore të ndërtimit. Unë jam duke shkuar për të ripërcaktuar ne nyje si më poshtë: bool quajti word-- dhe kjo mund të quhet asgjë. Por bool përfaqëson ajo që unë tërhoqi si një shenjë kontrolloni. Po. Ky është fundi i një varg Në këtë strukturë të dhënave. 

Dhe, sigurisht, ylli nyjen nuk i referohet fëmijëve. Dhe, me të vërtetë, ashtu si një pemë familjare, ju do të marrë në konsideratë nyje që janë të varur off e poshtme të ndonjë prind element të jenë fëmijë. Dhe kështu fëmijët do të të jetë një grup i 27, një 27 vetëm duke e apostrof. Ne jemi duke shkuar për të zgjidhur e rastit të veçantë asaj. Kështu që ju mund të keni të sigurtë Emrat me apostrofat. Ndoshta edhe vizë ndarëse duhet të shkojnë në atje, por ju do të shihni në p grup 5 ne vetëm të kujdesit në lidhje me letrat dhe apostrofat. 

Dhe pastaj si bëni ju përfaqësoni Struktura e të dhënave në vetvete? Si mund të përfaqësojnë rrënjë i këtij trie, kështu që të flasin? E pra, ashtu si me një listë të lidhura, ju duhet një tregues për elementin e parë. Me një trie ju vetëm nevojë për një treguesin në rrënjë të këtij trie. Dhe nga atje ju mund të hash rrugën tuaj poshtë thellë e më thellë për çdo nyje tjetër në strukturën. Pra, thjesht me kjo mund të ne përfaqësojmë atë e strukturës. 

Tani Meanwhile-- Oh, pyetje. 

AUDIENCA: Çfarë është fjala bool? 

DAVID Malan: Fjala bool është vetëm këtë mishërim C e asaj që e përshkroi në këtë kuti këtu, kur I filluar ndarjen secili prej Elementet Array it ndahen në dy pjesë. Njëra është një tregues për nyjen e ardhshëm. Tjetër duhet të jetë diçka si një kuti kontrolloni të themi po, ka një Fjala Daven që përfundon këtu, sepse ne nuk duam, në këtë moment, Dave. 

Edhe pse Dave do të jetë një Fjala legjitim, ai nuk është në trie ende. Dhe D nuk është një fjalë. Dhe D-A nuk është një fjalë ose një emër. Pra, në shenjë kontrolloni tregon vetëm një herë ju hit kjo nyjë është rruga e mëparshme e karaktereve në fakt një varg që e keni futur. Pra, kjo është e gjitha bool nuk është duke bërë për ne. 

Çdo pyetje të tjera mbi përpiqet? Po. 

AUDIENCA: Çfarë është mbivendosje? Çfarë ndodh nëse ju keni një Dave dhe Daven? DAVID Malan: Perfect. Çfarë ndodh nëse ju keni një Dave dhe Daven? Pra, nëse ne të futur, thonë se një pseudonim, për David-- Dave-- D-A-V-E? Kjo është në të vërtetë super e thjeshtë. Pra, ne jemi vetëm duke shkuar për të marrë katër hapa. D-A-V-E. Dhe çfarë kam për të të bëjë një herë unë goditi atë nyje të katërt? Vetëm duke shkuar për të kontrolluar. Ne jemi tashmë të mirë për të shkuar. Bërë. Katër hapa. Koha Constant asymptotically. Dhe tani ne kemi treguar se si Dave dhe Daven janë vargjet në strukturën. Pra, nuk është një problem. Dhe vini re se si praninë e Daven nuk e bëjnë atë marrë ndonjë më shumë kohë ose më pak koha për Dave dhe anasjelltas. 

Pra, çfarë tjetër mund të bëjmë tani? Ne kemi përdorur këtë metaforë më parë e tabaka përfaqësojnë diçka. Por kjo rezulton se një rafte e tabaka është në të vërtetë demonstrative të një të dhënave abstrakte type-- një strukturë e të dhënave të nivelit të lartë se në fund dita është vetëm si një grup apo një listë e lidhur ose diçka më shumë i zakonshëm. Por kjo është një më interesante Koncepti konceptual. Një turrë, si këto tabaka këtu në Mather, janë quajtur përgjithësisht vetëm that-- një pirg. 

Dhe në këtë lloj të strukturës së të dhënave ju keni dy operations-- ju keni një të quajtur shtytje për duke shtuar diçka për të rafte, vënë si një tabaka Kthehu në krye të rafte. Dhe pastaj pop, që do të thotë ju marrë tabaka off larti. Por, ajo që është shumë e rëndësishme në lidhje me një pirg është se ajo e mori këtë karakteristikë kurioz. Si stafit sallë ngrënie janë rikomponimin e tabaka për vakt tjetër, çfarë do të jetë e vërtetë në lidhje me mënyrën se si studentët ndërveprojnë me këtë strukturë të dhënat? AUDIENCA: Ata do të pop një off. DAVID Malan: Ata janë duke shkuar për të pop një off, me shpresë të lartë. Përndryshe kjo është vetëm lloj i trashë për të shkuar gjatë gjithë rrugës për në fund. E drejtë? Struktura e të dhënave të vërtetë nuk lejon ju për të rrëmbyer tabaka fund paku të lehtë. Pra, nuk është kjo kurioz pronës në një pirg se pika e fundit në është do të jetë i pari ai jashtë. Dhe shkencëtarët kompjuter telefononi kjo LIFO-- fundit në, e parë jashtë. Dhe ai në fakt ka aplikacione interesante. Kjo nuk është domosdoshmërisht aq e qartë si disa të tjerët, por ajo mund të, me të vërtetë, të jetë e dobishme, dhe kjo mund të, me të vërtetë, do të zbatohen në disa mënyra të ndryshme. 

Pra një, dhe në fakt, le të mua mos të zhyten në atë. Le ta bëjmë këtë vend. Le të shikojmë në atë që është pothuajse e të njëjtën ide, por kjo është një më të drejtë të vogël. E drejtë? Nëse ju jeni një nga këta djem tifoz, ose Vajzat që me të vërtetë i pëlqen produktet Apple dhe ju u zgjua në 3:00 të vijë deri në një dyqan për të marrë iPhone më të fundit, ju mund të ketë queued lart si kjo. 

Tani një radhë është quajtur me shumë kujdes. Kjo është një linjë, sepse nuk ka disa korrektësisë me të. E drejtë? Ajo do lloj thithur në qoftë se ju keni mori aty për herë të parë në Apple Store por ju jeni në mënyrë efektive më i fundit tabaka sepse punonjësit Apple pastaj pop personin e fundit që në të vërtetë mori në linjë. Pra, oxhaqet dhe radhët e gjata, madje edhe pse funksionalisht ata janë lloj i same-- kjo është vetëm për këtë koleksion e burimeve që është do të rritet dhe shrink-- atje ka ky aspekt drejtësia me të, të paktën në botën e vërtetë, ku operacionet ju ushtroni janë krejtësisht të ndryshme. Një stack-- një radhë rather-- është e thënë të ketë dy operacione: n radhë dhe d radhë. Ose ju mund të telefononi ata çdo numër të gjërave. Por ju vetëm doni të kapni nocioni se ai është duke shtuar dhe një është në fund të fundit i zbritur. 

Tani nën kapuç, si rafte dhe një radhë të mund të zbatohet si? Ne nuk do të shkojë në kodin e kjo për shkak të nivelit të lartë Ideja është lloj më i dukshëm. Unë do të thotë, çfarë bëjnë njerëzit? Në qoftë se unë jam personi i parë në Apple Dyqan dhe kjo është derë e parë, ju e dini, unë jam duke shkuar për të dalë këtu. Dhe personi tjetër të do të qëndrojë këtu. Dhe personi tjetër të do të qëndrojë këtu. Pra, çfarë strukturë e të dhënave jep vetë në një radhë? 

AUDIENCA: A radhë. DAVID Malan: Pra, a radhë. Të sigurt. Çfarë tjetër? 

AUDIENCA: Një listë të lidhura. 

DAVID Malan: Një lidhje lista që ju mund të zbatojë. Dhe një listë e lidhur është e bukur, sepse atëherë ajo mund të rritet në mënyrë arbitrare të gjatë në krahasim për të pasur një numër të caktuar e njerëzve në dyqan. Por ndoshta një numër të caktuar e vendeve është e ligjshme. Sepse në qoftë se ata vetëm kanë si 20 iPhones në ditën e parë, ndoshta ata kanë nevojë vetëm për një grup të madhësisë 20 për të përfaqësuar atë radhë, e cila vetëm të them tani sapo kemi filluar duke folur në lidhje me këto probleme të nivelit të lartë, ju mund të zbatojë atë në çdo numër të mënyra. Dhe nuk ka ndoshta vetëm do të të jetë një tregti off në hapësirë ​​dhe kohë ose vetëm në vetë kompleksitetin tuaj kodit. 

Po në lidhje me një pirg? E pra, një pirg, ne kemi parë shumë mund të jetë vetëm këto tabaka. Dhe ju mund të zbatojë këtë një grup. Por në një moment në qoftë se ju përdorni një rrjet, se çfarë do të ndodhë me tabaka jeni duke u përpjekur për të vënë poshtë? Dakord. Ju jeni vetëm do të të jenë në gjendje për të shkuar deri të lartë. Dhe unë mendoj se në Mather ata janë fakt recessed në këtë hapje. Pra me të vërtetë, kjo është pothuajse e si Mather është duke përdorur një grup të madhësisë fikse, sepse ju vetëm mund të përshtatet kaq shumë tabaka në atë hapje në muri poshtë nën gjunjë njerëzve. Dhe kështu që mund të jetë e thënë të jetë një grup, por ne me siguri mund të zbatojë atë më përgjithësisht me një listë të lidhura. 

E pra, çka në lidhje me një tjetër strukturën e të dhënave? Më lejoni të tërheqë një tjetër vizuale këtu. Diçka si si në lidhje me këtë këtu? Pse mund të jetë e dobishme që të mos ketë diçka si dashuroj si një trie, e cila pamë pasur këto nyje shumë të gjerë, secili i cili është në një grup? Por, çfarë nëse ne bëjmë diçka më shumë thjesht, si një pemë e vjetër familjare shkollë, secili nga nyjet këtu cilit është vetëm ruajtjen e një numri. Në vend të një emri apo një pasardhës është vetëm ruajtjen e një numër të tillë. 

Well, zhargon ne përdorim në Strukturat e të dhënave është edhe mundohet dhe pemë, ku një trie, përsëri, është e vetëm një nyje e të cilit janë të vargjeve, është ende ajo që ju mund të përdorim nga klasën e shkollës kur keni bërë një familje lë tree-- dhe rrënja nga pema dhe fëmijët e prind dhe vëllezërit e motrat e tyre. Dhe ne mund të zbatojë një pemë, për shembull, si thjesht si kjo. Një pemë, në qoftë se ajo si një nyje, një prej këto qarqe që ka një numër, ajo nuk do të ketë një akrep, por dy. Dhe, sa më shpejt që ju të shtoni një tregues të dytë, ju mund të vërtetë të bëjë tani lloj të të dhënave të dy-dimensionale Strukturat në kujtesën. Ashtu si një dy-dimensionale array, ju mund të kemi lloj i dy-dimensionale Listat e lidhura, por ato që ndjekin një model ku nuk ka asnjë cikle. Kjo është me të vërtetë një pemë me një Mënyra gjysh deri këtu dhe pastaj disa prindër dhe fëmijët e nipërit dhe stërnipërit e stërmbesat. dhe kështu me radhë. 

Por ajo që është me të vërtetë i zoti për këtë shumë, vetëm për të vë në lojë ju me një pak të kodit, recursion risjell nga një copë herë prapa, ku ju shkruani një funksion që e quan veten. Kjo është një mundësi e bukur të zbatojnë diçka si recursion, sepse e konsiderojnë këtë. 

Kjo është një pemë. Dhe unë kam qenë një anal pak me mënyrën se si I vënë integers në rrugë. Pra, shumë në mënyrë që ajo ka një të veçantë name-- një pemë kërkimi binar. Tani ne kemi dëgjuar binar kërkoni, por ju mund të punojnë prapa nga emri kjo gjë është? Cili është modeli se si unë futur integers në këtë pemë? Kjo nuk është arbitrare. Ka disa model. Po. 

AUDIENCA: ato më të vogla në të majtë. 

DAVID Malan: Po. Ato më të vogla janë në të majtë. Ato janë më të mëdha në të djathtë. Tillë që një deklaratë e vërtetë është një prind është më i madh se fëmijën e saj të majtë, por më pak se fëmijën e saj të drejtë. Dhe kjo është vetëm edhe një përkufizim gjithkund rekursive verbal sepse ju mund të aplikoni atë të njëjtën logjikë për çdo nyje dhe ai vetëm fundeve out, një rast bazë, nëse ju do, kur ju goditi një gjethet, në mënyrë që të flasin, ku një pushimi nuk ka fëmijë më tej. 

Tani si mund ju të gjeni numrin 44? Ju do të fillojë në rrënjë dhe të thonë, HM. 55 nuk është 44 Prandaj nuk dua të shkoj drejtë ose nuk dua të shkojnë majtas? Well, natyrisht që ju dëshironi të shkoni majtas. Dhe kështu kjo është vetëm si telefon shembull libër në kërkim binar në përgjithësi. Por ne jemi në zbatim të tij tani pak më dinamike se një grup mund të lejojë. Dhe në fakt, në qoftë se ju doni të shikoni në kodin, në shikim të parë i sigurt. Ajo duket si një bandë e tërë e linjave. Por kjo është bukur e thjeshtë. Nëse ju doni të zbatojë një funksion quajtur search qëllimi i të cilit në jetë është për të kërkuar për një vlerë si n, një numër i plotë, dhe ju jeni duke kaluar në një një pointer-- një tregues për nyjen e rrënjëve, në vend, e atë pemë prej të cilave ju mund të hyni në çdo gjë tjetër, njoftim sa drejpërdrejtë ju mund të zbatojë logjikën. Nëse pema është i pavlefshëm, natyrisht kjo nuk është atje. Le të kthehen vetëm false. E drejtë? Nëse ju dorë atë asgjë, nuk ka asgjë atje. 

Tjetër, nëse n është më pak se pemë shigjetë n-- tani shigjetë n, kujtojnë ne kemi prezantuar super shkurtimisht ditë të tjera, dhe kjo vetëm do të thotë de-referencë e tregues dhe të kërkoni në fushën e quajtur n. Pra, kjo do të thotë të shkojnë atje dhe të shikoni në fushën e quajtur n. Pra, nëse n, vlera ju jeni duke i dhënë, është më pak i se vlera e pemëve numër i plotë, ku ju doni të shkoni? Në të majtë. 

Pra njoftim recursion. Unë jam returning-- nuk është e vërtetë. Jo false. Unë jam kthyer çfarëdo përgjigje është nga një thirrje për veten time, duke kaluar n një herë, i cili është i tepërt, por ajo është pak më ndryshe tani? Sa jam unë duke e bërë problem më të vogël? Unë jam duke kaluar në, si të dytë Argumenti, nuk rrënja e pemës, por fëmija majtë në këtë rast. Kështu që unë jam duke kaluar në fëmijën e majtë. 

Ndërkohë, nëse n është më e madhe se nyja Unë jam duke kërkuar në, I kërko anën e djathtë. Tjetër, në qoftë se pema nuk është i pavlefshëm, dhe nëse element nuk është në të majtë dhe kjo nuk është në të djathtë, çfarë është mrekullisht rasti? Ne kemi gjetur në të vërtetë nyjen në pyetje, dhe kështu që ne kthehemi vërtetë. 

Pra, ne kemi gërvishtem vetëm sipërfaqen tani disa prej këtyre strukturave të dhënave. Në Problemi vendosur pesë ju do të eksplorojë këto akoma më tej, dhe ju do të jepet dizajnit tuaj zgjedhje se si të shkojë në lidhje me këtë. Ajo që unë do të doja të përfundojë në është vetëm një ngacmues 30 dytë e asaj që pret javën e ardhshme dhe më gjerë. 

Si ne begin-- fatmirësisht ju mund të think-- tranzicionit tonë ngadalë nga bota e C dhe më të ulët Detajet e implementimit të nivelit, në një botë në të cilën ne mund të marrë për të dhënë se dikush tjetër e ka më në fund zbatohen këto të dhëna Strukturat për ne, dhe ne do të fillojmë të kuptojmë bota reale do të thotë të zbatimit Programet web-bazuar dhe faqet e internetit më të përgjithshme dhe gjithashtu shumë i sigurisë Implikimet që ne kemi vetëm filluar për të zeroja sipërfaqe e. Këtu është ajo që na pret në ditët që do të vijnë. 

[VIDEO Playback] 

-Ai Erdhi me një mesazh, me një protokoll delet e tij. Ai erdhi në një botë të egër firewalls, routers pa ndjenja, dhe rreziqe shumë më keq se vdekja. Ai është i shpejtë. Ai është i fortë. Ai është TCP / IP, dhe ai mori adresën tuaj. "Warriors e Net". [END VIDEO rishikim] DAVID Malan: Së javën e ardhshme. Ne do të shohim ju pastaj. [VIDEO Playback] -Dhe Tani, "Mendime të thella" nga Daven Farnham. -David Gjithmonë fillon ligjërata me "gjithë të drejtë." Pse jo, "Ja zgjidhja të problemit të vendosur e kësaj jave " apo "Ne jemi duke i dhënë të gjithë ju një A?" [Qesh] [END VIDEO rishikim]