DAVID Malan: Yaxşı. CS50 geri salamlayıram. Bu həftə 8 başlayın. Və problem set 5 sona çatdı geri bir problem bir az. Belə ki, sizin bütün bərpa hərfinin tədris əməkdaşları və CA fotoşəkillər ki, card.raw fayl, siz uyğun İndi insanların bütün tapmaq və bir xoşbəxt qalibi biri ilə ev gəzmək bu şeyi, sıçrayış hərəkət Siz final üçün istifadə edə bilərsiniz ki, cihaz Misal üçün layihələr. 

Bu, hər il gətirib çıxarır creepiness bir bit. Və buna nə Mən bunu istədiyiniz fikir payı sizinlə olan qeydlərindən bəzi artıq geri və irəli getdi gec heyəti siyahısı. Məsələn, yalnız dünən gecə quote üçün heyəti bir-birinə dırnağı bağlamaq üzvləri, "Mən yalnız bir tələbə knock idi mənim qapısını mənə bir şəkil çəkmək üçün. Stalkers, Mən sizə deyə. "Başladı biz köçürülüb sonra ədalətli təsviri və üçün, bir saat və ya sonra, "Mən idi Tələbə dünyası sonra məni gözləyir və o, bizim adları və şəkilləri bütün idi kağız bəzi vərəqələri. "Yaxşı. Belə ki, təşkil, lakin hələ bütün ürpertici. 

Sonra, "Mən bu həftə sonu, şəhər olub və geri əldə zaman, bir var idi mənim yataq otağı. "[gülüş] DAVID Malan: a heyəti Sonrakı quote üzvü, "Bir tələbə mənim evinə gəldi 4 Somerville bu səhər AM. "Next heyəti, "Mən San mənim otel var Francisco və tələbə gözləyirdi üç DSLRs ilə lobbisi mənə. " Kamera növü. "Mən heyət Bu dövr belə deyiləm lakin bir tələbə mənim ev bu qırdı bütün şey səhər və qeyd . Google Cam "və sonra nəhayət, "Ən azı 12 nəfər maraqla idi Mən həyata əldə zaman mənim üçün gözləyir limo, sonra oyandım. "Yaxşı. Belə ki, fotoşəkillər arasında kimi ola bilər Xatırladaq ki, bu fellow Sən kimsən burada, yaşayan Milo Banana kimi bilirik bilər Lauren Carvalho, bizim başçısı ilə Fellow tədris. Milo, Milo, burada oğlan gəlir. Milo. Milo. Ağla, o, Google Glass qalıcı oldu Bu, bütün sonra göstərilir. Əgər istəyirsinizsə Belə ki, bu Milo edir Sonra onunla bir fotoşəkil edir. Siz baxmaq istəyirsinizsə, orada tamaşaçı. OK. Yaxşı görüntülər var. Yaxşı, Milo Banana. Oh, bu nə yoxdur. 

[Gülüş] 

OK. Irəli yalan nə sonra bir söz Belə ki, biz keçid başlayacaq kimi, çünki, bu həftə xüsusilə, bir C-dən command line PHP üçün ətraf mühit və JavaScript və SQL və HTML və CSS-ci ildə bir web-based mühit, biz olacaq bütün ilə təchiz üçün daha çox bilik potensial final layihələr. Ki, sonuna doğru, kurs bir var seminarlar keçirilməsi ənənə olan teğetsel mövzular haqqında seyrinə. Çox proqramlaşdırma ilə əlaqədar app inkişaf və s, lakin mütləq tərəfindən tədqiq deyil Kursun öz proqramı. 

Bir maraqlı ola bilər Belə ki, əgər bu il seminarların və ya daha çox cs50.net/seminar qeydiyyatdan. Older seminarlar var cs50.net/seminars edir. Bu il üçün bu günə qədər Kadrosu haqqında Ruby ilə Amazing web apps var Alternativ olan relslər, PHP dili. Computational Dilçilik. Da olan iOS, Giriş və iPhone üçün istifadə ki, platforma iPad inkişafı. JavaScript Web Apps üçün, biz əhatə edəcəyik ki, lakin bu seminar, siz gedəcəyəm daha ətraflı daxil. 

Motion atılmaq, belə ki, biz, həqiqətən, bəzi olacaq Leap Motion bizim dostlar, Şirkət özü, bizə qoşul. Sabah, əslində, təmin etmək üçün bir praktiki seminar, əgər Əgər maraq. Meteor.js üçün alternativ texnika bir brauzerinizin JavaScript istifadə edərək, lakin bir server. Çox olan Node.js, Bu baxımdan, o cümlədən. Hamar Android Design. Android bir çox məşhur alternativ olan iOS və Windows Phone üçün və digər mobil platformalar. Və Web Təhlükəsizlik Aktiv Müdafiə. 

Belə ki, əslində, istədiyiniz əgər Bu məşğul olmaq, mənə bildirin Bu qeyd edir. Biz ki, çox memnun Leap bizim dostlarımız Başlanğıc olan Motion - Bu cihaz həqiqətən yalnız gəldi bir neçə ay əvvəl out - graciously 30 Belə cihazları hədiyyə etmişdir bir çox tələbə kimi sinif, əgər Siz hardware borc istiyorum semestr sonuna doğru və üçün istifadə faktiki son layihəsi. Onlar dil bir sıra dəstəkləyir. Onların heç biri belə C, onların heç biri PHP, həyata bu seminarların bir və ya daha çox maraq sübut ola bilər. Və onların hamısı lentə olunacaq edə olmayan hadisə şəxsən iştirak etmək. Cədvəli vasitəsilə açıqlanacaq biz otaqlar bərkimək kimi e-poçt. 

Və nəhayət, siz getmək əgər projects.cs.50.net, bu haqqinda biz dəvət hər il saxlamaq ictimaiyyət fakültəsini dən insanlar şöbələri, kadr, həm CS50 üçün bir kənarda layihə ideyaları təklif. Tələbə qruplarının maraq şeylər. Şöbələri maraq şeylər. Siz mübarizə istəyirsinizsə Belə ki, orada tövbə yoxdur nə kimi qeyri-müəyyənlik ilə özünüz həll etmək istəyirik. 

Belə ki, sonuncu dəfə biz arguably təqdim daha mürəkkəb data structure biz had çox son həftə görüldü. Biz olduqca seriallarda istifadə edilmişdir ediyorum Əgər məsud kimi faydalı basitçe data structure. Sonra, bu tətbiq edən əlbəttə siyahıları bağlıdır. Üçün və motivasiya biri nə idi Bu data strukturu tətbiq? Bəli? Nə olub? 

Auditoriya: Dinamik ölçüsü. 

DAVID Malan: Dinamik ölçüsü. Array isə Belə ki, sizə qabaqcadan onun ölçüsü ne zaman siz onu ayırırlar. Bağlı siyahısında, deyil bilirik ki, var. Siz ümumiyyətlə yalnız malloc, və ya, bilər əlavə ayrılması node, belə danışmaq, hər hansı bir zaman daha çox məlumat əlavə etmək istəyirəm. Və node heç bir mənası müəyyən etmişdir. Bu, sadəcə izah ümumi bir müddət var Biz istəyirik ki, konteyner bir növ saxlamaq üçün bizim data structure istifadə bu maraq bəzi maddə olan halda integers olmaq nə. 

Amma bir tradeoff həmişə var. Beləliklə, biz məlumatların dinamik ölçüləri almaq strukturu, amma biz nə qiymət ödəmək edirsiniz? Bağlı siyahıların İşin mənfi tərəfi odur nədir? Bəli? 

Auditoriya: daha çox yaddaş tələb edir. 

DAVID Malan: Bu daha çox tələb edir yaddaş, necə? 

Auditoriya: [işitilemez]. 

DAVID Malan: Eynilə elə. Belə ki, indi biz göstəricilərinə alaraq ki, əlavə yaddaş daha əvvəl ki, ehtiyac yox idi, çünki üstünlüyü bir sıra, əlbəttə, ki, hər şey bitişik, geri geri yükləndiyindən, bu Siz təsadüfi imkanı verir. Çünki yalnız kvadrat mötərizə istifadə edərək, notation və ya daha çox texniki pointer hesab, çox sadə Bundan əlavə, Əgər hər hansı bir istifadə edə bilərsiniz daimi zaman elementləri. Və əslində, ki, imalı növü var biz ilə ödənilməsi edirik ki, bir qiymət bağlı siyahısı. 

Nə çalışan zaman olur Axtarış kimi bir şey, mən istəyirsinizsə bəzi dəyəri və daxili tapmaq bir bağlı siyahı? Mənim çalışan zaman nə olmaq edir? N böyük Ç. Bu sıralanır olur? Nə data structure sıralanır olur? Böyük daha yaxşı edə bilərsiniz Axtarmaq üçün n O? Xeyr, çünki ən pis halda bu ola bilər çox yaxşı sorted, lakin sayı Siz böyük ola bilər arıyoruz. Bu, sayı 100 ola bilər bütün olmaq nə bilər sonunda yolu. Və yalnız bir bağlı əldə edə bilərsiniz, çünki bu həyata keçirilməsində siyahısı ilk node yolu, sen uğurlar həyata hələ cür. Siz bütün şey axır var ilk tapmaq üçün davam 100 kimi böyük dəyəri. Bu və ya müəyyən etmək üçün belə var. 

Beləliklə, biz məlumatların nə alqoritm edə bilməz strukturu kimi görünür ki? Biz binar axtarış edə bilməz, çünki ikili search ki, tələb rasgele erişim. Biz yalnız yer üçün atılmaq bilər riayət olmadan yer şəklində bu çörək qırıntıları Bütün bu göstəricilər edir. 

İndi necə bu həyata idi? Yaxşı, biz burada ekran getmək halda, əgər biz tez Bu data reimplement bilər strukturu - mənim yazı bütün deyil burada böyük, ancaq biz çalışacağıq. Belə ki typedef struct və nə etdi mən Bu şey burada zəng etmək istəyirsiniz? Node. Belə ki, mən açılmış almaq lazımdır. İndi nə daxilində olmalıdır ki story üçün veri strukturu siyahısı bağlıdır? Necə bir çox sahələrdə? 

Iki SO. Bir olduqca asandır. N Belə ki, int. Və biz istəyirik n bir şey zəng edə bilər biz əgər ancaq int olmalıdır ints üçün bağlı siyahı həyata keçirilməsi. İndi nə ikinci edir sahəsində lazımdır? Struct node *. Mən struct node *, sonra mən əgər Mən də istəyirəm nə bu zəng edə bilərsiniz, ancaq mən zəng edəcəyik aydın olacaq gələn, biz bunu olduğunuz kimi. Və sonra mən buruq aşırma yaxın olacaq. 

İndi, son dəfə olaraq, Burada node yazmaq. Amma bu elan alıram əgər kimi node, nə mən olan narahat idi burada struct elan ci verbose node * Növbəti kimi fərqli Növbəti yalnız node * üçün? Bəli? 

Auditoriya: [işitilemez]. 

DAVID Malan: Eynilə elə. Eynilə elə. C, həqiqətən, sizin sözün edir və Çünki yalnız node müəyyən görür burada yolla, siz bilməzsiniz burada qədər baxın. Beləliklə, biz preemptive bu növ var admittedly olan burada bəyannamə, daha ayrıntılı. Struct node o deməkdir ki, indi gedə bilərsiniz məlumatların strukturu daxilində. 

Və bir kənara kimi, bu, çünki , indi bir az daha subyektiv olmaq ulduz texniki burada bilərsiniz, burada getmək olar, ola bilər hətta orta gedir. Biz üçün stil təlimatda qəbul etdik gedişində qoyulması qurultayının məlumatların hüququ yanındakı ulduz növü, bu halda ki, struct node olardı. Lakin dərsliklərin bir çox dərk edir və online istinadlar, həqiqətən, qüdrət digər tərəfdə görürəm. Lakin əslində hər iki həyata işləmək və sadəcə olmalıdır ardıcıl. 

Bütün hüquqlar. Beləliklə, bizim bəyannamə idi ki, struct node. Amma sonra biz çox iş başladı müasir şeylər. Məsələn, biz tətbiq qərar verdi bir hash masa kimi bir şey. Belə ki, burada ölçüsü n bir hash masa edir n yuxarı sol 0 endekslenen minus altındakı 1 buraxdı. Bu hash ola bilər bir şey üçün masa. Amma biz şeyi cür danışmaq nə bir hash masa istifadə haqqında? Nə saxlanılması? 

Adlar. Biz kimi adları edə bilər Biz son dəfə idi. Və həqiqətən, heç bir şey saxlaya bilərsiniz. Və biz yenə bu görürsünüz PHP və JavaScript. A hash masa İsveçrə gözəl bir növ Siz saxlamaq üçün imkan verir ki, Ordu bıçaq olduqca çox siz daxilində istədiyiniz hər hansı dəyərləri ilə düymələri şərik tərəfindən. Dəyərləri ilə Keys. 

İndi bu sadə halda, bizim düymələri yalnız nömrələr. Biz hash həyata edirik bir sıra kimi masa. Və belə açarları 0 var, 1, 2, və s. Və beləliklə, biz insanlar kimi, son qərar Əgər istəyirsinizsə nə bilirik həftə ki, mağaza adları gedən edək yalnız özbaşına, lakin olduqca məntiqi, güman ki, Alice, A adı, yalnız 0 daxil dizine olacaq. Və Bob B adı, indexed olunacaq 1 dilinə və s. Beləliklə, biz, giriş arasında mapping idi olan strings və hash ədəd olan yerlərdə. 

Belə ki, prosesi ümumiyyətlə kimi tanınır bir hash funksiyası, və siz həqiqətən bilərsiniz bu kodu həyata keçirir. Mən hash funksiyası həyata keçirmək istəyirdi ki, dəqiq nə biz edir yalnız keçən zaman təsvir, mən güc kimi, görür ki, bir funksiyası elan Misal üçün giriş - və Gəlin bu barədə bunu buraya ekran. Mən hash həyata keçirmək istəyirdi funksiyası, mən demək olar bu kimi bir şey. 

Bu int geri olacaq. Bu hash adlı olacaq, və bu bir dəlil kimi qəbul etmək niyyətindədir simli, və ya, indi daha çox uyğun ola bilər və char * demək, biz bu s zəng edəcəyik. Və sonra bütün bu funksiya, nə var nəticə etibarilə, bir int qayıtmaq edir. İndi, necə ki, güc belə aydın deyil. Mən heç bir olmadan bu həyata gidiyorum İndi yoxlanılması səhv təşkil edir. Mən kor-koranə demək gedirəm, qayıtmaq s bracket 0 nə edir, mənfi qoy paytaxtı A nöqtəli vergül, deyirlər. 

Ümumilikdə qırıldı. Bu mükəmməl deyil, çünki bir, s null nə olur? Bad şeylər edir. Iki, nə bu ilk məktub adı kapital məktub deyil? Çevirmək niyyətində deyil ki, həyata yaxşı ya. Bu kiçik məktub ola bilər və ya heç bir məktubu. Burada yaxşılaşdırılması üçün Belə ki, tamamilə otağı, lakin bu əsas fikirdir. 

Biz şifahi keçən həftə açıqlanan nə üçün Alice birdən bir proses 1 0 Bob ifadə etmək olar əlbəttə daha formulaically C kimi burada fəaliyyət göstərir. Yenidən hash adlı kimi simli edir giriş, və sonra birtəhər bir şey yoxdur bir çıxış istehsal üçün giriş ilə. Bizim qara qutusu təsviri fərqli biz uzun etdik ki,. Mən bu ola bilər necə bilmirəm başlıq altında işləyir. 

Problem set 6, problemlərdən biri üçün Əgər qərar qəbul etmək üçün nə sizin hash funksiyası olacaq? Ki, qara daxilində olacaq nə qutusu, və ehtimalla, bu olacaq az daha bu daha maraqlı və səhv mütləq daha çox meylli bu artıq yoxlanılması həyata keçirilməsi. 

Amma problemlər hüququ yarana bilər? Biz bu kimi bir veri strukturu varsa biri problemlərdən biri var daxil etməzdən kimi zamanla daxil edə bilərsiniz daxil daha çox adları hash table? Siz sağ, toqquşma almaq? Nə Alice Harun varsa, adları baş iki nəfər A ilə başlayacaq? Harada ki, siz, sual begs ikinci bir ad qoymaq? 

Yaxşı, siz naively yalnız qoymaq bilər Bob aid olduğu, lakin sonra Bob edir Siz cəhd Əgər cür berbat Növbəti onun adını daxil edin və Onun üçün heç bir otaq yoxdur. Belə ki, Charlie olduğu Bob qoymaq bilər və bu çox tez təsəvvür edə bilərsiniz bir mess bir qədər daxil devolving. Sonunda xətti bir şey hara yalnız bütün şey axtarmaq lazımdır Alice ya Bob axtarır və ya Harun və ya Charlie. 

Belə ki, əvəzinə yerine yalnız təklif xətti açıq fəzalarında probing və biz orada adları plopping bir meraklısı yanaşma təklif edir. Bir ilə hələ də həyata bir hash table indeksləri dizi, amma məlumatların növü bu göstəriciləri indi göstəricilərinə idi. Nə Pointers? Bağlı siyahıları Pointers. 

Çünki bağlı siyahısı Xatırladaq ki, həqiqətən yalnız bir node pointer və düyün növbəti sahəsində və node var bir sonrakı yatağı var və s. Belə ki, indi bu array hesab edə bilər bir hash masa kimi sol tərəfində bir bağlı siyahısına aparıcı. Bir almaq olan üstünlüyü Alice Harun arasında toqquşma, Siz ilə nə etməliyəm ikinci şəxs? Siz yalnız onu əlavə və ya onun sonunda, hətta əvvəlinə ki, bağlı siyahısı. 

Və faktiki vasitəsilə yalnız əriştə edək ki, yalnız ikinci edir. Harada ən mənada edəcək? Mən Alice daxil edin və o qədər başa əgər İlk yeri, sonra cəhd Harunun adını daxil edin və var açıq-aydın bir toqquşma, mən qoymaq lazımdır Onun başında bağlı siyahıda? Ki, birinci yer var və ya sonunda? 

Auditoriya: [işitilemez]. 

DAVID Malan: OK. Mən başlayan eşitdim. Nə başında? 

Auditoriya: [işitilemez]. 

DAVID Malan: OK. Bu əlifba var, gözəl var ki. Yaxşı bir əmlak var. Bu, mənim potensial bir neçə dəfə qənaət edəcək. Bu, mənim ikili axtarış qoy, lakin deyil mən ən azı çıxmaq edə bilər Mən həyata bir loop, yaxşı, mən yol Ben keçmiş idi Harun bu olacaq bağlı siyahı çeşidlənir. Mən axtarır mənim vaxt sərf yoxdur sonuna bütün yol. Belə ki, ağlabatan deyil. Niyə başqa siz daxil edə bilərsiniz müəssisələrdə vuruşan adı siyahısı başlayan? Nə olub? 

Auditoriya: [işitilemez]. 

DAVID Malan: Bu uzun bir müddət bilər siyahının sonuna almaq üçün. Və əslində, daha uzun və daha uzun. Daxil etməzdən çox adları ki, A, artıq başlamaq zəncir almaq üçün gedir. Uzun bağlı ki, siyahısını almaq üçün gedir. Beləliklə, siz həqiqətən yalnız istəyirik zaman israf. Bəlkə saxlanması daha yaxşı off istəyirik daimi durub zaman, 1 böyük O, həmişə vuruşan adı qoyaraq bağlı siyahının başında və çox narahat deyil çeşidlənməsi haqqında. 

Ən yaxşı cavab nədir? Aydın deyil. Bu cür asılıdır nə paylanması modeli nə edir adları siz daxil edilir. Bu mütləq deyil açıq-aydın cavab. Amma burada, təkrar edir bir dizayn imkanı. 

Beləliklə, biz, sonra bu şey baxdı olan həqiqətən digər böyük imkandır p-set 6. Və siz artıq varsa, dərk Hash bu həm daxil Zamyla dalış, masalar və daha ətraflı çalışır. Və video gözden geçirmek edir p-set spec ilə əlaqədar. Bu trie idi - T-R-I-E. Haqqında maraqlı nə idi Bu, çalışan dəfə Maxwell kimi, adı axtarmaq son dəfə nə böyük O idi? Nə olub? 

Auditoriya: məktublar sayı. 

DAVID Malan: məktublar sayı. Mən iki şeyi eşitdim. Məktubları və daimi vaxt sayı. Belə ki, ilk getmək bildirin. Məktublar sayı. Bəli, bu data structure, geri ki, bir ağac, bir ailə ağac, hər istəyirəm olan qovşaqlarının serialları təşkil edir. Və bu diziler göstəricilərinə var bu kimi digər qovşaqlarının və ya digər ağac dizilerin. 

Sonra müəyyən etmək istəyirdi Belə ki, əgər Maxwell burada olub, mən getmək bilər çox üst ilk sıra üçün ağac, sözdə kök, üst sonra trie və m pointer edin sonra bir göstərici, x, w, e, l, l. Və sonra, bəzi xüsusi simvolu görəndə bir üçbucaq kimi burada adlandırılmışdır. Kodu biz təklif görürsünüz ki, yalnız bəli deyərək, bir bool kimi həyata keçirilir və ya heç bir söz burada dayanır. 

Yaxşı, bir dəfə biz M-A-X-W-E-L-L getdi sonra, bəlkə yeddi kimi hiss səkkiz biz bu son bir, səkkiz Əgər Maxwell tapmaq üçün addımlar. Yoxsa İT K. deyirik Lakin son geri zaman, mən varsa iddia etdi ki, A real maksimum uzunluğu söz, 40-bəzi küsər simvol kimi, maksimum uzunluğu nəzərdə tutur daimi dəyər. Belə ki, həqiqətən, bəli, bu, texniki böyük O Amma 8 və ya 7, və ya K. həqiqətən böyük O nə bir məhdud cap varsa K ola bilər, bu, daimi var. Və bu 1 böyük O da var Günün sonu. 

Deyil, real dünyada. Həqiqətən seyr başlamaq deyil Proqram çalışan kimi saat. Bu, tamamilə bir az olacaq həqiqətən daimi ləng bir addım vaxt. Bu, yeddi və ya səkkiz addımlar olacaq lakin hələ ki, çox, daha yaxşı ki, n böyük Ey kimi alqoritm daha da ne ölçüsündən asılıdır data structure. 

Burada ayaq biz əlavə edə bilərsiniz fark bu bir milyon ad daha data structure, amma necə bir çox addımlar tapmaq üçün bizi gedir Bu halda Maxwell? Heç biri. O, səmimi deyil. Və bu günə qədər, biz gördük düşünmürəm məlumat strukturu və ya bir nümunəsi tamamilə idi ki, alqoritmi xarici ilə səmimi kimi davranışlar. Amma bu gözəl ola bilməz. Bu yalnız həll ola bilməz p-set üçün 

Və bu deyil. Bu data mütləq deyil strukturu üçün çekilmek lazımdır çünki hash masaları kimi tradeoff. Burada ödəmək qiyməti nədir? Yaddaş. Mən demək, bu dəhşətli deyil yaddaş məbləği. Və kifayət qədər burada görmək bilməz, çünki Bu şəkil müəllifidir Aydındır ki, serialların bütün qaralar və biz A çox görən və deyilik B və C və Q və Y-in və Z-nin bu Diziler edir. Lakin onlar orada istəyirik. 

Bu qovşaqlarının hər biri bütün array edir bir 26 və ya daha çox bayt, hər bir məktub təmsil edir. Biz kömək edə bilər ki, bizim halda 27 problem dəsti apostrophes. Bu data strukturu həqiqətən Belə ki, həqiqətən sıx və geniş. Və tək yavaşlatan başa bilər şeylər down, və ya ən azı bir qiymətqoyma çox daha çox yer. Ancaq yenə də, biz cəlb edə bilər Burada müqayisə. 

Geri bir müddət Xatırladaq, biz çox əldə çeşidlənməsi daha maraqlı çalışan zaman biz birləşməsi sort, lakin qiymət istifadə edərkən biz birləşməsi üçün n nail olmaq n daxil ödənilmiş sort biz sərf ki, tələb daha nə resurs? Daha çox yer. Biz ikinci array lazım kimi, insanları surəti Biz səhnədə burada idi. Belə ki, yenə də, heç bir aydın qalibləri ancaq subyektiv dizayn qərarlar qəbul ediləcək. 

Bütün hüquqlar. Belə ki, necə bu barədə? Hər kəs D-Hall tanımaq? OK. Belə ki, bizim üç yoxdur. Mather House. Beləliklə, bu Mather yemək üçün. Mən bütün yemək zalı var bahis olacaq Bu kimi tepsiler destesi. Və bu həqiqətən nümayəndəsi biz etdik şey açıq-aydın artıq görülür. Biz sanki bir yığın adlandırıb. Sizin baxımından və yığını data gedir kompüter yaddaş edir funksiyaları çağrıldığını edilir. 

Məsələn, hər şeyi nə cür getmək ilə bağlı yığını haqqında biz müzakirə etdik yaddaş layout son həftə? Nə olub? 

Auditoriya: funksiyaları çağırır. 

DAVID Malan: Üzgünüm. 

Auditoriya: funksiyaları çağırır. 

DAVID Malan: funksiyaları zənglər, lakin xüsusilə, hər daxilində var o çərçivələri? Şeyi nə cür? Bəli. Yerli dəyişənlər belə. Anytime biz bəzi yerli storage lazım bir dəlil kimi və ya int I, və ya int temp, və ya hər hansı yerli dəyişən, biz olduğunuz edir yığını ki qoymuşdur. Və biz bunu bir yığın zəng çünki ki, layering fikir. Reallığı ilə matçlarda yalnız cür, onun konsepsiyası. 

Amma bu, çıxır bir yığın da ki məlumat strukturu kimi görünür, bir bir sıra alternativ, alternativ bir bağlı siyahısına. Konseptual daha maraqlı bir şey hələ də ola bilər ki, o ya istifadə həyata şeylər, ancaq fərqli növü var data structure, həqiqətən, dəstəklənməsi yalnız iki əməliyyatları. Amma meraklısı əlavə edə bilərsiniz Bu çox xüsusiyyətləri. Amma bu əsasları var - itələmək və pop. 

Və bir yığın fikir ki, əgər mən və ya Annenberg olmadan, burada növbəti qapı bir tray bilmədən bu sayı 9. Belə ki, yalnız bir int. Mən data üzərinə bu basmaq istəyirəm Hal-hazırda boş olan strukturu. Bu yığını alt düşünün. Mən üzərinə bu sayı 9 təkan olardı yığın, indi sağ var. 

Amma bir yığın haqqında maraqlı şey İndi basmaq istəyirsinizsə ki, digər bəzi dəyəri kimi 17 və mən push yığını üzərinə bu, Mən gedirəm , yalnız gedirəm yalnız intuitiv şey sağ qoymaq üçün harada biz insanların üst, qoyun meylli olardı. Bəs indi Maraqlıdır , necə 9 alıram olunur? Bilirsiniz, mən bir səy olmadan deyil. 

Belə ki, nə haqqında maraqlı bir yığın ki, dizayn edir bir LIFO data structure var. Izah Silly yolu son, ilk. Belə ki, son sayı Bu zaman 17 oldu. Mən bir şey off pop istəyirəm əgər yığını, o yalnız 17 ola bilər. Belə ki, məcburi qaydada var burada əməliyyatları, burada son maddə ilk biri olmalıdır. Beləliklə abbreviaturadır, LIFO. 

Belə ki, niyə bu faydalı ola bilər? Onların məzmunları siz had olan bu kimi bir data structure istəyirsiniz? Bəli, əlbəttə ki, faydalı oldu kompüter daxilində. Belə ki, əməliyyat sistemləri aydın şəkildə istifadə çıxarıcı borular üçün bir veri strukturunun növ. Biz də eyni fikri görürsünüz web pages gəldikdə. Bu həftə və gələn həftə Belə və kənarda, və web həyata başlamaq kimi bir dildə pages HTML, siz adlı həqiqətən kimi data structure istifadə Bu müəyyən etmək üçün əgər səhifə düzgün biçimli edir. Görəcəyik Çünki bütün web pages edin iyerarxiya bir növ, bir abzas , günün sonunda bir olacaq başlıq altında ağac strukturu. Yalnız bir az ki, belə daha çox. 

Amma indi üçün, üzrə üçün təklif bildirin an, biz necə getmək bilər bir yığın nədir? təmsil Biz həyata ki, mənə təklif edək bu kimi kodunu yığın. Belə ki, bir yığın onun daxilində sahib olur iki şeyi, bir sıra adlı qablar, yalnız demo uyğun olmalıdır. Və sıra maddələrin hər bir növü int olacaq. Və tutum ehtimalla nədir? Mən yazılmışdır etdik Çünki Burada tam təyini. 

Bu yəqin ki, maksimum var serialın ölçüsü. Və yəqin ki, kəskin elan edir bəzi fayl üst müəyyən daimi cür nəzərdə tutulan sadəcə kapitallaşma. Belə ki, haradasa gücü müəyyən edilir maksimum ölçüsü kimi. Eyni zamanda, daxili məlumatların strukturu bir yığın kimi tanınan orada olacaq yalnız məlum bir tamsayı sadəcə ölçüsü kimi. 

Mən indi bu təmsil etmək idi əgər pictorially, bu Güman edək ki, bu bütün black box mənim yığını təmsil edir. Bu Inside iki dəyişənlər var. Mən cəlb etmək gidiyorum ölçüsü kimi ilk biridir. Və gedirəm ikinci bir sıra kimi cəlb etmək. 

Lakin, hər şeyi nizamlı saxlamaq adətən mən kimi bir sıra çəkmək olardı gözəl bu, ancaq bu cür biz reallıq uyğun və ya ruhi model uyğun. Mənə əvəzinə array cəlb edək şaquli, olan yalnız, yenə, Sənətçinin ifa. Həqiqətən nə etməz başlıq altında. Və biz, ismarıcları ki, demək lazımdır gücü üç olacaq. Belə ki, bu yeri 0, bu olacaq yeri 1, bu olacaq yeri 2 olacaq. 

Mən stress topu rüşvət varsa, ki, kimsə gəlib və işlətmək istəyirəm yalnız bir an üçün buraya minməyə? OK, ilk əl gördüm. Up Hadi. Bütün hüquqlar. Mən Steven olduğuna inanıram. Up Hadi. Bütün hüquqlar. 

Amma indi biz ilkin geri Güman Dünyanın dövlət harada yalnız bir yığın elan etdi, bu var gücü üç olacaq. Amma ölçüsü hələ müəyyən olunmayıb. Qablar hələ müəyyən olunmayıb. Ilk sual bir neçə belə. Və mənə mic verək siz belə Bu daha fəal iştirak. 

Belə ki, ölçüsü daxilində bu anda nə vaxt mən görülən bütün əgər ilə bir yığın elan kodu bir line? 

Steven: çox deyil. 

DAVID Malan: OK, çox deyil. Biz, ölçüsü daxilində nə bilirsinizmi biz daxili ne bilirik Bu serialın? 

Steven: Just təsadüfi kodu, sağ? Just - 

DAVID Malan: Bəli, mən gedirəm şifrəsini zəng, lakin təsadüfi - 

Steven: Things. 

DAVID Malan: təsadüfi kimi şeylər 

Steven: Bits. 

DAVID Malan: Bits, sağ? Zibil dəyərlər Belə ki, sağ? Belə ki, 0 və 1-nin permutations. Əvvəlki bulges qalıqları Bu yaddaş. Və biz həqiqətən bilmirəm nə dəyərlər , biz adətən onları cəlb edir sual işarələri kimi. 

Biz güman etdiyiniz Belə ki, ilk şey burada etmək istəyirəm gedən - və mənə içərisində bu sahədə verim qablar - bir adı. Biz güman nə başlamaq lazımdır ölçüsü biz istəyirik əgər Bu yığını istifadə başlamaq? 

Steven: Tablası sub 3. 

DAVID Malan: Belə ki, OK. Aydın olmaq üçün, potensialın elan başqa yerdə üç. Və mən istifadə etdiyiniz nə var serialın ayrılacaq. Size istinad gedir nə qədər qablar yığını hazırda var. 

Steven: Zero. 

DAVID Malan: Belə ki, sıfır olmalıdır. Belə ki, davam və hər hansı bir barmaq ilə, ölçüsü sıfır cəlb edir. Bütün hüquqlar. Belə ki, indi, bu daxilində var Burada, biz bilmirik. Bu, həqiqətən, yalnız zibil dəyərlərdir. Beləliklə, biz sual işarələri çəkmək, lakin bilər indi üçün board təmiz saxlamaq edək əhəmiyyətli deyil, çünki orada nə var. Biz serialın başlamaq lazım deyil bir şey, biz bilirik ki, çünki yığını həcmi sıfır, yaxşı, biz bir şey baxaraq lazım deyil hər halda bu array Bu baxımdan zaman. 

Belə ki, indi mən təkan güman ki, yığını üzərinə sayı 9. Necə data structure yeniləmək lazımdır bu qara qutu daxilində? Nə dəyərlər dəyişdirmək lazımdır? 

Steven: Within - ölçüsü? 

DAVID Malan: OK. Size nə olmalıdır? 

Steven: Ölçü biri olacaq. 

DAVID Malan: OK. Belə ki, ölçüsü bir olmalıdır. Belə ki, bir neçə yollarla bunu edə bilərsiniz. Indi mənə vermək imkan verir barmaq Silgi edir. Bütün hüquqlar. Sonra artıq sizin barmaq bir fırça edir. Bütün hüquqlar. İndi nə dəyişdirmək var Aydındır ki, data strukturu? 

Steven: Biz gedirik 9 alt up. 

DAVID Malan: 9. OK, Yaxşı. Belə ki, hələ də nə etməz yeri bir və ya iki onlar istəyirik, çünki zibil dəyərlər, amma biz narahat olmamalıdır ölçüsü, çünki orada axtarır izah edir ki, yalnız ilk element həqiqətən qanunidir. Belə ki, indi mən siyahı üzərinə 17 basmaq. Bu şəkil olur? 

Steven: Yəni ölçüsü iki getmək üçün gedir. 

DAVID Malan: OK. Siz pozan etdiyiniz - oops. Siz pozan istəyirik. 

Steven: Eraser. 

DAVID Malan: Siz bir fırça istəyirik. 

Steven: fırçalayın. 

DAVID Malan: OK. Və daha nəyi? 

Sonra biz -: Steven 

DAVID Malan: Biz 17 itələdi. 

Steven: Biz belə üst 17 Stik - 

DAVID Malan: OK, yaxşı. 

Steven: - Bu açılır. 

DAVID Malan: Yaxşı. Bu, asan əldə. Mən sizə bu dəfə kömək fikrində deyiləm. 22 basın. 

Steven: Done. Silgi olmuşdur. Mən bir fırça olmaq alıram. Və sonra 22 qoyaraq edirəm. 

DAVID Malan: 22. Əla. Belə ki, bir dəfə daha. İndi təkan gidiyorum yığını 26 üzərində. 

Steven: Ooh. Gosh Oh. Siz, həqiqətən, qarovul off məni tutdu. 

DAVID Malan: Siz vermədi Bu gələn görmək? 

Steven: Bu gələn görmədim. Biz yenidən ilkin buraxılış qabiliyyəti bilər? 

DAVID Malan: Bu yaxşı bir sual. Beləliklə, biz növ özümüzü boyalı etdik Burada bir küncündə. Həqiqətən Steven üçün yaxşı yoxdur biz bu array ayrılan etdik, çünki statik, belə ki, içəridə danışmaq məlumatların strukturu. Və biz mahiyyətcə çətin kodlu etdik bu ölçüsü üç olmalıdır. Beləliklə, biz, həqiqətən, təkrar bölüşdürə bilməz. 

Biz, geri getdi bilər qablar bir göstərici ola yenidən təyin sonra əl xatirəsinə malloc istifadə edin. Çünki biz yaddaş var, əgər malloc vasitəsilə yığın, biz sonra onu azad edə bilər. Lakin bu azad əvvəl biz bilər , yaddaş daha yığın təkrar bölüşdürə göstərici yeniləmək və s. Amma indi, bu həqiqətən ən yaxşı biz edə bilərsiniz. Push və pop ehtimalla gedir bəzi səhv siqnal var. 

Belə ki, məsələn, bizim həyata push bir bool qayıtmaq bilər hansı əvvəllər doğru, gerçək, doğru döndü. Ancaq dördüncü dəfə, o, var olacaq Məsələn, saxta qayıtmaq üçün. Bütün hüquqlar. Çox yaxşı. Tebrik edirik. Bu gün stress top əldə etdik. 

[Alqış] 

Steven: Təşəkkür edirəm. 

DAVID Malan: Təşəkkür edirəm. OK, belə ki, bu çox deyil görünür irəliyə doğru addım, sağ? Biz Bu data strukturu təsvir. Bu doğru, çekici oldu? Əməliyyat sistemləri bunu istəyirəm. Göründüyü web, bu istifadə edə bilərsiniz hələ də və digər applications. Amma biz istəyirik ki, bir axmaq məhdudiyyət növ həftə iki məhdudiyyətlər geri Biz ölçüsü Diziler müəyyən etmişdir. 

Belə ki, bir neçə həqiqətən var yolları biz bu həll edə bilər. Biz dinamik serialın ayıra bilər Mən var tərəfindən çətin ki, kodlaşdırma deyil burada görülmüş, lakin əvəzinə yenidən elan Bu, kimi, aydın olmaq bu kimi bir şey. Int * qablar, həlledici deyil hələ gücü. Amma başqa yığını bəyan edərkən Mənim kodu, mən, sonra malloc zəng edə bilər bir yığın üçün ünvan almaq yaddaş, və mən təyin edə bilər qablar ki, ünvanı. 

Və sonra, çünki yalnız bir yığın var yaddaş, mən kvadrat istifadə davam edə bilər adi qaydada bracket notation. Yenə də, bu cür var, çünki funksional serialları ekvivalent və gəlib ki, yaddaş chunks geri malloc edir. Biz digər bir müalicə edə bilərsiniz göstərici hesab istifadə və ya kvadrat mötərizə notation. Belə ki, bir yanaşma. 

Amma necə başqa biz bu həyata bilər Eyni data structure, potensial? Sağ? Biz yalnız bu həll kimi mən hiss edirəm bir həftə əvvəl kimi problem. Bu problemin həlli nə idi Steven qaçdı ki? Beləliklə bağlı siyahıları, doğru. 

Problem biz rəsm edirik ki, əgər ayrılması bir küncə özümüzü əvvəlcədən çox az yaddaş ki, biz sonra birtəhər, yaxşı, ilə məşğul olmaq niyə yalnız qarşısını almaq deyil cəmi vermək? Niyə yalnız tepsiler bir olmaq elan bir node, bundan dolayı bir əlaqəli siyahısına pointer və sonra sadəcə yeni qovşaqlarının ayrılması Steven bir uyğun üçün lazım hər dəfə məlumatların strukturuna daxil nömrəsini. 

Belə ki, şəkil dəyişdirmək lazımdır. Bu təmiz və olacaq deyil üç ints yalnız bir sıra kimi sadə. İndi bir göstərici olacaq struct ki, struct gedir bir int və növbəti göstərici var. Bu göstərici vasitəsilə səbəb olacaq başqa cür struct üçün başqa cür struct. Belə ki, şəkil həqiqətən ki, bir az Messier almaq. Və biz oxlar tying var ediyorum birlikdə hər şey. 

Amma ki, sağ gözəl Bunu necə gördüm. Və sonra rahat olsun Bağlantılı kimi həyata bir şey Siz bilərsiniz siyahısı, əgər bir hash masa həyata keçirmək üçün seçin p-set 6 ayrı chaining, siz bir bina blok, və ya kimi istifadə tərkib hissəsi və ya sıfırdan bir danışmaq, qaydası, siz qoymaq ki, bir şey Öz puzzle parça yaradıldı Əgər yenidən istifadə edə bilərsiniz ki. Belə ki, əvəzetmələr, lakin potensial həllər Biz, həqiqətən, əvvəl gördüm ki. 

Belə ki, tez-tez, bu, hər görmək iki il zaman Apple relizlər yeni və bütün crazy insanlar bir Apple kənarda xətti onların marjinal almaq saxlaya hardware yükseltin. Mən deyirəm, çünki, OK Mən insanlardan biri deyiləm. Belə ki, nə cür data strukturu Bu reallığı əks bilər? 

Bəli, bu bir sıra xətti zəng edək. Belə ki, Britaniya bu adətən zəng növbə hər halda, belə bir gözəl ad var. Və bir sıra iki əməliyyatları biz enqueue arayacaðým yardım edirlər əməliyyat və dequeue əməliyyat, olan oxşar itələmək və pop ruh. Bu müxtəlif yalnız sort var Konvensiya, nə biz bu zəng edirik. Amma bir şey enqueue əlavə etmək deməkdir ya veri strukturu onu daxil edin. Dequeue üçün aradan qaldırılması deməkdir. Amma bir yığın bir LIFO data olduğu halda, strukturu, bir sıra, ilk deyil data structure həyata ilk. 

Siz uyğun olaraq ilk şəxs varsa, siz almaq üçün ilk şəxs olacaq line həyata və yeni cihaz almaq. Bu insanlar necə narahat olacağını təsəvvür Apple əvəzinə bir yığın istifadə etdikdə üçün Məsələn, bu picking həyata keçirilməsi Yeni oyuncaq up. Belə sıralarında əlbəttə ki, hissi və biz bütün növ hesab edə bilər ərizə, ehtimalla sıralarında üçün, Əgər ədalət istəyirik xüsusilə. Belə ki, necə biz bu həyata bilər məlumat strukturu kimi? 

Yaxşı, mən ki, biz güc təklif bu yolu etmək lazımdır. Beləliklə, mən indi nömrələri üçün gedirəm. Beləliklə, biz bu sadə və davam edəcəyik mütləq qablar baxımından danışmaq. Insanlar kazanılmış Just ədəd edir. Tutum yenə gedir ki, düzeltmek ola bilər ki, insanların ümumi sayı Bu xətt, üç və ya digər hər hansı dəyər. 

Amma mən track saxlamaq lazımdır ki, təklif nın ölçüsü yalnız növbə, bu nə qədər şeylər var. Belə ki, ölçüsü cari ölçüsü, potensialı maksimum ölçüsü. Yalnız təkrar nomenklaturası Konvensiya ilə. Neden bir əlavə int daxilində lazımdır var kim takip sıranın xətti qarşısında? Niyə bu halda bunu etmək lazımdır? 

Bəli, bu şəkil necə dəyişdirmək üçün gedir? Mən yəqin ki, ən çox təkrar edə bilərsiniz bu şəkil. Mənə irəli getmək və burada nə silmək edək. Biz bu qədər verəcəyik Burada müxtəlif adını. 17 qurtarmaq Gəlin, Gəlin qurtarmaq 9, bu 3 xilas edək. Və biri başqa bir şey əlavə edək. Mən track saxlamaq lazımdır ki, təklif siyahının ön, hansı yalnız eləcə də int olacaq. Və biz bu sadə saxlamaq olacaq. Henüz bağlıdır siyahısı. 

Biz olacaq etiraf edəcəyik bu limiti qarşı qabar. Amma görmək nə istəyirsiniz Bu zaman baş? Mən irəli getmək və ilk Belə güman nəfər line up gəlir və bu sayı 9 var. Biz stress toplar var. Mən, demək, iki və ya üç nəfər oğurlamaq edə bilərəmmi? Bir, iki, üç? Up Hadi. Sağ ön, çünki Bu bir tez etmək lazımdır. 

Hər indi olacaq Apple line bir fan oğlan. Siz Apple hardware qəbul olunmayacaq Bu baxmayaraq sonunda. Bütün hüquqlar. Siz sayı 9 etdiyiniz Belə ki, sen 17 saylı, 22 nömrəli. Bu kimi, özbaşına nömrələr tələbə şəxsiyyət vəsiqələrini və ya etajer. Və yalnız bir anda, bu başlasın şeylər əlavə başlamaq üçün. Və mən burada bu dəfə board run lazımdır. 

Belə ki, bu halda, mən başlatılmış etdik ön olacaq - Mən, həqiqətən, həqiqətən, qayğı yoxdur nə ölçüsü sıfır, çünki ön edir. Beləliklə, bu həmçinin yalnız bilər sual işarəsi ola bilər. Bu bütün sual işarələri var. Belə ki, indi biz həqiqətən bəzi görmək başlamaq lazımdır nəfər mağaza astarlı. 

Belə ki, 9 saylı, əgər birinci istəyirik orada AM 5, davam və sıralamaq və ya gecə əvvəl. OK. Belə ki, indi 9 burada. Belə ki, 9 siyahı qarşısında. Beləliklə, mən irəli getmək və yeniləmək üçün gidiyorum bu cari məlumatların ölçüsü strukturu, artıq 0 ola lakin 1 olmalıdır. Mən 9 qoymaq gidiyorum siyahısının ön. Mənə davam və ekran keçid edək belə ki, biz burada bizi keçmiş bilərsiniz. 

İndi nə istəyirsən ön qoymaq? Mən track saxlamaq gidiyorum ki, İndi növbə qarşısında yeri 0 edir. Sonra nə hazırlaşır çünki? Yaxşı, mən enqueue indi Güman 17 həmçinin. Belə ki, orada line hop. Və yenə qapı sıralama ilə mağaza burada olacaq. Belə ki, indi mən 17 ekledik. Və bu uşaqlar blok baxmayaraq OK ki, ekran, Biz burada bu qədər edə bilərsiniz, çünki. Bağışlayın. 

Auditoriya: Biz hərəkət edə bilər - 

DAVID Malan: Xeyr, o OK. Bu var böyük var. Belə ki, 17-daxilində sıranın indi. Mən güncellemeniz lazımdır sahələrdə indi necə? OK, mütləq ölçüsü. Və necə ön haqqında? OK, no. Ön, dəyişmək lazım deyil, çünki bir yığın fərqli olaraq, biz ədalət saxlamaq istəyirik. 9 birinci gəldi Belə ki, biz 9 istəyirik xəttin ilk olmaq və mağaza daxil. 

Əslində, ki, görək. Biz 22 daxil əvvəl, edək davam və dequeue 9. Adınız ne yenidən? 

Auditoriya: Jake. 

DAVID Malan: Jake gedir İndi dequeued olunacaq. Belə ki, mağaza daxil gəzmək almaq. Və iddia edən mağaza orada. Belə ki, indi lazımdır nə - Dit-Dit-Dit! İndi nə etmək lazımdır? Design qərar. Belə ki, pis bir instinkt, ancaq - Adınız ne yenidən? 

Auditoriya: David. 

DAVID Malan: David. Davud nə idi? O data düzeltmek növ çalışırdı onun yer quruluşu və hərəkət Jake keçmiş yeri daxil. Biz istediğiniz əgər ki, gözəl bir kimi qəbul həyata ətraflı. Lakin birincisi, bu və veri yeniləmə imkan biz quruluşu əvvəl. Mən bütün ideyası sevən deyiləm Çünki insanlar bu istiqamətdə dəyişir. 

David ilə əgər Bu, heç böyük var bir addım, lakin yenə geri hesab edirəm ki, biz səkkiz könüllü yaşadım zaman mərhələ və biz durub kimi etdik biz başlamaq üçün olduğu sort, ətrafında hər kəs hərəkət. Bu doğru, bahalı var? Bu böyük O mənə yarınmaq edir n, n böyük O yenə kvadrat. Bu kimi hiss deyil ideal nəticəsi. 

Elə məhz bu yeniləmə imkan verir. Belə ki, növbə həcmi artıq 2-dir. İndi sadəcə 1 var. Amma indi bir şey təkmilləşdirə bilər Mən əvvəl yeniləmə vermədi siyahısının ön. Mən demək olar ki, yer 1? Belə ki, indi biz burada zibil dəyəri zibil burada dəyəri və David Bu zibil orta. Amma data structure hələ də bütöv deyil. 

Və əslində, mən hətta lazım deyil Jake sabiq sayı dəyişə 9, umurunda kim çünki. Mən indi kifayət qədər məlumat var Mən var bir şəxs bilirik ölçüsü Bu növbə. Və bilirəm ki, həmin şəxs yeri 1, 0 edir. Mən sayılması deyiləm. O cümlədən 1 belə. Belə ki, data structure hələ OK. 

Yaxşı, sonra nə olacaq? Edək enqueue - Sizin adınız nədir? 

Auditoriya: Callen. 

DAVID Malan: Callen. Üzrə Callen enqueue edək və 22 növbə indi. Belə ki, indi burada dəyişdirə nə? Ön niyyətində deyil Aydındır ki, dəyişir. Size daha 2 olmaq dəyişdirmək üçün gedir. Və 22 burada bitər, 9, hələ də mövcuddur lakin səmərəli A indi zibil dəyəri. Bu, sadəcə Jake keçmişin qalığı var. 

Belə ki, indi baş verərsə, nə Mən David dequeue? Son əməliyyat, dequeue David. Biz keçmək bilər, lakin mən edək təklif mümkün qədər az iş kimi edirik. İndi data structure gedir 2 1 ölçüsü geri. Amma queue qarşısında İndi 2 olur. Mən bu nömrələri dəyişdirmək lazım deyil onlar etdiyiniz yalnız hələ, çünki yalnız zibil dəyərlər. 

Amma indi nə olar? Mən, 26 özümü enqueue güman edirlər? Mən buraya aid kimi hiss edirəm. Beləliklə, mən enqueued olunur alıram. Belə ki, I növ burada məxsusdur. Və kifayət qədər belə olsa səhnədə vizual bunu yüksək qiymətləndiririk, biz oda çox var, çünki mən olmalıdır Burada daimi ola bilməz, niyə? 

Auditoriya: Siz həddi bitti. 

DAVID Malan: Sağ. Mən həddi həyata edirəm. Mən kənarda dizine sonra Bu serialın həddi. Mən, həqiqətən, biri olmalıdır üç mümkün yer. İndi getmək harada ən təbii var? Edirəm ki, biz kullanılarak geliştirilebiliyor təklif həftədə bir oyun. Bu mod operator, faizlə. Mən texniki duran alıram Çünki yeri 3, amma 3 mod tutumu etmək belə 3 faiz işarə, 3 - tutumu 3 var. Nə olub? Qalan nə var 3 3 bölmək? 0. 

Mənə qoyur Belə ki, Jake idi hansı həqiqətən yaxşıdır. Belə ki, indi həyata keçirilməsi bu şey olacaq və baş ağrısı bir az ola bilər. Bu, həqiqətən, yalnız bir xətt var baş ağrısı, kodu. Lakin ən azı indi zibil var dəyər burada, lakin iki var burada qanuni ints. Və mən indi biz görmüşük ki iddia biz belə uzun kimi nə etmək lazımdır dəqiq nə biz nə Jake nin dəyişdirmək dəyəri 26 olmaq idi. 

İndi hələ də kifayət qədər məlumat var bütövlüyünü qorumaq üçün Bu data quruluşu. Biz hələ cür uğurlar həyata olduğunuzda, biz dörd və ya daha çox məlumat əlavə etmək istəyirəm elementləri, amma ən azı göyçəkləşdirmək bilər bu daimi səmərəli istifadə zaman, əslində. Mən dəyişkən narahat yoxdur David meyl kimi hər kəs idi. 

Çıxarıcı borular hər hansı bir sual, və ya bu növbə? 

Auditoriya: səbəbi nə Bilirsiniz ki, siz ölçüsü lazımdır bir şəxs üçün harada? 

DAVID Malan: Eynilə elə. Mən serialın ölçüsünü bilmək lazımdır Mən dəqiq necə bilmək lazımdır, çünki bu dəyərlər bir çox qanuni, qoymaq harada və mən tapa bilərsiniz ki, növbəti şəxs. Eynilə elə. Ölçüsü - Əslində, biz hələ bu verməmişdir. Mən 26 özümü əlavə edib. Ölçüsü, indi 1, lakin 2. Belə ki, indi bu, həqiqətən məni tapmaq kömək edir siyahısının rəhbəri olan 0 deyil, deyil 1, lakin 2-dir. Siyahısının ön həqiqətən sayı 22-dir. O, ilk gəldi, belə ki, o, çünki Məndən əvvəl mağaza daxil icazə verilə, olsa da vizual I duran alıram yaxın mağaza. 

Bütün hüquqlar? Bu uşaqlar üçün alqış dəyirmi və biz onları orada buraxmaq lazımdır. 

[Alqış] 

DAVID Malan: Mən bildirin bilər Siz tray saxlayın. Biz ne olur görmək olar istədiyiniz, amma bəlkə deyil. Bütün hüquqlar. Bəs indi bizi tərk edir? Bəli, bir var ki, mənə təklif edək biz ola bilər bir neçə digər məlumatlar strukturları olacaq ki, bizim alət dəsti əlavə başlamaq həqiqətən, çox, olduqca müvafiq kimi biz web məhsulları daxil Dive. Yenə əlaqədar bir növ var şəklində ağaclar DOM, sənəd deyilən şey obyekt modeli. Amma biz daha çox görürsünüz ki, uzun əvvəl. 

Mənə definitionally təklif edək ki, indi kimi bilirik hansı ağac zəng bir ailə ağac, siz daha çox olan bəzi ulu var Ağacın kökləri. A patriarxal və ya matriarch Ağac çox üst. Öz həyat yoldaşı olmadan, bu halda. Amma biz indi zəng edəcəyik nə var asmaq ki, qovşaqlarının olan uşaqlar, sol uşaq və ya sağ uşaq off, burada təsvir kimi oxlar. 

Bir ağac data structure başqa sözlə, kompüter, bir ağac sıfır var və ya daha çox qovşaqlarının. Ən azı bir node varsa, ki, kök deyirlər. Bu vizual ki, hər şeyi var biz üst cəlb edir. Və node, hər hansı digər node kimi bilərsiniz , sıfır, bir və ya iki, ya üç və ya lakin bir çox uşaqlar data structure dəstəkləyir. Bu halda, kök də saxlama anbarları dəyər bir, iki uşaq, 2 və 3 var belə ki, biz ümumiyyətlə, 2 sol zəng uşaq və 3 hüququna uşaq. 

Və sonra, biz 5-6-aşağı almaq və zaman 7, 6 orta uşaq cəlb oluna bilər. Dörd uşaq varsa, bu confusing olur. Beləliklə, biz bu cür istifadə dayandırmaq şifahi qısa edir. Amma həqiqətən, yalnız bir ailə ağac var. Və burada tərk edən qovşaqlarının var özlərini heç bir övladı var. Onlar ağac altındakı off Restoran. 

Belə ki, necə biz bir ağac ki, həyata bilər maksimum iki övladı var? Biz bu ikili ağac zəng edəcəyik. Bi yenə bu iki məna binar ilə kimi halda. Və belə ki, sıfır, bir ola bilər maksimum və ya iki övladı var. 

Hesab edirəm ki, node həyata ki, təklif edəcəyik bir int n ki, strukturu, və sonra iki göstəricilərinə, bir adlı sol bir sağ çağırıb. Ancaq o yalnız gözəl ixtiyari konvensiya. Və indi xüsusilə gözəl nə var növü ilə konseptual mübarizə recursion və ya deyil idi ki, bir şey, həqiqətən, bir həll Xüsusilə bilər yaddaş tökülmək. Verileri haqqında danışıqlar indi strukturları və imkan verən alqoritmlər bizə axır və onlara manipulyasiya recursion geri gəlir çıxır ki, daha çekici gözəl şəkildə əgər. 

Mən təklif bu həyata keçirilməsidir Belə ki, Axtarış funksiyası. Iki giriş nəzərə alaraq - belə bir qara qutu kimi düşünün. Iki giriş, n, bir int və nəzərə alaraq bir ağac göstərici, bir bir göstərici bir ağac node və ya həqiqətən kök, mən Bu funksiya ola bilər ki, iddia doğru və ya yalan ki, dəyəri n bu ağacın daxilində. 

Bu qara qutu içərisində nedir? Yaxşı, dörd filialları. İlk yalnız yoxlayır. Ağac null deyil, yalnız yalan qaytarın. Heç bir node varsa, heç n var heç bir nömrə var, yalnız saxta qaytarın. Siz aradığınız olsa da, n, dəyəri varsa, üçün, ağac arrow n az və yalnız aydın olması üçün, zaman nə deməkdir Mən sonra ağac və arrow yazmaq notation, n? Eynilə elə. Bu dereference deməkdir ki, göstərici ağac çağırıb. Ki, daxilində almaq sonra orada getmək və node və n adlı sahəsində almaq. Və sonra idi ki, faktiki n müqayisə buna qarşı Search keçdi. 

N n dəyər azdır Belə ki, əgər ağac node özü də, ki, nə deməkdir? Bu ilk baxışda heç bir şey deməkdir. Sağ? Siz bir sıra zaman kimi dəyərlər, siz ikili müraciət etmək istəyirəm bilər uçurum bir forması kimi axtarış və fəth. Amma biz nə ehtimal lazımdır idi binar axtarış bütün iş üçün telefon kitab və əvvəllər nümunələri? 

Sıralanır necə. Elə ağac anlayışına saflaşdırmaq qoy burada olan bilər yalnız bir ağac olmaq uşaqların hər hansı bir sayı vardır. Yalnız ikili ağac, hansı bilər maksimum 0, 1, ya 2 var. Lakin ikili axtarış ağac, və ya TSİ kimi olan yalnız bir söz bir xülya yoludur belə ikili ağac hər node in sol uşaq, indiki halda ki, node azdır. Hər node hüququ uşaq, Hazırda halda, böyükdür node özü çox. 

Belə ki, başqa sözlə, əgər çəkmək üçün idi ağac həyata, nömrələrin bütün diqqətlə bu kimi tarazlaşdırılmış ki, əgər Əgər kök kimi 55 var, 33 bilərsiniz onun sol onu 55-dən az, çünki. 77 hüququndan çünki bilərsiniz 55-dən çox deyil. Amma indi, eyni definition qeyd ki, şifahi bir recursive sözünün var 33 üçün müraciət var. 33 sol uşaq, bu az olmalıdır və 33 sağ uşaq, 44, olmalıdır bu daha böyük. 

Beləliklə, bu bir ikili axtarış ağac və Mən bir az istifadə edərək, təklif recursion, indi n tapa bilərsiniz. N ki, dəyəri n azdır Belə ki, əgər cari node, mən getmək gidiyorum irəli və ayaqla zərbə, belə danışmaq, və yalnız cavab nə qayıtmaq üzrə n üçün axtarış ağacın sol uşaq. Yenidən bildiriş, bu funksiya yalnız bir node ulduz, gözləyir bir node göstərici. Belə ki, Həqiqətən, Mən ağac olduğu edə bilər gətirəcək arrow sol, hidrogücləndirici, mənə bir node. Amma bu node nədir? 

Bəli, bu bəyannamə görə, sol belə ki, yalnız, yalnız bir göstəricisidir Mən axtarış funksiyası keçməsi alıram deməkdir fərqli bir göstərici, yəni təmsil bir mənim sol uşaq ağac. Belə ki, bu halda, pointer, əgər 33 bu, bizim nümunə giriş Eyni zamanda, əgər n da dəyəri n daha böyük ağac mövcud node, sonra Ben digər qabaqda və ayaqla zərbə getmək davam istiqamət və yalnız demək, mən bunu Bu dəyər n ağac olduğu halda bilirsiniz, lakin əgər mən bilirəm ki, bu, aşağı mənim sağ filialı, belə danışmaq. Mənə recursively axtarış zəng edək, yenidən n keçən, lakin keçən mənim sağ uşaq pointer. 

Başqa sözlə, Hal-hazırda Ben əgər 55 və mən 99 arıyorum, mən bilirəm ki, 99 Mən parçaladı belə kimi, 55-dən çox deyil telefon kitab həftə öncə və biz haqlı çıxdıq, eyni biz Burada getmək üçün gedir. Mənim sağ var, əgər bilmirəm uşaq və bu deyil, 77 var, lakin Hesab edirəm ki, bu istiqamətdə bilirik. Beləliklə, mən, mənim sağ uşaq axtarış zəng 77, və axtarış rəqəm buraxmaq orada bu ixtiyari 99 Məsələn, orada əslində. 

Başqa, son halda nə var? Ağac Əgər null bir haldır. N cari node daha az olarsa dəyəri başqa haldır. N cari büyükse node dəyəri üçüncü haldır. Dördüncü və son halda nədir? Mən, biz hallarda bitti mi? Bu n ki olmalıdır Mən Ben cari node. 

Mən bu nöqtədə 55 üçün axtarış alıram Belə ki, əgər Bu hekayə ki, filialı ağac doğru qayıtmaq olardı. Beləliklə, nə maraqlı edir ki, həqiqətən, həftə fərqli olaraq keçmiş, biz cür iki baza hallarda var. Onlar yoxdur üst bütün ola bilər. Üst bir baza halda, çünki əgər ağac null ki, heç bir əlaqəsi yoxdur. Bir ağır kodlu qayıtmaq saxta dəyəri. 

Alt filialı növ edir Default, qovuşdurmağımız biz yoxlanılır olsanız bu olmalıdır, əgər null, biz işaretlediğinizden sol, lakin bu ola bilməz, biz var doğru olmalıdır yoxlanılır, lakin o, olmamalıdır, aydın olmalıdır doğru yerləşir biz. Bir baza halda var. Belə ki, iki recursive hallarda var ortada var sandwiched. Amma yazılı bilərdi Bu hər hansı bir sırada. Mən yalnız növ təbii hiss fikir İlk mümkün səhv kontrol etmək üçün, sonra sol yoxlamaq, sonra, sağ yoxlamaq Siz node da olduğunu güman həqiqətən, aradığınız. 

Belə ki, niyə bu faydalı ola bilər? Belə çıxır - və mənə bir iltifat Keç bildirin burada internet var. Biz istifadə edərək başlamaq olacaq proqramlaşdırma ilk dil, lakin biçimlendirme dili. Ki, bir olan bir biçimlendirme dili proqramlaşdırma ruhda oxşar dil, ancaq vermir qabiliyyəti məntiqi özünüzü bildirirəm. Bu yalnız sizə imkan verir struktur özünüzü bildirirəm. 

Harada bir şey qoymaq istəyirsiniz sayfada, web page? Nə rəng onu istəyirsiniz? Nə font size onu istəyirsiniz? Hansı sözləri həqiqətən siz web page istəyirsiniz? Belə ki, bir biçimlendirme dili var. Amma sonra biz bunu çox sürətlə tətbiq edəcəyik Tamhüquqlu olan JavaScript, dil proqramlaşdırma. Syntactically görünüşləri çox oxşar C, ancaq bəzi olacaq gözəl, daha güclü, daha istifadəçi dostu funksiyalar. 

Və bu da frustrations biri dövr nöqtəsi biz edəcəyik ki, tezliklə çox az ilə speller həyata başqa dillərdə istifadə kodu xətləri C özü imkan verir çox, lakin səbəbi üçün biz tezliklə başa bilərsiniz. Bu, birinci belə web page olacaq. Bu, tamamilə underwhelming olacaq biz birinci. Bu, sadəcə dünya hello, deyəcəklər. Amma siz onu görməmişəm, əgər əvvəl bu, HTML Hypertext Markup Language. 

Siz müəyyən bir menyu seçimi getmək Əgər hər hansı bir web page ən çox hansı brauzer, internet, siz HTML bilərsiniz bəzi insanlar yazdı web səhifə yaratmaq. Və yəqin ki, kimi baxmaq deyil qısa və ya bu kimi səliqəli. Amma bu modeli izləyəcək açıq mötərizədə və slashes və məktubları və potensial nömrələri. 

Mən sizə bir teaser vermək istədiyiniz fikir Siz edə bilərsiniz nə CS50 sonra. Mənə cs.harvard.edu / rob gedək, öz Rob Bowden ana. O, bizim üçün bu etmişdir. Belə ki, tezliklə bunu edə bilərsiniz. Və həmçinin, nə eşitdim Bu səhər - Siz bu gün səhər eşitdim nə - 

[Hamster DANCE MUSIC] 

- You'll bu edə bilər. Bu barədə çərşənbə günü bizi gözləyir. Biz sizə sonra görəcəksiniz. 

[Hamster DANCE MUSIC] DAVID Malan: növbəti CS50 hazırda -