JASON Hirsch: Welkom almal na die artikel sewe. Ons is in week sewe van die kursus. En hierdie komende Donderdag is Halloween so ek geklee soos 'n pampoen. Ek kon nie buig oor en sit op my skoene, so dit is waarom ek net dra sokkies. Ek is ook nie die dra van enige iets onder hierdie, so ek kan dit nie af as dit afleidende na jou toe. Ek vra om verskoning by voorbaat vir wat. Jy hoef nie te dink wat gaan aan. Ek dra boksers. So dit is alles goed. 

Ek het 'n langer storie oor hoekom ek geklee as 'n pampoen, maar ek gaan behalwe dat vir later in hierdie afdeling omdat ek nie wil hê om te begin. Ons het 'n baie opwindende dinge om te gaan oor hierdie week. Die meeste van hulle hou regstreeks verband met hierdie week se probleem stel, spelfoute. Ons gaan te wees gaan oor gekoppel lyste en hash tabelle vir die hele afdeling. Ek het hierdie lys word elke week, 'n lys van hulpbronne vir jou om jou te help met Die materiaal op hierdie kursus. As teen 'n verlies of soek vir 'n paar meer inligting, kyk uit een van hierdie hulpbronne. 

Weereens, pset6 is spelfoute, hierdie week se pset. En dit moedig jou ook, en ek jou aan te moedig, 'n ander te gebruik hulpbronne spesifiek vir hierdie pset. In die besonder, die drie Ek het gelys op die skerm - gdb, wat ons het is vertroud met en is gebruik vir 'n rukkie nou, is gaan baie nuttig wees om hierdie week. So ek sit dit hier. Maar wanneer jy werk met C, jy moet altyd gebruik word gdb te ontfout jou programme. Hierdie week het ook valgrind. Het enige iemand weet wat valgrind doen? 

Publiek: Dit gaan vir die geheue lekkasies? 

JASON Hirsch: Valgrind tjeks vir die geheue lekkasies. So as jy malloc iets in jou program, jy vra vir die geheue. Aan die einde van die program, moet jy vry om te skryf oor alles wat jy het malloced die geheue terug te gee. As jy nie vrye skryf nie aan die einde en jou program kom tot 'n gevolgtrekking, Alles sal outomaties bevry word. En vir klein programme, is dit nie so 'n groot deal. Maar as jy 'n langer loop skryf program wat nie ophou, noodwendig nie, in 'n paar minute of 'n paar sekondes, dan die geheue lekkasies kan 'n groot deal word. 

So vir pset6, is die verwagting dat jy sal hê nul geheue lekkasies met jou program. Om seker te maak vir die geheue lekkasies, hardloop valgrind en dit sal vir jou 'n paar mooi uitset om jou te laat weet of of nie alles gratis. Ons sal later oefen met dit Vandag, hopelik. 

Ten slotte, die verskil opdrag. Jy gebruik word om iets soortgelyk aan dit in pset5 met die blik instrument. Toegelaat om jou te binne te kyk. Jy kan ook gebruik word verskil ook per die probleem gestel spec. Maar in jou toegelaat het om te vergelyk twee lêers. Jy kan die bitmap lêer en te vergelyk info kop van 'n personeellid oplossing en jou oplossing in pset5 indien jy gekies het om dit te gebruik. Verskil sal toelaat om te doen, as well. Jy kan die korrekte antwoord vergelyk hierdie week se probleem stel om jou antwoord en kyk of dit in lyn is of sien waar die foute is. 

So dit is drie goeie gereedskap wat wat jy moet gebruik vir hierdie week, en beslis check jou program met hierdie drie gereedskap voordat hy dit in Weereens, as ek elke week genoem het, Indien u enige terugvoer vir my - beide positiewe en opbouende - voel vry om aan die hoof van die webwerf aan die onderkant van hierdie skyfie en insette dit daar. Ek het regtig nie waardeer en al die terugvoer. En as jy my spesifieke dinge wat Ek kan doen om te verbeter of dat ek om goed te doen wat jy vir my wil voort te gaan, ek neem aan dat dit die hart en probeer regtig hard om te luister om jou terugvoer. Ek kan nie belowe ek gaan doen alles, al is, soos die dra van 'n pampoen kostuum elke week. 

So gaan ons die grootste deel van die te spandeer artikel, soos ek genoem het, praat oor geskakelde lyste en hash tabelle, wat sal direk van toepassing is op die wees probleem stel hierdie week. Geskakelde lyste sal ons gaan oor relatief vinnig, want ons het 'n eerlike bietjie bestee van die tyd gaan oor dit in artikel. En so sal ons kry reguit in die kodering probleme gekoppel lyste. En dan aan die einde sal ons praat oor hash tabelle en hoe dit van toepassing is op hierdie week se probleem stel. 

Jy het hierdie kode gesien het nie. Dit is 'n struct, en dit is die definisie iets nuuts genoem 'n knoop. En binne-in 'n knoop is daar 'n heelgetal hier en daar is 'n verwysing na ander rekenaars. Ons het dit gesien voor. Dit is te kom vir 'n paar weke nou. Dit kombineer wysers, wat ons al werk met, en structs, wat toelaat ons twee verskillende te kombineer dinge in een data tipe. 

Daar is 'n baie gaan op die skerm. Maar dit alles moet relatief wees vertroud is met jou. Op die eerste lyn, ons verklaar 'n nuwe knoop. En dan binne daardie nuwe knoop, ek Die heelgetal in die knoop teen een. Ons sien op die volgende reël ek doen 'n printf opdrag, maar ek het vergrys die printf bevel omdat die werklik belangrike deel is hierdie lyn hier - new_node.n. Wat beteken die dot beteken? 

Publiek: Gaan na die knoop en bepaal die waarde vir n dit. 

JASON Hirsch: Dis presies reg. Dot beteken toegang tot die n deel van hierdie nuwe knoop. Hierdie volgende lyn doen wat? Michael. 

Publiek: Dit skep 'n ander node wat verwys na die nuwe knoop. 

JASON Hirsch: So is dit nie Skep 'n nuwe node. Dit skep 'n wat? 

Publiek: 'n wyser. 

JASON Hirsch: 'n verwysing na 'n knoop, soos aangedui deur die knoop * hier. So skep dit 'n verwysing na 'n knoop. En wat knoop is dit wys te, Michael? 

Publiek: New knoop? 

JASON Hirsch: New knoop. En dit is daar wys, want ons het gee dit die adres van die nuwe knoop. En nou in hierdie lyn wat ons sien twee verskillende maniere uitdrukking van die dieselfde ding. En ek wou om uit te wys hoe hierdie twee dinge is dieselfde. In die eerste lyn, ons dereference die wyser. So gaan ons na die knoop. Dit is wat hierdie ster beteken. Ons het gesien dat voor met wysers. Gaan na daardie knoop. Dit is in hakies. En dan toegang via die dot operateur die n element van die knoop. 

So dit is die neem van die sintaksis sien ons hier en nou gebruik dit met 'n muis. Natuurlik, dit kry soort van besig as jy skryf die hakies - dat die ster en dat dot. Dit raak 'n bietjie besig. So ons het 'n paar sintaktiese suiker. En hierdie lyn hier - ptr_node-> n. Dit beteken presies dieselfde ding. So hierdie twee reëls van die kode is ekwivalent en sal doen presies dieselfde ding. 

Maar ek wou diegene uit te wys voordat ons verder gaan, sodat jy verstaan wat regtig die ding hier is net sintaktiese suiker vir ontwysing die wyser en dan gaan die n deel van daardie struct. Enige vrae oor hierdie skuif? OK. 

So ons gaan om te gaan deur 'n paar van bedrywighede wat jy op kan doen geskakelde lyste. 'N geskakelde lys, onthou, is 'n reeks nodes wat na mekaar. En ons in die algemeen begin met 'n verwysing genoem hoof, oor die algemeen, wat verwys na Die eerste ding wat in die lys. So op die eerste lyn hier, ons het ons oorspronklike L eerste. So die ding wat jy kan dink - dit teks hier wat jy kan dink as net die wyser het ons gestoor êrens dat punte na die eerste element. En in hierdie verband lys Ons het vier knope. Elke node is 'n groot boks. Die groter boks binne-in die groot box is die heeltallige deel. En dan het ons 'n wyser deel. 

Hierdie bokse is nie gevestig op skaal, want hoe groot is 'n heelgetal in grepe? Hoe nou groot? Vier. En hoe groot is 'n muis? Vier. So regtig, as ons te trek hierdie bokse beide op die skaal sou dieselfde grootte wees. In hierdie geval, ons wil voeg iets in die lys. Sodat jy kan sien hier is ons inbring Vyf Ons deurkruis deur die gekoppel lys vind waar vyf gaan, en dan plaas dit. 

Kom ons breek dat af en gaan 'n bietjie stadiger. Ek gaan om te wys op die bord. So het ons ons node vyf wat ons geskep het in mallocs. Hoekom is almal lag? Net 'n grap. OK. Dus het ons malloced vyf. Ons het hierdie knoop iewers anders. Ons is gereed om te gaan. Ons begin by die voorkant van ons lys met twee. En ons wil in te voeg in 'n gesorteerde mode. 

So as ons sien twee en ons wil om te sit vyf, wat doen ons wanneer ons sien iets minder as ons? Wat? Ons wil in te voeg vyf in hierdie gekoppel lys, hou dit gesorteer. Ons sien nommer twee. So, wat doen ons? Marcus? 

Publiek: Bel die wyser na die volgende knoop. 

JASON Hirsch: En hoekom doen ons gaan na die volgende een? 

Publiek: Want dit is die volgende nodus in die lys. En ons weet net dat ander plek. 

JASON Hirsch: En vyf groter as twee, in die besonder. Omdat ons wil dit gesorteer te hou. So vyf is groter as twee. So het ons beweeg na die volgende een. En nou kom ons vier. En wat gebeur wanneer ons vier bereik? 

Vyf is groter as vier. So ons gaan hou. En nou is ons op ses. En wat sien ons op ses? Ja, Carlos? 

Publiek: Ses is groter as vyf. 

JASON Hirsch: Ses is groter as vyf. So dit is waar ons wil te voeg vyf. Hou egter in gedagte dat indien ons het net een wyser hier - dit is ons ekstra wyser wat dwars deur die lys. En ons wys na ses. Ons het spoor verloor van wat kom voor ses. So as ons iets wil voeg in hierdie lys om dit gesorteer ons waarskynlik hoeveel riglyne? 

Publiek: Twee. 

JASON HIRSCHORN: Twee. Een baan van die huidige te hou een en tred te hou met die vorige een. Dit is net 'n enkel gekoppel lys. Dit gaan net een rigting. As ons 'n dubbel gekoppel lys, waar alles wys na die ding nadat dit en die ding voordat dit dan sou ons nie nodig het om dit te doen. Maar in hierdie geval het ons nie wil verloor spoor van wat voor ons gekom het in die geval Ons moet vyf iewers te voeg in die middel. Sê ons is die inbring van nege. Wat sou gebeur wanneer ons het tot agt? 

Publiek: Jy wil hê om te kry dat die nul punt. In plaas van om nul punt wat jy wil hê 'n element te voeg en dan dit verwys na nege. 

JASON HIRSCHORN: Presies. So kry ons agt. Ons bereik die einde van die lys, want dit is wys om null. En nou, in plaas van om dit te wys null ons het dit verwys na ons nuwe knoop. En ons het die wyser in ons nuwe node te null. Het enige iemand enige vrae oor die inbring? Wat as ek nie omgee vir hou die lys gesorteer? 

Publiek: Hou dit by die begin of die einde. 

JASON HIRSCHORN: Plak dit op die begin of die einde. Watter een moet ons doen? Bobby? Hoekom die einde? 

Publiek: Omdat die begin is reeds gevul. 

JASON HIRSCHORN: OK. Die begin is reeds gevul. Wie wil om te argumenteer teen Bobby. Marcus. 

Publiek: Wel, jy waarskynlik wil hou dit aan die begin, want anders as jy sit dit op die einde wat jy wil hê om te deurkruis die hele lys. 

JASON HIRSCHORN: Presies. So as ons dink oor runtime, die runtime van die plaas aan die einde sou n wees, die grootte van hierdie. Wat is die groot O looptyd van die plaas aan die begin? Konstante tyd. So as jy nie omgee oor die behoud van iets gesorteer, veel beter om net te voeg aan die begin van die lys. En dit kan in konstante tyd gedoen word. 

OK. Volgende operasie vind wat ander - Ons het hierdie geformuleer as soek. Maar ons gaan om te kyk deur die gekoppel lys vir 'n paar voorwerp. Julle het gesien kode vir soek voor in lesing. Maar ons soort het dit net met voeg, of ten minste inbring iets gesorteer. Jy kyk deur, gaan knoop deur knoop, totdat jy die nommer wat jy soek. Wat gebeur as jy bereik die einde van die lys? Sê ek is op soek na nege en ek bereik die einde van die lys. Wat doen ons? 

Publiek: Terug vals? 

JASON HIRSCHORN: Terug onwaar. Ons het dit nie vind nie. As jy aan die einde van die lys en jy het nie die nommer wat jy is soek, dit is nie daar in. Enige vrae oor kry? As dit was 'n gesorteerde lys, wat sou wees anders vir ons soek? Ja. 

Publiek: Dit sal die eerste waarde vind dit is groter as die een wat jy soek en dan terug onwaar. 

JASON HIRSCHORN: Presies. So as dit is 'n gesorteerde lys, as ons kry om te iets wat groter is as wat ons soek, moet ons nie te hou gaan aan die einde van die lys. Ons kan op daardie punt terug valse want ons gaan nie om dit te vind. Die vraag is nou, ons het gepraat oor hou verband lyste gesorteer, hou hulle ongesorteerde. Dit gaan iets wat jy moet wees waarskynlik gaan hê om te dink oor wanneer kodering probleem stel vyf as jy kies 'n hash tafel met aparte chaining benadering, wat Ons sal later praat. 

Maar is dit die moeite werd om die lys te hou gesorteer en dan in staat wees om dalk het vinniger soektogte? Of is dit beter om vinnig te voeg iets in konstante runtime maar dan langer op soek? Dit is 'n nadeel reg daar dat jy kry om te besluit wat is meer gepas vir jou spesifieke probleem. En daar is nie noodwendig 'n absoluut reg antwoord. Maar dit is beslis 'n besluit wat jy kry te maak, en waarskynlik goed te verdedig wat in, sê, 'n opmerking of twee waarom jy het een oor die ander. 

Ten slotte, die verwydering. Ons het gesien hoe die verwydering. Dit is soortgelyk aan die soek. Ons kyk vir die element. Sê dat ons probeer om te verwyder van ses. So vind ons ses reg hier. Die ding wat ons het om seker te maak ons doen, is dat alles wat dui op ses - soos ons sien in stap twee hier - alles is wys tot ses behoeftes te slaan ses nou en word verander na net ses wys na. Ons wil nie om ooit die res van Orphan ons lys deur te vergeet om dit te stel vorige wyser. En dan soms, afhangende op die program, sal hulle net skrap hierdie knoop heeltemal. Soms sal jy wil om terug te keer die waarde wat in hierdie knoop. So dit is hoe die verwydering van werke. Enige vrae oor skrap? 

Publiek: So as jy gaan om te verwyder dit was, sou jy net gebruik vry omdat vermoedelik was dit malloced? 

JASON HIRSCHORN: As jy wil vry iets wat is presies reg, en jy malloced dit. Sê ons wou hierdie waarde om terug te keer. Ons kan terugkeer ses en dan gratis hierdie knoop en oproep gratis op dit. Of ons sou waarskynlik vry bel eerste en dan terug te keer ses. 

OK. So laat ons beweeg om te oefen kodering. Ons gaan drie funksies te kode. Die eerste een is insert_node genoem. So jy het kode wat ek per e-pos wat jy, en As jy hierdie is kyk later jy kan die kode toegang in linked.c op die CS50 webwerf. Maar in linked.c, daar is 'n paar geraamte kode wat reeds geskryf is vir jou. En dan is daar 'n paar funksies wat jy nodig het om te skryf. 

Eerste ons gaan skryf insert_node. En wat doen insert_node IS voeg 'n heelgetal. En jy gee die heelgetal in 'n geskakelde lys. En in die besonder, moet jy die lys gesorteer te hou van die kleinste tot die grootste. Ook, het jy nie wil Voeg enige duplikate. Ten slotte, as jy kan sien insert_node gee 'n Bool. So jy veronderstel is om jou te laat die gebruiker weet of die insetsel was suksesvolle deur die terugkeer waar of vals is. Aan die einde van hierdie program - en vir hierdie stadium het jy nie nodig bekommerd te wees oor die vrylating van enigiets. So al wat jy doen, is om 'n heelgetal en jy dit op 'n lys. 

Dit is wat ek vra jou nou te doen. Weereens, in die linked.c, wat jy al het, is die geraamte kode. En jy moet sien aan die onderkant die funksie voorbeeld verklaring. Maar voor hy in die kodering dit in C, ek raai u aan om te gaan deur die stappe wat ons het al oefen elke week. Ons het reeds deurgedring 'n foto van hierdie. So moet jy n mate van begrip het van hoe dit werk. Maar ek wil jou aanmoedig om te skryf sommige pseudokode voor duik in En ons gaan om te gaan pseudokode as 'n groep. En dan keer jy geskryf het jou pseudokode, en sodra ons geskryf ons pseudokode as 'n groep, kan jy gaan in die kodering in C. 

As 'n kop, die insert_node funksie is waarskynlik die moeilijkste van die drie ons gaan om te skryf, want ek bygevoeg 'n paar ekstra beperkinge te jou ontwikkeling, in die besonder wat jy is nie van plan om enige te voeg duplikate en dat die lys gesorteer moet bly. So dit is 'n nie-triviale program wat jy nodig het om te kode. En hoekom neem jy nie 06:55 minute net om die werk op die pseudokode en die kode. En dan sal ons begin gaan as 'n groep. Weereens, as jy enige vrae het net verhoog jou hand en ek sal bykom. . 

Ons het ook oor die algemeen doen hierdie - of ek uitdruklik sê nie dat jy met mense kan werk. Maar natuurlik, ek raai u aan, As jy vrae het, vra die naaste wat langs jou sit of selfs werk met iemand anders as jy wil. Dit hoef nie aan 'n individu wees stil aktiwiteit. 

Kom ons begin met die skryf van 'n pseudokode op die bord. Wie kan my die eerste reël van die pseudokode vir hierdie program? Vir hierdie funksie, eerder - insert_node. Alden? 

Publiek: So die eerste ding wat ek gedoen het, was skep 'n nuwe wyser na die knoop en ek geïnisialiseer dit verwys na dieselfde ding dat die lys is wat verwys na. 

JASON HIRSCHORN: OK. So jy skep 'n nuwe wyser aan die lys, nie aan die knoop. 

Publiek: Right. Ja. 

JASON HIRSCHORN: OK. En dan wat ons wil doen? Wat se nadat dit? Wat van die knoop? Ons het nie 'n knoop nie. Ons het net 'n waarde. As ons wil 'n knoop te voeg, wat doen ons moet jy eers doen voordat ons kan selfs dink oor die inbring nie? 

Publiek: Ag, jammer. ons nodig het om ruimte te malloc vir 'n knoop. 

JASON HIRSCHORN: Uitstekende. Kom ons doen - OK. Kan bereik nie dat 'n hoë. OK. Ons gaan om af te gaan, en dan ons gebruik twee kolomme. Ek kan nie gaan dat - OK. Skep 'n nuwe node. Jy kan 'n ander wyser skep om 'n lys of jy kan net gebruik lys as dit bestaan. Jy nie regtig nodig om dit te doen. 

So skep ons 'n nuwe knoop. Groot. Dit is wat ons doen eerste. Wat is volgende? 

Publiek: Wag. Indien ons 'n nuwe node nou of moet ons wag om seker te maak dat daar is geen duplikate van die node op die lys voordat ons dit skep? 

JASON HIRSCHORN: Goeie vraag. Kom ons hou dit vir later, want die meerderheid van die tyd wat ons sal skep 'n nuwe knoop. So sal ons hier te hou nie. Maar dit is 'n goeie vraag. As ons dit geskep het en ons vind 'n duplikaat, wat moet ons doen voordat hy terugkeer? 

Publiek: vry om dit. 

JASON HIRSCHORN: Ja. Waarskynlik bevry nie. OK. Wat doen ons na ons Skep 'n nuwe node? Annie? 

Publiek: Ons het die nommer in die knoop? 

JASON HIRSCHORN: Presies. Ons het die nommer - ons malloc ruimte. Ek is van plan om dit te verlaat al as 'n reël. Maar jy is reg. Ons malloc ruimte, en dan Ons het die nommer in Ons kan selfs die wyser deel van dit te null. Dit is presies reg. En wat dan van daarna? Ons het hierdie foto op die bord. So, wat doen ons? 

Publiek: Ons gaan deur die lys. 

JASON HIRSCHORN: Gaan deur die lys. OK. En wat kyk ons ​​vir by elke node. Kurt, wat doen ons kyk vir ten elke knoop? 

Publiek: Kyk of die n waarde van dat node is groter as die n waarde van ons node. 

JASON HIRSCHORN: OK. Ek gaan om te doen - ja, OK. So dit is n - Ek gaan om te sê as waarde is groter as dit knoop, dan wat doen ons? 

Publiek: Wel, dan moet ons voeg die ding reg voor dit. 

JASON HIRSCHORN: OK. So as dit is groter as dit, dan wil ons in te voeg. Maar ons wil om dit te sit reg voor omdat ons ook nodig sou wees dop, dan, van wat tevore was. So voeg voor. Dus het ons waarskynlik iets gemis Vroeër op. Ons het waarskynlik moet word hou spoor van wat aangaan. Maar ons sal terug te kry daar. So watter waarde is minder as? Kurt, wat doen ons as waarde is minder as? 

Publiek: Dan moet jy hou net gaan tensy dit is die laaste een. 

JASON HIRSCHORN: Ek hou daarvan. So gaan na die volgende knoop. Tensy dit is die laaste een - ons is waarskynlik die nagaan vir daardie in die terme van 'n toestand. Maar ja, die volgende knoop. En dit is steeds te laag is, so ons sal hier te beweeg. Maar as - kan almal sien dit? As ons gelyke wat doen ons? Indien die waarde wat ons probeer om te voeg is gelyk aan die knoop se waarde? Ja? 

Publiek: [onhoorbaar]. 

JASON HIRSCHORN: Ja. Gegewe hierdie - Marcus is reg. Ons kon dalk gedoen iets anders. Maar gegewe dat ons het dit geskep, hier ons moet vry en dan terug te keer. Oh boy. Is dit beter? Hoe is dit? OK. Gratis en dan wat doen ons terugkeer, [onhoorbaar]? OK. Is ons ontbreek enigiets? So waar gaan ons die dop van die vorige knoop? 

Publiek: Ek dink dit sou gaan na 'n nuwe knoop. 

JASON HIRSCHORN: OK. So aan die begin Ons sal waarskynlik - Ja, ons kan 'n wyser skep van 'n nuwe knoop, soos 'n vorige node wyser en 'n knoop wyser. So laat se plaas dit hier. Skep huidige en vorige verwysings na die nodes. Maar toe ons die wysers pas? Waar doen ons dit in die kode? Jeff? 

Publiek: - waarde toestande? 

JASON HIRSCHORN: Watter een in die besonder? 

Publiek: Ek is net verwar. As waarde is groter as die knoop, nie dat beteken dat jy wil gaan na die volgende knoop? 

JASON Hirsch: So as ons waarde is groter as die waarde van hierdie knoop. 

Publiek: Ja, dan moet jy graag wil hê om gaan verder in die ry nie, reg? 

JASON Hirsch: Right. Sodat ons nie hier plaas dit nie. As waarde is minder as die knoop, dan Ons gaan na die volgende knoop - of dan voeg voor. 

Publiek: Wag, wat hierdie knoop en wat is waarde? 

JASON Hirsch: Goeie vraag. Waarde per hierdie funksie definisie is wat ons gegee. So waarde is die getal wat ons gegee. Dus, as die waarde is minder as dit knoop, moet ons tyd in te voeg. As waarde is groter as die knoop, Ons gaan na die volgende knoop. En terug na die oorspronklike vraag, al is, waar - 

Publiek: As waarde is groter as hierdie knoop. 

JASON Hirsch: En so wat doen ons hier doen? Soet. Dit is korrek. Ek gaan net om te skryf update wysers. Maar ja, met die huidige een jy sal dit werk na verwys na die volgende een. Enigiets anders wat ons mis? So ek gaan om dit te tik kode in gedit. En terwyl ek dit doen, kan jy 'n paar minute om te werk aan kodering dit in C. 

So ek het die invoer van die pseudokode. 'N vinnige nota voordat ons begin. Ons kan nie in staat om heeltemal klaar is met hierdie in alle drie van hierdie funksies. Daar is korrekte oplossings aan hulle dat ek sal e-pos aan u ouens na artikel, en dit sal op CS50.net gepos. So ek moedig jou nie gaan kyk na die artikels. Ek moedig jou om dit te probeer op jou besit, en gebruik dan die praktyk probleme jou antwoorde te kontroleer. Hierdie is almal ontwerp om te werk nou verband hou en vas te hou wat jy hoef te doen oor die probleem stel. So ek u aanmoedig om dit te oefen op jou eie en gebruik dan die kode kontroleer jou antwoorde. Omdat ek nie wil hê om aan te beweeg om hash tafels op 'n sekere punt in die artikel. So ons kan dit nie kry deur dit alles. Maar ons sal nou soveel ons kan doen. 

OK. Kom ons begin. ASAM, hoe skep ons 'n nuwe knoop? 

Publiek: Jy struct *. 

JASON Hirsch: So ons het dat hier. O, jammer. Jy het gesê struct *. 

Publiek: En dan [? soort?] knoop of c knoop. 

JASON Hirsch: OK. Ek gaan om dit te noem new_node sodat ons kan bly konsekwent. 

Publiek: En jy wil om dit te stel aan die hoof, die eerste knoop. 

JASON Hirsch: OK. So nou is dit wys om - so dit het nie 'n nuwe node geskep het nie. Dit is net te wys op die eerste nodus in die lys. Hoe kan ek 'n nuwe knoop? As ek moet ruimte 'n nuwe node te skep. Malloc. En hoe groot? 

Publiek: Die grootte van die struct. 

JASON Hirsch: Die grootte van die struct. En wat is die struct genoem? 

Publiek: Node? 

JASON Hirsch: Node. So malloc (sizeof (nodig)); gee ons die ruimte. En is hierdie lyn - een ding is verkeerd op hierdie lyn. Is new_node 'n verwysing na 'n struct? Dit is 'n generiese naam. Wat is dit - knoop, presies. Dit is 'n knoop *. En wat doen ons reg na ons malloc iets Asan? Wat is die eerste ding wat ons doen? Wat as dit nie werk nie? 

Publiek: Ag, kyk of dit wys na die knoop? 

JASON Hirsch: Presies. So as jy new_node gelyk gelykes nul, wat doen ons? Dit gee 'n Bool, hierdie funksie. Presies. Lyk goed. Enigiets om daar te voeg? Ons sal dinge aan die einde voeg. Maar dat so ver lyk goed. Skep huidige en vorige wysers. Michael, hoe doen ek dit? 

Publiek: Jy wil hê 'n knoop te doen *. Jy wil hê om een ​​te maak nie vir new_node maar vir die nodes ons reeds het. 

JASON Hirsch: OK. So het die knoop ons op. Ek bel dat Kur. Alle regte. Ons het besluit ons wil hou twee, want ons moet weet Wat is voordat dit. Wat kry hulle geïnisialiseer om? 

Publiek: die waarde daarvan in ons lys. 

JASON Hirsch: So, wat is die eerste ding op die lys? Of hoe weet ons waar die begin van ons lys is? 

Publiek: Is dit nie geslaag in die funksie? 

JASON Hirsch: Right. Dit is in hier verby. So as dit geslaag het in die funksie, die die begin van die lys, wat moet ons Stel huidige gelyk aan? 

Publiek: List. 

JASON Hirsch: Lys. Dit is presies reg. Nou het dit die adres van die begin van die lys. En wat van die vorige? 

Publiek: Lys minus een? 

JASON Hirsch: Daar is niks voor dit. So wat kan ons niks doen nie, om aan te dui? 

Publiek: null. 

JASON Hirsch: Ja. Dit klink soos 'n goeie idee. Perfect. Dankie. Gaan deur die lys. Konstantyn, hoe lank gaan ons om te gaan deur die lys? 

Publiek: totdat ons null. 

JASON Hirsch: OK. So as ons, terwyl, vir lus. Wat doen ons? 

Publiek: Miskien is 'n lus vir? 

JASON Hirsch: Kom ons doen 'n lus vir. OK. 

Publiek: En ons sê vir - totdat die huidige wyser is nie gelyk aan nul. 

JASON Hirsch: So as ons weet wat die toestand is, hoe kan ons skryf 'n lus gebaseer af die toestand. Watter soort van 'n lus moet ons gebruik? 

Publiek: Terwyl. 

JASON Hirsch: Ja. Dit maak meer sin gebaseer af van wat jy gesê het. As ons wil net om te gaan in ons sou dit weet net dat die ding, sou dit maak sin 'n rukkie lus om te doen. Terwyl die huidige nie gelyk nul, As waarde is minder as die knoop. Akshar, gee my daardie lyn. 

Publiek: As die huidige-> n n minder as waarde. Of reverse nie. Skakel dat bracket. 

JASON Hirsch: Jammer. 

Publiek: Verander die bracket. 

JASON Hirsch: So as dit groter as waarde. Want dit is verwarrend met die kommentaar hierbo, ek gaan om dit te doen. Maar ja. As ons waarde is minder as dit knoop, wat doen ons? Oh. Ek het dit hier. Voeg tevore. OK. Hoe doen ons dit? 

Publiek: Is dit nog steeds vir my? 

JASON Hirsch: Ja. 

Publiek: Jy - new_node-> volgende. 

JASON Hirsch: So, wat is wat gaan gelyk? 

Publiek: Dit gaan gelyk huidige. 

JASON Hirsch: Presies. En so het die ander - Wat anders moet ons te werk? 

Publiek: Kyk of gelyk afgelope null. 

JASON Hirsch: As Vorige - so as vorige gelyk aan nul. 

Publiek: Dit beteken dit gaan aan die hoof geword. 

JASON Hirsch: Dit beteken dit is nou die hoof. So dan wat doen ons? 

Publiek: Ons doen hoof gelyk new_node. 

JASON Hirsch: Hoof gelyk new_node. En hoekom kop hier, nie die lys? 

Publiek: Omdat kop is 'n globale veranderlike, wat is die beginpunt. 

JASON Hirsch: Sweet. OK. En - 

Publiek: dan doen jy anders prev-> volgende gelyk new_node. En dan moet jy weer waar. 

JASON Hirsch: Waar Ons stel new_node einde? 

Publiek: Ek sou - Ek stel dat aan die begin. 

JASON Hirsch: So watter lyn? 

Publiek: Na afloop van die if-stelling seker te maak dat dit bekend is. 

JASON Hirsch: Right hier? 

Publiek: ek wil doen new_node-> n gelyk aan waarde. 

JASON Hirsch: Klink goed. Waarskynlik maak dit sin - ons doen nie nodig het om te weet wat die lys is ons op omdat ons net die hantering met 'n lys. So 'n beter funksie verklaring vir dit is net om ontslae te raak van hierdie geheel en voeg net 'n waarde in die kop. Ons het nie eens nodig om te weet wat lys ons is in Maar ek sal dit hou vir nou en dan verander dit op die opdatering die skyfies en kode. So wat goed lyk vir nou. As waarde - wat hierdie lyn kan doen? Indien - wat doen ons hier doen, Noag. 

Publiek: As waarde is groter as Kur-> n - 

JASON Hirsch: Hoe doen Ons gaan na die volgende knoop? 

Publiek: Kur-> n is gelyk aan new_node. 

JASON Hirsch: So n ' wat deel van die struct? Die heelgetal. En new_node is 'n verwysing na 'n knoop. So, wat deel uitmaak van Kur moet ons werk? Indien nie n, dan wat is die ander deel? Noag, wat is die ander deel. 

Publiek: Ag, die volgende. 

JASON Hirsch: Volgende, presies. Presies. Volgende is die regte een. En wat anders het ons nodig te werk, Noag? 

Publiek: Die wysers. 

JASON Hirsch: So ons by die huidige. 

Publiek: Vorige-> volgende. 

JASON Hirsch: Ja. OK, ons sal breek. Wat ons kan help hier? Manu, wat moet ons doen? 

Publiek: Jy het om te stel dit gelyk aan Kur-> volgende. Maar dit doen voordat die vorige lyn. 

JASON Hirsch: OK. Enigiets anders? Akshar. 

Publiek: Ek dink nie jy bedoel Kur-> te verander volgende. Ek dink jy bedoel Kur gelykes te doen Kur-> volgende om te gaan na die volgende knoop. 

JASON Hirsch: So jammer, waar? Op watter lyn? Hierdie lyn? 

Publiek: Ja. Maak Kur gelyk Kur-> volgende. 

JASON Hirsch: So dit is korrek omdat die huidige is 'n wyser na 'n knoop. En ons wil om dit te wys op die volgende knoop van wat tans kry wys na. Kur self het 'n volgende. Maar as ons curr.next te werk, het ons sou opdatering word om die werklike noot self, nie waar hierdie wyser is wys. Wat van hierdie lyn, al is. Avi? 

Publiek: Vorige-> langs gelyk Kur. 

JASON Hirsch: So weer, as vorige is 'n wyser na 'n knoop, vorige-> Volgende is die werklike wyser in die knoop. So dit sal die opdatering word om 'n aanwijzer in 'n knoop te Kur. Ons wil nie te werk 'n wyser in 'n knoop. Ons wil om te werk vorige. So, hoe kan ons dit doen? 

Publiek: Dit sou net prev word. 

JASON Hirsch: Right. Vorige is 'n verwysing na 'n knoop. Nou is ons om dit te verander na 'n nuwe wyser na 'n knoop. OK Kom ons af beweeg. Ten slotte, hierdie laaste toestand. Jeff, wat doen ons hier doen? 

Publiek: As waarde is gelyk aan Kur-> n. 

JASON Hirsch: Jammer. Ag, my goedheid. Wat? Waarde == Kur-> n. Wat doen ons? 

Publiek: Jy wil bevry ons new_node, en dan sal jy terugkeer onwaar. 

JASON Hirsch: Dit is wat wat ons tot dusver geskryf. Het enige iemand iets te voeg voordat ons? OK. Kom ons probeer dit. Beheer kan die einde bereik van 'n nie-leemte funksie. Avi, wat gaan aan? 

Publiek: Is jy veronderstel terugkeer te sit ware buite die lus? 

JASON Hirsch: Ek weet nie. Wil jy my te? 

Publiek: Toemaar. No 

JASON Hirsch: akshar? 

Publiek: Ek dink jy bedoel om te sit terugkeer valse aan die einde van die lus. 

JASON Hirsch: So waar wil jy dit om te gaan? 

Publiek: Hou buite die lus. So as jy die uitgang van die tyd lus wat beteken wat jy aan die einde gekom en niks gebeur het. 

JASON Hirsch: OK. So, wat doen ons hier? 

Publiek: Jy terugkeer valse is daar ook. 

JASON Hirsch: Ag, het ons doen dit in beide plekke? 

Publiek: Ja. 

JASON Hirsch: OK. Moet ons gaan? Ag, my goedheid. Ek is jammer. Ek vra om verskoning vir die skerm. Dit is soort van uitgefreakt oor ons. So kies 'n opsie. Zero, per die kode, verlaat die program. Een voeg iets. Kom ons voeg drie. Die insetsel was nie suksesvol nie. Ek gaan om uit te druk. Ek het niks nie. OK. Miskien was dit net 'n gelukskoot. Voeg een. Nie suksesvol nie. OK. Kom ons loop deur GDB regtig vinnig om te kyk na wat aangaan. 

Onthou gdb. / Die naam van jou program kry ons in GDB. Is dit 'n baie om te hanteer? Die flikker? Waarskynlik. Maak jou oë toe en neem 'n diep blaas as jy moeg om daarna te kyk. Ek is in GDB. Wat is die eerste ding wat ek doen in GDB? Ons het om uit te vind wat gaan hier aan. Kom ons kyk. Ons het ses minute na figuur uit te vind wat gaan aan. Breek hoof. En dan wat doen ek? Carlos? Begin. OK. Kom ons kies 'n opsie. En wat beteken N doen? Volgende. Ja. 

Publiek: Het jy nie noem - Het jy nie gesê dat die hoof, was dit geïnisialiseer te null aan die begin. Maar ek het gedink jy het gesê dit was OK. 

JASON Hirsch: Kom ons gaan - kom ons kyk in GDB, en dan sal ons terug te gaan. Maar dit klink asof jy reeds 'n paar idees oor wat aangaan. So wil ons iets te voeg. OK. Ons het plaas. Tik 'n int. Ons sal voeg drie. En dan is ek op hierdie lyn. Hoe gaan ek begin debugging die insetsel bekend funksie? Ag, my goedheid. Dit is 'n baie. Is dit uitgefreakt 'n baie? 

Publiek: O, dit is dood. 

JASON Hirsch: Ek het net trek dit uit. OK. 

Publiek: Miskien is dit die ander kant van die draad. 

JASON Hirsch: Wow. So het die onderste lyn - wat het jy gesê? 

Publiek: Ek het die ironie van die tegniese probleme in hierdie klas. 

JASON Hirsch: Ek weet. As ek maar net beheer oor die deel. [Onhoorbaar] Dit klink great. Hoekom nie julle ouens begin nie dink oor wat ons kan verkeerd gedoen het, en ons sal in 90 sekondes. 

Avica, ek gaan om te vra hoe om te gaan binne insert_node dit te ontfout. So dit is waar ons gebly het. Hoe kan ek gaan binne insert_node, Avica, te ondersoek wat gaan aan? Wat GDB opdrag? Breek nie sou neem my binnekant. Maak Marquise ken? 

Publiek: Wat? 

JASON Hirsch: Wat GDB opdrag Ek gebruik om te gaan binne hierdie funksie? 

Publiek: Stap? 

JASON Hirsch: Stap via S. Dit neem my binnekant. OK. New_node mallocing ruimte. Dat al lyk sy gaan. Kom ons ondersoek new_node. Dit het 'n paar geheue adres. Kom ons kyk - dit is alles reg. So alles hier lyk word korrek werk. 

Publiek: Wat is die verskil tussen P en vertoon? 

JASON Hirsch: P staan ​​vir die gedrukte media. En so jy vra wat is die verskil tussen dit en dit? In hierdie geval, niks. Maar oor die algemeen is daar 'n paar verskille. En jy moet kyk in die GDB handleiding. Maar in hierdie geval, niks. Ons is geneig om druk te gebruik nie, want hoef ons nie veel meer as om te doen druk 'n enkele waarde. 

OK. So ons is op die lyn 80 van ons kode, opstel knoop * Kur gelyk aan lys. Kom ons druk Kur. Dit is gelyk aan die lys. Soet. Wag nie. Dit is gelykstaande aan iets. Dit beteken nie reg lyk. Daar gaan ons. Dit is omdat in GDB, regs, indien dit is die lyn wat jy op dit het nie uitgevoer nie. Sodat jy nodig het om werklik te tik volgende die lyn uit te voer voor sien sy resultate. So hier is ons. Ons het net uitgevoer hierdie lyn, vorige gelyk aan nul. So weer, as ons druk vorige sal ons nie sien nie vreemd. Maar as ons eintlik voer wat lyn, dan sal ons sien dat die lyn gewerk. 

So ons het Kur. Dit is beide goed. Reg? Nou is ons op hierdie lyn hier. Terwyl Kur nie gelyk null. Wel, wat doen Kur gelyk? Ons het net het dit geëwenaar null. Ons het dit gedruk word. Ek sal dit druk weer. So is dat terwyl lus gaan uit te voer? 

Publiek: No 

JASON Hirsch: So dat wanneer ek getik lyn, jy sien ons gespring al die pad af na die onderkant, terugkeer onwaar. En dan gaan ons valse om terug te keer en gaan terug na ons program en uiteindelik druk, soos ons gesien het, die insetsel was nie suksesvol nie. So, enigiemand enige idees oor wat ons nodig het om te doen dit op te los? Ek gaan om te wag totdat ek sien 'n paar hande optrek. Ons het nie uit te voer nie. Hou in gedagte, dit was die eerste ding wat ons doen. Ek gaan nie 'n paar om te doen. Ek gaan 'n paar om te doen. Omdat 'n paar beteken twee. Ek sal wag vir meer as twee. 

Die eerste plasing, Kur, by verstek gelyk aan nul. En dit loop net voer As Kur is nie null. So hoe kan ek kry om dit? Ek sien drie hande. Ek sal wag vir meer as drie. Marcus, wat dink jy? 

Publiek: Wel, as jy nodig het om dit te voer meer as een keer, jy het net verander dit na 'n do-while lus. 

JASON Hirsch: OK. Sal dit los ons probleem, al is? 

Publiek: In hierdie geval nie as gevolg van die feit dat die lys is leeg. So dan is jy waarskynlik net nodig om by te voeg 'n verklaring dat indien die lus uitgange dan moet jy aan die einde van die lys, op watter punt jy kan net plaas dit. 

JASON Hirsch: Ek hou daarvan. Dit maak sin. As die lus verlaat - want dit sal terugkeer valse hier. Dus, as die lus uitgange, dan is ons op die einde van die lys, of dalk die die begin van 'n lys indien daar is niks in dit, wat dieselfde is as die einde. So nou wil ons in te voeg iets hier. So hoe die kode kyk, Marcus? 

Publiek: As jy reeds 'die knoop malloced, kan jy net sê new_node-> langs gelyk aan nul, omdat dit het tot aan die einde. Of new_node-> langs gelyk aan nul. 

JASON Hirsch: OK. Jammer. New_node-> langs gelyk aan nul want ons is aan die einde. Dit beteken nie sit dit in Hoe kan ons dit in die lys? Right. Dit is net die opstel van dit gelyk aan. Nee Hoe doen ons eintlik sit dit in die lys? Wat is verwys na die einde van die lys? 

Publiek: Hoof. 

JASON Hirsch: Jammer? 

Publiek: Hoof wys aan die einde van die lys. 

JASON Hirsch: As daar is niks in die lys, is die hoof te wys op die einde van die lys. So dit sal werk vir die Eerste plasing. Wat van as daar is 'n paar dinge in die lys? As ons wil nie te stel kop gelyk aan new_node. Wat wil ons doen? Ja? Waarskynlik vorige. Sal dit werk? Onthou dat die vorige is net 'n verwysing na 'n knoop. En die vorige is 'n plaaslike veranderlike. So hierdie lyn sal 'n plaaslike veranderlike, vorige, gelyk aan of wys na die nuwe knoop. Dit sal eintlik nie sit dit in ons lys, al is. Hoe kan ons dit in ons lys? Akchar? 

Publiek: Ek dink jy Moenie huidige-> volgende. 

JASON Hirsch: OK. Kur-> volgende. So weer, die enigste rede waarom ons af hier is, wat beteken huidige gelyk? 

Publiek: Is gelyk aan nul. 

JASON Hirsch: En ja, wat gebeur as ons dit doen nul-> volgende? Wat gaan ons doen te kry? Ons sal 'n segmentering skuld. 

Publiek: Do Kur gelyk aan nul. 

JASON Hirsch: Dit is dieselfde ding as vorige, al is, want daar is 'n plaaslike veranderlike ons die opstel gelyk aan die nuwe knoop. Kom ons gaan terug na ons foto van die plaas iets. Sê ons inbring teen die einde van die lys, so reg hier. Ons het 'n huidige wyser wat wys na nul en 'n vorige punt dit is wys om 8. So wat doen ons nodig het om te werk, Avi? 

Publiek: Vorige-> volgende? 

JASON Hirsch: Vorige-> volgende is wat ons wil om te werk, want dit eintlik plaas dit op die einde van die lys. Ons het nog 'n fout, al is, dat ons gaan om te loop in. Wat is dat die fout? Ja? 

Publiek: Dit gaan om terug te keer valse in hierdie geval? 

JASON Hirsch: O, is word gaan valse om terug te keer. Maar daar is nog 'n fout. So ons sal moet sit in ruil waar. 

Publiek: vorige steeds gelyk Maak nul aan die bokant van die lys? 

JASON Hirsch: So vorige steeds gelyk aan nul aan die begin. So, hoe kan ons oor dit? Ja? 

Publiek: Ek dink jy kan 'n tjek te doen voor die tyd loop om te sien of dit is 'n leë lys. 

JASON Hirsch: OK. So laat ons gaan hier. Doen 'n tjek. Indien - 

Publiek: So as hoof gelyk is gelyk aan nul. 

JASON Hirsch: As hoof gelyk is gelyk aan nul - wat sal ons sê of dit is 'n leë lys. 

Publiek: En dan is jy doen hoof gelyk aan nuwe. 

JASON Hirsch: Hoof gelyk new_node? En wat anders moet ons doen? 

Publiek: En dan is jy terug waar. 

JASON Hirsch: Nie heeltemal nie. Ons ontbreek een stap. 

Publiek: New_node volgende het om aan te dui null. 

JASON Hirsch: Presies, Alden. En dan kan ons terug waar. OK. Maar dit is nog steeds 'n goeie idee om dinge te doen aan die einde van die lys, reg? Alle regte. Ons het nog steeds kan kry eintlik aan die einde van die lys. So is hierdie kode fyn as ons by die einde van die lys en daar is 'n paar dinge in die lys? Reg? Omdat ons nog Marcus se idee. Ons kan dit loop verlaat omdat ons is aan die einde van die lys. So het ons nog wil hierdie kodeer hier? 

Gehoor: Ja. 

JASON Hirsch: Ja. En wat moet ons dit te verander? Waar. Klink goed vir almal so ver? Enigiemand enige - Avi, het jy iets om by te voeg? 

Publiek: No 

JASON Hirsch: OK. Dus het ons het 'n paar veranderinge. Ons het die tjek gemaak voordat ons het in 'n leë lys. So het ons sorg geneem het van 'n leë lys. En hier is ons het sorg van die plaas iets aan die einde van die lys. So lyk dit soos hierdie, terwyl lus neem sorg van die dinge in tussen, iewers in die lys as daar is dinge in die lys. 

OK. Laat ons hierdie program weer. Nie suksesvol nie. 

Publiek: Jy het dit nie. 

JASON Hirsch: Ag, Ek het dit nie. Goeie punt, Michael. Kom ons voeg 'n make gekoppel. Line 87 is daar 'n fout. Line 87. Alden, dit was die lyn wat jy my gegee het. Wat is verkeerd? 

Publiek: Dit het te wees van nul. 

JASON Hirsch: Uitstekende. Presies reg. Dit moet nul wees. Kom ons maak weer. Stel. OK. Kom ons voeg drie. Die insetsel was suksesvol. Kom ons druk dit uit. Ag, as ons maar net kon gaan. Maar ons het nie gedoen word om die druk funksie nie. Kom ons tree iets anders. Wat moet ons in? 

Publiek: Sewe. 

JASON Hirsch: Sewe? 

Gehoor: Ja. 

JASON Hirsch: Ons het 'n seg skuld. So het ons een nie, maar ons kan duidelik kan nie twee. Dit is 05:07. Sodat ons kan ontfout hierdie vir drie minute. Maar Ek gaan vir ons om hier te verlaat en skuif op tafels te hash. Maar weereens, die antwoorde vir hierdie kode Ek sal dit per e-pos aan jou in 'n bietjie. Ons is baie naby aan dit. Ek raai u aan om uit te vind wat gaan hier aan en dit reg te stel. So ek sal e-pos wat jy hierdie kode as goed plus die oplossing - waarskynlik die oplossing later. Eerste hierdie kode. 

Die ander ding wat ek wil doen voordat ons afwerking is ons niks bevry. So ek wil om te wys wat valgrind lyk. As ons hardloop valgrind grense op ons program. / gekoppel. Weereens, volgens hierdie skuif, het ons moet valgrind hardloop met 'n soort van opsie, in hierdie geval - Lek-check = vol. So laat skryf valgrind - Lek-check = vol. So dit sal loop valgrind op ons program. En nou het die program loop eintlik. So ons gaan om dit te doen, net soos voor, sit iets in Ek gaan sit in drie. Dit werk. Ek gaan nie om te probeer om te sit in iets anders, want ons gaan 'n seg valse in daardie geval. So ek gaan net om op te hou. 

En nou sien jy hier lek en hoop opsomming. Dit is die goeie dinge wat jy wil om te kyk na. So het die hoop opsomming - dit sê, in gebruik uitgang - agt grepe in een blok. Dat een blok is die node ons malloced. Michael, jy het gesê voor 'n knoop is agt byt, want dit het die heelgetal en die wyser. So dit is ons node. En dan sê dit wat ons gebruik malloc sewe keer en ons bevry iets ses keer. Maar ons nooit vry genoem, so ek het geen idee wat dit praat. 

Maar is dit voldoende om te sê dat wanneer jou program lopies, is malloc genoem in 'n paar ander plekke wat ons hoef nie te bekommer nie. So malloc is waarskynlik genoem in sommige plekke. Ons hoef nie bekommerd wees oor waar. Maar dit is regtig ons. Die eerste reël is ons. Ons het daardie blok. En jy kan sien dat hier in die lek opsomming. Nog beskikbaar - agt grepe in een blok. Dit beteken dat die geheue - Ons het uitgelek dat die geheue. Beslis verloor - iets is verlore vir die goeie. Die algemeen, sal jy nie sien nie daar nie. Nog beskikbaar is oor die algemeen waar sal jy sien dinge, waar jy wil om te kyk om te sien wat kode wat jy moet het bevry, maar jy het vergeet om te bevry. 

En dan as dit nie die geval was, As ons het vrye alles, ons kan seker maak dat. Laat ons net die program nie om in enigiets. Jy sal sien hier in gebruik by die uitgang - nul grepe in nul blokke. Dit beteken dat ons het niks oorgehad wanneer hierdie program opgewonde. So voor die draai in pset6, hardloop valgrind en maak seker jy het nie enige geheue lekkasies in jou program. As jy enige vrae het met valgrind, voel vry om uit te reik. Maar dit is hoe jy dit gebruik. Baie eenvoudig - kyk of jy het in gebruik by die uitgang - enige grepe in enige blokke. 

So het ons gewerk het op insetsel knoop. Ek het twee ander funksies hier - druk nodes en vrye nodes. Weereens, dit is funksies wat goed gaan wees vir jou om te oefen want hulle sal jou help om nie net met hierdie monster oefeninge, maar ook op die probleem gestel. Hulle kaart op nou mooi dinge jy gaan hê om te doen in die probleem stel. Maar ek wil om seker te maak raak ons ​​aan alles. En hash tabelle is ook belangrik om te wat ons doen in artikel hierdie week - of in die probleem stel. 

So ons gaan die artikel te voltooi praat oor hash tabelle. As jy sien ek 'n bietjie hash tafel. Dit is nie wat ons praat oor, egter. Ons praat oor 'n ander tipe hash tabelle. En in sy kern, 'n hash tafel is niks meer as 'n verskeidenheid plus 'n hash funksie. Ons gaan om te praat vir 'n bietjie net om te maak seker dat almal verstaan ​​wat 'n hash funksie is. En ek vertel jou nou dat dit niks meer as twee dinge - 'n skikking en 'n hash funksie. En hier is die stappe deur wat hierdie bedryf. 

Daar is ons verskeidenheid. Daar is ons funksie. In die besonder, hash funksies nodig het om te doen 'n paar van die dinge wat met hierdie. Ek gaan spesifiek praat oor hierdie probleem stel. Dit is waarskynlik gaan om te neem in 'n string. En wat gaan dit om terug te keer? Watter tipe data? Alden? Jou hash funksie terugkeer? 'N heelgetal. So dit is wat die hash tabel bestaan ​​uit - 'n tafel in die vorm van 'n skikking en 'n hash funksie. Hoe werk dit? Dit werk in drie stappe. Ons gee dit 'n sleutel. In hierdie geval, sal ons gee dit 'n string. Ons noem die hash funksie per stap een op die sleutel en ons kry 'n waarde. 

Spesifiek, sal ons sê kry ons 'n heelgetal. Dit heelgetal is, is daar baie spesifieke grense aan wat daardie heelgetal wees. In hierdie voorbeeld, ons verskeidenheid is van die grootte drie. So, wat getalle kan daardie getal is. Wat is die omvang van geldige waardes vir dat heelgetal, die terugkeer van hierdie soort hash funksie? Nul, een en twee. Die punt van die hash funksie is om te uit te vind die plek in die skikking waar ons die sleutel gaan. Daar is slegs drie moontlike plekke hier - nul, een, of twee. So hierdie funksie beter opbrengs nul, een, of twee. Sommige geldig indice in hierdie reeks. 

En dan, afhangende van waar dit terugkeer, jy kan sien daar verskeidenheid oop in hakies die waarde. Dit is waar ons die sleutel. So ons gooi in die pampoen, ons uit nul. Op verskeidenheid bracket 0, ons sit pampoen. Ons gooi in katte, ons kry een. Ons het die kat aan die een. Ons sit in spin. Ons kry twee. Ons sit spin op verskeidenheid bracket twee. Dit sou so lekker wees as dit het gewerk soos dit. Maar helaas, soos ons sal sien, dit is 'n bietjie meer ingewikkeld. 

Voordat ons daar enige vrae oor hierdie basiese opstel van 'n hash tafel? Dit is 'n beeld van presies wat ons het op die bord. Maar omdat ons getrek het dit op die raad, ek gaan nie te gaan in dit verder. In wese sleutels, die magic black box - of in hierdie geval, teal box - van 'n hash funksie sit hulle in emmers. En in hierdie voorbeeld ons nie om die naam. Ons is besig om die verband selfoon nommer van die naam in die emmer. Maar jy kan baie goed net het die naam in die emmer. 

Dit is net 'n prentjie van wat Ons het op die bord. Ons het slaggate, al is. En daar is twee in die besonder skyfies wat ek wil om te gaan. Die eerste een is oor die 'n hash funksie. So ek vra die vraag, wat maak 'n goeie hash funksie? Ek gee twee antwoorde. Die eerste is dat dit deterministies. In die konteks van hash funksies, wat beteken dit? Ja? 

Publiek: Dit kan die indeks in konstante tyd? 

JASON Hirsch: Dit is nie wat dit beteken nie. Maar dit is 'n goeie raaiskoot. Enigiemand anders het 'n raaiskoot na wat dit beteken? Dat 'n goeie hash funksie is deterministiese? Annie? 

Publiek: dat 'n belangrike net gekarteer kan word op een plek in die hash tafel. 

JASON Hirsch: Dis presies reg. Elke keer as jy in die pampoen, dit is altyd terug nul. As jy in die pampoen en jou hash funksie gee terug nul, maar het 'n waarskynlikheid van die terugkeer van iets anders groter as nul - so miskien kan dit weer een soms of twee ander tye - dit is nie 'n goeie hash funksie. Jy is presies reg. Jou hash funksie moet terugkeer om die presies dieselfde getal, in hierdie geval, vir presies dieselfde string. 

Miskien is dit terug presies dieselfde heelgetal vir presies dieselfde string ongeag van hoofletters. Maar in daardie geval is dit steeds deterministiese omdat verskeie dinge is gekarteer op die dieselfde waarde. Dit is fyn. Solank as wat daar is net een uitset vir 'n gegewe insette. 

OK. Die tweede ding is dat dit terugkeer geldig indekse. Ons het tot wat vroeër. Dit hash funksie - oh boy - 'n hash funksie moet terugkeer geldig indekse. So sê - laat se terug na hierdie voorbeeld gaan. My hash funksie tel tot die letters in die woord. Dit is die hash funksie. En opbrengste wat heelgetal. So as ek die woord A, dit is gaan een om terug te keer. En dit gaan 'n reg te stel hier. Wat as ek in die woord kolf? Dit gaan om terug te keer drie. Waar kom kolf gaan? 

Dit pas nie. Maar dit moet iewers te gaan. Dit is my hash tafel na alles, en alles moet iewers te gaan. So waar moet kolf gaan? Enige gedagtes? Raai? Goeie raai? 

Publiek: Zero. 

JASON Hirsch: Hoekom nul? 

Publiek: Omdat drie modulo drie nul? 

JASON Hirsch: Drie modulo drie is nul. Dit is 'n groot raaiskoot, en dat die inligting korrek is. So in hierdie geval is dit moet waarskynlik gaan op nul. So 'n goeie manier om te verseker dat hierdie hash funksie gee slegs geldig indekse word om dit te modulo deur die grootte van die tafel. As jy modulo net hierdie opgawes deur drie, gaan jy altyd te kry iets tussen nul, een, en twee. En as dit altyd terug sewe en jy altyd modulo deur drie, is jy altyd dieselfde ding te kry. 

So dit is nog steeds deterministiese As jy modulo. Maar wat sal verseker dat jy nooit iets kry - 'n ongeldig bedryf. Die algemeen, wat moet gebeur modulo binne-in jou hash funksie. So jy hoef nie te bekommerd oor hierdie. Jy kan net verseker dat dit is 'n geldige indice. Enige vrae oor hierdie potensiële slaggat? 

OK. En daar gaan ons. Volgende potensiële slaggat, en dit is die groot een. Wat as twee sleutels kaart dieselfde waarde? So is daar twee maniere om dit te hanteer. Die eerste een is lineêr genoem indringende, wat ek gaan nie oor te gaan. Maar jy moet vertroud wees met hoe wat werk en wat dit is. 

Die tweede een gaan ek om oor te gaan want dit is die een wat baie mense sal waarskynlik uiteindelik besluit te gebruik in hul probleem stel. Natuurlik, jy hoef nie. Maar vir die probleem stel, baie mense geneig om te kies 'n hash tafel te skep met aparte aaneenskakeling te implementeer hul woordeboek. So ons gaan om te gaan oor wat dit beteken 'n gemors tafel te skep met afsonderlike aaneenskakeling. 

So het ek in die pampoen. Dit gee nul. En ek sit hier pampoen. Toe ek in die - Wat is 'n ander Halloween-tema ding? 

Publiek: Candy. 

JASON Hirsch: Candy! Dit is 'n groot een. Ek het in lekkergoed, en lekkergoed gee my ook nul. Wat moet ek doen? Enige idees? Omdat jy al die soort van weet wat afsonderlike aaneenskakeling is. So enige idees wat om te doen? Ja. 

Publiek: Om die string eintlik in die hash tafel. 

JASON Hirsch: So ons gaan teken die goeie idee hier. OK. 

Publiek: Het die hashtable [Onhoorbaar] die wyser wat verwys na die begin van 'n lys. En dan het die pampoen die eerste waarde in wat gekoppel lys en lekkergoed die tweede waarde wat gekoppel lys. 

JASON Hirsch: OK. Marcus, wat was uitstaande. Ek is van plan om dit af te breek. Marcus sê nie oorskryf pampoen. Dit sou sleg wees. Moenie lekkergoed iewers anders. Ons gaan hulle te sit sowel by nul. Maar ons gaan om te gaan met om hulle by zero deur skep 'n lys op nul. En ons gaan 'n lys van te skep alles wat gekarteer is aan nul. En die beste manier waarop ons geleer het om te skep 'n lys wat kan groei en krimp dinamies is nie binne 'n ander skikking. So nie 'n multi-dimensionele skikking. Maar om net 'n geskakelde lys. 

So, wat hy voorgestel het - Ek gaan 'n nuwe te kry - is die skep van 'n skikking met wysers, 'n verskeidenheid van wysers. OK. Enige idee of wenk wat die tipe van hierdie wenke moet wees? Marcus? 

Publiek: Pointers - 

JASON Hirsch: Omdat jy het gesê 'n geskakelde lys, so - 

Publiek: Node riglyne? 

JASON Hirsch: Node wysers. As die dinge in ons verbind lys is nodes dan is hulle moet knoop wysers. En wat doen hulle aanvanklik gelyk? 

Publiek: null. 

JASON Hirsch: null. So daar is ons leë ding. Pampoen opbrengste nul. Wat doen ons? Loop my deur dit? Eintlik, Marcus my al gegee het. Iemand anders loop my deur dit. Wat doen ons wanneer ons - dit lyk baie soortgelyk aan wat ons net doen. Avi. 

Publiek: Ek gaan 'n raaiskoot te neem. So wanneer jy lekkergoed. 

JASON Hirsch: Ja. Wel, ons het pampoen. Kom ons kry ons eerste een. Ons het pampoen. 

Publiek: OK. Pampoen opbrengste nul. So jy sit dit in daardie. Of eintlik, jy sit dit in die geskakelde lys. 

JASON Hirsch: Hoe doen ons sit dit in die geskakelde lys? 

Publiek: O, die werklike sintaksis? 

JASON Hirsch: Slegs loop - sê meer. Wat doen ons? 

Publiek: Jy voeg net dit as die eerste knoop. 

JASON Hirsch: OK. So het ons ons node, pampoen. En nou hoe kan ek voeg dit? 

Publiek: Jy ken dit aan die wyser. 

JASON Hirsch: Watter wyser? 

Publiek: Die wyser op nul. 

JASON Hirsch: So waar doen hierdie punt? 

Publiek: Om nou van nul. 

JASON Hirsch: Wel, dit is wys om null. Maar ek is om in die pampoen. So waar moet dit wys? 

Publiek: Om pampoen. 

JASON Hirsch: Om pampoen. Presies. So dui dit op pampoen. En waar doen dit wyser in die pampoen punt? Om 

Publiek: null. 

JASON Hirsch: Om null. Presies. So het ons net ingevoeg iets in die lys. Ons het net hierdie kode het om dit te doen. Byna ons amper het dit heeltemal gekraak. Nou voeg ons lekkergoed. Ons lekkergoed gaan ook aan nul. So, wat doen ons met lekkergoed? 

Publiek: Dit hang af van die vraag of nie ons probeer om dit uit te sorteer. 

JASON Hirsch: Dis presies reg. Dit hang af van die vraag of Ons probeer om dit uit te sorteer. Kom ons aanvaar dat ons nie gaan om dit te sorteer. 

Publiek: Wel, dan, as ons bespreek voor, is dit die eenvoudigste net om dit te sit reg aan die begin so die wyser van nul punte te lekkergoed. 

JASON Hirsch: OK. Hou op. Laat my skep lekkergoed reg hier. So dit wyser - 

Publiek: Ja, nou moet word verwys na lekkergoed. Toe het die verwysing van lekkergoed punt pampoen. 

JASON Hirsch: Soos wat? En sê ons het 'n ander ding te karteer aan nul? 

Publiek: Wel, jy moet net doen dieselfde ding? 

JASON Hirsch: Doen dieselfde ding. So in hierdie geval, as ons dit nie doen nie wil hou dit gesorteer is dit klink eerder eenvoudig. Ons neem die wyser in die indice gegee deur ons hash funksie. Ons het die punt om ons nuwe knoop. En dan ook al dit was wys voorheen - In hierdie geval nul, in die tweede geval pampoen - dat alles wat dit is wys om Voorheen het ons by te voeg in die volgende van ons nuwe knoop. Ons is die inbring van iets in die begin. In werklikheid is dit 'n baie makliker as probeer om die lys gesorteer te hou. Maar weereens, sal soek wees meer ingewikkeld hier. Ons sal altyd het om te gaan tot die einde. 

OK. Enige vrae oor afsonderlike aaneenskakeling? Hoe dit werk? Vra hulle asseblief nou. Ek wil regtig om te maak seker dat jy al verstaan ​​voordat ons kop uit. 

Publiek: Hoekom dink jy sit pampoen en lekkergoed in dieselfde deel van die hash tafel? 

JASON Hirsch: Goeie vraag. Hoekom moet ons hulle in dieselfde deel van die hash tafel? Wel, in hierdie geval ons hash funksie opbrengste nul vir beide van hulle. So wat hulle nodig het om te gaan op indice nul want dit is waar ons gaan kyk vir hulle as ons ooit hulle wil kyk. Weereens, met 'n lineêre indringende benadering sou ons nie sit hulle albei op nul. Maar in die afsonderlike ketting benadering, ons gaan hulle te sit sowel by zero en dan 'n lys af van nul. 

En ons wil nie pampoen te vervang eenvoudig vir dat, omdat dan sal ons aanvaar dat pampoen was nooit plaas. As ons net een ding hou in die plek wat sleg sou wees. Dan sou daar geen kans van ons ooit - As ons ooit 'n duplikaat het, dan het ons wil net vee ons aanvanklike waarde. So dit is hoekom ons doen hierdie benadering. Of dit is hoekom ons gekies het - maar weer, ons verkies om die afsonderlike aaneenskakeling benadering, waarin daar is baie ander benaderings 'n mens kan kies. Maak dit jou vraag? 

OK. Carlos. Lineêre indringende sou betrek - As ons 'n botsing op nul, ons sou lyk in die volgende plek om te sien of dit was oop en sit dit daar. En dan kyk ons ​​in die volgende sport en sien of dit was oop en sit dit daar. So vind ons die volgende beskikbare oop plek en sit dit daar. Enige ander vrae? Ja, Avi. 

Publiek: As 'n opvolg op dat, wat bedoel jy deur die volgende plek? In die hash tafel of in 'n geskakelde lys. 

JASON Hirsch: Vir lineêre ontwikkeling, geen geskakelde lyste. Die volgende plek op die hash tafel. 

Publiek: OK. So het die hash tafel sou wees geïnisialiseer met die grootte - soos die aantal snare dat jy inbring? 

JASON Hirsch: Jy sou dit wil wees baie groot. Ja. Hier is 'n prentjie van wat ons net getrek op die bord. Weereens, ons het 'n botsing reg hier. by 152. En jy sal sien ons ' 'n geskakelde lys van dit af. Weereens, die hash tafel aparte aaneenskakeling benadering is nie die een wat jy moet neem vir probleme soos ses, maar is een wat 'n baie studente is geneig om te neem. So op daardie noot, laat ons praat kortliks voordat ons kop uit oor die probleem ses, en dan sal ek 'n storie met jou deel. Ons het drie minute. 

Probleem stel ses. Jy het vier funksies - vrag, kyk, die grootte en aflaai. Vrag - Wel, ons het al baie oor load nou net. Ons het las op die bord. En ons het selfs begin kodering 'n baie inbring in 'n geskakelde lys. So vrag is nie veel meer as wat ons nou net gedoen het. 

Check is wanneer jy iets gelaai. Dit is dieselfde proses soos hierdie. Dieselfde eerste twee dele waar jy gooi iets in die hash funksie en kry die waarde daarvan. Maar nou is ons nie die inbring nie. Nou is ons op soek na dit. Ek het die voorbeeld kode geskryf vir die vind van iets in 'n geskakelde lys. Ek moedig julle wat om te oefen. Maar intuïtief vind iets redelik soortgelyk aan die inbring iets. Trouens, ons het 'n foto van die vind van iets in 'n geskakelde lys, beweeg deur totdat jy aan die einde. En as jy het aan die einde en kon nie vind nie, dan is dit nie daar nie. So dit is tjek, wese. 

Volgende is die grootte. Kom ons slaan grootte. Ten slotte het jy los. Los is een wat ons het nie getrek op die bord of gekodeer nie. Maar ek u aanmoedig om te probeer om die kodering dit in ons voorbeeld gekoppel lys voorbeeld. Maar los intuïtief is soortgelyk aan gratis - of ek bedoel is soortgelyk aan gaan. Behalwe vir nou elke keer as jy gaan deur, is jy nie net om toe te sien as jy jou waarde daar. Maar jy neem dat knoop en bevry het, in wese. Dit is wat, aflaai vra om te doen. Gratis alles wat jy het malloced. So jy gaan deur die hele lys weer, gaan deur die hele hash tabel weer. Hierdie keer kyk nie om te sien wat daar is. Net bevry wat daar is. 

En uiteindelik grootte. Grootte moet geïmplementeer word. As jy nie die grootte te implementeer nie - Ek sal sê dit soos hierdie. As jy nie die grootte presies implementeer nie een lyn van kode, insluitend die terug verklaring, jy is doen grootte verkeerd. So maak seker dat die grootte, vir 'n volledige ontwerp punte, jy doen dit in presies een lyn van kode, insluitend die terugkeer verklaring. 

En moenie pak nog nie op, Akchar. Gretig bever. Ek wou dankie ouens te sê vir die komende artikel. Het jy 'n Happy Halloween. Dit is my kostuum. Ek sal dra hierdie op Donderdag As ek sien jy op kantoorure. En as jy nuuskierig is oor 'n paar meer agtergrond tot hierdie kostuum, voel vry om te check 2011 artikel vir 'n storie oor hoekom ek dra die pampoen kostuum. En dit is 'n hartseer storie. So maak seker dat jy Sommige weefsel in die buurt. Maar op daardie, indien u enige vrae wat ek sal rondom stok buite na artikel. Sterkte met die probleem sit ses. En soos altyd, indien u enige vrae, laat my weet.