JASON HIRSCHHORN: Welkom iedereen aan de afdeling Seven. We zijn in week zeven van de cursus. En dat aanstaande donderdag is Halloween dus ik ben verkleed als een pompoen. Ik kon niet bukken en op mijn schoenen, dus dat is waarom ik ben alleen het dragen van sokken. Ik ben ook niet dragen van iets onder dit, dus ik kan niet het opstijgen als het afleidend aan u. Ik verontschuldig me bij voorbaat voor. U hoeft niet voor te stellen wat er gaande is. Ik draag boxers. Dus het is allemaal goed. 

Ik heb een langer verhaal over waarom ik gekleed als een pompoen, maar ik ga bewaren voor later in deze paragraaf want ik wil aan de slag. We hebben een heleboel spannende dingen te gaan over deze week. De meesten van hen hebben rechtstreeks betrekking op dit probleem set week, spelfouten. We gaan gaan over verbonden lijsten en hash tabellen Voor het volledige overzicht. Ik heb deze lijst elke week, een lijst van middelen voor u om u te helpen met het materiaal op deze cursus. Als bij een verlies of als op zoek naar een aantal meer informatie, kijk op een van deze middelen. 

Nogmaals, pset6 is spelfouten, PSET van deze week. En het stimuleert je ook, en ik u aanmoedigen, om een ​​aantal andere gebruiken middelen die specifiek voor deze PSET. Met name de drie heb ik up op het scherm weergegeven - gdb, die we bekend met zijn geweest en gebruikt voor een tijdje nu, is gaat zeer nuttige week. Dus heb ik dat hier. Maar als je werkt met C, je moet altijd gebruiken gdb aan debuggen uw programma's. Deze week ook Valgrind. Weet iemand wat valgrind doet? 

Publiek: Er wordt gecontroleerd of memory leaks? 

JASON HIRSCHHORN: Valgrind controles voor memory leaks. Dus als je malloc iets in uw programma, bent u vragen om het geheugen. Aan het einde van je programma, je hebt te schrijven gratis op alles wat je hebt malloced om het geheugen terug te geven. Als je niet schrijven gratis aan het eind en uw programma komt tot een conclusie, alles automatisch worden bevrijd. En voor kleine programma's, het is niet zo'n groot probleem. Maar als je het schrijven van een langer lopende programma dat niet stoppen, se, in een paar minuten of een paar seconden, dan is het geheugen lekt kan een enorme deal geworden. 

Dus voor pset6, de verwachting is dat je zult nul geheugenlekken hebben met uw programma. Om te controleren of het geheugen lekken, lopen valgrind en het zal u geven een aantal leuke uitgang te laten weten of of niet alles was gratis. We zullen later oefenen met het vandaag, hopelijk. 

Ten slotte is de diff commando. Je iets wat lijkt op het gebruikt in pset5 met de peek tool. Mag je naar binnen te kijken. Je gebruikt ook diff ook, per het probleem te stellen spec. Maar je mag vergelijken van twee bestanden. Je kon de bitmap-bestand en vergelijk info headers van een staf-oplossing en uw oplossing in pset5 als je ervoor kiest om het te gebruiken. Diff zal u toelaten om dat te doen, ook. Je kunt het vergelijken het juiste antwoord voor probleem van deze week in te stellen om uw antwoord en zien of het lijnen of zie waar de fouten. 

Dus dat zijn drie goede tools die u moet gebruiken voor deze week, en zeker check je programma met deze drie instrumenten voordat u het in Nogmaals, als ik elke week heb genoemd, Als u feedback heeft voor mij - zowel positieve en constructieve - voel je vrij om naar de website onderaan deze dia en voer het daar. Ik elke waardeer en alle feedback. En als je me specifieke dingen die Ik kan doen om te verbeteren of dat ik ben goed te doen dat je zou willen dat ik blijven, neem ik dat ter harte en echt hun best om te luisteren aan uw feedback. Ik kan niet beloven dat ik ga doen alles, hoewel, als het dragen van een pompoen kostuum elke week. 

Dus gaan we het grootste deel van de te besteden sectie, zoals ik al zei, het over gelinkte lijsten en hash tabellen, die zal direct van toepassing op de te probleem stelt u deze week. Gelinkte lijsten we over relatief gaan snel omdat we een eerlijke beetje hebt besteed van tijd gaan over het in sectie. En dus gaan we rechtstreeks naar het krijgen coderen problemen voor gelinkte lijsten. En dan aan het eind zullen we praten over hash tabellen en hoe ze van toepassing op deze probleem week in te stellen. 

Je hebt deze code eerder gezien. Dit is een structuur, en definieert iets nieuws wordt een knooppunt genoemd. En in een knooppunt is een integer hier en daar is een pointer naar ander knooppunt. We hebben dit eerder gezien. Dit komt al voor een paar weken nu. Het combineert pointers, die we geweest zijn werken met, en structs, waardoor wij twee combineren dingen in een datatype. 

Er is veel gaande op het scherm. Maar al het moet relatief zijn vertrouwd zijn met je. Op de eerste regel, we verklaren een nieuw knooppunt. En dan binnen dat nieuwe knooppunt, ik het gehele getal in dat knooppunt een. We zien op de volgende regel ik een doe printf commando, maar ik heb grijs de printf commando omdat het echt belangrijk deel is deze lijn hier - new_node.n. Wat betekent de stip betekenen? 

PUBLIEK: Ga naar het knooppunt en beoordelen van de n-waarde voor. 

JASON HIRSCHHORN: Dat is precies goed. Dot betekent toegang tot de n deel deze nieuwe knooppunt. Deze volgende regel doet wat? Michael. 

Publiek: Het creëert een ander knooppunt die naar het nieuwe knooppunt. 

JASON HIRSCHHORN: het doet dus niet maak een nieuw knooppunt. Het creëert een wat? 

PUBLIEK: Een pointer. 

JASON HIRSCHHORN: Een pointer naar een knooppunt, zoals aangegeven door dit knooppunt * hier. Dus creëert een pointer naar een knooppunt. En welke node wordt deze naar tot, Michael? 

PUBLIEK: Nieuw knooppunt? 

JASON HIRSCHHORN: Nieuw knooppunt. En het wijst er omdat we hebben gegeven het adres van de nieuwe node. En nu in deze lijn zien we twee verschillende manieren uiting van hetzelfde. En ik wilde erop wijzen hoe deze twee dingen zijn hetzelfde. In de eerste regel, dereferentie we de aanwijzer. Dus gaan we naar het knooppunt. Dat is wat deze ster betekent. We hebben gezien dat voordat met pointers. Ga naar dat knooppunt. Dat is tussen haakjes. En dan toegang via de puntoperator de n element van dat knooppunt. 

Dus dat is het nemen van de syntaxis we hier en nu zag internetten met een pointer. Natuurlijk, het wordt een beetje druk als je bent het schrijven van die haakjes - die ster en dat stip. Het wordt een beetje druk. Zodat we een aantal syntactische suiker. En deze lijn hier - ptr_node-> n. Dat doet precies hetzelfde. Dus die twee regels code zijn gelijkwaardig en zal doen precies hetzelfde. 

Maar ik wilde wijzen die vóór we verder gaan, zodat je begrijpt die echt dit ding hier is alleen syntactische suiker voor dereferentie de aanwijzer en vervolgens naar n de deel van die structuur. Heeft u vragen over deze dia? OK. 

Dus we gaan om te gaan door een paar van de activiteiten die u kunt doen gelinkte lijsten. Een gelinkte lijst, rappel, is een serie van knooppunten die naar elkaar. En we beginnen meestal met een wijzer genoemd hoofd algemeen die verwijst naar het eerste wat in de lijst. Dus op de eerste lijn hier, we eerst onze oorspronkelijke L. Zodat wat je maar kunt bedenken - dit tekst hier je kunt bedenken als alleen de pointer die we hebben opgeslagen ergens dat punten het eerste element. En in deze gelinkte lijst hebben we vier knooppunten. Elk knooppunt is een grote doos. De grotere doos in de grote box is het gehele deel. En dan hebben we een pointer deel. 

Deze dozen zijn niet op schaal want hoe groot is een geheel getal bytes? Hoe nu groot? Four. En hoe groot is een pointer? Four. Dus echt, als we trekken Deze beide vakken schaal zou dezelfde grootte. In dit geval willen we voegen iets in de gelinkte lijst. Zo kunt u hier beneden zien we het invoegen vijf We doorkruisen via de gelinkte lijst, vinden waar vijf gaat, en steek deze vervolgens. 

Laten we breken die naar beneden en gaan een beetje langzamer. Ik ga om te wijzen op het bord. Dus hebben we onze knooppunt vijf die we hebben gemaakt in mallocs. Waarom is iedereen lachen? Grapje. OK. Dus we hebben malloced vijf. We hebben dit knooppunt gemaakt ergens anders. We hebben het klaar om te gaan. We beginnen bij de voorzijde van onze lijst met twee. En we willen invoegen in een gesorteerde manier. 

Dus als we zien twee en we willen zetten in vijf, wat doen we als we zien doen iets minder dan wij? Wat? We willen invoegen vijf in deze gelinkte lijst, waardoor het opgelost. We zien nummer twee. Dus wat doen we? Marcus? 

PUBLIEK: Bel de wijzer naar het volgende knooppunt. 

JASON HIRSCHHORN: En waarom doen gaan we naar de volgende? 

Publiek: Omdat het de volgende knooppunt in de lijst. En we weten alleen dat een andere locatie. 

JASON HIRSCHHORN: En vijf is groter dan twee, in het bijzonder. Omdat we willen het gesorteerde houden. Dus vijf groter is dan twee. Dus gaan we over naar de volgende. En nu komen we bij vier. En wat gebeurt er als we vier bereiken? 

Vijf is groter dan vier. Dus houden we gaan. En nu zijn we om zes uur. En wat zien we om zes uur? Ja, Carlos? 

PUBLIEK: Zes is groter dan vijf. 

JASON HIRSCHHORN: Six is groter dan vijf. Dus dat is waar we willen in te voegen vijf. Houd er echter rekening mee dat als we slechts een wijzer hier - dit is onze extra pointer dat is doorkruist door de lijst. En we wijzen op zes. We hebben verloren spoor van wat komt voor zes. Dus als we iets willen in voegen deze lijst houden van het te regelen, we waarschijnlijk hoeveel pointers? 

PUBLIEK: Twee. 

JASON Hirschorn: Two. Een te houden van de huidige te houden een en een bij te houden de vorige. Dit is slechts een enkelvoudig gelinkte lijst. Het gaat slechts een richting. Als we een dubbel gelinkte lijst, waar alles wees naar het ding na het en het ding voor, dan zouden we niet nodig om dat te doen. Maar in dit geval willen we niet verliezen bij wat voor ons kwamen in geval we moeten vijf ergens invoegen in het midden. Zeggen dat we het plaatsen van negen. Wat zou er gebeuren als we tot acht? 

PUBLIEK: Je zou krijgen dat nulpunt. In plaats van nulpunt zou je om een ​​element toe te voegen en dan hebben het wijzen op negen. 

JASON Hirschorn: Precies. Dus krijgen we acht. We bereiken het einde van de lijst omdat dit wijst op null. En nu, in plaats van het hebben van het wijzen op null we hebben het naar onze nieuwe knooppunt. En we stellen de aanwijzer in onze nieuwe knooppunt op null. Heeft iemand enig vragen over het invoegen? Wat als ik niet schelen het bijhouden van de lijst gesorteerd? 

PUBLIEK: Plak het op de het begin of het einde. 

JASON Hirschorn: Stick it in het begin of het einde. Welke moeten we doen? Bobby? Waarom het einde? 

PUBLIEK: Omdat het begin is al ingevuld. 

JASON Hirschorn: OK. Het begin is al ingevuld. Wie wil om te betogen tegen Bobby. Marcus. 

PUBLIEK: Nou wil je waarschijnlijk plak het in het begin, omdat anders als je het op het einde je zou moeten doorkruisen de hele lijst. 

JASON Hirschorn: Precies. Dus als we denken over runtime, de looptijd van inbrengen eind n zou zijn, de grootte van deze. Wat is het grote O runtime van het plaatsen van begin? Constante tijd. Dus als je niet de zorg over het houden van iets gesorteerd, veel beter om gewoon Steek aan het begin van deze lijst. En dat kan worden gedaan in constante tijd. 

OK. Volgende handeling is te vinden, die andere - we hebben dit geformuleerd als zoekopdracht. Maar we gaan kijken door de gekoppelde lijst voor een object. Jullie zijn code gezien voor zoeken voordat in collegezaal. Maar we soort net deed het met invoegen, althans invoegen iets gesorteerd. Je kijkt door, gaan knoop door knoop, totdat u het nummer dat u vindt zoekt. Wat gebeurt er als je te bereiken het einde van de lijst? Zeggen dat ik ben op zoek naar negen en ik bereiken het einde van de lijst. Wat doen wij? 

PUBLIEK: return false? 

JASON Hirschorn: return false. We vonden het niet. Als je het einde van de lijst te bereiken en je hebt het nummer je niet vinden op zoek naar, het is niet daar. Heeft u vragen over vinden? Als dit een gesorteerde lijst, wat zou anders onze zoeken? Yeah. 

Publiek: Het zou de eerste waarde te vinden dat is groter dan de u zoekt en dan terug vals. 

JASON Hirschorn: Precies. Dus als het een gesorteerde lijst, als we naar iets dat groter is dan we zoeken, hoeven we niet te steeds naar het einde van de lijst. We kunnen op dat punt return false omdat we niet van plan om het te vinden. De vraag is nu, we hebben gesproken over het houden van gelinkte lijsten gesorteerd, houden ze ongesorteerd. Dat gaat iets wat je wel waarschijnlijk zal moeten nadenken over bij het coderen probleem van de vijf als je kies een hash table met aparte chaining benadering, die we later wel over. 

Maar is het de moeite waard om de lijst te houden gesorteerd en vervolgens in staat zijn om misschien hebben sneller zoekopdrachten? Of is het beter om snel in te voegen iets in constante runtime maar dan hebben langere zoeken? Dat is een afweging daar dat je krijgen om te beslissen wat is meer geschikt voor uw specifieke probleem. En er is niet per se een helemaal gelijk antwoord. Maar het is zeker een beslissing die je krijgt maken en waarschijnlijk goed te verdedigen dat in, zeg, een opmerking of twee waarom je kiest een over de ander. 

Tenslotte verwijderen. We hebben gezien verwijderen. Het is vergelijkbaar met het zoeken. We kijken voor het element. Zeggen dat we proberen te verwijderen zes. Dus vinden we zes hier. Het ding dat we moeten zorgen dat we te maken doen, is dat wat wijst naar zes - zoals we zien in stap twee hier beneden - wat wijst naar zes behoeften skip zes nu en worden veranderd in wat zes wijst. We willen niet de rest van steeds verweesde onze lijst door te vergeten om dat te stellen vorige pointer. En dan soms, afhankelijk op het programma, zullen ze gewoon dit knooppunt geheel te verwijderen. Soms wil je terug de waarde die in dit knooppunt. Dus dat is hoe het verwijderen werkt. Heeft u vragen over verwijderen? 

PUBLIEK: Dus als u gaat verwijderen , zou je gewoon gratis te gebruiken, omdat vermoedelijk was het malloced? 

JASON Hirschorn: Als u wilt vrijmaken iets dat is precies goed en je malloced het. Zeggen dat we wilden deze waarde terug te keren. We zouden terugkeren zes en dan vrij dit knooppunt en oproep gratis op. Of we zouden waarschijnlijk gratis bellen eerste en dan terug zes. 

OK. Dus laten we verder gaan om te oefenen codering. We gaan drie functies coderen. De eerste heet insert_node. Dus je hebt code die ik je gemaild, en als je dit ziet later kunt u de code in linked.c de CS50 website. Maar in linked.c, is er een aantal skelet code die al geschreven voor jou. En dan is er nog een paar functies je nodig hebt om te schrijven. 

Eerst gaan we schrijven insert_node. En wat doet insert_node wil zeggen voegt een geheel getal. En je geeft de integer in een gelinkte lijst. En in het bijzonder, moet u aan de lijst gesorteerd houden van klein naar groot. Ook hoeft u niet wilt steek geen duplicaten. Tot slot, zoals je kunt zien insert_node retourneert een bool. Dus jij moet de gebruiker te laten weten of het inzetstuk is succesvol door terug te keren waar of onwaar. Na afloop van dit programma - en voor deze fase je niet nodig hebt te maken over alles vrijmaken. Dus alles wat je doet is het nemen van een geheel getal en deze in een lijst. 

Dat is wat ik vraag je nu moet doen. Nogmaals, in de linked.c, die u allemaal hebben, is het skelet code. En je moet zien naar de bodem het monster functie verklaring. Echter, voordat je in het coderen in C, ik je ten zeerste aanmoedigen om te gaan door de stappen die we geweest zijn oefenen elke week. We hebben al meegemaakt een foto van deze. Dus je moet enig begrip hebben van hoe dit werkt. Maar ik wil u aanmoedigen om te schrijven sommige pseudocode voor de duik inch En we gaan over pseudocode als groep. En dan als je eenmaal hebt geschreven uw pseudocode, en zodra we hebben geschreven onze pseudocode als een groep, kunt u gaan in het coderen in C. 

Als een heads-up, de insert_node functie is waarschijnlijk de lastigste van de drie we gaan schrijven omdat ik additionele eisen toegevoegd de programmering, in het bijzonder dat je bent niet van plan om in te voegen duplicaten en dat de lijst moet gesorteerde blijven. Dus dit is een niet-triviale programma die je nodig hebt om te coderen. En waarom ga je niet vijf naar zeven minuten alleen maar om te werken aan de pseudocode en de code. En dan gaan we beginnen gaan als een groep. Nogmaals, als je gewoon vragen hebt steek je hand en ik zal rond komen. . 

We hebben ook over het algemeen doen deze - of ik niet expliciet je zegt kan werken met mensen. Maar het is duidelijk, ik u sterk aan te moedigen, als u vragen hebt, om de vragen buurman naast je zit of zelfs werken met iemand anders als u wilt. Dit hoeft niet aan een individu zijn stille activiteit. 

Laten we beginnen met het schrijven van een aantal pseudocode op het bord. Wie kan mij de eerste regel van geven pseudocode voor dit programma? Voor deze functie nogal - insert_node. Alden? 

PUBLIEK: Dus het eerste wat ik deed was maak een nieuwe verwijzing naar het knooppunt en ik geïnitialiseerd is die naar dezelfde ding die lijst wijst. 

JASON Hirschorn: OK. Dus je bent een nieuwe pointer aan de lijst, niet naar het knooppunt. 

PUBLIEK: Juist. Yeah. 

JASON Hirschorn: OK. En wat willen we doen? Wat is er daarna? Hoe zit het met de knoop? We hebben geen knooppunt. We hebben slechts een waarde. Willen we een knoop in te voegen, wat doen we eerst moeten doen voordat we kunnen zelfs denken over het plaatsen van het? 

PUBLIEK: Oh, sorry. we moeten ruimte malloc voor een knooppunt. 

JASON Hirschorn: Excellent. Laten we het doen - OK. Kan die hoge niet bereiken. OK. We gaan naar beneden te gaan, en vervolgens we gebruiken twee kolommen. Ik kan niet gaan, dat - OK. Maak een nieuw knooppunt. U kunt een andere wijzer maken naar de lijst of u kunt gewoon gebruik maken van de lijst als het bestaat. Je hoeft niet echt nodig om dat te doen. 

Zo creëren we een nieuw knooppunt. Geweldig. Dat is wat we eerst doen. Wat is het volgende? 

PUBLIEK: Wacht. Moeten we een nieuw knooppunt nu of moeten we wachten om ervoor te zorgen dat er is geen duplicaten van het knooppunt op de lijst voordat we creëren het? 

JASON Hirschorn: Goede vraag. Laten we stellen dat voor later, omdat de meerderheid van de tijd zullen we creëren een nieuw knooppunt. Dus we zullen hier te houden dat. Maar dat is een goede vraag. Als we creëren het en vinden we een duplicaat, wat moet we eerder terug doen? 

PUBLIEK: Bevrijd het. 

JASON Hirschorn: Yeah. Waarschijnlijk bevrijden. OK. Wat doen we nadat we maak een nieuw knooppunt? Annie? 

PUBLIEK: We zetten de nummer in de knoop? 

JASON Hirschorn: Precies. We zetten het nummer - we malloc ruimte. Ik ga laat dat allen als een regel. Maar je hebt gelijk. We malloc ruimte, en vervolgens we het aantal inch We kunnen zelfs stellen de aanwijzer deel ervan op null. Zo is het precies. En hoe zit het dan daarna? We trokken deze foto op het bord. Dus wat doen we? 

PUBLIEK: We gaan door de lijst. 

JASON Hirschorn: Ga door de lijst. OK. En wat doen we controleren op elk knooppunt. Kurt, wat doen we controleren gedurende elk knooppunt? 

PUBLIEK: Kijk of de n-waarde van dat knooppunt groter is dan de aangegeven waarde onze knooppunt. 

JASON Hirschorn: OK. Ik ga doen - ja, OK. Dus het is n - Ik ga zeggen als de waarde groter is dan dit knooppunt, wat doen we dan? 

PUBLIEK: Nou, dan voegen we het ding vlak voor dat. 

JASON Hirschorn: OK. Dus als het groter is dan deze, dan willen we voegen. Maar we willen het invoegen vlak voor omdat we ook zouden moeten bijhouden, dan, van wat vroeger was. Dus invoegen voor. Dus we waarschijnlijk iets gemist eerder. We moeten waarschijnlijk worden houden houden van wat er gaande is. Maar we zullen er terug te krijgen. Dus wat waarde lager is dan? Kurt, wat doen we als waarde kleiner dan? 

PUBLIEK: Dan moet je gewoon blijven gaan tenzij het de laatste. 

JASON Hirschorn: Dat vind ik leuk. Dus ga naar het volgende knooppunt. Tenzij het de laatste - we waarschijnlijk controleren op dat in de voorwaarden van een aandoening. Maar ja, volgende knoop. En dat wordt te laag, dus we zullen hier te verplaatsen. Maar als - kan iedereen dit zien? Als we gelijk wat doen we? Als de waarde we proberen in te voegen is gelijk aan de waarde van dit knooppunt? Yeah? 

PUBLIEK: [onverstaanbaar]. 

JASON Hirschorn: Yeah. Gezien deze - Marcus heeft gelijk. We konden misschien hebben gedaan iets anders. Maar gezien het feit dat we het hebben gemaakt, hier we moeten bevrijden en dan terug. Oh boy. Is dat beter? Hoe is dat? OK. Gratis en dan wat doen we terugkeren, [onverstaanbaar]? OK. Missen we iets? Waar gaan we bijhouden van de voorafgaande knoop? 

Publiek: Ik denk dat het zou gaan na een nieuwe node. 

JASON Hirschorn: OK. Dus aan het begin We zullen waarschijnlijk - ja, we kunnen een pointer te creëren om een ​​nieuwe knooppunt, als een vorig knooppunt pointer en een huidige knooppunt pointer. Dus laten we dat hier invoegen. Maak huidige en vorige verwijzingen naar de knooppunten. Maar toen we die pointers aanpassen? Waar doen we dat in de code? Jeff? 

PUBLIEK: - voorwaarden waarde? 

JASON Hirschorn: Welke een in het bijzonder? 

Publiek: Ik ben gewoon in de war. Als de waarde groter is dan dit knooppunt, betekent dat dan niet dat je wilt gaan naar het volgende knooppunt? 

JASON HIRSCHHORN: Dus als onze waarde is groter dan de waarde van deze knoop. 

PUBLIEK: Ja, dan zou je willen ga verder naar beneden de lijn, toch? 

JASON HIRSCHHORN: Juist. Zodat we niet plaatsen het hier. Als waarde dan dit knooppunt, dan gaan we naar de volgende knoop - of dan we invoegen voor. 

PUBLIEK: Wacht, wat is dit knooppunt en dat is de waarde? 

JASON HIRSCHHORN: Goede vraag. Waarde per deze functie definitie is wat we krijgen. Dus waarde is het aantal ons gegeven. Als de waarde minder is dan de knooppunt, tijd om in te voegen moeten we. Als de waarde groter is dan dit knooppunt, gaan we naar het volgende knooppunt. En terug naar de oorspronkelijke vraag, hoewel, waar - 

PUBLIEK: Als de waarde groter is dan dit knooppunt. 

JASON HIRSCHHORN: En zo wat doen we hier doen? Sweet. Dat is juist. Ik ben gewoon gaan schrijven Update pointers. Maar ja, met de huidige zou je het updaten om verwijzen naar de volgende. Alles wat we mist? Dus ga ik dit typ coderen in gedit. En terwijl ik dit doen, kunt u een hebt paar minuten om te werken aan de codering dit in C. 

Dus ik heb de ingang van de pseudocode. Een korte opmerking voordat we beginnen. We kunnen niet in staat om volledig te afmaken in alle drie van deze functies. Er is juiste oplossing te dat ik zal een e-mail naar jullie na sectie, en het zal worden geplaatst op CS50.net. Dus ik hoef je niet aan te moedigen om gaan kijken naar de secties. Ik moedig u aan om deze te proberen op uw bezitten, en gebruik vervolgens de de praktijk problemen om je antwoorden te controleren. Deze zijn allemaal ontworpen om nauw betreffen en zich aan welke je hoeft te doen aan het probleem set. Dus ik hoef u aanraden om dit te oefenen op uw eigen en gebruik vervolgens de code te Controleer uw antwoorden. Omdat ik wil overgaan tot hash tabellen op een bepaald punt in de sectie. Dus we kunnen niet door dit alles. Maar we zullen zo veel we kunnen nu doen. 

OK. Laten we beginnen. Asam, hoe creëren we een nieuw knooppunt? 

PUBLIEK: U hoeft struct *. 

JASON HIRSCHHORN: Dus we hebben dat hier. Oh, sorry. U zei struct *. 

PUBLIEK: En dan [? soort?] knoop of c knooppunt. 

JASON HIRSCHHORN: OK. Ik ga noemen new_node zodat we kunnen blijven consistent. 

PUBLIEK: En u wilt dat instellen aan het hoofd, het eerste knooppunt. 

JASON HIRSCHHORN: OK. Dus nu deze wijst naar - dus dit heeft een nieuw knooppunt nog niet gemaakt. Dit is gewoon te wijzen op de eerste knooppunt in de lijst. Hoe maak ik een nieuw knooppunt? Als ik de ruimte om een ​​nieuw knooppunt te maken. Malloc. En hoe groot? 

Publiek: De grootte van de structuur. 

JASON HIRSCHHORN: De grootte van de structuur. En wat is de structuur genoemd? 

PUBLIEK: Node? 

JASON HIRSCHHORN: Node. Dus malloc (sizeof (node)); geeft ons de ruimte. En is deze lijn - een ding is onjuist op deze lijn. Is new_node een pointer naar een struct? Dat is een algemene naam. Wat is het - knooppunt, precies. Het is een knooppunt *. En wat doen we direct na we malloc iets, Asan? Wat is het eerste wat we doen? Wat als het niet werkt? 

PUBLIEK: Oh, controleer dan of het wijst op het knooppunt? 

JASON HIRSCHHORN: Precies. Dus als je new_node gelijk gelijken null, wat doen we? Dit geeft een bool, deze functie. Precies. Ziet er goed uit. Alles om er toe te voegen? We zullen dingen toe te voegen aan het eind. Maar dat tot nu toe ziet er goed uit. Maak huidige en vorige pointers. Michael, hoe doe ik dit? 

PUBLIEK: U zou hebben om een ​​knooppunt te doen *. Je zou men niet maken voor new_node maar voor de nodes we al hebben. 

JASON HIRSCHHORN: OK. Zodat we het huidige knooppunt bent. Ik zal die curr bellen. Oke. We hebben besloten dat we willen houden twee omdat we moeten weten wat is voordat het. Wat krijgen ze geïnitialiseerd? 

PUBLIEK: Hun waarde in onze lijst. 

JASON HIRSCHHORN: Dus wat is de eerste wat op onze lijst? Of hoe weten we waar de begin van onze lijst is? 

PUBLIEK: Is het niet voorbij in de functie? 

JASON HIRSCHHORN: Juist. Het werd doorgegeven in hier. Dus als het doorgegeven aan de functie, de start van de lijst, wat moeten we ingesteld stroom gelijk aan? 

PUBLIEK: List. 

JASON HIRSCHHORN: List. Zo is het precies. Nu heeft het adres het begin van onze lijst. En hoe zit het met de vorige? 

PUBLIEK: Lijst min een? 

JASON HIRSCHHORN: Er is niets ervoor. Dus wat kunnen we doen om niets te betekenen? 

PUBLIEK: Null. 

JASON HIRSCHHORN: Yeah. Dat klinkt als een goed idee. Perfect. Dank u. Ga door de lijst. Constantijn, hoe lang gaan we om door de lijst? 

PUBLIEK: totdat we bij nul. 

JASON HIRSCHHORN: OK. Dus als, terwijl, voor loop. Wat doen wij? 

PUBLIEK: Misschien een lus? 

JASON HIRSCHHORN: Laten we doen een lus. OK. 

Publiek: En wij zeggen - totdat de huidige wijzer is niet gelijk aan nul. 

JASON HIRSCHHORN: Dus als we weten dat de staat, hoe kunnen we schrijven een lus gebaseerd off die voorwaarde. Wat voor een lus moeten we gebruiken? 

PUBLIEK: Hoewel. 

JASON HIRSCHHORN: Yeah. Dat heeft meer zin gebaseerd af van wat je zei. Als we willen gewoon naar we gaan het zou weet alleen dat ding, zou het zinvol om een ​​while lus doen. Terwijl de huidige is niet gelijk aan nul, als de waarde lager is dan dit knooppunt. Akshar, geef mij deze lijn. 

PUBLIEK: Als de huidige-> n n minder dan waarde. Of omgekeerd dat. Schakel die beugel. 

JASON HIRSCHHORN: Sorry. 

PUBLIEK: Verander de beugel. 

JASON HIRSCHHORN: Dus als het groter dan waarde. Want dat is verwarrend met de comment hierboven, ga ik dat doen. Maar ja. Als onze waarde lager is dan deze knooppunt, wat doen we? Oh. Ik heb het hier. Invoegen voor. OK. Hoe doen we dat? 

PUBLIEK: Is het nog me? 

JASON HIRSCHHORN: Yeah. 

PUBLIEK: U - new_node-> volgende. 

JASON HIRSCHHORN: Dus wat is dat gaat gelijk? 

Publiek: Het gaat gelijk stroom. 

JASON HIRSCHHORN: Precies. En dus is de andere - wat hebben we nodig om te werken? 

PUBLIEK: Controleer of verleden gelijk nul. 

JASON HIRSCHHORN: als vorige - dus als vorige gelijk nul. 

PUBLIEK: Dat betekent dat het gaat het hoofd worden. 

JASON HIRSCHHORN: Dat betekent het is geworden het hoofd. Dus wat doen we dan? 

PUBLIEK: Wij doen hoofd gelijk new_node. 

JASON HIRSCHHORN: Hoofd gelijk new_node. En waarom hier het hoofd, geen lijst? 

PUBLIEK: Omdat hoofd is een wereldwijde variabele, die de startplaats. 

JASON HIRSCHHORN: Zoet. OK. En - 

PUBLIEK: Dan heb je anders vorige-> volgende evenaart new_node. En dan terugkeren waar je. 

JASON HIRSCHHORN: Waar doen we new_node einde? 

Publiek: Ik zou - Ik dat in het begin. 

JASON HIRSCHHORN: Dus welke lijn? 

PUBLIEK: Na de instructie if controleren of het bekend is. 

JASON HIRSCHHORN: Right here? 

PUBLIEK: ik zou doen new_node-> n is gelijk aan de waarde. 

JASON HIRSCHHORN: Klinkt goed. Waarschijnlijk is het logisch - dat doen we niet moet weten wat lijst we op omdat we alleen te maken met een lijst. Dus een betere functie verklaring voor dit is gewoon om zich te ontdoen van deze geheel en plaatst u gewoon een waarde in het hoofd. We hoeven niet eens te weten wat lijst we binnen Maar ik zal het blijven voor nu en dan veranderen bij het updaten de dia's en code. Dus dat ziet er goed uit voor nu. Als de waarde - die deze lijn kan doen? Als - wat doen wij hier doen, Noah. 

PUBLIEK: Als de waarde groter is dan curr-> n - 

JASON HIRSCHHORN: Hoe gaan we naar de volgende knoop? 

PUBLIEK: Curr-> n gelijk aan new_node. 

JASON HIRSCHHORN: Dus n is welk deel van de structuur? De integer. En new_node is een pointer naar een knooppunt. Dus welk deel van curr moeten we updaten? Zo niet n, wat is dan het andere deel? Noah, wat is het andere deel. 

PUBLIEK: Oh, de volgende. 

JASON HIRSCHHORN: Next, precies. Precies. Vervolgens is de juiste is. En wat hebben we nodig bij te werken, Noah? 

Publiek: De wijzers. 

JASON HIRSCHHORN: Dus we bijgewerkt stroom. 

PUBLIEK: Vorige-> volgende. 

JASON HIRSCHHORN: Yeah. OK, we pauzeren. Wie kan ons helpen hier? Manu, wat moeten we doen? 

PUBLIEK: Je moet instellen het gelijk aan curr-> volgende. Maar dat doen voordat de vorige regel. 

JASON HIRSCHHORN: OK. Iets anders? Akshar. 

Publiek: Ik denk niet dat je bent bedoeld om curr-> volgende veranderen. Ik denk dat je bedoeld om curr gelijken doen curr-> Volgende om naar het volgende knooppunt. 

JASON HIRSCHHORN: Het spijt me, waar? Op welke lijn? Deze lijn? 

PUBLIEK: Ja. Maak curr gelijk curr-> volgende. 

JASON HIRSCHHORN: Dus dat klopt omdat de huidige is een pointer naar een knooppunt. En we willen dat het wijzen op de volgende knooppunt van wat krijgt momenteel wees. Curr zelf heeft een volgende. Maar als we curr.next updaten, we zou het bijwerken van de eigenlijke noot zelf, niet waar wijzer wees. Hoe zit het met deze lijn, dat wel. Avi? 

PUBLIEK: Vorige-> volgende evenaart curr. 

JASON HIRSCHHORN: Dus nogmaals, als vorige is een pointer naar een knooppunt, vorige-> volgende is de werkelijke aanwijzer in het knooppunt. Dus dit zou het bijwerken van een aanwijzer in een knoop te curr. We willen niet werken een pointer in een knoop. We willen updaten vorige. Dus hoe kunnen we dat doen? 

Publiek: Het zou gewoon vorige. 

JASON HIRSCHHORN: Juist. Vorig is een pointer naar een knooppunt. Nu zijn we het omzetten naar een nieuwe pointer naar een knooppunt. OK Laten we naar beneden gaan. Tot slot is deze laatste voorwaarde. Jeff, wat doen we hier doen? 

PUBLIEK: Als de waarde gelijk aan curr-> n. 

JASON HIRSCHHORN: Sorry. Oh mijn god. Wat? Value == curr-> n. Wat doen wij? 

PUBLIEK: Je zou onze new_node bevrijden, en dan zou je valse terugkeren. 

JASON HIRSCHHORN: Dit is wat we tot nu toe geschreven. Heeft iemand iets toe te voegen voordat we te maken? OK. Laten we het proberen. Controle kan het einde te bereiken van een niet-lege functie. Avi, wat gebeurt er? 

PUBLIEK: Bent u verondersteld om rendement te zetten ware buiten de while loop? 

JASON HIRSCHHORN: Ik weet het niet. Wil je dat ik aan? 

PUBLIEK: Never mind. Nee. 

JASON HIRSCHHORN: Akshar? 

Publiek: Ik denk dat je bedoeld om zet return valse aan het eind van de while-lus. 

JASON HIRSCHHORN: Dus waar wil je het gaan? 

PUBLIEK: Net buiten de while lus. Dus als je de while lus die middelen te verlaten dat je het einde hebt bereikt en niets is gebeurd. 

JASON HIRSCHHORN: OK. Dus wat doen we hier? 

PUBLIEK: U return false daar ook. 

JASON HIRSCHHORN: Oh, we doe het in beide plaatsen? 

PUBLIEK: Ja. 

JASON HIRSCHHORN: OK. Moeten we gaan? Oh mijn god. Het spijt me. Ik verontschuldig me voor het scherm. Het is een soort van freaken op ons. Dus kies een optie. Nul, volgens de code, stopt het programma. Men voegt iets. Laten we drie plaatsen. De insert is mislukt. Ik ga om uit te printen. Ik heb helemaal niets. OK. Misschien dat was gewoon een toevalstreffer. Plaats een. Niet succesvol. OK. Laten we lopen door GDB heel snel om te controleren wat er gaande is. 

Vergeet gdb. / De naam van uw programma brengt ons in GDB. Is dat een veel te hanteren? De knipperende? Waarschijnlijk. Sluit je ogen en haal een paar keer diep ademt als je moe naar te kijken. Ik ben in GDB. Wat is het eerste wat ik doe in GDB? We moeten uitzoeken wat hier aan de hand. Laten we eens kijken. We hebben zes minuten figuur te komen wat er gaande is. Breken belangrijkste. En wat moet ik doen? Carlos? Run. OK. Laten we kiezen voor een optie. En wat doet N doen? Volgende. Yeah. 

PUBLIEK: Heb je niet vergeten - heb je niet zeggen dat de kop, het was geïnitialiseerd op nul bij het begin. Maar ik dacht dat je zei dat was OK. 

JASON HIRSCHHORN: Laten we gaan - laten we eens kijken in GDB, en dan gaan we terug. Maar het klinkt alsof je al hebt een aantal ideeën over wat er gaande is. Dus we willen iets in te voegen. OK. Wij voegen. Vul een int. We zullen drie plaatsen. En dan ben ik op deze lijn. Hoe ga ik beginnen met debuggen de insert bekende functie? Oh mijn god. Dat is veel. Wordt dat freaking out veel? 

PUBLIEK: Oh, het stierf. 

JASON HIRSCHHORN: Ik heb net trok het uit. OK. 

PUBLIEK: Misschien is het de andere uiteinde van de draad. 

JASON HIRSCHHORN: Wow. Dus de onderste regel - wat zeg je? 

Publiek: Ik zei dat de ironie van technische moeilijkheden in deze klasse. 

JASON HIRSCHHORN: Ik weet het. Als ik had controle over dat deel. [Onverstaanbaar] Dat klinkt geweldig. Waarom gaan jullie niet gaan nadenken over wat we konden verkeerd hebben gedaan, en we zullen terug in 90 seconden. 

Avica, ga ik je vragen hoe om te gaan binnen insert_node te debuggen. Dus dit is waar we het laatst gebleven was. Hoe kan ik naar binnen insert_node, Avica, om te onderzoeken wat er aan de hand? Wat GDB commando? Break zou me niet binnen. Heeft Marquise weten? 

PUBLIEK: Wat? 

JASON HIRSCHHORN: Wat GDB commando Ik gebruik te gaan binnen deze functie? 

PUBLIEK: Step? 

JASON HIRSCHHORN: Stap via S. Dat binnenkant kost me. OK. New_node mallocing wat ruimte. Dat alles lijkt op haar gaan. Laten we eens onderzoeken new_node. Het kreeg een aantal geheugen adres. Laten we eens kijken - dat is allemaal correct. Dus alles lijkt hier correct werken. 

Publiek: Wat is het verschil tussen P en scherm? 

JASON HIRSCHHORN: P staat voor print. En dus je vraagt ​​wat is de verschil tussen dat en dit? In dit geval niets. Meestal zijn er wel enkele verschillen. En moet je kijken in het GDB handleiding. Maar in dit geval niets. We hebben de neiging om afdruk te gebruiken, maar, omdat we hoeven niet veel meer doen dan afdrukken van een enkele waarde. 

OK. Dus we zijn op lijn 80 van onze code, het instellen van knooppunt * curr gelijk aan lijst. Laten we uitprinten curr. Het is gelijk aan de lijst. Sweet. Wacht. Het is gelijk iets. Dat lijkt niet juist. Daar gaan we. Het is omdat in GDB, rechts, indien het is de lijn je op het is nog niet uitgevoerd. Dus je moet eigenlijk typen naast de lijn uit te voeren voordat het zien van de resultaten. Dus hier zijn we. We hebben net deze lijn uitgevoerd, vorige gelijk aan null. Dus nogmaals, als we drukken vorige zullen we niet zien iets vreemds. Maar als we daadwerkelijk uit te voeren dat lijn, dan zullen we zien dat die lijn gewerkt. 

Dus we hebben curr. Dat zijn allebei goed. Rechts? Nu zijn we op deze lijn hier. Terwijl curr is niet gelijk aan nul. Nou, wat doet curr gelijk? We zagen het gewoon geëvenaard null. We uitgeprint. Ik zal het er weer uit te printen. Zo is dat, terwijl lus gaan voeren? 

PUBLIEK: Nee 

JASON HIRSCHHORN: Zodat wanneer ik typte lijn, zie je sprongen we de hele weg tot op de bodem, return false. En dan gaan we return false en ga terug naar ons programma en uiteindelijk uit te printen, zoals we zagen, de insert was niet succesvol. Dus, iemand enig idee over wat we moeten doen om dit op te lossen? Ik ga wachten tot ik zie een paar handen gaan omhoog. We hebben dit niet uitvoeren. Houd in gedachten, dit was de eerste wat we aan het doen waren. Ik ben niet van plan om een ​​paar te doen. Ik ga een paar doen. Omdat een paar betekent twee. Ik wacht op meer dan twee. 

De eerste insertie, curr, standaard is gelijk aan null. En alleen deze lus voert als curr is niet nul. Dus hoe kan ik rond dit? Ik zie drie handen. Ik wacht op meer dan drie. Marcus, wat denk je? 

PUBLIEK: Nou, als je het nodig hebt om voeren meer dan eens, je gewoon veranderen in een do-while lus. 

JASON HIRSCHHORN: OK. Zal dat ons probleem op te lossen, hoewel? 

PUBLIEK: In dit geval is geen gevolg van het feit dat de lijst leeg. Dus dan heb je waarschijnlijk gewoon moet toevoegen een verklaring dat als de lus uitgangen dan moet je op het einde van de lijst, op welk punt je kan gewoon invoegen. 

JASON HIRSCHHORN: Dat vind ik leuk. Dat klinkt logisch. Als de lus verlaat - want het zal hier return false. Dus als de lus verlaat, dan zijn we op het einde van de lijst, of misschien de starten van een lijst als er niets in het, wat hetzelfde is als het einde. Dus nu willen we voegen hier iets. Dus hoe die code kijken, Marcus? 

PUBLIEK: Als je al het knooppunt malloced, kon je gewoon zeggen new_node-> volgende is gelijk nul, omdat het moet eind. Of new_node-> volgende gelijk nul. 

JASON HIRSCHHORN: OK. Sorry. New_node-> volgende evenaart null want we zijn aan het einde. Dat plaatst hem nog niet binnen Hoe zetten we het in de lijst? Rechts. Dat is gewoon de oprichting ervan gelijk aan. Geen hoe kunnen we eigenlijk zet het in de lijst? Wat wijst naar de einde van de lijst? 

PUBLIEK: Head. 

JASON HIRSCHHORN: Sorry? 

PUBLIEK: Hoofd wijst aan het einde van de lijst. 

JASON HIRSCHHORN: Als er niets in de lijst, wordt het hoofd wijst naar de einde van de lijst. Dus dat zal werken voor de eerste plaatsing. Hoe zit het als er een paar dingen in de lijst? Dan we willen niet instellen ga gelijk aan new_node. Wat willen we daar doen? Yeah? Waarschijnlijk vorige. Zal dat werken? Bedenk dat vorige is gewoon een pointer naar een knooppunt. En eerdere is een lokale variabele. Dus deze lijn zal een lokale variabele in te stellen, previous gelijk aan of dat naar het nieuwe knooppunt. Dat zal niet echt zet het in onze lijst, dat wel. Hoe kunnen we het in onze lijst? Akchar? 

Publiek: Ik denk dat je do huidige-> volgende. 

JASON HIRSCHHORN: OK. curr-> volgende. Dus nogmaals, de enige reden waarom we naar beneden hier is, wat doet stroom gelijk? 

PUBLIEK: Is gelijk aan null. 

JASON HIRSCHHORN: En wat gebeurt er als we dat doen null-> volgende? Wat doen we gaan krijgen? We zullen een segmentation fault krijgen. 

PUBLIEK: Do curr gelijk aan null. 

JASON HIRSCHHORN: Dat is hetzelfde als vorige, hoewel, omdat er een lokale variabele we bent instelling gelijk aan deze nieuwe knoop. Laten we teruggaan naar onze foto van het plaatsen van iets. Zeggen dat we het invoegen aan het einde van de lijst, dus hier. We hebben een actuele pointer dat is wijzend op null en een vorig punt die wijst naar 8. Dus wat hebben we nodig om te werken, Avi? 

PUBLIEK: Vorige-> volgende? 

JASON HIRSCHHORN: Vorige-> volgende is wat we willen werken, want dat daadwerkelijk plaatst u deze op het einde van de lijst. We hebben nog steeds een bug, hoewel, dat we gaan tegenkomen. Wat is dat fout? Yeah? 

PUBLIEK: Het gaat om terug te keren vals in dit geval? 

JASON HIRSCHHORN: Oh, is wordt gaan return false. Maar er is nog een bug. Dus we moeten in ruil daarvoor trouw aan zetten. 

PUBLIEK: Heeft vorige nog steeds gelijk null aan de top van de lijst? 

JASON HIRSCHHORN: Dus vorige stilstaand gelijk aan nul aan het begin. Dus hoe kunnen we meer dan dat? Yeah? 

Publiek: Ik denk dat je een controle te doen voordat de while lus om te zien of het een lege lijst. 

JASON HIRSCHHORN: OK. Dus laten we gaan hier. Doe een cheque. Als - 

PUBLIEK: Dus als hoofd gelijk gelijk aan null. 

JASON HIRSCHHORN: Als hoofd gelijk gelijk aan null - dat zal ons vertellen of het een lege lijst. 

PUBLIEK: En dan heb je do hoofd is gelijk aan nieuw. 

JASON HIRSCHHORN: Hoofd gelijk new_node? En wat moeten we doen? 

PUBLIEK: En dan heb je echt terug. 

JASON HIRSCHHORN: Niet helemaal. We missen een stap. 

PUBLIEK: new_node volgende moet wijzen op null. 

JASON HIRSCHHORN: Precies, Alden. En dan kunnen we echt terug. OK. Maar het is nog steeds een goed idee om dingen te doen aan het einde van de lijst, toch? Oke. We zouden eigenlijk nog wel krijgen aan het einde van de lijst. Dus is deze code prima als we op de het einde van de lijst en er zijn enkele dingen in de lijst? Rechts? Want we hebben nog idee Marcus. We zouden deze lus te verlaten, omdat we zijn aan het einde van de lijst. Dus doen we nog steeds dit willen coderen hier beneden? 

PUBLIEK: Ja. 

JASON HIRSCHHORN: Yeah. En wat hebben we nodig om dit te veranderen naar? True. Klinkt dat goed iedereen tot nu toe? Iemand enig - Avi, doe je iets toevoegen? 

PUBLIEK: Nee 

JASON HIRSCHHORN: OK. Dus we hebben een paar wijzigingen. We hebben deze controle gedaan voordat we ging voor een lege lijst. Dus we hebben gezorgd een lege lijst. En hier hebben we de zorg van het plaatsen van iets aan het einde van de lijst. Dus het lijkt erop dat deze while lus nemen verzorgen van de dingen in tussen, ergens in de lijst als er zijn dingen in de lijst. 

OK. Laten we dit programma opnieuw uit te voeren. Niet succesvol. 

PUBLIEK: U heeft het niet gehaald. 

JASON HIRSCHHORN: Oh, Ik heb het niet gehaald. Goed punt, Michael. Laten we eerst nog te maken met elkaar verbonden. Lijn 87 is er een fout. Lijn 87. Alden, dit was de lijn die je me gaf. Wat is er mis? 

Publiek: Het moet op null. 

JASON HIRSCHHORN: Excellent. Precies goed. Het moet nul zijn. Laten we weer. Samen te stellen. OK. Laten we drie plaatsen. De insert is geslaagd. Laten printen. O, als we konden controleren. Maar we hebben niet gedaan afdrukken nog functie. Laten we iets anders gaan. Wat moeten we voeren? 

PUBLIEK: Zeven. 

JASON HIRSCHHORN: Seven? 

PUBLIEK: Ja. 

JASON HIRSCHHORN: We hebben een seg fout. Dus we hebben een, maar we duidelijk kan niet twee. Het is 05:07. Dus we konden deze debug gedurende drie minuten. Maar ik ga om ons hier te vertrekken en gaan naar tabellen hash. Maar nogmaals, de antwoorden voor deze code Ik zal het e-mail naar u in een beetje. We zijn erg dicht bij. Ik je ten zeerste aan te moedigen om erachter te komen wat er hier op en zet het vast. Dus ik zal u e-mail de code als goed plus de oplossing - waarschijnlijk de oplossing later. Eerst deze code. 

Het andere wat ik wil doen voordat we afwerking is we hebben niets bevrijd. Dus ik wil je laten zien wat valgrind eruit ziet. Als we lopen valgrind grenzen op ons programma. / gekoppeld. Ook volgens deze dia, we moet valgrind lopen met een soort van Geef in dit geval - Lek-check = vol. Dus laten we schrijven valgrind - Lek-check = vol. Dus dit zal valgrind draaien op ons programma. En nu het programma daadwerkelijk wordt uitgevoerd. Dus we gaan om het uit te voeren, net als vóór, zet iets in Ik ga in drie zetten. Dat werkt. Ik ga niet proberen iets te zetten anders want we gaan naar krijgen een seg vals in dat geval. Dus ik ga gewoon om te stoppen. 

En nu zie je beneden lekken en heap samenvatting. Dit zijn de goede dingen die u wilt controleren. Dus de hoop samenvatting - het zegt, in gebruik bij afslag - acht bits in een blok. Dat een blok is de knooppunt we malloced. Michael, je zei eerder een knooppunt is acht beten omdat het de integer en de aanwijzer. Dus dat is onze knooppunt. En dan staat we gebruikten malloc zeven keer en we bevrijd iets zes keer. Maar we nooit vrij heet, dus ik heb geen idee wat dit is het over. 

Maar het volstaat te zeggen dat wanneer uw programma wordt uitgevoerd, wordt malloc geroepen in sommige andere plaatsen die we geen zorgen te maken over. Dus malloc werd waarschijnlijk genoemd op sommige plaatsen. We hebben geen zorgen te maken waar. Maar dit is echt ons. Deze eerste lijn is met ons. We vertrokken dat blok. En je kunt zien dat hier in het lek samenvatting. Nog steeds bereikbaar - acht bits in een blok. Dit betekent dat het geheugen - we hebben dat geheugen gelekt. Zeker verloren - iets voorgoed verloren is gegaan. Over het algemeen zul je niet zie niets daar. Nog steeds bereikbaar is over het algemeen waar je zult dingen zien, waar je wilt te kijken om te zien welke code je moet hebben bevrijd, maar je vergat te bevrijden. 

En als dit niet het geval was, als we dat alles gratis, we kunnen controleren dat. Laten we gewoon het programma uit te voeren niet zetten in iets. Je zult zien hier in gebruik bij afslag - nul bytes nul blokken. Dat betekent dat we hadden niets meer wanneer dit programma verlaten. Dus voordat u in pset6, lopen valgrind en zorg ervoor dat u niet hoeft alle vormen van geheugen lekken in uw programma. Als u vragen heeft met valgrind, voel je vrij om uit te reiken. Maar dit is hoe je het gebruikt. Heel eenvoudig - kijk of je in gebruik hebben bij afslag - elke bytes alle blokken. 

Dus we waren bezig met insert knooppunt. Ik had twee andere functies hier - afdrukken knooppunten en vrije knopen. Nogmaals, dit zijn functies die goed te zijn voor u om te oefenen omdat ze je niet alleen helpen met deze steekproef oefeningen, maar ook het probleem stellen. Ze kaart op vrij nauw om dingen je gaat moeten doen in de probleem stellen. Maar ik wil ervoor zorgen dat we ingaan op alles. En hash tabellen zijn ook van cruciaal belang om wat we doen in deze sectie week - of het probleem set. 

Dus we gaan naar de sectie afmaken praten over hash tables. Als u merkt dat ik een beetje hash table. Dat is niet waar we het over, echter. We hebben het over een andere type hash tabellen. En in de kern, een hash table is niets meer dan een serie plus een hash-functie. We gaan voor een beetje te praten alleen maar om zorgen dat iedereen begrijpt wat een hash-functie is. En ik zeg je nu dat het niets meer dan twee dingen - een array en een hash-functie. En hier zijn de stappen door waarin deze actief is. 

Er is ons aanbod. Daar is onze functie. Met name moet hash functies doe een paar dingen met dit. Ik ga specifiek hebben over dit probleem te stellen. Het gaat waarschijnlijk nemen in een string. En wat gaat het om terug te keren? Welke gegevens soort? Alden? Uw hash-functie terug te keren? Een geheel getal. Dus dit is wat de hash tabel bestaat uit - een tafel in de vorm van een matrix en een hash-functie. Hoe het werkt? Het werkt in drie stappen. Wij geven het een sleutel. In dit geval, zullen we het een string. We noemen de hash-functie per stap een op de sleutel en we krijgen een waarde. 

Concreet zullen we zeggen krijgen we een integer. Dat integer, kunnen de zeer specifieke grenzen aan wat dat getal kan zijn. In dit voorbeeld ons aanbod is van grote drie. Wat nummers die geheel getal zijn. Wat is het bereik van geldige waarden voor dat integer, de return type van deze hash-functie? Nul, een en twee. Het punt van de hash-functie is achterhalen van de plaats in de array waar onze sleutel gaat. Er zijn slechts drie mogelijke plaatsen hier - nul, een of twee. Dus deze functie beter rendement nul, een of twee. Sommige geldig indice in deze array. 

En afhankelijk van waar het terugkeert, je kunt er matrix zien geopend beugel de waarde. Dat is waar we de sleutel. Dus we gooien in de pompoen, we uit nul. Bij serie beugel 0, hebben we pompoen. We gooien bij katten, we uit een. We zetten kat in een. We zetten in spin. We stappen uit twee. We zetten spin in serie beugel twee. Het zou zo mooi zijn als het werkte als dat. Maar helaas, zoals we zullen zien, het is een beetje ingewikkelder. 

Voordat we er, welke vragen over deze fundamentele set-up van een hash table? Dit is een afbeelding precies wat we trokken op het bord. Maar omdat we trokken het op het bord, ik ga niet verder in te gaan. Wezen toetsen, de magische zwarte doos - of in dit geval, blauwgroen box - van een hash-functie zet ze in emmers. En in dit voorbeeld zijn we niet zetten de naam. We zetten de bijbehorende telefoon nummer van de naam in de emmer. Maar je kon heel goed alleen zet de naam in de emmer. 

Dit is slechts een beeld van wat stelden we op het bord. We hebben mogelijke valkuilen, dat wel. Er zijn twee name dia's die ik wil gaan over. De eerste is om een hash-functie. Dus vroeg ik de vraag, wat maakt een goede hash-functie? Ik geef twee antwoorden. De eerste is dat het deterministisch. In het kader van hashfuncties, wat betekent dit? Ja? 

Publiek: Het kan u de index in constante tijd? 

JASON HIRSCHHORN: Dat is niet wat het betekent. Maar dat is een goede gok. Iemand anders nog een gok wat dit inhoudt? Dat een goede hash-functie deterministisch? Annie? 

PUBLIEK: Dat een toets slechts een kaart kan worden gebracht om een ​​plaats in de hash tabel. 

JASON HIRSCHHORN: Dat is precies goed. Elke keer als je in pompoen, het altijd nul terug. Als je in pompoen en je hash functie geeft nul, maar heeft een kans op terugkeer iets anders groter dan nul - dus misschien kan het een soms terug of twee andere keren - dat geen goede hashfunctie. Je hebt helemaal gelijk. Uw hash-functie moet de terugkeer van de exact dezelfde integer, in dit geval, voor exact dezelfde string. 

Misschien geeft het exact dezelfde integer voor exact dezelfde snaar ongeacht de kapitalisatie. Maar in dat geval is het nog steeds deterministische omdat meerdere dingen worden afgebeeld op dezelfde waarde. Dat is prima. Zolang er slechts een output voor een bepaald ingangssignaal. 

OK. Het tweede ding is dat het retourneert geldig indices. We opgevoed dat eerder. Deze hash-functie - oh boy - een hash-functie moet terug geldig indices. Dat zeggen - laten we terugkeren naar dit voorbeeld gaan. Mijn hash-functie telt de letters in het woord. Dat is de hash-functie. En geeft dat integer. Dus als ik het woord A, het is gaat naar een terug te keren. En het gaat om een ​​recht hier te zetten. Wat als ik in het woord vleermuis? Het gaat om drie terugkeren. Waar komt knuppel heen? 

Het past niet. Maar het moet ergens heen. Dit is mijn hash table immers, en alles moet ergens heen. Dus waar moet bat gaan? Elke gedachten? Gissingen? Goede schattingen? 

PUBLIEK: Zero. 

JASON HIRSCHHORN: Waarom nul? 

PUBLIEK: Omdat drie modulo drie nul is? 

JASON HIRSCHHORN: Drie modulo drie nul is. Dat is een grote gok, en dat klopt. Dus in dit geval moet waarschijnlijk gaan op nul. Dus een goede manier om ervoor te zorgen dat deze hash functie geeft alleen geldig indices wordt het modulo door de grootte van de tabel. Als je modulo wat dit rendement door drie, je bent altijd gaat krijgen iets tussen nul, een en twee. En als dit altijd terugkeert zeven, en je altijd modulo door drie, je bent altijd naar hetzelfde te krijgen. 

Dus het is nog steeds deterministische als je modulo. Maar dat zal ervoor zorgen dat u nooit iets te krijgen - een ongeldige industrie. In het algemeen moet dat modulo gebeuren in je hash-functie. Dus je hoeft geen zorgen te maken over dit. Je kan het gewoon ervoor zorgen dat dit is een geldige indice. Heeft u vragen over dit potentiële valkuil? 

OK. En daar gaan we. Volgende potentiële valkuil, en dit is de grote. Wat gebeurt er als twee sleutels kaart op dezelfde waarde? Dus zijn er twee manieren om dit te behandelen. De eerste wordt lineair genoemd sonderen, dat ben ik niet van plan om over te gaan. Maar je moet bekend zijn met hoe dat werkt en wat dat is. 

De tweede ga ik om over te gaan want dat is degene die vele mensen zullen waarschijnlijk uiteindelijk beslissen om te gebruiken in hun probleem set. Natuurlijk hoef je niet hoeft te doen. Maar voor het probleem set, veel mensen de neiging om te kiezen voor een hash tabel te maken met aparte chaining te implementeren hun woordenboek. Dus we gaan te gaan over wat het betekent een hash tabel met aparte chaining. 

Dus ik zet in pompoen. Het nul terug. En ik zet hier pompoen. Dan zet ik in - Wat is een ander Halloween-thema-ding? 

PUBLIEK: Candy. 

JASON HIRSCHHORN: Candy! Dat is een geweldig. Ik heb in snoep en snoep geeft me ook nihil. Wat moet ik doen? Het even welke ideeën? Omdat je alle soort van weten wat aparte chaining is. Dus enig idee wat te doen? Yeah. 

PUBLIEK: Aanbrengen van de snaar eigenlijk in de hash tabel. 

JASON HIRSCHHORN: Dus we gaan trekken het goede idee hier. OK. 

PUBLIEK: Laat de hash [Onverstaanbaar] de pointer die verwijst naar het begin van een lijst. En dan hebben pompoen zijn de eerste waarde in dat gelinkte lijst en snoep zijn de tweede waarde in dat gelinkte lijst. 

JASON HIRSCHHORN: OK. Marcus, die was uitstekend. Ik ga breken die naar beneden. Marcus zegt niet overschrijven pompoen. Dat zou slecht zijn. Doe geen snoep ergens anders. We gaan ze allebei op nul gezet. Maar we gaan om te gaan met waardoor ze op nul door creëren van een lijst op nul. En we gaan een lijst maken alles wat toegewezen aan nul. En de beste manier leerden we creëren een lijst die kan groeien en krimpen dynamisch niet binnen andere array. Dus geen multi-dimensionale array. Maar om gewoon een gelinkte lijst. 

Dus wat hij voorgesteld - Ik ga een nieuwe krijgen - is het creëren van een array met pointers, een array van pointers. OK. Enig idee of hint wat het type van deze aanwijzingen moeten zijn? Marcus? 

PUBLIEK: Pointers naar - 

JASON HIRSCHHORN: Omdat je zei een gelinkte lijst, dus - 

PUBLIEK: Node pointers? 

JASON HIRSCHHORN: Node pointers. Als de dingen in ons verbonden lijst zijn knooppunten dan ze moet knooppunt pointers. En wat doen ze in eerste instantie gelijk? 

PUBLIEK: Null. 

JASON HIRSCHHORN: Null. Er is dus onze lege ding. Pompoen rendement nul. Wat doen wij? Loop me er doorheen? Eigenlijk, Marcus gaf me reeds. Iemand anders lopen me er doorheen. Wat we doen als we - Dit lijkt sterk op wat we net deden. Avi. 

Publiek: Ik ga een gok te nemen. Dus als je snoep. 

JASON HIRSCHHORN: Yeah. Wel, we hebben pompoen. Laten we onze eerste. We kregen pompoen. 

Publiek: OK. Pompoen rendement nul. Zodat u deze in dat. Of eigenlijk, je zet het in de gelinkte lijst. 

JASON HIRSCHHORN: Hoe doen we zet het in de gelinkte lijst? 

PUBLIEK: Oh, de werkelijke syntax? 

JASON HIRSCHHORN: Gewoon lopen - meer zeggen. Wat doen wij? 

PUBLIEK: U voegt gewoon als het eerste knooppunt. 

JASON HIRSCHHORN: OK. Dus hebben we onze knooppunt, pompoen. En nu hoe plaats ik het? 

PUBLIEK: U wijst het naar de aanwijzer. 

JASON HIRSCHHORN: Welke wijzer? 

Publiek: De wijzer op nul. 

JASON HIRSCHHORN: Dus waar doet dit punt? 

PUBLIEK: Om nu meteen null. 

JASON HIRSCHHORN: Nou, het wijzend op null. Maar ik zet in pompoen. Dus waar zou ze moeten aanduiden? 

PUBLIEK: Om pompoen. 

JASON HIRSCHHORN: Om pompoen. Precies. Dus dit wijst op pompoen. En waar komt deze pointer in pompoen punt? Aan 

PUBLIEK: Null. 

JASON HIRSCHHORN: op null. Precies. Dus we gewoon iets ingebracht in de gelinkte lijst. We schreven deze code om dit te doen. Bijna kregen we het bijna volledig gekraakt. Nu voegen we snoep. Onze snoep gaat ook naar nul. Dus wat doen we met snoep? 

Publiek: Het hangt af van de vraag of niet we proberen te sorteren. 

JASON HIRSCHHORN: Dat is precies goed. Het hangt af van het al dan niet we proberen te sorteren. Laten we aannemen dat we niet gaan om het te sorteren. 

PUBLIEK: Nou dan, zoals we besproken voor, het eenvoudigste gewoon om het te zetten meteen aan het begin zodat de wijzer van nul punten op snoep. 

JASON HIRSCHHORN: OK. Wacht even. Laat me snoep maken hier. Dus deze pointer - 

PUBLIEK: Ja, moet nu worden gewezen op snoep. Dan hebben de wijzer van candy wijs pompoen. 

JASON HIRSCHHORN: Net als dat? En zeggen dat we een andere kregen ding naar de kaart op nul? 

PUBLIEK: Nou, je gewoon hetzelfde doen? 

JASON HIRSCHHORN: Doe hetzelfde. Dus in dit geval, als we niet willen houden loste het klinkt nogal eenvoudig. We nemen de aanwijzer in de indice gegeven door onze hash-functie. We hebben dat punt aan onze nieuwe knooppunt. En dan wat het aanwees eerder - in dit geval nul, in het tweede geval pompoen - dat, wat het ook wijst naar eerder, voegen we in het volgende van onze nieuwe knooppunt. We zijn het invoegen iets in het begin. In feite is dit een stuk eenvoudiger dan proberen om de gesorteerde lijst te houden. Maar nogmaals, het zoeken zal zijn meer hier ingewikkeld over. We zullen altijd moeten gaan tot het einde. 

OK. Heeft u vragen over aparte chaining? Hoe dat werkt? Vraag ze nu. Ik wil heel graag dat je alles maken begrijpen voordat we het hoofd uit. 

PUBLIEK: Waarom zet je pompoen en snoep in dezelfde deel van de hash table? 

JASON HIRSCHHORN: Goede vraag. Waarom hebben we ze in dezelfde deel van de hash table? Nou, in dit geval onze hash-functie rendement nul voor hen beiden. Dus moeten ze gaan op indice nul want dat is waar we gaan kijk voor hen als we ooit willen ze opzoeken. Opnieuw met een lineaire indringende benadering we zouden hen niet er zowel op nul. Maar in de aparte ketenbenadering, we gaan ze allebei op nul zetten en maak vervolgens een lijst af van nul. 

En we willen niet pompoen overschrijven gewoon voor dat want dan gaan we veronderstellen dat pompoen was nooit geplaatst. Als we gewoon blijven een ding in de locatie die slecht zou zijn. Dan zou er geen kans van ons ooit - als we ooit een duplicaat gehad, toen we zou gewoon wissen onze initiële waarde. Dus dat is de reden waarom we doen deze aanpak. Of dat is waarom we kozen - maar nogmaals, we koos voor de aparte chaining aanpak, waarvan er vele andere benaderingen men kon kiezen. Is dat een antwoord op je vraag? 

OK. Carlos. Lineaire indringende zou inhouden - als we vonden een botsing op nul, we zou er in de volgende plek om te zien of het was open en zet het daar. En dan kijken we in de volgende sport en zien of dat was open en zet het daar. Dus vinden we de volgende beschikbare open plek en zet het daar. Andere vragen? Ja, Avi. 

PUBLIEK: Als vervolg op dat, wat bedoel je met volgende plek? In de hash tabel of in een gekoppelde lijst. 

JASON HIRSCHHORN: Voor lineaire programmering, geen gelinkte lijsten. De volgende plek op de hash table. 

Publiek: OK. Dus de hash table zou zijn geïnitialiseerd om de grootte - zoals het aantal snaren dat je het invoegen? 

JASON HIRSCHHORN: U zou wil dat het echt groot zijn. Ja. Hier is een foto van wat we net trok op het bord. Nogmaals, we hebben een botsing hier. bij 152. En je zult zien hebben we een gelinkte lijst van af. Nogmaals, de hash table aparte chaining aanpak is niet degene die je moeten nemen voor problemen stellen zes maar een die veel studenten hebben de neiging zich te nemen. Dus op deze nota, laten we even praten voordat we uit over probleem zes, en dan zal ik een verhaal met u delen. We hebben drie minuten. 

Probleem ingesteld zes. Je hebt vier functies - belasting, controleren, grootte en lossen. Belasting - goed, we zijn gaan over belasting zojuist. We trokken belasting op het bord. En we zelfs begonnen met het coderen van een veel ingevoegd in een gelinkte lijst. Dus belasting niet meer dan wat we net gedaan. 

Check is als je eenmaal hebt iets geladen. Het is hetzelfde proces als dit. Dezelfde eerste twee delen waar je gooit iets in de hash-functie en krijg de waarde ervan. Maar nu zijn we niet te laden. Nu zijn we op zoek naar het. Ik heb voorbeeldcode geschreven voor het vinden van iets in een gelinkte lijst. Ik moedig u aan om te oefenen dat. Maar intuïtief vinden van iets wordt redelijk vergelijkbaar met het invoegen van iets. Inderdaad, trok we een beeld van het vinden iets in een gelinkte lijst, bewegen door tot dat je aan het einde. En als je echt naar het einde en kon niet vinden, dan is het er niet. Dus dat is controle, in wezen. 

Vervolgens is de grootte. Laten we overslaan grootte. Tenslotte moet je uitladen. Unload is degene die we hebben niet getekend op het bord of nog gecodeerd. Maar ik moedig u aan om te proberen het coderen in onze steekproef gelinkte lijst voorbeeld. Maar lossen intuïtief lijkt vrij - of ik bedoel is vergelijkbaar met controleren. Behalve voor nu elke keer dat je gaat door, je bent niet alleen controleren om zien of u er uw waarde. Maar je neemt dat knooppunt en vrijmaken van het wezen. Dat is wat lossen vraagt ​​je te doen. Gratis alles wat je hebt malloced. Dus je gaat door de hele lijst weer, gaan door de hele hash opnieuw tafel. Deze keer niet controleren om te zien wat er staat. Gewoon gratis wat er staat. 

En tenslotte grootte. Maat zal worden uitgevoerd. Als je niet implementeren grootte - Ik zeg het als dit. Als je niet implementeren grootte in precies een regel code, waaronder de terug statement, je bent verkeerd doet grootte. Dus zorg ervoor dat de grootte, voor volledige ontwerp punten, je doet het in precies een regel code, met inbegrip de return statement. 

En nog niet inpakken, Akchar. Eager Beaver. Ik wilde zeggen dank je wel jongens voor zijn komst naar sectie. Hebben een Happy Halloween. Dit is mijn kostuum. Ik zal het dragen van dit op donderdag als ik zie je op kantooruren. En als je nieuwsgierig bent wat meer bent achtergrond als om dit kostuum, voel vrij om te controleren 2011 deel voor een verhaal over waarom ik ben het dragen van de pompoen kostuum. En het is een triest verhaal. Dus zorg ervoor dat je sommige weefsels in de buurt. Maar op dat, als u een vragen die ik zal blijven hangen buiten na sectie. Veel succes op probleem ingesteld zes. En zoals altijd, als u een vragen, laat het me weten.