JASON HIRSCHHORN: Mirë se vini të gjithë në seksionin e Shtatë. Ne jemi në javën e shtatë të kursit. Dhe këtë të enjte ardhshme Halloween është kështu që unë jam veshur si një kungull. Unë nuk mund të përkulem dhe vënë në këpucët e mia, kështu që kjo është arsyeja pse unë jam i vetëm veshur çorape. Unë jam gjithashtu nuk veshur asgjë nën këtë, kështu që unë nuk mund të marrë atë nëse është e vëmendjen për ju. Unë kërkoj falje paraprakisht për këtë. Ju nuk keni nevojë të imagjinohet çfarë po ndodh. Unë jam veshur boxers. Pra, kjo është e gjitha e mirë. 

Unë kam një histori më të gjatë në lidhje me pse unë jam veshur si një kungull, por unë jam duke shkuar për të shpëtuar atë për më vonë në këtë seksion sepse unë dua të të marrë filluar. Ne kemi shumë gjëra të mrekullueshme për të shkuar mbi këtë jave. Shumica e tyre kanë të bëjnë direkt me këtë set jave problemi, misspellings. Ne jemi duke shkuar për të do mbi të lidhura Listat dhe tavolina hash për tërë pjesës. I vënë këtë listë deri çdo javë, një listë të burimeve për ju për t'ju ndihmuar me Materiali në këtë kurs. Në qoftë se në një humbje ose në qoftë se duke kërkuar për disa më shumë informacion, shikoni një nga këto burime. 

Përsëri, pset6 është misspellings, pset kësaj jave. Dhe gjithashtu ju inkurajon, dhe unë ju inkurajojmë, të përdorin disa të tjera Burimet posaçërisht për këtë pset. Në veçanti, unë kam tre të listuara deri në ekran - gdb, të cilat ne kemi qenë të njohur me dhe qenë duke përdorur për një kohë tani, është do të jetë shumë e dobishme këtë javë. Kështu që unë vendosur se deri këtu. Por sa herë që ju jeni duke punuar me C, ju duhet të jetë duke përdorur gdb për të korrigjoj programet tuaja. Këtë javë edhe valgrind. A e dini se çfarë valgrind bën? 

Audienca: Ajo kontrollon për rrjedhjet e kujtesës? 

JASON HIRSCHHORN: Valgrind kontrolle për rrjedhjet e kujtesës. Pra, nëse ju diçka malloc në tuaj program, ju jeni duke kërkuar për kujtesën. Në fund të programit tuaj, ju keni për të shkruar të lirë në çdo gjë që ju keni malloced për të dhënë e kujtesës prapa. Nëse ju nuk shkruani lirë në fund dhe programi juaj vjen në një përfundim, çdo gjë do të automatikisht të lirohen. Dhe për programe të vogla, është e një punë e jo se e madhe. Por në qoftë se ju jeni duke shkruar një running më të gjatë program që nuk e lë, domosdoshmërisht, në disa minuta ose a disa sekonda, pastaj memorie rrjedhjet mund të bëhet një marrëveshje e madhe. 

Pra për pset6, pritet që ju do të keni zero rrjedhjet e kujtesës me programi juaj. Për të kontrolluar për rrjedhjet e kujtesës, valgrind drejtuar dhe kjo do të ju jap disa të bukur Prodhimi lejuar të dinë nëse apo jo çdo gjë ishte e lirë. Ne do të praktikë me të më vonë sot, me shpresë. 

Së fundi, komanda ndrysh. Keni përdorur diçka të ngjashme me të në pset5 me mjet përgjim. Lejuar ju që të shikoni brenda. Ju gjithashtu përdoret ndrysh, gjithashtu, për problemi vendosur spekulim. Por në ju lejohet të krahasoni dy fotografi. Ju mund të krahasoni fotografi bitmap dhe headers info e një zgjidhje të stafit dhe zgjidhja e juaj në pset5 nëse ju zgjodhi për të përdorur atë. Diff do të lejojë të bërë këtë, po ashtu. Ju mund të krahasoni përgjigje të saktë për Problemi i kësaj jave vendosur për përgjigjen tuaj dhe të shohim nëse ajo linjat deri ose të shihni ku gabimet janë. 

Pra, këto janë tri mjete të mira që ju duhet të përdorni për këtë javë, dhe patjetër të shikoni programin tuaj me këto tri mjete para se të kthyer atë in Përsëri, siç e kam përmendur çdo javë, nëse keni ndonjë reagime për mua - të dy pozitive dhe konstruktive - të ndjehen të lirë të shkojnë në faqen e internetit në fund të këtij rrëshqitje dhe input ajo atje. I really appreciate çdo dhe të gjitha reagimet. Dhe në qoftë se ju më jepni gjëra të veçanta që Unë mund të bëj për të përmirësuar apo që unë jam duke bërë mirë që ju do të donte mua për të të vazhdojë, unë të marrë atë në zemër dhe të vërtetë të përpiqet shumë për të dëgjuar të përshtypjet tuaja. Unë nuk mund të premtoj unë jam duke shkuar për të bërë çdo gjë, edhe pse, si veshur një kungull kostum çdo javë. 

Pra, ne do të shpenzojnë pjesën më të madhe seksioni, siç e përmenda, duke folur për Listat e lidhura dhe tavolina hash, të cilat do të jetë drejtpërdrejt e zbatueshme për Problemi vendosur këtë javë. Listat e lidhura ne do të shkoj për relativisht të shpejt sepse ne kemi shpenzuar pak të drejtë e kohës do mbi të në seksion. Dhe kështu që ne do të merrni direkt në coding probleme për listat e lidhura. Dhe pastaj në fund ne do të flasim për hash tabelat dhe se si ata të aplikojnë për këtë Problemi jave vendosur. 

Ju keni parë këtë kod para. Kjo është një struct, dhe ajo është e përcaktimit diçka që quhet një nyje të re. Dhe brenda një nyje ka një numër të plotë këtu dhe atje është një tregues për një tjetër nyje. Ne e kemi parë këtë më parë. Kjo ka ardhur për disa javë tani. Ajo kombinon pointers, të cilat ne kemi qenë duke punuar me të, dhe structs, të cilat lejojnë ne që të kombinohen dy të ndryshme gjërat në një lloj të të dhënave. 

Ka shumë në vazhdim e sipër në ekran. Por e gjithë kjo duhet të jetë relativisht njohur me ju. Në rreshtin e parë, ne deklarojë një nyje të re. Dhe pastaj brenda se nyje të re, kam vendosur integer në atë nyje njerit. Ne e shohim në linjë tjetër unë jam duke bërë një printf komandë, por unë kam grayed jashtë komandën printf sepse me të vërtetë pjesë e rëndësishme është kjo vijë këtu - new_node.n. Çfarë do të thotë dot? 

Audienca: Shko në nyje dhe vlerësuar vlerën n për të. 

JASON HIRSCHHORN: Kjo është saktësisht e drejtë. Dot do të thotë të hyrë në pjesën N i kësaj nyje të re. Kjo linjë e ardhshme bën çfarë? Michael. 

Audienca: Ajo krijon një tjetër nyje që do të tregojë për nyjen e ri. 

JASON HIRSCHHORN: Pra, kjo nuk ka të krijojë një nyje të re. Ajo krijon një çfarë? 

Audienca: Një akrep. 

JASON HIRSCHHORN: Një tregues për një nyje, siç tregohet nga kjo nyje * këtu. Pra, kjo krijon një tregues për një nyje. Dhe cila nyje është ajo duke treguar të, Michael? 

Audienca: nyja e re? 

JASON HIRSCHHORN: nyja e re. Dhe kjo është vënë atje, sepse ne kemi duke pasur parasysh atë adresën e nyjeve të reja. Dhe tani në këtë linjë ne e shohim dy mënyra të ndryshme të shprehur të njëjtën gjë. Dhe kam kërkuar të vinte në dukje se si këto dy gjëra janë të njëjta. Në rreshtin e parë, ne dereference akrep. Pra, ne do të shkojmë në nyje. Kjo është ajo që do të thotë ky yll. Ne kemi parë se më parë me pointers. Shko në atë nyje. Kjo është në kllapa. Dhe pastaj të hyrë nëpërmjet dot operatori element n e atij nyje. 

Kështu që është duke marrë sintaksë kemi pa të drejtë këtu dhe tani duke e përdorur atë me një tregues. Natyrisht, ajo merr lloj i zënë, nëse jeni të shkruar ato kllapa - se yll dhe se dot. Ajo merr pak i zënë. Pra, ne kemi disa sheqer sintaktik. Dhe kjo vijë të drejtë këtu - ptr_node-> n. Kjo e bën të njëjtën gjë e saktë. Pra, këto dy rreshta të kodit janë të barabartë dhe do të bëjë saktë të njëjtën gjë. 

Por unë doja të theksoj ato para ne shkojmë më tutje në mënyrë që ju të kuptoni që me të vërtetë kjo gjë e drejtë këtu është vetëm sheqeri sintaktik për dereferencing tregues dhe më pas do të n pjesë e atij struct. Çdo pyetje në lidhje me këtë rrëshqitje? OK. 

Pra, ne jemi duke shkuar për të shkuar nëpërmjet një çift e veprimeve që mund të bëni në Listat e lidhura. Një listë e lidhur, kujtojnë, është një seri e nyje që çojnë tek njëri tjetrin. Dhe ne në përgjithësi të fillojë me një tregues quajtur kreu, në përgjithësi, që tregon për gjëja e parë në listë. Pra, në rreshtin e parë këtu, ne duhet L tonë origjinale të parë. Kështu që gjë që ju mund të mendoni - kjo tekst të drejtë këtu ju mund të mendoni si vetëm tregues që ne kemi ruajtur se diku pika të elementit të parë. Dhe në këtë listë e lidhur ne kemi katër nyje. Çdo nyjë është një kuti e madhe. Kuti të mëdha brenda madh kuti është pjesë numër i plotë. Dhe pastaj ne kemi një pjesë pointer. 

Këto kuti nuk janë tërhequr për të shkallë sepse sa e madhe është një numër i plotë në bytes? Sa i madh tani? Katër. Dhe sa i madh është një akrep? Katër. Pra, me të vërtetë, në qoftë se ne ishim për të nxjerrë kjo në shkallë të dy kutive do të jetë të njëjtën madhësi. Në këtë rast, ne duam të futur diçka në listën e lidhur. Kështu që ju mund të shihni këtu ne jemi futur pesë Ne udhëtimin në lista e lidhur, të gjetur se ku pesë shkon, dhe pastaj futur atë. 

Le të thyejnë atë poshtë dhe të shkojnë pak më ngadalë. Unë jam duke shkuar për pikë për të bordit. Pra, ne kemi nyje tonë pesë që ne kemi krijuar në mallocs. Pse është e gjithë qesh? Just kidding. OK. Pra, ne kemi malloced pesë. Ne e kemi krijuar këtë nyje diku tjetër. Ne kemi atë gati për të shkuar. Ne të fillojë në fillim të listën tonë me dy. Dhe ne duam të futur në një mënyrë të renditura. 

Pra, nëse ne shohim dy dhe ne duam të vënë në pesë, çfarë bëjmë ne kur ne shohim diçka më pak se ne? Çfarë? Ne duam të futur pesë në këtë lista e lidhur, duke e mbajtur atë të renditura. Ne e shohim numrin dy. Pra, çfarë bëjmë ne? Marcus? 

Audienca: Telefononi në treguesin në nyjen e ardhshëm. 

JASON HIRSCHHORN: Dhe pse nuk ne do të shkojmë në një tjetër? 

Audienca: Sepse është e Nyja e ardhshme në listë. Dhe ne vetëm e di se lokali tjetër. 

JASON HIRSCHHORN: Dhe pesë është më i madh se dy, në mënyrë të veçantë. Sepse ne duam të mbajtur atë renditura. Kështu pesë është më e madhe se dy. Pra, ne të lëvizin për në një tjetër. Dhe tani arrijmë katër. Dhe çfarë ndodh kur kemi arritur katër? 

Pesë është më e madhe se sa katër. Pra, ne do të mbajë. Dhe tani ne jemi në gjashtë. Dhe çfarë shohim në gjashtë? Po, Carlos? 

AUDIENCA: gjashtë është më e madhe se pesë. 

JASON HIRSCHHORN: Gjashtë është madhe se pesë. Pra, kjo është ajo ku ne duam për të futur pesë. Megjithatë, mbani në mend se në qoftë se ne kanë vetëm një tregues këtu - ky është tregues tonë shtesë që është traversing nëpër lista. Dhe ne jemi duke treguar në gjashtë. Ne kemi humbur gjurmët e asaj vjen para gjashtë. Pra, nëse ne duam të futur diçka në kjo listë e mbajtur atë të renditura, ne ndoshta duhet se si shumë pointers? 

Audienca: Dy. 

JASON HIRSCHORN: Dy. Një për të mbajtur gjurmët e tanishme një dhe një për të mbajtur nën e mëparshmja. Kjo është vetëm një listë e lidhur në formë individuale. Ajo shkon vetëm një drejtim. Nëse do të kishte një listë e lidhur dyfish, ku çdo gjë ishte duke treguar për gjë pas saj dhe të asaj para saj, atëherë ne nuk do të duhet për të bërë këtë. Por në këtë rast ne nuk duam të humbasin gjurmët e asaj që erdhën para nesh, në rast ne kemi nevojë për të futur pesë diku në mes. Thuaj ne u futur nëntë. Çfarë do të ndodhë kur ne mori të tetë? 

Audienca: Ju do të duhet të merrni atë pikë null. Në vend të që pikë zero ju do të keni për të shtuar një element dhe më pas kanë ajo pikë në nëntë. 

JASON HIRSCHORN: Pikërisht. Pra, ne të merrni tetë. Ne arrijë në fund të listës për shkak kjo është duke treguar null. Dhe tani, në vend që të tregojnë për null kemi atë pikë në nyje tonë të ri. Dhe ne kemi vendosur në treguesin në nyje tonë të ri të null. A ka dikush ndonjë pyetje rreth futur? Çka nëse unë nuk e kujdesit për mbajtjen listën renditura? 

Audienca: Stick atë në fillim apo fund. 

JASON HIRSCHORN: Rrinë atë në fillimi apo fundi. Cili duhet të bëjmë? Bobby? Pse fundi? 

Audienca: Për shkak se në fillim është e mbushur tashmë. 

JASON HIRSCHORN: OK. Fillimi është e mbushur tashmë. Kush dëshiron të argumentojnë kundër Bobby. Marcus. 

Audienca: E pra ju ndoshta dëshironi të ngjit atë në fillim, sepse përndryshe nëse ju vënë atë në në fund ju do të keni për të kaloj nëpër gjithë listën. 

JASON HIRSCHORN: Pikërisht. Pra, nëse ne jemi duke menduar për kohën e duhur, duhur të futur në fund do të ishte n, madhësia e kësaj. Çfarë është O runtime i madh i futur në fillim? Koha konstante. Pra, nëse ju nuk bëni kujdes për mbajtjen e diçka të renditura, shumë më mirë për të vetëm futur në fillim të kësaj liste. Dhe kjo mund të bëhet në kohë të vazhdueshme. 

OK. Operacion tjetër është gjetur, të cilat të tjera - ne kemi formuluar këtë si kërkim. Por ne jemi duke shkuar për të parë përmes lista e lidhur për ndonjë objekt. Ju djema keni parë kodin për kërkoni para në leksion. Por ne lloj vetëm e bëri atë me insert, ose të paktën futur diçka e renditura. Ju shikoni përmes, duke shkuar nga nyje nyje, deri sa ju të gjeni numrin që ju jeni kërkoni. Çfarë ndodh nëse keni arritur në fund të listës? Thuaj Po kërkoj për nëntë dhe unë arritur në fund të listës. Çfarë bëjmë ne? 

Audienca: Kthimi i rremë? 

JASON HIRSCHORN: Kthehu false. Ne nuk e gjeti atë. Nëse keni arritur në fund të listës dhe të ju nuk e gjeni numrin ju jeni kërkoni, nuk është në atje. Ndonjë pyetje në lidhje gjeni? Nëse kjo ishte një listë të renditura, çfarë do të të jenë të ndryshme për kërkimin tonë? Po. 

Audienca: Ajo do të gjeni vlerën e parë që është më e madhe se ajo e ju jeni duke kërkuar për dhe pastaj të kthimit të rreme. 

JASON HIRSCHORN: Pikërisht. Pra, nëse kjo është një listë të renditura, në qoftë se ne të merrni për të diçka që është më e madhe se ajo që ne jemi duke kërkuar për të, ne nuk kemi nevojë të mbajë në fund lista. Ne mund të në atë pikë kthimit të rreme sepse ne nuk jemi duke shkuar për të gjetur atë. Pyetja është tani, ne kemi biseduar për mbajtjen e listave të lidhura renditura, mbajtja e tyre unsorted. Kjo do të jetë diçka që ju jeni të ndoshta do të duhet të mendojnë për kur problemi coding vendosur pesë në qoftë se ju zgjidhni një tabelë hash me i veçantë chaining qasje, e cila ne do të flasim më vonë. 

Por është me vlerë që ajo të mbajë listën renditura dhe pastaj të jenë në gjendje të ketë ndoshta kërkimet më të shpejtë? Apo është më mirë për të shpejt të futur diçka në kohën e duhur të vazhdueshme, por pastaj kanë më të gjatë në kërkim? Kjo është një kompromis të drejtë atje që të ju të merrni për të vendosur se çfarë është më e përshtatshme për problemin tuaj të veçantë. Dhe nuk është domosdoshmërisht një përgjigje plotësisht të drejtë. Por kjo është me siguri një vendim që ju merrni për të bërë, dhe ndoshta e mirë për të mbrojtur që në, të themi, një koment ose dy pse ju zgjodhi një lidhje të tjera. 

Së fundi, fshirjes. Ne e kemi parë fshirjes. Është e ngjashme me kërkim. Ne i shohim për elementin. Thonë se ne jemi duke u përpjekur për të fshirë gjashtë. Pra, ne gjejmë gjashtë të drejtë këtu. Gjë që ne duhet të sigurohemi që ne bëni është që çdo gjë është duke treguar për gjashtë - si ne e shohim në hap dy poshtë këtu - çdo gjë është duke treguar gjashtë nevojave të kaloni gjashtë tani dhe të ndryshohet në çfarëdo gjashtë është duke treguar për të. Ne nuk duam të ndonjëherë jetime pjesën tjetër të listën tonë duke harruar për të vendosur se akrep mëparshme. Dhe pastaj ndonjëherë, varësisht të programit, ata vetëm do të fshini kete nyje tërësisht. Ndonjëherë ju do të duan të kthehen vlera që është në këtë nyje. Pra, kjo është se si veprat e fshirjes. Çdo pyetje për të fshirë? 

Audienca: Pra, nëse ju jeni do të fshini kjo, do të ju vetëm përdorni të lirë për shkak se me sa duket u malloced? 

JASON HIRSCHORN: Nëse ju doni për të liruar diçka që është saktësisht e drejtë dhe ju malloced atë. Thuaj kemi dashur të kthehen këtë vlerë. Ne mund të kthehemi gjashtë dhe më pas të lirë kjo nyje dhe thirrje të lirë mbi të. Ose ndoshta do të thërrasin pa i parë dhe pastaj të kthehen gjashtë. 

OK. Pra, le të shkojë përpara për të praktikuar coding. Ne jemi duke shkuar për kodin tri funksione. I pari është quajtur insert_node. Pra, ju keni kodin që unë ju emailed, dhe në qoftë se ju jeni të shikuar këtë më vonë ju mund të hyni në kodin në linked.c në faqen e internetit CS50. Por në linked.c, ka disa Kodi skelet kjo është tashmë është shkruar për ju. Dhe pastaj nuk ka funksionon çift ju duhet të shkruani. 

Së pari ne do të shkruani insert_node. Dhe çfarë bën insert_node nuk është në fut një numër të plotë. Dhe ju jeni duke i dhënë numër i plotë në listën e lidhur. Dhe në mënyrë të veçantë, ju duhet për të mbajtur listë të renditura nga më i vogli tek më i madh. Gjithashtu, ju nuk doni të futur ndonjë kopje identike. Së fundi, si ju mund të shihni insert_node kthen një bool. Pra, ju jeni duke menduar për të lejuar përdoruesit e di nëse insert ishte apo jo suksesshme duke u kthyer e vërtetë apo e rreme. Në fund të këtij programi - dhe për këtë fazë ju nuk keni nevojë të shqetësohen për çlirimin asgjë. Pra, të gjithë ju jeni bërë është duke marrë një numër të plotë dhe futur atë në një listë. 

Kjo është ajo që unë jam duke kërkuar që ju të bëni tani. Përsëri, në linked.c, të cilat ju të gjithë e kanë, është kodi skelet. Dhe ju duhet të shikoni drejt fundit Deklarata funksion mostër. Megjithatë, para se të shkojnë në coding atë në C, I highly ju inkurajojmë që të shkoni me hapat që ne kemi qenë praktikuar çdo javë. Ne kemi kaluar tashmë nëpër një foto të kësaj. Kështu që ju duhet të keni disa të kuptuarit se si kjo funksionon. Por unë do të ju inkurajojmë që të shkruaj disa pseudokod para se të zhyten in Dhe ne jemi duke shkuar për të shkuar mbi pseudokod si nje grup. Dhe pastaj një herë ju keni shkruar tuaj pseudokod, dhe një herë ne kemi shkruar tonë pseudokod si një grup, ju mund të shkojnë në coding atë në C. 

Si një kokat lart, funksioni insert_node është ndoshta trickiest e tre ne jemi duke shkuar për të shkruar, sepse unë shtuar disa kufizime të tjera për të programimit tuaj, në mënyrë të veçantë që ju nuk do të jeni për të futur çdo kopje identike dhe se lista duhet të mbetet renditura. Pra, ky është një program jo-parëndësishëm që ju duhet të kodit. Dhe pse nuk ju merrni 6:55 minuta vetëm për të punuar në pseudokod dhe kodin. Dhe pastaj ne do të fillojmë shkon si nje grup. Përsëri, në qoftë se ju keni ndonjë pyetje vetëm ngrini dorën dhe unë do të vijnë rreth. . 

Ne gjithashtu në përgjithësi të bëjë këto - ose unë nuk e them në mënyrë eksplicite të ju mund të punojnë me njerëz. Por natyrisht, I highly ju inkurajojmë, nëse keni ndonjë pyetje, për të kërkuar fqinj ulur tjetër për ju apo edhe të punojnë me dikë tjetër në qoftë se ju doni të. Kjo nuk duhet të jetë një individ Aktiviteti i heshtur. 

Le të fillojmë me shkrim disa pseudokod në bord. Kush mund të jepni rreshtin e parë të pseudokod për këtë program? Për këtë funksion, në vend - insert_node. Alden? 

Audienca: Pra, gjëja e parë që bëra ishte të krijojë një tregues të ri në nyje dhe unë initialized ajo duke treguar të njëjtën gjë gjë që lista është duke treguar për të. 

JASON HIRSCHORN: OK. Pra, ju jeni duke krijuar një tregues të ri në listë, të mos nyjen. 

Audienca: E drejta. Po. 

JASON HIRSCHORN: OK. Dhe pastaj çfarë ne duam të bëjmë? Çfarë ka të pas kësaj? Po në lidhje me nyjen? Ne nuk kemi një nyje. Ne vetëm duhet një vlerë. Në qoftë se ne duam të futur një nyje, çfarë bëjmë ne duhet të bëni të parë para se të mund edhe mendoni për të futur atë? 

Audienca: Oh, sorry. ne duhet të malloc hapësirë ​​për një nyje. 

JASON HIRSCHORN: Excellent. Le të bëjmë - OK. Nuk mund të arrijnë atë nivel të lartë. OK. Ne jemi duke shkuar për të shkuar poshtë, dhe pastaj ne jemi duke përdorur dy kolona. Unë nuk mund të shkojnë se - OK. Krijo një nyje të re. Ju mund të krijojë një tjetër tregues tek lista ose ju mund të përdorni vetëm listën si ajo ekziston. Ju nuk duhet të vërtetë për të bërë këtë. 

Pra, ne të krijojë një nyje të re. Great. Kjo është ajo që ne bëjmë së pari. Çfarë ndodh më pas? 

Audienca: Prisni. A duhet të krijojë një nyje të re tani apo duhet të presim për të siguruar që nuk ka kopje identike e nyjeve në listën para se të krijuar atë? 

JASON HIRSCHORN: Pyetje e mirë. Le të mbajë atë për më vonë për shkak se Shumica e kohës ne do të krijuar një nyje të re. Pra, ne do të vazhdojmë që këtu. Por kjo është një pyetje e mirë. Nëse ne të krijuar atë dhe të gjejmë një kopje, çfarë duhet të bëjmë para se të kthehej? 

Audienca: pa atë. 

JASON HIRSCHORN: Po. Ndoshta pa atë. OK. Çfarë bëjmë ne pas ne të krijojë një nyje të re? Annie? 

Audienca: Ne kemi vënë Numri në nyjen? 

JASON HIRSCHORN: Pikërisht. Ne kemi vënë numrin - ne malloc hapësirë. Unë jam duke shkuar për të lënë që të gjithë si një rresht. Por ju jeni të drejtë. Ne malloc hapësirë, dhe pastaj ne kemi vënë numrin in Ne edhe mund të vendosni treguesin pjesë e saj të null. Kjo është saktësisht e drejtë. Dhe pastaj çfarë lidhje pas kësaj? Ne tërhoqi kete foto në bord. Pra, çfarë bëjmë ne? 

Audienca: Ne do të shkojmë nëpër lista. 

JASON HIRSCHORN: Go nëpër lista. OK. Dhe çfarë bëjmë ne të kontrolluar për në çdo nyje. Kurt, çfarë nuk kemi kontrolluar për në çdo nyje? 

Audienca: Shih nëse vlera e n e që nyja është më e madhe se vlera n i nyjeve tonë. 

JASON HIRSCHORN: OK. Unë jam duke shkuar për të bërë - yeah, OK. Pra, kjo është n - Unë jam duke shkuar për të thënë nëse vlera është më e madhe se këtë nyje, atëherë çfarë bëjmë ne? 

Audienca: E pra, atëherë ne të futur gjëja e drejtë para se. 

JASON HIRSCHORN: OK. Pra, në qoftë se është më e madhe se kjo, atëherë ne duam të futur. Por ne duam të futur atë të drejtë para se të sepse ne gjithashtu do të duhet të jenë të regjistrimin, atëherë, i asaj që ishte më parë. Pra, para se të futur. Pra, ne ndoshta humbur diçka më herët. Ne ndoshta duhet të jetë mbajtur gjurmët e asaj që po ndodh. Por ne do të kthehemi atje. Pra, çfarë vlerë është më pak se? Kurt, çfarë bëjmë ne nëse vlerë është më pak se? 

Audienca: Pastaj ju vetëm do të mbajë përveç nëse kjo është e fundit. 

JASON HIRSCHORN: Më pëlqen kjo. Kështu që të shkojnë në nyjen e ardhshëm. Përveç nëse kjo është e fundit - ne jemi ndoshta duke kontrolluar për të cilat në kushtet e një gjendje. Por, vërtet, nyje e ardhshme. Dhe kjo është duke u shumë i ulët, kështu që ne do të lëvizin gjatë këtu. Por në qoftë se - mund ta shohin të gjithë këtë? Nëse ne jemi të barabartë, çfarë bëjmë ne? Nëse vlera që ne jemi duke u përpjekur për të futur është e barabartë me vlerën e kësaj nyje-së? Po? 

Audienca: [padëgjueshme]. 

JASON HIRSCHORN: Po. Duke pasur parasysh këtë - Marcus është e drejtë. Ne mund të ketë bërë ndoshta diçka të ndryshme. Por duke pasur parasysh se ne kemi krijuar atë, këtu ne duhet të lirë dhe pastaj të kthehen. Oh boy. A është kjo më mirë? Si është ajo? OK. Pa pagesë dhe pastaj çfarë të bëjmë ne kthehen, [e padëgjueshme]? OK. A jemi të humbur ndonjë gjë? Pra, ku jemi ne regjistrimin i nyjeve paraprak? 

Audienca: Unë mendoj se do të shkojë pas të krijojë një nyje të re. 

JASON HIRSCHORN: OK. Pra, në fillim ne do të ndoshta - po, ne mund të krijojë një tregues për një të ri nyje, si një tregues të mëparshëm nyjeve dhe të një tregues i tanishëm nyje. Pra, le të futur atë këtu. Krijo aktuale dhe të mëparshme pointers në nyje. Por kur nuk kemi të rregulluar këto pointers? Ku e bëjmë këtë në kodin? Jeff? 

Audienca: - Kushtet vlerë? 

JASON HIRSCHORN: Cili Një në veçanti? 

Audienca: Unë jam vetëm i hutuar. Nëse vlera është më e madhe se kjo nyje, nuk do të thotë kjo që ju doni të shkoni në nyjen e ardhshëm? 

JASON HIRSCHHORN: Pra, nëse vlera jonë është e madhe se vlera e kësaj nyje. 

Audienca: Po, atëherë ju do të duan të shkojnë më poshtë vijës, e drejtë? 

JASON HIRSCHHORN: E drejta. Pra, ne nuk e futur atë këtu. Nëse vlera është më pak se këtë nyje, atëherë ne do të shkojmë në nyjen e ardhshëm - ose pastaj ne futur para. 

Audienca: Prisni, cili është ky Nyja dhe cila është vlera? 

JASON HIRSCHHORN: Pyetje e mirë. Vlera për këtë përkufizim të funksionit është ajo që ne jemi duke i dhënë. Pra, vlera është numri ne jemi duke i dhënë. Kështu nëse vlera është më pak se kjo nyje, ne kemi nevojë për kohë për të futur. Nëse vlera është më e madhe se kjo nyje, ne do të shkojmë në nyjen e ardhshëm. Dhe përsëri në pyetje origjinal, pse, ku - 

Audienca: Nëse vlera është më e madhe se kjo nyje. 

JASON HIRSCHHORN: Dhe kështu çfarë bëjmë ne këtu? Sweet. Kjo është e saktë. Unë jam vetëm duke shkuar për të shkruar përditësimin pointers. Por po, me atë aktuale ju do të update it për të pikë në një tjetër. Çdo gjë tjetër ne jemi të humbur? Kështu që unë jam duke shkuar për këtë lloj kodin në gedit. Dhe, ndërsa unë bëj këtë, ju mund të ketë një çift ​​shumë minuta për të punuar në kodim kjo në C. 

Pra, unë kam të dhëna të pseudokod. Një shënim të shpejtë para se të ketë filluar. Ne nuk mund të jetë në gjendje që plotësisht përfundojë këtë në të gjitha tre prej këtyre funksioneve. Nuk ka zgjidhje të saktë për to se unë do të email nga ju djema pas nenit, dhe kjo do të të postuar në CS50.net. Kështu që unë nuk do të ju inkurajoj që të shkoni shikoni në seksionet. Unë ju inkurajoj që të provoni ato në tuaj vet, dhe pastaj të përdorin praktika Problemet për të kontrolluar përgjigjet tuaja. Këto kanë qenë të gjitha të dizajnuara për të ngushtë kanë të bëjnë dhe t'i përmbahen asaj që ju duhet të bëni në grup problemit. Kështu që unë do të ju inkurajoj për të ushtruar këtë në tuaj dhe pastaj të përdorni kodin për kontrolloni përgjigjet tuaja. Sepse unë dua të lëvizin për të përpunojnë tavolina në një pikë në seksionin. Pra, ne nuk mund të marrë me të gjitha. Por ne do të bëjmë sa më shumë që mundemi tani. 

OK. Le të fillojmë. Asam, si nuk kemi krijuar një nyje të re? 

Audienca: Ju keni struct *. 

JASON HIRSCHHORN: Pra, ne kanë se deri këtu. Oh, sorry. Ju u thënë e strukturës *. 

Audienca: Dhe pastaj [? lloj?] nyje ose c nyje. 

JASON HIRSCHHORN: OK. Unë jam duke shkuar për të thirrur atë new_node kështu që ne mund të qëndrojnë në përputhje. 

Audienca: Dhe ju doni të vendosur që në krye, nyjen e parë. 

JASON HIRSCHHORN: OK. Deri tani ky treguar për të - kështu që kjo nuk ka krijuar një nyje të re ende. Kjo është vetëm për të treguar Nyja e parë në listë. Si mund të krijoj një nyje të re? Nëse kam nevojë për hapësirë ​​për të krijuar një nyje të re. Malloc. Dhe sa e madhe? 

Audienca: Madhësia e struct. 

JASON HIRSCHHORN: Madhësia e struct. Dhe çfarë po struct quhet? 

Audienca: Nyja? 

JASON HIRSCHHORN: Nyja. Pra malloc (sizeof (nyje)); na jep hapësirë. Dhe është kjo linjë - një gjë është e gabuar në këtë linjë. A është new_node një tregues për një struct? Kjo është një emër gjenerik. Çfarë është ajo - nyje, pikërisht. Kjo është një nyje *. Dhe çfarë bëjmë ne të drejtë pas ne malloc diçka, Asan? Cila është gjëja e parë që ne bëjmë? Po në qoftë se ajo nuk punon? 

Audienca: Oh, kontrolloni nëse ajo tregon për nyjen? 

JASON HIRSCHHORN: Pikërisht. Pra, nëse ju new_node është e barabartë me të barabartëve null, çfarë bëjmë ne? Kjo kthen një bool, këtë funksion. Pikërisht. Duket e mirë. Çdo gjë për të shtuar aty? Ne do të shtuar gjëra në fund. Por kjo deri tani duket e mirë. Krijo pointers aktuale dhe të mëparshme. Michael, si mund ta bëni këtë? 

Audienca: Ju do të duhet për të bërë një nyje *. Ju do të duhet të mos bëjë një për new_node por për nyjet ne tashmë kemi. 

JASON HIRSCHHORN: OK. Pra, nyja e tanishme ne jemi në. Unë do të thërrasë atë curr. Dakord. Ne kemi vendosur që ne duam të mbajnë dy sepse ne duhet të dimë çfarë është para tij. Çfarë ata marrin niset për të? 

Audienca: Vlera e tyre në listën tonë. 

JASON HIRSCHHORN: Pra, çfarë është gjëja e parë në listën tonë? Ose, si mund ta dimë se ku fillimi i listës sonë është? 

Audienca: A nuk është kaluar në funksion? 

JASON HIRSCHHORN: E drejta. Ajo u miratua në të drejtë këtu. Pra, në qoftë se është kaluar në funksion, fillojnë të listës, çfarë duhet të kemi Grupi aktual i barabartë? 

Audienca: Lista. 

JASON HIRSCHHORN: Lista. Kjo është saktësisht e drejtë. Tani ajo ka adresën e fillimi i listës sonë. Dhe çfarë lidhje të mëparshme? 

Audienca: Lista minus një? 

JASON HIRSCHHORN: Ka asgjë para saj. Pra, çfarë mund të bëjmë për të ditur asgjë? 

Audienca: Null. 

JASON HIRSCHHORN: Po. Kjo tingëllon si një ide e mirë. Perfect. Falemnderit. Go nëpër lista. Constantine, sa kohë do të shkojmë për të shkuar nëpër lista? 

Audienca: Deri Ne arrijnë null. 

JASON HIRSCHHORN: OK. Pra, nëse, përderisa, për lak. Çfarë po bëjmë? 

Audienca: Ndoshta një për lak? 

JASON HIRSCHHORN: Le të bëjmë një për lak. OK. 

Audienca: Dhe ne themi për - deri në treguesin e tanishme nuk është e barabartë me null. 

JASON HIRSCHHORN: Pra, në qoftë se ne e dimë kusht, si mund të shkruani një lak bazuar jashtë atë gjendje. Çfarë lloj i një lak duhet të përdorim? 

Audienca: Përderisa. 

JASON HIRSCHHORN: Po. Kjo e bën shumë kuptim bazë off të asaj që ju tha. Nëse ne vetëm duan të shkojnë në ne kjo do të vetëm e di atë gjë, kjo do të bëjë kuptim për të bërë një lak, ndërsa. Ndërsa e tanishme bën null jo të barabartë, nëse vlera është më pak se këtë nyje. Akshar, më jep këtë linjë. 

Audienca: Nëse aktuale>-n n më pak se vlera. Ose të kundërt se. Switch se kllapa. 

JASON HIRSCHHORN: Na vjen keq. 

Audienca: Ndryshimi kllapa. 

JASON HIRSCHHORN: Pra, nëse është e madhe se vlera. Sepse kjo është konfuze me të komentuar më sipër, unë jam duke shkuar për të bërë këtë. Por po. Në qoftë se vlera jonë është më pak se kjo nyje, çfarë bëjmë ne? Oh. Unë kam atë të drejtë këtu. Fut para. OK. Si e bëjmë këtë? 

Audienca: A është ende e mua? 

JASON HIRSCHHORN: Po. 

Audienca: Ju - new_node-> ardhshme. 

JASON HIRSCHHORN: Pra, çfarë është që do të barabartë? 

Audienca: Ajo do të tanishëm të barabartë. 

JASON HIRSCHHORN: Pikërisht. Dhe kështu të tjera - çfarë tjetër na duhet për të rinovuar? 

Audienca: Kontrolloni në qoftë se e kaluara është e barabartë null. 

JASON HIRSCHHORN: Nëse prev - kështu që nëse prev barabartë null. 

Audienca: Kjo do të thotë se do për t'u bërë kreu. 

JASON HIRSCHHORN: Kjo do të thotë është bërë kokë. Pra, atëherë çfarë bëjmë ne? 

Audienca: Ne bëjmë kokën e barabartë new_node. 

JASON HIRSCHHORN: Shef është e barabartë me new_node. Dhe pse kreu këtu, jo lista? 

Audienca: Për shkak se koka është një globale e ndryshueshme, e cila është vendi duke filluar. 

JASON HIRSCHHORN: Sweet. OK. Dhe - 

Audienca: Pastaj ju bëni tjetër prev-> tjetër është e barabartë new_node. Dhe pastaj ju kthehen e vërtetë. 

JASON HIRSCHHORN: Ku ne kemi vendosur fundin new_node? 

Audienca: Unë do të - I vendosur që në fillim. 

JASON HIRSCHHORN: Pra, çfarë linjë? 

Audienca: Pas qoftë se deklarata kontrolluar nëse është e njohur. 

JASON HIRSCHHORN: Të drejtë këtu? 

Audienca: Unë do të bëj new_node-> n është e barabartë me vlerën. 

JASON HIRSCHHORN: Tinguj e mirë. Ndoshta kjo ka kuptim - ne nuk bëjmë duhet të dini se çfarë lista ne jemi në sepse ne jemi vetëm që kanë të bëjnë me një listë. Pra, një deklaratë më të mirë funksion për kjo është vetëm për të hequr qafe këtë tërësisht dhe vetëm futur një vlerë në kokë. Ne as nuk duhet të dini ajo lista ne jemi in Por unë do të mbajë atë tani për tani dhe pastaj të ndryshojë atë mbi përditësimin slides dhe Kodi. Kështu që duket e mirë tani për tani. Nëse vlera - që mund ta bëjë këtë linjë? Nëse - çfarë bëjmë ne këtu, Noeu. 

Audienca: Nëse vlera është më e madhe se curr-> n - 

JASON HIRSCHHORN: Si mund të ne do të shkojmë në nyjen e ardhshëm? 

Audienca: Curr-> n është barabartë me new_node. 

JASON HIRSCHHORN: Pra, n është çfarë pjesë e struct? Numër i plotë. Dhe new_node është një tregues për një nyje. Pra, çfarë pjesë e curr duhet ne update? Nëse jo n, atëherë çfarë është pjesa tjetër? Noeu, çfarë është pjesa tjetër. 

Audienca: Oh, e ardhshëm. 

JASON HIRSCHHORN: Next, saktësisht. Pikërisht. Tjetër është një e drejtë. Dhe çfarë tjetër nuk kemi nevojë për të rinovuar, Noeun? 

Audienca: Të pointers. 

JASON HIRSCHHORN: Pra, ne updated aktuale. 

Audienca: Prev-> ardhshme. 

JASON HIRSCHHORN: Po. OK, ne do të pauzë. Kush mund të na ndihmojë jashtë këtu? Manu, çfarë duhet të bëjmë? 

Audienca: Ju keni marrë për të vendosur është e barabartë tek curr-> tjeter. Por të bërë këtë para se të vijë më parë. 

JASON HIRSCHHORN: OK. Çdo gjë tjetër? Akshar. 

Audienca: Unë nuk mendoj se ju jeni për qëllim të ndryshojë curr-> ardhshme. Unë mendoj se ju jeni duke menduar për të bërë të barabartëve curr curr-> tjetër për të shkuar në nyjen e ardhshëm. 

JASON HIRSCHHORN: Pra vjen keq, ku? Në çfarë linjë? Kjo linjë? 

Audienca: Po. Bëni curr barabartë curr-> ardhshme. 

JASON HIRSCHHORN: Pra, kjo është e saktë sepse i tanishëm është një tregues për një nyje. Dhe ne duam që ajo të pikë për të ardhshëm nyje të asaj që është duke u aktualisht vuri në dukje. Vetë curr ka një tjetër. Por në qoftë se ne kemi qenë të rinovuar curr.next, ne do të jetë e informuar shënimin aktuale vetvete nuk, kur kjo akrep u treguar. Po në lidhje me këtë linjë, edhe pse. Avi? 

Audienca: Prev-> tjetër është e barabartë curr. 

JASON HIRSCHHORN: Pra, përsëri, në qoftë se prev është një tregues për një nyje, prev-> tjetër është akrep aktuale në nyje. Pra, kjo do të jetë e informuar a treguesin në një nyje të curr. Ne nuk duam të rinovuar një tregues në një nyje. Ne duam të rinovuar mëparshme. Pra, si do ta bëjmë këtë? 

Audienca: Ajo thjesht do të prev. 

JASON HIRSCHHORN: E drejta. Prev është një tregues për një nyje. Tani ne jemi duke ndryshuar atë në një tregues të re në një nyje. OK Le të lëvizin poshtë. Së fundi, ky kusht të fundit. Jeff, çfarë bëjmë ne këtu? 

Audienca: Nëse vlera është barabartë tek curr-> n. 

JASON HIRSCHHORN: Na vjen keq. Oh mirësinë time. Çfarë? Vlera == curr-> n. Çfarë bëjmë ne? 

Audienca: Ju do të liruar new_node tonë, dhe pastaj ju do të ktheheni të rreme. 

JASON HIRSCHHORN: Kjo është ajo që ne kemi shkruar deri tani. A ka dikush ndonjë gjë për të shtuar para se të bëjmë? OK. Le të provoni. Kontrolli mund të arrijnë në fund e nje funksion jo-pavlefshme. Avi, çfarë po ndodh? 

Audienca: A jeni menduar për të vënë kthimin vërtetë jashtë lak ndërsa? 

JASON HIRSCHHORN: Nuk e di. A doni më për të? 

Audienca: Mos u mërzit. Jo. 

JASON HIRSCHHORN: Akshar? 

Audienca: Unë mendoj se ju do të thotë të vënë FALSE kthimit në fund e lak ndërsa. 

JASON HIRSCHHORN: Pra, ku nuk ju duan të të shkoni? 

Audienca: Ashtu si jashtë lak ndërsa. Pra, nëse ju dilni nga lak, ndërsa kjo do të thotë që ju keni arritur fundin dhe asgjë nuk ka ndodhur. 

JASON HIRSCHHORN: OK. Pra, çfarë bëjmë ne këtu? 

Audienca: Ju kthimit të rreme edhe atje. 

JASON HIRSCHHORN: Oh, ne bëni atë në të dy vendet? 

Audienca: Po. 

JASON HIRSCHHORN: OK. A duhet të shkojmë? Oh mirësinë time. Më vjen keq. Unë kërkoj falje për të ekranit. Është lloj i freaking out mbi ne. Pra, zgjidhni një opsion. Zero, sipas kodit të, shpërblej programin. Një fut diçka. Le të futur tre. Insert nuk ishte i suksesshëm. Unë jam duke shkuar për të shtypur jashtë. Unë nuk kam asgjë. OK. Ndoshta kjo ishte vetëm një pikë për shans. Fut një të tillë. Nuk është i suksesshëm. OK. Le të vazhdojë deri gdb vërtetë shpejt për të parë se çfarë po ndodh. 

Mos harroni gdb. / Emri i juaj program na merr në gdb. Është se shumë për të trajtuar? Ndezje? Ndoshta. Mbyll sytë tuaj dhe të marrë disa të thellë frymë në qoftë se ju merrni lodhur e shikuar atë. Unë jam në gdb. Cila është gjëja e parë që unë bëj në gdb? Ne duhet të kuptoj se çfarë po ndodh këtu. Le të shohim. Ne kemi gjashtë minuta për figurën se çfarë po ndodh. Pushim kryesore. Dhe pastaj çfarë të bëj? Carlos? Run. OK. Le të zgjidhni një opsion. Dhe çfarë do të bëjë N? Next. Po. 

Audienca: A nuk e përmend - nuk ju them se koka, ishte e initialized të null në fillim. Por Mendova se ju tha se ishte në rregull. 

JASON HIRSCHHORN: Le të shkojmë - le të shohim në gdb, dhe pastaj ne do të kthehemi. Por kjo tingëllon si ju tashmë keni disa ide se çfarë po ndodh. Pra, ne duam të futur diçka. OK. Ne kemi futur. Ju lutem, jepni një int. Ne do të futur tre. Dhe atëherë unë jam në këtë linjë. Si mund të shkoj të fillojë debugging insert njohur funksionin? Oh mirësinë time. Kjo është një shumë. Është që freaking out shumë? 

Audienca: Oh, ai vdiq. 

JASON HIRSCHHORN: Unë vetëm nxorrën atë jashtë. OK. 

Audienca: Ndoshta është fundi tjetër e telit. 

JASON HIRSCHHORN: Wow. Pra, qëllimi i fundit - çfarë the? 

Audienca: I tha ironia e teknike Vështirësitë në këtë klasë. 

JASON HIRSCHHORN: Unë e di. Sikur të isha kthyer kontroll mbi atë pjesë. [Padëgjueshme] Kjo duket e madhe. Pse nuk ju djema fillojnë të mendojnë për ajo që ne mund të ketë bërë keq, dhe ne do të kthehet në 90 sekonda. 

Avica, unë jam do të ju pyes se si për të shkuar insert_node brenda të korrigjoj atë. Pra, kjo është ajo ku ne fundit u ndërpre. Si mund të shkoj brenda insert_node, Avica, për të ekzaminuar se çfarë po ndodh? Çfarë komandë Gdb? Pushim nuk do të më brenda. A e dini markeze? 

Audienca: Çfarë? 

JASON HIRSCHHORN: Çfarë komandë Gdb I përdorni për të hyrë brenda këtë funksion? 

Audienca: Hapi? 

JASON HIRSCHHORN: Hapi via S. Ajo merr mua brenda. OK. New_node mallocing një hapësirë. Që të gjitha duket si e saj duke shkuar. Le të shqyrtojmë new_node. Ajo mori disa adresën e memories. Le të kontrolloni - kjo është e gjitha e saktë. Pra, çdo gjë këtu duket se jetë duke punuar si duhet. 

Audienca: Cila është diferenca midis P dhe ekranit? 

JASON HIRSCHHORN: P qëndron për shtyp. Dhe kështu që ju jeni duke i kërkuar se çfarë është Dallimi në mes të se dhe kjo? Në këtë rast, asgjë. Por në përgjithësi ka disa dallime. Dhe ju duhet të shikoni në doracakun gdb. Por në këtë rast, asgjë. Ne priremi për të përdorur të shtypura, edhe pse, sepse ne nuk kemi nevojë të bëjë shumë më tepër se shkruar një vlerë të vetme. 

OK. Pra, ne jemi on line 80 të kodit tonë, vendosjen nyje * curr barabartë me listë. Le të shtypura nga curr. Kjo është e barabartë me listë. Sweet. Prisni. Kjo është e barabartë me diçka. Kjo nuk duket e drejtë. Nuk shkojmë. Kjo për shkak se në gdb, të drejtë, në qoftë se kjo është linjë që ju jeni në të nuk ka ekzekutuar ende. Kështu që ju duhet të vërtetë shkruani tjetër për të ekzekutuar linjë para se të shohim rezultatet e tij. Pra, ja ku jemi. Ne vetëm të ekzekutuar këtë linjë, mëparshme është e barabartë null. Pra, përsëri, në qoftë se ne të shtypura e mëparshme ne nuk do të shohim asgjë të pazakontë. Por në qoftë se ne fakt ekzekutuar që line, atëherë ne do të shohim se kjo linjë ka punuar. 

Pra, ne kemi curr. Ata janë të dy të mira. E drejtë? Tani ne jemi në këtë linjë të drejtë këtu. Ndërsa curr nuk ka null barabartë. E pra, çfarë e bën të barabartë curr? Ne vetëm e pa atë barabartë null. Ne të shtypura it out. Unë do të shtypura atë përsëri. Pra, është se ndërsa loop duke shkuar për të ekzekutuar? 

Audienca: Jo. 

JASON HIRSCHHORN: Pra, kur i shtypur që line, ju shihni ne kërceu gjithë rrugës poshtë në fund, kthimit të rreme. Dhe pastaj ne do të kthimit të rreme dhe të kthehemi në programin tonë dhe përfundimisht të shtypura nga, si e pamë, insert nuk ishte i suksesshëm. Pra, dikush ndonjë ide se çfarë ne duhet të bëni për të rregulluar këtë? Unë do të pres deri sa të shoh disa duarve të shkojnë deri. Ne nuk e kryej këtë. Mbani në mend, kjo ishte e para gjë që ne ishim duke bërë. Unë nuk jam duke shkuar për të bërë një çift. Unë jam duke shkuar për të bërë disa. Për shkak se një çift do të thotë dy. Unë do të pres për më shumë se dy. 

Futje e parë, curr, nga parazgjedhur është e barabartë null. Dhe kjo loop vetëm ekzekuton në qoftë se nuk është e curr null. Pra, si mund të marrë rreth kësaj? Unë shoh tre duar. Unë do të pres për më shumë se tre. Marcus, çfarë mendoni ju? 

Audienca: E pra, nëse keni nevojë për të ekzekutuar më shumë se një herë, ju vetëm ndryshojë atë në një lak për ta bërë ndërsa. 

JASON HIRSCHHORN: OK. A do që të zgjidhë problemin tonë, pse? 

Audienca: Në këtë rast nuk ka për shkak të fakti se lista është e zbrazët. Pra, atëherë ju ndoshta vetëm duhet të shtoni një deklaratë se në qoftë se daljet lak atëherë ju duhet të jetë në fund të listë, në të cilën pikë ju vetëm mund ta futur atë. 

JASON HIRSCHHORN: Më pëlqen kjo. Kjo ka kuptim. Nëse loop daljet - për shkak se ajo do të kthehet të rreme këtu. Pra, nëse daljet loop, atëherë ne jemi në në fund të listës, ose ndoshta filloni nga një listë nëse nuk ka asgjë në ajo, e cila është e njëjtë si në fund. Pra, tani ne duam të futur diçka këtu. Pra, si duket se kodi, Marcus? 

Audienca: Nëse ju tashmë e mori nyjen malloced, ju mund të thoni vetëm new_node-> tjetër është e barabartë null sepse ajo duhet të jetë në fund. Ose new_node-> tjetër është e barabartë null. 

JASON HIRSCHHORN: OK. Më vjen keq. New_node-> next barabartë null sepse ne jemi në fund. Kjo nuk do të vënë atë in Si mund të vënë atë në listë? E drejta. Kjo është vetëm vendosur atë barabartë me. Nuk ka se si të bëjmë ne në të vërtetë vënë atë në listën? Çfarë është duke treguar fund të listës? 

Audienca: Shef. 

JASON HIRSCHHORN: Na vjen keq? 

Audienca: Shef është duke treguar në fund të lista. 

JASON HIRSCHHORN: Nëse nuk ka asgjë në lista, kokë është duke treguar fundi i listës. Kështu që do të punojnë për futje e parë. Po në lidhje në qoftë se ka disa gjërat në listë? Se ne nuk duam për të vendosur kokë e barabartë me new_node. Çfarë duam të bëjmë atje? Po? Ndoshta mëparshme. A do që të punojnë? Kujtojnë se mëparshme është vetëm një tregues për një nyje. Dhe e mëparshme është një variabël lokale. Pra, kjo linjë do të vendosë një ndryshore lokale, mëparshme, e barabartë me ose duke treguar për këtë nyje të re. Kjo nuk do të vërtetë vënë atë në listën tonë, pse. Si mund të vënë atë në listën tonë? Akchar? 

Audienca: Unë mendoj se ju bëni aktuale-> ardhshme. 

JASON HIRSCHHORN: OK. curr-> ardhshme. Pra, përsëri, e vetmja arsye ne jemi poshtë këtu është, ajo që e bën aktuale të barabartë? 

Audienca: barabartë null. 

JASON HIRSCHHORN: Dhe kështu që ajo që ndodh në qoftë se ne bëjmë zero-> ardhshme? Ajo që nuk kemi shkuar për të marrë? Ne do të merrni një defekt segmentimit. 

Audienca: A curr barabartë null. 

JASON HIRSCHHORN: Kjo është e njëjta gjë si prev, edhe pse, sepse nuk ka një variabël lokale ne jemi ngritjen barabartë me këtë nyje të re. Le të kthehemi në foto tonë të futur diçka. Thuaj ne jemi futur në fund i listës, në mënyrë të drejtë këtu. Ne kemi një tregues aktuale që është duke treguar null dhe një pikë e mëparshme që është duke treguar në 8. Pra, çfarë nuk kemi nevojë për të rinovuar, Avi? 

Audienca: Kthehu-> ardhshme? 

JASON HIRSCHHORN: Kthehu-> tjetër është ajo që ne duam të rinovuar për shkak se në të vërtetë do të futur atë në në fund të listës. Ne ende kemi një bug, edhe pse, se ne do të kandidojë në. Ç'është kjo bug? Po? 

Audienca: Ajo do të kthehen rreme në këtë rast? 

JASON HIRSCHHORN: Oh, është i do të kthimit të rreme. Por ka një tjetër bug. Pra, ne do të duhet për të vënë në kthim të vërtetë. 

Audienca: A previous ende të barabartë zero në majë të lista? 

JASON HIRSCHHORN: ende Pra mëparshme është e barabartë me zero në fillim. Pra, si mund të merrni mbi këtë? Po? 

Audienca: Unë mendoj se ju mund të bëni një kontroll para lak, ndërsa për të parë nëse është e një listë e zbrazët. 

JASON HIRSCHHORN: OK. Pra, le të shkojnë këtu. Të bëjë një kontroll. Nëse - 

Audienca: Pra, nëse koka është e barabartë barabartë null. 

JASON HIRSCHHORN: Nëse kokë është e barabartë barabartë null - që do të na thuash në se kjo është një listë e zbrazët. 

Audienca: Dhe pastaj ju të bëjë kreu i barabartë i ri. 

JASON HIRSCHHORN: Shef është e barabartë me new_node? Dhe çfarë tjetër na duhet të bëjmë? 

Audienca: Dhe pastaj ju kthehen e vërtetë. 

JASON HIRSCHHORN: Jo mjaft. Ne jemi të humbur një hap. 

Audienca: New_node tjetër duhet të tregojnë për null. 

JASON HIRSCHHORN: Pikërisht, Alden. Dhe atëherë ne mund të kthehen vërtetë. OK. Por është ende një ide e mirë për të bërë gjëra në fund të lista, drejtë? Dakord. Ne ende mund të ketë në fakt në fund të lista. Pra, është kjo e mirë kodi në qoftë se ne jemi në fund të listës dhe ka disa gjërat në listë? E drejtë? Sepse ne ende kemi idenë e Marcus-së. Ne mund të dalë këtë lak, sepse Ne jeni në fund të lista. Pra, nuk kemi ende duan këtë kodin këtu? 

Audienca: Po. 

JASON HIRSCHHORN: Po. Dhe ajo që nuk kemi nevojë për të ndryshuar këtë? Vërtetë. A do të mirë të shëndoshë për të gjithë deri më tani? Çdokush keni ndonjë - Avi, a keni diçka për të shtuar? 

Audienca: Jo. 

JASON HIRSCHHORN: OK. Pra, ne kemi bërë disa ndryshime. Ne e kemi bërë këtë kontroll para se ne shkoi në për një listë të zbrazët. Pra, ne kemi marrë kujdesin e një listë të zbrazët. Dhe këtu ne u kujdes të futur diçka në fund të lista. Pra, kjo duket si ky marrjen loop ndërsa kujdesi për gjëra në mes, diku në listë, nëse ka janë gjëra në listë. 

OK. Le të drejtuar këtë program përsëri. Nuk është i suksesshëm. 

Audienca: Ju nuk e bëni atë. 

JASON HIRSCHHORN: Oh, Unë nuk e kam bërë atë. Pikë e mirë, Michael. Le të shtoni një make lidhur. Line 87 ka një gabim. Line 87. Alden, kjo ishte vija që ju dha mua. Çfarë është e gabuar? 

Audienca: Ajo duhet të jetë për të null. 

JASON HIRSCHHORN: Excellent. Saktësisht e drejtë. Ajo duhet të jetë null. Le të bëjmë përsëri. Përpiloni. OK. Le të futur tre. Insert ishte i suksesshëm. Le të shtypura it out. Oh, në qoftë se vetëm ne mund të kontrolloni. Por ne nuk kemi bërë shtypura funksion akoma. Le të hyjë diçka tjetër. Çfarë duhet të hyjë? 

Audienca: Shtatë. 

JASON HIRSCHHORN: Shtatë? 

Audienca: Po. 

JASON HIRSCHHORN: Ne kemi një defekt seg. Pra, kemi marrë një të tillë, por në mënyrë të qartë nuk mund të marrë dy. Ajo është 05:07. Pra, ne mund të korrigjoj këtë për tre minuta. Por unë jam duke shkuar për të na lënë këtu dhe për të shkuar më të përpunojnë tavolina. Por përsëri, përgjigjet për këtë kod Unë do të email-it për ju në një grimë. Ne jemi shumë të afërt me të. I highly ju inkurajojmë që të kuptoj se çfarë po ndodh këtu dhe fix it. Kështu që unë do të ju email këtë kod si edhe plus zgjidhje - ndoshta zgjidhja më vonë. Së pari ky kod. 

Gjë tjetër që unë dua të bëj para se ne përfundojë është që ne nuk e kemi liruar asgjë. Kështu që unë dua të ju tregojnë se çfarë valgrind duket si. Nëse kemi drejtuar kufijtë valgrind në programin tonë,. / e lidhur. Përsëri, sipas kësaj rrëshqitje, ne duhet të kandidojë valgrind me disa lloj opsion, në këtë rast - Rrjedhje-check = të plotë. Pra, le të shkruajë valgrind - Rrjedhje-check = të plotë. Pra, kjo do të kandidojë valgrind në programin tonë. Dhe tani programi në të vërtetë shkon. Pra, ne jemi duke shkuar për të drejtuar atë vetëm si para, të vënë diçka in Unë jam duke shkuar për të vënë në tre. Që punon. Unë nuk jam do të përpiqen të vënë në diçka tjetër, sepse ne jemi duke shkuar për të marrë një FALSE Seg në atë rast. Kështu që unë jam vetëm do të të lënë. 

Dhe tani që ju shihni këtu poshtë del në shesh dhe përmbledhje grumbull. Këto janë gjëra të mira që ju doni të shikoni. Pra përmbledhje grumbull - ai thotë, në përdorim në dalje - tetë bytes në një bllok. Se një bllok është nyje ne malloced. Michael, ju tha para një nyje është tetë kafshimet sepse ajo ka integer dhe akrep. Pra, kjo është nyja tonë. Dhe pastaj ai thotë se kemi përdorur malloc shtatë herë dhe ne e lirë diçka gjashtë herë. Por kurrë nuk e kemi quajtur të lirë, kështu që unë nuk kam asnjë ide se çfarë kjo është duke folur për. 

Por mjafton të them se kur tuaj shkon e programit, malloc është duke u thirrur në disa vende të tjera që ne nuk kanë nevojë për t'u shqetësuar rreth. Pra malloc u quajt ndoshta në disa vende. Ne nuk duhet të shqetësohen se ku. Por kjo është me të vërtetë na. Kjo linjë e parë na është. Ne u largua që bllokut. Dhe ju mund të shihni se këtu në përmbledhjen rrjedhje. Ende e arritshme - tetë bytes në një bllok. Kjo do të thotë se kujtesës - ne kemi rrjedhur këtë kujtesë. Definitely humbur - diçka është e humbur për të mirë. Në përgjithësi, ju nuk do të shoh ndonjë gjë atje. Ende e arritshme është përgjithësisht ku ju do të shihni gjëra, ku ju do të dëshironi për të kërkuar për të parë se çfarë kodi duhet të ju kanë liruar por keni harruar të lirë. 

Dhe pastaj në qoftë se kjo nuk ishte rasti, në qoftë se ne e bëmë gjithçka të lirë, ne mund të kontrolloni atë. Le të vetëm të drejtuar programin nuk e vënë në asgjë. Ju do të shihni këtu poshtë në përdorim në dalje - zero bytes në zero blloqe. Kjo do të thotë që kishim lënë asgjë kur ky program exited. Pra, para se të kthyer në pset6, drejtuar valgrind dhe sigurohuni që ju nuk e keni çdo memorie rrjedhjet në programin tuaj. Nëse keni ndonjë pyetje me valgrind, të ndjehen të lirë për të arritur jashtë. Por kjo është se si ju të përdorni atë. Shumë e thjeshtë - të parë nëse kanë në përdorim në dalje - çdo bytes në çdo blloqe. 

Pra, ne kemi qenë duke punuar në insert nyje. I kishte dy funksione të tjera këtu - shtypura nyjet dhe nyjet e lirë. Përsëri, këto janë funksione që janë të do të jetë e mirë për ju për të praktikuar sepse ata do të ju ndihmojë jo vetëm me këto ushtrime mostër, por edhe mbi problemin vendosur. Ata hartë për mjaft të ngushtë me gjëra të ju jeni do të duhet të bëni në Problemi vendosur. Por unë dua të bëni të sigurtë ne prekë në çdo gjë. Dhe tabelat hash janë gjithashtu të rëndësishme për të ajo që ne jemi duke bërë në këtë seksion javë - ose në grup problemit. 

Pra, ne jemi duke shkuar për të përfunduar pjesën duke folur për tabelat hash. Nëse vëreni kam bërë një pak tabelë hash. Kjo nuk është ajo që ne jemi duke folur rreth, megjithatë. Ne po flasim për një tjetër Lloji i tabelave hash. Dhe në bazë, një tavolinë e saj të hash nuk është asgjë më shumë se një array plus një funksion hash. Ne do të flasim për një grimë vetëm për të sigurohuni që të gjithë e kuptojnë se çfarë është një funksion hash është. Dhe unë po ju them tani se ajo është asgjë më shumë se dy gjëra - një grup dhe një funksion hash. Dhe këtu janë hapat përmes të cilat kjo vepron. 

Ka koleksion tona. Ka funksion tonë. Në veçanti, funksionet hash duhet të të bëjë disa gjëra me këtë. Unë jam duke shkuar për të folur në mënyrë specifike në lidhje me këtë problem i vendosur. Kjo ndoshta do të të marrë në një varg. Dhe çfarë është e do të kthehet? Çfarë lloji të dhënat? Alden? Funksioni i juaj hash kthehen? Një numër të plotë. Pra, kjo është ajo që hash Tabela përbëhet nga - një tabelë në formën e grup dhe një funksion hash. Si punon kjo? Ajo punon në tre hapa. Ne jepte një çelës. Në këtë rast, ne do të të jap një varg. Ne e quajmë funksionin hash për një hap në kyçe dhe të marrim një vlerë. 

Në mënyrë të veçantë, ne do të themi ne kemi marrë një numër të plotë. Ky numër i plotë, ka shumë specifike kufizime në atë që mund të jetë që numër i plotë. Në këtë shembull, koleksion tona është i madhësisë tre. Pra, çfarë numrat mund të jetë që numër i plotë. Çfarë është varg i vlerave të vlefshme për se numër i plotë, lloji kthimi i kësaj hash funksion? Zero, një dhe dy. Pika e funksionit hash është gjej vend në rrjet ku çelësi jonë është duke shkuar. Nuk janë vetëm tre të mundshme vende këtu - zero, një ose dy. Pra, ky funksion më të mirë kthimi zero, një ose dy. Disa indice të vlefshme në këtë grup. 

Dhe pastaj në varësi se ku ajo kthehet, ju mund të shihni atje rrjet të hapur kllapa vlerën. Kjo është ku ne kemi vënë çelësin. Pra, ne të hedhin në kungull, ne kemi marrë nga zero. Në array kllapa 0, ne kemi vënë kungull. Ne hedhin në macet, ne kemi marrë nga një të tillë. Ne kemi vënë cat në një. Ne kemi vënë në merimangë. Ne kemi marrë nga dy. Ne kemi vënë merimangë në array dy kllapa. Ajo do të jetë aq e bukur nëse ai ka punuar si kjo. Por për fat të keq, siç do të shohim, kjo është pak më e komplikuar. 

Para se të arritur atje, ndonjë pyetje në lidhje me këtë bazë set-up e një tabelë hash? Ky është një imazh i saktësisht ajo që ne tërhoqi në bord. Por, që ne e tërhoqi atë në bord, unë nuk jam duke shkuar për të shkuar në atë më tej. Thelb çelësat, kuti magjike e zezë - ose në këtë rast, kuti bajukë - e një funksion hash i vë ata në kova. Dhe në këtë shembull ne jemi nuk e vënë emrin. Ne jemi duke vënë telefonin të lidhur Numri i emrit në kovë. Por ju mund shumë mirë vetëm vënë emrin në kovë. 

Kjo është vetëm një fotografi e asaj ne tërhoqi në bord. Ne kemi kurthet e mundshme, edhe pse. Dhe ka dy në mënyrë të veçantë slides që unë dua të shkoj gjatë. I pari ka të bëjë me një funksion hash. Kështu që unë pyetjen, çfarë bën një funksion të mirë të hash? Unë jap dy përgjigje. E para është se është e determinist. Në kuadër të funksioneve të hash, çfarë do të thotë kjo? Po? 

Audienca: Ajo mund të gjeni Indeksi në kohë të vazhdueshme? 

JASON HIRSCHHORN: Kjo nuk është çfarë do të thotë. Por kjo është një mend mirë. Dikush tjetër të ketë një guess për çfarë do të thotë kjo? Se një funksion hash mirë është determinist? Annie? 

Audienca: Se një kyç mund të jetë plotësisht vetëm për një vend në tabelën hash. 

JASON HIRSCHHORN: Kjo është saktësisht e drejtë. Çdo herë që të vënë në kungull, ai gjithmonë kthehet zero. Nëse vendosni në kungull dhe të hash tuaj funksion të kthimit zero, por ka një Mundësia e kthimit diçka tjetër e madhe se zero - kështu që ndoshta ajo mund të kthehet një të tillë ndonjëherë ose dy herë të tjera - se nuk është një funksion i mirë hash. Ju jeni saktësisht e drejtë. Funksioni hash juaj duhet të kthehet integer njëjtë saktë, në këtë rast, për të njëjtën gjë string saktë. 

Ndoshta ajo e kthimit të njëjtin numër të plotë saktë për të njëjtin varg e saktë pavarësisht nga kapitalizimit. Por në këtë rast është ende determinist sepse gjëra të shumta janë plotësisht në të njëjtën vlerë. Kjo është në rregull. Për sa kohë që ka vetëm një prodhimit për një input të caktuar. 

OK. Gjëja e dytë është se ajo kthehet indekseve të vlefshme. Ne sjellë deri që më herët. Ky funksion hash - oh boy - një funksion hash duhet kthehen indekseve të vlefshme. Pra, thonë - le të kthehemi në këtë shembull. Funksioni im hash akuza deri letra në fjalë. Kjo është funksion hash. Dhe kthehet se numër i plotë. Pra, nëse unë kam fjalën A, është e do të kthehen një të tillë. Dhe ajo do të vënë një të drejtë këtu. Po në qoftë se kam vënë në fjalë bat? Ajo do të kthehen tre. Ku bat shkoni? 

Kjo nuk i përshtatet. Por ajo ka nevojë për të shkuar diku. Ky është im tabelë hash në fund të fundit, dhe çdo gjë ka nevojë për të shkuar diku. Pra, ku duhet të shkoni lakuriq nate? Çdo mendime? Supozime? Supozime të mira? 

Audienca: Zero. 

JASON HIRSCHHORN: Pse zero? 

Audienca: Sepse tre modulo tre është zero? 

JASON HIRSCHHORN: Tre modulo tre është zero. Kjo është një mend e madhe, dhe kjo është e saktë. Pra, në këtë rast duhet ndoshta shkojnë në zero. Pra, një mënyrë e mirë për të siguruar që ky hash Funksioni i vetëm kthen indekset e vlefshme është të modulo atë nga madhësia e tabelës. Nëse ju modulo çfarëdo këtë kthimit nga tre, ju jeni gjithmonë do të merrni diçka mes zero, një, dhe dy. Dhe në qoftë se kjo gjithmonë kthehet shtatë, dhe ju gjithmonë modulo nga tre, ju jeni gjithmonë do të merrni të njëjtën gjë. 

Pra, kjo është ende determinist në qoftë se ju modulo. Por kjo do të sigurojë që ju kurrë nuk merrni diçka - një industri të pavlefshme. Në përgjithësi, kjo duhet të ndodhë modulo brenda funksionit tuaj të hash. Pra, ju nuk keni nevojë për t'u shqetësuar për këtë. Ju vetëm mund të sigurojë që kjo është një indice vlefshme. Çdo pyetje në këtë kurth potencial? 

OK. Dhe ne do të shkojmë atje. Kurth Next potencial, dhe kjo është një e madhe. Çfarë ndodh nëse dy çelësat hartë në të njëjtën vlerë? Pra, ka dy mënyra për të trajtuar këtë. I pari është quajtur linear probing, të cilën unë jam i nuk do të shkoj për. Por ju duhet të jetë njohur me atë se si që punon dhe çka është. 

E dyta unë jam duke shkuar për të shkuar mbi sepse ajo është një që shumë njerëz ndoshta do të përfundojë duke vendosur për të përdorur në grup e problemit. Sigurisht, ju nuk keni për të. Por, për të vendosur të problemit, shumë njerëz kanë tendencë për të zgjedhur për të krijuar një tabelë hash me chaining të veçantë të zbatimit të fjalor tyre. Pra, ne do të shkoj për çfarë do të thotë për të krijuar një tabelë hash me chaining veçantë. 

Kështu që unë vë në kungull. Ajo kthehet zero. Dhe kam vënë kungull këtu. Pastaj kam vënë në - çfarë është një tjetër gjë e Halloween-themed? 

Audienca: Candy. 

JASON HIRSCHHORN: Candy! Kjo është një njeri i madh. I vënë në karamele, dhe karamele gjithashtu jep zero. Çfarë të bëj? Ndonjë ide? Për shkak se ju të gjitha llojet e di çfarë chaining veçantë është. Pra, ndonjë ide se çfarë të bëni? Po. 

Audienca: Vendosja string në të vërtetë në tabelën hash. 

JASON HIRSCHHORN: Pra, ne do të të nxjerrë ide të mirë mbi këtu. OK. 

Audienca: A hashtable [Padëgjueshme] tregues që tregon për fillimi i një liste. Dhe pastaj kanë kungull të jetë vlera e parë në atë listën e lidhur dhe karamele të jetë e Vlera e dytë në atë listën e lidhur. 

JASON HIRSCHHORN: OK. Marcus, që ishte i shquar. Unë jam duke shkuar për të thyer atë poshtë. Marcus është duke thënë nuk prishësh kungull. Kjo do të ishte e keqe. A nuk e vënë karamele diku tjetër. Ne jemi duke shkuar për të vënë ato të dy në zero. Por ne jemi duke shkuar për t'u marrë me vënien e tyre në zero duke duke krijuar një listë në zero. Dhe ne jemi duke shkuar për të krijuar një listë të çdo gjë që plotësisht në zero. Dhe mënyra më e mirë që ne mësuam për të krijuar një listë që mund të rritet dhe tkurret dinamike nuk është brenda një tjetër grup. Pra, nuk është një grup shumë-dimensionale. Por për të vetëm të krijojë një listë e lidhur. 

Pra, atë që ai e propozuar - Unë jam duke shkuar për të marrë një të ri - është krijuar një grup me pointers, një grup i pointers. OK. Çdo ide apo aluzion se çfarë lloji i këtij pointers duhet të jetë? Marcus? 

Audienca: Pointers në - 

JASON HIRSCHHORN: Për shkak të ju tha se një listë e lidhur, kështu - 

Audienca: Nyja pointers? 

JASON HIRSCHHORN: Nyja pointers. Në qoftë se gjërat në të lidhura tonë listë janë nyje atëherë ata duhet të jetë nyje pointers. Dhe çfarë ata të barabartë në fillim? 

Audienca: Null. 

JASON HIRSCHHORN: Null. Pra, nuk ka gjë jonë bosh. Kthimit kungull zero. Çfarë bëjmë ne? Ecni më nëpërmjet saj? Në fakt, Marcus tashmë dha mua. Dikush tjetër ecin mua me të. Ajo që ne bëjmë kur ne - kjo duket shumë e ngjashme me ajo që ne ishim vetëm duke bërë. Avi. 

Audienca: Unë jam duke shkuar për të marrë një guess. Pra, kur ju të merrni karamele. 

JASON HIRSCHHORN: Po. E pra, kemi marrë kungull. Le të marrë një të tillë tonë të parë. Ne morëm kungull. 

Audienca: OK. Kthimit kungull zero. Kështu që ju vënë atë në se. Ose në të vërtetë, ju vënë atë në lista lidhur. 

JASON HIRSCHHORN: Si e vënë atë në listën e lidhur? 

Audienca: Oh, sintaksë aktuale? 

JASON HIRSCHHORN: Vetëm ecin - thonë më shumë. Çfarë bëjmë ne? 

Audienca: Ju sapo futur ajo si nyjen e parë. 

JASON HIRSCHHORN: OK. Pra, ne kemi nyje tonë, kungull. Dhe tani si mund ta futur atë? 

Audienca: Ju caktojë ajo te kursorit. 

JASON HIRSCHHORN: Cili akrep? 

Audienca: pointer në zero. 

JASON HIRSCHHORN: Pra, ku e bën këtë pikë? 

Audienca: Të null tani. 

JASON HIRSCHHORN: E pra, ajo është duke treguar null. Por unë jam vënë në kungull. Pra, ku duhet të theksojnë? 

Audienca: Të kungull. 

JASON HIRSCHHORN: Të kungull. Pikërisht. Pra, kjo tregon për kungull. Dhe ku e bën këtë akrep në pikën kungull? Në 

Audienca: Null. 

JASON HIRSCHHORN: Të null. Pikërisht. Pra, ne vetëm të futur diçka në lista lidhur. Ne vetëm shkroi këtë kod për të bërë këtë. Pothuajse kemi gati got it plasaritur plotësisht. Tani kemi futur karamele. Karamele jonë gjithashtu bëhet zero. Pra, çfarë bëjmë ne me karamele? 

Audienca: Kjo varet nëse ose jo ne jemi duke u përpjekur për të zgjidhur atë. 

JASON HIRSCHHORN: Kjo është saktësisht e drejtë. Kjo varet nëse ose jo ne jemi duke u përpjekur për të zgjidhur atë. Le të supozojmë që ne nuk jemi duke shkuar për të zgjidhur atë. 

Audienca: Mirë atëherë, siç kemi diskutuar para, është më e thjeshtë vetëm për të vënë atë të drejtë në fillim në mënyrë akrep nga zero pikë në karamele. 

JASON HIRSCHHORN: OK. Prit. Më lejoni të krijuar karamele drejtë këtu. Pra, ky tregues - 

Audienca: Po, duhet tani të treguar për karamele. Pastaj kanë treguesin nga pika karamele për të kungull. 

JASON HIRSCHHORN: Ashtu si ajo? Dhe thonë se ne mori një tjetër gjë për të hartë në zero? 

Audienca: E pra, ju vetëm të bëjë të njëjtën gjë? 

JASON HIRSCHHORN: Bëni të njëjtën gjë. Pra, në këtë rast, në qoftë se ne nuk e bëjmë duan të mbajnë atë të renditura atë tingëllon mjaft e thjeshtë. Ne kemi marrë treguesin në indice dhënë nga funksioni tonë hash. Ne kemi atë pikë për nyje tonë të ri. Dhe pastaj çfarëdo qoftë ajo ishte treguar të parë - në këtë rast null, në Rasti kungull i dytë - që, çfarëdo qoftë ajo është duke treguar më parë, ne shtoni në tjetër i nyje tonë të ri. Ne jemi duke futur diçka në fillim. Në fakt kjo është një shumë të thjeshtë se sa duke u përpjekur për të mbajtur listë të renditura. Por përsëri, në kërkim do të jetë më shumë e komplikuar këtu. Ne gjithmonë do të duhet të shkojë deri në fund. 

OK. Ndonjë pyetje në lidhje me chaining të veçantë? Si punon kjo? Ju lutem, pyesni ata tani. Unë me të vërtetë dëshironi të bëni të sigurt që të gjithë kuptojnë këtë para se kreu jashtë. 

Audienca: Pse ju vendosni kungull dhe karamele në të njëjtën Pjesa e tabelës hash? 

JASON HIRSCHHORN: Pyetje e mirë. Pse nuk kemi vënë ato në të njëjtën Pjesa e tabelës hash? E pra, në këtë rast funksioni ynë hash kthimit zero për të dy ata. Pra, ata kanë nevojë për të shkuar në indice zero sepse kjo është ajo ku ne jemi duke shkuar për të shikoni për ta në qoftë se ne ndonjëherë dëshironi të shikoni ata. Përsëri, me një qasje lineare probing ne nuk do të vinte që të dy në zero. Por në qasjen zinxhir të veçantë, ne jemi duke shkuar për të vënë ato si në zero dhe pastaj të krijojë një listë off e zero. 

Dhe ne nuk duam të prishësh kungull thjesht për shkak se atëherë ne do të supozojmë se kungull ishte kurrë futur. Nëse ne vetëm i mbajnë një gjë të vend që do të ishte keq. Atëherë nuk do të kishte shans prej nesh ndonjëherë - në qoftë se ne ndonjëherë kishte një kopje, atëherë ne vetëm do të fshihet vlerën tonë fillestare. Pra, kjo është arsyeja pse ne e bëjmë këtë qasje. Apo kjo është arsyeja pse ne zgjodhëm - por përsëri, ne zgjodhi qasjen veçantë chaining, e cila ka shumë qasje të tjera një mund të zgjidhni. A do të përgjigjem pyetjes tuaj? 

OK. Carlos. Linear probing do të përfshijë - nëse kemi gjetur një përplasje në zero, ne do të shikojmë në vendin e ardhshëm për të parë nëse ajo ishte e hapur dhe e vënë atë atje. Dhe pastaj ne shikojmë në sport tjetër dhe të parë nëse kjo ishte e hapur dhe e vënë atë atje. Pra, ne gjejmë tjetër dispozicion vend i hapur dhe vënë atë atje. Çdo pyetje të tjera? Po, Avi. 

Audienca: Si vazhdim të kësaj, çfarë do të thotë nga vend tjetër? Në tabelën hash ose në listën e lidhur. 

JASON HIRSCHHORN: Për lineare programimi, nuk ka lista të lidhura. Vend tjetër në tryezë hash. 

Audienca: OK. Pra, tabela hash do të ishte initialized të madhësisë - si numrit të strings se ju u futur? 

JASON HIRSCHHORN: Ju do të duan që ajo të jetë me të vërtetë i madh. Po. Këtu është një foto e asaj që ne vetëm tërhoqi në bord. Përsëri, ne kemi një përplasje të drejtë këtu. në 152. Dhe ju do të shihni kemi krijuar një listë e lidhur jashtë të saj. Përsëri, tabela hash chaining veçantë qasje nuk është një që ju duhet të marrin për problemet vendosur gjashtë por është një që shumë studentët kanë tendencë për të marrë. Pra, në këtë, le të flasim shkurtimisht para se kreu jashtë në lidhje me problemin e gjashtë, dhe pastaj unë do të ndajnë një histori me ju. Ne kemi tre minuta. 

Problem vendosur gjashtë. Ju keni katër funksione - ngarkesës, kontrolloni, madhësia, dhe zbraz. Load - mirë, ne kemi qenë duke shkuar mbi ngarkesës vetëm tani. Ne tërhoqi ngarkesës në bord. Dhe ne edhe filluar coding shumë futur në listën e lidhur. Pra ngarkesës nuk është shumë më tepër se ajo që ne kemi qenë vetëm duke bërë. 

Kontrollo është një herë ju keni diçka e ngarkuar. Është i njëjti proces si ky. Të njëjtat dy pjesët e para ku ju hedhin diçka në funksion hash dhe për të marrë vlerën e saj. Por tani ne nuk jemi futur atë. Tani ne jemi duke kërkuar për të. Unë kam shkruar kodin mostër për gjetjen e diçka në listën e lidhur. Unë ju inkurajoj për të praktikuar atë. Por intuitive gjetur diçka është shumë e ngjashme me futur diçka. Në të vërtetë, ne tërhoqi një pamje të gjetur diçka në listën e lidhur, duke lëvizur nëpërmjet deri sa të marrë deri në fund. Dhe në qoftë se ju mori deri në fund dhe nuk mund të gjeni atë, atëherë ajo nuk është aty. Pra, kjo është kontroll, në thelb. 

Tjetra është madhësia. Le të kaloni madhësinë. Së fundi ju keni shkarkuar. Shkarkoj është një ne nuk kemi tërhequr në bordin ose koduar ende. Por unë ju inkurajoj që të provoni coding atë në mostër lidhur shembullin tonë lista. Por shkarkoj intuitive është e ngjashme me të lirë - ose Unë do të thotë është e ngjashme për të kontrolluar. Përveç për tani çdo kohë do të jeni përmes, ju nuk jeni thjesht duke kontrolluar për të të parë nëse ju keni vlerën tuaj atje. Por ju jeni duke marrë atë nyje dhe liruar atë, në thelb. Kjo është ajo që zbraz ju pyet për të bërë. Gjithçka pagesë ju keni malloced. Pra, ju jeni duke shkuar nëpër të gjithë listën përsëri, duke shkuar nëpër të gjithë hash Tabela përsëri. Këtë herë nuk e shikoni për të parë se çfarë është atje. Vetëm lirë çfarë është atje. 

Dhe së fundi madhësia. Madhësia duhet të zbatohet. Nëse ju nuk e zbatojnë madhësinë - Unë do të them atë si kjo. Nëse ju nuk e zbatojnë në madhësinë pikërisht një linjë e kodit përfshirë deklaratë të kthehet, ju jeni duke bërë madhësinë gabimisht. Pra, sigurohuni që madhësia, për dizajn të plotë pikë, ju jeni duke bërë atë pikërisht në një linjë e kodit, duke përfshirë Deklarata e kthimit. 

Dhe nuk do të mbledh plaçkat ende, Akchar. Kastor i etur. Unë të kërkuar për të thënë faleminderit djema për të ardhur në nenin. Keni një Halloween Gëzuar. Kjo është kostum e mia. Do të veshur këtë të enjten në qoftë se unë shoh se jeni në orarit të punës. Dhe nëse ju jeni kurioz rreth disa më shumë background si me këtë kostum, të ndjehen të lirë për të shikoni seksionin 2011 për një histori më se pse unë jam veshur kostum kungull. Dhe kjo është një histori e trishtuar. Pra, sigurohuni që ju keni disa indet afër. Por në se, në qoftë se ju keni ndonjë pyetje unë do të rrinë rreth jashtë pas seksion. Good luck në problemin vendosur gjashtë. Dhe si gjithmonë, në qoftë se ju keni ndonjë pyetje, let me know.