>> [MUSIC PLAYING]
>> ANDI PENG: Selamat Datang di minggu 6 bagian.
Kami menyimpang dari standar kami Bagian waktu Selasa
sore hingga Minggu pagi yang indah ini.
Terima kasih untuk semua orang yang bergabung dengan saya hari ini, tapi serius,
tepuk tangan.
>> Itu upaya yang cukup besar.
Aku hampir tidak bahkan membuatnya dalam waktu, tetapi itu OK.
Jadi saya tahu bahwa kalian semua telah membuat untuk kuis.
Pertama-tama, selamat datang untuk sisi lain dari itu.
>> Kedua, kita akan berbicara tentang hal itu.
Kita akan berbicara tentang kuis.
Kami akan berbicara tentang bagaimana Anda lakukan di kelas.
Kamu akan baik-baik saja.
Saya memiliki kuis Anda untuk Anda di akhir di sini,
jadi jika kalian ingin mengambil a melihat itu, benar-benar baik-baik saja.
>> Begitu cepat sebelum kita mulai, yang agenda hari ini adalah sebagai berikut.
Seperti yang Anda lihat, kami tembak pada dasarnya cepat
melalui sejumlah besar struktur data benar-benar, benar-benar, benar-benar cepat.
Jadi dengan demikian, itu tidak akan hari ini yang super interaktif.
Itu hanya akan saya semacam berteriak hal-hal yang Anda, dan jika aku membingungkan Anda,
jika aku akan terlalu cepat, beritahu saya.
Mereka hanya berbagai data struktur, dan sebagai bagian
dari pset Anda untuk ini Minggu mendatang, Anda akan
diminta untuk melaksanakan salah satu dari mereka, mungkin dua dari them-- dua dari mereka
di pset Anda.
OK, jadi aku hanya akan mulai dengan beberapa pengumuman.
Kami akan pergi ke tumpukan dan antrian lebih mendalam dari apa yang kita lakukan sebelumnya kuis.
Kami akan pergi ke terkait daftar lagi, sekali lagi,
lebih mendalam dari apa kami memiliki sebelum kuis.
Dan kemudian kita akan berbicara tentang hash tabel, pohon dan mencoba, yang
semua cukup diperlukan untuk pset Anda.
Dan kemudian kita akan membahas beberapa tips-tips untuk pset5.
>> OK, jadi kuis 0.
Rata-rata adalah 58%.
Itu sangat rendah, sehingga kalian semua melakukan sangat, sangat baik sesuai
dengan.
>> Cukup banyak, aturan praktis adalah jika Anda dalam standar deviasi dari mean
terutama karena kita berada dalam kurang Bagian yang nyaman, Anda benar-benar baik-baik saja.
Anda berada di jalur.
Hidup adalah baik.
>> Aku tahu itu menakutkan untuk berpikir bahwa Aku punya seperti 40% pada kuis ini.
Aku akan gagal kelas ini.
Aku berjanji, Anda tidak akan gagal kelas.
Anda benar-benar baik-baik saja.
>> Bagi Anda yang punya lebih dari mean, mengesankan, mengesankan,
seperti, serius dilakukan dengan baik.
Saya memiliki mereka dengan saya.
Jangan ragu untuk datang mendapatkan mereka pada akhir bagian.
Let me know jika Anda memiliki masalah, pertanyaan dengan mereka.
Jika kita menambahkan nilai Anda salah, beritahu kami.
>> OK, jadi pset5, ini adalah benar-benar Minggu aneh untuk Yale dalam arti
yang pset kami adalah karena Rabu siang termasuk
hari akhir, sehingga benar-benar secara teoritis karena Selasa siang.
Mungkin tidak ada yang selesai di Selasa siang.
Itu benar-benar baik-baik saja.
Kita akan memiliki jam kantor malam serta Senin malam.
Dan semua bagian ini akan minggu benar-benar akan berubah menjadi lokakarya,
sehingga merasa bebas untuk pop setiap bagian yang Anda inginkan,
dan mereka akan menjadi semacam mini-pset lokakarya untuk bantuan itu.
Jadi dengan demikian, ini adalah satu-satunya bagian di mana kita mengajar materi.
Semua bagian lainnya akan memfokuskan eksklusif pada bantuan untuk pset tersebut.
Ya?
>> AUDIENCE: Dimana jam kantor?
>> ANDI PENG: jam Office tonight-- oh, pertanyaan yang bagus.
Saya pikir malam ini jam kantor berada di Teal atau Commons.
Jika Anda memeriksa CS50 secara online dan Anda pergi ke jam kantor,
harus ada jadwal yang memberitahu Anda di mana semua dari mereka adalah.
>> Saya tahu baik malam ini atau besok adalah teal,
dan saya pikir kita mungkin memiliki commons untuk malam.
Aku tidak yakin.
Pertanyaan bagus.
Memeriksa CS50.
>> Keren, pertanyaan tentang Jadwal untuk selanjutnya seperti tiga hari?
Aku berjanji kalian seperti David mengatakan, ini adalah puncak bukit.
Kalian hampir ada.
Hanya tiga hari lagi.
Sampai di sana, dan kemudian kita semua akan turun.
Kami akan memiliki baik istirahat CS-bebas.
Selamat Datang kembali.
Kami akan menyelam ke web pemrograman dan pengembangan,
hal-hal yang sangat menyenangkan dibandingkan untuk beberapa psets lainnya.
Dan itu akan menjadi dingin, dan kita akan memiliki banyak bersenang-senang.
Kami akan memiliki lebih banyak permen.
Maaf untuk permen.
Saya lupa permen.
Pagi itu kasar.
Jadi kalian hampir di sana, dan aku benar-benar bangga kalian.
>> OK, jadi tumpukan.
Yang mencintai pertanyaan tentang Jack dan pakaiannya di kuis?
Tak seorangpun?
Baiklah tidak apa apa.
>> Jadi pada dasarnya yang Anda bisa gambar Jack, orang ini di sini,
mencintai untuk mengambil pakaian dari puncak stack,
dan ia menempatkan kembali ke tumpukan setelah dia lakukan.
Jadi dengan cara ini, dia tidak pernah tampaknya akan semakin
ke bawah tumpukan di pakaiannya.
Jadi ini semacam menggambarkan struktur data dasar
bagaimana stack diimplementasikan.
>> Pada dasarnya, memikirkan tumpukan sebagai salah tumpukan benda
di mana Anda meletakkan segala sesuatu ke atas, dan maka Anda pop mereka keluar dari atas.
Jadi LIFO adalah singkatan kita suka untuk use-- terakhir Dalam, First Out.
Dan terakhir ke atas stack adalah yang pertama yang keluar.
Dan dua istilah kami ingin mengasosiasikan
dengan yang disebut push dan pop.
Ketika Anda mendorong sesuatu ke stack, dan Anda pop itu kembali.
>> Dan jadi saya kira ini adalah jenis konsep abstrak bagi anda
yang ingin melihat seperti implementasi aktual ini
di dunia nyata.
Berapa banyak dari Anda telah menulis sebuah esai mungkin seperti satu jam sebelum itu karena,
dan Anda tidak sengaja menghapus besar sepotong itu, seperti sengaja?
Dan kemudian apa yang kontrol dilakukan kita gunakan untuk menempatkan kembali?
Control-Z, ya?
Control-Z, sehingga jumlah kali bahwa Control-Z telah menyelamatkan hidup saya,
telah menyelamatkan pantatku, setiap kali yang dilaksanakan melalui stack.
>> Dasarnya semua informasi yang ada di dokumen Word Anda,
itu akan mendorong dan muncul di akan.
Dan pada dasarnya setiap kali Anda menghapus apapun, Anda pop itu kembali.
Dan kemudian jika Anda membutuhkannya kembali, Anda dorong, yang adalah apa Control-C tidak.
Dan fungsi dunia begitu nyata dari struktur data cara sederhana
dapat membantu dengan kehidupan sehari-hari Anda.
>> Jadi struct adalah cara yang kita benar-benar membuat stack.
Kita ketik mendefinisikan struct, dan kemudian kita menyebutnya tumpukan di bagian bawah.
Dan dalam stack, kita memiliki dua parameter
bahwa kita pada dasarnya dapat memanipulasi, jadi kita harus arang kapasitas bintang string.
>> Semua yang melakukan adalah menciptakan sebuah array
bahwa kita dapat menyimpan apapun yang Anda inginkan yang kita dapat menentukan kapasitasnya.
Kapasitas Apakah hanya jumlah maksimum barang yang kami dapat dimasukkan ke dalam array ini.
ukuran int adalah counter yang terus melacak berapa banyak item yang saat ini
dalam tumpukan.
Jadi kita bisa melacak, A, kedua seberapa besar tumpukan sebenarnya,
dan, B, berapa banyak tumpukan yang kami diisi karena kita tidak ingin
meluap atas apa kapasitas kami adalah.
>> Jadi misalnya, ini indah pertanyaan pada kuis Anda.
Pada dasarnya bagaimana kita mendorong ke atas tumpukan.
Cukup sederhana.
Jika Anda melihat itu, kita akan berjalan melalui ini.
Jika [tidak terdengar] size-- ingat, setiap kali Anda
ingin mengakses parameter dalam struct,
Anda nama struct.parameter tersebut.
>> Dalam hal ini, s adalah nama tumpukan kami.
Kami ingin mengakses ukuran itu, jadi kami lakukan s.size.
Jadi selama ukuran tidak sama dengan kapasitas atau selama
seperti itu kurang dari kapasitas, baik akan bekerja di sini.
>> Anda ingin mengakses dalam tumpukan Anda, sehingga s.strings,
dan Anda akan menempatkan bahwa nomor baru bahwa Anda ingin masukkan ke sana.
Anggap saja kita akan ingin masukkan int n ke stack,
kita bisa melakukan s.strings, kurung, s.size sama n.
Karena ukuran adalah di mana kita saat ini berada di stack
jika kita akan mendorong itu, kita hanya mengakses
dimanapun ukuran adalah, kepenuhan saat stack,
dan kami mendorong int n ke atasnya.
Dan kemudian kami ingin memastikan bahwa kami juga incrementing ukuran n,
sehingga kami bisa melacak kita sudah menambahkan hal ekstra untuk stack.
Sekarang kita memiliki ukuran yang lebih besar.
Apakah ini di sini masuk akal untuk semua orang, bagaimana secara logis kerjanya?
Itu jenis cepat.
AUDIENCE: Dapatkah Anda pergi yang s.stringss.strings [s.size] lagi?
ANDI PENG: Tentu, jadi apa s.size saat memberi kita?
AUDIENCE: Ini ukuran saat ini.
ANDI PENG: Tepat, sehingga Indeks saat ini bahwa ukuran kami di,
dan jadi kami ingin menempatkan integer baru bahwa kita ingin masukkan ke s.size.
Apakah itu masuk akal?
Karena s.strings, semua yang adalah adalah nama dari array.
Semua itu adalah mengakses Array dalam struct kami,
dan jadi jika kita ingin menempatkan n ke dalam indeks itu,
kita hanya bisa mengaksesnya menggunakan kurung s.size.
Keren.
>> Baiklah, pop, saya pseudocode itu untuk kalian, tapi konsep yang sama.
Apakah itu masuk akal?
Jika ukuran lebih besar dari nol, maka Anda
tahu bahwa Anda ingin mengambil sesuatu karena jika ukuran tidak
lebih besar dari nol, maka Anda tidak ada dalam tumpukan.
>> Jadi Anda hanya ingin mengeksekusi kode ini, hanya bisa
pop jika ada sesuatu untuk pop.
Jadi jika ukuran lebih besar dari 0, kita dikurangi ukuran.
Kami pengurangan ukuran dan kemudian kembali apapun yang di dalamnya karena
oleh bermunculan, kita ingin Akses apapun yang disimpan
dalam indeks dari atas tumpukan.
Semuanya masuk akal?
Jika saya membuat kalian menulis ini keluar, akan kalian dapat menulis itu?
OK, kalian bisa bermain-main dengan hal itu.
Jangan khawatir jika Anda tidak mendapatkannya.
Kami tidak punya waktu untuk kode keluar hari ini karena kami sudah
mendapat banyak struktur ini untuk pergi melalui, tetapi pada dasarnya
pseudocode, sangat, sangat mirip dengan mendorong.
Cukup ikuti bersama logika.
Pastikan Anda mengakses semua fitur struct Anda benar.
Ya?
>> AUDIENCE: Will slide ini dan semua ini sampai hari ini-ish?
ANDI PENG: Selalu, yep.
Aku akan mencoba untuk menempatkan ini seperti satu jam setelah.
Saya akan mengirimkan email David, David akan mencoba untuk memasangnya seperti satu jam setelah ini.
>> OK, jadi maka kita pindah ke lain ini struktur data indah yang disebut antrian.
Seperti kalian bisa lihat di sini, sebuah antrian, untuk Inggris di antara kita,
semua itu adalah garis.
Jadi bertentangan dengan apa Anda berpikir stack adalah,
antrian adalah apa yang logis Anda pikirkan.
Ini diselenggarakan oleh aturan FIFO, yang Pertama Dalam, First Out.
Jika Anda pertama satu di baris, Anda
yang pertama yang keluar dari garis.
>> Jadi apa yang kita suka menyebutnya ini adalah dequeueing dan enqueueing.
Jika kita ingin menambahkan sesuatu untuk antrian kami, kami enqueue.
Jika kita ingin dequeue, atau mengambil sesuatu yang jauh, kita dequeue.
>> Akal sehingga sama yang kita jenis menciptakan elemen berukuran tetap yang kita
dapat menyimpan tertentu hal, tapi kami juga bisa
mengubah mana kita menempatkan parameter dalam diri mereka
berdasarkan jenis fungsi yang kita inginkan.
Jadi tumpukan, kami ingin yang terakhir satu, N menjadi yang pertama keluar.
Antrian adalah kami ingin hal pertama untuk menjadi hal pertama keluar.
>> Jadi struct-jenis mendefinisikan, seperti yang Anda lihat,
itu sedikit berbeda dari apa stack adalah
karena kita tidak hanya harus terus melacak di mana ukuran saat ini,
kami juga ingin melacak kepala serta di mana saat ini kita berada.
Jadi saya pikir itu lebih mudah jika saya menggambar hal ini.
Jadi mari kita bayangkan kita punya antrian, jadi mari kita katakan kepala ada di sini.
Kepala garis, mari kita hanya mengatakan itu saat ini ada,
dan kami ingin memasukkan sesuatu ke dalam antrian.
Aku akan memanggil ukuran dasarnya adalah hal yang sama seperti ekor,
akhir mana pun antrian Anda.
Mari kita hanya mengatakan ukuran ada di sini.
>> Jadi bagaimana satu feasibly memasukkan sesuatu ke dalam antrian?
Apa Indeks kita ingin menempatkan di mana kita ingin memasukkan ke dalam.
Jika ini adalah awal dari Anda antrian dan ini adalah akhir dari itu
atau ukuran itu, di mana kita ingin menambahkan objek berikutnya?
>> AUDIENCE: [tidak terdengar]
ANDI PENG: Tepat, Anda ingin menambahkan itu tergantung pada yang telah ditulis itu.
Entah ini kosong atau yang kosong.
Jadi Anda ingin menambahkan mungkin di sini karena jika ukuran is--
jika ini semua penuh, Anda ingin menambahkannya di sini, kan?
>> Dan jadi itu, sementara sangat, sangat sederhana, tidak cukup selalu benar
karena perbedaan utama antara antrian dan tumpukan
adalah bahwa antrian bisa sebenarnya dimanipulasi
sehingga perubahan kepala tergantung di mana Anda ingin
awal isyarat Anda untuk memulai.
Dan sebagai hasilnya, ekor Anda juga akan berubah.
Dan lihatlah Kode ini sekarang.
Seperti kalian juga diminta untuk menulis pada kuis, enqueue.
Mungkin kita akan berbicara melalui mengapa jawabannya adalah apa itu.
>> Saya tidak bisa cukup sesuai baris ini pada satu, tapi pada dasarnya ini bagian dari kode
harus pada satu baris.
Menghabiskan seperti 30 detik.
Coba lihat, dan melihat mengapa ini adalah cara yang itu.
>> Sangat, struct sangat mirip, sangat, sangat struktur yang sama seperti sebelumnya
tumpukan kecuali mungkin satu baris kode.
Dan bahwa satu baris kode menentukan fungsi tersebut.
Dan itu benar-benar membedakan antrian dari tumpukan.
>> Siapapun ingin mengambil bacokan di menjelaskan mengapa Anda sudah
mendapat hal ini rumit di sini?
Kita melihat kembalinya kami indah teman modulus.
Seperti kalian akan segera datang untuk mengenali dalam pemrograman,
hampir kapan saja Anda perlu sesuatu untuk membungkus sesuatu,
modulus akan menjadi cara untuk melakukannya.
Jadi mengetahui bahwa, apakah ada yang ingin mencoba menjelaskan bahwa baris kode?
Ya, semua jawaban yang diterima dan diterima.
AUDIENCE: Apakah Anda berbicara dengan saya?
ANDI PENG: Ya.
AUDIENCE: Oh, tidak menyesal.
ANDI PENG: OK, jadi mari kita berjalan melalui kode ini.
Jadi, ketika Anda mencoba untuk menambahkan sesuatu ke antrian,
dalam kasus indah yang kepala terjadi menjadi di sini, itu sangat mudah bagi kita
untuk hanya pergi ke akhir memasukkan sesuatu, kan?
Tapi seluruh titik antrian adalah bahwa kepala benar-benar dapat dinamis
berubah tergantung pada di mana kita ingin awal q kami untuk menjadi,
dan dengan demikian, ekor juga akan berubah.
>> Dan membayangkan bahwa ini bukan antrian, melainkan ini adalah antrian.
Katakanlah kepala ada di sini.
Katakanlah antrian kami tampak seperti ini.
Jika kita ingin menggeser mana awal garis adalah,
katakanlah kita bergeser kepala cara ini dan ukuran di sini.
>> Sekarang kita ingin menambahkan sesuatu untuk antrian ini, tetapi sebagai kalian bisa lihat,
itu tidak begitu sederhana seperti hanya menambahkan apa pun adalah setelah ukuran
karena dengan begitu kita kehabisan batas-batas array kita yang sebenarnya.
Di mana kita ingin benar-benar menambah sini.
Itulah keindahan antrian adalah bahwa untuk kita, visual itu
Sepertinya garis berjalan seperti ini, tetapi ketika disimpan dalam struktur data,
mereka memberikan sebagai seperti siklus.
Ini semacam membungkus di sekitar ke depan dengan cara yang sama
bahwa garis juga bisa membungkus sekitar tergantung pada di mana pun Anda
ingin awal baris untuk menjadi.
Dan jika kita mengambil melihat ke bawah sini, mari kita
mengatakan kami ingin membuat fungsi yang disebut enqueue.
Kami ingin menambahkan int n ke q itu.
Jika q.size q-- kita akan menelepon bahwa data kami structure-- jika queue.size kami tidak
sama dengan kapasitas atau jika itu kurang dari kapasitas,
q.strings adalah array dalam q kami.
Kita akan mengatur yang sama dengan q.heads,
yang ada di sini, ditambah q.size modulus oleh kapasitas, yang
membungkus kita kembali di sini.
>> Jadi, dalam contoh ini, indeks kepala adalah 1, kan?
Indeks ukuran 0, 1, 2, 3, 4.
Jadi kita bisa melakukan 1 ditambah 4 modulus oleh kemampuan kita yang 5.
Apa yang memberi kita?
Apa indeks yang keluar dari ini?
>> AUDIENCE: 0.
>> ANDI PENG: 0, yang kebetulan di sini,
dan jadi kami ingin dapat untuk memasukkan ke sini.
Dan persamaan ini di sini jenis hanya bekerja dengan angka apapun
tergantung di mana Anda kepala dan ukuran Anda.
Jika Anda tahu apa yang mereka hal-hal yang, Anda tahu
persis di mana Anda ingin menyisipkan apa pun yang setelah antrian Anda.
Apakah itu masuk akal untuk semua orang?
>> Saya tahu jenis otak teaser terutama karena ini
datang setelah kuis Anda.
Tapi mudah-mudahan semua orang sekarang dapat memahami
mengapa solusi ini atau ini Fungsi adalah cara yang itu.
Siapapun agak tidak jelas itu?
OKE.
>> Dan sekarang, jika Anda ingin dequeue, ini
adalah di mana kepala kita akan menggeser karena jika kita dequeue,
kita tidak mengambil dari ujung q itu.
Kami ingin melepas kepala, kan?
Jadi sebagai hasilnya, kepala akan berubah, dan itulah sebabnya ketika Anda enqueue,
Anda harus melacak di mana kepala Anda dan ukuran Anda
yang dapat memasukkan ke posisi yang benar.
>> Dan jadi ketika Anda dequeue, Saya juga pseudocode itu.
Jangan ragu untuk jika Anda ingin untuk mencoba coding ini.
Anda ingin memindahkan kepala, kan?
Jika saya ingin dequeue, saya akan memindahkan kepala lebih.
Ini akan menjadi kepala.
>> Dan ukuran kami saat ini akan kurangi karena kita tidak lagi
memiliki empat elemen dalam array.
Kami hanya memiliki tiga, dan kemudian kita ingin untuk kembali apa pun yang disimpan di dalam
kepala karena kami ingin mengambil ini Nilai keluar sehingga sangat mirip dengan stack.
Hanya Anda mengambil dari tempat yang berbeda,
dan Anda harus menetapkan kembali pointer Anda ke tempat yang berbeda sebagai hasilnya.
Logikanya, semua orang ikuti?
Besar.
>> OK, jadi kita akan berbicara sedikit lebih mendalam tentang daftar terkait
karena mereka akan sangat, sangat berharga untuk Anda dalam perjalanan minggu ini
psets.
Daftar terkait, seperti kalian ingat, semua mereka
adalah node yang node tertentu nilai-nilai baik nilai dan pointer
yang dihubungkan bersama oleh mereka pointer.
Dan struct pada bagaimana kami membuat simpul di sini adalah kita
memiliki int n, yang adalah apa pun nilai di toko atau tali n
atau apa pun yang Anda ingin menyebutnya, n bintang arang.
Struct bintang node, yang merupakan pointer bahwa Anda ingin memiliki di setiap node,
Anda akan memiliki yang titik pointer ke arah depan.
Anda akan memiliki kepala dari linked list yang
akan menunjukkan ke seluruh nilai-nilai sebagainya dan sebagainya
sampai Anda akhirnya mencapai akhir.
Dan node terakhir ini hanya akan tidak memiliki pointer.
Ini akan menunjukkan null, dan saat itulah
Anda tahu Anda telah memukul akhir daftar Anda terkait
adalah ketika pointer terakhir Anda tidak menunjuk ke apapun.
>> Jadi kita akan pergi sedikit lebih dalam mendalam tentang bagaimana seseorang akan mungkin
mencari daftar link.
Ingat apa adalah beberapa kelemahan dari daftar terkait
ayat array mengenai pencarian.
Array Anda bisa pencarian biner, tapi mengapa Anda tidak dapat melakukan itu dalam sebuah linked list?
>> AUDIENCE: Karena mereka semua terhubung, tapi Anda tidak cukup tahu di mana
[Tidak terdengar].
>> ANDI PENG: Ya, persis begitu ingat bahwa kecemerlangan array
adalah fakta bahwa kami memiliki random access memory mana
jika saya ingin nilai dari indeks enam, saya hanya bisa mengatakan indeks enam,
memberikan nilai tersebut.
Dan itu karena array diurutkan dalam ruang memori yang berdekatan
di satu tempat, sedangkan jenis daftar terkait
adalah acak diselingi sekitar, dan satu-satunya cara Anda dapat menemukan satu
adalah melalui pointer yang memberitahu Anda alamat di mana simpul berikutnya adalah.
>> Dan sebagai hasilnya, satu-satunya cara untuk mencari melalui linked list
adalah pencarian linear.
Karena saya tidak tahu persis di mana nilai 12 dalam linked list adalah,
Saya harus melintasi keseluruhan yang itu terkait daftar satu
oleh salah satu dari kepala ke node pertama, ke node kedua, ke node ketiga,
semua jalan sampai akhirnya aku mendapatkan ke tempat yang simpul saya cari adalah.
Dan dalam hal ini, pencarian pada linked list selalu n.
Itu selalu n.
Itu selalu dalam waktu linier.
>> Dan kode yang kita melaksanakan ini, dan ini
agak baru untuk kalian karena Anda orang belum benar-benar berbicara tentang atau pernah
pointer terlihat di cara mencari melalui pointer,
jadi kita akan berjalan melalui ini sangat, sangat lambat.
Jadi pencarian bool, tepat, mari kita bayangkan kita ingin
untuk membuat fungsi yang disebut pencarian yang mengembalikan benar
jika Anda menemukan nilai dalam terkait daftar, dan ia mengembalikan palsu sebaliknya.
Daftar bintang node Saat ini hanya pointer
untuk item pertama dalam daftar Anda terkait.
int n adalah nilai yang Anda mencari dalam daftar itu.
>> Jadi Bintang simpul pointer sama dengan daftar.
Itu berarti kita sedang menyiapkan dan menciptakan pointer
untuk yang node pertama dalam daftar.
Semua orang dengan saya?
Jadi jika kita pergi kembali ke sini, saya akan memiliki
diinisialisasi pointer yang menunjuk ke kepala dari apa pun daftar itu.
>> Dan kemudian setelah Anda mendapatkan di sini, sementara pointer tidak nol sama,
sehingga merupakan lingkaran di mana kita akan kemudian melintasi
sisa daftar kami karena apa terjadi ketika pointer sama dengan nol?
Kita tahu bahwa kita have--
>> AUDIENCE: [tidak terdengar]
>> ANDI PENG: Tepat, jadi kita tahu bahwa kita telah mencapai akhir dari daftar, kan?
Jika Anda pergi ke sini, setiap node harus menunjuk ke node lain
dan sebagainya dan sebagainya sampai Anda menekan akhirnya
ekor daftar Anda terhubung, yang memiliki pointer yang hanya
tidak menunjuk mana saja selain tidak ada.
Dan sehingga Anda pada dasarnya tahu bahwa daftar Anda masih ada up
sampai pointer tidak sama dengan null karena setelah itu sama dengan nol,
Anda tahu bahwa tidak ada hal yang lebih.
>> Jadi itu adalah lingkaran dimana kami akan memiliki pencarian yang sebenarnya.
Dan jika pointer-- yang Anda lihat semacam panah fungsi sana?
Jadi jika pointer menunjuk ke n, jika pointer pada n sama sama n,
sehingga berarti bahwa jika pointer yang Anda
mencari di akhir setiap simpul sebenarnya sama dengan nilai
Anda sedang mencari, kemudian Anda ingin kembali benar.
Jadi pada dasarnya, jika Anda berada di sebuah node yang memiliki nilai yang Anda cari,
Anda tahu bahwa Anda sudah berhasil mencari.
>> Jika tidak, Anda ingin mengatur pointer Anda ke node berikutnya.
Itulah yang yang sejalan sini adalah melakukan.
Pointer sama pointer berikutnya.
Semua orang melihat bagaimana yang bekerja?
>> Dan pada dasarnya Anda akan hanya melintasi keseluruhan daftar,
ulang pointer Anda setiap kali sampai Anda akhirnya memukul akhir daftar.
Dan Anda tahu bahwa tidak ada lebih node untuk mencari melalui,
dan kemudian Anda dapat kembali palsu karena Anda tahu bahwa, oh, baik,
jika saya sudah bisa mencari melalui keseluruhan daftar.
Jika dalam contoh ini, jika saya ingin untuk mencari nilai 10,
dan aku mulai kepala, dan Saya mencari semua jalan ke bawah,
dan saya akhirnya harus ini, yang pointer yang menunjuk ke null,
Aku tahu itu, omong kosong, saya kira 10 tidak di daftar ini karena saya tidak bisa menemukannya.
Dan aku di akhir daftar.
Dan dalam hal ini Anda tahu Aku akan kembali palsu.
>> Biarkan yang rendam dalam untuk sedikit.
Ini akan cukup penting untuk pset Anda.
Logika sangat sederhana, mungkin sintaksis hanya mengimplementasikannya.
Kalian ingin membuat Pastikan bahwa Anda memahami.
Keren.
>> OK, jadi bagaimana kita akan menyisipkan node, tepat,
ke dalam daftar karena ingat apa apa manfaat
memiliki daftar link vs array dalam hal penyimpanan?
>> AUDIENCE: Ini dinamis, sehingga lebih mudah to--
>> ANDI PENG: Tepat, jadi dinamis, yang
berarti bahwa ia dapat memperluas dan menyusut tergantung pada kebutuhan pengguna.
Dan, dalam pengertian ini, kita tidak perlu membuang memori yang tidak perlu karena saya
jika saya tidak tahu berapa banyak nilai-nilai yang saya inginkan ke toko, itu tidak masuk akal bagi saya
untuk membuat sebuah array karena jika saya ingin menyimpan 10 nilai
dan saya membuat sebuah array dari 1.000, yang banyak memori terbuang, diberikan.
Itu sebabnya kami ingin menggunakan linked Daftar untuk dapat dinamis
mengubah atau menyusut ukuran kami.
>> Dan sehingga membuat penyisipan sedikit lebih rumit.
Karena kita tidak dapat secara acak mengakses elemen cara kita akan dari array.
Jika saya ingin memasukkan unsur dalam indeks ketujuh,
Aku hanya bisa masukkan ke dalam indeks ketujuh.
Pada linked list, tidak cukup bekerja dengan mudah,
dan jadi jika kita ingin menyisipkan satu di sini dalam linked list,
visual, itu sangat mudah untuk melihat.
Kami hanya ingin memasukkannya di sana, tepat di awal daftar,
setelah kepala.
>> Namun cara di mana kita harus menetapkan kembali pointer adalah sedikit berbelit-belit
atau, secara logis, masuk akal, tapi Anda ingin memastikan bahwa Anda memilikinya
benar-benar turun karena hal terakhir yang Anda inginkan
adalah untuk menetapkan kembali pointer yang cara yang kita lakukan di sini.
Jika Anda dereference pointer dari kepala sampai 1,
maka semua dari tiba-tiba sisa daftar Anda terkait
hilang karena Anda harus benar-benar menciptakan sesuatu yang sementara.
Itu menunjuk ke 2.
Jika Anda menetapkan kembali pointer, maka sisa daftar Anda benar-benar hilang.
Jadi Anda ingin menjadi sangat, sangat berhati-hati di sini
untuk pertama menetapkan pointer dari apa pun yang Anda
ingin masukkan ke mana pun yang Anda inginkan, dan kemudian Anda
bisa dereference sisa daftar Anda.
>> Jadi ini berlaku untuk dimanapun Anda mencoba untuk memasukkan ke dalam.
Jika Anda ingin memasukkan di kepala, jika Anda ingin menjawab di sini,
jika Anda ingin memasukkan di akhirnya, baik, akhirnya saya
kira Anda akan hanya tidak memiliki pointer, tetapi Anda
ingin memastikan bahwa Anda tidak kehilangan sisa daftar Anda.
Anda selalu ingin memastikan node baru Anda menunjuk
terhadap apa pun yang Anda ingin masukkan ke dalam,
dan kemudian Anda dapat menambahkan chaining pada.
Semua orang yang jelas?
>> Ini akan menjadi salah satu masalah yang nyata.
Salah satu yang paling isu utama Anda akan memiliki pada pset Anda
adalah bahwa Anda akan mencoba untuk membuat daftar link dan hal insert
tapi kemudian hanya kehilangan sisa daftar Anda terkait.
Dan Anda akan menjadi seperti, saya tidak tahu mengapa hal ini terjadi?
Dan itu sakit untuk pergi melalui dan mencari semua pointer Anda.
>> Dan saya jamin Anda di pset ini, menulis dan menggambar node ini keluar
akan sangat, sangat membantu.
Jadi Anda benar-benar dapat melacak dari mana semua pointer Anda,
apa yang salah, di mana semua node Anda,
apa yang perlu Anda lakukan untuk mengakses atau memasukkan atau menghapus atau salah satu dari mereka.
Semua orang baik dengan itu?
Keren.
>> Jadi jika kita ingin melihat kode?
Oh, aku tidak tahu apakah kita dapat melihat OK the--, sehingga
di atas semua itu adalah fungsi bernama insert mana kita ingin
untuk menyisipkan int n ke dalam linked list.
Kita akan berjalan melalui ini.
Ini banyak kode, banyak sintaks baru.
Kami akan OK.
>> Jadi di atas, setiap kali kami ingin menciptakan sesuatu
apa yang perlu kita lakukan, terutama jika Anda ingin untuk tidak disimpan di stack
namun di heap?
Kami pergi ke malloc, kan?
Jadi kita akan membuat sebuah pointer.
Node, pointer, equals baru malloc ukuran node
karena kami ingin node yang akan dibuat.
Kami ingin jumlah memori yang node memakan
akan dialokasikan untuk penciptaan node baru.
>> Dan kemudian kita akan memeriksa untuk melihat apakah sama dengan yang baru sama null.
Ingat apa yang kita katakan?
Apa pun yang Anda malloc, apa yang harus Anda selalu lakukan?
Anda harus selalu memeriksa untuk melihat apakah atau tidak itu adalah nol.
>> Sebagai contoh, jika operasi Anda Sistem benar-benar penuh,
jika Anda tidak memiliki lebih banyak memori di semua dan Anda mencoba untuk malloc,
itu akan kembali null untuk Anda.
Dan jadi jika Anda mencoba untuk menggunakannya ketika itu menunjuk ke null,
Anda tidak akan bisa untuk mengakses informasi tersebut.
Dan dengan demikian, kami ingin membuat Pastikan bahwa setiap kali Anda mallocing,
Anda selalu memeriksa untuk melihat apakah bahwa memori diberikan kepada Anda adalah nol.
Dan jika tidak, maka kita bisa bergerak pada dengan sisa kode kita.
>> Jadi kita akan menginisialisasi node baru.
Kami akan melakukan yang baru n sama n.
Dan kemudian kita akan melakukan mengatur baru pointer pada baru
untuk nol karena sekarang kita tidak ingin apa-apa untuk itu untuk menunjuk ke.
Kami tidak tahu di mana itu akan menempatkan Anda,
dan kemudian jika kita ingin masukkan di kepala,
maka kita dapat menetapkan kembali pointer ke kepala.
Apakah setiap orang mengikuti logika dari mana itu terjadi?
>> Semua yang kita lakukan adalah menciptakan baru node, pengaturan pointer ke null,
dan kemudian pemindahan untuk kepala jika kita
tahu kita ingin memasukkannya di kepala.
Dan kemudian kepala akan menunjuk ke arah yang simpul baru.
Semua orang OK dengan itu?
>> Jadi itu adalah proses dua langkah.
Anda harus menetapkan pertama apa pun yang Anda ciptakan.
Mengatur bahwa pointer ke referensi, dan kemudian Anda
bisa jenis dereference pointer pertama
dan menunjuk ke arah simpul baru.
Di mana pun Anda ingin memasukkannya, logika yang akan berlaku.
>> Ini semacam seperti menugaskan variabel sementara.
Ingat, Anda punya memastikan bahwa Anda
tidak kehilangan jejak jika Anda swapping.
Anda ingin memastikan bahwa Anda memiliki variabel sementara jenis terus
melacak di mana hal yang disimpan sehingga Anda
tidak kehilangan nilai dalam kursus seperti main-main dengan hal itu.
>> OK, jadi kode akan berada di sini.
Kalian lihat setelah bagian.
Ini akan berada di sana.
>> Jadi saya kira bagaimana ini berbeda jika kita ingin
untuk memasukkan ke tengah atau akhir?
Apakah ada yang punya ide tentang apa pseudocode sebagai referensi logis
bahwa kita akan mengambil jika kita ingin untuk menyisipkan di tengah?
Jadi jika kita ingin masukkan di kepala, semua yang kita lakukan adalah membuat node baru.
Kami mengatur pointer itu node baru apa pun kepala,
dan kemudian kita mengatur kepala ke node baru, kan?
Jika kita ingin memasukkannya di tengah dari daftar, apa yang harus kita lakukan?
>> AUDIENCE: Ini akan masih menjadi proses yang sama
seperti menugaskan pointer dan kemudian menugaskan pointer itu,
tapi kita harus mencari di sana.
>> ANDI PENG: Tepat, sehingga persis proses yang sama kecuali Anda
harus mencari di mana tepatnya Anda ingin bahwa pointer baru untuk masuk ke dalam,
jadi jika saya ingin masukkan ke tengah terkait list-- OK,
katakanlah itu linked list kami.
Jika kita ingin memasukkannya di sini, kita akan membuat node baru.
Kita akan malloc.
Kita akan membuat node baru.
Kita akan menetapkan pointer dari node ini di sini.
>> Tapi masalahnya yang berbeda dari mana kepala adalah
adalah bahwa kita tahu persis di mana kepala adalah.
Itu tepat di pertama, kan?
Tapi di sini kita harus melacak dari mana kita memasukkan ke.
Jika kita memasukkan kami simpul di sini, kami punya
untuk memastikan bahwa sebelumnya ke node ini
adalah salah satu yang reassigns pointer.
Jadi Anda harus jenis melacak dua hal.
Jika Anda melacak di mana ini simpul saat ini memasukkan ke.
Anda juga harus melacak di mana node sebelumnya yang Anda cari di
juga ada.
Semua orang baik dengan itu?
OKE.
>> Bagaimana memasukkan ke akhir?
Jika saya ingin menambahkannya di sini-jika saya ingin untuk menambahkan node baru ke akhir daftar,
bagaimana mungkin aku pergi untuk melakukan itu?
AUDIENCE: Jadi saat ini, yang satu lalu menunjuk ke null.
ANDI PENG: Ya.
Tepat, jadi yang satu ini saat ini menunjuk tahu,
dan jadi saya kira, dalam pengertian ini, itu sangat mudah untuk menambahkan ke akhir daftar.
Yang harus Anda lakukan adalah mengatur itu sama dengan nol dan kemudian booming.
Di sana, sangat mudah.
Sangat sederhana.
>> Sangat mirip dengan kepala, tetapi secara logis Anda
ingin memastikan bahwa langkah-langkah Anda ambil terhadap melakukan semua ini,
Anda mengikuti bersama.
Ini sangat mudah untuk, di tengah kode Anda, terjebak pada,
oh, aku punya begitu banyak pointer.
Saya tidak tahu di mana apapun menunjuk ke.
Aku bahkan tidak tahu yang simpul aku di.
Apa yang sedang terjadi?
>> Tenang, tenang, ambil napas dalam.
Menarik keluar daftar Anda terkait.
Jika Anda mengatakan, saya tahu di mana tepatnya Saya harus memasukkan ini ke
dan saya tahu persis bagaimana untuk menetapkan kembali saya pointer, jauh, jauh lebih mudah untuk membayangkan
out-- banyak, jauh lebih mudah untuk tidak tersesat di bug kode Anda.
Semua orang OK dengan itu?
OKE.
>> Jadi saya kira konsep yang kita miliki tidak benar-benar berbicara tentang sebelum sekarang,
dan saya kira Anda mungkin tidak akan menghadapi banyak yet--
itu jenis dari concept-- canggih adalah bahwa kita benar-benar memiliki data
struktur yang disebut daftar ganda terkait.
Sehingga kalian bisa melihat, semua yang kita lakukan adalah menciptakan
nilai sebenarnya, tambahan pointer pada setiap node kami
yang juga menunjuk ke simpul sebelumnya.
Jadi kita tidak hanya memiliki kita node menunjuk ke yang berikutnya.
Mereka juga menunjuk pada sebelumnya.
Aku akan mengabaikan kedua sekarang.
>> Jadi Anda memiliki rantai yang dapat bergerak dua arah,
dan kemudian itu sedikit lebih mudah untuk secara logis mengikuti bersama.
Seperti di sini, bukannya melacak, oh, saya
harus tahu bahwa simpul ini salah satu yang saya harus menetapkan kembali,
Aku hanya bisa pergi di sini dan hanya tarik sebelumnya.
Kemudian saya tahu persis di mana yaitu, dan kemudian Anda
tidak perlu melintasi keseluruhan dari linked list.
Ini sedikit lebih mudah.
>> Tapi dengan demikian, Anda memiliki dua kali lipat jumlah pointer,
itu dua kali lipat jumlah memori.
Ini banyak pointer untuk melacak.
Ini sedikit lebih kompleks, tapi itu sedikit lebih user friendly tergantung
pada apa yang Anda capai.
>> Sehingga jenis data struktur benar-benar ada,
dan struktur adalah sangat, sangat sederhana kecuali semua Anda mengalami adalah,
bukan hanya pointer ke depan, Anda juga memiliki pointer ke sebelumnya.
Itu semua perbedaan itu.
Semua orang baik dengan itu?
Keren.
>> Baiklah, jadi sekarang aku untuk benar-benar menghabiskan mungkin
seperti 15 sampai 20 menit atau bulk dari sisa waktu di bagian
berbicara tentang tabel hash.
Berapa banyak dari kalian telah membaca pset5 spesifikasi?
Baiklah, baik.
Itu lebih tinggi dari 50% dari biasanya.
Tidak apa-apa.
>> Sehingga kalian akan melihat, Anda tantangan di pset5
akan menerapkan kamus di mana Anda memuat lebih dari 140.000 kata-kata
bahwa kita memberikan dan spell check melawan semua teks.
Kami akan memberikan acak potongan sastra.
Kami akan memberikan Odyssey.
Kami akan memberikan The Iliad.
Kami akan memberikan Austin Powers.
>> Dan tantangan Anda akan mengeja cek
setiap kata di semua orang kamus
dasarnya dengan spell checker kita.
Dan jadi ada beberapa bagian menciptakan pset ini,
pertama yang Anda ingin menjadi dapat benar-benar memuat
semua kata-kata menjadi Anda kamus, dan kemudian Anda
ingin dapat spell check semua dari mereka.
Dan dengan demikian, Anda akan memerlukan struktur data yang dapat melakukan hal ini dengan cepat
dan efisien dan dinamis.
>> Jadi saya kira yang paling mudah cara untuk melakukan ini, Anda
mungkin akan membuat sebuah array, kan?
Cara termudah penyimpanan adalah Anda dapat membuat array 140.000 kata
dan hanya menempatkan mereka semua ada dan kemudian melintasi mereka dengan pencarian biner
atau dengan pilihan atau not-- maaf yang penyortiran.
Anda dapat mengurutkan mereka dan kemudian melintasi mereka oleh pencarian biner atau pencarian hanya linear
dan hanya akhir kata-kata, tapi itu Dibutuhkan sejumlah besar memori,
dan itu tidak sangat efisien.
>> Dan kita akan mulai berbicara tentang cara membuat
waktu kita berjalan lebih efisien.
Dan tujuan kami adalah untuk mendapatkan waktu yang konstan di mana
itu hampir seperti array, di mana Anda memiliki akses seketika.
Jika saya ingin mencari sesuatu, Saya ingin bisa hanya,
booming, merasa persis, dan menariknya keluar.
Dan struktur di mana kita akan menjadi sangat dekat
untuk dapat mengakses konstan waktu, grail suci ini
dalam pemrograman konstan waktu disebut tabel hash.
Dan David yang disebutkan sebelumnya [Tak terdengar] sedikit di kuliah,
tapi kita akan benar-benar menyelam di dalam minggu ini
pada selembar yang mengenai bagaimana tabel hash bekerja.
>> Jadi cara yang hash karya meja, misalnya,
jika saya ingin menyimpan sekelompok kata-kata, sebuah sekelompok kata-kata dalam bahasa Inggris,
Saya secara teoritis bisa menempatkan pisang, apel, kiwi, mangga, pasangan,
dan melon semua hanya pada array.
Mereka semua bisa cocok dan akan menemukan.
Ini akan menjadi semacam rasa sakit untuk mencari melalui dan akses,
tapi cara yang lebih mudah untuk melakukan hal ini adalah bahwa kita dapat membuat benar-benar struktur
disebut tabel hash mana kita hash.
Kami menjalankan semua kunci kami melalui fungsi hash, persamaan,
yang mengubah mereka semua ke dalam semacam nilai
yang kemudian kita dapat menyimpan ke dasarnya array linked list.
>> Dan jadi di sini, jika kita ingin untuk menyimpan kata-kata bahasa Inggris,
kita bisa berpotensi hanya, saya tidak tahu, mengubah semua huruf pertama
menjadi semacam nomor.
Dan sebagainya, misalnya, jika saya ingin Sebuah identik dengan apple--
atau dengan indeks 0, dan B menjadi identik dengan 1,
kita dapat memiliki 26 entri yang hanya dapat menyimpan
semua surat dari alfabet yang kita akan mulai dengan.
Dan kemudian kita dapat memiliki apple di indeks 0.
Kita dapat memiliki pisang di indeks 1, blewah di indeks 2,
dan sebagainya dan sebagainya.
Dan dengan demikian jika saya ingin mencari meja dan akses hash saya apel,
Aku tahu apel dimulai dengan A, dan saya tahu persis
bahwa hal itu harus dan hash tabel pada indeks 0 karena
fungsi yang sebelumnya ditetapkan.
>> Jadi saya tidak tahu, kita program pengguna mana
Anda akan dikenakan biaya dengan arbitrarily-- tidak sewenang-wenang,
dengan mencoba untuk serius memikirkan persamaan baik
untuk dapat menyebar semua nilai Anda
dengan cara mereka dapat dengan mudah mengakses nanti dengan seperti persamaan
Anda, diri sendiri, tahu.
Jadi dalam arti jika saya ingin pergi ke mangga, aku tahu, oh, itu dimulai dengan m.
Itu harus di indeks 12.
Saya tidak perlu mencari melalui apa-apa.
Aku tahu exactly-- aku bisa pergi ke indeks 12 dan menarik yang keluar.
>> Semua orang yang jelas tentang bagaimana Fungsi hash tabel bekerja?
Ini semacam hanya array yang lebih kompleks.
Itu semua itu.
OKE.
>> Jadi saya kira kita mengalami masalah ini apa
yang terjadi jika Anda memiliki beberapa hal yang memberikan indeks yang sama?
Jadi mengatakan fungsi kita, semua itu lakukan adalah mengambil huruf pertama
dan mengubahnya menjadi masing 0 sampai 25 indeks.
Itu benar-benar baik-baik saja jika Anda hanya memiliki satu dari masing-masing.
Tapi yang kedua Anda mulai memiliki lebih, Anda
akan memiliki apa yang disebut tabrakan.
>> Jadi jika saya mencoba untuk memasukkan mengubur dalam hash tabel yang sudah memiliki pisang di atasnya,
apa yang akan terjadi ketika Anda mencoba untuk memasukkan itu?
Hal-hal buruk karena pisang sudah ada dalam indeks
bahwa Anda ingin menyimpannya dalam.
Berry jenis seperti, ah, apa yang harus saya lakukan?
Saya tidak tahu ke mana harus pergi.
Bagaimana cara mengatasi ini?
>> Dan kalian akan jenis melihat kita melakukan hal yang rumit ini
di mana kita bisa benar-benar jenis membuat daftar terkait dalam array kami.
Dan cara termudah untuk berpikir tentang hal ini,
semua tabel hash adalah array daftar terkait.
Dan, dalam arti bahwa, Anda memiliki array yang indah ini pointer,
dan kemudian setiap pointer di nilai itu, indeks itu,
benar-benar dapat menunjukkan hal-hal lain.
Dan sehingga Anda memiliki semua ini terpisah rantai datang dari satu array besar.
>> Dan jadi di sini, jika saya ingin memasukkan berry,
Aku tahu, OK, saya akan masukan melalui fungsi hash saya.
Aku akan berakhir dengan indeks 1, dan kemudian aku akan dapat memiliki
hanya subset kecil dari ini Raksasa kamus 140.000-kata.
Dan kemudian aku hanya dapat melihat melalui 1/26 itu.
>> Dan kemudian aku hanya bisa memasukkan berry baik sebelum atau setelah pisang
pada kasus ini?
Setelah, kan?
Dan sehingga Anda akan ingin menyisipkan node ini setelah pisang,
dan sehingga Anda akan memasukkan pada ekor yang linked list.
Aku akan kembali ke slide ini sebelumnya,
sehingga kalian bisa melihat bagaimana Fungsi hash bekerja.
>> Jadi fungsi hash adalah persamaan ini bahwa Anda menjalankan jenis masukan Anda
melalui untuk mendapatkan indeks apapun Anda ingin menetapkan arah.
Dan, dalam contoh ini, semua yang kita inginkan lakukan adalah mengambil huruf pertama,
mengubah itu menjadi sebuah indeks, maka kita dapat menyimpan bahwa dalam fungsi hash kami.
Semua yang kita lakukan di sini adalah kita mengkonversi huruf pertama.
Jadi keykey [0] hanya huruf pertama string apapun yang kita mengalami,
kita lewat di.
Kami mengubah bahwa untuk bagian atas, dan kita mengurangkan oleh huruf besar A,
sehingga semua yang melakukan memberikan kita nomor
di mana kita dapat hash nilai-nilai kita ke.
>> Dan kemudian kita akan kembali hash modulus UKURAN.
Sangat, sangat berhati-hati karena, secara teoritis, di sini
nilai hash Anda bisa tak terbatas.
Itu hanya bisa terus dan terus dan terus.
Bisa jadi beberapa benar-benar, benar-benar nilai besar,
tetapi karena tabel hash Anda yang Anda telah membuat hanya memiliki 26 indeks,
Anda ingin memastikan Anda modulusing sehingga Anda
tidak run-- itu sama hal sebagai queue-- Anda
sehingga Anda tidak menjalankan off bawah fungsi hash Anda.
>> Anda ingin membungkusnya kembali sekitar dengan cara yang sama di [tak terdengar] ketika
Anda memiliki seperti sangat, surat yang sangat besar, Anda
tidak ingin hal itu hanya lari akhir.
Hal yang sama di sini, Anda ingin memastikan itu tidak berjalan dari ujung dengan membungkus
sekitar untuk bagian atas meja.
Jadi ini hanya sangat Fungsi hash sederhana.
Semua yang dilakukannya adalah mengambil pertama surat apa pun masukan kami
dan mengubahnya menjadi sebuah indeks yang kita bisa dimasukkan ke dalam tabel hash kami.
>> Ya, dan seperti yang saya katakan sebelumnya, cara kita menyelesaikan tabrakan
di hash kami tabel mengalami, apa yang kita sebut, chaining.
Jadi jika Anda mencoba untuk memasukkan beberapa kata-kata yang dimulai dengan hal yang sama,
Anda akan memiliki satu nilai hash.
Alpukat dan apel, jika Anda sudah menjalankannya melalui fungsi hash kami,
akan memberi Anda nomor yang sama, jumlah 0.
Dan cara kita menyelesaikan yang bahwa kita benar-benar dapat jenis menghubungkan mereka
bersama-sama melalui daftar link.
>> Dan dalam hal ini, kalian dapat melihat jenis
bagaimana struktur data yang kami telah menetapkan sebelumnya
seperti kismis terkait daftar jenis dari dapat datang bersama-sama menjadi satu.
Dan kemudian Anda dapat membuat jauh struktur data yang lebih efisien
yang dapat menangani jumlah yang lebih besar dari data, yang secara dinamis mengubah ukuran tergantung
pada kebutuhan Anda.
Semua orang yang jelas?
Semua orang semacam jelas pada apa yang terjadi di sini?
>> Jika saya ingin insert-- apa yang buah yang dimulai dengan, saya tidak tahu,
B, selain berry, pisang.
>> AUDIENCE: Blackberry.
>> ANDI PENG: Blackberry, blackberry.
Dimana blackberry pergi di sini?
Nah, kita benar-benar belum diurutkan ini belum, tapi secara teoritis
jika kita ingin memiliki ini dalam urutan abjad,
mana harus pergi blackberry?
>> AUDIENCE: [tidak terdengar]
>> ANDI PENG: Tepat, setelah di sini, kan?
Tapi karena itu sangat sulit untuk reorder-- Saya kira itu terserah kalian.
Kalian bisa benar-benar melaksanakan apa pun yang Anda inginkan.
Cara yang lebih efisien untuk melakukan hal ini mungkin
akan memilah Anda terkait daftar ke urutan abjad,
dan jadi ketika Anda memasukkan hal-hal, Anda ingin
untuk memastikan untuk memasukkan mereka dalam urutan abjad
sehingga kemudian ketika Anda mencoba untuk mencari mereka,
Anda tidak harus melintasi segala sesuatu.
Anda tahu persis di mana itu, dan lebih mudah.
>> Tapi jika Anda memiliki jenis hal diselingi secara acak,
Anda masih akan memiliki untuk melintasi anyways.
Dan jadi jika saya ingin hanya masukkan blackberry sini
dan saya ingin mencari itu, aku tahu, oh, blackberry
harus dimulai dengan indeks 1, jadi saya tahu seketika hanya mencari pada 1.
Dan kemudian saya dapat jenis melintasi linked list
sampai saya mendapatkan blackberry, dan then-- ya?
>> AUDIENCE: Jika Anda mencoba untuk create-- Saya kira seperti ini adalah hash sangat sederhana
fungsi.
Dan jika kita ingin melakukan beberapa lapisan seperti itu,
OK, kita ingin memisahkan ke seperti semua huruf abjad
dan sekali lagi seperti set huruf abjad dalam itu,
kita menempatkan seperti hash tabel dalam tabel hash,
atau seperti fungsi dalam fungsi?
Atau itu--
>> ANDI PENG: Jadi hash Anda function-- tabel hash Anda
dapat sebagai besar seperti yang Anda inginkan.
Jadi dalam hal ini, saya pikir itu sangat mudah, sangat
sederhana bagi saya untuk hanya semacam berdasarkan pada huruf dari kata pertama.
Dan hanya ada 26 pilihan.
Aku hanya bisa mendapatkan 26 pilihan dari 0-25 karena mereka hanya bisa
mulai dari A sampai Z. Tapi Jika Anda ingin menambahkan, mungkin, lebih kompleksitas
atau lebih cepat menjalankan waktu untuk Anda tabel hash, Anda benar-benar
dapat melakukan segala macam hal.
Anda dapat membuat Anda sendiri persamaan yang memberikan
distribusi yang lebih dalam Anda kata-kata, maka ketika Anda mencari,
itu akan menjadi lebih cepat.
>> Ini benar-benar sampai kalian bagaimana Anda ingin menerapkan itu.
Anggap saja sebagai hanya ember.
Jika saya ingin memiliki 26 ember, aku akan
untuk menyelesaikan dalam ember.
Tapi aku akan memiliki a bunch barang di setiap kotak,
jadi jika Anda ingin membuatnya lebih cepat dan lebih efisien,
biarkan aku memiliki seratus ember.
>> Tapi kemudian Anda harus mencari tahu cara untuk menyelesaikan masalah sehingga mereka
di ember yang tepat mereka harus di.
Tapi kemudian ketika Anda benar-benar ingin melihat ember itu,
itu jauh lebih cepat karena ada hal yang kurang di setiap kotak.
Dan, ya, itu benar-benar trik untuk kalian di pset5
adalah bahwa Anda akan ditantang untuk hanya membuat
apa yang paling efisien Fungsi Anda bisa memikirkan untuk menjadi
mampu menyimpan dan memeriksa nilai-nilai ini.
>> Benar-benar sampai kalian namun Anda ingin melakukannya,
tapi itu titik benar-benar baik.
Bahwa jenis logika Anda ingin mulai berpikir tentang
adalah, baik, kenapa tidak saya membuat lebih banyak ember.
Dan kemudian saya harus mencari hal yang kurang, dan kemudian mungkin aku
memiliki fungsi hash yang berbeda.
>> Ya, ada banyak cara untuk melakukan hal ini pset, beberapa lebih cepat dari yang lain.
Aku benar-benar akan hanya melihat bagaimana cepat adalah yang tercepat kalian akan
bisa mendapatkan fungsi Anda untuk bekerja.
OK, semua orang di baik chaining dan hash tabel?
Ini benar-benar seperti sangat sederhana Konsep jika Anda berpikir tentang hal itu.
Semua itu adalah memisahkan apa pun input Anda ke dalam ember,
menyortir mereka, dan kemudian mencari daftar yang ada yang terkait dengan.
>> Keren.
Baiklah, sekarang kita memiliki semacam berbeda struktur data yang disebut pohon.
Mari kita pergi dan berbicara tentang mencoba yang jelas berbeda,
tetapi dalam kategori yang sama.
Pada dasarnya, semua pohon adalah bukan pengorganisasian data dalam cara yang linear
bahwa tabel hash does-- Anda tahu, itu punya atas dan bawah sebuah
dan kemudian Anda jenis menghubungkan off dari itu-- sebuah pohon memiliki atas yang Anda sebut akar,
dan kemudian memiliki daun di sekitar itu.
>> Dan sehingga semua yang Anda miliki di sini hanya node atas
yang menunjuk ke node lain, yang poin untuk lebih node, dan seterusnya dan sebagainya.
Dan sehingga Anda hanya memiliki cabang membelah.
Ini hanya cara yang berbeda pengorganisasian data, dan karena kita menyebutnya pohon,
kalian hanya-- itu hanya dimodelkan untuk terlihat seperti pohon.
Itulah mengapa kami menyebutnya pohon.
>> Tabel hash terlihat seperti meja.
Sebuah pohon hanya tampak seperti pohon.
Semua itu adalah adalah terpisah cara mengatur node
tergantung pada apa kebutuhan Anda.
>> Jadi Anda memiliki akar dan maka Anda memiliki daun.
Cara yang kita bisa sangat berpikir tentang hal ini adalah pohon biner,
pohon biner hanya jenis tertentu pohon
di mana setiap node hanya poin untuk, di max, dua node lainnya.
Dan jadi di sini Anda memiliki yang berbeda simetri di pohon Anda
yang membuatnya lebih mudah untuk jenis terlihat apa nilai Anda karena Anda
selalu kiri atau kanan.
Tidak pernah seperti sepertiga dari kiri kiri atau keempat dari kiri.
Itu hanya Anda memiliki kiri dan kanan sebuah dan Anda dapat mencari salah satu dari dua.
Dan jadi mengapa ini berguna?
Cara bahwa ini adalah berguna adalah jika Anda sedang mencari
untuk mencari melalui nilai-nilai, kan?
Daripada menerapkan biner cari di array kesalahan,
jika Anda ingin dapat memasukkan node dan mengambil node di akan dan juga
melestarikan pencarian kapasitas pencarian biner.
Jadi dengan cara ini, kami jenis tricking-- ingat ketika kita
mengatakan daftar terkait tidak bisa pencarian biner?
Kami semacam menciptakan struktur data yang trik yang dalam bekerja.
>> Dan daftar jadi karena terkait yang linear, mereka hanya menghubungkan satu demi satu.
Kita dapat memiliki jenis jenis yang berbeda dari pointer
saat itu untuk node yang berbeda yang dapat membantu kami dengan pencarian.
Dan jadi di sini, jika saya ingin memiliki pohon pencarian biner,
Saya tahu bahwa saya tengah jika 55.
Aku hanya akan membuat yang sebagai tengah saya, sebagai root saya,
dan kemudian aku akan memiliki nilai-nilai spin off itu.
>> Jadi di sini, jika aku akan mencari nilai 66, saya bisa mulai 55.
Ini 66 besar dari 55?
Ya itu, jadi aku tahu aku mus mencari i n pointer kanan pohon ini.
Aku pergi ke 77.
OK, adalah kurang dari 66 atau lebih besar dari 77?
Ini kurang dari, sehingga Anda tahu, oh, yang harus menjadi simpul kiri.
>> Dan jadi di sini kita jenis melestarikan semua hal-hal besar tentang array,
jadi seperti Resize dinamis benda, menjadi
mampu menyisipkan dan menghapus di akan, tanpa harus khawatir tentang tetap
jumlah ruang.
Kami masih melestarikan semua hal-hal yang indah
sementara juga mampu melestarikan log dan waktu pencarian biner mencari
bahwa kami hanya sebelumnya bisa mendapatkan frase.
>> Struktur data yang dingin, jenis kompleks untuk melaksanakan, node.
Seperti yang Anda lihat, semua itu adalah struct node
adalah bahwa Anda memiliki kiri dan pointer tepat.
Itu semua itu.
Jadi bukan hanya memiliki x atau sebelumnya.
Anda memiliki kiri atau kanan, dan kemudian Anda dapat jenis menghubungkan mereka bersama-sama
Namun Anda memilih demikian.
>> OK, kita benar-benar akan hanya mengambil beberapa menit.
Jadi kita akan pergi ke sini.
Seperti yang saya katakan sebelumnya, Aku agak menjelaskan
logika di balik bagaimana kita akan mencari melalui ini.
Kami akan mencoba pseudocoding keluar ini untuk melihat
jika kita bisa jenis menerapkan Logika yang sama dari pencarian biner
untuk berbagai jenis struktur data.
Jika kalian ingin mengambil seperti pasangan menit untuk hanya berpikir tentang hal ini.
OKE.
Baiklah, aku akan sebenarnya hanya memberikan the-- tidak,
kita akan berbicara tentang pseudocode pertama.
Jadi tidak ada yang ingin untuk memberikan menusuk apa
hal pertama yang Anda ingin lakukan ketika Anda memulai pencarian adalah?
Jika kita sedang mencari nilai 66, apa
hal pertama yang kita ingin lakukan jika kami ingin mencari biner pohon ini?
>> AUDIENCE: Anda ingin terlihat benar dan melihat kiri dan melihat [tidak terdengar]
jumlah yang lebih besar.
>> ANDI PENG: Ya, persis.
Jadi Anda akan melihat akar Anda.
Ada banyak cara Anda dapat menghubungi itu, orang tua simpul Anda katakan.
Saya ingin mengatakan akar karena itu seperti akar pohon.
Anda akan melihat simpul akar Anda, dan Anda
akan melihat adalah 66 besar dari atau kurang dari 55.
Dan jika itu lebih besar dari, baik, itu adalah lebih besar dari, di mana kita ingin melihat?
Di mana kita ingin mencari sekarang, kan?
Kami ingin mencari bagian kanan pohon ini.
>> Jadi kita miliki, nyaman, sebuah pointer yang menunjuk ke kanan.
Dan kemudian kita dapat mengatur akar baru kami untuk menjadi 77.
Kami hanya bisa pergi ke mana pun pointer menunjuk.
Nah, oh, di sini kita mulai pada 77, dan kami hanya bisa
melakukan ini secara rekursif lagi dan lagi.
Dengan cara ini, Anda jenis dari memiliki fungsi.
Anda memiliki cara untuk mencari yang Anda hanya dapat mengulangi berulang-ulang,
tergantung di mana Anda ingin melihat sampai Anda akhirnya mendapatkan nilai
yang Anda cari.
Masuk akal?
>> Saya akan menunjukkan Anda sebenarnya kode, dan itu banyak kode.
Tidak perlu panik.
Kita akan berbicara melalui itu.
>> Sebenarnya tidak.
Itu hanya pseudocode.
OK, itu hanya pseudocode, yang sedikit rumit,
tapi itu benar-benar baik-baik saja.
Semua orang berikut bersama di sini?
Jika akar adalah nol, pulang palsu karena itu berarti
Anda bahkan tidak punya apa-apa di sana.
>> Jika akar n adalah nilai, sehingga jika terjadi menjadi salah satu yang sedang melihat,
maka Anda akan kembali benar karena Anda tahu Anda menemukannya.
Tetapi jika nilai kurang dari akar n, kau
akan mencari kiri anak atau daun kiri,
apa pun yang Anda ingin menyebutnya.
Dan jika nilai lebih besar dari akar, Anda akan mencari pohon yang tepat,
kemudian hanya menjalankan fungsi melalui pencarian lagi.
>> Dan jika akar adalah nol, bahwa berarti Anda telah mencapai akhir?
Itu berarti Anda tidak memiliki lebih daun lebih untuk mencari,
maka Anda tahu, oh, saya rasa itu bukan di sini
karena setelah saya telah melihat melalui seluruh hal dan itu tidak ada di sini,
itu hanya mungkin tidak berada di sini.
>> Apakah itu masuk akal untuk semua orang?
Jadi seperti pencarian biner melestarikan kemampuan daftar terkait.
Keren, dan jenis kedua dari struktur data kalian
dapat mencoba menerapkan pada pset Anda, Anda hanya harus memilih satu metode.
Tapi mungkin metode alternatif untuk tabel hash adalah apa yang kita sebut trie.
>> Semua trie adalah adalah jenis tertentu pohon yang
memiliki nilai-nilai yang pergi ke nilai-nilai lain.
Jadi alih-alih memiliki biner pohon dalam arti bahwa hanya satu
Hal dapat menunjukkan dua, Anda dapat memiliki satu hal titik ke banyak, banyak hal.
Anda pada dasarnya memiliki array dalam yang Anda simpan
pointer yang menunjuk ke array lain.
>> Jadi simpul dari bagaimana kita akan menentukan trie
adalah kita ingin memiliki Boolean, c kata, kan?
Jadi node adalah Boolean seperti benar atau salah,
pertama-tama di kepala array, apakah ini sebuah kata?
Kedua, Anda ingin memiliki pointer apa pun sisa dari mereka adalah.
Sebuah sedikit rumit, sedikit abstrak, tapi Saya akan menjelaskan apa yang segala cara.
>> Jadi di sini, di bagian atas, jika Anda memiliki sebuah array menyatakan sudah,
node di mana Anda memiliki sebuah Boolean nilai yang disimpan di depan
yang memberitahu Anda apakah ini sebuah kata?
Apakah ini bukan sebuah kata?
Dan kemudian Anda memiliki sisa array yang
sebenarnya menyimpan semua kemungkinan apa itu bisa.
Jadi, misalnya, seperti di atas Anda memiliki
hal pertama yang mengatakan benar atau palsu, ya atau tidak, ini adalah sebuah kata.
>> Dan kemudian Anda memiliki 0 sampai 26 dari huruf yang dapat Anda simpan.
Jika saya ingin mencari disini untuk kelelawar, aku pergi ke atas
dan saya mencari B. Saya menemukan B di saya array, dan jadi saya tahu, OK, adalah B kata?
B adalah bukan kata, sehingga dengan demikian Aku harus terus mencari.
Aku pergi dari B, dan saya melihat ke pointer yang menunjuk ke arah B
dan saya melihat array lain informasi, struktur yang sama yang kita miliki sebelumnya.
>> Dan di sini-oh, berikutnya surat di [tidak terdengar] adalah A.
Jadi kita melihat dalam array itu.
Kami menemukan nilai delapan, dan kemudian kita melihat untuk melihat, oh,
hey, adalah bahwa kata, adalah B-A kata?
Ini bukan sebuah kata.
Kita harus terus mencari.
>> Dan kemudian kita melihat ke mana pointer A poin,
dan itu menunjukkan cara lain di yang kita memiliki nilai lebih yang disimpan.
Dan akhirnya, kita bisa B-A-T, yang merupakan sebuah kata.
Dan sehingga waktu berikutnya Anda melihat, Anda akan
untuk memiliki cek, ya, Fungsi Boolean ini benar.
Dan dalam arti kami jenis memiliki pohon dengan array.
>> Jadi Anda dapat mencari jenis turun.
Daripada hashing fungsi dan menugaskan nilai dengan linked list,
Anda hanya dapat menerapkan trie yang mencari downwords.
Benar-benar, benar-benar rumit hal.
Tidak mudah untuk berpikir tentang karena aku seperti meludah begitu banyak struktur data keluar
pada Anda, tetapi tidak semua orang jenis memahami bagaimana logika ini bekerja?
>> OK keren.
Jadi B-A-T, dan kemudian Anda akan mencari.
Lain kali Anda akan untuk melihat, oh, hei, itu benar,
sehingga aku tahu ini harus menjadi sebuah kata.
>> Hal yang sama untuk kebun binatang.
Jadi, inilah hal yang sekarang, jika kita ingin mencari kebun binatang, sekarang,
Saat ini kebun binatang bukanlah kata dalam kamus kami
karena, seperti kalian lihat, Tempat pertama yang harus kita Boolean sebuah
kembali benar adalah pada akhir zoom.
Kami memiliki Z-O-O-M.
>> Dan jadi di sini, kita tidak benar-benar memiliki kata, kebun binatang, dalam kamus kami
karena kotak ini tidak dicentang.
Jadi komputer tidak tahu bahwa kebun binatang adalah sebuah kata
karena cara bahwa kita sudah disimpan itu, hanya zoom sini
sebenarnya memiliki nilai Boolean yang telah berubah benar.
Jadi jika kita ingin memasukkan kata, kebun binatang, dalam kamus kami,
bagaimana kita akan pergi untuk melakukan itu?
Apa yang harus kita lakukan untuk memastikan kami komputer tahu bahwa Z-O-O adalah sebuah kata
dan bukan kata pertama adalah Z-O-O-M?
>> AUDIENCE: [tidak terdengar]
>> ANDI PENG: Tepat, kita ingin memastikan bahwa ini
di sini, bahwa nilai Boolean adalah diperiksa bahwa hal itu benar.
Z-O-O, maka kita akan memeriksa bahwa, sehingga kita tahu persis, hei, kebun binatang adalah sebuah kata.
Aku akan memberitahu komputer bahwa itu sebuah kata sehingga
bahwa ketika cek komputer, ia tahu bahwa kebun binatang adalah sebuah kata.
>> Karena mengingat semua data ini struktur, itu sangat mudah bagi kita
mengatakan, oh, kelelawar sebuah kata.
Zoo sebuah kata.
Zoom sebuah kata.
Tetapi ketika Anda sedang membangun itu, komputer tidak tahu.
>> Jadi, Anda harus memberitahu persis pada titik ini adalah sebuah kata?
Pada titik itu bukan kata?
Dan pada titik apa yang saya perlu hal-hal mencari,
dan pada titik yang harus saya pergi berikutnya?
Semua orang jelas itu?
Keren.
>> Dan kemudian datang masalah bagaimana akan kita
pergi tentang memasukkan sesuatu bahwa sebenarnya tidak ada?
Jadi mari kita hanya mengatakan kita ingin menyisipkan kata, mandi, ke trie kami.
Seperti kalian bisa melihat seperti saat ini semua yang kita miliki sekarang adalah B-A-T,
dan struktur ini data baru ada memiliki setengah liter yang
menunjuk nol karena kita berasumsi bahwa, oh, tidak ada kata-kata setelah B-A-T,
mengapa kita perlu menjaga memiliki hal-hal setelah T. yang
>> Tapi masalahnya muncul jika kita melakukan Anda ingin memiliki sebuah kata yang datang setelah
T ini.
Jika Anda memiliki mandi, Anda akan ingin H tepat.
Dan cara kita akan melakukan itu adalah kita akan membuat simpul terpisah.
Kami tidak membagikan jumlah berapapun memori untuk array baru ini,
dan kita akan menetapkan kembali pointer.
>> Kita akan menetapkan H, Pertama-tama, null ini,
kita akan menyingkirkan.
Kita akan memiliki ke bawah titik H.
Jika kita melihat H, kami ingin untuk pergi ke tempat lain.
>> Di sini, kita kemudian dapat memeriksa off ya.
Jika kita memukul H setelah T, oh, maka kita tahu bahwa ini adalah sebuah kata.
Boolean akan kembali benar.
Semua orang yang jelas tentang bagaimana yang terjadi?
OKE.
>> Jadi pada dasarnya, semua struktur data ini
bahwa kita sudah lebih hari ini, saya sudah pergi atas mereka benar-benar, benar-benar cepat
dan tidak banyak detail, dan itu OK.
Setelah Anda mulai bermain-main dengan itu, Anda akan
melacak di mana semua pointer,
apa yang terjadi di Anda struktur data, dan lain-lain.
Mereka akan sangat berguna, dan terserah kepada Anda
orang untuk benar-benar mengetahui bagaimana Anda ingin menerapkan hal.
>> Dan pset4, dari 5-- oh, itu salah.
Pset5 adalah salah eja.
Seperti yang saya katakan sebelumnya, Anda akan, sekali lagi, men-download kode sumber dari kami.
Ada akan menjadi tiga utama hal yang Anda akan men-download.
Anda akan men-download kamus, kers, dan teks.
>> Semua hal-hal yang berada baik kamus kata-kata
bahwa kami ingin Anda untuk memeriksa atau tes informasi
bahwa kami ingin Anda untuk mengeja cek.
Dan kamus kami memberikan Anda akan
untuk memberikan kata-kata yang sebenarnya yang kita inginkan Anda untuk menyimpan entah dengan cara yang
lebih efisien daripada sebuah array.
Dan kemudian teks yang akan menjadi apa yang kita
meminta Anda untuk memeriksa ejaan untuk memastikan semua kata-kata ada kata-kata yang nyata.
>> Dan tiga blok dari program yang akan kami berikan
disebut dictionary.c, dictionary.h, dan speller.c.
Dan sehingga semua dictionary.c dilakukan adalah apa yang Anda diminta untuk menerapkan.
Ini beban kata-kata.
Ini mantra cek mereka, dan itu membuat yakin bahwa segala sesuatu dimasukkan dengan benar.
>> diction.h hanyalah sebuah file library yang menyatakan semua fungsi tersebut.
Dan speller.c, kami akan memberikan Anda.
Anda tidak perlu memodifikasi itu.
Semua speller.c dilakukan adalah mengambil, beban itu, memeriksa kecepatan itu,
tes benchmark seperti bagaimana cepat Anda dapat melakukan hal-hal.
>> Ini ejaan a.
Hanya jangan main-main dengan hal itu, tapi membuat Pastikan Anda memahami apa yang dilakukannya.
Kami menggunakan fungsi yang disebut getrusage yang menguji kinerja mantra Anda
pemeriksa.
Semua hal ini pada dasarnya menguji saat segala sesuatu dalam kamus Anda,
jadi pastikan Anda memahami itu.
Hati-hati untuk tidak main-main dengan hal itu atau hal lain tidak akan berjalan dengan baik.
>> Dan sebagian besar tantangan ini adalah untuk kalian benar-benar memodifikasi dictionary.c.
Kami akan memberikan 140.000 kata dalam kamus.
Kami akan memberikan teks file yang memiliki kata-kata,
dan kami ingin Anda dapat mengatur mereka ke dalam tabel hash atau trie
karena ketika kami meminta Anda untuk mengeja check-- bayangkan jika Anda mantra
memeriksa seperti Odyssey Homer.
Ini seperti besar, tes besar ini.
>> Bayangkan jika setiap satu kata yang Anda harus melihat
melalui array 140.000 nilai.
Yang akan mengambil selamanya untuk mesin Anda untuk menjalankan.
Itulah sebabnya kami ingin mengatur kami data ke dalam struktur data yang lebih efisien
seperti tabel hash atau trie.
Dan kemudian kalian bisa jenis ketika Anda mencari akses
hal yang lebih mudah dan lebih cepat.
>> Dan jadi hati-hati untuk menyelesaikan tabrakan.
Anda akan mendapatkan bunch dari kata-kata yang mulai dengan A.
Anda akan mendapatkan kata-kata sekelompok yang dimulai dengan B. Sampai Anda
orang bagaimana Anda ingin mengatasinya.
Mungkin masih ada lagi fungsi hash efisien
dari sekedar huruf pertama dari sesuatu, dan itu terserah Anda
orang untuk jenis melakukan apapun yang Anda inginkan.
>> Mungkin Anda ingin menambahkan semua huruf bersama-sama.
Mungkin Anda ingin seperti melakukan hal-hal aneh untuk memperhitungkan jumlah huruf,
apapun.
Sampai kalian bagaimana Anda ingin melakukannya.
Jika Anda ingin melakukan tabel hash, jika Anda ingin mencoba trie, benar-benar terserah pada Anda.
Saya akan memperingatkan Anda di depan waktu itu trie biasanya sedikit lebih sulit
hanya karena ada banyak lebih pointer untuk melacak.
Tapi benar-benar sampai kalian.
Ini jauh lebih efisien dalam kebanyakan kasus.
Anda ingin benar-benar dapat menjaga melacak semua pointer Anda.
Seperti melakukan hal yang sama bahwa saya lakukan di sini.
Ketika Anda mencoba untuk memasukkan nilai ke dalam tabel hash atau menghapus,
pastikan bahwa Anda benar-benar melacak
dari mana segala sesuatu karena itu benar-benar mudah untuk jika saya
mencoba untuk menyisipkan seperti kata, andy.
Mari kita hanya mengatakan bahwa adalah kata nyata, kata, andy,
dalam daftar raksasa A kata.
>> Jika saya hanya kebetulan menetapkan kembali yang salah pointer, oops,
ada pergi keseluruhan sisa linked list saya.
Sekarang satu-satunya kata yang saya miliki adalah andy, dan sekarang
semua kata lain dalam kamus telah hilang.
Dan sehingga Anda ingin memastikan Anda melacak semua pointer Anda
atau Anda akan mendapatkan masalah besar dalam kode Anda.
Menarik hal-hal dengan hati-hati langkah demi langkah.
Itu membuat lebih mudah untuk memikirkan.
>> Dan terakhir, Anda ingin dapat menguji kinerja Anda program Anda
di papan besar.
Jika kalian mengambil melihat CS50 sekarang,
kita memiliki apa yang disebut papan besar.
Ini adalah lembar skor tercepat mantra kali memeriksa di semua CS50
sekarang, saya pikir atas seperti 10 kali saya pikir delapan dari mereka adalah staf.
Kami benar-benar ingin kalian untuk mengalahkan kami.
>> Semua dari kita mencoba untuk menerapkan kode tercepat mungkin.
Kami ingin kalian mencoba untuk menantang kita dan menerapkan lebih cepat dari kita semua
bisa.
Dan ini benar-benar pertama kalinya bahwa kita
meminta kalian untuk melakukan pset yang Anda benar-benar bisa melakukan apa pun metode yang di
kamu ingin.
>> Saya selalu mengatakan, ini lebih mirip untuk solusi kehidupan nyata, kan?
Saya katakan, hei, saya perlu Anda lakukan ini.
Membangun program yang melakukan ini untuk saya.
Lakukan namun Anda inginkan.
Saya hanya tahu bahwa saya ingin cepat.
Itu tantangan Anda untuk minggu ini.
Kalian, kita akan untuk memberikan tugas.
Kami akan memberikan tantangan.
Dan kemudian terserah kalian untuk benar-benar hanya mencari tahu
apa cara tercepat dan paling cara yang efisien untuk melaksanakan hal ini.
Ya?
>> AUDIENCE: Apakah kita diperbolehkan untuk jika diinginkannya untuk penelitian cara cepat
untuk melakukan tabel hash online, yang bisa kita lakukan itu dan mengutip kode orang lain?
ANDI PENG: Ya, benar-benar baik-baik saja.
Jadi jika kalian membaca spec, ada garis
di spec yang mengatakan kalian benar-benar bebas untuk penelitian hash
fungsi pada apa adalah beberapa fungsi hash lebih cepat
untuk menjalankan hal-hal melalui sebagai Selama Anda mengutip kode tersebut.
Jadi beberapa orang sudah tahu cara cepat
melakukan spell checker, cepat cara menyimpan informasi.
Benar-benar sampai kalian jika Anda ingin hanya mengambil itu, kan?
Pastikan Anda mengutip.
Tantangan di sini benar-benar bahwa kita mencoba untuk menguji
adalah memastikan bahwa Anda tahu jalan sekitar pointer.
Sejauh yang Anda menerapkan fungsi hash yang sebenarnya
dan datang dengan seperti matematika untuk melakukan itu,
kalian dapat penelitian apa pun metode online kalian inginkan.
Ya?
>> AUDIENCE: Bisakah kita mengutip hanya dengan menggunakan [tidak terdengar]?
>> ANDI PENG: Ya.
Anda hanya bisa, dalam komentar Anda, Anda dapat mengutip seperti, oh,
diambil dari Yada, Yada, Yada, fungsi hash.
Ada yang punya pertanyaan?
Kami benar-benar melenggang melalui bagian hari ini.
Aku akan sampai di sini untuk menjawab pertanyaan-pertanyaan juga.
>> Juga, seperti yang saya katakan, kantor jam malam ini dan besok.
Spec minggu ini sebenarnya super mudah dan super pendek untuk membaca.
Saya akan menyarankan mengambil melihat, hanya membaca keseluruhan itu.
>> Dan Zamyla sebenarnya menuntun Anda melalui masing-masing fungsi
Anda perlu untuk mengimplementasikan, dan jadi sangat, sangat jelas bagaimana melakukan segala sesuatu.
Hanya untuk memastikan Anda melacak pointer.
Ini adalah pset sangat menantang.
>> Ini tidak menantang karena seperti, oh, konsep-konsep yang jauh lebih
sulit, atau Anda harus belajar begitu banyak sintaks baru jalan
yang Anda lakukan untuk pset terakhir.
Pset ini sulit karena ada begitu banyak pointer,
dan kemudian itu sangat, sangat mudah sekali Anda memiliki bug dalam kode Anda tidak dapat
untuk menemukan di mana bug yang.
>> Dan begitu lengkap dan iman di dalam kamu mengucapkan orang untuk dapat mengalahkan kami [tidak terdengar]
ejaan.
Aku benar-benar tidak punya tambang ditulis , tapi aku akan menulis saya.
Jadi saat Anda sedang menulis Anda, saya akan menulis saya.
Aku akan mencoba untuk membuat saya lebih cepat dari Anda.
Kami akan melihat siapa yang memiliki salah satu yang paling cepat.
>> Dan ya, aku akan melihat semua kalian di Jakarta, Selasa.
Saya akan menjalankan semacam seperti lokakarya pset.
Semua bagian ini minggu lokakarya pset,
sehingga kalian punya banyak kesempatan bantuan, jam kantor seperti biasa,
dan saya benar-benar melihat ke depan untuk membaca semua kode-orang Anda '.
Saya memiliki kuis di sini jika Anda orang ingin datang mendapatkan mereka.
Itu saja.