1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [MUSIC PLAYING] 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 bagian. 6 00:00:14,600 --> 00:00:18,660 Saya harap Anda semua sukses pulih dari kuis Anda 7 00:00:18,660 --> 00:00:19,510 dari minggu lalu. 8 00:00:19,510 --> 00:00:22,564 Aku tahu itu sedikit gila di kali. 9 00:00:22,564 --> 00:00:25,230 Seperti yang saya katakan sebelumnya, jika Anda dalam standar deviasi, 10 00:00:25,230 --> 00:00:28,188 tidak benar-benar khawatir tentang hal itu, terutama untuk bagian yang kurang nyaman. 11 00:00:28,188 --> 00:00:30,230 Itu adalah tentang di mana Anda harus. 12 00:00:30,230 --> 00:00:32,850 >> Jika Anda melakukan besar, maka mengagumkan. 13 00:00:32,850 --> 00:00:33,650 Kudos kepada Anda. 14 00:00:33,650 --> 00:00:36,149 Dan jika Anda merasa seperti Anda perlu sedikit bantuan lebih lanjut, silakan 15 00:00:36,149 --> 00:00:38,140 merasa bebas untuk mencapai ke salah satu TF. 16 00:00:38,140 --> 00:00:40,030 Kami semua di sini untuk membantu. 17 00:00:40,030 --> 00:00:40,960 >> Itu sebabnya kita mengajar. 18 00:00:40,960 --> 00:00:44,550 Itulah sebabnya aku di sini setiap hari Senin untuk Anda orang dan di kantor jam pada hari Kamis. 19 00:00:44,550 --> 00:00:48,130 Jadi jangan ragu untuk membiarkan saya tahu jika Anda khawatir tentang apa pun 20 00:00:48,130 --> 00:00:52,450 atau jika ada sesuatu di kuis bahwa Anda benar-benar ingin untuk mengatasi. 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 mendapatkan Anda akrab dengan ini. 23 00:01:01,520 --> 00:01:04,870 Anda mungkin tidak pernah menerapkan mereka di kelas ini. 24 00:01:04,870 --> 00:01:08,690 Beberapa dari mereka Anda akan, seperti untuk pset ejaan Anda. 25 00:01:08,690 --> 00:01:11,380 >> Anda akan memiliki pilihan Anda antara tabel hash dan mencoba. 26 00:01:11,380 --> 00:01:13,680 Jadi kita akan pasti akan atas mereka. 27 00:01:13,680 --> 00:01:18,690 Ini akan menjadi pasti lebih jenis dari bagian tingkat tinggi hari ini, meskipun, 28 00:01:18,690 --> 00:01:22,630 karena ada banyak dari mereka, dan jika kami pergi ke rincian implementasi 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 tabel 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 kali ini. 33 00:01:33,530 --> 00:01:36,870 Jika Anda memiliki pertanyaan tentang hal itu atau Anda ingin melihatnya dilaksanakan 34 00:01:36,870 --> 00:01:39,260 atau mencobanya sendiri, Saya merekomendasikan 35 00:01:39,260 --> 00:01:44,250 akan study.cs50.net, yang memiliki contoh semua ini. 36 00:01:44,250 --> 00:01:46,400 Ini akan memiliki PowerPoint saya dengan catatan bahwa kita 37 00:01:46,400 --> 00:01:50,860 cenderung menggunakan serta beberapa pemrograman latihan, terutama untuk hal-hal 38 00:01:50,860 --> 00:01:55,250 seperti daftar terhubung dan biner pohon tumpukan dan isyarat. 39 00:01:55,250 --> 00:01:59,590 Jadi sedikit tingkat yang lebih tinggi, yang mungkin bagus untuk kalian. 40 00:01:59,590 --> 00:02:01,320 >> Maka dengan itu, kita akan memulai. 41 00:02:01,320 --> 00:02:03,060 Dan juga, kuis yes--. 42 00:02:03,060 --> 00:02:06,550 Saya pikir sebagian besar dari Anda yang berada di Bagian saya memiliki kuis Anda, 43 00:02:06,550 --> 00:02:12,060 tapi setiap orang datang atau alasan tertentu Anda tidak, mereka di sini, di depan. 44 00:02:12,060 --> 00:02:12,740 >> Jadi terkait daftar. 45 00:02:12,740 --> 00:02:15,650 Aku tahu semacam ini berjalan untuk kembali sebelum kuis Anda. 46 00:02:15,650 --> 00:02:17,940 Itu adalah minggu sebelum bahwa kita belajar tentang hal ini. 47 00:02:17,940 --> 00:02:21,040 Tapi dalam kasus ini, kita hanya akan pergi sedikit lebih mendalam. 48 00:02:21,040 --> 00:02:25,900 >> Jadi mengapa mungkin kita memilih linked list lebih dari array? 49 00:02:25,900 --> 00:02:27,130 Apa yang membedakan mereka? 50 00:02:27,130 --> 00:02:27,630 Ya? 51 00:02:27,630 --> 00:02:30,464 >> AUDIENCE: Anda dapat memperluas terkait daftar versus 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 Sebuah array tetap memiliki ukuran sedangkan linked list memiliki ukuran variabel. 54 00:02:33,970 --> 00:02:36,970 Jadi jika kita tidak tahu bagaimana banyak kita ingin menyimpan, 55 00:02:36,970 --> 00:02:39,880 linked list memberikan kita besar cara untuk melakukan itu karena kita hanya bisa 56 00:02:39,880 --> 00:02:43,730 menambahkan node lain dan menambah node lain dan menambah node lain. 57 00:02:43,730 --> 00:02:45,750 Tapi apa yang mungkin menjadi trade-off? 58 00:02:45,750 --> 00:02:49,521 Apakah ada yang ingat trade-off antara array dan linked list? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> AUDIENCE: Anda harus pergi melalui semua jalan 61 00:02:51,460 --> 00:02:53,738 melalui linked list menemukan elemen dalam daftar. 62 00:02:53,738 --> 00:02:55,570 Dalam sebuah array, Anda dapat hanya menemukan elemen. 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 >> AUDIENCE: [tak terdengar]. 66 00:02:58,500 --> 00:03:01,090 >> SPEAKER 1: Dengan array, kita memiliki apa yang disebut akses acak. 67 00:03:01,090 --> 00:03:04,820 Berarti jika kita ingin apa yang pernah titik kelima daftar 68 00:03:04,820 --> 00:03:07,230 atau titik kelima kami array, kita bisa meraihnya. 69 00:03:07,230 --> 00:03:10,440 Jika itu adalah linked list, kita memiliki iterate melalui, kan? 70 00:03:10,440 --> 00:03:14,020 Jadi mengakses sebuah elemen dalam array adalah waktu yang konstan, 71 00:03:14,020 --> 00:03:19,530 sedangkan dengan linked list itu akan kemungkinan besar akan waktu linier karena mungkin 72 00:03:19,530 --> 00:03:21,370 Elemen kami adalah semua jalan di akhir. 73 00:03:21,370 --> 00:03:23,446 Kami harus mencari melalui segala sesuatu. 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 untuk menghabiskan sedikit lebih banyak waktu pada, apa saja plus dan negatif. 76 00:03:29,330 --> 00:03:31,480 Kapan kita ingin menggunakan satu atas yang lain? 77 00:03:31,480 --> 00:03:34,970 Dan itu semacam itu hal yang lebih besar untuk mengambil. 78 00:03:34,970 --> 00:03:40,140 >> Jadi kita harus di sini definisi node. 79 00:03:40,140 --> 00:03:43,040 Hal ini seperti salah satu unsur dalam linked list kita, kan? 80 00:03:43,040 --> 00:03:46,180 Jadi kita semua kenal dengan struct typedef kami, 81 00:03:46,180 --> 00:03:47,980 yang kami pergi di review terakhir kali. 82 00:03:47,980 --> 00:03:53,180 Itu pada dasarnya hanya menciptakan Jenis data lain yang dapat kita gunakan. 83 00:03:53,180 --> 00:03:57,930 >> Dan dalam hal ini, itu beberapa simpul yang akan memegang beberapa integer dalam. 84 00:03:57,930 --> 00:04:00,210 Dan kemudian apa bagian kedua di sini? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Siapa? 87 00:04:05,677 --> 00:04:06,680 >> AUDIENCE: [tak terdengar]. 88 00:04:06,680 --> 00:04:07,020 >> SPEAKER 1: Ya. 89 00:04:07,020 --> 00:04:08,400 Ini adalah pointer ke node berikutnya. 90 00:04:08,400 --> 00:04:12,610 Jadi ini benar-benar harus di sini. 91 00:04:12,610 --> 00:04:18,790 Ini adalah pointer tipe node ke hal berikutnya. 92 00:04:18,790 --> 00:04:22,410 Dan itulah yang mereka meliputi simpul kami. 93 00:04:22,410 --> 00:04:24,060 Keren. 94 00:04:24,060 --> 00:04:29,390 >> Baiklah, jadi dengan pencarian, karena kami hanya mengatakan sebelum tangan, jika Anda 95 00:04:29,390 --> 00:04:31,840 akan mencari melalui, Anda harus benar-benar iterate 96 00:04:31,840 --> 00:04:33,660 melalui daftar link. 97 00:04:33,660 --> 00:04:38,530 Jadi jika kita sedang mencari nomor 9, kita akan mulai dari kepala kita 98 00:04:38,530 --> 00:04:41,520 dan yang menunjuk kami di awal dari linked list kita, kan? 99 00:04:41,520 --> 00:04:44,600 Dan kita katakan, OK, apakah ini simpul berisi nomor 9? 100 00:04:44,600 --> 00:04:45,690 Tidak ada? 101 00:04:45,690 --> 00:04:47,500 >> Baiklah, pergi ke yang berikutnya. 102 00:04:47,500 --> 00:04:48,312 Mengikutinya. 103 00:04:48,312 --> 00:04:49,520 Apakah itu berisi nomor 9? 104 00:04:49,520 --> 00:04:50,570 Tidak. 105 00:04:50,570 --> 00:04:51,550 Ikuti berikutnya. 106 00:04:51,550 --> 00:04:55,490 >> Jadi kita harus benar-benar iterate melalui linked list kami. 107 00:04:55,490 --> 00:05:00,070 Kita tidak bisa hanya pergi langsung ke tempat 9 adalah. 108 00:05:00,070 --> 00:05:05,860 Dan jika kalian benar-benar ingin melihat beberapa pseudo-code di atas sana. 109 00:05:05,860 --> 00:05:10,420 Kami memiliki beberapa fungsi pencarian di sini yang mengambil in-- apa yang dibutuhkan dalam? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Bagaimana menurut Anda? 112 00:05:14,320 --> 00:05:15,960 Begitu mudah satu. 113 00:05:15,960 --> 00:05:17,784 Apa ini? 114 00:05:17,784 --> 00:05:18,700 AUDIENCE: [tak terdengar]. 115 00:05:18,700 --> 00:05:20,366 SPEAKER 1: Jumlah yang kita cari. 116 00:05:20,366 --> 00:05:20,980 Benar? 117 00:05:20,980 --> 00:05:22,875 Dan apa yang akan ini sesuai dengan? 118 00:05:22,875 --> 00:05:25,020 Ini adalah pointer ke? 119 00:05:25,020 --> 00:05:26,000 >> AUDIENCE: Sebuah node. 120 00:05:26,000 --> 00:05:28,980 >> SPEAKER 1: Sebuah node ke dalam daftar bahwa kita sedang melihat, kan? 121 00:05:28,980 --> 00:05:33,700 Jadi kita memiliki beberapa node pointer di sini. 122 00:05:33,700 --> 00:05:37,240 Ini adalah titik yang akan sebenarnya iterate melalui daftar kami. 123 00:05:37,240 --> 00:05:39,630 Kami mengaturnya sama dengan daftar karena itu hanya 124 00:05:39,630 --> 00:05:44,380 pengaturannya sama dengan mulai dari linked list kami. 125 00:05:44,380 --> 00:05:50,660 >> Dan sementara itu tidak NULL, sementara kita masih memiliki hal-hal dalam daftar kami, 126 00:05:50,660 --> 00:05:55,580 memeriksa untuk melihat apakah node yang memiliki jumlah yang kita cari. 127 00:05:55,580 --> 00:05:57,740 Kembali benar. 128 00:05:57,740 --> 00:06:01,070 Jika tidak, memperbarui, kan? 129 00:06:01,070 --> 00:06:04,870 >> Jika NULL, kami keluar kami while dan return false 130 00:06:04,870 --> 00:06:08,340 karena itu berarti kita belum menemukannya. 131 00:06:08,340 --> 00:06:11,048 Apakah setiap orang mendapatkan bagaimana 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 memiliki tiga cara yang berbeda. 135 00:06:20,260 --> 00:06:25,250 Anda dapat tambahkan, Anda dapat menambahkan dan Anda dapat memasukkan ke dalam berbagai macam. 136 00:06:25,250 --> 00:06:28,215 Dalam hal ini, kami akan melakukan tambahkan sebuah. 137 00:06:28,215 --> 00:06:33,380 Apakah ada yang tahu bagaimana mereka tiga kasus mungkin berbeda? 138 00:06:33,380 --> 00:06:36,920 >> Jadi tambahkan berarti bahwa Anda menempatkan itu di depan daftar Anda. 139 00:06:36,920 --> 00:06:39,770 Jadi itu berarti bahwa tidak peduli apa simpul Anda, tidak peduli 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 Ini akan menjadi yang pertama elemen dalam daftar Anda. 142 00:06:45,160 --> 00:06:49,510 >> Jika Anda tambahkan, itu akan untuk pergi ke belakang daftar Anda. 143 00:06:49,510 --> 00:06:54,010 Dan masukkan ke dalam berbagai macam berarti Anda akan menempatkan benar-benar ke tempat 144 00:06:54,010 --> 00:06:57,700 di mana itu membuat daftar Anda terhubung diurutkan. 145 00:06:57,700 --> 00:07:00,810 Sekali lagi, bagaimana Anda menggunakan mereka dan saat Anda menggunakan 146 00:07:00,810 --> 00:07:02,530 mereka akan bervariasi tergantung pada kasus Anda. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Jika tidak perlu diurutkan, tambahkan cenderung 149 00:07:07,750 --> 00:07:10,460 menjadi apa yang kebanyakan orang digunakan karena Anda tidak 150 00:07:10,460 --> 00:07:15,680 harus melalui seluruh daftar untuk menemukan akhir untuk menambahkannya, kan? 151 00:07:15,680 --> 00:07:17,720 Anda hanya dapat menempel tepat di. 152 00:07:17,720 --> 00:07:21,930 >> Jadi kita akan pergi melalui penyisipan 1 sekarang. 153 00:07:21,930 --> 00:07:26,360 Jadi satu hal yang aku akan sangat merekomendasikan pada pset ini 154 00:07:26,360 --> 00:07:29,820 adalah untuk menarik hal-hal, seperti biasa. 155 00:07:29,820 --> 00:07:35,130 Ini sangat penting bahwa Anda memperbarui pointer Anda dalam urutan yang benar 156 00:07:35,130 --> 00:07:38,620 karena jika Anda memperbarui mereka sedikit rusak, 157 00:07:38,620 --> 00:07:42,210 Anda akan berakhir kehilangan bagian dari daftar Anda. 158 00:07:42,210 --> 00:07:49,680 >> Jadi misalnya, dalam hal ini, kami mengatakan kepala untuk hanya titik untuk 1. 159 00:07:49,680 --> 00:07:56,070 Jika kita hanya melakukan itu tanpa menyimpan 1 ini, 160 00:07:56,070 --> 00:07:58,570 kita tidak tahu apa 1 harus menunjuk ke sekarang 161 00:07:58,570 --> 00:08:02,490 karena kita sudah kehilangan apa kepala menunjuk. 162 00:08:02,490 --> 00:08:05,530 Jadi, satu hal yang perlu diingat ketika Anda sedang melakukan tambahkan sebuah 163 00:08:05,530 --> 00:08:09,630 adalah untuk menyelamatkan apa yang kepala poin pertama, 164 00:08:09,630 --> 00:08:15,210 kemudian menetapkan kembali, dan kemudian memperbarui apa node 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 telah melakukannya dengan cara ini di mana kita hanya ditugaskan kembali kepala, 168 00:08:25,440 --> 00:08:30,320 kita kehilangan dasarnya kami seluruh daftar, kan? 169 00:08:30,320 --> 00:08:38,000 Salah satu cara untuk melakukannya adalah untuk memiliki 1 poin untuk berikutnya, dan kemudian memiliki titik kepala ke 1. 170 00:08:38,000 --> 00:08:42,650 Atau Anda dapat melakukan jenis seperti penyimpanan sementara, yang saya bicarakan. 171 00:08:42,650 --> 00:08:45,670 >> Tapi pemindahan Anda pointer dalam urutan yang benar 172 00:08:45,670 --> 00:08:48,750 akan menjadi sangat, sangat penting untuk pset ini. 173 00:08:48,750 --> 00:08:53,140 Jika tidak, Anda akan memiliki hash tabel atau mencoba yang hanya akan menjadi 174 00:08:53,140 --> 00:08:56,014 hanya sebagian dari kata-kata yang Anda inginkan dan kemudian mmhmm you're--? 175 00:08:56,014 --> 00:08:58,930 AUDIENCE: Apa sementara hal penyimpanan yang Anda bicarakan? 176 00:08:58,930 --> 00:09:00,305 SPEAKER 1: The penyimpanan sementara. 177 00:09:00,305 --> 00:09:02,760 Jadi pada dasarnya lain cara Anda bisa melakukan ini 178 00:09:02,760 --> 00:09:07,650 adalah menyimpan kepala sesuatu, seperti menyimpannya variabel sementara. 179 00:09:07,650 --> 00:09:11,250 Menetapkan ke 1 dan kemudian memperbarui 1 ke titik 180 00:09:11,250 --> 00:09:13,830 apa pun kepala digunakan untuk menunjuk ke. 181 00:09:13,830 --> 00:09:16,920 Cara ini jelas lebih elegan karena Anda 182 00:09:16,920 --> 00:09:20,770 tidak membutuhkan nilai sementara, tapi hanya menawarkan cara lain untuk melakukannya. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 Dan kita benar-benar memiliki beberapa kode untuk ini. 185 00:09:25,790 --> 00:09:28,080 Jadi untuk linked list, kita benar-benar memiliki beberapa kode. 186 00:09:28,080 --> 00:09:31,930 Jadi masukkan di sini, ini mengawali. 187 00:09:31,930 --> 00:09:34,290 Jadi ini masuk itu di kepala. 188 00:09:34,290 --> 00:09:38,820 >> Sehingga hal pertama, Anda perlu buat node baru Anda, tentu saja, 189 00:09:38,820 --> 00:09:40,790 dan memeriksa NULL. 190 00:09:40,790 --> 00:09:43,250 Selalu baik. 191 00:09:43,250 --> 00:09:47,840 Dan kemudian Anda harus menetapkan nilai-nilai. 192 00:09:47,840 --> 00:09:51,260 Setiap kali Anda membuat node baru, Anda tidak tahu apa itu menunjuk ke depan, 193 00:09:51,260 --> 00:09:54,560 sehingga Anda ingin menginisialisasi ke NULL. 194 00:09:54,560 --> 00:09:58,760 Jika tidak berakhir menunjuk ke sesuatu lain, hal itu akan ditugaskan kembali dan itu baik-baik saja. 195 00:09:58,760 --> 00:10:00,740 Jika itu hal pertama dalam daftar, dibutuhkan 196 00:10:00,740 --> 00:10:04,270 untuk menunjuk ke NULL karena itulah akhir dari daftar. 197 00:10:04,270 --> 00:10:12,410 >> Jadi untuk memasukkannya, kita lihat di sini kami menugaskan nilai berikutnya node kami 198 00:10:12,410 --> 00:10:17,380 untuk menjadi apa pun kepala, yang adalah apa yang kami punya di sini. 199 00:10:17,380 --> 00:10:19,930 Itulah apa yang baru saja kami lakukan. 200 00:10:19,930 --> 00:10:25,820 Dan kemudian kita menugaskan kepala ke titik ke node baru, karena ingat, 201 00:10:25,820 --> 00:10:31,090 baru beberapa pointer ke node, dan itulah apa kepala. 202 00:10:31,090 --> 00:10:34,370 Itulah mengapa kami memiliki panah accessor ini. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 Keren? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> AUDIENCE: Apakah kita harus menginisialisasi berikutnya baru ke NULL pertama, 207 00:10:41,100 --> 00:10:44,240 atau bisa kita hanya menginisialisasi ke kepala? 208 00:10:44,240 --> 00:10:48,210 >> SPEAKER 1: berikutnya Baru harus NULL untuk memulai 209 00:10:48,210 --> 00:10:53,760 karena Anda tidak tahu di mana itu akan menjadi. 210 00:10:53,760 --> 00:10:56,100 Juga, ini adalah jenis persis seperti paradigma. 211 00:10:56,100 --> 00:10:59,900 Anda menetapkan sama dengan NULL hanya untuk membuat memastikan bahwa semua basis Anda tertutup 212 00:10:59,900 --> 00:11:04,070 sebelum Anda melakukan penugasan sehingga Anda selalu dijamin bahwa hal itu akan 213 00:11:04,070 --> 00:11:08,880 menunjuk ke nilai tertentu dibandingkan seperti nilai sampah. 214 00:11:08,880 --> 00:11:12,210 Karena, ya, kita memberikan baru berikutnya secara otomatis, 215 00:11:12,210 --> 00:11:15,420 tapi lebih seperti sebuah praktik yang baik untuk menginisialisasi 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 pikirkan? 219 00:11:24,601 --> 00:11:26,350 Apa yang berbeda dengan ganda terkait daftar? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Jadi dalam daftar terhubung, kita bisa hanya bergerak dalam satu arah, kan? 222 00:11:34,300 --> 00:11:35,270 Kami hanya memiliki berikutnya. 223 00:11:35,270 --> 00:11:36,760 Kami hanya bisa maju. 224 00:11:36,760 --> 00:11:40,300 >> Dengan linked list ganda, kami juga bisa bergerak mundur. 225 00:11:40,300 --> 00:11:44,810 Jadi kita harus tidak hanya nomor yang ingin kita simpan, 226 00:11:44,810 --> 00:11:50,110 kami memiliki di mana ia menunjuk ke depan dan di mana kami hanya datang dari. 227 00:11:50,110 --> 00:11:52,865 Jadi ini memungkinkan untuk beberapa traversal yang lebih baik. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Node Jadi ganda terkait, sangat mirip, kan? 230 00:12:01,240 --> 00:12:05,000 Hanya bedanya sekarang kita memiliki berikutnya dan sebelumnya. 231 00:12:05,000 --> 00:12:06,235 Ini satu-satunya perbedaan. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Jadi jika kita tambahkan atau kita append-- tidak memiliki kode untuk ini sampai di sini- 234 00:12:14,790 --> 00:12:17,830 tetapi jika Anda adalah untuk mencoba dan masukkan, yang penting 235 00:12:17,830 --> 00:12:19,980 adalah Anda perlu membuat Pastikan Anda menetapkan 236 00:12:19,980 --> 00:12:23,360 baik Anda sebelumnya dan Anda pointer berikutnya dengan benar. 237 00:12:23,360 --> 00:12:29,010 Jadi dalam hal ini, Anda akan tidak hanya menginisialisasi berikutnya, 238 00:12:29,010 --> 00:12:31,820 Anda menginisialisasi sebelumnya. 239 00:12:31,820 --> 00:12:36,960 Jika kita berada di puncak daftar, kita tidak hanya akan membuat kepala sama baru, 240 00:12:36,960 --> 00:12:41,750 tetapi harus kami sebelumnya baru menunjuk ke kepala, kan? 241 00:12:41,750 --> 00:12:43,380 >> Itulah satu-satunya perbedaan. 242 00:12:43,380 --> 00:12:47,200 Dan jika Anda ingin lebih banyak latihan dengan ini dengan daftar link, dengan memasukkan, 243 00:12:47,200 --> 00:12:49,900 dengan menghapus, dengan insert ke daftar berbagai macam, 244 00:12:49,900 --> 00:12:52,670 silahkan periksa study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Ada sekelompok latihan besar. 246 00:12:54,870 --> 00:12:55,870 Saya sangat merekomendasikan mereka. 247 00:12:55,870 --> 00:12:59,210 Saya berharap kami punya waktu untuk pergi melalui mereka tapi ada banyak struktur data 248 00:12:59,210 --> 00:13:01,530 untuk melewati. 249 00:13:01,530 --> 00:13:02,650 >> OK, jadi tabel hash. 250 00:13:02,650 --> 00:13:07,070 Ini mungkin yang paling berguna bit untuk pset Anda 251 00:13:07,070 --> 00:13:11,090 di sini karena Anda akan menjadi menerapkan salah satu dari ini, atau mencoba. 252 00:13:11,090 --> 00:13:12,200 Saya sangat suka tabel hash. 253 00:13:12,200 --> 00:13:13,110 Mereka cukup keren. 254 00:13:13,110 --> 00:13:17,080 >> Jadi pada dasarnya apa terjadi adalah tabel hash 255 00:13:17,080 --> 00:13:22,050 adalah ketika kita benar-benar membutuhkan cepat penyisipan, penghapusan, dan pencarian. 256 00:13:22,050 --> 00:13:25,010 Mereka adalah hal-hal yang kita memprioritaskan dalam tabel hash. 257 00:13:25,010 --> 00:13:29,500 Mereka bisa mendapatkan cukup besar, tapi karena kami akan melihat dengan mencoba, 258 00:13:29,500 --> 00:13:33,040 ada hal-hal yang jauh lebih besar. 259 00:13:33,040 --> 00:13:38,330 >> Tapi pada dasarnya, semua hash tabel adalah fungsi hash 260 00:13:38,330 --> 00:13:47,215 yang memberitahu Anda yang ember untuk menempatkan setiap data Anda, masing-masing elemen di. 261 00:13:47,215 --> 00:13:51,140 Cara mudah untuk memikirkan tabel hash adalah bahwa itu hanya ember hal, 262 00:13:51,140 --> 00:13:51,770 kan? 263 00:13:51,770 --> 00:13:59,720 Jadi, ketika Anda menyortir hal-hal dengan seperti huruf pertama dari nama mereka, 264 00:13:59,720 --> 00:14:01,820 itu jenis seperti tabel hash. 265 00:14:01,820 --> 00:14:06,180 >> Jadi jika saya ke grup kalian adalah ke dalam kelompok siapa nama ini dimulai 266 00:14:06,180 --> 00:14:11,670 dengan A di sini, atau siapa pun yang ulang tahun adalah pada bulan Januari, Februari, Maret, 267 00:14:11,670 --> 00:14:15,220 apa pun, yang secara efektif membuat tabel hash. 268 00:14:15,220 --> 00:14:18,120 Hanya saja menciptakan ember yang Anda menyortir elemen Anda ke 269 00:14:18,120 --> 00:14:19,520 sehingga Anda dapat menemukan mereka lebih mudah. 270 00:14:19,520 --> 00:14:22,300 Jadi cara ini ketika saya membutuhkan untuk menemukan salah satu dari Anda, 271 00:14:22,300 --> 00:14:24,680 Saya tidak harus mencari melalui masing-masing nama Anda. 272 00:14:24,680 --> 00:14:29,490 Aku bisa seperti, oh, aku tahu bahwa Ulang tahun Danielle adalah in-- 273 00:14:29,490 --> 00:14:30,240 AUDIENCE: --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 ember, dan dengan sedikit keberuntungan, 276 00:14:33,120 --> 00:14:38,270 dia akan menjadi satu-satunya di sana dan waktu saya konstan dalam arti bahwa, 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 itu akan memakan waktu lebih lama. 279 00:14:43,090 --> 00:14:45,830 Jadi tabel hash yang benar-benar hanya ember. 280 00:14:45,830 --> 00:14:48,630 Cara mudah untuk memikirkan mereka. 281 00:14:48,630 --> 00:14:52,930 >> Jadi hal yang sangat penting tentang tabel hash adalah fungsi hash. 282 00:14:52,930 --> 00:14:58,140 Jadi hal-hal yang saya hanya berbicara tentang, seperti huruf pertama Anda nama pertama Anda 283 00:14:58,140 --> 00:15:01,450 atau bulan ulang tahun Anda, ini adalah ide 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 Ini hanya cara untuk memutuskan yang ember Anda elemen tidak masuk ke, OK? 286 00:15:08,900 --> 00:15:14,850 Jadi untuk pset ini, Anda dapat melihat hampir semua fungsi hash yang Anda inginkan. 287 00:15:14,850 --> 00:15:16,030 >> Tidak harus Anda sendiri. 288 00:15:16,030 --> 00:15:21,140 Ada beberapa yang benar-benar keren out ada yang melakukan segala macam gila matematika. 289 00:15:21,140 --> 00:15:25,170 Dan jika Anda ingin 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 >> Tapi ada juga yang sederhana, seperti menghitung 292 00:15:32,390 --> 00:15:39,010 jumlah dari kata-kata, seperti setiap huruf memiliki nomor. 293 00:15:39,010 --> 00:15:39,940 Menghitung penjumlahan. 294 00:15:39,940 --> 00:15:42,230 Yang menentukan ember. 295 00:15:42,230 --> 00:15:45,430 Mereka juga memiliki orang-orang mudah yang sama seperti semua A di sini, 296 00:15:45,430 --> 00:15:47,050 semua B di sini. 297 00:15:47,050 --> 00:15:48,920 Salah satu dari mereka. 298 00:15:48,920 --> 00:15:55,770 >> Pada dasarnya, itu 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 adalah. 300 00:15:58,690 --> 00:16:04,180 Jadi di sini kita memiliki contoh yang hanya huruf pertama dari string 301 00:16:04,180 --> 00:16:05,900 bahwa saya hanya berbicara tentang. 302 00:16:05,900 --> 00:16:11,900 >> Jadi Anda memiliki beberapa hash itu hanya huruf pertama dari string dikurangi A, 303 00:16:11,900 --> 00:16:16,090 yang akan memberi Anda beberapa angka antara 0 dan 25. 304 00:16:16,090 --> 00:16:20,790 Dan apa yang ingin Anda lakukan adalah pastikan bahwa ini mewakili 305 00:16:20,790 --> 00:16:24,110 ukuran hash Anda table-- berapa banyak ember ada. 306 00:16:24,110 --> 00:16:25,860 Dengan banyak dari fungsi hash, mereka 307 00:16:25,860 --> 00:16:31,630 akan nilai-nilai kembali yang mungkin jauh di atas jumlah ember 308 00:16:31,630 --> 00:16:33,610 bahwa Anda benar-benar memiliki dalam tabel hash Anda, 309 00:16:33,610 --> 00:16:37,240 sehingga Anda perlu membuat yakin dan mod oleh mereka. 310 00:16:37,240 --> 00:16:42,190 Jika tidak, itu akan berkata, oh, itu harus dalam ember 5.000 311 00:16:42,190 --> 00:16:46,040 tapi Anda hanya memiliki 30 ember dalam tabel hash Anda. 312 00:16:46,040 --> 00:16:49,360 Dan tentu saja, kita semua tahu itu akan menghasilkan beberapa kesalahan gila. 313 00:16:49,360 --> 00:16:52,870 Jadi pastikan untuk mod oleh ukuran tabel hash Anda. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Keren. 316 00:16:58,930 --> 00:17:00,506 Jadi tabrakan. 317 00:17:00,506 --> 00:17:02,620 Apakah semua orang baik sejauh ini? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> AUDIENCE: Mengapa itu kembali seperti nilai besar? 320 00:17:05,900 --> 00:17:09,210 >> SPEAKER 1: Tergantung pada algoritma bahwa fungsi hash Anda menggunakan. 321 00:17:09,210 --> 00:17:12,270 Beberapa dari mereka akan melakukan perkalian gila. 322 00:17:12,270 --> 00:17:16,270 Dan itu semua tentang mendapatkan bahkan distribusi, 323 00:17:16,270 --> 00:17:18,490 sehingga mereka melakukan beberapa benar-benar hal-hal gila kadang-kadang. 324 00:17:18,490 --> 00:17:20,960 Itu saja. 325 00:17:20,960 --> 00:17:22,140 Ada lagi? 326 00:17:22,140 --> 00:17:22,829 OK. 327 00:17:22,829 --> 00:17:24,480 >> Jadi tabrakan. 328 00:17:24,480 --> 00:17:29,270 Pada dasarnya, seperti yang saya katakan sebelumnya, dalam skenario kasus terbaik, 329 00:17:29,270 --> 00:17:32,040 setiap ember saya melihat ke dalam adalah akan memiliki satu hal, 330 00:17:32,040 --> 00:17:34,160 jadi saya tidak harus melihat sama sekali, kan? 331 00:17:34,160 --> 00:17:37,040 Aku juga tahu itu ada atau itu tidak, dan itulah apa yang kita inginkan. 332 00:17:37,040 --> 00:17:43,960 Tetapi jika kita memiliki puluhan ribu titik data dan kurang dari jumlah itu 333 00:17:43,960 --> 00:17:48,700 ember, kita akan memiliki tabrakan di mana akhirnya sesuatu 334 00:17:48,700 --> 00:17:54,210 akan harus berakhir di ember yang sudah memiliki unsur. 335 00:17:54,210 --> 00:17:57,390 >> Jadi pertanyaannya adalah, apa yang kita lakukan dalam kasus 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 memiliki sesuatu di sana? 338 00:17:59,300 --> 00:18:00,060 Apakah kita buang saja keluar? 339 00:18:00,060 --> 00:18:00,700 >> Tidak. 340 00:18:00,700 --> 00:18:01,980 Kami harus menjaga mereka berdua. 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 yang kami hanya berbicara tentang? 343 00:18:08,400 --> 00:18:09,316 AUDIENCE: Daftar Linked. 344 00:18:09,316 --> 00:18:10,500 SPEAKER 1: Sebuah linked list. 345 00:18:10,500 --> 00:18:16,640 Jadi sekarang, bukan masing-masing ember hanya memiliki satu elemen, 346 00:18:16,640 --> 00:18:24,020 itu akan berisi daftar link dari unsur-unsur yang hash ke dalamnya. 347 00:18:24,020 --> 00:18:27,588 OK, tidak semua orang mendapatkan semacam ide itu? 348 00:18:27,588 --> 00:18:30,546 Karena kita tidak bisa memiliki sebuah array karena kita tidak tahu berapa banyak hal 349 00:18:30,546 --> 00:18:31,730 akan berada di sana. 350 00:18:31,730 --> 00:18:36,540 Sebuah linked list memungkinkan kita untuk baru saja jumlah yang tepat yang 351 00:18:36,540 --> 00:18:38,465 adalah hash ke dalam ember itu, kan? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Jadi linear probing adalah pada dasarnya idea-- ini 354 00:18:50,500 --> 00:18:52,300 itu salah satu cara untuk menangani tabrakan. 355 00:18:52,300 --> 00:18:58,010 Apa yang dapat Anda lakukan adalah jika, dalam hal ini kasus, berry hash ke 1 356 00:18:58,010 --> 00:19:01,130 dan kita sudah memiliki sesuatu di sana, Anda hanya 357 00:19:01,130 --> 00:19:04,840 terus ke bawah sampai Anda menemukan 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 daftar disebut chaining. 361 00:19:12,280 --> 00:19:20,510 >> Jadi ide ini bekerja jika tabel hash Anda Anda berpikir 362 00:19:20,510 --> 00:19:24,150 jauh lebih besar daripada mengatur data Anda atau jika Anda 363 00:19:24,150 --> 00:19:28,870 ingin mencoba dan meminimalkan chaining sampai benar-benar diperlukan. 364 00:19:28,870 --> 00:19:34,050 Jadi satu hal yang linear menyelidik jelas berarti 365 00:19:34,050 --> 00:19:37,290 bahwa fungsi hash Anda tidak cukup berguna 366 00:19:37,290 --> 00:19:42,200 karena Anda akan berakhir dengan menggunakan fungsi hash Anda, sampai ke titik, 367 00:19:42,200 --> 00:19:46,400 Anda linier menyelidiki ke beberapa tempat yang tersedia. 368 00:19:46,400 --> 00:19:49,670 Tapi sekarang, tentu saja, apa pun lain yang berakhir di sana, 369 00:19:49,670 --> 00:19:52,050 Anda akan harus mencari lebih jauh ke bawah. 370 00:19:52,050 --> 00:19:55,650 >> Dan ada lebih banyak Beban penelusuran yang 371 00:19:55,650 --> 00:19:59,820 masuk ke memasukkan elemen dalam tabel hash Anda sekarang, kan? 372 00:19:59,820 --> 00:20:05,640 Dan sekarang ketika Anda pergi dan mencoba dan menemukan berry lagi, Anda akan hash itu, 373 00:20:05,640 --> 00:20:07,742 dan itu akan berkata, oh, lihat di ember 1, 374 00:20:07,742 --> 00:20:09,700 dan itu 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 banyak kasus, 377 00:20:17,720 --> 00:20:22,660 kita akan mengatakan bahwa chaining adalah apa yang ingin Anda lakukan. 378 00:20:22,660 --> 00:20:25,520 >> Jadi kita membicarakan hal ini sebelumnya. 379 00:20:25,520 --> 00:20:27,812 Aku punya depan sedikit diriku sendiri. 380 00:20:27,812 --> 00:20:33,560 Tapi chaining pada dasarnya yang setiap kotak dalam tabel hash Anda 381 00:20:33,560 --> 00:20:36,120 hanya linked list. 382 00:20:36,120 --> 00:20:39,660 >> Jadi cara lain, atau lebih teknis cara, untuk memikirkan tabel hash 383 00:20:39,660 --> 00:20:44,490 adalah bahwa itu hanya sebuah array dari daftar terkait, yang 384 00:20:44,490 --> 00:20:49,330 ketika Anda sedang menulis kamus Anda dan Anda mencoba untuk memuatnya, 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 membuatnya lebih mudah bagi Anda untuk inisialisasi. 387 00:20:54,390 --> 00:20:57,680 >> AUDIENCE: table Jadi hash memiliki ukuran yang telah ditentukan, 388 00:20:57,680 --> 00:20:58,980 seperti [tidak terdengar] ember? 389 00:20:58,980 --> 00:20:59,220 >> SPEAKER 1: Benar. 390 00:20:59,220 --> 00:21:01,655 Sehingga memiliki sejumlah set ember yang Anda determine-- 391 00:21:01,655 --> 00:21:03,530 yang kalian harus merasa bebas untuk bermain dengan. 392 00:21:03,530 --> 00:21:05,269 Hal ini dapat cukup keren untuk melihat apa yang terjadi 393 00:21:05,269 --> 00:21:06,810 ketika Anda mengubah nomor Anda dari ember. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Tapi ya, ia memiliki mengatur jumlah ember. 396 00:21:11,510 --> 00:21:15,360 Apa yang memungkinkan Anda untuk menyesuaikan sebagai banyak unsur yang Anda butuhkan 397 00:21:15,360 --> 00:21:19,350 adalah chaining terpisah ini di mana Anda telah menghubungkan daftar dalam setiap kotak. 398 00:21:19,350 --> 00:21:22,850 Itu berarti tabel hash Anda akan persis ukuran 399 00:21:22,850 --> 00:21:25,440 yang Anda butuhkan untuk menjadi, kan? 400 00:21:25,440 --> 00:21:27,358 Itulah inti dari daftar terkait. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Keren. 403 00:21:32,480 --> 00:21:38,780 >> Jadi setiap orang OK sana? 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 baru saja terjadi? 407 00:21:41,860 --> 00:21:42,960 Benar-benar sekarang. 408 00:21:42,960 --> 00:21:45,250 Tebak seseorang membunuh saya. 409 00:21:45,250 --> 00:21:52,060 >> OK kita akan pergi ke mencoba, yang sedikit gila. 410 00:21:52,060 --> 00:21:53,140 Saya suka tabel hash. 411 00:21:53,140 --> 00:21:54,460 Saya pikir mereka benar-benar keren. 412 00:21:54,460 --> 00:21:56,710 Tries keren, juga. 413 00:21:56,710 --> 00:21:59,590 >> Jadi tidak ada yang ingat apa dicoba adalah? 414 00:21:59,590 --> 00:22:01,740 Anda harus pergi lebih sebentar dalam kuliah? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Apakah Anda ingat jenis cara kerjanya? 417 00:22:06,377 --> 00:22:08,460 AUDIENCE: Aku hanya mengangguk bahwa kami 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 dari sekarang adalah apa yang kita katakan. 420 00:22:13,100 --> 00:22:14,860 >> AUDIENCE: 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 pohon pengambilan. 423 00:22:16,196 --> 00:22:16,960 Mengagumkan. 424 00:22:16,960 --> 00:22:23,610 Jadi satu hal untuk melihat di sini adalah bahwa kita akan mencari 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 sedang melihat kata-kata secara keseluruhan, 427 00:22:29,710 --> 00:22:32,270 dan sekarang kami sedang mencari lebih pada karakter, bukan? 428 00:22:32,270 --> 00:22:38,380 Jadi kita memiliki Maxwell di sini dan Mendel. 429 00:22:38,380 --> 00:22:47,840 Jadi pada dasarnya try-- cara untuk berpikir tentang ini adalah bahwa setiap tingkat di sini 430 00:22:47,840 --> 00:22:49,000 adalah array dari huruf. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Jadi ini adalah simpul akar Anda di sini, kan? 433 00:22:55,790 --> 00:23:01,980 Ini memiliki semua karakter dari alfabet untuk memulai setiap kata. 434 00:23:01,980 --> 00:23:06,480 >> Dan apa yang ingin Anda lakukan adalah mengatakan, OK, kita memiliki beberapa kata M. 435 00:23:06,480 --> 00:23:10,590 Kita akan mencari Maxwell, jadi kita pergi ke M. Dan M poin untuk keseluruhan 436 00:23:10,590 --> 00:23:14,800 lainnya array di mana setiap kata, selama ada 437 00:23:14,800 --> 00:23:17,044 adalah kata yang memiliki A sebagai huruf kedua, 438 00:23:17,044 --> 00:23:19,460 asalkan ada kata yang memiliki B sebagai huruf kedua, 439 00:23:19,460 --> 00:23:24,630 itu akan memiliki pointer pergi ke beberapa array yang berikutnya. 440 00:23:24,630 --> 00:23:29,290 >> Ada mungkin bukan kata yang MP sesuatu, 441 00:23:29,290 --> 00:23:32,980 sehingga pada posisi P dalam hal ini array, itu hanya akan menjadi NULL. 442 00:23:32,980 --> 00:23:38,840 Ini akan mengatakan, OK, tidak ada kata yang telah M diikuti oleh P, OK? 443 00:23:38,840 --> 00:23:43,100 Jadi jika kita berpikir tentang hal ini, masing-masing salah satu hal yang lebih kecil 444 00:23:43,100 --> 00:23:47,990 sebenarnya adalah 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 hal itu adalah jenis kelemahan dari mencoba? 446 00:23:55,064 --> 00:23:56,500 >> AUDIENCE: Banyak memori. 447 00:23:56,500 --> 00:23:59,940 >> SPEAKER 1: Ini satu ton memori, kan? 448 00:23:59,940 --> 00:24:08,750 Masing-masing blok ini di sini mewakili 26 ruang, 26 elemen array. 449 00:24:08,750 --> 00:24:13,680 Jadi mencoba mendapatkan sangat ruang berat. 450 00:24:13,680 --> 00:24:17,100 >> Tapi mereka sangat cepat. 451 00:24:17,100 --> 00:24:22,540 Jadi sangat cepat tetapi benar-benar ruang yang tidak efisien. 452 00:24:22,540 --> 00:24:24,810 Jenis harus mencari out mana yang Anda inginkan. 453 00:24:24,810 --> 00:24:29,470 Ini benar-benar keren untuk pset Anda, tetapi mereka mengambil banyak memori, 454 00:24:29,470 --> 00:24:30,290 sehingga Anda trade off. 455 00:24:30,290 --> 00:24:31,480 Ya? 456 00:24:31,480 --> 00:24:34,300 >> AUDIENCE: Apakah mungkin untuk mendirikan mencoba dan kemudian 457 00:24:34,300 --> 00:24:37,967 setelah Anda memiliki semua Data di dalamnya yang Anda need-- 458 00:24:37,967 --> 00:24:39,550 Saya tidak tahu apakah itu akan masuk akal. 459 00:24:39,550 --> 00:24:42,200 Aku menyingkirkan semua Karakter NULL, tapi 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 membutuhkan mereka. 462 00:24:43,275 --> 00:24:44,854 >> AUDIENCE: - dengan 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 membutuhkan karakter NULL untuk membiarkan Anda tahu apakah tidak ada kata di sana. 465 00:24:50,460 --> 00:24:52,040 Ben kau memiliki sesuatu yang Anda inginkan? 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 teknis di balik mencoba dan bekerja melalui contoh. 469 00:24:58,920 --> 00:25:01,490 >> OK, jadi ini adalah hal yang sama. 470 00:25:01,490 --> 00:25:06,290 Sedangkan dalam sebuah linked list, utama kami jenis of-- apa kata saya inginkan? - 471 00:25:06,290 --> 00:25:08,350 seperti membangun blok adalah sebuah node. 472 00:25:08,350 --> 00:25:12,280 Dalam mencoba, kami juga memiliki node, tapi itu didefinisikan secara berbeda. 473 00:25:12,280 --> 00:25:17,000 >> Jadi kita memiliki beberapa bool yang mewakili apakah kata benar-benar 474 00:25:17,000 --> 00:25:23,530 ada di lokasi ini, dan kemudian kami memiliki beberapa array yang di sini-atau lebih tepatnya, 475 00:25:23,530 --> 00:25:27,840 ini adalah pointer ke array 27 karakter. 476 00:25:27,840 --> 00:25:33,339 Dan ini adalah untuk, dalam hal ini, ini 27-- Saya yakin kalian semua seperti, tunggu, 477 00:25:33,339 --> 00:25:34,880 ada 26 huruf dalam alfabet. 478 00:25:34,880 --> 00:25:36,010 Mengapa kita memiliki 27? 479 00:25:36,010 --> 00:25:37,870 >> Jadi tergantung pada cara Anda menerapkan ini, 480 00:25:37,870 --> 00:25:43,240 ini adalah dari pset yang diperbolehkan untuk apostrof. 481 00:25:43,240 --> 00:25:46,010 Jadi itu sebabnya satu tambahan. 482 00:25:46,010 --> 00:25:50,500 Anda juga akan memiliki dalam beberapa kasus null terminator 483 00:25:50,500 --> 00:25:53,230 termasuk sebagai salah satu karakter yang itu boleh, 484 00:25:53,230 --> 00:25:56,120 dan itulah bagaimana mereka memeriksa untuk melihat apakah itu akhir kata. 485 00:25:56,120 --> 00:26:01,340 Jika Anda tertarik, check out Video Kevin di study.cs50, 486 00:26:01,340 --> 00:26:04,790 serta Wikipedia memiliki beberapa sumber daya yang baik di sana. 487 00:26:04,790 --> 00:26:09,000 >> Tapi kita akan pergi melalui hanya jenis bagaimana Anda dapat bekerja melalui mencoba 488 00:26:09,000 --> 00:26:11,010 jika Anda diberi satu. 489 00:26:11,010 --> 00:26:16,230 Jadi kita memiliki satu super sederhana di sini bahwa memiliki kata-kata "kelelawar" dan "zoom" di dalamnya. 490 00:26:16,230 --> 00:26:18,920 Dan seperti yang kita lihat di sini, ruang kecil ini di sini 491 00:26:18,920 --> 00:26:22,560 merupakan bool kami yang berkata, ya, ini adalah sebuah kata. 492 00:26:22,560 --> 00:26:27,060 Dan kemudian ini memiliki kami array karakter, kan? 493 00:26:27,060 --> 00:26:33,480 >> Jadi kita akan pergi melalui menemukan "kelelawar" dalam mencoba ini. 494 00:26:33,480 --> 00:26:38,340 Jadi mulai dari atas, kan? 495 00:26:38,340 --> 00:26:46,290 Dan kita tahu bahwa b sesuai dengan indeks kedua, elemen kedua 496 00:26:46,290 --> 00:26:47,840 dalam array ini, karena 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 mengatakan, OK, keren, mengikuti ke array berikutnya, karena jika kita ingat, 499 00:26:58,820 --> 00:27:02,160 bukan itu masing-masing sebenarnya mengandung elemen. 500 00:27:02,160 --> 00:27:07,110 Masing-masing dari array ini mengandung pointer, kan? 501 00:27:07,110 --> 00:27:10,030 Ini merupakan perbedaan penting untuk membuat. 502 00:27:10,030 --> 00:27:13,450 >> Saya tahu ini akan be-- mencoba adalah benar-benar sulit untuk mendapatkan pada pertama kalinya, 503 00:27:13,450 --> 00:27:15,241 sehingga bahkan jika ini adalah kedua atau ketiga kalinya 504 00:27:15,241 --> 00:27:18,370 dan itu masih baik dari tampak sulit, 505 00:27:18,370 --> 00:27:21,199 Aku berjanji jika Anda pergi menonton pendek lagi besok, 506 00:27:21,199 --> 00:27:22,740 mungkin akan membuat banyak lebih masuk akal. 507 00:27:22,740 --> 00:27:23,890 Dibutuhkan banyak untuk dicerna. 508 00:27:23,890 --> 00:27:27,800 Saya masih kadang-kadang saya seperti, tunggu, apa coba? 509 00:27:27,800 --> 00:27:29,080 Bagaimana cara menggunakan ini? 510 00:27:29,080 --> 00:27:33,880 >> Jadi kita telah b dalam kasus ini, yang merupakan indeks kedua kami. 511 00:27:33,880 --> 00:27:40,240 Jika kita memiliki, katakanlah, c atau d atau surat lainnya, 512 00:27:40,240 --> 00:27:45,810 kita perlu memetakan bahwa kembali ke indeks array kita bahwa yang sesuai dengan. 513 00:27:45,810 --> 00:27:56,930 Jadi kita akan mengambil seperti rchar dan kami hanya kurangi off untuk memetakan menjadi 0-25. 514 00:27:56,930 --> 00:27:58,728 Semua orang yang baik bagaimana kita memetakan karakter 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 kami melihat bahwa, ya, itu tidak NULL. 517 00:28:05,980 --> 00:28:07,780 Kita bisa melanjutkan ke array yang berikutnya ini. 518 00:28:07,780 --> 00:28:12,300 Jadi kami pergi ke array yang berikutnya ini di sini. 519 00:28:12,300 --> 00:28:15,500 >> Dan kita katakan, OK, sekarang kita perlu untuk melihat apakah ada di sini. 520 00:28:15,500 --> 00:28:18,590 Apakah Sebuah nol atau apakah itu sebenarnya bergerak maju? 521 00:28:18,590 --> 00:28:21,880 Jadi benar-benar bergerak maju dalam array ini. 522 00:28:21,880 --> 00:28:24,570 Dan kita katakan, OK, t adalah huruf terakhir kami. 523 00:28:24,570 --> 00:28:27,580 Jadi kami pergi ke t pada indeks. 524 00:28:27,580 --> 00:28:30,120 Dan kemudian kita bergerak maju karena ada satu lagi. 525 00:28:30,120 --> 00:28:38,340 Dan yang satu ini pada dasarnya mengatakan bahwa, ya, ia mengatakan bahwa ada sebuah kata di sini- 526 00:28:38,340 --> 00:28:41,750 bahwa jika Anda mengikuti ini jalan, Anda telah tiba 527 00:28:41,750 --> 00:28:43,210 di kata, yang kita tahu adalah "kelelawar." 528 00:28:43,210 --> 00:28:43,800 Ya? 529 00:28:43,800 --> 00:28:46,770 >> AUDIENCE: Apakah standar untuk memiliki indeks 0 dan kemudian memiliki semacam pada 1 530 00:28:46,770 --> 00:28:47,660 atau untuk memiliki akhir? 531 00:28:47,660 --> 00:28:48,243 >> SPEAKER 1: No. 532 00:28:48,243 --> 00:28:55,360 Jadi jika kita melihat kembali pada kami deklarasi di sini, itu bool, 533 00:28:55,360 --> 00:28:59,490 jadi elemen sendiri dalam node. 534 00:28:59,490 --> 00:29:03,331 Jadi bukan bagian dari array. 535 00:29:03,331 --> 00:29:03,830 Keren. 536 00:29:03,830 --> 00:29:08,370 Jadi ketika kita selesai kata kami dan kami di array ini, apa yang ingin kita lakukan 537 00:29:08,370 --> 00:29:12,807 adalah melakukan pemeriksaan adalah ini sebuah kata. 538 00:29:12,807 --> 00:29:14,390 Dan dalam hal ini, itu akan kembali ya. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Jadi pada catatan, kita tahu bahwa "kebun binatang" - kita kenal sebagai manusia bahwa "kebun binatang" adalah sebuah kata, 541 00:29:24,090 --> 00:29:24,820 kan? 542 00:29:24,820 --> 00:29:28,990 Tetapi coba di sini akan mengatakan, tidak, itu tidak. 543 00:29:28,990 --> 00:29:33,980 Dan itu akan mengatakan bahwa karena kita belum ditunjuk sebagai kata di sini. 544 00:29:33,980 --> 00:29:40,440 Meskipun kita dapat melintasi melalui array ini, 545 00:29:40,440 --> 00:29:43,890 mencoba ini akan mengatakan bahwa, tidak, kebun binatang tidak ada dalam kamus Anda 546 00:29:43,890 --> 00:29:47,070 karena kita belum ditunjuk seperti itu. 547 00:29:47,070 --> 00:29:52,870 >> Jadi salah satu cara untuk melakukan itu-- oh, maaf, yang satu ini. 548 00:29:52,870 --> 00:29:59,450 Jadi dalam hal ini, "kebun binatang" tidak kata, tetapi dalam try kami. 549 00:29:59,450 --> 00:30:05,690 Tapi dalam satu ini, katakanlah kita ingin memperkenalkan kata "mandi," apa yang terjadi 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 berada di array ini, dan kita pergi untuk mencari h. 552 00:30:11,820 --> 00:30:15,220 >> Dalam hal ini, ketika kita melihat pointer pada 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 secara eksplisit menunjuk ke array lain, 555 00:30:20,780 --> 00:30:25,000 Anda berasumsi bahwa semua pointer dalam array ini menunjuk ke null. 556 00:30:25,000 --> 00:30:28,270 Jadi dalam hal ini, h menunjuk untuk null jadi kami tidak bisa berbuat apa-apa, 557 00:30:28,270 --> 00:30:31,540 sehingga juga akan kembali palsu, "mandi" tidak 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 bahwa "kebun binatang" di try kita. 561 00:30:39,790 --> 00:30:42,920 Bagaimana kita masukkan "kebun binatang" dalam mencoba 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, mulai dari akar hal-hal ini. 564 00:30:50,600 --> 00:30:53,330 >> Dan kita akan mengatakan, OK, z. 565 00:30:53,330 --> 00:30:55,650 z ada dalam hal ini, dan itu tidak. 566 00:30:55,650 --> 00:30:58,370 Jadi Anda pindah ke array berikutnya, OK? 567 00:30:58,370 --> 00:31:01,482 Dan kemudian pada yang berikutnya, kita katakan, OK, apakah o ada? 568 00:31:01,482 --> 00:31:03,000 Itu tidak. 569 00:31:03,000 --> 00:31:04,330 Ini lagi. 570 00:31:04,330 --> 00:31:08,670 >> Dan seterusnya satu kami berikutnya, kami katakan, OK, "kebun binatang" sudah ada di sini. 571 00:31:08,670 --> 00:31:12,440 Semua yang perlu kita lakukan adalah mengatur hal ini sama true, bahwa ada sebuah kata di sana. 572 00:31:12,440 --> 00:31:15,260 Jika Anda telah mengikuti semua sampai sebelum titik itu, 573 00:31:15,260 --> 00:31:17,030 itu kata, jadi hanya mengaturnya sama dengan itu. 574 00:31:17,030 --> 00:31:17,530 Ya? 575 00:31:17,530 --> 00:31:22,550 >> AUDIENCE: Jadi apakah itu berarti bahwa "ba" adalah kata 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 itu sebuah kata, 578 00:31:28,870 --> 00:31:31,590 dan masih akan 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 >> AUDIENCE: Jadi setelah Anda apakah itu kata dan Anda menjawab ya, maka 582 00:31:36,360 --> 00:31:38,380 akan berisi 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 "kebun binatang" adalah sebuah kata. 585 00:31:43,640 --> 00:31:47,020 Ketika Anda pergi ke check-- seperti, katakanlah Anda ingin mengatakan, 586 00:31:47,020 --> 00:31:49,400 tidak "kebun binatang" yang ada dalam kamus ini? 587 00:31:49,400 --> 00:31:54,200 Anda hanya akan mencari "kebun binatang," dan kemudian memeriksa untuk melihat apakah itu sebuah kata. 588 00:31:54,200 --> 00:31:57,291 Anda tidak akan pernah bergerak melalui m karena itulah tidak 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 ingin menambahkan "mandi" dalam mencoba ini, 592 00:32:08,070 --> 00:32:11,390 kami akan melakukan hal yang sama seperti yang kita lakukan dengan "kebun binatang," 593 00:32:11,390 --> 00:32:15,380 kecuali kita akan melihat bahwa ketika kita mencoba dan mendapatkan h, itu tidak ada. 594 00:32:15,380 --> 00:32:20,090 Sehingga Anda dapat menganggap ini sebagai mencoba untuk menambahkan node baru ke dalam linked list, 595 00:32:20,090 --> 00:32:27,210 jadi kita akan perlu menambahkan lain salah satu array tersebut, seperti begitu. 596 00:32:27,210 --> 00:32:35,670 Dan kemudian apa yang kita lakukan adalah kita hanya mengatur h elemen dari array ini menunjuk ke 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 Tambahkan sama dengan benar karena itu kata. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Keren. 601 00:32:48,150 --> 00:32:48,700 Aku tahu. 602 00:32:48,700 --> 00:32:51,170 Mencoba tidak 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 hal untuk mewujudkan dengan mencoba, Aku berkata, mereka sangat efisien. 605 00:32:58,040 --> 00:33:00,080 Jadi kita telah melihat mereka mengambil satu ton 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 karena mereka sangat efisien. 609 00:33:05,450 --> 00:33:08,130 >> Jadi jika Anda pernah melihat sebuah 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 kata yang panjang lima, 612 00:33:15,210 --> 00:33:20,940 Anda hanya pernah akan harus membuat paling banyak lima perbandingan, OK? 613 00:33:20,940 --> 00:33:25,780 Sehingga membuatnya pada dasarnya konstan. 614 00:33:25,780 --> 00:33:29,150 Seperti penyisipan dan pencarian pada dasarnya waktu yang konstan. 615 00:33:29,150 --> 00:33:33,750 >> Jadi, jika Anda pernah bisa mendapatkan sesuatu dalam waktu yang konstan, 616 00:33:33,750 --> 00:33:35,150 itu sebagai baik karena mendapat. 617 00:33:35,150 --> 00:33:37,990 Anda tidak bisa lebih baik daripada waktu yang konstan untuk hal-hal ini. 618 00:33:37,990 --> 00:33:43,150 Jadi itu adalah salah satu Plus besar mencoba. 619 00:33:43,150 --> 00:33:46,780 >> Tapi itu adalah banyak ruang. 620 00:33:46,780 --> 00:33:50,380 Jadi Anda jenis harus memutuskan apa yang lebih penting bagi Anda. 621 00:33:50,380 --> 00:33:54,700 Dan pada komputer saat ini, ruang yang mencoba bisa memakan waktu hingga 622 00:33:54,700 --> 00:33:57,740 mungkin tidak mempengaruhi Anda bahwa banyak, tapi mungkin 623 00:33:57,740 --> 00:34:01,350 Anda sedang berhadapan dengan sesuatu yang memiliki jauh, jauh lebih banyak hal, 624 00:34:01,350 --> 00:34:02,810 dan mencoba hanya tidak masuk akal. 625 00:34:02,810 --> 00:34:03,000 Ya? 626 00:34:03,000 --> 00:34:05,610 >> AUDIENCE: Tunggu, sehingga Anda memiliki 26 huruf dalam setiap satu? 627 00:34:05,610 --> 00:34:07,440 >> SPEAKER 1: Mmhmm. 628 00:34:07,440 --> 00:34:08,570 Ya, Anda memiliki 26. 629 00:34:08,570 --> 00:34:16,984 Anda memiliki beberapa adalah penanda kata dan kemudian Anda memiliki 26 pointer dalam setiap orang. 630 00:34:16,984 --> 00:34:17,775 Dan mereka point-- 631 00:34:17,775 --> 00:34:20,280 >> AUDIENCE: Dan setiap 26, apakah mereka masing-masing memiliki 26? 632 00:34:20,280 --> 00:34:21,500 >> SPEAKER 1: Ya. 633 00:34:21,500 --> 00:34:27,460 Dan itulah mengapa, yang Anda bisa lihat, 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 pohon, yang Saya merasa seperti lebih mudah dan mungkin akan 636 00:34:32,524 --> 00:34:36,150 menjadi penangguhan hukuman kecil yang bagus dari mencoba sana. 637 00:34:36,150 --> 00:34:39,620 Jadi mudah-mudahan sebagian besar dari Anda 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 pergi di luar ruangan baru-baru ini. 640 00:34:44,340 --> 00:34:49,230 Aku pergi memetik apel akhir pekan ini, dan oh my gosh, itu indah. 641 00:34:49,230 --> 00:34:52,250 Aku tidak tahu daun bisa melihat bahwa cantik. 642 00:34:52,250 --> 00:34:53,610 >> Jadi ini hanya pohon, kan? 643 00:34:53,610 --> 00:34:56,790 Ini hanyalah beberapa node, dan menunjuk ke sekelompok node 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 Node menunjuk ke node adalah jenis esensi dari banyak struktur data. 646 00:35:03,720 --> 00:35:06,670 Ini tergantung pada bagaimana kita memiliki mereka menunjuk ke 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 menyisipkan hal-hal yang menentukan karakteristik yang berbeda mereka. 649 00:35:14,500 --> 00:35:17,600 >> Jadi hanya beberapa terminologi, yang saya gunakan sebelumnya. 650 00:35:17,600 --> 00:35:20,010 Jadi akar apa saja yang di bagian paling atas. 651 00:35:20,010 --> 00:35:21,200 itu adalah di mana kita selalu mulai. 652 00:35:21,200 --> 00:35:23,610 Anda dapat menganggapnya sebagai kepala juga. 653 00:35:23,610 --> 00:35:28,750 Tapi untuk pohon, kita cenderung untuk menyebutnya sebagai root. 654 00:35:28,750 --> 00:35:32,820 >> Apa-apa di sini-bawah di sangat, sangat bottom-- 655 00:35:32,820 --> 00:35:34,500 daun dipertimbangkan. 656 00:35:34,500 --> 00:35:37,210 Jadi sejalan dengan Semuanya pohon, kan? 657 00:35:37,210 --> 00:35:39,860 Daun berada di tepi pohon Anda. 658 00:35:39,860 --> 00:35:45,820 >> Dan kemudian kami juga memiliki beberapa istilah untuk berbicara tentang node dalam kaitannya 659 00:35:45,820 --> 00:35:46,680 satu sama lain. 660 00:35:46,680 --> 00:35:49,700 Jadi kita memiliki orang tua, anak-anak, dan saudara kandung. 661 00:35:49,700 --> 00:35:56,260 Jadi dalam hal ini, 3 adalah induk dari 5, 6, dan 7. 662 00:35:56,260 --> 00:36:00,370 Jadi orang tua adalah apa pun yang satu langkah di atas apa pun yang Anda 663 00:36:00,370 --> 00:36:02,940 maksud, jadi hanya seperti pohon keluarga. 664 00:36:02,940 --> 00:36:07,090 Mudah-mudahan, ini semua sedikit sebuah sedikit lebih intuitif daripada mencoba. 665 00:36:07,090 --> 00:36:10,970 >> Saudara adalah setiap yang memiliki induk yang sama, kan? 666 00:36:10,970 --> 00:36:13,470 Mereka berada di tingkat yang sama di sini. 667 00:36:13,470 --> 00:36:16,960 Dan kemudian, karena aku mengatakan, anak-anak hanya 668 00:36:16,960 --> 00:36:22,630 apa adalah salah satu langkah di bawah ini node tersebut, OK? 669 00:36:22,630 --> 00:36:23,470 Keren. 670 00:36:23,470 --> 00:36:25,610 Jadi pohon biner. 671 00:36:25,610 --> 00:36:31,450 Adakah yang bisa menebak di salah satu karakteristik pohon biner? 672 00:36:31,450 --> 00:36:32,770 >> AUDIENCE: 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 satu ini sebelumnya, kami memiliki satu ini yang memiliki tiga, tetapi dalam pohon biner, 676 00:36:39,730 --> 00:36:45,000 Anda memiliki maksimal dua anak per induk, kan? 677 00:36:45,000 --> 00:36:46,970 Ada satu lagi Karakteristik yang menarik. 678 00:36:46,970 --> 00:36:51,550 Apakah ada yang tahu itu? 679 00:36:51,550 --> 00:36:52,620 Pohon biner. 680 00:36:52,620 --> 00:37:00,350 >> Jadi pohon biner akan memiliki segalanya pada the-- satu ini tidak sorted-- 681 00:37:00,350 --> 00:37:05,320 tetapi dalam pohon biner diurutkan, semua yang ada di sebelah kanan 682 00:37:05,320 --> 00:37:08,530 lebih besar dari orang tua, dan segala sesuatu di sebelah kiri 683 00:37:08,530 --> 00:37:10,035 kurang dari orangtua. 684 00:37:10,035 --> 00:37:15,690 Dan yang telah kuis pertanyaan sebelumnya, jadi baik untuk tahu. 685 00:37:15,690 --> 00:37:19,500 Jadi cara kita mendefinisikan ini, lagi, kita memiliki node lain. 686 00:37:19,500 --> 00:37:21,880 Hal ini terlihat sangat mirip 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 >> AUDIENCE: Linked daftar 690 00:37:29,320 --> 00:37:31,100 >> SPEAKER 1: Sebuah linked list ganda, kan? 691 00:37:31,100 --> 00:37:33,690 Jadi jika kita mengganti ini dengan sebelumnya dan berikutnya, 692 00:37:33,690 --> 00:37:35,670 ini akan menjadi daftar ganda terkait. 693 00:37:35,670 --> 00:37:40,125 Tapi dalam kasus ini, kita benar-benar memiliki kiri dan kanan dan hanya itu. 694 00:37:40,125 --> 00:37:41,500 Jika tidak, itu persis sama. 695 00:37:41,500 --> 00:37:43,374 Kami masih memiliki elemen Anda sedang mencari, 696 00:37:43,374 --> 00:37:45,988 dan Anda hanya memiliki dua pointer akan apa pun yang berikutnya. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Ya, pohon pencarian biner begitu. 699 00:37:51,870 --> 00:37:57,665 Jika kita perhatikan, semua yang ada di di sini adalah than-- lebih besar 700 00:37:57,665 --> 00:37:59,850 atau segala sesuatu yang segera ke kanan di sini 701 00:37:59,850 --> 00:38:02,840 lebih besar dari, segala sesuatu di sini kurang dari. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Jadi jika kita mencari melalui, itu harus terlihat sangat dekat dengan pencarian biner 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 setengah array, 706 00:38:17,640 --> 00:38:21,720 kita hanya melihat baik kiri samping atau sisi kanan pohon. 707 00:38:21,720 --> 00:38:24,850 Sehingga mendapat sedikit lebih sederhana, saya pikir. 708 00:38:24,850 --> 00:38:29,300 >> Jadi jika root anda adalah NULL, jelas itu 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 itu kurang dari, kita mencari kiri. 711 00:38:35,320 --> 00:38:37,070 Jika itu lebih besar dari, kita mencari kanan. 712 00:38:37,070 --> 00:38:39,890 Ini persis seperti pencarian biner, hanya struktur data yang berbeda 713 00:38:39,890 --> 00:38:40,600 bahwa kita sedang menggunakan. 714 00:38:40,600 --> 00:38:42,790 Alih-alih sebuah array, itu hanya sebuah pohon biner. 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, sepertinya kita mungkin memiliki sedikit waktu. 718 00:38:51,550 --> 00:38:54,460 Jika kita lakukan, saya senang untuk pergi lebih dari semua 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-- setiap karakteristik stack? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, jadi kebanyakan dari kita, saya pikir, makan di makan halls-- 723 00:39:10,400 --> 00:39:13,100 sebanyak yang kita mungkin tidak suka. 724 00:39:13,100 --> 00:39:16,900 Tapi jelas, Anda bisa memikirkan stack benar-benar hanya sebagai tumpukan nampan 725 00:39:16,900 --> 00:39:18,460 atau setumpuk hal. 726 00:39:18,460 --> 00:39:21,820 Dan apa yang penting untuk menyadari adalah bahwa hal itu 727 00:39:21,820 --> 00:39:26,850 something-- karakteristik bahwa kita menyebutnya by-- adalah LIFO. 728 00:39:26,850 --> 00:39:28,450 Apakah ada yang tahu apa yang berdiri untuk? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> AUDIENCE: Terakhir, 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 hal-hal up, hal yang paling mudah untuk ambil off-- 733 00:39:36,585 --> 00:39:39,570 dan mungkin satu-satunya hal yang kita bisa ambil off jika tumpukan kami adalah enough-- besar 734 00:39:39,570 --> 00:39:40,850 adalah bahwa unsur atas. 735 00:39:40,850 --> 00:39:43,460 Jadi apa pun yang diletakkan di last-- seperti yang kita lihat di sini, 736 00:39:43,460 --> 00:39:46,370 apa pun yang mendorong pada kebanyakan recently-- adalah 737 00:39:46,370 --> 00:39:51,160 akan menjadi yang pertama hal yang kita pop off, OK? 738 00:39:51,160 --> 00:39:56,324 >> Jadi apa yang kita miliki di sini adalah struct typedef lain. 739 00:39:56,324 --> 00:39:58,740 Ini benar-benar hanya seperti kecelakaan saja dalam struktur data, 740 00:39:58,740 --> 00:40:01,650 sehingga ada banyak dilemparkan pada kalian. 741 00:40:01,650 --> 00:40:02,540 Aku 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 hal ini, itu adalah beberapa pointer ke array yang memiliki beberapa kapasitas. 745 00:40:16,660 --> 00:40:20,830 Jadi ini merupakan tumpukan kami di sini, seperti array kita sebenarnya 746 00:40:20,830 --> 00:40:22,520 yang memegang elemen kami. 747 00:40:22,520 --> 00:40:24,850 Dan maka di sini kita memiliki beberapa ukuran. 748 00:40:24,850 --> 00:40:31,170 >> Dan biasanya, Anda ingin menyimpan melacak seberapa besar tumpukan Anda 749 00:40:31,170 --> 00:40:36,180 karena apa yang akan memungkinkan Anda lakukan adalah jika Anda tahu ukuran, 750 00:40:36,180 --> 00:40:39,170 memungkinkan Anda untuk mengatakan, OK, aku pada kapasitas? 751 00:40:39,170 --> 00:40:40,570 Apakah saya dapat menambahkan sesuatu yang lebih? 752 00:40:40,570 --> 00:40:44,650 Dan itu juga memberitahu Anda di mana bagian atas tumpukan Anda 753 00:40:44,650 --> 00:40:48,180 sehingga Anda tahu apa yang Anda benar-benar bisa lepas landas. 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 push, satu hal, jika Anda pernah untuk melaksanakan dorong, 756 00:40:57,350 --> 00:41:01,330 karena saya hanya mengatakan, Anda tumpukan memiliki ukuran terbatas, kan? 757 00:41:01,330 --> 00:41:03,990 Array kita memiliki beberapa kapasitas. 758 00:41:03,990 --> 00:41:04,910 Ini sebuah array. 759 00:41:04,910 --> 00:41:08,930 Ini adalah ukuran yang tetap, jadi kita perlu memastikan bahwa kita tidak menempatkan lebih 760 00:41:08,930 --> 00:41:11,950 ke array kita daripada kita benar-benar memiliki ruang untuk. 761 00:41:11,950 --> 00:41:16,900 >> Jadi, ketika Anda sedang menciptakan dorongan fungsi, hal pertama yang Anda lakukan adalah mengatakan, OK, 762 00:41:16,900 --> 00:41:18,570 apakah saya memiliki ruang dalam tumpukan saya? 763 00:41:18,570 --> 00:41:23,330 Karena jika saya tidak melakukannya, maaf, Saya tidak bisa menyimpan elemen Anda. 764 00:41:23,330 --> 00:41:28,980 Jika saya melakukannya, maka Anda ingin menyimpan di bagian atas tumpukan, kan? 765 00:41:28,980 --> 00:41:31,325 >> Dan ini adalah mengapa kita memiliki untuk melacak ukuran kami. 766 00:41:31,325 --> 00:41:35,290 Jika kita tidak melacak ukuran kami, kita tidak tahu di mana harus menaruhnya. 767 00:41:35,290 --> 00:41:39,035 Kita tidak tahu berapa banyak hal berada dalam array kita sudah. 768 00:41:39,035 --> 00:41:41,410 Seperti jelas ada cara yang mungkin Anda bisa melakukannya. 769 00:41:41,410 --> 00:41:44,610 Anda bisa menginisialisasi segalanya untuk NULL dan kemudian memeriksa NULL terbaru, 770 00:41:44,610 --> 00:41:47,950 tapi hal yang jauh lebih mudah hanya mengatakan, OK, melacak ukuran. 771 00:41:47,950 --> 00:41:51,840 Seperti saya tahu saya memiliki empat elemen dalam array saya, jadi hal berikutnya 772 00:41:51,840 --> 00:41:55,930 yang kita pasang di, kami akan menyimpan di indeks 4. 773 00:41:55,930 --> 00:42:00,940 Dan kemudian, tentu saja, ini berarti bahwa Anda telah berhasil mendorong sesuatu 774 00:42:00,940 --> 00:42:03,320 ke stack Anda, Anda ingin meningkatkan ukuran 775 00:42:03,320 --> 00:42:08,880 sehingga Anda tahu di mana Anda begitu bahwa Anda dapat mendorong lebih banyak hal di. 776 00:42:08,880 --> 00:42:12,730 >> Jadi jika kita mencoba untuk pop sesuatu dari tumpukan, 777 00:42:12,730 --> 00:42:16,072 apa yang mungkin menjadi hal pertama bahwa kita ingin memeriksa? 778 00:42:16,072 --> 00:42:18,030 Anda mencoba untuk mengambil sesuatu dari tumpukan Anda. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Apakah Anda yakin 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 ingin memeriksa? 783 00:42:26,894 --> 00:42:27,810 >> AUDIENCE: [tak terdengar]. 784 00:42:27,810 --> 00:42:29,880 SPEAKER 1: Periksa ukuran? 785 00:42:29,880 --> 00:42:31,840 Ukuran. 786 00:42:31,840 --> 00:42:38,520 Jadi kami ingin memeriksa untuk melihat apakah ukuran kami lebih besar dari 0, OK? 787 00:42:38,520 --> 00:42:44,970 Dan jika sudah, maka kita ingin menurunkan Ukuran kami dengan 0 dan kembali itu. 788 00:42:44,970 --> 00:42:45,840 Mengapa? 789 00:42:45,840 --> 00:42:49,950 >> Dalam yang pertama kami mendorong, kami mendorongnya 790 00:42:49,950 --> 00:42:52,460 ke ukuran dan ukuran kemudian diperbarui. 791 00:42:52,460 --> 00:42:57,850 Dalam hal ini, kita decrementing ukuran dan kemudian mengambil it off, mencabut itu 792 00:42:57,850 --> 00:42:58,952 dari array kita. 793 00:42:58,952 --> 00:42:59,826 Mengapa kita bisa melakukannya? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Jadi jika saya memiliki satu hal di stack saya, apa yang akan menjadi ukuran saya pada saat 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 AUDIENCE: 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 selalu perlu untuk membuat sure-- 802 00:43:22,800 --> 00:43:27,630 bukannya kembali ukuran minus 1, karena kita 803 00:43:27,630 --> 00:43:31,730 tahu bahwa elemen kita akan disimpan pada 1 kurang 804 00:43:31,730 --> 00:43:34,705 apa pun ukuran kami, ini hanya mengurus itu. 805 00:43:34,705 --> 00:43:36,080 Ini adalah cara yang sedikit lebih elegan. 806 00:43:36,080 --> 00:43:41,220 Dan kita hanya pengurangan kami ukuran dan kemudian kembali ukuran. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> AUDIENCE: Saya kira hanya secara umum, mengapa struktur data 809 00:43:45,300 --> 00:43:47,800 bermanfaat? 810 00:43:47,800 --> 00:43:50,660 >> SPEAKER 1: Hal ini tergantung pada 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 biarkan aku melihat apakah ada yang menguntungkan yang bermanfaat bagi lebih dari luar 813 00:44:02,750 --> 00:44:05,420 CS. 814 00:44:05,420 --> 00:44:15,780 Dengan tumpukan, setiap kali Anda perlu untuk melacak sesuatu yang 815 00:44:15,780 --> 00:44:20,456 adalah yang paling baru ditambahkan adalah ketika Anda akan ingin menggunakan stack. 816 00:44:20,456 --> 00:44:24,770 >> Dan aku tidak bisa memikirkan suatu barang contoh yang sekarang. 817 00:44:24,770 --> 00:44:29,955 Tapi setiap kali terbaru hal yang paling penting bagi Anda, 818 00:44:29,955 --> 00:44:31,705 saat itulah setumpuk akan menjadi berguna. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Saya mencoba untuk berpikir jika ada satu yang baik untuk ini. 821 00:44:39,330 --> 00:44:43,720 Jika saya memikirkan contoh yang baik di akhirat 20 menit, saya pasti akan memberitahu Anda. 822 00:44:43,720 --> 00:44:49,455 >> Tapi secara keseluruhan, jika ada apa-apa, seperti saya katakan sebagian besar, di mana terbaru 823 00:44:49,455 --> 00:44:52,470 yang paling penting, yang mana stack datang ke dalam bermain. 824 00:44:52,470 --> 00:44:58,860 Sedangkan antrian adalah jenis 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 bagus, kan? 827 00:45:00,890 --> 00:45:03,299 Saya merasa seperti saya harus hanya memiliki video kelinci 828 00:45:03,299 --> 00:45:05,090 tepat di tengah-tengah bagian untuk kalian 829 00:45:05,090 --> 00:45:08,870 karena ini adalah bagian yang intens. 830 00:45:08,870 --> 00:45:10,480 >> Jadi antrian. 831 00:45:10,480 --> 00:45:12,710 Pada dasarnya antrian seperti garis. 832 00:45:12,710 --> 00:45:15,780 Kalian Saya yakin penggunaan sehari-hari ini, hanya seperti di ruang makan kami. 833 00:45:15,780 --> 00:45:18,160 Jadi kita harus pergi di dan mendapatkan nampan kami, aku 834 00:45:18,160 --> 00:45:21,260 Pastikan Anda harus menunggu dalam antrean menggesek atau mendapatkan makanan Anda. 835 00:45:21,260 --> 00:45:24,650 >> Jadi perbedaan di sini adalah bahwa ini adalah FIFO. 836 00:45:24,650 --> 00:45:30,090 Jadi jika LIFO terakhir di, pertama out, FIFO adalah pertama, keluar pertama. 837 00:45:30,090 --> 00:45:33,400 Jadi ini adalah di mana apa pun 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-- kaleng 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 itu tumpukan di mana orang terakhir di garis mendapatkannya pertama, 841 00:45:42,800 --> 00:45:44,160 orang akan membunuh satu sama lain. 842 00:45:44,160 --> 00:45:49,800 >> Jadi FIFO, kita semua sangat akrab dengan di dunia nyata di sini, 843 00:45:49,800 --> 00:45:54,930 dan itu semua harus dilakukan dengan benar-benar jenis menciptakan seluruh baris ini 844 00:45:54,930 --> 00:45:56,900 dan antrian struktur. 845 00:45:56,900 --> 00:46:02,390 Jadi sedangkan dengan tumpukan, kami memiliki dorongan dan pop. 846 00:46:02,390 --> 00:46:06,440 Dengan antrian, kami memiliki enqueue dan dequeue. 847 00:46:06,440 --> 00:46:10,910 Jadi enqueue pada dasarnya berarti memasukkannya ke belakang, 848 00:46:10,910 --> 00:46:13,680 dan sarana dequeue mengambil 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 memiliki hal yang kedua untuk melacak. 851 00:46:21,060 --> 00:46:25,950 >> Jadi tanpa kepala, ini adalah persis tumpukan, kan? 852 00:46:25,950 --> 00:46:27,900 Ini adalah struktur yang sama seperti stack. 853 00:46:27,900 --> 00:46:32,480 Satu-satunya hal yang berbeda sekarang adalah kita memiliki kepala ini, yang apa yang Anda pikirkan 854 00:46:32,480 --> 00:46:34,272 akan melacak? 855 00:46:34,272 --> 00:46:35,510 >> AUDIENCE: Yang pertama. 856 00:46:35,510 --> 00:46:38,685 >> SPEAKER 1: Benar, yang Hal pertama yang kita masukkan ke dalam. 857 00:46:38,685 --> 00:46:41,130 Kepala antrian 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 salah satu struktur data, 863 00:46:55,920 --> 00:46:59,760 karena kita sedang berhadapan dengan sebuah array, kita perlu memeriksa apakah kita memiliki ruang. 864 00:46:59,760 --> 00:47:03,290 >> Ini adalah jenis seperti saya mengatakan kalian, jika Anda membuka file, 865 00:47:03,290 --> 00:47:04,760 Anda perlu memeriksa null. 866 00:47:04,760 --> 00:47:08,330 Dengan salah satu tumpukan ini dan antrian, Anda perlu 867 00:47:08,330 --> 00:47:13,420 untuk melihat apakah ada ruang karena kita berurusan dengan ukuran array tetap, 868 00:47:13,420 --> 00:47:16,030 seperti yang kita lihat di sini-0, 1 semua sampai 5. 869 00:47:16,030 --> 00:47:20,690 Jadi apa yang kita lakukan dalam hal ini adalah memeriksa untuk melihat apakah kita masih memiliki ruang. 870 00:47:20,690 --> 00:47:23,110 Apakah ukuran kami kurang dari kapasitas? 871 00:47:23,110 --> 00:47:28,480 >> Jika demikian, kita perlu menyimpannya di ekor dan kami memperbarui ukuran kami. 872 00:47:28,480 --> 00:47:30,250 Jadi apa yang mungkin ekor dalam kasus ini? 873 00:47:30,250 --> 00:47:32,360 Ini tidak secara eksplisit ditulis. 874 00:47:32,360 --> 00:47:33,380 Bagaimana kita akan menyimpannya? 875 00:47:33,380 --> 00:47:34,928 Apa yang akan ekor itu? 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 array dari ukuran 6, kan? 879 00:47:44,590 --> 00:47:49,220 Dan kita miliki sekarang, ukuran kami adalah 5. 880 00:47:49,220 --> 00:47:55,240 Dan ketika kita memasukkannya ke dalam, itu akan untuk masuk ke 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 >> Cara lain untuk menulis ekor akan hanya menjadi array kita di indeks ukuran, kan? 883 00:48:05,600 --> 00:48:07,560 Ini adalah ukuran 5. 884 00:48:07,560 --> 00:48:11,490 Hal berikutnya yang akan masuk ke 5. 885 00:48:11,490 --> 00:48:12,296 Keren? 886 00:48:12,296 --> 00:48:13,290 OK. 887 00:48:13,290 --> 00:48:16,350 Ia mendapat sedikit lebih rumit ketika kita mulai bermain-main dengan kepala. 888 00:48:16,350 --> 00:48:17,060 Ya? 889 00:48:17,060 --> 00:48:20,090 >> AUDIENCE: Apakah itu berarti bahwa kita akan menyatakan sebuah array yang 890 00:48:20,090 --> 00:48:23,880 adalah lima elemen panjang dan kemudian kita 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 stack. 893 00:48:27,560 --> 00:48:31,760 Hal ini akan dinyatakan sebagai array dari ukuran 6. 894 00:48:31,760 --> 00:48:37,120 Dan dalam hal ini, kita hanya memiliki satu kiri ruang. 895 00:48:37,120 --> 00:48:42,720 >> OK, jadi satu hal yang dalam hal ini kasus, jika kepala kita adalah pada 0, 896 00:48:42,720 --> 00:48:45,270 maka kita hanya bisa menambahkannya pada ukuran. 897 00:48:45,270 --> 00:48:51,020 Tapi itu akan sedikit rumit karena sesungguhnya, mereka 898 00:48:51,020 --> 00:48:52,840 tidak memiliki slide untuk ini, jadi aku akan 899 00:48:52,840 --> 00:48:56,670 untuk menarik satu karena itu tidak cukup yang sederhana sekali 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 stack Anda hanya pernah memiliki 902 00:49:03,920 --> 00:49:08,920 khawatir tentang apa ukurannya ketika Anda menambahkan sesuatu pada, 903 00:49:08,920 --> 00:49:15,710 dengan antrian Anda juga perlu membuat memastikan bahwa kepala Anda dicatat, 904 00:49:15,710 --> 00:49:20,760 karena hal yang keren tentang antrian adalah bahwa jika Anda tidak pada kapasitas, 905 00:49:20,760 --> 00:49:23,040 Anda benar-benar dapat membuatnya membungkus. 906 00:49:23,040 --> 00:49:28,810 >> OK, jadi salah satu thing-- oh, ini adalah kapur yang mengerikan. 907 00:49:28,810 --> 00:49:31,815 Satu hal yang perlu dipertimbangkan adalah kasus. 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, dan silahkan memiliki hal-hal di dalamnya. 913 00:49:54,210 --> 00:49:58,340 Dan kita ingin menambahkan sesuatu, kan? 914 00:49:58,340 --> 00:50:01,170 Jadi hal yang perlu kita tahu adalah bahwa kepala selalu 915 00:50:01,170 --> 00:50:05,620 akan memindahkan cara ini dan maka loop kembali sekitar, OK? 916 00:50:05,620 --> 00:50:10,190 >> Jadi antrian ini memiliki ruang, kan? 917 00:50:10,190 --> 00:50:13,950 Memiliki ruang di awal, jenis kebalikan dari ini. 918 00:50:13,950 --> 00:50:17,920 Jadi apa yang perlu kita lakukan adalah kita perlu menghitung ekor. 919 00:50:17,920 --> 00:50:20,530 Jika Anda tahu bahwa 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 >> Namun pada kenyataannya, jika Anda menggunakan antrian, kepala Anda mungkin sedang diperbarui. 922 00:50:30,000 --> 00:50:33,890 Jadi apa yang perlu Anda 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 aku akan membiarkan Anda 924 00:50:39,990 --> 00:50:42,680 Orang-orang berpikir tentang, dan maka kita akan bicara tentang hal itu. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Jadi ini adalah kapasitas. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Jadi ini benar-benar akan memberi Anda cara untuk melakukannya. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Karena dalam kasus ini, apa? 931 00:51:04,330 --> 00:51:09,205 Pusat kami di 1, ukuran kami adalah 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Jika kita mod bahwa dengan 5, kita mendapatkan 0, yang mana kita harus masukan itu. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Jadi dalam kasus berikutnya, jika kita melakukan hal ini, 936 00:51:26,080 --> 00:51:33,390 kita katakan, 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 menambahkan hal lain. 940 00:51:47,930 --> 00:51:52,470 Ini pada dasarnya adalah belakang baris kami, 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 perbedaan utama. 943 00:51:57,310 --> 00:51:58,780 Tumpukan, Anda tidak bisa melakukan ini. 944 00:51:58,780 --> 00:52:01,140 >> Dengan antrian, Anda bisa karena semua yang penting 945 00:52:01,140 --> 00:52:03,940 adalah bahwa Anda tahu apa itu yang terakhir ditambahkan. 946 00:52:03,940 --> 00:52:10,650 Karena semuanya akan ditambahkan dalam arah ke kiri ini, dalam hal ini, 947 00:52:10,650 --> 00:52:16,480 dan kemudian membungkus, Anda dapat terus menempatkan dalam unsur-unsur baru 948 00:52:16,480 --> 00:52:18,830 di depan array karena itu tidak benar-benar 949 00:52:18,830 --> 00:52:20,640 bagian depan array lagi. 950 00:52:20,640 --> 00:52:26,320 Anda dapat menganggap awal array sebagai mana kepala Anda sebenarnya. 951 00:52:26,320 --> 00:52:29,710 >> Jadi rumus ini adalah bagaimana Anda menghitung ekor Anda. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Apakah itu 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 menit 957 00:52:44,040 --> 00:52:48,840 untuk menanyakan pertanyaan klarifikasi yang Anda inginkan, karena saya tahu itu gila. 958 00:52:48,840 --> 00:52:51,980 >> Baiklah, jadi di way-- yang sama Aku tidak tahu apakah kalian melihat, 959 00:52:51,980 --> 00:52:53,450 tapi CS adalah semua tentang pola. 960 00:52:53,450 --> 00:52:57,370 Hal-hal yang cukup banyak sama, hanya dengan tweak kecil. 961 00:52:57,370 --> 00:52:58,950 Hal begitu sama di sini. 962 00:52:58,950 --> 00:53:04,040 Kita perlu memeriksa untuk melihat apakah kita benar-benar memiliki sesuatu dalam antrian kami, kan? 963 00:53:04,040 --> 00:53:05,960 Katakanlah, OK, adalah ukuran kami lebih besar dari 0? 964 00:53:05,960 --> 00:53:06,730 Keren. 965 00:53:06,730 --> 00:53:10,690 >> Jika kita lakukan, maka kita menggerakkan kepala kami, yang adalah apa yang saya hanya ditunjukkan di sini. 966 00:53:10,690 --> 00:53:13,870 Kami memperbarui kepala kita untuk menjadi satu lagi. 967 00:53:13,870 --> 00:53:18,390 Dan kemudian kami pengurangan kami Ukuran dan kembali elemen. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Ada banyak lagi beton kode pada study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 dan saya sangat merekomendasikan pergi melalui itu jika Anda punya waktu, 971 00:53:29,440 --> 00:53:30,980 bahkan jika itu hanya pseudo-code. 972 00:53:30,980 --> 00:53:35,980 Dan jika kalian ingin berbicara melalui bahwa dengan saya satu lawan satu, tolong beritahu saya 973 00:53:35,980 --> 00:53:37,500 tahu. 974 00:53:37,500 --> 00:53:38,770 Aku akan senang untuk. 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 bahwa struktur data menjadi sangat menyenangkan dan ini baru saja dimulai. 977 00:53:47,830 --> 00:53:50,350 >> Jadi saya tahu itu sulit. 978 00:53:50,350 --> 00:53:51,300 Tidak apa-apa. 979 00:53:51,300 --> 00:53:52,410 Kami berjuang. 980 00:53:52,410 --> 00:53:53,630 Saya masih dilakukan. 981 00:53:53,630 --> 00:53:56,660 Jadi jangan terlalu khawatir tentang hal itu. 982 00:53:56,660 --> 00:54:02,390 >> Tapi itu pada dasarnya Anda kecelakaan saja 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 Apakah ada sesuatu yang kita ingin pergi lagi? 985 00:54:06,860 --> 00:54:09,400 Apa pun yang kita ingin berbicara melalui? 986 00:54:09,400 --> 00:54:10,060 Ya? 987 00:54:10,060 --> 00:54:16,525 >> AUDIENCE: Misalnya itu, jadi ekor baru 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 AUDIENCE: OK. 990 00:54:18,230 --> 00:54:24,220 Jadi akan melalui, Anda akan memiliki 1 ditambah 4 or-- 991 00:54:24,220 --> 00:54:27,671 >> SPEAKER 1: Jadi Anda berkata, ketika kita ingin pergi melakukan ini lagi? 992 00:54:27,671 --> 00:54:28,296 AUDIENCE: Ya. 993 00:54:28,296 --> 00:54:38,290 Jadi jika Anda mencari out-- mana Anda menghitung ekor dari dalam? 994 00:54:38,290 --> 00:54:44,260 >> SPEAKER 1: Jadi ekor adalah in-- Saya mengubah 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 Jadi kita memiliki hal-hal dalam 1, 2, 3, dan 4. 997 00:54:54,670 --> 00:55:05,850 Jadi kita memiliki kepala kita adalah sama dengan 1 pada titik ini, dan ukuran kita sama dengan 4 998 00:55:05,850 --> 00:55:07,050 pada titik ini, kan? 999 00:55:07,050 --> 00:55:08,960 >> Anda semua sepakat itu yang terjadi? 1000 00:55:08,960 --> 00:55:14,620 Jadi kita lakukan kepala plus ukuran, yang memberi kita 5, dan kemudian kita mod oleh 5. 1001 00:55:14,620 --> 00:55:20,690 Kami mendapatkan 0, yang mengatakan kepada kita bahwa 0 adalah mana ekor kami, di mana kami memiliki ruang. 1002 00:55:20,690 --> 00:55:22,010 >> AUDIENCE: Apa topi? 1003 00:55:22,010 --> 00:55:23,520 >> SPEAKER 1: Kapasitas. 1004 00:55:23,520 --> 00:55:24,020 Maaf. 1005 00:55:24,020 --> 00:55:29,640 Jadi itu adalah ukuran array Anda. 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 >> AUDIENCE: [tak terdengar] sebelum kita kembali elemen? 1009 00:55:39,210 --> 00:55:46,270 >> SPEAKER 1: Jadi kita memindahkan kepala atau kembali saat ini? 1010 00:55:46,270 --> 00:55:52,680 Jadi jika kita bergerak satu, pengurangan ukuran? 1011 00:55:52,680 --> 00:55:54,150 Tunggu. 1012 00:55:54,150 --> 00:55:55,770 Aku pasti lupa lagi. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 Sudahlah. 1015 00:56:01,990 --> 00:56:04,980 Tidak ada rumus lain. 1016 00:56:04,980 --> 00:56:09,980 Ya, Anda akan ingin kembali kepala dan kemudian memindahkannya kembali. 1017 00:56:09,980 --> 00:56:13,270 >> AUDIENCE: OK, karena At ini titik, kepala berada di 0, 1018 00:56:13,270 --> 00:56:18,452 dan kemudian Anda ingin kembali Indeks 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 pikir ada yang lain rumus jenis seperti ini. 1021 00:56:22,820 --> 00:56:26,970 Saya tidak memilikinya di atas kepala saya sebagai Saya tidak ingin memberikan salah satu. 1022 00:56:26,970 --> 00:56:35,470 Tapi saya pikir itu sangat valid untuk mengatakan, OK, menyimpan element-- ini apa pun 1023 00:56:35,470 --> 00:56:40,759 elemen head is-- pengurangan Anda ukuran, gerakkan kepala Anda lebih, dan kembali 1024 00:56:40,759 --> 00:56:41,800 apa pun 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 merasa seperti ini adalah tidak seperti most-- Anda tidak 1029 00:56:53,560 --> 00:56:55,740 akan berjalan keluar dari sini seperti, ya, saya tahu mencoba. 1030 00:56:55,740 --> 00:56:56,880 Aku punya itu semua. 1031 00:56:56,880 --> 00:56:57,670 Tidak apa-apa. 1032 00:56:57,670 --> 00:57:00,200 Aku berjanji. 1033 00:57:00,200 --> 00:57:05,240 Tetapi struktur data adalah sesuatu yang dibutuhkan banyak waktu untuk membiasakan diri. 1034 00:57:05,240 --> 00:57:10,010 Mungkin salah satu yang paling sulit hal, saya pikir, dalam kursus. 1035 00:57:10,010 --> 00:57:15,330 >> Jadi pasti membutuhkan pengulangan dan mencari at-- saya 1036 00:57:15,330 --> 00:57:20,050 tidak benar-benar tahu daftar terkait sampai aku terlalu banyak dengan mereka, 1037 00:57:20,050 --> 00:57:22,550 dengan cara yang sama bahwa saya tidak benar-benar memahami pointer 1038 00:57:22,550 --> 00:57:27,040 sampai aku harus mengajarkannya untuk dua tahun dan melakukan psets saya sendiri dengan itu. 1039 00:57:27,040 --> 00:57:28,990 Dibutuhkan banyak pengulangan dan waktu. 1040 00:57:28,990 --> 00:57:32,600 Dan akhirnya, itu akan jenis klik. 1041 00:57:32,600 --> 00:57:36,320 >> Tapi sementara itu, jika Anda memiliki jenis dari pemahaman tingkat tinggi apa 1042 00:57:36,320 --> 00:57:39,321 ini dilakukan, pro mereka dan cons-- yang adalah apa yang 1043 00:57:39,321 --> 00:57:41,820 kita benar-benar cenderung menekankan, terutama dalam kegiatan intro. 1044 00:57:41,820 --> 00:57:45,511 Seperti, mengapa kita akan menggunakan mencoba lebih dari array? 1045 00:57:45,511 --> 00:57:48,010 Seperti, apa positif dan negatif dari masing-masing? 1046 00:57:48,010 --> 00:57:51,610 >> Dan memahami trade-off antara masing-masing struktur 1047 00:57:51,610 --> 00:57:54,910 adalah apa yang jauh lebih penting sekarang. 1048 00:57:54,910 --> 00:57:58,140 Mungkin ada yang gila pertanyaan atau dua yang 1049 00:57:58,140 --> 00:58:03,710 akan meminta Anda untuk menerapkan dorong atau menerapkan pop atau enqueue dan dequeue. 1050 00:58:03,710 --> 00:58:07,340 Tetapi untuk sebagian besar, memiliki itu pemahaman tingkat yang lebih tinggi dan lebih 1051 00:58:07,340 --> 00:58:09,710 dari pemahaman yang intuitif adalah lebih penting daripada benar-benar 1052 00:58:09,710 --> 00:58:11,250 mampu menerapkannya. 1053 00:58:11,250 --> 00:58:14,880 >> Ini akan benar-benar mengagumkan jika Anda semua bisa pergi keluar dan pergi melaksanakan mencoba, 1054 00:58:14,880 --> 00:58:19,720 tetapi kami memahami itu belum tentu hal yang paling masuk akal sekarang. 1055 00:58:19,720 --> 00:58:23,370 Tapi Anda bisa dalam pset Anda, jika Anda ingin untuk, dan kemudian Anda akan mendapatkan praktek, 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 >> AUDIENCE: OK, jadi mana yang kita dimaksudkan untuk digunakan dalam pset tersebut? 1059 00:58:30,440 --> 00:58:31,916 Apakah saya perlu menggunakan salah satu dari mereka? 1060 00:58:31,916 --> 00:58:32,540 SPEAKER 1: Ya. 1061 00:58:32,540 --> 00:58:34,199 Jadi, Anda memiliki pilihan Anda. 1062 00:58:34,199 --> 00:58:36,740 Saya kira dalam kasus ini, kita bisa berbicara tentang pset sedikit 1063 00:58:36,740 --> 00:58:40,480 karena saya berlari melalui ini. 1064 00:58:40,480 --> 00:58:47,779 Jadi dalam pset Anda, Anda memiliki Anda pilihan mencoba atau tabel hash. 1065 00:58:47,779 --> 00:58:49,570 Beberapa orang akan mencoba dan menggunakan filter mekar, 1066 00:58:49,570 --> 00:58:51,840 tetapi mereka secara teknis tidak benar. 1067 00:58:51,840 --> 00:58:55,804 Karena sifat probabilistik mereka, mereka memberikan hasil positif palsu kadang-kadang. 1068 00:58:55,804 --> 00:58:57,095 Mereka terlihat keren ke dalam, meskipun. 1069 00:58:57,095 --> 00:58:59,030 Sangat merekomendasikan mencari pada mereka setidaknya. 1070 00:58:59,030 --> 00:59:03,260 Tapi Anda memiliki pilihan Anda antara tabel hash dan mencoba. 1071 00:59:03,260 --> 00:59:06,660 Dan itu akan menjadi tempat Anda memuat dalam kamus Anda. 1072 00:59:06,660 --> 00:59:09,230 >> Dan Anda harus memilih fungsi hash Anda, 1073 00:59:09,230 --> 00:59:13,420 Anda harus memilih berapa banyak Ember yang Anda miliki, dan itu akan bervariasi. 1074 00:59:13,420 --> 00:59:17,440 Seperti jika Anda memiliki lebih ember, mungkin itu akan berjalan lebih cepat. 1075 00:59:17,440 --> 00:59:22,790 Tapi mungkin Anda membuang-buang a banyak ruang seperti itu, meskipun. 1076 00:59:22,790 --> 00:59:26,320 Anda harus mencari tahu. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> AUDIENCE: Anda katakan sebelumnya bahwa kita dapat menggunakan fungsi hash lainnya, 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, benar. 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 keren. 1083 00:59:40,770 --> 00:59:43,250 Anda tidak diharapkan untuk membangun fungsi hash Anda sendiri. 1084 00:59:43,250 --> 00:59:46,100 Orang-orang menghabiskan mereka tesis tentang hal-hal ini. 1085 00:59:46,100 --> 00:59:50,250 >> Jadi jangan khawatir tentang membangun Anda sendiri. 1086 00:59:50,250 --> 00:59:53,350 Cari satu online untuk memulai dengan. 1087 00:59:53,350 --> 00:59:56,120 Beberapa dari mereka Anda harus memanipulasi sedikit 1088 00:59:56,120 --> 00:59:59,430 untuk memastikan jenis kembali cocok dan yang lainnya, sehingga pada awalnya, 1089 00:59:59,430 --> 01:00:02,420 Saya akan merekomendasikan menggunakan sesuatu sangat 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 setelah Anda memiliki kerja itu, menggabungkan fungsi hash dingin. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> AUDIENCE: Apakah mencoba menjadi atau efisien tapi hanya sulit untuk, like-- 1094 01:00:13,020 --> 01:00:15,880 >> SPEAKER 1: Jadi mencoba, saya pikir, adalah intuitif sulit untuk menerapkan 1095 01:00:15,880 --> 01:00:18,310 tapi sangat cepat. 1096 01:00:18,310 --> 01:00:20,620 Namun, membutuhkan lebih banyak tempat. 1097 01:00:20,620 --> 01:00:25,270 Sekali lagi, Anda dapat mengoptimalkan kedua dari mereka di cara yang berbeda dan ada cara to-- 1098 01:00:25,270 --> 01:00:26,770 AUDIENCE: Bagaimana kita dinilai pada ini? 1099 01:00:26,770 --> 01:00:27,540 Apakah itu masalah- 1100 01:00:27,540 --> 01:00:29,164 >> SPEAKER 1: Jadi kau dinilai cara biasa. 1101 01:00:29,164 --> 01:00:31,330 Anda akan dinilai pada desain. 1102 01:00:31,330 --> 01:00:36,020 Apapun cara yang Anda lakukan, Anda ingin pastikan itu sebagai elegan karena dapat 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 mencoba atau hash tabel, selama bekerja, 1105 01:00:41,950 --> 01:00:45,350 kami senang dengan itu. 1106 01:00:45,350 --> 01:00:48,370 Dan jika Anda menggunakan sesuatu yang hash pada huruf pertama, itu baik-baik saja, 1107 01:00:48,370 --> 01:00:51,410 seperti mungkin seperti desain-bijaksana. 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 apakah Anda orang noticed-- jika Anda 1110 01:00:55,340 --> 01:00:58,780 nilai pset menurun sedikit karena desain dan yang lainnya, 1111 01:00:58,780 --> 01:00:59,900 itu baik-baik saja. 1112 01:00:59,900 --> 01:01:02,960 Sudah mulai ke titik di mana Anda program yang semakin rumit. 1113 01:01:02,960 --> 01:01:04,830 Ada banyak tempat Anda dapat memperbaiki. 1114 01:01:04,830 --> 01:01:06,370 >> Jadi itu sangat normal. 1115 01:01:06,370 --> 01:01:08,810 Ini bukan berarti bahwa Anda melakukan lebih buruk pada pset 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 merasakan hal itu. 1118 01:01:13,732 --> 01:01:14,940 Aku hanya dinilai semua psets Anda. 1119 01:01:14,940 --> 01:01:16,490 Aku tahu semua orang merasakan hal itu. 1120 01:01:16,490 --> 01:01:19,600 >> Jadi jangan khawatir tentang itu. 1121 01:01:19,600 --> 01:01:23,580 Dan jika Anda memiliki pertanyaan tentang psets sebelumnya atau cara-cara Anda dapat meningkatkan, 1122 01:01:23,580 --> 01:01:27,760 Aku mencoba dan komentar para spesifik tempat, tapi kadang-kadang terlambat 1123 01:01:27,760 --> 01:01:30,840 dan aku bosan. 1124 01:01:30,840 --> 01:01:34,885 Apakah ada hal-hal lain tentang struktur data? 1125 01:01:34,885 --> 01:01:37,510 Saya yakin kalian tidak benar-benar ingin berbicara tentang mereka lagi, 1126 01:01:37,510 --> 01:01:42,650 tetapi jika ada, saya senang untuk pergi atas mereka, serta apa pun 1127 01:01:42,650 --> 01:01:45,580 dari kuliah ini melewati minggu atau minggu lalu. 1128 01:01:45,580 --> 01:01:51,580 >> Aku tahu minggu lalu adalah semua ulasan, jadi kita mungkin telah melompati beberapa ulasan 1129 01:01:51,580 --> 01:01:54,190 dari kuliah. 1130 01:01:54,190 --> 01:01:58,230 Pertanyaan lain saya bisa 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 menit lebih awal. 1133 01:02:02,400 --> 01:02:08,370 >> Saya berharap ini adalah semi-membantu setidaknya, dan aku akan melihat kalian minggu depan, 1134 01:02:08,370 --> 01:02:12,150 atau Kamis jam kantor. 1135 01:02:12,150 --> 01:02:15,285 Apakah ada permintaan untuk makanan ringan untuk minggu depan, itu hal? 1136 01:02:15,285 --> 01:02:17,459 Karena aku lupa permen hari ini. 1137 01:02:17,459 --> 01:02:19,750 Dan aku membawa permen terakhir Minggu, tapi itu Columbus Day, 1138 01:02:19,750 --> 01:02:25,400 sehingga ada seperti enam orang yang memiliki empat kantong permen untuk diri mereka sendiri. 1139 01:02:25,400 --> 01:02:28,820 Aku bisa 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, kedengarannya bagus. 1142 01:02:32,250 --> 01:02:35,050 Have a great day, guys. 1143 01:02:35,050 --> 01:02:39,510