[Powered by Google Translate] [Teden 6, Nadaljevanje]
[David J. Malan] [Harvard University]
[To je CS50.] [CS50.TV]
To je CS50 in to je konec 6. tednu.
Torej CS50x, eden od prvih programov Harvarda, vključenih v pobudo EDX
celo debitiral v preteklem ponedeljek.
Če bi želeli, da bi dobili vpogled, kaj drugi na internetu
Zdaj spremljate skupaj z lahko glavo, da x.cs50.net.
To vas bo preusmeril na ustrezno mesto na edx.org,
ki je bil po tem in drugih tečaje iz MIT in Berkeley zdaj živi.
Boste morali, da se prijavite za račun, boste ugotovili, da je material v veliki meri enaki
kot ste imeli ta semester, čeprav z zamudo v nekaj tednih, saj smo dobili vse pripravljeno.
Toda kaj študenti CS50x bodo zdaj videli, je vmesnik precej, kot je ta.
To, na primer, je Zamyla vodi walkthrough za postavitev problema 0.
Ob prijavi na edx.org, CS50x študent vidi marsikaj
, ki bi jih pričakujejo v času: predavanje za ponedeljek,
predavanje v sredo, različne kratke hlače, problem sprejemnikov, walkthroughs, datotek PDF.
Poleg tega, kot jih vidite tukaj, strojni prevodi
angleških transkriptov v kitajski, japonski, španski, italijanski,
in cel kup drugih jezikov, ki bo zagotovo nepopolna
kot smo jih razvaljamo načrtno uporabo nekaj, kar ti API,
ali programski vmesnik, iz Googla
ki nam omogoča, da pretvorite angleškem teh drugih jezikih.
Ampak hvala za čudovito duhu nekaj sto in nekaj prostovoljcev,
naključnih ljudi na internetu, ki so se prijazno ponudili, da se vključijo
v tem projektu, bomo postopno izboljšanje kakovosti teh prevodov
ki jih imajo ljudje popraviti napake, ki so naši računalniki naredili.
>> Tako se izkaže, da je nekaj več študentov pokažejo v ponedeljek, kot smo sprva pričakovali.
Pravzaprav, zdaj CS50x ima 100.000 ljudi po skupaj doma.
Tako ugotoviš, da so vsi del tega Uvodno razred da se ta tečaj računalništva
izobraževanja bolj na splošno, širše dostopen.
In v resnici je zdaj, z nekaterimi od teh velikih spletnih tečajev,
vsi so začeli s temi zelo visokih številk, kot se zdi, da so tukaj končali.
Vendar pa je cilj, v končni fazi, CS50x je res, da bi dobili čim več ljudi do ciljne črte, kot je mogoče.
Z zasnovo CS50x se bo ponujena od tega preteklo ponedeljek
vse tja do 15. april 2013, tako da ljudje, ki imajo šolske obveznosti drugje,
delo, družina, drugi konflikti in podobno, imajo malo več prožnosti
s katerimi se potopite v tem tečaju, ki je dovolj opozoriti na to,
je zelo ambiciozno le v primeru, če v teku samo treh mesecih med običajni semester.
Vendar pa se bodo ti študenti reševanje istega problema sklopov, si isto vsebino,
ki imajo dostop do istih hlačah in podobno.
Tako spoznamo, da smo vsi res v tem skupaj.
In eden od končnih ciljev CS50x ne samo da bi dobili čim več ljudje
do ciljne črte, in jim to na novo odkrito razumevanje računalništva
in programiranje, ampak tudi, da so jih imeli te skupne izkušnje.
Ena od pomembnih značilnosti 50 na kampusu, upamo,
je bila ta vrsta komunalne izkušenj, za boljše ali slabše, včasih,
vendar imajo ti ljudje obrnejo na levo in desno,
in uradne ure in hackathon in pošteno.
To je malo težje narediti, da osebe z ljudje na spletu,
vendar bo CS50x sklene aprila s prvim vedno CS50 Expo,
ki bo dosegljiv prilagoditev naši ideji sejma
ko bodo ti na tisoče študentov, vsi povabljeni k oddaji 1 - do 2-minutni video,
bodisi screencast njihovega zadnjega projekta ali video njimi mahal zdravo
in govori o svojem projektu in ga demoing,
podobno kot vaša predhodnika tu naredil na univerzi na sejmu,
tako da do konca semester, upanje je, da so na svetovni razstavi
iz velikih CS50x učencev končnih projektov, podobno kot je to, kar vas čaka v decembru tukaj na kampusu.
Torej, več o tem v prihodnjih mesecih.
>> S 100.000 študentov, čeprav gre za potrebo po še nekaj CA.
Glede na to, da so fantje neverjetno pot tukaj, in ob CS50
nekaj tednov pred objavo tega materiala je na ljudi, na EDX,
zavedate, da bi rad, da gre čim več naših študentov, kot je to mogoče pri tej pobudi,
tako v polletju, kot tudi to zimo, in to prihaja pomlad.
Torej, če bi želeli, da se vključijo v CS50x,
zlasti pridružil na CS50x razpravljajo je različica z EDX CS50 razpravljajo,
ki ga mnogi od vas so bili z uporabo na univerzi, online oglasna deska,
prosim, od glave do tega URL-ja, nam to sporočite, kdo ste,
zato, ker bi radi, da zgraditi ekipo študentov in osebja in Fakulteta enako
na kampusu, ki so preprosto igrajo skupaj in pomoč.
In ko bodo videli, vprašanje, ki je seznanjeni,
slišite študenta poročanja nekaj bug nekje v neki državi, na internetu,
in da so obroči zvon, ker tudi vi imeli ta isti problem
v vašem d dvorani nekaj časa nazaj, upam, da potem lahko trobili v en rog in delite svoje izkušnje.
Zato vas prosimo, da sodelujete, če bi želeli.
>> Tečaje računalništva na Harvardu imajo malo tradicije,
CS50 med njimi, da ima nekaj oblačil, nekaj oblačil, ki jih lahko nosite s ponosom
na koncu semester, ki pravijo, zelo ponosno, da končate CS50
in je CS50 in podobno, in smo vedno poskušali vključiti učence
v tem procesu, kolikor je to mogoče, pri čemer vas vabimo,
po tem času semestra študenti predložiti načrte
uporabljate Photoshop, ali karkoli orodje želite uporabljati
Če ste oblikovalec, naj predložijo načrte za majice in jopice
in dežniki in malo bandanas za pse imamo in podobno.
In vse, kar je nato - zmagovalci vsako leto, se nato razstavil
na spletni strani Seveda je pri store.cs50.net.
Vse se prodaja po ceni, toda le spletna stran se zažene
in omogoča ljudem, da izberete barve in modele, ki so jim všeč.
Pa sem mislil, da bova samo deliti nekaj modelov lanskoletnih
da so na spletni strani poleg tega je ta v tej zadevi, ki je letno tradicijo.
"Vsak dan sem SEG Faultn" je bila ena od vlog v lanskem letu,
ki je še vedno tam na voljo za diplomantom.
Imeli smo enega, "CS50, ustanovljena 1989."
Eden od naših Bowdens Rob, je bil zelo priljubljen lani.
"Ekipa Bowden" se je rodil, je bila ta oblika vpisali med najboljših prodajalcev.
Ker je bila to ena tukaj. Veliko ljudi je bilo "Bowden Fever" v skladu s prodajnimi hlodov.
Zavedaj se, da bi zdaj lahko vaš model tam gor na internetu.
Več podrobnosti o tem v naslednjem problemu določa, da pridejo.
>> Še eno orodje: ste imeli nekaj izpostavljenosti in upam, da zdaj
nekatere praktične izkušnje z gdb,
ki je, seveda, razhroščevalnik in vam omogoča, da manipulira
vaš program na razmeroma nizki ravni, gre za kakšne stvari?
Kaj GDB kaj si naredil?
Ja? Daj mi nekaj. [Student odgovor, nerazumljiv]
Dobro. Korak v funkcijo, tako da ne boste morali vnesti zagon
in imajo program udarec skozi celoti, tiskanje stvari na standardni izhod.
Namesto tega lahko stopite skozi to vrstico po vrstico, ali vnesete naslednjo
iti po vrsticah z vrvico ali stopnjo, da se potopite v funkciji, ponavadi tisti, ki si napisal.
Kaj drugega GDB kaj si naredil? Ja? [Student odgovor, nerazumljiv]
Natisni spremenljivk. Torej, če želite, da to malo introspekcijo znotraj vašega programa
ne bilo treba zateči k pisanju printf izjave po vsem mestu,
lahko samo natisniti spremenljivko ali prikazati spremenljivko.
Kaj še lahko narediš z razhroščevalnik gdb podobnega?
[Student odgovor, nerazumljiv]
Točno tako. Nastavite lahko prelomnih točk, ki jih lahko rekli prekinitvijo izvajanja
Na glavno funkcijo ali funkcije foo.
Lahko rečemo prekinitvijo izvajanja v vrstici 123.
In Prelomne točke so zelo močna tehnika
ker če imate splošno občutek, kje je vaš problem
Verjetno je, da vam ni treba izgubljati časa z poglobitvi celoti programa.
Lahko skočite v bistvu tam in začnite tipkati -
Vmesni skozi, korak ali dostavo ali podobno.
Ampak ulov z nekaj podobnega gdb je, da vam pomaga, človeški,
našli svoje težave in najti svoje napake.
Ni nujno, da je bil toliko jih za vas.
>> Tako smo uvedli drugi dan style50, ki je kratek ukazni vrstici orodje
da poskuša Stilizovati kodo malo bolj čisto kot ti, bi lahko človek, ki so ga opravili.
Ampak tudi to je res samo estetska stvar.
Izkaže pa se, da je to drugo orodje, imenovano Valgrind, da je malo bolj skrivnostno za uporabo.
Njena moč je atrociously skrivnosten na prvi pogled.
Ampak to je čudovito koristno, še posebej zdaj, ko smo na delu mandata
če ste začeli uporabljati malloc in dinamično dodeljevanje pomnilnika.
Stvari lahko gredo zelo zelo narobe hitro.
Ker, če ste pozabili, da sprostite svoj spomin, ali pa dereference nekaj NULL kazalec,
ali pa dereference nekaj smeti kazalec, kar je običajno znak, da so rezultati?
SEG napake. In dobiš te glavne datoteke z nekaj več kilobajtov ali megabajtih
, ki predstavlja stanje pomnilnika programa, ko je strmoglavilo,
ampak vaš program na koncu seg napake, segmentacijo napako
kar pomeni, da je nekaj slabega zgodilo skoraj vedno
v spomin povezane napake, ki ste jih naredili nekje.
Torej Valgrind pomaga najti stvari, kot je ta.
To je orodje, ki ga vodijo, kot gdb, ko ste zbrati svoj program,
ampak kot zaženete program za neposredno zaženete Valgrind
in hodite za njim svoj program, tako kot ste storili z gdb.
Zdaj, uporaba, da bi dobili najboljše vrste proizvodnje,
je malo dolgo, tako da tam na vrhu strani zaslona boste videli Valgrind-V.
"-V" skoraj povsod pomeni, verbose, ko boste uporabljali programe na Linux računalniku.
Torej to pomeni, izpljuni več podatkov, kot si morda privzeto.
"- Puščanja preverite = polna." To je samo rekel, prijave za vse možne spomin pušča,
Napake, ki so morda sem naredila. Tudi to je pogost vzorec z Linux programov.
Na splošno, če imate argument v ukazni vrstici, da je "stikalo",
to naj bi spremenili programa ravnanja, in to je ena črka,
to je, proti, če pa je vklopljen, samo z zasnovo programer,
je celotno besedo ali zaporedje besed, je argument v ukazni vrstici se začne z -.
To so le področja človekovih, pa boste videli vse.
In potem, na koncu, "a.out" je poljubno ime za program v tem konkretnem primeru.
In tukaj je nekaj predstavnik izhod.
>> Preden pogledamo, kaj naj bi to pomenilo, naj grem več na odrezek kode tam.
In mi umaknete s poti kmalu,
in naj si na memory.c, ki je ta kratek primer tukaj.
Torej, v tem programu, mi povečate naloge in vprašanja.
Imamo funkcijo main, ki kliče funkcijo, f,
in potem kaj storiti f nadaljuje v nekoliko strokovne angleščine?
Kaj f nadaljuje narediti?
Kaj pa bom začela z linijo 20 in zvezde lokacija ni pomembna,
ampak bom samo biti v skladu z zadnjim predavanjem tukaj.
Kaj je linija 20 pa za nas? Na levi strani zaslona. Bomo razčleniti naprej.
Int * x: kaj to storiti?
Ok. To razglasitvi kazalec, zdaj pa bodimo še bolj tehnične narave.
Kaj to pomeni, zelo konkretno, naj razglasi kazalec? Nekdo drug?
Ja? [Student odgovor, nerazumljiv] predolga.
Torej berete na desni strani enačaja.
Osredotočimo se le na levi strani, samo na int * x.
To pomeni "razglasi" kazalec, ampak zdaj pa si se potopite globlje v to definicijo.
Kaj to konkretno pomeni tehnično? Ja?
[Student odgovor, nerazumljiv]
Ok. To je priprava za shranjevanje naslov v pomnilniku.
Dobro. In naj bo to en korak naprej, to je razglasitev spremenljivko x, ki je 32 bitov.
In vem, da je 32 bitov, ker -?
To ni zato, ker je int, ker je kazalec v tej zadevi.
Naključje, da je to eno in isto s notr,
vendar je dejstvo, da je zvezda pa pomeni, da je to kazalec
in naprave, tako kot pri mnogih računalnikih, vendar ne vse, kazalci so 32 bitov.
Na več moderno strojno opremo, kot so najnovejše Mac, najnovejši računalniki, morda imate 64-bitne kazalce,
vendar v napravi, te stvari so 32 bitov.
Torej bomo standardizirali na to. Bolj konkretno, zgodba gre takole:
Mi "razglasi" kazalec, kaj to pomeni?
Pripravljamo za shranjevanje naslov pomnilnika.
Kaj to pomeni?
Ustvarjamo spremenljivo imenom X, ki traja do 32 bitov
da bo kmalu shranjevanje naslov celo število.
In to je verjetno približno tako natančni, kot smo lahko dobili.
Je že v redu napreduje poenostaviti svet, samo povem, razglasi kazalec imenovan x.
Ugotovi kazalec, toda zavedati in razumeti, kaj se pravzaprav dogaja
celo v samo tistih nekaj znakov.
>> No, ta je skoraj malo lažje, čeprav je več izraz.
Torej, kaj je to početje, ki je danes poudaril: "malloc (10 * sizeof (int));" Ja?
[Student odgovor, nerazumljiv]
Dobro. In ga bom odpeljal tja. To je razporejanju kos pomnilnika za 10 celih števil.
In zdaj pa se potopite v nekoliko globlje, to je dodelitvijo kos pomnilnika za 10 števil.
Kaj je malloc potem vrnil?
Naslov tega kos, ali bolj konkretno, naslov prvega bajta te bloku.
Kako potem sem jaz, programer, da vem, če je ta kos pomnilnika koncih?
Vem, da je to stikata. Malloc, po definiciji, vam sosednje kos pomnilnika.
Ni razlike v njej. Imate dostop do vseh bajt v tem bloku,
back to back to back, ampak kako naj vem, kje je konec tega kos pomnilnika?
Ko uporabljate malloc? [Student odgovor, nerazumljiv] Dobro.
Saj ne. Moraš vedeti.
Moram vedeti, da sem uporabil vrednost 10, in mi sploh ne zdi, da so to storili tukaj.
Toda breme je v celoti na mene. Strlen, ki ste postali smo nekoliko odvisen od nizov,
deluje samo zaradi tega dogovora, ki imajo \ 0
ali ta posebni znak NUL, NUK, na koncu niza.
To ne drži za samo samovoljno kose pomnilnika.
To je odvisno od vas. Torej linije 20, nato pa namenja kos pomnilnika
da lahko shranite 10 celih števil, in ga shrani naslov prvega bajta
navedene kos pomnilnika v spremenljivko, imenovano x.
Ergo, ki je kazalec. Torej linije 21, na žalost, je bila napaka.
Ampak najprej, kaj počne? To je rekel trgovino na lokaciji, 10 indeksirajo 0,
za kos pomnilnika, imenovano x vrednost 0.
>> Torej, opazil nekaj stvari, ki se dogajajo.
Čeprav je x kazalec odpokliče nekaj tednov nazaj
da lahko še vedno uporabljate niz slogu zapis oglati oklepaj.
Ker je to pravzaprav kratki roki zapis za bolj skrivnosten usmerjene aritmetične kazalec.
če bi to naredili nekako takole: Vzemi naslov x, premaknite 10 mest več,
potem pa je, da ne glede naslov je shranjena na tem mestu.
Ampak odkrito povedano, to je samo za branje krute in se udobno.
Tako svet običajno uporablja oglate oklepaje samo zato, ker je tako veliko bolj človeku prijazen brati.
Ampak to je tisto, kar se v resnici dogaja pod pokrovom;
x je naslov, ni matrika, sama po sebi.
Torej, to je shranjevanje 0 na lokaciji v 10 x.
Zakaj je to slabo? Ja?
[Student odgovor, nerazumljiv] Točno tako.
Mi samo dodeljenih 10 ints, vendar računamo od 0 pri programiranju v C,
tako imate dostop do 0 1 2 3 4 5 6 7 8 9, ne pa 10.
Torej, ali je program SEG bo kriv ali ni.
Ampak res ne vem, to je neke vrste nondeterministic vedenja.
Res je odvisno od tega, ali bomo imeli srečo.
Če se izkaže, da operacijski sistem ne moti, če uporabim ta dodatni zlog,
kljub temu, da ni dal meni, moj program morda ne bo sesul.
To je surov, je Otroški voziček, vendar morda ne boste videli, da je simptom,
ali bi lahko vidiš le enkrat v nekaj časa.
Ampak dejstvo je, da je hrošč, v resnici obstaja.
In to je res problematično, če ste napisali program, ki ga želite, da so pravilne,
da ste prodali program, ki jih ljudje uporabljajo, da vsake toliko časa sesuje
ker, seveda, to ni dobro. V bistvu, če imate telefon Android ali iPhone
in si prenesete apps v teh dneh, če ste kdaj imeli app kar odnehati,
kar naenkrat izgine, to je skoraj vedno posledica nekaterih spomin povezano vprašanje,
pri čemer programer zamočil in dereferenced kazalec
da je on ali ona ne sme imeti, in posledica iOS ali Android je samo ubil program v celoti
namesto tveganja nedoločen vedenja ali nekakšen kompromis varnosti.
>> Še ena napaka v tem programu, poleg tega.
Kaj vse sem zamočil pri tem programu?
Nisem vadili, kar sem pridigal. Ja?
[Student odgovor, nerazumljiv] Dobro.
Nisem osvobodili pomnilnik. Tako pravilo zdaj
mora biti kadarkoli pokličete malloc, morate poklicati brezplačno, ko ste končali z uporabo te spomin.
Zdaj, ko bi želel osvoboditi ta spomin?
Verjetno, ob predpostavki, da je to prva vrstica je bila pravilna, bi rad, da to storite tukaj.
Ker nisem mogla, na primer, to storite tukaj. Zakaj?
Samo zunaj obsega. Torej, čeprav govorimo o kazalci,
To je teden, 2 ali 3 izdaje, kjer je x le v obsegu od znotraj zavitih oklepajih, kjer je navedeno, da.
Torej, zagotovo ne more osvoboditi tam. Moja edina možnost, da se sprostite, je približno po liniji 21.
To je dokaj preprost program, bilo je precej enostavno, ko si nekako zaviti vaš um
okoli kaj počne program, kjer so bile napake.
In tudi če ga niste videli na prvi, upam, da je to malo očitno zdaj
da se te napake zelo enostavno rešiti in enostavno je.
Toda, ko je program več kot 12 vrstic, to je 50 vrstic, 100 vrstic,
hoja skozi kodo po vrsticah, misleč, da s tem logično,
je možno, vendar ni posebno zabavno delati, nenehno iščejo napake,
in to je tudi težko narediti, in da je, zakaj orodje, kot Valgrind obstaja.
Naj gredo naprej in to je to: Naj odprem okno terminala,
in mi ne zaženete, le spomin, ker je pomnilnik zdi, da je v redu.
Grem srečo. Going to dodatno bajt na koncu matrike
ne zdi preveč težavno.
Vendar mi dovolite, kljub temu narediti pregled duševnega zdravja, kar pomeni samo, da preveri
ali je to dejansko pravilna.
>> Torej, kaj je naredil valgrind-V - puščanja preverite = celoti,
in nato ime programa v tem primeru je spomin, ne a.out.
Torej, naj gredo naprej in to je to. Pritisnite tipko Enter.
Dragi Bog. To je njena proizvodnja, in to je tisto, kar sem že prej omenili.
Ampak, če boste izvedeli, da se glasi skozi vse neumnosti tukaj,
večina je to samo diagnostični izhod, da to ni tako zanimivo.
Kaj vaše oči resnično želi, da se iščejo, je vsaka omemba napake ali neveljavna.
Besede, ki kažejo na težave.
In res, da vidimo, kaj je narobe tukaj.
Imam povzetek neke vrste ", ki se uporablja v izhodu:. 40 bajti v blokih 1"
Nisem ravno prepričan, kaj blok je še, ampak 40 bytes
dejansko počuti, kot sem lahko, da ugotovimo, kje prihaja.
40 bajtov. Zakaj je 40 bajtov uporabo na izhodu?
In še posebej, če se pomaknite dol,
Zato sem se dokončno izgubil 40 zlogi? Ja?
[Student odgovor, nerazumljiv] Perfect. Ja, točno tako.
Bilo je 10 cela števila, in vsak od njih je velikost 4 ali 32 bitov,
Tako sem izgubil natanko 40 bajte, ker, kot ste predlagali, nisem se imenuje brezplačno.
To je ena napaka, sedaj pa si poglejmo še malo dol in videli, poleg tega,
"Neveljavno napišite velikosti 4". Zdaj, kaj je to?
Ta naslov se izraža izhodiščno zapis, očitno?
To je šestnajstiški in kadarkoli vidite število začne z 0x,
to pomeni, šestnajstiški, ki smo davnega leta, mislim, da je oddelek pset 0 vprašanj,
, ki je bila le, da to warmup izvajanje, spreminjanje decimalno za hex za dvokomponentne in tako naprej.
Šestnajstiški, samo zaradi človeške konvencije, se običajno uporablja za predstavitev kazalcev
ali, bolj splošno, obravnava. To je samo dogovor,
ker je malo lažje brati, da je malo bolj kompakten kot nekaj podobnega decimalko,
binarni in je neuporabna za večino ljudi za uporabo.
Torej, kaj zdaj to pomeni? No, izgleda, kot da je neveljavna pisanje
velikosti 4 on line 21 memory.c.
Torej pojdimo nazaj na liniji 21 in seveda v tem, da neveljavni pisanje.
Torej Valgrind ne bo popolnoma držal za roko in mi povej, kaj popraviti, je,
vendar je odkrivanje, da delam neveljaven zapis.
Jaz sem se dotika 4 bajte, da ne smem biti, in očitno je to zato, ker
kot ste poudarili, da delam [10] namesto [9] maksimalno
ali [0] ali nekaj vmes.
Z Valgrind, spoznali koli ste zdaj pisanje programa
ki uporablja napotke in uporablja pomnilnik, in malloc natančneje,
zagotovo dobili v navado teče tako dolgo
vendar zelo preprosto kopirate in prilepite ukaz Valgrind
da vidim, če obstaja nekaj napak notri.
In to bo velika vsakič, ko vidiš izhoda,
ampak razčleniti skozi vizualno vse učinke, in videli, če boste videli omenja napak
ali opozorila ali neveljavno ali izgubljen.
Vse besede, ki zveni kot ste zajebali nekje.
Torej zavedaš, da je novo orodje v vašem orodij.
>> Zdaj v ponedeljek smo imeli cel kup ljudje pridejo sem gor
in predstavlja pojem povezan seznam.
In smo uvedli povezan seznam kot rešitev za problem, kaj?
Ja? [Student odgovor, nerazumljiv] Dobro.
Polja ne more imeti spomin jim dodane.
Če dodelijo paleto velikosti 10, to je vse, kar dobiš.
Lahko pokličete funkcijo kot realloc, če jo na začetku poimenovali malloc,
in da se lahko poskusite rastejo niz, če je prostor proti koncu tega
da nihče drug ne uporablja, in če ne, bo to samo poiskati večji kos nekje drugje.
Ampak potem se bo kopiranje vseh teh bajtov v novo polje.
To zveni kot zelo pravilna rešitev.
Zakaj je to neprivlačno?
Mislim, da deluje, ljudje so rešili ta problem.
Zakaj ga moramo rešiti v ponedeljek, povezanih s seznamov? Ja?
[Student odgovor, nerazumljiv] To lahko traja dolgo časa.
V bistvu, vsakič, ko kličeš malloc ali realloc ali calloc, kar je še ena,
vsakič, ko je program, v pogovoru z operacijskim sistemom,
ste nagnjeni k upočasni programa navzdol.
In če delaš te vrste stvari zank, ste res upočasnjuje stvari navzdol.
Ne boš opazil tole najenostavnejši "Hello World" tipa programov,
vendar v veliko večjih programov, ki prosi za operacijski sistem znova in znova, za spomin
ali daje znova in znova kaže, da ni dobra stvar.
Plus, to je nekako intelektualno - to je popolna izguba časa.
Zakaj dodeli več in več pomnilnika, tveganje kopiranje vse v novo polje,
Če imate možnost, ki vam omogoča, da dodeli le toliko pomnilnika, kot ga dejansko potrebujejo?
Torej je v pluse in minuse tukaj.
Eden od pluse zdaj, je, da imamo dinamiko.
Ni važno, če so kosi spomin so, da so svobodne,
Lahko samo nekako ustvarili te krušnih drobtin prek kazalcev
za niz ves moj povezani seznam skupaj.
Ampak plačam vsaj eno ceno.
>> Kaj moram storiti, da bi se pri pridobivanju povezane sezname?
Ja? [Student odgovor, nerazumljiv] Dobro.
Če potrebujete več pomnilnika. Zdaj rabim prostor za te napotke,
in v primeru te super navadno povezan seznam
da je le poskušal shraniti celih, ki so 4 bajte, da ponavljate
No, kazalec je 4 bajte, tako da zdaj sem dobesedno podvojilo
količino pomnilnika, rabim samo za shranjevanje ta seznam.
Ampak spet, to je stalna kompromis v računalništvu
med časom in prostorom in razvoj, trud in drugih virov.
Kaj je druga negativna uporabo povezani seznam? Ja?
[Student odgovor, nerazumljiv]
Dobro. Ni tako enostavno dostopna. Mi ne more več vzvoda
teden 0 načela, kot so deli in vladaj.
In še posebej, binarno iskanje. Ker čeprav smo ljudje
grobo videti, kje je sredi tega seznama je
računalnik ve, da je to povezano Seznam se začne na naslovu imenovani prvi.
In to je 0x123 ali kaj podobnega.
In edini način, da se program je bil srednji element
je pravzaprav iskanje celoten seznam.
In tudi takrat, dobesedno mora poiskati celoten seznam, ker
Niti enkrat pridete v srednji element z upoštevanjem nasvetov,
ti, program, ne vem, kako dolgo ta seznam, potencialno
dokler si udaril konec njej, in kako veš programsko
da si na koncu povezan seznam?
Obstaja posebna NULL kazalec, tako da spet konvencije.
Namesto tega uporabite kazalec, da zagotovo ne želite, da bi bilo nekaj smeti vrednost
kaže odra nekje, želimo, da bi bilo z roko navzdol, NULL,
tako da imamo to postajo v tej strukturo podatkov, da vemo, kje se konča.
>> Kaj pa, če želimo, da manipulira to?
Naredili smo večino tega vizualno in z ljudmi,
kaj pa, če želimo narediti vstavljanje?
Tako je bil prvotni seznam 9, 17, 20, 22, 29, 34.
Kaj, če bi potem želel prostora malloc za številko 55, vozlišča za to,
in potem želimo vstaviti na seznam 55 tako kot smo storili v ponedeljek?
Kako to storiti? No, Anita prišel gor in je v bistvu hodil seznam.
Začela je pri prvem elementu, nato pa je naslednji, naslednji, naslednji, naslednji, naslednji.
Končno je zadel na levi strani vse do konca
in ugotovil, oh, to je NULL. Torej, kaj je kazalec manipulacijo je treba storiti?
Oseba, ki je bil na koncu, številka 34, je potrebno njegovo levo roko dvigne
točko na 55, 55 potrebna svojo levo roko obrnjeno navzdol, da je novi terminator NULL. Končano.
Precej enostavno vstavljanje 55 v seznamu razvrščeni.
In kako bi to izgledalo?
>> Naj gredo naprej in odprla nekaj kode primer tukaj.
Jaz bom odprl gedit, in mi odprla dve datoteki prvi.
Eden od njih je list1.h, in dovolite mi, spomnil, da je bil to kos kode
ki smo jo uporabili, da predstavlja vozlišče.
Vozlišče ima tako imenovano int n in kazalec se imenuje naslednji, ki le opozarja na naslednje stvari na seznamu.
To je zdaj v datoteko. H. Zakaj?
Tam je ta konvencija, in nismo izkoristili te ogromne količine sami,
ampak oseba, ki je napisal printf in druge naloge
je kot darilo na svetu vseh teh funkcij, s pisanjem datoteko z imenom stdio.h.
In potem je tukaj še string.h, in potem je tukaj še map.h, in tam je vse te datoteke h
da ste morda videli ali se uporabljajo v času pisnega drugih ljudi.
Običajno pri njih. H datoteke so samo stvari, kot typedefs
ali izjave po meri, vrste ali izjav konstant.
Vi ne dajo funkcijo "izvedb v glavi datoteke.
Ti pa, namesto, le svoje prototipe.
Si dal stvari, ki jih želite deliti s svetom, kar potrebujejo
da se pripravijo svojo kodo. Torej, samo priti v to navado,
smo se odločili, da storijo enako stvar. Ni veliko list1.h,
pa smo pripravili nekaj, kar bi lahko v interesu ljudi v svetu
ki želijo uporabljati svoj povezano izvajanje seznam.
Zdaj, v list1.c, ne bo šel skozi vso to stvar
ker je nekoliko predolg, je ta program, vendar naj vodijo to resnično hitro na poziv.
Naj pripravijo List1, dovolite mi, torej prost List1, in kar boste videli se
Mi smo simulirano preprost program za malo tukaj
da se dogaja, da mi dovolite, da dodate in odstranite številke na seznamu.
Torej, naj gredo naprej in tip 3 za 3 menija.
Želim vstavite številko - naredimo prva številka, ki je bila 9,
in zdaj sem povedal, je seznam zdaj 9.
Naj gredo naprej in eno vstavljanje, tako da sem zadel menija 3.
Kaj več ne želim vstaviti? 17.
Enter. In jaz bom samo še eno.
Naj vstavite številko 22.
Torej imamo začetke povezan seznam, ki smo jih imeli v obliki diapozitiva pred nekaj trenutki.
Kako se to dejansko dogaja vstavljanje?
Seveda, 22 je zdaj na koncu seznama.
Torej zgodbe nam povedali na odru v ponedeljek in recapped pravkar
treba dejansko dogaja v kodi.
Oglejmo si. Dovolite mi, da se pomaknete navzdol v tej datoteki.
Mi bomo zatajili nekatere funkcije,
ampak bomo šli dol na, recimo, vstaviti funkcijo.
>> Poglejmo, kako bomo šli o vstavljanju novo vozlišče v tem povezan seznam.
Če je seznam prijavljena? No, pa se pomaknite vso pot navzgor na vrhu,
in opazil, da je moj povezani seznam bistvu je deklariran kot en sam kazalec, ki je sprva NULL.
Torej, jaz sem z globalno spremenljivko tukaj, ki na splošno smo pridigal proti
ker je tako kodo malo grdo, da ohranjajo,
to je nekako leni, običajno, ampak ne leni in ni narobe in to ni slabo
Če je vaš program je edini cilj v življenju je, da simulira eno povezano seznam.
Kar je točno to, kar delamo.
Torej, namesto navesti v glavni nato pa so ga posredovati v vsaki funkciji
smo napisana v tem programu, smo namesto tega zavedaš, oh, kaj je samo, da je svetovna
ker je glavni namen tega programa je pokazati eno in samo eno povezani seznam.
Tako, da se počuti v redu. Tukaj so moji prototipi, in ne bomo šli skozi vse to,
vendar sem napisal funkcijo za brisanje, je najti funkcijo, je vstaviti funkcijo in funkcijo premikanja.
Ampak kaj je zdaj šel nazaj na vstaviti funkcijo
in videli, kako se dela tukaj.
Vstavi se na spletu - gremo.
Vstavi. Torej, da ne bo nobenih argumentov, ker bomo to ask
uporabnik znotraj te funkcije za številko, ki jih želite vstaviti.
Ampak najprej moramo pripraviti, da jim nekaj prostora.
To je neke vrste kopiraj in prilepi iz drugega npr.
V tem primeru smo dodeljevanja int, tokrat bomo dodelitvi vozlišče.
Ne spomnim se, koliko bajtov vozlišče je, ampak to je v redu.
Sizeof lahko ugotovimo, da je zame.
In zakaj sem iskal v skladu NULL 120?
Kaj bi lahko šlo narobe v skladu 119? Ja?
[Student odgovor, nerazumljiv]
Dobro. Tako bi se lahko zgodilo, da sem prosila za preveč pomnilnika
ali je nekaj narobe, in operacijski sistem nima dovolj bajte, da bi me dali,
tako da kaže, kolikor ga vrne NULL, in če ne bom preveriti, da
in sem slepo nadaljuje z uporabo naslov vrnil, bi bilo NULL.
Lahko bi bilo nekaj neznanega vrednost, ni dobro, če ne -
dejansko ne bo neznano vrednost. To je lahko NULL, zato ne želim,
da ga zlorabljajo in tveganja, ki ga Dereferenciranje.
Če se to zgodi, sem vrnil in pretvarjali se bomo, tako kot nisem dobil nazaj vsako spomin na vse.
>> Sicer pa vem, da si mi nekaj, da vstavite kličem, naš stari prijatelj GetInt,
in potem je bila to nova skladnja smo predstavili v ponedeljek.
"Newptr-> n 'pomeni imeti naslov, ki ste bili, ki jo knjižnične funkcije malloc
ki predstavlja prvi bajt nov objekt vozlišča,
nato pa pojdite na polje, imenovano n.
Malo trivia vprašanje: To je enako, v kakšnem bolj Grobni vrstico kode?
Kako bi drugače sem napisal to? Želite, da bi zabodel?
[Student odgovor, nerazumljiv]
Dobro. Uporaba n., Vendar to ni tako preprosto, kot je ta.
Kaj morali najprej narediti? [Student odgovor, nerazumljiv]
Dobro. Moram narediti * newptr.n.
Torej, to je rekel nov kazalec, je očitno naslov. Zakaj?
Ker se je vrnila knjižnične funkcije malloc. Znak * newptr rekel "pojdi tja"
in potem, ko si tam, potem lahko uporabite bolje pozna. n,
vendar je to samo izgleda malce grdo, še posebej, če smo ljudje bodo
pripravi nasvetov s puščicami ves čas, svet je standardiziran na tem arrow zapisu
ki ima natanko isto stvar.
Torej, uporabite le -> zapis, ko je stvar na levi strani je kazalec.
Sicer pa, če je to dejansko struct uporabite. N.
In potem je to: Zakaj se zažene newptr-> naslednji na NULL?
Ne želimo, da binglja levo roko off na koncu stopnje.
Želimo, da usmerjena naravnost navzdol, kar pomeni konec tega seznama
bi lahko bilo v tem vozlišču, zato smo se raje prepričajte, da je NULL.
In na splošno inicializacijo spremenljivk ali vaše podatkovne članov in konstrukti
za nekaj, kar je le dobra praksa.
Samo da smeti obstajajo in še naprej obstajati tudi ti zaide v težave
če ste pozabili, da narediš nekaj kasneje.
>> Tukaj je nekaj primerov. To pa ponovno je vstaviti funkcijo,
in prva stvar, ki sem preveriti, če je spremenljivka imenovan prvi,
da je globalna spremenljivka je NULL, kar pomeni, da ni povezan seznam.
Nismo vstavi vse številke, tako da je nepomembno, da vstavite to trenutno število
na seznam, ker samo sodi na začetku seznama.
Torej, to je bilo, ko Anita sem samo stal tu sam pretvarja
nihče drug je bil tu gor na oder, dokler ne bomo namenili vozlišče,
potem bi ona dvignila roko, prvič,
če bi vsi ostali prišli na oder za njo v ponedeljek.
Zdaj je tu, to je malo pregled, kjer moram reči, če je novo vozlišče je vrednost n
je <vrednost n v sedanji prvega vozla,
to pomeni, da je povezani seznam, ki je začela.
Tam je vsaj en vozel v seznamu, vendar je ta novi tip
Spada pred, zato moramo premakniti stvari na bolje.
Z drugimi besedami, če je seznam začelo s preprosto, recimo,
samo številka 17, ki je - pravzaprav, lahko to bolj jasno.
Če začnemo našo zgodbo s kazalcem tu imenuje prvi,
in na začetku je NULL, in smo vstavite številko 9,
številka 9, očitno pripada na začetku seznama.
Torej, kaj je pretvarjal smo samo malloced naslov ali številko 9 in ga tukaj.
Če Prvi je 9 privzeto, prvi scenarij smo se pogovarjali samo pomeni točko, dajmo ta tip tukaj,
pustite, da je to NULL, zdaj imamo številko 9.
Naslednja številka želimo vstaviti je 17.
17 spada sem, da bomo morali narediti nekaj logičnih korakih skozi to.
Torej, namesto, preden bomo to storili, dajmo se pretvarjamo, da smo želeli vstaviti številko 8.
>> Torej samo zaradi priročnosti je, da bom tu izvlekli.
Ampak zapomni si, lahko malloc dal najbolj kjerkoli.
Ampak za božjo risba je, ga bom dal sem.
Tako se pretvarjamo, da sem pravkar dodeljen vozlišče za številko 8, kar je NULL privzeto.
Kaj je zdaj zgodilo? Nekaj ​​stvari.
Naredili smo to napako na odru v ponedeljek, ko smo posodobili kazalec, kot je ta,
potem je to storil, nato pa smo trdili - smo vsi ostali brez staršev na odru.
Ker si moreš - vrstni red operacij tu je pomembno,
ker zdaj smo izgubili to vozlišče 9, ki je nekako lebdi v prostoru.
Torej to ni pravi pristop v ponedeljek.
Najprej smo morali narediti nekaj drugega.
Stanje na svetu videti takole. Sprva je bil dodeljen 8.
Kaj bi lahko bil boljši način za vstavljanje 8?
Namesto posodabljanje tega kazalca prvič, samo posodobite tole tukaj namesto tega.
Zato moramo vrstico kode, ki se dogaja, da želite to NULL značaja
v dejanski kazalec, ki je obrnjena na vozlišču 9,
in potem bomo lahko varno spremeniti najprej opozoriti na ta tip tukaj.
Zdaj imamo seznam, povezani seznam, dveh elementov.
In kaj to dejansko videti tukaj?
Če pogledamo kodo, opazil, da sem storil prav to.
Rekel sem newptr, in v tej zgodbi, newptr je kazal tega tipa.
>> Torej, naj pripravi še eno stvar, in jaz bi pustil malo več prostora za to.
Torej, odpusti mali risbo.
Ta tip se imenuje newptr.
To je spremenljivka smo objavili nekaj vrstic prej, v skladu - malo nad 25 let.
In to je obrnjena na 8. Torej, ko rečem newptr-> naslednji, kar pomeni, da gre za struct
da se je opozoril na po newptr, zato pa smo tukaj, pojdi tja.
Potem je rekel arrow dobili naslednje polje in nato = pravi dal kakšno vrednost tam?
Vrednost, ki je bil v prvi, kakšno vrednost je bila v prvi?
Najprej je pokazal na tem vozlišču, da to pomeni, da mora to zdaj opozoriti na to vozlišče.
Z drugimi besedami, kar je videti smešno, čeprav igraš z mojo pisavo,
Kaj je preprosta ideja samo premika puščici, okoli
prevaja kodo s samo te ene plasti.
Shranite, kar je v prvi na naslednje polje in nato posodobite kaj 1. dejansko je.
Pojdimo in hitro naprej skozi nekaj tega,
in poglej samo na tej rep vstavitve, za zdaj.
Recimo, da sem prišel do točke, ko sem ugotovila, da je naslednje polje nekega vozlišča NULL.
In na tej točki v zgodbo, podrobnosti, ki sem preskakujem
to, da sem uvedli še kazalec gor v skladu 142, predhodnik kazalca.
V bistvu, v tem trenutku v zgodbi, ko dobi seznam dolg,
Nekako morate hoditi z dvema prstoma, ker če grem predaleč,
spomnim na eno dolžino seznamu, ne morete iti nazaj.
Torej ta ideja predptr je moja leva prst in newptr - ne newptr.
Še en namig, da je tu je moj drugi prst, in sem nekako hoje seznam.
Zato, da obstaja. No, pa upoštevamo samo eno od enostavnejših primerov tukaj.
Če tega kazalca se naslednje polje NULL, kaj je logično posledice?
Če ste vozili ta seznam in ga zadel NULL kazalec?
Ste na koncu seznama, in tako kodo, nato priložiti 1 dodaten element
se bo nekako intuitivno sprejeti, da vozlišče, katerega naslednji kazalec NULL,
tako da je to trenutno NULL, in ga spremenil, da je naslov novega vozlišča.
Torej smo samo risbo v kodi puščico, ki smo potegnil na odru z dvigom nekoga levo roko.
>> In v primeru, da bom pomahal roke na za zdaj,
samo zato, ker mislim, da je enostavno se izgubiš, ko to počnemo v to vrsto okolja,
preverja za vključitev v sredini poštnega spiska.
Ampak samo intuitivno, kaj bi se zgodilo, če hočeš, da ugotovimo,
kjer je nekaj več, spada v sredini pa morate, da jo peš
z več kot enim prstom, več kot en kazalec,
ugotovimo, kamor spada s preverjanjem je element, <se bo sedanji,
> Trenutni 1, in ko ste našli to mesto,
potem moraš to storiti vrste divjadi lupine, kjer ste premakniti kazalcev po zelo previdno.
In to je odgovor, če želite, da zato s tega doma sami,
izvira prav na teh dveh vrstic kode, vendar je zaradi teh vrstic je zelo pomembno.
Ker, če nekdo spusti roko in dvig nekdo drug v napačnem vrstnem redu,
še enkrat, bi lahko na koncu orphaning seznam.
Če povzamemo bolj konceptualno, vstavljanja na repu je dokaj preprosta.
Vključitev na čelu je tudi relativno enostavna,
vendar pa boste morali posodobiti dodaten kazalec, tokrat
stisniti številko 5 na seznam tukaj,
in potem vključitev v sredini vključuje še več truda,
zelo previdno vstavite številko 20 v svojem pravem mestu,
, ki je med 17 in 22.
Tako da boste morali narediti nekaj podobnega imajo novo vozlišče točko 20 do 22,
in potem, ki je vozlišče je kazalec je treba posodobiti nazadnje?
To je 17, v resnici ga vstavite.
Torej, še enkrat, bom odloži dejansko kodo za posamezno izvedbo.
>> Na prvi pogled je to malo veliko, ampak to je res samo neskončno zanko
da je zanka, zanka, zanka, zanka, in zlom takoj, ko hit kazalec NULL,
Takrat lahko narediš potrebno vstavljati.
To je torej zastopnik povezani seznam vstavljanje kode.
To je neke vrste veliko, in se počuti kot smo rešili eno težavo,
pa smo uvedli celo drugo. Odkrito povedano, smo porabili ves ta čas
na velikem O in Ω in teče čas, poskuša reševati probleme hitreje,
in tukaj smo naredili velik korak nazaj, se mu zdi.
In še to, če je cilj za shranjevanje podatkov,
se zdi, kot sveti gral, kot smo rekli v ponedeljek, bi bilo res
Shranjevanje stvari takoj.
>> Dejstvo je, denimo, da smo odložili povezani seznam za trenutek
in smo namesto tega uvedel pojem mizo.
In kaj je samo pomislite na mizi za trenutek kot matriko.
Ta pestrost in ta primer tukaj je nekaj 26 elementov, od 0 do 25,
in predvidevam, da je potrebno nekaj kos shranjevanje imen:
Alice in Bob in Charlie in podobno.
In boste potrebovali nekaj podatkovno strukturo za shranjevanje teh imen.
No, lahko uporabite nekaj podobnega povezan seznam
in lahko hodiš seznam vstavljanje Alice pred Bob in Charlie po Bobu in tako naprej.
In v resnici, če želite videti kodo, kot je ta v prahi,
vem, da je v list2.h, delamo točno to.
Mi ne bo šel skozi to kodo, ampak to je varianta prvi primer
, ki uvaja še eno struct, ki smo jih videli, preden ti študenta,
in kaj potem dejansko shrani v povezano seznamu je kazalec na strukturo študentov
namesto da preprosto malo celo število, n.
Torej zavedaš, da je oznaka, ki vključuje dejansko obstaja niti,
če pa je cilj na strani res zdaj je reševanje problema učinkovitosti,
Ne bi bilo lepo, če smo glede na predmet z imenom Alice,
želimo, da bi jo dal v pravo mesto v strukturo podatkov,
se zdi, kot bi bilo res lepo, samo da Alice,
katerih ime se začne z, na prvem mestu.
In Bob, katerih ime se začne z B, v drugem mestu.
Z matriko, ali pa začnimo kliče to tabelo, hash tabele pri tem,
ne moremo storiti prav to. Če smo dobili takšno ime Alice,
Niz kot Alice, kje si dal a-L-i-C-e?
Potrebujemo hueristic. Potrebujemo funkcijo, da sprejmejo nekatere prispevke, kot Alice
in vrne odgovor, "Put Alice na tej lokaciji."
In to funkcijo, to črno polje, se bo imenovano funkcijo razpršitve.
>> Razpršilna funkcija je nekaj, kar se vnosa, kot je "Alice",
in se vrne v vas, ponavadi, številčna lokacijo v nekaterih strukture podatkov, kadar Alice pripada.
V tem primeru bi morala biti naša hash funkcija je dokaj preprost.
Naša hash funkcijo je treba povedati, če ste dobili "Alice", ki je znak naj skrbi?
Prvi. Torej gledam [0], potem pa sem rekel, če [0] znak je, vrne število 0.
Če je B, vrne 1. Če je C, vrne 2, in tako naprej.
Vse indeks 0, in da bi mi dovolite, da vstavite Alice in nato Bob in nato Charlie in tako naprej
V to strukturo podatkov. Vendar obstaja problem.
Kaj pa, če Anita prihaja skupaj spet?
Kam smo pripravili Anita? Njeno ime je tudi, začne s črko A,
in se počuti kot smo naredili še večjo zmešnjavo tega problema.
Zdaj imamo takojšnjo vključitev, konstantna čas vnosa, v strukturo podatkov
kot najslabšo linearna,
ampak kaj lahko storimo z Anito v tem primeru?
Kakšne so dve možnosti, res? Ja?
[Student odgovor, nerazumljiv] Ok, tako da bi lahko dobili novo razsežnost.
To je dobro. Tako lahko gradimo stvari v 3D tehniki, kot smo govorili v ponedeljek ustno.
Lahko bi dodali še en dostop do tu, ampak predvidevam, da ne, sem poskušal ohraniti to preprosto.
Celoten cilj tukaj je, da imajo takojšen stalen dostop času,
tako, da je dodal preveč kompleksnosti.
Kakšne so druge možnosti, ko skušajo vstaviti Anita v tej strukturi podatkov? Ja?
[Student odgovor, nerazumljiv] Dobro. Torej lahko gremo vsi ostali navzdol
kot Charlie dregne navzdol Bob in Alice, nato pa smo se Anita, če res želi biti.
>> Seveda, zdaj pa je stranski učinek tega.
Ta struktura podatkov, je verjetno koristno, ne zato, ker želimo vstaviti ljudi, ko
ampak zato, ker smo želeli preveriti, če so tam kasneje
če želimo izpisati vsa imena v strukturi podatkov.
Bomo nekaj storiti s temi podatki na koncu.
Zdaj smo že vrsto privili v Alice, ki je ni več kje je moral biti.
Prav tako je Bob, prav tako je Charlie.
Mogoče to ni tako dobra ideja.
Ampak seveda, to je ena od možnosti. Mi lahko premakne vse navzdol,
ali pekel, Anita prišla prepozno v igro, zakaj ne bi raje dal Anita
ne tukaj, ne tukaj, ne tukaj, kaj je pravkar jo dal malo nižje na seznamu.
Ampak potem je to problem se začne znova prenesti.
Morda boste lahko našli Alice takoj, na podlagi njenega imena.
In Bob takoj in Charlie. Ampak potem iskati Anita,
in vidite, hmm, Alice je v napoto.
No, naj preverim pod Alice. Bob ni Anita.
Charlie ni Anita. Oh, je Anita.
In če boste še naprej vlak logike vso pot,
kaj je najslabši čas vožnje za iskanje in vstavljanje Anita v novo strukturo podatkov?
To je O (n), kajne?
Ker v najslabšem primeru pa je Alice, Bob, Charlie. . .
vso pot navzdol, da nekdo z imenom "Y", tako da je le eno mesto levo.
K sreči smo imeli nikogar, imenovano "Z", zato smo se Anita na samem dnu.
>> Nismo zares rešil ta problem.
Mogoče pa je treba uvesti to tretjo dimenzijo.
In izkazalo se je, če ne bomo uvesti to tretjo dimenzijo,
ne moremo narediti odlično, vendar je sveti gral se bo pridobivanje
stalen čas vstavitve in dinamične vstavljanja, tako da
nimamo na trdo koda matrika velikosti 26.
Mi lahko vstavite toliko imen, kot smo želeli, vendar pa si vzamemo 5-minutni odmor tukaj
in potem to naredil pravilno.
V redu. Sem nastavil zgodbo precej umetno tam
z izbiro Alice in nato Bob in nato Charlie in nato Anita,
čigar ime je bilo očitno bo trčijo z Alice.
Toda vprašanje, ki se je končalo v ponedeljek, z le tem, kako verjetno je, da
da bi dobili te vrste trčenj? Z drugimi besedami,
če začnemo uporabljati to tabelarične strukture, ki je res samo matrika,
v tem primeru 26 lokacijah,
Kaj pa, če so naši vložki namesto enakomerno porazdeljeno?
To ni umetno Alice in Bob in Charlie in David in tako naprej po abecedi
to je enakomerno porazdeljeno po Z.
>> Mogoče bomo le srečo in mi ne bo treba 2 je B-jev ali dva
z zelo veliko verjetnostjo, ampak kot nekdo opozoril,
če posplošena ta problem in ne storiti 0-25
ampak, recimo, od 0 do 364 in 65, se je število dni, v običajnem letu,
in vprašala: "Kaj pa je verjetnost, da sta dva od nas v tej sobi imajo isti rojstni dan?"
Povedano drugače, v čem je verjetnost, da naju imajo ime se začne z?
Neke vrste vprašanje je enak, vendar je ta naslovni prostor,
to iskanje prostora, je večja pri rojstnih dnevih,
ker imamo toliko več dni v letu, od črk v abecedi.
Kakšna je verjetnost trka?
No, lahko razmišljamo o tem, ki jih poskušal ugotoviti, matematika v nasprotno smer.
Kakšna je verjetnost, da brez trkov?
No, ta izraz pravi, da tisto, kar je verjetnost
če je samo ena oseba v tej sobi, da imajo edinstveno rojstni dan?
To je 100%. Ker če je samo ena oseba v sobi,
njegov ali njen rojstni dan je lahko katera koli od 365 dni v letu.
Torej 365/365 možnosti mi daje vrednost 1.
Zato je verjetnost, zadevni v tem trenutku je le 1.
Ampak, če obstaja druga oseba v sobi,
kaj je verjetnost, da je njihov rojstni dan drugačen?
Tukaj je le mogoče, 364 dni, če izvzamemo prestopna leta,
za rojstni dan niso v nasprotju z drugimi osebami.
Torej 364/365. Če tretja oseba prihaja, to je 363/365 in tako naprej.
Tako smo ostali zmnožku teh frakcij, ki so vse manjši in manjši,
da ugotovimo, kaj je verjetnost, da imamo vsi edinstvene rojstne dneve?
Ampak potem bomo lahko, seveda, samo da ta odgovor in ga flip okoli
in še 1 minus vse to, izraz, da bomo na koncu dobili
če se spomnite na zadnjo stran vaših matematičnih knjig, izgleda malo kaj takega,
ki je veliko lažje razumeti grafično.
In tukaj je ta grafični na os x število rojstni dan,
ali število ljudi s rojstni dan, in na osi y, je verjetnost, da bo tekmo.
In kaj je rekel je, da če imate, recimo, tudi,
kaj je izbrati nekaj podobnega 22, 23 let.
Če je 22 ali 23 ljudi v sobi,
je verjetnost, da sta dva od teh zelo malo ljudi, ki bodo imeli enako rojstni dan
je pravzaprav zelo visoka, combinatorially.
50% verjetnost, da je v razredu le 22 ljudi, seminar, praktično,
2 od teh ljudi se dogaja, da imajo enako rojstni dan.
Ker obstaja toliko načinov, na katere lahko imajo isti rojstni dan.
Še huje, če pogledaš na desni strani grafikona,
čas, ki ga imajo v razredu z 58 učenci v njem,
verjetnost 2 ljudi, ki imajo rojstni dan je super, super visoka, skoraj 100%.
No, to je neke vrste zabavna dejstva o resničnem življenju.
>> Toda posledice, zdaj, podatkovnih struktur in shranjevanje informacij
pomeni, da le ob predpostavki, da imate lepo, čisto in enakomerno porazdelitev podatkov
in imate dovolj velik spekter, da se prilega kup stvari
ne pomeni, da boš dobil ljudi v različnih lokacij.
Ti boš moral trčenja. Torej ta pojem hašiš, kot se imenuje,
ob vnosa, kot je "Alice" in ga vmasirajte na nek način
in potem dobili nazaj odgovor, kot 0 ali 1 ali 2.
Vrnil nekaj izhod iz te funkcije je pestile ta verjetnost trka.
Torej, kako lahko obravnavo teh trkov?
No, na enem primeru, da bomo lahko idejo, da je bil predlagan.
Mi lahko samo premakniti vse navzdol, ali morda, malo bolj enostavno,
kot vsi ostali move, kaj je samo premakniti Anita na dnu voljo kraju samem.
Torej, če je v Alice 0, Bob je 1, Charlie je v 2,
bomo samo da Anita na lokaciji 3.
In to je tehnika, pri podatkovne strukture imenujemo linearna sondiranje.
Linearni saj ste samo peš to vrstico in si nekako sondiranje
razpoložljive mestih v strukturi podatkov.
Seveda, to je naloga v O (n).
Če podatkovna struktura je zelo polno, tam je 25 ljudi je v njem že
in potem Anita prihaja skupaj, ona konča, kaj bi mesto Z, in to je v redu.
Še vedno paše, in smo jo lahko našli kasneje.
>> Ampak to je bilo v nasprotju s ciljem pospešiti stvari.
Pa kaj, če smo namesto tega uvedli tretjo dimenzijo?
Ta tehnika je navadno imenujemo Veriženje, ali ima verige.
In kaj je sedaj razpršena tabela, to tabelarični struktura,
vaša miza je le niz kazalcev.
Ampak kaj so ti kazalci kažejo, da je ugibanje, kaj?
Povezani seznam. Pa kaj, če bomo najboljše obeh svetov?
Mi uporabljamo nize za začetne indekse
v strukturo podatkov, da bomo lahko takoj pojdite na [0] [1], [30] ali tako dalje,
vendar tako, da imamo nekaj prožnosti, da lahko fit Anita in Alice in Adam
in katero koli drugo ime,
smo namesto tega kaj druga os rastejo samovoljno.
In končno, kot v ponedeljek, so, da izrazno zmogljivost z povezanem seznamu.
Mi lahko raste podatkovno strukturo samovoljno.
Druga možnost je, lahko bi le, da veliko 2-dimenzionalni array,
ampak to se dogaja, da je grozno stanje, če ena od vrstic v 2-dimenzionalni array
ni dovolj velika za dodatno osebo, katere ime se zgodi, da začnete z A.
Bog ne daj, da bomo morali prerazporediti velik 2-dimenzionalno strukturo
Samo zato, ker je toliko ljudi z imenom,
še posebej, ko je tako malo ljudi, imenovana Z nekaj.
To je le, da bo treba zelo redka strukturo podatkov.
Torej, to ni popoln na kakršen koli način, zdaj pa smo vsaj imeli možnost
da takoj našli, če Alice in Anita pripada,
vsaj z vidika navpične osi
in potem bomo morali odločiti, kam Anita ali Alice v tem povezan seznam.
Če nam ni mar za urejanje stvari, kako hitro smo lahko vstavite Alice v strukturo, kot je ta?
To je stalen čas. Mi indeks v [0], in če je nihče ni tam,
Alice gre na začetku tega povezanega seznama.
Ampak to ni velik posel. Ker če Anita potem pride skupaj
nekaj več korakov pozneje, če ne pripada Anita?
No, [0]. OOP. Alice je že v tem povezan seznam.
>> Toda, če ne skrbi za urejanje teh imen,
lahko samo premaknete Alice več, Anita vložek, ampak tudi, da je konstantna čas.
Tudi če obstaja Alice in Adama in vsi ti A imena,
to ni res jih prestavljajo fizično. Zakaj?
Ker smo pravkar naredil sem z povezanega seznama, ki ve, so ta vozlišča so anyway?
Vse kar morate storiti je, da se premaknete na krušnih drobtin.
Move okrog s puščicami, zato vam ni treba fizično premakniti nobenih podatkov naokoli.
Tako bomo lahko vstavite Anita, v tem primeru takoj. Stalno čas.
Torej imamo konstantno času lookup in konstantno času vstavitev nekoga, kot je Anita.
Ampak nekako oversimplifying svet.
Kaj, če bi kasneje želeli, da bi našli Alice?
Koliko korakov je, da bo trajalo?
[Student odgovor, nerazumljiv]
Točno tako. Število ljudi, pred Alica v povezanem seznamu.
Torej, to ni čisto popoln, saj je naša podatkovna struktura, še enkrat, je to navpično dostop
in potem je ta povezana sezname visi - pravzaprav naj ne pripravi ga niza.
To je ti povezani seznam visi za to, da izgleda malo kaj takega.
Ampak problem je, če se Alice in Adama in vsi ti A imena
na koncu bolj in bolj tam,
iskanje nekdo lahko na koncu ob kup korakov,
bcause morate prečkati povezani seznam,
ki je linearna operacija.
Torej res, potem, ko je navsezadnje vstavljanje O (n), kjer je n število elementov v seznamu.
Delimo jih, kaj je samovoljno imenujejo m, kjer je m število povezanih seznamov
da imamo v tem navpične osi.
Z drugimi besedami, če bomo resnično prevzeti enakomerno porazdelitev imen,
popolnoma nerealen. Tu je seveda še nekaterih pisem od drugih.
>> Ampak, če predpostavimo, zaenkrat enotno distribucijsko
in smo N skupaj ljudi in celotne verige m
imamo na voljo, potem dolžina vsakega od teh verig
dokaj preprosto se bo skupna, n deljen s številom verig.
Torej n / m. Ampak tukaj kjer smo lahko vsi matematično pameten.
m je konstantna, ker je določeno število teh.
Ti boš razglasila svojo paleto na začetku,
in nismo spreminjanje velikosti navpične osi. Po definiciji, ki je določena ostane.
To je samo horizontalna os, če se tako izrazim, ki se spreminja.
Torej, tehnično, to je konstanta. Torej, zdaj, vstavljanje čas
je precej O (n).
Tako, da ne čuti vse, da je veliko bolje.
Toda kaj je resnica tukaj? No, ves ta čas, za tedne,
smo bili pravi O (n ²). O (n), 2 x n ², - n, deljeno z 2. . . ECH.
To je samo n ². Toda zdaj, v tem delu semestra,
lahko začnemo govoriti o resničnem svetu znova.
In n / m je popolnoma hitreje kot le n sam.
Če imate več kot tisoč imen, in jih razbije na več segmentov
tako da imate samo 10 imen v vsaki od teh verig,
Popolnoma iskati deset stvari, se bo hitreje kot tisoč stvari.
In tako eno od naslednjih problemskih sklopov vas bo izpodbijala
razmišljati o točno to, čeprav, ja,
asimptotično in matematično, je to še vedno samo linearna,
, ki je zanič na splošno, ko poskušajo najti stvari.
V resnici pa se dogaja, da se hitreje, kot je
zaradi tega delitelj.
In tako se je spet bo ta kompromis
in ta konflikt med teorijo in realnostjo,
in bo eden izmed gumbov začela vrteti v tem trenutku v semestru
je bolj za realnost 1, kot smo nekako pripraviti na koncu semster je,
kot uvajamo v svet programiranja spletnih strani,
če res, uspešnost štelo bo, ker uporabniki se bodo
začnete počutiti in cenijo slabe odločitve design.
>> Torej, kako si šel o izvajanju povezano - razpršitve tabelo z 31 elementi?
In prejšnji primer je samovoljno o rojstnih dnevih.
Če ima nekdo rojstni dan 1. januar ali februar 1, jih bomo dal v ta segment.
Če je 2. januar, 2. februar, marec 2, jih bomo dal v ta segment.
Zato je bil 31. Kako se razglasi razpršene tabele?
To je lahko zelo enostavno, vozlišče * miza je moje poljubno ime za to, [31].
To mi daje napotke za 31 vozlišč,
in ki mi omogoča, da imajo 31 nasvetov za povezane sezname
tudi če te verige so sprva NULL.
Kaj hočem dati, če želim shraniti "Alice", "Bob", "Charlie"?
No, moramo zaviti tiste stvari, v strukturi
ker moramo opozoriti, da Alice Bob, ki kaže na Charlie, in tako naprej.
Ne moremo imeti imena sami, tako da sem lahko zgradili novo strukturo, imenovano vozlišče tukaj.
>> Kaj je dejansko vozel? Kaj je vozlišče v tem novem povezana seznamu?
Prva stvar, ki se imenuje beseda, je za ime osebe.
DOLŽINA, domnevno nanaša na največjo dolžino imena človekova je,
karkoli že to je, 20, 30, 40 znakov v norih primerih kotiček,
in 1 je za kaj? To je samo dodatno NULL znak, \ 0.
Torej, to vozlišče je zavijanje "nekaj" znotraj samega sebe,
pa tudi izjavlja, kazalec, imenovan Naslednja
tako da bomo lahko veriga Alice, da Bob s Charlijem in tako naprej.
More biti nič, vendar ni nujno, da je.
Vsa vprašanja v zvezi s temi hash tabele? Ja?
[Student sprašuje vprašanje, nerazumljiv] matrika - dobro vprašanje.
Zakaj je to znak beseda v polju in ne samo char *?
V tem primeru nekoliko arbitrarno, nisem hotel, da zateči
za knjižnične funkcije malloc za izvirnih imen.
Želel sem jo razglaša za največjo količino pomnilnika za niz
tako da sem lahko kopirate v strukturi Alice \ 0 in ni treba ukvarjati z knjižnične funkcije malloc in brezplačno in podobnega.
Vendar pa bi to naredil, če sem hotel biti bolj dovzetni za uporabo prostora. Dobro vprašanje.
Torej poskusimo posploševati od tega
in se osredotočiti na preostalem danes na podatkovne strukture bolj na splošno
in druge težave, ki jih lahko rešujemo z uporabo istih temeljih
čeprav so podatkovne strukture lahko sami razlikujejo v svojih podatkov.
>> Tako se izkaže, računalništva, drevesa so zelo pogosti.
In lahko si misliš drevesa vrste kot družinsko drevo,
kjer je nekaj korenine, nekatere matriarch ali patriarh,
babica ali dedek ali prej nazaj,
pod katero se mama in oče ali različne bratje in sestre ali podobno.
Tako drevo struktura vozlišč in ima otroke,
ponavadi 0 ali več otrok, za vsako vozlišče.
In nekaj žargona, ki jih vidite na sliki here
je katera koli majhni otroci ali vnuki, na obrobju
ki nima puščice, ki izhajajo iz njih,
to so tako imenovane liste, in kdorkoli v notranjosti
je notranja vozlišča, ki jih lahko imenujemo tudi kaj podobnega.
Toda ta struktura je precej pogosta. Ta je malce arbitraren.
Imamo enega otroka na levi, imamo tri otroke na desni strani,
dva otroka na dnu levo.
Tako imamo lahko različnih velikosti drevesa, ampak če bomo začeli standardizirati stvari,
in morda spomnite iz tega videa Patrika na binarnem iskanju od prejšnje kratek
spletu, binarno iskanje ni treba izvajati z vrsto
ali kos papirja na tabli.
Recimo, da ste želeli za shranjevanje številk na bolj prefinjeno strukturo podatkov.
Lahko ustvarite drevo, kot je ta.
Lahko bi vozlišče prijavljeni v C, in da vozlišče lahko vsaj dva elementa v njej.
Eno je številka, ki jo želite shraniti, in drugi je - no, potrebujemo še eno.
Drugi so njeni otroci.
Torej, tukaj je še en struktura podatkov. Tokrat je vozlišče opredeljena kot shranjevanje število n
in potem 2 kazalci, levo in desno otrok otrok.
In oni ne samovoljno. Kaj je zanimivo to drevo?
>> Kaj je vzorec, kako smo iz tega, oziroma kako Patrick je določeno v svojem videu?
To je nekako jasno, da obstaja nekaj sortiranje dogaja,
kaj pa je preprosto pravilo? Ja?
[Student odgovor, nerazumljiv]
Popolno. Če pogledam v to, boste videli majhno število na levi strani,
velike številke na levi strani, ampak to velja za vsako vozlišče.
Za vsako vozlišče, njena leva otrok, mlajši od nje, in njena pravica otrok večji od njega.
Kaj to pomeni, je zdaj, če želim iskati to podatkovno strukturo, na primer, je število 44,
Moram začeti pri korenu, saj je pri vseh teh bolj kompleksnih podatkovnih struktur zdaj,
imamo le kazalec na eno stvar, začetek.
In v tem primeru, je začetek korenine. Ne levi konec,
da je vzrok za to strukturo. Vidim, tukaj je 55, in iščem 44.
V katero smer ne želim iti?
No, rad bi šel na levo, saj je očitno, da pravica se bo prevelika.
Torej, opazil sem, da si nekako konceptualno sekanje drevesa na pol
ker nikoli ne boš dol na desni strani.
Zdaj sem šel od 55 do 33 let. To je premajhen števila.
Iščem 44, zdaj pa vem, če je 44 je v tem drevesu, grem lahko seveda na desni.
Torej, še enkrat, jaz sem obrezovanje drevo na polovico.
To je precej enak pojmovni v imenik.
To je enako, kar smo naredili z dokumenti na tabli,
ampak to je bolj prefinjena struktura, ki nam omogoča, da dejansko ne
To deli in vladaj z zasnovo algoritma,
in v resnici, vozijo strukturo, kot je ta - Ops.
Vozijo strukturo, kot je ta, če je to le "gredo v to smer, ali iti v to smer,"
pomeni vse to kodo, ki sklonil vaš um najprej pri njenem izvajanju v oddelku
ali hojo po njej doma, za binarno iskanje, z uporabo rekurzije ali ponovitvi
to je bolečina v vratu. Najdi srednji element, naredite svojo zaokroži navzgor ali navzdol.
>> Tukaj je lepota tega, ker se lahko sedaj uporablja rekurzijo spet,
vendar veliko bolj čisto. Pravzaprav, če ste na številko 55 in si želim, da bi našli 44,
greš levo v tem primeru, kaj bi vi naredili? Ti vodijo natančno enak algoritem.
Ti preveri vrednost vozlišča, potem greš levo ali desno.
Potem pa preveri vrednost vozlišča, pojdite levo ali desno.
To je idealno za rekurzije.
Torej, čeprav je v preteklosti smo naredili nekaj precej samovoljno primere, ki vključujejo rekurzijo
da ni treba rekurzivno s podatki stuctures,
predvsem drevesa, to je popolna uporaba te ideje ob težave,
to zmanjšuje, nato pa reševanje iste vrste, vendar manjše, program.
>> Torej obstaja še druga struktura podatkov, ki jih lahko predstavimo.
Ta je zasnovan na prvi pogled videti, da skrivnosten, ampak tale je neverjetno.
Torej, to je struktura podatkov, ki se imenuje Trie, Trie, ki se deduje iz besede nalaganju
ki se ne izgovarja ponovno poskusite-val, ampak to je tisto, kar svet imenuje te stvari. Poskuša. T-r-i-e.
To je drevesna struktura neke vrste, ampak vsak od vozlišč v Trie
Zdi se, da kaj? In to je malce zavajajoče, ker je vrsta krajša.
Ampak izgleda, da vsako vozlišče v tem Trie je pravzaprav polje.
In čeprav je avtor tega diagrama ne prikaže,
v tem primeru je to Trie je podatkovna struktura, katere namen v življenju je, da shranite besede
kot a-L-i-C-E ali B-o-b.
In način, na katerega so ti podatki prodajalne Alice in Bob in Charlie in Anita in tako naprej
se uporablja za shranjevanje niz, s katerim Alice v Trie,
začnemo na korenski vozel, ki izgleda kot matriko,
in je bilo napisano v zapisu bljižnica.
Avtor izpusti ABCDEFG, ker ni bilo imen s tem.
So pokazali le, M in P in T, vendar v tem primeru,
pojdimo stran od Alice in Bob in Charlija nekaterih imen, ki so tukaj.
Maxwell je pravzaprav v tem diagramu.
Torej, kako si avtorja trgovino M--x-w-e-l-l?
On ali ona se je začela v korensko vozlišče, in odšel v [M], tako da približno 13, 13. mesto v polje.
Potem od tam, tam je kazalec.
Kazalec vodi v drugo polje.
Od tam avtor indeksirana v tem polju na lokaciji A, kot je prikazano tam zgoraj levo,
in potem on ali ona sledi, da je kazalec na drugo polje,
in odšel na kazalec na lokaciji X.
Potem pa v naslednjem mestu matrike W, E, L, L, in tako naprej,
in končno, kaj je dejansko poskuša postaviti sliko na to.
Kaj vozlišče izgledal v kodi?
Vozlišče v Trie vsebuje niz kazalcev za več vozlišč.
Vendar pa je tudi dobil, da je neke vrste logično vrednost, vsaj v tem izvajanju.
Jaz mislim, da ga pokličete is_word. Zakaj?
Ker, ko ste vstavljanju Maxwell, ti ne vstavite
kaj v to strukturo podatkov.
Saj ne bi pisal M. Saj ne bi pisal X.
Vse kar počnete, je po kazalca.
Kazalec, ki predstavlja M, potem je kazalec, ki predstavlja,
Nato kazalec, ki predstavlja X, nato W, E, L, L,
ampak kaj morate storiti, na koncu je nekako gre, preverite, sem dosegel to mesto.
Prišlo je beseda, ki se konča tukaj v podatkovni strukturi.
>> Torej, kaj je res poln Trie in je avtor odločil za zastopanje
ti terminuses z malo trikotnikov.
To samo pomeni, da je dejstvo, ta trikotnik je tu, ta logična vrednost velja
pomeni, da če greš nazaj v drevesu
to pomeni, da besede, imenovano Maxwell je v tem.
Toda beseda foo, na primer,
ni v drevesu, ker če začnem na korenski vozel gor na vrhu,
Ni f kazalec, kazalec ne o, ne o kazalec. Foo ni ime na tem slovarju.
Toda po drugi strani prestrukturiranje, t-u-r-i-n-g. Še enkrat, nisem shranjevanje t ali u ali R ali I ali N ali g.
Ampak sem trgovino v to strukturo podatkov vrednost prave poti navzdol tu v tem vozlišču - v drevesu
z nastavitvijo tega boolean vrednost is_word, da res.
Torej, Trie je nekako to zelo zanimivo strukturo meta,
če niste zares shranjevanje besede, se za tovrstno slovarju.
Da bo jasno, da si samo hranjenje z da ali ne, je beseda, ki se konča tukaj.
>> Zdaj, kaj je posledice?
Če imate 150.000 besed iz slovarja, ki ga poskušate shraniti v pomnilnik
nekako takole: povezan seznam,
boste imeli 150.000 vozlišč v vašem povezani seznam.
In lahko najti eno od teh besed po abecedi, da O (n) časa.
Linearni čas. Toda v tem primeru za Trie,
kaj teče čas za iskanje besedo?
Izkazalo se je, lepoto, tukaj je, da tudi, če imate 149.999 besed, ki so že v tem slovarju,
kot je bil izveden s to strukturo podatkov,
koliko časa traja, da najdejo ali vstavite še eno osebo, ki v to, kot je Alice, Alice?
No, to je le 5, morda 6 korakov za zaključnimi značaja.
Ker presense drugih imen v strukturi
ne v napoto, da vstavite Alice.
Poleg tega je ugotovil, Alice, ko je 150.000 besed v tem slovarju
ne v napoto pri iskanju Alice sploh,
ker je Alice. . . . . tukaj, ker sem ugotovila, boolean vrednost.
In če ni logična res, potem Alice ni v tem strukturo podatkov besed.
Z drugimi besedami, čas delovanja za odkrivanje stvari in vstavljanje stvari v novi
Podatki struktura Trie je od O - to ni n.
Ker presense 150.000 ljudi nima vpliva na Alice, se mi zdi.
Torej, recimo, da k, kjer je k največja dolžina v angleškem jeziku
ki je ponavadi ni več kot 20-nekaj znakov.
Torej, k je konstanta. Torej svetega grala zdi, da smo zdaj ugotovljeno,
je, da je za Trie, stalno časa za vložke, za poizvedbe za brisanje.
Ker je število stvari, ki so že v strukturi,
ki sploh niso fizično tam. Še enkrat, ti si samo nekako odkljukali, da ali ne,
nima nobenega vpliva na prihodnji teče čas.
>> Vendar pa ima za ulov, sicer se ne bi zapravili toliko časa
o vseh teh drugih podatkovnih struktur, samo da na koncu pridemo do tajnih eno, ki je neverjetno.
Torej, kakšno ceno plačujemo za dosego tega veličino tukaj? Vesolje.
Ta stvar je ogromen. In razlog, da avtor
ni ga tukaj predstavljamo, opazili, da se vse te stvari, ki izgledajo kot nizi,
da ni sprejela ostalo na drevesu, ostali v Trie,
ker oni niso pomembni le za zgodbo.
Toda vse te vozle so super širok in vsak vozlišče v drevesu prevzame
26 ali dejansko, je lahko 27 znakov, ker v tem primeru sem bil tudi prostor za opuščajem
Tako bi lahko, da imamo apostrophized besede.
V tem primeru gre za velike nizi. Torej, čeprav oni ne picutured,
To zavzema ogromno količino RAM-a.
Ki bi bilo v redu, especilly v sodobni strojni opremi,
ampak to je kompromis. Smo dobili manj časa, ki ga porabi več prostora.
Torej, če je vse to dogaja?
No, dajmo narediti - kaj je tu za videti.
Naredimo skok tega tipa tukaj.
>> Verjeli ali ne, tako zabavno kot je C že nekaj časa,
smo dosegli točko, na polovici, kjer je čas za prehod na bolj modernih stvari.
Stvari na višji ravni. In čeprav za naslednjih nekaj tednov
bomo še naprej se bomo potopite v svet kazalcev in upravljanje pomnilnika
da se da udobno, s katerimi bomo lahko potem gradi naprej,
Konec igre je končno uvesti, ironično, ne ta jezik.
Bomo preživeli kot 10 minut govorijo o HTML.
Vse HTML je označevalni jezik, in kaj je označevalni jezik
je ta vrsta odprtih in zaprtih nosilci nosilci, ki pravijo, da "bi to krepko"
"Naj bo to poševnem tisku" "bo to sredino."
To pa še ni vse, da je intelektualno zanimiva, vendar je to zelo koristno.
In to je zagotovo povsod prisoten v teh dneh.
Toda kaj je močna o svetu HTML in spletno programiranje na splošno
gradi dinamične stvari, pisanje kode v jezikih, kot so PHP ali Python ali Ruby in Java ali C #.
Res, ne glede na vaš jezik izbire je in ustvarja HTML dinamično.
Ustvarjanje nekaj, kar ti CSS dinamično.
Cascading Style Sheets, ki je prav tako stvar estetike.
In tako, čeprav je danes, če grem na neki spletni strani, kot je znano Google.com,
in grem na ogled, razvijalec, pogled na vir, ki ste morda storili prej,
vendar pa bo za ogled vira, te stvari najbrž izgleda precej skrivnosten.
Ampak to je osnovno kodo, ki izvaja Google.com.
Na sprednjem koncu. In dejansko je vse to puhasto estetika stvari.
To je CSS tukaj. Če sem pomikajo navzdol bomo dobili nekaj barvnih kod stvari.
To je HTML. Koda Googlov izgleda kot zmešnjavo, ampak če bi dejansko odprl drugo okno,
smo lahko videli nekaj strukturo za to.
Če odprem tole, opazil sem, da je malo bolj berljiva.
Bomo videli kmalu to oznako, [beseda] je oznaka,
HTML, glava, telo, div, scenarij, besedilo območja, razpon, sredina, div.
In to je tudi nekako skrivnosten usmerjena na prvi pogled
ampak vse to zmešnjavo sledi določenim vzorcem in ponovljive vzorce,
tako da, ko smo dobili osnove navzdol, boste lahko, da napišete kodo, kot je ta
in potem manipulirati kodo, kot je ta z uporabo še enega jezika, ki se imenuje JavaScript.
In JavaScript je jezik, ki deluje znotraj brskalnika
danes, da bomo uporabili na Harvard tečajev, za orodje seveda nakupovanje, da Google maps uporablja
da vam cel kup dinamiko, Facebook vam daje prikaz takojšnje podatke o stanju,
Twitter ga uporablja, da vam pokažem tweets takoj.
Vse to bomo začeli sami potopi palca
Ampak do tja, moramo razumeti nekaj o internetu.
Ta posnetek sem le minuto časa, in predpostavimo, za zdaj je to v resnici,
kako internet deluje kot teaser za kaj kmalu prišel. Dam ti "Warriors mreže."
>> [♫ ♫ Slow zbor glasbene]
[Moški pripovedovalec] je prišel s sporočilom.
S protokolom vse svoje lastne.
[♫ ♫ Hitrejše elektronske glasbe]
Prišel je na svet kul požarni zidovi, usmerjevalniki neskrbni,
in nevarnosti, če huje kot smrt.
On je hiter. On je močan. On je TCP / IP, in je dobil svoj naslov.
Bojevniki mreže.
[Malan] Naslednji teden, potem. Internet. Spletno programiranje. To je CS50.
[CS50.TV]