JASON Hirschhorn: Bonvenon ĉiuj al la Sekcio Sep. Ni estas en semajno sep de la kurso. Kaj ĉi tiu venonta ĵaŭdo estas Halloween tia mi estas alivestita kiel kukurbo. Mi ne povus klini super kaj surmetis miaj ŝuoj, do tio estas kial mi estas nur surhavis ŝtrumpetojn. Mi ankaŭ ne surhavis ion sub tion, do mi ne povas preni ĝin, se ĝi estas distri vin. Mi pardonpetas anticipe por tio. Vi ne bezonas imagi kio okazas. Mi surhavas boksistoj. Do estas tute bona. Mi havas pli longan rakonton pri kial mi estas vestita kiel kukurbo, sed mi tuj krom tio, ke por poste en ĉi tiu sekcio ĉar mi ne volas komenci. Ni havas multe da interesaj aferoj iri super tiu semajno. La plimulto de ili rilatas rekte al koncerna semajno da problemo aro, fuŝo. Ni tuj iros super ligita listoj kaj hash tabloj cxar la tuta sekcio. Mi metas ĉi listo ĉiun semajnon, listo de rimedojn por vin helpi vin kun la materialo je tiu kurso. Se je perdo aŭ se serĉas iun pliaj informoj, vizitu unu el tiuj rimedoj. Denove, pset6 estas fuŝo, ĉi semajno pset. Kaj ĝi ankaŭ instigas vin, kaj mi kuraĝigas vin, por uzi iun alian rimedoj specife por tiu pset. En aparta, la tri mi havas listita supre sur la ekrano - gdb, kiun ni estis familiara kun kaj estis uzante por tempo nun estas tuj estos tre utila ĉi tiu semajno. Do mi metis tiun ĉi tien. Sed kiam ajn vi laboras kun C, vi devus ĉiam esti uzanta gdb al elpurigi viajn programojn. Tiu semajno ankaŭ Valgrind. Ĉu iu scias kio Valgrind faras? Spektantaro: ĝi kontrolas por memoro likoj? JASON Hirschhorn: Valgrind ĉekojn por memoro likas. Do se vi malloc ion en via programon, vi petante memoro. Je la fino de via programo, vi havas skribi libera je ĉio vi havas malloced doni la memoro dorso. Se vi ne skribas libera ĉe la fino kaj via programo venas al konkludo, Ĉio estos aŭtomate esti liberigita. Kaj por malgrandaj programoj, ĝi estas Ne ke granda traktadon. Sed se vi skribas pli longa kurado Programo kiu ne lasis, nepre, en kelkaj minutoj aux kelkaj sekundoj, do memoron filtras povas fariĝi grandegan multon. Do por pset6, La atendo estas, ke vi havos nula memoro likoj kun via programo. Por kontroli por memoro likoj, kuri Valgrind kaj gxi donos al vi iom bela eligo lasanta vi scias ĉu aŭ ne ĉiu estis libera. Ni devos praktiki kun ĝi poste hodiaŭ, mi esperas. Fine, la malsamoj komando. Vi uzas ion similan al tio en pset5 kun la peek ilo. Permesitaj vi rigardi interne. Vi ankaŭ uzata malsamoj, tro, po la problemo metita spec. Sed en permesis al vi komparu du dosierojn. Vi povus kompari la bitmap dosieron kaj info titolaj de bastono solvo kaj vian solvon en pset5 se vi elektis uzi ĝin. Klarigo ebligos vin fari tion, tiel. Vi povas kompari la korekta respondo por ĉi semajno problemon agordi vian respondon kaj vidi se ĝi regiono aŭ vidi kie la eraroj estas. Do tiuj estas tri bonajn ilojn kiuj Vi devus uzi por ĉi tiu semajno, kaj definitive kontroli viajn programo kun tiuj tri iloj antaŭ ĝiri it in Denove, kiel mi jam menciis, ĉiu semajno, se vi havas iun opinion pri mi - ambaŭ pozitiva kaj konstrua - bonvolu direkti al la retejo ĉe la malsupro de tiu diapozitivo kaj enigo ŝin tie. Mi vere dankas ajnan kaj ĉiuj sugestoj. Kaj se vi donos al mi specifaj aferoj kiuj Mi povas fari por plibonigi aŭ ke mi estas faras bone, ke vi ŝatus min al daŭrigi, mi prenos ke al koro vere provas malfacile aŭskulti al viaj sugestoj. Mi ne povas promesi ke mi faros ĉio, kvankam, kiel portanta Kukurbo kostumo ĉiusemajne. Do ni intencas pasigi la plejparto de sekcio, kiel mi menciis, parolante pri ligita lertaj kaj hash tabloj, kiuj estos rekte aplikebla al la problemo starigis ĉi tiun semajnon. Ligita lertaj ni transiru relative rapide, ĉar ni pasigis belan iom el tempo iras trans gxin en sekcio. Kaj tiel ni ricevos rekte en la kodiga problemojn ligita listoj. Kaj poste fine ni parolos pri hash tabloj kaj kiamaniere ili apliki al tiu semajno da problemo metita. Vi jam vidis tiun kodon antaŭe. Tio ĉi estas struct, kaj ĝi estas difinanta io nova nomita nodo. Kaj ene de nodo estas entjero ĝuste ĉi tie kaj tie estas montrilo por alia nodo. Ni jam vidis ĉi tion antaŭe. Ĉi tio estis venanta ĉe kelkaj semajnoj nun. Ĝi kombinas montriloj, kiun ni vizitis laborante kun, kaj structs, kiuj permesas ni kombini du malsamajn aferojn en unu datumtipo. Estas multe okazas en la ekrano. Sed ĉiuj de ĝi devus esti relative familiara kun vi. Sur la unua linio, ni deklari novan nodon. Kaj tiam la interno de tiu nova nodo, mi starigis la entjero en tiu nodo al unu. Ni vidos en la sekvanta linio mi faras printf komando, sed mi grayed ekstere la printf komando ĉar la vere grava parto estas tiu linio tie - new_node.n. Kion signifas la skalara signifi? Spektantaro: Iru al la nodo kaj taksi la n valoron por ĝi. JASON Hirschhorn: Tio estas ĝuste. Dot signifas aliri la n parto de tiu nova nodo. Ĉi sekvanta linio faras kion? Michael. Spektantaro: Ĝi kreas alian nodon ke estos fingromontras la nova nodo. JASON Hirschhorn: do tio ne krei novajn nodo. Ĝi kreas kio? Spektantaro: A montrilo. JASON Hirschhorn: A montrilon al nodo, kiel indikita de ĉi tiu nodo * tie. Do ĝi kreas montrilon al nodo. Kaj kio nodo estas tio indikante al, Michael? Spektantaro: Nova nodon? JASON Hirschhorn: Nova nodo. Kaj tio montras tie, ĉar ni jam donis al ĝi la adreson de nova nodo. Kaj nun en tiu linio ni vidas du malsamaj manieroj de esprimi la saman aferon. Kaj mi volis atentigi, kiel tiuj du aferoj estas la sama. En la unua linio, ni dereference la montrilo. Do ni iru al la nodo. Tion ĉi stelo signifas. Ni jam vidis ke antaŭ kun montriloj. Iru al tiu nodo. Tio estas en krampoj. Kaj poste aliri tra la skalara operatoro la n elemento de tiu nodo. Do tio estas preni la sintakso ni vidis ĝuste ĉi tie kaj nun uzante ĝin kun montrilo. Kompreneble, ĝi ricevas ia okupata se vi skribas tiujn parentezoj - ke stelon kaj tiu punkto. Ĝi alvenas iom okupita. Do ni havas kelkajn sintaksa sukero. Kaj ĉi tiu lineo ĝuste ĉi tie - ptr_node-> n. Tio faras la saman ĝusta afero. Do tiuj du linioj de kodo estas ekvivalentaj kaj faros la ĝusta sama afero. Sed mi volis atentigi tiujn antaux ni iru plu tiel vi komprenu ke vere tion ĝuste ĉi tie estas nur sintaksa sukero por dereferencing la montrilon kaj tiam tuj la n parto de tiu struct. Demandojn pri tiu diapozitivo? OK. Do ni tuj iru tra paro de operacioj kiujn vi povas fari sur ligita listoj. A ligillisto, recall, estas serio de nodoj kiuj indikas unu la alian. Kaj ni ĝenerale komenciĝas per montrilo nomita kapo, ĝenerale, ke antaŭ al la unua afero en la listo. Do en la unua linio tie, ni havas nian originalan L unua. Do tiu afero vi povas pensi - tio teksto ĝuste ĉi tie vi povas pensi pri kiel nur la montrilon ni stokis ie ke punktoj al la unua ero. Kaj en ĉi ligillisto ni havos kvar nodoj. Ĉiu nodo estas granda skatolo. La pli granda skatolo interne de la grandaj skatolo estas la entjera parto. Kaj tiam ni havas montrilon parto. Ĉi tiuj skatoloj ne estas allogataj al skalo ĉar kiom granda estas entjero en bajtoj? Kiom grandaj estas nun? Kvar. Kaj kiom granda estas montrilo? Kvar. Do vere, se ni devis desegni ĉi grimpi ambaŭ skatoloj estus la sama amplekso. En ĉi tiu kazo, ni volas enmeti io en la ligillisto. Do vi povas vidi cxi tie ni enmeto kvin Ni trairi tra la ligillisto, trovi kie kvin iras, kaj poste enigi ĝin. Ni rompu ke malsupren kaj iri iomete pli malrapide. Mi tuj atentigi al la estraro. Do ni havas nian nodo kvin kiu ni kreis en mallocs. Kial ĉiuj ridante? Nur ŝercas. OK. Do ni malloced kvin. Ni kreis ĉi tiun nodon ie ajn. Ni havas ĝin preta por foriri. Ni komencos je la fronto de nia listo per du. Kaj ni volas enmeti en ordo modo. Do, se ni vidas du kaj ni volas meti en kvin, kion ni faros kiam ni vidas io malpli ol ni? Kio? Ni volas enmeti kvin en tiun ligillisto, subtenante ŝin ordo. Ni vidas numero du. Do kion ni faru? Marcus? Spektantaro: Alvoku la montrilo al la sekva nodo. JASON Hirschhorn: Kaj kial ni iru al la sekvanta unu? Spektantaro: Ĉar ĝi estas la sekvanta nodo en la listo. Kaj oni nur scias, ke aliaj situo. JASON Hirschhorn: Kaj kvin estas pli granda ol du, en aparta. Ĉar ni volas konservi ĝin ordo. Do kvin estas pli granda ol du. Do ni pluiru al la sekva. Kaj nun ni atingas kvar. Kaj kio okazas, kiam ni atingos kvar? Kvin estas pli granda ol kvar. Do ni observu iras. Kaj nun ni estas en ses. Kaj kion ni vidas en ses? Jes, Karolo? Spektantaro: Ses estas pli granda ol kvin. JASON Hirschhorn: Ses estas pli granda ol kvin. Do tiu estas kie ni volas enigi kvin. Tamen memoru, ke se ni havas nur unu montrilon tie - tio estas nia ekstra montrilon tio petolanta tra la listo. Kaj ni indikante ses. Ni miskalkulis kio venas antaux ses. Do, se ni volas enmeti ion en tiu listo subtenante ŝin ordo, ni verŝajne bezonos kiom da montriloj? Spektantaro: Du. JASON HIRSCHORN: Du. Unu por konservi trako de la nuna unu kaj unu por sekvigi la antaŭa. Ĉi tio estas nur unuope ligillisto. Ĝi nur iras unu direkto. Se ni havis duoble ligillisto, kie ĉio estis indikante la afero post tio kaj la afero antaux gxi, tiam ni ne bezonas fari tion. Sed en tiu kazo ni ne volis perdi spuro de kio venis antaŭ ni en kazo ni bezonas enmeti kvin ie en la mezo. Diru al ni enmeto naŭ. Kio okazus kiam ni akiris al ok? Spektantaro: Vi devus su ke nula punkto. Anstataŭ havanta nula punkto vi havus aldoni elementon kaj tiam havi ĝi indikas naŭ. JASON HIRSCHORN: Ekzakte. Do ni ricevas ok. Ni atingas la finon de la listo ĉar ĉi notas al nula. Kaj nun, anstataŭ havi ĝin indikas nula ni havas ĝin marki niajn novajn nodo. Kaj ni starigis la montrilon en nia nova vertico al nula. Ĉu iu havas demandojn pri enmeto? Kio, se mi ne zorgas pri plenumantaj listo ordo? Spektantaro: Stick ĝin ĉe la komencante aŭ la finon. JASON HIRSCHORN: Stick ĝin ĉe la komenco aŭ la fino. Kiu el ni faru? Bobby? Kial la fino? Spektantaro: Ĉar la komenco Estas jam plenigitaj. JASON HIRSCHORN: okej. La komenco estas jam plena. Kiu volas argumenti kontraŭ Bobby. Marcus. Spektantaro: Bone vi verŝajne volas trae ĉe la komenco, ĉar alie, se vi metas ĝin ĉe Fine vi devus trairi la tutan liston. JASON HIRSCHORN: Ekzakte. Do, se ni pensas pri ekzekuto, la runtime de enmeto fine estus n, la amplekso de ĉi. Kio estas la granda O runtime de enmeto ĉe la komenco? Konstanta tempo. Do se vi ne zorgas pri subtenante io ordo, multe pli bone simple enmeti komence de ĉi tiu listo. Kaj kiu povas esti farita en konstanta tempo. OK. Sekva operacio trovi, kion aliaj - ni verkitaj ĉi tiel serĉo. Sed ni tuj trarigardi la ligillisto por iu celo. Vi infanoj vidis kodo serĉu antaŭe en prelego. Sed ni ia ĝuste faris ĝin kun enigi, aŭ almenaŭ la enmeto io ordo. Vi aspektas tra, irante nodo per nodo, ĝis vi trovos la numero kiun vi estas serĉas. Kio okazas se oni atingas la finon de la listo? Diru Mi serĉas naux kaj mi atingi la finon de la listo. Kion ni faru? Spektantaro: Reiru falsa? JASON HIRSCHORN: Reiru falsaj. Ni ne trovis ĝin. Se vi atingas la fino de la listo kaj vi ne trovos la nombro vi estas serĉas, ĝi ne estas en tie. Demandojn pri trovi? Se tiu estis ordo listo, kion farus esti malsamaj por nia serĉado? Jes. Spektantaro: ĝi trovus la unua valoro tio estas pli granda ol la vi serĉas kaj tiam revenu falsaj. JASON HIRSCHORN: Ekzakte. Do, se ĝi estas ordigitaj listo, se ni atingos iu kiu estas pli granda ol kion ni serĉas, ni ne bezonas teni tuj la fino de la listo. Ni povas je tiu punkto redoni malvera Ĉar ni ne tuj trovas ĝin. La demando estas nun, ni jam parolis pri teni ligita lertaj ordo, gardante ilin Unsorted. Tio okazas al esti io, kion vi estas probable tuj devos pensi kiam kodigo problemo starigis kvin se vi elekti hash tabelo kun apartaj ĉeni alproksimiĝo, kio Ni parolos pri poste. Sed ĉu ĝi valoras por gardi la listo ordo kaj tiam povos eble havas rapida serĉoj? Aŭ ĉu pli bone estas por rapide enigi io en konstanta runtime sed tiam havi plu serĉanta? Tio estas tradeoff rajton tie, ke vi akiri por decidi kio estas pli taŭga por via specifa problemo. Kaj ne estas nepre unu absolute dekstra respondo. Sed estas certe decidon vi ricevas fari, kaj probable bona defendi ke en, ekzemple, komento aŭ du kial vi elektis unu super la alia. Fine, forigado. Ni jam vidis forviŝo. Ĝi estas simila al serĉado. Ni serĉas la elemento. Diru ni provas forigi ses. Do ni trovas ses ĝuste ĉi tie. La afero, kiun ni devas certigi ni fari estas, ke kio estas montrante ses - kiel ni vidas en ŝtupo du ĉi tie - kion ajn'S indikante ses bezonojn salti ses nun kaj oni ŝanĝis al kion ajn ses notas al. Ni ne volas iam orfo la cetera nia listo per forgesante agordi ke antaŭa montrilo. Kaj poste kelkfoje, depende pri la programo, ili timige nur forviŝi ĉi tiu nodo tute. Kelkfoje vi volas reveni la valoro kiu estas en ĉi tiu nodo. Do jen kiel forviŝo verkoj. Demandojn pri forviŝi? Spektantaro: Do, se vi tuj forviŝi tio, ĉu vi nur uzu liberan ĉar supozeble ĝi malloced? JASON HIRSCHORN: Se vi volas liberigi iu kiu estas ekzakte rajton kaj vi malloced ĝin. Diru ni volis reveni ĉi valoro. Ni povus reveni ses kaj poste liberaj tiu nodo kaj alvoko libera je tio. Aŭ ni havus verŝajne nomos liberaj unua kaj tiam revenu ses. OK. Do ni pluiru al ekzerci kodigo. Ni tuj programi tri funkcioj. La unuan oni nomas insert_node. Do vi havas kodon, kiun mi retpoŝtis vin, kaj se vi rigardas ĉi poste vi povas aliri la kodon en linked.c sur la CS50 retejo. Sed en linked.c, tie estas kelkaj skeleto kodo kiu estas jam estis verkita por vi. Kaj tiam tie estas kelkaj funkcioj vi devas skribi. Unue ni tuj skribi insert_node. Kaj kion insert_node faras estas enmetas entjero. Kaj vi donas al la entjero en ligillisto. Kaj precipe, vi bezonos observi la listo ordo de malgranda ĝis granda. Ankaŭ, vi ne volas enigi ajnan duobligitaj. Fine, kiel vi povas vidi insert_node resendas bool. Do vi devus lasi la uzanton scias ĉu ĉu ne la insert estis prospera por redoni vera aŭ malvera. Je la fino de tiu programo - kaj por tiu ĉi etapo vi ne bezonas maltrankviligi liberigante nenion. Do ĉiuj vi faras estas prenante entjero kaj la enmeto ĝin en listo. Tio estas kion mi petas vin fari nun. Denove, en la linked.c, kion vi ĉiuj havas, estas la skeleto kodo. Kaj vi devus vidi al la fundo la specimena funkcio deklaro. Tamen, antaŭ ol iri en kodiga ĝi en C, mi ege rekomendas al vi iri tra la paŝojn ni vizitis praktiki ĉiun semajnon. Ni jam iris tra bildo de ĉi. Do vi devas havi iun komprenon pri kiel tio funkcias. Sed mi volas instigi vin skribi iuj _pseudocode_ antaux subnaĝado in Kaj ni tuj iru super _pseudocode_ kiel grupo. Kaj tiam tuj vi skribas vian _pseudocode_, kaj iam ni skribas niaj _pseudocode_ kiel grupo, vi povas iru en kodiga gxin en C. Kiel kapojn supren, la insert_node funkcio estas probable la trickiest de la tri ni tuj skribos, ĉar mi aldonis iujn pliajn limigojn al via programado, precipe tiu vi ne tuj enigi ajnan duobligitaj kaj ke la listo devus resti ordo. Do tiu estas ne-bagatela programo ke vi bezonas kodigi. Kaj kial vi ne prenas kvin ĝis sep minutoj nur por akiri laboras pri la _pseudocode_ kaj la kodon. Kaj tiam ni komencos irante kiel grupo. Denove, se vi havas demandojn simple levi vian manon kaj mi venos ĉirkaŭe. . Ni ankaŭ ĝenerale faras tiuj - aŭ mi ne eksplicite diras, ke vi povas labori kun homoj. Sed evidente, mi ege rekomendas al vi, se vi havas demandojn, peti al la najbaro sidis apud vi aŭ eĉ labori kun iu alie, se vi volas. Ĉi tio ne devas esti individua silenta aktiveco. Ni komencu per skribi iun _pseudocode_ sur la tabulo. Kiu povas doni al mi la unuan linion de _pseudocode_ por tiu programo? Por ĉi tiu funkcio, prefere - insert_node. Alden? Spektantaro: Do ​​la unua afero, kiun mi faris estis krei novan sagon al la nodo kaj mi pravalorizita gxin indikante la sama afero, kiun listo estas indikante. JASON HIRSCHORN: okej. Do vi kreas novan montrilo al la listo, ne al la nodo. Spektantaro: Dekstra. Jes. JASON HIRSCHORN: okej. Kaj poste kion ni volas fari? Kio post tio? Kio pri la nodon? Ni ne havas nodo. Ni nur havas valoron. Se ni volas enmeti nodo, kion ni faras bezonas fari unue, antaŭ ol ni povas eĉ pensas pri enmeto ĝi? Spektantaro: Ho, pardonon. ni bezonas malloc spaco por nodo. JASON HIRSCHORN: Bonege. Ni do - OK. Ne eblas atingi tiun altan. OK. Ni tuj iras malsupren, kaj poste ni uzas du kolumnoj. Mi ne povas iri, ke - OK. Krei novan nodon. Vi povas krei alian montrilon al listo aux vi povas simple uzi lerta kiel ĝi ekzistas. Vi ne vere bezonas tion fari. Do ni kreu novan nodon. Granda. Tio estas kion ni faru unue. Kio estas sekvanta? Spektantaro: Atendu. Ĉu ni krei novan nodon nun aŭ cxu ni atendu por certigi ke ne estas duobligitaj de la nodo sur la listo antaux ni krei ĝin? JASON HIRSCHORN: Bona demando. Ni opinias, ke por poste pro la plimulto de la tempo ni estos kreado nova nodo. Do ni observu ke tie. Sed tio estas bona demando. Se ni kreu ĝin kaj ni trovu duplikaton, kio devus ni faros antaux reveni? Spektantaro: Liberigu lin. JASON HIRSCHORN: Jes. Probable liberigi ĝin. OK. Kion ni faros post ni krei novan nodon? Annie? Spektantaro: ni metis la nombro en la nodo? JASON HIRSCHORN: Ekzakte. Ni metis la nombro - Ni malloc spaco. Mi tuj lasi tiun ĉiuj kiel unu linio. Sed vi pravas. Ni malloc spaco, kaj poste ni metas la nombro in Ni povas ecx starigu la montrilo parton de ĝi al nula. Tio estas ekzakte pravas. Kaj poste kio pri post tio? Ni eltiris ĉi tiun pentraĵon sur la tabulo. Do kion ni faru? Spektantaro: Ni iru tra la listo. JASON HIRSCHORN: Iru tra la listo. OK. Kaj kion ni kontrolos je ĉiu vertico. Kurt, kion ni kontrolu cxar je ĉiu vertico? Spektantaro: Vidu, ĉu la n valoro de ke nodo estas pli granda ol la n valoro de nia nodo. JASON HIRSCHORN: okej. Mi tuj faros - yeah, OK. Do estas n - Mi intencis diri, se valoro estas pli granda ol tiu nodo, do kion ni faru? Spektantaro: Bone, tiam ni enŝovu la afero ĝuste antaŭ tio. JASON HIRSCHORN: okej. Do, se ĝi estas pli granda ol tio, do ni volas enmeti. Sed ni deziras enmeti ĝin ĝuste antaŭ ĉar ni ankaŭ devus esti konservanta trako, do, de kio estis antaŭe. Do enŝovu antaŭe. Do ni verŝajne maltrafis ion fruaj plu. Ni probable devas esti subtenante spuro de kio okazas. Sed ni devos reiri tien. Do kio valoro estas malpli ol? Kurt, kion ni faros, se valoro estas malpli ol? Spektantaro: Do ​​vi nur plu iri krom se ĝi estas la lasta. JASON HIRSCHORN: Mi ŝatas tiun. Do iru al la sekva nodo. Krom se ĝi estas la lasta - ni probable kontrolanta por ke en la terminoj de kondiĉo. Sed jes, proksima nodo. Kaj tio Fariĝas tro malalta, do ni havos movi tien. Sed se - povas everybody vidi ĉi tion? Se ni estas egalaj, kion ni faros? Se la valoro ni provas enmeti estas egala al tiu nodo valoron? Jes? Spektantaro: [inaudibles]. JASON HIRSCHORN: Jes. Donita ĉi - Marcus pravas. Ni povis esti eble farita io malsama. Sed pro tio ke ni jam kreis ĝin, tie ĉi Ni devas liberiĝi kaj tiam revenu. Ho knabo. Ĉu tio estas bona? Kiel estas tiu? OK. Liberaj kaj tiam kio ni reveni, [inaudibles]? OK. Ĉu ni mankas io? Do kie ni konservanta trako de la antaŭa nodo? Spektantaro: mi kredas ke estus iri post krei novan nodon. JASON HIRSCHORN: okej. Do komence ni devos probable - yeah, ni povas krei montrilon al nova nodo, kiel antaŭa nodo montrilon kaj kurento nodo montrilo. Do ni enmetu cxi tiu. Krei aktuala kaj antaŭa montriloj al la nodoj. Sed kiam ni ĝustigus tiuj indikoj? Kie do oni faru tion en la kodo? Jeff? Spektantaro: - valoro kondiĉoj? JASON HIRSCHORN: Kiu unu en aparta? Spektantaro: mi simple konfuzis. Se valoro estas pli granda ol tiu nodo, Ĉu tio ne signifas, ke vi deziras iri al la sekva nodo? JASON Hirschhorn: Do, se nia valoro estas pli granda ol la valoro de ĉi tiu nodo. Spektantaro: Jes, tiam vi ŝatus voli iri pluen en la linio, ĉu ne? JASON Hirschhorn: Ĝuste. Do ni ne enmetu ĝin ĉi tie. Se valoro estas malpli ol tiu nodo, tiam ni iru al la sekva nodo - aŭ poste ni enŝovu antaŭe. Spektantaro: Atendu, kio estas tio nodo kaj kiu estas valoro? JASON Hirschhorn: Bona demando. Valoro por ĉi tiu funkcio tiu difino estas tio, kion ni donas. Do valoro estas la kvanto ni donis. Do se la valoro estas malpli ol tio nodo, ni bezonas tempon por enmeti. Se valoro estas pli granda ol tiu nodo, ni iru al la sekva nodo. Kaj reen al la originala demando, kvankam, kie - Spektantaro: Se valoro estas pli granda ol ĉi tiu nodo. JASON Hirschhorn: Kaj tiel Kion ni faros ĉi tie? Dolĉa. Tio estas korekta. Mi simple verkos ĝisdatigo montriloj. Sed jes, kun la nuna vi devus aktualigi ĝin atentigi al la sekva. Ion alian ni mankas? Do mi tuj tajpi ĉi kodigi en gedit. Kaj dum mi faras tion, vi povas havi paro minutojn pli labori pri kodigo tiu en C. Do mi devas eniro la _pseudocode_. Rapida noto antaŭ ol ni komencu. Ni eble ne povos tute fini ĉi en ĉiuj tri el tiuj funkcioj. Tie estas korekta solvojn al ili ke mi donos retmesaĝi al Vi infanoj post sekcio, kaj ĝi volas oni afiŝis sur CS50.net. Do mi ne instigas vin al iru rigardi la sekcioj. Mi kuraĝigas vin provi tiujn en via posedi, kaj poste uzi la la praktiko problemoj por kontroli viajn respondojn. Tiuj ĉiuj estas desegnita por proksime rilati al kaj aliĝas al kio vi devos fari pri la problemo aro. Do mi rekomendas al vi ekzerci ĉi sur via propra kaj poste uzi la kodon por kontroli viajn respondojn. Ĉar mi volis pluiri al hash tabloj en iu punkto de la sekcio. Do ni ne povus akiri per ĝi ĉiujn. Sed ni tion faros tiel ni povas nun. OK. Ni komencu. Asam, kial ni kreu novan nodon? Spektantaro: Vi struct *. JASON Hirschhorn: Do nin havi tiun ĉi tien. Ho, pardonon. Vi diris, struct *. Spektantaro: Kaj tiam [? speco?] nodo aŭ c nodo. JASON Hirschhorn: okej. Mi iras por voki lin new_node do ni povas resti konsekvenca. Spektantaro: Kaj vi volas agordi ke al kapo, la unua nodo. JASON Hirschhorn: okej. Do nun tio indikus - tiel ĉi ne jam kreis novan nodon ankoraŭ. Tiu estas ĝuste montrante la unuan nodon en la listo. Kjel mi kreas novan nodon? Se mi bezonas spacon por krei novan nodon. Malloc. Kaj kiom granda? Spektantaro: La grandeco de la struct. JASON Hirschhorn: La grandeco de la struct. Kaj kio estas la struct vokis? Spektantaro: Nodo? JASON Hirschhorn: Nodo. Do malloc (sizeof (nodo)); donas al ni spacon. Kaj estas tiu linio - unu afero estas malĝusta pri ĉi tiu linio. Ĉu new_node puntero al struct? Tio estas ĝenerala nomo. Kio estas ĝi - nodo, ekzakte. Ĝi estas nodo *. Kaj kion ni faros tuj post ni malloc ion, Asán? Kio estas la unua aĵo kiun ni faras? Kio, se ĝi ne funkcias? Spektantaro: Ho, kontrolu se ĝi antaŭ la nodon? JASON Hirschhorn: Ekzakte. Do se vi new_node egalas egaluloj nula, kion ni faros? Ĉi resendas bool, ĉi tiu funkcio. Ekzakte. Aspektas bone. Io ajn aldoni tie? Ni devos aldoni tion al la fino. Sed kiu ĝis nun aspektas bone. Krei aktuala kaj antaŭa montriloj. Michael, kiel mi faru tion? Spektantaro: Vi havus fari nodon *. Vi devus fari ne por new_node sed por la nodoj ni jam havas. JASON Hirschhorn: okej. Do la nuna nodo ni estas sur. Mi vokos ke curr. Ĉiuj pravas. Ni decidis ni volas konservi du, ĉar ni bezonas scii kio estas antaŭ ĝi. Kion ili get pravalorizita al? Spektantaro: Ilia valoro en nia listo. JASON Hirschhorn: Do kio estas la unua afero en nia listo? Aŭ kiel ni scias, kie la komencante de nia listo estas? Spektantaro: Ĉu ne pasis en la funkcio? JASON Hirschhorn: Ĝuste. Ĝi estis aprobita en ĝuste ĉi tie. Do, se ĝi estas transiris en la funkcio, la komenci de la listo, kion ni starigis nuna egalas? Spektantaro: Listo. JASON Hirschhorn: Listo. Tio estas ekzakte pravas. Nun ĝi havas la adreson de la komenco de nia listo. Kaj kio pri la antaŭaj? Spektantaro: Listo minus unu? JASON Hirschhorn: Estas nenion antaux gxi. Do kion ni povas fari por signifi nenion? Spektantaro: Nula. JASON Hirschhorn: Jes. Tio sonas kiel bona ideo. Perfekta. Dankon. Iru tra la listo. Konstantino, kiel longe ni iras iri tra la listo? Spektantaro: Ĝis Ni atingos nula. JASON Hirschhorn: okej. Do, se, dum, por buklo. Kion ni faras? Spektantaro: Eble por buklo? JASON Hirschhorn: Ni faru por buklo. OK. Spektantaro: Kaj ni diras por - ĝis la aktuala montrilo estas ne egala al nula. JASON Hirschhorn: Do, se ni konas la kondiĉo, kiel oni povas skribi buklo bazita sur tiu kondiĉo. Kiajn loop devus ni uzi? Spektantaro: Dum. JASON Hirschhorn: Jes. Tio igas pli senco bazita for de tio, kion vi diris. Se ni nur volas iri en ni li farus nur scias tion, ĝi farus senco fari dum buklo. Dum aktuala ne egala nula, se valoro estas malpli ol tiu nodo. Akshar, donu al mi cxi tiun linion. Spektantaro: Se nuna-> n n malpli ol valoro. Aŭ inversigi tion. Switch ke krampo. JASON Hirschhorn: Pardonu. Spektantaro: Ŝanĝi la krampo. JASON Hirschhorn: Do, se ĝi estas pli granda ol valoro. Ĉar tio estas konfuziga kun la komenti supre, mi faros tion. Sed jes. Se nia valoro estas malpli ol tio nodo, kion ni faros? Oh. Mi havas ĝin ĉi tie. Enŝovu antaŭe. OK. Kiel ni faru tion? Spektantaro: Ĉu ĝi ankoraŭ min? JASON Hirschhorn: Jes. Spektantaro: Vi - new_node-> proksima. JASON Hirschhorn: Do kio estas ke tuj egalas? Spektantaro: Ĝi okazas al egala fluo. JASON Hirschhorn: Ekzakte. Kaj tiel la alia - kion ajn ni bezonas ĝisdatigi? Spektantaro: Kontroli se pasinteco egalas nula. JASON Hirschhorn: Se Prev - do se prev egalas nula. Spektantaro: Tio signifas, ke ĝi okazas igi la kapo. JASON Hirschhorn: Tio signifas ĝi nun estas la kapo. Tial do, kion ni faros? Spektantaro: Ni faru kapo egalas new_node. JASON Hirschhorn: Kapo egalas new_node. Kaj kial estras ĉi tie, ne listo? Spektantaro: Pro kapo estas tutmonda variablo, kiu estas la starta loko. JASON Hirschhorn: Dolĉa. OK. Kaj - Spektantaro: Do ​​vi ne alie prev-> sekvanta egalas new_node. Kaj tiam vi revenos vera. JASON Hirschhorn: Kie do Ni starigis new_node fino? Spektantaro: mi volus, - Mi proponas ke je la komenco. JASON Hirschhorn: Do, kion linio? Spektantaro: Post la se komunikaĵo kontrolanta se ĝi estas konata. JASON Hirschhorn: Ĝuste ĉi tie? Spektantaro: Mi volus fari new_node-> n egalas valoron. JASON Hirschhorn: Sonas bone. Probable ĝi havas sencon - ni ne bezonas scii kion listo ni estas en ĉar ni nur kontraktanta kun listo. Do bonan funkcion deklaro por tio estas nur por forigi la tute kaj nur enmeti valoron en kapo. Ni eĉ ne bezonas scii kion listo ni estas in Sed mi gardos ĝin por nun kaj tiam ŝanĝu ĝin sur ĝisdatigi la diapozitivojn kaj kodo. Por ke aspektas bona por nun. Se valoro -, kiu povas fari ĉi tiu linio? Se - Kion ni faros ĉi tie, Noa. Spektantaro: Se valoro estas pli granda ol curr-> n - JASON Hirschhorn: Kiel fari ni iru al la sekva nodo? Spektantaro: Curr-> n estas egala al new_node. JASON Hirschhorn: Do n estas Kiun parton de la struct? La entjero. Kaj new_node estas montrilo al nodo. Do kio parto de curr ni aktualigi? Se ne n, tiam kio estas la alia parto? Noa, kio estas la alia parto. Spektantaro: Ho, proksima. JASON Hirschhorn: Venonta, ekzakte. Ekzakte. Sekva estas la dekstra. Kaj kion ajn ni bezonas ĝisdatigi, Noa? Spektantaro: La montriloj. JASON Hirschhorn: Tiel Ni ĝisdatigis aktualan. Spektantaro: Prev-> proksima. JASON Hirschhorn: Jes. OK, ni paŭzi. Kiu povas helpi al ni el ĉi tie? Manu, kion ni faru? Spektantaro: Vi havas por agordi gxi egalas al curr-> proksima. Sed faru tion antaŭ la antaŭa linio. JASON Hirschhorn: okej. Ĉu io alia? Akshar. Spektantaro: Mi ne opinias ke vi estas signifis ŝanĝi curr-> proksima. Mi kredas ke vi intencis fari curr egaluloj curr-> apud iri al la sekva nodo. JASON Hirschhorn: Do bedaŭras, kie? Sur kio linio? Ĉi tiu linio? Spektantaro: Jes. Faru curr egalas curr-> proksima. JASON Hirschhorn: Do tio estas korekta ĉar nuna estas montrilon al nodo. Kaj ni volas atentigi al la sekva nodo de kio Fariĝas aktuale fingromontris. Curr mem havas proksiman. Sed se ni estis ĝisdatigi curr.next, ni estus ĝisdatigi la efektiva noto mem, ne tie, kie tio montrilo notis. Kio pri ĉi tiu linio, kvankam. Avi? Spektantaro: Prev-> apud egalas curr. JASON Hirschhorn: Do denove, se prev estas montrilon al nodo, prev-> proksima estas la reala montrilon en la nodo. Do tio estus ĝisdatigi a montrilon en nodo al curr. Ni ne volas aktualigi puntero en nodo. Ni volas aktualigi antaŭa. Do kiel ni faros tion? Spektantaro: Estus simple esti prev. JASON Hirschhorn: Ĝuste. Prev estas montrilo al nodo. Nun ni ŝanĝas ĝin al nova montrilon al nodo. OK Ni movi malsupren. Fine, tiu lasta kondiĉo. Jeff, kion ni faros ĉi tie? Spektantaro: Se valoro estas egala al curr-> n. JASON Hirschhorn: Pardonu. Ho mia bono. Kio? Valoro == curr-> n. Kion ni faru? Spektantaro: Vi ŝatus liberigi nian new_node, kaj tiam vi povus redoni malvera. JASON Hirschhorn: Jen kion ni skribis tiel multe. Ĉu iu havas ion aldoni antaux ni faru? OK. Ni provu ĝin. Kontrolo povu atingi la finon de ne-nula funkcio. Avi, kio okazas? Spektantaro: Cxu vi supozas meti reveno vera ekster la tempo buklo? JASON Hirschhorn: Mi ne scias. Ĉu vi volas de mi? Spektantaro: Ne gravas. N-ro JASON Hirschhorn: Akshar? Spektantaro: Mi kredas ke vi intencis meti reveno falsaj fine de la dum-cirklon. JASON Hirschhorn: Do kie ĉu vi volas, ke ĝi iras? Spektantaro: Kiel ekstere dum buklo. Do se vi eliras dume buklo ke rimedoj ke vi jam atingis la finon kaj nenio okazis. JASON Hirschhorn: okej. Do, kion ni faros ĉi tie? Spektantaro: Vi revenos malvera tie ankaŭ. JASON Hirschhorn: Ho, ni faru ĝin en ambaŭ lokoj? Spektantaro: Jes. JASON Hirschhorn: okej. Ĉu ni iru? Ho mia bono. Mi bedaŭras. Mi pardonpetas pro la ekrano. Ĝi estas speco de freaking surversxis sur nin. Do elektu eblo. Nulo, por la kodo, fermas la programon. Oni enmetas ion. Ni enmetu tri. La insert ne sukcesis. Mi tuj presi. Mi ne havas ion. OK. Eble tio estis nur bonŝancaĵo. Enmetu unu. Ne sukcesas. OK. Ni kuras tra GDB vere rapide por kontroli kio okazas. Memoru gdb. / La nomon de via programo akiras nin en GDB. Ĉu tio estas multe manipuli? La brilantaj? Verŝajne. Fermu viajn okulojn, kaj prenu iom profunda spirojn se vi laciĝos rigardi ĝin. Mi estas en GDB. Kio estas la unua aĵo kiun mi faras en GDB? Ni devas eltrovi kio okazas ĉi tie. Ni vidu. Ni havas ses minutojn al figuro el kio okazas. Break ĉefa. Kaj tiam kion mi faru? Karolo? Kuru. OK. Ni elektu eblo. Kaj kion tio N fari? Sekva. Jes. Spektantaro: Ĉu vi ne mencii - vi ne dirus, ke la kapo, tio estis pravalorizita al nula ĉe la komenco. Sed mi pensis, ke vi diris ke estis okej. JASON Hirschhorn: Ni iru - ni rigardu en GDB, kaj poste ni reiros. Sed sonas kiel vi jam havas iuj ideoj pri kio okazas. Do ni volas enmeti ion. OK. Ni enmeti. Bonvolu entajpi int. Ni devos enmeti tri. Kaj tiam mi estas sur tiu linio. Kjel mi iras komenci debugging la insert sciata funkcio? Ho mia bono. Tio estas tre. Estas ke freaking multon? Spektantaro: Ho, ĝi mortis. JASON Hirschhorn: mi ĵus tiris ĝin. OK. Spektantaro: Eble ĝi estas la alia fino de la drato. JASON Hirschhorn: Wow. Do la funda linio - Kion vi diris? Spektantaro: Mi diris la ironio de teknikaj malfacilaĵojn en ĉi tiu kategorio. JASON Hirschhorn: Mi scias. Se nur mi havis kontrolon super tiu parto. [Inaudibles] Tio sonas bonege. Kial vi ne knaboj komenci pensi pri kion ni povus fari maljustecon, kaj ni estos denove en 90 sekundoj. Avica, mi tuj demandas al vi kiel iri interne insert_node elpurigi ĝin. Do tiu estas kie ni lastaj cxesis. Kjel mi iras interne insert_node, Avica, ekzameni kio okazas? Kio GDB ordonon? Break ne prenu min enen. Ĉu markizino scias? Spektantaro: Kio? JASON Hirschhorn: Kio GDB komando Mi uzas por iri ene ĉi funkcio? Spektantaro: Paŝu? JASON Hirschhorn: Paŝi tra S. Tio portas min enen. OK. New_node mallocing iun spacon. Ke ĉiuj similas liajn iras. Ekzamenu new_node. Ĝi alvenis iuj memoro adreso. Ni kontrolu - ke estas ĉio ĝustas. Do ĉio ĉi tie ŝajnas laboros korekte. Spektantaro: Kio estas la diferenco inter P kaj ekrano? JASON Hirschhorn: P staras por presi. Kaj do vi demandas, kio estas la diferenco inter tio kaj tio? En ĉi tiu kazo, nenio. Sed ĝenerale estas iuj diferencoj. Kaj vi devas rigardi en la GDB manlibro. Sed en tiu kazo, nenio. Ni inklinas uzi print, kvankam, ĉar ni ne bezonas fari multe pli ol presi sola valoro. OK. Do ni estas sur linio 80 de nia kodo, opcio nodo * curr egala al listo. Ni presi curr. Ĝi egalas listo. Dolĉa. Atendu. Ĝi egalas ion. Tio ne ŝajnas pravas. Tie ni iru. Ĝi estas pro tio en GDB, dekstra, se ĝi estas la linio estas en gxi ne ekzekutitaj ankoraŭ. Do vi devas reale tajpi sekvanta ekzekuti la linion antaŭ vidi liajn rezultojn. Do tie estas ni. Ni nur ekzekutita tiun linion, antaŭa egalas nula. Do denove, se ni presi antaŭa ni ne vidas ion strangan. Sed se ni vere ekzekuti ke linio, tiam ni vidos ke tiu linio laboris. Do ni havas curr. Tiuj estas ambaŭ bonaj. Ĝuste? Nun ni estas sur tiu linio ĝuste ĉi tie. Dum curr ne egala nula. Nu, kion faras curr egala? Ni nur vidis ŝin egalis nula. Ni presas gxin. Mi tion printi ĝin denove. Do estas ke dum buklo tuj ekzekuti? Spektantaro: N-ro JASON Hirschhorn: Do kiam mi tajpis ke linio, vi vidas ni saltis tuta vojo malsupren al la fundo, revenu falsaj. Kaj tiam ni tuj revenos malvera kaj li revenu al nia programo kaj eventuale elprinti, kiel ni vidis, la insert ne sukcesis. Do, iu havas ajn ideojn pri kio Ni bezonas fari ripari tion? Mi iras al atendu ĝis mi vidos paro de manoj iru. Ni ne ekzekutis ĉi. Rememoru, tiu estis la unua afero, kiun ni estis farantaj. Mi ne volas fari paron. Mi tuj faros kelkajn. Ĉar paron signifas du. Mi atendos pli ol du. La unua inserción, curr, defaŭlte egalas nula. Kaj tiu buklo nur ekzekutas se curr ne estas nula. Do kiel mi povas preni ĉirkaŭ ĉi? Mi vidas tri manoj. Mi atendos pli ol tri. Marko, kion vi opinias? Spektantaro: Nu, se vi bezonas ĝin ekzekuti pli ol unufoje, vi nur ŝanĝi ĝin al la do-while buklo. JASON Hirschhorn: okej. Ĉu tio solvos nia problemo, kvankam? Spektantaro: En ĉi tiu kazo ne pro la fakto ke la listo estas malplena. Tial do vi eble simple bezonas aldoni deklaro, ke se la buklo elirojn tiam vi devos esti en la fino de la listo, en kiu punkto vin povas simple enŝovi ĝin. JASON Hirschhorn: Mi ŝatas tiun. Tio faras sencon. Se la buklo eliroj - ĉar ĝi revenos falsaj tie. Do se la buklo elirojn, tiam ni estas ĉe la finon de la listo, aŭ eble la komenci de listo, se estas nenio en tio, kio estas la sama kiel la fino. Do nun ni volas enmeti ion tie. Do kiel tiu kodo rigardu, Marcus? Spektantaro: Se vi jam havas la nodo malloced, vi povus simple diri new_node-> apud egalas nula ĉar ĝi devas esti ĉe la fino. Aŭ new_node-> apud egalas nula. JASON Hirschhorn: okej. Pardonon. New_node-> apud egalas nula ĉar ni estas ĉe la fino. Tio ne metu it in Kiel oni metis gxin en la listo? Ĝuste. Tio estas nur opcio tio egala al. Neniu kiel do ni efektive metu gxin en la listo? Kio montrante la fino de la listo? Spektantaro: Kapo. JASON Hirschhorn: Pardonu? Spektantaro: Kapo notas al la fino de la listo. JASON Hirschhorn: Se nenio estas en la listo, kapo indikante la fino de la listo. Do tio devos labori por la unua inserción. Kio pri se estas paro aĵoj en la listo? Ol ni ne volas agordi estras egalas new_node. Kion ni volas fari tie? Jes? Probable antaŭa. Ĉu tio funkcias? Memoru ke antaŭa estas ĝuste puntero al nodo. Kaj antaŭaj estas loka variablo. Do tiun linion starigos lokan variablon, antaŭa, egala al aŭ montrante al tiu nova nodo. Tio ne vere metis ĝin en nia listo, kvankam. Kiel oni metis gxin en nia listo? Akchar? Spektantaro: Mi opinias, ke vi fari nuna-> proksima. JASON Hirschhorn: okej. curr-> proksima. Do denove, la nura kialo ni malsupren ĉi tie estas, kion faras aktualan egala? Spektantaro: Egalas nula. JASON Hirschhorn: Kaj do, kion okazas se ni faru nula-> poste? Kion ni tuj ricevas? Ni ricevos segmentación kulpo. Spektantaro: Do ​​curr egalas nula. JASON Hirschhorn: Tio estas la sama aĵo kiel prev, kvankam, ĉar estas loka variablo ni opcio egala al tiu nova nodo. Ni reiru al nia bildo de enmeto de io. Diru ni enmeto fine el la listo, do ĝuste ĉi tie. Ni havas aktualan montrilon tio indikante nula kaj antaŭa punkto tio estas indikante 8. Do, kion ni bezonas ĝisdatigi, Avi? Spektantaro: Antaŭa-> poste? JASON Hirschhorn: Antaŭa-> proksima estas kion ni volas ĝisdatigi ĉar tio efektive enŝovu ĝin ĉe la finon de la listo. Ni havas ankoraŭ unu cimon, tamen, ke ni tuj kolizias. Kio estas tio cimon? Jes? Spektantaro: Oni tuj revenos malvera en tiu kazo? JASON Hirschhorn: Ho, ĉu estas tuj revenos falsaj. Sed estas alia besteto. Do ni bezonas meti en reveno vera. Spektantaro: Ĉu antaŭa ankoraŭ egalaj nula ĉe la supro de la listo? JASON Hirschhorn: Do antaŭa ankoraŭ egalas nula ĉe la komenco. Do kiel ni akiros pli ol tio? Jes? Spektantaro: Mi opinias ke vi povas fari ĉekon antaŭ la tempo buklo vidi se ĝi estas malplena listo. JASON Hirschhorn: okej. Do ni iru tien. Ĉu ĉekon. Se - Spektantaro: Do, se la kapo egalas egalas nula. JASON Hirschhorn: Se kapo egalas egalas nula - kiuj diros al ni se ĝi estas malplena listo. Spektantaro: Kaj tiam vi fari kapo egalas nova. JASON Hirschhorn: Kapo egalas new_node? Kaj kion ajn ni bezonas fari? Spektantaro: Kaj tiam vi revenos vera. JASON Hirschhorn: Ne tute. Ni mankas unu paŝo. Spektantaro: New_node apud havas atentigi al nula. JASON Hirschhorn: Ekzakte, Alden. Kaj tiam ni povas reveni vera. OK. Sed estas ankoraŭ bona ideo por fari tion fine de la listo, ĉu ne? Ĉiuj pravas. Ni ankoraŭ povus reale preni al la fino de la listo. Tia estas tiu kodo delikata se ni estas ĉe la fino de la listo kaj tie estas kelkaj aĵoj en la listo? Ĝuste? Ĉar ni ankoraŭ havas Marcus ideo. Ni povus eliri ĉi buklo ĉar ni estas ĉe la fino de la listo. Do cxu ni tamen volas ĉi kodigi suben ĉi tien? Spektantaro: Jes. JASON Hirschhorn: Jes. Kaj kion ni bezonas por ŝanĝi ĉi tion al? Vera. Ĉu tiu sono bonaj al ĉiuj, ĝis nun? Iu ajn havas ajnan - Avi, ĉu vi havas ion por aldoni? Spektantaro: N-ro JASON Hirschhorn: okej. Do ni jam faris kelkajn ŝanĝojn. Ni faris ĉi ĉekon antaŭ ol ni eniris por malplena listo. Do ni jam prizorgita malplenan liston. Kaj tie ni zorgis pri enmeto de ion fine de la listo. Do ĝi ŝajnas kiel ĉi tio dum buklo preno prizorgi aferojn en inter: ie en la listo, se tie Estas aferoj en la listo. OK. Ni kuros ĉi programo denove. Ne sukcesas. Spektantaro: Vi ne faris ĝin. JASON Hirschhorn: Oh, Mi ne faris ĝin. Bona punkto, Michael. Ni aldonu make ligitaj. Linio 87 tie estas eraro. Linio 87. Alden, tiu estis la linio vi donis al mi. Kio okazas? Spektantaro: Ĝi devas esti nula. JASON Hirschhorn: Bonege. Ekzakte pravas. Ĝi devus esti nula. Ni faru denove. Kompili. OK. Ni enmetu tri. La insert sukcesis. Ni presas gxin. Ho, se nur ni povus kontroli. Sed ni ne faris la presi funkcio ankoraŭ. Ni eniros ion alian. Kion ni eniri? Spektantaro: Sep. JASON Hirschhorn: Sep? Spektantaro: Jes. JASON Hirschhorn: Ni havas seg kulpo. Do ni havas unu, sed ni klare ne povas akiri du. Ĝi estas 5:07. Do ni povus elpurigi ĉi por tri minutoj. Sed mi tuj forlasos nin ĉi tie kaj pluiru al hash tabloj. Sed denove, la respondoj por tiu kodo Mi retposxtu gxin al vi en iom. Ni estas tre proksime al ĝi. Mi tre kuraĝigas vin elkompreni kio okazas ĉi tie kaj korektu ĝin. Do mi devos retmesaĝi al vi tiun kodon kiel bone plus la solvo - probable la solvo poste. Unue tiu kodo. La alia afero, kiun mi volas fari antaŭ ol ni fino estas ni ne liberigis nenion. Do mi volas montri al vi, kion Valgrind aspektas. Se ni kuras Valgrind landlimoj en nia programo,. / ligitaj. Denove, laŭ ĉi tiu diapozitivo, ni devus kuri Valgrind kun iu tipo de eblo, en tiu kazo - Liko-ĉeko = plena. Do ni skribu Valgrind - Liko-ĉeko = plena. Do tiu kuros Valgrind en nia programo. Kaj nun la programo efektive funkcias. Do ni tuj kuri ĝin nur kiel antaŭe, metis ion in Mi tuj metos en tri. Tio funkcias. Mi ne tuj provi meti en ion alie ĉar ni tuj akiri seg malvera en tiu kazo. Do mi simple tuj rezignis. Kaj nun vi vidos ĉi tie filtri kaj amason resumon. Tiuj estas la bonajn aferojn, kiujn vi volas kontroli. Do la havaĵon resumo - ĝi diras, en uzo ĉe eliro - ok bitokoj en unu bloko. Tiu bloko estas la nodo ni malloced. Michael, vi diris antaŭ nodo estas ok pikoj ĉar ĝi havas la entjero kaj la montrilo. Do jen nia nodo. Kaj tiam ĝi diras, ke ni uzis malloc sep fojojn, kaj ni liberigitaj io ses fojojn. Sed ni neniam nomis libera, do mi ne havas ideo, kio estas tiu parolas pri. Sed sufiĉas diri ke kiam via programo kuras, malloc estas nomata en kelkaj aliaj lokoj, ke ni ne bezonas zorgi pri. Do malloc probable nomata en kelkaj lokoj. Ni ne bezonas zorgi kie. Sed tio estas vere nin. Tiu unua linio estas ni. Ni lasis ke bloko. Kaj vi povas vidi, ke tie en la liko resumon. Ankoraŭ atingebla - ok bitokoj en unu bloko. Tio signifas, ke memoro - ni filtris ke memoro. Definitive perdita - io estas perdita por ĉiam. Ĝenerale, oni ne faros vidi ion tie. Ankoraŭ atingebla estas ĝenerale kie vi vidos tion, kie vi volas rigardi por vidi kion kodo devus vin liberigis sed vi forgesis liberigi. Kaj tiam se tiu ne estis la kazo, se ni agis liberaj ĉio, ni povas kontroli tion. Ni nur ruli la programon ne metante en nenion. Vi vidos cxi tie malsupre en uzo ĉe eliro - nulo bitokoj en nulo blokoj. Tio signifas ke ni havis nenion lasis kiam tiu programo ĝi eliris. Do antaŭ ol sin en pset6, kuri Valgrind kaj certigi vin ne devas neniu memoro filtras en via programo. Se vi havas demandojn kun Valgrind, bonvolu atingi eksteren. Sed ĉi tiu estas kiel vi uzas ĝin. Tre simpla - vidu, se vi havas en uzo ĉe eliro - neniu bitokoj en ajna blokoj. Do ni laboris sur insert nodo. Mi havis du aliajn funkciojn tie - presi nodoj kaj libera nodoj. Denove, tiuj estas funkcioj, kiuj estas tuj estos bona por vi por ekzerci ĉar ili helpos vin ne nur kun tiuj specimeno ekzercoj sed ankaŭ sur la problemo metita. Ili mapi je belaj mallarĝe aferoj vi tuj devas fari en la problemo metita. Sed mi volas certigi ni tuŝas al ĉio. Kaj hash tabloj estas ankaŭ grava por kion ni faras en sekcio ĉi semajno - aŭ en la problemo aro. Do ni iras fini la sekcio parolante pri hash tabloj. Se vi rimarkos mi faris iom hash tablo. Tio ne estas kio ni parolas pri, tamen. Ni parolas pri malsamaj tipo de hash tabloj. Kaj en sia kerno, kradon tablo estas nenio pli ol tabelo plus hash funkcio. Ni tuj parolos por iom simple certigi ĉiuj komprenas kia krada funkcio estas. Kaj mi diras al vi nun, ke ĝi estas nenio pli ol du aferoj - tabelo kaj hash funkcio. Kaj jen estas la paŝoj tra kion tio funkcias. Estas nia tabelo. Tie estas nia funkcio. En aparta, kradaj funkcioj bezonas fari kelkajn aferojn kun tiu. Mi iras por paroli specifically pri tiu problemo metita. Ĝi estas verŝajne tuj preni en ĉeno. Kaj kio ĝi tuj revenos? Kio datumtipo? Alden? Viaj hash funkcio reveni? Entjero. Do tio estas kion la hash tablo konsistas - tablon en la formo de tabelo kaj hash funkcio. Kiel ĝi funkcias? Ĝi funkcias en tri ŝtupoj. Ni donu al ĝi ŝlosilo. En ĉi tiu kazo, ni donos al gxi ĉenon. Ni nomas la krada funkcio po paŝo unu sur la ŝlosilon kaj ni preni valoron. Specife, ni diros, ni preni entjero. Ke entjero, estas tre specifa limoj por kion tio entjero povas esti. En ĉi tiu ekzemplo, niaj tabelo estas de amplekso tri. Do kio nombroj povas ke entjero estu. Kio estas la gamo de validaj valoroj por ke entjero, la reveno tipo de ĉi tiu hash funkcio? Nulo, unu kaj du. La punkto de la krada funkcio estas eltrovi la lokon en la tabelo kie nia ŝlosilo tuj. Estas nur tri eblaj lokoj tie - nulo, unu, aŭ du. Do tiu funkcio bonan revenon nulo, unu, aŭ du. Kelkaj valida indice en ĉi tiu tabelo. Kaj tiam depende kie denove, vi povas vidi tie tabelo malfermita heligas la valoro. Tie estas kie ni metas la ŝlosilon. Do ni ĵetu en la kukurbo, ni eliru nulo. Ĉe tabelo krampo 0, ni metis kukurbo. Ni ĵetu en katoj, ni eliru tiu. Ni metis katon je unu. Ni metis en araneo. Ni eliros du. Ni metis araneo at tabelo krampo du. Estus tiel bela, se laboris kiel tio. Sed bedaŭrinde, kiel ni vidos, ĝi estas iom pli komplika. Antaŭ ni alvenos tien, ajna demandoj pri tiu baza preparo de hash tablo? Tiu estas bildo de akurate kion ni metis sur la tabulo. Sed ĉar ni tiris ĝin sur la tabulo, mi Ne tuj eniru en lin plu. Esence klavoj, la magio de nigra skatolo - aŭ en tiu kazo, kreko skatolo - de hash funkcio metas ilin en rubujoj. Kaj en ĉi tiu ekzemplo ni estas ne meti la nomon. Ni metas la asociita telefono numeron de la nomo en la rubujon. Sed vi povus tre bone nur metu la nomon en la rubujon. Tiu estas nur bildo de kio Ni tiris sur la tabulo. Ni havas potencialon kaptiloj, kvankam. Kaj ekzistas du en aparta diapozitiva, kiun mi volas iri super. La unua estas proksimume kradon funkcio. Do mi demandis al la demando, kion faras bonan hash funkcio? Mi donas du respondojn. La unua estas, ke ĝi estas determina. En la kunteksto de kradaj funkcioj, kion tio signifas? Jes? Spektantaro: Ĝi povas trovi la indekso en konstanta tempo? JASON Hirschhorn: Tio ne estas kion tio signifas. Sed tio estas bona diveno. Iu ajn havas diveno kion tio signifas? Ke bona hash funkcio estas determinisma? Annie? Spektantaro: Tio kerna nur povas esti mapita unu lokon en la hash tablo. JASON Hirschhorn: Tio estas ĝuste. Ĉiufoje vi metis en la kukurbo, ĝi ĉiam revenas nulo. Se vi metas en kukurbon kaj via hash funkcio liveras nulon sed havas probablo de redoni ion alie granda ol nulo - do eble ĝi povos reveni unu foje aux du aliajn fojojn - ke ne estas bona hash funkcio. Vi estas ekzakte pravas. Viaj hash funkcio devus redoni la sama ĝusta entjero, en ĉi tiu kazo, la sama ĝusta kordo. Eble li revenas al la sama ĝusta entjero cxar la sama ĝusta kordo sendepende de la majuskloj. Sed en tiu kazo ĝi estas ankoraŭ determinisma ĉar multnombraj aferoj estas mapita sur la saman valoron. Tio estas bone. Tiel longe kiel ekzistas nur unu eligo por donita enigo. OK. La dua afero estas, ke gxi Revenas valida indeksoj. Ni alportis tion antaŭe. Ĉi hash funkcio - Ho knabo - kradon funkcio devus revenu valida indeksoj. Do diru - ni reiru al ĉi tiu ekzemplo. Mia hash funkcio rakontas supren la literoj en la vorto. Tio estas la krada funkcio. Kaj redonas ke entjero. Do, se mi havas la vorton A, ĝi estas tuj revenos unu. Kaj ĝi tuj metis ĉi tie. Kio se mi metis en la vorto batilo? Ĝi tuj reveni tri. Kie bat iri? Ĝi ne taŭgas. Sed tio bezonas iri ien. Tiu estas mia hash tablo post ĉiu, kaj ĉiu bezonas por iri ien. Do kie devus bat iri? Ajna pensojn? Divenas? Bonan divenoj? Spektantaro: Nulo. JASON Hirschhorn: Kial nulo? Spektantaro: Pro tri module tri estas nulo? JASON Hirschhorn: Tri module tri estas nulo. Tio estas granda diveno, kaj tio estas korekta. Do, en tiu kazo ĝi devus probable iros je nulo. Do bonan manieron por certigi, ke tiu hash funkcio nur revenas valida indeksoj estas al module gxin per la grandeco de la tablo. Se vi module ajn ĉi revenas per tri, ke vi ĉiam tuj akiri iu inter nulo, unu, du. Kaj se tiu ĉiam revenas sep, kaj vi ĉiam module per tri, vi estas ĉiam tuj akiri la saman aferon. Do estas ankoraŭ determinisma se vi module. Sed tio certigos ke vi neniam ricevas ion - nevalidan industrio. Ĝenerale, tio module devus okazi en via hash funkcio. Do vi ne bezonas zorgi pri tio. Vi nur povas certigi ke tio estas valida indice. Demandojn pri tiu potenciala kaptilo? OK. Kaj tie ni iru. Sekva potencialo kaptilo, kaj tio estas la granda. Kio se du klavoj mapo al la sama valoro? Do estas du manieroj manipuli ĉi. La unua nomiĝas lineara sondado, kiu mi estas Ne tuj iros super. Sed vi devus koni lin kiu funkcias kaj kio tio estas. La duan mi tuj iros super ĉar kiu estas, ke multaj popolo versxajne finos decidi uzi en siaj problemo aro. Kompreneble, vi ne devas. Sed por la problemo aro, multaj homoj inklinas elekti krei hash tablo kun apartaj sinsekvon apliki ilia vortaro. Do ni tuj iru super kio signifas krei hash tablo kun apartan sinsekvon. Do mi metis en la kukurbo. Ĝi redonas nulo. Kaj mi metis kukurbo tie. Tiam mi metis en - kio estas alia Halloween-temática afero? Spektantaro: Candy. JASON Hirschhorn: Frandaĵo! Tio estas granda. Mi metis en candy, kaj dolĉaj ankaŭ donas al mi nulo. Kion mi faros? Ajna ideoj? Ĉar vi ĉiuj ia scias kio apartaj sinsekvon estas. Do ĉiu ideojn kion fari? Jes. Spektantaro: Meti la kordo fakte en la hash tablo. JASON Hirschhorn: Do ni tuj desegni la bona ideo tie. OK. Spektantaro: Cxu la hashtable [Inaudibles] la montrilon kiu notas al la komencon de listo. Kaj poste mi kukurbon esti la unua valoro en tiu ligillisto kaj dolĉaĵoj esti La dua valoro en tiu ligillisto. JASON Hirschhorn: okej. Marcus, kiu estis elstaraj. Mi iras al rompi ke malsupren. Marcus estas diranta ne anstataŭigi kukurbo. Tio estus malbona. Ne skribu dolĉaĵoj aliloke. Ni tuj metis ilin ambaŭ en nulo. Sed ni tuj pritrakti metante ilin al nulo por kreante listo je nulo. Kaj ni tuj krei liston de ĉion mapita al nulo. Kaj la plej bona maniero ni lernis krei lerta kiu povas kreski kaj retiri dinamike ne estas ene alia tabelo. Do ne estas mult-dimensia tabelo. Sed por ĝuste krei ligillisto. Do, kion li proponis - Mi iros por ricevi novan - estas krei tabelon kun indikoj, tabelo de montriloj. OK. Ĉiu ideo aŭ aludo kion la tipo de tiu pointers devus esti? Marcus? Spektantaro: Pointers al - JASON Hirschhorn: Ĉar vi diris ligillisto, do - Spektantaro: Nodo pointers? JASON Hirschhorn: Nodo montriloj. Se la aferoj en nia ligita listo estas nodoj tiam ili devus esti nodo montriloj. Kaj kion ili egalos komence? Spektantaro: Nula. JASON Hirschhorn: Nula. Do tie estas niaj malplenaj afero. Kukurbo revenas nulo. Kion ni faru? Iradu min tra gxi? Reale, Marcus jam donis al mi. Iu ajn promeni min tra ĝi. Kion ni faros kiam ni - ĉi aspektas tre simila al kion ni ĵus faris. Avi. Spektantaro: Mi iras preni diveno. Do, kiam vi ricevas dolĉaĵoj. JASON Hirschhorn: Jes. Nu, ni akiris kukurbo. Ni prenu nian unuan. Ni akiris kukurbo. Spektantaro: okej. Kukurbo revenas nulo. Do vi metis ŝin en tio. Aŭ fakte, vi metis ĝin en la ligillisto. JASON Hirschhorn: Kiel ni metu gxin en la ligillisto? Spektantaro: Ho, la efektiva sintakso? JASON Hirschhorn: Nur marŝi - diri pli. Kion ni faru? Spektantaro: Vi simple enŝovi ĝin kiel la unua nodo. JASON Hirschhorn: okej. Do ni havas nian nodo, kukurbo. Kaj nun kiel mi enŝovu ĝin? Spektantaro: Vi asigni ĝin al la montrilo. JASON Hirschhorn: Kiujn montrilo? Spektantaro: La montrilon je nulo. JASON Hirschhorn: Do kie faras ĉi punkto? Spektantaro: Por Nula ĝuste nun. JASON Hirschhorn: Nu, ĝi estas indikante nula. Sed mi metas en kukurbo. Do kie devus gxi notas? Spektantaro: Por Pumpkin. JASON Hirschhorn: Por kukurbo. Ekzakte. Do tiu notas al kukurbo. Kaj kie faras ĉi montrilo kukurbajn punkto? Al Spektantaro: Nula. JASON Hirschhorn: Por nula. Ekzakte. Do ni simple enmetitaj ion en la ligillisto. Ni nur skribis tiun kodon por fari tion. Preskaŭ ni preskaŭ havas ĝin tute krakis. Nun ni enŝovu dolĉaĵoj. Nia dolĉaĵoj ankaŭ iras al nulo. Do kion ni faru kun dolĉaĵoj? Spektantaro: Ĝi dependas de ĉu aŭ Ne ni provas ordigi ĝin. JASON Hirschhorn: Tio estas ĝuste. Ĝi dependas de ĉu ĉu ne ni provas ordigi ĝin. Ni supozu ke ni ne tuj ordigi ĝin. Spektantaro: Nu do, kiel ni diskutis antaŭe, ĝi estas simpla simple meti ĝin ĝuste en la komenco tiel la montrilo de nulo poentojn al bombono. JASON Hirschhorn: okej. Atendu. Permesu al mi krei dolĉaĵoj ĝuste ĉi tie. Do tiu montrilo - Spektantaro: Jes, devus nun esti indikante dolĉaĵoj. Tiam ektimis la montrilon de karamelo punkto kukurbo. JASON Hirschhorn: Kiel tio? Kaj diras, ke ni havas la alian afero por mapi al nulo? Spektantaro: Nu, vi nur fari la samon? JASON Hirschhorn: Faru la samon. Do, en tiu kazo, se ni ne volas fari gxin ordo ĝi sonas sufiĉe simpla. Ni prenu la montrilon en la indice donita per nia hash funkcio. Ni havas tiun punkton al niaj novaj nodo. Kaj tiam tiu, kiu estis montrante al la antaŭe - en ĉi tiu kazo nula, en la dua kazo kukurbo - ke, kio ajn ĝi estas montrante antaŭe, ni aldonas al la sekva de nia nova nodo. Ni enmeto ion en la komenco. Fakte tio estas multe pli simpla ol provante konservi la listo ordo. Sed denove, serĉo estos pli komplika ĉi tie. Ni ĉiam devas iri al la fino. OK. Demandojn pri apartaj sinsekvon? Kiel tio funkcias? Bonvolu peti ilin nun. Mi vere volas certigi vin ĉiujn kompreni tion antaŭ ol ni estrus eksteren. Spektantaro: Kial vi metis kukurbo kaj dolĉaĵoj en la sama parton de la hash tablo? JASON Hirschhorn: Bona demando. Kial ni metis ilin en la sama parton de la hash tablo? Nu, en tiu kazo, nia hash funkcio revenoj nulo por ambaux. Do ili bezonas iri ĉe indice nulo ĉar tio estas kie ni iras al serĉi ilin, se ni iam volas rigardi ilin. Denove kun lineara sondado alproksimiĝo ni ne metis ilin ambaŭ en nulo. Sed en la aparta ĉeno alproksimiĝo, Ni tuj metis ilin ambaŭ en nulo kaj tiam krei lerta for de nulo. Kaj ni ne volas anstataŭigi kukurbo simple por ke ĉar tiam ni supozi ke kukurbo estis neniam enmetitaj. Se ni simple subteni unu afero en la situo tio estus malbona. Tiam ne estus Ebla ni iam - se ni iam havis duplikato, tiam ni estus simple viŝos nia komenca valoro. Do jen kial ni faros ĉi alproksimiĝo. Aŭ tio estas kial ni elektis - sed denove, ni elektis la apartajn sinsekvon alproksimiĝo, kio estas multaj aliaj aliroj oni povus elekti. Ĉu tio respondas vian demandon? OK. Karolo. Linearaj sondado implicus - se ni trovis kolizio je nulo, ni aspektus en la venonta loko por vidi se Ĝi estis malfermita kaj metis ĝin tie. Kaj poste ni rigardas en la sekvanta sporto kaj rigardu, cxu tio estis malfermita kaj metis ĝin tie. Do ni trovu la sekvantan havebla malfermita loko kaj metis ĝin tie. Ajna alia demandojn? Jes, Avi. Spektantaro: Kiel sekvi supren al tiu, Kion vi celas per proksima loko? En la hash tablo aŭ en ligillisto. JASON Hirschhorn: Por linearaj programado, ne ligita listoj. La sekva makulo sur la hash tablo. Spektantaro: okej. Do la hash tablo estus pravalorizita al la grandeco - kiel la nombro de kordoj ke vi estis enmeto? JASON Hirschhorn: Vi havus volas ke ĝi estu vere granda. Jes. Ĉi tie estas bildo pri kio ni ĝuste surtiris la tabulo. Denove, ni havas kolizio ĝuste ĉi tie. ĉe 152. Kaj vi vidos ni kreis a ligillisto ekstere de ĝi. Denove, la hash tablo apartajn sinsekvon alproksimiĝo ne estas tiu kiun vi devas preni por problemojn starigis ses sed estas tiu kiu multe lernantoj emas preni. Do en tiu noto, ni diskutu mallonge antaŭ ol ni estrus ekstere pri problemo ses, kaj tiam mi dividas historion kun vi. Ni havas tri minutoj. Problemo starigis ses. Vi havas kvar funkcioj - ŝarĝo, kontrolu, grandeco, kaj malŝarĝi. Ŝarĝi - bone, ni estis irante super ŝarĝo gxuste nun. Ni tiris ŝarĝon sur la tabulo. Kaj ni eĉ komencis kodigo multan enmeto en ligillisto. Do ŝarĝo estas ne multe pli ol kion ni ĵus estis farante. Ĉeko estas iam vi havos io ŝarĝita. Ĝi estas la sama procezo kiel ĉi tio. La samaj du unuaj partoj kie throw io en la krada funkcio kaj akiri ĝian valoron. Sed nun ni ne enmeto ĝi. Nun ni serĉas ĝin. Mi specimeno kodo verkita por trovi io en ligillisto. Mi rekomendas al vi ekzerci tion. Sed intuicie trovante iun bela simila al la enmeto de io. Ja, ni desegnis bildon de trovo io en ligillisto, movante tra ĝis vi atingis la finon. Kaj se vi atingis la finon kaj ne povis trovu ĝin, ĉar ĝi ne estas tie. Do jen ĉekon, esence. Sekva estas grandeco. Ni skip grandeco. Finfine vi malŝarĝi. Malŝarĝi estas unu ni jam ne eltiris sur la tabulo aŭ coded ankoraŭ. Sed mi kuraĝigas vin provi kodigo ĝi en nia specimeno ligillisto ekzemplo. Sed malŝarĝi intuicie Estas simila al libera - aŭ mi volas diri estas simila por kontroli. Krom nun ĉiu tempo vi iras tra, vi ne simple kontrolanta al rigardu, cxu vi havas viajn valoron tie. Sed vi estas preni tiun nodon kaj liberigante ĝin, esence. Tio estas kion malŝarĝas petas vin fari. Senpaga ĉio vi malloced. Do vi iras tra la tuta listo denove, irante tra la tuta hash tablo denove. Tiu tempo ne kontrolu por vidi kio estas tie. Nur liberigi kio estas tie. Kaj fine grandeco. Grandeco devus esti efektivigita. Se vi ne havas grandecon - Mi tion diri ĝi kiel ĉi tio. Se vi ne havas grandecon en akurate unu linio de kodo inkludante la revenu deklaro, vi estas faranta grandeco malĝuste. Do certigu grandeco, por plena dezajno punktoj, vi faras gxin en akurate unu linio de kodo, inkludante la reveno komunikaĵo. Kaj ne paki ankoraux, Akchar. Avida kastoro. Mi volis diri dankon infanoj por veni al sekcio. Havas Happy Halloween. Tiu estas mia kostumo. Mi estos surhavas ĉi ĵaŭde se mi vidas vin ĉe oficejo horoj. Kaj se vi estas scivolema pri kelkaj pli fono kiel al ĉi kostumo, senti libera por kontroli 2011 sekcio por historio pri kial mi estas portante la kukurbo kostumo. Kaj tio estas malgaja rakonto. Do certigi vin havas iuj histoj apude. Sed pri tio, se vi havas ajnan demandojn mi algluita ĉirkaŭe eksteren post sekcio. Bonan sorton sur problemo starigis ses. Kaj kiel ĉiam, se vi havas ajnan demandojn, lasu min scii.