[Muziek] SPEAKER 1: Oké. Iedereen welkom terug naar sectie. Ik hoop dat jullie allemaal zijn succes hersteld van uw quiz van vorige week. Ik weet dat het een beetje gek soms. Zoals ik al eerder zei: als je binnen de standaardafwijking, niet echt zorgen over te maken, in het bijzonder een minder comfortabel sectie. Dat is ongeveer waar je moet zijn. Als je deed het geweldig, dan is geweldig. Kudos voor jou. En als je het gevoel dat je nodig hebt een beetje meer hulp nodig, dan kunt u voel je vrij om te komen uit voor een van de TF's. We zijn hier allemaal om te helpen. 

Dat is waarom wij onderwijzen. Dat is waarom ik hier ben elke maandag voor u jongens en op het kantoor uren op donderdag. Dus aarzel niet om mij te laten weten als u zich zorgen over iets bent of als er iets aan de quiz dat je echt wilt pakken. 

Dus de agenda voor vandaag alles over datastructuren. Sommige van deze zijn gewoon te gewoon om aan de slag u vertrouwd gemaakt met deze. Je mag nooit implementeren ze in deze klasse. Sommigen van hen je wil, net als voor uw speller pset. 

U zult uw keuze tussen hash tabellen en probeert. Dus we zullen zeker gaan over deze. Het zal zeker meer van aard zijn van een level sectie hoog vandaag, hoewel, want er zijn veel van hen, en als gingen we naar de implementatie details Op al deze, zouden we niet zelfs via gelinkte lijsten en misschien een klein beetje hash tabellen. 

Dus geduld met mij. We gaan niet te doen zoveel coderen deze tijd. Als u vragen heeft over het of je wilt zien gebeuren of probeer het zelf, Ik zeker aanraden naar study.cs50.net die heeft voorbeelden van al deze. Het zal mijn PowerPoints hebben met de notities die we de neiging om te gebruiken als ook een beetje kan programmeren oefeningen, vooral wat er zoals gelinkte lijsten en binaire bomen stacks en cues. Dus iets meer hoog niveau, dat misschien wel leuk voor jullie. 

Dus met dat, zullen we aan de slag. En ook, yes-- quizzen. Ik denk dat de meeste van jullie die in mijn deel heb je quizzen, maar iedereen komt in of andere reden niet doen, ze zijn hier in de voorkant. 

Dus gelinkte lijsten. Ik weet dat dit soort gaat om een ​​back voordat je quiz. Dat was de week voor dat we geleerd over dit. Maar in dit geval, zullen we gewoon ga een beetje meer in de diepte. 

Dus waarom zouden we kiezen voor een gelinkte lijst over een array? Wat onderscheidt hen? Ja? 

Publiek: U kunt uitbreiden van een gekoppelde lijst versus een array vaste grootte. SPEAKER 1: Recht. Een array heeft vaste afmetingen, terwijl een gelinkte lijst heeft een variabele grootte. Dus als we niet weten hoe veel we willen slaan, een gelinkte lijst geeft ons een grote manier om dat te doen, want we kunnen gewoon toevoegen ander knooppunt en toevoegen andere knoop en toevoegen ander knooppunt. Maar wat kan een trade-off zijn? Herinnert iemand zich de trade-off tussen arrays en gelinkte lijsten? Mmhmm? 

Publiek: Je moet gaan door de hele weg via de gelinkte lijst vind een element in een lijst. In een array, kunt u vind enkel een element. 

SPEAKER 1: Recht. Dus met arrays-- 

Publiek: [onverstaanbaar]. 

SPEAKER 1: Met arrays, we hebben wat heet random access. Betekent dat wat als we willen is ooit het vijfde punt van een lijst of het vijfde punt van ons array, kunnen we net pak het. Als het een gekoppelde lijst, we om door te herhalen, toch? Dus toegang tot een element in een array constant is tijd, terwijl met een gekoppelde lijst het zou lineaire tijd hoogstwaarschijnlijk want misschien onze element is helemaal aan het eind. We hebben om door middel van alles. Dus met al deze gegevens structuren gaan we worden uitgaven een beetje meer tijd op, wat zijn de plussen en negatieven. Wanneer zouden we willen Gebruik een over de ander? En dat is een soort van de groter ding om mee te nemen. 

Dus we hebben hier de definitie van een knooppunt. Het is als een element in onze gelinkte lijst, toch? Dus we zijn allemaal bekend met onze typedef structs, die gingen we dan in beoordeling laatste keer. Het was eigenlijk gewoon het creëren van een ander datatype die we konden gebruiken. 

En in dit geval, het is wat het knooppunt dat zal wat integer in te houden. En wat is dan het tweede deel hier? Anyone? 

Publiek: [onverstaanbaar]. 

SPEAKER 1: Ja. Het is een pointer naar het volgende knooppunt. Dus dit zou eigenlijk hier te worden weergegeven. Dit is een pointer van het type knooppunt naar het volgende ding. En dat is wat ze omvat onze node. Cool. 

Oké, dus met zoeken, want we waren gewoon te zeggen voor de hand, als je gaan doorzoeken, je moet eigenlijk herhalen via uw gekoppelde lijst. Dus als we op zoek bent naar het nummer 9, zouden we beginnen bij ons hoofd en dat wijst ons in het begin van onze gelinkte lijst, toch? En we zeggen, OK, doet dit knooppunt bevatten het nummer 9? Nee? 

Oké, ga dan naar de volgende. Volg het. Bevat het de nummer 9? Nee. Volg de volgende. 

Dus moeten we eigenlijk herhalen via onze gelinkte lijst. We kunnen niet zomaar rechtstreeks naar waar 9 is. En als jullie eigenlijk willen zie een aantal pseudo-code daar. We hebben een aantal zoekfunctie hier dat neemt in-- wat is er nodig in? Wat denk je? Dus gemakkelijke. Wat is dit? Publiek: [onverstaanbaar]. SPEAKER 1: Het nummer dat we zoeken. Right? En wat zou dit overeenkomen met? Het is een verwijzing naar? 

Publiek: Een knooppunt. 

SPEAKER 1: Een knooppunt aan de lijst dat we kijken naar, toch? Dus hebben we een aantal knooppunten zijn pointer hier. Dit is een punt dat gaat eigenlijk doorlopen onze lijst. We stellen het gelijk aan lijst want dat is gewoon oprichting ervan gelijk aan de start van onze gelinkte lijst. 

En hoewel het niet NULL, terwijl we hebben nog steeds dingen in onze lijst, controleren om te zien of dat knooppunt het aantal dat we zoeken. Return true. Anders werken, toch? 

Als het NULL, we verlaten onze while loop en return false want dat betekent dat we hebben het niet gevonden. Krijgt iedereen hoe dat werkt? OK. 

Dus met inbrengen, je hebben drie verschillende manieren. U kunt prepend, u kunt toevoegen en u kunt invoegen in assorti. In dit geval zijn we ga een prepend doen. Weet iemand hoe die drie gevallen kunnen verschillen? 

Dus prepend betekent dat je het aan de voorzijde van uw lijst. Dus dat zou betekenen dat het niet uitmaakt wat uw knooppunt is, maakt niet uit wat de waarde is, je gaat om het goed hier op kop, OK? Het zal de eerste te zijn element in uw lijst. 

Als je het voegen, het gaat om naar de achterkant van je lijst. En in te voegen in assorti betekent dat je gaat daadwerkelijk in de plaats te zetten waar het houdt je gelinkte lijst gesorteerd worden. Nogmaals, hoe je het gebruikt deze en wanneer u gebruik ze zullen variëren afhankelijk van uw zaak. Als het niet nodig gesorteerd worden, prepend neigt te zijn wat de meeste mensen gebruiken omdat je dat niet doet moeten gaan door de hele lijst tot het einde om het op toe te vinden, toch? Je kunt gewoon plak het recht in. 

Dus gaan we door middel van een inbrengen 1 op dit moment. Dus een ding dat ik ga raden op deze pset is om dingen uit te trekken, zoals altijd. Het is erg belangrijk dat u op de hoogte uw pointers in de juiste volgorde want als je ze bij te werken iets niet in orde, je gaat eindigen het verliezen van onderdelen van uw lijst. 

Dus bijvoorbeeld, in dit geval, we vertelt het hoofd om gewoon punt 1. Als we gewoon doen dat zonder op te slaan dit 1, we hebben geen idee wat 1 moet nu wijzen op omdat we hebben verloren wat de kop wees. Dus een ding om te onthouden wanneer je aan het doen bent een prepend is aan wat het te redden hoofd punten naar de eerste plaats, opnieuw toewijzen het dan, en dan updaten wat uw nieuwe knooppunt moet verwijzen naar. In dit geval, dit is een manier om het te doen. 

Dus als we het gedaan had op deze manier waar we gewoon opnieuw toegewezen hoofd, we eigenlijk onze verliezen hele lijst, toch? Een manier om het te doen is om 1 punt te volgende, en dan het hoofd punt 1. Of u kunt soort doen, zoals de tijdelijke opslag, die ik sprak over. 

Maar de overheveling van uw pointers in de juiste volgorde zal heel erg worden belangrijk deze pset. Anders, je gaat naar een hash hebben tafel of een keer te proberen dat gewoon gaat worden slechts een deel van de woorden die je willen en dan you're-- mmhmm? Publiek: Wat was de tijdelijke opslag ding dat je het over? SPEAKER 1: De tijdelijke opslag. Dus eigenlijk een andere manier kon je dit doen is slaan het hoofd van iets, zoals slaan de tijdelijke variabele. Toewijzen aan 1 en dan update 1 naar punt in wat head gebruikt verwijzen. Zo is vanzelfsprekend eleganter omdat je kan een tijdelijke waarde niet nodig, maar gewoon het aanbieden van een andere manier om het te doen. En we eigenlijk hebben een code voor dit. Dus voor gelinkte lijst, we eigenlijk hebben enkele code. Dus steek hier, dit is prepending. Dus dit voert aan het hoofd. 

Dus eerste wat, moet je creëer je nieuwe knooppunt, natuurlijk, en controleren op NULL. Altijd goed. En dan moet je de waarden toe te wijzen. Wanneer u een nieuw knooppunt te maken, je weet niet wat het is te wijzen op de volgende, dus je wilt om het te initialiseren op NULL. Als het uiteindelijk naar iets anders, het wordt opnieuw toegewezen en het is prima. Als het het eerste wat vermeldt, moet aan te wijzen, omdat NULL dit is het einde van de lijst. 

Dus dan om deze in te voegen, zien we hier dat we zijn het toewijzen van de volgende waarde van ons knooppunt om welke kop is, dat is wat we hier hadden. Dat is wat we net gedaan. En dan zijn we het toewijzen van kop tot punt om onze nieuwe knooppunt, want vergeet niet, nieuwe enige pointer naar een knooppunt, en dat is precies wat het hoofd is. Dat is precies de reden waarom we hebben deze pijl accessor. Cool? Mmhmm? 

Publiek: Moeten we initialiseren nieuwe naast de eerste null, of kunnen we gewoon initialiseren om het hoofd? 

SPEAKER 1: New volgende moet NULL beginnen te omdat je niet weet waar het gaat worden. Ook dit is een soort van Net als een paradigma. U stelt het gelijk aan NULL gewoon om ervoor te zeker van zijn dat al uw bases gedekt voordat u een nieuwe toewijzing, zodat doen je bent altijd gegarandeerd dat het zal wijzen op een specifieke waarde versus zoals een garbage waarde. Omdat, ja, we toewijzen nieuwe next automatisch, maar het is meer net als een goede praktijken om het te initialiseren op die manier en vervolgens opnieuw toe te wijzen. 

OK, dus dubbel gelinkte nu lijsten. Wat vinden we? Wat is er anders met dubbel gelinkte lijsten? 

Dus in onze gelinkte lijsten, we kunnen slechts in één richting bewegen, toch? We hebben slechts de volgende. We kunnen alleen maar vooruit gaan. 

Met een dubbel gelinkte lijst, we kunnen ook achteruit bewegen. We hebben dus niet alleen de nummer dat we willen bewaren, we hebben waar het wijst op volgende en waar we net vandaan kwamen. Dus dit maakt sommige beter traversal. 

Dus dubbel gelinkte nodes, zeer vergelijkbaar zijn, toch? Enige verschil is nu dat we een volgende en vorige. Het is het enige verschil. 

Dus als we prepend of append-- we geen code voor deze up hier-- hebben maar als je om te proberen en te steek deze, de belangrijkste is wat je nodig hebt om te maken zorgen dat je het toewijzen zowel uw vorige en uw volgende pointer correct. Dus in dit geval, zou je niet alleen initialiseren volgende, u initialiseren vorige. Als we aan de kop van de lijst, we zou niet alleen het hoofd gelijk nieuwe te maken, maar onze nieuwe voorgaande moet wijzen op het hoofd, toch? 

Dat is het enige verschil. En als je meer oefenen met willen deze met gelinkte lijsten, met invoegen, met het verwijderen, met insert in een gevarieerd overzicht, kijk dan op study.cs50.net. Er is een bos van grote oefeningen. Ik beveel ze. Ik wou dat we tijd hadden om te gaan door ze te maar er is een hoop datastructuren door te komen. 

OK, dus hash tabellen. Dit is waarschijnlijk de meest nuttig bit voor uw pset hier omdat je gaat worden uitvoering van een van deze, of een keer te proberen. Ik hou echt van hash tabellen. Ze zijn wel cool. 

Dus eigenlijk wat gebeurt is een hash table is wanneer we echt nodig speedy insertie, deletie, en lookup. Dat zijn de dingen die we prioriteren in een hash table. Ze kan behoorlijk groot, maar zoals we zullen zien bij de pogingen, er zijn dingen die veel groter zijn. 

Maar in principe, alle een hash tafel is een hash-functie dat vertelt u welke emmer te leggen elk van uw gegevens, elk van uw elementen in. Een eenvoudige manier om te denken van een hash table is dat het gewoon emmers van de dingen, toch? Dus als u het sorteren dingen door net als de eerste letter van hun naam, dat is net zoiets als een hash table. 

Dus als ik naar de groep jongens is in groepen van wie de naam begint met een meer dan hier, of wie dan ook jarig is in januari, februari, maart, wat dat effectief het creëren van een hash table. Het is gewoon het creëren van emmers die u elementen sorteren van klein naar zodat je ze makkelijker kunt vinden. Dus op deze manier als ik het nodig naar één van je vinden, Ik hoef niet te zoeken door elk van uw namen. Ik kan zijn als, oh, ik weet dat Danielle's verjaardag is in-- Publiek: --April. SPEAKER 1: April. Dus ik kijk in mijn april emmer, en met een beetje geluk, ze zal de enige in daar te zijn en mijn tijd was constant in die zin, terwijl als ik moet kijken door middel van een hele hoop mensen, het zal veel langer duren. Dus hash tabellen zijn eigenlijk alleen maar emmers. Gemakkelijke manier om te denken van hen. 

Dus een heel belangrijk ding over een hash table is een hash-functie. Dus de dingen die ik net over gesproken, zoals je eerste letter van je voornaam of je verjaardag maand, Dit zijn ideeën die echt correleren met een hashfunctie. Het is gewoon een manier om te bepalen welke emmer Je Bent element gaat in, OK? Dus voor deze PSET, kunt u opzoeken vrijwel elke hash functie die u wilt. 

Hoeft niet je eigen zijn. Er zijn een aantal echt toffe gasten uit daar dat allerlei gekke math. En als u wilt uw maken spellingscontrole super snel, Ik zou zeker kijken naar een van die. 

Maar er zijn ook slechten, zoals compute de som van de woorden, zoals elke letter een nummer. Bereken de som. Bepaalt de emmer. Ze hebben ook de hand liggend dat zijn net als alle van de A's hier, alle van de B is hier. Een van deze. 

Kortom, het is gewoon vertelt u welke array-index van uw element moet ingaan. Net beslissen de bucket-- het is allemaal een hash-functie is. Hier hebben we een voorbeeld dat gewoon de eerste letter van de string dat ik net over sprak. 

Dus heb je een aantal hash dat is slechts het eerste letter van je touwtje minus A, waarin u een aantal zal geven getal tussen 0 en 25. En wat je wilt doen is Zorg ervoor dat dit vertegenwoordigt de grootte van uw hash table-- hoeveel emmers er zijn. Met veel van deze hash functies, ze zijn zal terugkeren waarden die kunnen ver boven het aantal emmers dat je eigenlijk hebt in je hash table, dus je moet ervoor zeker en mod door degenen. Anders, het gaat om te zeggen, oh, het moet in emmer 5000 maar heb je alleen 30 emmers in je hash table. En natuurlijk, we weten allemaal dat is zal resulteren in een aantal gekke fouten. Dus zorg ervoor dat mod door de grootte van de hash table. Cool. Zo botsingen. Is iedereen goed tot nu toe? Mmhmm? 

Publiek: Waarom zou het zo'n enorme waarde retourneren? 

SPEAKER 1: Afhankelijk van het algoritme dat je hash-functie gebruikt. Sommigen doen crazy vermenigvuldiging. En het is allemaal over het krijgen van een gelijkmatige verdeling, dus ze doen wat echt gekke dingen soms. Dat is alles. Iets anders? OK. 

Zo botsingen. Kortom, zoals ik al eerder zei, in het beste geval, elke emmer Ik kijk in is gaat om een ​​ding te hebben, dus ik hoef niet te kijken naar alle, toch? Ik ofwel weet dat het er of het is niet, en dat is wat we echt willen. Maar als we hebben tienduizenden gegevenspunten en minder dan nummer emmers, we gaan te hebben botsingen waar uiteindelijk iets zal hebben om te eindigen in een emmer die al een element. 

Dus de vraag is, wat doen we in dat geval? Wat doen wij? We iets er al? Gooien we het gewoon uit? 

Nee. We moeten beiden houden. Dus de manier waarop we typisch dat doen is wat? Wat is de datastructuur we alleen maar over gesproken? Publiek: Linked lijst. SPEAKER 1: Een gelinkte lijst. Nu, in plaats van elk van deze emmers gewoon met één element, het gaat om een ​​gekoppelde lijst bevatten de elementen die werden gehashd erin. OK, doet iedereen soort van dat idee? Omdat we een array niet konden omdat we niet weten hoeveel dingen gaan er in kunnen. Een gelinkte lijst laat ons toe om hoeft alleen het exacte aantal dat zijn hash in die emmer, toch? 

Dus lineaire indringende is in principe is deze idea-- het is een manier om te gaan met een botsing. Wat je kunt doen is als, in dit geval, bes werd hash in 1 en die we al hebben daar iets, je gewoon blijf naar beneden totdat u vindt een leeg slot. Dat is een manier om het te verwerken. De andere manier te hanteren het is met wat we zojuist called-- de gekoppelde lijst wordt genoemd chaining. 

Dus dit idee werkt als je hash table je denkt veel groter dan uw gegevens in te stellen of als u wilt proberen en te minimaliseren chaining totdat het is absoluut noodzakelijk. Dus een ding is lineair indringende betekent uiteraard dat je hash-functie is niet zo bruikbaar want je gaat uiteindelijk met behulp van je hash-functie, om naar een punt, je Linear sonde naar beneden te een plaats die beschikbaar is. Maar nu natuurlijk alles anders dat eindigt daar, je gaat te hebben om zoeken nog verder naar beneden. 

En er is nog veel meer zoeken uitgave die gaat in het invoeren van een element in je hash table nu, toch? En nu wanneer je gaat en proberen te vinden berry nogmaals, je gaat om het te hashen, en het zal zeggen: oh, kijk in emmer 1, en het is niet van plan te zijn in emmer 1, dus je bent gaat moeten doorkruisen de rest van deze. Dus het is soms nuttig, maar in de meeste gevallen, we gaan om te zeggen dat chaining is wat je wilt doen. 

Dus hebben we gesproken over dit eerder. Ik kreeg een beetje voor mezelf. Maar chaining is in feite dat elke emmer in je hash table is gewoon een gelinkte lijst. 

Dus een andere manier, of meer technische manier te denken van een hash table is dat het is gewoon een array van gelinkte lijsten, die als je het schrijven van je woordenboek en je probeert om het te laden, denk aan het als een reeks van gelinkte lijsten zal het veel gemakkelijker maken voor u om te initialiseren. 

Publiek: Dus hash table een vooraf bepaalde grootte, zoals een [onverstaanbaar] van emmers? 

SPEAKER 1: Recht. Dus het heeft een bepaald aantal emmers dat je determine-- die jullie moeten voel je vrij om mee te spelen. Het kan wel cool zijn om te zien wat er gebeurt als je je een aantal emmers veranderen. Maar ja, het heeft een ingestelde aantal emmers. Wat kunt u fit als veel elementen als je nodig hebt is dit aparte chaining waar u hebben lijsten verbonden in elke emmer. Dat betekent dat uw hash table zal precies de grootte dat je het nodig hebt om, toch? Dat is het hele punt van gelinkte lijsten. Cool. 

Dus iedereen OK daar? Prima. Ah. Wat is er gebeurd? Echt nu. Denk dat iemand vermoordt me. 

OK we gaan in te gaan pogingen, die zijn een beetje gek. Ik hou van hash tabellen. Ik denk dat ze echt gaaf. Tries zijn koel, ook. 

Dus heeft iemand nog wat te proberen is? Je moet dan zijn gegaan Kortom in collegezaal? Weet je nog een soort van hoe het werkt? Publiek: Ik ben gewoon knikken dat we gaan eroverheen. SPEAKER 1: We gaan er overheen. OK, we gaan echt te gaan dan is het nu wat we zeggen. 

PUBLIEK: Dat is voor een retrieval boom. 

SPEAKER 1: Ja. Het is een retrieval boom. Awesome. Dus een ding om hier te merken is dat we zijn op zoek naar individuele tekens hier, toch? 

Dus voordat met onze hash-functie, we waren op zoek naar de woorden als een geheel, en nu zijn we nog op zoek bij de personages, toch? Dus hebben we Maxwell hier en Mendel. Dus eigenlijk een try-- een manier om na te denken hiervan is dat elk niveau hier is een reeks letters. Dus dit is je root node hier, toch? Dit heeft alle tekens van de alfabet voor het begin van elk woord. 

En wat je wilt doen is laten we zeggen, OK, we hebben een aantal M woord. We gaan op zoek naar Maxwell, dus gaan we naar M. En M wijst op een hele andere een serie waar elke woorden, zolang er is een woord dat A heeft als de tweede letter, zolang er is een woord dat heeft B als de tweede letter, zal een pointer ga wat volgende array. 

Er is waarschijnlijk geen woord dat MP iets, dus bij de P positie in deze array, zou het gewoon NULL zijn. Het zou zeggen, OK, er is geen woord dat heeft M gevolgd door een P, OK? Dus als we denken, elke één van deze kleinere zaken is eigenlijk een van deze grote arrays van A tot Z. Dus wat zou een van de dingen dat is een soort van een nadeel van een keer te proberen? 

Publiek: Veel geheugen. 

SPEAKER 1: Het is een ton van het geheugen, toch? Elk van deze blokken hier vertegenwoordigt 26 ruimtes, 26 element array. Dus probeert te krijgen ongelooflijk ruimte zwaar. 

Maar ze zijn erg snel. Zo ongelooflijk snel, maar echt ruimte inefficiënt. Soort te achterhalen uit welke je wilt. Dit zijn echt cool voor uw PSET, maar ze nemen veel van het geheugen, zodat je de handel af. Yeah? 

Publiek: Zou het mogelijk zijn het opzetten van een keer te proberen en dan als je eenmaal alle gegevens in het dat je need-- Ik weet niet of dat zinvol zou zijn. Ik was het wegwerken van alle NULL karakters, maar dan zou je niet kunnen indexeren them-- 

SPEAKER 1: Je ziet ze nog steeds nodig. 

PUBLIEK: - op dezelfde manier elke keer. SPEAKER 1: Ja. U hebt de NULL karakters te laten je weet als er geen woord daar. Ben heb je iets wat je wilt hebben? OK. Oké, dus we gaan om een ​​beetje meer te gaan in de technische details achter een keer te proberen en werken door middel van een voorbeeld. 

OK, dus dit is het zelfde ding. Overwegende dat in een gelinkte lijst, onze soort van-- wat is het woord dat ik wil? - zoals het bouwen van blok was een knooppunt. In een keer te proberen, hebben we ook een knooppunt, maar het is anders gedefinieerd. 

Dus we hebben een aantal bool dat vertegenwoordigt of een woord eigenlijk Er is op deze locatie, en vervolgens we hebben een aantal scala hier-- of beter gezegd, Dit is een pointer naar een reeks van 27 tekens. En dit is in dit geval, dit 27-- Ik weet zeker dat jullie allemaal zijn als, wacht, er zijn 26 letters in het alfabet. Waarom hebben we 27? 

Dus afhankelijk van de manier waarop je dit te implementeren, dit is van een PSET dat toegestaan ​​voor de apostrof. Dus dat is de reden waarom de extra één. U zult ook in sommige gevallen de null terminator is als een van de tekens dat het mag zijn, en dat is hoe ze te controleren op te zien of het is het einde van het woord. Als je geïnteresseerd bent, check out Kevin's video op study.cs50, evenals Wikipedia heeft een aantal goede middelen daar. 

Maar we gaan om te gaan door gewoon een soort van hoe je zou kunnen werken via een try als je krijgt een. Dus we hebben een super eenvoudig hier dat heeft de woorden "bat" en "zoom" in hen. En zoals we zien hier, deze kleine ruimte hier vertegenwoordigt onze bool dat zegt: ja, dit is een woord. En dan is dit onze arrays van karakters, toch? 

Dus we gaan door te gaan het vinden van "bat" in deze poging. Dus beginnen bij de top, toch? En we weten dat B komt overeen met de tweede index, het tweede element in deze array, omdat a en b. Zo ongeveer de tweede. 

En het zegt, OK, cool, volgt dat in de volgende reeks, want als we ons herinneren, het is niet zo dat elk van deze eigenlijk bevat het element. Elk van deze arrays bevat een pointer, toch? Het is een belangrijk onderscheid te maken. 

Ik weet dat dit gaat om be-- probeert zijn echt hard op de eerste keer te krijgen, dus zelfs als dit het tweede of derde keer en het is nog steeds soort van schijnbaar moeilijk, Ik beloof als je horloge de korte morgen weer, het zal waarschijnlijk maken veel meer zin. Het duurt veel te verteren. Ik heb nog steeds wel eens ben als, wacht, wat is het proberen? Hoe kan ik deze gebruiken? 

Daarom hebben we in dit geval B, dat is onze tweede index. Als we hadden, laten we zeggen, c of d of andere letter, moeten we dat terug naar de index in kaart onze array die overeenkomt met. Dus we zouden nemen als rchar en we gewoon aftrekken buiten een om het opsplitsen 0 tot 25. Iedereen goed hoe we kaart ons karakter? OK. 

Dus we gaan naar de tweede en we zien dat, ja, het is niet op NULL. We kunnen doorstromen naar deze volgende array. Dus we gaan op naar deze volgende reeks hier. 

En we zeggen, OK, nu we nodig om te zien of een is hier. Is een null of toch niet eigenlijk vooruit? Dus een echt beweegt zendt in deze array. En we zeggen, OK, t is onze laatste brief. Dus gaan we naar de t op de index. En dan gaan we vooruit want er is een andere. En dit zegt in feite dat, ja, het zegt dat er een woord hier-- dat als je dit volgen pad, u bent gearriveerd in een woord, waarvan we weten dat "vleermuis." Ja? 

Publiek: Is het standaard te hebben dat als index 0 en dan een soort op 1 of aan het eind? 

SPEAKER 1: No. Dus als we terugkijken naar onze verklaring hier, het is een bool, dus het eigen element in knooppunt. Dus het is niet een deel van de array. Cool. Dus toen we eindigen ons woord en we zijn op deze array, wat we willen doen is doen een cheque voor is dit een woord. En in dit geval, zou ja terugkeren. 

Dus op die opmerking, we weten dat "zoo" - wij kennen als mens, dat "zoo" is een woord, toch? Maar probeer hier zou zeggen, nee, het is niet. En het zou zeggen dat, omdat we heb het niet aangewezen als een woord hier. Hoewel we kunnen doorkruisen tot deze array, Deze try zou zeggen dat, nee, dierentuin is niet in jouw woordenboek want we hebben niet aangewezen als zodanig. 

Dus een manier om dat-- doen oh, sorry, deze. Dus in dit geval, "zoo" is niet een woord, maar het is in onze poging. Maar in dit ene, zeggen we dat willen introduceren het woord 'bad', wat er gebeurt is volgen we through-- b, a, t. We zijn in deze serie, en we gaan om te zoeken naar h. 

In dit geval, wanneer we kijk naar de aanwijzer op h, het wijzend op NULL, OK? Dus tenzij het expliciet verwijzing naar een andere array, u ervan uitgaan dat alle pointers in deze array wijzen op null. Dus in dit geval, is h wijst op null dus kunnen we niets doen, dus het zou ook terugkeren vals, "bad" is niet in hier. Dus nu zijn we eigenlijk gaan om te gaan door hoe zouden we eigenlijk zeggen dat "zoo" is in onze poging. Hoe gaan we invoegen "dierentuin" in onze try? Dus op dezelfde manier dat we begonnen met onze gelinkte lijst, we beginnen bij de wortel. Bij twijfel, beginnen bij de wortel van deze dingen. 

En we zullen zeggen, OK, z. z bestaat hierin, en het doet. Dus je bent over te gaan tot uw volgende array, OK? En dan de volgende, wij zeggen, OK, doet o bestaan? Het doet. Dit bericht. 

En dus op onze volgende, hebben we gezegd, OK, "dierentuin" bestaat al hier. Het enige wat we moeten doen is deze gelijk te stellen true, dat er een woord daar. Als je alles had gevolgd tot ervóór, het is een woord, dus gewoon stel deze gelijk aan dergelijke. Ja? 

Publiek: Dus dan doet dat betekenen dat "ba" is een woord dat ook? 

SPEAKER 1: No. Dus in dit geval, "ba" we zouden krijgen hier, zouden we zeggen is het een woord, en het zou nog niet. OK? Mmhmm? 

Publiek: Dus als je eenmaal is het een woord en je zegt ja, dan is het bevat naar m? 

SPEAKER 1: dit heeft dus te maken met-- je het laden van deze in. Je zegt "zoo" is een woord. Als je naar check-- als, zeg je wilt zeggen, betekent "dierentuin" Er bestaan ​​in dit woordenboek? Je bent alleen gaat om te zoeken naar "dierentuin" en controleer om te zien of het een woord. Je bent nooit gaan verhuizen tot en met m, want dat is niet wat u zoekt. 

Dus als we eigenlijk wilden add "bad" in deze poging, we zouden hetzelfde doen zoals we hebben gedaan met "zoo," behalve wij zouden dat zien als we proberen en te h, bestaat het niet. Zo kunt u denken aan dit als een poging naar een nieuw knooppunt toe te voegen in een gelinkte lijst, dus we zouden moeten naar een andere toe te voegen één van deze arrays, zoals zo. En wat we doen is dat we zojuist de h element van deze array die aan deze. 

En wat zouden we hier willen doen? Voeg het toe dat gelijk is aan true want het is een woord. Cool. Ik weet het. Tries zijn niet de meest opwindende. Geloof me, ik weet het. 

Dus een ding om te beseffen met pogingen, Ik zei, ze zijn zeer efficiënt. Dus we hebben ze gezien nemen een ton van de ruimte. Ze zijn soort van verwarrend. Dus waarom zouden we ooit deze gebruiken? We gebruiken deze omdat ze ongelooflijk efficiënt. 

Dus als je ooit op zoek bent een woord, je bent alleen begrensd door de lengte van het woord. Dus als u op zoek bent naar een woord dat lengte vijf, je bent alleen maar zullen moeten maken hooguit vijf vergelijkingen, OK? Zo maakt het in principe een constante. Zoals het inbrengen en lookup zijn in principe constante tijd. 

Dus als je ooit kunt krijgen iets in constante tijd, dat is zo goed als het wordt. Je kan niet beter dan krijgen constante tijd voor deze dingen. Dat is een van de enorme plussen van pogingen. 

Maar het is veel ruimte. Dus je soort moet beslissen wat meer is belangrijk voor je. En op de computers van vandaag, de ruimte die een try kan duren misschien heeft geen invloed je dat veel, maar misschien je te maken hebt met iets dat heeft veel, veel meer dingen, en een keer te proberen is gewoon niet redelijk. Ja? 

PUBLIEK: Wacht, dus je hebt 26 letters in een ieder? 

SPEAKER 1: Mmhmm. Ja, je hebt 26. Je hebt een aantal is woord marker en dan je hebt 26 pointers in ieder. En ze point-- 

Publiek: En elke 26, ze hebben elk 26? 

SPEAKER 1: Ja. En dat is waarom, als je kan zie, het heel snel uitbreidt. Prima. Dus we gaan om in bomen, die Ik voel me net is gemakkelijker en zal waarschijnlijk zijn een leuk klein uitstel uit probeert daar. Dus hopelijk de meeste van jullie hebben een boom gezien. Niet zoals de mooie degenen buiten, die ik weet niet of iemand ging buiten onlangs. Ik ging appel plukken dit weekend, en oh mijn god, het was prachtig. Ik wist niet dat bladeren eruit zou kunnen zien dat mooi. 

Dus dit is gewoon een boom, toch? Het is slechts enkele knoop, en het wijst op een heleboel andere nodes. Zoals je hier ziet, is dit soort van een terugkerend thema. Knooppunten wijst naar knooppunten is een soort van de essentie van vele datastructuren. Het is maar net hoe wij laten wijzen naar elkaar en hoe we doorkruisen door hen en hoe we dingen in te voegen dat bepaalt hun verschillende eigenschappen. 

Dus gewoon wat terminologie, die ik eerder heb gebruikt. Dus wortel is wat er aan de top. het is waar we altijd beginnen. Je kunt het zien als het hoofd ook. Maar voor bomen, hebben we de neiging om te verwijzen naar het als de wortel. 

Alles wat op de bodem hier-- bij de zeer, zeer bottom-- zijn beschouwd bladeren. Het gaat dus met de hele boom ding, toch? De bladeren zijn aan de randen van uw boom. 

En dan hebben we ook een paar termen te praten over knooppunten in relatie elkaar. Dus we hebben de ouders, kinderen, en broers en zussen. Dus in dit geval 3 is de ouder van 5, 6 en 7. Dus de ouder is wat is één stap boven wat je bent verwijzen naar, dus gewoon als een stamboom. Hopelijk is dit allemaal een beetje beetje meer intuïtief dan het probeert. 

Broers en zussen zijn enige die hebben dezelfde ouder, toch? Ze zijn op hetzelfde niveau hier. En dan, als ik was zeggen, kinderen zijn net wat is een stap hieronder het knooppunt in kwestie, OK? Cool. Dus een binaire boom. Kan iedereen maar raden op een van de kenmerken van de binaire boom? 

Publiek: Max twee bladeren. 

SPEAKER 1: Recht. Dus maximum van twee bladeren. Dus in dit ene vóór, hadden we dit één dat drie hadden, maar in een binaire boom, heb je een maximum van twee kinderen per ouder, toch? Er is een andere interessante eigenschap. Weet iemand dat? Binaire boom. 

Dus een binaire boom zal alles hebben Op the-- deze is niet sorted-- maar in een gesorteerd binaire boom, alles rechts groter is dan de ouder, en alles links kleiner is dan de oorspronkelijke. En dat is een quiz geweest vraag voor, dus goed om te weten. Dus de manier waarop we dit te definiëren, nogmaals, we hebben een ander knooppunt. Dit lijkt erg op wat? Dubbel 

Publiek: Linked lijsten 

SPEAKER 1: Een dubbel gelinkte lijst, toch? Dus als we dit vervangen met vorige en volgende, dit zou een dubbel gelinkte lijst zijn. Maar in dit geval, we eigenlijk hebben links en rechts en dat is het. Anders is het precies hetzelfde. We hebben nog steeds het element u zoekt, en je hoeft alleen twee pointers gaan naar wat de toekomst biedt. Ja, dus binaire zoekboom. Als we merken, alles op de hier is groter than-- of alles onmiddellijk naar rechts hier groter dan alles Hier is dan. 

Dus als we waren te doorzoeken het, moet zeer dicht bij binary search kijken hier, toch? Behalve in plaats van naar de helft van de array, we alleen maar naar de linker- side of rechterkant van de boom. Dus het wordt een beetje eenvoudiger, denk ik. 

Dus als je root is NULL, uiteraard is het gewoon vals. En als het er is, natuurlijk is het waar. Als het minder dan zoeken we de linkerkant. Als het groter is dan, we zoeken de juiste. Het is precies zoals binary search, gewoon een andere datastructuur dat we gebruiken. In plaats van een array, het is gewoon een binaire boom. 

OK, stapelt. En ook, het lijkt erop dat we misschien een beetje tijd. Als we dat doen, ik ben blij om te gaan meer dan een van deze weer. OK, dus stapelt. Weet iemand wat herinneren stacks-- enige kenmerken van een stapel? 

OK, dus de meesten van ons, denk ik, eten in de eetzaal halls-- zo veel als we kunnen er niet van om. Maar natuurlijk kunt u denken aan een stapel letterlijk net als een stapel trays of een stapel van dingen. En wat belangrijk is om te beseffen is dat het something-- de karakteristieke dat noemen we het by-- is LIFO. Weet iemand wat dat voor staat? Mmhmm? 

Publiek: last in, first out. 

SPEAKER 1: Rechts, last in, first out. Dus als we weten dat, als we het stapelen dingen up, de makkelijkste om te off-- grijpen en misschien het enige wat we kunnen grijpen uit als onze stack is groot enough-- is dat top element. Dus wat is aan te trekken last-- zoals we hier zien, wat werd geduwd meeste recently-- is gaat de eerste te zijn ding dat we knallen, OK? 

Dus wat we hier hebben is andere typedef struct. Dit is echt net als een Spoedcursus in datastructuur, dus er is een hoop gegooid op je jongens. Ik weet het. Dus nog een struct. Yay voor structuren. 

En in dit geval, het is wat wijzer een array dat sommige capaciteit heeft. Dus dit vertegenwoordigt onze stack hier, net als onze eigenlijke serie die vasthoudt onze elementen. En dan hebben we hier een aantal grootte. 

En meestal, dat u wilt behouden spoor van hoe groot je stack want wat het gaat toestaan je moet doen is als je weet dat de grootte, staat het u te zeggen, OK, ben ik op de capaciteit? Kan ik iets meer toe te voegen? En het vertelt je ook waar de top van je stack is zodat je weet wat je daadwerkelijk kan opstijgen. En dat is eigenlijk gaat zijn hier een beetje meer duidelijk. 

Dus voor push, een ding, als je waren ooit te implementeren duwen, zoals ik was gewoon te zeggen, uw stack heeft een beperkte omvang, toch? Ons aanbod had wat capaciteit. Het is een matrix. Het is een vaste grootte, dus we moeten ervoor te zorgen dat we niet zetten meer in ons aanbod dan wij eigenlijk hebben ruimte voor. 

Dus als je het maken van een push functie, het eerste wat je doet is zeggen, OK, moet ik ruimte in mijn stack? Want als ik niet, sorry, Ik kan uw element niet bewaren. Als ik dat doe, dan wil je slaan het aan de top van de stack, recht? 

En dit is de reden waarom we hebben bij te houden van onze omvang te houden. Als we niet te houden van onze omvang, we weten niet waar te zetten. We weten niet hoeveel dingen zijn in ons aanbod al. Net als natuurlijk zijn er manieren dat misschien zou je het kunnen doen. Je kon alles initialiseren op NULL en controleer vervolgens voor de nieuwste NULL, maar een veel eenvoudiger ding is gewoon te zeggen, OK, bijhouden van grootte. Net als ik weet dat ik vier elementen in mijn array, dus de volgende ding dat we op, we zijn gaat slaan bij index 4. En dan, natuurlijk, betekent dit dat je hebt met succes iets geduwd op je stack, je het formaat wilt vergroten zodat je weet waar je bent zo dat je meer dingen kunt duwen. 

Dus als we proberen om pop iets uit de stapel, wat zou het eerste ding zijn dat we willen controleren? Je probeert te nemen iets van je stack. Weet je zeker dat er iets in je stack? Nee. Dus wat zouden we willen controleren? 

Publiek: [onverstaanbaar]. SPEAKER 1: Controleer voor de grootte? Size. Dus we willen controleren om te zien of onze omvang is groter dan 0, OK? En als het is, dan willen we verlagen onze omvang door 0 en terug te keren dat. Waarom? 

In de eerste waren we duwen, we duwde hem op grootte en vervolgens geactualiseerd grootte. In dit geval zijn we aflopende grootte en vervolgens het nemen van het uit, het plukken van het uit ons aanbod. Waarom zouden we dat doen? Dus als ik een ding op mijn stack, wat mijn maat op dat punt zou zijn? 1. 

En waar wordt element 1 opgeslagen? Op welke index? Publiek: 0. SPEAKER 1: 0. Dus in dit geval, we altijd moet maken sure-- in plaats van terug te keren minus 1, omdat we weten dat onze element is gaan 1 minder worden opgeslagen wat onze omvang is, dit net verzorgt het. Het is een iets elegantere manier. En we gewoon verlagen onze grootte en dan terug grootte. Mmhmm? 

Publiek: Ik denk gewoon in het algemeen, waarom zou deze datastructuur nuttig zijn? 

SPEAKER 1: Het hangt af van uw context. Dus voor sommige van de theorie, als je werkt met-- OK, laat me zien of er een heilzame die bijdragen tot meer dan daarbuiten van CS. Met stapels, elke keer dat je nodig hebt bij te houden van iets houden dat wordt de meest recent toegevoegde is wanneer je gaat te willen een stack gebruiken. 

En ik kan niet denken aan een goede voorbeeld van dat recht nu. Maar wanneer de meest recente wat is het meest belangrijk voor je is, dat is wanneer een stapel zal nuttig zijn. Ik probeer te denken als er is een goed jaar voor dit. Als ik denk aan een goed voorbeeld in het volgende 20 minuten, ik zal zeker je vertellen. 

Maar over het algemeen, als er iets is, zoals ik al zei de meeste, waar de meest recente het belangrijkste is, dat is waar een stapel in het spel komt. Overwegende dat de wachtrijen zijn soort van het tegenovergestelde. En alle kleine honden. Is dit niet geweldig, toch? Ik voel me alsof ik zou moeten gewoon een konijntje video in het midden van sectie voor jullie omdat dit een intense sectie. 

Dus een wachtrij. In principe is een wachtrij is als een lijn. Jullie Ik weet zeker gebruik deze elke dag, Net als in onze eetzalen. Dus we moeten gaan in en krijg onze dienbladen, ik ben ervoor dat je hoeft te wachten in de rij te vegen of je je eten. 

Dus hier het verschil is dat dit FIFO. Dus als LIFO is voor het laatst in, eerst out, FIFO is first in, first out. Dus dit is waar wat je zetten op eerste is uw belangrijkste. Dus als je zaten te wachten in een line-- kunt u stel je voor als je ging naar haal de nieuwe iPhone en het was een stapel waarbij de laatste persoon in de rij kreeg het eerste, mensen zouden vermoorden elkaar. 

Dus FIFO, we zijn allemaal zeer vertrouwd met in hier de echte wereld, en het heeft allemaal te maken met het daadwerkelijk soort herscheppen van dit hele lijn en de rij-structuur. Dus terwijl de stack, we hebben push en pop. Met een wachtrij, we hebben enqueue en dequeue. Dus enqueue betekent in feite zet het op de rug, en dequeue middelen nemen off van het front. Dus onze datastructuur is een beetje meer ingewikkeld. We hebben een tweede ding bij te houden. 

Dus zonder het hoofd, dit is precies een stapel, toch? Dit is dezelfde structuur als een stapel. Het enige wat anders is dat we nu hebben dit hoofd, dat wat denk je gaat om bij te houden? 

Publiek: De eerste. 

SPEAKER 1: Rechts, de eerste ding dat we in. Het hoofd van onze wachtrij. Wie is de eerste in de rij. Oké, dus als we enqueue doen. Opnieuw met een van deze datastructuren, omdat we te maken hebben met een array, we moeten controleren of we nog ruimte. 

Dit is net zoiets als mij te vertellen jullie, als je een bestand opent, je nodig hebt om te controleren op null. Met een van deze stapels en wachtrijen, moet je om te zien of er ruimte omdat we maken met een vaste grootte array, zoals we zien hier-- 0, 1 al tot 5. Dus wat wij doen in dat geval is check om te zien of we nog steeds de ruimte. Is onze omvang kleiner dan de capaciteit? 

Als dat zo is, moeten we het op te slaan op de staart en we onze omvang te updaten. Dus wat zou de staart zijn in dit geval? Het is niet expliciet uitgeschreven. Hoe zouden we opslaan? Wat zou de staart zijn? 

Dus laten we lopen door dit voorbeeld. Dus dit is een array van grootte 6, toch? En we hebben op dit moment, onze grootte is 5. En toen we hem in, het gaat in te gaan op de vijfde index, toch? Dus slaan bij de staart. 

Een andere manier om de staart te schrijven zou net zijn ons aanbod aan index van omvang, toch? Deze maat is 5. Volgende ding is in te gaan op 5 om te gaan. Cool? OK. Het wordt iets ingewikkelder wanneer we beginnen knoeien met het hoofd. Ja? 

Publiek: Betekent dit dat we zou een array hebben verklaard dat was vijf elementen lang en Vervolgens voegen we op het? 

SPEAKER 1: No. Dus in dit geval, is een stapel. Dit wordt verklaard als een array van grootte 6. En in dit geval, we slechts één ruimte links. 

OK, dus een ding is in dit geval, als ons hoofd is op 0, dan kunnen we alleen maar kunnen het toevoegen aan de grootte. Maar het wordt een beetje lastiger omdat zelfs, zij heb een dia niet voor deze, dus ik ga om één te tekenen omdat het niet zo simpel als je eenmaal start het wegwerken van dingen. Dus terwijl met een stapel zodat u alleen te maken over wat de grootte is als je iets toe te voegen aan, met een wachtrij die u moet ook ervoor ervoor dat je hoofd wordt verantwoord, omdat een koele ding over wachtrijen is dat als je niet bij de capaciteit, je kunt eigenlijk maken het wikkelen. 

OK, dus één thing-- oh, dit is verschrikkelijk krijt. Een ding om te overwegen is het geval. We zullen gewoon doen vijf. OK, dus we gaan zeggen dat de kop is hier. Dit is 0, 1, 2, 3, 4. 

De kop is er, en neem eens dingen in hen. En we willen iets toe te voegen, toch? Dus het ding dat we nodig hebben om weten is dat het hoofd is altijd gaat op deze manier te bewegen en dan loop terug rond, OK? 

Dus deze wachtrij heeft ruimte, toch? Het heeft ruimte in het allereerste begin, soort Tegengesteld hieraan. Dus wat we moeten doen is dat we nodig om de staart te berekenen. Als u weet dat uw hoofd heeft niet bewogen, staart is gewoon de array op de index van de grootte. 

Maar in werkelijkheid, als je met behulp van een wachtrij, je hoofd is waarschijnlijk bijgewerkt. Dus wat je hoeft te doen is eigenlijk berekenen de staart. Dus wat we doen is deze formule hier, die ik ga u laten jullie denken over, en dan kunnen we erover praten. Dus dit is de capaciteit. 

Zo zal dit ook daadwerkelijk geven u een manier om het te doen. Omdat in dit geval, wat? Ons hoofd is op 1, onze grootte is 4. Als we mod dat door 5, krijgen we 0, dat is waar we moeten ingang het. 

Dus dan in het volgende geval, als we waren om dit te doen, wij zeggen, OK, laten we dequeue iets. We dequeue dit. We nemen dit element, toch? 

En nu ons hoofd is hier te wijzen, en we willen voegen in een ander ding. Dit is in principe achterkant van onze lijn, toch? Wachtrijen kunnen wikkel rond de array. Dat is een van de belangrijkste verschillen. Stacks, kun je dit niet doen. 

Met wachtrijen, je kan want het enige dat telt is dat je weet wat werd het meest recent toegevoegd. Aangezien alles zal worden toegevoegd deze naar links richting, in dit geval, en vervolgens wikkel rond, je kan voort te zetten in nieuwe elementen aan de voorzijde van de matrix want het is niet echt de voorzijde van de matrix meer. U kunt denken aan het begin van de array waar je hoofd eigenlijk is. 

Dus deze formule is hoe je je staart te berekenen. Is dat zinvol? OK. OK, dequeue, en vervolgens jullie hebben 10 minuten om me vragen te verduidelijken vragen je wilt, want ik weet dat het gek. 

Oké, dus in dezelfde way-- Ik weet niet of jullie opgevallen, maar CS is alles over patronen. Dingen zijn vrijwel hetzelfde, alleen met kleine tweaks. Dus hier hetzelfde. We moeten controleren om of we eigenlijk zien hebben iets in onze rij, toch? Zeggen, OK, is onze omvang groter dan 0? Cool. 

Als we dat doen, dan ons hoofd, gaan we die is wat ik net hier gedemonstreerd. We werken onze hoofd naar een meer te zijn. En dan verlagen we onze de grootte en de terugkeer van het element. 

Er is veel concreter code op study.cs50.net, en ik aanbevelen te gaan er doorheen als je tijd hebt, zelfs als het is gewoon een pseudo-code. En als jullie willen door middel van praten die bij mij één op één, laat het me ken. Ik zou graag. Gegevensstructuren als je CS 124 nemen, dan heb je weten dat datastructuren erg plezier en dit is nog maar net begonnen. 

Dus ik weet dat het moeilijk. Het is OK. We worstelen. Doe ik nog steeds. Dus niet te veel zorgen over te maken. 

Maar dat is in principe uw Spoedcursus in datastructuren. Ik weet dat het veel. Is er iets dat we wil om opnieuw te gaan? Alles wat we willen door middel van praten? Ja? 

Publiek: voor dat voorbeeld, zodat de nieuwe staart is aan 0 dan dat? SPEAKER 1: Ja. Publiek: OK. Dus dan gaan door, zou je 1 plus 4 of-- hebben 

SPEAKER 1: Dus je zei, wanneer we willen gaan opnieuw doen dit? Publiek: Ja. Dus als je het uitzoeken out-- waar zijn u de berekening van de staart uit in dat? 

SPEAKER 1: Dus de staart was in-- ik dit veranderd. In dit voorbeeld hier was de array waar we naar kijken, OK? Dus hebben we de dingen in 1, 2, 3, en 4. Dus hebben we onze kop is gelijk aan 1 op dit punt, en onze wijdte 4 op dit punt, toch? 

Je allemaal over eens dat het geval is? Dus we doen het hoofd plus de grootte, die geeft ons 5, en dan modden we door 5. We krijgen 0, die ons vertelt dat 0 is waar is onze staart, waar we de ruimte. 

Publiek: Wat is een pet? 

SPEAKER 1: De capaciteit. Sorry. Dus dat is de grootte van de array. Ja? 

Publiek: [onverstaanbaar] vóór we het element terug? 

SPEAKER 1: Dus gaan we de hoofd of terugkeren op het moment? Dus als we een te verplaatsen, te verlagen van de grootte? Hold on. Ik vergat zeker een ander. Maakt niet uit. Er is niet een andere formule. Ja, zou je willen terugkeren de kop en verplaats het dan terug. 

Publiek: OK, omdat op dit punt, het hoofd was op 0, en dan wil je om terug te keren index 0 en vervolgens het hoofd 1? 

SPEAKER 1: Recht. Ik denk dat er een andere formule zoiets als dit. Ik heb het niet op de top van mijn hoofd als Ik wil niet dat je de verkeerde te geven. Maar ik denk dat het volkomen geldig tot laten we zeggen, OK, bewaar dit element-- wat hoofd element is-- verlagen uw grootte, beweeg je hoofd over, en terugkeer wat dat element is. Dat is volkomen geldig. OK. Ik voel me als dit is niet zoals de most-- je bent niet gaan om uit te lopen van hier als, ja, ik weet het probeert. Ik heb het allemaal. Dat is OK. Ik beloof het. Maar datastructuren zijn iets dat het kost veel tijd om te wennen aan. Waarschijnlijk een van de moeilijkste dingen, denk ik, in de loop. 

Dus het duurt zeker herhaling en op zoek at-- I niet echt weten gelinkte lijsten totdat ik deed veel te veel met hen, op dezelfde manier dat ik niet echt begrijpen pointers totdat ik heb gehad om het te leren voor twee jaar en doe mijn eigen psets mee. Het kost veel herhaling en tijd. En uiteindelijk zal dit soort klik. 

Maar in de tussentijd, als je soort hebt een hoog begrip van wat deze doen, hun voor- en cons-- dat is wat we echt de neiging om te benadrukken, vooral in de intro cursus. Zoals, waarom zouden we gebruiken een keer te proberen over een array? Zoals, wat zijn de positieve en negatieven van elk van deze? 

En het begrijpen van de trade-offs tussen deze structuren is wat veel belangrijker op dit moment. Er kan één gek zijn vraag of twee dat is ga je vragen om te implementeren push of implementeren pop of enqueue en dequeue. Maar voor het grootste gedeelte heeft dat hoger niveau begrip en meer van een intuïtief begrip is belangrijker dan eigenlijk in staat om het te implementeren. 

Het zou echt geweldig zijn als jullie allemaal kon uit te gaan en te gaan implementeren een keer te proberen, maar we begrijpen dat het niet per se de meest redelijke ding nu. Maar je kunt in uw PSET, als je wilt aan, en dan zul je de praktijk te krijgen, en dan misschien zult echt begrijpen. Ja? 

Publiek: OK, dus welke zijn we bedoeld voor gebruik in de PSET? Heb ik nodig om een ​​van hen te gebruiken? SPEAKER 1: Ja. Dus je hebt je keuze. Ik denk dat in dit geval, we kunnen praten over de pset een beetje want ik liep door deze. Dus in uw PSET, je hebt je keuze van pogingen of hash tabellen. Sommige mensen zullen proberen en gebruik bloei filters, maar die technisch gezien niet correct zijn. Vanwege hun probabilistische aard ze geven valse positieven soms. Ze zijn koele blik in, dat wel. Zeer aan te bevelen op zoek hen tenminste. Maar je hebt je keuze tussen een hash table en een keer te proberen. En dat gaat zijn waar die u in uw woordenboek. 

En je zult moeten kiezen je hash-functie, je nodig hebt om te kiezen hoeveel Emmers je hebt, en het zal variëren. Net als je meer emmers, misschien zal het sneller lopen. Maar misschien je verspilt een veel ruimte op die manier, dat wel. Je moet het uitzoeken. Mmhmm? 

Publiek: U zei eerder dat kunnen we andere hash-functies te gebruiken, dat we niet hoeven te het creëren van een hash-functie? 

SPEAKER 1: Ja, rechts. Dus letterlijk voor uw hash-functie, zoals google "hash-functie" en kijken naar een aantal toffe gasten. U bent niet verwacht op te bouwen je eigen hash-functies. Mensen besteden hun stellingen over deze dingen. 

Dus maak je geen zorgen over het bouwen van je eigen. Vind een online om mee te beginnen. Sommigen van hen moet je manipuleren een beetje om er zeker van terugkeer types overeenkomen en wat al niet, dus in het begin, Ik raad je aan om iets echt makkelijk dat misschien gewoon hashes op de eerste letter. En dan als je eenmaal hebt dat werken, het opnemen van een koeler hash-functie. Mmhmm? 

Publiek: Zou een keer te proberen te zijn of efficiënt, maar gewoon moeilijker om, like-- 

SPEAKER 1: Dus een keer te proberen, denk ik, is intuïtief moeilijk te implementeren maar is erg snel. Echter, meer plaats inneemt. Ook hier kunt u deze beide te optimaliseren in verschillende manieren en er zijn manieren to-- Publiek: Hoe worden we beoordeeld op dit? Heeft het matter-- 

SPEAKER 1: Dus je bent ingedeeld normale manier. Je gaat om te worden beoordeeld op design. Welke manier je ook doet, je wilt zorg ervoor dat het zo elegant als het kan worden en zo efficiënt kan zijn. Maar als je een keer te proberen of hash kiezen tafel, zolang het werkt, zijn we blij mee. En als je iets gebruiken dat hashes op de eerste letter, dat is prima, zoals misschien als ontwerp-wijs. We zijn ook het bereiken van de punt in deze semester-- Ik weet niet of je jongens noticed-- als je pset kwaliteiten dalen een beetje vanwege het ontwerp en wat al niet, dat is prima. Het wordt naar een punt waar je 's worden steeds ingewikkelder. Er zijn meer plaatsen je kunt verbeteren op. 

Dus het is volkomen normaal. Het is niet dat je bent slechter doet op uw pset. Het is gewoon dat we harder wezen op je nu. Dus iedereen voelt het. Ik graded al uw psets. Ik weet dat iedereen voelt het. 

Wees dus niet ongerust over. En als je vragen hebt over voorafgaand psets of manieren waarop u kunt verbeteren, Ik probeer en commentaar van de specifieke plaatsen, maar soms is het te laat en ik moe. Zijn er nog andere dingen over data structuren? Ik weet zeker dat jullie echt niet doen wil over hen meer over praten, maar als er zijn, ik ben blij om gaat over hen, evenals om het even wat vanaf lezing afgelopen week of vorige week. 

Ik weet van vorige week was alle review, dus we kunnen over sommige beoordeling hebben overgeslagen van lezing. Eventuele andere vragen die ik kan beantwoorden? OK, goed. Nou, jullie krijgen 15 minuten te vroeg. 

Ik hoop dat dit was semi-behulpzaam tenminste, en ik zie je jongens volgende week, of donderdag kantooruren. Zijn er verzoeken voor snacks voor volgende week, het is het ding? Omdat ik vergat snoep vandaag. En ik bracht snoep laatste week, maar het was de Dag van Columbus, dus er waren als zes mensen die had vier zakken snoep aan zichzelf. Ik kan brengen Starbursts nogmaals als je wilt. Starbursts? OK, klinkt goed. Heb een grote dag, jongens.