1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> SPEAKER 1: Baiklah, jadi kita balik. 3 00:00:13,120 --> 00:00:14,480 Selamat datang ke CS50. 4 00:00:14,480 --> 00:00:16,510 Ini adalah hujung minggu tujuh. 5 00:00:16,510 --> 00:00:20,200 Jadi ingat bahawa masa lalu, kami mula melihat yang lebih canggih 6 00:00:20,200 --> 00:00:21,100 struktur data. 7 00:00:21,100 --> 00:00:25,110 Sejak sehingga kini, semua kita telah benar-benar di tangan kita adalah ini, array. 8 00:00:25,110 --> 00:00:29,340 >> Tetapi sebelum kita membuang pelbagai tidak apa yang menarik, yang sememangnya ia 9 00:00:29,340 --> 00:00:33,570 sebenarnya, apa yang adalah sebahagian daripada plus ini data mudah 10 00:00:33,570 --> 00:00:34,560 struktur setakat ini? 11 00:00:34,560 --> 00:00:36,110 Apakah ia baik? 12 00:00:36,110 --> 00:00:39,450 Setakat yang kita lihat? 13 00:00:39,450 --> 00:00:42,540 Apa yang anda dapat? 14 00:00:42,540 --> 00:00:44,028 Tiada apa-apa. 15 00:00:44,028 --> 00:00:45,020 >> PELAJAR: [didengar]. 16 00:00:45,020 --> 00:00:45,395 >> SPEAKER 1: Apakah itu? 17 00:00:45,395 --> 00:00:46,410 >> PELAJAR: [didengar]. 18 00:00:46,410 --> 00:00:47,000 >> SPEAKER 1 saiz tetap. 19 00:00:47,000 --> 00:00:51,260 OK, jadi mengapa adalah saiz tetap baik walaupun? 20 00:00:51,260 --> 00:00:53,180 >> PELAJAR: [didengar]. 21 00:00:53,180 --> 00:00:56,240 >> SPEAKER 1: OK, jadi ia berkesan dalam erti kata bahawa anda boleh memperuntukkan 22 00:00:56,240 --> 00:01:00,070 jumlah tetap ruang, yang diharapkan adalah tepat sebanyak 23 00:01:00,070 --> 00:01:01,180 ruang yang anda mahu. 24 00:01:01,180 --> 00:01:02,720 Jadi yang boleh menjadi benar-benar ditambah. 25 00:01:02,720 --> 00:01:06,530 >> Apa lagi sampingan daripada array? 26 00:01:06,530 --> 00:01:07,610 Ya? 27 00:01:07,610 --> 00:01:08,750 >> PELAJAR: [didengar]. 28 00:01:08,750 --> 00:01:09,550 >> SPEAKER 1: Semua - maaf? 29 00:01:09,550 --> 00:01:11,270 >> PELAJAR [didengar]. 30 00:01:11,270 --> 00:01:13,620 >> SPEAKER 1: Semua tempat dalam ingatan atau di sebelah satu sama lain. 31 00:01:13,620 --> 00:01:15,220 Dan yang membantu - mengapa? 32 00:01:15,220 --> 00:01:15,970 Itu agak benar. 33 00:01:15,970 --> 00:01:18,611 Tetapi bagaimana kita boleh mengeksploitasi kebenaran itu? 34 00:01:18,611 --> 00:01:21,500 >> PELAJAR: [didengar]. 35 00:01:21,500 --> 00:01:24,490 >> SPEAKER 1: Tepat sekali, kita dapat mengesan di mana segala-galanya hanya dengan mengetahui 36 00:01:24,490 --> 00:01:28,560 satu alamat, iaitu alamat bait pertama yang sebahagian memori. 37 00:01:28,560 --> 00:01:30,420 Atau dalam kes tali, alamat yang pertama 38 00:01:30,420 --> 00:01:31,460 char dalam rentetan itu. 39 00:01:31,460 --> 00:01:33,330 Dan dari situ, kita boleh mencari hujung tali. 40 00:01:33,330 --> 00:01:35,710 Kita boleh mencari unsur kedua, Elemen ketiga, dan sebagainya. 41 00:01:35,710 --> 00:01:38,740 >> Dan sebagainya cara mewah untuk menggambarkan bahawa ciri adalah yang memberikan kita array 42 00:01:38,740 --> 00:01:40,020 capaian rawak. 43 00:01:40,020 --> 00:01:44,330 Hanya dengan menggunakan kurungan persegi makluman dan nombor, anda boleh melompat ke 44 00:01:44,330 --> 00:01:48,070 elemen tertentu dalam pelbagai dalam masa yang berterusan, besar O 45 00:01:48,070 --> 00:01:49,810 satu, jadi untuk bercakap. 46 00:01:49,810 --> 00:01:51,080 >> Tetapi ada beberapa kelemahan. 47 00:01:51,080 --> 00:01:53,110 Apa array tidak sangat mudah? 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 Apakah ia tidak baik pada? 50 00:01:57,170 --> 00:01:58,810 >> PELAJAR: [didengar]. 51 00:01:58,810 --> 00:01:59,860 >> SPEAKER 1: Apakah itu? 52 00:01:59,860 --> 00:02:00,530 >> PELAJAR [didengar]. 53 00:02:00,530 --> 00:02:01,460 >> SPEAKER 1: Mengembangkan dalam saiz. 54 00:02:01,460 --> 00:02:04,800 Jadi kelemahan pelbagai adalah tepat bertentangan dengan apa yang 55 00:02:04,800 --> 00:02:05,540 upsides berada. 56 00:02:05,540 --> 00:02:07,610 Jadi salah satu kelemahan adalah bahawa ia adalah saiz yang tetap. 57 00:02:07,610 --> 00:02:09,400 Jadi anda tidak boleh benar-benar ia berkembang. 58 00:02:09,400 --> 00:02:13,510 Anda boleh mengagihkan semula sebahagian yang lebih besar ingatan, dan kemudian bergerak unsur-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 pelbagai lama, untuk Contohnya, dengan menggunakan malloc atau serupa 61 00:02:18,060 --> 00:02:21,180 fungsi dipanggil realloc, yang ingatan reallocates. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, sebagai diketepikan, cuba untuk memberikan anda memori yang bersebelahan pelbagai 63 00:02:25,490 --> 00:02:26,610 yang anda sudah mempunyai. 64 00:02:26,610 --> 00:02:28,740 Tetapi ia mungkin perkara-perkara yang bergerak sekitar sama sekali. 65 00:02:28,740 --> 00:02:30,710 Tetapi dalam jangka pendek, itu mahal, kan? 66 00:02:30,710 --> 00:02:33,440 Kerana jika anda mempunyai sebahagian daripada ingatan saiz ini, tetapi anda benar-benar mahu satu 67 00:02:33,440 --> 00:02:36,710 saiz ini, dan anda mahu mengekalkan unsur-unsur asal, anda perlu 68 00:02:36,710 --> 00:02:40,510 kira-kira satu masa proses penyalinan linear yang perlu berlaku dari 69 00:02:40,510 --> 00:02:41,900 pelbagai lama ke baru. 70 00:02:41,900 --> 00:02:44,630 Dan realiti meminta operasi sistem lagi dan lagi dan 71 00:02:44,630 --> 00:02:48,340 lagi untuk ketulan besar memori boleh memulakan kos anda sedikit masa juga. 72 00:02:48,340 --> 00:02:52,250 Jadi ia adalah kedua-dua satu rahmat dan kutuk di menyamar, hakikat bahawa array 73 00:02:52,250 --> 00:02:53,860 mempunyai saiz tetap. 74 00:02:53,860 --> 00:02:56,790 Tetapi jika kita memperkenalkan dan bukannya sesuatu seperti ini, yang kita dipanggil berkaitan 75 00:02:56,790 --> 00:03:00,580 senarai, kita akan mendapat upsides dan beberapa satu kelemahan beberapa di sini juga. 76 00:03:00,580 --> 00:03:05,780 >> Jadi senarai yang dikaitkan hanya satu data struktur terdiri daripada C structs dalam 77 00:03:05,780 --> 00:03:09,850 kes, di mana struct, ingat, hanya bekas untuk satu atau lebih khusus 78 00:03:09,850 --> 00:03:11,100 jenis pembolehubah. 79 00:03:11,100 --> 00:03:16,110 Dalam kes ini, apa yang jenis data kelihatan dalam struct yang 80 00:03:16,110 --> 00:03:17,600 Kali terakhir kita dipanggil nod? 81 00:03:17,600 --> 00:03:19,380 Setiap segi empat tepat adalah nod. 82 00:03:19,380 --> 00:03:22,660 Dan setiap segi empat tepat kecil di dalamnya adalah sejenis data. 83 00:03:22,660 --> 00:03:25,300 Apakah jenis-jenis yang kita katakan mereka pada hari Isnin? 84 00:03:25,300 --> 00:03:26,478 Ya? 85 00:03:26,478 --> 00:03:27,870 >> PELAJAR: [didengar]. 86 00:03:27,870 --> 00:03:30,721 >> SPEAKER 1: A berubah dan penunjuk, atau lebih khusus, int, bagi n, 87 00:03:30,721 --> 00:03:32,180 dan penunjuk di bahagian bawah. 88 00:03:32,180 --> 00:03:35,360 Kedua-dua mereka berada 32 bit, pada kurangnya pada komputer seperti ini CS50 89 00:03:35,360 --> 00:03:37,980 Perkakas, dan supaya mereka berada disediakan sama dalam saiz. 90 00:03:37,980 --> 00:03:42,260 >> Jadi apa yang menggunakan penunjuk walaupun untuk nampaknya? 91 00:03:42,260 --> 00:03:47,690 Mengapa menambah arrow ini sekarang apabila array adalah begitu baik dan bersih, dan mudah? 92 00:03:47,690 --> 00:03:50,460 Apakah penunjuk lakukan untuk kita dalam setiap nod ini? 93 00:03:50,460 --> 00:03:52,160 >> PELAJAR: [didengar]. 94 00:03:52,160 --> 00:03:52,465 >> SPEAKER 1: Tepat sekali. 95 00:03:52,465 --> 00:03:54,120 Ia memberitahu anda di mana yang seterusnya adalah. 96 00:03:54,120 --> 00:03:57,350 Jadi saya jenis menggunakan analogi menggunakan benang untuk menyusun daripada 97 00:03:57,350 --> 00:03:59,180 thread nod ini bersama-sama. 98 00:03:59,180 --> 00:04:01,760 Dan itulah apa yang kami lakukan dengan petunjuk kerana masing-masing 99 00:04:01,760 --> 00:04:06,360 ketulan memori mungkin atau mungkin tidak berdampingan, kembali ke belakang untuk menyokong 100 00:04:06,360 --> 00:04:09,500 dalam RAM, kerana setiap kali anda memanggil malloc berkata, memberikan saya cukup 101 00:04:09,500 --> 00:04:12,510 bait untuk nod baru, ia mungkin berada di sini atau ia mungkin berada di sini. 102 00:04:12,510 --> 00:04:13,120 Ia mungkin berada di sini. 103 00:04:13,120 --> 00:04:13,730 Ia mungkin berada 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 petunjuk di alamat mereka nod, anda boleh menjahit mereka 106 00:04:17,880 --> 00:04:22,370 bersama-sama dengan cara yang kelihatan visual seperti senarai walaupun perkara-perkara ini adalah 107 00:04:22,370 --> 00:04:26,770 semua tersebar di seluruh satu atau anda dua atau empat gigabait anda RAM 108 00:04:26,770 --> 00:04:28,760 di dalam komputer anda sendiri. 109 00:04:28,760 --> 00:04:33,230 >> Jadi keburukan, maka, daripada senarai yang dikaitkan adalah apa? 110 00:04:33,230 --> 00:04:34,670 Apakah harga yang kami nampaknya membayar? 111 00:04:34,670 --> 00:04:36,010 >> PELAJAR: [didengar]. 112 00:04:36,010 --> 00:04:36,920 >> SPEAKER 1: Lebih banyak ruang, bukan? 113 00:04:36,920 --> 00:04:39,340 Kami telah, dalam kes ini, dua kali ganda jumlah ruang kerana kita telah pergi 114 00:04:39,340 --> 00:04:43,500 daripada 32 bit untuk setiap nod, bagi setiap int, jadi sekarang 64 bit sebab kita perlu 115 00:04:43,500 --> 00:04:45,050 menyimpan sekitar penunjuk juga. 116 00:04:45,050 --> 00:04:48,860 Anda mendapatkan kecekapan yang lebih jika anda struct adalah lebih besar daripada perkara ini mudah. 117 00:04:48,860 --> 00:04:52,020 Jika anda benar-benar mempunyai pelajar di dalam yang merupakan beberapa rentetan untuk 118 00:04:52,020 --> 00:04:55,430 nama dan rumah, mungkin nombor ID, mungkin beberapa bidang lain sama sekali. 119 00:04:55,430 --> 00:04:59,000 >> Jadi, jika anda mempunyai struct cukup besar, maka mungkin kos penunjuk adalah 120 00:04:59,000 --> 00:05:00,010 tidak apa-apa masalah besar. 121 00:05:00,010 --> 00:05:03,570 Ini adalah sedikit kes sudut dalam yang kita menyimpan apa-apa yang mudah primitif 122 00:05:03,570 --> 00:05:04,760 dalam senarai berkaitan. 123 00:05:04,760 --> 00:05:05,790 Tetapi persoalannya adalah sama. 124 00:05:05,790 --> 00:05:08,230 Sedang anda pasti berbelanja lebih memori, tetapi anda mendapat 125 00:05:08,230 --> 00:05:08,990 fleksibiliti. 126 00:05:08,990 --> 00:05:12,280 Kerana sekarang jika saya ingin menambah satu elemen pada awal senarai ini, 127 00:05:12,280 --> 00:05:14,340 Saya perlu memperuntukkan nod baru. 128 00:05:14,340 --> 00:05:17,180 Dan saya hanya perlu mengemas kini panah entah bagaimana dengan hanya bergerak 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-tengah senarai, saya tidak perlu 131 00:05:20,580 --> 00:05:24,410 menolak semua orang selain seperti yang kita lakukan pada lepas minggu dengan sukarelawan kita yang 132 00:05:24,410 --> 00:05:25,700 diwakili array. 133 00:05:25,700 --> 00:05:29,470 Saya hanya boleh memperuntukkan nod baru dan kemudian hanya menunjukkan anak panah dalam 134 00:05:29,470 --> 00:05:32,290 arah yang berbeza kerana ia tidak perlu kekal dalam sebenar 135 00:05:32,290 --> 00:05:35,670 memori talian benar seperti saya telah disediakan di sini pada skrin. 136 00:05:35,670 --> 00:05:38,400 >> Kemudian akhir sekali, jika anda mahu untuk memasukkan sesuatu yang pada akhir senarai, ia 137 00:05:38,400 --> 00:05:39,210 lebih mudah. 138 00:05:39,210 --> 00:05:43,320 Ini adalah sejenis notasi sewenang-wenangnya, tetapi penunjuk 34 ini, mengambil tekaan. 139 00:05:43,320 --> 00:05:46,710 Apakah nilai penunjuk yang paling apapun yang mungkin dilukis seperti lama 140 00:05:46,710 --> 00:05:47,700 antena sekolah di sana? 141 00:05:47,700 --> 00:05:48,920 >> PELAJAR: [didengar]. 142 00:05:48,920 --> 00:05:49,900 >> SPEAKER 1: Ia mungkin null. 143 00:05:49,900 --> 00:05:52,710 Dan sesungguhnya yang merupakan salah satu pengarang perwakilan null. 144 00:05:52,710 --> 00:05:56,310 Dan ia batal kerana anda benar-benar perlu tahu di mana hujung berkaitan 145 00:05:56,310 --> 00:06:00,050 senarai adalah, supaya anda menyimpan berikut dan mengikuti dan mengikuti anak panah 146 00:06:00,050 --> 00:06:01,170 untuk beberapa nilai sampah. 147 00:06:01,170 --> 00:06:06,230 Jadi null akan menandakan bahawa tidak ada lebih nod di sebelah kanan nombor 34, 148 00:06:06,230 --> 00:06:07,200 dalam kes ini. 149 00:06:07,200 --> 00:06:10,270 >> Jadi kita mencadangkan supaya kita boleh melaksanakan nod ini dalam kod. 150 00:06:10,270 --> 00:06:12,130 Dan kita telah melihat ini jenis sintaks sebelum ini. 151 00:06:12,130 --> 00:06:15,090 Typedef hanya mentakrifkan jenis baru untuk kita, memberikan kita sinonim seperti 152 00:06:15,090 --> 00:06:17,100 tali adalah untuk char *. 153 00:06:17,100 --> 00:06:21,030 Dalam kes ini, ia akan memberi kita notasi trengkas supaya nod struct 154 00:06:21,030 --> 00:06:24,010 boleh bukan hanya ditulis sebagai nod, yang lebih bersih banyak. 155 00:06:24,010 --> 00:06:25,360 Ia banyak kurang lantung. 156 00:06:25,360 --> 00:06:30,080 >> Di dalam nod nampaknya int dipanggil n, dan kemudian nod struct * 157 00:06:30,080 --> 00:06:34,670 yang bermaksud apa yang kita mahu anak panah untuk bermakna, penunjuk yang lain 158 00:06:34,670 --> 00:06:36,940 nod yang tepat jenis data yang sama. 159 00:06:36,940 --> 00:06:40,300 Dan saya mencadangkan supaya kita boleh melaksanakan fungsi carian seperti ini, yang pada 160 00:06:40,300 --> 00:06:41,890 pandangan pertama mungkin kelihatan kompleks sedikit. 161 00:06:41,890 --> 00:06:43,330 Tetapi mari kita lihat dalam konteks. 162 00:06:43,330 --> 00:06:45,480 >> Biar saya pergi ke perkakas di sini. 163 00:06:45,480 --> 00:06:48,460 Izinkan saya membuka fail yang dipanggil senarai sifar dot h. 164 00:06:48,460 --> 00:06:53,950 Dan itu hanya mengandungi definisi yang kita hanya melihat masa lalu untuk data ini 165 00:06:53,950 --> 00:06:55,390 Jenis dipanggil nod. 166 00:06:55,390 --> 00:06:57,350 Jadi kami telah meletakkan ke dalam titik h fail. 167 00:06:57,350 --> 00:07:01,430 >> Dan sebagai diketepikan, walaupun ini program yang anda kira-kira untuk melihat adalah 168 00:07:01,430 --> 00:07:05,410 tidak semua kompleks itu, ia memang konvensyen semasa menulis program untuk 169 00:07:05,410 --> 00:07:10,270 meletakkan perkara-perkara seperti jenis data, untuk menarik pemalar kadang-kadang, di dalam anda 170 00:07:10,270 --> 00:07:13,210 file kepala dan tidak semestinya dalam file C anda, sudah tentu apabila anda 171 00:07:13,210 --> 00:07:17,370 program mendapatkan yang lebih besar dan lebih besar, supaya anda tahu di mana untuk melihat kedua-dua 172 00:07:17,370 --> 00:07:20,840 dokumentasi dalam kes-kes tertentu, atau untuk asas-asas seperti ini, 173 00:07:20,840 --> 00:07:22,360 definisi jenis tertentu. 174 00:07:22,360 --> 00:07:25,680 >> Jika saya kini membuka senarai sifar dot c, perhatikan beberapa perkara. 175 00:07:25,680 --> 00:07:29,090 Ia termasuk beberapa fail header, kebanyakan yang kita lihat sebelum ini. 176 00:07:29,090 --> 00:07:31,980 Ia termasuk fail header sendiri. 177 00:07:31,980 --> 00:07:35,200 >> Dan sebagai diketepikan, mengapa itu dua sebut di sini, berbanding dengan sudut 178 00:07:35,200 --> 00:07:38,340 kurungan pada baris yang Saya menekankan di sana? 179 00:07:38,340 --> 00:07:39,180 >> PELAJAR: [didengar]. 180 00:07:39,180 --> 00:07:40,460 >> SPEAKER 1: Ya, jadi ini adalah fail tempatan. 181 00:07:40,460 --> 00:07:44,300 Jadi, jika ia adalah fail tempatan anda sendiri di sini on line 15, misalnya, anda menggunakan 182 00:07:44,300 --> 00:07:46,570 petikan berganda bukannya daripada kurungan sudut. 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 bahawa saya telah mengisytiharkan global berubah-ubah dalam program ini on line 18 185 00:07:51,830 --> 00:07:55,910 dipanggil pertama, idea itu ini akan menjadi penunjuk kepada yang pertama 186 00:07:55,910 --> 00:07:59,190 nod dalam senarai berkaitan saya, dan saya dimulakan untuk menyeimbangkan, kerana saya telah 187 00:07:59,190 --> 00:08:02,310 tidak diperuntukkan mana-mana sebenar nod hanya lagi. 188 00:08:02,310 --> 00:08:07,570 >> Jadi ini merupakan, bergambar, apa yang kita melihat masa lalu di gambar sebagai 189 00:08:07,570 --> 00:08:10,090 bahawa penunjuk di hujung bahagian kiri. 190 00:08:10,090 --> 00:08:12,260 Jadi sekarang, penunjuk yang tidak mempunyai anak panah. 191 00:08:12,260 --> 00:08:14,590 Ia bukan hanya null. 192 00:08:14,590 --> 00:08:17,880 Tetapi ia mewakili apa yang akan menjadi alamat pertama yang sebenarnya 193 00:08:17,880 --> 00:08:19,480 nod dalam senarai ini. 194 00:08:19,480 --> 00:08:22,120 Jadi saya telah dilaksanakan ia adalah global kerana, seperti yang anda akan lihat, semua ini 195 00:08:22,120 --> 00:08:25,310 program tidak dalam hidup adalah melaksanakan senarai dikaitkan bagi saya. 196 00:08:25,310 --> 00:08:27,050 >> Sekarang saya telah mendapat beberapa prototaip sini. 197 00:08:27,050 --> 00:08:31,190 Saya membuat keputusan untuk melaksanakan ciri-ciri seperti penghapusan, memasukkan, mencari, dan 198 00:08:31,190 --> 00:08:31,740 traversal - 199 00:08:31,740 --> 00:08:35,210 lalu hanya menjadi berjalan di seluruh senarai, mencetak unsur-unsur. 200 00:08:35,210 --> 00:08:36,750 Dan kini di sini adalah rutin utama saya. 201 00:08:36,750 --> 00:08:39,890 Dan kita tidak akan menghabiskan terlalu banyak masa pada ini kerana ini adalah jenis, mudah-mudahan 202 00:08:39,890 --> 00:08:41,780 topi lama oleh sekarang. 203 00:08:41,780 --> 00:08:45,370 >> Saya akan melakukan yang berikut, sementara pengguna bekerjasama. 204 00:08:45,370 --> 00:08:47,300 Jadi, satu, saya akan mencetak daripada menu ini. 205 00:08:47,300 --> 00:08:49,420 Dan saya telah diformat sebagai bersih seperti yang saya boleh. 206 00:08:49,420 --> 00:08:52,240 Jika jenis pengguna dalam satu, ini bermakna mereka mahu memadam sesuatu. 207 00:08:52,240 --> 00:08:54,560 Jika jenis pengguna dalam dua, yang bermakna mereka mahu untuk memasukkan sesuatu. 208 00:08:54,560 --> 00:08:55,930 Dan sebagainya. 209 00:08:55,930 --> 00:08:58,270 Saya akan kemudian meminta maka untuk perintah. 210 00:08:58,270 --> 00:08:59,300 Dan kemudian saya akan menggunakan GetInt. 211 00:08:59,300 --> 00:09:02,790 >> Jadi ini adalah benar-benar mudah menuing muka di mana anda hanya perlu menaip 212 00:09:02,790 --> 00:09:05,270 pemetaan nombor untuk satu mereka arahan. 213 00:09:05,270 --> 00:09:08,730 Dan kini saya mempunyai suis yang bersih baik kenyataan yang akan menghidupkan 214 00:09:08,730 --> 00:09:10,090 apa pengguna ditaip masuk 215 00:09:10,090 --> 00:09:12,180 Dan jika mereka ditaip satu demi satu, saya akan memanggil memadam dan pecah. 216 00:09:12,180 --> 00:09:14,380 Jika mereka ditaip dua, saya akan memanggil memasukkan dan pecah. 217 00:09:14,380 --> 00:09:16,490 >> Dan kini notis saya telah setiap ini di barisan yang sama. 218 00:09:16,490 --> 00:09:18,360 Ini adalah satu keputusan yang 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 Tetapi saya hanya membuat keputusan, terus-terang, program saya kelihatan lebih mudah dibaca kerana 221 00:09:23,260 --> 00:09:25,980 ia adalah hanya empat kes untuk hanya senarai ia seperti ini. 222 00:09:25,980 --> 00:09:28,360 Penggunaan sepenuhnya sah gaya. 223 00:09:28,360 --> 00:09:31,480 Dan saya akan melakukan ini selagi pengguna tidak ditaip sifar, yang saya 224 00:09:31,480 --> 00:09:33,910 memutuskan akan bermakna mereka mahu berhenti. 225 00:09:33,910 --> 00:09:36,630 >> Jadi sekarang melihat apa yang saya akan dilakukan di sini. 226 00:09:36,630 --> 00:09:38,650 Saya akan membebaskan senarai nampaknya. 227 00:09:38,650 --> 00:09:40,230 Tetapi lebih kepada yang dalam hanya seketika. 228 00:09:40,230 --> 00:09:41,640 Mari kita mula-mula menjalankan program ini. 229 00:09:41,640 --> 00:09:45,250 Jadi biarlah saya membuat terminal yang lebih besar tingkap, dot slash senarai 0. 230 00:09:45,250 --> 00:09:49,510 Saya akan pergi ke hadapan dan memasukkan oleh menaip dua, beberapa seperti 50, dan kini 231 00:09:49,510 --> 00:09:51,590 anda akan melihat senarai kini 50. 232 00:09:51,590 --> 00:09:53,380 Dan teks saya hanya menatal sedikit. 233 00:09:53,380 --> 00:09:55,940 Jadi sekarang melihat senarai mengandungi nombor 50. 234 00:09:55,940 --> 00:09:58,220 >> Mari kita buat memasukkan satu lagi dengan mengambil dua. 235 00:09:58,220 --> 00:10:01,630 Mari menaip nombor seperti satu. 236 00:10:01,630 --> 00:10:03,940 Senarai kini merupakan salah satu, diikuti oleh 50. 237 00:10:03,940 --> 00:10:06,020 Jadi ini adalah hanya perwakilan teks senarai. 238 00:10:06,020 --> 00:10:10,550 Dan mari kita memasukkan nombor satu lebih seperti nombor 42, yang diharapkan 239 00:10:10,550 --> 00:10:14,620 akan berakhir di tengah-tengah, kerana program ini dalam pelbagai tertentu ia 240 00:10:14,620 --> 00:10:16,320 unsur-unsur kerana ia memasukkan mereka. 241 00:10:16,320 --> 00:10:17,220 Jadi kita ada. 242 00:10:17,220 --> 00:10:20,730 Program Super mudah yang boleh benar-benar telah menggunakan pelbagai, tetapi saya 243 00:10:20,730 --> 00:10:23,280 berlaku untuk menggunakan senarai yang berkaitan hanya jadi saya boleh dinamik 244 00:10:23,280 --> 00:10:24,610 berkembang dan mengecut ia. 245 00:10:24,610 --> 00:10:28,470 >> Jadi mari kita lihat carian, jika saya menjalankan arahan tiga, saya mahu mencari 246 00:10:28,470 --> 00:10:31,040 untuk, katakan, nombor 43. 247 00:10:31,040 --> 00:10:34,190 Dan tiada apa yang nampaknya dijumpai, kerana saya pulang tiada jawapan. 248 00:10:34,190 --> 00:10:35,010 Jadi mari kita buat ini lagi. 249 00:10:35,010 --> 00:10:35,690 Mencari. 250 00:10:35,690 --> 00:10:39,520 Mari kita cari 50, atau lebih tepat mencari 42, yang mempunyai yang bagus 251 00:10:39,520 --> 00:10:40,850 makna halus sedikit. 252 00:10:40,850 --> 00:10:42,610 Dan saya dapati makna kehidupan di sana. 253 00:10:42,610 --> 00:10:44,990 Bilangan 42, jika anda tidak tahu rujukan, Google ia. 254 00:10:44,990 --> 00:10:45,350 Baiklah. 255 00:10:45,350 --> 00:10:47,130 Jadi apa yang program ini dilakukan untuk saya? 256 00:10:47,130 --> 00:10:50,660 Ia hanya membenarkan saya untuk memasukkan itu jauh dan mencari unsur-unsur. 257 00:10:50,660 --> 00:10:53,650 >> Mari kita cepat ke hadapan, kemudian, untuk bahawa fungsi kita memandang pada 258 00:10:53,650 --> 00:10:55,360 pada hari Isnin sebagai memujuknya. 259 00:10:55,360 --> 00:10:59,620 Jadi fungsi ini, saya menuntut, mencari satu elemen dalam senarai dengan terlebih dahulu 260 00:10:59,620 --> 00:11:03,830 satu, menyebabkan pengguna dan kemudian memanggil GetInt untuk mendapatkan int sebenar 261 00:11:03,830 --> 00:11:05,060 yang anda mahu mencari. 262 00:11:05,060 --> 00:11:06,460 >> Kemudian notis ini. 263 00:11:06,460 --> 00:11:10,690 Saya akan membuat ubah sementara sejajar 188 dipanggil penunjuk - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 boleh memanggilnya apa-apa. 266 00:11:12,440 --> 00:11:16,140 Dan ia adalah penunjuk kepada nod kerana saya berkata nod * sana. 267 00:11:16,140 --> 00:11:19,900 Dan saya Memulakan ia menjadi sama dengan terlebih dahulu supaya saya berkesan mempunyai saya 268 00:11:19,900 --> 00:11:22,860 jari, jadi untuk bercakap, di sangat Elemen pertama dalam senarai itu. 269 00:11:22,860 --> 00:11:27,460 Jadi, jika tangan kanan saya di sini adalah PTR Saya menghala ke arah perkara yang sama yang pertama 270 00:11:27,460 --> 00:11:28,670 yang menghala ke arah. 271 00:11:28,670 --> 00:11:31,430 >> Jadi kini kembali kod, apa yang berlaku seterusnya - 272 00:11:31,430 --> 00:11:35,070 ini adalah paradigma biasa apabila iterating atas struktur seperti 273 00:11:35,070 --> 00:11:35,970 senarai berkaitan. 274 00:11:35,970 --> 00:11:40,410 Saya akan melakukan perkara berikut semasa penunjuk tidak sama untuk menyeimbangkan itu, sambil 275 00:11:40,410 --> 00:11:47,530 jari saya tidak menghala ke arah beberapa null nilai, jika penunjuk arrow n sama n. 276 00:11:47,530 --> 00:11:52,290 Kami akan notis pertama yang n adalah apa yang pengguna ditaip dalam setiap GetInts hubungi di sini. 277 00:11:52,290 --> 00:11:54,280 >> Dan penunjuk arrow n bermaksud apa? 278 00:11:54,280 --> 00:11:59,020 Baik jika kita kembali kepada gambar di sini, jika saya mempunyai jari menghala ke arah 279 00:11:59,020 --> 00:12:02,960 nod yang pertama yang mengandungi sembilan, yang arrow asasnya bermakna pergi ke bahawa 280 00:12:02,960 --> 00:12:08,860 nod dan merebut nilai di lokasi n, dalam hal ini, medan data yang dipanggil n. 281 00:12:08,860 --> 00:12:14,120 >> Sebagai mengetepikan - dan kita melihat ini pasangan minggu lalu apabila seseorang bertanya - 282 00:12:14,120 --> 00:12:18,840 sintaks ini adalah baru, tetapi ia tidak memberi kita kuasa yang kita 283 00:12:18,840 --> 00:12:20,040 tidak sudah mempunyai. 284 00:12:20,040 --> 00:12:25,325 Apakah ungkapan ini bersamaan dengan menggunakan dot makluman dan bintang pasangan 285 00:12:25,325 --> 00:12:29,490 minggu lalu apabila kita dikupas kembali lapisan ini agak terlalu awal? 286 00:12:29,490 --> 00:12:31,780 >> PELAJAR: [didengar]. 287 00:12:31,780 --> 00:12:38,880 >> SPEAKER 1: Tepat sekali, ia adalah bintang, dan maka ia adalah bintang dot n, dengan 288 00:12:38,880 --> 00:12:41,930 kurungan di sini, yang kelihatan, terus-terang, saya berfikir banyak 289 00:12:41,930 --> 00:12:43,320 lebih samar untuk dibaca. 290 00:12:43,320 --> 00:12:46,270 Tetapi penunjuk bintang, seperti biasa, cara pergi ke sana. 291 00:12:46,270 --> 00:12:49,090 Dan apabila anda berada di sana, apa yang data bidang yang anda mahu untuk mengakses? 292 00:12:49,090 --> 00:12:52,730 Baik anda menggunakan notasi dot untuk mengakses medan data structs, dan saya 293 00:12:52,730 --> 00:12:54,140 khusus mahu n. 294 00:12:54,140 --> 00:12:56,240 >> Terus terang, saya akan berhujah ini hanya sukar untuk dibaca. 295 00:12:56,240 --> 00:12:58,080 Ia adalah sukar untuk ingat di mana jangan kurungan pergi, 296 00:12:58,080 --> 00:12:59,030 bintang dan semua itu. 297 00:12:59,030 --> 00:13:02,150 Jadi dunia telah menerima pakai beberapa sintaktik gula, jadi untuk bercakap. 298 00:13:02,150 --> 00:13:04,740 Hanya satu cara seksi berkata, ini adalah setaraf, dan 299 00:13:04,740 --> 00:13:05,970 mungkin lebih intuitif. 300 00:13:05,970 --> 00:13:09,600 Jika penunjuk merupakan penunjuk, yang arrow notasi cara pergi ke sana dan mendapati 301 00:13:09,600 --> 00:13:11,890 bidang dalam kes ini dipanggil n. 302 00:13:11,890 --> 00:13:13,660 >> Jadi jika saya merasa, melihat apa yang saya lakukan. 303 00:13:13,660 --> 00:13:17,430 Saya hanya mencetak, saya mendapati peratus i, memasang dalam nilai untuk int itu. 304 00:13:17,430 --> 00:13:20,730 Saya menyeru tidur untuk kedua hanya untuk jenis perkara yang berhenti pada skrin untuk 305 00:13:20,730 --> 00:13:22,900 memberi pengguna kedua untuk menyerap apa sahaja yang berlaku. 306 00:13:22,900 --> 00:13:24,290 Dan kemudian saya memecahkan. 307 00:13:24,290 --> 00:13:26,330 Jika tidak, apa yang saya lakukan? 308 00:13:26,330 --> 00:13:30,960 Saya kini penunjuk kepada sama penunjuk arrow depan. 309 00:13:30,960 --> 00:13:35,840 >> Jadi hanya perlu jelas, ini bermakna pergi ada, dengan menggunakan notasi lama sekolah saya. 310 00:13:35,840 --> 00:13:39,580 Jadi ini hanya bermaksud untuk pergi ke apa-apa anda menghala ke arah, yang sangat 311 00:13:39,580 --> 00:13:43,660 Kes pertama adalah saya menghala ke arah struct dengan sembilan di dalamnya. 312 00:13:43,660 --> 00:13:44,510 Jadi saya telah pergi ke sana. 313 00:13:44,510 --> 00:13:47,880 Dan kemudian notasi dot bermakna, mendapat nilai di depan. 314 00:13:47,880 --> 00:13:50,470 >> Tetapi nilai itu, walaupun ia telah disediakan sebagai sempit, hanya nombor. 315 00:13:50,470 --> 00:13:51,720 Ia adalah satu alamat angka. 316 00:13:51,720 --> 00:13:55,670 Jadi garis ini satu kod, sama ada ditulis begini, lebih samar 317 00:13:55,670 --> 00:14:00,190 cara, atau seperti ini, lebih sedikit cara intuitif, hanya bermaksud menggerakkan tangan saya 318 00:14:00,190 --> 00:14:03,460 dari nod pertama yang akan datang, dan kemudian yang seterusnya, dan kemudian 319 00:14:03,460 --> 00:14:05,320 datang satu, dan sebagainya. 320 00:14:05,320 --> 00:14:09,920 >> Oleh itu, kita tidak akan kekal di pihak yang lain perlaksanaan memasukkan dan memadam 321 00:14:09,920 --> 00:14:14,030 dan traversal, kedua-dua pertama yang terlibat secara adil. 322 00:14:14,030 --> 00:14:17,010 Dan saya fikir ia agak mudah untuk mendapatkan hilang apabila melakukannya secara lisan. 323 00:14:17,010 --> 00:14:19,890 Tetapi apa yang kita boleh lakukan di sini adalah cuba 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 Kerana saya akan mencadangkan bahawa jika kita mahu memasukkan unsur-unsur ini ke dalam 326 00:14:24,800 --> 00:14:26,680 senarai yang sedia ada, yang mempunyai 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 telah pergi untuk melaksanakan ini dalam kod, saya perlu memikirkan bagaimana untuk pergi 329 00:14:33,300 --> 00:14:34,160 melakukan ini. 330 00:14:34,160 --> 00:14:37,720 >> Dan saya akan mencadangkan mengambil langkah-langkah bayi di mana, dalam kes ini saya maksudkan, apakah 331 00:14:37,720 --> 00:14:41,090 senario yang mungkin kita mungkin menghadapi secara umum? 332 00:14:41,090 --> 00:14:44,120 Apabila melaksanakan memasukkan untuk berkaitan senarai, ini hanya berlaku untuk menjadi 333 00:14:44,120 --> 00:14:46,090 contoh khusus saiz lima. 334 00:14:46,090 --> 00:14:50,420 Baik jika anda ingin memasukkan nombor, suka mengatakan nombor satu, dan 335 00:14:50,420 --> 00:14:53,380 mengekalkan perintah disusun, di mana jelas tidak nombor satu perlu 336 00:14:53,380 --> 00:14:55,686 pergi dalam contoh ini tertentu? 337 00:14:55,686 --> 00:14:56,840 Seperti pada permulaan. 338 00:14:56,840 --> 00:15:00,030 >> Tetapi apa yang menarik ada yang jika anda mahu untuk memasukkan satu ke dalam ini 339 00:15:00,030 --> 00:15:04,100 senarai, apa penunjuk khas perlu perlu dikemaskini nampaknya? 340 00:15:04,100 --> 00:15:04,610 Pertama. 341 00:15:04,610 --> 00:15:07,830 Jadi, saya akan berhujah, ini adalah kes pertama bahawa kita mungkin mahu mempertimbangkan, satu 342 00:15:07,830 --> 00:15:11,140 senario yang melibatkan memasukkan di permulaan senarai. 343 00:15:11,140 --> 00:15:15,400 >> Mari kita memetik bulir mungkin satu yang mudah atau kes lebih mudah, secara relatif. 344 00:15:15,400 --> 00:15:18,110 Katakan saya mahu memasukkan nombor 35 untuk disusun. 345 00:15:18,110 --> 00:15:20,600 Ia jelas tergolong di sana. 346 00:15:20,600 --> 00:15:25,320 Jadi apa penunjuk jelas akan perlu dikemaskini dalam senario itu? 347 00:15:25,320 --> 00:15:30,060 34 penunjuk ini tidak menjadi batal tetapi alamat struct itu 348 00:15:30,060 --> 00:15:31,800 yang mengandungi nombor 35. 349 00:15:31,800 --> 00:15:32,750 Itulah kes dua. 350 00:15:32,750 --> 00:15:36,190 Jadi sudah, saya jenis quantizing berapa banyak kerja yang saya lakukan di sini. 351 00:15:36,190 --> 00:15:39,880 >> Dan akhirnya, kes tengah jelas adalah sesungguhnya, di tengah-tengah, jika saya mahu 352 00:15:39,880 --> 00:15:45,870 memasukkan sesuatu seperti berkata 23, yang pergi antara 23 dan 26, tetapi 353 00:15:45,870 --> 00:15:48,680 kini perkara-perkara mendapatkan lebih sedikit yang terlibat kerana apa yang 354 00:15:48,680 --> 00:15:52,800 petunjuk perlu berubah? 355 00:15:52,800 --> 00:15:56,680 Jadi 22 jelas perlu berubah kerana dia tidak boleh menunjukkan kepada 26 lagi. 356 00:15:56,680 --> 00:16:00,320 Dia perlu menunjukkan nod baru yang Saya akan mempunyai untuk memperuntukkan dengan menghubungi 357 00:16:00,320 --> 00:16:01,770 malloc atau setaraf beberapa. 358 00:16:01,770 --> 00:16:05,990 >> Tetapi saya juga perlu bahawa nod baru, 23 dalam kes ini, mempunyai penunjuk yang 359 00:16:05,990 --> 00:16:07,870 menghala ke arah siapa? 360 00:16:07,870 --> 00:16:08,560 26. 361 00:16:08,560 --> 00:16:10,380 Dan ada akan menjadi satu perintah operasi di sini. 362 00:16:10,380 --> 00:16:13,410 Kerana jika saya lakukan ini bodoh, dan saya untuk permulaan contoh pada awal 363 00:16:13,410 --> 00:16:16,040 senarai, dan matlamat saya adalah untuk memasukkan 23. 364 00:16:16,040 --> 00:16:18,610 Dan saya lihat, adakah ia tergolong di sini, berhampiran sembilan? 365 00:16:18,610 --> 00:16:18,950 No 366 00:16:18,950 --> 00:16:20,670 Adakah ia tergolong di sini, bersebelahan dengan 17? 367 00:16:20,670 --> 00:16:20,940 No 368 00:16:20,940 --> 00:16:22,530 Adakah ia tergolong di sini bersebelahan dengan 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 berfikir ini melalui, saya mungkin 371 00:16:26,400 --> 00:16:28,320 memperuntukkan nod baru saya untuk 23. 372 00:16:28,320 --> 00:16:32,080 Saya mungkin mengemas kini penunjuk dari nod yang dipanggil 22, menunjuk 373 00:16:32,080 --> 00:16:33,080 ia pada nod baru. 374 00:16:33,080 --> 00:16:36,140 Dan kemudian apa yang saya perlu mengemaskini penunjuk nod baru boleh? 375 00:16:36,140 --> 00:16:38,120 >> PELAJAR: [didengar]. 376 00:16:38,120 --> 00:16:38,385 >> SPEAKER 1: Tepat sekali. 377 00:16:38,385 --> 00:16:39,710 Menghala ke arah 26. 378 00:16:39,710 --> 00:16:45,590 Tetapi keparat jika saya tidak mengemas kini sudah 22 penunjuk untuk menunjukkan pada lelaki ini, dan 379 00:16:45,590 --> 00:16:48,260 kini saya mempunyai anak-anak yatim, yang lain senarai, jadi untuk bercakap. 380 00:16:48,260 --> 00:16:52,140 Jadi perintah operasi di sini akan menjadi penting. 381 00:16:52,140 --> 00:16:55,100 >> Untuk melakukan ini saya boleh mencuri, berkata, enam sukarelawan. 382 00:16:55,100 --> 00:16:57,650 Dan mari kita lihat jika kita tidak boleh melakukan ini visual dan bukannya kod yang bijak. 383 00:16:57,650 --> 00:16:59,330 Dan kita mempunyai beberapa tekanan yang indah bola untuk anda hari ini. 384 00:16:59,330 --> 00:17:02,510 OK, bagaimana kira-kira satu, dua, dalam kembali - di hujung sana. 385 00:17:02,510 --> 00:17:04,530 tiga, empat, kedua-dua anda lelaki di akhir. 386 00:17:04,530 --> 00:17:05,579 Dan lima, enam. 387 00:17:05,579 --> 00:17:05,839 Pasti. 388 00:17:05,839 --> 00:17:06,450 Lima dan enam. 389 00:17:06,450 --> 00:17:08,390 Semua hak dan kami akan datang kepada anda semua masa akan datang. 390 00:17:08,390 --> 00:17:09,640 Baiklah, datang ke atas. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Baiklah, kerana anda di sini pertama, anda ingin menjadi salah satu canggung 393 00:17:14,819 --> 00:17:16,119 in Google Kaca di sini? 394 00:17:16,119 --> 00:17:19,075 Baiklah, jadi, OK, Kaca, merakam 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 anda semua boleh datang di sini, saya telah disediakan terlebih dahulu 398 00:17:27,950 --> 00:17:30,110 beberapa nombor. 399 00:17:30,110 --> 00:17:31,240 Baiklah, datang di sini. 400 00:17:31,240 --> 00:17:33,440 Dan mengapa tidak anda pergi sedikit lagi cara itu. 401 00:17:33,440 --> 00:17:35,520 Dan mari kita lihat, apa nama, dengan Kaca Google? 402 00:17:35,520 --> 00:17:35,910 >> PELAJAR: 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 literal. 405 00:17:38,380 --> 00:17:40,580 Jadi, kita akan menghantar anda hingga akhir pentas. 406 00:17:40,580 --> 00:17:41,670 Baiklah, dan nama anda? 407 00:17:41,670 --> 00:17:41,990 >> PELAJAR: Jason. 408 00:17:41,990 --> 00:17:44,530 >> SPEAKER 1: Jason, OK anda akan menjadi nombor sembilan. 409 00:17:44,530 --> 00:17:46,700 Jadi, jika anda ingin mengikuti Ben cara itu. 410 00:17:46,700 --> 00:17:47,010 >> PELAJAR: Jill. 411 00:17:47,010 --> 00:17:49,630 >> SPEAKER 1: Jill anda akan menjadi 17, yang jika saya melakukan ini lebih 412 00:17:49,630 --> 00:17:51,260 bijak, saya akan bermula pada hujung yang lain. 413 00:17:51,260 --> 00:17:52,370 Anda pergi cara itu. 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 >> PELAJAR: 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 >> PELAJAR: 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 akhirnya. 422 00:18:00,740 --> 00:18:01,400 >> PELAJAR: 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 anda datang ke sini. 425 00:18:03,920 --> 00:18:06,360 >> Baiklah, jadi sempurna disusun memerintahkan sudah. 426 00:18:06,360 --> 00:18:09,600 Dan mari kita pergi ke hadapan dan melakukan ini supaya kita dapat benar-benar - 427 00:18:09,600 --> 00:18:11,720 Ben anda hanya jenis mencari keluar ke mana-mana tempat di sana. 428 00:18:11,720 --> 00:18:15,670 OK, jadi mari kita pergi ke hadapan dan menggambarkan ini menggunakan senjata, sama seperti saya adalah, sebenarnya, 429 00:18:15,670 --> 00:18:16,250 apa yang berlaku. 430 00:18:16,250 --> 00:18:19,540 Oleh itu, pergilah ke hadapan dan memberi diri yang kaki atau dua di antara kamu. 431 00:18:19,540 --> 00:18:22,900 Dan pergi ke hadapan dan menunjukkan dengan satu tangan untuk sesiapa yang anda perlu menghala ke arah 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 null lurus ke bawah ke lantai. 434 00:18:25,890 --> 00:18:27,690 OK, jadi yang baik. 435 00:18:27,690 --> 00:18:32,290 >> Jadi sekarang kita mempunyai senarai yang berkaitan, dan biarlah saya mencadangkan bahawa saya akan memainkan peranan 436 00:18:32,290 --> 00:18:35,110 PTR, jadi saya tidak akan mengganggu menjalankan ini sekitar. 437 00:18:35,110 --> 00:18:37,830 Dan kemudian - konvensyen bodoh seseorang - anda boleh memanggil apa-apa ini yang anda mahu - 438 00:18:37,830 --> 00:18:39,800 penunjuk sebelumnya, penunjuk Pred - 439 00:18:39,800 --> 00:18:43,930 ia hanya nama samaran kami mengalah contoh kod untuk tangan kiri saya. 440 00:18:43,930 --> 00:18:47,240 Sebaliknya yang akan menjaga menjejaki yang yang di 441 00:18:47,240 --> 00:18:48,400 berikutan senario. 442 00:18:48,400 --> 00:18:52,390 >> Jadi rasa, pertama, saya ingin memetik bulir bahawa contoh pertama memasukkan, berkata 443 00:18:52,390 --> 00:18:54,330 20, ke dalam senarai. 444 00:18:54,330 --> 00:18:57,160 Jadi saya akan memerlukan seseorang untuk merangkumi nombor 20 untuk kita. 445 00:18:57,160 --> 00:18:58,950 Jadi saya perlu malloc seseorang daripada penonton. 446 00:18:58,950 --> 00:18:59,380 Ayuh up. 447 00:18:59,380 --> 00:19:00,340 Apa nama anda? 448 00:19:00,340 --> 00:19:01,300 >> PELAJAR: Brian. 449 00:19:01,300 --> 00:19:05,270 >> SPEAKER 1: Brian, semua betul, jadi anda hendaklah nod yang mengandungi 20. 450 00:19:05,270 --> 00:19:06,810 Baiklah, datang di sini. 451 00:19:06,810 --> 00:19:10,025 Dan jelas, di mana adakah Brian tergolong? 452 00:19:10,025 --> 00:19:12,190 Jadi, di tengah-tengah - sebenarnya, tunggu satu minit. 453 00:19:12,190 --> 00:19:13,420 Kami melakukan ini daripada perintah. 454 00:19:13,420 --> 00:19:17,170 Kami membuat ini jauh lebih sukar daripada ia perlu pada mulanya. 455 00:19:17,170 --> 00:19:21,210 OK, kita akan bebas Brian dan realloc Brian sebagai lima. 456 00:19:21,210 --> 00:19:23,680 >> OK, jadi sekarang kita mahu memasukkan Brian sebagai lima. 457 00:19:23,680 --> 00:19:25,960 Jadi datang ke sini di sebelah Ben hanya seketika. 458 00:19:25,960 --> 00:19:28,250 Dan anda mungkin boleh memberitahu di mana cerita ini berterusan. 459 00:19:28,250 --> 00:19:30,500 Tetapi mari kita berfikir dengan teliti tentang perintah operasi. 460 00:19:30,500 --> 00:19:32,880 Dan ia adalah tepat ini visual itu akan beratur 461 00:19:32,880 --> 00:19:34,080 dengan kod sampel. 462 00:19:34,080 --> 00:19:40,120 Jadi di sini saya telah PTR menunjuk pada mulanya tidak pada Ben, per se, tetapi pada apa sahaja 463 00:19:40,120 --> 00:19:43,245 menghargai dia mengandungi, yang dalam kes ini adalah - apa nama anda lagi? 464 00:19:43,245 --> 00:19:43,670 >> PELAJAR: Jason. 465 00:19:43,670 --> 00:19:47,350 >> SPEAKER 1: Jason, supaya kedua-dua Ben dan saya menghala ke arah Jason pada masa ini. 466 00:19:47,350 --> 00:19:49,700 Jadi sekarang saya perlu ditentukan, di mana tidak Brian tergolong? 467 00:19:49,700 --> 00:19:53,500 Jadi satu-satunya perkara saya mempunyai akses kepada sekarang adalah perkara data n beliau. 468 00:19:53,500 --> 00:19:58,280 Jadi saya akan menyemak, adalah Brian kurang daripada Jason? 469 00:19:58,280 --> 00:19:59,770 Jawapannya adalah benar. 470 00:19:59,770 --> 00:20:03,680 >> Jadi apa yang kini perlu berlaku, dalam susunan yang betul? 471 00:20:03,680 --> 00:20:07,120 Saya perlu mengemaskinikan berapa banyak petunjuk dalam jumlah di dalam cerita ini? 472 00:20:07,120 --> 00:20:10,720 Di mana tangan saya masih menghala ke arah Jason, dan tangan anda - jika anda mahu 473 00:20:10,720 --> 00:20:12,930 meletakkan tangan anda seperti, jenis, 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, jadi anda perlu calon-calon ini. 476 00:20:15,670 --> 00:20:20,500 Sama ada Ben atau saya atau Brian atau Jason atau orang lain, yang 477 00:20:20,500 --> 00:20:21,370 petunjuk perlu berubah? 478 00:20:21,370 --> 00:20:23,260 Berapa ramai dalam jumlah? 479 00:20:23,260 --> 00:20:24,080 >> OK, jadi dua. 480 00:20:24,080 --> 00:20:27,090 Penunjuk saya tidak benar-benar perkara lagi kerana saya hanya sementara. 481 00:20:27,090 --> 00:20:31,370 Jadi ia adalah kedua-dua lelaki itu, mungkin, kedua-dua Ben dan Brian. 482 00:20:31,370 --> 00:20:34,410 Jadi biarlah saya mencadangkan supaya kita kini Ben, kerana dia pertama. 483 00:20:34,410 --> 00:20:36,350 Elemen pertama dalam senarai ini kini 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 >> Yang mendapat menunjuk ke arah siapa? 488 00:20:43,460 --> 00:20:44,710 >> PELAJAR: [didengar]. 489 00:20:44,710 --> 00:20:46,180 >> SPEAKER 1: OK jadi Brian mempunyai ke titik di Jason. 490 00:20:46,180 --> 00:20:48,360 Tetapi saya hilang mengesan penunjuk itu? 491 00:20:48,360 --> 00:20:49,980 Saya tahu di mana Jason? 492 00:20:49,980 --> 00:20:50,790 >> PELAJAR: [didengar]. 493 00:20:50,790 --> 00:20:52,620 >> SPEAKER 1: saya lakukan, kerana saya penunjuk sementara. 494 00:20:52,620 --> 00:20:55,110 Dan mungkin, saya tidak berubah untuk menunjukkan pada nod baru. 495 00:20:55,110 --> 00:20:58,300 Oleh itu, kita hanya boleh mempunyai titik Brian pada sesiapa yang saya menghala ke arah. 496 00:20:58,300 --> 00:20:59,000 Dan kita selesai. 497 00:20:59,000 --> 00:21:01,890 Jadi mana-mana satu, kemasukan di awal senarai. 498 00:21:01,890 --> 00:21:02,950 Terdapat dua langkah utama. 499 00:21:02,950 --> 00:21:06,750 Pertama, kita perlu mengemaskini Ben, dan kemudian kita juga perlu mengemaskini Brian. 500 00:21:06,750 --> 00:21:09,230 Dan maka saya tidak perlu bersusah payah traipsing melalui seluruh 501 00:21:09,230 --> 00:21:12,680 senarai, kerana kita sudah menemui beliau lokasi, kerana dia milik 502 00:21:12,680 --> 00:21:14,080 meninggalkan unsur yang pertama. 503 00:21:14,080 --> 00:21:15,400 >> Baiklah, jadi agak mudah. 504 00:21:15,400 --> 00:21:18,110 Malah, rasanya kita sudah hampir membuat ini terlalu rumit. 505 00:21:18,110 --> 00:21:20,240 Jadi mari kita kini memetik off akhir senarai, dan melihat di mana 506 00:21:20,240 --> 00:21:21,380 kerumitan bermula. 507 00:21:21,380 --> 00:21:24,560 Jadi, jika kini, saya alloc dari penonton. 508 00:21:24,560 --> 00:21:25,540 Sesiapa yang mahu bermain 55? 509 00:21:25,540 --> 00:21:26,700 Baiklah, saya melihat tangan pertama. 510 00:21:26,700 --> 00:21:29,620 Ayuh up. 511 00:21:29,620 --> 00:21:30,030 Yeah. 512 00:21:30,030 --> 00:21:31,177 Apa nama anda? 513 00:21:31,177 --> 00:21:32,310 >> PELAJAR: [didengar]. 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 nombor 55. 517 00:21:35,730 --> 00:21:37,820 Jadi anda, sudah tentu, kepunyaan pada akhir senarai. 518 00:21:37,820 --> 00:21:41,850 Jadi mari kita memainkan simulasi dengan saya menjadi PTR untuk seketika. 519 00:21:41,850 --> 00:21:44,050 Jadi, saya mula-mula pergi ke titik di apa Ben yang menghala ke arah. 520 00:21:44,050 --> 00:21:45,900 Kami kedua-dua menunjuk di Brian. 521 00:21:45,900 --> 00:21:48,420 Jadi 55 tidak kurang daripada lima. 522 00:21:48,420 --> 00:21:52,510 Jadi, saya akan mengemas kini diri dengan menunjuk kepada penunjuk seterusnya Brian, yang 523 00:21:52,510 --> 00:21:54,450 kini sudah tentu Jason. 524 00:21:54,450 --> 00:21:57,310 55 tidak kurang daripada sembilan, jadi Saya akan mengemas kini PTR. 525 00:21:57,310 --> 00:21:58,890 Saya akan mengemas kini PTR. 526 00:21:58,890 --> 00:22:02,290 Saya akan mengemas kini PTR Saya akan mengemaskini PTR. 527 00:22:02,290 --> 00:22:05,060 Dan saya akan - hmm, apa nama anda lagi? 528 00:22:05,060 --> 00:22:05,560 >> PELAJAR: Diana. 529 00:22:05,560 --> 00:22:09,190 >> SPEAKER 1: Diana menunjukkan, sudah tentu, di batal dengan tangan kirinya. 530 00:22:09,190 --> 00:22:13,030 Oleh itu, bagaimana sebenarnya Habata tergolong dengan 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 meletakkan beliau sini Saya rasa saya telah kacau sehingga. 533 00:22:19,460 --> 00:22:22,420 Kerana apa yang PTR seni masa ini dalam masa? 534 00:22:22,420 --> 00:22:23,240 Menyeimbangkan. 535 00:22:23,240 --> 00:22:25,580 Jadi, walaupun, visual, kita boleh jelas melihat semua ini 536 00:22:25,580 --> 00:22:26,610 lelaki di sini di atas pentas. 537 00:22:26,610 --> 00:22:29,680 Saya tidak disimpan mengesan sebelumnya orang di dalam senarai. 538 00:22:29,680 --> 00:22:33,210 Saya tidak mempunyai jari menunjuk keluar, dalam kes ini, bilangan nod 34. 539 00:22:33,210 --> 00:22:34,760 >> Jadi mari kita benar-benar bermula lebih ini. 540 00:22:34,760 --> 00:22:37,560 Jadi sekarang saya sebenarnya perlu pembolehubah tempatan kedua. 541 00:22:37,560 --> 00:22:40,980 Dan ini adalah apa yang anda akan lihat di sebenar sampel kod C, di mana seperti yang saya pergi, 542 00:22:40,980 --> 00:22:45,860 apabila saya mengemaskini tangan kanan saya untuk menunjukkan Jason, dengan itu meninggalkan Brian belakang, saya 543 00:22:45,860 --> 00:22:51,440 lebih baik mula menggunakan tangan kiri saya untuk mengemas kini mana saya berada, supaya apabila saya pergi 544 00:22:51,440 --> 00:22:52,700 melalui senarai ini - 545 00:22:52,700 --> 00:22:55,040 lebih canggung daripada saya bertujuan sekarang di sini visual - 546 00:22:55,040 --> 00:22:56,740 Saya akan mendapatkan kepada akhir senarai. 547 00:22:56,740 --> 00:23:00,020 >> Tangan ini masih sah, yang cukup tidak berguna, selain daripada untuk menunjukkan 548 00:23:00,020 --> 00:23:02,980 Saya dengan jelas pada akhir senarai, tetapi kini sekurang-kurangnya saya mempunyai ini 549 00:23:02,980 --> 00:23:08,270 penunjuk sebelumnya menunjuk di sini, jadi kini apa yang tangan dan apa yang perlu petunjuk 550 00:23:08,270 --> 00:23:10,150 akan dikemas kini? 551 00:23:10,150 --> 00:23:13,214 Yang tangan yang anda mahu untuk menyusun semula pertama? 552 00:23:13,214 --> 00:23:15,190 >> PELAJAR: [didengar]. 553 00:23:15,190 --> 00:23:16,220 >> SPEAKER 1: OK, jadi ini Diana. 554 00:23:16,220 --> 00:23:21,110 Di manakah anda mahu menunjukkan Penunjuk kiri Diana di? 555 00:23:21,110 --> 00:23:23,620 Pada 55, mungkin, supaya kami telah dimasukkan di sana. 556 00:23:23,620 --> 00:23:25,560 Dan di mana 55 penunjuk harus pergi? 557 00:23:25,560 --> 00:23:27,000 Down, mewakili null. 558 00:23:27,000 --> 00:23:28,890 Dan tangan saya, pada masa ini, tidak masalah kerana mereka hanya 559 00:23:28,890 --> 00:23:30,070 pembolehubah sementara. 560 00:23:30,070 --> 00:23:31,030 Jadi sekarang kita sedang dilakukan. 561 00:23:31,030 --> 00:23:34,650 >> Jadi kerumitan tambahan yang ada - dan ia tidak begitu sukar untuk melaksanakan, 562 00:23:34,650 --> 00:23:38,660 tetapi kita perlu berubah-ubah menengah untuk membuat memastikan bahawa sebelum saya bergerak kanan saya 563 00:23:38,660 --> 00:23:42,140 tangan, saya mengemaskini nilai kiri saya Sebaliknya, penunjuk Pred dalam kes ini, jadi 564 00:23:42,140 --> 00:23:45,860 bahawa saya mempunyai penunjuk ketinggalan untuk menjejaki di mana saya berada. 565 00:23:45,860 --> 00:23:49,360 Sekarang sebagai diketepikan, jika anda berfikir ini melalui, ini berasa seperti ia adalah 566 00:23:49,360 --> 00:23:51,490 sedikit menjengkelkan perlu menyimpan mengesan tangan kiri ini. 567 00:23:51,490 --> 00:23:54,015 >> Apa yang akan penyelesaian lain kepada masalah ini berlaku? 568 00:23:54,015 --> 00:23:56,500 Jika anda mendapat untuk mereka bentuk semula 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 jenis ini hanya daripada merasakan sedikit menjengkelkan untuk mempunyai, suka, dua petunjuk 571 00:24:02,690 --> 00:24:08,430 melalui senarai itu, siapa lagi yang boleh telah, dalam dunia yang ideal, dikekalkan 572 00:24:08,430 --> 00:24:10,160 maklumat yang kita perlukan? 573 00:24:10,160 --> 00:24:11,360 Ya? 574 00:24:11,360 --> 00:24:12,610 >> PELAJAR: [didengar]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> SPEAKER 1: Tepat sekali. 577 00:24:16,150 --> 00:24:19,130 Betul supaya ada sebenarnya yang menarik kuman idea. 578 00:24:19,130 --> 00:24:22,470 Dan idea ini penunjuk sebelumnya, menghala ke arah elemen sebelumnya. 579 00:24:22,470 --> 00:24:25,580 Bagaimana jika saya hanya termaktub bahawa di dalam senarai itu sendiri? 580 00:24:25,580 --> 00:24:27,810 Dan ia akan menjadi sukar untuk menggambarkan 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 Tetapi menganggap bahawa lelaki yang digunakan kedua-dua tangan mereka mempunyai sebelumnya 583 00:24:31,860 --> 00:24:35,950 penunjuk, dan penunjuk akan datang, sekali gus melaksanakan apa yang kita akan memanggil duanya adalah terpakai 584 00:24:35,950 --> 00:24:36,830 senarai berkaitan. 585 00:24:36,830 --> 00:24:41,090 Yang akan membolehkan saya untuk menyusun daripada memutar balik, lebih mudah tanpa saya, 586 00:24:41,090 --> 00:24:43,800 programmer, perlu menyimpan menjejaki 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 sebelum ini dalam senarai. 589 00:24:47,280 --> 00:24:48,110 Jadi kita tidak akan berbuat demikian. 590 00:24:48,110 --> 00:24:50,950 Kami akan memastikan ia mudah kerana itulah akan datang pada harga, dua kali ganda 591 00:24:50,950 --> 00:24:53,450 banyak ruang untuk petunjuk, jika anda mahu yang kedua. 592 00:24:53,450 --> 00:24:55,760 Tetapi itulah sesungguhnya yang sama struktur data yang dikenali sebagai 593 00:24:55,760 --> 00:24:57,410 senarai duanya adalah terpakai dikaitkan. 594 00:24:57,410 --> 00:25:01,310 >> Mari kita buat contoh terakhir di sini dan meletakkan lelaki ini keluar daripada kesengsaraan mereka. 595 00:25:01,310 --> 00:25:03,270 Jadi malloc 20. 596 00:25:03,270 --> 00:25:05,320 Ayuh dari lorong di sana. 597 00:25:05,320 --> 00:25:06,280 Baiklah, apa nama anda? 598 00:25:06,280 --> 00:25:07,440 >> PELAJAR: [didengar]. 599 00:25:07,440 --> 00:25:07,855 >> SPEAKER 1: Maaf? 600 00:25:07,855 --> 00:25:08,480 >> PELAJAR: [didengar]. 601 00:25:08,480 --> 00:25:09,410 >> SPEAKER 1 Demeron? 602 00:25:09,410 --> 00:25:10,230 OK datang di atas. 603 00:25:10,230 --> 00:25:11,910 Anda hendaklah 20. 604 00:25:11,910 --> 00:25:14,720 Anda jelas akan tergolong di antara 17 dan 22. 605 00:25:14,720 --> 00:25:16,150 Jadi biarlah saya belajar pelajaran saya. 606 00:25:16,150 --> 00:25:18,150 Saya akan memulakan penunjuk menghala ke arah Brian. 607 00:25:18,150 --> 00:25:21,190 Dan saya akan mempunyai tangan kiri saya hanya mengemaskini kepada Brian kerana saya berpindah ke 608 00:25:21,190 --> 00:25:23,600 Jason, pemeriksaan tidak 20 kurang daripada sembilan? 609 00:25:23,600 --> 00:25:24,060 No 610 00:25:24,060 --> 00:25:25,430 Ialah 20 kurang daripada 17? 611 00:25:25,430 --> 00:25:25,880 No 612 00:25:25,880 --> 00:25:27,450 Ialah 20 kurang daripada 22? 613 00:25:27,450 --> 00:25:28,440 Ya. 614 00:25:28,440 --> 00:25:34,070 Jadi apa petunjuk atau tangan perlu menukar di mana mereka menunjuk sekarang? 615 00:25:34,070 --> 00:25:37,070 >> Oleh itu, kita boleh melakukan 17 menghala ke arah 20. 616 00:25:37,070 --> 00:25:37,860 Jadi itulah denda. 617 00:25:37,860 --> 00:25:40,080 Jika kita mahu untuk menunjukkan penunjuk 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 penunjuk sementara saya. 620 00:25:45,410 --> 00:25:46,760 Jadi kita OK di sana. 621 00:25:46,760 --> 00:25:49,440 Jadi kerana penyimpanan sementara ini Saya telah disimpan mengesan di mana semua orang. 622 00:25:49,440 --> 00:25:55,055 Dan sekarang anda visual boleh pergi ke mana anda tergolong, dan kini kita perlu 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 bola tekanan, dan pusingan tepukan untuk 624 00:25:58,410 --> 00:25:59,770 lelaki ini, jika kita boleh. 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 boleh menyimpan keping kertas sebagai tanda mata. 629 00:26:09,860 --> 00:26:15,930 >> Baiklah, jadi, amanah saya ia banyak lebih mudah untuk berjalan melalui dengan 630 00:26:15,930 --> 00:26:17,680 manusia daripada ia adalah dengan kod sebenar. 631 00:26:17,680 --> 00:26:22,690 Tetapi apa yang anda akan dapati di seketika kini, adalah yang 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 bahawa anda akan mendapati bahawa data yang sama struktur, senarai yang berkaitan, boleh sebenarnya 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 menyedari terlalu tema di sini ialah kita telah benar-benar memperkenalkan lebih 636 00:26:37,620 --> 00:26:40,060 kerumitan dalam pelaksanaan algoritma ini. 637 00:26:40,060 --> 00:26:43,940 Kemasukan, dan jika kita pergi melaluinya, penghapusan dan mencari, adalah sedikit 638 00:26:43,940 --> 00:26:46,660 lebih rumit daripada ia adalah dengan array. 639 00:26:46,660 --> 00:26:48,040 Tetapi kita mendapat beberapa dinamik. 640 00:26:48,040 --> 00:26:50,180 Kami mendapat satu struktur data penyesuaian. 641 00:26:50,180 --> 00:26:54,010 >> Tetapi sekali lagi, kita membayar harga yang mempunyai beberapa kerumitan tambahan, dalam kedua-dua 642 00:26:54,010 --> 00:26:54,910 melaksanakannya. 643 00:26:54,910 --> 00:26:56,750 Dan kita berputus asa akses rawak. 644 00:26:56,750 --> 00:27:00,450 Dan untuk bersikap jujur, tidak ada beberapa nice membersihkan slaid saya boleh memberi anda bahawa 645 00:27:00,450 --> 00:27:03,120 mengatakan di sini ialah mengapa senarai dikaitkan adalah lebih baik daripada array. 646 00:27:03,120 --> 00:27:04,100 Dan tinggalkan ia pada itu. 647 00:27:04,100 --> 00:27:07,520 Kerana tema yang sering muncul sekarang, walaupun lebih-lebih lagi pada minggu-minggu akan datang, adalah 648 00:27:07,520 --> 00:27:10,200 bahawa tidak semestinya jawapan yang betul. 649 00:27:10,200 --> 00:27:13,830 >> Inilah sebabnya mengapa kita mempunyai paksi yang berasingan reka bentuk untuk set masalah. 650 00:27:13,830 --> 00:27:17,700 Ia akan menjadi sangat peka konteks sama ada anda mahu menggunakan data ini 651 00:27:17,700 --> 00:27:21,750 struktur atau yang satu, dan ia akan bergantung kepada apa yang penting kepada anda dari segi 652 00:27:21,750 --> 00:27:24,620 sumber dan kerumitan. 653 00:27:24,620 --> 00:27:28,830 >> Tetapi biarlah saya mencadangkan bahawa data yang sesuai struktur, kaedah berpotensi suci, akan menjadi 654 00:27:28,830 --> 00:27:32,200 sesuatu yang masa yang berterusan, tanpa mengira berapa banyak barangan adalah 655 00:27:32,200 --> 00:27:36,940 di dalamnya, ia tidak akan menjadi hebat jika struktur data kembali jawapan dalam 656 00:27:36,940 --> 00:27:37,920 masa yang sama. 657 00:27:37,920 --> 00:27:38,330 Ya. 658 00:27:38,330 --> 00:27:40,110 Perkataan ini di dalam kamus yang besar anda. 659 00:27:40,110 --> 00:27:41,550 Atau tidak, perkataan ini tidak. 660 00:27:41,550 --> 00:27:43,270 Atau mana-mana masalah itu di sana. 661 00:27:43,270 --> 00:27:46,360 Nah mari kita lihat jika kita tidak boleh sekurang-kurangnya mengambil satu langkah ke arah itu. 662 00:27:46,360 --> 00:27:50,190 >> Biar saya mencadangkan satu struktur data baru yang boleh digunakan untuk perkara-perkara yang berbeza, 663 00:27:50,190 --> 00:27:52,260 dalam kes ini dipanggil jadual hash. 664 00:27:52,260 --> 00:27:55,590 Dan jadi kita sebenarnya kembali kepada mengerling di pelbagai, dalam kes ini, dan 665 00:27:55,590 --> 00:28:00,550 agak sewenang-wenangnya, saya telah disediakan ini jadual hash sebagai array dengan jenis yang 666 00:28:00,550 --> 00:28:02,810 dua dimensi pelbagai - 667 00:28:02,810 --> 00:28:05,410 atau sebaliknya ia digambarkan di sini sebagai dua dimensi pelbagai - tetapi ini hanya 668 00:28:05,410 --> 00:28:10,770 pelbagai saiz 26, apa-apa jika kita hubungi meja pelbagai, kurungan jadual 669 00:28:10,770 --> 00:28:12,440 sifar adalah segi empat tepat di atas. 670 00:28:12,440 --> 00:28:15,090 Jadual kurungan 25 adalah segi empat tepat di bahagian bawah. 671 00:28:15,090 --> 00:28:18,620 Dan ini adalah bagaimana saya boleh menarik data struktur di mana saya mahu menyimpan 672 00:28:18,620 --> 00:28:19,790 orang nama. 673 00:28:19,790 --> 00:28:24,370 >> Jadi sebagai contoh, dan saya tidak akan menarik segala-galanya di sini di atas, jika saya 674 00:28:24,370 --> 00:28:29,160 mempunyai pelbagai ini, yang saya kini akan memanggil jadual hash, dan ini sekali lagi 675 00:28:29,160 --> 00:28:31,360 lokasi sifar. 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 mendakwa bahawa saya ingin menggunakan data ini struktur, demi perbincangan, 678 00:28:37,880 --> 00:28:42,600 untuk menyimpan nama-nama orang, Alice dan Bob dan Charlie dan lain-lain nama-nama itu. 679 00:28:42,600 --> 00:28:46,110 Jadi berfikir ini sekarang sebagai permulaan , berkata, kamus 680 00:28:46,110 --> 00:28:47,520 dengan banyak perkataan. 681 00:28:47,520 --> 00:28:49,435 Mereka berlaku adalah nama-nama dalam contoh kita di sini. 682 00:28:49,435 --> 00:28:52,560 Dan ini adalah semua terlalu yg, mungkin, untuk melaksanakan pemeriksa ejaan, seperti yang kita 683 00:28:52,560 --> 00:28:54,400 mungkin bagi masalah yang ditetapkan enam. 684 00:28:54,400 --> 00:28:59,300 >> Jadi, jika kita mempunyai pelbagai jumlah saiz 26 supaya ini adalah lokasi ke-25 685 00:28:59,300 --> 00:29:03,390 di bahagian bawah, dan saya mendakwa bahawa Alice perkataan pertama di kamus 686 00:29:03,390 --> 00:29:07,260 nama-nama yang saya mahu masukkan ke dalam RAM, ke dalam struktur data ini, di mana 687 00:29:07,260 --> 00:29:12,480 naluri memberitahu anda bahawa Alice Nama harus pergi dalam barisan ini? 688 00:29:12,480 --> 00:29:13,510 >> Kami mempunyai 26 pilihan. 689 00:29:13,510 --> 00:29:14,990 Di mana kita mahu meletakkan dia? 690 00:29:14,990 --> 00:29:16,200 Kami mahu dia dalam kurungan sifar, bukan? 691 00:29:16,200 --> 00:29:18,280 A untuk Alice, mari kita memanggilnya yang sifar. 692 00:29:18,280 --> 00:29:20,110 And B akan menjadi salah satu, dan C akan menjadi dua. 693 00:29:20,110 --> 00:29:22,600 Jadi, kita akan menulis Nama Alice di sini. 694 00:29:22,600 --> 00:29:24,890 Jika kita kemudian memasukkan Bob, beliau nama akan pergi 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 ke bawah melalui ini struktur data. 697 00:29:30,500 --> 00:29:32,090 >> Ini adalah satu struktur data yang indah. 698 00:29:32,090 --> 00:29:32,730 Mengapa? 699 00:29:32,730 --> 00:29:37,460 Nah apakah masa perjalanan memasukkan nama manusia ke dalam ini 700 00:29:37,460 --> 00:29:39,850 data struktur sekarang? 701 00:29:39,850 --> 00:29:43,702 Memandangkan jadual ini dilaksanakan, benar-benar, seperti array. 702 00:29:43,702 --> 00:29:44,940 Baik ia adalah masa yang berterusan. 703 00:29:44,940 --> 00:29:45,800 Ia adalah untuk satu. 704 00:29:45,800 --> 00:29:46,360 Mengapa? 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 boleh sampai ke sana, jika ia rentetan, dengan hanya melihat rentetan 709 00:29:54,350 --> 00:29:55,200 kurungan sifar. 710 00:29:55,200 --> 00:29:57,110 Jadi watak sifar tali. 711 00:29:57,110 --> 00:29:57,610 Yang mudah. 712 00:29:57,610 --> 00:30:00,350 Kami melakukan bahawa dalam kripto tugasan minggu lalu. 713 00:30:00,350 --> 00:30:05,310 Dan kemudian sekali anda tahu bahawa ini Alice huruf modal, kita boleh tolak 714 00:30:05,310 --> 00:30:08,160 kira 65 atau modal A sendiri, yang memberikan kita sifar. 715 00:30:08,160 --> 00:30:10,940 Oleh itu, kita kini tahu bahawa Alice kepunyaan di lokasi sifar. 716 00:30:10,940 --> 00:30:14,240 >> Dan memberi penunjuk kepada data ini struktur, beberapa jenis, berapa lama 717 00:30:14,240 --> 00:30:18,840 ia membawa saya untuk mencari lokasi sifar dalam array? 718 00:30:18,840 --> 00:30:22,080 Hanya satu langkah, betul Ia adalah masa yang berterusan kerana akses rawak kami 719 00:30:22,080 --> 00:30:23,780 dicadangkan adalah ciri-ciri array. 720 00:30:23,780 --> 00:30:28,570 Jadi dalam jangka pendek, memikirkan apa yang indeks nama Alice adalah, yang adalah, dalam 721 00:30:28,570 --> 00:30:32,610 kes ini, adalah A, atau mari kita hanya menyelesaikan yang kepada sifar, di mana B adalah salah dan C ialah 722 00:30:32,610 --> 00:30:34,900 dua, memikirkan bahawa daripada adalah masa yang berterusan. 723 00:30:34,900 --> 00:30:38,510 Saya hanya perlu melihat surat pertama, memikirkan mana sifar adalah satu 724 00:30:38,510 --> 00:30:40,460 pelbagai juga merupakan masa yang berterusan. 725 00:30:40,460 --> 00:30:42,140 Jadi secara teknikal itu seperti dua langkah sekarang. 726 00:30:42,140 --> 00:30:43,330 Tetapi itu masih berterusan. 727 00:30:43,330 --> 00:30:46,880 Jadi kita panggil yang O besar satu, jadi kami telah Alice dimasukkan ke dalam jadual ini 728 00:30:46,880 --> 00:30:48,440 masa yang sama. 729 00:30:48,440 --> 00:30:50,960 >> Tetapi sudah tentu, saya menjadi naif di sini, bukan? 730 00:30:50,960 --> 00:30:53,240 Bagaimana jika terdapat satu Harun di dalam kelas? 731 00:30:53,240 --> 00:30:53,990 Atau Alicia? 732 00:30:53,990 --> 00:30:57,230 Atau mana-mana nama-nama lain bermula dengan A. Di manakah kita akan meletakkan 733 00:30:57,230 --> 00:31:00,800 orang itu, bukan? 734 00:31:00,800 --> 00:31:03,420 Maksud saya, sekarang hanya terdapat tiga orang-orang di atas meja, jadi mungkin kita 735 00:31:03,420 --> 00:31:07,490 Harun harus meletakkan di lokasi sifar satu dua tiga. 736 00:31:07,490 --> 00:31:09,480 >> Betul, saya boleh meletakkan A di sini. 737 00:31:09,480 --> 00:31:13,350 Tetapi, jika kita cuba untuk memasukkan ke dalam David senarai ini, di mana tidak David pergi? 738 00:31:13,350 --> 00:31:15,170 Sekarang sistem kita mula berbuka ke bawah, bukan? 739 00:31:15,170 --> 00:31:19,210 Kerana kini David berakhir di sini jika Harun sebenarnya di sini. 740 00:31:19,210 --> 00:31:23,060 Dan sekarang ini idea keseluruhan yang mempunyai struktur data yang bersih yang memberikan kita 741 00:31:23,060 --> 00:31:28,010 sisipan masa berterusan tidak lagi masa yang berterusan, kerana saya perlu 742 00:31:28,010 --> 00:31:31,240 memeriksa, oh, damnit, seseorang sudah di lokasi Alice. 743 00:31:31,240 --> 00:31:35,320 >> Biar saya menyiasat seluruh 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 sebagainya yang terlalu bermula mengambil masa linear. 746 00:31:39,390 --> 00:31:42,710 Selain itu, jika anda kini mahu mencari Harun dalam struktur data ini, dan anda 747 00:31:42,710 --> 00:31:45,430 memeriksa, dan nama Harun tidak ada di sini. 748 00:31:45,430 --> 00:31:47,960 Sebaik-baiknya, anda hanya akan mengatakan Harun tidak dalam struktur data. 749 00:31:47,960 --> 00:31:51,530 Tetapi jika anda mula membuat ruang untuk Harun di mana sepatutnya ada D 750 00:31:51,530 --> 00:31:55,600 atau, anda, kes E teruk, perlu menyemak struktur data keseluruhan, 751 00:31:55,600 --> 00:31:59,480 mana ia anaknya itu adalah turun ke dalam sesuatu linear dalam saiz meja. 752 00:31:59,480 --> 00:32:00,920 >> Jadi semua betul, saya akan menetapkan ini. 753 00:32:00,920 --> 00:32:04,200 Masalah di sini adalah bahawa saya telah 26 elemen dalam array ini. 754 00:32:04,200 --> 00:32:05,000 Biar saya mengubahnya. 755 00:32:05,000 --> 00:32:06,010 Whoops. 756 00:32:06,010 --> 00:32:10,600 Izinkan saya mengubah supaya agak kesejahteraan saiz 26 dalam jumlah, notis bawah 757 00:32:10,600 --> 00:32:12,720 indeks akan berubah n tolak 1. 758 00:32:12,720 --> 00:32:16,610 Jika 26 adalah jelas terlalu kecil untuk manusia ' nama, kerana terdapat beribu-ribu 759 00:32:16,610 --> 00:32:20,830 nama-nama di dunia, mari kita hanya membuat 100 atau 1,000 atau 10,000. 760 00:32:20,830 --> 00:32:22,960 Mari kita memperuntukkan lebih banyak ruang. 761 00:32:22,960 --> 00:32:27,230 >> Well yang tidak semestinya mengurangkan kebarangkalian bahawa kita tidak akan mempunyai dua 762 00:32:27,230 --> 00:32:31,510 orang dengan nama-nama yang bermula dengan A, dan demikian, anda akan cuba untuk meletakkan A 763 00:32:31,510 --> 00:32:33,120 nama-nama pada sifar lokasi masih. 764 00:32:33,120 --> 00:32:36,850 Mereka masih akan berlanggar, yang bermakna kita masih memerlukan penyelesaian untuk meletakkan 765 00:32:36,850 --> 00:32:41,020 Alice dan Harun dan Alicia dan lain-lain nama-nama yang bermula dengan A di tempat lain. 766 00:32:41,020 --> 00:32:43,460 Tetapi berapa banyak masalah ini? 767 00:32:43,460 --> 00:32:46,870 Apakah kebarangkalian bahawa anda mempunyai perlanggaran dalam data 768 00:32:46,870 --> 00:32:48,240 Struktur seperti ini? 769 00:32:48,240 --> 00:32:52,570 >> Baiklah, biar saya - kita akan kembali kepada soalan itu di sini. 770 00:32:52,570 --> 00:32:55,530 Dan melihat bagaimana kita mungkin menyelesaikan terlebih dahulu. 771 00:32:55,530 --> 00:32:58,480 Biar saya tarik sehingga cadangan ini di sini. 772 00:32:58,480 --> 00:33:02,020 Apa yang kita hanya digambarkan adalah satu algoritma, heuristik yang dipanggil linear 773 00:33:02,020 --> 00:33:05,030 menyelesaikan sesuatu di mana, jika anda cuba untuk memasukkan sesuatu di sini dalam data ini 774 00:33:05,030 --> 00:33:08,920 struktur yang dipanggil jadual hash, dan terdapat tiada ruang di sana, anda 775 00:33:08,920 --> 00:33:12,000 benar-benar menyiasat struktur data memeriksa, adakah ini boleh didapati? 776 00:33:12,000 --> 00:33:13,430 Adakah ini yang ada ialah ini boleh didapati? 777 00:33:13,430 --> 00:33:13,980 Adakah ini boleh didapati? 778 00:33:13,980 --> 00:33:17,550 Dan apabila ia akhirnya adalah, anda memasukkan nama yang anda asalnya bertujuan 779 00:33:17,550 --> 00:33:19,370 di tempat lain di lokasi tersebut. 780 00:33:19,370 --> 00:33:23,360 Tetapi dalam kes paling teruk, satu-satunya tempat mungkin bahagian paling bawah data 781 00:33:23,360 --> 00:33:25,090 struktur, akhir sangat pelbagai. 782 00:33:25,090 --> 00:33:30,130 >> Jadi linear menyelesaikan sesuatu, dalam kes paling teruk, anaknya itu adalah turun ke dalam algoritma linear di mana 783 00:33:30,130 --> 00:33:34,500 Harun, jika dia berlaku akan dimasukkan lepas dalam struktur data ini, dia mungkin 784 00:33:34,500 --> 00:33:39,540 bertembung dengan lokasi pertama ini, tetapi kemudian berakhir dengan nasib malang pada akhir sangat. 785 00:33:39,540 --> 00:33:43,940 Jadi ini bukan berterusan masa suci kaedah berpotensi untuk kita. 786 00:33:43,940 --> 00:33:47,650 Pendekatan memasukkan unsur-unsur ke struktur data yang dipanggil hash 787 00:33:47,650 --> 00:33:52,050 jadual nampaknya tidak menjadi masa yang berterusan sekurang-kurangnya tidak dalam kes umum. 788 00:33:52,050 --> 00:33:54,000 Ia boleh menjadi sesuatu yang diturunkan linear. 789 00:33:54,000 --> 00:33:56,970 >> Jadi apa jika kita menyelesaikan pertembungan agak berbeza? 790 00:33:56,970 --> 00:34:00,740 Jadi di sini adalah yang lebih canggih pendekatan untuk apa yang masih 791 00:34:00,740 --> 00:34:02,800 dipanggil jadual hash. 792 00:34:02,800 --> 00:34:05,890 Dan dengan hash, sebagai diketepikan, apa yang Yang saya maksudkan adalah indeks yang 793 00:34:05,890 --> 00:34:07,070 Saya disebut lebih awal. 794 00:34:07,070 --> 00:34:09,810 Untuk sesuatu hash boleh dianggap sebagai kata kerja. 795 00:34:09,810 --> 00:34:13,690 >> Jadi, jika anda hash Alice adalah nama, fungsi hash, jadi untuk bercakap, 796 00:34:13,690 --> 00:34:14,710 perlu kembali nombor. 797 00:34:14,710 --> 00:34:18,199 Dalam kes ini adalah sifar jika dia tergolong di lokasi sifar, satu jika dia tergolong 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 setakat ini telah sangat mudah, 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 Tetapi fungsi hash mengambil sebagai input beberapa keping data, 802 00:34:29,090 --> 00:34:30,210 tali, int an, apa sahaja. 803 00:34:30,210 --> 00:34:32,239 Dan ia memuntahkannya keluar biasanya nombor. 804 00:34:32,239 --> 00:34:35,739 Dan bilangan yang mana data unsur tergolong dalam struktur data 805 00:34:35,739 --> 00:34:37,800 dikenali di sini sebagai sebuah jadual hash. 806 00:34:37,800 --> 00:34:41,400 >> Jadi hanya intuitif, ini adalah satu konteks yang sedikit berbeza. 807 00:34:41,400 --> 00:34:44,170 Ini sebenarnya adalah merujuk kepada contoh melibatkan hari lahir, di mana 808 00:34:44,170 --> 00:34:46,850 mungkin terdapat sebanyak 31 hari dalam bulan tersebut. 809 00:34:46,850 --> 00:34:52,239 Tetapi apa yang orang ini memutuskan untuk dilakukan sekiranya berlaku perlanggaran? 810 00:34:52,239 --> 00:34:55,304 Konteks kini sedang, bukan perlanggaran nama, tetapi perlanggaran hari lahir, 811 00:34:55,304 --> 00:35:00,760 jika dua orang mempunyai hari jadi yang sama pada ke-2 Oktober, misalnya. 812 00:35:00,760 --> 00:35:02,120 >> PELAJAR: [didengar]. 813 00:35:02,120 --> 00:35:05,010 >> SPEAKER 1: Ya, jadi di sini kita mempunyai yang memanfaatkan senarai berkaitan. 814 00:35:05,010 --> 00:35:07,830 Jadi ia kelihatan sedikit berbeza dari kita menarik ia awal. 815 00:35:07,830 --> 00:35:10,790 Tetapi kita nampaknya perlu array di sebelah kiri. 816 00:35:10,790 --> 00:35:13,230 Itulah salah satu indeks, tanpa sebab tertentu. 817 00:35:13,230 --> 00:35:14,630 Tetapi ia masih array. 818 00:35:14,630 --> 00:35:16,160 Ia adalah pelbagai petunjuk. 819 00:35:16,160 --> 00:35:20,670 Dan setiap unsur-unsur, setiap golongan-golongan ini atau garis condong - tanda palang 820 00:35:20,670 --> 00:35:23,970 mewakili null - masing-masing petunjuk nampaknya menunjuk ke 821 00:35:23,970 --> 00:35:25,730 apa struktur data? 822 00:35:25,730 --> 00:35:26,890 Satu senarai berkaitan. 823 00:35:26,890 --> 00:35:30,530 >> Jadi sekarang kita mempunyai keupayaan untuk kod keras ke dalam program kami 824 00:35:30,530 --> 00:35:32,010 saiz meja. 825 00:35:32,010 --> 00:35:35,360 Dalam hal ini, kita tahu ada tidak pernah lebih daripada 31 hari dalam sebulan. 826 00:35:35,360 --> 00:35:38,480 Begitu sukar pengekodan nilai seperti 31 adalah munasabah dalam konteks itu. 827 00:35:38,480 --> 00:35:42,700 Dalam konteks nama, keras pengekodan 26 tidak munasabah ia rakyat 828 00:35:42,700 --> 00:35:46,340 nama-nama yang hanya bermula dengan, misalnya, abjad melibatkan A hingga Z. 829 00:35:46,340 --> 00:35:50,180 >> Kami boleh mengasak mereka semua ke dalam data struktur selagi, apabila kita mendapat 830 00:35:50,180 --> 00:35:55,330 perlanggaran, kita tidak meletakkan nama-nama di sini, kita bukannya berfikir sel-sel 831 00:35:55,330 --> 00:36:00,270 tidak seperti tali diri mereka sendiri, tetapi sebagai petunjuk untuk, misalnya, Alice. 832 00:36:00,270 --> 00:36:03,660 Dan kemudian Alice boleh mempunyai penunjuk lain kepada nama lain bermula dengan 833 00:36:03,660 --> 00:36:06,150 A. Dan Bob sebenarnya berlaku di sini. 834 00:36:06,150 --> 00:36:10,850 >> Dan jika ada nama lain bermula dengan B, dia berakhir di sini. 835 00:36:10,850 --> 00:36:15,070 Dan sebagainya setiap elemen ini jadual dua, jika kita direka ini 836 00:36:15,070 --> 00:36:17,350 sedikit lebih bijak - 837 00:36:17,350 --> 00:36:18,125 datang pada - 838 00:36:18,125 --> 00:36:22,950 jika kita direka ini lebih sedikit bijak, kini menjadi data penyesuaian 839 00:36:22,950 --> 00:36:27,720 struktur, di mana tidak ada had keras kepada berapa banyak unsur-unsur anda boleh memasukkan 840 00:36:27,720 --> 00:36:30,700 ke dalam kerana jika anda mempunyai perlanggaran, itulah denda. 841 00:36:30,700 --> 00:36:34,690 Hanya pergi ke hadapan dan menambah kepada apa yang kita lihat sedikit lalu adalah 842 00:36:34,690 --> 00:36:38,290 dikenali sebagai senarai yang berkaitan. 843 00:36:38,290 --> 00:36:39,690 >> Nah mari kita berhenti untuk seketika. 844 00:36:39,690 --> 00:36:42,570 Apakah kebarangkalian perlanggaran di tempat pertama? 845 00:36:42,570 --> 00:36:45,480 Betul, mungkin saya lebih berfikir, mungkin Saya lebih kejuruteraan masalah ini, 846 00:36:45,480 --> 00:36:46,370 kerana anda tahu apa? 847 00:36:46,370 --> 00:36:49,070 Ya, saya boleh datang dengan sewenang-wenangnya contoh dari bahagian atas kepala saya seperti 848 00:36:49,070 --> 00:36:52,870 Allison dan Harun, tetapi dalam realiti, diberi taburan seragam 849 00:36:52,870 --> 00:36:56,990 input, iaitu beberapa sisipan rawak ke dalam struktur data, apa yang benar-benar 850 00:36:56,990 --> 00:36:58,580 kebarangkalian perlanggaran? 851 00:36:58,580 --> 00:37:01,670 Nah ternyata, ia sebenarnya super tinggi. 852 00:37:01,670 --> 00:37:03,850 Biar saya umum ini masalah adalah seperti ini. 853 00:37:03,850 --> 00:37:08,890 >> Jadi di dalam bilik n CS50 pelajar, apa yang kebarangkalian bahawa sekurang-kurangnya 854 00:37:08,890 --> 00:37:11,010 dua pelajar di dalam bilik mempunyai hari jadi yang sama? 855 00:37:11,010 --> 00:37:13,346 Jadi ada apa. anjing yang sedikit - 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 mahu bertanya kepada diri sendiri apa yang kebarangkalian dua orang 858 00:37:20,670 --> 00:37:23,930 di dalam bilik ini mempunyai hari jadi yang sama, kita boleh memikirkan ini. 859 00:37:23,930 --> 00:37:26,250 Dan saya benar-benar mendakwa terdapat dua orang-orang yang lahir yang sama. 860 00:37:26,250 --> 00:37:29,560 >> Sebagai contoh, adakah sesiapa mempunyai hari jadi hari ini? 861 00:37:29,560 --> 00:37:31,340 Semalam? 862 00:37:31,340 --> 00:37:32,590 Esok? 863 00:37:32,590 --> 00:37:35,980 Baiklah, jadi ia berasa seperti saya akan perlu melakukan ini 363 atau lebih lebih 864 00:37:35,980 --> 00:37:39,500 masa untuk benar-benar memahami jika kita mempunyai perlanggaran. 865 00:37:39,500 --> 00:37:42,350 Atau kita hanya boleh melakukan ini secara matematik bukannya tediously 866 00:37:42,350 --> 00:37:43,200 berbuat demikian. 867 00:37:43,200 --> 00:37:44,500 Dan mencadangkan yang berikut. 868 00:37:44,500 --> 00:37:48,740 >> Jadi, saya mencadangkan supaya kita boleh model Kebarangkalian dua orang yang mempunyai 869 00:37:48,740 --> 00:37:55,320 ulang tahun yang sama dengan kebarangkalian 1 tolak kemungkinan tiada siapa yang mempunyai 870 00:37:55,320 --> 00:37:56,290 hari lahir yang sama. 871 00:37:56,290 --> 00:37:59,960 Jadi untuk mendapatkan ini, dan ini hanya cara mewah untuk menulis ini, bagi 872 00:37:59,960 --> 00:38:03,090 orang pertama di dalam bilik, dia boleh mempunyai mana-mana satu yang mungkin 873 00:38:03,090 --> 00:38:07,370 hari lahir dengan andaian 365 hari dalam tahun ini, dengan memohon maaf kepada orang-orang dengan 874 00:38:07,370 --> 00:38:08,760 hari lahir 29 Februari. 875 00:38:08,760 --> 00:38:13,470 >> Jadi orang pertama di dalam bilik ini adalah percuma mempunyai apa-apa bilangan hari lahir 876 00:38:13,470 --> 00:38:18,280 daripada kemungkinan 365 supaya kami akan berbuat demikian 365 dibahagikan 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 yang akan datang di dalam bilik, jika matlamat adalah untuk mengelakkan perlanggaran, hanya boleh 879 00:38:22,700 --> 00:38:26,460 mempunyai atau hari jadi beliau tentang bagaimana beberapa hari yang berbeza mungkin? 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Jadi penggal kedua dalam ungkapan ini adalah dasarnya melakukan matematik yang bagi kami 882 00:38:31,430 --> 00:38:33,460 dengan menolak off satu hari mungkin. 883 00:38:33,460 --> 00:38:36,390 Dan kemudian pada hari berikutnya, hari akan datang, hari berikutnya ke jumlah 884 00:38:36,390 --> 00:38:38,100 orang di dalam bilik. 885 00:38:38,100 --> 00:38:41,290 >> Dan jika kita kemudian pertimbangkan, apakah cara kemungkinan tidak semua orang mempunyai 886 00:38:41,290 --> 00:38:45,265 hari lahir yang unik, tetapi sekali lagi 1 tolak itu, apa yang kita dapat adalah ungkapan 887 00:38:45,265 --> 00:38:47,810 yang boleh sangat fancifully kelihatan seperti ini. 888 00:38:47,810 --> 00:38:50,330 Tetapi ia lebih menarik melihat visual. 889 00:38:50,330 --> 00:38:55,120 Ini adalah carta di mana di paksi-x ialah jumlah orang di dalam bilik itu, 890 00:38:55,120 --> 00:38:56,180 beberapa hari lahir. 891 00:38:56,180 --> 00:38:59,840 Pada paksi-y kebarangkalian perlanggaran, dua orang 892 00:38:59,840 --> 00:39:01,230 mempunyai hari jadi yang sama. 893 00:39:01,230 --> 00:39:05,020 >> Dan bawa pulang dari keluk ini bahawa sebaik sahaja anda mendapat seperti 40 894 00:39:05,020 --> 00:39:11,110 pelajar, anda sehingga pada kebarangkalian 90% combinatorically dua 895 00:39:11,110 --> 00:39:13,550 orang atau lebih mempunyai hari lahir yang sama. 896 00:39:13,550 --> 00:39:18,600 Dan apabila anda mendapat 58 orang suka ia hampir 100% dari peluang kedua-dua 897 00:39:18,600 --> 00:39:21,310 orang di dalam bilik akan mempunyai hari jadi yang sama, walaupun terdapat 898 00:39:21,310 --> 00:39:26,650 365 atau 366 baldi mungkin, dan hanya 58 orang di dalam bilik. 899 00:39:26,650 --> 00:39:29,900 Hanya statistik anda mungkin mendapatkan perlanggaran, yang pendek 900 00:39:29,900 --> 00:39:31,810 mendorong perbincangan ini. 901 00:39:31,810 --> 00:39:35,890 Bahawa walaupun kita mendapatkan mewah di sini, dan mula mempunyai rantaian ini, kita masih 902 00:39:35,890 --> 00:39:36,950 akan mempunyai pertembungan. 903 00:39:36,950 --> 00:39:42,710 >> Jadi yang menimbulkan persoalan, apakah kos menjalankan sisipan dan pemotongan 904 00:39:42,710 --> 00:39:44,850 ke dalam struktur data yang seperti ini? 905 00:39:44,850 --> 00:39:46,630 Nah biar saya mencadangkan - 906 00:39:46,630 --> 00:39:51,570 dan biarlah saya kembali ke skrin di atas di sini - jika kita mempunyai n unsur dalam 907 00:39:51,570 --> 00:39:56,330 senarai, jadi jika kita cuba untuk memasukkan n elemen, dan kami mempunyai 908 00:39:56,330 --> 00:39:58,050 berapa jumlah baldi? 909 00:39:58,050 --> 00:40:03,450 Katakan 31 jumlah baldi dalam hal lahir. 910 00:40:03,450 --> 00:40:09,240 Apakah panjang maksimum satu ini rantaian berpotensi? 911 00:40:09,240 --> 00:40:12,670 >> Jika ada lagi 31 mungkin hari lahir pada bulan tertentu. 912 00:40:12,670 --> 00:40:14,580 Dan kami hanya pembungkusan materi semua orang - 913 00:40:14,580 --> 00:40:15,580 sebenarnya itu adalah satu contoh bodoh. 914 00:40:15,580 --> 00:40:16,960 Mari kita buat 26 sebaliknya. 915 00:40:16,960 --> 00:40:20,890 Jadi, jika benar-benar orang-orang yang mempunyai nama-nama bermula dengan A hingga Z, dengan itu memberi 916 00:40:20,890 --> 00:40:22,780 kita 26 kemungkinan. 917 00:40:22,780 --> 00:40:25,920 Dan kita menggunakan struktur data seperti yang kita hanya melihat, di mana kita mempunyai 918 00:40:25,920 --> 00:40:30,210 pelbagai petunjuk, yang mana setiap mata kepada senarai yang berkaitan di mana 919 00:40:30,210 --> 00:40:32,360 Senarai pertama adalah semua orang dengan nama Alice. 920 00:40:32,360 --> 00:40:35,770 Senarai kedua ialah setiap dengan nama bermula dengan A, bermula 921 00:40:35,770 --> 00:40:36,980 dengan B, dan sebagainya. 922 00:40:36,980 --> 00:40:41,020 >> Apa yang panjang mungkin setiap senarai mereka jika kita andaikan yang bersih baik 923 00:40:41,020 --> 00:40:45,410 pengedaran nama A hingga Z seluruh struktur data keseluruhan? 924 00:40:45,410 --> 00:40:50,210 Ada n orang dalam struktur data dibahagikan 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 masing-masing rantaian adalah n dibahagikan dengan 26. 927 00:40:54,970 --> 00:40:57,380 Tetapi dalam O notasi besar, apakah 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 ia adalah benar-benar hanya n, bukan? 931 00:41:04,150 --> 00:41:06,620 Kerana kita telah berkata pada masa lalu, ugh bahawa anda membahagikan sebanyak 26. 932 00:41:06,620 --> 00:41:08,710 Ya, dalam realiti, ia adalah lebih cepat. 933 00:41:08,710 --> 00:41:12,720 Tetapi dalam teori, ia bukan asasnya semua yang lebih cepat. 934 00:41:12,720 --> 00:41:16,040 >> Oleh itu, kita seolah-olah tidak menjadi semua yang banyak dekat dengan kaedah berpotensi suci ini. 935 00:41:16,040 --> 00:41:17,750 Malah, ini adalah hanya masa linear. 936 00:41:17,750 --> 00:41:20,790 Heck, pada ketika ini, mengapa tidak kita hanya menggunakan satu senarai dikaitkan besar? 937 00:41:20,790 --> 00:41:23,510 Mengapa kita tidak hanya menggunakan satu besar pelbagai untuk menyimpan nama-nama 938 00:41:23,510 --> 00:41:25,010 semua orang di dalam bilik? 939 00:41:25,010 --> 00:41:28,280 Nah, ada sesuatu yang masih menarik tentang jadual hash? 940 00:41:28,280 --> 00:41:30,810 Masih terdapat sesuatu yang menarik mengenai struktur data 941 00:41:30,810 --> 00:41:33,940 yang kelihatan seperti ini? 942 00:41:33,940 --> 00:41:35,182 Ini. 943 00:41:35,182 --> 00:41:37,050 >> PELAJAR: [didengar]. 944 00:41:37,050 --> 00:41:39,840 >> SPEAKER 1: Hak, dan sekali lagi jika ia hanya algoritma masa linear, dan 945 00:41:39,840 --> 00:41:42,780 struktur data masa linear, mengapa tidak saya hanya menyimpan nama semua orang dalam yang besar 946 00:41:42,780 --> 00:41:44,210 pelbagai, atau dalam senarai yang besar dikaitkan? 947 00:41:44,210 --> 00:41:47,010 Dan berhenti membuat CS begitu jauh lebih sukar dari ia perlu? 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 Apa yang menarik tentang perkara ini, walaupun walaupun saya tercalar ia keluar? 950 00:41:53,190 --> 00:41:54,930 >> PELAJAR: [didengar]. 951 00:41:54,930 --> 00:41:57,040 >> SPEAKER 1 sisipan 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 boleh masa yang berterusan, walaupun data anda 954 00:42:03,390 --> 00:42:07,910 struktur kelihatan seperti ini, pelbagai petunjuk, setiap yang menghala ke arah 955 00:42:07,910 --> 00:42:09,550 berpotensi senarai berkaitan. 956 00:42:09,550 --> 00:42:15,220 Bagaimana anda boleh mencapai berterusan memasukkan masa nama? 957 00:42:15,220 --> 00:42:16,280 Melekat di hadapan, bukan? 958 00:42:16,280 --> 00:42:19,290 >> Jika kita mengorbankan matlamat reka bentuk daripada sebelum ini, di mana kita mahu menyimpan 959 00:42:19,290 --> 00:42:22,650 nama semua orang, misalnya, disusun, atau semua nombor di atas pentas disusun, 960 00:42:22,650 --> 00:42:25,020 menganggap bahawa kita mempunyai senarai dikaitkan Unsorted. 961 00:42:25,020 --> 00:42:29,960 Ia hanya kos kami satu atau dua langkah, seperti dalam kes Ben dan Brian 962 00:42:29,960 --> 00:42:32,750 sebelum ini, untuk memasukkan elemen di permulaan senarai. 963 00:42:32,750 --> 00:42:36,090 Jadi, jika kita tidak mengambil berat tentang menyusun semua nama-nama yang bermula dengan A atau semua 964 00:42:36,090 --> 00:42:39,660 nama-nama yang bermula dengan B, kita masih boleh mencapai memasukkan masa yang berterusan. 965 00:42:39,660 --> 00:42:43,900 Kini melihat ke atas Alice atau Bob atau apa-apa nama secara umum masih apa? 966 00:42:43,900 --> 00:42:48,100 Ia adalah besar O n dibahagikan dengan 26, pada kes yang sesuai di mana semua orang adalah seragam 967 00:42:48,100 --> 00:42:51,190 diedarkan, di mana terdapat banyak A kerana ada yang Z, yang mungkin 968 00:42:51,190 --> 00:42:52,220 tidak realistik. 969 00:42:52,220 --> 00:42:53,880 Tetapi itu masih linear. 970 00:42:53,880 --> 00:42:57,120 >> Tetapi di sini, kami datang kembali ke titik notasi asimptot menjadi 971 00:42:57,120 --> 00:42:58,600 teorinya benar. 972 00:42:58,600 --> 00:43:02,960 Tetapi dalam dunia sebenar, jika saya mengatakan bahawa program saya boleh melakukan sesuatu yang 26 kali 973 00:43:02,960 --> 00:43:06,210 lebih cepat daripada anda, yang mana program 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 Realistik, orang yang ialah 26 kali lebih cepat, walaupun secara teori 976 00:43:14,320 --> 00:43:18,790 algoritma kami berjalan di yang sama asimptot berjalan masa. 977 00:43:18,790 --> 00:43:20,940 >> Biar saya mencadangkan yang berbeza penyelesaian sama sekali. 978 00:43:20,940 --> 00:43:24,380 Dan jika ini tidak meniup fikiran anda, kita berada di luar struktur data. 979 00:43:24,380 --> 00:43:27,420 Jadi ini adalah ia indone a - 980 00:43:27,420 --> 00:43:28,520 jenis nama bodoh. 981 00:43:28,520 --> 00:43:32,880 Ia datang daripada dapatan, dan perkataan dieja indone, t-r-i-e, kerana 982 00:43:32,880 --> 00:43:34,450 kursus semula bunyi seperti indone. 983 00:43:34,450 --> 00:43:36,580 Tetapi itu sejarah daripada indone perkataan. 984 00:43:36,580 --> 00:43:40,980 >> Jadi indone yang memang beberapa jenis pokok, dan ia juga yang bermain di perkataan itu. 985 00:43:40,980 --> 00:43:46,330 Dan walaupun anda tidak boleh agak melihatnya dengan visualisasi ini, indone adalah 986 00:43:46,330 --> 00:43:50,790 pokok berstruktur, seperti pokok kekeluargaan dengan satu moyang di atas dan banyak 987 00:43:50,790 --> 00:43:54,530 cucu dan cicit seperti daun di bahagian bawah. 988 00:43:54,530 --> 00:43:58,100 Tetapi setiap nod dalam indone adalah array. 989 00:43:58,100 --> 00:44:00,680 Dan ia adalah dalam array - dan mari menggampangkan seketika - ia adalah satu 990 00:44:00,680 --> 00:44:04,600 pelbagai, dalam hal ini, saiz 26, di mana setiap nod lagi adalah pelbagai saiz 991 00:44:04,600 --> 00:44:09,000 26, di mana unsur sifar dalam itu pelbagai mewakili A, dan yang terakhir 992 00:44:09,000 --> 00:44:11,810 elemen dalam setiap apa-apa pelbagai mewakili Z. 993 00:44:11,810 --> 00:44:15,520 >> Jadi saya mencadangkan, kemudian, bahawa data ini struktur, yang dikenali sebagai indone, boleh menjadi 994 00:44:15,520 --> 00:44:17,600 juga digunakan untuk menyimpan kata-kata. 995 00:44:17,600 --> 00:44:21,740 Kita melihat masa lalu bagaimana kita boleh menyimpan kata-kata, atau dalam kes ini nama-nama, dan kami 996 00:44:21,740 --> 00:44:25,440 lihat sebelum ini bagaimana kita boleh menyimpan nombor, tetapi jika kita memberi tumpuan kepada nama atau tali 997 00:44:25,440 --> 00:44:27,460 di sini, melihat apa yang menarik. 998 00:44:27,460 --> 00:44:32,210 Saya menuntut bahawa nama Maxwell adalah dalam struktur data ini. 999 00:44:32,210 --> 00:44:33,730 Di manakah anda melihat Maxwell? 1000 00:44:33,730 --> 00:44:35,140 >> PELAJAR: [didengar]. 1001 00:44:35,140 --> 00:44:36,240 >> SPEAKER 1: Di sebelah kiri. 1002 00:44:36,240 --> 00:44:39,910 Jadi apa yang menarik dengan data ini struktur adalah bukannya kedai 1003 00:44:39,910 --> 00:44:46,200 rentetan M-A-X-W-E-L-L backslash sifar, semua contiguously, apa yang anda lakukan dan bukannya 1004 00:44:46,200 --> 00:44:46,890 sedang mengikuti. 1005 00:44:46,890 --> 00:44:50,510 Jika ini adalah indone seperti struktur data, setiap nod yang sekali lagi array, 1006 00:44:50,510 --> 00:44:54,650 dan anda mahu menyimpan Maxwell, anda indeks dan sebagainya nod akar, jadi 1007 00:44:54,650 --> 00:44:57,810 untuk bercakap, nod yang paling atas, di lokasi M, betul, jadi 1008 00:44:57,810 --> 00:44:59,160 kira-kira ke tengah-tengah. 1009 00:44:59,160 --> 00:45:03,740 Dan kemudian dari sana, anda mengikuti penunjuk kepada nod kanak-kanak, jadi untuk bercakap. 1010 00:45:03,740 --> 00:45:06,150 Jadi, dalam erti kata pokok keluarga, anda mengikutinya ke bawah. 1011 00:45:06,150 --> 00:45:09,030 Dan yang membawa anda ke nod yang lain di sebelah kiri ada, yang 1012 00:45:09,030 --> 00:45:10,540 hanya pelbagai yang lain. 1013 00:45:10,540 --> 00:45:14,710 >> Dan kemudian jika anda mahu menyimpan Maxwell, anda mencari penunjuk 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 nod seterusnya. 1016 00:45:17,840 --> 00:45:20,100 Dan notis - ini adalah mengapa gambar ini yang terpedaya sedikit - 1017 00:45:20,100 --> 00:45:21,990 nod ini kelihatan super kecil. 1018 00:45:21,990 --> 00:45:26,050 Tetapi di sebelah kanan ini adalah Y dan Z. Ia hanya penulis telah dipenggal yang 1019 00:45:26,050 --> 00:45:27,630 gambar supaya anda benar-benar melihat sesuatu. 1020 00:45:27,630 --> 00:45:30,400 Jika gambar ini akan menjadi sangat luas. 1021 00:45:30,400 --> 00:45:36,180 Jadi sekarang anda index ke lokasi X, maka W, E Kemudian, maka L, maka L. Kemudian apa 1022 00:45:36,180 --> 00:45:37,380 rasa ingin tahu ini? 1023 00:45:37,380 --> 00:45:41,250 >> Nah, jika kita menggunakan jenis ini baru mengambil bagaimana untuk menyimpan tali dalam 1024 00:45:41,250 --> 00:45:44,500 struktur data, anda masih perlu asasnya memeriksa dalam data 1025 00:45:44,500 --> 00:45:47,250 struktur yang perkataan yang berakhir di sini. 1026 00:45:47,250 --> 00:45:50,830 Dalam erti kata lain, setiap nod ini entah bagaimana harus ingat bahawa kita 1027 00:45:50,830 --> 00:45:53,500 sebenarnya diikuti semua petunjuk dan meninggalkan sedikit 1028 00:45:53,500 --> 00:45:58,370 remah roti di bahagian bawah di sini ini struktur untuk menunjukkan M-A-X-W-E-L-L adalah 1029 00:45:58,370 --> 00:46:00,230 memang dalam struktur data ini. 1030 00:46:00,230 --> 00:46:02,040 >> Oleh itu, kita boleh melakukan ini seperti berikut. 1031 00:46:02,040 --> 00:46:06,810 Setiap satu daripada nod dalam gambar kita hanya saw mempunyai satu, pelbagai saiz 27. 1032 00:46:06,810 --> 00:46:10,550 Dan kini ia 27, kerana dalam p yang ditetapkan enam, kita benar-benar akan memberikan anda apostrofe, 1033 00:46:10,550 --> 00:46:13,590 supaya kita boleh mempunyai nama-nama seperti O'Reilly dan lain-lain dengan apostrofi. 1034 00:46:13,590 --> 00:46:14,820 Tetapi idea sama. 1035 00:46:14,820 --> 00:46:17,710 Setiap satu daripada unsur-unsur dalam mata untuk pelbagai struct a 1036 00:46:17,710 --> 00:46:19,320 nod, jadi hanya nod. 1037 00:46:19,320 --> 00:46:21,430 Jadi ini adalah sangat mengingatkan senarai berkaitan kami. 1038 00:46:21,430 --> 00:46:24,550 >> Dan kemudian saya mempunyai Boolean, yang saya akan memanggil perkataan, yang hanya akan menjadi 1039 00:46:24,550 --> 00:46:29,120 benar jika perkataan yang berakhir di nod dalam pokok itu. 1040 00:46:29,120 --> 00:46:32,870 Ia berkesan mewakili sedikit segi tiga yang kita lihat sebentar tadi. 1041 00:46:32,870 --> 00:46:37,190 Jadi, jika satu perkataan yang bermula pada nod dalam pokok, bahawa bidang perkataan akan menjadi kenyataan, 1042 00:46:37,190 --> 00:46:41,990 yang konsep memeriksa off, atau kita melukis segi tiga ini, ya ada 1043 00:46:41,990 --> 00:46:44,080 adalah perkataan di sini. 1044 00:46:44,080 --> 00:46:45,120 >> Jadi ini adalah indone a. 1045 00:46:45,120 --> 00:46:48,540 Dan kini persoalannya ialah, apa yang sedang berjalan itu masa? 1046 00:46:48,540 --> 00:46:49,930 Adakah ia besar O n? 1047 00:46:49,930 --> 00:46:51,410 Adakah ia sesuatu yang berlainan? 1048 00:46:51,410 --> 00:46:57,330 Nah, jika anda mempunyai n nama dalam data ini struktur, Maxwell menjadi hanya salah satu daripada 1049 00:46:57,330 --> 00:47:02,330 mereka, apakah masa perjalanan memasukkan atau mencari Maxwell? 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Apa masa larian memasukkan Maxwell? 1052 00:47:09,050 --> 00:47:11,740 Jika ada n nama-nama lain sudah dalam jadual? 1053 00:47:11,740 --> 00:47:12,507 Ya? 1054 00:47:12,507 --> 00:47:15,429 >> PELAJAR: [didengar]. 1055 00:47:15,429 --> 00:47:17,550 >> SPEAKER 1: Ya, ia adalah panjang nama, bukan? 1056 00:47:17,550 --> 00:47:24,420 Jadi M-a-x-w-e-l-l jadi ia berasa seperti ini algoritma adalah besar O tujuh. 1057 00:47:24,420 --> 00:47:26,580 Kini, sudah tentu, nama akan berbeza-beza. 1058 00:47:26,580 --> 00:47:27,380 Mungkin ia adalah nama yang singkat. 1059 00:47:27,380 --> 00:47:28,600 Mungkin ia adalah nama yang lebih panjang. 1060 00:47:28,600 --> 00:47:33,390 Tetapi apa yang penting di sini ialah bahawa ia adalah satu jumlah yang tetap. 1061 00:47:33,390 --> 00:47:36,810 Dan mungkin ia tidak benar-benar berterusan, tetapi tuhan, jika realistik, dalam 1062 00:47:36,810 --> 00:47:41,570 kamus, ada mungkin beberapa had kepada bilangan huruf dalam 1063 00:47:41,570 --> 00:47:43,820 nama orang itu dalam negara tertentu. 1064 00:47:43,820 --> 00:47:46,940 >> Dan supaya kita boleh mengandaikan bahawa nilai adalah satu pemalar. 1065 00:47:46,940 --> 00:47:47,750 Saya tidak tahu apa yang ada. 1066 00:47:47,750 --> 00:47:50,440 Ia mungkin lebih besar daripada kita fikir ia. 1067 00:47:50,440 --> 00:47:52,720 Kerana selalu ada beberapa sudut kes dengan nama yang panjang gila. 1068 00:47:52,720 --> 00:47:56,360 Jadi mari kita memanggilnya k, tetapi ia masih berterusan mungkin, kerana setiap 1069 00:47:56,360 --> 00:48:00,190 nama di dunia, sekurang-kurangnya dalam negara tertentu, adalah panjang yang atau 1070 00:48:00,190 --> 00:48:01,780 pendek, jadi ia tetap. 1071 00:48:01,780 --> 00:48:04,490 Tetapi apabila kita telah berkata sesuatu yang besar O nilai yang tetap, apa yang 1072 00:48:04,490 --> 00:48:07,760 benar-benar sama dengan? 1073 00:48:07,760 --> 00:48:10,420 Itu benar-benar perkara yang sama sebagai berkata masa yang berterusan. 1074 00:48:10,420 --> 00:48:11,530 >> Sekarang kita jenis penipuan, bukan? 1075 00:48:11,530 --> 00:48:15,340 Kami jenis memanfaatkan teori beberapa di sini untuk mengatakan yang baik, perintah k ialah 1076 00:48:15,340 --> 00:48:17,450 benar-benar hanya memerintahkan satu, dan ia adalah masa yang berterusan. 1077 00:48:17,450 --> 00:48:18,200 Tetapi ia benar-benar adalah. 1078 00:48:18,200 --> 00:48:22,550 Kerana wawasan utama di sini adalah bahawa jika kita mempunyai n nama pun dalam 1079 00:48:22,550 --> 00:48:26,010 struktur data, dan kami memasukkan Maxwell, ialah jumlah masa yang membawa kita ke 1080 00:48:26,010 --> 00:48:29,530 memasukkan Maxwell pada semua yang terlibat dengan berapa ramai orang lain 1081 00:48:29,530 --> 00:48:31,100 adalah dalam struktur data? 1082 00:48:31,100 --> 00:48:31,670 Nampaknya tidak menjadi. 1083 00:48:31,670 --> 00:48:36,280 Jika saya mempunyai satu bilion lebih unsur ini indone, dan kemudian memasukkan Maxwell, adalah 1084 00:48:36,280 --> 00:48:38,650 beliau pada semua yang terlibat? 1085 00:48:38,650 --> 00:48:39,050 No 1086 00:48:39,050 --> 00:48:42,950 Dan yang tidak seperti mana-mana data hari struktur yang kita lihat setakat ini, di mana 1087 00:48:42,950 --> 00:48:46,820 masa berjalan algoritma anda benar-benar bebas daripada berapa banyak 1088 00:48:46,820 --> 00:48:51,430 barangan atau tidak sudah dalam struktur data. 1089 00:48:51,430 --> 00:48:54,650 >> Dan sebagainya dengan ini mampu anda sekarang adalah peluang untuk p set enam, yang akan 1090 00:48:54,650 --> 00:48:58,310 sekali lagi melibatkan melaksanakan anda sendiri pemeriksa ejaan, membaca dalam 150,000 1091 00:48:58,310 --> 00:49:01,050 kata-kata, cara terbaik untuk menyimpan yang tidak semestinya jelas. 1092 00:49:01,050 --> 00:49:04,030 Dan walaupun saya telah bercita-cita untuk mencari kaedah berpotensi suci, saya tidak 1093 00:49:04,030 --> 00:49:05,330 mendakwa bahawa indone adalah. 1094 00:49:05,330 --> 00:49:09,810 Malah, satu jadual hash boleh sangat baik membuktikan untuk menjadi lebih cekap. 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 daripada keputusan reka bentuk anda akan mempunyai untuk membuat. 1097 00:49:14,620 --> 00:49:18,920 >> Tetapi dalam menutup mari kita 50 atau lebih saat untuk mengambil mengintip pada apa yang terletak di 1098 00:49:18,920 --> 00:49:22,190 seminggu sebelum datang dan seterusnya kita peralihan daripada baris arahan ini 1099 00:49:22,190 --> 00:49:26,220 dunia jika program C kepada perkara-perkara web berdasarkan dan bahasa seperti PHP dan 1100 00:49:26,220 --> 00:49:30,350 JavaScript dan internet itu sendiri, protokol seperti HTTP, yang anda telah 1101 00:49:30,350 --> 00:49:32,870 diambil untuk diberikan selama bertahun-tahun sekarang, dan yang paling ditaip 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 mula mengupas kembali lapisan apa yang internet. 1104 00:49:37,420 --> 00:49:40,650 Dan apa kod yang mendasari alat hari ini. 1105 00:49:40,650 --> 00:49:43,230 Jadi 50 saat penggoda ini di sini. 1106 00:49:43,230 --> 00:49:46,570 Saya memberi anda Warriors of Internet. 1107 00:49:46,570 --> 00:49:51,370 >> [MAIN SEMULA VIDEO] 1108 00:49:51,370 --> 00:49:56,764 >> -Beliau datang dengan mesej. 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, peduli router, dan bahaya yang jauh 1112 00:50:19,780 --> 00:50:22,600 lebih teruk 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 mendapat alamat anda. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Warriors of Internet. 1119 00:50:34,590 --> 00:50:35,290 >> [AKHIR VIDEO MAIN SEMULA] 1120 00:50:35,290 --> 00:50:38,070 >> SPEAKER 1: Itu adalah bagaimana internet boleh bekerja pada minggu depan. 1121 00:50:38,070 --> 00:50:40,406