1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID MALAN: Baiklah. 3 00:00:12,250 --> 00:00:13,860 Selamat kembali ke CS50. 4 00:00:13,860 --> 00:00:16,190 Ini adalah permulaan minggu 8. 5 00:00:16,190 --> 00:00:21,320 Dan ingat bahawa set masalah 5 berakhir dengan sedikit cabaran. 6 00:00:21,320 --> 00:00:25,210 Jadi andaian anda pulih semua anda Felo pengajaran dan gambar-gambar CA 7 00:00:25,210 --> 00:00:30,480 dalam fail card.raw, anda layak kini mencari semua orang-orang, dan 8 00:00:30,480 --> 00:00:34,510 seorang pemenang bertuah akan berjalan kaki ke rumah dengan satu perkara-perkara ini, gerakan lompat 9 00:00:34,510 --> 00:00:37,450 alat yang boleh anda gunakan untuk akhir projek, misalnya. 10 00:00:37,450 --> 00:00:39,860 >> Ini, setiap tahun, membawa kepada sedikit creepiness. 11 00:00:39,860 --> 00:00:43,480 Dan supaya apa yang saya fikir saya akan lakukan ialah berkongsi dengan anda beberapa nota yang mempunyai 12 00:00:43,480 --> 00:00:47,370 pergi dan balik ke atas senarai kakitangan lewat. 13 00:00:47,370 --> 00:00:51,110 Sebagai contoh, hanya malam tadi, quote unquote, dari salah seorang kakitangan 14 00:00:51,110 --> 00:00:55,000 anggota, "Saya hanya mempunyai ketukan pelajar di pintu saya untuk mengambil gambar dengan saya. 15 00:00:55,000 --> 00:00:59,020 Stalkers, saya memberitahu anda. "Bermula dari agak deskriptif dan kemudian kami berpindah 16 00:00:59,020 --> 00:01:02,830 ke, satu jam atau lebih kemudian, "Saya mempunyai pelajar menunggu saya selepas seksyen 17 00:01:02,830 --> 00:01:06,080 dan dia mempunyai semua nama-nama dan gambar kami pada beberapa keping kertas. "Baiklah. 18 00:01:06,080 --> 00:01:09,230 Jadi dianjurkan, tetapi tidak semua yang menyeramkan yet. 19 00:01:09,230 --> 00:01:12,520 >> Kemudian, "Saya berada di luar bandar hujung minggu ini, dan apabila saya kembali, terdapat satu dalam 20 00:01:12,520 --> 00:01:12,630 saya 21 00:01:12,630 --> 00:01:16,740 bilik tidur. "[Ketawa] 22 00:01:16,740 --> 00:01:20,410 DAVID MALAN: quote Next daripada kakitangan anggota, "seorang pelajar datang ke rumah saya di 23 00:01:20,410 --> 00:01:25,330 Somerville pada 4:00 pagi ini. "Next kakitangan, "saya mendapat ke hotel saya di San 24 00:01:25,330 --> 00:01:30,016 Francisco dan pelajar yang sedang menunggu saya di lobi dengan tiga DSLRs. " 25 00:01:30,016 --> 00:01:31,510 Jenis kamera. 26 00:01:31,510 --> 00:01:34,980 "Saya tidak walaupun pada kakitangan semester ini, tetapi pelajar memecah masuk ke rumah saya ini 27 00:01:34,980 --> 00:01:40,480 pagi dan merekodkan segala-galanya dengan Google Glass. "Dan kemudian akhir sekali, 28 00:01:40,480 --> 00:01:43,650 "Sekurang-kurangnya 12 orang telah bersungguh-sungguh menunggu bagi saya apabila saya keluar dari saya 29 00:01:43,650 --> 00:01:44,800 limousin, dan kemudian saya 30 00:01:44,800 --> 00:01:46,970 bangun. "Baiklah. 31 00:01:46,970 --> 00:01:57,690 Jadi antara gambar-gambar, seperti yang anda boleh ingat, adalah rakan-rakan ini di sini, yang anda 32 00:01:57,690 --> 00:02:01,850 mungkin dikenali sebagai Milo Pisang, yang tinggal dengan Lauren Carvalho, kepala kita 33 00:02:01,850 --> 00:02:02,905 Fellow pengajaran. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, datang ke sini lelaki. 35 00:02:05,170 --> 00:02:06,320 Milo. 36 00:02:06,320 --> 00:02:08,650 Milo. 37 00:02:08,650 --> 00:02:12,230 Minda anda, dia memakai Google Glass, jadi kami akan menunjukkan kepada anda semua ini selepas. 38 00:02:12,230 --> 00:02:16,190 Jadi ini adalah Milo jika anda ingin mengambil gambar dengan dia selepas itu. 39 00:02:16,190 --> 00:02:18,240 Jika anda ingin untuk melihat keluar pada penonton di sana. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 Itulah rakaman yang baik. 42 00:02:20,200 --> 00:02:22,556 Nah, Milo Pisang. 43 00:02:22,556 --> 00:02:23,941 Oh, tidak berbuat demikian. 44 00:02:23,941 --> 00:02:29,020 >> [Ketawa] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Jadi perkataan kemudian apa yang akan berlaku, kerana seperti yang kita mula peralihan, 47 00:02:34,550 --> 00:02:38,410 minggu ini khususnya, daripada C dalam persekitaran baris arahan untuk PHP dan 48 00:02:38,410 --> 00:02:42,720 JavaScript dan SQL dan HTML dan CSS dalam persekitaran berasaskan web, kami akan 49 00:02:42,720 --> 00:02:44,490 melengkapkan anda dengan semua lebih banyak pengetahuan untuk 50 00:02:44,490 --> 00:02:46,010 potensi projek akhir. 51 00:02:46,010 --> 00:02:49,240 Ke arah itu, tentu mempunyai tradisi mengadakan seminar yang 52 00:02:49,240 --> 00:02:50,950 adalah mengenai topik-topik yang menyeleweng untuk kursus. 53 00:02:50,950 --> 00:02:54,330 Sangat banyak yang berkaitan dengan pengaturcaraan dan pembangunan aplikasi dan sebagainya, tetapi 54 00:02:54,330 --> 00:02:57,010 tidak semestinya diterokai oleh sukatan pelajaran kursus sendiri. 55 00:02:57,010 --> 00:03:00,250 >> Jadi, jika anda mungkin berminat dalam satu atau lebih seminar tahun ini, 56 00:03:00,250 --> 00:03:02,530 mendaftar di cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Terdapat seminar lebih tua di cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 Dan dalam jadual setakat ini untuk tahun ini adalah Amazing Web Apps dengan Ruby on 59 00:03:10,620 --> 00:03:13,580 Rails, yang merupakan alternatif bahasa untuk PHP. 60 00:03:13,580 --> 00:03:14,900 Linguistik pengiraan. 61 00:03:14,900 --> 00:03:18,710 Pengenalan kepada IOS, yang merupakan platform yang digunakan untuk iPhone dan 62 00:03:18,710 --> 00:03:19,850 pembangunan iPad. 63 00:03:19,850 --> 00:03:22,890 JavaScript untuk Web Apps, kami akan meliputi itu, tetapi dalam seminar ini, anda akan pergi 64 00:03:22,890 --> 00:03:24,070 ke lebih terperinci. 65 00:03:24,070 --> 00:03:27,390 >> Melompat Motion, jadi kita benar-benar akan mempunyai beberapa rakan-rakan kami dari Usul Leap, 66 00:03:27,390 --> 00:03:29,160 syarikat itu sendiri, menyertai kami. 67 00:03:29,160 --> 00:03:31,800 Esok, sebenarnya, untuk memberikan hands-on seminar, jika 68 00:03:31,800 --> 00:03:33,320 menarik minat anda. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, teknik alternatif bagi menggunakan JavaScript tidak dalam pelayar, 70 00:03:38,770 --> 00:03:39,970 tetapi pada pelayan. 71 00:03:39,970 --> 00:03:42,110 Node.js, yang sangat banyak dalam urat itu juga. 72 00:03:42,110 --> 00:03:43,650 Anggun Android Design. 73 00:03:43,650 --> 00:03:46,990 Android menjadi alternatif yang sangat popular untuk IOS dan Telefon Windows 74 00:03:46,990 --> 00:03:48,790 dan platform mudah alih yang lain. 75 00:03:48,790 --> 00:03:51,180 Dan Web Keselamatan Pertahanan Aktif. 76 00:03:51,180 --> 00:03:54,590 >> Jadi pada hakikatnya, jika anda ingin untuk melibatkan diri dalam hal ini, izinkan saya 77 00:03:54,590 --> 00:03:55,840 membuat nota ini. 78 00:03:55,840 --> 00:03:57,790 Kami amat gembira untuk mengatakan bahawa rakan-rakan kami di Leap 79 00:03:57,790 --> 00:03:59,140 Gerakan, yang merupakan permulaan - 80 00:03:59,140 --> 00:04:01,300 peranti ini benar-benar hanya datang keluar beberapa bulan lalu - 81 00:04:01,300 --> 00:04:05,960 telah anggun menderma 30 peranti sedemikian dalam kelas sebagai ramai pelajar, jika 82 00:04:05,960 --> 00:04:08,670 anda ingin meminjam perkakasan penghujung semester dan menggunakannya untuk 83 00:04:08,670 --> 00:04:10,390 projek akhir sebenar. 84 00:04:10,390 --> 00:04:11,890 Mereka menyokong beberapa bahasa. 85 00:04:11,890 --> 00:04:16,040 Tiada seorang pun daripada mereka C, tiada mereka PHP, jadi sedar satu atau lebih daripada seminar ini 86 00:04:16,040 --> 00:04:16,899 mungkin membuktikan kepentingan. 87 00:04:16,899 --> 00:04:19,730 Dan semua mereka akan difilemkan di Sekiranya anda tidak dapat 88 00:04:19,730 --> 00:04:21,380 untuk hadir. 89 00:04:21,380 --> 00:04:25,000 Jadual ini akan diumumkan melalui e-mel seperti yang kita mengukuhkan bilik. 90 00:04:25,000 --> 00:04:28,460 >> Dan akhir sekali, jika anda pergi ke projects.cs.50.net, ini adalah laman web 91 00:04:28,460 --> 00:04:31,450 kami mengekalkan setiap tahun bahawa kami menjemput orang dari masyarakat, fakulti, 92 00:04:31,450 --> 00:04:36,420 jabatan, kakitangan, dan kedua-dua di luar CS50 untuk 93 00:04:36,420 --> 00:04:37,730 mencadangkan idea-idea projek. 94 00:04:37,730 --> 00:04:39,050 Perkara yang menarik minat kumpulan pelajar. 95 00:04:39,050 --> 00:04:40,600 Perkara yang menarik untuk jabatan. 96 00:04:40,600 --> 00:04:43,990 Jadi jangan menjadikan di sana jika anda berjuang dengan ketidaktentuan tentang apa yang anda 97 00:04:43,990 --> 00:04:46,700 diri anda ingin untuk menangani. 98 00:04:46,700 --> 00:04:51,760 >> Jadi masa lepas, kita memperkenalkan dikatakan struktur data yang lebih kompleks daripada kita akan 99 00:04:51,760 --> 00:04:53,300 dilihat dalam beberapa minggu lalu. 100 00:04:53,300 --> 00:04:56,550 Kami akan telah menggunakan array cukup gembira sebagai berguna jika 101 00:04:56,550 --> 00:04:58,160 struktur data mudah. 102 00:04:58,160 --> 00:05:00,570 Kemudian kami memperkenalkan ini, yang sudah tentu dikaitkan senarai. 103 00:05:00,570 --> 00:05:05,470 Dan apa yang merupakan salah satu motivasi untuk memperkenalkan struktur data ini? 104 00:05:05,470 --> 00:05:06,930 Ya? 105 00:05:06,930 --> 00:05:07,250 Apa itu? 106 00:05:07,250 --> 00:05:08,080 >> PENONTON: saiz Dinamik. 107 00:05:08,080 --> 00:05:09,040 >> DAVID MALAN: saiz Dinamik. 108 00:05:09,040 --> 00:05:11,890 Jadi, manakala dalam pelbagai, anda perlu tahu saiz terlebih dahulu apabila 109 00:05:11,890 --> 00:05:12,740 anda memperuntukkan itu. 110 00:05:12,740 --> 00:05:14,380 Dalam senarai berkaitan, anda tidak perlu tahu bahawa. 111 00:05:14,380 --> 00:05:17,610 Anda boleh hanya malloc, atau lebih amnya, peruntukan tambahan 112 00:05:17,610 --> 00:05:20,720 nod, jadi untuk bercakap, bila-bila masa anda mahu masukkan lebih banyak data. 113 00:05:20,720 --> 00:05:22,670 Dan nod tidak mempunyai ditentukan makna. 114 00:05:22,670 --> 00:05:25,580 Ia hanya istilah generik menggambarkan beberapa jenis bekas yang kami 115 00:05:25,580 --> 00:05:29,610 menggunakan dalam struktur data kami untuk menyimpan beberapa perkara yang menarik, yang ini 116 00:05:29,610 --> 00:05:31,750 kes berada integer. 117 00:05:31,750 --> 00:05:33,160 >> Tetapi selalu ada tradeoff a. 118 00:05:33,160 --> 00:05:38,070 Jadi kita mendapatkan saiz dinamik data struktur, tetapi apakah harga yang kita bayar? 119 00:05:38,070 --> 00:05:40,040 Apa keburukan senarai berkaitan? 120 00:05:40,040 --> 00:05:41,006 Ya? 121 00:05:41,006 --> 00:05:41,980 >> PENONTON: Memerlukan memori yang lebih. 122 00:05:41,980 --> 00:05:44,240 >> DAVID MALAN: Ia memerlukan lebih ingatan, bagaimana sebenarnya? 123 00:05:44,240 --> 00:05:46,440 >> PENONTON: [didengar]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID MALAN: Tepat sekali. 125 00:05:47,050 --> 00:05:50,460 Jadi sekarang kita telah mengambil petunjuk memori tambahan yang kita sebelum ini 126 00:05:50,460 --> 00:05:53,040 tidak perlu, kerana kelebihan sebuah array, sudah tentu, adalah bahawa 127 00:05:53,040 --> 00:05:54,860 segala-galanya berdampingan, belakang untuk kembali ke belakang, yang 128 00:05:54,860 --> 00:05:56,380 memberikan anda akses secara rawak. 129 00:05:56,380 --> 00:06:00,710 Kerana hanya dengan menggunakan kurungan persegi notasi, atau lebih teknikal penunjuk 130 00:06:00,710 --> 00:06:03,580 aritmetik, tambahan yang sangat mudah, anda boleh mengakses mana-mana 131 00:06:03,580 --> 00:06:05,700 elemen dalam masa yang sama. 132 00:06:05,700 --> 00:06:08,975 Dan sebenarnya, itu jenis membayangkan pada harga lain yang kita membayar dengan 133 00:06:08,975 --> 00:06:09,760 senarai berkaitan. 134 00:06:09,760 --> 00:06:13,890 >> Apa yang berlaku kepada masa perjalanan sesuatu seperti Search, jika saya ingin 135 00:06:13,890 --> 00:06:17,270 mencari nilai dan di dalam senarai yang dikaitkan? 136 00:06:17,270 --> 00:06:20,290 Apakah masa saya berjalan menjadi? 137 00:06:20,290 --> 00:06:21,560 Big O n. 138 00:06:21,560 --> 00:06:24,060 Jika ia disusun? 139 00:06:24,060 --> 00:06:25,440 Bagaimana jika struktur data yang disusun? 140 00:06:25,440 --> 00:06:28,640 Bolehkah saya melakukan lebih baik daripada yang besar O n untuk mencari? 141 00:06:28,640 --> 00:06:31,700 Tidak, kerana dalam kes paling teruk ia mungkin baik boleh disusun, tetapi bilangan 142 00:06:31,700 --> 00:06:32,950 yang anda cari mungkin besar. 143 00:06:32,950 --> 00:06:35,370 Ia mungkin menjadi nombor 100, yang mungkin berlaku untuk semua 144 00:06:35,370 --> 00:06:36,410 cara pada akhir. 145 00:06:36,410 --> 00:06:39,950 Dan kerana anda hanya boleh mengakses berkaitan senarai dalam pelaksanaan ini dengan 146 00:06:39,950 --> 00:06:42,690 cara nod pertama, anda masih jenis daripada nasib. 147 00:06:42,690 --> 00:06:47,450 Anda perlu merentasi segala-galanya dari pertama berlangsung untuk mencari 148 00:06:47,450 --> 00:06:49,150 bahawa nilai besar seperti 100. 149 00:06:49,150 --> 00:06:51,350 Atau untuk menentukan sama ada ia tidak walaupun di sana. 150 00:06:51,350 --> 00:06:55,960 >> Jadi kita tidak boleh melakukan apa algoritma dalam data struktur yang kelihatan seperti ini? 151 00:06:55,960 --> 00:06:59,460 Kita tidak boleh melakukan carian binari, kerana carian binari diperlukan bahawa kita mempunyai 152 00:06:59,460 --> 00:07:00,740 akses rawak. 153 00:07:00,740 --> 00:07:04,500 Kita hanya boleh melompat dari lokasi ke lokasi tanpa perlu mengikuti 154 00:07:04,500 --> 00:07:07,080 ini serbuk roti dalam bentuk semua ini petunjuk. 155 00:07:07,080 --> 00:07:08,300 >> Sekarang, bagaimana kita melaksanakan ini? 156 00:07:08,300 --> 00:07:12,830 Nah, jika kita pergi ke skrin di sini, jika kita boleh dengan cepat reimplement data ini 157 00:07:12,830 --> 00:07:13,440 struktur - 158 00:07:13,440 --> 00:07:15,670 tulisan tangan saya tidak semua yang yang besar di sini, tetapi kita akan cuba. 159 00:07:15,670 --> 00:07:22,030 Struct Jadi typedef, dan apa yang tidak saya mahu memanggil perkara ini di sini? 160 00:07:22,030 --> 00:07:22,960 Nod. 161 00:07:22,960 --> 00:07:24,580 Jadi saya akan mendapatkan kami bermula. 162 00:07:24,580 --> 00:07:27,860 Dan kini, apa yang perlu dalam struktur data untuk itu tunggal 163 00:07:27,860 --> 00:07:28,430 senarai dikaitkan? 164 00:07:28,430 --> 00:07:29,950 Berapa banyak bidang? 165 00:07:29,950 --> 00:07:30,450 >> Jadi kedua-duanya. 166 00:07:30,450 --> 00:07:31,570 Satu adalah cukup mudah. 167 00:07:31,570 --> 00:07:33,050 Jadi int n. 168 00:07:33,050 --> 00:07:35,930 Dan kita boleh memanggil n apa-apa yang kita mahu, tetapi ia perlu int jika kami 169 00:07:35,930 --> 00:07:37,660 melaksanakan senarai dikaitkan untuk Ints. 170 00:07:37,660 --> 00:07:41,920 Dan kini apakah kedua bidang perlu? 171 00:07:41,920 --> 00:07:43,460 Struct nod *. 172 00:07:43,460 --> 00:07:50,570 Jadi, jika saya lakukan struct nod *, dan kemudian saya boleh memanggil ini juga apa yang saya mahu, 173 00:07:50,570 --> 00:07:53,510 tetapi hanya jelas saya akan memanggil ia akan datang, seperti yang kita telah lakukan. 174 00:07:53,510 --> 00:07:55,270 Dan kemudian saya akan menutup pendakap kerinting saya. 175 00:07:55,270 --> 00:08:00,700 >> Dan sekarang, kerana masa lalu, Saya meletakkan nod di sini. 176 00:08:00,700 --> 00:08:03,830 Tetapi jika saya mengisytiharkan ini adalah sebagai nod, kenapa saya bersusah payah begitu 177 00:08:03,830 --> 00:08:07,320 lantung di sini mengisytiharkan struct nod * akan datang, berbanding 178 00:08:07,320 --> 00:08:09,210 hanya nod * seterusnya? 179 00:08:09,210 --> 00:08:09,904 Ya? 180 00:08:09,904 --> 00:08:12,810 >> PENONTON: [didengar]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID MALAN: Tepat sekali. 182 00:08:14,050 --> 00:08:14,530 Tepat sekali. 183 00:08:14,530 --> 00:08:18,320 Kerana C benar-benar akan membawa anda secara literal dan hanya melihat definisi nod 184 00:08:18,320 --> 00:08:21,230 cara turun di sini, anda tidak boleh merujuk kepada di sini. 185 00:08:21,230 --> 00:08:24,760 Jadi kita mempunyai jenis ini terlebih dahulu perisytiharan di sini, yang diakui 186 00:08:24,760 --> 00:08:25,390 lebih lantung. 187 00:08:25,390 --> 00:08:27,810 Struct nod, yang bermakna kita kini boleh mengakses 188 00:08:27,810 --> 00:08:29,760 dalam struktur data. 189 00:08:29,760 --> 00:08:33,370 >> Dan sebagai diketepikan, kerana ini adalah menjadi sedikit lebih subjektif sekarang, 190 00:08:33,370 --> 00:08:36,230 bintang teknikal boleh pergi di sini, ia boleh pergi di sini, ia boleh 191 00:08:36,230 --> 00:08:37,179 walaupun pergi di tengah-tengah. 192 00:08:37,179 --> 00:08:39,890 Kami telah diterima pakai, dalam panduan gaya untuk kursus, konvensyen meletakkan 193 00:08:39,890 --> 00:08:42,299 bintang di sebelah kanan kepada data jenis, yang dalam kes ini, 194 00:08:42,299 --> 00:08:43,460 akan struct nod. 195 00:08:43,460 --> 00:08:46,620 Tetapi sedar dalam banyak buku teks dan rujukan dalam talian, anda mungkin memang 196 00:08:46,620 --> 00:08:48,450 lihat di sebelah yang lain. 197 00:08:48,450 --> 00:08:52,200 Tetapi hanya menyedari bahawa kedua-dua sebenarnya akan bekerja dan anda hanya perlu 198 00:08:52,200 --> 00:08:52,970 konsisten. 199 00:08:52,970 --> 00:08:53,580 >> Baiklah. 200 00:08:53,580 --> 00:08:55,630 Jadi itu adalah pengakuan kita struct nod. 201 00:08:55,630 --> 00:08:59,430 Tetapi kemudian kami mula melakukan lebih perkara-perkara yang canggih. 202 00:08:59,430 --> 00:09:03,410 Sebagai contoh, kami mengambil keputusan untuk memperkenalkan sesuatu seperti jadual hash. 203 00:09:03,410 --> 00:09:08,160 Jadi di sini adalah jadual hash n saiz, diindeks dari 0 di sebelah kiri untuk n 204 00:09:08,160 --> 00:09:09,690 tolak 1 di bahagian bawah kiri. 205 00:09:09,690 --> 00:09:11,640 Ini boleh menjadi hash jadual untuk apa-apa. 206 00:09:11,640 --> 00:09:15,340 Tetapi apa jenis perkara yang kita bercakap kira-kira menggunakan jadual hash untuk? 207 00:09:15,340 --> 00:09:18,370 Menyimpan apa? 208 00:09:18,370 --> 00:09:18,800 >> Nama. 209 00:09:18,800 --> 00:09:20,870 Kita boleh melakukan nama-nama seperti kita lakukan masa lalu. 210 00:09:20,870 --> 00:09:22,200 Dan benar-benar, anda boleh menyimpan apa-apa. 211 00:09:22,200 --> 00:09:24,640 Dan kita akan melihat ini sekali lagi di PHP dan JavaScript. 212 00:09:24,640 --> 00:09:28,550 Satu jadual hash adalah sejenis bagus Swiss Pisau tentera yang membolehkan anda untuk menyimpan 213 00:09:28,550 --> 00:09:33,690 cukup banyak apa sahaja yang anda mahu dalam ia dengan mengaitkan dengan nilai-nilai kunci. 214 00:09:33,690 --> 00:09:34,770 Kunci dengan nilai. 215 00:09:34,770 --> 00:09:37,800 >> Sekarang dalam kes ini mudah, kami kunci hanya nombor. 216 00:09:37,800 --> 00:09:40,380 Kami melaksanakan hash meja sebagai array. 217 00:09:40,380 --> 00:09:43,500 Dan sebagainya kekunci 0, 1, 2, dan sebagainya. 218 00:09:43,500 --> 00:09:47,200 Dan supaya kita, sebagai manusia, memutuskan lepas minggu yang anda tahu apa, jika kita 219 00:09:47,200 --> 00:09:50,410 akan menyimpan nama, mari kita hanya sewenang-wenangnya, tetapi cukup munasabah, 220 00:09:50,410 --> 00:09:54,680 menganggap bahawa Alice, nama A, hanya akan diindeks ke 0. 221 00:09:54,680 --> 00:09:58,030 Dan Bob, nama B, akan diindeks ke 1, dan sebagainya. 222 00:09:58,030 --> 00:10:02,490 Jadi kita mempunyai pemetaan antara input, yang tali, dan hash 223 00:10:02,490 --> 00:10:04,560 lokasi, yang nombor. 224 00:10:04,560 --> 00:10:07,740 >> Jadi proses yang secara amnya dikenali sebagai fungsi hash, dan anda boleh benar-benar 225 00:10:07,740 --> 00:10:09,130 melaksanakannya dalam kod. 226 00:10:09,130 --> 00:10:12,080 Jika saya mahu untuk melaksanakan fungsi hash yang tidak betul-betul apa yang kita 227 00:10:12,080 --> 00:10:17,070 hanya diterangkan dari masa lalu, saya mungkin mengisytiharkan fungsi yang diperlukan, sebagai 228 00:10:17,070 --> 00:10:18,330 input misalnya - 229 00:10:18,330 --> 00:10:22,190 dan mari kita melakukan ini pada ini skrin di sini. 230 00:10:22,190 --> 00:10:26,180 Jika saya mahu melaksanakan hash fungsi, saya mungkin berkata 231 00:10:26,180 --> 00:10:27,410 sesuatu seperti ini. 232 00:10:27,410 --> 00:10:29,030 >> Ia akan kembali int an. 233 00:10:29,030 --> 00:10:33,600 Ia akan dipanggil hash, dan ia akan menerima sebagai hujah yang 234 00:10:33,600 --> 00:10:38,920 tali, atau kita boleh menjadi lebih betul sekarang, dan berkata char *, kami akan memanggilnya s. 235 00:10:38,920 --> 00:10:43,840 Dan kemudian semua fungsi ini telah lakukan, akhirnya, adalah kembali int an. 236 00:10:43,840 --> 00:10:45,990 Sekarang, bagaimana ia yang mungkin tidak begitu jelas. 237 00:10:45,990 --> 00:10:49,510 Saya akan melaksanakan ini tanpa apa-apa membentuk kesilapan memeriksa sekarang. 238 00:10:49,510 --> 00:10:55,740 Saya hanya akan buta berkata, kembali apa yang ada pada s kurungan 0, tolak, 239 00:10:55,740 --> 00:10:58,850 katakan, modal koma bertitik A. 240 00:10:58,850 --> 00:10:59,960 >> Benar-benar rosak. 241 00:10:59,960 --> 00:11:02,620 Ia tidak sempurna kerana satu, bagaimana jika s adalah batal? 242 00:11:02,620 --> 00:11:04,000 Perkara-perkara buruk yang akan berlaku. 243 00:11:04,000 --> 00:11:07,940 Kedua, apa yang jika huruf yang pertama dalam nama bukan huruf besar? 244 00:11:07,940 --> 00:11:09,860 Itu tidak akan berubah dengan baik sama ada. 245 00:11:09,860 --> 00:11:11,970 Ia mungkin menjadi huruf kecil atau tidak surat pada semua. 246 00:11:11,970 --> 00:11:15,520 Jadi benar-benar ruang untuk penambahbaikan di sini, tetapi ini adalah idea asas. 247 00:11:15,520 --> 00:11:19,010 >> Apa yang kita diterangkan minggu lepas secara lisan sebagai hanya satu proses pemetaan Alice untuk 248 00:11:19,010 --> 00:11:23,360 0 dan Bob 1 boleh dinyatakan pastinya lebih formulaically sebagai C 249 00:11:23,360 --> 00:11:24,320 berfungsi di sini. 250 00:11:24,320 --> 00:11:28,630 Dipanggil lagi hash, mengambil tali sebagai input, dan kemudian entah bagaimana melakukan sesuatu 251 00:11:28,630 --> 00:11:31,020 dengan input untuk menghasilkan output. 252 00:11:31,020 --> 00:11:34,130 Tidak seperti Penerangan kotak hitam kami yang kita telah lama dilakukan. 253 00:11:34,130 --> 00:11:36,550 Saya tidak tahu bagaimana ini mungkin bekerja di bawah hood. 254 00:11:36,550 --> 00:11:40,120 >> Untuk set masalah 6, salah satu cabaran adalah untuk anda untuk memutuskan apa yang 255 00:11:40,120 --> 00:11:41,920 fungsi hash anda akan? 256 00:11:41,920 --> 00:11:45,760 Apa yang akan menjadi bahagian dalam yang hitam kotak, dan mungkin, ia akan menjadi 257 00:11:45,760 --> 00:11:50,380 sedikit lebih menarik daripada ini, dan pasti lebih terdedah kepada kesilapan 258 00:11:50,380 --> 00:11:53,180 memeriksa daripada ini tertentu pelaksanaan. 259 00:11:53,180 --> 00:11:54,580 >> Tetapi masalah boleh timbul, bukan? 260 00:11:54,580 --> 00:11:57,760 Jika kita mempunyai struktur data seperti ini satu, apa yang salah satu masalah 261 00:11:57,760 --> 00:12:01,600 anda boleh menghadapi masa ke masa sebagai anda memasukkan lebih banyak nama-nama ke 262 00:12:01,600 --> 00:12:02,880 jadual hash? 263 00:12:02,880 --> 00:12:04,630 Anda mendapat perlanggaran, bukan? 264 00:12:04,630 --> 00:12:07,560 Bagaimana jika anda mempunyai Alice dan Harun, dua orang yang nama mereka berlaku 265 00:12:07,560 --> 00:12:08,190 bermula dengan A? 266 00:12:08,190 --> 00:12:11,660 Yang menimbulkan persoalan, di mana anda meletakkan kedua seperti nama A? 267 00:12:11,660 --> 00:12:15,050 >> Nah, anda mungkin naif hanya meletakkan ia di mana Bob milik, tetapi kemudian Bob 268 00:12:15,050 --> 00:12:17,300 jenis diskru jika anda cuba untuk memasukkan nama beliau akan datang dan 269 00:12:17,300 --> 00:12:18,240 tidak ada ruang untuk beliau. 270 00:12:18,240 --> 00:12:21,400 Jadi, anda mungkin meletakkan Bob di mana Charlie adalah, dan anda boleh bayangkan ini sangat cepat 271 00:12:21,400 --> 00:12:23,020 devolving ke dalam sedikit kacau-bilau. 272 00:12:23,020 --> 00:12:25,600 Sesuatu linear pada akhirnya, di mana anda hanya perlu untuk mencari segala-galanya 273 00:12:25,600 --> 00:12:28,190 mencari Alice atau Bob atau Harun atau Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Jadi, kami mencadangkan, bukan hanya linear menyelesaikan sesuatu kawasan lapang 275 00:12:33,230 --> 00:12:36,450 dan plopping nama-nama di sana, kami mencadangkan pendekatan yang penjaga. 276 00:12:36,450 --> 00:12:41,740 Satu jadual hash masih dilaksanakan dengan pelbagai indeks, tetapi jenis data 277 00:12:41,740 --> 00:12:44,500 mereka kini adalah indeks petunjuk. 278 00:12:44,500 --> 00:12:47,360 Petunjuk untuk apa? 279 00:12:47,360 --> 00:12:48,730 Petunjuk untuk senarai berkaitan. 280 00:12:48,730 --> 00:12:53,330 >> Kerana ingat bahawa senarai yang dikaitkan adalah benar-benar hanya penunjuk kepada nod, dan 281 00:12:53,330 --> 00:12:57,110 nod mempunyai bidang yang akan datang, dan nod yang mempunyai bidang yang akan datang, dan sebagainya. 282 00:12:57,110 --> 00:13:00,690 Jadi, anda kini boleh memikirkan pelbagai ini pada sebelah kiri jadual hash sebagai 283 00:13:00,690 --> 00:13:01,820 membawa kepada senarai yang berkaitan. 284 00:13:01,820 --> 00:13:07,000 Kelebihan yang jika anda mendapat pertembungan antara Alice dan Harun, 285 00:13:07,000 --> 00:13:09,300 apa yang anda lakukan dengan orang kedua seperti itu? 286 00:13:09,300 --> 00:13:14,150 Anda hanya melampirkan kepadanya untuk yang akhir, malah awal 287 00:13:14,150 --> 00:13:15,490 senarai yang berkaitan. 288 00:13:15,490 --> 00:13:17,340 >> Dan sebenarnya, mari kita hanya mi melalui yang hanya kedua. 289 00:13:17,340 --> 00:13:18,640 Di mana akan masuk akal yang paling? 290 00:13:18,640 --> 00:13:22,060 Jika saya memasukkan Alice dan dia berakhir di lokasi pertama, maka saya cuba untuk 291 00:13:22,060 --> 00:13:25,310 memasukkan nama Harun, dan ada jelas perlanggaran, saya perlu meletakkan 292 00:13:25,310 --> 00:13:27,400 beliau pada mulanya senarai dikaitkan? 293 00:13:27,400 --> 00:13:30,944 Itulah di lokasi yang pertama, atau pada akhir? 294 00:13:30,944 --> 00:13:31,440 >> PENONTON: [didengar]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID MALAN: OK. 296 00:13:31,990 --> 00:13:32,490 Saya dengar bermula. 297 00:13:32,490 --> 00:13:33,903 Mengapa pada permulaan? 298 00:13:33,903 --> 00:13:34,750 >> PENONTON: [didengar]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID MALAN: OK. 300 00:13:34,940 --> 00:13:36,520 Ia abjad, supaya baik. 301 00:13:36,520 --> 00:13:37,330 Itulah harta yang baik. 302 00:13:37,330 --> 00:13:39,335 Ia akan menyelamatkan saya sedikit masa yang mungkin. 303 00:13:39,335 --> 00:13:43,290 Ia tidak akan membiarkan saya melakukan carian binari, tetapi saya mungkin sekurang-kurangnya dapat keluar 304 00:13:43,290 --> 00:13:47,340 gelung jika saya sedar, baik, saya cara lepas adalah Harun akan berada di dalam ini 305 00:13:47,340 --> 00:13:48,310 disusun senarai berkaitan. 306 00:13:48,310 --> 00:13:50,360 Saya tidak perlu membuang masa saya mencari sepanjang jalan ke akhir. 307 00:13:50,360 --> 00:13:51,530 Jadi itulah yang munasabah. 308 00:13:51,530 --> 00:13:54,710 Mengapa lagi anda mungkin mahu untuk memasukkan nama berlanggar di 309 00:13:54,710 --> 00:13:56,660 awal senarai? 310 00:13:56,660 --> 00:13:57,397 Apa itu? 311 00:13:57,397 --> 00:13:58,680 >> PENONTON: [didengar]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID MALAN: Ia boleh mengambil masa yang lama untuk sampai ke akhir senarai. 313 00:14:00,820 --> 00:14:02,490 Dan sebenarnya, lagi dan lagi. 314 00:14:02,490 --> 00:14:04,920 Lebih banyak nama-nama yang anda memasukkan bermula dengan A, yang lebih panjang 315 00:14:04,920 --> 00:14:06,280 rantaian akan mendapatkan. 316 00:14:06,280 --> 00:14:07,890 Semakin lama yang dikaitkan senarai akan mendapatkan. 317 00:14:07,890 --> 00:14:09,420 Jadi anda benar-benar hanya membuang masa anda. 318 00:14:09,420 --> 00:14:14,070 Mungkin anda lebih baik mengekalkan masa kemasukan berterusan, besar O 1, 319 00:14:14,070 --> 00:14:18,470 dengan sentiasa meletakkan nama berlanggar di permulaan senarai berkaitan, 320 00:14:18,470 --> 00:14:21,230 dan tidak perlu bimbang kerana banyak tentang sorting. 321 00:14:21,230 --> 00:14:22,600 >> Apakah jawapan yang terbaik? 322 00:14:22,600 --> 00:14:23,320 Ia adalah tidak jelas. 323 00:14:23,320 --> 00:14:26,140 Ia jenis bergantung kepada apa yang pengedaran, apa corak adalah 324 00:14:26,140 --> 00:14:27,850 nama-nama yang anda memasukkan. 325 00:14:27,850 --> 00:14:29,430 Ia tidak semestinya jawapan yang jelas. 326 00:14:29,430 --> 00:14:33,100 Tetapi di sini untuk, sekali lagi, adalah peluang reka bentuk. 327 00:14:33,100 --> 00:14:37,220 >> Jadi kita kemudian melihat perkara ini, yang adalah benar-benar peluang besar lain 328 00:14:37,220 --> 00:14:38,180 untuk p-set 6. 329 00:14:38,180 --> 00:14:41,770 Dan sedar, jika anda tidak mempunyai sudah, Zamyla selam ke dalam kedua-dua, hash 330 00:14:41,770 --> 00:14:43,260 jadual dan cuba, dengan lebih terperinci. 331 00:14:43,260 --> 00:14:45,630 Dan Walkthrough video tertanam dalam p-set spec. 332 00:14:45,630 --> 00:14:46,590 Ini adalah indone a - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. Dan apa yang menarik tentang ini adalah bahawa masa berjalan 334 00:14:51,670 --> 00:14:59,510 mencari nama, seperti Maxwell Kali terakhir, adalah besar O apa? 335 00:14:59,510 --> 00:15:01,040 Apa itu? 336 00:15:01,040 --> 00:15:01,920 >> PENONTON: Bilangan huruf. 337 00:15:01,920 --> 00:15:02,550 >> DAVID MALAN Bilangan huruf. 338 00:15:02,550 --> 00:15:03,210 Saya mendengar dua perkara. 339 00:15:03,210 --> 00:15:04,630 Bilangan surat dan masa yang berterusan. 340 00:15:04,630 --> 00:15:05,540 Jadi mari kita pergi dengan yang pertama. 341 00:15:05,540 --> 00:15:06,410 Bilangan huruf. 342 00:15:06,410 --> 00:15:10,195 Nah, struktur data ini, ingat, adalah seperti pokok, pokok keluarga, setiap 343 00:15:10,195 --> 00:15:12,860 nod yang terdiri daripada tatasusunan. 344 00:15:12,860 --> 00:15:16,300 Dan orang-orang barisan adalah petunjuk untuk nod lain itu, atau lain-lain seperti 345 00:15:16,300 --> 00:15:17,670 array di pokok itu. 346 00:15:17,670 --> 00:15:22,890 >> Jadi, jika kita mahu kemudian menentukan sama ada Maxwell adalah di sini, saya boleh pergi 347 00:15:22,890 --> 00:15:26,890 kepada pelbagai pertama, di bahagian paling atas pokok, akar yang kononnya, atas 348 00:15:26,890 --> 00:15:30,521 indone, dan kemudian ikut penunjuk m, maka penunjuk, maka x, 349 00:15:30,521 --> 00:15:31,710 w, e, l, l. 350 00:15:31,710 --> 00:15:34,910 Dan kemudian apabila saya melihat beberapa simbol khas, ditandakan di sini sebagai segi tiga. 351 00:15:34,910 --> 00:15:38,480 Dalam kod anda akan melihat kami mencadangkan bahawa anda dilaksanakan sebagai bool, hanya berkata ya 352 00:15:38,480 --> 00:15:40,540 atau tidak, perkataan berhenti di sini. 353 00:15:40,540 --> 00:15:45,270 >> Nah, sebaik sahaja kami telah pergi ke M-A-X-W-E-L-L, rasanya tujuh, mungkin 354 00:15:45,270 --> 00:15:48,910 lapan jika kita pergi satu masa lalu itu, lapan langkah-langkah untuk mencari Maxwell. 355 00:15:48,910 --> 00:15:53,050 Atau mari kita memanggilnya K. Tetapi ingat lepas masa, saya berpendapat bahawa jika ada 356 00:15:53,050 --> 00:15:57,540 realistik panjang maksimum pada perkataan, seperti watak-watak 40-beberapa-ganjil, yang 357 00:15:57,540 --> 00:16:00,810 maksimum panjang membayangkan nilai yang berterusan. 358 00:16:00,810 --> 00:16:05,770 Jadi benar-benar, ya, ia adalah O teknikal besar 8 atau 7, atau benar-benar besar O K. Tetapi 359 00:16:05,770 --> 00:16:09,420 jika ada topi terbatas kepada apa yang K boleh, ia adalah tetap. 360 00:16:09,420 --> 00:16:12,080 Dan supaya ia besar O 1 pada akhir hari. 361 00:16:12,080 --> 00:16:13,040 >> Tidak dalam dunia sebenar. 362 00:16:13,040 --> 00:16:15,960 Tidak apabila anda sebenarnya mula menonton jam anda sebagai menjalankan program anda. 363 00:16:15,960 --> 00:16:20,690 Ia benar-benar akan menjadi sedikit lebih perlahan daripada yang benar-benar berterusan 364 00:16:20,690 --> 00:16:21,840 masa dengan satu langkah. 365 00:16:21,840 --> 00:16:25,540 Ia akan menjadi tujuh atau lapan langkah-langkah, tetapi masih yang jauh, jauh lebih baik 366 00:16:25,540 --> 00:16:30,080 daripada algoritma seperti besar O n yang bergantung kepada saiz apa yang di 367 00:16:30,080 --> 00:16:31,220 struktur data. 368 00:16:31,220 --> 00:16:34,970 >> Notis terbalik di sini ialah kita boleh memasukkan satu juta nama lagi ke ini 369 00:16:34,970 --> 00:16:38,170 struktur data, tetapi berapa banyak lagi langkah-langkah yang ia akan membawa kita untuk mencari 370 00:16:38,170 --> 00:16:40,480 Maxwell dalam kes itu? 371 00:16:40,480 --> 00:16:40,780 Tiada. 372 00:16:40,780 --> 00:16:41,820 Dia tidak terjejas. 373 00:16:41,820 --> 00:16:45,480 Dan sehingga kini, saya tidak fikir kita telah melihat contoh struktur data atau 374 00:16:45,480 --> 00:16:48,560 algoritma yang benar-benar terjejas oleh luar 375 00:16:48,560 --> 00:16:50,040 tingkah laku seperti itu. 376 00:16:50,040 --> 00:16:51,160 Tetapi ini tidak boleh menjadi yang menakjubkan. 377 00:16:51,160 --> 00:16:52,900 Ini tidak boleh menjadi satu-satunya penyelesaian untuk p-set 378 00:16:52,900 --> 00:16:53,570 >> Dan ia tidak. 379 00:16:53,570 --> 00:16:55,980 Ini tidak semestinya data struktur yang perlu anda tertarik kepada, 380 00:16:55,980 --> 00:16:58,220 kerana seperti jadual hash, kompromi. 381 00:16:58,220 --> 00:17:00,500 Apakah harga yang anda bayar di sini? 382 00:17:00,500 --> 00:17:00,940 Ingatan. 383 00:17:00,940 --> 00:17:02,890 Maksud saya, ini adalah satu kejam Jumlah ingatan. 384 00:17:02,890 --> 00:17:05,569 Dan anda tidak boleh agak lihat di sini kerana pengarang gambar ini 385 00:17:05,569 --> 00:17:09,420 jelas dipenggal semua array, dan kami tidak melihat banyak A dan 386 00:17:09,420 --> 00:17:12,700 B dan C dan Q dan Y itu dan ini Z dalam tatasusunan. 387 00:17:12,700 --> 00:17:13,630 Tetapi mereka berada di sana. 388 00:17:13,630 --> 00:17:17,660 >> Setiap nod ini adalah pelbagai keseluruhan beberapa 26 atau lebih bait, setiap 389 00:17:17,660 --> 00:17:19,170 yang mewakili surat. 390 00:17:19,170 --> 00:17:22,920 27 dalam kes ini, supaya kita boleh menyokong apostrofi dalam set masalah. 391 00:17:22,920 --> 00:17:27,030 Jadi struktur data ini adalah benar-benar, benar-benar tebal dan lebar. 392 00:17:27,030 --> 00:17:30,880 Dan itu sahaja mungkin berakhir dengan perlahan perkara ke bawah, atau sekurang-kurangnya berharga anda 393 00:17:30,880 --> 00:17:32,240 lebih banyak ruang. 394 00:17:32,240 --> 00:17:34,020 Tetapi sekali lagi, kita boleh membuat perbandingan di sini. 395 00:17:34,020 --> 00:17:39,190 >> Ingat manakala belakang, kita mencapai banyak masa berjalan lebih menarik dalam menyusun 396 00:17:39,190 --> 00:17:42,880 apabila kita menggunakan merge jenis, tetapi harga kita dibayar untuk mencapai n log n untuk merge 397 00:17:42,880 --> 00:17:46,930 apapun yang dikehendaki yang kita belanjakan lebih apa sumber? 398 00:17:46,930 --> 00:17:47,690 Lebih banyak ruang. 399 00:17:47,690 --> 00:17:50,530 Kami memerlukan pelbagai menengah menyalin orang ke dalam, seperti 400 00:17:50,530 --> 00:17:51,620 yang kami lakukan di sini di atas pentas. 401 00:17:51,620 --> 00:17:55,880 Jadi sekali lagi, ada pemenang yang jelas, tetapi hanya reka bentuk subjektif 402 00:17:55,880 --> 00:17:57,710 keputusan dibuat. 403 00:17:57,710 --> 00:17:58,060 >> Baiklah. 404 00:17:58,060 --> 00:17:59,130 Jadi bagaimana tentang perkara ini? 405 00:17:59,130 --> 00:18:02,050 Sesiapa yang mengenali D-Dewan? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Jadi kami bertiga lakukan. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Jadi ini adalah untuk makan Mather ini. 410 00:18:05,070 --> 00:18:09,650 Saya rasa semua dewan makan mempunyai susunan dulang seperti ini. 411 00:18:09,650 --> 00:18:11,950 Dan ini adalah benar-benar wakil sesuatu yang kita telah 412 00:18:11,950 --> 00:18:13,050 jelas dilihat sudah. 413 00:18:13,050 --> 00:18:14,850 Kami menyeru ia benar-benar timbunan. 414 00:18:14,850 --> 00:18:18,970 Dan timbunan, dari segi anda memori komputer, di mana data pergi 415 00:18:18,970 --> 00:18:20,460 manakala fungsi dipanggil. 416 00:18:20,460 --> 00:18:23,410 >> Sebagai contoh, apa jenis perkara yang pergi pada timbunan berkenaan dengan 417 00:18:23,410 --> 00:18:27,420 susun atur memori yang kita telah dibincangkan dalam beberapa minggu yang lalu? 418 00:18:27,420 --> 00:18:28,736 Apa itu? 419 00:18:28,736 --> 00:18:29,670 >> PENONTON: Panggilan ke fungsi. 420 00:18:29,670 --> 00:18:30,260 >> DAVID MALAN: Saya minta maaf. 421 00:18:30,260 --> 00:18:31,210 >> PENONTON: Panggilan ke fungsi. 422 00:18:31,210 --> 00:18:33,590 >> DAVID MALAN: Panggilan ke fungsi, tetapi khusus, apa yang di dalam setiap 423 00:18:33,590 --> 00:18:35,340 mereka bingkai? 424 00:18:35,340 --> 00:18:37,220 Apakah jenis perkara? 425 00:18:37,220 --> 00:18:37,460 Yeah. 426 00:18:37,460 --> 00:18:38,500 Jadi pembolehubah tempatan. 427 00:18:38,500 --> 00:18:43,080 Bila-bila masa kita perlu ada simpanan tempatan, seperti hujah, atau int saya, atau int 428 00:18:43,080 --> 00:18:45,940 suhu, atau apa sahaja tempatan ubah, kita telah 429 00:18:45,940 --> 00:18:47,210 meletakkan bahawa dalam timbunan. 430 00:18:47,210 --> 00:18:49,610 Dan kita panggil ia timbunan kerana itu idea lapisan. 431 00:18:49,610 --> 00:18:52,940 Hanya jenis perlawanan dengan realiti, konsep tersebut. 432 00:18:52,940 --> 00:18:56,650 >> Tetapi ternyata bahawa timbunan juga boleh dilihat sebagai satu struktur data, 433 00:18:56,650 --> 00:19:00,110 alternatif kepada array, alternatif untuk senarai yang berkaitan. 434 00:19:00,110 --> 00:19:02,770 Sesuatu konsep yang lebih menarik yang masih boleh 435 00:19:02,770 --> 00:19:06,030 dilaksanakan dengan menggunakan salah satu daripada orang-orang perkara, tetapi ia adalah jenis yang berbeza 436 00:19:06,030 --> 00:19:09,140 struktur data sokongan, benar-benar, hanya dua operasi. 437 00:19:09,140 --> 00:19:11,000 Tetapi, anda boleh menambah penjaga ciri-ciri daripada ini. 438 00:19:11,000 --> 00:19:12,180 Tetapi ini adalah asas - 439 00:19:12,180 --> 00:19:13,510 menolak dan pop. 440 00:19:13,510 --> 00:19:19,240 >> Dan idea dengan timbunan adalah bahawa jika saya ada di sini, dengan atau tanpa Annenberg 441 00:19:19,240 --> 00:19:22,880 mengetahui, dulang dari sebelah dengan nombor 9 di atasnya. 442 00:19:22,880 --> 00:19:23,870 Jadi hanya int an. 443 00:19:23,870 --> 00:19:26,990 Dan saya mahu untuk menolak ini ke data struktur, yang kini kosong. 444 00:19:26,990 --> 00:19:28,790 Pertimbangkan ini bahagian bawah timbunan. 445 00:19:28,790 --> 00:19:33,150 Saya akan menolak jumlah ini 9 ke timbunan, dan kini ia di sana. 446 00:19:33,150 --> 00:19:36,040 >> Tetapi perkara yang menarik tentang timbunan adalah bahawa jika saya kini mahu untuk menolak 447 00:19:36,040 --> 00:19:40,210 beberapa nilai lain, seperti 17, dan saya menolak ini ke tepi, saya akan melakukan 448 00:19:40,210 --> 00:19:43,290 satu-satunya perkara intuitif, saya hanya akan untuk meletakkan ia tepat di mana kita manusia 449 00:19:43,290 --> 00:19:45,180 akan cenderung untuk meletakkan ia, di atas. 450 00:19:45,180 --> 00:19:48,850 Tetapi apa yang menarik kini ialah, bagaimana saya boleh mendapatkan sekurang-9? 451 00:19:48,850 --> 00:19:50,670 Anda tahu, saya tidak tanpa usaha beberapa. 452 00:19:50,670 --> 00:19:54,070 >> Jadi apa yang menarik tentang timbunan ialah dengan reka bentuk, 453 00:19:54,070 --> 00:19:56,330 ia adalah satu struktur data LIFO. 454 00:19:56,330 --> 00:19:59,680 Cara bodoh untuk menggambarkan terakhir dalam, mula-mula keluar. 455 00:19:59,680 --> 00:20:03,280 Jadi nombor terakhir dalam pada masa ini adalah 17. 456 00:20:03,280 --> 00:20:07,540 Jadi jika saya mahu pop sesuatu dari tepi, ia hanya boleh menjadi 17. 457 00:20:07,540 --> 00:20:11,890 Jadi ada suatu perintah mandatori operasi di sini, di mana item yang lalu 458 00:20:11,890 --> 00:20:14,260 dalam telah menjadi salah satu yang pertama keluar. 459 00:20:14,260 --> 00:20:16,440 Oleh itu singkatan, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Jadi mengapa ini mungkin berguna? 461 00:20:19,160 --> 00:20:22,690 Adakah mereka dalam konteks yang anda lebih mahu struktur data yang seperti ini? 462 00:20:22,690 --> 00:20:24,810 Nah, ia sememangnya menjadi berguna di dalam komputer. 463 00:20:24,810 --> 00:20:29,050 Jadi sistem beroperasi dengan jelas menggunakan ini jenis struktur data untuk susunan. 464 00:20:29,050 --> 00:20:32,800 Kita juga akan melihat idea yang sama apabila ia datang ke laman web. 465 00:20:32,800 --> 00:20:35,890 Jadi minggu ini dan minggu depan dan seterusnya, dan seperti yang anda mula melaksanakan web 466 00:20:35,890 --> 00:20:39,490 halaman dalam bahasa yang dikenali sebagai HTML, anda boleh sebenarnya menggunakan struktur data seperti 467 00:20:39,490 --> 00:20:42,690 ini untuk menentukan jika halaman adalah diformat dengan betul. 468 00:20:42,690 --> 00:20:47,170 Kerana kita akan melihat semua laman web ikuti sejenis hierarki, lekukan sesuatu 469 00:20:47,170 --> 00:20:52,030 yang akan, pada akhir hari, menjadi struktur pokok di bawah hood. 470 00:20:52,030 --> 00:20:53,620 Jadi lebih pada itu dalam hanya sedikit. 471 00:20:53,620 --> 00:20:56,560 >> Tetapi untuk sekarang, mari kita mencadangkan untuk masa, bagaimana kita boleh pergi kira-kira 472 00:20:56,560 --> 00:20:58,830 mewakili apa timbunan itu? 473 00:20:58,830 --> 00:21:03,370 Biar saya mencadangkan supaya kita melaksanakan timbunan dengan kod seperti ini. 474 00:21:03,370 --> 00:21:07,990 Jadi timbunan akan mempunyai di dalamnya dua perkara, array, yang dipanggil dulang, 475 00:21:07,990 --> 00:21:09,510 hanya untuk menjadi selaras dengan demo. 476 00:21:09,510 --> 00:21:12,660 Dan setiap item dalam array yang akan menjadi int jenis. 477 00:21:12,660 --> 00:21:14,740 Dan kapasiti mungkin apa? 478 00:21:14,740 --> 00:21:18,796 Kerana saya tidak bertulis definisi penuh di sini. 479 00:21:18,796 --> 00:21:21,535 >> Ia mungkin maksimum saiz array. 480 00:21:21,535 --> 00:21:25,150 Dan ia mungkin diisytiharkan sebagai tajam menentukan di bahagian atas fail, beberapa 481 00:21:25,150 --> 00:21:28,450 jenis yang berterusan seperti yang dibayangkan oleh permodalan semata-mata. 482 00:21:28,450 --> 00:21:32,250 Jadi tempat keupayaan ditakrifkan sebagai saiz maksimum. 483 00:21:32,250 --> 00:21:35,590 Sementara itu, di dalam struktur data dikenali sebagai timbunan ada akan 484 00:21:35,590 --> 00:21:38,630 menjadi integer hanya dikenali hanya sebagai saiz. 485 00:21:38,630 --> 00:21:43,400 >> Jadi, jika saya adalah untuk mewakili ini sekarang bergambar, mari kita andaikan bahawa ini 486 00:21:43,400 --> 00:21:48,070 kotak hitam mewakili seluruh timbunan saya. 487 00:21:48,070 --> 00:21:50,070 Di dalam ia adalah dua pembolehubah. 488 00:21:50,070 --> 00:21:54,780 Jadi saya akan untuk menarik Yang pertama seperti saiz. 489 00:21:54,780 --> 00:21:57,420 Dan yang kedua saya akan untuk menarik sebagai array. 490 00:21:57,420 --> 00:22:01,060 >> Tetapi hanya untuk menjaga perkara-perkara yang teratur, biasanya saya akan menarik array seperti 491 00:22:01,060 --> 00:22:04,910 ini, tetapi ia jenis nice jika kita sepadan dengan realiti, atau 492 00:22:04,910 --> 00:22:06,230 perlawanan model mental. 493 00:22:06,230 --> 00:22:12,880 Jadi biarlah saya bukannya membuat pelbagai menegak, yang hanya, sekali lagi, 494 00:22:12,880 --> 00:22:13,840 rendition artis. 495 00:22:13,840 --> 00:22:16,610 Adakah benar-benar perkara apa yang ia adalah di bawah hood. 496 00:22:16,610 --> 00:22:20,350 Dan kita akan mengatakan bahawa, secara lalai, kapasiti akan menjadi tiga. 497 00:22:20,350 --> 00:22:23,480 Jadi ini akan menjadi lokasi 0, ini akan menjadi lokasi 1, ini 498 00:22:23,480 --> 00:22:25,740 akan menjadi lokasi 2. 499 00:22:25,740 --> 00:22:29,330 >> Jika saya rasuah dengan bola tekanan, akan orang suka datang dan menjalankan 500 00:22:29,330 --> 00:22:30,870 menaiki di sini untuk seketika? 501 00:22:30,870 --> 00:22:31,960 OK, menyaksikan tangan pertama. 502 00:22:31,960 --> 00:22:33,950 Ayuh up. 503 00:22:33,950 --> 00:22:36,500 Baiklah. 504 00:22:36,500 --> 00:22:38,760 Jadi saya percaya ia adalah Steven. 505 00:22:38,760 --> 00:22:40,035 Ayuh up. 506 00:22:40,035 --> 00:22:40,770 Baiklah. 507 00:22:40,770 --> 00:22:46,760 >> Tetapi sekarang kita andaikan memundurkan untuk permulaan keadaan dunia di mana saya 508 00:22:46,760 --> 00:22:52,180 baru sahaja mengisytiharkan timbunan, dan ia akan menjadi kapasiti tiga. 509 00:22:52,180 --> 00:22:54,470 Tetapi saiz masih belum ditentukan. 510 00:22:54,470 --> 00:22:56,100 Dulang belum ditentukan. 511 00:22:56,100 --> 00:22:57,300 Jadi beberapa soalan pertama. 512 00:22:57,300 --> 00:23:01,310 Dan biarlah saya memberikan mikrofon supaya anda boleh mengambil bahagian secara lebih aktif dalam hal ini. 513 00:23:01,310 --> 00:23:05,190 >> Jadi apa yang ada di dalam saiz pada masa ini dalam masa jika semua yang saya lakukan adalah 514 00:23:05,190 --> 00:23:09,340 diisytiharkan timbunan dengan satu baris kod? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Not much. 516 00:23:10,100 --> 00:23:12,080 >> DAVID MALAN: OK, tidak banyak. 517 00:23:12,080 --> 00:23:14,410 Adakah kita tahu apa yang di dalam saiz, adakah kita tahu apa yang di dalam 518 00:23:14,410 --> 00:23:16,330 array ini di sini? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Hanya kod rawak, bukan? 520 00:23:18,630 --> 00:23:20,220 Just - 521 00:23:20,220 --> 00:23:23,230 >> DAVID MALAN: Ya, saya akan memanggilnya kod, tetapi rawak - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Perkara. 523 00:23:23,820 --> 00:23:28,290 >> DAVID MALAN: Perkara seperti rawak 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bit. 525 00:23:28,870 --> 00:23:29,530 >> DAVID MALAN: Bits, bukan? 526 00:23:29,530 --> 00:23:31,190 Jadi nilai sampah, bukan? 527 00:23:31,190 --> 00:23:33,470 Jadi pilih atur ini 0 dan 1 ini. 528 00:23:33,470 --> 00:23:35,920 Sisa-sisa kelaziman sebelumnya memori ini. 529 00:23:35,920 --> 00:23:38,150 Dan kita tidak benar-benar tahu apa nilai-nilai adalah, jadi kita biasanya menarik mereka 530 00:23:38,150 --> 00:23:38,930 sebagai tanda tanya. 531 00:23:38,930 --> 00:23:41,990 >> Jadi perkara pertama yang kita mungkin akan mahu lakukan di sini - 532 00:23:41,990 --> 00:23:46,630 dan biarlah saya memberikan bidang ini di dalam dari sana nama - dulang. 533 00:23:46,630 --> 00:23:49,540 Apa yang perlu kita mungkin memulakan saiz jika kita mahu 534 00:23:49,540 --> 00:23:51,040 mula menggunakan timbunan ini? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Dulang adalah sub 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID MALAN: Jadi, OK. 537 00:23:53,910 --> 00:23:56,710 Untuk menjadi jelas, kapasiti diisytiharkan tempat lain seperti tiga. 538 00:23:56,710 --> 00:23:58,570 Dan itulah yang saya telah menggunakan memperuntukkan array. 539 00:23:58,570 --> 00:24:03,535 Saiz akan merujuk kepada berapa banyak dulang kini pada timbunan. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID MALAN: Jadi ia perlu sifar. 542 00:24:04,460 --> 00:24:07,760 Oleh itu, pergilah ke hadapan, dan dengan mana-mana jari, menarik sifar dalam saiz. 543 00:24:07,760 --> 00:24:08,440 Baiklah. 544 00:24:08,440 --> 00:24:10,920 Jadi sekarang, apa yang di dalam ini di sini, kami tidak tahu. 545 00:24:10,920 --> 00:24:12,160 Ini adalah benar-benar nilai-nilai sampah sahaja. 546 00:24:12,160 --> 00:24:14,800 Oleh itu, kita boleh menarik tanda tanya, tetapi mari kita menyimpan lembaga bersih kini 547 00:24:14,800 --> 00:24:16,300 kerana ia tidak kira apa yang ada. 548 00:24:16,300 --> 00:24:19,130 Kita tidak perlu untuk memulakan pelbagai apa-apa, kerana jika kita tahu bahawa 549 00:24:19,130 --> 00:24:23,100 saiz timbunan adalah sifar, baik, kami tidak perlu melihat apa-apa dalam 550 00:24:23,100 --> 00:24:25,590 pelbagai ini pula di masa ini. 551 00:24:25,590 --> 00:24:29,970 >> Jadi sekarang menganggap bahawa saya menolak nombor 9 ke dalam tindanan. 552 00:24:29,970 --> 00:24:33,750 Bagaimana kita harus mengemas kini struktur data dalam kotak hitam ini? 553 00:24:33,750 --> 00:24:35,540 Apakah nilai-nilai yang perlu berubah? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Dalam - 555 00:24:36,200 --> 00:24:37,400 saiz? 556 00:24:37,400 --> 00:24:37,650 >> DAVID MALAN: OK. 557 00:24:37,650 --> 00:24:38,770 Saiz harus menjadi apa? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Saiz akan menjadi salah. 559 00:24:39,580 --> 00:24:39,870 >> DAVID MALAN: OK. 560 00:24:39,870 --> 00:24:41,110 Jadi saiz harus menjadi satu. 561 00:24:41,110 --> 00:24:42,540 Jadi, anda boleh melakukan ini dalam beberapa cara. 562 00:24:42,540 --> 00:24:46,920 Biar saya memberi anda, kini anda jari adalah pemadam. 563 00:24:46,920 --> 00:24:47,260 Baiklah. 564 00:24:47,260 --> 00:24:49,960 Maka sekarang jari anda berus. 565 00:24:49,960 --> 00:24:50,330 Baiklah. 566 00:24:50,330 --> 00:24:52,820 Dan kini apa lagi yang telah berubah, jelas, dalam struktur data? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Kami pergi dari bawah ke atas hingga 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID MALAN: 9. 569 00:24:57,760 --> 00:24:58,420 OK, yang baik. 570 00:24:58,420 --> 00:25:01,550 Jadi masih tidak kira apa yang di lokasi satu atau dua kerana mereka 571 00:25:01,550 --> 00:25:04,520 nilai-nilai sampah, tetapi kita tidak perlu bersusah payah mencari di sana kerana saiz adalah 572 00:25:04,520 --> 00:25:07,540 memberitahu kita bahawa hanya Elemen pertama sebenarnya yang sah. 573 00:25:07,540 --> 00:25:10,400 Jadi sekarang saya menolak 17 ke senarai. 574 00:25:10,400 --> 00:25:11,830 Apa yang berlaku kepada gambar ini? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Jadi saiz akan pergi ke dua. 576 00:25:14,720 --> 00:25:15,300 >> DAVID MALAN: OK. 577 00:25:15,300 --> 00:25:16,070 Anda pemadam - 578 00:25:16,070 --> 00:25:16,810 oops. 579 00:25:16,810 --> 00:25:18,026 Anda pemadam. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Pemadam. 581 00:25:18,840 --> 00:25:19,720 >> DAVID MALAN: Anda berus. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID MALAN: OK. 584 00:25:20,920 --> 00:25:21,600 Dan apa lagi? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: Dan kemudian kita - 586 00:25:22,600 --> 00:25:22,915 >> DAVID MALAN: Kami menolak 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Kami berpegang 17 di atas, jadi - 588 00:25:24,760 --> 00:25:25,710 >> DAVID MALAN: OK, baik. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - jatuh ke bawah. 590 00:25:27,040 --> 00:25:27,530 >> DAVID MALAN: Baiklah. 591 00:25:27,530 --> 00:25:27,940 Ia semakin mudah. 592 00:25:27,940 --> 00:25:29,300 Saya tidak akan membantu anda masa ini. 593 00:25:29,300 --> 00:25:30,510 Tolak 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Selesai. 595 00:25:31,720 --> 00:25:34,870 Menjadi pemadam. 596 00:25:34,870 --> 00:25:37,340 Saya menjadi berus. 597 00:25:37,340 --> 00:25:39,340 Dan kemudian saya meletakkan 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID MALAN: 22. 599 00:25:40,100 --> 00:25:40,620 Excellent. 600 00:25:40,620 --> 00:25:41,380 Jadi sekali lagi. 601 00:25:41,380 --> 00:25:44,280 Saya kini akan menolak ke timbunan 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh cuilah. 604 00:25:50,278 --> 00:25:52,520 Anda benar-benar ditangkap saya tidak bersedia. 605 00:25:52,520 --> 00:25:53,703 >> DAVID MALAN: Anda tidak melihat ini datang? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Saya tidak melihat ini akan datang. 607 00:25:55,930 --> 00:25:58,756 Bolehkah kita keupayaan semula awal? 608 00:25:58,756 --> 00:25:59,790 >> DAVID MALAN: Itu satu soalan yang baik. 609 00:25:59,790 --> 00:26:02,360 Jadi kami jenis dicat diri di satu sudut di sini. 610 00:26:02,360 --> 00:26:06,740 Ada benar-benar tidak keluar baik untuk Steven kerana kita telah memperuntukkan pelbagai ini 611 00:26:06,740 --> 00:26:09,130 statik, jadi untuk bercakap, di dalam struktur data. 612 00:26:09,130 --> 00:26:12,170 Dan kita telah dikodkan dasarnya keras ia menjadi saiz tiga. 613 00:26:12,170 --> 00:26:14,170 Jadi kita tidak boleh benar-benar mengagihkan semula ia. 614 00:26:14,170 --> 00:26:20,020 >> Kita boleh jika kita kembali, kami ditakrifkan semula dulang untuk menjadi penunjuk bahawa 615 00:26:20,020 --> 00:26:22,300 kita kemudian gunakan malloc ke memori tangan untuk. 616 00:26:22,300 --> 00:26:25,050 Kerana jika kita mendapat memori daripada timbunan melalui malloc, kita 617 00:26:25,050 --> 00:26:26,430 kemudian boleh membebaskannya. 618 00:26:26,430 --> 00:26:29,630 Tetapi sebelum membebaskan, kita boleh mengagihkan semula sebahagian yang lebih besar memori, 619 00:26:29,630 --> 00:26:31,330 mengemaskini penunjuk, dan sebagainya. 620 00:26:31,330 --> 00:26:33,500 Tetapi untuk sekarang, ini adalah benar-benar yang terbaik yang boleh kita lakukan. 621 00:26:33,500 --> 00:26:36,360 Menolak dan pop yang mungkin akan perlu menunjukkan sedikit kesilapan. 622 00:26:36,360 --> 00:26:40,270 >> Jadi untuk contoh, pelaksanaan kami daripada usaha boleh mengembalikan bool yang 623 00:26:40,270 --> 00:26:42,390 sebelum kembali benar, benar, benar. 624 00:26:42,390 --> 00:26:48,390 Tetapi kali keempat, ia akan mempunyai untuk kembali palsu, misalnya. 625 00:26:48,390 --> 00:26:48,540 Baiklah. 626 00:26:48,540 --> 00:26:49,540 Sangat baik dilakukan. 627 00:26:49,540 --> 00:26:50,060 Tahniah. 628 00:26:50,060 --> 00:26:52,160 Anda telah memperoleh bola tekanan anda hari ini. 629 00:26:52,160 --> 00:26:53,110 >> [Tepuk tangan] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Terima kasih. 631 00:26:54,382 --> 00:26:55,680 >> DAVID MALAN: Terima kasih. 632 00:26:55,680 --> 00:26:59,740 OK, jadi ini seolah-olah tidak banyak satu langkah ke hadapan, bukan? 633 00:26:59,740 --> 00:27:01,410 Kami diterangkan struktur data ini. 634 00:27:01,410 --> 00:27:02,320 Ia adalah menarik, bukan? 635 00:27:02,320 --> 00:27:03,200 Sistem operasi seperti itu. 636 00:27:03,200 --> 00:27:06,360 Rupa-rupanya web boleh menggunakan ini, dan aplikasi lain masih. 637 00:27:06,360 --> 00:27:10,870 Tetapi apa yang had bodoh yang kami kembali ke jenis dua minggu had 638 00:27:10,870 --> 00:27:12,880 di mana kita telah ditetapkan array saiz. 639 00:27:12,880 --> 00:27:15,010 >> Jadi memang ada beberapa cara kita boleh menyelesaikan masalah ini. 640 00:27:15,010 --> 00:27:18,750 Kami dinamik boleh memperuntukkan pelbagai, bukan dengan keras kod kerana saya telah 641 00:27:18,750 --> 00:27:22,600 dilakukan di sini, tetapi sebaliknya-mengisytiharkan semula ini, hanya perlu jelas, sebagai 642 00:27:22,600 --> 00:27:23,830 sesuatu seperti ini. 643 00:27:23,830 --> 00:27:29,040 * Dulang Int, tidak membuat keputusan atas kapasiti yet. 644 00:27:29,040 --> 00:27:35,460 Tetapi apabila saya mengisytiharkan timbunan di tempat lain dalam kod saya, maka saya boleh memanggil malloc, 645 00:27:35,460 --> 00:27:38,250 mendapatkan alamat sebahagian daripada ingatan, dan saya boleh memberikan 646 00:27:38,250 --> 00:27:39,980 alamat untuk dulang. 647 00:27:39,980 --> 00:27:43,340 >> Dan kemudian, kerana ia hanya sebahagian daripada ingatan, saya boleh terus menggunakan persegi 648 00:27:43,340 --> 00:27:45,450 notasi kurungan dalam cara yang biasa. 649 00:27:45,450 --> 00:27:49,020 Kerana sekali lagi, ada jenis ini bersamaan fungsi tatasusunan dan 650 00:27:49,020 --> 00:27:50,820 ketulan memori yang datang kembali dari malloc. 651 00:27:50,820 --> 00:27:53,090 Kita boleh merawat satu dengan yang lain menggunakan aritmetik penunjuk atau 652 00:27:53,090 --> 00:27:54,440 notasi kurungan persegi. 653 00:27:54,440 --> 00:27:55,660 Jadi itulah satu pendekatan. 654 00:27:55,660 --> 00:28:00,120 >> Tetapi bagaimana lagi kita boleh melaksanakan ini struktur data yang sama, yang berpotensi? 655 00:28:00,120 --> 00:28:00,280 Betul? 656 00:28:00,280 --> 00:28:04,530 Saya rasa seperti kita ini diselesaikan masalah seperti minggu lalu. 657 00:28:04,530 --> 00:28:08,860 Apakah penyelesaian kepada masalah ini bahawa Steven berlari ke? 658 00:28:08,860 --> 00:28:10,370 Senarai Jadi dikaitkan, betul. 659 00:28:10,370 --> 00:28:13,410 >> Jika masalah ini ialah bahawa kita lukisan diri kita ke satu sudut dengan memperuntukkan 660 00:28:13,410 --> 00:28:17,580 terlebih dahulu memori yang terlalu kecil yang kita kemudian telah entah bagaimana berurusan dengan, baik, 661 00:28:17,580 --> 00:28:19,880 mengapa tidak hanya mengelakkan bahawa mengeluarkan sama sekali? 662 00:28:19,880 --> 00:28:26,170 Mengapa tidak hanya mengisytiharkan dulang untuk menjadi penunjuk kepada nod, ergo senarai berkaitan, 663 00:28:26,170 --> 00:28:30,740 dan kemudian hanya memperuntukkan nod baru setiap kali Steven diperlukan untuk dimuatkan 664 00:28:30,740 --> 00:28:32,400 nombor ke dalam struktur data. 665 00:28:32,400 --> 00:28:34,200 >> Jadi gambar tersebut akan perlu berubah. 666 00:28:34,200 --> 00:28:38,220 Ia tidak akan menjadi seperti yang bersih dan sebagai semudah hanya pelbagai tiga Ints. 667 00:28:38,220 --> 00:28:42,970 Kini ia akan menjadi penunjuk kepada struct, dan struct yang akan 668 00:28:42,970 --> 00:28:44,830 mempunyai int dan penunjuk akan datang. 669 00:28:44,830 --> 00:28:47,670 Ia akan membawa melalui penunjuk bahawa yang lain struct itu 670 00:28:47,670 --> 00:28:48,600 lain struct itu. 671 00:28:48,600 --> 00:28:50,560 Jadi gambar yang akan benar-benar mendapatkan Messier bit. 672 00:28:50,560 --> 00:28:52,950 Dan kita telah mengikat anak panah semua bersama-sama. 673 00:28:52,950 --> 00:28:55,280 >> Tetapi itu halus, betul, kerana kita telah melihat bagaimana untuk melakukan ini. 674 00:28:55,280 --> 00:28:58,180 Dan apabila anda mendapatkan selesa melaksanakan sesuatu seperti berkaitan 675 00:28:58,180 --> 00:29:01,450 senarai, yang anda perlu lakukan jika anda memilih untuk melaksanakan jadual hash dengan 676 00:29:01,450 --> 00:29:05,120 chaining berasingan untuk p-set 6, anda boleh menggunakannya sebagai blok bangunan, atau 677 00:29:05,120 --> 00:29:08,870 bahan, atau dalam Scratch bercakap, satu prosedur, sesuatu yang anda meletakkan, anda 678 00:29:08,870 --> 00:29:12,560 mencipta sekeping teka-teki anda sendiri bahawa anda boleh menggunakan semula. 679 00:29:12,560 --> 00:29:17,090 Melepas begitu, tetapi penyelesaian yang berpotensi bahawa kita telah benar-benar dilihat sebelum ini. 680 00:29:17,090 --> 00:29:20,560 >> Jadi agak kerap, anda lihat ini setiap atau dua tahun apabila Apple siaran 681 00:29:20,560 --> 00:29:23,060 sesuatu yang baru, dan semua orang gila beratur di luar Apple 682 00:29:23,060 --> 00:29:27,050 menyimpan untuk membeli kecil mereka menaik taraf pada perkakasan. 683 00:29:27,050 --> 00:29:30,420 Saya katakan ini, ia adalah OK, kerana Saya salah seorang daripada orang-orang. 684 00:29:30,420 --> 00:29:35,140 Jadi apa jenis struktur data mungkin mewakili realiti ini? 685 00:29:35,140 --> 00:29:36,980 >> Nah, mari kita memanggil ia satu barisan, satu barisan. 686 00:29:36,980 --> 00:29:40,270 Jadi British akan memanggil ia biasanya beratur anyway, jadi ia nama yang bagus. 687 00:29:40,270 --> 00:29:44,960 Dan kedua-dua operasi yang beratur akan menyokong kami akan memanggil enqueue a 688 00:29:44,960 --> 00:29:48,900 operasi dan operasi dequeue, yang serupa dalam 689 00:29:48,900 --> 00:29:50,120 semangat untuk menolak dan pop. 690 00:29:50,120 --> 00:29:54,060 Ia hanya jenis yang berbeza dalam konvensyen, apa yang kita memanggil ini. 691 00:29:54,060 --> 00:29:57,680 Tetapi untuk enqueue sesuatu yang bermakna untuk menambah atau memasukkan kepada struktur data. 692 00:29:57,680 --> 00:29:59,570 Untuk dequeue bermakna untuk mengeluarkannya. 693 00:29:59,570 --> 00:30:05,170 Tetapi manakala timbunan adalah data yang LIFO struktur, beratur adalah dalam pertama, 694 00:30:05,170 --> 00:30:06,740 pertama daripada struktur data. 695 00:30:06,740 --> 00:30:10,050 >> Jika anda adalah orang yang pertama dalam talian, anda akan menjadi orang yang pertama untuk mendapatkan 696 00:30:10,050 --> 00:30:12,420 keluar dari barisan dan membeli peranti baru anda. 697 00:30:12,420 --> 00:30:18,070 Bayangkan bagaimana perut orang-orang ini akan menjadi jika Apple sebaliknya digunakan timbunan, untuk 698 00:30:18,070 --> 00:30:21,250 contoh, untuk melaksanakan memetik daripada mainan baru anda. 699 00:30:21,250 --> 00:30:24,310 Jadi beratur masuk akal, sudah tentu, dan kita boleh berfikir semua jenis 700 00:30:24,310 --> 00:30:27,480 aplikasi, mungkin, untuk beratur, terutama apabila anda mahu keadilan. 701 00:30:27,480 --> 00:30:30,040 Jadi bagaimana kita boleh melaksanakan ini sebagai struktur data? 702 00:30:30,040 --> 00:30:33,680 >> Well, saya mencadangkan supaya kita mungkin perlu melakukannya dengan cara ini. 703 00:30:33,680 --> 00:30:35,225 Jadi saya akan kini mempunyai nombor. 704 00:30:35,225 --> 00:30:38,190 Oleh itu, kita akan memastikan ia mudah dan tidak semestinya bercakap dari segi dulang. 705 00:30:38,190 --> 00:30:40,220 Hanya nombor yang rakyat mendapat. 706 00:30:40,220 --> 00:30:43,760 Kapasiti akan, sekali lagi, menetapkan jumlah bilangan orang-orang yang boleh di 707 00:30:43,760 --> 00:30:46,900 baris ini, seperti tiga atau apa nilai lain. 708 00:30:46,900 --> 00:30:50,760 >> Tetapi saya mencadangkan bahawa saya perlu untuk mengesan bukan sahaja saiz 709 00:30:50,760 --> 00:30:52,370 beratur, berapa banyak perkara-perkara yang di dalamnya. 710 00:30:52,370 --> 00:30:56,310 Jadi saiz adalah saiz semasa, kapasiti adalah saiz maksimum. 711 00:30:56,310 --> 00:30:58,540 Hanya sekali lagi, tatanama oleh konvensyen. 712 00:30:58,540 --> 00:31:03,680 Kenapa saya perlu int tambahan di dalam satu barisan untuk mengesan yang dalam 713 00:31:03,680 --> 00:31:05,365 hadapan baris? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Kenapa saya perlu untuk berbuat demikian dalam kes ini? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Nah, bagaimana gambar ini akan berubah? 718 00:31:16,190 --> 00:31:19,280 Saya mungkin boleh menggunakan semula yang paling gambar ini. 719 00:31:19,280 --> 00:31:21,480 Biar saya pergi ke hadapan dan memadam apa yang di sini. 720 00:31:21,480 --> 00:31:24,580 Kami akan memberikan ini yang sedikit nama yang berbeza di sini. 721 00:31:24,580 --> 00:31:28,930 Mari kita menghilangkan 17, mari kita menghilangkan daripada 9, mari kita menghilangkan 3. 722 00:31:28,930 --> 00:31:30,410 Dan mari kita menambah satu perkara yang lain. 723 00:31:30,410 --> 00:31:34,710 Saya mencadangkan bahawa saya perlu untuk mengesan hadapan senarai, yang hanya 724 00:31:34,710 --> 00:31:35,570 akan menjadi int an juga. 725 00:31:35,570 --> 00:31:36,550 Dan kita akan pastikan ia mudah. 726 00:31:36,550 --> 00:31:37,740 Tiada senarai dikaitkan buat masa sekarang. 727 00:31:37,740 --> 00:31:40,900 >> Kami akan mengakui bahawa kita akan benjolan sehingga terhadap had ini. 728 00:31:40,900 --> 00:31:43,720 Tetapi apa yang saya mahu melihat berlaku pada masa ini? 729 00:31:43,720 --> 00:31:47,240 Jadi rasa saya pergi ke hadapan dan yang pertama orang yang datang dalam talian, dan 730 00:31:47,240 --> 00:31:48,560 ia adalah nombor 9. 731 00:31:48,560 --> 00:31:49,680 Kami mempunyai bola tekanan. 732 00:31:49,680 --> 00:31:51,330 Bolehkah saya mencuri, berkata, dua atau tiga orang? 733 00:31:51,330 --> 00:31:52,690 Satu, dua, tiga? 734 00:31:52,690 --> 00:31:53,120 Ayuh up. 735 00:31:53,120 --> 00:31:56,022 Hak dari depan, kerana kami akan membuat satu ini cepat. 736 00:31:56,022 --> 00:31:59,415 >> Setiap satu daripada anda kini akan menjadi seorang budak peminat dalam talian di Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Anda tidak akan menerima perkakasan Apple pada akhir walaupun ini. 739 00:32:06,210 --> 00:32:06,500 Baiklah. 740 00:32:06,500 --> 00:32:09,430 Jadi anda nombor 9, anda nombor 17, nombor 22. 741 00:32:09,430 --> 00:32:12,130 Ini adalah nombor sewenang-wenangnya, seperti ID pelajar atau barang kecil. 742 00:32:12,130 --> 00:32:14,550 Dan hanya seketika, mari kita mulakan untuk mula menambah perkara. 743 00:32:14,550 --> 00:32:16,000 Dan saya akan berjalan lembaga di sini kali ini. 744 00:32:16,000 --> 00:32:19,570 >> Jadi dalam kes ini, saya telah dimulakan hadapan supaya menjadi - 745 00:32:19,570 --> 00:32:22,380 Saya sebenarnya tidak benar-benar peduli apa yang depan, kerana saiz adalah sifar. 746 00:32:22,380 --> 00:32:24,480 Jadi ini mungkin juga hanya menjadi tanda tanya. 747 00:32:24,480 --> 00:32:26,170 Ini semua adalah tanda tanya. 748 00:32:26,170 --> 00:32:29,880 Jadi sekarang kita akan mula untuk benar-benar melihat beberapa orang beratur di kedai. 749 00:32:29,880 --> 00:32:33,320 >> Jadi, jika nombor 9, anda yang pertama di sana pada 05:00, teruskan dan beratur, 750 00:32:33,320 --> 00:32:34,210 atau malam sebelum. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Jadi sekarang 9 di sini. 753 00:32:35,940 --> 00:32:37,940 Jadi 9 adalah di hadapan senarai. 754 00:32:37,940 --> 00:32:41,440 Jadi, saya akan pergi ke hadapan dan mengemaskini saiz data ini semasa 755 00:32:41,440 --> 00:32:44,740 struktur tidak 0 lagi, tetapi untuk menjadi 1. 756 00:32:44,740 --> 00:32:47,630 Saya akan meletakkan di 9 hadapan senarai. 757 00:32:47,630 --> 00:32:51,020 Biar saya pergi ke hadapan dan bertukar-tukar skrin supaya kita boleh melihat masa lalu kami di sini. 758 00:32:51,020 --> 00:32:53,220 >> Dan kini apa yang saya mahu untuk meletakkan di hadapan? 759 00:32:53,220 --> 00:32:56,240 Saya akan mengesan bahawa hadapan barisan sekarang 760 00:32:56,240 --> 00:32:58,570 adalah di lokasi 0. 761 00:32:58,570 --> 00:33:00,510 Kerana apa yang akan datang akan berlaku? 762 00:33:00,510 --> 00:33:03,000 Nah, sekarang saya rasa enqueue 17 juga. 763 00:33:03,000 --> 00:33:04,510 Jadi melompat dalam talian di sana. 764 00:33:04,510 --> 00:33:07,060 Dan sekali lagi, jenis pintu kepada kedai akan berada di sini. 765 00:33:07,060 --> 00:33:08,700 Jadi sekarang saya telah menambah 17. 766 00:33:08,700 --> 00:33:10,810 Dan walaupun lelaki ini telah menyekat skrin, itu OK, 767 00:33:10,810 --> 00:33:12,300 kerana kita boleh lihat di sini. 768 00:33:12,300 --> 00:33:12,910 Maaf. 769 00:33:12,910 --> 00:33:13,810 >> PENONTON: Kita boleh bergerak - 770 00:33:13,810 --> 00:33:14,660 >> DAVID MALAN: Tidak, itu OK. 771 00:33:14,660 --> 00:33:16,000 Ia besar di sana. 772 00:33:16,000 --> 00:33:18,580 Jadi 17 kini dalam barisan. 773 00:33:18,580 --> 00:33:21,332 Saya perlu mengemaskinikan yang bidang kini walaupun? 774 00:33:21,332 --> 00:33:23,210 OK, pasti saiz. 775 00:33:23,210 --> 00:33:26,430 Dan bagaimana pula depan? 776 00:33:26,430 --> 00:33:27,040 OK, tidak. 777 00:33:27,040 --> 00:33:30,200 Hadapan tidak berubah, kerana tidak seperti timbunan, kita 778 00:33:30,200 --> 00:33:31,370 mahu mengekalkan keadilan. 779 00:33:31,370 --> 00:33:35,150 Jadi, jika 9 datang pertama, kami mahu 9 akan keluar pertama baris 780 00:33:35,150 --> 00:33:36,420 dan ke dalam kedai. 781 00:33:36,420 --> 00:33:37,220 >> Malah, mari kita lihat itu. 782 00:33:37,220 --> 00:33:42,235 Sebelum kita memasukkan 22, mari kita teruskan dan dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Apa nama anda lagi? 784 00:33:42,970 --> 00:33:43,680 >> PENONTON: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID MALAN: Jake akan untuk dequeued sekarang. 786 00:33:45,440 --> 00:33:48,050 Jadi anda boleh berjalan kaki ke kedai. 787 00:33:48,050 --> 00:33:49,880 Dan berpura-pura bahawa kedai ada di sana. 788 00:33:49,880 --> 00:33:51,970 Jadi sekarang apa yang perlu - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 Apa yang perlu berlaku sekarang? 790 00:33:53,400 --> 00:33:54,490 Keputusan reka bentuk. 791 00:33:54,490 --> 00:33:56,825 Jadi tidak naluri buruk, tetapi - apa nama anda lagi? 792 00:33:56,825 --> 00:33:57,090 >> PENONTON: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID MALAN: David. 794 00:33:57,500 --> 00:33:58,810 Jadi apakah Nabi Daud lakukan? 795 00:33:58,810 --> 00:34:02,590 Dia cuba untuk menyusun daripada menetapkan data struktur dan bergerak dari lokasi beliau 796 00:34:02,590 --> 00:34:04,100 ke bekas lokasi Jake. 797 00:34:04,100 --> 00:34:06,740 Dan yang baik jika kita sanggup untuk menerima bahawa sebagai 798 00:34:06,740 --> 00:34:08,199 detail pelaksanaan. 799 00:34:08,199 --> 00:34:11,100 Tetapi pertama, mari kita mengemas kini data struktur sebelum kita berbuat demikian. 800 00:34:11,100 --> 00:34:14,139 Kerana saya tidak suka idea semua rakyat beralih di dalam bidang ini. 801 00:34:14,139 --> 00:34:17,360 >> Ia tidak masalah besar jika David tidak dengan satu langkah, tetapi sekali lagi, berfikir kembali ke 802 00:34:17,360 --> 00:34:20,360 apabila kita telah mempunyai lapan sukarelawan pada pentas dan kita telah dilakukan seperti memasukkan 803 00:34:20,360 --> 00:34:22,600 jenis, di mana kita terpaksa bermula bergerak semua orang di sekeliling. 804 00:34:22,600 --> 00:34:23,790 Yang mendapat mahal, kan? 805 00:34:23,790 --> 00:34:28,330 Yang membuatkan saya merasa jijik tentang besar O n, besar O n kuasa dua lagi. 806 00:34:28,330 --> 00:34:30,650 Ia tidak berasa seperti hasil yang ideal. 807 00:34:30,650 --> 00:34:32,080 >> Jadi mari kita hanya mengemaskini ini. 808 00:34:32,080 --> 00:34:35,120 Jadi saiz barisan tidak lagi 2. 809 00:34:35,120 --> 00:34:37,090 Ia kini hanya 1. 810 00:34:37,090 --> 00:34:40,360 Tetapi sekarang saya boleh mengemas kini sesuatu Saya tidak mengemas kini sebelum ini, 811 00:34:40,360 --> 00:34:41,130 hadapan senarai. 812 00:34:41,130 --> 00:34:45,420 Saya hanya boleh berkata, adalah lokasi yang 1? 813 00:34:45,420 --> 00:34:49,770 Jadi sekarang kita mempunyai nilai sampah di sini, nilai sampah di sini, dan Daud dalam 814 00:34:49,770 --> 00:34:51,469 tengah-tengah sampah ini. 815 00:34:51,469 --> 00:34:54,980 Tetapi struktur data masih utuh. 816 00:34:54,980 --> 00:34:58,540 >> Dan sebenarnya, saya tidak perlu menukar bekas pemain nombor Jake 817 00:34:58,540 --> 00:35:00,460 9, kerana yang peduli. 818 00:35:00,460 --> 00:35:04,470 Saya mempunyai maklumat yang cukup sekarang dalam saiz yang saya tahu ada satu orang 819 00:35:04,470 --> 00:35:05,030 beratur ini. 820 00:35:05,030 --> 00:35:08,340 Dan saya tahu bahawa orang itu adalah di lokasi 1, tidak 0. 821 00:35:08,340 --> 00:35:09,760 Saya tidak mengira. 822 00:35:09,760 --> 00:35:11,300 Jadi 1 juga. 823 00:35:11,300 --> 00:35:13,410 Jadi struktur data masih OK. 824 00:35:13,410 --> 00:35:14,330 >> Nah, apa yang berlaku seterusnya? 825 00:35:14,330 --> 00:35:15,010 Mari enqueue - 826 00:35:15,010 --> 00:35:15,370 apa nama anda? 827 00:35:15,370 --> 00:35:16,160 >> PENONTON: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID MALAN: Callen. 829 00:35:16,580 --> 00:35:20,770 Mari kita enqueue a Callen, dan 22 kini dalam barisan. 830 00:35:20,770 --> 00:35:22,300 Jadi sekarang apa yang telah berubah di sini? 831 00:35:22,300 --> 00:35:24,380 Hadapan tidak akan berubah, jelas. 832 00:35:24,380 --> 00:35:27,160 Saiz akan berubah menjadi 2 lagi. 833 00:35:27,160 --> 00:35:31,590 Dan 22 berakhir di sini, 9 masih ada, tetapi ia berkesan yang 834 00:35:31,590 --> 00:35:32,600 nilai sampah sekarang. 835 00:35:32,600 --> 00:35:35,910 Ia hanya sisa Jake lalu. 836 00:35:35,910 --> 00:35:39,200 >> Jadi sekarang apa yang berlaku jika Saya dequeue Daud? 837 00:35:39,200 --> 00:35:41,560 Satu operasi lepas, dequeue Daud. 838 00:35:41,560 --> 00:35:46,070 Kita boleh berubah, tetapi saya mencadangkan mari lakukan sebagai kerja sedikit yang mungkin. 839 00:35:46,070 --> 00:35:50,280 Sekarang struktur data saya pergi menyokong saiz dari 2 kepada 1. 840 00:35:50,280 --> 00:35:53,730 Tetapi hadapan barisan kini menjadi 2. 841 00:35:53,730 --> 00:35:56,640 Saya tidak perlu menukar nombor-nombor sahaja lagi, kerana mereka 842 00:35:56,640 --> 00:35:58,230 hanya nilai-nilai sampah. 843 00:35:58,230 --> 00:35:59,720 >> Tetapi sekarang apa yang berlaku? 844 00:35:59,720 --> 00:36:03,280 Katakan saya enqueue diri saya sendiri, 26? 845 00:36:03,280 --> 00:36:05,890 Saya rasa seperti saya tergolong di sini. 846 00:36:05,890 --> 00:36:06,890 Jadi saya sedang enqueued. 847 00:36:06,890 --> 00:36:08,760 Jadi saya jenis tergolong di sini. 848 00:36:08,760 --> 00:36:11,300 Dan walaupun anda tidak berapa menghargai ini visual di atas pentas, 849 00:36:11,300 --> 00:36:15,075 kerana kita mempunyai banyak ruang, saya perlu tidak akan berdiri di sini, mengapa? 850 00:36:15,075 --> 00:36:16,290 >> PENONTON: Anda berada di luar batas. 851 00:36:16,290 --> 00:36:16,370 >> DAVID MALAN: Betul. 852 00:36:16,370 --> 00:36:16,940 Saya keluar dari batas. 853 00:36:16,940 --> 00:36:19,330 Saya telah diindeks di luar batas array ini. 854 00:36:19,330 --> 00:36:23,420 Saya benar-benar seharusnya berada di dalam salah satu tiga lokasi mungkin. 855 00:36:23,420 --> 00:36:25,150 Sekarang, mana yang paling semula jadi untuk pergi? 856 00:36:25,150 --> 00:36:27,760 Saya mencadangkan kita dimanfaatkan seminggu satu helah. 857 00:36:27,760 --> 00:36:30,150 Pengendali mod, peratusan. 858 00:36:30,150 --> 00:36:36,850 Kerana saya teknikal berdiri di lokasi 3, tetapi saya 3 kapasiti mod, 859 00:36:36,850 --> 00:36:40,250 jadi 3, tanda peratus, 3 - 860 00:36:40,250 --> 00:36:40,970 kapasiti adalah 3. 861 00:36:40,970 --> 00:36:41,720 Apa itu? 862 00:36:41,720 --> 00:36:43,700 Apa yang selebihnya apabila anda membahagikan 3 oleh 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Supaya meletakkan saya telah Jake adalah, yang sebenarnya baik. 865 00:36:48,140 --> 00:36:50,370 Jadi sekarang pelaksanaan perkara ini akan 866 00:36:50,370 --> 00:36:51,250 menjadi sedikit sakit kepala. 867 00:36:51,250 --> 00:36:53,740 Ia benar-benar hanya satu baris sakit kepala, kod. 868 00:36:53,740 --> 00:36:56,580 Tetapi sekurang-kurangnya kini terdapat sampah nilai di sini, tetapi terdapat dua 869 00:36:56,580 --> 00:36:57,910 Ints sah di sini. 870 00:36:57,910 --> 00:37:04,160 Dan mendakwa saya bahawa sekarang kita telah dilakukan apa yang perlu kita lakukan selagi 871 00:37:04,160 --> 00:37:08,600 kita mengubah apa yang Jake nilai adalah untuk menjadi 26. 872 00:37:08,600 --> 00:37:12,110 >> Kami kini mempunyai maklumat yang cukup masih untuk mengekalkan integriti 873 00:37:12,110 --> 00:37:13,060 struktur data ini. 874 00:37:13,060 --> 00:37:17,160 Kami masih jenis daripada nasib apabila kita mahu memasukkan empat atau lebih jumlah 875 00:37:17,160 --> 00:37:20,740 unsur-unsur, tetapi saya boleh sekurang-kurangnya membuat cantik kecekapan penggunaan ini berterusan 876 00:37:20,740 --> 00:37:21,740 masa, sebenarnya. 877 00:37:21,740 --> 00:37:27,150 Saya tidak perlu bimbang tentang peralihan semua orang, kerana kecenderungan Daud adalah. 878 00:37:27,150 --> 00:37:30,816 >> Mana-mana soalan mengenai susunan, atau barisan ini? 879 00:37:30,816 --> 00:37:32,184 >> PENONTON: Apakah sebab mengapa anda memerlukan saiz supaya anda tahu 880 00:37:32,184 --> 00:37:34,010 di mana untuk mempunyai seseorang? 881 00:37:34,010 --> 00:37:34,770 >> DAVID MALAN: Tepat sekali. 882 00:37:34,770 --> 00:37:38,230 Saya perlu tahu saiz array kerana saya perlu tahu bagaimana 883 00:37:38,230 --> 00:37:41,940 banyak nilai-nilai yang sah, dan supaya saya boleh mencari di mana untuk meletakkan 884 00:37:41,940 --> 00:37:42,800 orang yang akan datang. 885 00:37:42,800 --> 00:37:43,300 Tepat sekali. 886 00:37:43,300 --> 00:37:44,580 Saiz adalah - 887 00:37:44,580 --> 00:37:46,360 sebenarnya, kami tidak mengemaskini ini. 888 00:37:46,360 --> 00:37:48,380 Saya tambah diri saya 26. 889 00:37:48,380 --> 00:37:51,760 Saiz adalah sekarang, bukan 1, tetapi 2. 890 00:37:51,760 --> 00:37:57,780 Jadi sekarang ini memang membantu saya mencari ketua senarai, yang bukan 0, bukan 891 00:37:57,780 --> 00:37:59,250 1, tetapi 2. 892 00:37:59,250 --> 00:38:01,665 Hadapan senarai memang nombor 22. 893 00:38:01,665 --> 00:38:05,120 Kerana dia datang pertama, jadi dia perlu dibenarkan masuk ke dalam kedai sebelum saya, 894 00:38:05,120 --> 00:38:08,780 walaupun visual saya berdiri dekat dengan kedai. 895 00:38:08,780 --> 00:38:09,220 >> Semua betul? 896 00:38:09,220 --> 00:38:12,410 Satu pusingan tepukan untuk lelaki ini dan kami akan membiarkan mereka keluar dari sana. 897 00:38:12,410 --> 00:38:17,090 >> [Tepuk tangan] 898 00:38:17,090 --> 00:38:18,150 >> DAVID MALAN: Saya boleh membiarkan anda menyimpan dulang. 899 00:38:18,150 --> 00:38:20,760 Kita boleh melihat apa yang berlaku jika anda mahu, tetapi mungkin tidak. 900 00:38:20,760 --> 00:38:21,590 Baiklah. 901 00:38:21,590 --> 00:38:25,380 Jadi apa yang sekarang bagaimana dengan kita? 902 00:38:25,380 --> 00:38:28,900 Baiklah, biar saya mencadangkan bahawa terdapat beberapa struktur data yang lain kita boleh 903 00:38:28,900 --> 00:38:33,810 mula menambah kepada kit alat kita yang akan sebenarnya agak, agak relevan 904 00:38:33,810 --> 00:38:35,270 kita menyelam ke dalam barangan web. 905 00:38:35,270 --> 00:38:38,150 Yang sekali lagi, mempunyai beberapa jenis sambungan pokok-pokok dalam bentuk 906 00:38:38,150 --> 00:38:40,550 sesuatu yang dinamakan DOM, dokumen model objek. 907 00:38:40,550 --> 00:38:42,370 Tetapi kita akan melihat lebih banyak yang tidak lama lagi. 908 00:38:42,370 --> 00:38:46,260 >> Biar saya mencadangkan bahawa kita definitionally memanggil pokok kini apa yang anda mungkin tahu sebagai 909 00:38:46,260 --> 00:38:48,820 lebih daripada pokok keluarga, di mana anda mempunyai beberapa moyang di 910 00:38:48,820 --> 00:38:49,790 akar pokok itu. 911 00:38:49,790 --> 00:38:54,480 A ibu pemimpin keluarga patriarki atau di bahagian paling atas pokok. 912 00:38:54,480 --> 00:38:56,700 Tanpa pasangan mereka, dalam kes ini. 913 00:38:56,700 --> 00:39:00,940 Tetapi sekarang kita mempunyai apa yang kita akan memanggil kanak-kanak, iaitu nod yang menggantung 914 00:39:00,940 --> 00:39:05,480 off kanak-kanak itu kiri atau kanak-kanak yang betul, anak panah seperti yang digambarkan di sini. 915 00:39:05,480 --> 00:39:10,490 >> Dalam erti kata lain, dalam struktur data pokok dalam komputer, pokok telah sifar 916 00:39:10,490 --> 00:39:11,480 atau lebih nod. 917 00:39:11,480 --> 00:39:13,500 Jika ia mempunyai sekurang-kurangnya satu nod, yang dinamakan akar. 918 00:39:13,500 --> 00:39:15,700 Ia adalah perkara-perkara yang visual kami menarik di atas. 919 00:39:15,700 --> 00:39:20,280 Dan simpulan bahawa, seperti mana-mana nod lain, boleh mempunyai sifar, satu, atau dua, atau tiga, 920 00:39:20,280 --> 00:39:23,600 atau bagaimanapun ramai kanak-kanak yang struktur data menyokong. 921 00:39:23,600 --> 00:39:29,150 Dalam kes ini, akar, menyimpan nilai satu, mempunyai dua orang anak, 2 dan 3, 922 00:39:29,150 --> 00:39:33,020 jadi kita biasanya memanggil 2 kiri kanak-kanak dan 3 kanak-kanak yang betul. 923 00:39:33,020 --> 00:39:36,940 >> Dan kemudian apabila kita pergi ke 5, 6, dan 7, 6 akan dipanggil anak tengah. 924 00:39:36,940 --> 00:39:38,940 Jika anda mempunyai empat orang anak, ia mendapat mengelirukan. 925 00:39:38,940 --> 00:39:42,260 Jadi kita berhenti menggunakan jenis yang jalan pintas secara lisan. 926 00:39:42,260 --> 00:39:44,580 Tetapi ia adalah benar-benar hanya pohon keluarga. 927 00:39:44,580 --> 00:39:48,880 Dan daun di sini adalah nod yang diri mereka tidak mempunyai anak. 928 00:39:48,880 --> 00:39:52,540 Mereka menggantung dari bahagian bawah pokok itu. 929 00:39:52,540 --> 00:39:56,940 >> Jadi bagaimana kita boleh melaksanakan pokok yang mempunyai hanya dua kanak-kanak maksima? 930 00:39:56,940 --> 00:39:58,410 Kami akan memanggilnya pokok binari. 931 00:39:58,410 --> 00:40:00,960 Bi lagi bermakna dua, dalam kes, seperti dengan binari. 932 00:40:00,960 --> 00:40:04,830 Dan supaya ia boleh mempunyai sifar, satu, atau dua kanak-kanak maksima. 933 00:40:04,830 --> 00:40:08,650 >> Saya akan mencadangkan supaya kita melaksanakan nod untuk struktur yang dengan int n, 934 00:40:08,650 --> 00:40:11,910 dan kemudian dua petunjuk, satu dipanggil kiri, satu dipanggil betul. 935 00:40:11,910 --> 00:40:14,830 Tetapi orang-orang yang hanya baik konvensyen sewenang-wenangnya. 936 00:40:14,830 --> 00:40:18,170 Dan apa yang baik sekarang, terutamanya jika anda jenis berjuang dengan konsep 937 00:40:18,170 --> 00:40:21,300 rekursi, atau berfikir bahawa ia tidak benar-benar satu penyelesaian kepada apa-apa, 938 00:40:21,300 --> 00:40:23,120 terutamanya jika anda boleh kehabisan memori. 939 00:40:23,120 --> 00:40:26,600 Sekarang kita bercakap tentang data struktur dan algoritma yang membolehkan 940 00:40:26,600 --> 00:40:31,030 kita merentasi dan memanipulasi mereka, ternyata bahawa rekursi datang kembali 941 00:40:31,030 --> 00:40:34,240 yang lebih menarik jika tidak cara yang indah. 942 00:40:34,240 --> 00:40:38,670 >> Jadi ini saya mencadangkan adalah pelaksanaan daripada fungsi Cari. 943 00:40:38,670 --> 00:40:39,870 Memandangkan dua input - 944 00:40:39,870 --> 00:40:41,570 jadi berfikir ini sebagai kotak hitam. 945 00:40:41,570 --> 00:40:46,560 Memandangkan dua input, n, int, dan satu penunjuk kepada pokok, penunjuk kepada 946 00:40:46,560 --> 00:40:50,020 nod, atau benar-benar akar pokok, saya tuntutan bahawa fungsi ini boleh kembali 947 00:40:50,020 --> 00:40:53,530 benar atau palsu, bahawa nilai n berada di dalam pokok ini. 948 00:40:53,530 --> 00:40:55,210 >> Apa yang di dalam kotak hitam ini? 949 00:40:55,210 --> 00:40:57,440 Nah, empat cawangan. 950 00:40:57,440 --> 00:40:58,385 Hanya cek pertama. 951 00:40:58,385 --> 00:41:00,490 Jika pokok adalah batal, hanya kembali palsu. 952 00:41:00,490 --> 00:41:04,580 Jika tiada nod, tidak ada n, tidak ada nombor, hanya kembali palsu. 953 00:41:04,580 --> 00:41:12,330 Jika walaupun, n, nilai yang anda sedang mencari untuk, adalah kurang daripada pokok arrow n, dan 954 00:41:12,330 --> 00:41:15,180 hanya untuk menjadi jelas, apa maknanya apabila Saya menulis pokok dan kemudian anak panah 955 00:41:15,180 --> 00:41:18,150 notasi, n? 956 00:41:18,150 --> 00:41:18,690 Tepat sekali. 957 00:41:18,690 --> 00:41:21,970 Ini bermakna bahawa dereference penunjuk dipanggil pokok. 958 00:41:21,970 --> 00:41:26,750 Pergi ke sana, dan kemudian masuk ke dalam itu nod dan mendapatkan bidang yang dipanggil n. 959 00:41:26,750 --> 00:41:30,810 Dan kemudian membandingkan n sebenar yang dipindahkan ke dalam Search terhadapnya. 960 00:41:30,810 --> 00:41:35,390 >> Jadi, jika n adalah kurang daripada, nilai n nod dalam pokok itu sendiri, baik, 961 00:41:35,390 --> 00:41:36,720 apa maksudnya? 962 00:41:36,720 --> 00:41:40,690 Ini bermakna apa-apa pada pandangan pertama. 963 00:41:40,690 --> 00:41:40,900 Betul? 964 00:41:40,900 --> 00:41:45,560 Sama seperti apabila anda mempunyai pelbagai nilai, anda mungkin ingin memohon binari 965 00:41:45,560 --> 00:41:48,290 mencari sebagai satu bentuk jurang dan menakluk. 966 00:41:48,290 --> 00:41:51,790 Tetapi apa andaian yang kita perlu membuat carian binari untuk bekerja di semua 967 00:41:51,790 --> 00:41:54,510 di dalam buku telefon dan contoh awal? 968 00:41:54,510 --> 00:41:55,530 >> Bagaimana untuk diselesaikan. 969 00:41:55,530 --> 00:41:59,490 Jadi mari kita menghalusi takrif pokok di sini tidak hanya pokok, yang boleh 970 00:41:59,490 --> 00:42:00,880 mempunyai beberapa kanak-kanak. 971 00:42:00,880 --> 00:42:04,700 Bukan sahaja pokok binari, yang boleh mempunyai 0, 1, 2 atau maksima. 972 00:42:04,700 --> 00:42:09,700 Tetapi sebagai pokok carian binari, atau BST, yang hanya satu cara yang mewah untuk mengatakan yang 973 00:42:09,700 --> 00:42:15,430 pokok binari itu bahawa setiap nod yang anak kiri, jika ada, adalah 974 00:42:15,430 --> 00:42:16,830 kurang daripada nod. 975 00:42:16,830 --> 00:42:20,170 Dan kanak-kanak yang betul setiap nod itu, jika ada, adalah lebih besar 976 00:42:20,170 --> 00:42:21,740 daripada nod itu sendiri. 977 00:42:21,740 --> 00:42:25,200 >> Jadi, dalam erti kata lain, jika anda adalah untuk menarik keluar pokok, semua nombor-nombor 978 00:42:25,200 --> 00:42:30,620 seimbang dengan berhati-hati seperti ini supaya jika anda mempunyai 55 sebagai akar, 33 boleh pergi 979 00:42:30,620 --> 00:42:33,090 ke kiri kerana ia kurang daripada 55 tahun. 980 00:42:33,090 --> 00:42:36,430 77 boleh pergi ke kanan kerana ia adalah lebih daripada 55 tahun. 981 00:42:36,430 --> 00:42:40,750 Tetapi sekarang notis, definisi yang sama, ia adalah satu definisi rekursi lisan, 982 00:42:40,750 --> 00:42:42,600 telah memohon 33. 983 00:42:42,600 --> 00:42:47,610 Anak kiri 33 mestilah kurang daripada itu, dan kanak-kanak yang betul 33-an, 44, mesti 984 00:42:47,610 --> 00:42:48,580 lebih besar daripada itu. 985 00:42:48,580 --> 00:42:51,670 >> Jadi ini adalah satu pokok carian binari, dan Saya mencadangkan, dengan menggunakan sedikit 986 00:42:51,670 --> 00:42:53,910 rekursi, kini kita boleh mencari n. 987 00:42:53,910 --> 00:42:59,160 Jadi, jika n adalah kurang daripada n nilai itu nod semasa, saya akan pergi 988 00:42:59,160 --> 00:43:04,090 hadapan dan menyepak bola, jadi untuk bercakap, dan hanya kembali apa sahaja jawapannya adalah 989 00:43:04,090 --> 00:43:08,470 mencari n pada anak kiri pokok itu. 990 00:43:08,470 --> 00:43:11,370 Perhatikan lagi, fungsi ini hanya menjangka bintang nod, yang 991 00:43:11,370 --> 00:43:12,780 penunjuk kepada nod. 992 00:43:12,780 --> 00:43:17,360 Jadi sesungguhnya aku hanya boleh melakukan pokok panah kiri, yang akan membawa 993 00:43:17,360 --> 00:43:18,400 saya ke nod yang lain. 994 00:43:18,400 --> 00:43:19,480 Tetapi apa yang nod itu? 995 00:43:19,480 --> 00:43:22,820 >> Nah, menurut pengisytiharan ini, kiri hanya penunjuk, supaya hanya 996 00:43:22,820 --> 00:43:27,090 bermakna saya berpindah kepada fungsi carian penunjuk yang berbeza, iaitu 997 00:43:27,090 --> 00:43:30,750 satu yang mewakili anak pokok kiri saya. 998 00:43:30,750 --> 00:43:36,040 Jadi dalam kes ini, penunjuk kepada 33, jika ini adalah input sampel kami Sementara itu, jika 999 00:43:36,040 --> 00:43:40,740 n lebih besar daripada n nilai di nod semasa di pokok itu, maka saya 1000 00:43:40,740 --> 00:43:43,370 akan pergi ke hadapan dan menyepak bola di lain-lain arahan dan hanya berkata, saya tidak 1001 00:43:43,370 --> 00:43:47,280 tahu jika ini n nilai adalah di pokok itu, tetapi saya tahu jika ia adalah, ia turun saya 1002 00:43:47,280 --> 00:43:49,090 cawangan yang betul, jadi untuk bercakap. 1003 00:43:49,090 --> 00:43:53,120 Jadi biarlah saya panggilan rekursif mencari, lulus n satu lagi, tetapi lulus dalam 1004 00:43:53,120 --> 00:43:54,580 penunjuk kepada kanak-kanak kanan saya. 1005 00:43:54,580 --> 00:44:00,020 >> Dalam erti kata lain, jika saya kini pada 55 dan saya mencari untuk 99, saya tahu bahawa 99 1006 00:44:00,020 --> 00:44:04,270 adalah lebih besar daripada 55, jadi hanya seperti saya mengoyakkan minggu-minggu buku telefon yang lalu dan kita 1007 00:44:04,270 --> 00:44:07,140 pergi kanan, begitu juga kita akan pergi di sini. 1008 00:44:07,140 --> 00:44:11,960 Dan saya tidak tahu jika ia di sebelah kanan saya kanak-kanak, dan ia tidak, 77 ada, tetapi 1009 00:44:11,960 --> 00:44:13,210 Saya tahu ia adalah ke arah itu. 1010 00:44:13,210 --> 00:44:18,770 Jadi saya menyeru carian pada anak kanan saya, 77, dan membiarkan angka carian dari 1011 00:44:18,770 --> 00:44:24,950 jika terdapat 99 dalam sewenang-wenangnya contoh adalah sebenarnya di sana. 1012 00:44:24,950 --> 00:44:26,900 >> Yang lain, apa yang mana-mana yang terakhir? 1013 00:44:26,900 --> 00:44:28,620 Jika pokok adalah batal adalah satu kes. 1014 00:44:28,620 --> 00:44:31,890 Jika n adalah kurang daripada nod semasa nilai adalah kes yang lain. 1015 00:44:31,890 --> 00:44:35,120 Jika n adalah lebih besar daripada semasa nilai nod ini adalah kes ketiga. 1016 00:44:35,120 --> 00:44:38,250 Apa kes keempat dan terakhir? 1017 00:44:38,250 --> 00:44:39,480 Saya fikir kita berada di luar kes, betul? 1018 00:44:39,480 --> 00:44:44,690 Ia mesti yang n dalam nod semasa yang saya pada. 1019 00:44:44,690 --> 00:44:49,640 >> Jadi, jika saya mencari 55 pada ketika ini dalam cerita, yang cawangan 1020 00:44:49,640 --> 00:44:51,780 pokok akan kembali benar. 1021 00:44:51,780 --> 00:44:55,380 Jadi apa yang menarik di sini ialah kita sebenarnya, tidak seperti minggu lalu, kita jenis 1022 00:44:55,380 --> 00:44:56,740 daripada mempunyai dua kes asas. 1023 00:44:56,740 --> 00:44:58,300 Dan mereka tidak perlu menjadi semua di atas. 1024 00:44:58,300 --> 00:45:01,390 Atas adalah kes asas kerana jika pokok adalah batal, tiada apa-apa yang perlu dilakukan. 1025 00:45:01,390 --> 00:45:03,410 Hanya kembali berkod keras nilai palsu. 1026 00:45:03,410 --> 00:45:07,400 >> Cawangan bawah adalah jenis yang lalai, di mana jika kita telah diperiksa untuk 1027 00:45:07,400 --> 00:45:11,550 null, kami telah diperiksa jika ia harus kiri, tetapi ia tidak sepatutnya, kita kena 1028 00:45:11,550 --> 00:45:14,640 diperiksa jika ia harus betul, tetapi ia tidak perlu, jelas ia telah menjadi 1029 00:45:14,640 --> 00:45:15,870 betul di mana kita berada. 1030 00:45:15,870 --> 00:45:16,780 Itulah kes asas. 1031 00:45:16,780 --> 00:45:19,920 Jadi ada dua kes rekursi adalah diapit di sana di tengah-tengah. 1032 00:45:19,920 --> 00:45:21,630 Tetapi saya boleh telah menulis ini di mana-mana perintah. 1033 00:45:21,630 --> 00:45:24,520 Saya hanya fikir ia jenis berasa semula jadi terlebih dahulu menyemak kesilapan yang mungkin, 1034 00:45:24,520 --> 00:45:28,340 kemudian memeriksa kiri, kemudian memeriksa betul, maka menganggap bahawa anda berada di nod 1035 00:45:28,340 --> 00:45:30,630 anda sebenarnya cari. 1036 00:45:30,630 --> 00:45:36,240 >> Jadi mengapa ini mungkin berguna? 1037 00:45:36,240 --> 00:45:37,910 Jadi ia ternyata - 1038 00:45:37,910 --> 00:45:42,110 dan biarlah saya melompat untuk memujuknya di sini bahawa dalam web. 1039 00:45:42,110 --> 00:45:44,920 Kami akan mula menggunakan bukan bahasa pengaturcaraan pada mulanya, tetapi 1040 00:45:44,920 --> 00:45:46,030 bahasa markup. 1041 00:45:46,030 --> 00:45:48,740 Sebuah bahasa markup yang satu itu serupa dalam semangat kepada pengaturcaraan 1042 00:45:48,740 --> 00:45:51,715 bahasa, tetapi ia tidak memberi anda keupayaan untuk meluahkan diri anda secara logik. 1043 00:45:51,715 --> 00:45:55,070 Ia hanya memberikan anda keupayaan untuk menyatakan diri struktur. 1044 00:45:55,070 --> 00:45:57,960 >> Di manakah anda ingin meletakkan sesuatu pada halaman, laman web ini? 1045 00:45:57,960 --> 00:45:59,200 Warna apa yang anda mahu menjadikan ia? 1046 00:45:59,200 --> 00:46:00,950 Apa saiz font yang anda mahu untuk membuat ia? 1047 00:46:00,950 --> 00:46:02,970 Apa perkataan yang anda sebenarnya mahu di laman web? 1048 00:46:02,970 --> 00:46:04,060 Jadi itu adalah satu bahasa markup. 1049 00:46:04,060 --> 00:46:07,690 Tetapi kita dengan cepat akan memperkenalkan JavaScript, yang merupakan sepenuhnya 1050 00:46:07,690 --> 00:46:08,560 bahasa pengaturcaraan. 1051 00:46:08,560 --> 00:46:12,530 Sangat serupa sintaksis dalam penampilan kepada C, tetapi ia akan mempunyai beberapa 1052 00:46:12,530 --> 00:46:15,200 baik, lebih kuat, lebih ciri-ciri mesra pengguna. 1053 00:46:15,200 --> 00:46:18,050 >> Dan salah satu daripada kekecewaan di titik dalam semester adalah bahawa kita akan 1054 00:46:18,050 --> 00:46:22,065 segera melaksanakan ejaan yang jauh lebih kecil baris kod dengan menggunakan bahasa-bahasa lain 1055 00:46:22,065 --> 00:46:25,580 daripada C sendiri membenarkan, tetapi atas sebab ini kita tidak lama lagi akan faham. 1056 00:46:25,580 --> 00:46:27,750 Ini akan menjadi yang pertama laman web itu. 1057 00:46:27,750 --> 00:46:30,120 Ia akan benar-benar underwhelming, yang pertama yang kita buat. 1058 00:46:30,120 --> 00:46:31,400 Ia hanya akan berkata, hello dunia. 1059 00:46:31,400 --> 00:46:34,010 Tetapi jika anda tidak pernah melihat ia sebelum ini, ini adalah HTML, 1060 00:46:34,010 --> 00:46:35,670 Hiperteks Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Jika anda pergi ke pilihan menu tertentu dalam mana-mana pelayar yang paling, di mana-mana laman web di 1062 00:46:39,310 --> 00:46:43,160 internet, anda boleh melihat HTML bahawa beberapa orang telah menulis kepada 1063 00:46:43,160 --> 00:46:44,400 mewujudkan bahawa laman web. 1064 00:46:44,400 --> 00:46:47,850 Dan ia mungkin tidak kelihatan seperti ringkas atau kemas seperti ini. 1065 00:46:47,850 --> 00:46:51,400 Tetapi ia akan mengikuti corak ini kurungan terbuka dan garis condong dan 1066 00:46:51,400 --> 00:46:53,660 surat dan berpotensi nombor. 1067 00:46:53,660 --> 00:46:56,770 >> Saya fikir saya akan memberikan anda memujuknya apa yang anda akan dapat melakukan 1068 00:46:56,770 --> 00:46:57,950 selepas mengambil CS50. 1069 00:46:57,950 --> 00:47:02,620 Biar saya pergi ke cs.harvard.edu / merompak, Laman Rob kita sendiri Bowden itu. 1070 00:47:02,620 --> 00:47:06,080 Dia menjadikan ini untuk kita. 1071 00:47:06,080 --> 00:47:07,490 Jadi, anda tidak lama lagi akan dapat berbuat demikian. 1072 00:47:07,490 --> 00:47:10,660 Dan juga, apa yang anda dengar pagi ini - 1073 00:47:10,660 --> 00:47:12,480 apa yang anda mendengar pagi ini - 1074 00:47:12,480 --> 00:47:13,780 >> [Hamster DANCE MUSIC] 1075 00:47:13,780 --> 00:47:15,702 >> - Karena dapat membuat ini. 1076 00:47:15,702 --> 00:47:16,790 Yang menanti kita pada hari Rabu. 1077 00:47:16,790 --> 00:47:17,791 Kita akan melihat anda kemudian. 1078 00:47:17,791 --> 00:47:22,950 >> [Hamster DANCE MUSIC] 1079 00:47:22,950 --> 00:47:24,300 DAVID MALAN: Pada CS50 seterusnya - 1080 00:47:24,300 --> 00:47:31,670