[Speel van musiek] ANDI Peng: Welkom by week 6 van artikel. Ons afgewyk van ons standaard artikel tyd van Dinsdag middag om hierdie pragtige Sondag oggend. Dankie vir almal wat saam met my vandag, maar ernstig, 'n ronde van die applous. Dit is 'n mooi groot poging. Ek het amper nie eens maak dit up in die tyd, maar dit was OK. So ek weet dat julle almal het dit net gemaak om die quiz. Eerste van alles, welkom om die ander kant van daardie. Tweedens, sal ons daaroor praat. Ons sal praat oor die quiz. Ons sal praat oor hoe jy doen in die klas. Jy sal goed wees. Ek het jou vasvrae vir jy aan die einde van hier, so as jy ouens wil neem 'n blik op dit, heeltemal fyn. So vinnig voor ons begin, die agenda vir vandag is soos volg. Soos jy kan sien, is ons basies vinnige vuur deur 'n hele klomp van die data strukture regtig, regtig, regtig vinnig. So as sodanig, sal dit nie wees nie super interaktiewe vandag. Dit sal net my soort skree dinge wat jy, en as ek verwar jy, as ek gaan te vinnig, laat my weet. Hulle is net verskillende data strukture, en as deel jou pset vir hierdie komende week, sal jy word gevra om een ​​van hulle te implementeer, miskien twee van them-- twee van hulle in jou pset. OK, so ek is net gaan om te begin met 'n paar aankondigings. Ons gaan oor stapels en toue meer diepte as wat ons voor die quiz gedoen het. Ons sal gaan oor gekoppelde lys weer, weer, meer in diepte as wat ons moes voor die quiz. En dan sal ons praat oor hash tafels, bome en drieë, wat is almal mooi wat nodig is vir jou pset. En dan sal ons gaan oor 'n paar nuttige wenke vir pset5. OK, so quiz 0. Die gemiddelde was 'n 58%. Dit was baie laag is, en so julle ouens al het baie, baie goed in ooreenstemming met daardie. Pretty much, reël is as jy binne 'n standaardafwyking van die gemiddelde veral omdat ons in 'n minder gemaklike artikel, jy is heeltemal fyn. Jy is op die regte spoor. Die lewe is goed. Ek weet dit is scary om te dink dat Ek het soos 'n 40% op hierdie quiz. Ek gaan hierdie klas misluk. Ek belowe jou, jy is nie gaan aan die klas misluk. Jy is heeltemal fyn. Vir dié van julle wat oor het die gemiddelde, indrukwekkend, indrukwekkend, soos, ernstig goed gedoen. Ek het hulle met my. Voel vry om te kom kry hulle aan die einde van afdeling. Laat my weet as jy enige het kwessies, vrae saam met hulle. As ons jou telling verkeerd is, laat ons weet. OK, so pset5, dit is 'n baie vreemde week vir Yale in die sin dat ons pset is te danke Woensdag middag insluitend die laat dag, so dit is eintlik teoreties gevolg Dinsdag middag. Waarskynlik niemand klaar op Dinsdag middag. Dit is heeltemal fyn. Ons gaan kantoorure het vanaand asook Maandag nag. En al die afdelings sal hierdie week eintlik verander in werkswinkels, so voel vry om te pop in enige artikel wat jy wil, en hulle sal soort van mini-pset wees werkswinkels vir hulp op daardie. So as sodanig, dit is die enigste artikel waar ons leer materiaal. Al die ander afdelings sal fokus uitsluitlik op hulp vir die pset. Ja? GEHOOR: Waar is kantoorure? ANDI Peng: Kantoor ure tonight-- oh, goeie vraag. Ek dink kantoorure vanaand is in Teal of by Commons. As jy online CS50 kyk en jy gaan na kantoorure, daar moet 'n skedule wees dat vertel jou waar almal van hulle is. Ek weet nie vanaand of môre is teal, en ek dink ons ​​kan hê commons vir die ander aand. Ek is nie seker nie. Goeie vraag. Kyk op CS50. Cool, enige vrae oor die skedule vir die volgende drie dae soos? Ek belowe julle ouens soos David gesê dit is die top van die berg. Julle is amper daar. Net drie dae. Kry daar, en dan sal ons almal kom neer. Ons sal 'n mooi CS-vry te breek nie. Ons sal terug te kom. Ons sal duik in web ontwikkeling en ontwikkeling, dinge wat baie pret in vergelyking sommige van die ander psets. En dit sal chill wees, en ons sal baie pret hê. Ons sal meer lekkergoed. Jammer vir lekkergoed. Ek het vergeet lekkergoed. Dit was 'n rowwe oggend. So julle ouens is amper daar, en ek is baie trots op julle. OK, so stapels. Wie was lief vir die vraag oor Jack en sy klere aan die quiz? Niemand? OK, dit is goed. So in wese as wat jy kan prentjie Jack, hierdie man hier, lief vir die klere te neem uit die top van die stapel, en hy sit dit terug op die stapel nadat hy gedoen het. So op hierdie manier, het hy nooit blyk te wees om aan die onderkant van die stapel in sy klere. So hierdie soort beskryf die basiese data struktuur van hoe 'n stapel geïmplementeer word. Wese, dink aan 'n stapel as enige stapel van voorwerpe waar jy dinge op die top, en hulle dan pop julle uit die top. So LIFO is die akroniem ons graag om use-- Laaste in, eerste uit. En so duur in die top van die stapel is die eerste een wat kom uit. En so het die twee terme ons graag assosieer met wat push en pop genoem. Wanneer jy iets op die druk stapel, en jy dit pop back-up. En so het ek dink dit is soort van 'n abstrakte konsep vir dié van julle wat wil om te sien soos 'n werklike implementering van hierdie in die werklike wêreld. Hoeveel van julle het 'n opstel geskryf Miskien soos 'n uur voor dit te wyte, en jy per ongeluk geskrap 'n groot stuk van dit, soos per ongeluk? En dan wat beheer te doen ons gebruik om dit terug te sit? Beheer-Z, ja? Beheer-Z, sodat die bedrag van die tye wat beheer-Z my lewe gered het, het my gat gered, elke keer dit is geïmplementeer deur 'n stapel. Wese al die inligting dit is op jou Word dokument, dit word gestoot en inloer wil. En so in wese wanneer jy enigiets verwyder, jy pop back-up. En dan as jy dit nodig het weer op, jy stoot dit, en dit is wat beheer-C nie. En so die werklike wêreld funksie van hoe eenvoudige data struktuur kan help met jou alledaagse lewe. So 'n struct is die pad wat ons eintlik skep 'n stapel. Ons tik definieer struct, en dan ons noem dit stapel aan die onderkant. En binne die stapel, ons het twee parameters wat kan ons in wese te manipuleer, so ons het char star snare kapasiteit. Al wat dit doen skep 'n skikking dat ons kan stoor wat jy wil waarin ons sy kapasiteit kan bepaal. Kapasiteit is net die maksimum bedrag van items wat ons in hierdie reeks kan sit. int grootte is die toonbank wat hou hou van hoeveel items is tans in die stapel. So dan kan ons hou van, A, beide hoe groot die werklike stapel is, en, B, hoeveel van daardie stapel ons gevul omdat ons wil nie om oor oorloop wat ons kapasiteit is. So byvoorbeeld, hierdie pragtige vraag was op jou quiz. Wese hoe doen ons stoot op die top van 'n stapel. Eenvoudig. As jy kyk na dit, ons sal loop deur middel van hierdie. As [onhoorbaar] size-- Onthou, wanneer jy wil enige toegang parameter binne 'n struct, jy die naam van die struct.parameter. In hierdie geval, is s die naam van ons stapel. Ons wil die grootte toegang dit, so ons doen s.size. So solank die grootte is nie gelyk aan kapasiteit of so lank as dit is minder as kapasiteit, óf sou hier werk. Jy wil om toegang tot die binnekant van jou stapel, so s.strings, en jy gaan om dit te sit nuwe nommer wat jy wil plaas in daar. Laat ons net sê ons wil voeg int N op die stapel, ons kon s.strings te doen, hakies, s.size gelyk n. Omdat grootte is waar ons tans in die stapel as ons gaan om te stoot dit op, ons het net toegang waar die grootte is, die huidige volheid van die stapel, en ons stoot die int N op dit. En dan wil ons seker maak dat ons is ook die verhoog grootte van die N, sodat ons kan hou van wat ons het 'n ekstra ding by die stapel. Nou het ons 'n groter grootte. Is dit hier sin maak om almal, hoe logies dit werk? Dit was soort van 'n vinnige. GEHOOR: Kan jy gaan oor die s.stringss.strings [s.size] weer? ANDI Peng: Seker, so wat doen s.size ons tans te gee? GEHOOR: Dis die huidige grootte. ANDI Peng: Presies, so die huidige indeks wat ons grootte is op, en so wil ons die nuwe heelgetal sit wat ons wil voeg in s.size. Maak wat sin maak? Omdat s.strings, alles wat is die naam van die skikking. Al wat dit is, is toegang tot die verskeidenheid binne ons struct, en so as ons wil plaas n in daardie indeks kan ons net toegang tot dit die gebruik van hakies s.size. Koel. Alle reg, pop, ek pseudokode dit uit vir julle nie, maar soortgelyke konsep. Maak wat sin maak? As die grootte is groter as nul, dan moet jy weet dat jy iets wil neem uit, want as die grootte is nie groter as nul, dan moet jy het niks in die stapel. So jy wil net om uit te voer hierdie kode, kan dit slegs pop as daar is iets om te pop. So as die grootte is groter as 0, ons minus die grootte. Ons decrement die grootte en dan terug alles wat binnekant van dit, want deur die knal, ons wil toegang ongeag gestoor in die indeks van die top van die stapel. Alles sin maak? As ek gemaak julle skryf dit uit, sou julle in staat wees om dit uit te skryf? OK, julle ouens kan speel met dit. Geen bekommernisse as jy dit nie kry nie. Ons het nie tyd om kode hê dit vandag, want ons het het 'n baie van hierdie strukture om deur te gaan, maar in wese pseudokode, baie, baie soortgelyk aan te stoot. Volg net langs die logika. Maak seker dat jy toegang tot al die eienskappe van jou struct korrek. Ja? GEHOOR: Sal hierdie skyfies en hierdie hele ding wees vandag-ish? ANDI Peng: Altyd, yep. Ek gaan om te probeer om te sit hierdie up soos 'n uur daarna. Ek sal e-pos Dawid sal Dawid probeer om sit dit op soos 'n uur nadat die. OK, so dan skuif ons in hierdie ander pragtige data struktuur genaamd 'n tou. As julle ouens hier kan sien, 'n ry, vir die Britse onder ons, al is dit is 'n lyn. So anders as wat jy dink 'n stapel is, 'n tou is presies wat logies jy dink dit is. Dit is gehou deur die reëls van die EIEU, wat is die eerste in, eerste uit. As jy die eerste een in die lyn, is jy die eerste een wat kom uit die lyn. So, wat ons graag noem dit is dequeueing en enqueueing. As ons iets wil voeg ons ry, ons enqueue. As ons wil dequeue, of neem iets weg, ons dequeue. So dieselfde sin dat ons soort skep vaste grootte elemente wat ons kan sekere stoor dinge, maar ons kan ook verander waar ons plaas parameters binnekant van hulle gebaseer op watter tipe funksie wat ons wil. So stapels, ons wou die laaste een, N om die eerste een uit wees. Tou is ons wil die eerste ding in die eerste ding uit te wees. So die struct-tipe definieer, soos jy kan sien, dit is 'n bietjie anders van wat die stapel was want nie net het ons om aan te hou spoor van waar die grootte tans, ons wil ook om tred te hou van die kop te hou asook waar ons tans is. So ek dink dit is makliker as ek teken dit op. So laat dink ons ​​het 'n tou het, so kom ons sê die hoof is reg hier. Die hoof van die lyn, laat net sê dit is daar op die oomblik, en ons wil voeg iets in die tou. Ek gaan grootte wese roep is dieselfde ding as stert, die einde van waar jou tou is. Laat ons net sê grootte is reg hier. So hoe kry mens feasibly voeg iets in 'n tou? Wat indeks wil ons plaas waar ons wil voeg in. As dit is die begin van jou ry en dit is die einde van dit of die grootte van dit, waar ons doen wil die volgende voorwerp voeg? GEHOOR: [onhoorbaar] ANDI Peng: Presies, wat jy wil byvoeg dit afhangende het jy geskryf. Óf dit is leeg, of dat is leeg. So jy wil om dit waarskynlik voeg hier, want as die grootte is-- As dit is al vol, jy wil om dit reg hier by te voeg, reg? En so is dit, terwyl baie, baie eenvoudige, nie heeltemal altyd korrek omdat die belangrikste verskil tussen 'n tou en 'n stapel is dat die tou kan eintlik gemanipuleer sodat die hoof veranderinge afhangende van waar jy wil die begin van jou cue om te begin. En as 'n gevolg, jou stert ook gaan verander. En so 'n blik op hierdie kode nou. As julle ouens is ook gevra om skryf uit op die quiz, enqueue. Miskien sal ons deur die rede waarom praat was die antwoord wat dit was. Ek kon nie heeltemal inpas hierdie lyn op een, maar in wese hierdie stuk van die kode moet wees op een lyn. Spandeer soos 30 sekondes. Neem 'n blik, en sien waarom dit is die manier waarop dit is. Baie, baie soortgelyk struct, baie, baie soortgelyke struktuur as die vorige stapel behalwe vir miskien een lyn van kode. En dat 'n mens reël van die kode bepaal die funksie. En dit is werklik 'n onderskeid 'n tou van 'n stapel. Iemand wil hê om 'n steek te neem om te verduidelik waarom jy het het hierdie ingewikkelde ding hier? Ons sien die terugkeer van ons wonderlike vriend modulus. As julle ouens gou sal kom om te erken in programmering, byna elke keer as jy iets nodig het te draai om enigiets, modulus gaan die manier om dit te doen. So weet dat nie almal wil om te probeer verduidelik dat die lyn van die kode? Ja, al die antwoorde is aanvaar en welkom. GEHOOR: Is jy met my praat? ANDI Peng: Ja. GEHOOR: O, nee jammer. ANDI Peng: OK, so laat loop deur hierdie kode. So wanneer jy probeer om iets by te voeg op 'n tou, in die pragtige geval dat die hoof gebeur om hier te wees, is dit baie maklik vir ons om net na die einde voeg iets, reg? Maar die hele punt van 'n tou is dat die hoof eintlik kan dinamiese verander, afhangende van waar ons wil die begin van ons q te wees, en as sodanig, die stert ook gaan verander. En so dink dat dit nie die was ry nie, maar eerder dit was die tou. Kom ons sê die hoof is reg hier. Kom ons sê die tou lyk soos hierdie. As ons wou skuif waar die begin van die lyn is, Kom ons sê ons verskuif hoof hierdie manier en groottes hier. Nou wil ons iets om by te voeg hierdie ry, maar as julle kan sien, dit is nie so eenvoudig soos om net te voeg alles wat na die grootte want dan uit loop ons perke van ons werklike skikking. Waar ons wil regtig voeg is hier. Dit is die skoonheid van 'n tou is dat ons, visueel dit lyk soos die lyn gaan soos hierdie, maar wanneer gestoor in 'n data struktuur, hulle gee dit as 'n siklus soos. Dit vou soort rondom aan die voorkant van die dieselfde manier dat 'n lyn kan ook draai rondom afhangende waar jy wil begin van die lyn te wees. En so as ons 'n kyk hier, laat ons sê ons wil 'n te skep funksie genoem enqueue. Ons wou int N add in daardie q. As q.size q-- ons sal noem dat ons data structure-- as ons queue.size nie gelyk aan kapasiteit of indien dit is minder as kapasiteit, q.strings is die skikking in ons q. Ons gaan sit wat gelyk is aan q.heads, wat is reg hier, plus q.size modulus deur die kapasiteit, wat draai ons terug hier rond. So in hierdie voorbeeld, indeks van die kop is 1, reg? Die indeks van grootte is 0, 1, 2, 3, 4. So kan ons 1 plus 4 modulus doen deur ons kapasiteit wat is 5. Wat beteken dit vir ons? Wat is die indeks wat kom uit hierdie? GEHOOR: 0. ANDI Peng: 0, wat gebeur na regs hier te wees, en so het ons wil in staat wees in te voeg in hier. En so hierdie vergelyking hier soort van net werk met enige nommers afhangende van waar jou kop en jou maat is. As jy weet wat die dinge is, jy weet presies waar jy wil plaas alles wat na jou tou. Maak dit sin om almal? Ek weet van 'n brein soort teaser veral aangesien hierdie gekom het in die nasleep van jou quiz. Maar hopelik almal nou kan verstaan waarom hierdie oplossing of hierdie funksie is die manier waarop dit is. Enigiemand 'n bietjie onduidelik op daardie? OK. En so nou, as jy wou dequeue, hierdie is waar ons hoof sal wees verskuif want as ons dequeue, Ons neem nie af aan die einde van die q. Ons wil die kop te neem, reg? So as 'n gevolg hiervan, is die hoof van plan te verander, en dit is hoekom wanneer jy enqueue, jy het om tred te hou waar jou kop en jou maat is om in staat wees om in te voeg in die regte posisie. En so wanneer jy dequeue, Ek pseudokode dit ook. Voel vry om as jy wil om te probeer kodering dit uit. Jy wil die kop te skuif, reg? As ek wou dequeue, ek sou die kop te skuif oor. Dit sal die hoof wees. En ons huidige grootte sou trek omdat ons nie meer het vier elemente in die skikking. Ons het net drie, en dan wil ons om terug te keer alles binne gestoor van die kop, want ons wil om dit te neem waarde uit so baie soortgelyk aan die stapel. Net jy neem uit 'n ander plek, en jy het om jou muis toewys om ander plek as 'n gevolg. Logies, almal volg? Groot. OK, so ons gaan 'n bietjie praat meer in diepte oor geskakelde lyste omdat hulle baie, baie waardevol sal wees vir jou in die loop van hierdie week se psets. Geskakelde lyste, as julle ouens kan onthou, al is hulle is nodes wat nodes van sekere waardes van beide 'n waarde en 'n wyser wat saam gekoppel deur diegene wenke. En so het die struct oor hoe Ons skep 'n node hier is ons het int N, wat ook al die waarde in 'n winkel of string N of wat ook al jy wil dit noem, die char star n. Struct node ster, wat die wyser wat jy wil hê in elke knoop, jy gaan wat wyser punt teenoor die volgende. Jy sal die kop het van 'n geskakelde lys dis gaan om te wys op die res van die waardes so aan en so voort totdat jy uiteindelik die einde. En dit is net die laaste node gaan 'n wyser nie. Dit gaan om te wys op null, en dit is wanneer jy weet jy het druk op die einde van jou geskakelde lys is wanneer jou laaste wyser nie wys nie. So ons gaan 'n bietjie meer in te gaan diepte oor hoe 'n mens sou moontlik soek 'n geskakelde lys. Onthou wat is 'n paar van die nadele van die geskakelde lyste verse 'n skikking rakende navrae. 'N skikking kan jy binêre soek, maar Hoekom kan jy dit nie doen nie in 'n geskakelde lys? GEHOOR: Omdat hulle almal is verbind, maar jy hoef nie heeltemal weet waar [Onhoorbaar]. ANDI Peng: Ja, presies so onthou dat die glans van 'n verskeidenheid was die feit dat ons moes ewetoeganklike geheue waar as ek wou die waarde van indeks ses, ek kon net sê indeks ses gee my daardie waarde. En dit is omdat skikkings gesorteer in 'n aangrensende ruimte van die geheue in een plek, terwyl soort geskakelde lyste is lukraak afgewissel rondom, en die enigste manier waarop jy kan 'n mens vind is deur middel van 'n wyser wat jou vertel Die adres van waar dat die volgende node is. En so as 'n gevolg, die enigste manier om te soek deur 'n geskakelde lys lineêr search. Want ek weet nie presies waar die 12de waarde in die geskakelde lys is, Ek het na die geheel deurkruis van daardie geskakelde lys een een van die hoof na die eerste knoop, na die tweede node, na die derde knoop, al die pad af totdat ek uiteindelik om waar daardie node Ek soek is. En so in hierdie sin, soek op 'n geskakelde lys is altyd n. Dit is altyd n. Dit is altyd in lineêre tyd. En so die kode in wat voer ons hierdie, en dit is 'n bietjie nuut vir julle omdat julle ouens het nie regtig gepraat oor of ooit gesien wenke oor hoe om soek deur wysers, so ons sal loop deur hierdie baie, baie stadig. So Bool search, regs, laat dink ons ​​wil om 'n funksie genoem te skep soek dat ware terug as jy 'n waarde in die verband gevind lys, en is dit terug valse anders. Node star lys is tans net die wyser om die eerste item in jou geskakelde lys. int N is die waarde wat jy soek in die lys. So node star wyser gelyk lys. Dit beteken dat ons die opstel is en die skep van 'n wyser dat die eerste node binnekant van die lys. Almal met my? So as ons was om te gaan terug hier, sou ek geïnisialiseer 'n wyser wat verwys na die hoof van alles wat die lys is. En dan wanneer jy hier kom neer, terwyl wyser nie gelyk nul, sodat die lus in wat ons is gaan dan wees kameelkoei die res van ons lys, want wat gebeur wanneer wyser gelyk null? Ons weet dat ons have-- GEHOOR: [onhoorbaar] ANDI Peng: Presies, so ons weet dat ons het die einde van die lys bereik, reg? As jy hier gaan terug, elke node moet op 'n ander node en so aan en so voort totdat jy uiteindelik getref die stert van jou geskakelde lys, wat 'n wyser het wat net nêrens anders as geen punt. En sodat jy basies weet dat jou lys is daar nog steeds totdat wyser nie gelyk null want sodra dit gelyk nul, jy weet dat daar is geen dinge meer. Dit is dus die lus in wat ons is gaan na die werklike soek het. En as die pointer-- sien jy dat die soort van pyl funksie daar? So as wyser punte N, as die wyser op n gelyk gelyk N, so dit beteken dat indien die wyser dat jy soek vir die einde van elke node is eintlik gelyk aan die waarde jy soek, dan jy wil om waar te keer. So basies, as jy op 'n node wat het die waarde wat jy soek, jy weet dat jy is in staat wees om suksesvol te soek. Andersins, jy wil in te stel jou muis na die volgende knoop. Dit is wat die lyn hier doen. Wyser gelyk wyser volgende. Almal sien hoe dit werk? En in wese gaan jy net deurkruis die geheel van die lys, Herstel jou muis elke keer tot jy uiteindelik getref die einde van die lys. En jy weet dat daar geen meer nodes om te soek deur, en dan kan jy terug valse omdat julle weet dat, oh, goed, as ek in staat om te soek gewees het deur die geheel van die lys. As in hierdie voorbeeld, as ek wou om te kyk vir die waarde van 10, en ek begin by die hoof en Ek soek al die pad af, en ek het uiteindelik na hierdie, wat 'n wyser wat verwys na nul Ek weet dat, crap, ek dink 10 is nie in hierdie lys, want ek kon dit nie vind nie. En ek is aan die einde van die lys. En in watter geval jy weet Ek gaan valse terugkeer. Laat dit week in vir 'n bietjie. Dit sal mooi wees belangrik vir jou pset. Die logika van dit is baie eenvoudig, miskien sintakties net die uitvoering daarvan. Julle wil maak seker dat jy verstaan. Koel. OK, so hoe sou ons invoeging nodes, regs, in 'n lys want onthou wat die wat van die voordele van 'n geskakelde lys versus 'n skikking in terme van die stoor? GEHOOR: Dis dinamiese, sodat dit makliker is aan- ANDI Peng: Presies, so dit is dinamiese, wat beteken dat dit kan uitbrei en krimp afhangende van die gebruiker se behoeftes. En so, in hierdie sin, ons hoef nie onnodige geheue mors, want ek as ek nie weet hoeveel waardes Ek wil op te slaan, is dit nie sin maak vir my om 'n skikking te skep, omdat as ek wil 10 waardes te stoor en Ek skep 'n skikking van 1000, wat 'n baie vermors geheue, toegeken. Dit is hoekom ons wil gebruik om 'n verband lys in staat wees om dinamies verander of krimp ons grootte. En so wat maak invoeging 'n bietjie meer ingewikkeld. Aangesien ons kan nie lukraak toegang elemente die manier waarop ons 'n skikking sou van. As ek wil 'n element te voeg in die sewende indeks Ek kan dit net voeg in die sewende indeks. Op 'n geskakelde lys, is dit nie baie werk so maklik, en so as ons wou voeg die een wat hier in die geskakelde lys, visueel, dit is baie maklik om te sien. Ons wil net om dit reg daar te plaas, reg aan die begin van die lys, reg na kop. Maar die manier waarop ons moet toewys die wysers is 'n bietjie gekronkelde of, logies, maak dit sin, maar jy wil om seker te maak dat jy dit het heeltemal af, omdat die laaste ding wat jy wil is om 'n wyser toewys die manier wat ons hier doen. As jy die dereference verwysing van kop tot 1, dan is almal van 'n skielike die res van jou geskakelde lys verlore, want jy het nie eintlik het 'n tydelike enigiets. Dit is gewys op die 2. As jy die wyser, dan is die toewys res van jou lys is totaal verlore. So jy wil wees baie, baie versigtig hier eerste toewys die wyser van alles wat jy wil plaas in waar jy wil, en dan sal jy kan dereference die res van jou lys. So dit geld vir waar jy probeer om te voeg in. As jy wil te voeg by die kop, as jy hier wil beantwoord, as jy wil voeg by die einde, goed, die einde Ek dink jy wil net het geen wyser, maar jy wil seker maak dat jy dit nie doen nie verloor die res van jou lys. Jy wil altyd om seker te maak jou nuwe node wys teenoor alles wat jy wil voeg in, en dan kan jy voeg die aaneenskakeling op. Almal duidelik? Dit gaan wees een van die werklike kwessies. Een van die mees belangrike kwessies jy gaan op jou pset is dat jy gaan om te probeer om te skep 'n geskakelde lys en voeg dinge maar dan net verloor die res van jou geskakelde lys. En jy gaan om te wees soos ek weet nie hoekom dit gebeur? En dit is 'n pyn om te gaan deur en soek al jou wenke. En ek waarborg jou op hierdie pset, skryf en teken hierdie nodes uit sal baie, baie nuttig. So kan jy heeltemal tred te hou van waar al jou wenke is, wat verkeerd gaan, waar al jou nodes is, wat jy nodig het om te doen om toegang te verkry of voeg of te verwyder of enige van hulle. Almal goed met dit? Koel. So as ons wou om te kyk na die kode? O, ek weet nie of ons kan the-- OK sien, so by die top al is dit is 'n funksie vernoem insetsel waar ons wil om int N voeg in die geskakelde lys. Ons gaan om te loop deur middel van hierdie. Dit is 'n baie van die kode, 'n baie nuwe sintaksis. Ons sal OK wees. So by die top, wanneer Ons wil niks te skep wat doen wat ons moet doen, veral as jy dit wil nie gestoor word op die stapel maar in die hoop? Ons gaan na 'n malloc, reg? So ons gaan 'n wyser skep. Knoop, pointer, nuwe gelykes malloc die grootte van 'n node omdat ons wil hê dat die node geskep. Ons wil hê dat die bedrag van geheue wat 'n node neem word toegeken vir die skepping van die nuwe knoop. En dan gaan ons kyk na sien as nuwe gelykes gelyk null. Onthou wat ons gesê het? Wat jy ook al malloc, wat moet jy altyd doen? Jy moet altyd kyk om te sien of wat null. Byvoorbeeld, as jou bedryfstelsel stelsel is heeltemal vol, as jy het nie meer geheue almal en jy probeer om malloc, dit sou null vir jou terug. En so as jy probeer om dit te gebruik toe dit wys na nul jy gaan nie in staat om toegang tot die inligting. En so as sodanig, ons wou maak seker dat wanneer jy mallocing, Jy is altyd om te kyk of dat die geheue wat aan jou gegee is null. En as dit is nie, dan kan ons beweeg met die res van ons kode. So ons gaan inisialiseer die nuwe knoop. Ons gaan om te doen nuwe N gelyk n. En dan gaan ons doen stel nuwe die wyser op die nuwe om null want nou is ons nie wil niks vir dit om te wys. Ons het geen idee waar dit gaan jy, en dan as ons wil plaas dit op die kop, dan kan ons toewys die wyser na die kop. Maak almal volg die logika waar wat gebeur? Al wat ons doen is die skep van 'n nuwe knoop, die opstel van die wyser na nul en dan gehou indiensneming dit aan die hoof as ons weet ons dit wil voeg by die kop. En dan is die hoof gaan wys na nuwe knoop. Almal is ok met dit? So dit is 'n twee-stap proses. Jy het die eerste assign alles wat jy skep. Stel dat wyser na die verwys, en dan moet jy kan soort van dereference die eerste wyser en wys dit na die nuwe knoop. Waar jy wil om dit te plaas, daardie logika gaan ware te hou. Dit is soort van soos die toeken tydelike veranderlikes. Onthou, jy het om seker te maak dat jy moenie die spoor van as jy uitruiling verloor nie. Jy wil om seker te maak dat jy 'n tydelike veranderlike wat soort van hou spoor van waar daardie ding gestoor sodat jy nie enige waarde verloor nie in die kursus van soos die rond met dit. OK, so-kode sal hier wees. Julle neem 'n blik na artikel. Dit sal daar wees. So ek dink hoe werk hierdie verskil as ons wou in te voeg in die middel of aan die einde? Is daar iemand het 'n idee van wat die pseudokode as die logiese verwysing dat ons sal neem as ons wou om dit te plaas in die middel? So as ons dit wou voeg by die kop, al wat ons doen, is 'n nuwe knoop. Ons stel die wyser van daardie nuwe node om ongeag die kop, en dan het ons die hoof om die nuwe node, reg? As ons wou dit voeg in die middel van die lys, wat sou ons moet doen? GEHOOR: sou dit nog steeds 'n soortgelyke proses van soos die toeken wyser en dan toeken wat pointer, maar ons wil hê om daar te spoor. ANDI Peng: Presies, so presies dieselfde proses, behalwe jy het presies waar jy op te spoor wil hê dat die nuwe wyser in te gaan, so as ek wil voeg in die middel van gekoppelde list-- OK, Kom ons sê dit is ons geskakelde lys. As ons wil hê om dit reg hier te plaas, ons gaan 'n nuwe node skep. Ons gaan malloc. Ons gaan 'n nuwe node skep. Ons gaan die toewys wyser van hierdie node hier. Maar die probleem wat verskil van waar die kop is is dat ons presies geweet waar die kop is. Dit was reg by die eerste, reg? Maar hier het ons 'om tred te hou van waar ons dit in te voeg. As ons die inbring ons node hier, ons het om seker te maak dat die een vorige hierdie node is die een wat die wyser reassigns. So dan moet jy soort hou van twee dinge. As jy hou van waar hierdie hou node tans invoeging in. Jy moet ook op hoogte van waar hou die vorige node wat jy kyk na was ook daar. Almal goed met dit? OK. Hoe gaan in die einde? As ek dit wou voeg here-- as ek wou om 'n nuwe node by te voeg tot die einde van 'n lys, hoe kan ek gaan om dit te doen? GEHOOR: So tans die laaste een se wys na nul. ANDI Peng: Ja. Presies, so hierdie een tans daarop om te weet, en so dink ek, in hierdie sin, is dit baie maklik om by te voeg tot die einde van 'n lys. Al wat jy hoef te doen, is sit dit gelyk aan nul en dan boom. Reg daar, baie maklik. Baie eenvoudig. Baie soortgelyk aan die kop, maar logies jy wil seker maak dat die stappe neem jy die rigting van enige van dit te doen, jy die volgende saam. Dit is baie maklik om te, in die middel van die kode, kry gevang op, oh, ek het so baie verwysings. Ek weet nie waar enigiets wat dui op. Ek weet nie eens wat node Ek is. Wat gaan aan? Ontspan, kalmeer, neem 'n diep asem. Teken jou geskakelde lys. As jy sê, ek weet presies waar Ek het nodig om hierdie plaas in en ek weet presies hoe om toewys my wysers, baie, baie makliker om te beeld out-- baie, baie makliker om nie verdwaal in die foute van die kode. Almal is ok met dit? OK. So ek dink 'n konsep wat ons het nie regtig gepraat oor voor nou, en ek dink jy waarskynlik sal nie veel teëkom yet-- dit is soort van 'n gevorderde concept-- is dat ons eintlik 'n data struktuur bekend as 'n dubbel geskakelde lys. So as julle kan sien, Al wat ons doen is die skep van 'n werklike waarde, 'n ekstra wyser op elkeen van ons nodes wat ook dui op die vorige node. So nie net ons het ons nodes dui op die volgende een. Hulle wys ook aan die vorige een. Ek gaan om te ignoreer hierdie twee nou. So dan het jy 'n ketting wat kan beide maniere beweeg, en dan is dit 'n bietjie makliker logies volg saam. Soos hier, in plaas van dop van, o, ek moet weet dat hierdie node is die een wat ek het om te toewys, Ek kan net gaan hier en net trek die vorige. Dan weet ek presies waar dit is, en dan sal jy nie aan die deurkruis geheel van die geskakelde lys. Dit is 'n bietjie makliker te maak. Maar as sodanig, dubbel jy die bedrag van die wysers, dit is dubbel die bedrag van die geheue. Dit is 'n baie van wysers om tred te hou. Dit is 'n bietjie meer ingewikkeld, maar dit is 'n bietjie meer gebruikersvriendelik afhangende op wat jy probeer om te bereik. So hierdie tipe van data struktuur heeltemal bestaan, en die struktuur vir baie, baie eenvoudige behalwe al wat jy het, is, in plaas van net 'n verwysing na die volgende, jy het ook 'n verwysing na die vorige. Dit is al wat die verskil was. Almal goed met dit? Koel. Alle reg, sodat nou is ek om werklik waarskynlik spandeer soos 15 tot 20 minute of die grootste deel van die res van die tyd in artikel praat oor hash tabelle. Hoeveel van julle ouens pset5 spec gelees het? Alle reg, goed. Dit is hoër as die 50% van normaal. Dit is OK. So as julle sal sien, jy uitdaging in pset5 sal wees om 'n woordeboek te implementeer waar jy laai meer as 140,000 woorde dat ons vir u en speltoets dit teen alle van die teks. Ons gee jou ewekansige stukke van die letterkunde. Ons gee jou die Odyssey. Ons gee jou die Ilias. Ons gee jou Austin Powers. En jou uitdaging sal wees om check spel elke enkele woord in alle van daardie woordeboeke wese met ons speltoetser. En dus is daar 'n paar dele van die skep van hierdie pset, die eerste wat jy wil wees staat is om werklik te laai al die woorde in jou woordeboek, en dan moet jy wil in staat wees om speltoets almal van hulle. En so as sodanig, jy gaan om te vereis 'n datastruktuur dat dit vinnig kan doen en doeltreffend en dinamiese. So ek dink die maklikste manier om dit te doen, moet jy sou waarskynlik Skep 'n skikking, reg? Die maklikste manier van die stoor is jy kan 'n verskeidenheid van 140,000 woorde te skep en net hulle almal te plaas daar en dan deurkruis hulle deur die binêre soek of deur keuses of not-- jammer dit is sorteer. Jy kan sorteer hulle en dan deurkruis hulle deur binêre soek, of net lineêre soek en net finale die woorde nie, maar dat neem 'n groot hoeveelheid van die geheue, en dit is nie baie doeltreffend nie. En so gaan ons begin praat oor maniere om ons hardloop tyd meer doeltreffend. En ons doel is om te kry konstante tyd waar Dit is amper soos skikkings, waar jy oombliklike toegang. As ek wou om te soek vir enigiets, Ek wil in staat wees om net, boom, vind dit presies, en trek dit uit. En so 'n struktuur waarin ons sal raak baie geheg in staat wees om toegang te verkry tot voortdurende tyd, hierdie heilige graal in programmering van konstante tyd word 'n hash tafel. En so het Dawid voorheen genoem die [Onhoorbaar] 'n bietjie in lesing maar ons gaan om werklik duik in diep hierdie week op 'n stuk wat betrekking is hoe 'n hash tafel werk. So die manier waarop 'n gemors tabel werk, byvoorbeeld, As ek wou 'n klomp van die woorde te stoor, 'n n klomp van die woorde in die Engelse taal, Ek kon teoreties sit piesang, appel, kiwi, mango, paar, en spanspek almal op net 'n skikking. Hulle kon almal pas in en word vind. Dit sou soort van 'n pyn wees om soek deur en toegang, maar die makliker manier om dit te doen is dat ons eintlik kan skep 'n struktuur bekend as 'n hash tafel waar ons hash. Ons loop al ons sleutels deur 'n hash funksie, 'n vergelyking, wat draai hulle almal in 'n soort van 'n waarde wat dan kan ons slaan op in wese 'n verskeidenheid van geskakelde lys. En so hier, as ons wou om Engelse woorde te slaan, ons kon potensieel net, ek doen nie weet, draai al die eerste letters in 'n soort van 'n aantal. En so, byvoorbeeld, as ek wou A tot sinoniem met apple-- wees of met die indeks van 0, en B sinoniem met 1 te wees, kan ons 26 inskrywings wat kan net stoor al die letters van die alfabet dat ons sal begin met. En dan kan ons ' appel op die indeks van 0. Ons kan piesang het by die indeks van 1, spanspek by die indeks van 2, en so aan en so voort. En dus as ek wou om te soek my hash tafel en toegang appel, Ek weet appel begin met 'n A, en ek weet presies dat dit moet wees en die hash tafel by indeks 0 omdat van die funksie voorheen toegeken. So ek weet nie, ons is 'n gebruiker program waar jy sal aangekla word arbitrarily-- nie arbitrêr, met die probeer om denkend dink goeie vergelykings in staat wees om te versprei uit al jou waardes in 'n manier wat hulle kan maklik toegang dit later met soos 'n vergelyking dat jy, jouself, te leer ken. So in die sin as ek wou om te gaan na mango, weet ek, o, dit begin met m. Dit moet by die indeks van 12. Ek hoef nie te soek deur enigiets. Ek weet exactly-- ek kon net gaan die indeks van 12 en trek dat uit. Almal duidelik hoe 'n funksie hash tafel se werk? Dit is soort van net 'n meer komplekse skikking. Dit is al wat dit is. OK. So ek dink ons ​​loop in hierdie kwessie van wat gebeur as jy meer dinge wat gee jou dieselfde indeks? So sê ons funksie, al is dit gedoen het, was dat die eerste letter en draai dit in 'n onderskeie 0 deur 25 indeks. Dit is heeltemal fyn, indien jy het net een van elk. Maar die tweede jy begin met meer, is jy gaan hê wat 'n botsing genoem. So as ek probeer om in te voeg in 'n hash begrawe tafel wat reeds piesang op dit, wat gaan gebeur wanneer jy probeer om in te voeg dit? Slegte dinge omdat piesang reeds binne die indeks bestaan wat jy wil om dit te stoor in. Berry soort is soos, ah, wat moet ek doen? Ek weet nie waar om te gaan. Hoe kan ek hierdie los? En so julle ouens sal soort sien ons doen dit moeilike ding waar ons kan soort van eintlik skep geskakelde lys in ons skikkings. En so het die maklikste manier om te dink oor hierdie, al hash tabel is 'n verskeidenheid van geskakelde lyste. En so, in die sin dat, jy het hierdie pragtige verskeidenheid van wenke, en dan elke wyser in wat waarde, in die indeks, kan eintlik verwys na ander dinge. En so het jy al hierdie afsonderlike kettings af kom een ​​groot verskeidenheid. En so hier, as ek wou berry voeg, Ek weet nie, OK, ek gaan om insette dit deur my hash funksie. Ek gaan om te eindig met die indeks van 1, en dan gaan ek in staat wees om net 'n kleiner subset van hierdie reuse 140,000 woord woordeboek. En dan kan ek net kyk deur 1/26 van daardie. En so kan ek net voeg berry voor of na piesang in hierdie geval? Na, reg? En so gaan jy wil voeg hierdie node na piesang, en so gaan jy voeg aan die stert van die geskakelde lys. Ek gaan om terug te gaan hierdie vorige skyfie, sodat jy kan sien hoe ouens hash funksie werk. So hash funksie is hierdie vergelyking dat jy 'n soort van jou insette deur na kry wat indeks jy wil dit na toewys. En so, in hierdie voorbeeld, al wat ons wou om te doen, was om die eerste brief, draai wat in 'n indeks, dan sal ons kan stoor wat in ons hash funksie. Al wat ons hier doen, is ons omskepping van die eerste brief. So keykey [0] is net die eerste letter van watter string ons het nie, ons verby in. Ons omskakeling wat na die boonste en ons trek deur hoofletters A, so al wat doen gee ons 'n aantal waarop ons ons waardes hash op. En dan gaan ons terugkeer hash modulus grootte. Wees baie, baie versigtig want, teoreties, hier jou hash waarde kan wees oneindig. Dit kon net gaan op en op en op. Dit kan regtig 'n paar, regtig groot waarde, maar omdat jou hash tafel wat jy gemaak het net 26 indekse, jy wil om seker te maak jou modulusing sodat jy nie run-- dit is dieselfde ding as jou queue-- sodat jy nie afloop van die onderkant van jou hash funksie. Jy wil dit om te draai terug op dieselfde manier in [onhoorbaar] wanneer jy moes soos 'n baie, baie groot brief jy wou nie dat net loop af die einde. Dieselfde ding hier, wil jy om seker te maak dit nie afloop van die einde deur die wikkel om na die top van die tafel. So dit is net 'n baie eenvoudige hash funksie. Al wat gedoen het, was die eerste letter van wat ook al ons insette was en draai wat in 'n indeks wat ons kon in ons hash tafel. Ja, en so soos ek gesê het, die manier waarop ons botsings te los in ons hash tabelle word met, wat ons noem, chaining. So as jy probeer om in te voeg verskeie woorde wat begin met die dieselfde ding, jy gaan een hash waarde het. Avokado en appel, as jy het voer dit deur ons hash funksie, gaan jy die gee dieselfde nommer, die aantal 0. En so het die manier waarop ons los dit dat ons kan eintlik soort van hulle te skakel saam via geskakelde lyste. En so in hierdie sin, julle ouens kan sien soort hoe data strukture wat ons het al voorheen die opstel soos 'n rosyntjie geskakelde lys soort saam kan kom in een. En dan kan jy ver te skep meer doeltreffende data strukture wat kan groter hoeveelhede hanteer data, wat dinamiese grootte afhangende op jou behoeftes. Almal duidelik? Almal soort duidelik op wat hier gebeur? As ek wou insert-- wat is 'n vrugte wat begin met, ek weet nie, B, behalwe berry, piesang. GEHOOR: Blackberry. ANDI Peng: Blackberry, Blackberry. Waar kom blackberry gaan hier? Wel, ons het eintlik nie gesorteer hierdie nie, maar teoreties as ons wou dit hê in alfabetiese volgorde, waar moet BlackBerry gaan? GEHOOR: [onhoorbaar] ANDI Peng: Presies, na hier, reg? Maar aangesien dit is baie moeilik om reorder-- Ek dink dit is aan julle. Julle kan heeltemal implementeer wat jy wil. Die meer doeltreffende manier van hierdie dalk doen sou wees om te sorteer jou gekoppelde lys in alfabetiese volgorde, en so wanneer jy invoeging dinge wat jy wil om seker te wees om hulle te voeg in alfabetiese volgorde sodat dan wanneer jy probeer om hulle te soek, jy hoef nie alles te deurkruis. Jy weet presies waar dit is, en dit is makliker. Maar as jy soort van het dinge lukraak afgewissel, jy nog gaan hê om dit anyways deurkruis. En so as ek wou net voeg BlackBerry hier en ek wou om te soek na dit weet ek, o, BlackBerry moet begin met die indeks van 1, so ek weet onmiddellik net soek op 1. En dan kan ek soort van deurkruis die geskakelde lys totdat ek kry Blackberry, en then-- ja? GEHOOR: As jy probeer om create-- Ek dink dit is soos 'n baie eenvoudige hash funksie. En as ons wou doen verskeie lae van daardie wil, OK, ons wil skei in soos al die alfabetiese letters en dan weer na 'n ander stel graag alfabetiese letters in daardie, Ons sit soos 'n hash tafel binne 'n hash tafel, of soos 'n funksie binne 'n funksie? Of is that-- ANDI Peng: So jou hash function-- jou hash tafel kan so groot wees as jy dit wil hê. So in hierdie sin, het ek gedink dit was baie maklik, baie eenvoudig vir my om net soort gebaseer op die letters van die eerste woord. En so is daar net 26 opsies. Ek kan net 26 opsies uit 0-25, want hulle kan net begin van A tot Z. Maar as jy wou om by te voeg, miskien, meer kompleksiteit of vinniger te hardloop tyd om jou hash tafel, jy absoluut kan allerhande dinge te doen. Jy kan jou eie te maak vergelyking wat gee jou meer verspreiding in jou woorde, dan wanneer jy soek, dit gaan vinniger. Dit is heeltemal aan jou ouens hoe jy wil om te implementeer nie. Dink aan dit as net emmers. As ek wou hê 26 emmers, ek gaan dinge in die emmers te sorteer. Maar ek gaan 'n klomp het dinge in elke emmer, so as jy wil om dit te maak vinniger en meer doeltreffende, laat my 'n honderd emmers. Maar dan moet jy om uit te vind 'n manier om dinge te sorteer sodat hulle in die regte emmer hulle behoort te wees in. Maar dan wanneer jy eintlik wil om te kyk na die emmer, dit is 'n baie vinniger, want daar is minder dinge in elke emmer. En so, ja, dit is eintlik die truuk vir julle in pset5 is dat jy sal wees uitgedaag om net te skep alles wat die mees doeltreffende funksie wat jy kan dink om te wees in staat wees om op te slaan en gaan hierdie waardes. Heeltemal aan julle ouens maar jy wil om dit te doen, maar dit is 'n baie goeie punt. Dat die soort van logika wat jy wil begin dink oor is, wel, hoekom nie ek nie meer emmers. En dan moet ek soek minder dinge, en dan miskien is ek 'n ander hash funksie. Ja, daar is 'n baie maniere om dit te doen pset, sommige is vinniger as ander. Ek is heeltemal gaan net sien hoe vinnige was die vinnigste julle sal in staat wees om jou funksies om te werk. OK, almal goed op aaneenskakeling en hash tabelle? Dit is eintlik soos 'n baie eenvoudige konsep as jy daaroor dink. Al wat dit is, is alles wat skei u insette is in emmers, sorteer hulle, en dan soek die lyste wat daar in verband met. Koel. Alle reg, nou het ons 'n ander soort van data struktuur wat is bekend as 'n boom. Kom ons gaan op en praat oor drieë wat duidelik verskillende, maar in dieselfde kategorie. Wese, al 'n boom is in plaas organiseer data in die lineêre manier dat 'n hash tafel does-- jy weet, is dit 'n top en 'n onderkant en dan sal jy soort skakel af van it-- n boom het 'n top wat jy die wortel noem, en dan is dit het blare al rondom dit. En so al wat jy hier het is net die top node wat verwys na ander nodes dat punte meer nodes, en so aan en so voort. En so moet jy net verdeel takke. Dit is net 'n ander manier van organisering data, en omdat ons noem dit 'n boom, julle ouens just-- dit is net gemodelleer uit om te kyk soos 'n boom. Dit is hoekom ons noem dit bome. Hash tafel lyk soos 'n tafel. 'N boom lyk net soos 'n boom. Al wat dit is, is 'n afsonderlike manier van organisering nodes afhangende van wat jou behoeftes is. So jy het 'n wortel en dan moet jy die blare. Die manier wat ons kan veral dink oor dit is 'n binêre boom 'n binêre boom is net 'n spesifieke tipe van 'n boom waar elke knoop net punte om op max, twee ander nodes. En so hier het jy duidelike het simmetrie in jou boom wat maak dit makliker om te soort van kyk op watter waardes jy want dan is jy het altyd 'n links of 'n reg. Daar is nooit soos 'n links derde van links of 'n vierde van links. Dis net jy het 'n linker en 'n reg en jy kan soek een van die twee. En so hoekom is dit nuttig? Die manier waarop dit is bruikbaar is as jy op soek is om te soek deur waardes, reg? Eerder as die implementering van binêre soek in 'n fout skikking, as jy wou in staat wees om nodes voeg en neem nodes weg by wil en ook die behoud van die search vermoëns van binêre soek. So op hierdie manier, ons is soort van tricking-- onthou wanneer ons gesê geskakelde lyste kan nie binêre soek? Ons soort van die skep van 'n datastruktuur dat truuks wat in werkende. En so, want gekoppel lyste is lineêre, hulle het net 'n skakel een na die ander. Ons kan soort van het ander soort van wysers daardie punt om verskillende nodes wat ons kan help met die soektog. En so hier, as ek wou 'n binêre soekboom, Ek weet dat my middel as 55. Ek gaan net om te skep wat as my middel, as my wortel, en dan gaan ek het waardes spin af van dit. So hier, as ek gaan om te soek na die waarde van 66, kan ek begin by 55. Dit is 66 groter as 55? Ja, dit is nie, so ek weet ek moe soek i n die regte wyser van hierdie boom. Ek gaan na 77. OK, is 66 minder as of groter as 77? Dit is minder as, sodat jy weet, o, wat aan die linkerkant node wees. En so hier is ons soort van die behoud van al die groot dinge oor skikkings, so soos dinamiese resizing voorwerpe, wat in staat wees om in te voeg en te verwyder word nie, sonder om te bekommer oor die vaste bedrag van die ruimte. Ons het nog steeds al te bewaar daardie wonderlike dinge terwyl dit ook in staat is om die behoud van teken en soek tyd van binêre soek dat ons voorheen net in staat wees om 'n frase te kry. Cool data struktuur, soort komplekse te implementeer, die knoop. Soos jy kan sien, al is dit is die struct van die node is dat jy 'n links en 'n reg wyser. Dit is al wat dit is. So eerder as om net met 'n x of 'n vorige. Jy het 'n linker-of die reg, en dan jy kan soort skakel hulle saam maar jy so verkies. OK, ons is eintlik gaan net 'n paar minute. So ons gaan hier terug te gaan. Soos ek gesê het voorheen, Ek soort van verduidelik die logika agter hoe ons sou soek deur middel van hierdie. Ons gaan om te probeer pseudocoding dit uit te sien as ons soort kan aansoek doen die dieselfde logika van binêre soek om 'n ander tipe van data-struktuur. As jy ouens wil neem soos 'n paar minute om net te dink oor hierdie. OK. Alle reg, ek gaan eintlik net gee jy nie the--, ons oor die pseudokode sal praat eerste. So nie almal wil om 'n steek op te gee wat die eerste ding wat jy wil doen wanneer jy begin soek is? As ons soek die waarde van 66, wat is die eerste ding wat ons wil doen as ons wil binêre soek hierdie boom? GEHOOR: Jy wil na regs kyk en kyk links en sien [onhoorbaar] groter aantal. ANDI Peng: Ja, presies. So jy gaan om te kyk na jou wortel. Daar is baie maniere wat jy kan noem dit jou ouers node mense sê. Ek hou daarvan om te sê, want die wortel dit is soos die wortel van die boom. Jy gaan om te kyk na jou wortel node, en jy is gaan om te sien is 66 groter as of minder as 55. En as dit is groter as, wel, dit is groter as, waar ons wil om te kyk? Waar wil ons soek nou, reg? Ons wil die soek regter helfte van die boom. So ons het, gerieflik, 'n wyser wat verwys na die reg. En so kan ons dan stel ons nuwe wortel te wees 77. Ons kan net gaan na waar die wyser wys. Wel, o, hier ons begin op 77, en ons kan net doen dit rekursief weer en weer. Op hierdie manier, jy soort van 'n funksie. Jy het 'n manier dat jy soek kan net herhaal oor en oor en oor, afhangende van waar jy wil om te kyk totdat jy uiteindelik kry om die waarde dat jy soek. Maak sin? Ek is op die punt om te wys jy die werklike kode, en dit is 'n baie van die kode. Geen behoefte om freak uit. Ons sal praat deur dit. Eintlik, no. Dit was net pseudokode. OK, dit was net die pseudokode, wat is 'n bietjie kompleks, maar dit is heeltemal fyn. Almal volgende saam hier? As die wortel is van nul, terugkeer valse want dit beteken jy hoef nie eens iets het daar. As wortel N is die waarde, so as dit gebeur met die een wat jy soek by wees, dan is jy gaan om ware terugkeer want jy weet jy dit gevind. Maar as die waarde minder as wortel van N, jy is gaan aan die linkerkant soek kind of links blaar, alles wat jy wil om dit te noem. En as die waarde is groter as wortel, jy gaan die regte boom soek, dan net die funksie hardloop deur 'n soektog weer. En as die wortel is van nul, dat die beteken jy aan die einde bereik het? Dit beteken dat jy het geen meer meer blare te soek, dan weet jy, o, ek dink dit is nie hier want nadat ek kyk deur die hele ding en dit is nie hier nie, dit mag dalk net nie hier wees nie. Maak dit sin om almal? So dit is soos binêre soek behoud die vermoëns van geskakelde lyste. Cool, en so die tweede tipe datastruktuur julle ouens kan probeer om die uitvoering van jou pset, jy het net een metode te kies. Maar miskien 'n alternatiewe metode om die hash tafel is wat ons 'n Trie noem. Al wat 'n Trie is 'n spesifieke tipe boom wat het waardes wat na ander waardes. So in plaas van om 'n binêre boom in die sin dat slegs een ding kan wys twee kan jy een ding punt om baie, baie dinge. Jy het in wese skikkings binnekant van wat jy slaan wysers wat na ander skikkings. So die knoop van hoe ons sou 'n Trie definieer is ons wil 'n te hê Boole, c woord, reg? So die knoop is Boole soos ware of vals, eerste van alles aan die hoof van dat skikking, is dit 'n woord? Tweedens, wil jy wenke het om ongeag die res van hulle is. 'N bietjie kompleks, 'n bietjie abstrakte, maar Ek sal wat dit alles beteken verduidelik. So hier, by die top, as jy het 'n verskeidenheid verklaar reeds 'n knoop waar jy 'n Boole waarde gestoor aan die voorkant wat vertel jy is dit 'n woord? Is dit nie 'n woord? En dan moet jy die res van jou skikking wat eintlik slaan al die moontlikhede van wat dit kan wees. So, byvoorbeeld, soos by die top jy die eerste ding wat waar of sê valse, ja of nee, dit is 'n woord. En dan moet jy 0 deur 26 van die letters wat jy kan stoor. As ek wou hier soek vir kolf, ek gaan na die top en ek kyk vir B. Ek B vind in my skikking, en so ek weet, OK, is B 'n woord? B is nie 'n woord, so dus Ek moet soek hou. Ek gaan van B, en ek kyk na die wyser dat B dui op en ek sien 'n ander verskeidenheid van inligting, dieselfde struktuur wat ons voorheen gehad het. En here-- oh, die volgende brief [onhoorbaar] is A. So ons kyk in daardie skikking. Ons vind die agtste waarde en dan kyk ons ​​om te sien, o, hey, is dat 'n woord, is B-A 'n woord? Dit is nie 'n woord. Ons het om te hou soek. En so dan kyk ons ​​na waar die wyser van 'n punte, en dit dui op 'n ander manier in wat ons het meer waarde gestoor. En uiteindelik, kry ons B-A-T, wat is 'n woord. En so het die volgende keer jy kyk, jy gaan dat die tjek van, ja het, hierdie Boole-funksie is waar. En so in die sin is ons soort van 'n boom met skikkings. So dan kan jy soort soek down. Eerder as 'n funksie en hashing toeken waardes gekoppel lys jy kan net implementeer Trie dat downwords soek. Regtig, regtig ingewikkeld dinge. Nie maklik om te dink oor, want ek is soos ' spoeg so baie data strukture uit na jou, maar doen almal soort verstaan ​​hoe die logika van hierdie werk? OK, cool. So B-A-T, en dan jy gaan soek. Die volgende keer wat jy gaan om te sien, o, hey, dit is waar, dus ek weet dit moet 'n woord te wees. Dieselfde ding vir dieretuin. So hier is die ding nou, as ons wou soek dieretuin, reg nou, tans dieretuin is nie 'n woord in ons woordeboek want soos julle kan sien, die eerste plek dat ons 'n Boole terugkeer waar is aan die einde van zoom. Ons het Z-O-O-M. En so hier het ons nie eintlik die woord, dieretuin, in ons woordeboek want dit boks is nie nagegaan. So die rekenaar nie weet dat dieretuin is 'n woord omdat die pad wat ons het gestoor is, slegs 'n zoom hier het eintlik 'n Boolese waarde dit is gedraai waar. So as ons wil hê dat die plaas woord dieretuin, in ons woordeboek, hoe sou ons gaan oor om dit te doen? Wat moet ons doen om seker te maak ons rekenaar weet dat Z-O-O is 'n woord en nie die eerste woord is Z-O-O-M? GEHOOR: [onhoorbaar] ANDI Peng: Presies, ons wil seker maak dat dit hier dat Boole waarde is nagegaan af dat dit is waar. Z-O-O, dan gaan ons seker maak dat, sodat ons presies weet, hey, dieretuin is 'n woord. Ek gaan die vertel rekenaar wat dit is 'n woord so dat wanneer die rekenaar tjeks, dit weet dat dieretuin is 'n woord. Want onthou al hierdie data strukture, dit is baie maklik vir ons om te sê, o, kolf is 'n woord. Zoo is 'n woord. Klik is 'n woord. Maar wanneer jy die bou van dit, die rekenaar het geen idee nie. So moet jy dit presies vertel op watter punt is dit 'n woord? Op watter punt is dit nie 'n woord? En op watter punt het ek nodig het om dinge te soek, en op watter punt moet ek volgende gaan? Almal duidelik van dit? Koel. En so dan kom die probleem van hoe sou ons gaan invoeging iets dit is eintlik nie daar? So laat ons net sê ons wil voeg die woord, bad, in ons Trie. As julle ouens kan sien soos wat tans Al wat ons nou het, is B-A-T, en hierdie nuwe data struktuur Daar was 'n pint wat wys na nul, want ons aanvaar dat O, daar is geen woorde na B-A-T, Daarom het ons nodig om te hou met dinge daarna T. Maar die probleem ontstaan ​​as ons wat jy doen wil 'n woord wat kom na het die T se. As jy 'n bad, jy is gaan 'n H reg wil hê. En so het die manier waarop ons gaan om dit te doen is ons gaan 'n aparte node skep. Ons is nie net die bedrag toeken geheue vir hierdie nuwe skikking, en ons gaan pointers toewys. Ons gaan die toewys H, Eerste van alles, dit null, ons gaan om ontslae te raak van. Ons gaan hê die H punt afwaarts. As ons sien 'n H, ons wil dit om te gaan na 'n ander plek. In hier, kan ons dan seker ja af. As ons 'n H getref nadat die T, o, dan weet ons dat dit 'n woord. Die Boole gaan ware terugkeer. Almal duidelik oor hoe dit gebeur het? OK. So in wese, al hierdie data strukture dat ons oor vandag gegaan het, ek het regtig, regtig vinnig gegaan oor hulle en nie in te veel detail, en dit is OK. Sodra jy begin geknoei met dit, sal jy dop van waar al die wysers is, wat gaan aan in jou data strukture, ensovoorts. Hulle sal baie nuttig wees, en dit is aan jou ouens heeltemal uit te vind hoe jy wil om dinge te implementeer. En so pset4 van 5-- O, dit is verkeerd. Pset5 is spelfoute. Soos ek gesê het, gaan jy, sodra weer, laai bronkode van ons. Daar gaan drie hoof wees dinge wat jy sal laai. Jy sal woordeboeke aflaai, kers, en tekste. Al daardie dinge is, is óf woordeboeke woorde dat ons wil hê jy om te kyk of toets van die inligting dat ons wil hê jy moet check spel. En so het die woordeboeke ons gee jou gaan om jou werklike woorde wat ons wil gee jy een of ander manier te stoor in 'n manier wat meer doeltreffend as 'n skikking. En dan is die tekste gaan wees wat ons is vra jou om te spel om seker te al die woorde daar werklike woorde. En so het die drie blokke van programme wat ons sal gee jou is dictionary.c genoem, dictionary.h en speller.c. En so sal die hele dictionary.c doen is wat jy gevra word om te implementeer. Dit laai woorde. Dit spel tjeks hulle, en dit maak seker dat alles behoorlik ingesit. diction.h is net 'n biblioteek lêer wat verklaar al die funksies. En speller.c, ons gaan om jou te gee. Jy hoef nie aan enige van dit te verander. Alle speller.c doen is neem, vragte dit gaan die spoed van dit, toets die maatstaf van soos hoe vinnig jy kan om dinge te doen. Dit is 'n speller. Net doen nie gemors met dit, maar maak seker jy verstaan ​​wat dit doen. Ons gebruik 'n funksie genoem getrusage dat toets van die prestasie van jou spel checker. Al wat dit doen is basies die toets van die tyd van alles wat in jou woordeboek, so maak seker jy verstaan ​​dit. Wees versigtig om nie gemors met dit of anders sal dinge nie behoorlik uit te voer. En die grootste deel van hierdie uitdaging is vir julle ouens om werklik dictionary.c verander. Ons gaan om jou te gee 140,000 woorde in 'n woordeboek. Ons gaan jou 'n SMS te gee lêer wat daardie woorde het, en ons wil hê jy moet in staat wees om te organiseer hulle in 'n hash tafel of 'n Trie want as ons vra om te spel check-- dink as jy spel kontrole soos Homer se Odyssey. Dit is soos die groot, groot toets. Stel jou voor dat elke enkele woord wat jy het om te kyk deur 'n verskeidenheid van 140,000 waardes. Dit sou vir ewig vir jou rekenaar uit te voer. Dit is hoekom ons wil hê dat ons organiseer data in meer doeltreffende data strukture soos 'n hash tafel of 'n Trie. En dan moet jy ouens kan soort wanneer jy toegang soek dinge makliker en vinniger. En so wees versigtig om botsings te los. Jy gaan 'n klomp te kry woorde van wat begin met A. Jy gaan 'n klomp woorde kry wat begin met B. Tot jy ouens hoe jy wil om dit te los. Miskien is daar meer doeltreffende hash funksie as net die eerste letter van iets, en so dit is aan jou ouens soort doen wat jy wil. Miskien het jy wil byvoeg al die letters saam. Miskien wil jy graag doen vreemde dinge om die aantal letters rekening wat ook al. Tot julle hoe jy wil om dit te doen. As jy wil 'n hash tafel doen, as jy wil 'n Trie probeer, heeltemal aan jou. Ek sal julle voor te waarsku van die tyd dat die Trie is tipies 'n bietjie meer moeilik net omdat daar 'n baie meer wenke om tred te hou. Maar heeltemal aan julle. Dit is veel meer doeltreffende in die meeste gevalle. Jy wil regtig in staat wees om aan te hou spoor van al jou wenke. Soos dieselfde ding doen dat ek hier doen. Wanneer jy probeer om in te voeg waardes in 'n hash tafel of te verwyder, maak seker dat jy regtig dop van waar alles is omdat dit is baie maklik vir as ek probeer om in te voeg soos die woord, Andy. Laat ons net sê dit is 'n werklike woord die woord, Andy, in 'n reuse lys van A woorde. As ek net gebeur om toewys 'n wyser verkeerd is, oops, daar gaan die geheel van die res van my geskakelde lys. Nou is die enigste woord wat ek het, is Andy, en nou al die ander woorde in die woordeboek het verlore gegaan. En so jy wil om seker te maak jy hou van al jou wenke of anders wat jy gaan kry groot probleme in jou kode. Teken dinge uit versigtig stap vir stap. Dit maak dit 'n baie makliker om te dink. En laastens, wil jy in staat wees om toets jou prestasie van jou program op die groot bord. As jy ouens neem 'n kyk na CS50 nou, ons het wat is bekend as die groot bord. Dit is die telkaart van die vinnigste spellingscontrole keer oor al CS50 nou, ek dink die top 10 soos Soms dink ek agt van hulle is die personeel. Ons wil regtig julle ouens om ons te klop. Almal van ons het probeer om te implementeer die vinnigste kode as moontlik. Ons wil julle ouens om te probeer om uit te daag ons en implementeer vinniger as ons almal kan. En so dit is regtig die eerste keer dat ons vra julle om 'n pset doen jy kan regtig nie in watter metode jy wil. Ek sê altyd, dit is meer verwant om 'n werklike oplossing, reg? Ek sê, hey, ek het jou nodig om dit te doen. Bou 'n program wat dit doen vir my. Doen dit egter jy wil. Ek weet net dat ek wil om te vas. Dit is jou uitdaging vir hierdie week. Julle ouens, ons gaan om jou 'n taak gee. Ons gaan jou 'n uitdaging gee. En dan is dit aan julle ouens heeltemal net uitvind wat is die vinnigste en mees doeltreffende manier om dit te implementeer. Ja? GEHOOR: Is ons toegelaat om as wou vinniger maniere te vors om hash tabelle aanlyn te doen, kan ons doen dit en noem kode iemand anders se? ANDI Peng: Ja, heeltemal fyn. So as jy lees die ouens spec, is daar 'n lyn in die spec dat jy ouens sê is heeltemal gratis om hash navorsing funksies op wat is 'n paar van die vinniger hash funksies om dinge loop deur as Solank as wat jy daardie kode noem. So 'n paar mense reeds uitgepluis vinnige maniere doen speltoetsers, van 'n vinnige maniere van die stoor inligting. Heeltemal aan julle ouens as jy wil net neem, reg? Maak seker dat jy met verwysing na. Die uitdaging hier regtig dat ons probeer om te toets maak seker dat jy weet jou pad om wenke. So ver as jy die uitvoering van die werklike hash funksie en kom met soos die wiskunde om dit te doen, julle ouens kan navorsing wat ookal metodes aanlyn jy ouens wil. Ja? GEHOOR: Kan ons noem net deur die gebruik van die [onhoorbaar]? ANDI Peng: Ja. Jy kan net in jou kommentaar, jy kan noem soos, ag, geneem uit yada, yada, yada, hash funksie. Enigiemand enige vrae? Ons het eintlik breezed deur artikel vandag. Ek sal hier wees om vrae te beantwoord as well. Ook, soos ek gesê het, kantoor uur vanaand en môre. Die spec hierdie week is eintlik super maklik en super kort om te lees. Ek sou voorstel om 'n blik, net lees deur die geheel van dit. En Zamyla eintlik loop jy deur elk van die funksies wat jy nodig het om te implementeer, en dit is dus baie, baie duidelik hoe om alles te doen. Net om seker te maak jy dop van wysers. Dit is 'n baie uitdagende pset. Dit is nie 'n uitdaging, want soos, O, die konsepte is soveel meer moeilik, of jy het om te leer soveel nuwe sintaksis die pad wat jy gedoen het vir die laaste pset. Dit is moeilik, want pset daar is so baie wysers, en dan is dit baie, baie maklik om te keer jy het 'n fout in jou kode nie in staat wees om uit te vind waar daardie fout is. En so volledig en volslae geloof in julle ouens in staat wees om ons [onhoorbaar] klop spellings. Ek het eintlik nie enige skriftelike myn nie, maar ek is op die punt om my te skryf. Dus, terwyl jy skryf joune is, sal ek skryf myne. Ek gaan om te probeer om te maak my vinniger as joune. Ons sal sien wat die vinnigste een. En ja, ek sal al sien julle ouens hier op Dinsdag. Ek sal 'n soort soos 'n pset werkswinkel loop. Al die afdelings van hierdie week is pset werkswinkels, so julle ouens het baie van die geleenthede vir hulp, kantoorure soos altyd, en Ek het regtig uitsien na lees al jou ouens se kode. Ek het vasvrae hier as jy ouens wil kom kry wat. Dit is al.