1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [MUSIC PLAYING] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID MALAN: Bu CS50 edir. 5 00:00:14,010 --> 00:00:18,090 Bu başlanğıc və həm də sanki demək olar ki, sonuna kimi lazımdır, çünki 6 00:00:18,090 --> 00:00:18,825 Həftə altı. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Mən bölüşmək istədiyiniz düşündüm bir əyləncə fakt az. 9 00:00:22,640 --> 00:00:25,370 Mən bu qədər çıxardı etdik Son semestr data seçin. 10 00:00:25,370 --> 00:00:29,710 Biz hər sizi xahiş ki geri bilər p set form online seyr etdik əgər 11 00:00:29,710 --> 00:00:31,580 və ya şəxs iştirak etdik, əgər. 12 00:00:31,580 --> 00:00:33,020 Və burada data deyil. 13 00:00:33,020 --> 00:00:34,710 Belə ki, bu gün çox gözlənilən idi. 14 00:00:34,710 --> 00:00:37,126 Amma biz bir az sərf istədi zaman sizinlə yenə. 15 00:00:37,126 --> 00:00:40,599 Niyə hər kəs bu zənn istəyirsiniz graph, aşağı, aşağı, belə jaggy edir 16 00:00:40,599 --> 00:00:41,265 belə ardıcıl? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Nə zirvələri hər şeyi və çökəkliklər təmsil edir? 19 00:00:45,130 --> 00:00:46,005 >> Auditoriya: [işitilemez] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID MALAN: Həqiqətən. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Və daha çox gülməli, Allah qorusun, biz bir cümə günü bir mühazirə 24 00:00:55,480 --> 00:00:58,960 semestr əvvəlində, ki, biz nə görürük budur. 25 00:00:58,960 --> 00:01:03,430 Belə ki, bu gün biz bir az iştirak data strukturları haqqında daha çox. 26 00:01:03,430 --> 00:01:06,660 Və bir bərk daha vermək beş problemlərin ruhi model, 27 00:01:06,660 --> 00:01:07,450 indi deyil. 28 00:01:07,450 --> 00:01:10,817 Bad yazımlar, orada, biz will bir mətn faylı əl bəzi 100,000 29 00:01:10,817 --> 00:01:12,650 plus İngilis dili sözlər, və Siz olacaq 30 00:01:12,650 --> 00:01:17,770 Ağılla onları yüklemek üçün necə anlamaq üçün yaddaş daxil, RAM, bəzi data istifadə edərək, 31 00:01:17,770 --> 00:01:19,330 Seçdiyiniz strukturu. 32 00:01:19,330 --> 00:01:22,470 >> İndi belə bir data strukturu bilər olmamalıdır yəqin ki, lakin, 33 00:01:22,470 --> 00:01:25,630 Bu kifayət qədər sadə bağlı siyahı, biz son dəfə təqdim etdi. 34 00:01:25,630 --> 00:01:29,220 Və bir bağlı siyahı azı idi bir sıra üzərində bir üstünlüyü. 35 00:01:29,220 --> 00:01:32,096 Bir üstünlüyü nədir arguably bir bağlı siyahı? 36 00:01:32,096 --> 00:01:32,950 >> Auditoriya: Insertion. 37 00:01:32,950 --> 00:01:33,908 >> DAVID MALAN: Insertion. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Siz nə deməkdir? 40 00:01:35,196 --> 00:01:37,872 >> Auditoriya: Yerdə boyunca siyahısı [Işitilemez]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID MALAN: Yaxşı. 42 00:01:38,770 --> 00:01:42,090 Belə ki, bir element yerdə əlavə edə bilərsiniz Siz siyahısı ortasında istəyirik 43 00:01:42,090 --> 00:01:45,490 bir şey shuffle olmadan, Hansı ki, biz sıralayaraq, bağlanmış 44 00:01:45,490 --> 00:01:47,630 müzakirələr deyil mütləq yaxşı bir şey, 45 00:01:47,630 --> 00:01:51,200 Bu vaxt tələb edir, çünki həqiqətən hərəkət bu insan bütün sol və ya sağ. 46 00:01:51,200 --> 00:01:55,540 Və belə bir bağlı siyahısı ilə, siz yalnız malloc ilə ayrılması, yeni node, 47 00:01:55,540 --> 00:01:58,385 və sonra bir neçə yeniləmə göstəricilərinə iki, üç əməliyyatlar max-- 48 00:01:58,385 --> 00:02:01,480 və biz kimsə slot edirik siyahısına daxil hər yerdə. 49 00:02:01,480 --> 00:02:03,550 >> Nə sərfəli idi bir bağlı siyahısı haqqında? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Bəli? 52 00:02:05,659 --> 00:02:06,534 >> Auditoriya: [işitilemez] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID MALAN: Perfect. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Perfect. 57 00:02:11,090 --> 00:02:12,070 Bu, həqiqətən dinamik. 58 00:02:12,070 --> 00:02:15,100 Və törətməkdə deyilik ki, əvvəlcədən bəzi sabit ölçüsü 59 00:02:15,100 --> 00:02:18,750 yaddaş yığın, kimi olardı bir sıra ilə, alt üçün olan 60 00:02:18,750 --> 00:02:22,455 Siz yalnız qovşaqlarının ayıra bilər ki, tələb bununla yalnız çox yer istifadə 61 00:02:22,455 --> 00:02:23,330 Siz, həqiqətən, ehtiyac kimi. 62 00:02:23,330 --> 00:02:26,830 Bir sıra fərqli olaraq, siz bilər təsadüfən çox az ayrılması. 63 00:02:26,830 --> 00:02:28,871 Və o, yalnız gedir boyun bir ağrı olmaq 64 00:02:28,871 --> 00:02:32,440 yeni böyük bir sıra təkrar bölüşdürə, surəti hər şey üzərində, köhnə array pulsuz 65 00:02:32,440 --> 00:02:33,990 və sonra iş haqqında hərəkət. 66 00:02:33,990 --> 00:02:37,479 Və ya pis, siz yol ayrılması bilər Siz, həqiqətən, ehtiyac daha çox yaddaş, 67 00:02:37,479 --> 00:02:40,520 və belə bir çox olacaq belə danışmaq, array seyrək əhalinin. 68 00:02:40,520 --> 00:02:44,350 >> Belə ki, bir bağlı siyahı bu verir dinamizm və rahatlıq üstünlükləri 69 00:02:44,350 --> 00:02:46,080 insertions və silme ilə. 70 00:02:46,080 --> 00:02:48,000 Amma şübhəsiz ki, ödənilən qiymət olmalıdır. 71 00:02:48,000 --> 00:02:50,000 Mövzular əslində, bir viktorina sıfır tədqiq 72 00:02:50,000 --> 00:02:52,430 idi ticarət-off bir neçə biz belə uzaq gördüm. 73 00:02:52,430 --> 00:02:56,161 Belə ki, bir ödənişli qiyməti və ya nə bir bağlı siyahı aşağı istiqamətli? 74 00:02:56,161 --> 00:02:56,660 Bəli. 75 00:02:56,660 --> 00:02:57,560 >> Auditoriya: Xeyr təsadüfi giriş. 76 00:02:57,560 --> 00:02:58,809 >> DAVID MALAN: No təsadüfi giriş. 77 00:02:58,809 --> 00:02:59,540 Amma kimin umurunda? 78 00:02:59,540 --> 00:03:01,546 Random access çekici səs deyil. 79 00:03:01,546 --> 00:03:02,421 >> Auditoriya: [işitilemez] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID MALAN: Exactly. 82 00:03:05,740 --> 00:03:07,580 Siz istəyirsinizsə müəyyən bir alqoritm 83 00:03:07,580 --> 00:03:10,170 və mənə həqiqətən təklif edək Xüsusilə ikili axtarış, olan 84 00:03:10,170 --> 00:03:12,600 biz bir bit istifadə etdiyiniz biridir Siz təsadüfi çıxışı yoxdur, əgər, 85 00:03:12,600 --> 00:03:15,516 Siz sadə hesab edə bilməz orta element kimi tapmaq 86 00:03:15,516 --> 00:03:16,530 və ona doğru jumping. 87 00:03:16,530 --> 00:03:20,239 Siz əvəzinə ilk başlamaq üçün element və xətti sol axtarış 88 00:03:20,239 --> 00:03:22,780 sağ tapmaq istəyirsinizsə orta və ya hər hansı digər element. 89 00:03:22,780 --> 00:03:24,410 >> Auditoriya: Bu yəqin ki, daha çox yaddaş tutur. 90 00:03:24,410 --> 00:03:25,040 >> DAVID MALAN: daha çox yaddaş edir. 91 00:03:25,040 --> 00:03:27,464 Harada əlavə edir yaddaş gələn başa? 92 00:03:27,464 --> 00:03:28,339 >> Auditoriya: [işitilemez] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID MALAN: Exactly. 95 00:03:33,440 --> 00:03:35,679 Burada bu halda, biz idi integers üçün bir bağlı siyahı 96 00:03:35,679 --> 00:03:37,470 və hələ biz misli edirik yaddaş həcmi 97 00:03:37,470 --> 00:03:39,680 biz də bu göstəricilərinə saxlamaqla lazımdır. 98 00:03:39,680 --> 00:03:42,090 Kimi bir böyük İndi az Sizin structs böyük almaq 99 00:03:42,090 --> 00:03:45,320 və bir sıra saxlanılması edirik lakin bəlkə bir tələbə və ya digər obyekt. 100 00:03:45,320 --> 00:03:46,880 Amma nöqtə əlbəttə qalır. 101 00:03:46,880 --> 00:03:49,421 Və belə bir sıra əməliyyatları bağlı siyahıları çağırıldı 102 00:03:49,421 --> 00:03:50,570 n xətti böyük O idi. 103 00:03:50,570 --> 00:03:54,730 Taxılması və ya axtarış kimi Things və ya halda bir element silinməsi 104 00:03:54,730 --> 00:03:57,720 çox sonunda oldu Bu sıralanır və ya deyil olub siyahısı. 105 00:03:57,720 --> 00:04:01,167 >> Bəzən uğurlu almaq və bilər bu əməliyyatlar belə aşağı həddi 106 00:04:01,167 --> 00:04:04,250 değilseniz də daimi vaxt ola bilər həmişə ilk element baxaraq, 107 00:04:04,250 --> 00:04:05,070 məsələn. 108 00:04:05,070 --> 00:04:09,360 Amma nəticədə, biz vəd müqəddəs grail nail olmaq üçün 109 00:04:09,360 --> 00:04:12,630 data strukturları, və ya bəzi uyğunlaşdırılması onların, 110 00:04:12,630 --> 00:04:14,290 daimi vaxt yolu ilə. 111 00:04:14,290 --> 00:04:17,579 Biz elementləri tapmaq və ya elementləri əlavə edə bilərsiniz və ya bir siyahıdan elementləri aradan qaldırılması? 112 00:04:17,579 --> 00:04:19,059 Biz kifayət qədər tezliklə görəcəksiniz. 113 00:04:19,059 --> 00:04:21,100 Və bir çıxır Biz istəyirik mexanizmlərinin 114 00:04:21,100 --> 00:04:23,464 Bu gün istifadə başlamaq niyyətindədir, p illik istifadə, beş set 115 00:04:23,464 --> 00:04:24,630 həqiqətən olduqca tanış edir. 116 00:04:24,630 --> 00:04:27,430 Məsələn, bu dəstə əgər imtahan kitab, hər hansı 117 00:04:27,430 --> 00:04:29,660 tələbə ilk var bu və soyadı adı, 118 00:04:29,660 --> 00:04:31,820 Mən onlara ala bir imtahan sonunda, 119 00:04:31,820 --> 00:04:33,746 və onlar bütün olduqca istəyirik təsadüfi qaydada çox, 120 00:04:33,746 --> 00:04:36,370 və biz çeşidlənməsi haqqında getmək istəyirəm Bu imtahanları belə ki, bir dəfə pilləli 121 00:04:36,370 --> 00:04:38,661 yalnız bir çox asan və sürətli onları geri əl 122 00:04:38,661 --> 00:04:40,030 əlifba sırası ilə şagirdlərə. 123 00:04:40,030 --> 00:04:42,770 Sizin instinktlərdən nə olardı bu kimi imtahanları bir qalaq üçün? 124 00:04:42,770 --> 00:04:45,019 >> Yaxşı, siz mənim kimi değilseniz, siz Bu m olduğunu görmək bilər, 125 00:04:45,019 --> 00:04:48,505 mən növ bu qoymaq gedirəm Bu mənim masa və ya mərtəbə tapa əgər 126 00:04:48,505 --> 00:04:50,650 Mən hər şeyi yayılması alıram yazaraq və ya array, həqiqətən 127 00:04:50,650 --> 00:04:52,210 Mən orada Ms bütün qoymaq bilər. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Burada A. Mən güc var burada kimi qoydu. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Burada gedirəm başqa A. var burada qoymaq. 132 00:04:57,980 --> 00:05:02,490 Burada Z. Burada başqa M. Və belə Mən bu kimi hemoroid edilməsi başlamaq bilər. 133 00:05:02,490 --> 00:05:06,620 Və sonra bəlkə mən sonra getmək istədiyiniz və sort çox nitpicky-ly sort 134 00:05:06,620 --> 00:05:07,710 fərdi hemoroid. 135 00:05:07,710 --> 00:05:11,300 Amma nöqtə görünür bilər Mən əlli edirəm ki, giriş at 136 00:05:11,300 --> 00:05:14,016 və mən bəzi hesablanmışdır edəcək giriş əsasında qərar. 137 00:05:14,016 --> 00:05:15,640 Bu A ilə başlayır, orada qoyun. 138 00:05:15,640 --> 00:05:18,980 A-dan Z ilə başlayır varsa, üzərində qoymaq arasında var, və hər şey. 139 00:05:18,980 --> 00:05:22,730 >> Belə ki, bu ki, bir texnikadır ümumiyyətlə hashing-- H-A-S-H-- kimi tanınan 140 00:05:22,730 --> 00:05:26,550 olan ümumiyyətlə kimi görülməsi deməkdir giriş və hesablamaq üçün daxil etmədən istifadə edərək 141 00:05:26,550 --> 00:05:30,940 dəyəri, ümumiyyətlə sayı, və ki, sayı saxlama daxil indeksi 142 00:05:30,940 --> 00:05:32,260 konteyner, bir sıra kimi. 143 00:05:32,260 --> 00:05:35,490 Belə ki, başqa sözlə, mən bir ola bilər hash funksiyası, mən baş nə kimi, 144 00:05:35,490 --> 00:05:37,940 Mən kimsə görmək ki A ilə başlayır edən adı, 145 00:05:37,940 --> 00:05:40,190 Mən xəritəyə gedirəm mənim baş sıfır. 146 00:05:40,190 --> 00:05:44,160 Mən Z kimsə görmək əgər, mən deyiləm başım 25 xəritəsi gedir 147 00:05:44,160 --> 00:05:46,220 və sonra daxil qoymaq sonuncu ən qalaq. 148 00:05:46,220 --> 00:05:50,990 >> İndi, əgər mənim beyin deyil düşünmək lakin bir C proqram, nə nömrələri bilər 149 00:05:50,990 --> 00:05:53,170 Siz eyni nəticə əldə etmək üçün etibar? 150 00:05:53,170 --> 00:05:55,594 Başqa sözlə, əgər ASCII xarakter idi 151 00:05:55,594 --> 00:05:57,510 necə müəyyən edirsiniz nə bucket qoymaq? 152 00:05:57,510 --> 00:05:59,801 Siz yəqin ki, istəmirəm bucket 65, onu qoymaq 153 00:05:59,801 --> 00:06:01,840 orada kimi olacaq heç bir yaxşı səbəbdən. 154 00:06:01,840 --> 00:06:04,320 Harada A qoymaq istəyirəm onun ASCII dəyəri baxımından? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Harada onun ASCII üçün nə etmək istəyirəm dəyəri asan bucket ilə gəlmək 157 00:06:08,920 --> 00:06:09,480 qoymaq? 158 00:06:09,480 --> 00:06:10,206 >> Auditoriya: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID MALAN: Bəli. 160 00:06:10,956 --> 00:06:13,190 Belə ki, minus A və ya mənfi xüsusi 65 bu əgər 161 00:06:13,190 --> 00:06:18,240 kapital A. Or 98 əgər bir kiçik bir var. 162 00:06:18,240 --> 00:06:21,300 Və belə ki, çox, bizə imkan verir sadəcə və çox arithmetically, 163 00:06:21,300 --> 00:06:23,260 kimi bir vedrə bir şey qoymaq. 164 00:06:23,260 --> 00:06:26,010 Belə ki, biz, həqiqətən, nə çıxır Bu həmçinin belə sınavlar ilə. 165 00:06:26,010 --> 00:06:29,051 >> Belə ki, siz dairəvi geri bilər sizin qapağında tədris fellow adı. 166 00:06:29,051 --> 00:06:32,270 Və TF-nin adları təşkil edildi əlifba sırası ilə Bu sütun, 167 00:06:32,270 --> 00:06:34,400 yaxşı, iman və ya, zaman hamımız 80 plus 168 00:06:34,400 --> 00:06:37,800 sinifə, digər gecə birlikdə var Bizim grading prosesi son addım 169 00:06:37,800 --> 00:06:41,830 böyük daxil sınavlar hash edir [Işitilemez] at mərtəbə kosmik 170 00:06:41,830 --> 00:06:45,110 və hər kəsin sınavlar qoymaq onların TF tam qaydada 171 00:06:45,110 --> 00:06:47,700 qapağında adları, çünki sonra bizim üçün çox asandır 172 00:06:47,700 --> 00:06:51,290 istifadə edərək xətti ilə axtarış axtarış və ya dərrakə bir növ 173 00:06:51,290 --> 00:06:54,050 bir TF tapmaq üçün onun və ya Onun tələbələrin viktorina. 174 00:06:54,050 --> 00:06:56,060 >> Hashing Belə ki, bu fikir siz görəcəksiniz ki, 175 00:06:56,060 --> 00:07:00,520 olduqca güclü, həqiqətən, olduqca adi və çox intuitiv, 176 00:07:00,520 --> 00:07:03,000 çox bəlkə bölmək kimi fəth həftə sıfır idi. 177 00:07:03,000 --> 00:07:05,250 Hackathon Mən sürətli irəli bir neçə il əvvəl. 178 00:07:05,250 --> 00:07:08,040 Bu Zamyla və bir neçə idi digər heyət təbrik tələbələr 179 00:07:08,040 --> 00:07:09,030 Onlar da gəlib kimi. 180 00:07:09,030 --> 00:07:12,680 Və biz qatlama bütün dəstə idi adı tags ilə masalar. 181 00:07:12,680 --> 00:07:15,380 Və biz adı tags təşkil etmişdi ilə orada kimi 182 00:07:15,380 --> 00:07:16,690 və orada Zs. 183 00:07:16,690 --> 00:07:20,350 Və belə TFS biri çox ağıllı təlimatları bu yazdı 184 00:07:20,350 --> 00:07:21,030 Bu gün üçün. 185 00:07:21,030 --> 00:07:24,480 Və dövr bu həftə 12 bütün mükəmməl mənada və hər kəsə 186 00:07:24,480 --> 00:07:25,310 nə bilirdi. 187 00:07:25,310 --> 00:07:27,900 Amma zaman siz var Eyni şəkildə sıraya, 188 00:07:27,900 --> 00:07:30,272 Siz həyata edirik bir hash eyni anlayışı. 189 00:07:30,272 --> 00:07:31,730 Belə ki, bir az rəsmiləşdirilməsi bildirin. 190 00:07:31,730 --> 00:07:32,890 Burada bir sıra edir. 191 00:07:32,890 --> 00:07:36,820 Bu bir az cəlb edir geniş yalnız vizual, təsvir etmək, 192 00:07:36,820 --> 00:07:38,920 biz strings qoymaq bilər ki, bu kimi bir şey. 193 00:07:38,920 --> 00:07:41,970 Bu array edir aydın ölçüsü 26 cəmi. 194 00:07:41,970 --> 00:07:43,935 Və şey adlanır masa özbaşına. 195 00:07:43,935 --> 00:07:48,930 Amma bu yalnız bir rəssamın icra edir bir hash table ola bilər nə. 196 00:07:48,930 --> 00:07:52,799 >> Belə ki, bir hash table, indi gedir yüksək səviyyəli data strukturu olacaq. 197 00:07:52,799 --> 00:07:54,840 Günün sonunda biz sizə ki, görmək haqqında olduğunuz 198 00:07:54,840 --> 00:07:58,700 bir hash masa, həyata bilər çox check-line kimi 199 00:07:58,700 --> 00:08:02,059 çox bu kimi bir Hackathon at masa imtahan kitab çeşidlənməsi üçün istifadə. 200 00:08:02,059 --> 00:08:03,850 Amma bir hash masa Bu yüksək səviyyəli sort 201 00:08:03,850 --> 00:08:08,250 bir sıra istifadə edə bilər ki, konsepsiya , başlıq onu həyata keçirmək üçün altında 202 00:08:08,250 --> 00:08:11,890 və ya uzunluğu siyahısını istifadə, və ya hətta bilər bəlkə bəzi digər məlumatlar strukturları. 203 00:08:11,890 --> 00:08:15,590 İndi ki, theme-- alaraq var Bu fundamental maddələr bəzi 204 00:08:15,590 --> 00:08:18,310 bir sıra və bu bina kimi uzunluğu siyahısı indi blok 205 00:08:18,310 --> 00:08:21,740 və biz inşa edə bilərsiniz nə görən bu üst, maddələr kimi 206 00:08:21,740 --> 00:08:26,550 bir resept, daha çox və daha çox maraqlı və faydalı yekun nəticələri. 207 00:08:26,550 --> 00:08:28,680 >> Bu hash masa ilə belə biz bunu həyata bilər 208 00:08:28,680 --> 00:08:32,540 yaddaş pictorially bu kimi, lakin necə həqiqətən kodlu bilər? 209 00:08:32,540 --> 00:08:33,789 Bəli, bəlkə sadəcə olaraq bu. 210 00:08:33,789 --> 00:08:38,270 Bütün caps QABİLİYYƏTİ, yalnız əgər Məsələn 26 üçün bəzi constant--, 211 00:08:38,270 --> 00:08:42,030 Bu alphabet-- 26 məktublar üçün Mən dəyişən masa zəng edə bilər, 212 00:08:42,030 --> 00:08:45,630 və mən gedirəm ki, iddia edə bilər orada, və ya simli char ulduz qoydu. 213 00:08:45,630 --> 00:08:49,880 Belə ki, kimi sadə deyil, bu kimi bir hash masa həyata keçirmək istəyirik. 214 00:08:49,880 --> 00:08:51,490 Və hələ, bu, həqiqətən yalnız bir sıra edir. 215 00:08:51,490 --> 00:08:53,198 Ancaq yenə də, bir hash masa nə biz will indi 216 00:08:53,198 --> 00:08:57,470 yalnız bir mücərrəd data type zəng üst bir konseptual layering sort 217 00:08:57,470 --> 00:09:00,780 daha dünyəvi bir şey İndi bir sıra istəyirəm. 218 00:09:00,780 --> 00:09:02,960 >> İndi biz getmək yoxdur problemlərin həlli haqqında? 219 00:09:02,960 --> 00:09:06,980 Bəli, əvvəllər mən lüks idi burada kifayət qədər masa yer olan 220 00:09:06,980 --> 00:09:09,460 Mən qoymaq bilər ki, sınavlar yerdə Mən istəyirdim. 221 00:09:09,460 --> 00:09:10,620 Belə ki, kimi burada getmək bilər. 222 00:09:10,620 --> 00:09:12,100 Zs burada getmək bilər. 223 00:09:12,100 --> 00:09:13,230 Ms burada getmək bilər. 224 00:09:13,230 --> 00:09:14,740 Və sonra mən bəzi əlavə yer var idi. 225 00:09:14,740 --> 00:09:18,740 Amma bu bir fırıldaqçı sol bir az İndi bu masa, çünki mən, həqiqətən, 226 00:09:18,740 --> 00:09:22,720 bir sıra kimi fikir, yalnız Bəzi sabit ölçüsü olacaq. 227 00:09:22,720 --> 00:09:25,380 >> Belə ki, texniki, mən çəkmək əgər başqa şagirdin viktorina qədər 228 00:09:25,380 --> 00:09:28,490 və bu şəxs, oh bax adı da A ilə başlayır 229 00:09:28,490 --> 00:09:30,980 I növ orada qoymaq istəyirəm. 230 00:09:30,980 --> 00:09:34,740 Amma tezliklə əgər, orada qoymaq kimi Bu cədvəldə həqiqətən bir sıra təmsil, 231 00:09:34,740 --> 00:09:37,840 Mən əsas və ya clobbering gedirəm kim bu tələbə viktorina edir. 232 00:09:37,840 --> 00:09:38,340 Right? 233 00:09:38,340 --> 00:09:41,972 Bu bir sıra deyil, yalnız bir şey edə bilərsiniz Bu hüceyrələri və ya elementlərin hər getmək. 234 00:09:41,972 --> 00:09:43,680 Və mən növ var seçin və seçmək üçün. 235 00:09:43,680 --> 00:09:45,735 >> İndi əvvəllər I növ cheated və bu və ya etdim 236 00:09:45,735 --> 00:09:47,526 yalnız cür dizilir bir-birinə yuxarıda onlara. 237 00:09:47,526 --> 00:09:49,170 Amma ki, kodu uçmaq niyyətində deyil. 238 00:09:49,170 --> 00:09:52,260 Mən harada qoymaq bilər Onun adı ikinci tələbə 239 00:09:52,260 --> 00:09:54,964 Mən bütün bu əgər A mövcud masa yer? 240 00:09:54,964 --> 00:09:57,880 Mən üç yuva və istifadə etdiyiniz Yalnız bir neçə başqaları var kimi görünür. 241 00:09:57,880 --> 00:09:58,959 Siz nə edə bilər? 242 00:09:58,959 --> 00:09:59,834 Auditoriya: [işitilemez] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID MALAN: Bəli. 245 00:10:01,315 --> 00:10:02,370 Bəlkə yalnız sadə saxlamaq imkan verir. 246 00:10:02,370 --> 00:10:02,660 Right? 247 00:10:02,660 --> 00:10:04,243 Mən bunu qoymaq istədiyiniz uyğun deyil. 248 00:10:04,243 --> 00:10:07,450 Mən onu qoymaq gedirəm texniki B getmək harada. 249 00:10:07,450 --> 00:10:09,932 İndi, əlbəttə, mən başlayan alıram bir küncə özümü boya. 250 00:10:09,932 --> 00:10:11,890 Mən bir tələbə almaq Onun adı əslində B, 251 00:10:11,890 --> 00:10:14,840 İndi B bir az köçürülüb olacaq irəli kimi, yep, baş verə bilər 252 00:10:14,840 --> 00:10:17,530 bu bir B əgər, indi burada getmək üçün var. 253 00:10:17,530 --> 00:10:20,180 >> Və bu çox tez problemli ola bilər 254 00:10:20,180 --> 00:10:23,850 lakin bu texnika həqiqətən var xətti probing kimi istinad edilir, 255 00:10:23,850 --> 00:10:26,650 qovuşdurmağımız yalnız hesab sizin array xətti boyunca olmalıdır. 256 00:10:26,650 --> 00:10:29,680 Və yalnız cür sonda ya Hər bir mövcud element yoxlamaq 257 00:10:29,680 --> 00:10:31,360 mövcud spot axtarır. 258 00:10:31,360 --> 00:10:34,010 Və tezliklə tapmaq kimi bir, siz orada onu buraxın. 259 00:10:34,010 --> 00:10:38,390 >> İndi qiymət indi ödənilir Bu həlli üçün nə edir? 260 00:10:38,390 --> 00:10:41,300 Biz sabit ölçüsü array var, Mən adları daxil zaman 261 00:10:41,300 --> 00:10:44,059 onu, ən azı ilkin nə durub çalışan zaman 262 00:10:44,059 --> 00:10:46,350 tələbələrin qoyulması üçün sağ buketler sınavlar? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Nə Big O? 265 00:10:50,002 --> 00:10:51,147 >> Auditoriya: n. 266 00:10:51,147 --> 00:10:52,480 DAVID MALAN: Mən n böyük O eşitdim. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Doğru deyil. 269 00:10:54,300 --> 00:10:56,490 Amma biz ayrı dolaşmaq lazımdır niyə yalnız bir anda. 270 00:10:56,490 --> 00:10:57,702 Başqa nə ola bilər? 271 00:10:57,702 --> 00:10:58,755 >> Auditoriya: [işitilemez] 272 00:10:58,755 --> 00:11:00,380 DAVID MALAN: Və mənə vizual bunu bildirin. 273 00:11:00,380 --> 00:11:04,720 Belə ki, bu məktub S. güman 274 00:11:04,720 --> 00:11:05,604 >> Auditoriya: Bu, bir var. 275 00:11:05,604 --> 00:11:06,520 DAVID MALAN: Bu biridir. 276 00:11:06,520 --> 00:11:06,710 Right? 277 00:11:06,710 --> 00:11:08,950 Bu array olan biz təsadüfi giriş var deməkdir. 278 00:11:08,950 --> 00:11:11,790 Və biz bu hesab sıfır və bu kimi 25 kimi, 279 00:11:11,790 --> 00:11:13,800 və biz həyata, oh, burada mənim giriş S var, 280 00:11:13,800 --> 00:11:16,350 Mən, əlbəttə, çevirə bilərsiniz S, bir ASCII xarakter, 281 00:11:16,350 --> 00:11:18,540 müvafiq sıra sıfır və 25 arasında 282 00:11:18,540 --> 00:11:20,910 və sonra dərhal Bu məxsusdur yerləşir qoymaq. 283 00:11:20,910 --> 00:11:26,120 >> Amma əlbəttə, tezliklə mən almaq kimi adı olan ikinci şəxs A və ya B və ya C 284 00:11:26,120 --> 00:11:29,300 nəhayət, Mən istifadə etdiyiniz əgər xətti, mənim həlli kimi yoxlamağa 285 00:11:29,300 --> 00:11:31,360 çalışan zaman Ən pis halda durub 286 00:11:31,360 --> 00:11:33,120 həqiqətən nə daxil qalmaq gedir? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Və mən burada eşitmisiniz düzgün erkən. 289 00:11:36,045 --> 00:11:36,920 Auditoriya: [işitilemez] 290 00:11:36,920 --> 00:11:41,620 DAVID MALAN: Belə ki, həqiqətən bir n Siz kifayət qədər böyük data dəsti var. 291 00:11:41,620 --> 00:11:44,410 Belə ki, bir tərəfdən, əgər Sizin array kifayət qədər böyük deyil 292 00:11:44,410 --> 00:11:48,287 və sizin data, kifayət qədər seyrək Bu gözəl daimi vaxt almaq. 293 00:11:48,287 --> 00:11:50,620 Amma tezliklə başlamaq kimi daha çox elementləri almaq, 294 00:11:50,620 --> 00:11:53,200 və yalnız statistik almaq hərfi ilə daha çox insanlar 295 00:11:53,200 --> 00:11:56,030 A onların adı və ya məktub B, potensial bilər 296 00:11:56,030 --> 00:11:57,900 bir şey daha xətti daxil qalmaq. 297 00:11:57,900 --> 00:11:59,640 Belə ki, kifayət qədər mükəmməl deyil. 298 00:11:59,640 --> 00:12:00,690 Belə ki, biz daha yaxşı bilər? 299 00:12:00,690 --> 00:12:03,210 >> Yaxşı, nə oldu bizim həll zaman biz əvvəl 300 00:12:03,210 --> 00:12:06,820 daha çox dinamizm var istəyirəm bir sıra kimi bir şey icazə? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 Auditoriya: [işitilemez] 303 00:12:08,960 --> 00:12:10,030 DAVID MALAN: biz nə təqdim etməyib? 304 00:12:10,030 --> 00:12:10,530 Bəli. 305 00:12:10,530 --> 00:12:11,430 Belə ki, bir bağlı siyahı. 306 00:12:11,430 --> 00:12:14,430 Yaxşı, bir bağlı nə görmək edək siyahısı əvəzinə bizim üçün edə bilər. 307 00:12:14,430 --> 00:12:17,630 Yaxşı, mənə biz təklif edək aşağıdakı kimi şəkil çəkmək. 308 00:12:17,630 --> 00:12:19,620 İndi bu fərqli Məsələn şəkil 309 00:12:19,620 --> 00:12:24,750 müxtəlif mətn, həqiqətən, həqiqətən ölçüsü 31 bir sıra istifadə edir. 310 00:12:24,750 --> 00:12:28,220 Bu müəllif sadəcə strings hash qərar 311 00:12:28,220 --> 00:12:32,430 şəxsin adları əsasında deyil, lakin onların doğum günlerinin əsaslanır. 312 00:12:32,430 --> 00:12:35,680 Asılı olmayaraq ayın, onlar fiqurlu Bir ayın ilk anadan edirsinizsə 313 00:12:35,680 --> 00:12:39,580 və ya bir ay 31, müəllif ki, dəyəri əsasında hash edəcək, 314 00:12:39,580 --> 00:12:44,154 bir az həyata adları yaymaq kimi yalnız 26 ləkələr imkan bilər daha çox. 315 00:12:44,154 --> 00:12:47,320 Və bəlkə bir az daha vahid var əlifba hərfləri ilə gedən daha, 316 00:12:47,320 --> 00:12:50,236 çünki, əlbəttə yəqin ki, var adları ilə dünyada daha çox insanın 317 00:12:50,236 --> 00:12:54,020 əlbəttə çox A ilə start Əlifba digər məktublar. 318 00:12:54,020 --> 00:12:56,380 Belə ki, bəlkə, bu bir az daha vahid, fərz 319 00:12:56,380 --> 00:12:58,640 vahid paylanması Bir ay boyunca körpələr. 320 00:12:58,640 --> 00:12:59,990 >> Lakin, əlbəttə, bu hələ təkmil deyil. 321 00:12:59,990 --> 00:13:00,370 Right? 322 00:13:00,370 --> 00:13:01,370 Biz toqquşma qarşılaşdıqda. 323 00:13:01,370 --> 00:13:04,680 Bu çox insanlar data strukturu hələ 324 00:13:04,680 --> 00:13:08,432 ən azı eyni doğum olan Siz ay asılı olmayaraq istəyirik. 325 00:13:08,432 --> 00:13:09,640 Lakin müəllif nə görmüşdür? 326 00:13:09,640 --> 00:13:13,427 Biz bir sıra var kimi Bəli, görünür şaquli tərtib sol tərəfində, 327 00:13:13,427 --> 00:13:15,010 lakin yalnız bir rəssamın icra edir. 328 00:13:15,010 --> 00:13:18,009 Fərq etməz hansı istiqamətdə bir sıra çəkmək, o, hələ bir sıra var. 329 00:13:18,009 --> 00:13:20,225 Bu yəqin bir sıra nədir? 330 00:13:20,225 --> 00:13:21,500 >> Auditoriya: Əlaqəli siyahısı. 331 00:13:21,500 --> 00:13:21,650 >> DAVID MALAN: Bəli. 332 00:13:21,650 --> 00:13:23,490 Bir var kimi görünür bağlı siyahı array. 333 00:13:23,490 --> 00:13:26,490 Belə ki, yenə növ bu nöqtəyə İndi bu data strukturları istifadə 334 00:13:26,490 --> 00:13:28,550 daha çox maddələr kimi maraqlı həllər, 335 00:13:28,550 --> 00:13:30,862 Siz tamamilə bir edə bilər fundamental, bir sıra kimi, 336 00:13:30,862 --> 00:13:33,320 və daha çox bir şey almaq bir bağlı siyahı kimi maraqlı 337 00:13:33,320 --> 00:13:36,660 və hətta daha onları birləşdirmək daha maraqlı data strukturu. 338 00:13:36,660 --> 00:13:39,630 Və həqiqətən, bu çox olardı bir hash masa adlanır, 339 00:13:39,630 --> 00:13:42,610 qovuşdurmağımız array edir həqiqətən hash table, 340 00:13:42,610 --> 00:13:45,600 lakin hash table var zəncirlər, belə ki, danışmaq 341 00:13:45,600 --> 00:13:50,220 ki, inkişaf edə bilər və ya əsasında shrink elementlərin sayı əlavə etmək istəyirəm. 342 00:13:50,220 --> 00:13:52,990 >> İndi buna görə, nə indi vaxt çalışan? 343 00:13:52,990 --> 00:13:58,030 Mən kimsə daxil etmək istəyirsinizsə, 31 oktyabr kimin ad, 344 00:13:58,030 --> 00:13:59,040 o Ü getmək edir? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Bütün hüquqlar. 347 00:14:01,030 --> 00:14:02,819 Bu 31 deyir çox alt. 348 00:14:02,819 --> 00:14:03,610 Və mükəmməl. 349 00:14:03,610 --> 00:14:05,060 Ki, daimi vaxt idi. 350 00:14:05,060 --> 00:14:08,760 Amma biz başqa kimsə nə tapmaq əgər kimin ad günü, görək ki, 351 00:14:08,760 --> 00:14:10,950 Oktyabr, noyabr, dekabr 31? 352 00:14:10,950 --> 00:14:12,790 Harada o getmək üçün gedir? 353 00:14:12,790 --> 00:14:13,290 Eyni şey. 354 00:14:13,290 --> 00:14:13,970 Baxmayaraq iki addım. 355 00:14:13,970 --> 00:14:15,303 Ki, baxmayaraq daimi deyil? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Bütün hüquqlar. 358 00:14:16,860 --> 00:14:17,840 Hal-hazırda deyil. 359 00:14:17,840 --> 00:14:20,570 Amma ümumi halda, biz əlavə daha çox insan, 360 00:14:20,570 --> 00:14:23,790 probabilistically, gedirik daha çox toqquşma almaq üçün. 361 00:14:23,790 --> 00:14:26,820 >> İndi bu bir az yaxşı texniki çünki 362 00:14:26,820 --> 00:14:34,580 İndi mənim zəncirlər ola bilər ən pis halda necə uzun? 363 00:14:34,580 --> 00:14:38,890 Mən bu daha çox daxil N insanları daxil edin inkişaf etmiş data strukturu, n insanlar, 364 00:14:38,890 --> 00:14:41,080 ən pis halda n olacaq. 365 00:14:41,080 --> 00:14:41,815 Niyə? 366 00:14:41,815 --> 00:14:43,332 >> Auditoriya: Çünki əgər hər kəs eyni ad var, 367 00:14:43,332 --> 00:14:44,545 onlar bir xətt olacaq. 368 00:14:44,545 --> 00:14:45,420 DAVID MALAN: Perfect. 369 00:14:45,420 --> 00:14:47,480 Bu, bir az göstərdi ola bilər lakin həqiqətən ən pis halda, 370 00:14:47,480 --> 00:14:50,117 hər kəs eyni ad var, Siz giriş verilmiş, 371 00:14:50,117 --> 00:14:51,950 Bir var olacaq kütləvi uzun zəncir. 372 00:14:51,950 --> 00:14:54,241 Belə ki, siz bir zəng edə bilər hash table, lakin həqiqətən bu 373 00:14:54,241 --> 00:14:56,810 yalnız kütləvi bağlı siyahı sərf kosmik bir çox. 374 00:14:56,810 --> 00:15:00,460 Lakin ümumiyyətlə, biz güman əgər ən azı ad günü uniform-- var 375 00:15:00,460 --> 00:15:01,750 və yəqin ki, deyil. 376 00:15:01,750 --> 00:15:02,587 Mən qədər edilməsi alıram. 377 00:15:02,587 --> 00:15:04,420 Amma biz güman əgər, üçün müzakirə naminə 378 00:15:04,420 --> 00:15:07,717 Onlar sonra nəzəri, əgər ki, Bu şaquli təmsil edir 379 00:15:07,717 --> 00:15:11,050 serialın, yaxşı sonra inşallah siz etdiyiniz var, bilirsiniz ki, zəncirlər almaq üçün gedir, 380 00:15:11,050 --> 00:15:15,880 təxminən eyni uzunluğu olduğu hər bu ay bir gün edir. 381 00:15:15,880 --> 00:15:19,930 >> Ay 31 gün var, əgər İndi, ki, həqiqətən, mənim çalışan zaman deməkdir 382 00:15:19,930 --> 00:15:25,230 31-dən çox n böyük O olan xətti daha yaxşı hiss edir. 383 00:15:25,230 --> 00:15:27,950 Amma biri idi bizim öhdəliklər bir neçə həftə 384 00:15:27,950 --> 00:15:31,145 əvvəl ifadə gəlib zaman alqoritm çalışan zaman? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Yalnız yüksək order müddətli baxmaq. 387 00:15:35,190 --> 00:15:35,690 Right? 388 00:15:35,690 --> 00:15:37,400 31 mütləq faydalıdır. 389 00:15:37,400 --> 00:15:39,610 Amma bu hələ n böyük O edir. 390 00:15:39,610 --> 00:15:41,730 Amma mövzulardan biri problemi beş set 391 00:15:41,730 --> 00:15:43,950 üçün olacaq tamamilə etiraf, 392 00:15:43,950 --> 00:15:47,320 asimptotik, nəzəri Bu data strukturu 393 00:15:47,320 --> 00:15:50,470 yalnız daha yaxşıdır bir kütləvi bağlı siyahısı. 394 00:15:50,470 --> 00:15:53,550 Və həqiqətən, ən pis halda, bu hash table ki, daxil qalmaq bilər. 395 00:15:53,550 --> 00:15:57,620 >> Lakin real dünyada, bizimlə insanlar öz Mac və ya PC və ya hər hansı ki, 396 00:15:57,620 --> 00:16:01,240 və real dünya çalışan real dünya data software, 397 00:16:01,240 --> 00:16:03,260 olan alqoritm üstünlük gedir? 398 00:16:03,260 --> 00:16:09,180 Son addımlar və ya alır ki, bir n 31 addımlar bölünür edir ki, bir 399 00:16:09,180 --> 00:16:12,900 məlumatların bir parça tapmaq və ya bəzi informasiya axtarmaq üçün? 400 00:16:12,900 --> 00:16:16,580 Mən tamamilə 31 markalar demək real dünyada bir fərq. 401 00:16:16,580 --> 00:16:18,540 Bu 31 dəfə daha sürətli edir. 402 00:16:18,540 --> 00:16:20,880 Və biz insanlar əlbəttə var ki, təşəkkür olacaq. 403 00:16:20,880 --> 00:16:23,004 >> Belə ki, ayrılığın həyata faktiki arasında 404 00:16:23,004 --> 00:16:25,920 nəzəri şeylər haqqında danışır mütləq və asimptotik olan 405 00:16:25,920 --> 00:16:28,760 biz gördük kimi dəyər var, lakin real dünyada, 406 00:16:28,760 --> 00:16:32,930 yalnız edilməsi haqqında qayğı əgər ümumi giriş insan xoşbəxt, 407 00:16:32,930 --> 00:16:36,010 Siz çox yaxşı qəbul etmək istəyirəm bilər Bəli, bu xətti, ki, 408 00:16:36,010 --> 00:16:38,360 lakin 31 dəfə daha sürətli daha xətti ola bilər. 409 00:16:38,360 --> 00:16:41,610 Və daha yaxşı hələ, biz yalnız yoxdur bir doğum kimi ixtiyari bir şey, 410 00:16:41,610 --> 00:16:44,030 biz bir az sərf edə bilər daha çox vaxt və dərrakə 411 00:16:44,030 --> 00:16:47,140 və biz edə bilər nə haqqında düşünmək, verilən şəxsin adı və bəlkə 412 00:16:47,140 --> 00:16:50,130 Onların doğum o birləşdirmək maddələr bir şey anlamaq üçün 413 00:16:50,130 --> 00:16:52,720 həqiqətən çox vahid və daha az jaggy, 414 00:16:52,720 --> 00:16:56,250 bu şəkil daha danışmaq Hal-hazırda ola bilər göstərir. 415 00:16:56,250 --> 00:16:57,750 Necə ki, biz kodu bu həyata bilər? 416 00:16:57,750 --> 00:17:00,280 Yaxşı, mənə biz təklif edək yalnız biz bəzi sintaksis borc 417 00:17:00,280 --> 00:17:01,799 İndiyədək bir neçə dəfə istifadə. 418 00:17:01,799 --> 00:17:03,590 Və mən müəyyən gedirəm bir node, yenidən 419 00:17:03,590 --> 00:17:06,812 yalnız bəzi ümumi anlayışdır bəzi data strukturunda üçün konteyner. 420 00:17:06,812 --> 00:17:09,020 Mən təklif gedirəm bir simli var gedir. 421 00:17:09,020 --> 00:17:11,369 Amma biz alaraq başlamaq olacaq İndi off təkərlər təlim olanlar. 422 00:17:11,369 --> 00:17:13,230 >> No daha CS50 kitabxana həqiqətən, istədiyiniz halda 423 00:17:13,230 --> 00:17:15,230 Sizin final üçün istifadə etmək gözəl olan layihə, 424 00:17:15,230 --> 00:17:18,569 lakin indi biz geri çəkmək olacaq pərdə və yalnız bir char ulduz deyirlər. 425 00:17:18,569 --> 00:17:22,069 Sözü Belə ki, orada olacaq sözügedən şəxsin adı. 426 00:17:22,069 --> 00:17:25,079 İndi bir link var Burada növbəti node 427 00:17:25,079 --> 00:17:28,170 Bu etdirir ki, qovşaqlarının hər 428 00:17:28,170 --> 00:17:30,950 zəncirində, potensial, bir bağlı siyahı. 429 00:17:30,950 --> 00:17:34,090 >> İndi necə bəyan etmək Bu hash table özü? 430 00:17:34,090 --> 00:17:36,660 Mən bu bütün struktur bəyan edirsiniz? 431 00:17:36,660 --> 00:17:40,960 Yaxşı, həqiqətən, çox mən bir pointer istifadə kimi siyahısı yalnız ilk element 432 00:17:40,960 --> 00:17:44,510 əvvəl eyni mən yalnız demək olar Mən yalnız göstəricilər bir dəstə lazımdır 433 00:17:44,510 --> 00:17:46,270 Bu bütün hash table həyata. 434 00:17:46,270 --> 00:17:49,484 Mən bir sıra üçün gedirəm hash masa çağırıb masa. 435 00:17:49,484 --> 00:17:50,900 Bu ölçüsü tutumu olacaq. 436 00:17:50,900 --> 00:17:52,525 Ki, uyğun necə çox elementləri var. 437 00:17:52,525 --> 00:17:56,180 Və bu həmin elementlərin hər array bir node ulduz olacaq. 438 00:17:56,180 --> 00:17:56,810 Niyə? 439 00:17:56,810 --> 00:18:00,160 Bəli, bu şəkil başına, Mən nə edirəm Bu hash masa kimi həyata 440 00:18:00,160 --> 00:18:04,330 effektiv yalnız başlanğıcı biz şaquli tərtib etdik ki, bu array, 441 00:18:04,330 --> 00:18:06,820 olan meydanların hər bir göstərici təmsil edir. 442 00:18:06,820 --> 00:18:09,170 Olanlar slashes var ki, onların vasitəsilə yalnız null var. 443 00:18:09,170 --> 00:18:11,410 Və olanlar var doğru gedir oxlar 444 00:18:11,410 --> 00:18:16,140 faktiki qovşaqlarının üçün faktiki göstəricilər var, bir bağlı siyahı start bundan dolayı. 445 00:18:16,140 --> 00:18:19,050 >> Belə ki, burada, sonra biz necə qüdrət bir hash table həyata ki, 446 00:18:19,050 --> 00:18:21,580 ayrı-ayrı chaining həyata keçirir. 447 00:18:21,580 --> 00:18:22,840 İndi biz daha yaxşı edə bilər? 448 00:18:22,840 --> 00:18:25,632 Bütün hüquqlar Mən keçən dəfə vəd ki, biz daimi vaxt nail. 449 00:18:25,632 --> 00:18:27,381 Mən cür sizə verdi Burada daimi vaxt, 450 00:18:27,381 --> 00:18:29,850 lakin sonra həqiqətən, bildirib daimi vaxt hələ, çünki 451 00:18:29,850 --> 00:18:31,890 ümumi asılı elementlərin sayı 452 00:18:31,890 --> 00:18:34,500 Siz daxil giren edirik Bu data strukturu. 453 00:18:34,500 --> 00:18:35,980 Amma biz bunu güman edirlər. 454 00:18:35,980 --> 00:18:39,550 Mənə burada ekran geri getmək edək. 455 00:18:39,550 --> 00:18:44,520 , Burada mənə də bu qədər layihə aydın olsun ekran, və mən bu görmüşük. 456 00:18:44,520 --> 00:18:49,300 Mən adını daxil etmək istədiyini düşünək Daven mənim data strukturu. 457 00:18:49,300 --> 00:18:52,100 >> Mən bir string daxil etmək istəyirəm Məlumat strukturu Daven. 458 00:18:52,100 --> 00:18:54,370 Mən istifadə etməyin, əgər hash table, amma istifadə 459 00:18:54,370 --> 00:18:56,980 daha çox bir şey ağac kimi bir ailə ağac, olduğu kimi 460 00:18:56,980 --> 00:18:59,670 Siz bəzi kök var üst və sonra qovşaqlarının və yarpaqları 461 00:18:59,670 --> 00:19:01,440 ki, aşağı və zahiri gedin. 462 00:19:01,440 --> 00:19:04,450 , Sonra mən güman Daven nin daxil etmək istəyirəm 463 00:19:04,450 --> 00:19:06,430 Hal-hazırda boş siyahısı nə. 464 00:19:06,430 --> 00:19:09,780 Mən aşağıdakı gedirəm: Mən bu ailə bir node yaratmaq niyyətindədir 465 00:19:09,780 --> 00:19:15,170 ağac kimi data strukturu görünür ki, bir az bu kimi, hər hansı 466 00:19:15,170 --> 00:19:19,640 düzbucaqlı, deyək edib bu artıq 26 elementləri üçün. 467 00:19:19,640 --> 00:19:21,650 Və hüceyrələrin hər Bu array gedir 468 00:19:21,650 --> 00:19:23,470 əlifba məktub təmsil etmək üçün. 469 00:19:23,470 --> 00:19:28,190 >> Xüsusilə, mən müalicə gedirəm Bu, A, sonra B, sonra C, onda D 470 00:19:28,190 --> 00:19:29,310 bu burada. 471 00:19:29,310 --> 00:19:32,940 Belə ki, bu səmərəli gedir məktub D. təmsil 472 00:19:32,940 --> 00:19:36,040 Amma Daven nin bütün daxil Mən bir az daha nə etmək lazımdır adı. 473 00:19:36,040 --> 00:19:37,840 Mən ilk belə danışmaq, hash gedirəm. 474 00:19:37,840 --> 00:19:41,049 Mən ilk məktub baxmaq gedirəm da Daven açıq-aydın bir D olan, 475 00:19:41,049 --> 00:19:42,840 və mən ayrılması gedirəm görünür ki, bir node 476 00:19:42,840 --> 00:19:45,570 kimi böyük böyük düzbucaqlı Hələ bütün əlifbası uyğun kifayət qədər. 477 00:19:45,570 --> 00:19:47,140 >> İndi D edilir. 478 00:19:47,140 --> 00:19:49,720 İndi A. D-A-V-E-N məqsədidir. 479 00:19:49,720 --> 00:19:51,220 Belə ki, indi mən gedirəm nə bu. 480 00:19:51,220 --> 00:19:54,027 Kimi tezliklə Mən D bildiriş başladı heç bir göstərici var. 481 00:19:54,027 --> 00:19:56,860 Bu anda zibil dəyərlər və ya null başlamaq bilər. 482 00:19:56,860 --> 00:19:59,630 Amma mənə ilə davam edək bir ağac bina bu fikir. 483 00:19:59,630 --> 00:20:04,260 Mənə bu başqa bir ayrılması bildirin bu 26 elementlər vardır ki qovşaqlarının. 484 00:20:04,260 --> 00:20:05,150 >> Və nə bilirik? 485 00:20:05,150 --> 00:20:09,130 Bu yaddaş yalnız bir node ki, əgər Mən struct istifadə edərək, malloc ilə yaradılmışdır 486 00:20:09,130 --> 00:20:11,240 biz tezliklə görəcəksiniz kimi, Mən Hələ gedirəm 487 00:20:11,240 --> 00:20:14,450 Mən ox çəkmək üçün gedirəm aşağı D təmsil edən şey 488 00:20:14,450 --> 00:20:15,860 Bu yeni node. 489 00:20:15,860 --> 00:20:19,240 Və ilk növbəti indi Daven adı məktub, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- Mən irəli getmək üçün gedirəm və bu kimi başqa node, 491 00:20:24,150 --> 00:20:30,150 vasitəsi, burada V elementləri olan biz misal whoops üçün çəkmək lazımdır. 492 00:20:30,150 --> 00:20:31,020 Biz orada çəkmək olmaz. 493 00:20:31,020 --> 00:20:31,936 Burada getmək olacaq. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Sonra biz olacaq Bu V. hesab 496 00:20:35,712 --> 00:20:44,920 Və sonra aşağı burada biz index olacaq aşağı V biz E. hesab lazımdır nə daxil 497 00:20:44,920 --> 00:20:50,100 Və sonra burada biz olacaq Burada bu qovşaqlarının biri getmək. 498 00:20:50,100 --> 00:20:52,930 İndi biz cavab bir sual var. 499 00:20:52,930 --> 00:20:57,840 Mən göstərir ki, elə etmək lazımdır biz simli Daven sonunda istəyirik. 500 00:20:57,840 --> 00:20:59,490 Mən yalnız null tərk edə bilər. 501 00:20:59,490 --> 00:21:02,670 >> Amma biz Daven nin nə varsa də tam adı, olan 502 00:21:02,670 --> 00:21:04,280 biz Davenport bildirib etdiyiniz kimi, var? 503 00:21:04,280 --> 00:21:06,970 Belə ki, Daven nə varsa əslində bir substring, 504 00:21:06,970 --> 00:21:08,960 Bir daha uzun simli bir prefiks? 505 00:21:08,960 --> 00:21:11,450 Biz yalnız daimi bilməz heç bir şey gedir demək 506 00:21:11,450 --> 00:21:14,410 Çünki ola bilər, orada getmək Davenport kimi bir söz daxil heç vaxt 507 00:21:14,410 --> 00:21:15,840 Bu data strukturu 508 00:21:15,840 --> 00:21:19,560 >> Belə ki, biz nə əvəzinə Bu elementlərin hər müalicə 509 00:21:19,560 --> 00:21:22,170 bəlkə iki olan onların içərisində elementləri. 510 00:21:22,170 --> 00:21:24,810 Bir, həqiqətən, bir göstəricisidir Mən bunu etdik. 511 00:21:24,810 --> 00:21:27,100 Bu qutuları hər belə yalnız bir mobil deyil. 512 00:21:27,100 --> 00:21:29,855 Amma nə əgər top one-- alt birinin 513 00:21:29,855 --> 00:21:32,230 Çünki, null olacaq Yalnız hələ heç bir Davenport var. 514 00:21:32,230 --> 00:21:34,197 Nə üst bir bəzi xüsusi dəyəri? 515 00:21:34,197 --> 00:21:36,530 Və bir az olacaq Bu ölçüsü çəkmək çətindir. 516 00:21:36,530 --> 00:21:38,130 Amma bu yalnız bir onay işareti Güman. 517 00:21:38,130 --> 00:21:38,920 Yoxlayın. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N simli Bu data strukturu. 519 00:21:44,230 --> 00:21:48,350 >> Eyni zamanda, əgər mən daha çox yer var idi burada, mən P-O-R-T edə bilər 520 00:21:48,350 --> 00:21:52,650 və mən node çek qoymaq bilər ki, çox sonunda məktub T var. 521 00:21:52,650 --> 00:21:55,460 Belə ki, bu kütləvi deyil kompleks görünüşlü data strukturu. 522 00:21:55,460 --> 00:21:57,210 Və mənim yazı əlbəttə kömək etmir. 523 00:21:57,210 --> 00:22:00,043 Amma bir şey daxil etmək istəyirdi başqa, biz nə hesab. 524 00:22:00,043 --> 00:22:03,370 Biz Davudu qoymaq istəyirdi, Biz, eyni məntiq, D-A-V izləmək istədiyiniz 525 00:22:03,370 --> 00:22:08,802 lakin indi mən növbəti qeyd olardı element deyil E, lakin I D. 526 00:22:08,802 --> 00:22:10,760 Belə ki, var olacaq Bu ağac daha qovşaqlarının. 527 00:22:10,760 --> 00:22:12,325 Daha çox zəng malloc olacaq. 528 00:22:12,325 --> 00:22:14,700 Amma bir etmək istəmirəm Bu şəkil tam mess. 529 00:22:14,700 --> 00:22:17,710 Belə ki, əvəzinə bir baxaq ki, əvvəlcədən ifadə edilmişdir 530 00:22:17,710 --> 00:22:21,810 dot deyil bu kimi, dot, nöqtələr, ancaq qısaldılmış Diziler. 531 00:22:21,810 --> 00:22:23,950 Amma qovşaqlarının hər burada bu ağac qədər 532 00:22:23,950 --> 00:22:26,700 Eyni şey təmsil bir sıra ölçüsü 26 Ray. 533 00:22:26,700 --> 00:22:28,860 >> Yoxsa biz olmaq istəyirsinizsə həqiqətən müvafiq indi nə 534 00:22:28,860 --> 00:22:30,790 kiminsə adı kimi əgər bir apostrof, edək 535 00:22:30,790 --> 00:22:35,560 hər node həqiqətən var ki, güman bu 27 göstəriciləri, yalnız 26 kimi. 536 00:22:35,560 --> 00:22:42,020 Belə ki, indi bir veri olacaq struktur trie T-R-I-E çağırıb. 537 00:22:42,020 --> 00:22:46,120 Guya olan bir trie, bir ağac üçün tarixən bir ağıllı adı 538 00:22:46,120 --> 00:22:49,040 ki, optimize axtarış, əlbəttə, 539 00:22:49,040 --> 00:22:50,870 Bu trie belə bir I-E yazılır. 540 00:22:50,870 --> 00:22:52,710 Amma bu trie tarixidir. 541 00:22:52,710 --> 00:22:55,860 >> Belə bir trie, bu ağac kimi data bir ailə ağac kimi strukturu 542 00:22:55,860 --> 00:22:57,510 ki, nəticədə kimi davranır. 543 00:22:57,510 --> 00:23:00,890 Və burada bir yalnız bir nümunəsidir digər insanların adları dəstə. 544 00:23:00,890 --> 00:23:03,540 Amma indi sual əl var nə 545 00:23:03,540 --> 00:23:08,070 biz arguably daha tanıdaraq əldə mürəkkəb data strukturu və bir, 546 00:23:08,070 --> 00:23:09,870 səmimi, yaddaş bir çox istifadə edir. 547 00:23:09,870 --> 00:23:11,703 >> , Çünki baxmayaraq Hal-hazırda, mən yalnız deyiləm 548 00:23:11,703 --> 00:23:15,050 D's göstərici istifadə və A V və Es və Ns, və 549 00:23:15,050 --> 00:23:16,700 Mən yaddaş çox bir heck israf edirəm. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Amma bir resurs sərf harada, Mən geri bir əldə edirsiniz edirlər. 552 00:23:22,660 --> 00:23:26,020 Mən daha çox yer sərf edirəm əgər Belə ki, yəqin ki, ümid var? 553 00:23:26,020 --> 00:23:27,407 Mən nə az sərf edirəm ki? 554 00:23:27,407 --> 00:23:28,240 Auditoriya: az vaxt. 555 00:23:28,240 --> 00:23:28,990 DAVID MALAN: Time. 556 00:23:28,990 --> 00:23:30,320 İndi nə ola bilər? 557 00:23:30,320 --> 00:23:33,880 Yaxşı, durub nə vaxt, indi böyük O baxımından, 558 00:23:33,880 --> 00:23:37,660 Daven kimi adı və ya Davenport və ya David? 559 00:23:37,660 --> 00:23:39,340 Yaxşı, Daven beş addımlar idi. 560 00:23:39,340 --> 00:23:42,350 Davenport doqquz addımlar olacaq, belə ki, bir neçə addımlar olardı. 561 00:23:42,350 --> 00:23:44,250 David həmçinin beş addımlar olardı. 562 00:23:44,250 --> 00:23:47,230 Belə ki, konkret var nömrələri, lakin, şübhəsiz ki var 563 00:23:47,230 --> 00:23:49,550 Bu bir üst bound kiminsə adı uzunluğu. 564 00:23:49,550 --> 00:23:52,240 Və həqiqətən, problemi Beş dəqiqləşdirilməsi dəstləri, 565 00:23:52,240 --> 00:23:54,050 Biz təklif olacaq bir şey var ki, 566 00:23:54,050 --> 00:23:55,470 40-bəzi-tək simvol var. 567 00:23:55,470 --> 00:23:58,180 >> Real, heç bir var sonsuz uzun adı, 568 00:23:58,180 --> 00:24:01,542 demək olan bir uzunluğu Ad və ya simli uzunluğu Biz güc 569 00:24:01,542 --> 00:24:03,750 Dövlət müəyyən var strukturu arguably nədir? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Bu sabit deyil. 572 00:24:06,250 --> 00:24:06,430 Right? 573 00:24:06,430 --> 00:24:09,310 Bu kimi böyük bir sabit ola bilər 40-bir şey, lakin sabit deyil. 574 00:24:09,310 --> 00:24:13,752 Və nə qədər heç bir asılılıq var digər adları Bu data strukturu var. 575 00:24:13,752 --> 00:24:15,460 Başqa sözlə, mən əgər İndi daxil etmək istədi 576 00:24:15,460 --> 00:24:20,540 Colton və ya Gabriel ya Rob ya Zamyla və ya Alison ya Belinda və ya hər hansı digər adları 577 00:24:20,540 --> 00:24:23,940 Bu data daxil heyəti strukturu, çalışan vaxt 578 00:24:23,940 --> 00:24:26,750 digər adları daxil bütün təsir da olacaq 579 00:24:26,750 --> 00:24:30,220 necə bir çox digər elementləri ilə var artıq data strukturunda? 580 00:24:30,220 --> 00:24:31,040 Bu deyil. 581 00:24:31,040 --> 00:24:31,540 Right? 582 00:24:31,540 --> 00:24:36,150 Biz səmərəli istifadə edirik, çünki Bu multi-qat hash table. 583 00:24:36,150 --> 00:24:38,280 Və çalışan zaman Bu əməliyyatların hər hansı 584 00:24:38,280 --> 00:24:41,510 sayı deyil asılıdır Bu data strukturu var ki elementləri 585 00:24:41,510 --> 00:24:43,090 və ya nəticədə gedir Bu data strukturu olmaq, 586 00:24:43,090 --> 00:24:44,714 lakin nə xüsusi uzunluğu? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Olan string , daxil edir olan 589 00:24:49,200 --> 00:24:52,580 Bu asimptotik daimi bir time-- böyük Ç. 590 00:24:52,580 --> 00:24:54,720 Və səmimi, yalnız Real dünya, bu 591 00:24:54,720 --> 00:24:58,380 Daven adı alır daxil deməkdir beş addımlar, və ya Davenport doqquz kimi 592 00:24:58,380 --> 00:25:00,100 addımlar, və ya David beş addımlar. 593 00:25:00,100 --> 00:25:03,071 Bu olduqca darn kiçik çalışan dəfə var. 594 00:25:03,071 --> 00:25:05,320 Və həqiqətən, bir çox var Yaxşı şey, xüsusilə 595 00:25:05,320 --> 00:25:08,126 Bu cəmi asılı deyil orada elementlərin sayı. 596 00:25:08,126 --> 00:25:10,500 Beləliklə, biz bu həyata bilər necə kodu strukturunun cür? 597 00:25:10,500 --> 00:25:12,900 Bu bir az daha çox mürəkkəb, lakin hələ də var 598 00:25:12,900 --> 00:25:15,050 yalnız bir proqram əsas bloklar. 599 00:25:15,050 --> 00:25:17,830 Mən yenidən gedirəm Bizə node aşağıdakı kimi: 600 00:25:17,830 --> 00:25:21,100 bool word-- adlanır və bu bir şey adlandırmaq olar. 601 00:25:21,100 --> 00:25:23,970 Amma bool təmsil nə bir onay işareti kimi çəkdi. 602 00:25:23,970 --> 00:25:24,490 Bəli. 603 00:25:24,490 --> 00:25:26,720 Bu simli sonu Bu data strukturu. 604 00:25:26,720 --> 00:25:30,702 >> Və, əlbəttə, node ulduz uşaq var istinad edilir. 605 00:25:30,702 --> 00:25:32,410 Və həqiqətən, yalnız kimi bir ailə ağacı, siz 606 00:25:32,410 --> 00:25:34,370 qovşaqlarının hesab edirəm off asma olunur 607 00:25:34,370 --> 00:25:36,920 bəzi müəssisənin alt element uşaqlar üçün. 608 00:25:36,920 --> 00:25:40,510 Və belə ki, uşaqlar gedir 27 bir sıra 27 biri ola 609 00:25:40,510 --> 00:25:41,680 yalnız apostrof üçün olan. 610 00:25:41,680 --> 00:25:43,390 Biz düzmək olacaq Xüsusi halda ki. 611 00:25:43,390 --> 00:25:45,400 Belə ki, müəyyən ola bilər apostrophes ilə adları. 612 00:25:45,400 --> 00:25:47,399 Bəlkə hətta tire olmalıdır orada getmək, lakin siz lazımdır 613 00:25:47,399 --> 00:25:50,330 p set 5 yalnız qayğı görmək məktublar və apostrophes haqqında. 614 00:25:50,330 --> 00:25:52,990 >> Və sonra necə təmsil edə Bu data strukturu özü? 615 00:25:52,990 --> 00:25:56,454 Necə kök təmsil Bu trie, belə danışmaq? 616 00:25:56,454 --> 00:25:59,620 Bəli, yalnız bir bağlı siyahısı ilə kimi ilk element bir göstərici lazımdır. 617 00:25:59,620 --> 00:26:04,270 Bir trie ilə yalnız bir ehtiyac bu trie kök göstərici. 618 00:26:04,270 --> 00:26:07,290 Və oradan hash bilər yol aşağı dərin və daha dərin 619 00:26:07,290 --> 00:26:10,460 tərkibində hər node. 620 00:26:10,460 --> 00:26:13,440 Belə ki, sadəcə bu can ilə biz struct təmsil edir. 621 00:26:13,440 --> 00:26:15,877 >> İndi Oh sual Meanwhile--. 622 00:26:15,877 --> 00:26:17,220 >> Auditoriya: bool söz nədir? 623 00:26:17,220 --> 00:26:20,490 >> DAVID MALAN: Bool söz yalnız bu C təcəssüm 624 00:26:20,490 --> 00:26:22,920 Mən təsvir nə Burada, bu qutusuna 625 00:26:22,920 --> 00:26:26,000 Mən hər parçalanması başladı iki hissəyə serialın elementləri. 626 00:26:26,000 --> 00:26:27,600 One növbəti node bir göstərici deyil. 627 00:26:27,600 --> 00:26:30,280 Digər olmalıdır bir onay qutusu kimi bir şey 628 00:26:30,280 --> 00:26:33,770 bir var, bəli demək burada bitir Daven söz, 629 00:26:33,770 --> 00:26:35,610 Biz istəmirik Hal-, Dave da. 630 00:26:35,610 --> 00:26:39,320 >> Dave bir olacaq baxmayaraq qanuni söz, o trie deyil 631 00:26:39,320 --> 00:26:39,830 hələ. 632 00:26:39,830 --> 00:26:40,950 Və D bir söz deyil. 633 00:26:40,950 --> 00:26:42,770 Və D-A bir söz və ya bir ad deyil. 634 00:26:42,770 --> 00:26:45,020 Bu onay işareti So yalnız sizin dəfə göstərir 635 00:26:45,020 --> 00:26:48,190 Bu node təşkil edib simvol əvvəlki yolu 636 00:26:48,190 --> 00:26:50,700 Siz daxil etdiyiniz həqiqətən bir string. 637 00:26:50,700 --> 00:26:53,660 Belə ki, bütün bool var Bizim üçün edir. 638 00:26:53,660 --> 00:26:55,500 >> Çalışır hər hansı digər suallar? 639 00:26:55,500 --> 00:26:56,215 Bəli. 640 00:26:56,215 --> 00:26:58,035 >> Auditoriya: üst-üstə düşür nədir? 641 00:26:58,035 --> 00:26:59,945 Nə Dave və Daven varsa? 642 00:26:59,945 --> 00:27:00,820 DAVID MALAN: Perfect. 643 00:27:00,820 --> 00:27:02,580 Nə Dave və Daven varsa? 644 00:27:02,580 --> 00:27:06,240 Biz daxil Belə ki, bir ləqəb demək David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Bu, həqiqətən, super sadədir. 647 00:27:08,700 --> 00:27:10,325 Beləliklə, biz yalnız dörd addımlar olacaq. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. Mən nə var Mən dördüncü node hit bir dəfə? 650 00:27:15,847 --> 00:27:16,680 Just yoxlamaq olacaq. 651 00:27:16,680 --> 00:27:18,000 Biz artıq getmək iyi. 652 00:27:18,000 --> 00:27:18,840 Done. 653 00:27:18,840 --> 00:27:19,750 Dörd addımlar. 654 00:27:19,750 --> 00:27:21,590 Asimptotik daimi vaxt. 655 00:27:21,590 --> 00:27:26,300 Və indi biz də Dave qeyd etdik və Daven tərkibində strings var. 656 00:27:26,300 --> 00:27:27,710 Belə bir problem. 657 00:27:27,710 --> 00:27:30,200 Və necə varlığı hiss Daven onu etməyib 658 00:27:30,200 --> 00:27:34,750 daha çox vaxt az və ya vaxt Dave və əksinə. 659 00:27:34,750 --> 00:27:36,000 >> Beləliklə, biz indi başqa nə edə bilər? 660 00:27:36,000 --> 00:27:40,680 Biz əvvəl bu məcaz istifadə etdiyiniz qablar bir şey təmsil. 661 00:27:40,680 --> 00:27:43,380 Amma bu çıxır ki, bir qablar yığını əslində 662 00:27:43,380 --> 00:27:47,187 başqa mücərrəd data nümayişkaranə yüksək səviyyəli data strukturu yazın 663 00:27:47,187 --> 00:27:49,770 sonunda gün yalnız ki, bir sıra və ya bir bağlı siyahısı kimi 664 00:27:49,770 --> 00:27:50,970 daha çox dünyəvi və ya bir şey. 665 00:27:50,970 --> 00:27:53,270 Amma bir daha maraqlıdır konseptual anlayış. 666 00:27:53,270 --> 00:27:56,440 Bu kimi bir yığın, Mather burada novları, 667 00:27:56,440 --> 00:27:58,750 ümumiyyətlə deyilir yalnız bir yığın that--. 668 00:27:58,750 --> 00:28:02,540 >> Və data strukturu bu növü iki operations-- var 669 00:28:02,540 --> 00:28:05,880 bir adlı təkan üçün yığını bir şey əlavə, 670 00:28:05,880 --> 00:28:08,320 başqa bir tray qoyulması kimi yığını üst geri. 671 00:28:08,320 --> 00:28:11,350 Sizə deməkdir və sonra pop topmost tray off edir. 672 00:28:11,350 --> 00:28:16,210 Amma bir yığın ki, haqqında əsas nə Bu maraqlı xüsusiyyəti var. 673 00:28:16,210 --> 00:28:19,560 Yemekhane heyəti kimi növbəti yemək üçün qablar yenidən, 674 00:28:19,560 --> 00:28:21,380 nə olacaq tələbələrə haqqında doğru 675 00:28:21,380 --> 00:28:22,856 Bu data strukturu ilə qarşılıqlı? 676 00:28:22,856 --> 00:28:24,480 Auditoriya: Onlar bir off pop olacaq. 677 00:28:24,480 --> 00:28:26,550 DAVID MALAN: Onlar olacaq bir off, inşallah üst pop. 678 00:28:26,550 --> 00:28:28,910 Əks halda yalnız cür axmaq var alt bütün yol getmək. 679 00:28:28,910 --> 00:28:29,070 Right? 680 00:28:29,070 --> 00:28:31,620 Bu data strukturu həqiqətən imkan vermir ən azı alt tray qamarlamaq üçün 681 00:28:31,620 --> 00:28:32,520 asanlıqla. 682 00:28:32,520 --> 00:28:35,040 Belə ki, bu maraqlı var Bir yığın əmlak 683 00:28:35,040 --> 00:28:39,730 son maddə ilk biri olacaq. 684 00:28:39,730 --> 00:28:43,400 Və kompüter alimləri zəng Bu ilk, həyata davam LIFO--. 685 00:28:43,400 --> 00:28:45,540 Və həqiqətən var maraqlı applications. 686 00:28:45,540 --> 00:28:50,090 Bu, mütləq bəzi kimi aydın deyil başqaları, lakin, həqiqətən, faydalı ola bilər 687 00:28:50,090 --> 00:28:54,040 və bu, həqiqətən, həyata keçirilə bilər müxtəlif yollarla bir neçə. 688 00:28:54,040 --> 00:28:58,550 >> Belə ki, bir, həqiqətən, qoy Mənə daxil dalış deyil. 689 00:28:58,550 --> 00:28:59,860 Əvəzinə bunu edək. 690 00:28:59,860 --> 00:29:03,700 Nin demək olar ki, var ki, bir baxaq eyni fikir, lakin bir az ədalətli var. 691 00:29:03,700 --> 00:29:04,200 Right? 692 00:29:04,200 --> 00:29:07,560 Bu fan oğlanlar biri edirsinizsə və ya həqiqətən Apple məhsulları sevir ki, qızlar 693 00:29:07,560 --> 00:29:10,130 və 3:00 AM oyandı Bəzi mağaza sıralamaq üçün 694 00:29:10,130 --> 00:29:14,150 son iPhone almaq üçün, bu kimi sıraya ola bilər. 695 00:29:14,150 --> 00:29:15,800 >> İndi növbə çox qəsdən adlanır. 696 00:29:15,800 --> 00:29:18,190 Var, çünki xətti bəzi ədalət. 697 00:29:18,190 --> 00:29:18,690 Right? 698 00:29:18,690 --> 00:29:21,690 Siz var əgər bu cür sucked ki Apple Store ilk var 699 00:29:21,690 --> 00:29:25,700 lakin səmərəli bottommost var tray sonra Apple işçilərinin çünki 700 00:29:25,700 --> 00:29:28,189 son şəxs pop edən həqiqətən xətti var. 701 00:29:28,189 --> 00:29:31,230 Borular və sıralarında, baxmayaraq belə funksional onlar same-- cür edirik 702 00:29:31,230 --> 00:29:33,105 yalnız bu toplanması resursların ki 703 00:29:33,105 --> 00:29:36,210 orada var shrink-- inkişaf gedir və bu bu ədalət aspekt, 704 00:29:36,210 --> 00:29:39,634 Real dünyada ən azı, burada əməliyyatları həyata 705 00:29:39,634 --> 00:29:40,800 əsaslı fərqlidir. 706 00:29:40,800 --> 00:29:43,360 Bir sıra A stack-- rather-- deyilir 707 00:29:43,360 --> 00:29:45,320 iki əməliyyatları: n queue və d queue. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Yoxsa onlara zəng edə bilərsiniz hər hansı bir sayı. 710 00:29:48,090 --> 00:29:50,770 Amma yalnız tutmaq istəyirəm bir əlavə edir ki, anlayışı 711 00:29:50,770 --> 00:29:53,230 və bir nəticədə subtracting edir. 712 00:29:53,230 --> 00:29:58,840 >> İndi başlıq altında, həm də yığını və bir sıra necə həyata keçirilə bilər? 713 00:29:58,840 --> 00:30:01,390 Biz kodu daxil deyil çünki yüksək səviyyəli 714 00:30:01,390 --> 00:30:03,387 fikir sort daha göz qabağındadır. 715 00:30:03,387 --> 00:30:04,470 Mən demək, insanlar nə etməliyəm? 716 00:30:04,470 --> 00:30:07,030 Mən Apple ilk şəxs deyiləm, Saxlamaq və bu ön qapı, 717 00:30:07,030 --> 00:30:08,130 Mən burada durmaq gedirəm, bilirik. 718 00:30:08,130 --> 00:30:09,750 Və növbəti şəxsin burada durmaq gedir. 719 00:30:09,750 --> 00:30:11,500 Və növbəti şəxsin burada durmaq gedir. 720 00:30:11,500 --> 00:30:13,792 Belə ki, nə data strukturu özü bir sıra verir? 721 00:30:13,792 --> 00:30:14,542 >> Auditoriya: A queue. 722 00:30:14,542 --> 00:30:15,667 DAVID MALAN: Bəli, bir sıra. 723 00:30:15,667 --> 00:30:16,390 Sure. 724 00:30:16,390 --> 00:30:16,920 Nə? 725 00:30:16,920 --> 00:30:17,600 >> Auditoriya: A bağlı siyahı. 726 00:30:17,600 --> 00:30:18,990 >> DAVID MALAN: A bağlıdır Siz həyata bilər edin. 727 00:30:18,990 --> 00:30:22,500 Və əlaqəli siyahısı sonra, çünki gözəl fərqli olaraq uzun özbaşına inkişaf edə bilər 728 00:30:22,500 --> 00:30:24,880 Bəzi sabit sayı olan mağaza insanların. 729 00:30:24,880 --> 00:30:27,030 Amma bəlkə bir sabit sayı yerlərdə qanuni. 730 00:30:27,030 --> 00:30:30,350 Yalnız 20 kimi varsa, çünki bəlkə ilk günündə iPhone 731 00:30:30,350 --> 00:30:33,930 yalnız ölçüsü bir sıra lazımdır 20 ki növbə təmsil edən 732 00:30:33,930 --> 00:30:37,070 Biz söhbət başlamaq dəfə yalnız indi demək olunur Bu yüksək səviyyəli problemlərin, 733 00:30:37,070 --> 00:30:38,890 Siz həyata keçirə bilər yolları bir sıra. 734 00:30:38,890 --> 00:30:42,030 Və yəqin ki, yalnız gedən var məkan və zamanda bir ticarət off ola 735 00:30:42,030 --> 00:30:43,950 və ya yalnız öz kodu mürəkkəbliyi. 736 00:30:43,950 --> 00:30:45,380 >> Bir yığın haqqında nə? 737 00:30:45,380 --> 00:30:48,190 Yaxşı, bir yığın, biz də gördük yalnız bu qablar ola bilər. 738 00:30:48,190 --> 00:30:50,007 Və bu bir sıra həyata bilər. 739 00:30:50,007 --> 00:30:53,090 Lakin bəzi noktada, bir sıra istifadə əgər nə qablar nə olacaq 740 00:30:53,090 --> 00:30:54,173 siz yazmaq çalışdığınız? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Bütün hüquqlar. 743 00:30:55,670 --> 00:30:57,490 Siz yalnız olacaq qədər yüksək getmək mümkün. 744 00:30:57,490 --> 00:31:00,156 Mən onlar Mather hesab həqiqətən açılışında recessed. 745 00:31:00,156 --> 00:31:01,950 Belə ki, həqiqətən, demək olar ki, var Mather istifadə kimi 746 00:31:01,950 --> 00:31:03,783 sabit ölçüsü bir sıra, yalnız, çünki 747 00:31:03,783 --> 00:31:08,302 ki, açılış çox qablar uyğun xalq diz aşağı divar. 748 00:31:08,302 --> 00:31:10,010 Və belə ki, ola bilər, bir sıra olduğu ifadə, 749 00:31:10,010 --> 00:31:14,300 lakin biz, əlbəttə ki, həyata bilər ümumiyyətlə bir bağlı siyahısı ilə. 750 00:31:14,300 --> 00:31:16,390 >> Yaxşı, nə başqa data strukturu haqqında? 751 00:31:16,390 --> 00:31:18,760 Mənə burada vizual birini qoparmaq edək. 752 00:31:18,760 --> 00:31:24,710 Necə burada bu barədə kimi bir şey? 753 00:31:24,710 --> 00:31:28,920 Niyə üçün faydalı ola bilər bir trie, kimi bir şey zənn edən 754 00:31:28,920 --> 00:31:32,370 biz bu çox geniş qovşaqlarının idi gördüm olan hər bir sıra var? 755 00:31:32,370 --> 00:31:35,740 Amma biz bir şey daha nə əgər sadəcə, köhnə məktəb ailə ağac kimi, 756 00:31:35,740 --> 00:31:38,110 kimin burada qovşaqlarının hər yalnız bir sıra saxlanılması. 757 00:31:38,110 --> 00:31:42,180 Bunun əvəzinə bir adı və ya nəslindən yalnız bu kimi bir sıra saxlanılması. 758 00:31:42,180 --> 00:31:45,250 >> Yaxşı, jargon biz istifadə data strukturları, həm də çalışır deyil 759 00:31:45,250 --> 00:31:49,510 və ağaclar, bir trie, yenə olduğu yalnız onların qovşaqlarının Diziler biri, 760 00:31:49,510 --> 00:31:51,680 hələ nə bilər sinif məktəbin istifadə 761 00:31:51,680 --> 00:31:53,860 Bir ailə zaman ağac yarpaqları və kök 762 00:31:53,860 --> 00:31:57,250 ağac və uşaqların valideyn və onların bacı. 763 00:31:57,250 --> 00:32:03,670 Və biz bir ağac həyata bilər, Məsələn, kimi sadəcə bu kimi. 764 00:32:03,670 --> 00:32:07,420 A ağac, bu bir node, biri kimi bir sıra var ki, bu dairələr, 765 00:32:07,420 --> 00:32:09,947 Bu var niyyətində deyil bir pointer, lakin iki. 766 00:32:09,947 --> 00:32:11,780 Və tezliklə əlavə kimi ikinci göstərici, siz 767 00:32:11,780 --> 00:32:13,905 həqiqətən, indi sort edə bilərsiniz iki ölçülü məlumatların 768 00:32:13,905 --> 00:32:14,780 yaddaş strukturları. 769 00:32:14,780 --> 00:32:16,660 Iki ölçülü kimi Much array, siz 770 00:32:16,660 --> 00:32:18,904 iki ölçülü cür var bağlı siyahıları lakin olanları 771 00:32:18,904 --> 00:32:20,820 ki, bir model edin burada heç bir dövründən var. 772 00:32:20,820 --> 00:32:24,487 Bu biri ilə həqiqətən canından burada və sonra grandparent yolu 773 00:32:24,487 --> 00:32:27,320 bəzi valideynlər və uşaqlar və nəvəsi və böyük nəvəsi. 774 00:32:27,320 --> 00:32:28,370 və s. 775 00:32:28,370 --> 00:32:32,390 >> Lakin, çox bu barədə həqiqətən səliqəli nə yalnız kodu bir az ilə siz tease üçün, 776 00:32:32,390 --> 00:32:35,370 olan geri recursion biraz geri, vasitəsi 777 00:32:35,370 --> 00:32:38,220 özünü çağırır ki, bir funksiyası yazmaq. 778 00:32:38,220 --> 00:32:41,140 Bu gözəl imkandır bir şey həyata 779 00:32:41,140 --> 00:32:42,920 Recursion kimi, çünki bu hesab. 780 00:32:42,920 --> 00:32:43,860 >> Bu ağac. 781 00:32:43,860 --> 00:32:48,040 Mən necə bir az anal oldum Mən küçəyə integers qoydu. 782 00:32:48,040 --> 00:32:51,020 Belə ki, bu xüsusi var bir ikili axtarış ağac konseptual mənada adı. 783 00:32:51,020 --> 00:32:53,460 İndi biz ikili eşitdim siz axtarış, lakin bilər 784 00:32:53,460 --> 00:32:55,180 Bu şey adı geri iş? 785 00:32:55,180 --> 00:32:59,280 I necə model nədir bu ağac daxil integers daxil? 786 00:32:59,280 --> 00:33:00,696 Bu ixtiyari deyil. 787 00:33:00,696 --> 00:33:01,570 Bəzi model var. 788 00:33:01,570 --> 00:33:02,090 Bəli. 789 00:33:02,090 --> 00:33:03,370 >> Auditoriya: sol Kiçik olanları. 790 00:33:03,370 --> 00:33:03,690 >> DAVID MALAN: Bəli. 791 00:33:03,690 --> 00:33:05,062 Kiçik olanları sol var. 792 00:33:05,062 --> 00:33:06,270 Böyük olanları sağ var. 793 00:33:06,270 --> 00:33:12,940 Belə bir gerçək bir bəyanat ki, valideyn, onun sol uşaq daha böyükdür 794 00:33:12,940 --> 00:33:14,850 Onun sağ uşaq daha lakin az. 795 00:33:14,850 --> 00:33:17,750 Və tək ki, hətta bir deyil recursive şifahi definition 796 00:33:17,750 --> 00:33:20,500 ki, müraciət edə bilər, çünki hər node eyni məntiq 797 00:33:20,500 --> 00:33:23,080 və yalnız dibi həyata, baza halda əgər 798 00:33:23,080 --> 00:33:25,740 olacaq, zaman bir hit yarpaq, belə ki, danışmaq 799 00:33:25,740 --> 00:33:28,580 bir məzuniyyət daha heç bir övladı var olduğu. 800 00:33:28,580 --> 00:33:30,614 >> İndi necə sayı 44 tapa bilərsiniz? 801 00:33:30,614 --> 00:33:32,280 Siz hm kök başlamaq və deyərdim. 802 00:33:32,280 --> 00:33:35,690 55 Mən getmək istəyirəm 44 deyil sağ və ya sol getmək istəyirsiniz? 803 00:33:35,690 --> 00:33:37,190 Bəli, açıq-aydın sol getmək istəyirəm. 804 00:33:37,190 --> 00:33:40,060 Və belə ki, yalnız telefon kimi Binar axtarış kitab nümunə 805 00:33:40,060 --> 00:33:41,099 ümumiyyətlə. 806 00:33:41,099 --> 00:33:43,390 Amma biz bunu həyata edirik İndi bir az daha dinamik 807 00:33:43,390 --> 00:33:45,339 bir sıra imkan bilər daha. 808 00:33:45,339 --> 00:33:48,130 Və əslində, siz baxmaq istəyirsinizsə kodu, ilk baxışda əmin olun. 809 00:33:48,130 --> 00:33:49,671 Bu xətləri bütün dəstə kimi görünür. 810 00:33:49,671 --> 00:33:51,220 Amma bu gözəl sadə. 811 00:33:51,220 --> 00:33:54,490 Bir funksiyası həyata istəyirsinizsə, kimin məqsədi həyat deyilən axtarış 812 00:33:54,490 --> 00:33:57,290 dəyəri axtarmaq üçün nə kimi n, bir tam, 813 00:33:57,290 --> 00:34:01,756 və bir pointer qəbul edirik kökləri node bir göstərici, 814 00:34:01,756 --> 00:34:04,380 daha ki, ağac olan Siz başqa hər şey edə bilərsiniz 815 00:34:04,380 --> 00:34:08,850 necə straightforwardly qeyd Siz məntiq həyata keçirə bilər. 816 00:34:08,850 --> 00:34:10,880 Ağac null əgər, Aydındır ki, bu yoxdur. 817 00:34:10,880 --> 00:34:11,880 Yalnız yalan qayıtmaq edək. 818 00:34:11,880 --> 00:34:12,000 Right? 819 00:34:12,000 --> 00:34:14,040 Siz heç bir şey edirsinizsə, var heç bir şey yoxdur. 820 00:34:14,040 --> 00:34:17,900 >> Else n az, əgər İndi n arrow n ağac arrow, 821 00:34:17,900 --> 00:34:20,670 biz super təqdim geri qısa gün, 822 00:34:20,670 --> 00:34:25,100 və yalnız de-istinad deməkdir pointer və n adlı sahəsində baxmaq. 823 00:34:25,100 --> 00:34:27,690 Belə ki, orada getmək deməkdir n adlı sahəsində baxmaq. 824 00:34:27,690 --> 00:34:33,810 Belə ki, n, əgər sunulur dəyəri, az ağaclar tam dəyərinin daha, 825 00:34:33,810 --> 00:34:35,449 harada getmək istəyirsiniz? 826 00:34:35,449 --> 00:34:36,389 Sol. 827 00:34:36,389 --> 00:34:37,780 >> Belə ki, recursion bilərsiniz. 828 00:34:37,780 --> 00:34:39,860 Mən doğru deyil returning-- deyiləm. 829 00:34:39,860 --> 00:34:40,989 Yalan deyil. 830 00:34:40,989 --> 00:34:45,670 Mən nə cavab qaytarılması alıram özümə zəng edir, keçən 831 00:34:45,670 --> 00:34:50,100 lazımsız olan daha bir n, lakin indi az müxtəlif var? 832 00:34:50,100 --> 00:34:51,989 Necə mən kiçik problem qəbul edirəm? 833 00:34:51,989 --> 00:34:54,920 Mən ikinci keçən alıram dəlil, ağac deyil kök, 834 00:34:54,920 --> 00:34:59,616 lakin bu halda sol uşaq. 835 00:34:59,616 --> 00:35:00,990 Mən sol uşaq keçən alıram. 836 00:35:00,990 --> 00:35:04,720 >> Eyni zamanda n daha böyük, əgər Hal-hazırda da arıyorum node, 837 00:35:04,720 --> 00:35:06,690 Mən sağ tərəfdən axtarış. 838 00:35:06,690 --> 00:35:10,880 Else, ağac, null deyil və Bu element sol deyil, 839 00:35:10,880 --> 00:35:13,240 və, sağ deyil halda gözəl nədir? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Biz, həqiqətən də node gördük sual, və biz doğru qayıtmaq. 842 00:35:18,440 --> 00:35:21,490 >> Beləliklə, biz yalnız səthi cızıqlanmış sonra İndi bu data strukturları bəzi. 843 00:35:21,490 --> 00:35:24,370 Problem set beş sizə lazımdır hələ bundan sonra da bu araşdırmaq, 844 00:35:24,370 --> 00:35:27,250 və sizin dizayn verilir bu barədə getmək necə seçim. 845 00:35:27,250 --> 00:35:30,250 Mən bağlamaq istədiyiniz nə yalnız 30 ikinci iltifat edir 846 00:35:30,250 --> 00:35:32,080 kənarda gələn həftə və gözləyir nə. 847 00:35:32,080 --> 00:35:35,390 >> Biz təşəkkürlə begin-- kimi bilər yavaş-yavaş bizim keçid think-- 848 00:35:35,390 --> 00:35:38,680 C və aşağı dünya səviyyədə həyata ətraflı, 849 00:35:38,680 --> 00:35:42,090 bir dünyada olan biz bilər başqası nəhayət ki, verilən 850 00:35:42,090 --> 00:35:44,010 Bu data tətbiq bizim üçün strukturları, 851 00:35:44,010 --> 00:35:47,570 və biz anlamaq üçün başlamaq lazımdır real dünya həyata deməkdir 852 00:35:47,570 --> 00:35:50,560 web-based proqramları və saytları ümumiyyətlə 853 00:35:50,560 --> 00:35:52,910 və də çox təhlükəsizlik biz yalnız var ki, təsiri 854 00:35:52,910 --> 00:35:54,850 səthində danışıq başlayıb. 855 00:35:54,850 --> 00:35:57,320 Burada bizi gözləyir nə gün gəlib. 856 00:35:57,320 --> 00:36:00,480 >> [Video playback] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> O, bir mesaj gəldi bütün öz protokol. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 O, qəddar bir dünyaya gəldi firewall, uncaring yönlendirici, 861 00:36:30,894 --> 00:36:33,368 və təhlükələr ölüm çox pis. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 O, sürətli. 864 00:36:36,236 --> 00:36:37,980 O, güclü var. 865 00:36:37,980 --> 00:36:42,830 O, TCP / IP, və o ünvanınızı var. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Net Warriors." 868 00:36:48,074 --> 00:36:49,660 [END video playback] 869 00:36:49,660 --> 00:36:50,910 DAVID MALAN: gələn həftə gəlir. 870 00:36:50,910 --> 00:36:51,880 Biz sonra görəcəksiniz. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [Video playback] 873 00:36:56,060 --> 00:36:59,240 -Və Indi "Deep Thoughts" Daven Farnham tərəfindən. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 David həmişə başlayır ilə mühazirələr "Bütün hüququ." 876 00:37:05,820 --> 00:37:08,750 Niyə "Burada həll bu həftə problem set "üçün 877 00:37:08,750 --> 00:37:12,180 və ya "Biz A sizə bütün ötürür?" 878 00:37:12,180 --> 00:37:13,380 [Gülür] 879 00:37:13,380 --> 00:37:15,530 [END video playback]