[Powered by Google Translate] [6. §] [kényelmes]
[Rob Bowden] [Harvard Egyetem]
[Ez a CS50.] [CS50.TV]
>> Mi lehet a fejét, hogy mi részén kérdésekre.
Elküldtem az URL-címet a tér előtt.
Az elején a szakasz a kérdések mondja
nyilvánvalóan nem vagyok teljesen unsick-egy nagyon egyszerű kérdés
hogy csak mi Valgrind?
Mit jelent valgrind csinálni?
Bárki, aki azt akarom mondani, hogy mi valgrind csinál?
[Student] Ellenőrzések memóriavesztés.
Ja, Valgrind általános memória ellenőrző.
Azt, hogy a végén, azt mondja, ha bármilyen memóriavesztés,
ami leginkább mi vagyunk használja azt, mert ha azt szeretnénk, hogy
Jól szerepelnek a probléma beállított vagy ha azt szeretné,
kap a nagy fórumon, meg kell, hogy nincs memóriavesztés egyáltalán,
és abban az esetben van egy memóriavesztés, amit nem talál,
is szem előtt tartani, hogy ha megnyit egy fájlt
és ha nem zárja be, ez egy memóriavesztés.
>> Egy csomó ember keres egy csomópont, hogy ők nem szabadít
ha tényleg, nem zárja le a szótárban a legelső lépés.
Azt is megmondja, ha bármilyen helytelen olvas vagy ír,
ami azt jelenti, ha megpróbálod, és állítsa be egy értéket
ez túl vége a halom, és nem történik seg hiba
de valgrind elkapja, ahogyan akkor valójában nem írni ott,
és így biztosan nem kell semmilyen e sem.
Hogyan kell használni Valgrind?
>> Ez egy általános kérdés
fajta futtatni, és nézd meg a kimeneten.
A kimenet elsöprő sokszor.
Van még szórakoztató hibát, ahol ha van valami borzasztóan rossz dolog
történik a hurok, akkor előbb-utóbb azt mondják: "Túl sok hibát.
Fogom megállítani számlálás most. "
Ez alapvetően szöveges kimenetet, hogy meg kell értelmezni.
A végén, azt fogja mondani, hogy minden memóriavesztés, hogy van,
hány blokkok, amelyek hasznosak lehetnek, mivel
ha ez egy blokk unfreed, akkor ez általában könnyebb megtalálni
mint 1.000 blokkok unfreed.
1.000 blokkok unfreed valószínűleg azt jelenti, hogy nem szabadít
a kapcsolt listák megfelelően, vagy ilyesmi.
Ez Valgrind.
>> Most már a részén kérdések
ahol nem kell letölteni.
Akkor kattintson a nevem, és húzza őket a térben.
Most kattints rám.
Felülvizsgálat 1 lesz a stack, amit csinálunk 1..
Revision 2 lesz várólista, és a Revision 3 lesz az egyszeresen láncolt lista.
Kezdve le a stack.
Ahogy azt itt, vagy egymástól az egyik alapvető,
alapvető adatstruktúrák a számítógép-tudomány.
A nagyon prototipikus példa
a verem tálcák az étkezőben.
Ez alapvetően, amikor vezetnek be a verem,
valaki fogja mondani, hogy "Ó, mint egy halom tálcák."
Te verem a tálcákat fel.
Aztán ha megy, hogy húzza a tálcát,
az első tálcát, ami egyre húzta az utolsó, amit hozott a köteget.
A kémény is,-mint azt mondja, itt van-
megvan a szegmens a memória az úgynevezett stack.
És miért hívják a stack?
>> Mert, mint egy halom adatszerkezetet,
tolja és durran stack frame a stack,
ahol stack keretek olyan, mint egy különleges hívást egy függvény.
És mint egy halom, akkor mindig vissza kell térnie
Egy függvényhívás előtt juthatsz le a kisebb stack frame újra.
Nem lehet fontosabb hívást foo hívás bár és bár visszatérés a fő közvetlenül.
Ez mindig van, hogy kövesse a helyes stack toló és popping.
A két művelet, mint mondtam, a push és pop.
Ezek egyetemes értelemben.
Tudnia kell, hogy push és pop szempontjából zsetonnal nem számít, mit.
Meglátjuk sorok fajta különböző.
Ez nem igazán egyetemes kifejezést, de push és pop egyetemes a stack.
Push csak tedd a verem.
Pop vedd le a stack.
És azt látjuk, itt már a typedef struct stack,
így már char ** szálakat.
Ne félek semmilyen **.
Ez lesz a végén, hogy egy sor húrok
vagy egy tömb mutatókat karakterek, ahol
mutatókat karakterek általában vonósok.
Nem kell, hogy vonósok, de itt, ők lesznek vonósok.
>> Van egy sor húrok.
Van egy méret, ami az, hogy hány elem jelenleg a stack,
és akkor megvan a kapacitása, ami hány elem lehet a verem.
A kapacitás kell kezdeni, ki, mint valami nagyobb, mint 1,
de a mérete fog indulni, mint 0-ra.
Nos, van alapvetően három különböző módon lehet gondolni egy verem.
Nos, valószínűleg több, de a két fő módja van
akkor végre használatával egy tömb, vagy pedig végrehajtja segítségével láncolt lista.
Csatolt listák ilyen triviális, hogy a stack-től.
Ez nagyon egyszerű, hogy egy köteg használatával linkelt listákat,
így itt, mi megy, hogy egy verem segítségével tömbök,
majd a tömbök, van még két módon lehet gondolni.
Előtt, amikor azt mondtam, hogy van egy kapacitás stack,
így elfér egy elemet a verem.
>> Az egyetlen módja, hogy megtörténhet az, amint elérte a 10 elemet, akkor kész.
Lehet, hogy tudja, hogy van egy felső határa 10 dolog, amit a világban
hogy soha nem lesz több, mint 10 dolgot a stack,
ebben az esetben is van egy felső korlát a mérete a verem.
Vagy lehet, hogy a stack kell korlátos,
de ha csinálsz egy tömböt, ami azt jelenti, hogy minden egyes alkalommal, amikor elérte a 10 elemet,
akkor most kell majd növekedni és 20 elemeket, és ha bejön 20 elemet,
fogsz, hogy növekszik a tömb 30-elemek vagy 40 elemeket.
Fogsz hogy növelni kell a kapacitást, ami mit fogunk csinálni itt.
Minden egyes alkalommal, amikor eléri a maximális méretét a verem,
amikor nyomja valami mást, megyünk, hogy növelni kell a kapacitást.
Itt már toló nyilvánított bool push (char * str).
Char * str a húr, hogy mi nyomja a verembe,
és bool csak azt mondja, hogy sikerült vagy nem sikerült.
>> Hogyan sikerül?
Mi az az egyetlen körülmény, hogy tudsz gondolni
ahol kellene visszatérni hamis?
Igen.
[Student] Ha ez teljes mértékben és mi egy korlátos végrehajtását.
Igen, hogyan határozza meg, azt válaszolta,
ha ez a teljes és mi egy korlátos végrehajtását.
Akkor biztosan visszatér hamis.
Amint elérte a 10 dolog, a tömbben, akkor nem fér 11, úgyhogy vissza hamis.
Mi van, ha ez korlátlan? Igen.
Ha nem tudja bővíteni a tömböt valamilyen okból.
Igen, a memória korlátozott erőforrás,
és végül, ha folyamatosan nyomja a dolgokat a verembe újra és újra,
fogunk próbálni, és lefoglalni egy nagyobb tömböt, hogy illeszkedjen
A nagyobb kapacitású, és a malloc vagy bármilyen általunk használt megy vissza hamis.
Nos, malloc visszatér null.
>> Ne feledje, hogy minden egyes alkalommal, amikor valaha hívja malloc, akkor ellenőrzik, hogy ha ez
visszatér null vagy mást, ami a korrektség levonás.
Mivel azt szeretnénk, hogy egy kötetlen verem,
az egyetlen eset fogunk visszatér hamis, ha megpróbáljuk
kapacitásának növelése és a malloc vagy bármi visszatér hamis.
Aztán pop nincsenek argumentumai,
és visszaadja a karakterlánc van a tetején a verem.
Bármi is volt, legutóbb tolta a veremben, ami pop visszatér,
és ez is eltávolítja a veremből.
És észre, hogy visszatér null, ha nincs a veremben.
Ez mindig lehetséges, hogy a verem üres.
A Java, ha használják, hogy vagy más nyelven,
próbálja pop egy üres verem okozhat kivételt, vagy ilyesmi.
>> De C, null egyfajta tétel az esetek hogyan kezeljük ezeket a problémákat.
Visszatérő null, hogyan fogjuk jelzi, hogy a verem üres volt.
Már feltéve kódot, amely próbára stack funkcionalitását,
végre push és pop.
Ez nem lesz egy csomó kódot.
Úgy lesz, valójában, mielőtt csinálni, tipp, tipp-
ha még nem látta, malloc nem ez az egyetlen funkciója
hogy osztja memóriát a heap az Ön számára.
Van egy család alloc funkciók.
Az első a malloc, amelyen éppen használt.
Aztán ott van calloc, amely nem ugyanaz, mint a malloc,
de ez nullára mindent az Ön számára.
Ha valaha is akartam állítani mindent null után mallocing valamit
akkor éppen használt calloc az első helyen írása helyett
a for ciklus nullára ki az egész blokk memória.
>> Realloc olyan, mint a malloc, és van egy csomó különleges esetekben,
de alapvetően mi realloc csinál,
tart a mutató, már korábban is osztottak.
Realloc a funkció azt szeretné, hogy figyel ide.
Beletelik egy mutatót, amely már visszatért malloc.
Tegyük fel, hogy kér malloc egy mutató a 10 bájt.
Aztán később rájössz akart 20 bájt,
így realloc e mutatót 20 bájt,
és realloc automatikusan átmásolja mindent az Ön számára.
Ha csak hívott malloc megint, mint van egy blokk 10 byte.
Most kell egy blokk 20 byte,
szóval ha malloc 20 bájt, akkor azt kell kézzel másolja át a 10 byte az első dolog, amit
a második dolog, majd szabad az első dolog.
Realloc fogja kezelni, hogy az Ön számára.
>> Figyeljük meg az aláírás lesz void *
ami csak visszatér a mutatót a blokk memória,
akkor void * ptr.
Azt hiszem void *, mint egy általános mutató.
Általában soha nem foglalkozik void *
de a malloc visszatér a void *, aztán ez csak használni, mint
ez valóban lesz egy char *.
Az előző void *, hogy már malloc által visszaadott
most lesz átadni realloc, majd méret
az új bájtok számát szeretnénk lefoglalni, így az új kapacitást.
Adok egy pár percig, és tegye azt a helyet.
Kezdje Felülvizsgálat 1.
Abbahagyom, miután remélhetőleg arról elég időt végre push,
majd adok egy kis szünetet tenni pop.
De ez tényleg nem olyan sok kódot egyáltalán.
A legtöbb kód talán a terjeszkedő cucc, bővül a kapacitás.
Oké, nincs nyomás teljesen meg kell tenni,
de amíg úgy érzed, te vagy a helyes út, ez jó.
>> Van valakinek bármilyen kódot ők jól érzik magukat velem húzza fel?
Igen, lesz, de nem akárki volna semmilyen kódot tudom felhúzni?
Oké, akkor indul, mentse el, bármi legyen is az?
Mindig elfelejtem, hogy a lépést.
Oké, nézett push,
szeretnéd magyarázni a kódot?
[Tanuló] Először is, én emelkedett a méretet.
Azt hiszem, talán kellett volna, hogy az-amúgy, én nagyobb a méret,
és látom, ha ez kevesebb, mint a kapacitás.
És ha ez kevesebb, mint a kapacitás, hozzáteszem, hogy a tömb, hogy már van.
És ha ez nem, szorozza meg a kapacitás 2,
és én átcsoportosítja a húrok tömb valami egy nagyobb kapacitású mérete most.
És ha ez nem sikerül, elmondom a felhasználó és a return false,
és ha ez rendben van, akkor tettem a húr az új helyszínen.
>> [Rob B.] is észre, hogy használt egy szép bitenkénti operátor itt
sokszorozza 2-vel.
Ne feledje, a bal Shift mindig lesz szorozva 2.
Jobb váltás osztva 2, amíg eszébe jut, hogy ez azt jelenti,
osszuk el 2 mint egy egész osztva 2.
Lehet, hogy csonkolni a 1 itt vagy ott.
De a műszakváltás által hagyott 1 mindig lesz szorozva 2,
ha túlcsordulás határait az egész, és akkor nem lesz.
Mellékes megjegyzés.
Szeretem csinálni, ez nem fogja megváltoztatni a kódolás semmilyen módon,
de én szeretnék csinálni valami ilyesmi.
Valójában megy, hogy egy kicsit hosszabb.
Lehet, hogy nem ez a tökéletes eset mutatja ezt,
de szeretem részes be ezeket a blokkokat of-
oké, ha ez ha bekövetkezik, akkor fogok csinálni valamit,
és akkor a függvény történik.
Azt nem kell majd görgessen a szemem egészen a funkció
hogy mi történik a mást.
Ez, ha ez, ha bekövetkezik, akkor csak vissza.
Azt is a szép előnye mindent ezen túl
most tolódott marad egyszer.
Azt már nem kell, ha valaha is közel nevetségesen hosszú sorokat,
akkor ezek a 4 byte segítségével, valamint a még hátra valami,
A kevésbé túlterheltek magad, ha tetszik, oké, meg kell emlékezni
Én jelenleg egy while ciklus belsejében egy más belsejében egy for ciklus.
Bárhol meg tudod csinálni ezt vissza azonnal, valahogy, mint a.
Ez teljesen opcionális, és nem várható semmilyen módon.
>> [Student] Szükség van a méret - a hibamentes állapotban van?
Az elutasítási feltétel itt nem sikerült realloc, szóval igen.
Figyeljük meg, hogy a fail állapotban, feltehetően
hacsak nem ingyen cucc később, mi mindig lesz sikertelen
nem számít, hányszor próbáljuk nyomni valamit.
Ha folyamatosan nyomva, tartjuk növelésének méret,
bár nem vagyunk helyezzen semmit a verembe.
Általában nem növeljük a méret-ig
miután sikeresen helyezze a köteget.
Szeretnénk csinálni, mondjuk, akár itt és itt.
Aztán ahelyett, hogy s.size ≤ kapacitást, ez kevesebb, mint kapacitás,
Csak azért, mert költözött, ahol minden volt.
>> És ne feledd, az egyetlen hely, hogy esetleg vissza false
van, ahol a realloc vissza null,
és ha történetesen emlékezni standard hiba,
talán érdemes megfontolni ezt az esetet, ha a nyomtatni kívánt standard hiba,
így fprintf stderr helyett csak közvetlen nyomtatás a szabványos ki.
Ismét, ez nem az az elvárás, de ha ez egy hiba,
írja printf, akkor érdemes tenni nyomtatni standard hiba helyett a szabványos ki.
>> Bárki, aki mást megjegyezni? Igen.
[Student] Tud megy át a [hallható]?
[Rob B.] Igen, a tényleges binariness belőle, vagy csak, mi ez?
[Student] Szóval szorozza meg 2?
[Rob B.] Igen, alapvetően.
A bináris föld, mi mindig a sor számjegy.
Shifting ezt a bal 1-alapvetően betétekkel itt a jobb oldalon.
Vissza az ezt, csak emlékezve arra, hogy mindent, ami bináris
egy 2 hatványa, így ez képezi a 2 a 0,
ez a 2 a 1, ez a 2 a 2.
Helyez a 0 a jobb oldalon most már csak műszak mindent át.
Mi használt mennyiség: 2 a 0 jelentése most 2 a 1, értéke 2, a 2.
A jobb oldalon, hogy ki
szükségszerűen lesz 0,
ami teljesen érthető.
Ha valaha megszorozzuk a szám 2, akkor nem fog a végén furcsa,
így a 2-a 0 helyre legyen 0,
és ez az, amit én 1/2 figyelmeztetett, mielőtt az, ha nem történik váltani
túl a bitek száma egy egész szám,
akkor ez 1 lesz a végén megy ki.
Ez az egyetlen gond, ha történetesen foglalkozik igazán nagy kapacitással.
De ezen a ponton, akkor dolgunk egy sor milliárd dolgok
ami nem fér a memóriába egyébként.
>> Most már lehet kapni a pop, ami még egyszerűbb.
Lehet csinálni, mint ha történetesen, hogy a pop egy csomó,
és most fél kapacitással újra.
Lehet realloc csökken a memória van,
de nem kell aggódni, hogy így csak a realloc ügy lesz
növekvő memória, nem zsugorodó memória,
ami megy, hogy pop szuper könnyű.
Most sorokat, melyek lesznek, mint a halom,
de a sorrend, hogy vegye a dolgokat megfordul.
A prototipikus példa a sorban egy vonal,
így azt hiszem, ha volt angolul, azt mondtam volna
a prototipikus példája a sorban van egy sorban.
Tehát, mint egy vonal, ha te vagy az első ember a sorban,
azt várod, hogy legyen az első, aki kilóg a sorból.
Ha te vagy az utolsó ember a sorban, akkor lesz az utolsó, aki szervizbe.
Úgy hívják, hogy a FIFO motívum, míg a verem LIFO volt a minta.
Ezek a szavak nagyon univerzális.
>> Mint stack és ellentétben tömbök, sorok általában nem engednek hozzáférést elemeket a közepén.
Itt egy halom, már push és pop.
Itt történik, hogy felhívtam őket sorba állítása és dequeue.
Én is hallottam őket nevezik shift és unshift.
Hallottam, azt mondják, push és pop is vonatkoznak sorok.
Hallottam be, távolítsa el,
így push és pop, ha beszélsz stack, akkor nyomja és popping.
Ha beszélsz sorokat, akkor vedd a szavakat használni kívánt
behelyezhető és eltávolítása, és nincs egyetértés, hogy mit kell hívni.
De itt, van sorba állítása és dequeue.
Most, a struct néz ki majdnem teljesen azonos a verem struct.
De meg kell nyomon követni a fejét.
Azt hiszem, azt mondja itt, de miért van szükségünk a feje?
A prototípusok alapvetően megegyezik a push és pop.
Azt hiszem, hogy ez egy push és pop.
Az egyetlen különbség, pop visszatér-helyett az utolsó, ez vissza az első.
2, 1, 3, 4, vagy valami.
És itt van a kezdet.
A várólista teljesen tele van, ezért van négy elem benne.
A végén a várólista jelenleg 2,
és most megy be valami mást.
>> Ha szeretnénk beszúrni, hogy valami mást, amit tettünk a verem változat
A kiterjesztettük blokk memória.
Mi a baj ezzel?
[Student] Ön mozgatni a 2.
Azt mondta, mielőtt a vége a sorba,
ennek nincs értelme, hogy kezdjük 1,
akkor szeretnénk dequeue 1, akkor dequeue 3, majd dequeue 4,
akkor dequeue 2, akkor dequeue ezt.
Mi ezért nem használhatja realloc most,
vagy legalábbis, akkor kell használni realloc más módon.
De valószínűleg nem csak használja realloc.
Meg kell majd manuálisan másolja át a memória.
>> Két funkció másolni memória.
Van memcopy és memmove.
Én jelenleg olvasni a man oldalakat, hogy melyiket fogjuk használni kíván.
Oké, memcopy, a különbség
hogy memcopy és memmove egyik kezeli az ügyet helyesen
hová másolni egy régió történik átfedés a régió
te másolást.
Memcopy nem kezelni. Memmove teszi.
Azt hiszem a probléma-
mondjuk akarok másolni ezt a fickót,
E négy ezzel a fickóval vége.
A végén, amit a tömb kell kinéznie
után a másolat 2, 1, 2, 1, 3, 4, és majd pár dolgot a végén.
De ez függ a sorrend, amelyben ténylegesen másolni,
hiszen ha nem veszik figyelembe azt a tényt, hogy a régió vagyunk másolás figyelembe
átfedések az egyik vagyunk másoláshoz,
akkor lehet csinálni, mint a kezdetén van, másolja a 2 arra a helyre akarunk menni,
majd mozgassa a mutatót előre.
>> Most mi lesz itt és itt, és most szeretnénk másolni
ez a srác felett ez a fickó, és mozgassa a mutatót előre.
Mit fogunk a végén kapok 2, 1, 2, 1, 2, 1
helyett a megfelelő 2, 1, 2, 1, 3, 4 mivel
2, 1 nyíltságot felülírhatják az eredeti 3, 4.
Memmove kezeli, hogy helyesen.
Ebben az esetben, alapvetően csak mindig memmove
mert kezeli megfelelően.
Ez általában nem végez rosszabb.
Az alapötlet az, helyett kezdetétől és másolás így
mint mi most itt volt, akkor indul a végéig, és másolja be,
és ebben az esetben, akkor soha nem jelentett gondot.
Ehhez nincs teljesítmény elveszett.
Mindig memmove. Soha ne aggódj memcopy.
És ez az, ahol fogsz kell külön memmove
a becsomagolt-around részét a sorban.
Ne aggódj, ha nem teljesen kész.
Ez sokkal nehezebb, mint a verem, push és pop.
>> Bárki bármilyen kódot, tudna dolgozni?
Még ha teljesen hiányos?
[Student] Igen, ez teljesen hiányos, mégis.
Teljesen hiányos rendben van, amíg mi, tudod menteni a felülvizsgálat?
Azt felejtsük el, hogy minden egyes alkalommal.
Oké, figyelmen kívül hagyva, hogy mi történik, amikor meg kell átméretezni a dolgokat.
Teljesen figyelmen kívül átméretezés.
Magyarázd ezt a kódot.
Én ellenőrzése először is, ha a mérete kisebb, mint a másolat először is
majd azt követően, hogy én be-veszek head + méret,
és én meg arról, hogy körbe a kapacitás a tömb,
és úgy helyezze be az új húr az adott helyzetben.
Aztán méretének növelése és vissza igaz.
>> [Rob B.] Ez minden bizonnyal az egyik az esetben, ha fogsz szeretné, hogy a mod.
Bármilyen esetben, ha Ön védőcsomagolás körül, ha úgy gondolja, védőcsomagolás körül,
A közvetlen gondolat legyen mod.
Egy gyors optimalizálás / teheti kódját egy sor rövidebb,
azt észleli, hogy a vonal után azonnal ezt
mindössze méret + +, így egyesíteni, hogy bele ezt a sort, méret + +.
Most itt, mi a helyzet
ahol nincs elég memória,
így növekszik a kapacitás 2-vel.
Azt hiszem, akkor is ugyanaz a probléma itt, de tudjuk figyelmen kívül hagyni, hogy most,
ahol, ha nem sikerült növelni a kapacitást,
akkor fogsz szeretné csökkenteni a kapacitást a 2 újra.
További rövid megjegyzés, mint amit tehetünk, + =,
akkor is csinálni << =.
Szinte bármit lehet menni előtt egyenlő, + =, | =, & =, << =.
Char * új, az új blokk memória.
Oh, itt vagyok.
>> Mit gondolnak az emberek arról, hogy milyen új blokk memória?
[Student] Meg kell char **.
Gondolkodás vissza a struct itt,
húrok, amit mi újraelosztása.
Teszünk egy teljesen új dinamikus tárolás elemek a sorban.
Amit mi leszel hozzárendelése a húrok, amit mi mallocing most,
és így az új lesz a char **.
Ez lesz egy sor húrok.
Akkor mi a helyzet áll fenn, amelyek alapján fogunk visszatérni hamis?
[Student] kéne csinál a char *?
[Rob B.] Igen, jó hívást.
[Student] Mi volt ez?
[Rob B.] akartunk csinálni mérete char *, mert mi már nem-
ez valóban egy nagyon nagy probléma, mert sizeof (char) lenne 1.
Sizeof char * lesz 4,
így sok idő, amikor dolgunk ints,
Hajlamos megússza, mert mérete int és mérete int *
egy 32-bites rendszer lesz ugyanaz a dolog.
De itt, sizeof (char) és a sizeof (char *) most lesz ugyanaz a dolog.
>> Mi az a körülmény, ha visszatérünk hamis?
[Student] Új null.
Igen, ha az új null, visszatérünk hamis,
és megyek, hogy dobja le a továb-
[Student] [hallható]
[Rob B.] Igen, ez rendben van.
Lehet akár 2-szer csinálni befogadóképessége, illetve váltás 1 és akkor is csak állítsa le itt, vagy bármi.
Fogjuk csinálni, mint mi volt ez.
Kapacitás >> = 1.
És te soha nem kell majd aggódnia, hogy elvesznek az 1 helye
mert elmentél tolódott 1, így a 1-es hely szükségképpen 0,
így jobb változó 1, te még mindig rendben lesz.
[Student] Van, amit tennie kell, hogy mielőtt a visszatérés?
[Rob B.] Igen, ez teszi semmi értelme.
>> Most tegyük fogunk a végén visszatér igaz a végére.
Ahogy megyünk ezek memmoves,
kell, hogy legyen óvatos, hogy hogyan tesszük őket.
Van valakinek bármilyen javaslata, hogyan csináljunk velük?
Itt a start.
Elkerülhetetlen, szeretnénk kezdeni az elején újra
és másolat dolgokat onnan, 1, 3, 4, 2.
Hogy csinálod ezt?
Először is, meg kell nézni a man oldalt memmove újra.
Memmove, hogy az érvek mindig fontos.
Azt szeretnénk, hogy cél az első, forrás második, méret harmadik.
Van egy csomó funkciók fordított forrás és a cél.
Cél, forrás általában lenniük valamelyest.
Mozgás, mi ez vissza?
Ez visszaad egy pointert a hely, bármilyen okból érdemes ezt.
Tudok képet olvasni, de azt szeretnénk, hogy beköltözik a célpontja.
>> Mi a cél lesz?
[Student] Új.
[Rob B.] Igen, és hol vagyunk másol?
Az első dolog, amit másol ez az 1, 3, 4.
Mi az e-1, 3, 4.
Mi a címe ennek a 1?
Mi a címe az 1?
[Student] [hallható]
[Rob B.] Fej + a címe az első elemet.
Hogyan jutunk az első elem a tömbben?
[Student] Sor.
[Rob B.] Igen, q.strings.
Ne feledje, hogy itt, a mi fej 1 lehet.
Darn meg. Azt hiszem, hogy ez varázslatos-
Itt a fejünket 1 lehet. Fogom megváltoztatni a színét is.
És itt a szálakat.
Ez akkor sem írni, mint mi ide
fejjel + q.strings.
Egy csomó ember is írni és q.strings [head].
Ez nem igazán kevésbé hatékony.
Azt hihetnénk, hogy rá, mint te dereferencing azt, majd egyre címét,
de a fordító fog lefordítani a mi azelőtt amúgy q.strings + fej.
Akárhogy is szeretnénk gondolni rá.
>> És hány bájtot akarunk másolni?
[Student] Kapacitás - fejét.
Kapacitás - fej.
És akkor is mindig írja ki egy példát
hogy kitaláljuk, ha ez igaz.
[Student] Meg kell osztani 2, akkor.
Igen, azt hiszem, jól jönne méretét.
Még mindig van, hogy méret-
az SW, van méret szerint: 4.
A mérete 4. Fejünk 1 lehet.
Szeretnénk másolni a 3 elem.
Ez a józanság ellenőrizze, hogy a méret - Egymás helyesen 3.
És jön ide vissza, mint azt korábban említettük,
ha használt kapacitás, akkor volna, hogy osszuk el 2
mert mi már nőtt a kapacitás, így ahelyett, fogunk használni méretét.
Ez a másolatok részét.
Most kell másolni a többi része, a része maradt a kezdet.
>> Ez lesz memmove bele milyen pozícióban?
[Student] molett - fejét.
Igen, így már másolható méret - head bájt,
és így, ahol szeretnénk másolni a fennmaradó byte az új
majd mérete mínusz-nos, a byte-ok száma, amit már másolt be
És akkor hol vagyunk másol?
[Student] Q.strings [0].
[Rob B.] Igen, q.strings.
Tudtuk Vagy csináld & q.strings [0].
Ez lényegesen kevésbé gyakori, mint ezt.
Ha ez csak lesz 0, akkor majd inkább látni q.strings.
Ez az, ahol vagyunk másol.
Hány bytes tudjuk maradt másolni? >> [Student] 10.
Rendben.
[Student] Muszáj szorozni 5-10-szer a méret a byte, vagy valami?
Igen, ez az, ahol, mit fogunk másolást?
[Student] [hallható]
Milyen típusú a dolog, mi a másolást?
[Student] [hallható]
Ja, így a char * s, hogy mi másolás, nem tudjuk, ha e érkezik.
Hát, ha ők mutat, mint a húrok, a végén nyomja rá a sor
vagy enqueuing rá a sor.
Amennyiben ezek jönnek, akkor fogalmam sincs.
Csak meg kell nyomon követni a char * s magukat.
Nem akarunk másolni Méret - fej bájt.
Azt akarjuk, hogy másolni méret - Egymás char * s,
így fogunk szorozni ezt sizeof (char *).
Ugyanaz itt lent, egymás * sizeof (char *).
>> [Student] Mi [hallható]?
Ez a jog itt?
[Student] Nem, alatt, hogy a méret - fejét.
[Rob B.] Ez itt?
Mutató aritmetika.
Hogyan mutató számtani fog dolgozni az
automatikusan megszorozza a méret a típus, hogy mi dolgunk.
Csakúgy, mint ide, új + (méret - fej)
pontosan egyenértékű és új [size - fej]
amíg azt várjuk, hogy megfelelően működjön,
hiszen ha dolgunk egy int tömböt, akkor mi nem index int-
vagy ha ez a méret az 5 és szeretné, hogy a 4. elemet, majd index a
int array [4].
Te ne-[4] * mérete int.
Hogy kezeli automatikusan, és ebben az esetben
szó szerint azonos, így a konzol szintaxis
csak megy át kell alakítani az e amint összeállításához.
Ez valami, amit kell, hogy legyen óvatos, hogy a
ha hozzá méret - head
felveszi, nem egy bájt.
Te hozzáadását char *, mely lehet egy bájt vagy bármi.
>> Egyéb kérdés?
Oké, dequeue lesz könnyebb.
Adok egy percet végrehajtani.
Ja, és azt hiszem, ez ugyanaz a helyzet, amikor
amit a sorba állítása esetben, ha mi enqueuing null,
talán akarjuk kezelni, talán nem.
Mi nem fog még egyszer itt, hanem ugyanaz, mint a stack ügyben.
Ha sorba állításához null, akkor lehet, hogy figyelmen kívül hagyja azt.
Bárki, aki egy kódot tudok felhúzni?
[Student] Én csak azt dequeue.
Version 2, hogy a-rendben.
Akarsz megmagyarázni?
[Student] Először is, győződjön meg arról, hogy van valami a sorban
és hogy a méret lement 1-gyel.
Meg kell csinálni, és akkor vissza a fejét
majd mozgassa a fejét 1.
Oké, szóval van egy sarok esetben figyelembe kell vennünk. Igen.
[Student] Ha a fej az utolsó elem,
akkor nem akar fejet mutatni kívül a tömbben.
>> Igen, amint feje eléri a végén a tömb,
amikor dequeue, fejünk kell modded vissza 0-ra.
Sajnos, nem tudjuk, hogy az egy lépésben.
Azt hiszem, ahogy én valószínűleg erősít meg
ez lesz a char *, amit mi vissza,
amit a változó neve akar lenni.
Aztán szeretnénk mod head által kapacitás
majd vissza ret.
Egy csomó ember van itt tehetnének-
Ebben az esetben a-you'll látni az emberek csinálni, ha fej
nagyobb kapacitás, do fej - kapacitás.
És ez csak a munka körül mi mod.
Fej-mod = kapacitás sokkal tisztább
A csomagolás körül, mint ha a feje nagyobb kapacitás fej - kapacitás.
>> Kérdései vannak?
Oké, az utolsó dolog, mi maradt a mi linkelt lista.
Lehet használni néhány a láncolt lista viselkedést, ha nem
kapcsolt listák a hash táblák, ha nem egy hash táblát.
Azt javasoljuk, csinál egy hash táblát.
Lehet, hogy már megtette a Trie,
de a próbálkozás nehezebb.
Elvileg ők aszimptotikusan jobb.
De nézd meg a nagy táblára,
és megpróbálja soha nem jobb, és nem vesz fel több memóriát.
Minden, ami megpróbálja végül is rosszabb, több munka.
Ez az, amit David Malan megoldása mindig van
ő mindig álláshely a Trie megoldás, és nézzük meg, ahol éppen van.
Mi volt ő alatt, David J?
Ő # 18, úgy, hogy ez nem túl rossz,
és ez lesz az egyik legjobb megpróbálja tudsz gondolni
vagy az egyik a legjobb próbál egy Trie.
Ez még csak nem is az eredeti megoldás?
Úgy érzem, Trie megoldások általában jobban ebben a tartományban a RAM használat.
>> Menj le a csúcsra, és a RAM használat az egységes számjegy.
Menj le alja felé, és akkor látja, megpróbál
ahol kapsz teljesen masszív RAM használat,
és próbál nehezebb.
Nem teljesen megéri, de egy oktatási tapasztalat, ha nem egy.
Az utolsó dolog, a mi linkelt lista,
és ez a három dolog, halom, sorok, és a kapcsolt listák,
bármely jövőbeni dolog, amit valaha is a számítástechnikában
feltételezi, akkor ismeri ezeket a dolgokat.
Ők annyira alapvető mindent.
>> Csatolt listák, és itt már egy egyszeresen láncolt lista lesz a végrehajtás.
Mit jelent egyedül kapcsolódó jelent, szemben a kétszeresen kötött? Igen.
[Student] Csak mutat a következő mutató helyett a mutatók,
, mint például az megelőző és azt az egymás után is.
Igen, így képformátumot, mit tettem most csinálni?
Van két dolgot. Van kép és kép.
A képformátum, mi egyedül kapcsolt listák,
elkerülhetetlenül, van valamilyen mutatót a fejét a listán,
majd a listán, már csak mutató,
és talán ez rámutat arra, hogy null.
Ez lesz a tipikus rajz egy egyszeresen láncolt lista.
A kétszeresen láncolt lista, akkor menj visszafelé.
Ha adok neked bármelyik csomópont szerepel a listán, akkor feltétlenül kap
bármely egyéb csomópont a listában, ha van egy kétszeresen kapcsolt lista.
De ha neked a harmadik csomópontot a listából, és ez egy egyedül láncolt lista,
semmilyen módon nem te valaha is, hogy az első és a második csomópontok.
És ott van előnyöket és hátrányok, és egy nyilvánvaló lett
van az előírtnál több méret, és van, hogy nyomon követheti, ha ezeket a dolgokat mutat most.
De csak érdekel egyszeresen kapcsolódik.
>> Néhány dolgot fogunk végre kell hajtania.
A typedef struct csomópont, int i: struct node * next; csomópont.
Ezt a typedef kell égetni az Ön fejében.
Quiz 1 kell szeretnék adni typedef egy láncolt lista csomópont,
és képesnek kell lennie arra, hogy azonnal irkál azt le
anélkül, hogy gondolkodtam rajta.
Azt hiszem, egy pár kérdést, miért van szükségünk struct itt?
Miért nem mondjuk node *?
[Student] [hallható]
Igen.
Az egyetlen dolog, amely meghatározza a csomópont, mint egy dolog
a typedef maga.
De ezen a ponton, amikor mi vagyunk a fajta elemzés ezen keresztül struct csomóponton meghatározás
még nem fejeztük be a typedef még, igaz, mivel a typedef még nem fejeződött be,
csomópont nem létezik.
De struct csomópont működik, és ez a csomópont itt,
ezt is nevezhetnénk mást.
Ezt nevezhetnénk n.
Ezt nevezhetnénk linkelt lista csomópont.
Ezt nevezhetnénk semmit.
De ez struct csomópontot kell az úgynevezett ugyanaz, mint a struct csomópont.
Mit hívják ezt meg is lehet itt,
és hogy is választ a második pont a kérdés
ezért-sokszor, amikor meglátja Struktúrák és typedefs a struktúrákat,
látni fogja, névtelen struktúrákat, ahol akkor csak látni typedef struct,
végrehajtása struct, szótár, vagy bármi más.
>> Miért van akkor meg kell mondani csomópont?
Miért nem lehet az egy anonim struktúra?
Ez majdnem ugyanaz a válasz.
[Student] Meg kell utalni, hogy a struct.
Igen, a struct, meg kell nézze meg a struct magát.
Ha nem ad a struct egy nevet, ha ez egy névtelen struct, akkor nem hivatkozhat rá.
És végül, de nem utolsó sorban, ezeket mind kissé egyszerű,
és ezeket segít megvalósítani, ha írsz ezt le
hogy te csinálsz valamit rosszul, ha ezek a dolgok nem értelme.
Végül, de nem utolsó sorban, miért ezt kell struct node *?
Miért nem lehet pusztán struct csomópont a következő lépés?
[Student] Pointer a következő struct.
Ez elkerülhetetlenül, amit akarunk.
Miért lehet ez soha nem lehet struct node következő?
Miért kell struct node * a következő lépés? Igen.
[Student] Ez olyan, mint egy végtelen hurok.
Igen.
[Student] lenne mind egyben.
Igen, csak gondolom, hogyan tennénk mérete, vagy ilyesmi.
Mérete a struct alapvetően + vagy - néhány minta itt vagy ott.
Ez alapvetően lesz az összege mérete dolog a struct.
Ez itt megváltoztatása nélkül semmit, a méret lesz könnyű.
Mérete struct csomópont lesz méretének i + méretű következő.
Mérete i lesz 4. Mérete mellett lesz 4.
Mérete struct csomópont lesz 8.
Ha nincs meg a *, gondolva sizeof,
akkor sizeof (i) lesz 4.
Mérete struct csomópont mellett lesz méretének i + méretű struct csomópont mellett
+ Méret i + méretű struct csomópont mellett.
Lenne egy végtelen rekurzió csomópontok.
Ez az, amiért ez a dolgok kell lennie.
>> Ismét határozottan megjegyezni, hogy a
vagy legalább megérteni, elég, hogy lehet, hogy képes legyen
Ezért át, amit meg kell kinéznie.
A dolgok fogunk akar végrehajtani.
Ha hosszú a lista-
akkor csal, és tartsa körül
globális hossz vagy valami, de nem fogunk csinálni.
Megyünk számít a hossza a listán.
Van tartalmaz annak érdekében, hogy ez alapvetően, mint a keresés,
így van egy láncolt lista az egész, hogy ha ez egész szám van a láncolt lista.
Előre betoldott megy be az a lista elején.
Append megy be a végén.
Insert_sorted fog beilleszteni a rendezve pozícióra a listán.
Insert_sorted fajta feltételezi, hogy Ön soha nem használt elé vagy mögé rossz módon.
>> Insert_sorted amikor végrehajtási insert_sorted-
mondjuk már a láncolt lista.
Ez az, ami úgy néz ki, mint jelenleg, 2, 4, 5.
Szeretnék beszúrni 3, így amíg a lista maga már rendezve,
könnyű megtalálni, ahol 3 tartozik.
Elkezdek a 2.
Oké, 3 nagyobb mint 2, ezért szeretném, hogy folyamatosan megy.
Oh, 4 túl nagy, úgyhogy tudom 3 fog menni a 2 és 4,
és én kijavítani mutatók és minden ilyesmi.
De ha mi nem feltétlenül használja insert_sorted,
mint mondjuk én hozzáfűzése 6,
aztán a linkelt listát fog válni ezt.
Most nincs értelme, így insert_sorted, akkor csak feltételezik,
hogy a sorrend, bár műveletek léteznek
ami okozhat, hogy nem lehet válogatni, és ennyi.
Keressen egy hasznos betét hát ezek a legfontosabb dolgok, amit kell majd végrehajtani.
>> Most, hogy egy percet csinálni hosszúságú és tartalmazza,
és azokat kell viszonylag gyorsan.
Közeledik záróra, így bárki, van valami, hossz, illetve tartalmaz?
Ők lesznek majdnem azonos.
[Student] Hossz.
Lássuk, felülvizsgálatára.
Oké.
Akarsz megmagyarázni?
[Student] Most hozzon létre egy mutatót csomópont és inicializálni azt az első, ami a mi globális változó,
és akkor nézze meg, ha ez nulla, így nem kap egy seg hiba és vissza 0, ha ez a helyzet.
Egyébként, én áthidalás, hogy nyomon követhetőek legyenek a integer
hányszor voltam elérhető a következő eleme a lista
és ugyanabban a növekmény művelet is elérheti, hogy az aktuális elem,
és aztán folyamatosan, hogy a csekket, hogy ha ez null,
és ha ez nulla, akkor megszakítja és csak visszaadja az elemek száma, amit elérni.
>> [Rob B.] Van valakinek észrevételek valamit?
Ez jól néz ki helyességét bölcs.
[Student] Nem hiszem, hogy szükségünk van a node == null.
Igen, ha a csomópont == null return 0.
De ha node == null akkor ez-oh, van egy korrektség kérdése.
Ez csak te vissza én, de ez nem a körét most.
Csak azt kell int i, tehát i = 0.
De ha a csomópont null, akkor én még mindig lesz 0,
és megyünk vissza 0, ezért ebben az esetben azonos.
Egy másik gyakori dolog, hogy a nyilatkozat
A csomópont belsejében a hurok.
Mondhatjuk-oh, nem.
Maradjon is, mint ez.
Én valószínűleg fel int i = 0 itt,
majd node * node = először itt.
És ez valószínűleg how-szerzés eltűnjön ez a most.
Ez valószínűleg hogyan írt volna meg.
Te is, néztem, mint ez.
Ez a hurok struktúra itt
kell szinte természetes, hogy Ön, mint az int i = 0
i kisebb mint hossza tömb i + +.
Ha ez hogyan iterációkhoz egy tömb, ez hogyan iterációkhoz csatolt listát.
>> Ez legyen második természet egy bizonyos ponton.
Ezt szem előtt tartva, ez lesz szinte ugyanaz a dolog.
Fogsz szeretne navigálhat egy láncolt lista.
Ha a csomópont, fogalmam sincs, hogy mi az érték hívják.
Node i.
Ha az érték az adott node = i return true, és ennyi.
Figyelje meg, hogy az egyetlen módja annak, amit valaha return false
, ha már navigálhat az egész láncolt lista, és soha nem tér vissza igaz,
annak érdekében, hogy az, amit ez csinál.
Mint Mellékesen jegyzem meg, hogy valószínűleg nem fog hozzáfűzni vagy hozzáfűzése.
>> Quick utolsó megjegyzés.
Ha látod a statikus kulcsszó, tehát mondjuk static int count = 0,
akkor mi count + +, akkor alapvetően úgy gondolja, hogy ez egy globális változót,
bár én most mondta, hogy ez nem így fogjuk végrehajtani hosszát.
Én ezt itt, majd a count + +.
Bármilyen módon tudjuk meg egy csomópont a mi linkelt lista mi növelésével a gróf.
A lényeg ez az, amit a statikus kulcsszót jelent.
Ha most volt int count = 0 lenne a rendszeres éves globális változót.
Mi static int count azt jelenti, hogy ez egy globális változót ezt a fájlt.
Lehetetlen, hogy egy másik fájl,
tetszik gondolni Pset 5, ha már elindult.
Van két speller.c, és van dictionary.c,
, és ha csak egy dolog nyilvánítja globális, akkor bármit speller.c
lehet hozzáférni dictionary.c és fordítva.
A globális változók elérhetőek bármilyen. C fájlt,
de statikus változók csak elérhető a fájl maga,
így belseje spell checker belül vagy dictionary.c,
ez a fajta mennyire szeretném kijelentem a változó a mérete az én tömb
vagy a méret a számom szavak a szótárban.
Mivel én nem akarok nyilatkozni egy globális változó, hogy bárki hozzáfér,
Én tényleg csak érdekel, hogy a saját célra.
>> A jó dolog is ez a teljes név ütközés cucc.
Ha néhány egyéb fájl megpróbál globális változó nevű gróf dolgok nagyon, nagyon rossz,
így ez a szépen tartja a dolgokat széffel, és csak úgy érheti el,
, és senki más nem tud, és ha valaki kijelenti, egy globális változó nevű gróf,
akkor nem zavarja a statikus változó nevű gróf.
Ez az, amit statikus van. Ez a fájl globális változót.
>> Kérdések a valamit?
All set. Szia.
[CS50.TV]