HOPARLÖR 1: Bütün sağ, biz geri edir. CS50 xoş gəlmisiniz. Bu həftə yeddi sonu. Belə ki, son dəfə xatırlayıram, biz başladı biraz daha mürəkkəb baxaraq məlumat strukturlar. İndiyə qədər bu yana, biz bütün həqiqətən idi bizim sərəncamında bu, bir sıra idi. Amma biz serialın imtina kimi deyil, əvvəl bütün maraqlı, hansı həqiqətən Əslində, bəzi nə edilir Bu sadə məlumatların müsbət strukturu indiyə qədər? Bu yaxşı nədir? İndiyə qədər gördük kimi? Nə var? Heç bir şey. TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Nə o? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Sabit ölçüsü. OK, belə ki, niyə sabit ölçüsü olsa yaxşıdır? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: OK, belə ki, səmərəli var bir ayrılması bilər ki, mənada kosmik sabit məbləğ, hansı inşallah dəqiq çox yer istədiyiniz kimi. Belə ki, tamamilə bir plus ola bilər. Bir sıra digər up tərəfi nədir? Bəli? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Bütün - üzr? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: yaddaş Bütün qutuları və ya bir-birinə yanında. Və faydalı var - niyə? Bu çox doğru. Amma necə ki, həqiqət istifadə edə bilər? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Məhz, biz takip edə bilərsiniz hər şey yalnız bilerek olduğu bir yəni ünvanı, yerləşdiyi ünvan yaddaş ki yığın ilk byte. Və ya simli halda, ilk ünvanı ki, simli ildə karakter. Və orada, biz tapa bilərsiniz simli sonunda. Biz ikinci element ki, tapa bilərsiniz Üçüncü element, və s. Və izah belə xülya yolu xüsusiyyət Diziler bizə ki, rasgele erişim. Yalnız kvadrat mötərizə istifadə edərək, notation və bir sıra, siz atlayabilir serialın müəyyən bir element daimi vaxt, böyük O bir, belə danışmaq. Lakin bəzi downsides olub. Bir sıra çox asanlıqla nə deyil? Bu yaxşı nə deyil? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Nə o? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: ölçüsü genişləndirilməsi. Ki, serialın downsides ki nə dəqiq əks upsides var. Belə ki, downsides biri bir sabit ölçüsü var. Beləliklə, siz, həqiqətən, inkişaf edə bilməz. Siz böyük bir yığın təkrar bölüşdürə bilər yaddaş, sonra köhnə elementləri hərəkət yeni massivinə. Və sonra pulsuz köhnə dizi, Məsələn, malloc və ya oxşar istifadə edərək, realloc adlı funksiyası olan reallocates yaddaş. Realloc bir kənara kimi, sizə vermək çalışır serialın yanında olduğunu yaddaş Əgər siz artıq var. Amma bu şeyi hərəkət edə bilər cəmi ətrafında. Amma qısa ki, sağ, bahalı? Çünki siz yaddaş bir yığın varsa Bu ölçüsü, ancaq həqiqətən bir istəyirəm Bu ölçüsü, və qorumaq istəyirsinizsə orijinal elementləri var təxminən xətti vaxt çıxarmaq prosesi ki, nə lazımdır yeni köhnə array. Və reallıq əməliyyat istiyor təkrar sistemi və yenə yaddaş böyük chunks başlaya bilər eləcə də bir müddət başa. Belə ki, xeyir-dua və lənət, həm də var , faktı ört-basdır bu seriallarda sabit ölçüsü var. Amma biz əvəzinə bir şey təqdim əgər bu kimi hansı bir bağlı deyilən siyahısı, biz bir neçə upsides almaq və bir neçə burada downsides həmçinin. Bir bağlı siyahı sadəcə bir məlumat belə strukturu C structs təşkil bir struct, geri, yalnız olduğu halda, bir və ya daha spesifik üçün konteyner dəyişənlərin növləri. Bu halda, nə məlumat növləri etmək ki, struct daxilində görünür ki, Sonuncu dəfə biz bir node deyilən? Bu düzbucaqlı hər bir node edir. Və kiçik düzbucaqlı hər onun daxilində bir məlumat növüdür. Biz nə növ demək idi Onlar bazar ertəsi idi? Bəli? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: A dəyişən və bir pointer, və ya Daha konkret desək, bir int, n, və altındakı bir göstərici. O həm də, 32 bit olmaq nə Bu CS50 kimi kompüter üzrə ən Appliance və onlar etdiyiniz belə ölçüsü bərabər etmişdir. Yaxşı pointer istifadə yəqin üçün necə? Diziler zaman niyə indi bu arrow əlavə belə gözəl və təmiz və sadə? Göstərici üçün nə edir bizə bu qovşaqlarının hər? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Eynilə elə. Harada belirten oldu növbəti biridir. Beləliklə, mən növ ilə analogiya istifadə və düzmək üçün bir mövzu istifadə birlikdə bu qovşaqlarının Mövzu. Və biz yapýyorsun dəqiq nə var göstəricilərinə çünki bu hər yaddaş chunks ola bilər və ya bitişik, geri geri geri RAM daxilində, çünki hər zaman malloc deyərək zəng, mənə kifayət qədər vermək Yeni node üçün bytes, bu güc Burada olmaq və ya burada ola bilər. Burada ola bilər. Burada ola bilər. Siz yalnız bilmirəm. Amma ünvanlarda göstəricilərinə istifadə o qovşaqlarının, siz stitch onlara bilər birlikdə vizual görünür ki, bir yol bu şeyi, hətta əgər bir siyahı kimi bütün bir və ya həyata yayılmışdır Sizin iki və ya RAM sizin dörd qiqabayt öz kompüter daxilində. , Sonra, İşin mənfi tərəfi odur Belə ki, bir bağlı siyahı nədir? Biz istəyirik qiymət nedir yəqin ödəyən? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: daha çox yer, sağ? Biz bu halda, məbləği iki dəfə etdik kosmik biz getdi sonra, çünki hər biri üçün hər node üçün 32 bit olan int, indi biz 64 bit çünki eləcə də bir göstərici ətrafında saxlamaq. Daha çox səmərəliliyi almaq struct əgər Bu sadə şey böyükdür. Həqiqətən daxilində bir tələbə varsa olan strings bir neçə üçün adı və ev, bəlkə bir şəxsiyyət nömrəsi, cəmi bəlkə bəzi digər sahələrdə. Böyük bir kifayət qədər struct varsa, onda bəlkə göstərici dəyəri belə böyük. Bu bir künc işin bir az biz belə bir sadə primitiv saxlanılması edirik bağlı siyahı daxilində. Amma baxımından eynidir. Siz mütləq daha çox sərf edirik yaddaş, lakin siz əldə etdiyiniz rahatlıq. İndi bir element əlavə etmək istəyirsinizsə Çünki Bu siyahının başında, Yeni node ayırmaq lazımdır. Və mən yalnız yeniləmə var yalnız hərəkət birtəhər oxlar ətrafında bir göstəricilərinə. Mən bir şey əlavə etmək istəyirsinizsə siyahısının orta, mən yoxdur Biz nə kimi kənara hər kəs təkan Bizim könüllüləri ilə həftə keçmiş olan bir sıra təmsil. Mən yalnız bir yeni node ayrılması bilər sonra yalnız okları qeyd müxtəlif istiqamətlərdə deyil, çünki faktiki qalmaq üçün Mən tərtib etdiyiniz kimi yaddaş əsl xətt burada ekranda bu. Və sonra nəhayət, siz əlavə etmək istəyirsinizsə siyahının sonunda bir şey, bu, daha asan. Bu, ixtiyari notation növ edir lakin 34-nin pointer, bir tahmin edir. Ən çox onun göstərici dəyəri nədir köhnə kimi ehtimal tərtib sort orada məktəb antenna? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Bu, yəqin ki null var. And olsun ki, bir müəllif null nümayəndəliyi. Çünki siz tamamilə Və null var bilmək lazımdır bir bağlı sonunda siyahısı aşağıdakı saxlamaq deyə, və Bu oxlar aşağıdakı və aşağıdakı bəzi zibil dəyəri. Belə null yoxdur ki, demek edəcək 34 saylı hüququ daha çox qovşaqlarının, bu halda. Belə ki, biz həyata keçirə bilər ki, təklif kod bu node. Və biz bu cür gördüm syntax əvvəl. Typedef yalnız yeni növü müəyyən bizə kimi bizə sinonimi verir string char * idi. Bu halda, bu, bizə vermək olacaq stenoqrafiya notation ki struct node yerine kimi yazıla bilər bir çox təmiz olan node. Az ayrıntılı bir çox var. Bir node daxilində yəqin bir int edir adlı n, sonra struct node * olan biz istədik dəqiq nə deməkdir oxlar başqa bir pointer demək eyni data tipli node. Və mən, biz həyata keçirmişik ki, təklif Bu kimi axtarış funksiyası olan İlk baxışdan görünə bilər bir az kompleksi. Lakin bu kontekstdə baxaq. Mənə burada cihaz üzərində gidelim. Mənə zəng bir fayl açmaq edək siyahısı sıfır dot h. Və yalnız müəyyən biz ehtiva yalnız bu məlumat üçün bir an əvvəl gördüm növü node çağırıb. Beləliklə, biz bir dot h fayla gətirdik. Və bir kənara, hətta bu, sanki görmək haqqında olduğunu proqramı bütün ki, kompleks, həqiqətən var bir proqram yazarkən konvensiya çəkmək üçün, data növləri kimi şeylər qoymaq bəzən daxili sizin sabitləri header fayl və mütləq ildə C fayl, əlbəttə zaman proqramları daha böyük və daha böyük almaq, belə ki, üçün, həm də baxmaq harada olduğunu bilirsinizmi bəzi hallarda sənədlərin və ya bu kimi əsasları, üçün bir növü müəyyən. İndi siyahısı sıfır dot açmaq edin c, bir neçə şey qeyd. Bu ən çox bir neçə mövzu faylları daxildir olan biz əvvəl gördüm. O, öz header file daxildir. Və bir kənara kimi, buna görə ikiqat var burada quotes, kimi bucaq fərqli xətt üzərində Mötərizədə ki, Mən orada qeyd etdik? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Bəli belə bir yerli fayl var. Burada öz yerli faylı Belə ki, əgər line 15, məsələn, istifadə ikiqat quotes əvəzinə ki, açılı mötərizələrin. İndi bu maraqlı növüdür. Mən qlobal elan etdik Qeyd edək ki, line 18 Bu proqram dəyişən ilk adlanan bu olan fikir ilk göstərici olacaq Mənim bağlı siyahısında node və mən var Mən var, çünki null başlatılmış faktiki ayrılmayıb hələ yalnız qovşaqlarının. Beləliklə, bu nə biz, pictorially, təmsil şəkil kimi bir an əvvəl gördüm uzaq ki pointer tərəfdən buraxdı. Belə ki, indi ki, pointer ox yoxdur. Bu yerine null edir. Amma bu necə olacaq təmsil İlk faktiki ünvanı Bu siyahıda node. Mən bir qlobal həyata etdik Bütün bu, görəcəksiniz kimi, çünki proqram həyatda həyata etmez mənim üçün bağlıdır siyahısı. İndi mən burada bir neçə prototipləri var. Mən kimi xüsusiyyətləri həyata keçirilməsinə qərar silinməsi, durub, axtarış və traversal - The arasında son yalnız olan gəzmək siyahısı, onun elementlərinin çap. İndi burada mənim əsas gündəlik var. Və biz çox vaxt sərf deyil Bu ildən bu yana ümid, sort edir indi köhnə papaq. Mən, aşağıdakı etmək gidiyorum istifadəçi əməkdaşlıq edir. Bir Belə ki, çap gidiyorum Bu menyu həyata. Və mən bu biçimlendirilmiş etdik cleanly mən biləcəyi kimi. Deməkdir bir istifadəçi növləri, əgər onlar bir şey silmək istəyirəm. Deməkdir iki istifadəçi ki, əgər onlar bir şey əlavə etmək istəyirəm. Və s. Mən təklif gidiyorum sonra bir komanda üçün. Və sonra GetInt istifadə gedirəm. Beləliklə, bu, həqiqətən sadə menuing edir yalnız yazın olduğu interface bir bir sıra mapping bu əmrləri. İndi gözəl təmiz açarı var yandırın olacaq ki, bəyanat istifadəçi kimi daxil yazılmış hər hansı Onlar bir tipli varsa, mən lazımdır silmək zəng və pozub. Onlar iki tipli varsa, mən lazımdır daxil zəng və pozub. İndi hər gətirdik BİLDİRİŞ eyni xətt üzərində bu. Bu yalnız bir üslub qərardır. Adətən biz bir şey gördüm bunu bəyənir. Amma yalnız, səmimi, mənim proqram qərar daha oxunaqlı baxdı, çünki ona yalnız dörd hallarda olmuşdur yalnız bu kimi siyahısı. Stil tamamilə qanuni istifadə. Mən bu belə uzun etmək gidiyorum istifadəçi sıfır tipli deyil, I qərar onlar çıxmaq istəyirik demək olacaq. Belə ki, indi Ben nə hiss burada gedir. Mən yəqin siyahısına pulsuz gedirəm. Bir an ki, lakin daha çox. Ilk bu proqram run edək. Mənə böyük bir terminal edək pəncərə, nöqtə çizgi siyahısı 0. Buna davam və daxil etmək üçün gidiyorum yazaraq iki, indi 50 kimi sayı və siz siyahısına indi 50 görəcəksiniz. Və mətn yalnız biraz kaydırılmış. Belə ki, indi siyahısını ehtiva fark sayı 50. Iki alaraq başqa insert nə edək. Biri kimi sayının yazın edək. Siyahısı artıq 50 izlədi biridir. Bu yalnız bir mətn nümayəndəliyi belə siyahısı. Və nin kimi daha bir sayı daxil bildirin inşallah olan sayı 42, çünki ortada sonuna qədər davam xüsusi növ bu proqram bu edər onları elementləri. Belə ki, orada biz var. Ki, ola bilər Super sadə proqram tamamilə bir sıra istifadə, lakin bir bağlı siyahısını istifadə edərək, üçün baş yalnız mən dinamik bilər böyümək və bu shrink. Belə ki, axtarış bir nəzər edək mən komanda üç run, mən axtarmaq istəyirsinizsə sayı 43, demək üçün. Və heç bir şey yəqin edib, Mən heç bir cavab geri var, çünki. Belə ki, daha bu nə edək. Axtar. 50 və ya daha çox axtarış üçün edək axtarış 42, bir gözəl var az incə mənası. Və mən orada həyatın mənasını tapdı. Əgər bilmirsinizsə sayı 42, istinad, Google. Bütün hüquqlar. Belə ki, nə mənə bu proqram görüb? Bu, yalnız mənə beləliklə əlavə etmək üçün izin verilen elementləri üçün uzaq və axtarış. , Sonra, sürətli irəli edək biz nəzər funksiyası bazar ertəsi iltifat kimi. Bu funksiya Belə ki, mən, axtarış iddia birinci siyahıda bir element bir, istifadəçi isteyen və sonra zəng Faktiki int almaq üçün GetInt sizin üçün axtarış istəyirik. Sonra bu bildiriş. Mən müvəqqəti dəyişən yaratmaq üçün gidiyorum line 188. pointer çağırıb - Ptr - bir şey çağırıb bilər. Və bir node bir göstərici var Mən orada node * bildirib. Və mən ona bərabər olmalıdır başlatılıyor alıram ilk mən səmərəli var ki, barmaq, belə ki, çox haqqında danışmaq siyahısının ilk element. Burada mənim sağ Ptr Ben Belə ki, əgər Eyni şey işarə ilk da işarə edir. Belə ki, indi geri kodunu, Bundan sonra nə olacaq - iterating bu ümumi bir paradiqma edir bir kimi bir quruluş üzərində bağlı siyahısı. Mən isə aşağıdakı gidiyorum pointer Belə null bərabər deyil isə mənim barmaq bir null da işarə deyil dəyəri, pointer arrow n n bərabərdir varsa. Biz n ilk görəcəksiniz nə hər GetInts Yığdığınız istifadəçi burada çağırırıq. Və göstərici arrow n nə deməkdir? Burada şəkil geri Yaxşı, əgər Mən işarə barmağı varsa doqquz də olan ilk node arrow mahiyyətcə ki, getmək deməkdir node və yeri N dəyəri qamarlamaq Bu halda, data sahəsində n çağırıb. Bir kənara kimi - və biz bu neçə gördüm həftə öncə kimsə xahiş zaman - Bu sintaksis yeni, lakin deyil bizə səlahiyyətlər verir ki, artıq yox idi. Istifadə ekvivalent bu söz nə idi dot notation və ulduz bir neçə həftə bundan əvvəl biz geri soyulmuş zaman bu bir az vaxtından əvvəl qat? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Məhz, bu ulduz idi, sonra bu, ulduz dot n oldu burada parantez, hansı görünür, Açığı, mən bir çox hesab edirəm ki, oxumaq daha çox sirli. Lakin ulduz pointer, həmişə olduğu kimi, vasitələri var gedin. Və sonra nə məlumat var, istəyirik alan daxil olmaq istəyirsiniz? Yaxşı siz daxil olmaq üçün dot notation istifadə bir structs data sahəsində, mən xüsusi n istəyirik. Açığı, mən bu iddia edirəm oxumaq yalnız çətindir. Bu harada yadda çətindir parantez ki, getmək yoxdur ulduz və bütün. Belə ki, dünyanın bəzi sintaktik qəbul şəkər, belə danışmaq. Söyləyən Bir sexy yol, bu ekvivalent və bəlkə də daha asan. Pointer həqiqətən bir göstərici olarsa, arrow notation vasitəsilə getmək və tapmaq bu halda sahə n çağırıb. Mən bunu tapmaq Belə ki, mən nə görürsünüz. Mən sadəcə çap I, i tapdı ki, int üçün dəyəri sayede. I növ üçün yalnız bir ikinci yatmaq zəng üçün ekranda fasilə şeyi istifadəçi udmaq üçün ikinci vermək Ne oldu. Və sonra pozub. Əks halda, mən nə etməliyəm? Mən bərabər pointer güncelleyin Növbəti göstərici arrow. Belə ki, yalnız aydın olmaq, bu getmək deməkdir , mənim köhnə məktəb notation orada istifadə edərək. Bu yalnız nə getmək deməkdir Belə ki, Siz çox olaraq, hansı işarə edirik Birinci halda mən işarə alıram edir bu doqquz ilə struct. Belə ki, orada getdi etdik. Və sonra dot notation deməkdir növbəti dəyəri almaq. Amma dəyər, bu tərtib edir, baxmayaraq ki, bir dar kimi, yalnız bir sıra deyil. Bu rəqəmli ünvan var. Olub, kod bu bir xətt Belə ki, , bu kimi yazılı daha sirli yol, və ya bu kimi, bir az daha intuitiv şəkildə, yalnız mənim əl hərəkət deməkdir növbəti bir ilk node ki, sonra və sonra növbəti bir və bir sonrakı və s. Beləliklə, biz digər dayanmaq olmaz daxil edin və silin uygulamalarındaki və traversal, ilk iki olan kifayət qədər cəlb edir. Və mən onu almaq üçün çox asandır edirəm şifahi bunu zaman itirdi. Amma biz burada edə bilərsiniz müəyyən etmək üçün cəhd necə yaxşı vizual bunu. Mən təklif edirəm ki, əgər biz bu dilinə elementləri əlavə etmək istəyirəm Mövcud siyahısı, hansı beş elementlər vardır - 9, 17, 22, 26 və 33 - Mən bu həyata keçirəcəyik, əgər kodu, mən getmək necə nəzərə almaq lazımdır Bunu haqqında. Və mən körpə addımlar təklif edir Bu halda demək vasitəsi, nə mümkün ssenariləri ki, ümumi qarşılaşa bilər? Bağlantılı üçün daxil həyata keçirilərkən siyahısı, bu, yalnız olmaq olur ölçüsü beş xüsusi nümunəsidir. Əgər bir rəqəm daxil etmək istəyirəm yaxşı, əgər bir nömrəli demək istəyirəm və harada, sorted asayişin qorunması açıq-aydın bir ehtiyac sayı yoxdur bu nümunə getmək? Əvvəlinə kimi. Amma maraqlı nə var Bu daxil bir əlavə etmək istəyirsinizsə, siyahısı, nə xüsusi pointer lazımdır yəqin aydınlıq olmalıdır? Birinci. Beləliklə, mən bu ilk halda, iddia edirəm biz, hesab edə bilərsiniz ki, da daxil cəlb ssenari siyahının başında. Hətta bir qədər asan və ya bəlkə yoluq-yoluq edək asan halda, nisbətən danışan. Mən əlavə etmək istəyirəm Güman sorted üçün sayı 35. Bu açıq-aydın orada məxsusdur. Yaxşı göstərici açıq-aydın gedir ki, ssenari yenilənir lazımdır? 34-nin göstərici null deyil çevrilir lakin struct yerləşdiyi ünvan sayı 35 olan. Belə ki, bu halda iki var. Belə ki, artıq mən quantizing növ Ben Mən burada nə qədər çalışır. Və nəhayət, açıq-aydın ortada olduğu Həqiqətən, ortasında, əgər mən istəyirəm gedir ki, 23 kimi bir şey daxil 23 və 26 arasında, lakin indi hər şeyi bir az daha çox almaq cəlb çünki nə göstəricilərinə dəyişdirilə lazımdır? 22 açıq-aydın dəyişdirilə lazımdır Belə ki, O, artıq 26-qeyd bilməz. O, yeni node qeyd etmək lazımdır ki, Mən zəng ayrılması lazımdır malloc və ya bir ekvivalent. Amma sonra mən də ki, yeni node, 23 ehtiyac Bu halda, onun pointer var kimə də işarə? 26. Və bir olmalıdır gedir Burada əməliyyatlar üçün. Çünki mən ağılsızlıq bunu, mən əgər əvvəlində misal başlamaq üçün siyahısı və mənim qol 23 daxil etməkdir. Və mən bunu aid edir, yoxlamaq Burada doqquz yaxın? No Bu 17 növbəti, burada məxsusdur mu? No O, 22 yanındakı burada məxsusdur mu? Bəli. İndi mən burada axmaq Ben əgər deyil, Bu vasitəsilə düşüncə, mən güc 23 Yeni node ayırırlar. Mən göstərici yeniləmə bilər node işarə edərək, 22 çağırıb bu yeni node edir. Və sonra yeniləmə nə var Yeni node in göstərici olacaq? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Eynilə elə. 26 işarə edərək. Mən artıq verməmişdir Amma əgər dammit 22-nin göstərici bu oğlan da qeyd və İndi yetimlər, istirahət siyahı, belə danışmaq. Burada əməliyyatların Belə sifarişi əhəmiyyətli olacaq. Bunu etmək üçün, mən oğurlamaq bilər , altı könüllü deyirlər. Və biz bunu edə bilərsiniz Bakalým vizual əvəzinə kod müdrik. Və biz bir sevimli stress var Bu gün sizin üçün top. OK, haqqında bir, iki, də Geri - orada sonunda. Siz də üç, dörd, sonunda uşaqlar. Və beş, altı. Əmin olun. Beş və altı. Bütün hüquqlar və biz gələcəyik! Siz uşaqlar üçün növbəti dəfə. Bütün hüquqlar qədər gəlib. Bütün sağ, burada ilk istəyirik yana, Siz yöndəmsiz bir olmaq istəyirəm Burada Google şüşə? Bütün sağ, belə, OK, Cam, bir video qeyd edin. OK, siz getmək iyi. Bütün sağ, belə ki, uşaqlar üzərində gəlmək bilər Burada əvvəlcədən hazırlamışıq bir ədəd. Bütün sağ, burada gəlib. Və niyə bir az getmirlər daha yol. Və nin görək, adınız nədir, Google Glass ilə? TƏLƏBƏ: Ben. HOPARLÖR 1: Ben? OK, Ben, siz sözün birinci olacaq. Beləliklə, biz göndərmək olacaq səhnə sonuna. Bütün sağ, və adı? TƏLƏBƏ: Jason. HOPARLÖR 1: Jason, OK will sayı doqquz ola bilər. Siz Ben o yolla istəyirəm əgər. TƏLƏBƏ: Jill. HOPARLÖR 1: Jill, siz olacaq 17, I daha çox işlər etsəniz ağıllı, mən var ki, digər sonunda başladı. Bilirsiniz ki, yol getmək. 22. Və siz? TƏLƏBƏ: Mary. HOPARLÖR 1: Mary, siz 22 olacaq. Və adı? TƏLƏBƏ: Chris. HOPARLÖR 1: Chris, siz 26 olacaq. Və sonra son. TƏLƏBƏ: Diana. HOPARLÖR 1: Diana, siz 34 olacaq. Belə ki, burada gəlib. Bütün sağ, belə sıralanır təkmilləşdirilməsi artıq sifariş. Və nin irəli getmək və bunu bildirin belə ki, biz, həqiqətən bilər - Ben siz axtarır yalnız cür istəyirik həyata heç bir yerdə orada daxil. OK, belə ki, in irəli getmək və bu təsvir edək Mən çox istəyirəm, silah istifadə edərək, dəqiq, neler. Belə ki, davam və özünüzü ver ayaq və ya aranızdakı iki. Və bir tərəfdən ilə davam və qeyd sizə kim işarə edilməlidir bu əsaslanır. Siz null əgər və yalnız qeyd düz aşağı mərtəbə. OK, belə yaxşı. Belə ki, indi biz bir bağlı siyahı var və mənə bildirin Mən rolunu oynamaq lazımdır ki, təklif Ptr, mən narahat deyil ətrafında bu balans. Və sonra - kimsə axmaq Konvensiyası - istədiyiniz bu bir zəng edə bilərsiniz - sələfi göstərici proqnozu pointer - yalnız biz verdi ləqəb var mənim sol tərəfdən Örnek kodu. Saxlanılması olacaq ki, digər tərəfdən olan olan takip ssenari aşağıdakı. Belə ki, ilk, mən off dərmək istəyirəm, güman daxil olduğunu ilk nümunəsi, demək 20 siyahısına daxil. Beləliklə, mən kimsə lazımdır gidiyorum bizim üçün sayı 20 etdirir. Beləliklə, mən malloc kimsə lazımdır tamaşaçı. Up Hadi. Sizin adınız nədir? TƏLƏBƏ: Brian. HOPARLÖR 1: Brian, bütün sağ, belə ki, 20 olan node olmalıdır. Bütün sağ, burada gəlib. Və təbii ki, burada Brian aid edir? Belə ki, ortasında - faktiki olaraq, bir dəqiqə gözləyin. Biz üçün bu həyata edirik. Biz bir çox çətindir bu edirik Bu ilk olmalıdır edir. OK, biz pulsuz Brian olacaq və beş realloc Brian. OK, belə ki, indi biz daxil istəyirik Beş Brian. Belə ki, yanında buraya gəlib Yalnız bir an Ben. Və ehtimalla deyə bilərsiniz Bu hekayə gedir yerləşir. Lakin edək haqqında diqqətlə düşünmək əməliyyatları üçün. Və məhz bu vizual var sıralamaq olacaq ki, ki, örnek kod ilə. Belə ki, burada mən Ptr əvvəlcə işarə var deyil per se Ben,, lakin hər hansı bir at O, ehtiva dəyəri bu halda deyil - adınız yenidən var? TƏLƏBƏ: Jason. HOPARLÖR 1: Jason, Ben və mən də belə Hal-hazırda Jason da işarə. Belə ki, indi müəyyən etmək üçün var, Brian Ü aid edir? Tək şey Beləliklə, mən etmək imkanı var İndi onun n data item edir. Buna görə yoxlamaq gidiyorum Jason daha Brian az? Cavab doğrudur. Beləliklə, nə indi, nə etmək lazımdır düzgün qaydada? Mən neçə göstəricilərinə güncellemeniz lazımdır Bu hekayə cəmi? Mənim əl hələ də işarə edir Harada Jason, və əl - Əgər istəyirsinizsə növ kimi sizin əl qoymaq, mən bir sual işarəsi bilmirəm. OK, yaxşı. Bütün sağ, siz belə bir neçə namizəd. Ben yaxud I və ya Brian ya Jason Ya başqa və ya hər kəs, hansı göstəricilərinə dəyişdirmək lazımdır? Necə ümumi bir çox? OK, belə ki, iki. Mənim göstərici həqiqətən artıq etməz Mən yalnız müvəqqəti Ben çünki. Belə ki, ehtimalla, bu iki uşaqlar var Ben və Brian də. Beləliklə, biz yeniləmə ki, mənə təklif edək Ben, ildən ilk var. Bu siyahıda ilk element indi Brian olacaq. Brian belə Ben nöqtə. OK, indi nə? Kim da qeyd edilir? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: OK belə Brian var Jason da qeyd etmək. Amma pointer izini itirmiş? Jason harada mən bilirsinizmi? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Ben çünki mən, nə müvəqqəti göstərici. Və ehtimalla, mən dəyişməyib Yeni node da qeyd etmək. Beləliklə, biz sadəcə Brian nöqtəsi ola bilər kim mən də işarə edirəm. Və biz tamamlayın. Belə halda biri də durub siyahı əvvəli. Iki əsas addım var idi. Bir, biz Ben yeniləmək üçün var, və sonra biz də Brian yeniləmək lazımdır. Və sonra mən narahat yoxdur geri qalan vasitəsilə traipsing Biz artıq aşkar siyahısı, çünki onun O məxsus yer, çünki ilk element sol. Bütün sağ, belə olduqca sadə. Biz demək olar ki, etdiyiniz kimi, əslində, hiss Bu çox mürəkkəb edir. Belə ki, indi sonunda yoluq-yoluq bildirin siyahısı, və harada görmək mürəkkəbliyi başlayır. Tamaşaçı Belə ki, indi, mən alloc. Hər kəs 55 oynamaq istəyirsiniz? Bütün sağ, mən ilk əl gördüm. Up Hadi. Bəli. Sizin adınız nədir? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Habata. OK qədər gəlib. Siz sayı 55 olacaq. Beləliklə, siz, əlbəttə, məxsusdur siyahının sonunda. Elə mənimlə simulyasiya replay imkan yalnız bir an Ptr olan. Beləliklə, mən ilk qeyd etmək gidiyorum Ben-da işarə edir nə. Biz indi Brian da işarə edirik də. Belə ki, 55-dən az beş deyil. Belə ki, I özümü yeniləmək üçün gidiyorum Brian növbəti göstərici işarə edən İndi əlbəttə Jason edir. 55 belə az doqquz deyil Mən Ptr yeniləmək üçün gedirəm. Mən Ptr yeniləmək üçün gedirəm. Mən Ptr yeniləmək üçün gidiyorum Mən Ptr yeniləmək üçün gedir. Və mən gedirəm - hmm, ne adınız yenidən? TƏLƏBƏ: Diana. HOPARLÖR 1: Diana işarə edir, əlbəttə, onun sol əli ilə null edir. Beləliklə, harada Habata əslində yoxdur aydın məxsusdur? Sola, burada. Belə ki, necə mən burada onun qoymaq üçün bilmirəm Mən qədər berbat sonra hesab edirəm. Nə Ptr incəsənət Çünki vaxt bu an? Null. Belə olsa da, vizual, biz açıq-aydın bütün bunlar bax burada səhnəyə uşaqlar. Mən əvvəlki track saxlanılır deyil etdik Siyahıda şəxs. Mən işarə barmağı yoxdur Bu halda, node sayı 34. Elə həqiqətən bu artıq başlamaq bildirin. Belə ki, indi mən, həqiqətən lazımdır ikinci yerli dəyişən. Və bu siz görürsünüz nə faktiki nümunə C kodu kimi mən getmək harada, Mən qeyd etmək mənim sağ yeniləmə zaman Jason, bununla mən geridə Brian tərk daha mənim sol tərəfdən istifadə edərək başlamaq Mən harada getmək kimi ki, yeniləmə Bu siyahıda vasitəsilə - daha yöndəmsiz I nəzərdə dən indi burada vizual - Mən almaq üçün gidiyorum siyahısı sonu. Bu tərəfdən olduqca ki, hələ null edir göstərmək üçün başqa faydasız Mən siyahının sonunda aydın Ben amma indi ən azı mən bu var sələfi göstərici Belə ki, burada işarə indi nə əllər və nə göstəricilərinə lazımdır aydınlıq olmalıdır? Kimin tərəfdən istəyirsiniz ilk reconfigure? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: OK, Diana belə. Harada qeyd etmək istəyirəm At Diana sol pointer? 55, güman ki, belə biz daxil etdik. Və harada 55 pointer getmək lazımdır? Down, null etdirir. Və mənim əlləri, bu nöqtədə deyil Onlar yalnız, çünki Fərq müvəqqəti dəyişənlər. Belə ki, indi biz tamamlayın. Belə ki, əlavə var mürəkkəbliyi - və ki, həyata ki, çətin deyil lakin biz etmək üçün orta dəyişən lazımdır əmin mən sağa hərəkət əvvəl əl, mən sol dəyəri yeniləmək tərəfdən proqnozu bu halda pointer, belə ki, Mən arxada göstərici var ki, Mən harada takip. İndi bir kənara kimi, bu düşünür istəyirsinizsə bu kimi vasitəsilə bu hiss bir saxlamaq üçün az annoying bu sol tərəfdən baxın. Nə başqa bir həll ki, Bu problemin olub? Veri yeniden tasarlarken var, əgər biz danışıqlar strukturu İndi vasitəsilə? Bu yalnız cür bir az hiss edin kimi, iki göstəricilərinə malik annoying başqa edən siyahısını bilər gedir ideal dünyada, saxlamışlar biz lazımdır ki, informasiya? Bəli? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Eynilə elə. Sağ belə maraqlı həqiqətən var bir fikir rüşeymləri. Və əvvəlki göstərici bu fikir, əvvəlki element də işarə. Mən yalnız təcəssüm ki, əgər siyahısını özü daxilində? Və görüntüləmək üçün çətin olacaq Bu, bütün kağız olmadan yerə düşür. Lakin bu uşaqlar də istifadə edirlər ki, əllərini bir əvvəlki var bununla pointer və sonrakı göstərici biz ikiqat arayacaðým nə həyata bağlı siyahısı. Ki, mənə geri növ imkan verir daha asanlıqla mənə olmadan, proqramçı saxlamaq üçün olan əl Track - həqiqətən əl - Mən əvvəllər olmuşdu harada Siyahıda. Belə ki, etməyəcək. Ki, çünki Biz bu sadə davam edəcəyik iki dəfə kimi bir qiymətə gəlib gedir ki göstəricilərinə üçün çox yer, Bir ikinci istəyirsinizsə. Amma bu, doğrudan da yaygın data strukturu kimi tanınan ikiqat siyahısı bağlıdır. Burada son misal etmək və qoymaq edək onların həyatlarının həyata bu uşaqlar. Malloc 20 belə. Orada koridorda qədər Hadi. Bütün sağ, adınız nədir? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Pardon? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Demeron? OK qədər gəlib. 20 olmalıdır. Siz açıq-aydın edir 17 və 22 arasında məxsusdur. Belə ki, mənə dərs bildirin. Mən göstərici başlamaq üçün gidiyorum Brian da işarə. Mən sol əl üçün gidiyorum Mən hərəkət kimi yalnız Brian yeniləmə Jason, yoxlanılması doqquz 20-dən az edir? No 17 20-dən azdır? No 22 20-dən azdır? Bəli. Beləliklə, nə göstəricilərinə və ya əlləri dəyişdirmək lazımdır onlar indi işarə edirik? Beləliklə, biz 20 işarə 17 edə bilərsiniz. Belə ki, gözəl. Biz qeyd etmək istəyirik Sizin pointer indi? 22. 22 Harada və yenə, thanks bilirik mənim müvəqqəti göstərici üçün. Beləliklə, biz OK orada istəyirik. Belə ki, çünki bu müvəqqəti saxlama Mən hər kəs olduğu takip saxlanılır etdik. İndi siz vizual yerləşir daxil edə bilərsiniz Siz məxsusdur və indi 1, 2, 3, ehtiyac 4, 5, 6, 7, 8, 9 stress top, və alqışlarla bir dəyirmi Bu uşaqlar, biz bilər. Qəşəng edilir. [Alqış] HOPARLÖR 1: Yaxşı. Və ədəd saxlaya bilər mementos kimi kağız. Bütün sağ, belə ki, bir çox var mənə etibar asan ilə vasitəsilə gəzmək faktiki kodu ilə daha insanlar. Amma nə bir an tapa bilərsiniz İndi ki, eyni - oh, təşəkkür edirəm. Təşəkkür edirik - siz eyni məlumat tapa bilərsiniz ki, strukturu, bir bağlı siyahı əslində bilər daha bir bina blok kimi istifadə edilə müasir data strukturlar. Və burada da mövzu dərk edir ki, biz tamamilə daha təqdim etdik yerinə mürəkkəbliyi Bu alqoritm. Durub, və biz onun vasitəsilə gedib, silinməsi və axtarış, bir az bu daha mürəkkəb bir sıra idi. Amma biz bir dinamizm qazanmaq. Biz adaptiv data structure almaq. Ancaq yenə də, bəzi olan bir qiymət ödəmək əlavə mürəkkəbliyi, həm də bunu həyata keçirir. Və biz rasgele erişim imtina edirik. Və vicdanlı olmaq, bəzi gözəl mövcud deyil slide təmiz Mən sizə verə bilər ki, burada deyir niyə bağlıdır siyahısı bir sıra daha yaxşıdır. Və onu buraxın. Mövzusunda, hətta indi reoccurring Çünki daha belə önümüzdəki həftə edir mütləq yoxdur ki, doğru cavab. Biz ayrı-ayrı ox niyə bu problem kümeleri üçün dizayn. Bu, çox kontekstində həssas olacaq Bu məlumatdan istifadə etmək istəyirəm olub strukturu və ya bir və olacaq baxımından sizə məsələ nə asılıdır resursları və mürəkkəblik. Amma mənə təklif edək ki, ideal data strukturu, müqəddəs grail olacağını daimi vaxt ki, bir şey, asılı olmayaraq, çox şeylər necə bu, daxili, gözəl ola bilməz ki, bir halda data structure cavab döndü daimi vaxt. Bəli. Bu söz üçün böyük lüğət edir. Və ya heç bu söz deyil. Yoxsa, hər hansı bu cür problem. Yaxşı görək biz ən azı əgər ki, doğru bir addım atmaq. Mənə bir yeni məlumatlar strukturu təklif edək ki, müxtəlif şeylər üçün istifadə edilə bilər, Bu halda bir hash masa çağırıb. Və belə ki, biz salan geri həqiqətən istəyirik bir bu halda dizi,, və qədər özbaşına, bu tərtib etdik bir növ ilə bir sıra kimi hash table iki ölçülü Array - daha doğrusu bir iki burada təsvir var ölçülü Array - ancaq bu yalnız Belə ölçüsü 26 bir sıra ki, əgər biz serialın masa, masa bracket zəng sıfır üst düzbucaqlı edir. Cədvəl bracket 25 düzbucaqlı edir alt. Bu Mən data çəkmək bilər necə Mən saxlamaq istədiyiniz strukturu insanların adları. Belə ki, məsələn, mən də cəlb edəcək burada hava haqqında bütün şey, əgər mən İndi gedirəm bu array var idi, bir hash masa zəng və bu, yenə yeri sıfır. Burada yeri, bir, və s. Mən bu məlumatdan istifadə etmək istəyirəm ki, iddia strukturu, müzakirə naminə, insanların adları saxlamaq üçün, Alice və Bob və Charlie və digər bu kimi adlar. Belə ki, başlanğıclar kimi indi bu hesab Bir lüğət, demək ki, sözləri çox. Onlar adları nə Burada nümunə. Və bu, bəlkə də, bütün çox ilgili edir biz, bir yazım checker həyata problem üçün altı müəyyən edə bilər. Biz ümumi ölçüsü 26 bir sıra var Belə ki, əgər Bu 25-ci yeri, belə ki, alt və mən Alice olduğunu iddia lüğətini ilk sözü Mən RAM daxil istəyirəm ki, adları, Bu data strukturu, harada var belirten instinktlərdən ki, Alice adı bu sıra getmək lazımdır? Biz 26 variantları var. Biz öz qoymaq istəyirik harada? Biz bracket sıfır onun istəyirsiniz mi? Alice üçün, ki, sıfır zəng edək. Və b biri olacaq və C iki olacaq. Beləliklə, biz yazmaq olacaq Burada Alice adı up. Sonra Bob onun daxil edin adı burada gedəcək. Charlie burada gedəcək. Və s down vasitəsilə Bu data quruluşu. Bu gözəl data strukturu. Niyə? Quyunun çalışan zaman nə bu bir insan adı daxil İndi data structure? Bu cədvəldə həyata keçirilir olduğunu nəzərə alaraq, həqiqətən, bir sıra kimi. Yaxşı daimi vaxt var. Bu, bir qaydası var. Niyə? Yaxşı necə müəyyən edirsiniz Alice aid olduğu? Siz onun adı olan məktub baxmaq? İlk. Bir string varsa və siz orada əldə edə bilərsiniz yalnız simli baxaraq bracket sıfır. Ki, simli zeroth xarakteri belə. Bu çox asandır. Biz gizli ki, etdi təyin həftə əvvəl. Və sonra bir dəfə ki, Alice bilirik məktub kapital, biz çıxmaq bilər 65 və ya kapital A özü, off ki, sıfır verir. Beləliklə, biz indi Alice məxsusdur bilirik ki, yeri sıfır. Bu data göstərici verilir strukturu, bir növ, nə qədər görür o yeri tapmaq üçün mənə almaq bir sıra sıfıra? Yalnız bir addım, doğru daimi vaxt təsadüfi giriş çünki biz Təklif olunan bir sıra bir xüsusiyyət idi. Belə ki, qısa, figuring nə indeksi ALICE adını, olan deyil Bu halda, A, və ya edək yalnız həll sıfır olduğu B biridir və C ki, iki ki, figuring daimi dəfə. Mən yalnız onun ilk məktub baxmalıyıq sıfır olduğu figuring bir array də daimi dəfə. Belə ki, texniki var İndi iki addımlar kimi. Amma hələ də daimi deyil. Beləliklə, biz bir böyük O zəng ki, biz var Bu cədvəl daxil Alice daxil daimi vaxt. Amma əlbəttə, mən olan alıram burada sadəlövh, sağ? Nə sinif bir Aaron var əgər? Və ya Alicia? Və ya hər hansı digər adları ilə başlayan A. Biz qoymaq üçün gedir həmin şəxs, sağ? Mən demək, hazırda yalnız üç var masa insanlar, belə ki, bəlkə biz yer Aaron qoymalıdır sıfır bir iki üç. Sağ, burada A qoymaq bilər. Lakin sonra, biz daxil David əlavə etmək üçün cəhd edin Bu siyahıda, David nereye gidiyor? İndi bizim sistem qırılma başlayır aşağı, sağ? İndi David burada bitir Çünki Aaron burada əslində əgər. Malik və artıq bu bütün fikir bizə verir ki, təmiz data structure daimi vaxt insertions artıq Mən çünki daimi vaxt, yoxlamaq, oh, damnit, kimsə artıq var Alice in yerdə. Mənə Bu data qalan sonda edək strukturu, qoymaq üçün bir ləkə axtarır Harunun adı kimi kimsə. Və buna görə də başlayır ki, xətti vaxt. Bundan əlavə, indi tapmaq istəyirsinizsə, Bu data tərkibində Harun və siz yoxlamaq və Harunun adı burada deyil. İdeal halda, yalnız Harunun deyərdim deyil data strukturunda. Amma əgər üçün otaq edilməsi başlamaq Harun bir D olmalı idi və ya E, siz, ən pis halda, yoxlamaq üçün olan bütün məlumat strukturu, bir şey daxil devolves bu halda masanın ölçüsü xətti. Bütün sağ Belə ki, mən bu düzeltmek lazımdır. Burada problem var idi ki, Bu array 26 elementləri. Mənə dəyişdirmək edək. Whoops. Daha çox olan, belə ki, mənə dəyişdirmək imkan cəmi ölçüsü 26, alt qeyd index n mənfi 1 dəyişdirmək üçün gedir. 26 insanların üçün aydın çox kiçik deyil adları, çünki minlərlə var Dünyanın adları, ədalətli edək 100 və ya 1000 və ya 10,000 edir. Ədalətli bir çox yer ayırmağa edək. Yaxşı mütləq azaltmaq deyil ki, iki olmayacaq ehtimalı adları ilə insanlar ilə başlayan və belə ki, siz qoymaq üçün cəhd gedirdi hələ yeri sıfır adları. Onlar hələ toqquşmaq olacaq olan biz hələ qoymaq üçün bir həll lazımdır deməkdir Alice və Harunun və Alicia və digər A başqa yerdə ilə başlayan adlar. Amma bu nə qədər problem var? Ehtimalı nədir ki, bir məlumatları toqquşma var bu kimi strukturu? Yaxşı, mənə bildirin - biz geri gəlmək lazımdır Burada sual. Və necə ola bilər baxmaq ilk həll edir. Məni bura bu təklifi qoparmaq edək. Biz yalnız təsvir bir alqoritmi belədir xətti adlı bir Heuristic Siz daxil cəhd əgər vasitəsi probing Bu data burada bir şey bir hash masa adlanan strukturu, və heç bir otaq var var həqiqətən data structure sonda yoxlanılması, bu mümkündür? Bu mövcud bu mümkün mü? Bu mövcud? Və nəhayət olduqda, siz daxil siz ilk nəzərdə ki, adı başqa yerdə ki, yer. Amma pis halda, yalnız spot məlumatların çox aşağı ola bilər strukturu, serialın çox sonunda. Belə ki, xətti, ən pis halda, probing, xətti alqoritm daxil devolves yerləşir Aaron, keçən daxil edilməlidir olur Bu data strukturu, o, güc Bu ilk yeri ilə toqquşmaq, lakin sonra çox sonunda pis luck ilə başa. Beləliklə, bu daimi deyil bizim üçün vaxt müqəddəs grail. Daxil elementlərinin Bu yanaşma nəzərə məlumat strukturu hash çağırıb masa daimi dəfə görünmür ən azı ümumi halda. Bu xətti bir şey qalmaq bilər. Biz toqquşma həll Yaxşı, əgər qədər fərqli? Belə ki, burada daha təcrübəli var hələ nə müraciət bir hash masa çağırıb. Və hash ilə bir kənara, nə kimi Hesab edirəm ki, index demək Mən əvvəllər edilir. Etmək üçün hash bir şey ola bilər bir verb kimi düşündüm. Əgər hash Alice bir adı var Belə ki, bir hash funksiyası, belə danışmaq, bir sıra qaytarmalıdır. O da məxsusdur Bu halda əgər sıfır o da aiddir, əgər yeri sıfır, bir yeri bir, və s. Belə ki, mənim hash funksiyası belə uzaq olub super sadə, yalnız baxaraq Birinin adı ilk məktubu. Amma hash funksiyası kimi görür input data bir parça, bir simli, bir int, nə. Və adətən bir sıra spits. Və ki sayı olduğu məlumatlar element data structure məxsusdur bir hash masa kimi burada bilinir. Belə ki, yalnız daxilən, bu, az fərqli kontekstində. Bu əslində bir nümunə istinad cəlb ad günü olduğu kimi bir çox ola bilər Ay 31 gün. Lakin bu şəxs nə qərar verdiniz bir toqquşma halında nə? Context indi bir toqquşma olmayan adları, lakin ad günləri toqquşma, iki nəfər eyni ad varsa Məsələn oktyabr 2-ci. TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Bəli, belə ki, burada biz bağlı siyahılarının yararlanarak. Belə ki, fərqli bir az görünür biz əvvəllər cəlb edir. Amma biz bir sıra üçün görünür sol tərəfində. Bu heç, bir index var xüsusi səbəb. Amma hələ bir sıra var. Bu göstəricilər bir sıra var. Və hər bir bu elementlərin hər biri Bu dairələr və ya slashes - Bu çizgi təmsil null - bu hər göstəricilərinə yəqin işarə edir nə data structure? A bağlıdır siyahısı. Belə ki, indi biz imkanı var bizim proqram ağır kodu Tablonun ölçüsü. Bu halda, biz heç vaxt olduğunu bilirik bir ay çox 31 gün. Belə ağır 31 kimi bir dəyəri coding Bu kontekstdə müvafiq. Adları kontekstində, ağır kodlaşdırma 26 əsassız deyil insanların adları yalnız, məsələn, ilə başlamaq Z. vasitəsilə cəlb əlifbası Biz ki, data onları bütün CRAM bilər strukturu belə uzun biz zaman kimi toqquşma, biz burada adları qoymaq deyil, yerine bu hüceyrələr hesab deyil strings özləri, lakin kimi Məsələn, Alice göstəricilərinə. Və sonra Alice başqa bir pointer ola bilər ilə başlayan başqa adı A. Və Bob həqiqətən burada üzərində gedir. Və başlanğıc başqa bir ad var, əgər B ilə, o burada bitər. Və belə bu elementlərin hər birindən biz bu nəzərdə əgər masa iki, az daha ağıllı - gəlib - Biz bu bir az daha nəzərdə əgər ağılla, indi bir adaptiv data çevrilir heç bir ağır limit var olduğu quruluşu, Siz əlavə edə bilərsiniz neçə elementləri onu Əgər çünki bir toqquşma ki, gözəl. Yalnız irəli getmək və ona əlavə biz idi bir az əvvəl gördüyüm bir bağlı siyahı kimi tanınır. Yaxşı, yalnız bir an nin fasilə edək. Bir toqquşma ehtimalı nədir ilk növbədə? Sağ, bəlkə artıq, bəlkə düşünür alıram Mən bu problem Engineering artıq Ben nə bilirlər? Bəli, mən özbaşına ilə gəlmək olar kimi mənim baş üst off nümunələri Allison və Harun, lakin əslində, vahid paylanması verilmişdir bəzi təsadüfi insertions ki, giriş, məlumat strukturu, həqiqətən nə bir toqquşma ehtimalının? Yaxşı çıxır, bu, həqiqətən var super yüksək. Bu mənə ümumiləşdirmək edək problem bu deyil. Belə n bir otaqda CS50 tələbələr, var ehtimal ki, ən azı otaqda iki tələbə eyni ad var? Belə ki, nə var. bir neçə Hund - Burada bir neçə 200, 300 nəfər Bu gün evdə yüz nəfər. Siz nə özümüzü soruşmaq istəyirdi Belə ki, əgər iki nəfər ehtimalı eyni ad günü olan bu otaqda, biz bu anlamaq bilər. Və mən iki var həqiqətən iddia eyni ad günü insanlar. Məsələn, hər kəs edir Bu gün ad günü var? Dünən? Sabah? Gedirəm kimi bütün hüququ, belə ki, hiss daha bu 363 və ya bunu etmək dəfə həqiqətən anlamaq üçün biz bir toqquşma var. Və ya biz yalnız riyazi bunu edə bilər daha maraqsız çox bunu. Və aşağıdakı təklif edirik. Ona görə də mən, biz model ola bilər ki, təklif Əyalətin iki nəfər ehtimalı 1 ehtimalı eyni ad günü olan heç bir mənfi ehtimalı eyni ad. Belə ki, bu almaq üçün və bu yalnız edir üçün Bu yazı xülya yolu, oda ilk şəxs, o, mümkün hər hansı bir ola bilər ad günləri, ildə 365 gün hərfinin şəxslər üçün üzr ilə Fevral 29 doğum günüdür. Belə ki, bu otaq ilk adam pulsuz Ad günləri hər hansı bir sayı üçün həyata 365 imkanlarının ki, biz, 365 ilə 365 ayırmış edəcəyik olan biridir. Oda növbəti şəxs, əgər məqsəd bir toqquşma qarşısını almaq üçün, yalnız necə onun ad günü var çox müxtəlif mümkün gün? 364. Belə ki, bu ifadə ikinci dövr mahiyyətcə bizim üçün ki, riyaziyyat bunu bir mümkün günü çıxarılaraq. Və sonra növbəti gün, növbəti gün, aşağı ümumi sayına Növbəti gün oda insanların. Və biz sonra nəzərə alsaq, onda nə olmayan hər kəs ehtimalı unikal ad günləri, lakin yenə 1 minus ki, biz əldə ifadə çox fancifully bilər bu kimi görünür. Amma daha maraqlı var vizual baxmaq. Bu x-ox üzrə olduğu bir chart edir oda insanların sayı, Ad günləri sayı. Y-ox üzrə ehtimalı bir vuruşma, iki nəfər eyni ad günü olan. Bu əyri olan paket edir ki, siz 40 kimi almaq kimi tezliklə tələbələr, siz 90% ehtimal da hazır combinatorically iki insanların və ya daha çox olan eyni ad. Və sonra bu 58 adam kimi almaq bir şans iki təxminən 100% oda insanlar üçün gedir eyni ad var olsa belə, 365 və ya 366 mümkün buketler və otaqda yalnız 58 nəfər. Yalnız statistik siz güman etdiyiniz , toqquşma almaq qısa Bu müzakirə motive. Biz burada xülya almaq, hətta ki, əgər Bu zəncirlər olan başlamaq, biz hələ istəyirik toqquşma edəcəyik. Sualına begs Belə ki, nə edir insertions ve silme bunu dəyəri bu kimi bir veri strukturu? Yaxşı mənə təklif edək - və mənə üzərində ekrana geri gidelim burada - biz elementlərinin N əgər siyahısı, biz daxil çalışdığınız əgər n elementləri, və biz neçə ümumi buketler? Gəlin 31 cəmi buketler Cavab Ad günləri halda. Bir maksimum uzunluğu nədir potensial bu zəncirlər? Daha mümkün 31 varsa müəyyən bir ayda ad günü. Və biz yalnız hər kəs clumping edirik - əslində bir axmaq nümunə var. Əvəzinə 26 etmək edək. Həqiqətən adları adam var Belə ki, əgər bununla verilməsi, Z vasitəsilə başlamaq Bizi 26 imkanları. Və biz kimi bir veri strukturu istifadə etdiyiniz biz qovuşdurmağımız biz yalnız gördüm bir, göstəricilərinə bir sıra, o cümlədən hər bir burada bir bağlı siyahısına bal ilk siyahısı hər kəs adı Alice ilə. İkinci siyahı hər ilə başlayaraq, A ilə başlayan ad B, və s. Hər ehtimal uzunluğu nədir həmin siyahıların biz gözəl təmiz fərz əgər A-dan Z vasitəsilə adları bölüşdürülməsi bütün data structure arasında? Veri strukturu n insanlar var onlar qəşəng istəyirsinizsə, 26 bölünür bütün üzərində yayılmışdır data structure. Belə ki, bu hər birinin uzunluğu zəncirlər 26 bölünür n. Lakin böyük O notation ki, nədir? Həqiqətən nədir? Belə ki, sağ, həqiqətən yalnız n var? Biz keçmişdə deyib sonra Çünki, uf siz 26 bölmək ki. Bəli, əslində daha sürətli edir. Lakin nəzəriyyəsi, o, əsaslı deyil bütün sürətli. Belə ki, biz bütün ki, çox ola görünmüyor yaxın bu müqəddəs grail üçün. Əslində, bu, yalnız xətti dəfə. Heck, bu nöqtədə, nə biz bunu yalnız bir böyük bağlı siyahısını istifadə edin? Niyə biz bir böyük istifadə etməyin adları saxlamaq üçün array otaqda hər kəs? Yaxşı, bir şey hələ də var bir hash masa haqqında çekici? Çekici bir şey hələ də məlumat strukturu haqqında bu kimi görünür? Bu. TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: yalnız hüququ və yenə əgər xətti vaxt alqoritm və xətti vaxt data strukturu, nə deyil yalnız böyük hər kəsin adı saxlamaq dizi, və ya böyük bağlı siyahıda? Və belə çox çətindir CS edilməsi dayandırmaq bu olmalıdır çox? Hətta bu barədə çekici nədir Mən onu cızıqlanmış baxmayaraq? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Insertions deyil? Artıq bahalı. Belə ki, insertions potensial hələ ola bilər , daimi vaxt ola bile data struktur, bu kimi bir sıra görünür göstəricilər də işarə edir hər biri potensial bağlı siyahısı. Necə sabit nail adları vaxtı durub? Sağ, qarşısında qalmaq? Biz bir dizayn qol qurban edin əvvəllər, biz saxlamaq istəyirdi yerləşir hər kəsin adı, məsələn, sorted, və ya səhnədə ədəd bütün sıralanır biz ki, güman çeşidlənməmiş bağlı siyahısı. Bu, yalnız, bizə bir-iki addım xərcləri Ben və Brian halda olduğu kimi əvvəllər bir element əlavə etmək üçün siyahının başında. Biz bütün çeşidlənməsi haqqında qayğı yoxdur Belə ki, əgər ilə başlayan adlar A və ya bütün B ilə başlayan adlar, biz hələ də bilər daimi vaxt durub nail olmaq. İndi Alice ya Bob və ya hər hansı bir ad ararken ümumiyyətlə hələ nədir? Bu 26 bölünür n böyük O, var hər kəs bərabər olduğu ideal halda paylanmış, kimi bir çox A var olduğu Z-nin, yəqin olan var qeyri-real. Amma hələ xətti var. Amma burada, biz nöqtəsinə geri gəlmək olan asimptotik notation və nəzəri doğrudur. Lakin real dünyada, əgər mən iddia mənim proqram 26 dəfə bir şey edə bilərsiniz olan proqram sizin, çox daha sürətli istifadə tercih edir? Sizin və ya mina, hansı 26 dəfə sürətli? Real, onun şəxs 26 dəfə daha sürətli, hətta nəzəri cəhətdən əgər bizim alqoritmlər eyni çalışır vaxt çalışan asimptotik. Mənə bir fərqli təklif edək cəmi həlli. Və bu fikrinizi əsəcək deyilsə, biz data strukturların bitti. Beləliklə, bu bir trie deyil - bir axmaq adı cür. Bu söz alımları gəlir və çünki trie, t-r-i-e, yazıldığına Əlbəttə axtarış trie kimi səslənir. Amma bu tarixi sözü trie edir. Belə bir trie, həqiqətən ağac bir növ edir və bu da ki, söz bir oyun var. Və çox görmək bilməz, baxmayaraq ki, Bu vizual ilə bir trie bir ağac ilə bir ailə ağac kimi, strukturlaşdırılmış üst və çox bir əcdad nəvəsi və böyük nəvəsi kimi alt yaradır. Amma trie hər node bir sıra edir. Və bir sıra var - və Haydi bir an oversimplify - Bu bir dizi, bu halda, ölçüsü 26, harada hər node yenidən ölçüsü bir sıra edir 26 olduğu ildə zeroth element array A təmsil və son hər belə element array Z. təmsil Buna görə, sonra təklif Bu data bir trie kimi tanınan quruluşu, ola bilər sözləri saxlamaq üçün də istifadə olunur. Biz saxlamaq necə bir an əvvəl gördüm sözlər, və ya bu halda adlar və biz , biz nömrələri saxlaya bilərsiniz necə daha əvvəl gördüm ancaq adları və ya strings diqqət əgər Burada maraqlı nə görürsünüz. Mən ad Maxwell olduğunu iddia Bu data strukturu daxilində. Harada Maxwell görürsünüz? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Sol. Belə Bu data maraqlı nə var strukturu deyil, mağaza daha string M-A-X-W-E-L-L backslash sıfır, bütün contiguously, yerine nə izləyir. Bu data strukturu kimi bir trie varsa, olan qovşaqlarının hər birinin yenidən bir sıra edir və Maxwell saxlamaq istəyirəm ki, siz ilk index və o qədər kök-nin sözlə, , topmost node danışmaq sağ, belə yer M, at təxminən ortasına. Və oradan, bir edin bir uşaq qovşağına pointer, belə danışmaq. Belə ki, ailə ağacının mənada, Siz aşağı bunu edin. Və başqa bir node sizə rəhbərlik olan orada sol haqqında yalnız bir sıra. Və sonra, Maksvell saxlamaq istəyirsinizsə, Əgər təmsil göstərici tapmaq A, burada bu biridir. Sonra növbəti node gedin. Və xəbərdarlıq - bu nə şəkil Agentliyi bir az aldatma - Bu node kiçik super baxmaq. Amma bu hüququ Y və Z. edir Bu, yalnız müəllif kesilir etmişdir oldu şəkil ki, həqiqətən, şeyi görürük. Əks halda bu şəkil natarazcasına geniş olardı. Sonra yeri X daxil Belə ki, indi indeksi, Sonra sonra W, sonra E, L, L. var bu marağı? Yaxşı, biz yeni bu cür kullanıyorsanız bir simli saxlamaq üçün necə götürmək data structure, hələ lazımdır mahiyyətcə məlumatlara off yoxlamaq Bir sözlə, burada bitir quruluşu. Başqa sözlə, bu qovşaqlarının hər birtəhər unutmayın ki, biz həqiqətən sonra bu göstəricilər bütün və bir az tərk edir Bu burada altındakı çörək qırıntı M-A-X-W-E-L-L göstərir strukturu həqiqətən Bu data quruluşu. Beləliklə, biz aşağıdakı kimi bunu bilər. Biz yalnız şəkil qovşaqlarının hər gördüm bir, ölçüsü 27 bir sıra var. P altı müəyyən çünki, indi 27 var Biz, həqiqətən, bir Apostrof verəcəyik biz O'Reilly kimi adları ola bilər apostrophes və s. Amma eyni fikir. Ki, həmin elementlərin hər biri bir struct üçün array bal node, belə ki, yalnız bir node. Belə ki, bu çox xatırladan Bizim bağlı siyahısı. Və sonra bir Boolean var, I will söz zəng olan yalnız olacaq Bir sözlə, bu bitir doğru əgər ağac ilə node. Bu səmərəli az təmsil üçbucaq biz bir an əvvəl gördüm. Bir söz ki, node başa çatır Belə ki, əgər ağac, söz sahəsində, doğru olacaq olan konseptual off yoxlanılması, və ya biz bəli var, bu üçbucaq rəsm edirik burada söz. Belə ki, bu trie edir. İndi isə sual nə onun çalışan? O n böyük o? Başqa bir şey mi? Yaxşı, siz Bu data adları N əgər strukturu, Maxwell yalnız biri olan onlara da çalışan zaman nə daxil və ya Maxwell tapmaq? Çalışan zaman nədir Maxwell olunsa? N başqa adlar varsa artıq cədvəldə? Bəli? TƏLƏBƏ: [işitilemez]. HOPARLÖR 1: Bəli, uzunluğu var adı, sağ? M-a-x-w-e-l-l Belə ki, bu kimi hiss Belə ki, alqoritm yeddi böyük Ey edir. İndi, əlbəttə, adı uzunluğu dəyişir. Bəlkə bir qısa adı var. Bəlkə uzun adı var. Bəs burada əsas var ki, bir sabit bir sayı var. Və bəlkə, həqiqətən daimi deyil Allah, real, əgər bir lüğət, bəzi limit yəqin ki, yoxdur bir hərflərin sayı məxsusi ölkədə şəxsin adı. Və biz güman edə bilər dəyər və daimidir. Mən bunu nə bilmirəm. Yəqin ki, daha böyük var biz bunu hesab edirəm. Bəzi künc həmişə var, çünki dəli uzun adı ilə halda. Belə ki, İT k deyirik, lakin o, hələ də var daimi ehtimalla, hər çünki ən azı bir dünyada, adını ölkənin ki, uzunluğu və ya qısa, buna görə də daimi deyil. Amma biz bildirib etdiyiniz zaman böyük bir şey deyil Sabit dəyər O, nə ki, həqiqətən ekvivalent? Bu həqiqətən eyni şey daimi zaman deyib. İndi aldadıcı cür haklýsýn? Biz bəzi nəzəriyyəsi yararlanarak cür istəyirik burada yaxşı, k üçün deyil ki, həqiqətən, yalnız bir sifariş və bu daimi vaxt var. Amma bu, həqiqətən. Burada əsas fikir Çünki biz bu artıq adları N əgər data structure, biz insert Maxwell, bu bizə edir zaman məbləği təsirə məruz qalan bütün at Maxwell daxil necə bir çox digər insanlar tərəfindən veri strukturu var? Olmaq görünmür. Mən bu bir milyard elementləri olsaydı sonra trie və Maxwell olunur daxil o bütün təsir? No Və bu gün göstərilən hər hansı fərqli var biz, bu günə qədər gördüm strukturları Sizin alqoritm çalışan zaman nə qədər tamamilə müstəqil heyəti və ya artıq deyil ki, data strukturunda. Bu imkan və belə artıq deyil p set altı imkan verəcək yenə öz həyata cəlb 150,000 oxu İmla kontrolü, sözlər, nə yaxşı ki, saxlamaq üçün mütləq aydın deyil. Və mən tapmaq talib etdik baxmayaraq müqəddəs grail, mən bunu bir trie olduğunu iddia. Əslində, bir hash table çox yaxşı bilər daha səmərəli olduğunu sübut edir. Ancaq o yalnız var - ki, yalnız dizayn qərarlardan biri Bunu etmək olacaq. Lakin yekun bir-qoy 50 və ya belə saniyə yalan nə bir peek almaq irəli həftə növbəti və biz keçid kənarda Bu skript satırı şeyi web dünya C proqramları əgər əsaslanır və PHP kimi dil və JavaScript və internet özü, Siz etdiyiniz HTTP kimi protokolları, il göydən hər əksəriyyəti və çap gün, bəlkə, və ya görüldü. Və biz soymaq geri başlarsınız nə qat internet edir. Və kodu nedir ki, yatan bugünkü alətlər. Bu teaser belə 50 saniyə. Mən sizə Çəkisi Warriors verir. [Video playback] O, bir mesaj gəldi. Protokol bütün öz ilə. O, qəddar firewall dünya gəldi əhəmiyyət verməz yönlendirici və təhlükələr uzaq ölümdən betər. O, sürətli. O, güclü var. O Tcpip var. O ünvanı var. Net döyüşçülər. [END video playback] HOPARLÖR 1: Bu necə internet Gələn həftə kimi işləməlidir.