[MUSIC PLAYING]
SPEAKER 1: Baiklah.
Semua orang selamat datang kembali ke bagian.
Saya harap Anda semua sukses pulih dari kuis Anda
dari minggu lalu.
Aku tahu itu sedikit gila di kali.
Seperti yang saya katakan sebelumnya, jika Anda dalam standar deviasi,
tidak benar-benar khawatir tentang hal itu, terutama untuk bagian yang kurang nyaman.
Itu adalah tentang di mana Anda harus.
>> Jika Anda melakukan besar, maka mengagumkan.
Kudos kepada Anda.
Dan jika Anda merasa seperti Anda perlu sedikit bantuan lebih lanjut, silakan
merasa bebas untuk mencapai ke salah satu TF.
Kami semua di sini untuk membantu.
>> Itu sebabnya kita mengajar.
Itulah sebabnya aku di sini setiap hari Senin untuk Anda orang dan di kantor jam pada hari Kamis.
Jadi jangan ragu untuk membiarkan saya tahu jika Anda khawatir tentang apa pun
atau jika ada sesuatu di kuis bahwa Anda benar-benar ingin untuk mengatasi.
>> Jadi agenda untuk hari ini adalah semua tentang struktur data.
Beberapa di antaranya hanya akan menjadi hanya untuk mendapatkan Anda akrab dengan ini.
Anda mungkin tidak pernah menerapkan mereka di kelas ini.
Beberapa dari mereka Anda akan, seperti untuk pset ejaan Anda.
>> Anda akan memiliki pilihan Anda antara tabel hash dan mencoba.
Jadi kita akan pasti akan atas mereka.
Ini akan menjadi pasti lebih jenis dari bagian tingkat tinggi hari ini, meskipun,
karena ada banyak dari mereka, dan jika kami pergi ke rincian implementasi
pada semua ini, kita tidak akan bahkan melewati daftar terkait
dan mungkin sedikit tabel hash.
>> Jadi beruang dengan saya.
Kami tidak akan melakukan sebanyak coding kali ini.
Jika Anda memiliki pertanyaan tentang hal itu atau Anda ingin melihatnya dilaksanakan
atau mencobanya sendiri, Saya merekomendasikan
akan study.cs50.net, yang memiliki contoh semua ini.
Ini akan memiliki PowerPoint saya dengan catatan bahwa kita
cenderung menggunakan serta beberapa pemrograman latihan, terutama untuk hal-hal
seperti daftar terhubung dan biner pohon tumpukan dan isyarat.
Jadi sedikit tingkat yang lebih tinggi, yang mungkin bagus untuk kalian.
>> Maka dengan itu, kita akan memulai.
Dan juga, kuis yes--.
Saya pikir sebagian besar dari Anda yang berada di Bagian saya memiliki kuis Anda,
tapi setiap orang datang atau alasan tertentu Anda tidak, mereka di sini, di depan.
>> Jadi terkait daftar.
Aku tahu semacam ini berjalan untuk kembali sebelum kuis Anda.
Itu adalah minggu sebelum bahwa kita belajar tentang hal ini.
Tapi dalam kasus ini, kita hanya akan pergi sedikit lebih mendalam.
>> Jadi mengapa mungkin kita memilih linked list lebih dari array?
Apa yang membedakan mereka?
Ya?
>> AUDIENCE: Anda dapat memperluas terkait daftar versus ukuran tetap array ini.
SPEAKER 1: Benar.
Sebuah array tetap memiliki ukuran sedangkan linked list memiliki ukuran variabel.
Jadi jika kita tidak tahu bagaimana banyak kita ingin menyimpan,
linked list memberikan kita besar cara untuk melakukan itu karena kita hanya bisa
menambahkan node lain dan menambah node lain dan menambah node lain.
Tapi apa yang mungkin menjadi trade-off?
Apakah ada yang ingat trade-off antara array dan linked list?
Mmhmm?
>> AUDIENCE: Anda harus pergi melalui semua jalan
melalui linked list menemukan elemen dalam daftar.
Dalam sebuah array, Anda dapat hanya menemukan elemen.
>> SPEAKER 1: Benar.
Jadi dengan arrays--
>> AUDIENCE: [tak terdengar].
>> SPEAKER 1: Dengan array, kita memiliki apa yang disebut akses acak.
Berarti jika kita ingin apa yang pernah titik kelima daftar
atau titik kelima kami array, kita bisa meraihnya.
Jika itu adalah linked list, kita memiliki iterate melalui, kan?
Jadi mengakses sebuah elemen dalam array adalah waktu yang konstan,
sedangkan dengan linked list itu akan kemungkinan besar akan waktu linier karena mungkin
Elemen kami adalah semua jalan di akhir.
Kami harus mencari melalui segala sesuatu.
Jadi dengan semua data ini struktur kita akan
untuk menghabiskan sedikit lebih banyak waktu pada, apa saja plus dan negatif.
Kapan kita ingin menggunakan satu atas yang lain?
Dan itu semacam itu hal yang lebih besar untuk mengambil.
>> Jadi kita harus di sini definisi node.
Hal ini seperti salah satu unsur dalam linked list kita, kan?
Jadi kita semua kenal dengan struct typedef kami,
yang kami pergi di review terakhir kali.
Itu pada dasarnya hanya menciptakan Jenis data lain yang dapat kita gunakan.
>> Dan dalam hal ini, itu beberapa simpul yang akan memegang beberapa integer dalam.
Dan kemudian apa bagian kedua di sini?
Siapa?
>> AUDIENCE: [tak terdengar].
>> SPEAKER 1: Ya.
Ini adalah pointer ke node berikutnya.
Jadi ini benar-benar harus di sini.
Ini adalah pointer tipe node ke hal berikutnya.
Dan itulah yang mereka meliputi simpul kami.
Keren.
>> Baiklah, jadi dengan pencarian, karena kami hanya mengatakan sebelum tangan, jika Anda
akan mencari melalui, Anda harus benar-benar iterate
melalui daftar link.
Jadi jika kita sedang mencari nomor 9, kita akan mulai dari kepala kita
dan yang menunjuk kami di awal dari linked list kita, kan?
Dan kita katakan, OK, apakah ini simpul berisi nomor 9?
Tidak ada?
>> Baiklah, pergi ke yang berikutnya.
Mengikutinya.
Apakah itu berisi nomor 9?
Tidak.
Ikuti berikutnya.
>> Jadi kita harus benar-benar iterate melalui linked list kami.
Kita tidak bisa hanya pergi langsung ke tempat 9 adalah.
Dan jika kalian benar-benar ingin melihat beberapa pseudo-code di atas sana.
Kami memiliki beberapa fungsi pencarian di sini yang mengambil in-- apa yang dibutuhkan dalam?
Bagaimana menurut Anda?
Begitu mudah satu.
Apa ini?
AUDIENCE: [tak terdengar].
SPEAKER 1: Jumlah yang kita cari.
Benar?
Dan apa yang akan ini sesuai dengan?
Ini adalah pointer ke?
>> AUDIENCE: Sebuah node.
>> SPEAKER 1: Sebuah node ke dalam daftar bahwa kita sedang melihat, kan?
Jadi kita memiliki beberapa node pointer di sini.
Ini adalah titik yang akan sebenarnya iterate melalui daftar kami.
Kami mengaturnya sama dengan daftar karena itu hanya
pengaturannya sama dengan mulai dari linked list kami.
>> Dan sementara itu tidak NULL, sementara kita masih memiliki hal-hal dalam daftar kami,
memeriksa untuk melihat apakah node yang memiliki jumlah yang kita cari.
Kembali benar.
Jika tidak, memperbarui, kan?
>> Jika NULL, kami keluar kami while dan return false
karena itu berarti kita belum menemukannya.
Apakah setiap orang mendapatkan bagaimana yang bekerja?
OK.
>> Jadi dengan penyisipan, Anda memiliki tiga cara yang berbeda.
Anda dapat tambahkan, Anda dapat menambahkan dan Anda dapat memasukkan ke dalam berbagai macam.
Dalam hal ini, kami akan melakukan tambahkan sebuah.
Apakah ada yang tahu bagaimana mereka tiga kasus mungkin berbeda?
>> Jadi tambahkan berarti bahwa Anda menempatkan itu di depan daftar Anda.
Jadi itu berarti bahwa tidak peduli apa simpul Anda, tidak peduli
apa nilai tersebut, Anda akan untuk meletakkannya di sini, di depan, OK?
Ini akan menjadi yang pertama elemen dalam daftar Anda.
>> Jika Anda tambahkan, itu akan untuk pergi ke belakang daftar Anda.
Dan masukkan ke dalam berbagai macam berarti Anda akan menempatkan benar-benar ke tempat
di mana itu membuat daftar Anda terhubung diurutkan.
Sekali lagi, bagaimana Anda menggunakan mereka dan saat Anda menggunakan
mereka akan bervariasi tergantung pada kasus Anda.
Jika tidak perlu diurutkan, tambahkan cenderung
menjadi apa yang kebanyakan orang digunakan karena Anda tidak
harus melalui seluruh daftar untuk menemukan akhir untuk menambahkannya, kan?
Anda hanya dapat menempel tepat di.
>> Jadi kita akan pergi melalui penyisipan 1 sekarang.
Jadi satu hal yang aku akan sangat merekomendasikan pada pset ini
adalah untuk menarik hal-hal, seperti biasa.
Ini sangat penting bahwa Anda memperbarui pointer Anda dalam urutan yang benar
karena jika Anda memperbarui mereka sedikit rusak,
Anda akan berakhir kehilangan bagian dari daftar Anda.
>> Jadi misalnya, dalam hal ini, kami mengatakan kepala untuk hanya titik untuk 1.
Jika kita hanya melakukan itu tanpa menyimpan 1 ini,
kita tidak tahu apa 1 harus menunjuk ke sekarang
karena kita sudah kehilangan apa kepala menunjuk.
Jadi, satu hal yang perlu diingat ketika Anda sedang melakukan tambahkan sebuah
adalah untuk menyelamatkan apa yang kepala poin pertama,
kemudian menetapkan kembali, dan kemudian memperbarui apa node baru Anda harus menunjuk ke.
Dalam hal ini, ini adalah salah satu cara untuk melakukannya.
>> Jadi jika kita telah melakukannya dengan cara ini di mana kita hanya ditugaskan kembali kepala,
kita kehilangan dasarnya kami seluruh daftar, kan?
Salah satu cara untuk melakukannya adalah untuk memiliki 1 poin untuk berikutnya, dan kemudian memiliki titik kepala ke 1.
Atau Anda dapat melakukan jenis seperti penyimpanan sementara, yang saya bicarakan.
>> Tapi pemindahan Anda pointer dalam urutan yang benar
akan menjadi sangat, sangat penting untuk pset ini.
Jika tidak, Anda akan memiliki hash tabel atau mencoba yang hanya akan menjadi
hanya sebagian dari kata-kata yang Anda inginkan dan kemudian mmhmm you're--?
AUDIENCE: Apa sementara hal penyimpanan yang Anda bicarakan?
SPEAKER 1: The penyimpanan sementara.
Jadi pada dasarnya lain cara Anda bisa melakukan ini
adalah menyimpan kepala sesuatu, seperti menyimpannya variabel sementara.
Menetapkan ke 1 dan kemudian memperbarui 1 ke titik
apa pun kepala digunakan untuk menunjuk ke.
Cara ini jelas lebih elegan karena Anda
tidak membutuhkan nilai sementara, tapi hanya menawarkan cara lain untuk melakukannya.
Dan kita benar-benar memiliki beberapa kode untuk ini.
Jadi untuk linked list, kita benar-benar memiliki beberapa kode.
Jadi masukkan di sini, ini mengawali.
Jadi ini masuk itu di kepala.
>> Sehingga hal pertama, Anda perlu buat node baru Anda, tentu saja,
dan memeriksa NULL.
Selalu baik.
Dan kemudian Anda harus menetapkan nilai-nilai.
Setiap kali Anda membuat node baru, Anda tidak tahu apa itu menunjuk ke depan,
sehingga Anda ingin menginisialisasi ke NULL.
Jika tidak berakhir menunjuk ke sesuatu lain, hal itu akan ditugaskan kembali dan itu baik-baik saja.
Jika itu hal pertama dalam daftar, dibutuhkan
untuk menunjuk ke NULL karena itulah akhir dari daftar.
>> Jadi untuk memasukkannya, kita lihat di sini kami menugaskan nilai berikutnya node kami
untuk menjadi apa pun kepala, yang adalah apa yang kami punya di sini.
Itulah apa yang baru saja kami lakukan.
Dan kemudian kita menugaskan kepala ke titik ke node baru, karena ingat,
baru beberapa pointer ke node, dan itulah apa kepala.
Itulah mengapa kami memiliki panah accessor ini.
Keren?
Mmhmm?
>> AUDIENCE: Apakah kita harus menginisialisasi berikutnya baru ke NULL pertama,
atau bisa kita hanya menginisialisasi ke kepala?
>> SPEAKER 1: berikutnya Baru harus NULL untuk memulai
karena Anda tidak tahu di mana itu akan menjadi.
Juga, ini adalah jenis persis seperti paradigma.
Anda menetapkan sama dengan NULL hanya untuk membuat memastikan bahwa semua basis Anda tertutup
sebelum Anda melakukan penugasan sehingga Anda selalu dijamin bahwa hal itu akan
menunjuk ke nilai tertentu dibandingkan seperti nilai sampah.
Karena, ya, kita memberikan baru berikutnya secara otomatis,
tapi lebih seperti sebuah praktik yang baik untuk menginisialisasi
dengan cara itu dan kemudian menetapkan kembali.
>> OK, jadi ganda terkait daftar sekarang.
Apa yang kita pikirkan?
Apa yang berbeda dengan ganda terkait daftar?
>> Jadi dalam daftar terhubung, kita bisa hanya bergerak dalam satu arah, kan?
Kami hanya memiliki berikutnya.
Kami hanya bisa maju.
>> Dengan linked list ganda, kami juga bisa bergerak mundur.
Jadi kita harus tidak hanya nomor yang ingin kita simpan,
kami memiliki di mana ia menunjuk ke depan dan di mana kami hanya datang dari.
Jadi ini memungkinkan untuk beberapa traversal yang lebih baik.
>> Node Jadi ganda terkait, sangat mirip, kan?
Hanya bedanya sekarang kita memiliki berikutnya dan sebelumnya.
Ini satu-satunya perbedaan.
>> Jadi jika kita tambahkan atau kita append-- tidak memiliki kode untuk ini sampai di sini-
tetapi jika Anda adalah untuk mencoba dan masukkan, yang penting
adalah Anda perlu membuat Pastikan Anda menetapkan
baik Anda sebelumnya dan Anda pointer berikutnya dengan benar.
Jadi dalam hal ini, Anda akan tidak hanya menginisialisasi berikutnya,
Anda menginisialisasi sebelumnya.
Jika kita berada di puncak daftar, kita tidak hanya akan membuat kepala sama baru,
tetapi harus kami sebelumnya baru menunjuk ke kepala, kan?
>> Itulah satu-satunya perbedaan.
Dan jika Anda ingin lebih banyak latihan dengan ini dengan daftar link, dengan memasukkan,
dengan menghapus, dengan insert ke daftar berbagai macam,
silahkan periksa study.cs50.net.
Ada sekelompok latihan besar.
Saya sangat merekomendasikan mereka.
Saya berharap kami punya waktu untuk pergi melalui mereka tapi ada banyak struktur data
untuk melewati.
>> OK, jadi tabel hash.
Ini mungkin yang paling berguna bit untuk pset Anda
di sini karena Anda akan menjadi menerapkan salah satu dari ini, atau mencoba.
Saya sangat suka tabel hash.
Mereka cukup keren.
>> Jadi pada dasarnya apa terjadi adalah tabel hash
adalah ketika kita benar-benar membutuhkan cepat penyisipan, penghapusan, dan pencarian.
Mereka adalah hal-hal yang kita memprioritaskan dalam tabel hash.
Mereka bisa mendapatkan cukup besar, tapi karena kami akan melihat dengan mencoba,
ada hal-hal yang jauh lebih besar.
>> Tapi pada dasarnya, semua hash tabel adalah fungsi hash
yang memberitahu Anda yang ember untuk menempatkan setiap data Anda, masing-masing elemen di.
Cara mudah untuk memikirkan tabel hash adalah bahwa itu hanya ember hal,
kan?
Jadi, ketika Anda menyortir hal-hal dengan seperti huruf pertama dari nama mereka,
itu jenis seperti tabel hash.
>> Jadi jika saya ke grup kalian adalah ke dalam kelompok siapa nama ini dimulai
dengan A di sini, atau siapa pun yang ulang tahun adalah pada bulan Januari, Februari, Maret,
apa pun, yang secara efektif membuat tabel hash.
Hanya saja menciptakan ember yang Anda menyortir elemen Anda ke
sehingga Anda dapat menemukan mereka lebih mudah.
Jadi cara ini ketika saya membutuhkan untuk menemukan salah satu dari Anda,
Saya tidak harus mencari melalui masing-masing nama Anda.
Aku bisa seperti, oh, aku tahu bahwa Ulang tahun Danielle adalah in--
AUDIENCE: --April.
SPEAKER 1: April.
Jadi saya melihat pada bulan April saya ember, dan dengan sedikit keberuntungan,
dia akan menjadi satu-satunya di sana dan waktu saya konstan dalam arti bahwa,
sedangkan jika saya harus melihat melalui sejumlah besar orang,
itu akan memakan waktu lebih lama.
Jadi tabel hash yang benar-benar hanya ember.
Cara mudah untuk memikirkan mereka.
>> Jadi hal yang sangat penting tentang tabel hash adalah fungsi hash.
Jadi hal-hal yang saya hanya berbicara tentang, seperti huruf pertama Anda nama pertama Anda
atau bulan ulang tahun Anda, ini adalah ide yang
benar-benar berkorelasi dengan fungsi hash.
Ini hanya cara untuk memutuskan yang ember Anda elemen tidak masuk ke, OK?
Jadi untuk pset ini, Anda dapat melihat hampir semua fungsi hash yang Anda inginkan.
>> Tidak harus Anda sendiri.
Ada beberapa yang benar-benar keren out ada yang melakukan segala macam gila matematika.
Dan jika Anda ingin membuat Anda pemeriksa ejaan super cepat,
Saya pasti akan melihat ke dalam salah satu dari mereka.
>> Tapi ada juga yang sederhana, seperti menghitung
jumlah dari kata-kata, seperti setiap huruf memiliki nomor.
Menghitung penjumlahan.
Yang menentukan ember.
Mereka juga memiliki orang-orang mudah yang sama seperti semua A di sini,
semua B di sini.
Salah satu dari mereka.
>> Pada dasarnya, itu hanya memberitahu Anda yang indeks array elemen Anda harus masuk ke dalam.
Hanya memutuskan bucket-- yang itu semua fungsi hash adalah.
Jadi di sini kita memiliki contoh yang hanya huruf pertama dari string
bahwa saya hanya berbicara tentang.
>> Jadi Anda memiliki beberapa hash itu hanya huruf pertama dari string dikurangi A,
yang akan memberi Anda beberapa angka antara 0 dan 25.
Dan apa yang ingin Anda lakukan adalah pastikan bahwa ini mewakili
ukuran hash Anda table-- berapa banyak ember ada.
Dengan banyak dari fungsi hash, mereka
akan nilai-nilai kembali yang mungkin jauh di atas jumlah ember
bahwa Anda benar-benar memiliki dalam tabel hash Anda,
sehingga Anda perlu membuat yakin dan mod oleh mereka.
Jika tidak, itu akan berkata, oh, itu harus dalam ember 5.000
tapi Anda hanya memiliki 30 ember dalam tabel hash Anda.
Dan tentu saja, kita semua tahu itu akan menghasilkan beberapa kesalahan gila.
Jadi pastikan untuk mod oleh ukuran tabel hash Anda.
Keren.
Jadi tabrakan.
Apakah semua orang baik sejauh ini?
Mmhmm?
>> AUDIENCE: Mengapa itu kembali seperti nilai besar?
>> SPEAKER 1: Tergantung pada algoritma bahwa fungsi hash Anda menggunakan.
Beberapa dari mereka akan melakukan perkalian gila.
Dan itu semua tentang mendapatkan bahkan distribusi,
sehingga mereka melakukan beberapa benar-benar hal-hal gila kadang-kadang.
Itu saja.
Ada lagi?
OK.
>> Jadi tabrakan.
Pada dasarnya, seperti yang saya katakan sebelumnya, dalam skenario kasus terbaik,
setiap ember saya melihat ke dalam adalah akan memiliki satu hal,
jadi saya tidak harus melihat sama sekali, kan?
Aku juga tahu itu ada atau itu tidak, dan itulah apa yang kita inginkan.
Tetapi jika kita memiliki puluhan ribu titik data dan kurang dari jumlah itu
ember, kita akan memiliki tabrakan di mana akhirnya sesuatu
akan harus berakhir di ember yang sudah memiliki unsur.
>> Jadi pertanyaannya adalah, apa yang kita lakukan dalam kasus ini?
Apa yang kita lakukan?
Kita sudah memiliki sesuatu di sana?
Apakah kita buang saja keluar?
>> Tidak.
Kami harus menjaga mereka berdua.
Jadi cara yang kita biasanya melakukan itu adalah apa?
Bagaimana struktur data yang kami hanya berbicara tentang?
AUDIENCE: Daftar Linked.
SPEAKER 1: Sebuah linked list.
Jadi sekarang, bukan masing-masing ember hanya memiliki satu elemen,
itu akan berisi daftar link dari unsur-unsur yang hash ke dalamnya.
OK, tidak semua orang mendapatkan semacam ide itu?
Karena kita tidak bisa memiliki sebuah array karena kita tidak tahu berapa banyak hal
akan berada di sana.
Sebuah linked list memungkinkan kita untuk baru saja jumlah yang tepat yang
adalah hash ke dalam ember itu, kan?
>> Jadi linear probing adalah pada dasarnya idea-- ini
itu salah satu cara untuk menangani tabrakan.
Apa yang dapat Anda lakukan adalah jika, dalam hal ini kasus, berry hash ke 1
dan kita sudah memiliki sesuatu di sana, Anda hanya
terus ke bawah sampai Anda menemukan slot kosong.
Itu salah satu cara untuk menanganinya.
Cara lain untuk menangani itu dengan apa yang kita hanya
called-- yang terkait daftar disebut chaining.
>> Jadi ide ini bekerja jika tabel hash Anda Anda berpikir
jauh lebih besar daripada mengatur data Anda atau jika Anda
ingin mencoba dan meminimalkan chaining sampai benar-benar diperlukan.
Jadi satu hal yang linear menyelidik jelas berarti
bahwa fungsi hash Anda tidak cukup berguna
karena Anda akan berakhir dengan menggunakan fungsi hash Anda, sampai ke titik,
Anda linier menyelidiki ke beberapa tempat yang tersedia.
Tapi sekarang, tentu saja, apa pun lain yang berakhir di sana,
Anda akan harus mencari lebih jauh ke bawah.
>> Dan ada lebih banyak Beban penelusuran yang
masuk ke memasukkan elemen dalam tabel hash Anda sekarang, kan?
Dan sekarang ketika Anda pergi dan mencoba dan menemukan berry lagi, Anda akan hash itu,
dan itu akan berkata, oh, lihat di ember 1,
dan itu tidak akan menjadi di ember 1, sehingga Anda
akan harus melintasi melalui sisa ini.
Jadi kadang-kadang berguna, tetapi dalam banyak kasus,
kita akan mengatakan bahwa chaining adalah apa yang ingin Anda lakukan.
>> Jadi kita membicarakan hal ini sebelumnya.
Aku punya depan sedikit diriku sendiri.
Tapi chaining pada dasarnya yang setiap kotak dalam tabel hash Anda
hanya linked list.
>> Jadi cara lain, atau lebih teknis cara, untuk memikirkan tabel hash
adalah bahwa itu hanya sebuah array dari daftar terkait, yang
ketika Anda sedang menulis kamus Anda dan Anda mencoba untuk memuatnya,
memikirkan hal itu sebagai array daftar terkait
akan membuatnya lebih mudah bagi Anda untuk inisialisasi.
>> AUDIENCE: table Jadi hash memiliki ukuran yang telah ditentukan,
seperti [tidak terdengar] ember?
>> SPEAKER 1: Benar.
Sehingga memiliki sejumlah set ember yang Anda determine--
yang kalian harus merasa bebas untuk bermain dengan.
Hal ini dapat cukup keren untuk melihat apa yang terjadi
ketika Anda mengubah nomor Anda dari ember.
Tapi ya, ia memiliki mengatur jumlah ember.
Apa yang memungkinkan Anda untuk menyesuaikan sebagai banyak unsur yang Anda butuhkan
adalah chaining terpisah ini di mana Anda telah menghubungkan daftar dalam setiap kotak.
Itu berarti tabel hash Anda akan persis ukuran
yang Anda butuhkan untuk menjadi, kan?
Itulah inti dari daftar terkait.
Keren.
>> Jadi setiap orang OK sana?
Baik.
Ah.
Apa yang baru saja terjadi?
Benar-benar sekarang.
Tebak seseorang membunuh saya.
>> OK kita akan pergi ke mencoba, yang sedikit gila.
Saya suka tabel hash.
Saya pikir mereka benar-benar keren.
Tries keren, juga.
>> Jadi tidak ada yang ingat apa dicoba adalah?
Anda harus pergi lebih sebentar dalam kuliah?
Apakah Anda ingat jenis cara kerjanya?
AUDIENCE: Aku hanya mengangguk bahwa kami pergi lebih dari itu.
SPEAKER 1: Kami pergi lebih dari itu.
OK, kita benar-benar akan pergi lebih dari sekarang adalah apa yang kita katakan.
>> AUDIENCE: Itu untuk pohon pengambilan.
>> SPEAKER 1: Ya.
Ini adalah pohon pengambilan.
Mengagumkan.
Jadi satu hal untuk melihat di sini adalah bahwa kita akan mencari karakter individu
di sini, kan?
>> Jadi sebelum dengan fungsi hash kami, kami sedang melihat kata-kata secara keseluruhan,
dan sekarang kami sedang mencari lebih pada karakter, bukan?
Jadi kita memiliki Maxwell di sini dan Mendel.
Jadi pada dasarnya try-- cara untuk berpikir tentang ini adalah bahwa setiap tingkat di sini
adalah array dari huruf.
Jadi ini adalah simpul akar Anda di sini, kan?
Ini memiliki semua karakter dari alfabet untuk memulai setiap kata.
>> Dan apa yang ingin Anda lakukan adalah mengatakan, OK, kita memiliki beberapa kata M.
Kita akan mencari Maxwell, jadi kita pergi ke M. Dan M poin untuk keseluruhan
lainnya array di mana setiap kata, selama ada
adalah kata yang memiliki A sebagai huruf kedua,
asalkan ada kata yang memiliki B sebagai huruf kedua,
itu akan memiliki pointer pergi ke beberapa array yang berikutnya.
>> Ada mungkin bukan kata yang MP sesuatu,
sehingga pada posisi P dalam hal ini array, itu hanya akan menjadi NULL.
Ini akan mengatakan, OK, tidak ada kata yang telah M diikuti oleh P, OK?
Jadi jika kita berpikir tentang hal ini, masing-masing salah satu hal yang lebih kecil
sebenarnya adalah salah satu dari ini array besar dari A sampai Z.
Jadi apa yang mungkin menjadi salah satu hal itu adalah jenis kelemahan dari mencoba?
>> AUDIENCE: Banyak memori.
>> SPEAKER 1: Ini satu ton memori, kan?
Masing-masing blok ini di sini mewakili 26 ruang, 26 elemen array.
Jadi mencoba mendapatkan sangat ruang berat.
>> Tapi mereka sangat cepat.
Jadi sangat cepat tetapi benar-benar ruang yang tidak efisien.
Jenis harus mencari out mana yang Anda inginkan.
Ini benar-benar keren untuk pset Anda, tetapi mereka mengambil banyak memori,
sehingga Anda trade off.
Ya?
>> AUDIENCE: Apakah mungkin untuk mendirikan mencoba dan kemudian
setelah Anda memiliki semua Data di dalamnya yang Anda need--
Saya tidak tahu apakah itu akan masuk akal.
Aku menyingkirkan semua Karakter NULL, tapi kemudian
Anda tidak akan dapat indeks them--
>> SPEAKER 1: Anda masih membutuhkan mereka.
>> AUDIENCE: - dengan cara yang sama setiap kali.
SPEAKER 1: Ya.
Anda membutuhkan karakter NULL untuk membiarkan Anda tahu apakah tidak ada kata di sana.
Ben kau memiliki sesuatu yang Anda inginkan?
OK.
Baiklah, jadi kita akan untuk pergi sedikit lebih
ke detail teknis di balik mencoba dan bekerja melalui contoh.
>> OK, jadi ini adalah hal yang sama.
Sedangkan dalam sebuah linked list, utama kami jenis of-- apa kata saya inginkan? -
seperti membangun blok adalah sebuah node.
Dalam mencoba, kami juga memiliki node, tapi itu didefinisikan secara berbeda.
>> Jadi kita memiliki beberapa bool yang mewakili apakah kata benar-benar
ada di lokasi ini, dan kemudian kami memiliki beberapa array yang di sini-atau lebih tepatnya,
ini adalah pointer ke array 27 karakter.
Dan ini adalah untuk, dalam hal ini, ini 27-- Saya yakin kalian semua seperti, tunggu,
ada 26 huruf dalam alfabet.
Mengapa kita memiliki 27?
>> Jadi tergantung pada cara Anda menerapkan ini,
ini adalah dari pset yang diperbolehkan untuk apostrof.
Jadi itu sebabnya satu tambahan.
Anda juga akan memiliki dalam beberapa kasus null terminator
termasuk sebagai salah satu karakter yang itu boleh,
dan itulah bagaimana mereka memeriksa untuk melihat apakah itu akhir kata.
Jika Anda tertarik, check out Video Kevin di study.cs50,
serta Wikipedia memiliki beberapa sumber daya yang baik di sana.
>> Tapi kita akan pergi melalui hanya jenis bagaimana Anda dapat bekerja melalui mencoba
jika Anda diberi satu.
Jadi kita memiliki satu super sederhana di sini bahwa memiliki kata-kata "kelelawar" dan "zoom" di dalamnya.
Dan seperti yang kita lihat di sini, ruang kecil ini di sini
merupakan bool kami yang berkata, ya, ini adalah sebuah kata.
Dan kemudian ini memiliki kami array karakter, kan?
>> Jadi kita akan pergi melalui menemukan "kelelawar" dalam mencoba ini.
Jadi mulai dari atas, kan?
Dan kita tahu bahwa b sesuai dengan indeks kedua, elemen kedua
dalam array ini, karena a dan b.
Jadi kira-kira yang kedua.
>> Dan ia mengatakan, OK, keren, mengikuti ke array berikutnya, karena jika kita ingat,
bukan itu masing-masing sebenarnya mengandung elemen.
Masing-masing dari array ini mengandung pointer, kan?
Ini merupakan perbedaan penting untuk membuat.
>> Saya tahu ini akan be-- mencoba adalah benar-benar sulit untuk mendapatkan pada pertama kalinya,
sehingga bahkan jika ini adalah kedua atau ketiga kalinya
dan itu masih baik dari tampak sulit,
Aku berjanji jika Anda pergi menonton pendek lagi besok,
mungkin akan membuat banyak lebih masuk akal.
Dibutuhkan banyak untuk dicerna.
Saya masih kadang-kadang saya seperti, tunggu, apa coba?
Bagaimana cara menggunakan ini?
>> Jadi kita telah b dalam kasus ini, yang merupakan indeks kedua kami.
Jika kita memiliki, katakanlah, c atau d atau surat lainnya,
kita perlu memetakan bahwa kembali ke indeks array kita bahwa yang sesuai dengan.
Jadi kita akan mengambil seperti rchar dan kami hanya kurangi off untuk memetakan menjadi 0-25.
Semua orang yang baik bagaimana kita memetakan karakter kita?
OK.
>> Jadi kita pergi ke yang kedua dan kami melihat bahwa, ya, itu tidak NULL.
Kita bisa melanjutkan ke array yang berikutnya ini.
Jadi kami pergi ke array yang berikutnya ini di sini.
>> Dan kita katakan, OK, sekarang kita perlu untuk melihat apakah ada di sini.
Apakah Sebuah nol atau apakah itu sebenarnya bergerak maju?
Jadi benar-benar bergerak maju dalam array ini.
Dan kita katakan, OK, t adalah huruf terakhir kami.
Jadi kami pergi ke t pada indeks.
Dan kemudian kita bergerak maju karena ada satu lagi.
Dan yang satu ini pada dasarnya mengatakan bahwa, ya, ia mengatakan bahwa ada sebuah kata di sini-
bahwa jika Anda mengikuti ini jalan, Anda telah tiba
di kata, yang kita tahu adalah "kelelawar."
Ya?
>> AUDIENCE: Apakah standar untuk memiliki indeks 0 dan kemudian memiliki semacam pada 1
atau untuk memiliki akhir?
>> SPEAKER 1: No.
Jadi jika kita melihat kembali pada kami deklarasi di sini, itu bool,
jadi elemen sendiri dalam node.
Jadi bukan bagian dari array.
Keren.
Jadi ketika kita selesai kata kami dan kami di array ini, apa yang ingin kita lakukan
adalah melakukan pemeriksaan adalah ini sebuah kata.
Dan dalam hal ini, itu akan kembali ya.
>> Jadi pada catatan, kita tahu bahwa "kebun binatang" - kita kenal sebagai manusia bahwa "kebun binatang" adalah sebuah kata,
kan?
Tetapi coba di sini akan mengatakan, tidak, itu tidak.
Dan itu akan mengatakan bahwa karena kita belum ditunjuk sebagai kata di sini.
Meskipun kita dapat melintasi melalui array ini,
mencoba ini akan mengatakan bahwa, tidak, kebun binatang tidak ada dalam kamus Anda
karena kita belum ditunjuk seperti itu.
>> Jadi salah satu cara untuk melakukan itu-- oh, maaf, yang satu ini.
Jadi dalam hal ini, "kebun binatang" tidak kata, tetapi dalam try kami.
Tapi dalam satu ini, katakanlah kita ingin memperkenalkan kata "mandi," apa yang terjadi
adalah kita mengikuti through-- b, a, t.
Kami berada di array ini, dan kita pergi untuk mencari h.
>> Dalam hal ini, ketika kita melihat pointer pada h,
itu menunjuk ke NULL, OK?
Jadi kecuali jika secara eksplisit menunjuk ke array lain,
Anda berasumsi bahwa semua pointer dalam array ini menunjuk ke null.
Jadi dalam hal ini, h menunjuk untuk null jadi kami tidak bisa berbuat apa-apa,
sehingga juga akan kembali palsu, "mandi" tidak di sini.
Jadi sekarang kita benar-benar akan pergi melalui
bagaimana kita benar-benar mengatakan bahwa "kebun binatang" di try kita.
Bagaimana kita masukkan "kebun binatang" dalam mencoba kita?
Jadi dengan cara yang sama yang kita mulai dengan linked list kami, kami mulai pada akar.
Jika ragu, mulai dari akar hal-hal ini.
>> Dan kita akan mengatakan, OK, z.
z ada dalam hal ini, dan itu tidak.
Jadi Anda pindah ke array berikutnya, OK?
Dan kemudian pada yang berikutnya, kita katakan, OK, apakah o ada?
Itu tidak.
Ini lagi.
>> Dan seterusnya satu kami berikutnya, kami katakan, OK, "kebun binatang" sudah ada di sini.
Semua yang perlu kita lakukan adalah mengatur hal ini sama true, bahwa ada sebuah kata di sana.
Jika Anda telah mengikuti semua sampai sebelum titik itu,
itu kata, jadi hanya mengaturnya sama dengan itu.
Ya?
>> AUDIENCE: Jadi apakah itu berarti bahwa "ba" adalah kata juga?
>> SPEAKER 1: No.
Jadi dalam hal ini, "ba" kita akan mendapatkan di sini, kita akan mengatakan itu sebuah kata,
dan masih akan ada.
OK?
Mmhmm?
>> AUDIENCE: Jadi setelah Anda apakah itu kata dan Anda menjawab ya, maka
akan berisi pergi ke m?
>> SPEAKER 1: Jadi ini ada hubungannya with-- Anda memuat ini.
Anda mengatakan "kebun binatang" adalah sebuah kata.
Ketika Anda pergi ke check-- seperti, katakanlah Anda ingin mengatakan,
tidak "kebun binatang" yang ada dalam kamus ini?
Anda hanya akan mencari "kebun binatang," dan kemudian memeriksa untuk melihat apakah itu sebuah kata.
Anda tidak akan pernah bergerak melalui m karena itulah tidak
apa yang Anda cari.
>> Jadi jika kita benar-benar ingin menambahkan "mandi" dalam mencoba ini,
kami akan melakukan hal yang sama seperti yang kita lakukan dengan "kebun binatang,"
kecuali kita akan melihat bahwa ketika kita mencoba dan mendapatkan h, itu tidak ada.
Sehingga Anda dapat menganggap ini sebagai mencoba untuk menambahkan node baru ke dalam linked list,
jadi kita akan perlu menambahkan lain salah satu array tersebut, seperti begitu.
Dan kemudian apa yang kita lakukan adalah kita hanya mengatur h elemen dari array ini menunjuk ke ini.
>> Dan kemudian apa yang kita ingin lakukan di sini?
Tambahkan sama dengan benar karena itu kata.
Keren.
Aku tahu.
Mencoba tidak yang paling menarik.
Percayalah, saya tahu.
>> Jadi satu hal untuk mewujudkan dengan mencoba, Aku berkata, mereka sangat efisien.
Jadi kita telah melihat mereka mengambil satu ton ruang.
Mereka agak membingungkan.
Jadi, mengapa kita pernah menggunakan ini?
Kami menggunakan ini karena mereka sangat efisien.
>> Jadi jika Anda pernah melihat sebuah kata, Anda hanya
dibatasi oleh panjang kata.
Jadi jika Anda sedang mencari kata yang panjang lima,
Anda hanya pernah akan harus membuat paling banyak lima perbandingan, OK?
Sehingga membuatnya pada dasarnya konstan.
Seperti penyisipan dan pencarian pada dasarnya waktu yang konstan.
>> Jadi, jika Anda pernah bisa mendapatkan sesuatu dalam waktu yang konstan,
itu sebagai baik karena mendapat.
Anda tidak bisa lebih baik daripada waktu yang konstan untuk hal-hal ini.
Jadi itu adalah salah satu Plus besar mencoba.
>> Tapi itu adalah banyak ruang.
Jadi Anda jenis harus memutuskan apa yang lebih penting bagi Anda.
Dan pada komputer saat ini, ruang yang mencoba bisa memakan waktu hingga
mungkin tidak mempengaruhi Anda bahwa banyak, tapi mungkin
Anda sedang berhadapan dengan sesuatu yang memiliki jauh, jauh lebih banyak hal,
dan mencoba hanya tidak masuk akal.
Ya?
>> AUDIENCE: Tunggu, sehingga Anda memiliki 26 huruf dalam setiap satu?
>> SPEAKER 1: Mmhmm.
Ya, Anda memiliki 26.
Anda memiliki beberapa adalah penanda kata dan kemudian Anda memiliki 26 pointer dalam setiap orang.
Dan mereka point--
>> AUDIENCE: Dan setiap 26, apakah mereka masing-masing memiliki 26?
>> SPEAKER 1: Ya.
Dan itulah mengapa, yang Anda bisa lihat, mengembang cukup pesat.
Baik.
Jadi kita akan masuk ke dalam pohon, yang Saya merasa seperti lebih mudah dan mungkin akan
menjadi penangguhan hukuman kecil yang bagus dari mencoba sana.
Jadi mudah-mudahan sebagian besar dari Anda telah melihat pohon sebelumnya.
Tidak seperti cantik yang di luar, yang saya
tidak tahu apakah ada pergi di luar ruangan baru-baru ini.
Aku pergi memetik apel akhir pekan ini, dan oh my gosh, itu indah.
Aku tidak tahu daun bisa melihat bahwa cantik.
>> Jadi ini hanya pohon, kan?
Ini hanyalah beberapa node, dan menunjuk ke sekelompok node lain.
Seperti yang Anda lihat di sini, ini adalah jenis tema yang berulang.
Node menunjuk ke node adalah jenis esensi dari banyak struktur data.
Ini tergantung pada bagaimana kita memiliki mereka menunjuk ke satu sama lain
dan bagaimana kita melintasi melalui mereka dan bagaimana kita
menyisipkan hal-hal yang menentukan karakteristik yang berbeda mereka.
>> Jadi hanya beberapa terminologi, yang saya gunakan sebelumnya.
Jadi akar apa saja yang di bagian paling atas.
itu adalah di mana kita selalu mulai.
Anda dapat menganggapnya sebagai kepala juga.
Tapi untuk pohon, kita cenderung untuk menyebutnya sebagai root.
>> Apa-apa di sini-bawah di sangat, sangat bottom--
daun dipertimbangkan.
Jadi sejalan dengan Semuanya pohon, kan?
Daun berada di tepi pohon Anda.
>> Dan kemudian kami juga memiliki beberapa istilah untuk berbicara tentang node dalam kaitannya
satu sama lain.
Jadi kita memiliki orang tua, anak-anak, dan saudara kandung.
Jadi dalam hal ini, 3 adalah induk dari 5, 6, dan 7.
Jadi orang tua adalah apa pun yang satu langkah di atas apa pun yang Anda
maksud, jadi hanya seperti pohon keluarga.
Mudah-mudahan, ini semua sedikit sebuah sedikit lebih intuitif daripada mencoba.
>> Saudara adalah setiap yang memiliki induk yang sama, kan?
Mereka berada di tingkat yang sama di sini.
Dan kemudian, karena aku mengatakan, anak-anak hanya
apa adalah salah satu langkah di bawah ini node tersebut, OK?
Keren.
Jadi pohon biner.
Adakah yang bisa menebak di salah satu karakteristik pohon biner?
>> AUDIENCE: Max dua daun.
>> SPEAKER 1: Benar.
Jadi max dua daun.
Jadi dalam satu ini sebelumnya, kami memiliki satu ini yang memiliki tiga, tetapi dalam pohon biner,
Anda memiliki maksimal dua anak per induk, kan?
Ada satu lagi Karakteristik yang menarik.
Apakah ada yang tahu itu?
Pohon biner.
>> Jadi pohon biner akan memiliki segalanya pada the-- satu ini tidak sorted--
tetapi dalam pohon biner diurutkan, semua yang ada di sebelah kanan
lebih besar dari orang tua, dan segala sesuatu di sebelah kiri
kurang dari orangtua.
Dan yang telah kuis pertanyaan sebelumnya, jadi baik untuk tahu.
Jadi cara kita mendefinisikan ini, lagi, kita memiliki node lain.
Hal ini terlihat sangat mirip dengan apa?
Ganda
>> AUDIENCE: Linked daftar
>> SPEAKER 1: Sebuah linked list ganda, kan?
Jadi jika kita mengganti ini dengan sebelumnya dan berikutnya,
ini akan menjadi daftar ganda terkait.
Tapi dalam kasus ini, kita benar-benar memiliki kiri dan kanan dan hanya itu.
Jika tidak, itu persis sama.
Kami masih memiliki elemen Anda sedang mencari,
dan Anda hanya memiliki dua pointer akan apa pun yang berikutnya.
Ya, pohon pencarian biner begitu.
Jika kita perhatikan, semua yang ada di di sini adalah than-- lebih besar
atau segala sesuatu yang segera ke kanan di sini
lebih besar dari, segala sesuatu di sini kurang dari.
>> Jadi jika kita mencari melalui, itu harus terlihat sangat dekat dengan pencarian biner
di sini, kan?
Kecuali bukan melihat pada setengah array,
kita hanya melihat baik kiri samping atau sisi kanan pohon.
Sehingga mendapat sedikit lebih sederhana, saya pikir.
>> Jadi jika root anda adalah NULL, jelas itu hanya palsu.
Dan jika itu ada, jelas itu benar.
Jika itu kurang dari, kita mencari kiri.
Jika itu lebih besar dari, kita mencari kanan.
Ini persis seperti pencarian biner, hanya struktur data yang berbeda
bahwa kita sedang menggunakan.
Alih-alih sebuah array, itu hanya sebuah pohon biner.
>> OK, tumpukan.
Dan juga, sepertinya kita mungkin memiliki sedikit waktu.
Jika kita lakukan, saya senang untuk pergi lebih dari semua ini lagi.
OK, jadi tumpukan.
Apakah ada yang ingat apa stacks-- setiap karakteristik stack?
>> OK, jadi kebanyakan dari kita, saya pikir, makan di makan halls--
sebanyak yang kita mungkin tidak suka.
Tapi jelas, Anda bisa memikirkan stack benar-benar hanya sebagai tumpukan nampan
atau setumpuk hal.
Dan apa yang penting untuk menyadari adalah bahwa hal itu
something-- karakteristik bahwa kita menyebutnya by-- adalah LIFO.
Apakah ada yang tahu apa yang berdiri untuk?
Mmhmm?
>> AUDIENCE: Terakhir, keluar pertama.
>> SPEAKER 1: Benar, bertahan, keluar pertama.
Jadi jika kita tahu, jika kita susun hal-hal up, hal yang paling mudah untuk ambil off--
dan mungkin satu-satunya hal yang kita bisa ambil off jika tumpukan kami adalah enough-- besar
adalah bahwa unsur atas.
Jadi apa pun yang diletakkan di last-- seperti yang kita lihat di sini,
apa pun yang mendorong pada kebanyakan recently-- adalah
akan menjadi yang pertama hal yang kita pop off, OK?
>> Jadi apa yang kita miliki di sini adalah struct typedef lain.
Ini benar-benar hanya seperti kecelakaan saja dalam struktur data,
sehingga ada banyak dilemparkan pada kalian.
Aku tahu.
Jadi belum struct lain.
Yay untuk struktur.
>> Dan dalam hal ini, itu adalah beberapa pointer ke array yang memiliki beberapa kapasitas.
Jadi ini merupakan tumpukan kami di sini, seperti array kita sebenarnya
yang memegang elemen kami.
Dan maka di sini kita memiliki beberapa ukuran.
>> Dan biasanya, Anda ingin menyimpan melacak seberapa besar tumpukan Anda
karena apa yang akan memungkinkan Anda lakukan adalah jika Anda tahu ukuran,
memungkinkan Anda untuk mengatakan, OK, aku pada kapasitas?
Apakah saya dapat menambahkan sesuatu yang lebih?
Dan itu juga memberitahu Anda di mana bagian atas tumpukan Anda
sehingga Anda tahu apa yang Anda benar-benar bisa lepas landas.
Dan itu benar-benar akan menjadi sedikit lebih jelas di sini.
>> Jadi untuk push, satu hal, jika Anda pernah untuk melaksanakan dorong,
karena saya hanya mengatakan, Anda tumpukan memiliki ukuran terbatas, kan?
Array kita memiliki beberapa kapasitas.
Ini sebuah array.
Ini adalah ukuran yang tetap, jadi kita perlu memastikan bahwa kita tidak menempatkan lebih
ke array kita daripada kita benar-benar memiliki ruang untuk.
>> Jadi, ketika Anda sedang menciptakan dorongan fungsi, hal pertama yang Anda lakukan adalah mengatakan, OK,
apakah saya memiliki ruang dalam tumpukan saya?
Karena jika saya tidak melakukannya, maaf, Saya tidak bisa menyimpan elemen Anda.
Jika saya melakukannya, maka Anda ingin menyimpan di bagian atas tumpukan, kan?
>> Dan ini adalah mengapa kita memiliki untuk melacak ukuran kami.
Jika kita tidak melacak ukuran kami, kita tidak tahu di mana harus menaruhnya.
Kita tidak tahu berapa banyak hal berada dalam array kita sudah.
Seperti jelas ada cara yang mungkin Anda bisa melakukannya.
Anda bisa menginisialisasi segalanya untuk NULL dan kemudian memeriksa NULL terbaru,
tapi hal yang jauh lebih mudah hanya mengatakan, OK, melacak ukuran.
Seperti saya tahu saya memiliki empat elemen dalam array saya, jadi hal berikutnya
yang kita pasang di, kami akan menyimpan di indeks 4.
Dan kemudian, tentu saja, ini berarti bahwa Anda telah berhasil mendorong sesuatu
ke stack Anda, Anda ingin meningkatkan ukuran
sehingga Anda tahu di mana Anda begitu bahwa Anda dapat mendorong lebih banyak hal di.
>> Jadi jika kita mencoba untuk pop sesuatu dari tumpukan,
apa yang mungkin menjadi hal pertama bahwa kita ingin memeriksa?
Anda mencoba untuk mengambil sesuatu dari tumpukan Anda.
Apakah Anda yakin ada sesuatu dalam tumpukan Anda?
Tidak.
Jadi apa yang kita ingin memeriksa?
>> AUDIENCE: [tak terdengar].
SPEAKER 1: Periksa ukuran?
Ukuran.
Jadi kami ingin memeriksa untuk melihat apakah ukuran kami lebih besar dari 0, OK?
Dan jika sudah, maka kita ingin menurunkan Ukuran kami dengan 0 dan kembali itu.
Mengapa?
>> Dalam yang pertama kami mendorong, kami mendorongnya
ke ukuran dan ukuran kemudian diperbarui.
Dalam hal ini, kita decrementing ukuran dan kemudian mengambil it off, mencabut itu
dari array kita.
Mengapa kita bisa melakukannya?
Jadi jika saya memiliki satu hal di stack saya, apa yang akan menjadi ukuran saya pada saat itu?
1.
>> Dan di mana elemen 1 disimpan?
Apa indeks?
AUDIENCE: 0.
SPEAKER 1: 0.
Jadi dalam hal ini, kita selalu perlu untuk membuat sure--
bukannya kembali ukuran minus 1, karena kita
tahu bahwa elemen kita akan disimpan pada 1 kurang
apa pun ukuran kami, ini hanya mengurus itu.
Ini adalah cara yang sedikit lebih elegan.
Dan kita hanya pengurangan kami ukuran dan kemudian kembali ukuran.
Mmhmm?
>> AUDIENCE: Saya kira hanya secara umum, mengapa struktur data
bermanfaat?
>> SPEAKER 1: Hal ini tergantung pada konteks Anda.
Jadi untuk beberapa teori, jika Anda bekerja with-- OK,
biarkan aku melihat apakah ada yang menguntungkan yang bermanfaat bagi lebih dari luar
CS.
Dengan tumpukan, setiap kali Anda perlu untuk melacak sesuatu yang
adalah yang paling baru ditambahkan adalah ketika Anda akan ingin menggunakan stack.
>> Dan aku tidak bisa memikirkan suatu barang contoh yang sekarang.
Tapi setiap kali terbaru hal yang paling penting bagi Anda,
saat itulah setumpuk akan menjadi berguna.
Saya mencoba untuk berpikir jika ada satu yang baik untuk ini.
Jika saya memikirkan contoh yang baik di akhirat 20 menit, saya pasti akan memberitahu Anda.
>> Tapi secara keseluruhan, jika ada apa-apa, seperti saya katakan sebagian besar, di mana terbaru
yang paling penting, yang mana stack datang ke dalam bermain.
Sedangkan antrian adalah jenis sebaliknya.
Dan anjing-anjing kecil.
Bukankah ini bagus, kan?
Saya merasa seperti saya harus hanya memiliki video kelinci
tepat di tengah-tengah bagian untuk kalian
karena ini adalah bagian yang intens.
>> Jadi antrian.
Pada dasarnya antrian seperti garis.
Kalian Saya yakin penggunaan sehari-hari ini, hanya seperti di ruang makan kami.
Jadi kita harus pergi di dan mendapatkan nampan kami, aku
Pastikan Anda harus menunggu dalam antrean menggesek atau mendapatkan makanan Anda.
>> Jadi perbedaan di sini adalah bahwa ini adalah FIFO.
Jadi jika LIFO terakhir di, pertama out, FIFO adalah pertama, keluar pertama.
Jadi ini adalah di mana apa pun yang Anda meletakkan pada pertama adalah yang paling penting.
Jadi jika Anda sedang menunggu di line-- kaleng Anda
bayangkan jika Anda pergi ke pergi mendapatkan iPhone baru
dan itu tumpukan di mana orang terakhir di garis mendapatkannya pertama,
orang akan membunuh satu sama lain.
>> Jadi FIFO, kita semua sangat akrab dengan di dunia nyata di sini,
dan itu semua harus dilakukan dengan benar-benar jenis menciptakan seluruh baris ini
dan antrian struktur.
Jadi sedangkan dengan tumpukan, kami memiliki dorongan dan pop.
Dengan antrian, kami memiliki enqueue dan dequeue.
Jadi enqueue pada dasarnya berarti memasukkannya ke belakang,
dan sarana dequeue mengambil off dari depan.
Jadi struktur data kami adalah sedikit lebih rumit.
Kami memiliki hal yang kedua untuk melacak.
>> Jadi tanpa kepala, ini adalah persis tumpukan, kan?
Ini adalah struktur yang sama seperti stack.
Satu-satunya hal yang berbeda sekarang adalah kita memiliki kepala ini, yang apa yang Anda pikirkan
akan melacak?
>> AUDIENCE: Yang pertama.
>> SPEAKER 1: Benar, yang Hal pertama yang kita masukkan ke dalam.
Kepala antrian kami.
Siapa pun yang di baris pertama.
Baiklah, jadi jika kita melakukan enqueue.
Sekali lagi, dengan salah satu struktur data,
karena kita sedang berhadapan dengan sebuah array, kita perlu memeriksa apakah kita memiliki ruang.
>> Ini adalah jenis seperti saya mengatakan kalian, jika Anda membuka file,
Anda perlu memeriksa null.
Dengan salah satu tumpukan ini dan antrian, Anda perlu
untuk melihat apakah ada ruang karena kita berurusan dengan ukuran array tetap,
seperti yang kita lihat di sini-0, 1 semua sampai 5.
Jadi apa yang kita lakukan dalam hal ini adalah memeriksa untuk melihat apakah kita masih memiliki ruang.
Apakah ukuran kami kurang dari kapasitas?
>> Jika demikian, kita perlu menyimpannya di ekor dan kami memperbarui ukuran kami.
Jadi apa yang mungkin ekor dalam kasus ini?
Ini tidak secara eksplisit ditulis.
Bagaimana kita akan menyimpannya?
Apa yang akan ekor itu?
>> Jadi mari kita berjalan melalui contoh ini.
Jadi ini adalah array dari ukuran 6, kan?
Dan kita miliki sekarang, ukuran kami adalah 5.
Dan ketika kita memasukkannya ke dalam, itu akan untuk masuk ke indeks kelima, kan?
Jadi menyimpan di ekor.
>> Cara lain untuk menulis ekor akan hanya menjadi array kita di indeks ukuran, kan?
Ini adalah ukuran 5.
Hal berikutnya yang akan masuk ke 5.
Keren?
OK.
Ia mendapat sedikit lebih rumit ketika kita mulai bermain-main dengan kepala.
Ya?
>> AUDIENCE: Apakah itu berarti bahwa kita akan menyatakan sebuah array yang
adalah lima elemen panjang dan kemudian kita menambahkan ke atasnya?
>> SPEAKER 1: No.
Jadi dalam hal ini, ini adalah stack.
Hal ini akan dinyatakan sebagai array dari ukuran 6.
Dan dalam hal ini, kita hanya memiliki satu kiri ruang.
>> OK, jadi satu hal yang dalam hal ini kasus, jika kepala kita adalah pada 0,
maka kita hanya bisa menambahkannya pada ukuran.
Tapi itu akan sedikit rumit karena sesungguhnya, mereka
tidak memiliki slide untuk ini, jadi aku akan
untuk menarik satu karena itu tidak cukup yang sederhana sekali Anda
mulai menyingkirkan hal.
Jadi sedangkan dengan stack Anda hanya pernah memiliki
khawatir tentang apa ukurannya ketika Anda menambahkan sesuatu pada,
dengan antrian Anda juga perlu membuat memastikan bahwa kepala Anda dicatat,
karena hal yang keren tentang antrian adalah bahwa jika Anda tidak pada kapasitas,
Anda benar-benar dapat membuatnya membungkus.
>> OK, jadi salah satu thing-- oh, ini adalah kapur yang mengerikan.
Satu hal yang perlu dipertimbangkan adalah kasus.
Kami hanya akan melakukan lima.
OK, jadi kita akan mengatakan kepala di sini.
Ini adalah 0, 1, 2, 3, 4.
>> Kepala ada, dan silahkan memiliki hal-hal di dalamnya.
Dan kita ingin menambahkan sesuatu, kan?
Jadi hal yang perlu kita tahu adalah bahwa kepala selalu
akan memindahkan cara ini dan maka loop kembali sekitar, OK?
>> Jadi antrian ini memiliki ruang, kan?
Memiliki ruang di awal, jenis kebalikan dari ini.
Jadi apa yang perlu kita lakukan adalah kita perlu menghitung ekor.
Jika Anda tahu bahwa Anda kepala tidak bergerak, ekor
hanya array di indeks ukuran.
>> Namun pada kenyataannya, jika Anda menggunakan antrian, kepala Anda mungkin sedang diperbarui.
Jadi apa yang perlu Anda lakukan adalah benar-benar menghitung ekor.
Jadi apa yang kita lakukan adalah formula ini di sini, yang aku akan membiarkan Anda
Orang-orang berpikir tentang, dan maka kita akan bicara tentang hal itu.
Jadi ini adalah kapasitas.
>> Jadi ini benar-benar akan memberi Anda cara untuk melakukannya.
Karena dalam kasus ini, apa?
Pusat kami di 1, ukuran kami adalah 4.
Jika kita mod bahwa dengan 5, kita mendapatkan 0, yang mana kita harus masukan itu.
>> Jadi dalam kasus berikutnya, jika kita melakukan hal ini,
kita katakan, OK, mari kita dequeue sesuatu.
Kami dequeue ini.
Kami mengambil elemen ini, kan?
>> Dan sekarang kepala kita menunjuk sini, dan kami ingin menambahkan hal lain.
Ini pada dasarnya adalah belakang baris kami, kan?
Antrian dapat membungkus array.
Itulah salah satu perbedaan utama.
Tumpukan, Anda tidak bisa melakukan ini.
>> Dengan antrian, Anda bisa karena semua yang penting
adalah bahwa Anda tahu apa itu yang terakhir ditambahkan.
Karena semuanya akan ditambahkan dalam arah ke kiri ini, dalam hal ini,
dan kemudian membungkus, Anda dapat terus menempatkan dalam unsur-unsur baru
di depan array karena itu tidak benar-benar
bagian depan array lagi.
Anda dapat menganggap awal array sebagai mana kepala Anda sebenarnya.
>> Jadi rumus ini adalah bagaimana Anda menghitung ekor Anda.
Apakah itu masuk akal?
OK.
OK, dequeue, dan kemudian kalian punya 10 menit
untuk menanyakan pertanyaan klarifikasi yang Anda inginkan, karena saya tahu itu gila.
>> Baiklah, jadi di way-- yang sama Aku tidak tahu apakah kalian melihat,
tapi CS adalah semua tentang pola.
Hal-hal yang cukup banyak sama, hanya dengan tweak kecil.
Hal begitu sama di sini.
Kita perlu memeriksa untuk melihat apakah kita benar-benar memiliki sesuatu dalam antrian kami, kan?
Katakanlah, OK, adalah ukuran kami lebih besar dari 0?
Keren.
>> Jika kita lakukan, maka kita menggerakkan kepala kami, yang adalah apa yang saya hanya ditunjukkan di sini.
Kami memperbarui kepala kita untuk menjadi satu lagi.
Dan kemudian kami pengurangan kami Ukuran dan kembali elemen.
>> Ada banyak lagi beton kode pada study.cs50.net,
dan saya sangat merekomendasikan pergi melalui itu jika Anda punya waktu,
bahkan jika itu hanya pseudo-code.
Dan jika kalian ingin berbicara melalui bahwa dengan saya satu lawan satu, tolong beritahu saya
tahu.
Aku akan senang untuk.
Struktur data, jika Anda mengambil CS 124, Anda akan
tahu bahwa struktur data menjadi sangat menyenangkan dan ini baru saja dimulai.
>> Jadi saya tahu itu sulit.
Tidak apa-apa.
Kami berjuang.
Saya masih dilakukan.
Jadi jangan terlalu khawatir tentang hal itu.
>> Tapi itu pada dasarnya Anda kecelakaan saja dalam struktur data.
Aku tahu itu banyak.
Apakah ada sesuatu yang kita ingin pergi lagi?
Apa pun yang kita ingin berbicara melalui?
Ya?
>> AUDIENCE: Misalnya itu, jadi ekor baru pada 0 lebih dari itu?
SPEAKER 1: Ya.
AUDIENCE: OK.
Jadi akan melalui, Anda akan memiliki 1 ditambah 4 or--
>> SPEAKER 1: Jadi Anda berkata, ketika kita ingin pergi melakukan ini lagi?
AUDIENCE: Ya.
Jadi jika Anda mencari out-- mana Anda menghitung ekor dari dalam?
>> SPEAKER 1: Jadi ekor adalah in-- Saya mengubah ini.
Jadi, dalam contoh ini di sini, ini adalah array kita sedang melihat, OK?
Jadi kita memiliki hal-hal dalam 1, 2, 3, dan 4.
Jadi kita memiliki kepala kita adalah sama dengan 1 pada titik ini, dan ukuran kita sama dengan 4
pada titik ini, kan?
>> Anda semua sepakat itu yang terjadi?
Jadi kita lakukan kepala plus ukuran, yang memberi kita 5, dan kemudian kita mod oleh 5.
Kami mendapatkan 0, yang mengatakan kepada kita bahwa 0 adalah mana ekor kami, di mana kami memiliki ruang.
>> AUDIENCE: Apa topi?
>> SPEAKER 1: Kapasitas.
Maaf.
Jadi itu adalah ukuran array Anda.
Ya?
>> AUDIENCE: [tak terdengar] sebelum kita kembali elemen?
>> SPEAKER 1: Jadi kita memindahkan kepala atau kembali saat ini?
Jadi jika kita bergerak satu, pengurangan ukuran?
Tunggu.
Aku pasti lupa lagi.
Sudahlah.
Tidak ada rumus lain.
Ya, Anda akan ingin kembali kepala dan kemudian memindahkannya kembali.
>> AUDIENCE: OK, karena At ini titik, kepala berada di 0,
dan kemudian Anda ingin kembali Indeks 0 dan kemudian membuat kepala 1?
>> SPEAKER 1: Benar.
Saya pikir ada yang lain rumus jenis seperti ini.
Saya tidak memilikinya di atas kepala saya sebagai Saya tidak ingin memberikan salah satu.
Tapi saya pikir itu sangat valid untuk mengatakan, OK, menyimpan element-- ini apa pun
elemen head is-- pengurangan Anda ukuran, gerakkan kepala Anda lebih, dan kembali
apa pun unsur yang.
Itu benar berlaku.
OK.
Saya merasa seperti ini adalah tidak seperti most-- Anda tidak
akan berjalan keluar dari sini seperti, ya, saya tahu mencoba.
Aku punya itu semua.
Tidak apa-apa.
Aku berjanji.
Tetapi struktur data adalah sesuatu yang dibutuhkan banyak waktu untuk membiasakan diri.
Mungkin salah satu yang paling sulit hal, saya pikir, dalam kursus.
>> Jadi pasti membutuhkan pengulangan dan mencari at-- saya
tidak benar-benar tahu daftar terkait sampai aku terlalu banyak dengan mereka,
dengan cara yang sama bahwa saya tidak benar-benar memahami pointer
sampai aku harus mengajarkannya untuk dua tahun dan melakukan psets saya sendiri dengan itu.
Dibutuhkan banyak pengulangan dan waktu.
Dan akhirnya, itu akan jenis klik.
>> Tapi sementara itu, jika Anda memiliki jenis dari pemahaman tingkat tinggi apa
ini dilakukan, pro mereka dan cons-- yang adalah apa yang
kita benar-benar cenderung menekankan, terutama dalam kegiatan intro.
Seperti, mengapa kita akan menggunakan mencoba lebih dari array?
Seperti, apa positif dan negatif dari masing-masing?
>> Dan memahami trade-off antara masing-masing struktur
adalah apa yang jauh lebih penting sekarang.
Mungkin ada yang gila pertanyaan atau dua yang
akan meminta Anda untuk menerapkan dorong atau menerapkan pop atau enqueue dan dequeue.
Tetapi untuk sebagian besar, memiliki itu pemahaman tingkat yang lebih tinggi dan lebih
dari pemahaman yang intuitif adalah lebih penting daripada benar-benar
mampu menerapkannya.
>> Ini akan benar-benar mengagumkan jika Anda semua bisa pergi keluar dan pergi melaksanakan mencoba,
tetapi kami memahami itu belum tentu hal yang paling masuk akal sekarang.
Tapi Anda bisa dalam pset Anda, jika Anda ingin untuk, dan kemudian Anda akan mendapatkan praktek,
dan kemudian mungkin Anda akan benar-benar memahaminya.
Ya?
>> AUDIENCE: OK, jadi mana yang kita dimaksudkan untuk digunakan dalam pset tersebut?
Apakah saya perlu menggunakan salah satu dari mereka?
SPEAKER 1: Ya.
Jadi, Anda memiliki pilihan Anda.
Saya kira dalam kasus ini, kita bisa berbicara tentang pset sedikit
karena saya berlari melalui ini.
Jadi dalam pset Anda, Anda memiliki Anda pilihan mencoba atau tabel hash.
Beberapa orang akan mencoba dan menggunakan filter mekar,
tetapi mereka secara teknis tidak benar.
Karena sifat probabilistik mereka, mereka memberikan hasil positif palsu kadang-kadang.
Mereka terlihat keren ke dalam, meskipun.
Sangat merekomendasikan mencari pada mereka setidaknya.
Tapi Anda memiliki pilihan Anda antara tabel hash dan mencoba.
Dan itu akan menjadi tempat Anda memuat dalam kamus Anda.
>> Dan Anda harus memilih fungsi hash Anda,
Anda harus memilih berapa banyak Ember yang Anda miliki, dan itu akan bervariasi.
Seperti jika Anda memiliki lebih ember, mungkin itu akan berjalan lebih cepat.
Tapi mungkin Anda membuang-buang a banyak ruang seperti itu, meskipun.
Anda harus mencari tahu.
Mmhmm?
>> AUDIENCE: Anda katakan sebelumnya bahwa kita dapat menggunakan fungsi hash lainnya,
bahwa kita tidak perlu membuat fungsi hash?
>> SPEAKER 1: Ya, benar.
Jadi secara harfiah untuk fungsi hash Anda, seperti google "fungsi hash"
dan mencari beberapa yang keren.
Anda tidak diharapkan untuk membangun fungsi hash Anda sendiri.
Orang-orang menghabiskan mereka tesis tentang hal-hal ini.
>> Jadi jangan khawatir tentang membangun Anda sendiri.
Cari satu online untuk memulai dengan.
Beberapa dari mereka Anda harus memanipulasi sedikit
untuk memastikan jenis kembali cocok dan yang lainnya, sehingga pada awalnya,
Saya akan merekomendasikan menggunakan sesuatu sangat mudah yang mungkin hanya
hash pada huruf pertama.
Dan kemudian setelah Anda memiliki kerja itu, menggabungkan fungsi hash dingin.
Mmhmm?
>> AUDIENCE: Apakah mencoba menjadi atau efisien tapi hanya sulit untuk, like--
>> SPEAKER 1: Jadi mencoba, saya pikir, adalah intuitif sulit untuk menerapkan
tapi sangat cepat.
Namun, membutuhkan lebih banyak tempat.
Sekali lagi, Anda dapat mengoptimalkan kedua dari mereka di cara yang berbeda dan ada cara to--
AUDIENCE: Bagaimana kita dinilai pada ini?
Apakah itu masalah-
>> SPEAKER 1: Jadi kau dinilai cara biasa.
Anda akan dinilai pada desain.
Apapun cara yang Anda lakukan, Anda ingin pastikan itu sebagai elegan karena dapat
dan seefisien mungkin.
Tetapi jika Anda memilih mencoba atau hash tabel, selama bekerja,
kami senang dengan itu.
Dan jika Anda menggunakan sesuatu yang hash pada huruf pertama, itu baik-baik saja,
seperti mungkin seperti desain-bijaksana.
Kami juga mencapai titik dalam semester-- ini
Saya tidak tahu apakah Anda orang noticed-- jika Anda
nilai pset menurun sedikit karena desain dan yang lainnya,
itu baik-baik saja.
Sudah mulai ke titik di mana Anda program yang semakin rumit.
Ada banyak tempat Anda dapat memperbaiki.
>> Jadi itu sangat normal.
Ini bukan berarti bahwa Anda melakukan lebih buruk pada pset Anda.
Hanya saja kita yang lebih keras pada Anda sekarang.
Jadi semua orang merasakan hal itu.
Aku hanya dinilai semua psets Anda.
Aku tahu semua orang merasakan hal itu.
>> Jadi jangan khawatir tentang itu.
Dan jika Anda memiliki pertanyaan tentang psets sebelumnya atau cara-cara Anda dapat meningkatkan,
Aku mencoba dan komentar para spesifik tempat, tapi kadang-kadang terlambat
dan aku bosan.
Apakah ada hal-hal lain tentang struktur data?
Saya yakin kalian tidak benar-benar ingin berbicara tentang mereka lagi,
tetapi jika ada, saya senang untuk pergi atas mereka, serta apa pun
dari kuliah ini melewati minggu atau minggu lalu.
>> Aku tahu minggu lalu adalah semua ulasan, jadi kita mungkin telah melompati beberapa ulasan
dari kuliah.
Pertanyaan lain saya bisa menjawab?
OK, baiklah.
Nah, kalian keluar 15 menit lebih awal.
>> Saya berharap ini adalah semi-membantu setidaknya, dan aku akan melihat kalian minggu depan,
atau Kamis jam kantor.
Apakah ada permintaan untuk makanan ringan untuk minggu depan, itu hal?
Karena aku lupa permen hari ini.
Dan aku membawa permen terakhir Minggu, tapi itu Columbus Day,
sehingga ada seperti enam orang yang memiliki empat kantong permen untuk diri mereka sendiri.
Aku bisa membawa Starbursts lagi jika Anda suka.
Starbursts?
OK, kedengarannya bagus.
Have a great day, guys.