DAVID Malan: Nu labi. Welcome atpakaļ uz CS50. Tas ir sākums no 8 nedēļas. Un atcerēties, ka problēma komplekts 5 beigusies ar mazliet izaicinājums. Tātad, pieņemot, ka jūs atgūt visus jūsu mācību Fellows un CA ir fotogrāfijas ar card.raw failu, jums ir tiesības lai tagad atrast visiem tiem cilvēkiem, un viens laimīgais uzvarētājs būs staigāt mājās ar vienu no šīm lietām, lēciens kustības ierīce, ko var izmantot, lai gala projekti, piemēram. 

Tas katru gadu, izraisa mazliet creepiness. Un tā, ko es domāju, ka es gribētu darīt, ir dalīties ar Jums dažas no piezīmēm, kas ir gājusi uz priekšu un atpakaļ pa darbinieku sarakstu vēlu. Piemēram, tikai pagājušajā naktī, citējot likt pēdiņas beigās, no viena no darbinieku locekļi, "Es tikko bija studentu klauvēt pie manām durvīm, lai fotografētu ar mani. Stalkers, es jums saku "Started off. diezgan aprakstošs, un tad mēs pārcēlās uz, stundu, vai arī tā vēlāk, "man bija students gaida mani pēc iedaļas un viņam bija visas mūsu vārdi un fotogrāfijas par dažiem papīra loksnēm "Labi.. Tātad organizēta, bet ne viss, kas rāpojošs vēl. 

"Tad es biju ārpus pilsētas šīs nedēļas nogalē, un, kad es saņēmu atpakaļ, tur bija viens mans guļamistaba ". [smiekli] DAVID Malan: Nākamais citāts no darbinieku locekle, "students nāca uz manu māju pie Somerville at 4:00 šorīt "Next. personāls, "I got manu viesnīcā San Francisco un studentu gaidīju man pie foajē ar trim DSLRs. " Tipa kameru. "Es neesmu pat par personālu šajā semestrī, bet students ielauzās manā mājā šis no rīta un reģistrē visa lieta Google Glass. "Un tad visbeidzot, "Vismaz 12 cilvēki labprāt gaida mani, kad es saņēmu no manas limo, un pēc tam es pamodās "Labi.. Tātad starp fotogrāfijām, kā jūs varat atgādināt, ir šis puisis šeit, kas jūs varētu zināt, kā Milo banānu, kas dzīvo ar Lauren Carvalho, mūsu galvas mācību Fellow. Milo, Milo, nāk šeit zēns. Milo. Milo. Mind you, viņš valkā Google stikls, tāpēc mēs jums parādīsim tas viss pēc tam. Tātad šis ir Milo, ja vēlaties nofotografēt ar viņu pēc tam. Ja vēlaties meklēt, kas pie klausītājiem tur. Labi. Tas ir labi kadrus. Nu, Milo Banana. Ak, nedari to. 

[Smiekli] 

Labi. Tātad vārdu, tad par to, kas ir priekšā, jo, kā mēs sākam pāreju, šī nedēļa īpaši, no C koncentrāciju komandrindas vide PHP un JavaScript un SQL un HTML un CSS tīmekļa vidē, mēs būsim aprīkot jūs ar visu vairāk zināšanu par iespējamos galīgos projektus. Ceļā Tālab, protams, ir tradīcija rīkojot seminārus, kas ir par pieskaras tēmām līdz gaitā. Ļoti daudz kas saistīti ar plānošanu un app attīstība un tā tālāk, bet ne vienmēr pēta Kurss pašas mācību programmas. 

Tātad, ja jūs varētu būt ieinteresēts vienā vai vairāk no šī gada semināros, reģistrēties cs50.net/seminar. Ir vecāki semināri pie cs50.net/seminars. Un uz žurnāla līdz šim par šo gadu ir Amazing Web Apps ar Ruby on Sliedes, kas ir alternatīva valodu PHP. Skaitļošanas Valodniecība. Ievads uz IOS, kas ir platforma, kas tiek izmantots, lai iPhone un iPad attīstību. JavaScript Web Apps, mēs segtu ka, bet šajā seminārā, jums iet uz sīkāk. 

Lēciens Motion, tāpēc mēs tiešām ir dažas no mūsu draugiem no Leap Motion, pats uzņēmums, mums pievienoties. Rīt, faktiski, lai nodrošinātu hands-seminārs, ja interese uz Jums. Meteor.js, alternatīva tehnika izmantojot JavaScript nav pārlūkprogrammā, bet uz serveri. Node.js, kas ir ļoti daudz šādā veidā, kā labi. Gluds Android Design. Android ir ļoti populāra alternatīva iOS un Windows Phone un citas mobilās platformas. Un Web Security Active Defense. 

Tātad faktiski, ja vēlaties nodarboties ar šo, ļaujiet man pierakstiet to. Mēs esam ļoti priecīgi teikt, ka Mūsu draugi Leap Kustība, kas ir starta - šī ierīce patiešām vienkārši atnāca kas pirms dažiem mēnešiem - ir laipni ziedoja 30 šādas ierīces klasei uz tik daudziem studentiem, ja vēlaties aizņemties aparatūru uz semestra beigām, un izmantot to, lai faktiskais galīgais projekts. Tās atbalsta vairākas valodas. Neviens no viņiem C, neviens no tiem PHP, tāpēc realizēt viens vai vairāki no šiem semināriem var izrādīties interesi. Un visi no tiem tiks filmētas Gadījumā, ja jūs nevarat ierasties personīgi. Grafiks tiks paziņots, izmantojot e-pastu, kā mēs sacietēt istabas. 

Un, visbeidzot, ja jums iet uz projects.cs.50.net, tas ir tīmekļa vietne mēs uzskatām, katru gadu, ka mēs aicinām ļaudīm no sabiedrības, fakultātes, departamenti, personāla, un abi kādā ārpus CS50 līdz ierosina projektu idejas. Lietas, kas ir svarīgas studentu grupām. Lietas, kas interesē departamentu. Tātad, savukārt tur, ja jūs cīnās ar neskaidrību par to, ko jūs pats gribētu, lai risinātu. 

Tāpēc pēdējā laikā mēs ieviesām apstrīdami sarežģītāka datu struktūra, nekā mēs gribētu redzams nedēļu iepriekš. Mēs gribētu, izmantojot bloki diezgan laimīgi kā noderīgi, ja vienkāršots datu struktūra. Tad mēs iepazīstināja tām, kas Protams, ir saistīti sarakstus. Un kāda bija viens no motivācijas ieviešot šo datu struktūra? Yeah? Kas tas ir? 

Mērķauditorija: Dynamic izmēru. 

DAVID Malan: Dynamic izmēru. Tātad, tā kā masīvs, jums ir zināt savu izmēru iepriekš, kad jūs piešķirt to. Saistītajā sarakstā, jums nav ir jāzina, ka. Jūs varat vienkārši malloc, vai, plašākā nozīmē, piešķirt papildu mezglā, tā sakot, jebkurā laikā jums vēlaties ievietot vairāk datu. Un mezgls ir nemaināmi nozīmi. Tas ir tikai vispārējs termins, kas apraksta sava veida konteinerā, kas mēs esam Izmantojot mūsu datu struktūru, lai saglabātu kādu posteni, kas interesē, kas šajā ja gadās būt veseli skaitļi. 

Bet tur vienmēr tradeoff. Lai mēs iegūtu dinamiskās izmērus datiem struktūra, bet par kādu cenu mēs maksājam? Kas savienotu sarakstiem negatīvie? Yeah? 

Mērķauditorija: Nepieciešams vairāk atmiņas. 

DAVID Malan: Tas prasa vairāk atmiņa, kā tieši? 

Mērķauditorija: [nedzirdama]. 

DAVID Malan: Tieši tā. Tāpēc tagad mums ir norādes sākšanu papildu atmiņa, ko mēs iepriekš nav nepieciešams, jo priekšrocība masīva, protams, ir tas, ka viss ir blakus, muguras atpakaļ uz muguras, kas dod jums brīva piekļuve. Tāpēc, ka, tikai izmantojot kvadrātiekavas apzīmējums, vai vairāki tehniski rādītājs aritmētika, ļoti vienkāršs papildinājums, Jūs varat piekļūt jebkura elementi pastāvīgu laiku. Un patiesībā, tas ir sava veida hinting cita cena, mēs maksāt ar saistīts saraksts. 

Kas notiek ar braukšanas laiku kaut kas līdzīgs Search, ja es gribu atrast kādu vērtību un iekšpuses par saistīts sarakstu? Kāda mana darba laika kļūt? Big O n. Ja tas ir sakārtoti, lai? Ko darīt, ja datu struktūra ir sakārtoti? Es varu darīt labāk nekā liels O n meklēšanai? Nē, jo sliktākajā gadījumā tas varētu ļoti labi būt sakārtoti, bet to skaits jūs meklējat varētu būt liels. Tas varētu būt skaitlis 100, kas varētu notikt būt visu veids beigās. Un tāpēc, ka jūs varat piekļūt tikai saistīta sarakstu šajā īstenošanā, veids, kā savu pirmo mezglā, tu esi joprojām ir sava veida no luck. Jums ir, lai šķērsotu visu lieta no pirmā līdz pēdējam, lai atrastu ka liela vērtība ir, piemēram, 100. Vai, lai noteiktu, vai tas ir nav pat tur. 

Tātad, mēs nevaram darīt to, ko algoritms pēc datiem struktūra, kas izskatās šādi? Mēs nevaram darīt bināro meklēšanu, jo bināro meklēšanas nepieciešams, ka mums bija brīvpieejas. Mēs varētu vienkārši lēciens no vietas uz vieta bez sekot šīs maizes drupatas formā no visiem šiem norādes. 

Tagad, kā mēs īstenot šo? Nu, ja mēs ejam uz ekrāna šeit, ja mēs varam ātri reimplement šos datus struktūra - mans rokraksts nav viss, kas liels šeit, bet mēs cenšamies. Tātad typedef struktūrai, un to, ko darīju es vēlas, lai izsauktu šo lietu šeit? Mezglā. Tāpēc es nopirkšu mums sākusies. Un tagad, to, kas ir iekšpusē datu struktūra, kas atsevišķi saistīta sarakstu? Cik lauki? 

Tātad divi. Viens no tiem ir diezgan viegli. Tātad, int n. Un mēs varētu saukt n kaut ko mēs gribam, bet tas būtu int, ja mēs esam īstenojot saistīts sarakstu ints. Un tagad to, ko dara otrā lauks ir jābūt? Struct mezglā *. Tātad, ja man struct mezglā *, un tad es var zvanīt arī tas, ko gribu, bet tikai lai būtu skaidrs, es aicinu tai blakus, kā mēs to esam darījuši. Un tad es aizveru cirtaini lencēm. 

Un tagad, jo pēdējo reizi, Man mezglā uz leju šeit. Bet, ja es esmu atzīts tas ir mezglā, kāpēc man vajadzētu uztraukties ir tik runīgs šeit atzīstot struct mezglā * nākamo, pretstatā lai tikai mezglu * nākamā? Yeah? 

Mērķauditorija: [nedzirdama]. 

DAVID Malan: Tieši tā. Tieši tā. Jo C tiešām, jūs burtiski un redz tikai definīciju mezgla ceļu uz leju šeit, jūs nevarat atsaucas uz to šeit. Tāpēc mums ir šāda veida pirmpirkuma deklarācija šeit, kas ir, protams, vairāk runīgs. Struct mezglā, tas nozīmē, ka mēs tagad var piekļūt iekšpusē no datu struktūru. 

Un kā malā, jo tas ir kļūst nedaudz vairāk subjektīvs tagad, zvaigzne tehniski var doties šeit, tā var iet šeit, tas var pat iet pa vidu. Mēs esam pieņemti, jo stila rokasgrāmata Protams, konvencija liekot star pa labi blakus uz datiem, kas tips, kas šajā gadījumā, būtu struktūrai mezglā. Bet saprast, ir daudz grāmatu, un tiešsaistes atsauces, jūs varētu patiešām redzēt to, no otras puses. Bet tikai saprast, ka gan būs reāli strādāt, un jums vajadzētu vienkārši konsekventa. 

Labi. Tā, ka bija mūsu deklarācija gada struktūrai mezglā. Bet tad mēs sākām darīt vairāk sarežģītas lietas. Piemēram, mēs nolēmām ieviest kaut kas līdzīgs hash tabulu. Tātad, šeit ir hash tabulu izmēru n, indeksē no 0 uz augšu pa kreisi, lai n mīnus 1 uz apakšā pa kreisi. Tas varētu būt hash tabula neko. Bet kāda veida lietas, vai mēs runājam par izmantojot hash tabulu? Uzglabāšana, ko? 

Vārdi. Mēs varētu darīt vārdi, piemēram, mēs pēdējo reizi. Un tiešām, jūs varat saglabāt jebko. Un mēs redzam atkal PHP un JavaScript. Hash tabulu ir jauka veida Šveices Armijas nazis, kas ļauj jums saglabāt diezgan daudz neatkarīgi vēlaties iekšā tas, saistot atslēgas ar vērtībām. Taustiņi ar vērtībām. 

Tagad šo vienkāršo gadījumā, mūsu taustiņi ir tikai skaitļi. Mēs īsteno hash galda kā masīvu. Un tā taustiņi ir 0, 1, 2, un tā tālāk. Un tā mēs, kā cilvēkiem, nolemts pagājušajā nedēļā, ka jūs zināt, ko, ja mēs esam dodas uz veikalu nosaukumiem, pieņemsim tikai patvaļīgi, bet diezgan saprātīgi, pieņemsim, ka Alise, vārds, būs tikai jāindeksē uz 0. Un Bobs, B vārdu, tiks indeksētas uz 1, un tā tālāk. Tātad mums bija kartēšanu starp izejvielām, kas ir virknes, un hash vietas, kas ir skaitļi. 

Tā, ka process ir parasti zināms kā hash funkciju, un jūs varat patiešām ieviest to kodu. Ja es gribēju, lai īstenotu jaucējfunkciju kas dara tieši to, ko mēs tikko aprakstītā no pēdējo reizi, es varētu atzīt funkciju, kas ņem, kā input piemēram - un pieņemsim darīt par šo ekrāns nekā šeit. Ja es gribēju, lai īstenotu hash funkcija, es varētu teikt, kaut kas līdzīgs šim. 

Tas notiek, lai atgrieztos int. Tas būs saukt hash, un tas ir gatavojas pieņemt kā argumentu par virkne, vai arī mēs varam būt pareizi tagad, un teikt char *, mēs to saucam s. Un tad tas viss funkcija ir jādara, galu galā, ir atpakaļ int. Tagad, kā tas, ka varētu nav tik skaidrs. Es esmu gatavojas īstenot šo bez jebkāda veidot kļūdu pārbaudes tiesības tagad. Es esmu tikai gatavojas akli teikt, atgriezties kāds ir s grupā 0, mīnus, teiksim, kapitāla semikolu. 

Pilnīgi sadalīti. Tas nav ideāls, jo viens, kas notiks, ja s ir nulle? Sliktas lietas notiks. Divi, kas notiks, ja pirmais burts šajā nosaukums nav lielais burts? Tas nav gatavojas pārvērst out labi, vai nu. Tas varētu būt mazo burtu vai vēstule vispār. Tāpēc pilnīgi iespējams uzlabot šeit, bet tas ir pamata ideja. 

Ko mēs aprakstīts pagājušajā nedēļā mutiski, kā tikai process kartēšanas Alise 0 un Bob līdz 1 var izteikt noteikti vairāk formulaically kā C darboties šeit. Sauc atkal hash, ņem virkni kā ievadi, un pēc tam kaut kā kaut ko dara ar šo ieguldījumu ražot izejas. Ne atšķirībā no mūsu melnās kastes aprakstu ka mēs esam sen darīts. Es nezinu, kā tas varētu būt darba zem motora pārsega. 

Par problēmu kopumu 6, viens no izaicinājumiem ir, lai jūs varētu izlemt, ko būs jūsu hash funkcija būt? Kas būs iekšpusē, kas melns kastē, un, iespējams, tas būs nedaudz vairāk interesanti nekā šis, un noteikti ir vairāk tendētas uz kļūdu pārbaude par šo konkrēto īstenošanu. 

Taču problēmas var rasties, vai ne? Ja mums ir datu struktūra, piemēram, šis viens, kas ir viena no problēmām, kas jūs varat uzskriet laika gaitā, kā jūs ievietot vairāk un vairāk vārdi uz hash tabulu? Jūs saņemsiet sadursmes, vai ne? Ko darīt, ja jums ir Alise un Āronu, divi cilvēki, kuru vārdi ir noticis sākt ar? Tas izvirza jautājumu, kur jūs ielieciet otru šādu nosaukumu? 

Nu, jūs varētu naivi vienkārši ielieciet to kur Bobs pieder, bet tad Bobs ir veida ieskrūvē, ja jūs mēģināt ievietot savu vārdu blakus un tur nav par viņu istabu. Tātad, jūs varētu nodot Bob kur Čārlijs ir, un jūs varat iedomāties, tas ļoti ātri pārgājuši uz mazliet putru. Kaut lineāra beigās, kur jūs tikai meklēt visa lieta meklē Alice un Bob vai Aaron vai Charlie. 

Tā vietā mēs ierosinājām, nevis tikai lineāri zondēšana atvērtu telpu un plopping vārdus tur, mēs ierosināja mīļotājs pieeju. Hash tabulu īstenots joprojām ar masīvs no indeksiem, bet datu tips šie rādītāji tagad ir norādes. Norādes uz to, ko? Norādes uz saistītām sarakstos. 

Tāpēc atgādina, ka saistīts saraksts tiešām tikai rādītājs uz mezglu, un mezgls ir nākamo lauku, un ka mezglu ir nākamo lauku, un tā tālāk. Tātad jūs tagad domājat par šo masīva uz kreisajā pusē hash tabulu, jo rezultātā saistīta sarakstam. Kuru priekšrocība ir, ja jums sadursme starp Alise un Āronu, Ko jūs darīt ar otrais šāds cilvēks? Jūs vienkārši pievienot viņam vai viņai beigās, vai pat sākums Šī saistīta saraksta. 

Un patiesībā, pieņemsim tikai nūdeles ar ka tikai sekundi. Gadījumos, kad būtu visvairāk nozīmē? Ja es ievietot Alise un viņa nonāks pie pirmā vieta, tad es cenšas ievietojiet Ārona vārdu, un tur ir protams sadursmes, ja man viņam sākumā gada saistītajā sarakstā? Tas ir tajā pirmajā vietā, vai beigās? 

Mērķauditorija: [nedzirdama]. 

DAVID Malan: OK. Es dzirdēju sākumā. Kāpēc sākumā? 

Mērķauditorija: [nedzirdama]. 

DAVID Malan: OK. Tas ir alfabēta, tāpēc tas ir jauki. Tas ir labs īpašums. Tas ietaupīs man kādu laiku potenciāli. Tas neļaus man darīt bināro meklēšanu, bet es varētu vismaz varētu izcelties no cilpas, ja es saprotu, labi, es esmu ceļš agrāk bija Aaron būtu šī sakārtoti saistīts saraksts. Man nav tērēt savu laiku, meklējot visu ceļu līdz beigām. Tātad tas ir saprātīgs. Kāpēc vēl varētu vēlaties ievietot sadurties nosaukums pie sākuma saraksta? Kas tas ir? 

Mērķauditorija: [nedzirdama]. 

DAVID Malan: Tas var aizņemt ilgu laiku , lai iegūtu uz saraksta beigām. Un patiesībā, ilgāk un ilgāk. Jo vairāk vārdu jums ievietot, ka Vispirms, kas ir garāki par ķēde ir gatavojas saņemt. Jo ilgāk, ka saistīta saraksts ir gatavojas saņemt. Tātad, jūs esat patiešām vienkārši izšķērdēt Jūsu laiku. Varbūt jūs labāk saglabājot pastāvīga ievietošanas laiku, Big O 1, , vienmēr liekot sadursmē uzvārdu sākums saistītajā sarakstā, un nav neuztraucoties tik daudz par šķirošanu. 

Kas ir labākā atbilde? Tas ir skaidrs. Tā veida ir atkarīgs no kāda sadalījums ir, kāds modelis ir no nosaukumiem, Jūs ievietojat. Tas ne vienmēr ir acīmredzama atbilde. Bet šeit, atkal, ir dizaina iespējas. 

Tāpēc mēs pēc tam paskatījās šo lietu, kas ir tiešām cita liela iespēja par 6 p-komplektu. Un saprast, ja jums vēl nav, Zamyla ienirst abi šie, hašišs galdi un cenšas, sīkāk. Un video walkthrough ir iestrādāta p-komplekts spec. Tas bija Trie - T-R-I-E. Un kāda bija interesanti par tas bija tas, ka darba laiks lai meklētu vārdu, piemēram, Maxwell pēdējo reizi, bija liels O, ko? Kas tas ir? 

Mērķauditorija: burtu skaits. 

DAVID Malan: skaits burtiem. Es dzirdēju divas lietas. Burtu skaits un pastāvīgu laiku. Tāpēc iesim ar to pirmais. Burtu skaits. Nu, šie dati struktūru, atsaukšana, ir patīk koks, ģimenes koks, katra , kuru mezgli veido masīvi. Un šie bloki ir norādes uz citas šādas mezgli, vai citas tādas matricas koka. 

Tātad, ja mēs vēlējāmies, lai pēc tam noteiktu vai Maxwell ir šeit, es varētu iet uz pirmo masīva, pie ļoti top koks, ts saknes, top Trie, un pēc tam izpildiet m rādītāju, tad rādītājs, tad x, w, e, l, l. Un tad, kad es redzu kādu īpašu simbolu, apzīmē šeit kā trijstūri. Ar kodu jūs redzēt, mēs ierosinām, ka jūs īstenota kā bool, vienkārši sakot, jā vai nē, vārds apstājas šeit. 

Nu, kad mēs esam izgājuši uz M-A-X-W-E-L-L, jūtas kā septiņiem, varbūt astoņas, ja mēs ejam vienu pagātnē to, astoņas pasākumus, lai atrastu Maxwell. Vai sauksim to K. Bet atcerēties pēdējo reizi laiks, es apgalvoja, ka tad, ja tur ir reāli maksimālais garums uz vārdu, piemēram, 40-daži nepāra rakstzīmes, maksimālais garums nozīmē konstanta vērtība. Tik tiešām, jā, tas ir tehniski liels O gada 8 vai 7, vai tiešām ir liels un K. O Bet ja tur ir ierobežots vāciņu par to, K varētu būt, tas ir nemainīgs. Un tā ir liela O no 1 pie beigās, dienā. 

Nav reālajā pasaulē. Nevis tad, kad jūs faktiski sākt skatīties savu pulksteni kā jūsu programmas darbojas. Tas ir absolūti būs nedaudz lēnāk nekā patiesi konstante laiks ar vienu soli. Tas būs septiņi vai astoņi soļi, bet tomēr tas ir daudz, daudz labāk nekā algoritmu, piemēram, no n Big O minētajā ir atkarīga no izmēra to, kas ir datu struktūra. 

Paziņojums otrādi šeit ir, mēs varam ievietot miljons vairāk vārdu uz šo datu struktūra, bet cik daudz soļus tas gatavojas veikt mums, lai atrastu Maxwell šajā gadījumā? Nav. Viņš ir neskarti. Un līdz šim, es nedomāju, ka mēs esam redzējuši piemērs no datu struktūras vai algoritms, kas bija pilnīgi neietekmē ārējie uzvedību, piemēram, ka. Bet tas nevar būt pārsteidzošs. Tas var būt ne tikai šķīdums par p-komplektā 

Un tas nav. Tas ne vienmēr datus struktūru, jums vajadzētu pievilkties, jo, piemēram, hash tabulas, tradeoff. Kāda ir cena, ko maksāt šeit? Atmiņu. Es domāju, tas ir šausmīgs atmiņas apjoms. Un jūs nevar gluži redzēt šeit, jo autors šo attēlu protams saīsināts visi bloki, un mēs neredzam daudz s un B s un C un Q s un Y un z šajās masīvi. Bet viņi tur. 

Katrs no šiem mezgliem Ir virkni Dažu 26 vai vairāk baitu, katrs no kas pārstāv vēstuli. 27, mūsu gadījumā, tā ka mēs varam atbalstīt apostrofus šajā problēmu kopumu. Tātad šī datu struktūra ir patiesi, ļoti blīvs un plašs. Un tas vien, iespējams, galu galā samazinās lietas, uz leju, vai vismaz maksā jums daudz vairāk vietas. Bet atkal, mēs varam izdarīt salīdzinājumi šeit. 

Atsaukt kādu laiku atpakaļ, mēs panācām ļoti vairāk aizraujošu darba laiks šķirošanas kad mēs izmantojam sapludināšanas veida, bet cena mēs maksājām panākt n log n par sapludināšanas veida prasība, ka mēs tērēt vēl kādi resursi? Vairāk vietas. Mums bija nepieciešams sekundāro masīvs kopēt cilvēkus, tāpat kā mēs šeit uz skatuves. Tātad vēlreiz, nav skaidri uzvarētāji, bet tikai subjektīva dizains lēmumi, kas jāizdara. 

Labi. Tā kā par šo? Ikviens atzīst, kuras D-Hall? Labi. Tātad, trīs no mums darīt. Mather House. Tātad tas ir Mather ir dining. Varu derēt, ka visi ēdnīcas ir skursteņi paplātēm, piemēram, šo. Un tas ir tiešām reprezentatīvs par ko mēs esam acīmredzot redzējis jau. Mēs to sauca burtiski kaudze. Un kaudze, attiecībā uz jūsu datora atmiņa, ir vieta, kur dati iet bet funkcijas tiek saukta. 

Piemēram, kāda veida lietas iet uz skursteņa attiecībā uz Atmiņas izkārtojums mēs esam apspriests nedēļās agrāk? Kas tas ir? 

Mērķauditorija: Zvani uz funkcijām. 

DAVID Malan: Es atvainojos. 

Mērķauditorija: Zvani uz funkcijām. 

DAVID Malan: Zvani uz funkcijām, bet Konkrētāk, kas ir iekšā no katra no šie kadri? Kāda veida lietas? Jā. Tātad vietējās mainīgie. Anytime mēs vajag kādu vietējo krātuvi, kā argumentu, vai int man, vai arī int temperatūra, vai kāds vietējais mainīgais, mēs esam bijuši liekot ka uz skursteņa. Un mēs to saucam kaudze, jo Šī layering idejas. Tikko veida spēlēm ar realitāti, koncepcija to. 

Bet izrādās, ka kaudze var arī jāuzskata par datu struktūru, alternatīva masīvu, alternatīva līdz ar to saistītu sarakstu. Kaut kas konceptuāli interesantāku kas vēl var būt realizēts, izmantojot kādu no tiem, lietas, bet tas ir atšķirīgs veids datu struktūra atbalsta, tiešām, tikai divas operācijas. Bet jūs varat pievienot uz mīļotājs funkcijas nekā tās. Bet tie ir pamati - push un pop. 

Un ar kaudzi Ideja ir tāda, ka, ja es ir šeit, ar vai bez Annenberg zinot, paplāti no blakus durvīm ar numuru 9 par to. Tik vienkārši int. Un es gribu, lai push to uz datu struktūra, kas šobrīd ir tukšs. Uzskata, ka tas apakšā kaudzes. Es liktu šo numuru 9 uz kaudze, un tagad tas ir labi tur. 

Bet interesanta lieta par kaudze ir tas, ka, ja es tagad gribu, lai push kādu citu vērtību, piemēram, 17, un es push tas uz kaudzīti, es esmu gatavojas darīt vienīgā intuitīvu lieta, es esmu tikai gatavojas likt to tur, kur mēs, cilvēki būtu vēlme likt to, uz augšu. Bet kas ir interesanti tagad ir, kā es varu saņemt pēc 9? Ziniet, man ne bez pūlēm. 

Tātad, kas ir interesanti par kaudze ir, kas pēc konstrukcijas, tas ir LIFO datu struktūra. Dumjš veids, kā aprakstīt pēdējais iekšā, pirmais ārā. Tātad pēdējais numurs šajā laikā bija 17. Tātad, ja es gribu, lai pop kaut ko off no skursteņa, tā var būt tikai 17. Tātad tur ir obligāta kārtība operācijas šeit, kur pēdējā vienība , kas ir par pirmo viens out. Tādējādi akronīms, LIFO. 

Tātad, kāpēc tas varētu būt noderīga? Vai to kontekstu, kurā jūs gribētu gribu datu struktūra līdzīgs šim? Nu, tas noteikti ir bijis noderīgs iekšpusē datoru. Tātad operētājsistēmas nepārprotami izmantot šo veida datu struktūras skursteņi. Mēs redzam arī pašu domu kad runa ir par interneta lapas. Tātad, šīs nedēļas, un nākamajā nedēļā, un ārpus tās, un kā jūs sāktu īstenot internetā lappuses valodā sauc par HTML, jūs varat faktiski izmantot datu struktūra, piemēram, tas, lai noteiktu, vai lapa ir pareizi formatēts. Tāpēc, ka mēs redzēsim visas web lapas ievērot veida hierarhijas, iespiedumiem kas būs, beigās, dienā, būt koka struktūru zem motora pārsega. Tā vairāk, ka tikai mazliet. 

Bet tagad, pieņemsim ierosināt Mirklī, kā mēs varētu iet par pārstāv kāda kaudze ir? Ļaujiet man ieteikt, ka mēs īstenojam kaudze ar kodu, kā šis. Tātad kaudze nāksies iekšpusē no tā divas lietas, masīvs, ko sauc paplātes, tikai jāsaskan ar demo. Un katru no minētās masīva preces būs tipa int. Un jauda ir jādomā, ko? Tā kā es esmu nav rakstīts pilnas izšķirtspējas šeit. 

Tas ir iespējams maksimāli izmērs masīva. Un tas ir iespējams, deklarēta kā asas define augšpusē failu, daži veida pastāvīgu uz ko norāda tikai kapitalizācija. Tātad kaut kur jauda tiek definēta kā maksimāli iespējamo izmēru. Tajā pašā laikā, iekšpusē no datu struktūru pazīstams kā kaudze tur būs ir vesels skaitlis tikai zināms vienkārši kā izmēru. 

Tātad, ja es būtu, lai pārstāvētu šo tagad gleznieciski, pieņemsim, ka tas Visa melnā kaste ir mana kaudze. Iekšpusē no tā ir divi mainīgie. Tāpēc es esmu gatavojas izdarīt Pirmais kā izmēru. Un otrs es esmu gatavojas izdarīt tik masīva. 

Bet tikai, lai saglabātu lietas sakārtotu, Parasti es vēlētos pievērst masīvu, piemēram, , bet tas ir sava veida jauki ja mēs atbilst realitātei, vai atbilstu garīgo modeli. Tātad, ļaujiet man vietā izdarīt masīvs vertikāli, kas ir tikai, atkal, mākslinieka pārsūtīšanu. Nav īsti svarīgi, kas tas ir zem motora pārsega. Un mēs sakām, ka, pēc noklusējuma, jauda būs trīs. Tāpēc šī būs vieta 0, šī būs izvietojums 1, šis būs vieta 2. 

Ja es uzpirkt ar stresa bumbu, būtu kāds gribētu nākt klajā un palaist iekāpt šeit tikai uz brīdi? Labi, redzēju savu roku pirmās. Nāciet uz augšu. Labi. Tāpēc es uzskatu, ka ir Stīvens. Nāciet uz augšu. Labi. 

Bet pieņemsim, ka tagad mēs attītu uz sākotnējo valsts daļām, kurās es tikko paziņoja kaudze, un tas ir būs trīs jaudas. Bet lielums vēl nav noteikts. Paplātes vēl nav noteikts. Tātad pāris jautājumus pirmās. Un ļaujiet man sniegt jums mikrofonu, lai jūs varētu piedalīties aktīvāk šajā darbā. 

Tātad, kas ir iekšā izmēra šajā brīdī laikā, ja viss, kas man ir jādara, ir paziņoja kaudze ar viena līnija kodu? 

Steven: Nav daudz. 

DAVID Malan: Labi, nav daudz. Vai mēs zinām, kas ir iekšā no to lieluma, Vai mēs zinām, kas ir iekšā Šī masīva šeit? 

Steven: Just izlases kods, vai ne? Just - 

DAVID Malan: Jā, es esmu gatavojas to sauc par kodu, bet izlases - 

Steven: Lietas. 

DAVID Malan: Lietas, piemēram, izlases 

Steven: Bits. 

DAVID Malan: Bits, vai ne? Tātad atkritumu vērtībām, vai ne? Tātad permutācijas 0 un 1 s. Paliekas iepriekšējo paražas šīs atmiņas. Un mēs īsti nezinām, ko vērtībām ir, tāpēc mēs parasti izdarīt tos kā jautājuma zīmes. 

Tātad, pirmā lieta, ko mēs, iespējams, gatavojas vēlaties darīt šeit - un ļaujiet man sniegt šo lauku iekšpusē no turienes nosaukums - paplātes. Kas mums būtu iespējams inicializēt izmērs, ja mēs vēlamies, lai sāktu izmantot šo steku? 

Steven: Paplāte ir sub 3. 

DAVID Malan: Tātad, OK. Lai būtu skaidrs, jauda ir deklarēta citur, kā trīs. Un tas, ko es esmu, ko izmanto piešķirt masīva. Lielums gatavojas atsaukties uz cik paplātes pašlaik uz skursteņa. 

Steven: Zero. 

DAVID Malan: Tātad tas būtu nulle. Tik iet uz priekšu, un ar jebkuru pirkstu, izdarīt nulli izmēru. Labi. Tāpēc tagad, kas ir iekšā šīs šeit, mēs nezinām. Tie ir patiešām tikai atkritumu vērtības. Lai mēs varētu izdarīt jautājuma zīmes, bet pieņemsim uzturēt padome tīru tagad tāpēc, ka tas nav svarīgi to, kas ir tur. Mums nav nepieciešams, lai sāktu masīvs kaut ko, jo, ja mēs zinām, ka no kaudzes lielums ir nulle, labi, mēs nedrīkst meklē kaut ko, kas šis masīvs vienalga Šajā brīdī. 

Tāpēc tagad pieņemsim, ka man push uz kaudzīti 9 numuru. Kā mēs atjaunināt datu struktūra iekšā šajā melnajā kastē? Kādas vērtības ir jāmaina? 

Steven: Ievērojot - izmērs? 

DAVID Malan: OK. Izmērs jākļūst ko? 

Steven: Izmērs varētu būt viens. 

DAVID Malan: OK. Tātad lielums ir kļuvusi par vienu. Tātad jūs varat izdarīt pāris veidos. Ļaujiet man sniegt jums, tagad jūsu pirksts ir dzēšgumija. Labi. Tad tagad pirkstu ir suku. Labi. Un tagad, kas vēl ir jāmaina, protams, kas ir datu struktūra? 

Steven: Mēs ejam no no apakšas uz augšu līdz 9. 

DAVID Malan: 9. Labi, labi. Tātad joprojām nav svarīgi, kāda ir pie izvietojums viens vai divi, jo tie ir atkritumu vērtībām, bet mums nevajadzētu raizēties meklē tur, jo izmērs ir stāsta mums, ka tikai pirmais elements faktiski ir likumīga. Tāpēc tagad es push 17 uz sarakstā. Kas notiek ar šo attēlu? 

Steven: Tā lielums ir gatavojas doties uz diviem. 

DAVID Malan: OK. Jūs esat dzēšgumija - Ups. Tu esi dzēšgumija. 

Steven: Eraser. 

DAVID Malan: Tu esi suka. 

Steven: Brush. 

DAVID Malan: OK. Un ko vēl? 

Steven: Un tad mēs - 

DAVID Malan Mēs uzstājām 17. 

Steven: Mums jāturas 17 uz augšu, tāpēc - 

DAVID Malan: Labi, labi. 

Steven: - nomest to uz leju. 

DAVID Malan: Nu labi. Tas kļūst viegli. Es neesmu gatavojas, lai palīdzētu jums šajā laikā. Push 22. 

Steven: Done. Kļūstot dzēšgumija. Es esmu kļūst suku. Un tad es esmu liekot 22. 

DAVID Malan: 22. Excellent. Tātad vēl vienu reizi. Es esmu tagad gatavojas virzīt uz kaudzīti 26. 

Steven: Ooh. Ak Dievs. Jūs tiešām nozvejotas mani off aizsargs. 

DAVID Malan: Jums nav redzēt šo nāk? 

Steven: Es neredzēju šo nāk. Vai mēs vēlreiz sākotnējo jaudu? 

DAVID Malan: Tas ir labs jautājums. Tātad, mēs esam sava veida krāsotas sevi stūrī šeit. Tur tiešām nav labs, kas paredzēti Steven jo mēs esam piešķirti šo masīvu statiski, tā sakot, iekšā no datu struktūru. Un mēs esam būtībā grūti kodēta tā, lai būtu par trīs izmēru. Tātad, mēs nevaram īsti pārdalīt to. 

Mēs varētu, ja mēs devāmies atpakaļ, mēs jauna paplātes būt rādītājs, ka mēs pēc tam izmantot malloc rokā atmiņu līdz. Jo, ja mēs saņēmām atmiņas no kaudze ar malloc, mēs tad varētu atbrīvot to. Bet pirms atbrīvojot to, mēs varētu pārdalīt lielāku rieciens atmiņas, atjaunināt rādītāju, un tā tālāk. Bet tagad, tas ir patiešām labākais, ko mēs varam darīt. Push un pop ir iespējams gatavojas lai ir, kas signalizē dažas kļūdas. 

Tātad, piemēram, mūsu īstenošana no push varētu atgriezties bool kas iepriekš atgriezās taisnība, patiesība, taisnība. Bet ceturtā reize, tas nāksies atgriezties viltus, piemēram. Labi. Ļoti labi darīts. Apsveicu. Jūs esat nopelnījis savu stresa bumbu šodien. 

[Aplausi] 

Steven: Paldies. 

DAVID Malan: Paldies. Labi, tāpēc šķiet, ka tas nav daudz par soli uz priekšu, vai ne? Mēs aprakstīti šo datu struktūra. Tas ir bijis pārliecinoši, vai ne? Operētājsistēmas patīk. Acīmredzot Web var izmantot šo, un citi pieteikumi vēl. Bet ko stulba ierobežojums, ka mēs esam atpakaļ uz Kārtot nedēļas divām galējībām kur mēs esam fiksēta izmēra masīvus. 

Tātad tur ir tiešām pāris veidi, kā mēs varētu atrisināt šo. Mēs varētu dinamiski piešķirt masīvs, nevis grūti kodēšanas to, kā es esmu darīts šeit, bet gan atkārtoti paziņojot tas, tikai, lai būtu skaidrs, kā kaut kas līdzīgs šim. Int * paplātes, ne lemt uz jaudu vēl. Bet, kad es deklarēt kaudze citur manā kodu, es varētu saukt malloc, iegūt adresi rieciens atmiņu, un es varētu piešķirt šo adresi paplātes. 

Un tad, tāpēc, ka tas ir tikai rieciens atmiņu, es varētu turpināt izmantot kvadrātveida kronšteins notācija parastajā veidā. Jo atkal, tur ir sava veida šīs funkcionālā bloki ekvivalents un gabalos atmiņas, kas nāk atpakaļ no malloc. Mēs var ārstēt vienu, kā cits izmantojot rādītāja aritmētisko vai kvadrātiekavas notācija. Tāpēc tā ir viena pieeja. 

Bet kā gan citādi mēs varbūt īstenot šo pašu datu struktūru, iespējams? Labi? Es jūtu, ka mēs vienkārši atrisināt šo problēmas, piemēram, pirms nedēļas. Kāds bija šīs problēmas risinājums ka Steven uzbrauca? Tātad, kas saistītas saraksti, labi. 

Ja problēma ir tā, ka mēs esam krāsošana sevi kaktā, piešķirot iepriekš pārāk maz atmiņas, kas mums tad ir kaut kā tikt galā ar, labi, kāpēc ne tikai novērstu to, ka izdot pavisam? Kāpēc ne tikai deklarēt šķīvji būt rādītāju uz mezglu, ergo saistīts sarakstu, un tad vienkārši piešķirt jaunas mezglu katru reizi, kad Steven nepieciešams, lai ietilptu numurs uz datu struktūru. 

Tātad aina būtu jāmaina. Tas nav būs tik tīrs, un kā vienkārši, kā tikai masīva trīs ints. Tagad tas būs rādītājs struktūrai, un ka struktūrai gatavojas ir int un nākamo rādītāju. Tas būs vadīt, izmantojot šo rādītāju citai šādai struktūrai, kas vēl viens šāds struktūrai. Tātad aina būtu reāli iegūt mazliet Mesjē. Un mēs esam bultas sasaistīšana viss kopā. 

Bet tas ir labi, labi, jo mēs esam redzējuši, kā to izdarīt. Un, kad jūs iegūt apmierināti īsteno kaut kā saistīts sarakstu, kas jums jādara, ja jūs izvēlas īstenot hash tabulu atsevišķa Ķēžu par 6 p-komplekts, jūs varat izmantot to kā elements, vai sastāvdaļa, vai arī nulles runāt, procedūru, kaut kas jums runājot, jums izveidojāt savu puzzle gabals , kas pēc tam var atkārtoti. Tātad kompromisi, taču iespējamie risinājumi ka mēs esam patiesībā redzējis. 

Tātad diezgan bieži, jūs redzēt šo katru gadu vai diviem, kad Apple izlaidumi kaut ko jaunu, un visi trakie rindā ārpus Apple veikalu, lai nopirktu to mazsvarīgs jaunināt uz aparatūras. Es saku, tas ir OK, jo Es esmu viens no tiem cilvēkiem. Tātad, kāda veida datu struktūras varētu pārstāvēt šo realitāti? 

Nu, sauksim to rinda, līnija. Tātad Britu sauktu to parasti rinda anyway, tāpēc tas ir jauki nosaukumu. Un abas operācijas, kas rindā atbalsta mēs saucam par Enqueue darbību un dequeue darbību, , kas ir līdzīgas gars, lai push un pop. Tā ir tikai sava veida atšķiras konvencija, ko mēs esam aicinot tos. Bet, lai ierindod kaut ko nozīmē, lai pievienotu vai ievietot to uz datu struktūru. Lai dequeue līdzekļus, lai novērstu to. Bet, lai gan kaudze bija LIFO datu struktūra, rinda ir pirmais, pirmais ārā datu struktūras. 

Ja Jūs esat pirmais cilvēks rindā, Jums būs pirmā persona, lai iegūtu no līnijas, un iegādāties savu jauno ierīci. Iedomājieties, cik sajukums šie cilvēki būtu ja Apple vietā izmanto steku, lai Piemēram, lai īstenotu picking up savu jauno rotaļlietu. Tāpēc rindas jēgas, protams, un mēs varam domāt par visu veidu pieteikumi, iespējams, uz rindas, jo īpaši, ja jūs vēlaties godīgumu. Tātad, kā mēs varbūt īstenot šos kā datu struktūru? 

Nu, es ierosinu, ka mēs varētu nepieciešams to darīt šādā veidā. Tāpēc es esmu gatavojas tagad ir numuri. Tāpēc mēs saglabāt vienkāršu un ne vienmēr runājam attiecībā uz paplātes. Tikai cipari, ka cilvēki dabūt. Jauda ir gatavojas, atkal, noteikt Kopējais cilvēku skaits, kas var būt šī pozīcija, jo trīs vai kāda cita vērtība. 

Bet es ierosinu, ka man ir nepieciešams, lai izsekotu ne tikai no lieluma rinda, cik daudz lietas ir tajā. Tātad lielums ir pašreizējais lielums, ietilpība ir maksimālais izmērs. Tikai atkal, nomenklatūra pēc vienošanās. Kāpēc man ir nepieciešams papildu int iekšpusē no rindā, lai sekotu, kurš ir priekšējā rindā? Kāpēc man ir nepieciešams to darīt šajā gadījumā? 

Nu, cik ir šo attēlu mainīsies? Es varu droši atkārtoti visvairāk ar šo attēlu. Ļaujiet man iet uz priekšu un dzēst to, kas ir šeit. Mēs sniegsim tas nedaudz citu nosaukumu šeit. Let 's atbrīvoties no 17, pieņemsim atbrīvoties gada 9 ir, pieņemsim atbrīvoties no 3. Un pieņemsim pievienot vienu citu lietu. Es ierosinu, ka man ir nepieciešams, lai sekotu no saraksta priekšējais, kas ir tikai būs int kā labi. Un mēs ejam, lai saglabātu tā vienkārši. Nav saistīts saraksts tagad. 

Mēs jāatzīst, ka mēs spēsim sasist pret šo ierobežojumu. Bet ko es gribu redzēt notiks šoreiz? Tāpēc domāju, ka man iet uz priekšu, un pirmais cilvēks nāk uz augšu rindā, un tas ir skaitlis 9. Mums ir stresa bumbas. Es varu zagt, teiksim, divi vai trīs cilvēki? Viens, divi, trīs? Nāciet uz augšu. Jau no priekšpuses, jo mēs veiksim šo vienu ātri. 

Katrs no jums tagad būs ventilators zēns rindā pie Apple. Jums nebūs saņem Apple aparatūru beigās šo though. Labi. Tātad jūs esat numuru 9, tu esi 17 numurs, numurs 22. Tie ir patvaļīgi skaitļi, piemēram, students ID vai plauktiņš. Un tikai brīdi, sāksim lai sāktu pievienot lietas. Un es palaist kuģa šeit šoreiz. 

Tātad šajā gadījumā, es esmu inicializēts priekšējais būt - Man tiešām nav īsti aprūpi, ko priekšējais ir, jo izmērs ir nulle. Tātad tas varētu arī vienkārši ir jautājuma zīme. Tie visi ir jautājuma zīmes. Tāpēc tagad mēs sākam reāli redzēt dažus cilvēki uzliku up pie veikala. 

Tātad, ja skaitlis 9, tu esi pirmais tur 05:00, iet uz priekšu un rindā, vai naktī pirms. Labi. Tātad tagad 9 ir šeit. Tātad, 9 ir priekšā no saraksta. Tāpēc es esmu gatavojas iet uz priekšu un atjaunināt lielums šiem pašreizējiem datiem struktūra nav 0 vairs, bet, lai būt 1. Es esmu gatavojas īstenot 9 pie priekšējais no saraksta. Ļaujiet man iet uz priekšu un pārslēgtu ekrānu lai mēs varētu redzēt pagātni mums šeit. 

Un tagad to, ko es gribu likt priekšā? Es esmu gatavojas, lai sekotu, ka priekšējā rindā tieši tagad ir 0 atrašanās vietu. Jo to, kas ir blakus, kas notiks? Nu, pieņemsim, ka tagad es ierindod 17, kā arī. Tātad hop rindā tur. Un atkal, no durvju veida, lai veikals būs šeit. Tāpēc tagad es esmu pievienojusi 17. Un, pat ja šie puiši bloķē ekrāns, tas ir OK, jo mēs varam redzēt šeit. Žēl. 

Mērķauditorija: Mēs varam virzīties - 

DAVID Malan: Nē, tas ir OK. Tas ir milzīgs tur augšā. Tātad 17 tagad ir iekšā rindā. Man ir nepieciešams atjaunināt, kas lauki tagad, lai gan? Labi, noteikti izmēri. Un kā par priekšā? Labi, nē. Priekšējais nedrīkst mainīt, jo atšķirībā no kaudze, mēs vēlaties, lai saglabātu taisnīgumu. Tātad, ja 9 nāca pirmkārt, mēs vēlamies 9 līdz būt pirmais no līnijas un uz veikalu. 

Faktiski, pieņemsim redzēt, ka. Pirms mēs ievietot 22, pieņemsim iet uz priekšu un dequeue 9. Kāds ir Jūsu vārds atkal? 

Mērķauditorija: Džeiks. 

DAVID Malan: Džeiks dodas , kas dequeued tagad. Tātad jums iet uz veikalu. Un izlikties, ka veikalā ir vairāk nekā tur. Tātad tagad, ko nepieciešams - dit-dit-dit! Kas ir nepieciešams notikt tagad? Dizaina lēmums. Tātad nav slikts instinkts, bet - kāds ir tavs vārds atkal? 

Mērķauditorija: David. 

DAVID Malan: David. Tātad, ko Dāvids darīt? Viņš mēģina kārtot ar noteiktu datus struktūra un pārvietot no viņa atrašanās vietas uz Jake bijušajā vietā. Un tas ir labi, ja mēs esam gatavi pieņemt, ka īstenošanas detaļu. Bet vispirms, pieņemsim atjaunināt datus struktūru, pirms mēs to darām. Tā kā es neesmu patika ideja par visu cilvēki, novirzot šajā rindā. 

Tas nav liels galā, ja Dāvids dara to ar viens solis, bet atkal, domāju, ka atpakaļ uz kad mēs esam bija astoņi brīvprātīgie par posms, un mēs esam darījuši, piemēram, ievietojot kārtot, kur mums bija jāsāk pārvietojas visi apkārt. Kas ieguva dārgi, vai ne? Tas padara mani verdziskums par lielo O no N, O liels no n brusas vēlreiz. Tas nav sajūta, piemēram, ideāls rezultāts. 

Tāpēc pieņemsim tikai atjaunināt to. Tā izmērs no rindas vairs nav 2. Tas tagad ir vienkārši 1. Bet es tagad var atjaunināt kaut Man nav atjaunināt iepriekš, priekšējais no saraksta. Es varētu teikt, ir tas, ka vieta 1? Tāpēc tagad mums ir atkritumu vērtība šeit, atkritumu vērtību šeit, un David vidū šo atkritumu. Bet datu struktūra joprojām ir neskarts. 

Un patiesībā, man nav pat nepieciešams, lai mainīt Jake bijušais numuru 9, jo, kas rūpējas. Man ir pietiekami daudz informācijas tagad izmērs, ka es zinu, tur ir viena persona šajā rindā. Un es zinu, ka šī persona ir 1 vietā, nevis 0. Es neesmu skaitīšanas. Tātad, 1, kā arī. Tātad datu struktūra joprojām ir OK. 

Nu, kas notiek tālāk? Let 's Enqueue - kāds ir tavs vārds? 

Mērķauditorija: Callen. 

DAVID Malan: Callen. Let 's ierindod ar Callen, un 22 tagad rindā. Tātad tagad, ko ir jāmaina šeit? Priekšējais nav gatavojas mainīties, protams. Lielums būs jāmaina, lai būtu 2 atkal. Un 22 beidzas šeit, 9 joprojām ir klāt, bet tas ir faktiski atkritumu vērtība tagad. Tas ir tikai palieka no Jake pagātni. 

Tāpēc tagad, kas notiek, ja Es dequeue David? Viens no pēdējā operācija, dequeue Deivids. Mēs varētu pāriet, bet es ierosinu pieņemsim darīt tik maz darbu, cik vien iespējams. Tagad mans datu struktūra iet atpakaļ izmēru 2-1. Bet priekšā rindā tagad kļūst par 2. Man nav nepieciešams mainīt šos skaitļus tikai vēl, tāpēc, ka viņi tikai atkritumu vērtības. 

Bet tagad kas notiek? Pieņemsim, ka es ierindod sevi, 26? Es jūtu, ka man pieder vairāk nekā šeit. Tāpēc es esmu to enqueued. Tāpēc es veida pieder šeit. Un, pat ja jums nav gluži novērtēt to vizuāli uz skatuves, jo mums ir daudz vietas, es būtu nevar stāvot šeit, kāpēc? 

Mērķauditorija: Tu esi no robežas. 

DAVID Malan: pa labi. Es esmu no robežas. Esmu indeksē pēc robežas šī masīva. Es patiešām vajadzētu būt vienā no trīs iespējamās vietas. Tagad, kur ir visvairāk dabas doties? Es ierosinu mēs piesaistīto nedēļu viens triks. Mod operators, procentos. Tā kā es esmu tehniski stāvot 3 vieta, bet man 3 mod jaudu, līdz 3, procentu zīme, 3 - jauda ir 3. Kas tas ir? Kas ir atlikums, kad jūs sadalīt 3 ar 3? 0. 

Tātad, kas liek man bija Džeiks bija, kas ir tiešām laba. Tāpēc tagad īstenošanu Šī lieta dodas uz būt mazliet galvassāpes. Tas patiešām ir tikai viena līnija galvassāpes, koda. Bet vismaz tagad tur ir atkritumu vērtība šeit, bet tur ir divas likumīgu Ints šeit. Un es apgalvot, ka tagad mēs esam darījuši tieši tas, kas mums jādara tik ilgi, kamēr mēs mainām to, Jake vērtība bija par 26. 

Mums tagad ir pietiekami daudz informācijas vēl lai saglabātu integritāti Šīs datu struktūru. Mēs joprojām esam veida no luck, kad mēs vēlas, lai ievietotu četras vai vairāk kopā elementi, bet es varu vismaz dara diezgan efektīva izmantošana šī konstante laiks, patiesībā. Man nav jāuztraucas par novirzot ikviens, kā Dāvida slīpuma bija. 

Kādi jautājumi par skursteņi, vai šajā rindā? 

Mērķauditorija: Vai iemesls, kāpēc jums ir nepieciešams, izmēru, lai jūs zināt, kur ir persona? 

DAVID Malan: Tieši tā. Man vajag zināt izmēru masīva tāpēc, ka man ir nepieciešams zināt, kā tieši daudzas no šīm vērtībām ir likumīga, un tā, ka es varu atrast, kur likt nākamais cilvēks. Tieši tā. Izmērs ir - patiesībā, mēs neesam atjaunināt šo ziņu. I pievienotās sevi pie 26. Lielums ir tagad, nevis 1, 2 bet. Tātad tagad tas tiešām palīdz man atrast galva no saraksta, kas nav 0, ne 1, bet ir 2. Priekšējā saraksta patiešām ir numurs 22. Jo viņš nāca pirmais, lai viņš būtu ielaisti veikalā pirms manis, kaut gan vizuāli es stāvu tuvāk pie veikala. 

Visas tiesības? Kārta aplausi šiem puišiem un mēs ļaujiet viņiem no turienes ārā. 

[Aplausi] 

DAVID Malan: Es varētu ļaut Jūs saglabāt paplāti. Mēs varētu redzēt, kas notiek, ja jūs vēlaties, bet varbūt ne. Labi. Tātad, ko tagad tas atstāj mūs? Nu, ļaujiet man ieteikt, ka tur ir dažas citas datu struktūras mēs varētu sāk pievienot mūsu rīku komplektu, kas būs patiesībā var būt diezgan, diezgan svarīgs, jo mēs nodoties mājas sīkumi. Kas atkal, ir sava veida savienojuma līdz koku veidā kaut ko sauc DOM, dokumentu objekta modeli. Bet mēs redzēsim vairāk ka pirms ilgi. 

Ļaujiet man ieteikt definitionally, ka mēs zvaniet koks tagad, ko jūs varētu zināt, kā vairāk ģimenes koku, kur jūs ir dažas sencis pie saknes koku. Patriarhālā vai matriarch pie pašā augšā koku. Bez laulātā, šajā gadījumā. Bet tagad mums ir, ko mēs saucam bērni, kas ir mezgli, kas karājas pie kreisās bērnu vai labo bērns, bultas, kas attēlotas šeit. 

Citiem vārdiem sakot, jo koka datu struktūru ar datoru, koks ir nulle vai vairāk mezglu. Ja tas ir vismaz viena mezglā, ka sauc saknes. Tas ir lietas, redzes, kas mēs izdarīt augšpusē. Un tas mezglā, tāpat kā jebkuru citu mezglu, var ir nulle, viens, divi vai, vai trīs, vai tomēr daudzi bērni datu struktūra atbalsta. Šajā gadījumā, sakņu, glabāšanai vērtība vienam, ir divi bērni, 2 un 3, tāpēc mēs parasti saucam 2 kreiso Bērnam un 3 labi bērnam. 

Un pēc tam, kad mēs nokļūt uz leju līdz 5, 6, un 7, 6 varētu saukt vidū bērns. Ja jums ir četri bērni, tā izpaužas mulsinoši. Tāpēc mēs pārtraukt izmantot šāda veida no īsceļu mutiski. Bet tas patiešām ir tikai ģimenes koku. Un lapas šeit ir mezgli ka pašiem nav bērnu. Tie karājas pie apakšā koka. 

Tātad, kā mēs varbūt īstenot koku, ka ir tikai divi bērni maksimāli? Mēs to saucam par bināro koku. Bi atkal nozīmē divas, šajā gadījumā, piemēram, ar bināro. Un tāpēc tas var būt nulle, viens, vai divi bērni maksimāli. 

Es ierosinu, ka mēs īstenojam mezglu šajā struktūrā ar int n, un pēc tam divas norādes, viens sauc pa kreisi, viens sauc labi. Bet tie ir tikai jauki patvaļīgu konvencijām. Un kas ir jauki tagad, jo īpaši, ja jums veida cīnījās konceptuāli ar rekursijas, vai arī domāja, ka tas nebija tiešām risinājums, lai kaut ko, it īpaši, ja jūs varētu pietrūkt atmiņas. Tagad, kad mēs runājam par datiem struktūras un algoritmi, kas ļauj mums, lai šķērsotu un manipulēt ar viņiem, Izrādās, ka rekursija nāk atpakaļ daudz vairāk pārliecinoša ja ne skaists veids. 

Tātad, šo es ierosinu, ir īstenošana ar meklēšanas funkciju. Dotas divas ieejas - tāpēc domāju, ka par to kā melnā kaste. Ņemot vērā, divas ieejas, n, int, un rādītāju uz koku, rādītājs mezglā, vai tiešām saknes koku, es apgalvo, ka šo funkciju var atgriezties patiesa vai nepatiesa, ka vērtība n ir iekšpusē no šī koka. 

Kas ir iekšā šajā melnajā kastē? Nu, četras filiāles. Vispirms tikai pārbaudes. Ja koks ir nulle, tikai atgriezties viltus. Ja nav mezglu, nav n, tur nav skaitlis, vienkārši atgriezties viltus. Ja tomēr, n, vērtība, ko jūs meklējat par, ir mazāks nekā koka arrow n, un tikai, lai būtu skaidrs, ko tas nozīmē, kad Es rakstīt koku un tad arrow apzīmējums, n? Tieši tā. Tas nozīmē, ka dereference rādītāju sauc par koku. Iet tur, un pēc tam iegūt iekšpusē no ka mezglu un saņemt savu lauku ar nosaukumu n. Un tad salīdzināt faktisko n, kas bija nonākt Meklēt pret to. 

Tātad, ja n ir mazāks nekā, ka n vērtība no koku mezglā pati, labi, Ko tas nozīmē? Tas nozīmē, ka nekas no pirmā acu uzmetiena. Labi? Tāpat kā, ja jums ir masīvs vērtības, jūs varētu piemērot bināro meklēt kā sava veida plaisas un iekarot. Bet ko pieņēmums tomēr mums ir nepieciešams veikt par bināro meklēt darbu vispār telefona grāmatā, un agrāk piemēri? 

Kā ir sakārtoti. Tātad, pieņemsim precizēt definīciju koku šeit nevar būt tikai koks, kas var ir kāda bērnu skaitu. Ne tikai bināro koku, kas var ir 0, 1, 2 vai maksimāli. Bet kā bināro meklēšanas koku, vai BST, kas ir tikai iedomātā veids, kā pateikt bināro koku tā, lai katrs mezgls ir kreisi bērns, ja tāds ir, ir mazāk nekā mezglā. Un katra mezgla tiesības bērns, ja klāt, ir lielāks nekā mezglā pati. 

Tātad, citiem vārdiem sakot, ja jūs izdarīt koks out, visiem numuriem ir Rūpīgi balstīts piemēram, tas, lai tad, ja Jums ir 55, jo saknes, 33 var iet tā pa kreisi, jo tas ir mazāk nekā 55. 77 var doties uz tās tiesībām, jo tas ir lielāks nekā 55. Bet tagad paziņojums, to pašu definīciju, tas ir rekursīvs definīciju mutiski, ir pieteikties uz 33. 33 kreisā bērns nedrīkst būt mazāks par to, un 33 tiesības bērns, 44, ir jābūt lielāks par to. 

Tātad tas ir bināro meklēšanas koku, un Es ierosinu, izmantojot mazliet rekursijas, mēs tagad var atrast n. Tātad, ja n ir mazāks nekā vērtība N, kas ir arī Pašreizējā mezglā, es iešu priekšu un punt, tā sakot, un tikai atpakaļ neatkarīgi atbilde ir meklējot n gada koks kreisās malas bērns. Paziņojums atkal, šī funkcija tikai sagaida mezglu zvaigzne, rādītāju uz mezglu. Tātad, protams, es varu tikai darīt koku bultiņa pa kreisi, kas novedīs man citu mezglu. Bet kas ir tas mezgls? 

Nu, saskaņā ar šo deklarāciju, Kreisajā pusē ir tikai rādītājs, tā, ka vienkārši nozīmē, ka es esmu iet uz meklēšanas funkciju atšķirīgs rādītājs, proti, viens, kas apzīmē mana kreisā bērna koks. Tātad, šajā gadījumā, rādītāju līdz 33, ja tas ir mūsu paraugs ieejas Tikmēr, ja n ir lielāks nekā vērtība N, pie Pašreizējais mezglu koku, tad es esmu gatavojas iet uz priekšu un noslēgt derības ar otru virziens un tikai teikt, man nav zina, ja šī vērtība n ir no koka, bet es zinu, ja tā ir, tas ir uz leju manu labi filiāle, lai runāt. Tātad, ļaujiet man zvanu rekursīvi meklēt, nokārtojot n atkal, bet garāmejot rādītāju uz manu labo bērnam. 

Citiem vārdiem sakot, ja es esmu šobrīd 55 un es esmu meklē 99, es zinu, ka 99 ir lielāks par 55, tā tāpat kā es tore tālrunis grāmatu nedēļas atpakaļ, un mēs gāja labi, tāpat mēs esam gatavojas doties tieši šeit. Un es nezinu, vai tas ir pie manas labās bērnu, un tas nav, 77 ir tur, bet Es zinu, tas šajā virzienā. Tāpēc es aicinu meklēt pie manas labās bērnam, 77, un ļaujiet meklēšanas skaitlis, kas no tur, ja 99 šajā patvaļīgs piemērs ir patiesībā. 

Else, kas ir gala lieta? Ja koks ir Null ir viens gadījums. Ja n ir mazāks nekā tekošā mezgla vērtība ir cits gadījums. Ja n ir lielāks nekā pašreizējais mezgla vērtība ir trešais gadījums. Kas ir ceturtais un pēdējais gadījums? Es domāju, ka mēs esam ārā no gadījumiem, vai ne? Tas ir, ka n ir Pašreizējais mezglu, ka es esmu par. 

Tātad, ja es esmu meklē 55 šajā brīdī stāstā, ka filiāle koks varētu atgriezties taisnība. Tātad, kas ir interesanti ir tas, ka mēs tiešām, atšķirībā no nedēļas agrāk, mēs veida gada ir divas bāzes lietas. Un tie nav būt visi augšpusē. Top ir bāzes scenārijs, jo, ja koks ir nulle, tur neko darīt. Tikai atpakaļ grūti kodētu vērtība nepatiesa. 

Apakšējā filiāle ir sava veida noklusējuma, kurā, ja mēs esam pārbaudīts null, mēs esam pārbaudīts, ja tas būtu pa kreisi, bet tā nedrīkst būt, mēs esam pārbauda, ​​ja tas ir labi, bet tas nevajadzētu būt, skaidri tas ir jābūt tieši tur, kur mēs esam. Tas ir bāzes scenārijs. Tātad tur ir divas rekursīvas gadījumi iestiprināta tur pa vidu. Bet es varētu būt rakstīts šis jebkurā secībā. Es tikai domāju, tas veida filca dabas vispirms pārbaudīt iespējamo kļūdas, tad pārbaudiet kreisi, tad pārbaudiet labi, tad pieņemam, ka jūs esat pie mezglā jūs tiešām meklē. 

Tātad, kāpēc tas varētu būt noderīga? Tātad izrādās - un ļaujiet man pāriet uz teaser šeit tas ir internetā. Mēs ejam, lai sāktu lietot nav programmēšanas valoda sākumā, bet iezīmēšanas valoda. Iezīmēšanas valoda, kas ir viens, kas ir līdzīgi garā programmas izstrādes valoda, bet tas nedod jums spēja izteikt sevi loģiski. Tas tikai dod jums iespēju izteikt sevi strukturāli. 

Ja jūs vēlaties, lai kaut ko lapā, mājas lapā? Kādā krāsā jūs vēlaties, lai to? Kas fonta izmērs jūs vēlaties, lai to? Ko vārdi jūs faktiski vēlaties par mājas lapā? Tātad, tas ir iezīmēšanas valoda. Bet tad mēs ļoti ātri ieviest JavaScript, kas ir pilntiesīgs programmēšanas valodu. Ļoti līdzīgs sintaktiski pēc izskata līdz C, bet tas būs daži jauki, jaudīgākas, vairāk lietotājam draudzīgu iezīmes. 

Un viens no vilšanos pie šī punkts pusgadu ir tas, ka mēs drīzumā īstenos Speller ir daudz mazāk rindiņas kodu, izmantojot citas valodas nekā C pati par sevi pieļauj, bet iemesls ir mēs drīz saprast. Šī būs pirmā šāda veida mājas lapā. Tas būs pilnīgi underwhelming, pirmais viens mēs veikt. Tas būs vienkārši teikt, hello pasaule. Bet, ja jūs nekad neesmu redzējis pirms, tas ir HTML, Hiperteksta iezīmēšanas valoda. 

Ja jūs iet uz noteiktu izvēlnes opciju lielākā daļa jebkuru pārlūku, jebkurā tīmekļa lapā internets, jūs varat redzēt HTML ka daži cilvēki rakstīja izveidot šo mājas lapu. Un tas, iespējams, neizskatās tik īsu vai kā veikls kā šis. Bet tas sekos modelis no šiem atvērtām iekavām un slīpsvītras un burti un potenciāli numuri. 

Es domāju, ka man dot jums teaser par to, ko jūs varētu darīt ņemot CS50. Ļaujiet man iet uz cs.harvard.edu / aplaupīt, mūsu pašu Rob Bowden mājas lapa. Viņš padarīja šo par mums. Tātad, jūs drīz varētu darīt. Un arī, ko jūs dzirdējāt šorīt - ko esat dzirdējuši šorīt - 

[Hamster DANCE MUSIC] 

- You'Ll varētu veikt šo. Kas mūs sagaida trešdien. Mēs redzēsim jūs tam. 

[Hamster DANCE MUSIC] DAVID Malan: Nākamajā CS50 -