[Powered by Google Translate] [Həftə 6, davamı] [David J. Malan] [Harvard Universiteti] [Bu CS50 edir.] [CS50.TV] Bu CS50 və bu həftə 6 sonu. Belə CS50x ki, edX təşəbbüsü cəlb Harvard ilk kursları biri həqiqətən bu ötən Bazar ertəsi oldu. İnternet haqqında nə digər bir fikir almaq istəyirsinizsə İndi birlikdə aşağıdakı, siz x.cs50.net giderim bilər. Yəni, edx.org müvafiq yerə yönlendirir bu və MİT və Berkeley digər kursları indi yaşadıqları idi. Siz bir haqq-hesab üçün qeydiyyatdan lazımdır, siz maddi əsasən eyni olduğunu görəcəksiniz Əgər biz hər şeyi hazır olaraq, təxirə bir neçə həftə olsa da, bu dövr idi. etdiyiniz kimi Amma nə CS50x tələbələr indi görəcəksiniz olduqca bu kimi interfeys. Bu, misal üçün, problem set 0 üçün gözden geçirmek aparıcı Zamyla edir. Edx.org giriş sonra, CS50x tələbə şeyi növ görür Bir kurs görmək gözləmək olardı: Bazar ertəsi üçün mühazirə, Çərşənbə, müxtəlif şort, problem dəstləri, bu walkthroughs, PDF üçün mühazirə. Bundan əlavə, burada bax, maşın tərcümə , İspan, İtalyan, Yapon, Çin İngilis dili protokolları və əlbəttə təkmil olacaq ki, digər dilləri və bütün dəstə biz API deyilən bir şey istifadə program onları roll kimi Google və ya proqram proqramlaşdırma interface, ki, bu digər dillərdə İngilis çevirmək imkan verir. Lakin bəzi yüz-plus könüllü gözəl ruh sayəsində, xahiş məşğul olmaq təklif edən İnternet təsadüfi insanlar Bu layihə, biz tədricən bu tərcümə keyfiyyətinin yaxşılaşdırılması olacaq insanlar bizim kompüter etdiyiniz səhvləri düzəltmək malik. Biz bir neçə tələbə biz ilkin gözləniləndən daha Bazar ertəsi göstərilir ki, həyata Belə ki çevrilir. Əslində, indi CS50x evdə birlikdə aşağıdakı 100,000 nəfər var. Belə ki, kompüter bu kurs edilməsi bu ilk sinif bütün hissəsidir həyata ümumiyyətlə, təhsil, daha geniş, əlverişli. Və reallıq, bu kütləvi online kurslar bəzi, indi onlar bütün biz burada işlər görünür kimi, bu çox yüksək nömrələri ilə başlanır. Amma məqsədi, nəticə etibarilə, CS50x üçün mümkün finiş xəttinə kimi bir çox insanlar üçün həqiqətən. Dizayn, CS50x bu ötən Bazar ertəsi təklif edir başqa yerdə məktəb öhdəlikləri insanlar kim ki, 15 aprel 2013 vasitəsilə bütün yolu, iş, ailə, digər münaqişələr və kimi, bir az daha çox rahatlıq var Bu kurs daxil dalış olan, bu, o demək kifayətdir olduqca ambitiously edilir adi dövr ərzində yalnız üç ay ərzində yalnız. Lakin bu tələbələr, eyni məzmunlu görüntülerken, eyni problem dəstləri həll olunacaq Eyni şort və kimi çıxışı olan. Beləliklə, biz bu birlikdə bütün həqiqətən bilirik. Və CS50x sonunda məqsədlərindən biri kimi bir çox insanlar üçün deyil finiş xəttinə və onlara kompüter elminin bu newfound anlayış vermək və proqramlaşdırma, həm də onlara bu paylaşılan təcrübəsi var. Kampus 50 müəyyən xüsusiyyətlərindən biri, biz ümid edirik ki, , bəzən daha yaxşı və ya pis, kommunal təcrübə bu cür olmuşdur amma bu insanlar üçün sol və sağ açmaq üçün olan və ofis saat və Hackathon və ədalətli. Bu, online xalqları ilə adam da bunu bir az çətindir lakin CS50x, ilk CS50 Expo ilə aprel ayında yekunlaşacaq ədalətli bizim fikir bir online uyğunlaşma olacaq , 2 dəqiqəlik video - Ü tələbələr bu minlərlə bütün 1 təqdim etməyə dəvət olunacaq onlara öz yekun layihə və ya video bir screencast salam waving ya və onların layihə söhbət və demoing, çox öz sələfləri kimi, ədalətli kampus burada işlər semestr sonuna, ümid qlobal sərgi var ki bu CS50x tələbələr yekun layihələrin çox kimi olan kampus burada bu Dekabr gözləyir. Gələcək ay ki, daha çox. 100,000 tələbələri ilə olsa da, bir neçə CA'lar ehtiyac gəlir. Uşaqlar burada cığır parlaq və CS50 alaraq nəzərə alaraq bir neçə həftə edX üzrə insanlar bu material azad əvvəl, Biz bu təşəbbüsü mümkün kimi öz tələbələrin çox cəlb etmək istərdim həyata, dövr habelə bu qış zamanı və bu gələn bahar də. Beləliklə, siz CS50x cəlb almaq istəyirsinizsə, xüsusilə CS50x müzakirə CS50 müzakirə və edX versiyası üzrə qoşulma bir çox kampus üzrə istifadə edilmiş, online bulletin board, ki, URL rəhbəri edin, bizi kim bildirin biz eyni bir tələbə və heyəti komanda və fakültə yaratmaq sevindim, çünki kampus olan sadəcə yanaşı oynayan və kömək edir. Və onlara tanış olan bir sual gördükdə, Siz, Internet bəzi ölkədə orada haradasa bir səhv hesabat, tələbə eşitmək və siz də həmin məsələ ki, üzük bir zəng çünki bir müddət əvvəl sizin d zalında, inşallah sonra sizə zəng və öz təcrübə mübadiləsi edə bilərsiniz. Beləliklə, siz istəyirsinizsə iştirak edin. Harvard Kompüter elm kursları, bir ənənə bir az var Siz qürurla wear bilər ki, bəzi geyim, bəzi geyim, olan, onların arasında CS50, semestr sonunda, siz CS50 başa olduqca qürurla dedi və CS50 və kimi etdi və biz həmişə tələbələri cəlb etmək üçün cəhd edin Bu prosesin mümkün qədər, biz dəvət vasitəsi ilə, dövr bu dəfə ətrafında, tələbələr dizayn təqdim istifadə etmək istədiyiniz seçimi Photoshop istifadə edərək, və ya hər hansı bir alət siz T-shirt və sweatshirts üçün dizayn təqdim etmək, dizayner danışırsınızsa və itlər üçün çətir və az bandanas biz indi və s. Və hər şey sonra deyil - qalibləri hər il sonra nümayiş olunur store.cs50.net da kurs saytında. Hər şey orada dəyəri satılır, amma saytında yalnız özü uzanır edir və insanlar kimi rəng və dizayn seçmək üçün imkan verir. Mən yalnız ötən il dizayn bəzi bölüşmək istədiyiniz fikir bir illik ənənə olan, burada bu bir başqa veb olmuşdur. "Mən Faultn Seg alıram Hər gün", keçən il təqdim biri olan məzunlar üçün hələ də mövcuddur. Bu bir idi "CS50, 1989 yaranma tarixi." Bizim Bowdens biri Rob, keçən il çox populyar idi. "Komanda Bowden" anadan olub, bu dizayn üst satıcılar arasında təqdim edilmişdir. Burada bu idi. Bir çox insanlar satış logs görə "Bowden Fever" idi. Ki, indi İnternet var, sizin dizayn ola bilər bilirik. Növbəti problem bu barədə daha ətraflı gəlmək edir. Daha bir aracı: İndi inşallah bir ifşa idi və etdik gdb bəzi praktiki təcrübə, ki, əlbəttə, ayıklama və siz manipulyasiya imkan verir kifayət qədər aşağı səviyyədə proqram, nə cür şeylər edir? Gdb nə imkan vermir? Evet? Mənə bir şey verin. [Tələbə cavab anlaşılmaz] Yaxşı. Funksiyası daxil Addım, belə ki, yalnız run yazın yoxdur və standart çıxış şeyi çap bütövlükdə vasitəsilə proqram zərbə var. Əksinə, ya növbəti yazaraq, xətti ilə xətt vasitəsilə addım bilər xətti və ya yazdığı bir qayda olaraq, bir funksiyası daxil dalış addım xətti ilə line getmək. Gdb siz nə imkan vermir? Evet? [Tələbə cavab anlaşılmaz] Dəyişənlərin yazdırın. Siz proqram daxilində bir az introspection etmək istəyirəm əgər bütün yer üzərində printf hesabatları yazılı müraciət etmədən, yalnız bir dəyişən çap və ya bir dəyişən bilərsiniz. Siz gdb kimi ayıklama ilə başqa nə edə bilər? [Tələbə cavab anlaşılmaz] Exactly. Siz breakpoints bilərsiniz, siz fasilə icra deyə bilərsiniz əsas funksiyası və ya foo funksiyası. Siz line 123 at break icrası demək olar. Və breakpoints həqiqətən güclü texnika var Çünki harada problem ümumi mənada əgər Yəqin ki, siz proqramın tam vasitəsilə gücləndirməklə vaxt sərf yoxdur olunur. Siz mahiyyətcə orada jump və sonra yazmağa başlaya bilərsiniz - addım və ya növbəti və ya analoji ilə vasitəsilə gücləndirməklə. Amma gdb kimi bir şey tutmaq, bu insan, sizə kömək edir ki, Sizin problemləri tapmaq ve hataları tapa bilərsiniz. Bu mütləq sizin üçün çox tapmaq deyil. Belə ki, biz qısa bir command line vasitədir ki, digər gün style50 təqdim bir az daha cleanly siz artıq kodu stylize çalışır, insan, görülən bilər var. Amma ki, bu da həqiqətən yalnız estetik bir şeydir. Istifadə etmək üçün bir az daha gizli ki Valgrind adlı digər alət var həyata Amma çevrilir. Onun çıxışı ilk baxışda ermənilər tərəfindən xüsusi amansızlıqla sirli edir. Amma xüsusilə indi müddəti hissəsi olduğunu, gözəl faydalı harada malloc və dinamik yaddaş ayrılması istifadə başlayan edirik. Things tez həqiqətən, həqiqətən, yanlış getmək bilər. Çünki sizin yaddaş azad unutmaq, və ya bəzi NULL pointer dereference əgər, və ya bir zibil göstərici dereference, adətən nəticələri olan simptom nədir? Günah Seg. Və kilobayttan ya megabayt bəzi sayının bu əsas fayl almaq o düşdü ki, sizin proqramın yaddaş dövlət təmsil ancaq proqram nəhayət, seqmentləşdirmə günah çatışmazlıqlar seg bir şey pis demək olar ki, həmişə bağlı baş deməkdir Əgər haradasa ki bir yaddaş bağlı səhv. Belə Valgrind bu kimi şeylər tapmaq kömək edir. Siz proqram tərtib etdik sonra, gdb kimi, çalışan bir aracıdır lakin birbaşa proqram run deyil, siz Valgrind run və siz gdb ilə kimi, bu proqram keçir. İndi, istifadə, ən yaxşı cür çıxış əldə etmək , belə ki, orada ekran üstün siz Valgrind-v bir az uzun görürsünüz olunur. Bir Linux kompüter proqramları istifadə etdiyiniz zaman "v" demək olar ki, hamı verbose deməkdir. Belə ki, siz default güc artıq data tüpürmək deməkdir. "- = Tam sızması kontrol." Bu, bütün mümkün yaddaş sızıntıları üçün çek deyib mən qəbul edə bilər ki, səhvlər. Bu, çox, Linux proqramları ilə ortaq bir paradiqma edir. Bir command line arqument varsa Ümumiyyətlə, ki, bir "keçid" var ki, proqram davranışı dəyişmək üçün nəzərdə, bu bir hərf var oldu bu-v, lakin işə ki, əgər, yalnız proqramçı dizayn, , command line arqumenti ilə sözləri tam bir söz və ya seriyası başlayır edilir -. Bu yalnız insan konvensiyalar, lakin getdikcə onları görəcəksiniz. Və sonra, nəhayət, "a.out" bu misal proqram üçün ixtiyari adı. Burada bəzi nümayəndəsi çıxış edir. Ki, demək bilər nə baxmaq əvvəl, mənə burada bir kod parçası üzərində gedək. Və tezliklə mənə yol bu həyata hərəkət imkan və in burada bu qısa nümunəsi olan memory.c, nəzər salaq. Belə ki, bu proqram mənə funksiyaları və suallar zoom imkan verir. Biz bir funksiyası çağırır əsas funksiyası, f var və sonra nə f biraz texniki ingilis, nə davam edir? F nə davam edir? Necə haqqında I line 20 ilə başlar və ulduzun yeri etməz, amma yalnız son məruzə ilə burada ardıcıl olacaq. Bizim üçün line 20 nə var? Sol tərəfində. Biz daha da qırmaq lazımdır. Int * x ki: nə edir? Okay. Bu göstərici elan və indi nin daha texniki olsun var. Bir göstərici bəyan çox konkret nə deməkdir? Başqası? Evet? [Tələbə cavab anlaşılmaz] Çox uzaq. Beləliklə, siz bərabər Qeydiyyat sağ tərəfinə oxu edirik. Yalnız int * x üzrə yalnız sol-nin diqqət edək. Bu göstərici "bəyan", ancaq indi edək ki, definition dərin dalış. Ki, konkret, texniki nə deməkdir? Evet? [Tələbə cavab anlaşılmaz] Okay. Bu yaddaş bir ünvan saxlamaq hazırlanması oldu. Yaxşı. Və gələcək bu bir addım olsun bu 32 bit ki, dəyişən, x, elan edir. Mən çünki 32 bit olduğunu bilirik - Bu halda bir göstərici deyil, çünki bu, bir int var, çünki deyil. Bir int ilə eyni, ki, təsadüf ancaq ulduz var ki, bu göstərici var deməkdir və cihaz, bir çox kompüter kimi deyil, bütün göstəricilərinə 32 bit var. Son Macs, son PC kimi daha müasir avadanlıq, siz, 64-bit göstəricilərinə ola bilər ancaq cihaz, bu şeylər 32 bit var. Beləliklə, biz ki standartlaşdırmaq lazımdır. Daha konkret, hekayə aşağıdakı kimi gedir: Biz bir pointer "bəyan" nə deməkdir? Biz yaddaş ünvan saxlamaq üçün hazırlamaq. Ki, nə deməkdir? Biz 32 bit qədər edir ki, dəyişən adlandırılan x yaratmaq ki, tezliklə tam üçün ünvan saxlamaq olacaq. Və yəqin ki, biz əldə edə bilərsiniz kimi haqqında kimi dəqiq deyil. Bu dünya sadələşdirmək və yalnız x adlı göstərici bəyan demək irəliləyir gözəl var. Bir göstərici elan, lakin həyata və nə həqiqətən neler anlamaq hətta yalnız bir neçə simvol. İndi, bu bir daha ifadə edir, hətta, demək olar ki, bir az daha asandır. Beləliklə, bu artıq qeyd edir ki, nə edir: "malloc (10 * sizeof (int));" Evet? [Tələbə cavab anlaşılmaz] Yaxşı. Mən orada onu edəcəyik. Bu on integers üçün yaddaş yığın ayrılması oldu. İndi in qədər dərin dalış olsun on integers üçün yaddaş yığın ayrılması oldu. Malloc nə qayıdır? Daha konkret ki yığın ünvanı, və ya ki, yığın ilk byte və ünvanı. Mən necə deyiləm, proqramçı bilmək yerləşir yaddaş bitir ki, yığın? Mən bunu bitişik ki, bilirik. Malloc, definition edərək, yaddaş bitişik yığın verəcək. Bu No boşluqların. Siz ki, yığın hər byte etmək imkanı geri geri geri, lakin yaddaş bu yığın sonunda olduğu necə bilirik? Siz malloc istifadə zaman? [Tələbə cavab anlaşılmaz] Yaxşı. Siz deyil. Siz yadda var. Mən dəyəri 10 istifadə yadda var və mən hətta burada etmişik görünmür. Amma onus mənə tamamilə. Biz strings üçün az güvenen olmaq etdiyiniz Strlen, çünki \ 0 malik olan bu Konvensiya yalnız və ya simli sonunda bu xüsusi nul xarakteri, NUL. Bu yaddaş yalnız ixtiyari chunks keçirilən deyil. Bu qədər var. Line 20 Beləliklə, sonra yaddaş yığın ayırır ki, on integers saxlaya bilərsiniz, və bu ilk byte üçün ünvan saxlayan dəyişən adlı x yaddaş ki, yığın edir. Bir göstərici olan dolayı. Line 21 Beləliklə, təəssüf ki, bir səhv idi. Lakin ilk, o nə edir? Bu, yer 10, dizine 0 mağaza deyən oldu x dəyəri 0 adlı yaddaş yığın edir. Belə şeylər bir neçə gedir bilərsiniz. X bir göstərici olsa da, bir neçə həftə əvvəl geri siz hələ də array-stil kvadrat mötərizə notation istifadə edə bilərsiniz. Əslində çox sirli görünüşlü göstərici hesab üçün qısa tərəfdən notation çünki. biz bu kimi bir şey olardı: ünvan x götür, artıq 10 ləkələr hərəkət o yerdə saxlanılır nə ünvan üçün orada gedin. Amma səmimi, bu oxumaq və rahat almaq üçün yalnız dəhşətli deyil. Belə ki, dünya adətən bu qədər çox insan dostu oxumaq yalnız çünki kvadrat mötərizə istifadə edir. Amma nə həqiqətən başlıq altında gedən var; x bir ünvan deyil, bir sıra, hər se edir. Belə ki, bu x-ci yeri 10 0 saxlanılması edilir. Nə üçün bu pis? Evet? [Tələbə cavab anlaşılmaz] Exactly. Biz yalnız on ints ayrılmış, lakin C proqramlaşdırma zaman 0-dan saymaq belə ki, 0 1 2 3 4 5 6 7 8 9 deyil, 10 girmə imkanı vardır. Buna görə ya proqram seg günah edir və ya deyil. Amma biz həqiqətən bilmirəm, bu bir nondeterministic davranış sortudur. Bu, həqiqətən biz xoşbəxt almaq asılıdır. Mən ki, əlavə byte istifadə əgər əməliyyat sistemi ağla deyil çıxır ki, varsa, o mənə verilmir baxmayaraq, mənim proqram qəza bilər. Bu, xammal var o arabası var, lakin bu simptom görmək bilər və ya yalnız bir dəfə isə onu görə bilərsiniz. Lakin reallıq səhv var, əslində, olmasıdır. Siz doğru istəyirəm ki, bir proqram yazdıq, əgər o, həqiqətən problem var insanların hər dəfə bir müddət çöküyor ki, istifadə etdiyiniz proqram satılan etdik ki, çünki, əlbəttə, bu yaxşı deyil. Əslində, bir Android telefon və ya iPhone varsa və siz, bu gün apps download Əgər yaşadığınız halda app yalnız çıxın o yox qəflətən ki, demək olar ki, həmişə bir yaddaş bağlı problem var proqramçı bir pointer qıfıllar və dereferenced vasitəsi o yoxdur, və iOS və ya Android nəticəsində yalnız tamamilə proqram öldürmək ki, çox risk müəyyən davranış və ya təhlükəsizlik kompromis bir növ çox. Bu bir başqa bu proqram başqa bir səhv var. Bu proqram nə qədər berbat var? Mən təbliğ sonra nə tətbiq deyil etdik. Evet? [Tələbə cavab anlaşılmaz] Yaxşı. Mən yaddaş azad deyil. Belə ki, indi thumb qayda siz malloc zəng zaman siz həyata zaman, o yaddaş istifadə edərək, pulsuz zəng olmalıdır olmalıdır. İndi mən bu yaddaş azad istəyirsiniz? Yəqin ki, bu ilk düzgün idi fərz, mən burada bunu etmək istəyirəm. Mən, məsələn, burada aşağı edə bilmirdik. Niyə? Məhz həyata çərçivəsində. Belə ki, göstəricilər haqqında söhbət edirik, baxmayaraq bu həftə 2 və ya x yalnız elan edildiyi qıvrım aşırma daxilində daxilində olduğu 3 məsələdir. Belə ki, siz mütləq orada azad edə bilməz. Bu pulsuz Mənim yalnız şans təxminən line 21 sonra. Bu kifayət qədər sadə proqram, siz cür fikrinizi bükülmüş bir dəfə olduqca asan idi səhvləri olduğu nə ətrafında proqram etdiklərini edir. Və ilk onu görmədi belə, ümid edirəm ki, indi bir az aydın deyil bu səhvlər olduqca asanlıqla həll və asanlıqla qəbul edir. Amma bir proqram 12-dən çox xətləri uzun zaman, o, 100 xətləri uzun, 50 xətləri uzun məntiqi vasitəsilə düşüncə, xətti ilə kodu xətti ilə gəzinti, daim, hata tapmaq, mümkün deyil, bunu xüsusilə əyləncə deyil və bunu da çətindir, və Valgrind kimi bir alət var edirdi. Mənə irəli getmək və bunu edək: mənim terminal pəncərə açmaq qoy, və yaddaş gözəl görünür, çünki mənə yalnız yaddaş run deyil bildirin. Mən xoşbəxt alıram. Serialın sonunda əlavə byte gedən çox problematik görünür deyil. Lakin mə deməkdir ki, ağlı başında olma çeki, etmək, yenə mənə bildirin Bu həqiqətən doğru olub olmadığını. Belə valgrind-v nə edək - = tam sızması kontrol və bu halda proqramın adını yaddaş deyil, a.out edir. Mənə irəli getmək və bunu bildirin. Daxil Hit. Allah Əziz. Bu çıxış, bu mən əvvəllər üçün alluded edir. Lakin, burada ağılsızlıq bütün vasitəsilə oxumaq öyrənmək əgər, Bu ən maraqlı deyil ki, yalnız diaqnostik çıxış edir. Sizin göz həqiqətən axtarır istəyir səhv və ya etibarsız hər hansı qeyd edir. Problemlər göstərir ki, söz. Və həqiqətən, aşağı burada yanlış gedir nə edək. Mən bir növ bir xülasə vardır "exit-da istifadə:. 1 blok 40 bayt" Mən hələ həqiqətən bir blok nə əmin deyiləm, lakin 40 bayt ki, gələn yerdə mən anlamaq bilər kimi həqiqətən hiss edir. 40 bytes. Niyə çıxış istifadə 40 bytes var? Və daha konkret desək, biz burada aşağı diyirləyin əgər, mən niyə mütləq 40 bytes itirmişdir? Evet? [Tələbə cavab anlaşılmaz] mükəmməldir. Bəli, dəqiq. Var, on integers idi və o hər 4 və ya 32 bit ölçüsü siz təklif kimi, mən pulsuz adlı yoxdur, çünki mən dəqiq 40 bytes kaybettim. Yəni, bir səhv var, indi daha az aşağı baxaq və bu yanında görmək "Etibarsız ölçüsü 4 yazın." İndi bu nə deməkdir? Bu ünvan, yəqin, nə baza notation ifadə edir? Bu hexadecimal və hər hansı bir zaman siz 0x ilə başlayan bir sıra bax ki, biz geri suallar, hesab edirəm ki, pset 0 bölməsində yol idi ki, hexadecimal deməkdir olan ikili üçün hex üçün decimal konvertasiya və s, bir son hazırlıq həyata etmək yalnız idi. Hexadecimal, yalnız insan konvensiyası ilə, adətən göstəricilərinə təmsil etmək üçün istifadə olunur və ya ümumiyyətlə, ünvanlanır. Bu, yalnız bir konvensiya var oxumaq üçün bir az daha asandır, çünki decimal kimi bir şey bir az daha yığcam var ən insanlar istifadə üçün və ikili əhəmiyyətsizdir. Belə ki, indi bu nə deməkdir? Yalnış yazmaq var kimi Bəli, görünür, memory.c xətti 21 ölçülü 4. Belə in line 21 geri bildirin, və həqiqətən, burada yalnış yazmaq deyil. Belə Valgrind, tamamilə mənim əl keçirilməsi və nə fix mənə demək niyyətində deyil lakin mən yalnış yazmaq edirəm ki, aşkar edilir. Mən olmamalıdır 4 bayt toxunan deyiləm, və yəqin ki, çünki Siz qeyd kimi, mən əvəzinə [9] və [10] edirəm maksimum ya [0] və ya arasında bir şey. Valgrind ilə, indi bir proqram yazıyoruz hər zaman həyata göstəricilərinə istifadə edir və yaddaş istifadə edir və malloc xüsusilə ki, mütləq bu uzun çalışan vərdiş halına almaq lakin çox asanlıqla Valgrind əmri kopyalanamaz və yapışdırılır orada bəzi səhvlər var görmek üçün. Və, siz çıxış görmək hər zaman böyük olacaq ancaq vizual bütün çıxış vasitəsilə analiz və görmək görmek səhvlər qeyd ya xəbərdarlıq və ya etibarsız və ya itirdi. Siz kimi səs haradasa qıfıllar hər hansı bir söz. Sizin Toolbar yeni bir alət var ki, bilirik. İndi Bazar ertəsi, biz insanlar bütün dəstə idi bura qədər gəlib və əlaqəli siyahı anlayışı əks etdirir. Və biz hansı problemin həlli kimi bağlı siyahı təqdim? Evet? [Tələbə cavab anlaşılmaz] Yaxşı. Diziler yaddaş onlara əlavə ola bilməz. Siz ölçüsü 10 bir sıra ki, siz bütün ayrılması edin. Siz əvvəlcə malloc adlı əgər Siz realloc kimi bir funksiyası zəng edə bilərsiniz kosmik bunun sonuna olduqda və bu sıra inkişaf üçün cəhd edə bilərsiniz Başqa heç bir istifadə edir və orada deyil, bu, yalnız başqa bir yerdə bir daha yığın tapmaq olacaq. Lakin o, yeni array o bayt bütün surəti olacaq. Bu, çox düzgün həll kimi səslənir. Niyə bu çirkin deyil? Mən bu işləri demək, insanlar bu problemi həll etmişik. Niyə biz bağlı siyahıları ilə bazar ertəsi onu həll etmək lazım idi? Evet? [Tələbə cavab anlaşılmaz] Bu uzun müddət bilər. Əslində, malloc ya realloc və ya başqa biri olan calloc, zəng etdiyiniz istənilən vaxt, hər zaman, proqram, əməliyyat sistemi üçün gedir, proqramı yavaşlatmaq edirlər. Siz loops şeyi bu cür edirik, əgər, həqiqətən, hər şeyi yavaşladaraq edirik. Siz, "salam dünya" tipli proqramların sadə, bu qeyd etmək fikrində deyilik lakin çox böyük proqramların, yaddaş üçün təkrar əməliyyat sistemi tələb və ya təkrar geri verilməsi yaxşı bir şey olmayacaq çalışır. Plus, yalnız intellektual növ - bu zaman tam tullantılar var. Yeni array daxil hər şey çıxarmaq daha çox yaddaş ayrılması Niyə, risk, Siz, həqiqətən, ehtiyac kimi yalnız çox yaddaş ayırmağa imkan verir ki, bir alternativ varsa? Belə ki, burada müsbət və minuses var. Bu müsbət biri indi dinamizm var. Yaddaş chunks sərbəst olduğu əhəmiyyətli deyil, Mən yalnız göstəricilər vasitəsilə yaratmaq bu çörək qırıntıları sıralayabilirsiniz birlikdə mənim bütün bağlı siyahı simli üçün. Amma ən azı bir qiymət ödəyirlər. Mən bağlı siyahıları əldə imtina etmək lazımdır? Evet? [Tələbə cavab anlaşılmaz] Yaxşı. Daha çox yaddaş lazımdır. İndi, bu göstəricilər üçün yer lazımdır və bu super sadə bağlı siyahı halında yalnız 4 bayt olan integers saxlamaq üçün çalışır ki, deyirdik saxlamaq yaxşı bir göstərici 4 bayt, belə ki, indi sözün iki dəfə etdik yaddaş məbləği yalnız bu siyahıda saxlamaq lazımdır. Ancaq yenə də, bu kompüter sabit tradeoff edir zaman və məkan və inkişafı, səy və digər resurslar arasında. Bir bağlı siyahısını istifadə edərək, bir İşin mənfi tərəfi odur nədir? Evet? [Tələbə cavab anlaşılmaz] Yaxşı. Daxil olmaq kimi asan deyil. Biz leverage artıq ola bilər kimi həftə 0 prinsipləri bölmək və qalib. Və daha çox xüsusi, ikili axtarış. Çünki baxmayaraq biz insanlar Bu siyahıda ortasında olduğu təxminən bilərsiniz, kompüter yalnız bu bağlı siyahı ilk deyilən ünvan başlayır bilir. Və 0x123 və ya kimi bir şey var. Və proqram yalnız yol ortasında element tapa bilərsiniz əslində bütün siyahısını axtarış edir. Və hətta sonra, bu sözün bütün siyahısını axtarış çünki hətta bir dəfə siz göstəricilər aşağıdakı orta element çatmaq siz, proqram, potensial, bu siyahı necə uzun heç bir fikrim yoxdur siz sonunda edib, siz necə program bilmirəm qədər Bir bağlı siyahı sonunda olduğunu? Xüsusi NULL pointer, belə ki, yenə bir konvensiya var. Bu göstərici istifadə daha çox, biz mütləq bəzi zibil dəyəri istəmirəm haradasa mərhələ off işarə edərək, biz, bu tərəfdən olacaq NULL aşağı istəyirəm, o başa yerləşir biz bilirik ki, biz bu data tərkibində bu dayanacaq var ki. Biz bu manipulyasiya etmək istəyirsinizsə? Biz bu vizual çox idi, və insanlar ilə lakin nə biz durub etmək istəyirsinizsə? Belə ki, orijinal siyahı 9, 17, 20, 22, 29, 34 idi. Biz sonra sayı 55, bunun üçün bir node üçün malloc yer istədiyini əgər və sonra biz bazar ertəsi günü etdiyiniz kimi siyahısına 55 əlavə etmək istəyirsiniz? Biz bu etməliyəm? Yaxşı, Anita gəldi və o, mahiyyətcə siyahısı getdi. O, növbəti, növbəti, növbəti, növbəti, növbəti sonra ilk element başladı. Nəhayət sol bütün yol aşağı edib və oh həyata, bu NULL edir. Belə ki, nə göstərici manipulyasiya edilməsi lazım? Sonunda olan şəxs, sayı 34, sol əl qaldırdı lazım 55 qeyd etmək, 55 yeni NULL terminator olmaq pointing down onların sol qol lazımdır. Done. Pretty asan bir sıralaması siyahısına 55 əlavə etmək üçün. Və necə ola bilər? Mənə irəli getmək və burada kodu Məsələn açmaq edək. Mən gedit açmaq və mənə ilk iki faylları açmaq qoy edəcəyik. Bir list1.h və bu kod yığın ki, mənə yalnız Xatırladaq biz bir node təmsil etmək üçün istifadə edir. A node siyahısında növbəti şey yalnız xal növbəti adlı n adlı int və bir pointer də var. Bu. H fayl indi. Niyə? Var, bu Konvensiyanın və biz bu böyük məbləği özümüz istifadə deyil printf və digər funksiyaları yazırdı ancaq adam stdio.h adlı fayl yazmaqla dünya üçün hədiyyə kimi bu funksiyaları bütün verdi. Və sonra string.h var, sonra map.h var və bütün bu h fayllar var siz görüldü və ya digər insanlar tərəfindən yazılı müddətində istifadə edə bilər ki. Adətən o edir. H faylları typedefs kimi yalnız şeylər və ya xüsusi növləri və ya sabitləri bəyan bəyan. Siz mövzu faylları funksiyaları 'applications qoymaq deyil. Siz əvəzinə, yalnız onların prototipləri qoydu. Siz onlar ehtiyac nə dünya ilə bölüşmək istəyirəm şeyi qoymaq onların kodu tərtib etmək üçün. Belə ki, yalnız bu vərdiş halına almaq üçün, biz eyni şey etmək qərarına gəlib. Çox list1.h var deyil lakin biz dünyada insanların maraq ola bilər ki, bir şey gətirdik olan bağlı siyahı həyata keçirilməsi istifadə etmək istəyirik. İndi list1.c, mən bu bütün şey ilə getmək deyil o bir az uzun, çünki, bu proqram, lakin ən sətirinə tez real run bildirin. Mənə List1 tərtib mənə sonra List1 run bildirin, və nə görürsünüz yerləşir edək biz burada süni bir sadə kiçik proqram var mənə siyahısına nömrələrin əlavə və aradan qaldırılması üçün imkan olacaq. Mənə irəli getmək və menyu et 3 3 yazın edək. Mən rəqəm daxil etmək istəyirəm - Gəlin 9 olan ilk sayı, nə və indi mən siyahısı indi 9-a bildirib alıram. Mənə davam və başqa durub edək, mən menyu et 3 təşkil edib. Nə sayı mən əlavə etmək istəyirsiniz? 17. Daxil edin. Mən yalnız bir daha edəcəyik. Mənə sayı 22 daxil edək. Beləliklə, biz bir an əvvəl slayd şəklində olduğunu bağlıdır siyahısı əvvəlinə var. Bu durub əslində necə baş verir? Həqiqətən, 22 siyahının sonunda indi. Hekayə Beləliklə, biz bazar ertəsi mərhələdə bildirib və yalnız indi recapped həqiqətən kodu baş edilməlidir. Bir nəzər salaq. Bu fayl aşağıya fırladın edək. Biz, funksiyaları, bəzi üzərində parıltı olacaq amma biz enmək ki, daxil funksiyası lazımdır. Biz bu bağlı siyahı yeni node daxil haqqında getmək necə edək. Siyahısı Harada elan? Yaxşı, qoy ki, üst bütün yolu gedin və mənim bağlı siyahı mahiyyətcə ilkin NULL olan bir göstərici kimi elan fark. Mən ümumiyyətlə biz qarşı təbliğ etdiyiniz burada qlobal dəyişən kullanıyorum onu qorumaq üçün kodu bir az messy edir, çünki bu tənbəl, adətən sort, ancaq tənbəl deyil və bu yanlış deyil və bu, pis deyil həyat üçün proqram yeganə məqsədi bir bağlı siyahı simülasyonu üçün olsun. Hansı edirik məhz budur. Hər funksiyası üçün keçməli sonra əsas bu elan və buna daha çox biz bu proqram yazdıq, biz yerinə oh reallaşdırmaq isə yalnız qlobal edək Bu proqram bütün məqsəd bir və yalnız bir bağlı siyahı nümayiş edir. Belə ki, tamam hiss edir. Burada mənim prototipləri və biz, bu bütün vasitəsilə getməyəcək amma sil funksiyası, bir tapmaq funksiyası, bir insert funksiyası və traverse funksiyası yazdı. Amma indi daxil funksiyası geri enmək bildirin və bu burada necə işlədiyini görmək. Daxil line deyil - burada biz gedin. Daxil edin. Biz xahiş olacaq, çünki Belə ki, hər hansı arqumentlər etmir onlar əlavə etmək istədiyiniz nömrəni üçün bu funksiya istifadəçi içərisində. Lakin ilk, biz onlara bir yer vermək üçün hazırlamaq. Bu digər Məsələn surəti və yapışdırıb növ edir. Bu halda, biz int ayrılması edilmişdir; bu dəfə biz bir node ayrılması edirik. Mən, həqiqətən, bir node nə qədər bytes xatırlamıram, lakin gözəl var. Sizeof mənim üçün ki, anlamaq olar. Və niyə line 120 NULL kontrol edirəm? Line 119 yanlış getmək bilər? Evet? [Tələbə cavab anlaşılmaz] Yaxşı. Sadəcə mən çox yaddaş tələb etdiyiniz halda ola bilər və ya bir şey nın səhv və əməliyyat sistemi, mənə vermək üçün kifayət qədər bytes yoxdur belə ki, NULL qaytarılması ilə qədər siqnalları, və mən kontrol olmayan və yalnız kor-koranə ünvanı geri istifadə davam, bu, NULL ola bilər. Bəzi unknown dəyər ola bilər; bir yaxşı şey istisna olmaqla, mən - həqiqətən unknown dəyəri olmayacaq. Bu NULL ola bilər, mən istəmirəm belə bu sui-istifadə və dereferencing risk. Ki, baş verərsə, mən yalnız qayıtmaq və mən hər hansı bir yaddaş geri ala bilmədim kimi biz iddia lazımdır. Əks halda, mən istifadəçi mənə əlavə etmək üçün bir sıra demək, mən bizim köhnə dostumuz GetInt zəng və sonra bu biz bazar ertəsi təqdim yeni sintaksis idi. "Newptr-> n 'siz malloc tərəfindən verilmiş ünvanı almaq deməkdir olan, yeni bir node obyekt ilk byte təmsil və sonra n adlı sahəsində gedin. Bir az trivia sual: Bu kodu nə daha sirli line bərabərdir? Necə başqa mən bu yazılı ola bilər? Bir zərbə almaq istəyirsiniz? [Tələbə cavab anlaşılmaz] Yaxşı. Edin. N istifadə edərək, lakin bu kimi olduqca kimi sadə deyil. Mən ilk nə etmək lazımdır? [Tələbə cavab anlaşılmaz] Yaxşı. I * newptr.n etmək lazımdır. Belə ki, bu göstərici yeni açıq-aydın bir ünvan var deyib. Niyə? Bu malloc geri Çünki. Deyərək * newptr "getmək" siz olduğumuzda, sonra, sonra daha çox tanış. n istifadə edə bilərsiniz lakin bu, yalnız biz insanlar edir, xüsusilə də əgər, bir az çirkin görünür oxları ilə göstəricilərinə bütün vaxt çəkmək; dünyanın bu arrow notation haqqında standart var, hansı tam eyni şey yoxdur. Sol şey bir göstərici olduqda> notation - Beləliklə, siz yalnız istifadə edin. Bir faktiki struct varsa Əks halda, bu. N istifadə edin. Və sonra bu: Niyə newptr-> gələn başlamaq yoxdur null? Biz mərhələnin sonunda bir sallanan sol off istəmirəm. Biz düz aşağı işarə istəyirik, bu siyahının sonu deməkdir potensial bu node da ola bilər, belə ki, biz daha yaxşı NULL əmin olun. Və, ümumiyyətlə, sizin dəyişənlərin və ya data üzvləri və structs başlatılıyor bir şey yalnız yaxşı təcrübədir. Yalnız zibil var və ümumiyyətlə mövcud davam imkan sorun siz alır Daha sonra haqqında bir şey unutmaq əgər. Burada bir neçə hallarda var. Bu, bir daha, daxil funksiyası dəyişən ilk adlanan əgər mən kontrol ilk şey deyil, qlobal dəyişən NULL ki, heç bir bağlı siyahı var deməkdir. Biz hər hansı bir ədəd daxil deyil, belə ki, bu cari nömrəsi daxil mənasız deyil siyahısına, çünki yalnız siyahının əvvəlində məxsusdur. Anita yalnız iddiasında, yalnız burada duran zaman bu idi biz bir node ayrılmış qədər başqa heç bir mərhələsində burada idi sonra o, ilk dəfə əlini qaldırmaq bilər hər kəs bazar ertəsi onun sonra səhnəyə çıxmaq əgər. İndi burada, bu demək üçün bir az çek əgər n yeni node dəyəri , cari ilk node-ci ildə n dəyəri gələn demək zaman, struct getmək deməkdir ki, newptr tərəfindən də qeyd edilir ki, belə ki, burada biz orada getmək. Sonra arrow növbəti sahəsində əldə deyib, sonra = nə dəyəri qoymaq deyib? Nə dəyər ilk idi? Ilk idi dəyəri Birinci bu bu node da qeyd olunmalıdır deməkdir ki, bu düyün də işarə edilmişdir. Başqa sözlə, nə, mənim yazı ilə bir gülünc mess olsa görünür yalnız ətrafında bu oxlar hərəkət sadə bir fikir var bu bir liner ilə kodu tərcümə. Növbəti sahəsində ilk nə saxlamaq və sonra ilk əslində nə yeniləmə. Bu bəzi vasitəsilə irəli və sürətli irəli gedək, və indi bu quyruq durub yalnız baxmaq. Mən bir node növbəti sahəsində NULL olduğunu tapmaq nöqtəyə almaq düşünək. Və hekayə, bir detal bu nöqtədə mən artıq Parıldadıcı edirəm ki, Mən line 142, sələfi göstərici burada başqa göstərici qədər təqdim etdik ki. Əsasən, hekayə bu nöqtədə bir siyahısını uzun olur, I növ iki barmaqları ilə gəzmək lazımdır, mən də uzaq getmək əgər, çünki bir-uzunluğu siyahısına xatırlayıram, siz geri getmək bilməz. Belə predptr bu fikir mənim sol barmaq və newptr - deyil newptr. Burada bir başqa göstərici digər barmaq və mən siyahısı gəzinti yalnız cür edirəm. Ki, mövcud görə. Amma yalnız burada sadə hallarda biri hesab edək. Ki, pointer növbəti sahəsində NULL varsa, məntiqi dolayısı nə var? Bu siyahı traversing və Əgər bir NULL pointer edib? Siz siyahısı sonunda istəyirik, və s kodu bu bir əlavə element əlavə etmək intuitiv növ, onların növbəti pointer NULL ki node almaq olacaq Bu hazırda NULL, və yeni node ünvan üçün, baxmayaraq ki, o, dəyişir. Belə ki, yalnız biz kiminsə sol artırılması ilə səhnəyə çəkdi kodu ok rəsm edirik. Mən indi mənim əlləri dalğa lazımdır ki, işin Düşünürəm ki, biz ətraf mühit bu cür bunu zaman itirilmiş almaq asandır düşünmək yalnız, çünki, siyahısı nin ortasında durub kontrol edilir. Siz anlamaq istəyirsinizsə, ancaq daxilən, nə etmək lazımdır Bəzi sayı orta məxsusdur yerləşir siz gəzmək var birdən çox barmaq ilə bir çox göstərici, bu yoxlama ilə məxsus olduğu anlamaq element edir Cari və sonra ki, yer tapmaq sonra siz çox diqqətlə ətrafında göstəricilərinə hərəkət yerləşir shell oyun bu sort var. Və cavab, siz öz evdə vasitəsilə səbəb istəyirsinizsə, aşağı yalnız kodu bu iki xətti sonunda, lakin həmin xətlərin üçün super vacibdir. Əgər kimsə əl açılan və qaldırmaq əgər başqası, səhv üçün, çünki yenidən, siz siyahısı orphaning ola bilər. Daha konseptual yekunlaşdırmaq üçün, quyruq da daxil nisbətən sadə deyil. Baş da durub, həmçinin nisbətən sadə lakin bir əlavə göstərici bu dəfə güncellemeniz lazımdır burada siyahısına sayı 5 sıxmaq, və sonra ortada durub daha səy cəlb, çox diqqətlə onun düzgün yer sayı 20 əlavə etmək üçün, olan 17 və 22 arasında. Siz, 22 yeni node 20 nöqtəsi kimi bir şey etmək lazımdır sonra hansı node in göstərici ötən yenilənir lazımdır? Bu həqiqətən daxil, 17 var. Belə ki, təkrar edirəm ki, xüsusi həyata keçirilməsi üçün faktiki kodu uzatmaq lazımdır. İlk baxışdan, bu bir az böyük, amma bu, həqiqətən, yalnız sonsuz loop var ki, loop loop, loop, loop, siz NULL pointer hit kimi qırılma oldu bu noktada zəruri daxil edə bilərsiniz. Bu, sonra nümayəndəsi bağlı siyahı durub kodu. Ki, bir çox növ idi və biz bir problem həll etdiyiniz kimi hiss lakin biz bütün başqa bir təqdim etdik. Açığı, biz bütün bu vaxt sərf etdik böyük O və Ω və daha tez problemləri həll etmək üçün çalışır, vaxt çalışan, və burada biz geri, bu hiss böyük bir addım atırıq. Və hələ, məqsəd veri olsa, biz bazar ertəsi dedi ki, müqəddəs grail kimi hiss, həqiqətən olacaq dərhal hər şeyi saxlamaq üçün. Əslində, biz bir an qoymaq kənara bağlı siyahı etdi güman və biz əvəzinə masa anlayışı təqdim etdi. Və bir sıra kimi bir an üçün yalnız bir masa hesab edək. Bu array və bu halda burada 26 elementlər, 25 0 var və adları storage bəzi yığın lazım Güman: Alice və Bob və Charlie və kimi. Və bu adlar saxlamaq üçün bəzi data struktur lazımdır. Yaxşı, bir bağlı siyahısı kimi bir şey istifadə edə bilər və s Bob sonra Bob və Charlie əvvəl Alice daxil siyahısına gəzmək bilər. Və əslində, bir kənara kimi belə kodu görmək istəyirsinizsə, list2.h, biz məhz bunu bilirik. Biz bu kod vasitəsilə getmək deyil, lakin bu ilk nümunəsi bir variantdır ki, qondarma tələbə əvvəl gördüm başqa bir struct, təqdim və sonra nə faktiki bağlı siyahısında saxlayan bir tələbə strukturu bir göstəricisidir çox sadə bir az tam, n. Kod faktiki strings əhatə orada belə həyata lakin əl-qolu həqiqətən indi səmərəliliyi problemini həll etmək üçün, əgər biz Alice adlı bir obyekt verilir əgər bu gözəl ola bilməz, biz data strukturunda sağ yeri onu qoymaq istəyirəm yalnız Alice qoymaq həqiqətən gözəl olardı kimi hiss, adı birinci yeri, A ilə başlayır. Və onun adı ikinci yeri, B ilə başlayır Bob. Bir sıra ilə, və ya, bir masa ki, bir hash table zəng başlamaq edək biz məhz bunu edə bilərsiniz. Biz Alice kimi bir ad verilir varsa, Alice kimi simli, siz A-l-i-c-e yerləşir qoymaq bilərəm? Biz hueristic lazımdır. Biz Alice kimi daxil etmək funksiyası ehtiyac və cavab qaytarmaq, "bu yerdə Alice qoyun." Bu funksiya, bu qara qutusu, bir hash funksiyası adlanır gedir. A hash funksiyası, "Alice" kimi giriş edir ki, bir şey və qaytarır, adətən, bəzi data strukturunda rəqəmli yeri Alice məxsusdur yerləşir. Bu halda, bizim hash funksiyası nisbətən sadə olmalıdır. Bizim hash funksiyası hansı karakter mən qayğı lazımdır "Alice" verilir, əgər demək lazımdır? İlk. Mən [0] baxmaq, sonra [0] karakter A, əgər sayı 0 qayıtmaq deyirlər. O B varsa, 1 qayıtmaq. Onun C varsa, s 2 qayıtmaq, və. Bütün 0 indeksi, və s mənə Alice və sonra Bob və sonra Charlie daxil imkan və olardı Bu data strukturu. Amma bir problem var. Nə Anita yenidən çıxınca? Əgər Biz Anita harada qoymaq bilərəm? Onun adı da, A hərfi ilə başlayır biz bu məsələnin bir daha böyük mess etdik kimi və hiss edir. İndi data strukturu dərhal durub, daimi vaxt durub var olduqca pis halda daha xətti, ancaq bu halda Anita ilə nə edə bilər? Iki variant, həqiqətən, hansılardır? Evet? [Tələbə cavab anlaşılmaz] Okay, biz başqa ölçüsü ola bilər. Bu yaxşı. Belə ki, biz bazar ertəsi şifahi danışdıq kimi 3D şeylər inşa edə bilərsiniz. Biz burada bir giriş əlavə, lakin, bu sadə saxlamaq üçün çalışıram Güman bilər. Burada bütün məqsəd dərhal daimi zaman giriş əldə etmək ki, çox mürəkkəblik əlavə edir. Bu data strukturu Anita daxil çalışırken digər variantları hansılardır? Evet? [Tələbə cavab anlaşılmaz] Yaxşı. Belə ki, aşağı hər kəs hərəkət edə o, həqiqətən olmaq istəyir daha sonra Charlie Bob və Alice, aşağı nudges və kimi biz Anita qoydu. Əlbəttə ki, indi bu bir yan təsiri var. Bu data structure insanların bir dəfə daxil etmək istəmirəm, çünki yəqin ki, faydalı lakin biz onlar sonradan əgər yoxlamaq istəyirəm, çünki biz data strukturunda adları bütün çap istəyirsinizsə. Biz nəhayət Bu data ilə bir şey olacaq. Belə ki, indi biz o ehtimal yerdə artıq olan Alice, artıq berbat növü var. Nə Bob, nə Charlie edir. Belə ki, bəlkə bu yaxşı bir fikir deyil. Lakin, həqiqətən, bu bir variantdır. Biz hər kəs aşağı keçmək bilər və ya heck, Anita oyun gec gəldi, niyə biz yalnız Anita qoymaq deyil deyil, burada deyil, burada deyil, burada isə yalnız siyahıda bir az aşağı öz qoymaq bildirin. Amma sonra bu problem daha qalmaq başlayır. Siz onun ilk adı əsasında dərhal Alice tapa bilər. Və dərhal Bob və Charlie. Amma sonra, Anita axtarmaq və hmm bax Alice yolu var. Yaxşı, məni Alice aşağıda yoxlamaq edək. Bob Anita deyil. Charlie Anita deyil. Oh, Anita var. Və məntiq ki, qatar bütün yolu davam etsəniz, Bu yeni data strukturu tapmaq və ya Anita daxil ən pis halda çalışan zaman nə var? Bu doğru, O (n) var? Ən pis halda, çünki, Alice, Bob, Charlie var. . . bütün "Y" adına kimsə yol aşağı, belə ki, yalnız bir ləkə var buraxdı. Şükür ki, biz "Z" adlı heç bir, biz çox alt Anita qoydu. Biz həqiqətən problem həll deyil. Belə ki, bəlkə biz bu üçüncü ölçüsü təqdim etmək lazımdır. Biz bu üçüncü ölçüsü təqdim yoxsa Və bu, həyata çevirir biz mükəmməl bunu edə bilər, lakin müqəddəs grail almaq olacaq daimi zaman durub və dinamik insertions ki, biz ölçüsü 26 ağır kodu dizisi yoxdur. Biz istədiyiniz kimi bir çox adları kimi əlavə edə bilərsiniz, amma Gəlin burada 5 dəqiqə fasilə etmək və sonra düzgün edin. Bütün hüquqlar. Mən olduqca süni orada hekayə qurmaq Alice, sonra Bob və sonra Charlie və sonra Anita, seçerek onun adı aydın Alice ilə toqquşmaq gedirdi. Amma ilə bazar ertəsi günü sona çatdı sual yalnız necə ehtimal Bu cür toqquşma almaq olardı ki? Başqa sözlə, biz bu cədvəlli strukturunda istifadə başlamaq əgər, bu, həqiqətən, yalnız bir sıra deyil 26 locations bu halda, bizim giriş yerinə bərabər paylanır əgər nə? Bu süni Alice və Bob və Charlie və David deyil və s əlifba, bu eyni Z. vasitəsilə A yayılan oldu Bəlkə biz yalnız uğurlu almaq lazımdır və biz iki A və ya iki B etmək fikrində deyilik kimsə işarə çox yüksək ehtimalı ilə, həm biz ümumiləşdirilmiş bu problem deyil, əgər 0 25 lakin, demək, 0 364 və ya 65, tipik bir il gün tez-tez sayı, və sual, "bu otaq bizim iki eyni ad var ehtimalı nədir?" Başqa sözlə, ehtimal bizə iki A ilə başlayan bir adı var ki, nə var? Sual növ, eyni, lakin bu ünvan kosmik Bu axtarış yer, ad günləri halda böyükdür biz əlifba hərflərin çox il bir çox gün daha var. Bir toqquşma ehtimalı nədir? Yaxşı, biz riyaziyyat qarşı çıxış yolu figuring bu hesab edə bilər. Heç bir toqquşma ehtimalı nədir? Yaxşı, burada bu ifadə nə ehtimalı olduğunu deyir onlar unikal ad var ki, bu otaqda yalnız bir adam var, əgər? Bu 100% var. Çünki otaqda yalnız bir nəfər var, əgər onun ad günü ilin həyata 365 gün hər hansı ola bilər. Belə ki, 365/365 variantları mənə 1 dəyər verir. Belə ki, hazırda sözügedən ehtimal yalnız 1-dir. Ancaq otaq ikinci şəxs olduqda, onların ad günü fərqli ehtimalı var? Yalnız 364 mümkün gün məhəl sıçrayış il var onların ad günü üçün digər şəxslər ilə toqquşmaq deyil. Belə ki, 364/365. Üçüncü şəxs gəlir, bu, s 363/365, və. Belə ki, biz, kiçik və kiçik əldə olunur, bu fraksiyaları birlikdə vurulması saxlamaq anlamaq üçün bizə bütün unikal ad günü olduğunu ehtimal nədir? Amma sonra biz, əlbəttə, yalnız cavab almaq və onun ətrafında flip bilər və 1 minus bütün, biz nəhayət almaq lazımdır ifadə etmək Sizin math kitab geri xatırlayıram, o, bu kimi bir az bir şey görünür olan çox daha asan qrafik şərh olunur. Burada bu qrafik, x oxunda ad günü sayı var və ya ad günü olan insanlar və y ox üzrə sayı matç ehtimal edir. Və nə dedi, siz varsa, belə deyək ki, 22, 23 kimi bir şey seçə imkan verir. Otaq, 22 və ya 23 nəfər, varsa o çox az adam iki eyni ad üçün gedir ehtimalı combinatorially, həqiqətən, super yüksək. 50% bahis ki, praktiki olaraq yalnız 22 nəfər, seminar, bir sinif, Insanların 2 eyni ad üçün gedir. Çünki eyni ad ola bilər ki, bir çox yolları var. Hətta pis, siz chart və sağ tərəfdən baxsaq, zaman siz onu 58 tələbələri ilə bir sinif var ad olan 2 nəfər ehtimalı super, super yüksək, təxminən 100%-dir. İndi ki, real həyatı haqqında bir əyləncə fakt növ var. Ancaq təsiri, indi data strukturları və saxlanılması məlumat yalnız məlumatların bir gözəl, təmiz, bərabər yayılması var fərz o deməkdir ki, və şeyi bir dəstə uyğun bir böyük kifayət qədər array var Siz unikal yerlərdə insanların almaq olacaq demək deyil. Siz toqquşma var olacaq. , Bu deyilən kimi, hashing bu anlayışı Belə "Alice" kimi daxil alaraq və bir şəkildə masaj və sonra 0 və ya 1 və ya 2 kimi bir cavab geri almaq. Ki, funksiya bəzi çıxış geri almaq toqquşması bu ehtimalı ilə mürəkkəbləşdirilir olunur. Belə ki, necə biz bu toqquşma idarə edə bilərsiniz? Yaxşı, bir halda da, biz təklif edilib ki, ideya bilər. Biz yalnız bir az daha sadəcə, bəlkə hər kəs aşağı keçmək, və ya deyil, başqa hərəkət hər kəs çox isə yalnız mövcud spot altına Anita hərəkət edək. Alice 0 Yəni əgər, Bob 1 deyil, Charlie, 2 deyil biz yalnız yeri 3 Anita qoymaq lazımdır. Bu probing xətti deyilən data strukturlarında bir texnikadır. Yalnız bu xətt gəzinti edirik, siz probing növ istəyirik Xətti çünki məlumat tərkibində mövcud ləkələr üçün. Əlbəttə, bu, O (n) daxil devolves. Məlumat struktur həqiqətən tam varsa, bu 25 nəfər artıq var və sonra Anita çıxınca, o yeri Z olacaq nə başa və gözəl edir. O, hələ də uyğun, biz sonra onun tapa bilərsiniz. Amma bu şeyi sürətləndirmək məqsədi zidd idi. Yerine bu üçüncü ölçüsü təqdim nə olur? Bu texnika ümumiyyətlə ayrı-ayrı chaining adlanan və ya zəncirlər olan edilir. Və bir hash table, indi bu cədvəlli strukturunda nə Sizin masa yalnız göstəricilər bir sıra edir. Amma nə bu göstəricilər qeyd tahmin nədir? A bağlı siyahısı. Biz bu dünyanın, həm də ən yaxşı almaq nə olur? Biz ilkin göstəriciləri üçün seriallarda istifadə məlumat strukturu biz dərhal, [1], [30] və ya s [0] bilərsiniz lakin biz bəzi rahatlıq var və biz Anita və Alice və Adəm uyğun olar ki, və digər bir adı, biz əvəzinə digər ox özbaşına inkişaf edək. Və biz nəhayət, Bazar ertəsi kimi, bağlı siyahı ilə ifadə qabiliyyəti var. Biz qanunsuz məlumat strukturu inkişaf edə bilər. Alternativ olaraq, biz yalnız böyük 2-ölçülü array edə bilər lakin əgər bir dəhşətli vəziyyət olacaq 2 ölçülü array satırları bir onun adı A. ilə başlamaq olur əlavə şəxs üçün kifayət qədər böyük deyil Allah biz böyük 2-ölçülü struktur təkrar bölüşdürə var A adına bir çox insanlar var yalnız Z bir şey adına belə bir neçə nəfər var xüsusilə. Bu yalnız bir çox seyrək data quruluş olacaq. Belə ki, hər hansı bir vasitə ilə mükəmməl deyil, lakin indi biz ən azı imkanı var Alice ya Anita aid olduğu dərhal tapmaq, ən azı şaquli ox baxımından, və biz yalnız bu bağlı siyahısında Anita ya Alice qoymaq yerləşir qərar var. Biz şeyi çeşidlənməsi haqqında qayğı yoxdur, nə qədər tez biz bu kimi bir strukturu Alice daxil edə bilər? Bu daimi zamanı. [0] daxil Biz indeksi, və heç bir var, əgər Alice ki bağlı siyahı əvvəlində gedir. Lakin böyük bir məşğul deyil. Anita sonra çıxınca əgər Çünki addımlar bir sıra sonra, Anita Ü aid deyil? Yaxşı, [0]. Oop. Alice ki bağlı siyahı artıq. Amma biz bu adlar çeşidlənməsi haqqında qayğı yoxsa, biz yalnız Alice üzərində, insert Anita hərəkət edə bilər, lakin hətta daimi dəfə. Alice və Adəm və bütün bu digər bir adları var belə həqiqətən fiziki onlara dəyişkən deyil. Niyə? Biz yalnız bilən bağlı siyahısı ilə burada Çünki bu qovşaqlarının hər halda var idi? Siz bütün çörək qırıntıları hərəkət edir. Ətrafında okları hərəkət, siz fiziki ətrafında hər hansı bir məlumat hərəkət yoxdur. Beləliklə, biz dərhal, bu halda, Anita əlavə edə bilərsiniz. Sabit vaxt. Beləliklə, biz daimi zaman axtarış və Anita kimi kimsə daim zaman durub var. Amma dünya oversimplifying cür. Biz sonra Alice tapmaq istəyirsinizsə? Biz sonra Alice tapmaq istəyirsinizsə? Neçə addımlar ki, iştirak edir? [Tələbə cavab anlaşılmaz] Exactly. Də bağlı siyahısında Alice əvvəl insanların sayı. Bizim data strukturu, yenidən, bu şaquli çıxışı var, çünki Belə ki, kifayət qədər mükəmməl deyil və sonra asma bu bağlı siyahıları var - əslində isə bu bir sıra çəkmək deyil bildirin. Bu bağlı siyahıları bu kimi bir az bir şey görünür ki, bu off asma etdi. Ancaq problem varsa, Alice və Adəm və bütün bu digər bir adları orada daha çox başa, kimsə addımlar dəstə alaraq ola bilər tapmaq, , siz bağlı siyahı axır var bcause bir xətti əməliyyatdır. Belə ki, həqiqətən, sonra durub zaman nəticədə n siyahısına elementlərinin sayı yerləşir O (n) edir. Bölünür, in özbaşına bu m bağlı siyahıları sayı yerləşir m, zəng edək biz bu şaquli ox var ki. Başqa sözlə, biz həqiqətən adları bərabər yayılması güman əgər, tamamilə qeyri-real. Daha bir məktub açıq-aydın daha var. Amma biz an vahid paylanması üçün güman əgər, və biz ümumi insanlar, və m ümumi zəncir n Bu zəncir hər bizə mövcud, sonra uzunluğu ədalətli sadəcə ümumi, n zəncirlər sayı bölünür olacaq. Belə n / m. Biz bütün riyazi ağıllı ola bilər Lakin burada. Bu sabit sayı var, çünki m, daimi deyil. Siz əvvəlində sizin array bəyan olacaq və biz boyutlandırma şaquli ox deyilik. Anlayışı ilə, müəyyən edilir ki,. Bu dəyişən ki, danışmaq, yalnız üfüqi ox var. Belə ki, texniki, bu daimi deyil. Belə ki, indi durub dəfə olduqca çox O (n) edir. Belə ki, bütün daha yaxşı hiss etmir. Amma həqiqət burada nə var? Yaxşı, bütün bu vaxt, həftə, deyirdik olduğunuz O (n ²). O (n), 2 x n ², - n, 2 bölünür. . . ech. Bu, sadəcə n ² var. Amma indi dövr bu hissəsində, biz daha real dünya haqqında danışmağa başlaya bilərsiniz. Və n / m yalnız tək n artıq tamamilə daha sürətli edir. Bir min adları var, və çox buketler onları parçalamaq edin siz bu zəncirlər hər yalnız on adları var ki, tamamilə on şeyi axtarış min şey daha sürətli olacaq. Və qarşıdakı problem dəstdən birini siz etiraz edir məhz bu barədə düşünmək belə olsa, evet, asimptotik və riyazi, hələ də yalnız xətti deyil, şeyi tapmaq üçün çalışırıq zaman ümumi gücünü zaptetti. Əslində, bu çox daha sürətli olacaq çünki bu bölən edir. Və yenə bu ticarət-off olmalıdır olacaq və nəzəriyyəsi və reallıq arasındakı bu münaqişə, və kulplar bir dövr bu nöqtədə dönüş başlayacaq biz növ semster sonuna hazırlamaq kimi reallıq bir daha çox, biz web proqramlaşdırma dünya tanıtmaq kimi istifadəçilər üçün gedir çünki yerləşir həqiqətən, performans saymaq gedir yoxsul dizayn qərarları hiss təşəkkür başlayın. Bir bağlı həyata haqqında Belə ki, necə getmək yoxdur - bir hash table 31 elementləri ilə? Və əvvəlki Məsələn ad günləri haqqında əsassız idi. Kimsə 1 Yanvar və ya Fevral 1 ad varsa, bu bucket onları qoymaq lazımdır. Yanvar 2, 2 fevral, 2 mart varsa, bu bucket onları qoymaq lazımdır. 31 səbəb olmuşdur. Necə bir hash table bəyan edirsiniz? Bu olduqca sadə ola bilər, node * masa üçün mənim ixtiyari adı, [31] edir. Bu qovşaqlarının mənə 31 göstəricilərinə verir və mənə bağlı siyahıları 31 göstəricilərinə üçün imkan verir ki, o zəncirlər ilkin NULL, hətta əgər. Mən saxlamaq istəyirsinizsə, mən "Bob", "Charlie" "Alice" qoymaq üçün nə istəyirsiniz? Bəli, biz bir quruluş olan şeyi kesmek lazımdır biz Alice, Bob qeyd etmək Charlie qeyd etmək və s. lazımdır, çünki Biz yalnız tək adları ola bilməz, belə ki, mən burada node adlı yeni struktur yarada bilər. Faktiki node nədir? Bu yeni bağlı siyahısında node nədir? Söz adlı ilk şey, bu şəxsin adı üçün. BOY, ehtimalla, bir insan adı maksimum uzunluğu aiddir ki, nə olursa olsun, 20, crazy künc hallarda 30, 40 simvol və +1 nə üçün vacibdir? Bu, sadəcə əlavə NULL xarakteri, \ 0 var. Belə ki, bu düyün, içərisində özünü "bir şey" wrapping edir lakin sonrakı adlı göstərici bəyan biz Charlie Bob üçün zəncir Alice bilər və s edir. NULL ola bilər amma mütləq olmalıdır deyil. Bu hash masalar hər hansı suallar? Evet? [Tələbə anlaşılmaz, sualı] Bir sıra - yaxşı sual. Niyə bir sıra daha çox yalnız char * Bu char söz? Bu qədər əsassız Məsələn, mən müraciət etmək istəmir orijinal adları hər malloc üçün. Mən string üçün yaddaş maksimum məbləği bəyan istədi Mən Alice \ 0 və malloc və pulsuz və kimi ilə məşğul olan strukturu surəti bilər ki. I yer istifadə daha şüurlu olmaq istəyirdi, lakin mən bunu bilər. Sual Yaxşı. Belə ki, bu uzaq ümumiləşdirmək üçün cəhd edək və ümumiyyətlə data strukturları bu gün qalan diqqət və eyni əsaslar istifadə həll edə bilər ki, digər problemləri hətta data strukturları baxmayaraq öz özəllikləri fərqlənə bilər. Belə ki, kompüter çıxır, ağaclar çox rast gəlinir. Və siz, bir ailə ağac kimi bir ağac növ hesab edə bilər bəzi kökləri, bəzi matriarch ya patriarx var olduğu nənə və ya baba və ya əvvəllər geri, hansı altında ana və dad və ya müxtəlif bacı və ya bu kimi var. Belə ki, bir ağac strukturu qovşaqlarının var və övladı var hər node üçün adətən 0 və ya daha çox uşaq. Və jarqon bəzi burada bu şəkil bax edir kənarları haqqında kiçik uşaq və ya grandkids hər hansı kim onlardan qaynaqlanan heç bir oxlar var o deyilən yarpaq, və daxili hər kəs var daxili node edir; siz bu xətt bir şey zəng edə bilərsiniz. Amma bu quruluşu olduqca ümumi. Bu bir az ixtiyari var. Biz sağ üç övladı var, sol bir uşaq var altındakı iki övladı qaldı. Belə ki, biz hər şeyi standartlaşdırmaq başlamaq əgər müxtəlif ölçülü ağaclar var, ancaq və bir əvvəlki qısa olan binar axtarış Patrick video bu xatırlayıram bilər online, ikili axtarış bir sıra ilə həyata keçiriləcək yoxdur bir yazı taxtası üzrə kağız və ya ədəd. Bir daha mürəkkəb data strukturunda nömrələri saxlamaq istədiyini düşünək. Bu kimi bir ağac yarada bilər. Siz C elan node ola bilər ki, node daxilində bu ən azı iki elementləri ola bilər. Bir siz saxlamaq istədiyiniz nömrə və digər - yaxşı, biz bir daha lazımdır. Digər onun uşaqlar var. Belə ki, burada başqa data strukturu var. Bu dəfə bir node n bir sıra saxlanılması kimi müəyyən edilir və sonra iki göstəricilərinə; sol uşaq və sağ uşaq. Onlar özbaşına deyilik. Bu ağac haqqında maraqlı var? Biz Patrick onun video onu müəyyən necə bu müəyyən və ya sonra necə model nədir? O, burada bəzi çeşidlənməsi olduğunu cür Aşkar var lakin sadə qayda var? Evet? [Tələbə cavab anlaşılmaz] Mükəmməldir. Bu nəzər, siz, sol kiçik nömrələri bax böyük sol nömrələri, lakin hər node üçün doğru. Hər node üçün, artıq onun sol uşaq az və çox hüququ uşaq daha. Mən sayı 44, demək, bu data structure axtarmaq istəyirsinizsə, Bu artıq o deməkdir ki, Mən, çünki indi bu daha mürəkkəb data strukturları bütün kimi, kök başlamaq üçün biz yalnız başlanğıcdır, bir şey bir göstərici yoxdur. Və bu halda, əvvəlində kök edir. O, sol son deyil Bu struktur kökü var. Mən burada 55 var bax, mən 44 arıyorum. Hansı istiqamətdə mən getmək istəyirəm? Aydındır ki, doğru çox böyük olacaq, çünki Bəli, mən, sol getmək istəyirəm. Belə ki, burada qeyd, siz konseptual yarısında ağac Doğrama növ istəyirik Siz sağ enən heç etdiyiniz çünki. Belə ki, indi mən 55-dən 33-gedin. Bu bir sıra çox kiçik. Mən 44 arıyorum, indi mən 44 bu ağac olsa, mən sağa aşkar edə bilərsiniz bilirik. Belə ki, yenə, mən budama yarısında ağac edirəm. Bu telefon kitab konseptual olduqca çox eyni deyil. Bu, biz yazı taxtası üzrə sənədləri ilə nə eyni deyil amma bu bizə həqiqətən imkan verir ki, bir daha mürəkkəb strukturu var Bu, bölmək və alqoritmi dizayn fəth və əslində, belə bir struktur traversing - whoops. Bu kimi bir quruluş traversing, yalnız olduğu "bu yolla getmək və ya yol getmək" bölməsində bu həyata keçirərkən ilk fikrinizi əyilmiş bütün kod deməkdir və ya, recursion ya iteration istifadə edərək, ikili axtarışı üçün, evdə vasitəsilə gəzinti bu boyun bir ağrı var. Orta element tap, sonra yuvarlaqlaşdırma yuxarı və ya aşağı edin. İndi yenidən recursion istifadə edə bilərsiniz, çünki bir gözəllik, bu var lakin daha çox pakizə. Həqiqətən, siz sayı 55 istəyirik və 44 tapmaq istəyirsinizsə, Bu halda sola getmək, sonra nə etməliyəm? Siz eyni alqoritmi axır. Siz node dəyəri yoxlamaq, sonra sol və ya sağ getmək. Sonra sol və ya sağ gedin node dəyəri yoxlayın. Bu mükəmməl recursion uyğun. Belə ki, hətta keçmişdə biz recursion cəlb bəzi ədalətli ixtiyari nümunələri etdik ki, data stuctures ilə recursive olmalıdır etməyib xüsusən ağaclar, bir problem alaraq bu fikri mükəmməl bir proqram var bu daralır və sonra eyni tipli, lakin kiçik, proqram həlli. Belə ki, təqdim edə bilər ki, başqa data strukturu var. Bu sirli baxmaq ilk baxışda nəzərdə, lakin bu, bir gözəl edir. Belə ki, bu, söz axtarış miras olan trie, trie adlı data strukturu yenidən cəhd-val elan, lakin dünyada bunlar çağırır nə deyil. Çalışır. T-r-i-e. Bəzi növ ağac strukturu, lakin trie ildə qovşaqlarının hər nə görünür? Bu qısaldılmış növü var, çünki bu bir az yanlışdır. Lakin bu trie hər node həqiqətən bir sıra kimi görünür. Və baxmayaraq bu diaqram müəllifidir, o, göstərilən deyil Bu halda, bu trie kimin məqsədi həyat sözlər saxlamaq üçün bir data strukturu A-l-i-c-e və ya B-o-b kimi. Və yol olan s Bu data mağazalar Alice və Bob və Charlie və Anita və ki, bir trie Alisa saxlamaq vasitəsi bir sıra istifadə edir biz bir sıra kimi görünür olan kök node-da başlayacaq və stenoqrafiya notation yazılı oldu. Ilə heç bir adı var idi, çünki müəllif abcdefg çıxarılmışdır. Onlar yalnız M və P və T göstərdi, lakin bu halda, nin burada olan bəzi adların səfərdə Alice və Bob və Charlie hərəkət edək. Maxwell bu sxemdə əslində. Belə ki, necə müəllifi mağaza etdi M-a-x-w-e-l-l? O, kök node başladı və getdi [M], belə ki, təxminən 13-sıra 13 yer. Sonra oradan bir göstərici yoxdur. Başqa array gedən bir göstərici. Oradan müəllifi, sol üst orada təsvir kimi, yer A ki massivinə dizine və o, və ya o, başqa bir sıra ki, pointer sonra və yeri X. da pointer getdi Sonra s növbəti array yeri W, E, L, L, və, və nəhayət, in əslində bu şəkil qoymaq edək. Kodu kimi bir node baxmaq nə? Bir trie bir node daha qovşaqlarının üçün göstəricilər bir sıra var. Amma ən azı bu həyata, boolean dəyər bir növ var var. Mən bunu is_word zəng etmək üçün baş verir. Niyə? Siz Maxwell daxil olduğunuz zaman daxil deyilik Çünki Bu data strukturu şey. Siz X. yazılı deyilik M. yazılı deyilik Siz yapýyorsun bütün göstəricilər aşağıdakı edir. Sonra M, A təmsil göstəricisidir təmsil edən göstərici sonra X, W, E, L, L, təmsil göstəricisidir lakin nə sonunda nə etmək lazımdır kontrol getmək növ, mən bu yeri çatıb. Məlumat strukturunda burada bitir bir söz var idi. Belə ki, nə bir trie həqiqətən dolu və müəllif təmsil seçdi olunur az üçbucaq bu terminuses. Əsl Bu yalnız faktı bu üçbucağı burada o deməkdir ki, bu boolean dəyər Siz ağac geri getmək əgər deməkdir ki Maxwell bu deyil adlı bir söz deməkdir. Məsələn Amma söz foo, , ağac deyil mən üst qədər burada kök node-da başlayacaq əgər, çünki Heç bir f pointer, heç o pointer, heç o göstərici var. Foo bu lüğət bir ad deyil. Amma əksinə, turing, t-u-r-i-n-g. Yenə t və ya u və ya r ya i və ya n və ya g saxlaya bilmədi. Amma aşağı burada bu node doğru yol dəyəri Bu data tərkibində mağaza idi - ağac ilə doğru üçün is_word bu boolean dəyər yaradılması. Belə bir trie, bu çox maraqlı meta strukturunun növ həqiqətən lüğət bu cür sözləri özləri saxlanılması deyilik yerləşir. Aydın olmaq üçün, yalnız bəli ya heç saxlanılması edirik, burada bitir bir söz var. İndi dolayısı nə var? Siz yaddaşında saxlamaq üçün çalışdığınız bir lüğətdə 150,000 sözlər varsa bir bağlı siyahısı kimi bir şey istifadə edərək, Siz bağlı siyahısında 150,000 qovşaqlarının üçün gedir. Və əlifba sırası ilə bu sözlər bir tapmaq O (n) vaxt bilər. Xətti vaxt. Amma trie burada halda, bir söz tapmaq çalışan zaman nə var? Burada gözəllik çıxır ki, siz artıq bu lüğətdə 149.999 sözlər, olsa belə Bu data strukturu ilə həyata ki, daxil, Alice kimi, Alice bir daha şəxs tapmaq və ya əlavə etmək üçün nə qədər vaxt lazımdır? Yaxşı, bu arxada xarakter üçün bəlkə 6 addımlar yalnız 5 var. Çünki tərkibində digər adları presense Alice daxil yolu ilə almaq deyil. Bundan başqa, Alice tapmaq bu lüğətdə 150,000 sözlər var dəfə , bütün Alice tapmaq yolla almaq deyil Alice çünki. . . . . burada, çünki mən bir boolean dəyər tapdı. Və heç boolean doğru, sonra Alice olduqda sözlər Bu data struktur deyil. Başqa sözlə, bu yeni daxil şeyi şeyi tapmaq və daxil olan çalışan zaman trie data strukturu O - bu n deyil. 150,000 nəfər presense Alice heç bir təsiri var, çünki görünür. Nin bu k İngilis söz maksimum uzunluğu olduğu k, zəng Belə bildirin hansı adətən artıq 20-bir simvol çoxdur. Belə ki, k sabit deyil. Müqəddəs grail Beləliklə, biz artıq aşkar görünür edər bir trie, daimi vaxt ki silme üçün lookups üçün edir. Çünki artıq strukturunda şeyi sayı hətta fiziki yoxdur. Yenə yalnız off yoxlanılır və sort edirik, bəli və ya xeyr, gələcək çalışan zaman heç bir təsiri yoxdur. Amma tutmaq olmalıdır var, əks halda biz çox vaxt sərf olmazdı Bütün bu digər strukturlar üzrə yalnız nəhayət gözəl olan gizli bir almaq. Yaxşı qiymət biz burada bu böyüklük nail ödəyir? Space. Bu şey kütləvi deyil. Və səbəbi müəllifi burada təqdim etməmiş, qeyd seriallarda kimi baxmaq ki, bu şeyi ki, O ağac istirahət trie qalan, cəlb etməyib onlar yalnız hekayə müvafiq deyilik, çünki. Lakin bu qovşaqlarının bütün geniş super və ağac hər node tutur 26 və ya faktiki olaraq, bu halda mən apostrof üçün yer daxil olmaqla, çünki 27 simvol ola bilər belə ki, biz apostrophized sözləri ola bilər. Bu halda, bu geniş Diziler var. Onlar picutured deyilik Belə ki, baxmayaraq ki, Bu RAM kütləvi məbləği alır. Hansı müasir hardware especilly, gözəl ola bilər ancaq tradeoff var. Biz daha çox yer xərcləyərək az vaxt almaq. Belə ki, bu bütün gedir? Yaxşı, nə edək - burada bax edək. Burada bu oğlan bir jump etmək edək. Iman və ya, C indi bir neçə dəfə olub kimi çox fun, daha müasir şeyə keçid zaman olduğu dövr çatma nöqtəsində edirik. Yüksək səviyyədə şeylər. Və hətta həftə növbəti neçə olsa biz hələ göstəricilərinə və yaddaş idarə dünyada özümüzü batırmaq davam edəcəyik biz sonra qurmaq bilər ki, rahat almaq üçün, sonunda oyun Bu dil, istehzayana deyil, təqdim etmək, son nəticədə edir. Biz HTML söhbət 10 dəqiqə kimi xərcləmək lazımdır. HTML bütün biçimlendirme dili, və nə bir biçimlendirme dili "Bu qalın edin 'deyə açıq Mötərizədə və qapalı Mötərizədə bu sıra "Bu mərkəzli etmək 'Bu italik etmək'. ' Bu bütün intellektual maraqlı deyil, lakin faydalı super deyil. Və əlbəttə, bu gün hər yerdə var. Amma nə HTML dünya haqqında güclü və web proqramlaşdırma ümumiyyətlə, dinamik şeylər qurur; PHP və ya Python və ya Ruby və ya Java və ya C # kimi dillərdə kodu yazmaq. Həqiqətən, hər hansı seçdiyiniz dil və dinamik HTML yaradan. Dinamik CSS deyilən bir şey yaradan. Cascading stillər, estetik də edir. Və baxmayaraq, bu gün mən tanış Google.com kimi bəzi veb getmək əgər və mən, bəlkə əvvəl görülən etdiyiniz geliştirici, görünüşü mənbə, keçirmək üçün getmək lakin mənbə keçirmək üçün gedir, bu məhsulları yəqin ki, olduqca sirli görünür. Amma bu Google.com həyata keçirir əsas kodu. Ön sonuna. Və həqiqətən bütün bu qabarıq estetik stuff deyil. Burada CSS edir. Mən aşağı scrolling saxlamaq, biz bir renk kodlu məhsulları almaq lazımdır. Bu HTML edir. Google kodu mess kimi görünür, amma əslində fərqli bir pəncərə açmaq əgər biz bu bəzi struktur bilərsiniz. Mən bu açmaq varsa, burada qeyd, bir az daha oxunaqlı deyil. Biz əvvəl bu tag görmək olacaq, [söz] bir tag edir HTML, baş, bədən, div, script, mətn sahəsi, span, mərkəzi, div. Bu da, ilk baxışdan sirli görünüşlü və sort edir lakin bu mess bütün müəyyən nümunələri və repeatable nümunələri aşağıdakı bir dəfə biz əsasları aşağı almaq, belə ki, bu kimi kod yazmaq edə bilərsiniz və sonra JavaScript adlı başqa bir dil istifadə edərək, bu kimi kodu manipulyasiya. Və JavaScript browser daxilində çalışan bir dil Google xəritələri istifadə edir ki, əlbəttə alver alət Harvard kursları, istifadə ki, bu gün siz dinamizm bütün dəstə vermək, Facebook, ani statusu yenilikləri göstərmək verir Twitter anında tweets göstərmək üçün istifadə edir. Bütün bu özümüzü daxil batırmaq başlayacaq Amma almaq üçün biz Internet haqqında bir az bir şey anlamaq lazımdır. Burada Bu klip yalnız uzun bir dəqiqə və indi bu əslində kəsb edək, İnternet gəlmək haqqında nə üçün bir iltifat kimi çalışır. Mən sizə "Net və Warriors". Vermək [♫ Slow xor musiqi ♫] [Kişi dastançı] O bir mesaj gəldi. Protokol bütün öz ilə. [♫ Faster elektron musiqi ♫] O, yönlendirici uncaring, sərin firewall dünya gəldi və ölüm çox pis təhlükələr. O, sürətli. O, güclü deyil. O, TCP / IP, və o ünvan var. Net və Warriors. [Malan] Sonrakı həftə sonra. İnternet. Web proqramlaşdırma. Bu CS50 edir. [CS50.TV]