>> GARSIAKALBIS 1: Gerai, kad mes atgal.
Sveiki atvykę į CS50.
Tai savaitės septynių pabaiga.
Taigi priminti, kad paskutinį kartą, mes pradėjome žiūri truputį sudėtingesnės
duomenų struktūros.
Kadangi iki šiol, visi mes turėjome tikrai mūsų žinioje buvo tai, masyvo.
>> Bet kol mes išmeskite masyvo taip ne visi, kad įdomus, o iš tiesų
iš tikrųjų yra, kas yra kai kurių pliusai šį paprastą duomenų
struktūra iki šiol?
Kas tai gerai?
Tiek, kiek mes matėme?
Ką turite?
Nieko.
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Kas tai?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: fiksuotas dydis.
Gerai, tai kodėl yra fiksuoto dydžio gerai nors?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Gerai, kad tai efektyvus ta prasme, kad galite skirti
fiksuoto dydžio erdvę, kuri, tikiuosi, Būtent tiek, kiek
vietos, kiek norite.
Taigi, kad gali būti visiškai pliusas.
>> Kas yra kitas šalutinis masyvo?
Taip?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Visi - atsiprašau?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Visi atmintyje dėžės arba vienas šalia kito.
Ir tai naudinga - kodėl?
Tai visiškai teisinga.
Bet kaip mes galime pasinaudoti, kad tiesa?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Būtent, mes galime sekti kur viskas yra tik žinant
vienas adresas, ty adresas Pirmas baitas tos atminties riekė.
Arba eilutės atveju iš pirmųjų adresas
char tą eilutę.
Ir iš ten, mes galime rasti stringo pabaigos.
Mes galime rasti Antroji dalis, Trečiasis elementas, ir kt.
>> Ir taip išgalvotas būdas aprašyti, kad būdinga tai, kad matricos mums
laisvosios kreipties.
Tiesiog naudojant kvadratinės laikiklis notacijos ir skaičius, galite pereiti prie
specifinis elementas masyve nuolat laiko, didelis O
viena, taip sakant.
>> Bet ten buvo keletas praradimas.
Ką masyvas negali padaryti labai lengvai?
Kas tai nėra gerai?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Kas tai?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Išplečiamas dydžio.
Taigi iš masyvo praradimas yra tiksliai, kas priešinga
ilguoju yra.
Taigi vienas praradimas yra kad tai fiksuoto dydžio.
Taigi jūs tikrai negali augti.
Galite perskirstyti didesnį riekė atmintis, ir tada perkelti senus elementus
į naują masyvą.
Ir tada nemokamai senas masyvas, už Pavyzdžiui, naudojant malloc arba panašų
funkcija vadinama realloc, kuris perskirstys atmintį.
>> Realloc, kaip panaikinti, bando duoti jums atminties tai šalia masyvo
kad jūs jau turite.
Bet tai gali perkelti daiktus aplink apskritai.
Bet trumpai tariant, kad brangu, tiesa?
Nes jei jūs turite atminties riekė tai dydis, bet tikrai noriu,
tokio dydžio, ir jūs norite išsaugoti originalūs elementai, jūs turite
maždaug linijinis laikas kopijavimo procesas kad turi įvykti nuo
Esu masyvas naujas.
O realybė klausia veikti sistema vėl ir vėl ir
vėl didelių gabaliukus atmintis gali pradėti jums kainuoti šiek tiek laiko taip pat.
Taigi tai tiek palaiminimas ir prakeikimas į nuslėpti, kad šios matricos
yra fiksuoto dydžio.
Bet jei mes pristatome vietoj kažką kaip šis, kurį mes vadinami Tinkliniai
sąrašas, gausime keletą ilguoju ir keletas praradimas, čia taip pat.
>> Taigi susijęs sąrašas yra tiesiog duomenų struktūra sudaryta iš C structs šiame
atveju, jei konstrukto, priminti, yra tik vieną ar daugiau specifinių konteineris
tipų kintamųjų.
Šiuo atveju, ką duomenų tipai Atrodo, kad viduje struct kad
Paskutinį kartą mes vadinamas mazgą?
Kiekvienas iš šių stačiakampių yra mazgas.
Ir kiekvienas iš mažesnius stačiakampius viduje ji yra duomenų tipas.
Kokios gi mes pasakyti jie buvo pirmadienį?
Taip?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: kintama ir rodyklė, arba tiksliau, int n reikšmę,
ir apačioje rodyklę.
Tiek tų atsitikti, kad 32 bitai, bent jau patiko šį CS50 kompiuteryje
Prietaisą, ir todėl jie parengti vienodai dydžio.
>> Taigi, kas yra naudojant žymeklį nors ir atrodo?
Kodėl pridėti šį rodyklę dabar, kai matricos buvo toks gražus ir švarus ir paprastas?
Kas yra rodyklė darai mums kiekvienoje iš šių mazgų?
>> STUDENTŲ: [negirdimi].
>> GARSIAKALBIS 1: Būtent.
Tai sakau, jei Kitas vienas.
Taigi aš tarsi naudoti analogiją naudojant siūlai rūšiuoti
thread šiuos mazgus kartu.
Ir tai būtent tai, ką mes darome su patarimų, nes kiekvienas iš jų
gabaliukus atmintį gali arba negali būti greta, atgal atgal atgal
viduje RAM, nes kiekvieną kartą, kai skambinti malloc sako, duok man pakankamai
baitų naują mazgas, jis gali būti čia arba ji gali būti čia.
Tai gali būti čia.
Jūs tiesiog nežinau.
>> Tačiau naudojant rodykles į adresais tie mazgai, galite dygsnio juos
kartu taip, kad atrodo vizualiai panašus į sąrašą, net jei šie dalykai yra
visi išsikeroti visoje savo vieną ar savo du ar savo keturių gigabaitų RAM
viduje savo kompiuterį.
>> Taigi neigiama, tada, susijęs sąrašas yra kas?
Kas yra kaina, kurią mes esame matyt moka?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Daugiau vietos, tiesa?
Mes šiuo atveju dvigubai sumą vietos, nes mes jau dingo
nuo 32 bitų kiekvieno mazgo, kiekvienam int, todėl dabar 64 bitus, nes mes turime
išlaikyti aplink žymeklį, taip pat.
Jūs gaunate daugiau veiksmingumo, jei jūsų konstrukto yra didesnis nei šis paprastas dalykas.
Jei jūs iš tikrųjų turi studentą viduje kurių eilučių pora už
pavadinimas ir namo, gal ID numeris, gal kai kurie kiti laukai nedaugiau.
>> Taigi, jei turite pakankamai didelis struct, tada gal su rodykle kaina
nėra tokia baisi.
Tai kampinio atveju tiek tuo, kad mes saugojimo toks paprastas primityvus
viduje susijusį sąrašą.
Bet esmė yra ta pati.
Jūs tikrai išleidžia daugiau atminties, bet jūs gaunate
lankstumą.
Nes dabar jei noriu pridėti elementą prie šio sąrašo pradžioje
Turiu skirti naują mazgas.
Ir aš turiu tiesiog atnaujinti tuos rodyklės kažkaip tiesiog perkelti
keletas patarimų aplink.
>> Jei aš noriu įdėti kažką į viduryje sąraše, aš neturiu
stumti visus į šalį kaip tai darėme savaičių anksčiau su mūsų savanorių, kurie
atstovavo masyvą.
Galiu tik skirti naują mazgas ir tada tiesiog nukreipkite rodykles
įvairiomis kryptimis, nes ji neturi turi likti faktinis
atminties tiesa linija kaip aš sudarytas tai čia ekrane.
>> Ir tada galiausiai, jei norite įterpti kažkas ne iš sąrašo pabaigoje, tai
net lengviau.
Tai tarsi savavališkai žymėjimą, bet 34 yra rodyklė, spėti.
Kas yra jos žymeklis labiausiai vertė tikėtina, sudarytas tarsi metai
mokykla antena ten?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Tai tikriausiai null.
Ir iš tiesų tai yra vienas autoriaus atstovavimas null.
Ir tai niekinis, nes jūs visiškai reikia žinoti, kur iš Tinkliniai pabaiga
sąrašas, kitaip jūs nuolat taip ir taip ir šiuos rodykles
tam tikru šiukšlių vertę.
Taigi null reikš, kad nėra daugiau mazgų į skaičiaus 34 dešinėje
šiuo atveju.
>> Taigi, mes siūlome, kad galėtume įgyvendinti tai kodu mazgas.
Ir mes matėme šios rūšies sintaksė anksčiau.
Typedef tik apibrėžia naują tipą mus, suteikia mums sinonimas kaip
eilutė buvo skirta char *.
Tokiu atveju, jis ketina duoti mums Sutrumpintas žymėjimas, kad konstrukto mazgas
gali vietoj tiesiog būti parašyta, kaip mazgas, kuris yra daug švaresnis.
Tai daug mažiau išsami.
>> Viduje mazgas, matyt int vadinamas n, ir tada konstrukto mazgas *
o tai reiškia, ką mes norėjome rodyklės reiškia, žymeklį į kitą
mazgas patį duomenų tipą.
Ir aš siūlau, kad galėtume įgyvendinti paieškos funkcija, kaip šis, kuris tuo
Iš pirmo žvilgsnio gali atrodyti, šiek tiek sudėtinga.
Bet pažiūrėkime, tai kontekste.
>> Leiskite man pereiti prie prietaiso čia.
Leiskite man atverti failą pavadinimu sąrašas nulinis taškas val.
Ir tai yra tik apibrėžimo mes tik pamačiau prieš akimirką Dėl šios duomenų
tipas vadinamas mazgas.
Taigi, mes įdėti, kad į dot h failą.
>> Ir kaip žemę, nors tai programa, kad jūs apie pamatyti, yra
ne visi, kad sudėtinga, tai tikrai konvencija rašant programą
įdėti dalykų, pavyzdžiui, duomenų tipų, traukti konstantos kartais viduje jūsų
failo antraštės ir nebūtinai Jūsų failas C, žinoma, kai jūsų
programos gauti didesni ir didesni, todėl, kad jūs žinote, kur ieškoti tiek
dokumentus tam tikrais atvejais, arba už pagrindai, pavyzdžiui, tai, kad
apibrėžimas kai tipo.
>> Jei aš dabar atverti sąrašą nulio taškas c, pastebėti keletą dalykų.
Jis apima keletą antraščių failus, dauguma iš kurių mes matėme anksčiau.
Ji apima savo antraštės failą.
>> Ir kaip žemę, kodėl tai dvigubai citatos čia, o ne kampu
kronšteinai ant linijos, kad Aš pabrėžė ten?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Taip taip, tai vietos failas.
Taigi, jei tai vietos failą savo čia on line 15 Pavyzdžiui, jūs naudojate
į kabutes, o ne iš kampuotų skliaustuose.
>> Dabar tai yra rūšies įdomus.
Atkreipkite dėmesį, kad aš paskelbė pasaulio kintamasis šioje programoje eilutė 18
vadinama pirma, idėja, tai bus rodyklė į pirmąjį
mazgas mano susietą sąrašą, ir aš inicializuoti tai nulis, nes aš
neskiriami bet tikrasis mazgai tik dar.
>> Taigi tai reiškia, pavaizduotomis piktogramo, ką mes pamačiau momentas prieš pat paveikslėlyje kaip
kad toli rodyklė kairėje pusėje.
Taigi dabar, kad rodyklė neturi rodyklę.
Ji vietoj yra tik tuščias.
Bet tai reiškia, kas bus adresas pirmasis faktinis
mazgas šiame sąraše.
Taigi, aš įdiegėme yra pasaulinė nes, kaip pamatysite, visa tai
programa neveikia gyvenime yra įdiegti susijęs sąrašas už mane.
>> Dabar aš turiu keletą prototipų čia.
Aš nusprendė įgyvendinti funkcijas, pavyzdžiui, išbraukta, intarpas, ieškoti, ir
Sankryþos -
paskutinis tiesiog yra pėsčiomis visoje sąrašas, spausdinti jo elementus.
Ir dabar čia yra pagrindinis mano rutina.
Ir mes ne praleidžia per daug laiko tai, nes tai yra tarsi, tikiuosi
sena skrybėlę dabar.
>> Aš ruošiuosi padaryti taip, o vartotojo bendradarbiauja.
Taigi vienas, aš ruošiuosi spausdinti iš šio meniu.
Ir aš suformatuotas kaip švariai, kaip galėčiau.
Jei vartotojas įveda į vieną, tai reiškia, kad jie nori ištrinti kažką.
Jei vartotojas įveda į dvi dalis, tai reiškia, kad jie nori įterpti kažką.
Ir kt.
Aš ruošiuosi tada greitai tada komandą.
Ir tada aš ruošiuosi naudoti GetInt.
>> Taigi tai yra tikrai paprasta menuing sąsaja, kur jūs tiesiog įrašykite
numeris žemėlapių į vieną iš šių komandų.
Ir dabar turiu gražų švarų jungiklį pareiškimas, kad ketina įjungti
ką vartotojas turi įvesti in
Ir jei jie atspausdinti vieną, aš skambinti i ¹ trinti ir pertrauka.
Jei jie spausdinami du, aš skambinti įterpti ir lūžti.
>> Ir dabar pastebite, aš įdėti kiekvienas iš jų toje pačioje eilutėje.
Tai tik stilistinė sprendimas.
Paprastai mes matėme kažką kaip šis.
Bet aš tiesiog nusprendžiau, tiesą sakant, savo programą atrodė įskaitomas, nes
tai buvo tik keturias bylas tiesiog įtraukti ją, kaip šis.
Visiškai teisėtas naudojimas stiliaus.
Ir aš ruošiuosi tai padaryti tol, kol vartotojas dar įvedėte nulio, kurią aš
nusprendė reiškia jie nori mesti rūkyti.
>> Taigi dabar pastebėsite, ką aš ketina padaryti čia.
Aš ruošiuosi išlaisvinti sąrašą matyt.
Bet daugiau apie tai vos akimirką.
Tegul pirmasis paleisti šią programą.
Taigi leiskite man padaryti didesnį terminalą langas, taškas velniop sąrašas 0.
Aš ruošiuosi eiti į priekį ir įterpti pagal rašyti du, kaip 50 numeris, o dabar
pamatysite sąrašas dabar yra 50.
Ir mano tekstas tiesiog išeis šiek tiek.
Taigi dabar pastebėti sąraše yra skaičius 50.
>> Darykime kitą lapelį, atsižvelgiant du.
Leiskite įvesti į kaip vienas skaičius.
Sąrašas dabar yra viena, o po to 50.
Taigi tai yra tik teksto atstovavimas iš sąrašo.
Ir tegul įterpti dar vieną numerį, kaip skaičius 42, kuris, tikiuosi,
ketina baigti per vidurį, nes Tai visų pirma rūšių programos, kurią ji
elementus, kadangi jis įterpia juos.
Taigi, mes turime jį.
Super paprasta programa, kuri galėtų visiškai naudojo masyvą, bet aš
atsitiktų būti naudojant susietą sąrašą tik tiek galiu dinamiškai
plėstis ir trauktis jį.
>> Taigi, galime imtis paieškai atrodo, jei aš paleisti komandą tris, aš noriu ieškoti
už, tarkim, numeris 43.
Ir nieko matyt rasta, nes aš gavau atgal jokio atsakymo.
Taigi, galime tai padaryti ir vėl.
Paieška.
Leiskite paieška 50 arba, tiksliau ieškoti už 42, kuris yra gražus
mažai subtilus prasmę.
Ir radau gyvenimo prasmę ten.
Numeris 42, jei jūs nežinote, nuoroda tai Google.
Gerai.
Taigi, kas šią programą padaryti už mane?
Tai tiesiog leido man įterpti taip toli ir ieškoti elementų.
>> Leiskite pirmyn, tada į kad funkcija mes žvilgtelėjau
, pirmadienį, kaip erzina.
Taigi šią funkciją, galiu reikalauti, ieško sąraše elementas pirmiausia
vienas, paskatino vartotoją ir tada skambinti GetInt gauti realią int
kad jūs norite ieškoti.
>> Tada pastebėti tai.
Aš ruošiuosi sukurti laikiną kintamąjį atitinka 188 pavadino rodyklė -
PTR -
galėjo pavadino jį nieko.
Ir tai rodyklė mazgas nes sakiau mazgas * ten.
Ir aš Inicijuojama, kad ji būtų lygi pirmas, kad aš iš tikrųjų turiu
pirštas, taip sakant, ant labai pirmasis elementas iš sąrašo.
Taigi, jei mano dešinioji ranka čia yra PTR aš nukreipta į tą patį dalyką, kad pirmasis
yra nukreipta į.
>> Taigi dabar vėl kodą, kas bus toliau -
tai yra bendra paradigma, kai Iteracja daugiau panašaus struktūra
susijęs sąrašą.
Aš ruošiuosi padaryti taip, o rodyklė nėra lygus nulis Taigi, nors
mano pirštas nėra nukreipta tam tikru null vertė, jei rodyklė rodyklė n lygus n.
Mes pirmiausia pastebite, kad n yra kas vartotojas turi įvesti per GetInts skambinti čia.
>> Ir rodyklė rodyklė n reiškia ką?
Na, jei mes einame atgal į paveikslėlį čia jei turiu pirštu rodydamas į
kad pirmasis mazgas, kuriame devynių, kad rodyklė esmės reiškia eiti, kad
mazgas ir patraukti už vietos n vertę, šiuo atveju duomenų laukas vadinamas n.
>> Kaip žemę - ir pamatėme šį pora savaičių atgal, kai kažkas paklausė -
šį sintaksė yra nauja, bet jis nėra mums įgaliojimus, kad mes
dar nebuvo.
Kas buvo ši frazė atitinka naudojant taško žymėjimas ir žvaigždės pora
savaičių atgal, kai mes nulupus šis sluoksnis šiek tiek per anksti?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Būtent, tai buvo žvaigždė, ir tada ji buvo žvaigždė taškas n, su
skliaustai čia, kuri atrodo, atvirai, manau, kad daug
daugiau paslaptingas skaityti.
Bet žvaigždė žymeklis, kaip visada, reiškia eiti ten.
Ir kai jūs ten, kokie duomenys laukas jūs norite pasiekti?
Na jūs naudojate dot žymėjimą naudotis structs duomenų laukas, ir aš
konkrečiai norite n.
>> Atvirai kalbant, aš norėčiau ginčytis tai yra tik sunkiau skaityti.
Tai sunkiau prisiminti, kur Ar skliaustuose eiti,
žvaigždė ir visa tai.
Taigi pasaulis priėmė kai sintaksinė cukraus, taip sakant.
Tiesiog seksualus būdas pasakyti, tai atitinka ir
galbūt labiau intuityvus.
Jei rodyklė yra iš tikrųjų rodyklė, rodyklių notacijos reiškia eiti ten ir rasite
šiuo atveju laukas vadinamas n.
>> Taigi, jei aš galėčiau jį rasti, pastebėti, ką darau.
Aš tiesiog atsispausdinti, radau proc I prijungti į tos int vertę.
Aš vadinu miegoti vieną sekundę tiesiog natūra iš pristabdyti dalykų ekrane
suteikti vartotojui antra sugerti kas atsitiko.
Ir tada aš pertraukos.
Priešingu atveju, ką man daryti?
Aš atnaujinti žymiklį lygūs rodyklė rodyklė kitą.
>> Taigi, tiesiog, kad būtų aišku, tai reiškia eiti ten, naudodami savo senosios mokyklos žymėjimą.
Taigi tai tiesiog reiškia eiti į whatever jūs nukreipta į, kuris labai
Pirmasis atvejis aš nukreipta į su devynių jame struct.
Taigi, aš nuėjo ten.
Ir tada taškas žymėjimas reiškia, gauti vertę kitą.
>> Bet vertė, nors jis sudarytas kaip siauras, tik skaičius.
Tai skaitmeninis adresą.
Taigi tai viena eilutė kodo, ar parašyta, kaip šis, daugiau paslaptingas
būdu, arba, kaip šis, šiek tiek daugiau intuityvus būdas, tiesiog reiškia, perkelti savo ranką
nuo pirmojo mazgo į kitą, ir tada kitą, ir tada
kitą, ir taip toliau.
>> Taigi mes ne gyventi dėl kitų realizacijos įterpti ir ištrinti
ir Sankryþos, pirmieji du kuris yra gana dalyvauja.
Ir manau, kad tai gana lengva gauti prarastomis tada, kai tai daryti žodžiu.
Bet ką mes galime padaryti čia pabandyti nustatyti, kaip
geriausia tai padaryti vizualiai.
Nes aš norėčiau pasiūlyti, kad, jei mes norite įterpti elementus į tai
esamą sąrašą, kuris turi penkis elementus -
9, 17, 22, 26 ir 33 -
jei aš buvo ketiname įgyvendinti tai kodas, man reikia apsvarstyti, kaip eiti
apie tai daryti.
>> Ir aš norėčiau pasiūlyti, atsižvelgiant kūdikio žingsnius pagal kurią, šiuo atveju aš turiu galvoje, kas yra
galimi scenarijai, kad mes gali susidurti apskritai?
Įgyvendinant įdėklas Tinkliniai sąrašas, tai tiesiog atsitinka būti
Konkretus pavyzdys dydžio penki.
Na, jei norite įterpti numerį, norėčiau pasakyti, kad numeris vienas, ir
išlaikyti surūšiuoti užsakymą, kur akivaizdžiai nėra numeris vienas turi
eiti šiuo konkrečiu pavyzdžiu?
Kaip pradžioje.
>> Bet įdomiausia yra tai, kad jei norite įterpti vieną į šią
sąrašas, kokių specialiųjų rodyklė turi būti atnaujintas matyt?
Pirmas.
Taigi aš norėčiau ginčytis, tai yra pirmas atvejis kad mes galbūt norėsite apsvarstyti,
scenarijų įtraukiant įstatykite sąrašo pradžioje.
>> Leiskite roviau gal taip paprasta, ar net lengviau atveju, santykinai kalbant.
Tarkime, aš noriu įterpti į rūšiuotų kad 35 skaičius.
Tai akivaizdžiai priklauso ten.
Taigi, kas rodyklė akivaizdžiai ketina turi būti atnaujinami tokiu atveju?
34 s žymeklis tampa NOT NULL bet iš struct adresas
, kuriame yra skaičius 35.
Štai atveju du.
Taigi jau, aš tarsi Kvantas kiek darbo turiu padaryti čia.
>> Ir, pagaliau, akivaizdu, vidutinio atvejis Iš tiesų, per vidurį, jei noriu
įterpti kažką panašaus pasakyti 23, kuris eina tarp 23 ir 26, bet
dabar ko gauti šiek tiek daugiau naudojami, nes tai, ką
rodykles reikia keisti?
Taigi 22 akivaizdžiai turi būti pakeista nes jis negali nurodyti 26 nebėra.
Jam reikia, kad rodytų į naujas mazgas, kad Aš turiu skirti telefonu
malloc arba kitu lygiaverčiu.
>> Bet tada aš taip pat reikia, kad naujas mazgas, 23 šiuo atveju, turi turėti savo rodyklę
nukreipta į ką?
26.
Ir ten bus Užsakyti operacijų čia.
Nes jei aš tai kvailai, ir aš pavyzdžiui, pradėkite nuo pradžios
sąrašas, o mano tikslas yra įdėti 23.
Ir aš patikrinti, ar ji priklauso Čia, netoli devynių?
Ne.
Ar tai priklauso čia, šalia 17?
Ne.
Ar tai priklauso čia šalia 22?
Taip.
>> Dabar, jei aš kvailas čia, o ne galvoju, kad šis pro galėčiau
skirti savo naują mazgą 23.
Galiu atnaujinti žymiklį nuo mazgas vadinamas 22, rodydamas
tai ne naujas mazgas.
Ir tada, ką aš turiu atnaujinti naujos mazgo rodyklė būti?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Būtent.
Nukreipta į 26.
Bet velniai, jei aš ne jau atnaujinti 22 'žymeklis atkreipti į šį vaikiną, ir
dabar turiu našlaičius, poilsio sąrašo, taip sakant.
Taigi, kad veiklos čia bus svarbus.
>> Norėdami tai padaryti, galėčiau pavogti, tarkim, šešių savanorių.
Ir tegul pamatyti, jei mes negalime padaryti vizualiai vietoj kodo išmintingas.
Ir mes turime keletą gražių stresą rutuliai jums šiandien.
Gerai, kaip apie vieną, du, į atgal - nuo pabaigos.
trijų, keturių, jums abiems vaikinai pabaigos.
Ir penkių, šešių.
Tikrai.
Penkių ir šešių.
Visos teisės ir mes ateiti Jums, vaikinai kitą kartą.
Viskas gerai, ateiti iki.
>> Viskas gerai, nes esate čia pirma, norėtumėte būti vienas nerangiai
"Google" Stiklo čia?
Gerai, taip, gerai, Stiklas, filmuoti.
Gerai, jūs gerai eiti.
>> Visos teisės, todėl, jei jus vaikinai gali ateiti per čia aš iš anksto paruošti
kai kurie numeriai.
Gerai, eikš čia.
Ir kodėl gi ne jums eiti šiek tiek toliau, kad taip.
Pažiūrėkime, kas yra jūsų vardas, su "Google" stiklo?
>> STUDENTŲ: Ben.
>> GARSIAKALBIS 1: Benas?
Gerai, Benas, jums bus pirmasis, tiesiogine prasme.
Taigi, mes ketiname atsiųsti iki etapo pabaigos.
Visos teisės ir tavo vardas?
>> STUDENTŲ: Jason.
>> GARSIAKALBIS 1: Jasonas Gerai jums būti numeris devyni.
Taigi, jei norite sekti Ben kad taip.
>> STUDENTŲ: Jill.
>> GARSIAKALBIS 1: Jill, jūs ketinate būti 17, kuri, jei aš padariau tai daugiau
protingai, aš norėčiau turėti pradėjo kitame gale.
Jūs eikite, kad taip.
22.
Ir jūs esate?
>> STUDENTŲ: Marija.
>> GARSIAKALBIS 1: Marija, jums bus 22.
Ir jūsų vardas?
>> STUDENTŲ: Chris.
>> GARSIAKALBIS 1: Chris, jums bus 26.
Ir tada galiausiai.
>> STUDENTŲ Diana.
>> GARSIAKALBIS 1 Diana, jums bus 34.
Taigi, jūs ateiti čia.
>> Visos teisės, todėl puikiai surūšiuoti užsisakyti jau.
Ir eikime į priekį ir tai padaryti kad mes galime tikrai -
Ben jūs tik rūšies ieškote išeiti į niekur ten.
Gerai, kad galime eiti į priekį ir vaizduoti tai naudojant rankas, panašiai kaip aš, būtent,
kas vyksta.
Taigi, eikite į priekį ir suteikti sau pėdų arba du tarp savęs.
Ir eiti į priekį ir taškas viena ranka jei kas jums turėtų būti nukreipta į
remiantis tai.
Ir jei jūs null tiesiog atkreipti tiesiai žemyn prie grindų.
Gerai, kad gerai.
>> Taigi dabar mes turime susietą sąrašą, ir leiskite man pasiūlyti, kad aš žaisti vaidmenį
PTR, todėl aš ne nerimauti atliekant šį kartą aplink.
Ir tada - kažkas kvailas konvencija - galite skambinti šiuo ką tik norite -
pirmtakas rodyklė, pred rodyklė -
tai tik slapyvardis mes pasidavė mūsų mėginio kodą į savo kairę ranką.
Kita vertus, kad bus išlaikyti sekti, kas yra kas
po scenarijus.
>> Taigi manau, kad, pirma, noriu roviau kad pirmasis pavyzdys įterpiant, tarkim
20, į sąrašą.
Taigi, aš ruošiuosi reikia ką nors įkūnija numeris 20 mums.
Taigi man reikia malloc nors iš auditorijos.
Ateik iki.
Koks tavo vardas?
>> STUDENTŲ Brian.
>> GARSIAKALBIS 1: Brian, viskas gerai, todėl jūs turi būti mazgo, kurių sudėtyje yra 20.
Gerai, eikš čia.
Ir akivaizdu, kur nėra Brian priklauso?
Taigi, į vidurį - iš tikrųjų, palauk.
Mes darome tai iš eilės.
Mes darome tai dalis sunkiau nei ji turi būti pirmas.
Gerai, mes ketiname nemokamai Brian ir realloc Brian kaip penkių.
>> Gerai, kad dabar mes norime įterpti Brian kaip penkių.
Taigi eikš čia šalia Benas tik akimirką.
Ir jūs galite tikriausiai pasakys kur ši istorija vyksta.
Bet tegul kruopščiai galvoti apie iš operacijų eiliškumas.
Ir tai būtent ši vaizdo kad ketina išsirikiuoti
su tuo mėginio kodą.
Taigi čia aš PTR nukreipta pradžių ne Ben, per se, bet kokia
Vertiname jis yra, kuris šiuo atveju yra - kas tavo vardas?
>> STUDENTŲ: Jason.
>> GARSIAKALBIS 1: Jason, todėl tiek Benas ir aš nukreipta į Jason šiuo metu.
Taigi dabar turiu nustatyti, kur veikia Brian priklauso?
Taigi vienintelis dalykas, aš turėti prieigą prie dabar yra jo n duomenų elementas.
Taigi, aš ruošiuosi patikrinti, yra Brian mažiau nei Jason?
Atsakymas yra tiesa.
>> Taigi, ką dabar turi įvykti, teisinga tvarka?
Man reikia atnaujinti, kiek patarimų iš viso šioje istorijoje?
Kur mano ranka vis dar nukreipta į Jason, o jūsų ranka - jei norite
įdėti savo ranką, kaip, tarsi aš Nežinau, klaustuką.
Gerai, gerai.
>> Gerai, taigi jūs neturite keli kandidatai.
Bet Benas arba I ar Brian ar Jason ar visi kiti, kurie
rodykles reikia pakeisti?
Kiek iš viso?
>> Gerai, kad du.
Mano rodyklė tikrai ne klausimas nebėra nes aš tik laikinas.
Todėl šie du vaikinai, matyt, tiek Benas ir Brian.
Taigi leiskite man pasiūlyti, kad mes atnaujinti Benas, nes jis pirmas.
Pirmasis elementas iš šio sąrašo dabar bus Brian.
Taigi Benas taškas Brian.
Gerai, dabar ką?
>> Kas gauna nurodė kam?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Gerai, kad Brian , pabrėžiama, Jason.
Bet aš prarado stebėti, kad žymeklis?
Ar aš žinau, kur Jasonas yra?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: aš, nes aš laikinas žymeklis.
Ir matyt, aš nepasikeitė atkreipti į naujas mazgas.
Taigi, mes galime tiesiog Brian tašką ne tas, kas aš nukreipta į.
Ir mes padaryti.
Taigi, jei vienas, įterpimas į pradžioje sąrašo.
Yra du pagrindiniai žingsniai.
Vienas iš jų, mes turime atnaujinti Ben, tada mes taip pat turime atnaujinti Brian.
Ir tada aš neturiu nerimauti traipsing per likusį
sąrašas, nes mes jau rado savo vieta, nes jis priklausė
paliko pirmojo elemento.
>> Gerai, kad gana paprasta.
Tiesą sakant, jaučiasi mes beveik todėl tai pernelyg sudėtinga.
Taigi tegul dabar roviau pabaigos sąrašo, ir pamatyti, kur
sudėtingumas prasideda.
Taigi, jei dabar, aš alloy iš auditorijos.
Kiekvienas nori žaisti 55?
Gerai, aš pamačiau savo ranką pirmas.
Ateik iki.
Taip.
Koks tavo vardas?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Habata.
Gerai, ateik iki.
Būsite skaičius 55.
Taigi, jūs, žinoma, priklauso prie sąrašo pabaigoje.
Taigi leiskite pakartoti modeliavimą su manimi yra PTR tik akimirką.
Taigi, aš pirmą kartą ketina atkreipti į kokia BEN'S nukreipta į.
Mes abu nukreipta dabar Brian.
Taigi 55 yra ne mažesnis nei penki.
Taigi, aš ruošiuosi atnaujinti save pagal nukreipta į Briano kitą žymeklis, kuris
Dabar, žinoma, Jason.
55 yra ne mažiau kaip devynių, todėl Aš ruošiuosi atnaujinti ptr.
Aš ruošiuosi atnaujinti PTR Aš ketina atnaujinti ptr.
Ir aš ruošiuosi - Hmm, kas tavo vardas?
>> STUDENTŲ Diana.
>> GARSIAKALBIS 1: Diana nukreipta, žinoma, ne niekiniu su savo kaire ranka.
Taigi, kur veikia Habata tikrųjų priklauso aiškiai?
Į kairę, čia.
Taigi, kaip man žinoti, kad įdėti ją čia Manau, kad aš įsukus.
Nes tai, kas yra PTR menas tai laiko momentas?
Null.
Taigi, nors vizualiai galime akivaizdžiai matyti visi jie
vaikinai čia ant scenos.
Aš ne nuolat stebėti iš ankstesnių asmuo sąraše.
Aš neturiu pirštą nurodydamas, kad šiuo atveju mazgas numeris 34.
>> Taigi, galime iš tikrųjų pradėti tai per.
Taigi, dabar aš iš tikrųjų reikia Antrasis vietos kintamąjį.
Ir tai, ką jūs matote Tikrasis bandinys C kodas, kur, kaip aš einu,
kai aš atnaujinti savo dešinę ranką į tašką Jasonas paliekant Brian atsilieka, aš
geriau pradėti naudoti savo kairę ranką į atnaujinti kur aš buvau, kad, kaip aš einu
per šį sąrašą -
daugiau nerangiai nei aš skirtas dabar čia vizualiai -
Aš ruošiuosi gauti pabaigoje sąrašo.
>> Ši ranka vis dar null, kuri yra gana nenaudingas, išskyrus tai, kad nurodyti
Aš aiškiai sąrašo pabaigoje, bet dabar bent turiu tai
pirmtakas rodyklė nukreipta čia, todėl kas dabar rankas ir kas patarimų turi
būti atnaujintas?
Kieno ranka tu nori pertvarkyti pirmąjį?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Gerai, kad Dianos.
Jeigu jūs norite nurodyti Dianos kairę rodyklė ne?
Ne 55, matyt, todėl, kad mes įterpiami ten.
Ir kur turėtų 55 rodyklė eiti?
Žemyn, ty null.
Ir mano rankos, šiuo metu, ar ne klausimas, nes jie buvo tik
laikini kintamieji.
Taigi dabar mes padaryti.
>> Taigi papildomas sudėtingumas ten - ir tai nereiškia, kad sunku įgyvendinti,
bet mums reikia vidurinį kintamąjį pateikti įsitikinkite, kad prieš man perkelti savo teisę
Kita vertus, aš atnaujinti mano kairę vertę Kita vertus, pred žymeklis šiuo atveju, todėl
kad turiu gale žymeklį sekti kur buvau.
Dabar, kaip panaikinti, jei jūs galvojate tai per, tai jaučiasi, kad tai
šiek tiek erzina, kad nuolat sekti šios kaire ranka.
>> Kas būtų kitas sprendimas Šios problemos buvo?
Jei turite pertvarkyti duomenis struktūra mes kalbame
per dabar?
Jeigu tai tik rūšies jaučiasi tiek erzina, kad, pavyzdžiui, dvi rodykles
išgyvena sąrašo, kuris dar gali buvo, idealiame pasaulyje, prižiūrima
informacija, kad mums reikia?
Taip?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Būtent.
Teisę taip, ten tikrai įdomu gemalai idėja.
Ir tai praėjusiais rodyklė idėja, nukreipta į ankstesnį elementą.
Ką daryti, jei aš tiesiog įkūnijo kad viduje paties sąrašo?
Ir tai bus sunku įsivaizduoti tai be visų popieriaus
sumažės iki grindų.
Bet tarkime, kad šie vaikinai naudojami tiek iš jų rankų, kad ankstesnė
rodyklė, ir kitą rodyklė, taip įgyvendinti tai, ką mes vadiname dvigubai
susijęs sąrašą.
Tai leistų man rūšiuoti atgal, daug lengviau be manęs,
programuotojas, turintis išlaikyti sekti rankiniu būdu -
tikrai rankiniu būdu -
, kur buvau anksčiau sąraše.
Taigi mes negalime padaryti.
Mes keep it simple, nes tai vyksta jį ateiti kainą, du kartus
daug erdvės, rodyklės, jei norite antrasis.
Bet tai iš tikrųjų yra bendroji duomenų struktūra vadinama
dvigubai susijęs sąrašas.
>> Padarykim galutinį pavyzdį čia ir įdėti šie iš savo kančių vaikinai.
Taigi malloc 20.
Nagi iki nuo altoriaus ten.
Gerai, kas yra jūsų vardas?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Atsiprašome?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Demeron?
Gerai ateiti iki.
Jūs turi būti 20.
Jūs akivaizdžiai ketina priklausyti nuo 17 iki 22.
Taigi leiskite man sužinoti savo pamoką.
Aš ruošiuosi pradėti rodyklę nukreipta į Brian.
Ir aš ruošiuosi mano kairę ranką tik atnaujinti Brian kaip aš pereiti prie
Jasonas patikrinimo metu 20 mažiau nei devynių?
Ne.
Yra 20 mažiau nei 17?
Ne.
Yra 20 mažiau kaip 22?
Taip.
Taigi, kas patarimų ar rankas reikia pakeisti kur jie nukreipta dabar?
>> Taigi, mes galime padaryti, 17 nukreipta į 20.
Taigi, kad viskas gerai.
Kur norime atkreipti Jūsų rodyklė dabar?
Už 22.
Ir mes žinome, kur 22, vėlgi dėka mano laikinas žymeklis.
Taigi mes Gerai ten.
Taigi dėl šio laikino saugojimo Aš nuolat stebėti, kur visi yra.
Ir dabar jūs galite vizualiai eiti į kur jūs priklausote, ir dabar mes turime 1, 2, 3,
4, 5, 6, 7, 8, 9 streso rutuliai, ir ar plojimų už
šie vaikinai, jei galėtume.
Gražiai padaryta.
>> [Plojimai]
>> GARSIAKALBIS 1: Gerai.
Ir tu gali laikyti gabalus Popieriaus kaip suvenyrai.
>> Gerai, taip, pasitikėk manimi, tai daug lengviau eiti per, kad su
žmonės, nei ji yra su realiais kodą.
Bet kas jums rasti tik akimirką dabar yra tas pats - oi, ačiū.
Ačiū -
yra tai, kad jūs pamatysite, kad tuos pačius duomenis struktūra, susijusi sąrašas, iš tikrųjų gali
būti naudojama kaip statybinis blokas su dar Sudėtingesnės duomenų struktūros.
>> Ir suvokti pernelyg tema čia yra, kad mes visiškai pristatė daugiau
sudėtingumo į įgyvendinimo Šio algoritmo.
Intarpas, ir jei mes nuėjome per ją, išbraukta ir paieška, yra šiek tiek
sudėtingesnis nei buvo su masyvo.
Bet mes gauti šiek tiek dinamiškumo.
Mes gauname prisitaikanti duomenų struktūrą.
>> Bet vėl, mes mokėti tam tikra kaina papildomas sudėtingumas, tiek
jį įgyvendinant.
Ir mes atsisakė laisvą prieigą.
Ir tiesą sakant, ten nėra kažkoks gražus valyti skaidrę aš galiu duoti jums, kad
sako čia yra, kodėl susijęs sąrašas yra geriau nei masyvo.
Ir palikti jį tuo.
Kadangi tema pasikartoja dabar net labiau, kad per ateinančias savaites, yra
kad nebūtinai Teisingas atsakymas.
>> Tai kodėl mes turime atskirą ašį iš dizaino problema rinkinių.
Tai bus labai konteksto ar norite naudoti šiuos duomenis
struktūra arba kad vienas, ir tai bus priklauso nuo to, ką jums rūpi požiūriu
išteklių ir sudėtingumo.
>> Bet leiskite man pasiūlyti, kad idealus duomenys struktūra, Gralis, būtų
kažkas, kad pastovus laikas, nepriklausomai nuo to, kiek medžiaga yra
viduje, ar nebūtų nuostabu, jei duomenų struktūra grįžo atsakymus
pastovus laikas.
Taip.
Šis žodis yra jūsų didžiulis žodyną.
Ar ne, šis žodis nėra.
Arba bet tokia problema egzistuoja.
Na pažiūrėkime, jei mes negalime bent imtis siekiant šio žingsnio.
>> Leiskite man pasiūlyti naują duomenų struktūrą, kuri gali būti naudojami įvairių dalykų,
šiuo atveju vadinamas maišos lentelė.
Ir taip mes iš tikrųjų grįžti į skaitydamas ne masyvo, šiuo atveju, ir
šiek tiek savavališkai, aš sudarytas šis maišos lentelė kaip su rūšies masyvo
dvimatis masyvas -
ar veikiau jis vaizduojamas čia kaip du masyvas - bet tai tik
dydžio 26 masyvas, pavyzdžiui, kad jei mes skambinti masyvo staliukas, stalas laikiklis
nulis viršuje stačiakampis.
Stalo laikiklis 25 yra stačiakampis apačioje.
Ir tai, kaip aš galėtų vilkti duomenis struktūrą, kurioje aš noriu laikyti
žmonių vardus.
>> Taigi, pavyzdžiui, ir aš ne atkreipti Visa tai čia Viršuje, jei aš
turėjo tai, masyvas, kurį aš dabar ketina skambinti maišos lentelę, ir tai dar kartą
vieta nuliui.
Tai čia vieta vienas, ir kt.
Galiu reikalauti, kad aš noriu naudoti šiuos duomenis struktūra, siekiant aptarti labui,
saugoti žmonių vardus, Alisa ir Bobas ir Čarlis ir kiti tokie pavadinimai.
Taigi manau, tai dabar kaip pradžia , tarkim, į žodyną
su daug žodžių.
Jie atsitiktų būti pavadinimai Mūsų pavyzdyje čia.
Ir visa tai per Germane, ko gero, įgyvendinti rašybos tikrintuvą, kaip mes
galėtų būti, problema nustatyti šešių.
>> Taigi, jei mes turime bendro dydžio 26 masyvas todėl, kad tai yra 25 vieta
apačioje, ir galiu reikalauti, kad Alice Pirmasis žodis žodyne
vardai, noriu įterpti į RAM, į šią duomenų struktūros, kur
instinktai sakau, kad Alisos pavadinimas turėtų eiti šiame masyve?
>> Mes turime 26 variantų.
Jeigu mes norime įdėti ją?
Norime ją grupėje nulio, tiesa?
Už Alice, pavadinkime, kad nulį.
Ir B bus vienas ir C bus du.
Taigi, mes ketiname rašyti Alisos vardas čia.
Jei mes tada įdėkite Bob, jo pavadinimas bus eiti čia.
Čarlis bus čia.
Ir taip toliau žemyn per tai duomenų struktūra.
>> Tai nuostabi duomenų struktūra.
Kodėl?
Na, kas yra veikimo laikas įterpiant žmogaus vardą į šią
Duomenų struktūra dabar?
Atsižvelgiant į tai, kad šioje lentelėje bus įgyvendinta, tikrai, kaip masyvo.
Na tai pastovus laikas.
Tai, kad vienas.
Kodėl?
>> Na, kaip jūs nustatote, kur Alisa priklauso?
Jūs žiūrite kuris laiške savo vardą?
Pirmas.
Ir jūs galite gauti ten, jei tai eilutė, tiesiog žiūri eilutę
laikiklis nuliui.
Taigi nulinis pobūdžio eilutę.
Tai paprasta.
Mes padarėme, kad kriptografija priskyrimo savaites.
Ir tada, kai jūs žinote, kad Alisos laiškas yra kapitalo, mes galime atimti
nuo 65 ar sostinę pati, , kuri suteikia mums nulį.
Taigi dabar mes žinome, kad pati Alice priklauso ne vietoje nulio.
>> Ir atsižvelgiant į rodyklę į šiuos duomenis struktūra, tam tikros rūšies, kiek laiko
jis mane rasti vietą nulio masyvo?
Tik vienas žingsnis, tiesa Tai pastovus laikas dėl laisvosios kreipties mes
Siūlomas buvo masyvo funkcija.
Taigi trumpai tariant, suprasti, kas puslapis iš Alisos vardas, kuris yra
šiuo atveju yra, ar galime tik išspręsti kad iki nulio, kur B yra viena, o C
du, suprasti, kad iš yra pastovus laikas.
Aš tiesiog pažvelgti į savo pirmąjį laišką, suprasti, kur nulis
masyvo taip pat pastovus laikas.
Taigi, techniškai tai kaip dviem etapais dabar.
Bet tai dar pastovi.
Taigi mes vadiname, kad didelis Ö vieną, todėl mes įterpiamas Alisa į šią lentelę
pastovus laikas.
>> Bet, žinoma, aš vis naivus čia, tiesa?
Ką daryti, jei ten klasėje Aaronas?
Arba Alicia?
Arba bet kokie kiti pavadinimai, pradedant A. Kur mes einame įdėti
kad asmuo, tiesa?
Aš turiu galvoje, dabar yra tik trys žmonės ant stalo, tai gal mes
reikia įdėti Aaroną vietą nulis vienas du trys.
>> Teisė, galėčiau įdėti čia.
Bet tada, jei mes stengiamės įdėti Dovydą į Šis sąrašas, kur veikia Davidas einate?
Dabar mūsų sistema pradeda skaidyti žemyn, dešinėn?
Kadangi dabar Davidas baigiasi čia jei Aaronas tikrųjų čia.
Ir todėl dabar ši idėja turėti švarus duomenų struktūra, kuri suteikia mums
nuolat laiko intarpai nebėra pastovus laikas, nes turiu
patikrinti, oi, velnių, kažkas jau ne Alisos vietą.
>> Leiskite zondas šių duomenų pailsėti struktūra, ieško vietoje įdėti
kažkas panašaus Aarono vardą.
Ir todėl, kad per daug pradeda priimti linijinį laiką.
Be to, jei jūs dabar norite rasti Aaronas šioje duomenų struktūros, ir jūs
patikrinti ir Aarono vardas čia nėra.
Būtų idealu, jei būtų tiesiog pasakyti Aarono nėra duomenų struktūrą.
Bet jei jūs pradėsite uždirbti vietos Aaronas, kur turėjo būti D
arba E, tu, blogiausiu atveju, turi patikrinti, Visa duomenų struktūra, kad
tokiu atveju ji pereina į kažką tiesinė stalo dydžio.
>> Taigi viskas gerai, aš tai pataisyti.
Problema čia yra, kad aš 26 elementų šiame masyve.
Leiskite pakeiskite jį.
Oi.
Leiskite man pakeisti jį taip, kad, o gerovė iš viso 26 dydis, atkreipkite dėmesį dugną
indeksas ketina pakeisti iki n minus 1.
Jei 26 yra aiškiai per maža, žmonės " pavadinimai, nes ten yra tūkstančiai
pavadinimai pasaulyje, tegul tiesiog padaryti iš 100 ar 1000 ar 10.000.
Tegul tik skirti daug daugiau vietos.
>> Na tai nebūtinai sumažės Tikimybė, kad mes ne turėti du
žmonės, kurių vardai prasideda ir Taigi, jūs ketinate pabandyti įdėti
vardus vietos nulio vietoje.
Jie dar ketina susidurti, kuris reiškia, kad mes vis dar reikia išspręsti įdėti
Alisa ir Aaronas ir Alicia ir kiti Vardai prasidedantys su A kitur.
Bet kiek yra problema tai?
Kas yra tikimybė, kad jūs turi susidūrimų į duomenų
struktūra, kaip tai?
>> Na, leiskite man - mes grįžti į šį klausimą čia.
Ir pažvelgti, kaip mes galime spręsti pirmiausia.
Leiskite atsigriebti šį pasiūlymą čia.
Ką mes ką tik aprašytos yra algoritmas, euristinis vadinamas linijinis
zondavimo, pagal kurią, jei jūs bandėte įdėti kažkas čia šiuos duomenis
struktūra, kuri yra vadinama maišos lentelė, ir ten nėra vietos ten, jūs
tikrai zondas duomenų struktūros patikrinti, ar tai galima?
Ar tai Turimas tai galima?
Ar tai galima?
Ir kai jis pagaliau yra įdėsite pavadinimą, kad jūs iš pradžių skirti
kitur toje vietoje.
Tačiau blogiausiu atveju, tik vietoje gali būti labai apačioje duomenis
struktūra, labai pabaiga masyvo.
>> Taigi linijinis zondavimas, blogiausiu atveju, pereina į linijiniu algoritmu, kur
Aaronas, jei jis atsitinka įterpiamas paskutinis Šiame duomenų struktūros, jis gali
susiduria su šios pirmosios vietos, tačiau tada baigtis nesėkme pačioje pabaigoje.
Taigi tai nėra pastovus laikas Gralis mums.
Šis įterpimą elementų požiūris į duomenų struktūra vadinama maišos
stalo neatrodo, kad būti pastovus laikas bent jau ne bendrojo byloje.
Jis gali perduoti į kažką linijinis.
>> Taigi ką daryti, jei mes išspręsti susidūrimų šiek tiek kitaip?
Taigi čia vis sudėtingesnės požiūris į tai, kas dar
vadinama maišos lentelė.
Ir maiša, nes žemę, ką Aš turiu galvoje, yra puslapis, kad
Aš nurodytas anksčiau.
Norėdami maišos kažkas gali būti suvokiami kaip veiksmažodis.
>> Taigi, jei jūs maišos Alisos pavadinimas, maišos funkcija, taip sakant,
turėtų grįžti numerį.
Šiuo atveju yra nulis, jei ji priklauso ne vieta nulis, vienas, jei ji priklauso ne
vieta viena, ir kt.
Taigi, mano maišos funkcija iki šiol buvo super paprasta, tik žiūri
pirmoji raidė kieno nors vardu.
Bet maišos funkcija priima kaip įėjimas kai duomenų vienetą,
eilutę, int, nesvarbu.
Ir tai išspjauna specifiniu numerį.
Ir šis skaičius yra kur, kad duomenys elementas priklauso ir duomenų struktūros
žinoma, čia kaip maišos lentelė.
>> Taigi tiesiog intuityviai, tai šiek tiek kitokiame kontekste.
Tai iš tikrųjų yra nuoroda į pavyzdį dalyvauja gimtadieniai, jei
ten gali būti tiek, kiek 31 dienų mėnesį.
Bet ką šis asmuo nusprendžia daryti susidūrimo atveju?
Kontekstas dabar yra, o ne susidūrimas pavadinimai, bet apie gimtadienius susidūrimo,
jei du žmonės turi tą patį gimtadienį spalio 2 d, pvz.
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Taip, kad čia mes turime sverto sujungtų sąrašus.
Taigi atrodo šiek tiek kitaip nei mes išsitraukė jį anksčiau.
Bet mes, atrodo, turi masyvo kairėje pusėje.
Tai vienas indeksas, ne ypatingos priežasties.
Bet tai dar masyvo.
Tai rodykles masyvo.
Ir kiekvienas iš šių elementų, kiekvienas šių apskritimų nerijos - velniop
ty niekinis - kiekvienas iš jų patarimų, matyt, nukreipta į
kas duomenų struktūra?
Susijęs sąrašą.
>> Taigi dabar mes turime galimybę į sunku kodą į mūsų programą
pateiktos lentelės dydis.
Tokiu atveju, mes žinome, kad niekada daugiau nei 31 dienų per mėnesį.
Taigi sunku kodavimo kaip 31 vertę, pagrįstas šiame kontekste.
Į pavadinimų kontekste, sunku kodavimo 26 nėra nepagrįsta tai sudaro žmonių
pavadinimai tik pradėti, pavyzdžiui, abėcėlė dalyvauja per Z.
>> Mes galime prisikimšti juos visus į tą duomenų struktūra tol, kol, kai mes gauti
susidūrimo, mes ne pateikti pavardes čia mes vietoj galvoti apie šių ląstelių
ne kaip stygos patys, bet kaip rodykles į, pavyzdžiui, Alice.
Ir tada Alisa gali turėti kitą žymeklį su kitu pavadinimu, pradedant
A. Ir Bobas tikrųjų vyksta čia.
>> Ir jei yra dar vienas pavadinimas prasideda su B, jis baigiasi čia.
Ir todėl kiekvienas iš šio elementų stalo du, jei mes sukūrėme šį
šiek tiek daugiau gudriai -
come on -
jei mes sukūrėme tai šiek tiek daugiau protingai, dabar tampa prisitaikanti duomenis
struktūra, kurioje nėra sunku apriboti nuo to, kiek elementų galite įterpti
į jį, nes jei jūs turite susidūrimo, tai gerai.
Tiesiog eikite į priekį ir pridėti jį prie ką mes matėme šiek tiek atgal buvo
žinomas kaip susietą sąrašą.
>> Na galime pristabdyti tik akimirką.
Kokia susidūrimo tikimybė į pirmąją vietą?
Teisė, gal aš per galvoju, gal Aš per inžinerinių šią problemą,
nes jūs žinote, ką?
Taip, galiu sugalvoti savavališkai pavyzdžių Off mano galvos viršaus, pavyzdžiui,
Allison ir Aaronas, bet iš tikrųjų, nes tolygiai pasiskirstytų
įėjimai, kad yra keletas atsitiktinių intarpai į duomenų struktūros, kas iš tikrųjų yra
iš susidūrimo tikimybė?
Na Pasirodo, tai tikrai Super didelis.
Leiskite man apibendrinti tai Problema yra, kaip šis.
>> Taigi daugelyje n kambarį CS50 studentų, kas Tikimybė, kad bent
du studentai kambarį turi tas pačias gimtadienis?
Taigi yra kas. keletas Hund -
200, 300 žmonės čia ir keletas šimtai žmonių namuose šiandien.
Taigi, jei jūs norėjote paklausti savęs, kas du žmonės tikimybė
Šiame kambaryje, turintys tą patį gimtadienį, galime suprasti tai.
Ir galiu reikalauti iš tikrųjų yra du žmonės su tuo pačiu gimtadienį.
>> Pavyzdžiui, ar kas turi šiandien švenčia gimtadienį?
Vakar?
Rytoj?
Gerai, kad jis jaučiasi kaip aš ruošiuosi turėti tai padaryti 363 arba tiek daugiau
kartus tikrųjų išsiaiškinti jei mes turime susidūrimo.
Arba mes galime tiesiog padaryti tai matematiškai o ne nuobodžiai
tai daryti.
Ir pasiūlyti veiksmus.
>> Taigi, aš siūlau, kad mes galime modeliuoti Tikimybė, du žmonės, turintys
pats gimtadienis kaip 1 tikimybe atėmus niekas turintys tikimybė
pats gimtadienis.
Taigi, norint gauti tai, ir tai tik išgalvotas būdas tai rašau, nes
pirmas žmogus į kambarį, jis ar ji gali turėti bet įmanoma vieną
gimtadieniai darant prielaidą, kad 365 dienų per metus, su atsiprašymą asmenims, turintiems
29 Vas gimtadienis.
>> Taigi, pirmas žmogus šiame kambaryje nemokamai turėti jokių gimtadienių numeris
iš 365 galimybių, kad mes tai padarysime 365 padalintas iš 365,
kuri yra viena.
Kitas asmuo kambaryje, jei tikslas yra išvengti susidūrimo, galime tik
jo arba jos gimtadienis, kaip daug įvairių galimų dienų?
364.
Taigi antroji kadencija šiame išraiškos esmės daro tą matematiką mums
atėmus ne vieną galimą dieną.
Ir tada kitą dieną, kitą dieną, Kitą dieną iki bendro skaičiaus
žmonių kambaryje.
>> Ir jei mes tada apsvarstyti, ką gi ne kiekvienas asmuo tikimybė
unikalių gimtadieniai, tačiau ir vėl 1 atėmus kad tai, ką mes gauti yra išraiška
kuri gali labai Fantazyjnie atrodyti taip.
Bet tai įdomiau ieškoti vizualiai.
Tai schema kur ant x ašies yra žmonių skaičius kambaryje,
skaičius gimtadienius.
Į Y ašies yra tikimybė, dėl susidūrimo, du žmonės
turintys tą patį gimtadienį.
>> Ir Pagal šią kreivę išsinešimui yra kad kaip tik jums patinka 40
studentų, esate į 90% tikimybe combinatorically dviejų
žmonės ar daugiau turintys pats gimtadienis.
Ir kai jums patinka 58 žmonėms tai beveik 100% progos dviejų
žmonių kambaryje teks pats gimtadienis, nors ten
365 arba 366 galimi kaušai ir tik 58 žmonių kambaryje.
Tiesiog statistiškai jūs greičiausiai gauti susidūrimų, kuris trumpai
motyvuoja šią diskusiją.
Kad net jei mes gauti išgalvotas čia, ir pradėti turintys šių grandines, mes vis dar
teks susidūrimų.
>> Taigi, kad kyla klausimas, kas yra kaina tai įkišimo ir naikinimus
į duomenų struktūros, kaip tai?
Na leiskite man pasiūlyti -
ir leiskite man grįžti prie ekrano per čia - jei mes n elementų
sąrašas, todėl, jei mes bandome įterpti n elementų, ir mes turime
kiek iš viso kibirai?
Tarkime, kad 31 iš viso kibirus į gimtadienius atveju.
Koks maksimalus ilgis vieno Šių tinklų potencialiai?
>> Jei vėl ten 31 galima Gimtadieniai tam tikrą mėnesį.
Ir mes tiesiog drumzlių visus -
iš tikrųjų tai kvailas pavyzdys.
Padarykim 26 vietoj.
Taigi, jei iš tikrųjų turi žmones, kurių vardai ir pavardės pradėti iki Z, taip suteikiant
mus 26 galimybių.
Ir mes naudojame duomenų struktūrą kaip vienas mes tik pamačiau, kai mes turime
rodykles masyvas, kurių kiekvienas atkreipia dėmesį į susietą sąrašą, kur
Pirmasis sąrašas yra visi su pavadinimu Alisa.
Antrame sąraše yra visos su pavadinimas pradedant, pradedant
su B, ir kt.
>> Kas greičiausiai ilgis kiekvieno šie sąrašai jei mes manome, gražus švarus
paskirstymo pavadinimų iki Z visoje duomenų struktūros?
Yra n žmonių duomenų struktūros padalintas iš 26, jei jie gražiai
paskirstyti per visą duomenų struktūra.
Taigi kiekvienos iš šių ilgis tinklai yra n dalijamas iš 26.
Tačiau didelis O žymėjimą, kas tai?
Kas tai tikrai?
Taigi tai tikrai tik n, tiesa?
Kadangi mes jau sakiau anksčiau, kad ugh jums padalinti iš 26.
Taip, iš tikrųjų jis yra greitesnis.
Tačiau teoriškai tai nėra iš esmės visa tai greičiau.
>> Taigi mes neatrodo, kad būti visi, kad daug arčiau šio Gralis.
Tiesą sakant, tai yra tik linijinis laikas.
Heck, šiuo metu, kodėl ne mes tiesiog naudoti vienas didžiulis susijęs sąrašą?
Kodėl mes tiesiog naudoti vienas didžiulis masyvas saugoti vardai
visi į kambarį?
Na, ar dar kažkas įtikinamų apie maišos lentelė?
Ar yra dar kažkas įtikinamų apie duomenų struktūros
kad atrodo taip?
Tai.
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Teisė, ir dar kartą, jei tai tik linijinis laikas algoritmas ir
linijinis laiko duomenų struktūra, kodėl ne aš tiesiog laikyti kiekvieno vardą didelis
masyvas, arba į didelį susijusios sąraše?
Ir nebedaryti CS tiek daug sunkiau nei ji turi būti?
Kas yra įtikinamų apie tai, net nors aš subraižyti jį?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1 intarpai yra ne?
Brangus nebėra.
Taigi intarpai potencialiai galėtų dar būti pastovus laikas, net jei jūsų duomenų
struktūra atrodo taip, masyvas patarimų, kurių kiekviena yra nukreipta į
potencialiai Tinkliniai sąrašą.
Kaip tu galėjai pasiekti pastovus laikas įterpimo vardų?
Klijuoti jį į priekį, tiesa?
>> Jei mes paaukoti dizaino įvarčio anksčiau, kur mes norėjome išlaikyti
kiekvienas vardas, pavyzdžiui, rūšiuojami, ar visi ant scenos numerius rūšiuojami,
tarkime, kad turime Unsorted susijęs sąrašą.
Tai kainuoja tik mums vieną ar du žingsnius, Kaip ir Ben ir Brian atveju
anksčiau, įterpti elementą į sąrašo pradžioje.
Taigi, jei mes nerūpi rūšiavimo visas pavadinimų, prasidedančių arba visas
vardai prasidedantys raide B, mes vis dar galime pasiekti pastovią laiko užpildymui.
Dabar žiūrint Alisa arba Bob arba bet kokį vardą apskritai dar kas?
Tai didelis O n dalijamas iš 26 visų idealus atvejis, kai visi yra vienodai
paskirstyti, kur yra tiek daug s nes yra Z, kuris yra tikriausiai
nerealus.
Bet tai dar tiesinis.
>> Bet čia mes einame atgal iki taško, iš asimptotinėje notacijos Būdama
teoriškai tiesa.
Tačiau realiame pasaulyje, jei galiu reikalauti, kad mano programa gali ką nors padaryti 26 kartų
greičiau nei jūsų, kurių programa jūs ketinate nori naudojate?
Jūsų arba mano, kuris yra 26 kartų greičiau?
Nereikėtų pamiršti, kad asmuo, kurio yra 26 kartų greičiau, net jei teoriškai
mūsų algoritmai paleisti pats asymptotic darbo.
>> Leiskite man pasiūlyti skirtingi sprendimas apskritai.
Ir jei tai nėra smūgis apsigalvoti, mes iš duomenų struktūrų.
Taigi, tai jis trie -
rūšies kvailas pavadinimas.
Jis kilęs iš paieškų, o žodis rašomas TRIE, T-R-i-E, nes
kursas paieška skamba kaip TRIE.
Bet tai istorija žodžio TRIE.
>> Taigi trie yra iš tiesų, kai medžių rūšis, ir tai taip pat tą žodį žaisti.
Ir nors jums gali ne visai matyti su šiuo vizualizacija, trie yra
medžio struktūra, kaip šeimos medį viena protėvis viršuje ir daug
anūkai ir proanūkiai kaip palieka ant dugno.
Tačiau kiekvienas į TRIE mazgas yra masyvas.
Ir tai masyve - ir tegul per daug supaprastinti for a moment, - tai
masyvas, šiuo atveju, dydžio 26, kur kiekvienas mazgas vėl yra dydžio masyvas
26, kur nulinis elementas, kad masyvuose, o paskutinis
elementas kiekvienas toks masyvas yra Z.
>> Taigi aš siūlau, tada, kad šie duomenys struktūra, vadinama TRIE, gali būti
naudojamas taip pat saugoti žodžius.
Mes matėme metu senumo, kaip mes galime laikyti Kitaip tariant, ar šiuo atveju pavadinimų, ir mes
matėme, kaip mes galime laikyti numerius, bet jei mes orientuojamės į pavadinimų ar tinkleliuose
čia pastebėti tai, kas įdomu.
Galiu reikalauti, kad vardas Maxwell viduje šios duomenų struktūros.
Kur matote Maxwell?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Kairėje.
Taigi, kas įdomu šiuos duomenis struktūra, o ne saugoti
styginių M-X-W-El-L-L Backslash nulis, visi Kaimynystėje, ką jūs, o ne daryti
laikosi.
Jei tai, pavyzdžiui, duomenų struktūros trie, kiekvieno iš jų mazgų vėl masyvas,
ir norite išsaugoti Maxwell, pirmiausia indeksas ir taip šaknis mazge, todėl
kalbėti, viršutinį mazgą, ne vietos M, teisė, todėl
maždaug į vidurį.
Ir iš ten, jums sekti rodyklė vaikas mazgai, taip sakant.
Taigi, šeimos medį prasme, jums sekti jį žemyn.
Ir, kad nuves jus į kitą mazgą Kairėje, kuris yra
tik dar vienas masyvas.
>> Ir tada, jei norite išsaugoti Maxwell, Jums susirasti žymiklį, kuri atstovauja
, O tai yra vienas iš čia.
Tada jūs einate į kitą mazgą.
Ir pranešimas - tai kodėl paveikslėlio šiek tiek klaidinantis -
tai mazgas atrodo super maža.
Tačiau šios teisės yra Y ir Z. Tai tiesiog autorius sutrumpintas
paveikslėlį tiek, kad jūs iš tikrųjų pamatyti dalykus.
Priešingu atveju šį paveiksliuką Būtų labai platus.
Taigi, dabar jūs indeksą į vietos X, tada W Tada E, tada L, tada L. Tada kas
tai smalsumas?
>> Na, jei mes naudojame šią naujos rūšies imtis, kaip saugoti eilutę
duomenų struktūra, jums vis tiek reikia iš esmės patikrinti išjungti duomenų
struktūra, kad žodis baigiasi čia.
Kitaip tariant, kiekvienas iš šių mazgų kažkaip turi prisiminti, kad mes
laikytasi visų šių patarimų ir palieka mažai
duonos trupiniai apačioje čia šio struktūra rodo, M-A-X-W-e-L-L yra
Iš tiesų šioje duomenų struktūra.
>> Taigi, mes galime tai padaryti taip.
Kiekvienas iš paveikslėlio Mes tiesiog mazgų Pjūklas turi vieną, dydžio 27 masyvo.
Ir tai dabar 27, nes p nustatytas šešių, mes tikrai suteiks jums kabutes,
todėl mes galime turėti tokius pavadinimus kaip O'Reilly ir kiti su kabutes.
Bet pati idėja.
Kiekvienas iš šių elementų masyvo nukreipia į struct
mazgų, vartotojų tad tiesiog mazgas.
Taigi tai yra labai primenantis mūsų susietą sąrašą.
>> Ir tada aš turiu Būlio, kurį aš skambinti žodį, kuris yra tik bus
tiesa, jei žodis baigiasi tai mazgas medžio.
Jis efektyviai atstovauja mažai trikampis matėme prieš akimirką.
Taigi, jei žodis baigiasi tos mazgas medis, kad žodis laukas bus tiesa,
kuris konceptualiai Odfajkowanie arba mes piešimo Šis trikampis, taip nėra
yra žodis čia.
>> Taigi tai yra trie.
Ir dabar klausimas, ką yra jo veikimo laikas?
Ar tai didelis O n?
Ar tai kažkas kita?
Na, jei jūs turite n vardus šiuos duomenis struktūra, Maksvelo gerovę tik vienas
jiems, kas yra veikimo laikas įdėdami arba rasti Maxwell?
Kas važiavimo laikas įterpti Maxwell?
Jei yra n kitų pavadinimų jau stalo?
Taip?
>> STUDENTŲ: [nesigirdi].
>> GARSIAKALBIS 1: Taip, tai ilgis vardo, tiesa?
Taigi M-x-w-e-l-l, kad jis jaučiasi kaip tai algoritmas yra didelis O iš septynių.
Dabar, žinoma, pavadinimas ilgis gali būti įvairus.
Gal tai sutrumpintas pavadinimas.
Gal tai jau pavadinimas.
Bet kas svarbiausia čia yra tai, kad tai pastovus skaičius.
O gal tai nėra labai pastovus, Bet Dievas, jei realiai, į
žodyną, ten tikriausiai kai riba dėl laiškų skaičių
asmens vardas konkrečioje šalyje.
>> Ir taip mes galime manyti, kad vertė yra pastovi.
Aš nežinau, kas tai yra.
Tai tikriausiai didesnis nei mes manome, kad ji yra.
Nes ten visada kai kampas atveju su crazy ilgu pavadinimu.
Taigi galime vadinti k, bet jis vis dar pastovus matyt, nes kiekvienas
vardas pasaulyje, bent jau pirma šalis, yra tai, kad ilgis arba
trumpesnis, todėl pastovus.
Bet kai mes kažką pasakė yra didelis O iš pastovios vertės, kas tai
tikrai atitiks?
Tai tikrai tas pats kaip sako pastovų laiką.
>> Dabar mes rūšies sukčiavimo, tiesa?
Mes rūšies sverto tam tikrą teoriją čia pasakyti, kad gerai, kad iš K
tikrai tik kad vienas, ir tai pastovus laikas.
Bet ji tikrai yra.
Kadangi pagrindinė įžvalga yra ta, kad jei mes n vardus jau tai
duomenų struktūra, ir mes įterpti Maksvelo yra laiko užtrunka mus
įterpti Maxwell kiek nenukenčia pagal tai, kiek kiti žmonės
yra duomenų struktūros?
Ar neatrodo, kad būti.
Jeigu aš turėjo milijardą daugiau elementų į šį trie ir įdėkite Maxwell, yra
jis išvis veikia?
Ne.
Ir tai, skirtingai nei bet kuriuo paros duomenų struktūros mes matėme iki šiol, kur
veikimo laikas jūsų algoritmas visiškai nepriklausomi nuo to, kiek
medžiaga yra ar nėra jau toje duomenų struktūra.
>> Ir taip su tai suteikia jums dabar yra galimybė šešių rinkinys p, kuris bus
vėl įtraukti įgyvendinant savo Rašybos tikrintuvas, skaityti 150.000
žodžiai, kaip geriausia laikyti, kad nebūtinai yra akivaizdūs.
Ir nors aš tikėjosi rasti Gralis, aš ne
teigia, kad trie yra.
Tiesą sakant, maišos lentelė gali labai gerai įrodyti, kad bus daug efektyvesnis.
Tačiau tai tik -
tai tik vienas iš dizaino sprendimus jūs turite padaryti.
>> Tačiau uždarymo Paimkime 50 ar taip sekundžių pažvelkite, kas slypi žvilgtelėti
prieš kitą savaitę ir vėliau mes pereiti iš šio komandinės eilutės
pasaulyje, jei C programos dalykų internete pagrįstas ir kalba kaip PHP ir
JavaScript ir interneto pati, protokolai, pavyzdžiui, HTTP, kurios jūs
savaime suprantamu dalyku metų dabar, ir įvedėte labiausiai kiekvienas
dieną, galbūt, ar matė.
Ir mes pradėsime žievelės atgal sluoksniai, kas yra internetas.
Ir kas yra kodas, kuris scenarijumi grindžiamos šiandienos įrankiai.
Taigi 50 sekundžių šio erzina čia.
Aš jums Warriors internete.
>> [VIDEO PLAYBACK]
>> -Jis atėjo su pranešimu.
Su protokolu, visi jo paties.
Jis atėjo į žiaurių ugniasienių pasaulyje, uncaring maršrutizatoriai, ir pavojus toli
blogiau, nei mirties.
Jis greitas.
Jis stiprus.
Jis TCPIP.
Ir jis gavo savo adresą.
Warriors internete.
>> [PABAIGA VIDEO PLAYBACK]
>> GARSIAKALBIS 1: Štai kaip interneto turi veikti kaip kitą savaitę.