[Musikken afspilles] DAVID MALAN: Dette er CS50. Og det er både begyndelsen og end-- ligesom literally-- næsten enden af uge seks. Jeg troede, jeg ville dele en lidt af en sjov kendsgerning. Jeg har trukket det op fra en data forløbne semesters indstillet. Du husker måske, at vi beder dig om hver p sæt formular, hvis du har set online eller hvis du har deltaget i person. Og her er dataene. Så i dag var meget forudsigelig. Men vi ønskede at tilbringe en smule af tid sammen med dig alligevel. Ville nogen gerne formodninger hvorfor dette graf er så jaggy, op ned, op ned, så konsekvent? Hvad gør hver af toppene og trug repræsentere? PUBLIKUM: [uhørligt] DAVID MALAN: Ja. Og mere underholdende, gud forbyde det, vi holder et foredrag på en fredag i begyndelsen af ​​semestret, det er, hvad vi ser ske. Så i dag, vi deltager i en lidt mere om datastrukturer. Og for at give dig mere af en solid mental model for problemer på fem, der er nu ude. Stavefejl, hvor, vil vi hånd du en tekstfil omkring 100.000 plus engelske ord, og du er nødt til at finde ud af, hvordan man behændigt indlæse dem ind i hukommelsen, i RAM, ved hjælp af nogle data opbygning af dit valg. Nu en sådan datastruktur kunne være, men burde nok ikke være, den ret forsimplede linkede liste, som vi introducerede sidste gang. Og en sammenkædet liste havde mindst en fordel i forhold til et array. Hvad der er en fordel ved en sammenkædet liste velsagtens? PUBLIKUM: Indsættelse. DAVID MALAN: Indsættelse. Hvad mener du med det? PUBLIKUM: Anywhere sammen listen [uhørligt]. DAVID MALAN: God. Så du kan indsætte et element, hvor du ønsker i midten af ​​listen uden at blande noget, som vi konkluderede i vores sortering diskussioner, er ikke nødvendigvis en god ting, fordi det tager tid at faktisk bevæge alle disse mennesker til venstre eller højre. Og så med en linket liste, kan du bare tildele med malloc en ny node, og derefter opdatere et par pointers-- to, tre operationer max-- og vi er i stand til slot nogen i overalt i en liste. Hvad der ellers var fordelagtig om en sammenkædet liste? Ja? PUBLIKUM: [uhørligt] DAVID MALAN: Perfect. Perfect. Det er virkelig dynamisk. Og at du ikke begå, i forvejen, til nogle faste størrelse luns af hukommelse, ligesom du ville have til med et array, opadrettede som er, at du kan tildele knuder kun på efterspørgsel og dermed kun bruger så meget plads som du rent faktisk har brug for. I modsætning til et array, kan du uheld tildele for lidt. Og så er det bare at gå at være en smerte i nakken at omfordele en ny større array, kopiere alt i, befri den gamle array, og derefter flytte om din virksomhed. Eller endnu værre, kan du tildele måde mere hukommelse end du rent faktisk har brug for, og så du kommer til at have en meget tyndt befolkede array, så at sige. Så en sammenkædet liste giver dig disse fordele ved dynamik og fleksibilitet med indsætninger og sletninger. Men sikkert skal der være en pris betalt. Faktisk er en af ​​de temaer udforskes på quiz nul var et par af de afvejninger vi har set hidtil. Så hvad er en pris, der betales eller en Ulempen ved en linket liste? Ja. PUBLIKUM: Ingen random access. DAVID MALAN: Ingen random access. Men hvem bekymrer sig? Random access lyder ikke overbevisende. PUBLIKUM: [uhørligt] DAVID MALAN: Præcis. Hvis du vil have en vis algorithm-- og lad mig faktisk foreslå søgning binær især som er en vi har brugt en hel bit-- hvis du ikke har random access, du kan ikke gøre det simple aritmetiske finde ligesom den midterste element og hoppe ret til det. Du i stedet nødt til at starte på det første element og lineært søge fra venstre til højre, hvis du ønsker at finde midten eller noget andet grundstof. PUBLIKUM: Det tager nok mere hukommelse. DAVID MALAN: Tager mere hukommelse. Hvor er det ekstra koste kommer fra i hukommelsen? PUBLIKUM: [uhørligt] DAVID MALAN: Præcis. I dette tilfælde her, havde vi en sammenkædet liste for heltal, og alligevel er vi fordobling mængden af ​​hukommelse vi har brug for ved også at opbevare disse pejlemærker. Nu mindre af en big deal som dine structs får større og du lagre ikke et nummer, men måske en studerende eller en anden genstand. Men punktet bestemt tilbage. Og så en række af de aktioner, om hægtede lister blev kaldt var store O n- lineær. Ting som indsættelse eller søg eller sletning i tilfælde et element tilfældigvis i slutningen af listen uanset om det er sorteret eller ej. Nogle gange kan du få heldig og i så nedre grænser på disse operationer kunne også være konstant tid, hvis du er altid kigger på det første element, f.eks. Men i sidste ende, vi lovede at opnå den hellige gral datastrukturer, eller vis tilnærmelse deraf ved konstant tid. Kan vi finde elementer eller tilføje elementer eller fjerne elementer fra en liste? Vi skal se meget snart. Og det viser sig, at en af de mekanismer, vi er vil begynde at bruge i dag, årlige forbrug i p sæt fem, er faktisk temmelig bekendt. For eksempel, hvis dette er en flok eksamensspørgsmål bøger, som hver har en elevs første navn og efternavn på den, og jeg hente dem fra ved slutningen af ​​en eksamen, og de er alle temmelig meget i en tilfældig rækkefølge, og vi ønsker at gå om sortering disse eksamener, så engang sorteres det er bare meget nemmere og hurtigere at udlevere dem ud igen til studerende alfabetisk. Hvad ville dine instinkter være for en bunke af eksamener som denne? Tja, hvis du er ligesom mig, du kunne se, at dette er m, så jeg har tænkt mig at slags sætte det i, hvis dette er mit bord eller min etage, hvor Jeg sprede tingene out-- eller min opstilling really-- Jeg kunne sætte alle MS i der. Oh. Her er en A. Så jeg måske sætte Som herovre. Oh. Her er en anden A. Jeg har tænkt mig at sætte det herovre. Her er en Z. Her er en anden M. Og så Jeg kunne begynde at gøre bunker som denne. Og så måske jeg vil gå i senere og sortering af meget nitpicky-ly slags de enkelte pæle. Men pointen er, at jeg ville se ved indgangen, at jeg er handed og jeg ville gøre nogle beregnede beslutning baseret på denne indgang. Hvis den begynder med A, sætte det derovre. Hvis den begynder med Z, sætte det over der, og alt derimellem. Så dette er en teknik, der er almindeligt kendt som hashing-- H-A-S-H-- hvilket generelt betyder at tage som input og bruge dette input til at beregne en værdi, der generelt er et tal, og at nummer er indekset i et lager beholder, som et array. Så med andre ord, kunne jeg have en hash-funktionen, som jeg gør i mit hoved, at hvis jeg ser nogen er navn, der starter med A, Jeg har tænkt mig at kortlægge det til nul i mit hoved. Og hvis jeg ser en person med Z, jeg er kommer til kort, der til 25 i mit hoved og derefter sætte det ind sidste mest bunken. Nu, hvis du tænker over ikke min hjerne men et C-program, hvilke numre kunne du stole på at opnå det samme resultat? Med andre ord, hvis du havde ASCII A, hvordan kan du bestemme hvad spand at sætte det i? Du har sandsynligvis ikke ønsker at sætte det ind i spand 65, som ville være ligesom derovre uden god grund. Hvor vil du sætte A i form af dens ASCII værdi? Hvor vil du gøre for at dens ASCII værdi at komme op med en smartere spand at sætte det i? PUBLIKUM: Minus A. DAVID MALAN: Ja. Så minus A eller minus specifikt 65, hvis det er en kapital A. Eller 98, hvis det er et lille et. Og så ville tillade os at, meget enkelt og meget aritmetisk sætte noget i en spand som. Så det viser sig, vi rent faktisk gør det så godt selv med quizzer. Så du kan huske du kredsede din undervisning fyrs navn på omslaget. Og TF navne var organiseret i disse kolonner alfabetisk, godt, tro det eller ej, når alle 80 plus os fik sammen den anden aften til lønklasse, det sidste trin i vores grading proces er at hash quizzer ind i en stor rum etage på [uhørligt] og lægge alles quizzer ud i nøjagtig den rækkefølge, deres TF s navne på dækslet, da så er det meget lettere for os at søge gennem at anvendelse af lineær søge eller anden form for klogskab til TF at finde hans eller hendes studerendes quizzer. Så denne idé om hashing at du vil se, er ganske stærke er faktisk temmelig banal og meget intuitiv, ligesom måske opdele og erobring var i uge nul. Jeg hurtigt frem til hackathon et par år siden. Dette var Zamyla og et par andre ansatte hilsen studerende som de kom ind. Og vi havde en hel bunke af foldning tabeller der med navneskilte. Og vi havde navneskilte organiseret med ligesom Som derovre og Zs derovre. Og så en af ​​TFS meget behændigt skrev dette som instruktioner for dagen. Og i uge 12 af semestret dette alle gav god mening, og alle vidste, hvad de skal gøre. Men når du har kø på samme måde, du gennemføre samme forestilling om en hash. Så lad os formalisere det en lille smule. Her er et array. Det er udarbejdet til at være lidt bred bare at skildre, visuelt, at vi kan sætte strenge i noget som dette. Og dette array er tydeligt af størrelse 26 total. Og de ting kaldes tabel vilkårligt. Men dette er blot en kunstners gengivelse af, hvad en hash tabel kan være. Så en hashtabel nu kommer til at være et højere niveau datastruktur. Ved slutningen af ​​dagen vi er ved at se, at du kan gennemføre en hash tabel, som er meget ligesom check-in-line ved en hackathon meget som denne Tabellen, der anvendes til sortering eksamen bøger. Men en hash tabel er art af det høje koncept, der kunne bruge et array under hætten til at gennemføre den, eller det kunne bruge en liste længde, eller endog måske nogle andre datastrukturer. Og nu det er den theme-- udtagning nogle af disse grundlæggende ingredienser som en matrix, og denne bygning blokere nu en liste længde og se, hvad vi ellers kan bygge på toppen af ​​dem, ligesom ingredienser i en opskrift, så mere og mere interessante og nyttige endelige resultater. Så med hash tabellen vi måske gennemføre den i hukommelsen billedligt som denne, men hvordan kan det faktisk være kodet op? Nå, måske så enkelt er det. Hvis kapacitet i alle kasketter, er bare nogle constant-- for eksempel 26, for 26 bogstaver i det alphabet-- Jeg kunne kalde min variabel bord, og jeg kunne påstå, at jeg har tænkt mig at sætte char stjerner derinde, eller snor. Så det er så simpelt som dette, hvis du ønsker at gennemføre en hash tabel. Og dog, det er virkelig bare et array. Men igen, en hash Tabellen er nu, hvad vi får kalder en abstrakt datatype, der er bare sortering af en begrebsmæssig lagdeling på toppen af noget mere prosaisk Nu vil et array. Nu, hvordan gør vi gå om at løse problemer? Tja, tidligere havde jeg den luksus for at have nok bordplads her så jeg kunne sætte quizzer overalt jeg ønskede. Så kan gå her. Zs kan gå her. Ms kan gå her. Og så havde jeg nogle ekstra plads. Men det er lidt af en snyde ret nu, fordi denne tabel, hvis jeg virkelig tænkte på det som et array, er bare kommer til at være af en vis fast størrelse. Så teknisk set, hvis jeg trækker op en anden elevs quiz og se, åh, denne persons navn starter med et A også, Jeg slags ønsker at sætte det der. Men så snart jeg sætte det der, hvis denne tabel faktisk udgør et array, Jeg har tænkt mig at være tvingende eller clobbering hvem denne studerendes quiz er. Right? Hvis dette er et array, kun én ting kan gå i hver af disse celler eller elementer. Og så jeg har slags at vælge og vrage. Nu jeg tidligere slags snydt og gjorde dette eller jeg lige slags stablet dem over hinanden. Men det kommer ikke til at flyve i koden. Så hvor kan jeg sætte anden elev, hvis navn er A, hvis alt havde jeg er dette tilgængelig tabel plads? Og jeg har brugt tre slots og det ser ud der er bare et par andre. Hvad kunne du gøre? PUBLIKUM: [uhørligt] DAVID MALAN: Ja. Måske lad os bare holde det simpelt. Right? Det passer ikke, hvor jeg ønsker at sætte det. Så jeg har tænkt mig at sætte det teknisk hvor B ville gå. Nu, selvfølgelig, er jeg begyndt at male mig op i et hjørne. Hvis jeg kommer til en elev hvis navn er faktisk B, nu B vil blive flyttet lidt fremad, som kunne ske, jep, hvis dette er et B, nu er det at gå her. Og så dette meget hurtigt kan blive problematisk, men det er en teknik, der faktisk betegnes som lineær probing, hvorved du lige overveje din array til at være langs linien. Og du bare slags sonde eller inspicere hver tilgængelig element på udkig efter en ledig plet. Og så snart du finder en, du skulle tabe det derinde. Nu, idet den betalte pris nu denne løsning er hvad? Vi har en fast størrelse array, og når jeg sætter navne i det mindste i begyndelsen, hvad er køretiden for indsættelse for at sætte de studerende quizzer i de rigtige spande? Big O i hvad? PUBLIKUM: n. DAVID MALAN: Jeg hørte store O n. Ikke sandt. Men vi vil drille hinanden hvorfor i bare et øjeblik. Hvad ellers kunne det være? PUBLIKUM: [uhørligt] DAVID MALAN: Og lad mig gøre det visuelt. Så formoder, det er bogstavet S. PUBLIKUM: Det er én. DAVID MALAN: Det er én. Right? Dette er et array, som betyder, at vi har random access. Og hvis vi tænker på dette som nul og dette som 25, og vi indser, at, åh, her er mit input S, Jeg kan helt sikkert konvertere S, en ASCII-tegn, til et tilsvarende antal mellem nul og 25 og derefter straks sætte det, hvor det hører hjemme. Men selvfølgelig, så snart jeg kommer til anden person, der er navn er A, B eller C til sidst, hvis jeg har brugt den lineær sondering som min løsning, køretiden for indsættelse i værste fald rent faktisk vil udvikle sig til hvad? Og jeg hørte det her korrekt tidligt. PUBLIKUM: [uhørligt] DAVID MALAN: Så det er n faktisk en gang du har et tilstrækkeligt stort datasæt. Så på den ene side, hvis dit array er stor nok og dine data er sparsomme nok, du få denne smukke konstant tid. Men så snart du begynder at få flere og flere elementer, og bare statistisk får du flere mennesker med bogstavet A som deres navn eller bogstavet B, det kunne potentielt udvikle sig til noget mere lineær. Så ikke helt perfekt. Så kunne vi gøre bedre? Nå, hvad var vores løsning før, når vi ønsker at have mere dynamik end noget som et array tilladt? PUBLIKUM: [uhørligt] DAVID MALAN: Hvad gjorde vi præsentere? Ja. Så en sammenkædet liste. Nå, lad os se, hvad en sammenkædet Listen kan gøre for os i stedet. Nå, lad mig foreslå, at vi tegne billedet som følger. Nu er det en anden billede fra et eksempel fra en anden tekst, faktisk, at er faktisk ved hjælp af en vifte af størrelse 31. Og denne forfatter simpelthen besluttede at hash strings ikke er baseret på personens navn, men baseret på deres fødselsdage. Uafhængigt af den måned, de regnede hvis du er født den første i en måned eller den 31. i en måned, forfatteren vil hash baseret på denne værdi, således at sprede navne en smule mere end blot 26 spots kunne give. Og måske er det en smule mere ensartet end at gå med alfabetiske bogstaver, fordi selvfølgelig er der sandsynligvis flere mennesker i verden med navne at starte med A end sikkert nogle andre bogstaver i alfabetet. Så måske det er lidt mere ensartet, antager en ensartet fordeling babyer over en måned. Men, selvfølgelig, det er stadig ufuldkommen. Right? Vi skal have kollisioner. Flere mennesker i denne datastruktur er stadig har den samme fødselsdato mindst du er uanset måned. Men hvad har forfatteren gjort? Tja, det ser ud til vi har en array på den venstre side trukket vertikalt, men det er bare en kunstners gengivelse. Det er ligegyldigt, hvilken retning du tegne et array, er det stadig et array. Hvad er dette en række tilsyneladende? PUBLIKUM: Linked listen. DAVID MALAN: Ja. Det ligner det er en vifte af linkede liste. Så igen, at dette punkt i form anvende disse datastrukturer nu som ingredienser til mere interessante løsninger, du kan absolut tage en grundlæggende som et array, og derefter tage noget mere interessant som en sammenkædet liste og endda kombinere dem til et endnu mere interessant datastruktur. Og ja, dette også ville kaldes en hash tabel, hvorved array er virkelig hash tabellen, men at hash bordet har kæder, så at sige, der kan vokse eller skrumpe baseret på Antallet af elementer, du vil indsætte. Nu derfor, hvad er køretiden nu? Hvis jeg ønsker at indsætte nogen hvis fødselsdag er den 31. oktober hvor er han eller hun gå? Ok. Nederst, hvor der står 31. Og det er perfekt. Det var konstant tid. Men hvad nu, hvis vi finder en anden hvis fødselsdag er, lad os se, Oktober, november, 31. December? Hvor er han eller hun kommer til at gå? Samme ting. To skridt selv. Det er konstant dog er det ikke? Ok. I øjeblikket er det. Men i det generelle tilfælde, jo flere mennesker, vi tilføjer, probalistisk, vil vi for at få flere og flere kollisioner. Nu er det en lille bedre, fordi teknisk nu er mine kæder kunne være i værste fald hvor længe? Hvis jeg indsætter n folk ind i denne mere sofistikeret datastruktur, n mennesker, i værste fald kommer til at være n. Hvorfor? PUBLIKUM: Fordi hvis alle har samme fødselsdag, de kommer til at være en linje. DAVID MALAN: Perfect. Det kan være en smule konstruerede, men virkelig i værste fald hvis alle har samme fødselsdag, givet de indgange, du har, du kommer til at have en massivt lang kæde. Og så kan du kalde det en hash tabellen, men det er virkelig blot en massiv forbundet liste med en hel masse spildplads. Men generelt, hvis vi antager, at mindst fødselsdage er uniform-- og er det sandsynligvis ikke. Jeg gør det op. Men hvis vi antager, for af hensyn til diskussion at de er, så i teorien, hvis dette er den lodrette repræsentation af array, ja så forhåbentlig er du vil få kæder, der er, du kender, omtrent den samme længde, hvor hver af disse repræsenterer en dag i måneden. Nu, hvis der er 31 dage i måneden, det betyder min køretid virkelig er stor O n over 31, som føles bedre end lineær. Men hvad var en af ​​vores forpligtelser et par uger siden, når det kom til at udtrykke køretiden for en algoritme? Bare kun se på den høje orden sigt. Right? 31 er absolut nyttige. Men det er stadig big O n. Men en af ​​de temaer, af problem sæt fem vil være til anerkender, at absolut, asymptotisk, teoretisk denne datastruktur er ikke bedre end bare en massiv linkede liste. Og ja, i værste fald, dette hash tabel kan udvikle sig til det. Men i den virkelige verden, med os mennesker at egne Mac eller pc eller hvad og kører virkelige verden software på virkelige verden data hvilken algoritme vil du foretrække? Den ene, der tager de endelige skridt eller den en, der tager n divideret med 31 trin at finde nogle stykke af data, eller at slå op nogle oplysninger? Jeg mener, absolut de 31 mærker en forskel i den virkelige verden. Det er 31 gange hurtigere. Og vi mennesker er helt sikkert vil forstå, at. Så indser dikotomien der mellem faktisk taler om ting, teoretisk og asymptotisk som definitivt har værdi som vi har set, men i den virkelige verden, hvis du interesserer bare gøre human glad for generelle input, du kan meget vel ønsker at acceptere den kendsgerning, at ja, det er lineær, men det er 31 gange hurtigere end lineær kunne være. Og bedre endnu, vi ikke bare nødt til at gøre noget vilkårlig som en fødselsdato, vi kunne bruge lidt mere tid og dygtighed og tænke over, hvad vi kan gøre, givet en persons navn og måske deres fødselsdato at kombinere de ingredienser til at finde ud af noget der er virkelig mere ensartet og mindre jaggy, så at sige end dette billede i øjeblikket tyder det kunne være. Hvordan kunne vi gennemføre dette i koden? Nå, lad mig foreslå, at vi bare låne nogle syntaks vi har brugt et par gange hidtil. Og jeg har tænkt mig at definere en knude, som igen er en generisk betegnelse for blot nogle container for nogle datastruktur. Jeg har tænkt mig at foreslå, at en streng går derind. Men vi kommer til at begynde at tage dem uddannelse hjul off nu. Ikke mere CS50 bibliotek virkelig, medmindre du ønsker at bruge det til din endelige projekt, hvilket er fint, men nu vil vi trække sig tilbage gardin og siger, det er bare en char stjerne. Så ordet der vil være personens navn pågældende. Og nu har jeg et link her til den næste node således at disse repræsenterer hvert af knudepunkterne i kæden potentielt af en sammenkædet liste. Og nu, hvordan gør jeg erklærer hash tabellen selv? Hvordan kan jeg erklære hele denne struktur? Nå, virkelig, ligesom jeg brugte en pointer til blot det første element i en liste før, ligeledes kan jeg bare sige Jeg skal bare have en masse pointers at gennemføre hele denne hash tabel. Jeg har tænkt mig at have et array kaldet bord til hash tabellen. Det kommer til at være på størrelse kapacitet. Det er, hvor mange elementer kan passe ind i det. Og hver af disse elementer i dette array vil være en node stjerne. Hvorfor? Nå, per dette billede, hvad jeg gennemførelse af hash tabellen som effektivt i starten er bare dette array, som vi har trukket vertikalt, hver af hvis firkanter betegner en pointer. At dem, der har skråstreger gennem dem er lige nul. Og dem, der har pile der går til højre er faktiske henvisninger til faktiske noder, ergo starten på en sammenkædet liste. Så her er så, hvordan vi kan gennemføre en hash tabel, implementerer særskilt chaining. Nu kan vi gøre bedre? Okay jeg lovede sidste gang, vi kunne opnå konstant tid. Og jeg slags gav dig konstant tid her, men så sagde ikke rigtig konstant tid, fordi det er stadig afhængig af den totale antallet af elementer du indtaster ind datastrukturen. Men formoder, at vi gjorde dette. Lad mig gå tilbage til skærmen herovre. Lad mig også projicere det op her, klar skærmen, og formoder jeg gjorde dette. Antag jeg ønskede at indsætte navnet Daven i ind i min datastruktur. Så jeg ønsker at indsætte en streng Daven i datastrukturen. Hvad hvis jeg ikke bruger en hash tabellen, men jeg bruger noget, der er mere trælignende ligesom et stamtræ, hvor du har nogle rod på toppen og derefter knudepunkter og blade at gå nedad og udad. Antag derefter, at jeg vil indsætte Daven s i, hvad der er i øjeblikket en tom liste. Jeg har tænkt mig at gøre følgende: Jeg er vil skabe et knudepunkt i denne familie trælignende datastruktur, der ser lidt ligesom dette, som hver rektangler har, lad os sige, for nu 26 elementer i det. Og hver af cellerne i dette array går at repræsentere bogstav i et alfabet. Konkret vil jeg behandle dette er A, så B, og C, og D, denne ene her. Så det kommer til at effektivt repræsenterer bogstavet D. Men at indsætte alle Daven s navn, jeg er nødt til at gøre lidt mere. Så jeg først kommer til hash, så at sige. Jeg har tænkt mig at kigge på det første bogstav i Daven s hvilket naturligvis er en D, og jeg har tænkt mig at tildele en knude, der ser ligesom denne-- en stor rektangel big nok til at passe til hele alfabetet. Nu D er færdig. Nu A. D-A-V-E-N er målet. Så nu, hvad jeg har tænkt mig at gøre, er dette. Så snart jeg begyndte D varsel der er ingen pointer der. Det er skrald værdier i øjeblikket, eller jeg kunne initialisere den til null. Men lad mig holde i gang med denne idé om at bygge et træ. Lad mig tildele endnu en af ​​disse noder, der har 26 elementer i det. Og ved du hvad? Hvis dette er bare en knude i hukommelsen som Jeg oprettede med malloc, ved hjælp af en struct som vi snart vil se, Jeg har tænkt mig at gøre denne-- Jeg har tænkt mig at tegne en pil fra de ting, der repræsenterede D ned til denne nye knudepunkt. Og nu, først den næste brev i Daven navn, V-- D-A-V-- Jeg har tænkt mig at gå videre og tegne en anden node som dette, hvorved V elementer her, som vi vil trække for instance-- hovsa. Vi vil ikke trække der. Det kommer til at gå her. Så vi kommer til at anser dette for at være V. Og derefter ned her vi kommer til indeks ned fra V ind i, hvad vi vil overveje E. Og så herfra vil vi gå have en af ​​disse knudepunkter her. Og nu har vi et spørgsmål at besvare. Jeg har brug for en eller anden måde viser, at vi er ved enden af ​​strengen Daven. Så jeg kunne bare lade det null. Men hvad hvis vi har Daven s fulde navn også, som er, som vi har sagt, Davenport? Så hvad nu hvis Daven er faktisk en understreng, et præfiks af en meget længere snor? Vi kan ikke bare permanent siger ingenting kommer at gå der, fordi vi kunne aldrig indsætte et ord ligesom Davenport i denne datastruktur Så hvad vi kunne gøre i stedet er behandle hvert af disse elementer som måske har to elementer inde i dem. Den ene er en pointer, ja, som jeg har gjort. Så hver af disse kasser er ikke blot en celle. Men hvad nu, hvis top en-- bunden ens kommer til at være nul, fordi der er ingen Davenport endnu. Hvad hvis den øverste er nogle særlige værdi? Og det kommer til at være lidt svært at tegne det denne størrelse. Men formoder, det er bare et flueben. Tjek. D-A-V-E-N er en streng i denne datastruktur. I mellemtiden, hvis jeg havde mere plads her, jeg kunne gøre P-O-R-T, og jeg kunne sætte check i knudepunktet der har bogstavet T til allersidst. Så dette er et massivt kompleks udseende datastruktur. Og min håndskrift bestemt ikke hjælpe. Men hvis jeg ønskede at indsætte noget andet, overveje, hvad vi ville gøre. Hvis vi ønskede at sætte David i, vi ville følge den samme logik, D-A-V, men nu vil jeg gerne i den næste element ikke fra E, men fra I til D. Så der vil være flere knuder i træet. Vi kommer til at have opkald malloc mere. Men jeg ønsker ikke at lave en komplet rod af dette billede. Så lad os i stedet se på en der er blevet præ-formuleret som dette med ikke dot, dot, prikker, men blot forkortede arrays. Men hver af knudepunkterne i dette træ op her repræsenterer den samme thing-- et array Ray størrelse 26. Eller hvis vi ønsker at være virkelig ordentlig nu, hvad hvis en persons navn som en apostrof, lad os antager, at hvert knudepunkt har faktisk ligesom 27 indekser i den, ikke bare 26. Så det nu kommer til at være en data struktur, der kaldes en trie-- T-R-I-E. En trie, som er angiveligt historisk set et smart navn til et træ der er optimeret til hentning, hvilket naturligvis, staves med et I-E, så det er trie. Men det er historien om trie. Så en trie er dette træ-lignende data struktur som et stamtræ der i sidste ende opfører sig sådan. Og her er bare endnu et eksempel på en hel masse andre folks navne. Men spørgsmålet er nu ved hånden er det har vi opnået ved at indføre velsagtens en mere kompliceret datastruktur, og en, helt ærligt, der bruger en masse hukommelse. Fordi selvom, i det øjeblik, jeg er kun ved hjælp af D's pointer og A og V og Es og Ns, Jeg spilder en dælen af ​​meget hukommelse. Men hvor jeg tilbringer en ressource, Jeg har tendens til at gøre vinde tilbage en anden. Så hvis jeg bruger mere plads, hvad er sandsynligvis det håb? At jeg bruger mindre hvad? PUBLIKUM: Mindre tid. DAVID MALAN: Time. Nu hvorfor kan det være? Nå, hvad er indsættelsen tid, i form af store O nu af et navn som Daven eller Davenport eller David? Nå, Daven var fem trin. Davenport ville være ni trin, så det ville være et par flere trin. David ville være fem skridt så godt. Så dem er konkrete tal, men mon der er en øvre grænse for længden af ​​en persons navn. Og ja, i det problem sæt af fem specifikation vi kommer til at foreslå at det er noget der er 40-nogle-ulige tegn. Realistisk set ingen har en uendelig lang navn, hvilket vil sige, at længden af ​​en navn eller længden af ​​en streng vi måske har visse tilstand struktur er det nok? Det er konstant. Right? Det kan være en stor konstant ligesom 40 noget, men det er konstant. Og det har ingen afhængighed af hvor mange andre navne er i denne datastruktur. Med andre ord, hvis I ville nu indsætte Colton eller Gabriel eller Rob eller Zamyla eller Alison eller Belinda eller andre navne fra personalet i disse data struktur, er køretiden indsætte andre navne vil være på alle påvirket ved hvor mange andre elementer er i data, der allerede struktur? Det er det ikke. Right? Fordi vi er effektivt ved hjælp af denne multi-lag hashtabel. Og køretiden for nogen af ​​disse operationer afhænger ikke af antallet af elementer, der er i datastrukturen eller som i sidste ende går at være i datastrukturen, men af ​​længden af ​​hvad der specifikt? Strengen er indsat, hvilket gør dette asymptotisk konstant time-- store O i én. Og helt ærligt, bare i den virkelige verden, det betyder indsættelse Daven navn tager ligesom fem trin, eller Davenport ni trin eller David fem trin. Det er temmelig darn små køretider. Og, ja, det er en meget god ting, især når det er ikke afhængig af den totale antallet af elementer i der. Så hvordan kan vi gennemfører dette form for struktur i koden? Det er lidt mere kompleks, men det er stadig blot en anvendelse af grundlæggende byggesten. Jeg har tænkt mig at omdefinere os node på følgende måde: bool kaldet word-- og dette kunne kaldes noget. Men bool repræsenterer hvad jeg tegnede som en markering. Ja. Dette er afslutningen af ​​en streng i denne datastruktur. Og naturligvis knudepunktet stjerne der henviser til børn. Og, ja, ligesom et stamtræ, du ville overveje knudepunkterne der hænger ud af bunden af ​​nogle forælder element til at være børn. Og så børnene kommer til at være en vifte af 27 den 27. ene bare at være for apostrof. Vi kommer til at sortere af særtilfælde det. Så du kan have en vis navne med apostrof. Måske endda bindestreg bør gå derind, men du vil se i p sæt 5 vi kun pleje om bogstaver og apostroffer. Og så hvordan gør du repræsenterer datastrukturen selv? Hvordan du repræsenterer roden af denne trie, så at sige? Nå, bare gerne med en linket liste, du brug for en pointer til det første element. Med en trie du bare har brug for en pointer til roden af ​​denne trie. Og derfra kan du hash din vej ned dybere og dybere til hver andet knudepunkt i strukturen. Så blot med denne dåse vi repræsenterer, at struct. Nu Meanwhile-- Åh, spørgsmål. PUBLIKUM: Hvad er bool ord? DAVID MALAN: Bool ord er netop dette C inkarnation af hvad jeg beskrev i denne ramme, når Jeg begyndte at opdele hver af de array-elementer i to stykker. Den ene er en pointer til den næste node. Den anden skal være noget som et afkrydsningsfelt til at sige ja, der er en Ordet Daven der ender her, fordi vi ikke ønsker, i øjeblikket, Dave. Selvom Dave vil være en legitime ord, han er ikke i trie endnu. Og D er ikke et ord. Og D-A er ikke et ord eller et navn. Så markeringen angiver kun, når du ramt dette knudepunkt er tidligere sti tegn faktisk en streng, som du har indsat. Så det er alle de bool der gør for os. Alle andre spørgsmål om forsøg? Ja. PUBLIKUM: Hvad er overlap? Hvad hvis du har en Dave og en Daven? DAVID MALAN: Perfect. Hvad hvis du har en Dave og en Daven? Så hvis vi indsætter, siger et kaldenavn, for David-- Dave-- D-A-V-E? Dette er faktisk super enkel. Så vi kun kommer til at tage fire trin. D-A-V-E. Og hvad skal jeg gøre, når jeg ramte det fjerde node? Bare for at kontrollere. Vi er allerede gode til at gå. Udført. Fire trin. Konstant tid asymptotisk. Og nu har vi angivet, at både Dave og Daven er strenge i strukturen. Så ikke et problem. Og bemærk, hvordan tilstedeværelsen af Daven ikke gøre det tage noget mere tid eller mindre tid for Dave og vice versa. Så hvad andet kan vi nu gøre? Vi har brugt denne metafor før bakker repræsenterer noget. Men det viser sig, at en stablen af ​​bakker er faktisk demonstrative af en anden abstrakt data Motortype- et højere niveau datastruktur at der ved udgangen af ​​dagen er bare som en matrix eller en sammenkædet liste eller noget mere prosaisk. Men det er en mere interessant konceptuelle koncept. En stak, som disse bakker her i Mather, kaldes generelt bare at-- en stak. Og i denne type datastruktur du har to operations-- du har en kaldet fremstød for tilføje noget til stakken, som at sætte en anden bakke tilbage på toppen af ​​stakken. Og derefter pop, hvilket betyder, at du tage den øverste bakke off. Men hvad er nøglen omkring en stak, er, at det har fået denne besynderlige egenskab. Som den spisesal personale er omarrangere bakker til det næste måltid, hvad der kommer til at være sandt om, hvordan de studerende interagere med denne datastruktur? PUBLIKUM: De kommer til at poppe en off. DAVID MALAN: De kommer til at poppe en off, forhåbentlig toppen. Ellers er det bare lidt dum at gå hele vejen til bunden. Right? Datastrukturen ikke rigtig tillade dig at få fat den nederste bakke i det mindste let. Så der er denne besynderlige ejendom til en stak at det sidste element i er vil være den første ud. Og dataloger kalder dette LIFO-- vare ind, først ud. Og det faktisk har interessante anvendelser. Det er ikke nødvendigvis så indlysende, som nogle andre, men det kan faktisk være nyttigt, og det kan faktisk implementeres i et par forskellige måder. Så en, og faktisk, lad mig ikke at dykke ned i det. Lad os gøre det i stedet. Lad os se på en, der er næsten samme idé, men det er lidt mere retfærdig. Right? Hvis du er en af ​​disse fan drenge eller piger, der virkelig kan lide Apples produkter og du vågnede op på 3:00 at line op på nogle butik at få det nyeste iPhone, du kunne have kø som denne. Nu er en kø er meget bevidst navngivet. Det er en linje, fordi der er nogle retfærdighed til det. Right? Det ville suges slags, hvis du har fik der først på Apple Store men du er faktisk det nederste bakke, fordi Apple ansatte derefter pop den sidste person, der faktisk fik i linje. Så stakke og køer, selv om der funktionelt de er slags af same-- det er bare denne samling af ressourcer, som er kommer til at vokse og shrink-- der er denne fairness aspekt til det, i det mindste i den virkelige verden, hvor operationerne du motionerer er fundamentalt forskellige. En stack-- en kø rather-- siges at have to operationer: n kø og d kø. Eller du kan ringe til dem en række ting. Men du blot ønsker at fange det begreb, at man tilføjer og man er i sidste ende at subtrahere. Nu under hætten, både stakken og en kø kan gennemføres hvordan? Vi vil ikke gå ind i koden for det, fordi det højere niveau Ideen er slags mere indlysende. Jeg mener, hvad gør mennesker gør? Hvis jeg er den første person på Apple Opbevar og det er hoveddøren, du ved, jeg har tænkt mig at stå her. Og den næste person kommer til at stå her. Og den næste person kommer til at stå her. Så hvad datastruktur egner sig til en kø? PUBLIKUM: En kø. DAVID MALAN: Tja, en kø. Sure. Hvad ellers? PUBLIKUM: En linkede liste. DAVID MALAN: Et sammenkædet liste, du kunne gennemføre. Og en linket liste er rart, fordi så det kan vokse vilkårligt længe i modsætning at have nogle fast antal af mennesker i butikken. Men måske et fast antal steder er legitim. Fordi hvis de kun har ligesom 20 Iphones på den første dag, måske de kun behøver en vifte af størrelse 20 til at repræsentere den kø, som er kun at sige nu, når vi begynder at tale om disse problemer højere niveau, du kan gennemføre det i en række forskellige måder. Og der er nok bare at gå til være en afvejning i tid og rum eller bare i din egen kode kompleksitet. Hvad med en stak? Tja, en stak, har vi set alt for kunne bare være disse bakker. Og man kunne gennemføre denne et array. Men på et tidspunkt, hvis du bruger et array, hvad der vil ske med bakkerne du forsøger at lægge ned? Ok. Du vil kun være i stand til at gå så højt. Og jeg tror i Mather, de er faktisk forsænket i denne åbning. Så ja, det er næsten ligesom Mather bruger en matrix af fast størrelse, fordi du kun kan passer så mange bakker i, at åbningen i muren ned under folks knæ. Og så der kan være siges at være et array, men vi kunne sikkert gennemføre denne mere generelt med en linket liste. Nå, hvad en anden datastruktur? Lad mig trække op en anden visuel her. Noget som hvordan omkring denne ene her? Hvorfor kan det være nyttigt at have ikke noget så fancy som en trie, som vi så haft disse meget brede knudepunkter, som hver er i en array? Men hvad nu, hvis vi gør noget mere simpelthen, som en gammel skole stamtræ, hver af hvis knudepunkter her blot lagre et nummer. I stedet for et navn eller en efterkommer er bare at lagre et nummer som dette. Nå, den jargon, vi bruger i datastrukturer er begge forsøg og træer, hvor en trie igen, er blot én, hvis knudepunkter er arrays, er stadig, hvad man kunne bruge fra folkeskolen når du har lavet en familie tree-- blade og roden af træet og børn af forælder og søskende deraf. Og vi kan gennemføre et træ, for eksempel så enkelt som dette. Et træ, hvis det som et knudepunkt, en af disse kredse, der har et nummer det kommer ikke til at have en pointer, men to. Og så snart du tilføjer en anden pointer, du kan faktisk nu gøre slags af to-dimensionelle data strukturer i hukommelsen. Ligesom en todimensional array, kan du har form af to-dimensionelle hægtede lister, men dem at følge et mønster hvor der er ingen cykler. Det er virkelig et træ med en bedsteforælder vej op her og derefter nogle forældre og børn, og børnebørn og oldebørn. og så videre. Men hvad er virkelig sirlige om dette også, bare for at drille dig en smule kode med, tilbagekaldelse rekursion fra et stykke tid tilbage, hvorved du skriver en funktion, der kalder sig selv. Dette er en smuk lejlighed at implementere noget ligesom rekursion, fordi overveje dette. Dette er et træ. Og jeg har været lidt anal med hvordan Jeg sætter heltal på gaden. Så meget, at det har en særlig name-- en binær søgning træ. Nu har vi hørt om binær at søge, men kan du arbejde baglæns fra denne ting navn? Hvad er det mønster af, hvordan jeg indsættes heltal i dette træ? Det er ikke vilkårlig. Der er nogle mønster. Ja. PUBLIKUM: Mindre dem til venstre. DAVID MALAN: Ja. Mindre er på venstre. Større virksomheder er på rette. Sådan at en sand erklæring er en forælder er større end dens venstre barn, men mindre end dens højre barn. Og det alene er endda en rekursive verbal definition fordi du kan anvende denne samme logik til hver node og det kun bunde ud, en base tilfældet, hvis du vil, når du rammer en af bladene, så at sige, hvor en orlov har ingen børn yderligere. Nu, hvordan kan du finde nummeret 44? Du ville starte ved roden og sige, hm. 55 er ikke 44 Så gør jeg ønsker at gå ret eller skal jeg ønsker at gå tilbage? Nå, selvfølgelig, du ønsker at gå til venstre. Og så er det bare ligesom telefonen Bogen eksempel i binær søgning mere generelt. Men vi gennemføre den nu lidt mere dynamisk end et array kunne give. Og i virkeligheden, hvis du ønsker at se på den kode, ved første øjekast sikker. Det ligner en hel masse linjer. Men det er smukt enkle. Hvis du ønsker at gennemføre en funktion kaldet søgning hvis formål i livet er at søge efter en værdi ligesom n, et helt tal, og du er gået i en en pointer-- en pointer til knudepunktet af rødder, snarere af det træ, hvorfra du kan få adgang til alt det andet, mærke til, hvor ligefremt du kan gennemføre logikken. Hvis træet er null, selvfølgelig er det ikke der. Lad os bare return false. Right? Hvis du aflevere det ingenting, der er ikke noget der. Else, hvis n er mindre end træ pil n- nu arrow n, husker vi indførte super kort den anden dag, og det betyder bare de-reference pointer og se på det område, der kaldes n. Så betyder det, gå der og se felt, der kaldes n. Så hvis n, den værdi, du er givet, er mindre end værdien i træerne heltal, Hvor vil du hen? Til venstre. Så mærke rekursionen. Jeg returning-- ikke sandt. Ikke falsk. Jeg tilbage uanset svaret er fra et kald til mig selv, der passerer en n igen, hvilket er overflødig men hvad er lidt anderledes nu? Hvordan skal jeg gøre problemet mindre? Jeg passerer ind som den anden argument, ikke roden af ​​træet, men den venstre barn i dette tilfælde. Så jeg passerer i venstre barn. I mellemtiden, hvis n er større end node Jeg er i øjeblikket kigger på, Jeg søger den højre side. Else, hvis træet ikke er nul, og Hvis elementet ikke er til venstre og det er ikke til højre, hvad er vidunderligt tilfældet? Vi har faktisk fundet node i spørgsmål, og så vender vi tilbage sandt. Så vi har lige kradset i overfladen nu nogle af disse datastrukturer. I problem sæt fem du vil udforske disse endnu videre, og du vil blive givet dit design valg af, hvordan man kan gå om dette. Hvad jeg gerne vil slutte på er bare en 30 sekunders teaser af, hvad der venter i næste uge og videre. Som vi begin-- heldigvis du måske tror-- langsomt vores overgang fra en verden af ​​C og lavere implementering niveau detaljer, til en verden, hvor vi kan tage for givet, at en anden har endelig gennemført disse data strukturer for os, og vi vil begynde at forstå virkelige verden betyder, at gennemføre web-baserede programmer, og websites mere generelt og også meget sikkerhed konsekvenser, vi har kun begyndt at ridse overfladen på. Her er hvad der venter os i de kommende dage. [VIDEO PLAYBACK] -Han Kom med et budskab, med en protokol alle hans egen. Han kom til en verden af ​​grusom firewalls, ufølsom routere, og farer langt værre end døden. Han er hurtig. Han er stærk. Han er TCP / IP, og han har fået din adresse. "Warriors den i nettet." [END VIDEO PLAYBACK] DAVID MALAN: Kommer i næste uge. Vi vil se dig derefter. [VIDEO PLAYBACK] -Og Nu, "dybe tanker" af Daven Farnham. -David Starter altid forelæsninger med "All right." Hvorfor ikke: "Her er løsningen til denne uges problem sæt " eller "Vi giver jer alle et A?" [LAUGHING] [END VIDEO PLAYBACK]