>> JASON HIRSCHHORN: Üdvözlünk mindenkit A fejezet hét.
Mi vagyunk a hét hét a kurzus.
És ez a következő csütörtök Halloween ezért vagyok
öltözött fel, mint a tök.
Nem tudtam lehajolni, és tegye a cipőmet, úgyhogy ezért vagyok
csak visel zoknit.
Én is nem visel semmit alá ezt, így nem tudom levenni, ha ez
zavaró az Ön számára.
Előre is elnézést ezért.
Önnek nem kell elképzelni, mi folyik itt.
Rajtam bokszolók.
Szóval minden rendben.
>> Van egy hosszabb történet arról, hogy miért vagyok öltözött, mint egy tök, de fogok
kivéve, hogy később ebben a fejezetben mert én szeretnék elkezdeni.
Van egy csomó izgalmas dolgot hogy menjen át ezen a héten.
Legtöbbjük közvetlenül kapcsolódik ehhez a heti probléma meg, helyesírási hibák.
Mi lesz megy át kapcsolódik listák és hash táblák
A teljes szakaszt.
Tettem ezt a listát minden héten, a lista forrásokat, hogy segítsen
az anyag ezt a folyamatot.
Ha veszteséges, vagy ha keres egy További információkért nézd meg az egyik
ezeket a forrásokat.
>> Ismét pset6 a helyesírási hibák, e heti Pset.
És ez azt is ösztönzi, és én javasoljuk, hogy egy más
forrásokat kifejezetten erre Pset.
Különösen a három I ve szerepel a képernyőn -
gdb, amit már ismerik és már használja egy ideje, az
lesz nagyon hasznos ezen a héten.
Így tettem, hogy akár itt.
De amikor éppen dolgozik C, akkor mindig használni gdb
programok hibakereséséhez.
Ezen a héten is Valgrind.
Tudja valaki, hogy mit valgrind csinál?
>> Közönség: Ellenőrzi a memória szivárgás?
>> JASON HIRSCHHORN: Valgrind ellenőrzi a memóriavesztés.
Tehát, ha malloc valami a programot, akkor kér memóriát.
Végén a program, akkor írni, ingyenes mindent, amit
malloced, hogy a memóriát vissza.
Ha nem írok szabad a végén, és A program csak arra a következtetésre,
Mindent automatikusan kell szabadítani.
És a kis program, ez nem olyan nagy dolog.
De ha írsz egy hosszabb futó program nem áll le,
szükségképpen, egy pár percig, vagy a Pár másodpercig, majd memóriavesztés
válhat egy hatalmas üzlet.
>> Így pset6, az elvárás, hogy akkor nulla memória szivárgást
a program.
Ellenőrzéséhez memóriavesztés, fuss valgrind és kapsz néhány szép
output hogy tudd, hogy a vagy nem minden szabad volt.
Majd gyakorolsz később ma, remélhetőleg.
>> Végül a diff parancs.
Régebben valami ahhoz hasonló a pset5 a Peek eszközzel.
Lehetővé tette, hogy belenézel.
Azt is használják diff is, egy A probléma meg spec.
De lehetővé tette, hogy összehasonlítani két fájlt.
Lehet összehasonlítani a bitmap fájlt, és Dátum fejlécek a személyzet megoldást, és
A megoldás pset5 ha úgy döntött, hogy használja azt.
Diff lehetővé teszi, hogy csinálni, valamint.
Össze lehet hasonlítani a helyes választ e heti probléma meg a választ
és nézd meg, hogy vonalban vagy látni hol a hiba.
>> Tehát ezek három jó eszközök akkor érdemes használni ezen a héten, és a
feltétlenül nézd meg a program ezekkel a három eszköz
mielőtt be!
Ismét, mint már említettem, minden héten, ha bármilyen visszajelzést a számomra - mindkét
pozitív és építő -
nyugodtan a fejét, hogy a honlapon alján a dia
és a bemeneti ott.
Igazán hálás vagyok minden és az összes visszajelzést.
És ha adsz nekem bizonyos dolgokat, hogy Meg tudom csinálni, hogy javítsa, vagy, hogy én vagyok
jól, hogy szeretné, hogy továbbra is azt venni, hogy a szív-és
Nagyon igyekszünk hallgatni a visszajelzéseket.
Nem ígérhetek fogok csinálni mindent, bár, mint visel
tök jelmez minden héten.
>> Így fogunk költeni a nagy részét rész, mint már említettem, beszélek
kapcsolt listák és hash táblák, melyek közvetlenül alkalmazandó, az
probléma meg ezen a héten.
Csatolt listák megyünk át viszonylag gyorsan, mert már töltöttem egy tisztességes darab
Az idő megy át azt a részt.
És hogy mi lesz egyenesen a kódolási problémák láncolt listák.
És akkor a végén fogunk beszélni, hash táblák és hogyan kell alkalmazni erre
heti probléma meg.
>> Láttad ezt a kódot korábban.
Ez egy olyan struktúra, és ez meghatározó valami új, úgynevezett csomópontot.
És belsejében egy csomópont van egy egész szám itt és van egy mutató
másik csomópont.
Már láttam ilyet.
Ezt már jön fel Egy pár hete.
Egyesíti a mutató, amit már dolgozik, és struktúrákat, amelyek lehetővé teszik
számunkra, hogy összekapcsolják a két különböző a dolgok egy adat típusát.
>> Van egy csomó folyik a képernyőn.
De minden meg kell viszonylag ismerik meg.
Az első sorban, akkor kijelentik, egy új csomópont.
És akkor benne, hogy az új csomópont, én meg az egész, hogy a csomópont egy.
Látjuk a következő sorban csinálok egy printf parancsot, de én szürkítve
A printf parancsot, mert az igazán Fontos része ez a vonal itt -
new_node.n.
Mit jelent a dot jelent?
>> Közönség: Menj a csomópont és értékeli az n értéket is.
>> JASON HIRSCHHORN: Ez pontosan így van.
Pont azt jelenti, elérheti a n részt Ennek az új csomópontot.
Ez a következő sor mit csinál?
Michael.
>> Közönség: teremt egy másik csomópont hogy fog mutatni az új csomópontot.
>> JASON HIRSCHHORN: így nem hozzon létre egy új csomópontot.
Ez létrehoz egy mi?
>> Közönség: A mutató.
>> JASON HIRSCHHORN: A mutató egy csomópont, amint az a csomópont * itt.
Tehát ez létrehoz egy mutatót egy csomóponthoz.
És melyik csomópont azt mutat az, Michael?
>> Közönség: Új csomópont?
>> JASON HIRSCHHORN: új csomópontot.
És ez mutat ott, mert mi már adta azt a címet az új csomópont.
És most ebben a sorban látjuk két különböző módon
kifejező ugyanezt.
És szerettem volna rámutatni, hogy ezek a két dolog ugyanaz.
Az első sorban, mi feloldási a mutatót.
Szóval, megyünk a csomópontot.
Ez az, amit ez a csillag jelent.
Láttuk, hogy a korábban a mutató.
Megy, hogy a csomópont.
Ez zárójelben.
És akkor hozzáférhet keresztül dot üzemeltető n eleme a csomópont.
>> Tehát, hogy a vevő a szintaxis láttuk, itt és most
használja a mutató.
Persze, hogy lesz olyan elfoglalt, ha írsz ezek a zárójelek -
hogy a csillag és a dot.
Ez lesz egy kicsit zsúfolt.
Tehát van egy kis szintaktikai cukor.
És ezt a sort itt -
ptr_node-> n.
Hogy nem pontosan ugyanolyan dolog.
Tehát a két sornyi kódot egyenértékű és fog tenni
pontosan ugyanaz a dolog.
>> De azt akartam, hogy pont azokat, mielőtt mennénk tovább, így érthető
Tényleg ez a dolog itt a csak szintaktikai cukor dereferencing
a mutató, majd megy n része, hogy a struktúra.
Bármilyen kérdése erről a slide?
OK.
>> Így fogunk átmenni egy pár A művelet, amit tehetünk a
kapcsolt listák.
A láncolt lista, emlékszem, egy sor csomópontok, hogy pont az egymással.
És általában kezdeni a mutató úgynevezett fej, általában, hogy pont
Az első dolog a listán.
Tehát az első sorban itt, megvan az eredeti L először.
Tehát azt, amit gondol - ez szöveg itt tud gondolni, mint
csak a mutató már tárolt valahol, hogy pontokat
az első elem.
És ebben a láncolt lista már négy csomópont.
Minden csomópont egy nagy doboz.
A nagyobb doboz belsejében nagy doboz az egész része.
És akkor van egy mutató része.
>> Ezek a dobozok nem állítják, hogy skála, mert mekkora
egy egész byte?
Mekkora most?
Four.
És milyen nagy ez a mutató?
Four.
Szóval tényleg, ha mi voltunk, hogy dolgozzon ez a skála mindkét dobozok
lenne az azonos méretű.
Ebben az esetben azt a beszúrni kívánt valamit a láncolt lista.
Tehát látható, itt vagyunk behelyezése Öt Mi áthalad a
láncolt lista, megtalálni, ahol az öt megy, majd helyezze.
>> Nézzük, hogy le, és menj egy kicsit lassabban.
Fogom mutatni, hogy a fórumon.
Tehát a node öt, hogy általunk létrehozott mallocs.
Miért mindenki nevetett?
Csak vicceltem.
OK.
Így már malloced öt.
Már létre ezt a csomópontot valahol máshol.
Van, hogy kész.
Kezdjük az elején a listát a kettő.
És szeretnénk beszúrni egy rendezett módon.
>> Tehát, ha azt látjuk, a két, és azt akarjuk, hogy öt, mit teszünk, ha látni
valamivel kevesebb, mint mi?
Mi az?
Azt szeretné szúrni öt ebbe láncolt lista, tartása sorrendje.
Látjuk a kettes számú.
Szóval, mit tegyünk?
Marcus?
>> Közönség: Hívja a mutató a következő csomópontot.
>> JASON HIRSCHHORN: És miért megyünk a következő?
>> Közönség: Mert ez az következő csomópont a listán.
És csak annyit tudunk, hogy a másik helyen.
>> JASON HIRSCHHORN: Öt nagyobb mint két, különösen.
Mert azt akarjuk tartani rendezve.
Tehát öt nagyobb, mint kettő.
Tehát lépni a következőre.
És most érünk négy.
És mi történik, ha eléri a négy?
>> Öt nagyobb, mint négy.
Így folyamatosan megy.
És most itt vagyunk hat.
És mit látunk hat?
Igen, Carlos?
>> KÖZÖNSÉG: Hat nagyobb, mint öt.
>> JASON HIRSCHHORN: Six nagyobb, mint öt.
Szóval, ez az, ahol szeretnénk beszúrni öt.
Azonban ne feledje, hogy ha csak egy mutató itt -
ez a mi külön mutató, ami áthaladó végig a listát.
És mi mutat hat.
Elvesztettük követni, mi előbb hat.
Tehát ha azt akarjuk beszúrni valamit ezen a listán tartása sorrendje, akkor
valószínűleg szükség van, hogy sok mutató?
>> Közönség: Kettő.
>> JASON HIRSCHORN: Two.
Egy nyomon követni az aktuális egy és nyomon követni a
az előzőt.
Ez csak egy egyszeresen láncolt lista.
Ez csak az egyik irányban megy.
Ha volt egy kétszeresen láncolt lista, ahol a mindent rámutatva, hogy a dolog
után és a dolog előtt, majd akkor nem kell csinálni.
De ebben az esetben nem akarjuk elveszíteni követni, mi jött elénk esetén
kell beszúrni öt valahol a közepén.
Mondjuk mi behelyezése kilenc.
Mi történne, ha a kaptunk nyolc?
>> Közönség: Meg kéne kap, hogy a null pontot.
Ahelyett, hogy null pont akkor volna hozzá egy elemet és utána
ez pont kilenc.
>> JASON HIRSCHORN: Pontosan.
Így kap nyolc.
Elérjük a végét a listán, mert ez mutat null.
És most, ahelyett, hogy pont null van ez pont a mi új csomópontot.
És mi meg a mutatót Az új csomópont null.
Van valakinek kérdése behelyezésével?
Mi van, ha nem érdekel tartva a rendezett lista?
>> Közönség: Dobd a elején vagy végén.
>> JASON HIRSCHORN: Stick azt az elején vagy a végén.
Melyiket kellene tennünk?
Bobby?
Miért a végén?
>> Közönség: mert az elején már ki van töltve.
>> JASON HIRSCHORN: OK.
Az elején már ki van töltve.
Ki akar vitatkozni ellen Bobby.
Marcus.
>> Közönség: Nos, akkor érdemes kibír az elején, mert
Különben, ha ez az érték A végén azt kell
áthalad a teljes lista.
>> JASON HIRSCHORN: Pontosan.
Tehát, ha gondolkodik runtime, a runtime behelyezése a végén
n lenne, a mérete.
Mi ez a nagy O futási behelyezése az elején?
Állandó időben.
Tehát, ha nem érdekel vezetése valami sorrendje, sokkal jobb, hogy csak
helyezze elején a lista.
És, hogy lehet tenni konstans id.
>> OK.
Következő művelet megtalálni, ami a többi - már megfogalmazott ezt a keresést.
De megyünk, hogy nézze át a láncolt lista néhány tárgyat.
Srácok, láttam kódot keresés előtt előadás.
De mi a fajta, csak tette a be, vagy legalábbis behelyezése
valami rendezve.
Akkor nézd át, majd csomópont a csomópont, amíg meg nem találja a számot, hogy te
keres.
Mi történik, ha eléri a végén a lista?
Mondd keresek kilenc és elérjük a végét a lista.
Mit csináljunk?
>> Közönség: return false?
>> JASON HIRSCHORN: return false.
Nem találom.
Ha elérjük a végét, a lista és a nem találja a számot, amit
keres, nincs benne.
Minden kérdést meg?
Ha ez egy rendezett lista, mi lenne eltérő lehet a keresést?
Igen.
>> Közönség: Ez meg az első érték ez nagyobb, mint az egy
keres és majd vissza hamis.
>> JASON HIRSCHORN: Pontosan.
Tehát ha ez egy rendezett lista, ha eljutunk valamit, ami nagyobb, mint amit
keresünk, nem kell, hogy menj a lista végére.
Mi is ezen a ponton return false mert nem fogjuk megtalálni.
A kérdés most, beszéltünk tartva kapcsolt listák sorrendje,
tartása rendezetlen.
Az lesz, amit te valószínűleg meg kell gondolni,
amikor a kódolási probléma meg öt, ha válasszon egy hash tábla külön
láncolás megközelítést, amely fogunk beszélni később.
>> De megéri, hogy a lista rendezett és így képes lesz, hogy talán még
gyorsabb keresést?
Vagy jobb, ha gyorsan be valami állandó runtime, de aztán
hosszabb keres?
Ez egy üzlet, ott, amit kap eldönteni, hogy mi a megfelelőbb
az adott problémát.
És ez nem feltétlenül egy teljesen helyes választ.
De ez persze egy döntés, amit kap tenni, és valószínűleg jó, hogy megvédje
hogy, mondjuk, egy-két megjegyzést, hogy miért úgy döntött, az egyik vagy a másik.
>> Végül, törlése.
Láttuk törlését.
Ez hasonló a keresést.
Keresünk az elem.
Mondjuk próbálunk törölni hat.
Úgy találjuk, hat itt.
A dolog, hogy van, hogy megbizonyosodjon arról, hogy nem az, hogy bármit is mutat
hat - mint látjuk lépésben két ide -
bármi is mutat, hogy hat igényeket hagyja hat most és változtatható
amit hat mutat.
Nem akarjuk, hogy valaha is árva a többi a listát elfelejti beállítani, hogy
előző mutató.
Aztán néha, attól A program akkor majd csak
törölni ezt a csomópont teljesen.
Néha akkor akar visszatérni az érték, hogy van ebben a csomópontban.
Szóval így törli működik.
Bármilyen kérdése a törölni?
>> Közönség: Tehát, ha akarsz törölni akkor lenne csak használja szabad, mert
feltehetően ez volt malloced?
>> JASON HIRSCHORN: Ha azt szeretné, hogy szabad valamit, ami pontosan így van, és
malloced azt.
Mondjuk volna vissza ezt az értéket.
Lehet, hogy vissza hat majd a szabad ez a csomópont és a hívás ingyenes rajta.
Vagy mi lenne talán hívás ingyenes első majd vissza hat.
>> OK.
Akkor térjünk rá a gyakorlatban kódolás.
Fogunk kódot három funkció.
Az első az úgynevezett insert_node.
Szóval kódot, amit e-mailben neked, és ha nézed ezt később
el tudja érni a kódot linked.c A CS50 honlapján.
De linked.c, van egy kis csontváz kód, ami már
írtak az Ön számára.
És akkor ott van egy-két funkció meg kell írni.
>> Először megyünk levelet insert_node.
És mi insert_node csinál IS beszúr egy egész szám.
És te, hogy a egész egy láncolt lista.
És főleg, meg kell , hogy a rendezett lista
a legkisebbtől a legnagyobbig.
Továbbá, ha nem akar helyezzen be ismétli.
Végül, mint látod insert_node vissza bool.
Szóval kéne, hogy a felhasználó tudja, e vagy sem a betét volt
sikeres visszaküldésével igaz vagy hamis.
Végén a program -
, és ebben a szakaszban nem szükséges aggódni felszabadítása semmit.
Tehát minden, amit tesz, vesz egy egész szám és helyezze be a listát.
>> Ez az, amit kérek, hogy nem most.
Ismét a linked.c, amit mind, a csontváz kódot.
És látnod kell alja felé A minta függvény deklaráció.
Azonban mielőtt a kódolás is C, én nagyon javasoljuk, hogy menjen
azokon a lépéseken voltunk gyakorló minden héten.
Már ment keresztül ennek egy képet.
Így kell egy kis megértést Az, hogy ez hogyan működik.
De azt javasoljuk, hogy írni Néhány pszeudokódját merülés előtt be
És fogunk menni át pszeudokódját mint egy csoport.
És ha egyszer megírtad a pszeudokódját, és ha egyszer már írt a
pszeudokódját mint egy csoport, akkor bemegy kódolás azt C.
>> A heads-up, a insert_node funkció talán a legnehezebb a
A három fogunk írni, mert én hozzá néhány további korlátok
a programozás, különösen azt, hogy akkor nem fog helyezzen
ismétlődések és a lista továbbra is rendezett.
Tehát ez egy nem triviális programban hogy meg kell kódot.
És miért nem veszi 06:55 percig csak, hogy dolgozik a
pszeudokódja és a kódot.
És akkor kezdjük megy, mint egy csoport.
Ismét, ha bármilyen kérdése van csak emeld fel a kezed, és én majd magához tér.
.
>> Azt is, ezt általában -
vagy én nem kifejezetten mondja, tud dolgozni az emberek.
De természetesen, én nagyon javasoljuk, Ha kérdése van, hogy kérje fel a
szomszéd ül melletted vagy akár dolgozni valakivel
mást, ha akarsz.
Ez nem kell, hogy az egyén csendes tevékenység.
>> Kezdjük írásban néhány pszeudokódja a táblán.
Ki tud adni nekem az első sorban a pszeudokódját a program?
Ehhez a funkcióhoz, hanem - insert_node.
Alden?
>> Közönség: Tehát az első dolgom az volt, hozzon létre egy új mutatót a csomópontot, és én
inicializálja azt mutat az azonos dolog, hogy a lista mutat.
>> JASON HIRSCHORN: OK.
Szóval egy új mutatót a listához, hogy ne a csomópontot.
>> Közönség: Rendben.
Igen.
>> JASON HIRSCHORN: OK.
És akkor mit akarunk csinálni?
Mi után?
Mi a helyzet a csomópont?
Jelenleg nincs egy csomópont.
Mi csak egy értéket.
Ha azt szeretné szúrni egy csomópont, mit is kell tennie, mielőtt mi is
gondolj helyezze?
>> KÖZÖNSÉG Ó, sajnálom.
kell malloc helyet egy csomópont.
>> JASON HIRSCHORN: Kiváló.
Csináljuk -
OK.
Nem tudja elérni, hogy a magas.
OK.
Fogunk lemenni, majd a mi két oszlopban.
Nem tudok menni, hogy -
OK.
Hozzon létre egy új csomópontot.
Tudod teremt egy másik mutató a listára vagy ha csak használni lista létezik.
Te tényleg nem kell csinálni.
>> Tehát egy új csomópontot.
Remek.
Ez az, amit nem először.
Mi a következő lépés?
>> Közönség: Várjon.
Ha létrehozunk egy új csomópontot most vagy kellene várni, hogy megbizonyosodjon arról, hogy az
ott nem lehet azonos a csomópont a listán, mielőtt létrehozni?
>> JASON HIRSCHORN: Jó kérdés.
Nézzük meg, hogy később, mert a legtöbb időt fogunk létrehozni
egy új csomópont.
Így fogjuk tartani, hogy itt van.
De ez egy jó kérdés.
Ha létre, és találunk egy másolatot, mit kell
mi, mielőtt visszatér?
>> Közönség: kiszabadítani.
>> JASON HIRSCHORN: Igen.
Valószínűleg kiszabadítani.
OK.
Mit tegyünk, miután hozzon létre egy új csomópont?
Annie?
>> Közönség: Azt hogy a szám a csomópont?
>> JASON HIRSCHORN: Pontosan.
Azt hogy a szám - mi malloc helyet.
Fogom hagyni, hogy minden egy sorba.
De igazad van.
Mi malloc tér, majd a tesszük be a számot
Azt is meg a mutatót része null.
Ez pontosan így van.
És akkor mi van utána?
Felhívtuk ezt a képet a táblán.
Szóval, mit tegyünk?
>> Közönség: megyünk végig a listát.
>> JASON HIRSCHORN: Menj át a listát.
OK.
És mit ellenőrizni minden csomópontban.
Kurt mit ellenőrizni az egyes csomópont?
>> Közönség: Lásd, hogy az n értékét amely csomópont nagyobb, mint az n értékhez
mi csomópont.
>> JASON HIRSCHORN: OK.
Azt fogom tenni -
igen, az OK gombra.
Tehát n -
Azt fogom mondani, ha az érték nagyobb, mint ez a csomópont, akkor mit csinálunk?
>> Közönség: Nos, akkor be A dolog van előtte.
>> JASON HIRSCHORN: OK.
Tehát, ha ez nagyobb, mint ez, akkor szeretnénk beszúrni.
De azt akarjuk, hogy helyezze mielőtt mert mi is lenne szükség
követi nyomon, majd, mi volt korábban.
Így be korábban.
Tehát valószínűleg valami elkerülte korábban.
Valószínűleg meg kell tartani követni, hogy mi folyik itt.
De mi lesz vissza.
Tehát mi értéke kevesebb, mint?
Kurt, mit tegyünk, ha értéke kisebb, mint a?
>> Közönség: Akkor csak menj kivéve, ha ez az utolsó.
>> JASON HIRSCHORN: Ez tetszik.
Így megy a következő csomópontot.
Hacsak nem az utolsó -
mi valószínűleg ellenőrzése, hogy a szempontból egy állapot.
De igen, a következő csomópont.
És ez kezd túl alacsony, így fogunk áttérni itt.
De ha -
is mindenki látja ezt?
Ha nem vagyunk egyenlő mit csináljunk?
Ha az érték próbálunk beszúrni egyenlő ez a csomópont értékét?
Igen?
>> Közönség: [hallható].
>> JASON HIRSCHORN: Igen.
Mivel ez a -
Marcus igaza van.
Mi volna, talán kész valami más.
De tekintettel arra, hogy amit létrehoztunk, itt meg kell szabadítani, majd vissza.
Oh boy.
Ez jobb?
Hogy-hogy?
OK.
Szabad és akkor mi teszünk vissza, [nem hallható]?
OK.
Vajon hiányzik valami?
Szóval hol vagyunk nyomon követése Az előzetes csomópont?
>> Közönség: Azt hiszem, ez menni után hozzon létre egy új csomópontot.
>> JASON HIRSCHORN: OK.
Így az elején akkor valószínűleg -
Igen, mi is létrehozhatunk egy mutatót az új csomópont, mint az előző csomópont mutatót, és
a jelenlegi csomópont mutatót.
Úgyhogy be itt.
Létrehozása a jelenlegi és az előző mutatókat a csomópontokat.
De amikor nem állítjuk be azokat mutatók?
Hol ezt, hogy a kódot?
Jeff?
>> Közönség: - érték körülmények között?
>> JASON HIRSCHORN: Melyik egy különös?
>> Közönség: Én csak összezavarodott.
Ha az érték nagyobb, mint ez a csomópont, nem azt jelenti, hogy szeretne menni
a következő csomópont?
>> JASON HIRSCHHORN: Tehát, ha az érték nagyobb, mint az érték a csomópont.
>> Közönség: Igen, akkor azt szeretné, hogy megy tovább le a pályáról, igaz?
>> JASON HIRSCHHORN: Így van.
Tehát ne helyezze be itt.
Ha az érték kisebb, mint a csomóponton, majd megyünk a következő csomópont - vagy akkor
be korábban.
>> Közönség: Várj, amely ezt a csomópont, és amely érték?
>> JASON HIRSCHHORN: Jó kérdés.
Érték jutó ezt a funkciót definíció az, amit mi adni.
Így érték az a szám vagyunk adni.
Tehát, ha az érték kisebb, mint ez node, időre van szükségünk, hogy helyezze.
Ha az érték nagyobb, mint ez a csomópont, megyünk a következő csomópontot.
És vissza az eredeti kérdésre, azonban, ahol -
>> Közönség: Ha az érték nagyobb, mint ez a csomópont.
>> JASON HIRSCHHORN: És így mit csinálunk itt?
Édes.
Így van.
Meg fogom írni frissítést mutatók.
De igen, a jelenlegi akkor frissíti a
pont a következő.
Van még mi hiányzik?
Így fogom írja ezt kódot gedit.
És ha már ezt, akkor egy pár percig dolgozni kódolás
Ezt C.
>> Szóval be a pszeudokód.
Egy gyors megjegyzés, mielőtt elkezdjük.
Azt nem lehet tudni, hogy teljesen befejezni ezt a minden
három, ezeket a funkciókat.
Van jó megoldás a számukra hogy én is e-mailt, hogy titeket
szakasz után, és ez lesz felkerül CS50.net.
Szóval nem javasoljuk, hogy menj nézd meg a szakaszok.
Azt javasoljuk, hogy próbálja meg ezeket a a saját, majd a gyakorlatban
probléma, hogy ellenőrizze a válaszokat.
Ezek mind úgy tervezték, hogy szorosan kapcsolódnak, és tartsák be, amit
meg kell tennie a probléma meg.
Szóval nem javasoljuk, hogy gyakorlatban ez a saját, majd a kód
ellenőrizze a válaszokat.
Mert akarok lépni a hash asztalok valamikor a szakaszban.
Tehát lehet, hogy nem jut át ​​az egészet.
De megteszem, amennyire csak lehet most.
>> OK.
Kezdjük.
Asam, hogyan hozzon létre egy új csomópont?
>> Közönség: Ugye struct *.
>> JASON HIRSCHHORN: Tehát van, hogy akár itt.
Ó, bocsánat.
Azt mondtad struct *.
>> Közönség: majd a [? fajta?] csomópont vagy c csomópont.
>> JASON HIRSCHHORN: OK.
Fogom nevezni new_node így maradhat következetes.
>> Közönség: És azt akarod beállítani, hogy élére, az első csomópont.
>> JASON HIRSCHHORN: OK.
Tehát most ez a mutató - így ez a nem teremtett új csomópontot még.
Ez csak mutat a első csomópont a listában.
Hogyan készíthetek egy új csomópont?
Ha kell hely, hogy hozzon létre egy új csomópontot.
Malloc.
És milyen nagy?
>> Közönség: A méret a struktúra.
>> JASON HIRSCHHORN: A méretét a struct.
És mi a struct hívják?
>> Közönség: Node?
>> JASON HIRSCHHORN: Node.
Tehát malloc (sizeof (node)); ad helyet.
És ezt a sort -
egy dolog hibás ezen a vonalon.
Van new_node egy pointert a struktúra?
Ez egy generikus név.
Mi ez -
node, pontosan.
Ez egy csomópont *.
És mit tegyünk után mi malloc valamit, Asan?
Mi az első dolog, amit csinálni?
Mi van, ha ez nem működik?
>> KÖZÖNSÉG Ó, ellenőrizze, hogy rámutat, hogy a csomópont?
>> JASON HIRSCHHORN: Pontosan.
Tehát, ha new_node egyenlő az egyenlők null, mit tegyünk?
Ez visszaad egy bool, ezt a funkciót.
Pontosan.
Jól néz ki.
Bármit, hozzá van?
Majd add a dolgokat a végén.
De eddig jól néz ki.
Létrehozása a jelenlegi és a korábbi mutatók.
Michael, hogyan tudom ezt megtenni?
>> Közönség: Meg kellett volna hogy csinál egy node *.
Meg kéne, hogy egy nem a new_node hanem a
csomópontok már van.
>> JASON HIRSCHHORN: OK.
Tehát a jelenlegi csomópont vagyunk.
Hívom, hogy Pn.
Rendben van.
Úgy döntöttünk, meg akarjuk tartani két, mert tudnunk kell, hogy
mi van előtte.
Mit kapnak kezdeti értéke?
>> Közönség: Értékük a listánkon.
>> JASON HIRSCHHORN: Tehát mi a az első dolog a listán?
Vagy honnan tudjuk, ahol a elején a lista?
>> Közönség: Hát nem telt el a funkciót?
>> JASON HIRSCHHORN: Így van.
Úgy telt el itt.
Tehát ha ez átment a funkciót, a indítsa el a lista, mit is
beállított áram egyenlő?
>> Közönség: Lista.
>> JASON HIRSCHHORN: Lista.
Ez pontosan így van.
Most azt a címét kezdete listánkon.
És mi a helyzet az előző?
>> Közönség: lista mínusz egyet?
>> JASON HIRSCHHORN: Van sem előtte.
Tehát mit tehetünk, hogy jelent semmit?
>> Közönség: Null.
>> JASON HIRSCHHORN: Igen.
Ez úgy hangzik, mint egy jó ötlet.
Tökéletes.
Köszönöm.
Menj át a listát.
Constantine, hogy meddig megyünk hogy menjen végig a listán?
>> Közönség: amíg el nem érjük null.
>> JASON HIRSCHHORN: OK.
Tehát, ha, míg a ciklus.
Mit csinálunk?
>> Közönség: Lehet, hogy a for ciklus?
>> JASON HIRSCHHORN: Csináljunk egy for ciklus.
OK.
>> Közönség: És mi mondjuk -
amíg a jelenlegi mutató nem egyenlő null.
>> JASON HIRSCHHORN: Tehát, ha tudjuk, hogy a állapot, hogyan lehet írni egy hurkot
alapján le ezt a feltételt.
Milyen hurok használjunk?
>> Közönség: Bár a.
>> JASON HIRSCHHORN: Igen.
Ennek már több értelme alapján le, hogy mit mondott.
Ha csak akar belemenni mi lenne Csak azt tudom, hogy a dolog, akkor lenne
értelme csinálni a while ciklus.
Bár a jelenlegi nem egyenlő nulla, ha az érték kisebb, mint a csomópont.
Akshar, add nekem ezt a sort.
>> Közönség: Ha a jelenlegi-> n n-nél kisebb érték.
Vagy fordított ezt.
Kapcsoló konzol.
>> JASON HIRSCHHORN: Elnézést.
>> Közönség: Változtassuk meg a konzol.
>> JASON HIRSCHHORN: Tehát ha ez nagyobb, mint értéket.
Mert ez zavaró a véleményét a fenti, fogom csinálni.
De igen.
Ha az érték kisebb, mint ez node, mit tegyünk?
Oh.
Megvan itt.
Helyezze előtt.
OK.
Hogyan csináljuk ezt?
>> Közönség: Még mindig én?
>> JASON HIRSCHHORN: Igen.
>> Közönség: You -
new_node-> kov.
>> JASON HIRSCHHORN: Akkor mi hogy lesz egyenlő?
>> Közönség: Ez lesz azonos a jelenlegi.
>> JASON HIRSCHHORN: Pontosan.
És így a másik -
mi mást is kell frissíteni?
>> Közönség: Ellenőrizze, hogy a múlt egyenlő null.
>> JASON HIRSCHHORN: Ha az előző -
Tehát, ha előző értéke null.
>> Közönség: Ez azt jelenti, hogy megy lesz a fejét.
>> JASON HIRSCHHORN: Ez azt jelenti ez lesz a feje.
Szóval, akkor mit csinálunk?
>> Közönség: Mi fej egyenlő new_node.
>> JASON HIRSCHHORN: Head egyenlő new_node.
És miért fej van, nem sorolja fel?
>> Közönség: Mivel a feje a globális változó, amely nem a kiindulási helyre.
>> JASON HIRSCHHORN: Édes.
OK.
És -
>> KÖZÖNSÉG: Akkor te még prev-> következő egyenlő new_node.
És akkor vissza igaz.
>> JASON HIRSCHHORN: Hol mi meg new_node végén?
>> Közönség: Szeretném -
Én meg, hogy az elején.
>> JASON HIRSCHHORN: Akkor mi sorban?
>> Közönség: Miután az if ellenőrzésére, ha ez ismert.
>> JASON HIRSCHHORN: Itt?
>> Közönség: Én megtenném new_node-> n egyenlő értéket.
>> JASON HIRSCHHORN: Jól hangzik.
Talán van értelme - mi nem tudniuk kell, mi lista vagyunk
mert mi csak szó egy lista.
Tehát jobb funkciót nyilatkozat ez csak azért, hogy megszabaduljon a
teljesen, és csak helyezze egy értéket a fejét.
Azt nem is kell tudni, hogy amit lista bent vagyunk
De én tartsa meg most, és akkor változtassa meg upon frissítése
A diák és a kód.
Annak érdekében, hogy jól néz ki most.
Ha az érték -, aki képes ezt a vonalat?
Ha -
mit csinálunk itt, Noah.
>> Közönség: Ha az érték nagyobb, mint akt-> N -
>> JASON HIRSCHHORN: Hogyan megyünk a következő csomópont?
>> Közönség: Curr-> n egyenlő new_node.
>> JASON HIRSCHHORN: Tehát n mely része a struktúra?
Az egész.
És new_node egy mutató egy csomópont.
Tehát mi része curr kellene frissíteni?
Ha nem, n, akkor mi a másik része?
Noah, mi a másik része.
>> Közönség: Ó, legközelebb.
>> JASON HIRSCHHORN: Next, pontosan.
Pontosan.
A következő a helyes.
És mit kell nekünk frissíteni, Noah?
>> Közönség: a mutatók.
>> JASON HIRSCHHORN: Tehát frissítettük áram.
>> Közönség: Előző-> kov.
>> JASON HIRSCHHORN: Igen.
OK, akkor szünet.
Ki segíthet itt?
Manu, mit tegyünk?
>> Közönség: Meg kell állítani ez egyenlő akt-> kov.
De vajon, hogy mielőtt az előző sor.
>> JASON HIRSCHHORN: OK.
Van még valami?
Akshar.
>> Közönség: Én nem hiszem, hogy célja, hogy változtatni akt-> kov.
Azt hiszem, azt jelentette, hogy nem akt egyenlő akt-> kov menni a következő csomópontot.
>> JASON HIRSCHHORN: Nagyon sajnálom, hol?
Milyen sorban?
Ez a vonal?
>> Közönség: Igen.
Legyen curr egyenlő akt-> kov.
>> JASON HIRSCHHORN: Szóval ez a helyes mivel a jelenlegi egy
mutató egy csomópont.
És azt akarjuk, hogy pont a következő node, hogy mi kap jelenleg
mutatott.
Curr maga is a következő.
De ha mi voltunk, hogy frissíteni curr.next, akkor lenne frissítése az aktuális megjegyzés
önmagában, nem ott, ahol ez a pointer mutatott.
Mi a helyzet ezen a vonalon, mégis.
Avi?
>> Közönség: Előző-> kov egyenlő Pn.
>> JASON HIRSCHHORN: Tehát újra, ha előző egy mutató egy node, prev-> next a
tényleges mutatót a csomópontot.
Szóval ez lenne frissítésekor mutatót egy csomópont a Pn.
Nem akarjuk frissíteni a mutatót egy csomóponthoz.
Azt akarjuk, hogy frissíteni a korábbi.
Szóval hogyan lehet csinálni?
>> Közönség: Ez csak a prev.
>> JASON HIRSCHHORN: Így van.
Előző egy mutató egy csomópont.
Most már változó, hogy egy új mutató a csomópont.
OK Lépjünk le.
Végül ez utóbbi feltétel.
Jeff, mit csinálunk itt?
>> Közönség: Ha az érték egyenlő akt-> n.
>> JASON HIRSCHHORN: Elnézést.
Te jó ég.
Mi az?
Érték == akt-> n.
Mit csináljunk?
>> Közönség: Az ember szabad a new_node, és akkor azt vissza hamis.
>> JASON HIRSCHHORN: Ez az, amit írtunk eddig.
Van valakinek valami hozzá, mielőtt teszünk?
OK.
Próbáljuk meg.
Az ellenőrzés elérjük a végét egy nem void funkciót.
Avi, mi folyik itt?
>> Közönség: kéne, hogy cserébe igaz kívül a while ciklus?
>> JASON HIRSCHHORN: Nem tudom.
Akarod, hogy?
>> Közönség: Nem baj.
Nem.
>> JASON HIRSCHHORN: Akshar?
>> Közönség: Azt hiszem, azt jelentette, hogy fel return false végén
A while ciklus.
>> JASON HIRSCHHORN: Hol akarod, hogy menjen?
>> Közönség: Mint kívül a while ciklus.
Tehát, ha kilép a while ciklus, hogy az eszköz hogy elérte a végén, és
semmi sem történt volna.
>> JASON HIRSCHHORN: OK.
Szóval, mit csinálunk itt?
>> Közönség: A return false ott is.
>> JASON HIRSCHHORN: Ó, csinálni mindkét helyen?
>> Közönség: Igen.
>> JASON HIRSCHHORN: OK.
Menjünk?
Te jó ég.
Sajnálom.
Elnézést kérek a képernyőn.
Ez a fajta akadva ránk.
Tehát válasszon egy lehetőséget.
Zero, egy a kódot, kilép a program.
Egy lapkák valamit.
Nézzünk be a három.
A betét nem volt sikeres.
Megyek kinyomtatni.
Nem semmi.
OK.
Lehet, hogy ez csak a véletlen műve.
Helyezze be az egyik.
Nem sikerült.
OK.
Fussunk át GDB nagyon gyorsan hogy nézd meg, mi folyik itt.
>> Emlékezz gdb. / A nevét a program kerül minket GDB.
Ez sokat kezelni?
A villogó?
Valószínűleg.
Csukd be a szemed, és vegyen egy mély lélegzik ha elfárad
néztem.
Vagyok GDB.
Mi az első dolog, amit csinálni GDB?
Van, hogy kitaláljuk, mi folyik itt.
Lássuk csak.
Jelenleg hat percig szám , hogy mi folyik itt.
Szünet fő.
És akkor mit tegyek?
Carlos?
Run.
OK.
Nézzünk válasszon egy lehetőséget.
És mit N csinálni?
Tovább.
Igen.
>> Közönség: Nem mondod -
Nem azt mondják, hogy a fej volt kezdeti értéke null az elején.
De azt hittem, azt mondta, hogy minden rendben volt.
>> JASON HIRSCHHORN: Menjünk - nézzük A GDB, aztán megyünk vissza.
De ez úgy hangzik, mintha már néhány ötlet, hogy mi folyik itt.
Tehát szeretné szúrni valamit.
OK.
Mi be.
Adjon meg egy int.
Majd be három.
És akkor én vagyok ezen a vonalon.
Hogyan nyissunk hibakeresés A betét ismert funkciót?
Te jó ég.
Ez nagyon sok.
Az, hogy kiborult a sok?
>> Közönség: Ó, meghalt.
>> JASON HIRSCHHORN: Én csak húzta ki.
OK.
>> Közönség: Lehet, hogy a másik végét a drót.
>> JASON HIRSCHHORN: Wow.
Tehát a lényeg -
mit mondtál?
>> Közönség: Azt mondtam, az iróniát a technikai nehézségek ebben az osztályban.
>> JASON HIRSCHHORN: Tudom.
Bárcsak felett azt a részét.
[Nem hallható]
Ez jól hangzik.
Miért nem vagytok kezdeni gondolkodni mit tehettünk volna rossz,
és mi lesz hát a 90 másodperc.
>> Avica, fogom kérni, hogy hogyan megy belső insert_node debug azt.
Szóval, ez az, ahol utoljára abbahagytuk.
Hogyan tudok bemenni insert_node, Avica, hogy vizsgálja meg, mi folyik itt?
Mi GDB parancs?
Szünet nem vigyél be.
Nem Marquise tudja?
>> Közönség: Mi van?
>> JASON HIRSCHHORN Mi GDB parancs ÉN használ bemenni ezt a funkciót?
>> Közönség: lépés?
>> JASON HIRSCHHORN: Step keresztül S. Ez visz benne.
OK.
New_node mallocing néhány helyet.
Az egész úgy néz ki, mint a fog.
Vizsgáljuk meg new_node.
Meg van egy kis memória cím.
Nézzük -
ez mind helyes.
Tehát itt minden úgy tűnik, hogy működik megfelelően.
>> Közönség: Mi a különbség a P és a kijelző?
>> JASON HIRSCHHORN: P jelentése nyomtatás.
És azt kérdezi, mi a különbség az, hogy ez?
Ebben az esetben semmi.
De általában vannak bizonyos különbségek.
És meg kell nézni a GDB kézikönyvben.
De ebben az esetben, semmi.
Hajlamosak vagyunk arra, hogy használja a nyomtatási, mégis, mert nem kell, hogy sokkal többre
nyomtat egyetlen érték.
>> OK.
Tehát mi on line 80 kódunkat, beállítás node * curr egyenlő a listához.
Engedje meg, nyomtassa ki Pn.
Ez egyenlő lista.
Édes.
Várjon.
Ez egyenlő valamit.
Ez nem tűnik helyesnek.
Ott vagyunk.
Ez azért van, mert a GDB, jobb, ha a ez a vonal akkor rajta
nem hajtotta végre még.
Így meg kell, hogy ténylegesen típus mellett végre a vonal
előtt látta az eredményeket.
Tehát itt vagyunk.
Most végre ezt a sort, előző értéke null.
Tehát újra, ha kinyomtatni előző nem fogjuk látni valami furcsát.
De ha tényleg végre, hogy vonal, akkor látni fogjuk,
hogy a vonal működött.
>> Tehát Pn.
Ezek a jó.
Nem igaz?
Most már ezen a vonalon itt.
Bár a curr nem egyenlő null.
Nos, mit akt egyenlő?
Most látta, hogy párja null.
Mi kinyomtatta.
Majd nyomtassa ki újra.
Tehát az, hogy míg a hurok fog végre?
>> Közönség: Nem.
>> JASON HIRSCHHORN: Tehát amikor beírtam, hogy vonal, látod, mi ugrott egészen
aljára, return false.
Aztán megyünk return false és menj vissza a programot, és
végül nyomtassa ki, mint láttuk, A betét nem volt sikeres.
Tehát bárki bármilyen ötletet, hogy mit meg kell tennie, hogy erősít ez?
Fogok várni, amíg nem látom pár kéz megy fel.
Nem végrehajtani ezt.
Ne feledje, ez volt az első dolog, amit csinálunk.
Nem fogok csinálni egy pár.
Fogok csinálni egy pár.
Mert egy pár olyan két.
Megvárom több, mint kettő.
>> Az első behelyezés, akt, alapértelmezés szerint egyenlő null.
És ez a ciklus csak végrehajt ha curr nem null.
Akkor hogyan lehet megkerülni ezt?
Látom három kéz.
Megvárom több mint három.
Marcus, mit gondolsz?
>> Közönség: Nos, ha szükség van rá, hogy végre többször, csak
változás, hogy a do-while ciklus.
>> JASON HIRSCHHORN: OK.
Vajon, hogy oldja meg a problémát, igaz?
>> Közönség: Ebben az esetben nem, mert az az a tény, hogy a lista üres.
Szóval, akkor valószínűleg csak kell hozzá nyilatkozat arról, hogy ha a ciklus kilép
akkor van, hogy a végén A lista, ahol pont akkor
csak helyezze.
>> JASON HIRSCHHORN: Ez tetszik.
Ennek van értelme.
Ha a hurok kilép -
mert akkor return false itt.
Tehát, ha a ciklus kilép, akkor már itt tartunk Az a lista végére, vagy talán a
indul a lista, ha nincs semmi azt, ami ugyanaz, mint a végén.
Tehát most szeretnénk beszúrni itt valami.
Tehát hogyan, hogy a kódot nézd, Marcus?
>> Közönség: Ha már megvan a csomópontot malloced, akkor csak annyit,
new_node-> kov egyenlő nulla, mivel azt, hogy a végén.
Vagy new_node-> kov egyenlő null.
>> JASON HIRSCHHORN: OK.
Bocsánat.
New_node-> kov egyenlő null mert mi vagyunk a végén.
Ez nem tesz be!
Hogyan rakjuk a listán?
Rendben.
Ez csak a beállítás, egyenlő.
Nem, hogy mi is valójában tedd a listán?
Mit mutat a a lista végén?
>> Közönség: Head.
>> JASON HIRSCHHORN: Tessék?
>> Közönség: Head mutat az a lista végére.
>> JASON HIRSCHHORN: Ha nincs semmi A lista, fej rámutatva, hogy a
a lista végén.
Annak érdekében, hogy jó lesz a első behelyezése.
Mi a helyzet, ha van egy pár a dolgok a listán?
Mint nem akarjuk beállítani fej egyenlő new_node.
Mit akarsz itt?
Igen?
Valószínűleg a korábbi.
Fog, hogy a munka?
Emlékezzünk vissza, hogy az előző csak a mutatót egy csomóponthoz.
És az előző egy helyi változót.
Tehát ez a sor meg egy helyi változó, korábbi, azonos, vagy
mutat az új csomópont.
Ez valójában nem tette a listánkon, mégis.
Hogyan tedd a listán?
Akchar?
>> Közönség: Azt hiszem, do áram-> kov.
>> JASON HIRSCHHORN: OK.
akt-> kov.
Tehát újra, csak azért vagyunk lent Itt van, mit jelent a jelenlegi egyenlő?
>> Közönség: Egyenlő null.
>> JASON HIRSCHHORN: És mi történik, ha mi null-> kov?
Mit fog kapni?
Majd kap egy szegmentációs hiba.
>> Közönség: Do akt egyenlő null.
>> JASON HIRSCHHORN: Ez ugyanaz a dolog az előző, mégis, mert ott van
lokális változót vagyunk beállítás egyenlő az új csomópontot.
Menjünk vissza a kép behelyezése valamit.
Mondjuk mi behelyezése a végén a lista, így itt.
Van egy érvényes mutató, ami mutat null és egy korábbi pont
ami mutat 8.
Szóval mit is kell frissíteni, Avi?
>> Közönség: Előző-> a következő?
>> JASON HIRSCHHORN: Előző-> következő az, ami szeretnénk frissíteni, mert a
valóban be azt a végén a listán.
Még mindig van egy hiba, mégis, hogy fogunk befut.
Mi ez bug?
Igen?
>> Közönség: Ez lesz, hogy visszatérjen hamis ebben az esetben?
>> JASON HIRSCHHORN: Ó, nem majd vissza hamis.
De van egy másik hiba.
Tehát mi kell tenni cserébe igaz.
>> Közönség: Vajon az előző is egyenlő null tetején a lista?
>> JASON HIRSCHHORN: Tehát az előző még egyenlő null a legelején.
Szóval hogyan lehet túljutni, hogy?
Igen?
>> Közönség: Azt hiszem, meg tudod csinálni egy csekket mielőtt a while ciklus, hogy ha ez
egy üres lista.
>> JASON HIRSCHHORN: OK.
Szóval menjünk innen.
Van egy csekket.
Ha -
>> Közönség: Tehát, ha fej egyenlő értéke null.
>> JASON HIRSCHHORN: Ha a fej egyenlő egyenlő null -
hogy elmondja, ha ez egy üres lista.
>> Közönség: És akkor do fej egyenlő az új.
>> JASON HIRSCHHORN: Head egyenlő new_node?
És mi mást kell tennünk?
>> Közönség: És akkor vissza igaz.
>> JASON HIRSCHHORN: Nem egészen.
Mi hiányzik egy lépéssel.
>> Közönség: New_node következő van, hogy pont a null.
>> JASON HIRSCHHORN: Pontosan, Alden.
És akkor mi is vissza igaz.
OK.
De ez még mindig egy jó ötlet, hogy a dolgokat végén a lista, nem igaz?
Rendben van.
Még mindig lehet, hogy tényleg kap az a lista végére.
Tehát ez a kód rendben van, ha mi vagyunk a a lista végére, és van néhány
a dolgok a listán?
Nem igaz?
Mert még mindig Marcus ötlete.
Lehet, hogy lépjen ki a hurok, mert mi vagyunk az a lista végén.
Tehát még mindig akarjuk, hogy ez kódot itt?
>> Közönség: Igen.
>> JASON HIRSCHHORN: Igen.
És mit kell változtatni ezt?
Igaz.
Jól hangzik mindenkinek eddig?
Van valakinek -
Avi, van valami hozzá?
>> Közönség: Nem.
>> JASON HIRSCHHORN: OK.
Így tettünk egy pár változás.
Tettük ezt a csekket, mielőtt bement egy üres lista.
Így már gondoskodott egy üres lista.
És itt gondját behelyezése valamit a végén a lista.
Így úgy tűnik, mintha ez a while ciklus figyelembe ellátás a dolgok között,
valahol a listában, ha olyan dolgok a listán.
>> OK.
Fussunk ezt a programot.
Nem sikerült.
>> Közönség: Nem sikerült.
>> JASON HIRSCHHORN: Ó, Nem sikerült.
Jó pont, Michael.
Adjuk hozzá a make kapcsolt.
87. sorban van egy hiba.
87. sorban.
Alden, ez volt az a vonal, amit adtál.
Mi a baj?
>> Közönség: Meg kell, hogy null.
>> JASON HIRSCHHORN: Kiváló.
Pontosan így van.
Meg kell null.
Legyen újra.
Fordítsuk le.
OK.
Nézzünk be a három.
A lapka sikeres volt.
Nézzük nyomtassa ki.
Ó, bárcsak tudnánk ellenőrizni.
De még nem történt meg a nyomtat funkció még.
Nézzük meg valami mást.
Mit kell belépünk?
>> Közönség: Hét.
>> JASON HIRSCHHORN: Hét?
>> Közönség: Igen.
>> JASON HIRSCHHORN: Van egy szegmens hibája.
Tehát van egy, de világosan nem tud két.
Ez 05:07.
Így lehet hibakeresést ezt három percig.
De fogom hagyni minket és lépni a hash táblák.
De ismétlem, a választ ez a kód Én e-mailben neked egy kicsit.
Nagyon közel vagyunk hozzá.
Én nagyon javasoljuk, hogy kitaláljuk, mi folyik itt, és javítsd ki.
Szóval majd e-mailben ezt a kódot jól valamint a megoldás -
talán a megoldás később.
Először is ezt a kódot.
>> A másik dolog, amit szeretnék csinálni, mielőtt borítás még nem szabadult semmit.
Szóval azt akarom mutatni, hogy mi Valgrind néz ki.
Ha fut valgrind határokat A programunk,. / kötött.
Ismét szerint ez a dia, akkor kell futtatni Valgrind bizonyos típusú
lehetőség, ebben az esetben - Szivárgás-ellenőrzés = teljes.
Szóval írni valgrind - Szivárgás-ellenőrzés = teljes.
Tehát ez fog futni valgrind A programunk.
És most a program valóban fut.
Így fogjuk futtatni, mint előtt, hogy valamit be
Azt fogom tenni, három.
Ez működik.
Nem fogom próbálni tenni valamit mást, mert fogunk
kap egy seg hamis ebben az esetben.
Szóval csak úgy, hogy kilép.
>> És most látod itt szivárgás és a kupac összefoglaló.
Ezek azok a jó dolog, hogy szeretné, hogy nézd meg.
Tehát a halom összefoglaló - azt mondja, a használat at exit - nyolc bájt egyben.
Ez egyben a node mi malloced.
Michael azt mondta, mielőtt a csomópont nyolc falatok mert az egész
és a mutató.
Szóval ez a csomópont.
És akkor azt mondja, hogy használni malloc hétszer és felszabadította
valami hatszor.
De soha nem úgynevezett szabad, úgyhogy nincs ez mit beszél.
>> De legyen elég annyi, hogy amikor a a program fut, malloc kerül meghívásra
néhány más helyen, hogy mi Nem kell aggódni.
Tehát malloc valószínűleg az úgynevezett néhány helyen.
Nem kell aggódni, hogy hol.
De ez tényleg minket.
Ez első sorban a számunkra.
Elhagytuk a blokk.
És láthatjuk, hogy itt A szivárgás összefoglaló.
Still elérhető -
nyolc bájt egyben.
Ez azt jelenti, hogy a memória -
már kiszivárgott, hogy az emlékezet.
Határozottan elveszett -
valami elveszett a jó.
Általában, akkor nem látni semmit ott.
Még elérhető általában, ahol a fogod látni a dolgokat, ahol akkor akar
hogy vizsgálja meg, hogy milyen kódot kéne már felszabadult, de elfelejtette, hogy szabad.
>> És aztán, ha nem ez volt a helyzet, ha nem szabad mindent,
akkor ellenőrizze, hogy.
Nézzük csak futtatni a programot nem hozta meg semmit.
Látni fogod itt használatban exit -
nulla byte nulla blokkokat.
Ez azt jelenti, hogy már semmi sem maradt Ha ez a program kilép.
Tehát mielőtt a pset6, fuss valgrind és győződjön meg róla, hogy nincs
minden memóriavesztés a programban.
Ha bármilyen kérdése van a valgrind, nyugodtan, hogy elérje.
De ez, hogyan használja azt.
Nagyon egyszerű - nézd meg, van használatban exit -
minden bájt minden blokk.
>> Ezért dolgoztunk a betét csomóponton.
Volt két másik funkció itt - nyomtat csomópontok és ingyenes csomópontok.
Ismét, ezek a funkciók, amelyek lesz jó, hogy a gyakorlatban
mert segít, hogy ne csak a ezeket a minta a gyakorlatok, hanem
A probléma meg.
A térkép a szép szorosan a dolgokat fogsz kell tennie a
probléma meg.
De azt szeretnénk, hogy győződjön meg arról, megérintjük mindent.
És hash táblázatok is fontos, hogy mit csinálunk részben ebben a
hét - és a probléma meg.
>> Így fogjuk befejezni a szakaszt beszél hash táblákat.
Ha azt észleli, csináltam egy kis hash tábla.
Ez nem az, amit mi beszélünk körülbelül, de.
Beszélünk a másik típusú hash táblák.
És a fő, a hash tábla nem más, mint egy
tömb és egy hash függvényt.
Fogunk beszélni egy kicsit, csak hogy győződjön meg róla, mindenki érti, mi a
hash függvény.
És én most mondom, hogy ez nem más, mint két dolog -
tömb és a hash függvényt.
És itt vannak a lépések segítségével amelyre ez működik.
>> Ott a tömb.
Ott a funkciót.
Különösen a hash funkciókat kell nem egy pár dolgot ezzel.
Fogok beszélni konkrétan erről a probléma meg.
Ez valószínűleg meg is hogy egy szövegben.
És mi a helyzet, hogy visszatérjen?
Milyen adattípus?
Alden?
A hash függvény visszatérési?
Egy egész szám.
Tehát ez az, amit a hash asztal áll -
a tábla formájában tömb és a hash függvényt.
Hogyan működik?
Úgy működik, három lépésben.
Azt, hogy ez a kulcs.
Ebben az esetben, akkor, hogy ez a szöveg.
Hívjuk a hash függvényt egy lépés A legfontosabb, és kapunk egy értéket.
>> Pontosabban, azt fogja mondani, kapunk egy egész szám.
Ez az egész szám, vannak nagyon specifikus határok, hogy mit, hogy egész lehet.
Ebben a példában, a mi tömb a mérete a három.
Tehát mi a számok, hogy egész legyen.
Milyen tartományban érvényes értékei hogy egész, a visszatérési típus ennek
hash függvény?
Nulla, egy és kettő.
A lényeg a hash függvény, hogy kitalálni a helyét a tömbben
ahol a kulcs megy.
Már csak három lehetséges helyen van -
nulla, egy vagy kettő.
Tehát ez a funkció jobb megtérülést nulla, egy vagy kettő.
Egyes érvényes Index ebben a tömbben.
>> És akkor attól függően, hol visszatér, látható, van array nyitva
zárójelbe az értéket.
Ez az, ahol a kulcsot.
Így dobja a sütőtök, kikerülünk nulla.
A tömb konzol 0 tesszük sütőtök.
Mi dobja macskák jutunk ki az egyik.
Azt hogy a macska az egyik.
Azt hogy a pók.
Kapunk ki kettő.
Azt hogy pók tömb tartó kettő.
Nem lenne olyan rossz, ha úgy működött, mint ezt.
De sajnos, mint látni fogjuk, ez egy kicsit bonyolultabb.
>> Mielőtt odaérünk, bármilyen kérdése erről az alapvető
set-up egy hash tábla?
Ez a kép pontosan mi felhívtuk a táblán.
De mivel felhívtuk azt a fórumon, azt most nem megyek bele tovább.
Lényegében gombok, a mágikus fekete doboz - vagy ebben az esetben, kékeszöld doboz - egy
hash funkció teszi őket vödörben.
És ebben a példában vagyunk nem hozta a nevét.
Mi amivel a kapcsolódó telefon száma a nevet a vödör.
De akkor is nagyon jól, csak fel a nevét a tengerben.
>> Ez csak egy képet, amit felhívtuk a táblán.
Van lehetséges buktatókat, mégis.
És van két különösen diák, hogy én akarok menni.
Az első arról szól, a hash függvényt.
Szóval a kérdést, hogy mi tesz egy jó hash függvény?
Adok két válasz.
Az első az, hogy ez a determinisztikus.
Összefüggésében a hash függvények, mit jelent ez?
Igen?
>> Közönség: Ez meg az index konstans id?
>> JASON HIRSCHHORN: Az nem, hogy mit jelent.
De ez egy jó tipp.
Bárki más egy becslés hogy ez mit jelent?
Ez egy jó hash függvény determinisztikus?
Annie?
>> Közönség: Ez a kulcs csak akkor lehet térképezni hogy egy helyen a hash tábla.
>> JASON HIRSCHHORN: Ez pontosan így van.
Minden alkalommal, amikor fel sütőtök, mindig visszatér nulla.
Ha fel a sütőtök és a hash függvény nulla, de a
valószínűsége visszatérő valamit mást nullánál nagyobb -
így talán visszatérhet az egyik néha vagy két alkalommal -
hogy ez nem egy jó hash függvény.
Teljesen igazad van.
A hash függvény, vissza kell adnia a egész pontosan ugyanolyan, ebben az esetben, a
pontosan ugyanolyan húr.
>> Lehet, hogy vissza pontosan ugyanolyan egész a pontosan ugyanolyan húr
függetlenül attól, kapitalizáció.
De ebben az esetben még mindig mérvadó, hiszen több dolgot
vannak leképezve ugyanazt az értéket.
Ez rendben van.
Mindaddig, amíg csak egy van output egy adott bemenet.
>> OK.
A másik dolog az, hogy visszatér érvényes indexeket.
Azt hozta fel, hogy a korábbi.
Ez a hash funkció -
oh boy -
a hash függvény vissza érvényes indexeket.
Tehát mondjuk -
térjünk vissza erre a példára.
A hash függvény számol fel A betűk a szó.
Ez a hash függvényt.
, És visszaadja az egész.
Tehát, ha van a szó A, ez majd vissza egy.
És ez megy, hogy egy itt.
Mi történik, ha tettem a szó denevér?
Ez lesz, hogy visszatérjen a három.
Hol bat menni?
>> Ez nem illik.
De kell menni valahova.
Ez a hash tábla után, és mindent kell menni valahova.
Szóval, hol bat menni?
Minden gondolat?
Találgatások?
Jó találgatások?
>> Közönség: Zero.
>> JASON HIRSCHHORN: miért nulla?
>> Közönség: Mivel a három modulo három nulla?
>> JASON HIRSCHHORN: három modulo három nulla.
Ez egy nagy találgatás, és ez a helyes.
Tehát ebben az esetben kell valószínűleg menni nulla.
Tehát egy jó módja annak, hogy ezt a hash funkció csak akkor ad vissza érvényes indexek
a modulo ez a méret az asztal.
Ha modulo amit ez a bevallásokat három, te mindig fog kapni
valami között nulla, egy, és két.
És ha ez mindig visszatér a hét, és a mindig modulo három, akkor
mindig lesz, hogy ugyanazt a dolgot.
>> Tehát még mindig determinisztikus ha modulo.
De ez biztosítja, hogy soha nem kap valamit -
Érvénytelen az ipar.
Általában, hogy a modulo történjen belül a hash függvényt.
Szóval nem kell aggódni emiatt.
Csak tudja biztosítani, hogy ez egy érvényes Index.
Bármilyen kérdése ezen lehetséges buktató?
>> OK.
És ott vagyunk.
Ezután a lehetséges buktató, és ez az a nagy dobás.
Mi történik, ha két kulcs megjelenítése ugyanazt az értéket?
Tehát két módon kezelni ezt.
Az első az úgynevezett lineáris szondázás, ami vagyok
nem megyek át.
De meg kell ismernie, hogyan ami működik, és mi az.
>> A második én megyek át mert ez az egyik, hogy sok
az emberek valószínűleg a végén úgy döntött, használni a problémát meg.
Persze, nem kell.
De a probléma meg, sokan inkább úgy dönt, hogy hozzon létre egy hash tábla
külön láncolási végrehajtására a szótárban.
Szóval megyek át, hogy mit jelent hogy hozzon létre egy hash táblát
külön láncolás.
>> Így tettem a sütőtök.
Visszatér nulla.
És tettem sütőtök itt.
Aztán hozott -
mi egy Halloween-témájú dolog?
>> Közönség: Candy.
>> JASON HIRSCHHORN: Candy!
Ez egy nagy ember.
Tettem a cukorka, és a cukorka is ad nekem nulla.
Mit tegyek?
Valami ötlet?
Mert minden fajta tudják mi külön-láncolatok.
Tehát valami ötleted, mit tegyek?
Igen.
>> Közönség: Elhelyezés a húr valójában a hash tábla.
>> JASON HIRSCHHORN Szóval megyünk felhívni a jó ötlet itt.
OK.
>> Közönség: Legyen a hash tábla [Nem hallható]
a mutató, amely rámutat, hogy az elején egy listát.
És akkor már tök az első érték abban a láncolt lista és édesség is
a második érték, hogy láncolt lista.
>> JASON HIRSCHHORN: OK.
Marcus, hogy kiemelkedő volt.
Fogom törni azt le.
Marcus azt mondja, nem felülírja sütőtök.
Az rossz lenne.
Ne tegye cukorkát valahol máshol.
Meg fogjuk őket mind nulla.
De fogunk foglalkozni helyezzük el őket nullára
ami egy lista nulla.
És mi lesz, hogy hozzon létre egy listát a leképezett mindent, ami a nullához.
És a legjobb módja annak, megtanultuk, hogy hozzon létre a lista, amely képes növekedni, és csökken
dinamikusan nem tartozik másik tömböt.
Tehát nem egy több dimenziós tömb.
De ahhoz, hogy csak hozzon létre egy láncolt lista.
>> Tehát mi azt javasolta -
Megyek, hogy egy új -
, hogy hozzon létre egy tömb mutató, egy sor mutató.
OK.
Valami ötlet, vagy tipp, milyen típusú Ezen mutatók kellene?
Marcus?
>> Közönség: Mutatók -
>> JASON HIRSCHHORN: Mert mondta egy láncolt lista, így -
>> Közönség: Node mutatók?
>> JASON HIRSCHHORN: Node mutatók.
Ha a dolgok a mi kötött listán csomópontok akkor
legyen node mutatók.
És mit egyenlő először?
>> Közönség: Null.
>> JASON HIRSCHHORN: Null.
Tehát itt van az üres dolog.
Tök visszatér nulla.
Mit csináljunk?
Séta velem ez?
Valójában, Marcus már kaptam.
Valaki más kísérjen át rajta.
Mit teszünk, ha -
ez úgy néz ki, nagyon hasonlít a , amit éppen csinál.
Avi.
>> Közönség: fogok egy kitalálni.
Tehát, amikor már cukorkát.
>> JASON HIRSCHHORN: Igen.
Nos, van tök.
Menjünk az első.
Megvan sütőtök.
>> Közönség: OK.
Tök visszatér nulla.
Szóval tedd ezt.
Vagy valóban, akkor tedd A láncolt lista.
>> JASON HIRSCHHORN: Hogyan tedd a láncolt lista?
>> Közönség: Ó, az aktuális szintaxis?
>> JASON HIRSCHHORN: Csak sétáljon -
többet mondani.
Mit csináljunk?
>> Közönség: Csak be úgy, mint az első csomóponthoz vezet.
>> JASON HIRSCHHORN: OK.
Tehát a node, sütőtök.
És most hogyan helyezze?
>> Közönség: Ön hozzá ez a mutató.
>> JASON HIRSCHHORN: Melyik mutató?
>> Közönség: A mutató nulla.
>> JASON HIRSCHHORN: Hol nem ezen a ponton?
>> Közönség: NULL most.
>> JASON HIRSCHHORN: Nos, ez mutat null.
De én üzembe sütőtök.
Szóval, hol kell mutatni?
>> Közönség: A sütőtök.
>> JASON HIRSCHHORN: A sütőtök.
Pontosan.
Tehát ez arra utal, hogy tök.
És honnan származik ez a mutató sütőtök pont?
Az
>> Közönség: Null.
>> JASON HIRSCHHORN: NULL.
Pontosan.
Szóval csak be valamit a láncolt lista.
Mi csak azt írta ezt a kódot erre.
Szinte majdnem megvan teljesen repedt.
Most be cukorkát.
A cukorkát is nullára.
Szóval, mit csináljunk cukorka?
>> Közönség: Ez attól függ, hogy Nem akarunk rendezni azt.
>> JASON HIRSCHHORN: Ez pontosan így van.
Ez attól függ-e vagy sem próbáljuk rendezni azt.
Tegyük fel, hogy nem vagyunk fogja rendezni azt.
>> Közönség: Hát akkor, ahogy megbeszéltük előtt, ez a legegyszerűbb, csak tedd
rögtön az elején, így a mutató A nulla pontot a cukorkát.
>> JASON HIRSCHHORN: OK.
Várj.
Hadd létre cukorkát itt.
Tehát ez a mutató -
>> Közönség: Igen, most lehet mutatva cukorkát.
Akkor a mutatót candy pont sütőtök.
>> JASON HIRSCHHORN: Tetszik ez?
És azt mondom, van egy másik dolog, hogy térkép nulla?
>> Közönség: Nos, csak nem ugyanaz a dolog?
>> JASON HIRSCHHORN: Nem ugyanaz a dolog.
Tehát ebben az esetben, ha nem akarja tartani sorrendje is
hangzik meglehetősen egyszerű.
Vesszük a mutatót az Index által a hash függvény.
Meg kell, hogy pont az új csomópontot.
És akkor bármi is mutatott korábban -
ebben az esetben nulla, a második esetben sütőtök -
hogy bármilyen ez mutat korábban, hozzáadjuk a legközelebbi
az új csomópontot.
Mi behelyezése valamit az elején.
Valójában ez sokkal egyszerűbb, mint próbálják tartani a rendezett lista.
De ismétlem, a keresés lesz bonyolultabb itt.
Majd mindig megy a végére.
>> OK.
Minden kérdést külön láncolást?
Hogyan működik?
Kérdezze meg őket.
Nagyon szeretnénk, hogy győződjön meg arról, hogy az összes érti ezt, mielőtt távozik.
>> Közönség: Miért teszed sütőtök és cukorka az azonos
része a hash tábla?
>> JASON HIRSCHHORN: Jó kérdés.
Miért őket ugyanabban a része a hash tábla?
Nos, ebben az esetben a hash függvény visszatér nulla mindkettőjüknek.
Így kell menni az Index-nulla mert ott fogunk
keresni őket, ha valaha is meg akarom nézni őket.
Ismét, lineáris megközelítéssel tapintási akkor nem őket mind nulla.
De az egyedi lánc megközelítést, fogjuk őket mind nulla
majd hozzon létre egy listát le nullára.
>> És mi nem akarjuk felülírni sütőtök egyszerűen, mert aztán
Feltételezem, hogy tök volt soha be.
Ha csak egy dolog tartja a helyen, hogy rossz lenne.
Akkor nem lenne esélye, hogy mi valaha -
ha valaha is volt egy példányban, akkor akkor csak törli a kezdeti érték.
Szóval ezért tesszük ezt a megközelítést.
Vagy ezért választottuk - de a lényeg, hogy választotta külön láncolás megközelítés
amely sok más megközelítés lehetett választani.
Van, hogy a kérdésére?
>> OK.
Carlos.
Lineáris szondázás járna -
Ha találtunk egy ütközés nulla, akkor nézne a következő helyszínen, hogy ha
nyitva volt, és tedd oda.
És akkor nézzük a következő sport-és nézd meg, hogy nyitva volt, és tedd oda.
Így megtalálja a következő szabad a nyílt helyszínen, és tedd oda.
Van még kérdés?
Ja, Avi.
>> Közönség: A nyomon követése, hogy, hogy a mit értesz azon, hogy a következő helyszínen?
A hash tábla vagy egy láncolt lista.
>> JASON HIRSCHHORN: A lineáris programozás, nem kapcsolt listák.
A következő helyszínen a hash tábla.
>> Közönség: OK.
Így a hash tábla lenne inicializálni, hogy a méret -
mint a több húrok hogy te behelyezése?
>> JASON HIRSCHHORN: Azt akarom, hogy igazán nagy.
Igen.
Itt van egy kép, amit csak felhívta a táblán.
Ismét van egy ütközés itt.
152.
És látni fogod, amit létre A láncolt lista le róla.
Ismét a hash tábla külön láncolást megközelítés nem az, amit
kell, hogy a problémák beállított hat, de az egyik, hogy egy csomó
diákok inkább, hogy.
Szóval a figyelmét, hogy beszéljünk röviden mielőtt útnak indulunk, a probléma a hat,
aztán majd megosztani egy történetet veled.
Van három percet.
>> Probléma meg hat.
Van négy funkció -
terhelés, ellenőrizze, méret és kirak.
Load -
Nos, mi már megy túlterhelés most.
Felhívtuk a terhelést a fedélzeten.
És mi is kezdett kódolási sok behelyezése egy láncolt lista.
Tehát terhelés nem sokkal több, mint mi most voltunk csinál.
>> Check, ha van valami betöltve.
Ez ugyanaz a folyamat, mint ez.
Ugyanez első két része, ahol dobja valamit a hash függvény
és kap az értékét.
De most mi nem behelyezni.
Most már keresi.
Én minta kódot írt találni valamit egy láncolt lista.
Azt javasoljuk, hogy a gyakorlatban ezt.
De ösztönösen találni valami nagyon hasonlít behelyezése valamit.
Sőt, lerajzolta találni valamit egy láncolt lista, mozgó
keresztül, amíg van a végén.
És ha van, hogy a végén, és nem tudott találja meg, akkor nincs ott.
Szóval ez az ellenőrzés lényegében.
>> Tovább a méret.
Hagyjuk méretét.
Végül meg kell kipakolni.
Unload az egyik még nem készült a fedélzeten vagy a kódolt még.
De azt javasoljuk, hogy próbálja kódolás is A mintánkban láncolt lista példa.
De kirak ösztönösen hasonló ingyenes -
vagy én értem hasonló ellenőrizni.
Kivéve most már minden egyes alkalommal, amikor mész keresztül, akkor nem bejelöli a
hogy ha az érték is.
De te figyelembe, hogy a csomópont és a felszabadítva azt lényegében.
Ez az, amit kirak kér, hogy nem.
Ingyenes mindent, amit malloced.
Szóval megy keresztül, a teljes lista ismét megy át az egész hash
tábla újra.
Ez alkalommal nem ellenőrzi hogy mi van ott.
Csak szabad, mi van ott.
>> És végül méretét.
Méret végre kell hajtani.
Ha nem hajtják végre méret -
Azt mondom, mint ez.
Ha nem hajtják végre mérete pontosan egy sor kódot, beleértve a
vissza nyilatkozatot, akkor a Ennek mérete nem megfelelő.
Ügyeljen arra, méretét, a teljes tervezési pontokat, csinálod pontosan egy
kódsor, beleértve a a return.
>> És ne pakol még Akchar.
Eager Beaver.
Azt akartam mondani, köszönöm srácok a következő fejezetben.
Van egy Happy Halloween.
Ez a ruha.
Fogom viselni ezt csütörtök ha találkozunk munkaidőben.
Ha kíváncsi vagy még több háttér, hogy ezt a jelmezt, érezni
szabad, hogy nézd meg 2011 rész a történet, hogy miért vagyok
visel a sütőtök ruha.
És ez egy szomorú történet.
Ügyeljen arra, hogy van bizonyos szövetek a közelben.
De, hogy, ha bármilyen kérdés maradok
külső szakasz után.
Sok szerencsét a probléma meg hat.
És mint mindig, ha bármilyen kérdése, tudassa velem.