[Powered by Google Translate] [6. nädalal Jätkub]
[David J. Malan] [Harvardi Ülikool]
[See on CS50.] [CS50.TV]
See on CS50 ja see on lõpuks 6. nädal.
Nii CS50x, üks Harvardi esimest kursust kaasatud EDX algatus
tõepoolest debüteeris möödunud esmaspäeval.
Kui soovite saada pilguheit mida teised Internetis
nüüd pärast koos, saate pea x.cs50.net.
See suunab teid sobiva koha edx.org,
mis oli, kus see ja teine ​​kursust MIT ja Berkeley nüüd elame.
Sa pead sisse logida konto, leiad, et see materjal on üldjoontes sama
kui teil on olnud see semester, kuigi paar nädalat edasi lükata, kui saame kõik valmis.
Aga mida õpilased CS50x kuvatakse nüüd on liides, täiesti nagu see üks.
See näiteks on Zamyla viib läbikäiguks jaoks probleem komplekt 0.
Pärast sisselogimist edx.org, CS50x õpilane näeb asjadele
ootate näha muidugi: loeng esmaspäev,
loeng kolmapäev, erinevate lühikesed püksid, probleem komplekti, walkthroughs, PDF-faile.
Lisaks, nagu näete siin, masintõlge
inglise ärakirju hiina, jaapani, hispaania, itaalia,
ja terve hunnik teisi keeli, et kindlasti ebatäiuslik
nagu me veereta neid programmiliselt kasutades midagi, mida nimetatakse API
või rakenduse programmeerimise liidest, Google
mis võimaldab meil muuta inglise nendele teistes keeltes.
Kuid tänu imeline vaimus paarisaja-pluss vabatahtlikega
juhuslik inimesed internetis, kes on lahkelt pakutakse kaasa lööma
selles projektis, siis me järk-järgult kvaliteedi parandamise need tõlked
lastes inimestel parandada vigu, et meie arvutid on tehtud.
>> Nii selgub olime veel mõned õpilased näitavad üles esmaspäeval kui me algselt lootsime.
Tegelikult nüüd CS50x on 100.000 inimest pärast mööda kodus.
Nii mõistad, sa on kõik osa sellest avaistung klassi muuta see muidugi infotehnoloogia
haridus üldisemalt laiemalt kättesaadav.
Ja reaalsus on nüüd, kusjuures mõned neist tohutu online kursused,
nad kõik algab järgmiste väga suurtes kogustes, sest näib, et oleme siin teinud.
Aga eesmärk lõpuks selleni, et CS50x on tõesti saada nii palju inimesi finišijoone kui võimalik.
Autor disain, CS50x läheb antakse alates möödunud esmaspäev
kõik teed läbi 15 aprill 2013, nii et inimesed, kes on kooli kohustused mujal
töö, pere, muud konfliktid jms, on veidi rohkem paindlikkust
kellega siis sukelduda sellesse muidugi, mis piisab, kui öelda,
on üsna ambitsioonikalt teha, kui ainult jooksul vaid kolm kuud ajal tavaline poolaastal.
Aga need õpilased on võidelda sama probleem komplekti, vaatamise sama sisu,
kellel on juurdepääs sama lühikesed püksid jms.
Nii mõistame, et me kõik oleme tõesti selles koos.
Ja üks lõppeesmärgid CS50x ei ole lihtsalt saada nii palju toredaid inimesi
kuni finišijoone ja anda neile seda taasleitud arusaam infotehnoloogia
ja programmide, vaid ka lasta on see jagatud kogemus.
Üks omaduste määratlemise 50 loengusse, loodame,
on olnud selline ühiskondlik kogemus, hea või halb, mõnikord,
kuid võttes need inimesed pöörduvad vasakule ja paremale,
ja tööajal ja hackathon ja õiglane.
See on natuke raskem teha, et inimene inimesed online,
kuid CS50x lõppeb aprillis esmakordselt CS50 Expo,
mis on internetis kohandamine meie idee õiglane
kus need tuhanded õpilased kogu palutakse esitada 1 - kuni 2-minutilise video,
kas kaadrid oma lõpliku projekti või video neist viipab tere
ja räägi oma projekti ja demoing see,
palju nagu teie eelkäijad on teinud siin ülikoolilinnakus õiglane,
nii et semestri lõpus, lootus on luua ülemaailmne näitus
Euroopa CS50x õpilaste lõplik projekte, meelega, mis ootab sind selle aasta detsembris siin ülikooli.
Nii et rohkem, et lähikuudel.
>> Mis 100000 üliõpilastele, aga tekib vajadus veel mõned pädevad asutused.
Arvestades, et kutid on lõõskav rada siin ja võttes CS50
mitu nädalat enne seda materjali sattumist inimesed edasi EDX,
realiseerida oleks tore kaasata võimalikult palju oma õpilastele kui võimalik selles algatuses
nii poolaastal samuti sel talvel ja tuleval kevadel.
Nii et kui soovid kaasa lüüa CS50x,
eriti ühineda sisse CS50x arutada, EDX versioon CS50 arutada
mis paljud teist on kasutanud loengusse, online teadetetahvel,
palun tehke pea et link, andke teada, kes sa oled,
sest meile meeldiks ehitada meeskond õpilased ja töötajad ja õppejõud nii
ülikoolilinnakus, kes lihtsalt mängivad kaasa ja aitasid.
Ja kui nad näevad küsimus, mis on tuttav neile,
kuulete õpilane aru mõned bug kuskil seal mõnes riigis Internetis
ja et rõngad kelluke, sest sa liiga oli sama teema
oma d-hallis mõni aeg tagasi, loodetavasti siis saate Säestää ja jagada oma kogemusi.
Nii et palun ärge osalema, kui soovid.
>> Informaatika kursuste Harvardi on natuke traditsioon,
CS50 nende seas, kellel oli ka rõivad, mõned riided, mida saab kanda uhkelt
kell semestri lõppu, öeldes üsna uhkelt, et oled lõpetanud CS50
ja võttis CS50 jms, ja me püüame alati kaasata üliõpilasi
Selle protsessi nii palju kui võimalik, mille kutsume,
umbes sel ajal poolaastal, õpilased esitada kujunduse
kasutades Photoshop, või mis iganes soositud soovite kasutada
kui sa oled disainer, esitama kujundused T-särgid ja dressipluusid
ja vihmavarjud ja vähe bandanas koertele on meil nüüd jms.
Ja kõik on siis - võitjate igal aastal on siis eksponeeritud
rajal veebilehel store.cs50.net.
Kõik on müüdud soetusmaksumuses olemas, kuid kodulehel lihtsalt jookseb ise
ja võimaldab inimestel valida värve ja disaine, mis neile meeldib.
Nii et ma arvasin, et me lihtsalt jagada mõningaid eelmisel aastal kujunduse
mis olid veebilehel peale selle ühe siin, mis on iga-aastane traditsioon.
"Iga päev ma olen Seg Faultn" oli ühes vastuses eelmisel aastal
mis on kättesaadav seal vilistlased.
Meil oli see üks, "CS50, Asutatud 1989."
Üks meie Bowdens, Rob, oli väga populaarne eelmisel aastal.
"Meeskond Bowden" sündis, see disain esitati seas top müüjad.
Nagu oli see siin. Paljud inimesed olid "Bowden Fever" vastavalt müügi logisid.
Aru, et see võiks nüüd olla oma disaini seal üleval internetis.
Täpsemat infot selle kohta järgmise probleem seab tulla.
>> Veel üks tööriist: teil on olnud mõned kokkupuute ja loodetavasti nüüd
mõned praktilisi kogemusi koos GDB,
mis on muidugi siluri ning võimaldab teil manipuleerida
oma programmi üsna madalal tasemel, tehes milliseid asju?
Mis GDB lase sul teha?
Jah? Anna mulle midagi. [Student vastus, arusaamatult]
Hea. Astu funktsioon, et sa ei lihtsalt tüüp joosta
ja on programm löök läbi tervikuna, väljatrükk asjad standardväljundisse.
Pigem saab astuda läbi rida-realt, kas kirjutades kõrval
minna rida rea ​​kaupa või samm sukelduda funktsiooni, tavaliselt üks, mis sa kirjutasid.
Mida veel ei GDB lase sul teha? Jah? [Student vastus, arusaamatult]
Prindi muutujad. Nii et kui sa tahad teha vähe enesevaatluse sees oma programmi
ilma et oleks vaja kasutada kirjutamise printf avaldusi üle kogu koht,
Sa võid printida muutuja või kuvada muutuja.
Mida saab teha siluri nagu GDB?
[Student vastus, arusaamatult]
Täpselt. Saate määrata murdepunktid; võite öelda pausi täitmine
kell põhiülesanne või suva funktsioon.
Võite öelda pausi täitmine real 123.
Ja murdepunktid on tõesti võimas tehnika
sest kui sul on üldises mõttes kui sinu probleem
ilmselt on, sa ei pea aega raiskama astutakse läbi programmi tervikuna.
Võite sisuliselt hüpata seal ja siis alustage tippimist -
astutakse läbi see samm või järgmisel vms.
Aga saak koos midagi GDB on see, et see teid aitab, inimeste,
leida oma probleeme ja leida oma vigu.
See ei pruugi tingimata leida neid nii palju teile.
>> Nii et me tutvustas teisel päeval style50, mis on lühikese käsureatööriist
mis üritab Tyylitellä oma koodi veidi puhtamalt kui sina, inimene, võib-olla teha.
Aga see, liiga, on tõesti ainult esteetiline asi.
Aga selgub seal on see teine ​​tööriist nimega Valgrind, mis on veidi rohkem keerulisse kasutada.
Selle tulemused on atrociously segasena esimesel pilgul.
Aga see on imeliselt kasulik, eriti nüüd, kui me oleme osa mõiste
kus sa oled hakanud kasutama malloc ja dünaamiline mälu eraldamisel.
Asjad võivad minna väga, väga vale kiiresti.
Sest kui te unustate tasuta oma mälu, või sa dereference mõned NULL pointer,
või sa dereference mõned prügi osuti, mis on tavaliselt sümptom, et tulemused?
Seg süü. Ja sa saad selle tuum faili teatud arvu kilobaiti või megabaiti
et esindab riiki oma programmi mällu kui see alla kukkus,
kuid oma programmi lõpuks seg vead, killustatust süü,
mis tähendab midagi halba juhtunud peaaegu alati seotud
et mälu seotud viga, mis sa tegid kuskil.
Nii Valgrind aitab teil leida selliseid asju.
See on vahend, et sa jooksed, nagu GDB, kui olete koostanud oma programmi,
kuid mitte käivitada oma programmi otse, sa jooksed Valgrind
ja te kaotate seda oma programmi, nagu te teete GDB.
Nüüd kasutamine, et saada parim liiki toodangut,
on veidi pikk, nii et seal atop ekraani näed Valgrind-v.
"-V" peaaegu universaalselt tähendab verbose kui te kasutate programme Linuxi arvuti.
Nii et see tähendab sülitama rohkem andmeid kui võite vaikimisi.
"- Lekke-check = täis." See on lihtsalt öeldes kontroll kõigi võimalike mälu lekked,
vigu, mida ma oleks võinud teha. Ka see on ühine paradigma Linux programmid.
Üldiselt, kui sul on käsurea argument see "lüliti",
See peaks muutma programmi käitumine, ja see on üks täht,
see-V, kuid kui see on sisse lülitatud, lihtsalt disain programmeerija,
on terve sõna või mitu sõna, käsurea argument algab -.
Need on vaid inimese konventsioonid, aga näete neid järjest.
Ja siis lõpuks, "a.out" on meelevaldne nimi programm sellel konkreetsel juhul.
Ja siin on mõned esindaja väljund.
>> Enne vaatame, mida see võiks tähendada, lase mul minna üle koodilõik siin.
Ja lubage mul liigutada välja viis, varsti,
ja võtame pilk memory.c, mis on selle lühikese näiteks siin.
Nii et selles programmis, las ma suumida ülesanded ja küsimused.
Meil on funktsiooni main, mis nõuab funktsiooni, f,
ja siis mida see f edasi teha, pisut tehnilist inglise keelt?
Mis f edasi teha?
Kuidas ma alustan rida 20 ja tähtede asukohta ei ole oluline,
kuid ma lihtsalt olla järjekindel siin viimane loeng.
Mis rida 20 teha meie jaoks? Vasakul küljel. Me jaotada see veelgi.
Int * x: mida see teeb?
Okei. See kuulutab pointer, ja nüüd olgem veelgi tehniline.
Mis see tähendab, väga konkreetselt, kuulutada pointer? Keegi teine?
Jah? [Student vastus, arusaamatult] Liiga kaugele.
Nii et sa loed paremal servas võrdusmärk.
Olgem keskenduda ainult vasakul, just int * x.
See "kuulutab" pointer, kuid nüüd olgem sukelduda sügavamale sellele.
Mida see konkreetselt, tehniliselt tähendab? Jah?
[Student vastus, arusaamatult]
Okei. See valmistab säästa aadress mällu.
Hea. Ja võtame selle ühe sammu edasi, see on, mis kuulutab muutuja x, mis on 32 bitti.
Ja ma tean, et see 32 bitti, sest -?
See ei ole, sest see on keskmine, sest see on osuti käesoleval juhul.
Juhus, et see on üks ja sama int,
kuid asjaolu, et seal on täht seal tähendab see pointer
ja aparaat, nagu paljude arvutitega, kuid mitte kõik, osuti on 32 bitti.
On moodsam riist nagu viimased Mac, hiljemalt arvutid, mida oleks võinud 64-bitine suunanäitajaks,
kuid seadme, need asjad on 32 bitti.
Nii et me ühtlustada selle kohta. Täpsemalt räägitakse järgmiselt:
Me "kuulutab" osuti; mida see tähendab?
Valmistame salvestada mälu aadressi.
Mida see tähendab?
Loome muutuja nimega x, et kulub 32 bitti
et varsti salvestada aadress täisarv.
Ja see on ilmselt umbes sama täpne kui saame.
See on hea edasi liikuda lihtsustada maailma ja lihtsalt öelda kuulutada osuti nimetatakse x.
Tuvastada pointer, kuid aru ja mõista, mis tegelikult toimub
isegi lihtsalt need paar tähte.
>> Nüüd, see on peaaegu veidi lihtsam, kuigi see on pikem väljend.
Mis siis on see tee, mis on esile tõstetud nüüd: "malloc (10 * sizeof (int));" Jah?
[Student vastus, arusaamatult]
Hea. Ja ma võtan selle sealt. See eraldamise patakas mälu kümme täisarvud.
Ja nüüd sukelduda pisut sügavamale, see on eraldamise patakas mälu kümme täisarvud.
Mis on malloc siis tagasi?
Aadress, et patakas, või, konkreetsemalt, aadress esimese baidi et patakas.
Kuidas siis olen mina, programmeerija, et tean, kus see patakas mälu otsas?
Ma tean, et see on piirnevad. Malloc määratluse järgi annab sulle külgnevas patakas mälu.
Ei lüngad ta. Teil on juurdepääs iga bait selles patakas,
tagasi seljad, aga kuidas ma tean, kus lõpuks selle tüki mälu on?
Kui kasutate malloc? [Student vastus, arusaamatult] Hea.
Sa ei tee seda. Te peate meeles pidama.
Mul on meeles pidada, et ma kasutasin väärtus 10 ja ma isegi ei tundu olevat teinud, et siin.
Aga lasub täielikult mulle. Strlen, mis me oleme saanud veidi sõltuv keelpillidele,
töötab ainult tänu sellele konventsioonile võttes \ 0
või see eriline nul iseloomu, NUL, lõpus stringi.
See ei kehti aga lihtsalt suvalise mäluhulka.
See on kuni teile. Nii et liin 20, siis jaotab patakas mälu
et saab salvestada 10 täisarvud, samuti salvestab aadress esimene bait
Selle tüki mälu muutuja nimega x.
Ergo, mis on osuti. Nii et liin 21, kahjuks oli viga.
Aga kõigepealt, mida ta teeb? See ütleb poe asukoht 10, 0 indekseeritud,
on patakas mälu nimetatakse x väärtus 0.
>> Nii märkate paar asja on pooleli.
Isegi x on pointer, mäletate paar nädalat tagasi
et saate siiski kasutada massiivi stiilis nurksulg märke.
Sest see on tegelikult lühiajaline küljest märke rohkem segasena suunatud pointer aritmeetika.
kus me teeks midagi sellist: Võtke aadress x, liikuda 10 laigud üle,
siis sinna minna, et mis iganes aadress salvestatakse selles kohas.
Aga ausalt öeldes, see on lihtsalt jõle lugeda ja saada rahul.
Nii et maailm kasutab tavaliselt nurksulgudesse lihtsalt seetõttu, et nii palju inim-sõbralik lugeda.
Aga see, mis tegelikult toimub all kapuuts;
x on aadress, mitte massiiv, iseenesest.
Nii et see on hoidmiseks 0. asukohta 10 x.
Miks on see halb? Jah?
[Student vastus, arusaamatult] Täpselt.
Me ainult eraldatud 10 ints, kuid me loota 0 kui Programmeerimine C,
nii et teil on juurdepääs 0 1 2 3 4 5 6 7 8 9, kuid mitte 10.
Nii et kas programm läheb SEG süü või see ei ole.
Aga me ei tea, see on omamoodi mittedetermineeritud käitumist.
On tõesti sõltub, kas meil veab.
Kui selgub, et operatsioonisüsteem ei pahanda, kui ma kasutan seda pildi bait,
kuigi see pole andnud seda mulle, mu programm ei pruugi krahhi.
See on toores, see on lollakas, aga sa ei pruugi näha, et sümptom,
või võite näha seda ainult üks kord samal ajal.
Kuid reaalsus on see, et viga on tegelikult olemas.
Ja see on tõesti problemaatiline, kui olete kirjutanud programmi, mis sa tahad olla õige,
et olete müünud ​​programm, et inimesed kasutavad, et iga kord samal ajal jookseb
sest muidugi, see ei ole hea. Tegelikult, kui sul on Android telefon või iPhone
ja sa alla laadida apps nendel päevadel, kui sa oled kunagi olnud app lihtsalt loobuda,
äkki kaob see, mis on peaaegu alati tingitud mõnede mälu seotud probleem,
kusjuures programmeerija silmamunad ja dereferenced pointer
et ta ei peaks, ja tulemus iOS või Android on lihtsalt tappa programmi kokku
mitte riski määratlemata käitumine või mingi turvalisuse kompromiss.
>> On veel üks viga selles programmis peale selle ühe.
Mida muud ma olen silmamunad selle programmiga?
Ma ei ole harjutanud mida ma olen kuulutanud. Jah?
[Student vastus, arusaamatult] Hea.
Ma ei ole vabanenud mälu. Nii rusikareegel nüüd
peab olema millal helistada malloc, peate helistama tasuta, kui olete teinud kasutades, et mälu.
Nüüd, kui ma tahan, et vabastada see mälu?
Tõenäoliselt, eeldades see esimene rida oli õige, ma tahan seda teha siin.
Sest ma ei saanud näiteks seda siin all. Miks?
Lihtsalt välja ulatus. Nii et kuigi me räägime suunanäitajaks,
See on nädal 2 või 3 küsimust, kus x on ainult ulatuse sees looksulg kus see on deklareeritud.
Nii et sa kindlasti ei saa vabastada seal. Minu ainus võimalus vabastada see on umbes pärast rida 21.
See on üsna lihtne programm, see oli üsna lihtne, kui sa selline pakitud meelt
ümber, mida programm teeb, kus vigu.
Ja isegi kui sa ei näinud seda alguses, loodetavasti see on natuke ilmne nüüd
et need vead on üsna lihtne lahendada ja lihtne teha.
Aga kui programm on rohkem kui 12 rida pikk, see on 50 rida pikk, 100 rida pikk,
jalgsi läbi oma koodi rida realt, läbi mõelda loogiliselt,
on võimalik, kuid mitte eriti lõbus teha, pidevalt otsivad vigu,
ja see on ka raske teha, ja sellepärast tööriista nagu Valgrind olemas.
Lubage mul minna ja teha nii: lase mul avada minu terminaliakent,
ja andke mulle mitte lihtsalt käivitada mälu, sest mälu pole midagi viga.
Ma saan õnnelik. Lähen, et täiendav baidi lõpus massiivi
ei tundu olevat liiga problemaatiline.
Aga las ma siiski, teha meelerahu kontroll, mis tähendab lihtsalt, et kontrollida
kas see on tegelikult õige.
>> Teeme valgrind-V - lekke-check = täis,
ja siis programmi nimi on sel juhul mälu, ei a.out.
Nii et lubage mul minna ja seda teha. Enter.
Kallis Jumal. See on oma toodang ja seda ma viitas varem.
Aga kui sa õpid, et lugeda läbi kõik jama siin,
enamus sellest on lihtsalt diagnostika väljund, et ei ole nii huvitav.
Mis silma tahab otsivad on üldse mainimata viga või kehtetu.
Sõnad, mis viitavad probleemidele.
Ja tõepoolest, vaatame mis toimub vale siin.
Mul on kokkuvõte mingi "kasutusel väljumise: 40 baiti 1 plokke."
Ma ei ole tegelikult kindel, mida plokk on veel, kuid 40 baiti
tegelikult tundub, nagu ma võiks aru saada, kus see on pärit.
40 baiti. Miks on 40 baiti kasutusel väljumise?
Ja täpsemalt, kui me keri siin,
miks ma kindlasti kaotanud 40 baiti? Jah?
[Student vastus, arusaamatult] Perfect. Jah, täpselt.
Seal oli 10 täisarvud ja kõik need on suurus 4, või 32 bitti,
nii et ma kaotasin just 40 baiti, sest nagu sa ettepanek, ma ei ole kutsutud tasuta.
See on üks viga, ja nüüd vaatame allapoole veel veidi ja vaata kõrval see,
"Vigane kirjutame suurus 4". Nüüd mis see on?
See aadress on väljendatud mida baasi märke, ilmselt?
See on kuueteistkümnendsüsteemis, ja iga kord, kui näen mitmeid alustades 0x,
see tähendab kuueteistkümnendsüsteemi, mis me tegime nii tagasi, ma arvan, pset 0-osa küsimused,
mis oli lihtsalt teha soojendus liikumine, teisendades koma Hex kahekomponentsete jne.
Kuueteistkümnendsüsteemi, lihtsalt inimeste konventsiooni, mida tavaliselt kasutatakse esindama viiteid
või üldisemalt tegeleb. See on lihtsalt printsiibist,
sest see on natuke lihtsam lugeda, see on veidi kompaktsem kui midagi koma,
ja binaarne on kasutu kõige inimestel kasutada.
Nii et nüüd mida see tähendab? Noh, tundub, et seal on kehtetu kirjutada
suurus 4 rida 21 memory.c.
Nii et lähme tagasi liin 21, ja tõepoolest, siin on see, et vigane kirjutada.
Nii Valgrind ei kavatse täiesti hoidke mu kätt ja ütle mulle, mida fix on
kuid see on avastada, et ma teen vale kirjutada.
Ma puudutan 4 baiti, et ma ei tohiks olla, ja ilmselt ongi, sest,
nagu olete rõhutanud, ma teen [10] asemel [9] maksimaalselt
või [0] või midagi vahepealset.
Mis Valgrind, aru igal ajal sa nüüd kirjutamise programm
mis kasutab viiteid ja kasutab mälu, ja malloc täpsemalt
Kindlasti satuvad harjumus töötab nii kaua
kuid väga kergesti kopeerida ja kleepida käsu Valgrind
et näha, kas seal on mõned vead seal.
Ja see saab olema valdav iga kord näed väljund,
aga lihtsalt sõeluda läbi visuaalselt kogu võimsuse ja vaata, kas näed mainib vigu
või hoiatusi või vigane või kadunud.
Kõik sõnad, mis kõlavad nagu te silmamunad kusagil.
Nii mõistame, et see on uus vahend oma tööriistakomplekti.
>> Nüüd esmaspäeval oli meil terve hunnik inimesed siia tulla
ja esindada mõiste seotud nimekirja.
Ja me tutvustas seotud nimekirja lahendusena mida probleem?
Jah? [Student vastus, arusaamatult] Hea.
Massiivid ei saa mälu lisamist.
Kui te eraldada massiivi suurus 10, see on kõik, mida saan.
Teil on võimalik helistada funktsioon nagu RealLOC kui sa algselt nimega malloc,
ja et võib proovida kasvatada massiivi kui on ruumi lõpu poole see
et keegi teine ​​kasutab, ja kui seal ei ole, siis lihtsalt leida suurem patakas kusagil mujal.
Aga siis kopeerib kõik need baidid uude massiivi.
See kõlab väga õige lahendus.
Miks on see ebameeldiv?
Ma mõtlen see toimib, inimesed on lahendanud selle probleemi.
Miks me peame seda lahendada esmaspäeval seotud nimekirjad? Jah?
[Student vastus, arusaamatult] See võib võtta kaua aega.
Tegelikult igal ajal olete helistaja malloc või RealLOC või calloc, mis on veel teine,
iga kord, kui programm, räägime operatsioonisüsteemi,
siis kipuvad aeglustada programmi alla.
Ja kui sa teed selliseid asju silmad, sa oled tõesti aeglustub asju ette.
Sa ei lähe märgata seda kõige lihtsam "Hello World" tüüpi programme,
aga märksa suuremates programmides, paludes operatsioonisüsteemi ja jälle mälu
või andes talle ikka ja jälle tagasi kipub mitte olema hea.
Plus, see on lihtsalt omamoodi intellektuaalselt - see on täielik ajaraiskamine.
Miks eraldada rohkem ja rohkem mälu, riski kopeerimine kõike uude massiivi
kui teil on alternatiiv, mis võimaldab teil eraldada ainult nii palju mälu sa tegelikult vajad?
Nii et seal on plussid ja miinused siit.
Üks plussid on see, et meil on dünaamilisust.
Vahet pole, kus mäluhulka on, mis on tasuta,
Võin lihtsalt omamoodi luua nende leivapuru kaudu lähtekohtadeks
string kogu mu lingitud nimekiri koos.
Aga ma maksan vähemalt ühe hinnaga.
>> Mida ma pean loobuma omandada seotud nimekirjad?
Jah? [Student vastus, arusaamatult] Hea.
Sa pead rohkem mälu. Nüüd on mul vaja ruumi neid viiteid,
ja juhul, kui see super lihtne seotud nimekirja
et on ainult üritab salvestada täisarvud, mis on 4 baiti, me ütleme
Noh, osuti on 4 baiti, nii et nüüd ma olen sõna otseses mõttes kahekordistunud
mälu mul on vaja lihtsalt hoida seda nimekirja.
Aga jälle, see on pidev Miinuseks infotehnoloogia
vahel ajas ja ruumis ja areng, jõudu ja muid ressursse.
Mis on teine ​​negatiivne külg kasutades seotud loetelu? Jah?
[Student vastus, arusaamatult]
Hea. Ei ole nii lihtne ligi pääseda. Me ei saa enam võimendada
nädal 0 põhimõtteid nagu jaga ja valitse.
Ja täpsemalt, binaarne otsing. Sest kuigi me inimestele
näete jämedalt kus keset seda nimekirja on
arvuti ainult teab, et see on seotud nimekirja algab aadress helistama.
Ja see on 0x123 või midagi sellist.
Ja ainus viis programmi leida keset element
on tegelikult otsida kogu nimekiri.
Ja isegi siis, see sõna on otsida kogu nimekiri, sest
isegi kui jõuad keskel element järgides suunanäitajaks,
te, programmi, ei tea, kui kaua see nimekiri on potentsiaalselt
kuni jõuate lõpuks see, ja kuidas sa tead, programmiliselt
et sa oled lõpus seotud nimekirja?
Seal on spetsiaalne NULL pointer, nii et jällegi konventsiooni.
Selle asemel, et kasutada selle osuti, me kindlasti ei taha ta olla mõne prügi väärtus
juhtides lavalt kuhugi, me tahame seda käe ette, NULL,
nii et meil on see lõpp selles andmestruktuur nii et me teame, kus see lõpeb.
>> Mis siis, kui me tahame muuta seda?
Me tegime kõige selle visuaalselt, ja inimestega,
aga mis siis, kui me tahame teha sisestamist?
Nii esialgses nimekirjas oli 9, 17, 20, 22, 29, 34.
Mis siis, kui me siis tahtsime malloc ruumi number 55, sõlm see,
ja siis me tahame lisada 55 soodusravimite loetellu lihtsalt nagu tegime esmaspäeval?
Kuidas me seda teeme? Noh, Anita tulid ja ta sisuliselt kõndis nimekirja.
Ta alustas esimese osa, siis järgmine, järgmine, järgmine, järgmine, järgmine.
Lõpuks tabas vasakpoolne täiesti alla
ja mõistsin, oh, see on NULL. Mida pointer manipuleerimine vaja teha?
Isik, kes oli lõpuks number 34, mis on vajalik tema vasak käsi tõsta
punkti 55, 55 vaja oma vasaku käe suunaga allapoole tuleb uus NULL terminaator. Valmis.
Päris lihtne lisada 55 arvesse järjestatud nimekirja.
Ja kuidas võiks see välja näeb?
>> Lubage mul minna ja avada mõned koodi näiteks siin.
Avan gedit, ja lubage mul avada kaks faili esimene.
Üks on list1.h, ja lubage mul meelde tuletada, et see oli patakas kood
et me kujutamiseks kasutatakse sõlme.
Sõlm on nii int nimetatakse n ja osuti nimetas tuleva et lihtsalt punkte Järgmine asi nimekirjas.
See on nüüd. H faili. Miks?
Seal on käesoleva konventsiooni, ja me ei ole seda ära tohutu end,
aga inimene, kes kirjutas printf ja muud funktsioonid
kinkis maailmale, kõik need funktsioonid, kirjutades faili nimega stdio.h.
Ja siis on string, ja siis seal on map.h, ja seal on kõik need h failid
et te olete näinud või kasutatud tähtaja jooksul kirjaliku teistele inimestele.
Tavaliselt nendes. H failid on ainsad asjad, nagu typedefs
või deklaratsioonide oma tüüpe või deklaratsioonide konstandid.
Sa ei pane funktsioonid "realisatsioonid päisefaile.
Sa panid selle asemel lihtsalt oma prototüübid.
Paned asjad, mida soovite jagada maailma, mida nad vajavad
selleks, et koguda oma kood. Nii lihtsalt sattuda see harjumus,
me otsustasime teha sama asja. Seal ei ole palju list1.h,
kuid me oleme panna midagi, mis võiks huvi pakkuda inimestele maailmas
kes tahavad kasutada meie seotud nimekirja rakendamist.
Nüüd, list1.c, ma ei lähe läbi kogu see asi
sest see on natuke pikk, see programm, kuid olgem kestab see päris kiiresti käsureale.
Lubage mul koostada List1, las ma siis kestab List1, ja mida te näete on
oleme simuleeritud lihtne väike programm siin
et läheb lubage mul lisada ja eemaldada numbrite nimekiri.
Nii et lubage mul minna ja tüüp 3 menüüvalikut 3.
Ma tahan sisestada number - teeme esimese numbri, mis oli 9,
ja nüüd ma olen kuulnud, nimekiri on nüüd 9.
Lubage mul minna ja teha teine ​​sisestamise, nii et ma tabanud menüü 3. variant.
Mis number ma tahan lisada? 17.
Enter. Ja ma teen veel üks.
Lubage mul lisada number 22.
Nii et meil on alguse seotud nimekirja, mis meil oli slaidi kujul hetk tagasi.
Kuidas seda sisestamise tegelikult toimub?
Tõepoolest, 22 on nüüd lõpuks nimekirjas.
Nii et lugu me rääkisime laval esmaspäeval ja recapped lihtsalt nüüd
tuleb tegelikult toimub kood.
Võtame pilk. Las ma kerin alla see fail.
Me ilustada teatud funktsioone,
aga me läheme, ütleme, sisestada funktsiooni.
>> Vaatame, kuidas me lisada uus tipp sellesse seotud nimekirja.
Kui on nimekiri kuulutatud? Noh, olgem liikuda kogu tee kuni ülaosas,
ja märkate, et minu lingitud nimekiri on sisuliselt deklareeritakse ühe osutiga, mis on algselt NULL.
Nii et ma kasutan globaalse muutuja siin, mis üldiselt oleme kuulutanud vastu
sest see muudab oma koodi veidi räpane säilitada,
See on omamoodi laisk, tavaliselt, kuid see ei ole laisk ja see pole vale ja see ei ole halb
Kui teie programmi ainus eesmärk elus on simuleerida ühe seotud nimekirja.
Mis on täpselt see, mida me teeme.
Nii et pigem deklareerima selle peamine ja siis pea seda iga funktsioon
oleme kirjutanud selle programmi, me mitte aru oh, lähme siis tee seda maailma
sest kogu eesmärk on see programm on näidata ainult üks seotud nimekirja.
Nii et tundub okei. Siin on minu prototüüpe, ja me ei lähe läbi kõik need,
aga ma kirjutasin Kustutamise funktsiooni, leida funktsiooni sisestada funktsioon ja traavers funktsioon.
Kuid olgem nüüd minna tagasi alla insertfunktsioonide
ja näha, kuidas üks töötab siin.
Lisa on joonel - siin me läheme.
Lisa. Nii et see ei võta mingeid argumente, sest me ei kavatse küsida
kasutaja sees seda funktsiooni arvu nad tahavad lisada.
Aga kõigepealt, me valmistume andma neile ruumi.
See on omamoodi kopeeri ja kleebi teise näite.
Sel juhul olime eraldades int; seekord me eraldades sõlme.
Ma tõesti ei mäleta, kui palju baite sõlm on, kuid sellest pole midagi.
Sizeof saab aru, et minu jaoks.
Ja miks ma kontrollimine NULL kooskõlas 120?
Mis võiks minna valesti line 119? Jah?
[Student vastus, arusaamatult]
Hea. Lihtsalt võib juhtuda, et ma käskisin liiga palju mälu
või et midagi on valesti ja operatsioonisüsteemi ei ole piisavalt baiti mulle,
nii see annab nii palju, tagastades NULL, ja kui ma ei kontrollige, et
ja ma lihtsalt pimesi edasi kasutada aadressi tagastatakse, võiks see olla NULL.
See võiks olla mingi tundmatu väärtuse; ei ole hea kui ma -
tegelikult ei ole tundmatu väärtus. See võib olla NULL, nii et ma ei taha
kuritarvitama ja riskida viite mahavõtmine ta.
Kui see juhtub, siis lihtsalt tagasi ja me teeskleme, et ma ei saanud tagasi kõik mälu üldse.
>> Muidu ma ütlen kasutaja anna mulle number sisestada, ma kutsun meie vana sõber GetInt,
ja siis see oli uus süntaks tutvustasime esmaspäeval.
"Newptr-> n 'tähendab võtta aadress, mida andsid malloc
mis on esimene bait uus sõlm objekti,
ja siis lähevad põllule nimetatakse n.
Väike trivia küsimus: See on samaväärne sellega, mis rohkem segasena rida koodi?
Kuidas muidu oleks ma olen kirjutanud seda? Tahad võtta pussitada?
[Student vastus, arusaamatult]
Hea. Kasutades. N, kuid see ei ole päris nii lihtne.
Mida ma kõigepealt tegema? [Student vastus, arusaamatult]
Hea. Ma pean tegema * newptr.n.
Nii et see ütleb uus pointer on ilmselt aadress. Miks?
Sest see tagastati malloc. * Newptr öeldes: "sinna minna"
ja siis kui sa oled seal, siis saate rohkem tuttav. n
kuid see lihtsalt tundub natuke kole, eriti kui meie, inimesed hakkavad
juhtida vihjeid nooltega kogu aeg; maailmas on standardiseeritud selle noole märke,
mis ei täpselt sama asi.
Nii et kasutate ainult -> märke, kui asi vasakul on kursor.
Vastasel juhul, kui see on tegelik struct, kasutage. N.
Ja siis selline: Miks ma initsialiseerida newptr-> kõrval NULL?
Me ei taha rippuvad vasakul off etapi lõpus.
Me tahame, juhtides otse alla, mis tähendab lõpuks seda nimekirja
võiks olla see sõlm, nii et me parem veenduge, et see on NULL.
Ja üldiselt initsialiseerimisel oma muutujate või oma andmete kohal ja structs
et midagi on lihtsalt hea tava.
Lihtsalt lase prügi olemas ja on endiselt olemas üldiselt saab teid hätta
kui te unustate midagi hiljem.
>> Siin on mõned juhtumid. See omakorda on lisada funktsioon,
ja esimene asi, mida ma kontrollida on, kui muutuja nimega esmalt
et globaalse muutuja on NULL, mis tähendab, et ei ole seotud nimekirja.
Me ei ole sisestatud ühtegi arvu, nii et see on triviaalne lisada see praegune number
nimistusse, sest see lihtsalt kuulub alguses nimekirja.
Nii et see oli siis, kui Anita oli just püsti siin üksi, teeseldes
keegi oli siin laval kuni me eraldatud sõlme,
siis ta võiks tõsta oma käsi esimest korda,
kui kõik teised olid tulnud lavale pärast teda esmaspäeval.
Nüüd siin on vähe kontrolli, kus ma pean ütlema, kui uus sõlm väärtus n
on <väärtus n praeguses esimese sõlme,
See tähendab, et on seotud nimekirja, mis on alanud.
Seal on vähemalt üks tipp nimekirjas, kuid see uus kutt
kuulub enne seda, seega peame liikuma asju ümber.
Teisisõnu, kui loetelu on alanud lihtsalt, ütleme,
lihtsalt number 17, see on - tegelikult, me saame seda teha selgemalt.
Kui alustame meie lugu pointer siin nimetatakse esmalt
ja esialgu on see NULL, ja me sisestada number 9,
number 9 selgelt kuulub alguses nimekirja.
Nii oletame, me lihtsalt malloced aadress või number 9 ja pane see siia.
Kui esimene on 9 vaikimisi esimese stsenaariumi me arutasime lihtsalt tähendab, olgem punkt see kutt siin,
jätke see nagu NULL; nüüd on meil number 9.
Järgmine number tahame lisada on 17.
17 kuulub siia, et me ei kavatse teha mõned loogiline samm selle kaudu.
Nii et olgem selle asemel, enne kui me seda teeme, oletame, et me tahtsime sisestada number 8.
>> Nii lihtsalt mugavuse pärast, ma lähen teha siin.
Kuid pidage meeles, malloc ei pane see kõige kõikjal.
Aga joonistus pärast, ma panen selle siia.
Nii teesklen, et ma olen lihtsalt eraldatud sõlm nr 8, see on NULL vaikimisi.
Mis nüüd juhtub? Paar asja.
Tegime seda viga laval esmaspäeval, kui me uuendatud osuti nagu see,
siis tegin seda, ja siis me väitis - me orvuks kõik teisedki laval.
Sest sa ei saa - selleks toimingute siin on oluline,
sest nüüd me kaotasime selle sõlme 9, et on lihtsalt omamoodi ujuvad ruumi.
Nii et see ei olnud õige lähenemine esmaspäeval.
Peame esmalt teha midagi muud.
Olukorda maailmas näeb välja selline. Esialgu, 8 on eraldatud.
Mis oleks parem viis sisestamist 8?
Selle asemel, uuendades seda osuti esimene, lihtsalt uuendada see siin mitte.
Seega peame rida koodi, mis läheb omakorda see NULL sümbol
arvesse tegelik osuti, mis on suunatud sõlme 9,
ja siis saame ohutult muuta esimene, kes seda venda siin.
Nüüd on meil nimekirjas, mis on seotud nimekirja, kahest elemendist.
Ja mida see tegelikult välja näeb siin?
Kui me vaatame koodi, märkate, et ma olen teinud täpselt seda.
Ma olen öelnud newptr, ja selles loos, newptr oli suunatud seda venda.
>> Nii et las ma joonistan veel üks asi, ja ma oleks pidanud vasakule rohkem ruumi seda.
Nii andeks tilluke joonistus.
See mees on nn newptr.
See on muutuv me kuulutasime paar rida varem, liin - veidi üle 25.
Ja see osutavad 8. Nii et kui ma ütlen newptr-> next, see tähendab minna struct
mis kuramuse osutas poolt newptr, nii siin me oleme, sinna minna.
Siis nool ütleb saada järgmisele väljale ja seejärel = ütleb pane milline väärtus on?
Väärtus, mis oli esimene; milline väärtus oli esimene?
Esiteks oli suunatud selles sõlme, et tähendab see peaks nüüd juhtida seda sõlme.
Teisisõnu, milline näeb välja küll naeruväärne jama minu käekiri,
mida on lihtne idee, et lihtsalt liiguvad need nooled ümber
tõlgib koodi vaid selle ühe riba.
Hoida mis on esimene järgmisele väljale ja seejärel värskendage mida esimesena tegelikult on.
Lähme edasi ja edasi kerin natuke seda,
ja vaatavad vaid see saba sisestamise nüüd.
Oletame, et ma saan selle punktini, kus ma leian, et järgmise välja mõned sõlm on NULL.
Ja siinkohal lugu, täpselt, et ma ilustamise
on see, et ma olen kasutusele teise osuti siia üles rida 142, eelkäija pointer.
Sisuliselt siinkohal lugu, kui nimekiri saab pikk,
Ma vajan kõndida ta kaks sõrme, sest kui ma liiga kaugele,
mäletan ühte pikkusega nimekirja, sa ei saa minna tagasi.
Nii et see idee predptr on minu vasak sõrme ja newptr - ei newptr.
Teine osuti, mis siin on minu teine ​​sõrm, ja ma olen lihtsalt selline kõndimine nimekirja.
Sellepärast, et on olemas. Kuid olgem arvesse ainult üks lihtsamaid juhtumeid siin.
Kui see osuti järgmiseks valdkonnas on NULL, mis on loogiline jätk?
Kui te liiklevad see nimekiri ja põrkad NULL pointer?
Sa oled lõpus nimekirja, ja nii koodi siis lisab see veel ühe elemendi
on omamoodi intuitiivne võtab, et sõlm, kelle kõrval pointer on NULL,
nii on see praegu NULL, ja seda muuta, kuigi oleks aadress uus sõlm.
Nii et me lihtsalt joonist kood nool, et me juhtis laval tõstes kellegi vasaku käega.
>> Ja nii, et ma siputan käed nüüd,
lihtsalt sellepärast, et ma arvan, et see on lihtne ära eksida, kui me teeme seda selline keskkond,
kontrollib lisamiseks kell listi keskel.
Aga lihtsalt intuitiivselt, mida on vaja juhtuda, kui sa tahad aru saada,
kus mõned number kuulub keskel on sa ei pea kõndima seda
rohkem kui ühe sõrmega, rohkem kui üks pointer,
nuputada, kuhu see kuulub kontrollides on element <praegust,
> Praegust, ja kui sa leiad, et koht,
siis sa pead tegema seda sorti koorimata mäng kus liigutad osuti ümber väga hoolikalt.
Ja see vastus, kui soovite põhjusel kaudu seda kodus ise,
taandub lihtsalt need kaks rida koodi, kuid et nende read on super oluline.
Sest kui sa tilk kellegi käsi ja tõsta kellegi vales järjekorras,
uuesti, siis võib lõpuks orvustumine nimekirja.
Kokkuvõttes rohkem kontseptuaalselt sisestamise tagaosa on suhteliselt lihtne.
Sisestamise eesotsas on ka suhteliselt lihtne,
kuid teil on vaja ajakohastada täiendavaid osuti seekord
pigistada number 5 esitatud loetellu siin,
ja siis on asetatud keset hõlmab veelgi rohkem jõupingutusi,
väga hoolikalt sisestada number 20 oma õigesse asukohta,
mis on vahemikus 17 ja 22.
Nii et sa pead tegema midagi sellist on uus sõlm 20 punktist 22,
ja siis, mis sõlme osuti tuleb ajakohastada viimase?
See on 17, tegelikult lisada.
Nii et taas, ma lükata tegelikku koodi selle konkreetse rakendamise.
>> Esmapilgul see on veidi ülepaisutatud, kuid tegelikult on see vaid lõputu silmuse
mis on silmuspõletamise, silmuspõletamise, silmuspõletamise, silmuspõletamise ja murdsid niipea kui vajutad NULL pointer,
misjärel saate teha vajalikud sisestamist.
See on siis esindaja seotud nimekirja sisestamise koodi.
See oli tõesti palju, ja tundub, nagu me oleme lahendada üks probleem,
aga meil kasutusele terve teine. Ausalt öeldes, oleme kulutanud kogu selle aja
aasta suur O ja Ω ja sõiduaega, püüdes lahendada probleeme kiiremini,
ja siin me võtame suure sammu tahapoole, tundub.
Ja veel, kui eesmärgiks on andmete salvestamiseks,
tundub, nagu Püha Graal, kui me ütles esmaspäeval, oleks tõesti
salvestada asju koheselt.
>> Tegelikult arvan, et me tegime kõrvale panema seotud nimekirja hetkeks
ja me asemel kasutusele mõiste tabelis.
Ja olgem lihtsalt mõtlema tabelis hetkeks massiivina.
See massiivi ja antud juhul on siin umbes 26 elementi, 0 kuni 25,
ja oletame, et teil on vaja mõned patakas ladustamine nimed:
Alice ja Bob ja Charlie jms.
Ja sa pead mõned andmestruktuur salvestada need nimed.
Noh, sa võiksid kasutada midagi seotud nimekirja
ja sina võiks kõndida nimekirja lisada Alice enne Bob ja Charlie pärast Bob ja nii edasi.
Ja tegelikult, kui soovite näha koodi niimoodi nagu kõrvale,
tean, et list2.h, me teeme just nii.
Me ei lähe läbi see kood, kuid see on variant esimene näide
, mis tutvustab üht struct oleme näinud nn õpilane,
ja siis mida see tegelikult kauplust seotud nimekirja on viit õpilane struktuur
mitte lihtsalt väike täisarv, n.
Nii aru, seal kood seal, mis hõlmab tegelik stringid,
kuid kui eesmärgiks käepärast tõesti nüüd on tegeleda efektiivsuse probleem,
kas ei oleks tore, kui me antud objekti nimega Alice,
me tahame panna tema õigesse asukohta andmestruktuur,
tundub, nagu see oleks tõesti tore lihtsalt panna Alice,
kelle nimi algab esimeses kohas.
Ja Bob, kelle nimi algab B, teises kohas.
Mis array, või alustame nimetades seda tabelit, hash tabel, et
me saame teha just nii. Kui oleme andnud nime nagu Alice,
string nagu Alice, kus sa paned-l-i-c-e?
Me vajame hueristic. Meil on vaja funktsiooni, et võtta mõned sisend nagu Alice
ja tagastab vastuse: "Pane Alice selles kohas."
Ja see funktsioon, see must kast, läheb nimega räsifunktsiooniga.
>> Räsifunktsiooniga on midagi, mis võtab sisendina, nagu "Alice",
ja tagastab teile, tavaliselt numbriline asukoht mingis andmestruktuur, kus Alice kuulub.
Sel juhul meie räsifunktsiooniga peaks olema suhteliselt lihtne.
Meie räsifunktsiooniga peaks ütlema, kui sulle antakse "Alice", mis laadi peaks ma hoolin?
Esimene. Nii et ma vaatan [0], ja siis ma ütlen, kui [0] märk on, tagastab arvu 0.
Kui see on B, return 1. Kui see on C, tagastab 2, ja nii edasi.
Kõik 0 indeks ning mis võimaldaks mul lisada Alice ja siis Bob ja siis Charlie ja nii edasi
sellesse andmestruktuur. Aga seal on probleem.
Mis siis, kui Anita tuleb mööda jälle?
Kust me paneme Anita? Tema nimi ka, algab tähega,
ja tundub, nagu oleme teinud isegi suurem jama selle probleemi.
Meil on nüüd kohe sisestamise pidevalt aega sisestamisel arvesse andmestruktuur
mitte halvimast lineaarne,
kuid mida me saame teha koos Anita sel juhul?
Millised on kaks võimalust, kas tõesti? Jah?
[Student vastus, arusaamatult] Okei, nii et meil oleks teine ​​dimensioon.
See on hea. Nii et me saame ehitada asju läbi 3D nagu me rääkisime suuliselt esmaspäeval.
Võiksime lisada veel juurdepääsu siin, kuid arvan, et ei, ma üritan hoida seda lihtsat.
Kogu eesmärk siin on kohe pidev tööajaga juurdepääsu,
Nii et lisades liiga palju keerukust.
Mis on ka teisi võimalusi, kui soovitakse sisestada Anita sellesse andmestruktuur? Jah?
[Student vastus, arusaamatult] Hea. Nii et me võiks minna kõik teisedki maha,
nagu Charlie Nudget alla Bob ja Alice, ja siis me paneme Anita kus ta tahab olla.
>> Muidugi, nüüd, seal on kõrvalnäht seda.
See andmestruktuur on ilmselt kasulik ei ole, sest me tahame lisada inimesed kord
kuid kuna me tahame, et kontrollida, kas nad on sinna hiljem
kui me tahame, et printida välja kõik nimed andmestruktuur.
Me teeme midagi koos käesoleva andmete lõpuks.
Nii et nüüd oleme omamoodi kruvitud üle Alice, kes ei ole enam, kus ta olema pidi.
Samuti on Bob, ega Charlie.
Nii et võibolla see ei ole nii hea idee.
Aga tõesti, see on üks võimalus. Me võiks suunata kõik alla,
või kuradit, Anita tulid hilja mängu, miks me lihtsalt ei pane Anita
mitte siin, mitte siin, mitte siin, paneme ta veidi madalam nimekirjas.
Aga siis see probleem algab delegeerida uuesti.
Sul võib olla võimalik leida Alice koheselt, mis põhineb tema eesnimi.
Ja Bob koheselt, ja Charlie. Aga siis sa ootad Anita,
ja näed, hmm, Alice on viis.
Noh, las ma vaatan alla Alice. Bob ei ole Anita.
Charlie ei Anita. Oh, seal on Anita.
Ja kui te jätkate et rong loogika kogu tee,
Mis on halvim sõiduaega leida või lisada Anita uude andmestruktuur?
See on O (n), eks?
Sest halvimal juhul, seal on Alice, Bob, Charlie. . .
kõik tee alla keegi nimega "Y", nii seal on ainult üks koht on jäänud.
Õnneks ei ole meil üks nn "Z", nii me paneme Anita väga põhjas.
>> Me ei ole tegelikult lahendanud selle probleemi.
Nii et võib-olla me ei vaja kehtestada selle kolmanda mõõtme.
Ja selgub, kui me tutvustada see kolmas dimensioon,
me ei saa seda teha ideaalselt, kuid Püha Graal saab olema saada
konstantse aja sisestamise ja dünaamiline lisamised nii et
me ei pea raskesti kood massiivi suurus 26.
Me ei saa sisestada nii palju nimesid kui tahame, kuid võtame meie 5-minutilise vaheaja siin
ja siis tee seda korralikult.
Hea küll. Seadsin lugu üles päris kunstlikult seal
valides Alice ja siis Bob ja siis Charlie ja siis Anita,
kelle nimi oli ilmselt läheb põrkuvad Alice.
Kuid küsimus meil lõppes esmaspäeval on lihtsalt kui tõenäoline on see
et sa saaksid selliseid kokkupõrkeid? Teisisõnu,
kui me hakkame kasutama seda tabelina struktuur, mis on tegelikult lihtsalt massiiv,
antud juhul 26. asukohad,
Mis siis, kui meie sisendite asemel ühtlaselt jaotatud?
See ei ole kunstlikult Alice ja Bob ja Charlie ja David ja nii edasi tähtedega,
see on jaotatud ühtlaselt läbi Z.
>> Võib-olla me lihtsalt veab ja me ei kavatse on kaks poolt või kaks B
väga suure tõenäosusega, kuid kui keegi märkis,
kui me üldiste see probleem ja ei tee 0-25
aga, ütleme, 0 kuni 364 või 65, sageli päevade tüüpiline aastal
ja küsis: "Mis on tõenäosus, et kaks meist siin ruumis on sama sünnipäev?"
Teisisõnu, mis on tõenäosus, et kaks meist on nimi algab?
Selline küsimus on sama, kuid see aadress ruumi,
see otsing ruum on suurem juhul, sünnipäevad,
sest meil on nii palju rohkem päeval aastas kui tähte tähestikus.
Mis on kokkupõrke tõenäosus?
Noh, me ei mõtle seda figuring matemaatika vastupidi.
Mis on tõenäosus ei kokkupõrkeid?
Noh, see väljend siin ütleb, et mis on tõenäosus
kas seal on ainult üks inimene siin ruumis, et neil on unikaalne sünnipäeva?
See on 100%. Sest kui seal on ainult üks inimene toas,
tema sünnipäev võib olla mis tahes 365 päeva läbi aasta.
Nii et 365/365 valikutest annab mulle väärtus 1.
Nii et tõenäosus kõnealuse hetkel on vaid 1.
Aga kui seal on teine ​​inimene toas,
Mis on tõenäosus, et nende sünnipäev on erinevad?
Seal on vaid 364 võimaliku päeva, unustades liigaasta,
oma sünnipäeva mitte sattuda vastuollu teiste isikutega.
Nii et 364/365. Kui kolmas isik tuleb, see on 363/365, ja nii edasi.
Nii et me hoiame korrutades koos nende fraktsioonid, mis on üha väiksemaid ja väiksemaid,
selgitada, milline on tõenäosus, et kõik meist on unikaalne sünnipäevad?
Aga siis me muidugi lihtsalt võtta seda vastust ja klapp selle ümber
ja teha 1 miinus kõik, et väljend me lõpuks saada
kui sa mäletad tagasi oma matemaatika raamatuid, tundub natuke midagi sellist,
mis on palju kergem tõlgendada graafiliselt.
Ja see graafiline siin on x-telg arvu sünnipäevad,
või inimeste arv sünnipäevad, ja y-telg on tõenäosus sobi.
Ja mida see ütleb on, et kui sul on, ütleme, isegi,
Valime midagi 22, 23.
Kui seal on 22 või 23 inimest ruumis,
Tõenäosus, et kaks neist väga vähesed inimesed hakkavad olema sama sünnipäev
on tegelikult super kõrge, combinatorially.
50% tõenäosus, et klassi vaid 22 inimest, seminar, praktiliselt,
2 need inimesed hakkavad olema sama sünnipäev.
Sest seal on nii palju võimalusi, kus saab olema sama sünnipäev.
Isegi hullem, kui te vaatate paremale küljele diagrammi,
selleks ajaks teil on klassis ainult 58 õpilast seda,
tõenäosus 2 inimest, kellel on sünnipäev on super, super suur, ligi 100%.
Nüüd, see on omamoodi lõbus fakt reaalses elus.
>> Aga mõju, nüüd, andmestruktuurid ja teabe hoidmise
tähendab, et lihtsalt eeldades, et teil on kena, puhas, ühtlane jaotus andmeid
ja sul on piisavalt suur massiiv mahtuda hunnik asju
ei tähenda, sa lähed, et saada inimesi ainulaadne kohtades.
Sa lähed on kokkupõrkeid. Nii et see mõiste segamist, nagu seda nimetatakse,
võttes sisend nagu "Alice" ja massaging see kuidagi
ja siis saada tagasi vastus nagu 0 või 1 või 2.
Getting tagasi mõned väljund, et funktsioon on vaevanud see tõenäosus kokkupõrke.
Niisiis, kuidas me saame hakkama neid kokkupõrkeid?
Noh, ühel juhul saame idee, et pakuti.
Me ei saa lihtsalt minema kõik maha, või ehk, veidi lihtsamalt,
selle asemel et liikuda kõik teisedki, lihtsalt liikuda Anita põhjale saadaval kohapeal.
Nii et kui Alice on 0, Bob on 1, Charlie on 2,
me lihtsalt panna Anita at asukoht 3.
Ja see on tehnika andmestruktuurid nimetatakse lineaarse katsetamine.
Lineaarne, sest sa oled lihtsalt kõndides seda joont, ja sa oled omamoodi katsetamine
olemasolevaid kohti andmestruktuur.
Muidugi, see devolves O (n).
Kui andmestruktuur on tõesti täis, seal on 25 inimest seda juba,
ja siis Anita jõuab mööda, ta jõuab, mida oleks asukoha Z, ja see on hea.
Ta ikka sobib, ja me leiame ta hiljem.
>> Aga see oli vastuolus eesmärgiga kiirendada asju üles.
Mis siis, kui me selle asemel kasutusele see kolmas mõõde?
See meetod on üldiselt nimetatakse eraldi Aheldamise või kellel ketid.
Ja mida hash tabelis nüüd on see tabelina struktuur,
Teie lauas on vaid massiivi osuti.
Aga mis need näpunäited käsk on guess what?
Seotud nimekirja. Mis siis, kui me võtame parima mõlemad maailmad?
Me kasutame massiivid esialgse indeksid
arvesse andmete struktuuri, et saaksime koheselt minna [0] [1], [30] või nii edasi,
kuid nii, et meil on teatud paindlikkust ja me ei sobi Anita ja Alice ja Adam
ja muu nime,
me selle asemel lasta teine ​​telg kasvada meelevaldselt.
Ja me lõpuks alates esmaspäevast, on selle ilmekas võime koos seotud nimekirja.
Meil võib kasvada andmestruktuur meelevaldselt.
Teise me võiks lihtsalt teha suur 2-mõõtmeline massiiv,
kuid see saab olema kohutav olukord, kui üks rida 2-mõõtmeline massiiv
ei ole piisavalt suur, et täiendav isik, kelle nimi juhtub alustada A.
Jumal hoidku me peame ümber tohutu 2-mõõtmeline struktuur
lihtsalt sellepärast, et seal on nii palju inimesi nimega,
eriti kui seal on nii vähe inimesi nimega Z midagi.
See on lihtsalt saab olema väga hõre andmestruktuur.
Nii see ei ole täiuslik igasuguste vahenditega, kuid nüüd me vähemalt on võime
Et koheselt leida, kui Alice või Anita kuulub,
vähemalt nii vertikaalteljel,
ja siis me lihtsalt peame otsustama, kuhu panna Anita või Alice see seotud nimekirja.
Kui me ei hooli sorteerimine asjad, kui kiiresti saaks me lisada Alice struktuuri, nagu see on?
See on pidevalt aega. Me indeks [0], ja kui keegi seal,
Alice läheb alguses, et seotud nimekirja.
Aga see ei ole suur asi. Sest kui Anita siis tuleb mööda
mõned mitmeid samme hiljem, kui ei Anita kuulub?
Noh, [0]. OOP. Alice on juba selles seotud nimekirja.
>> Aga kui me ei hooli sorteerimine nende nimed,
me võime lihtsalt liikuda Alice üle, sisesta Anita, kuid isegi see on pidevalt aega.
Isegi kui seal on Alice ja Aadam ja kõik need muud nimed,
See ei ole tegelikult muudavad need füüsiliselt. Miks?
Sest me lihtsalt ei siin lingitud nimekiri, kes teab olid need sõlmed on niikuinii?
Kõik, mida selleks vaja on liikuda leivapuru.
Liigu nooltega ringi, sa ei pea füüsiliselt liigutada andmeid ümber.
Nii saame sisestada Anita, sellisel juhul koheselt. Pidev aeg.
Nii et meil on pidevalt ajaga lookup, ja pidev aja sisestamise keegi nagu Anita.
Aga selline Oversimplifying maailmas.
Mis siis, kui me hiljem tahad leida Alice?
Mitu sammu on, et aega võtab?
[Student vastus, arusaamatult]
Täpselt. Inimeste arv enne Alice seotud nimekirja.
Nii et see ei ole päris täiuslik, sest meie andmestruktuur, jälle on see vertikaalne juurdepääsu
ja siis on need seotud nimekirjad ripuvad - tegelikult, ärme joonistada massiivi.
On need seotud nimekirjad ripuvad välja sellest, mis näeb välja natuke midagi sellist.
Probleem on aga selles, kui Alice ja Aadam ja kõik need muud nimed
lõpuks rohkem ja rohkem seal,
leida keegi võiks lõpuks võtta hunnik samme,
bcause teil läbida seotud nimekirja,
mis on lineaarne operatsioon.
Nii et tõesti, siis sisestamise aja lõpuks on O (n), kus n on elementide arv nimekirjas.
Jagades, olgem meelevaldselt nimetame seda m, kus m on arv lingitud nimekirjad
et meil on selles vertikaalteljel.
Teisisõnu, kui me tõesti eeldada ühtlase jaotuse nimed,
täiesti ebareaalne. Seal on ilmselt rohkem mõnede tähtede kui teised.
>> Aga kui me eeldame hetkel ühtlase jaotuse,
ja me oleme N Kokku inimesi, ja m kokku ketid
meile kättesaadav, siis pikkus kummagi ketid
üsna lihtsalt saab olema kokku, n arvuga ahelate.
Nii n / m. Aga siin, kus me saame olla kõik matemaatiliselt tark.
m on konstant, sest seal on fikseeritud hulk neid.
Sa lähed kuulutada oma massiivi alguses,
ja me ei ole saneerimist vertikaalteljel. Definitsiooni järgi, mis jääb samaks.
See on ainult horisontaalteljel niiöelda, et muutub.
Nii et tehniliselt on see pidev. Nii et nüüd, sisestusajaga
on päris palju O (n).
Nii et ei tunne kõik, et palju parem.
Aga mis on tõde siin? Noh, kõik see aeg, nädalaid,
oleme rääkinud O (n ²). O (n), 2 x n ², - n, jagatud 2. . . ech.
See on lihtsalt n ². Aga nüüd, selles osas semestri
saame hakata rääkima reaalses maailmas uuesti.
Ja n / m on täiesti kiiremini kui lihtsalt n üksi.
Kui teil on tuhat nime, ja te murda neid mitmeks ämbrid
nii et teil on ainult kümme nimed kõigis nendes ahelates,
absoluutselt otsivad kümme asja, saab olema kiirem kui tuhat asja.
Ja nii üks tulemas probleem komplekti läheb sulle väljakutse
mõelda täpselt, et kuigi, jah,
asümptootiliselt ja matemaatiliselt, see on ikka lihtsalt lineaarne,
mis imeb üldiselt kui nad püüavad leida asju.
Tegelikult see saab olema kiirem kui
sest see jagaja.
Ja nii pole jälle saab olema see kompromiss
ja see vastuolu teooria ja tegelikkus,
ja üks nupud hakkab keerates siinkohal semester
on rohkem reaalsuseks, nagu me omamoodi valmistuda semster lõpuks,
kui me võtame kasutusele maailmas veebi programmeerimine,
kus tõesti, tulemuslikkust loen, sest teie kasutajad hakkavad
enesetunne ja hindame halva disaini otsuseid.
>> Niisiis, kuidas sa minna rakendamisel seotud - hash tabelis on 31 elementi?
Ja eelmises näites oli omavoliliselt umbes sünnipäevad.
Kui keegi ei ole sünnipäeva 1. jaanuaril või 1. veebruar me paneme neid selles ämber.
Kui see on 2. jaanuar veebruar 2, 2. märts paneme neid selles ämber.
Sellepärast oli 31. Kuidas kuulutada hash tabelit?
See võib olla üsna lihtne, sõlme * tabelis on minu suvalise nime see, [31].
See annab mulle 31 viiteid tippu,
ja mis võimaldab mul on 31 viiteid seotud nimekirjad
isegi kui need ketid on esialgu NULL.
Mida ma tahan panna kui ma tahan salvestada "Alice", "Bob", "Charlie"?
Noh, me peame pakkima need asjad struktuur
sest me vajame Alice osutada Bob, osutada Charlie, ja nii edasi.
Me ei saa lihtsalt nimed üksi, nii et ma võiks luua uue struktuuri, mida nimetatakse sõlme siin.
>> Mis on tegelik sõlme? Mis on sõlm selles uues seotud nimekirja?
Esimene asi, mida nimetatakse sõna, on isiku nimi.
PIKKUS, arvatavasti, puudutab pikkust inimese nimi,
mis iganes see on, 20, 30, 40 tähemärki hull nurgas juhtudel,
ja +1 on milleks? See on lihtsalt pildi NULL sümbol, \ 0.
Nii et see sõlm on ümbriste "midagi" sees ise,
kuid see kinnitab osuti nimetas tuleva
et saaksime kett Alice Bobile Charlie ja nii edasi.
Ei saa olla NULL, kuid ei pruugi olla.
Kõik küsimused nende hash tabeleid? Jah?
[Student küsib küsimuse, arusaamatult] massiivi - hea küsimus.
Miks on see char sõna array asemel lihtsalt char *?
Selles mõnevõrra meelevaldne näide, ma ei taha olla abiks
kuni malloc iga algsed nimed.
Tahtsin kuulutada maksimaalselt mälu string
nii et ma võiksin kopeerida selle struktuuri Alice \ 0 ja ei pea tegelema malloc ja tasuta jms.
Aga ma võiks teha, et kui ma tahtsin olla teadlik ruumi kasutamise. Hea küsimus.
Nii et proovime üldistada eemale sellest
ning keskenduda ülejäänud täna andmestruktuurid üldisemalt
ja muid probleeme, et saame lahendada kasutades samu alused
kuigi andmestruktuurid ise võib erineda oma andmed.
>> Nii selgub infotehnoloogia, puud on väga levinud.
Ja sa ei mõtle puu omamoodi nagu sugupuu,
kui seal on mõned juured, mõned matriarh või patriarh,
vanaema või vanaisa või varem tagasi,
all, mis on ema ja isa või erinevate õed-vennad vms.
Nii puu struktuuri on sõlmed ja tal on lapsed,
tavaliselt 0 või enam last iga sõlme.
Ja mõned kõnepruuki, et näed sellel pildil siin
on mis tahes väikesed lapsed või lapselapsed äärealadel
kellel ei ole nooled, mis tulenevad nende
need on nn lehed, ja keegi sees
on sisemine sõlme; võite helistada see midagi sarnast.
Aga see struktuur on üsna tavalised. See üks on natuke meelevaldne.
Meil on üks laps vasakul, meil on kolm last paremal
kahe lapse all vasakul.
Nii et meil on erineva suurusega puud, aga kui me hakkame standardiseerida asju,
ja te võiks meenutada, seda alates Patricku video binaarne otsing eelmisest lühike
internetis, binaarne otsing ei pea olema rakendatav massiivi
või paberitükke tahvli.
Oletame, et sa tahad säilitada oma numbrid keerukamaid andmete struktuuri.
Sa võid luua puu niimoodi.
Sul võib olla sõlme deklareeritud C, ja et sõlm võib olla vähemalt kaks elementi sees on.
Üks on number, mida soovite salvestada, ja teine ​​on - noh, me vajame veel ühte.
Teine on oma lapsed.
Nii et siin on veel üks andmestruktuur. Seekord sõlm on määratletud ladustamiseks arv n
ja siis kaks suunanäitajaks; vasak laps ja õigus lapse.
Ja nad pole meelevaldne. Mis on huvitav see puu?
>> Mis on muster, kuidas me ette selle välja või kuidas Patrick pani välja oma video?
See on selline selge, et seal on mõned sorteerimine toimub siin,
kuid milline on lihtne reegel? Jah?
[Student vastus, arusaamatult]
Perfect. Kui te pilk sellele, näete vähesel arvul vasakul,
suured numbrid vasakul, aga see on tõsi iga sõlme.
Iga sõlme, tema vasak lapse vähem kui see, ja tema õigus lapse üle ta.
Mida see tähendab nüüd on, kui ma tahan, et otsida seda andmestruktuuri, ütleme, number 44,
Ma pean alustama keskmes, sest kui kõiki neid keerulisem andmestruktuurid nüüd,
meil on ainult kursor üks asi, alguses.
Ja sel juhul, alguses on juur. See ei ole vasakus servas,
see on just see struktuur. Nii et ma näen siin on 55, ja ma otsin 44.
Millises suunas ma tahan minna?
Noh, ma tahan minna vasakule, sest ilmselgelt, et õigus saab olema liiga suur.
Nii märkate siin, sa oled omamoodi kontseptuaalselt tükeldamise puu pooleks
sest sa oled kunagi alla paremas servas.
Nii et nüüd ma lähen alates 55 kuni 33. See on liiga väike number.
Otsin 44, kuid nüüd ma tean, et 44 on sellel puul, ma ei lähe ilmselt paremale.
Nii et taas, ma olen pügamine puud pooleks.
See on päris palju identne kontseptuaalselt kuuluv telefoniraamat.
See on identne mida tegime paberid tahvel,
aga see on keerukam struktuur, mis võimaldab meil tegelikult teha
Selle jaga ja valitse, mille konstruktsioon on algoritm,
ja tegelikult liiklevad struktuur niimoodi - Ups.
Liikumine struktuur meeldib see, kus see on ainult "minna sel viisil või seda teed minna,"
kaugeltki kõik, kood, painutatud meelt esimesel rakendamisel tuleks rubriigis
või jalgsi läbi kodus, binaarne otsing, kasutades rekursiooni või iteratsiooni
see on tüütu. Leia keset element, tehke oma ümardamine üles või alla.
>> Seal on ilu, sest saame nüüd kasutada rekursiooni uuesti,
aga palju puhtamalt. Tõepoolest, kui sa oled number 55 ja soovite leida 44,
sa mine vasakule antud juhul siis mida sa teed? Sa jooksed täpselt sama algoritmi.
Sa kontrolli väärtus sõlme, siis lähete vasakule või paremale.
Siis kontrollida väärtust sõlme, mine vasakule või paremale.
See sobib suurepäraselt rekursioon.
Nii et kuigi varem oleme teinud mõned üsna meelevaldne näiteid erinevate rekursioon
et ei pea olema rekursiivne, andmete STUCTURES,
eriti puud, see on täiuslik käesoleva idee võtta probleemi,
kahanemine ning seejärel lahendada sama tüüpi, kuid väiksem, programm.
>> Nii et seal on teine ​​andmestruktuur, et saame tutvustada.
See üks on mõeldud esmapilgul vaadata segasena, kuid see üks on hämmastav.
Nii et see on andmestruktuur nimetatakse trie, trie, mis on päritud sõna leidmiseks,
mis ei hääldata uuesti proovida-val, kuid see, mida maailm kutsub neid asju. Proovib. T-r-i-e.
See on puu struktuuri mingisugune, kuid iga tippe trie
tundub olevat mida? Ja see on natuke eksitav, sest see on selline lühendatud.
Aga tundub iga sõlme see trie on tegelikult massiivi.
Ja kuigi autor seda skeemi ei ole tõendanud seda,
sel juhul see trie on andmestruktuur, mille eesmärk elus on salvestada sõnad
nagu-l-i-c-e või B-o-b.
Ja kuidas see info kauplustes Alice ja Bob ja Charlie ja Anita ja nii edasi
on ta kasutab massiivi, mille salvestada Alice trie,
alustame kell Juursõlme mis näeb välja nagu massiivi
ja see on kirjutatud stenografisti märke.
Autor jätta abcdefg sest puudusid nimed sellega.
Nad näitasid ainult M ja P ja T, kuid sel juhul,
liigume eemale Alice ja Bob ja Charlie, et mõned nimed, mis on siin.
Maxwell on tegelikult selles diagramm.
Kuidas siis autor poe M--x-w-e-l-l?
Ta alustas keskmes sõlme, ja läks [M], nii umbes 13, 13 asukohta massiiv.
Siis sealt, seal on osuti.
Pointer viib teise massiivi.
Sealt autor indekseeritud et reaga asukohta, mida on kujutatud seal üleval vasakul
ja siis ta järgneb, et kursor teise massiivi,
ja läks pointer asukoha X.
Siis järgmise massiivi asukoha W, E, L, L, ja nii edasi,
ja lõpuks, olgem tegelikult proovida panna pilt sellele.
Mida tähendab sõlme välja nagu koodi?
Sõlme trie sisaldab massiivi osuti rohkem tippe.
Aga seal on ka ju olema mingi tõeväärtuse, vähemalt selle rakendamises.
Satun nimetame seda is_word. Miks?
Sest kui sa sisestamist Maxwell, sa ei sisestamist
midagi sellele andmestruktuur.
Sa ei kirjuta M. Sa ei kirjuta X.
Kõik mida sa teed on pärast suunanäitajaks.
Pointer, mis tähistab M, siis osuti, mis tähistab,
siis osuti, mis tähistab X, siis W, E, L, L,
aga mida sa pead tegema, lõpus on omamoodi minna, vaadake, ma jõudnud sellesse asukohta.
Seal oli sõna, mis lõpeb siin andmestruktuur.
>> Mida trie on tõesti täis ja autor valis esindama
Nende terminuses vähe kolmnurgad.
See tähendab lihtsalt, et tegelikult on see kolmnurk on siin, see boolean väärtus tõene
tähendab, et kui te lähete tagasi puus,
mis tähendab sõna nimega Maxwell on selles.
Aga sõna foo, näiteks
ei ole puu, sest kui ma alustan kell Juursõlme siin üleval,
Pole f kursor ei o pointer, ei o pointer. Foo ei ole nime see sõnastik.
Aga seevastu Turingi, t-U-R-i-n-g. Jällegi, ma ei salvestada t või u või r või i või n või g.
Aga ma tegin kaupluse andmete struktuur väärtus tõene siia alla selle sõlme - puus
seades selle tõeväärtuse kohta is_word true.
Nii trie on selline väga huvitav meta struktuur,
kus sa ei ole tõesti ladustamiseks sõnad ise seda tüüpi sõnaraamatut.
Et asi oleks selge, sa oled lihtsalt ladustamiseks jah või ei, seal on sõna, mis lõpeb siin.
>> Nüüd mis see tähendas?
Kui teil on 150.000 sõnu sõnastikku, et sa üritad salvestada mällu
kasutades midagi seotud nimekirja,
sa ei kavatse on 150000 tippe oma seotud nimekirja.
Ja leida üks neist sõnadest tähestiku järgi võiks O (n) ajaga.
Lineaarne aeg. Aga kui siin trie,
Mis sõiduaega leida sõna?
Selgub, ilu on selles, et isegi kui sul on 149999 sõnad juba selles sõnaraamat,
kui rakendatakse käesoleva andmete struktuuri,
kui palju aega läheb aega, et leida või lisada veel üks inimene sellesse, nagu Alice, Alice?
Noh, see on ainult 5, ehk 6 samme, et lõpus on tühik.
Sest presense teiste nimede struktuuri
ei saa sel viisil sisestades Alice.
Lisaks leidis Alice kord on 150.000 sõnad selles sõnaraamat
ei saada oma teel leida Alice üldse
sest Alice on. . . . . siin, sest ma leidsin tõeväärtuse.
Ja kui ei ole tõeväärtus tõene, siis Alice ei ole selles andmestruktuur sõnu.
Teisisõnu, sõiduaega leida asju ja lisada asjad uude
andmete struktuuri trie on O - see ei ole n.
Sest presense 150.000 inimest ei mõjuta Alice tundub.
Nii et olgem kutsuvad seda k, kus k on maksimaalne pikkus sõna inglise keeles
mis on tavaliselt mitte rohkem kui 20-midagi tähemärki.
Nii et k on konstant. Nii et Püha Graal näib, et oleme leidnud nüüd
on see, et trie, pidev aega lisab, sest otsingud, kustutamiseks.
Kuna mitmed asjad juba struktuuris,
mis ei ole isegi füüsiliselt olemas. Jällegi, nad lihtsalt omamoodi kontrollitud maha, jah või ei,
ei mõjuta tema tulevasi sõiduaega.
>> Aga seal ju olema saagi, muidu me ei oleks raisata nii palju aega
kõigi nende teiste andmestruktuurid lihtsalt lõpuks ometi saladus üks, et on hämmastav.
Nii et mis hinnaga me pöörates seda saavutada ülevus siin? Space.
See asi on massiline. Ja põhjus, et autor
ei kujuta see siin, märkad, et kõik need asjad, mis näevad välja nagu massiivid,
ta ei tehta ülejäänud puud, ülejäänud trie,
sest nad lihtsalt ei puuduta lugu.
Aga kõik need sõlmed on super lai ja iga sõlme puu kulub
26 või tegelikult võiks olla 27 tähemärki, sest sel juhul ma ka ruumi ülakoma
nii et meil oleks apostrophized sõnu.
Sel juhul on need laia massiivid. Nii et kuigi nad ei picutured,
see võtab tohutu hulga RAM.
Milline võiks olla trahvi, especilly kaasaegse riistvara,
aga see on kompromiss. Me saame vähem aega veetes rohkem ruumi.
Nii et kui on see kõik läheb?
Noh, teeme ära - vaatame siin.
Teeme Hüppa see kutt siin.
>> Uskuge või mitte, sama palju rõõmu kui C on olnud juba mõnda aega,
me jõuda punktist semester, kus on aeg minna asju moodsam.
Asju kõrgemal tasemel. Ja kuigi järgmise paari nädala jooksul
me jätkuvalt kastke end maailma viiteid ja mälu haldamine
saada, et mugavus, millega saame siis toetuda,
aasta lõpus mäng on lõpuks tutvustada irooniliselt, mitte selles keeles.
Me kulutame, nagu 10 minutit räägime HTML.
Kõik HTML-is on märgistuskeel, ja mida märgistuskeel on
on need sarjad avatud sulgudes ja suletud sulgudes, et öelda "seda paksu"
"Seda kaldkirjas" "muuta see keskne."
See pole veel kõik, et intellektuaalselt huvitav, kuid see on super kasulik.
Ja see on kindlasti kõikjal nendel päevadel.
Aga mis on võimas umbes maailma HTML ja veebi programmeerimine üldisemalt
ehitab dünaamiline asju kirjalikult koodi keeltes nagu PHP või Python või Ruby või Java või C #.
Tõesti, sõltumata oma keele valik on, ja tekitavad HTML dünaamiliselt.
Luua midagi, mida nimetatakse CSS dünaamiliselt.
Kaskaadlaadistikke, mis on ka umbes esteetika.
Ja nii olgugi, täna, kui ma lähen teatud veebilehel nagu tuttav Google.com,
ja ma lähen, et näha, arendaja, et allikas, mis võib-olla olete teinud enne,
kuid läheb vaatamiseks allikas, seda kraami ilmselt tundub päris segasena.
Kuid see on aluseks koodi, mis rakendab Google.com.
Esiots. Ja tegelikult on see kõik kohev esteetika kraami.
See on CSS siin. Kui ma hoida kerimine alla lähme värvikoodiga asjad.
See on HTML. Google'i kood tundub jama, aga kui ma tegelikult avada erinevaid aknas
näeme mõningaid struktuur sellele.
Kui ma avada see üles, märkate siin, see on natuke paremini arusaadavaks.
Me näeme peagi seda tundnud, [sõna] on silt,
HTML, pea, keha, div, script, teksti ala, span, keskne, div.
Ja see on ka omamoodi segasena ilmega esmapilgul
kuid kõik see jama järgmiselt teatud mustrid ja korratav mustrid,
nii et kui saame põhitõdesid alla, on sul võimalik kirjutada koodi niimoodi
ja siis manipuleerida koodi niimoodi kasutades järjekordne keel, mida nimetatakse programmi JavaScript.
Ja JavaScript on keel, mis töötab sees brauseri
täna, et me kasutame Harvardi kursused, kursus shopping vahend, et Google maps kasutab
teile terve hunnik dünaamikat, Facebook annab teile näidata instant staatus värskendusi,
Twitter kasutab seda näidata tweets koheselt.
Kõik see hakkame kastke end sisse
Aga sinna jõuda, peame mõistma vähe midagi internetist.
See klipp on siin just minut pikk, ja oletame nüüd on see tegelikult
kuidas Internet töötab teaser, mida on umbes tulla. Ma annan sulle "Warriors of the Net."
>> [♫ Aeglane koori muusika ♫]
[Mees jutustaja] Ta tuli sõnum.
Koos protokolliga kõik omal.
[♫ Kiirem elektroonilise muusika ♫]
Ta tuli maailma jahe tulemüürid, uncaring ruuterid,
ja ohtudest palju hullem kui surm.
Ta on kiire. Ta on tugev. Ta on TCP / IP, ja ta sai oma aadress.
Warriors of the Net.
[Malan] Järgmisel nädalal siis. Interneti. Veebi programmeerimine. See on CS50.
[CS50.TV]