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. 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š 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ę.