SPEAKER 1: All right, så vi er tilbake. Velkommen til CS50. Dette er slutten av uke syv. Så husker at sist gang, begynte vi sett på litt mer sofistikert datastrukturer. Siden frem til nå, alt vi hadde egentlig til rådighet var dette en matrise. Men før vi forkaste matrisen som ikke alle som interessant, som faktisk er det faktisk er, hva er noen av de positive til denne enkle data struktur så langt? Hva er det gode på? Så langt som vi har sett? Hva har du? Ingenting. STUDENT: [uhørlig]. SPEAKER 1: Hva er det? STUDENT: [uhørlig]. SPEAKER 1: Fast størrelse. OK, så hvorfor er fast størrelse bra skjønt? STUDENT: [uhørlig]. SPEAKER 1: OK, så det er effektiv i den forstand at du kan tildele en fast beløp på plass, som forhåpentligvis er nettopp så mye plass som du vil. Så det kan være absolutt et pluss. Hva er en annen opp side av en matrise? Yeah? STUDENT: [uhørlig]. SPEAKER 1: All the - beklager? STUDENT: [uhørlig]. SPEAKER 1: Alle boksene i minnet eller ved siden av hverandre. Og det er nyttig - hvorfor? Det er helt sant. Men hvordan kan vi utnytte at sannheten? STUDENT: [uhørlig]. SPEAKER 1: Akkurat, kan vi holde styr på der alt er bare ved å vite en adresse, nemlig den adresse i første byte av at mengde minne. Eller i tilfelle av strengen, adressen til den første røye i strengen. Og derfra kan vi finne slutten av strengen. Vi kan finne det andre elementet, den tredje element, og så videre. Og så fancy måte å beskrive at funksjonen er at arrays gi oss random access. Bare ved hjelp av hakeparentes notasjon og et nummer, kan du hoppe til et spesifikt element i matrisen i konstant tid, big O av en, så å si. Men det har vært noen ulemper. Hva en rekke ikke veldig lett? Hva er det ikke god på? STUDENT: [uhørlig]. SPEAKER 1: Hva er det? STUDENT: [uhørlig]. SPEAKER 1: Utvidelse i størrelse. Så ulempene i matrisen er nettopp det motsatte av hva oppsider er. Så en av ulempene er at det er en fast størrelse. Så du kan egentlig ikke vokse det. Du kan omdisponere en større del av minnet, og deretter flytte de gamle elementene inn det nye utvalget. Og så fri den gamle array, for eksempel, ved å bruke malloc eller en lignende funksjon kalt realloc, som reallocates minne. Realloc, som en side, prøver å gi deg minne som er ved siden av rekken som du allerede har. Men det kan flytte ting rundt helt. Men kort sagt, det er dyrt, ikke sant? Fordi hvis du har en mengde minne om denne størrelsen, men du virkelig vil ha en av denne størrelsen, og du ønsker å bevare de opprinnelige elementene, må du omtrent en lineær tid kopieringen som må skje fra gamle array til nye. Og virkeligheten ber operativsystemet systemet igjen og igjen og igjen for store biter av minne kan starte til å koste deg litt tid også. Så det er både en velsignelse og en forbannelse i skjule det faktum at disse arrays er av fast størrelse. Men hvis vi innfører i stedet noe som dette, som vi kalte en koblet liste, får vi noen oppsider og noen downsides her også. Så en lenket liste er bare en data Strukturen består av C structs i dette tilfelle, hvor en struct, husker, er bare en beholder for en eller flere bestemte typer variabler. I dette tilfellet, hva gjør de datatyper synes å være inne i struct som siste gang vi kalte en node? Hver av disse rektangler er en node. Og hver av de mindre rektanglene innsiden av det er en datatype. Hvilke typer vi si de var på mandag? Yeah? STUDENT: [uhørlig]. SPEAKER 1: En variabel og en peker, eller mer spesifikt, en int, for n, og en peker på bunnen. Begge disse tilfeldigvis er 32 biter, ved minst på en datamaskin som dette CS50 Apparatet, og slik at de er trukket like i størrelse. Så hva bruker pekeren selv for tilsynelatende? Hvorfor legge denne pilen nå når arrays var så fint og rent og enkelt? Hva er pekeren gjør for oss i hver av disse nodene? STUDENT: [uhørlig]. SPEAKER 1: Nettopp. Det forteller deg hvor den neste er. Så jeg liksom bruke analogien ved hjelp av en tråd å sortere av træ disse nodene sammen. Og det er akkurat det vi gjør med pekere fordi hver av disse biter av hukommelsen kan eller ikke kan være sammenhengende, rygg mot rygg mot rygg innsiden av RAM, fordi hver gang du kalle malloc sier, gi meg nok byte for en ny node, kan det være her eller det kan være her. Det kan være her. Det kan være her. Du vet bare ikke. Men ved hjelp av pekere i adressene til disse nodene, kan du sy dem sammen på en måte som ser visuelt som en liste, selv om disse tingene er spredt ut i hele ett eller dine to eller dine fire gigabyte RAM innsiden av din egen datamaskin. Så nedsiden, da, en lenket liste er hva? Hva er en pris vi er tilsynelatende å betale? STUDENT: [uhørlig]. SPEAKER 1: Mer plass, ikke sant? Vi har, i dette tilfellet, doblet mengde plass fordi vi har gått fra 32 bits for hver node, for hver int, så nå 64 bits fordi vi må holde rundt en peker også. Du får mer effektivitet hvis struct er større enn dette enkle ting. Hvis du faktisk har en student inne av disse er et par strenger for navn og hus, kanskje et ID-nummer, kanskje noen andre felt helt. Så hvis du har en stor nok struct, så kanskje kostnadene for pekeren er ikke en så big deal. Dette er en bit av et hjørne i tilfelle at vi lagre en så enkel primitiv innsiden av lenket liste. Men her er den samme. Du definitivt bruke mer minne, men du får fleksibilitet. Fordi nå hvis jeg ønsker å legge til et element i begynnelsen av denne listen, Jeg har til å tildele en ny node. Og jeg må bare oppdatere dem piler eller annen måte ved å bare flytte noen tips rundt. Hvis jeg ønsker å sette noe inn i midten av listen, trenger jeg ikke å presse alle til side som vi gjorde i ukers fortiden med våre frivillige som representerte en matrise. Jeg kan bare tildele en ny node og så bare peke pilene i forskjellige retninger fordi det gjør ikke må forbli i selve minne en sann linje som jeg har tegnet det her på skjermen. Og så til slutt, hvis du vil sette inn noe ved slutten av listen, er det enda enklere. Dette er liksom vilkårlig notasjon, men 34 er pekeren, ta en gjetning. Hva er verdien av sin pekeren mest sannsynlig trukket liksom som en gammel skole antenne der? STUDENT: [uhørlig]. SPEAKER 1: Det er sannsynligvis null. Og ja det er en forfatters representasjon av null. Og det er null fordi du absolutt behov for å vite hvor enden av en koblet listen er, så du holder følgende og følge og følge disse pilene til noen søppel verdi. Så null vil markere at det er ingen flere noder til høyre for tallet 34, i dette tilfellet. Så vi foreslår at vi kan implementere denne noden i koden. Og vi har sett denne typen av syntaksen før. Typedef definerer bare en ny type for oss, gir oss et synonym som streng var for røye *. I dette tilfellet, det kommer til å gi oss korte notasjonen slik at struct node kan i stedet bare skrives som node, som er mye renere. Det er mye mindre detaljert. Innsiden av en node er tilsynelatende en int kalt n, og deretter en struct node * som betyr nøyaktig hva vi ønsket pilene til å bety, en peker til en annen node av nøyaktig samme datatype. Og jeg foreslår at vi kunne gjennomføre en Søkefunksjonen som dette, som på første øyekast kan virke litt komplisert. Men la oss se det i sammenheng. La meg gå over til apparatet her. La meg åpne opp en fil som heter liste null dot h. Og som bare inneholder definisjonen vi bare så en stund siden for disse dataene typen kalles en node. Så vi har satt det inn i en prikk h-fil. Og som en side, selv om dette program som du er i ferd med å se er ikke så komplisert, det er faktisk konvensjonen når du skriver et program for å sette ting som datatyper, for å trekke konstanter noen ganger, inne i ditt header-fil og ikke nødvendigvis i C-fil, sikkert når programmer får større og større, slik at du vet hvor du skal lete både for dokumentasjon i noen tilfeller, eller for grunnleggende som dette, de definisjon av noen type. Hvis jeg nå åpner opp liste null dot c, merke noen ting. Den inneholder noen header-filer, de fleste som vi har sett før. Det inkluderer en egen header-fil. Og som en side, hvorfor det er dobbelt sitater her, i motsetning til vinkelen brakettene på linjen som Jeg har merket det? STUDENT: [uhørlig]. SPEAKER 1: Ja, så det er en lokal fil. Så hvis det er en lokal fil på din egen her på linje 15, for eksempel, bruker du de doble anførselstegn i stedet av de vinklede braketter. Nå er dette ganske interessant. Legg merke til at jeg har erklært en global variabel i dette programmet på linje 18 ringte først, er ideen er dette kommer til å være en peker til den første node i min lenket liste, og jeg har initialisert det til null, fordi jeg har ikke tildelt noen faktiske noder ennå. Så dette representerer, billedlig, hva vi så et øyeblikk siden i bildet som at pekeren på langt venstre side. Så akkurat nå, som peker ikke har en pil. Det er i stedet bare null. Men det viser hva som vil være den adressen til den første faktiske node i denne listen. Så jeg har implementert det er en global fordi, som du ser, alt dette Programmet i livet er å implementere en lenket liste for meg. Nå har jeg fått noen prototyper her. Jeg bestemte meg for å implementere funksjoner som sletting, innsetting, søking og traversering - den siste bare å være spasertur over liste, skrive ut dens elementer. Og nå her er min viktigste rutine. Og vi vil ikke bruke for mye tid på disse siden dette er liksom, forhåpentligvis gammelt hat nå. Jeg kommer til å gjøre følgende, mens brukeren samarbeider. Så en, kommer jeg til å skrive ut ut denne menyen. Og jeg har formatert den som en ren, så jeg kunne. Hvis brukeren skriver i ett, betyr det at de ønsker å slette noe. Hvis brukeren skriver i to, det betyr de ønsker å sette inn noe. Og så videre. Jeg skal da be deretter for en kommando. Og så jeg kommer til å bruke GetInt. Så dette er en veldig enkel menuing grensesnitt der du bare trenger å skrive et nummer til en kartlegging av disse kommandoene. Og nå har jeg en fin clean switch uttalelse som kommer til å slå på hva brukeren har skrevet i. Og hvis de skrev en, vil jeg ringe slette og bryte. Hvis de har skrevet to, vil jeg ringe inn og bryte. Og nå merker jeg har satt hver av disse på samme linje. Dette er bare en stilistisk avgjørelse. Vanligvis vi har sett noe som dette. Men jeg bare bestemte meg, ærlig, mitt program så mer lesbar fordi det var bare fire saker til bare liste det slik. Helt legitim bruk av stilen. Og jeg kommer til å gjøre dette så lenge Brukeren har ikke skrevet null, som jeg besluttet vil bety at de ønsker å slutte. Så nå merke til hva jeg er kommer til å gjøre her. Jeg kommer til å frigjøre listen tilsynelatende. Men mer om det i løpet av et øyeblikk. La oss først kjøre dette programmet. Så la meg gjøre en større terminal vindu, dot slash liste 0. Jeg kommer til å gå videre og sette inn med to typing, et tall som 50, og nå du vil se listen er nå 50. Og teksten min bare rullet opp litt. Så nå merke listen inneholder nummer 50. La oss gjøre en annen innsats ved å ta to. La oss skrive inn nummeret som en. Listen er nå en, etterfulgt av 50. Så dette er bare en tekstlig representasjon av listen. Og la oss sette inn en flere antall som tallet 42, som er forhåpentligvis kommer til å ende opp i midten, fordi dette programmet i spesielle former det elementer som det setter dem. Så der har vi det. Super enkelt program som kunne absolutt ha brukt en matrise, men jeg måtte bruke en lenket liste bare så jeg kan dynamisk vokse og krympe det. Så la oss ta en titt for søk, hvis jeg kjøre kommandoen tre, jeg ønsker å søke for, si, nummer 43. Og ingenting ble tydeligvis funnet, fordi jeg fikk tilbake noe svar. Så la oss gjøre dette igjen. Søke. La oss søke for 50, eller snarere søke henholdsvis 42, som har en fin lite subtil betydning. Og jeg fant meningen med livet der. Number 42, hvis du ikke vet referansen, Google det. OK. Så hva har dette programmet gjort for meg? Det er bare tillatt meg å sette dermed langt og søk etter elementer. La oss spole fremover, da, for å den funksjonen vi kikket på på mandag som en teaser. Så denne funksjonen, hevder jeg, søker etter et element i listen ved første en, spørre brukeren og deretter ringer GetInt å få en faktisk int du vil søke etter. Deretter merke til dette. Jeg kommer til å lage en midlertidig variabel på linje 188 som heter spisser - PTR - kunne ha kalt det noe. Og det er en peker til en node fordi jeg sa node * der. Og jeg klargjør den til å være lik først, slik at jeg effektivt har min finger, så å si, på den meget første element av listen. Så hvis min høyre hånd her er PTR jeg er peker på det samme som første peker på. Så nå tilbake i kode, hva som skjer videre - dette er en vanlig paradigme ved gjentakelse over en struktur som en lenket liste. Jeg kommer til å gjøre følgende mens pekeren er ikke lik null Så mens min finger peker ikke på noen null verdi, hvis Pekerpilen n er lik n. Vi vil merke først at n er hva brukeren har skrevet i per GetInts ringe her. Og Pekerpilen n betyr det? Vel, hvis vi går tilbake til bildet her, hvis jeg har en finger peker på at første noden som inneholder ni, pil betyr i hovedsak gå til det node og ta tak i verdien på plasseringen n, I dette tilfellet kalles datafeltet n. Som en side - og vi så denne et par uker siden, da noen spurte - denne syntaksen er nytt, men det gjør ikke gi oss krefter som vi ikke allerede har. Hva var dette uttrykket tilsvarer å bruke dot notasjon og stjerne et par uker siden da vi skrelles tilbake dette laget litt for tidlig? STUDENT: [uhørlig]. SPEAKER 1: Akkurat, var det stjerne, og da var det stjerners dot n, med parentes her, som ser, ærlig, tror jeg mye mer kryptisk å lese. Men stjerners pekeren, som alltid, betyr gå dit. Og når du er der, hvilke data Feltet vil du få tilgang til? Vel du bruker dot notasjon for å få tilgang en structs data-feltet, og jeg ønsker spesielt n. Ærlig, vil jeg hevde dette er bare vanskeligere å lese. Det er vanskeligere å huske hvor trenger parentesene går, jo stjerners og alt det. Så verden vedtatt noen syntaktisk sukker, så å si. Bare en sexy måte å si: Dette er tilsvarende, og kanskje mer intuitivt. Hvis pekeren er faktisk en pekeren, arrow notasjon del gå dit og finne feltet i dette tilfelle kalles n. Så hvis jeg finner den, legge merke til hva jeg gjør. Jeg ganske enkelt skrive ut, fant jeg prosent i, plugge i verdien for den int. Jeg kaller sove i ett sekund bare for å kind av pause ting på skjermen for å gi brukeren en annen for å absorbere hva skjedde. Og da jeg bryte. Ellers hva gjør jeg? Jeg oppdaterer pekeren til lik Pekerpilen neste. Så bare for å være klar, betyr dette gå der, ved hjelp av min gamle skolen notasjon. Så dette betyr bare å gå til uansett du peker på, som i svært første tilfellet er jeg peker på struct med ni i den. Så jeg har gått der. Og så dot notasjon betyr, få verdien på neste. Men verdien, selv om den er trukket som en smal, er bare et tall. Det er en numerisk adresse. Så man denne linjen med kode, enten skrevet som dette, jo mer kryptisk måte, eller som dette, de litt mer intuitiv måte, betyr bare flytte hånden min fra den første noden til den neste, og deretter den neste, og deretter neste, og så videre. Så vi vil ikke dvele ved den andre implementeringer av sette inn og slette og traversering, de første to av som er ganske involvert. Og jeg tror det er ganske lett å få tapt når du gjør det verbalt. Men hva vi kan gjøre her er prøve for å bestemme hvordan best å gjøre dette visuelt. Fordi jeg ville foreslå at hvis vi vil sette inn elementer i dette eksisterende liste, som har fem elementer - 9, 17, 22, 26, og 33 - hvis jeg skulle gjennomføre dette i kode, jeg trenger å vurdere hvordan du skal gå om du gjør dette. Og jeg vil foreslå å ta små steg der, i dette tilfellet jeg mener, hva er de mulige scenarier som vi kan støte på generelt? Ved implementering av innsatsen for en koblet listen, så skjer dette bare å være en spesifikt eksempel på størrelse fem. Vel, hvis du vil sette inn et tall, liker si nummer én, og opprettholde sortert rekkefølge, der åpenbart gjør nummer én må gå i denne konkrete eksempel? Som i begynnelsen. Men det som er interessant er det at Hvis du ønsker å sette et inn i dette liste, må det spesielle pekeren å bli oppdatert tilsynelatende? Først. Så jeg vil hevde at dette er den første saken at vi kanskje vil vurdere, en scenario som involverer innsetting på begynnelsen av listen. La oss plukke ut kanskje en så enkel eller lettere fall relativt sett. Anta ønsker jeg å sette inn nummer 35 i sortert rekkefølge. Det hører selvsagt der borte. Så hva pekeren åpenbart kommer til å må oppdateres i det scenarioet? 34 er pekeren blir ikke null men adressen til struct inneholder nummer 35. Så det er tilfelle to. Så allerede, jeg er liksom kvantisering hvor mye arbeid jeg må gjøre her. Og til slutt, er det opplagte midt saken faktisk, i midten, hvis jeg vil sette inn noe sånt som 23 si, som går mellom 23 til og 26, men nå ting blir litt mer involvert fordi det pekere må endres? Så 22 må åpenbart må endres fordi han ikke kan vise til 26 lenger. Han trenger å peke på den nye noden som Jeg må fordele ved å ringe malloc eller noe tilsvarende. Men så må jeg også at ny node, 23 i dette tilfellet, å ha sin pekeren peker på hvem? 26. Og det kommer til å bli en rekkefølgen av operasjoner her. For hvis jeg gjør dette tåpelig, og jeg for eksempel start ved begynnelsen av listen, og målet mitt er å sette inn 23. Og jeg sjekke, hører det her, nær ni? Nei. Hører det her, ved siden av 17? Nei. Betyr det hører hjemme her ved siden av 22? Ja. Nå hvis jeg er tåpelig her, og ikke tenker dette gjennom, kanskje jeg tildele min nye node for 23. Jeg kan oppdatere pekeren fra noden som kalles 22, peker det ved den nye noden. Og hva må jeg oppdatere den nye nodens pekeren å være? STUDENT: [uhørlig]. SPEAKER 1: Nettopp. Peker på 26.. Men faen om jeg ikke allerede oppdaterer 22 er pekeren å peke på denne fyren, og nå har jeg foreldreløse, resten av listen, så å si. Så rekkefølgen av operasjoner her kommer til å være viktig. For å gjøre dette kan jeg stjele, si, seks frivillige. Og la oss se om vi ikke kan gjøre dette visuelt i stedet for kode-messig. Og vi har noen herlige stresset baller for deg i dag. OK, hva med en, to, i tilbake - på slutten der. tre, fire, begge to gutta på slutten. Og fem, seks. Jada. Fem og seks. Greit og vi vil komme til dere neste gang. Greit, kom igjen opp. Greit, siden du er her oppe først, ønsker du å være en klønete i Google Glass her? Ok, så, OK, Glass, spille inn en video. OK, du er god til å gå. Ok, så hvis dere kan komme over her har jeg forberedt på forhånd noen tall. Greit, kom på over her. Og hvorfor ikke du går litt videre på den måten. Og la oss se, hva heter du, med Google Glass? STUDENT: Ben. SPEAKER 1: Ben? OK, Ben, vil du være den første, bokstavelig talt. Så vi kommer til å sende deg til slutten av den scene. Greit, og navnet ditt? STUDENT: Jason. SPEAKER 1: Jason, OK du vil bli nummer ni. Så hvis du ønsker å følge Ben på den måten. STUDENT: Jill. SPEAKER 1: Jill, du kommer til å være 17, som hvis jeg hadde gjort dette mer intelligent, ville jeg ha startet i den andre enden. Du går den veien. 22. Og du er? STUDENT: Mary. SPEAKER 1: Mary, vil du være 22. Og navnet ditt er? STUDENT: Chris. SPEAKER 1: Chris, vil du være 26. Og så til slutt. STUDENT: Diana. SPEAKER 1: Diana, vil du være 34. Så du kommer på over her. All right, så perfekt sortert bestille allerede. Og la oss gå videre og gjøre dette slik at vi virkelig kan - Ben du er bare slags jakt ut i intet der. OK, så la oss gå videre og skildre dette bruker armene, mye som jeg var, akkurat, hva som skjer. Så gå videre og gi dere en fot eller to mellom dere. Og gå videre og peker med den ene hånden til hvem du skal peke på basert på dette. Og hvis du er null bare peke rett ned til gulvet. OK, så bra. Så nå har vi en lenket liste, og la meg foreslår at jeg skal spille rollen som PTR, så jeg vil ikke bry bærer dette rundt. Og så - noen dum konvensjonen - du kan kalle dette noe du vil - forgjenger pekeren, Pred spisser - det er bare kallenavnet vi ga i vår eksempelkode til min venstre hånd. Den andre hånden som kommer til å være å holde styr på hvem som er hvem i følge scenarier. Så vel, først vil jeg rykke ut det første eksempel på å sette inn, sier 20, inn i listen. Så jeg kommer til å trenge noen til legemliggjøre nummer 20 for oss. Så jeg trenger å malloc noen fra publikum. Kom opp. Hva heter du? STUDENT: Brian. SPEAKER 1: Brian, all right, slik at du skal være den noden som inneholder 20. Greit, kom på over her. Og selvsagt, der hører Brian? Så, i midten av - faktisk vent litt. Vi gjør dette ut av drift. Vi gjør dette mye vanskeligere enn den trenger å være først. OK, vi skal til gratis Brian og realloc Brian som fem. OK, så nå ønsker vi å sette inn Brian som fem. Så kom igjen over her ved siden av Ben for bare et øyeblikk. Og du kan antagelig fortelle hvor denne historien går. Men la oss tenke nøye rekkefølgen av operasjoner. Og det er nettopp denne visuelle som kommer til å stille opp med at eksempelkode. Så her har jeg PTR peker innledningsvis ikke på Ben, per se, men uansett hvilken setter han inneholder, som i dette tilfellet er - hva heter du igjen? STUDENT: Jason. 1 SPEAKER: Jason, slik at både Ben og jeg er peker på Jason i dette øyeblikk. Så nå må jeg bestemme, hvor hører Brian? Så det eneste jeg har tilgang til akkurat nå er hans n data element. Så jeg kommer til å sjekke, er Brian mindre enn Jason? Svaret er sant. Så hva må nå skje, i riktig rekkefølge? Jeg trenger å oppdatere hvor mange pekere totalt i denne historien? Hvor min hånd er fremdeles peker på Jason, og hånden din - hvis du vil legg din hånd som, liksom, jeg vet ikke, et spørsmålstegn. OK, bra. Ok, så du har noen få kandidater. Enten Ben eller jeg eller Brian eller Jason eller alle andre, som pekere må endre? Hvor mange totalt? OK, så to. Min pekeren spiller egentlig ingen rolle lenger fordi jeg er bare midlertidig. Så det er disse to gutta, formodentlig, både Ben og Brian. Så la meg foreslå at vi oppdaterer Ben, siden han er først. Det første elementet i denne liste nå kommer til å være Brian. Så Ben punktet Brian. OK, hva nå? Hvem blir pekt på hvem? STUDENT: [uhørlig]. SPEAKER 1: OK så Brian har å peke på Jason. Men har jeg mistet oversikten over at pekeren? Vet jeg hvor Jason er? STUDENT: [uhørlig]. SPEAKER 1: jeg gjør, siden jeg er den midlertidige pekeren. Og antagelig har jeg ikke endret å peke på den nye noden. Så vi kan rett og slett ha Brian point på hvem jeg peker på. Og vi er ferdige. Så fall en, innsetting på begynnelsen av listen. Det var to viktige skritt. One, må vi oppdatere Ben, og deretter vi må også oppdatere Brian. Og så jeg ikke trenger å bry seg traipsing gjennom resten av liste, fordi vi allerede funnet sin plassering, fordi han tilhørte den venstre for det første element. Greit, så ganske grei. Faktisk føles som vi er nesten gjør dette for komplisert. Så la oss nå nappe av enden av listen, og se hvor kompleksiteten starter. Så hvis nå, Alloc jeg fra publikum. Alle som ønsker å spille 55? Greit, jeg så hånden først. Kom opp. Yeah. Hva heter du? STUDENT: [uhørlig]. SPEAKER 1: Habata. OK, kom igjen opp. Du vil være nummer 55 år. Så du, selvfølgelig, tilhører ved enden av listen. Så la oss spille av simulering med meg være PTR for bare et øyeblikk. Så jeg først kommer til å peke på hva Ben peker på. Vi er begge peker nå på Brian. Så 55 er ikke mindre enn fem. Så jeg kommer til å oppdatere meg selv ved peker til Brians neste pekeren, som nå er selvfølgelig Jason. 55 er ikke mindre enn ni, så Jeg kommer til å oppdatere PTR. Jeg kommer til å oppdatere PTR. Jeg kommer til å oppdatere PTR Jeg kommer til å oppdatere PTR. Og jeg kommer til å - hmm, hva er navnet ditt igjen? STUDENT: Diana. SPEAKER 1: Diana peker, selvfølgelig, på null med sin venstre hånd. Så hvor kommer Habata faktisk hører klart? Til venstre her. Så hvordan vet jeg å sette henne her Jeg tror jeg har skrudd opp. Fordi det er PTR kunst dette øyeblikket i tid? Null. Så selv om, visuelt, kan vi selvsagt se alle disse Gutta her på scenen. Jeg har ikke holdt orden på den forrige person i listen. Jeg har ikke en finger peker ut, I dette tilfellet noden nummer 34. Så la oss faktisk starte dette over. Så nå er jeg faktisk trenger en annen lokal variabel. Og dette er hva du vil se i Selve prøven C-kode, der som jeg går, når jeg oppdaterer min høyre hånd til å peke Jason, og dermed forlate Brian bak, jeg bedre begynne å bruke min venstre hånd til oppdatere hvor jeg var, slik at når jeg går gjennom denne listen - mer klønete enn jeg ment nå her visuelt - Jeg kommer til å komme til slutten av listen. Denne hånden er fortsatt null, noe som er ganske ubrukelig, annet enn for å indikere Jeg er tydelig på slutten av listen, men nå i hvert fall jeg ha denne forgjenger pekeren peker her, så nå hva hender og hva pekere trenger å bli oppdatert? Hvis hånd vil du å konfigurere først? STUDENT: [uhørlig]. 1 SPEAKER: OK, så Dianas. Hvor vil du peke Dianas venstre peker på? 55 at, formodentlig slik at vi har satt inn der. Og hvor skal 55 pekeren gå? Down, som representerer null. Og hendene mine, på dette punktet, ikke saken fordi de var bare midlertidige variabler. Så nå er vi ferdige. Så den ekstra kompleksitet der - og det er ikke så vanskelig å implementere, men vi trenger en sekundær variabel å gjøre sikker på at før jeg flytter min høyre hånd, oppdaterer jeg verdien av min venstre hånd, pred pekeren i dette tilfellet, så at jeg har en etterfølgende pekeren å holde styr på hvor jeg var. Nå som en side, hvis du tenker på dette gjennom, føles dette som om det er en Litt irriterende å måtte holde spore av denne venstre hånd. Hva ville en annen løsning på dette problemet har vært? Hvis du fikk til å omstrukturere dataene strukturen vi snakker gjennom akkurat nå? Hvis dette bare slags føles litt irriterende å ha, som, to pekere gå gjennom listen, kan hvem andre har, i en ideell verden, opprettholdes informasjon som vi trenger? Yeah? STUDENT: [uhørlig]. SPEAKER 1: Nettopp. Høyre, så det er faktisk en interessant spiren til en idé. Og denne ideen om en tidligere peker, peker på den forrige element. Hva om jeg bare nedfelt at innsiden av selve listen? Og det kommer til å være vanskelig å visualisere dette uten alt papiret falle ned på gulvet. Men anta at disse gutta brukte både av sine hender til å ha en tidligere pekeren, og en neste peker, og dermed gjennomføre det vi kaller en dobbelt lenket liste. Som ville tillate meg å sortere av spole tilbake, mye lettere uten meg, programmerer, måtte holde spore manuelt - virkelig manuelt - på hvor jeg hadde vært tidligere i listen. Så vi vil ikke gjøre det. Vi vil holde det enkelt fordi det er kommer til å komme til en pris, dobbelt så mye plass for pekere, Hvis du vil ha en ny en. Men det er faktisk en felles datastruktur kjent som en dobbelt lenket liste. La oss gjøre det siste eksempel her og sette disse gutta ut av sin elendighet. Så 20 malloc. Kom opp fra midtgangen der. Ok, hva heter du? STUDENT: [uhørlig]. SPEAKER 1: Sorry? STUDENT: [uhørlig]. SPEAKER 1: Demeron? OK tennes opp. Du skal være 20. Du åpenbart kommer til å tilhøre mellom 17 og 22. Så la meg lære min lekse. Jeg kommer til å starte pekeren peker på Brian. Og jeg kommer til å ha min venstre hånd bare oppdatere til Brian som jeg flytter til Jason, kontroll gjør 20 mindre enn ni? Nei. Er 20 mindre enn 17? Nei. Er 20 mindre enn 22? Ja. Så hva pekere eller hender må endre hvor de peker nå? Så vi kan gjøre 17 peker på 20.. Så det er fint. Hvor ønsker vi å peke pekeren nå? På 22. Og vi vet hvor 22 er, igjen takk til min midlertidige pekeren. Så vi er OK der. Det på grunn av denne mellomlagring Jeg har holdt styr på hvor alle er. Og nå kan du visuelt gå inn der du tilhører, og nå trenger vi en, to, tre, 4, 5, 6, 7, 8, 9 stress baller, og en runde med applaus for disse gutta, hvis vi kunne. Pent gjort. [APPLAUSE] SPEAKER 1: All right. Og du kan holde bitene av papir som minner. All right, så stol på meg det er mye lettere å gå gjennom det med mennesker enn det er med selve koden. Men hva du finner på bare et øyeblikk nå, er det samme - jo takk. Takk - er at du vil finne at de samme dataene struktur, en lenket liste, kan faktisk anvendes som en byggesten for enda mer sofistikerte datastrukturer. Og innse for temaet her er at vi har absolutt innført mer kompleksiteten i gjennomføringen av denne algoritmen. Innsetting, og hvis vi gikk gjennom det, sletting og søking, er litt mer komplisert enn det ble med en matrise. Men vi få litt dynamikk. Vi får en adaptiv datastruktur. Men igjen, vi betaler en pris for å ha noen ytterligere kompleksitet, både implementere det. Og vi gitt opp random access. Og for å være ærlig, det er ikke noe hyggelig rengjøre lysbilde jeg kan gi deg at sier her er hvorfor en lenket liste er bedre enn en matrise. Og la det bli med det. Fordi temaet repeterte nå, selv mer i de kommende ukene, er at det ikke nødvendigvis et korrekt svar. Dette er grunnen til at vi har egen akse av design for oppgavesett. Det vil være svært kontekstavhengig om du vil bruke disse dataene struktur, eller at man, og det vil avhenge av hva som er viktig for deg i form av ressurser og kompleksitet. Men la meg foreslå at de ideelle data struktur, den hellige gral, ville være noe som er konstant tid, uavhengig av hvor mye ting er inni den, ville ikke det være fantastisk hvis en datastruktur returnert svarene i konstant tid. Ja. Dette ordet er i stor ordbok. Eller nei, dette er ikke ordet. Eller noe slikt problem der. Vel la oss se om vi kan ikke minst ta et skritt mot dette. La meg foreslå en ny datastruktur som kan brukes til forskjellige ting, i dette tilfelle kalles en hash tabell. Og så er vi faktisk tilbake til skotter ved en matrise, i dette tilfellet, og noe tilfeldig, jeg har tatt dette hash table som en matrise med en slags todimensjonal matrise - eller rettere sagt den er avbildet her som en to dimensjonal array - men dette er bare en matrise av størrelse 26, slik at hvis vi kaller matrisen, bord brakett null er rektangelet på toppen. Bordbrakett 25 er rektangelet nederst. Og dette er hvordan jeg kunne trekke en data struktur der jeg ønsker å lagre folks navn. Så for eksempel, og jeg vil ikke trekke hele greia her på overhead, hvis jeg hadde denne tabellen, som jeg nå kommer til å kalle en hash bord, og dette er igjen plassering null. Dette her er beliggenheten en, og så videre. Jeg påstår at jeg ønsker å bruke disse dataene struktur, av hensyn til diskusjonen, for å lagre folks navn, Alice og Bob og Charlie og andre slike navn. Så tenk på dette nå som begynnelsen av, sier en ordbok med mange ord. De måtte være navn i vårt eksempel her. Og dette er alt for germane, kanskje, å gjennomføre en stavekontroll, som vi kanskje for problem satt seks. Så hvis vi har en rekke total størrelse 26 slik at dette er den 25. plassering på bunnen, og jeg hevder at Alice er det første ordet i ordlisten av navnene som jeg ønsker å sette inn i RAM, inn i denne datastruktur, hvor er instinkter som forteller deg at Alices Navnet bør gå i denne tabellen? Vi har 26 alternativer. Hvor vi ønsker å sette henne? Vi ønsker henne i braketten null, ikke sant? En for Alice, la oss kalle det null. Og B vil være en, og C vil være to. Så vi kommer til å skrive Alice navn her oppe. Hvis vi deretter sette Bob, hans Navnet vil gå her. Charlie vil gå her. Og så videre ned igjennom dette datastruktur. Dette er en fantastisk datastruktur. Hvorfor? Vel hva er kjøretiden til sette inn et menneskes navn inn i denne datastruktur akkurat nå? Gitt at denne tabellen er implementert, virkelig, som en matrise. Vel det er konstant tid. Det er rekkefølgen på en. Hvorfor? Vel hvordan kan du bestemme hvor Alice tilhører? Du ser på hvilken bokstav i navnet hennes? Den første. Og du kan få det, hvis det er en streng, bare ved å se på streng brakett null. Så zeroth tegnet i strengen. Det er lett. Vi gjorde det i krypto oppdrag uker siden. Og så når du vet at Alice Brevet er hovedstaden A, kan vi trekke off 65 eller formue A selv, som gir oss null. Så nå vet vi at Alice tilhører ved plassering null. Og gitt en peker til disse dataene struktur, av noe slag, hvor lenge varer det tar meg å finne sted null i en matrise? Bare ett skritt, akkurat det er konstant tid på grunn av tilfeldig tilgang vi foreslått var en funksjon av en matrise. Så kort sagt, å finne ut hva indeksen av Alice navn er, som er i dette tilfellet er A, eller la oss bare løse at til null, hvor B er en-og C er to, finne det ut er konstant tid. Jeg må bare se på sitt første brev, finne ut hvor null er en matrise er også konstant tid. Så teknisk sett det er som to skritt nå. Men det er fortsatt konstant. Så vi kaller den store O av en, så har vi satt Alice inn i denne tabellen i konstant tid. Men selvfølgelig, jeg blir naiv her, ikke sant? Hva hvis det er en Aron i klassen? Eller Alicia? Eller noen andre navn som starter med A. Hvor skal vi sette som person, ikke sant? Jeg mener, akkurat nå er det bare tre folk på bordet, så kanskje vi bør sette Aaron på stedet null en to tre. Høyre, kunne jeg sette A her. Men så, hvis vi prøver å sette inn David inn denne listen, betyr hvor David reise? Nå systemet vårt begynner å bryte ned, ikke sant? Fordi nå David havner her hvis Aaron er faktisk her. Og så nå dette hele ideen om å ha en ren datastruktur som gir oss konstant tid innsettinger er ikke lenger konstant tid, fordi jeg må sjekk, oh, damnit, er noen allerede på Alice beliggenhet. La meg undersøke resten av disse dataene struktur, på jakt etter et sted å sette noen som Aaron navn. Og så vil også den starter å ta lineær tid. Dessuten, hvis du nå ønsker å finne den Aaron i dette datastruktur, og du sjekk, og Aaron navn er ikke her. Ideelt sett ville du bare si Arons ikke i datastrukturen. Men hvis du begynner å lage rom for Aaron der det skulle ha vært en D eller en E, du, verste fall må sjekke hele datastruktur, i og da er det tilfaller til noe lineær i størrelsen av bordet. Så all right, jeg skal fikse dette. Problemet her er at jeg hadde 26 elementer i denne tabellen. La meg endre det. Uff da. La meg endre det slik at heller være av størrelse 26 totalt, merker bunnen indeks kommer til å endre til n minus en. Hvis 26 er helt klart for lite for mennesker ' navn, fordi det er tusenvis av navnene i verden, la oss bare gjøre i 100 eller 1000 eller 10000. La oss bare bevilge mye mer plass. Vel som ikke nødvendigvis redusere sannsynligheten for at vi ikke vil ha to folk med navn som starter med A, og så, skulle du prøve å sette en navn på stedet null fortsatt. De er fortsatt kommer til å kollidere, noe som betyr at vi fortsatt trenger en løsning å sette Alice og Aron og Alicia og andre navn som starter med A andre steder. Men hvor mye av et problem er dette? Hva er sannsynligheten for at du har kollisjoner i en data struktur som dette? Vel, la meg - vi vil komme tilbake på det spørsmålet her. Og se på hvordan vi kan løse det først. La meg trekke opp dette forslaget her. Hva vi nettopp beskrev er en algoritme, en heuristisk kalt lineær sondering der, hvis du prøvde å sette inn noe her i disse dataene struktur, som kalles en hash tabell, og det er ikke plass der, du virkelig sondere datastruktur kontroll, er dette tilgjengelig? Dette Tilgjengelig er dette tilgjengelig? Er dette tilgjengelig? Og når det endelig er, setter du den nevne at du opprinnelig ment andre steder på den plasseringen. Men i verste fall, den eneste flekk kan være den aller bunnen av data struktur, helt på slutten av tabellen. Så lineær sondering, i verste fall, tilfaller i en lineær algoritme hvor Aaron, hvis han tilfeldigvis settes inn sist i denne datastruktur, kanskje han kolliderer med denne første plasseringen, men deretter avslutte med uflaks helt på slutten. Så dette er ikke en konstant tid hellige gral for oss. Denne tilnærmingen av å sette inn elementer inn en datastruktur kalt en hash tabell ser ikke ut til å være konstant tid i det minste ikke i det generelle tilfellet. Det kan tilfalle til noe lineær. Så hva om vi løse kollisjoner noe annerledes? Så her er en mer sofistikert tilnærming til hva som fortsatt er kalles en hash table. Og etter hasj, som en side, hva Jeg mener er den indeksen som Jeg refererte til tidligere. Til hasj noe kan være tenkt som et verb. Så hvis du hash Alice er et navn, en hash-funksjon, så å si, skal returnere et tall. I dette tilfelle er null hvis hun hører til null beliggenhet, en hvis hun hører på sted en, og så videre. Så min hash-funksjon så langt har vært super enkelt, bare å se på første bokstaven i noens navn. Men en hash-funksjon tar som innspill noen stykke data, en string, en int, uansett. Og den spytter ut vanligvis et tall. Og at antallet er der at data element hører hjemme i en datastruktur kjent her som en hash table. Så bare intuitivt, er dette en litt annen sammenheng. Dette faktisk henviser til et eksempel involverer bursdager, der det kan være så mange som 31 dager i måneden. Men hva gjorde denne personen bestemmer seg for å gjøre i tilfelle av en kollisjon? Kontekst nå være, ikke en kollisjon mellom navn, men en kollisjon på fødselsdager, hvis to mennesker har samme bursdag på den 2. oktober for eksempel. STUDENT: [uhørlig]. SPEAKER 1: Ja, så her har vi den utnytte av lenkede lister. Så det ser litt annerledes enn vi trakk det tidligere. Men vi ser ut til å ha til en matrise på den venstre side. Det er en indeks, for ingen spesiell grunn. Men det er fortsatt en matrise. Det er en rekke pekere. Og hver av disse elementer, og hver av disse sirklene eller skråstreker - skråstreken representerer null - hver av disse pekere er tilsynelatende peker til hva datastruktur? En lenket liste. Så nå har vi muligheten til å hardt kode i vårt program størrelsen av bordet. I dette tilfellet vet vi at det er aldri mer enn 31 dager i en måned. Så vanskelig koding en verdi som 31 er rimelig i denne sammenheng. I sammenheng med navn, hard koding 26 er ikke urimelig det folks bare navn begynner med, for eksempel, alfabetet involverer A til Z. Vi kan stappe dem alle i at data struktur så lenge, når vi får en kollisjon, kan vi ikke sette navnene her, vi i stedet tenker på disse cellene ikke som strengene selv, men som pekere til, for eksempel, Alice. Og så Alice kan ha en annen pekeren til et annet navn som starter med A. Og Bob faktisk går over her. Og hvis det er et annet navn som starter med B, ender han opp over her. Og slik at hver av delene av denne tabell to, hvis vi utviklet dette til en litt mer smart - come on - hvis vi laget denne litt mer smart, blir nå en adaptiv data struktur, hvor det er ingen hard grense av hvor mange elementer du kan sette inn inn i det fordi hvis du har en kollisjon, er det fint. Bare gå videre og legge den til hva vi så litt siden var kjent som en lenket liste. Vel la oss stoppe opp et lite øyeblikk. Hva er sannsynligheten for en kollisjon i første omgang? Høyre, kanskje jeg å tenke over, kanskje Jeg er over Engineering Dette problemet, fordi du vet hva? Ja, jeg kan komme opp med vilkårlig eksempler av toppen av hodet mitt som Allison og Aron, men i virkeligheten, gitt en jevn fordeling av innganger, som er noen tilfeldige innsettinger inn i en datastruktur, hva er egentlig sannsynligheten for en kollisjon? Vel viser seg, er det faktisk super høy. La meg generalisere dette Problemet er som dette. Så på et rom av n CS50 studenter, hva er sannsynligheten for at minst to studenter i rommet har samme bursdag? Så det er hva. noen hund - 200, 300 mennesker her og flere hundre folk hjemme i dag. Så hvis du ønsker å spørre oss selv hva som er sannsynligheten for to personer i dette rommet som har samme bursdag, vi kan finne ut av dette. Og jeg hevder faktisk det er to personer med samme fødselsdag. For eksempel er det noen som har bursdag i dag? I går? I morgen? All right, så det føles som jeg kommer til å gjøre dette 363 eller så mer ganger for å faktisk finne ut hvis vi har en kollisjon. Eller vi kan bare gjøre dette matematisk snarere enn ordinært gjør dette. Og foreslår følgende. Så jeg foreslår at vi kunne modellere Sannsynligheten for to mennesker som har det samme fødselsdag som sannsynligheten for en minus sannsynligheten for at ingen har samme fødselsdag. Så for å få dette, og dette er bare fancy måte å skrive dette, for første personen i rommet, han eller hun kan ha en hvilken som helst en av de mulige bursdager forutsatt 365 dager i året, med unnskyldninger til personer med februar 29 bursdag. Så den første personen i dette rommet er gratis å ha en rekke bursdager ut av den 365, slik at mulighetene vi vil gjøre at 365 delt på 365, som er en. Den neste personen i rommet, hvis målet er å unngå en kollisjon, kan bare har hans eller hennes bursdag på hvordan mange forskjellige mulige dager? 364. Så det andre leddet i dette uttrykket er hovedsak gjør at regnestykket for oss ved å trekke ut en mulig dag. Og så den neste dag, neste dag, Neste dag ned til det totale antallet av mennesker i rommet. Og hvis vi da vurdere, hva er da sannsynligheten ikke fra alle har unike bursdager, men igjen en minus det, hva vi får er et uttrykk som kan veldig fancifully se slik ut. Men det er mer interessant å se på visuelt. Dette er et diagram der på x-aksen er antall personer i rommet, antall fødselsdager. På y-aksen er sannsynligheten av en kollisjon, to personer har samme fødselsdag. Og takeaway fra denne kurven er at så snart du kommer til å like 40 studenter, er du opp i en 90% sannsynlighet combinatorically av to personer eller mer har samme fødselsdag. Og når du kommer til å like 58 mennesker er det nesten 100% av en sjanse de to personer i rommet skal ha samme fødselsdag, selv om det er 365 eller 366 mulige bøtter, og bare 58 personer i rommet. Bare statistisk du sannsynligvis til å få kollisjoner, som kort fortalt motiverer denne diskusjonen. At selv om vi får fancy her, og begynner å ha disse kjedene, er vi fremdeles nødt til kollisjoner. Så det ber spørsmålet, hva er kostnadene ved å gjøre innsettinger og slettinger inn i en datastruktur som dette? Vel la meg foreslå - og la meg gå tilbake til skjermen over her - hvis vi har n elementer i liste, så hvis vi prøver å sette inn n elementer, og vi har hvor mange totalt bøtter? La oss si 31 totalt bøtter i tilfelle av fødselsdager. Hva er den maksimale lengden på en av disse kjedene potensielt? Hvis det er det altså 31 mulige bursdager i en gitt måned. Og vi er bare klumper alle - faktisk det er en dum eksempel. La oss gjøre 26 i stedet. Så hvis faktisk har folk som har navn starter med A til Z, og dermed gi oss 26 muligheter. Og vi bruker en datastruktur som den vi nettopp så, hvor vi har en rekke pekere, hvorav hver enkelt peker på en lenket liste der første listen er alle med navnet Alice. Den andre listen er alle med navn som starter med A, fra med B, og så videre. Hva den sannsynlige lengden av hvert disse listene hvis vi antar en fin ren fordeling av navnene A til Z på tvers av hele datastrukturen? Det er n mennesker i datastruktur delt på 26, hvis de er pent spredt ut langs hele datastruktur. Slik at lengden av hver av disse kjedene er n delt på 26. Men i store O notasjon, hva er det? Hva er det egentlig? Så det er egentlig bare n, ikke sant? Fordi vi har sagt i det siste, at ugh du deler med 26. Ja, i virkeligheten er det raskere. Men i teorien, det er ikke fundamentalt alt raskere. Slik at vi ikke ser ut til å være så mye nærmere dette hellige gral. Faktisk er dette bare lineær tid. Heck, på dette punktet, hvorfor gjør ikke vi bare bruke en stor lenket liste? Hvorfor kan ikke vi bare bruke en stor array til å lagre navnene alle i rommet? Vel, er det fortsatt noe overbevisende om en hash table? Er det fortsatt noe overbevisende om en datastruktur som ser ut som dette? Dette. STUDENT: [uhørlig]. SPEAKER 1: Høyre, og igjen hvis det er bare en lineær tid algoritme, og en lineær tid datastruktur, hvorfor gjør ikke jeg bare lagre alles navn i en stor matrise, eller i en stor lenket liste? Og slutte å lage CS så mye vanskeligere enn den trenger å være? Hva er overbevisende om dette, selv selv om jeg klødde det ut? STUDENT: [uhørlig]. SPEAKER 1: Innsettinger ikke? Dyrt lenger. Så innsettinger potensielt kunne fortsatt være konstant tid, selv om dataene Strukturen ser ut som dette, en rekke pekere er hver av hvilke peker mot potensielt en lenket liste. Hvordan kan du oppnå konstant tid innsetting av navn? Stikke den i fronten, ikke sant? Hvis vi ofrer et design mål fra tidligere, hvor vi ønsket å holde alles navn, for eksempel, sorteres eller alle av tallene på scenen sortert, anta at vi har en usortert lenket liste. Det koster bare oss ett eller to trinn, som i tilfellet med Ben og Brian tidligere, for å sette inn et element på begynnelsen av listen. Så hvis vi ikke bryr seg om sortering alle av de navn som starter med A eller alle navnene som begynner på B, kan vi likevel oppnå konstant tid innsetting. Nå ser opp Alice eller Bob eller navn mer generelt er fortsatt hva? Det er stor O n delt på 26, i ideell sak der alle er jevnt distribuert, hvor det er så mange As som det er Z, som sannsynligvis urealistisk. Men det er fortsatt lineær. Men her kommer vi tilbake til det punktet av asymptotisk notasjon være teoretisk sant. Men i den virkelige verden, hvis hevder jeg at mitt program kan gjøre noe 26 ganger raskere enn din, hvis program skal du foretrekker å bruke? Yours eller mine, som er 26 ganger raskere? Realistisk, er den personen som 26 ganger raskere, selv om det teoretisk at algoritmene løpe i samme asymptotisk kjøretid. La meg foreslå en annen løsning helt. Og hvis dette ikke blåse ditt sinn, vi er ute av datastrukturer. Så dette er det en trie - slags dumt navn. Det kommer fra uttak, og ordet er stavet trie, t-r-i-e, på grunn av Kurset henting høres ut som trie. Men det er historie av ordet trie. Så en trie er faktisk noen slags tre, og det er også en spiller på det ordet. Og selv om du ikke helt kan se det med denne visualiseringen, er et en trie tre strukturert, som en familie tre med en stamfar på toppen og masse av barnebarn og oldebarn som blader på bunnen. Men hver node i et trie er en matrise. Og det er i en matrise - og la oss oversimplify for et øyeblikk - det er en matrise, i dette tilfellet, av størrelse 26, hvor hver node er igjen en matrise av størrelse 26, hvor zeroth element i det matrise Å representerer, og den siste element i hvert slikt matrise representerer Z. Så jeg foreslår da at disse dataene struktur, kjent som en trie, kan bli brukes også til å lagre ord. Vi så et øyeblikk siden hvor vi kunne lagre ord, eller i dette tilfellet navnene, og vi så tidligere hvordan vi kan lagre numre, men hvis vi fokuserer på navn eller strenger her, legge merke til hva som er interessant. Jeg hevder at navnet Maxwell er innsiden av denne datastruktur. Hvor ser du Maxwell? STUDENT: [uhørlig]. SPEAKER 1: På venstre. Så hva er interessant med disse dataene Strukturen er stedet lagre det streng M-A-X-W-E-L-L skråstrek null, alt contiguously, hva du i stedet gjøre følger. Hvis dette er en trie som datastruktur hver av nodene som er igjen en matrise, og du vil lagre Maxwell, må du først indeks og så root sin node, så å snakke, den øverste node, ved plassering M, til høyre, så omtrent i midten. Og derfra, følger du en pekeren til et barn noder, så å si. Så i ditt tre forstand, du følger den nedover. Og som fører deg til en annen node til venstre der, som er bare en annen array. Og så hvis du ønsker å lagre Maxwell, du finner pekeren som representerer A, er hvor denne her. Så går du til neste node. Og legg merke til - dette er grunnen til at bildets litt villedende - denne noden ser super bittesmå. Men til høyre for denne er Y og Z. Det er bare forfatteren har avkortet den bilde, slik at du faktisk se ting. Ellers er dette bildet ville være enormt stort. Så nå indeksen i sted X, deretter W, så E, deretter L, da L. Så hva er denne nysgjerrigheten? Vel, hvis vi bruker denne typen ny ta om hvordan du lagrer en streng i en datastruktur, du fortsatt trenger å hovedsak krysse av i data struktur som et ord slutter her. Med andre ord, hver av disse nodene en eller annen måte må huske på at vi faktisk fulgt alle disse pekerne og drar litt brød smule på bunnen av dette her for å indikere hvilken M-A-X-W-E-L-L er faktisk i dette datastruktur. Så vi kan gjøre dette på følgende måte. Hver av nodene i bildet vi bare Sagen har en, en rekke størrelse 27. Og det er nå 27, fordi i p satt seks, vi vil faktisk gi deg en apostrof, slik at vi kan ha navn som O'Reilly og andre med apostrofer. Men samme idé. Hvert av disse elementer i array-peker til en struct node, så bare en node. Så dette er veldig minner av vår lenket liste. Og så har jeg en boolsk, som jeg vil ringe ordet, som bare kommer til å være sant hvis et ord slutter på dette node i treet. Det representerer effektivt den lille trekant vi så for et øyeblikk siden. Så hvis et ord slutter på at node i treet, vil det ordet feltet være sant, som er konseptuelt krysse av, eller vi trekker denne trekanten, ja det er et ord her. Så dette er en trie. Og nå er spørsmålet, hva er kjøretiden? Er det stort O av n? Er det noe annet? Vel, hvis du har n navnene på disse dataene struktur, Maxwell blir bare én av dem, hva er kjøretiden til innsetting eller finne Maxwell? Hva er kjøretiden med å sette Maxwell? Hvis det er n andre navn allerede i tabellen? Yeah? STUDENT: [uhørlig]. SPEAKER 1: Ja, det er lengden av navnet, ikke sant? Så M-en-x-w-e-l-l så det føles som dette algoritmen er big O på syv. Nå, selvfølgelig, navnet vil variere i lengde. Kanskje det er et kort navn. Kanskje det er en lengre navn. Men det som er viktig her er at det er et konstant tall. Og kanskje det er egentlig ikke konstant, men gud, hvis realistisk, i en ordbok, er det sannsynligvis noen grense på antallet bokstaver i en personens navn i et bestemt land. Og så kan vi anta at Verdien er en konstant. Jeg vet ikke hva det er. Det er trolig større enn vi tror det er. Fordi det er alltid noen hjørne tilfelle med en gal langt navn. Så la oss kalle det k, men det er fortsatt et konstant formodentlig, fordi hver navn i verden, i hvert fall i en bestemt land, er at lengden eller kortere, slik at den er konstant. Men når vi har sagt noe er stort O av en konstant verdi, hva er det egentlig tilsvarer? Det er egentlig det samme som å si konstant tid. Nå er vi litt juks, ikke sant? Vi er på en måte å utnytte noen teori her å si at vel, er rekkefølgen på k egentlig bare bestille ett, og det er konstant tid. Men det er virkelig. Fordi det her er viktig innsikt at Hvis vi har observert N navnene allerede i denne datastruktur, og vi insert Maxwell, er hvor lang tid det tar oss til Sett Maxwell i det hele tatt berørte av hvor mange andre mennesker er i datastruktur? Synes ikke å være. Hvis jeg hadde en milliard flere elementer i denne trie, og deretter sette Maxwell, er han i det hele tatt berørt? Nei. Og det er i motsetning til noen av dagen data strukturer vi har sett så langt, hvor kjøretiden til algoritmen din er helt uavhengig av hvor mye ting er eller ikke allerede ved at datastrukturen. Og så med dette gir deg er nå en mulighet for p seks sett, som vil igjen innebære å implementere din egen stavekontroll, lesing i 150.000 ord, hvordan best å lagre det er ikke nødvendigvis åpenbar. Og selv om jeg har håpet på å finne den hellige gral, vet jeg ikke hevder at en trie er. Faktisk en hash tabell kan godt vise seg å være mye mer effektiv. Men de er bare - det er bare én av design beslutninger du må gjøre. Men i avsluttende la oss ta 50 eller så sekunder for å ta en titt på hva som ligger videre neste uke og utover vi overgang fra denne kommandolinjen verden hvis C programmer til ting web basert og språk som PHP og JavaScript og selve Internett, protokoller som HTTP, som du har satt tatt for gitt i årevis nå, og skrevet de fleste hver dag, kanskje, eller sett. Og vi begynner å skrelle tilbake lag av hva er internett. Og hva er koden som ligger til grunn for dagens verktøy. Så 50 sekunder av denne teaseren her. Jeg gir deg Warriors of the Net. [VIDEOAVSPILLING] -Han kom med et budskap. Med en protokoll all sin egen. Han kom til en verden av grusom brannmurer, uncaring rutere, og farer langt verre enn døden. Han er rask. Han er sterk. Han er TCPIP. Og han har adressen din. Warriors of Net. [END VIDEOAVSPILLING] SPEAKER 1: Det er hvordan internett skal arbeide med neste uke.