SPEAKER 1: Labi, tāpēc mēs esam atpakaļ. Laipni lūdzam CS50. Tas ir beigu septiņiem nedēļā. Tāpēc atgādinām, ka pēdējo reizi, mēs sākām meklē nedaudz sarežģītāka datu struktūras. Tā kā līdz šim, viss, kas mums bija patiešām mūsu rīcībā bija tas, masīvs. Taču, pirms mēs izmestu masīvs, jo ne visu, kas interesants, ko tas patiešām faktiski ir, kādi ir daži no plusi šo vienkāršo datu struktūru līdz šim? Kas ir tas labi? Līdz šim, kā mēs esam redzējuši? Ko jums? Nekas. STUDENTU: [nedzirdama]. SPEAKER 1: Kas tas ir? STUDENTU: [nedzirdama]. SPEAKER 1: Fiksēta izmēra. Labi, tad kāpēc ir fiksēta izmēra laba, lai gan? STUDENTU: [nedzirdama]. SPEAKER 1: Labi, tāpēc tas ir efektīvs sajūta, ka jūs varat piešķirt fiksēta summa telpu, kas, cerams, Tieši tik daudz kosmosa, kā jūs vēlaties. Tātad tas varētu būt absolūti plus. Kas vēl veido puse no masīva? Yeah? STUDENTU: [nedzirdama]. SPEAKER 1: Visi - žēl? STUDENTU: [nedzirdama]. SPEAKER 1: Visas kastes atmiņā vai blakus viens otram. Un tas ir noderīgi, - kāpēc? Tas ir diezgan patiess. Bet kā mēs varam izmantot šo patiesību? STUDENTU: [nedzirdama]. SPEAKER 1: Tieši tā, mēs varam sekot kur viss ir vienkārši zinot viens adrese, proti, no adrese Pirmais baits šī rieciens atmiņas. Vai gadījumā, ja no virknes, adrese no pirmā char šajā virknē. Un no turienes, mēs varam atrast beigām virkni. Mēs varam atrast uz otro elementu, ka Trešais elements, un tā tālāk. Un tā iedomātā veids, kā aprakstīt, ka iezīme ir tā, ka masīvi dod mums brīvpieejas. , Tikai izmantojot kvadrātiekava nošu un numuru, jūs varat pāriet uz īpašs elements masīva pastāvīgu laiku, Big O vienu, lai runāt. Bet tur ir bijuši daži downsides. Kas masīvs nav darīt ļoti viegli? Kas ir tas nav labi? STUDENTU: [nedzirdama]. SPEAKER 1: Kas tas ir? STUDENTU: [nedzirdama]. SPEAKER 1: Paplašinot lieluma. Tātad no masīva downsides ir tieši pretējs tam, ko upsides ir. Tātad, viens no downsides ir ka tā ir fiksēta izmēra. Tātad, jūs nevarat īsti augt. Jūs varat pārdalīt lielāku rieciens atmiņa, un pēc tam pārvietot vecās elementus jaunajā masīvs. Un tad bez vecā masīvs, lai Piemēram, izmantojot malloc vai līdzīgu funkciju sauc realloc, kas pārdalīt atmiņas. Realloc, kā malā, cenšas dot jums atmiņa, kas ir blakus masīva kas jums jau ir. Bet tas varētu pārvietoties lietas apkārt vispār. Bet sakot, tas ir dārgi, vai ne? Jo, ja jums ir rieciens atmiņas šis lielums, bet jūs patiešām vēlaties vienu Šāda izmēra, un jūs vēlaties, lai saglabātu sākotnējie elementi, jums ir aptuveni lineārā laika kopēšanas process kas ir nepieciešams notikt no Vīrietis masīvu jaunu. Un realitāte ir jautā darbojas sistēma atkal un atkal, un Vēlreiz liels gabalos atmiņas var sākt izmaksas jums kādu laiku, kā arī. Tātad, tas ir gan svētība un lāsts, kas noslēpt, ka šie bloki ir no noteikta lieluma. Bet, ja mēs ieviestu, nevis kaut ko piemēram, tas, ko mēs saucām saistītais sarakstu, mēs iegūt dažas upsides un daži downsides arī šeit. Tātad saistīts saraksts ir vienkārši dati struktūra, kas sastāv no C structs jo šī gadījumā, ja struktūrai, atsaukšana, ir tikai konteiners, lai viens vai vairāki specifiski veidu mainīgajiem lielumiem. Šajā gadījumā, ko darīt datu tipus šķiet iekšpusē struktūrai, kas Pēdējo reizi mēs sauc par mezglu? Katrs no šiem taisnstūriem ir mezglā. Un katrs no mazajām taisnstūru iekšpusē tā ir datu tips. Kādi bija mēs sakām tie bija pirmdien? Yeah? STUDENTU: [nedzirdama]. SPEAKER 1: mainīga, un rādītājs, vai precīzāk, int, lai n, un rādītājs apakšā. Abi no tiem gadās būt 32 biti, pēc Vismaz uz datora, piemēram, CS50 šo Appliance, un lai viņi sagatavots tikpat lieluma. Tātad, ko izmanto rādītāju gan attiecībā uz šķietami? Kāpēc pievienot šīs bultiņas tagad, kad bloki bija tik jauks un tīrs un vienkāršs? Kas ir rādītājs dara mums ir katrs no šiem mezgliem? STUDENTU: [nedzirdama]. SPEAKER 1: Tieši tā. Tā stāsta jums, kur nākamā ir. Tāpēc es veida izmantot analoģiju izmantojot diegu, lai kārtotu ar pavedienu šos mezglus kopā. Un tas ir tieši tas, ko mēs darām ar norādes, jo katrs no tiem gabalos atmiņas var vai nevar būt blakus, atpakaļ atpakaļ atpakaļ iekšpusē RAM, jo katru reizi, kad jūs zvanu malloc sakot, man pietiek baiti jaunu mezglu, tas varētu būt šeit, vai tas varētu būt šeit. Tas varētu būt šeit. Tas varētu būt šeit. Jūs vienkārši nezināt. Bet izmantojot norādes īpaši adresēm šie mezgli, jūs varat šūt tos kopā tādā veidā, ka izskatās vizuāli kā sarakstā, pat tad, ja šīs lietas ir visu izlīdzina visā jūsu vienu vai Jūsu divi vai jūsu četru gigabaitu RAM iekšā savā datorā. Tātad negatīvie, tad, saistīts saraksts ir tas, ko? Kāda ir cena, mēs esam acīmredzot maksā? STUDENTU: [nedzirdama]. SPEAKER 1: Vairāk vietas, vai ne? Mēs esam, šajā gadījumā, divas reizes summu vietas, jo mēs esam izgājuši no 32 bitiem uz katru mezglu, par katru int, tāpēc tagad 64 bitus, jo mums ir turēt ap rādītāju, kā arī. Jūs saņemsiet lielāku efektivitāti, ja jūsu struktūrai ir lielāks nekā šo vienkāršo lietu. Ja jums tiešām ir students iekšā no kuriem ir no virknes pāris par nosaukumu un māju, varbūt ID numurs, varbūt dažas citas jomas vispār. Tātad, ja jums ir pietiekami liela struct, tad varbūt par rādītāju izmaksas ir nav tik liels darījumu. Tas ir mazliet stūra gadījumā, ar to, ka mēs esam uzglabātu tik vienkāršs primitīva iekšpusē saistītajā sarakstā. Bet punkts ir tas pats. Jūs esat noteikti tērēt vairāk atmiņa, bet jūs saņemat elastību. Jo tagad, ja es gribu, lai pievienotu elementu sākumā šī saraksta, Man ir piešķirt jaunu mezglu. Un man ir vienkārši atjaunināt tiem bultas kaut kā, tikai pārvietojot dažas norādes apkārt. Ja es gribu, lai ievietotu kaut ko uz vidū saraksta, man nav push visi malā tāpat kā mēs to darījām nedēļu agrāk ar mūsu brīvprātīgajiem, kuri bija masīvs. Es varu tikai piešķirt jaunu mezglu un tad vienkārši norādīt uz bultiņām dažādos virzienos, jo tas nav ir jāpaliek faktisko atmiņas patiess līnija, piemēram, es esmu sastādīts tā šeit uz ekrāna. Un tad visbeidzot, ja jūs vēlaties, lai ievietotu kaut beigās saraksta, tas ir vēl vieglāk. Tas ir sava veida patvaļīgu apzīmējums, bet 34 ir rādītājs, ņem minējums. Kāda ir tās rādītāju visvairāk vērtība iespējams izdarīt veida, piemēram, veco skola antena tur? STUDENTU: [nedzirdama]. SPEAKER 1: Tas ir iespējams, null. Un tiešām tas ir viens no autora pārstāvību null. Un tas ir null, jo jūs absolūti ir nepieciešams, lai zina, kur beigām linked saraksts ir, citādi jums saglabāt tekstu un sekojot un ievērojot šos bultas uz kādu atkritumu vērtībai. Tātad null nozīmēs, ka tur nav vairāk mezglus pa labi no 34 numuru, šajā gadījumā. Tāpēc mēs ierosinām, ka mēs varam īstenot tas mezglu kodu. Un mēs esam redzējuši šāda veida sintakses agrāk. Typedef tikai nosaka jaunu veidu mums, dod mums sinonīmu, piemēram, string bija char *. Šajā gadījumā, tas notiek, lai dotu mums saīsināts apzīmējums lai struct mezglā var nevis vienkārši rakstīts kā mezgls, kas ir daudz tīrītājs. Tas ir daudz mazāk runīgs. Iekšpusē mezglā ir acīmredzami int sauc n, un pēc tam struktūrai mezgls * kas nozīmē tieši to, ko mēs vēlējāmies bultas nozīmē, rādītāju uz otru mezgla tieši tādu pašu datu tipu. Un es ierosinu, ka mēs varētu īstenot meklēšanas funkciju, piemēram, tas, kas tajā pirmā acu uzmetiena varētu šķist mazliet sarežģīta. Bet pieņemsim redzēt to kontekstā. Ļaujiet man iet vairāk nekā uz ierīci šeit. Ļaujiet man atvērt failu ar nosaukumu Saraksts nulle dot st. Un tas ir tikai definīciju mēs tikko redzēju pirms brīža šos datus veids, ko sauc par mezglu. Tāpēc mēs esam izveidojuši kas stājas dot h failā. Un kā malā, lai gan tas programma, ka jūs gatavojaties redzēt, ir ne viss, kas sarežģīts, tas ir patiešām konvencija, rakstot programmu, lai nodot lietas, piemēram, datu tipu, lai vilktu konstantes reizēm, iekšpusē jūsu header failu un ne vienmēr Jūsu C failu, protams, ja jūsu programmām iegūt lielāku un lielāku, lai jūs zināt, kur meklēt gan dokumentācija, atsevišķos gadījumos, vai attiecībā uz pamatiem, piemēram, tas, ka definīcija dažu tipu. Ja es tagad atvērt sarakstu nulle dot c, ievērosiet dažas lietas. Tā ietver dažas header failus, lielākā daļa par ko mēs esam redzējuši iepriekš. Tas ietver savu header failu. Un kā malā, tāpēc tas ir dubultā citātus šeit, atšķirībā no leņķa iekavās uz līnijas, kas Es esmu uzsvērusi tur? STUDENTU: [nedzirdama]. SPEAKER 1: Jā, tā tas ir vietējais fails. Tātad, ja tas ir vietējais fails savu šeit 15 līnijas, piemēram, jūs izmantojat pēdiņas vietā no leņķveida iekavās. Tagad tas ir diezgan interesants. Ievērojiet, ka es esmu atzīts pasaules mainīgais šajā programmā 18 līnijas sauc pirmkārt, ideja ir, tas ir būs rādītājs uz pirmo mezglu manā saistītajā sarakstā, un es esmu inicializēts tai null, jo es esmu nav piešķirts faktiska mezgli tikai yet. Tātad tas nozīmē, gleznieciski, ko mēs redzēju pirms brīža attēlā kā ka rādītājs par tālu Kreisajā pusē. Tāpēc tagad, ka rādītājs nav bultiņu. Tā vietā ir tikai nulle. Bet tas ir to, kas būs adrese Pirmajām mezglu šajā sarakstā. Tāpēc es esmu īstenota tā ir globāla jo, kā jūs redzēsiet, tas viss Programmā nav dzīvē ir jāīsteno saistīts saraksts par mani. Tagad es esam ieguvuši dažas prototipus šeit. Es nolēmu, lai īstenotu funkcijas, piemēram, dzēšanu, ievietošanas, meklējot, un šķērsošana - pēdējais vienkārši ir staigāt pāri sarakstā, izdrukāt savus elementus. Un tagad šeit ir mans galvenais rutīnas. Un mēs ne tērēt pārāk daudz laika šiem, jo ​​tas ir sava veida, cerams veco cepuri, ko tagad. Es esmu gatavojas veikt šādas darbības, kamēr lietotājs sadarbojas. Tātad viena, es esmu gatavojas drukāt veic šo izvēlni. Un es esmu formatēti to kā tīri kā es varētu. Ja lietotājs vienā, tas nozīmē, ka viņi vēlas, lai izdzēstu kaut ko. Ja lietotājs veidu divi, tas nozīmē, ka viņi vēlas, lai ievietotu kaut ko. Un tā tālāk. Es esmu gatavojas, lai pēc tam ātri tad uz komandu. Un tad es esmu gatavojas izmantot GetInt. Tātad tas ir ļoti vienkāršs menuing interfeisu, kur jūs vienkārši ir veids numurs kartēšanas uz vienu no šīm komandām. Un tagad man ir jauka tīru slēdzi paziņojumu, kas notiek, lai ieslēgtu kāds lietotājs drukāti collas Un, ja tie drukāti vienu, es ņemšu zvanu dzēst un pauze. Ja tie drukāti divi, es ņemšu zvanu ievietot un lauzt. Un tagad novērojat es esmu likts katrā no tiem uz vienas līnijas. Tas ir tikai stilistiskās lēmums. Parasti mēs esam redzējuši kaut ko kā šis. Bet es tikko nolēma, atklāti sakot, mana programma izskatījās vairāk lasāms, jo tas bija tikai četri gadījumi, tikai sarakstu to, kā šis. Pilnīgi likumīgu izmantošanu stilu. Un es esmu gatavojas darīt to tik ilgi, kamēr lietotājs nav ievadījis nulli, ko es nolēma nozīmēs viņi vēlas atmest. Tāpēc tagad paziņojums, ko es esmu gatavojas darīt šeit. Es esmu gatavojas, lai atbrīvotu sarakstu acīmredzot. Bet vairāk par to tikai brīdi. Pieņemsim vispirms palaist šo programmu. Tātad, ļaujiet man sniegt lielāku termināli logu, dot slash sarakstu 0. Es iešu uz priekšu un ievietojiet ar ierakstot divi, skaitlis, piemēram, 50, un tagad jūs redzēsiet saraksts tagad ir 50. Un mans teksts vienkārši ritinot uz augšu mazliet. Tāpēc tagad paziņojums sarakstā ir numuru 50. Darīsim citas ieliktni, veicot divus. Let 's tipa numuru, piemēram, vienu. Saraksts ir tagad viens, kam seko 50. Tātad tas ir tikai tekstuālu pārstāvība no saraksta. Un pieņemsim ievietot vēl vienu numuru, piemēram, skaitlis 42, kas ir cerams gatavojas galu galā vidū, jo šī programma jo īpaši veidu tā elementus kā tas ievieto tos. Tātad mums ir tā. Super vienkārša programma, kas varētu absolūti ir izmantots masīvu, bet es gadās būt, izmantojot saistītu sarakstu tikai, lai es varētu dinamiski augt un sarauties to. Tātad, pieņemsim to apskatīt meklēšanas, ja es palaist komandu trīs, es gribu, lai meklētu , teiksim, uz numuru 43. Un nekas netika acīmredzot atrasts, tāpēc, ka es saņēmu atpakaļ nekādu atbildi. Tātad, pieņemsim darīt atkal. Meklēt. Pieņemsim meklēt 50, vai drīzāk meklēt par 42, kas ir patīkami maz smalks nozīme. Un es atklāju dzīves jēgu tur. Numuru 42, ja jūs nezināt, atsauces, Google to. Labi. Tātad, kādi ir šo programmu darīts attiecībā uz mani? Tas ir tikai ļāva man, lai ievietotu tādējādi tālu un meklēt elementiem. Pieņemsim ātri uz priekšu, tad, lai ka funkcija mēs paskatījās pirmdien kā teaser. Tātad šo funkciju, es apgalvot, meklē elements sarakstā ar pirmo viens, pamudinot lietotājam, un tad zvana GetInt iegūt faktisko int ka jūs vēlaties meklēt. Tad paziņojums šo. Es esmu gatavojas izveidot pagaidu mainīgo 188 rindā sauc rādītājs - PTR - varēja saukt tā neko. Un tas ir rādītājs, lai mezglu tāpēc es teicu mezglā * tur. Un es esmu inicializēšana, ka tas ir vienāds ar Pirmais tāpēc, ka man faktiski ir mana pirkstu, tā sakot, par ļoti pirmais elements no saraksta. Tātad, ja mana labā roka šeit ir PTR es esmu norāda uz vienu un to pašu, kas pirmo reizi ir vērsta uz. Tāpēc tagad atkal kodu, kas notiek tālāk - tas ir kopīgs paradigma, kad atkārtojot pār struktūru, piemēram, saistīts saraksts. Es esmu gatavojas veikt šādas darbības, kamēr rādītājs nav vienāds ar null Tāpēc, kamēr mans pirksts nav vērsta uz kādu null vērtība, ja rādītājs bultiņa n ir vienāds ar n. Mēs ievērosiet, ka, pirmkārt, n ir tas, ko lietotājs drukāti uz GetInts zvanu šeit. Un rādītājs arrow n nozīmē ko? Nu, ja mēs ejam atpakaļ uz attēlu šeit, ja man ir pirkstu norādot uz ka pirmais mezgls, kurā deviņi, to arrow būtībā nozīmē iet, ka mezglu un paķert vērtību atrašanās n, Šajā gadījumā, datu lauks sauc n. Kā malā - un mēs redzējām šo pāris nedēļas atpakaļ, kad kāds jautāja - Šī sintakse ir jauns, bet tas nav dod mums pilnvaras, kas mums nebija jau ir. Kāda bija šī frāze līdzvērtīgs izmantojot dot nošu un zvaigžņu pāris nedēļas atpakaļ, kad mēs mizoti atpakaļ šis slānis mazliet priekšlaicīgi? STUDENTU: [nedzirdama]. SPEAKER 1: Tieši tā, tas bija zvaigzne, un tad tas bija star dot n, ar iekavas šeit, kas izskatās, godīgi sakot, es domāju, ka daudz vairāk noslēpumains, lai lasītu. Bet zvaigzne rādītājs, kā vienmēr, nozīmē iet uz turieni. Un, kad jūs esat tur, kādi dati lauka jūs vēlaties piekļūt? Nu jūs izmantojat dot apzīmējumu, lai piekļūtu structs datu lauks, un es īpaši vēlas n. Atklāti sakot, es teiktu, tas ir tikai grūtāk lasīt. Tas ir grūtāk atcerēties, kur Vai iekavas iet, zvaigzne, un visu to. Tātad pasaule pieņēma dažus sintaktisko cukurs, lai runāt. Tikai sexy veids, kā pateikt, tas ir ekvivalents, un iespējams, vairāk intuitīvi. Ja rādītājs ir patiešām rādītājs, arrow notācija nozīmē iet tur un atrast Šajā gadījumā lauks sauc n. Tātad, ja man šķiet, pamanīt to, ko es daru. Es vienkārši izdrukāt, es atklāju procentiem I, tapām vērtību šajā int. Es aicinu gulēt vienu sekundi tikai natūrā gada pauzes lietas uz ekrāna, lai dod lietotājam otrs, lai absorbētu kas tikko notika. Un tad es pārkāpšu. Pretējā gadījumā, ko man darīt? Es atjaunināt rādītāju uz vienlīdzīgu rādītāju bultiņas blakus. Tik vienkārši, lai būtu skaidrs, tas nozīmē iet tur, izmantojot manu old-school notācija. Tātad tas nozīmē tikai doties uz whatever jūs norādot uz, kas ir ļoti Pirmā lieta ir tā, es esmu norādot uz struktūrai ar deviņiem tajā. Tāpēc es esmu gājusi tur. Un tad dot pieraksts nozīmē, saņemt vērtību nākamo. Bet vērtība, pat ja tas ir sastādīts kā šaurs, ir tikai skaitlis. Tas ir ciparu adrese. Tāpēc šī līnija kods, vai rakstīts, piemēram, tas, vairāk mistisks veidā, vai, piemēram, tas, nedaudz intuitīvā veidā, vienkārši nozīmē pārvietot manu roku no pirmā mezgla uz nākamo, un pēc tam blakus viens, un pēc tam Nākamais vienu, un tā tālāk. Tāpēc mēs ne aiztures par otru implementācijas ievietot un dzēst un šķērsošana, pirmais divi no , kas ir diezgan iesaistīti. Un es domāju, ka tas ir diezgan viegli nokļūt zaudētas, kad to dara mutiski. Bet ko mēs varam darīt, šeit ir mēģināt noteikt, kā vislabāk to darīt vizuāli. Tā kā es ierosinu, ka, ja mēs vēlaties ievietot elementus šajā esošais saraksts, kurā ir pieci elementi - 9, 17, 22, 26, 33 un - ja man bija gatavojas, lai īstenotu šo kods, man ir nepieciešams apsvērt, kā iet par to izdarīt. Un es ierosinu veikt bērnu pasākumus , saskaņā ar kuru, šajā gadījumā es domāju, kas ir iespējamos scenārijus, kas mums varētu rasties kopumā? Īstenojot ieliktni, lai saistītu sarakstā, tas vienkārši notiek, ir Konkrēts piemērs piecu izmēru. Nu, ja jūs vēlaties, lai ievietotu numuru, gribētu teikt, ka numur viens, un uzturot sakārtoti secībā, kur acīmredzot nav numur viens ir nepieciešams, lai iet šajā konkrētajā piemērā? Tāpat kā gada sākumā. Bet kas ir interesanti ir tas, ka Ja vēlaties ievietot vienu uz to sarakstā, ko īpaša rādītājs vajadzībām jāatjaunina acīmredzami? Pirmais. Tāpēc es teiktu, šis ir pirmais gadījums ka mēs varētu vēlēties apsvērt, scenārijs ietver ievietojot tajā sākums sarakstā. Let 's nošķīt varbūt tik viegli vai pat vieglāka gadījumā, relatīvi runājot. Pieņemsim, ka es gribu, lai ievietotu ir sakārtoti secībā 35 numuru. Tas, protams, pieder tur. Tātad, kādi rādītājs acīmredzot gatavojas ir jāatjaunina šajā scenārijā? 34 ir rādītājs kļūst ne null bet adrese struktūrai , kas satur skaitli 35. Tātad, tas ir gadījums divi. Tāpēc jau es esmu veida quantizing cik daudz darba, man ir jādara šeit. Un, visbeidzot, skaidrs vidū lieta ir protams, pa vidu, ja es gribu ievietot kaut ko līdzīgu 23 teiksim, kas iet starp 23 un 26, bet Tagad lietas iegūt nedaudz vairāk iesaistīti, jo to, ko norādes ir jāmaina? Tātad 22 acīmredzot ir jāmaina tāpēc, ka viņš nevar norādīt uz 26 vairs. Viņam vajag, lai norādītu uz jaunu mezglu, kas Es ņemšu, lai sadalītu pa tālruni malloc vai kādu līdzvērtīgu. Bet tad es arī nepieciešams, ka jaunu mezglu, 23 Šajā gadījumā, lai tās rādītājs norādot uz kuriem? 26. Un tur būs Lai darbību šeit. Jo ja es to muļķīgi, un es , piemēram, sākuma sākumā sarakstu, un mans mērķis ir, lai ievietotu 23. Un es varētu pārbaudīt, vai tas pieder Šeit, netālu no deviņiem? Nē. Vai tas pieder šeit, pie 17? Nē. Vai tas pieder šeit, pie 22? Jā. Tagad, ja es esmu muļķīgi šeit, un ne domāšana tas cauri, es varētu piešķirt savu jauno mezglu 23. Es varētu atjaunināt rādītāju no mezglu sauc 22, norādot tas pie jaunu mezglu. Un tad ko man ir, lai atjauninātu jaunā mezgla rādītājs būt? STUDENTU: [nedzirdama]. SPEAKER 1: Tieši tā. Norādot uz 26. Bet, dammit, ja man nav jau atjaunināt 22 ir rādītājs norādīt uz šo puisis, un tagad man ir bāreņi, atpūtas saraksta, lai runāt. Tātad, lai darbību šeit būs svarīgi. Lai to izdarītu es varētu nozagt, teiksim, seši brīvprātīgie. Un pieņemsim redzēt, ja mēs nevaram izdarīt vizuāli nevis koda gudrs. Un mums ir daži jauki stress bumbas jums šodien. OK, kā apmēram viens, divi, jo atpakaļ - uz beigām tur. trīs, četri, jums abiem puiši uz gada beigām. Un pieciem, sešiem. Pārliecināts. Piecus un sešus. Visas tiesības, un mēs nāksim jums puiši nākamreiz. Labi, come on augšu. Labi, jo jūs esat šeit pirmo reizi, Jūs vēlētos, lai būtu viens neveikli Google Glass šeit? Labi, jā, OK, stikla, ierakstītu video. Labi, jūs esat labi iet. Visas tiesības, tādēļ, ja jūs guys var nākt pāri šeit, es esmu gatava iepriekš daži skaitļi. Visas tiesības, nāk vairāk nekā šeit. Un kāpēc nav jums iet mazliet turklāt šādā veidā. Un redzēsim, kāds ir tavs vārds, ar Google Glass? STUDENTU: Ben. SPEAKER 1: Ben? Labi, Ben, jums būs, pirmkārt, burtiski. Tāpēc mēs esam gatavojas nosūtīt jums līdz beigām posmā. Visas tiesības, un jūsu vārds? STUDENTU: Jason. 1 SPEAKER: Jason, OK jūs būtu numur deviņi. Tātad, ja jūs vēlaties sekot Ben, ka veidā. STUDENTU: Jill. SPEAKER 1: Jill, jūs esat būs 17, kas, ja es gribētu darīt šo vairāk gudri, es būtu sākās pie otrā galā. Jums iet šo ceļu. 22. Un jūs esat? STUDENTU: Mary. SPEAKER 1: Marija, jums būs 22. Un jūsu vārds ir? STUDENTU: Chris. 1 SPEAKER: Chris, jums būs 26. Un tad visbeidzot. STUDENTU: Diana. 1 SPEAKER: Diana, jums būs 34. Tātad jums nāk vairāk nekā šeit. Visas tiesības, tik perfekts sakārtoti pasūtīt jau. Un iesim uz priekšu un darīt to lai mēs varētu tiešām - Ben jūs vienkārši veida meklē ārā nekur tur. Labi, tāpēc iesim uz priekšu un attēlot šo izmantojot rokas, līdzīgi man bija, tieši tā, kas notiek. Tik iet uz priekšu un dot sev pēdu vai starp sevi divi. Un iet uz priekšu, un norādīt ar vienu roku Kurš jums būtu vērsti pamatojoties uz šo. Un, ja jūs esat null tikai punkts taisni uz leju uz grīdas. Labi, tik labi. Tāpēc tagad mums ir saistīts saraksts, un ļaujiet man ierosina, ka es spēlēt lomu PTR, tāpēc es ne apnikt veicot šo apkārt. Un tad - kāds stulbi konvencija - Jūs varat zvanīt šo kaut ko vēlaties - priekšgājējs rādītājs, ieteik rādītājs - tas ir tikai segvārds mums padevās mūsu parauga kodu uz manu kreiso roku. No otras puses, kas būs tur līdzi, kas ir kas pēc scenārijus. Tātad pieņemsim, ka, pirmkārt, es vēlos nošķīt ka pirmais piemērs ievietojot, teiksim 20, uz sarakstu. Tāpēc es esmu gatavojas ir nepieciešams kāds, lai iemieso numuru 20 uz mums. Tāpēc man ir nepieciešams malloc kādam no auditorijas. Nāciet uz augšu. Kāds ir Jūsu vārds? STUDENTU: Brian. SPEAKER 1: Brian, labi, lai jūs ir mezgls, kas satur 20. Visas tiesības, nāk vairāk nekā šeit. Un, protams, ja tas Brian pieder? Tātad, pa vidu - faktiski, pagaidiet minūti. Mēs darām to iziet no ierindas. Mēs esam padarot šo daudz grūtāk , nekā tai vajadzētu būt sākumā. Labi, mēs ejam uz brīvu Brian un realloc Brian kā pieci. Labi, tāpēc tagad mēs vēlamies, lai ievietotu Brian kā pieci. Lai nāk vairāk nekā šeit pie Ben tikai brīdi. Un jūs varat iespējams pateikt ja šis stāsts turpinās. Bet pieņemsim rūpīgi apdomāt rīkojums darbību. Un tas ir tieši tas vizuāli kas notiek, lai rindā ar šo parauga kodu. Tātad, šeit es esmu PTR norādot sākotnēji nav Ben, per se, bet neatkarīgi augstu viņš ir, kas šajā gadījumā ir - kāda ir Jūsu vārds atkal? STUDENTU: Jason. 1 SPEAKER: Jason, lai gan Ben, un es esam norādot uz Jason šajā brīdī. Tāpēc tagad man ir, lai noteiktu, ja nav Brian pieder? Tātad vienīgā lieta, man ir pieeja tagad ir viņa n datu postenis. Tāpēc es esmu gatavojas, lai pārbaudītu, ir Brian mazāk nekā Jason? Atbilde ir taisnība. Tā, kādi tagad ir nepieciešams notikt, pareizā secībā? Man vajag, lai atjauninātu cik norādes kopumā šajā stāstā? Kur mana roka joprojām norādot uz Jason, un jūsu rokas - ja vēlaties nodot savu roku, piemēram, sava veida, es nezinu, jautājuma zīmi. Labi, labi. Labi, tāpēc jums ir daži kandidāti. Nu Ben, vai es, vai Brian vai Jason vai ikviens cits, kas norādes nepieciešams mainīt? Cik kopumā? Labi, tāpēc divi. Mans rādītājs nav īsti jautājums vairs jo es esmu tikai īslaicīga. Tātad, tas ir šie divi puiši, iespējams, gan Ben un Brian. Tātad, ļaujiet man ieteikt, ka mēs atjaunināt Ben, jo viņš ir pirmais. Pirmais elements no šī saraksta tagad būs Brian. Tātad Ben punkts, Brian. Labi, tagad ko? Kurš izpaužas norādīja kam? STUDENTU: [nedzirdama]. SPEAKER 1: Labi, tāpēc Brian ir norādīt uz Jason. Bet es esmu zaudējis dziesmu no šīs rādītājs? Vai es zinu, kur Jason ir? STUDENTU: [nedzirdama]. SPEAKER 1: man, jo es esmu pagaidu rādītājs. Un, iespējams, man nav mainījies norādīt uz jaunu mezglu. Tātad, mēs varam vienkārši ir Brian punkts pie tam, kurš es esmu norādot uz. Un mēs esam darīts. Tātad, viens gadījums, ievietošanas pie sākumā sarakstā. Tur bija divi galvenie pasākumi. Viens, mums ir, lai atjauninātu ben, un pēc tam mums ir arī atjaunināt Brian. Un tad man nav jāuztraucas traipsing visā pārējā sarakstā, jo mēs jau atrasts viņa vieta, jo viņš piederēja pa kreisi no pirmā elementa. Labi, tāpēc diezgan vienkārši. Faktiski, uzskata, tāpat kā mēs esam gandrīz padarot šo pārāk sarežģīta. Tātad, pieņemsim tagad raut pie beigām no saraksta, un redzēt, kur sarežģītība sākas. Tātad, ja tagad, es alloc no auditorijas. Ikviens vēlas spēlēt 55? Labi, es redzēju savu roku pirmās. Nāciet uz augšu. Jā. Kāds ir Jūsu vārds? STUDENTU: [nedzirdama]. SPEAKER 1: Habata. Labi, nāc uz augšu. Jūs būsiet numuru 55. Tātad, jūs, protams, pieder beigās saraksta. Tātad, pieņemsim atkārtot simulācija ar mani ir PTR tikai brīdi. Tāpēc es esmu pirmo reizi gatavojas norādīt uz neatkarīgi Ben ir vērsti. Mēs abi norādot tagad Brian. Tātad, 55 ir ne mazāks par pieci. Tāpēc es esmu gatavojas atjaunināt sevi ar norādot uz Brian nākamais rādītājs, kurš Tagad, protams, Jason. 55 ir ne mazāks par deviņiem, tā Es esmu gatavojas atjaunināt PTR. Es esmu gatavojas atjaunināt PTR. Es esmu gatavojas atjaunināt PTR Es gatavojas atjaunināt PTR. Un es esmu gatavojas - hmm, kas ir Jūsu vārds atkal? STUDENTU: Diana. SPEAKER 1: Diana ir vērsta, protams, uz nulli ar savu kreiso roku. Tātad, ja nav Habata faktiski pieder skaidri? Pa kreisi, šeit. Tātad, kā es varu zināt likt viņai šeit Es domāju, ka es esmu ieskrūvē augšu. Jo, ko PTR mākslas šajā brīdī? Null. Tātad, lai gan vizuāli, mēs varam protams, redzēt visus šos puiši šeit uz skatuves. Man nav tur līdzi iepriekšējo persona sarakstā. Man nav pirkstu norādot,, Šajā gadījumā, mezglu skaits 34. Tā ļauj faktiski sākt šo pāri. Tāpēc tagad es tiešām ir nepieciešams Otrais lokālais mainīgais. Un tas ir tas, ko jūs redzēsiet faktiskais paraugu C kodu, kur, kā man iet, kad es mainīšu labo roku norādīt Jason, tādējādi atstājot Brian aiz muguras, es labāk sākt, izmantojot manu kreiso roku atjaunināt kur es bija, tā, ka kā es iet caur šo sarakstu - vairāk neveikli nekā es paredzēts tagad šeit vizuāli - Es esmu gatavojas nokļūt saraksta beigās. Šī roka ir vēl null, kas ir diezgan bezjēdzīgi, izņemot, lai norādītu Es skaidri beigās no saraksta, bet tagad vismaz man ir šī priekštecis rādītājs norādot šeit, tāpēc Tagad to, kas rokās un kas norādes nepieciešams jāatjauno? Kuru roku tu gribi pārveidot pirmo? STUDENTU: [nedzirdama]. SPEAKER 1: Labi, tāpēc Diānas. Ja jūs vēlaties norādīt Diānas kreisi rādītājs ir? Pie 55, iespējams, tā ka mēs esam ievietota tur. Un kur ir 55 rādītājs doties? Uz leju, kas pārstāv null. Un manas rokas, šajā brīdī, nav nozīmes, jo tie bija vienkārši pagaidu mainīgie. Tāpēc tagad mēs esam darīts. Tātad papildu sarežģījumus tur - un tas nav tik grūti īstenot, bet mums ir nepieciešama sekundāra mainīgo, lai padarītu pārliecinieties, ka pirms es pārvietot manu tiesības No otras puses, es atjaunināt vērtību manu kreiso No otras puses, Pred rādītājs šajā gadījumā, tā ka man ir trailing rādītājs izsekot, kur es biju. Tagad kā malā, ja jūs domājat šo cauri, tas uzskata, tāpat kā tas ir mazliet kaitinošas ir, lai saglabātu izsekot šīs kreisās rokas. Kas būtu cits risinājums Šīs problēmas ir bijušas? Ja jums pārveidot datus struktūru mēs runājam izmantojot tieši tagad? Ja tas tikai veida jūtas nedaudz kaitinošas ir, piemēram, divas norādes iet caur sarakstu, kurš gan cits varētu ir, ideālā pasaulē, uztur informāciju, kas mums ir vajadzīgs? Yeah? STUDENTU: [nedzirdama]. SPEAKER 1: Tieši tā. Labi, lai tur tiešām interesants dīgļi ideja. Un šī ideja par iepriekšējo rādītāju, norādot iepriekšējā elementa. Ko darīt, ja es tikai iemieso ka iekšpusē no saraksta pati? Un tas būs grūti iztēloties tas bez visiem papīra nokrīt uz grīdas. Bet pieņemsim, ka šie puiši izmanto gan viņu rokās, lai būtu iepriekšējo rādītājs, un blakus rādītājs, tādējādi īstenot to, ko mēs saucam divtik saistīts saraksts. Tas ļauj man, lai sakārtotu ar attītu atpakaļ, daudz vieglāk bez manis, programmētājs, kam, lai saglabātu izsekot manuāli - patiesi manuāli - , kur es biju agrāk sarakstā. Tāpēc mēs nevarēsim darīt. Mēs turpināsim to vienkārši tāpēc, ka tas ir nāks par cenu, divreiz daudz vietas, lai norādes, Ja jūs vēlaties otru. Bet tas ir patiešām kopēja datu struktūra pazīstams kā divkārt saistīts saraksts. Darīsim galīgo piemēru šeit un nodot šie puiši, kas to postu. Tātad 20 malloc. Nāc uz augšu no eju tur. Labi, kāds ir tavs vārds? STUDENTU: [nedzirdama]. SPEAKER 1: Atvaino? STUDENTU: [nedzirdama]. SPEAKER 1: Demeron? OK, come on augšu. Tev ir 20. Jūs, protams, gatavojas pieder starp 17 un 22. Tātad, ļaujiet man mācīties, mana mācība. Es esmu gatavojas sākt rādītāju norādot uz Brian. Un es esmu nāksies manu kreiso roku tikai atjaunināt ar Brian, kā es pārietu uz Jason, pārbaude nav 20 mazāk nekā deviņi? Nē. Ir par 20 mazāk nekā 17? Nē. Ir par 20 mazāk nekā 22? Jā. Tātad, ko norādes vai rokas jāmaina kur viņi norāda tagad? Tātad, mēs varam darīt 17 norāda uz 20. Tātad, tas ir jauki. Kur mēs vēlamies norādīt Jūsu rādītājs tagad? Gada 22. Un mēs zinām, kur 22 ir, atkal pateicoties uz manu pagaidu rādītājs. Tāpēc mēs esam OK tur. Tāpēc, ka šīs pagaidu uzglabāšanas Es esmu tur līdzi, kur visi ir. Un tagad jūs varat vizuāli iedziļināties, kur jums pieder, un tagad mums ir 1, 2, 3, 4, 5, 6, 7, 8, 9 stresa bumbas, un kārtu aplausi par šie puiši, ja mēs varētu. Labi darīts. [Aplausi] SPEAKER 1: Nu labi. Un jūs varat saglabāt gabalus papīra, kā mementos. Labi, tāpēc, ticiet man, tas ir daudz vieglāk staigāt cauri, ka ar cilvēkiem, nekā tas ir ar faktisko kodu. Bet ko jūs atradīsiet tikai brīdi Tagad ir tā, ka tas pats - ak, paldies. Paldies - ir tas, ka jūs atradīsiet, ka tos pašus datus struktūru, saistīts saraksts, faktiski var tikt izmantoti kā celtniecības bloku pat vairāk sarežģītas datu struktūras. Un realizēt pārāk tēma šeit ir tas, ka mēs esam absolūti ieviesa vairāk sarežģītība vērā īstenošanu Šī algoritma. Ievietošanas, un, ja mēs devāmies caur to, dzēšanu un meklēšana, ir nedaudz sarežģītāka, nekā tas bija ar masīvu. Bet mēs gūstam zināmu dinamiku. Mēs saņemam adaptīvā datu struktūra. Bet atkal, mēs maksājam cenu ar dažu papildu sarežģījumus, gan to īsteno. Un mēs esam atteikušies brīva piekļuve. Un, ja godīgi, tur nav kādu jauku tīrīt slaidu es varu dot jums, ka saka, ka šeit ir iemesls, kāpēc saistīts saraksts ir labāka nekā masīva. Un atstāt to, ka. Tāpēc, ka tēma atkārtošanos tagad, pat jo vairāk tāpēc, ka tuvākajās nedēļās, ir ka tur ne vienmēr Pareizā atbilde. Tas ir iemesls, kāpēc mums ir atsevišķas ass no dizaina problēmu kopas. Tas būs ļoti konteksta jutīga vai jūs vēlaties izmantot šos datus struktūra vai ka viens, un tas tiks atkarīgi no faktiem, kas jums attiecībā resursu un sarežģītību. Bet ļaujiet man ieteikt, ka ideāls dati struktūru, Svētais Grāls, būtu kaut kas ir nemainīgs laiks, neatkarīgi no tā, cik daudz sīkumi tā iekšpusē, tas nebūtu pārsteidzoši, ja datu struktūra atgriezās atbildes pastāvīgu laiku. Jā. Šis vārds ir jūsu milzīgs vārdnīcā. Vai nē, šis vārds nav. Vai jebkura šāda problēma pastāv. Nu pieņemsim redzēt, ja mēs nevaram vismaz spert soli pretim kas. Ļaujiet man piedāvāt jaunu datu struktūra, kas var izmantot dažādas lietas, šajā gadījumā sauc hash tabulu. Un tāpēc mēs esam patiesībā atpakaļ uz glancing pie masīva, šajā gadījumā, un nedaudz patvaļīgi, es esmu sastādīts šis hash tabulu kā masīva ar veida divdimensiju masīvs - vai drīzāk tā ir attēlota šeit kā divām trešdaļām balsu dimensiju masīvs - bet tas ir tikai masīvs 26 izmēra, piemēram, ka, ja mēs zvaniet masīva galda, galda kronšteins nulle ir taisnstūris augšpusē. Galda skava 25 ir taisnstūris apakšā. Un tas ir, kā es varētu vilkt datu struktūru, kurā es gribu saglabāt cilvēku vārdus. Tātad, piemēram, un es ne izdarīt viss šeit uz virs galvas, ja es bija šis masīvs, ko es esmu tagad gatavojas zvanīt hash tabulu, un tas ir atkal vieta nulle. Tas šeit ir vieta viena, un tā tālāk. Man apgalvo, ka es vēlos, lai izmantotu šos datus struktūru, lai nodrošinātu diskusiju, lai saglabātu cilvēku vārdus, Alise un Bobs un Čārlijs un citi šādi nosaukumi. Tāpēc domāju, ka par to tagad, jo pirmsākumiem , teiksim, vārdnīcu ar daudz vārdiem. Tie gadās būt vārdi mūsu piemērs šeit. Un tas ir pārāk piederīgs, iespējams, līdz īstenojot pareizrakstības pārbaudītājs, kā mēs var būt par problēmu, kas seši. Tātad, ja mums ir masīva kopējo platību 26 tā, ka tas ir 25 vieta apakšā, un es pretenziju, ka Alise pirmais vārds vārdnīcā vārdi, kas es gribu ievietot RAM, šajā datu struktūru, kur ir instinkti stāsta, ka Alises nosaukums ir jāiet šajā masīvā? Mums ir 26 iespējas. Kur mēs gribam likt viņai? Mēs vēlamies viņai nulles grupā, vai ne? Par Alice, sauksim šo nulli. Un B būs viens, un C būs divi. Tāpēc mēs esam gatavojas rakstīt Alises vārds šeit. Ja mēs pēc tam ievietojiet Bob, viņa Vārds dosies šeit. Čārlija iet šeit. Un tā tālāk uz leju pa Šī datu struktūra. Tas ir brīnišķīgs datu struktūra. Kāpēc? Nu, kas ir darbības laiks ievietojot cilvēka vārdu uz to Datu struktūra tieši tagad? Ņemot vērā, ka šī tabula tiek īstenota, patiesi, kā masīvu. Nu tas ir nemainīgs laiks. Tas ir rīkojums par vienu. Kāpēc? Nu, kā jūs noteikt, kur Alice pieder? Paskatās, kas burtu viņas vārdu? Pirmais. Un jūs varat tur nokļūt, ja tas ir string, , tikai aplūkojot virkni kronšteins nulle. Tātad 0. raksturu virkni. Tas ir viegli. Mēs did, ka kriptogrāfiskā sadalījumu nedēļas atpakaļ. Un tad, kad jūs zināt, ka Alises burts ir kapitāls, mēs varam atņemt off 65 vai kapitāla A pati, kas dod mums nulli. Tātad, mēs tagad zinām, ka Alise pieder nulles atrašanās vietu. Un, ņemot vērā rādītāju uz šiem datiem struktūru, dažu šķirot, cik ilgi paies man atrast vietu nullei masīvā? Tikai viens solis, labi tas ir pastāvīgs laiks jo brīvpieejas mums Ierosinātais bija iezīme masīva. Tātad īsumā, norādītas, ko indekss no Alises nosaukums ir, kas ir, jo Šajā gadījumā ir, vai pieņemsim tikai atrisināt ka uz nulli, kur B ir viens un C ir divi, norādītas ka no ir nemainīgs laika. Man vienkārši ir jāskatās uz savu pirmo burtu, norādītas, kur nulle ir masīvs ir arī pastāvīgs laiks. Tātad, tehniski tas ir tāpat kā divos posmos tagad. Bet tas joprojām ir nemainīgs. Tātad, mēs to saucam par lielu O viens, tāpēc mēs esam ievietota Alice šajā tabulā pastāvīgu laiku. Bet, protams, es esmu to naivs šeit, vai ne? Ko darīt, ja tur klasē Ārons? Vai Alicia? Vai kādi citi nosaukumi, kas sākas ar A. Uz kurieni mēs ejam, lai šī persona, vai ne? Es domāju, tagad tur ir tikai trīs cilvēki, uz galda, tāpēc varbūt mēs vajadzētu likt Āronu atrašanās vietā nulle viens divi trīs. Labi, es varētu likt šeit. Bet tad, ja mēs mēģinātu ievietot Dāvidu vērā šis saraksts, kur tas Dāvids iet? Tagad mūsu sistēma sāk sadalīšana uz leju, pa labi? Jo tagad Deivids nonāks šeit ja Aaron ir faktiski šeit. Un tāpēc tagad šī ideja, kam tīrs datu struktūra, kas dod mums konstantā ievietošanas vairs nav pastāvīgu laiku, jo man ir pārbauda, ​​ak, Damnit, kādam jau pie Alises vietā. Ļaujiet man zonde pārējo šo datu struktūru, meklē vietas likt kāds, piemēram, Ārona vārdu. Un tā, ka arī sāk veikt lineāru laiku. Turklāt, ja jūs tagad vēlaties, lai atrastu Aaron šajā datu struktūra, un jūs pārbaude, un Ārona vārds nav šeit. Vislabāk, ja jūs vienkārši pateikt Ārona ne ar datu struktūru. Bet, ja jūs sākat padarot telpu Aaron kur būtu bijis D vai E, jūs, sliktākajā gadījumā, ir jāpārbauda visa datu struktūra, kas tādā gadījumā tas tiek nodots uz kaut ko lineāra lielumu tabulā. Tātad viss, labi, es jums salabot. Problēma šeit ir tā, ka man bija 26 elementi šajā masīvā. Ļaujiet man to mainīt. Whoops. Ļaujiet man mainīt tā, lai drīzāk labklājību kopumā 26 izmērs, paziņojums dibenu indekss mainīsies līdz n mīnusa 1. Ja 26 ir acīmredzami pārāk mazs cilvēkam " vārdus, jo tur ir tūkstošiem nosaukumi pasaulē, pieņemsim tikai darīt ar 100 vai 1000 vai 10000. Pieņemsim tikai piešķirt daudz vairāk vietas. Labi, ka ne vienmēr samazinās varbūtība, ka mums nebūs divi cilvēki ar nosaukumiem, kas sākas ar A, un tā, jūs gatavojas, lai mēģinātu likt nosaukumi atrašanās vietā nulles joprojām. Viņi joprojām turpinās, lai saduras, kas nozīmē, ka mums joprojām ir nepieciešams risinājums likt Alise un Ārons un Alicia un citi nosaukumi, kas sākas ar A citur. Bet cik daudz problēmu tas ir? Kāda ir varbūtība, ka jūs ir sadursmju ar datu struktūra, kā šis? Nu, ļaujiet man - mēs atgriezīsimies uz šo jautājumu šeit. Un skatīties, kā mēs varētu atrisināt tā pirmo reizi. Ļaujiet man uzvilkt šo priekšlikumu šeit. Ko mēs tikko aprakstīts ir algoritms, heiristisko sauc par lineāru zondēšana saskaņā ar kuru, ja esat mēģinājuši ievietot kaut kas šeit šiem datiem struktūru, ko sauc hash galds, un tur nav vietas tur, jūs patiesi zonde datu struktūra pārbaudot, tas ir pieejams? Vai tas ir pieejams tas ir pieejams? Vai tas ir pieejams? Un, kad tas beidzot ir, jūs ievietojiet nosaukt, ka jūs sākotnēji paredzēts citur šajā vietā. Bet sliktākajā gadījumā, tikai vieta varētu būt ļoti apakšā no datu struktūra, pašās beigās no masīva. Tātad lineāra zondēšana, sliktākajā gadījumā, devolves par lineāru algoritmu, kurā Ārons, ja viņš notiek, ir ievietota pagājušajā Šajā datu struktūra, viņš varētu saduras ar šo pirmo vietu, bet tad galu ar sliktu luck pašās beigās. Tātad tas nav konstants laiks Svētais Grāls mums. Šī pieeja ievietojot elementiem iekļaut datu struktūra sauc hash tabulā nav, šķiet, ir nemainīga laiks vismaz ne vispārējā gadījumā. Tas var pāriet uz kaut ko lineāro. Tātad, ko tad, ja mēs atrisināt sadursmes nedaudz savādāk? Tātad, šeit ir daudz sarežģītākas pieeja, kas ir vēl sauc hash tabulu. Un hash, kā malā, ko Es domāju, ir rādītājs, ka Es minēju iepriekš. Lai hash kaut ko var būt domā kā darbības vārds. Tātad, ja jūs Hash Alise ir vārds, hash funkciju, tā sakot, vajadzētu atgriezties numuru. Šajā gadījumā ir nulle, ja viņa pieder pie vieta nulle, viens, ja viņa pieder pie vieta viena, un tā tālāk. Tātad mans Hash funkcija līdz šim ir bijis super vienkārši, tikai apskatot Pirmais burts ir kāds vārda. Bet hash funkcija ir pieņemts, input daži gabals no datiem, string, int, neatkarīgi. Un tas atklepo tipiski numuru. Un šis skaits ir, ja, ka dati elements pieder ar datu struktūru pazīstams šeit kā hash tabulu. Tik vienkārši intuitīvi, tas ir nedaudz citā kontekstā. Tas patiesībā ir, atsaucoties uz piemēru iesaistot dzimšanas dienas, ja tur varētu būt tikpat daudz kā 31 dienas mēnesī. Bet ko šī persona nolemj do, kas sadursmes gadījumā? Konteksts tagad ir, nevis sadursme nosaukumi, bet sadursme dzimšanas dienas, ja divi cilvēki ir tāda pati dzimšanas dienu 2 oktobris, piemēram. STUDENTU: [nedzirdama]. SPEAKER 1: Jā, tāpēc šeit mēs esam pārplūšanu saistītas sarakstiem. Tātad, tas izskatās nedaudz savādāk nekā mēs izvilka to agrāk. Bet mēs, šķiet, ir masīvs kreisajā pusē. Tas ir viens rādītājs, ne īpašs iemesls. Bet tas joprojām ir masīvs. Tas ir masīvs norādes. Un katrs no šiem elementiem, katrs no šīs aprindas vai slīpsvītras - slash pārstāvot null - katram no šiem norādes ir acīmredzami vērsta uz kādi datu struktūra? Saistīts saraksts. Tāpēc tagad mums ir iespēja grūti kodu mūsu programmā izmērs no tabulā. Šajā gadījumā, mēs zinām, ka nekad vairāk nekā 31 dienas mēnesī. Tik grūti kodēšanas vērtību, piemēram, 31 ir saprātīgi šajā kontekstā. Saistībā ar nosaukumiem, grūti kodēšana 26 nav nesaprātīgi tas Tautas nosaukumi sākas tikai ar, piemēram, alfabēts iesaistot caur Z. Mēs varam piestūķēt tos visus šos datus struktūra tik ilgi, kamēr, kad mēs nokļūt sadursme, mēs nelieciet vārdus šeit, tā vietā mēs domājam par šīm šūnām nevis kā stīgas paši, bet kā norādes uz to, piemēram, Alice. Un tad Alice var būt vēl viens rādītājs uz citu nosaukumu, sākot ar A. Un Bobs faktiski iet vairāk nekā šeit. Un, ja tur ir cits nosaukums sākas ar B, viņš nonāk vairāk nekā šeit. Un tā katru šo elementu galda divas, ja mēs paredzēti šajā nedaudz vairāk gudri - come on - ja mēs izstrādājām šo nedaudz vairāk gudri, tagad kļūst par adaptīvu datu struktūra, kurā nav grūti ierobežot no tā, cik daudz elementi var ievietot par to, jo, ja jums ir sadursmes, tas ir jauki. Vienkārši iet uz priekšu un pievienot to tas, ko mēs redzējām mazliet atpakaļ bija pazīstams kā saistītu sarakstu. Nu pieņemsim pauzi tikai brīdi. Kas ir no sadursmes varbūtība pirmajā vietā? Labi, varbūt es esmu vairāk domāju, varbūt Es esmu vairāk nekā inženierzinātnes šo problēmu, tāpēc, ka jūs zināt, ko? Jā, es varētu nākt klajā ar patvaļīgu piemēri off augšpusē manu galvu, piemēram, Allison un Ārons, bet patiesībā, dota vienota sadale ieejas, ka ir daži izlases iespraudumiem uz datu struktūru, kas patiešām ir varbūtība sadursmes? Nu izrādās, tas ir faktiski super augsts. Ļaujiet man vispārināt šo problēma ir kā šī. Tātad telpā ar n CS50 studenti, kas ir varbūtība, ka vismaz divi studenti telpā ir pašas dzimšanas diena? Tātad tur ir kas. daži Hund - 200, 300 cilvēki šeit un vairākām simti cilvēku mājās šodien. Tātad, ja jums gribēju jautāt sev, kas ir varbūtība divi cilvēki šajā telpā, kam ir tāda pati dzimšanas, mēs varam skaitlis šo out. Un es varu pieprasīt patiesībā ir divi cilvēki ar tādu pašu dzimšanas dienā. Piemēram, vai kāds ir dzimšanas diena šodien? Vakar? Rīt? Labi, lai tā uzskata, tāpat kā es esmu gatavojas lai to darīt 363, vai arī tā vairāk reizes, lai tiešām noskaidrotu ja mums ir sadursmi. Vai mēs varētu vienkārši darīt matemātiski nevis tediously darot. Un ierosināt sekojošo. Tāpēc es ierosinu, ka mēs varētu modelēt varbūtība, ka diviem cilvēkiem, kam pats dzimšanas diena kā varbūtību 1 mīnus varbūtība, ka neviens, kam pats dzimšanas diena. Tātad, lai iegūtu šo, un tas ir tikai iedomātā veids, kā rakstot šo, lai pirmais cilvēks telpā, viņš vai viņa var būt jebkura no šīm iespējams dzimšanas dienas, pieņemot, 365 dienas gadā, ar atvainošanos personām ar februāris 29 dzimšanas dienu. Tātad, pirmais cilvēks šajā telpā ir bez maksas lai jebkuru skaitu dzimšanas dienas no 365 iespējām, lai mēs darīsim, ka 365 dalīts ar 365, , kas ir viens. Nākamajai personai telpā, ja mērķis ir, lai izvairītos no sadursmes, var tikai ir viņa vai viņas dzimšanas dienu par to, kā daudzi un dažādi iespējamie dienās? 364. Tātad otrais termins šajā izpausmes ir būtībā dara, ka math par mums atņemot off vienu iespējamo dienu. Un tad nākamajā dienā, nākamajā dienā, Otrā dienā uz leju, lai kopējā cilvēku telpā. Un, ja mēs pēc tam apsvērt, kādi tad ir varbūtība nav ikvienam, kam unikālas dzimšanas dienas, bet atkal 1 mīnus tas, ko mēs saņemam, ir izteiksme ka var ļoti fancifully izskatās šādi. Bet tas ir vairāk interesanti apskatīt vizuāli. Tas ir diagramma, kur uz x ass ir cilvēku skaits telpā, numurs dzimšanas dienas. Uz y-ass ir varbūtība no sadursmes, divi cilvēki kam ir tāda pati dzimšanas diena. Un no šīs līknes takeaway ir ka tiklīdz jums patīk 40 studenti, jūs pat pie 90% varbūtību combinatorically divu cilvēkiem vai vairāk, kam pats dzimšanas diena. Un, kad jums patīk 58 cilvēkiem, tas ir gandrīz 100% no iespēju divu cilvēki telpā nāksies pats dzimšanas diena, lai gan tur ir 365 vai 366 iespējamie kausi, un Tikai 58 cilvēki telpā. Vienkārši statistiski jūs varētu get sadursmes, kas īsā motivē šo diskusiju. Ka, pat ja mēs fancy šeit, un sākat ar šo ķēdes, mēs joprojām esam nāksies sadursmes. Tā, ka Rodas jautājums, kāda ir izmaksas, kā to ievietošanas un dzēšanas par datu struktūru, piemēram, tas? Nu ļaujiet man ieteikt - un ļaujiet man iet atpakaļ uz ekrāna vairāk šeit - ja mums ir n elementi sarakstā, tāpēc, ja mēs cenšamies, lai ievietotu n elementi, un mums ir cik kopā kausi? Teiksim 31 Kopā kausi gadījumā, dzimšanas dienas. Kāds ir maksimālais garums ir viena no šīs ķēdes, iespējami? Ja atkal tur ir 31 iespējas dzimšanas dienu, kas attiecīgajā mēnesī. Un mēs esam tikai salipšanu ikvienam - patiesībā tas ir muļķīgs piemērs. Darīsim 26 vietā. Tātad, ja tiešām ir cilvēki, kuru vārdi sākt ar līdz Z, tādējādi dodot mums 26 iespējas. Un mēs esam, izmantojot datu struktūra, piemēram, kuru mēs tikko redzējām, ar kuru mēs esam masīvu norādes, katrs no kuriem norāda uz saistītā sarakstā, ja to Pirmais saraksts ir visi ar nosaukumu Alice. Otrajā sarakstā ir katrs ar nosaukt sākot ar, sākot ar B, un tā tālāk. To, kas ir iespējams, garums no katras no šie saraksti, ja mēs pieņemam, skaistu tīru izplatīšana vārdu, izmantojot Z visā datu struktūru? Tur ir n cilvēki, datu struktūru dalīts ar 26, ja viņi labi sadalīts pa visu datu struktūra. Tā garums no katra no tām ķēdes ir n dalot ar 26. Bet Big O notācija, kas tas ir? Kas ir tas, ka tiešām? Tātad, tas ir tiešām tikai n, vai ne? Tāpēc, ka mēs esam teica agrāk, ka ugh jūs izdalot ar 26. Jā, patiesībā tas ir ātrāk. Bet teorētiski, tas nav būtiski viss, kas ātrāk. Tāpēc mums nav, šķiet, ir viss, kas daudz tuvāk šim Svētais Grāls. Faktiski, tas ir tikai lineārs laiks. Heck, šajā brīdī, kāpēc ne mēs tikai izmantot vienu milzīgu saistīts saraksts? Kāpēc ne mēs tikai izmantot viens milzīgs masīvs, lai saglabātu vārdus ikvienam istabā? Nu, tur vēl kaut kas pārliecinoši par hash tabulu? Vai ir vēl kaut kas pārliecinoši par datu struktūru ka izskatās šādi? Tas. STUDENTU: [nedzirdama]. SPEAKER 1: labi, un, ja tā ir tikai lineāra laiks algoritmu, un lineārā laika datu struktūra, kāpēc ne es tikai glabāt ikviena vārdu liels masīvs, vai arī lielā saistīts sarakstu? Un pārtraukt nākt klajā ar CS tik daudz grūtāk nekā tai vajadzētu būt? Kas ir pārliecinoši par to, pat lai gan es saskrāpēts to ārā? STUDENTU: [nedzirdama]. SPEAKER 1: Iespraudumi nav? Dārgi vairs. Tātad ievietošanas potenciāli varētu vēl ir nemainīgs laikā, pat tad, ja jūsu dati struktūra izskatās šādi, masīvs norādes, katrs no kuriem ir pavērsts potenciāli saistīts saraksts. Kā jūs varētu panākt pastāvīgu laiks ievietošanas nosaukumus? Stick to priekšā, vai ne? Ja mēs upurēt dizaina mērķi no agrāk, ja mēs vēlējāmies, lai saglabātu ikviena cilvēka vārdu, piemēram, sakārtoti, vai visu uz skatuves numuriem sakārtoti, pieņemsim, ka mums ir nešķiroti saistīts saraksts. Tas tikai izmaksas mums vienu vai divus soļus, piemēram, attiecībā uz Ben un Brian agrāk, lai ievietotu elements ir sākums sarakstā. Tātad, ja mums nav jārūpējas par šķirošanas visu no nosaukumiem, kas sākas ar vai visiem nosaukumi, kas sākas ar burtu B, mēs joprojām var panāktu pastāvīgu laiku ievietošanas. Tagad meklē up Alise vai Bobs vai jebkuru nosaukumu kopumā ir vēl kāda? Tas ir liels n O dalīts ar 26, jo Ideāls gadījums, kad visi ir vienādi izplatīt, ja tur ir tik daudz s kā tur ir z, kas, iespējams, ir nereāls. Bet tas joprojām ir lineāra. Bet šeit mēs nonākam atpakaļ uz punktu gada asimptotiskās notācijas pagaidām teorētiski taisnība. Bet reālajā pasaulē, ja man apgalvo, ka mana programma var darīt kaut 26 reizes ātrāk nekā jums, kuru programma jūs gatavojas vēlaties izmantot? Jūsu vai raktuves, kas ir 26 reizes ātrāks? Reāli, persona, kura ir 26 reizes ātrāk, pat tad, ja teorētiski mūsu algoritmi darbojas pats asimptotiskā darbības laiks. Ļaujiet man piedāvāt atšķirīgu risinājums vispār. Un, ja tas nav trieciens jūsu prātā, mēs esam no datu struktūras. Tātad šis ir tas Trie - sava veida stulba nosaukumu. Tas nāk no ieguves, un vārdu tekstā ir ierakstīts Trie, t-r-i-e, jo no kurss izguves izklausās Trie. Bet tas ir vēsture vārda Trie. Tātad Trie ir tiešām sava veida koku, un tas ir arī saspēle šo vārdu. Un, pat ja jūs nevar gluži redzēt ar šo vizualizāciju, Trie ir koku strukturēti, kā ģimenes koku ar viens sencis augšā un daudz par mazbērniem un lielu mazbērniem kā atstāj uz grunts. Bet katrs savā Trie mezgls ir masīvs. Un tas ir masīvā - un pieņemsim pārspīlēju brīdi - tas ir masīvs, šajā gadījumā, no 26 izmēra, kur katrs mezgls atkal ir masīvs izmēra 26, kur 0. Elements, kas masīvs pārstāv, un pēdējā elements, katrs šāds masīvs pārstāv Z. Tāpēc es ierosinu, tad, ka šie dati struktūra, kas pazīstams kā Trie, var būt izmantot arī, lai saglabātu vārdus. Mēs redzējām pirms brīža, kā mēs varētu uzglabāt Citiem vārdiem sakot, vai šajā gadījumā vārdu, un mēs redzēja agrāk kā mēs varam saglabāt numurus, bet, ja mēs koncentrējamies uz nosaukumiem vai virknes šeit, paziņojums, kas ir interesanti. Man apgalvo, ka vārds Maxwell ir iekšpusē no šī datu struktūru. Kur jūs redzat Maxwell? STUDENTU: [nedzirdama]. SPEAKER 1: Pa kreisi. Tātad, kas ir interesanti ar šiem datiem struktūra ir nevis veikalā ar string M-A-X-W-E-L-L slīpsvītru nulle, visi contiguously, ko jūs, nevis darīt seko. Ja tas ir Trie, piemēram, datu struktūru, kuriem katram mezglu atkal masīvs, un jūs vēlaties saglabāt Maxwell, vispirms indekss un tā saknes ir mezglā, lai runāt, augšējais mezglu, pēc atrašanās M, pa labi, tā aptuveni uz centru. Un tad no turienes, jums sekot rādītāju uz bērnu mezglu, lai runāt. Tātad ciltskoku nozīmē, jums sekot to uz leju. Un tas noved jūs uz citu mezglu pa kreisi tur, kas ir tikai citā masīvs. Un tad, ja jūs vēlaties saglabāt Maxwell, Jūs atradīsiet rādītāju, kas pārstāv , Kas ir šī viena šeit. Tad jums doties uz nākamo mezglu. Un paziņojums - tas ir iemesls, kāpēc bildes nedaudz maldinošs - šis mezgls izskatās super niecīga. Bet uz tā labajā pusē ir Y un Z. Tas ir tikai autors ir saīsināts attēlu, lai jūs faktiski redz lietas. Pretējā gadījumā šo attēlu varētu būt ļoti plašs. Tātad tagad jūs indekss par atrašanās vietu X, tad W, tad E, tad L, pēc tam L. Tad to, kas ir tas zinātkāre? Nu, ja mēs, izmantojot šāda veida jaunas uzņemties par to, kā saglabāt virknes datu struktūra, jums joprojām ir nepieciešams būtībā ir pārbaudīt pie datos struktūra, vārds beidzas šeit. Citiem vārdiem sakot, katrs no šiem mezgliem kaut kā ir jāatceras, ka mēs faktiski sekoja visi šie norādes un atstāj maz maizes druskas apakšā šeit šā struktūra, lai norādītu, M-A-X-W-E-L-L ir tiešām šajā datu struktūra. Tātad, mēs varētu darīt šādi. Katrs no attēla, mēs tikai mezgliem motorzāģis ir viens, masīvs 27 izmēra. Un tas tagad ir 27, jo p noteikti seši, mēs faktiski dod jums apostrofu, lai mēs varētu būt nosaukumi, piemēram, O'Reilly un citi ar apostrofus. Bet pati ideja. Katrs no šiem elementiem masīvs norāda uz struct mezglā, lai tikai mezglā. Tātad tas ir ļoti atgādina Mūsu saistītajā sarakstā. Un tad man ir Būla, ko es ņemšu zvanu vārdu, kas ir tikai būs taisnība, ja vārds beidzas šis mezglu kokā. Tā faktiski ir maz trijstūris mēs redzējām pirms brīža. Tātad, ja vārds beidzas tajā mezglā koks, ka vārds lauks būs taisnība, , kas ir konceptuāli pārbaudīt off, vai mēs pie šī trīsstūris, jā ir vārds šeit. Tātad šī ir Trie. Un tagad jautājums ir, ko ir tās darbības laiks? Vai tas ir liels O n? Vai tas ir kaut kas cits? Nu, ja jums ir n nosaukumus šiem datiem struktūru, Maxwell ir tikai viens no tiem, kas ir darba laiks Ievietojot vai atrast Maxwell? Kāds ir darba laiks ievietojot Maxwell? Ja tur ir n citi nosaukumi jau galda? Yeah? STUDENTU: [nedzirdama]. SPEAKER 1: Jā, tas ir garums nosaukuma, vai ne? Tātad, M-a-x-W-e-l-l, lai tā uzskata, piemēram, tas algoritms ir liels O septiņi. Tagad, protams, nosaukums atšķiras pēc garuma. Varbūt tas ir īsais nosaukums. Varbūt tas ir garāks nosaukumu. Bet kas ir galvenais šeit ir tas, ka tas ir konstante. Un varbūt tas nav īsti nemainīgs, bet, dievs, ja reāli, jo vārdnīcu, tur droši vien dažas robeža par burtu skaits, kas personas vārds kādā konkrētā valstī. Un tā mēs varam pieņemt, ka vērtība ir nemainīga. Es nezinu, kas tas ir. Tas ir iespējams, lielāks nekā mēs uzskatām, ka ir. Tāpēc, ka tur vienmēr ir dažas stūra gadījumā ar crazy garu nosaukumu. Tāpēc sauksim to k, bet tas joprojām nemainīgs iespējams, jo katrs vārds pasaulē, vismaz konkrētā valstī, ir tas, ka garums vai īsāks, tāpēc tas ir nemainīgs. Bet, kad mēs esam kaut ko teica, ir liels O par konstantu vērtību, kas ir kas tiešām atbilst? Tas ir patiešām pats kā saka pastāvīgu laiku. Tagad mēs esam sava veida krāpšanos, vai ne? Mēs esam veida piesaistot kādu teoriju šeit teikt, ka labi, lai k ir tiešām tikai pasūtīt vienu, un tas ir nemainīgs laiks. Bet tas tiešām ir. Jo galvenais ieskatu šeit ir tas, ka ja mums ir n vārdi jau šajā datu struktūra, un mēs ievietot Maxwell, ir laika daudzums, kas nepieciešams, lai mēs ievietot Maxwell vispār skarto pēc tā, cik daudz citu cilvēku ir datu struktūra? Nešķiet būt. Ja man būtu miljards vairāk elementiem, lai šis Trie, un pēc tam ievietojiet Maxwell, tiek viņš vispār ietekmē? Nē. Un tas ir atšķirībā no jebkura no dienas datu struktūras, mēs esam redzējuši līdz šim, kur darba laiks jūsu algoritms ir pilnīgi neatkarīgi no tā, cik daudz sīkumi ir vai nav jau šajā datu struktūra. Un tā ar šo sniedz jums tagad ir iespēja p kopumu sešiem, kas būs atkal iesaistīt īsteno savu pareizrakstības pārbaudītājs, lasot 150000 Citiem vārdiem sakot, kā labāk uzglabāt, ka ne vienmēr ir acīmredzama. Un, lai gan es esmu vēlējusies, lai atrastu Svētais Grāls, man nav apgalvo, ka Trie ir. Faktiski, hash tabulu var ļoti labi izrādīties daudz efektīvāka. Bet tie ir tikai - tas ir tikai viens no dizains lēmumus Jums būs jāveic. Bet noslēguma pieņemsim 50, vai arī tā sekundes, lai palūkoties, kādi slēpjas priekšu nākamnedēļ, un pēc mēs pārejas No šīs komandrindas pasaulē, ja C programmas uz lietām tīmeklī pamatā, un valodas, piemēram, PHP, un JavaScript un internets pats par sevi, protokolus, piemēram, HTTP, ko jūs esat pašsaprotama gadiem tagad, un drukāti biežāk kā reizi diena, varbūt, vai redzējis. Un mēs sāksim ar mizu atpakaļ slāņi Kas ir internets. Un kāda ir kods, kas ir pamatā mūsdienu instrumenti. Tātad 50 sekundes šajā teaser šeit. Es jums Warriors par Net. [VIDEO PLAYBACK] -Viņš nāca ar ziņojumu. Ar protokolu visiem viņa paša. Viņš nāca pasaulē, nežēlīgi ugunsmūri, uncaring maršrutētāji, un briesmas tālu ļaunāks par nāvi. Viņš ir ātrs. Viņš ir spēcīgs. Viņš ir TCPIP. Un viņš dabūja savu adresi. Karavīri Net. [END VIDEO PLAYBACK] SPEAKER 1: Tas ir kā internets strādā no nākamās nedēļas.