[Musik spiller] 

ANDI Peng: Velkommen til uge 6 i afsnittet. Vi afveg fra vores standard sektion tid tirsdag eftermiddag til denne dejlige søndag morgen. Tak til alle, der sluttede sig til mig i dag, men alvorligt, en runde af bifald. 

Det er en temmelig stor indsats. Jeg næsten ikke engang gøre det op i tid, men det var OK. Så jeg ved, at alle jer har netop gjort det til quizzen. Først og fremmest, velkommen til bagsiden af ​​dette. 

For det andet vil vi tale om det. Vi taler om quizzen. Vi taler om, hvordan du laver i klassen. Du vil være fint. Jeg har dine quizzer for dig i slutningen af ​​her, så hvis du fyre ønsker at tage et kig på det, helt fint. 

Så hurtigt, før vi begynder, den dagsorden for i dag, er som følger. Som du kan se, er vi dybest set hurtig fyring gennem en hel masse datastrukturer virkelig, virkelig, virkelig hurtigt. Så som sådan, vil det ikke være Super interaktive dag. Det vil bare være mig slags råbe ting, som du, og hvis jeg forvirre dig, hvis jeg går for hurtigt, så lad mig det vide. De er bare forskellige data strukturer, og som en del af din pset for denne kommende uge, vil du blive bedt om at gennemføre en af ​​dem, måske to af them-- to af dem i dit pset. OK, så jeg bare kommer til at starte med nogle annonceringer. Vi vil gå over stakke og køer mere i dybde end hvad vi gjorde før quizzen. Vi vil gå over knyttet listen igen, endnu en gang, mere i dybden end hvad vi havde før quizzen. Og så vil vi tale om hash borde, træer og forsøger, som er alle temmelig nødvendigt for din pset. Og så vil vi gå over nogle nyttige tips til pset5. 

OK, så quiz 0. Gennemsnittet var en 58%. Det var meget lav, og så jer alle gjorde meget, meget godt i overensstemmelse med det. 

Temmelig meget, tommelfingerregel er, hvis du er inden en standardafvigelse på middelværdien især da vi er i en mindre comfy sektion, er du helt fint. Du er på rette spor. Livet er godt. 

Jeg ved det er skræmmende at tænke, at Jeg fik ligesom en 40% på denne quiz. Jeg har tænkt mig at svigte denne klasse. Jeg lover dig, du er ikke vil mislykkes klassen. Du er helt fint. 

For dem af jer, der fik over middelværdien, imponerende, imponerende, lignende, alvorligt godt gået. Jeg har dem med mig. Du er velkommen til at komme få dem i slutningen af ​​afsnittet. Lad mig vide, hvis du har nogen problemer, spørgsmål med dem. Hvis vi tilføje op din score forkert, så lad os det vide. 

OK, så pset5, dette er en virkelig underlig uge for Yale i den forstand at vores pset skyldes Onsdag ved middagstid, herunder den sene dag, så er det faktisk teoretisk grund tirsdag ved middagstid. Sandsynligvis ingen færdig på tirsdag ved middagstid. Det er helt fint. Vi kommer til at have kontortid i aften samt mandag aften. Og alle afsnittene i denne uge vil faktisk blive til workshops, så er du velkommen til at pop i alle afsnit, du ønsker, og de vil være slags mini-pset workshops for hjælp på det. Så som sådan, det er den eneste sektion hvor vi undervisningsmateriale. Alle de andre sektioner vil fokusere udelukkende på hjælp til pset. Ja? 

PUBLIKUM: Hvor er kontortid? 

ANDI Peng: Kontortid tonight-- åh, godt spørgsmål. Jeg tror kontortid i aften er i Teal eller i Commons. Hvis du tjekke online CS50 og du går til kontortid, der bør være en tidsplan, fortæller dig, hvor alle af dem er. 

Jeg kender enten i aften eller i morgen er krikand, og jeg tror, ​​vi kan have overdrev for den anden aften. Jeg er ikke sikker. Godt spørgsmål. Tjek på CS50. 

Cool, spørgsmål til tidsplan for den næste ligesom tre dage? Jeg lover jer som David sagde, det er toppen af ​​bakken. Du fyre er der næsten. Blot tre dage mere. Komme dertil, og så vil vi alle komme ned. Vi vil have en dejlig CS-fri pause. Velkommen tilbage. Vi vil dykke ned i web programmering og udvikling, ting, som er meget sjovt sammenlignet at nogle af de andre psets. Og det vil være chill, og Vi vil have masser af sjov. Vi vil have mere slik. Sorry for slik. Jeg glemte slik. Det var et groft morgen. Så du fyre er næsten der, og jeg er virkelig stolt af jer. 

OK, så stakke. Hvem elskede spørgsmål om Jack og hans tøj på quizzen? Ingen? OK, det er fint. 

Så det væsentlige, som du kan billede Jack, denne fyr her, elsker at tage tøj ud af toppen af ​​stakken, og han udtrykker det tilbage på stakken efter at han har gjort. Så på denne måde, han aldrig synes at være at få til bunden af stak i hans tøj. Så denne slags beskriver den grundlæggende datastruktur på, hvordan en stabel implementeres. 

Væsentlige, tænk på en stable så enhver stak af objekter hvor du lægger tingene på toppen, og så du pop dem ud fra toppen. Så LIFO er akronymet vi gerne at use-- Sidste In, First Out. Og så holde i den øverste del af stakken er den første, der kommer ud. Og så de to begreber vi gerne knytte med der kaldes skub og pop. Når du skubber noget på stak, og du pop det op igen. 

Og så jeg tror det er sådan en abstrakt begreb for dem af jer der ønsker at se som en faktiske gennemførelse af dette i den virkelige verden. Hvor mange af jer har skrevet et essay måske som en time før det var på grund af, og du ved et uheld slettet en enorm bid af det, ligesom et uheld? Og hvad så kontrol gøre vi bruger til at sætte det tilbage? Kontrol-Z, ikke? Ctrl-Z, så mængden af ​​gange at ctrl-Z har reddet mit liv, har reddet min røv, hver gang der er gennemført ved hjælp af en stak. 

Væsentlige alle de oplysninger der er på dit Word-dokument, det bliver skubbet dukkede efter behag. Og så væsentligt, når du slette noget, du pop den op igen. Og så hvis du har brug for den igen, du skubbe det, hvilket er, hvad Control-C gør. Og så virkelige verden funktion af, hvor nemt datastruktur kan hjælpe med din hverdag. 

Så en struct er den måde, vi faktisk skabe en stak. Vi skriver definere struct, og derefter vi kalder det stable nederst. Og inden for stakken, vi har to parametre at vi kan hovedsagelig manipulere, så vi har char stjerne strings kapacitet. 

Alt, hvad det gør skaber et array at vi kan gemme, hvad du ønsker som vi kan bestemme sin kapacitet. Kapacitet er bare max beløb af emner, vi kan sætte ind i denne række. int størrelse er tælleren, der holder styr på, hvor mange emner er i øjeblikket i stablen. Så kan vi holde styr på, A, både hvor stor den faktiske stakken er, og B, hvor meget af denne stak vi fyldt fordi vi ikke ønsker til overløb over, hvad vores kapacitet er. 

Så for eksempel denne dejlige Spørgsmålet var på din quiz. Hovedsagelig hvordan gør vi skubbe på toppen af ​​en stabel. Temmelig enkel. Hvis man ser på det, vi vil gå gennem dette. Hvis [uhørligt] size-- Husk, når du ønsker at få adgang til alle parameter inden for en struct, du gør navnet på struct.parameter. 

I dette tilfælde, s er navnet på vores stack. Vi ønsker at få adgang til størrelse af det, så gør vi s.size. Så længe størrelsen ikke er lig med kapaciteten eller så længe da det er mindre end kapaciteten, enten ville arbejde her. 

Du ønsker at få adgang til indersiden af din stack, så s.strings, og du kommer til at sætte det nye nummer at du ønsker at indsætte i der. Lad os bare sige, at vi gerne vil Indsæt int n på stakken, vi kunne gøre s.strings, beslag, s.size lig n. Fordi størrelse er, hvor vi øjeblikket er i stakken hvis vi kommer til at skubbe det på, vi bare få adgang hvor størrelsen er, jo nuværende fylde af stakken, og vi skubbe int n på det. Og så vil vi sørge for, at vi også forøge størrelsen af ​​n, så vi kan holde styr på vi har tilføjet en ekstra ting at stakken. Nu har vi en større størrelse. Betyder det her mening at alle, hvor logisk virker det? Det var slags hurtig. PUBLIKUM: Kan du gå over de s.stringss.strings [s.size] igen? ANDI Peng: Sure, så hvad betyder s.size øjeblikket give os? PUBLIKUM: Det er den nuværende størrelse. ANDI Peng: Præcis, så aktuelle indeks, som vores størrelse er på, og så vi ønsker at sætte den nye heltal at vi ønsker at indsætte i s.size. Giver det mening? Fordi s.strings, alt, er er navnet på arrayet. Alt det er er adgang til vifte inden for vores struct, og så hvis vi ønsker at placere n ind i det indeks, Vi kan bare få adgang til det ved hjælp af beslag s.size. Afkøle. 

Okay, pop, jeg pseudokode det ud til jer, men lignende koncept. Giver det mening? Hvis størrelsen er større end nul, så er du ved, at du ønsker at tage noget ud, fordi hvis størrelse ikke er større end nul, så er du har intet i stakken. 

Så du kun ønsker at udføre denne kode, kan det kun pop hvis der er noget til pop. Så hvis størrelsen er større end 0, vi minus størrelse. Vi formindske størrelsen og derefter vende tilbage hvad der er inde i det, fordi ved popping, ønsker vi at adgang uanset er gemt i indekset af toppen af ​​stakken. Alt mening? Hvis jeg gjorde jer skrive det ud, ville du fyre kunne skrive det ud? OK, kan du fyre lege med det. Ingen bekymringer, hvis du ikke får det. Vi har ikke tid til at kode det ud i dag, fordi vi har fik en masse af disse strukturer til at gå igennem, men hovedsagelig pseudokode, meget, meget lig skubbe. Bare følg langs logik. Sørg for, at du får adgang alle de funktionerne i din struct korrekt. Ja? 

PUBLIKUM: Vil disse lysbilleder og hele denne ting være op i dag-ish? ANDI Peng: Altid, jep. Jeg har tænkt mig at prøve at sætte dette op som en time efter. Jeg e-mailer David, vil David forsøge at sætte det op som en time efter dette. 

OK, så da vi bevæger os ind i denne anden dejlige datastruktur kaldes en kø. Som du fyre kan se her, en kø, for briterne blandt os, alt det er er en linje. Så i modsætning til hvad du mener en stak er, en kø er præcis, hvad logisk du tror det er. Det er holdt af reglerne i FIFO, som er First In, First Out. Hvis du er den første én i rækken, er du den første, som kommer ud af linjen. 

Så det, vi kan lide at kalde dette er dequeueing og enqueueing. Hvis vi ønsker at tilføje noget til vores kø, vi enqueue. Hvis vi ønsker at dequeue, eller tage noget væk, vi dequeue. 

Så samme forstand, at vi er sådan skabe fast størrelse elementer, som vi kan lagre visse ting, men vi kan også ændre, hvor vi placerer parametre inde i dem baseret på, hvad type funktionalitet, vi ønsker. Så stakke, vi ønskede det sidste én, N for at være den første ud. Kø er vi ønsker den første ting i at være den første ting ud. 

Så struct-typen definere, som du kan se, det er en lille smule anderledes fra det stakken var fordi ikke alene har vi nødt til at holde styr på, hvor størrelsen øjeblikket, Vi ønsker også at holde styr på hovedet samt hvor vi i øjeblikket er. Så jeg tror, ​​det er nemmere hvis jeg trækker det op. Så lad os forestille os, vi har fået en kø, så lad os sige hovedet er lige her. Lederen af ​​den linje, lad os bare sige, at der aktuelt er der, og vi ønsker at indsætte noget ind i køen. Jeg har tænkt mig at ringe størrelse væsentlige er det samme som hale, I slutningen af ​​hvor end din kø er. Lad os bare sige størrelse er lige her. 

Så hvordan gør man indpasses indsætte noget i en kø? Hvad indeks ønsker vi at placere hvor vi ønsker at indsætte i. Hvis dette er begyndelsen af ​​din kø og dette er enden på det eller størrelsen af ​​det, hvor skal vi ønsker at tilføje det næste objekt? 

PUBLIKUM: [uhørligt] ANDI Peng: Præcis, du ønsker at tilføje det afhængigt af du har skrevet den. Enten det er tomt, eller som er tomt. Så du ønsker at tilføje det sandsynligvis her, fordi hvis størrelsen is-- hvis disse er alle fulde, du ønsker at tilføje det her, ikke? 

Og så det er, mens meget, meget enkle, ikke helt altid er korrekte fordi den vigtigste forskel mellem en kø og en stak er, at køen kan faktisk manipuleres således at hovedet ændringer afhængigt af hvor du ønsker begyndelsen af ​​din cue til at starte. Og som et resultat, din hale også kommer til at ændre sig. Og så tage et kig på denne kode lige nu. Som jer også blev bedt om at skrive ud på quizzen, enqueue. Måske vil vi tale igennem, hvorfor svaret var, hvad det var. 

Jeg kunne ikke helt passe denne linje på et, men hovedsagelig dette stykke kode bør være på én linie. Tilbring ligesom 30 sekunder. Tag et kig, og se, hvorfor det er den måde, at det er. 

Meget, meget lignende struct, meget, meget lignende struktur som den tidligere stable undtagen måske én linje kode. Og at en linje kode bestemmer funktionaliteten. Og det er virkelig adskiller en kø fra en stabel. 

Nogen ønsker at tage et stik til at forklare, hvorfor du har fik denne komplicerede ting i her? Vi ser tilbagelevering af vores vidunderlige ven modul. Som du fyre snart vil komme at erkende i programmering, næsten når som helst du har brug for noget til wrap omkring noget, modul vil være måden at gøre det. Så vel vidende, at, er der nogen ønsker at forsøge at forklare denne linje kode? Ja, alle svar er accepteret og velkommen. PUBLIKUM: Taler du til mig? ANDI Peng: Ja. PUBLIKUM: Åh, nej undskyld. ANDI Peng: OK, så lad os gå gennem denne kode. Så når du forsøger at tilføje noget på en kø, i den dejlige tilfælde, at hovedet sker at være lige her, det er meget let for os bare gå til slutningen indsætte noget, ikke? Men hele pointen med en kø er at hovedet kan faktisk dynamisk ændre sig afhængigt af, hvor vi ønsker starten af ​​vores q at være, og som sådan, halen også kommer til at ændre sig. 

Og så forestille sig, at dette ikke var den kø, men snarere var køen. Lad os sige, hovedet er lige her. Lad os sige vores kø lignede dette. Hvis vi ønskede at flytte, hvor begyndelsen af ​​linjen er, Lad os sige, at vi skiftede hoved denne måde og størrelser her. 

Nu ønsker vi at tilføje noget til denne kø, men da du fyre kan se, det er ikke så simpelt som at bare tilføje, hvad der er efter størrelse fordi så vi løber tør for grænserne for vores faktiske matrix. Hvor vi vil virkelig tilføje, er her. Det er skønheden i en kø er, at for os, visuelt det ligner den linje går sådan her, men når de opbevares i en datastruktur, de giver det som som en cyklus. Den slags ombrydes omkring til fronten på samme måde at en linje også kan pakke rundt, afhængigt af hvor du vil begyndelsen af ​​linjen for at være. Og så hvis vi tager en se ned her, lad os siger vi ønskede at skabe et funktion kaldet Sæt i kø. Vi ønskede at tilføje int n ind at q. Hvis q.size q-- vi vil kalde, at vores data structure-- hvis vores queue.size ikke lig med kapaciteten eller hvis det er mindre end kapaciteten, q.strings er grupperingen i vores q. Vi kommer til at sætte at svare til q.heads, som er lige her, plus q.size modul af kapaciteten, hvilket wrap os tilbage her omkring. 

Så i dette eksempel indeks af hoved er 1, ikke? Indekset for størrelse er 0, 1, 2, 3, 4. Så vi kan gøre 1 plus 4 modul af vores kapacitet, der er 5. Hvad betyder, at give os? Hvad er det indeks, der kommer ud af dette? 

PUBLIKUM: 0. 

ANDI Peng: 0, hvilket sker for at være lige her, og så vi vil være i stand at indsætte i lige her. Og så denne ligning her slags for bare fungerer med nogen tal afhængigt af, hvor din hoved og din størrelse er. Hvis du ved, hvad de ting er, du ved præcis, hvor du vil indsætte hvad er efter din kø. Giver det mening for alle? 

Jeg kender sådan en hjerne teaser især da dette kom i kølvandet på din quiz. Men forhåbentlig alle nu kan forstå hvorfor denne opløsning eller dette funktion er den måde, det er. Nogen lidt uklart om det? OK. 

Og så nu, hvis du ønskede at dequeue, dette er, hvor vores hoved ville være at flytte fordi hvis vi skulle dequeue, vi ikke tage ud i slutningen af ​​q. Vi ønsker at tage ud i hovedet, ikke? Så som et resultat, er hovedet kommer til at ændre, og det er derfor, når du enqueue, you got at holde styr på hvor dit hoved og din størrelse skal være i stand til at indsætte i den korrekte position. 

Og så når du dequeue, Jeg har også pseudokode det ud. Du er velkommen til, hvis du vil at forsøge kodning det ud. Du ønsker at flytte hovedet, ikke? Hvis jeg ønskede at dequeue, jeg ville flytte hovedet over. Dette ville være hovedet. 

Og vores nuværende størrelse ville trække, fordi vi ikke længere har fire elementer i arrayet. Vi har kun tre, og så vil vi at returnere uanset var gemt inde af hovedet, fordi vi ønsker at tage dette værdi ud, så meget lig stakken. Bare du tager fra et andet sted, og du er nødt til at overflytte Deres pointer til andet sted som følge heraf. Logisk set alle følge? Stor. 

OK, så vi kommer til at tale lidt mere i dybden om hægtede lister fordi de vil være meget, meget værdifuldt for dig i løbet af denne uges psets. Hægtede lister, som du fyre kan huske, alle de er er knuder, som knudepunkter i visse værdier af både en værdi og en pointer der er bundet sammen disse pointere. Og så struct om, hvordan skaber vi en node her er vi har int n, som er hvad værdien i en butik eller snor n eller hvad du ønsker at kalder det, char stjerne n. Struct node stjerne, som er markøren at du ønsker at have i hvert knudepunkt, du kommer til at have det pointer peger næste. Du får hovedet en sammenkædet liste, der er kommer til at pege på resten af værdierne så videre og så videre indtil du til sidst når til slutningen. Og denne sidste node er bare vil ikke have en pointer. Det kommer til at pege på null, og det er når du ved, du har ramt slutningen af ​​din linkede liste er, når din sidste pointer ikke pege på noget. 

Så vi kommer til at gå lidt mere i dybde med hensyn til, hvordan man ville muligvis søger en sammenkædet liste. Husk, hvad er nogle af de ulemper ved de hægtede lister vers et array med hensyn søgninger. Et array kan du binær søgning, men Hvorfor kan du ikke gøre det i en linket liste? 

PUBLIKUM: Fordi de alle er tilsluttet, men du ved ikke helt, hvor [Uhørligt]. 

ANDI Peng: Ja, præcis så husk at glans af et array var, at vi havde random access memory, hvor hvis jeg ønskede at værdien fra indeks seks, kunne jeg bare sige indeks seks, give mig denne værdi. Og det er fordi arrays sorteres i en sammenhængende plads hukommelse på ét sted, mens slags hægtede lister er tilfældigt afbrudt hele vejen rundt, og den eneste måde du kan finde en er gennem en pointer, der fortæller dig adressen på, hvor denne næste knudepunkt er. 

Og så et resultat, den eneste måde at søge gennem en sammenkædet liste er lineær søgning. Fordi jeg ikke præcist ved, hvor 12. værdi i linkede liste er, Jeg er nødt til at krydse helhed af den linkede liste én efter én fra hovedet til det første knudepunkt, til det andet knudepunkt, til den tredje knudepunkt, hele vejen ned, indtil jeg endelig får til hvor at node jeg leder efter er. Og så i denne forstand, søg på en sammenkædet liste er altid n. Det er altid n. Det er altid i lineær tid. 

Og så den kode, hvori vi gennemfører dette, og dette er en smule nyt for jer, siden du fyre har ikke rigtig talt om eller nogensinde set pejlemærker i, hvordan man søge gennem pointere, så vi vil gå gennem denne meget, meget langsomt. Så bool søgning, højre, lad os forestille os, vi ønsker at skabe en funktion kaldet søgning, der returnerer true hvis du har fundet en værdi inde i linket listen, og den returnerer falsk ellers. Node stjerne listen er i øjeblikket bare markøren til det første emne i din linkede liste. int n er den værdi, du er søger efter på listen. 

Så node stjerne pointer lig listen. Det betyder, at vi sætte og skabe en pointer denne første knudepunkt inde i listen. Alle med mig? Så hvis vi skulle gå tilbage her, ville jeg have initialiseret en pegepind, der peger på lederen af ​​hvad det så listen er. 

Og så når du får hernede, mens markøren ikke er lig nul, så det er løkken, hvor vi er kommer til at være efterfølgende gennemkører resten af ​​vores liste, fordi hvad sker, når markøren er lig nul? Vi ved, at vi have-- 

PUBLIKUM: [uhørligt] 

ANDI Peng: Præcis, så vi ved, at vi har nået enden af ​​listen, ikke? Hvis du går tilbage her, hver node skal pege til en anden node og så videre og så videre indtil du rammer til sidst halen af ​​din linkede liste, som har en pointer, der bare peger ikke andre steder end ingen. Og så du dybest set ved, at din liste er der stadig op indtil markøren er ikke lig null fordi når det er lig nul, du ved, at der er ikke flere ting. 

Så det er den løkke, hvor vi er vil have den faktiske søgning. Og hvis pointer-- ser du den slags pil funktion der? Så hvis peger mod n, hvis markøren ved n lig lig n, så betyder, at hvis markøren, at du er efter på udgangen af ​​hvert node er faktisk lig med værdien du leder efter, så du ønsker at returnere sandt. Så dybest set, hvis du er på en node, har den værdi, du leder efter, du ved, at du har været i stand til at søge. 

Ellers du vil indstille markøren til den næste node. Det er, hvad denne linje her gør. Pointer lig pointer næste. Alle se, hvordan det fungerer? 

Og hovedsagelig du vil bare krydse helhed af listen, nulstille din pointer hver gang, indtil du i sidste ende ramte i slutningen af ​​listen. Og du ved, at der ikke er nogen flere noder for at søge igennem, og derefter kan du returnere false fordi du ved, at, åh, ja, hvis jeg har været i stand til at søge gennem helheden af ​​listen. Hvis i dette eksempel, hvis jeg ønskede at kigge efter den værdi af 10, og jeg starter i spidsen, og Jeg søger hele vejen ned, og jeg fik til sidst til dette, hvilket en pointer, der peger til null, Jeg ved, at, lort, jeg gætte 10 ikke er i denne liste, fordi jeg ikke kunne finde den. Og jeg er i slutningen af ​​listen. Og i hvilket tilfælde du vide Jeg har tænkt mig at vende tilbage falsk. 

Lad der lægges i blød i for en lille smule. Dette vil være temmelig vigtigt for din pset. Logikken i det er meget simpelt, måske syntaktisk bare gennemføre det. Du fyre ønsker at gøre sikker på, at du forstår. Afkøle. 

OK, så hvordan vi ville være indsætte noder, højre, i en liste, fordi huske hvad er hvad af de fordele for at have en sammenkædet liste versus et array i form af lagerplads? 

PUBLIKUM: Det er dynamisk, så det er nemmere at-- 

ANDI Peng: Præcis, så det er dynamisk, hvilket betyder, at det kan udvide og krympe afhængigt af brugerens behov. Og så, i denne forstand, at vi ikke har brug for at spilde unødvendig hukommelse, fordi jeg hvis jeg ikke ved, hvor mange værdier, jeg ønsker til butik, giver det ikke mening for mig at skabe et array, fordi hvis jeg ønsker at gemme 10 værdier og jeg skabe en række på 1.000, det er en masse spildt hukommelse, tildeles. Det er derfor, vi ønsker at bruge en sammenkædet listen at kunne dynamisk ændre eller skrumpe vores størrelse. 

Og så gør indsættelse en smule mere kompliceret. Da vi ikke tilfældigt kan få adgang til elementer den måde, at vi ville af et array. Hvis jeg ønsker at indsætte et element i den syvende indeks, Jeg kan bare indsætte det i den syvende indeks. På en sammenkædet liste, ikke det gør ganske arbejde så let, og så hvis vi ønskede at indsætte den ene her i den linkede liste, visuelt, det er meget nemt at se. Vi ønsker blot at indsætte det lige der, lige i starten af ​​listen, lige efter hovedet. 

Men den måde, som vi er nødt til at overflytte de pejlemærker er lidt komplicerede eller logisk, det giver mening, men du vil være sikker på, at du har det helt ned, fordi det sidste, du ønsker er at overflytte en pegepind den måde, at vi laver her. Hvis du dereference den pointer fra hoved til 1, så lige pludselig det resten af ​​dit linkede liste er tabt, fordi du har faktisk ikke oprettet et midlertidigt noget. Der er peget på 2. Hvis De overflytter markøren, så den Resten af ​​din liste er helt tabt. Så du ønsker at være meget, meget forsigtige her først tildele pointer fra hvad du vil indsætte i overalt, hvor du ønsker, og så skal du kan dereference resten af ​​din liste. 

Så det gælder uanset hvor du forsøger at indsætte i. Hvis du vil indsætte på hoved, hvis du ønsker at besvare her, Hvis du vil indsætte på enden, ja, enden jeg gætte du ville bare have nogen pointer, men du vil være sikker på, at du ikke gør mister resten af ​​din liste. Du ønsker altid at sørge for din nye node peger mod hvad du vil indsætte i, og så kan du tilføje den kæde på. Alle klar? 

Dette vil være en af ​​de virkelige problemer. En af de mest vigtige spørgsmål du kommer til at have på din pset er, at du vil forsøge at skabe en linket liste og indsætte ting men så bare tabe resten af ​​dit linkede liste. Og du kommer til at være ligesom, jeg ved ikke, hvorfor dette sker? Og det er en smerte at gå gennem og søg alle dine pointere. 

Og jeg garanterer dig på denne pset, skrive og tegne disse knudepunkter ud vil være meget, meget hjælpsomme. Så du kan helt holde styr af hvor alle dine pointere er, hvad der går galt, hvor alle dine noder er, hvad du skal gøre for at få adgang til eller indsætte eller slette eller nogen af ​​dem. Alle godt med det? Afkøle. 

Så hvis vi ønskede at se på koden? Åh, jeg ved ikke, om vi kan se til-- OK, så øverst alt er det er en funktion opkaldt indsats, hvor vi ønsker at indsætte int n i linkede liste. Vi kommer til at gå gennem dette. Det er en masse kode, en masse nye syntaks. Vi vil være OK. 

Så op på toppen, når vi ønsker at skabe noget hvad skal vi gøre, især hvis du ønsker, at det ikke gemmes på stakken men i den bunke? Vi går til en malloc, ikke? Så vi kommer til at skabe en pegepind. Node, pointer, nye ligemænd malloc størrelsen af ​​et knudepunkt fordi vi ønsker, at node, der skal oprettes. Vi ønsker, at mængden af hukommelse, en knude optager skal tildeles til oprettelsen af ​​den nye node. 

Og så vil vi kontrollere, se, om nye ligemænd lig nul. Husk, hvad vi sagde? Uanset hvad du malloc, hvad skal du altid gøre? Du skal altid kontrollere at se uanset om det er nul. 

For eksempel, hvis dit operativsystem Systemet var helt fuld, hvis du havde ikke mere hukommelse på alle og du forsøger at malloc, det ville returnere null for dig. Og så hvis du forsøger at bruge det da det blev peger til null, du kommer ikke til at kunne at få adgang til disse oplysninger. Og så som sådan, vi ønskede at gøre sikker på, at når du mallocing, du altid kontrollere at se, om at hukommelsen givet til dig er nul. Og hvis det ikke er, så vi kan flytte videre med resten af ​​vores kode. 

Så vi kommer til at initialisere den nye node. Vi vil gøre nye n er lig med n. Og så vil vi gøre sætte nyt markøren på nye til nul fordi lige nu har vi ikke ønsker noget for det til at pege på. Vi har ingen idé om, hvor det kommer til at sætte dig, og derefter, hvis vi ønsker at indsætte det i spidsen, så kan vi overflytte markøren til hovedet. Har alle følge den logik hvor der sker? 

Alt vi gør, er at skabe en ny node, indstilling markøren til null, og derefter omfordeling det i hovedet, hvis vi ved, at vi ønsker at indsætte den på hovedet. Og derefter hovedet kommer til at peger i retning af, at nye node. Alle OK med det? 

Så det er en to-trins proces. Du bliver nødt til først tildele uanset hvad du opretter. Indstil, at markøren til reference, og så skal du kan slags dereference den første pointer og pege mod nye node. Uanset hvor du ønsker at indsætte det, at logik kommer til at holde stik. 

Det er lidt ligesom at tildele midlertidige variabler. Husk, du har fået at sikre, at du ikke mister overblikket over, hvis du bytte. Du ønsker at sikre, at du har en midlertidig variabel den slags holder styr på, hvor at ting lagres så du ikke mister nogen værdi i løbet ligesom rode rundt med det. 

OK, så koden vil være her. Du fyre kigger efter sektion. Det vil være der. 

Så jeg gætte hvordan gør dette adskiller hvis vi ønskede at indsætte i midten eller slutningen? Er der nogen der har en idé om, hvad der er den pseudokode som den logiske henvisning at vi ville tage, hvis vi ønskede at indsætte det i midten? Så hvis vi ønskede at indsætte det på hoved, alt vi gør, er at oprette en ny knude. Vi sætter markøren af ​​denne ny node til uanset hovedet, og så har vi sat hovedet til den nye node, ikke? Hvis vi ønskede at indsætte det i midten på listen, hvad ville vi gøre? 

PUBLIKUM: Det ville stadig være en lignende proces ligesom tildele pointer og derefter tildele den pointer, men vi ville have til at lokalisere der. 

ANDI Peng: Præcis, så præcist den samme proces undtagen dig nødt til at lokalisere præcis, hvor du ønsker, at nye pointer til at gå ind i, så hvis jeg ønsker at indsætte i midt i tilknytning list-- OK, lad os sige det er vores linkede liste. Hvis vi ønsker at indsætte det lige her, vi vil oprette en ny knude. Vi kommer til at malloc. Vi kommer til at oprette en ny knude. Vi kommer til at tildele pointer af denne node her. 

Men problemet, der adskiller sig fra hvor hovedet er er, at vi vidste præcis hvor hovedet er. Det var lige på det første, ikke? Men her har vi at holde styr af, hvor vi indsætter det i. Hvis vi indsætter vores node her har vi for at sikre, at én tidligere til dette knudepunkt er den, der gentildeler markøren. Så er du nødt til at slags holde styr på to ting. Hvis du holder styr på, hvor dette node øjeblikket indsættelse ind. Du er også nødt til at holde styr på, hvor den forrige node, du kigger på var også der. Alle godt med det? OK. 

Hvad med at indsætte ind i enden? Hvis jeg ønskede at føje det her-- hvis jeg ønskede at tilføje et nyt knudepunkt til slutningen af ​​en liste, hvordan kan jeg gå om at gøre det? PUBLIKUM: Så i øjeblikket, det sidste ens pegede på nul. ANDI Peng: Ja. Præcis, så dette øjeblikket bliver peget på ved, og så jeg gætte, i denne forstand, er det meget nemt at tilføje til slutningen af ​​en liste. Alt du skal gøre er at sætte den svarende til null og derefter boom. Lige der, meget let. Meget enkel. 

Meget lig den hoved, men logisk du ønsker at sikre, at de skridt, du tager i retning af at gøre noget af dette, du følger med. Det er meget let at, i midten af din kode, blive fanget op på, Åh, jeg har så mange pointere. Jeg ved ikke, hvor noget peger på. Jeg ved ikke engang, hvilken node jeg er på. Hvad sker der? 

Slap af, falde til ro, tage en dyb indånding. Tegn din linkede liste. Hvis du siger, jeg ved, hvor præcist Jeg har brug for at indsætte dette i og jeg ved præcis, hvordan man overflytte min pointere, meget, meget nemmere at forestille out-- meget, meget lettere at ikke fare vild i de fejl i din kode. Alle OK med det? OK. 

Så jeg gætter et koncept, som vi ikke har virkelig talte om før nu, og jeg gætter du sandsynligvis vil ikke støde meget yet-- det er sådan en avanceret concept-- er, at vi faktisk har en data struktur, der kaldes en dobbelt linket liste. Så som du fyre kan se, alt vi gør er at skabe en faktisk værdi, en ekstra pointer på hver af vores knudepunkter der peger også på forudgående knudepunkt. Så ikke nok med at vi har vores knudepunkter peger på den næste. De peger også på den foregående. Jeg har tænkt mig at ignorere disse to lige nu. 

Så har du en kæde der kan bevæge sig begge veje, og så er det lidt nemmere til logisk følge med. Som her, i stedet for holde styr på, åh, jeg nødt til at vide, at denne node er den, som jeg er nødt til at overflytte, Jeg kan bare gå her og bare trække den forrige. Så jeg ved præcis, hvor der er, og så skal du behøver ikke at krydse hele den linkede liste. Det er lidt lettere. 

Men som sådan, har du dobbelt mængden af ​​pegepinde, det er dobbelt så meget hukommelse. Det er en masse pointere at holde styr på. Det er lidt mere kompliceret, men det er lidt mere brugervenlig, afhængigt om, hvad du forsøger at opnå. 

Så denne type data struktur helt eksisterer, og strukturen for er meget, meget enkel undtagen alt du har, er, i stedet for blot en pegepind til næste, har du også en pointer til forrige. Det er hele forskellen var. Alle godt med det? Afkøle. 

Okay, så nu er jeg til virkelig at tilbringe nok som 15 til 20 minutter eller hovedparten af resten af ​​tiden i afsnittet taler om hash tabeller. Hvor mange af jer har læst pset5 spec? Okay, godt. Der er højere end 50% af normalt. Det er ok. 

Så som du fyre vil se, du er udfordringen i pset5 vil være at gennemføre en ordbog hvor du lægger mere end 140.000 ord at vi giver dig og stavekontrol den mod hele teksten. Vi giver dig tilfældige stykker af litteratur. Vi giver dig Odysseen. Vi giver dig Iliaden. Vi giver dig Austin Powers. 

Og din udfordring vil være at stavekontrol hvert eneste ord i alt af disse ordbøger hovedsageligt med vores stavekontrol. Og så der er et par dele at skabe denne pset, først du ønsker at være stand til rent faktisk at indlæse alle ordene i din ordbog, og så skal du vil være i stand til stavekontrol dem alle. Og så som sådan, er du nødt til at kræve en datastruktur, der kan gøre dette hurtigt og effektivt og dynamisk. 

Så jeg formoder det nemmeste måde at gøre dette, du ville sandsynligvis skabe en række, ikke? Den nemmeste måde at lagring er dig kan skabe en række 140.000 ord og bare placere dem alle der, og derefter krydse dem ved binær søgning eller ved valg eller not-- ked, der er sortering. Du kan sortere dem og derefter krydse dem ved binær søgning eller bare lineær søgning og bare sidste ord, men at tager en enorm mængde hukommelse, og det er ikke særlig effektiv. 

Og så vil vi starte taler om måder at gøre vores køretid mere effektiv. Og vores mål er at få konstant tid, hvor det er næsten som arrays, hvor har du øjeblikkelig adgang til. Hvis jeg ønskede at søge efter noget, Jeg ønsker at være i stand til bare, boom, finde det præcist, og træk den ud. Og så en struktur, hvor vi vil blive meget tæt at være i stand til at få adgang til konstant tid, denne hellige gral i programmering af konstant tidspunkt kaldes en hash tabel. Og så David tidligere nævnt [Uhørlig] en lille smule i foredrag, men vi vil virkelig dykke i dyb denne uge på et stykke, der er med hensyn til hvordan en hash tabel fungerer. 

Så den måde, at en hash tabelværker, f.eks hvis jeg ønskede at gemme en masse ord, en bundt af ord i det engelske sprog, Jeg kunne i teorien sætte banan, æble, kiwi, mango, par, og cantaloupe alle på blot et array. De kunne alle passer ind og være finde. Det ville være slags en smerte at søge gennem og adgang, men den nemmere måde at gøre dette er at vi kan skabe faktisk en struktur kaldes en hash tabel, hvor vi hash. Vi kører alle vores nøgler gennem en hash-funktion, en ligning, der forvandler dem alle i en slags værdi at så kan vi gemme på hovedsagelig en matrix af linkede liste. 

Og så her, hvis vi ønskede at lagre engelske ord, vi kunne potentielt bare, det gør jeg ikke kender, slå alle de første bogstaver til en slags et nummer. Og så, for eksempel, hvis jeg ønskede En til at være synonymt med apple-- eller til indekset på 0, og B at være synonymt med 1, vi kan have 26 indgange der kan bare gemme alle bogstaver i alfabet, som vi vil starte med. Og så kan vi have Apple på indekset for 0. Vi kan have bananer på indekset for 1, cantaloupe på indekset for 2, og så videre og så videre. Og således hvis jeg ønskede at søge min hash tabellen og adgang æble, Jeg kender æble starter med en A, og jeg ved præcis at det skal være og hash bord på indeks 0, fordi af funktionen tidligere tildelt. 

Så ved jeg ikke, vi er en bruger program, hvor du vil blive opkrævet med arbitrarily-- ikke vilkårligt, med at forsøge at omtanke tænke på gode ligninger at kunne sprede ud af alle dine værdier på en måde, de nemt kan få adgang det senere med som en ligning at du, selv, kender. Så i den forstand, hvis jeg ønskede at gå til mango, jeg ved, åh, begynder med m det. Det skal være indekset for 12. Jeg behøver ikke at søge gennem noget. Jeg ved exactly-- jeg kunne bare gå til indekset på 12 og træk det ud. 

Alle klar over, hvordan en hash tabellen funktion virker? Det er sådan bare en mere kompleks array. Det er alt det er. OK. 

Så jeg tror vi løber ind dette spørgsmål om, hvad sker der, hvis du har flere ting at give dig det samme indeks? Så siger vores funktion, alle det gjorde var tage det første bogstav og vende det til en respektive 0 til 25 indekset. Det er helt fint, hvis du kun har en af ​​hver. Men det andet du starter have mere, er du vil have, hvad der kaldes en kollision. 

Så hvis jeg forsøger at indsætte begrave ind i en hash tabel, der allerede har banan på det, hvad der kommer til at ske, når du forsøger at indsætte det? Dårlige ting fordi banan findes den allerede i indekset at du ønsker at gemme det i. Berry slags er ligesom, ah, hvad gør jeg? Jeg ved ikke, hvor de skal gå. Hvordan kan jeg løse dette? 

Og så du fyre vil slags se vi gør det vanskelig ting hvor vi kan slags faktisk oprette linket liste i vore arrays. Og så den nemmeste måde at tænke over dette, al hash tabel er en vifte af hægtede lister. Og så, i den forstand, har du denne smukke vifte af pegepinde, og derefter hver pointer i denne værdi, i nævnte indeks, kan faktisk pege på andre ting. Og så har du alle disse særskilte kæder kommer ud af en stor matrix. 

Og så her, hvis jeg ønskede at indsætte bær, Jeg ved, OK, jeg har tænkt mig at input det gennem min hash-funktionen. Jeg har tænkt mig at ende op med indekset for 1, og så jeg har tænkt mig at være i stand til at have kun en mindre delmængde af denne gigant 140.000 ord ordbog. Og så kan jeg bare se gennem 1/26 af det. 

Og så kan jeg bare indsætte bær enten før eller efter banan I dette tilfælde? Efter, ikke? Og så du vil ønsker at indsætte denne node efter banan, og så du kommer til at indsætte på halen af ​​den linkede liste. Jeg har tænkt mig at gå tilbage til denne forrige dias, så du fyre kan se, hvordan hash-funktionen fungerer. 

Så hash-funktionen er denne ligning at du kører slags dit input igennem for at få uanset indeks du vil tildele mod. Og så, i dette eksempel, alle vi ønskede at gøre, var at tage det første bogstav, vende det til et indeks, så er vi kan gemme disse i vores hash-funktionen. Alt vi laver her er vi omdannelse af første bogstav. Så keykey [0] er blot det første bogstav uanset snor vi har, vi passerer i. Vi konverterer det til øverste, og vi fratrække med store bogstaver A, så alt, hvad der gør giver os en række hvor vi kan hash vores værdier på. 

Og så vil vi returnere hash modul størrelse. Være meget, meget forsigtig fordi, teoretisk, her din hashværdi kunne være uendelig. Det kunne bare blive ved og ved og ved. Det kunne være nogle virkelig, virkelig store værdi, men fordi din hash tabel, du har oprettet kun har 26 indekser, du vil sikre dig din modulusing så du ikke run-- det er det samme ting som din queue-- så du ikke løber væk fra bunden af ​​din hash-funktionen. 

Du ønsker at pak det tilbage omkring på samme måde i [uhørligt], når du havde som en meget, meget store bogstav, du ønskede ikke, at for at bare køre ud i slutningen. Samme ting her, du vil være sikker på det ikke løber ud i slutningen af ​​indpakning rundt til øverst i tabellen. Så dette er blot en meget simple hash-funktionen. Alle, der gjorde var at tage den første brev af uanset vores input var og vende det til et indeks, vi kunne sætte ind i vores hash tabellen. 

Ja, og så som jeg sagde før, den måde, vi løser kollisioner i vores hash tabeller har, hvad vi kalder, kæde. Så hvis du forsøger at indsætte flere ord, der starter med det samme, du kommer til at have en hash-værdi. Avocado og æble, hvis du har køre det gennem vores hash-funktionen, kommer til at give dig den samme nummer, antallet af 0. Og så den måde, vi løser, der er at vi kan faktisk slags linke dem sammen via hægtede lister. 

Og så i denne forstand, du fyre kan se slags på, hvordan datastrukturer, vi har været indstilling tidligere som en rosin sammenkædet liste art af kan komme sammen i én. Og så kan du oprette langt mere effektive datastrukturer der kan håndtere større mængder data, der dynamisk ændrer størrelse afhængigt på dine behov. Alle klar? Alle slags klart på, hvad der sker her? 

Hvis jeg ønskede at insert-- hvad er en frugt, der starter med, ved jeg ikke, B, bortset fra bær, bananer. 

PUBLIKUM: Blackberry. 

ANDI Peng: Blackberry, brombær. Hvor kommer brombær gå her? Nå, vi faktisk har ikke sorteres dette endnu, men i teorien hvis vi ønskede at have denne i alfabetisk rækkefølge, hvor skal blackberry hen? 

PUBLIKUM: [uhørligt] 

ANDI Peng: Præcis, efter her, ikke? Men da det er meget vanskeligt at reorder-- Jeg tror det er op til jer. Du fyre kan helt gennemføre hvad du vil. Jo mere effektiv måde at gøre dette måske ville være at sortere dit forbundet listen i alfabetisk rækkefølge, og så når du er indsætte ting, du ønsker være sikker på at indsætte dem i alfabetisk rækkefølge så så, når du er forsøger at søge dem, du behøver ikke at krydse alt. Du ved præcis, hvor det er, og det er lettere. 

Men hvis du slags har ting indflettet tilfældigt, du stadig vil have til at krydse det anyways. Og så hvis jeg ønskede at bare Indsæt blackberry her og jeg ønskede at søge efter det, jeg ved, åh, brombær skal starte med indekset på 1, så jeg kender øjeblikkeligt bare søge ved 1. Og så kan jeg slags krydse sammenkædet liste indtil jeg kommer til Blackberry, og then-- ikke? 

PUBLIKUM: Hvis du forsøger at create-- Jeg gætter ligesom dette er en meget simpel hash fungere. Og hvis vi ønskede at gøre flere lag af denne lignende, OK, vi ønsker at adskille i ligesom alle de alfabetiske bogstaver og derefter igen at kunne lide et andet sæt af alfabetiske bogstaver inden for denne, sætter vi gerne en hash tabel i en hash tabel, eller som en funktion i en funktion? Eller er at-- 

ANDI Peng: Så din hash function-- din hash tabel kan være så stor som du ønsker det. Så i den forstand, tænkte jeg det var meget let, meget nemt for mig at bare slags baserede på breve i det første ord. Og så der er kun 26 muligheder. Jeg kan kun få 26 muligheder fra 0 til 25, fordi de kun kan starte fra A til Z. men hvis du ønskede at tilføje, måske, mere kompleksitet eller hurtigere køre tid til din hash tabellen, du absolut kan gøre alle mulige ting. Du kan lave din egen ligning, der giver dig mere distribution i din ord, så når du søger, det vil være hurtigere. 

Det er helt op til jer hvordan du ønsker at gennemføre det. Tænk på det som bare spande. Hvis jeg ønskede at have 26 spande, jeg vil at sortere ting i disse spande. Men jeg har tænkt mig at have en flok ting i hver spand, så hvis du ønsker at gøre det hurtigere og mere effektiv, lad mig få hundrede spande. 

Men så er du nødt til at finde ud af en måde at sortere tingene, så de er i den rigtige bucket de skal være i. Men så når du rent faktisk ønsker at se på den spand, Det er meget hurtigere, fordi der er mindre ting i hver spand. Og så, ja, det er faktisk det trick for jer i pset5 er, at du vil være udfordret til bare oprette hvad der er den mest effektive funktion, du kan tænke på at være i stand til at lagre og kontrollere disse værdier. 

Helt op til jer men du ønsker at gøre det, men det er en rigtig god pointe. At den slags logiske dig ønsker at begynde at tænke over er, godt, hvorfor jeg ikke lave flere spande. Og så er jeg nødt til at søge mindre ting, og så måske jeg har en anden hash-funktionen. 

Ja, der er en masse måder at gøre dette pset, nogle er hurtigere end andre. Jeg helt vil bare se, hvordan hurtig var den hurtigste du fyre vil være i stand til at få funktioner til at arbejde. OK, alle godt på CHAINING og hash tabeller? Det er faktisk ligesom en meget enkel koncept, hvis man tænker over det. Alt det er at adskille, hvad dine input er i spande, sortere dem, og derefter søge på lister, der er forbundet med. 

Afkøle. Okay, nu har vi en anden slags af datastruktur, der kaldes et træ. Lad os gå på og tale om forsøg som er tydeligt forskellige, men i samme kategori. Væsentlige alle et træ er stedet for at organisere data i den lineære måde at en hash-tabel does-- dig kender, er det fik en top og en bund og så du slags linke ud af det-- en Træet har en top, som du kalder roden, og så har det blade rundt omkring det. 

Og så alt hvad du har her er kun den øverste node som peger på andre knudepunkter, der peger til flere noder, og så videre og så videre. Og så skal du bare opdele filialer. Det er bare en anden måde at organisere data, og fordi vi kalder det et træ, jer bare-- det er bare modelleret ud til at ligne et træ. Det er derfor, vi kalder det træer. 

Hash tabel ligner et bord. Et træ bare ligner et træ. Alt det er er en separat måde at organisere knuder afhængigt af, hvad dine behov er. 

Så du har en rod og så har du blade. Den måde, vi kan især tænker over det er et binært træ, et binært træ er blot en specifik type af et træ hvor hver node eneste punkter til, ved max, to andre knuder. Og så her har du distinkt symmetri i dit træ der gør det lettere at slags se på hvilke værdier du er, fordi du derefter har altid en venstre eller en højre. Der er aldrig ligesom en venstre tredjedel fra venstre eller en fjerde fra venstre. Det er bare du har en venstre og en højre og du kan søge en af ​​disse to. Og så hvorfor er det nyttigt? Den måde, at dette er nyttigt, er, hvis du søger at søge gennem værdier, ikke? Snarere end at gennemføre binær søge i en fejl array, hvis du ønsker at være i stand til at indsætte noder og tage væk knuder på vilje, og også bevare søgning kapacitet binær søgning. Så på den måde, vi er slags tricking-- huske, når vi sagde hægtede lister ikke kan binær søgning? Vi slags skabe en datastruktur at tricks, der i arbejdslivet. 

Og så fordi hægtede lister er lineære, de kun forbinde den ene efter den anden. Vi kan slags har anden slags pejlemærker der peger på forskellige noder der kan hjælpe os med søgning. Og så her, hvis jeg ønskede at har en binær søgning træ, Jeg ved, at mit mellemnavn, hvis 55. Jeg er bare kommer til at skabe den som mit mellemnavn, som min rod, og så vil jeg have værdier spin off af det. 

Så her, hvis jeg har tænkt mig at søge efter værdien af ​​66, kan jeg starte på 55. Det er 66 mere end 55? Ja, det er, så jeg ved, at jeg kødstykke søge I n højre pointer dette træ. Jeg går til 77. OK, er 66 mindre end eller større end 77? Det er mindre end, så du ved, åh, der skal være venstre node. 

Og så her er vi slags bevare alle de store ting om arrays, så ligesom dynamisk resizing af genstande, som er i stand til at indsætte og slette efter behag, uden at skulle bekymre sig om den faste mængde plads. Vi bevarer stadig alle disse vidunderlige ting samtidig være i stand til at bevare den log og søg tidspunktet for binær søgning at vi var kun tidligere stand til at få en sætning. 

Cool datastruktur, slags komplekse at gennemføre, knudepunktet. Som du kan se, alt det er struct knudepunktets er, at du har en venstre og en højre pointer. Det er alt det er. Så snarere end blot have en x eller en tidligere. Du har en venstre eller en højre og derefter du kan slags linke dem sammen men du så vælger. 

OK, vi rent faktisk vil bare tage et par minutter. Så vi kommer til at gå tilbage her. Som jeg sagde tidligere, Jeg forklarede slags logikken bag hvordan vi vil søge gennem dette. Vi kommer til at prøve pseudocoding dette ud for at se hvis vi slags kan anvende den samme logik binær søgning til en anden type datastruktur. Hvis du fyre ønsker at tage som et par minutter til bare at tænke over dette. OK. Okay, jeg har tænkt mig at faktisk bare give dig til-- nej, Vi vil tale om pseudokoden først. Så er der nogen ønsker at give et stik på, hvad den første ting du vil gøre, når du starter ud søgning er? Hvis vi leder efter værdien af ​​66, hvad er den første ting, vi ønsker at gøre, hvis vi ønsker at binær søgning dette træ? 

PUBLIKUM: Du ønsker at se lige og ser til venstre og se [uhørligt] større antal. 

ANDI Peng: Ja, præcis. Så du kommer til at se på din rod. Der er masser af måder, du kan ringe til det, siger dine forældre node mennesker. Jeg gerne sige rod, fordi det er ligesom roden af ​​træet. Du kommer til at se på din root node, og du er kommer til at se er 66 større eller mindre end 55. Og hvis det er større end, ja, det er større end, hvor vi ønsker at se? Hvor ønsker vi at søge nu, ikke? Vi ønsker at søge på højre halvdel af dette træ. 

Så vi har, bekvemt, en pointer, der peger til højre. Og så kan vi sætte vores nye rod at være 77. Vi kan bare gå derhen, hvor markøren peger. Nå, åh, her vi starter på 77, og vi kan bare gøre dette rekursivt igen og igen. På den måde du slags af en funktion. Du har en mulighed for at søge, at du kan bare gentage igen og igen og igen, afhængigt af hvor du ønsker at se indtil du til sidst kommer til den værdi, at du søger efter. Give mening? 

Jeg er ved at vise dig den faktiske kode, og det er en masse kode. Ingen grund til at flipper ud. Vi taler igennem det. 

Faktisk, nr. Det var bare pseudokode. OK, det var bare pseudokode, som er en smule kompliceret, men det er helt fint. Alle følger sammen her? Hvis roden er null, afkast falsk, fordi det betyder du behøver ikke engang noget der. 

Hvis rod n er værdien, så hvis det sker for at være den, du kigger på, så du kommer til at returnere sandt fordi du ved, du fandt den. Men hvis værdien er mindre end roden af ​​n, er du kommer til at søge venstre barn eller venstre blad, uanset hvad du vil kalde det. Og hvis værdien er større end root, du kommer til at søge den rigtige træet, så bare køre funktionen gennem søgning igen. 

Og hvis rod er nul, at denne betyder, at du har nået slutningen? Det betyder, at du ikke har nogen mere flere blade til at søge, så ved du, åh, jeg gætte det er ikke herinde fordi efter jeg har kigget igennem det hele og det er ikke her, det måske bare ikke være her. 

Giver det mening for alle? Så det er ligesom binær søgning bevare mulighederne i hægtede lister. Cool, og så den anden type af data struktur jer kan prøve at gennemføre på dit pset, du kun nødt til at vælge en metode. Men måske en alternativ metode til hash tabellen er, hvad vi kalder en trie. 

Alle en trie er en bestemt type træ, har værdier, der går til andre værdier. Så i stedet for at have en binær træ i den forstand, at kun én ting kan pege på to, kan du få én ting peger på mange, mange ting. Du hovedsageligt har arrays inde som du gemmer pointere, der peger på andre arrays. 

Så knudepunktet, hvordan vi ville definere en trie er, vi ønsker at have en Boolean c ord, ikke? Så knuden er boolesk ligesom sandt eller falsk, først og fremmest i spidsen for den opstilling, er det et ord? For det andet, du ønsker at have pejlemærker til, hvad resten af ​​dem er. En smule kompliceret, lidt abstrakt, men Jeg vil forklare, hvad at alle midler. 

Så her, i toppen, hvis du har en array erklæret allerede en node, hvor du har en boolesk lagret på forsiden der fortæller dig, er det et ord? Er det ikke et ord? Og så har du resten af ​​dit array, faktisk gemmer alle mulighederne for, hvad det kunne være. Så for eksempel, som øverst du har den første ting, der siger sandt eller falsk, ja eller nej, det er et ord. 

Og så har du 0 gennem 26 de bogstaver, som du kan gemme. Hvis jeg ønskede at søge her for flagermus, jeg gå til toppen og jeg ser for B. Jeg finde B i min array, og så ved jeg, OK, er B et ord? B er ikke et ord, så derfor Jeg må holde søger. Jeg går fra B, og jeg ser til pointer, at B peger i retning af og jeg ser en anden vifte af information, den samme struktur, som vi havde før. 

Og her-- åh, den næste bogstav i [uhørligt] er A. Så vi ser i dette array. Vi finder den ottende værdi, og derefter se vi at se, åh, hey, er, at et ord, er B-A et ord? Det er ikke et ord. Vi har fået at holde udkig. 

Og så så ser vi på, hvor markøren over A-punkter, og den peger på en anden måde i hvor vi har mere værdi gemt. Og til sidst, vi får at B-A-T, som er et ord. Og så næste gang du ser, er du nødt at have denne kontrol af, ja, denne Boolesk funktion er sandt. Og så i den forstand er vi slags for at have et træ med arrays. 

Så kan du slags søge ned. Snarere end hashing en funktion og tildele værdier ved linket liste, kan du bare gennemføre en Trie, der søger downwords. Virkelig, virkelig kompliceret ting. Ikke let at tænke over, fordi jeg er ligesom spytte så mange datastrukturer ud på dig, men gør alle slags forstå, hvordan logikken i dette fungerer? 

OK, cool. Så B-A-T, og derefter du kommer til at søge. Næste gang du går at se, åh, hey, det er sandt, derfor jeg ved, at dette skal være et ord. 

Samme for zoo. Så her er de ting lige nu, hvis vi ønskede at søge efter zoo, lige nu, øjeblikket zoo er ikke en ord i vores ordbog fordi, som du fyre kan se, første sted, at vi har en boolesk returnere sandt er i slutningen af ​​zoom. Vi har Z-O-O-M. 

Og så her, vi faktisk ikke har ordet, zoo, i vores ordbog fordi dette afkrydsningsfelt ikke er markeret. Så computeren ikke ved, at zoo er et ord fordi den måde, at vi har gemt det, kun en zoom her faktisk har en boolesk værdi der er blevet vendt rigtigt. Så hvis vi ønsker at indsætte ord, zoo, ind i vores ordbog, hvordan ville vi gå om at gøre det? Hvad skal vi gøre for at sikre vores computer ved, at Z-O-O er et ord og ikke det første ord er Z-O-O-M? 

PUBLIKUM: [uhørligt] 

ANDI Peng: Præcis, vi ønsker at sikre, at denne her, at Boolesk værdi afkrydset, at det er sandt. Z-O-O, så vi kommer til at kontrollere, at, så vi ved præcis, hey, zoo er et ord. Jeg har tænkt mig at fortælle computer, det er et ord, så at når computeren checks, det ved, at zoo er et ord. 

Fordi huske alle disse data strukturer, er det meget let for os at sige, åh, bat er et ord. Zoo er et ord. Zoom er et ord. Men når du bygger det, computeren har ingen idé. 

Så du er nødt til at fortælle det nøjagtigt på hvilket tidspunkt er det et ord? På hvilket tidspunkt er det ikke et ord? Og på hvilket tidspunkt gør jeg nødt til at søge ting, og på hvilket tidspunkt har jeg brug for at gå næste? Enhver fri af det? Afkøle. 

Og så så kommer den problemet med, hvordan ville vi gå om at indsætte noget det er faktisk ikke der? Så lad os bare sige, at vi ønsker at indsætte ordet, bad, ind i vores trie. Som du fyre kan se som i øjeblikket alle vi har nu, er B-A-T, og denne nye datastruktur der havde en fadøl, der pegede på nul, fordi vi antager at, åh, er der ingen ord efter B-A-T, hvorfor har vi brug for at holde have tingene efter denne T. 

Men problemet opstår, hvis vi gør du ønsker at have et ord, der kommer efter T s. Hvis du har bad, er du vil ønsker en H højre. Og så den måde, vi kommer til at gøre det er vi kommer til at oprette en separat node. Vi er ikke tildele uanset mængde hukommelse for denne nye array, og vi kommer til at overflytte pointere. 

Vi kommer til at tildele H, Først og fremmest, dette null, vi kommer til at slippe af med. Vi kommer til at have H-punktet nedad. Hvis vi ser et H, vi ønsker det at gå til et andet sted. 

Herinde kan vi derefter kontrollere ud ja. Hvis vi rammer et H efter T, åh, så ved vi, at dette er et ord. Den boolesk kommer til at returnere sandt. Alle klar på, hvordan det skete? OK. 

Så det væsentlige, alle disse datastrukturer at vi har gået over i dag, jeg har gået over dem virkelig, virkelig hurtigt og ikke på meget detaljer, og det er OK. Når du begynder at rode med det, vil du være holde styr på, hvor alle pejlemærker er, hvad der foregår i dit datastrukturer, et cetera. De vil være meget nyttigt, og det er op til dig fyre til helt finde ud af hvordan du ønsker at gennemføre tingene. 

Og så pset4, af 5-- åh, det er forkert. Pset5 er stavefejl. Som jeg sagde før, er du nødt til, når igen, hente kildekoden fra os. Der kommer til at være tre vigtigste ting, du skal downloade. Du vil downloade ordbøger, KERS, og tekster. 

Alle disse ting er er enten ordbøger af ord at vi vil have dig til at tjekke eller test af oplysninger at vi vil have dig til stavekontrol. Og så ordbøgerne vi giver du vil at give dig faktiske ord, vi ønsker dig at gemme en eller anden måde på en måde, der er mere effektiv end et array. Og så teksterne er kommer til at være, hvad vi er beder dig om at stave tjekke for at sikre alle de ord der er reelle ord. 

Og så de tre blokke af programmer, som vi vil give dig kaldes dictionary.c, dictionary.h og speller.c. Og så alle dictionary.c gør er hvad du bedt om at gennemføre. Den indlæser ord. Det stave checks dem, og det gør sikker at alt er indsat korrekt. 

diction.h er bare et bibliotek fil der erklærer alle disse funktioner. Og speller.c, vi vil give dig. Du behøver ikke at ændre noget af det. Alle speller.c gør, er at tage det, belastninger det, kontrollerer hastigheden af ​​det, tester benchmark ligesom hvordan hurtigt du er i stand til at gøre ting. 

Det er en speller. Bare ikke rode med det, men gør at du forstår hvad det gør. Vi bruger en funktion kaldet getrusage som tester effektiviteten af ​​din magi checker. Alt det gør, er dybest set teste tid af alt i din ordbog, så sørg for at forstå det. Vær omhyggelig med ikke at rode med det, eller ellers ting vil ikke køre ordentligt. 

Og hovedparten af ​​denne udfordring er for du fyre til virkelig ændre dictionary.c. Vi vil give dig 140.000 ord i en ordbog. Vi vil give dig en tekst fil, der har disse ord, og vi ønsker at du skal være i stand til at organisere dem i en hash tabel eller en trie fordi når vi beder dig om at stave check-- forestille mig, hvis du er magi kontrol ligesom Homers Odysseen. Det er ligesom denne enorme, enorme test. 

Tænk, hvis hver eneste ord, du var nødt til at se gennem en række værdier 140.000. Det ville tage for evigt til din maskine til at køre. Det er derfor, vi ønsker at organisere vores data i mere effektive datastrukturer såsom en hash bord eller et trie. Og så du fyre kan slags på, når du søger adgang tingene lettere og hurtigere. 

Og så vær omhyggelig med at løse kollisioner. Du kommer til at få en masse af ord, der starter med A. Du kommer til at få en masse ord at starte med B. Op til dig fyre hvordan du vil løse det. Måske er der mere effektiv hashfunktion end blot det første bogstav i noget, og så det er op til dig fyre at slags gøre hvad du vil. 

Måske du ønsker at tilføje alle bogstaver sammen. Måske du ønsker at lide at gøre underlige ting at redegøre antallet af bogstaver, hvad end. Op til jer, hvordan du ønsker at gøre. Hvis du ønsker at gøre en hash tabel, hvis du ønsker at prøve en trie, helt op til dig. Jeg vil advare dig på forhånd, at den Trie er typisk en smule mere vanskeligt bare fordi der er en masse flere pointere at holde styr på. Men helt op til jer. Det er langt mere effektiv i de fleste tilfælde. Du vil virkelig være i stand til at holde styr på alle dine pointere. Ligesom gøre det samme at jeg gjorde her. Når du forsøger at indsætte værdier ind i en hash tabel eller slette, sørg for, at du er virkelig holde styr hvor alt er fordi det er virkelig nemt for hvis jeg forsøger at indsætte ligesom ordet, andy. Lad os bare sige, det er en virkelige ord, det ord, andy, til en gigantisk liste over et ord. 

Hvis jeg bare tilfældigvis overflytte en pointer forkert, Ups, der går i sin helhed resten af ​​min sammenkædet liste. Nu det eneste ord, jeg har, er Andy, og nu alle de andre ord i ordbog er gået tabt. Og så du vil være sikker på, du holde styr på alle dine pegepinde eller andet, du vil få store problemer i din kode. Tegn tingene ud forsigtigt skridt for skridt. Det gør det meget lettere at tænke på. 

Og endelig, du ønsker at være i stand til teste din præstation af dit program på den store bord. Hvis du fyre tage en se på CS50 lige nu, Vi har, hvad der kaldes den store bord. Det er scoren ark af den hurtigste stave gange kontrol på tværs af alle CS50 lige nu, tror jeg toppen ligesom 10 gange jeg tror otte af dem er personale. Vi virkelig ønsker jer til at slå os. 

Alle os forsøgte at gennemføre den hurtigste kode som muligt. Vi ønsker jer til at prøve at udfordre os og gennemføre hurtigere end alle os kan. Og så dette er virkelig første gang, at vi er beder jer til at gøre en pset der du virkelig kan gøre i uanset metode du vil have. 

Jeg siger altid, det er mere beslægtet til en real-life løsning, ikke? Jeg siger, hey, jeg har brug for dig til at gøre dette. Byg et program, der gør dette for mig. Gør det dog, du ønsker. Jeg ved bare, at jeg vil til at faste. Det er din udfordring for denne uge. Du gutter, vi kommer at give dig en opgave. Vi vil give dig en udfordring. Og så er det op til jer til helt at bare regne ud hvad er den hurtigste og mest effektiv måde at gennemføre dette. Ja? 

PUBLIKUM: Er vi lov til, hvis ønskede at forske hurtigere måder at gøre hash tabeller online, kan vi gøre det og citere en andens kode? ANDI Peng: Ja, helt fint. Så hvis du fyre læser spec, der er en linje i spec, der siger jer er helt gratis at forske hash funktioner på hvad er nogle af de hurtigere hashfunktioner at køre tingene igennem som længe du nævner denne kode. Så nogle mennesker har allerede regnet ud hurtige måder gøre stavekontrol, af hurtige måder at lagring af oplysninger. Helt op til jer, hvis du bare ønsker at tage den, ikke? Sørg for, at du citerer. Udfordringen her virkelig at vi prøver at teste er at sikre, at du ved din vej rundt pointere. Så langt som du gennemføre den faktiske hash-funktionen og kommer op med lignende matematik til at gøre det, du fyre kan forskning, hvad metoder online jer ønsker. Ja? 

PUBLIKUM: Kan vi nævne bare ved hjælp af [uhørligt]? 

ANDI Peng: Ja. Du kan bare i din kommentar, du kan citere ligesom, åh, taget fra yada, yada, yada, hash-funktionen. Nogen der har nogen spørgsmål? Vi har faktisk breezed gennem afsnit dag. Jeg vil være op her til besvare spørgsmål så godt. 

Også, som jeg sagde, kontor timer i aften og i morgen. Den spec denne uge er faktisk super let og super kort at læse. Jeg vil foreslå at tage et kig, bare læse helhed af det. 

Og Zamyla faktisk fører dig gennem hver af de funktioner du har brug for at gennemføre, og så det er meget, meget klart, hvordan at gøre alt. Blot for at sikre, at du er holde styr på pointers. Dette er en meget udfordrende pset. 

Det er ikke udfordrende, fordi lignende, Åh, de begreber er så meget mere svært, eller du nødt til at lære så meget ny syntaks vejen at du gjorde for den sidste pset. Denne pset er vanskeligt, fordi der er så mange markører, og så er det meget, meget let til en gang du har en fejl i din kode ikke være i stand at finde, hvor at fejlen er. 

Og så fuldstændig og totalt tro på dig fyre at være i stand til at slå vores [uhørligt] stavemåder. Jeg har faktisk ikke nogen skriftlig miner endnu, men jeg er ved at skrive mine. Så mens du skriver dit, jeg vil skrive mine. Jeg har tænkt mig at forsøge at gøre mine hurtigere end din. Vi vil se, hvem der har den hurtigste. 

Og ja, jeg vil se alle jer her på tirsdag. Jeg vil køre en form som en pset værksted. Alle sektionerne denne uge er pset workshops, så du fyre har masser af muligheder om hjælp, kontortid som altid, og jeg ser virkelig frem til læse alle dine guys kode. Jeg har quizzer op her, hvis du fyre ønsker at komme få dem. Det er alt.