[Muusika mängimine] DAVID Humala: See on CS50. Ja see on nii algus ja väljatöötamiseni nagu literally-- peaaegu lõpuni nädala kuus. 

Ma mõtlesin, et ma jagan natuke lõbus fakt. Olen tõmmatakse see üles Viimase semestri andmekogum. Sul võib meelde tuletada, et me palume teil iga p set vormi, kui olete võrgus vaadatud või kui olete käinud isiklikult. Ja siin on andmed. Nii et täna oli väga etteaimatav. Aga me tahtsime kulutada natuke aega teiega siiski. Kas keegi tahaks hüpotees miks see graafik on nii sakiline, üles alla, üles alla, nii järjekindlalt? Mida iga piikide ja rennid esindama? 

Sihtrühm: [kuuldamatu] DAVID Humala: Tõepoolest. Ja veel Lõbusas, jumal hoidku, hoiame üks loeng reedel alguses semester, see, mida me näeme juhtuda. Nii et täna me võtame natuke rohkem andmestruktuurid. Ja teile rohkem tahke vaimne mudel probleeme viis, mis on nüüd välja. Õigekirjavead, mida iseloomustab, siis me käe tekstifaili mõned 100.000 pluss inglise sõnad ja sa lähed on nuputada, kuidas nutikalt laadida mällu RAM, kasutades mõned andmed struktuuri oma valik. 

Nüüd üks selline andmestruktuur võib olla, kuid ilmselt ei tohiks olla, küllaltki lihtsustatud seotud nimekirja, mis tutvustasime viimast korda. Ja ahelloend oli vähemalt üks eelis massiivi. Mis on üks eelis ahelloend vaieldamatult? 

Sihtrühm: täiendus. 

DAVID Humala: täiendus. Mida sa mõtled? 

Sihtrühm: kuhu tahes mööda nimekiri [kuuldamatu]. 

DAVID Humala: Hea. Nii saate sisestada element kõikjal soovite keskel nimekiri ilma shuffle midagi, mis me järeldada, meie sorteerimine arutelud, ei ole tingimata hea asi, sest see võtab aega, et tegelikult liiguvad kõik need inimesed vasakule või paremale. Ja nii koos seotud nimekirja, saate lihtsalt eraldada koos malloc, uus sõlm, ja seejärel ajakohastada paar pointers-- kaks, kolm operatsiooni max-- ja me saame pesa keegi kuhugi loendisse. 

Mida muud oli soodne umbes ahelloend? Jah? 

Sihtrühm: [kuuldamatu] DAVID Humala: Perfect. Perfect. See on tõesti dünaamiline. Ja et sa ei ole toime, ette, et teatud fikseeritud suurus patakas mälu, nagu sa oleks et array, tagurpidi, mis on, et saate eraldada sõlmede ainult nõudlus kasutades seejuures ainult nii palju ruumi kui sa tegelikult vajad. Erinevalt massiivi, siis võib kogemata eraldada liiga vähe. Ja siis see lihtsalt läheb olla valu kaela ümber paigutama uus suurem massiiv, kopeerida kõik üle, vaba vana massiiv, ja siis liikuda oma äri. Või veel hullem, siis võiks eraldada viis rohkem mälu kui te tegelikult vaja, ja et sa lähed on väga hõreda asustusega massiiv, nii rääkida. 

Nii ahelloend annab teile need eelised dünaamilisus ja paindlikkus koos sisestusi ja parandusi. Aga kindlasti peab olema hind, mida makstakse. Tegelikult on üks neist teemadest Uurimist viktoriin null oli paar kompromissid oleme näinud siiani. Mis on hind, mida makstakse või Negatiivne seotud nimekirja? Jah. 

Sihtrühm: No muutmälu. 

DAVID Humala: No muutmälu. Aga keda see huvitab? Muutmälu ei kõla veenvad. 

Sihtrühm: [kuuldamatu] DAVID Humala: Täpselt. Kui sa tahad olla teatud algorithm-- ja andke mulle tegelikult ettepaneku Kahendotsingupuu eelkõige mis on üks me olen kasutanud üsna bit-- Kui sul ei ole juhuslik juurdepääs, sa ei saa seda teha lihtsa aritmeetilise leida nagu keskmine element ja hüppas õigus seda. Te asemel on alustada esimesel element ja lineaarselt otsida vasakusse paremale, kui soovite leida keskel või mõni muu element. 

Sihtrühm: Tõenäoliselt võtab rohkem mälu. 

DAVID Humala: võtab rohkem mälu. Kus on, et täiendavad maksab pärit mälu? 

Sihtrühm: [kuuldamatu] DAVID Humala: Täpselt. Selles asjas oli meil seotud nimekirja täisarvud, ja veel me kahekordistada mälu vajame poolt ka ladustamiseks neid viiteid. Nüüd vähem suur asi, kui Sinu structs saada suuremat ja sa ei salvestata mitmeid kuid võibolla õpilane või mõne muu esemega. Aga asi kindlasti jääb. Ja nii mitmeid operatsioone kohta ahelloendid kutsuti olid suured O n-- lineaarne. Asjad sisestamine ja otsing või kustutamise korral element juhtus olema päris lõpus nimekiri kas see sorteeritud või mitte. 

Mõnikord võite saada õnnelik ja nii alam- need toimingud Võib ka olla pidev aeg, kui sa oled Jälgides esimene element, näiteks. Aga lõpuks me lubasime saavutada Püha Graal andmestruktuuride või teatud ühtlustamist, ning teel konstantse ajaga. Kas me leiame elemendid või lisada elemente või eemaldada elemente nimekirja? Me näeme üsna varsti. Ja selgub, et üks mehhanismide me oleme kavatse hakata kasutama täna aastane kasutamiseks p määrata viis, on tegelikult päris tuttav. Näiteks, kui see on kamp eksami raamatuid, millest igaüks on õpilase esimene nimi ja perekonnanimi seda, ja ma valida neid üles lõpus eksam, ja nad kõik on päris palju juhuslikus järjekorras, ja me tahame minna sorteerimine need eksamid nii, et kui sorteeritud see on lihtsalt palju lihtsam ja kiiremini kätte neid tagasi viia õpilastele tähestikulises järjekorras. Mida oma instinkte olla vaiade eksamid nagu see on? 

Noh, kui sa oled nagu mina, siis võib näha, et see on m, nii et ma lähen omamoodi panna see, kui see on mu laua või minu korrusel, kus Ma levib asjad out-- või minu massiivi really-- Ma võin panna kõik Ms seal. Oh. Siin on A. Nii et ma võiks pane Nagu siin. Oh. Siin on veel üks A. Ma lähen panna, et siin. Siin on Z. Siin on veel üks M. Ja nii Ma võin hakata vaiad niimoodi. Ja siis äkki ma tahaks minna hiljem ja omamoodi väga nitpicky-Ly sorteeri üksikute vaiad. Aga küsimus on, ma näeks sisendis, et ma olen käega ja ma teeks mõned arvutatud otsus põhineb, et sisend. Kui see algab, pane see sinna. Kui see algab Z, pane see üle seal, ja kõik sellises vahel. 

Nii et see on tehnika, mis on üldiselt tuntud hashing-- H--S-H- mis tähendab üldiselt võttes sisend ja kasutades sisendina arvutada väärtus, tavaliselt mitu, ja et number on indeks ladustamine konteiner, nagu massiivi. Nii teisisõnu I võivad olla hash funktsiooni, kui ma oma peas, et kui ma näen kedagi on nime, kes algab, Ma lähen kaarti, et null peas. Ja kui ma näen kedagi, kellel Z, ma olen läheb kaarti, et 25 minu peas ja seejärel panna, et arvesse viimane kõige pakk. 

Nüüd, kui sa arvad, ei ole minu aju kuid C programm, mis numbrid võiks sa tugineda, et saavutada sama tulemus? Teisisõnu, kui te oli ASCII, kuidas sa kindlaks mida kopp panna see? Sa ilmselt ei taha pane see ämber 65, mis oleks nagu seal mingit põhjust. Kui sa tahad panna poolest ASCII väärtus? Kui sa tahad teha oma ASCII väärtus tulla targemaks ämber pane see? 

Sihtrühm: Minus A. 

DAVID Humala: Jah. Seega miinus miinus just 65, kui see on kapitali A. Või 98, kui see on väiketähed. Ja nii, et võimaldaks meil väga lihtsalt ja väga aritmeetiliselt, panna midagi ämbrisse niimoodi. Nii selgub me tegelikult teha see ka isegi viktoriine. 

Nii võite meenutada teile ringiga oma õpetamise mehe nimi kaanel. Ja TF nimed korraldati viiakse need sambad tähestikuliselt, noh, uskuge või mitte, kui kõik 80 pluss meist said kokku ühel õhtul astmeni, viimane samm meie hindamisprotsessi on hash viktoriinid suurde ruumi põrandale [kuuldamatu] ning määrata igaühe viktoriinid välja täpselt järjekorras TF nimed kaanel, sest siis see on palju lihtsam meile otsida, et lineaarse otsida või mingi nutikust jaoks TF leida oma või Tema õpilaste viktoriine. 

Nii et see idee hashing et näete, on üsna võimas on tegelikult päris tavaline ja väga intuitiivne, meelega ehk jagada ja vallutada oli nädal null. Ma kiiresti edasi hackathon paar aastat tagasi. See oli Zamyla ja paar teiste töötajate tervitus üliõpilastele kui nad tulid. Ja meil oli terve hunnik kokkuklapitavad tabelid seal nimesiltide. Ja meil oli nimesiltide korraldatud sarnaselt Kuna seal ja Zs seal. Ja nii üks TF väga nutikalt kirjutas selle kui kasutusjuhendid eest päevas. Ja 12. nädalal semestri see kõik tegi väga mõistlik ja igaüks teadis, mida teha. Aga millal olete Järjekorras samamoodi, sa rakendamisel Sama mõiste hash. Nii et olgem vormistada natuke. Siin on massiiv. See on koostatud olema veidi lai lihtsalt kujutada visuaalselt, et me võiksime panna stringid midagi sellist. Ja see massiiv on selgelt suurus 26 kokku. Ja asi on nn Tabelis meelevaldselt. Aga see on lihtsalt kunstniku üleviimise mida hash tabel võiks olla. 

Nii hash tabelit nüüd läheb olla kõrgem andmestruktuur. Lõpus päeval me parasjagu näha, et sa saab rakendada hash tabelit, mis on palju nagu check-in line kell hackathon palju nagu see Tabelis sorteerimisaedikutest eksam raamatuid. Kuid hash tabelit omamoodi kõrge taseme mõiste, mida võiks kasutada massiivi all kapuuts seda rakendada, või siis võiks kasutada pikkuse nimekirja, või isegi võibolla mõned muud andmed struktuure. Ja nüüd see on theme-- võtmist mõned neist põhiline koostisosa nagu massiivi ja selle hoone blokeerida nüüd pikkusega nimekiri ja näha, mida muidu saame ehitada lisaks neile, nagu koostisosade arvesse retsept, üha enam huvitav ja kasulik lõpptulemused. 

Nii et hash tabelit me võime seda rakendada mälu piltlikult meeldib see, kuid kuidas võib see tegelikult olla kodeeritud up? Noh, võibolla kui lihtsalt on selline. Kui suutlikkust kõigis mütsid, on lihtsalt mõned constant-- näiteks 26, 26 tähte alphabet-- Võib ju olla, minu muutuja tabel, ja ma võin väita, et ma lähen pane char tähed seal, või string. Nii et see on nii lihtne kui see, kui sa soovivad rakendada hash tabelis. Ja veel, see on tõesti ainult massiivi. Aga jälle, hash Tabelis on nüüd, mida jagame helistada abstraktsete andmete tüüp, mis on lihtsalt omamoodi kontseptuaalne kihilisus peal midagi rohkem Ilmalik nüüd meeldib massiivi. 

Nüüd, kuidas me minna umbes probleemide lahendamisel? Noh, varem oli mul luksus võttes piisavalt laud ruumi siin nii et ma võiksin panna viktoriinid kuskil ma tahtsin. Nii võiks minna siin. Zs võiks minna siin. Ms võiks minna siin. Ja siis ma pidin mõned ekstra ruumi. Aga see on natuke petta õigus nüüd, sest see tabel, kui ma tõesti mõtles ta massiiv, on lihtsalt kavatse olla mõned fikseeritud suurus. 

Nii tehniliselt kui tõmban järjekordse õpilase viktoriin ja vaata, oh, kuidas see inimene nimi algab ka Ma nagu tahan panna sinna. Aga niipea, kui ma panin selle sinna, kui Selle tabeli esindab tõepoolest massiiv, Ma lähen esmatähtsad või clobbering kes iganes see õpilase viktoriin on. Õigus? Kui see on massiiv, ainult üks asi ei saa minna iga kõnealuste rakkude või elemente. Ja nii ma selline on hoolikalt valima. 

Nüüd varem I tüüpi pettis ja tegi seda või I lihtsalt selline laotud neid teineteise kohal. Aga see ei kavatse lennata koodi. Nii et kui ma saaksin panna teine ​​õpilane, kelle nimi on siis, kui kõik oli mul see saadaval tabeli ruumi? Ja olen kasutanud kolm pesa ja see Tundub, seal on lihtsalt mõned teised. Mida saaksid teha? Sihtrühm: [kuuldamatu] DAVID Humala: Jah. Äkki lähme lihtsalt hoida lihtsa. Õigus? See ei sobi, kui ma tahan panna. Nii et ma panen ta tehniliselt kui B läheks. Nüüd, muidugi, ma olen hakanud maalida ennast nurka. Kui ma saan üliõpilane kelle nimi on tegelikult B nüüd B läheb liigutada veidi edasi, kuna võib juhtuda, jah, kui see on B, nüüd peab minema siit. 

Ja nii see väga kiiresti võib muutuda problemaatiliseks, aga see on tehnika, mis tegelikult nimetatakse lineaarse sondeerimine, mille sa lihtsalt kaaluma oma massiiv olla liinil. Ja sa lihtsalt omamoodi sondi või kontrollima iga saadaval element otsin saadaval kohapeal. Ja kui sa leiad üks, siis langeb ta sinna. 

Nüüd on hind, mida makstakse praegu Selle lahenduse on mis? Meil on fikseeritud suurus massiiv, ja kui ma sisestada nimed sinna, vähemalt esialgu, mis on sõiduaega sisestamise laskmise õpilaste viktoriinid õiges ämbrid? Big O mida? 

Sihtrühm: n. DAVID Humala: Kuulsin suur O n. Ei ole tõsi. Aga me tease peale miks just praegu. Mis veel võiks olla? 

Sihtrühm: [kuuldamatu] DAVID Humala: Ja las ma teen selle visuaalselt. Nii et arvan, et see on täht S. 

Sihtrühm: See on üks. DAVID Humala: See on üks. Õigus? See on massiiv, mille tähendab, et meil on ligi pääsema. Ja kui me mõtleme selle null ja seda 25, ja me saame aru, et oh, siin on minu sisend S, Võin kindlasti teisendada S, ASCII, kuni vastav arv nulli ja 25 ja siis kohe pane see, kuhu see kuulub. 

Aga muidugi, niipea kui saan Teine isik, kelle nime on A või B või C lõpuks, kui olen kasutanud lineaarne katsetamine minu lahendus, töötamise aeg sisestamise halvimal juhul tegelikult läheb vaimule mida? Ja ma ei kuule seda siin õigesti varakult. Sihtrühm: [kuuldamatu] DAVID Humala: Nii et see on n tõesti kord sul on piisavalt suur andmekogum. Niisiis, ühelt poolt, kas Sinu massiiv on piisavalt suur ja teie andmed on hõre piisavalt, siis saada see ilus konstantse ajaga. Aga niipea, kui hakkate üha rohkem ja rohkem elemente, ja lihtsalt statistiliselt saad rohkem inimesi tähega Oma nime või täht B, siis võib see vaimule midagi lineaarne. Nii et ei ole päris täiuslik. Nii saaksime teha paremini? 

Noh, mis oli meie lahendus enne, kui me tahad olla rohkem dünaamikat kui midagi massiivi lubatud? Sihtrühm: [kuuldamatu] DAVID Humala: Mida me tutvustada? Jah. Nii ahelloend. Noh, vaatame, mis on seotud nimekirja võib teha meie jaoks mitte. Noh, las ma ettepaneku, et me joonistada pilt järgmine. Nüüd on see erinev Pildi näide erinevast tekst, tegelikult, et on tegelikult kasutades massiivi suurus 31. Ja selle autor lihtsalt otsustas hash stringid ei põhine isiku nimed, vaid põhineb nende birthdates. Sõltumata sellest, kuu, siis arvasin kui sa oled sündinud esimene kuu või 31. kuu, autor ei räsi, mis põhineb selle väärtuse, et levinud nimesid välja natuke enamat kui lihtsalt 26 laigud võivad anda. Ja võib-olla see on natuke ühtlasem kui lähen tähestiku tähti sest loomulikult on ilmselt rohkem inimesi maailmas nimed et alustada kui kindlasti mõne teise tähestiku tähti. Nii et võib-olla see on natuke ühtsema, eeldades, ühtlase jaotuse beebide üle kuu. 

Aga muidugi, see on veel puudulik. Õigus? Meil oli kokkupõrkeid. Mitu inimest selles andmestruktuur veel millel on sama sünnikuupäev vähemalt sa oled olenemata kuus. Aga milline on autor teinud? Noh, tundub, et meil on massiiv vasakul servas joonistatud vertikaalselt, aga see on lihtsalt kunstniku üleviimise. Ei ole oluline, millises suunas sa juhtida massiivi, see on ikka massiivi. Mis see on massiivi ilmselt? 

Sihtrühm: seotud nimekirja. 

DAVID Humala: Jah. Tundub, et see on massiivi seotud nimekirja. Nii et jällegi, et see koht omamoodi kasutades nende andmestruktuuride nüüd koostisosadena rohkem huvitavaid lahendusi, saab absoluutselt võtma põhiõiguste, nagu massiiv, ja siis võta midagi rohkem huvitav nagu ahelloend ja isegi ühendada need isegi huvitavam andmestruktuur. Ja tõepoolest, ka see oleks nimetada hash tabelit, mille massiiv on tõesti hash tabelit, kuid hash tabelis on ketid, niiöelda mis võib kasvada või kahaneb põhineb mitmeid elemente, mida soovite lisada. 

Nüüd, seega, mis on sõiduaega nüüd? Kui ma tahan, et sisestada keegi kelle sünnipäev on 31. oktoober, kui ei, ta läks? Hea küll. Kõige all, kus ta ütleb 31. Ja see on täiuslik. See oli pidev aega. Aga mis siis, kui me leiame kellegi teise kelle sünnipäev on, vaatame, Oktoober, november, detsember 31? Kus on ta lähe? Sama asi. Kaks sammu küll. See on püsiv, kuigi kas pole? Hea küll. Praegusel hetkel on. Kuid üldiselt juhul, rohkem inimesi lisame, tõenäosuslikult me ​​läheme et saada rohkem ja rohkem kokkupõrkeid. 

Nüüd on see väike parem, sest tehniliselt nüüd on mu ahelaid võiks olla Halvimal juhul, kui kaua? Kui ma sisestan n inimesed sellesse rohkem keerukamaid andmestruktuur, n inimesi, halvimal juhul, et see saab olema n. Miks? 

Sihtrühm: Sest kui kõik on sama sünnipäev, nad ei kavatse olla üks rida. DAVID Humala: Perfect. See võib olla natuke kunstlik, kuid tõeliselt halvimal juhul kui kõigil on sama sünnipäev, antud sisendite olete, sa lähed on tohutult pikk kett. Ja nii, siis võiks seda nimetada hash tabel, kuid tegelikult on see lihtsalt massiivne seotud nimekirja Kogu palju raisatud ruumi. Aga üldiselt, kui me eeldame, et vähemalt sünnipäevad on uniform-- ja siis ilmselt ei ole. Ma teen selle ära. Aga kui me eeldame, et Huvides arutelu et nad on, siis teoreetiliselt kui see on vertikaalse esindatuse massiiv, hästi siis loodetavasti oled hakka ketid, tead, umbes sama pikk, kui iga need on päev kuus. 

Nüüd, kui seal on 31 päeva kuus, see tähendab, et minu sõiduaega tõesti on suur O n üle 31, mis tundub parem kui lineaarne. Aga mis oli üks meie kohustuste paar nädalat tagasi, kui ta tuli väljendades töötamise aeg algoritm? Lihtsalt vaadata ainult kõrge, et perspektiivis. Õigus? 31 on kindlasti kasulik. Aga see on ikka suur O n. Aga üks teemasid Probleemi seatud viis läheb üles tunnistama, et absoluutselt, asümptootiliselt teoreetiliselt see andmestruktuur ei ole parem kui lihtsalt üks massiivne seotud nimekirja. Ja tõepoolest, halvimal juhul on see hash tabelit võiks vaimule et. 

Aga reaalses maailmas, meie inimestele et oma Mac või PC-või mis iganes ja töötab reaalses maailmas tarkvara reaalses maailmas andmed, mis algoritmi sa lähed eelistate? Üks, mis leiab lõpuks samme või üks, mis võtab n jagatud 31 sammu leida mingi tükk andmed või otsida mõned andmed? Ma mõtlen, et absoluutselt 31 marki Erinevus reaalses maailmas. See on 31 korda kiirem. Ja meie, inimesed, oleme kindlasti läheb hindan seda. 

Nii et realiseerida dihhotoomia seal vahel tegelikult räägime asjad teoreetiliselt ja asymptotically mis kindlasti on väärtus, nagu me oleme näinud, kuid reaalses maailmas, kui sa hoolid lihtsalt tegemise inimese õnnelikuks üldine sisendite sa võiksid väga hästi taha nõustuda asjaolu, et jah, see on lineaarne, aga see on 31 korda kiirem kui lineaarne olla. Ja veel parem, me lihtsalt ei pea midagi meelevaldset nagu sünnikuupäev, võiksime kulutada veidi rohkem aega ja nutikust ja mõtle, mida me võiksime teha, antud isiku nime ja võib-olla oma sünnikuupäev ühendada need koostisosad välja nuputada midagi see on tõesti rohkem ühtne ja vähem sakiline, nii rääkida kui seda pilti Praegu näitab see võiks olla. Kuidas me saame rakendada seda koodi? Noh, las ma ettepaneku, et me lihtsalt laenata süntaks me oleme kasutatud paar korda siiani. Ja ma lähen, et määratleda sõlm, mis jällegi on üldnimetus vaid mõned konteiner mõne andmestruktuuri. Ma lähen ettepaneku string läheb sinna. Aga me ei kavatse hakata võtma need abirattad ära nüüd. 

Enam CS50 raamatukogu tõesti, kui soovite kasutada seda teie lõplik Projekt, mis on hea, kuid nüüd me ei kavatse tõmmake kardinapuud ja öelda, et see on lihtsalt char täht. Nii sõna seal saab olema isiku nimele. Ja nüüd on mul link siin järgmise sõlme nii, et need esindavad Iga sõlmed ahelas, potentsiaalselt on seotud nimekirja. 

Ja nüüd, kui ma kuulutada hash tabelit ise? Kuidas kuulutada kogu see struktuur? Noh, tegelikult, palju nagu ma harjunud pointer lihtsalt esimene element nimekirja enne sarnaselt ma saan ainult öelda, Ma lihtsalt pean hunnik viiteid rakendada seda kogu hash tabelis. Ma lähen on massiivi nimetatakse tabelit hash tabelis. See saab olema suurust võimsust. See, kui palju elemente mahub ta. Ja kõik need elemendid selles massiivi läheb sõlme star. Miks? Noh, kohta see pilt, mida ma olen rakendamisel hash tabelit tõhusalt algusest on lihtsalt Selle massiivi et oleme tõmmatud vertikaalselt, Iga kelle väljakud esindab pointer. See need, mis on kaldkriipsuga nende kaudu on lihtsalt null. Ja need, mis on nooled läheb paremale on tegelik vihjeid tegelik sõlmede Ergo algust seotud nimekirja. 

Nii et siin on siis kuidas me võiksime rakendada hash tabelit, et rakendab eraldi ühendamine. Nüüd me saame teha paremini? Olgu Lubasin viimane kord, võiksime saavutada konstantset aega. Ja ma omamoodi andis sulle konstantset aega siin, kuid siis ütles, ei ole tõesti pidev aeg, sest see on ikka sõltub kokku elementide arv sa oled sisestamist andmestruktuur. Aga oletame me seda tegime. Lubage mul minna tagasi ekraanil siin. Lubage mul ka projitseerida see siin, selge ekraanile ja arvan, et ma tegin seda. Oletame, et ma tahtsin lisada nimi Daven aastal minu andmete struktuuri. 

Ma tahan lisada string Daven arvesse andmete struktuuri. Mida teha, kui ma ei kasuta hash tabel, kuid ma kasutan midagi, mis on rohkem puu-like nagu sugupuu, kus teil on root top ja siis sõlmede ja lehed mis lähevad alla ja väljapoole. Oletame siis, et ma soovite lisada Daven poolt arvesse, milline on hetkel tühi nimekiri. Ma lähen tegema järgmist: Ma olen kavatse luua sõlme selles perekonnas puu-like andmete struktuur, mis näeb välja natuke niimoodi, millest igaüks ristkülikud on, ütleme, nüüd 26 elemente. Ja iga rakkudes selles array läheb esindada kirja tähestik. 

Täpsemalt, ma lähen raviks see on, siis B, siis C, siis D see siin. Nii et see saab tõhusalt esindavad kirja D. Aga sisestada kõik Daven on nimi mida ma pean tegema natuke rohkem. Nii et ma olen esimene läheb räsi, nii rääkida. Ma lähen vaatama algustäht aastal Daven on mis on ilmselgelt D ja ma lähen eraldada sõlm, mis näeb välja nagu see-- suur ristkülik suur piisavalt, et see sobiks kogu tähestikku. 

Nüüd D on tehtud. Nüüd A. D--V-E-N on eesmärk. Nii et nüüd ma lähen tegema, on see. Niipea kui hakkasin D teade pole pointer seal. See on prügi väärtused hetkel, või ma võin selle vormindamiseks tühjaks. Aga las ma käiks koos Selle ehitamise idee puu. Lubage mul eraldada veel üks neist sõlmed, mis on 26 elemente. 

Ja tead mis? Kui see on lihtsalt sõlme mälu Ma loodud malloc, kasutades struct nagu me varsti näeme, Ma lähen tegema see-- Ma lähen juhtida nool asi, mis esindab D alla Selle uue sõlme. Ja nüüd, esimene järgmise kirja Daven nimi, V- D--V- ma lähen edasi minna ja juhtida teise sõlme meeldib see, kusjuures, V elementide siit, mida me joonistada instance-- whoops. Me ei tõmba sinna. See saab minna siin. 

Siis me ei kavatse peavad seda V. Ja siis siin me ei kavatse indeks maha V, mida me kaaluda E. Ja siis siit me läheme minge üks neist sõlmede siin. Ja nüüd on küsimus vastata. Mul on vaja kuidagi näidata, et me lõpus stringi Daven. Nii et ma võiks lihtsalt jätta see null. 

Aga kui meil on Daven poolt täisnimi ka, mis on, nagu me oleme öelnud, Davenport? Mis siis, kui Daven on tegelikult alamstring, eesliide palju pikem string? Me ei saa lihtsalt püsivalt Rääkimata läheb sinna minna, sest me võiksime kunagi sisestada sõna nagu Davenport sellesse andmestruktuur 

Niisiis, mida me võiksime teha, selle asemel on Raviks iga nende elementide nagu võibolla millel on kaks elementide sees neist. Üks on osuti tõepoolest nagu ma olen teinud. Nii et kõik need karbid ei ole vaid ühe lahtri. Aga kui top one-- alt üks saab olema null, sest puudub Davenport veel. Mis siis, kui ülemine on mingi eriline väärtus? Ja see saab olema veidi raske tõmmata ta selle suurus. Aga arvan, et see on lihtsalt linnuke. Kontrolli. D--V-E-N on string selles andmestruktuur. 

Vahepeal, kui mul oleks rohkem ruumi siin, ma võiks teha P-O-R-T, ja ma võiks panna check sõlme mis on kirjas T päris lõpus. Nii et see on tohutult keeruline välimusega andmestruktuur. Ja minu käekiri Kindlasti ei aita. Aga kui ma tahan lisada midagi muud, kaaluma, mida me teeme. Kui me tahtsime panna Taavet, me tahaks järgida sama loogikat, D--V aga nüüd märgin järgmise element mitte E, vaid I D. Nii et saab olema rohkem tippe seda puud. Me läheme on kõne malloc rohkem. Aga ma ei taha teha täielik jama see pilt. Nii et olgem selle asemel vaadata ühe mis on olnud eelnevalt koostatud niimoodi ei dot, dot, täpid, aga lihtsalt lühendatult massiivid. Kuid iga sõlmed Selles puu siin on sama asi-- massiivi Ray suurus 26. 

Või kui me tahame olla tõesti õige nüüd, mida kui kellegi nime ülakomaga, olgem eeldada, et iga sõlm on tegelikult nagu 27 indeksid seda, mitte ainult 26. Nii et see nüüd läheb andmed struktuuri nimetatakse trie-- T-R-I-E. Prefiksipuu, mis on väidetavalt ajalooliselt nutikas nimi puu mis on optimeeritud otsing, mis muidugi kirjutatakse I-E, nii see on Prefiksipuu. Aga see on ajalugu Prefiksipuu. 

Nii Prefiksipuu on see puu-like andmete struktuur nagu sugupuu et lõpuks käitub niimoodi. Ja siin on lihtsalt üks järjekordne näide terve hunnik teiste inimeste nimed. Aga küsimus nüüd käepärast on see, mis on Me saime kehtestades vaieldamatult rohkem keeruline andmestruktuur, ja üks, ausalt, mis kasutab palju mälu. 

Sest kuigi hetkel, ma olen ainult kasutades D's osuti ja Ja V Es ja Ns, Ma raisata Heck palju mälu. Aga kus ma veedan ühe ressursi, Ma pigem ei saada tagasi teise. Nii et kui ma kulutada rohkem ruumi mis on ilmselt lootust? Et ma olen vähem kulutama mida? Sihtrühm: Vähem aega. DAVID Humala: Aeg. Nüüd, miks see võiks olla? Noh, mis on sisestamise ajal nii suur O nüüd, nime nagu Daven või Davenport või David? Noh, Daven oli viis sammu. Davenport oleks üheksa astet, nii et see oleks veel paar sammu. David oleks viis sammu samuti. Nii et need on betooni numbreid, kuid kindlasti pole ülemise kohta pikkus kellegi nime. Ja tõepoolest, on probleem komplekti viis kirjeldusele me ei kavatse teha ettepanekuid et see on midagi, see on 40-mõned-paaritu tähemärki. 

Reaalselt ei ole keegi lõpmatult pikk nimi, mis tähendab, et pikkus Nimi või pikkus string me võiksime on teatud seisund struktuur on vaieldamatult mida? See on pidev. Õigus? See võib olla suur konstantne nagu 40-midagi, kuid see on konstantne. Ja see ei ole sõltuvus, kui palju teised nimed on selles andmestruktuur. Teisisõnu, kui ma tahtsin nüüd sisestada Colton või Gabriel või Rob või Zamyla või Alison või Belinda või muud nimed alates personal sellesse andmed struktuuri, on sõiduaega sisestades muud nimed saab olema kõik mõjutanud kui palju muid elemente andmestruktuuris juba? See ei ole. Õigus? Kuna me tegelikult kasutab see mitmekihiline hash tabelis. Ja sõiduaega kõik need toimingud ei sõltu arvu kohta elemendid, mis on andmestruktuur või mis lõpuks läheb olema andmestruktuur, kuid pikkus, mida konkreetselt? 

String on sisestatud, mis ei tee Selle asymptotically pidev AEG_ suur O ühe. Ja ausalt öeldes, igaks reaalses maailmas, see tähendab sisestamist Daven nime võtab nagu viis sammu või Davenport üheksa samme või David viis sammu. See on päris darn väike jooksmine korda. Ja tõesti, see on väga hea asi, eriti kui see ei sõltu kokku elementide arv seal. Niisiis, kuidas võiks me rakendada seda selline struktuur koodi? See on veidi rohkem keeruline, kuid siiski on see lihtsalt kohaldamist põhiplokke. Ma lähen uuesti meile sõlme järgmiselt: bool nimetatakse word-- ja see võiks nimetada midagi. Aga bool esindab mida ma joonistasin nagu linnuke. Jah. See on lõpuks string selles andmestruktuur. 

Ja muidugi sõlme tärni seal viitab lastele. Ja tõesti, just nagu sugupuu, siis kaaluks sõlmed mis ripuvad välja põhja mõned vanema element olema lapsed. Ja nii lastel läheb olema massiiv 27, 27. üks olemisele eest ülakoma. Me läheme sorteeri erijuhtum seda. Nii et teil on teatud nimed ülakomad. Võib-olla isegi sidekriipsuga peaks sinna minna, aga sa pead vt lk komplekt 5 me vaid ravi umbes tähed ja ülakomad. 

Ja siis kuidas te esindate andmestruktuur ise? Kuidas esindavad juur Selle Prefiksipuu niiöelda? Noh, lihtsalt meeldib koos seotud nimekirja, siis vaja viit esimese osaga. Mis Prefiksipuu sa lihtsalt vaja üks kursor root selle Prefiksipuu. Ja sealt saab hash teed alla sügavamale ja sügavamale iga teise sõlme struktuuri. Nii lihtsalt selle saab me esindame, et struktuure. 

Nüüd Meanwhile-- Oh küsimus. 

Sihtrühm: Mis bool sõna? 

DAVID Humala: Bool sõna just see C kehastus mida ma kirjeldasin Selles lahtris siin, kui Hakkasin jagades iga massiivi elemente kaks tükki. Üks on viit järgmise sõlme. Muud peab olema midagi ruut öelda jah, seal on Sõna Daven mis lõpeb siin, sest me ei taha, hetkel, Dave. 

Kuigi Dave saab olema õigustatud sõna, ta ei Prefiksipuu veel. Ja D ei ole sõna. Ja D-ei ole sõna või nimi. Nii linnuke näitab alles siis, kui tabanud see sõlm on Eelmise tee tähemärki tegelikult string et olete sisestanud. Nii et kõik bool seal teeb meile. 

Muid küsimustele proovib? Jah. 

Sihtrühm: Mis on kattuvad? Mida teha, kui teil on Dave ja Daven? DAVID Humala: Perfect. Mida teha, kui teil on Dave ja Daven? Nii et kui me lisada, ütleme hüüdnimi jaoks David-- Dave-- D--V-E? See on tegelikult super lihtne. Nii et me ainult kavatse võtta neljast etapist. D--V-E. Ja mida ma pean teha, kui ma tabanud, et neljanda sõlme? Just kavatse vaadata. Oleme juba hea minna. Valmis. Neli sammu. Pidev aja asymptotically. Ja nüüd me oleme näidanud, et nii Dave ja Daven on stringid struktuuris. Niisiis ei ole probleem. Ja pange tähele, kuidas kohalolek kohta Daven ei pääsenud võtab rohkem aega või vähem aeg Dave ja vastupidi. 

Niisiis, mida me saame nüüd teha? Oleme kasutanud seda metafoori enne plaate esindavad midagi. Aga selgub, et virna on tegelikult demonstratiivne teise abstraktsete andmete liik-- kõrgem andmestruktuur et lõpus päeval on lihtsalt nagu massiivi või seotud nimekirja või midagi rohkem Ilmalik. Aga see on huvitav kontseptuaalne mõiste. Stack, nagu need salved siin Mather, nimetatakse üldiselt lihtsalt selle-- virna. 

Ja seda tüüpi andmestruktuuri Teil on kaks operations-- teil on üks nn push lisades midagi virna, justkui teise salve tagasi magasini tippu. Ja siis pop, mis tähendab, et sa võtta tähtsaim salve välja. Aga mis peamine kohta virna, et see ju see kummaline omadus. Kuna söögisaal töötajad ümberkorraldamine salved järgmise toidukorra, mis saab olema tõsi, kuidas õpilased suhelda andmete struktuur? Sihtrühm: Nad lähevad pop ühekordne. DAVID Humala: Nad lähed pop ühekordne loodetavasti tippu. Muidu on see lihtsalt tobe minna kõik viis põhja. Õigus? Andmete struktuur ei võimalda hästi teil haarata põhja salve vähemalt lihtsalt. Nii et see on uudishimulik vara korstnat et viimane element on saab olema esimene välja. Ja arvuti teadlased nimetavad Selle LIFO-- kesta sisse, esimesena välja. Ja tegelikult ei ole huvitavaid rakendusi. See ei ole tingimata nii ilmne, nagu mõned teised, kuid see võib tõepoolest olla kasulik, ja see võib tõepoolest ellu paari erinevalt. 

Nii et üks, ja tegelikult, las mulle ei sukelduda seda. Teeme selle asemel. Vaatame üks, mis on peaaegu Sama mõte, aga see on natuke õiglasem. Õigus? Kui sa oled üks neist fänn poisid või tüdrukud, mis tõesti meeldib Apple tooted ja sa ärkasin kell 03:00 rivistama teatud kauplus saada uusimaid iPhone, siis oleks sabas kuni niimoodi. 

Nüüd järjekord on väga teadlikult nimega. See on joon, sest seal on mõned õiglus ta. Õigus? Oleks selline imeda kui olete sain seal esmalt Apple Store aga sa oled tegelikult kõige alumine salve, sest Apple töötajad siis pop viimane inimene, kes tegelikult sain kooskõlas. Nii korstnad ja järjekorrad, kuigi funktsionaalselt nad omamoodi same-- see on lihtsalt selle kollektsiooni ressursse, mis on läheb kasvama ja shrink-- seal see õigluse aspekt see, vähemalt reaalses maailmas, kus tegevuse treenite on täiesti erinevad. Stack-- järjekorda rather-- ütles, et on kaks operatsiooni: n järjekorda ja d järjekorda. Või võite helistada neile mis tahes mitmeid asju. Aga sa lihtsalt tahad lüüa arusaam, et üks on lisades ja üks on lõpuks lahutada. 

Nüüd all kapuuts, nii korstnat ja järjekord võiks rakendada siis kuidas? Me ei hakka koodi sest kõrgema Idee on omamoodi ilmsem. Ma mõtlen, mida inimesed teevad? Kui ma olen esimene inimene, kes on Apple Hoidke ja see on välisuks, tead, ma lähen siin seista. Ja järgmine isiku läheb siin seista. Ja järgmine isiku läheb siin seista. Mida andmestruktuur sobiv järjekord? 

Sihtrühm: järjekorda. DAVID Humala: Noh, järjekorda. Muidugi. Mida veel? 

Sihtrühm: seotud nimekirja. 

DAVID Humala: seotud nimekiri, mida võiks rakendada. Ja ahelloend on tore, sest siis see võib kasvada meelevaldselt pika erinevalt võttes teatud fikseeritud number inimesed poest. Aga võib-olla fikseeritud arv kohti on õigustatud. Sest kui nad ainult nagu 20 iPhone'i esimesel päeval, võibolla nad on vaja ainult massiivi suurus 20 esindamiseks et järjekorda, mis ainult öelda nüüd, kui hakkame rääkima nendest kõrgema taseme probleemid, saab seda rakendada igal mitmel viisil. Ja seal on ilmselt lihtsalt läheb olema kompromiss ajas ja ruumis või ainult oma koodi keerukust. 

Aga pakk? Noh, korstna, oleme näinud liiga võib olla lihtsalt nende plaate. Ja siis võiks rakendada seda massiivi. Aga mingil hetkel, kui kasutad massiiv, mis juhtub, et salved üritate panema? Hea küll. Sa oled ainult kavatse oleks võimalik minna nii kõrge. Ja ma arvan, et Mather nad tegelikult süvistatakse et avamist. Nii et tõesti, see on peaaegu nagu Ema kasutab massiivi fikseeritud suurus, sest saab ainult mahub nii palju plaate, et avamine seina allapoole inimeste põlvi. Ja nii, et oleks Öeldakse, massiiv, aga me võiksime kindlasti rakendada, et üldisemalt seotud nimekirja. 

Noh, mida veel umbes andmestruktuur? Lubage mul tõmba üks muu visuaalse siin. Midagi kuidas see siin? Miks võib see olla kasulik pole midagi nii väljamõeldud kui Prefiksipuu, mis me nägime oli neid väga palju tippe, millest igaüks on massiivi? Aga mis siis, kui me teeme midagi lihtsalt, nagu vana kooli sugupuu Iga mille sõlmed siin lihtsalt ladustamiseks number. Selle asemel, et nime või järeltulija lihtsalt ladustamiseks number niimoodi. 

Noh, kõnepruuki me kasutame andmestruktuurid on nii üritab ja puud, kus Prefiksipuu on jällegi vaid üks, mille tipud on massiivid on ikka see, mida sa võiksid kasutada alates algkool kui sa tegid perekond tree-- lehed ja juur puu ja lapsed vanem ja õdede-vendade hulgast. Ja me võiksime rakendada puu, Näiteks, kui lihtsalt see. Puu, kui seda sõlme, üks need ringid, mis on mitu, ta ei kavatse olla üks pointer, vaid kaks. Ja niipea, kui lisate teine ​​osuti, siis võib tegelikult nüüd tegema omamoodi kahemõõtmeline andmed struktuuride mälu. Palju nagu kahemõõtmeline massiiv, saate on omamoodi kahemõõtmeline ahelloendid kuid need et järgida muster kus pole tsüklit. See on tõeliselt puu ühe vanavanem, kuidas siia üles ja siis mõned vanemad ja lapsed ja lapselapsed ja lapse-lapselast. ja nii edasi. 

Aga mis on tegelikult puhas sellest ka, lihtsalt kiusa natuke koodi tagasikutsumise recursion alates mõnda aega tagasi, kusjuures Sa kirjutad funktsioon, mis nimetab ennast. See on ilus võimalus rakendada midagi nagu recursion, sest pean seda. 

See on puu. Ja ma olen olnud veidi anal, kuidas Panin täisarvud tänavale. Nii palju, et see on eriline name-- kahendotsingupuu. Nüüd oleme kuulnud binaarne otsida, kuid sa saad tööle tagasi selle asja nimi on? Mis on muster, kuidas ma sisestatud täisarvud sellesse puu? See ei ole meelevaldne. Seal on mõned muster. Jah. 

Sihtrühm: Väiksemad vasakul. 

DAVID Humala: Jah. Väiksemad on vasakul. Suuremad neist on paremal. Selline, et õige väide on vanem on suurem kui vasaku laps, kuid vähem kui selle õige laps. Ja et üksi on isegi rekursiivne verbaalne definitsioon sest võite taotleda, et Sama loogika, et iga sõlme ja see ainult põhjad välja, tugipunkti, kui te hakkab, kui vajutad üks lehed, nii et rääkida, kui puhkust ei ole lapsi veelgi. 

Nüüd, kuidas võiks leida number 44? Sa hakkaks keskmes ja öelda, hm. 55 ei ole 44 Nii et ma tahan minna õige või ma tahan minna vasakule? Noh, ilmselt sa tahad minna vasakule. Ja nii see on nagu telefon raamat näiteks binaarne otsing üldisemalt. Aga me selle rakendamiseks Nüüd veidi dünaamiliselt kui massiivi võib lubada. Ja tegelikult, kui soovite otsida kell kood esmapilgul kindel. Tundub, et terve hunnik ridu. Aga see on ilusti lihtne. Kui soovite rakendada funktsioon nimetatakse otsingumootori kelle eesmärk elus on otsida väärtus nagu n, täisarv ja sa oled sooritanud ühe pointer-- kursor sõlme juured, pigem selle puu, millest pääsete kõik muu, märgata, kuidas arusaadav saab rakendada loogikat. Kui puu on null, ilmselt see ei ole seal. Lähme lihtsalt tagasi vale. Õigus? Kui sa käe ta midagi, seal on midagi seal. 

Muud, kui n on alla puu nool n-- nüüd nool n, meenutada tutvustasime super lühidalt mõni päev tagasi, ja see tähendab lihtsalt de-viide pointer ja vaadata Väli n. Nii et see tähendab, minna ja vaadata Väli n. Nii et kui n väärtus olete andnud, on vähem kui väärtus on puud täisarv, kus sa tahad minna? Vasakule. 

Nii märkate recursion. Ma returning-- ole tõsi. Ei ole vale. Ma naasmist iganes vastus on kõne ise, mis kulgeb n uuesti, mis on koondatud, kuid milline on veidi erinev nüüd? Kuidas ma muutes probleem väiksem? Ma möödaminnes kui teine argument, mitte puu juur, kuid vasakul lapse käesolevas asjas. Nii et ma olen kulgeb vasakult laps. 

Vahepeal, kui n on suurem kui sõlme Ma olen praegu vaadates, Ma otsin löögile. Else, kui puu ei ole null, ja kui element on mitte vasakul ja see ei ole õigust, mis on imeliselt puhul? Me oleme tegelikult leidnud sõlme küsimus, ja nii me tagasi tõsi. 

Nii oleme lihtsalt kriimustatud pinda nüüd mõned neist andmestruktuuride. In probleem seatud viie saate uurida neid veelgi, ja antakse teile oma disaini otsustada, kuidas edasi minna. Mida ma tahaksin teha järeldusi on vaid 30-sekundiline teaser mis ootab järgmisel nädalal ja pärast seda. 

Nagu me begin-- õnneks võite think-- meie üleminek aeglaselt maailmast C ja madalam tasandil rakendamise üksikasju, et maailmas, kus me saame võtta anda, et keegi on lõpuks rakendatakse neid andmeid struktuuride meile ja hakkame mõistma Reaalses maailmas rakendusaktidega veebipõhiste programmidega ja veebilehed üldisemalt ja ka väga julgeolek mõju, et me oleme ainult hakanud pinnapealselt. Siin on, mida ootab meid päevil tulla. 

[VIDEO PLAYBACK] 

-Ta Tuli teade, koos protokolliga kõik omal. Ta tuli maailma julm tulemüürid uncaring ruuterid ja ohte palju hullem kui surm. Ta on kiire. Ta on tugev. Ta on TCP / IP, ja tal on oma aadress. "Warriors of the Net." [END VIDEO PLAYBACK] DAVID Humala: Tulevad järgmisel nädalal. Me näeme siis. [VIDEO PLAYBACK] -Ja Nüüd, "Deep Mõtted" poolt Daven Farnham. -David Algab alati loengud, "Olgu." Miks mitte, "Siin on lahendus selle nädala probleem komplekt " või "Me anname teile kõigile?" [Naerab] [END VIDEO PLAYBACK]