[Powered by Google Translate] [6 savaitė, Tęsinys]
[David J. Malan] [Harvardo universiteto]
[Tai CS50.] [CS50.TV]
Tai CS50 ir tai yra 6 savaitės pabaigos.
Taigi CS50x, vienas iš Harvardo universiteto pirmųjų kursuose dalyvaujančių EDX iniciatyva
iš tikrųjų debiutavo praėjusį pirmadienį.
Jei norėtumėte gauti, ką kiti žvilgsnis internete
dabar po kartu su, jūs galite galvą į x.cs50.net.
Kad bus nukreipti į tinkamą vietą edx.org
kuris buvo, kai šį ir kitus kursus, iš MIT ir Berkeley dabar gyvena.
Jūs turite užsiregistruoti sąskaitą, jūs rasite, kad medžiaga yra iš esmės tas pats
kaip jūs jau šį pusmetį, nors per kelias savaites vėluoja, kaip mes gauti viskas paruošta.
Bet tai, ką studentai CS50x dabar matome sąsaja labai patiko šį vieną.
Tai, pavyzdžiui, yra Zamyla pirmaujančių 0 problemą, žingsnis po žingsnio.
Po prisijungti į edx.org, CS50x studentas mato dalykų rūšių
būtų galima tikėtis pamatyti kursą: pirmadienį paskaitą,
paskaita trečiadienį, įvairių šortai, problema rinkiniai, Walkthroughs, PDF.
Be to, kaip čia matote, mašininio vertimo
iš anglų į kinų, japonų, ispanų, italų nuorašai,
ir visa krūva kitų kalbų, kad tikrai bus netobulas
kaip mes Roll juos programiškai naudojant kažką vadinama API
arba taikomųjų programų programavimo sąsaja iš "Google"
, kuri leidžia mums konvertuoti iš anglų į šių kalbų.
Tačiau dėka į nuostabų dvasios maždaug šimtą plius savanorių,
atsitiktinių žmonių internete, kurie maloniai pasiūlė įsitraukti
šiame projekte, mes palaipsniui gerėja šių vertimų kokybę
žmonės ištaisyti klaidas, kad padarė mūsų kompiuterius.
>> Taigi paaiškėja, iš mes turėjo keletą daugiau studentų pasirodyti pirmadienį, nei mes iš pradžių tikėjomės.
Iš tiesų, dabar CS50x turi 100.000 žmonių, kartu namuose.
Taigi suprantate, jūs visi esate dalis įžanginė klasė šio kurso informatikos
švietimo apskritai, o plačiau prieinama.
O realybė yra dabar, su kai kuriais iš šių masinių internetinių kursų,
jie visi pradėti su šiais labai daug, kaip mums atrodo, padarė čia.
Bet tikslas, galų gale, CS50x tikrai gauti kuo daugiau žmonių į finišo liniją, kaip įmanoma.
Konstrukcijos, CS50x bus siūlomi praeitą pirmadienį
per 15 Bal 2013 būdas, kad žmonės, kurie mokyklos įsipareigojimus kitur,
darbas, šeima, kiti konfliktai ir panašiai, turi šiek tiek daugiau lankstumo
su kuriuo būtų galima pasinerti į šį kursą, kuris, pakanka pasakyti,
gana ambicingai padaryti, jei tik per vos tris mėnesius per įprastą semestro metu.
Tačiau šie studentai bus spręsti ta pati problema rinkinius, peržiūrėti tą patį turinį,
turėti prieigą prie tų pačių šortai ir pan.
Taigi suprasti, kad mes visi esame iš tikrųjų tai kartu.
Ir vienas iš galutinių tikslų CS50x yra ne tik gauti kuo daugiau žmonės
į finišo liniją ir suteikti jiems šį naujai atrastą suprasti kompiuterių mokslo
ir programavimas, bet taip pat, kad jie turi šią dalijosi darbo patirtimi.
Vienas iš apibūdinančių 50 miesteliu, tikimės,
buvo tokios bendruomeninės patirties, geriau ar blogiau, kartais,
bet šie žmonės pasukti į kairę ir į dešinę,
ir darbo valandomis, ir hackathon ir teisingas.
Tai šiek tiek sunkiau padaryti, kad asmeniui su žmonių internete,
bet, CS50x bus baigtas balandžio pirmąjį CS50 Expo,
kuris bus interneto pritaikymas mūsų idėja teisinga
kur šie tūkstančiai studentų, visi bus kviečiami pateikti 1 - 2 minučių trukmės vaizdo,
arba jų galutinę projekto ar jų vaizdo Screencast garbanojimo Apie
ir kalbėti apie savo projektą ir jį demoing
panašiai kaip savo pirmtakų padarėme čia Campus mugėje
kad iki semestro pabaigos, tikimasi turėti pasaulinę parodą
studentų CS50x galutinių projektų, labai panaši į jus pasitiks šių metų gruodžio čia miesteliu.
Taigi daugiau, kad per ateinančius mėnesius.
>> Su 100.000 studentų, nors, ateina keletą KI.
Atsižvelgiant į tai, kad jus vaikinai Blazing takas čia ir atsižvelgiant CS50
kelias savaites iš anksto Ši medžiaga išleidimo žmonės dėl EDX,
suprasti, mes norėtume įtraukti į šią iniciatyvą, nes daugelis iš mūsų pačių studentų, kaip įmanoma,
tiek per pusmetį, taip pat šią žiemą ir šių metų pavasarį.
Taigi, jei norite įsitraukti į CS50x,
ypač prisijungs aptarti, CS50x CS50 aptarti EDX versija,
kurį daugelis iš jūsų buvo naudojant miesteliu, internetinė skelbimų lenta,
atlikite galvą į šį URL, leiskite mums žinoti, kas jūs esate,
nes mes norėtume sukurti tiek studentų ir darbuotojų ir dėstytojų komanda
su miesteliu, kurie tiesiog žaidžia kartu ir padėti.
Ir kai jie mato klausimą, kad susipažinę su jų,
išgirsite studentui apie kai kurių klaidų kažkur ten kai šalyje internete,
ir kad žiedai varpas, nes jūs taip pat turėjo tą pačią problemą
savo D-salėje prieš šiek tiek laiko, tikiuosi, tada galite varpelių ir pasidalinti savo patirtimi.
Taigi, prašome dalyvauti, jei norite.
>> Kompiuterių mokslo kursai Harvardo šiek tiek tradicija,
CS50 tarp jų, šiek tiek drabužių, kai kurie drabužiai, kad jūs galite dėvėti išdidžiai
semestrą pabaigoje, sakydamas gana išdidžiai, kad jūs baigėte CS50
ir paėmė CS50 ir panašiai, ir mes visada stengiamės įtraukti studentus
į šį procesą kaip įmanoma, pagal kurį mes kviečiame,
apie šio semestro metu studentai turi pateikti dizainą
naudojant Photoshop, ar kas pasirinkimo įrankis norite naudoti
jei esate dizaineris, pateikti dizaino marškinėliai ir palaidinės
ir skėčiai ir mažai spalvotos skarelės, šunims, dabar mes turime ir pan.
Ir viskas tada - nugalėtojai kasmet eksponuojami
aikštyno tinklalapyje store.cs50.net.
Savikaina, ten viskas yra parduodama, bet svetainė tik veikia
ir leidžia žmonėms pasirinkti spalvas ir dizainą, kad jiems patinka.
Taigi, aš maniau, mes norime tiesiog pasidalinti kai praėjusių metų dizaino
svetainėje be šio čia, kuris yra kasmetinė tradicija.
"Kiekvieną dieną aš Sekundes Faultn" buvo vienas iš pateiktos pastabos ir pernai,
kuri dar absolventai.
Mes turėjome šį vieną, CS50, įkurta 1989 m. "
Vienas iš mūsų Bowdens, Rob, praėjusiais metais buvo labai populiarus.
"Komandos Bowden" gimė, šis projektas buvo pateiktas, tarp geriausių pardavėjų.
Kaip buvo tai vienas čia. Daugelis žmonių turėjo "Bowden Fever" pagal pardavimo rąstų.
Suprantu,, kad dabar gali būti jūsų projektas internete.
Daugiau informacijos apie tai kitą problemą rinkiniai ateiti.
>> Dar vienas įrankis: jūs turėjo tam tikrą poveikį ir, tikiuosi, dabar
kai rankas ant patirtis su GDB,
kuris, žinoma, Debugger ir leidžia manipuliuoti
jūsų programa gana žemo lygio, daryti tai, ką rūšių dalykų?
Ką GDB jums tai padaryti?
Taip? Duoti man ką nors. [Studentų atsakymas, nesuprantamas]
Geras. Žingsnis į funkciją, todėl jūs ne tik turėsite įrašyti paleisti
ir per visą programos smūgį, spausdinimo iš dalykų, į standartinį išvedimą.
Priešingai, jūs gali žingsnis, per jį linija, arba rašyti kitą
eiti liniją kiekvieną eilutę po eilutės ar pakopą, pasinerti į funkciją, paprastai vienas, kad jūs rašė.
Ką dar GDB jums tai padaryti? Taip? [Studentų atsakymas, nesuprantamas]
Spausdinti kintamuosius. Taigi, jei norite padaryti šiek tiek savistaba viduje savo programą
be imtis rašyti printf pareiškimus visur,
galite tiesiog atspausdinti kintamojo arba rodyti kintamąjį.
Ką dar galite daryti su kaip GDB debugger?
[Studentų atsakymas, nesuprantamas]
Tiksliai. Galite nustatyti ribines vertes; pertraukos vykdymą galite pasakyti
pagrindinės funkcijos arba foo funkcija.
Galite pasakyti, pertraukos vykdymą eilutėje 123.
Ir atskaitos taškas yra tikrai galinga technika
nes jei turite plačiąja prasme, kur jūsų problema
tikriausiai yra, jūs neturite gaišti laiko žengia per programos visas.
Galite iš esmės šokinėti teisę ten ir tada pradėkite rašyti
žengia per jį žingsnis ar kitą arba panašūs.
Bet su kažką panašaus GDB laimikis yra tai, kad jis padeda jums, žmogaus,
rasti savo problemas ir rasti savo klaidas.
Tai nebūtinai juos rasti tiek daug už jus.
>> Taigi, mes pristatė kitą dieną style50, kuris yra trumpas komandų eilutės įrankis
kad bando Stilizuoti savo kodą ir šiek tiek daugiau švariai, nei jūs, žmogaus, gali būti padaryta.
Bet, taip pat, yra tikrai tik estetinis dalykas.
Tačiau paaiškėja, ten tai įrankis, vadinamas Valgrind, kad yra šiek tiek daugiau paslaptingų naudoti.
Pirmo žvilgsnio jos produkcija yra atrociously paslaptingas.
Bet tai nuostabiai naudinga, ypač dabar, kad mes termino
kur jūs pradedate naudoti malloc ir dinaminis atminties paskirstymas.
Dalykai gali eiti tikrai, tikrai negerai greitai.
Nes jei tu pamiršai išlaisvinti savo atmintį, arba šiek tiek dereference NULL žymiklį,
ar jums dereference šiek tiek šiukšlių žymeklį, tai, kas paprastai yra simptomas, kad rezultatai?
Seg kaltės. Ir gausite šį pagrindinį failą kai kilobaitų ir megabaitų
, kuri atstovauja savo programos atminties būsena, kai jis sudužo,
bet jūsų programa galiausiai seg gedimus, segmentavimo kaltės,
, o tai reiškia, kažkas blogo atsitiko beveik visada yra susijusi
atminties klaida, kad jūs padarėte kažkur.
Taigi Valgrind padeda jums rasti dalykų, pavyzdžiui,.
Tai priemonė, kuri leidžia paleisti, kaip GDB, kai jūs parengė savo programą,
o kaip paleisti programą tiesiai, paleidus Valgrind
ir jums pereiti į savo programą, kaip ir jūs su GDB.
Dabar, naudojimas, siekiant gauti geriausią rūšies produkcijos,
yra šiek tiek ilgai, todėl teisę ten ant ekrano jums pamatyti Valgrind-v.
"-V" reiškia beveik visuotinai vedant, kai jūs naudojate programas "Linux" kompiuteryje.
Taigi, tai reiškia, kad išspjauti daugiau duomenų, nei galite pagal nutylėjimą.
"- Nuotėkio = visas." Tai tiesiog pasakyti patikrinti visų galimų atminties nutekėjimas,
klaidų, kad aš galėjo padaryti. Tai taip pat yra paplitusi paradigma su Linux programų.
Apskritai, jei turite komandinės eilutės argumentas, kad "jungiklis"
tai turėtų pakeisti programos elgesį, ir tai vienos raidės,
tai-v, bet jei, įjungiama, tiesiog dizaino programuotojas,
yra visą žodį arba žodžių seka, komandinės eilutės argumentas prasideda.
Tai tik žmogaus konvencijas, bet pamatysite juos vis labiau.
Ir tada, pagaliau, "a.out" yra savavališkai Šiame konkrečiame pavyzdyje programos pavadinimas.
Ir štai kai atstovas produkcija.
>> Prieš mes pažvelgsime, ką tai gali reikšti, kad, leiskite man pereiti prie kodo fragmentą, per čia.
Ir leiskite man perkelti šią iš kelio, netrukus
ir galime imtis kambarį memory.c, kuri yra tai trumpas pavyzdys čia atrodo.
Taigi, leiskite man šioje programoje priartinti funkcijų ir klausimus.
Mes turime pagrindinę funkciją, kad vadina funkciją, f,
ir kas tada f tęsti padaryti, šiek tiek techninės anglų?
Ką f pradėti daryti?
Kaip apie pradėsite su 20 eilutėje, ir žvaigždės vieta nesvarbu,
bet aš tiesiog būti suderintos su praėjusiais paskaitą.
, Kas 20 eilutėje už mus? Kairėje pusėje. Mes ją padalyti toliau.
Int * x: ką daryti?
Gerai. Tai skelbiantis žymeklis, ir dabar galime būti dar labiau techninio pobūdžio.
Ką tai reiškia, labai konkrečiai, paskelbti rodyklę? Kažkas kitas?
Taip? [Studento atsakymas, nesuprantamas] per toli.
Taigi jūs skaitote dešinėje lygybės ženklą.
Sutelkime tik kairėje pusėje, tiesiog int * x.
Tai reiškia "paskelbti" rodyklę, bet dabar galime pasinerti giliau į šį apibrėžimą.
Ką tai konkrečiai, techniškai reiškia? Taip?
[Studentų atsakymas, nesuprantamas]
Gerai. Jis ruošiasi įrašyti adresą atmintyje.
Geras. Ir Paimkime vieną žingsnį toliau, tai deklaruojant kintamąjį x, tai 32 bitai.
Ir aš žinau, tai 32 bitų, nes?
Tai ne todėl, kad int, nes tai, kad šiuo atveju rodyklė.
Sutapimas, kad tai vienas ir tas pats su int
bet faktas, kad yra žvaigždė reiškia, kad tai rodyklė
ir į prietaisą, su daug kompiuterių, bet ne visi, patarimų yra 32 bitai.
Moderni įranga, pavyzdžiui, naujausias "Mac", naujausi kompiuteriai, jūs galite turėti 64-bitų patarimų,
bet į prietaisą, šie dalykai yra 32 bitai.
Taigi mes standartizuoti, kad. Konkrečiau, sakoma taip:
Mes "paskelbti" rodyklę, ką tai reiškia?
Mes ruošiame saugoti atminties adresą.
Ką tai reiškia?
Mes sukurti kintamą vadinama X, kuri užima 32 bitus
kad netrukus saugoti sveikasis skaičius adresą.
Ir tai tikriausiai taip tiksliai, kaip mes galime gauti.
Tai gerai, judėti į priekį supaprastinti pasaulį ir tiesiog pasakyti paskelbti žymeklį vadinama X.
Paskelbti žymeklį, tačiau suvokti ir suprasti, kas iš tikrųjų vyksta
net tik tuos keletą simbolių.
>> Dabar, tai vienas beveik šiek tiek lengviau, nors tai ilgiau išraiška.
Taigi, kas tai daro, kad dabar bus paryškinta: "malloc (10 * sizeof (int));" Taip?
[Studentų atsakymas, nesuprantamas]
Geras. Imsiu jį ten. Tai skiriant dešimt sveikųjų skaičių iš atminties riekė.
O dabar leisk pasinerti šiek tiek giliau, tai skiriant dešimt sveikųjų skaičių atminties riekė.
Kas yra malloc tada grįžti?
Tos riekė adresas, arba, konkrečiau, tos riekė pirmojo baito adresas.
Kaip tada aš, programuotojas, žinoti, kur riekė, kad atminties baigiasi?
Žinau, kad tai gretutinė. Malloc, pagal apibrėžimą, duos jums vientisą atminties riekė.
Nėra spragų. Jūs turite prieigą prie kiekvieno toje riekė baitas,
atgal atgal atgal, bet kaip man žinoti, kur šios atminties riekė pabaiga?
Kai naudojate malloc? [Studento atsakymas, nesuprantamas] Geras.
Jūs neturite. Jūs turite prisiminti.
Turiu prisiminti, kad aš vertę 10, o aš net atrodo, padarė, kad čia.
Bet pareiga yra tik ant manęs. Strlen, kurį mes jau šiek tiek priklauso nuo stygos,
veikia tik todėl, kad šios konvencijos \ 0
ar šis specialus nul charakteris, NUL, eilutės pabaigoje.
Kad neturi tik savavališkai gabaliukus atmintimi.
Tai priklauso nuo jūsų. Taigi, 20 eilutėje, tada skiria atminties riekė
kad galima laikyti dešimt sveikieji skaičiai, ir ji saugo pirmojo baito adresas
tos atminties kintamojo vadinama X riekė.
Ergo, kuris yra rodyklė. Taigi eilutę 21, deja, buvo klaida.
Bet pirmiausia, kas tai daro? Tai sakydamas, 10, 0 indeksuojami buvimo vietos parduotuvėje,
atminties riekė, x vertė 0.
>> Taigi pastebėti keletą dalykų vyksta.
Net jei x yra rodyklė, prisiminti iš prieš porą savaičių
, kad jūs vis dar galite naudoti masyvo stiliaus kvadratinių laikiklis žymėjimą.
, Nes tai iš tikrųjų labiau paslaptingas orientuotą rodyklių aritmetinis trumpas ranka notacijos.
kur mes padaryti kažką panašaus į tai: Paimkite adresų x perkelti 10 Dėmelės
tada ten kokia adresas yra saugomas toje vietoje.
Bet atvirai, tai tik žiaurią skaityti ir gauti patogiai.
Taigi pasaulis paprastai naudoja skliaustus, tik todėl, kad tiek daug daugiau žmonių draugiškas.
Bet tai, kas iš tikrųjų vyksta po gaubtu;
x yra adresas, masyvas, per se.
Todėl tai saugoti 0 x 10 vietą.
Kodėl tai yra blogai? Taip?
[Studento atsakymas, nesuprantamas] Būtent.
Mes tik skyrė dešimt int, bet mes skaičiuojame nuo 0, kai Programming in C,
todėl jūs turite prieigą prie 0 1 2 3 4 5 6 7 8 9, bet ne 10.
Taigi, arba programa seg kaltės ar tai ne.
Bet mes ne tikrai žinote, tai yra tarsi iš niezdeterminowane elgesį.
Tai tikrai priklauso nuo to, ar mes pasisekė.
Jei paaiškėja, kad operacinė sistema neturi proto, jei aš naudoju, kad papildomų baitas,
, nors ji nedavė man, mano programa gali strigti.
Tai žalias, tai Buggy, bet jūs negalite matyti, kad simptomas,
arba jūs galite pamatyti tik vieną kartą, o.
Tačiau tikrovė yra tokia, kad problema yra, iš tikrųjų, yra.
Ir tai tikrai problema, jei jūs parašiau programą, kurią norite būti teisinga,
kad jūs pardavė programą, kad žmonės naudojasi, kad kiekvieną kartą, o sugenda
nes, žinoma, tai nėra gerai. Iš tiesų, jei turite "Android" telefoną ar "iPhone"
ir jums atsisiųsti programas šių dienų, jei jūs kada nors turėjo app tiesiog mesti,
visi staiga ji išnyksta, tai beveik visada kai kurių atminties susijusiu klausimu,
, kurią programuotojas įsukus ir dereferenced rodyklę
, kad jis neturėtų, ir iOS arba Android rezultatas yra tiesiog viso nužudyti programą
o ne rizikos neapibrėžtas elgesio ar kažkokia Įsibrovimo.
>> Yra viena kita klaida šioje programoje, ne tik šį vieną.
Ką dar aš įsukus šioje programoje?
Aš ne praktikuojama, ką aš pamokslavo. Taip?
[Studento atsakymas, nesuprantamas] Geras.
Aš ne išlaisvino atmintį. Taigi nykščio taisykle dabar
turi būti, kada jūs vadinate malloc, turite skambinti nemokamai, kai baigsite, naudojant šią atmintį.
Dabar, kai aš noriu išlaisvinti šią atmintį?
Tikriausiai, darant prielaidą, kad pirmoji eilutė buvo teisinga, aš norėtų tai padaryti čia.
Nes aš negalėjau, pavyzdžiui, padaryti jį žemyn. Kodėl?
Tik iš taikymo srities. Taigi, nors mes kalbame apie rodykles,
tai per savaitę, 2 ar 3 klausimas, kur x yra tik savo apimtimi, viduje, kur ji buvo paskelbta Garbanotasis petnešos.
Taigi, jūs tikrai negali išlaisvinti jį ten. Mano vienintelis šansas išlaisvinti yra maždaug po eilutę 21.
Tai yra gana paprasta programa, tai buvo gana lengva, kai jūs rūšies suvynioti savo mintis
apie tai, ką programa daro, kur klaidas.
Ir net jei jums nebuvo matyti ne pirmas, tikiuosi, ji šiek tiek akivaizdu dabar
kad šios klaidos yra gana lengvai išsprendžiama ir lengvai.
Bet, kai programa yra daugiau nei 12 eilučių ilgio, tai 50 eilučių ilgio, 100 eilučių ilgio,
vaikščioti per savo kodo eilutę po eilutės, galvoju per ją logiškai,
yra įmanoma, tačiau ne itin smagu daryti, nuolat ieško už klaidas,
ir tai taip pat sunku padaryti, ir tai, kodėl, kaip Valgrind įrankis.
Leiskite man eiti į priekį ir tai padaryti: leiskite man atidaryti savo terminalo langą,
ir neleisk man tiesiog paleisti atminties, nes visa atmintis atrodo gerai.
Gaunu pasisekė. Ėjimas į tą papildomą baitą masyvo pabaigos
neatrodo, kad pernelyg sudėtinga.
Bet vis dėlto, leiskite man padaryti normalumas patikrinti, kuris tiesiog reiškia, patikrinti
, ar iš tikrųjų tai yra teisinga.
>> Taigi darykime Valgrind-v - nuotėkio patikrinti = visas,
ir tada šiuo atveju programos pavadinimas yra atmintyje, o ne a.out.
Taigi leiskite man eiti į priekį ir tai padaryti. Paspauskite Enter.
Brangus Dieve. Tai jos produkcija, ir tai, ką aš užsiminiau anksčiau.
Tačiau, jei jūs išmoksite skaityti čia per nesąmonė,
dažniausiai tai yra tiesiog diagnostikos produkcija, tai ne, kad įdomu.
Kokios reikia jūsų akiai tikrai nori būti ieškote yra kokia nors klaida arba neteisingas paminėti.
Žodžiai, rodančių problemas.
Ir iš tiesų, galime pamatyti, kas vyksta neteisingai žemyn čia.
Turiu tam tikros rūšies santrauką, "naudojant išvežimo. 40 baitų 1 blokus"
Aš tikrai ne tikras, ką blokas dar, bet 40 baitų
iš tikrųjų mano, kaip aš galėtų išsiaiškinti, kur, kad ateina iš.
40 baitų. Kodėl 40 baitų išvežimo naudojimui?
O tiksliau, jei mes slinkti žemyn čia,
kodėl aš tikrai prarado 40 baitų? Taip?
[Studento atsakymas, nesuprantamas] Perfect. Taip, tiksliai.
Ten buvo dešimt sveikieji skaičiai, o kiekvienas iš jų yra dydis 4, arba 32 bitų,
todėl Pamečiau arba neatsimenu tiksliai 40 baitų, nes, kaip siūloma, aš ne vadinamų laisvaisiais.
Kad viena klaida, o dabar pažvelkime šiek tiek žemyn, toliau ir pamatyti šalia,
"Negalioja rašyti 4 dydžio." Dabar kas tai yra?
Šis adresas yra išreiškiamas kokie atskaitos notacijos, matyt?
Tai yra šešioliktainis, ir, bet kuriuo metu galite pamatyti skaičių pradedant 0x,
tai reiškia, šešioliktainis, kuriems mes radome kelią atgal, manau, klausimų pset 0 skyriuje,
kuris buvo tiesiog padaryti WarmUp naudotis, konvertuoti dešimtainės į šešioliktainį į dvejetainį ir pan.
Šešioliktainis, tiesiog žmogaus konvencijos, paprastai naudojamas atstovauti patarimų
arba, apskritai, adresus. Tai tik konvencija,
, nes tai šiek tiek lengviau skaityti, tai šiek tiek daugiau kompaktiškas nei kažką panašaus dešimtosios,
ir dvejetainiai dauguma žmonių yra nenaudingas naudoti.
Taigi, dabar, ką tai reiškia? Na, atrodo, kad yra neteisingas rašyti
dėl memory.c 21 eilutėje 4 dydžio.
Taigi, grįžkime į eilutę 21, ir iš tikrųjų, čia yra tai, kad neteisingas rašyti.
Taigi Valgrind nesiruošia turėti savo ranką ir pasakykite man, ką nustatyti yra
tačiau ji aptinka, kad aš darau neteisingą rašyti.
Aš neliesti 4 baitai, kad aš ne, ir, matyt, tai todėl, kad,
kaip Jūs nurodėte, aš darau, o ne [9] [10] maksimaliai
[0] ar kažkas tarp.
Su Valgrind, supranta, kad bet kuriuo metu, jūs dabar rašymo programą
, kuri naudoja patarimų ir naudoja atmintį ir malloc tiksliau,
tikrai gauti į įpročiai veikia ši ilgai
bet labai lengvai nukopijuoti ir įklijuoti vadovavimą Valgrind
norėdami pamatyti, jei yra keletas klaidų, ten.
Ir tai bus didele kiekvieną kartą pamatysite produkcijos,
bet tik išanalizuoti per vizualiai visos produkcijos, ir pamatyti, jei jūs matote mini klaidų
ar įspėjimus arba neteisingas arba prarasti.
Bet kurie žodžiai atrodykite, kad jūs įsukus kažkur.
Taip suprasti, kad yra nauja priemonė, savo priemonių rinkinį.
>> Dabar pirmadienį, mes turėjome visa krūva žmonių sugalvoti čia
ir atstovauja susietą sąrašą sąvoką.
Ir mes pristatė susietą sąrašą kaip išspręsti kokia problema?
Taip? [Studento atsakymas, nesuprantamas] Geras.
Matricos negali turėti atminties prie jų pridėti.
Jei jums skirti, dydis 10, tai visi jums masyvo.
Galite skambinti, jei jūs iš pradžių malloc kaip realloc funkciją,
ir kad gali bandyti augti masyvas, jei yra vietos link jo pabaigos
, kad niekas kitas naudoja, o jei jų nėra, tai bus tiesiog rasti jums didesnį gabalą kažkur kitur.
Bet tada ji bus nukopijuoti visi iš tų baitų į naują masyvą.
Tai skamba kaip labai teisingą sprendimą.
Kodėl tai yra nepatraukli?
Aš turiu galvoje, tai veikia, žmonės išsprendė šią problemą.
Kodėl mes turime ją išspręsti Pirmadienį, susijusius sąrašus? Taip?
[Studentų atsakymas, nesuprantamas] Tai gali užtrukti ilgą laiką.
Iš tiesų, bet kuriuo metu, jūs skambinate malloc arba realloc arba calloc, kuris yra dar vienas,
bet kada, programa, kalbame su operacine sistema,
jūs linkę sulėtinti programą.
Ir jei jūs darote šių dalykų kilpų rūšių, jūs tikrai lėtėja dalykų žemyn.
Jūs esate nesiruošia pastebėti tai paprasčiausias "Hello World" tipo programomis,
bet daug didesnių programų, prašydami operacinę sistemą iš naujo ir vėl iš atminties
arba suteikiant jai vėl ir vėl, paprastai negali būti geras dalykas.
Be to, tai tiesiog tarsi intelekto - tai visiškas laiko švaistymas.
Kodėl reikia skirti vis daugiau ir daugiau atminties, rizikos kopijuoti viską į naują masyvo,
jei turite alternatyvą, kuri leidžia jums skiria tik tiek, kiek atminties, kaip jūs iš tikrųjų reikia?
Todėl nėra čia pliusų ir minusų.
Vienas iš pliusų yra tai, kad mes turime dinamiškumą.
Nesvarbu, kur atminties gabaliukus, kurie yra laisvi,
Aš galiu tik rūšiuoti sukurti šių duonos trupinius per rodykles
styginių visą mano susietą sąrašą kartu.
Bet aš mokėti bent vieną kainą.
>> Ką aš turiu mesti įgyti, susijusius sąrašus?
Taip? [Studento atsakymas, nesuprantamas] Geras.
Jums reikia daugiau atminties. Dabar man reikia erdvės šiuos patarimus,
ir šio super paprasta susijęs sąrašą
kad tik bando laikyti sveikieji skaičiai, kurie yra 4 baitų, mes nuolat sako
gerai, rodyklė yra 4 baitų, todėl dabar aš tiesiog dvigubai
atminties kiekis man reikia tiesiog išsaugoti šį sąrašą.
Bet vėl, tai yra nuolatinis kompromisas kompiuterių mokslo
tarp laiko ir erdvės požiūriu plėtros, pastangų ir kitų išteklių.
Kaip dar naudojant susietą sąrašą neigiama? Taip?
[Studentų atsakymas, nesuprantamas]
Geras. Ne taip lengva naudotis. Mes nebegalime sverto
savaitę 0 principus kaip skaldyk ir valdyk.
O tiksliau, dvejetainis paieškos. Nes, nors mes, žmonės
galite pamatyti maždaug, kur šio sąrašo viduryje yra,
kompiuteris tik žino, kad šis sąrašas prasideda adresu vadinama pirmoji.
Ir kad 0x123 ar kažkas panašaus.
Ir vienintelis būdas programa gali rasti vidurinį elementą
yra iš tikrųjų ieškoti visą sąrašą.
Ir net tada, jis tiesiog turi ieškoti visą sąrašą, nes
net kai jūs pasieksite vidurinįjį elementą, po patarimų,
jūs, programa, neįsivaizduoju, kiek laiko šis sąrašas, gali,
kol paspausite jo pabaigoje, ir kaip jūs žinote, programiškai
, kad esate tuo susietą sąrašo pabaigoje?
NULL pointeris yra speciali, todėl vėl konvencija.
O ne naudoti šį žymeklį, mes tikrai nenori būti šiek tiek šiukšlių vertė
nukreipta nuo scenos kažkur, mes norime, kad ji būtų ranka žemyn, NULL,
kad mes turime šį terminus šios duomenų struktūros, todėl mes žinome, kur jis baigiasi.
>> Ką daryti, jei norime valdyti?
Šį vizualiai mes padarėme, ir su žmonėmis,
bet ką daryti, jei mes norime padaryti įterpties?
Taigi pradinis sąrašas buvo 9, 17, 20, 22, 29, 34.
Ką daryti, jei po to mes norėjome malloc erdvėje skaičius 55, už tai mazgo,
, tai mes norime įterpti į sąrašą, tiesiog, kaip mes padarėme, pirmadienį 55?
Kaip mes tai darome? Na, Anita atėjo ir ji iš esmės vaikščiojo sąrašą.
Ji pradėjo pirmąjį elementą, tada kitas, kitas, kitas, kitas, kitas.
Pagaliau paspauskite kairįjį visą kelią žemyn
ir supratau, oh, tai yra NULL. Taigi, kas rodyklė manipuliacija reikia padaryti?
Asmuo, kuris buvo pabaigos, tačiau skaičius 34, reikia jo kaire ranka iškėlė
taško, esančio 55, 55 reikia savo kairę ranką žemyn nukreiptą bus naujas NULL terminatorius. Atlikta.
Gana lengva įterpti 55 į rūšiuotų sąrašą.
Ir kaip tai galėtų atrodyti?
>> Leiskite man eiti į priekį ir atverti šiek tiek kodo pavyzdį čia.
Aš atverti gedit ir leiskite man atidaryti du failus pirmą kartą.
Vienas iš jų yra list1.h, ir leiskite man tiesiog priminti, kad tai buvo kodo riekė
kad mes naudojamas atstovauti mazgas.
Mazgas turi tiek int vadinamos N ir rodyklę, pavadintą kitą, kad tik taškai į kitą dalyką sąraše.
Kad dabar yra H failo. Kodėl?
Ši konvencija, ir mes iki šiol nepasinaudojo tai didžiulis patys,
bet tas, kas rašė printf ir kitas funkcijas
davė kaip dovaną į pasaulį iš šių funkcijų raštu failą pavadinimu stdio.h.
Ir tada ten string.h ir tada ten map.h, ir ten visi šie h failai
, kad jūs galėjote pastebėti ar per kitų žmonių termino raštu.
Paprastai tie h failai yra tik tai, kas, pavyzdžiui, tikrų tipų
arba pareiškimai nestandartinių tipų ar konstantų deklaracijų.
Jums nereikia įdėti funkcijų "įgyvendinančius header files.
Jūs galėsite įdėti, o ne tik savo prototipus.
Jūs įdedate ką norite pasidalinti su pasauliu, tai, ko jiems reikia
siekiant sudaryti savo kodą. Taigi, tiesiog patekti į šio įpročio,
mes nusprendėme padaryti tą patį. Yra ne daug list1.h
bet mes įdėti kažką, kad gali būti įdomūs žmonėms pasaulyje
kurie nori naudotis mūsų susietą sąrašo įgyvendinimu.
Dabar, list1.c aš ne eiti per visas šis dalykas
, nes jis šiek tiek per ilgas, ši programa, bet tegul ją paleisti realus greitai greitai.
Leiskite man sudaryti List1, leiskite man paleiskite List1 ir ką jūs pamatysite
Mes imituoti paprastą maža programa Čia
kad vyksta leiskite man pridėti ir pašalinti numerius į sąrašą.
Taigi leiskite man eiti į priekį ir 3 tipo meniu 3 variantas.
Norite įterpti skaičių - darykime Pirmasis numeris, kuris buvo 9,
ir dabar aš sakė, sąrašas dabar yra 9.
Leiskite man eiti į priekį ir padaryti kitą įterpti, kad aš paspauskite meniu 3.
Ką skaičių aš noriu įterpti? (17)
Įveskite. Ir aš padarysiu tik dar vienas.
Leiskite man įrašyti skaičių 22.
Taigi mes turime iš susietų sąrašą, kad mes turėjome prieš skaidrių forma momentas pradžia.
Kaip tai įterpimas iš tikrųjų vyksta?
Iš tiesų, 22 šiuo metu yra sąrašo pabaigoje.
Taigi istorija papasakojo apie pirmadienį etape ir recapped tik dabar
turi būti iš tikrųjų vyksta kodą.
Leiskite pažvelgti. Leiskite man slinkti žemyn į šį failą.
Mes Koloryzować kai kurių funkcijų,
bet mes eiti, tarkim, įterpti funkciją.
>> Pažiūrėkime, kaip mes einame apie Į šią susietą sąrašą įtraukti naują mazgas.
Kur yra sąrašas paskelbė? Ką gi, pereikite visą kelią iki viršuje
ir pastebiu, kad mano susijęs sąrašas iš esmės yra deklaruojamas kaip vienas žymeklis, kad iš pradžių NULL.
Taigi, aš naudojant pasaulinį kintamąjį,, kurias paprastai mes pamokslavo prieš
nes ji daro jūsų kodas šiek tiek nepatogus, išlaikyti,
tai tarsi tingus, paprastai, bet tai ne tingus ir tai nėra blogai ir tai nėra blogai
jei jūsų programa vienintelis gyvenimo tikslas yra imituoti vieną susijusią sąrašą.
Būtent tai, ką mes darome.
Taip, o ne pranešti apie tai pagrindinis ir tada turi perduoti jį į kiekvieną funkciją
mes parašiau šioje programoje, mes, o ne suprasti, oh, galime tiesiog padaryti jį pasaulio
nes visa šios programos tikslas yra parodyti, vienas ir tik vienas susijęs sąrašą.
Taigi, kad jaučiasi gerai. Čia yra mano prototipus, ir mes negalime eiti per visą šių
bet aš parašiau "Delete funkcija, rasti funkcijos, įterpti funkciją, ir skersiniu funkciją.
Bet tegul dabar eiti atgal įterpti funkciją
ir pamatyti, kaip tai vienas čia dirba.
Intarpas yra on-line - čia mes einame.
Įterpti. Todėl ji neturi imtis jokių argumentų, nes mes ketiname paklausti
vartotojo viduje šio telefono numeris, kurį norite įterpti funkciją.
Bet pirmiausia, mes ruošiamės suteikti jiems šiek tiek vietos.
Tai tarsi kopijuoti ir įklijuoti iš kitos, pavyzdžiui.
Tokiu atveju, mes buvo skirti int Šiuo metu mes skirti mazgas.
Aš tikrai ne prisiminti, kiek baitų mazgas, bet tai gerai.
Sizeof gali suprasti, kad už mane.
Ir kodėl aš patikrinti for null linija 120?
Kas galėtų suklysti 119 atitinka? Taip?
[Studentų atsakymas, nesuprantamas]
Geras. Tik galėtų būti atvejis, kad aš paprašė per daug atminties
arba kažkas negerai ir operacinė sistema neturi pakankamai baitų duoti man,
todėl nurodo, kiek grąžinant NULL, ir jei aš ne patikrinti, ar
ir aš tiesiog aklai tęsti naudoti, adresas grįžo, tai gali būti NULL.
Tai gali būti kai nežinoma vertė, nėra geras dalykas, nebent aš -
iš tikrųjų nebus nežinoma vertė. Ji gali būti lygi NULL, todėl aš nenoriu
ja piktnaudžiauti ir rizikos dereferencing jį.
Jei tai atsitiks, aš tiesiog grįžti ir mes apsimesti, kaip aš ne grįžti jokios atminties.
>> Kitaip, sakau vartotojui man duoti numerį norite įterpti, aš vadinu Mūsų senas draugas GetInt,
ir tada tai buvo nauja sintaksė, mes pristatė pirmadienį.
"Newptr-> n 'reiškia, adresą, kurį buvo suteikta malloc
kuris yra pirmas baitas naujas mazgas objekto,
ir tada eiti į lauką, vadinamas n.
Mažai smulkmenos klausimas: Tai atitinka, ką dar paslaptingas eilutę kodo?
Kaip kitaip galėčiau tai parašiau? Nori imtis Pabandyti?
[Studentų atsakymas, nesuprantamas]
Geras. Naudojant N, bet tai ne visai taip paprasta, kaip šis.
Ką aš pirmiausia reikia daryti? [Studentų atsakymas, nesuprantamas]
Geras. Man reikia daryti * newptr.n.
Taigi tai sako nauja rodyklė akivaizdžiai adresas. Kodėl?
Nes jis buvo grąžintas malloc. * Newptr sako: "ten,"
ir tada, kai jūs ten, tada jūs galite naudoti daugiau susipažinę N,
bet tai tik atrodo šiek tiek negraži, mes, žmonės, ypač jei ketinate
atkreipti patarimų su rodyklėmis visą laiką, pasaulis turi būti standartizuotas pagal šią rodyklę, notacijos,
kuris daro lygiai tą patį.
Taigi jums reikia tik naudoti -> žymėjimą, kai kairėje dalykas yra rodyklė.
Kitaip, jei tai tikrasis struct, naudokite n.
Ir tada tai: Kodėl aš inicijuoti newptr-> Kitas NULL?
Mes nenorime, kabančios kairę ranką etapo pabaigoje.
Mes norime, kad ji nukreipta tiesiai žemyn, o tai reiškia šio sąrašo pabaigą
potencialiai gali būti mazgo, todėl mes geriau įsitikinti, ar jis yra NULL.
Ir apskritai, Inicijuojama kintamuosius arba savo duomenų nariai ir structs
kažkas yra tiesiog gera praktika.
Tik nuomos šiukšlių egzistuoja ir toliau egzistuoja paprastai pasireiškia jums į bėdą
jei pamiršote kažką daryti vėliau.
>> Štai keletas atvejų. Tai, vėlgi, yra įterpti funkciją,
ir pirmas dalykas, aš patikrinti, jei kintamasis vadinamas
pasaulio kintamasis yra NULL, tai reiškia, kad nėra susijęs sąrašas.
Mes neįdėta jokių numerius, todėl trivialus įterpti šį numerį
į sąrašą, nes jis tiesiog priklauso sąrašo pradžioje.
Taigi tai buvo Anita tik atsistojus čia vienas, apsimesdami
niekas kitas čia ant scenos, kol skyrėme mazgas,
tada ji galėtų pakelti ranką pirmą kartą,
jei visi kiti atėjo į sceną po jos pirmadienį.
Dabar čia, tai yra šiek tiek patikrinti, kur aš turiu pasakyti, jei naujas mazgas vertė n
<n vertę dabartinėje pirmojo mazgo,
tai reiškia, kad yra susijusi sąrašas, kurį pradėjo.
Yra bent vienas mazgas sąraše, tačiau šis naujas vaikinas
priklauso prieš jį, todėl mes turime judėti dalykų aplink.
Kitaip tariant, jei tik sąrašas pradėjo su, tarkim,
tik numeris 17, tai - iš tiesų, mes galime tai padaryti aiškiai.
Jei pradėsime savo istoriją su rodykle čia vadinama pirmoji,
ir iš pradžių tai NULL, ir mes įterpti skaičių "9",
numeris 9 aiškiai priklauso sąrašo pradžioje.
Todėl galime apsimesti, mes tiesiog malloced adresą ar numerį 9 ir įdėti jį čia.
Jei pirmasis yra 9 pagal nutylėjimą, Pirmasis scenarijus aptarėme tiesiog reiškia, tegul tašką Šis vaikinas,
palikti tai kaip yra NULL, dabar mes turime numeris 9.
Kitas numeris norime įterpti yra 17.
17 priklauso per čia, todėl mes ketiname padaryti tam tikrą loginį žingsninis per šį.
Taigi, tegul vietoj to, prieš tai darome, galime apsimesti, kad mes norime įterpti skaičių 8.
>> Taigi tik patogumo dėlei, aš ruošiuosi padaryti čia.
Tačiau nepamirškite, kad malloc galite įdėti ją labiausiai bet kur.
Bet Brėžinys dėlei, aš įdėti jį čia.
Taip apsimesti, aš ką tik skyrė skaičius 8 mazgas, tai pagal nutylėjimą yra NULL.
Tai, ką dabar turi įvykti? Pora dalykų.
Mes padarėme šią klaidą scenoje pirmadienį, kai mes atnaujinome žymiklį, kaip šis,
tada tai padarė, ir tada mes tvirtino mes našlaičiai visi kiti ant scenos.
, Nes jūs Negaliu - čia operacijų tvarka yra svarbi,
nes dabar mes praradome šį mazgas 9, kuris yra tiesiog tarsi plaukiojantieji erdvėje.
Taigi tai buvo ne teisingas požiūris pirmadienį.
Pirmiausiai mes turime daryti kažką kita.
Pasaulio valstybė atrodo taip. Iš pradžių, 8 buvo skirta.
Kokia turėtų būti geresnis būdas įterpti 8?
O ne atnaujinti šį žymeklį, tiesiog atnaujinti šį vieną čia vietoj.
Taigi, mums reikia kodo eilutę, kad ketinate išjungti šią NULL pobūdžio
į faktinė rodyklę, kad nukreipta mazgas 9,
ir tada mes galime saugiai pakeisti pirmiausia reikia priminti čia šis vaikinas.
Dabar mes turime sąrašą, susijęs su dviejų elementų sąrašą,.
O ką tai iš tikrųjų atrodo kaip čia?
Jei pažvelgsime į kodą, pastebėsite, kad aš padariau lygiai taip pat.
Jau sakiau, ir šioje istorijoje, newptr newptr buvo nukreipta ne šis vaikinas.
>> Taigi, leiskite man padaryti vieną dalyką, ir aš turėjo palikti šiek tiek daugiau erdvės.
Taigi atleisk Rasito piešinį.
Šis vaikinas yra vadinamas newptr.
Tai yra kintamasis, paskelbė keletą eilučių anksčiau, atsižvelgiant - šiek tiek virš 25.
Ir ji nukreipta į 8. Taigi, kai aš sakau, newptr-> Kitas, tai reiškia, kad eiti į struct
kad nurodė pagal newptr, todėl čia mes esame, ten eiti.
Tada rodyklė sako gauti kitą lauką, ir tada = sako įdėti, kas vertė?
Vertę, kuri buvo pirmą kartą, kas vertė buvo pirmas?
Pirmasis buvo nukreipta į šiame mazge, todėl tai reiškia, kad tai dabar turėtų atkreipti dėmesį šiame mazge.
Kitaip tariant, tai, kas atrodo, nors ir juokinga netvarka su mano ranka,
tai, kas paprasta idėja tiesiog perkelti šias rodykles aplink
tik su šiuo one liner kodas išsiverčia į.
Laikyti, kas yra pirmoji į kitą lauką ir tada atnaujinti, ką 1. iš tikrųjų yra.
Eikime į priekį ir pirmyn per kai tai,
ir tik šiuo uodegos įterpimą dabar.
Tarkime, aš gauti iki taško, kur aš suprato, kad kitas sritis kai mazgas yra NULL.
Ir į istoriją, išsamiai šiuo klausimu, kad aš įvardinant
yra tai, kad aš pristatė dar vieną žymiklį čia 142 eilutėje "pirmtakas rodykle.
Iš esmės, Šiuo istorija, kai sąrašas gauna ilgas,
I rūšies reikia eiti su dviem pirštais, nes jei aš einu per toli,
Prisimenu vieno ilgio sąrašą, jūs negalite eiti atgal.
Taigi šis predptr idėja yra mano kairėje pirštu, ir newptr - ne newptr.
Kitas rodyklė, kad čia yra mano pirštas, ir aš tiesiog malonu vaikščioti sąrašą.
Štai kodėl tai egzistuoja. Bet galime svarstyti tik vieną iš paprastesnių atvejų čia.
Jei tos POINTER Kitas laukas yra NULL, kas logiška potekstė?
Jei esate važiuojantiems šį sąrašą ir jūs nukentėjo NULL žymiklį?
Esate ne sąrašo pabaigoje, ir taip kodas pridėti šį vieną papildomą elementą
yra tarsi intuityvus imtis, kad mazgas, kurio žymeklis yra NULL,
todėl tai yra šiuo metu NULL, ir jį pakeisti, nors, naujas mazgas adresas.
Taigi mes tiesiog piešimo kodas rodyklę, kad mes rėmėsi kažkieno kairę ranką didinant etape.
>> Ir, kad aš pamojuoti savo rankas dabar,
tik todėl, kad aš manau, kad lengva pasiklysti, kai mes tai darome šioje aplinkoje rūšiuoti,
tikrinti įterpimą ne sąrašo viduryje.
Bet tiesiog intuityviai, kas turi atsitikti, jei norite išsiaiškinti,
kai kurie numeris priklauso viduryje yra jūs turite vaikščioti
su daugiau nei vienu pirštu daugiau nei vieną rodyklę,
išsiaiškinti, kur ji priklauso tikrinimo elementas <dabartinė
> Vienas, ir kai jums rasti tą vietą,
tada jūs turite tai padaryti, Shell žaidimas rūšiuoti, kur jums judėti patarimų apie labai atsargiai.
Ir kad atsakymas, jei norite prie priežasties, per šį savo namuose,
suvesta tik šių dviejų eilučių kodo, bet šių eilučių, kad yra super svarbu.
Nes jei jūs lašas kažkieno ranką ir kelti kažkieno neteisinga tvarka,
dar kartą, jums gali baigtis sąrašą orphaning.
Apibendrinti konceptualiai uodegos įterpimas yra gana paprasta.
Galvos įterpimas yra taip pat gana paprasta,
bet jums reikia atnaujinti papildomą POINTER šį kartą
išspausti į sąrašą 5,
ir tada viduryje įterpimo reikia dar daugiau pastangų,
labai atsargiai įkiškite į teisingą vietą, kurios numeris 20
kuris yra tarp 17 ir 22.
Taigi, ką jums reikia padaryti kažką panašaus į naują mazgas 20 punkte iki 22,
ir tada, Kuris mazgas rodyklė turi būti atnaujintas paskutinis?
Tai 17, faktiškai įdėkite jį.
Taigi dar kartą, aš atidėti faktinį tos konkrečios įgyvendinimo kodą.
>> Iš pirmo žvilgsnio, tai šiek tiek absoliuti, bet tai tikrai tik begalinis ciklas
ciklais, kilpų, kilpų, kilpų, ir trūkimo, kai tik paspausite NULL žymiklį,
, kuriame jūs galite padaryti, reikalingą įterpti.
Tai, tada, yra atstovas susijęs sąrašas įterpimo kodas.
Tai buvo natūra partijos, ir ji mano, kaip mes išspręsti vieną problemą,
bet mes įdiegėme visą kitą. Atvirai kalbant, mes praleido visą šį laiką
didelis O ir Ω ir važiavimo laiką, bando išspręsti problemas greičiau,
ir čia mes žengiame didelį žingsnį atgal, jis jaučiasi.
Ir dar, jei tikslas yra saugoti duomenis,
jis jaučiasi Šventojo Gralio, kaip sakėme, pirmadienį, būtų tikrai
laikyti dalykų iš karto.
>> Iš tikrųjų, tarkime, kad mes tai padarėme atidėti susietą sąrašą for a moment,
ir mes vietoj pristatė stalo sąvoką.
Ir tegul tiesiog manau, kad lentelės kaip masyvo metu.
Šis masyvas ir šiuo atveju čia yra apie 26 elementų, nuo 0 iki 25,
ir manyti, kad jums reikia šiek tiek saugojimo riekė pavadinimų:
Alisa ir Bobas ir Čarlis ir kaip.
Ir jums reikia tam tikrą duomenų struktūrą laikyti tuos pavadinimus.
Na, galite naudoti kažką panašaus į susietą sąrašą
ir tu gali vaikščioti sąrašą įdėti Alice prieš po Bob Bob ir Charlie ir kt.
Ir iš tiesų, jeigu norite pamatyti kodą, kaip kad panaikinti,
žinoti, kad list2.h, mes lygiai taip pat.
Mes negalime eiti per šio kodekso, bet tai yra ir pirmajame pavyzdyje variantas
kad pristato vieną kitą struct mes matėme prieš vadinamosios studentų,
ir kas tada ji iš tikrųjų saugo į susietą sąrašą, yra rodyklė į studentų struktūrą
o ne paprastas mažas sveikasis skaičius, n.
Taigi, suprantate, kodas, apima faktines eilutes,
bet jei po ranka tikslas tikrai dabar spręsti efektyvumo problema,
ar nebūtų malonu, jei mes suteikiama objektas, vadinamas Alisa,
mes norime įdėti ją į tinkamą vietą, duomenų struktūros,
jis jaučiasi, kad būčiau tikrai gražus, tiesiog įdėti Alice,
kurio pavadinimas prasideda pirmoje vietoje.
Ir Bobas, kurio vardas prasideda su B, antroje vietoje.
Masyvo, arba leisti pradėti skambinti lentelę, maišos lentelė tuo,
mes galime daryti būtent tai. Jei mes kaip Alisa pavadinimą,
kaip Alice eilutę, kur jūs įtraukėte A-L-i-c-e?
Mums reikia hueristic. Mes turime funkciją, šiek tiek kaip Alisa indėlį
ir grąžina atsakymą: "Kišk Alice šioje vietoje."
Ir ši funkcija, tai black box ", bus vadinamas maišos funkcija.
>> Maišos funkcija yra kažkas, kad mano indėlį, pavyzdžiui, "Alisa",
ir grįžta į jus, paprastai, skaitmeninis vieta kai duomenų struktūra, kurioje Alisa priklauso.
Šiuo atveju, mūsų maišos funkcija turėtų būti gana paprasta.
Mūsų maišos funkcija turėtų pasakyti, jei jums būtų suteikta "Alice", kuris personažas man rūpi?
Pirmasis. Taigi aš žiūriu [0], ir tada aš sakau jei [0] charakteris yra, grįžti skaičių 0.
Jei tai B grąžinti 1. Jei tai C, grįžkite 2, ir taip toliau.
Visi 0 indeksą, ir kad leistų man įterpti Alisa ir tada Bob ir tada Charlie ir tt
į šią duomenų struktūros. Bet yra problema.
Ką daryti, jei Anita vėl ateina kartu?
Kur mes įdėti Anita? Jos vardas irgi prasideda raide A,
ir jis jaučiasi, kaip mes padarėme dar didesnę netvarką šios problemos.
Dabar mes turime nedelsiant įterpimą, nuolatinio laiko, furnitūra, į duomenų struktūros
o ne blogiausiam atvejui, linijinė,
bet ką mes galime padaryti su Anita šiuo atveju?
Kokie yra du variantai, tikrai? Taip?
[Studentų atsakymas, nesuprantamas] Gerai, kad galėtume turėti dar vieną aspektą.
Tai gerai. Taigi, mes galime kurti daiktus iš 3D, kaip mes kalbėjome apie tai žodžiu pirmadienį.
Mes galime pridėti dar vieną prieigą, bet manyti, kad ne, aš bando išlaikyti tai paprasta.
Visa tikslas čia yra nedelsiant pastovaus laiko susipažinti,
kad pridedant per daug sud ÷ tingumą.
Kas yra ir kitų variantų, bandant įterpti Anita į šią duomenų struktūros? Taip?
[Studento atsakymas, nesuprantamas] Geras. Taigi, mes galime judėti žemyn, visi kiti
kaip Charlie nudges žemyn Bob ir Alisa, ir tada mes įdėti Anita, kur ji tikrai nori būti.
>> Žinoma, dabar, yra šalutinis poveikis.
Ši duomenų struktūra yra turbūt naudinga, ne todėl, kad norite įterpti žmonių kartą
bet todėl, kad mes norime patikrinti, jei jie ten vėliau
, jei norime atspausdinti visų pavadinimų duomenų struktūros.
Mes ketiname kažką daryti su šiais duomenimis galiausiai.
Taigi dabar mes rūšies prisukamas per Alice, kuris nebėra, kur ji turėtų būti.
Be to, Bobas, nei Čarlis.
Taigi, galbūt tai nėra tokia gera idėja.
Bet iš tikrųjų, tai yra viena iš galimybių. Mes galime pereiti visus žemyn,
ar gi Anita atėjo vėlai į žaidimą, kodėl ne mes tiesiog įdėti Anita
ne čia, ne čia, ne čia, tegul tiesiog įdėti ją šiek tiek mažesnis sąraše.
Bet tada ši problema vėl pradeda išsigimti.
Jums gali būti suteikta rasti Alice akimirksniu, remiantis savo vardą.
Ir Bob iš karto, ir Charlie. Bet tada jums atrodo Anita
ir pamatysite, hmm, Alice yra kelyje.
Na, leiskite man patikrinti žemiau Alisa. Bob nėra Anita.
Čarlis Anita. O, aš Anita.
Ir jei jūs ir toliau tos pačios logikos traukinys visą kelią,
kas blogiausio atvejo veikimo laikas surasti arba įdėti į šią naują duomenų struktūros Anita?
O (n), tiesa?
Nes blogiausiu atveju, yra Alice, Bob, Charlie. . .
paliko visą kelią žemyn kažkas pavadino "Y", todėl yra tik vienoje vietoje.
Laimei, mes turime niekas vadinamas "Z", todėl mes įdėti Anita pačioje apačioje.
>> Mes tikrai ne išspręsti šią problemą.
Taigi, gal mes reikia pristatyti šį trečiąjį aspektą.
Ir it turns out, jei mes pristatyti šį trečiąjį aspektą,
mes negalime padaryti, tai puikiai, bet šventasis Gralis bus gauti
pastovaus laiko įterpimas ir dinaminės intarpai, kad
mes neturime sunkiai kodas 26 dydžio masyvas.
Mes galime įterpti kaip daug pavadinimų, kaip mes norime, tačiau galime imtis mūsų 5-minučių pertrauką
ir tada padaryti, kad tinkamai.
Gerai. Aš nustačiau istorija gana dirbtinai ten
pasirenkant Alice ir Bob ir tada tada Charlie ir tada Anita,
kurio vardas buvo akivaizdžiai susiduria su Alice.
Bet klausimas, mes galų Pirmadienį tik kaip tikėtina, yra
, kad galėtumėte gauti šių rūšių susidūrimų? Kitaip tariant,
jei mes pradėsime naudoti šį lentelių struktūrą, kuri yra tikrai tik matrica,
šiuo atveju yra 26 vietų,
ką daryti, jei mūsų įėjimai, o ne tolygiai paskirstyta?
Tai ne dirbtinai Alisa ir Bobas ir Charlie ir Davidas ir tt pagal abėcėlę
jis tolygiai paskirstytą nuo A iki Z.
>> Gal mes tiesiog gauti pasisekė ir mes neketiname turėti du ar du b
su labai didele tikimybe, bet kaip kažkas atkreipė dėmesį,
jei mes apibendrintas tai problema, o ne 0-25
bet, tarkim, nuo 0 iki 364 arba 65, dažnai dienų skaičius tipiškas metais,
ir paprašė klausimą: "Kokia tikimybė, kad du iš mūsų šiame kambaryje turi tą patį gimtadienį?"
Kitaip tariant, kas yra tikimybė, kad du iš mūsų turi vardą, pradedant?
Klausimo rūšiuoti yra tas pats, tačiau šis adresas erdvė,
šią paiešką erdvė, yra didesnis gimtadienius atveju,
nes mes turime tiek daug daugiau dienų per metus, nei abėcėlės raidėmis.
Kas yra susidūrimo tikimybė?
Na, mes galime galvoti apie tai suprasti, matematikos priešinga kryptimi.
, Kas be susidūrimų tikimybė?
Na, tai sąvoka čia sako, kad tai, kas yra tikimybė,
jei yra tik vienas asmuo šiame kambaryje, kad jie turi unikalią gimtadienį?
Tai 100%. Nes jei yra tik vienas asmuo, į kambarį,
jo arba jos gimtadienis gali būti bet koks 365 dienų iš metų.
Taigi 365/365 variantų suteikia man vertę 1.
Taigi atitinkamas tikimybė šiuo metu yra tik 1.
Bet jei ten antras žmogus į kambarį,
kas yra tikimybė, kad jų gimtadienis yra kitoks?
Yra tik 364 galimi dienų, ignoruodama keliamaisiais metais,
jų gimimo nesikirstų su kitų asmenų.
Taigi 364/365. Jei trečiasis asmuo ateina, tai 363/365 ir kt.
Todėl mes nuolat dauginant šias frakcijas, kurios vis mažesni ir mažesni,
išsiaiškinti, kokia yra tikimybė, kad visi mes turime unikalius gimtadienius?
Bet tada mes galime, žinoma, tik šį atsakymą ir apversti jį aplink
ir padaryti 1 atėmus visus, išraiška, mes galų gale gauti
Jei prisimenate savo matematikos knygose atgal, atrodo, šiek tiek kažką panašaus į tai,
kuris yra daug lengviau interpretuojamos grafiškai.
Ir tai grafinis čia yra x ašyje gimimo dienų skaičių,
arba skaičius žmonių, kurių gimtadieniai, ir ant y ašies yra rungtynių tikimybė.
Ir ką tai sako, kad jei turite, tarkim, net,
galime pasirinkti kažką panašaus į 22, 23.
Jei yra 22 arba 23 žmonių kambaryje,
tikimybė, kad du iš tų nedaugelio žmonių ketinate turėti tą patį gimtadienį
iš tikrųjų yra super didelis, combinatorially.
50% tikimybė, kad vos 22 žmonių, seminaras, praktiškai klasei,
2 iš tų žmonių, kurie ketinate turėti tą patį gimtadienį.
, Nes ten yra tiek daug būdų, kuriais jūs galite turėti tą patį gimtadienį.
Dar blogiau, jei peržvelgsite dešinėje diagramos pusėje,
iki to laiko turite klasėje su 58 studentų,
iš 2 žmonių, turinčių gimtadienį tikimybė yra super, super didelė, beveik 100%.
Dabar, tai tarsi įdomus faktas apie realiame gyvenime.
>> Tačiau pasekmės, dabar duomenų struktūrų ir saugoti informaciją
reiškia, kad tik jei turite gražią, švarią, vienodą duomenų platinimą
ir jūs turite pakankamai didelė matrica, kad tilptų krūva dalykų
nereiškia, kad jūs ketinate gauti žmonių unikalių vietų.
Jūs ketinate turėti susidūrimų. Taigi šis maišos sąvoka, kaip ji vadinama,
atsižvelgiant, pavyzdžiui, "Alisa" indėlį ir masažuojant ją tam tikru būdu
ir tada gauti atsakymą kaip 0 arba 1 arba 2.
Kamuoja šio susidūrimo tikimybės gauti atgal kai išėjimo iš šios funkcijos.
Taigi, kaip mes galime tvarkyti šiuos susidūrimų?
Na, vienu atveju, mes galime imtis buvo pasiūlyta idėja, kad.
Mes galime tiesiog perkelti visus žemyn, arba gal, šiek tiek daugiau tiesiog,
, o visi kiti ne perkelti, tegul tiesiog perkelti Anita turima vietoje apačioje.
Taigi, jei Alice yra 0, Bobas yra 1, Charlie yra 2
mes tiesiog įdėti Anita buvimo vietos 3.
Ir tai yra technika vadinama linijinis zondavimo duomenų struktūrų.
Linijinis, nes jūs tiesiog vaikščioti šią eilutę, ir jūs tarsi zondavimo
įmanomų vietovių duomenų struktūros.
Žinoma, tai pereina į O (n).
Jei tikrai pilna duomenų struktūra, yra jau 25 žmonių,
ir tada Anita ateina kartu, ji galų gale, kas būtų vieta Z, ir to pakanka.
Ji vis dar tinka, ir mes galime rasti ją vėliau.
>> Bet tai buvo priešingai spartumo dalykų tikslo.
Taigi ką daryti, jei mes vietoj pristatė šią trečiąją dimensiją?
Šis metodas yra paprastai vadinamas atskiras Grupavimo, arba turintys grandines.
Ir kas maišos lentelė yra dabar, tai Tabular struktūra
jūsų stalo yra tiesiog patarimų masyvo.
Bet kokios rodykles rodo, kad yra atspėti, ką?
Susijęs sąrašas. Taigi ką daryti, jei mes priimame tiek iš šitų pasaulių geriausias?
Mes naudojame masyvų pradinių rodiklių
į duomenų struktūrą, todėl mes galime iš karto eiti į [0] [1] [30] arba taip toliau,
bet taip, kad mes turime tam tikrą lankstumą ir mes galime pritaikyti Anita ir Alice ir Adomas
ir bet kuris kitas vardas,
mes o ne tegul kitą ašį augti savavališkai.
Ir mes pagaliau, kaip nuo pirmadienio, kad išraiškingą galimybes su susietą sąrašą.
Duomenų struktūrą mes galime augti savavališkai.
Kita vertus, mes galime tiesiog padaryti didelį 2-dimensional array,
bet tai bus baisu situacija, jei vienas iš 2-dimensional array eilučių
nėra pakankamai didelis, už papildomą asmuo, kurio vardas atsitinka pradėti su A.
Neduok Dieve, mes turime perskirstyti tam tikrą didžiulį 2-dimensijų struktūrą
tik todėl, kad yra tiek daug žmonių, pavadintas,
ypač kai yra tiek mažai žmonių, pavadintas Z kažkas.
Tai tiesiog bus labai nedaug duomenų struktūra.
Taigi, tai nėra tobula, bet kokiomis priemonėmis, tačiau dabar mes bent jau turi galimybę
iš karto rasti, kur Alisa ar Anita priklauso,
bent jau kalbant apie vertikalią ašį,
ir tada mes tiesiog turite nuspręsti, kur įdėti Anita arba Alice šiame susietą sąrašą.
Jei mes neturime rūpintis apie rūšiavimas dalykų, kaip greitai mes galime įterpti Alice į kaip šis struktūrą?
Tai nuolatinio laiko. Mūsų rodyklę į [0], ir jei ten niekas,
Alisa eina šios susijusios sąrašo pradžioje.
Bet tai nėra didžiulis spręsti. Nes jei Anita tada ateina kartu
vėliau kai kurių žingsnių, kur Anita priklauso?
Na, [0]. OOP. Alice yra jau šios susijusios sąraše.
>> Bet jei mes nerūpi rūšiavimo šiuos pavadinimus,
mes galime tiesiog perkelti Alice daugiau, įterpti Anita, tačiau net ir tai yra pastovi laiko.
Net jei yra Ieva ir Adomas ir visi tie kiti pavadinimai,
tai nėra labai perkelia jas fiziškai. Kodėl?
Nes mes tiesiog padarė čia susijęs sąrašą, kuris žino, šie centrai yra bet kokiu atveju?
Viskas, ką jums reikia padaryti, tai perkelti duonos trupinius.
Perkelti rodykles aplink, jums nereikia fiziškai perkelti visus duomenis, aplink.
Taigi, mes galime įterpti Anita, tokiu atveju iš karto. Nuolatinio laiko.
Taigi, mes turime pastovios laiko paieškos, ir nuolatinis laiko kažkas panašaus Anita įterpimo.
Bet rūšies oversimplifying pasaulį.
Ką daryti, jei mes vėliau norite rasti Alice?
Kiek žingsnių yra tai, kad ketinate imtis?
[Studentų atsakymas, nesuprantamas]
Tiksliai. Žmonių skaičius prieš Alisa į susietą sąrašą.
Taigi tai ne visai tobulas, nes, vėlgi, yra mūsų duomenų struktūra Ši vertikali prieigos
ir tada ji turi šių susijusių sąrašus kabinti - iš tiesų, tegul ne atkreipti masyvo.
Ji šie susiję sąrašai kabo ne apie tai, kad atrodo šiek tiek kažką panašaus į tai.
Bet problema yra, jei Alisa ir Adomas ir visi tie kiti pavadinimai
galų gale, vis daugiau ir daugiau ten,
rasti kas nors galėtų galų gale imtis tam tikrų veiksmų krūva,
Bcause turite feed susietą sąrašą,
kuri yra tiesinė operacija.
Taigi tikrai, tada, įterpimo laikas galiausiai yra O (n), kur n yra sąrašo elementų skaičius.
Padalinta iš, galime savavališkai m, kur m yra sujungtų sąrašų skaičius
kad mes turime šios vertikalios ašies.
Kitaip tariant, jei mes iš tiesų prisiimti vienodą paskirstymo pavadinimų,
visiškai nerealu. Yra akivaizdžiai daugiau kai kurių raidžių, nei kiti.
>> Bet jei mes manome, šiuo metu vienodas platinimo,
ir mes n Iš viso žmonių, ir m Bendras tinklai
mums prieinama, tada kiekvieną iš šių tinklų ilgis
gana tiesiog bus iš viso, n padalintas iš grandinių.
Taigi n / m. Bet čia, kur mes galime būti visi matematiškai protingas.
m yra konstanta, nes ten yra nustatytas jų skaičius.
Jūs ketinate paskelbti savo komplekta pradžioje,
ir mes ne dydžio keitimas vertikalią ašį. , Pagal apibrėžimą, lieka nustatyta.
Tai tik horizontalioji ašis, taip sakant, kad keičiasi.
Techniškai, tai yra konstanta. Taigi dabar, įterpimo laikas
yra gana daug O (n).
Taip, kad visi, kad daug geriau nesijaučia.
Bet kas tiesa čia? Na, visą šį laiką, savaites,
mes buvo sakydamas O (n ²). O (n), 2 x n ² - n, padalintas iš 2. . . ech.
Tai tiesiog n ². Bet dabar, šį semestrą,
mes galime pradėti kalbėti apie realiame pasaulyje vėl.
Ir n / m yra neabejotinai greičiau nei tiesiog n vien.
Jei turite tūkstančių pavadinimų, o jūs pertrauka juos į kelis kibirus
, kad jūs turite tik dešimt kiekvieną iš šių tinklų pavadinimus,
visiškai ieško dešimt dalykų bus greičiau nei tūkstantis dalykų.
Ir taip vienas iš artėjančių problema rinkinių ketina iššūkis jums
galvoti apie tai tiksliai, kad net jei, taip,
asimptotiškai ir matematiškai, tai dar tik linijinis,
kuris sucks apskritai, kai bando rasti ką.
Iš tikrųjų, tai bus greičiau nei
nes daliklis.
Ir taip ten vėl bus šis kompromisas
ir tai tarp teorijos ir realybės konfliktas,
ir viena iš rankenėlių pradėti tekinimo šiuo metu į tą semestrą,
yra daugiau tikrovės, vienas, kaip mes tarsi pasirengti semster pabaigoje,
mes pristatome interneto programavimo pasaulį
kur tikrai, veiklos ketina skaičiuoti, nes jūsų naudotojai
pradeda pajusti ir įvertinti prastos dizaino sprendimus.
>> Taigi, kaip jums eiti apie įgyvendinimo susietą maišos lentelę su 31 elementų?
Ir ankstesniame pavyzdyje buvo savavališkai apie gimtadienius.
Jei kas nors turi sausio 1 ir vasario 1 gimtadienį, mes juos šiame kibirą.
Jei tai sausio 2 vasaris 2, kovo 2, mes juos šiame kibirą.
Štai kodėl ji buvo 31 metų. Kaip jūs deklaruojate maišos lentelę?
Tai gali būti gana paprasta, mazgas * Lentelėje yra mano savavališkai pavadinimas [31].
Tai suteikia man 31 patarimų mazgams,
ir kad leidžia man daryti 31 patarimų, kad, susijusius sąrašus
net jei tie tinklai yra iš pradžių NULL.
Ką aš noriu daryti, jei noriu laikyti "Alice", "Bobas", "Charlie"?
Na, mes turime tuos dalykus, į kuriuos vyniojami konstrukcija,
nes mes turime Alice Bob, kad rodytų į Charlie, ir kt.
Mes negalime tiesiog vien tik vardus, kad galėčiau sukurti naują struktūrą, pavadintą mazgas čia.
>> Kas yra tikrasis mazgas? Kas yra šioje naujoje susijęs sąrašo mazgas?
Pirmas dalykas, vadinamas žodis, yra asmens vardą.
ILGIS, matyt, susijęs su žmogaus vardą maksimalus ilgis,
kas tai bebūtų, 20, 30, 40 simbolių Crazy kampe atvejais,
+1 yra už ką? Tai tiesiog papildomai NULL personažas, \ 0.
Taigi šis mazgas vyniojimo viduje "kažkas" apie save,
tačiau ji taip pat pareiškia, žymeklį vadinamas Kitas
, kad mes galėtume grandinės Alice Bob su Charlie ir pan.
Gali būti lygus NULL, tačiau nebūtinai turi būti.
Kokių nors klausimų dėl šių maišos lenteles? Taip?
[Studentų klausia klausimą, neįskaitomai] masyvas - geras klausimas.
Kodėl tai char žodis masyvo, o ne tik char *?
Šioje šiek tiek savavališka Pavyzdžiui, aš nenoriu turėti imtis
malloc kiekvienam originalius vardus.
Aš norėjau paskelbti, kad maksimaliai atminties eilutę
, kad galėčiau nukopijuoti į struktūrą Alice \ 0, o ne kovoti su malloc ir laisvo ir panašios.
Bet aš galėtų padaryti, kad jei aš norėjau būti labiau suvokia erdv ÷ je naudoti. Geras klausimas.
Taigi, pabandykime apibendrinti atokiau nuo
ir sutelkti šiandien likusią duomenų struktūrų apskritai
ir kitas problemas, kad mes galime išspręsti naudojant tuos pačius pagrindus
nors duomenų struktūros gali skirtis patys savo duomenis.
>> Taigi paaiškėja, informatikos, medžių yra labai dažnas.
Ir jūs galite galvoti kaip šeimos medį, iš medžio rūšies
kur yra kai kurie šakniavaisiai, kai matriarch arba patriarchas,
močiutė ar senelis ar anksčiau atgal
žemiau kurios yra mama ir tėtis ar įvairios broliai ir seserys ar pan.
Taigi medžio struktūra mazgus ir ji turi vaikų,
paprastai 0 arba daugiau vaikų, kiekvieno mazgo.
Ir kai kurie iš žargono, kad jūs matote šioje nuotraukoje čia
yra mažų vaikų ar grandkids kraštų
kurie neturi rodykles, sklindančius iš jų,
tie vadinamieji lapai, ir visiems į vidų
yra vidinis mazgas, galite skambinti ji kažką išilgai šių linijų.
Tačiau ši struktūra yra gana dažnas. Tai vienas šiek tiek savavališkas.
Mes turime vieną vaiką, turime tris vaikus dešinėje, kairėje
liko du vaikai ant dugno.
Taigi, mes galime turėti skirtingo dydžio medžius, tačiau jei mes pradėsime ką standartizuoti,
ir jūs tikriausiai pamenate, kad tai iš Patriko vaizdo ankstesnis trumpas dvejetainis paieškos
internete, dvejetainis paieškos neturi būti įgyvendintos masyvo
ar popieriaus lapų ant lentos.
Tarkime, kad jūs norėjote saugoti savo numerius į tobulesnę duomenų struktūros.
Jūs galite sukurti tokį medį.
Jūs galite turėti mazgas deklaruotas C, ir kad mazgas gali turėti bent du elementus viduje ji.
Vienas yra skaičius, kurį norite išsaugoti, ir kita yra - gerai, mes turime dar vieną.
Kitas yra jo vaikai.
Taigi čia jau kita duomenų struktūra. Šį kartą mazgas yra apibrėžiamas kaip saugoti skaičių n
ir tada du patarimų, kairėje vaikų ir teisė vaikas.
Ir jie nėra savavališkas. Kas įdomu apie šio medžio?
>> Kas yra modelis, kaip mes nustatyti tai ar kaip Patrick paguldė jį iš savo vaizdo?
Tai tipo akivaizdu, kad kai rūšiavimas vyksta čia,
bet tai, kas paprasta taisyklė? Taip?
[Studentų atsakymas, nesuprantamas]
Tobula. Jei jums pažvelgti į tai, kaip matote kairėje nurodytas nedidelis skaičius,
didelis skaičius kairėje, bet tai tiesa kiekvieno mazgo.
Kiekvieno mazgo, jos kairysis vaikas mažiau nei jis, ir jo teisė vaikas didesnis, nei ji.
Ką tai reiškia dabar, jei noriu ieškote šio duomenų struktūrą, tarkim, numeris 44,
Turiu pradėti ne šaknis, nes, kaip su visais iš šių sudėtingų duomenų struktūrų,
turime tik rodyklę į vieną dalyką, pradžia.
Ir šiuo atveju, pradžia yra šaknis. Tai ne kairėje pusėje,
tai šios struktūros šaknis. Taigi, matau, čia yra 55, ir aš ieškau už 44.
Aš noriu, kuria kryptimi eiti?
Na, aš noriu eiti į kairę, nes akivaizdu, į dešinę bus per didelis.
Taigi pastebėsite čia, jūs tarsi konceptualiai kapojimo per pusę medis
nes jūs niekada į dešinėje pusėje.
Todėl dabar aš einu iš 55 į 33. Tai per mažas skaičius,.
Aš ieškau 44, bet dabar aš žinau, jei 44 yra šio medžio, žinoma, aš galiu eiti į dešinę.
Taigi dar kartą, aš per pusę genėjimo medžių.
Tai beveik identiškas konceptualiai į telefonų knygą.
Tai identiška tai, ką mes padarėme su lentos dokumentus,
bet tai vis sudėtingesnės struktūros, kuri leidžia mums iš tikrųjų
tai skaldyk ir valdyk dizaino algoritmo,
ir iš tiesų, važiuojantiems struktūrą panašaus į tai - šūksniais.
Važiuojantiems struktūra panašaus į tai, kur jis yra tik "eiti tokiu būdu, arba eiti, kad taip"
- visą tą kodą, kad sulenkta savo mintis ją įgyvendinant skyriuje
ar vaikščioti per ją namuose, dvejetainis paieškos, naudojant rekursija arba iteracija,
kaklo skausmas. Rasti vidurinį elementą, tada padaryti savo apvalinimas iki didesnio ar.
>> Yra grožio, nes dabar mes galime naudoti rekursija vėl,
bet daug daugiau švariai. Iš tiesų, jei jūs esate, kurios numeris 55, ir norite rasti 44,
jūs einate į kairę šiuo atveju, tada, ką jūs darote? Paleisti tą patį algoritmą.
Galite patikrinti mazgo vertę, tada pereikite į kairę arba į dešinę.
Tada galite patikrinti mazgo vertę, eikite į kairę arba į dešinę.
Tai puikiai tinka rekursijos.
Taigi, nors mes padarėme praeityje keletas gana savavališkai pavyzdžius, susijusius su rekursija
kad nereikėjo rekursinis su duomenų stuctures
ypač medžių, tai puikus taikant šią problemą idėja,
mažėja jį, o tada spręsti tos pačios rūšies, bet mažesnis, programą.
>> Taigi yra kita duomenų struktūra, kad mes galime pristatyti.
Tai vienas iš pirmo žvilgsnio atrodo paslaptingas, bet tai vienas nuostabus.
Taigi tai yra duomenų struktūra, vadinama trie, trie, kuris yra paveldėtas iš žodžio paieškos,
tariamos naujo pabandyti-VAL, bet tai, ką pasaulis vadina šie dalykai. Šalyse. T-r-i el.
Tai yra medis, struktūra, tam tikros rūšies, bet kiekvienas iš mazgų yra trie
atrodo, kad tai, ką? Ir tai yra šiek tiek klaidinantis, nes tai tipo sutrumpintų.
Bet atrodo, kad kiekvienas šiame trie mazgas yra masyvas.
Ir nors šioje diagramoje autorius neįrodė, tai,
Šiuo atveju, tai trie yra duomenų struktūra, kurių gyvenimo tikslas yra saugoti žodžius
kaip A-L-i-c-e arba B-o-B.
Ir tai, kaip šie duomenys parduotuvės Alice ir Bob ir Charlie ir Anita ir tt
jis naudoja masyvą, pagal kurią saugoti yra trie Alisa,
mes pradedame šakninis mazgas, kuris atrodo kaip masyvo,
ir tai buvo parašyta sutrumpinimą notacijos.
Autorius praleisti abcdefg nes nebuvo su tuo, kuris pavadinimai.
Jie tik parodė, M ir P ir T, tačiau šiuo atveju,
tegul tolti Alisa ir Bobas ir Charlie kai kurių pavadinimų, kad esate čia.
Maksvelo yra iš tikrųjų šioje diagramoje.
Taigi, kaip padarė autorius parduotuvė M--x-w-e-l-l?
Jis ar ji pradėjo šakninis mazgas ir nuėjo į [M], kad maždaug 13, 13 vieta masyve.
Iš ten, yra rodyklė.
Rodyklė į kitą masyvą.
Iš ten indeksuoti į tą masyvo A buvimo vietos, kaip parodyta viršutiniame kairiajame kampe,
ir tada jis ar ji po to, kad žymeklį į kitą masyvą,
ir nuėjo rodyklė vietą X
Tada kitą masyvo vietą W, E, L, L, ir taip toliau,
ir, pagaliau, galime iš tikrųjų bando įdėti paveikslėlį.
Ką mazgas atrodo kaip kodą?
Į trie mazgas yra masyvas rodykles į daugiau mazgų.
Tačiau taip pat turite būti kažkoks Būlio vertė, bent jau šį įgyvendinimą.
Aš atsitikti jį vadinti is_word. Kodėl?
Kadangi, kai jūs įterpiant Maxwell, jūs ne įterpiant
Niekada nieko neduokite į šią duomenų struktūros.
Jūs nesate raštu M. Jūs nesate raštu X
Darote po rodykles.
Rodyklę, kad atstovauja m, rodyklė, kuri atstovauja,
tada rodyklę, kad atstovauja X, tada W, E, L, L,
tačiau tai, ką jums reikia padaryti, pabaigoje yra tarsi eiti, patikrinti, aš pasiekė šią vietą.
Ten buvo žodis, kuris baigiasi čia, duomenų struktūros.
>> Taigi, kas trie tikrai alsuoja ir autorius pasirinko atstovauti
šių mažai trikampių terminuses.
Tai tiesiog reiškia, kad tai, šis trikampis yra čia, tai Būlio vertė tiesa
reiškia, kad, jei jūs einate atgal į medį,
tai reiškia, kad žodį "Maxwell yra.
Tačiau žodis rūšys, pavyzdžiui,
ne į medį, nes jei aš čia prasideda šakninis mazgas viršuje
Yra ne f rodyklė, ne o rodyklė, ne o rodyklė. Foo yra ne šiame žodyne vardas.
Tačiau priešingai, restruktūrizavimo, T-U-R-i-n g. Vėlgi, aš ne aukštesnėje t arba u arba R arba I arba N arba g.
Bet aš šio duomenų struktūros parduotuvę tikrąjį kelią žemyn čia, šiame mazge vertė - į medį
nustatant šį boolean vertę is_word tiesa.
Taigi trie yra šioje labai įdomus meta struktūros rūšies,
kur jūs tikrai ne saugoti patys žodžiai tokio žodyno.
Būti aiškus, jūs tiesiog saugoti "taip" arba "ne", yra žodis, kuris baigiasi čia.
>> Dabar, kas potekstė?
Jei turite 150.000 žodžių žodyne, kad jūs bandote laikyti atmintyje
naudojant kažką panašaus į susietą sąrašą,
jūs ketinate turėti 150.000 mazgų susieta "sąrašą.
Ir rasti vieną šių žodžių abėcėlės O (n) laiko.
Linijinis laikas. Bet čia tuo atveju, kai trie,
kas veikimo laikas rasti žodį?
Pasirodo grožį čia yra tai, kad net jei turite 149.999 žodžių žodyne jau šiame,
kaip įgyvendinamos šios duomenų struktūros,
kiek laiko reikia, kad rasti arba įterpti dar vieną asmenį, į, kad, kaip Alice, Alice?
Na, tai tik 5, gal 6 žingsniai užpakalinės pobūdžio.
Nes kitų pavadinimų struktūros presense
negauna įterpiant Alisa.
Be to, surandant Alice, kai yra 150.000 žodžių žodyno
negauna į savo kelią rasti Alice ne visi,
nes Alice yra. . . . . čia, nes aš rasiu vertė logiška.
Ir, jei yra ne boolean true, tada Alisa nėra šio duomenų struktūra, žodžiais.
Kitaip tariant, veikimo laikas rasti dalykų, ir įterpiant dalykų, į šią naują
duomenų struktūrą trie O - tai ne n.
Nes neturi apie Alice 150.000 žmonių presense, atrodo.
Todėl galime jį vadiname k, kur k yra Ilgiausias anglų kalbos žodis
kuris paprastai yra ne daugiau kaip 20-kažkas simbolių.
Taigi k konstanta. Taigi Šventasis Gralis, mes, atrodo, kad rado dabar
trie nuolat laiko įdėklais, paieška, norint ištrinti.
Kadangi dalykų jau struktūrą,
kurie nėra net fiziškai ten. Vėlgi, jie tiesiog tarsi tikrinama ne, "taip" arba "ne",
neturi įtakos būsimiems jos veikimo laiką.
>> Bet ten turi būti sugauti, nes kitaip mes būtume ne veltui tiek daug laiko
nuo visų šių kitų duomenų struktūrų tiesiog pagaliau gauti slaptą Tai nuostabu.
Taigi, kokia kaina mes mokame pasiekti šitą didybę? Erdvė.
Šis dalykas yra milžiniška. Ir todėl, kad autorius
nepateikė čia, pastebėsite, kad visų šių dalykų, kad atrodo kaip masyvai,
jis nepadarė pailsėti, medžio trie poilsio,
nes jie tiesiog nėra susiję su istorija.
Tačiau visų šių mazgų yra super platus, ir kiekvienas medžio mazgas užima
26 arba iš tikrųjų, gali būti 27 simboliai, nes šiuo atveju aš įskaitant vietos į kabutes
kad mes galėtume turėti apostrophized žodžius.
Šiuo atveju, tai yra dideli matricos. Taigi, net jei jie nėra picutured
tai užima didžiulės RAM.
Kuris gali būti gerai, especilly moderni įranga,
bet tai kompromisas. Mes gauname mažiau laiko praleisti daugiau vietos.
Taigi, kur visa tai vyksta?
Na, galime daryti - pažiūrėkime čia.
Darykime šuolis šis vaikinas.
>> Tikėkite arba ne, taip smagu, kaip C buvo tam tikrą laiką dabar,
mes pasiekti tašką semestrą, kai atėjo laikas pereiti į ką daugiau modernių.
Dalykų, dėl aukštesnio lygio. Ir nors per ateinančius porą savaičių
mes vis dar toliau pasineriame į nurodymus ir atminties valdymas pasaulyje
gauti, kad komfortą, su kuria mes galime remtis,
pabaigoje žaidimas galiausiai pristatyti, ironiškai, tai ne kalba.
Mes praleisti, pavyzdžiui, 10 minučių kalbėti apie HTML.
HTML yra žymėjimo kalba, ir kokia žymėjimo kalba
yra šių atvirų skliausteliuose ir uždarų skliausteliuose, kurie sako, kad "šis drąsus" serijos
"Šis kursyvu" Taip buvo ".
Tai dar ne viskas, kad intelektualiai įdomu, bet tai super naudingas.
Ir tai tikrai visur šių dienų.
Bet kas yra galingas apie HTML pasaulyje ir web programavimas apskritai,
kurti dinaminius dalykus, rašyti kodą kalbomis, pavyzdžiui, PHP ar Python arba Ruby ar Java ar C #.
Tikrai, kokia jūsų pasirinkta kalba, ir generuoti HTML dinamiškai.
Kurti kažką vadinama CSS dinamiškai.
Cascading Style Sheets, kuris taip pat apie estetika.
Ir todėl, nors šiandien, jei aš einu Some Like pažįstamas Google.com svetainėje,
ir aš einu, kūrėjas, vaizdas šaltinis, kuris gal padarei prieš, kad galėtumėte peržiūrėti
tačiau ketina peržiūrėti šaltinį, ši medžiaga tikriausiai atrodo gana paslaptingas.
Bet tai yra pagrindinis kodas, kuris įgyvendina Google.com.
Ant priekio. Ir iš tikrųjų visa tai yra purus estetika stuff.
Tai yra CSS čia. Jei aš judame žemyn, mes gauti šiek tiek spalvomis stuff.
Tai yra HTML. "Google" kodas atrodo netvarka, bet jei aš iš tikrųjų atverti kitą langą,
mes galime pamatyti šiek tiek struktūrą.
Jei aš atidarau tai padaryti, pastebėsite čia, tai šiek tiek lengviau skaityti.
Mes ketiname pamatyti iki kol šią žymę, [žodis] yra žymė,
HTML, galvos, kūno, div, scenarijus, teksto sritį, trukmę, orientuotą, div.
Ir tai taip pat rūšiuoti paslaptingas išvaizdos, iš pirmo žvilgsnio,
bet visa tai netvarka taip tam tikrus modelius, ir pakartoti modelius,
taip, kad, kai mes gauname pagrindai, galėsite rašyti kodą, kaip šis
ir tada manipuliuoti kaip dar vieną kalbą, vadinamą "JavaScript" kodą.
Ir JavaScript kalba, kuri veikia viduje naršyklėje
šiandien, kad mes naudojame Harvardo kursus, kursui prekybos priemonė, kuri "Google Maps" naudoja
suteiks jums visa krūva dinamikos, "Facebook" suteikia jums parodyti tiesioginius būsenos atnaujinimus,
"Twitter" naudoja jį parodyti jums tweets iš karto.
Visa tai mes pradėsime pasineriame.
Bet ten nuvykti, mes turime suprasti, truputį kažką apie interneto.
Šis klipas čia yra tik minučių trukmės, ir Tarkime, dabar tai yra, iš tikrųjų,
kaip internetas veikia kaip kibinimas už tai, kas apie ateiti. Aš tau "Warriors" Net ".
>> [♫ Lėtas choras muzika ♫]
[Vyras pasakotojas] Jis atėjo su pranešimu.
Visi jo paties protokolo.
[♫ greičiau elektroninės muzikos ♫]
Jis atėjo į cool ugniasienes pasaulyje, uncaring maršrutizatoriai,
pavojaus ir kur kas blogiau, nei mirties.
Jis greitai. Jis stiprus. Jis TCP / IP, ir jis gavo savo adresą.
Net kariai.
[Malan] Kitą savaitę, tada. Internetas. Web programavimas. Tai CS50.
[CS50.TV]