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 datang kembali ke CS50. 4 00:00:13,860 --> 00:00:16,190 Ini adalah awal minggu 8. 5 00:00:16,190 --> 00:00:21,320 Dan mengingat bahwa masalah set 5 berakhir dengan sedikit tantangan. 6 00:00:21,320 --> 00:00:25,210 Jadi asumsi Anda pulih semua Anda Fellows pengajaran dan foto CA 7 00:00:25,210 --> 00:00:30,480 dalam file card.raw, Anda berhak sekarang semua orang-orang, dan 8 00:00:30,480 --> 00:00:34,510 salah satu pemenang yang beruntung akan berjalan pulang dengan satu hal ini, gerakan lompatan 9 00:00:34,510 --> 00:00:37,450 perangkat yang dapat Anda gunakan untuk akhir proyek, misalnya. 10 00:00:37,450 --> 00:00:39,860 >> Ini, setiap tahun, menyebabkan sedikit keanehan. 11 00:00:39,860 --> 00:00:43,480 Dan apa yang saya pikir saya akan lakukan adalah berbagi dengan Anda beberapa catatan yang memiliki 12 00:00:43,480 --> 00:00:47,370 pergi bolak-balik atas daftar staf terlambat. 13 00:00:47,370 --> 00:00:51,110 Misalnya, hanya semalam, kutipan tanda kutip, dari salah satu staf 14 00:00:51,110 --> 00:00:55,000 anggota, "Saya hanya memiliki ketukan mahasiswa pintu untuk mengambil foto dengan saya. 15 00:00:55,000 --> 00:00:59,020 Penguntit, Aku berkata kepadamu. "Dimulai cukup deskriptif dan kemudian kami pindah 16 00:00:59,020 --> 00:01:02,830 pada, satu jam atau lebih kemudian, "Aku punya mahasiswa menunggu saya setelah bagian 17 00:01:02,830 --> 00:01:06,080 dan dia memiliki semua nama dan foto pada beberapa lembar kertas. "Baiklah. 18 00:01:06,080 --> 00:01:09,230 Jadi terorganisir, tetapi tidak semua yang belum menyeramkan. 19 00:01:09,230 --> 00:01:12,520 >> Lalu, "Saya berada di luar kota akhir pekan ini, dan ketika aku kembali, ada satu di 20 00:01:12,520 --> 00:01:12,630 saya 21 00:01:12,630 --> 00:01:16,740 kamar tidur. "[Tertawa] 22 00:01:16,740 --> 00:01:20,410 DAVID Malan: kutipan berikutnya dari staf anggota, "seorang siswa datang ke rumah saya di 23 00:01:20,410 --> 00:01:25,330 Somerville at 4:00 pagi ini. "Berikutnya staf, "aku ke hotel saya di San 24 00:01:25,330 --> 00:01:30,016 Francisco dan mahasiswa sedang menunggu saya di lobi dengan tiga DSLR. " 25 00:01:30,016 --> 00:01:31,510 Jenis kamera. 26 00:01:31,510 --> 00:01:34,980 "Aku bahkan tidak pada staf semester ini, tapi mahasiswa masuk ke rumah saya ini 27 00:01:34,980 --> 00:01:40,480 pagi dan mencatat semuanya dengan Google Glass. "Dan kemudian terakhir, 28 00:01:40,480 --> 00:01:43,650 "Setidaknya 12 orang yang penuh semangat menunggu untuk saya ketika aku keluar dari saya 29 00:01:43,650 --> 00:01:44,800 limo, dan kemudian aku 30 00:01:44,800 --> 00:01:46,970 bangun. "Baiklah. 31 00:01:46,970 --> 00:01:57,690 Jadi di antara foto-foto, karena Anda mungkin ingat, sesama ini di sini, siapa Anda 32 00:01:57,690 --> 00:02:01,850 mungkin tahu seperti Milo Banana, yang tinggal dengan Lauren Carvalho, kepala kita 33 00:02:01,850 --> 00:02:02,905 mengajar Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo Milo, datang ke sini anak. 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 Pikiran Anda, dia memakai Google Glass, sehingga kami akan menunjukkan semua ini setelah. 38 00:02:12,230 --> 00:02:16,190 Jadi ini adalah Milo jika Anda ingin mengambil foto dengan dia sesudahnya. 39 00:02:16,190 --> 00:02:18,240 Jika Anda ingin 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 Itu rekaman yang baik. 42 00:02:20,200 --> 00:02:22,556 Nah, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Oh, jangan lakukan itu. 44 00:02:23,941 --> 00:02:29,020 >> [Tertawa] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Jadi kata itu pada apa yang ada di depan, karena seperti yang kita mulai transisi, 47 00:02:34,550 --> 00:02:38,410 minggu ini khusus, dari C dalam lingkungan perintah line untuk PHP dan 48 00:02:38,410 --> 00:02:42,720 JavaScript dan SQL dan HTML dan CSS dalam lingkungan berbasis web, kami akan 49 00:02:42,720 --> 00:02:44,490 melengkapi Anda dengan semua pengetahuan lebih untuk 50 00:02:44,490 --> 00:02:46,010 potensi proyek akhir. 51 00:02:46,010 --> 00:02:49,240 Menjelang itu, tentu saja memiliki tradisi mengadakan seminar yang 52 00:02:49,240 --> 00:02:50,950 berada di topik tangensial untuk kursus. 53 00:02:50,950 --> 00:02:54,330 Sangat banyak terkait dengan program dan pengembangan aplikasi dan sebagainya, tapi 54 00:02:54,330 --> 00:02:57,010 tidak selalu dieksplorasi oleh silabus kursus sendiri. 55 00:02:57,010 --> 00:03:00,250 >> Jadi, jika Anda mungkin tertarik 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 Ada seminar tua di cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 Dan di daftar sejauh ini untuk tahun ini adalah Web Apps yang menakjubkan dengan Ruby on 59 00:03:10,620 --> 00:03:13,580 Rails, yang merupakan alternatif bahasa PHP. 60 00:03:13,580 --> 00:03:14,900 Komputasi Linguistik. 61 00:03:14,900 --> 00:03:18,710 Pengantar IOS, yang merupakan Platform yang digunakan untuk iPhone dan 62 00:03:18,710 --> 00:03:19,850 pengembangan iPad. 63 00:03:19,850 --> 00:03:22,890 JavaScript untuk Web Apps, kita akan membahas itu, tetapi dalam seminar ini, Anda akan pergi 64 00:03:22,890 --> 00:03:24,070 ke lebih rinci. 65 00:03:24,070 --> 00:03:27,390 >> Leap Gerak, jadi kita akan benar-benar memiliki beberapa teman-teman kita dari Leap Gerak, 66 00:03:27,390 --> 00:03:29,160 perusahaan itu sendiri, bergabung dengan kami. 67 00:03:29,160 --> 00:03:31,800 Besok, pada kenyataannya, untuk memberikan tangan-seminar, jika 68 00:03:31,800 --> 00:03:33,320 menarik bagi Anda. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, suatu teknik alternatif untuk menggunakan JavaScript tidak dalam browser, 70 00:03:38,770 --> 00:03:39,970 tetapi pada server. 71 00:03:39,970 --> 00:03:42,110 Node.js, yang sangat banyak dalam vena juga. 72 00:03:42,110 --> 00:03:43,650 Desain Android ramping. 73 00:03:43,650 --> 00:03:46,990 Android menjadi alternatif yang sangat populer untuk iOS dan Windows Phone 74 00:03:46,990 --> 00:03:48,790 dan platform mobile lainnya. 75 00:03:48,790 --> 00:03:51,180 Dan Web Security Aktif Pertahanan. 76 00:03:51,180 --> 00:03:54,590 >> Jadi sebenarnya, jika Anda ingin untuk terlibat dalam hal ini, biarkan aku 77 00:03:54,590 --> 00:03:55,840 membuat catatan ini. 78 00:03:55,840 --> 00:03:57,790 Kami sangat senang untuk mengatakan bahwa teman-teman kita di Leap 79 00:03:57,790 --> 00:03:59,140 Gerak, yang merupakan startup - 80 00:03:59,140 --> 00:04:01,300 perangkat ini benar-benar hanya datang keluar beberapa bulan yang lalu - 81 00:04:01,300 --> 00:04:05,960 telah anggun menyumbangkan 30 perangkat tersebut ke kelas untuk banyak siswa, jika 82 00:04:05,960 --> 00:04:08,670 Anda ingin meminjam perangkat keras menjelang akhir semester dan menggunakannya untuk 83 00:04:08,670 --> 00:04:10,390 proyek akhir yang sebenarnya. 84 00:04:10,390 --> 00:04:11,890 Mereka mendukung beberapa bahasa. 85 00:04:11,890 --> 00:04:16,040 Tidak satupun dari mereka C, tidak satupun dari mereka PHP, sehingga menyadari satu atau lebih dari seminar ini 86 00:04:16,040 --> 00:04:16,899 mungkin terbukti menarik. 87 00:04:16,899 --> 00:04:19,730 Dan mereka semua akan difilmkan di Apabila Anda tidak dapat 88 00:04:19,730 --> 00:04:21,380 untuk menghadiri secara pribadi. 89 00:04:21,380 --> 00:04:25,000 Jadwal diumumkan melalui email saat kami memperkuat kamar. 90 00:04:25,000 --> 00:04:28,460 >> Dan terakhir, jika Anda pergi ke projects.cs.50.net, ini adalah sebuah situs web 91 00:04:28,460 --> 00:04:31,450 kita mempertahankan setiap tahun yang kami mengundang orang-orang dari masyarakat, fakultas, 92 00:04:31,450 --> 00:04:36,420 departemen, staf, dan keduanya di luar CS50 untuk 93 00:04:36,420 --> 00:04:37,730 mengusulkan ide-ide proyek. 94 00:04:37,730 --> 00:04:39,050 Hal yang menarik bagi kelompok-kelompok mahasiswa. 95 00:04:39,050 --> 00:04:40,600 Hal yang menarik bagi departemen. 96 00:04:40,600 --> 00:04:43,990 Jadi jangan mengubah ada jika Anda berjuang dengan ketidakpastian apa yang Anda 97 00:04:43,990 --> 00:04:46,700 sendiri ingin mengatasi. 98 00:04:46,700 --> 00:04:51,760 >> Jadi terakhir kali kami memperkenalkan dibilang struktur data yang lebih kompleks daripada yang kita 99 00:04:51,760 --> 00:04:53,300 terlihat pada minggu terakhir. 100 00:04:53,300 --> 00:04:56,550 Kami telah menggunakan array cantik bahagia sebagai berguna jika 101 00:04:56,550 --> 00:04:58,160 sederhana struktur data. 102 00:04:58,160 --> 00:05:00,570 Kemudian kami memperkenalkan ini, yang tentu saja terkait daftar. 103 00:05:00,570 --> 00:05:05,470 Dan apa yang salah satu motivasi untuk memperkenalkan struktur data? 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 >> AUDIENCE: Ukuran Dinamis. 107 00:05:08,080 --> 00:05:09,040 >> DAVID Malan: Ukuran Dinamis. 108 00:05:09,040 --> 00:05:11,890 Jadi sedangkan dalam array, Anda harus tahu ukurannya di muka ketika 109 00:05:11,890 --> 00:05:12,740 Anda mengalokasikan itu. 110 00:05:12,740 --> 00:05:14,380 Dalam linked list, Anda tidak harus tahu itu. 111 00:05:14,380 --> 00:05:17,610 Anda hanya dapat malloc, atau lebih umum, mengalokasikan tambahan 112 00:05:17,610 --> 00:05:20,720 node, sehingga untuk berbicara, setiap kali Anda ingin memasukkan lebih banyak data. 113 00:05:20,720 --> 00:05:22,670 Dan simpul tidak memiliki makna yang telah ditentukan. 114 00:05:22,670 --> 00:05:25,580 Ini hanya istilah generik yang menggambarkan semacam wadah yang kita 115 00:05:25,580 --> 00:05:29,610 menggunakan struktur data kami untuk menyimpan beberapa item yang menarik, yang dalam hal ini 116 00:05:29,610 --> 00:05:31,750 Kasus kebetulan bilangan bulat. 117 00:05:31,750 --> 00:05:33,160 >> Tapi selalu ada tradeoff. 118 00:05:33,160 --> 00:05:38,070 Jadi kita mendapatkan ukuran dinamis dari data struktur, tapi berapa harga yang kita bayar? 119 00:05:38,070 --> 00:05:40,040 Apa Kelemahan dari daftar terkait? 120 00:05:40,040 --> 00:05:41,006 Ya? 121 00:05:41,006 --> 00:05:41,980 >> AUDIENCE: Membutuhkan lebih banyak memori. 122 00:05:41,980 --> 00:05:44,240 >> DAVID Malan: Hal ini membutuhkan lebih memori, bagaimana sebenarnya? 123 00:05:44,240 --> 00:05:46,440 >> AUDIENCE: [Tak terdengar]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID Malan: Tepat. 125 00:05:47,050 --> 00:05:50,460 Jadi sekarang kita telah mengambil pointer memori tambahan yang kami sebelumnya 126 00:05:50,460 --> 00:05:53,040 tidak perlu, karena keuntungan dari sebuah array, tentu saja, adalah bahwa 127 00:05:53,040 --> 00:05:54,860 semuanya berdekatan, kembali untuk kembali ke belakang, yang 128 00:05:54,860 --> 00:05:56,380 memberi Anda akses acak. 129 00:05:56,380 --> 00:06:00,710 Karena hanya dengan menggunakan braket persegi notasi, atau lebih teknis pointer 130 00:06:00,710 --> 00:06:03,580 aritmatika, tambahan yang sangat sederhana, Anda dapat mengakses 131 00:06:03,580 --> 00:06:05,700 elemen dalam waktu konstan. 132 00:06:05,700 --> 00:06:08,975 Dan pada kenyataannya, itu semacam mengisyaratkan harga lain yang kita membayar dengan 133 00:06:08,975 --> 00:06:09,760 linked list. 134 00:06:09,760 --> 00:06:13,890 >> Apa yang terjadi pada saat menjalankan Cari sesuatu seperti, jika saya ingin 135 00:06:13,890 --> 00:06:17,270 menemukan beberapa nilai dan dalam dari linked list? 136 00:06:17,270 --> 00:06:20,290 Apa waktu 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 itu diurutkan ke? 139 00:06:24,060 --> 00:06:25,440 Bagaimana jika struktur data yang diurutkan? 140 00:06:25,440 --> 00:06:28,640 Aku bisa melakukan lebih baik daripada besar O n untuk mencari? 141 00:06:28,640 --> 00:06:31,700 Tidak, karena dalam kasus terburuk itu mungkin sangat baik akan diurutkan, namun jumlah tersebut 142 00:06:31,700 --> 00:06:32,950 Anda sedang mencari mungkin besar. 143 00:06:32,950 --> 00:06:35,370 Mungkin nomor 100, yang mungkin kebetulan semua 144 00:06:35,370 --> 00:06:36,410 cara di akhir. 145 00:06:36,410 --> 00:06:39,950 Dan karena Anda hanya dapat mengakses linked daftar dalam pelaksanaan ini dengan 146 00:06:39,950 --> 00:06:42,690 cara simpul pertama, Anda masih agak kurang beruntung. 147 00:06:42,690 --> 00:06:47,450 Anda harus melintasi seluruh hal dari awal sampai akhir untuk menemukan 148 00:06:47,450 --> 00:06:49,150 bahwa nilai besar seperti 100. 149 00:06:49,150 --> 00:06:51,350 Atau untuk menentukan apakah itu bahkan tidak ada. 150 00:06:51,350 --> 00:06:55,960 >> Jadi kita tidak bisa melakukan apa algoritma dalam data struktur yang terlihat seperti ini? 151 00:06:55,960 --> 00:06:59,460 Kita tidak dapat melakukan pencarian biner, karena pencarian biner diperlukan bahwa kita memiliki 152 00:06:59,460 --> 00:07:00,740 random access. 153 00:07:00,740 --> 00:07:04,500 Kami hanya bisa melompat dari lokasi ke lokasi tanpa harus mengikuti 154 00:07:04,500 --> 00:07:07,080 ini remah-remah roti dalam bentuk semua petunjuk ini. 155 00:07:07,080 --> 00:07:08,300 >> Sekarang, bagaimana kita menerapkan ini? 156 00:07:08,300 --> 00:07:12,830 Nah, jika kita pergi ke layar di sini, jika kita dapat 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 besar di sini, tapi kami akan mencoba. 159 00:07:15,670 --> 00:07:22,030 Struct typedef Jadi, dan apa yang saya ingin menelepon hal ini di sini? 160 00:07:22,030 --> 00:07:22,960 Node. 161 00:07:22,960 --> 00:07:24,580 Jadi aku akan mendapatkan kita mulai. 162 00:07:24,580 --> 00:07:27,860 Dan sekarang, apa yang perlu dalam struktur data untuk tunggal 163 00:07:27,860 --> 00:07:28,430 linked list? 164 00:07:28,430 --> 00:07:29,950 Berapa banyak bidang? 165 00:07:29,950 --> 00:07:30,450 >> Jadi dua. 166 00:07:30,450 --> 00:07:31,570 Salah satunya 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 bisa menyebut n apapun yang kita inginkan, tetapi harus menjadi int jika kita 169 00:07:35,930 --> 00:07:37,660 menerapkan linked list untuk ints. 170 00:07:37,660 --> 00:07:41,920 Dan sekarang apa yang kedua lapangan harus? 171 00:07:41,920 --> 00:07:43,460 Struct simpul *. 172 00:07:43,460 --> 00:07:50,570 Jadi jika saya lakukan struct simpul *, dan kemudian saya dapat menyebut ini juga apapun yang saya inginkan, 173 00:07:50,570 --> 00:07:53,510 tetapi hanya harus jelas aku akan menelepon di samping, seperti yang telah kita lakukan. 174 00:07:53,510 --> 00:07:55,270 Dan kemudian aku akan menutup kurung kurawal saya. 175 00:07:55,270 --> 00:08:00,700 >> Dan sekarang, seperti terakhir kali, Aku meletakkan simpul di sini. 176 00:08:00,700 --> 00:08:03,830 Tapi kalau aku menyatakan ini sebagai node, kenapa aku repot-repot begitu 177 00:08:03,830 --> 00:08:07,320 verbose sini dalam menyatakan struct simpul * berikutnya, sebagai lawan 178 00:08:07,320 --> 00:08:09,210 hanya simpul * berikutnya? 179 00:08:09,210 --> 00:08:09,904 Ya? 180 00:08:09,904 --> 00:08:12,810 >> AUDIENCE: [Tak terdengar]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID Malan: Tepat. 182 00:08:14,050 --> 00:08:14,530 Tepat. 183 00:08:14,530 --> 00:08:18,320 Karena C benar-benar membawa Anda secara harfiah dan hanya melihat definisi simpul 184 00:08:18,320 --> 00:08:21,230 cara ke sini, Anda tidak bisa lihat itu di sini. 185 00:08:21,230 --> 00:08:24,760 Jadi kita memiliki semacam ini preemptive deklarasi di sini, yang diakui 186 00:08:24,760 --> 00:08:25,390 lebih verbose. 187 00:08:25,390 --> 00:08:27,810 Struct node, yang berarti kita sekarang dapat mengaksesnya 188 00:08:27,810 --> 00:08:29,760 dalam struktur data. 189 00:08:29,760 --> 00:08:33,370 >> Dan sebagai samping, karena ini adalah menjadi sedikit lebih subyektif sekarang, 190 00:08:33,370 --> 00:08:36,230 Bintang secara teknis bisa pergi di sini, itu bisa pergi di sini, dapat 191 00:08:36,230 --> 00:08:37,179 bahkan pergi di tengah. 192 00:08:37,179 --> 00:08:39,890 Kami telah diadopsi, di buku gaya untuk kursus, konvensi menempatkan 193 00:08:39,890 --> 00:08:42,299 bintang tepat di sebelah data jenis, yang dalam hal ini, 194 00:08:42,299 --> 00:08:43,460 akan struct simpul. 195 00:08:43,460 --> 00:08:46,620 Tapi menyadari dalam banyak buku teks dan referensi online, Anda mungkin memang 196 00:08:46,620 --> 00:08:48,450 melihatnya di sisi lain. 197 00:08:48,450 --> 00:08:52,200 Tapi menyadari bahwa kedua akan benar-benar bekerja dan Anda hanya harus 198 00:08:52,200 --> 00:08:52,970 konsisten. 199 00:08:52,970 --> 00:08:53,580 >> Baik. 200 00:08:53,580 --> 00:08:55,630 Jadi itu deklarasi kami struct simpul. 201 00:08:55,630 --> 00:08:59,430 Tapi kemudian kami mulai melakukan lebih hal canggih. 202 00:08:59,430 --> 00:09:03,410 Misalnya, kami memutuskan untuk memperkenalkan sesuatu seperti tabel hash. 203 00:09:03,410 --> 00:09:08,160 Jadi di sini adalah tabel hash berukuran n, diindeks dari 0 di kiri atas ke n 204 00:09:08,160 --> 00:09:09,690 dikurangi 1 di kiri bawah. 205 00:09:09,690 --> 00:09:11,640 Ini bisa menjadi hash meja untuk apa pun. 206 00:09:11,640 --> 00:09:15,340 Tapi apa hal-hal yang kita bicarakan tentang menggunakan tabel 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 bisa melakukan nama seperti kami lakukan terakhir kali. 210 00:09:20,870 --> 00:09:22,200 Dan benar-benar, Anda dapat menyimpan apa-apa. 211 00:09:22,200 --> 00:09:24,640 Dan kita akan melihat ini lagi di PHP dan JavaScript. 212 00:09:24,640 --> 00:09:28,550 Sebuah tabel hash adalah semacam bagus Swiss Army pisau yang memungkinkan Anda untuk menyimpan 213 00:09:28,550 --> 00:09:33,690 cukup banyak apa pun yang Anda inginkan dalam dengan menghubungkan kunci dengan nilai-nilai. 214 00:09:33,690 --> 00:09:34,770 Kunci dengan nilai-nilai. 215 00:09:34,770 --> 00:09:37,800 >> Sekarang dalam kasus sederhana ini, kami kunci hanya angka. 216 00:09:37,800 --> 00:09:40,380 Kami menerapkan hash tabel sebagai array. 217 00:09:40,380 --> 00:09:43,500 Dan kunci adalah 0, 1, 2, dan sebagainya. 218 00:09:43,500 --> 00:09:47,200 Dan kita, sebagai manusia, memutuskan lalu minggu bahwa Anda tahu apa, jika kita 219 00:09:47,200 --> 00:09:50,410 akan menyimpan nama, mari kita sewenang-wenang, tapi cukup cukup, 220 00:09:50,410 --> 00:09:54,680 mengasumsikan bahwa Alice, nama A, hanya akan diindeks ke 0. 221 00:09:54,680 --> 00:09:58,030 Dan Bob, nama B, akan diindeks menjadi 1, dan sebagainya. 222 00:09:58,030 --> 00:10:02,490 Jadi, kami punya pemetaan antara input, yang adalah string, dan hash 223 00:10:02,490 --> 00:10:04,560 lokasi, yang nomor. 224 00:10:04,560 --> 00:10:07,740 >> Jadi proses yang umumnya dikenal sebagai fungsi hash, dan Anda dapat benar-benar 225 00:10:07,740 --> 00:10:09,130 menerapkannya dalam kode. 226 00:10:09,130 --> 00:10:12,080 Jika saya ingin menerapkan fungsi hash yang tidak persis apa yang kita 227 00:10:12,080 --> 00:10:17,070 hanya dijelaskan dari waktu terakhir, aku mungkin mendeklarasikan fungsi yang mengambil, sebagai 228 00:10:17,070 --> 00:10:18,330 masukan misalnya - 229 00:10:18,330 --> 00:10:22,190 dan mari kita lakukan ini tentang hal ini layar di sini. 230 00:10:22,190 --> 00:10:26,180 Jika saya ingin menerapkan hash fungsi, saya mungkin mengatakan 231 00:10:26,180 --> 00:10:27,410 sesuatu seperti ini. 232 00:10:27,410 --> 00:10:29,030 >> Ini akan mengembalikan int. 233 00:10:29,030 --> 00:10:33,600 Ini akan disebut hash, dan itu akan menerima sebagai argumen 234 00:10:33,600 --> 00:10:38,920 tali, atau kita bisa lebih tepat sekarang, dan berkata char *, kita akan menyebutnya s. 235 00:10:38,920 --> 00:10:43,840 Dan kemudian semua fungsi ini harus dilakukan, akhirnya, adalah mengembalikan int. 236 00:10:43,840 --> 00:10:45,990 Sekarang, bagaimana melakukan itu mungkin tidak begitu jelas. 237 00:10:45,990 --> 00:10:49,510 Aku akan menerapkan ini tanpa membentuk memeriksa kesalahan sekarang. 238 00:10:49,510 --> 00:10:55,740 Aku hanya akan mengatakan membabi buta, kembali apa pun yang di s braket 0, dikurangi, 239 00:10:55,740 --> 00:10:58,850 katakanlah, modal koma A. 240 00:10:58,850 --> 00:10:59,960 >> Benar-benar rusak. 241 00:10:59,960 --> 00:11:02,620 Ini tidak sempurna karena satu, bagaimana jika s adalah null? 242 00:11:02,620 --> 00:11:04,000 Hal-hal buruk yang akan terjadi. 243 00:11:04,000 --> 00:11:07,940 Dua, bagaimana jika huruf pertama dalam Nama bukan huruf kapital? 244 00:11:07,940 --> 00:11:09,860 Itu tidak akan mengubah dengan baik baik. 245 00:11:09,860 --> 00:11:11,970 Mungkin huruf kecil atau tidak surat sama sekali. 246 00:11:11,970 --> 00:11:15,520 Jadi benar-benar ruang untuk perbaikan di sini, tapi ini adalah ide dasar. 247 00:11:15,520 --> 00:11:19,010 >> Apa yang kita dijelaskan minggu lalu secara verbal hanya proses pemetaan Alice 248 00:11:19,010 --> 00:11:23,360 0 dan Bob 1 dapat dinyatakan pasti 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 Menelepon lagi hash, mengambil string sebagai masukan, dan kemudian entah bagaimana melakukan sesuatu 251 00:11:28,630 --> 00:11:31,020 dengan masukan untuk menghasilkan output. 252 00:11:31,020 --> 00:11:34,130 Tidak seperti deskripsi kotak hitam kami bahwa kita sudah lama dilakukan. 253 00:11:34,130 --> 00:11:36,550 Saya tidak tahu bagaimana ini mungkin bekerja di bawah tenda. 254 00:11:36,550 --> 00:11:40,120 >> Untuk masalah set 6, salah satu tantangan adalah bagi Anda untuk memutuskan apa 255 00:11:40,120 --> 00:11:41,920 akan fungsi hash Anda? 256 00:11:41,920 --> 00:11:45,760 Apa yang akan menjadi bagian dalam yang berwarna hitam kotak, dan mungkin, itu akan menjadi 257 00:11:45,760 --> 00:11:50,380 sedikit lebih menarik daripada ini, dan pasti lebih rentan terhadap kesalahan 258 00:11:50,380 --> 00:11:53,180 memeriksa dari ini khusus implementasi. 259 00:11:53,180 --> 00:11:54,580 >> Namun masalah dapat muncul, kan? 260 00:11:54,580 --> 00:11:57,760 Jika kita memiliki struktur data seperti ini satu, apa salah satu masalah 261 00:11:57,760 --> 00:12:01,600 Anda bisa lari ke dari waktu ke waktu seperti yang Anda masukkan nama yang lebih dan lebih ke dalam 262 00:12:01,600 --> 00:12:02,880 tabel hash? 263 00:12:02,880 --> 00:12:04,630 Anda mendapatkan tabrakan, kan? 264 00:12:04,630 --> 00:12:07,560 Bagaimana jika Anda memiliki Alice dan Harun, dua orang yang namanya terjadi 265 00:12:07,560 --> 00:12:08,190 untuk memulai dengan A? 266 00:12:08,190 --> 00:12:11,660 Itu menimbulkan pertanyaan, di mana Anda menempatkan kedua seperti nama A? 267 00:12:11,660 --> 00:12:15,050 >> Nah, Anda naif mungkin hanya menaruhnya di mana Bob milik, tapi kemudian Bob 268 00:12:15,050 --> 00:12:17,300 jenis kacau jika Anda mencoba untuk masukkan namanya berikutnya dan 269 00:12:17,300 --> 00:12:18,240 tidak ada ruang baginya. 270 00:12:18,240 --> 00:12:21,400 Jadi Anda mungkin menempatkan Bob mana Charlie, dan Anda bisa bayangkan ini sangat cepat 271 00:12:21,400 --> 00:12:23,020 mengalihkan menjadi sedikit berantakan. 272 00:12:23,020 --> 00:12:25,600 Sesuatu linear pada akhirnya, di mana Anda hanya perlu mencari semuanya 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, bukannya kami mengusulkan, bukan hanya linear probing untuk ruang terbuka 275 00:12:33,230 --> 00:12:36,450 dan plopping nama-nama di sana, kami mengusulkan pendekatan pelamun. 276 00:12:36,450 --> 00:12:41,740 Sebuah tabel hash dilaksanakan masih dengan array indeks, tetapi tipe data 277 00:12:41,740 --> 00:12:44,500 mereka indeks sekarang adalah pointer. 278 00:12:44,500 --> 00:12:47,360 Pointer ke apa? 279 00:12:47,360 --> 00:12:48,730 Pointer ke daftar terhubung. 280 00:12:48,730 --> 00:12:53,330 >> Karena ingat bahwa linked list benar-benar hanya pointer ke node, dan 281 00:12:53,330 --> 00:12:57,110 node memiliki kolom berikutnya, dan simpul tersebut memiliki kolom berikutnya, dan sebagainya. 282 00:12:57,110 --> 00:13:00,690 Jadi sekarang Anda bisa memikirkan array ini pada sisi kiri dari sebuah tabel hash sebagai 283 00:13:00,690 --> 00:13:01,820 mengarah ke linked list. 284 00:13:01,820 --> 00:13:07,000 Keuntungan dari yang jika Anda mendapatkan tabrakan antara Alice dan Harun, 285 00:13:07,000 --> 00:13:09,300 apa yang Anda lakukan dengan kedua orang tersebut? 286 00:13:09,300 --> 00:13:14,150 Anda tinggal memasang dia ke akhir, atau bahkan awal 287 00:13:14,150 --> 00:13:15,490 itu linked list. 288 00:13:15,490 --> 00:13:17,340 >> Dan sebenarnya, mari kita mie melalui yang sesaat. 289 00:13:17,340 --> 00:13:18,640 Dimana akan membuat paling masuk akal? 290 00:13:18,640 --> 00:13:22,060 Jika saya memasukkan Alice dan dia berakhir di lokasi pertama, maka saya mencoba untuk 291 00:13:22,060 --> 00:13:25,310 masukkan nama Harun, dan ada jelas tabrakan, harus saya masukkan 292 00:13:25,310 --> 00:13:27,400 dia di awal dari linked list? 293 00:13:27,400 --> 00:13:30,944 Itu pada saat itu lokasi pertama, atau di akhir? 294 00:13:30,944 --> 00:13:31,440 >> AUDIENCE: [Tak terdengar]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID Malan: OK. 296 00:13:31,990 --> 00:13:32,490 Aku mendengar dimulai. 297 00:13:32,490 --> 00:13:33,903 Mengapa di awal? 298 00:13:33,903 --> 00:13:34,750 >> AUDIENCE: [Tak terdengar]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID Malan: OK. 300 00:13:34,940 --> 00:13:36,520 Ini abjad, jadi itu bagus. 301 00:13:36,520 --> 00:13:37,330 Itu properti baik. 302 00:13:37,330 --> 00:13:39,335 Ini akan menyelamatkan saya beberapa waktu berpotensi. 303 00:13:39,335 --> 00:13:43,290 Ini tidak akan membiarkan saya melakukan pencarian biner, tapi aku mungkin setidaknya dapat untuk keluar 304 00:13:43,290 --> 00:13:47,340 loop jika saya menyadari, well, aku cara masa lalu adalah Aaron akan berada di ini 305 00:13:47,340 --> 00:13:48,310 diurutkan linked list. 306 00:13:48,310 --> 00:13:50,360 Saya tidak perlu membuang waktu saya melihat semua jalan sampai akhir. 307 00:13:50,360 --> 00:13:51,530 Jadi itu wajar. 308 00:13:51,530 --> 00:13:54,710 Mengapa lagi yang mungkin ingin Anda masukkan nama bertabrakan di 309 00:13:54,710 --> 00:13:56,660 awal daftar? 310 00:13:56,660 --> 00:13:57,397 Apa itu? 311 00:13:57,397 --> 00:13:58,680 >> AUDIENCE: [Tak terdengar]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID Malan: Ini bisa memakan waktu yang lama untuk sampai ke akhir daftar. 313 00:14:00,820 --> 00:14:02,490 Dan pada kenyataannya, lagi dan lagi. 314 00:14:02,490 --> 00:14:04,920 Semakin banyak Anda memasukkan nama yang mulai dengan A, semakin lama 315 00:14:04,920 --> 00:14:06,280 rantai akan mendapatkan. 316 00:14:06,280 --> 00:14:07,890 Semakin lama yang terkait Daftar akan mendapatkan. 317 00:14:07,890 --> 00:14:09,420 Jadi Anda benar-benar hanya membuang-buang waktu Anda. 318 00:14:09,420 --> 00:14:14,070 Mungkin Anda lebih baik mempertahankan waktu penyisipan konstan, O besar dari 1, 319 00:14:14,070 --> 00:14:18,470 dengan selalu menempatkan nama bertabrakan di awal linked list, 320 00:14:18,470 --> 00:14:21,230 dan tidak khawatir sebanyak tentang menyortir. 321 00:14:21,230 --> 00:14:22,600 >> Apa jawaban terbaik? 322 00:14:22,600 --> 00:14:23,320 Tidak jelas. 323 00:14:23,320 --> 00:14:26,140 Ini semacam tergantung pada apa yang distribusi adalah, apa pola 324 00:14:26,140 --> 00:14:27,850 nama-nama Anda memasukkan. 325 00:14:27,850 --> 00:14:29,430 Ini tidak selalu jawaban yang jelas. 326 00:14:29,430 --> 00:14:33,100 Tapi di sini, sekali lagi, adalah kesempatan desain. 327 00:14:33,100 --> 00:14:37,220 >> Jadi kita kemudian melihat hal ini, yang benar-benar kesempatan besar lainnya 328 00:14:37,220 --> 00:14:38,180 untuk p-set 6. 329 00:14:38,180 --> 00:14:41,770 Dan menyadari, jika Anda belum melakukannya, Zamyla menyelam ke kedua, hash 330 00:14:41,770 --> 00:14:43,260 tabel dan mencoba, lebih terinci. 331 00:14:43,260 --> 00:14:45,630 Dan walkthrough video tertanam dalam p-set spesifikasi. 332 00:14:45,630 --> 00:14:46,590 Ini adalah trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. Dan apa yang menarik tentang ini adalah bahwa waktu berjalan 334 00:14:51,670 --> 00:14:59,510 untuk mencari nama, seperti Maxwell terakhir kali, adalah O besar dari apa? 335 00:14:59,510 --> 00:15:01,040 Apa itu? 336 00:15:01,040 --> 00:15:01,920 >> AUDIENCE: Jumlah huruf. 337 00:15:01,920 --> 00:15:02,550 >> DAVID Malan: Jumlah huruf. 338 00:15:02,550 --> 00:15:03,210 Aku mendengar dua hal. 339 00:15:03,210 --> 00:15:04,630 Jumlah surat dan waktu yang konstan. 340 00:15:04,630 --> 00:15:05,540 Jadi mari kita pergi dengan yang pertama kali. 341 00:15:05,540 --> 00:15:06,410 Jumlah huruf. 342 00:15:06,410 --> 00:15:10,195 Nah, ini struktur data, ingat, adalah seperti pohon, pohon keluarga, masing-masing 343 00:15:10,195 --> 00:15:12,860 yang node terdiri dari array. 344 00:15:12,860 --> 00:15:16,300 Dan orang-orang array pointer ke node seperti lainnya, atau lainnya seperti 345 00:15:16,300 --> 00:15:17,670 array di pohon. 346 00:15:17,670 --> 00:15:22,890 >> Jadi jika kita ingin kemudian menentukan apakah Maxwell ada di dalam sini, aku bisa pergi 347 00:15:22,890 --> 00:15:26,890 ke array pertama, di bagian paling atas dari pohon, yang disebut akar, atas 348 00:15:26,890 --> 00:15:30,521 dengan trie, kemudian ikuti pointer m, maka pointer, 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 ketika saya melihat beberapa simbol khusus, dilambangkan di sini sebagai segitiga. 351 00:15:34,910 --> 00:15:38,480 Dalam kode Anda akan melihat kami mengusulkan agar Anda diimplementasikan sebagai bool, hanya mengatakan ya 352 00:15:38,480 --> 00:15:40,540 atau tidak, kata berhenti di sini. 353 00:15:40,540 --> 00:15:45,270 >> Nah, setelah kami telah pergi ke M-A-X-W-E-L-L, terasa seperti tujuh, mungkin 354 00:15:45,270 --> 00:15:48,910 delapan jika kita pergi satu melewatinya, delapan langkah-langkah untuk menemukan Maxwell. 355 00:15:48,910 --> 00:15:53,050 Atau sebut saja K. Tapi ingat terakhir waktu, saya berpendapat bahwa jika ada 356 00:15:53,050 --> 00:15:57,540 realistis panjang maksimum pada kata, seperti tokoh-tokoh 40-beberapa-aneh, a 357 00:15:57,540 --> 00:16:00,810 panjang maksimum menyiratkan nilai konstan. 358 00:16:00,810 --> 00:16:05,770 Jadi benar-benar, ya, itu O teknis besar 8 atau 7, atau O benar-benar besar dari K. Tapi 359 00:16:05,770 --> 00:16:09,420 jika ada topi terbatas pada apa yang K bisa, itu adalah konstan. 360 00:16:09,420 --> 00:16:12,080 Dan jadi O besar 1 di akhir hari. 361 00:16:12,080 --> 00:16:13,040 >> Tidak di dunia nyata. 362 00:16:13,040 --> 00:16:15,960 Tidak ketika Anda benar-benar mulai menonton Jam Anda sebagai berjalan program anda. 363 00:16:15,960 --> 00:16:20,690 Ini benar-benar akan menjadi sedikit lebih lambat dari yang benar-benar konstan 364 00:16:20,690 --> 00:16:21,840 waktu dengan satu langkah. 365 00:16:21,840 --> 00:16:25,540 Ini akan menjadi tujuh atau delapan langkah, tapi masih itu jauh, jauh lebih baik 366 00:16:25,540 --> 00:16:30,080 dari sebuah algoritma seperti O besar n yang tergantung pada ukuran apa yang ada di 367 00:16:30,080 --> 00:16:31,220 struktur data. 368 00:16:31,220 --> 00:16:34,970 >> Perhatikan terbalik di sini adalah kita dapat menyisipkan satu juta nama lebih ke ini 369 00:16:34,970 --> 00:16:38,170 struktur data, tapi berapa banyak langkah itu akan membawa kita untuk menemukan 370 00:16:38,170 --> 00:16:40,480 Maxwell dalam kasus itu? 371 00:16:40,480 --> 00:16:40,780 Tidak ada. 372 00:16:40,780 --> 00:16:41,820 Dia tidak terpengaruh. 373 00:16:41,820 --> 00:16:45,480 Dan sampai saat ini, saya tidak berpikir kami telah melihat contoh struktur data atau 374 00:16:45,480 --> 00:16:48,560 algoritma yang benar-benar terpengaruh oleh eksternal 375 00:16:48,560 --> 00:16:50,040 perilaku seperti itu. 376 00:16:50,040 --> 00:16:51,160 Tapi ini tidak bisa menjadi luar biasa. 377 00:16:51,160 --> 00:16:52,900 Ini tidak bisa menjadi satu-satunya solusi untuk p-set 378 00:16:52,900 --> 00:16:53,570 >> Dan itu tidak. 379 00:16:53,570 --> 00:16:55,980 Hal ini belum tentu data struktur Anda harus tertarik ke, 380 00:16:55,980 --> 00:16:58,220 karena seperti tabel hash, tradeoff. 381 00:16:58,220 --> 00:17:00,500 Apa harga yang Anda bayar di sini? 382 00:17:00,500 --> 00:17:00,940 Memori. 383 00:17:00,940 --> 00:17:02,890 Maksudku, ini adalah mengerikan jumlah memori. 384 00:17:02,890 --> 00:17:05,569 Dan Anda tidak bisa melihatnya di sini karena penulis gambar ini 385 00:17:05,569 --> 00:17:09,420 jelas terpotong 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 dan Z dalam array. 387 00:17:12,700 --> 00:17:13,630 Tapi mereka ada. 388 00:17:13,630 --> 00:17:17,660 >> Masing-masing node ini adalah seluruh array dari sekitar 26 atau lebih byte, masing-masing 389 00:17:17,660 --> 00:17:19,170 yang merupakan surat. 390 00:17:19,170 --> 00:17:22,920 27 dalam kasus kami, sehingga kami dapat mendukung apostrof dalam sejumlah masalah. 391 00:17:22,920 --> 00:17:27,030 Jadi ini benar-benar struktur data, benar-benar padat dan lebar. 392 00:17:27,030 --> 00:17:30,880 Dan itu saja mungkin berakhir memperlambat segalanya, atau setidaknya biaya Anda 393 00:17:30,880 --> 00:17:32,240 lebih banyak ruang. 394 00:17:32,240 --> 00:17:34,020 Tapi sekali lagi, kita dapat menarik perbandingan di sini. 395 00:17:34,020 --> 00:17:39,190 >> Ingat beberapa waktu lalu, kita mencapai banyak waktu berjalan lebih menarik dalam memilah 396 00:17:39,190 --> 00:17:42,880 ketika kita menggunakan merge sort, tapi harga kita dibayar untuk mencapai n log n untuk penggabungan 397 00:17:42,880 --> 00:17:46,930 semacam diperlukan bahwa kita menghabiskan lebih apa sumber daya? 398 00:17:46,930 --> 00:17:47,690 Lebih banyak ruang. 399 00:17:47,690 --> 00:17:50,530 Kami membutuhkan array sekunder untuk menyalin orang dalam, seperti 400 00:17:50,530 --> 00:17:51,620 kita lakukan di sini di atas panggung. 401 00:17:51,620 --> 00:17:55,880 Jadi sekali lagi, tidak ada pemenang yang jelas, tapi hanya desain subjektif 402 00:17:55,880 --> 00:17:57,710 keputusan yang harus dibuat. 403 00:17:57,710 --> 00:17:58,060 >> Baik. 404 00:17:58,060 --> 00:17:59,130 Jadi bagaimana ini? 405 00:17:59,130 --> 00:18:02,050 Siapapun mengenali D-Hall? 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. 410 00:18:05,070 --> 00:18:09,650 Saya berani bertaruh semua ruang makan memiliki tumpukan nampan seperti ini. 411 00:18:09,650 --> 00:18:11,950 Dan ini sebenarnya perwakilan dari sesuatu yang kita sudah 412 00:18:11,950 --> 00:18:13,050 jelas terlihat sudah. 413 00:18:13,050 --> 00:18:14,850 Kami menyebutnya harfiah stack. 414 00:18:14,850 --> 00:18:18,970 Dan stack, dalam hal Anda memori komputer, di mana data berjalan 415 00:18:18,970 --> 00:18:20,460 sementara fungsi dipanggil. 416 00:18:20,460 --> 00:18:23,410 >> Misalnya, apa hal-hal pergi pada tumpukan sehubungan dengan 417 00:18:23,410 --> 00:18:27,420 tata letak memori kita bahas di minggu terakhir? 418 00:18:27,420 --> 00:18:28,736 Apa itu? 419 00:18:28,736 --> 00:18:29,670 >> AUDIENCE: Panggilan ke fungsi. 420 00:18:29,670 --> 00:18:30,260 >> DAVID Malan: Maafkan aku. 421 00:18:30,260 --> 00:18:31,210 >> AUDIENCE: Panggilan ke fungsi. 422 00:18:31,210 --> 00:18:33,590 >> DAVID Malan: Panggilan ke fungsi, tetapi khusus, apa yang di dalam masing-masing 423 00:18:33,590 --> 00:18:35,340 frame tersebut? 424 00:18:35,340 --> 00:18:37,220 Apa macam hal? 425 00:18:37,220 --> 00:18:37,460 Ya. 426 00:18:37,460 --> 00:18:38,500 Jadi variabel lokal. 427 00:18:38,500 --> 00:18:43,080 Kapan saja kita membutuhkan beberapa penyimpanan lokal, seperti sebuah argumen, atau int I, atau int 428 00:18:43,080 --> 00:18:45,940 temp, atau apa pun lokal variabel, kita sudah 429 00:18:45,940 --> 00:18:47,210 menempatkan bahwa pada stack. 430 00:18:47,210 --> 00:18:49,610 Dan kami menyebutnya setumpuk karena itu ide layering. 431 00:18:49,610 --> 00:18:52,940 Hanya jenis pertandingan dengan realitas, konsep tersebut. 432 00:18:52,940 --> 00:18:56,650 >> Tapi ternyata bahwa tumpukan juga bisa dilihat sebagai struktur data, 433 00:18:56,650 --> 00:19:00,110 alternatif untuk array, alternatif ke linked list. 434 00:19:00,110 --> 00:19:02,770 Sesuatu konseptual lebih menarik yang masih bisa 435 00:19:02,770 --> 00:19:06,030 diimplementasikan menggunakan salah satu dari mereka hal, tapi itu jenis yang berbeda 436 00:19:06,030 --> 00:19:09,140 struktur data pendukung, benar-benar, hanya dua operasi. 437 00:19:09,140 --> 00:19:11,000 Tapi Anda dapat menambahkan pada pelamun fitur dari ini. 438 00:19:11,000 --> 00:19:12,180 Tetapi ini adalah dasar - 439 00:19:12,180 --> 00:19:13,510 mendorong dan pop. 440 00:19:13,510 --> 00:19:19,240 >> Dan ide dengan tumpukan adalah bahwa jika saya miliki di sini, dengan atau tanpa Annenberg 441 00:19:19,240 --> 00:19:22,880 mengetahui, nampan dari sebelah dengan nomor 9 di atasnya. 442 00:19:22,880 --> 00:19:23,870 Jadi hanya sebuah int. 443 00:19:23,870 --> 00:19:26,990 Dan saya ingin mendorong ini ke data struktur, yang saat ini kosong. 444 00:19:26,990 --> 00:19:28,790 Pertimbangkan ini bagian bawah tumpukan. 445 00:19:28,790 --> 00:19:33,150 Saya akan mendorong nomor ini ke 9 menumpuk, dan sekarang itu ada di sana. 446 00:19:33,150 --> 00:19:36,040 >> Tapi yang menarik tentang tumpukan adalah bahwa jika saya sekarang ingin mendorong 447 00:19:36,040 --> 00:19:40,210 beberapa nilai lainnya, seperti 17, dan saya mendorong ini ke stack, aku akan melakukan 448 00:19:40,210 --> 00:19:43,290 satu-satunya hal yang intuitif, aku hanya akan untuk menempatkan tepat di mana kita manusia 449 00:19:43,290 --> 00:19:45,180 akan cenderung untuk meletakkannya, di atas. 450 00:19:45,180 --> 00:19:48,850 Tapi apa yang menarik sekarang adalah, bagaimana saya mendapatkan jam 9? 451 00:19:48,850 --> 00:19:50,670 Kau tahu, aku tidak tanpa usaha. 452 00:19:50,670 --> 00:19:54,070 >> Jadi apa yang menarik tentang stack adalah bahwa dengan desain, 453 00:19:54,070 --> 00:19:56,330 itu adalah struktur data LIFO. 454 00:19:56,330 --> 00:19:59,680 Cara konyol untuk menggambarkan terakhir, keluar pertama. 455 00:19:59,680 --> 00:20:03,280 Jadi nomor terakhir di saat ini adalah 17. 456 00:20:03,280 --> 00:20:07,540 Jadi jika saya ingin pop sesuatu dari tumpukan, itu hanya bisa 17. 457 00:20:07,540 --> 00:20:11,890 Jadi ada perintah wajib operasi di sini, di mana item terakhir 458 00:20:11,890 --> 00:20:14,260 di harus menjadi yang pertama keluar. 459 00:20:14,260 --> 00:20:16,440 Oleh karena itu singkatan, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Jadi mengapa hal ini menjadi berguna? 461 00:20:19,160 --> 00:20:22,690 Apakah konteks mereka di mana kau lebih menginginkan sebuah struktur data seperti ini? 462 00:20:22,690 --> 00:20:24,810 Yah, itu pasti telah berguna dalam komputer. 463 00:20:24,810 --> 00:20:29,050 Jadi sistem operasi jelas menggunakan ini jenis struktur data untuk tumpukan. 464 00:20:29,050 --> 00:20:32,800 Kita juga akan melihat ide yang sama ketika datang ke halaman web. 465 00:20:32,800 --> 00:20:35,890 Jadi minggu ini dan minggu depan dan seterusnya, dan ketika Anda mulai menerapkan web 466 00:20:35,890 --> 00:20:39,490 halaman dalam bahasa yang disebut HTML, Anda dapat benar-benar menggunakan struktur data seperti 467 00:20:39,490 --> 00:20:42,690 ini untuk menentukan apakah halaman adalah diformat dengan benar. 468 00:20:42,690 --> 00:20:47,170 Karena kita akan melihat semua halaman web mengikuti semacam hirarki, lekukan 469 00:20:47,170 --> 00:20:52,030 yang akan, pada akhir hari, menjadi struktur pohon bawah tenda. 470 00:20:52,030 --> 00:20:53,620 Jadi lebih pada bahwa dalam hanya sedikit. 471 00:20:53,620 --> 00:20:56,560 >> Tapi untuk saat ini, mari kita mengusulkan untuk saat, bagaimana kita bisa pergi tentang 472 00:20:56,560 --> 00:20:58,830 mewakili apa stack? 473 00:20:58,830 --> 00:21:03,370 Mari saya mengusulkan agar kita menerapkan tumpukan dengan kode seperti ini. 474 00:21:03,370 --> 00:21:07,990 Jadi tumpukan akan memiliki di dalamnya dua hal, sebuah array, yang disebut nampan, 475 00:21:07,990 --> 00:21:09,510 hanya untuk konsisten dengan demo. 476 00:21:09,510 --> 00:21:12,660 Dan masing-masing item dalam array yang akan menjadi tipe int. 477 00:21:12,660 --> 00:21:14,740 Dan kapasitas diduga apa? 478 00:21:14,740 --> 00:21:18,796 Karena saya sudah tidak menulis Definisi lengkap di sini. 479 00:21:18,796 --> 00:21:21,535 >> Ini mungkin maksimal ukuran array. 480 00:21:21,535 --> 00:21:25,150 Dan itu mungkin dinyatakan sebagai tajam mendefinisikan di bagian atas file, beberapa 481 00:21:25,150 --> 00:21:28,450 jenis konstan seperti yang tersirat oleh kapitalisasi belaka. 482 00:21:28,450 --> 00:21:32,250 Jadi suatu kapasitas didefinisikan sebagai kemungkinan ukuran maksimum. 483 00:21:32,250 --> 00:21:35,590 Sementara itu, dalam struktur data dikenal sebagai tumpukan akan ada 484 00:21:35,590 --> 00:21:38,630 menjadi integer hanya dikenal hanya sebagai ukuran. 485 00:21:38,630 --> 00:21:43,400 >> Jadi jika saya untuk mewakili sekarang pictorially, mari kita anggap bahwa ini 486 00:21:43,400 --> 00:21:48,070 Seluruh kotak hitam menunjukkan tumpukan saya. 487 00:21:48,070 --> 00:21:50,070 Di dalamnya adalah dua variabel. 488 00:21:50,070 --> 00:21:54,780 Jadi aku akan menggambar pertama sebagai ukuran. 489 00:21:54,780 --> 00:21:57,420 Dan yang kedua aku akan menggambar sebagai array. 490 00:21:57,420 --> 00:22:01,060 >> Tapi hanya untuk menjaga hal-hal yang teratur, biasanya aku akan menggambar sebuah array seperti 491 00:22:01,060 --> 00:22:04,910 ini, tapi itu jenis yang baik jika kita sesuai dengan kenyataan, atau 492 00:22:04,910 --> 00:22:06,230 cocok model mental. 493 00:22:06,230 --> 00:22:12,880 Jadi biarkan aku malah menggambar array vertikal, yang hanya, sekali lagi, 494 00:22:12,880 --> 00:22:13,840 membawakan lagu artis. 495 00:22:13,840 --> 00:22:16,610 Tidak terlalu penting apa adalah di bawah tenda. 496 00:22:16,610 --> 00:22:20,350 Dan kami akan mengatakan bahwa, secara default, kapasitas 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 menyuap dengan bola stres, akan seseorang ingin datang dan menjalankan 500 00:22:29,330 --> 00:22:30,870 naik di sini untuk sesaat? 501 00:22:30,870 --> 00:22:31,960 OK, melihat tangan Anda terlebih dahulu. 502 00:22:31,960 --> 00:22:33,950 Ayo up. 503 00:22:33,950 --> 00:22:36,500 Baik. 504 00:22:36,500 --> 00:22:38,760 Jadi saya percaya itu adalah Steven. 505 00:22:38,760 --> 00:22:40,035 Ayo up. 506 00:22:40,035 --> 00:22:40,770 Baik. 507 00:22:40,770 --> 00:22:46,760 >> Tapi misalkan sekarang kita mundur ke awal keadaan dunia di mana aku 508 00:22:46,760 --> 00:22:52,180 baru saja mengumumkan stack, dan itu akan kapasitas tiga. 509 00:22:52,180 --> 00:22:54,470 Tapi ukuran belum ditentukan. 510 00:22:54,470 --> 00:22:56,100 Nampan belum ditentukan. 511 00:22:56,100 --> 00:22:57,300 Jadi beberapa pertanyaan pertama. 512 00:22:57,300 --> 00:23:01,310 Dan izinkan saya memberi Anda mic sehingga Anda dapat turut lebih aktif dalam hal ini. 513 00:23:01,310 --> 00:23:05,190 >> Jadi apa yang ada dalam ukuran saat ini dalam waktu jika semua yang saya lakukan adalah 514 00:23:05,190 --> 00:23:09,340 menyatakan tumpukan dengan satu baris kode? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Tidak banyak. 516 00:23:10,100 --> 00:23:12,080 >> DAVID Malan: OK, tidak banyak. 517 00:23:12,080 --> 00:23:14,410 Apakah kita tahu apa yang ada dalam ukuran, kita tahu apa yang ada di dalamnya 518 00:23:14,410 --> 00:23:16,330 array ini di sini? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Hanya kode acak, kan? 520 00:23:18,630 --> 00:23:20,220 Hanya - 521 00:23:20,220 --> 00:23:23,230 >> DAVID Malan: Ya, aku akan menyebutnya kode, tapi acak - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Hal. 523 00:23:23,820 --> 00:23:28,290 >> DAVID Malan: Hal-hal seperti acak 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID Malan: Bits, kan? 526 00:23:29,530 --> 00:23:31,190 Jadi nilai-nilai sampah, kan? 527 00:23:31,190 --> 00:23:33,470 Jadi permutasi dari 0 dan 1. 528 00:23:33,470 --> 00:23:35,920 Sisa-sisa penggunaan sebelumnya memori ini. 529 00:23:35,920 --> 00:23:38,150 Dan kita tidak benar-benar tahu apa nilai-nilai yang, jadi kami 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 hal pertama yang kita mungkin akan ingin lakukan di sini - 532 00:23:41,990 --> 00:23:46,630 dan biarkan aku memberikan bidang ini dalam dari ada nama - nampan. 533 00:23:46,630 --> 00:23:49,540 Apa yang harus kita mungkin menginisialisasi ukuran jika kita ingin 534 00:23:49,540 --> 00:23:51,040 mulai menggunakan tumpukan ini? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Baki 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, kapasitas dinyatakan tempat lain sebagai tiga. 538 00:23:56,710 --> 00:23:58,570 Dan itulah yang saya gunakan untuk mengalokasikan array. 539 00:23:58,570 --> 00:24:03,535 Ukuran akan mengacu pada berapa banyak nampan saat ini di stack. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Nol. 541 00:24:03,880 --> 00:24:04,460 >> DAVID Malan: Jadi harus nol. 542 00:24:04,460 --> 00:24:07,760 Jadi silakan, dan dengan jari apapun, menggambar nol dalam ukuran. 543 00:24:07,760 --> 00:24:08,440 Baik. 544 00:24:08,440 --> 00:24:10,920 Jadi sekarang, apa yang ada di dalam ini di sini, kita tidak tahu. 545 00:24:10,920 --> 00:24:12,160 Ini benar-benar hanya nilai sampah. 546 00:24:12,160 --> 00:24:14,800 Jadi kita bisa menggambar tanda tanya, tapi mari kita menjaga papan bersih untuk saat ini 547 00:24:14,800 --> 00:24:16,300 karena tidak peduli apa yang ada. 548 00:24:16,300 --> 00:24:19,130 Kita tidak perlu menginisialisasi array apa-apa, karena jika kita tahu bahwa 549 00:24:19,130 --> 00:24:23,100 ukuran stack adalah nol, well, kita seharusnya tidak melihat apa pun di 550 00:24:23,100 --> 00:24:25,590 array ini pula pada titik waktu ini. 551 00:24:25,590 --> 00:24:29,970 >> Jadi sekarang mengira bahwa aku mendorong nomor 9 ke stack. 552 00:24:29,970 --> 00:24:33,750 Bagaimana kita harus memperbarui struktur data dalam kotak hitam ini? 553 00:24:33,750 --> 00:24:35,540 Nilai-nilai apa yang perlu berubah? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Dalam - 555 00:24:36,200 --> 00:24:37,400 ukuran? 556 00:24:37,400 --> 00:24:37,650 >> DAVID Malan: OK. 557 00:24:37,650 --> 00:24:38,770 Ukuran harus menjadi apa? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Ukuran akan menjadi salah satu. 559 00:24:39,580 --> 00:24:39,870 >> DAVID Malan: OK. 560 00:24:39,870 --> 00:24:41,110 Sehingga ukuran harus menjadi satu. 561 00:24:41,110 --> 00:24:42,540 Sehingga Anda dapat melakukan ini dalam beberapa cara. 562 00:24:42,540 --> 00:24:46,920 Mari saya beri, sekarang Anda jari penghapus. 563 00:24:46,920 --> 00:24:47,260 Baik. 564 00:24:47,260 --> 00:24:49,960 Maka sekarang jari Anda adalah kuas. 565 00:24:49,960 --> 00:24:50,330 Baik. 566 00:24:50,330 --> 00:24:52,820 Dan sekarang apa lagi harus berubah, jelas, dalam struktur data? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Kita akan dari bottom up sampai 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID Malan: 9. 569 00:24:57,760 --> 00:24:58,420 OK, baik. 570 00:24:58,420 --> 00:25:01,550 Jadi masih tidak peduli apa yang di lokasi satu atau dua karena mereka 571 00:25:01,550 --> 00:25:04,520 nilai sampah, tapi kita tidak perlu repot-repot mencari sana karena ukuran 572 00:25:04,520 --> 00:25:07,540 mengatakan kepada kita bahwa hanya elemen pertama sebenarnya sah. 573 00:25:07,540 --> 00:25:10,400 Jadi sekarang aku mendorong 17 ke daftar. 574 00:25:10,400 --> 00:25:11,830 Apa yang terjadi dengan gambar ini? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: Jadi ukuran 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 Kau penghapus - 578 00:25:16,070 --> 00:25:16,810 oops. 579 00:25:16,810 --> 00:25:18,026 Kau penghapus. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID Malan: Kau kuas. 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 mendorong 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Kami tetap di atas 17, sehingga - 588 00:25:24,760 --> 00:25:25,710 >> DAVID Malan: OK, baik. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - menjatuhkannya ke bawah. 590 00:25:27,040 --> 00:25:27,530 >> DAVID Malan: Baiklah. 591 00:25:27,530 --> 00:25:27,940 Sudah mulai mudah. 592 00:25:27,940 --> 00:25:29,300 Aku tidak akan membantu Anda saat ini. 593 00:25:29,300 --> 00:25:30,510 Dorong 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Selesai. 595 00:25:31,720 --> 00:25:34,870 Menjadi penghapus. 596 00:25:34,870 --> 00:25:37,340 Aku menjadi kuas. 597 00:25:37,340 --> 00:25:39,340 Dan kemudian saya menempatkan 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID Malan: 22. 599 00:25:40,100 --> 00:25:40,620 Luar biasa. 600 00:25:40,620 --> 00:25:41,380 Jadi sekali lagi. 601 00:25:41,380 --> 00:25:44,280 Saya sekarang akan mendorong ke tumpukan 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh gosh. 604 00:25:50,278 --> 00:25:52,520 Anda benar-benar menangkap saya lengah. 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 datang. 607 00:25:55,930 --> 00:25:58,756 Bisakah kita kapasitas re-awal? 608 00:25:58,756 --> 00:25:59,790 >> DAVID Malan: Itu pertanyaan yang bagus. 609 00:25:59,790 --> 00:26:02,360 Jadi kita semacam dicat diri di sudut sini. 610 00:26:02,360 --> 00:26:06,740 Benar-benar ada keluar yang baik untuk Steven karena kita telah dialokasikan array ini 611 00:26:06,740 --> 00:26:09,130 statis, sehingga untuk berbicara, di dalam dari struktur data. 612 00:26:09,130 --> 00:26:12,170 Dan kami telah dasarnya sulit kode itu menjadi ukuran tiga. 613 00:26:12,170 --> 00:26:14,170 Jadi kita tidak bisa benar-benar mengalokasikan itu. 614 00:26:14,170 --> 00:26:20,020 >> Kita bisa jika kita kembali, kita didefinisikan ulang nampan menjadi pointer yang 615 00:26:20,020 --> 00:26:22,300 kita kemudian menggunakan malloc ke memori tangan untuk. 616 00:26:22,300 --> 00:26:25,050 Karena jika kita punya memori dari tumpukan melalui malloc, kami 617 00:26:25,050 --> 00:26:26,430 kemudian bisa membebaskannya. 618 00:26:26,430 --> 00:26:29,630 Tapi sebelum membebaskan, kita bisa mengalokasikan sepotong besar memori, 619 00:26:29,630 --> 00:26:31,330 memperbarui pointer, dan sebagainya. 620 00:26:31,330 --> 00:26:33,500 Tetapi untuk sekarang, ini benar-benar yang terbaik yang bisa kita lakukan. 621 00:26:33,500 --> 00:26:36,360 Mendorong dan pop yang mungkin akan harus sinyal beberapa error. 622 00:26:36,360 --> 00:26:40,270 >> Jadi misalnya, implementasi kami push bisa kembali bool yang 623 00:26:40,270 --> 00:26:42,390 sebelumnya kembali benar, benar, benar. 624 00:26:42,390 --> 00:26:48,390 Tapi keempat kalinya, itu akan memiliki untuk kembali palsu, misalnya. 625 00:26:48,390 --> 00:26:48,540 Baik. 626 00:26:48,540 --> 00:26:49,540 Sangat baik dilakukan. 627 00:26:49,540 --> 00:26:50,060 Selamat. 628 00:26:50,060 --> 00:26:52,160 Anda telah menerima bola stres 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 tampaknya tidak banyak dari langkah maju, kan? 633 00:26:59,740 --> 00:27:01,410 Kami menggambarkan struktur data ini. 634 00:27:01,410 --> 00:27:02,320 Sudah menarik, kan? 635 00:27:02,320 --> 00:27:03,200 Sistem operasi seperti itu. 636 00:27:03,200 --> 00:27:06,360 Rupanya web dapat memanfaatkan ini, dan aplikasi lain masih. 637 00:27:06,360 --> 00:27:10,870 Tapi apa batasan bodoh bahwa kita kembali ke semacam dua minggu batas 638 00:27:10,870 --> 00:27:12,880 di mana kita telah tetap ukuran array. 639 00:27:12,880 --> 00:27:15,010 >> Jadi memang ada beberapa cara kita bisa memecahkan masalah ini. 640 00:27:15,010 --> 00:27:18,750 Kita bisa secara dinamis mengalokasikan array, tidak dengan dikodekan itu seperti yang telah saya 641 00:27:18,750 --> 00:27:22,600 dilakukan di sini, tapi malah kembali mendeklarasikan ini, hanya harus jelas, seperti 642 00:27:22,600 --> 00:27:23,830 sesuatu seperti ini. 643 00:27:23,830 --> 00:27:29,040 Int * nampan, tidak memutuskan pada kapasitas belum. 644 00:27:29,040 --> 00:27:35,460 Tapi ketika saya menyatakan stack tempat lain dalam kode saya, saya kemudian bisa menelepon malloc, 645 00:27:35,460 --> 00:27:38,250 mendapatkan alamat dari sepotong memori, dan aku bisa menetapkan 646 00:27:38,250 --> 00:27:39,980 alamat ke nampan. 647 00:27:39,980 --> 00:27:43,340 >> Dan kemudian, karena itu hanya sepotong memori, saya bisa terus menggunakan persegi 648 00:27:43,340 --> 00:27:45,450 notasi braket dengan cara biasa. 649 00:27:45,450 --> 00:27:49,020 Karena sekali lagi, ada semacam ini setara fungsional array dan 650 00:27:49,020 --> 00:27:50,820 potongan memori yang datang kembali dari malloc. 651 00:27:50,820 --> 00:27:53,090 Kita dapat memperlakukan satu dengan yang lain menggunakan pointer aritmetika atau 652 00:27:53,090 --> 00:27:54,440 persegi notasi braket. 653 00:27:54,440 --> 00:27:55,660 Jadi itu salah satu pendekatan. 654 00:27:55,660 --> 00:28:00,120 >> Tapi bagaimana lagi kita bisa menerapkan ini struktur data yang sama, berpotensi? 655 00:28:00,120 --> 00:28:00,280 Benar? 656 00:28:00,280 --> 00:28:04,530 Saya merasa seperti baru saja kita selesaikan ini masalah seperti tahun lalu. 657 00:28:04,530 --> 00:28:08,860 Apa solusi untuk masalah ini bahwa Steven berlari ke? 658 00:28:08,860 --> 00:28:10,370 Jadi daftar terkait, benar. 659 00:28:10,370 --> 00:28:13,410 >> Jika masalahnya adalah bahwa kita melukis diri ke sudut dengan mengalokasikan 660 00:28:13,410 --> 00:28:17,580 di muka memori terlalu sedikit yang kita kemudian harus entah bagaimana berurusan dengan, baik, 661 00:28:17,580 --> 00:28:19,880 mengapa tidak hanya menghindari menerbitkan sama sekali? 662 00:28:19,880 --> 00:28:26,170 Mengapa tidak hanya menyatakan nampan menjadi pointer ke node, ergo sebuah linked list, 663 00:28:26,170 --> 00:28:30,740 dan kemudian hanya mengalokasikan node baru setiap kali Steven yang dibutuhkan untuk memenuhi 664 00:28:30,740 --> 00:28:32,400 nomor ke dalam struktur data. 665 00:28:32,400 --> 00:28:34,200 >> Jadi gambar harus berubah. 666 00:28:34,200 --> 00:28:38,220 Ini tidak akan menjadi sebagai bersih dan sederhana seperti hanya sebuah array dari tiga ints. 667 00:28:38,220 --> 00:28:42,970 Sekarang akan menjadi pointer ke struct, dan struct yang akan 668 00:28:42,970 --> 00:28:44,830 memiliki int dan pointer berikutnya. 669 00:28:44,830 --> 00:28:47,670 Ini akan memimpin melalui pointer yang lain struct tersebut untuk 670 00:28:47,670 --> 00:28:48,600 lain struct tersebut. 671 00:28:48,600 --> 00:28:50,560 Jadi gambar akan benar-benar mendapatkan berantakan sedikit. 672 00:28:50,560 --> 00:28:52,950 Dan kita akan panah mengikat segalanya bersama-sama. 673 00:28:52,950 --> 00:28:55,280 >> Tapi itu baik-baik saja, kan, karena kita telah melihat bagaimana melakukan ini. 674 00:28:55,280 --> 00:28:58,180 Dan setelah Anda merasa nyaman menerapkan sesuatu seperti linked 675 00:28:58,180 --> 00:29:01,450 Daftar, yang Anda harus lakukan jika Anda memilih untuk menerapkan tabel hash dengan 676 00:29:01,450 --> 00:29:05,120 chaining terpisah untuk p-set 6, Anda dapat menggunakannya sebagai sebuah blok bangunan, atau 677 00:29:05,120 --> 00:29:08,870 bahan, atau dalam Scratch berbicara, prosedur, sesuatu yang Anda menempatkan, Anda 678 00:29:08,870 --> 00:29:12,560 menciptakan potongan puzzle Anda sendiri yang kemudian dapat digunakan kembali. 679 00:29:12,560 --> 00:29:17,090 Jadi pengorbanan, tetapi solusi potensial bahwa kita sudah benar-benar terlihat sebelumnya. 680 00:29:17,090 --> 00:29:20,560 >> Jadi cukup sering, Anda melihat ini setiap atau dua tahun ketika Apple rilis 681 00:29:20,560 --> 00:29:23,060 sesuatu yang baru, dan semua orang yang gila berbaris di luar dari Apple 682 00:29:23,060 --> 00:29:27,050 menyimpan untuk membeli marjinalnya upgrade pada hardware. 683 00:29:27,050 --> 00:29:30,420 Saya mengatakan ini, itu OK, karena Aku salah satu dari orang-orang. 684 00:29:30,420 --> 00:29:35,140 Jadi, apa jenis struktur data mungkin mewakili kenyataan ini? 685 00:29:35,140 --> 00:29:36,980 >> Yah, sebut saja antrian, garis. 686 00:29:36,980 --> 00:29:40,270 Jadi Inggris akan menyebutnya biasanya antrian, jadi itu adalah nama yang bagus. 687 00:29:40,270 --> 00:29:44,960 Dan dua operasi yang antrian harus mendukung kami akan menelepon enqueue sebuah 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 mendorong dan pop. 690 00:29:50,120 --> 00:29:54,060 Ini hanya semacam berbeda dalam konvensi, apa yang kita panggil ini. 691 00:29:54,060 --> 00:29:57,680 Tetapi untuk enqueue sesuatu berarti menambah atau masukkan ke struktur data. 692 00:29:57,680 --> 00:29:59,570 Untuk dequeue berarti untuk menghapusnya. 693 00:29:59,570 --> 00:30:05,170 Namun, sementara tumpukan adalah data LIFO struktur, antrian adalah di pertama, 694 00:30:05,170 --> 00:30:06,740 pertama keluar struktur data. 695 00:30:06,740 --> 00:30:10,050 >> Jika Anda adalah orang di baris pertama, Anda akan menjadi orang pertama untuk mendapatkan 696 00:30:10,050 --> 00:30:12,420 keluar dari barisan dan membeli perangkat baru. 697 00:30:12,420 --> 00:30:18,070 Bayangkan betapa sedih orang-orang ini akan jika Apple malah menggunakan stack, untuk 698 00:30:18,070 --> 00:30:21,250 Misalnya, untuk melaksanakan memilih yang up mainan baru Anda. 699 00:30:21,250 --> 00:30:24,310 Jadi antrian masuk akal, tentu, dan kita bisa memikirkan segala macam 700 00:30:24,310 --> 00:30:27,480 aplikasi, mungkin, untuk antrian, terutama bila Anda ingin keadilan. 701 00:30:27,480 --> 00:30:30,040 Jadi bagaimana mungkin kita menerapkan sebagai struktur data? 702 00:30:30,040 --> 00:30:33,680 >> Nah, saya mengusulkan bahwa kita mungkin perlu melakukannya dengan cara ini. 703 00:30:33,680 --> 00:30:35,225 Jadi aku akan sekarang memiliki nomor. 704 00:30:35,225 --> 00:30:38,190 Jadi kita akan tetap sederhana dan tidak selalu berbicara dalam hal nampan. 705 00:30:38,190 --> 00:30:40,220 Hanya angka yang orang mendapatkan. 706 00:30:40,220 --> 00:30:43,760 Kapasitas akan, sekali lagi, memperbaiki jumlah orang yang dapat di 707 00:30:43,760 --> 00:30:46,900 baris ini, sebagai tiga atau apapun lainnya nilai. 708 00:30:46,900 --> 00:30:50,760 >> Tapi saya mengusulkan bahwa saya perlu untuk melacak tidak hanya dari ukuran 709 00:30:50,760 --> 00:30:52,370 antrian, berapa banyak hal di dalamnya. 710 00:30:52,370 --> 00:30:56,310 Jadi ukuran adalah ukuran saat ini, kapasitas adalah ukuran maksimum. 711 00:30:56,310 --> 00:30:58,540 Hanya lagi, nomenklatur dengan konvensi. 712 00:30:58,540 --> 00:31:03,680 Mengapa saya perlu sebuah int tambahan di dalam dari antrian untuk melacak siapa yang 713 00:31:03,680 --> 00:31:05,365 garis depan? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Mengapa saya harus melakukan itu dalam kasus 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 dapat menggunakan kembali sebagian gambar ini. 719 00:31:19,280 --> 00:31:21,480 Biarkan aku pergi ke depan dan menghapus apa yang ada di sini. 720 00:31:21,480 --> 00:31:24,580 Kami akan memberikan ini sedikit nama yang berbeda di sini. 721 00:31:24,580 --> 00:31:28,930 Mari kita menyingkirkan 17, mari kita menyingkirkan dari 9, mari kita menyingkirkan 3. 722 00:31:28,930 --> 00:31:30,410 Dan mari kita tambahkan satu hal lain. 723 00:31:30,410 --> 00:31:34,710 Saya mengusulkan bahwa saya perlu untuk melacak depan daftar, yang hanya 724 00:31:34,710 --> 00:31:35,570 akan menjadi int juga. 725 00:31:35,570 --> 00:31:36,550 Dan kita akan tetap sederhana. 726 00:31:36,550 --> 00:31:37,740 Tidak ada linked list untuk saat ini. 727 00:31:37,740 --> 00:31:40,900 >> Kita akan mengakui bahwa kita akan benjolan melawan batas ini. 728 00:31:40,900 --> 00:31:43,720 Tapi apa yang saya ingin melihat terjadi saat ini? 729 00:31:43,720 --> 00:31:47,240 Jadi misalkan saya pergi ke depan dan yang pertama orang muncul sejalan, dan 730 00:31:47,240 --> 00:31:48,560 itu adalah nomor 9. 731 00:31:48,560 --> 00:31:49,680 Kami memiliki bola stres. 732 00:31:49,680 --> 00:31:51,330 Dapatkah saya mencuri, katakanlah, 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 Ayo up. 735 00:31:53,120 --> 00:31:56,022 Kanan dari depan, karena kami akan membuat satu ini cepat. 736 00:31:56,022 --> 00:31:59,415 >> Anda masing-masing sekarang akan menjadi seorang anak penggemar di baris di Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Anda tidak akan menerima hardware Apple pada akhir meskipun hal ini. 739 00:32:06,210 --> 00:32:06,500 Baik. 740 00:32:06,500 --> 00:32:09,430 Jadi kau nomor 9, Anda nomor 17, nomor 22. 741 00:32:09,430 --> 00:32:12,130 Ini adalah nomor sewenang-wenang, seperti mahasiswa ID atau entah apa lagi. 742 00:32:12,130 --> 00:32:14,550 Dan hanya dalam beberapa saat, mari kita mulai untuk mulai menambahkan sesuatu. 743 00:32:14,550 --> 00:32:16,000 Dan aku akan menjalankan papan di sini saat ini. 744 00:32:16,000 --> 00:32:19,570 >> Jadi dalam hal ini, saya telah diinisialisasi depan untuk menjadi - 745 00:32:19,570 --> 00:32:22,380 Aku sebenarnya tidak benar-benar peduli apa yang depan, karena ukurannya adalah nol. 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 mulai untuk benar-benar melihat beberapa orang berbaris di toko. 749 00:32:29,880 --> 00:32:33,320 >> Jadi jika nomor 9, kau yang pertama ada pada 05:00, maju dan berbaris, 750 00:32:33,320 --> 00:32:34,210 atau malam sebelumnya. 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 depan daftar. 754 00:32:37,940 --> 00:32:41,440 Jadi aku akan pergi ke depan dan memperbarui ukuran ini data saat 755 00:32:41,440 --> 00:32:44,740 struktur untuk tidak menjadi 0 lagi, tetapi untuk menjadi 1. 756 00:32:44,740 --> 00:32:47,630 Aku akan menempatkan 9 di depan daftar. 757 00:32:47,630 --> 00:32:51,020 Biarkan aku pergi ke depan dan beralih layar sehingga kita bisa melihat masa lalu kita di sini. 758 00:32:51,020 --> 00:32:53,220 >> Dan sekarang apa yang saya inginkan untuk diletakkan di depan? 759 00:32:53,220 --> 00:32:56,240 Aku akan melacak bahwa depan antrian sekarang 760 00:32:56,240 --> 00:32:58,570 adalah di lokasi 0. 761 00:32:58,570 --> 00:33:00,510 Karena apa yang selanjutnya akan terjadi? 762 00:33:00,510 --> 00:33:03,000 Nah, misalkan sekarang saya enqueue 17 juga. 763 00:33:03,000 --> 00:33:04,510 Jadi hop sejalan sana. 764 00:33:04,510 --> 00:33:07,060 Dan lagi, semacam pintu ke toko akan berada di sini. 765 00:33:07,060 --> 00:33:08,700 Jadi sekarang saya telah menambahkan 17. 766 00:33:08,700 --> 00:33:10,810 Dan meskipun orang-orang yang menghalangi layar, itu OK, 767 00:33:10,810 --> 00:33:12,300 karena kita bisa melihatnya di sini. 768 00:33:12,300 --> 00:33:12,910 Maaf. 769 00:33:12,910 --> 00:33:13,810 >> AUDIENCE: Kita bisa bergerak - 770 00:33:13,810 --> 00:33:14,660 >> DAVID Malan: Tidak, itu OK. 771 00:33:14,660 --> 00:33:16,000 Ini sangat besar di sana. 772 00:33:16,000 --> 00:33:18,580 Jadi 17 sekarang dalam antrian. 773 00:33:18,580 --> 00:33:21,332 Saya perlu memperbarui yang bidang sekarang meskipun? 774 00:33:21,332 --> 00:33:23,210 OK, pasti ukuran. 775 00:33:23,210 --> 00:33:26,430 Dan bagaimana depan? 776 00:33:26,430 --> 00:33:27,040 OK, tidak ada. 777 00:33:27,040 --> 00:33:30,200 Depan tidak harus berubah, karena seperti tumpukan, kita 778 00:33:30,200 --> 00:33:31,370 ingin mempertahankan keadilan. 779 00:33:31,370 --> 00:33:35,150 Jadi jika 9 datang pertama, kami ingin 9 menjadi pertama kali keluar dari garis 780 00:33:35,150 --> 00:33:36,420 dan masuk ke toko. 781 00:33:36,420 --> 00:33:37,220 >> Bahkan, mari kita lihat itu. 782 00:33:37,220 --> 00:33:42,235 Sebelum kita memasukkan 22, mari kita pergi ke depan 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 >> AUDIENCE: 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 bisa berjalan ke toko. 787 00:33:48,050 --> 00:33:49,880 Dan berpura-pura bahwa toko 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 harus terjadi sekarang? 790 00:33:53,400 --> 00:33:54,490 Desain keputusan. 791 00:33:54,490 --> 00:33:56,825 Jadi bukan insting buruk, tapi - apa nama Anda lagi? 792 00:33:56,825 --> 00:33:57,090 >> AUDIENCE: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID Malan: David. 794 00:33:57,500 --> 00:33:58,810 Jadi apa yang Daud lakukan? 795 00:33:58,810 --> 00:34:02,590 Dia mencoba untuk semacam memperbaiki data struktur dan bergerak dari lokasi nya 796 00:34:02,590 --> 00:34:04,100 ke bekas lokasi Jake. 797 00:34:04,100 --> 00:34:06,740 Dan itu baik jika kita bersedia untuk menerima bahwa sebagai 798 00:34:06,740 --> 00:34:08,199 implementasi detail. 799 00:34:08,199 --> 00:34:11,100 Tapi pertama-tama, mari kita update data Struktur sebelum kita melakukan itu. 800 00:34:11,100 --> 00:34:14,139 Karena aku tidak menyukai ide dari semua orang-orang pergeseran di baris ini. 801 00:34:14,139 --> 00:34:17,360 >> Ini bukan masalah besar jika David melakukannya dengan satu langkah, tapi sekali lagi, pikirkan kembali 802 00:34:17,360 --> 00:34:20,360 ketika kita punya delapan relawan di panggung dan kami telah dilakukan seperti penyisipan 803 00:34:20,360 --> 00:34:22,600 semacam, di mana kita harus memulai bergerak semua orang di sekitar. 804 00:34:22,600 --> 00:34:23,790 Yang mendapat mahal, kan? 805 00:34:23,790 --> 00:34:28,330 Itu membuat saya merasa ngeri tentang O besar n, O besar n kuadrat lagi. 806 00:34:28,330 --> 00:34:30,650 Ini tidak merasa seperti hasil yang ideal. 807 00:34:30,650 --> 00:34:32,080 >> Jadi mari kita update ini. 808 00:34:32,080 --> 00:34:35,120 Jadi ukuran antrian tidak lagi 2. 809 00:34:35,120 --> 00:34:37,090 Ini sekarang hanya 1. 810 00:34:37,090 --> 00:34:40,360 Tapi saya sekarang dapat memperbarui sesuatu Aku tidak memperbarui sebelumnya, 811 00:34:40,360 --> 00:34:41,130 depan daftar. 812 00:34:41,130 --> 00:34:45,420 Aku hanya bisa mengatakan, adalah lokasi itu 1? 813 00:34:45,420 --> 00:34:49,770 Jadi sekarang kita memiliki nilai sampah di sini, nilai sampah di sini, dan David di 814 00:34:49,770 --> 00:34:51,469 tengah sampah ini. 815 00:34:51,469 --> 00:34:54,980 Tapi struktur data masih utuh. 816 00:34:54,980 --> 00:34:58,540 >> Dan pada kenyataannya, aku bahkan tidak perlu mengubah nomor mantan Jake 817 00:34:58,540 --> 00:35:00,460 9, karena siapa yang peduli. 818 00:35:00,460 --> 00:35:04,470 Saya memiliki cukup informasi sekarang dalam ukuran yang saya tahu ada satu orang di 819 00:35:04,470 --> 00:35:05,030 antrian ini. 820 00:35:05,030 --> 00:35:08,340 Dan saya tahu bahwa orang itu berada di lokasi 1, bukan 0. 821 00:35:08,340 --> 00:35:09,760 Aku tidak menghitung. 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 terjadi selanjutnya? 825 00:35:14,330 --> 00:35:15,010 Mari kita enqueue - 826 00:35:15,010 --> 00:35:15,370 siapa namamu? 827 00:35:15,370 --> 00:35:16,160 >> AUDIENCE: 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 sebuah Callen, dan 22 sekarang dalam antrian. 830 00:35:20,770 --> 00:35:22,300 Jadi sekarang apa yang harus berubah di sini? 831 00:35:22,300 --> 00:35:24,380 Depan tidak akan berubah, jelas. 832 00:35:24,380 --> 00:35:27,160 Ukuran akan berubah menjadi 2 lagi. 833 00:35:27,160 --> 00:35:31,590 Dan 22 berakhir di sini, 9 masih ada, tapi itu efektif 834 00:35:31,590 --> 00:35:32,600 nilai sampah sekarang. 835 00:35:32,600 --> 00:35:35,910 Ini hanya sisa-sisa masa lalu Jake. 836 00:35:35,910 --> 00:35:39,200 >> Jadi sekarang apa yang terjadi jika Saya dequeue David? 837 00:35:39,200 --> 00:35:41,560 Salah satu operasi terakhir, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Kita bisa bergeser, tapi saya mengusulkan mari kita melakukan pekerjaan sesedikit mungkin. 839 00:35:46,070 --> 00:35:50,280 Sekarang struktur data saya pergi kembali dalam ukuran 2-1. 840 00:35:50,280 --> 00:35:53,730 Tapi depan antrian kini menjadi 2. 841 00:35:53,730 --> 00:35:56,640 Saya tidak perlu mengubah angka-angka ini dulu, karena mereka 842 00:35:56,640 --> 00:35:58,230 hanya nilai sampah. 843 00:35:58,230 --> 00:35:59,720 >> Tapi sekarang apa yang terjadi? 844 00:35:59,720 --> 00:36:03,280 Misalkan saya enqueue diriku, 26? 845 00:36:03,280 --> 00:36:05,890 Saya merasa seperti saya milik di sini. 846 00:36:05,890 --> 00:36:06,890 Jadi aku sedang enqueued. 847 00:36:06,890 --> 00:36:08,760 Jadi aku agak berada di sini. 848 00:36:08,760 --> 00:36:11,300 Dan meskipun Anda tidak cukup menghargai ini secara visual di atas panggung, 849 00:36:11,300 --> 00:36:15,075 karena kita memiliki banyak ruang, aku harus tidak bisa berdiri di sini, mengapa? 850 00:36:15,075 --> 00:36:16,290 >> AUDIENCE: Anda di luar batas. 851 00:36:16,290 --> 00:36:16,370 >> DAVID Malan: Benar. 852 00:36:16,370 --> 00:36:16,940 Aku di luar batas. 853 00:36:16,940 --> 00:36:19,330 Aku sudah diindeks di luar batas-batas array ini. 854 00:36:19,330 --> 00:36:23,420 Aku benar-benar harus di salah satu tiga lokasi mungkin. 855 00:36:23,420 --> 00:36:25,150 Sekarang, mana yang paling alami untuk pergi? 856 00:36:25,150 --> 00:36:27,760 Saya mengusulkan kita leveraged satu minggu trik. 857 00:36:27,760 --> 00:36:30,150 Mod operator, persentase. 858 00:36:30,150 --> 00:36:36,850 Karena aku secara teknis berdiri di Lokasi 3, tapi aku 3 kapasitas mod, 859 00:36:36,850 --> 00:36:40,250 jadi 3, tanda persen, 3 - 860 00:36:40,250 --> 00:36:40,970 kapasitas adalah 3. 861 00:36:40,970 --> 00:36:41,720 Apa itu? 862 00:36:41,720 --> 00:36:43,700 Apa sisanya ketika Anda membagi 3 dengan 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Sehingga menempatkan saya sedang Jake adalah, yang benar-benar baik. 865 00:36:48,140 --> 00:36:50,370 Jadi sekarang pelaksanaan hal ini akan 866 00:36:50,370 --> 00:36:51,250 menjadi sedikit sakit kepala. 867 00:36:51,250 --> 00:36:53,740 Ini benar-benar hanya satu baris sakit kepala, kode. 868 00:36:53,740 --> 00:36:56,580 Tapi setidaknya sekarang ada sampah nilai di sini, tapi ada dua 869 00:36:56,580 --> 00:36:57,910 ints sah sini. 870 00:36:57,910 --> 00:37:04,160 Dan saya menyatakan bahwa sekarang kami telah melakukan apa yang harus kita lakukan asalkan 871 00:37:04,160 --> 00:37:08,600 kita mengubah apa yang Jake nilai adalah menjadi 26. 872 00:37:08,600 --> 00:37:12,110 >> Kami sekarang memiliki informasi yang cukup masih untuk mempertahankan integritas 873 00:37:12,110 --> 00:37:13,060 dari struktur data. 874 00:37:13,060 --> 00:37:17,160 Kami masih agak kurang beruntung ketika kita ingin memasukkan empat atau lebih Total 875 00:37:17,160 --> 00:37:20,740 elemen, tapi aku setidaknya bisa membuat cantik efisiensi penggunaan konstan ini 876 00:37:20,740 --> 00:37:21,740 waktu, sebenarnya. 877 00:37:21,740 --> 00:37:27,150 Saya tidak perlu khawatir tentang pergeseran semua orang, sebagai kecenderungan David adalah. 878 00:37:27,150 --> 00:37:30,816 >> Setiap pertanyaan pada tumpukan, atau antrian ini? 879 00:37:30,816 --> 00:37:32,184 >> AUDIENCE: Apakah alasan mengapa Anda membutuhkan ukuran sehingga Anda tahu 880 00:37:32,184 --> 00:37:34,010 mana untuk seseorang? 881 00:37:34,010 --> 00:37:34,770 >> DAVID Malan: Tepat. 882 00:37:34,770 --> 00:37:38,230 Aku perlu tahu ukuran array karena saya perlu tahu persis bagaimana 883 00:37:38,230 --> 00:37:41,940 banyak nilai-nilai yang sah, dan agar saya dapat menemukan tempat untuk meletakkan 884 00:37:41,940 --> 00:37:42,800 orang berikutnya. 885 00:37:42,800 --> 00:37:43,300 Tepat. 886 00:37:43,300 --> 00:37:44,580 Ukurannya - 887 00:37:44,580 --> 00:37:46,360 sebenarnya, kita tidak update ini. 888 00:37:46,360 --> 00:37:48,380 Saya menambahkan sendiri di 26. 889 00:37:48,380 --> 00:37:51,760 Ukurannya sekarang, tidak 1, tapi 2. 890 00:37:51,760 --> 00:37:57,780 Jadi sekarang ini memang membantu saya menemukan kepala daftar, yang tidak 0, tidak 891 00:37:57,780 --> 00:37:59,250 1, tapi 2. 892 00:37:59,250 --> 00:38:01,665 Bagian depan daftar memang nomor 22. 893 00:38:01,665 --> 00:38:05,120 Karena dia datang pertama, jadi dia harus akan diizinkan masuk ke toko sebelum saya, 894 00:38:05,120 --> 00:38:08,780 meskipun secara visual aku berdiri lebih dekat ke toko. 895 00:38:08,780 --> 00:38:09,220 >> Baiklah? 896 00:38:09,220 --> 00:38:12,410 Sebuah tepuk tangan untuk orang-orang 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: aku bisa membiarkan Anda tetap baki. 899 00:38:18,150 --> 00:38:20,760 Kita bisa melihat apa yang terjadi jika Anda inginkan, tapi mungkin tidak. 900 00:38:20,760 --> 00:38:21,590 Baik. 901 00:38:21,590 --> 00:38:25,380 Jadi apa sekarang yang meninggalkan kita? 902 00:38:25,380 --> 00:38:28,900 Nah, biarkan aku mengusulkan bahwa ada Beberapa struktur data lainnya kita bisa 903 00:38:28,900 --> 00:38:33,810 mulai menambah tool kit kami yang akan sebenarnya cukup, cukup relevan sebagai 904 00:38:33,810 --> 00:38:35,270 kita menyelam ke web hal. 905 00:38:35,270 --> 00:38:38,150 Yang sekali lagi, memiliki beberapa jenis koneksi pohon-pohon dalam bentuk 906 00:38:38,150 --> 00:38:40,550 sesuatu yang disebut DOM, dokumen model objek. 907 00:38:40,550 --> 00:38:42,370 Tapi kita akan melihat lebih banyak bahwa sebelum lama. 908 00:38:42,370 --> 00:38:46,260 >> Mari saya mengusulkan bahwa kita definitionally menyebut pohon sekarang apa yang mungkin Anda kenal sebagai 909 00:38:46,260 --> 00:38:48,820 lebih dari sebuah pohon keluarga, di mana Anda memiliki beberapa leluhur di 910 00:38:48,820 --> 00:38:49,790 akar pohon. 911 00:38:49,790 --> 00:38:54,480 Sebuah ibu pemimpin patriarki atau di bagian paling atas pohon. 912 00:38:54,480 --> 00:38:56,700 Tanpa pasangan mereka, dalam kasus ini. 913 00:38:56,700 --> 00:39:00,940 Tapi kita sekarang memiliki apa yang akan kita sebut anak-anak, yang merupakan node yang menggantung 914 00:39:00,940 --> 00:39:05,480 dari anak kiri atau anak kanan, panah seperti yang digambarkan di sini. 915 00:39:05,480 --> 00:39:10,490 >> Dengan kata lain, dalam struktur data pohon di komputer, sebuah pohon memiliki nol 916 00:39:10,490 --> 00:39:11,480 atau lebih node. 917 00:39:11,480 --> 00:39:13,500 Jika memiliki setidaknya satu simpul, itu disebut akar. 918 00:39:13,500 --> 00:39:15,700 Hal-hal yang visual kita menarik di bagian atas. 919 00:39:15,700 --> 00:39:20,280 Dan simpul tersebut, seperti node lain, bisa memiliki nol, satu, atau dua, atau tiga, 920 00:39:20,280 --> 00:39:23,600 atau namun banyak anak-anak struktur data mendukung. 921 00:39:23,600 --> 00:39:29,150 Dalam kasus ini, akar, menyimpan nilai satu, memiliki dua anak, 2 dan 3, 922 00:39:29,150 --> 00:39:33,020 jadi kita umumnya memanggil 2 kiri anak dan 3 anak kanan. 923 00:39:33,020 --> 00:39:36,940 >> Dan kemudian ketika kita turun ke 5, 6, dan 7, 6 bisa disebut anak tengah. 924 00:39:36,940 --> 00:39:38,940 Jika Anda memiliki empat anak, itu akan membingungkan. 925 00:39:38,940 --> 00:39:42,260 Jadi kita berhenti menggunakan jenis yang shortcut verbal. 926 00:39:42,260 --> 00:39:44,580 Tapi itu benar-benar hanya pohon keluarga. 927 00:39:44,580 --> 00:39:48,880 Dan daun sini adalah node yang sendiri tidak memiliki anak. 928 00:39:48,880 --> 00:39:52,540 Mereka menggantung dari bawah pohon. 929 00:39:52,540 --> 00:39:56,940 >> Jadi bagaimana mungkin kita menerapkan pohon yang memiliki hanya dua anak maksimal? 930 00:39:56,940 --> 00:39:58,410 Kita akan menyebutnya sebuah pohon biner. 931 00:39:58,410 --> 00:40:00,960 Bi berarti dua lagi, dalam hal ini kasus, seperti dengan biner. 932 00:40:00,960 --> 00:40:04,830 Dan sehingga dapat memiliki nol, satu, atau dua anak maksimal. 933 00:40:04,830 --> 00:40:08,650 >> Saya akan mengusulkan agar kita menerapkan node untuk itu struktur dengan n int, 934 00:40:08,650 --> 00:40:11,910 dan kemudian dua pointer, satu disebut kiri, yang disebut benar. 935 00:40:11,910 --> 00:40:14,830 Tetapi mereka hanya bagus konvensi sewenang-wenang. 936 00:40:14,830 --> 00:40:18,170 Dan apa yang bagus sekarang, terutama jika Anda jenis berjuang konseptual dengan 937 00:40:18,170 --> 00:40:21,300 rekursi, atau berpikir bahwa itu bukan benar-benar solusi untuk apa pun, 938 00:40:21,300 --> 00:40:23,120 terutama jika Anda bisa kehabisan memori. 939 00:40:23,120 --> 00:40:26,600 Sekarang bahwa kita sedang berbicara tentang data struktur dan algoritma yang memungkinkan 940 00:40:26,600 --> 00:40:31,030 kita untuk melintasi dan memanipulasi mereka, Ternyata rekursi datang kembali 941 00:40:31,030 --> 00:40:34,240 yang jauh lebih menarik jika tidak dengan cara yang indah. 942 00:40:34,240 --> 00:40:38,670 >> Jadi ini saya usulkan adalah pelaksanaan dari fungsi Search. 943 00:40:38,670 --> 00:40:39,870 Mengingat dua input - 944 00:40:39,870 --> 00:40:41,570 jadi menganggap ini sebagai kotak hitam. 945 00:40:41,570 --> 00:40:46,560 Mengingat dua masukan, n, int, dan pointer ke pohon, pointer ke 946 00:40:46,560 --> 00:40:50,020 node, atau benar-benar akar pohon, saya menyatakan bahwa fungsi ini dapat kembali 947 00:40:50,020 --> 00:40:53,530 benar atau salah, bahwa nilai n di dalam pohon ini. 948 00:40:53,530 --> 00:40:55,210 >> Apa yang ada didalam kotak hitam ini? 949 00:40:55,210 --> 00:40:57,440 Nah, empat cabang. 950 00:40:57,440 --> 00:40:58,385 Pertama hanya memeriksa. 951 00:40:58,385 --> 00:41:00,490 Jika pohon null, hanya kembali palsu. 952 00:41:00,490 --> 00:41:04,580 Jika tidak ada simpul, tidak ada n, tidak ada nomor, hanya kembali palsu. 953 00:41:04,580 --> 00:41:12,330 Jika meskipun, n, nilai yang Anda cari untuk, kurang dari pohon panah n, dan 954 00:41:12,330 --> 00:41:15,180 hanya harus jelas, apa artinya bila Saya menulis pohon dan kemudian panah 955 00:41:15,180 --> 00:41:18,150 notasi, n? 956 00:41:18,150 --> 00:41:18,690 Tepat. 957 00:41:18,690 --> 00:41:21,970 Ini berarti bahwa dereference pointer disebut pohon. 958 00:41:21,970 --> 00:41:26,750 Pergi ke sana, dan kemudian masuk ke dalam itu simpul dan lapangan yang disebut n. 959 00:41:26,750 --> 00:41:30,810 Dan kemudian membandingkan n aktual yang dilewatkan ke Cari menentangnya. 960 00:41:30,810 --> 00:41:35,390 >> Jadi jika n kurang dari, nilai n di node pohon itu sendiri, baik, 961 00:41:35,390 --> 00:41:36,720 apa artinya? 962 00:41:36,720 --> 00:41:40,690 Itu berarti apa-apa pada pandangan pertama. 963 00:41:40,690 --> 00:41:40,900 Benar? 964 00:41:40,900 --> 00:41:45,560 Sama seperti ketika Anda memiliki sebuah array nilai-nilai, Anda mungkin ingin menerapkan biner 965 00:41:45,560 --> 00:41:48,290 pencarian sebagai bentuk membagi dan menaklukkan. 966 00:41:48,290 --> 00:41:51,790 Tapi apa asumsi yang kita perlu membuat untuk pencarian biner untuk bekerja sama sekali 967 00:41:51,790 --> 00:41:54,510 dalam buku telepon dan contoh sebelumnya? 968 00:41:54,510 --> 00:41:55,530 >> Bagaimana akan diurutkan. 969 00:41:55,530 --> 00:41:59,490 Jadi mari kita memperbaiki definisi pohon di sini tidak hanya pohon, yang dapat 970 00:41:59,490 --> 00:42:00,880 memiliki sejumlah anak. 971 00:42:00,880 --> 00:42:04,700 Tidak hanya pohon biner, yang dapat memiliki 0, 1, atau 2 maksimal. 972 00:42:04,700 --> 00:42:09,700 Tapi sebagai pohon pencarian biner, atau BST, yang hanya cara mewah untuk mengatakan suatu 973 00:42:09,700 --> 00:42:15,430 pohon biner sehingga setiap node anak kiri, jika ada, adalah 974 00:42:15,430 --> 00:42:16,830 kurang dari node. 975 00:42:16,830 --> 00:42:20,170 Dan anak kanan setiap node, jika ada, lebih besar 976 00:42:20,170 --> 00:42:21,740 dari simpul itu sendiri. 977 00:42:21,740 --> 00:42:25,200 >> Jadi dengan kata lain, jika Anda adalah untuk menarik pohon keluar, semua nomor yang 978 00:42:25,200 --> 00:42:30,620 hati-hati seimbang seperti ini sehingga jika Anda memiliki 55 sebagai root, 33 bisa pergi 979 00:42:30,620 --> 00:42:33,090 ke kiri karena itu kurang dari 55. 980 00:42:33,090 --> 00:42:36,430 77 bisa pergi ke kanan karena itu lebih besar dari 55. 981 00:42:36,430 --> 00:42:40,750 Tapi sekarang perhatikan, definisi yang sama, itu adalah definisi rekursif secara lisan, 982 00:42:40,750 --> 00:42:42,600 harus mengajukan 33. 983 00:42:42,600 --> 00:42:47,610 Anak kiri 33 itu harus kurang dari itu, dan anak kanan 33 itu, 44, harus 984 00:42:47,610 --> 00:42:48,580 lebih besar dari itu. 985 00:42:48,580 --> 00:42:51,670 >> Jadi ini adalah sebuah pohon pencarian biner, dan Saya mengusulkan, menggunakan sedikit 986 00:42:51,670 --> 00:42:53,910 rekursi, kita sekarang dapat menemukan n. 987 00:42:53,910 --> 00:42:59,160 Jadi jika n kurang dari nilai n yang node saat ini, aku akan pergi 988 00:42:59,160 --> 00:43:04,090 depan dan menyepak bola, sehingga untuk berbicara, dan hanya kembali apa jawabannya adalah 989 00:43:04,090 --> 00:43:08,470 mencari n pada anak kiri pohon. 990 00:43:08,470 --> 00:43:11,370 Perhatikan lagi, fungsi ini hanya mengharapkan bintang node, sebuah 991 00:43:11,370 --> 00:43:12,780 pointer ke node. 992 00:43:12,780 --> 00:43:17,360 Jadi pasti aku hanya bisa melakukan pohon panah kiri, yang akan menyebabkan 993 00:43:17,360 --> 00:43:18,400 saya ke node lain. 994 00:43:18,400 --> 00:43:19,480 Tapi apa simpul itu? 995 00:43:19,480 --> 00:43:22,820 >> Nah, menurut deklarasi ini, kiri adalah hanya pointer, sehingga hanya 996 00:43:22,820 --> 00:43:27,090 berarti aku melewati ke fungsi pencarian pointer yang berbeda, yaitu 997 00:43:27,090 --> 00:43:30,750 salah satu yang mewakili Pohon anak kiri saya. 998 00:43:30,750 --> 00:43:36,040 Jadi dalam hal ini, pointer ke 33, jika ini adalah masukan sampel kami Sementara itu, jika 999 00:43:36,040 --> 00:43:40,740 n lebih besar dari nilai n di node saat ini di pohon, maka aku 1000 00:43:40,740 --> 00:43:43,370 akan pergi ke depan dan menyepak bola yang lain arah dan hanya mengatakan, saya tidak 1001 00:43:43,370 --> 00:43:47,280 tahu apakah nilai ini n adalah di pohon, tapi aku tahu apakah itu, itu saya turun 1002 00:43:47,280 --> 00:43:49,090 cabang kanan, sehingga untuk berbicara. 1003 00:43:49,090 --> 00:43:53,120 Jadi biarkan saya panggilan rekursif mencari, melewati n lagi, tapi lewat di 1004 00:43:53,120 --> 00:43:54,580 pointer ke anak kanan saya. 1005 00:43:54,580 --> 00:44:00,020 >> Dengan kata lain, jika aku saat ini di 55 dan saya sedang mencari 99, saya tahu bahwa 99 1006 00:44:00,020 --> 00:44:04,270 lebih besar dari 55, jadi seperti aku merobek minggu buku telepon lalu dan kami 1007 00:44:04,270 --> 00:44:07,140 pergi kanan, sama kita akan pergi di sini. 1008 00:44:07,140 --> 00:44:11,960 Dan aku tidak tahu apakah itu di sebelah kanan saya anak, dan itu tidak, 77 ada, tapi 1009 00:44:11,960 --> 00:44:13,210 Aku tahu itu ke arah itu. 1010 00:44:13,210 --> 00:44:18,770 Jadi saya sebut pencarian di anak kanan saya, 77, dan biarkan angka pencarian keluar dari 1011 00:44:18,770 --> 00:44:24,950 sana jika 99 di sewenang-wenang ini contoh adalah sebenarnya ada. 1012 00:44:24,950 --> 00:44:26,900 >> Lain, apa kasus terakhir? 1013 00:44:26,900 --> 00:44:28,620 Jika pohon null adalah salah satu kasus. 1014 00:44:28,620 --> 00:44:31,890 Jika n kurang dari simpul saat ini yang Nilai adalah kasus lain. 1015 00:44:31,890 --> 00:44:35,120 Jika n lebih besar dari saat ini Nilai node adalah kasus ketiga. 1016 00:44:35,120 --> 00:44:38,250 Apa kasus keempat dan terakhir? 1017 00:44:38,250 --> 00:44:39,480 Saya pikir kita keluar dari kasus, kan? 1018 00:44:39,480 --> 00:44:44,690 Harus bahwa n adalah di node saat ini bahwa aku di. 1019 00:44:44,690 --> 00:44:49,640 >> Jadi jika saya mencari 55 pada saat ini dalam cerita, bahwa cabang 1020 00:44:49,640 --> 00:44:51,780 pohon akan kembali benar. 1021 00:44:51,780 --> 00:44:55,380 Jadi apa yang menarik di sini adalah bahwa kita sebenarnya, tidak seperti minggu terakhir, kita jenis 1022 00:44:55,380 --> 00:44:56,740 dari memiliki dua kasus dasar. 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 kasus dasar karena jika pohon adalah nol, tidak ada yang dapat dilakukan. 1025 00:45:01,390 --> 00:45:03,410 Hanya mengembalikan kode keras nilai palsu. 1026 00:45:03,410 --> 00:45:07,400 >> Bagian bawah cabang adalah semacam default, dimana jika kita sudah diperiksa untuk 1027 00:45:07,400 --> 00:45:11,550 null, kami telah memeriksa jika harus kiri, tapi itu tidak boleh, kami telah 1028 00:45:11,550 --> 00:45:14,640 diperiksa jika harus tepat, tetapi tidak boleh, jelas itu harus 1029 00:45:14,640 --> 00:45:15,870 tepat di mana kita berada. 1030 00:45:15,870 --> 00:45:16,780 Itu kasus dasar. 1031 00:45:16,780 --> 00:45:19,920 Jadi ada dua kasus rekursif terjepit ada di tengah. 1032 00:45:19,920 --> 00:45:21,630 Tapi aku bisa menulis ini dalam urutan apapun. 1033 00:45:21,630 --> 00:45:24,520 Saya hanya berpikir itu agak merasa alami untuk pertama memeriksa untuk kesalahan yang mungkin, 1034 00:45:24,520 --> 00:45:28,340 kemudian memeriksa kiri, kemudian memeriksa kanan, kemudian berasumsi bahwa Anda berada di node 1035 00:45:28,340 --> 00:45:30,630 Anda benar-benar mencari. 1036 00:45:30,630 --> 00:45:36,240 >> Jadi mengapa hal ini menjadi berguna? 1037 00:45:36,240 --> 00:45:37,910 Jadi ternyata - 1038 00:45:37,910 --> 00:45:42,110 dan biarkan aku melompat ke teaser di sini yang ada di web. 1039 00:45:42,110 --> 00:45:44,920 Kita akan mulai menggunakan bukan bahasa pemrograman pada awalnya, tetapi 1040 00:45:44,920 --> 00:45:46,030 markup language. 1041 00:45:46,030 --> 00:45:48,740 Sebuah bahasa markup menjadi salah satu yang semangat yang sama pemrograman 1042 00:45:48,740 --> 00:45:51,715 bahasa, tetapi tidak memberikan kemampuan untuk mengekspresikan diri secara logis. 1043 00:45:51,715 --> 00:45:55,070 Ini hanya memberi Anda kemampuan untuk mengekspresikan diri secara struktural. 1044 00:45:55,070 --> 00:45:57,960 >> Di mana Anda ingin menempatkan sesuatu pada halaman, halaman web? 1045 00:45:57,960 --> 00:45:59,200 Warna apa yang Anda ingin membuatnya? 1046 00:45:59,200 --> 00:46:00,950 Apa ukuran font yang Anda ingin membuatnya? 1047 00:46:00,950 --> 00:46:02,970 Apa kata-kata yang Anda benar-benar inginkan pada halaman web? 1048 00:46:02,970 --> 00:46:04,060 Jadi itulah bahasa markup. 1049 00:46:04,060 --> 00:46:07,690 Tapi kemudian kami akan sangat cepat memperkenalkan JavaScript, yang merupakan penuh 1050 00:46:07,690 --> 00:46:08,560 bahasa pemrograman. 1051 00:46:08,560 --> 00:46:12,530 Sangat mirip dalam penampilan sintaktis ke C, tapi itu akan memiliki beberapa 1052 00:46:12,530 --> 00:46:15,200 bagus, lebih kuat, lebih fitur ramah pengguna. 1053 00:46:15,200 --> 00:46:18,050 >> Dan salah satu frustrasi ini titik dalam semester adalah bahwa kita akan 1054 00:46:18,050 --> 00:46:22,065 segera menerapkan ejaan dalam jauh lebih sedikit baris kode menggunakan bahasa lain 1055 00:46:22,065 --> 00:46:25,580 daripada C sendiri memungkinkan, tapi untuk alasan yang kita akan segera mengerti. 1056 00:46:25,580 --> 00:46:27,750 Ini akan menjadi yang pertama halaman web tersebut. 1057 00:46:27,750 --> 00:46:30,120 Ini akan benar-benar underwhelming, yang pertama kita buat. 1058 00:46:30,120 --> 00:46:31,400 Ini hanya akan berkata, hello world. 1059 00:46:31,400 --> 00:46:34,010 Tetapi jika Anda belum pernah melihatnya sebelumnya, ini adalah HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Jika Anda pergi ke opsi menu tertentu dalam kebanyakan browser, pada setiap halaman web pada 1062 00:46:39,310 --> 00:46:43,160 internet, Anda dapat melihat HTML bahwa beberapa orang menulis kepada 1063 00:46:43,160 --> 00:46:44,400 membuat halaman web. 1064 00:46:44,400 --> 00:46:47,850 Dan mungkin tidak terlihat sebagai singkat atau serapi ini. 1065 00:46:47,850 --> 00:46:51,400 Tapi itu akan mengikuti pola ini kurung terbuka dan garis miring dan 1066 00:46:51,400 --> 00:46:53,660 huruf dan angka berpotensi. 1067 00:46:53,660 --> 00:46:56,770 >> Saya pikir saya akan memberikan menggoda Anda dari apa yang Anda akan mampu melakukan 1068 00:46:56,770 --> 00:46:57,950 setelah mengambil CS50. 1069 00:46:57,950 --> 00:47:02,620 Biarkan aku pergi ke cs.harvard.edu / rob, homepage kita sendiri Rob Bowden ini. 1070 00:47:02,620 --> 00:47:06,080 Dia membuat ini untuk kita. 1071 00:47:06,080 --> 00:47:07,490 Jadi, Anda akan segera dapat melakukan itu. 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 dengar pagi ini - 1074 00:47:12,480 --> 00:47:13,780 >> [HAMSTER DANCE MUSIC] 1075 00:47:13,780 --> 00:47:15,702 >> - Anda 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 berikutnya - 1080 00:47:24,300 --> 00:47:31,670