JASON Hirschhorn: Velkomin á síðuna mína til kafla sjö. Við erum í viku sjö af námskeiðinu. Og þetta komandi Fimmtudagur er Halloween þannig að ég er klæddur upp eins og grasker. Ég gat ekki beygt sig niður til að setja á skóna mína, svo er það þess vegna sem ég er bara þreytandi sokkum. Ég er líka ekki þreytandi neitt undir þetta, svo ég get ekki tekið það af ef það er truflandi að þér. Ég afsökunar fyrirfram fyrir það. Þú þarft ekki að ímynda sér hvað er að gerast. Ég er þreytandi Boxer. Svo það er allt gott. Ég er með lengri sögu um hvers vegna ég er klæddur eins og grasker, en ég ætla að vista það fyrir síðar í þessum kafla vegna þess að ég vil til að byrja. Við höfum mikið af spennandi hlutum að fara yfir í þessari viku. Flest þeirra tengjast beint þessum viku Heimadæmi, stafsetningarvillur. Við erum að fara að vera að fara yfir tengd listum og kjötkássa matskeið fyrir allt hlutanum. Ég setti þessa lista upp í hverri viku, lista yfir úrræði fyrir þig að hjálpa þér með efni á þessu námskeiði. Ef með tapi eða ef útlit fyrir sumir Nánari upplýsingar, kíkja á eitt af þessar auðlindir. Aftur, pset6 er stafsetningarvillur, þessa viku pset. Og það hvetur þig líka, og ég hvetja þig til að nota einhver önnur auðlindir sérstaklega fyrir þessa pset. Sér í lagi þrjú ég hef skráð sig á skjánum - gdb, sem við höfum verið kunnugur og verið að nota fyrir a á meðan nú, er að fara að vera mjög hjálpsamur í þessari viku. Þannig að ég setti það upp hér. En þegar þú ert að vinna með C, þú ættir alltaf að vera með gdb til kemba þinn programs. Þessi vika einnig valgrind. Hefur einhver veit hvað valgrind gerir? Áhorfendur: Það stöðva fyrir leka minni? JASON Hirschhorn: Valgrind stöðva fyrir leka minni. Þannig að ef þú malloc eitthvað í þinn program, þú ert að biðja um minni. Í lok program, hefur þú til að skrifa ókeypis á allt sem þú hefur malloced til þess að gefa minni til baka. Ef þú skrifar ekki frjáls í lok og program kemur að niðurstöðu, Allt mun sjálfkrafa vera leystur. Og fyrir lítil verkefnum, það er ekki það stór samningur. En ef þú ætlar að skrifa lengur í birtingu program þessi hjartarskinn ekki hætta, endilega, í nokkrar mínútur eða A nokkrar sekúndur, þá minni lekur getur orðið gríðarstór samningur. Svo fyrir pset6, von er að þú munt hafa núll minni lekur með forritið þitt. Að athuga fyrir leka minni, hlaupa valgrind og það mun gefa þér sumir ágætur framleiðsla láta þig vita hvort eða ekki allt var ókeypis. Við munum æfa með það seinna í dag, vonandi. Að lokum, breyting stjórn. Þú notaðir eitthvað svipað og það í pset5 við gægjast tól. Leyft þér að líta inn. Þú notaðir líka diff, of, fyrir vandamálið sett sérstakur. En í leyfa þér að bera saman tvær skrár. Þú getur bera saman punktamynd skrá og Upplýsa Hausar starfsmannafundi lausn og lausnin í pset5 ef þú velur að nota það. Diff mun leyfa þér að að gera það, eins vel. Þú getur borið saman rétta svarið fyrir vandamál þessa viku stillt á svarið þitt og sjá hvort það línur upp eða sjá þar sem villur eru. Þeir eru þrjár góðar tól sem þú ættir að nota fyrir þessa viku, og örugglega athuga program með þessum þremur verkfærum áður en þú kveikir það inn Aftur, eins og ég hef getið í hverri viku, ef þú hefur einhverjar athugasemdir fyrir mig - bæði jákvæð og uppbyggileg - ekki hika við að fara á vef neðst á þessari mynd og inntak það þar. Ég þakka virkilega allir og allt álit. Og ef þú gefur mér ákveðin atriði sem Ég get gert til að bæta eða að ég er gera vel að þú vilt mig til að halda áfram, ég tek það til hjarta og virkilega reyna erfitt að hlusta að álit þitt. Ég get ekki lofað að ég ætla að gera allt, þó, eins og að ganga inn grasker búning í hverri viku. Þannig að við erum að fara að eyða megnið af kafla, eins og ég nefndi, að tala um tengd listum og kjötkássa matskeið, sem verður beint við til Heimadæmi í þessari viku. Tengd listum við munum fara yfir tiltölulega fljótt vegna þess að við höfum eytt sanngjarn hluti tíma að fara yfir það í kafla. Og svo við munum fá beint inn í erfðaskrá vandamál fyrir tengd listum. Og þá í lok við munum tala um kjötkássa matskeið og hvernig þeir eiga að þetta viku Heimadæmi. Þú hefur séð þetta númer áður. Þetta er struct, og það er að skilgreina eitthvað nýtt kallað hnút. Og innan hnút það er heil tala hérna og er það bendi til annan hnút. Við höfum séð þetta áður. Þetta hefur verið að koma upp fyrir nokkrar vikur núna. Það sameinar ábendingum sem við höfum verið vinna með, og structs, sem leyfa okkur að blanda saman tveimur ólíkum hlutir í eina tegund gagna. There 'a einhver fjöldi að gerast á skjánum. En allt það ætti að vera tiltölulega þekki þig. Á fyrstu línu, við lýsa nýja hnút. Og þá inni þessi nýjan hnút, setti ég heiltölunni í þeim hnút í eitt. Við sjáum á næstu línu sem ég er að gera printf skipunina, en ég hef óvirkir á printf skipunin því raunverulega mikilvægur hluti er þessi lína hér - new_node.n. Hvað þýðir punktur meina? Áhorfendur: Farðu í hnút og meta n gildi fyrir það. JASON Hirschhorn: Það er nákvæmlega rétt. Punktur þýðir sjá N Part þessarar nýju hnút. Þessi næsta lína gerir hvað? Michael. Áhorfendur: Það skapar annan hnút sem mun benda á nýja hnút. JASON Hirschhorn: Þannig að það skiptir ekki búa til nýja hnút. Það skapar hvað? Áhorfendur: A músina. JASON Hirschhorn: bendi á hnút, eins og sýnt með þessu node * hér. Svo það skapar bendi á hnút. Og hvaða hnút er það bendir til, Michael? Áhorfendur: New hnútur? JASON Hirschhorn: New hnút. Og það er að benda þar vegna þess að við höfum gefið það veffang nýjan hnút. Og nú í þessari línu og við sjáum tvær mismunandi leiðir til tjá það sama. Og ég vildi að benda á hvernig þessir tveir hlutir eru eins. Í fyrstu línu, við dereference bendillinn. Svo förum við í hnút. Það er það sem þetta stjörnu þýðir. Við höfum séð það áður með ábendingum. Fara til hnút. Það er í sviga. Og þá aðgangur í gegnum punktur rekstraraðila n þáttur í þeirri hnút. Svo sem tekur setningafræði við sáum hér og nú nota það með músina. Auðvitað fær það frekar upptekinn ef þú ert að skrifa þá sviga - að stjörnu og að punktur. Það fær lítið upptekinn. Þannig að við höfum sumir Nokkur dæmi um setningarleg sykur. Og þessi lína hérna - ptr_node-> n. Það er sama nákvæmlega hlutur. Svo þessir tvær línur af kóða er jafngildar og mun gera nákvæmlega það sama. En ég vildi benda þeim út áður við förum lengra svo þú skiljir sem raunverulega er þetta hérna bara nokkur dæmi um setningarleg sykur fyrir dereferencing bendillinn og þá að fara að n hluti af því að strúktúrinn. Einhverjar spurningar um þessa mynd? OK. Þannig að við ætlum að fara í gegnum nokkra starfsemi sem þú getur gert á tengd listum. A tengda listanum, muna, er röð af hnúður sem benda til annars. Og við byrjum yfirleitt með músina kallað höfuð, almennt, sem bendir til The fyrstur hlutur í listanum. Svo á fyrstu línu hér, við hafa upprunalega L okkar fyrst. Þannig að hlutur sem þú getur hugsa um - þetta texta hérna sem þú getur hugsað sem bara bendillinn við höfum geymt einhvers staðar að stig að fyrsta frumefni. Og í þessu tengda listanum höfum við fjóra hnúta. Hver hnútur er stór kassi. Stærri kassi inni stór kassi er heiltala hluti. Og þá höfum við bendi hluta. Þessir kassar eru ekki vakin mælikvarði því hversu stór er heiltala í bætum? Hversu stór núna? Fjórir. Og hversu stór er bendillinn? Fjórir. Svo í raun, ef við vorum að teikna þetta að skala bæði kassa væri sama stærð. Í þessu tilfelli, við viljum að setja eitthvað inn í tengda listanum. Svo þú getur séð hérna við erum að setja fimm Við yfirferðar gegnum tengda listanum, finna hvar fimm fer, og þá setja það upp. Skulum brjóta þetta niður og fara svolítið hægar. Ég ætla að benda á borð. Þannig að við höfum hnút okkar fimm sem Við höfum búið í mallocs. Hvers vegna er allir hlæja? Bara að grínast. OK. Þannig að við höfum malloced fimm. Við höfum búið þennan hnút einhvers staðar annars. Við höfum það tilbúið til að fara. Við byrjum á framan lista okkar með tveimur. Og við viljum að setja í raðaða tísku. Þannig að ef við sjáum tvo og við viljum að setja fimm, hvað gerum við þegar við sjáum eitthvað minna en okkur? Hvað? Við viljum setja fimm í þetta tengda listanum, halda það flokkað. Við sjáum númer tvö. Svo hvað gerum við? Marcus? Áhorfendur: Hringdu músina í næsta hnút. JASON Hirschhorn: Og hvers vegna ekki við förum til the næstur einn? Áhorfendur: Vegna þess að það er Næsta hnút í listanum. Og við vitum bara, að öðrum stað. JASON Hirschhorn: Og fimm er meiri en tveir, sér í lagi. Vegna þess að við viljum halda það flokkað. Svo er fimm hærri en tveir. Þannig að við hreyfa á til the næstur einn. Og nú erum við að ná fjórum. Og hvað gerist þegar við náð til? Fimm er hærra en fjórum. Svo við höldum áfram. Og nú erum við klukkan sex. Og hvað sjáum við klukkan sex? Já, Carlos? Áhorfendur: Sex er meiri en fimm. JASON Hirschhorn: Sex er meiri en fimm. Svo er það sem við viljum til að setja inn fimm. Hins vegar skaltu hafa í huga að ef við aðeins hafa eitt bendi hér - Þetta er auka músina okkar sem er fara yfir í gegnum listann. Og við erum að benda á sex. Við höfum misst utan um hvað kemur fyrir sex. Þannig að ef við viljum að setja eitthvað inn Þessi listi halda það flokkað, við líklega þurfa hversu margir ábendingar? Áhorfendur: Tveir. JASON HIRSCHORN: Tveir. Einn til að halda utan um núverandi einn og einn til að halda utan um fyrri einn. Þetta er aðeins ein sér tengda listanum. Það fer einungis einn átt. Ef við hefðum tvöfalt tengda listanum, þar allt var að benda til þings eftir það og málið áður en það, þá við myndum ekki þurfa að gera það. En í þessu tilfelli sem við viljum ekki missa utan um það sem kom á undan okkur ef við þurfum að setja fimm einhvers staðar í miðju. Segja að við vorum að setja níu. Hvað myndi gerast þegar fengum við átta? Áhorfendur: Þú vilt hafa til fá þessi núll punkt. Í stað þess að hafa núll punkt sem þú vilt hafa að bæta þáttur og þá hafa það benda til níu. JASON HIRSCHORN: Einmitt. Svo við fáum átta. Við náð í lok listanum vegna þetta bendir til null. Og nú, í stað þess að hafa það benda til null við hafa það benda til nýjan hnút okkar. Og við setjum bendilinn í nýr hnútur okkar til null. Hefur einhver hefur einhverjar spurningar um að setja? Hvað ef ég er ekki sama um halda lista raðað? Áhorfendur: Stick það á upphafi eða lok. JASON HIRSCHORN: Stick það á upphaf eða endir. Hver einn ættum við að gera? Bobby? Hvers vegna enda? Áhorfendur: Þar sem upphaf er nú þegar fyllt. JASON HIRSCHORN: OK. Í upphafi er þegar fyllt. Hver vill halda því fram gegn Bobby. Marcus. Áhorfendur: Jæja þú vilt sennilega að stafur það í upphafi vegna þess að annars ef þú setur hana á í lok þú vilt hafa til fara yfir allan listann. JASON HIRSCHORN: Einmitt. Þannig að ef við erum að hugsa um Runtime, Runtime innsetning í lok væri n, the stærð af þessu. Hvað er stór O afturkreistingur innsetning í upphafi? Föstu tíma. Þannig að ef þú hefur ekki sama um að halda eitthvað raðað, miklu betra að bara að setja inn í upphafi þessum lista. Og það er hægt að gera í föstu tíma. OK. Næsta aðgerð er að finna, sem öðrum - við höfum orðaði þetta sem leit. En við erum að fara að horfa í gegnum tengda listanum fyrir nokkrum hlut. Þú krakkar hafa séð kóðann fyrir leita áður í fyrirlestrinum. En við svoleiðis bara gerði það með að setja inn, eða að minnsta kosti að setja eitthvað flokkað. Þú horfir í gegnum, fara hnút eftir hnút, þar til þú finnur númerið sem þú ert leita að. Hvað gerist ef þú nærð í lok listanum? Segja að ég er að leita að níu og ég ná í lok listanum. Hvað gerum við? Áhorfendur: return false? JASON HIRSCHORN: return false. Við fundum hann ekki. Ef þú nærð í lok listanum og þú ekki finna númerið sem þú ert leita að, er það ekki þar. Einhverjar spurningar um finna? Ef þetta var raðað lista, hvað myndi vera öðruvísi til að leita okkar? Já. Áhorfendur: Það myndi finna fyrstu gildi sem er meiri en sá þú ert að leita að og þá return false. JASON HIRSCHORN: Einmitt. Þannig að ef það er raðað lista, ef við fáum að eitthvað sem er stærra en það sem við erum að leita að, þá þurfum við ekki að halda áfram til loka listanum. Við getum á þeim tímapunkti return false vegna þess að við erum ekki að fara að finna það. Spurningin er nú, höfum við talað um halda tengd listum raðað, halda þeim óflokkað. Það er að fara að vera eitthvað sem þú ert líklega að fara að þurfa að hugsa um þegar erfðaskrá vandamál setja fimm ef þú velja kjötkássa borð með aðskildum chaining nálgun, sem við munum tala um síðar. En er það þess virði að halda lista raðað og þá geta kannski hafa fljótari leit? Eða er betra að fljótt setja eitthvað í stöðugri afturkreistingur en þá hafa lengur að leita? Það er tradeoff rétt þar sem þér fá að ákveða hvað er meira viðeigandi fyrir tiltekna vandamál þitt. Og það er ekki endilega eitt algerlega rétt svar. En það er vissulega ákvörðun sem þú færð að gera, og líklega gott að verja að í, segjum, athugasemd eða tveir af hverju þú velur einn yfir annan. Að lokum, eyða. Við höfum séð að eyða. Það er svipað og að leita. Við erum að leita að frumefni. Segja að við erum að reyna að eyða sex. Þannig að við að finna sex hérna. Það sem við verðum að tryggja að við gera er að allt bendir til sex - eins og við sjáum í skrefi tveir hérna - hvað er að benda á sex þarf að sleppa sex núna og hægt að breyta til hvað sex bendir til. Við viljum ekki að alltaf munaðarlaus restina af lista okkar með að gleyma að setja sem Fyrri músina. Og þá stundum, eftir á dagskrá, þeir 'réttlátur eyða þennan hnút alveg. Stundum þú munt vilja til að fara aftur gildi sem er í þessum hnút. Svo er það hvernig eyða verk. Einhverjar spurningar um að eyða? Áhorfendur: Svo ef þú ert að fara að eyða það, myndir þú nota bara ókeypis vegna væntanlega var það malloced? JASON HIRSCHORN: Ef þú vilt að losa eitthvað sem er nákvæmlega rétt og þú malloced það. Segja að við vildum að skila þetta gildi. Við gætum aftur sex og þá frjáls þennan hnút og kalla ókeypis á það. Eða við myndum líklega kalla frjáls fyrst og síðan aftur sex. OK. Þannig að við skulum fara að æfa forritun. Við erum að fara að kóða þrjár aðgerðir. Sú fyrsta er kallað insert_node. Svo þú ert númer sem ég sendi þér, og ef þú ert að horfa á þetta síðar þú getur fengið aðgang að kóða í linked.c á CS50 website. En í linked.c, það er sumir beinagrind númer sem er þegar verið skrifuð fyrir þig. Og þá er par HLUTVERK þar þú þarft að skrifa. Fyrst við erum að fara að skrifa insert_node. Og hvað insert_node gerir IS setur heiltölu. Og þú ert að gefa heiltölunni í tengda listanum. Og einkum, þú þarft að halda lista raðað frá smæstu til stærstu. Einnig, þú vilt ekki að setja neinar tvítekningar. Að lokum, eins og þú geta sjá insert_node skilar bool. Svo þú ert að ætlast til að láta notandann vita hvort sem innskotið var vel með því að skila satt eða ósatt. Í lok þessarar áætlunar - og fyrir þessu stigi að þú þarft ekki að hafa áhyggjur frjáls neitt. Svo er allt sem þú ert að gera að taka heiltölu og setja það inn í lista. Það er það sem ég er að biðja þig að gera núna. Aftur í linked.c, sem þú allir hafa, er beinagrind númer. Og þú ættir að sjá til the botn sýnið virka yfirlýsingu. Samt sem áður að fara í erfðaskrá það í C, ég hvet mjög þú að fara í gegnum skrefin sem við höfum verið æfa í hverri viku. Við höfum þegar farið í gegnum mynd af þessu. Svo þú ættir að hafa skilning um hvernig þetta virkar. En ég myndi hvetja þig til að skrifa sumir sauðakóðanum áður en köfun tommu Og við erum að fara að fara yfir sauðakóðanum sem hópur. Og síðan þegar þú hefur skrifað þinn sauðakóðanum, og þegar við höfum skrifað okkar sauðakóðanum sem hópur, þú getur fara í erfðaskrá það í C. Sem a heyrnartól upp, insert_node virka er líklega erfiðustu af þriggja við erum að fara að skrifa því ég bætt við nokkrum fleiri þvingun til Forritun, einkum að þú ert ekki að fara að setja einhverjar afrit og að listinn ætti að vera flokkað. Þannig að þetta er ekki léttvæg forrit að þú þarft að kóða. Og hvers vegna ertu ekki að 06:55 mínútur bara til að fá að vinna á sauðakóðanum og númer. Og þá munum við byrja fara sem hópur. Aftur, ef þú hefur einhverjar spurningar bara hækka hönd þína og ég kem í kring. . Við einnig gera almennt þetta - eða ég get ekki beinlínis sagt þér getur unnið með fólki. En vitanlega, hvetjum ég mjög, ef þú hefur einhverjar spurningar, til að spyrja Nágranni sat við hliðina á þér eða jafnvel vinna með einhverjum annars ef þú vilt. Þetta þarf ekki að vera einstaklingur hljóður virkni. Við skulum byrja með að skrifa nokkrar sauðakóðanum á borðinu. Hver getur gefið mér fyrstu línu sauðakóðanum fyrir þetta forrit? Fyrir þessa aðgerð, frekar - insert_node. Alden? Áhorfendur: Svo það fyrsta sem ég gerði var búa til nýtt bendi á hnút og ég frumstilla það vísa á sömu hlutur sem listi er bendir til. JASON HIRSCHORN: OK. Svo þú ert að búa til nýja músina á listann, ekki í hnút. Áhorfendur: Rétt. Já. JASON HIRSCHORN: OK. Og þá hvað við viljum gera? Hvað er eftir það? Hvað um hnút? Við höfum ekki hnút. Við höfum bara gildi. Ef við viljum að setja hnút, hvað gerum við þarf að gera fyrst áður en við getum jafnvel hugsa um að setja það? Áhorfendur: Ó, fyrirgefðu. við þurfum að malloc pláss fyrir hnút. JASON HIRSCHORN: Excellent. Skulum gera - OK. Getur ekki náð að mikil. OK. Við ætlum að fara niður, og þá við erum að nota tvo dálka. Ég get ekki farið að - OK. Búa til nýjan hnút. Þú getur búið til annan músina til að skrá eða þú getur bara notað lista eins og það er. Þú gera ekki raunverulega þörf til að gera það. Svo við að búa til nýjan hnút. Great. Það er það sem við gerum fyrst. Hvað er næst? Áhorfendur: Bíddu. Ættum við að búa til nýjan hnút núna eða ættum við að bíða til að vera viss um að það er engin afrit af hnút á listanum áður en við búum til það? JASON HIRSCHORN: Góð spurning. Skulum halda að til seinna vegna þess að meirihlutinn af þeim tíma sem við munum vera að skapa í nýjum hnút. Þannig að við munum halda því hér. En það er góð spurning. Ef við búum hana og við finnum afrit, hvað ætti við gerum áður en aftur? Áhorfendur: frjáls það. JASON HIRSCHORN: Já. Sennilega losa hana. OK. Hvað gerum við eftir að við búa til nýjan hnút? Annie? Áhorfendur: Við setja tala í hnút? JASON HIRSCHORN: Einmitt. Við setja númer - við malloc pláss. Ég ætla að fara að allt sem einni línu. En þú ert rétt. Við malloc rúm, og þá við að setja númerið inn Við getum jafnvel sett bendilinn hluti af því að null. Það er einmitt rétt. Og þá hvað um eftir það? Við brá þessari mynd á borðinu. Svo hvað gerum við? Áhorfendur: Við förum í gegnum listann. JASON HIRSCHORN: Fara í gegnum listann. OK. Og hvað gera athuga við fyrir á hverjum hnút. Kurt, hvað eigum við að stöðva fyrir á hverjum hnút? Áhorfendur: Sjá hvort n gildi sem hnúturinn er meiri en n value tengipunktur okkar. JASON HIRSCHORN: OK. Ég ætla að gera - já, allt í lagi. Svo er það n - Ég ætla að segja ef gildið er hærra en þennan hnút, þá hvað gerum við? Áhorfendur: Jæja, þá erum við að setja hlutur rétt áður. JASON HIRSCHORN: OK. Þannig að ef það er meiri en þetta, þá viljum við setja. En við viljum setja það rétt áður vegna þess að við einnig þyrfti að vera halda utan þá, hvað var áður. Svo setja áður. Þannig að við ungfrú líklega eitthvað fyrr. Við þurfum líklega að halda utan um hvað er að gerast. En við munum fá til baka þar. Svo hvaða gildi er minna en? Kurt, hvað gerum við ef gildið er minna en? Áhorfendur: Síðan sem þú halda bara að fara nema það er síðasta einn. JASON HIRSCHORN: Mér líkar það. Svo fara á næsta hnút. Nema það er síðasta - við erum líklega að haka við að terms ástands. En já, næsta hnút. Og það er að fá of lágt, þannig að við munum fara yfir hérna. En ef - geta allir séð þetta? Ef við erum jafnir hvað gerum við? Ef gildið við erum að reyna að setja inn er jafnt og gildi þetta hnúturinn er? Já? Áhorfendur: [inaudible]. JASON HIRSCHORN: Já. Í ljósi þessa - Marcus er rétt. Við gætum hafa kannski gert eitthvað öðruvísi. En í ljósi þess að við höfum skapað það, hér við ættum að losa og síðan heim aftur. Ó boj. Er það betra? Hvernig er það? OK. Frjáls og þá hvað gerum við aftur, [inaudible]? OK. Eru við vantar eitthvað? Svo hvar erum við að halda utan úr áður hnút? Áhorfendur: Ég held að það myndi fara eftir að búa til nýjan hnút. JASON HIRSCHORN: OK. Svo í byrjun trulega - já, þá getum við búið bendi til nýtt hnút, eins og fyrri hnútabendinn og núverandi hnútabendinn. Svo skulum setja það hér. Búa núverandi og fyrri ábendingum til hnúður. En þegar við stilla þeim ábendingum? Hvar gerum við það í kóða? Jeff? Áhorfendur: - gildi aðstæður? JASON HIRSCHORN: Hvaða einn í sérstakur? Áhorfendur: Ég er bara að rugla. Ef gildið er stærra en þetta hnút, Er ekki að meina að þú vilt fara í næsta hnút? JASON Hirschhorn: Svo ef gildi okkar er meiri en gildi þessarar hnút. Áhorfendur: Já, þá þú vilt vilt fara neðar í línu, ekki satt? JASON Hirschhorn: Hægri. Svo við gerum setja hann inn hér. Ef gildið er minna en þetta hnút, þá við förum á næsta hnút - eða þá erum við setja áður. Áhorfendur: Bíddu, hver er þetta hnút og sem er virði? JASON Hirschhorn: Góð spurning. Virði þessi aðgerð skilgreiningu er það sem við erum að gefa. Svo er gildi fjöldi við erum gefið. Þannig að ef gildið er minna en þetta hnút, við þurfum tíma til að setja inn. Ef gildið er stærra en þetta hnút, við förum á næsta hnút. Og aftur að upprunalegu spurningunni, þó, þar sem - Áhorfendur: Ef gildið er stærra en þennan hnút. JASON Hirschhorn: Og svo hvað gerum við hér? Sætur. Það er rétt. Ég ætla bara að fara að skrifa uppfæra ábendingum. En já, með núverandi Þú munt uppfæra það til benda til the næstur einn. Eitthvað annað sem við erum að missa? Þannig að ég ætla að slá þessu kóða í gedit. Og á meðan ég gera þetta, getur þú hafa a par fleiri mínútur til að vinna á erfðaskrá þetta í C. Svo ég hef Inntak sauðakóðanum. A fljótur í huga áður en við að byrja. Við mega ekki vera fær til fullkomlega klára þetta í öllu þrír af þessum störfum. Það er rétt lausnir þeirra að ég mun senda út til ykkar eftir kafla, og það mun vera settar á CS50.net. Svo ég hvet ykkur ekki til fara að líta á köflum. Ég hvet þig til að reyna þetta á þinn eiga, og þá nota the æfa sig vandamál að athugað svörin. Þetta hafa öll verið hönnuð til að náið tengjast og fylgja því sem þú þarft að gera á Heimadæmi. Svo ég hvet ykkur til að æfa þetta á eigin spýtur og þá nota kóðann til athugað svörin. Því ég vil að fara á kjötkássa töflur á einhverjum tímapunkti í kaflanum. Þannig að við gætum ekki að komast í gegnum það allt. En við munum gera eins mikið og við getum nú. OK. Leyfðu okkur að byrja. Asam, hvernig eigum við að búa til nýjan hnút? Áhorfendur: Þú strúktúr *. JASON Hirschhorn: Svo við hafa þetta upp hér. Ó, fyrirgefðu. Þú varst að segja strúktúr *. Áhorfendur: Og svo [? góður?] hnútur eða c hnút. JASON Hirschhorn: OK. Ég ætla að kalla það new_node svo við getum vera í samræmi. Áhorfendur: Og þú vilt setja það að höfuð, fyrsta hnút. JASON Hirschhorn: OK. Svo nú þetta benda til - þannig að þetta hefur ekki búið til nýja hnút ennþá. Þetta er bara að benda á að fyrsta hnút í listanum. Hvernig bý ég til nýjan hnút? Ef ég þarf pláss til að búa til nýja hnút. Malloc. Og hversu stór? Áhorfendur: Stærð strúktúrinn. JASON Hirschhorn: The Stærð Struct. Og hvað er strúktúr sem heitir? Áhorfendur: Hnútur? JASON Hirschhorn: Hnútur. Svo malloc (sizeof (node)); gefur okkur pláss. Og er þetta lína - eitt er rangt á þessari línu. Er new_node bendi til strúktúr? Það er samheiti. Hvað er það - hnút, einmitt. Það er hnút *. Og hvað gerum við rétt eftir við malloc eitthvað, Asan? Hvað er það fyrsta sem við gerum? Hvað ef það virkar ekki? Áhorfendur: Ó, athuga hvort það bendir í hnút? JASON Hirschhorn: Einmitt. Þannig að ef þú new_node jafngildir jafn null, hvað gerum við? Þetta skilar bool, þessi aðgerð. Nákvæmlega. Lítur vel út. Bæta einhverju við þarna? Við munum bæta við hlutum í lokin. En að svo langt er girnilegt. Búa núverandi og fyrri ábendingum. Michael, hvernig geri ég þetta? Áhorfendur: Þú þyrftir að gera hnút *. Þú vilt verða að gera einn ekki fyrir new_node en fyrir hnúður við höfum nú þegar. JASON Hirschhorn: OK. Svo núverandi hnút við erum á. Ég kalla það Viðsk. Allt í lagi. Við höfum ákveðið að við viljum halda tveir vegna þess að við þurfum að vita hvað er fyrir það. Hvað gera þeir fá frumstilla að? Áhorfendur: Verðmæti þeirra á lista okkar. JASON Hirschhorn: Svo hvað er fyrstur hlutur á listanum okkar? Eða hvernig vitum við hvar Byrjun upptalningar okkar er? Áhorfendur: Er það ekki staðist í aðgerðina? JASON Hirschhorn: Hægri. Það var samþykkt í hérna. Þannig að ef það er liðin í aðgerð, byrja á listanum, hvað eigum við að setja núverandi jafnt? Áhorfendur: List. JASON Hirschhorn: List. Það er einmitt rétt. Nú hefur það veffang byrjunin á listanum okkar. Og hvað um fyrri? Áhorfendur: List mínus einn? JASON Hirschhorn: Það er ekkert fyrir það. Og hvað getum við gert til að signify ekkert? Áhorfendur: Null. JASON Hirschhorn: Já. Það hljómar eins og góð hugmynd. Fullkominn. Þakka þér. Fara í gegnum listann. Constantine, hversu lengi við erum að fara að fara í gegnum listann? Áhorfendur: fyrr en við náum null. JASON Hirschhorn: OK. Þannig að ef, á meðan, til hliðar. Hvað erum við að gera? Áhorfendur: Kannski for lykkju? JASON Hirschhorn: Við skulum gera for lykkju. OK. Áhorfendur: Og við segjum fyrir - þar til núverandi músina er ekki jafnt null. JASON Hirschhorn: Svo ef við vitum að ástand, hvernig getum við skrifað lykkju byggt burt því ástandi. Hvers konar lykkju eigum við að nota? Áhorfendur: Þó. JASON Hirschhorn: Já. Það gerir meira vit byggt burt af því sem þú sagðir. Ef við viljum bara að fara inn í við það væri Bara vita að hlutur, myndi það gera vit í að gera meðan lykkja. Þó núverandi ekki jafn null, ef gildið er minna en þennan hnút. Akshar, gefa mér þessa línu. Áhorfendur: Ef núverandi-> n n minna en gildi. Eða snúa því. Rofi sem krappi. JASON Hirschhorn: Því miður. Áhorfendur: Breyttu krappi. JASON Hirschhorn: Svo ef það er meiri en verðmæti. Því það er ruglingslegt með comment að ofan, ég ætla að gera það. En já. Ef gildi okkar er minna en þetta hnút, hvað gerum við? Oh. Ég hef það hérna. Setja áður. OK. Hvernig gerum við það? Áhorfendur: Er það enn mig? JASON Hirschhorn: Já. Áhorfendur: Þú - new_node-> næst. JASON Hirschhorn: Svo er það að fara til að jafna? Áhorfendur: Það er að fara til að jafna núverandi. JASON Hirschhorn: Einmitt. Og svo hitt - Hvað annað þurfum við að uppfæra? Áhorfendur: Athugaðu hvort fortíð jafngildir null. JASON Hirschhorn: Ef prev - þannig að ef fyrri jafngildir null. Áhorfendur: Það þýðir að það er að fara til að verða yfirmaður. JASON Hirschhorn: það þýðir það er orðið höfuð. Svo þá hvað gerum við? Áhorfendur: Við gerum höfuð jafngildir new_node. JASON Hirschhorn: Head jafngildir new_node. Og hvers vegna höfuð hér, ekki lista? Áhorfendur: Vegna höfuð er alþjóðlegt breytu, sem er byrjun staður. JASON Hirschhorn: Sweet. OK. Og - Áhorfendur: Síðan sem þú ert annars prev-> Næsta jafngildir new_node. Og þá þú aftur satt. JASON Hirschhorn: Hvar við setjum new_node enda? Áhorfendur: Ég myndi - Ég sett það í upphafi. JASON Hirschhorn: Svo hvaða línu? Áhorfendur: Eftir ef yfirlýsingu stöðva ef það er vitað. JASON Hirschhorn: Hérna? Áhorfendur: Ég myndi gera new_node-> n jafnt gildi. JASON Hirschhorn: Hljómar vel. Sennilega gerir það vit í - við gerum ekki þarf að vita hvað listi við erum á vegna þess að við erum aðeins að takast með einum lista. Svo betra virka yfirlýsingu fyrir þetta er bara til að losna við þetta algjörlega og bara setja gildi í höfuð. Við gerum ekki einu sinni að vita hvað listi við erum inn En ég mun halda það fyrir nú og þá breyta því á uppfærslu glæranna og kóða. Svo lítur það gott í bili. Ef gildi - sem getur gert þessa línu? Ef - hvað gerum við hér, Noah. Áhorfendur: Ef gildið er stærra en Viðsk-> n - JASON Hirschhorn: Hvernig við förum í næsta hnút? Áhorfendur: Viðsk-> n er jafnt new_node. JASON Hirschhorn: Svo n er hvaða hluti af strúktúr? The heiltölu. Og new_node er bendi á hnút. Svo hvaða hluti af Nota s ættum við að uppfæra? Ef ekki n, þá er það annar hluti? Nói, hvað er annar hluti. Áhorfendur: Oh, við hliðina. JASON Hirschhorn: Next, einmitt. Nákvæmlega. Næstur er the réttur einn. Og hvað annað þurfum við að uppfæra, Nói? Áhorfendur: The ábendingum. JASON Hirschhorn: Svo við uppfært straumur. Áhorfendur: Fyrri-> næst. JASON Hirschhorn: Já. OK, við munum gera hlé. Sem getur hjálpað okkur út hér? Manu, hvað eigum við að gera? Áhorfendur: Þú hefur got til að setja það jafn Nota s-> Næsta. En gera það áður en fyrri línu. JASON Hirschhorn: OK. Nokkuð fleira? Akshar. Áhorfendur: Ég held ekki að þú sért ætlað að breyta Viðsk-> Næsta. Ég held að þú ert ætlað að gera Viðsk jafn Viðsk-> hliðina til að fara á næsta hnút. JASON Hirschhorn: Fyrirgefðu, hvar? Á hvaða línu? Þessi lína? Áhorfendur: Já. Gerðu Viðsk jafngildir Viðsk-> næst. JASON Hirschhorn: Svo er það rétt vegna þess að núverandi er bendi á hnút. Og við viljum það til að benda á næsta Hnúturinn í hvað er að fá nú benti á. Viðsk sjálft er næst. En ef við vorum að uppfæra curr.next, við myndi vera að uppfæra í raun huga sjálft, ekki þar sem þetta bendillinn var að benda. Hvað um þessa línu, þó. Avi? Áhorfendur: Fyrri-> Næsta jafngildir Viðsk. JASON Hirschhorn: Svo aftur, ef fyrri er bendi á hnút, prev> næst er Raunveruleg músina í hnút. Þannig að þetta myndi vera að uppfæra bendillinn í hnút Nota s. Við viljum ekki að uppfæra bendillinn í hnút. Við viljum að uppfæra fyrri. Svo hvernig gerum við það? Áhorfendur: Það myndi bara vera prev. JASON Hirschhorn: Hægri. Fyrri er bendi á hnút. Nú erum við að breyta því til að ný bendi á hnút. OK Höldum niður. Að lokum, þetta síðasta ástand. Jeff, hvað gerum við hér? Áhorfendur: Ef gildið er jafnt og CURR-> n. JASON Hirschhorn: Því miður. Ó góðvild mína. Hvað? Gildi == Viðsk-> n. Hvað gerum við? Áhorfendur: Þú vilt losa new_node okkar, og þá þú vilt return false. JASON Hirschhorn: Þetta er það sem við höfum skrifað hingað til. Hefur einhver hafa nokkuð að bæta áður en við tökum? OK. Skulum reyna það. Eftirlit getur náð í lok af a non-void virkni. AVI, hvað er að gerast? Áhorfendur: Ert þú ætlast til að setja aftur satt utan while lykkju? JASON Hirschhorn: Ég veit það ekki. Ert þú vilt að ég? Áhorfendur: Aldrei hugur. Nei JASON Hirschhorn: Akshar? Áhorfendur: Ég held að þú átt að setja aftur ósatt í lok á while lykkju. JASON Hirschhorn: Svo þar viltu það að fara? Áhorfendur: Eins utan while lykkju. Þannig að ef þú hættir í while lykkju sem þýðir að þú hefur náð í lok og ekkert hefur gerst. JASON Hirschhorn: OK. Svo hvað við gerum hérna? Áhorfendur: Þú return false þar sem vel. JASON Hirschhorn: Oh, við gera það á báðum stöðum? Áhorfendur: Já. JASON Hirschhorn: OK. Ættum við að fara? Ó góðvild mína. Fyrirgefðu. Ég biðjumst velvirðingar á skjánum. Það er góður af stórfurðulegur út á okkur. Svo velja valkost. Zero, á kóða, kvittir forritið. Einn setur eitthvað. Skulum setja þrjú. Innskotið var ekki vel. Ég ætla að prenta út. Ég hef ekki neitt. OK. Kannski var bara fluke. Settu einn. Ekki vel. OK. Við skulum hlaupa í gegnum gdb virkilega hratt að athuga hvað er að gerast. Mundu gdb. / Nafn þitt program kemur okkur inn gdb. Er að mikið að höndla? Blikkandi? Sennilega. Loka augunum og taka nokkuð djúpt andann ef þú færð þreytt að líta á það. Ég er í gdb. Hvað er það fyrsta sem ég geri í gdb? Við verðum að reikna út hvað er að gerast hér. Við skulum sjá. Við höfum sex mínútur til að reikna hvað er að gerast. Brjóta aðal. Og þá hvað á ég að gera? Carlos? Hlaupa. OK. Skulum velja valkost. Og hvað þýðir N gera? Next. Já. Áhorfendur: Vissir þú ekki að nefna - sagðirðu að höfuð, það var frumstilla að null í upphafi. En ég hélt að þú sagðir að væri í lagi. JASON Hirschhorn: Förum - við skulum líta í gdb, og þá munum við fara til baka. En það hljómar eins og þú hefur nú þegar nokkrar hugmyndir um hvað er að gerast. Þannig að við viljum að setja eitthvað. OK. Við höfum sett inn. Vinsamlegast sláðu inn int. Við munum setja þrjú. Og þá er ég á þessari línu. Hvernig fer ég að aflúsa innskotið þekkt virka? Ó góðvild mína. Það er mikið. Er að stórfurðulegur út mikið? Áhorfendur: Oh, dó hann. JASON Hirschhorn: Ég bara draga það út. OK. Áhorfendur: Kannski er það Hinn endi vír. JASON Hirschhorn: Wow. Svo the botn lína - hvað sagðir þú? Áhorfendur: Ég sagði kaldhæðni tæknilega erfiðleikar í þessum flokki. JASON Hirschhorn: Ég veit. Bara ef ég hefði stjórn á þeim hluta. [Inaudible] Sem hljómar frábærlega. Hví ekki þú krakkar byrja að hugsa um hvað við hefðum getað gert rangt, og við munum vera aftur í 90 sekúndur. Avica, ég ætla að spyrja þig hvernig á að fara inni insert_node að kemba það. Svo þetta er þar við fórum síðast burt. Hvernig fer ég inn insert_node, Avica, að kanna hvað er í gangi? Hvað GDB stjórn? Break myndi ekki taka mig inni. Er Marquise vita? Áhorfendur: Hvað? JASON Hirschhorn: Hvað GDB stjórn Ég nota til að fara inn þessa aðgerð? Áhorfendur: Skref? JASON Hirschhorn: Skref í gegnum S. Það tekur mig inni. OK. New_node mallocing pláss. Það allt lítur út eins og þess að fara. Skulum skoða new_node. Það fengum minni heimilisfang. Skulum athuga - það er allt rétt. Svo allt hér virðist að vinna rétt. Áhorfendur: Hver er munurinn milli P og sýna? JASON Hirschhorn: P stendur fyrir prentun. Og svo þú ert að spyrja hvað er munur á milli sem og þetta? Í þessu tilviki, ekkert. En yfirleitt eru nokkur munur. Og þú ættir að líta í GDB handbók. En í þessu tilfelli, ekkert. Við hafa tilhneigingu til að nota prenta, þó, vegna þess að við þurfum ekki að gera mikið meira en prenta eitt gildi. OK. Þannig að við erum á línu 80 í númerið okkar, setja node * Viðsk jafnt á listann. Leyfðu okkur að prenta út Viðsk. Það jafngildir lista. Sætur. Bíddu. Það jafngildir eitthvað. Það virðist ekki rétt. Svona. Það er vegna þess að í gdb, hægri, ef það er línan sem þú ert á það hefur ekki framkvæmt ennþá. Svo þú þarft að raunverulega tegund hliðina til að framkvæma línuna áður að sjá niðurstöður hennar. Svo hér erum við. Við keyrð bara þessa línu, Fyrri jafngildir null. Svo aftur, ef við prentum fyrri við munum ekki sjá neitt undarlegt. En ef við framkvæmum reyndar að lína, þá munum við sjá að þessi lína uppnámi. Þannig að við höfum Viðsk. Þeir eru báðir vel. Satt? Núna erum við á þessari línu hérna. Þó Viðsk ekki jafn null. Jæja, hvað þýðir Viðsk jafnir? Við sáum bara að það jafn null. Við prentuðum það út. Ég prenta það út aftur. Svo er að á meðan lykkja fara að framkvæma? Áhorfendur: Nei JASON Hirschhorn: Svo þegar ég slóst að lína, þú sérð við hljóp alla leið niður á botn, return false. Og þá erum við að fara að fara aftur ósatt og fara aftur í prógrammi okkar og lokum prenta út, eins og við sáum, innskotið var ekki vel. Svo, einhver hafa einhverjar hugmyndir um hvað við þurfum að gera til að laga þetta? Ég ætla að bíða þangað til ég sé a par af höndum fara upp. Við vildum ekki að framkvæma þetta. Hafðu í huga, þetta var fyrsta sem við vorum að gera. Ég ætla ekki að fara að gera a par. Ég ætla að gera nokkrar. Vegna þess að par þýðir tvö. Ég ætla að bíða í meira en tvö. Fyrsta innsetning, Viðsk, Sjálfgefin jafngildir null. Og þetta lykkja aðeins keyrir ef Viðsk er ekki núll. Svo hvernig get ég fengið í kringum þetta? Ég sé þrjá hendur. Ég ætla að bíða í meira en þrjú. Marcus, hvað finnst þér? Áhorfendur: Jæja, ef þú þarft það til að framkvæma meira en einu sinni, þú bara breyta því að gera-while lykkju. JASON Hirschhorn: OK. Mun að leysa vandamál okkar, þó? Áhorfendur: Í þessu tilfelli ekki vegna sú staðreynd að listinn er tómur. Svo þá þú sennilega bara þurft að bæta yfirlýsing þess efnis að ef lykkja hættir þá verður þú að vera í lok lista, á hver benda þér getur bara sett það. JASON Hirschhorn: Mér líkar það. Það er vit í. Ef lykkja hættir - því það verður return false hér. Þannig að ef að lykkja hættir, þá erum við í lok listanum, eða kannski byrja á lista ef það er ekkert í það, sem er það sama og á endanum. Svo nú viljum við setja eitthvað hér. Svo hvernig virkar þessi númer útlit, Marcus? Áhorfendur: Ef þú got nú þegar hnúturinn malloced, þú bara að segja new_node-> Næsta jafngildir null vegna það þarf að vera í lokin. Eða new_node-> Næsta jafngildir null. JASON Hirschhorn: OK. Sorry. New_node-> Næsta jafngildir null vegna þess að við erum í lok. Það þýðir ekki að setja það inn Hvernig eigum við að setja það í listanum? Rétt. Það er bara að setja það jafnt. Nei hvernig við raunverulega setja það á listanum? Hvað er að benda á að endir af listanum? Áhorfendur: Head. JASON Hirschhorn: Fyrirgefðu? Áhorfendur: Head er að benda til loka listanum. JASON Hirschhorn: Ef það er ekkert í listi, höfuð er að benda á að lok lista. Svo sem mun vinna fyrir Fyrsta innsetning. Hvað um ef það eru nokkrar hlutir á listanum? En við viljum ekki að setja höfuð jafn new_node. Hvað viljum við að gera þar? Já? Sennilega fyrri. Mun það virka? Muna að fyrri er bara bendi á hnút. Og fyrri er staðbundin breytu. Þannig að fyrirsögnin mun setja a heimamaður breytu, fyrri, sem er jafn eða benda til þessa nýja hnút. Það mun í raun ekki setja það á listanum okkar, þó. Hvernig eigum við að setja það í lista okkar? Akchar? Áhorfendur: Ég held að þú gera núverandi-> Næsta. JASON Hirschhorn: OK. Viðsk-> næst. Svo aftur, eina ástæðan að við erum niður hér er, hvað þýðir nú jafnir? Áhorfendur: Jafnt null. JASON Hirschhorn: Og hvað með það gerist ef við gerum null-> næst? Hvað eigum við að fara að fá? Við munum fá skiptingu kenna. Áhorfendur: Ekki Viðsk jafngildir null. JASON Hirschhorn: Það er það sama sem fyrra, þó, vegna þess að það er a heimamaður breytu sem við erum að setja jafnt þessu nýja hnút. Við skulum fara aftur til myndin okkar innsetning eitthvað. Segja að við erum að setja í lok af listanum, svo hérna. Við höfum núverandi músina sem er bendir til núll og fyrri lið sem er bendir til 8.. Svo hvað þurfum við að uppfæra, Avi? Áhorfendur: Fyrri-> næst? JASON Hirschhorn: Fyrri-> næsta er það við viljum að uppfæra vegna þess að mun í raun setja það á í lok listanum. Við höfum enn einum galla, þó, að við erum að fara að keyra inn. Hvað er þetta galla? Já? Áhorfendur: Það er að fara að fara aftur rangar í þessu tilviki? JASON Hirschhorn: Oh, er er fara að skila falskur. En það er önnur padda. Þannig að við munum þurfa að setja í staðinn satt. Áhorfendur: Er fyrri enn jafnir null efst á listanum? JASON Hirschhorn: Svo fyrri enn jafngildir null í upphafi. Og hvernig getum við fengið yfir það? Já? Áhorfendur: Ég held að þú getur gert ávísun áður en á meðan lykkja til að sjá hvort það er tómt lista. JASON Hirschhorn: OK. Svo skulum við fara hér. Gera a stöðva. Ef - Áhorfendur: Svo ef höfuðið jafngildir jafngildir null. JASON Hirschhorn: Höfuð jafngildir jafngildir null - sem mun segja okkur ef það er tómt lista. Áhorfendur: Og þá er gera höfuð jafngildir nýtt. JASON Hirschhorn: Head jafngildir new_node? Og hvað annað þurfum við að gera? Áhorfendur: Og þá aftur að veruleika. JASON Hirschhorn: Ekki alveg. Við erum vantar eitt skref. Áhorfendur: New_node næstu þarf að benda á núll. JASON Hirschhorn: Einmitt, Alden. Og þá getum við aftur satt. OK. En það er samt góð hugmynd að gera hlutina í lok listanum, ekki satt? Allt í lagi. Við enn gæti raunverulega fá til loka listanum. Svo er þetta númer í lagi ef við erum á því lok lista og það eru sumir hlutir á listanum? Satt? Þar sem við höfum enn hugmynd Marcus er. Við gætum loka þessa lykkju þar við erum í lok listanum. Svo viljum við enn þetta kóðann hér niðri? Áhorfendur: Já. JASON Hirschhorn: Já. Og hvað þurfum við að breyta því í? True. Hefur þessi hljóð gott til alla svo langt? Einhver hafa allir - AVI, þú þarft eitthvað til að bæta? Áhorfendur: Nei JASON Hirschhorn: OK. Þannig að við höfum gert nokkrar breytingar. Við höfum gert þessa athugun áður en við fór í fyrir tóma listann. Þannig að við höfum gætt tóman lista. Og hér við hugsað um að setja eitthvað í lok listanum. Svo það virðist eins og þetta á meðan lykkja taka sjá um hlutina á milli, einhvers staðar á listanum ef það eru hlutir á listanum. OK. Leyfðu okkur að keyra þetta forrit aftur. Ekki vel. Áhorfendur: Þú komst ekki. JASON Hirschhorn: Ó, Ég vissi ekki að gera það. Góður punktur, Michael. Skulum bæta Gerðu tengd. Lína 87 Það er villa. Lína 87. Alden, þetta var línan sem þú gafst mér. Hvað er rangt? Áhorfendur: Það hlýtur að vera að null. JASON Hirschhorn: Excellent. Nákvæmlega rétt. Það ætti að vera núll. Skulum gera aftur. Safna saman. OK. Skulum setja þrjú. Innskotið var vel. Skulum prenta það út. Ó, ef aðeins við gætum stöðva. En við höfum ekki gert það prenta virka ennþá. Skulum setja eitthvað annað. Hvað eigum við að koma inn? Áhorfendur: Sjö. JASON Hirschhorn: Seven? Áhorfendur: Já. JASON Hirschhorn: Við höfum seg kenna. Svo við fengum einn, en við greinilega getur ekki fengið tvö. Það er 05:07. Þannig að við gætum kemba þetta í þrjár mínútur. En ég ætla að láta okkur hér og hreyfa á til kjötkássa matskeið. En aftur, svör fyrir þessum kóða Ég mun senda það til þín í smá. Við erum mjög nálægt því. Ég hvet mjög þú að reikna út hvað er að gerast hér og festa það. Þannig að ég ætla að senda þér þennan kóða sem vel auk lausnin - sennilega lausnin síðar. Fyrst þetta númer. The annar hlutur sem ég vil gera áður en við klára er að við höfum ekki leystur neitt. Svo vil ég að sýna þér hvað valgrind lítur út. Ef við hlaupum valgrind mörk um kerfi okkar,. / tengd. Again, í samræmi við þessa mynd, sem við ætti að keyra valgrind með einhvers konar valkostur, í þessu tilfelli - Leka-stöðva = fullur. Svo skulum skrifa valgrind - Leka-stöðva = fullur. Þannig að þetta mun keyra valgrind um kerfi okkar. Og nú forritið keyrir í raun. Þannig að við erum að fara að keyra hana bara svona áður, setja eitthvað inn Ég ætla að setja í þremur. Sem virkar. Ég ætla ekki að reyna að setja á eitthvað annars vegna þess að við erum að fara að fá seg RANGT því tilfelli. Þannig að ég ætla bara að fara að hætta. Og nú þú sérð hérna leka og hrúga samantekt. Þetta eru góðir hlutir sem þú vilt kíkja. Svo hrúga samantekt - það segir, í notkun á brottför - átta bæti í einu blokk. Að ein húsaröð er hnút við malloced. Michael, þú sagðir áður en hnútur er átta bit vegna þess að það hefur fyrir heiltöluna og bendilinn. Svo er það hnút okkar. Og þá segir hún við notuðum malloc sjö sinnum og við leystur eitthvað sex sinnum. En við kölluðum aldrei ókeypis, þannig að ég hef engin hugmynd hvað þetta er að tala um. En nægja að segja að þegar þinn forritið keyrir, malloc er kallað í sumum öðrum stöðum sem við þarft ekki að hafa áhyggjur. Svo malloc var líklega kallað í sumum stöðum. Við þurfum ekki að hafa áhyggjur þar. En þetta er í raun okkur. Þessi fyrsta lína er okkur. Við fórum að loka. Og þú getur séð að hér í leka samantekt. Enn náðist - átta bæti í einum reitnum. Það þýðir að minni - við höfum lekið að minni. Ákveðið glatað - eitthvað er glataður til góðs. Almennt, þú vilja ekki sjá neitt þar. Enn náðist almennt þar þú munt sjá það, þar sem þú munt vilja að leita að sjá hvaða númer ætti að hafa frelsi en þú gleymdir að losa. Og þá ef þetta var ekki raunin, ef við gerðum ókeypis allt, við getum stöðva það. Skulum hlaupa bara forritið ekki setja í neinu. Þú munt sjá hér niðri í notkun á brottför - Núll bæti í núll blokkir. Það þýðir að við höfðum ekkert til vinstri Þegar þessi áætlun lauk. Svo áður en þú kveikir í pset6, hlaupa valgrind og ganga úr skugga um að þú ert ekki hvaða minni lekur í forritinu. Ef þú hefur einhverjar spurningar með valgrind, ekki hika við að ná út. En þetta er hvernig þú notar það. Mjög einfalt - að sjá hvort þú hafa í notkun á brottför - allir bæti í hvaða blokkum. Þannig að við vorum að vinna á insert hnút. Ég átti tvo aðra valkosti hér - prenta hnúður og frjáls hnúður. Aftur, þetta eru aðgerðir sem eru að fara að vera gott fyrir þig að æfa vegna þess að þeir munu hjálpa þér ekki aðeins með þessi sýnishorn æfingar en einnig á vandamálinu stillt. Þeir kortinu á nokkuð náið að hlutum þú ert að fara til verða að gera í Heimadæmi. En ég vil vera viss um við snertingu á allt. Og kjötkássa matskeið eru einnig mikilvægt að hvað við erum að gera í kafla þessum viku - eða í Heimadæmi. Þannig að við ætlum að klára kafla tala um kjötkássa matskeið. Ef þú tekur eftir að ég gerði lítið kjötkássa borð. Það er ekki það sem við erum að tala um, þó. Við erum að tala um mismunandi tegund af kjötkássa matskeið. Og á kjarna þess, kjötkássa borð er ekkert annað en array auk kjötkássa virka. Við erum að fara að tala um hluti bara til að ganga úr skugga um að allir skilji hvað A kjötkássa virka er. Og ég ætla að segja þér núna að það er ekkert meira en tvo hluti - fylki og kjötkássa virka. Og hér eru skref í gegnum sem þetta rekur. Það er array okkar. Það er hlutverk okkar. Sér í lagi þarf kjötkássa aðgerðir til að gera nokkra hluti með þessu. Ég ætla að tala sérstaklega um þetta vandamál setja. Það er líklega að fara að taka í streng. Og hvað er það að fara að koma aftur? Hvaða gögn tegund? Alden? Kjötkássa virka aftur? Heiltala. Svo er þetta það sem kjötkássa Tafla samanstendur af - borð í formi array og kjötkássa virka. Hvernig það virkar? Það virkar í þremur skrefum. Við gefa það a takkann. Í þessu tilfelli, munum við gefa það a band. Við köllum kjötkássa virka á skrefi eitt á takkann og við fáum gildi. Sérstaklega munum við segja fáum við heiltölu. That heiltala, eru mjög sérstakar takmörk fyrir því hvað þessi tala getur verið. Í þessu dæmi, array okkar af stærð þrjú. Svo hvaða tölur geta að heiltala vera. Hvað er á bilinu Leyfð gildi fyrir sem heiltala, aftur gerð þessa kjötkássa virka? Núll, einn og tveir. Að benda á kjötkássa virka er að reikna út stað í fylkinu þar lykill okkar er að fara. Það eru bara þrjú möguleg stöðum hér - núll, einn, eða tveir. Þannig að þetta virka betur aftur núll, einn, eða tveir. Sumir gild Índice í þessu fylki. Og þá eftir því hvar það skilar, þú getur séð það array opinn krappi gildi. Það er þar sem við setja takkann. Þannig að við henda í grasker, við fá út núll. Á array krappi 0, leggjum grasker. Við henda köttum, fáum við út einn. Við setjum köttur á einn. Við setja í kónguló. Við fáum út tvo. Við setjum kónguló á array krappi tvö. Það væri svo gott ef það í uppnámi eins og þessi. En því miður, eins og við munum sjá, það er dálítið flóknara. Áður en við fáum það, einhverjar spurningar um þetta undirstöðu sett upp af kjötkássa borð? Þetta er mynd af nákvæmlega hvað við brá á borðinu. En þar sem við dró hana á borð, ég ætla ekki að fara inn í það frekar. Í raun takkana, töfra svartur kassi - eða í þessu tilfelli, Teal Box - Með kjötkássa virka setur þá í fötunum. Og í þessu dæmi erum við ekki að setja nafn. Við erum að setja tilheyrandi símann fjöldi nafni í fötu. En þú getur mjög vel bara setja nafn í fötu. Þetta er bara mynd af því sem við brá á borðinu. Við höfum hugsanlega komu, þó. Og það eru tveir sérstaklega renna að ég vil fara yfir. Sú fyrsta er um kjötkássa virka. Svo ég spurði, hvað gerir gott kjötkássa virka? Ég gef tvö svör. Hið fyrra er að það er deterministic. Í tengslum við kjötkássa aðgerðir, hvað þýðir þetta? Já? Áhorfendur: Það má finna á neysluverðs í föstu tíma? JASON Hirschhorn: Það er ekki hvað það þýðir. En það er góð ágiskun. Einhver annar hafa giska að hvað þetta þýðir? Að góð kjötkássa virka er deterministic? Annie? Áhorfendur: Það lykill getur aðeins verið varpað einum stað í kjötkássa töflunni. JASON Hirschhorn: Það er nákvæmlega rétt. Hvert skipti sem þú setja í grasker, það skilar alltaf núll. Ef þú setur í grasker og kjötkássa þinn skilar núll en hefur líkur á að skila eitthvað annars er hærri en núll - svo kannski getur það aftur einn stundum eða tveir aðrir tímar - það er ekki góð kjötkássa virka. Þú ert alveg rétt. Kjötkássa virka skal skila sama nákvæmlega heiltala, í þessu tilfelli, fyrir sama nákvæmlega band. Kannski skilar það sama nákvæmlega heiltölu fyrir sama nákvæmlega band óháð hástöfum. En í því tilviki er það enn deterministic því margar hlutir eru varpað á sama gildi. Það er allt í lagi. Svo lengi sem það er aðeins einn framleiðsla fyrir tiltekið inntak. OK. The second hlutur er að það skilar gild vísitölur. Við tókum upp að fyrr. Þetta kjötkássa virka - ó drengur - kjötkássa fall ætti aftur gild vísitölur. Svo segja - við skulum fara aftur til þessa dæmis. Kjötkássa virka minn telur upp stafina í orðinu. Það er kjötkássa virka. Og skilar það heiltölu. Svo ef ég hef orðið er, það er að fara að fara aftur einn. Og það er að fara að setja hérna. Hvað ef ég setti í orðinu kylfu? Það er að fara að skila þremur. Hvar er kylfu fara? Það passar ekki. En það þarf að fara eitthvað. Þetta er kjötkássa borð mitt eftir allt saman, og allt þarf að fara eitthvað. Svo hvar ætti kylfu fara? Allir hugsun? Giskar? Góður giska? Áhorfendur: Zero. JASON Hirschhorn: Hvers vegna núll? Áhorfendur: Vegna þriggja modulo þrjú er núll? JASON Hirschhorn: Three modulo þrjú er núll. Það er frábær giska, og það er rétt. Þannig að í þessu tilviki það ætti sennilega fara á núlli. Svo góð leið til að tryggja að þessi tæti virka aðeins skilar gild vísitölur er til modulo það með stærð á töflunni. Ef þú modulo hvað sem Þetta skilar því þrír, þú ert alltaf að fara að fá eitthvað á milli núll, einn og tveir. Og ef þetta alltaf skilar sjö, og þú modulo alltaf um þrjár, þú ert alltaf að fara til að fá það sama. Svo það er enn deterministic ef þú modulo. En það mun tryggja að þú aldrei fá eitthvað - ógild iðnaður. Almennt, að modulo ætti að gerast inni kjötkássa virka. Svo þú þarft ekki að hafa áhyggjur af þessu. Þú bara að tryggja að þetta er gild Índice. Einhverjar spurningar um þetta möguleiki pitfall? OK. Og þar sem við förum. Næsta möguleiki pitfall, og þetta er ein stór. Hvað ef tveir lyklar kort að sama gildi? Þannig að það eru tvær leiðir til að höndla þetta. Sú fyrsta er kallað línulegt leit, sem ég er ekki að fara yfir. En þú ættir að þekkja hvernig það virkar og hvað það er. Annað sem ég er að fara að fara yfir því að það er eitt sem margir fólk mun líklega á endanum að ákveða til að nota í vandamál sín. Auðvitað, þú þarft ekki að. En fyrir Heimadæmi, margir hafa tilhneigingu til að velja að búa til kjötkássa borð með sérstakri chaining að hrinda í framkvæmd orðabók þeirra. Þannig að við ætlum að fara yfir hvað það þýðir til að búa til kjötkássa borð með aðskilin chaining. Svo ég setti í grasker. Það skilar núll. Og ég setti grasker hér. Þá er ég setja í - hvað er annað Halloween-þema hlutur? Áhorfendur: Candy. JASON Hirschhorn: Candy! Það er a mikill einn. Ég setti í sælgæti og sælgæti einnig gefur mér núll. Hvað á ég að gera? Einhverjar hugmyndir? Vegna þess að þú allir tegund af vita hvað sérstakt chaining er. Svo einhverjar hugmyndir hvað ég á að gera? Já. Áhorfendur: Pútt the band reyndar í kjötkássa töflunni. JASON Hirschhorn: Þannig að við erum að fara að draga góða hugmynd hérna. OK. Áhorfendur: Hafa Hashtable [Inaudible] bendillinn sem bendir til upphafið af lista. Og þá hafa grasker vera fyrsta gildi í því tengda listanum og sælgæti vera annað gildi í þeim tengda listanum. JASON Hirschhorn: OK. Marcus, sem var framúrskarandi. Ég ætla að brjóta það niður. Marcus er að segja ekki skrifa grasker. Það væri slæmt. Ekki setja nammi annars staðar. Við erum að fara að setja þá bæði á núlli. En við erum að fara að takast á við setja þau á núlli með búa til lista á núlli. Og við erum að fara að búa til lista yfir allt sem varpað á núll. Og besta leiðin til að við lærðum að búa til listi sem geta vaxið og skreppa virk er ekki innan annað array. Svo ekki multi-víddar array. En bara að búa til tengda listanum. Svo hvað hann lagði - Ég ætla að fá nýja - er að búa til fylki með ábendingum, fjölda ábendinga. OK. Einhver hugmynd eða vísbending hvað tegund þessa ábendingum ætti að vera? Marcus? Áhorfendur: ábendingum til - JASON Hirschhorn: Þar sem þú sagði tengda listanum, svo - Áhorfendur: Hnútur ábendingum? JASON Hirschhorn: Hnútur ábendingum. Ef hlutir í tengdir okkar lista eru hnútar þá þeir ætti að vera hnút ábendingum. Og hvað gera þeir jafnir í upphafi? Áhorfendur: Null. JASON Hirschhorn: Null. Þannig að það er tóm hlutur okkar. Grasker skilar núll. Hvað gerum við? Ganga mér í gegnum það? Reyndar Marcus þegar gaf mér. Einhver annar ganga mér í gegnum það. Hvað við gerum þegar við - þetta lítur mjög svipað það sem við vorum bara að gera. Avi. Áhorfendur: Ég ætla að taka giska. Svo þegar þú færð nammi. JASON Hirschhorn: Já. Jæja, við fengum grasker. Skulum fá fyrst einn okkar. Við fengum grasker. Áhorfendur: OK. Grasker skilar núll. Svo þú setja það í það. Eða í raun, þú setur það í tengda listanum. JASON Hirschhorn: Hvernig eigum við setja það í tengda listanum? Áhorfendur: Oh, í raun setningafræði? JASON Hirschhorn: Bara ganga - segja meira. Hvað gerum við? Áhorfendur: Þú settu bara það sem fyrsta hnút. JASON Hirschhorn: OK. Þannig að við höfum hnút okkar, grasker. Og nú hvernig ég setja það? Áhorfendur: Þú framselja það til bendillinn. JASON Hirschhorn: Hvaða músina? Áhorfendur: Bendillinn á núlli. JASON Hirschhorn: Svo þar er þetta lið? Áhorfendur: Til null núna. JASON Hirschhorn: Jæja, það er að benda á að null. En ég er að setja í grasker. Svo hvar ætti það að benda? Áhorfendur: Til grasker. JASON Hirschhorn: Til grasker. Nákvæmlega. Svo bendir þetta til grasker. Og hvar er þetta bendi í grasker lið? Að Áhorfendur: Null. JASON Hirschhorn: Til null. Nákvæmlega. Svo við sett bara eitthvað í tengda listanum. Við skrifuðum bara þennan kóða til að gera þetta. Næstum við fengum hana nánast alveg klikkaður. Nú erum við að setja nammi. Nammi okkar fer einnig í núll. Svo hvað við gerum með nammi? Áhorfendur: Það fer eftir því hvort eða ekki að við erum að reyna að flokka það. JASON Hirschhorn: Það er nákvæmlega rétt. Það fer eftir því hvort eða ekki við erum að reyna að flokka það. Skulum gera ráð við erum ekki fara að flokka það. Áhorfendur: Jæja þá, eins og við ræddum áður, það er einfaldast að setja það rétt í byrjun svo bendillinn frá núll stig í sælgæti. JASON Hirschhorn: OK. Bíddu. Leyfðu mér að búa nammi hérna. Þannig að þetta bendiprik - Áhorfendur: Já, ætti nú vera að benda sælgæti. Þá hafa músina frá nammi benda til grasker. JASON Hirschhorn: Svona? Og segja að við fengum annan hlutur til landakort á núll? Áhorfendur: Jæja, þú bara gera það sama? JASON Hirschhorn: Ekki það sama. Svo í þessu tilfelli, ef við gerum ekki vilja til að halda það flokkað það hljómar frekar einfalt. Við tökum bendilinn í Índice gefið með kjötkássa virka okkar. Við höfum sem benda á nýjan hnút okkar. Og þá hvað sem það var að benda að áður - í þessu tilfelli null, Í Annað mál grasker - að, hvað það er að benda á að áður, bæta við inn í the næstur af nýr hnútur okkar. Við erum að setja eitthvað í upphafi. Í raun er þetta mikið einfaldara en reyna að halda lista raðað. En aftur, að leita verður flóknari hér. Við munum alltaf þurfa að fara til enda. OK. Einhverjar spurningar um aðskilda chaining? Hvernig það virkar? Vinsamlegast biðja þá núna. Ég vil virkilega að ganga úr skugga um að þú allur skilja þetta áður en við förum. Áhorfendur: Hví freistið þér grasker og nammi í sama hluti af kjötkássa töflunni? JASON Hirschhorn: Góð spurning. Hvers vegna eigum við að setja þá í sama hluti af kjötkássa töflunni? Jæja, í þessu tilfelli kjötkássa virka okkar skilar núll fyrir þau bæði. Svo þeir þurfa að fara á Índice núll vegna þess að þar sem við erum að fara að leita að þeim ef við alltaf langar að líta þær upp. Again, með línulegum leit nálgun við myndum ekki setja þá báða á núlli. En í sérstakri keðju nálgun, við erum að fara að setja þá bæði á núlli og síðan að búa til lista af núll. Og við viljum ekki að skrifa grasker einfaldlega fyrir að því þá munum við gera ráð fyrir að grasker var aldrei sett inn. Ef við höldum bara eitt í staðsetningu sem væri slæmt. Þá væri ekki tækifæri af okkur alltaf - ef við hefðum alltaf afrit, þá erum við myndi bara eyða fyrstu gildi okkar. Svo að hvers vegna við gerum þessa nálgun. Eða það er hvers vegna við völdum - en aftur, við valdi sérstakt chaining nálgun, sem það eru mörg önnur aðferðir einn gæti valið. Er að svara spurningunni þinni? OK. Carlos. Línuleg leit myndi fela - ef við fundum árekstur á núlli, við myndi líta í næsta stað til að sjá hvort það var opið og setja það þar. Og þá erum við að líta á næstu íþrótt og sjá ef það var opið og setja það þar. Þannig að við að finna næsta boði opinn blettur og setja það þar. Aðrar spurningar? Já, AVI. Áhorfendur: Til að fylgja að því, hvað áttu við með næstu blettur? Þegar um er að kjötkássa töflunni eða í tengda listanum. JASON Hirschhorn: Fyrir línuleg forritun, engin tengd listum. Næsta blettur á kjötkássa töflunni. Áhorfendur: OK. Svo kjötkássa borð væri frumstilla að stærð - eins og fjöldi strengi sem þú varst að setja inn? JASON Hirschhorn: Þú myndir vilja það til að vera mjög stór. Já. Hér er mynd af því sem við bara brá á borðinu. Aftur höfum við árekstur hérna. á 152. Og þú munt sjá að við bjuggum A tengda listanum burt af því. Again, tætið borð aðskilið chaining nálgun er ekki það sem þú að taka fyrir vandamál setja sex en er eitt sem mikið af nemendur hafa tilhneigingu til að taka. Svo á að huga, láttu okkur að tala stuttlega Áður en við höldum út um vandamál sex, og svo skal ég segja sögu með þér. Við höfum þrjár mínútur. Heimadæmi sex. Þú hefur fjóra valkosti - hlaða, athuga, stærð, og afferma. Load - Jæja, höfum við verið að fara yfir álagi bara núna. Við brá álag á borðinu. Og við byrjuðum jafnvel kóðun mikið af setja í tengda listanum. Svo er ekki mikið meira en hlaða það sem við höfum bara verið að gera. Stöðva er þegar þú ert búinn eitthvað hlaðinn. Það er sama ferli og þetta. Sömu Fyrstu tveir hlutar þar sem þú kasta eitthvað inn í kjötkássa virka og fá gildi þess. En nú erum við ekki að setja það. Nú erum við að leita að því. Ég hef dæmi um kóða skrifað til að finna eitthvað í tengda listanum. Ég hvet þig til að æfa það. En innsær finna eitthvað er nokkuð svipað því að setja eitthvað. Reyndar dró við mynd af finna eitthvað í tengda listanum, færa gegnum þar til þú got til enda. Og ef þú got til enda og gat ekki finna það, þá er það ekki þar. Svo er það stöðva, í raun. Næst er stærð. Skulum sleppa stærð. Að lokum þarftu að afferma. Afferma er eitt sem við höfum ekki dregið á borð eða dulmáli ennþá. En ég hvet þig til að reyna erfðaskrá það í úrtaki okkar tengda listanum td. En afferma innsær er svipað frjáls - eða ég meina er svipuð að athuga. Nema nú hvert skipti sem þú ert að fara gegnum, þú ert ekki bara að haka við sjá hvort þú hefur gildi þar. En þú ert að taka þessi hnút og frjáls það, í raun. Það er það sem afferma biður þig að gera. Frjáls allt sem þú hefur malloced. Svo þú ert að fara í gegnum allan listann aftur, að fara í gegnum allt kjötkássa Tafla aftur. Í þetta sinn hakar ekki til að sjá hvað er þarna. Bara losa hvað er þar. Og að lokum stærð. Stærð ætti að vera framkvæmd. Ef þú framkvæma ekki stærð - Ég segi það eins og þetta. Ef þú framkvæma ekki stærð í nákvæmlega ein lína af kóða þar á meðal skila yfirlýsingu, ert þú gera stærð rangt. Svo tryggja stærð, fyrir fullt hönnun stig, ert þú að gera það á nákvæmlega einn lína af kóða, þar á meðal aftur yfirlýsingu. Og pakki ekki upp enn, Akchar. Uppveðraður nemandinn. Mig langaði til að segja þakka ykkur fyrir að koma til kafla. Hafa Happy Halloween. Þetta er búningur minn. Ég ætla að klæðast þetta á fimmtudaginn ef ég sé þig á skrifstofutíma. Og ef þú ert forvitinn um meira bakgrunnur og að þessu búning, finnst frjáls til skrá sig út 2011 kafla að sögum um af hverju ég er þreytandi grasker búning. Og það er sorgleg saga. Svo tryggja þú hafa sumir vefi nágrenninu. En um það, ef þú hefur einhverjar spurningar sem ég ætla að vera kyrr úti eftir kafla. Gangi þér vel á Heimadæmi sex. Og eins og alltaf, ef þú hefur einhverjar spurningar, láttu mig vita.