[MUSIK BERMAIN]
SPEAKER 1: Baiklah.
Semua orang selamat datang kembali ke bahagian.
Saya berharap anda semua berjaya pulih dari kuiz anda
dari minggu lepas.
Saya tahu ia adalah sedikit gila di kali.
Seperti yang saya katakan sebelum ini, jika anda dalam sisihan piawai,
tidak benar-benar bimbang tentang hal itu, terutama seksyen yang kurang selesa.
Itulah kira-kira di mana anda harus.
>> Jika anda melakukan besar, maka yang menggerunkan.
Tahniah kepada anda.
Dan jika anda merasa seperti anda perlu sedikit bantuan lanjut, sila
merasa bebas untuk mencapai kepada mana-mana TF.
Kita semua di sini untuk membantu.
>> Itulah sebabnya kita mengajar.
Itu sebabnya saya di sini setiap hari Isnin untuk anda orang-orang dan pada waktu pejabat pada hari Khamis.
Jadi jangan ragu untuk membiarkan saya tahu jika anda bimbang tentang apa-apa
atau jika ada apa-apa pada kuiz bahawa anda benar-benar ingin untuk menangani.
>> Jadi agenda untuk hari ini adalah semua tentang struktur data.
Beberapa di antaranya hanya akan menjadi hanya untuk anda berjinak dengan ini.
Anda mungkin tidak pernah melaksanakan mereka di dalam kelas ini.
Sesetengah daripada mereka yang anda akan, seperti untuk Serangga ejaan anda.
>> Anda akan mempunyai pilihan anda antara jadual hash dan cuba.
Oleh itu, kita akan pasti akan ke atas.
Ia akan menjadi pasti lebih dari jenis seksyen yang tinggi hari ini, walaupun,
kerana ada banyak dari mereka, dan jika kami pergi ke butir-butir pelaksanaan
pada semua ini, kita tidak akan bahkan melewati daftar terkait
dan mungkin sedikit jadual hash.
>> Jadi beruang dengan saya.
Kami tidak akan melakukan sebanyak coding masa ini.
Jika anda mempunyai apa-apa soalan tentang hal itu atau anda mahu melihat ia dilaksanakan
atau cuba untuk diri sendiri, Saya pasti mengesyorkan
akan study.cs50.net, yang mempunyai contoh-contoh semua ini.
Ia akan mempunyai Power Point saya dengan nota-nota yang kita
cenderung untuk menggunakan dan juga beberapa program latihan, terutama untuk perkara-perkara
seperti daftar terhubung dan binari pokok tumpukan dan isyarat.
Jadi sedikit tingkat yang lebih tinggi, yang mungkin lebih baik untuk kalian.
>> Maka dengan itu, kami akan memulakan.
Dan juga, yes-- kuiz.
Saya rasa kebanyakan dari orang-orang yang berada dalam seksyen saya mempunyai kuiz anda,
tetapi ada orang datang di atau sebab-sebab tertentu anda tidak, mereka di sini di depan.
>> Begitu dihubungkan senarai.
Saya tahu ini jenis pergi ke belakang sebelum kuiz anda.
Itu adalah seminggu sebelum yang kita pelajari tentang hal ini.
Tetapi dalam kes ini, kita hanya akan pergi sedikit lebih mendalam.
>> Jadi mengapa kita mungkin memilih linked list lebih array?
Apa yang membezakan mereka?
Ya?
>> PENONTON: Anda boleh mengembangkan berpaut daftar berbanding ukuran tetap array ini.
SPEAKER 1: Benar.
Pelbagai telah menetapkan ukuran sedangkan linked list mempunyai saiz yang berubah-ubah.
Jadi, jika kita tidak tahu bagaimana banyak yang kita mahu untuk menyimpan,
senarai berpaut memberi kita yang besar cara untuk melakukan itu kerana kita boleh hanya
menambah nod lain dan menambah nod lain dan menambah nod lain.
Tetapi apa yang mungkin menjadi trade-off?
Apakah ada yang ingat trade-off antara tatasusunan dan daftar link?
Mmhmm?
>> PENONTON: Anda perlu melalui semua cara yang
melalui senarai terkait mencari elemen dalam senarai.
Dalam array, anda boleh hanya menemukan unsur.
>> SPEAKER 1: Benar.
Jadi dengan arrays--
>> PENONTON: [didengar].
>> SPEAKER 1: Dengan array, kita ada apa yang disebut capaian rawak.
Bermakna jika kita mahu apa yang pernah titik kelima senarai
atau titik kelima kami array, kita hanya boleh ambil itu.
Jika ia senarai yang disambungkan, kita ada untuk beralih melalui, kan?
Jadi mengakses unsur dalam array adalah masa yang berterusan,
sedangkan dengan senarai berpaut itu akan kemungkinan besar akan masa linear kerana mungkin
elemen kami adalah semua cara di akhir.
Kita perlu mencari melalui segala-galanya.
Jadi, dengan semua data ini struktur kita akan
yang akan menghabiskan lebih banyak masa sedikit di, apakah kebaikan dan negatif.
Apabila kita mungkin mahu menggunakan salah satu dari yang lain?
Dan itulah jenis yang hal yang lebih besar untuk mengambil.
>> Jadi kita mempunyai di sini definisi nod.
Ia seperti satu elemen dalam linked list kita, kan?
Oleh itu, kita semua biasa dengan struct typedef kami,
yang kami pergi lebih dalam kajian masa lepas.
Ia pada dasarnya hanya mewujudkan lain jenis data yang kita boleh gunakan.
>> Dan dalam kes ini, ia adalah beberapa nod yang akan mengadakan beberapa integer dalam.
Dan kemudian apa yang bahagian kedua di sini?
Sesiapa sahaja?
>> PENONTON: [didengar].
>> SPEAKER 1: Ya.
Ia adalah penunjuk ke nod seterusnya.
Jadi ini sebenarnya harus di sini.
Ini adalah penunjuk dari jenis nod untuk perkara yang akan datang.
Dan itulah apa yang mereka merangkumi nod kami.
Sejuk.
>> Baiklah, jadi dengan carian, karena kami hanya mengatakan sebelum tangan, jika anda
akan mencari melalui, Anda harus benar-benar beralih
melalui linked list anda.
Jadi, jika kita cari bilangan 9, kita akan bermula di kepala kita
dan yang mengarahkan kita pada permulaan dari linked list kita, kan?
Dan kita berkata, OK, adakah ini nod mengandungi bilangan 9?
Tidak?
>> Baiklah, pergi ke satu depan.
Mengikutinya.
Adakah ia mengandungi bilangan 9?
Tidak.
Ikuti salah satu yang akan datang.
>> Oleh itu, kita harus benar-benar beralih melalui linked list kami.
Kita tidak boleh hanya pergi terus ke mana 9 adalah.
Dan jika kalian benar-benar ingin melihat beberapa pseudo-kod di atas sana.
Kami mempunyai beberapa fungsi pencarian di sini yang mengambil dalam- apakah yang diperlukan dalam?
Apa yang anda fikir?
Satu begitu mudah.
Apa ini?
PENONTON: [didengar].
SPEAKER 1: Jumlah yang kami cari.
Betul?
Dan apa ini akan sesuai dengan?
Ia adalah penunjuk ke?
>> PENONTON: nod A.
>> SPEAKER 1: nod ke dalam senarai bahawa kita sedang melihat, kan?
Oleh itu, kita mempunyai beberapa nod adalah penunjuk di sini.
Ini adalah titik yang akan sebenarnya beralih melalui senarai kami.
Kami set sama dengan daftar kerana itulah
menetapkan ia sama dengan mulai dari linked list kami.
>> Dan manakala ia bukan NULL, manakala kita masih ada kerja lain yang dalam senarai kami,
memeriksa untuk melihat jika nod yang mempunyai jumlah yang kami cari.
Kembali benar.
Jika tidak, mengemaskinikannya, kan?
>> Jika ia adalah NULL, kami keluar kami while dan pulangan palsu
kerana itu bermakna kami tidak menjumpainya.
Adakah semua orang mendapatkan cara yang bekerja?
OK.
>> Jadi dengan penyisipan, anda mempunyai tiga cara yang berbeza.
Anda boleh tambahkan, anda boleh menambah dan anda boleh masukkan ke dalam berbagai macam.
Dalam hal ini, kami tidak akan melakukan tambahkan satu.
Apakah ada yang tahu bagaimana tiga kes mungkin berbeza?
>> Jadi tambahkan bermakna anda meletakkan ia di depan senarai anda.
Jadi ini bermakna bahawa tidak kira apa nod anda, tidak kira
apa nilai tersebut, anda akan untuk meletakkannya di sini di depan, OK?
Ia akan menjadi yang pertama elemen dalam senarai anda.
>> Jika anda menambah ia, ia akan untuk pergi ke belakang senarai anda.
Dan masukkan ke dalam berbagai macam ertinya anda akan meletakkan benar-benar ke dalam tempat
di mana ia menyimpan daftar link anda disusun.
Sekali lagi, bagaimana anda menggunakan orang-orang dan apabila anda menggunakan
mereka akan berbeza-beza bergantung kepada kes anda.
Jika ia tidak perlu diurutkan, tambahkan cenderung
jadi apa yang kebanyakan orang digunakan kerana anda tidak
perlu melalui seluruh senarai untuk mencari akhirnya menambahkannya, kan?
Anda hanya boleh bertahan di dalam.
>> Oleh itu, kita akan melalui penyisipan 1 sekarang.
Jadi satu perkara yang saya akan sangat mengesyorkan pada Serangga ini
adalah untuk menarik perkara-perkara yang keluar, seperti biasa.
Ini sangat penting bahawa anda mengemas kini pointer anda dalam susunan yang betul
kerana jika anda mengemaskinikannya sedikit daripada perintah,
Anda akan berakhir kehilangan bagian dari senarai anda.
>> Jadi, sebagai contoh, dalam hal ini, kami tidak memberitahu kepala untuk hanya titik ke 1.
Jika kita hanya melakukan itu tanpa menyimpan ini 1,
kita tidak tahu apa yang 1 harus menunjuk ke sekarang
kerana kita telah kehilangan apa yang kepala menunjuk.
Jadi, satu hal yang perlu diingat ketika sedang melakukan tambahkan satu
adalah untuk menyelamatkan apa yang tempat kepala terlebih dahulu,
kemudian menetapkan kembali, dan kemudian mengemas apa nod baru anda harus menunjuk ke.
Dalam hal ini, ini adalah salah satu cara untuk melakukannya.
>> Jadi jika kita melakukannya dengan cara ini di mana kita hanya ditugaskan semula kepala,
kita kehilangan pada dasarnya kami semua senarai, kan?
Salah satu cara untuk melakukannya adalah untuk mempunyai 1 mata berikutnya, dan kemudian ada benarnya kepala ke 1.
Atau anda boleh melakukan jenis seperti penyimpanan sementara, yang saya bercakap tentang.
>> Tetapi pemindahan anda pointer dalam susunan yang betul
akan menjadi sangat, sangat penting bagi Serangga ini.
Jika tidak, anda akan mempunyai hash meja atau cuba itu hanya akan menjadi
hanya sebahagian daripada kata-kata yang anda mahu dan kemudian mmhmm you're--?
PENONTON: Apa yang sementara hal penyimpanan anda bercakap tentang?
SPEAKER 1: penyimpanan sementara.
Jadi, pada asasnya lain cara yang anda boleh lakukan ini
yang menyimpan kepala sesuatu, seperti menyimpannya pembolehubah sementara.
Menetapkan ke 1 dan kemudian update 1 ke titik
untuk apa sahaja kepala yang digunakan untuk menunjuk ke.
Dengan cara ini adalah jelas lebih elegan kerana anda
tidak memerlukan nilai sementara, tetapi hanya menawarkan satu lagi cara untuk melakukannya.
Dan kita benar-benar mempunyai beberapa kod untuk ini.
Jadi untuk linked list, kami sebenarnya ada beberapa kod.
Jadi masukkan di sini, ini adalah mengawali.
Jadi ini mula ia di kepala.
>> Sehingga hal pertama, anda perlu membuat nod baru anda, tentu saja,
dan periksa NULL.
Selalu baik.
Dan kemudian anda perlu untuk menetapkan nilai-nilai.
Setiap kali anda membuat nod baru, anda tidak tahu apa yang ia menunjuk ke depan,
sehingga anda ingin memulakan untuk NULL.
Jika ia akhirnya menunjuk kepada sesuatu yang lain, hal itu akan ditugaskan semula dan tidak apa-apa.
Jika itu perkara pertama yang dalam senarai, ia perlu
untuk menunjuk ke NULL kerana itulah akhir dari senarai.
>> Jadi kemudian memasukkannya, kita lihat di sini kita yang memberikan nilai seterusnya nod kami
untuk menjadi apa yang kepala adalah, yang adalah apa yang kami di sini.
Itu yang kami baru saja melakukannya.
Dan kemudian kami memberikan kepala ke titik untuk nod baru kita, kerana ingat,
baru beberapa penunjuk kepada nod, dan itulah yang kepala.
Itulah sebabnya kita mempunyai panah ini pencapai.
Cool?
Mmhmm?
>> PENONTON: Apakah kita harus memulakan seterusnya baru ke NULL pertama,
atau kita hanya boleh memulakan itu untuk kepala?
>> SPEAKER 1: New seterusnya perlu menjadi NULL untuk memulakan
kerana anda tidak tahu di mana ia akan menjadi.
Juga, ini adalah jenis hanya suka paradigma.
Anda set sama dengan NULL hanya untuk memastikan bahawa semua asas anda dilindungi
sebelum anda melakukan apa-apa tugas kembali supaya anda sentiasa dijamin bahawa ia akan
menunjuk kepada nilai tertentu berbanding seperti nilai sampah.
Kerana, ya, kita memberikan baru yang akan datang secara automatik,
tetapi ia lebih adil seperti amalan yang baik untuk memulakan ia
dengan cara itu dan kemudian menetapkan kembali.
>> OK, jadi ganda terkait daftar sekarang.
Apa yang kita fikir?
Apa yang berbeza dengan penggandaan senarai?
>> Jadi dalam daftar link kita, kita dapat hanya bergerak dalam satu arah, bukan?
Kami hanya mempunyai depan.
Kita hanya boleh pergi ke hadapan.
>> Dengan senarai ganda terkait, kami juga boleh bergerak ke belakang.
Oleh itu, kita bukan sahaja yang jumlah yang kita mahu untuk menyimpan,
kita ada di mana ia menunjuk ke depan dan di mana kita telah datang.
Jadi ini membolehkan beberapa penyusuran lebih baik.
>> Nod Jadi ganda terkait, hampir sama, bukan?
Satu-satunya perbezaan adalah sekarang kita mempunyai depan dan sebelumnya.
Ini satu-satunya perbezaan.
>> Jadi jika kita prepend atau kita append-- tidak mempunyai apa-apa kod untuk ini sehingga di sini-
tetapi jika anda adalah untuk mencuba dan masukkan, apa yang penting
adalah anda perlu membuat pasti anda sedang memberikan
kedua-dua sebelumnya dan anda penunjuk berikutnya dengan betul.
Jadi dalam kes ini, anda akan bukan sahaja memulakan depan,
anda memulakan sebelumnya.
Jika kita berada di kepala senarai, kita bukan sahaja akan membuat kepala sama baru,
tetapi harus sebelumnya baru kami menunjuk ke kepala, kan?
>> Itulah satu-satunya perbezaan.
Dan jika anda mahu lebih banyak latihan dengan ini dengan daftar terkait, dengan memasukkan,
dengan memotong, dengan memasukkan ke dalam senarai yang pelbagai,
sila lihat study.cs50.net.
Ada sekumpulan latihan besar.
Saya sangat mengesyorkan mereka.
Saya berharap kami mempunyai masa untuk pergi melalui mereka tapi ada banyak struktur data
untuk mendapatkan melalui.
>> OK, jadi jadual hash.
Ini mungkin adalah yang paling sedikit berguna untuk anda Serangga
di sini kerana anda akan berada melaksanakan salah satu dari ini, atau cuba.
Saya sangat suka jadual hash.
Mereka cukup sejuk.
>> Jadi, pada asasnya apa yang berlaku adalah jadual hash
adalah ketika kita benar-benar perlu cepat penyisipan, penghapusan, dan pencarian.
Mereka adalah perkara-perkara yang kami keutamaan dalam jadual hash.
Mereka boleh mendapatkan cukup besar, tetapi seperti yang kita akan melihat dengan mencoba,
ada perkara-perkara yang jauh lebih besar.
>> Tapi pada dasarnya, semua hash meja adalah fungsi hash
yang memberitahu anda yang ember untuk menempatkan setiap data anda, setiap satu daripada unsur-unsur anda di.
Cara mudah untuk memikirkan jadual hash adalah bahawa ia hanya baldi perkara,
kan?
Oleh itu, apabila anda memilah perkara oleh seperti huruf pertama dari nama mereka,
itu semacam seperti meja hash.
>> Jadi jika saya kepada kumpulan kalian adalah ke dalam kumpulan sesiapa nama yang bermula
dengan A di sini, atau siapa pun yang hari jadi adalah pada bulan Januari, Februari, Mac,
apa sahaja, yang berkesan mewujudkan carta hash.
Ia hanya menciptakan baldi yang anda menyusun unsur-unsur anda ke
supaya anda boleh mencari mereka lebih mudah.
Jadi cara ini apabila saya perlu untuk mencari salah seorang dari kamu,
Saya tidak mempunyai untuk mencari melalui setiap nama anda.
Saya boleh menjadi seperti, oh, saya tahu bahawa Ulang tahun Danielle adalah dalam-
PENONTON: --April.
SPEAKER 1: April.
Jadi saya melihat pada bulan April saya baldi, dan dengan sedikit keberuntungan,
dia akan menjadi satu-satunya di sana dan masa saya adalah berterusan dalam hal ini,
sedangkan jika saya harus melihat melalui sejumlah besar orang,
ia akan mengambil masa lebih lama.
Jadi jadual hash adalah benar-benar hanya baldi.
Cara mudah untuk berfikir dari mereka.
>> Jadi satu perkara yang sangat penting tentang jadual hash adalah fungsi hash.
Jadi perkara yang saya hanya berbicara tentang, seperti surat pertama anda dari nama pertama anda
atau bulan hari lahir anda, ini adalah idea-idea yang
benar-benar berkorelasi dengan fungsi hash.
Ia hanya satu cara untuk membuat keputusan yang bucket anda elemen sedang masuk ke dalam, OK?
Jadi untuk Serangga ini, anda boleh melihat ke atas cukup banyak apa-apa fungsi hash yang anda mahu.
>> Tidak perlu anda sendiri.
Ada beberapa yang benar-benar sejuk keluar sana yang melakukan segala macam matematik gila.
Dan jika anda mahu untuk membuat anda pemeriksa ejaan super cepat,
Saya pasti akan melihat ke dalam salah satu dari mereka.
>> Tetapi ada juga yang yang sederhana, seperti menghitung
jumlah dari kata-kata, seperti setiap huruf mempunyai nombor.
Mengira jumlah.
Yang menentukan baldi.
Mereka juga mempunyai orang-orang yang mudah yang hanya seperti semua A di sini,
semua B yang ada di sini.
Mana-mana satu dari mereka.
>> Pada asasnya, ia hanya memberitahu anda yang indeks array elemen anda harus masuk ke dalam.
Hanya memutuskan bucket-- yang itu semua fungsi hash.
Jadi di sini kita mempunyai sebuah contoh yang hanya huruf pertama dari rentetan
itu, saya baru bercakap tentang.
>> Jadi, anda mempunyai beberapa hash itu hanya Huruf pertama tolak tali anda A,
yang akan memberikan anda beberapa nombor di antara 0 dan 25.
Dan apa yang anda mahu lakukan adalah memastikan bahawa ini merupakan
saiz hash Anda table-- berapa banyak baldi ada.
Dengan banyak syarikat- fungsi hash, mereka
akan kembali nilai-nilai yang mungkin jauh di atas bilangan baldi
Anda benar-benar mempunyai dalam jadual hash anda,
jadi anda perlu untuk membuat yakin dan mod oleh mereka.
Jika tidak, ia akan berkata, oh, itu harus dalam baldi 5,000
tetapi anda hanya mempunyai 30 baldi dalam jadual hash anda.
Dan sudah tentu, kita semua tahu itu akan menghasilkan beberapa kesalahan gila.
Jadi pastikan untuk mod oleh ukuran meja hash anda.
Sejuk.
Jadi perlanggaran.
Apakah semua orang yang baik setakat ini?
Mmhmm?
>> PENONTON: Mengapa ia kembali apa-apa jumlah yang besar-besaran?
>> SPEAKER 1: Bergantung kepada algoritma bahawa fungsi hash anda menggunakan.
Beberapa dari mereka akan melakukan pendaraban gila.
Dan itu semua tentang mendapatkan yang pemerataan,
sehingga mereka benar-benar melakukan beberapa perkara gila kadang-kadang.
Itu sahaja.
Apa-apa lagi?
OK.
>> Jadi perlanggaran.
Pada dasarnya, seperti yang saya katakan sebelum ini, dalam kes senario yang terbaik,
setiap baldi saya melihat ke dalam adalah akan mempunyai satu perkara,
jadi saya tidak perlu melihat sama sekali, bukan?
Saya sama ada tahu itu ada atau itu tidak, dan itulah yang kita benar-benar mahu.
Tetapi jika kita mempunyai puluhan ribu titik data dan kurang daripada jumlah itu
dari baldi, kita akan mempunyai tabrakan di mana sesuatu yang akhirnya
akan perlu berakhir di ember yang sudah memiliki unsur.
>> Jadi pertanyaannya adalah, apa yang yang kita lakukan dalam hal ini?
Apa yang kita lakukan?
Kita sudah ada sesuatu di sana?
Adakah kita hanya membuang ia keluar?
>> Tidak.
Kita perlu menjaga kedua-dua mereka.
Jadi cara yang kita biasanya melakukan itu adalah apa?
Bagaimana struktur data kita hanya bercakap tentang?
PENONTON: Senarai Berkaitan.
SPEAKER 1: Daftar terkait.
Jadi sekarang, bukan masing-masing baldi hanya mempunyai satu elemen,
itu akan mengandungi senarai berpaut dari unsur-unsur yang telah dicincang ke dalamnya.
OK, adakah semua orang jenis mendapat idea itu?
Kerana kita tidak boleh mempunyai array kerana kita tidak tahu berapa banyak perkara
yang akan berada di sana.
Daftar terkait membolehkan kita untuk mempunyai hanya jumlah yang tepat bahawa
adalah hash ke dalam baldi itu, kan?
>> Jadi linear menyelidik adalah pada dasarnya idea-- ini
itu salah satu cara untuk berurusan dengan perlanggaran.
Apa yang boleh anda lakukan adalah jika, dalam hal ini kes, berry hash ke 1
dan kita sudah mempunyai sesuatu di sana, anda hanya
terus ke bawah sehingga anda mencari slot kosong.
Itu salah satu cara untuk menanganinya.
Cara lain untuk menangani itu dengan apa yang kita hanya
called-- yang terkait senarai dipanggil rantaian.
>> Jadi idea ini bekerja jika jadual hash anda, anda berfikir
jauh lebih besar daripada data anda menetapkan atau jika anda
ingin mencuba dan mengurangkan chaining sehingga ia benar-benar diperlukan.
Jadi satu perkara yang linear menyelesaikan sesuatu jelas berarti
bahawa fungsi hash Anda tidak cukup berguna
kerana anda akan berakhir dengan menggunakan fungsi hash anda, sampai ke titik,
Anda linier menyiasat ke beberapa tempat yang disediakan.
Tapi sekarang, sudah tentu, apa-apa lain yang berakhir di sana,
Anda akan perlu mencari lebih jauh.
>> Dan ada banyak lagi perbelanjaan carian yang
masuk ke dalam memasukkan unsur dalam jadual hash anda sekarang, kan?
Dan sekarang ketika anda pergi dan cuba dan mencari buah lagi, anda akan hash itu,
dan ia akan berkata, oh, lihat dalam baldi 1,
dan ia tidak akan menjadi di ember 1, sehingga anda
akan harus melintasi melalui sisa ini.
Jadi kadang-kadang berguna, tetapi dalam kebanyakan kes,
kita akan mengatakan bahawa chaining adalah apa yang anda mahu lakukan.
>> Oleh itu, kita bercakap tentang perkara ini sebelum ini.
Saya mendapat lebih awal sedikit dari diri saya.
Tetapi chaining pada dasarnya yang setiap kotak dalam jadual hash Anda
hanya daftar link.
>> Jadi cara yang lain, atau lebih teknikal cara, untuk memikirkan jadual hash
adalah bahawa ia hanya array yang terhubung daftar, yang
bila anda menulis kamus anda dan anda cuba untuk memuat itu,
memikirkan hal itu sebagai array daftar terkait
akan membuat ia lebih mudah bagi anda untuk memulakan.
>> PENONTON: Jadi jadual hash mempunyai saiz yang telah ditetapkan,
seperti [terdengar] dari baldi?
>> SPEAKER 1: Benar.
Oleh itu, ia mempunyai beberapa set kotak yang Anda determine--
yang kalian harus berasa bebas untuk bermain dengan.
Ia boleh menjadi cukup sejuk untuk melihat apa yang berlaku
apabila anda menukar nombor anda dari baldi.
Tapi ya, ia mempunyai mengatur jumlah baldi.
Apa yang membolehkan anda untuk cocok sebagai banyak elemen yang anda perlukan
adalah chaining berasingan di mana anda telah mengaitkan senarai dalam setiap kotak.
Ini bermakna jadual hash Anda akan persis saiz
yang anda perlukan untuk menjadi, bukan?
Itu titik seluruh daftar terkait.
Sejuk.
>> Jadi setiap orang ada OK?
Baik.
Ah.
Apa yang terjadi?
Benar-benar sekarang.
Meneka seseorang membunuh saya.
>> OK kita akan masuk ke mencoba, yang sedikit gila.
Saya suka jadual hash.
Saya rasa mereka benar-benar sejuk.
Cuba sejuk juga.
>> Jadi tidak ada yang ingat apa yang cuba adalah?
Anda seharusnya pergi lebih ia secara ringkas dalam kuliah?
Adakah anda ingat jenis bagaimana ia berfungsi?
PENONTON: Saya hanya mengangguk-angguk bahwa kita pergi lebih dari itu.
SPEAKER 1: Kami pergi lebih dari itu.
OK, kita benar-benar akan pergi lebih sekarang adalah apa yang kita katakan.
>> PENONTON: Itu untuk pohon pengambilan.
>> SPEAKER 1: Ya.
Ini adalah pokok pengambilan.
Awesome.
Jadi, satu perkara yang perlu diperhatikan di sini adalah bahawa kita sedang melihat karakter individu
di sini, kan?
>> Jadi sebelum dengan fungsi hash kami, kami cari akan kata-kata secara keseluruhan,
dan sekarang kami sedang mencari lebih banyak pada watak-watak, bukan?
Jadi kita mempunyai Maxwell di sini dan Mendel.
Jadi, pada asasnya sebuah try-- satu cara untuk berfikir tentang ini adalah bahawa setiap peringkat di sini
adalah array surat.
Jadi, ini adalah nod root anda di sini, kan?
Ini semua watak-watak dari abjad untuk permulaan setiap kata.
>> Dan apa yang anda mahu lakukan adalah berkata, OK, kita mempunyai beberapa kata M.
Kita akan mencari Maxwell, jadi kita pergi ke M. Dan M mata kepada keseluruhan
lain lokasi di mana setiap kata, selama ada
adalah kata yang mempunyai A sebagai surat yang kedua,
selagi ada perkataan yang mempunyai B seperti surat kedua,
ia akan mempunyai penunjuk pergi ke beberapa pelbagai berikutnya.
>> Mungkin ada yang tidak kata yang MP sesuatu,
jadi pada kedudukan P dalam ini array, ia hanya akan menjadi NULL.
Ia akan berkata, OK, tidak ada kata yang telah M diikuti oleh P, oke?
Jadi jika kita berfikir tentang hal itu, masing-masing salah satu perkara-perkara ini lebih kecil
sebenarnya salah satu dari ini array besar dari A sampai Z.
Jadi apa yang mungkin menjadi salah satu perkara yang yang jenis kelemahan dari mencuba?
>> PENONTON: Banyak memori.
>> SPEAKER 1: Ini satu tan memori, kan?
Masing-masing dari blok ini di sini mewakili 26 ruang, 26 elemen array.
Jadi cuba mendapatkan ruang sangat berat.
>> Tetapi mereka sangat cepat.
Jadi sangat cepat tetapi benar-benar tidak cekap ruang.
Jenis harus mencari yang mana satu anda mahu.
Ini adalah benar-benar sejuk untuk Serangga anda, tetapi mereka mengambil banyak memori,
jadi anda trade off.
Ya?
>> PENONTON: Adakah mungkin untuk menubuhkan mencuba dan kemudian
apabila anda mempunyai semua data di dalamnya yang anda need--
Saya tidak tahu apakah yang akan masuk akal.
Saya telah menyingkirkan semua Aksara NULL, tetapi kemudian
Anda tidak akan dapat indeks them--
>> SPEAKER 1: Anda masih memerlukannya.
>> PENONTON: - cara yang sama setiap kali.
SPEAKER 1: Ya.
Anda memerlukan karakter NULL untuk membiarkan anda tahu jika tidak ada satu perkataan di sana.
Ben adakah anda mempunyai sesuatu yang anda mahu?
OK.
Baiklah, jadi kita akan untuk pergi sedikit lebih
ke detail teknikal di belakang yang berusaha dan bekerja melalui contoh.
>> OK, jadi ini adalah perkara yang sama.
Manakala dalam senarai yang disambungkan, utama kami jenis daripada- apa perkataan yang saya mahu? -
seperti membina blok adalah nod.
Di cuba, kami juga mempunyai nod, tetapi ia ditakrifkan berbeza.
>> Oleh itu, kita mempunyai beberapa bool yang mewakili sama ada perkataan yang benar-benar
wujud di lokasi ini, dan kemudian kami mempunyai pelbagai sini-atau lebih tepat,
ini adalah satu penunjuk kepada array 27 aksara.
Dan ini adalah untuk, dalam hal ini, ini 27-- saya pasti kamu semua adalah seperti, tunggu,
terdapat 26 huruf dalam abjad.
Mengapa kita mempunyai 27?
>> Jadi bergantung kepada cara anda melaksanakan ini,
ini adalah dari Serangga yang dibenarkan untuk apostrof.
Jadi itulah sebabnya satu tambahan.
Anda juga akan mempunyai di beberapa kes terminator nol
dimasukkan sebagai salah satu daripada aksara yang ia dibenarkan untuk menjadi,
dan itulah bagaimana mereka memeriksa untuk melihat apakah itu akhir perkataan.
Jika anda berminat, lihat Video Kevin pada study.cs50,
dan juga Wikipedia mempunyai beberapa sumber yang baik di sana.
>> Tetapi kita akan pergi melalui hanya jenis bagaimana anda boleh bekerja melalui cuba
jika anda diberi satu.
Jadi kita mempunyai satu super sederhana di sini bahawa mempunyai perkataan "kelawar" dan "zoom" di dalamnya.
Dan seperti yang kita lihat di sini, ruang ini kecil di sini
mewakili bool kami bahawa berkata, ya, ini adalah satu perkataan.
Dan kemudian ini mempunyai kami tatasusunan aksara, kan?
>> Jadi kita akan pergi melalui mencari "kelawar" dalam cuba ini.
Jadi bermula di bahagian atas, bukan?
Dan kita tahu bahawa b sepadan dengan Indeks kedua, elemen kedua
dalam array ini, kerana a dan b.
Jadi kira-kira yang kedua.
>> Dan ia berkata, OK, sejuk, ikuti itu ke dalam array akan datang, kerana jika kita ingat,
ia tidak bahawa masing-masing sebenarnya mengandungi elemen.
Masing-masing dari array ini mengandungi pointer, bukan?
Ia merupakan satu perbezaan penting untuk membuat.
>> Saya tahu ini akan adalah-- mencoba adalah benar-benar sukar untuk mendapatkan pada kali pertama,
jadi walaupun ini adalah kedua atau ketiga kalinya
dan ia masih jenis dari tampak sukar,
Saya berjanji jika anda pergi menonton pendek lagi besok,
ia mungkin akan masuk akal lebih banyak.
Ia mengambil banyak untuk dihadam.
Saya masih kadang-kadang saya seperti, tunggu, apa yang cuba?
Bagaimana saya menggunakan ini?
>> Oleh itu, kita telah b dalam kes ini, yang merupakan indeks kedua kami.
Jika kita mempunyai, katakan, atau c d atau apa-apa surat yang lain,
kita perlu peta yang kembali kepada indeks dari array kita bahawa yang sepadan dengan.
Oleh itu, kita akan mengambil seperti rchar dan kami hanya tolak dari sebuah peta itu ke 0-25.
Semua orang yang baik bagaimana kita peta aksara kita?
OK.
>> Jadi kita pergi ke yang kedua dan kita melihat bahawa, ya, ia tidak adalah dengan NULL.
Kita boleh bergerak ke array ini akan datang.
Jadi kita pergi ke array ini seterusnya di sini.
>> Dan kita berkata, OK, sekarang kita perlu untuk melihat apakah yang ada di sini.
Apakah A batal atau tidak ia sebenarnya ke depan?
Jadi yang benar-benar bergerak maju dalam array ini.
Dan kita berkata, OK, t ialah surat terakhir kami.
Jadi kita pergi ke t di indeks.
Dan kemudian kita bergerak ke hadapan kerana ada satu lagi.
Dan salah satu ini mengatakan bahawa pada dasarnya, ya, ia mengatakan bahawa ada satu kata di sini-
bahawa jika anda mengikuti ini jalan, anda telah tiba
di kata, yang kita tahu ialah "kelawar".
Ya?
>> PENONTON: Apakah standard untuk memiliki sebagai indeks 0 dan kemudian memiliki semacam pada 1
atau mempunyai di akhir?
>> SPEAKER 1: No.
Oleh itu, jika kita melihat kembali pada kami deklarasi di sini, itu bool,
jadi ia adalah elemen tersendiri dalam nod anda.
Jadi ia bukan sebahagian daripada array.
Sejuk.
Oleh itu, apabila kita menyelesaikan kata kami dan kami di array ini, apa yang kita mahu lakukan
adalah melakukan cek ialah perkataan.
Dan dalam kes ini, ia akan kembali ya.
>> Maka pada masa yang sama, kita tahu bahawa "kebun binatang" - kita kenal sebagai manusia yang "zoo" adalah satu perkataan,
kan?
Tetapi cuba di sini akan berkata, tidak, tidak.
Dan ia akan mengatakan bahawa kerana kita belum ditetapkan sebagai kata di sini.
Walaupun kita dapat melintasi melalui array ini,
cuba ini akan mengatakan bahawa, tidak, kebun binatang tidak ada di dalam kamus anda
kerana kita tidak mempunyai ditetapkan seperti itu.
>> Jadi salah satu cara untuk melakukan bahawa- oh, maaf, yang satu ini.
Jadi dalam hal ini, "zoo" tidak kata, tetapi ia adalah dalam cuba kami.
Tetapi dalam satu ini, mengatakan bahawa kita mahu memperkenalkan perkataan "mandi," apa yang berlaku
adalah kita mengikuti through-- b, a, t.
Kami dalam array ini, dan kita pergi untuk mencari h.
>> Dalam hal ini, apabila kita melihat penunjuk di h,
itu menunjuk ke NULL, OK?
Jadi kecuali jika jelas menunjuk ke array lain,
anda menganggap bahawa semua pointer dalam array ini menunjuk ke null.
Jadi dalam hal ini, h menunjuk null itu kita tidak boleh berbuat apa-apa,
jadi ia juga akan kembali palsu, "mandi" tidak ada di sini.
Jadi sekarang kita benar-benar akan pergi melalui
bagaimana kita benar-benar mengatakan bahawa "kebun binatang" adalah dalam cuba kami.
Bagaimana kita memasukkan "zoo" ke dalam cuba kita?
Jadi dengan cara yang sama yang kita mulai dengan linked list kami, kami mulai pada akar.
Jika ragu, bermula akar dari perkara-perkara ini.
>> Dan kita akan berkata, OK, z.
z ada dalam hal ini, dan itu.
Jadi, kau pindah ke array seterusnya, OK?
Dan kemudian kepada orang yang akan datang, kita kata, OK, adakah o wujud?
Tentu saja.
Ini sekali lagi.
>> Dan sebagainya yang berikutnya, kami telah berkata, OK, "zoo" sudah ada di sini.
Apa yang kita perlu lakukan adalah membuat ini sama kepada benar, yang ada kata ada.
Jika anda telah mengikuti semua sehingga sebelum saat itu,
itu kata, jadi hanya set sama dengan itu.
Ya?
>> PENONTON: Jadi adakah itu bermakna "ba" adalah satu perkataan juga?
>> SPEAKER 1: No.
Jadi dalam hal ini, "ba" kita akan mendapatkan di sini, kita akan mengatakan ia adalah perkataan,
dan itu akan tetap ada.
OK?
Mmhmm?
>> PENONTON: Jadi sekali anda apakah itu kata dan anda menjawab ya, maka ia
akan mengandungi pergi ke m?
>> SPEAKER 1: Jadi ini ada hubungannya with-- Anda memuat ini.
Anda mengatakan "zoo" adalah satu perkataan.
Apabila anda pergi ke check-- seperti, katakan anda ingin mengatakan,
maksud "zoo" wujud dalam kamus ini?
Anda hanya akan mencari "kebun binatang," dan kemudian memeriksa untuk melihat sama ada ianya perkataan.
Anda tidak akan pernah bergerak melalui m kerana itu bukan
apa yang anda cari.
>> Jadi, jika kita benar-benar mahu menambah "mandi" ke cuba ini,
kita akan melakukan perkara yang sama seperti yang kita lakukan dengan "zoo,"
kecuali kita akan melihat bahawa apabila kita cuba mendapatkan hingga h, ia tidak wujud.
Jadi, anda boleh menganggap ini sebagai cuba untuk menambah nod baru ke dalam senarai yang disambungkan,
Jadi, kita perlu untuk menambah satu lagi salah satu array ini, seperti begitu.
Dan kemudian apa yang kita lakukan adalah kita hanya mengatur h elemen array ini menunjuk kepada ini.
>> Dan kemudian apa yang kita ingin lakukan di sini?
Tambah itu sama dengan benar kerana ia adalah satu perkataan.
Sejuk.
Saya tahu.
Cuba tidak adalah yang paling menarik.
Percayalah, saya tahu.
>> Jadi, satu perkara yang perlu sedar dengan mencoba, Saya berkata, mereka sangat cekap.
Oleh itu, kita telah melihat mereka mengambil masa sehingga satu tan ruang.
Mereka agak membingungkan.
Jadi, mengapa kita pernah menggunakan ini?
Kami menggunakan ini kerana mereka sangat cekap.
>> Jadi, jika anda pernah melihat sehingga kata, anda hanya
dibatasi oleh panjang kata.
Jadi, jika anda sedang mencari perkataan yang panjang lima,
Anda hanya pernah akan perlu membuat paling banyak lima perbandingan, OK?
Sehingga membuatnya pada dasarnya yang tetap.
Seperti penyisipan dan lookup pada dasarnya masa yang sama.
>> Jadi jika anda pernah mendapatkan sesuatu dalam masa yang tetap,
itu sebagai baik kerana mendapat.
Anda tidak boleh mendapatkan lebih baik daripada pemalar masa untuk perkara-perkara ini.
Jadi itu adalah salah satu daripada plus besar daripada cuba.
>> Tetapi ia adalah banyak ruang.
Jadi anda jenis perlu membuat keputusan apa yang lebih penting kepada anda.
Dan pada komputer hari ini, ruang yang cuba mungkin mengambil masa sehingga
mungkin tidak menjejaskan yang banyak, tetapi mungkin
Anda sedang berhadapan dengan sesuatu yang yang mempunyai jauh, jauh lebih banyak hal,
dan cuba hanya tidak masuk akal.
Ya?
>> PENONTON: Tunggu, jadi anda mempunyai 26 huruf dalam setiap satu daripadanya?
>> SPEAKER 1: Mmhmm.
Ya, anda mempunyai 26.
Anda mempunyai beberapa adalah penanda kata dan kemudian anda mempunyai 26 petunjuk dalam setiap satu.
Dan mereka point--
>> PENONTON: Dan setiap 26, adakah mereka masing-masing mempunyai 26?
>> SPEAKER 1: Ya.
Dan sebab itu, yang anda boleh lihat, ia mengembang cukup pesat.
Baik.
Jadi, kita akan masuk ke dalam pokok-pokok, yang Saya rasa seperti lebih mudah dan mungkin akan
menjadi penangguhan hukuman kecil yang menyenangkan dari negara-sana.
Jadi mudah-mudahan kebanyakan kamu telah melihat pohon sebelumnya.
Tidak seperti cantik yang di luar, yang saya
tidak tahu apakah ada orang keluar rumah baru-baru ini.
Saya pergi memetik apel hujung minggu ini, dan oh ya ampun, itu indah.
Saya tidak tahu daun boleh melihat yang cantik.
>> Jadi, ini adalah hanya pokok, kan?
Ia hanya beberapa nod, dan ia menunjuk ke sekumpulan nod lain.
Seperti yang anda lihat di sini, ini adalah jenis tema yang berulang.
Nod yang menunjuk ke nod adalah jenis intipati struktur data banyak.
Ia hanya bergantung kepada bagaimana kita memiliki titik mereka antara satu sama lain
dan bagaimana kita melintasi melalui mereka dan bagaimana kita
memasukkan sesuatu yang menentukan ciri-ciri yang berbeza.
>> Jadi hanya beberapa istilah, yang saya gunakan sebelum ini.
Jadi akar adalah apa yang ada di bahagian paling atas.
itu di mana kita selalu bermula.
Anda boleh menganggapnya sebagai kepala juga.
Tetapi bagi pokok-pokok, kita cenderung untuk menyebutnya sebagai akar.
>> Apa-apa sahaja di sini-bahagian bawah di sangat, sangat bottom--
adalah daun dipertimbangkan.
Jadi ia pergi bersama-sama dengan perkara pokok keseluruhan, bukan?
Daun di tepi pokok anda.
>> Kemudian kami juga mempunyai beberapa hal untuk bercakap tentang nod berhubung
satu sama lain.
Jadi kita mempunyai ibu bapa, anak-anak, dan saudara kandung.
Jadi dalam kes ini, 3 adalah induk dari 5, 6, dan 7.
Jadi ibu bapa adalah apa yang ada satu langkah di atas apa sahaja yang anda
merujuk kepada, jadi seperti pohon keluarga.
Mudah-mudahan, ini semua kecil yang sedikit lebih intuitif daripada cuba.
>> Saudara adalah setiap yang mempunyai ibu bapa yang sama, kan?
Mereka berada di tahap yang sama di sini.
Dan kemudian, kerana saya berkata, kanak-kanak hanya
apa sahaja yang merupakan salah satu langkah di bawah nod yang berkenaan, OK?
Sejuk.
Jadi pokok binari.
Ada yang bisa menebak pada salah satu ciri-ciri pokok binari?
>> PENONTON: Max dua daun.
>> SPEAKER 1: Benar.
Jadi max dua daun.
Jadi, dalam hal ini sebelumnya, kami mempunyai satu ini yang mempunyai tiga orang, tetapi di pohon binari,
Anda mempunyai maksimum dua kanak-kanak setiap ibu bapa, kan?
Ada satu lagi ciri-ciri yang menarik.
Apakah ada yang tahu?
Pokok binari.
>> Jadi pokok binari akan mempunyai segala-galanya pada the-- satu ini tidak sorted--
tetapi dalam pokok binari yang disusun, semua yang ada di sebelah kanan
adalah lebih besar daripada ibu bapa, dan semua yang ada di sebelah kiri
kurang dari induk.
Dan yang telah kuiz soalan sebelum ini, jadi baik untuk tahu.
Jadi cara kita menentukan ini, lagi, kita mempunyai nod lain.
Ini kelihatan hampir sama dengan apa?
Ganda
>> PENONTON: Berkaitan senarai
>> SPEAKER 1: Daftar terkait ganda, kan?
Jadi jika kita mengganti ini dengan sebelum dan sesudahnya,
ini akan menjadi satu senarai duanya adalah terpakai dikaitkan.
Tetapi dalam kes ini, kita benar-benar mempunyai kiri dan kanan dan itu sahaja.
Jika tidak, itu betul-betul sama.
Kami masih mempunyai elemen anda cari,
dan anda hanya perlu dua pointer akan apa pun yang akan datang.
Ya, pokok pencari sehingga binari.
Kalau kita lihat, semua yang ada di di sini adalah than-- lebih besar
atau segala sesuatu dengan segera di sini yang betul
adalah lebih besar daripada, segala-galanya di sini adalah kurang daripada.
>> Jadi, jika kita adalah untuk mencari melalui, ia harus terlihat sangat dekat dengan carian binari
di sini, kan?
Kecuali bukan melihat pada separuh array,
kita hanya melihat sama ada sebelah kiri sisi atau sebelah kanan pokok itu.
Sehingga mendapat sedikit lebih mudah, saya fikir.
>> Jadi, jika root anda adalah NULL, jelas ia hanya palsu.
Dan jika itu ada, jelas itu benar.
Jika kurang daripada, kita mencari sebelah kiri.
Jika ia lebih besar dari, kita mencari kanan.
Ini persis seperti carian binari, hanya struktur data yang berbeza
yang kita gunakan.
Daripada array, itu hanya pokok binari.
>> OK, tumpukan.
Dan juga, ia kelihatan seperti kita mungkin mempunyai sedikit masa.
Jika kita lakukan, saya senang untuk pergi atas mana-mana dari ini lagi.
OK, jadi tumpukan.
Apakah ada yang ingat apa stacks-- apa-apa ciri-ciri stack?
>> OK, jadi kebanyakan kita, saya fikir, makan di makan halls--
seperti yang kita mungkin tidak suka.
Tetapi jelas, anda boleh memikirkan tumpukan benar hanya sebagai tumpukan dulang
atau tumpukan hal.
Dan apa yang penting sedar ialah bahawa itu
something-- ciri yang kita sebut itu oleh- adalah LIFO.
Adakah sesiapa yang tahu apa itu singkatan?
Mmhmm?
>> PENONTON: Kamari, keluar pertama.
>> SPEAKER 1: Benar, bertahan, keluar pertama.
Jadi, jika kita tahu, jika kita susun perkara atas, perkara yang paling mudah untuk mengambil off--
dan mungkin satu-satunya perkara yang boleh kita ambil off jika tumpukan kami adalah enough-- besar
ialah elemen atas.
Jadi apa pun yang memakai last-- seperti yang kita lihat di sini,
apa sahaja yang didorong pada kebanyakan recently-- adalah
akan menjadi yang pertama hal yang kita meninggal, OK?
>> Jadi apa yang kita ada di sini adalah lain struct typedef.
Ini benar-benar hanya seperti crash kursus dalam struktur data,
jadi ada banyak dilemparkan pada anda semua.
Saya tahu.
Jadi belum struct lain.
Yay untuk struktur.
>> Dan dalam kes ini, ia adalah beberapa penunjuk ke array yang mempunyai kapasiti beberapa.
Jadi ini merupakan tumpukan kami di sini, seperti array yang sebenarnya kami
yang memegang unsur-unsur kita.
Dan kemudian di sini kita mempunyai beberapa saiz.
>> Dan biasanya, yang anda hendak simpan menjejaki seberapa besar stack adalah
kerana apa yang ia akan membenarkan Anda lakukan adalah jika anda tahu saiz,
ia membolehkan anda untuk mengatakan, OK, saya pada kapasiti?
Bolehkah saya menambah apa-apa lagi?
Dan ia juga memberitahu anda di mana bahagian atas tumpukan
adalah supaya anda tahu apa yang anda benar-benar dapat dilaksanakan.
Dan itu benar-benar akan menjadi sedikit lebih jelas di sini.
>> Jadi untuk menolak, satu perkara, jika anda pernah untuk melaksanakan push,
kerana saya hanya mengatakan, anda tumpukan mempunyai saiz yang terhad, bukan?
Array kita mempunyai keupayaan beberapa.
Ini array.
Ini saiz yang tetap, jadi kita perlu memastikan bahawa kita tidak meletakkan lebih
ke dalam array kita daripada kita sebenarnya mempunyai ruang untuk.
>> Oleh itu, apabila anda membuat tolakan fungsi, perkara pertama yang anda lakukan adalah berkata, OK,
saya perlu ruang di tumpukan saya?
Kerana jika saya tidak, maaf, Saya tidak boleh menyimpan elemen anda.
Jika saya lakukan, maka anda mahu untuk menyimpan ia di bahagian atas tindanan, kan?
>> Dan ini adalah mengapa kita mempunyai untuk mengesan saiz kami.
Jika kita tidak menjejaki saiz kami, kita tidak tahu di mana untuk meletakkan ia.
Kita tidak tahu berapa banyak perkara berada dalam array kita sudah.
Seperti jelas ada cara yang mungkin anda boleh melakukannya.
Anda boleh memulakan segala-galanya kepada NULL dan kemudian memeriksa NULL terkini,
tetapi satu perkara yang lebih mudah adalah hanya berkata, OK, menjejaki saiz.
Seperti yang saya tahu saya mempunyai empat elemen yang sedang saya, jadi perkara yang akan datang
yang kita pasang di, kami tidak akan menyimpan pada indeks 4.
Dan kemudian, sudah tentu, ini bermakna Anda telah berjaya menolak sesuatu
ke dalam tindanan anda, anda ingin meningkatkan saiz
supaya anda tahu di mana anda begitu bahawa anda boleh menolak lebih banyak perkara pada.
>> Jadi, jika kita cuba untuk pop sesuatu dari tumpukan,
apa yang mungkin menjadi perkara pertama yang yang kita mahu untuk memeriksa?
Anda sedang cuba untuk mengambil sesuatu dari stack.
Adakah anda pasti ada sesuatu dalam tumpukan anda?
Tidak.
Jadi apa yang kita mahu untuk memeriksa?
>> PENONTON: [didengar].
SPEAKER 1: Semak untuk saiz?
Saiz.
Oleh itu, kita mahu untuk memeriksa untuk melihat jika saiz kami adalah lebih besar daripada 0, OK?
Dan jika ya, maka kita mahu mengurangkan saiz kami oleh 0 dan kembali itu.
Mengapa?
>> Dalam kes pertama kita menolak, kami mendorong ia
ke saiz dan ukuran kemudian diperbarui.
Dalam hal ini, kami decrementing saiz dan kemudian mengambil it off, ia mencabut
dari array kita.
Mengapa kita boleh berbuat demikian?
Jadi jika saya mempunyai satu pada stack saya, apa yang akan menjadi saiz saya pada ketika itu?
1.
>> Dan di mana elemen 1 disimpan?
Apa indeks?
PENONTON: 0.
SPEAKER 1: 0.
Jadi dalam hal ini, kita sentiasa perlu membuat sure--
bukannya kembali saiz tolak 1, kerana kita
tahu bahawa kita adalah elemen akan disimpan pada 1 kurang
apa pun saiz kita, ini hanya mengambil mengurusnya.
Ia adalah cara yang sedikit lebih elegan.
Dan kami hanya pengurangan kami saiz dan kemudian kembali saiz.
Mmhmm?
>> PENONTON: Saya kira hanya secara umum, mengapa struktur data ini
memberi manfaat?
>> SPEAKER 1: Ia bergantung kepada konteks anda.
Jadi untuk beberapa teori, jika anda bekerja with-- OK,
saya melihat apakah ada satu yang menguntungkan yang memberi manfaat kepada lebih daripada di luar
CS.
Dengan tumpukan, bila-bila masa yang anda perlukan untuk mengesan sesuatu yang
adalah yang paling baru-baru ini ditambah adalah ketika Anda akan mahu menggunakan tumpukan.
>> Dan saya tidak boleh memikirkan baik yang contoh yang sekarang.
Tapi setiap kali yang paling baru-baru ini perkara yang paling penting bagi anda,
saat itulah tumpukan akan menjadi berguna.
Saya cuba untuk berfikir jika ada satu yang baik untuk ini.
Jika saya fikirkan satu contoh yang baik di akhirat 20 minit, saya pasti akan memberitahu anda.
>> Tapi secara keseluruhan, jika ada apa-apa, seperti saya katakan kebanyakan, di mana yang terkini
yang paling penting, yang mana tumpukan datang ke dalam bermain.
Manakala antrian adalah jenis yang sebaliknya.
Dan anjing-anjing kecil.
Bukankah ini yang besar, bukan?
Saya rasa seperti saya sepatutnya hanya mempunyai video kelinci
betul-betul di tengah-tengah bahagian untuk kalian
kerana ini adalah bahagian yang kuat.
>> Jadi antrian.
Pada dasarnya antrian adalah seperti garis.
Kalian saya gunakan pasti ini setiap hari, sama seperti di ruang makan kami.
Oleh itu, kita harus masuk dan mendapatkan nampan kami, saya
pasti anda perlu menunggu dalam talian meleretkan atau mendapatkan makanan anda.
>> Jadi perbezaan di sini adalah bahawa ini adalah FIFO.
Jadi jika LIFO kali terakhir dalam, pertama keluar, FIFO adalah masuk dahulu, keluar dahulu.
Jadi, ini adalah di mana apa sahaja yang anda meletakkan pada pertama adalah yang paling penting.
Jadi jika anda sedang menunggu di line-- yang boleh anda
bayangkan jika anda pergi ke pergi mendapatkan iPhone baru
dan ia adalah timbunan di mana orang terakhir selaras mendapatkannya pertama,
orang akan membunuh antara satu sama lain.
>> Jadi FIFO, kami semua sangat akrab dengan di dunia nyata di sini,
dan semuanya mempunyai kaitan dengan sebenarnya jenis mencipta baris ini seluruh
dan beratur struktur.
Jadi sedangkan dengan tumpukan, kita mempunyai dorongan dan pop.
Dengan barisan, kita mempunyai enqueue dan dequeue.
Jadi pada dasarnya berarti enqueue memasukkannya ke belakang,
dan cara-cara mengambil dequeue off dari depan.
Jadi struktur data kami adalah sedikit lebih rumit.
Kami mempunyai Hal kedua yang perlu diketahui.
>> Jadi tanpa kepala, ini betul-betul tumpukan, kan?
Ini adalah struktur yang sama sebagai stack.
Satu-satunya perkara yang berbeza sekarang ialah kita mempunyai kepala ini, yang apa yang anda fikir
akan menjejaki?
>> PENONTON: Yang pertama.
>> SPEAKER 1: Benar, yang Perkara pertama yang kita masukkan ke dalam.
Ketua barisan kami.
Siapa pun yang di baris pertama.
Baiklah, jadi jika kita melakukan enqueue.
Sekali lagi, dengan mana-mana struktur data,
kerana kita sedang berhadapan dengan array, kita perlu memeriksa jika kita mempunyai ruang.
>> Ini adalah jenis seperti saya memberitahu kalian, jika anda membuka fail,
anda perlu memeriksa null.
Dengan mana-mana tumpukan ini dan antrian, anda perlu
untuk melihat jika ada ruang kerana kita berurusan dengan pelbagai saiz tetap,
seperti yang kita lihat di sini-0, 1 semua hingga 5.
Jadi apa yang kita lakukan dalam kes cek untuk melihat apakah kita masih mempunyai ruang.
Apakah saiz kami kurang daripada kapasiti?
>> Jika demikian, kita perlu menyimpannya di ekor dan kita update ukuran kami.
Jadi apa yang mungkin ekor berada dalam kes ini?
Ia tidak jelas ditulis.
Bagaimana kita menyimpannya?
Apa yang akan menjadi ekor?
>> Jadi mari kita berjalan melalui contoh ini.
Jadi ini adalah pelbagai saiz 6, kan?
Dan kita miliki sekarang, saiz kami adalah 5.
Dan ketika kita memasukkannya ke dalam, ia akan untuk pergi ke dalam indeks kelima, kan?
Jadi menyimpan di ekor.
>> Satu lagi cara untuk menulis ekor akan hanya menjadi array kita pada indeks ukuran, kan?
Ini adalah saiz 5.
Perkara seterusnya yang akan masuk ke 5.
Cool?
OK.
Ia mendapat sedikit lebih rumit apabila kita mula bermain-main dengan kepala.
Ya?
>> PENONTON: Apakah itu bermakna kita akan diisytiharkan array yang
adalah lima elemen panjang dan kemudian kami menambahkan ke atasnya?
>> SPEAKER 1: No.
Jadi dalam hal ini, ini adalah tumpukan.
Ini akan dinyatakan sebagai array ukuran 6.
Dan dalam hal ini, kita hanya mempunyai satu ruangan kiri.
>> OK, jadi satu perkara yang dalam ini kes, jika kepala kita adalah pada 0,
maka kita hanya boleh menambahkannya pada saiz.
Tetapi ia menjadi sedikit rumit kerana sebenarnya, mereka
tidak mempunyai slaid yang untuk ini, jadi saya akan
untuk menarik satu kerana ia bukan sesederhana itu sebaik sahaja anda
mulai menyingkirkan hal.
Jadi sedangkan dengan tumpukan Anda hanya pernah mempunyai
bimbang tentang apa saiz adalah apabila anda menambah sesuatu pada,
dengan barisan yang anda juga perlu membuat memastikan bahawa kepala anda diambil kira,
kerana satu perkara yang sejuk kira-kira antrian adalah bahawa jika anda tidak pada kapasiti,
Anda benar-benar boleh membuat ia membungkus.
>> OK, jadi satu thing-- oh, ini adalah kapur mengerikan.
Satu perkara yang perlu dipertimbangkan adalah kes itu.
Kami hanya akan melakukan lima.
OK, jadi kita akan mengatakan kepala di sini.
Ini adalah 0, 1, 2, 3, 4.
>> Kepala ada di sana, dan sila memiliki hal-hal di dalamnya.
Dan kami ingin menambahkan sesuatu, kan?
Jadi perkara yang kita perlu tahu ialah kepala sentiasa
akan bergerak dengan cara ini dan maka gelung kembali sekitar, OK?
>> Jadi barisan ini mempunyai ruang, bukan?
Ia mempunyai ruang di awal-awal lagi, jenis yang bertentangan dengan ini.
Jadi apa yang perlu kita lakukan adalah kita perlu mengira ekor.
Jika anda tahu bahawa anda kepala tidak bergerak, ekor
hanya array di indeks ukuran.
>> Tetapi dalam realiti, jika anda menggunakan antrian, kepala anda mungkin sedang dikemas kini.
Jadi apa yang anda perlu lakukan adalah benar-benar menghitung ekor.
Jadi apa yang kita lakukan adalah formula ini di sini, yang saya akan memberitahu anda
semua berfikir tentang, dan maka kita akan bercakap tentang hal itu.
Jadi, ini adalah kapasiti.
>> Jadi ini akan benar-benar memberi anda cara untuk melakukannya.
Kerana dalam kes ini, apa?
Pusat kami pada 1, saiz kami adalah 4.
Jika kita mod yang sebanyak 5, kita akan mendapat 0, yang di mana kami perlu input itu.
>> Jadi, dalam keadaan yang akan datang, jika kita melakukan ini,
kita kata, OK, mari kita dequeue sesuatu.
Kami dequeue ini.
Kami mengambil elemen ini, kan?
>> Dan sekarang kepala kita menunjuk sini, dan kami ingin menambah dalam perkara lain.
Ini pada dasarnya adalah belakang garis kita, kan?
Antrian dapat membungkus array.
Itulah salah satu perbezaan utama.
Tumpukan, anda tidak boleh melakukan ini.
>> Dengan antrian, anda boleh kerana apa yang penting
adalah bahawa anda tahu apa yang ditambah yang paling baru-baru ini.
Oleh kerana semuanya akan ditambahkan dalam arah ke kiri ini, dalam kes ini,
dan kemudian membungkus, anda boleh terus menyediakan elemen-elemen baru
di depan array kerana ia tidak benar-benar
hadapan array lagi.
Anda boleh berfikir dari awal array sebagai mana kepala anda sebenarnya.
>> Jadi formula ini adalah bagaimana anda mengira ekor anda.
Adakah ini masuk akal?
OK.
OK, dequeue, dan kemudian kalian punya 10 minit
untuk bertanyakan soalan klarifikasi anda mahu, kerana saya tahu ia adalah gila.
>> Baiklah, jadi dalam way-- yang sama Saya tidak tahu jika anda semua perasan,
tetapi CS adalah tentang corak.
Hal yang hampir sama, hanya dengan tweak kecil.
Jadi perkara yang sama di sini.
Kita perlu menyemak untuk melihat jika kita benar-benar mempunyai sesuatu dalam barisan kita, kan?
Berkata, OK, adalah saiz kami lebih besar dari 0?
Sejuk.
>> Jika kita lakukan, maka kita bergerak kepala kita, yang adalah apa yang saya hanya ditunjukkan di sini.
Kami untuk mengemaskinikan kepala kita untuk menjadi satu lagi.
Dan kemudian kita pengurangan kami saiz dan kembali elemen.
>> Ada banyak lagi yang konkrit kod pada study.cs50.net,
dan saya sangat menyarankan akan melaluinya jika anda mempunyai masa,
walaupun itu hanya pseudo-kod.
Dan jika kalian ingin berbicara melalui bahawa dengan saya satu-satu, sila beritahu saya
tahu.
Saya dengan senang hati.
Struktur data, jika Anda mengambil CS 124, anda akan
tahu bahawa struktur data menjadi sangat menyenangkan dan ini baru sahaja bermula.
>> Jadi saya tahu ia sukar.
Tidak apa-apa.
Kita berjuang.
Aku masih.
Jadi jangan bimbang terlalu banyak tentang hal itu.
>> Tetapi itu pada asasnya anda crash kursus dalam struktur data.
Aku tahu itu banyak.
Adakah terdapat apa-apa yang kita ingin pergi lagi?
Apa pun yang kita mahu bercakap melalui?
Ya?
>> PENONTON: Sebagai contoh itu, jadi ekor baru adalah pada 0 lebih dari itu?
SPEAKER 1: Ya.
PENONTON: OK.
Jadi kemudian akan melalui, Anda harus 1 ditambah 4 or--
>> SPEAKER 1: Jadi, anda telah berkata, apabila kita mahu pergi melakukan ini lagi?
PENONTON: Ya.
Jadi jika anda telah mencari out-- mana Anda mengira ekor dari dalam itu?
>> SPEAKER 1: Jadi ekor adalah dalam- saya berubah ini.
Jadi, dalam contoh ini di sini, ini adalah array kita sedang melihat, OK?
Oleh itu, kita mempunyai perkara-perkara dalam 1, 2, 3, dan 4.
Jadi kita mempunyai kepala kita adalah sama dengan 1 pada ketika ini, dan saiz kami adalah sama dengan 4
pada ketika ini, kan?
>> Anda semua setuju itu yang terjadi?
Oleh itu, kita melakukan kepala plus saiz, yang memberi kita 5, dan kemudian kami mod sebanyak 5.
Kita mendapat 0, yang memberitahu kita bahawa 0 adalah di mana ekor kita, di mana kita mempunyai ruang.
>> PENONTON: Apa topi?
>> SPEAKER 1: Keupayaan.
Maaf.
Jadi itulah saiz array.
Ya?
>> PENONTON: [didengar] sebelum kita kembali elemen?
>> SPEAKER 1: Jadi kita memindahkan kepala atau kembali masa ini?
Jadi, jika kita bergerak satu, pengurangan saiz?
Tunggu.
Saya pasti lupa lain.
Tidak apa-apa.
Tidak ada formula lain.
Ya, anda akan mahu kembali kepala dan kemudian memindahkannya kembali.
>> PENONTON: OK, kerana Pada ini mata, kepala adalah pada 0,
dan kemudian anda ingin kembali Isi 0 dan kemudian membuat kepala 1?
>> SPEAKER 1: Benar.
Saya rasa terdapat satu lagi jenis formula seperti ini.
Saya tidak mempunyai ia di atas kepala saya sebagai Saya tidak mahu memberikan satu yang salah.
Tetapi saya rasa ia benar-benar berlaku ke berkata, OK, menyimpan element-- ini apa pun yang
elemen kepala ini is-- pengurangan anda saiz, gerakkan kepala anda ke atas, dan pulangan
apa sahaja unsur yang.
Itu benar berlaku.
OK.
Saya rasa seperti ini bukan seperti most-- anda tidak
akan berjalan keluar dari sini seperti, ya, aku tahu cuba.
Saya mendapat semuanya.
Tidak apa-apa.
Aku janji.
Tetapi struktur data adalah sesuatu yang ia mengambil banyak masa untuk membiasakan diri.
Mungkin salah satu yang paling sukar perkara, saya fikir, dalam kursus ini.
>> Jadi ia pasti mengambil masa pengulangan dan melihat saya at--
tidak benar-benar tahu daftar terkait sampai saya melakukan terlalu banyak dengan mereka,
dengan cara yang sama bahawa saya tidak benar-benar memahami petunjuk
sehingga aku sudah mengajar selama dua tahun dan melakukan pşet saya sendiri dengannya.
Ia mengambil banyak pengulangan dan masa.
Dan akhirnya, ia jenis akan klik.
>> Tetapi dalam pada itu, jika anda mempunyai jenis dari pemahaman yang tinggi tentang apa yang
ini lakukan, kebaikan mereka dan cons-- yang adalah apa yang
kita benar-benar cenderung menekankan, terutama dalam perjalanan intro.
Seperti, mengapa kita akan menggunakan cuba lebih array?
Seperti, apakah positif dan negatif dari masing-masing?
>> Dan memahami keseimbangan antara setiap struktur ini
adalah apa yang lebih penting sekarang.
Mungkin ada yang gila soalan atau dua itu
akan meminta anda untuk melaksanakan tolak atau melaksanakan pop atau enqueue dan dequeue.
Tetapi bagi sebahagian besar, yang mempunyai pemahaman yang lebih tinggi dan lebih
dari pemahaman intuitif adalah lebih penting daripada benar-benar
mampu untuk melaksanakannya.
>> Ia akan menjadi benar-benar luar biasa jika anda semua mampu keluar dan pergi melaksanakan cuba,
tetapi kita faham ia tidak semestinya perkara yang paling wajar sekarang.
Tetapi anda boleh dalam Serangga anda, jika anda mahu kepada, dan kemudian anda akan mendapat latihan,
dan kemudian mungkin anda akan benar-benar memahaminya.
Ya?
>> PENONTON: OK, jadi mana yang kita dimaksudkan untuk digunakan dalam Serangga ini?
Adakah saya perlu menggunakan salah satu daripada mereka?
SPEAKER 1: Ya.
Jadi, anda mempunyai pilihan anda.
Saya rasa dalam hal ini, kita dapat bercakap tentang Serangga yang sedikit
kerana saya berlari melalui ini.
Jadi dalam Serangga anda, anda mempunyai anda pilihan mencoba atau jadual hash.
Sesetengah orang akan cuba dan menggunakan penapis mekar,
tetapi mereka secara teknikal tidak betul.
Kerana sifat kebarangkalian mereka, mereka memberikan hasil positif palsu kadang-kadang.
Mereka melihat sejuk ke dalam, walaupun.
Sangat mengesyorkan mencari pada mereka sekurang-kurangnya.
Tetapi anda mempunyai pilihan anda antara jadual hash dan cuba.
Dan itu akan berada di tempat anda memuatkan kamus anda.
>> Dan anda akan perlu untuk memilih fungsi hash anda,
Anda akan perlu untuk memilih berapa banyak baldi pada anda, dan ia akan berubah-ubah.
Seperti jika anda mempunyai lebih ember, mungkin itu akan berjalan lebih cepat.
Tapi mungkin anda membuang banyak ruang dengan cara itu, walaupun.
Anda perlu mencari jalan keluar.
Mmhmm?
>> PENONTON: Anda berkata sebelum itu kita boleh menggunakan fungsi-fungsi hash yang lain,
bahwa kita tidak perlu membuat fungsi hash?
>> SPEAKER 1: Ya, betul.
Jadi secara harfiah untuk fungsi hash anda, seperti google "fungsi hash"
dan mencari beberapa yang sejuk.
Anda tidak diharapkan untuk membina fungsi hash anda sendiri.
Orang-orang menghabiskan mereka tesis tentang perkara-perkara ini.
>> Jadi jangan risau tentang membina anda sendiri.
Cari satu talian untuk memulakan dengan.
Sebahagian daripada mereka yang anda perlu memanipulasi sedikit
untuk membuat jenis pulangan pasti cocok dan barang kecil, jadi pada mulanya,
Saya akan mengesyorkan menggunakan sesuatu benar-benar mudah yang mungkin hanya
hash pada huruf pertama.
Dan kemudian sekali anda mempunyai kerja yang, menggabungkan fungsi hash yang lebih sejuk.
Mmhmm?
>> PENONTON: Apakah yang cuba menjadi atau cekap tetapi hanya lebih sukar untuk, like--
>> SPEAKER 1: Jadi cuba, saya fikir, secara intuitif keras untuk melaksanakan
tetapi sangat cepat.
Walau bagaimanapun, mengambil lebih banyak ruang.
Sekali lagi, anda boleh mengoptimumkan kedua-dua mereka yang berada dalam cara yang berbeza dan ada cara kepada-
PENONTON: Bagaimana kita dinilai pada ini?
Adakah ia masalah-
>> SPEAKER 1: Jadi anda dinilai dengan cara biasa.
Anda akan dinilai pada reka bentuk.
Ke mana sahaja yang anda lakukan, anda mahu pastikan itu sebagai elegan kerana ia boleh menjadi
dan seefisien mungkin.
Tetapi jika anda memilih yang cuba atau hash meja, selama ia berfungsi,
kami gembira dengan itu.
Dan jika anda menggunakan sesuatu yang hash surat pertama, tidak apa-apa,
seperti mungkin seperti reka bentuk-bijak.
Kami juga mencapai titik dalam semester-- ini
Saya tidak tahu jika anda orang noticed-- jika anda
gred Serangga menurun sedikit kerana reka bentuk dan yang lainnya,
yang baik-baik saja.
Ia sampai ke titik di mana anda program yang semakin rumit.
Ada lebih banyak tempat anda boleh memperbaiki.
>> Jadi ia adalah perkara biasa.
Ia bukan bahawa anda melakukan lebih buruk pada Serangga anda.
Hanya saja kita yang lebih keras pada anda sekarang.
Jadi semua orang perasaan itu.
Saya hanya dinilai semua pşet anda.
Aku tahu semua orang berasa ia.
>> Jadi jangan bimbang tentang itu.
Dan jika anda mempunyai sebarang soalan mengenai pşet sebelumnya atau cara anda boleh meningkatkan,
Saya cuba dan komen yang spesifik tempat, tetapi kadang-kadang lewat
dan saya mendapat letih.
Apakah ada perkara-perkara lain tentang struktur data?
Saya pasti anda semua tidak benar-benar mahu bercakap tentang mereka lagi,
tetapi jika ada, aku senang pergi atas mereka, serta apa-apa
dari kuliah yang lepas minggu atau minggu lepas.
>> Saya tahu minggu lepas adalah kajian semua, jadi kita mungkin telah melangkau lebih kajian beberapa
dari kuliah.
Apa-apa soalan lain yang boleh menjawab?
OK, baiklah.
Nah, kalian keluar 15 minit awal.
>> Saya berharap ini adalah separuh membantu sekurang-kurangnya, dan saya akan melihat kalian minggu depan,
atau Kamis waktu pejabat.
Adakah terdapat permintaan untuk makanan ringan untuk minggu depan, ia adalah perkara yang?
Oleh kerana saya terlupa gula-gula hari ini.
Dan aku membawa gula-gula lepas minggu, tetapi ia adalah hari Columbus,
jadi ada seperti enam orang yang mempunyai empat beg gula-gula kepada diri mereka sendiri.
Saya dapat membawa Starbursts lagi jika anda suka.
Starbursts?
OK, bunyi yang baik.
Mempunyai hari yang hebat, orang-orang.