[Speel van musiek] Spreker 1: Alle reg. Almal terug na afdeling verwelkom. Ek hoop julle almal is suksesvol verhaal van jou quiz van verlede week. Ek weet dit is 'n bietjie mal by tye. Soos ek voor sê, as jy binne die standaard afwyking, nie regtig nie bekommerd daaroor, veral vir 'n minder gemaklike afdeling. Dit is oor waar jy moet wees. As jy het 'n groot, dan awesome. Kudos aan jou. En as jy voel jy moet 'n bietjie meer hulp, asseblief voel vry om te bereik uit enige van die TFS. Ons is almal hier om te help. 

Dit is hoekom ons leer. Dit is hoekom ek hier is elke Maandag vir jou ouens en by kantoorure op Donderdae. So voel asseblief vry om my te laat weet As jy bekommerd is oor enigiets of as daar iets op die toets dat jy regtig wil, aan te spreek. 

So het die agenda vir vandag alles oor data strukture. Sommige van hierdie is net gaan om net te wees te kry wat jy vertroud met hierdie. Jy mag nie ooit implementeer hulle in hierdie klas. Sommige van hulle sal jy, soos vir jou speller pset. 

Jy sal jou keuse hê tussen hash tabelle en drieë gedruk. So ons sal beslis gaan word oor diegene. Dit gaan beslis meer van aard te wees van 'n hoë vlak artikel vandag, al is, want daar is baie van hulle, en as ons het in die implementering besonderhede op al hierdie, sou ons nie selfs deur geskakelde lyste en miskien 'n bietjie van 'n gemors tafels. 

So met my dra. Ons is nie van plan om te doen soveel kodering hierdie tyd. As jy enige vrae het oor dit of jy wil sien dit geïmplementeer of probeer om dit vir jouself, Ek beslis aanbeveel gaan study.cs50.net, wat het voorbeelde van al hierdie. Dit sal my kragpunte het met die notas wat ons geneig is om te word, sowel as 'n paar programme oefeninge, veral vir dinge soos gekoppel lyste en binêre bome stapels en leidrade. So bietjie meer hoë vlak, wat kan lekker vir julle wees. 

So met dit, sal ons begin. En ook, yes-- vasvrae. Ek dink die meeste van julle wat in my artikel jou vasvrae, maar iemand kom of ander rede doen nie, hulle is reg hier in die voorkant. 

So gekoppel lyste. Ek weet van hierdie soort gaan om terug voor jou quiz. Dit was die week voor dat ons geleer het oor hierdie. Maar in hierdie geval, sal ons net gaan 'n bietjie meer in diepte. 

So hoekom kan ons kies 'n gekoppel lys oor 'n skikking? Wat onderskei hulle? Ja? 

Publiek: Jy kan uit te brei 'n gekoppelde lys teenoor 'n skikking se vaste grootte. Spreker 1: Right. 'N skikking het vaste grootte, terwyl 'n gekoppel lys het 'n veranderlike grootte. So, as ons nie weet hoe veel ons wil op te slaan, 'n geskakelde lys gee ons 'n groot manier om dit te doen, want ons kan net voeg op 'n ander knoop en voeg op 'n ander knoop en voeg op 'n ander knoop. Maar wat kan 'n trade-off wees? Is daar iemand onthou die trade-off tussen skikkings en geskakelde lyste? Mmhmm? 

Publiek: Jy moet gaan deur al die pad deur die geskakelde lys vind 'n element in 'n lys. In 'n skikking, kan jy vind net 'n element. 

Spreker 1: Right. So met arrays-- 

Publiek: [onhoorbaar]. 

Spreker 1: Met skikkings, ons het wat genoem ewekansige toegang. Beteken dat as ons wil hê wat ooit die vyfde punt van 'n lys of die vyfde punt van ons skikking, kan ons net gryp dit. As dit is 'n geskakelde lys, ons het te Itereer deur, reg? So toegang tot 'n element in 'n skikking is konstante tyd, terwyl met 'n geskakelde lys sou dit waarskynlik lineêre tyd, want miskien ons element is al die pad aan die einde. Ons het om te soek deur alles. So met al die data strukture wat ons gaan word spandeer 'n bietjie meer tyd op, Wat is die plus punte en negatiewe. Wanneer sal ons wil Gebruik een oor die ander? En dit is soort van die groter ding om weg te neem. 

Dus het ons hier die definisie van 'n knoop. Dit is soos 'n element in ons geskakelde lys, reg? So ons is almal vertroud met ons typedef gelas, wat het ons oor in hersiening laaste keer. Dit was basies net die skep van ander data tipe wat ons kan gebruik. 

En in hierdie geval, dit is 'n paar node wat sal 'n heelgetal in hou. En dan wat is die tweede deel hier? Iemand? 

Publiek: [onhoorbaar]. 

Spreker 1: Ja. Dit is 'n verwysing na die volgende knoop. So dit moet eintlik up wees hier. Dit is 'n aanduiding van die tipe knoop na die volgende ding. En dit is wat hulle sluit ons node. Cool. 

Alle reg, so met 'n soektog, soos ons was net sê voor die hand, as jy gaan soek deur, jy moet eintlik Itereer deur jou geskakelde lys. So as ons kyk vir die aantal 9, sal ons begin by ons kop en dat wys ons aan die begin van ons geskakelde lys, reg? En ons sê, OK, doen dit knoop bevat die nommer 9? Geen? 

Alle reg, gaan na die volgende een. Dit volg. Bevat dit die nommer 9? No. Volg die volgende een. 

So ons moet eintlik Itereer deur ons geskakelde lys. Ons kan nie net gaan direk na die plek waar 9 is. En as julle eintlik wil sien 'n paar pseudo-kode daar. Ons het 'n paar soek funksie hier wat neem in-- wat dit neem om in? Wat dink jy? So maklik. Wat is dit? Publiek: [onhoorbaar]. Spreker 1: Die getal wat ons soek. Reg? En wat sou dit ooreen? Dit is 'n verwysing na? 

GEHOOR: 'n knoop. 

Spreker 1: 'n knoop aan die lys dat ons is op soek na, reg? So ons het 'n paar knope is wyser hier. Dit is 'n punt wat gaan eintlik Itereer deur ons lys. Ons stel dit gelyk aan die lys want dit is net om dit te stel gelyk aan die begin van ons geskakelde lys. 

En terwyl dit is nie NULL, terwyl het ons nog dinge in ons lys, kyk om te sien of dit knoop het die getal wat ons soek. Terugkeer waar. Andersins, werk dit, reg? 

As dit is NULL, ons verlaat ons while lus en stuur vals want dit beteken dat ons nog nie gevind nie. Nie almal kry hoe dit werk? OK. 

So met plasing, jy het drie verskillende maniere. Jy kan prefix, kan jy voeg en jy kan voeg in verskillende soorte. In hierdie geval, ons is gaan 'n plaas jou te doen. Is daar iemand wat weet hoe om die drie gevalle kan verskil? 

So plaas jou beteken dat jy dit aan die voorkant van jou lys. So dit sou beteken dat maak nie saak wat jou node is, maak nie saak wat die waarde is, gaan jy om dit te sit hier voor, OK? Dit gaan die eerste wees element in jou lys. 

As jy dit voeg, gaan dit om te gaan na die agterkant van jou lys. En voeg in verskillende soorte beteken dat jy gaan eintlik sit in die plek waar dit hou jou geskakelde lys gesorteer. Weereens, hoe jy gebruik diegene en wanneer jy gebruik sal hulle wissel, afhangende van jou saak. As dit nie nodig het om te word gesorteer, plaas geneig te wees wat die meeste mense gebruik omdat jy dit nie doen nie het om te gaan deur die hele lys die einde dit toe te voeg aan te vind, reg? Jy kan net plak dit reg. 

So sal ons gaan deur 'n voeg 1 nou. So een ding wat ek gaan raai op hierdie pset is om dinge te trek uit, soos altyd. Dit is baie belangrik dat jy werk jou wenke in die korrekte volgorde want as jy hulle werk effens buite orde, jy gaan om te eindig verloor dele van jou lys. 

So byvoorbeeld, in hierdie geval, ons is vertel die hoof net punt 1. As ons net dit doen sonder om hierdie 1, Ons het geen idee wat 1 moet nou omdat ons verloor het wat die hoof verwys na. So een ding om te onthou Wanneer jy 'n plaas jou doen is om te red wat die hoof punte na die eerste, dan toewys dit, en dan werk wat jou nuwe node behoort te wys. In hierdie geval, dit is een manier om dit te doen nie. 

So as ons gedoen het dit op hierdie manier waar ons net oorgeplaas kop, Ons het basies ons verloor hele lys, reg? Een manier om dit te doen, is 1 punt te hê volgende, en dan het die hoof punt 1. Of jy kan doen soort van soos die tydelike stoor, wat ek het gepraat oor. 

Maar gehou indiensneming jou wysers in die korrekte volgorde gaan baie, baie wees belangrik vir hierdie pset. Andersins, jy gaan 'n gemors te hê tafel of 'n drie wat net gaan wees slegs 'n deel van die woorde wat jy wil en dan you're-- Mmhmm? Publiek: Wat was die tydelike stoor ding wat jy praat? Spreker 1: die tydelike stoor. So basies 'n ander manier waarop jy dit kan doen is slaan die hoof van iets, soos stoor dit die tydelike veranderlike. Toewys om dit te 1 en dan werk 1 te wys aan alles wat kop gebruik om aan te dui. Hierdie manier is natuurlik meer elegante, want jy nie 'n tydelike waarde het nie, maar net die aanbied van 'n ander manier om dit te doen nie. En ons werklik doen het sommige kode vir hierdie. So vir gekoppelde lys ons eintlik 'n paar kode. So voeg hier, is dit en tik. So dit gaan dit op die kop. 

So die eerste ding wat jy nodig het om te skep jou nuwe node, natuurlik, en kyk vir NULL. Altyd goed. En dan moet jy die waardes te wys. Wanneer jy 'n nuwe knoop, jy Ek weet nie wat dit is wys om die volgende, sodat jy wil om dit te inisialiseer te null. As dit nie die einde wys na iets anders, word dit oorgeplaas en dit is goed. As dit is die eerste ding wat in die lys is, is dit nodig om aan te dui omdat null dit is die einde van die lys. 

So dan is dit te plaas, hier sien ons ons is die toeken van die volgende waarde van ons node te wees wat hoof is, en dit is wat ons hier het. Dit is wat ons nou net gedoen het. En dan is ons toeken hoof punt ons nuwe knoop, want onthou, nuwe is 'n verwysing na 'n knoop, en dit is presies wat die hoof is. Dit is presies die rede waarom ons hierdie pyl accessor. Cool? Mmhmm? 

Publiek: Het ons te inisialiseer nuwe langs eerste van nul, of kan ons net inisialiseer aan die hoof? 

Spreker 1: New volgende moet NULL te begin want jy weet nie waar dit gaan wees. Ook, dit is soort van net soos 'n paradigma. Jy stel dit gelyk aan NULL net te maak seker dat al jou basisse word gedek voordat jy enige bestemming sodat jy altyd gewaarborg dat dit sal word verwys na 'n spesifieke waarde versus soos 'n gemors waarde. Omdat, ja, ons ken nuwe volgende outomaties, maar dit is meer net soos 'n goeie praktyk om dit te inisialiseer Op dié manier en dan toewys. 

OK, so dubbeld gekoppel lyste nou. Wat dink ons? Wat is anders met dubbel gekoppel lyste? 

So in ons geskakelde lyste, kan ons slegs in een rigting beweeg, reg? Ons het net die volgende. Ons kan net vorentoe gaan. 

Met 'n dubbel gekoppel lys Ons kan ook agteruit beweeg. So ons het nie net die getal wat ons wil op te slaan, ons het waar dit verwys na die volgende en waar ons net vandaan kom. So dit maak voorsiening vir 'n beter traversal. 

So dubbel gekoppel knope, baie soortgelyk, reg? Enigste verskil is nou ons 'n volgende en 'n vorige. Dit is die enigste verskil. 

So as ons die prefix of append-- ons nie enige kode vir die up here-- maar as jy was om te probeer en plaas dit, die belangrikste ding is wat jy nodig het om te maak seker dat jy die toeken beide jou vorige en jou volgende wyser korrek. So in hierdie geval, sou jy nie net langs inisialiseer, jy inisialiseer vorige. As ons aan die hoof van die lys, ons nie net maak kop gelyk nuwe, maar ons nuwe vorige indien wys op die kop, reg? 

Dit is die enigste verskil. En as jy meer oefening wil dit met geskakelde lyste met inbring, met die verwydering, met insetsel in 'n verskeidenheid lys check study.cs50.net. Daar is 'n klomp van die groot oefeninge. Ek raai hulle. Ek wens ons tyd om te gaan deur middel van hulle het maar daar is 'n baie data strukture te kry deur. 

OK, so hash tabelle. Dit is waarskynlik die mees nuttige bietjie vir jou pset hier, want jy gaan wees implementering van een van hierdie, of 'n drie. Ek het regtig soos hash tabelle. Hulle is redelik cool. 

So basies wat gebeur, is 'n gemors tafel is wanneer ons regtig nodig spoedige plasing, skrap, en soek. Dit is die dinge wat ons is prioritiseer in 'n gemors tafel. Hulle kan 'n bietjie groot, maar soos ons sal sien met drieë, daar is dinge wat veel groter. 

Maar basies, al 'n gemors tabel is 'n hash funksie wat vir jou vertel wat emmer elke te sit van jou data, elkeen van jou elemente in. 'N eenvoudige manier om te dink van 'n hash tafel is dat dit net emmers van dinge, reg? So wanneer jy sorteer dinge deur soos die eerste letter van die naam, dit is soort van soos 'n hash tafel. 

So as ek by die groep julle ouens is in groepe van wie se naam begin met 'n hier, of wie se verjaarsdag is in Januarie, Februarie, Maart, wat ook al, dit is effektief skep van 'n hash tafel. Dit is net die skep van emmers wat jou elemente sorteer in sodat jy dit makliker kan vind. So op hierdie manier wanneer ek nodig het een van jou te vind, Ek hoef nie te soek deur elkeen van julle name. Ek kan wees, o, ek weet dat Danielle se verjaarsdag is in-- Publiek: --April. Spreker 1: April. So ek sien in my April emmer, en met 'n bietjie geluk, sy die enigste een in daar sal wees en my tyd was konstant in daardie sin, terwyl as ek het om te kyk deur 'n hele klomp van die mense, dit gaan veel langer neem. So hash tabelle is regtig net emmers. Maklike manier om te dink van hulle. 

So 'n baie belangrike ding oor 'n gemors tabel is 'n hash funksie. So die dinge wat ek net gepraat het, soos jou eerste letter van jou naam of jou verjaarsdag maand, hierdie is idees wat regtig ooreen met 'n hash funksie. Dit is net 'n manier om te besluit watter emmer jy is element gaan in, OK? So vir hierdie pset, kan jy kyk op pretty much enige hash funksie wat jy wil. 

Hoef nie jou eie wees. Daar is 'n paar regtig cool kinders uit daar wat dit doen allerhande mal wiskunde. En as jy wil om jou te maak speltoetser super vinnig, Ek sou beslis kyk na een van daardie. 

Maar daar is ook die eenvoudige mense, soos bereken Die som van die woorde, soos elke letter het 'n aantal. Bereken die som. Dit bepaal die emmer. Hulle het ook die maklike kinders wat is net soos al die A's hier, al die B is hier. Enige een van daardie. 

Eintlik is dit net vir jou vertel wat verskeidenheid indeks jou element moet gaan in. Net die besluit van die bucket-- dit is alles 'n hash funksie is. So hier het ons 'n voorbeeld wat net die eerste letter van die string dat ek net praat. 

So jy het 'n paar hash dit is net die eerste letter van jou string minus A, wat julle sal gee getal tussen 0 en 25. En wat jy wil doen, is seker te maak dat dit verteenwoordig die grootte van jou hash table-- hoeveel emmers is daar. Met baie van hierdie hash funksies, hulle is gaan word terugkeer waardes wat kan wees ver bo die aantal emmers dat jy eintlik ' in jou hash tafel, sodat jy nodig het om te maak seker en mod deur diegene. Andersins, dit gaan om te sê, O ja, moet dit in die emmer 5000 wees maar jy het net 30 emmers in jou hash tafel. En natuurlik, ons almal weet dit is gaan lei tot 'n paar mal foute. So maak seker dat jy mod deur die grootte van jou hash tafel. Cool. So botsings. Is almal goeie so ver? Mmhmm? 

Publiek: Hoekom sou dit terug so 'n massiewe waarde? 

Spreker 1: Afhangende van die algoritme dat jou hash funksie gebruik. Sommige van hulle sal doen gek vermenigvuldiging. En dit is alles oor die manier waarop 'n eweredige verspreiding, sodat hulle nie 'n paar baie gek dinge soms. Dit is al. Enigiets anders? OK. 

So botsings. Basies, soos ek vroeër gesê het, in die beste geval, enige emmer Ek kyk na is gaan een ding om te hê, so ek het nie om te kyk na alles, reg? Ek weet ook dit is daar of dit is nie, en dit is wat ons regtig wil. Maar as ons tienduisende data punte en minder as dat die getal emmers, ons gaan te hê botsings waar uiteindelik iets gaan hê om te eindig in 'n emmer wat reeds 'n element. 

So die vraag is, wat doen ons in so 'n geval? Wat doen ons? Ons het reeds iets daar te hê? Moenie net gooi ons dit uit? 

No. Ons het beide van hulle te hou. So die manier waarop ons tipies doen is wat? Wat is die data struktuur Ons het net gepraat oor? Publiek: Gekoppel lys. Spreker 1: 'n geskakelde lys. So nou, in plaas van elk van hierdie emmers net met een element, dit gaan 'n gekoppelde lys van te bevat die elemente wat hashed is in dit. OK, nie almal soort van daardie idee? Omdat ons nie kan het 'n verskeidenheid want ons weet nie hoe baie dinge gaan wees daar. 'N geskakelde lys ons toelaat om te het net die presiese aantal wat word hashed in die emmer, reg? 

So lineêre indringende is basies hierdie idea-- dit is een manier om te gaan met 'n botsing. Wat jy kan doen is as in hierdie geval, was Berry hashed in 1 en ons het reeds iets daar, jy moet net hou totdat vind jy 'n leë slot. Dit is een manier om dit te hanteer. Die ander manier te hanteer dit is met wat ons nou net called-- die gekoppelde lys aaneenskakeling genoem. 

So hierdie idee werk as jou hash tafel wat jy dink is baie groter as datastel of as jy wil om te probeer en verminder chaining totdat dit absoluut noodsaaklik is. So een ding is lineêre indringende natuurlik beteken dat jou hash funksie is nie so nuttig want jy gaan om te eindig met behulp van jou hash funksie, om na 'n punt, jy Lineêre ondersoek af te 'n plek wat beskikbaar is. Maar nou, natuurlik, enigiets anders wat eindig daar, jy gaan te hê soek nog verder af. 

En daar is 'n baie meer soek koste wat gaan in die skryf van 'n element in jou hash tafel nou, reg? En nou wanneer jy gaan en probeer en vind Berry weer jy gaan om dit te hash, en dit gaan om te sê, O, kyk in die emmer 1, en dit is nie van plan om in die emmer 1, sodat jy gaan hê om oor te steek deur die res van hierdie. So dit is soms nuttig, maar in die meeste gevalle, ons gaan om te sê dat aaneenskakeling is wat jy wil doen. 

So het ons gepraat oor hierdie vroeër. Ek het 'n bietjie voor my. Maar aaneenskakeling is basies dat elke emmer in jou hash tafel is net 'n geskakelde lys. 

So 'n ander manier, of meer tegniese manier om te dink van 'n hash tafel is dat dit net 'n skikking van geskakelde lyste, wat wanneer jy jou woordeboek wil skryf en jy probeer om dit te laai, dink aan dit as 'n verskeidenheid van geskakelde lyste maak dit baie makliker vir jou te begin. 

Publiek: So hash tafel 'n voorafbepaalde grootte, soos 'n [onhoorbaar] emmers? 

Spreker 1: Right. So het dit 'n sekere aantal emmers dat jy determine-- wat julle moet voel vry om te speel met. Dit kan wees pretty cool om te sien wat gebeur as jy jou aantal emmers verander. Maar ja, dit het 'n stel aantal emmers. Wat kan jy aan te pas as baie elemente as wat jy nodig het is hierdie aparte aaneenskakeling waar jy gekoppel lyste in elke emmer. Dit beteken dat jou hash tafel presies die grootte wat jy nodig het om dit te wees, reg? Dit is die hele punt van geskakelde lyste. Cool. 

Sodat almal OK daar? Alle regte. Ag. Wat het gebeur? Nou regtig. Raai iemand se dood vir my. 

OK ons gaan om te gaan in drieë, wat is 'n bietjie mal. Ek hou van hash tabelle. Ek dink dit is regtig cool. Drieë is koel, ook. 

So nie almal onthou wat 'n drie is? Jy moes gegaan het oor dit kortliks in lesing? Onthou jy soort van hoe dit werk? Publiek: Ek is net knik dat ons nie gaan oor dit. Spreker 1: Ons gaan oor dit. OK, ons is regtig gaan om te gaan oor dit nou is wat ons sê. 

Publiek: Dit is vir 'n herwinning boom. 

Spreker 1: Ja. Dit is 'n herwinning boom. Awesome. So een ding om hier te let is dat ons is op soek na individuele karakters hier, reg? 

So voordat ons hash funksie, ons is op soek na die woorde as 'n geheel, en nou is ons meer soek by die karakters, reg? So ons het Maxwell hier en Mendel. So basies 'n try-- 'n manier om te dink oor hierdie is dat elke vlak hier is 'n skikking van die briewe. So is dit jou wortel node hier, reg? Dit het al die karakters van die alfabet vir die begin van elke woord. 

En wat jy wil doen, is sê, OK, ons het 'n paar M woord. Ons gaan om te kyk vir Maxwell, so ons gaan na M. En M punte na 'n hele ander 'n skikking waar elke woord, solank as wat daar is 'n woord wat 'n as die tweede brief, so lank as wat daar is 'n woord wat het B as die tweede brief, dit sal 'n wyser het gaan 'n volgende reeks. 

Daar is waarskynlik nie 'n woord wat LP iets, so by die P posisie in dié skikking, sou dit net wees NULL. Dit sou sê, OK, daar is geen woord wat M gevolg deur 'n P, OK? So as ons dink oor dit, elke een van hierdie kleiner dinge is eintlik een van hierdie groot skikkings van 'n deur Z. So, wat kan een van die dinge wees dit is soort van 'n nadeel van 'n probeer? 

GEHOOR: 'n baie van die geheue. 

Spreker 1: Dit is 'n ton van die geheue, reg? Elkeen van hierdie blokke hier verteenwoordig 26 ruimtes, 26 element skikking. So drieë kry ongelooflik ruimte swaar. 

Maar hulle is baie vinnig. So ongelooflik vinnig, maar werklik ruimte ondoeltreffend. Soort het om uit te vind uit watter een jy wil. Dit is werklik 'n koel vir jou pset, maar hulle doen neem 'n baie van die geheue, sodat jy handel nie. Ja? 

Publiek: Sou dit moontlik wees om 'n drie gedruk en dan Sodra jy al die data in dit wat jy need-- Ek weet nie of dit sal sin maak. Ek is om ontslae te raak van al die NULL karakters, maar dan sou jy nie in staat wees om na die indeks them-- 

Spreker 1: Jy moet nog steeds hulle. 

Publiek: - op dieselfde manier elke keer. Spreker 1: Ja. Jy moet die NULL karakters te laat jy weet as daar nie 'n woord daar. Ben het jy iets wat jy wil hê? OK. Alle reg, so ons gaan 'n bietjie meer gaan in die tegniese detail agter 'n probeer en werk deur middel van 'n voorbeeld. 

OK, so dit is dieselfde ding. Terwyl dit in 'n geskakelde lys, ons vernaamste soort of-- wat is die woord wat ek wil hê? - soos die bou blok was 'n knoop. In 'n drie, ons het ook 'n knoop, maar dit is verskillend gedefinieer. 

So ons het 'n paar Bool wat verteenwoordig of 'n woord eintlik bestaan ​​by hierdie plek, en dan Ons het 'n paar verskeidenheid here-- of liewer, Dit is 'n verwysing na 'n verskeidenheid van 27 karakters. En dit is vir, in hierdie geval, is hierdie 27-- Ek is seker almal van julle is soos, wag, daar is 26 letters in die alfabet. Hoekom het ons 27? 

So, afhangende van die manier waarop jy die uitvoering van hierdie, Dit is van 'n pset wat toegelaat vir apostrofes. So dit is waarom die ekstra een. Jy sal ook in sommige gevalle die nul terminator is ingesluit as een van die karakters dat dit toegelaat word om te wees, en dit is hoe hulle gaan om te sien of dit is die einde van die woord. As jy belangstel, check Kevin se video op study.cs50, sowel as Wikipedia het 'n paar goeie hulpbronne daar. 

Maar ons gaan om te gaan deur net soort van hoe jy deur middel van 'n drie kan werk As jy een gegee. So ons het 'n super eenvoudige een hier wat het die woorde "kolf" en "zoom" in hulle. En as ons sien hier, hierdie klein ruimte hier verteenwoordig ons Bool wat sê, ja, dit is 'n woord. En dan moet dit ons skikkings van die karakters, reg? 

So gaan ons deur te gaan vind "kolf" in hierdie drie. So begin by die top, reg? En ons weet dat b ooreenstem met die tweede indeks, is die tweede element in hierdie skikking, omdat a en b. So ongeveer die tweede een. 

En dit sê, OK, koel, volg wat in die volgende skikking, want as ons onthou, dit is nie dat elkeen van hierdie eintlik bevat die element. Elkeen van hierdie skikkings bevat 'n wyser, reg? Dit is 'n belangrike onderskeid te maak. 

Ek weet dit gaan be-- drieë is werklik moeilik om te kry op die eerste keer, sodat selfs wanneer dit is die tweede of derde keer en dit is nog steeds soort van oënskynlike moeilik, Ek belowe as jy gaan kyk die kort môre weer, dit sal waarskynlik 'n baie meer sin. Dit neem baie om te verteer. Ek het nog soms is soos, wag, wat is 'n probeer? Hoe gebruik ek dit? 

So het ons in hierdie geval B sal hê, wat is ons tweede indeks. As ons gehad het, sê, c of d of enige ander brief, ons moet dit terug na die indeks te karteer van ons skikking wat wat ooreenstem met. So ons sal neem soos rchar en ons het net trek uit 'n dit te karteer in 0-25. Almal goeie hoe ons kaart ons karakters? OK. 

So gaan ons na die tweede een, en ons sien dat, ja, dit is nie NULL. Ons kan aanbeweeg na die volgende reeks. So gaan ons na hierdie volgende skikking hier. 

En ons sê, OK, nou is ons nodig het om te kyk of 'n is hier. Is 'n nul of is dit eintlik vorentoe te beweeg? So 'n werklikheid beweeg vorentoe in hierdie reeks. En ons sê, OK, t is ons laaste brief. So gaan ons na die t op die indeks. En dan vorentoe beweeg ons want daar is 'n ander een. En hierdie een sê basies dat, ja, dit sê dat daar is 'n woord here-- dat as jy hierdie pad, jy het aangekom 'n woord wat ons weet, is "kolf." Ja? 

Publiek: Is dit standaard te hê wat as indeks 0 en dan 'n soort op 1 of aan die einde? 

Spreker 1: No. So, as ons terugkyk na ons verklaring hier, dit is 'n Bool, so dit is sy eie element in jou knoop. So dit is nie deel van die skikking. Cool. So wanneer ons klaar is met ons woorde en ons is op hierdie skikking, wat ons wil doen is nie 'n tjek vir is dit 'n woord. En in hierdie geval, sou dit wel terugkeer. 

So op daardie noot, ons weet dat "dieretuin" - ons weet as mense wat "dieretuin" is 'n woord, reg? Maar probeer om hier sou sê, nee, dit is nie. En dit sal sê dat omdat ons het nie aangewys as 'n woord hier. Selfs al het ons kan deurkruis deur hierdie skikking, hierdie drie sou sê dat, nee, dieretuin is nie in jou woordeboek want ons het nie aangewese dit so. 

So 'n manier om te doen that-- O, jammer, hierdie een. So in hierdie geval, "dieretuin" is nie 'n woord, maar dit is in ons probeer. Maar in hierdie een, sê ons dit wil hê voer die woord "bad," wat gebeur is ons volg through-- b, a, t. Ons is in hierdie skikking, en ons gaan om te soek na h. 

In hierdie geval, toe ons kyk na die wyser op h, dit is wys om te NULL, OK? So tensy dit uitdruklik verwys na 'n skikking, jy aanvaar dat al die verwysings in hierdie skikking verwys na null. So in hierdie geval, is h wys te null sodat ons kan niks doen nie, so sal dit ook terug vals is, "bad" is nie hier nie. So nou is ons eintlik gaan om te gaan deur middel van hoe sou ons eintlik sê dat "dieretuin" is in ons probeer. Hoe voeg ons nie "dieretuin" in ons probeer? So in die dieselfde manier as wat ons begin met ons geskakelde lys, ons begin by die wortel. Wanneer jy twyfel, begin by die wortel van hierdie dinge. 

En ons sal sê, OK, z. Z bestaan ​​in hierdie, en dit doen nie. So jy beweeg na jou volgende skikking, OK? En dan op die volgende een, ons sê, OK, nie o bestaan ​​nie? Dit doen nie. Dit het weer eens. 

En so op ons volgende een, het ons gesê: OK, "dieretuin" bestaan ​​reeds hier. Al wat ons moet doen, is ingestel om hierdie gelyke waar, dat daar is 'n woord daar. As jy alles gevolg het tot voor daardie punt, dit is 'n woord, sodat net stel dit gelyk aan sulke. Ja? 

Publiek: doen dit dan beteken dat "ba" is 'n woord ook? 

Spreker 1: No. So in hierdie geval, "ba" Ons sou kry hier, sal ons sê, is dit 'n woord, en dit sou nog steeds nie. OK? Mmhmm? 

Publiek: So as jy is om dit 'n woord en jy sê ja, dan is dit sal bevat om te gaan na m? 

Spreker 1: So dit het te doen with-- jy laai dit in. Jy sê: "dieretuin" is 'n woord. Wanneer jy na check-- soos, sê wat jy wil sê, beteken "dieretuin" bestaan ​​in hierdie woordeboek? Jy net gaan soek vir "dieretuin" en dan kyk om te sien of dit is 'n woord. Jy gaan nooit te beweeg deur na m, want dit is nie wat jy soek. 

So as ons eintlik wou voeg "bad" in hierdie drie, sou ons dieselfde ding doen as ons gedoen het met "dieretuin" behalwe ons sien dat wanneer ons probeer en kry om te h, beteken dit nie bestaan ​​nie. So jy kan dink van hierdie as om 'n nuwe node by te voeg in 'n geskakelde lys, sodat ons sal moet 'n ander te voeg een van hierdie skikkings, soos so. En dan wat ons doen, is ons net soos die h element van hierdie reeks verwys na hierdie. 

En dan wat sou ons hier wil doen? Voeg dit gelyk aan ware want dit is 'n woord. Cool. Ek weet nie. Drieë is nie die mees opwindende. Glo my, ek weet. 

So een ding om te besef met drieë, Ek het gesê, hulle is baie effektief. So het ons hulle gesien neem 'n ton van die ruimte. Hulle is soort van verwarrend. So hoekom sou ons ooit gebruik? Ons gebruik hierdie, want hulle is ongelooflik doeltreffend. 

So as jy ooit op soek 'n woord, is jy net begrens deur die lengte van die woord. So as jy op soek is na 'n woord wat 'n lengte van vyf, jy net ooit gaan hê maak op die meeste vyf vergelykings, OK? So dit maak dit eintlik 'n konstante. Soos inplanting en soek is basies konstante tyd. 

So as jy ooit kan kry iets in konstante tyd, dit is so goed soos dit kry. Jy kan nie beter as kry konstante tyd vir hierdie dinge. So dit is een van die groot pluspunte van die drieë. 

Maar dit is 'n baie ruimte. So jy soort van moet besluit Wat is meer belangrik vir jou. En op vandag se rekenaars, die ruimte wat 'n drie kan tot Miskien raak nie julle het, maar miskien jy te doen het met iets wat ver, ver meer dinge, en 'n drie is net nie redelik. Ja? 

Publiek: Wag, sodat jy het 26 letters in elke enkele een? 

Spreker 1: Mmhmm. Ja, jy het 26. Jy het 'n paar is woord merker en dan jy het 26 wenke in elke een. En hulle point-- 

Publiek: En elke 26, hulle het elkeen 26? 

Spreker 1: Ja. En dit is hoekom, as jy kan sien, dit uit redelik vinnig. Alle regte. So ons gaan om te kry in die bome, wat Ek voel is makliker en sal waarskynlik 'n mooi klein uitstel uit drieë daar. So hopelik die meeste van julle het 'n boom gesien het. Nie soos die mooi kinders buite, wat ek Ek weet nie of iemand het onlangs in die buitelug. Ek het appel pluk hierdie naweek, en oh my gosh, dit was pragtig. Ek het nie blare weet kon kyk wat mooi. 

So dit is net 'n boom, reg? Dit is net 'n paar knoop, en dit dui op 'n klomp van die ander nodes. As jy hier sien, is dit soort van 'n herhalende tema. Knope wat verwys na nodes is 'n soort van die essensie van baie data strukture. Dit hang net af hoe ons het hulle na mekaar en hoe ons deurkruis deur hulle en hoe ons voeg dinge wat bepaal hul verskillende eienskappe. 

So net 'n paar terme, wat ek voorheen gebruik het. So wortel is alles wat by die heel boonste. dit is waar ons altyd begin. Jy kan dink dat dit as die hoof ook. Maar vir bome, is ons geneig om te verwys na dit as die wortel. 

Enigiets aan die onderkant here-- by die baie, baie bottom-- is van mening blare. So dit gaan saam met die hele boom ding, reg? Blare is op die rand van jou boom. 

En dan het ons ook 'n paar terme te praat oor knope in verhouding aan mekaar. So het ons 'n ouer, kinders, en broers en susters. So in hierdie geval, 3 is die ouer van 5, 6 en 7. So het die ouer wat ookal een stap bo alles wat jy is verwys na, sodat net soos 'n stamboom. Hopelik is dit al 'n bietjie bietjie meer intuïtief as die drieë. 

Broers en susters enige wat dieselfde ouer, reg? Hulle is op dieselfde vlak hier. En dan, soos ek was sê, kinders is net wat is 'n stap onder die knoop in die vraag, OK? Cool. So 'n binêre boom. Kan iemand 'n raaiskoot waag op een van die eienskappe van die tweeledige boom? 

Publiek: Max twee blare. 

Spreker 1: Right. So maksimum van twee blare. So in hierdie een voor, ons het hierdie een dat drie, maar in 'n binêre boom, jy het 'n maksimum van twee kinders per ouer, reg? Daar is nog 'n interessante kenmerk. Is daar iemand wat weet dat? Binêre boom. 

So 'n binêre boom sal alles hê op the-- hierdie een is nie sorted-- maar in 'n gesorteer binêre boom, alles op die regte groter is as die ouer, en alles aan die linkerkant minder is as die ouer. En wat is 'n toets vraag voor, so goed om te weet. So die manier waarop ons definieer dit, Weereens, ons het nog 'n knoop. Dit lyk baie soortgelyk aan wat? Dubbel 

Publiek: Gekoppel lyste 

Spreker 1: 'n dubbel gekoppel lys, reg? So as ons die plek van hierdie met vorige en die volgende, dit sou 'n dubbel gekoppel lys wees. Maar in hierdie geval, het ons eintlik het links en regs en dit is dit. Andersins, is dit presies dieselfde. Ons het nog steeds die element jy soek, en jy moet net twee wysers gaan net die volgende. Ja, so binêre soek boom. As ons sien, alles op die hier is groter than-- of alles onmiddellik aan die regterkant hier is groter as alles hier is minder as. 

So as ons om te soek deur dit moet kyk baie naby aan binêre soek hier, reg? Behalwe in plaas van om te kyk teen die helfte van die skikking, Ons is net op soek na die linker kant of die regterkant van die boom. So raak dit 'n bietjie makliker, dink ek. 

So as jou wortel is NULL, natuurlik is dit net vals. En as dit is daar, natuurlik, dit is waar. As dit is minder as ons soek die linkerkant. As dit is groter as, Ons soek die reg. Dit is presies soos binêre soek, net 'n ander datastruktuur wat ons gebruik. In plaas van 'n skikking, dit is net 'n binêre boom. 

OK, stapels. En ook, dit lyk asof ons dalk 'n bietjie van die tyd. As ons dit doen, ek is gelukkig om te gaan oor enige van hierdie weer. OK, so stapels. Is daar iemand onthou wat stacks-- enige eienskappe van 'n stapel? 

OK, so die meeste van ons, dink ek, eet in die eetkamer halls-- soveel as wat ons mag nie graag. Maar natuurlik, kan jy dink van 'n stapel letterlik net so 'n stapel van bak of 'n stapel van dinge. En wat is belangrik om te besef is dat dit something-- die kenmerkende dat ons noem dit deur- is LIFO. Is daar iemand wat weet wat dit staan ​​vir? Mmhmm? 

Publiek: Laaste in, eerste uit. 

Spreker 1: Right, die laaste in, eerste uit. So as ons weet, as ons stapel dinge up, die maklikste ding om te gryp off-- en miskien die enigste ding wat ons kan gryp af as ons stapel is 'n groot enough-- is dat top element. Dus, wat is op last-- soos ons hier sien, alles is gedruk op die meeste recently-- is gaan na die eerste wees ding wat ons pop af, OK? 

So wat ons hier het is ' 'n ander typedef struct. Dit is regtig net graag 'n crash kursus in die data struktuur, so daar is 'n baie gegooi by julle. Ek weet nie. So nog 'n struct. Yay vir strukture. 

En in hierdie geval, dit is 'n paar wyser om 'n skikking wat 'n kapasiteit. Sodat hierdie verteenwoordig ons stapel hier, soos ons werklike verskeidenheid dit is hou ons elemente. En dan is hier ons het 'n paar groot. 

En tipies, wat jy wil hou spoor van hoe groot jou stapel want hoe dit gaan te laat jy moet doen is as jy weet wat die grootte, dit laat jou te sê, OK, ek by kapasiteit? Kan ek iets byvoeg? En dit ook vertel waar die top van jou stapel so jy weet wat jy eintlik kan opstyg. En dit is eintlik gaan 'n bietjie meer duidelik. 

So vir stoot, een ding, as jy ooit druk te implementeer, as ek net sê, jou stapel het 'n beperkte grootte, reg? Ons verskeidenheid het 'n paar kapasiteit. Dit is 'n skikking. Dit is 'n vaste grootte, sodat ons nodig het om te seker te maak dat ons nie meer om in ons verskeidenheid as wat ons eintlik ruimte vir. 

So wanneer jy skep 'n druk funksie, die eerste ding wat jy doen is om te sê, OK, ek het ruimte in my stapel? Want as ek dit nie doen nie, jammer, Ek kan nie slaan jou element. As ek dit doen, dan is jy wil op te slaan dit aan die bokant van die stapel, reg? 

En dit is hoekom ons spoor van ons grootte te hou. As ons nie tred hou van ons grootte nie, Ons weet nie waar om dit te sit. Ons weet nie hoe baie dinge in ons verskeidenheid reeds. Soos duidelik daar is maniere dat miskien jy kan dit doen. Jy kan alles inisialiseer te null en dan gaan vir die jongste NULL, maar 'n baie makliker ding is net om te sê, OK, hou van grootte. Soos ek weet ek het vier elemente in my skikking, so die volgende ding wat ons aan, ons is gaan om te slaan op indeks 4. En dan, natuurlik, beteken dit dat jy het suksesvol gestoot iets op jou stapel, jy wil die grootte te verhoog sodat jy weet waar jy is so dat jy meer dinge kan druk op. 

So as ons probeer om te pop iets uit die stapel, wat dalk die eerste ding wees wat ons wil om te kyk vir? Jy probeer om te neem iets uit jou stapel. Is jy seker daar is iets in jou stapel? No. So, wat sou ons wil om te kyk? 

Publiek: [onhoorbaar]. Spreker 1: Check vir die grootte? Grootte. So ons wil om te kyk om te sien of ons grootte is groter as 0, OK? En as dit is, dan wil ons te verminder ons grootte deur 0 en terugkeer nie. Hoekom? 

In die eerste een wat ons was stoot, ons stoot dit op die grootte en dan opgedateer grootte. In hierdie geval, ons decrementing grootte en dan neem dit af, pluk dit van ons verskeidenheid. Hoekom kan ons dit doen? So as ek een ding op my stapel, Wat sou my grootte op daardie punt wees? 1. 

En waar is element 1 gestoor? Op watter indeks? Publiek: 0. Spreker 1: 0. So in hierdie geval, ons altyd nodig om te maak sure-- in plaas van die terugkeer grootte minus 1, want ons weet dat ons element is gaan op 1 minder geberg word alles wat ons grootte is, is hierdie net sorg nie. Dit is 'n bietjie meer elegante manier. En ons het net decrement ons grootte en dan terug grootte. Mmhmm? 

Publiek: Ek dink net in die algemeen, hoekom sou hierdie data struktuur voordelig wees? 

Spreker 1: Dit hang af van jou konteks. So vir 'n paar van die teorie, As jy werk with-- OK, Laat my sien of daar is 'n voordelige een wat voordelig is vir meer as buite CS. Met stapels, enige tyd wat jy nodig het spoor van iets te hou wat is die mees onlangs bygevoeg is wanneer jy gaan om te wil 'n stapel te gebruik. 

En ek kan nie dink aan 'n goeie voorbeeld van wat nou. Maar wanneer die mees onlangse ding is vir jou die belangrikste, dit is wanneer 'n stapel gaan nuttig te wees. Ek probeer om te dink as daar is 'n goeie een vir hierdie. As ek dink aan 'n goeie voorbeeld in die volgende 20 minute, ek sal beslis vir jou sê. 

Maar algehele, as daar enigiets is, soos ek gesê het die meeste, waar die meeste onlangse is baie belangrik, dis waar 'n stapel kom in die spel. Terwyl toue is soort van die teenoorgestelde. En al die klein honde. Is dit nie die groot, reg? Ek voel soos ek moet net 'n bunny video reg in die middel van die artikel vir julle want dit is 'n intense afdeling. 

So 'n tou. Basies 'n tou is soos 'n lyn. Julle ek is seker gebruik hierdie alledaagse, net soos in ons eetsale. So ons het om te gaan in en kry ons bak, ek is seker jy het om te wag in lyn te krap of kry jou kos. 

So het die verskil hier is dat dit EIEU. So as LIFO was laaste in, eerste uit EIEU is die eerste in, eerste uit. So dit is waar wat jy sit op die eerste is jou belangrikste. So, as jy wag in 'n line-- kan jy dink as jy na gaan kry die nuwe iPhone en dit was 'n stapel waar die laaste persoon in lyn het dit die eerste keer, mense sal mekaar doodmaak. 

So EIEU, ons is almal baie bekend in die werklike wêreld hier, en dit alles het te doen met eintlik soort herskep hierdie hele lyn en toustaan ​​struktuur. So terwyl met die stapel, Ons het druk en pop. Met 'n tou, ons het enqueue en dequeue. So enqueue beteken basies sit dit op die rug, en dequeue middel neem af van die voorkant. So ons data struktuur is 'n bietjie meer ingewikkeld. Ons het 'n tweede ding om tred te hou. 

So sonder die kop, hierdie is presies 'n stapel, reg? Dit is dieselfde struktuur as 'n stapel. Die enigste ding wat anders is, is ons nou het die hoof, wat doen wat jy dink gaan om tred te hou? 

Publiek: Die eerste een. 

Spreker 1: Right, die eerste ding wat ons in. Die hoof van ons ry. Wie is die eerste in die lyn. Alle reg, so as ons dit doen enqueue. Weer, met enige van hierdie data strukture, omdat ons te doen het met 'n skikking, ons nodig het om te kyk of ons 'n ruimte. 

Dit is soort van soos vir my vertel julle ouens, as jy 'n lêer oop te maak, wat jy nodig het om te kyk vir nul. Met enige van hierdie stapels en toue, moet jy om te sien of daar is ruimte, want ons is doen met 'n vaste grootte skikking, soos ons sien here-- 0, 1 al tot 5. So wat ons doen in daardie geval is tjek om te sien of ons nog plek. Is ons grootte minder as kapasiteit? 

As dit so is, moet ons dit op te slaan op die stert en ons grootte werk. So wat kan die stert wees in hierdie geval? Dit is nie duidelik uitgeskryf. Hoe sal ons dit stoor? Wat sou die stert wees? 

So laat loop deur middel van hierdie voorbeeld. So, dit is 'n verskeidenheid van grootte 6, reg? En ons het op die oomblik, ons grootte is 5. En wanneer ons dit in, dit gaan om te gaan in die vyfde indeks, reg? So slaan op die stert. 

Nog 'n manier stert te skryf wil net wees ons opgestel by indeks van grootte, reg? Dit is die grootte 5. Volgende ding wat gaan om te gaan in 5. Cool? OK. Dit raak 'n bietjie meer ingewikkeld wanneer ons begin geknoei met die kop. Ja? 

Publiek: Beteken dit dat ons sou 'n skikking verklaar het dat was vyf elemente lang en dan is ons voeg op dit? 

Spreker 1: No. So in hierdie geval, dit is 'n stapel. Dit sou verklaar word as 'n verskeidenheid van grootte 6. En in hierdie geval, ons net een spasie links. 

OK, so een ding is in hierdie geval, as ons kop is by 0, dan moet ons net dit kan byvoeg by grootte. Maar dit raak 'n bietjie moeiliker want eintlik, het hulle het nie 'n skyfie vir hierdie, so ek gaan een te trek, want dit is nie heeltemal so eenvoudig as jy begin om ontslae te raak van die dinge. So terwyl met 'n stapel jy net ooit bekommerd te wees oor wat die grootte is wanneer jy iets toe te voeg aan, met 'n tou moet jy ook te maak seker dat jou kop is verantwoordelik vir, omdat 'n cool ding oor toue is dat as jy nie by die kapasiteit, jy kan eintlik maak dit draai om. 

OK, so een thing-- O, dit is verskriklik kryt. Een ding om te oorweeg is die geval nie. Ons sal net doen vyf. OK, so ons gaan sê die hoof is hier. Dit is 0, 1, 2, 3, 4. 

Die hoof is daar, en asseblief dinge in hulle. En ons wil iets in te voeg, reg? So die ding wat ons nodig het om te weet, is dat die kop is altyd gaan op hierdie manier te beweeg en dan loop terug rond, OK? 

So hierdie tou het ruimte, reg? Dit het ruimte in die begin, soort van die teenoorgestelde hiervan. So wat ons moet doen is om ons moet die stert te bereken. As jy weet dat jou hoof het nie beweeg nie, stert is net jou opgestel by Die indeks van die grootte. 

Maar in werklikheid, as jy met 'n tou, jou kop is waarskynlik opgedateer. So, wat jy hoef te doen is eintlik bereken die stert. So wat ons doen is om hierdie formule hier, wat ek gaan om jou te laat ouens dink oor, en dan sal ons daaroor praat. So is dit kapasiteit. 

So dit sal eintlik gee jou 'n manier om dit te doen nie. Want in hierdie geval, wat? Ons hoof is op 1, ons grootte is 4. As ons mod wat deur 5, kry ons 0, en dit is waar ons moet invoer nie. 

So dan in die volgende geval, As ons dit doen, ons sê, OK, laat ons dequeue iets. Ons dequeue hierdie. Ons neem hierdie element, reg? 

En nou is ons kop is hier wys, en ons wil by te voeg in 'n ander ding. Dit is basies die agterkant van ons lyn, reg? Toue kan draai om die skikking. Dit is een van die belangrikste verskille. Stapels, kan jy dit nie doen nie. 

Met toue, kan jy want al wat saak maak is dat jy weet wat mees onlangs bygevoeg. Want alles gaan in gevoeg word hierdie linkswaartse rigting, in hierdie geval, en dan draai rond, kan jy voortgaan om in die nuwe elemente aan die voorkant van die skikking want dit is nie regtig die voorkant van die skikking nie. Jy kan dink van die begin van die skikking as waar jou kop eintlik is. 

So hierdie formule is hoe jy bereken jou stert. Doen wat sin maak? OK. OK, dequeue, en dan julle ouens het 10 minute my enige verduidelik vrae te vra wat jy wil, want ek weet dit is gek. 

Alle reg, sodat in dieselfde way-- Ek weet nie of julle opgemerk, maar CS is al oor die patrone. Dinge is pretty much die dieselfde, net met 'n klein tweaked. So dieselfde ding hier. Ons moet kyk na as ons eintlik sien iets in ons ry, reg? Sê, OK, is ons grootte groter as 0? Cool. 

As ons dit doen, dan beweeg ons ons kop, wat is wat ek net hier gedemonstreer. Ons werk ons ​​hoof een te wees. En dan het ons decrement ons grootte en die standaard van die element. 

Daar is baie meer konkrete kode op study.cs50.net, en ek raai gaan deur dit as jy tyd het, selfs al is dit net 'n pseudo-kode. En as julle wil praat deur wat met my een op een, laat my asseblief weet. Ek sal bly wees om te wees. Data strukture, indien jy CS 124, sal jy weet dat data strukture kry baie pret en dit is net die begin. 

So ek weet dit is moeilik. Dit is OK. Ons sukkel. Ek nog steeds doen. So te veel bekommerd wees nie oor dit. 

Maar dit is basies jou crash kursus in die data strukture. Ek weet dit is 'n baie. Is daar enigiets wat ons wil om te gaan oor weer? Enigiets wat ons wil om te praat deur middel van? Ja? 

Publiek: Vir daardie voorbeeld, so die nuwe stert is by 0 oor dit? Spreker 1: Ja. Publiek: OK. So dan gaan deur, jy wil hê 1 plus 4 or-- 

Spreker 1: So jy sê, wanneer ons wil gaan doen dit weer? Publiek: Ja. So, as jy besyfering out-- waar is jy die berekening van die stert van daardie? 

Spreker 1: So het die stert was in-- Ek verander nie. So in hierdie voorbeeld hier, dit was die skikking ons kyk na, OK? Dus het ons dinge in 1, 2, 3 en 4. So het ons ons kop is gelyk aan 1 by hierdie punt, en ons grootte is gelyk aan 4 Op hierdie punt, reg? 

Julle almal is dit eens dat dit die geval is? So ons doen om die kop, plus die grootte, wat gee ons 5, en dan moet ons mod deur 5. Ons kry 0, wat vertel ons dat 0 is waar is ons stert, waar ons die ruimte. 

Publiek: Wat is 'n pet? 

Spreker 1: Die kapasiteit. Jammer. So dit is die grootte van jou skikking. Ja? 

Publiek: [onhoorbaar] voor ons terugkeer van die element? 

Spreker 1: So beweeg ons die kop of die standaard van die oomblik? So as ons beweeg een, decrement die grootte? Hou op. Ek het beslis vergeet 'n ander. Toemaar. Daar is nie 'n ander formule. Ja, sou jy wil om terug te keer die kop en dan beweeg dit terug. 

Publiek: OK, want op hierdie punt, die hoof was by 0, en dan wat jy wil om terug te keer indeks 0 en dan maak kop 1? 

Spreker 1: Right. Ek dink daar is 'n ander formule soort van soos hierdie. Ek het dit nie op die top van my kop Ek wil nie hê jy moet die verkeerde een. Maar ek dink dit is heeltemal geldig sê, OK, slaan hierdie element-- wat hoof se element is-- Trek jou grootte, beweeg jou kop oor en terugkeer wat dit ook al element is. Dit is volkome geldig. OK. Ek voel soos hierdie is nie soos die most-- jy nie gaan hier uit te loop soos, ja, ek weet drieë gedruk. Ek het dit alles. Dit is OK. Ek belowe. Maar data strukture is iets wat dit neem baie tyd om gewoond te raak aan. Waarskynlik een van die moeilikste dinge, dink ek, in die kursus. 

So dit is beslis neem herhaling en soek at-- ek het nie regtig weet gekoppel lyste totdat ek het te veel met hulle, in dieselfde manier as wat ek gedoen het nie regtig verstaan ​​wysers totdat ek het dit vir twee tot leer jaar en doen my eie psets met dit. Dit neem 'n baie van die herhaling en tyd. En uiteindelik, sal dit soort klik. 

Maar in die tussentyd, as jy 'n soort van 'n hoë vlak van begrip van wat doen dit, hul voor- en cons-- is wat ons regtig is geneig om te beklemtoon, veral in die intro kursus. Soos, hoekom sou ons gebruik 'n probeer om oor 'n skikking? Soos wat die positiewe en negatiewe van elkeen van daardie? 

En die begrip van die trade-offs tussen elk van hierdie strukture is wat is baie meer belangrik nou. Daar kan 'n gek wees vraag of twee wat gaan jou vra druk te implementeer of implementeer pop of enqueue en dequeue. Maar vir die grootste deel, met wat hoër vlak van begrip en meer van 'n intuïtiewe begrip is meer belangrik as eintlik in staat is om dit te implementeer. 

Dit sou regtig awesome as almal van julle kon uitgaan en gaan implementeer 'n drie, Maar ons verstaan ​​dit is nie noodwendig die mees redelike ding nou. Maar jy kan in jou pset, as jy wil te, en dan sal jy die praktyk kry, en dan miskien sal jy regtig verstaan ​​nie. Ja? 

Publiek: OK, so watter is ons bedoel is om te gebruik in die pset? Het ek nie een van hulle te gebruik? Spreker 1: Ja. So jy het jou keuse. Ek dink in hierdie geval, kan ons praat oor die pset 'n bietjie want ek het deur middel van hierdie. So in jou pset, moet jy jou keuse van drieë of hash tabelle. Sommige mense sal probeer en gebruik bloei filters, maar diegene tegnies nie korrek is nie. As gevolg van hul probabilistiese natuur, hulle gee vals positiewes soms. Hulle is cool kyk na, al is. Raai soek by hulle ten minste. Maar jy moet jou keuse tussen 'n hash tafel en 'n drie gedruk. En wat gaan om te wees waar jy laai in jou woordeboek. 

En jy sal nodig het om te kies jou hash funksie, wat jy nodig het om van te kies hoeveel emmers wat jy het, en dit sal wissel. Soos as jy meer emmers, miskien sal dit vinniger te hardloop. Maar miskien is jy mors baie ruimte op die manier, al is. Jy het dit om uit te vind. Mmhmm? 

Publiek: Jy het gesê voor daardie ons kan gebruik om ander hash funksies, dat ons nie hoef te 'n hash funksie? 

Spreker 1: Ja, reg. So letterlik vir jou hash funksie, soos Google "hash funksie" en kyk vir 'n paar koel kinders. Jy is nie verwag om te bou jou eie hash funksies. Mense spandeer hul verhandelings op hierdie dinge. 

So moenie bekommerd wees oor die bou van jou eie. Vind 'n aanlyn te begin. Sommige van hulle wat jy hoef te 'n bietjie te manipuleer om seker te maak terugkeer tipes ooreen en noem maar op, so in die begin, Ek sou raai die gebruik iets baie maklik dat ons dalk net hashes op die eerste brief. En dan wanneer jy dit werk, waarin 'n koeler hash funksie. Mmhmm? 

Publiek: Sou 'n probeer wees of doeltreffende, maar net harder te, like-- 

Spreker 1: So 'n drie, dink ek, is intuïtief moeilik om te implementeer maar is baie vinnig. Maar neem meer ruimte. Weereens, kan jy optimaliseer beide van diegene in verskillende maniere en daar is maniere aan- Publiek: Hoe is ons gegradeer op dit? Is dit matter-- 

Spreker 1: So jy gegradeer normale manier. Jy gaan gegradeer op die ontwerp. Ongeag hoe jy dit doen, jy wil maak seker dit is so elegant soos dit kan wees en so doeltreffend as wat dit kan wees. Maar as jy kies om 'n drie of hash tafel, so lank as dit werk, ons is gelukkig met dit. En as jy iets gebruik wat hashes op die eerste brief, dit is goed, soos miskien soos ontwerp-wyse. Ons is ook die bereiking van die punt in hierdie semester-- Ek weet nie of jy ouens noticed-- as jy pset grade weier om 'n bietjie as gevolg van die ontwerp en noem maar op, dit is heeltemal fyn. Dit is steeds op 'n punt waar jou programme kry meer ingewikkeld. Daar is meer plekke jy kan verbeter op. 

So dit is heeltemal normaal. Dit is nie dat jy doen erger op jou pset. Dit is net ons om harder op jou nou. Sodat almal die gevoel nie. Ek het net gegradeer al jou psets. Ek weet almal voel dit. 

So moenie bekommerd wees oor dit wees nie. En indien u enige vrae oor voor psets of maniere waarop jy kan verbeter, Ek probeer en kommentaar van die spesifieke plekke, maar soms is dit laat en ek moeg. Is daar enige ander dinge oor datastrukture? Ek is seker dat julle nie regtig wil om te praat oor hulle nie, maar as daar is, ek is bly om te gaan oor hulle, sowel as enigiets vanaf lesing die afgelope week of verlede week. 

Ek weet verlede week was al hersiening, so ons kan oor 'n paar hersiening oorgeslaan het van lesing. Enige ander vrae wat ek kan antwoord? OK, alles reg. Wel, jy ouens kry 15 minute vroeg. 

Ek hoop dit was semi-nuttig ten minste, en ek sal sien julle volgende week, of Donderdag kantoorure. Is daar versoeke vir snacks vir volgende week, is dit die ding? Omdat ek vandag lekkergoed vergeet. En ek het lekkergoed laaste week, maar dit was Columbus Day, so daar was soos ses mense wat het vier sakke van snoep vir hulself. Ek kan bring Starbursts weer as jy wil. Starbursts? OK, klink goed. Het jy 'n groot dag, ouens.