Jason HIRSCHHORN: Maligayang pagdating sa lahat ng tao sa Seksyon Pitong. Kami ay nasa linggo pitong mga kurso. At ito paparating na Huwebes ay Halloween kaya ako bihis tulad ng isang kalabasa. Hindi ko yumuko sa at ilagay sa ang aking sapatos, kaya na ang dahilan kung bakit ako suot lamang medyas. Hindi rin ako ang may suot ng anumang bagay sa ilalim ito, kaya hindi ko maaaring dalhin ito off kung ito ay distracting sa iyo. Humihingi ako ng paumanhin nang maaga para doon. Hindi mo kailangang isipin ano ang nangyayari sa. Ako ay may suot boxers. Kaya lahat ng ito ay mabuti. Mayroon akong na kuwento tungkol sa kung bakit ako ay bihis bilang isang kalabasa, ngunit pupuntahan ko i-save na para sa ibang pagkakataon sa seksyon na ito dahil ko nais upang makapagsimula. Mayroon kaming maraming mga kapana-panabik na bagay upang pumunta sa paglipas ng linggong ito. Karamihan sa kanila direktang umuugnay sa ito hanay problema linggong, mga maling spelling. Kami ay pagpunta sa ay pagpunta sa paglipas ng naka-link na mga listahan at hash talahanayan para sa buong seksyon. Naglagay ako listahang ito up bawat linggo, isang listahan ng mga mga mapagkukunan para sa iyo na tulungan ka sa ang materyal sa kursong ito. Kung nalilito o kung naghahanap para sa ilang mga sa higit pang impormasyon, tingnan ang isa sa mga mga mapagkukunang ito. Muli, pset6 ay maling pagbabaybay, pset ito linggong ito. At ito ay naghihikayat din sa iyo, at ako Hinihikayat ka, upang gamitin ang ilang mga iba pang mga mapagkukunan para mismo sa mga ito pset. Sa partikular, ang tatlong na hindi ko na nakalista up sa screen - gdb, na kung saan kami nakapunta pamilyar sa at ginagamit para sa isang habang ngayon, ay pagpunta sa maging kapaki-pakinabang sa linggong ito. Kaya ilagay ko na dito. Ngunit sa tuwing nakikipagtulungan ka sa C, lagi ka dapat na gamit gdb upang i-debug ang iyong mga program. Sa linggong ito valgrind din. Alam ba ng sinuman kung ano ang ginagawa valgrind? Madla: nagsusuri Ito para sa memory paglabas? Jason HIRSCHHORN: Valgrind mga tseke para sa memory paglabas. Kaya't kung ikaw malloc isang bagay sa iyong programa, ikaw ay humihingi ng memorya. Sa dulo ng iyong programa, mayroon kang magsulat ng libreng on lahat ng bagay na iyong malloced upang bigyan ang memory pabalik. Kung hindi mo isulat libre sa dulo at iyong programa pagdating sa isang konklusyon, Awtomatikong lahat habilin ay napalaya. At para sa maliit na mga programa, ito ay hindi na malaki isang deal. Ngunit kung ikaw ay sumusulat ng mas mahabang tumakbo programa na hindi tumigil, kinakailangang, sa loob ng ilang minuto o sa isang ilang segundo, pagkatapos ay i-memorya paglabas ay maaaring maging isang malaking pakikitungo. Kaya para sa pset6, ang pag-asa ay na magkakaroon ka ng zero memory paglabas sa iyong programa. Upang suriin para sa memory paglabas, patakbuhin valgrind at makikita ito magbibigay sa iyo ng ilang mga maganda output pagpapaalam sa iyo kung ang o hindi ang lahat ng bagay ay libre. Susubukan naming pagsasanay sa ito mamaya ngayon, sana. Sa wakas, ang command diff. Ginamit mo ang isang bagay na katulad nito sa pset5 sa pagsilip tool. Pinayagan ka upang tumingin sa loob. Ginamit mo din diff, masyadong, per itakda ang spec ang problema. Ngunit pinapayagan ka sa upang paghambingin ang dalawang mga file. Maaari mong ihambing ang bitmap file at mga header ng info ng isang kawani at solusyon ang iyong mga solusyon sa pset5 kung pinili mong gamitin ito. Diff ay magbibigay-daan sa iyo upang gawin iyon, pati na rin. Maaari mong ihambing ang tamang sagot para sa ang problemang ito linggong nakatakda sa iyong sagot at makita kung ito linya up o makita kung saan ang mga error ay. Kaya mga tatlong mahusay na tool na dapat mong gamitin para sa linggong ito, at Talagang suriin ang iyong mga programa may mga tatlong mga tool bago i ito in Muli, bilang ko na nabanggit sa bawat linggo, kung mayroon kang anumang feedback para sa akin - kapwa positibo at nakabubuti - huwag mag-atubiling magtungo sa website sa ibaba ng slide na ito at input ito doon. Talaga Pinapahalagahan ko ang anumang at ang lahat ng feedback. At kung bibigyan ninyo sa akin ang mga tukoy na bagay na Ang maaari kong gawin upang mapabuti o na ako mahusay na gumagana na nais mong sa akin na magpatuloy, magtagal ko na sa puso at talagang magsumikap upang makinig sa iyong feedback. Hindi ko ma-nangangako ako pagpunta sa gawin ang lahat ng bagay, bagaman, tulad ng suot ng isang kalabasa costume bawat linggo. Kaya pupunta kami sa gastusin sa karamihan ng seksyon, bilang ko nabanggit, pakikipag-usap tungkol sa naka-link na mga listahan at mga talahanayan ng hash, na Magiging direkta naaangkop sa itakda ang problemang ito linggo. Mga listahan ng Linked ipagpapatuloy namin sa paglipas ng relatibong mabilis dahil ginugol namin ang isang makatarungang bit ng oras ng pagpunta sa paglipas ng ito sa seksyon. At kaya susuriin namin diretso sa coding ng mga problema para sa naka-link na mga listahan. At pagkatapos ay sa dulo namin makipag-usap tungkol sa hash table at kung paano ilapat ang mga ito sa ito itakda problema linggong ito. Nakita mo na ang code na ito bago. Ito ay isang struct, at ito ay pagtukoy ng isang bagong bagay na tinatawag na node. At sa loob ng isang node doon ay isang integer dito mismo at doon ay isang pointer sa isa pang node. Nakita namin ang bago. Ito ay darating up para sa ng ilang linggo ngayon. Pinagsasama nito ang mga payo, na kami nakapunta nagtatrabaho sa, at structs, na nagbibigay-daan amin upang pagsamahin ang dalawang magkaibang bagay sa isang uri ng data. Mayroong maraming nagaganap sa screen. Ngunit dapat ay relatibong lahat ng ito pamilyar sa iyo. Sa unang linya, namin magpahayag ng isang bagong node. At pagkatapos ay sa loob na ang mga bagong node, ako magse-set ang integer sa na node sa isa. Nakakakita kami sa susunod na linya ako paggawa ng printf utos, ngunit nagbigay kulay-abo ko ang command printf dahil ang talagang mahalagang bahagi ay ang linyang ito dito - new_node.n. Ano ang ibig sabihin ng tuldok? Madla: Pumunta sa node at tasahin ang n halaga para dito. Jason HIRSCHHORN: Iyon akmang-akma. Dot ay nangangahulugan na ma-access ang n bahagi ng ang bagong node. Ang susunod na linya ang ginagawa kung ano? Michael. Madla: Ito ay lumilikha ng isa pang node na magtuturo sa bagong node. Jason HIRSCHHORN: Kaya hindi lumikha ng isang bagong node. Ito ay lumilikha ng isang ano? Madla: Ang isang pointer. Jason HIRSCHHORN: Ang isang pointer sa isang node, bilang ipinapahiwatig ng mga ito na node * dito. Kaya ito ay lumilikha ng isang pointer sa isang node. At kung aling mga node ay ito na tumuturo sa, Michael? Madla: Bagong node? Jason HIRSCHHORN: Bagong node. At ito ay tumuturo doon dahil hindi namin naibigay na ito sa address ng bagong node. At ngayon sa linyang ito na nakikita namin dalawang magkaibang mga paraan ng pagpapahayag ng ang parehong bagay. At Nais kong ituro kung paano ang mga dalawang bagay ay pareho. Sa unang linya, dereference namin ang pointer. Kaya pumunta kami sa node. Iyan ay ano ang ibig sabihin ng bituin na ito. Nakita namin na ang bago sa mga payo. Pumunta sa na node. Iyon ay naka-panaklong. At pagkatapos ma-access sa pamamagitan ng tuldok operator ang n elemento ng na node. Kaya na paglalaan ay ang syntax Nakita namin dito mismo at ngayon gamitin ito sa isang pointer. Siyempre, nakakakuha ito uri ng abala kung sumusulat ka sa mga panaklong - na bituin at na tuldok. Ito ay makakakuha ng isang maliit na abala. Kaya mayroon kaming ilang mga sintaktik asukal. At ang linyang ito dito mismo - ptr_node-> n. Iyan ang ginagawa ng parehong eksaktong bagay. Kaya ang dalawang linya ng code ay katumbas at ang gagawin ang eksaktong parehong bagay. Subalit Nais kong ituro ang mga sumali bago pumunta kami ng anumang karagdagang gayon maunawaan mo na talaga ito bagay dito mismo ay lamang sintaktik asukal para dereferencing ang pointer at pagkatapos ng pagpunta sa ang n bahagi ng na struct. Ang anumang mga katanungan tungkol sa slide na ito? OK. Kaya kami ay pagpunta sa pumunta sa pamamagitan ng ilang ng mga operasyon na maaari mong gawin sa naka-link na mga listahan. Ang isang naka-link na listahan, pagpapabalik, ay isang serye ng node na nagtuturo sa isa't isa. At namin magsimula sa isang pointer sa pangkalahatan tinatawag ulo, sa pangkalahatan, na tumuturo sa ang unang bagay na sa listahan. Kaya sa unang linya dito, namin mayroon muna ang aming orihinal na L. Kaya bagay na maaari mong isipin - na ito text dito mismo maaari mong isipin bilang lamang ang pointer sa iyong itinago namin sa isang lugar na puntos sa unang elemento. At sa naka-link na listahan mayroon kaming apat na node. Ang bawat node ay isang malaking box. Ang mas malaking box sa loob ng malaki kahon ang integer bahagi. At pagkatapos ay mayroon kaming isang pointer bahagi. Ang mga box ay hindi iguguhit sa scale dahil sa kung paano malaki ay isang integer sa bytes? Gaano kalaki ngayon? Four. At kung gaano kalaki ang isang pointer? Four. Kaya talaga, kung kami ay upang gumuhit ito upang masukat ang parehong mga kahon ay magiging ang parehong laki. Sa kasong ito, nais naming isingit isang bagay papunta sa naka-link na listahan. Kaya maaari mong makita down na dito kami ng pagpasok limang pagtawid namin sa pamamagitan ng naka-link na listahan, hanapin kung saan limang mangyaring hindi, at pagkatapos ay ipasok ito. Masira na down at pumunta Hayaan mas mabagal nang kaunti. Pupunta ako upang tumuro sa board. Kaya mayroon kaming ang aming node limang na na nilikha namin sa mallocs. Bakit tumatawa ay lahat ng tao? Kidding lang. OK. Kaya nagbigay malloced namin lima. Lumikha kami ito node sa isang lugar pang tao. Mayroon kaming ito handa na upang patakbuhin. Simulan namin sa harap ng ang aming listahan na may dalawang. At gusto naming isingit sa isang pinagsunod-sunod sa fashion. Kaya kung makita natin ang dalawa at gusto naming ilagay sa limang, ano ang gagawin namin kapag nakita namin isang bagay na mas mababa sa amin? Ano? Gusto naming magpasok ng limang sa ito naka-link na listahan, pagpapanatiling ito pinagsunod-sunod. Nakakakita kami ng numero ng dalawang. Kaya kung ano ang gagawin namin? Marcus? Madla: Tawagan ang pointer sa susunod na node. Jason HIRSCHHORN: At bakit gawin pumunta kami sa susunod na isa? Madla: Dahil ito ang susunod na node sa listahan. At nalalaman natin lamang na ang ibang lokasyon. Jason HIRSCHHORN: At limang ay mas malaki sa dalawang, sa partikular. Dahil gusto naming panatilihin ito pinagsunod-sunod. Kaya lima ay mas malaki sa dalawa. Kaya lumipat kami sa susunod na isa. At ngayon, maabot namin apat. At kung ano ang mangyayari kapag naabot namin apat? Limang ay mas malaki kaysa sa apat. Kaya panatilihin namin ang pagpunta. At ngayon kami sa anim. At kung ano ang nakikita namin sa anim? Oo, Carlos? Madla: Six ay mas malaki sa limang. Jason HIRSCHHORN: Six ay mas higit sa limang. Kaya na kung saan namin gusto sa magpasok ng limang. Gayunpaman, tandaan na kung kami lamang magkaroon ng isang pointer dito - ito ay ang aming mga extrang pointer na traversing sa listahan. At kami ay tumuturo sa anim. Nawala namin ang subaybayan kung ano ang nauuna bago anim. Kaya kung nais namin upang ipasok ang isang bagay sa listahang ito pagpapanatiling ito pinagsunod-sunod, namin marahil kailangan kung gaano karaming mga payo? Madla: Dalawang. Jason HIRSCHORN: Dalawang. Ang isa upang masubaybayan ang kasalukuyang isa at isa upang masubaybayan ang ang isang nakaraan. Ito ay lamang ng isang isa-isa naka-link na listahan. Napupunta lamang ito sa isa direksyon. Kung nagkaroon kami ng doble naka-link na listahan, kung saan ang lahat ng bagay ay tumuturo sa mga bagay matapos na ito at ang mga bagay na bago ito, pagkatapos ay hindi namin kailangan upang gawin iyon. Ngunit sa kasong ito hindi namin nais na mawala subaybayan kung ano ang dumating bago sa amin sa kasong kailangan namin upang magpasok ng limang sa isang lugar sa gitna. Sabihing namin ang pagpasok ng siyam. Ano ang mangyayari kapag Nakakuha kami sa walong? Madla: gusto mong mag kumuha na null point. Sa halip ng pagkakaroon null point ang kailangan mong upang magdagdag ng isang sangkap at pagkatapos ay mayroon ito ay tumuturo sa siyam. Jason HIRSCHORN: Mismong. Kaya makuha namin ang alas-otso. Maabot namin ang dulo ng listahan dahil ito ay tumuturo sa null. At ngayon, sa halip ng pagkakaroon ng ituro ito sa null mayroon kaming ito ay tumuturo sa aming bagong node. At itinakda namin ang pointer sa ang aming bagong node sa null. Kahit sinong mayroon ba kayong mga katanungan tungkol sa pagpasok? Paano kung Wala akong pakialam tungkol sa pinapanatili ang listahan pinagsunod-sunod? Madla: stick ito sa simula o dulo. Jason HIRSCHORN: stick ito sa sa simula o dulo. Aling isa dapat naming gawin? Bobby? Bakit dulo? Madla: Dahil ang simula ay napunan. Jason HIRSCHORN: OK. Simula ay nai-puno. Sino ang nais ni na magtaltalan laban sa Bobby. Marcus. Madla: Well mo marahil nais na ilagay ito sa simula dahil kung hindi man kung inilagay mo ito sa ang katapusan kailangan mong i- bagtasin ang buong listahan. Jason HIRSCHORN: Mismong. Kaya kung pinag-iisipan namin ang tungkol sa runtime, ang runtime ng pagpasok sa dulo magiging n, ang laki ng mga ito. Ano ang malaking O runtime ng pagpasok sa simula? Ang patuloy na oras. Kaya kung hindi mo pakialam tungkol sa pagpapanatiling isang bagay na pinagsunod-sunod, magkano ang mas mahusay sa makatarungan isingit sa simula ng listahang ito. At na Pwedeng gawin sa pare-pareho ang panahon. OK. Susunod na operasyon ay mahanap, na iba pang mga - phrased na namin ang bilang ng paghahanap. Ngunit kami ay pagpunta sa tumingin sa pamamagitan ng naka-link na listahan para sa ilang mga bagay. Ikaw guys nakakita code para sa maghanap bago sa panayam. Ngunit kami uri ng lamang ginawa ito sa isingit, o hindi bababa sa pagpasok isang bagay na pinagsunod-sunod. Tumingin ka sa pamamagitan, ng pagpunta sa pamamagitan ng node node, hanggang sa mahanap mo ang numero na ikaw ay hinahanap. Ano ang mangyayari kung naabot mo sa dulo ng listahan? Sabihing Naghahanap ako ng siyam at ako maabot sa dulo ng listahan. Ano ang gagawin namin? Madla: Bumalik huwad? Jason HIRSCHORN: Bumalik false. Hindi namin mahanap ito. Kung naabot mo ang dulo ng listahan at hindi mo makita ang numero ng ikaw ay naghahanap ng, hindi ito sa doon. Ang anumang mga katanungan tungkol mahanap? Kung ito ay isang pinagsunod-sunod listahan, ano ang gagawin naiiba para sa aming paghahanap? Oo. Madla: Ito mahanap ang unang halaga na mas malaki kaysa sa isa ang iyong hinahanap para sa at pagkatapos ay bumalik hindi totoo. Jason HIRSCHORN: Mismong. Kaya kung ito ay isang pinagsunod-sunod na listahan, kung makuha namin sa isang bagay na mas malaki kaysa sa kung ano kaming naghahanap ng mga, hindi namin kailangang panatilihin ang pagpunta sa dulo ng listahan. Maaari sa puntong iyon kami ng hindi totoo dahil hindi namin pagpunta upang hanapin ito. Ang tanong ay ngayon, na-usapan natin ang tungkol sa pinapanatiling naka-link na listahan pinagsunod-sunod, pinapanatili ang mga ito unsorted. Iyon ay magiging isang bagay ikaw ay marahil pagpunta sa kailangang isipin ang tungkol sa kapag itinakda sa coding problema limang kung ikaw pumili ng isang hash talahanayan na may nakahiwalay na chaining diskarte, na Makikita makipag-usap namin tungkol sa ibang pagkakataon. Ngunit kahalaga ito upang panatilihin ang mga listahan pinagsunod-sunod at pagkatapos ay magagawang siguro mayroon mas mabilis na mga paghahanap? O kaya naman ay mas mabuti upang mabilis na ipasok isang bagay sa pare-pareho ang runtime ngunit pagkatapos ay mayroon na maghanap? Iyan ay isang tradeoff doon na iyong makakuha upang magpasya kung ano ang mas naaangkop para sa iyong partikular na problema. At mayroong hindi kinakailangang isa talagang tamang sagot. Ngunit ito ay tiyak na isang desisyon na makukuha mo upang gawin, at marahil handa na upang ipagtanggol na sa, sabihin nating, ng isa o dalawang puna kung bakit na pinili mo ang isa sa ibabaw ng iba pang mga. Sa wakas, tinatanggal. Nakita namin ang pagtanggal. Ito ay katulad sa paghahanap. Inaasahan naming para sa mga elemento. Sabihin nating sinusubukan naming tanggalin anim. Kaya nakita namin anim dito mismo. Ang bagay na mayroon kami upang matiyak na namin gawin ay na kung ano ang ay tumuturo sa anim - tulad ng nakikita natin sa hakbang dalawang down na dito - ano naman ang nagtuturo sa anim na mga pangangailangan sa laktawan anim ngayon at mababago sa ano naman anim ay tumuturo sa. Hindi namin nais na kailanman ulila ang natitirang bahagi ng ang aming listahan sa pamamagitan ng forgetting upang i-set na nakaraang pointer. At pagkatapos minsan, depende sa programa, ipapakita lang nila tanggalin ang node kabuuan. Minsan gugustuhin mong bumalik ang halaga na ito sa node. Kaya na kung paano pagtanggal ng mga gawa. Ang anumang mga katanungan sa tanggalin? Madla: Kaya kung ikaw ay pagpunta sa tanggalin ito, gagamitin mo lang libre dahil siguro ito ay malloced? Jason HIRSCHORN: Kung gusto mong palayain isang bagay na akmang-akma at mo malloced ito. Sabihing namin pinaghahanap upang bumalik ang halagang ito. Maaari naming ibalik anim at pagkatapos ay libre ito node at tawag libreng on ito. O kaya nais naming marahil tumawag muna libre at pagkatapos ay bumalik sa anim. OK. Kaya ni magpatuloy sa pagsasanay sa coding ipaalam. Kami ay pagpunta sa code tatlong mga pag-andar. Ang unang isa ay tinatawag na insert_node. Kaya mayroon kang code na nag-email ako sa iyo, at kung pinapanood mo ito sa ibang pagkakataon sa Maaari mong i-access ang code sa linked.c sa CS50 website. Ngunit sa linked.c, mayroong ilang mga balangkas code na naka- napawalang para sa iyo. At pagkatapos ay mayroong ilang mga pag-andar kailangan mong magsulat. Una kami ay pagpunta sa sumulat insert_node. At ano ang ginagawa insert_node ay kung pagsingit ng isang integer. At ka pagbibigay ng integer sa isang naka-link na listahan. At sa partikular, kailangan mo upang panatilihin ang mga listahan pinagsunod-sunod mula sa pinakamaliit na pinakamalaking. Gayundin, hindi mo nais na magpasok ng anumang mga nauulit. Panghuli, bilang maaari mong makita insert_node ay nagbabalik ng bool. Kaya ka dapat ipagbigay-alam sa user man o hindi ang insert noon ay matagumpay sa pamamagitan ng pagbalik totoo o hindi. Sa dulo ng programang ito - at para sa hakbang na ito hindi mo kailangang mag-alala tungkol pagbabakante ng kahit ano. Kaya lahat ng ginagawa mo ay pagsasagawa ng isang integer at pagpasok ng mga ito sa isang listahan. Iyon ay kung ano ako humihiling sa iyo na gawin ngayon. Muli, sa linked.c, na kung saan mo lahat ng mayroon, ay ang balangkas ng code. At dapat mong makita patungo sa ibaba ang sample na deklarasyon ng function. Gayunman, bago pagpunta sa coding ito sa C, masidhing kong Hinihikayat ka upang pumunta sa pamamagitan ng hakbang na nakapunta namin pagsasanay sa bawat linggo. Na nawala na kami sa pamamagitan ng isang larawan ng ito. Kaya dapat mayroon kang ilang mga pag-unawa ng kung paano ito gumagana. Ngunit Gusto ko hinihikayat na sumulat ilang pseudocode bago diving in At kami ay pagpunta sa pumunta sa ibabaw pseudocode bilang isang grupo. At pagkatapos ay sa oras na iyong isinulat sa iyong pseudocode, at sa sandaling na-nakasulat na namin ang aming pseudocode bilang isang grupo, maaari kang pumunta sa coding ito sa C. Bilang isang ulo up, ang insert_node function na Marahil ang trickiest ng ang tatlong kami ay pagpunta sa magsulat dahil ako Idinagdag ang ilang karagdagang mga hadlang sa iyong programming, sa partikular na hindi ka pagpunta sa singit kadoble at na ang listahan dapat na manatiling pinagsunod-sunod. Kaya ito ay isang non-walang halaga programa na kailangan mong i-code. At bakit hindi mo tumagal 06:55 minuto lamang upang makakuha ng mga nagtatrabaho sa pseudocode at ang code. At pagkatapos ay magsisimula kami pagpunta bilang isang grupo. Muli, kung mayroon kang lamang anumang mga katanungan itaas ang iyong mga kamay at kukunin ko na dumating sa paligid. . Sa pangkalahatan din namin ang mga - o hindi ko tahasan mong sabihin ay maaaring gumana sa mga tao. Ngunit malinaw naman, ako lubos na hinihikayat ka, kung mayroon kang mga katanungan, upang hilingin sa kapit-bahay upo sa tabi mo o kahit na gumagana sa isang tao iba kung gusto mo. Hindi ito kailangang maging isang indibidwal silent aktibidad. Magsimula tayo sa pagsusulat ng ilang Hayaan pseudocode sa board. Sino ang maaaring magbigay sa akin ang unang linya ng pseudocode para sa programang ito? Para sa mga ito function, sa halip - insert_node. Alden? Madla: Kaya ang unang bagay na ginawa ko noon ay lumikha ng isang bagong pointer sa node at ako nasimulan ito na tumuturo sa parehong bagay na listahan ay tumuturo sa. Jason HIRSCHORN: OK. Kaya lumilikha ka ng isang bagong pointer sa listahan, hindi sa node. Madla: Mag-right. Oo. Jason HIRSCHORN: OK. At pagkatapos ay kung ano ang gusto naming gawin? Ano pagkaraan na? Paano ang tungkol sa mga node? Wala kaming isang node. Mayroon lang namin ng halaga. Kung gusto naming upang magpasok ng isang node, ano ang ginagawa namin kailangan na gawin ang unang bago namin makakaya kahit na isipin ang tungkol sa pagpasok ng mga ito? Madla: Oh, paumanhin. kailangan naming i-malloc espasyo para sa isang node. Jason HIRSCHORN: Mahusay. Ni gawin Hayaan - OK. Hindi ma-maabot na mataas. OK. Kami ay pagpunta sa pumunta down, at pagkatapos ay ginagamit namin ang dalawang mga hanay. Hindi ako maaaring pumunta na - OK. Lumikha ng isang bagong node. Maaari kang lumikha ng isa pang pointer upang ilista o maaari mo lamang gamitin ang listahan bilang umiiral na ito. Wala ka ba talagang kailangan upang gawin iyon. Kaya't lumikha kami ng isang bagong node. Mahusay. Iyon ay kung ano ang ginagawa namin muna. Ano ang susunod? Madla: Maghintay. Dapat ba naming lumikha ng isang bagong node ngayon o dapat maghintay naming matiyak na walang mga doble ng mga node nasa listahan bago namin likhain ito? Jason HIRSCHORN: Magandang katanungan. Ng matagalan na para dahil sa ibang pagkakataon Hayaan ang karamihan ng mga oras lilikha kami isang bagong node. Kaya makikita panatilihin namin na dito. Ngunit iyon ay isang mahusay na tanong. Kung lumikha namin ito at nakita namin isang duplicate, ano ang dapat ginagawa namin bago bumalik? Madla: Palayain ito. Jason HIRSCHORN: Oo. Malamang palayain ito. OK. Ano ang gagawin namin pagkatapos naming lumikha ng isang bagong node? Annie? Madla: ilagay namin ang numero sa node? Jason HIRSCHORN: Mismong. Ilagay namin ang bilang - malloc namin espasyo. Pupunta ako sa umalis na lahat bilang isang linya. Ngunit ikaw ay karapatan sa iyo. Malloc namin na espasyo, at pagkatapos ay ilalagay namin ang bilang in Maaaring itakda ng kahit na namin ang pointer bahagi nito sa null. Iyan ay akmang-akma. At pagkatapos ay kung ano ang tungkol sa pagkatapos na? Iginuhit namin ang larawang ito sa board. Kaya kung ano ang gagawin namin? Madla: pumunta kami sa listahan. Jason HIRSCHORN: Pumunta sa pamamagitan ng listahan. OK. At ano ang gagawin namin masuri para sa bawat node. Kurt, ano ang gagawin suriin namin para sa bawat node? Madla: Tingnan kung ang mga halaga ng n na node ay mas malaki sa halaga n sa aming mga node. Jason HIRSCHORN: OK. Pupunta ako sa gawin - oo, ang OK. Kaya n - Pupunta ako sa sabihin kung halaga ay mas malaki kaysa ito node, pagkatapos ay i-ano ang gagawin namin gawin? Madla: Well, pagkatapos ay ipasok namin ang bagay na bago mismo iyon. Jason HIRSCHORN: OK. Kaya kung ito ay mas mataas kaysa ito, pagkatapos ay nais naming isingit. Ngunit nais naming ipasok ito bago mismo dahil magdudulot din na kailangan namin upang maging pagpapanatili ng track, pagkatapos, ng kung ano ang bago. Kaya magpasok ng mga bago. Kaya marahil hindi inaabot kami ng isang bagay mas maaga sa. Marahil kailangan namin upang ma-pagpapanatiling subaybayan kung ano ang nangyayari sa. Ngunit babalikan ka namin doon. Kaya kung ano ang halaga ay mas mababa kaysa? Kurt, ano ang gagawin namin kung halaga ay mas mababa kaysa? Madla: Pagkatapos panatilihin mo lamang ng pagpunta maliban kung ito ay ang huli. Jason HIRSCHORN: gusto ko na. Kaya pumunta sa susunod na node. Maliban kung ito ay ang huling isa - marahil kami ay naghahanap ng mga na sa mga tuntunin ng kundisyon. Ngunit oo, susunod na node. At na pagkuha ng masyadong mababa, kaya ipapakita namin Ililipat nito ang dito. Ngunit kung - Maaari nang makita ang lahat ng tao? Kung hindi namin katumbas anong gagawin namin? Kung ang halaga sinusubukan naming isingit ay katumbas ng halaga na node na ito? Oo? Madla: [hindi marinig]. Jason HIRSCHORN: Oo. Given na ito - Marcus ang tama. Maaari siguro namin nagawa na isang bagay na naiiba. Ngunit ibinigay na nilikha namin ito, dito dapat naming palayain at pagkatapos ay bumalik. Oh batang lalaki. Iyan ba ang mas mainam? Paano iyan? OK. Libreng at pagkatapos ay kung ano ang ginagawa namin bumalik, [hindi marinig]? OK. Nawawala namin ang anumang bagay? Kaya kung saan ay namin pinapanatili track ng bago node? Madla: Sa tingin ko gusto ito pumunta pagkatapos lumikha ng isang bagong node. Jason HIRSCHORN: OK. Kaya sa simula kami ay marahil - oo, maaari naming lumikha ng isang pointer sa isang bagong node, tulad ng isang nakaraang node pointer at isang kasalukuyang node pointer. Kaya ni isingit na dito ipaalam. Lumikha ng kasalukuyan at nakaraang mga payo sa mga node. Ngunit kapag ako ayusin namin ang mga payo? Saan ang gagawin namin na sa code? Jeff? Madla: - kundisyon halaga? Jason HIRSCHORN: Aling isa sa mga partikular na? Madla: ako malito lang. Kung halaga ay mas mataas kaysa ito node, ay hindi na ibig sabihin na gusto mong pumunta sa susunod na node? Jason HIRSCHHORN: Kaya kung ang aming halaga ay mas mataas kaysa sa halaga ng mga ito na node. Madla: Oo, pagkatapos gusto mo gusto upang pumunta mas ibaba pa ng linya, i-right? Jason HIRSCHHORN: Mag-right. Kaya hindi kami ipasok ito dito. Kung halaga ay mas mababa kaysa ito node, pagkatapos ay pumunta kami sa susunod na node - o pagkatapos namin magpasok ng mga bago. Madla: Maghintay, na ito node at kung ano ang halaga? Jason HIRSCHHORN: Magandang katanungan. Halaga ng bawat kahulugan ng function na ito ay kung ano ang kami ay naibigay na. Kaya halaga ay ang bilang namin ibinigay. Kaya kung ang halaga ay mas mababa kaysa ito node, kailangan namin ng oras upang ipasok. Kung halaga ay mas mataas kaysa ito node, pumunta kami sa susunod na node. At bumalik sa orihinal na pinag-uusapan, bagaman, kung saan - Madla: Kung halaga ay mas malaki kaysa ito node. Jason HIRSCHHORN: At kaya ano ang gagawin namin dito? Sweet. Iyon ay tama. Lamang ako ng pagpunta sa magsulat update ng mga payo. Ngunit oo, gamit ang mga kasalukuyang isa Gusto mo itong i-update sa ituro sa susunod na isa. Ano pa nawawala namin? Kaya pupuntahan ko type ito code sa gedit. At habang ginagawa ko ito, maaari kang magkaroon ng isang ilang higit pang minuto upang gumana sa coding ito sa C. Kaya ba akong magkaroon ang pseudocode input. Isang maikling paalala bago kami makapagsimula. Maaaring hindi namin magagawang ganap tapusin ito sa lahat tatlong ng mga function. May tamang solusyon upang ang mga ito na ako ng email out sa iyo guys pagkatapos ng seksyon, at magpo ito mapo-post sa CS50.net. Kaya hindi ko hinihikayat ka upang pumunta tingnan ang mga seksyon. Hinihikayat ka kong subukan ang mga sa iyong pagmamay-ari, at pagkatapos ay gamitin ang mga kasanayan mga problema upang suriin ang iyong mga sagot. Ang mga ito ay ang lahat ng na-dinisenyo upang malapit umuugnay sa at sumunod sa kung ano kailangan mo lang gawin sa hanay problema. Kaya ko hinihikayat na pagsasanay na ito sa iyong sariling at pagkatapos ay gamitin ang code na ito sa suriin ang iyong mga sagot. Dahil ko nais upang lumipat sa hash mga talahanayan sa isang punto sa seksyon. Kaya maaaring hindi namin makuha sa pamamagitan ng lahat ng ito. Ngunit gagawin namin bilang magkano kaya namin ngayon. OK. Ipaalam sa amin magsimula. Asam, paano ako lilikha kami ng isang bagong node? Madla: mo struct *. Jason HIRSCHHORN: Kaya namin mayroon dito na up. Oh, paumanhin. Ay sinasabi mo struct *. Madla: At pagkatapos [? uri?] node o c node. Jason HIRSCHHORN: OK. Pupunta ako sa tumawag ito new_node upang maaari naming manatili pare-pareho. Madla: At gusto mong i-set na upang magtungo, ang unang node. Jason HIRSCHHORN: OK. Kaya ngayon ito pagturo sa - kaya ito ay hindi pa lumilikha ng isang bagong node. Ito ay lamang ng pagturo sa unang node sa listahan. Paano ako lilikha ng isang bagong node? Kung kailangan ko na espasyo upang lumikha ng isang bagong node. Malloc. At kung gaano kalaki? Madla: Ang laki ng struct. Jason HIRSCHHORN: Ang laki ng struct. At ano ang mga struct tinatawag? Madla: Node? Jason HIRSCHHORN: Node. Kaya malloc (sizeof (node)); Binibigyan kami ng espasyo. At ay ang linyang ito - isang bagay ay mali sa linyang ito. New_node ay isang pointer sa isang struct? Yan ang generic na pangalan. Ano ito - node, eksakto. Ito ay isang node *. At kung ano ang gagawin namin pagkatapos malloc kami ng isang bagay, Asan? Ano ang unang bagay na aming ginagawa? Paano kung hindi ito gumana? Madla: Oh, tingnan kung ito tumuturo sa node? Jason HIRSCHHORN: Mismong. Kaya kung new_node mo ay katumbas Kapantay null, anong gagawin namin? Nagbalik ito ng bool, ito function. Mismong. Mukhang magandang. Anumang bagay upang idagdag doon? Susubukan naming magdagdag ng mga bagay sa dulo. Ngunit na sa ngayon ay mukhang mahusay. Lumikha ng kasalukuyan at nakaraang mga payo. Michael, paano ang gagawin ko ito? Madla: Gusto mong magkaroon ng na gawin ang isang node *. Ang kailangan mong i gumawa ng isa hindi para new_node ngunit para sa nodes namin ay mayroon. Jason HIRSCHHORN: OK. Kaya ang kasalukuyang node kami sa. Tatawag ako na curr. Ayos lang. Nagpasya kaming gusto naming panatilihing dalawa dahil kailangan naming malaman kung ano ang bago ito. Ano ang gagawin nila makakuha ng nasimulan upang? Madla: Ang kanilang mga halaga sa aming listahan. Jason HIRSCHHORN: Kaya kung ano ay ang unang bagay na sa aming listahan? O kaya paano ko malalaman namin kung saan ang simula ng aming listahan ay? Madla: Ay hindi ito pumasa sa sa ang pag-andar? Jason HIRSCHHORN: Mag-right. Ito ay ang pumasa sa dito mismo. Kaya kung ito ay pumasa sa sa pag-andar, ang magsimula ng listahan, kung ano ang dapat naming itakda kasalukuyang katumbas? Madla: List. Jason HIRSCHHORN: Listahan. Iyan ay akmang-akma. Ngayon ay may mga ito sa address ng simula ng aming listahan. At kung ano ang tungkol sa nakaraang? Madla: Listahan minus isa? Jason HIRSCHHORN: Mayroong walang bago ito. Kaya kung ano ang maaari naming gawin upang walang maging tanda ng? Madla: Walang bisa. Jason HIRSCHHORN: Oo. Iyan tulad ng isang magandang ideya. Perpekto. Salamat sa inyo. Pumunta sa listahan. Constantine, kung gaano katagal kami makapupunta upang pumunta sa pamamagitan ng listahan? Madla: Hanggang sa maabot namin null. Jason HIRSCHHORN: OK. Kaya kung, habang, para sa loop. Anong ginagawa namin? Madla: Siguro isang para sa loop? Jason HIRSCHHORN: ni gawin ang isang para sa loop Hayaan. OK. Madla: At sinasabi namin para sa - hanggang sa kasalukuyang pointer ay hindi kapantay sa null. Jason HIRSCHHORN: Kaya kung malaman namin ang mga kalagayan, kung paano namin maaaring sumulat ng loop batay off ang kundisyon na. Anong uri ng isang loop ay dapat naming gamitin? Madla: Habang. Jason HIRSCHHORN: Oo. Na ginagawang higit pang kahulugan batay off ng kung ano ang iyong sinabi. Kung gusto lang namin upang pumunta sa naming ginagawa ito alam lang bagay na iyon, magiging gumawa pakiramdam na gawin ang isang habang loop. Habang kasalukuyang hindi gumagana ang pantay na null, kung halaga ay mas mababa kaysa ito node. Akshar, ibigay sa akin ang linyang ito. Madla: Kung kasalukuyang-> n n mas mababa sa halaga. O i-reverse na. Lumipat na bracket. Jason HIRSCHHORN: Paumanhin. Madla: Baguhin ang bracket. Jason HIRSCHHORN: Kaya kung ito ay mas malaki kaysa sa halaga. Dahil na nakalilito sa magkomento sa itaas, ako pagpunta sa gawin iyon. Ngunit oo. Kung ang aming halaga ay mas mababa kaysa ito node, anong gagawin namin? Oh. Mayroon akong ito dito mismo. Magpasok ng bago. OK. Paano ginagawa namin iyon? Madla: Ito ba ay pa rin sa akin? Jason HIRSCHHORN: Oo. Madla: mo - new_node-> susunod. Jason HIRSCHHORN: Kaya kung ano ang na pagpunta sa kasing-halaga? Madla: Ito ay pagpunta sa pantay na kasalukuyang. Jason HIRSCHHORN: Mismong. At gayon ang iba pang mga - ano pa ang kailangan naming i-update? Madla: Tingnan kung ang nakalipas ay katumbas null. Jason HIRSCHHORN: Kung Nakaraan - kaya kung nakaraan ay katumbas null. Madla: Iyon ay nangangahulugang ito ay pagpunta upang maging pinuno. Jason HIRSCHHORN: paraan Iyon ito ay naging pinuno. Kaya pagkatapos ay kung ano ang gagawin namin? Madla: Ginagawa namin ang ulo ay katumbas ng new_node. Jason HIRSCHHORN: Head ay katumbas ng new_node. At bakit magtungo dito, ilista? Madla: Dahil ang ulo ay isang pandaigdigang variable, kung saan ay ang panimulang lugar. Jason HIRSCHHORN: Sweet. OK. At - Madla: Pagkatapos mo pa Nakaraan-> susunod ay katumbas ng new_node. At pagkatapos ay bumalik ka totoo. Jason HIRSCHHORN: Saan gawin itinakda namin new_node dulo? Madla: gagawin ko - Ako magse-set na sa simula. Jason HIRSCHHORN: Kaya kung ano line? Madla: Pagkatapos ng kung pahayag check kung ito ay kilala. Jason HIRSCHHORN: Kanan dito? Madla: gusto kong gawin new_node-> n ay katumbas ng halaga. Jason HIRSCHHORN: Magaling. Marahil ito ang may katuturan - hindi namin kailangan malaman kung ano ang listahan kami sa dahil kami ay lamang pakikitungo may isang listahan. Kaya ng mas mahusay na pag-andar na pagpapahayag para sa ito ay isa lamang sa mapupuksa ito ganap at ipasok lamang isang halaga sa ulo. Hindi namin kahit na kailangang malaman kung ano ang listahan Ikinalulungkot namin in Ngunit ako ay panatilihin ito para sa ngayon at pagkatapos ay baguhin ito sa pag-update ang mga slide at code. Kaya mukhang mahusay para sa ngayon iyon. Kung halaga - kung sino ang maaaring gawin ang linyang ito? Kung - ano ang gagawin namin dito, si Noah. Madla: Kung halaga ay mas malaki kaysa curr-> n - Jason HIRSCHHORN: Paano ako pumunta kami sa susunod na node? Madla: Curr-> n ay katumbas ng new_node. Jason HIRSCHHORN: Kaya n ay anong bahagi ng struct? Ang integer. At new_node ay isang pointer sa isang node. Kaya kung ano ang bahagi ng curr dapat naming i-update? Kung hindi n, pagkatapos ay kung ano ang iba pang mga bahagi? Noah, ano ang iba pang mga bahagi. Madla: Oh, susunod. Jason HIRSCHHORN: Susunod, eksakto. Mismong. Susunod ay ang tama. At ano pa ang kailangan namin upang i-update, si Noah? Madla: Ang mga payo. Jason HIRSCHHORN: Kaya update namin kasalukuyang. Madla: Nakaraan-> susunod. Jason HIRSCHHORN: Oo. OK, ipapakita namin i-pause. Sino ang maaaring makatulong sa amin dito? Manu, ano ang dapat naming gawin? Madla: Mayroon kang i-set ito katumbas ng curr-> susunod. Ngunit gawin iyon bago ang nakaraang mga line. Jason HIRSCHHORN: OK. Ano pa? Akshar. Madla: Hindi sa tingin ko ikaw ay sinadya upang baguhin curr-> susunod. Sa tingin ko ka sinadya upang gawin curr Kapantay curr-> sa tabi ng pumunta sa susunod na node. Jason HIRSCHHORN: Kaya paumanhin, saan? Sa anong linya? Ng linyang ito? Madla: Oo. Gawing curr ay katumbas curr-> susunod. Jason HIRSCHHORN: Kaya na ay tama dahil kasalukuyang ay isang pointer sa isang node. At gusto namin ito upang tumuro sa susunod node ng kung ano ang pagkuha sa kasalukuyan itinuturo sa. Curr mismo ay may susunod. Ngunit kung kami ay i-update ang curr.next, namin ay ina-update ang aktwal na tala mismo, hindi kung saan ito pointer ay pagturo. Paano ang tungkol sa linyang ito, bagaman. Avi? Madla: Nakaraan-> susunod ay katumbas curr. Jason HIRSCHHORN: Kaya muli, kung nakaraan ay isang pointer sa isang node, nkrn-> susunod ay ang aktwal na pointer sa node. Kaya ito ay isang pag-update pointer sa isang node sa curr. Hindi namin nais na i-update isang pointer sa isang node. Gusto naming i-update ang nakaraang. Kaya kung paano ang gagawin namin na? Madla: Ito ay lamang ay Nakaraan. Jason HIRSCHHORN: Mag-right. Nakaraan ay isang pointer sa isang node. Ngayon kami ay ang pagbabago nito sa isang bagong pointer sa isang node. OK Ipaalam sa amin ilipat pababa. Sa wakas, ito huling kondisyon. Jeff, ano ang gagawin namin dito? Madla: Kung halaga ay katumbas ng curr-> n. Jason HIRSCHHORN: Paumanhin. Oh aking kabutihan. Ano? Halaga == curr-> n. Ano ang gagawin namin? Madla: gusto mo palayain ang aming new_node, at pagkatapos ay gusto mong bumalik hindi totoo. Jason HIRSCHHORN: Ito ay kung ano ang na namin ang nakasulat sa ngayon. Mayroon kahit ano ba ang kahit sino upang magdagdag ng mga bago namin gawin? OK. Subukan na ito Hayaan. Maaaring maabot Control dulo ng isang hindi-walang bisa function. Avi, ano kaya ang nangyari? Madla: Sigurado ka dapat na ilagay return totoo sa labas ng habang loop? Jason HIRSCHHORN: hindi ko alam. Huwag ako gusto mong? Madla: Hindi na bale. Hindi. Jason HIRSCHHORN: Akshar? Madla: Sa tingin ko mo nilalayong ilagay return false sa dulo ng habang loop. Jason HIRSCHHORN: Kaya kung saan nais mo ito upang pumunta? Madla: Tulad ng sa labas ng habang loop. Kaya kung lumabas ka ng habang loop sa paraan na na naabot mo na ang dulo at walang nangyari. Jason HIRSCHHORN: OK. Kaya kung ano ang gagawin namin in dito? Madla: bumalik ka ng hindi totoo doon pati na rin. Jason HIRSCHHORN: Oh, namin gawin ito sa parehong mga lugar? Madla: Oo. Jason HIRSCHHORN: OK. Dapat ba naming pumunta? Oh aking kabutihan. Sorry. Humihingi ako ng paumanhin para sa screen. Uri ng Ito ay freaking out sa amin. Kaya pumili ng opsyon. Zero, per ang code, kapalitan sa programa. Insert One isang bagay. Ni magpasok ng tatlong Hayaan. Insert ay hindi matagumpay. Pupunta ako sa print out. Wala akong anumang bagay. OK. Siguro na noon ay isang parasitiko lamang. Magpasok ng isa. Hindi matagumpay. OK. Tumakbo sa pamamagitan GDB talaga mabilis Hayaang upang tingnan kung ano ang nangyayari. Tandaan gdb. / Ang pangalan ng iyong ay nakakakuha sa amin programa sa GDB. Iyan ba ang marami upang mahawakan? Ang flashing? Malamang. Isara ang iyong mga mata at tumagal ng ilang malalim breaths kung makakuha ka pagod ng pagtingin sa ito. Ako ay GDB. Ano ang unang bagay na gagawin ko sa GDB? Mayroon kaming upang malaman kung ano ang nangyayari sa dito. Ni makita Hayaan. Mayroon kaming anim na minuto upang figure kung ano ang nangyayari. Hatiin pangunahing. At pagkatapos ay kung ano ang gagawin ko? Carlos? Magpatakbo. OK. Hayaan pumili ng isang pagpipilian. At kung ano ang ibig N gawin? Susunod. Oo. Madla: ba hindi mo banggitin - Hindi mo sabihin na ang ulo, ito ay nasimulan na null sa simula. Ngunit Akala ko kayo ay sinabi na noon ay OK. Jason HIRSCHHORN: Sabihin pumunta - tingnan natin hayaan sa GDB, at pagkatapos ay gagamitin namin bumalik. Ngunit ito tunog tulad ng mayroon ka ilang mga ideya tungkol sa kung ano ang nangyayari sa. Kaya gusto namin upang magpasok ng isang bagay. OK. Kami ay isingit. Mangyaring magpasok ng isang int. Susubukan naming magpasok ng tatlo. At pagkatapos ay ako sa linyang ito. Paano pumunta ko sisimulan ang pag-debug ang insert kilalang function na? Oh aking kabutihan. Iyan ay isang pulutong. Ay na freaking out ng maraming? Madla: Oh, namatay ito. Jason HIRSCHHORN: Kakalagay ko lang na nakuha ito. OK. Madla: Siguro ito ang iba pang mga dulo ng wire. Jason HIRSCHHORN: Wow. Kaya ang bottom line - ano ang sasabihin mo? Madla: sinabi ko ang kabalintunaan ng teknikal na mga kahirapan sa class na ito. Jason HIRSCHHORN: Alam ko. Kung lamang nagkaroon ako kontrol sa bahagi na iyon. [Hindi marinig] Iyan mahusay. Bakit hindi ka guys simulan ang pag-iisip tungkol sa ano ang maaari naming nagawa na mali, at hindi namin pabalik sa 90 segundo. Avica, ako pagpunta sa hilingin sa iyo kung paano pumunta sa loob insert_node upang i-debug ito. Kaya ito ay kung saan huli naming huminto. Paano ko pumunta ako sa loob insert_node, Avica, upang suriin kung anong nangyayari sa? Ano utos GDB? Break hindi gusto dalhin ako sa loob. Alam ba ng makwis? Madla: Ano? Jason HIRSCHHORN: Ano GDB utos Gamitin ko ang umalis sa loob ito ng function? Madla: Hakbang? Jason HIRSCHHORN: Hakbang sa pamamagitan ng S. Iyon ay tumatagal sa akin sa loob. OK. New_node mallocing ilang espasyo. Iyon lahat kamukha nito pagpunta. Suriin ni new_node Hayaan. Ito nakuha ang ilang mga memory address. Ni-check Hayaan - na tama ang lahat. Kaya lahat ng bagay dito ay anyong ay gumagana nang tama. Madla: Ano ang pagkakaiba sa sa pagitan ng P at display? Jason HIRSCHHORN: P ibig sabihin ay naka-print. At kaya ka nagtatanong kung ano ang mga pagkakaiba sa pagitan ng na at ito? Sa kasong ito, walang. Ngunit sa pangkalahatan ay mayroong mga ilang mga pagkakaiba. At dapat kang tumingin sa manu-manong ang GDB. Ngunit sa kasong ito, walang. May posibilidad naming gamitin ang naka-print na, bagaman, dahil hindi namin kailangan upang makagawa ng higit pa kaysa sa i-print ang isang solong halaga. OK. Kaya tayo sa 80 linya ng aming code, pagtatakda node * curr katumbas ng listahan. Ipaalam sa amin i-print out curr. Ito ay katumbas ng listahan. Sweet. Maghintay. Ito ay katumbas ng isang bagay. Hindi iyan mukhang tama. May pumunta namin. Ito ay dahil sa GDB, kanan, kung ito ang linya nandoon ka na ay hindi pa pinaandar. Kaya kailangan mo upang aktwal na nagta-type sa tabi ng maisagawa ang linya bago makita ang resulta nito. Kaya dito tayo. Naipatupad na lang namin ang linyang ito, nakaraang katumbas null. Kaya muli, kung i-print namin nakaraang hindi namin makikita ang anumang bagay kakaiba. Ngunit kung talagang execute namin na linya, tatanggalin namin makita na na linya nagtrabaho. Kaya mayroon kaming curr. Yaong parehong mga magandang. Mag-right? Ngayon ay handa kami sa linyang ito dito mismo. Habang curr ay hindi katumbas null. Well, kung ano ang ginagawa katumbas curr? Nakita lang namin ito equaled null. Naka-print na namin ito. Kukunin ko i-print ito muli. Kaya ay na habang loop pagpunta sa execute? Madla: Hindi. Jason HIRSCHHORN: Kaya kapag na-type ko na linya, makikita mo jumped namin ang lahat ng paraan pababa sa ilalim, bumalik hindi totoo. At pagkatapos ay kami ay pagpunta upang bumalik hindi totoo at bumalik sa aming programa at Sa kalaunan i-print out, tulad ng nakita natin, ang insert ay hindi matagumpay. Kaya, kahit sino ay may anumang mga ideya sa kung ano ang kailangan naming gawin upang ayusin ito? Pupunta ako sa maghintay hanggang makita ko isang pares ng mga kamay pumunta up. Hindi namin maisagawa ito. Tandaan, ito ay ang unang bagay namin ang iyong ginagawa. Hindi ako pagpunta sa gawin ng ilang. Pupunta ako sa ginagawa ng ilan. Dahil ilang Nangangahulugan dalawa. Kukunin ko maghintay para sa higit sa dalawa. Ang unang pagpapasok, curr, sa pamamagitan ng default ay katumbas null. At ito loop executes lamang kung curr ay hindi null. Kaya kung paano ang maaari kong makakuha ng paligid na ito? Nakakakita ako ng tatlong mga kamay. Kukunin ko maghintay para sa higit sa tatlong. Marcus, ano ang iyong palagay? Madla: Well, kung kailangan mo ito sa isakatuparan higit sa isang beses, mo lamang baguhin ito sa isang do-loop habang. Jason HIRSCHHORN: OK. Makakaapekto ba na malutas ang aming mga problema, bagaman? Madla: Sa kasong ito hindi dahil sa ang katotohanan na ang listahan ay walang laman. Kaya pagkatapos mo marahil lamang kailangan upang magdagdag ng isang pahayag na kung loop labasan pagkatapos ay mayroon kang upang maging sa dulo ng ang listahan, kung saang punto ka maaaring magpasok lamang ito. Jason HIRSCHHORN: gusto ko na. Iyon ang akma. Kung ang loop lumabas - dahil ito ay bumalik maling dito. Kaya kung ang loop labasan, pagkatapos kami ay sa sa dulo ng listahan, o marahil ang magsimula ng isang listahan kung walang nasa ito, na kung saan ay katulad ng sa dulo. Kaya ngayon gusto naming isingit isang bagay dito. Kaya kung paano na code ay tumingin, Marcus? Madla: Kung na nakuha mo ang node malloced, maaari mo lamang sabihin new_node-> susunod ay katumbas null dahil ito ay dapat na sa dulo. O new_node-> susunod ay katumbas null. Jason HIRSCHHORN: OK. Sorry. New_node-> susunod ay katumbas null dahil kami sa dulo. Hindi iyon ilagay ito in Paano ko ilalagay namin ito sa listahan? Mag-right. Iyon lang ang pag-set ito patas sa. Walang kung paano ginagawa namin talaga ilagay ito sa listahan? Ano ang nagtuturo sa dulo ng listahan? Madla: Head. Jason HIRSCHHORN: Paumanhin? Madla: Head nakaturo sa dulo ng listahan. Jason HIRSCHHORN: Kung walang nasa ang listahan, ulo ay nagtuturo sa dulo ng listahan. Kaya makikita na gumagana para sa unang insertion. Paano ang tungkol sa kung mayroong mga ilang bagay sa listahan? Kaysa hindi namin nais na i-set magtungo ang katumbas ng new_node. Ano ang gusto naming gawin doon? Oo? Marahil nakaraang. Makakaapekto ba na gumagana? Isipin na nakaraang lamang tagaturo patungo sa isang node. At nakaraang ay isang lokal na variable. Kaya ang linyang ito ay magse-set ng isang lokal na variable, nakaraang, na katumbas ng o nakaturo sa mga ito bagong node. Iyan ay hindi talagang ilagay ito sa aming listahan, bagaman. Paano ko ilalagay namin ito sa aming listahan? Akchar? Madla: Sa tingin ko sa iyo gawin kasalukuyang-> susunod. Jason HIRSCHHORN: OK. curr-> susunod. Kaya muli, ang tanging kadahilanan kami pababa dito ay, kung ano ang ginagawa kasalukuyang katumbas? Madla: Kapantay null. Jason HIRSCHHORN: At kaya kung ano ang mangyayari kung gagawin namin null-> susunod? Ano ang gagawin namin pagpunta upang makakuha? Susubukan naming makakuha ng segmentation fault. Madla: Do curr ay katumbas null. Jason HIRSCHHORN: Iyon ang parehong bagay bilang nakaraan, bagaman, dahil mayroong isang lokal na variable kami ng pagtatakda katumbas ito bagong node. Sabihin bumalik sa ating larawan ng pagpasok ng isang bagay. Sabihing kami ng pagpasok sa dulo ng listahan, kaya dito mismo. Mayroon kaming isang kasalukuyang pointer na nakaturo sa mga null at isang nakaraang point na tumuturo sa 8. Kaya kung ano ang kailangan namin upang i-update, Avi? Madla: Nakaraang-> susunod? Jason HIRSCHHORN: Nakaraang-> susunod ay kung ano ang gusto naming i-update dahil na ang talagang ipasok ito sa sa dulo ng listahan. Mayroon pa kaming isa bug, bagaman, na aming pagpunta upang tumakbo sa. Ano iyan bug? Oo? Madla: Ito ay pagpunta upang bumalik hindi totoo sa kasong ito? Jason HIRSCHHORN: Oh, ay ay pagpunta sa bumalik hindi totoo. Subalit mayroong isa pang bug. Kaya kailangan nating ilagay sa mga bumabalik na totoo. Madla: ba ang nakaraang pa rin pantay null sa tuktok ng listahan? Jason HIRSCHHORN: Kaya nakaraang pa rin ay katumbas ng null sa pinakadulo simula. Kaya kung paano maaari naming makakuha ng higit sa na? Oo? Madla: Sa tingin ko ang maaari mong gawin ng isang tseke bago ang habang loop upang makita kung ito ay isang walang laman na listahan. Jason HIRSCHHORN: OK. Kaya sabihin pumunta dito. Gumawa ng isang tseke. Kung - Madla: Kaya kung ulo katumbas ay katumbas null. Jason HIRSCHHORN: Kung ulo katumbas ay katumbas null - na kailangan sabihin sa amin kung ito ay isang walang laman na listahan. Madla: At pagkatapos mo gawin ulo ay katumbas ng bagong. Jason HIRSCHHORN: Head ay katumbas ng new_node? At ano pa ang kailangan naming gawin? Madla: At pagkatapos mong nagbabalik ng tunay. Jason HIRSCHHORN: Hindi masyadong. Kami ay kulang ng isa hakbang. Madla: New_node susunod May upang tumuro sa null. Jason HIRSCHHORN: Eksaktong, Alden. At pagkatapos ay maaari naming nagbabalik ng tunay. OK. Ngunit pa rin ito ng isang magandang ideya na gumawa ng mga bagay sa dulo ng listahan, tama? Ayos lang. Kami ay maaaring aktwal na makakuha pa rin sa dulo ng listahan. Kaya ay ang code na ito fine, kung hindi kami sa matatapos ang listahan at mayroong ilang mga bagay sa listahan? Mag-right? Dahil mayroon pa rin kaming ideya Marcus ni. Maaari naming lumabas ito dahil loop Ikinalulungkot namin sa dulo ng listahan. Kaya gusto namin ito pa rin Code down na dito? Madla: Oo. Jason HIRSCHHORN: Oo. At kung ano ang kailangan namin upang baguhin ito sa? True. Gumagana ba na tunog mahusay sa lahat ng tao sa ngayon? Sinuman ay may anumang mga - Avi, ang mayroon kang isang bagay upang idagdag? Madla: Hindi. Jason HIRSCHHORN: OK. Kaya gumawa kami ng ilang mga pagbabago. Gumawa kami ng mga ito check bago namin nagpunta sa para sa isang walang laman na listahan. Kaya nagsagawa kami ng pag-aalaga ng isang walang laman na listahan. At dito kinuha namin pag-aalaga ng pagpasok isang bagay sa dulo ng listahan. Kaya ito ay tila tulad nito habang loop pagkuha pag-aalaga ng mga bagay sa pagitan, sa isang lugar sa listahan kung may mga bagay sa listahan. OK. Ipaalam sa amin patakbuhin ang program na ito muli. Hindi matagumpay. Madla: Hindi mo ginawa ito. Jason HIRSCHHORN: Oh, Hindi ko gawin itong. Magandang punto, Michael. Magdagdag ng isang make-link Hayaan. Line 87 mayroong isang error. Line 87. Alden, ito ang linya na iyong ibinigay sa akin. Ano ang mali? Madla: upang maging sa null Mayroon itong. Jason HIRSCHHORN: Mahusay. Akmang-akma. Dapat itong maging null. Muli ni gumawa Hayaan. Sumulat ng libro. OK. Ni magpasok ng tatlong Hayaan. Insert Ang ay matagumpay. Mag-print ng ito Hayaan. Oh, kung lamang maaari naming suriin. Ngunit hindi pa namin nagawa ang i-print ang function pa. Hayaan magpasok ng ibang bagay. Ano ang dapat naming ilagay? Madla: Seven. Jason HIRSCHHORN: Seven? Madla: Oo. Jason HIRSCHHORN: Mayroon kaming seg fault. Kaya Nakakuha kami ng isa, ngunit namin malinaw na Hindi maaaring makakuha ng dalawang. Ito ay 05:07. Kaya maaari naming i-debug ito para sa tatlong minuto. Ngunit Pupunta ako upang mag-iwan sa amin dito at lumipat sa hash table. Ngunit muli, ang mga sagot para sa ang code na ito Ay ko ito i-email sa iyo sa isang bit. Kami ay napakalapit na ito. Masidhing kong hinihikayat ka upang malaman kung ano ang nangyayari sa dito at ayusin ito. Kaya magpapadala ako sa iyo ng email ang code na ito bilang well plus solusyon ang - marahil ang solusyon sa susunod. Una ang code na ito. Ang iba pang mga bagay na gusto kong gawin bago namin tapusin ay hindi kami nabakante ng kahit ano. Kaya gusto kong ipakita sa iyo kung ano valgrind kamukha. Kung nagpapatakbo namin ang mga hangganan ng valgrind sa aming programa,. / naka-link. Muli, ayon sa slide na ito, kami dapat tumakbo valgrind na may ilang mga uri ng pagpipiliang ito, sa kasong ito - Tumagas-check = puno na. Kaya hayaan sumulat ng valgrind - Tumagas-check = puno na. Kaya ito ay tatakbo valgrind sa aming programa. At ngayon ang programa aktwal na tumatakbo. Kaya kami ay pagpunta sa patakbuhin ito tulad lamang ng bago, ilagay ang isang bagay in Pupunta ako sa ilalagay sa tatlo. Iyon ay gumagana. Hindi ako pagpunta sa subukan ang ilalagay sa isang bagay iba dahil kami ay pagpunta sa makakuha ng isang seg hindi totoo sa kasong iyon. Kaya ako lamang ang pagpunta sa tumigil. At ngayon mo makita down na dito tumagas at buod magbunton. Ito ang mga mahusay na mga bagay na gusto mong i-check out. Kaya ang buod magbunton - sinasabi nito, sa paggamit sa exit - walong bytes sa isang bloke. Iyon isang bloke ay ang node malloced namin. Michael, sinabi mo bago ang isang node ay walong kagat dahil mayroon itong mga integer at ang pointer. Kaya iyon ang aming mga node. At pagkatapos ay sinasabi nito na ginamit namin malloc pitong beses at hindi na namin napalaya isang bagay anim na beses. Ngunit hindi namin tinatawag na libre, kaya wala akong mga ideya kung ano ito ay pakikipag-usap tungkol sa. Ngunit magkasiya ito upang sabihin na kapag ang iyong nagpapatakbo ng programa, malloc ay tinatawag na sa ilang iba pang mga lugar na aming Hindi kailangang mag-alala tungkol sa. Kaya malloc ay marahil na tinatawag na sa ilang mga lugar. Hindi namin kailangang mag-alala kung saan. Ngunit talaga ito sa amin. Ang unang linya ay sa amin. Iniwan namin na bloke. At maaari mong makita na dito sa buod tumagas. Pa rin naaabot - walong bytes sa isang bloke. Nangangahulugan iyon na memorya - na-leaked namin na memorya. Talagang mawawala - isang bagay ay nawala para sa mabuti. Sa pangkalahatan, hindi mo makita ng kahit ano doon. Pa rin naaabot ay pangkalahatan kung saan makikita mo ang mga bagay, kung saan makikita mo gusto upang tumingin upang makita kung ano ang code dapat mong nabakante ngunit nakalimutan upang palayain. At pagkatapos ay kung ito ay hindi ang kaso, kung ginawa namin libre lahat ng bagay, maaari naming suriin na. Tumakbo ni lamang ang programa Hayaan hindi paglalagay sa kahit ano. Makikita mo ang down na dito sa paggamit sa exit - zero bytes sa zero bloke. Ibig sabihin namin ay may walang kaliwa kapag lumabas sa programang ito. Kaya bago i-in pset6, patakbuhin valgrind at siguraduhin na hindi mo na kailangang anumang memory paglabas sa iyong programa. Kung mayroon kang anumang mga katanungan na may valgrind, huwag mag-atubiling makipag-ugnay. Ngunit ito ay kung paano mo gamitin ito. Napakasimpleng - makita kung mayroon sa paggamit sa exit - anumang bytes sa anumang mga block. Kaya tayo ay nagtatrabaho sa insert node. Mayroon akong dalawang iba pang mga pag-andar dito - i-print ang mga node at libreng mga node. Muli, ang mga ito ay mga pag-andar na pagpunta sa maging mahusay para sa iyo na pagsasanay dahil sila ay makakatulong sa iyo na hindi lamang sa mga sample na magsanay ngunit din sa ang problema set. Sila-map sa medyo malapit sa mga bagay ka ng pagpunta sa mayroon na gawin sa itakda ang problema. Subalit ko nais upang matiyak na pindutin namin sa lahat ng bagay. At hash table ay mahalaga upang din kung ano ang aming ginagawa sa seksyon na ito linggo - o sa hanay problema. Kaya kami ay pagpunta upang tapusin ang seksyon pakikipag-usap tungkol sa hash table. Kung napansin mo ako na ginawa ng isang maliit na hash table. Iyon ay hindi kung ano ang aming pinag-uusapan tungkol sa, gayunpaman. Pinag-uusapan namin ang tungkol sa isang iba't ibang mga uri ng hash talahanayan. At sa kanyang core, isang hash talahanayan ay wala ng higit sa isang array plus isang hash. Kami ay pagpunta sa makipag-usap para sa isang bit lamang sa tiyakin na lahat ng tao naiintindihan kung ano ang isang hash ay. At ako na nagsasabi sa iyo ngayon na ito ay walang anuman higit sa dalawang bagay - isang array at isang hash. At narito ang mga hakbang na ito sa pamamagitan ng na kung saan ito ay nagpapatakbo. Mayroong aming array. Mayroong aming mga function. Sa partikular, hash function kailangan upang gawin ang isang pares ng mga bagay sa mga ito. Pupunta ako sa partikular na makipag-usap tungkol itakda ang problemang ito. Marahil ito ay pagpunta sa kumuha sa isang string. At kung ano ang ito ng pagpunta sa bumalik? Anong uri ng data? Alden? Ibalik ang iyong pag-andar ng hash? Ang isang integer. Kaya ito ay kung ano ang hash Binubuo ang talahanayan ng - isang talahanayan sa anyo ng mga array at isang hash. Paano ito gumagana? Gumagana ito sa tatlong hakbang. Bigyan namin ito isang key. Sa kasong ito, ipapakita namin bigyan ito ng isang string. Tinatawag namin ang hash bawat hakbang isa sa key at makakakuha tayo ng isang halaga. Sa partikular, magpapadala kami sabihin makakakuha tayo ng isang integer. Integer na, mayroong napaka-tukoy na mga limitasyon sa kung ano na integer ay maaaring maging. Sa halimbawang ito, ang aming array ay ng laki tatlo. Kaya kung ano ang mga numero ay maaaring maging na integer. Ano ang hanay ng mga wastong halaga para sa na integer, ang uri pagbabalik ng ito hash? Zero, isa at dalawa. Ang punto ng hash ay upang tayahin ang lugar sa array kung saan ang aming mga key ay pagpunta. May tatlong lamang na posible mga lugar dito - zero, isa, o dalawa. Kaya mas mahusay na ito function na pagbalik zero, isa, o dalawa. Ang ilang mga wastong indice sa array. At pagkatapos ay depende sa kung saan ito ay nagbabalik, maaari mong makita doon array bukas bracket ang halaga. Iyon ay kung saan ilalagay namin ang key. Kaya itapon natin sa kalabasa, makuha namin ang zero. Sa array bracket 0, inilalagay namin ang kalabasa. Ihagis namin sa pusa, makuha namin ang isa. Ilagay namin pusa sa isa. Naglaan na kami ng spider. Kumuha na namin ang dalawa. Ilagay namin spider sa array bracket dalawa. Mas kaya maganda kung ito ay nagtrabaho tulad na. Ngunit sa kasamaang-palad, dahil kakailanganin naming makita, ito ay mas komplikado ng kaunti. Bago kami makarating doon, anumang mga katanungan tungkol sa mga pangunahing set-up ng isang hash talahanayan? Ito ay isang imahe ng eksaktong kung ano ang namin ang iginuhit sa board. Ngunit dahil iginuhit namin ito sa board, ako ako ay hindi pagpunta sa pumunta sa ito sa karagdagang. Mahalaga key, ang magic itim na kahon - o sa kasong ito, tial kahon - ng isang hash naglalagay ng mga ito sa mga bucket. At sa halimbawang ito kami ay hindi paglalagay ng pangalan. Kami ay paglalagay ng mga nauugnay telepono bilang ng mga pangalan sa mga bucket. Ngunit maaari mo nang napakahusay lamang ilagay sa pangalan sa mga bucket. Ito ay lamang ng isang larawan ng kung ano ang kami iginuhit sa board. Mayroon kaming mga potensyal na pitfalls, bagaman. At mayroong dalawang sa mga partikular na slides na gusto kong pumunta sa ibabaw. Ang unang isa ay tungkol sa isang hash. Kaya't tinanong ko ang pinag-uusapan, kung ano gumagawa ng isang mahusay na pag-andar ng hash? Ibinibigay ko ng dalawang mga sagot. Ang una ay na ito ay deterministic. Sa konteksto ng hash function, kung ano ang ibig sabihin nito? Oo? Madla: Maaari itong mahanap ang index sa pare-pareho ang oras? Jason HIRSCHHORN: Iyon ay hindi kung ano ang ibig sabihin nito. Ngunit iyon lamang ang isang magandang hulaan. Kahit sino pa ang magkaroon ng isang hula sa kung ano ang ibig sabihin nito? Iyon isang mahusay na pag-andar ng hash ay deterministic? Annie? Madla: Iyon ay maaari lamang mai-map ng key sa isang lugar sa hash table. Jason HIRSCHHORN: Iyon akmang-akma. Sa bawat oras na inilagay mo sa kalabasa, ito laging nagbabalik zero. Kung inilagay mo sa kalabasa at ang iyong hash function na ay nagbabalik zero ngunit may posibilidad ng pagbabalik ng isang bagay iba pa mas mataas sa zero - kaya siguro maaari itong bumalik isa minsan o dalawang iba pang mga oras - na ay hindi isang mahusay na pag-andar ng hash. Ikaw ay akmang-akma. Ang iyong pag-andar ng hash dapat ibalik ang parehong eksaktong integer, sa kasong ito, para sa ang parehong eksaktong string. Siguro ay nagbabalik nito ang parehong mga eksaktong integer para sa parehong eksaktong string anuman ang capitalization. Ngunit sa kasong iyon pa rin ito deterministic dahil maraming mga bagay ay nama-map papunta sa parehong halaga. Iyon ay pinong. Hangga't mayroon lamang isang output para sa ibinigay na input. OK. Ang ikalawang bagay ay na ito Ibinabalik ng wastong mga indeks. Kami nagdala up na mas maaga. Ito hash - oh batang lalaki - isang hash dapat bumalik wastong mga indeks. Kaya sabihin - sabihin bumalik sa halimbawang ito. Aking hash Binibilang up ang mga titik sa salita. Iyan ang hash. At nagbabalik na integer. Kaya kung mayroon akong mga salita A, ito ay pagpunta sa bumalik isa. At ito ay pagpunta sa ilagay ang isang dito mismo. Paano kung ko bang ilagay sa ang salita bat? Ito ay pagpunta upang bumalik tatlo. Saan kinukuha bat pumunta? Hindi ito magkasya. Ngunit kailangan nito upang pumunta sa isang lugar. Ito ang aking hash talahanayan pagkatapos ng lahat, at kailangang pumunta sa isang lugar ang lahat. Kaya kung saan dapat pumunta bat? Anumang mga saloobin? Guesses? Magandang guesses? Madla: Zero. Jason HIRSCHHORN: Bakit zero? Madla: Dahil tatlong modulo tatlong ay zero? Jason HIRSCHHORN: Tatlong modulo tatlong ay zero. Iyon ay isang mahusay na hula, at iyon ang tama. Kaya sa kasong ito dapat ito marahil pumunta sa zero. Kaya isang mahusay na paraan upang matiyak na ito ng hash nagbabalik lamang ang function ng wastong mga indeks ay sa modulo ito sa pamamagitan ng ang laki ng table. Kung modulo mo ang kahit anong ito babalik sa pamamagitan ng tatlo, lagi ka pagpunta upang makakuha ng isang bagay sa pagitan ng zero, isa, at dalawang. At kung ito laging nagbabalik pitong, at palagi kang modulo sa pamamagitan ng tatlong, ikaw ay palaging pagpunta upang makuha ang parehong bagay. Kaya deterministic pa rin kung modulo mo. Ngunit iyon ay tinitiyak na ang mo hindi kailanman makakuha ng isang bagay - ng di-wastong industriya. Sa pangkalahatan, na modulo dapat mangyari sa loob ng iyong hash. Kaya hindi mo kailangang mag-alala tungkol dito. Ikaw lang ang masisiguro na ito ay isang wastong indice. Ang anumang mga katanungan sa ito potensyal na patibong? OK. At doon pumunta kami. Susunod na mga potensyal na patibong, at ito ang isa malaki. Paano kung mapa dalawang mga susi sa parehong halaga? Kaya may mga dalawang paraan upang mahawakan ang mga ito. Ang unang isa ay tinatawag na linear probing, na ako ay hindi pagpunta sa pumunta sa ibabaw. Ngunit dapat mong maging pamilyar sa kung paano na gumagana at kung ano na. Ang ikalawang isa ako pagpunta sa pumunta sa ibabaw dahil na ay ang isa na marami mga tao ay marahil na nagtatapos up sa pagpapasya gamitin sa kanilang hanay problema. Siyempre, hindi mo na kailangang. Ngunit para sa hanay ng problema, maraming mga tao ay may posibilidad na pumili upang lumikha ng hash talahanayan may nakahiwalay na chaining ipatupad kanilang diksyunaryo. Kaya kami ay pagpunta sa pumunta sa kung ano ang ibig sabihin nito upang lumikha ng hash talahanayan na may hiwalay chaining. Kaya ko bang ilagay sa kalabasa. Ibinabalik nito ang zero. At ko bang ilagay ang kalabasa dito. Pagkatapos ko bang ilagay sa - kung ano ang isa pang Halloween-themed bagay? Madla: Candy. Jason HIRSCHHORN: Candy! Iyon ay isang mahusay na isa. Naglagay ako sa kendi, at kendi Binibigyan din ako zero. Ano ang gagawin ko? Ang anumang mga ideya? Dahil mo ang lahat ng uri ng mga alam ano nakahiwalay chaining ay. Kaya ang anumang mga ideya kung ano ang gagawin? Oo. Madla: ang paglalagay ng string talaga sa hash table. Jason HIRSCHHORN: Kaya kami ay pagpunta sa gumuhit ang magandang ideya sa paglipas dito. OK. Madla: Magkaroon ng hashtable [Hindi marinig] ang pointer na tumuturo sa ang simula ng isang listahan. At pagkatapos ay kalabasa maging unang halaga sa naka-link na listahan at kendi maging ang pangalawang halaga sa naka-link na listahan. Jason HIRSCHHORN: OK. Marcus, na noon ay natitirang. Pupunta ako sa masira na pababa. Marcus ay nagsasabi huwag patungan kalabasa. Iyon ay magiging masama. Huwag maglagay ng kendi sa iba pang lugar. Kami ay pagpunta sa ilagay ang mga ito sa parehong sa zero. Ngunit kami ay pagpunta upang harapin ang paglalagay sa kanila sa zero sa pamamagitan ng paglikha ng isang listahan sa zero. At kami ay pagpunta upang lumikha ng isang listahan ng mga lahat ng bagay na nai-map sa zero. At ang pinakamahusay na paraan natutunan namin upang lumikha ng isang listahan na maaaring lumago at pag-urong pabago-bago ay wala sa loob isa pang array. Kaya hindi isang multi-dimensional array. Ngunit upang lumikha lamang ng isang naka-link na listahan. Kaya kung ano siya ipinanukalang - Pupunta ako upang makakuha ng isang bagong - ay lumikha ng isang array na may mga payo, isang array ng mga payo. OK. Anumang mga ideya o pahiwatig kung ano ang uri ng mga payo ay dapat na? Marcus? Madla: pointer sa - Jason HIRSCHHORN: Dahil sa iyo Sinabi ng isang naka-link na listahan, kaya - Madla: Node mga payo? Jason HIRSCHHORN: Node na pointer. Kung ang mga bagay sa aming naka-link listahan ng mga nodes pagkatapos nila Dapat na node na pointer. At ano ang gagawin kasing-halaga nila sa umpisa? Madla: Walang bisa. Jason HIRSCHHORN: Walang bisa. Kaya mayroong aming walang laman na bagay. Kalabasa ang pagbalik ng zero. Ano ang gagawin namin? Maglakad sa akin sa pamamagitan nito? Talaga, Marcus na nagbigay sa akin. Ibang tao maglakad sa akin sa pamamagitan nito. Ano ang ginagawa namin kapag kami - ito ay mukhang na halos kapareho sa kung ano ang namin ang paggawa lamang. Avi. Madla: Pupunta ako sa maglaan ng hula. Kaya kapag kumuha ka ng kendi. Jason HIRSCHHORN: Oo. Well, nakuha namin kalabasa. Hayaan ang makakuha ng aming unang isa. Mayroon din kaming kalabasa. Madla: ang OK. Kalabasa ang pagbalik ng zero. Kaya mo ilagay ito sa na. O kaya naman talaga, inilagay mo ito sa naka-link na listahan. Jason HIRSCHHORN: Paano ginagawa namin ilagay ito sa naka-link na listahan? Madla: Oh, ang aktwal na syntax? Jason HIRSCHHORN: maglakad lang - sabihin pa. Ano ang gagawin namin? Madla: ipasok mo lang ito bilang unang node. Jason HIRSCHHORN: OK. Kaya mayroon kaming ang aming node, kalabasa. At ngayon paano ko isingit ko ito? Madla: magtalaga ka ito sa pointer. Jason HIRSCHHORN: Aling pointer? Madla: Ang pointer sa zero. Jason HIRSCHHORN: Kaya kung saan ang puntong ito? Madla: Upang null ngayon. Jason HIRSCHHORN: Well, ito ay tumuturo sa null. Ngunit ako ng paglalagay sa kalabasa. Kaya kung saan ito dapat na ituro? Madla: Upang kalabasa. Jason HIRSCHHORN: Upang kalabasa. Mismong. Kaya ito nagtuturo sa kalabasa. At kung saan ginagawa ang pointer sa kalabasa punto? Upang Madla: Walang bisa. Jason HIRSCHHORN: Upang null. Mismong. Kaya ipinasok na lamang kami ng isang bagay papunta sa naka-link na listahan. Sinulat ni lang namin ang code na ito upang gawin ito. Halos halos nakuha namin ito ganap na may lamat. Ngayon isingit namin kendi. Ang aming kendi napupunta din sa zero. Kaya kung ano ang gagawin namin sa kendi? Madla: Depende ito sa kung o hindi namin sinusubukan upang ayusin ito. Jason HIRSCHHORN: Iyon akmang-akma. Depende ito sa kung o hindi sinusubukan naming uri-uriin ito. Ipagpalagay nating hindi kami Hayaan pagpunta upang ayusin ito. Madla: Well pagkatapos, bilang namin tinalakay bago, ito ay pinakasimpleng lamang upang ilagay ito karapatan sa simula kaya ang pointer mula sa zero ang mga puntos sa kendi. Jason HIRSCHHORN: OK. I-hold on. Hayaan akong lumikha ng kendi dito mismo. Kaya ito pointer - Madla: Oo, dapat ngayon ay tumuturo sa kendi. Pagkatapos mayroon ang pointer mula sa kendi punto upang kalabasa. Jason HIRSCHHORN: Tulad ng mga iyon? At sabihin Nakakuha kami ng isa pang bagay upang i-map sa zero? Madla: Well, lamang sa iyo gawin ang parehong bagay? Jason HIRSCHHORN: Gawin ang parehong bagay. Kaya sa kasong ito, kung hindi namin nais na panatilihin itong pinagsunod-sunod ito tunog sa halip simple. Isinasaalang-alang namin ang pointer sa indice ibinigay sa pamamagitan ng aming hash. Mayroon kaming puntong iyon sa aming bagong node. At pagkatapos ay ang kahit anong ito ay tumuturo sa dati - sa kasong ito null, sa pangalawang kaso kalabasa - na, kahit anong ito ay tumuturo sa dati, idagdag namin sa susunod ng ang aming bagong node. Kami ay pagpasok ng isang bagay sa simula. Sa katunayan ito ay isang pulutong mas simple kaysa sinusubukan upang panatilihin ang mga listahan pinagsunod-sunod. Ngunit muli, searching ay magiging higit pang mga kumplikadong sa dito. Lagi ka naming magkaroon upang pumunta sa dulo. OK. Ang anumang mga katanungan tungkol sa hiwalay na chaining? Paano gumagana? Mangyaring hilingin sa kanila ngayon. Talagang gusto ko upang matiyak na ang lahat maunawaan ito bago magtungo ang out namin. Madla: Bakit inilagay mo kalabasa at kendi sa parehong bahagi ng hash talahanayan? Jason HIRSCHHORN: Magandang katanungan. Bakit inilalagay namin ang mga ito sa parehong bahagi ng hash talahanayan? Well, sa kasong ito ang aming hash babalik ang zero para sa parehong sa kanila. Kaya kailangan nila upang pumunta sa indice zero dahil na kung saan kami ay pagpunta sa hanapin ang mga ito kung namin kailanman gusto upang tumingin up ang mga ito. Muli, may isang linear probing diskarte hindi namin malalaman ilagay ang mga ito sa parehong sa zero. Ngunit sa hiwalay na chain diskarte, kami ay pagpunta sa ilagay ang mga ito sa parehong sa zero at pagkatapos ay lumikha ng isang listahan off ng zero. At hindi namin nais na i-overwrite kalabasa lamang para sa na dahil pagkatapos kami ay ipagpalagay na ang kalabasa noon ay hindi ipinapasok. Kapag patuloy pa lang namin ang isang bagay sa lokasyong iyon ay magiging masama. Pagkatapos doon ay magiging walang pagkakataon sa atin kailanman - kung kailanman namin ay may isang duplicate, pagkatapos namin Gusto burahin lamang ang aming paunang halaga. Kaya na ang dahilan kung bakit ginagawa namin ang paraan na ito. O kaya na ang dahilan kung bakit namin pinili - ngunit muli, namin pinili mo ang nakahiwalay chaining diskarte, kung saan mayroong maraming iba pang mga approach na ito maaaring isa piliin. Na sagutin ang iyong tanong? OK. Carlos. De-probing ay kasangkot - kung nakita namin ang isang banggaan sa zero, namin magiging ganito sa susunod na lugar upang makita kung ito ay bukas at ilagay ito doon. At pagkatapos ay tinitingnan namin sa susunod na isport at makita kung na noon ay bukas at ilagay ito doon. Kaya nakita namin sa susunod na magagamit bukas na puwesto at ilagay ito doon. Anumang iba pang mga katanungan? Oo, Avi. Madla: Bilang isang follow up sa na, kung ano ang ibig mong sabihin sa pamamagitan ng susunod na puwesto? Sa hash talahanayan o sa isang naka-link na listahan. Jason HIRSCHHORN: Para sa linear programming, walang naka-link na mga listahan. Ang susunod na lugar sa hash table. Madla: ang OK. Kaya ang hash talahanayan ay magiging nasimulan sa laki - tulad ng bilang ng mga string na ikaw ay pagpasok? Jason HIRSCHHORN: ginagawa mo gusto mo itong maging talagang malaki. Oo. Narito ang isang larawan ng kung ano ang aming iginuhit lang sa board. Muli, mayroon kaming isang banggaan dito mismo. sa 152. At makikita mo na nilikha namin naka-link na listahan off nito. Muli, ang hash talahanayan nakahiwalay chaining diskarteng ito ay hindi ang sa iyo mayroon na kumuha para sa set ng mga problema anim ngunit isa na may maraming mga mga mag-aaral ay may posibilidad na tumagal. Kaya sa na tala, ipaalam sa amin sa madaling sabi-usapan bago magtungo ang out namin tungkol sa problema anim, at pagkatapos ay kukunin ko na ibahagi ang isang kuwento sa iyo. Mayroon kaming tatlong minuto. Problema set anim. Mayroon kang apat na mga pag-andar - pagkarga, suriin, laki, at alisan ng bala. Mag-load ng - well, kami ay pagpunta sa ibabaw ng pagkarga ngayon lang. Iginuhit kami ng pag-load sa board. At kami makapagsimula sa coding ng maraming kahit pagpasok sa isang naka-link na listahan. Kaya pagkarga ay hindi magkano ang higit sa ano na lamang na ginagawa namin. Check ay isang beses mayroon kang isang bagay-load. Ito ay ang parehong proseso sa ito. Ang parehong unang dalawang bahagi kung saan mo itapon isang bagay sa hash at kumuha ng mga halaga nito. Ngunit ngayon hindi namin pagpasok dito. Ngayon kaming naghahanap ng mga ito. Ako sample code na isinulat para sa paghahanap ng isang bagay sa isang naka-link na listahan. Hinihikayat kita na pagsasanay na iyon. Ngunit intuitively sa paghahanap ng isang bagay ay medyo kapareho sa pagpasok ng isang bagay. Sa katunayan, iginuhit kami ng isang larawan ng paghahanap isang bagay sa isang naka-link na listahan, gumagalaw sa pamamagitan ng hanggang sa nakuha mo sa dulo. At kung nakuha mo sa dulo at ay hindi maaaring hanapin ito, pagkatapos ito ay hindi doon. Kaya na tseke, mahalagang. Susunod ay ang laki. Laktawan ng laki Hayaan. Panghuli mo na mag-ibis. Alisan ng bala ay isa hindi pa namin na iginuhit sa board o pa naka-code. Ngunit Hinihikayat ko mong subukan ang coding ito sa aming sample na naka-link listahan halimbawa. Ngunit mag-ibis intuitively ay pareho sa libreng - o Ibig kong sabihin ay katulad ng check. Maliban sa ngayon bawat oras na naka-pagpunta sa pamamagitan ng, ikaw ay hindi lamang ng pagsuri sa makita kung mayroon kang ang iyong mga halaga doon. Ngunit ka pagkuha na node at pagbabakante ito, mahalagang. Iyon ay kung ano ang humihiling sa iyo alisan ng bala ang gagawin. Libreng lahat ng bagay na iyong malloced. Kaya ka ng pagpunta sa pamamagitan ng buong listahan muli, sa pamamagitan ng pagpunta sa buong hash talahanayan muli. Oras na ito ay hindi suriin upang makita kung ano ang doon. Palayain lang kung ano ang doon. At sa wakas laki. Dapat na ipinatupad Laki. Kung hindi mo ipatupad ang laki - Sasabihin kong ito tulad nito. Kung hindi mo ipatupad ang laki sa eksaktong isang linya ng code kabilang ang bumalik pahayag, ikaw ay paggawa laki nang hindi tama. Kaya tiyaking laki, para sa buong disenyo mga punto, ninyo ito ginagawa sa eksaktong isang linya ng code, kabilang ang ang return statement. At wala ka pang mag-impake, Akchar. Sabik Beaver. Nais kong sabihin salamat guys para sa darating na seksyon. Magkaroon ng isang Happy Halloween. Ito ang aking costume. Kukunin ko ay may suot na ito sa Huwebes kung makikita ko sa iyo sa oras ng opisina. At kung gusto mong malaman ang tungkol sa ilang nang higit pa background bilang upang ito costume, huwag mag- libre upang tingnan ang seksyon 2011 para sa isang kuwento sa kung bakit ako ay suot na kalabasa costume. At ito ay isang malungkot na kuwento. Kaya tiyaking mayroon kang ilang tisiyu malapit. Ngunit sa na, kung mayroon kang anumang tanong Kukunin ko manatili sa paligid sa labas pagkatapos ng seksyon. Good luck sa problema itakda anim. At tulad ng dati, kung mayroon kang anumang mga katanungan, ipaalam sa akin.