1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> SPEAKER 1: Baiklah, jadi kami kembali. 3 00:00:13,120 --> 00:00:14,480 Selamat Datang CS50. 4 00:00:14,480 --> 00:00:16,510 Ini adalah akhir minggu ketujuh. 5 00:00:16,510 --> 00:00:20,200 Jadi ingat bahwa terakhir kali, kami mulai melihat sedikit lebih canggih 6 00:00:20,200 --> 00:00:21,100 struktur data. 7 00:00:21,100 --> 00:00:25,110 Karena sampai sekarang, semua kita telah benar-benar kita miliki adalah ini, sebuah array. 8 00:00:25,110 --> 00:00:29,340 >> Tapi sebelum kita membuang array tidak semua yang menarik, yang memang 9 00:00:29,340 --> 00:00:33,570 sebenarnya adalah, apa adalah beberapa Plus ini data sederhana 10 00:00:33,570 --> 00:00:34,560 Struktur sejauh ini? 11 00:00:34,560 --> 00:00:36,110 Apa itu baik? 12 00:00:36,110 --> 00:00:39,450 Sejauh yang kita lihat? 13 00:00:39,450 --> 00:00:42,540 Apa yang Anda punya? 14 00:00:42,540 --> 00:00:44,028 Tidak ada. 15 00:00:44,028 --> 00:00:45,020 >> SISWA: [Tak terdengar]. 16 00:00:45,020 --> 00:00:45,395 >> SPEAKER 1: Apa itu? 17 00:00:45,395 --> 00:00:46,410 >> SISWA: [Tak terdengar]. 18 00:00:46,410 --> 00:00:47,000 >> SPEAKER 1: ukuran tetap. 19 00:00:47,000 --> 00:00:51,260 OK, jadi mengapa ukuran tetap baik meskipun? 20 00:00:51,260 --> 00:00:53,180 >> SISWA: [Tak terdengar]. 21 00:00:53,180 --> 00:00:56,240 >> SPEAKER 1: OK, jadi efisien dalam arti bahwa Anda dapat mengalokasikan 22 00:00:56,240 --> 00:01:00,070 jumlah yang tetap ruang, yang diharapkan justru sebanyak 23 00:01:00,070 --> 00:01:01,180 ruang yang Anda inginkan. 24 00:01:01,180 --> 00:01:02,720 Sehingga bisa jadi benar-benar plus. 25 00:01:02,720 --> 00:01:06,530 >> Apa sisi atas yang lain dari sebuah array? 26 00:01:06,530 --> 00:01:07,610 Ya? 27 00:01:07,610 --> 00:01:08,750 >> SISWA: [Tak terdengar]. 28 00:01:08,750 --> 00:01:09,550 >> SPEAKER 1: Semua - maaf? 29 00:01:09,550 --> 00:01:11,270 >> SISWA: [Tak terdengar]. 30 00:01:11,270 --> 00:01:13,620 >> SPEAKER 1: Semua kotak dalam memori atau di samping satu sama lain. 31 00:01:13,620 --> 00:01:15,220 Dan itu membantu - mengapa? 32 00:01:15,220 --> 00:01:15,970 Itu cukup benar. 33 00:01:15,970 --> 00:01:18,611 Tapi bagaimana kita dapat memanfaatkan kebenaran itu? 34 00:01:18,611 --> 00:01:21,500 >> SISWA: [Tak terdengar]. 35 00:01:21,500 --> 00:01:24,490 >> SPEAKER 1: Tepat, kita bisa melacak di mana segala sesuatu hanya dengan mengetahui 36 00:01:24,490 --> 00:01:28,560 satu alamat, yaitu alamat byte pertama dari sepotong memori. 37 00:01:28,560 --> 00:01:30,420 Atau dalam kasus string, alamat pertama 38 00:01:30,420 --> 00:01:31,460 arang dalam string tersebut. 39 00:01:31,460 --> 00:01:33,330 Dan dari sana, kita dapat menemukan akhir string. 40 00:01:33,330 --> 00:01:35,710 Kita dapat menemukan elemen kedua, Unsur ketiga, dan sebagainya. 41 00:01:35,710 --> 00:01:38,740 >> Dan jadi cara mewah untuk menggambarkan bahwa Fitur adalah bahwa array memberi kita 42 00:01:38,740 --> 00:01:40,020 random access. 43 00:01:40,020 --> 00:01:44,330 Hanya dengan menggunakan braket persegi notasi dan nomor, Anda dapat melompat ke 44 00:01:44,330 --> 00:01:48,070 elemen tertentu dalam array dalam waktu yang konstan, O besar 45 00:01:48,070 --> 00:01:49,810 dari satu, sehingga untuk berbicara. 46 00:01:49,810 --> 00:01:51,080 >> Tapi sudah ada beberapa kerugian. 47 00:01:51,080 --> 00:01:53,110 Apa array tidak melakukannya dengan sangat mudah? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 Apa itu tidak baik? 50 00:01:57,170 --> 00:01:58,810 >> SISWA: [Tak terdengar]. 51 00:01:58,810 --> 00:01:59,860 >> SPEAKER 1: Apa itu? 52 00:01:59,860 --> 00:02:00,530 >> SISWA: [Tak terdengar]. 53 00:02:00,530 --> 00:02:01,460 >> SPEAKER 1: Memperluas ukuran. 54 00:02:01,460 --> 00:02:04,800 Jadi kelemahan dari array adalah justru kebalikan dari apa yang 55 00:02:04,800 --> 00:02:05,540 upsides adalah. 56 00:02:05,540 --> 00:02:07,610 Jadi salah satu kerugian adalah bahwa itu adalah ukuran tetap. 57 00:02:07,610 --> 00:02:09,400 Jadi Anda tidak bisa benar-benar tumbuh itu. 58 00:02:09,400 --> 00:02:13,510 Anda dapat mengalokasikan sepotong besar dari memori, dan kemudian memindahkan unsur lama 59 00:02:13,510 --> 00:02:14,460 ke array baru. 60 00:02:14,460 --> 00:02:18,060 Dan kemudian bebas array yang lama, untuk Misalnya, dengan menggunakan malloc atau serupa 61 00:02:18,060 --> 00:02:21,180 fungsi yang disebut realloc, yang direalokasi memori. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, sebagai samping, mencoba untuk memberikan memori yang sebelah array 63 00:02:25,490 --> 00:02:26,610 yang sudah Anda miliki. 64 00:02:26,610 --> 00:02:28,740 Tapi mungkin memindahkan sekitar sama sekali. 65 00:02:28,740 --> 00:02:30,710 Tapi singkatnya, itu mahal, kan? 66 00:02:30,710 --> 00:02:33,440 Karena jika Anda memiliki sepotong memori ukuran ini, tapi Anda benar-benar ingin satu 67 00:02:33,440 --> 00:02:36,710 ukuran ini, dan Anda ingin mempertahankan unsur-unsur asli, Anda harus 68 00:02:36,710 --> 00:02:40,510 kira-kira proses penyalinan waktu linier yang perlu terjadi dari 69 00:02:40,510 --> 00:02:41,900 array yang lama ke yang baru. 70 00:02:41,900 --> 00:02:44,630 Dan kenyataannya adalah meminta operasi sistem lagi dan lagi dan 71 00:02:44,630 --> 00:02:48,340 lagi untuk potongan besar memori dapat mulai dikenakan biaya beberapa waktu juga. 72 00:02:48,340 --> 00:02:52,250 Jadi baik berkat dan kutukan di menyamarkan, fakta bahwa array 73 00:02:52,250 --> 00:02:53,860 adalah ukuran tetap. 74 00:02:53,860 --> 00:02:56,790 Tetapi jika kita memperkenalkan bukan sesuatu seperti ini, yang kami sebut terkait 75 00:02:56,790 --> 00:03:00,580 Daftar, kami mendapatkan beberapa keuntungan dan beberapa kelemahan di sini juga. 76 00:03:00,580 --> 00:03:05,780 >> Jadi linked list hanyalah sebuah data yang Struktur terdiri dari C structs dalam 77 00:03:05,780 --> 00:03:09,850 kasus, di mana sebuah struct, ingat, hanya wadah untuk satu atau lebih spesifik 78 00:03:09,850 --> 00:03:11,100 jenis variabel. 79 00:03:11,100 --> 00:03:16,110 Dalam hal ini, apa tipe data tampaknya dalam struct yang 80 00:03:16,110 --> 00:03:17,600 terakhir kali kita disebut node? 81 00:03:17,600 --> 00:03:19,380 Masing-masing persegi panjang ini adalah sebuah node. 82 00:03:19,380 --> 00:03:22,660 Dan masing-masing persegi panjang kecil di dalamnya adalah tipe data. 83 00:03:22,660 --> 00:03:25,300 Jenis apa yang kita katakan mereka pada hari Senin? 84 00:03:25,300 --> 00:03:26,478 Ya? 85 00:03:26,478 --> 00:03:27,870 >> SISWA: [Tak terdengar]. 86 00:03:27,870 --> 00:03:30,721 >> SPEAKER 1: Sebuah variabel dan pointer, atau lebih khusus, int, untuk n, 87 00:03:30,721 --> 00:03:32,180 dan pointer di bagian bawah. 88 00:03:32,180 --> 00:03:35,360 Kedua mereka akan terjadi 32 bit, pada setidaknya pada komputer seperti CS50 ini 89 00:03:35,360 --> 00:03:37,980 Appliance, dan jadi mereka ditarik sama dalam ukuran. 90 00:03:37,980 --> 00:03:42,260 >> Jadi apa yang menggunakan pointer meskipun untuk rupanya? 91 00:03:42,260 --> 00:03:47,690 Mengapa menambahkan panah ini sekarang ketika array yang begitu bagus dan bersih dan sederhana? 92 00:03:47,690 --> 00:03:50,460 Apa yang pointer lakukan untuk kita di setiap node ini? 93 00:03:50,460 --> 00:03:52,160 >> SISWA: [Tak terdengar]. 94 00:03:52,160 --> 00:03:52,465 >> SPEAKER 1: Tepat. 95 00:03:52,465 --> 00:03:54,120 Ini memberitahu Anda di mana yang berikutnya. 96 00:03:54,120 --> 00:03:57,350 Jadi saya semacam menggunakan analogi menggunakan benang untuk semacam 97 00:03:57,350 --> 00:03:59,180 benang node ini bersama-sama. 98 00:03:59,180 --> 00:04:01,760 Dan itulah apa yang kita lakukan dengan pointer karena masing-masing 99 00:04:01,760 --> 00:04:06,360 potongan memori mungkin atau mungkin tidak berdekatan, kembali ke belakang ke belakang 100 00:04:06,360 --> 00:04:09,500 dalam RAM, karena setiap kali Anda memanggil malloc mengatakan, cukup memberikan 101 00:04:09,500 --> 00:04:12,510 byte untuk sebuah node baru, itu mungkin berada di sini atau mungkin di sini. 102 00:04:12,510 --> 00:04:13,120 Mungkin di sini. 103 00:04:13,120 --> 00:04:13,730 Mungkin di sini. 104 00:04:13,730 --> 00:04:14,640 Anda hanya tidak tahu. 105 00:04:14,640 --> 00:04:17,880 >> Tetapi menggunakan pointer di alamat mereka node, Anda bisa menjahit mereka 106 00:04:17,880 --> 00:04:22,370 bersama-sama dengan cara yang terlihat secara visual seperti daftar bahkan jika hal-hal ini 107 00:04:22,370 --> 00:04:26,770 semua tersebar di seluruh satu atau dua atau empat Anda gigabyte RAM 108 00:04:26,770 --> 00:04:28,760 dalam komputer Anda sendiri. 109 00:04:28,760 --> 00:04:33,230 >> Jadi sisi negatifnya, maka, sebuah linked list adalah apa? 110 00:04:33,230 --> 00:04:34,670 Apa harga kita rupanya membayar? 111 00:04:34,670 --> 00:04:36,010 >> SISWA: [Tak terdengar]. 112 00:04:36,010 --> 00:04:36,920 >> SPEAKER 1: Lebih banyak ruang, kan? 113 00:04:36,920 --> 00:04:39,340 Kami telah, dalam kasus ini, dua kali lipat jumlah ruang karena kita sudah 114 00:04:39,340 --> 00:04:43,500 dari 32 bit untuk setiap node, untuk setiap int, jadi sekarang 64 bit karena kita harus 115 00:04:43,500 --> 00:04:45,050 menjaga sekitar pointer juga. 116 00:04:45,050 --> 00:04:48,860 Anda mendapatkan efisiensi lebih jika struct Anda lebih besar dari hal sederhana ini. 117 00:04:48,860 --> 00:04:52,020 Jika Anda benar-benar memiliki mahasiswa dalam yang merupakan beberapa string untuk 118 00:04:52,020 --> 00:04:55,430 Nama dan rumah, mungkin nomor ID, mungkin beberapa bidang lain sama sekali. 119 00:04:55,430 --> 00:04:59,000 >> Jadi jika Anda memiliki cukup struct besar, maka mungkin biaya pointer 120 00:04:59,000 --> 00:05:00,010 bukan masalah besar. 121 00:05:00,010 --> 00:05:03,570 Ini adalah sedikit dari kasus sudut dalam kita menyimpan seperti primitif sederhana 122 00:05:03,570 --> 00:05:04,760 dalam linked list. 123 00:05:04,760 --> 00:05:05,790 Tapi intinya adalah sama. 124 00:05:05,790 --> 00:05:08,230 Anda pasti menghabiskan lebih memori, tetapi Anda mendapatkan 125 00:05:08,230 --> 00:05:08,990 fleksibilitas. 126 00:05:08,990 --> 00:05:12,280 Karena sekarang jika saya ingin menambahkan elemen pada awal daftar ini, 127 00:05:12,280 --> 00:05:14,340 Saya harus mengalokasikan node baru. 128 00:05:14,340 --> 00:05:17,180 Dan saya harus hanya memperbarui kedua panah entah bagaimana dengan hanya menggerakkan 129 00:05:17,180 --> 00:05:17,980 beberapa petunjuk sekitar. 130 00:05:17,980 --> 00:05:20,580 >> Jika saya ingin memasukkan sesuatu ke dalam tengah daftar, saya tidak perlu 131 00:05:20,580 --> 00:05:24,410 mendorong semua orang selain seperti yang kami lakukan di minggu terakhir 'dengan para sukarelawan yang 132 00:05:24,410 --> 00:05:25,700 mewakili sebuah array. 133 00:05:25,700 --> 00:05:29,470 Aku hanya bisa mengalokasikan node baru dan kemudian hanya menunjuk panah di 134 00:05:29,470 --> 00:05:32,290 arah yang berbeda karena tidak harus tetap aktual 135 00:05:32,290 --> 00:05:35,670 memori garis sejati seperti saya sudah ditarik di sini di layar. 136 00:05:35,670 --> 00:05:38,400 >> Dan kemudian terakhir, jika Anda ingin menyisipkan sesuatu di akhir daftar, itu 137 00:05:38,400 --> 00:05:39,210 bahkan lebih mudah. 138 00:05:39,210 --> 00:05:43,320 Ini adalah semacam notasi sewenang-wenang, tapi 34 's pointer, mengambil menebak. 139 00:05:43,320 --> 00:05:46,710 Apa nilai pointer yang paling kemungkinan semacam ditarik dari seperti tua 140 00:05:46,710 --> 00:05:47,700 antena sekolah di sana? 141 00:05:47,700 --> 00:05:48,920 >> SISWA: [Tak terdengar]. 142 00:05:48,920 --> 00:05:49,900 >> SPEAKER 1: Ini mungkin nol. 143 00:05:49,900 --> 00:05:52,710 Dan memang itu adalah salah satu penulis representasi null. 144 00:05:52,710 --> 00:05:56,310 Dan itu null karena Anda benar-benar perlu tahu di mana akhir linked 145 00:05:56,310 --> 00:06:00,050 daftar adalah, jangan sampai Anda tetap berikut dan mengikuti dan mengikuti panah-panah ini 146 00:06:00,050 --> 00:06:01,170 untuk beberapa nilai sampah. 147 00:06:01,170 --> 00:06:06,230 Jadi nol akan menunjukkan bahwa tidak ada lebih node di sebelah kanan nomor 34, 148 00:06:06,230 --> 00:06:07,200 dalam kasus ini. 149 00:06:07,200 --> 00:06:10,270 >> Jadi kami mengusulkan bahwa kita dapat menerapkan node ini dalam kode. 150 00:06:10,270 --> 00:06:12,130 Dan kami telah melihat semacam ini sintaks sebelumnya. 151 00:06:12,130 --> 00:06:15,090 Typedef hanya mendefinisikan tipe baru untuk kita, memberi kita sinonim seperti 152 00:06:15,090 --> 00:06:17,100 String adalah untuk char *. 153 00:06:17,100 --> 00:06:21,030 Dalam kasus ini, itu akan memberi kita notasi singkat sehingga struct simpul 154 00:06:21,030 --> 00:06:24,010 bisa bukan hanya ditulis sebagai node, yang jauh lebih bersih. 155 00:06:24,010 --> 00:06:25,360 Ini jauh lebih sedikit verbose. 156 00:06:25,360 --> 00:06:30,080 >> Di dalam sebuah node tampaknya int disebut n, dan kemudian struct simpul * 157 00:06:30,080 --> 00:06:34,670 yang berarti persis apa yang kita ingin panah berarti, pointer yang lain 158 00:06:34,670 --> 00:06:36,940 node persis tipe data yang sama. 159 00:06:36,940 --> 00:06:40,300 Dan saya mengusulkan agar kita bisa menerapkan fungsi pencarian seperti ini, yang pada 160 00:06:40,300 --> 00:06:41,890 Sepintas mungkin tampak sedikit rumit. 161 00:06:41,890 --> 00:06:43,330 Tapi mari kita lihat dalam konteks. 162 00:06:43,330 --> 00:06:45,480 >> Biarkan aku pergi ke alat sini. 163 00:06:45,480 --> 00:06:48,460 Mari saya membuka sebuah file yang bernama Daftar nol dot h. 164 00:06:48,460 --> 00:06:53,950 Dan itu hanya berisi definisi kita hanya melihat beberapa saat yang lalu untuk data ini 165 00:06:53,950 --> 00:06:55,390 Jenis disebut node. 166 00:06:55,390 --> 00:06:57,350 Jadi kita sudah menempatkan bahwa ke dalam sebuah file dot h. 167 00:06:57,350 --> 00:07:01,430 >> Dan sebagai samping, meskipun ini program yang Anda lihat adalah 168 00:07:01,430 --> 00:07:05,410 tidak semua yang kompleks, itu memang konvensi ketika menulis sebuah program untuk 169 00:07:05,410 --> 00:07:10,270 menempatkan hal-hal seperti tipe data, untuk menarik konstanta kadang-kadang, dalam Anda 170 00:07:10,270 --> 00:07:13,210 header file dan tidak harus dalam C file Anda, tentu ketika Anda 171 00:07:13,210 --> 00:07:17,370 program lebih besar dan lebih besar, sehingga Anda tahu di mana mencarinya baik untuk 172 00:07:17,370 --> 00:07:20,840 dokumentasi dalam beberapa kasus, atau untuk dasar-dasar seperti ini, 173 00:07:20,840 --> 00:07:22,360 definisi dari beberapa jenis. 174 00:07:22,360 --> 00:07:25,680 >> Jika sekarang saya membuka daftar nol dot c, perhatikan beberapa hal. 175 00:07:25,680 --> 00:07:29,090 Ini termasuk file header sedikit, kebanyakan yang telah kita lihat sebelumnya. 176 00:07:29,090 --> 00:07:31,980 Ini termasuk file header sendiri. 177 00:07:31,980 --> 00:07:35,200 >> Dan sebagai samping, mengapa yang dua kali lipat kutipan di sini, sebagai lawan sudut 178 00:07:35,200 --> 00:07:38,340 kurung pada baris yang Aku sudah disorot sana? 179 00:07:38,340 --> 00:07:39,180 >> SISWA: [Tak terdengar]. 180 00:07:39,180 --> 00:07:40,460 >> SPEAKER 1: Ya jadi file lokal. 181 00:07:40,460 --> 00:07:44,300 Jadi jika itu file lokal Anda sendiri di sini on line 15, misalnya, Anda menggunakan 182 00:07:44,300 --> 00:07:46,570 tanda kutip ganda sebagai gantinya dari kurung siku. 183 00:07:46,570 --> 00:07:48,270 >> Sekarang ini adalah jenis yang menarik. 184 00:07:48,270 --> 00:07:51,830 Perhatikan bahwa saya telah menyatakan global variabel dalam program ini jalur 18 185 00:07:51,830 --> 00:07:55,910 dipanggil pertama, gagasan ini akan menjadi pointer yang pertama 186 00:07:55,910 --> 00:07:59,190 node dalam linked list saya, dan saya sudah diinisialisasi ke nol, karena saya sudah 187 00:07:59,190 --> 00:08:02,310 tidak mengalokasikan aktual node dulu. 188 00:08:02,310 --> 00:08:07,570 >> Jadi ini mewakili, pictorially, apa yang kita melihat beberapa saat yang lalu dalam gambar 189 00:08:07,570 --> 00:08:10,090 bahwa pointer pada jauh meninggalkan sisi. 190 00:08:10,090 --> 00:08:12,260 Jadi sekarang, pointer yang tidak memiliki panah. 191 00:08:12,260 --> 00:08:14,590 Ini bukan hanya nol. 192 00:08:14,590 --> 00:08:17,880 Tapi itu mewakili apa yang akan menjadi alamat sebenarnya pertama 193 00:08:17,880 --> 00:08:19,480 node dalam daftar ini. 194 00:08:19,480 --> 00:08:22,120 Jadi saya sudah menerapkan itu adalah global karena, seperti yang akan Anda lihat, semua ini 195 00:08:22,120 --> 00:08:25,310 Program tidak dalam hidup adalah menerapkan linked list untuk saya. 196 00:08:25,310 --> 00:08:27,050 >> Sekarang aku punya beberapa prototipe di sini. 197 00:08:27,050 --> 00:08:31,190 Saya memutuskan untuk mengimplementasikan fitur seperti penghapusan, penyisipan, mencari, dan 198 00:08:31,190 --> 00:08:31,740 traversal - 199 00:08:31,740 --> 00:08:35,210 yang terakhir hanya menjadi berjalan melintasi Daftar, mencetak unsur-unsurnya. 200 00:08:35,210 --> 00:08:36,750 Dan sekarang inilah rutinitas utama saya. 201 00:08:36,750 --> 00:08:39,890 Dan kita tidak akan menghabiskan terlalu banyak waktu pada ini karena ini adalah semacam, mudah-mudahan 202 00:08:39,890 --> 00:08:41,780 topi tua sekarang. 203 00:08:41,780 --> 00:08:45,370 >> Aku akan melakukan hal berikut, sementara pengguna bekerja sama. 204 00:08:45,370 --> 00:08:47,300 Jadi satu, aku akan mencetak out menu ini. 205 00:08:47,300 --> 00:08:49,420 Dan aku sudah diformat sebagai bersih yang aku bisa. 206 00:08:49,420 --> 00:08:52,240 Jika pengguna jenis dalam satu, yang berarti mereka ingin menghapus sesuatu. 207 00:08:52,240 --> 00:08:54,560 Jika jenis pengguna dalam dua, itu berarti mereka ingin memasukkan sesuatu. 208 00:08:54,560 --> 00:08:55,930 Dan lain sebagainya. 209 00:08:55,930 --> 00:08:58,270 Aku akan kemudian meminta maka untuk perintah. 210 00:08:58,270 --> 00:08:59,300 Dan kemudian aku akan menggunakan getInt. 211 00:08:59,300 --> 00:09:02,790 >> Jadi ini adalah benar-benar sederhana menuing antarmuka di mana Anda hanya perlu mengetikkan 212 00:09:02,790 --> 00:09:05,270 pemetaan nomor satu perintah-perintah. 213 00:09:05,270 --> 00:09:08,730 Dan sekarang saya memiliki tombol bagus bersih Pernyataan itu akan mengaktifkan 214 00:09:08,730 --> 00:09:10,090 apa pun pengguna diketik masuk 215 00:09:10,090 --> 00:09:12,180 Dan jika mereka mengetik satu, aku akan panggil delete dan istirahat. 216 00:09:12,180 --> 00:09:14,380 Jika mereka mengetik dua, aku akan panggilan menyisipkan dan istirahat. 217 00:09:14,380 --> 00:09:16,490 >> Dan sekarang perhatikan saya menempatkan masing-masing ini pada baris yang sama. 218 00:09:16,490 --> 00:09:18,360 Ini hanya keputusan gaya. 219 00:09:18,360 --> 00:09:20,210 Biasanya kita telah melihat sesuatu seperti ini. 220 00:09:20,210 --> 00:09:23,260 Tapi aku hanya memutuskan, terus terang, program saya tampak lebih mudah dibaca karena 221 00:09:23,260 --> 00:09:25,980 itu hanya empat kasus untuk hanya daftar seperti ini. 222 00:09:25,980 --> 00:09:28,360 Penggunaan benar-benar sah gaya. 223 00:09:28,360 --> 00:09:31,480 Dan aku akan melakukan hal ini asalkan pengguna belum diketik nol, yang saya 224 00:09:31,480 --> 00:09:33,910 memutuskan akan berarti mereka ingin berhenti. 225 00:09:33,910 --> 00:09:36,630 >> Jadi sekarang perhatikan apa yang saya akan dilakukan di sini. 226 00:09:36,630 --> 00:09:38,650 Aku akan membebaskan daftar rupanya. 227 00:09:38,650 --> 00:09:40,230 Tapi lebih pada bahwa hanya dalam beberapa saat. 228 00:09:40,230 --> 00:09:41,640 Mari kita pertama kali menjalankan program ini. 229 00:09:41,640 --> 00:09:45,250 Jadi biarkan aku membuat terminal besar window, dot daftar slash 0. 230 00:09:45,250 --> 00:09:49,510 Aku akan pergi ke depan dan masukkan oleh mengetik dua, nomor seperti 50, dan sekarang 231 00:09:49,510 --> 00:09:51,590 Anda akan melihat daftar sekarang 50. 232 00:09:51,590 --> 00:09:53,380 Dan teks saya hanya menggulir sedikit. 233 00:09:53,380 --> 00:09:55,940 Jadi sekarang melihat daftar berisi nomor 50. 234 00:09:55,940 --> 00:09:58,220 >> Mari kita melakukan insert lain dengan mengambil dua. 235 00:09:58,220 --> 00:10:01,630 Mari kita mengetikkan nomor seperti satu. 236 00:10:01,630 --> 00:10:03,940 Daftar sekarang salah satu, diikuti oleh 50. 237 00:10:03,940 --> 00:10:06,020 Jadi ini hanyalah sebuah representasi tekstual daftar. 238 00:10:06,020 --> 00:10:10,550 Dan mari kita masukkan nomor satu lebih seperti nomor 42, yang mudah-mudahan 239 00:10:10,550 --> 00:10:14,620 akan berakhir di tengah, karena Program ini macam tertentu itu 240 00:10:14,620 --> 00:10:16,320 elemen seperti memasukkan mereka. 241 00:10:16,320 --> 00:10:17,220 Jadi ada yang kita miliki. 242 00:10:17,220 --> 00:10:20,730 Program super sederhana yang bisa benar-benar telah menggunakan sebuah array, tapi saya 243 00:10:20,730 --> 00:10:23,280 kebetulan menggunakan linked list supaya saya bisa secara dinamis 244 00:10:23,280 --> 00:10:24,610 tumbuh dan menyusut itu. 245 00:10:24,610 --> 00:10:28,470 >> Jadi mari kita lihat untuk pencarian, jika saya menjalankan perintah tiga, saya ingin mencari 246 00:10:28,470 --> 00:10:31,040 untuk, misalnya, jumlah 43. 247 00:10:31,040 --> 00:10:34,190 Dan tidak ada yang tampaknya ditemukan, karena aku kembali tidak ada jawaban. 248 00:10:34,190 --> 00:10:35,010 Jadi mari kita lakukan ini lagi. 249 00:10:35,010 --> 00:10:35,690 Cari. 250 00:10:35,690 --> 00:10:39,520 Mari kita mencari 50, atau lebih tepatnya mencari untuk 42, yang memiliki bagus 251 00:10:39,520 --> 00:10:40,850 sedikit makna halus. 252 00:10:40,850 --> 00:10:42,610 Dan aku menemukan makna kehidupan di sana. 253 00:10:42,610 --> 00:10:44,990 Nomor 42, jika Anda tidak tahu referensi, Google itu. 254 00:10:44,990 --> 00:10:45,350 Baik. 255 00:10:45,350 --> 00:10:47,130 Jadi apa yang telah dilakukan program ini untuk saya? 256 00:10:47,130 --> 00:10:50,660 Itu hanya memungkinkan saya untuk memasukkan sehingga jauh dan mencari elemen. 257 00:10:50,660 --> 00:10:53,650 >> Mari kita cepat maju, kemudian, untuk fungsi yang kita melirik 258 00:10:53,650 --> 00:10:55,360 Senin sebagai teaser. 259 00:10:55,360 --> 00:10:59,620 Jadi fungsi ini, saya menyatakan, mencari elemen dalam daftar dengan pertama 260 00:10:59,620 --> 00:11:03,830 satu, mendorong pengguna dan kemudian memanggil GetInt untuk mendapatkan int aktual 261 00:11:03,830 --> 00:11:05,060 bahwa Anda ingin mencari. 262 00:11:05,060 --> 00:11:06,460 >> Kemudian melihat ini. 263 00:11:06,460 --> 00:11:10,690 Aku akan membuat variabel sementara sejalan 188 disebut pointer - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 bisa disebut apa-apa. 266 00:11:12,440 --> 00:11:16,140 Dan itu pointer ke node karena aku bilang simpul * sana. 267 00:11:16,140 --> 00:11:19,900 Dan aku memulainya untuk menjadi sama dengan pertama sehingga saya efektif punya saya 268 00:11:19,900 --> 00:11:22,860 jari, sehingga untuk berbicara, di bagian paling elemen pertama dari daftar. 269 00:11:22,860 --> 00:11:27,460 Jadi, jika tangan kanan saya di sini adalah PTR aku menunjuk pada hal yang sama yang pertama 270 00:11:27,460 --> 00:11:28,670 adalah menunjuk. 271 00:11:28,670 --> 00:11:31,430 >> Jadi sekarang kembali dalam kode, apa yang terjadi berikutnya - 272 00:11:31,430 --> 00:11:35,070 ini adalah paradigma umum ketika iterasi atas struktur seperti 273 00:11:35,070 --> 00:11:35,970 linked list. 274 00:11:35,970 --> 00:11:40,410 Aku akan lakukan hal berikut saat pointer tidak sama dengan null Jadi sementara 275 00:11:40,410 --> 00:11:47,530 jari saya tidak menunjuk pada beberapa nol nilai, jika pointer panah n sama n. 276 00:11:47,530 --> 00:11:52,290 Kita akan melihat pertama bahwa n adalah apa yang pengguna mengetik per GetInts panggilan di sini. 277 00:11:52,290 --> 00:11:54,280 >> Dan pointer panah n berarti apa? 278 00:11:54,280 --> 00:11:59,020 Nah jika kita kembali ke gambar di sini, jika saya memiliki jari menunjuk 279 00:11:59,020 --> 00:12:02,960 bahwa node pertama yang berisi sembilan, yang panah dasarnya berarti pergi ke 280 00:12:02,960 --> 00:12:08,860 simpul dan ambil nilai di lokasi n, dalam hal ini, data lapangan yang disebut n. 281 00:12:08,860 --> 00:12:14,120 >> Sebagai samping - dan kami melihat ini pasangan minggu lalu ketika seseorang bertanya - 282 00:12:14,120 --> 00:12:18,840 sintaks ini adalah baru, tetapi tidak memberi kita kekuatan yang kita 283 00:12:18,840 --> 00:12:20,040 tidak sudah memiliki. 284 00:12:20,040 --> 00:12:25,325 Apa kalimat ini setara dengan menggunakan dot notasi dan bintang pasangan 285 00:12:25,325 --> 00:12:29,490 minggu lalu ketika kita kupas kembali lapisan ini sedikit prematur? 286 00:12:29,490 --> 00:12:31,780 >> SISWA: [Tak terdengar]. 287 00:12:31,780 --> 00:12:38,880 >> SPEAKER 1: Tepat, itu adalah bintang, dan maka itu star dot n, dengan 288 00:12:38,880 --> 00:12:41,930 kurung di sini, yang terlihat, terus terang, saya pikir banyak 289 00:12:41,930 --> 00:12:43,320 lebih samar untuk membaca. 290 00:12:43,320 --> 00:12:46,270 Tapi bintang pointer, seperti biasa, berarti pergi ke sana. 291 00:12:46,270 --> 00:12:49,090 Dan sekali Anda berada di sana, data apa bidang yang Anda ingin mengakses? 292 00:12:49,090 --> 00:12:52,730 Nah Anda menggunakan notasi titik untuk mengakses data lapangan structs, dan saya 293 00:12:52,730 --> 00:12:54,140 khusus ingin n. 294 00:12:54,140 --> 00:12:56,240 >> Terus terang, saya berpendapat ini hanya sulit untuk dibaca. 295 00:12:56,240 --> 00:12:58,080 Lebih sulit untuk mengingat di mana jangan tanda kurung pergi, yang 296 00:12:58,080 --> 00:12:59,030 bintang dan semua itu. 297 00:12:59,030 --> 00:13:02,150 Jadi dunia mengadopsi beberapa sintaksis gula, sehingga untuk berbicara. 298 00:13:02,150 --> 00:13:04,740 Hanya cara seksi mengatakan, ini setara, dan 299 00:13:04,740 --> 00:13:05,970 mungkin lebih intuitif. 300 00:13:05,970 --> 00:13:09,600 Jika pointer memang pointer, yang panah notasi cara pergi ke sana dan menemukan 301 00:13:09,600 --> 00:13:11,890 lapangan dalam hal ini disebut n. 302 00:13:11,890 --> 00:13:13,660 >> Jadi jika saya menemukan itu, perhatikan apa yang saya lakukan. 303 00:13:13,660 --> 00:13:17,430 Aku hanya mencetak, saya menemukan persen i, menghubungkannya dengan nilai int itu. 304 00:13:17,430 --> 00:13:20,730 Saya sebut tidur selama satu detik hanya untuk jenis hal jeda pada layar untuk 305 00:13:20,730 --> 00:13:22,900 memberikan pengguna kedua untuk menyerap apa yang baru saja terjadi. 306 00:13:22,900 --> 00:13:24,290 Dan kemudian saya istirahat. 307 00:13:24,290 --> 00:13:26,330 Jika tidak, apa yang harus saya lakukan? 308 00:13:26,330 --> 00:13:30,960 Saya update pointer ke sama pointer panah di sebelah. 309 00:13:30,960 --> 00:13:35,840 >> Jadi hanya harus jelas, ini berarti pergi ada, menggunakan notasi tua-sekolah saya. 310 00:13:35,840 --> 00:13:39,580 Jadi ini hanya berarti pergi ke apa Anda menunjuk, yang dalam sangat 311 00:13:39,580 --> 00:13:43,660 Kasus pertama adalah aku tunjuk struct dengan sembilan di dalamnya. 312 00:13:43,660 --> 00:13:44,510 Jadi aku sudah ada. 313 00:13:44,510 --> 00:13:47,880 Dan kemudian notasi titik berarti, mendapatkan nilai di depan. 314 00:13:47,880 --> 00:13:50,470 >> Tapi nilai, meskipun itu ditarik sebagai sempit, hanya nomor. 315 00:13:50,470 --> 00:13:51,720 Ini adalah alamat numerik. 316 00:13:51,720 --> 00:13:55,670 Jadi satu baris kode ini, apakah ditulis seperti ini, lebih samar 317 00:13:55,670 --> 00:14:00,190 cara, atau seperti ini, sedikit lebih cara intuitif, hanya berarti menggerakkan tanganku 318 00:14:00,190 --> 00:14:03,460 dari simpul pertama ke yang berikutnya, dan kemudian yang berikutnya, dan kemudian 319 00:14:03,460 --> 00:14:05,320 yang berikutnya, dan sebagainya. 320 00:14:05,320 --> 00:14:09,920 >> Jadi kita tidak akan diam di sisi lain implementasi menyisipkan dan menghapus 321 00:14:09,920 --> 00:14:14,030 dan traversal, dua pertama dari yang cukup terlibat. 322 00:14:14,030 --> 00:14:17,010 Dan saya pikir itu cukup mudah untuk mendapatkan hilang ketika melakukan secara lisan. 323 00:14:17,010 --> 00:14:19,890 Tapi apa yang bisa kita lakukan di sini adalah mencoba untuk menentukan bagaimana 324 00:14:19,890 --> 00:14:21,640 terbaik untuk melakukan ini secara visual. 325 00:14:21,640 --> 00:14:24,800 Karena saya akan mengusulkan bahwa jika kita ingin memasukkan unsur-unsur ke dalam 326 00:14:24,800 --> 00:14:26,680 daftar yang ada, yang memiliki lima unsur - 327 00:14:26,680 --> 00:14:29,530 9, 17, 22, 26, dan 33 - 328 00:14:29,530 --> 00:14:33,300 jika saya akan menerapkan ini dalam kode, saya harus mempertimbangkan bagaimana untuk pergi 329 00:14:33,300 --> 00:14:34,160 melakukan hal ini. 330 00:14:34,160 --> 00:14:37,720 >> Dan saya akan mengusulkan mengambil langkah-langkah bayi dimana, dalam hal ini maksud saya, apa yang 331 00:14:37,720 --> 00:14:41,090 skenario yang mungkin bahwa kita mungkin menghadapi secara umum? 332 00:14:41,090 --> 00:14:44,120 Ketika menerapkan insert untuk linked daftar, ini hanya terjadi menjadi 333 00:14:44,120 --> 00:14:46,090 Contoh spesifik ukuran lima. 334 00:14:46,090 --> 00:14:50,420 Nah jika Anda ingin menyisipkan angka, seperti mengatakan nomor satu, dan 335 00:14:50,420 --> 00:14:53,380 menjaga ketertiban diurutkan, di mana jelas apakah nomor satu perlu 336 00:14:53,380 --> 00:14:55,686 pergi dalam contoh khusus ini? 337 00:14:55,686 --> 00:14:56,840 Seperti di awal. 338 00:14:56,840 --> 00:15:00,030 >> Tapi apa yang menarik di sana adalah bahwa jika Anda ingin memasukkan satu ke ini 339 00:15:00,030 --> 00:15:04,100 Daftar, apa pointer kebutuhan khusus harus diperbarui rupanya? 340 00:15:04,100 --> 00:15:04,610 Pertama. 341 00:15:04,610 --> 00:15:07,830 Jadi saya berpendapat, ini adalah kasus pertama bahwa kita mungkin ingin mempertimbangkan, sebuah 342 00:15:07,830 --> 00:15:11,140 Skenario yang melibatkan memasukkan di awal daftar. 343 00:15:11,140 --> 00:15:15,400 >> Mari kita merobek mungkin sebuah semudah atau bahkan kasus mudah, relatif berbicara. 344 00:15:15,400 --> 00:15:18,110 Misalkan saya ingin memasukkan nomor 35 dalam rangka diurutkan. 345 00:15:18,110 --> 00:15:20,600 Ini jelas milik sana. 346 00:15:20,600 --> 00:15:25,320 Jadi apa pointer jelas akan harus diperbarui dalam skenario itu? 347 00:15:25,320 --> 00:15:30,060 34 's pointer menjadi tidak null tapi alamat struct 348 00:15:30,060 --> 00:15:31,800 berisi nomor 35. 349 00:15:31,800 --> 00:15:32,750 Jadi itu yang terjadi dua. 350 00:15:32,750 --> 00:15:36,190 Jadi sudah, aku agak mengkuantisasi berapa banyak pekerjaan yang harus saya lakukan di sini. 351 00:15:36,190 --> 00:15:39,880 >> Dan akhirnya, kasus tengah jelas adalah memang, di tengah, jika saya ingin 352 00:15:39,880 --> 00:15:45,870 memasukkan sesuatu seperti mengatakan 23, yang berlangsung antara 23 dan 26, tetapi 353 00:15:45,870 --> 00:15:48,680 sekarang hal mendapatkan sedikit lebih terlibat karena apa 354 00:15:48,680 --> 00:15:52,800 pointer perlu diubah? 355 00:15:52,800 --> 00:15:56,680 Jadi 22 jelas perlu diubah karena ia tidak dapat menunjukkan 26 lagi. 356 00:15:56,680 --> 00:16:00,320 Dia perlu untuk menunjuk ke simpul baru yang Aku harus mengalokasikan dengan menelepon 357 00:16:00,320 --> 00:16:01,770 malloc atau setara. 358 00:16:01,770 --> 00:16:05,990 >> Tapi kemudian saya juga membutuhkan node baru, 23 dalam hal ini, memiliki pointer 359 00:16:05,990 --> 00:16:07,870 menunjuk siapa? 360 00:16:07,870 --> 00:16:08,560 26. 361 00:16:08,560 --> 00:16:10,380 Dan ada akan menjadi urutan operasi di sini. 362 00:16:10,380 --> 00:16:13,410 Karena jika aku melakukan ini bodoh, dan saya misalnya mulai dari awal 363 00:16:13,410 --> 00:16:16,040 daftar, dan tujuan saya adalah untuk memasukkan 23. 364 00:16:16,040 --> 00:16:18,610 Dan saya cek, itu milik di sini, di dekat sembilan? 365 00:16:18,610 --> 00:16:18,950 Tidak. 366 00:16:18,950 --> 00:16:20,670 Apakah itu termasuk di sini, di samping 17? 367 00:16:20,670 --> 00:16:20,940 Tidak. 368 00:16:20,940 --> 00:16:22,530 Apakah itu milik di sini di samping 22? 369 00:16:22,530 --> 00:16:23,300 Ya. 370 00:16:23,300 --> 00:16:26,400 >> Sekarang jika saya bodoh di sini, dan tidak berpikir ini melalui, aku mungkin 371 00:16:26,400 --> 00:16:28,320 mengalokasikan node baru saya untuk 23. 372 00:16:28,320 --> 00:16:32,080 Aku mungkin memperbarui pointer dari node disebut 22, menunjuk 373 00:16:32,080 --> 00:16:33,080 itu pada node baru. 374 00:16:33,080 --> 00:16:36,140 Lalu apa yang harus saya harus memperbarui pointer node baru untuk menjadi? 375 00:16:36,140 --> 00:16:38,120 >> SISWA: [Tak terdengar]. 376 00:16:38,120 --> 00:16:38,385 >> SPEAKER 1: Tepat. 377 00:16:38,385 --> 00:16:39,710 Sambil menunjuk 26. 378 00:16:39,710 --> 00:16:45,590 Tapi sialan jika aku tidak sudah memperbarui 22 itu pointer untuk menunjuk pada orang ini, dan 379 00:16:45,590 --> 00:16:48,260 sekarang aku punya anak yatim, sisanya dari daftar, sehingga untuk berbicara. 380 00:16:48,260 --> 00:16:52,140 Jadi urutan operasi di sini akan menjadi penting. 381 00:16:52,140 --> 00:16:55,100 >> Untuk melakukan hal ini bisa saya mencuri, mengatakan, enam sukarelawan. 382 00:16:55,100 --> 00:16:57,650 Dan mari kita lihat apakah kita tidak bisa melakukan ini visual bukan kode-bijaksana. 383 00:16:57,650 --> 00:16:59,330 Dan kami memiliki beberapa stres yang indah bola untuk Anda hari ini. 384 00:16:59,330 --> 00:17:02,510 OK, bagaimana kalau satu, dua, dalam kembali - di ujung sana. 385 00:17:02,510 --> 00:17:04,530 tiga, empat, kalian berdua orang di ujungnya. 386 00:17:04,530 --> 00:17:05,579 Dan lima, enam. 387 00:17:05,579 --> 00:17:05,839 Tentu. 388 00:17:05,839 --> 00:17:06,450 Lima dan enam. 389 00:17:06,450 --> 00:17:08,390 Semua benar dan kami akan datang untuk kalian waktu berikutnya. 390 00:17:08,390 --> 00:17:09,640 Baiklah, ayo bangun. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Baiklah, karena kau di sini pertama, Anda ingin menjadi orang yang canggung 393 00:17:14,819 --> 00:17:16,119 di Google Kaca sini? 394 00:17:16,119 --> 00:17:19,075 Baiklah, jadi, OK, Kaca, merekam video. 395 00:17:19,075 --> 00:17:22,720 396 00:17:22,720 --> 00:17:24,589 OK, Anda baik untuk pergi. 397 00:17:24,589 --> 00:17:27,950 >> Baiklah, jadi jika kalian bisa datang di sini, saya telah dipersiapkan sebelumnya 398 00:17:27,950 --> 00:17:30,110 beberapa angka. 399 00:17:30,110 --> 00:17:31,240 Baiklah, ayo ke sini. 400 00:17:31,240 --> 00:17:33,440 Dan kenapa tidak Anda pergi sedikit lanjut seperti itu. 401 00:17:33,440 --> 00:17:35,520 Dan mari kita lihat, siapa namamu, dengan Google Glass? 402 00:17:35,520 --> 00:17:35,910 >> SISWA: Ben. 403 00:17:35,910 --> 00:17:36,230 >> SPEAKER 1: Ben? 404 00:17:36,230 --> 00:17:38,380 OK, Ben, Anda akan menjadi yang pertama, secara harfiah. 405 00:17:38,380 --> 00:17:40,580 Jadi kita akan mengirim Anda ke ujung panggung. 406 00:17:40,580 --> 00:17:41,670 Baiklah, dan nama Anda? 407 00:17:41,670 --> 00:17:41,990 >> SISWA: Jason. 408 00:17:41,990 --> 00:17:44,530 >> SPEAKER 1: Jason, Anda akan OK menjadi nomor sembilan. 409 00:17:44,530 --> 00:17:46,700 Jadi jika Anda ingin mengikuti Ben seperti itu. 410 00:17:46,700 --> 00:17:47,010 >> SISWA: Jill. 411 00:17:47,010 --> 00:17:49,630 >> SPEAKER 1: Jill, Anda akan menjadi 17, yang jika aku melakukan ini lebih 412 00:17:49,630 --> 00:17:51,260 cerdas, aku akan dimulai di ujung lain. 413 00:17:51,260 --> 00:17:52,370 Anda pergi ke arah sana. 414 00:17:52,370 --> 00:17:53,030 22. 415 00:17:53,030 --> 00:17:53,670 Dan Anda? 416 00:17:53,670 --> 00:17:53,980 >> SISWA: Mary. 417 00:17:53,980 --> 00:17:56,130 >> SPEAKER 1: Mary, Anda akan 22. 418 00:17:56,130 --> 00:17:58,420 Dan nama Anda? 419 00:17:58,420 --> 00:17:58,810 >> SISWA: Chris. 420 00:17:58,810 --> 00:18:00,100 >> SPEAKER 1: Chris, Anda akan 26. 421 00:18:00,100 --> 00:18:00,740 Dan kemudian terakhir. 422 00:18:00,740 --> 00:18:01,400 >> SISWA: Diana. 423 00:18:01,400 --> 00:18:02,670 >> SPEAKER 1: Diana, Anda akan 34. 424 00:18:02,670 --> 00:18:03,920 Jadi kau datang ke sini. 425 00:18:03,920 --> 00:18:06,360 >> Baiklah, jadi sempurna diurutkan memesan sudah. 426 00:18:06,360 --> 00:18:09,600 Dan mari kita pergi ke depan dan melakukan hal ini sehingga kita benar-benar bisa - 427 00:18:09,600 --> 00:18:11,720 Ben Anda hanya semacam mencari keluar ke mana-mana ada. 428 00:18:11,720 --> 00:18:15,670 OK, jadi mari kita pergi ke depan dan menggambarkan ini menggunakan senjata, seperti aku, tepatnya, 429 00:18:15,670 --> 00:18:16,250 apa yang terjadi. 430 00:18:16,250 --> 00:18:19,540 Jadi pergi ke depan dan memberi dirimu kaki atau dua antara dirimu. 431 00:18:19,540 --> 00:18:22,900 Dan pergi ke depan dan menunjuk dengan satu tangan untuk siapapun Anda harus menunjuk 432 00:18:22,900 --> 00:18:23,470 berdasarkan ini. 433 00:18:23,470 --> 00:18:25,890 Dan jika Anda hanya menunjukkan nol lurus ke bawah ke lantai. 434 00:18:25,890 --> 00:18:27,690 OK, jadi baik. 435 00:18:27,690 --> 00:18:32,290 >> Jadi sekarang kita memiliki sebuah linked list, dan biarkan aku mengusulkan bahwa saya akan memainkan peran 436 00:18:32,290 --> 00:18:35,110 PTR, jadi saya tidak akan repot-repot membawa ini sekitar. 437 00:18:35,110 --> 00:18:37,830 Dan kemudian - seseorang konvensi bodoh - Anda dapat memanggil apa ini yang Anda inginkan - 438 00:18:37,830 --> 00:18:39,800 pendahulunya pointer, pointer pred - 439 00:18:39,800 --> 00:18:43,930 itu hanya julukan kami berikan kode sampel kami ke tangan kiri saya. 440 00:18:43,930 --> 00:18:47,240 Sisi lain yang akan menjaga melacak siapa yang di 441 00:18:47,240 --> 00:18:48,400 mengikuti skenario. 442 00:18:48,400 --> 00:18:52,390 >> Jadi misalkan, pertama, saya ingin merobek bahwa contoh pertama memasukkan, katakanlah 443 00:18:52,390 --> 00:18:54,330 20, ke dalam daftar. 444 00:18:54,330 --> 00:18:57,160 Jadi aku akan membutuhkan seseorang untuk mewujudkan nomor 20 bagi kita. 445 00:18:57,160 --> 00:18:58,950 Jadi saya harus malloc seseorang dari penonton. 446 00:18:58,950 --> 00:18:59,380 Ayo up. 447 00:18:59,380 --> 00:19:00,340 Siapa nama Anda? 448 00:19:00,340 --> 00:19:01,300 >> SISWA: Brian. 449 00:19:01,300 --> 00:19:05,270 >> SPEAKER 1: Brian, baiklah, sehingga Anda akan menjadi node yang berisi 20. 450 00:19:05,270 --> 00:19:06,810 Baiklah, ayo ke sini. 451 00:19:06,810 --> 00:19:10,025 Dan jelas, mana apakah Brian milik? 452 00:19:10,025 --> 00:19:12,190 Jadi, di tengah - sebenarnya, tunggu sebentar. 453 00:19:12,190 --> 00:19:13,420 Kami melakukan ini rusak. 454 00:19:13,420 --> 00:19:17,170 Kami membuat ini jauh lebih sulit daripada harus pada awalnya. 455 00:19:17,170 --> 00:19:21,210 OK, kita akan bebas Brian dan realloc Brian lima. 456 00:19:21,210 --> 00:19:23,680 >> OK, jadi sekarang kita ingin menyisipkan Brian lima. 457 00:19:23,680 --> 00:19:25,960 Jadi datang ke sini di samping Ben untuk sesaat. 458 00:19:25,960 --> 00:19:28,250 Dan Anda mungkin dapat memberitahu dimana kisah ini terjadi. 459 00:19:28,250 --> 00:19:30,500 Tapi mari berpikir hati-hati tentang urutan operasi. 460 00:19:30,500 --> 00:19:32,880 Dan itu justru visual ini itu akan berbaris 461 00:19:32,880 --> 00:19:34,080 dengan kode contoh. 462 00:19:34,080 --> 00:19:40,120 Jadi di sini saya telah PTR menunjuk awalnya tidak pada Ben, per se, tetapi pada apa pun 463 00:19:40,120 --> 00:19:43,245 menghargai dia mengandung, yang dalam hal ini adalah - siapa namamu lagi? 464 00:19:43,245 --> 00:19:43,670 >> SISWA: Jason. 465 00:19:43,670 --> 00:19:47,350 >> SPEAKER 1: Jason, sehingga kedua aku dan Ben menunjuk Jason saat ini. 466 00:19:47,350 --> 00:19:49,700 Jadi sekarang aku harus menentukan, dari mana Brian milik? 467 00:19:49,700 --> 00:19:53,500 Jadi satu-satunya hal yang saya memiliki akses ke sekarang adalah n item data nya. 468 00:19:53,500 --> 00:19:58,280 Jadi aku akan memeriksa, adalah Brian kurang dari Jason? 469 00:19:58,280 --> 00:19:59,770 Jawabannya adalah benar. 470 00:19:59,770 --> 00:20:03,680 >> Jadi apa yang sekarang perlu terjadi, dalam urutan yang benar? 471 00:20:03,680 --> 00:20:07,120 Saya perlu memperbarui berapa banyak pointer secara total dalam cerita ini? 472 00:20:07,120 --> 00:20:10,720 Dimana tanganku masih menunjuk Jason, dan tangan Anda - jika Anda ingin 473 00:20:10,720 --> 00:20:12,930 meletakkan tangan Anda seperti, semacam, saya tidak tahu, tanda tanya. 474 00:20:12,930 --> 00:20:14,070 OK, baik. 475 00:20:14,070 --> 00:20:15,670 >> Baiklah, sehingga Anda memiliki beberapa calon. 476 00:20:15,670 --> 00:20:20,500 Baik Ben maupun I atau Brian atau Jason atau orang lain, yang 477 00:20:20,500 --> 00:20:21,370 pointer perlu berubah? 478 00:20:21,370 --> 00:20:23,260 Berapa banyak total? 479 00:20:23,260 --> 00:20:24,080 >> OK, jadi dua. 480 00:20:24,080 --> 00:20:27,090 Pointer saya tidak benar-benar peduli lagi karena aku hanya sementara. 481 00:20:27,090 --> 00:20:31,370 Jadi dua orang, mungkin, kedua Ben dan Brian. 482 00:20:31,370 --> 00:20:34,410 Jadi biarkan saya mengusulkan agar kita memperbarui Ben, karena ia yang pertama. 483 00:20:34,410 --> 00:20:36,350 Elemen pertama dari daftar ini sekarang akan menjadi Brian. 484 00:20:36,350 --> 00:20:38,070 Jadi Ben titik di Brian. 485 00:20:38,070 --> 00:20:39,320 OK, sekarang apa? 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Siapa yang akan menunjuk siapa? 488 00:20:43,460 --> 00:20:44,710 >> SISWA: [Tak terdengar]. 489 00:20:44,710 --> 00:20:46,180 >> SPEAKER 1: OK jadi Brian memiliki untuk menunjuk Jason. 490 00:20:46,180 --> 00:20:48,360 Tapi apakah saya kehilangan jejak pointer itu? 491 00:20:48,360 --> 00:20:49,980 Apakah saya tahu di mana Jason? 492 00:20:49,980 --> 00:20:50,790 >> SISWA: [Tak terdengar]. 493 00:20:50,790 --> 00:20:52,620 >> SPEAKER 1: saya lakukan, karena aku pointer sementara. 494 00:20:52,620 --> 00:20:55,110 Dan mungkin, saya belum berubah untuk menunjuk pada simpul baru. 495 00:20:55,110 --> 00:20:58,300 Jadi kita hanya dapat memiliki Brian titik pada siapa aku tunjuk. 496 00:20:58,300 --> 00:20:59,000 Dan kita sudah selesai. 497 00:20:59,000 --> 00:21:01,890 Jadi satu kasus, penyisipan di awal daftar. 498 00:21:01,890 --> 00:21:02,950 Ada dua langkah kunci. 499 00:21:02,950 --> 00:21:06,750 Satu, kita harus memperbarui Ben, dan kemudian kita juga harus memperbarui Brian. 500 00:21:06,750 --> 00:21:09,230 Dan kemudian aku tidak perlu repot-repot traipsing melalui sisa 501 00:21:09,230 --> 00:21:12,680 daftar, karena kita sudah menemukan nya lokasi, karena dia milik 502 00:21:12,680 --> 00:21:14,080 kiri dari elemen pertama. 503 00:21:14,080 --> 00:21:15,400 >> Baiklah, jadi cukup sederhana. 504 00:21:15,400 --> 00:21:18,110 Bahkan, rasanya kita sudah hampir membuat ini terlalu rumit. 505 00:21:18,110 --> 00:21:20,240 Jadi mari kita merobek akhir daftar, dan melihat di mana 506 00:21:20,240 --> 00:21:21,380 kompleksitas dimulai. 507 00:21:21,380 --> 00:21:24,560 Jadi kalau sekarang, aku alokasi dari penonton. 508 00:21:24,560 --> 00:21:25,540 Siapapun ingin bermain 55? 509 00:21:25,540 --> 00:21:26,700 Baiklah, saya melihat tangan Anda terlebih dahulu. 510 00:21:26,700 --> 00:21:29,620 Ayo up. 511 00:21:29,620 --> 00:21:30,030 Ya. 512 00:21:30,030 --> 00:21:31,177 Siapa nama Anda? 513 00:21:31,177 --> 00:21:32,310 >> SISWA: [Tak terdengar]. 514 00:21:32,310 --> 00:21:33,240 >> SPEAKER 1: Habata. 515 00:21:33,240 --> 00:21:33,890 OK, datang ke atas. 516 00:21:33,890 --> 00:21:35,730 Anda akan menjadi nomor 55. 517 00:21:35,730 --> 00:21:37,820 Jadi Anda, tentu saja, termasuk pada akhir daftar. 518 00:21:37,820 --> 00:21:41,850 Jadi mari kita memutar ulang simulasi dengan saya menjadi PTR untuk sesaat. 519 00:21:41,850 --> 00:21:44,050 Jadi aku pertama akan menunjuk pada apapun Ben menunjuk. 520 00:21:44,050 --> 00:21:45,900 Kami berdua menunjuk sekarang di Brian. 521 00:21:45,900 --> 00:21:48,420 Jadi 55 adalah tidak kurang dari lima. 522 00:21:48,420 --> 00:21:52,510 Jadi aku akan memperbarui diri dengan menunjuk ke pointer berikutnya Brian, yang 523 00:21:52,510 --> 00:21:54,450 sekarang tentu saja Jason. 524 00:21:54,450 --> 00:21:57,310 55 tidak kurang dari sembilan, sehingga Aku akan memperbarui PTR. 525 00:21:57,310 --> 00:21:58,890 Aku akan memperbarui PTR. 526 00:21:58,890 --> 00:22:02,290 Aku akan memperbarui PTR Aku akan memperbarui PTR. 527 00:22:02,290 --> 00:22:05,060 Dan aku akan - hmm, apa Nama Anda lagi? 528 00:22:05,060 --> 00:22:05,560 >> SISWA: Diana. 529 00:22:05,560 --> 00:22:09,190 >> SPEAKER 1: Diana menunjuk, tentu saja, di nol dengan tangan kirinya. 530 00:22:09,190 --> 00:22:13,030 Jadi bagaimana sebenarnya Habata milik jelas? 531 00:22:13,030 --> 00:22:15,050 Di sebelah kiri, di sini. 532 00:22:15,050 --> 00:22:19,460 Jadi bagaimana saya tahu untuk menempatkan dia di Sini Saya pikir saya sudah kacau. 533 00:22:19,460 --> 00:22:22,420 Karena apa yang PTR seni saat ini dalam waktu? 534 00:22:22,420 --> 00:22:23,240 Null. 535 00:22:23,240 --> 00:22:25,580 Jadi meskipun, secara visual, kita bisa jelas melihat semua ini 536 00:22:25,580 --> 00:22:26,610 orang di sini di atas panggung. 537 00:22:26,610 --> 00:22:29,680 Aku sudah tidak terus melacak sebelumnya orang dalam daftar. 538 00:22:29,680 --> 00:22:33,210 Saya tidak memiliki jari menunjuk keluar, dalam hal ini, node nomor 34. 539 00:22:33,210 --> 00:22:34,760 >> Jadi mari kita benar-benar mulai selama ini. 540 00:22:34,760 --> 00:22:37,560 Jadi sekarang aku benar-benar perlu sebuah variabel lokal kedua. 541 00:22:37,560 --> 00:22:40,980 Dan ini adalah apa yang akan Anda lihat di sebenarnya contoh kode C, di mana saat aku pergi, 542 00:22:40,980 --> 00:22:45,860 ketika saya memperbarui tangan kananku ke titik Jason, sehingga meninggalkan Brian belakang, saya 543 00:22:45,860 --> 00:22:51,440 sebaiknya mulai menggunakan tangan kiri saya untuk memperbarui mana aku berada, sehingga saat aku pergi 544 00:22:51,440 --> 00:22:52,700 melalui daftar ini - 545 00:22:52,700 --> 00:22:55,040 lebih canggung daripada aku berniat sekarang di sini visual - 546 00:22:55,040 --> 00:22:56,740 Aku akan sampai ke akhir daftar. 547 00:22:56,740 --> 00:23:00,020 >> Tangan ini masih nol, yang cukup berguna, selain untuk menunjukkan 548 00:23:00,020 --> 00:23:02,980 Aku jelas di akhir daftar, tapi sekarang setidaknya aku punya ini 549 00:23:02,980 --> 00:23:08,270 pendahulunya pointer menunjuk sini, jadi sekarang apa tangan dan apa yang perlu pointer 550 00:23:08,270 --> 00:23:10,150 harus diperbarui? 551 00:23:10,150 --> 00:23:13,214 Tangan siapa yang Anda inginkan untuk mengkonfigurasi ulang pertama? 552 00:23:13,214 --> 00:23:15,190 >> SISWA: [Tak terdengar]. 553 00:23:15,190 --> 00:23:16,220 >> SPEAKER 1: OK, jadi Diana. 554 00:23:16,220 --> 00:23:21,110 Di mana Anda ingin menunjukkan Pointer kiri Diana di? 555 00:23:21,110 --> 00:23:23,620 Pada 55, mungkin, sehingga kami telah dimasukkan di sana. 556 00:23:23,620 --> 00:23:25,560 Dan di mana harus 55 pointer pergi? 557 00:23:25,560 --> 00:23:27,000 Bawah, mewakili nol. 558 00:23:27,000 --> 00:23:28,890 Dan tangan saya, pada saat ini, jangan penting karena mereka hanya 559 00:23:28,890 --> 00:23:30,070 variabel sementara. 560 00:23:30,070 --> 00:23:31,030 Jadi sekarang kita sudah selesai. 561 00:23:31,030 --> 00:23:34,650 >> Jadi kompleksitas tambahan di sana - dan itu tidak sulit untuk melaksanakan, 562 00:23:34,650 --> 00:23:38,660 tetapi kita perlu variabel sekunder untuk membuat Pastikan bahwa sebelum aku pindah kananku 563 00:23:38,660 --> 00:23:42,140 tangan, aku memperbarui nilai kiriku tangan, pointer pred dalam kasus ini, sehingga 564 00:23:42,140 --> 00:23:45,860 bahwa saya memiliki pointer membuntuti untuk melacak di mana aku berada. 565 00:23:45,860 --> 00:23:49,360 Sekarang sebagai samping, jika Anda berpikir ini melalui, ini terasa seperti itu 566 00:23:49,360 --> 00:23:51,490 sedikit menjengkelkan harus tetap melacak tangan kiri ini. 567 00:23:51,490 --> 00:23:54,015 >> Apa yang akan solusi lain untuk masalah ini telah? 568 00:23:54,015 --> 00:23:56,500 Jika Anda harus mendesain ulang data struktur kita berbicara 569 00:23:56,500 --> 00:23:59,630 melalui sekarang? 570 00:23:59,630 --> 00:24:02,690 Jika ini jenis hanya dari terasa sedikit mengganggu untuk memiliki, seperti, dua pointer 571 00:24:02,690 --> 00:24:08,430 akan melalui daftar, siapa lagi yang bisa telah, dalam dunia ideal, dipertahankan 572 00:24:08,430 --> 00:24:10,160 informasi yang kita butuhkan? 573 00:24:10,160 --> 00:24:11,360 Ya? 574 00:24:11,360 --> 00:24:12,610 >> SISWA: [Tak terdengar]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> SPEAKER 1: Tepat. 577 00:24:16,150 --> 00:24:19,130 Tepat sehingga sebenarnya ada yang menarik kuman dari sebuah ide. 578 00:24:19,130 --> 00:24:22,470 Dan ide ini dari sebuah pointer sebelumnya, menunjuk pada elemen sebelumnya. 579 00:24:22,470 --> 00:24:25,580 Bagaimana jika saya hanya diwujudkan bahwa dalam daftar itu sendiri? 580 00:24:25,580 --> 00:24:27,810 Dan itu akan menjadi sulit untuk memvisualisasikan ini tanpa semua kertas 581 00:24:27,810 --> 00:24:28,830 jatuh ke lantai. 582 00:24:28,830 --> 00:24:31,860 Tapi anggaplah bahwa orang-orang ini digunakan baik dari tangan mereka untuk memiliki sebelumnya 583 00:24:31,860 --> 00:24:35,950 pointer, dan pointer berikutnya, sehingga menerapkan apa yang akan kita sebut ganda 584 00:24:35,950 --> 00:24:36,830 linked list. 585 00:24:36,830 --> 00:24:41,090 Yang akan memungkinkan saya untuk semacam mundur, jauh lebih mudah tanpa saya, 586 00:24:41,090 --> 00:24:43,800 programmer, harus menjaga melacak secara manual - 587 00:24:43,800 --> 00:24:44,980 benar-benar secara manual - 588 00:24:44,980 --> 00:24:47,280 di mana saya telah sebelumnya dalam daftar. 589 00:24:47,280 --> 00:24:48,110 Jadi kita tidak akan melakukan itu. 590 00:24:48,110 --> 00:24:50,950 Kami akan tetap sederhana karena itulah akan datang pada harga, dua kali 591 00:24:50,950 --> 00:24:53,450 banyak ruang untuk pointer, jika Anda ingin yang kedua. 592 00:24:53,450 --> 00:24:55,760 Tapi itu memang umum struktur data yang dikenal sebagai 593 00:24:55,760 --> 00:24:57,410 daftar ganda terkait. 594 00:24:57,410 --> 00:25:01,310 >> Mari kita lakukan contoh terakhir di sini dan menaruh orang-orang ini keluar dari penderitaan mereka. 595 00:25:01,310 --> 00:25:03,270 Jadi malloc 20. 596 00:25:03,270 --> 00:25:05,320 Ayo naik dari lorong sana. 597 00:25:05,320 --> 00:25:06,280 Baiklah, siapa namamu? 598 00:25:06,280 --> 00:25:07,440 >> SISWA: [Tak terdengar]. 599 00:25:07,440 --> 00:25:07,855 >> SPEAKER 1: Maaf? 600 00:25:07,855 --> 00:25:08,480 >> SISWA: [Tak terdengar]. 601 00:25:08,480 --> 00:25:09,410 >> SPEAKER 1: Demeron? 602 00:25:09,410 --> 00:25:10,230 OK naiklah. 603 00:25:10,230 --> 00:25:11,910 Anda harus 20. 604 00:25:11,910 --> 00:25:14,720 Anda jelas akan milik antara 17 dan 22. 605 00:25:14,720 --> 00:25:16,150 Jadi biarkan aku belajar pelajaran saya. 606 00:25:16,150 --> 00:25:18,150 Aku akan memulai pointer menunjuk Brian. 607 00:25:18,150 --> 00:25:21,190 Dan aku akan memiliki tangan kiriku hanya update ke Brian saat aku pindah ke 608 00:25:21,190 --> 00:25:23,600 Jason, pemeriksaan tidak 20 kurang dari sembilan? 609 00:25:23,600 --> 00:25:24,060 Tidak. 610 00:25:24,060 --> 00:25:25,430 Adalah 20 kurang dari 17? 611 00:25:25,430 --> 00:25:25,880 Tidak. 612 00:25:25,880 --> 00:25:27,450 Adalah 20 kurang dari 22? 613 00:25:27,450 --> 00:25:28,440 Ya. 614 00:25:28,440 --> 00:25:34,070 Jadi apa pointer atau tangan perlu mengubah di mana mereka menunjuk sekarang? 615 00:25:34,070 --> 00:25:37,070 >> Jadi kita bisa melakukan 17 menunjuk pada 20. 616 00:25:37,070 --> 00:25:37,860 Jadi itu bagus. 617 00:25:37,860 --> 00:25:40,080 Di mana kami ingin menunjukkan pointer Anda sekarang? 618 00:25:40,080 --> 00:25:41,330 Pada 22. 619 00:25:41,330 --> 00:25:45,410 Dan kita tahu di mana 22 adalah, sekali lagi terima kasih untuk pointer sementara saya. 620 00:25:45,410 --> 00:25:46,760 Jadi kita OK ada. 621 00:25:46,760 --> 00:25:49,440 Jadi karena penyimpanan sementara ini Aku terus melacak di mana setiap orang. 622 00:25:49,440 --> 00:25:55,055 Dan sekarang Anda secara visual dapat pergi ke mana Anda milik, dan sekarang kami harus 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 bola stres, dan tepuk tangan untuk 624 00:25:58,410 --> 00:25:59,770 orang-orang ini, jika kita bisa. 625 00:25:59,770 --> 00:26:00,410 Baik dilakukan. 626 00:26:00,410 --> 00:26:05,320 >> [Tepuk Tangan] 627 00:26:05,320 --> 00:26:06,330 >> SPEAKER 1: Baiklah. 628 00:26:06,330 --> 00:26:09,860 Dan Anda dapat menyimpan potongan-potongan kertas sebagai kenang-kenangan. 629 00:26:09,860 --> 00:26:15,930 >> Baiklah, jadi, percayalah itu banyak mudah untuk berjalan melalui bahwa dengan 630 00:26:15,930 --> 00:26:17,680 manusia daripada dengan kode aktual. 631 00:26:17,680 --> 00:26:22,690 Tapi apa yang Anda akan menemukan hanya dalam beberapa saat sekarang, adalah bahwa sama - oh, terima kasih. 632 00:26:22,690 --> 00:26:23,630 Terima kasih - 633 00:26:23,630 --> 00:26:29,360 adalah bahwa Anda akan menemukan bahwa data yang sama struktur, linked list, dapat benar-benar 634 00:26:29,360 --> 00:26:33,200 digunakan sebagai blok bangunan untuk lebih struktur data yang canggih. 635 00:26:33,200 --> 00:26:37,620 >> Dan menyadari terlalu tema di sini adalah bahwa kita sudah benar-benar diperkenalkan lebih 636 00:26:37,620 --> 00:26:40,060 kompleksitas dalam pelaksanaan algoritma ini. 637 00:26:40,060 --> 00:26:43,940 Penyisipan, dan jika kami pergi melalui itu, penghapusan dan pencarian, sedikit 638 00:26:43,940 --> 00:26:46,660 lebih rumit daripada adalah dengan array. 639 00:26:46,660 --> 00:26:48,040 Tapi kita mendapatkan beberapa dinamisme. 640 00:26:48,040 --> 00:26:50,180 Kami mendapatkan struktur data adaptif. 641 00:26:50,180 --> 00:26:54,010 >> Tapi sekali lagi, kita membayar harga memiliki beberapa kompleksitas tambahan, baik dalam 642 00:26:54,010 --> 00:26:54,910 mengimplementasikannya. 643 00:26:54,910 --> 00:26:56,750 Dan kita diberi akses acak. 644 00:26:56,750 --> 00:27:00,450 Dan jujur, tidak ada beberapa nice membersihkan geser saya bisa memberikan Anda bahwa 645 00:27:00,450 --> 00:27:03,120 mengatakan di sini adalah mengapa sebuah linked list lebih baik dari array. 646 00:27:03,120 --> 00:27:04,100 Dan berhenti di situ. 647 00:27:04,100 --> 00:27:07,520 Karena tema reoccurring sekarang, bahkan lebih dalam beberapa minggu mendatang, adalah 648 00:27:07,520 --> 00:27:10,200 bahwa tidak ada tentu jawaban yang benar. 649 00:27:10,200 --> 00:27:13,830 >> Inilah sebabnya mengapa kita memiliki sumbu terpisah desain untuk set masalah. 650 00:27:13,830 --> 00:27:17,700 Ini akan sangat sensitif konteks apakah Anda ingin menggunakan data ini 651 00:27:17,700 --> 00:27:21,750 struktur atau yang satu, dan akan tergantung pada apa yang penting bagi Anda dalam hal 652 00:27:21,750 --> 00:27:24,620 sumber daya dan kompleksitas. 653 00:27:24,620 --> 00:27:28,830 >> Tapi biarkan aku mengusulkan bahwa data yang ideal struktur, grail suci, akan 654 00:27:28,830 --> 00:27:32,200 sesuatu yang waktu yang konstan, terlepas dari berapa banyak barang yang 655 00:27:32,200 --> 00:27:36,940 dalamnya, tidak akan menjadi luar biasa jika struktur data kembali jawaban dalam 656 00:27:36,940 --> 00:27:37,920 waktu yang konstan. 657 00:27:37,920 --> 00:27:38,330 Ya. 658 00:27:38,330 --> 00:27:40,110 Kata ini dalam kamus besar Anda. 659 00:27:40,110 --> 00:27:41,550 Atau tidak, kata ini tidak. 660 00:27:41,550 --> 00:27:43,270 Atau masalah tersebut ada. 661 00:27:43,270 --> 00:27:46,360 Nah mari kita lihat jika kita tidak bisa setidaknya mengambil langkah menuju itu. 662 00:27:46,360 --> 00:27:50,190 >> Mari saya mengusulkan struktur data baru yang dapat digunakan untuk hal yang berbeda, 663 00:27:50,190 --> 00:27:52,260 dalam hal ini disebut tabel hash. 664 00:27:52,260 --> 00:27:55,590 Dan jadi kita benar-benar kembali ke melirik pada array, dalam kasus ini, dan 665 00:27:55,590 --> 00:28:00,550 agak sewenang-wenang, saya sudah ditarik ini tabel hash sebagai array dengan semacam 666 00:28:00,550 --> 00:28:02,810 array dua dimensi - 667 00:28:02,810 --> 00:28:05,410 atau lebih tepatnya itu digambarkan di sini sebagai dua dimensi array - tapi ini hanya 668 00:28:05,410 --> 00:28:10,770 array ukuran 26, sehingga jika kita memanggil tabel array, tabel braket 669 00:28:10,770 --> 00:28:12,440 nol adalah persegi panjang di bagian atas. 670 00:28:12,440 --> 00:28:15,090 Tabel braket 25 adalah persegi panjang di bagian bawah. 671 00:28:15,090 --> 00:28:18,620 Dan ini adalah bagaimana saya bisa menggambar Data struktur di mana saya ingin menyimpan 672 00:28:18,620 --> 00:28:19,790 nama orang. 673 00:28:19,790 --> 00:28:24,370 >> Jadi misalnya, dan saya tidak akan menarik Semuanya di sini pada biaya overhead, jika saya 674 00:28:24,370 --> 00:28:29,160 memiliki array ini, yang aku sekarang akan memanggil tabel hash, dan ini lagi 675 00:28:29,160 --> 00:28:31,360 lokasi nol. 676 00:28:31,360 --> 00:28:34,840 Ini di sini adalah lokasi satu, dan sebagainya. 677 00:28:34,840 --> 00:28:37,880 Saya menyatakan bahwa saya ingin menggunakan data ini struktur, demi diskusi, 678 00:28:37,880 --> 00:28:42,600 untuk menyimpan nama orang, Alice dan Bob dan Charlie dan nama-nama seperti lainnya. 679 00:28:42,600 --> 00:28:46,110 Jadi pikirkan sekarang ini sebagai awal , katakanlah, kamus 680 00:28:46,110 --> 00:28:47,520 dengan banyak kata-kata. 681 00:28:47,520 --> 00:28:49,435 Mereka kebetulan nama dalam contoh kita di sini. 682 00:28:49,435 --> 00:28:52,560 Dan ini semua terlalu erat, mungkin, untuk menerapkan pemeriksa ejaan, seperti yang kita 683 00:28:52,560 --> 00:28:54,400 mungkin untuk masalah menetapkan enam. 684 00:28:54,400 --> 00:28:59,300 >> Jadi jika kita memiliki sebuah array dari ukuran total 26 sehingga ini adalah lokasi-25 685 00:28:59,300 --> 00:29:03,390 di bagian bawah, dan saya menyatakan bahwa Alice adalah kata pertama dalam kamus 686 00:29:03,390 --> 00:29:07,260 nama yang saya ingin masukkan ke dalam RAM, ke dalam struktur data, dimana 687 00:29:07,260 --> 00:29:12,480 naluri memberitahu Anda bahwa Alice Nama harus pergi dalam array ini? 688 00:29:12,480 --> 00:29:13,510 >> Kami memiliki 26 pilihan. 689 00:29:13,510 --> 00:29:14,990 Dimana kita ingin menempatkan dia? 690 00:29:14,990 --> 00:29:16,200 Kami ingin dia di braket nol, kan? 691 00:29:16,200 --> 00:29:18,280 A untuk Alice, mari kita sebut bahwa nol. 692 00:29:18,280 --> 00:29:20,110 Dan B akan menjadi salah satu, dan C akan menjadi dua. 693 00:29:20,110 --> 00:29:22,600 Jadi kita akan menulis Alice nama di sini. 694 00:29:22,600 --> 00:29:24,890 Jika kita kemudian memasukkan Bob, nya Nama akan pergi di sini. 695 00:29:24,890 --> 00:29:27,280 Charlie akan pergi di sini. 696 00:29:27,280 --> 00:29:30,500 Dan sebagainya bawah melalui ini struktur data. 697 00:29:30,500 --> 00:29:32,090 >> Ini adalah struktur data yang indah. 698 00:29:32,090 --> 00:29:32,730 Kenapa? 699 00:29:32,730 --> 00:29:37,460 Nah apa waktu berjalan memasukkan nama manusia ke dalam ini 700 00:29:37,460 --> 00:29:39,850 struktur data sekarang? 701 00:29:39,850 --> 00:29:43,702 Mengingat bahwa tabel ini diimplementasikan, benar-benar, sebagai array. 702 00:29:43,702 --> 00:29:44,940 Yah sudah waktunya konstan. 703 00:29:44,940 --> 00:29:45,800 Ini urutan satu. 704 00:29:45,800 --> 00:29:46,360 Kenapa? 705 00:29:46,360 --> 00:29:48,630 >> Nah bagaimana Anda menentukan di mana Alice milik? 706 00:29:48,630 --> 00:29:51,000 Anda melihat di mana surat namanya? 707 00:29:51,000 --> 00:29:51,490 Pertama. 708 00:29:51,490 --> 00:29:54,350 Dan Anda bisa sampai di sana, jika string, dengan hanya melihat tali 709 00:29:54,350 --> 00:29:55,200 braket nol. 710 00:29:55,200 --> 00:29:57,110 Jadi karakter ke nol dari string. 711 00:29:57,110 --> 00:29:57,610 Itu mudah. 712 00:29:57,610 --> 00:30:00,350 Kami melakukan itu di kripto tugas minggu lalu. 713 00:30:00,350 --> 00:30:05,310 Dan kemudian setelah Anda tahu bahwa Alice huruf modal, kita dapat mengurangi 714 00:30:05,310 --> 00:30:08,160 off 65 atau modal A sendiri, yang memberi kita nol. 715 00:30:08,160 --> 00:30:10,940 Jadi kita sekarang tahu bahwa Alice milik di lokasi nol. 716 00:30:10,940 --> 00:30:14,240 >> Dan mengingat pointer ke data ini struktur, dari beberapa macam, berapa lama 717 00:30:14,240 --> 00:30:18,840 itu membawa saya untuk menemukan lokasi nol dalam array? 718 00:30:18,840 --> 00:30:22,080 Hanya satu langkah, tepat Ini waktu yang konstan karena akses acak kita 719 00:30:22,080 --> 00:30:23,780 diusulkan adalah fitur dari sebuah array. 720 00:30:23,780 --> 00:30:28,570 Jadi singkatnya, mencari tahu apa indeks nama Alice adalah, yang, dalam 721 00:30:28,570 --> 00:30:32,610 kasus ini, adalah A, atau mari kita menyelesaikan bahwa untuk nol, dimana B adalah satu dan C adalah 722 00:30:32,610 --> 00:30:34,900 dua, dengan pertimbangan bahwa keluar adalah waktu yang konstan. 723 00:30:34,900 --> 00:30:38,510 Aku hanya harus melihat huruf pertama, mencari tahu di mana nol adalah 724 00:30:38,510 --> 00:30:40,460 array juga waktu yang konstan. 725 00:30:40,460 --> 00:30:42,140 Jadi secara teknis itu seperti dua langkah sekarang. 726 00:30:42,140 --> 00:30:43,330 Tapi itu masih konstan. 727 00:30:43,330 --> 00:30:46,880 Jadi kita sebut bahwa O besar satu, jadi kami sudah dimasukkan Alice ke dalam tabel ini dalam 728 00:30:46,880 --> 00:30:48,440 waktu yang konstan. 729 00:30:48,440 --> 00:30:50,960 >> Tapi tentu saja, aku sedang naif di sini, kan? 730 00:30:50,960 --> 00:30:53,240 Bagaimana jika ada sebuah Harun di kelas? 731 00:30:53,240 --> 00:30:53,990 Atau Alicia? 732 00:30:53,990 --> 00:30:57,230 Atau nama lain dimulai dengan A. Dimana kita akan menempatkan 733 00:30:57,230 --> 00:31:00,800 orang itu, kan? 734 00:31:00,800 --> 00:31:03,420 Maksudku, sekarang hanya ada tiga orang di atas meja, jadi mungkin kita 735 00:31:03,420 --> 00:31:07,490 harus menempatkan Aaron di lokasi nol satu dua tiga. 736 00:31:07,490 --> 00:31:09,480 >> Benar, aku bisa menempatkan A di sini. 737 00:31:09,480 --> 00:31:13,350 Tapi kemudian, jika kita mencoba untuk memasukkan David ke daftar ini, mana David pergi? 738 00:31:13,350 --> 00:31:15,170 Sekarang sistem kami mulai melanggar bawah, kanan? 739 00:31:15,170 --> 00:31:19,210 Karena sekarang David berakhir di sini jika Aaron sebenarnya di sini. 740 00:31:19,210 --> 00:31:23,060 Dan sekarang ini seluruh ide memiliki struktur data bersih yang memberi kita 741 00:31:23,060 --> 00:31:28,010 sisipan waktu yang konstan tidak lagi waktu yang konstan, karena saya harus 742 00:31:28,010 --> 00:31:31,240 periksa, oh, sialan, seseorang sudah di lokasi Alice. 743 00:31:31,240 --> 00:31:35,320 >> Biarkan aku menyelidiki sisa data ini struktur, mencari tempat untuk meletakkan 744 00:31:35,320 --> 00:31:37,130 seseorang seperti nama Harun. 745 00:31:37,130 --> 00:31:39,390 Dan itu juga mulai untuk mengambil waktu linier. 746 00:31:39,390 --> 00:31:42,710 Apalagi, jika Anda sekarang ingin menemukan Harun dalam struktur data, dan Anda 747 00:31:42,710 --> 00:31:45,430 cek, dan nama Harun tidak ada di sini. 748 00:31:45,430 --> 00:31:47,960 Idealnya, Anda hanya akan mengatakan Harun tidak dalam struktur data. 749 00:31:47,960 --> 00:31:51,530 Tapi jika Anda mulai membuat ruang untuk Aaron mana seharusnya ada D 750 00:31:51,530 --> 00:31:55,600 atau E, Anda, kasus terburuk, harus memeriksa struktur data keseluruhan, 751 00:31:55,600 --> 00:31:59,480 hal ini devolves menjadi sesuatu linear dalam ukuran meja. 752 00:31:59,480 --> 00:32:00,920 >> Jadi baik-baik saja, saya akan memperbaiki ini. 753 00:32:00,920 --> 00:32:04,200 Masalahnya di sini adalah bahwa saya punya 26 elemen dalam array ini. 754 00:32:04,200 --> 00:32:05,000 Biarkan aku mengubahnya. 755 00:32:05,000 --> 00:32:06,010 Whoops. 756 00:32:06,010 --> 00:32:10,600 Biarkan aku mengubahnya sehingga agak kesejahteraan ukuran 26 secara total, perhatikan bagian bawah 757 00:32:10,600 --> 00:32:12,720 Indeks akan berubah menjadi n dikurangi 1. 758 00:32:12,720 --> 00:32:16,610 Jika 26 adalah jelas terlalu kecil bagi manusia ' nama, karena ada ribuan 759 00:32:16,610 --> 00:32:20,830 nama dunia, mari kita membuat dalam 100 atau 1.000 atau 10.000. 760 00:32:20,830 --> 00:32:22,960 Mari kita mengalokasikan lebih banyak ruang. 761 00:32:22,960 --> 00:32:27,230 >> Nah itu tidak selalu menurun kemungkinan bahwa kita tidak akan memiliki dua 762 00:32:27,230 --> 00:32:31,510 orang-orang dengan nama dimulai dengan A, dan demikian, Anda akan mencoba untuk menempatkan A 763 00:32:31,510 --> 00:32:33,120 nama di lokasi nol masih. 764 00:32:33,120 --> 00:32:36,850 Mereka masih akan bertabrakan, yang berarti kita masih perlu solusi untuk menempatkan 765 00:32:36,850 --> 00:32:41,020 Alice dan Harun dan Alicia dan lainnya nama dimulai dengan tempat lain A. 766 00:32:41,020 --> 00:32:43,460 Tapi berapa banyak dari masalah ini? 767 00:32:43,460 --> 00:32:46,870 Apa probabilitas bahwa Anda memiliki tabrakan di data 768 00:32:46,870 --> 00:32:48,240 Struktur seperti ini? 769 00:32:48,240 --> 00:32:52,570 >> Nah, biarkan aku - kami akan kembali untuk pertanyaan itu di sini. 770 00:32:52,570 --> 00:32:55,530 Dan lihat bagaimana kita mungkin menyelesaikannya terlebih dahulu. 771 00:32:55,530 --> 00:32:58,480 Biarkan aku menarik usulan ini di sini. 772 00:32:58,480 --> 00:33:02,020 Apa yang kita baru saja dijelaskan adalah algoritma, heuristik disebut linear 773 00:33:02,020 --> 00:33:05,030 menyelidik dimana, jika Anda mencoba untuk memasukkan sesuatu di sini dalam data ini 774 00:33:05,030 --> 00:33:08,920 struktur, yang disebut tabel hash, dan tidak ada ruang di sana, Anda 775 00:33:08,920 --> 00:33:12,000 benar-benar menyelidiki struktur data memeriksa, apakah ini tersedia? 776 00:33:12,000 --> 00:33:13,430 Apakah Tersedia ini tersedia ini? 777 00:33:13,430 --> 00:33:13,980 Apakah ini tersedia? 778 00:33:13,980 --> 00:33:17,550 Dan ketika akhirnya adalah, Anda memasukkan nama yang awalnya ditujukan 779 00:33:17,550 --> 00:33:19,370 tempat lain di lokasi itu. 780 00:33:19,370 --> 00:33:23,360 Tapi dalam kasus terburuk, satu-satunya tempat mungkin bagian paling bawah dari data 781 00:33:23,360 --> 00:33:25,090 struktur, akhir array. 782 00:33:25,090 --> 00:33:30,130 >> Jadi linear probing, dalam kasus terburuk, devolves ke algoritma linear dimana 783 00:33:30,130 --> 00:33:34,500 Harun, jika ia kebetulan dimasukkan lalu dalam struktur data, ia mungkin 784 00:33:34,500 --> 00:33:39,540 berbenturan dengan lokasi pertama ini, namun kemudian berakhir dengan nasib buruk di akhir. 785 00:33:39,540 --> 00:33:43,940 Jadi ini bukan sebuah konstanta waktu grail suci bagi kita. 786 00:33:43,940 --> 00:33:47,650 Pendekatan elemen memasukkan ke struktur data yang disebut hash 787 00:33:47,650 --> 00:33:52,050 tabel tampaknya tidak menjadi waktu yang konstan setidaknya tidak dalam kasus umum. 788 00:33:52,050 --> 00:33:54,000 Hal ini dapat berpindah ke sesuatu yang linear. 789 00:33:54,000 --> 00:33:56,970 >> Jadi bagaimana jika kita menyelesaikan tabrakan agak berbeda? 790 00:33:56,970 --> 00:34:00,740 Jadi, inilah yang lebih canggih pendekatan apa yang masih 791 00:34:00,740 --> 00:34:02,800 disebut tabel hash. 792 00:34:02,800 --> 00:34:05,890 Dan dengan hash, sebagai samping, apa Maksudku adalah indeks yang 793 00:34:05,890 --> 00:34:07,070 Saya sebut sebelumnya. 794 00:34:07,070 --> 00:34:09,810 Untuk sesuatu yang hash dapat dianggap sebagai kata kerja. 795 00:34:09,810 --> 00:34:13,690 >> Jadi jika Anda hash Alice adalah nama, fungsi hash, sehingga untuk berbicara, 796 00:34:13,690 --> 00:34:14,710 harus kembali nomor. 797 00:34:14,710 --> 00:34:18,199 Dalam hal ini adalah nol jika dia milik di lokasi nol, satu jika dia milik di 798 00:34:18,199 --> 00:34:20,000 lokasi satu, dan sebagainya. 799 00:34:20,000 --> 00:34:24,360 Jadi fungsi hash saya sejauh ini telah super sederhana, hanya melihat 800 00:34:24,360 --> 00:34:26,159 huruf pertama dalam nama seseorang. 801 00:34:26,159 --> 00:34:29,090 Tapi fungsi hash mengambil sebagai masukan beberapa bagian dari data, 802 00:34:29,090 --> 00:34:30,210 String, int, apa pun. 803 00:34:30,210 --> 00:34:32,239 Dan meludah keluar biasanya nomor. 804 00:34:32,239 --> 00:34:35,739 Dan nomor itu adalah di mana data elemen termasuk dalam struktur data 805 00:34:35,739 --> 00:34:37,800 dikenal di sini sebagai tabel hash. 806 00:34:37,800 --> 00:34:41,400 >> Jadi hanya intuitif, ini adalah konteks yang sedikit berbeda. 807 00:34:41,400 --> 00:34:44,170 Ini sebenarnya adalah mengacu pada contoh melibatkan ulang tahun, di mana 808 00:34:44,170 --> 00:34:46,850 mungkin ada sebanyak 31 hari dalam sebulan. 809 00:34:46,850 --> 00:34:52,239 Tapi apa orang ini memutuskan untuk dilakukan jika terjadi tabrakan? 810 00:34:52,239 --> 00:34:55,304 Konteks sekarang sedang, bukan tabrakan nama, tapi tabrakan ulang tahun, 811 00:34:55,304 --> 00:35:00,760 jika dua orang memiliki ulang tahun yang sama pada tanggal 2 Oktober, misalnya. 812 00:35:00,760 --> 00:35:02,120 >> SISWA: [Tak terdengar]. 813 00:35:02,120 --> 00:35:05,010 >> SPEAKER 1: Ya, jadi di sini kita memiliki , mewarnai daftar terkait. 814 00:35:05,010 --> 00:35:07,830 Jadi terlihat sedikit berbeda daripada kita menarik itu sebelumnya. 815 00:35:07,830 --> 00:35:10,790 Tapi kita tampaknya harus array di sisi kiri. 816 00:35:10,790 --> 00:35:13,230 Itulah salah satu indeks, karena tidak ada alasan tertentu. 817 00:35:13,230 --> 00:35:14,630 Tapi itu masih array. 818 00:35:14,630 --> 00:35:16,160 Ini sebuah array dari pointer. 819 00:35:16,160 --> 00:35:20,670 Dan masing-masing unsur, masing-masing kalangan ini atau garis miring - slash 820 00:35:20,670 --> 00:35:23,970 mewakili nol - masing-masing pointer rupanya menunjuk ke 821 00:35:23,970 --> 00:35:25,730 apa struktur data? 822 00:35:25,730 --> 00:35:26,890 Sebuah linked list. 823 00:35:26,890 --> 00:35:30,530 >> Jadi sekarang kita memiliki kemampuan untuk kode keras ke dalam program kami 824 00:35:30,530 --> 00:35:32,010 ukuran meja. 825 00:35:32,010 --> 00:35:35,360 Dalam kasus ini, kita tahu tidak pernah ada lebih dari 31 hari dalam sebulan. 826 00:35:35,360 --> 00:35:38,480 Jadi hard coding nilai seperti 31 adalah wajar dalam konteks itu. 827 00:35:38,480 --> 00:35:42,700 Dalam konteks nama, hard coding 26 tidak masuk akal itu orang 828 00:35:42,700 --> 00:35:46,340 hanya nama mulai dengan, misalnya, alfabet yang melibatkan A sampai Z. 829 00:35:46,340 --> 00:35:50,180 >> Kita bisa menjejalkan mereka semua ke dalam data Struktur asalkan, ketika kita mendapatkan 830 00:35:50,180 --> 00:35:55,330 tabrakan, kita tidak menempatkan nama di sini, kita malah memikirkan sel-sel 831 00:35:55,330 --> 00:36:00,270 bukan sebagai string sendiri, tetapi sebagai pointer ke, misalnya, Alice. 832 00:36:00,270 --> 00:36:03,660 Dan kemudian Alice dapat memiliki pointer lain ke nama lain dimulai dengan 833 00:36:03,660 --> 00:36:06,150 A. Dan Bob benar-benar berjalan di sini. 834 00:36:06,150 --> 00:36:10,850 >> Dan jika ada nama lain mulai dengan B, ia berakhir di sini. 835 00:36:10,850 --> 00:36:15,070 Dan masing-masing unsur ini dua meja, jika kita merancang ini 836 00:36:15,070 --> 00:36:17,350 sedikit lebih cerdik - 837 00:36:17,350 --> 00:36:18,125 ayolah - 838 00:36:18,125 --> 00:36:22,950 jika kita merancang ini lebih sedikit cerdik, sekarang menjadi data yang adaptif 839 00:36:22,950 --> 00:36:27,720 struktur, di mana tidak ada batas keras pada berapa banyak elemen yang Anda dapat menyisipkan 840 00:36:27,720 --> 00:36:30,700 ke dalamnya karena jika Anda memiliki tabrakan, itu bagus. 841 00:36:30,700 --> 00:36:34,690 Hanya pergi ke depan dan menambahkan ke apa yang kita lihat sedikit lalu adalah 842 00:36:34,690 --> 00:36:38,290 dikenal sebagai linked list. 843 00:36:38,290 --> 00:36:39,690 >> Nah mari kita berhenti untuk sesaat. 844 00:36:39,690 --> 00:36:42,570 Berapa probabilitas tabrakan di tempat pertama? 845 00:36:42,570 --> 00:36:45,480 Benar, mungkin aku lebih berpikir, mungkin Aku di rekayasa masalah ini, 846 00:36:45,480 --> 00:36:46,370 karena Anda tahu apa? 847 00:36:46,370 --> 00:36:49,070 Ya, aku bisa datang dengan sewenang-wenang contoh dari atas kepalaku seperti 848 00:36:49,070 --> 00:36:52,870 Allison dan Harun, tetapi dalam kenyataannya, diberi distribusi seragam 849 00:36:52,870 --> 00:36:56,990 input, yaitu beberapa sisipan acak ke dalam struktur data, apa yang benar-benar 850 00:36:56,990 --> 00:36:58,580 probabilitas tabrakan? 851 00:36:58,580 --> 00:37:01,670 Nah ternyata, itu sebenarnya Super tinggi. 852 00:37:01,670 --> 00:37:03,850 Mari saya menggeneralisasi ini masalah adalah seperti ini. 853 00:37:03,850 --> 00:37:08,890 >> Jadi di ruang n CS50 siswa, apa probabilitas bahwa setidaknya 854 00:37:08,890 --> 00:37:11,010 dua mahasiswa di ruang memiliki ulang tahun yang sama? 855 00:37:11,010 --> 00:37:13,346 Jadi ada apa. sebuah Hund beberapa - 856 00:37:13,346 --> 00:37:16,790 200, 300 orang di sini dan beberapa ratus orang di rumah hari ini. 857 00:37:16,790 --> 00:37:20,670 Jadi jika Anda ingin bertanya kepada diri sendiri apa yang kemungkinan dua orang 858 00:37:20,670 --> 00:37:23,930 di ruangan ini memiliki ulang tahun yang sama, kita bisa mengetahui ini. 859 00:37:23,930 --> 00:37:26,250 Dan saya mengklaim sebenarnya ada dua orang dengan ulang tahun yang sama. 860 00:37:26,250 --> 00:37:29,560 >> Misalnya, apakah ada memiliki ulang tahun hari ini? 861 00:37:29,560 --> 00:37:31,340 Kemarin? 862 00:37:31,340 --> 00:37:32,590 Besok? 863 00:37:32,590 --> 00:37:35,980 Baiklah, jadi rasanya seperti aku akan harus melakukan ini 363 atau jadi lebih 864 00:37:35,980 --> 00:37:39,500 kali untuk benar-benar mengetahui jika kita memiliki tabrakan. 865 00:37:39,500 --> 00:37:42,350 Atau kita hanya bisa melakukan ini secara matematis daripada tediously 866 00:37:42,350 --> 00:37:43,200 melakukan hal ini. 867 00:37:43,200 --> 00:37:44,500 Dan mengusulkan berikut. 868 00:37:44,500 --> 00:37:48,740 >> Jadi saya mengusulkan bahwa kita dapat memodelkan kemungkinan dua orang memiliki 869 00:37:48,740 --> 00:37:55,320 ulang tahun yang sama sebagai probabilitas dari 1 minus probabilitas tidak ada yang memiliki 870 00:37:55,320 --> 00:37:56,290 ulang tahun yang sama. 871 00:37:56,290 --> 00:37:59,960 Jadi untuk mendapatkan ini, dan ini hanya cara mewah menulis ini, untuk 872 00:37:59,960 --> 00:38:03,090 orang pertama di dalam ruangan, ia dapat memiliki satu dari kemungkinan 873 00:38:03,090 --> 00:38:07,370 ulang tahun dengan asumsi 365 hari dalam setahun, dengan permintaan maaf kepada orang-orang dengan 874 00:38:07,370 --> 00:38:08,760 tanggal 29 Februari ulang tahun. 875 00:38:08,760 --> 00:38:13,470 >> Jadi orang pertama di ruangan ini gratis memiliki sejumlah umur 876 00:38:13,470 --> 00:38:18,280 dari 365 kemungkinan sehingga kita akan melakukan itu 365 dibagi dengan 365, 877 00:38:18,280 --> 00:38:18,990 yang merupakan salah satu. 878 00:38:18,990 --> 00:38:22,700 Orang berikutnya dalam ruangan, jika tujuan adalah untuk menghindari tabrakan, hanya dapat 879 00:38:22,700 --> 00:38:26,460 memiliki hari ulang tahunnya pada bagaimana banyak kemungkinan hari yang berbeda? 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Jadi istilah kedua dalam ungkapan ini dasarnya melakukan matematika untuk kita 882 00:38:31,430 --> 00:38:33,460 dengan mengurangkan off satu hari mungkin. 883 00:38:33,460 --> 00:38:36,390 Dan kemudian hari berikutnya, hari berikutnya, hari berikutnya ke jumlah 884 00:38:36,390 --> 00:38:38,100 orang di ruangan. 885 00:38:38,100 --> 00:38:41,290 >> Dan jika kita kemudian mempertimbangkan, lalu apa kemungkinan tidak semua orang memiliki 886 00:38:41,290 --> 00:38:45,265 ulang tahun yang unik, tapi sekali lagi dikurangi 1 itu, apa yang kita dapatkan adalah sebuah ekspresi 887 00:38:45,265 --> 00:38:47,810 yang dapat sangat fancifully terlihat seperti ini. 888 00:38:47,810 --> 00:38:50,330 Tapi itu lebih menarik untuk melihat secara visual. 889 00:38:50,330 --> 00:38:55,120 Ini adalah bagan mana pada sumbu-x adalah jumlah orang di ruangan, 890 00:38:55,120 --> 00:38:56,180 jumlah ulang tahun. 891 00:38:56,180 --> 00:38:59,840 Pada sumbu y adalah probabilitas tabrakan, dua orang 892 00:38:59,840 --> 00:39:01,230 memiliki ulang tahun yang sama. 893 00:39:01,230 --> 00:39:05,020 >> Dan takeaway dari kurva ini bahwa segera setelah Anda mendapatkan untuk seperti 40 894 00:39:05,020 --> 00:39:11,110 siswa, kau sudah bangun pada probabilitas 90% combinatorically dua 895 00:39:11,110 --> 00:39:13,550 orang atau lebih memiliki ulang tahun yang sama. 896 00:39:13,550 --> 00:39:18,600 Dan sekali Anda mendapatkan untuk seperti 58 orang itu hampir 100% dari dua kesempatan 897 00:39:18,600 --> 00:39:21,310 orang di ruangan itu akan memiliki ulang tahun yang sama, meskipun ada 898 00:39:21,310 --> 00:39:26,650 365 atau 366 mungkin ember, dan hanya 58 orang di dalam ruangan. 899 00:39:26,650 --> 00:39:29,900 Hanya statistik mungkin Anda mendapatkan tabrakan, yang singkatnya 900 00:39:29,900 --> 00:39:31,810 memotivasi diskusi ini. 901 00:39:31,810 --> 00:39:35,890 Itu bahkan jika kita mendapatkan mewah di sini, dan mulai memiliki rantai ini, kita masih 902 00:39:35,890 --> 00:39:36,950 akan memiliki tabrakan. 903 00:39:36,950 --> 00:39:42,710 >> Sehingga menimbulkan pertanyaan, apa biaya melakukan insersi dan penghapusan 904 00:39:42,710 --> 00:39:44,850 ke dalam struktur data seperti ini? 905 00:39:44,850 --> 00:39:46,630 Yah biarkan aku mengusulkan - 906 00:39:46,630 --> 00:39:51,570 dan biarkan aku kembali ke layar atas sini - jika kita memiliki n elemen dalam 907 00:39:51,570 --> 00:39:56,330 daftar, jadi jika kita mencoba untuk memasukkan n elemen, dan kami memiliki 908 00:39:56,330 --> 00:39:58,050 berapa banyak jumlah ember? 909 00:39:58,050 --> 00:40:03,450 Katakanlah 31 Total ember dalam kasus ulang tahun. 910 00:40:03,450 --> 00:40:09,240 Apa panjang maksimum satu dari rantai ini berpotensi? 911 00:40:09,240 --> 00:40:12,670 >> Jika lagi ada 31 mungkin ulang tahun pada bulan tertentu. 912 00:40:12,670 --> 00:40:14,580 Dan kami hanya penggumpalan orang - 913 00:40:14,580 --> 00:40:15,580 sebenarnya itu adalah contoh bodoh. 914 00:40:15,580 --> 00:40:16,960 Mari kita lakukan 26 sebagai gantinya. 915 00:40:16,960 --> 00:40:20,890 Jadi jika benar-benar memiliki orang yang namanya mulai dengan A sampai Z, sehingga memberikan 916 00:40:20,890 --> 00:40:22,780 kami 26 kemungkinan. 917 00:40:22,780 --> 00:40:25,920 Dan kita sedang menggunakan struktur data seperti yang kita hanya melihat, dimana kita memiliki 918 00:40:25,920 --> 00:40:30,210 sebuah array dari pointer, yang masing-masing menunjuk ke sebuah linked list mana 919 00:40:30,210 --> 00:40:32,360 Daftar pertama adalah orang dengan nama Alice. 920 00:40:32,360 --> 00:40:35,770 Daftar kedua adalah setiap dengan nama dimulai dengan A, mulai 921 00:40:35,770 --> 00:40:36,980 dengan B, dan sebagainya. 922 00:40:36,980 --> 00:40:41,020 >> Apa panjang kemungkinan dari masing-masing daftar tersebut jika kita mengasumsikan bersih bagus 923 00:40:41,020 --> 00:40:45,410 distribusi nama A sampai Z seluruh struktur data keseluruhan? 924 00:40:45,410 --> 00:40:50,210 Ada orang n dalam struktur data dibagi dengan 26, jika mereka baik 925 00:40:50,210 --> 00:40:52,110 tersebar di seluruh struktur data. 926 00:40:52,110 --> 00:40:54,970 Jadi panjang dari masing-masing rantai adalah n dibagi dengan 26. 927 00:40:54,970 --> 00:40:57,380 Namun dalam notasi O besar, apa itu? 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 Apa yang benar-benar? 930 00:41:02,440 --> 00:41:04,150 Jadi itu benar-benar hanya n, kan? 931 00:41:04,150 --> 00:41:06,620 Karena kita telah mengatakan di masa lalu, bahwa ugh Anda membagi dengan 26. 932 00:41:06,620 --> 00:41:08,710 Ya, pada kenyataannya itu lebih cepat. 933 00:41:08,710 --> 00:41:12,720 Tapi dalam teori, itu tidak mendasar semua yang cepat. 934 00:41:12,720 --> 00:41:16,040 >> Jadi kita tampaknya tidak menjadi semua yang banyak lebih dekat ke grail suci ini. 935 00:41:16,040 --> 00:41:17,750 Bahkan, ini hanya waktu linier. 936 00:41:17,750 --> 00:41:20,790 Heck, pada titik ini, kenapa tidak kita hanya menggunakan satu linked list besar? 937 00:41:20,790 --> 00:41:23,510 Kenapa tidak kita hanya menggunakan satu besar array untuk menyimpan nama-nama 938 00:41:23,510 --> 00:41:25,010 semua orang di ruangan? 939 00:41:25,010 --> 00:41:28,280 Nah, masih ada sesuatu yang menarik tentang tabel hash? 940 00:41:28,280 --> 00:41:30,810 Apakah masih ada sesuatu yang menarik tentang struktur data 941 00:41:30,810 --> 00:41:33,940 yang terlihat seperti ini? 942 00:41:33,940 --> 00:41:35,182 Ini. 943 00:41:35,182 --> 00:41:37,050 >> SISWA: [Tak terdengar]. 944 00:41:37,050 --> 00:41:39,840 >> SPEAKER 1: Benar, dan lagi jika itu hanya algoritma waktu linier, dan 945 00:41:39,840 --> 00:41:42,780 waktu linier struktur data, kenapa tidak saya hanya menyimpan nama semua orang di besar 946 00:41:42,780 --> 00:41:44,210 array, atau dalam linked list besar? 947 00:41:44,210 --> 00:41:47,010 Dan berhenti membuat CS begitu jauh lebih sulit selain itu perlu? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 Apa yang menarik tentang ini, bahkan meskipun aku menggaruk itu? 950 00:41:53,190 --> 00:41:54,930 >> SISWA: [Tak terdengar]. 951 00:41:54,930 --> 00:41:57,040 >> SPEAKER 1: Pemasangan tidak? 952 00:41:57,040 --> 00:41:58,140 Mahal lagi. 953 00:41:58,140 --> 00:42:03,390 Jadi sisipan berpotensi masih bisa menjadi waktu yang konstan, bahkan jika data Anda 954 00:42:03,390 --> 00:42:07,910 Struktur seperti ini, array pointer, yang masing-masing menunjuk 955 00:42:07,910 --> 00:42:09,550 berpotensi linked list. 956 00:42:09,550 --> 00:42:15,220 Bagaimana bisa Anda mencapai konstan waktu penyisipan nama? 957 00:42:15,220 --> 00:42:16,280 Tempelkan di depan, kan? 958 00:42:16,280 --> 00:42:19,290 >> Jika kita mengorbankan tujuan desain dari sebelumnya, di mana kami ingin menjaga 959 00:42:19,290 --> 00:42:22,650 nama semua orang, misalnya, diurutkan, atau semua nomor di atas panggung diurutkan, 960 00:42:22,650 --> 00:42:25,020 misalkan kita memiliki disortir linked list. 961 00:42:25,020 --> 00:42:29,960 Itu hanya biaya kami satu atau dua langkah, seperti dalam kasus Ben dan Brian 962 00:42:29,960 --> 00:42:32,750 sebelumnya, untuk memasukkan unsur di awal daftar. 963 00:42:32,750 --> 00:42:36,090 Jadi jika kita tidak peduli tentang menyortir semua dari nama dimulai dengan A atau semua 964 00:42:36,090 --> 00:42:39,660 nama-nama yang diawali huruf B, kita masih bisa mencapai waktu yang konstan penyisipan. 965 00:42:39,660 --> 00:42:43,900 Sekarang mencari Alice atau Bob atau nama apapun lebih umum masih apa? 966 00:42:43,900 --> 00:42:48,100 Ini O besar n dibagi dengan 26, di kasus yang ideal di mana semua orang seragam 967 00:42:48,100 --> 00:42:51,190 didistribusikan, di mana ada banyak A karena ada Z, yang mungkin 968 00:42:51,190 --> 00:42:52,220 realistis. 969 00:42:52,220 --> 00:42:53,880 Tapi itu masih linear. 970 00:42:53,880 --> 00:42:57,120 >> Tapi di sini, kita kembali ke titik notasi asimtotik menjadi 971 00:42:57,120 --> 00:42:58,600 secara teoritis benar. 972 00:42:58,600 --> 00:43:02,960 Tapi di dunia nyata, jika saya menyatakan bahwa program saya dapat melakukan sesuatu 26 kali 973 00:43:02,960 --> 00:43:06,210 lebih cepat dari Anda, yang programnya Anda akan lebih suka menggunakan? 974 00:43:06,210 --> 00:43:09,660 Anda atau saya, yang adalah 26 kali lebih cepat? 975 00:43:09,660 --> 00:43:14,320 Realistis, orang yang adalah 26 kali lebih cepat, bahkan jika secara teoritis 976 00:43:14,320 --> 00:43:18,790 algoritma kami berjalan di sama asymptotic waktu berjalan. 977 00:43:18,790 --> 00:43:20,940 >> Mari saya mengusulkan berbeda solusi sama sekali. 978 00:43:20,940 --> 00:43:24,380 Dan jika ini tidak meniup pikiran Anda, kita keluar dari struktur data. 979 00:43:24,380 --> 00:43:27,420 Jadi ini dia trie - 980 00:43:27,420 --> 00:43:28,520 jenis nama bodoh. 981 00:43:28,520 --> 00:43:32,880 Itu berasal dari retrievals, dan kata dieja trie, t-r-i-e, karena 982 00:43:32,880 --> 00:43:34,450 pengambilan saja terdengar seperti trie. 983 00:43:34,450 --> 00:43:36,580 Tapi itu sejarah dari trie kata. 984 00:43:36,580 --> 00:43:40,980 >> Jadi trie memang beberapa jenis pohon, dan juga bermain pada kata itu. 985 00:43:40,980 --> 00:43:46,330 Dan meskipun Anda tidak bisa melihatnya dengan visualisasi ini, trie adalah 986 00:43:46,330 --> 00:43:50,790 pohon terstruktur, seperti pohon keluarga dengan satu nenek moyang di bagian atas dan banyak 987 00:43:50,790 --> 00:43:54,530 cucu dan cicit seperti daun di bagian bawah. 988 00:43:54,530 --> 00:43:58,100 Tetapi masing-masing node dalam trie adalah array. 989 00:43:58,100 --> 00:44:00,680 Dan dalam sebuah array - dan mari kita menyederhanakan sejenak - itu adalah 990 00:44:00,680 --> 00:44:04,600 array, dalam kasus ini, ukuran 26, di mana setiap node lagi adalah array dari ukuran 991 00:44:04,600 --> 00:44:09,000 26, di mana unsur zeroth dalam array mewakili A, dan terakhir 992 00:44:09,000 --> 00:44:11,810 unsur tiap seperti array mewakili Z. 993 00:44:11,810 --> 00:44:15,520 >> Jadi saya mengusulkan, kemudian, bahwa data ini struktur, yang dikenal sebagai trie, bisa 994 00:44:15,520 --> 00:44:17,600 digunakan juga untuk menyimpan kata-kata. 995 00:44:17,600 --> 00:44:21,740 Kami melihat beberapa saat yang lalu bagaimana kita bisa menyimpan kata-kata, atau dalam hal ini nama kasus, dan kami 996 00:44:21,740 --> 00:44:25,440 lihat sebelumnya bagaimana kita dapat menyimpan nomor, tetapi jika kita fokus pada nama atau string 997 00:44:25,440 --> 00:44:27,460 di sini, perhatikan apa yang menarik. 998 00:44:27,460 --> 00:44:32,210 Saya menyatakan bahwa nama Maxwell adalah dalam struktur data ini. 999 00:44:32,210 --> 00:44:33,730 Di mana Anda melihat Maxwell? 1000 00:44:33,730 --> 00:44:35,140 >> SISWA: [Tak terdengar]. 1001 00:44:35,140 --> 00:44:36,240 >> SPEAKER 1: Pada bagian kiri. 1002 00:44:36,240 --> 00:44:39,910 Jadi apa yang menarik dengan data ini Struktur ini bukan toko 1003 00:44:39,910 --> 00:44:46,200 String M-A-X-W-E-L-L backslash nol, semua contiguously, apa yang Anda lakukan sebagai gantinya 1004 00:44:46,200 --> 00:44:46,890 mengikuti. 1005 00:44:46,890 --> 00:44:50,510 Jika ini adalah trie seperti struktur data, masing-masing yang node lagi array, 1006 00:44:50,510 --> 00:44:54,650 dan Anda ingin menyimpan Maxwell, pertama Indeks dan sebagainya simpul akar, sehingga 1007 00:44:54,650 --> 00:44:57,810 untuk berbicara, simpul paling atas, di lokasi M, kanan, sehingga 1008 00:44:57,810 --> 00:44:59,160 kira-kira ke tengah. 1009 00:44:59,160 --> 00:45:03,740 Dan kemudian dari sana, Anda mengikuti pointer ke node anak, sehingga untuk berbicara. 1010 00:45:03,740 --> 00:45:06,150 Jadi dalam arti pohon keluarga, Anda mengikutinya ke bawah. 1011 00:45:06,150 --> 00:45:09,030 Dan yang menuntun Anda ke node lain di sebelah kiri ada, yang 1012 00:45:09,030 --> 00:45:10,540 hanya array lain. 1013 00:45:10,540 --> 00:45:14,710 >> Dan kemudian jika Anda ingin menyimpan Maxwell, Anda menemukan pointer yang mewakili 1014 00:45:14,710 --> 00:45:16,430 A, yang merupakan salah satu ini di sini. 1015 00:45:16,430 --> 00:45:17,840 Kemudian Anda pergi ke node berikutnya. 1016 00:45:17,840 --> 00:45:20,100 Dan perhatikan - ini adalah mengapa gambar itu sedikit menipu - 1017 00:45:20,100 --> 00:45:21,990 node ini terlihat super kecil. 1018 00:45:21,990 --> 00:45:26,050 Tapi di sebelah kanan ini adalah Y dan Z. Hanya saja penulis telah terpotong 1019 00:45:26,050 --> 00:45:27,630 gambar sehingga Anda benar-benar melihat hal-hal. 1020 00:45:27,630 --> 00:45:30,400 Jika gambar ini akan menjadi sangat lebar. 1021 00:45:30,400 --> 00:45:36,180 Jadi sekarang Anda indeks ke lokasi X, maka W, Lalu E, maka L, kemudian L. Lalu apa 1022 00:45:36,180 --> 00:45:37,380 keingintahuan ini? 1023 00:45:37,380 --> 00:45:41,250 >> Nah, jika kita menggunakan semacam ini baru mengambil tentang cara menyimpan string dalam 1024 00:45:41,250 --> 00:45:44,500 struktur data, Anda masih perlu dasarnya cek dalam data 1025 00:45:44,500 --> 00:45:47,250 struktur yang kata berakhir di sini. 1026 00:45:47,250 --> 00:45:50,830 Dengan kata lain, masing-masing node ini entah bagaimana harus ingat bahwa kita 1027 00:45:50,830 --> 00:45:53,500 benar-benar mengikuti semua petunjuk ini dan meninggalkan sedikit 1028 00:45:53,500 --> 00:45:58,370 remah roti di bagian bawah di sini ini Struktur untuk menunjukkan M-A-X-W-E-L-L 1029 00:45:58,370 --> 00:46:00,230 memang dalam struktur data. 1030 00:46:00,230 --> 00:46:02,040 >> Jadi kita bisa melakukan hal ini sebagai berikut. 1031 00:46:02,040 --> 00:46:06,810 Setiap node dalam gambar kita hanya gergaji memiliki satu, array ukuran 27. 1032 00:46:06,810 --> 00:46:10,550 Dan sekarang 27, karena dalam hal menetapkan enam, kita benar-benar akan memberikan apostrof, 1033 00:46:10,550 --> 00:46:13,590 sehingga kita bisa memiliki nama seperti O'Reilly dan lain-lain dengan apostrof. 1034 00:46:13,590 --> 00:46:14,820 Tapi ide yang sama. 1035 00:46:14,820 --> 00:46:17,710 Masing-masing elemen dalam Array menunjuk ke struct 1036 00:46:17,710 --> 00:46:19,320 node, jadi hanya sebuah simpul. 1037 00:46:19,320 --> 00:46:21,430 Jadi ini sangat mengingatkan dari linked list kami. 1038 00:46:21,430 --> 00:46:24,550 >> Dan kemudian aku punya Boolean, yang saya akan menyebut kata, yang hanya akan menjadi 1039 00:46:24,550 --> 00:46:29,120 benar jika kata berakhir ini node di pohon. 1040 00:46:29,120 --> 00:46:32,870 Secara efektif merupakan sedikit segitiga kami melihat beberapa saat yang lalu. 1041 00:46:32,870 --> 00:46:37,190 Jadi, jika sebuah kata berakhir pada simpul di pohon, bahwa field kata akan menjadi kenyataan, 1042 00:46:37,190 --> 00:46:41,990 yang secara konseptual mengecek, atau kita menggambar segitiga ini, ya ada 1043 00:46:41,990 --> 00:46:44,080 adalah kata di sini. 1044 00:46:44,080 --> 00:46:45,120 >> Jadi ini adalah trie. 1045 00:46:45,120 --> 00:46:48,540 Dan sekarang pertanyaannya adalah, apa yang adalah nya waktu berjalan? 1046 00:46:48,540 --> 00:46:49,930 Apakah O besar n? 1047 00:46:49,930 --> 00:46:51,410 Apakah itu sesuatu yang lain? 1048 00:46:51,410 --> 00:46:57,330 Nah, jika Anda memiliki n nama dalam data ini struktur, Maxwell menjadi salah satu 1049 00:46:57,330 --> 00:47:02,330 mereka, apa waktu berjalan memasukkan atau mencari Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Apa waktu berjalan memasukkan Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Jika ada n nama lain sudah di meja? 1053 00:47:11,740 --> 00:47:12,507 Ya? 1054 00:47:12,507 --> 00:47:15,429 >> SISWA: [Tak terdengar]. 1055 00:47:15,429 --> 00:47:17,550 >> SPEAKER 1: Ya, itu panjang dari nama, kan? 1056 00:47:17,550 --> 00:47:24,420 Jadi M-a-x-w-e-l-l jadi rasanya seperti ini algoritma adalah O besar tujuh. 1057 00:47:24,420 --> 00:47:26,580 Sekarang, tentu saja, nama panjangnya bervariasi. 1058 00:47:26,580 --> 00:47:27,380 Mungkin itu nama pendek. 1059 00:47:27,380 --> 00:47:28,600 Mungkin itu nama lagi. 1060 00:47:28,600 --> 00:47:33,390 Tapi apa kunci di sini adalah bahwa itu nomor konstan. 1061 00:47:33,390 --> 00:47:36,810 Dan mungkin tidak benar-benar konstan, tapi Tuhan, jika realistis, dalam 1062 00:47:36,810 --> 00:47:41,570 kamus, mungkin ada beberapa batas pada jumlah huruf dalam 1063 00:47:41,570 --> 00:47:43,820 nama orang di negara tertentu. 1064 00:47:43,820 --> 00:47:46,940 >> Dan jadi kita bisa berasumsi bahwa Nilai adalah konstan. 1065 00:47:46,940 --> 00:47:47,750 Aku tidak tahu apa itu. 1066 00:47:47,750 --> 00:47:50,440 Ini mungkin lebih besar dari kami pikir itu adalah. 1067 00:47:50,440 --> 00:47:52,720 Karena selalu ada beberapa sudut kasus dengan nama yang panjang gila. 1068 00:47:52,720 --> 00:47:56,360 Jadi sebut saja k, tapi masih konstan mungkin, karena setiap 1069 00:47:56,360 --> 00:48:00,190 nama di dunia, setidaknya dalam negara tertentu, adalah bahwa panjang atau 1070 00:48:00,190 --> 00:48:01,780 pendek, jadi konstan. 1071 00:48:01,780 --> 00:48:04,490 Tapi ketika kita sudah mengatakan sesuatu yang besar O dari nilai konstan, apa itu 1072 00:48:04,490 --> 00:48:07,760 benar-benar setara dengan? 1073 00:48:07,760 --> 00:48:10,420 Itu benar-benar hal yang sama mengatakan waktu yang konstan. 1074 00:48:10,420 --> 00:48:11,530 >> Sekarang kita semacam kecurangan, kan? 1075 00:48:11,530 --> 00:48:15,340 Kami agak memanfaatkan beberapa teori sini untuk mengatakan bahwa baik, urutan k 1076 00:48:15,340 --> 00:48:17,450 benar-benar hanya memesan satu, dan itu waktu yang konstan. 1077 00:48:17,450 --> 00:48:18,200 Tapi itu benar-benar adalah. 1078 00:48:18,200 --> 00:48:22,550 Karena wawasan kunci di sini adalah bahwa jika kita memiliki n nama sudah dalam 1079 00:48:22,550 --> 00:48:26,010 struktur data, dan kami memasukkan Maxwell, adalah jumlah waktu yang dibutuhkan kita untuk 1080 00:48:26,010 --> 00:48:29,530 masukkan Maxwell sama sekali terpengaruh oleh berapa banyak orang lain 1081 00:48:29,530 --> 00:48:31,100 berada dalam struktur data? 1082 00:48:31,100 --> 00:48:31,670 Tampaknya tidak menjadi. 1083 00:48:31,670 --> 00:48:36,280 Jika saya punya miliar lebih elemen ini trie, dan kemudian memasukkan Maxwell, adalah 1084 00:48:36,280 --> 00:48:38,650 ia sama sekali terpengaruh? 1085 00:48:38,650 --> 00:48:39,050 Tidak. 1086 00:48:39,050 --> 00:48:42,950 Dan itu tidak seperti dari data hari struktur yang telah kita lihat sejauh ini, di mana 1087 00:48:42,950 --> 00:48:46,820 waktu berjalan dari algoritma Anda benar independen dari berapa banyak 1088 00:48:46,820 --> 00:48:51,430 hal ini atau belum dalam struktur data. 1089 00:48:51,430 --> 00:48:54,650 >> Dan dengan ini memberi Anda sekarang adalah kesempatan bagi p set enam, yang akan 1090 00:48:54,650 --> 00:48:58,310 lagi melibatkan menerapkan Anda sendiri spell checker, membaca di 150.000 1091 00:48:58,310 --> 00:49:01,050 kata-kata, cara terbaik untuk menyimpan bahwa belum tentu jelas. 1092 00:49:01,050 --> 00:49:04,030 Dan meskipun aku sudah bercita-cita untuk menemukan grail suci, saya tidak 1093 00:49:04,030 --> 00:49:05,330 mengklaim bahwa trie adalah. 1094 00:49:05,330 --> 00:49:09,810 Bahkan, tabel hash mungkin sangat baik terbukti jauh lebih efisien. 1095 00:49:09,810 --> 00:49:10,830 Tetapi mereka hanya - 1096 00:49:10,830 --> 00:49:14,620 itu hanya salah satu keputusan desain Anda akan harus membuat. 1097 00:49:14,620 --> 00:49:18,920 >> Namun dalam penutupan mari kita 50 atau lebih detik untuk mengintip apa yang ada di 1098 00:49:18,920 --> 00:49:22,190 depan minggu depan dan seterusnya kita transisi dari baris perintah ini 1099 00:49:22,190 --> 00:49:26,220 dunia jika program C untuk hal-hal web berbasis dan bahasa seperti PHP dan 1100 00:49:26,220 --> 00:49:30,350 JavaScript dan internet itu sendiri, protokol seperti HTTP, yang Anda sudah 1101 00:49:30,350 --> 00:49:32,870 diambil untuk diberikan selama bertahun-tahun sekarang, dan diketik paling setiap 1102 00:49:32,870 --> 00:49:34,440 hari, mungkin, atau dilihat. 1103 00:49:34,440 --> 00:49:37,420 Dan kita akan mulai mengupas lapisan apa internet. 1104 00:49:37,420 --> 00:49:40,650 Dan apa kode yang mendasari alat hari ini. 1105 00:49:40,650 --> 00:49:43,230 Jadi 50 detik teaser ini di sini. 1106 00:49:43,230 --> 00:49:46,570 Aku memberikan Laskar Net. 1107 00:49:46,570 --> 00:49:51,370 >> [VIDEO PEMUTARAN] 1108 00:49:51,370 --> 00:49:56,764 >> -Dia datang dengan pesan. 1109 00:49:56,764 --> 00:50:00,687 Dengan protokol semua sendiri. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 Dia datang ke dunia firewall kejam, tidak peduli router, dan bahaya yang jauh 1112 00:50:19,780 --> 00:50:22,600 lebih buruk daripada kematian. 1113 00:50:22,600 --> 00:50:23,590 Dia cepat. 1114 00:50:23,590 --> 00:50:25,300 Dia kuat. 1115 00:50:25,300 --> 00:50:27,700 Dia TCPIP. 1116 00:50:27,700 --> 00:50:30,420 Dan dia punya alamat Anda. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Warriors of Net. 1119 00:50:34,590 --> 00:50:35,290 >> [END VIDEO PEMUTARAN] 1120 00:50:35,290 --> 00:50:38,070 >> SPEAKER 1: Itu adalah bagaimana internet akan bekerja pada minggu depan. 1121 00:50:38,070 --> 00:50:40,406