1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [MUSIK BERMAIN] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 SPEAKER 1: Baiklah. 5 00:00:12,900 --> 00:00:14,600 Semua orang selamat datang kembali ke bahagian. 6 00:00:14,600 --> 00:00:18,660 Saya berharap anda semua berjaya pulih dari kuiz anda 7 00:00:18,660 --> 00:00:19,510 dari minggu lepas. 8 00:00:19,510 --> 00:00:22,564 Saya tahu ia adalah sedikit gila di kali. 9 00:00:22,564 --> 00:00:25,230 Seperti yang saya katakan sebelum ini, jika anda dalam sisihan piawai, 10 00:00:25,230 --> 00:00:28,188 tidak benar-benar bimbang tentang hal itu, terutama seksyen yang kurang selesa. 11 00:00:28,188 --> 00:00:30,230 Itulah kira-kira di mana anda harus. 12 00:00:30,230 --> 00:00:32,850 >> Jika anda melakukan besar, maka yang menggerunkan. 13 00:00:32,850 --> 00:00:33,650 Tahniah kepada anda. 14 00:00:33,650 --> 00:00:36,149 Dan jika anda merasa seperti anda perlu sedikit bantuan lanjut, sila 15 00:00:36,149 --> 00:00:38,140 merasa bebas untuk mencapai kepada mana-mana TF. 16 00:00:38,140 --> 00:00:40,030 Kita semua di sini untuk membantu. 17 00:00:40,030 --> 00:00:40,960 >> Itulah sebabnya kita mengajar. 18 00:00:40,960 --> 00:00:44,550 Itu sebabnya saya di sini setiap hari Isnin untuk anda orang-orang dan pada waktu pejabat pada hari Khamis. 19 00:00:44,550 --> 00:00:48,130 Jadi jangan ragu untuk membiarkan saya tahu jika anda bimbang tentang apa-apa 20 00:00:48,130 --> 00:00:52,450 atau jika ada apa-apa pada kuiz bahawa anda benar-benar ingin untuk menangani. 21 00:00:52,450 --> 00:00:56,940 >> Jadi agenda untuk hari ini adalah semua tentang struktur data. 22 00:00:56,940 --> 00:01:01,520 Beberapa di antaranya hanya akan menjadi hanya untuk anda berjinak dengan ini. 23 00:01:01,520 --> 00:01:04,870 Anda mungkin tidak pernah melaksanakan mereka di dalam kelas ini. 24 00:01:04,870 --> 00:01:08,690 Sesetengah daripada mereka yang anda akan, seperti untuk Serangga ejaan anda. 25 00:01:08,690 --> 00:01:11,380 >> Anda akan mempunyai pilihan anda antara jadual hash dan cuba. 26 00:01:11,380 --> 00:01:13,680 Oleh itu, kita akan pasti akan ke atas. 27 00:01:13,680 --> 00:01:18,690 Ia akan menjadi pasti lebih dari jenis seksyen yang tinggi hari ini, walaupun, 28 00:01:18,690 --> 00:01:22,630 kerana ada banyak dari mereka, dan jika kami pergi ke butir-butir pelaksanaan 29 00:01:22,630 --> 00:01:26,490 pada semua ini, kita tidak akan bahkan melewati daftar terkait 30 00:01:26,490 --> 00:01:28,520 dan mungkin sedikit jadual hash. 31 00:01:28,520 --> 00:01:31,200 >> Jadi beruang dengan saya. 32 00:01:31,200 --> 00:01:33,530 Kami tidak akan melakukan sebanyak coding masa ini. 33 00:01:33,530 --> 00:01:36,870 Jika anda mempunyai apa-apa soalan tentang hal itu atau anda mahu melihat ia dilaksanakan 34 00:01:36,870 --> 00:01:39,260 atau cuba untuk diri sendiri, Saya pasti mengesyorkan 35 00:01:39,260 --> 00:01:44,250 akan study.cs50.net, yang mempunyai contoh-contoh semua ini. 36 00:01:44,250 --> 00:01:46,400 Ia akan mempunyai Power Point saya dengan nota-nota yang kita 37 00:01:46,400 --> 00:01:50,860 cenderung untuk menggunakan dan juga beberapa program latihan, terutama untuk perkara-perkara 38 00:01:50,860 --> 00:01:55,250 seperti daftar terhubung dan binari pokok tumpukan dan isyarat. 39 00:01:55,250 --> 00:01:59,590 Jadi sedikit tingkat yang lebih tinggi, yang mungkin lebih baik untuk kalian. 40 00:01:59,590 --> 00:02:01,320 >> Maka dengan itu, kami akan memulakan. 41 00:02:01,320 --> 00:02:03,060 Dan juga, yes-- kuiz. 42 00:02:03,060 --> 00:02:06,550 Saya rasa kebanyakan dari orang-orang yang berada dalam seksyen saya mempunyai kuiz anda, 43 00:02:06,550 --> 00:02:12,060 tetapi ada orang datang di atau sebab-sebab tertentu anda tidak, mereka di sini di depan. 44 00:02:12,060 --> 00:02:12,740 >> Begitu dihubungkan senarai. 45 00:02:12,740 --> 00:02:15,650 Saya tahu ini jenis pergi ke belakang sebelum kuiz anda. 46 00:02:15,650 --> 00:02:17,940 Itu adalah seminggu sebelum yang kita pelajari tentang hal ini. 47 00:02:17,940 --> 00:02:21,040 Tetapi dalam kes ini, kita hanya akan pergi sedikit lebih mendalam. 48 00:02:21,040 --> 00:02:25,900 >> Jadi mengapa kita mungkin memilih linked list lebih array? 49 00:02:25,900 --> 00:02:27,130 Apa yang membezakan mereka? 50 00:02:27,130 --> 00:02:27,630 Ya? 51 00:02:27,630 --> 00:02:30,464 >> PENONTON: Anda boleh mengembangkan berpaut daftar berbanding ukuran tetap array ini. 52 00:02:30,464 --> 00:02:31,171 SPEAKER 1: Benar. 53 00:02:31,171 --> 00:02:33,970 Pelbagai telah menetapkan ukuran sedangkan linked list mempunyai saiz yang berubah-ubah. 54 00:02:33,970 --> 00:02:36,970 Jadi, jika kita tidak tahu bagaimana banyak yang kita mahu untuk menyimpan, 55 00:02:36,970 --> 00:02:39,880 senarai berpaut memberi kita yang besar cara untuk melakukan itu kerana kita boleh hanya 56 00:02:39,880 --> 00:02:43,730 menambah nod lain dan menambah nod lain dan menambah nod lain. 57 00:02:43,730 --> 00:02:45,750 Tetapi apa yang mungkin menjadi trade-off? 58 00:02:45,750 --> 00:02:49,521 Apakah ada yang ingat trade-off antara tatasusunan dan daftar link? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> PENONTON: Anda perlu melalui semua cara yang 61 00:02:51,460 --> 00:02:53,738 melalui senarai terkait mencari elemen dalam senarai. 62 00:02:53,738 --> 00:02:55,570 Dalam array, anda boleh hanya menemukan unsur. 63 00:02:55,570 --> 00:02:56,278 >> SPEAKER 1: Benar. 64 00:02:56,278 --> 00:02:57,120 Jadi dengan arrays-- 65 00:02:57,120 --> 00:02:58,500 >> PENONTON: [didengar]. 66 00:02:58,500 --> 00:03:01,090 >> SPEAKER 1: Dengan array, kita ada apa yang disebut capaian rawak. 67 00:03:01,090 --> 00:03:04,820 Bermakna jika kita mahu apa yang pernah titik kelima senarai 68 00:03:04,820 --> 00:03:07,230 atau titik kelima kami array, kita hanya boleh ambil itu. 69 00:03:07,230 --> 00:03:10,440 Jika ia senarai yang disambungkan, kita ada untuk beralih melalui, kan? 70 00:03:10,440 --> 00:03:14,020 Jadi mengakses unsur dalam array adalah masa yang berterusan, 71 00:03:14,020 --> 00:03:19,530 sedangkan dengan senarai berpaut itu akan kemungkinan besar akan masa linear kerana mungkin 72 00:03:19,530 --> 00:03:21,370 elemen kami adalah semua cara di akhir. 73 00:03:21,370 --> 00:03:23,446 Kita perlu mencari melalui segala-galanya. 74 00:03:23,446 --> 00:03:25,320 Jadi, dengan semua data ini struktur kita akan 75 00:03:25,320 --> 00:03:29,330 yang akan menghabiskan lebih banyak masa sedikit di, apakah kebaikan dan negatif. 76 00:03:29,330 --> 00:03:31,480 Apabila kita mungkin mahu menggunakan salah satu dari yang lain? 77 00:03:31,480 --> 00:03:34,970 Dan itulah jenis yang hal yang lebih besar untuk mengambil. 78 00:03:34,970 --> 00:03:40,140 >> Jadi kita mempunyai di sini definisi nod. 79 00:03:40,140 --> 00:03:43,040 Ia seperti satu elemen dalam linked list kita, kan? 80 00:03:43,040 --> 00:03:46,180 Oleh itu, kita semua biasa dengan struct typedef kami, 81 00:03:46,180 --> 00:03:47,980 yang kami pergi lebih dalam kajian masa lepas. 82 00:03:47,980 --> 00:03:53,180 Ia pada dasarnya hanya mewujudkan lain jenis data yang kita boleh gunakan. 83 00:03:53,180 --> 00:03:57,930 >> Dan dalam kes ini, ia adalah beberapa nod yang akan mengadakan beberapa integer dalam. 84 00:03:57,930 --> 00:04:00,210 Dan kemudian apa yang bahagian kedua di sini? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Sesiapa sahaja? 87 00:04:05,677 --> 00:04:06,680 >> PENONTON: [didengar]. 88 00:04:06,680 --> 00:04:07,020 >> SPEAKER 1: Ya. 89 00:04:07,020 --> 00:04:08,400 Ia adalah penunjuk ke nod seterusnya. 90 00:04:08,400 --> 00:04:12,610 Jadi ini sebenarnya harus di sini. 91 00:04:12,610 --> 00:04:18,790 Ini adalah penunjuk dari jenis nod untuk perkara yang akan datang. 92 00:04:18,790 --> 00:04:22,410 Dan itulah apa yang mereka merangkumi nod kami. 93 00:04:22,410 --> 00:04:24,060 Sejuk. 94 00:04:24,060 --> 00:04:29,390 >> Baiklah, jadi dengan carian, karena kami hanya mengatakan sebelum tangan, jika anda 95 00:04:29,390 --> 00:04:31,840 akan mencari melalui, Anda harus benar-benar beralih 96 00:04:31,840 --> 00:04:33,660 melalui linked list anda. 97 00:04:33,660 --> 00:04:38,530 Jadi, jika kita cari bilangan 9, kita akan bermula di kepala kita 98 00:04:38,530 --> 00:04:41,520 dan yang mengarahkan kita pada permulaan dari linked list kita, kan? 99 00:04:41,520 --> 00:04:44,600 Dan kita berkata, OK, adakah ini nod mengandungi bilangan 9? 100 00:04:44,600 --> 00:04:45,690 Tidak? 101 00:04:45,690 --> 00:04:47,500 >> Baiklah, pergi ke satu depan. 102 00:04:47,500 --> 00:04:48,312 Mengikutinya. 103 00:04:48,312 --> 00:04:49,520 Adakah ia mengandungi bilangan 9? 104 00:04:49,520 --> 00:04:50,570 Tidak. 105 00:04:50,570 --> 00:04:51,550 Ikuti salah satu yang akan datang. 106 00:04:51,550 --> 00:04:55,490 >> Oleh itu, kita harus benar-benar beralih melalui linked list kami. 107 00:04:55,490 --> 00:05:00,070 Kita tidak boleh hanya pergi terus ke mana 9 adalah. 108 00:05:00,070 --> 00:05:05,860 Dan jika kalian benar-benar ingin melihat beberapa pseudo-kod di atas sana. 109 00:05:05,860 --> 00:05:10,420 Kami mempunyai beberapa fungsi pencarian di sini yang mengambil dalam- apakah yang diperlukan dalam? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Apa yang anda fikir? 112 00:05:14,320 --> 00:05:15,960 Satu begitu mudah. 113 00:05:15,960 --> 00:05:17,784 Apa ini? 114 00:05:17,784 --> 00:05:18,700 PENONTON: [didengar]. 115 00:05:18,700 --> 00:05:20,366 SPEAKER 1: Jumlah yang kami cari. 116 00:05:20,366 --> 00:05:20,980 Betul? 117 00:05:20,980 --> 00:05:22,875 Dan apa ini akan sesuai dengan? 118 00:05:22,875 --> 00:05:25,020 Ia adalah penunjuk ke? 119 00:05:25,020 --> 00:05:26,000 >> PENONTON: nod A. 120 00:05:26,000 --> 00:05:28,980 >> SPEAKER 1: nod ke dalam senarai bahawa kita sedang melihat, kan? 121 00:05:28,980 --> 00:05:33,700 Oleh itu, kita mempunyai beberapa nod adalah penunjuk di sini. 122 00:05:33,700 --> 00:05:37,240 Ini adalah titik yang akan sebenarnya beralih melalui senarai kami. 123 00:05:37,240 --> 00:05:39,630 Kami set sama dengan daftar kerana itulah 124 00:05:39,630 --> 00:05:44,380 menetapkan ia sama dengan mulai dari linked list kami. 125 00:05:44,380 --> 00:05:50,660 >> Dan manakala ia bukan NULL, manakala kita masih ada kerja lain yang dalam senarai kami, 126 00:05:50,660 --> 00:05:55,580 memeriksa untuk melihat jika nod yang mempunyai jumlah yang kami cari. 127 00:05:55,580 --> 00:05:57,740 Kembali benar. 128 00:05:57,740 --> 00:06:01,070 Jika tidak, mengemaskinikannya, kan? 129 00:06:01,070 --> 00:06:04,870 >> Jika ia adalah NULL, kami keluar kami while dan pulangan palsu 130 00:06:04,870 --> 00:06:08,340 kerana itu bermakna kami tidak menjumpainya. 131 00:06:08,340 --> 00:06:11,048 Adakah semua orang mendapatkan cara yang bekerja? 132 00:06:11,048 --> 00:06:11,548 OK. 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> Jadi dengan penyisipan, anda mempunyai tiga cara yang berbeza. 135 00:06:20,260 --> 00:06:25,250 Anda boleh tambahkan, anda boleh menambah dan anda boleh masukkan ke dalam berbagai macam. 136 00:06:25,250 --> 00:06:28,215 Dalam hal ini, kami tidak akan melakukan tambahkan satu. 137 00:06:28,215 --> 00:06:33,380 Apakah ada yang tahu bagaimana tiga kes mungkin berbeza? 138 00:06:33,380 --> 00:06:36,920 >> Jadi tambahkan bermakna anda meletakkan ia di depan senarai anda. 139 00:06:36,920 --> 00:06:39,770 Jadi ini bermakna bahawa tidak kira apa nod anda, tidak kira 140 00:06:39,770 --> 00:06:43,160 apa nilai tersebut, anda akan untuk meletakkannya di sini di depan, OK? 141 00:06:43,160 --> 00:06:45,160 Ia akan menjadi yang pertama elemen dalam senarai anda. 142 00:06:45,160 --> 00:06:49,510 >> Jika anda menambah ia, ia akan untuk pergi ke belakang senarai anda. 143 00:06:49,510 --> 00:06:54,010 Dan masukkan ke dalam berbagai macam ertinya anda akan meletakkan benar-benar ke dalam tempat 144 00:06:54,010 --> 00:06:57,700 di mana ia menyimpan daftar link anda disusun. 145 00:06:57,700 --> 00:07:00,810 Sekali lagi, bagaimana anda menggunakan orang-orang dan apabila anda menggunakan 146 00:07:00,810 --> 00:07:02,530 mereka akan berbeza-beza bergantung kepada kes anda. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Jika ia tidak perlu diurutkan, tambahkan cenderung 149 00:07:07,750 --> 00:07:10,460 jadi apa yang kebanyakan orang digunakan kerana anda tidak 150 00:07:10,460 --> 00:07:15,680 perlu melalui seluruh senarai untuk mencari akhirnya menambahkannya, kan? 151 00:07:15,680 --> 00:07:17,720 Anda hanya boleh bertahan di dalam. 152 00:07:17,720 --> 00:07:21,930 >> Oleh itu, kita akan melalui penyisipan 1 sekarang. 153 00:07:21,930 --> 00:07:26,360 Jadi satu perkara yang saya akan sangat mengesyorkan pada Serangga ini 154 00:07:26,360 --> 00:07:29,820 adalah untuk menarik perkara-perkara yang keluar, seperti biasa. 155 00:07:29,820 --> 00:07:35,130 Ini sangat penting bahawa anda mengemas kini pointer anda dalam susunan yang betul 156 00:07:35,130 --> 00:07:38,620 kerana jika anda mengemaskinikannya sedikit daripada perintah, 157 00:07:38,620 --> 00:07:42,210 Anda akan berakhir kehilangan bagian dari senarai anda. 158 00:07:42,210 --> 00:07:49,680 >> Jadi, sebagai contoh, dalam hal ini, kami tidak memberitahu kepala untuk hanya titik ke 1. 159 00:07:49,680 --> 00:07:56,070 Jika kita hanya melakukan itu tanpa menyimpan ini 1, 160 00:07:56,070 --> 00:07:58,570 kita tidak tahu apa yang 1 harus menunjuk ke sekarang 161 00:07:58,570 --> 00:08:02,490 kerana kita telah kehilangan apa yang kepala menunjuk. 162 00:08:02,490 --> 00:08:05,530 Jadi, satu hal yang perlu diingat ketika sedang melakukan tambahkan satu 163 00:08:05,530 --> 00:08:09,630 adalah untuk menyelamatkan apa yang tempat kepala terlebih dahulu, 164 00:08:09,630 --> 00:08:15,210 kemudian menetapkan kembali, dan kemudian mengemas apa nod baru anda harus menunjuk ke. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 Dalam hal ini, ini adalah salah satu cara untuk melakukannya. 167 00:08:22,560 --> 00:08:25,440 >> Jadi jika kita melakukannya dengan cara ini di mana kita hanya ditugaskan semula kepala, 168 00:08:25,440 --> 00:08:30,320 kita kehilangan pada dasarnya kami semua senarai, kan? 169 00:08:30,320 --> 00:08:38,000 Salah satu cara untuk melakukannya adalah untuk mempunyai 1 mata berikutnya, dan kemudian ada benarnya kepala ke 1. 170 00:08:38,000 --> 00:08:42,650 Atau anda boleh melakukan jenis seperti penyimpanan sementara, yang saya bercakap tentang. 171 00:08:42,650 --> 00:08:45,670 >> Tetapi pemindahan anda pointer dalam susunan yang betul 172 00:08:45,670 --> 00:08:48,750 akan menjadi sangat, sangat penting bagi Serangga ini. 173 00:08:48,750 --> 00:08:53,140 Jika tidak, anda akan mempunyai hash meja atau cuba itu hanya akan menjadi 174 00:08:53,140 --> 00:08:56,014 hanya sebahagian daripada kata-kata yang anda mahu dan kemudian mmhmm you're--? 175 00:08:56,014 --> 00:08:58,930 PENONTON: Apa yang sementara hal penyimpanan anda bercakap tentang? 176 00:08:58,930 --> 00:09:00,305 SPEAKER 1: penyimpanan sementara. 177 00:09:00,305 --> 00:09:02,760 Jadi, pada asasnya lain cara yang anda boleh lakukan ini 178 00:09:02,760 --> 00:09:07,650 yang menyimpan kepala sesuatu, seperti menyimpannya pembolehubah sementara. 179 00:09:07,650 --> 00:09:11,250 Menetapkan ke 1 dan kemudian update 1 ke titik 180 00:09:11,250 --> 00:09:13,830 untuk apa sahaja kepala yang digunakan untuk menunjuk ke. 181 00:09:13,830 --> 00:09:16,920 Dengan cara ini adalah jelas lebih elegan kerana anda 182 00:09:16,920 --> 00:09:20,770 tidak memerlukan nilai sementara, tetapi hanya menawarkan satu lagi cara untuk melakukannya. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 Dan kita benar-benar mempunyai beberapa kod untuk ini. 185 00:09:25,790 --> 00:09:28,080 Jadi untuk linked list, kami sebenarnya ada beberapa kod. 186 00:09:28,080 --> 00:09:31,930 Jadi masukkan di sini, ini adalah mengawali. 187 00:09:31,930 --> 00:09:34,290 Jadi ini mula ia di kepala. 188 00:09:34,290 --> 00:09:38,820 >> Sehingga hal pertama, anda perlu membuat nod baru anda, tentu saja, 189 00:09:38,820 --> 00:09:40,790 dan periksa NULL. 190 00:09:40,790 --> 00:09:43,250 Selalu baik. 191 00:09:43,250 --> 00:09:47,840 Dan kemudian anda perlu untuk menetapkan nilai-nilai. 192 00:09:47,840 --> 00:09:51,260 Setiap kali anda membuat nod baru, anda tidak tahu apa yang ia menunjuk ke depan, 193 00:09:51,260 --> 00:09:54,560 sehingga anda ingin memulakan untuk NULL. 194 00:09:54,560 --> 00:09:58,760 Jika ia akhirnya menunjuk kepada sesuatu yang lain, hal itu akan ditugaskan semula dan tidak apa-apa. 195 00:09:58,760 --> 00:10:00,740 Jika itu perkara pertama yang dalam senarai, ia perlu 196 00:10:00,740 --> 00:10:04,270 untuk menunjuk ke NULL kerana itulah akhir dari senarai. 197 00:10:04,270 --> 00:10:12,410 >> Jadi kemudian memasukkannya, kita lihat di sini kita yang memberikan nilai seterusnya nod kami 198 00:10:12,410 --> 00:10:17,380 untuk menjadi apa yang kepala adalah, yang adalah apa yang kami di sini. 199 00:10:17,380 --> 00:10:19,930 Itu yang kami baru saja melakukannya. 200 00:10:19,930 --> 00:10:25,820 Dan kemudian kami memberikan kepala ke titik untuk nod baru kita, kerana ingat, 201 00:10:25,820 --> 00:10:31,090 baru beberapa penunjuk kepada nod, dan itulah yang kepala. 202 00:10:31,090 --> 00:10:34,370 Itulah sebabnya kita mempunyai panah ini pencapai. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 Cool? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> PENONTON: Apakah kita harus memulakan seterusnya baru ke NULL pertama, 207 00:10:41,100 --> 00:10:44,240 atau kita hanya boleh memulakan itu untuk kepala? 208 00:10:44,240 --> 00:10:48,210 >> SPEAKER 1: New seterusnya perlu menjadi NULL untuk memulakan 209 00:10:48,210 --> 00:10:53,760 kerana anda tidak tahu di mana ia akan menjadi. 210 00:10:53,760 --> 00:10:56,100 Juga, ini adalah jenis hanya suka paradigma. 211 00:10:56,100 --> 00:10:59,900 Anda set sama dengan NULL hanya untuk memastikan bahawa semua asas anda dilindungi 212 00:10:59,900 --> 00:11:04,070 sebelum anda melakukan apa-apa tugas kembali supaya anda sentiasa dijamin bahawa ia akan 213 00:11:04,070 --> 00:11:08,880 menunjuk kepada nilai tertentu berbanding seperti nilai sampah. 214 00:11:08,880 --> 00:11:12,210 Kerana, ya, kita memberikan baru yang akan datang secara automatik, 215 00:11:12,210 --> 00:11:15,420 tetapi ia lebih adil seperti amalan yang baik untuk memulakan ia 216 00:11:15,420 --> 00:11:19,270 dengan cara itu dan kemudian menetapkan kembali. 217 00:11:19,270 --> 00:11:23,420 >> OK, jadi ganda terkait daftar sekarang. 218 00:11:23,420 --> 00:11:24,601 Apa yang kita fikir? 219 00:11:24,601 --> 00:11:26,350 Apa yang berbeza dengan penggandaan senarai? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Jadi dalam daftar link kita, kita dapat hanya bergerak dalam satu arah, bukan? 222 00:11:34,300 --> 00:11:35,270 Kami hanya mempunyai depan. 223 00:11:35,270 --> 00:11:36,760 Kita hanya boleh pergi ke hadapan. 224 00:11:36,760 --> 00:11:40,300 >> Dengan senarai ganda terkait, kami juga boleh bergerak ke belakang. 225 00:11:40,300 --> 00:11:44,810 Oleh itu, kita bukan sahaja yang jumlah yang kita mahu untuk menyimpan, 226 00:11:44,810 --> 00:11:50,110 kita ada di mana ia menunjuk ke depan dan di mana kita telah datang. 227 00:11:50,110 --> 00:11:52,865 Jadi ini membolehkan beberapa penyusuran lebih baik. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Nod Jadi ganda terkait, hampir sama, bukan? 230 00:12:01,240 --> 00:12:05,000 Satu-satunya perbezaan adalah sekarang kita mempunyai depan dan sebelumnya. 231 00:12:05,000 --> 00:12:06,235 Ini satu-satunya perbezaan. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Jadi jika kita prepend atau kita append-- tidak mempunyai apa-apa kod untuk ini sehingga di sini- 234 00:12:14,790 --> 00:12:17,830 tetapi jika anda adalah untuk mencuba dan masukkan, apa yang penting 235 00:12:17,830 --> 00:12:19,980 adalah anda perlu membuat pasti anda sedang memberikan 236 00:12:19,980 --> 00:12:23,360 kedua-dua sebelumnya dan anda penunjuk berikutnya dengan betul. 237 00:12:23,360 --> 00:12:29,010 Jadi dalam kes ini, anda akan bukan sahaja memulakan depan, 238 00:12:29,010 --> 00:12:31,820 anda memulakan sebelumnya. 239 00:12:31,820 --> 00:12:36,960 Jika kita berada di kepala senarai, kita bukan sahaja akan membuat kepala sama baru, 240 00:12:36,960 --> 00:12:41,750 tetapi harus sebelumnya baru kami menunjuk ke kepala, kan? 241 00:12:41,750 --> 00:12:43,380 >> Itulah satu-satunya perbezaan. 242 00:12:43,380 --> 00:12:47,200 Dan jika anda mahu lebih banyak latihan dengan ini dengan daftar terkait, dengan memasukkan, 243 00:12:47,200 --> 00:12:49,900 dengan memotong, dengan memasukkan ke dalam senarai yang pelbagai, 244 00:12:49,900 --> 00:12:52,670 sila lihat study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Ada sekumpulan latihan besar. 246 00:12:54,870 --> 00:12:55,870 Saya sangat mengesyorkan mereka. 247 00:12:55,870 --> 00:12:59,210 Saya berharap kami mempunyai masa untuk pergi melalui mereka tapi ada banyak struktur data 248 00:12:59,210 --> 00:13:01,530 untuk mendapatkan melalui. 249 00:13:01,530 --> 00:13:02,650 >> OK, jadi jadual hash. 250 00:13:02,650 --> 00:13:07,070 Ini mungkin adalah yang paling sedikit berguna untuk anda Serangga 251 00:13:07,070 --> 00:13:11,090 di sini kerana anda akan berada melaksanakan salah satu dari ini, atau cuba. 252 00:13:11,090 --> 00:13:12,200 Saya sangat suka jadual hash. 253 00:13:12,200 --> 00:13:13,110 Mereka cukup sejuk. 254 00:13:13,110 --> 00:13:17,080 >> Jadi, pada asasnya apa yang berlaku adalah jadual hash 255 00:13:17,080 --> 00:13:22,050 adalah ketika kita benar-benar perlu cepat penyisipan, penghapusan, dan pencarian. 256 00:13:22,050 --> 00:13:25,010 Mereka adalah perkara-perkara yang kami keutamaan dalam jadual hash. 257 00:13:25,010 --> 00:13:29,500 Mereka boleh mendapatkan cukup besar, tetapi seperti yang kita akan melihat dengan mencoba, 258 00:13:29,500 --> 00:13:33,040 ada perkara-perkara yang jauh lebih besar. 259 00:13:33,040 --> 00:13:38,330 >> Tapi pada dasarnya, semua hash meja adalah fungsi hash 260 00:13:38,330 --> 00:13:47,215 yang memberitahu anda yang ember untuk menempatkan setiap data anda, setiap satu daripada unsur-unsur anda di. 261 00:13:47,215 --> 00:13:51,140 Cara mudah untuk memikirkan jadual hash adalah bahawa ia hanya baldi perkara, 262 00:13:51,140 --> 00:13:51,770 kan? 263 00:13:51,770 --> 00:13:59,720 Oleh itu, apabila anda memilah perkara oleh seperti huruf pertama dari nama mereka, 264 00:13:59,720 --> 00:14:01,820 itu semacam seperti meja hash. 265 00:14:01,820 --> 00:14:06,180 >> Jadi jika saya kepada kumpulan kalian adalah ke dalam kumpulan sesiapa nama yang bermula 266 00:14:06,180 --> 00:14:11,670 dengan A di sini, atau siapa pun yang hari jadi adalah pada bulan Januari, Februari, Mac, 267 00:14:11,670 --> 00:14:15,220 apa sahaja, yang berkesan mewujudkan carta hash. 268 00:14:15,220 --> 00:14:18,120 Ia hanya menciptakan baldi yang anda menyusun unsur-unsur anda ke 269 00:14:18,120 --> 00:14:19,520 supaya anda boleh mencari mereka lebih mudah. 270 00:14:19,520 --> 00:14:22,300 Jadi cara ini apabila saya perlu untuk mencari salah seorang dari kamu, 271 00:14:22,300 --> 00:14:24,680 Saya tidak mempunyai untuk mencari melalui setiap nama anda. 272 00:14:24,680 --> 00:14:29,490 Saya boleh menjadi seperti, oh, saya tahu bahawa Ulang tahun Danielle adalah dalam- 273 00:14:29,490 --> 00:14:30,240 PENONTON: --April. 274 00:14:30,240 --> 00:14:30,948 SPEAKER 1: April. 275 00:14:30,948 --> 00:14:33,120 Jadi saya melihat pada bulan April saya baldi, dan dengan sedikit keberuntungan, 276 00:14:33,120 --> 00:14:38,270 dia akan menjadi satu-satunya di sana dan masa saya adalah berterusan dalam hal ini, 277 00:14:38,270 --> 00:14:41,230 sedangkan jika saya harus melihat melalui sejumlah besar orang, 278 00:14:41,230 --> 00:14:43,090 ia akan mengambil masa lebih lama. 279 00:14:43,090 --> 00:14:45,830 Jadi jadual hash adalah benar-benar hanya baldi. 280 00:14:45,830 --> 00:14:48,630 Cara mudah untuk berfikir dari mereka. 281 00:14:48,630 --> 00:14:52,930 >> Jadi satu perkara yang sangat penting tentang jadual hash adalah fungsi hash. 282 00:14:52,930 --> 00:14:58,140 Jadi perkara yang saya hanya berbicara tentang, seperti surat pertama anda dari nama pertama anda 283 00:14:58,140 --> 00:15:01,450 atau bulan hari lahir anda, ini adalah idea-idea yang 284 00:15:01,450 --> 00:15:03,070 benar-benar berkorelasi dengan fungsi hash. 285 00:15:03,070 --> 00:15:08,900 Ia hanya satu cara untuk membuat keputusan yang bucket anda elemen sedang masuk ke dalam, OK? 286 00:15:08,900 --> 00:15:14,850 Jadi untuk Serangga ini, anda boleh melihat ke atas cukup banyak apa-apa fungsi hash yang anda mahu. 287 00:15:14,850 --> 00:15:16,030 >> Tidak perlu anda sendiri. 288 00:15:16,030 --> 00:15:21,140 Ada beberapa yang benar-benar sejuk keluar sana yang melakukan segala macam matematik gila. 289 00:15:21,140 --> 00:15:25,170 Dan jika anda mahu untuk membuat anda pemeriksa ejaan super cepat, 290 00:15:25,170 --> 00:15:27,620 Saya pasti akan melihat ke dalam salah satu dari mereka. 291 00:15:27,620 --> 00:15:32,390 >> Tetapi ada juga yang yang sederhana, seperti menghitung 292 00:15:32,390 --> 00:15:39,010 jumlah dari kata-kata, seperti setiap huruf mempunyai nombor. 293 00:15:39,010 --> 00:15:39,940 Mengira jumlah. 294 00:15:39,940 --> 00:15:42,230 Yang menentukan baldi. 295 00:15:42,230 --> 00:15:45,430 Mereka juga mempunyai orang-orang yang mudah yang hanya seperti semua A di sini, 296 00:15:45,430 --> 00:15:47,050 semua B yang ada di sini. 297 00:15:47,050 --> 00:15:48,920 Mana-mana satu dari mereka. 298 00:15:48,920 --> 00:15:55,770 >> Pada asasnya, ia hanya memberitahu anda yang indeks array elemen anda harus masuk ke dalam. 299 00:15:55,770 --> 00:15:58,690 Hanya memutuskan bucket-- yang itu semua fungsi hash. 300 00:15:58,690 --> 00:16:04,180 Jadi di sini kita mempunyai sebuah contoh yang hanya huruf pertama dari rentetan 301 00:16:04,180 --> 00:16:05,900 itu, saya baru bercakap tentang. 302 00:16:05,900 --> 00:16:11,900 >> Jadi, anda mempunyai beberapa hash itu hanya Huruf pertama tolak tali anda A, 303 00:16:11,900 --> 00:16:16,090 yang akan memberikan anda beberapa nombor di antara 0 dan 25. 304 00:16:16,090 --> 00:16:20,790 Dan apa yang anda mahu lakukan adalah memastikan bahawa ini merupakan 305 00:16:20,790 --> 00:16:24,110 saiz hash Anda table-- berapa banyak baldi ada. 306 00:16:24,110 --> 00:16:25,860 Dengan banyak syarikat- fungsi hash, mereka 307 00:16:25,860 --> 00:16:31,630 akan kembali nilai-nilai yang mungkin jauh di atas bilangan baldi 308 00:16:31,630 --> 00:16:33,610 Anda benar-benar mempunyai dalam jadual hash anda, 309 00:16:33,610 --> 00:16:37,240 jadi anda perlu untuk membuat yakin dan mod oleh mereka. 310 00:16:37,240 --> 00:16:42,190 Jika tidak, ia akan berkata, oh, itu harus dalam baldi 5,000 311 00:16:42,190 --> 00:16:46,040 tetapi anda hanya mempunyai 30 baldi dalam jadual hash anda. 312 00:16:46,040 --> 00:16:49,360 Dan sudah tentu, kita semua tahu itu akan menghasilkan beberapa kesalahan gila. 313 00:16:49,360 --> 00:16:52,870 Jadi pastikan untuk mod oleh ukuran meja hash anda. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Sejuk. 316 00:16:58,930 --> 00:17:00,506 Jadi perlanggaran. 317 00:17:00,506 --> 00:17:02,620 Apakah semua orang yang baik setakat ini? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> PENONTON: Mengapa ia kembali apa-apa jumlah yang besar-besaran? 320 00:17:05,900 --> 00:17:09,210 >> SPEAKER 1: Bergantung kepada algoritma bahawa fungsi hash anda menggunakan. 321 00:17:09,210 --> 00:17:12,270 Beberapa dari mereka akan melakukan pendaraban gila. 322 00:17:12,270 --> 00:17:16,270 Dan itu semua tentang mendapatkan yang pemerataan, 323 00:17:16,270 --> 00:17:18,490 sehingga mereka benar-benar melakukan beberapa perkara gila kadang-kadang. 324 00:17:18,490 --> 00:17:20,960 Itu sahaja. 325 00:17:20,960 --> 00:17:22,140 Apa-apa lagi? 326 00:17:22,140 --> 00:17:22,829 OK. 327 00:17:22,829 --> 00:17:24,480 >> Jadi perlanggaran. 328 00:17:24,480 --> 00:17:29,270 Pada dasarnya, seperti yang saya katakan sebelum ini, dalam kes senario yang terbaik, 329 00:17:29,270 --> 00:17:32,040 setiap baldi saya melihat ke dalam adalah akan mempunyai satu perkara, 330 00:17:32,040 --> 00:17:34,160 jadi saya tidak perlu melihat sama sekali, bukan? 331 00:17:34,160 --> 00:17:37,040 Saya sama ada tahu itu ada atau itu tidak, dan itulah yang kita benar-benar mahu. 332 00:17:37,040 --> 00:17:43,960 Tetapi jika kita mempunyai puluhan ribu titik data dan kurang daripada jumlah itu 333 00:17:43,960 --> 00:17:48,700 dari baldi, kita akan mempunyai tabrakan di mana sesuatu yang akhirnya 334 00:17:48,700 --> 00:17:54,210 akan perlu berakhir di ember yang sudah memiliki unsur. 335 00:17:54,210 --> 00:17:57,390 >> Jadi pertanyaannya adalah, apa yang yang kita lakukan dalam hal ini? 336 00:17:57,390 --> 00:17:58,480 Apa yang kita lakukan? 337 00:17:58,480 --> 00:17:59,300 Kita sudah ada sesuatu di sana? 338 00:17:59,300 --> 00:18:00,060 Adakah kita hanya membuang ia keluar? 339 00:18:00,060 --> 00:18:00,700 >> Tidak. 340 00:18:00,700 --> 00:18:01,980 Kita perlu menjaga kedua-dua mereka. 341 00:18:01,980 --> 00:18:06,400 Jadi cara yang kita biasanya melakukan itu adalah apa? 342 00:18:06,400 --> 00:18:08,400 Bagaimana struktur data kita hanya bercakap tentang? 343 00:18:08,400 --> 00:18:09,316 PENONTON: Senarai Berkaitan. 344 00:18:09,316 --> 00:18:10,500 SPEAKER 1: Daftar terkait. 345 00:18:10,500 --> 00:18:16,640 Jadi sekarang, bukan masing-masing baldi hanya mempunyai satu elemen, 346 00:18:16,640 --> 00:18:24,020 itu akan mengandungi senarai berpaut dari unsur-unsur yang telah dicincang ke dalamnya. 347 00:18:24,020 --> 00:18:27,588 OK, adakah semua orang jenis mendapat idea itu? 348 00:18:27,588 --> 00:18:30,546 Kerana kita tidak boleh mempunyai array kerana kita tidak tahu berapa banyak perkara 349 00:18:30,546 --> 00:18:31,730 yang akan berada di sana. 350 00:18:31,730 --> 00:18:36,540 Daftar terkait membolehkan kita untuk mempunyai hanya jumlah yang tepat bahawa 351 00:18:36,540 --> 00:18:38,465 adalah hash ke dalam baldi itu, kan? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Jadi linear menyelidik adalah pada dasarnya idea-- ini 354 00:18:50,500 --> 00:18:52,300 itu salah satu cara untuk berurusan dengan perlanggaran. 355 00:18:52,300 --> 00:18:58,010 Apa yang boleh anda lakukan adalah jika, dalam hal ini kes, berry hash ke 1 356 00:18:58,010 --> 00:19:01,130 dan kita sudah mempunyai sesuatu di sana, anda hanya 357 00:19:01,130 --> 00:19:04,840 terus ke bawah sehingga anda mencari slot kosong. 358 00:19:04,840 --> 00:19:06,370 Itu salah satu cara untuk menanganinya. 359 00:19:06,370 --> 00:19:09,020 Cara lain untuk menangani itu dengan apa yang kita hanya 360 00:19:09,020 --> 00:19:12,280 called-- yang terkait senarai dipanggil rantaian. 361 00:19:12,280 --> 00:19:20,510 >> Jadi idea ini bekerja jika jadual hash anda, anda berfikir 362 00:19:20,510 --> 00:19:24,150 jauh lebih besar daripada data anda menetapkan atau jika anda 363 00:19:24,150 --> 00:19:28,870 ingin mencuba dan mengurangkan chaining sehingga ia benar-benar diperlukan. 364 00:19:28,870 --> 00:19:34,050 Jadi satu perkara yang linear menyelesaikan sesuatu jelas berarti 365 00:19:34,050 --> 00:19:37,290 bahawa fungsi hash Anda tidak cukup berguna 366 00:19:37,290 --> 00:19:42,200 kerana anda akan berakhir dengan menggunakan fungsi hash anda, sampai ke titik, 367 00:19:42,200 --> 00:19:46,400 Anda linier menyiasat ke beberapa tempat yang disediakan. 368 00:19:46,400 --> 00:19:49,670 Tapi sekarang, sudah tentu, apa-apa lain yang berakhir di sana, 369 00:19:49,670 --> 00:19:52,050 Anda akan perlu mencari lebih jauh. 370 00:19:52,050 --> 00:19:55,650 >> Dan ada banyak lagi perbelanjaan carian yang 371 00:19:55,650 --> 00:19:59,820 masuk ke dalam memasukkan unsur dalam jadual hash anda sekarang, kan? 372 00:19:59,820 --> 00:20:05,640 Dan sekarang ketika anda pergi dan cuba dan mencari buah lagi, anda akan hash itu, 373 00:20:05,640 --> 00:20:07,742 dan ia akan berkata, oh, lihat dalam baldi 1, 374 00:20:07,742 --> 00:20:09,700 dan ia tidak akan menjadi di ember 1, sehingga anda 375 00:20:09,700 --> 00:20:11,970 akan harus melintasi melalui sisa ini. 376 00:20:11,970 --> 00:20:17,720 Jadi kadang-kadang berguna, tetapi dalam kebanyakan kes, 377 00:20:17,720 --> 00:20:22,660 kita akan mengatakan bahawa chaining adalah apa yang anda mahu lakukan. 378 00:20:22,660 --> 00:20:25,520 >> Oleh itu, kita bercakap tentang perkara ini sebelum ini. 379 00:20:25,520 --> 00:20:27,812 Saya mendapat lebih awal sedikit dari diri saya. 380 00:20:27,812 --> 00:20:33,560 Tetapi chaining pada dasarnya yang setiap kotak dalam jadual hash Anda 381 00:20:33,560 --> 00:20:36,120 hanya daftar link. 382 00:20:36,120 --> 00:20:39,660 >> Jadi cara yang lain, atau lebih teknikal cara, untuk memikirkan jadual hash 383 00:20:39,660 --> 00:20:44,490 adalah bahawa ia hanya array yang terhubung daftar, yang 384 00:20:44,490 --> 00:20:49,330 bila anda menulis kamus anda dan anda cuba untuk memuat itu, 385 00:20:49,330 --> 00:20:52,070 memikirkan hal itu sebagai array daftar terkait 386 00:20:52,070 --> 00:20:54,390 akan membuat ia lebih mudah bagi anda untuk memulakan. 387 00:20:54,390 --> 00:20:57,680 >> PENONTON: Jadi jadual hash mempunyai saiz yang telah ditetapkan, 388 00:20:57,680 --> 00:20:58,980 seperti [terdengar] dari baldi? 389 00:20:58,980 --> 00:20:59,220 >> SPEAKER 1: Benar. 390 00:20:59,220 --> 00:21:01,655 Oleh itu, ia mempunyai beberapa set kotak yang Anda determine-- 391 00:21:01,655 --> 00:21:03,530 yang kalian harus berasa bebas untuk bermain dengan. 392 00:21:03,530 --> 00:21:05,269 Ia boleh menjadi cukup sejuk untuk melihat apa yang berlaku 393 00:21:05,269 --> 00:21:06,810 apabila anda menukar nombor anda dari baldi. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Tapi ya, ia mempunyai mengatur jumlah baldi. 396 00:21:11,510 --> 00:21:15,360 Apa yang membolehkan anda untuk cocok sebagai banyak elemen yang anda perlukan 397 00:21:15,360 --> 00:21:19,350 adalah chaining berasingan di mana anda telah mengaitkan senarai dalam setiap kotak. 398 00:21:19,350 --> 00:21:22,850 Ini bermakna jadual hash Anda akan persis saiz 399 00:21:22,850 --> 00:21:25,440 yang anda perlukan untuk menjadi, bukan? 400 00:21:25,440 --> 00:21:27,358 Itu titik seluruh daftar terkait. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Sejuk. 403 00:21:32,480 --> 00:21:38,780 >> Jadi setiap orang ada OK? 404 00:21:38,780 --> 00:21:39,801 Baik. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 Apa yang terjadi? 407 00:21:41,860 --> 00:21:42,960 Benar-benar sekarang. 408 00:21:42,960 --> 00:21:45,250 Meneka seseorang membunuh saya. 409 00:21:45,250 --> 00:21:52,060 >> OK kita akan masuk ke mencoba, yang sedikit gila. 410 00:21:52,060 --> 00:21:53,140 Saya suka jadual hash. 411 00:21:53,140 --> 00:21:54,460 Saya rasa mereka benar-benar sejuk. 412 00:21:54,460 --> 00:21:56,710 Cuba sejuk juga. 413 00:21:56,710 --> 00:21:59,590 >> Jadi tidak ada yang ingat apa yang cuba adalah? 414 00:21:59,590 --> 00:22:01,740 Anda seharusnya pergi lebih ia secara ringkas dalam kuliah? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Adakah anda ingat jenis bagaimana ia berfungsi? 417 00:22:06,377 --> 00:22:08,460 PENONTON: Saya hanya mengangguk-angguk bahwa kita pergi lebih dari itu. 418 00:22:08,460 --> 00:22:09,626 SPEAKER 1: Kami pergi lebih dari itu. 419 00:22:09,626 --> 00:22:13,100 OK, kita benar-benar akan pergi lebih sekarang adalah apa yang kita katakan. 420 00:22:13,100 --> 00:22:14,860 >> PENONTON: Itu untuk pohon pengambilan. 421 00:22:14,860 --> 00:22:15,280 >> SPEAKER 1: Ya. 422 00:22:15,280 --> 00:22:16,196 Ini adalah pokok pengambilan. 423 00:22:16,196 --> 00:22:16,960 Awesome. 424 00:22:16,960 --> 00:22:23,610 Jadi, satu perkara yang perlu diperhatikan di sini adalah bahawa kita sedang melihat karakter individu 425 00:22:23,610 --> 00:22:24,480 di sini, kan? 426 00:22:24,480 --> 00:22:29,710 >> Jadi sebelum dengan fungsi hash kami, kami cari akan kata-kata secara keseluruhan, 427 00:22:29,710 --> 00:22:32,270 dan sekarang kami sedang mencari lebih banyak pada watak-watak, bukan? 428 00:22:32,270 --> 00:22:38,380 Jadi kita mempunyai Maxwell di sini dan Mendel. 429 00:22:38,380 --> 00:22:47,840 Jadi, pada asasnya sebuah try-- satu cara untuk berfikir tentang ini adalah bahawa setiap peringkat di sini 430 00:22:47,840 --> 00:22:49,000 adalah array surat. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Jadi, ini adalah nod root anda di sini, kan? 433 00:22:55,790 --> 00:23:01,980 Ini semua watak-watak dari abjad untuk permulaan setiap kata. 434 00:23:01,980 --> 00:23:06,480 >> Dan apa yang anda mahu lakukan adalah berkata, OK, kita mempunyai beberapa kata M. 435 00:23:06,480 --> 00:23:10,590 Kita akan mencari Maxwell, jadi kita pergi ke M. Dan M mata kepada keseluruhan 436 00:23:10,590 --> 00:23:14,800 lain lokasi di mana setiap kata, selama ada 437 00:23:14,800 --> 00:23:17,044 adalah kata yang mempunyai A sebagai surat yang kedua, 438 00:23:17,044 --> 00:23:19,460 selagi ada perkataan yang mempunyai B seperti surat kedua, 439 00:23:19,460 --> 00:23:24,630 ia akan mempunyai penunjuk pergi ke beberapa pelbagai berikutnya. 440 00:23:24,630 --> 00:23:29,290 >> Mungkin ada yang tidak kata yang MP sesuatu, 441 00:23:29,290 --> 00:23:32,980 jadi pada kedudukan P dalam ini array, ia hanya akan menjadi NULL. 442 00:23:32,980 --> 00:23:38,840 Ia akan berkata, OK, tidak ada kata yang telah M diikuti oleh P, oke? 443 00:23:38,840 --> 00:23:43,100 Jadi jika kita berfikir tentang hal itu, masing-masing salah satu perkara-perkara ini lebih kecil 444 00:23:43,100 --> 00:23:47,990 sebenarnya salah satu dari ini array besar dari A sampai Z. 445 00:23:47,990 --> 00:23:55,064 Jadi apa yang mungkin menjadi salah satu perkara yang yang jenis kelemahan dari mencuba? 446 00:23:55,064 --> 00:23:56,500 >> PENONTON: Banyak memori. 447 00:23:56,500 --> 00:23:59,940 >> SPEAKER 1: Ini satu tan memori, kan? 448 00:23:59,940 --> 00:24:08,750 Masing-masing dari blok ini di sini mewakili 26 ruang, 26 elemen array. 449 00:24:08,750 --> 00:24:13,680 Jadi cuba mendapatkan ruang sangat berat. 450 00:24:13,680 --> 00:24:17,100 >> Tetapi mereka sangat cepat. 451 00:24:17,100 --> 00:24:22,540 Jadi sangat cepat tetapi benar-benar tidak cekap ruang. 452 00:24:22,540 --> 00:24:24,810 Jenis harus mencari yang mana satu anda mahu. 453 00:24:24,810 --> 00:24:29,470 Ini adalah benar-benar sejuk untuk Serangga anda, tetapi mereka mengambil banyak memori, 454 00:24:29,470 --> 00:24:30,290 jadi anda trade off. 455 00:24:30,290 --> 00:24:31,480 Ya? 456 00:24:31,480 --> 00:24:34,300 >> PENONTON: Adakah mungkin untuk menubuhkan mencuba dan kemudian 457 00:24:34,300 --> 00:24:37,967 apabila anda mempunyai semua data di dalamnya yang anda need-- 458 00:24:37,967 --> 00:24:39,550 Saya tidak tahu apakah yang akan masuk akal. 459 00:24:39,550 --> 00:24:42,200 Saya telah menyingkirkan semua Aksara NULL, tetapi kemudian 460 00:24:42,200 --> 00:24:42,910 Anda tidak akan dapat indeks them-- 461 00:24:42,910 --> 00:24:43,275 >> SPEAKER 1: Anda masih memerlukannya. 462 00:24:43,275 --> 00:24:44,854 >> PENONTON: - cara yang sama setiap kali. 463 00:24:44,854 --> 00:24:45,520 SPEAKER 1: Ya. 464 00:24:45,520 --> 00:24:50,460 Anda memerlukan karakter NULL untuk membiarkan anda tahu jika tidak ada satu perkataan di sana. 465 00:24:50,460 --> 00:24:52,040 Ben adakah anda mempunyai sesuatu yang anda mahu? 466 00:24:52,040 --> 00:24:52,540 OK. 467 00:24:52,540 --> 00:24:54,581 Baiklah, jadi kita akan untuk pergi sedikit lebih 468 00:24:54,581 --> 00:24:58,920 ke detail teknikal di belakang yang berusaha dan bekerja melalui contoh. 469 00:24:58,920 --> 00:25:01,490 >> OK, jadi ini adalah perkara yang sama. 470 00:25:01,490 --> 00:25:06,290 Manakala dalam senarai yang disambungkan, utama kami jenis daripada- apa perkataan yang saya mahu? - 471 00:25:06,290 --> 00:25:08,350 seperti membina blok adalah nod. 472 00:25:08,350 --> 00:25:12,280 Di cuba, kami juga mempunyai nod, tetapi ia ditakrifkan berbeza. 473 00:25:12,280 --> 00:25:17,000 >> Oleh itu, kita mempunyai beberapa bool yang mewakili sama ada perkataan yang benar-benar 474 00:25:17,000 --> 00:25:23,530 wujud di lokasi ini, dan kemudian kami mempunyai pelbagai sini-atau lebih tepat, 475 00:25:23,530 --> 00:25:27,840 ini adalah satu penunjuk kepada array 27 aksara. 476 00:25:27,840 --> 00:25:33,339 Dan ini adalah untuk, dalam hal ini, ini 27-- saya pasti kamu semua adalah seperti, tunggu, 477 00:25:33,339 --> 00:25:34,880 terdapat 26 huruf dalam abjad. 478 00:25:34,880 --> 00:25:36,010 Mengapa kita mempunyai 27? 479 00:25:36,010 --> 00:25:37,870 >> Jadi bergantung kepada cara anda melaksanakan ini, 480 00:25:37,870 --> 00:25:43,240 ini adalah dari Serangga yang dibenarkan untuk apostrof. 481 00:25:43,240 --> 00:25:46,010 Jadi itulah sebabnya satu tambahan. 482 00:25:46,010 --> 00:25:50,500 Anda juga akan mempunyai di beberapa kes terminator nol 483 00:25:50,500 --> 00:25:53,230 dimasukkan sebagai salah satu daripada aksara yang ia dibenarkan untuk menjadi, 484 00:25:53,230 --> 00:25:56,120 dan itulah bagaimana mereka memeriksa untuk melihat apakah itu akhir perkataan. 485 00:25:56,120 --> 00:26:01,340 Jika anda berminat, lihat Video Kevin pada study.cs50, 486 00:26:01,340 --> 00:26:04,790 dan juga Wikipedia mempunyai beberapa sumber yang baik di sana. 487 00:26:04,790 --> 00:26:09,000 >> Tetapi kita akan pergi melalui hanya jenis bagaimana anda boleh bekerja melalui cuba 488 00:26:09,000 --> 00:26:11,010 jika anda diberi satu. 489 00:26:11,010 --> 00:26:16,230 Jadi kita mempunyai satu super sederhana di sini bahawa mempunyai perkataan "kelawar" dan "zoom" di dalamnya. 490 00:26:16,230 --> 00:26:18,920 Dan seperti yang kita lihat di sini, ruang ini kecil di sini 491 00:26:18,920 --> 00:26:22,560 mewakili bool kami bahawa berkata, ya, ini adalah satu perkataan. 492 00:26:22,560 --> 00:26:27,060 Dan kemudian ini mempunyai kami tatasusunan aksara, kan? 493 00:26:27,060 --> 00:26:33,480 >> Jadi kita akan pergi melalui mencari "kelawar" dalam cuba ini. 494 00:26:33,480 --> 00:26:38,340 Jadi bermula di bahagian atas, bukan? 495 00:26:38,340 --> 00:26:46,290 Dan kita tahu bahawa b sepadan dengan Indeks kedua, elemen kedua 496 00:26:46,290 --> 00:26:47,840 dalam array ini, kerana a dan b. 497 00:26:47,840 --> 00:26:51,340 Jadi kira-kira yang kedua. 498 00:26:51,340 --> 00:26:58,820 >> Dan ia berkata, OK, sejuk, ikuti itu ke dalam array akan datang, kerana jika kita ingat, 499 00:26:58,820 --> 00:27:02,160 ia tidak bahawa masing-masing sebenarnya mengandungi elemen. 500 00:27:02,160 --> 00:27:07,110 Masing-masing dari array ini mengandungi pointer, bukan? 501 00:27:07,110 --> 00:27:10,030 Ia merupakan satu perbezaan penting untuk membuat. 502 00:27:10,030 --> 00:27:13,450 >> Saya tahu ini akan adalah-- mencoba adalah benar-benar sukar untuk mendapatkan pada kali pertama, 503 00:27:13,450 --> 00:27:15,241 jadi walaupun ini adalah kedua atau ketiga kalinya 504 00:27:15,241 --> 00:27:18,370 dan ia masih jenis dari tampak sukar, 505 00:27:18,370 --> 00:27:21,199 Saya berjanji jika anda pergi menonton pendek lagi besok, 506 00:27:21,199 --> 00:27:22,740 ia mungkin akan masuk akal lebih banyak. 507 00:27:22,740 --> 00:27:23,890 Ia mengambil banyak untuk dihadam. 508 00:27:23,890 --> 00:27:27,800 Saya masih kadang-kadang saya seperti, tunggu, apa yang cuba? 509 00:27:27,800 --> 00:27:29,080 Bagaimana saya menggunakan ini? 510 00:27:29,080 --> 00:27:33,880 >> Oleh itu, kita telah b dalam kes ini, yang merupakan indeks kedua kami. 511 00:27:33,880 --> 00:27:40,240 Jika kita mempunyai, katakan, atau c d atau apa-apa surat yang lain, 512 00:27:40,240 --> 00:27:45,810 kita perlu peta yang kembali kepada indeks dari array kita bahawa yang sepadan dengan. 513 00:27:45,810 --> 00:27:56,930 Oleh itu, kita akan mengambil seperti rchar dan kami hanya tolak dari sebuah peta itu ke 0-25. 514 00:27:56,930 --> 00:27:58,728 Semua orang yang baik bagaimana kita peta aksara kita? 515 00:27:58,728 --> 00:28:00,440 OK. 516 00:28:00,440 --> 00:28:05,980 >> Jadi kita pergi ke yang kedua dan kita melihat bahawa, ya, ia tidak adalah dengan NULL. 517 00:28:05,980 --> 00:28:07,780 Kita boleh bergerak ke array ini akan datang. 518 00:28:07,780 --> 00:28:12,300 Jadi kita pergi ke array ini seterusnya di sini. 519 00:28:12,300 --> 00:28:15,500 >> Dan kita berkata, OK, sekarang kita perlu untuk melihat apakah yang ada di sini. 520 00:28:15,500 --> 00:28:18,590 Apakah A batal atau tidak ia sebenarnya ke depan? 521 00:28:18,590 --> 00:28:21,880 Jadi yang benar-benar bergerak maju dalam array ini. 522 00:28:21,880 --> 00:28:24,570 Dan kita berkata, OK, t ialah surat terakhir kami. 523 00:28:24,570 --> 00:28:27,580 Jadi kita pergi ke t di indeks. 524 00:28:27,580 --> 00:28:30,120 Dan kemudian kita bergerak ke hadapan kerana ada satu lagi. 525 00:28:30,120 --> 00:28:38,340 Dan salah satu ini mengatakan bahawa pada dasarnya, ya, ia mengatakan bahawa ada satu kata di sini- 526 00:28:38,340 --> 00:28:41,750 bahawa jika anda mengikuti ini jalan, anda telah tiba 527 00:28:41,750 --> 00:28:43,210 di kata, yang kita tahu ialah "kelawar". 528 00:28:43,210 --> 00:28:43,800 Ya? 529 00:28:43,800 --> 00:28:46,770 >> PENONTON: Apakah standard untuk memiliki sebagai indeks 0 dan kemudian memiliki semacam pada 1 530 00:28:46,770 --> 00:28:47,660 atau mempunyai di akhir? 531 00:28:47,660 --> 00:28:48,243 >> SPEAKER 1: No. 532 00:28:48,243 --> 00:28:55,360 Oleh itu, jika kita melihat kembali pada kami deklarasi di sini, itu bool, 533 00:28:55,360 --> 00:28:59,490 jadi ia adalah elemen tersendiri dalam nod anda. 534 00:28:59,490 --> 00:29:03,331 Jadi ia bukan sebahagian daripada array. 535 00:29:03,331 --> 00:29:03,830 Sejuk. 536 00:29:03,830 --> 00:29:08,370 Oleh itu, apabila kita menyelesaikan kata kami dan kami di array ini, apa yang kita mahu lakukan 537 00:29:08,370 --> 00:29:12,807 adalah melakukan cek ialah perkataan. 538 00:29:12,807 --> 00:29:14,390 Dan dalam kes ini, ia akan kembali ya. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Maka pada masa yang sama, kita tahu bahawa "kebun binatang" - kita kenal sebagai manusia yang "zoo" adalah satu perkataan, 541 00:29:24,090 --> 00:29:24,820 kan? 542 00:29:24,820 --> 00:29:28,990 Tetapi cuba di sini akan berkata, tidak, tidak. 543 00:29:28,990 --> 00:29:33,980 Dan ia akan mengatakan bahawa kerana kita belum ditetapkan sebagai kata di sini. 544 00:29:33,980 --> 00:29:40,440 Walaupun kita dapat melintasi melalui array ini, 545 00:29:40,440 --> 00:29:43,890 cuba ini akan mengatakan bahawa, tidak, kebun binatang tidak ada di dalam kamus anda 546 00:29:43,890 --> 00:29:47,070 kerana kita tidak mempunyai ditetapkan seperti itu. 547 00:29:47,070 --> 00:29:52,870 >> Jadi salah satu cara untuk melakukan bahawa- oh, maaf, yang satu ini. 548 00:29:52,870 --> 00:29:59,450 Jadi dalam hal ini, "zoo" tidak kata, tetapi ia adalah dalam cuba kami. 549 00:29:59,450 --> 00:30:05,690 Tetapi dalam satu ini, mengatakan bahawa kita mahu memperkenalkan perkataan "mandi," apa yang berlaku 550 00:30:05,690 --> 00:30:08,260 adalah kita mengikuti through-- b, a, t. 551 00:30:08,260 --> 00:30:11,820 Kami dalam array ini, dan kita pergi untuk mencari h. 552 00:30:11,820 --> 00:30:15,220 >> Dalam hal ini, apabila kita melihat penunjuk di h, 553 00:30:15,220 --> 00:30:17,890 itu menunjuk ke NULL, OK? 554 00:30:17,890 --> 00:30:20,780 Jadi kecuali jika jelas menunjuk ke array lain, 555 00:30:20,780 --> 00:30:25,000 anda menganggap bahawa semua pointer dalam array ini menunjuk ke null. 556 00:30:25,000 --> 00:30:28,270 Jadi dalam hal ini, h menunjuk null itu kita tidak boleh berbuat apa-apa, 557 00:30:28,270 --> 00:30:31,540 jadi ia juga akan kembali palsu, "mandi" tidak ada di sini. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Jadi sekarang kita benar-benar akan pergi melalui 560 00:30:35,810 --> 00:30:39,790 bagaimana kita benar-benar mengatakan bahawa "kebun binatang" adalah dalam cuba kami. 561 00:30:39,790 --> 00:30:42,920 Bagaimana kita memasukkan "zoo" ke dalam cuba kita? 562 00:30:42,920 --> 00:30:47,810 Jadi dengan cara yang sama yang kita mulai dengan linked list kami, kami mulai pada akar. 563 00:30:47,810 --> 00:30:50,600 Jika ragu, bermula akar dari perkara-perkara ini. 564 00:30:50,600 --> 00:30:53,330 >> Dan kita akan berkata, OK, z. 565 00:30:53,330 --> 00:30:55,650 z ada dalam hal ini, dan itu. 566 00:30:55,650 --> 00:30:58,370 Jadi, kau pindah ke array seterusnya, OK? 567 00:30:58,370 --> 00:31:01,482 Dan kemudian kepada orang yang akan datang, kita kata, OK, adakah o wujud? 568 00:31:01,482 --> 00:31:03,000 Tentu saja. 569 00:31:03,000 --> 00:31:04,330 Ini sekali lagi. 570 00:31:04,330 --> 00:31:08,670 >> Dan sebagainya yang berikutnya, kami telah berkata, OK, "zoo" sudah ada di sini. 571 00:31:08,670 --> 00:31:12,440 Apa yang kita perlu lakukan adalah membuat ini sama kepada benar, yang ada kata ada. 572 00:31:12,440 --> 00:31:15,260 Jika anda telah mengikuti semua sehingga sebelum saat itu, 573 00:31:15,260 --> 00:31:17,030 itu kata, jadi hanya set sama dengan itu. 574 00:31:17,030 --> 00:31:17,530 Ya? 575 00:31:17,530 --> 00:31:22,550 >> PENONTON: Jadi adakah itu bermakna "ba" adalah satu perkataan juga? 576 00:31:22,550 --> 00:31:24,120 >> SPEAKER 1: No. 577 00:31:24,120 --> 00:31:28,870 Jadi dalam hal ini, "ba" kita akan mendapatkan di sini, kita akan mengatakan ia adalah perkataan, 578 00:31:28,870 --> 00:31:31,590 dan itu akan tetap ada. 579 00:31:31,590 --> 00:31:32,822 OK? 580 00:31:32,822 --> 00:31:33,740 Mmhmm? 581 00:31:33,740 --> 00:31:36,360 >> PENONTON: Jadi sekali anda apakah itu kata dan anda menjawab ya, maka ia 582 00:31:36,360 --> 00:31:38,380 akan mengandungi pergi ke m? 583 00:31:38,380 --> 00:31:42,260 >> SPEAKER 1: Jadi ini ada hubungannya with-- Anda memuat ini. 584 00:31:42,260 --> 00:31:43,640 Anda mengatakan "zoo" adalah satu perkataan. 585 00:31:43,640 --> 00:31:47,020 Apabila anda pergi ke check-- seperti, katakan anda ingin mengatakan, 586 00:31:47,020 --> 00:31:49,400 maksud "zoo" wujud dalam kamus ini? 587 00:31:49,400 --> 00:31:54,200 Anda hanya akan mencari "kebun binatang," dan kemudian memeriksa untuk melihat sama ada ianya perkataan. 588 00:31:54,200 --> 00:31:57,291 Anda tidak akan pernah bergerak melalui m kerana itu bukan 589 00:31:57,291 --> 00:31:58,290 apa yang anda cari. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Jadi, jika kita benar-benar mahu menambah "mandi" ke cuba ini, 592 00:32:08,070 --> 00:32:11,390 kita akan melakukan perkara yang sama seperti yang kita lakukan dengan "zoo," 593 00:32:11,390 --> 00:32:15,380 kecuali kita akan melihat bahawa apabila kita cuba mendapatkan hingga h, ia tidak wujud. 594 00:32:15,380 --> 00:32:20,090 Jadi, anda boleh menganggap ini sebagai cuba untuk menambah nod baru ke dalam senarai yang disambungkan, 595 00:32:20,090 --> 00:32:27,210 Jadi, kita perlu untuk menambah satu lagi salah satu array ini, seperti begitu. 596 00:32:27,210 --> 00:32:35,670 Dan kemudian apa yang kita lakukan adalah kita hanya mengatur h elemen array ini menunjuk kepada ini. 597 00:32:35,670 --> 00:32:39,430 >> Dan kemudian apa yang kita ingin lakukan di sini? 598 00:32:39,430 --> 00:32:43,110 Tambah itu sama dengan benar kerana ia adalah satu perkataan. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Sejuk. 601 00:32:48,150 --> 00:32:48,700 Saya tahu. 602 00:32:48,700 --> 00:32:51,170 Cuba tidak adalah yang paling menarik. 603 00:32:51,170 --> 00:32:54,250 Percayalah, saya tahu. 604 00:32:54,250 --> 00:32:58,040 >> Jadi, satu perkara yang perlu sedar dengan mencoba, Saya berkata, mereka sangat cekap. 605 00:32:58,040 --> 00:33:00,080 Oleh itu, kita telah melihat mereka mengambil masa sehingga satu tan ruang. 606 00:33:00,080 --> 00:33:01,370 Mereka agak membingungkan. 607 00:33:01,370 --> 00:33:03,367 Jadi, mengapa kita pernah menggunakan ini? 608 00:33:03,367 --> 00:33:05,450 Kami menggunakan ini kerana mereka sangat cekap. 609 00:33:05,450 --> 00:33:08,130 >> Jadi, jika anda pernah melihat sehingga kata, anda hanya 610 00:33:08,130 --> 00:33:10,450 dibatasi oleh panjang kata. 611 00:33:10,450 --> 00:33:15,210 Jadi, jika anda sedang mencari perkataan yang panjang lima, 612 00:33:15,210 --> 00:33:20,940 Anda hanya pernah akan perlu membuat paling banyak lima perbandingan, OK? 613 00:33:20,940 --> 00:33:25,780 Sehingga membuatnya pada dasarnya yang tetap. 614 00:33:25,780 --> 00:33:29,150 Seperti penyisipan dan lookup pada dasarnya masa yang sama. 615 00:33:29,150 --> 00:33:33,750 >> Jadi jika anda pernah mendapatkan sesuatu dalam masa yang tetap, 616 00:33:33,750 --> 00:33:35,150 itu sebagai baik kerana mendapat. 617 00:33:35,150 --> 00:33:37,990 Anda tidak boleh mendapatkan lebih baik daripada pemalar masa untuk perkara-perkara ini. 618 00:33:37,990 --> 00:33:43,150 Jadi itu adalah salah satu daripada plus besar daripada cuba. 619 00:33:43,150 --> 00:33:46,780 >> Tetapi ia adalah banyak ruang. 620 00:33:46,780 --> 00:33:50,380 Jadi anda jenis perlu membuat keputusan apa yang lebih penting kepada anda. 621 00:33:50,380 --> 00:33:54,700 Dan pada komputer hari ini, ruang yang cuba mungkin mengambil masa sehingga 622 00:33:54,700 --> 00:33:57,740 mungkin tidak menjejaskan yang banyak, tetapi mungkin 623 00:33:57,740 --> 00:34:01,350 Anda sedang berhadapan dengan sesuatu yang yang mempunyai jauh, jauh lebih banyak hal, 624 00:34:01,350 --> 00:34:02,810 dan cuba hanya tidak masuk akal. 625 00:34:02,810 --> 00:34:03,000 Ya? 626 00:34:03,000 --> 00:34:05,610 >> PENONTON: Tunggu, jadi anda mempunyai 26 huruf dalam setiap satu daripadanya? 627 00:34:05,610 --> 00:34:07,440 >> SPEAKER 1: Mmhmm. 628 00:34:07,440 --> 00:34:08,570 Ya, anda mempunyai 26. 629 00:34:08,570 --> 00:34:16,984 Anda mempunyai beberapa adalah penanda kata dan kemudian anda mempunyai 26 petunjuk dalam setiap satu. 630 00:34:16,984 --> 00:34:17,775 Dan mereka point-- 631 00:34:17,775 --> 00:34:20,280 >> PENONTON: Dan setiap 26, adakah mereka masing-masing mempunyai 26? 632 00:34:20,280 --> 00:34:21,500 >> SPEAKER 1: Ya. 633 00:34:21,500 --> 00:34:27,460 Dan sebab itu, yang anda boleh lihat, ia mengembang cukup pesat. 634 00:34:27,460 --> 00:34:28,130 Baik. 635 00:34:28,130 --> 00:34:32,524 Jadi, kita akan masuk ke dalam pokok-pokok, yang Saya rasa seperti lebih mudah dan mungkin akan 636 00:34:32,524 --> 00:34:36,150 menjadi penangguhan hukuman kecil yang menyenangkan dari negara-sana. 637 00:34:36,150 --> 00:34:39,620 Jadi mudah-mudahan kebanyakan kamu telah melihat pohon sebelumnya. 638 00:34:39,620 --> 00:34:41,820 Tidak seperti cantik yang di luar, yang saya 639 00:34:41,820 --> 00:34:44,340 tidak tahu apakah ada orang keluar rumah baru-baru ini. 640 00:34:44,340 --> 00:34:49,230 Saya pergi memetik apel hujung minggu ini, dan oh ya ampun, itu indah. 641 00:34:49,230 --> 00:34:52,250 Saya tidak tahu daun boleh melihat yang cantik. 642 00:34:52,250 --> 00:34:53,610 >> Jadi, ini adalah hanya pokok, kan? 643 00:34:53,610 --> 00:34:56,790 Ia hanya beberapa nod, dan ia menunjuk ke sekumpulan nod lain. 644 00:34:56,790 --> 00:34:59,570 Seperti yang anda lihat di sini, ini adalah jenis tema yang berulang. 645 00:34:59,570 --> 00:35:03,720 Nod yang menunjuk ke nod adalah jenis intipati struktur data banyak. 646 00:35:03,720 --> 00:35:06,670 Ia hanya bergantung kepada bagaimana kita memiliki titik mereka antara satu sama lain 647 00:35:06,670 --> 00:35:08,600 dan bagaimana kita melintasi melalui mereka dan bagaimana kita 648 00:35:08,600 --> 00:35:14,500 memasukkan sesuatu yang menentukan ciri-ciri yang berbeza. 649 00:35:14,500 --> 00:35:17,600 >> Jadi hanya beberapa istilah, yang saya gunakan sebelum ini. 650 00:35:17,600 --> 00:35:20,010 Jadi akar adalah apa yang ada di bahagian paling atas. 651 00:35:20,010 --> 00:35:21,200 itu di mana kita selalu bermula. 652 00:35:21,200 --> 00:35:23,610 Anda boleh menganggapnya sebagai kepala juga. 653 00:35:23,610 --> 00:35:28,750 Tetapi bagi pokok-pokok, kita cenderung untuk menyebutnya sebagai akar. 654 00:35:28,750 --> 00:35:32,820 >> Apa-apa sahaja di sini-bahagian bawah di sangat, sangat bottom-- 655 00:35:32,820 --> 00:35:34,500 adalah daun dipertimbangkan. 656 00:35:34,500 --> 00:35:37,210 Jadi ia pergi bersama-sama dengan perkara pokok keseluruhan, bukan? 657 00:35:37,210 --> 00:35:39,860 Daun di tepi pokok anda. 658 00:35:39,860 --> 00:35:45,820 >> Kemudian kami juga mempunyai beberapa hal untuk bercakap tentang nod berhubung 659 00:35:45,820 --> 00:35:46,680 satu sama lain. 660 00:35:46,680 --> 00:35:49,700 Jadi kita mempunyai ibu bapa, anak-anak, dan saudara kandung. 661 00:35:49,700 --> 00:35:56,260 Jadi dalam kes ini, 3 adalah induk dari 5, 6, dan 7. 662 00:35:56,260 --> 00:36:00,370 Jadi ibu bapa adalah apa yang ada satu langkah di atas apa sahaja yang anda 663 00:36:00,370 --> 00:36:02,940 merujuk kepada, jadi seperti pohon keluarga. 664 00:36:02,940 --> 00:36:07,090 Mudah-mudahan, ini semua kecil yang sedikit lebih intuitif daripada cuba. 665 00:36:07,090 --> 00:36:10,970 >> Saudara adalah setiap yang mempunyai ibu bapa yang sama, kan? 666 00:36:10,970 --> 00:36:13,470 Mereka berada di tahap yang sama di sini. 667 00:36:13,470 --> 00:36:16,960 Dan kemudian, kerana saya berkata, kanak-kanak hanya 668 00:36:16,960 --> 00:36:22,630 apa sahaja yang merupakan salah satu langkah di bawah nod yang berkenaan, OK? 669 00:36:22,630 --> 00:36:23,470 Sejuk. 670 00:36:23,470 --> 00:36:25,610 Jadi pokok binari. 671 00:36:25,610 --> 00:36:31,450 Ada yang bisa menebak pada salah satu ciri-ciri pokok binari? 672 00:36:31,450 --> 00:36:32,770 >> PENONTON: Max dua daun. 673 00:36:32,770 --> 00:36:33,478 >> SPEAKER 1: Benar. 674 00:36:33,478 --> 00:36:34,640 Jadi max dua daun. 675 00:36:34,640 --> 00:36:39,730 Jadi, dalam hal ini sebelumnya, kami mempunyai satu ini yang mempunyai tiga orang, tetapi di pohon binari, 676 00:36:39,730 --> 00:36:45,000 Anda mempunyai maksimum dua kanak-kanak setiap ibu bapa, kan? 677 00:36:45,000 --> 00:36:46,970 Ada satu lagi ciri-ciri yang menarik. 678 00:36:46,970 --> 00:36:51,550 Apakah ada yang tahu? 679 00:36:51,550 --> 00:36:52,620 Pokok binari. 680 00:36:52,620 --> 00:37:00,350 >> Jadi pokok binari akan mempunyai segala-galanya pada the-- satu ini tidak sorted-- 681 00:37:00,350 --> 00:37:05,320 tetapi dalam pokok binari yang disusun, semua yang ada di sebelah kanan 682 00:37:05,320 --> 00:37:08,530 adalah lebih besar daripada ibu bapa, dan semua yang ada di sebelah kiri 683 00:37:08,530 --> 00:37:10,035 kurang dari induk. 684 00:37:10,035 --> 00:37:15,690 Dan yang telah kuiz soalan sebelum ini, jadi baik untuk tahu. 685 00:37:15,690 --> 00:37:19,500 Jadi cara kita menentukan ini, lagi, kita mempunyai nod lain. 686 00:37:19,500 --> 00:37:21,880 Ini kelihatan hampir sama dengan apa? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Ganda 689 00:37:28,836 --> 00:37:29,320 >> PENONTON: Berkaitan senarai 690 00:37:29,320 --> 00:37:31,100 >> SPEAKER 1: Daftar terkait ganda, kan? 691 00:37:31,100 --> 00:37:33,690 Jadi jika kita mengganti ini dengan sebelum dan sesudahnya, 692 00:37:33,690 --> 00:37:35,670 ini akan menjadi satu senarai duanya adalah terpakai dikaitkan. 693 00:37:35,670 --> 00:37:40,125 Tetapi dalam kes ini, kita benar-benar mempunyai kiri dan kanan dan itu sahaja. 694 00:37:40,125 --> 00:37:41,500 Jika tidak, itu betul-betul sama. 695 00:37:41,500 --> 00:37:43,374 Kami masih mempunyai elemen anda cari, 696 00:37:43,374 --> 00:37:45,988 dan anda hanya perlu dua pointer akan apa pun yang akan datang. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Ya, pokok pencari sehingga binari. 699 00:37:51,870 --> 00:37:57,665 Kalau kita lihat, semua yang ada di di sini adalah than-- lebih besar 700 00:37:57,665 --> 00:37:59,850 atau segala sesuatu dengan segera di sini yang betul 701 00:37:59,850 --> 00:38:02,840 adalah lebih besar daripada, segala-galanya di sini adalah kurang daripada. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Jadi, jika kita adalah untuk mencari melalui, ia harus terlihat sangat dekat dengan carian binari 704 00:38:14,000 --> 00:38:14,910 di sini, kan? 705 00:38:14,910 --> 00:38:17,640 Kecuali bukan melihat pada separuh array, 706 00:38:17,640 --> 00:38:21,720 kita hanya melihat sama ada sebelah kiri sisi atau sebelah kanan pokok itu. 707 00:38:21,720 --> 00:38:24,850 Sehingga mendapat sedikit lebih mudah, saya fikir. 708 00:38:24,850 --> 00:38:29,300 >> Jadi, jika root anda adalah NULL, jelas ia hanya palsu. 709 00:38:29,300 --> 00:38:33,470 Dan jika itu ada, jelas itu benar. 710 00:38:33,470 --> 00:38:35,320 Jika kurang daripada, kita mencari sebelah kiri. 711 00:38:35,320 --> 00:38:37,070 Jika ia lebih besar dari, kita mencari kanan. 712 00:38:37,070 --> 00:38:39,890 Ini persis seperti carian binari, hanya struktur data yang berbeza 713 00:38:39,890 --> 00:38:40,600 yang kita gunakan. 714 00:38:40,600 --> 00:38:42,790 Daripada array, itu hanya pokok binari. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> OK, tumpukan. 717 00:38:48,090 --> 00:38:51,550 Dan juga, ia kelihatan seperti kita mungkin mempunyai sedikit masa. 718 00:38:51,550 --> 00:38:54,460 Jika kita lakukan, saya senang untuk pergi atas mana-mana dari ini lagi. 719 00:38:54,460 --> 00:38:56,856 OK, jadi tumpukan. 720 00:38:56,856 --> 00:39:02,695 Apakah ada yang ingat apa stacks-- apa-apa ciri-ciri stack? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, jadi kebanyakan kita, saya fikir, makan di makan halls-- 723 00:39:10,400 --> 00:39:13,100 seperti yang kita mungkin tidak suka. 724 00:39:13,100 --> 00:39:16,900 Tetapi jelas, anda boleh memikirkan tumpukan benar hanya sebagai tumpukan dulang 725 00:39:16,900 --> 00:39:18,460 atau tumpukan hal. 726 00:39:18,460 --> 00:39:21,820 Dan apa yang penting sedar ialah bahawa itu 727 00:39:21,820 --> 00:39:26,850 something-- ciri yang kita sebut itu oleh- adalah LIFO. 728 00:39:26,850 --> 00:39:28,450 Adakah sesiapa yang tahu apa itu singkatan? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> PENONTON: Kamari, keluar pertama. 731 00:39:30,650 --> 00:39:32,250 >> SPEAKER 1: Benar, bertahan, keluar pertama. 732 00:39:32,250 --> 00:39:36,585 Jadi, jika kita tahu, jika kita susun perkara atas, perkara yang paling mudah untuk mengambil off-- 733 00:39:36,585 --> 00:39:39,570 dan mungkin satu-satunya perkara yang boleh kita ambil off jika tumpukan kami adalah enough-- besar 734 00:39:39,570 --> 00:39:40,850 ialah elemen atas. 735 00:39:40,850 --> 00:39:43,460 Jadi apa pun yang memakai last-- seperti yang kita lihat di sini, 736 00:39:43,460 --> 00:39:46,370 apa sahaja yang didorong pada kebanyakan recently-- adalah 737 00:39:46,370 --> 00:39:51,160 akan menjadi yang pertama hal yang kita meninggal, OK? 738 00:39:51,160 --> 00:39:56,324 >> Jadi apa yang kita ada di sini adalah lain struct typedef. 739 00:39:56,324 --> 00:39:58,740 Ini benar-benar hanya seperti crash kursus dalam struktur data, 740 00:39:58,740 --> 00:40:01,650 jadi ada banyak dilemparkan pada anda semua. 741 00:40:01,650 --> 00:40:02,540 Saya tahu. 742 00:40:02,540 --> 00:40:04,970 Jadi belum struct lain. 743 00:40:04,970 --> 00:40:06,740 Yay untuk struktur. 744 00:40:06,740 --> 00:40:16,660 >> Dan dalam kes ini, ia adalah beberapa penunjuk ke array yang mempunyai kapasiti beberapa. 745 00:40:16,660 --> 00:40:20,830 Jadi ini merupakan tumpukan kami di sini, seperti array yang sebenarnya kami 746 00:40:20,830 --> 00:40:22,520 yang memegang unsur-unsur kita. 747 00:40:22,520 --> 00:40:24,850 Dan kemudian di sini kita mempunyai beberapa saiz. 748 00:40:24,850 --> 00:40:31,170 >> Dan biasanya, yang anda hendak simpan menjejaki seberapa besar stack adalah 749 00:40:31,170 --> 00:40:36,180 kerana apa yang ia akan membenarkan Anda lakukan adalah jika anda tahu saiz, 750 00:40:36,180 --> 00:40:39,170 ia membolehkan anda untuk mengatakan, OK, saya pada kapasiti? 751 00:40:39,170 --> 00:40:40,570 Bolehkah saya menambah apa-apa lagi? 752 00:40:40,570 --> 00:40:44,650 Dan ia juga memberitahu anda di mana bahagian atas tumpukan 753 00:40:44,650 --> 00:40:48,180 adalah supaya anda tahu apa yang anda benar-benar dapat dilaksanakan. 754 00:40:48,180 --> 00:40:51,760 Dan itu benar-benar akan menjadi sedikit lebih jelas di sini. 755 00:40:51,760 --> 00:40:57,350 >> Jadi untuk menolak, satu perkara, jika anda pernah untuk melaksanakan push, 756 00:40:57,350 --> 00:41:01,330 kerana saya hanya mengatakan, anda tumpukan mempunyai saiz yang terhad, bukan? 757 00:41:01,330 --> 00:41:03,990 Array kita mempunyai keupayaan beberapa. 758 00:41:03,990 --> 00:41:04,910 Ini array. 759 00:41:04,910 --> 00:41:08,930 Ini saiz yang tetap, jadi kita perlu memastikan bahawa kita tidak meletakkan lebih 760 00:41:08,930 --> 00:41:11,950 ke dalam array kita daripada kita sebenarnya mempunyai ruang untuk. 761 00:41:11,950 --> 00:41:16,900 >> Oleh itu, apabila anda membuat tolakan fungsi, perkara pertama yang anda lakukan adalah berkata, OK, 762 00:41:16,900 --> 00:41:18,570 saya perlu ruang di tumpukan saya? 763 00:41:18,570 --> 00:41:23,330 Kerana jika saya tidak, maaf, Saya tidak boleh menyimpan elemen anda. 764 00:41:23,330 --> 00:41:28,980 Jika saya lakukan, maka anda mahu untuk menyimpan ia di bahagian atas tindanan, kan? 765 00:41:28,980 --> 00:41:31,325 >> Dan ini adalah mengapa kita mempunyai untuk mengesan saiz kami. 766 00:41:31,325 --> 00:41:35,290 Jika kita tidak menjejaki saiz kami, kita tidak tahu di mana untuk meletakkan ia. 767 00:41:35,290 --> 00:41:39,035 Kita tidak tahu berapa banyak perkara berada dalam array kita sudah. 768 00:41:39,035 --> 00:41:41,410 Seperti jelas ada cara yang mungkin anda boleh melakukannya. 769 00:41:41,410 --> 00:41:44,610 Anda boleh memulakan segala-galanya kepada NULL dan kemudian memeriksa NULL terkini, 770 00:41:44,610 --> 00:41:47,950 tetapi satu perkara yang lebih mudah adalah hanya berkata, OK, menjejaki saiz. 771 00:41:47,950 --> 00:41:51,840 Seperti yang saya tahu saya mempunyai empat elemen yang sedang saya, jadi perkara yang akan datang 772 00:41:51,840 --> 00:41:55,930 yang kita pasang di, kami tidak akan menyimpan pada indeks 4. 773 00:41:55,930 --> 00:42:00,940 Dan kemudian, sudah tentu, ini bermakna Anda telah berjaya menolak sesuatu 774 00:42:00,940 --> 00:42:03,320 ke dalam tindanan anda, anda ingin meningkatkan saiz 775 00:42:03,320 --> 00:42:08,880 supaya anda tahu di mana anda begitu bahawa anda boleh menolak lebih banyak perkara pada. 776 00:42:08,880 --> 00:42:12,730 >> Jadi, jika kita cuba untuk pop sesuatu dari tumpukan, 777 00:42:12,730 --> 00:42:16,072 apa yang mungkin menjadi perkara pertama yang yang kita mahu untuk memeriksa? 778 00:42:16,072 --> 00:42:18,030 Anda sedang cuba untuk mengambil sesuatu dari stack. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Adakah anda pasti ada sesuatu dalam tumpukan anda? 781 00:42:24,781 --> 00:42:25,280 Tidak. 782 00:42:25,280 --> 00:42:26,894 Jadi apa yang kita mahu untuk memeriksa? 783 00:42:26,894 --> 00:42:27,810 >> PENONTON: [didengar]. 784 00:42:27,810 --> 00:42:29,880 SPEAKER 1: Semak untuk saiz? 785 00:42:29,880 --> 00:42:31,840 Saiz. 786 00:42:31,840 --> 00:42:38,520 Oleh itu, kita mahu untuk memeriksa untuk melihat jika saiz kami adalah lebih besar daripada 0, OK? 787 00:42:38,520 --> 00:42:44,970 Dan jika ya, maka kita mahu mengurangkan saiz kami oleh 0 dan kembali itu. 788 00:42:44,970 --> 00:42:45,840 Mengapa? 789 00:42:45,840 --> 00:42:49,950 >> Dalam kes pertama kita menolak, kami mendorong ia 790 00:42:49,950 --> 00:42:52,460 ke saiz dan ukuran kemudian diperbarui. 791 00:42:52,460 --> 00:42:57,850 Dalam hal ini, kami decrementing saiz dan kemudian mengambil it off, ia mencabut 792 00:42:57,850 --> 00:42:58,952 dari array kita. 793 00:42:58,952 --> 00:42:59,826 Mengapa kita boleh berbuat demikian? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Jadi jika saya mempunyai satu pada stack saya, apa yang akan menjadi saiz saya pada ketika itu? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> Dan di mana elemen 1 disimpan? 798 00:43:15,180 --> 00:43:17,621 Apa indeks? 799 00:43:17,621 --> 00:43:18,120 PENONTON: 0. 800 00:43:18,120 --> 00:43:19,060 SPEAKER 1: 0. 801 00:43:19,060 --> 00:43:22,800 Jadi dalam hal ini, kita sentiasa perlu membuat sure-- 802 00:43:22,800 --> 00:43:27,630 bukannya kembali saiz tolak 1, kerana kita 803 00:43:27,630 --> 00:43:31,730 tahu bahawa kita adalah elemen akan disimpan pada 1 kurang 804 00:43:31,730 --> 00:43:34,705 apa pun saiz kita, ini hanya mengambil mengurusnya. 805 00:43:34,705 --> 00:43:36,080 Ia adalah cara yang sedikit lebih elegan. 806 00:43:36,080 --> 00:43:41,220 Dan kami hanya pengurangan kami saiz dan kemudian kembali saiz. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> PENONTON: Saya kira hanya secara umum, mengapa struktur data ini 809 00:43:45,300 --> 00:43:47,800 memberi manfaat? 810 00:43:47,800 --> 00:43:50,660 >> SPEAKER 1: Ia bergantung kepada konteks anda. 811 00:43:50,660 --> 00:43:57,420 Jadi untuk beberapa teori, jika anda bekerja with-- OK, 812 00:43:57,420 --> 00:44:02,750 saya melihat apakah ada satu yang menguntungkan yang memberi manfaat kepada lebih daripada di luar 813 00:44:02,750 --> 00:44:05,420 CS. 814 00:44:05,420 --> 00:44:15,780 Dengan tumpukan, bila-bila masa yang anda perlukan untuk mengesan sesuatu yang 815 00:44:15,780 --> 00:44:20,456 adalah yang paling baru-baru ini ditambah adalah ketika Anda akan mahu menggunakan tumpukan. 816 00:44:20,456 --> 00:44:24,770 >> Dan saya tidak boleh memikirkan baik yang contoh yang sekarang. 817 00:44:24,770 --> 00:44:29,955 Tapi setiap kali yang paling baru-baru ini perkara yang paling penting bagi anda, 818 00:44:29,955 --> 00:44:31,705 saat itulah tumpukan akan menjadi berguna. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Saya cuba untuk berfikir jika ada satu yang baik untuk ini. 821 00:44:39,330 --> 00:44:43,720 Jika saya fikirkan satu contoh yang baik di akhirat 20 minit, saya pasti akan memberitahu anda. 822 00:44:43,720 --> 00:44:49,455 >> Tapi secara keseluruhan, jika ada apa-apa, seperti saya katakan kebanyakan, di mana yang terkini 823 00:44:49,455 --> 00:44:52,470 yang paling penting, yang mana tumpukan datang ke dalam bermain. 824 00:44:52,470 --> 00:44:58,860 Manakala antrian adalah jenis yang sebaliknya. 825 00:44:58,860 --> 00:44:59,870 Dan anjing-anjing kecil. 826 00:44:59,870 --> 00:45:00,890 Bukankah ini yang besar, bukan? 827 00:45:00,890 --> 00:45:03,299 Saya rasa seperti saya sepatutnya hanya mempunyai video kelinci 828 00:45:03,299 --> 00:45:05,090 betul-betul di tengah-tengah bahagian untuk kalian 829 00:45:05,090 --> 00:45:08,870 kerana ini adalah bahagian yang kuat. 830 00:45:08,870 --> 00:45:10,480 >> Jadi antrian. 831 00:45:10,480 --> 00:45:12,710 Pada dasarnya antrian adalah seperti garis. 832 00:45:12,710 --> 00:45:15,780 Kalian saya gunakan pasti ini setiap hari, sama seperti di ruang makan kami. 833 00:45:15,780 --> 00:45:18,160 Oleh itu, kita harus masuk dan mendapatkan nampan kami, saya 834 00:45:18,160 --> 00:45:21,260 pasti anda perlu menunggu dalam talian meleretkan atau mendapatkan makanan anda. 835 00:45:21,260 --> 00:45:24,650 >> Jadi perbezaan di sini adalah bahawa ini adalah FIFO. 836 00:45:24,650 --> 00:45:30,090 Jadi jika LIFO kali terakhir dalam, pertama keluar, FIFO adalah masuk dahulu, keluar dahulu. 837 00:45:30,090 --> 00:45:33,400 Jadi, ini adalah di mana apa sahaja yang anda meletakkan pada pertama adalah yang paling penting. 838 00:45:33,400 --> 00:45:35,540 Jadi jika anda sedang menunggu di line-- yang boleh anda 839 00:45:35,540 --> 00:45:39,130 bayangkan jika anda pergi ke pergi mendapatkan iPhone baru 840 00:45:39,130 --> 00:45:42,800 dan ia adalah timbunan di mana orang terakhir selaras mendapatkannya pertama, 841 00:45:42,800 --> 00:45:44,160 orang akan membunuh antara satu sama lain. 842 00:45:44,160 --> 00:45:49,800 >> Jadi FIFO, kami semua sangat akrab dengan di dunia nyata di sini, 843 00:45:49,800 --> 00:45:54,930 dan semuanya mempunyai kaitan dengan sebenarnya jenis mencipta baris ini seluruh 844 00:45:54,930 --> 00:45:56,900 dan beratur struktur. 845 00:45:56,900 --> 00:46:02,390 Jadi sedangkan dengan tumpukan, kita mempunyai dorongan dan pop. 846 00:46:02,390 --> 00:46:06,440 Dengan barisan, kita mempunyai enqueue dan dequeue. 847 00:46:06,440 --> 00:46:10,910 Jadi pada dasarnya berarti enqueue memasukkannya ke belakang, 848 00:46:10,910 --> 00:46:13,680 dan cara-cara mengambil dequeue off dari depan. 849 00:46:13,680 --> 00:46:18,680 Jadi struktur data kami adalah sedikit lebih rumit. 850 00:46:18,680 --> 00:46:21,060 Kami mempunyai Hal kedua yang perlu diketahui. 851 00:46:21,060 --> 00:46:25,950 >> Jadi tanpa kepala, ini betul-betul tumpukan, kan? 852 00:46:25,950 --> 00:46:27,900 Ini adalah struktur yang sama sebagai stack. 853 00:46:27,900 --> 00:46:32,480 Satu-satunya perkara yang berbeza sekarang ialah kita mempunyai kepala ini, yang apa yang anda fikir 854 00:46:32,480 --> 00:46:34,272 akan menjejaki? 855 00:46:34,272 --> 00:46:35,510 >> PENONTON: Yang pertama. 856 00:46:35,510 --> 00:46:38,685 >> SPEAKER 1: Benar, yang Perkara pertama yang kita masukkan ke dalam. 857 00:46:38,685 --> 00:46:41,130 Ketua barisan kami. 858 00:46:41,130 --> 00:46:42,240 Siapa pun yang di baris pertama. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Baiklah, jadi jika kita melakukan enqueue. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Sekali lagi, dengan mana-mana struktur data, 863 00:46:55,920 --> 00:46:59,760 kerana kita sedang berhadapan dengan array, kita perlu memeriksa jika kita mempunyai ruang. 864 00:46:59,760 --> 00:47:03,290 >> Ini adalah jenis seperti saya memberitahu kalian, jika anda membuka fail, 865 00:47:03,290 --> 00:47:04,760 anda perlu memeriksa null. 866 00:47:04,760 --> 00:47:08,330 Dengan mana-mana tumpukan ini dan antrian, anda perlu 867 00:47:08,330 --> 00:47:13,420 untuk melihat jika ada ruang kerana kita berurusan dengan pelbagai saiz tetap, 868 00:47:13,420 --> 00:47:16,030 seperti yang kita lihat di sini-0, 1 semua hingga 5. 869 00:47:16,030 --> 00:47:20,690 Jadi apa yang kita lakukan dalam kes cek untuk melihat apakah kita masih mempunyai ruang. 870 00:47:20,690 --> 00:47:23,110 Apakah saiz kami kurang daripada kapasiti? 871 00:47:23,110 --> 00:47:28,480 >> Jika demikian, kita perlu menyimpannya di ekor dan kita update ukuran kami. 872 00:47:28,480 --> 00:47:30,250 Jadi apa yang mungkin ekor berada dalam kes ini? 873 00:47:30,250 --> 00:47:32,360 Ia tidak jelas ditulis. 874 00:47:32,360 --> 00:47:33,380 Bagaimana kita menyimpannya? 875 00:47:33,380 --> 00:47:34,928 Apa yang akan menjadi ekor? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Jadi mari kita berjalan melalui contoh ini. 878 00:47:40,190 --> 00:47:44,590 Jadi ini adalah pelbagai saiz 6, kan? 879 00:47:44,590 --> 00:47:49,220 Dan kita miliki sekarang, saiz kami adalah 5. 880 00:47:49,220 --> 00:47:55,240 Dan ketika kita memasukkannya ke dalam, ia akan untuk pergi ke dalam indeks kelima, kan? 881 00:47:55,240 --> 00:47:57,030 Jadi menyimpan di ekor. 882 00:47:57,030 --> 00:48:05,600 >> Satu lagi cara untuk menulis ekor akan hanya menjadi array kita pada indeks ukuran, kan? 883 00:48:05,600 --> 00:48:07,560 Ini adalah saiz 5. 884 00:48:07,560 --> 00:48:11,490 Perkara seterusnya yang akan masuk ke 5. 885 00:48:11,490 --> 00:48:12,296 Cool? 886 00:48:12,296 --> 00:48:13,290 OK. 887 00:48:13,290 --> 00:48:16,350 Ia mendapat sedikit lebih rumit apabila kita mula bermain-main dengan kepala. 888 00:48:16,350 --> 00:48:17,060 Ya? 889 00:48:17,060 --> 00:48:20,090 >> PENONTON: Apakah itu bermakna kita akan diisytiharkan array yang 890 00:48:20,090 --> 00:48:23,880 adalah lima elemen panjang dan kemudian kami menambahkan ke atasnya? 891 00:48:23,880 --> 00:48:24,730 >> SPEAKER 1: No. 892 00:48:24,730 --> 00:48:27,560 Jadi dalam hal ini, ini adalah tumpukan. 893 00:48:27,560 --> 00:48:31,760 Ini akan dinyatakan sebagai array ukuran 6. 894 00:48:31,760 --> 00:48:37,120 Dan dalam hal ini, kita hanya mempunyai satu ruangan kiri. 895 00:48:37,120 --> 00:48:42,720 >> OK, jadi satu perkara yang dalam ini kes, jika kepala kita adalah pada 0, 896 00:48:42,720 --> 00:48:45,270 maka kita hanya boleh menambahkannya pada saiz. 897 00:48:45,270 --> 00:48:51,020 Tetapi ia menjadi sedikit rumit kerana sebenarnya, mereka 898 00:48:51,020 --> 00:48:52,840 tidak mempunyai slaid yang untuk ini, jadi saya akan 899 00:48:52,840 --> 00:48:56,670 untuk menarik satu kerana ia bukan sesederhana itu sebaik sahaja anda 900 00:48:56,670 --> 00:48:59,230 mulai menyingkirkan hal. 901 00:48:59,230 --> 00:49:03,920 Jadi sedangkan dengan tumpukan Anda hanya pernah mempunyai 902 00:49:03,920 --> 00:49:08,920 bimbang tentang apa saiz adalah apabila anda menambah sesuatu pada, 903 00:49:08,920 --> 00:49:15,710 dengan barisan yang anda juga perlu membuat memastikan bahawa kepala anda diambil kira, 904 00:49:15,710 --> 00:49:20,760 kerana satu perkara yang sejuk kira-kira antrian adalah bahawa jika anda tidak pada kapasiti, 905 00:49:20,760 --> 00:49:23,040 Anda benar-benar boleh membuat ia membungkus. 906 00:49:23,040 --> 00:49:28,810 >> OK, jadi satu thing-- oh, ini adalah kapur mengerikan. 907 00:49:28,810 --> 00:49:31,815 Satu perkara yang perlu dipertimbangkan adalah kes itu. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Kami hanya akan melakukan lima. 910 00:49:37,140 --> 00:49:41,810 OK, jadi kita akan mengatakan kepala di sini. 911 00:49:41,810 --> 00:49:46,140 Ini adalah 0, 1, 2, 3, 4. 912 00:49:46,140 --> 00:49:54,210 >> Kepala ada di sana, dan sila memiliki hal-hal di dalamnya. 913 00:49:54,210 --> 00:49:58,340 Dan kami ingin menambahkan sesuatu, kan? 914 00:49:58,340 --> 00:50:01,170 Jadi perkara yang kita perlu tahu ialah kepala sentiasa 915 00:50:01,170 --> 00:50:05,620 akan bergerak dengan cara ini dan maka gelung kembali sekitar, OK? 916 00:50:05,620 --> 00:50:10,190 >> Jadi barisan ini mempunyai ruang, bukan? 917 00:50:10,190 --> 00:50:13,950 Ia mempunyai ruang di awal-awal lagi, jenis yang bertentangan dengan ini. 918 00:50:13,950 --> 00:50:17,920 Jadi apa yang perlu kita lakukan adalah kita perlu mengira ekor. 919 00:50:17,920 --> 00:50:20,530 Jika anda tahu bahawa anda kepala tidak bergerak, ekor 920 00:50:20,530 --> 00:50:24,630 hanya array di indeks ukuran. 921 00:50:24,630 --> 00:50:30,000 >> Tetapi dalam realiti, jika anda menggunakan antrian, kepala anda mungkin sedang dikemas kini. 922 00:50:30,000 --> 00:50:33,890 Jadi apa yang anda perlu lakukan adalah benar-benar menghitung ekor. 923 00:50:33,890 --> 00:50:39,990 Jadi apa yang kita lakukan adalah formula ini di sini, yang saya akan memberitahu anda 924 00:50:39,990 --> 00:50:42,680 semua berfikir tentang, dan maka kita akan bercakap tentang hal itu. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Jadi, ini adalah kapasiti. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Jadi ini akan benar-benar memberi anda cara untuk melakukannya. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Kerana dalam kes ini, apa? 931 00:51:04,330 --> 00:51:09,205 Pusat kami pada 1, saiz kami adalah 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Jika kita mod yang sebanyak 5, kita akan mendapat 0, yang di mana kami perlu input itu. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Jadi, dalam keadaan yang akan datang, jika kita melakukan ini, 936 00:51:26,080 --> 00:51:33,390 kita kata, OK, mari kita dequeue sesuatu. 937 00:51:33,390 --> 00:51:34,390 Kami dequeue ini. 938 00:51:34,390 --> 00:51:37,740 Kami mengambil elemen ini, kan? 939 00:51:37,740 --> 00:51:47,930 >> Dan sekarang kepala kita menunjuk sini, dan kami ingin menambah dalam perkara lain. 940 00:51:47,930 --> 00:51:52,470 Ini pada dasarnya adalah belakang garis kita, kan? 941 00:51:52,470 --> 00:51:55,450 Antrian dapat membungkus array. 942 00:51:55,450 --> 00:51:57,310 Itulah salah satu perbezaan utama. 943 00:51:57,310 --> 00:51:58,780 Tumpukan, anda tidak boleh melakukan ini. 944 00:51:58,780 --> 00:52:01,140 >> Dengan antrian, anda boleh kerana apa yang penting 945 00:52:01,140 --> 00:52:03,940 adalah bahawa anda tahu apa yang ditambah yang paling baru-baru ini. 946 00:52:03,940 --> 00:52:10,650 Oleh kerana semuanya akan ditambahkan dalam arah ke kiri ini, dalam kes ini, 947 00:52:10,650 --> 00:52:16,480 dan kemudian membungkus, anda boleh terus menyediakan elemen-elemen baru 948 00:52:16,480 --> 00:52:18,830 di depan array kerana ia tidak benar-benar 949 00:52:18,830 --> 00:52:20,640 hadapan array lagi. 950 00:52:20,640 --> 00:52:26,320 Anda boleh berfikir dari awal array sebagai mana kepala anda sebenarnya. 951 00:52:26,320 --> 00:52:29,710 >> Jadi formula ini adalah bagaimana anda mengira ekor anda. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Adakah ini masuk akal? 954 00:52:35,610 --> 00:52:36,110 OK. 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 OK, dequeue, dan kemudian kalian punya 10 minit 957 00:52:44,040 --> 00:52:48,840 untuk bertanyakan soalan klarifikasi anda mahu, kerana saya tahu ia adalah gila. 958 00:52:48,840 --> 00:52:51,980 >> Baiklah, jadi dalam way-- yang sama Saya tidak tahu jika anda semua perasan, 959 00:52:51,980 --> 00:52:53,450 tetapi CS adalah tentang corak. 960 00:52:53,450 --> 00:52:57,370 Hal yang hampir sama, hanya dengan tweak kecil. 961 00:52:57,370 --> 00:52:58,950 Jadi perkara yang sama di sini. 962 00:52:58,950 --> 00:53:04,040 Kita perlu menyemak untuk melihat jika kita benar-benar mempunyai sesuatu dalam barisan kita, kan? 963 00:53:04,040 --> 00:53:05,960 Berkata, OK, adalah saiz kami lebih besar dari 0? 964 00:53:05,960 --> 00:53:06,730 Sejuk. 965 00:53:06,730 --> 00:53:10,690 >> Jika kita lakukan, maka kita bergerak kepala kita, yang adalah apa yang saya hanya ditunjukkan di sini. 966 00:53:10,690 --> 00:53:13,870 Kami untuk mengemaskinikan kepala kita untuk menjadi satu lagi. 967 00:53:13,870 --> 00:53:18,390 Dan kemudian kita pengurangan kami saiz dan kembali elemen. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Ada banyak lagi yang konkrit kod pada study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 dan saya sangat menyarankan akan melaluinya jika anda mempunyai masa, 971 00:53:29,440 --> 00:53:30,980 walaupun itu hanya pseudo-kod. 972 00:53:30,980 --> 00:53:35,980 Dan jika kalian ingin berbicara melalui bahawa dengan saya satu-satu, sila beritahu saya 973 00:53:35,980 --> 00:53:37,500 tahu. 974 00:53:37,500 --> 00:53:38,770 Saya dengan senang hati. 975 00:53:38,770 --> 00:53:42,720 Struktur data, jika Anda mengambil CS 124, anda akan 976 00:53:42,720 --> 00:53:47,830 tahu bahawa struktur data menjadi sangat menyenangkan dan ini baru sahaja bermula. 977 00:53:47,830 --> 00:53:50,350 >> Jadi saya tahu ia sukar. 978 00:53:50,350 --> 00:53:51,300 Tidak apa-apa. 979 00:53:51,300 --> 00:53:52,410 Kita berjuang. 980 00:53:52,410 --> 00:53:53,630 Aku masih. 981 00:53:53,630 --> 00:53:56,660 Jadi jangan bimbang terlalu banyak tentang hal itu. 982 00:53:56,660 --> 00:54:02,390 >> Tetapi itu pada asasnya anda crash kursus dalam struktur data. 983 00:54:02,390 --> 00:54:03,400 Aku tahu itu banyak. 984 00:54:03,400 --> 00:54:06,860 Adakah terdapat apa-apa yang kita ingin pergi lagi? 985 00:54:06,860 --> 00:54:09,400 Apa pun yang kita mahu bercakap melalui? 986 00:54:09,400 --> 00:54:10,060 Ya? 987 00:54:10,060 --> 00:54:16,525 >> PENONTON: Sebagai contoh itu, jadi ekor baru adalah pada 0 lebih dari itu? 988 00:54:16,525 --> 00:54:17,150 SPEAKER 1: Ya. 989 00:54:17,150 --> 00:54:18,230 PENONTON: OK. 990 00:54:18,230 --> 00:54:24,220 Jadi kemudian akan melalui, Anda harus 1 ditambah 4 or-- 991 00:54:24,220 --> 00:54:27,671 >> SPEAKER 1: Jadi, anda telah berkata, apabila kita mahu pergi melakukan ini lagi? 992 00:54:27,671 --> 00:54:28,296 PENONTON: Ya. 993 00:54:28,296 --> 00:54:38,290 Jadi jika anda telah mencari out-- mana Anda mengira ekor dari dalam itu? 994 00:54:38,290 --> 00:54:44,260 >> SPEAKER 1: Jadi ekor adalah dalam- saya berubah ini. 995 00:54:44,260 --> 00:54:52,010 Jadi, dalam contoh ini di sini, ini adalah array kita sedang melihat, OK? 996 00:54:52,010 --> 00:54:54,670 Oleh itu, kita mempunyai perkara-perkara dalam 1, 2, 3, dan 4. 997 00:54:54,670 --> 00:55:05,850 Jadi kita mempunyai kepala kita adalah sama dengan 1 pada ketika ini, dan saiz kami adalah sama dengan 4 998 00:55:05,850 --> 00:55:07,050 pada ketika ini, kan? 999 00:55:07,050 --> 00:55:08,960 >> Anda semua setuju itu yang terjadi? 1000 00:55:08,960 --> 00:55:14,620 Oleh itu, kita melakukan kepala plus saiz, yang memberi kita 5, dan kemudian kami mod sebanyak 5. 1001 00:55:14,620 --> 00:55:20,690 Kita mendapat 0, yang memberitahu kita bahawa 0 adalah di mana ekor kita, di mana kita mempunyai ruang. 1002 00:55:20,690 --> 00:55:22,010 >> PENONTON: Apa topi? 1003 00:55:22,010 --> 00:55:23,520 >> SPEAKER 1: Keupayaan. 1004 00:55:23,520 --> 00:55:24,020 Maaf. 1005 00:55:24,020 --> 00:55:29,640 Jadi itulah saiz array. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Ya? 1008 00:55:36,047 --> 00:55:39,210 >> PENONTON: [didengar] sebelum kita kembali elemen? 1009 00:55:39,210 --> 00:55:46,270 >> SPEAKER 1: Jadi kita memindahkan kepala atau kembali masa ini? 1010 00:55:46,270 --> 00:55:52,680 Jadi, jika kita bergerak satu, pengurangan saiz? 1011 00:55:52,680 --> 00:55:54,150 Tunggu. 1012 00:55:54,150 --> 00:55:55,770 Saya pasti lupa lain. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 Tidak apa-apa. 1015 00:56:01,990 --> 00:56:04,980 Tidak ada formula lain. 1016 00:56:04,980 --> 00:56:09,980 Ya, anda akan mahu kembali kepala dan kemudian memindahkannya kembali. 1017 00:56:09,980 --> 00:56:13,270 >> PENONTON: OK, kerana Pada ini mata, kepala adalah pada 0, 1018 00:56:13,270 --> 00:56:18,452 dan kemudian anda ingin kembali Isi 0 dan kemudian membuat kepala 1? 1019 00:56:18,452 --> 00:56:19,870 >> SPEAKER 1: Benar. 1020 00:56:19,870 --> 00:56:22,820 Saya rasa terdapat satu lagi jenis formula seperti ini. 1021 00:56:22,820 --> 00:56:26,970 Saya tidak mempunyai ia di atas kepala saya sebagai Saya tidak mahu memberikan satu yang salah. 1022 00:56:26,970 --> 00:56:35,470 Tetapi saya rasa ia benar-benar berlaku ke berkata, OK, menyimpan element-- ini apa pun yang 1023 00:56:35,470 --> 00:56:40,759 elemen kepala ini is-- pengurangan anda saiz, gerakkan kepala anda ke atas, dan pulangan 1024 00:56:40,759 --> 00:56:41,800 apa sahaja unsur yang. 1025 00:56:41,800 --> 00:56:44,760 Itu benar berlaku. 1026 00:56:44,760 --> 00:56:45,260 OK. 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 Saya rasa seperti ini bukan seperti most-- anda tidak 1029 00:56:53,560 --> 00:56:55,740 akan berjalan keluar dari sini seperti, ya, aku tahu cuba. 1030 00:56:55,740 --> 00:56:56,880 Saya mendapat semuanya. 1031 00:56:56,880 --> 00:56:57,670 Tidak apa-apa. 1032 00:56:57,670 --> 00:57:00,200 Aku janji. 1033 00:57:00,200 --> 00:57:05,240 Tetapi struktur data adalah sesuatu yang ia mengambil banyak masa untuk membiasakan diri. 1034 00:57:05,240 --> 00:57:10,010 Mungkin salah satu yang paling sukar perkara, saya fikir, dalam kursus ini. 1035 00:57:10,010 --> 00:57:15,330 >> Jadi ia pasti mengambil masa pengulangan dan melihat saya at-- 1036 00:57:15,330 --> 00:57:20,050 tidak benar-benar tahu daftar terkait sampai saya melakukan terlalu banyak dengan mereka, 1037 00:57:20,050 --> 00:57:22,550 dengan cara yang sama bahawa saya tidak benar-benar memahami petunjuk 1038 00:57:22,550 --> 00:57:27,040 sehingga aku sudah mengajar selama dua tahun dan melakukan pşet saya sendiri dengannya. 1039 00:57:27,040 --> 00:57:28,990 Ia mengambil banyak pengulangan dan masa. 1040 00:57:28,990 --> 00:57:32,600 Dan akhirnya, ia jenis akan klik. 1041 00:57:32,600 --> 00:57:36,320 >> Tetapi dalam pada itu, jika anda mempunyai jenis dari pemahaman yang tinggi tentang apa yang 1042 00:57:36,320 --> 00:57:39,321 ini lakukan, kebaikan mereka dan cons-- yang adalah apa yang 1043 00:57:39,321 --> 00:57:41,820 kita benar-benar cenderung menekankan, terutama dalam perjalanan intro. 1044 00:57:41,820 --> 00:57:45,511 Seperti, mengapa kita akan menggunakan cuba lebih array? 1045 00:57:45,511 --> 00:57:48,010 Seperti, apakah positif dan negatif dari masing-masing? 1046 00:57:48,010 --> 00:57:51,610 >> Dan memahami keseimbangan antara setiap struktur ini 1047 00:57:51,610 --> 00:57:54,910 adalah apa yang lebih penting sekarang. 1048 00:57:54,910 --> 00:57:58,140 Mungkin ada yang gila soalan atau dua itu 1049 00:57:58,140 --> 00:58:03,710 akan meminta anda untuk melaksanakan tolak atau melaksanakan pop atau enqueue dan dequeue. 1050 00:58:03,710 --> 00:58:07,340 Tetapi bagi sebahagian besar, yang mempunyai pemahaman yang lebih tinggi dan lebih 1051 00:58:07,340 --> 00:58:09,710 dari pemahaman intuitif adalah lebih penting daripada benar-benar 1052 00:58:09,710 --> 00:58:11,250 mampu untuk melaksanakannya. 1053 00:58:11,250 --> 00:58:14,880 >> Ia akan menjadi benar-benar luar biasa jika anda semua mampu keluar dan pergi melaksanakan cuba, 1054 00:58:14,880 --> 00:58:19,720 tetapi kita faham ia tidak semestinya perkara yang paling wajar sekarang. 1055 00:58:19,720 --> 00:58:23,370 Tetapi anda boleh dalam Serangga anda, jika anda mahu kepada, dan kemudian anda akan mendapat latihan, 1056 00:58:23,370 --> 00:58:27,200 dan kemudian mungkin anda akan benar-benar memahaminya. 1057 00:58:27,200 --> 00:58:27,940 Ya? 1058 00:58:27,940 --> 00:58:30,440 >> PENONTON: OK, jadi mana yang kita dimaksudkan untuk digunakan dalam Serangga ini? 1059 00:58:30,440 --> 00:58:31,916 Adakah saya perlu menggunakan salah satu daripada mereka? 1060 00:58:31,916 --> 00:58:32,540 SPEAKER 1: Ya. 1061 00:58:32,540 --> 00:58:34,199 Jadi, anda mempunyai pilihan anda. 1062 00:58:34,199 --> 00:58:36,740 Saya rasa dalam hal ini, kita dapat bercakap tentang Serangga yang sedikit 1063 00:58:36,740 --> 00:58:40,480 kerana saya berlari melalui ini. 1064 00:58:40,480 --> 00:58:47,779 Jadi dalam Serangga anda, anda mempunyai anda pilihan mencoba atau jadual hash. 1065 00:58:47,779 --> 00:58:49,570 Sesetengah orang akan cuba dan menggunakan penapis mekar, 1066 00:58:49,570 --> 00:58:51,840 tetapi mereka secara teknikal tidak betul. 1067 00:58:51,840 --> 00:58:55,804 Kerana sifat kebarangkalian mereka, mereka memberikan hasil positif palsu kadang-kadang. 1068 00:58:55,804 --> 00:58:57,095 Mereka melihat sejuk ke dalam, walaupun. 1069 00:58:57,095 --> 00:58:59,030 Sangat mengesyorkan mencari pada mereka sekurang-kurangnya. 1070 00:58:59,030 --> 00:59:03,260 Tetapi anda mempunyai pilihan anda antara jadual hash dan cuba. 1071 00:59:03,260 --> 00:59:06,660 Dan itu akan berada di tempat anda memuatkan kamus anda. 1072 00:59:06,660 --> 00:59:09,230 >> Dan anda akan perlu untuk memilih fungsi hash anda, 1073 00:59:09,230 --> 00:59:13,420 Anda akan perlu untuk memilih berapa banyak baldi pada anda, dan ia akan berubah-ubah. 1074 00:59:13,420 --> 00:59:17,440 Seperti jika anda mempunyai lebih ember, mungkin itu akan berjalan lebih cepat. 1075 00:59:17,440 --> 00:59:22,790 Tapi mungkin anda membuang banyak ruang dengan cara itu, walaupun. 1076 00:59:22,790 --> 00:59:26,320 Anda perlu mencari jalan keluar. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> PENONTON: Anda berkata sebelum itu kita boleh menggunakan fungsi-fungsi hash yang lain, 1079 00:59:29,875 --> 00:59:31,750 bahwa kita tidak perlu membuat fungsi hash? 1080 00:59:31,750 --> 00:59:32,666 >> SPEAKER 1: Ya, betul. 1081 00:59:32,666 --> 00:59:38,150 Jadi secara harfiah untuk fungsi hash anda, seperti google "fungsi hash" 1082 00:59:38,150 --> 00:59:40,770 dan mencari beberapa yang sejuk. 1083 00:59:40,770 --> 00:59:43,250 Anda tidak diharapkan untuk membina fungsi hash anda sendiri. 1084 00:59:43,250 --> 00:59:46,100 Orang-orang menghabiskan mereka tesis tentang perkara-perkara ini. 1085 00:59:46,100 --> 00:59:50,250 >> Jadi jangan risau tentang membina anda sendiri. 1086 00:59:50,250 --> 00:59:53,350 Cari satu talian untuk memulakan dengan. 1087 00:59:53,350 --> 00:59:56,120 Sebahagian daripada mereka yang anda perlu memanipulasi sedikit 1088 00:59:56,120 --> 00:59:59,430 untuk membuat jenis pulangan pasti cocok dan barang kecil, jadi pada mulanya, 1089 00:59:59,430 --> 01:00:02,420 Saya akan mengesyorkan menggunakan sesuatu benar-benar mudah yang mungkin hanya 1090 01:00:02,420 --> 01:00:04,680 hash pada huruf pertama. 1091 01:00:04,680 --> 01:00:08,760 Dan kemudian sekali anda mempunyai kerja yang, menggabungkan fungsi hash yang lebih sejuk. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> PENONTON: Apakah yang cuba menjadi atau cekap tetapi hanya lebih sukar untuk, like-- 1094 01:00:13,020 --> 01:00:15,880 >> SPEAKER 1: Jadi cuba, saya fikir, secara intuitif keras untuk melaksanakan 1095 01:00:15,880 --> 01:00:18,310 tetapi sangat cepat. 1096 01:00:18,310 --> 01:00:20,620 Walau bagaimanapun, mengambil lebih banyak ruang. 1097 01:00:20,620 --> 01:00:25,270 Sekali lagi, anda boleh mengoptimumkan kedua-dua mereka yang berada dalam cara yang berbeza dan ada cara kepada- 1098 01:00:25,270 --> 01:00:26,770 PENONTON: Bagaimana kita dinilai pada ini? 1099 01:00:26,770 --> 01:00:27,540 Adakah ia masalah- 1100 01:00:27,540 --> 01:00:29,164 >> SPEAKER 1: Jadi anda dinilai dengan cara biasa. 1101 01:00:29,164 --> 01:00:31,330 Anda akan dinilai pada reka bentuk. 1102 01:00:31,330 --> 01:00:36,020 Ke mana sahaja yang anda lakukan, anda mahu pastikan itu sebagai elegan kerana ia boleh menjadi 1103 01:00:36,020 --> 01:00:38,610 dan seefisien mungkin. 1104 01:00:38,610 --> 01:00:41,950 Tetapi jika anda memilih yang cuba atau hash meja, selama ia berfungsi, 1105 01:00:41,950 --> 01:00:45,350 kami gembira dengan itu. 1106 01:00:45,350 --> 01:00:48,370 Dan jika anda menggunakan sesuatu yang hash surat pertama, tidak apa-apa, 1107 01:00:48,370 --> 01:00:51,410 seperti mungkin seperti reka bentuk-bijak. 1108 01:00:51,410 --> 01:00:53,410 Kami juga mencapai titik dalam semester-- ini 1109 01:00:53,410 --> 01:00:55,340 Saya tidak tahu jika anda orang noticed-- jika anda 1110 01:00:55,340 --> 01:00:58,780 gred Serangga menurun sedikit kerana reka bentuk dan yang lainnya, 1111 01:00:58,780 --> 01:00:59,900 yang baik-baik saja. 1112 01:00:59,900 --> 01:01:02,960 Ia sampai ke titik di mana anda program yang semakin rumit. 1113 01:01:02,960 --> 01:01:04,830 Ada lebih banyak tempat anda boleh memperbaiki. 1114 01:01:04,830 --> 01:01:06,370 >> Jadi ia adalah perkara biasa. 1115 01:01:06,370 --> 01:01:08,810 Ia bukan bahawa anda melakukan lebih buruk pada Serangga anda. 1116 01:01:08,810 --> 01:01:11,885 Hanya saja kita yang lebih keras pada anda sekarang. 1117 01:01:11,885 --> 01:01:13,732 Jadi semua orang perasaan itu. 1118 01:01:13,732 --> 01:01:14,940 Saya hanya dinilai semua pşet anda. 1119 01:01:14,940 --> 01:01:16,490 Aku tahu semua orang berasa ia. 1120 01:01:16,490 --> 01:01:19,600 >> Jadi jangan bimbang tentang itu. 1121 01:01:19,600 --> 01:01:23,580 Dan jika anda mempunyai sebarang soalan mengenai pşet sebelumnya atau cara anda boleh meningkatkan, 1122 01:01:23,580 --> 01:01:27,760 Saya cuba dan komen yang spesifik tempat, tetapi kadang-kadang lewat 1123 01:01:27,760 --> 01:01:30,840 dan saya mendapat letih. 1124 01:01:30,840 --> 01:01:34,885 Apakah ada perkara-perkara lain tentang struktur data? 1125 01:01:34,885 --> 01:01:37,510 Saya pasti anda semua tidak benar-benar mahu bercakap tentang mereka lagi, 1126 01:01:37,510 --> 01:01:42,650 tetapi jika ada, aku senang pergi atas mereka, serta apa-apa 1127 01:01:42,650 --> 01:01:45,580 dari kuliah yang lepas minggu atau minggu lepas. 1128 01:01:45,580 --> 01:01:51,580 >> Saya tahu minggu lepas adalah kajian semua, jadi kita mungkin telah melangkau lebih kajian beberapa 1129 01:01:51,580 --> 01:01:54,190 dari kuliah. 1130 01:01:54,190 --> 01:01:58,230 Apa-apa soalan lain yang boleh menjawab? 1131 01:01:58,230 --> 01:01:59,350 OK, baiklah. 1132 01:01:59,350 --> 01:02:02,400 Nah, kalian keluar 15 minit awal. 1133 01:02:02,400 --> 01:02:08,370 >> Saya berharap ini adalah separuh membantu sekurang-kurangnya, dan saya akan melihat kalian minggu depan, 1134 01:02:08,370 --> 01:02:12,150 atau Kamis waktu pejabat. 1135 01:02:12,150 --> 01:02:15,285 Adakah terdapat permintaan untuk makanan ringan untuk minggu depan, ia adalah perkara yang? 1136 01:02:15,285 --> 01:02:17,459 Oleh kerana saya terlupa gula-gula hari ini. 1137 01:02:17,459 --> 01:02:19,750 Dan aku membawa gula-gula lepas minggu, tetapi ia adalah hari Columbus, 1138 01:02:19,750 --> 01:02:25,400 jadi ada seperti enam orang yang mempunyai empat beg gula-gula kepada diri mereka sendiri. 1139 01:02:25,400 --> 01:02:28,820 Saya dapat membawa Starbursts lagi jika anda suka. 1140 01:02:28,820 --> 01:02:29,580 Starbursts? 1141 01:02:29,580 --> 01:02:32,250 OK, bunyi yang baik. 1142 01:02:32,250 --> 01:02:35,050 Mempunyai hari yang hebat, orang-orang. 1143 01:02:35,050 --> 01:02:39,510