JASON Hirschhorna: Vabljeni vsi na oddelku Seven. Mi smo v sedmih teden tečaja. In ta prihajajoči četrtek je noč čarovnic, zato sem oblečen kot buče. Nisem mogel ukrivijo in dal na moji čevlji, tako da je, zakaj sem Samo nosil nogavice. Jaz tudi ne nosim ničesar pod to, da ne morem vzleteti, če je moteča za vas. Se opravičujem vnaprej za to. Vam ni treba predstavljati kaj se dogaja. Nosim boksarice. Torej je vse v redu. 

Imam daljšo zgodbo o tem, zakaj sem oblečen kot buče, ampak bom prihranite za kasneje v tem razdelku ker jaz želim, da bi začeli. Imamo veliko zanimivih stvari iti čez ta teden. Večina od njih se neposredno nanašajo na to Problem set teden, pravopisne napake. Bomo šli čez povezano Seznami in razpršene tabele za celoten del. Sem dal ta seznam se vsak teden, seznam Sredstva za vas, da vam pomaga z gradivo na tej poti. Če z izgubo, ali če iščete nekaj Za več informacij si oglejte enega od teh virov. 

Again, pset6 je pravopisnih napak, pset ta teden. In tudi vas spodbuja, in jaz Spodbujam vas, da uporabite kakšen drug sredstev posebej za to pset. Zlasti tri sem Navedene na zaslonu - GDB, ki smo bili seznanjeni z in se uporabi za nekaj časa sedaj, je bo zelo koristno ta teden. Zato sem dal to gor. Ampak ko delate s C, morate vedno uporabljati gdb, da razhroščevanje programov. Ta teden tudi valgrind. Ali kdo ve, kaj valgrind počne? 

PUBLIKA: To preverja spomin razpoka? 

JASON Hirschhorna: Valgrind Pregledi za spomin razpoka. Torej, če ste malloc nekaj v vašem Program, ki ste ga prosi za spomin. Ob koncu svojega programa, imate pisati brezplačno na vse, kar ste malloced, da bi spomin nazaj. Če ne boste napisali prosti konec in vaš program prihaja do zaključka, Vse se bo samodejno osvoboditi. In za majhne programe, je ni tako velika stvar. Ampak, če pišete daljše delovanje Program, ki se ne zapre, nujno, v nekaj minutah ali A nekaj sekund, nato pa spomin pušča lahko postane velik posel. 

Torej za pset6, pričakovanje je, da boste imeli nič spomin razpoka z vaš program. Če želite preveriti, memory leaks, teči valgrind in to vam bom dal nekaj lepih izhodna najemnin veš, ali ali ni bilo vse zastonj. Bomo vaditi z njo kasneje danes, upam. 

Končno, ukaz diff. Ste uporabili nekaj podobnega, da ga v pset5 z orodjem pokukati. Dovoljeno vas, da si notri. Ki ste ga uporabili tudi za razlikovanje, preveč, na Problem je določeno spec. Toda v ti dovolijo primerjanje dveh datotek. Lahko primerjate datoteko bitnih slik in info Glave rešitev za zaposlene in vaša rešitev v pset5 če ste se odločili, da jo uporabljajo. Prim vam bo omogočilo to, da, kot je dobro. Lahko primerjate pravilen odgovor za Problem ta teden naj bi vaš odgovor in videli, če je vrstic gor ali glejte kje so napake. 

Torej, to so tri dobre orodja, ki jo je treba uporabiti za ta teden, in vsekakor preverite svoj program s temi tremi orodji preden ga noter Še enkrat, kot sem že omenil vsak teden, Če imate kakršne koli povratne informacije za mene - tako pozitiven in konstruktiven - vas prosimo, da se odpravite na spletno stran na dnu te diapozitiv in vhod je tam. Res sem hvaležen za kakršen koli in vse povratne informacije. In če mi daš določene stvari, ki jih Jaz lahko naredim za izboljšanje ali da sem delaš dobro, da bi me rad naprej, bom vzel k srcu in res trudim poslušati za vaše mnenje. Ne morem obljubiti, da bom naredil Vse, čeprav, kot je nošenje bučno kostum vsak teden. 

Tako, da bomo porabili večino oddelek, kot sem že omenil, govorim o povezani seznami in hash tabele, ki bo neposredno uporabljajo za Problem nastavite ta teden. Povezani seznam, da bomo šli čez razmeroma hitro, ker smo porabili kar precej časa bo nad njim v oddelku. In tako bomo dobili naravnost v kodiranje probleme, povezane sezname. In potem na koncu bomo govorili o hash tabele in kako se uporabljajo za to Problem teden nastavljena. 

Videli ste to kodo prej. To je struct, in se opredeljuje nekaj novega, se imenuje vozlišče. In znotraj vozlišče je celo število tu in tam je kazalec drugo vozlišče. Videli smo pred tem. To je prišlo na površje Že nekaj tednov. Združuje kazalce, ki smo bili sodelovanje in konstruktov, ki omogočajo kombiniranje dveh različnih Stvari v eno vrsto podatkov. 

Obstaja veliko dogaja na zaslonu. Ampak vse to naj bi bilo razmeroma seznanjeni s tabo. V prvi vrstici, smo razglasi novo vozlišče. In potem znotraj tega novega vozlišča, sem iz celo s tem, da vozlišče enem. Vidimo v naslednji vrstici delam printf ukaz, vendar sem posivel ukaz printf ker res Pomemben del je ta vrsta je tukaj - new_node.n. Kaj pika pomeni? 

PUBLIKA: Pojdi na vozlišče in oceniti vrednost n za to. 

JASON Hirschhorna: To je Točno tako. Pika pomeni, dostop z N, part tega novega vozlišča. Naslednja postavka za kaj? Michael. 

PUBLIKA: Ustvarja novo vozlišče da bodo kazale na novo vozlišče. 

JASON Hirschhorna: Torej ne ustvariti novo vozlišče. Ustvarja kaj? 

PUBLIKA: kazalec. 

JASON Hirschhorna: kazalec na vozlišče, kot je navedeno v tem vozlišču * tukaj. Tako da ustvari kazalec na vozlišče. In ki vozlišče je obrnjena da, Michael? 

PUBLIKA: New vozel? 

JASON Hirschhorna: Novo vozlišče. In to je tam obrnjena ker smo ji dal naslov novega vozlišča. In zdaj, v tej vrstici vidimo dva različna načina izraža isto stvar. In sem želel poudariti, kako ti dve stvari so enake. V prvi vrsti smo dereference kazalec. Torej gremo na vozlišče. To je, kaj pomeni ta zvezda. Videli smo, da je pred s kazalci. Pojdi na to vozlišče. To je v oklepaju. In potem dostopate preko operaterja dot n element vozlišča. 

, Tako da je ob sintakso videli smo tukaj in zdaj uporabo s kazalcem. Seveda, da postane neke vrste zaseden, če pišete tiste oklepaje - da je zvezda in pika. To postane malo zaseden. Torej, imamo nekaj skladenjsko sladkorja. In ta tukaj - ptr_node-> n. To počne točno isto stvar. Torej ti dve vrstic kode so enakovredna in bo storila točno isto stvar. 

Ampak sem želel izpostaviti tiste, preden gremo vse nadaljnje, tako da boste razumeli da je ta stvar tukaj je res samo skladenjska sladkor za Dereferenciranje kazalec, nato pa bo n del tega struct. Vsa vprašanja v zvezi s tem diapozitiv? OK. 

Tako da smo šli skozi nekaj operacij, ki jih lahko storite na povezani seznam. Povezani seznam, odpoklic, je serija vozlišča, ki kažejo, da med seboj. In smo se običajno začnejo s kazalcem imenovani glavo, na splošno, ki kaže na Najprej v seznamu. Torej, v prvi vrstici tu, imamo izvirno L prva. Tako, da stvar, ki jo lahko zamislite - to besedilo, tukaj si lahko zamislite kot samo kazalec, ki smo jih shranijo nekje, da točke na prvi element. In v tem povezani seznam imamo štiri vozle. Vsako vozlišče je velika škatla. Večje okno v notranjosti velika polje je celo del. In potem imamo kazalec del. 

Ta polja ne privlači Lestvica ker kako velik je celo v bajti? Kako zdaj velik? Štiri. In kako velik je kazalec? Štiri. Torej res, če smo bili, da pripravi to obsega obe polji bi enake velikosti. V tem primeru želimo vstaviti Nekaj ​​v povezanem seznamu. Torej si lahko ogledate tukaj smo vstavljanje pet sva prečkala prek povezani seznam, kje najti pet gre, nato pa ga vstavite. 

Oglejmo prekinil niz in pojdi malo bolj počasi. Grem, da kaže na krovu. Torej, imamo pet vozlišče, ki Ustvarili smo v mallocs. Zakaj se vsi smejali? Samo hecam. OK. Zato smo malloced pet. Ustvarili smo to vozlišče nekje drugje. Imamo pripravljen iti. Začnemo na sprednjem delu naš seznam z dvema. In želimo, da vstavite v urejenem način. 

Torej, če smo videli dva in želimo postaviti v petih, kaj bomo storili, ko smo videli nekaj manj od nas? Kaj? Želimo, da vstavite pet v to povezani seznam, držimo tako, da razporejene. Vidimo številka dve. Torej, kaj naj naredimo? Marcus? 

PUBLIKA: Call kazalec na naslednje vozlišče. 

JASON Hirschhorna: In zakaj gremo na naslednjega? 

PUBLIKA: Ker je naslednje vozlišče v seznamu. In vemo le to drugo lokacijo. 

JASON Hirschhorna: In pet večja kot dve, zlasti. Ker želimo, da ostane razvrščeni. Torej pet je večje od dva. Torej gremo na naslednjo. In zdaj smo dosegli štiri. In kaj se zgodi, ko smo dosegli štiri? 

Pet je večje od štiri. Tako smo naprej. Zdaj pa smo že ob šestih. In kaj vidimo ob šestih? Ja, Carlos? 

PUBLIKA: Šest je večje od pet. 

JASON Hirschhorna: Six je več kot pet. Tako, da je, če želimo vstaviti pet. Vendar pa imejte v mislih, da če bomo ima samo en kazalec tukaj - to je naš dodaten kazalec, da je prehaja skozi seznam. In mi kaže na šest. Izgubili smo spremljali, kaj pride pred šestimi. Torej, če želimo nekaj vstavili v Ta seznam je vodenje razporejene smo Verjetno je treba, koliko nasvetov? 

PUBLIKA: Two. 

JASON Hirschorn: Dva. Ena slediti toku ena in ena, da bi spremljali prejšnja. To je samo enkrat povezani seznam. To gre samo v eno smer. Če bi imeli dvojno povezani seznam, kjer Vse je poudaril, da stvar po njo in stvar pred njim, nato mi ne bi bilo treba storiti. Toda v tem primeru ne želimo izgubiti tir, kar je pred nami, v primeru moramo vstaviti pet nekje v sredini. Recimo, da so vstavljanje devet. Kaj bi se zgodilo, če imamo osem? 

PUBLIKA: Morali bi dobil to nulte točke. Namesto da nulte točke bi si moral dodati element in nato opozoriti na devet. 

JASON Hirschorn: Točno tako. Tako smo dobili osem. Dosežemo konec seznama, ker To kaže na null. In zdaj, namesto da bi to imelo za null moramo opozoriti na našo novo vozlišče. In smo postavili kazalec našo novo vozlišče na null. Ima kdo kakšna vprašanja o vstavljanju? Kaj pa, če ne skrbi vodenje seznama razporejene? 

PUBLIKA: Zabij na začetek ali konec. 

JASON Hirschorn: Vrzi na začetek ali konec. Katerega naj storimo? Bobby? Zakaj konec? 

PUBLIKA: Ker začetek je že napolnjena. 

JASON Hirschorn: OK. Začetek je že napolnjena. Kdo želi nasprotovati Bobbyju. Marcus. 

PUBLIKA: No, boste verjetno želeli ga držijo na začetku, ker drugače, če ste jo dali na konec bi si morali prečkanje celoten seznam. 

JASON Hirschorn: Točno tako. Torej, če razmišljate o času izvajanja, teka vstavljanja na koncu bi n, velikost tega. Kaj je velik O teka vstavljanje na začetku? Constant čas. Torej, če vam ni mar za vodenje Nekaj ​​razporejene, veliko bolje, da samo vstavite na začetku tega seznama. In to je mogoče storiti v enakem času. 

OK. Naslednja operacija našli, kar drugi - to smo oblikovali kot iskanje. Ampak bomo odmisliti povezani seznam za nek objekt. Vi ste videli kodo iskanje preden se je v predavanju. Vendar smo nekako le to storil z vstaviti, ali vsaj vstavljanje Nekaj ​​razporejene. Pogledaš skozi, bo vozlišče, ki ga vozlišče, dokler ne najdete številko, ki ste išče. Kaj se zgodi, če ne pridete Konec seznamu? Pravijo, iščem devet in I dosežejo konec seznama. Kaj naj naredimo? 

PUBLIKA: Return false? 

JASON Hirschorn: Return false. Nismo našli. Če pridete do konca seznama in niste našli številko, ki ste jo iščete, ni tam. Imate vprašanja nahajamo? Če je to razvrščenega.Vse seznam, kaj bi drugačna za naše iskanje? Ja. 

PUBLIKA: Bilo bi našli prvo vrednost ki je večja od enega iščete in nato vrne false. 

JASON Hirschorn: Točno tako. Torej, če je to razvrščenega.Vse seznam, če želimo priti do nekaj, kar je večje od tistega, kar iščemo, nam ni treba, da nadaljuj na koncu seznama. Mi lahko na tej točki vrne false ker ne gremo, da ga najdejo. Vprašanje je zdaj, smo se pogovarjali o vodenje povezanih seznamov razporejene, jih gojijo razvrščeni. To se dogaja, da nekaj, kar si Verjetno bomo morali razmišljati o ko, če kodiranje problem nastaviti pet Izberite razpršene tabele z ločeno verižni pristop, ki o tem bomo govorili kasneje. 

Vendar je vredno, da seznam sortirati in nato lahko morda imajo hitrejše iskanje? Ali je bolje, da se hitro vstaviti nekaj v stalnem runtime potem pa imajo več iskati? To je kompromis tam, da vam se mora odločiti, kaj je bolj primerno za svoj problem. In tam ni nujno, da ena popolnoma pravilen odgovor. Vsekakor pa to odločitev, ki jo dobite da bi, in verjetno dobro, da branijo da, recimo, komentar ali dva, zakaj ste izbrali eno nad drugo. 

Končno, brisanje. Videli smo izbrisali. To je podobno iskanju. Iščemo za element. Povejte, da smo poskušali izbrisati šest. Tako smo našli šest tukaj. Stvar, ki jo moramo narediti, da bomo storiti, je, da karkoli se kaže na šest - kot smo videli v koraku dve dol - kar se kaže na šest potrebami do preskočite šest sedaj in se spremeni v kar šest kaže, da. Nočemo, da bi kdaj starših ostalo naš seznam, ki ga pozabijo, da določi, da Predhodna kazalec. In potem včasih, odvisno o programu, pa bom samo v celoti izbrisati to vozlišče. Včasih boste želeli, da se vrnete vrednost, ki je v tem vozlišču. Torej, to je, kako črtanje dela. Vsa vprašanja glede izbrisati? 

PUBLIKA: Torej, če boste za brisanje da bi si samo uporabo brezplačno, ker verjetno je malloced? 

JASON Hirschorn: Če želite sprostiti nekaj, kar je ravno prav in vi ga malloced. Povejte, da smo želeli vrniti to vrednost. Morda bomo vrnili šest, nato pa brez to vozlišče in brez klic na njej. Ali pa bi verjetno pokličite brezplačno najprej in se nato vrne šest. 

OK. Torej gremo na vaditi kodiranja. Bomo kodo tri funkcije. Prvi se imenuje insert_node. Torej imate kodo, ki sem vam po e-pošti, in Če gledate to kasneje lahko dostopate kodo v linked.c na spletni strani CS50. Toda v linked.c, da je nekaj Okostje kodo, ki je že je napisal za vas. In potem je tukaj še nekaj Funkcije morate pisati. 

Prvi bomo napišite insert_node. In kaj počne insert_node se pravi vstavi celo število. In ti daje celi števili v povezanem seznamu. In predvsem, morate da seznam razvrščeni od najmanjše do največje. Prav tako si ne želite, da vtikajte dvojnikov. Končno, kot lahko vidite insert_node vrne bool. Torej boš moral pustiti uporabnik ve ali vložek je ali ni Uspešno ga vrne resnična ali neresnična. Ob koncu tega programa - in v tej fazi ne potrebujete skrbeti za osvoboditev ničesar. Torej, vse kar delaš je pokazal celo in ga vstavite v seznamu. 

To je tisto, kar vas prosim, da storite zdaj. Again, v linked.c, ki ga Vse imajo, je koda okostje. In bi morali videti proti dnu Izjava vzorec funkcija. Vendar pa, preden gredo v to kodiranje v C, sem močno vam svetujemo, da gredo skozi korake smo bili vadil vsak teden. Smo že šli skozi slika tega. Torej bi morali imeti nekaj razumevanja kako to deluje. Vendar bi vas pozivam, da napišete nekateri psevdokoda pred potopom palcev In smo šli čez psevdokoda kot skupina. In potem, ko sem napisal svoj psevdokoda, in ko smo napisal naš psevdokoda kot skupina, lahko gredo v to kodiranje v C. 

Kot heads up, funkcija insert_node je verjetno najzahtevnejše od trije bomo pisati, ker sem dodali nekaj dodatnih omejitev za programiranje, zlasti ne boš šel, da vstavite katerokoli dvojnikov in da seznam mora ostati razvrščeni. Torej je to nepomembno programa da morate kodo. In zakaj ne vzameš 06:55 minut, samo da se dela na psevdokoda in kodo. In potem bomo začeli bo kot skupina. Še enkrat, če imate vprašanja, preprosto dvignite roko in pridem okoli. . 

Prav tako na splošno se ti - ali pa sem izrecno ne rečeš Lahko delo z ljudmi. Ampak očitno sem zelo Spodbujam vas, Če imate vprašanja, da se vprašajte sosed sedi poleg vas ali celo delati z nekom drugje, če želite. To ni nujno, da je posameznik tiha dejavnost. 

Začnimo s pisanjem nekaterih psevdokoda na krovu. Kdo mi lahko pove prvo vrstico psevdokoda za ta program? Za to funkcijo, ne - insert_node. Alden? 

PUBLIKA: Torej prva stvar, ki sem je bil ustvariti nov kazalec na vozlišče in I inicializirana to kaže na isti stvar, ki je seznam kaže, da. 

JASON Hirschorn: OK. Torej ste ustvarili nov kazalec na seznamu ni na vozlišče. 

PUBLIKA: Right. Ja. 

JASON Hirschorn: OK. In potem kaj želimo narediti? Kaj je potem to? Kaj pa vozlišče? Nimamo vozlišče. Pravkar smo imeli vrednosti. Če želimo vstaviti vozlišče, kaj počnemo morate storiti, preden bomo lahko celo pomisli, da ga vstavimo? 

PUBLIKA: Oh, oprostite. moramo malloc prostor za vozlišče. 

JASON Hirschorn: Odlično. Naredimo - OK. Ne morejo doseči tako visoko. OK. Mi smo šli dol, nato pa smo z uporabo dveh stolpcev. Ne morem iti, da - OK. Ustvari novo vozlišče. Lahko ustvarite nov kazalec na seznam ali pa samo uporabite seznam, kot ga poznamo. Ne boste res morali storiti, da. 

Tako smo ustvarili novo vozlišče. Super. To je tisto, kar počnemo prvič. Kaj je naslednje? 

PUBLIKA: Počakajte. Moramo ustvariti novo vozlišče zdaj ali bi morali čakati, da se prepričajte, da ni nobenih dvojnikov vozlišča na seznamu, preden smo ga ustvarili? 

JASON Hirschorn: Dobro vprašanje. Oglejmo držite za kasneje, ker Večino časa bomo lahko ustvarjate novo vozlišče. Zato bomo še naprej, da je tu. Ampak to je dobro vprašanje. Če smo ga ustvarili in smo ugotovili, Dvojnik, na kaj mora biti storimo pred vrnitvijo? 

PUBLIKA: je prost. 

JASON Hirschorn: Ja. Verjetno ga osvobodi. OK. Kaj naj naredimo, ko smo ustvarite novo vozlišče? Annie? 

PUBLIKA: Mi dana Številka v vozlišču? 

JASON Hirschorn: Točno tako. Mi je dal številko - smo malloc prostor. Bom pustil, da vsi kot eno vrstico. Ampak imaš prav. Malloc smo prostor, nato pa smo dal številko noter Mi lahko celo nastavite kazalec del pa na null. Točno tako. In potem, kaj pa potem? Mi narisal to sliko na krovu. Torej, kaj naj naredimo? 

PUBLIKA: Mi gremo po seznamu. 

JASON Hirschorn: Pojdi po seznamu. OK. In kaj smo preveriti pri vsakem vozlišču. Kurt, kaj bomo preveri za na vsakem vozlišču? 

PUBLIKA: Glejte, ali vrednost n od da vozlišče je večja od vrednosti n našega vozlišča. 

JASON Hirschorn: OK. Jaz bom naredil - Ja, v redu. Torej je n - Jaz bom rekel, če je vrednost večja od tega vozlišča, potem kaj naj naredimo? 

PUBLIKA: No, potem pa vstavite stvar tik pred tem. 

JASON Hirschorn: OK. Torej, če je večji od tega, potem želimo vstaviti. Vendar želimo, da jo vstavite tik pred ker smo tako bi morali biti sledenja, potem pa, kaj je bilo prej. Torej vstavite prej. Tako smo verjetno zamudili nekaj prej. Verjetno moramo biti ohranjanje tir, kaj se dogaja. Ampak bomo dobili nazaj. Torej, kaj vrednost je manjša od? Kurt, kaj bomo storili, če vrednost je manjša od? 

PUBLIKA: Potem si nadaljuj razen če je to zadnja. 

JASON Hirschorn: mi je všeč. Torej pojdi na naslednje vozlišče. Razen če je to zadnja - bomo verjetno preverjanje, da v smislu pogoja. Ampak ja, naslednje vozlišče. In to je že preveč nizka, tako da bomo premakniti tukaj. Ampak, če - lahko vsi videli to? Če smo enaki, kaj naj naredimo? Če je vrednost poskušamo vstaviti je enaka vrednosti tega vozlišča? Ja? 

PUBLIKA: [neslišno]. 

JASON Hirschorn: Ja. Glede na to - Marcus je prav. Lahko bi morda naredil nekaj drugačnega. Toda glede na to, da smo jo ustvarili, tukaj moramo osvoboditi in se nato vrne. Oh fant. Je zdaj bolje? Kako je s tem? OK. Brezplačno in potem, kaj počnemo vrne, [neslišno]? OK. Nam manjka ničesar? Torej, kje smo sledenja od predhodnega vozlišča? 

PUBLIKA: Mislim, da bi šel Po ustvariti novo vozlišče. 

JASON Hirschorn: OK. Torej, na začetku se bomo verjetno - ja, lahko ustvarimo kazalec na novo vozlišče, kot prejšnje vozlišče kazalca in trenutni kazalec vozlišče. Torej, kaj je, da vstavite tukaj. Ustvarite sedanje in prejšnje kazalci na vozliščih. Toda, ko bomo prilagodili te kazalce? Kje naj naredimo, da v kodi? Jeff? 

PUBLIKA: - razmere vrednost? 

JASON Hirschorn: Kateri eden zlasti? 

PUBLIKA: Jaz sem samo zmeden. Če je vrednost večja od tega vozlišča to ne pomeni, da si želijo, da gredo na naslednje vozlišče? 

JASON Hirschhorna: Torej, če je naš vrednost večja od vrednosti tega vozlišča. 

OBČINSTVO: Ja, potem bi želeli iti naprej po vrsti, kajne? 

JASON Hirschhorna: Right. Torej, ne bomo ga vstavite tukaj. Če je vrednost nižja od tem vozlišču, nato pa gremo na naslednje vozlišče - ali pa smo vstaviti prej. 

PUBLIKA: Čakaj, ki je to vozlišče in ki je vrednost? 

JASON Hirschhorna: Dobro vprašanje. Vrednost po tej definiciji funkcije je tisto, kar si mi dal. Torej vrednost je število smo dati. Torej, če je vrednost manj kot to vozlišče, potrebujemo čas, da vstavite. Če je vrednost večja od tega vozlišča gremo na naslednje vozlišče. In nazaj na prvotno vprašanje, čeprav, če - 

PUBLIKA: Če je vrednost večja od tega vozlišča. 

JASON Hirschhorna: In tako Kaj delamo tukaj? Sladko. Da je pravilna. Jaz bom samo pisati posodabljanje kazalcev. Ampak ja, s sedanjim bi jo posodobili, da opozarjajo na naslednjega. Še kaj nam manjka? Tako da bom ta tip kodo v gedit. In ko sem to naredil, lahko imate nekaj minut, da delajo na kodiranje To v C. 

Torej imam vhoda psevdokoda. Quick note, preden začnemo. Morda ne bomo mogli v celoti dokončati to v vseh tri od teh funkcij. Obstaja pravilni rešitve zanje da bom po e-pošti, da vas fantje Po oddelku, in da bo objavljene na CS50.net. Torej, jaz ne spodbujajo k iti pogled na oddelkih. Spodbujam vas, da poskusite to na vašem lastnik, in nato uporabite prakso Težave, da preverite svoje odgovore. Vse te spremembe so zasnovane za tesno nanašajo in se držati kaj kar morate storiti na problem nizu. Tako da mi vas spodbujamo, da prakticirali na svoje in nato uporabite kodo preverite svoje odgovore. Ker pa bi rad, da se premaknete na hash mize na neki točki v oddelku. Torej, morda ne bomo dobili skozi vse to. Vendar bomo storili, kolikor smo lahko zdaj. 

OK. Začnimo. Asam, kako ustvariti novo vozlišče? 

PUBLIKA: Vam struct *. 

JASON Hirschhorna: Tako smo imajo, da tu gor. Oh, oprostite. Pravite, da je zgradimo *. 

PUBLIKA: In potem [? vrste?] vozlišče ali c vozlišče. 

JASON Hirschhorna: OK. Jaz ga bom poklical new_node tako da bomo lahko ostali dosledni. 

PUBLIKA: In želite nastaviti, da na glavo, prvo vozlišče. 

JASON Hirschhorna: OK. Torej, zdaj je to kaže na - zato je to še ni ustvaril novo vozlišče. To je samo kaže na prvo vozlišče v seznamu. Kako ustvariti novo vozlišče? Če rabim prostor za ustvarjanje novega vozlišča. Malloc. In kako velik? 

PUBLIKA: velikost struct. 

JASON Hirschhorna: velikost struct. In kaj struct imenuje? 

PUBLIKA: Node? 

JASON Hirschhorna: Node. Torej malloc (sizeof (vozlišče)); nam daje prostor. In je ta linija - ena stvar je napačna v tej vrstici. Je new_node kazalec na struct? To je generično ime. Kaj je to - vozlišče, točno. To je vozlišče *. In kaj bomo storili takoj po smo malloc nekaj, Asan? Kaj je prva stvar, bomo naredili? Kaj pa, če to ne deluje? 

PUBLIKA: Oh, preverite, če je opozarja na vozlišče? 

JASON Hirschhorna: Točno tako. Torej, če ste new_node enaka enaka null, kaj naj naredimo? To vrne bool, to funkcijo. Točno tako. Izgleda dobro. Kaj bi tam dodati? Mi bomo dodali stvari na koncu. Ampak, da do sedaj izgleda dobro. Ustvarite sedanje in prejšnje napotke. Michael, kako naj to naredim? 

PUBLIKA: Vi bi morali narediti vozlišče *. To bi morali narediti eno ne za new_node ampak za vozlišča že imamo. 

JASON Hirschhorna: OK. Torej trenutni vozel sva naprej. Poklical bom to Valuta. Vse je v redu. Odločili smo želeli obdržati dva, ker moramo vedeti kaj je pred njim. Kaj so dobili inicializirana na? 

PUBLIKA: Njihova vrednost v našem seznamu. 

JASON Hirschhorna: Torej, kaj je Prva stvar, na našem seznamu? Ali pa, kako bomo vedeli, kje začetek našem seznamu je? 

PUBLIKA: Ali ni opravil v funkciji? 

JASON Hirschhorna: Right. Sprejet je bil leta tukaj. Torej, če je to prešlo v funkciji, začetek seznama, kaj bi morali aktualnega enak? 

PUBLIKA: Seznam. 

JASON Hirschhorna: Seznam. Točno tako. Sedaj ima naslov začetek našega seznama. In kaj je prejšnja? 

PUBLIKA: Seznam minus ena? 

JASON Hirschhorna: Obstaja nič pred njim. Torej, kaj lahko storimo, da bi pomenilo nič? 

PUBLIKA: Null. 

JASON Hirschhorna: Ja. To se sliši kot dobra ideja. Popolna. Hvala vam. Pojdi po seznamu. Constantine, kako dolgo bomo iti skozi seznam? 

PUBLIKA: dokler ne bomo dosegli nič. 

JASON Hirschhorna: OK. Torej, če je, medtem ko je za zanke. Kaj počnemo? 

PUBLIKA: Morda za zanko? 

JASON Hirschhorna: Naredimo zanko. OK. 

PUBLIKA: In smo rekli za - Do konca tekočega kazalca ni enaka null. 

JASON Hirschhorna: Torej, če vemo, Pogoj, kako lahko pišemo zanko temelji off tega pogoja. Kakšno zanke moramo uporabiti? 

PUBLIKA: Med. 

JASON Hirschhorna: Ja. Da je bolj smiselno, ki temelji off, kaj si rekel. Če želimo le, da gredo v smo, da bo samo vem, da je stvar, bi bilo občutek, da to while zanko. Medtem ko je trenutni ni enaka nič, če je vrednost manj kot to vozlišče. Akshar, daj mi to linijo. 

PUBLIKA: Če trenutni-> n n manjša od vrednosti. Ali obratno, da. Switch to konzolo. 

JASON Hirschhorna: Žal mi je. 

PUBLIKA: Spremenite nosilec. 

JASON Hirschhorna: Torej, če je to večja od vrednosti. Ker to je zmedeno z komentar zgoraj, bom to storil. Ampak ja. Če je naša vrednost manj kot to vozlišče, kaj naj naredimo? Oh. Ga imam tukaj. Vstavite prej. OK. Kako bomo to storili? 

PUBLIKA: Je to še vedno jaz? 

JASON Hirschhorna: Ja. 

PUBLIKA: You - new_node-> naslednji. 

JASON Hirschhorna: Torej, kaj je da bo enako? 

PUBLIKA: To se dogaja, do enakega toka. 

JASON Hirschhorna: Točno tako. In tako drugi - kaj pa moramo posodobiti? 

PUBLIKA: Preverite, če mimo enaka null. 

JASON Hirschhorna: Če je prejšnja - tako da, če prej enaka null. 

PUBLIKA: To pomeni, da se dogaja da postane vodja. 

JASON Hirschhorna: To pomeni to je postal vodja. Torej, kaj naj naredimo? 

PUBLIKA: Mi glavo enaka new_node. 

JASON Hirschhorna: Head enaka new_node. In zakaj glavo tukaj, ne seznam? 

PUBLIKA: Ker je vodja globalne spremenljivka, katere izhodiščni kraj. 

JASON Hirschhorna: Sweet. OK. In - 

PUBLIKA: Potem ti drugega prejšnja-> Naslednja enaka new_node. In potem vrne true. 

JASON Hirschhorna: Kam smo postavili konec new_node? 

PUBLIKA: Jaz bi - Sem jih, da na začetku. 

JASON Hirschhorna: Torej, kaj je meja? 

PUBLIKA: Po if stavek preverjanje, če je to znano. 

JASON Hirschhorna: Tukaj? 

PUBLIKA: Jaz bi naredil new_node-> n enako vrednost. 

JASON Hirschhorna: Sliši se dobro. Verjetno je smiselno - ne bomo morate vedeti, kaj seznam smo na ker smo edini, ki se ukvarjajo z eno listo. Torej bolje izjava funkcija to je samo, da se znebite tega v celoti in samo vstavite vrednost v glavo. Mi sploh ne potrebujete vedeti Kaj Seznam notri smo Ampak bom ga hranite za zdaj in nato pa ga spremenite po posodobitvi diapozitive in kodo. Tako da izgleda dobro za zdaj. Če je vrednost - kdo lahko to linijo? Če - Kaj delamo tukaj, Noah. 

PUBLIKA: Če je vrednost večja kot Curr-> n - 

JASON Hirschhorna: Kako gremo na naslednje vozlišče? 

PUBLIKA: Valuta-> n enako new_node. 

JASON Hirschhorna: Tako je n kateri del struct? Celo število. In new_node je kazalec na vozlišče. Torej, kaj del curr bi morali posodobiti? Če ne n, potem kaj je na drugi strani? Noah, kaj je na drugi strani. 

PUBLIKA: Oh, naslednji. 

JASON Hirschhorna: Naprej, točno. Točno tako. Naslednja je pravi. In kaj še potrebujemo posodobiti, Noah? 

PUBLIKA: Kazalci. 

JASON Hirschhorna: Do smo posodobili tok. 

PUBLIKA: Nazaj-> naslednji. 

JASON Hirschhorna: Ja. OK, bomo premor. Kdo nam lahko pomagal? Manu, kaj naj storimo? 

PUBLIKA: Moraš nastaviti je enaka curr-> naslednji. Vendar pa, da je pred prejšnjo vrstico. 

JASON Hirschhorna: OK. Kaj drugega? Akshar. 

PUBLIKA: Ne verjamem, da si pomenilo, da spremenite Valuta-> next. Mislim, da si hotel storiti Valuta enaka curr-> zraven, da gredo na naslednje vozlišče. 

JASON Hirschhorna: Žal mi je, kje? O tem, kaj linija? Ta linija? 

OBČINSTVO: Ja. Naredite curr enaka curr-> naslednji. 

JASON Hirschhorna: Tako da je pravilna ker tok kazalec na vozlišče. In želimo, da kaže na naslednji vozlišče, kaj je že sedaj je poudaril, da. Valuta je sam zraven. Ampak, če smo bili posodobiti curr.next smo bi bilo treba posodobiti dejansko seznanil sama po sebi, ne tam, kjer je to kazalec je obrnjena. Kaj pa te vrstice, čeprav. Avi? 

PUBLIKA: Nazaj-> naslednji enaka Valuta. 

JASON Hirschhorna: Torej še enkrat, če je prejšnja kazalec na vozlišče, prev-> dostavo je dejanska kazalec v vozlišču. Torej, to bi bilo posodabljanje kazalec na vozlišče curr. Mi ne želimo posodobiti kazalec na vozlišče. Želimo posodobiti prejšnje. Torej, kako bomo to storili? 

PUBLIKA: To bi bilo šele prejšnja. 

JASON Hirschhorna: Right. Predhodni je kazalec na vozlišče. Zdaj smo jo spremeniti Novi kazalec na vozlišče. OK, gremo naprej navzdol. Končno, ta zadnji pogoj. Jeff, kaj delamo tukaj? 

PUBLIKA: Če je vrednost enak Curr-> n. 

JASON Hirschhorna: Žal mi je. Oh moj bog. Kaj? Vrednost == curr-> n. Kaj naj naredimo? 

PUBLIKA: Bi osvoboditi našo new_node, in potem boš vrne false. 

JASON Hirschhorna: To je tisto, ki smo jih doslej napisal. Ima kdo kaj dodati, preden naredimo? OK. Poskusimo. Nadzor lahko pridete do konca ne-nična funkcijo. Avi, kaj se dogaja? 

PUBLIKA: Ali bi moral dati vrnitev drži zunaj, medtem ko zanke? 

JASON Hirschhorna: Ne vem. Me želiš? 

PUBLIKA: Pozabi. Ne 

JASON Hirschhorna: Akshar? 

PUBLIKA: Mislim, da si mislil, da mu vrne false konec while zanke. 

JASON Hirschhorna: Torej, če želiš, da bi šel? 

PUBLIKA: Kot izven while zanko. Torej, če zaprete while zanko, kar pomeni, da da ste prišli do konca in se ni nič zgodilo. 

JASON Hirschhorna: OK. Torej, kaj bomo storili tukaj? 

PUBLIKA: Vrnete false tudi tam. 

JASON Hirschhorna: Oh, smo to storiti v obeh mestih? 

OBČINSTVO: Ja. 

JASON Hirschhorna: OK. Naj gremo? Oh moj bog. Žal mi je. Se opravičujem za zaslon. To je neke vrste nori na nas. Tako da izberete možnost. Nič, na oznako, zapre program. Ena vstavi nekaj. Oglejmo vstavite tri. Vložek ni bil uspešen. Grem natisniti. Jaz nimam ničesar. OK. Mogoče, da je bil samo krompir. Vstavite eno. Ni uspešen. OK. Oglejmo teči skozi GDB res hitro da preverite, kaj se dogaja. 

Zapomni si gdb. / Ime vašega Program nam pride v GDB. Je, da je veliko ravnati? Utripa? Verjetno. Zaprite oči in si nekaj globoko diha, če se naveličaš gledaš na to. Jaz sem v GDB. Kaj je prva stvar, ki mi v GDB? Moramo ugotoviti, kaj se dogaja tukaj. Pa poglejmo. Imamo šest minut, da ugotovimo izvedeti, kaj se dogaja. Glavni odmor. In potem, kaj naj storim? Carlos? Teči. OK. Oglejmo izberite možnost. In kaj N storiti? Naprej. Ja. 

PUBLIKA: Ali nisi omenil - nisi rekel, da je bil vodja inicializirana na ničlo na začetku. Vendar sem mislil, da si rekel, da je bilo v redu. 

JASON Hirschhorna: Pojdimo - oglejmo v GDB in potem gremo nazaj. Ampak to zveni kot ste že nekaj idej o tem, kaj se dogaja. Zato želimo vstaviti nekaj. OK. Imamo vstaviti. Vnesite int. Bomo vstaviti tri. In potem sem na tej progi. Kako naj grem začnete razhroščevanje vložek znano funkcijo? Oh moj bog. To je veliko. Je, da je vsa iz sebe veliko? 

PUBLIKA: Oh, to je umrl. 

JASON Hirschhorna: Pravkar sem ga potegnil ven. OK. 

PUBLIKA: Mogoče je drugi konec žice. 

JASON Hirschhorna: Wow. Torej bottom line - Kaj si rekel? 

PUBLIKA: Rekel sem ironija tehnične Težave v tem razredu. 

JASON Hirschhorna: Vem. Če bi le imel nadzor nad tem delom. [Neslišno] Sliši se odlično. Zakaj ne bi vi začeli razmišljati o kaj bi lahko naredil narobe, in se vrnemo v 90 sekundah. 

Avica, jaz te bom vprašal, kako iti znotraj insert_node jo debug. Torej, to je, če smo nazadnje končali. Kako naj grem noter insert_node, Avica, preučiti, kaj se dogaja? Kaj ukaz GDB? Break me ne bi notri. Ali Marquise vedeli? 

PUBLIKA: Kaj? 

JASON Hirschhorna: Kaj ukaz GDB Uporabljam noter to funkcijo? 

PUBLIKA: Step? 

JASON Hirschhorna: Korak preko S. To me popelje v notranjosti. OK. New_node mallocing nekaj prostora. Da vse izgleda kot njegova dogaja. Oglejmo new_node. To imam nekaj pomnilniški naslov. Poglejmo - da je vse pravilno. Torej, vse, kar sem se zdi, da deluje pravilno. 

PUBLIKA: Kakšna je razlika med P in zaslonom? 

JASON Hirschhorna: P stoji za tisk. In tako se sprašuješ, kaj je Razlika med to in to? V tem primeru nič. Ampak na splošno obstajajo nekatere razlike. In bi morali iskati v priročniku gdb. Toda v tem primeru nič. Smo nagnjeni k uporabi tisk, čeprav, saj nam ni treba storiti veliko več, kot natisniti eno vrednost. 

OK. Tako da smo na liniji 80 našega kodeksa, nastavitev vozlišča * Valuta enak seznam. Dovolite nam natisnite Valuta. To je enak seznam. Sladko. Čakati. To je enako nekaj. To se ne zdi prav. Takole. To je zato, ker v GDB, desno, če to je črta, da si na njem še ni izvršena. Torej boste morali dejansko tip Naslednja izvršiti linijo Pred videli rezultate. Torej, tukaj smo. Pravkar smo izvedli te vrstice, Predhodna enaka null. Torej, še enkrat, če tiskamo prejšnja ne bomo videli nič čudnega. Ampak, če smo dejansko izvršiti, da linijo, potem pa bomo videli da je ta linija delal. 

Torej imamo Valuta. Tisti, ki so tako dobri. Kajne? Zdaj smo na tej progi tukaj. Medtem ko curr ni enaka null. No, kaj počne curr enaka? Pravkar smo videli, je znašal null. Ga natisne bomo ven. Jaz ga bom še enkrat natisniti. Tako je, da medtem ko zanke gre za usmrtitev? 

PUBLIKA: Ne 

JASON Hirschhorna: Torej, ko sem tipkal, da linijo, boste videli smo skočili vso pot na dno, vrne false. In potem se bomo vrnili false in iti nazaj v naš program in sčasoma natisniti, kot smo videli, vložek ni bila uspešna. Torej, kdo kakšne ideje o tem, kaj moramo storiti, da popraviti to? Bom počakati, dokler ne vidim Nekaj ​​roke gredo gor. Nismo izvršiti to. Imejte v mislih, da je to prvi kar smo počeli. Ne bom narediti nekaj. Jaz bom naredil nekaj. Ker nekaj pomeni dva. Počakal bom za več kot dva. 

Prvi vstavljanje, Curr, Privzeto je enaka nič. In to zanko izvede le če curr ni nič. Torej, kako lahko dobim okoli tega? Vidim tri roke. Počakal bom za več kot tri mesece. Marcus, kaj misliš? 

PUBLIKA: No, če ga potrebujete, da izvesti več kot enkrat, ki ste jo pravkar spremenite v do-while zanko. 

JASON Hirschhorna: OK. Bo to rešili naš problem, čeprav? 

PUBLIKA: V tem primeru ni potrebna, ker Dejstvo, da je seznam prazen. Torej potem verjetno samo morali dodati izjava, da če se zanka izhodi potem boste morali biti na koncu Seznam, na kateri točki ste Lahko samo vstavite. 

JASON Hirschhorna: mi je všeč. To je smiselno. Če zanka izstopi - saj bom vrnil false tukaj. Torej, če zanke izhodov, nato pa smo v konec seznama, ali morda začetek seznama, če ni ničesar v to, kar je enako koncu. Torej, zdaj želimo vstaviti Nekaj ​​tukaj. Torej, kako to kodo videti, Marcus? 

PUBLIKA: Če že imaš vozlišče malloced, bi lahko rekli, new_node-> naslednji enaka null, ker da mora biti na koncu. Ali new_node-> naslednji enaka null. 

JASON Hirschhorna: OK. Žal mi je. New_node-> naslednji enaka null zato, ker smo na koncu. Da ne ga dal noter Kako bomo to dal na seznamu? Prav. To je samo nastavitev enaka. No, kako bomo dejansko ga na seznamu? Kaj je poudaril, da Konec seznamu? 

PUBLIKA: Head. 

JASON Hirschhorna: Oprostite? 

PUBLIKA: vodja kaže na koncu seznama. 

JASON Hirschhorna: Če ni nič v Seznam, glava kaže na konec seznama. Tako, da bo delo za prve vstavitve. Kaj če obstaja nekaj stvari na seznamu? Kot da ne želimo, da nastavite glavo enako new_node. Kaj želimo, da tam narediti? Ja? Verjetno prejšnje. Bo to delovalo? Spomnimo se, da je prejšnja le kazalec na vozlišče. In prejšnje je lokalna spremenljivka. Tako da bo ta vrstica nastaviti lokalno spremenljivko, Prejšnja enake ali kar kaže na to novo vozlišče. Da dejansko ne bo dal v našem seznamu, čeprav. Kako bomo to dal v našem seznamu? Akchar? 

PUBLIKA: ti misliš naredite sedanjega-> next. 

JASON Hirschhorna: OK. curr-> naslednji. Torej še enkrat, edini razlog, da smo dol Tukaj je, kaj počne sedanja enaka? 

PUBLIKA: Enako null. 

JASON Hirschhorna: Pa kaj se zgodi, če naredimo null-> naslednji? Kaj bomo dobili? Bomo dobili napako segmentacije. 

PUBLIKA: Do Valuta enaka null. 

JASON Hirschhorna: To je ista stvar kot predogled, čeprav zato, ker je lokalna spremenljivka smo nastavitev enako tega novega vozlišča. Vrnimo se k naši sliki vstavljanje nekaj. Pravijo, da smo vstavljanje na koncu seznama, tako da tukaj. Imamo trenutni kazalec, ki je kaže na nič in s prejšnjo točko , ki je poudaril, da je 8.. Torej, kaj moramo posodobiti, Avi? 

PUBLIKA: Prejšnja-> naslednji? 

JASON Hirschhorna: Nazaj-> naslednji je tisto, želimo posodobiti, ker to bo dejansko jo vstavite v konec seznama. Še vedno imamo eno napako, čeprav, da bomo zašli v. Kaj je to bug? Ja? 

PUBLIKA: To se dogaja, da se vrnete false v tem primeru? 

JASON Hirschhorna: Oh, se je vrača false. Toda obstaja še en bug. Torej bomo morali dati v zameno resnične. 

PUBLIKA: Ali je prejšnja vedno enaka nično na vrhu seznama? 

JASON Hirschhorna: Torej, prejšnji vedno enaka null že na samem začetku. Torej, kako lahko pridemo čez to? Ja? 

PUBLIKA: Mislim, da lahko narediš pregled pred zanko, medtem ko bi videli, če je Prazen seznam. 

JASON Hirschhorna: OK. Torej, gremo tukaj. Ali ček. Če - 

PUBLIKA: Torej, če glava enaka enaka null. 

JASON Hirschhorna: Če je glava enaka enaka null - ki nam bo povedal, če je prazen list. 

PUBLIKA: In potem si storiti glava enako novo. 

JASON Hirschhorna: Head enaka new_node? In kaj bomo morali narediti? 

PUBLIKA: In potem vrne true. 

JASON Hirschhorna: Ne čisto. Nam manjka en korak. 

PUBLIKA: new_node Naslednja je opozoriti na null. 

JASON Hirschhorna: Točno tako, Alden. In potem se lahko vrnemo true. OK. Ampak to je vedno dobra ideja, da počnejo stvari na koncu seznama, prav? Vse je v redu. Še vedno lahko dejansko dobili na koncu seznama. Torej je ta koda v redu, če sva že pri na koncu seznama in obstaja nekaj stvari na seznamu? Kajne? Ker imamo vedno Marcusov ideja. Mi lahko izhod iz te zanke, ker smo na koncu seznama. Torej smo še vedno želijo to kodo tukaj? 

PUBLIKA: Da. 

JASON Hirschhorna: Ja. In kaj bomo morali spremeniti, da? Res je. Ali to zveni dobro vsem tako daleč? Ima kdo sploh - Avi, imaš kaj za dodati? 

PUBLIKA: Ne 

JASON Hirschhorna: OK. Tako smo naredili nekaj sprememb. Naredili smo to preverjanje, preden smo šel za prazen seznam. Tako smo poskrbeli za praznim seznamom. In tukaj smo poskrbeli za vstavljanje Nekaj ​​na koncu seznama. Tako se zdi, kot te, medtem ko zanke pridobivanju Skrb stvari vmes, nekje na seznamu, če So stvari na seznamu. 

OK. Dovolite nam, znova zaženite program. Ni uspešen. 

PUBLIKA: Saj ni uspelo. 

JASON Hirschhorna: Oh, Mi ni uspelo. Dobra točka, Michael. Dodajmo make povezano. Linija 87 pa je napaka. Line 87. Alden je bil ta linija si mi jo dal. Kaj je narobe? 

PUBLIKA: Mora biti na null. 

JASON Hirschhorna: Odlično. Točno tako. To bi morala biti nična. Naj bo še enkrat. Prevesti. OK. Oglejmo vstavite tri. Vložek je uspela. Dajmo ga natisnite. Oh, če bi le lahko preveri. Vendar nismo storili Še funkcijo tiskanja. Oglejmo vnesti nekaj drugega. Kaj moramo vstopiti? 

PUBLIKA: Seven. 

JASON Hirschhorna: Sedem? 

PUBLIKA: Da. 

JASON Hirschhorna: Imamo napako SEG. Torej imamo eno, vendar smo jasno se ne more znebiti dva. To je 5:07. Torej bi to lahko debug tri minute. Ampak bom pustite nas tukaj in se premakniti na hash tabel. Ampak še enkrat, odgovori za to kodo Sem jo bomo e-pošto na vas v nekaj. Mi smo zelo blizu nje. Zelo sem Spodbujam vas, da ugotovimo, kaj se dogaja tukaj in popraviti. Zato ti bom pošlji kodo, kot je tudi plus raztopina - Verjetno raztopina kasneje. Prvi je ta številka. 

Druga stvar, želim storiti, preden bomo Zaključek je nismo osvobodili ničesar. Zato bi rad, da ti pokažem, kaj valgrind izgleda. Če bomo teči meje valgrind na našem programu. / povezani. Spet po tem diapozitiv smo Trajala naj bi valgrind z neko vrsto Možnost, v tem primeru - Puščanja check = polna. Torej, kaj je pisanje valgrind - Puščanja check = polna. Tako da bo to delovalo valgrind na našem programu. In zdaj program dejansko deluje. Torej bomo teči, tako kot prej, dal nekaj noter Bom dal v treh. To deluje. Jaz ne bom poskusil postaviti v nekaj sicer zato, ker bomo dobili SEG FALSE v tem primeru. Tako da sem le, da bo nehal. 

In zdaj vidite tukaj puščati in kopice povzetek. To so dobre stvari, ki jih želite odjaviti. Torej kup povzetek - pravi, v uporabi na izhodu - osem bajtov v enem bloku. Da en blok vozlišče smo malloced. Michael, rekel si pred vozlišče je osem ugrizi, ker ima celo število in kazalec. Tako, da je naša vozlišče. In potem pravi, da uporablja malloc sedemkrat in smo osvobojeni kar šestkrat. Ampak mi nikoli ne imenujemo svobodni, tako da nimam Ideja, kaj je to govoril. 

Ampak zadostuje, da pravijo, da če vaš Zažene se program, malloc se imenuje v nekaterih drugih krajih, ki smo vam ni treba skrbeti. Torej je malloc Verjetno se imenuje v nekaterih mestih. Nam ni treba skrbeti, kje. Ampak to je res midva. To je prva linija nas. Smo pustili, da je blok. In lahko vidite, da tu v povzetku uhajanja. Še vedno dosegljiv - osem bajtov v enem bloku. To pomeni, da je spomin - smo ušli, da je spomin. Dokončno izgubil - nekaj, kar se je izgubil za vedno. Na splošno, ne boste vidim ničesar tam. Še vedno dosegljiva na splošno, kjer boste videli stvari, kjer si boste želeli videti, da vidim, kaj kode bi smeli so se osvobodili, vendar si pozabil, da osvobodi. 

In potem, če to ni bilo tako, če smo storili vse, kar je brezplačno, lahko preverimo, da je. Reciva, zaženite program ne daje v nič. Boste videli tukaj v uporabi na izhodu - nič bajtov ničlo blokov. To pomeni, da bomo imeli ničesar več ko ta program izstopilo. Torej, preden se obrača v pset6, teči valgrind in poskrbite, da ne boste imeli koli spomin razpoka v vašem programu. Če imate kakršnakoli vprašanja s valgrind, vas prosimo, da stik. Ampak to je, kako ga uporabljate. Zelo preprosta - vidim, če ste imajo v uporabi na izhodu - vse bajte v katerih koli blokih. 

Tako smo delali vstaviti vozlišču. Imel sem dve druge funkcije tukaj - tiskanje vozlišč in brezplačno vozlišč. Še enkrat, to so funkcije, ki so bo dobro za vas, da prakse saj vam bodo pomagali ne le z Te vzorčne vaje, ampak tudi na problemu nastaviti. So map na zelo pozorno stvari boste morali storiti v Problem nastavite. Ampak jaz ne želim, da poskrbite, da bomo dotaknili vsega. In hash tabele so ključnega pomena tudi za kaj delamo v tem oddelku teden - ali problemskega nizu. 

Tako da bomo do konca odseka Govorimo o hash tabel. Če opazite, da je malo hash tabelo. To ni tisto, kar govorimo O, pa je. Govorimo o drugačni Vrsta razpršene tabele. In v svojem jedru, a razpršene tabele ni nič več kot Niz plus hash funkcijo. Bomo govorili za bit, samo da bi poskrbite, da vsakdo razume, kaj hash funkcija. In povem ti zdaj, da je nič več kot dveh stvari - matrika in hash funkcijo. In tukaj so koraki preko ki jih ta upravlja. 

Tam je naša niz. Tam je naša funkcija. Zlasti, zgoščevalne funkcije morali naredite nekaj stvari s tem. Bom posebej govoriti O tem problem nastaviti. To je verjetno, da bo sprejmejo v nizu. In kaj bo, da se vrnete? Kaj podatkovni tip? Alden? Vaš hash funkcija vrne? Število. Torej je to tisto, kar hash Tabela sestavljajo - miza v obliki matrike in hash funkcijo. Kako deluje? Deluje v treh korakih. Damo ključ. V tem primeru bomo ji dati niz. Pravimo funkcijo razpršitve na koraku na ključ in smo dobili vrednost. 

Natančneje, bomo rekli, smo dobili celo število. To število je zelo specifična omejitve glede tega, kaj je mogoče, da je celo lahko. V tem primeru je naša matrika z velikostjo tri. Torej, kaj številke lahko celo, da bo. Kakšen je obseg veljavnih vrednosti za da celo število, tip vrnitev tega hash funkcijo? Nič, ena in dve. Bistvo funkcije razpršitve je ugotovimo mesto v matriki kjer je naš ključni se dogaja. Obstajajo mogoče le trije kraji tukaj - nič, ena ali dve. Tako da je ta funkcija bolje vrnitev nič, ena ali dve. Nekateri velja Indice v tem polju. 

Nato pa odvisno od tega, kje se vrne, lahko vidite, obstaja niz odprta oklepati vrednost. To je, če smo dal ključ. Torej vržemo v buče, pridemo ven nič. Na diod nosilec 0, postavimo buče. Vržemo pri mačkah, smo dobili eno. Mi je dal mačko v enem. Damo v pajka. Pridemo ven dva. Mi je dal pajka na matrični nosilec dveh. Bilo bi lepo, če je delal tako. Ampak, žal, kot bomo videli, to je malo bolj zapletena. 

Preden smo prišli tja, na vsa vprašanja O tem osnovno set-up za razpršene tabele? To je slika ravno kaj smo narisal na krovu. Ampak, ker smo ga narisal na tablo, sem Ne bom se spuščal v to še naprej. V bistvu ključi, magic black box - ali v tem primeru, teal box - od hash funkcija jih postavlja v vedrih. In v tem primeru smo ne daje ime. Mi smo dajanje povezan telefon Število imena v vedro. Vendar pa bi bilo zelo dobro le dal ime v vedro. 

To je samo slika, kaj smo pripravili na krovu. Imamo potencialne pasti, čeprav. In tam sta dva zlasti drsi, da želim iti čez. Prvi je približno hash funkcijo. Zato sem vprašal, kaj naredi dober funkcijo razpršitve? Dam dva odgovora. Prvi je, da je deterministična. V okviru zgostitvene funkcije, kaj to pomeni? Ja? 

PUBLIKA: To lahko najdete Indeks v enakem času? 

JASON Hirschhorna: That ne, kaj to pomeni. Ampak to je dobro ugibanje. Ima še kdo drug ugibati kaj to pomeni? Da je dober hash funkcijo je deterministična? Annie? 

PUBLIKA: To se lahko preslika samo ključ na enem mestu v razpršene tabele. 

JASON Hirschhorna: To je Točno tako. Vsakič, ko si dal v bučo, se vedno vrne nič. Če si dal v bučo in vaše hash Funkcija vrne nič, ampak ima verjetnost, da se vračajo nekaj še večja od nič - tako da morda lahko vrne eno včasih ali dve drugi časi - da ni dober hash funkcijo. Ti si ravno prav. Vaš hash funkcija je treba vrniti Enako Natančen celo število, v tem primeru, na Enako natančen niz. 

Morda se vrne točno isto celo za isti besedni ne glede na kapitalizacijo. Toda v tem primeru je še vedno deterministična, ker več stvari so preslikane na isti vrednosti. To je v redu. Dokler je samo ena izhod za določenega vložka. 

OK. Druga pa je, da se vrne veljavne indeksov. Smo odraščali, da prej. Ta funkcija hash - oh boy - hash funkcija bi morala vrnitev veljavne indeksov. Tako pravijo - vrnimo se s tem primerom. Moj hash funkcija sešteva črke v besedi. To je funkcija hash. In se vrne, da število. Torej, če imam besede, to je vrača eno. In to se dogaja, da dajo tukaj. Kaj pa, če sem dal v besedi kij? To se dogaja, da se vrnete tri. Kje se bat iti? 

To ne ustreza. Vendar mora nekam iti. To je moj hash tabela po vsem, in vse, kar mora nekam iti. Torej, če je treba bat iti? Vsak misli? Ugiba? Dobri ugibanja? 

PUBLIKA: Zero. 

JASON Hirschhorna: Zakaj nič? 

PUBLIKA: Ker tri modulo trije nič? 

JASON Hirschhorna: Three modulo tri nič. To je veliko ugibati, in to je pravilno. Torej, v tem primeru bi moral verjetno šel v nič. Tako dober način, da se zagotovi, da ta hash Funkcija vrne le veljavne indeksov je ga modulu po velikosti tabele. Če ste modulu karkoli že to donose, ki jih tri, ste vedno tekoč, da bi dobili nekaj vmes nič, ena in dve. In če je ta vedno vrne sedem, in vedno modulu za tri, si vedno tekoč, da bi dobili isto stvar. 

Torej je še vedno deterministične Če modulu. Ampak da bo zagotovila, da vam nikoli dobili nekaj - neveljavna industrija. Na splošno bi bilo treba, da modulo zgodilo v vašem hash funkcijo. Torej vam ni treba skrbeti za to. Pravkar si lahko zagotovite, da to velja Indice. Vsa vprašanja o tem potencialna past? 

OK. In gremo. Naslednja potencialna past, in To je veliko. Kaj pa, če dva ključa zemljevid na isti vrednosti? Torej obstajata dva načina, da situacijo. Prva se imenuje linearna sondiranje, ki sem ne bo šel skozi. Vendar bi morali biti seznanjeni s tem, kako da deluje in kaj je to. 

Drugi pa bom šel čez ker je to tisti, ki veliko Ljudje bodo verjetno na koncu odločajo za uporabo v njihovem problem nizu. Seveda, ti ne bi bilo treba. Ampak za problem set, veliko ljudi ponavadi odločijo, da ustvarite razpršene tabele z Veriženje za izvajanje njihov slovar. Tako smo šli nad tem, kaj to pomeni ustvariti razpršene tabele z Veriženje. 

Zato sem dal v buče. Vrne nič. In sem dal buče tukaj. Potem sem dal v - kaj je še ena Halloween tematskih stvar? 

PUBLIKA: Candy. 

JASON Hirschhorna: Candy! To je eno veliko. Sem dal sladkarije in sladkarije Prav tako mi daje nič. Kaj naj storim? Vse ideje? Ker si vsi nekako vedeli kaj Veriženje je. Torej vse ideje, kaj naj naredim? Ja. 

PUBLIKA: Prenos niz dejansko razpršene tabele. 

JASON Hirschhorna: Torej bomo sestaviti dobro idejo tukaj. OK. 

PUBLIKA: Have Hashtable [Neslišno] kazalec, ki kaže na začetek seznama. In potem so buče je prva vrednost V tem povezanem seznamu in sladkarije biti druga vrednost v tem povezani seznam. 

JASON Hirschhorna: OK. Marcus, ki je bila odprta. Bom prekinil niz. Marcus je rekel ne prepisati buče. To bi bilo slabo. Ne dajaj sladkarij nekje drugje. Bomo, da jih tako na nič. Ampak bomo se ukvarjajo z jih postavi na ničlo ustvarite seznam na nič. In bomo ustvarili seznam vse, kar se preslika v nič. In najboljši način, da smo se naučili, da ustvarite Seznam, ki lahko rastejo in se skrči dinamično ni v še en niz. Torej ni multi-dimenzionalni array. Ampak, da se samo ustvariti povezani seznam. 

Torej, kaj je predlagal - Jaz bom dobil novo - je ustvariti array s kazalci, Niz kazalcev. OK. Kakšno idejo ali namig, kaj tip Od tega kazalcev bi moralo biti? Marcus? 

PUBLIKA: Kazalci za - 

JASON Hirschhorna: Ker vam je dejal povezani seznam, tako da - 

PUBLIKA: Node nasvetov? 

JASON Hirschhorna: Node kazalci. Če se stvari v naši povezan Seznam so vozlišča, nato pa mora biti vozlišče kazalca. In kaj so sprva enaka? 

PUBLIKA: Null. 

JASON Hirschhorna: Null. Torej je naša prazna stvar. Bučna vrne nič. Kaj naj naredimo? Hodi mi skozi to? Pravzaprav, Marcus me je že dal. Nekdo drug je hodil me skozi to. Kaj počnemo, ko smo - To je zelo podoben kaj smo samo delaš. Avi. 

PUBLIKA: bom ugibati. Torej, ko boste dobili sladkarije. 

JASON Hirschhorna: Ja. No, imamo buče. Naj se prvo. Imamo buče. 

PUBLIKA: OK. Bučna vrne nič. Torej si ga dal v to. Ali dejansko, si ga dal v povezanem seznamu. 

JASON Hirschhorna: Kako delamo ga v povezanem seznamu? 

PUBLIKA: Oh, dejanska sintaksa? 

JASON Hirschhorna: Samo sprehod - povedati več. Kaj naj naredimo? 

PUBLIKA: Vi samo vstavite je kot prvo vozlišče. 

JASON Hirschhorna: OK. Torej imamo vozlišča, buče. In zdaj, kako ga vstaviti? 

PUBLIKA: dodelite je s kazalcem. 

JASON Hirschhorna: Kateri kazalec? 

PUBLIKA: kazalec na ničli. 

JASON Hirschhorna: Torej, če pa to smisel? 

PUBLIKA: Za null zdaj. 

JASON Hirschhorna: No, to je obrnjena na null. Ampak jaz bom dal v buče. Torej, kje naj bi to imelo? 

PUBLIKA: Za bučno. 

JASON Hirschhorna: Za buče. Točno tako. Torej, to kaže na buče. In kje se ta kazalec V bučnem točke? Za 

PUBLIKA: Null. 

JASON Hirschhorna: Za null. Točno tako. Tako da smo samo vstavi nekaj v povezanem seznamu. Pravkar smo pisali to kodo, da to storijo. Skoraj skoraj bi ga dobili popolnoma razpokan. Zdaj smo vstavite sladkarije. Naša sladkarije gre tudi nič. Torej, kaj bomo naredili z bonboni? 

PUBLIKA: To je odvisno od tega, ali Ne trudimo, da ga rešiti. 

JASON Hirschhorna: To je Točno tako. To je odvisno od tega, ali se trudimo, da ga rešiti. Denimo, da nismo dogaja, da ga rešiti. 

PUBLIKA: No potem, ko smo razpravljali o pred tem, to je najenostavnejši, samo da bi ga takoj na začetku, tako kazalec z nič točkami na sladkarije. 

JASON Hirschhorna: OK. Počakaj. Dovolite mi, da ustvarite sladkarije tukaj. Tako da je ta kazalec - 

OBČINSTVO: Ja, naj bi zdaj se kaže na sladkarije. Potem so kazalec od sladkarije točka za buče. 

JASON Hirschhorna: Tako? In pravijo, da imamo še en stvar na zemljevid za nič? 

PUBLIKA: No, ste jo pravkar narediti isto stvar? 

JASON Hirschhorna: Ali isto stvar. Torej, v tem primeru, če ne bomo želite, da jo razporejene Sliši se precej enostavno. Peljemo kazalec v Indice saj jih naši hash funkcijo. Imamo to točko na naši novi vozlišče. In potem karkoli že je obrnjena predhodno - v tem primeru nič, v Drugi primer buče - da, karkoli že je, ki kažejo na prej, smo dodali v naslednji od naša nova vozlišča. Mi smo vstavljanje nekaj na začetku. V bistvu je to veliko lažje kot poskuša obdržati seznam razvrščeni. Toda spet bo Iskanje gre bolj zapleteno tukaj. Vedno bova morala iti do konca. 

OK. Imate vprašanja Veriženje? Kako to deluje? Prosite jih zdaj. Res si želim, da poskrbite, da boste vse razumeti, preden se odpravimo ven. 

PUBLIKA: Zakaj si dal buče in sladkarije v isti del razpršene tabele? 

JASON Hirschhorna: Dobro vprašanje. Zakaj smo jih postavili v isti del razpršene tabele? No, v tem primeru naše hash funkcija vrne nič za oba. Tako so morali iti na Indice nič ker to je, če bomo poglej za njih, če bomo kdaj želijo, da jih poiščete. Again, s pristopom linearno sondiranje jim ne bi dal tako na nič. Toda v ločenem pristopu verige bomo, da jih tako na ničli in nato ustvarite seznam off nič. 

In ne želimo prepisati buče preprosto za to, ker potem bomo Predvidevam, da je bilo bučno Nikoli ne vstavi. Če bomo kar naprej eno stvar v mesto, da bi bilo slabo. Potem ne bi bilo priložnost za nas doslej - če bomo kdaj imeli dvojnik, nato pa smo bi samo izbrisali našo začetno vrednost. Tako da je, zakaj mi ta pristop. Ali pa je to, zakaj smo se odločili - toda spet smo izbral drugačen pristop veriženje, ki obstaja še veliko drugih pristopov lahko bi izbrali. Ne da odgovoriti na vaše vprašanje? 

OK. Carlos. Linearni sondiranje bi vključevalo - Če smo ugotovili, trčenje na nič, smo bi bilo videti v naslednjem kraju samem, da vidim, če je bil odprt in ga tam. In potem si bomo ogledali v naslednjem športu in vidim, če je bil odprt in ga tam. Tako smo ugotovili, naslednji na voljo odprto mesto in ga tam. Še kakšno vprašanje? Ja, Avi. 

PUBLIKA: Kot nadaljevanje, da kaj misliš z naslednjo samem? V razpršene tabele ali v povezanem seznamu. 

JASON Hirschhorna: Za linearno programiranje, brez povezani seznam. Naslednja točka na razpršene tabele. 

PUBLIKA: OK. Torej bi hash tabela biti inicializiran na velikost - kot število nizov da si vstavljanje? 

JASON Hirschhorna: Bi želijo, da bi bilo res veliko. Da. Tukaj je slika tega, kar smo samo narisal na krovu. Spet imamo trčenje tukaj. na 152. In boste videli bomo ustvarili povezani seznam od tega. Again, razpršena tabela Veriženje pristop ni ti ena morali za nastavitev težave šest vendar je tista, ki je veliko študenti ponavadi traja. Torej, na ta opomba, nam govori na kratko preden se odpravimo ven o problemu šest, in potem bom deliti zgodbo z vami. Imamo tri minute. 

Problem nastavite šest. Imate štiri funkcije - obremenitev, preverite, velikost in razkladanje. Obremenitev - dobro, da smo šli nad obremenitvijo šele zdaj. Opozorili smo tovora na krovu. In smo celo začeli kodiranje veliko vtaknemo v povezanem seznamu. Torej obremenitev ni veliko več kot kar smo pravkar počeli. 

Preverjanje je, ko imate Nekaj ​​naložen. To je enak postopek, kot je ta. Isti Prva dva dela, kjer si vrgel Nekaj ​​v funkcije razpršitve in dobili svojo vrednost. Toda zdaj ne bomo ga vstavite. Zdaj smo iskali za to. Vzorec kode sem napisal za iskanje nekaj v povezanem seznamu. Spodbujam vas, da praksa, da. Ampak intuitivno najti nekaj je Precej podobno vstavljanje nekaj. Dejansko smo narisal iskanje nekaj v povezanem seznamu, ki se gibljejo skozi, dokler ne boste prišli do konca. In če imaš do konca in ne bi ga najdejo, potem je ni. Tako da je pregled, v bistvu. 

Naslednja je velikost. Oglejmo preskočite velikosti. Nazadnje ste raztovoriti. Raztovoriti je eden nismo pripraviti na krovu ali še kodirani. Vendar vas pozivam, da poskusite kodiranje v našem vzorcu povezan primer seznama. Ampak raztovarjanje intuitivno je podoben zastonj - ali hočem reči je, podobno preveriti. Razen za zdaj vsakič, ko greš skozi, ne boš samo preverjam, vidim, če imate svojo vrednost tam. Vendar ste ob to vozlišče in je osvoboditev, v bistvu. To je tisto, razkladanje vas prosi, da storijo. Brezplačne vse, kar ste malloced. Torej greste skozi celoten seznam znova, skozi celotno hash Ponovno tabela. Tokrat ne preverjajo videti, kaj je tam. Samo sprostiti, kaj je tam. 

In končno velikost. Velikost je treba izvajati. Če se ne izvajajo velikosti - Bom rekel, kot je ta. Če se ne izvajajo velikosti v točno ena vrstica kode, vključno vrnitev izjavo, da ste početje velikost napačno. Zato poskrbite, velikost, za popolno zasnovo točk, to počnete natanko eno vrstica kode, vključno Izjava donos. 

In ne spakiram še Akchar. Eager Beaver. Hotel sem reči hvala fantje za prihod v oddelku. Imajo Happy Halloween. To je moj kostum. Nosila bom ta četrtek če sem te videl na uradnih ur. In če ste radovedni nekaj več ozadja, da bi ta kostum, občutek prosimo, da preverite 2011 del za zgodbo o tem, zakaj sem nošenje bučno kostum. In to je žalostna zgodba. Torej, poskrbite, da imate nekateri tkiva v bližini. Ampak na to, če imate Vprašanja bom ostal zunaj po oddelku. Vso srečo na problem nastaviti šest. In kot vedno, če imate vprašanja, mi prosim povejte.