[Powered by Google Translate] [6. hét, folytatás]
[David J. Malan] [Harvard Egyetem]
[Ez a CS50.] [CS50.TV]
Ez a CS50 és ez a hét végén 6.
Szóval CS50x, az egyik Harvard első tanfolyamok bevont EDX kezdeményezés
Valóban debütált az elmúlt hétfőn.
Ha azt szeretné, hogy egy pillantást, amit mások az interneten
most következő együtt, akkor irány x.cs50.net.
Ez majd átirányítja a megfelelő hely edx.org,
ami volt, ahol ezt és egyéb tanfolyamok az MIT és a Berkeley él.
Neked kell regisztrálj egy fiókot, akkor rájössz, hogy az anyag nagyrészt ugyanaz
ahogy már volt ebben a félévben, de néhány héttel késik, mert kapunk mindent készen.
De mi a diákok CS50x most lát, az egy interfész egészen olyan, mint ez.
Ez például, Zamyla vezető walkthrough a probléma set 0.
Amikor bejelentkezik edx.org, a CS50x diák látja a dolgot
elvárható, hogy egy tanfolyam: az előadás Hétfő,
előadás, szerda különböző rövidnadrág, a probléma készletek, a walkthroughs, PDF formátumban.
Ráadásul, mivel itt látsz, gépi fordítás
Az angol nyelvű átirata a kínai, japán, spanyol, olasz,
és egy csomó más nyelveken, hogy minden bizonnyal nem tökéletes
ahogy gördül őket algoritmikusan használ valami úgynevezett API,
vagy alkalmazás programozási felület, a Google-tól
, amely lehetővé teszi számunkra, hogy megtérít angol e más nyelveken.
De hála a csodálatos szellemét néhány száz-plus önkéntesek,
random emberek az interneten, akik kedvesen felajánlotta, hogy vegyenek részt
ebben a projektben, akkor fokozatosan minőségének javítása e fordítások
azáltal, hogy az emberek javítani a hibákat, hogy a számítógépek tettek.
>> Így kiderül, mi volt még néhány diák jelenik meg hétfőn, mint azt eredetileg várták.
Sőt, most már CS50x 100.000 ember követően végig otthon.
Így kiderül, mind része ennek alakuló osztály, hogy ezt az utat a számítástechnikában
oktatás általában szélesebb körben hozzáférhető.
És a valóság most, néhány ilyen masszív online kurzusok,
mindannyian kezdeni ezekkel a nagyon nagy számokat, hiszen úgy tűnik, hogy volna itt.
De a cél, végül pedig az CS50x igazán, hogy minél több ember bevonása a célvonalon, mint lehetséges.
By design, CS50x fog felajánlani a múlt hétfő
végig április 15, 2013, hogy emberek, akik iskolai kötelezettségek mailt,
munka, család, egyéb konfliktusok és hasonlók, egy kicsit több rugalmasságot
amellyel merülni ebbe a tanfolyam, amely elegendő annyit mondani,
meglehetősen ambiciózus történik, ha csak folyamán mindössze három hónap alatt szokásos félévben.
De ezek a diákok is ugyanaz a probléma kezelése készletek, megtekintők ugyanaz a tartalom,
hozzáféréssel rendelkező azonos rövidnadrág és a hasonlók.
Így rájönnek, hogy mindannyian valóban az e együtt.
És az egyik végét céljainak CS50x nem csak azért, hogy a sok ember
a célvonalon, és adjon nekik ez újdonsült megértése számítástechnika
és programozási hanem azokat ezt közös élményt.
Az egyik meghatározó tulajdonsága az 50 az egyetemen, reméljük,
már ez a fajta közösségi élmény, a jobb vagy rosszabb, néha,
de mivel ezek az emberek, hogy forduljon balra és jobbra,
és irodai óra, hackathon és a valós.
Ez egy kicsit nehezebb csinálni, hogy személy emberek online,
de CS50x zárul áprilisban az első CS50 Expo,
melyik lesz egy online adaptációja a mi elképzelésünk a valós
ha ezek a diákok ezrei mind felkérik, hogy nyújtson be egy 1 - 2-perces videó,
vagy egy screencast azok végleges projekt vagy video azok hullámzó helló
és beszél a projektről és demoing azt,
ugyanúgy, mint az elődei volna itt az egyetemen, a tisztességes,
annak érdekében, hogy a félév végére, a remény, hogy egy átfogó kiállítás
A CS50x tanulók végső projektek, ugyanúgy, mint az, ami vár rád decemberben itt az egyetemen.
Tehát többet, hogy az elkövetkező hónapokban.
>> A 100.000 diák, bár, jön a szükség van egy néhány CA.
Tekintettel arra, hogy ti is lángoló a nyomvonalat ide, és figyelembe CS50
néhány héttel ez az anyag szabadon bocsátását, hogy az emberek, az EDX,
észre, mi lenne szeretni bevonni minél több saját diákok lehetséges ezt a kezdeményezést,
mind a félév során, valamint az ezen a télen, és a jövő tavasszal.
Tehát, ha szeretnének részt CS50x,
különösen csatlakozott részt CS50x Fórum, az EDX változata CS50 Fórum,
amelyet sokan közületek korábban már használta az egyetemen, az online hirdetőtábla,
tegye fejét, hogy az URL-t, tudassa velünk, hogy ki vagy,
mert szeretnék felépíteni egy csapatot a hallgatók és oktatók és a tanárok egyaránt
az egyetemen, akik egyszerűen csak játszani végig, és segítettem.
És ha látják a kérdést, ami ismerős számukra,
hallasz egy diák jelentéstételi néhány hiba valahol néhány országban az interneten,
és hogy a gyűrűk egy harang, mert túl volt, hogy ugyanabban a kérdésben
a d-terem néhány évvel ezelőtt, remélhetőleg akkor hangjelzés, és ossza meg saját tapasztalatai.
Ezért kérjük, ne vegyen, ha szeretné.
>> Számítástechnika tanfolyamok Harvard egy kicsit a hagyomány,
CS50 köztük annak, egyes ruházati cikkek, néhány ruhát, amit viselni büszkén
A félév végén, mondván, elég büszkén, hogy befejezte CS50
és elvette CS50 és hasonlók, és igyekszünk bevonni a diákok
ebben a folyamatban, amennyire csak lehetségesek, ahol meghívjuk,
ez idő tájt a félév, a hallgatók, hogy nyújtson be terveket
a Photoshop, vagy bármi más eszköz a választás szeretné használni
ha a tervező, hogy nyújtson be formatervezési pólók és pulóverek
és napernyőkkel és kis tarka selyemkendők kutyák most van, és hasonlók.
És minden ezután - a nyertesek minden évben, majd kiállításra
A kurzus honlapján store.cs50.net.
Minden eladott Olcsó ott, de a honlapon csak saját magát működteti
és lehetővé teszi, hogy válassza ki a színek és minták, hogy tetszik.
Szóval azt hittük, csak megosztani a tavalyi tervek
voltak a honlapon kívül ez itt, ami egy éves hagyomány.
"Minden nap vagyok Seg Faultn" egyike volt a beadványok tavaly
amely még mindig rendelkezésre áll ott öregdiák.
Mi volt ez, "CS50, alapították 1989-ben."
Az egyik Bowdens, Rob, nagyon népszerű volt az elmúlt évben.
"Team Bowden" született, ez a kialakítás nyújtottak be, többek között a legjobb eladók.
Mivel ez volt itt. Sok ember volt "Bowden Fever" szerint az eladási naplókat.
Ismerd fel, hogy ami most a design ott fel az interneten.
További részletek erről a következő probléma, állítja, hogy jöjjön.
>> Még egy szerszám: már volt néhány expozíció, és remélhetőleg most
Néhány gyakorlati tapasztalatok GDB,
ami, természetesen, a hibakereső és lehetővé teszi, hogy manipulálják
a program egy viszonylag alacsony szintről, mit csinál dolgokat?
Mit jelent a GDB engedi csinálni?
Igen? Adj valamit. [Student válasz, érthetetlen]
Jó. Lépjen be funkciót, így nem csak azt írja futtatni
és a programot csapást keresztül teljes egészében kinyomtatott dolgokat szabványos kimenetre.
Inkább, akkor lehet lépni rajta soronként, akár gépelés következő
menni soronként sorra vagy lépcső belevetik magukat egy funkciót, általában az egyik, hogy írtál.
Mi mást jelent GDB engedi csinálni? Igen? [Student válasz, érthetetlen]
Nyomtatás változókat. Tehát, ha szeretné, hogy egy kis önvizsgálat belül a program
anélkül, hogy igénybe írásban printf kimutatások az egész hely,
ha csak nyomtatni egy változó, vagy megjelenik egy változó.
Mi mást lehet csinálni egy debugger, mint a GDB?
[Student válasz, érthetetlen]
Pontosan. Beállíthatjuk töréspont, akkor lehet mondani, szünet végrehajtás
a fő funkciója, vagy a foo függvényt.
Azt lehet mondani, szünet végrehajtás sorban 123.
És töréspont egy igazán erős technika
mert ha van egy általános értelemben, ahol a probléma
talán az, hogy nem kell időt vesztegetni fokozása révén a program egészét.
Akkor lényegében ugrani ott majd kezdjen gépelni -
átlépve azt lépéssel vagy mellette vagy a hasonló.
De a fogási valami hasonló GDB, hogy ez segít, az emberi,
találni a problémákra, és keresd meg a hibákat.
Ez nem feltétlenül találja őket annyira neked.
>> Így vezette be a minap style50, ami egy rövid parancssori eszköz
hogy megpróbálja stilizál a kód egy kicsit tisztábban, mint te, az ember, lehet, kész.
De ez is tényleg csak egy esztétikai dolog.
De kiderült, hogy itt van ez a másik eszköz az úgynevezett Valgrind ez egy kicsit misztikus használni.
A kimenet atrociously rejtélyes első pillantásra.
De ez csodálatosan hasznos, különösen most, hogy mi vagyunk a része, a kifejezés
hol kezded használni malloc és dinamikus memória kiosztás.
A dolgok lehet menni nagyon, nagyon rossz gyorsan.
Mert ha elfelejtette, hogy szabad a memóriát, vagy ha valamilyen dereference NULL pointer,
vagy dereference valami szemetet pointer, ami tipikusan a jelenség, hogy az eredmények?
Seg hiba. És hogy ezt a core fájl egyes hány kilobájtot vagy megabyte
amely képviseli az állam a program memóriájában, amikor lezuhant,
de a program végül seg hibák, szegmentálási hiba,
ami azt jelenti, hogy valami rossz történt, szinte mindig kapcsolódik
a memóriával kapcsolatos hibát, amit tett valahol.
Szóval Valgrind segít megtalálni az ilyesmit.
Ez egy eszköz, hogy fut, mint a GDB, miután összeállítani a programot,
hanem mint a program futtatásával közvetlenül futtatni Valgrind
, és adja át neki a program, mint te a GDB.
Most, a használat, hogy a legjobb fajta teljesítmény,
egy kicsit hosszú, így ott a képernyő tetején látni fogod Valgrind-v.
"-V" szinte az egész világon olyan bőbeszédű, ha éppen használ programok Linux számítógépen.
Tehát ez azt jelenti, kiköp több adatot, mint talán alapértelmezés szerint.
"- Szivárgás-ellenőrzés = teljes." Ez csak azt mondom csekket minden lehetséges memóriavesztés,
hibákat, hogy talán volna. Ez is egy közös paradigma Linux programokat.
Általában, ha egy parancssori argumentum, hogy ez a "kapcsoló",
hogy kéne változtatni a program viselkedését, és ez egy levél,
ez-v, de ha ez kapcsolva, csak a design a programozó,
van egy teljes szót vagy sorozat szavakkal, a parancssori argumentum kezdődik -.
Ezek csak emberi egyezményeket, de akkor látni őket egyre.
És aztán, végül "a.out" a önkényes nevet a program az adott példában.
És itt van néhány reprezentatív kimenet.
>> Mielőtt megnézzük, hogy ez mit is jelent, hadd menjen át a kódrészletet ide.
És hadd mozgatni ezt az útból, jön hamarosan,
és vessünk egy pillantást memory.c, amely e rövid példa itt.
Tehát ebben a programban, hadd nagyításához funkciók és kérdéseket.
Van egy fontos funkciója, hogy meghív egy függvényt, f,
és akkor mit jelent f folytassa csinálni, kissé műszaki angolul?
Mit f folytassa csinálni?
Mi lenne, kezdjük a 20 vezetéken, és a csillag helyét nem számít,
de én csak itt kell lenniük utolsó előadás.
Mi van a 20 vezetéken nem nekünk? A bal oldalon. Fogjuk lebontani tovább.
Int * x: mit tegyek?
Oké. Ez nyilvánító mutató, és most legyünk még inkább technikai jellegű.
Mit jelent ez, nagyon konkrétan, hogy állapítsa meg a mutató? Valaki más?
Igen? [Student válasz, érthetetlen] Túl messzire.
Szóval olvasni a jobb oldali az egyenlőségjel.
Nézzük összpontosít csak a bal oldalon, csak az int * x.
Ez nem "nyilvánítja" a mutató, de most hadd merüljön mélyebbre e meghatározás.
Mit jelent ez konkrétan, technikailag jelent? Igen?
[Student válasz, érthetetlen]
Oké. Úgy készül, hogy megmentse egy címet a memóriában.
Jó. És vegyük ezt egy lépéssel tovább, ez nyilvánító változó, x, ez 32 bites.
És tudom, hogy ez 32 bit, mert -?
Nem azért, mert ez egy int, mert ez a mutató ebben az esetben.
Véletlen egybeesés, hogy ez egy és ugyanazon egy int,
de az a tény, hogy ott van a csillag van jelent ez a mutató
és a készülék, mint sok számítógép, de nem az összes mutató 32 bit.
A több modern hardvert, mint a legújabb Mac, a legújabb PC-k, lehet, hogy 64-bites mutatók,
de a készülék, ezek a dolgok 32 bit.
Így fogjuk egységesíteni rajta. Konkrétabban, a történet a következő:
Mi "nyilvánítja" a mutató, ez mit jelent?
Készítünk tárolja a memória címet.
Mit jelent ez?
Készítünk egy változó un x, hogy vesz fel 32 bites
hogy hamarosan tárolja címét egy egész szám.
És ez valószínűleg a legpontosabb juthatunk.
Ez rendben halad előre, hogy egyszerűsítse a világ és csak annyit nyilvánítja mutató úgynevezett x.
Állapítsa meg a mutató, de a megvalósítása, és megérteni, hogy mi folyik itt valójában
még csak a néhány karakter.
>> Nos, ez már majdnem egy kicsit könnyebb, bár ez egy hosszabb kifejezés.
Szóval, mit keres ez, ez most kiemelte: "malloc (10 * sizeof (int));" Igen?
[Student válasz, érthetetlen]
Jó. És én viszem oda. Ez kiosztása egy darab memória 10 egészek.
És most hadd merüljön kissé mélyebbre, ez kiosztása egy darab memória 10 egészek.
Mi malloc akkor visszatér?
A címét darabos, vagy konkrétabban a címe az első bájt adott darab.
Hogy akkor vagyok, a programozó, hogy hol, hogy a darab végén a memória?
Tudom, hogy ez folytonos. Malloc, definíció szerint, kapsz egy folytonos darab memória.
Nem hiányosságok benne. Hozzá tud férni minden byte e darab,
háttal hátra, de hogyan tudom, hol a vége ennek a darab memória?
Amikor malloc? [Student válasz, érthetetlen] Jó.
Tényleg nem. Meg kell emlékezni.
Meg kell emlékezni, hogy én használt a 10 értéket, és nem is úgy tűnik, hogy kellett volna ide.
De a felelősség teljes mértékben rám. Strlen, amit lettél kissé függ a húrok,
működik, csak azért, mert az egyezmény annak, \ 0
vagy a speciális NULL karakter, NUL végén egy string.
Ez nem tart mindössze tetszőleges darabokat memória.
Ez rajtad múlik. Szóval a 20 vezetéken, majd lefoglal egy darab memória
, amely képes tárolni 10 egész számok, és tárolja a címét az első bájt
E darab memória a nevű változó x.
Ergo, ami a mutató. Szóval vonal 21, sajnos, hiba volt.
De először is, mit csinál? Ez mondja áruház a helyszínen 10, 0 indexelt,
A darab az úgynevezett memória x értéke 0-ra.
>> Tehát észre egy pár dolog folyik.
Annak ellenére, hogy x egy mutatót, visszahívja a pár héttel ezelőtt
hogy továbbra is használhatja a tömb stílusú szögletes zárójel jelöléssel.
Mert ez tényleg rövid oldali jelölést a több rejtélyes kinézetű mutató számtani.
ha tennénk valami ilyesmit: Fogd a cím x, mozgás 10 foltok felett,
akkor megy oda, hogy bármilyen címen tárolják az adott helyen.
De őszintén szólva, ez csak szörnyű, hogy olvassa el, és kap kényelmes.
Így a világ általában használja a szögletes zárójelek csak azért, mert sokkal több ember-barát olvasni.
De ez az, amit igazán folyik a motorháztető alatt;
x egy cím, nem egy tömb, per se.
Szóval ez tárolja a 0 helyen a 10 x.
Miért van ez rossz? Igen?
[Student válasz, érthetetlen] Pontosan.
Csak kiosztott 10 ints, de számolni 0-tól, amikor programozás C,
így hozzáférhet 0 1 2 3 4 5 6 7 8 9, de nem 10-ig.
Szóval vagy a program fog seg hibája vagy nem.
De nem igazán tudom, ez egyfajta nemdeterminisztikus viselkedés.
Ez tényleg attól függ, hogy mi szerencsénk.
Ha kiderül, hogy az operációs rendszer nem bánja, ha használni, hogy extra byte,
annak ellenére, hogy nem adott el nekem, a program esetleg nem összeomolhat.
Ez a nyers, ez hibás, de lehet, hogy nem látja, hogy tünet,
vagy lehet, hogy látni csak egyszer egy darabig.
De a valóság az, hogy a hiba, sőt, ott.
És ez nagyon problematikus, ha már írt egy programot, amely azt szeretné, hogy helyes,
hogy már eladta a programot, hogy az emberek használják, hogy hébe-hóba összeomlik
mert természetesen, ez nem jó. Sőt, ha van egy Android telefont vagy egy iPhone
és letölteni apps ezekben a napokban, ha valaha is volt egy app csak kilép,
hirtelen eltűnik, ez szinte mindig az eredménye néhány memóriával kapcsolatos kérdés,
ahol a programozó elszúrta, és másolunk egy mutató
arról, hogy nem kellett volna, és az eredmény a iOS vagy Android, hogy csak megölni a program összesen
kockázat helyett meghatározatlan viselkedést vagy valamilyen biztonsági kompromisszumot.
>> Van egy másik hiba az e program mellett ezt.
Mi mást is elcsesztem ebben a programban?
Már nem gyakorolják, azt, amit prédikált. Igen?
[Student válasz, érthetetlen] Jó.
Még nem szabadult a memóriát. Tehát a szabály most
kell, hogy legyen, amikor csak hívja malloc, fel kell hívnia ingyenes, ha végezzük, hogy a memóriát.
Most, amikor azt akarom, hogy kiszabadítsa a memória?
Valószínűleg, feltételezve, hogy ez az első sor helyes volt, azt akarom csinálni itt.
Mert nem tudtam például, tedd le ide. Miért?
Csak ki a hatálya alól. Így annak ellenére, hogy beszélünk mutatók,
ez egy héten 2 vagy 3 kérdés, ahol az x csak a hatálya alá belsejében kapcsos zárójelek, ahol megadták.
Így biztosan nem lehet kiszabadítani ott. Az egyetlen esély, hogy kiszabadítsa az hozzávetőleg után sor 21.
Ez egy viszonylag egyszerű program, ez meglehetősen egyszerű, ha egyszer ilyen becsomagolt fejedben
körül, amit a program csinál, ahol a hibák voltak.
És akkor is, ha nem látod az első, remélhetőleg ez egy kicsit most már nyilvánvaló,
hogy ezek a hibák elég könnyen megoldható, és könnyen sor.
De ha a program több mint 12 sor hosszú, ez 50 sor hosszú, 100 sor hosszú,
séta a kódot sorról sorra, és arra gondolt át logikusan,
lehetséges, de nem különösebben szórakoztató csinálni, folyamatosan keresi a hibákat,
és ez is nehéz csinálni, és ezért egy olyan eszköz, mint a Valgrind létezik.
Hadd menjek előre, és ezt: hadd kinyitom a terminál ablak,
és hadd ne csak fuss memóriában, mert a memória úgy tűnik, hogy rendben van.
Kezdek szerencsés. Megy, hogy a további bájt végén a tömb
nem tűnik túl problematikus.
De hadd, mégis, nem a józan ellenőrzést, ami csak annyit jelent, hogy ellenőrizze
függetlenül attól, hogy ez valójában helyes.
>> Tehát lássuk valgrind-v - szivárgás-ellenőrzés = teljes,
majd a neve a program ebben az esetben memória, nem a.out.
Szóval hadd menjen előre, és ezt. Hit Enter billentyűt.
Édes Istenem. Ez a teljesítmény, és ez az, amit utalt korábban.
De, ha megtanulják, hogy olvassa el az összes értelmetlen itt,
ennek nagy része csak a diagnosztikai kimenet, hogy ez nem olyan érdekes.
Mi a szeme igazán akar keresni bármilyen említése hiba vagy érvénytelen.
Szavak, amelyek azt sugallják problémákat.
És valóban, lássuk, mi baj idelent.
Nekem van egy összefoglalót valamiféle "használatban lévő kijáratnál: 40 bytes in 1 blokkokat."
Nem vagyok biztos benne, mi a blokk még, de 40 bájt
tényleg olyan, mintha tudtam kitalálni, hogy hol ez jön.
40 bájt. Miért 40 bájt használatban kijárat?
És még pontosabban, ha lapozzunk lefelé ide,
miért Én határozottan vereség a 40 bájt? Igen?
[Student válasz, érthetetlen] Perfect. Igen, pontosan.
Volt tíz egész számok, és minden egyes ilyen a méret 4, vagy 32 bit,
így elvesztettem pontosan 40 bájt, mert, ahogy javasolta, én még nem hívott szabad.
Ez egy hiba, és most nézzük meg egy kicsit tovább, és lásd a következő e,
"Érvénytelen levelet a 4-es méretű." Most mi ez?
Ez a cím van kifejezve mit bázis jelölés, látszólag?
Ez hexadecimális, és minden alkalommal, amikor megjelenik egy számot kezdődő 0x,
ez azt jelenti, hexadecimális, amit csináltunk utat vissza, azt hiszem, Pset 0 szekció kérdések,
ami csak csinál egy warmup gyakorlat átalakítása tizedes hex bináris és így tovább.
Hexadecimális, csak emberi konvenció, általában arra használják, hogy képviselje mutatók
vagy még általánosabban foglalkozik. Ez csak egy egyezmény,
mert ez egy kicsit könnyebb olvasni, ez egy kicsit kompaktabb, mint valami hasonlót decimális,
és bináris használhatatlan a legtöbb ember használja.
Tehát most mit jelent ez? Nos, úgy néz ki, van egy érvénytelen write
A 4-es méretű on line 21 A memory.c.
Akkor térjünk vissza a vonal 21, és valóban, itt van, hogy érvénytelen írás.
Tehát Valgrind nem fog teljesen fogd meg a kezem, és mondd el, mi a javítás,
de azt érzékeli, hogy csinálok egy érvénytelen write.
Én megható 4 byte, amit nem kellene, és nyilvánvalóan azért, mert,
ahogy rámutatott, csinálok [10] helyett [9] maximálisan
vagy a [0] vagy valami a kettő között.
A Valgrind, észre bármikor te most írásban a program
használó mutatók és használ memóriát, és malloc még pontosabban,
határozottan bejutni a szokása, futás a hosszú
de nagyon könnyen a vágólapra másolni parancs Valgrind
hogy ha van valami hiba van.
És ez lesz nyomasztó minden alkalommal megjelenik a kimenet,
de csak feldolgozni révén vizuálisan az összes kimenetet, és ha látod megemlíti hibák
vagy figyelmeztetéseket vagy érvénytelen vagy elveszett.
Bármely szó, hogy a hang, mint te elcseszted valahol.
Szóval észre, hogy ez egy új eszköz a toolkit.
>> Most hétfőn, volt egy csomó emberek jönnek ide
és képviseli fogalma a láncolt lista.
És mi vezetett a csatolt lista megoldást, hogy milyen probléma?
Igen? [Student válasz, érthetetlen] Jó.
Tömbök nem lehet memóriát szerepel.
Ha osztja egy sor 10-es méret, ez minden, amit kap.
Hívhatja egy függvény, mint realloc ha eredetileg hívott malloc,
és hogy próbálja, hogy növekszik a tömb, ha van hely a vége felé, hogy
hogy senki más nem használja, és ha ott nem, akkor csak meg egy nagyobb darab valahol máshol.
De akkor azt fogja másolni az összes e bájt az új tömb.
Ez úgy hangzik, mint egy nagyon helyes megoldást.
Miért van ez vonzó?
Úgy értem, hogy működik, az emberek már megoldotta ezt a problémát.
Miért kell megoldani, hogy hétfőn a kapcsolt listák? Igen?
[Student válasz, érthetetlen] Ez lehet hosszú időt vesz igénybe.
Tény, hogy minden alkalommal, amikor hívsz malloc vagy realloc vagy calloc, ami még egy másik,
minden alkalommal, amikor a program, beszél az operációs rendszer,
Ön inkább lassítani a programot le.
És ha csinálsz efféle dolgok hurkok, te tényleg lassul dolgokat.
Nem fogod észrevenni ezt a legegyszerűbb "hello world" típusú programok,
de sokkal nagyobb programok, kérve az operációs rendszer újra és újra a memória
vagy arra, hogy újra és újra inkább, hogy nem egy jó dolog.
Plusz, ez csak egyfajta intellektuális - ez egy teljes időpocsékolás.
Miért fordítsanak több és több memóriát, kockázati másolás mindent az új tömb,
ha van egy másik, amely lehetővé teszi kiosztani csak annyi memóriát valóban szükséged?
Szóval van pluses és minuses itt.
Az egyik pluses most, hogy van dinamizmus.
Nem számít, ha a darabokat memória az, hogy szabad,
Én csak egyfajta létrehozni ezeket a zsemlemorzsa keresztül mutatók
hogy string az egész láncolt lista együtt.
De fizetni legalább egy árat.
>> Mit kell feladni árán kapcsolt listák?
Igen? [Student válasz, érthetetlen] Jó.
Szükséged van több memóriát igényel. Most kell helyet ezen mutatók,
és abban az esetben ennek a szuper egyszerű láncolt lista
hogy csak próbál tárolni egészek, amelyek 4 bájt, tartjuk mondván:
is, a mutató 4 byte, így most már szó szerint megduplázódott
A memória van szükségem, csak tárolni ezt a listát.
De ismétlem, ez egy állandó kompromisszum számítástechnika
közötti idő és a tér és fejlesztés, erőfeszítés és egyéb források.
Mi van a másik hátránya segítségével láncolt lista? Igen?
[Student válasz, érthetetlen]
Jó. Nem olyan könnyű hozzáférni. Mi lehet többé tőkeáttétel
hét 0 elveket, mint oszd meg és uralkodj.
És konkrétabban, bináris keresés. Mert annak ellenére, hogy mi, emberek
láthatjuk, ahol nagyjából a közepén ez a lista,
A számítógépet csak tudja, hogy ez láncolt lista indul címen hívott először.
És ez 0x123, vagy valami ilyesmi.
És az egyetlen módja a program megtalálja a középső elem
hogy valójában keresni a teljes listát.
És még akkor is, szó szerint meg kell keresni a teljes lista, mert
még akkor is, ha eléri a középső elem az alábbiak szerint mutatók,
te, a programot, fogalmam sincs, milyen hosszú ez a lista, potenciálisan,
amíg eléred a végét, és hogyan tudod programozottan
hogy te vagy a végén a láncolt lista?
Van egy speciális NULL pointer, így ismét egy ilyen egyezmény.
Ahelyett, hogy ezt a mutatót, hogy biztosan nem akarom, hogy valami szemetet érték
rámutatva a színpadon valahol, azt akarjuk, hogy kézzel le, NULL,
annak érdekében, hogy itt van ez a végállomás ezen adatszerkezet, így tudjuk, hogy hol végződik.
>> Mi van, ha azt akarjuk, hogy manipulálja ezt?
Mi volt ennek nagy része vizuálisan, és az emberek,
de mi van, ha azt akarjuk, hogy csinál egy helyezés?
Így az eredeti listában volt a 9., 17., 20., 22., 29., 34..
Mi lenne, ha akkor volna malloc hely száma 55, egy csomópont rá,
és akkor szeretné szúrni 55 a lista ahogy tettük hétfőn?
Hogyan tudjuk ezt megtenni? Nos, Anita jött, és ő lényegében elindult a listán.
Elindult az első elem, akkor a következő, a következő, a következő, a következő, a következő.
Végül nyomja meg a bal oldali egészen
és rájött, oh, ez NULL. Tehát mi pointer manipuláció kellett tenni?
Az a személy, aki a végén, a 34, szükséges a bal kezét emelte
pont a 55, 55 szükséges, a bal kar lefelé, hogy az új, NULL terminátor. Kész.
Elég könnyen be 55 egy rendezett listát.
És hogyan lehet ezt ki?
>> Hadd menjek előre, és nyissa fel néhány kódot példának.
Majd én nyit gedit, hadd nyit két fájlt először.
Az egyik list1.h, és hadd emlékeztessem, hogy ez a darab a kód
hogy használják, hogy képviselje a csomópont.
A csomópont egyaránt int hívott n, és egy mutatót nevű next hogy csak rámutat a következő dolog a listán.
Ez most egy. H fájlt. Miért?
Van ez a konvenció, és még nem vette igénybe ezt a hatalmas összeget magunkat,
de az a személy, aki írta printf és egyéb funkciók
adott, mint egy ajándék a világ összes ilyen funkciók írt nevű fájlt stdio.h.
És akkor ott van string.h, és akkor ott van map.h, és ott ezek h fájl
hogy lehet, hogy látott vagy használt futamideje alatt írta, más emberek.
Jellemzően e. H fájlok csak dolgok, mint typedefs
vagy nyilatkozatok egyéni típusú vagy nyilatkozatok állandók.
Nem valósult funkciók "megvalósítások header fájlokat.
Tedd helyett, csak a prototípusok.
Azt tegyük a dolgokat szeretné megosztani a világgal, amire szükségük van
annak érdekében, hogy lefordítanak kódokat. Szóval, csak azért, hogy ebbe a szokás,
úgy döntöttünk, hogy nem ugyanaz a dolog. Nincs sok list1.h,
de már fel valamit, ami talán érdekes lehet, hogy az emberek a világ
, akik szeretnék használni a linkelt lista végrehajtását.
Most, list1.c, nem megyek át ezt az egész dolgot
mert ez egy kicsit hosszú, ez a program, de inkább futni it real gyorsan a billentyűket.
Hadd összeállításához lista1, hadd majd futtassa lista1, és mit fog látni a
voltunk szimulált egy egyszerű kis program itt
hogy fog engedjék meg, hogy hozzá, és távolítsa el a számokat a listából.
Szóval hadd menjen előre, és írja be 3 a 3 menüopció.
Azt akarom, hogy illessze be a számot - csináljuk az első szám, ami 9,
és most mondtam a lista most már 9.
Hadd menjek előre, és csinálni egy másik beillesztés, így elütöttem 3 menüopció.
Milyen számon akarok beszúrni? 17.
Az Enter billentyűt. És én nem csak egy.
Hadd illessze be a számot 22.
Tehát a kezdetektől a láncolt lista, hogy mi volt a dia formában egy pillanattal ezelőtt.
Hogy van ez helyezés valójában történik?
Valóban, a 22-nél a jelenleg a lista végén.
Szóval a történet mondtuk színpadra hétfőn és recapped most
ténylegesen ki kell történik kódot.
Vessünk egy pillantást. Hadd lapozzunk le ezt a fájlt.
Majd elkendőz néhány funkciót,
de megyünk le, mondjuk, a betét funkciót.
>> Lássuk, hogyan megyünk behelyezésével egy új csomópont ebbe kapcsolt listát.
Hol van a listán bejelentett? Nos, lapozzunk egészen a tetején,
, és vegyük észre, hogy az én láncolt lista lényegében nyilvánították egyetlen mutató, ami kezdetben NULL.
Szóval egy globális változó van, amely általában általunk ellen prédikált
mert ez teszi a kódot egy kicsit rendetlen fenntartani,
ez a fajta lusta, általában, de ez nem lusta, és ez nem rossz, és ez nem rossz
ha a program egyetlen célja az életben, hogy szimulálja 1 linkelt listáról.
Ami pontosan az, amit csinálunk.
Tehát ahelyett, állapítsa meg ennek a fő, majd el kell telnie, hogy minden funkció
amit írtam ebben a programban, akkor inkább észre oh, nézzük csak teszi a globális
mert az egész célja a program célja, hogy bizonyítani egy és csak egy láncolt lista.
Annak érdekében, hogy úgy érzi, oké. Itt vannak a prototípusok, és nem megyünk át mindezen,
de én írtam egy törlés funkció, a talál funkció, insert funkció, és a traverse funkciót.
De nézzük most már menj vissza le a Függvény beszúrása
és látom, hogy ez itt dolgozik.
Beszúrás az on-line - itt is vagyunk.
Beszúrása. Tehát nem vállal semmilyen érvet, mert megyünk kérni
A felhasználó belsejében ezt a funkciót a számot akarnak szúrni.
De először készítünk, hogy adjon nekik egy kis teret.
Ez a fajta másolás és beillesztés a másik példa.
Ebben az esetben, mi volt kiosztásának int, ezúttal mi kiosztása egy csomópont.
Nem igazán emlékszem, hogy hány bájt a csomópont, de ez rendben van.
Sizeof tudja kitalálni nekem.
És miért vagyok ellenőrzésekor NULL sorban 120?
Mi lehet baj sorban 119? Igen?
[Student válasz, érthetetlen]
Jó. Csak lehet a helyzet, hogy én már kértem túl sok memóriát
vagy valami baj van, és az operációs rendszer nem rendelkezik elegendő bytes adni nekem,
így jelzi annyira visszaküldésével NULL, és ha nem ellenőrzi, hogy a
és én csak vakon folytassa használni a visszaadott cím, lehet NULL.
Ez lehet egy ismeretlen értéket nem egy jó dolog, ha I -
valójában nem lesz ismeretlen érték. Ez lehet NULL, úgyhogy nem akarom
visszaélésekre, és kockára dereferencing azt.
Ha ez megtörténik, én csak vissza, és mi úgy tenni, mintha nem kaptam vissza semmilyen memória egyáltalán.
>> Különben elmondom a felhasználó adjon nekem egy számot beszúrni, kérem régi barátunk getInt,
és akkor ez volt az új szintaxist vezettünk be hétfőn.
"Newptr-> n" az meghozza a címet, amit kaptak malloc
amely az első bájt az egy új csomópont objektum,
és aztán megy a mezőre hívott n.
Egy kis trivia kérdés: Ez megegyezik azzal, amit több rejtélyes kódsort?
Hogy mást írtam ezt? Szeretné, hogy a stab?
[Student válasz, érthetetlen]
Jó. A. N, de ez nem olyan egyszerű, mint ez.
Mit először meg kell tennem? [Student válasz, érthetetlen]
Jó. Meg kell tennem * newptr.n.
Szóval azt mondja, az új mutató nyilvánvalóan egy címet. Miért?
Mert azt malloc által visszaadott. A * newptr azt mondja: "menj oda"
majd ha egyszer ott van, akkor használd a jobban ismert. n,
de ez csak úgy néz ki, egy kicsit csúnya, különösen akkor, ha az ember megy
döntetlen mutató nyilakkal egész idő alatt, a világ szabványosított változata az erre a nyílra jelölést,
amely nem pontosan ugyanaz a dolog.
Szóval csak a -> jelölést, ha a dolog, a bal oldalon van egy mutató.
Ellenkező esetben, ha ez a tényleges struct, használja a. N.
És akkor ez: Miért nem tudom inicializálni newptr-> next NULL?
Nem akarjuk, hogy a lógó bal kéz le a végén a színpadon.
Azt akarom, hogy egyenesen lefelé, ami azt jelenti, a végén ez a lista
esetlegesen lehet ezen a csomóponton, úgyhogy jobb, győződjön meg róla, NULL.
És általában inicializálja a változókat, vagy az adatok tagjai és struktúrákat
valami csak jó gyakorlat.
Csak bérbeadás szemét létezik, és továbbra is fennáll általában kapja meg bajba
Ha elfelejtette, hogy tegyen valamit a későbbiekben.
>> Itt van egy pár esetben. Ez megint a betét funkció,
és az első dolog, amit ellenőrizni, ha a változó nevű első,
hogy a globális változó NULL, azt jelenti, hogy nincs kapcsolt lista.
Még nem egészül ki olyan számokat, így magától értetődő, hogy helyezze be a jelenlegi száma
a lista, mert ez csak tartozik elején a lista.
Szóval ez volt, amikor Anita csak állt fel ide egyedül, mintha
senki sem volt itt fent a színpadon, amíg kiosztott egy csomópont,
akkor tudta emelni a kezét az első alkalommal,
ha mindenki jött fel a színpadra utána hétfőn.
Most itt, ez egy kis ellenőrzés, ahol azt kell mondanom, hogy az új csomópont értéke n
a <n értéke a jelenlegi első csomópont,
azt jelenti, hogy van egy láncolt lista, ami elkezdődött.
Van legalább egy csomópontot a listán, de ez az új fickó
tartozik előtt, ezért meg kell mozgatni a dolgokat.
Más szóval, ha a lista indult és csak, mondjuk,
csak a szám 17, ez a - valójában, akkor ezt pontosabban.
Ha elkezdjük a történet egy mutató van úgynevezett első,
és kezdetben ez NULL, és illessze be a 9,
A 9-es számú egyértelműen tartozik elején a listán.
Szóval mintha mi csak malloced a címet vagy a 9 és tedd ide.
Ha az első 9 alapértelmezés szerint az első forgatókönyv beszéltünk csak azt nézzük pont ezt a fickót itt,
hagyja ezt NULL, most már a 9-es számú.
A következő számot szeretnénk beszúrni a 17.
17 tartozik ide, úgyhogy kell majd csinálni néhány logikai stepping keresztül.
Szóval ahelyett, mielőtt csinálni, mondjuk úgy, mintha azt akartuk, hogy helyezze be a 8-as szám.
>> Tehát csak a kényelem kedvéért, megyek, hogy dolgozzon itt.
De ne feledje, malloc nem tud rá leginkább sehol.
De a rajz kedvéért teszem ide.
Szóval mintha épp most kiosztott egy csomópontot a 8-as szám, ez NULL alapértelmezés szerint.
Mi most történni? Egy pár dolgot.
Mi tette ezt a hibát a színpadon hétfőn, ahol frissített egy mutató, mint ez,
akkor tette ezt, és aztán azt állította - mi elárvult mindenki más a színpadon.
Mert Nem látom - a műveletek sorrendjére itt fontos,
mert most már elvesztette ezt a 9 csomópont, amely csak egyfajta lebeg az űrben.
Szóval nem ez volt a megfelelő megközelítés hétfőn.
Először meg kell csinálni valami mást.
Az állam, a világ úgy néz ki, mint ez. Kezdetben, 8 osztottak.
Mi lenne jobb módja a behelyezése 8?
Ahelyett frissítésével mutató az első, csak frissíteni ez itt helyette.
Tehát szükségünk van egy sor kódot fog kapcsolni ezt NULL karaktert
egy tényleges pointer, ami mutat node 9,
és akkor nyugodtan változtatni először mutatni ezt a fickót itt.
Most van egy lista, a láncolt lista, a két elem.
És mit jelent ez valójában néz itt?
Ha megnézzük a kódot, észreveszi, hogy én csináltam, hogy pontosan.
Már mondtam newptr, és ez a történet, newptr mutatott meg ezt a fickót.
>> Szóval hadd dolgozzon még egy dolog, és meg kellett volna hagyni egy kicsit több hely erre.
Tehát megbocsátani apró rajzot.
Ez a fickó hívják newptr.
Ez a változó is bejelentett egy pár sort korábban, összhangban - csak a fenti 25.
És ez mutat 8. Tehát amikor azt mondom newptr-> next, azt jelenti, hogy menj a struct
ez alatt mutatott a newptr, ezért itt vagyunk, ott.
Ezután a nyíl azt mondja hogy a következő mezőt, majd az = mond fel milyen értéket ott?
Az érték volt az első, hogy mi az érték az első?
Gyártási mutatott ezen a csomóponton, így azt jelenti, hogy ennek most már mutatni ezen a csomóponton.
Más szóval, ami úgy néz ki még ha nevetséges rendetlenség az én kézírás,
Mi egy egyszerű ötlet, csak ha ezeket a nyilak körül
fordítja a kódot, csak ez az egy bélés.
Tárolja mi van az első a következő mezőt, majd frissítse 1. mi valójában.
Menjünk előre, és előre-valamilyen e,
és nézd csak ezt a farok helyezés most.
Tegyük fel, hogy jutok el a pontra, ahol azt találjuk, hogy a következő mező néhány csomópont NULL.
És ezen a ponton a történet, egy részlet, hogy én vagyok számolunk
az, hogy én már bevezetett egy másik mutatót ide sorban 142, elődje mutató.
Lényegében ezen a ponton a történet, ha a lista lesz hosszú,
Valahogy meg kell járni, hogy két ujjal mert ha túl messzire megy,
emlékszem egy hosszúságú listát, nem mehetsz vissza.
Szóval, ez a gondolat a predptr az én bal ujját, és newptr - nem newptr.
Egy másik mutató, ami itt van a másik ujját, és én csak ilyen séta a listán.
Ez az, hogy miért létezik. De nézzük csak úgy az egyik egyszerűbb esetek itt.
Ha ez a mutató a következő mezőben NULL, mi a logikai következmény?
Ha elmozdulási ezt a listát, és megüt egy NULL pointer?
Nálunk az a lista végére, és így a kódot, akkor csatolja ezt még egy további elem
A fajta az intuitív fog, hogy a csomópont, amelynek következő mutató NULL,
így ez jelenleg NULL, és változtassa meg, bár hogy a címe az új csomópontot.
Szóval, csak rajz kódot a nyíl, hogy felhívta a színpadon felemelésével valaki bal kezét.
>> És a helyzet, hogy én hullám kezem a most,
csak azért, mert úgy gondolom, hogy ez könnyű eltévedni, amikor csinálni ezt a fajta környezet,
ellenőrzi a helyezés az a lista közepén.
De csak ösztönösen, hogy minek kell történnie, ha azt szeretné, hogy kitaláljuk,
ahol néhány szám tartozik, a középső akkor kell járni, hogy
egynél több ujj, több mint egy mutató,
kitalálni, ahová tartozik az ellenőrzés az elem <a jelenlegi,
> Az aktuális, és ha úgy találja, hogy a helyet,
akkor meg kell, hogy ezt a fajta héj játék, ahol mozog a mutató körül nagyon óvatosan.
És ez a válasz, ha azt szeretné, hogy oka, ezen keresztül otthon a saját,
csapódik le, csak azért, hogy e két sornyi kódot, de a sorrend az említett vonalak szuper fontos.
Mert ha csökken valakinek a kezét, és fel valaki más a rossz érdekében,
újra, akkor a végén orphaning a listán.
Összefoglalva több fogalmi, a kurzort a farok viszonylag egyszerű.
A behelyezés fejénél is viszonylag egyszerű,
de meg kell frissíteni egy további mutató ebben az időben
szorítani 5-ös szám a lista itt
majd beillesztés a közepén jár, még nagyobb erőfeszítést,
nagyon óvatosan illessze be a számot a 20 a helyes location,
ami 17 és 22.
Tehát meg kell, hogy tegyen valamit, mint hogy az új csomópont 20 pont 22,
majd, amelyek csomópont mutató frissíteni kell utoljára?
Ez 17, ténylegesen helyezze.
Szóval megint én elhalasztja a tényleges kódot az adott végrehajtására.
>> Első pillantásra ez egy kicsit nyomasztó, de ez tényleg csak egy végtelen ciklus
ez hurok, a ciklusok, a ciklusok, a ciklusok, és a törés amint bejön a NULL pointer,
ekkor meg tudod csinálni a szükséges szerelést.
Ez tehát nem reprezentatív láncolt lista beillesztési kódot.
Ez kedves volt egy csomó, és úgy érzi, mintha már megoldotta egy probléma,
de már be egy egész másikat. Őszintén szólva, mi töltöttem ennyi idő
a nagy O és Ω és működési idő, próbálják megoldani a problémákat gyorsabban,
és itt teszünk egy nagy lépést hátra, érzés.
És mégis, ha a cél az, hogy az adatok tárolására,
úgy érzi, mint a Szent Grál, ahogy mondta hétfőn, azt valóban
tárolni dolgokat azonnal.
>> Sőt, tegyük fel, hogy megcsináltuk félretett láncolt lista egy pillanatra
és mi helyette bevezette a fogalmat egy táblázatot.
És nézzünk gondoljunk csak egy tábla egy pillanatra, mint egy tömb.
Ez a tömb, és ebben az esetben itt is mintegy 26 elemet, 0-tól 25,
és tegyük fel, hogy szükség van néhány darab a tárolási nevek:
Alice és Bob és Charlie és hasonlók.
És szükség van néhány adatszerkezet tárolja ezeket a neveket.
Hát, jól jönne valami, mint egy láncolt lista
és meg tudná járni a listát behelyezése Alice előtt, Bob és Charlie után Bob és így tovább.
És valóban, ha meg akarja nézni kódot így, mint egy félre,
tudják, hogy list2.h, mi pontosan ezt.
Mi nem megy át a kódot, de ez a változat az első példa
, amely bemutatja egy másik struct láttuk azelőtt hívott diák,
és akkor mi valójában tárolja a csatolt lista egy mutató egy diák struktúrát
inkább, mint egy egyszerű kis egész szám, n.
Tehát észre ott kód van, amely magában foglalja a tényleges húrok,
de ha a cél kéznél tényleg most, hogy foglalkozzon a hatékonysági probléma,
nem lenne jó, ha mi az adott objektum neve Alice,
akarjuk helyezni őt a megfelelő helyen egy adatszerkezet,
úgy érzi, mintha lenne igazán jó, hogy csak fel Alice,
akinek a neve kezdődik, az első helyen.
És Bob, akinek a neve kezdődik B, a második helyen.
Egy tömb, vagy kezdjük nevezni egy asztal, egy hash tábla, hogy a
meg tudjuk csinálni, hogy pontosan. Ha adott egy nevet, mint Alice,
egy string, mint Alice, hol teszed A-l-i-c-e?
Szükségünk van egy hueristic. Szükségünk van egy funkció, hogy bizonyos bemeneti mint Alice
és visszaküldi a választ: "Tedd Alice ezen a helyen."
És ez a funkció, a fekete doboz, fog nevezni egy hash függvény.
>> A hash függvény van valami, hogy vesz egy input, mint "Alice",
és visszatér hozzád, jellemzően a numerikus helyét néhány adatszerkezet, ahol Alice tartozik.
Ebben az esetben, a mi hash függvény legyen viszonylag egyszerű.
A hash függvény kell mondani, ha az adott "Alice", amely képességgel kéne érdekel?
Az első. Szóval nézd meg a [0], majd azt mondom, ha a [0] karakter A, térjen vissza a 0 szám.
Ha ez a B, vissza 1. Ha ez a C, Beküldendő: 2, és így tovább.
Összes 0 index, és ez lehetővé teszi számomra, hogy be Alice, majd Bob, majd Charlie és így tovább
ebbe adatstruktúra. De van egy kis gond.
Mi van, ha Anita jön megint?
Hová tesszük Anita? A neve is kezdődik a betű,
és úgy érzi, mint mi tettük még nagyobb rendetlenség ezt a problémát.
Most azonnal helyezés, állandó idő helyezés, egy adatstruktúra
ahelyett, legrosszabb esetre lineáris,
de mit tehetünk Anita ebben az esetben?
Mi a két lehetőség közül, tényleg? Igen?
[Student válasz, érthetetlen] Oké, szóval tudtuk, hogy egy másik dimenzióba.
Ez jó. Így tudjuk építeni a dolgokat, mint a 3D-ben beszélgettünk szóban hétfőn.
Tudtunk újabb hozzáférés van, de tegyük fel, hogy nem, próbálom tartani ezt az egyszerű.
Az egész cél itt az, hogy azonnali konstans idejű hozzáférést,
Szóval ez ha túl sokat összetettségét.
Milyen más lehetőségek, amikor megpróbálja beilleszteni Anita ebbe adatszerkezet? Igen?
[Student válasz, érthetetlen] Jó. Így tudtunk mozogni mindenki más le,
mint Charlie nudges le Bob és Alice, majd rakjuk Anita, ahol tényleg akar lenni.
>> Persze, most van egy mellékhatása ennek.
Ez az adat struktúra valószínűleg hasznos, nem azért, mert szeretné szúrni az emberek egyszer
hanem azért, mert azt szeretnénk, ha szeretné ellenőrizni, hogy ott vannak később
ha szeretnénk kinyomtatni az összes nevet az adatszerkezetet.
Fogunk valamit csinálni ezekkel az adatokkal végül.
Tehát most voltunk ilyen csavaros feletti Alice, aki már nem, hol kellene lennie.
Sem Bob, sem Charlie.
Szóval lehet, hogy ez nem is olyan jó ötlet.
De valóban, ez az egyik lehetőség. Mi lehet váltani mindenkit le,
vagy fene, Anita jött későn a játék, miért nem az imént Anita
Nem itt, nem itt, nem itt, menjünk csak fel neki egy kicsit lejjebb a listán.
De aztán ez a probléma kezd ruházni újra.
Lehet, hogy képes megtalálni Alice azonnal alapuló, az első nevét.
És Bob azonnal, és Charlie. De aztán keres Anita,
és látod, hmm, Alice van az úton.
Nos, hadd nézzem meg az alábbi Alice. Bob nem Anita.
Charlie nem Anita. Oh, van Anita.
És ha továbbra is, hogy a vonat a logika egész úton,
mi a legrosszabb futási idő a megállapítás behelyezése vagy Anita ebbe az új adatstruktúra?
Ez O (n), nem igaz?
Mivel a legrosszabb esetben, ott van Alice, Bob, Charlie. . .
egészen a valaki nevű "Y", így már csak egy hely maradt.
Szerencsére, nincs egy úgynevezett "Z", így tesszük Anita legalján.
>> Még nem igazán megoldani ezt a problémát.
Így talán nem kell bemutatni ezt a harmadik dimenzióba.
És kiderült, ha mi bevezetni a harmadik dimenziót,
nem tudjuk ezt tökéletesen, de a Szent Grál lesz, hogy egyre
állandó idő helyezés és dinamikus beszúrások, hogy a
nem kell a kemény-kód egy sor mérete 26.
Mi lehet beszúrni annyi nevet, mint szeretnénk, de nézzük mi 5-perces szünet van
majd csinálni rendesen.
Rendben van. Én meg a történetet fel elég mesterségesen ott
választásával Alice, majd Bob, majd Charlie majd Anita,
akinek a neve nyilvánvalóan fog ütközni Alice.
De a kérdés, amit én ért véget hétfőn mindössze mennyire valószínű ez
hogy Ön is kap az ilyen típusú ütközések? Más szóval,
ha elkezdjük használni ezt a táblázatos szerkezet, ami tényleg csak egy tömb,
Ebben az esetben a 26-helyek,
mi van, ha a bemenetek helyett egyenletesen oszlanak?
Ez nem mesterségesen Alice és Bob és Charlie és David és így tovább betűrendben,
ez egyenletesen eloszló A-tól Z-
>> Talán majd most, hogy szerencsés és nem fogunk, hogy a két A-vagy 2 B
nagyon nagy a valószínűsége, de valaki rámutatott,
ha ezt általánosított probléma, és nem tesz 0-25
hanem, mondjuk, a 0 és 364 vagy 65, gyakran a napok számát egy tipikus évben,
és feltette a kérdést: "Mi a valószínűsége annak, hogy mi ketten ebben a szobában van egyforma születésnapja?"
Másképp fogalmazva, mi a valószínűsége annak, hogy mi ketten egy nevet kezdődő A?
Az a fajta kérdés ugyanaz, de ez a címtartomány,
erre a keresési térben, nagyobb abban az esetben, születésnapok,
mert van olyan sok több napot ebben az évben, mint betűk az ábécé.
Mi a valószínűsége, hogy egy ütközés?
Nos, azt hiszem ezt kitalálni a matek az ellenkező irányba.
Mi a valószínűsége, hogy nincs ütközés?
Nos, ez a kifejezés itt azt mondja, hogy mi a valószínűsége
ha csak egy ember ebben a teremben, hogy van egy különleges születésnapja?
Ez 100%-os. Mert ha csak egy ember a szobában,
ő születésnapja bármelyike ​​lehet a 365 napot ki az év.
Tehát 365/365 lehetőséget ad nekem az 1 értéket.
Tehát a valószínűsége a kérdéses pillanatban mindössze 1.
De ha van egy másik személy a szobában,
mi a valószínűsége annak, hogy a születésnapját a különbség?
Már csak 364 nap lehet, figyelmen kívül hagyva a szökőév,
azok születésnapi ne ütközzenek a más személyekkel.
Szóval, 364/365. Ha egy harmadik személy bejön, igen 363/365, és így tovább.
Tehát folyamatosan szorzata együtt ezek frakciói, amelyek egyre kisebb és kisebb,
hogy kitaláljuk, mi a valószínűsége, hogy mindannyian egyedülálló születésnap?
De akkor mi is, persze, csak úgy, hogy a válasz és a flip körül
és nem 1 mínusz az összes, hogy egy kifejezés akkor végül kap
ha emlékszel a hátán a matek könyvet, úgy néz ki, egy kis valami, mint ez,
amely sokkal könnyebben értelmezhető grafikusan.
És ez a képe itt van az x tengelyen száma születésnapok,
vagy a személyek száma a születésnapokat, és az y tengely a valószínűsége, hogy a mérkőzés.
És mi ezt mondani, hogy ha, mondjuk, sőt,
hadd válasszon valami hasonlót 22, 23.
Ha van 22 vagy 23 ember van a szobában,
a valószínűsége, hogy két ilyen nagyon kevés ember megy van egyforma születésnapja
valójában szuper magas, kombinatorikusan.
50%-os esélye, hogy egy osztályban mindössze 22 fő, a szeminárium, gyakorlatilag
2-azok az emberek mennek, hogy ugyanazt a születésnapját.
Mert van sok szempontból, amelyek segítségével ugyanaz a születésnapját.
Még rosszabb, ha megnézi a jobb oldali diagram,
mire van egy osztályban 58 tanuló azt,
annak a valószínűsége, 2 fő részére, amelynek születésnap szuper, szuper magas, közel 100%-os.
Nos, ez egyfajta szórakozás tény a valós életben.
>> De a következmények, most, az adatstruktúrák és információ tárolására
azt jelenti, hogy csak feltételezve, hogy van egy szép, tiszta, egyenletes eloszlású adatok
és van egy elég nagy tömb, hogy illeszkedjen egy csomó dolgot
nem jelenti azt fogod, hogy az emberek a különleges helyszíneken.
Te megy, hogy ütközések. Tehát ez a fogalma kivonatoláshoz ahogy hívják,
figyelembe bemeneti mint "Alice" és a masszázsnak, hogy valamilyen módon
majd visszatérve a választ, mint a 0 vagy 1 vagy 2.
Megközelítés vissza néhány kimenete ez a funkció nem sújtja ez a valószínűsége ütközés.
Szóval, hogyan lehet kezelni ezeket ütközések?
Nos, az egyik esetben, akkor tegye meg a gondolat, hogy javasolták.
Mi is csak váltani mindenkit le, vagy talán egy kicsit egyszerű,
ahelyett move mindenki, menjünk csak mozgatni Anita, hogy az alján a rendelkezésre álló helyet.
Tehát, ha Alice in 0, Bob van 1, Charlie 2,
akkor csak tedd Anita a helyszínen 3.
És ez egy olyan technika adatszerkezetek nevű lineáris tapintás.
Lineáris mert te csak séta ezen a vonalon, és te valami szondázás
a rendelkezésre álló helyeket az adatszerkezetet.
Természetesen, ez hárul az O (n).
Ha az adatok szerkezete nagyon tele, van 25 ember már,
majd Anita jön, ő végül, hogy mi lenne a helye Z, és ez rendben van.
Még mindig illik, és megtalálja őt később.
>> De ez ellentétes volt a célja, hogy felgyorsítsa a dolgokat.
Szóval, mi lenne, ha helyette bevezette a harmadik dimenzióba?
Ezt a technikát általában az úgynevezett külön chaining, vagy amelynek láncok.
És mi a hash tábla most, ez a táblázatos szerkezet,
a tábla csak egy tömb mutató.
De mi a mutatókat mutasson az tudjátok mit?
A csatolt listában. Szóval, mi van, ha vesszük a legjobb mindkét világ?
Az általunk használt tömböket a kezdeti indexek
az adatszerkezet így azonnal menni [0] [1], [30] vagy így tovább,
de így, hogy van némi rugalmasságot, és mi fér Anita és Alice és Adam
és bármely más, Egy név,
akkor inkább hagyja, hogy a másik tengely nő önkényesen.
És végül, mint a hétfői, van, hogy kifejező képesség a linkelt listát.
Mi lehet a nő egy adatszerkezet önkényesen.
Alternatív tudtunk csak, hogy egy hatalmas, 2-dimenziós tömb,
de lesz egy szörnyű helyzetet, ha a sorok a 2-dimenziós tömb
nem elég nagy a további személyt, akinek neve történik kezdeni A.
Isten mentsen meg kell átcsoportosítása egy hatalmas 2-dimenziós szerkezet
csak azért, mert van olyan sok ember nevezett A,
különösen akkor, ha van olyan kevés ember nevű Z valamit.
Ez csak megy, hogy egy nagyon ritka adatszerkezet.
Szóval ez nem tökéletes bármilyen eszközzel, de most legalább megvan a képessége
hogy azonnal megtalálja, amikor Alice és Anita tartozik,
legalábbis szempontjából a függőleges tengely,
és akkor csak azt kell eldönteni, hogy hova tegye Anita vagy Alice ebben a láncolt lista.
Ha nem érdekel a válogatás dolgok milyen gyorsan tudnánk be Alice egy struktúra, mint ez?
Ez az állandó idő. Mi index a [0], és ha senki nem ott van,
Alice megy az elején, hogy a láncolt lista.
De ez nem egy nagy dolog. Mert ha Anita, akkor jön
Egyes lépések számát később, ha nem tartozik Anita?
Nos, [0]. OOP. Alice már, hogy a láncolt lista.
>> De ha nem érdekel a rendezési ezeket a neveket,
tudjuk csak mozgatni Alice felett, betét Anita, de még ez konstans idő.
Még ha van Alice és Ádám és az összes többi A nevek,
ez nem igazán azáltal, hogy fizikailag. Miért?
Mert mi csak volt itt láncolt lista, ki tudja, voltak ezek a csomópontok egyébként?
Mindössze annyit kell tennie, hogy mozog a zsemlemorzsa.
Mozgassa a nyilak körül, akkor nem kell fizikailag mozgatni bármilyen adat körül.
Így tudjuk beszúrni Anita, abban az esetben, azonnal. Constant idő.
Tehát állandó idő lookup, és állandó idő behelyezése valaki, mint Anita.
De milyen oversimplifying a világ.
Mi lenne, ha később akarjuk találni Alice?
Hány lépés az, hogy fog tartani?
[Student válasz, érthetetlen]
Pontosan. Az embereknek a száma, mielőtt Alice a láncolt lista.
Szóval ez nem egészen tökéletes, mert adatszerkezet újra, van ez a függőleges hozzáféréssel
és akkor van ilyen linkelt listák függő - valójában, ne dolgozzon ez egy tömb.
Ez ilyen láncolt listák lógott le róla, hogy néz ki egy kicsit valami ilyesmi.
De a probléma az, ha Aliz és Ádám és az összes többi A nevek
végül egyre több ott,
találni valakit a végén vesz egy csomó lépést,
bcause van, hogy áthalad a linkelt lista
amely egy lineáris művelet.
Szóval tényleg, akkor a beillesztés idő végül O (n), ahol n az elemek száma a listában.
Osztva, hadd önkényesen nevezik m, ahol m a száma kapcsolt listák
hogy van ebben a függőleges tengelyen.
Más szavakkal, ha feltételezzük, valóban egy egyenletes eloszlás a nevek,
teljesen irreális. Van nyilvánvalóan valamilyen betű, mint mások.
>> De ha feltételezzük a pillanatban egy egyenletes eloszlású,
és mi n teljes ember, és m teljes láncok
rendelkezésünkre álló, akkor a hossza egyenként ezeknek a láncoknak
meglehetősen egyszerű lesz az összes, n osztva száma láncokat.
Tehát n / m. De itt van, ahol lehet minden matematikailag okos.
m egy állandó, mert van egy fix számú ezeket.
Fogsz nyilvánítsa a tömb elején,
és nem vagyunk átméretezés a függőleges tengelyen. A dolog természetéből adódóan, ez marad rögzített.
Ez csak a vízszintes tengely, hogy úgy mondjam, ez változó.
Így technikailag, ez egy konstans. Tehát most, a beillesztési idő
nagyjából O (n).
Annak érdekében, hogy nem érzi, hogy sok minden jobb.
De mi az igazság itt? Nos, ebben az időben, a héten
mi már azt mondja O (n ²). O (n), 2 x n ², - n, osztva 2-vel. . . ECH.
Ez csak n ². De most, hogy ez a része a félév,
tudunk kezdeni beszélni a valós világban újra.
És N / m jelentése teljesen gyorsabb, mint csak egyedül n.
Ha van egy ezer nevet, és szünet őket a több vödör
úgy, hogy csak tíz neve minden ilyen láncok,
Teljesen keres 10 dolog lesz gyorsabb, mint ezer dolgot.
És így az egyik közelgő probléma készletek fog megtámadni téged
gondolni, hogy pontosan, hogy bár igen,
aszimptotikusan és matematikailag, ez még mindig csak a lineáris,
ami szar általában, amikor megpróbálja megtalálni a dolgokat.
A valóságban ez lesz gyorsabb, mint
emiatt osztó.
És így van ez megint lesz e trade-off
és ez a konfliktus az elmélet és a valóság,
és az egyik gombok indul fordulópontot ezen a ponton a félév
több a valóság az egyiket mi egyfajta felkészülés semster végén,
ahogy bemutatjuk a világ webes programozás,
ha tényleg, a teljesítmény fog számítani, mert a felhasználók fognak
kezd érezni és értékelni rossz tervezési döntéseket.
>> Szóval hogyan megy a végrehajtó linkelt - egy hash tábla, 31 elemeket?
És az előző példában volt önkényesen körülbelül születésnapok.
Ha valaki születésnapja január 1-jétől, illetve február 1-jén fogjuk őket ebben a vödörben.
Ha ez január 2. február 2., március 2, akkor tedd a vödörbe.
Ezért volt 31. Hogyan nyilvánítja a hash tábla?
Ez lehet nagyon egyszerű, node * asztal az én önkényes neve rá, [31].
Ez ad nekem 31 mutatókat csomópontok,
és amely lehetővé teszi számomra, hogy 31 mutató csatolt listák
még ha e láncok kezdetben NULL.
Mit akarok tenni, ha azt szeretné tárolni "Alice", "Bob", "Charlie"?
Nos, meg kell, hogy lezárja ezeket a dolgokat a szerkezet
mert meg kell mutatni, hogy Alice Bob, arra utalnak, hogy Charlie, és így tovább.
Nem lehet csak a neveket egyedül, így tudtam létrehozni egy új struktúra nevű csomópontot itt.
>> Mi az aktuális csomópont? Mi az a csomópont az új láncolt lista?
Az első dolog, az úgynevezett szó, az a személy nevét.
LENGTH, feltehetően összefügg a maximális hossza egy ember neve,
bármi azaz, 20, 30, 40 karakter őrült sarokban esetekben,
és +1 Az mi? Ez csak az extra NULL karaktert \ 0.
Tehát ez a csomópont csomagolópapír "valami" belsejében is,
hanem azt is kijelenti a pointer neve mellett
annak érdekében, hogy tudjuk lánc Alice Bob Charlie és így tovább.
Lehet NULL, de nem feltétlenül kell annak lennie.
Van még kérdése ezeken hash táblát? Igen?
[Student kérdezi kérdést, érthetetlen] Egy tömb - jó kérdés.
Miért van ez char szót egy tömbben nem csak char *?
Ebben a kissé önkényes példát, nem akartam, hogy kénytelenek
malloc minden egyes eredeti nevek.
Azt akartam, hogy nyilvánítsa a maximális memória a húr
úgy, hogy tudtam másolni a szerkezet Alice \ 0, és nem kell foglalkozni a malloc és free és hasonlók.
De tudtam csinálni, hogy ha akartam, hogy legyen tudatában a tér használatát. Jó kérdés.
Szóval próbáljuk általánosítani távol a
és fókuszáljon a fennmaradó mai adatszerkezetek általában
és más problémák, hogy meg tudjuk oldani ugyanazt a fundamentumok
bár az adatszerkezetek maguk is különböznek egymástól adatokat.
>> Így kiderül, a számítógép-tudomány, a fák nagyon gyakoriak.
És azt hiszem egy fa fajta, mint egy családfát,
ha van valami gyökér, néhány matriarcha vagy pátriárka,
nagymama vagy nagypapa vagy korábbi vissza,
alatt, amely anya és apa vagy különböző testvérek vagy hasonlók.
Tehát egy fa szerkezet csomópontok és azt gyermekek,
általában 0 vagy több gyermek esetében minden egyes csomóponthoz.
És néhány zsargon, amit látsz ezen a képen van
minden olyan a kis gyerekek vagy unoka a széleit
akiknek nincs nyilak származó őket,
ezek az úgynevezett levelek, és bárki be a belső
egy belső csomópont, hívhatja bármi ezekhez hasonlót.
De ez a szerkezet elég gyakori. Ez egy kicsit önkényes.
Van egy gyermek, a bal oldalon, már három gyermek a jobb oldalon,
két gyerek a bal alsó sarokban.
Tehát lehet különböző méretű fák, de ha elkezdjük, hogy egységesítsék a dolgokat,
és lehet, hogy visszahívja ezt honnan Patrick videót a bináris keresés egy korábbi rövid
online, bináris keresés nem kell végrehajtani egy sor
vagy papírdarabok a táblára.
Tegyük fel, hogy akarta, hogy tárolja a számokat kifinomultabb adatszerkezet.
Lehet létrehozni egy fát, mint ez.
Lehet, hogy egy csomópont a C-ben bejelentett, és a csomópont lehet legalább két elem belsejébe.
Az egyik a kívánt számot tárolni, a másik pedig - nos, meg kell még egy.
A másik a gyerekek.
Tehát itt van egy másik adatszerkezet. Ez alkalommal, egy csomópont a meghatározás szerint tárolására szám n
majd két mutatót, balra és jobbra gyermek gyermek.
És ők nem önkényes. Mi érdekes ezt a fát?
>> Mi van a minta, hogyan általunk meghatározott e ki, vagy hogyan Patrick fektette ki a videót?
Elég nyilvánvaló, hogy van néhány válogatás folyik itt,
de mi van az egyszerű szabály? Igen?
[Student válasz, érthetetlen]
Tökéletes. Ha ezt a pillantást, látod a kis számok a bal oldalon,
nagy számok a bal oldalon, de ez igaz minden csomópont.
Minden egyes csomópont a bal gyerek kevesebb, mint, és a jobb gyermek nagyobb, mint azt.
Mi ez most azt jelenti, ha akarom keresni az adatok struktúrája, mondjuk, a szám 44,
El kell kezdeni a gyökér, mert az összes ilyen bonyolultabb adatszerkezetek most,
már csak egy mutató, egy dolog, az elején.
És ebben az esetben, az elején a gyökér. Ez nem a bal szélen,
ez a gyökere ennek a szerkezetnek. Látom itt van 55, és én keresem 44.
Milyen irányba akarok menni?
Nos, azt akarom, hogy a bal, mert nyilvánvaló, hogy a jobb lesz túl nagy.
Tehát észre itt, te valami fogalmilag aprítás a fa fél
mert te soha nem megy le a jobb oldali.
Úgyhogy most megyek a 55 az 33. Ez túl kicsi egy szám.
Ezt keresem: 44, de most már tudom, ha 44 van ez a fa, tudok menni természetesen a jobb oldalon.
Szóval megint én vagyok metszést a fa felét.
Ez nagyjából megegyezik fogalmilag a telefonkönyv.
Ez megegyezik azzal, amit tettünk, a papírokat a táblára,
de ez egy kifinomult szerkezet, amely lehetővé teszi számunkra, hogy ténylegesen
ezt oszd meg és uralkodj a design az algoritmus,
és valóban, átkelés a struktúra, mint ez - Hoppá.
Mozgás a struktúra, mint ez, ahol ez csak "erre kell menni, vagy menjen, hogy így"
azt jelenti, hogy az összes kódot, hogy behajlítva a fejedben, amikor az első végrehajtó szakaszban
vagy séta otthon, a bináris keresés segítségével rekurzió és iteráció,
ez a fájdalom a nyak. Keresse meg a középső elemet, majd tedd a kerekítés felfelé vagy lefelé.
>> Van egy szépség, mert most már használhatja rekurzió ismét
de sokkal tisztábban. Valóban, ha a szám 55, és meg akarja találni 44,
menj maradt ebben az esetben, akkor mit csinálsz? Futtatja pontosan ugyanazt algoritmust.
Kivárunk értékét a csomópont, akkor menj balra vagy jobbra.
Ezután ellenőrizze az érték a csomópont, menj balra vagy jobbra.
Ez tökéletesen megfelel rekurziót.
Így annak ellenére, hogy a múltban tettünk néhány meglehetősen önkényes példát bevonásával rekurzió
ez nem kell rekurzív adatokat tartalmazó struktúrák,
különösen a fák, ez egy tökéletes alkalmazásának gondolatát vesz egy probléma,
csökkenő, majd megoldása az azonos típusú, de kisebb, program.
>> Szóval van egy másik adatszerkezet tudjuk bevezetni.
Ez az egyik célja, első pillantásra nézni rejtélyes, de ez elképesztő.
Tehát ez egy adatszerkezet úgynevezett Trie, Trie, amely örökölt szó visszakeresés,
amely nem ejtik re-try-val, de ez az, amit a világ hívja ezeket a dolgokat. Megpróbálja. T-r-i-e.
Ez egy fa struktúra néhány sort, de minden a csomópontok egy Trie
Úgy tűnik, hogy mi? És ez egy kicsit félrevezető, mert ez a fajta rövidített.
De úgy néz ki, minden egyes csomópontja e Trie valójában egy tömb.
És bár a szerző ezt a diagram nem bizonyította azt,
ebben az esetben, ez Trie egy adatstruktúra, melynek célja az életben tárolni szavak
, mint az A-l-i-C-E vagy B-o-b.
És ahogyan ezeket az adatokat tárolja Alice és Bob és Charlie és Anita, és így tovább
van ez használ egy tömböt amelyben tárolni Alice egy Trie,
kezdjük a gyökér csomópont, amely úgy néz ki, mint egy tömb,
és ez már írva rövidített írásmódot.
A szerző kihagyott abcdefg mert nem voltak nevek ezzel.
Ezek csak azt mutatta, M és P és T, de ebben az esetben,
menjünk el Alice és Bob és Charlie bizonyos neveket itt.
Maxwell valójában ebben a diagram.
Tehát hogyan volt a szerző bolt M-a-x-w-E-l-l?
Ő kezdte a gyökér csomópontot, és elment [M], így nagyjából 13, a 13. helyen a tömbben.
Aztán onnan, van egy mutató.
A mutató, ami egy másik tömböt.
Innen a szerző indexelt ebbe a tömb a helyszínen A., ahogyan azt ott a bal felső sarokban,
aztán ő következett, hogy egy másik mutató tömb,
és elment a mutató a következő helyen: X.
Majd a következő tömb helyszín W, E, L, L, és így tovább,
és végül, nézzük valóban megpróbál egy képet e.
Mit jelent egy csomópont néz a kódot?
A csomópont egy Trie tartalmaz egy sor mutató több csomópont.
De ez is van, hogy valamilyen logikai érték, legalábbis ennek végrehajtásában.
Én történetesen nevezni is_word. Miért?
Mert amikor behelyezésekor Maxwell, te nem beillesztése
bármit ebbe adatszerkezet.
Te nem ír M. Te nem ír X.
Minden, amit csinál a következő mutatók.
A mutató, amely képviseli M, akkor a mutató, amely egy,
akkor a mutató képviselő X, akkor W, E, L, L,
de mit kell tennie, hogy a végén van valami megy, ellenőrizze, én el ezt a helyet.
Volt egy szó, amely itt ér véget az adatszerkezet.
>> Tehát mi a Trie valóban tele van, és a szerző úgy döntött, hogy képviselje
Ezen terminuses kis háromszög.
Ez csak azt jelenti, hogy az a tény, ez a háromszög van itt, ez a boolean értéke true
azt jelenti, ha megy visszafelé a fa,
azt jelenti, hogy egy szó nevű Maxwell ebben.
De a szó foo, például,
nem a fán, mert ha elkezdem a gyökér csomópont ide a csúcson,
Nincs f mutató, nem o pointer, nem o mutató. Foo nem nevet ez a szótár.
Hanem ezzel szemben, Turing, terc-u-r-i-n-g. Ismét, nem tárolja t vagy a u vagy r vagy i vagy n vagy g.
De tettem áruház e adatszerkezet értékű igaz utat fel ide a csomópont - a fa
azáltal, hogy ezt a boolean értéke is_word igaz.
Tehát egy Trie egyfajta nagyon érdekes meta szerkezet,
ha te nem igazán tárolására maguk a szavak ilyen típusú szótárban.
Ahhoz, hogy világos, te csak tárolása igen vagy nem, van egy szó, hogy itt ér véget.
>> Most mi a hatása?
Ha van 150.000 szót a szótárban, hogy akarsz tárolni a memóriában
használatával olyasmi, mint egy láncolt lista,
megy, hogy a 150.000 csomópontok a láncolt lista.
És találni egy olyan szavak betűrendben vehetné O (n) idő.
Lineáris idő. De abban az esetben van egy Trie,
mi a működési ideje találni a szóval?
Kiderült, hogy a szépség, az, hogy akkor is, ha 149.999 szó már ez a szótár,
mivel végrehajtani ezen adatok struktúrája,
mennyi időbe telik, hogy megtalálja, vagy helyezze még egy személyt, hogy mint Alice, Alice?
Nos, ez csak 5, talán 6 lépéseket a záró karakter.
Mivel a presense egyéb nevek a szerkezet
nem lesz az olyan behelyezése Alice.
Továbbá megállapította, Alice egyszer van 150.000 szó ebben a szótárban
nem kap az utat találni Alice egyáltalán,
mert Alice. . . . . itt, mert találtam egy boolean értéket.
És ha nincs boolean true, akkor Alice nincs ebben adatstruktúrájának szavak.
Más szóval, a futási idő megtalálni a dolgokat, és helyezze a dolgok ebbe az új
adatstruktúrája Trie O of - ez nem n.
Mivel a presense a 150.000 ember nincs hatással Alice, úgy tűnik.
Így nevezzük k, ahol k a maximális hossza egy szót angolul
amely jellemzően nem több, mint 20-valami karaktert.
Így k egy konstans. Tehát a Szent Grál úgy tűnik, hogy megtalálta már
olyan, mint egy Trie, állandó időt lapkák, a keresések, a törlések.
Mivel a néhány dolog már a szerkezetben,
amelyek nem is fizikailag ott. Ismét, ők csak egyfajta ellenőrzött le, igen vagy nem,
nincs hatása a jövőbeli működési idő.
>> De van, hogy a fogást, különben nem lett volna olyan sok időt elvesztegetett
az összes többi adat struktúrákat, csak hogy végre kap a titok egyik, hogy elképesztő.
Szóval, milyen áron fizetünk elérni ezt a nagyságot itt? Space.
Ez a dolog masszív. És az ok, hogy a szerző
nem nyújtott be itt, észreveheti, hogy mindezek a dolgok úgy néz ki, mint a tömbök,
hogy nem készít a többi fa, a többi Trie,
mert ők egyszerűen nem releváns a történetet.
De mindezek csomópont rendkívül széles, és minden csomópont a fában vesz fel
26 vagy ténylegesen, lehet 27 karakter, mert ebben az esetben én szóközökkel az aposztróf
hogy mi volna apostrophized szavakat.
Ebben az esetben, ezek széles tömbök. Így még ha ők nem picutured,
ez veszi fel a hatalmas mennyiségű RAM.
Ami lehet, hogy finom, especilly a modern hardver,
de ez a kompromisszum. Kapunk kevesebb időt töltenek több helyet foglalnak.
Szóval, hol van ez az egész megy?
Nos, van - lássuk itt.
Csináljuk egy ugrás, hogy ez a fickó itt.
>> Hiszed vagy sem, olyan vicces, mint a C már egy ideje,
vagyunk elérte azt a pontot, ahol a félévben az ideje, hogy átmenet dolgokat modern.
A dolgok egy magasabb szinten. És bár a következő hetekben
akkor még továbbra is merítse magunkat a világ a mutatók és a memória kezelése
kap, hogy a kényelmet, amit aztán építeni,
a végén játék végül bevezetni, ironikusan, nem ezt a nyelvet.
Fogunk költeni, mint 10 perc alatt beszél HTML.
Minden HTML egy leíró nyelv, és mi a leíró nyelv
ezek a sorozat nyitott zárójelet és zárt zárójelek azt mondják ", hogy ez a merész"
"Hogy ez a dőlt", "teszi ezt központú."
Ez nem minden, intellektuálisan érdekes, de ez szuper hasznos.
És ez minden bizonnyal mindenütt ezekben a napokban.
De mi erős a HTML világában, és a webes programozás általában
épület dinamikus dolgokat írni kódot a nyelvek, mint a PHP vagy a Python vagy a Ruby vagy Java vagy C #.
Tényleg, amit a nyelv választás, és a termelő HTML dinamikus.
Generálása úgynevezett CSS dinamikusan.
Cascading Style Sheets, ami szintén kb esztétika.
És így még akkor is, ma, ha elmegyek néhány weboldal, mint az ismerős Google.com,
és megyek többet, fejlesztő, kilátás forrás, amely talán már azelőtt,
de azt, hogy megtekinthesse forrása, ez a cucc talán úgy néz ki elég rejtélyes.
De ez a mögöttes kód, amely megvalósítja Google.com.
Az elülső vég. És tulajdonképpen ez mind fluffy esztétika cucc.
Ez a CSS itt. Ha folyamatosan legördülő szerzünk néhány színkódolt cucc.
Ez a HTML. Google kód így néz ki a rendetlenség, de ha valóban nyitni egy másik ablak,
láthatjuk egy szerkezetet ennek.
Ha kinyitom ezt, észre itt, ez egy kicsit olvashatóbb.
Fogunk látni nemsokára ezt a címkét, [szó] egy tag,
HTML, fej, test, div, script, szöveges terület, span, középre, div.
És ez is egyfajta rejtélyes külsejű első pillantásra,
de mindez zűrzavar következik bizonyos mintákat, és ismételhető minták,
annak érdekében, hogy amint megkapjuk az alapokat le, akkor képes lesz arra, hogy kódot írni, mint ez
majd manipulálni kód használatával, mint ez még egy másik nyelvet, az úgynevezett JavaScript programot.
És a JavaScript olyan nyelv, amely fut belül a böngésző
ma, hogy használja Harvard tanfolyamok, a tanfolyam vásárlási eszköz a Google maps használ
hogy kapsz egy csomó a dinamizmus, a Facebook ad mutatni állapotfrissítéseiket,
Twitter használja fel, hogy mutassa meg tweets azonnal.
Mindez akkor kezdődik merítsük be magunkat
De oda, meg kell értenünk, egy kis valamit az interneten.
Ez a klip itt csak egy perc hosszú, és tegyük fel, most ez, sőt,
hogy az internet működik, mint egy teaser, mit szól, hogy jöjjön. Adok "Warriors of a neten."
>> [♫ Slow kórus zenei ♫]
[Férfi elbeszélő] jött egy üzenet.
A protokoll minden saját.
[♫ Gyorsabb elektronikus zene ♫]
Azért jött, hogy a világ a hűvös tűzfalak, nemtörődöm routerek,
és veszélyek sokkal rosszabb, mint a halál.
Ő gyors. Ő erős. Ő a TCP / IP, és van neki a címet.
Warriors of a neten.
[Malan] A jövő héten, akkor. Az internet. Web programozás. Ez CS50.
[CS50.TV]