SPEAKER 1: Okay, så vi er tilbage. Velkommen til CS50. Dette er slutningen af ​​uge syv. Så minde om, at sidste gang, vi startede ser på lidt mere sofistikerede datastrukturer. Siden indtil nu, havde vi alle virkelig til vores rådighed var dette et array. Men før vi kassere array som ikke alt det spændende, som ganske rigtigt er det faktisk, hvad er nogle af de plusser denne enkle data struktur hidtil? Hvad er det god til? Så vidt vi har set? Hvad har du? Nothing. STUDENT: [uhørlig]. SPEAKER 1: Hvad er det? STUDENT: [uhørlig]. SPEAKER 1: Fast størrelse. OK, så hvorfor er fast størrelse godt selv? STUDENT: [uhørlig]. SPEAKER 1: OK, så det er effektivt den forstand, at du kan tildele en fast mængde plads, som forhåbentlig er netop så meget rummet som du ønsker. Så der kunne være absolut et plus. Hvad er en anden op side i et array? Ja? STUDENT: [uhørlig]. SPEAKER 1: Alle - undskyld? STUDENT: [uhørlig]. SPEAKER 1: Alle kasserne i hukommelsen eller ved siden af ​​hinanden. Og det er nyttigt - hvorfor? Det er helt rigtigt. Men hvordan kan vi udnytte denne sandhed? STUDENT: [uhørlig]. SPEAKER 1: Præcis, vi kan holde styr på hvor alt er bare ved at vide én adresse, nemlig adresse første byte af denne luns af hukommelse. Eller i tilfælde af strengen, adressen på den første char i denne streng. Og derfra kan vi finde enden af ​​strengen. Vi kan finde det andet element, de tredje element, og så videre. Og så fancy måde at beskrive, at funktion er at arrays giver os random access. Blot ved hjælp af den firkantede beslag notation og et nummer, kan du springe til et specifikt element i array i konstant tid, store O af en, så at sige. Men der har været nogle ulemper. Hvad et array ikke meget nemt? Hvad er det ikke god til? STUDENT: [uhørlig]. SPEAKER 1: Hvad er det? STUDENT: [uhørlig]. SPEAKER 1: Udvidelse i størrelse. Så de ulemper array er præcis det modsatte af, hvad upsides er. Så en af ​​de ulemper er at det er en fast størrelse. Så du kan ikke rigtig dyrke det. Du kan omfordele en større bid af hukommelse, og derefter flytte de gamle elementer i det nye array. Og derefter fri den gamle matrix, for eksempelvis ved hjælp af malloc eller en lignende funktion kaldet realloc, som omfordeler hukommelse. Realloc, som en sidebemærkning, forsøger at give dig hukommelse, der er ved siden af ​​matrix at du allerede har. Men det kan flytte ting omkring helt. Men kort sagt, er det dyrt, right? Fordi hvis du har en luns af hukommelse denne størrelse, men du virkelig vil have en af denne størrelse, og du ønsker at bevare de oprindelige elementer, du har omkring en lineær tid kopieringen der skal ske fra gamle array til nye. Og virkeligheden beder operativsystemet systemet igen og igen og igen for store bidder af hukommelsen kan begynde til at koste dig lidt tid så godt. Så det er både en velsignelse og en forbandelse i skjule den kendsgerning, at disse arrays er af fast størrelse. Men hvis vi indfører i stedet noget som dette, vi som opfordrede en sammenkædet liste, vi får et par upsides og et par ulemper her. Så en linket liste er simpelthen en data struktur af C structs i dette sagen, hvor en struct, tilbagekaldelse, er bare en beholder til en eller flere specifikke typer af variabler. I dette tilfælde gør, hvad de datatyper synes at være inde i struct der sidste gang vi kaldes en knude? Hver af disse rektangler er et knudepunkt. Og hver af de mindre rektangler inde i det er en datatype. Hvilke typer gjorde vi siger de var på mandag? Ja? STUDENT: [uhørlig]. SPEAKER 1: En variabel og en pegepind, eller mere specifikt, en int, for n, og en pointer i bunden. Begge af dem tilfældigvis være 32 bit, på mindst på en computer som denne CS50 Apparat, og så de er trukket lige i størrelse. Så hvad bruger markøren selvom for tilsyneladende? Hvorfor tilføje denne pil nu, hvor arrays var så nice og ren og enkel? Hvad markøren gør for os i hver af disse knudepunkter? STUDENT: [uhørlig]. SPEAKER 1: Præcis. Det fortæller dig, hvor det næste er. Så jeg slags bruger analogien ved hjælp af en tråd for at sortere i tråd disse knudepunkter sammen. Og det er præcis, hvad vi gør med pointere fordi hver af disse bidder af hukommelsen kan eller ikke kan være sammenhængende, tilbage til tilbage til tilbage indersiden af ​​RAM, fordi hver gang du kalder malloc siger, giv mig nok bytes til en ny node, kan det blive være her, eller det kan være her. Det kunne være her. Det kunne være her. Du skal bare ikke kender. Men at bruge pointere i adresserne på disse knudepunkter, kan du sy dem sammen på en måde, der ser visuelt ligesom en liste selv om disse ting er alle spredt ud i hele din en eller dine to eller dine fire gigabyte RAM indersiden af ​​din egen computer. Så negativsiden så med en linket liste er hvad? Hvad er en pris, vi er tilsyneladende betale? STUDENT: [uhørlig]. SPEAKER 1: Mere plads, right? Vi har i dette tilfælde, fordoblet af plads, fordi vi har gået fra 32 bits for hver node, for hver int, så nu 64 bit, fordi vi er nødt til at holde omkring en pointer så godt. Du får mere effektivitet, hvis din struct er større end dette simple ting. Hvis du rent faktisk har en studerende inde hvoraf er et par strenge for navn og hus, måske et id-nummer, måske nogle andre områder helt. Så hvis du har en stor nok struct, så måske prisen på pointer er ikke sådan en big deal. Det er lidt af et hjørne tilfældet i det vi opbevare sådan en simpel primitiv indersiden af ​​linkede liste. Men pointen er den samme. Du absolut bruge mere hukommelse, men du får fleksibilitet. Fordi nu, hvis jeg ønsker at tilføje et element i begyndelsen af ​​denne liste, Jeg er nødt til at afsætte en ny node. Og jeg er nødt til bare opdatere dem pile eller anden måde ved blot at flytte nogle pejlemærker omkring. Hvis jeg ønsker at indsætte noget i midten af ​​listen, behøver jeg ikke at skubbe alle bort, ligesom vi gjorde i ugers fortid med vores frivillige, der repræsenterede et array. Jeg kan bare tildele en ny node og så bare pege pilene i forskellige retninger, fordi det ikke nødt til at forblive i den faktiske hukommelse et sandt linje som jeg har tegnet det her på skærmen. Og så endelig, hvis du ønsker at indsætte noget i slutningen af ​​listen, er det endnu nemmere. Dette er en slags vilkårlig notation, men 34 er pointer, tage et gæt. Hvad er værdien af ​​sin pointer mest sandsynligvis trukket lidt ligesom en gammel skole antenne der? STUDENT: [uhørlig]. SPEAKER 1: Det er nok null. Og faktisk det er en forfatters repræsentation af null. Og det er null, fordi du absolut brug for at vide, hvor enden af ​​en sammenkædet Listen er, lest du holder følgende, og følge og følge disse pile til nogle skrald værdi. Så null vil betyde, at der ikke er nogen flere knuder til højre for nummer 34, i dette tilfælde. Så vi foreslår, at vi kan gennemføre denne node i koden. Og vi har set den slags syntaks før. Typedef bare definerer en ny type for os, giver os et synonym som string var for char *. I dette tilfælde er det kommer til at give os stenografi notation så struct node kan i stedet bare skrives som knude, som er en meget renere. Det er en masse mindre verdslige. Inde i et knudepunkt er tilsyneladende en int kaldet n, og derefter en struct node * hvilket betyder præcis, hvad vi ønskede pilene til at betyde, en pointer til en anden node af nøjagtig samme datatype. Og jeg foreslår, at vi kunne gennemføre en søgefunktionen som dette, som på første øjekast kan virke en lille kompleks. Men lad os se det i sammenhæng. Lad mig gå over til apparatet her. Lad mig åbne en fil kaldet liste nul prik timer. Og at det kun indeholder definitionen vi lige set et øjeblik siden for disse data typen kaldet en knude. Så vi har lagt det ind i en prik h-fil. Og som en sidebemærkning, selv om dette program, du er ved at se, er ikke alle, der kompliceret, det er faktisk konvention, når du skriver et program til sætte ting som datatyper, til at trække konstanter sommetider inde i dit header fil og ikke nødvendigvis i dit C-fil, i hvert fald når din programmer får større og større, således at du ved hvor de skal lede både for dokumentation i nogle tilfælde, eller for basics som denne, de definition af nogle type. Hvis jeg nu åbne liste zero dot c bemærke et par ting. Den indeholder nogle få header-filer, de fleste som vi har set før. Det omfatter sin egen header fil. Og som en sidebemærkning, hvorfor der er dobbelt citater her, i modsætning til den vinkel beslag på den linje, der Jeg har fremhævet der? STUDENT: [uhørlig]. SPEAKER 1: Ja, så det er en lokal fil. Så hvis det er en lokal fil på din egen her på linie 15, for eksempel, du bruger de dobbelte citationstegn i stedet af de vinklede parenteser. Nu er det lidt interessant. Bemærk, at jeg har erklæret en global variabel i dette program på linie 18 kaldes første, Ideen er dette er kommer til at være en pegepind til den første knude i min linkede liste, og jeg har initialiseret det til null, fordi jeg har ikke tildelt nogen egentlig knuder endnu. Så dette repræsenterer billedligt, hvad vi oplevede et øjeblik siden i billedet som at markøren på langt venstre side. Så lige nu er, at pointer ikke har en pil. Det i stedet er bare null. Men det repræsenterer, hvad der vil være den adressen på den første egentlige node i denne liste. Så jeg har implementeret det er en global fordi, som du kan se, alt dette Programmet gør i livet er at gennemføre en linket liste til mig. Nu har jeg fået et par prototyper her. Jeg besluttede at implementere funktioner som deletion, insertion, søgning og traversal - det sidste bare at være gåtur på tværs af liste, trykning af sine elementer. Og nu her er min vigtigste rutine. Og vi vil ikke bruge for meget tid på disse, da dette er slags, forhåbentlig gamle hat nu. Jeg har tænkt mig at gøre følgende, mens brugeren samvirker. Så en, jeg kommer til at udskrive ud denne menu. Og jeg har formateret det som rent som jeg kunne. Hvis brugeren i én, der betyder de ønsker at slette noget. Hvis brugeren i to, der betyder de ønsker at indsætte noget. Og så videre. Jeg har tænkt mig at så spørge derefter i en kommando. Og så jeg har tænkt mig at bruge GetInt. Så dette er en meget simpel menuing interface, hvor du bare nødt til at skrive en række kortlægning til en af disse kommandoer. Og nu har jeg en dejlig ren switch erklæring om, at der kommer til at tænde hvad brugeren skrevet i. Og hvis de har skrevet en, jeg vil kalde slet og bryde. Hvis de har skrevet to, jeg vil ringe indsætte og knække. Og nu varsel jeg har lagt hver af disse på samme linje. Dette er blot en stilistisk beslutning. Typisk har vi set noget som dette. Men jeg har lige besluttet, helt ærligt, mit program så mere læsbar, fordi Det var kun fire sager til bare liste den som dette. Totally legitime brug af stil. Og jeg har tænkt mig at gøre dette, så længe den Brugeren har ikke skrevet nul, hvilket jeg besluttet, vil betyde, at de ønsker at holde op. Så nu mærke til, hvad jeg kommer til at gøre her. Jeg har tænkt mig at befri listen tilsyneladende. Men mere om det om et øjeblik. Lad os først køre dette program. Så lad mig gøre en større terminal vindue, dot skråstreg liste 0. Jeg har tænkt mig at gå videre og indsætte ved skrive to, et tal som 50, og nu vil du se listen er nu 50 år. Og min tekst bare rulles lidt op. Så nu mærke indeholder listen tallet 50. Lad os gøre en anden indsats ved at tage to. Lad os skrive i antallet som én. List er nu en, efterfulgt af 50. Så dette er blot en tekstuel repræsentation af listen. Og lad os indsætte en mere antallet som nummeret 42, som er forhåbentlig kommer til at ende i midten, fordi dette program i bestemte former det elementer som den indsætter dem. Så der har vi det. Super simpelt program, der kunne absolut have brugt en array, men jeg tilfældigvis bruger en sammenkædet liste bare så jeg kan dynamisk vokse og krympe det. Så lad os tage et kig for søgning, hvis jeg køre kommandoen tre, jeg ønsker at søge for, siger, antallet 43.. Og intet var tilsyneladende fundet, fordi jeg fik tilbage ikke noget svar. Så lad os gøre det igen. Søg. Lad os søge efter 50, eller rettere søge for 42, har som en dejlig lidt subtil betydning. Og jeg fandt meningen med livet der. Number 42, hvis du ikke kender referencen, Google det. Ok. Så hvad er der dette program gjort for mig? Det er bare tilladt mig at indsætte dermed langt og søge efter elementer. Lad os hurtigt fremad, så at denne funktion, vi kiggede på på mandag som en teaser. Så denne funktion, hævder jeg, søgninger efter et element i listen ved først en, spørge brugeren, og derefter kalde GetInt at få et virkeligt int at du ønsker at søge efter. Så bemærke dette. Jeg har tænkt mig at oprette en midlertidig variabel i linie 188 kaldet pegepind - PTR - kunne have kaldt det noget. Og det er en pointer til en knude fordi jeg sagde node * der. Og jeg initialiserer det at være lig med først, så jeg faktisk har min finger, så at sige, på den meget første element på listen. Så hvis min højre hånd her er PTR jeg peger på de samme ting, der først peger på. Så nu tilbage i kode, hvad der sker næste - dette er en fælles paradigme når iteration over en struktur som et linkede liste. Jeg har tænkt mig at gøre følgende, mens pointer er ikke lig med null Så mens min finger ikke peger på nogle null værdi, hvis Markørpilen n n lig. Vi vil bemærke det første, at n er, hvad brugeren har indtastet pr GetInts kalder her. Og Markørpilen n betyder hvad? Tja, hvis vi går tilbage til det billede her, hvis jeg har en finger peger på at første knudepunkt indeholder ni, pil væsentligt betyder at gå til, at node og fange den værdi på placeringen n, i dette tilfælde, kaldet datafelt n. Som en sidebemærkning - og vi oplevede det et par uger siden, når nogen spurgte - denne syntaks er nyt, men det gør ikke give os kræfter, som vi ikke allerede har. Hvad var denne sætning svarer til at bruge dot notation og stjerne et par uger siden, da vi skrællede tilbage dette lag lidt tidligt? STUDENT: [uhørlig]. SPEAKER 1: Præcis, det var stjerne, og så det var stjerne dot n, med parenteser her, som ser, helt ærligt, jeg tror en masse mere kryptiske at læse. Men stjerne pointer, som altid, midler gå der. Og når du er der, hvilke data felt vil du få adgang til? Nå du bruge dot notation for at få adgang en structs datafelt, og jeg specifikt ønsker n. Helt ærligt, vil jeg hævde dette er blot sværere at læse. Det er sværere at huske, hvor behøver parenteserne går, stjerne og alt dette. Så verden har vedtaget nogle syntaktisk sukker, så at sige. Bare en sexet måde at sige, svarer det, og måske mere intuitiv. Hvis markøren er faktisk en pointer, at pil notation midler gå der og finde feltet i dette tilfælde kaldet n. Så hvis jeg finder det, mærke, hvad jeg gør. Jeg simpelthen printe ud, jeg fandt procent i, tilslutte værdien for denne int. Jeg kalder sove en andenplads lige at slags af pause ting på skærmen for at give brugeren en anden til at absorbere hvad der lige skete. Og så vil jeg bryde. Ellers hvad gør jeg? Jeg opdatere pointer til lige Markørpilen næste. Så bare for at være klar, det betyder at gå der, ved hjælp af min gamle skole notation. Så det betyder bare at gå til uanset du peger på, hvilket i den meget første tilfælde er jeg peger på struct med ni i den. Så jeg har gået der. Og så dot notation betyder, få værdien ved næste. Men værdien, selvom det er trukket som en smal, er bare et tal. Det er en numerisk adresse. Så dette én linje kode, uanset om skrevet som dette, jo mere kryptiske måde, eller som dette, den lidt mere intuitiv måde, betyder bare flytte min hånd fra den første knude til den næste, og derefter den næste, og derefter næste, og så videre. Så vi vil ikke dvæle ved den anden implementeringer af indsætte og slette og traversal, de to første af som er temmelig involveret. Og jeg tror, ​​det er ganske nemt at få tabt, når gør det verbalt. Men hvad vi kan gøre her er forsøge at bestemme, hvordan bedst at gøre dette visuelt. Fordi jeg vil foreslå, at hvis vi ønsker at indsætte elementer i dette eksisterende liste, som har fem elementer - 9, 17, 22, 26 og 33 - hvis jeg skulle gennemføre dette i kode, jeg har brug for at overveje, hvordan man kan gå om at gøre dette. Og jeg vil foreslå, at tage små skridt hvorved, i dette tilfælde mener jeg, hvad er de mulige scenarier, som vi støde i almindelighed? Ved gennemførelsen af ​​skær til en sammenkædet liste, det bare sker for at være en specifikt eksempel på størrelse fem. Tja, hvis du vil indsætte et tal, gerne sige det nummer et, og opretholdelse sorteret orden, hvor selvfølgelig gør det nummer et behov for at går i denne specifikke eksempel? Ligesom i begyndelsen. Men hvad er interessant er, at Hvis du ønsker at indsætte en ind i dette liste, hvilke særlige pointer brug skal opdateres tilsyneladende? First. Så jeg vil hævde, det er den første sag at vi måske ønsker at overveje en scenarie involverer indsættelse på begyndelsen af ​​listen. Lad os plukker måske en så let eller endda lettere tilfælde, relativt set. Antag jeg ønsker at indsætte nummer 35 i sorteret rækkefølge. Det selvfølgelig hører derovre. Så hvad pointer selvfølgelig vil nødt til at blive opdateret på det scenarie? 34 s pointer bliver ikke null men den adresse struct med tallet 35.. Så det er tilfælde to. Så allerede, jeg er slags kvantisere hvor meget arbejde jeg skal gøre her. Og endelig, den indlysende midterste sag er ja, i midten, hvis jeg ønsker at indsætte noget som siger 23, der går mellem 23 og 26, men nu tingene bliver lidt mere involveret, fordi det pointers skal ændres? Så 22 selvfølgelig skal ændres fordi han ikke kan pege på 26 længere. Han har brug for at pege på den nye node, Jeg bliver nødt til at afsætte ved at ringe malloc eller et tilsvarende. Men da jeg har også brug for, at nye node, 23 i dette tilfælde har til sit pointerflag peger på hvem? 26.. Og der kommer til at være en rækkefølge af operationer her. Fordi hvis jeg gør det tåbeligt, og jeg for eksempel starter i begyndelsen af på listen, og mit mål er at indsætte 23. Og jeg tjekke, hører det her, nær ni? Nej. Er det hører til her, ved siden af ​​17? Nej. Betyder det hører til her siden 22? Ja. Nu, hvis jeg tåbelige her og ikke tænker dette igennem, jeg måske allokere min nye node for 23.. Jeg kunne opdatere markøren fra node kaldet 22, der peger det på den nye knudepunkt. Og hvad skal jeg nødt til at opdatere den nye node pointer at være? STUDENT: [uhørlig]. SPEAKER 1: Præcis. Peger på 26.. Men dammit hvis jeg ikke allerede opdatere 22 s pointer til at pege på denne fyr, og nu har jeg forældreløse, resten af listen, så at sige. Så rækkefølge af operationer her kommer til at være vigtige. For at gøre dette kunne jeg stjæle, sige, seks frivillige. Og lad os se om vi ikke kan gøre dette visuelt i stedet for code-wise. Og vi har nogle dejlige stress bolde til dig i dag. OK, hvad med en, to, i back - på enden der. tre, fire, begge to fyre på enden. Og fem, seks. Sure. Fem og seks. Okay og vi vil komme til jer næste gang. Okay, kom op. Okay, siden du er heroppe første, vil du gerne være den akavet i Google Glass her? Okay, så OK, Glass, optage en video. OK, du er god til at gå. Okay, så hvis du fyre kan komme over Her har jeg forberedt på forhånd nogle numre. Okay, kom herover. Og hvorfor du ikke gå lidt yderligere på den måde. Og lad os se, hvad er dit navn, med Google Glass? STUDENT: Ben. SPEAKER 1: Ben? OK, Ben, vil du være den første, bogstaveligt talt. Så vi vil sende dig til slutningen af ​​scenen. Okay, og dit navn? STUDENT: Jason. SPEAKER 1: Jason, OK vil du være nummer ni. Så hvis du ønsker at følge Ben den måde. STUDENT: Jill. SPEAKER 1: Jill, er du nødt til at være 17, som hvis jeg havde gjort dette mere intelligent, ville jeg have startede i den anden ende. Du går den vej. 22.. Og du er? STUDENT: Mary. SPEAKER 1: Mary, vil du være 22. Og dit navn er? STUDENT: Chris. SPEAKER 1: Chris, vil du være 26. Og så endelig. STUDENT: Diana. SPEAKER 1: Diana, vil du være 34. Så du kom herover. Okay, så perfekt sorteres ordre allerede. Og lad os gå videre og gøre det så vi virkelig kan - Ben du bare slags kigge ud i ingenting der. OK, så lad os gå videre og skildrer dette hjælp arme, ligesom jeg var, præcist, hvad der foregår. Så gå videre og give jer en fod eller to mellem jer. Og gå videre og pege med den ene hånd til hvem du skal pege på baseret på denne. Og hvis du er null blot pege lige ned til gulvet. OK, så godt. Så nu har vi en linket liste, og lad mig foreslå, at jeg vil spille rollen som PTR, så jeg vil ikke genere transporterer det rundt. Og så - nogen dumme konvention - du kan kalde dette noget, du ønsker - forgænger pointer, Gæt pointer - det er bare det kaldenavn gav vi vores prøve kode til min venstre hånd. Dels at gå at være at holde styr på hvem der er hvem i følgende scenarier. Så formoder, først vil jeg plukke off at første eksempel at indsætte, siger 20, på listen. Så jeg har tænkt mig at brug for nogen til legemliggøre nummer 20 for os. Så jeg er nødt til at allokere nogen fra publikum. Kom op. Hvad er dit navn? STUDENT: Brian. SPEAKER 1: Brian, okay, så du skal være knudepunkt indeholdende 20. Okay, kom herover. Og selvfølgelig, hvor betyder Brian tilhører? Så i midten af ​​- faktisk, vent et øjeblik. Vi gør dette ud af orden. Vi gør dette til en meget hårdere end det behøver at være i første omgang. OK, vi kommer til gratis Brian og realloc Brian som fem. OK, så nu vil vi indsætte Brian som fem. Så kom herover ved siden af Ben for bare et øjeblik. Og du kan formentlig fortælle hvor denne historie går. Men lad os tænke grundigt over rækkefølgen af ​​operationer. Og det er netop denne visuelle der kommer til at line op med denne prøve kode. Så her har jeg PTR peger indledningsvis ikke Ben, per se, på, men uanset hvad værdi, han indeholder, som i dette tilfælde er - hvad er dit navn igen? STUDENT: Jason. SPEAKER 1: Jason, så både Ben og jeg er peger på Jason i dette øjeblik. Så nu har jeg til at bestemme, hvor er Brian tilhører? Så det eneste, jeg har adgang til lige nu er hans n data element. Så jeg har tænkt mig at tjekke, er Brian mindre end Jason? Svaret er sandt. Så hvad nu skal ske, i den rigtige rækkefølge? Jeg har brug for at opdatere, hvor mange pointers i alt i denne historie? Hvor min hånd stadig peger på Jason og din hånd - hvis du vil sætte din hånd som, en slags, jeg ikke kender, et spørgsmålstegn. OK, godt. Okay, så du har et par kandidater. Enten Ben eller I eller Brian eller Jason eller alle andre, som pointers nødt til at ændre? Hvor mange i alt? OK, så to. Min pointer er faktisk ligegyldigt længere fordi jeg er bare midlertidig. Så det er disse to fyre, formentlig, både Ben og Brian. Så lad mig foreslå, at vi opdaterer Ben, da han er først. Det første element i denne liste nu kommer til at være Brian. Så Ben punkt Brian. OK, hvad nu? Hvem bliver pegede på hvem? STUDENT: [uhørlig]. SPEAKER 1: OK, så Brian har at pege på Jason. Men jeg har mistet overblikket over, at pointer? Må jeg ved, hvor Jason er? STUDENT: [uhørlig]. SPEAKER 1: Jeg gør, da jeg er den midlertidige markøren. Og formentlig, jeg har ikke ændret sig at pege på den nye knudepunkt. Så vi kan simpelthen nødt Brian point ved hvem jeg peger på. Og vi er færdig. Så tilfælde en, indsættelse på begyndelsen af ​​listen. Der var to vigtige skridt. Én, vi nødt til at opdatere Ben, og derefter vi også nødt til at opdatere Brian. Og så har jeg ikke behøver at bekymre traipsing gennem resten af liste, fordi vi allerede fundet sit placering, fordi han tilhørte venstre af det første element. Okay, så temmelig ligetil. Faktisk føles som om vi er næsten hvilket gør dette for kompliceret. Så lad os nu plukke ud i slutningen af listen, se og hvor kompleksiteten starter. Så hvis nu Alloc I fra publikum. Nogen ønsker at spille 55? Okay, jeg så din hånd først. Kom op. Ja. Hvad er dit navn? STUDENT: [uhørlig]. SPEAKER 1: Habata. OK, kom op. Du vil være nummer 55.. Så du, selvfølgelig, tilhører ved slutningen af ​​listen. Så lad os replay simuleringen med mig være PTR for bare et øjeblik. Så jeg først kommer til at pege på hvad Ben peger på. Vi begge peger nu på Brian. Så 55 er ikke mindre end fem. Så jeg har tænkt mig at opdatere mig selv ved peger på Brians næste pointer, der nu er selvfølgelig Jason. 55 ikke er mindre end ni, så Jeg har tænkt mig at opdatere PTR. Jeg har tænkt mig at opdatere PTR. Jeg har tænkt mig at opdatere PTR Jeg vil opdatere PTR. Og jeg har tænkt mig at - hmm, hvad er dit navn igen? STUDENT: Diana. SPEAKER 1: Diana peger naturligvis på null med sin venstre hånd. Så hvor kommer Habata faktisk hører klart? Til venstre her. Så hvordan kan jeg vide at sætte hende her Jeg tror, ​​jeg har skruet op. For hvad er PTR kunst dette tidspunkt? Null. Så selvom visuelt, kan vi naturligvis se alle disse fyre her på scenen. Jeg har ikke holdt styr på de tidligere person i listen. Jeg har ikke en finger at påpege, i dette tilfælde den node nummer 34. Så lad os faktisk begynder dette over. Så nu jeg faktisk har brug for en anden lokal variabel. Og dette er hvad du vil se i faktiske prøve C-kode, hvor som jeg går, når jeg opdatere min højre hånd til at pege Jason, og dermed forlader Brian bagefter, jeg bedre begynde at bruge min venstre hånd til opdatere, hvor jeg var, så når jeg går gennem denne liste - mere kejtet end jeg bestemt nu her visuelt - Jeg har tænkt mig at komme til slutningen af ​​listen. Denne hånd er stadig null, som er temmelig ubrugelig, andet end at indikere Jeg er helt klart i slutningen af ​​listen, men nu jeg i det mindste har denne forgænger pointer peger her, så nu, hvad hænder og hvilke pejlemærker brug skal opdateres? Hvis hånd vil du have omkonfigurere først? STUDENT: [uhørlig]. SPEAKER 1: OK, så Dianas. Hvor vil du pege Dianas venstre pointer på? Ved 55, formentlig, således at Vi har indsat der. Og hvor skal 55 pointer hen? Ned, der repræsenterer null. Og mine hænder på dette tidspunkt, ikke noget, fordi de var bare midlertidige variabler. Så nu er vi færdig. Så den yderligere kompleksitet der - og det er ikke så svært at gennemføre, men vi har brug for en sekundær variabel at gøre sikker på, at inden jeg flytter min ret hånd, jeg opdatere værdien af ​​min venstre hånd, Gæt pointer i denne sag, så at jeg har en efterfølgende pointer at holde styr på, hvor jeg var. Nu som en sidebemærkning, hvis du tænker dette igennem, det føles som om det er en lidt irriterende at have til at holde styr på denne venstre hånd. Hvad ville en anden løsning til dette problem har været? Hvis du fik at redesigne de data, struktur, vi taler igennem lige nu? Hvis dette lige slags føles lidt irriterende at have, ligesom, to pointers går igennem listen, som kunne ellers have, i en ideel verden, vedligeholdes oplysninger, som vi har brug for? Ja? STUDENT: [uhørlig]. SPEAKER 1: Præcis. Lige så der er faktisk et interessant kim af en idé. Og denne idé om en tidligere pointer, peger på det forrige element. Hvad hvis jeg bare legemliggjort, at inde i selve listen? Og det vil være svært at visualisere dette uden alt papir falder på gulvet. Men formoder, at disse fyre bruges både af deres hænder til at have en tidligere pointer, og et næste pointer, hvorved gennemføre det, vi vil kalde en dobbelt linkede liste. Der ville tillade mig at sortere i spole tilbage, meget lettere uden mig, at programmør, skulle holde spore manuelt - virkelig manuelt - hvor jeg havde været tidligere i listen. Så vi vil ikke gøre det. Vi vil holde det simpelt, fordi det er vil komme til en pris, dobbelt så meget plads til markørerne, hvis du ønsker en anden. Men det er faktisk en fælles datastruktur kendt som en dobbelt linkede liste. Lad os gøre det sidste eksempel her og sætte disse fyre ud af deres elendighed. Så malloc 20.. Kom op fra midtergangen der. Okay, hvad er dit navn? STUDENT: [uhørlig]. SPEAKER 1: Undskyld? STUDENT: [uhørlig]. SPEAKER 1: Demeron? OK kommer på op. Du skal være 20. Du selvfølgelig kommer til at hører mellem 17 og 22.. Så lad mig lære min lektie. Jeg har tænkt mig at starte pointer peger på Brian. Og jeg har tænkt mig at få min venstre hånd kun opdatere til Brian som jeg flytter til Jason, kontrol gør 20 mindre end ni? Nej. Er 20 mindre end 17? Nej. Er 20 mindre end 22? Ja. Så hvad pointers eller hænder nødt til at ændre hvor de peger nu? Så vi kan gøre 17 peger på 20.. Så det er fint. Hvor vil vi pege markøren nu? Ved 22. Og vi ved, hvor 22 er, igen tak til min midlertidige pointer. Så vi er OK der. Så på grund af denne midlertidige opbevaring Jeg har holdt styr på, hvor alle er. Og nu kan du visuelt gå ind, hvor du tilhører, og nu har vi brug 1, 2, 3, 4, 5, 6, 7, 8, 9 stress bolde, og en runde af bifald for disse fyre, hvis vi kunne. Pænt gjort. [Applaus] SPEAKER 1: Okay. Og du kan beholde brikkerne af papir som souvenirs. Okay, så tro mig det er en masse lettere at gå gennem det med mennesker, end det er med konkrete kode. Men hvad du vil finde på bare et øjeblik nu er den samme - oh, tak. Tak - er, at du vil opdage, at de samme data struktur, en linket liste, kan faktisk anvendes som byggesten til endnu mere sofistikerede datastrukturer. Og indse også temaet her er, at Vi har absolut indført mere kompleksitet i gennemførelsen af denne algoritme. Indsættelse, og hvis vi gik igennem det, sletning og søgning, er lidt mere kompliceret, end det var med et array. Men vi få nogle dynamik. Vi får en adaptiv datastruktur. Men igen, vi betaler en pris for at have nogle yderligere kompleksitet, både i gennemførelse. Og vi er givet op random access. Og for at være ærlig, er der ikke nogle nice rent slide jeg kan give dig, at siger her, er, hvorfor en linket liste er bedre end et array. Og lad det blive ved det. Fordi temaet gentager nu, selv så meget mere i de kommende uger, er at der ikke er nødvendigvis et korrekt svar. Det er derfor, vi har den separate akse design for problemet sæt. Det vil være meget kontekstafhængige om du ønsker at bruge disse data struktur eller at en, og det vil afhænger af, hvad der betyder noget for dig i form af ressourcer og kompleksitet. Men lad mig foreslå, at de ideelle data struktur, den hellige gral, ville være noget, der er konstant tid, uanset hvor mange ting er inde i det, ville det ikke være fantastisk, hvis en datastruktur returnerede svar i konstant tid. Ja. Dette ord er i din enorme ordbogen. Eller nej, dette ord er det ikke. Eller sådanne problemer der. Jamen så lad os se om vi ikke kan i det mindste tage et skridt i retning af det. Lad mig foreslå en ny datastruktur, kan bruges til forskellige ting, i dette tilfælde kaldes en hash tabel. Og så er vi faktisk tilbage til skævede på et array, i dette tilfælde, og noget vilkårligt, jeg har tegnet dette hash tabel som en matrix med en slags to-dimensionelle række - eller rettere det er afbildet her som et to dimensionelle array - men det er bare en vifte af størrelse 26, sådan at hvis vi kalde array, bord beslag nul er rektanglet foroven. Tabel beslag 25 er rektanglet nederst. Og det er, hvordan jeg kunne tegne et data struktur, hvor jeg ønsker at gemme folks navne. Så for eksempel, og jeg vil ikke trække hele her på overhead, hvis jeg havde dette array, som jeg nu kommer til at kalde en hash tabel, og dette er igen placering nul. Dette her er placering én, og så videre. Jeg hævder, at jeg ønsker at bruge disse data struktur, af hensyn til diskussionen, til at gemme folks navne, Alice og Bob og Charlie og andre sådanne navne. Så tænk på det nu som begyndelsen af, siger, en ordbog med masser af ord. De tilfældigvis navne i vores eksempel her. Og det er alt for germane, måske, at gennemføre en stavekontrol, som vi måske for problemet sæt seks. Så hvis vi har en bred vifte af total størrelse 26 således at dette er den 25. placering forneden, og jeg hævder, at Alice er det første ord i ordbogen for navne, som jeg ønsker at indsætte i RAM, i denne datastruktur, er hvor instinkter fortæller dig, at Alices navn skal gå i denne array? Vi har 26 valgmuligheder. Hvor vi ønsker at sætte hende? Vi ønsker hende i konsollen nul, right? A for Alice, lad os kalde det nul. Og B vil være en, og C vil være to. Så vi kommer til at skrive Alices navn heroppe. Hvis vi derefter indsætte Bob, hans navn vil gå her. Charlie vil gå her. Og så videre ned gennem dette datastruktur. Dette er en vidunderlig datastruktur. Hvorfor? Nå, hvad er køretiden for indsætte et menneskes navn til dette datastruktur lige nu? Da denne tabel er implementeret, sandhed, som en matrix. Jamen det er konstant tid. Det er rækkefølgen af ​​én. Hvorfor? Jamen hvordan kan du bestemme hvor Alice hører? Du ser på, hvilket bogstav i hendes navn? Den første. Og du kan få der, hvis det er en streng, ved bare at kigge på snor beslag nul. Så nulte tegn i strengen. Det er nemt. Vi gjorde det i krypto overdragelse uger siden. Og når du ved, at Alices bogstav stort A, kan vi fratrække off 65 eller kapitalen A selv, der giver os nul. Så vi ved nu, at Alice tilhører ved placering nul. Og givet en pointer til disse data struktur af en slags, hvor lang det tage mig at finde sted nul i et array? Blot ét skridt, højre Det er konstant tid på grund af den random access vi foreslåede var en funktion i et array. Så kort sagt, regne ud, hvad indekset af Alice navn er, hvilket er i dette tilfælde er A, eller lad os bare løse at til nul, hvor B er en og C er to, regne det ud er konstant tid. Jeg behøver bare at se på hende første bogstav, finde ud af hvor nul er en array er også konstant tid. Så teknisk set, det er som to trin nu. Men det er stadig konstant. Så vi kalder den store O i en, så vi har indsat Alice i denne tabel i konstant tid. Men selvfølgelig, jeg bliver naive her, right? Hvad hvis der er en Aron i klassen? Eller Alicia? Eller andre navne starter med A. Hvor skal vi sætte denne person, right? Jeg mener, lige nu er der kun tre folk på bordet, så måske vi bør sætte Aaron ved placeringen nul en to tre. Right, jeg kunne sætte en her. Men så, hvis vi forsøger at indsætte David ind denne liste, er, hvor David hen? Nu er vores system starter bryde ned, til højre? Fordi nu David ender her Hvis Aaron er faktisk her. Og så nu hele denne idé om at have en rene data struktur, der giver os konstant tid insertioner er ikke længere konstant tid, fordi jeg er nødt til at tjek, åh, damnit, nogen er allerede på Alice placering. Lad mig sonde resten af ​​disse data struktur, på udkig efter et sted at sætte en som Aaron navn. Og så også er begyndt at tage lineær tid. Desuden, hvis du nu ønsker at finde den Aaron i denne datastruktur, og du kontrollere, og Aaron navn er ikke her. Ideelt set ville du bare sige Aarons ikke i datastrukturen. Men hvis du gør begynde at gøre plads til Aaron hvor der skulle have været en D eller E, kan du i værste fald nødt til at kontrollere hele datastruktur, i hvilket tilfælde det overdrages til noget lineær i størrelsen af ​​tabellen. Så okay, jeg løse dette. Problemet her er, at jeg havde 26 elementer i dette array. Lad mig ændre det. Hovsa. Lad mig ændre det, så hellere værende af str. 26 i alt, mærke bunden indeks vil skifte til n minus 1. Hvis 26 er tydeligvis for lille for mennesker ' navne, fordi der er tusindvis af navne i verden, så lad os bare gøre i 100 eller 1.000 eller 10.000. Lad os bare afsætte meget mere plads. Nå, der ikke nødvendigvis falder sandsynligheden for, at vi ikke vil have to folk med navne der starter med A, og så ville du forsøge at sætte en navne på placering nul stille. De er stadig kommer til at kollidere, hvilket betyder, at vi stadig har brug for en løsning til at sætte Alice og Aron og Alicia og andre navne, der starter med A steder. Men hvor meget af et problem er det? Hvad er sandsynligheden for, at du har kollisioner i et data struktur som denne? Nå, lad mig - vi vil komme tilbage på dette spørgsmål her. Og se på, hvordan vi kan løse det først. Lad mig trække op dette forslag her. Det, vi lige har beskrevet er en algoritme, en heuristisk kaldet lineær sondering hvorved hvis du forsøgte at indsætte noget her i disse data struktur, der kaldes en hash tabel, , og der er ikke plads der, du virkelig sonde datastruktur kontrol, er den tilgængelig? Er den tilgængelig er den tilgængelig? Er det til rådighed? Og når det endelig er, kan du indsætte navn, som du oprindeligt beregnet andre steder på det sted. Men i værste fald kun stedet kunne være selve bunden af ​​data struktur, allersidst i array. Så lineær sondering, i værste fald, overdrages til en lineær algoritme hvor Aron hvis han tilfældigvis skal indsættes sidst i denne datastruktur, kan han kollidere med denne første placering, men så ende med uheld til allersidst. Så dette er ikke en konstant tid hellige gral for os. Denne tilgang indsætte elementer i en datastruktur kaldet en hash tabel synes ikke at være konstant tid i det mindste ikke i det generelle tilfælde. Det kan udvikle sig til noget lineært. Så hvad nu hvis vi løser kollisioner noget anderledes? Så her er en mere sofistikeret tilgang til, hvad der er stadig kaldes en hash tabel. Og ved hash, som en sidebemærkning, hvad Jeg mener, er det indeks, Jeg nævnte tidligere. Til hash noget kan være tænkt som et verbum. Så hvis du hash Alice er et navn, en hash-funktion, så at sige, skal returnere et nummer. I dette tilfælde er nul, hvis hun hører hjemme på location nul, en, hvis hun hører hjemme på placering én, og så videre. Så mit hash-funktionen hidtil har været super enkel, kun ser på første bogstav i en eller andens navn. Men en hash-funktion tager input nogle stykke data, en streng, en int, uanset hvad. Og det spytter typisk et tal. Og det tal er, hvor disse data element hører til i en datastruktur kendt her som en hash tabel. Så bare intuitivt, det er en lidt anden sammenhæng. Dette faktisk hentyder til et eksempel involverer fødselsdage, hvor Der kan være så mange som 31 dage i måneden. Men hvad gjorde denne person beslutter at gøre i tilfælde af en kollision? Kontekst nu ved at blive, ikke en kollision mellem navne, men en kollision af fødselsdage, hvis to mennesker har samme fødselsdag den 2. oktober for eksempel. STUDENT: [uhørlig]. SPEAKER 1: Ja, så her har vi Den gearing af hægtede lister. Så det ser lidt anderledes end vi trak det tidligere. Men vi synes at have til en matrix på venstre side. Det er en index, for ingen særlig grund. Men det er stadig et array. Det er en bred vifte af pegepinde. Og hver af disse elementer, og hvert af disse kredse eller skråstreger - skråstregen repræsenterer null - hver af disse pointere tilsyneladende peger på hvilke data struktur? En sammenkædet liste. Så nu har vi mulighed for at hard kode ind i vores program størrelsen af ​​tabellen. I dette tilfælde ved vi, at der er aldrig mere end 31 dage i en måned. Så svært kodning en værdi som 31 rimeligt i denne sammenhæng. I forbindelse med navne, kodning hårdt 26 er ikke urimeligt det folks navne kun starte med, for eksempel, alfabetet involverer A gennem Z. Vi kan proppe dem alle i disse data struktur, så længe, ​​når vi får en kollision, vi ikke sætte navne her vi i stedet tænker på disse celler ikke som strenge selv, men som henvisninger til, for eksempel, Alice. Og så Alice kan have en anden pointer til et andet navn, der starter med A. Og Bob faktisk går herovre. Og hvis der er et andet navn starter med B, ender han herovre. Og så hver af elementerne i dette tabel to, hvis vi designet denne a lidt mere behændigt - kommer på - hvis vi designet denne lidt mere dygtigt, bliver nu en adaptiv data struktur, hvor der er ingen hårde grænse på, hvor mange elementer, du kan indsætte i det, fordi hvis du har en kollision, det er fint. Bare gå videre og tilføje det til hvad vi så lidt siden var kendt som en sammenkædet liste. Jamen så lad os stoppe for bare et øjeblik. Hvad er sandsynligheden for en kollision i første omgang? Right, måske er jeg mere end tænker, måske Jeg er over Engineering Denne problem, fordi du ved, hvad? Ja, jeg kan komme op med vilkårlig eksempler fra toppen af ​​mit hoved som Allison og Aron, men i virkeligheden, en ensartet fordeling af indgange, der er nogle tilfældige indrykninger i en datastruktur, virkelig, hvad er sandsynligheden for en kollision? Nå viser sig, er det faktisk super høj. Lad mig generalisere dette Problemet er som dette. Så i et rum af n CS50 studerende, hvad er sandsynligheden for, at mindst to studerende i rummet har samme fødselsdag? Så der er hvad. et par hund - 200, 300 mennesker her, og flere hundrede mennesker derhjemme i dag. Så hvis du ønsker at spørge os selv, hvad der er sandsynligheden for to personer i dette rum har samme fødselsdag, vi kan finde ud af dette. Og jeg hævder faktisk er der to folk med samme fødselsdag. For eksempel er der nogen har fødselsdag i dag? I går? I morgen? Okay, så det føles som om jeg har tænkt mig nødt til at gøre dette 363 eller så flere gange til faktisk finde ud hvis vi har en kollision. Eller vi kunne bare gøre det matematisk snarere end kedelig at gøre dette. Og foreslå følgende. Så jeg foreslår, at vi kunne modellere sandsynligheden for to personer, der har samme fødselsdag som sandsynligheden for 1 minus sandsynligheden for ingen har den samme fødselsdag. Så for at få det, og det er bare det fancy måde at skrive dette, for første person i rummet, han eller hun kan have en af ​​de mulige fødselsdage antager 365 dage på året, med undskyldninger til personer med i februar 29 års fødselsdag. Så den første person i dette rum er gratis at have et vilkårligt antal fødselsdage ud af de 365 muligheder, således at vi vil gøre, at 365 divideret med 365 der er én. Den næste person i rummet, hvis målet er at undgå en kollision, kan kun har hans eller hendes fødselsdag, hvordan mange forskellige mulige dage? 364. Så den anden valgperiode i dette udtryk er væsentlige at gøre det math for os ved at fratrække en mulig dag. Og derefter den næste dag, den næste dag, næste dag ned til det samlede antal mennesker i lokalet. Og hvis vi så overveje, hvad er så sandsynligheden ikke af alle, der har unikke fødselsdage, men igen 1 minus det, hvad vi får, er et udtryk der kan meget fancifully se sådan ud. Men det er mere interessant at se på visuelt. Dette er et diagram, hvor på x-aksen er antallet af personer i rummet, antallet af fødselsdage. På y-aksen er sandsynligheden af en kollision, mennesker to med samme fødselsdag. Og takeaway fra denne kurve er at så snart du kommer til at lide 40 studerende, er du op på en 90% sandsynlighed combinatorically af to mennesker eller mere har den samme fødselsdag. Og når du kommer til at lide 58 mennesker er det næsten 100% af en chance to mennesker i lokalet skal have den samme fødselsdag, selvom der ikke er 365 eller 366 mulige spande og kun 58 personer i rummet. Bare statistisk du sandsynligvis få kollisioner, som i kort motiverer denne diskussion. At selv om vi får fancy her, og starter med disse kæder, er vi stadig nødt til kollisioner. Så det rejser spørgsmålet, hvad er omkostninger ved at drive indsætninger og sletninger ind i en datastruktur som dette? Jamen så lad mig foreslå - og lad mig gå tilbage til skærmen i løbet af her - hvis vi har n elementer i liste, så hvis vi forsøger at indsætte n elementer, og vi har hvor mange samlede spande? Lad os sige 31 af total spande i tilfælde af fødselsdage. Hvad er den maksimale længde på en af disse kæder potentielt? Hvis der igen er 31 mulige fødselsdage i en given måned. Og vi bare sammenklumpning alle - faktisk det er en dum eksempel. Lad os gøre 26 i stedet. Så hvis faktisk har folk, hvis navne starte med A til Z, og dermed give us 26 muligheder. Og vi bruger en datastruktur som den, vi lige har set, hvor vi har en bred vifte af henvisninger, som hver peger på en sammenkædet liste, hvor første liste er alle med navnet Alice. Den anden liste er alle med navn, der starter med A, startende med B, og så videre. Hvad er den sandsynlige længden af ​​hver af disse lister, hvis vi antager en dejlig ren fordeling af navne A til Z hele datastruktur? Der er n mennesker i datastrukturen divideret med 26, hvis de er pænt spredt ud over hele datastruktur. Så længden af ​​hver af disse kæderne er n divideres med 26.. Men i store O-notation, hvad er det? Hvad er det egentlig? Så det er egentlig bare n, right? Fordi vi har sagt tidligere, at ugh du dividere med 26.. Ja, i virkeligheden er det hurtigere. Men i teorien er det ikke fundamentalt alt det hurtigere. Så vi synes ikke at være så meget tættere på dette hellige gral. I virkeligheden er dette blot lineær tid. Heck, på dette punkt, hvorfor vi ikke bare bruge ét stort linkede liste? Hvorfor vi ikke bare bruge ét stort array til at gemme navnene på alle i lokalet? Nå, er der stadig noget overbevisende om en hash tabel? Er der stadig noget overbevisende om en datastruktur der ligner dette? Dette. STUDENT: [uhørlig]. SPEAKER 1: Right, og igen, hvis det er bare en lineær tid algoritme, og en lineære tid datastruktur, hvorfor jeg ikke bare gemme alles navn i en stor matrix, eller i en stor knyttet liste? Og stoppe med at lave CS så meget hårdere end det behøver at være? Hvad er overbevisende om dette, selv selvom jeg ridset det ud? STUDENT: [uhørlig]. SPEAKER 1: Indsættelser er ikke? Dyrt længere. Så indrykninger potentielt kunne stadig være konstant tid, selvom dine data struktur ligner det, en vifte af pegepinde, er hver især peger på potentielt en sammenkædet liste. Hvordan kunne du opnå konstant tid indsættelse af navne? Stik den i front, right? Hvis vi ofrer et design mål tidligere, hvor vi ønskede at holde alles navn, for eksempel, sorteres, eller alle numrene på scenen sorteret, Antag at vi har en usorteret linkede liste. Det koster kun os et eller to trin, gerne i tilfælde af Ben og Brian tidligere, at indsætte et element på begyndelsen af ​​listen. Så hvis vi er ligeglade om sortering alle De navne, der begynder med A eller alle de navne, der begynder med B, kan vi stadig opnå konstant tid indsættelse. Nu ser op Alice eller Bob eller hvilket som helst navn mere generelt er stadig, hvad? Det er stort O n divideret med 26, i ideelle tilfælde, hvor alle er ens distribueres, hvor der er så mange A'er som der er Zs, hvilket sandsynligvis urealistisk. Men det er stadig lineær. Men her kommer vi tilbage til det punkt af asymptotisk notation bliver teoretisk sandt. Men i den virkelige verden, hvis jeg hævder, at mit program kan gøre noget 26 gange hurtigere end din, hvis programmet vil du foretrækker at bruge? Yours eller mine, som er 26 gange hurtigere? Realistisk set den person, hvis er 26 gange hurtigere, selvom teoretisk vores algoritmer kører i samme asymptotisk køretid. Lad mig foreslå en anden opløsning helt. Og hvis dette ikke blæse dit sind, vi er ude af datastrukturer. Så dette er det en trie - slags dum navn. Den kommer fra søgninger, og ordet er stavet trie, t-r-i-e, fordi kursus hentning lyder som trie. Men det er historien af ordet trie. Så en trie er faktisk en form for træ, og det er også en spiller på det ord. Og selvom du ikke helt kan se det med denne visualisering, er en trie en træ struktureret, ligesom et stamtræ med en forfader foroven og partier af børnebørn og oldebørn som blade på bunden. Men hvert knudepunkt i en trie er en matrix. Og det er i et array - og lad os forsimpler et øjeblik - det er en array, i dette tilfælde, størrelse 26, hvor hver node igen er en vifte af størrelse 26, hvor den nulte element i det matrix repræsenterer A, og den sidste element i hver sådan matrix repræsenterer Z. Så jeg foreslår altså, at disse data struktur, kendt som en trie, kan være anvendes også til at gemme ord. Vi så for et øjeblik siden, hvordan vi kunne gemme ord, eller i dette tilfælde navne, og vi så tidligere, hvordan vi kan gemme telefonnumre, men hvis vi fokuserer på navne eller strygere her mærke til, hvad der er interessant. Jeg hævder, at navnet Maxwell er indersiden af ​​denne datastruktur. Hvor ser du Maxwell? STUDENT: [uhørlig]. SPEAKER 1: På venstre. Så hvad er interessant med disse data struktur er snarere end lagrer streng M-A-X-W-E-L-L omvendt skråstreg nul, alle contiguously, hvad du gør i stedet følger. Hvis dette er en trie ligesom datastruktur, hver af hvis knudepunkter er igen et array, og du ønsker at gemme Maxwell, skal du først indeks og så roden knudepunkt, så tale, den øverste knude, ved placeringen M, til højre, så groft ind mod midten. Og så derfra følger du en pointer til et barn noder, så at sige. Så i stamtræet forstand, du følger det nedad. Og der fører dig til en anden node til venstre er der, som er bare en anden array. Og hvis du ønsker at gemme Maxwell, du finder markøren, der repræsenterer En, der er denne ene her. Så kan du gå videre til næste node. Og bemærk - dette er grunden til billedets en lille bedrager - denne knude ser super lille. Men til højre for dette er Y og Z. Det er bare forfatteren har afkortet den billedet, så du rent faktisk se tingene. Ellers billede ville være enormt brede. Så nu er du indekset i location X, så W, så E, så L, så L. Så hvad er denne nysgerrighed? Tja, hvis vi bruger denne slags nye tage på, hvordan man gemme en snor i en datastruktur, du stadig nødt til at hovedsagelig afkrydse i de data, struktur, et ord ender her. Med andre ord, hver af disse knudepunkter en eller anden måde er nødt til at huske, at vi faktisk fulgt alle disse pejlemærker og forlader lidt brødkrummen nederst her på dette struktur at angive M-A-X-W-E-L-L er faktisk i dette datastruktur. Så vi kan gøre dette på følgende måde. Hver af knuder i det billede, vi bare Saven har en, en vifte af størrelse 27.. Og det er nu 27, fordi der i p sæt seks, Vi vil faktisk give dig en apostrof, så vi kan få navne som O'Reilly og andre med apostroffer. Men samme idé. Hvert af disse elementer i array-point til en struct knude, så bare en knude. Så det er meget minder af vores linkede liste. Og så har jeg en boolesk, som jeg vil kalde ord, som netop kommer til at være tilfældet, hvis et ord ender på dette knudepunkt i træet. Det effektivt repræsenterer den lille trekant oplevede vi for et øjeblik siden. Så hvis et ord slutter ved dette knudepunkt i træet, vil det ord felt være sandt, som er begrebsmæssigt tjekker ud, eller vi tegne denne trekant, ja der er et ord her. Så dette er en trie. Og nu er spørgsmålet, hvad er dens køretid? Er det store O n? Er det noget andet? Tja, hvis du har n navne i disse data struktur, Maxwell er blot én af dem, hvad er køretiden for indsætter eller finde Maxwell? Hvad er køretid at indsætte Maxwell? Hvis der er n andre navne allerede i tabellen? Ja? STUDENT: [uhørlig]. SPEAKER 1: Ja, det er længden af navnet, right? Så M-a-x-w-e-l-l, så det føles som dette algoritme er stort O i syv. Nu, selvfølgelig, navn vil variere i længde. Måske er det et kort navn. Måske er det en længere navn. Men hvad er nøglen her, er, at det er et konstant antal. Og måske er det ikke rigtig konstant, men Gud, hvis realistisk, i en ordbog, er der sandsynligvis nogle grænse på antallet af bogstaver i en persons navn i et bestemt land. Og så vi kan antage, at værdi er en konstant. Jeg ved ikke, hvad det er. Det er sandsynligvis større end vi synes, det er. Fordi der er altid nogle hjørne tilfældet med en vanvittig lange navn. Så lad os kalde det k, men det er stadig en konstant formentlig, fordi hver navn i verden, i det mindste i en bestemt land, er, at længde eller kortere, så det er konstant. Men når vi har sagt noget, er stort O i en konstant værdi, hvad er det virkelig svarer til? Det er virkelig det samme som siger konstant tid. Nu er vi slags snyd, right? Vi er slags udnytte noget teori her for at sige, at ja, orden k er egentlig bare bestille af en, og det er konstant tid. Men det virkelig er. Fordi det centrale indsigt her er at hvis vi har n navne allerede i dette datastruktur, og vi insert Maxwell, er den mængde tid, det tager os til indsætte Maxwell overhovedet berørte ved hvor mange andre mennesker er i datastrukturen? Synes ikke at være. Hvis jeg havde en milliard flere elementer i denne trie, og indsæt derefter Maxwell er Han overhovedet påvirket? Nej. Og det er ulig nogen af ​​dagen data strukturer, vi har set hidtil, hvor køretiden for din algoritme er helt uafhængigt af, hvor meget ting er, eller ikke allerede er i denne datastruktur. Og så med denne giver dig nu, er en mulighed for p sæt seks, hvilket vil igen involvere gennemføre din egen spell checker, læsning i 150.000 ord, hvordan man bedst opbevarer det er ikke nødvendigvis indlysende. Og selvom jeg har stræbt efter at finde den hellige gral, det gør jeg ikke hævder, at en trie er. I virkeligheden, kan en hash tabel udmærket vise sig at være meget mere effektivt. Men de er bare - det er bare én af design beslutninger bliver du nødt til at gøre. Men at lukke lad os tage 50 eller deromkring sekunder til at tage et kig på, hvad der ligger forude næste uge, og ud over vi overgangen fra denne kommandolinjen verden, hvis C-programmer til tingene web baseret, og sprog som PHP og JavaScript og internettet selv, protokoller som HTTP, som du har taget for givet i årevis nu, og maskinskrevet fleste hver dag, måske, eller set. Og vi vil begynde at skrælle tilbage lag af hvad er internettet. Og hvad er den kode, ligger til grund nutidens værktøjer. Så 50 sekunder af denne teaser her. Jeg giver dig Warriors of the Net. [VIDEO AFSPIL] -Han kom med et budskab. Med en protokol helt hans egen. Han kom til en verden af ​​grusomme firewalls, ufølsom routere, og farer langt værre end døden. Han er hurtig. Han er stærk. Han er TCPIP. Og han har din adresse. Warriors af nettet. [END VIDEOAFSPILNING] SPEAKER 1: Det er, hvordan internettet skal arbejde i næste uge.