>> [Bermain muzik]
>> ANDI PENG: Selamat datang ke minggu 6 seksyen.
Kami menyimpang dari standard kami seksyen masa Selasa
petang ke pagi Ahad ini indah.
Terima kasih untuk semua orang yang menyertai saya hari ini, tetapi serius,
satu pusingan tepukan.
>> Itu satu usaha yang cukup besar.
Saya hampir tidak juga membuat ia dalam masa, tetapi Ia adalah OK.
Jadi saya tahu bahawa anda semua baru sahaja berjaya ke kuiz.
Pertama sekali, selamat datang untuk sebelah flip itu.
>> Kedua, kami akan bercakap mengenainya.
Kami akan bercakap mengenai kuiz.
Kami akan bercakap tentang bagaimana yang anda lakukan di dalam kelas.
Anda akan selamat.
Saya mempunyai kuiz anda untuk anda pada akhir dari sini,
jadi jika anda semua ingin mengambil yang melihat ia, betul-betul halus.
>> Begitu cepat sebelum kita bermula, agenda untuk hari ini adalah seperti berikut.
Seperti yang anda lihat, kami tembakan pada dasarnya pesat
melalui sejumlah besar struktur data benar-benar, benar-benar, benar-benar cepat.
Maka oleh itu, ia tidak akan menjadi hari ini super interaktif.
Ia hanya akan menjadi saya agak menjerit perkara yang anda, dan jika saya mengelirukan anda,
jika saya akan terlalu cepat, maklumkan kepada saya.
Mereka hanya pelbagai data struktur, dan sebagai sebahagian
daripada pset anda untuk ini minggu yang akan datang, anda akan
diminta untuk melaksanakan salah satu daripada mereka, mungkin dua daripada mereka, kelak dua daripada mereka
dalam Serangga anda.
OK, jadi saya hanya akan bermula dengan beberapa pengumuman.
Kami akan pergi ke susunan dan beratur lebih dalam mendalam daripada apa yang kita lakukan sebelum ini kuiz.
Kami akan pergi dikaitkan senarai lagi, sekali lagi,
lebih mendalam daripada apa yang kita ada sebelum kuiz.
Dan kemudian kita akan bercakap tentang hash meja, pokok-pokok dan percubaan, yang
semua cukup diperlukan untuk pset anda.
Dan kemudian kita akan pergi ke beberapa tips berguna untuk pset5.
>> OK, jadi kuiz 0.
Purata adalah 58%.
Ia adalah sangat rendah, dan supaya kalian semua dengan sangat, sangat baik mengikut
dengan itu.
>> Cukup banyak, Peraturan praktikal adalah jika anda dalam sisihan piawai min
terutamanya kerana kita berada dalam yang kurang seksyen yang selesa, anda benar-benar baik.
Anda berada di landasan yang betul.
Hidup ini indah.
>> Saya tahu ia adalah menakutkan untuk berfikir bahawa Saya mendapat seperti 40% untuk kuiz ini.
Saya akan gagal kelas ini.
Saya berjanji kepada anda, anda tidak akan gagal kelas.
Anda benar-benar baik.
>> Bagi anda yang mendapat lebih min, mengagumkan, menarik,
seperti, serius dilakukan dengan baik.
Saya mempunyai mereka dengan saya.
Jangan ragu untuk datang mendapatkan mereka pada akhir bahagian.
Hubungi saya jika anda mempunyai sebarang isu, soalan dengan mereka.
Jika kita menambah skor anda salah, sila beritahu kami.
>> OK, jadi pset5, ini adalah benar-benar minggu pelik untuk Yale dalam erti kata
yang pset kami adalah kerana Rabu pada tengah hari termasuk
hari lewat, jadi ia sebenarnya secara teori kerana Selasa di tengah hari.
Mungkin tidak ada yang selesai pada Selasa di tengah hari.
Itu betul-betul halus.
Kita akan mempunyai waktu pejabat malam ini dan juga malam Isnin.
Dan kesemua seksyen minggu ini akan sebenarnya dijadikan bengkel,
jadi berasa bebas untuk pop dalam mana-mana bahagian yang anda mahu,
dan mereka akan menjadi jenis mini Serangga bengkel untuk membantu pada itu.
Maka oleh itu, ini adalah bahagian sahaja di mana kita bahan mengajar.
Semua bahagian-bahagian lain akan memberi tumpuan semata-mata pada bantuan untuk pset.
Ya?
>> PENONTON: Di manakah waktu pejabat?
>> ANDI PENG: Waktu pejabat tonight-- oh, soalan yang baik.
Saya rasa waktu pejabat malam ini berada di dalam atau di Teal Commons.
Jika anda mendaftar dalam talian CS50 dan anda pergi ke waktu pejabat,
perlu ada jadual yang memberitahu anda di mana kesemua mereka berada.
>> Saya tahu sama ada malam ini atau esok adalah Teal,
dan saya rasa kami mungkin mempunyai orang biasa untuk malam yang lain.
Saya tidak pasti.
Soalan yang baik.
Semak pada CS50.
>> Cool, sebarang pertanyaan mengenai jadual untuk seterusnya seperti tiga hari?
Saya berjanji kepada anda lelaki seperti David berkata, ini adalah bahagian atas bukit.
Anda lelaki yang hampir di sana.
Hanya tiga hari lagi.
Sampai ke sana, dan kemudian kami semua akan turun.
Kami akan perlu bagus rehat CS-percuma.
Kita akan kembali.
Kami akan menyelam ke dalam web pengaturcaraan dan pembangunan,
perkara-perkara yang sangat menyeronokkan berbanding kepada beberapa psets lain.
Dan ia akan menjadi sejuk, dan kita akan mempunyai banyak bersenang-senang.
Kami akan mempunyai lebih banyak gula-gula.
Maaf untuk gula-gula.
Saya terlupa gula-gula.
Ia adalah pagi yang kasar.
Jadi anda semua hampir di sana, dan saya amat bangga dengan anda semua.
>> OK, jadi susunan.
Yang suka soalan mengenai Jack dan pakaian beliau mengenai kuiz?
Tiada sesiapa?
OK, itulah denda.
>> Jadi pada asasnya yang anda boleh gambar Jack, Lelaki ini di sini,
suka mengambil pakaian daripada bahagian atas timbunan,
dan dia meletakkan ia kembali ke tindanan selepas dia lakukan.
Jadi dengan cara ini, dia tidak pernah nampaknya semakin
ke bahagian bawah stack dalam pakaiannya.
Jadi ini jenis menerangkan struktur data asas
bagaimana timbunan dilaksanakan.
>> Pada asasnya, memikirkan stack sebagai apa-apa timbunan objek
di mana anda meletakkan sesuatu ke atas, dan maka anda pop mereka keluar dari atas.
Jadi LIFO adalah singkatan yang kita suka untuk use-- Terakhir Dalam, Pertama Out.
Dan sebagainya bertahan dalam ke bahagian atas timbunan adalah yang pertama yang keluar.
Dan supaya kedua-dua istilah kita suka bergaul
dengan yang dipanggil tolak dan pop.
Apabila anda menolak sesuatu ke atas timbunan, dan anda pop kembali.
>> Oleh itu, saya rasa ini adalah jenis yang konsep abstrak bagi anda
yang mahu melihat seperti pelaksanaan sebenar ini
dalam dunia sebenar.
Berapa ramai daripada anda telah menulis esei mungkin seperti satu jam sebelum ia disebabkan,
dan anda secara tidak sengaja dipadam besar sebahagian daripadanya, seperti tidak sengaja?
Dan kemudian apa kawalan melakukan kita gunakan untuk meletakkannya kembali?
Kawalan-Z, ya?
Kawalan-Z, jadi jumlah kali bahawa kawalan-Z telah menyelamatkan hidup saya,
telah menyelamatkan pantat saya, setiap kali yang yang dilaksanakan melalui timbunan.
>> Pada dasarnya semua maklumat yang yang pada dokumen Word anda,
ia akan ditolak dan muncul sesuka hati.
Dan sebagainya pada dasarnya setiap kali anda memadam apa-apa, anda pop kembali.
Dan kemudian jika anda memerlukannya semula, anda menolak, yang adalah apa Control-C tidak.
Dan fungsi dunia begitu nyata struktur data bagaimana mudah
boleh membantu dengan kehidupan seharian anda.
>> Jadi struct adalah cara yang kita benar-benar mewujudkan timbunan.
Kita menaip menentukan struct, dan kemudian kita panggil ia stack di bahagian bawah.
Dan dalam timbunan, kita mempunyai dua parameter
yang kita dasarnya boleh memanipulasi, jadi kita perlu char kapasiti tali bintang.
>> Apa yang ia lakukan mencipta array
yang kita boleh menyimpan apa sahaja yang anda mahu mana kita boleh menentukan kapasitinya.
Kapasiti Adakah hanya jumlah yang maksimum barangan yang kita boleh dimasukkan ke dalam pelbagai ini.
saiz int adalah kaunter yang menyimpan menjejaki berapa banyak perkara pada masa ini
dalam timbunan.
Sebab itu kita boleh menjejaki, A, kedua-dua berapa besar timbunan sebenar adalah,
dan, B, berapa banyak timbunan yang kami mengisinya kerana kita tidak mahu
melimpah ke atas apa kapasiti kita.
>> Jadi, sebagai contoh, ini indah soalan adalah pada kuiz anda.
Pada dasarnya bagaimana kita menolak ke bahagian atas timbunan.
Agak mudah.
Jika anda melihat ia, kami akan berjalan melalui ini.
Jika [didengar] size-- ingat, setiap kali anda
ingin mengakses mana-mana parameter dalam struct,
anda melakukan perkara yang nama struct.parameter itu.
>> Dalam kes ini, s adalah nama timbunan kami.
Kami mahu mengakses saiz itu, jadi kami melakukan s.size.
Jadi selagi saiz tidak sama dengan kapasiti atau selama
kerana ia adalah kurang daripada kapasiti, sama ada akan bekerja di sini.
>> Anda mahu untuk mengakses di dalam timbunan anda, jadi s.strings,
dan anda akan meletakkan bahawa nombor baru yang anda mahu masukkan ke dalam sana.
Mari kita hanya mengatakan bahawa kita mahu memasukkan int n ke dalam tindanan,
kita boleh lakukan s.strings, kurungan, s.size sama n.
Kerana saiz adalah di mana kita kini berada di dalam timbunan
jika kita akan menolak di atas, kita hanya mengakses
di mana sahaja saiz adalah, kenyang semasa timbunan,
dan kita menolak int n ke ia.
Dan kemudian kita mahu memastikan bahawa kita juga menokok saiz n,
supaya kita boleh mengesan kami telah menambah perkara tambahan untuk timbunan.
Sekarang kita mempunyai saiz yang lebih besar.
Adakah ini di sini akal untuk semua orang, bagaimana logik ia berfungsi?
Ia adalah jenis yang cepat.
PENONTON: Bolehkah anda pergi yang s.stringss.strings [s.size] sekali lagi?
ANDI PENG: Pasti, jadi apakah s.size kini memberikan kita?
PENONTON: Ia adalah saiz semasa.
ANDI PENG: Tepat, jadi indeks semasa yang saiz kami adalah di,
dan dengan itu kita mahu meletakkan integer baru yang kita mahu masukkan ke dalam s.size.
Adakah ini masuk akal?
Kerana s.strings, apa yang adalah adalah nama array.
Semua itu adalah mengakses pelbagai dalam struct kami,
dan jadi jika kita mahu meletakkan n ke dalam indeks itu,
kita hanya boleh mengaksesnya menggunakan kurungan s.size.
Sejuk.
>> Baiklah, pop, saya pseudokod keluar untuk anda semua, tetapi konsep yang sama.
Adakah ini masuk akal?
Jika saiz lebih besar daripada sifar, maka anda
tahu bahawa anda mahu mengambil sesuatu keluar kerana jika saiz tidak
lebih besar daripada sifar, maka anda mempunyai apa-apa dalam timbunan.
>> Jadi anda hanya ingin melaksanakan kod ini, ia hanya boleh
pop jika ada sesuatu untuk pop.
Jadi jika saiz lebih besar daripada 0, kita tolak saiz.
Kami susutan saiz dan kemudian kembali apa yang ada di dalamnya kerana
oleh bermunculan, kita mahu akses apa sahaja yang disimpan
dalam indeks bahagian atas timbunan.
Semua yang masuk akal?
Jika saya membuat kamu menulis ini keluar, akan anda semua dapat menulis itu?
OK, anda semua boleh bermain-main dengannya.
Jangan bimbang jika anda tidak mendapatkannya.
Kami tidak mempunyai masa untuk kod ia keluar hari ini kerana kami telah
mendapat banyak struktur ini untuk pergi melalui, tetapi pada dasarnya
pseudokod, sangat, sangat serupa dengan menolak.
Hanya ikut bersama-sama logik.
Pastikan anda mengakses semua ciri-ciri struct anda dengan betul.
Ya?
>> PENONTON: Adakah slaid ini dan semua ini sehingga hari ini-ish?
ANDI PENG: Sentiasa, yep.
Saya akan cuba untuk meletakkan ini sehingga seperti satu jam selepas.
Saya akan mengemel David, David akan cuba untuk meletakkan ia seperti satu jam selepas ini.
>> OK, jadi kita bergerak ke dalam ini lain struktur data indah dipanggil barisan.
Seperti yang anda semua boleh lihat di sini, yang giliran, untuk British di kalangan kita,
semua itu adalah satu barisan.
Jadi bertentangan dengan apa yang anda berfikir timbunan adalah,
barisan yang adalah apa yang secara logik anda fikir ia.
Ia diadakan oleh kaedah-kaedah FIFO, yang Pertama Dalam, Pertama Out.
Jika anda pertama satu dalam baris, anda berada
yang pertama yang keluar dari barisan.
>> Jadi apa yang kita suka untuk memanggil ini adalah dequeueing dan enqueueing.
Jika kita mahu menambah sesuatu kepada barisan kita, kita enqueue.
Jika kita mahu dequeue, atau mengambil sesuatu yang jauh, kita dequeue.
>> Rasa begitu sama yang kita jenis mewujudkan unsur-unsur tetap saiz yang kita
boleh menyimpan tertentu perkara, tetapi kita juga boleh
perubahan di mana kita meletakkan parameter di dalam mereka
berdasarkan jenis apa fungsi yang kita mahu.
Jadi susunan, kita mahu yang lalu satu, N untuk menjadi yang pertama satu daripada itu.
Giliran ialah kita mahu perkara pertama masuk untuk perkara pertama yang keluar.
>> Jadi struct-jenis menentukan, seperti yang anda lihat,
ia sedikit berbeza dari apa timbunan itu
kerana bukan sahaja kita perlu terus mengesan di mana saiz yang masa ini adalah,
kami juga ingin untuk mengesan kepala serta di mana kita kini berada.
Jadi saya fikir lebih mudah jika saya menarik ini sehingga.
Jadi mari kita bayangkan kami mempunyai barisan, jadi katakan kepala adalah di sini.
Ketua talian, mari kita hanya mengatakan bahawa pada masa ini di sana,
dan kami mahu memasukkan sesuatu ke dalam barisan.
Saya akan memanggil saiz dasarnya adalah perkara yang sama seperti ekor,
akhir di mana sahaja giliran anda.
Mari kita katakan saiz yang tepat di sini.
>> Jadi bagaimana seseorang layak di memasukkan sesuatu ke dalam barisan?
Apa indeks kita mahu meletakkan di mana kita mahu memasukkan ke dalam.
Jika ini adalah permulaan anda beratur dan ini adalah akhir itu
atau saiz itu, di mana kita ingin menambah objek yang akan datang?
>> PENONTON: [didengar]
ANDI PENG: Tepat sekali, anda mahu tambah ia bergantung kepada anda telah menulis.
Sama ada ini adalah kosong atau yang kosong.
Jadi, anda mahu untuk menambah ia mungkin di sini kerana jika saiz is--
jika semua ini adalah penuh, anda mahu untuk menambah ia di sini, bukan?
>> Dan supaya, manakala sangat, sangat mudah, tidak cukup sentiasa betul
kerana perbezaan utama antara barisan dan timbunan
adalah bahawa barisan boleh sebenarnya dimanipulasi
supaya perubahan kepala bergantung kepada di mana anda mahu
awal isyarat anda untuk bermula.
Dan hasilnya, ekor anda juga akan berubah.
Dan supaya kita lihat kod ini buat masa ini.
Seperti yang anda semua juga diminta untuk menulis kuiz, enqueue.
Mungkin kita akan bercakap melalui mengapa jawapannya adalah apa yang ia.
>> Saya tidak boleh agak sesuai baris ini pada satu, tetapi pada dasarnya ini sekeping kod
harus pada satu baris.
Belanja seperti 30 saat.
Sila lihat dan melihat mengapa ini adalah cara yang bahawa ia adalah.
>> Sangat, struct hampir sama, sangat, sangat struktur yang sama seperti sebelumnya
timbunan kecuali mungkin satu baris kod.
Dan itu satu baris kod menentukan fungsi.
Dan ia benar-benar membezakan giliran dari timbunan.
>> Sesiapa pun mahu mengambil tikaman untuk menerangkan mengapa anda telah
mendapat perkara ini rumit di sini?
Kami menyaksikan kembalinya kami rakan modulus indah.
Seperti yang anda semua tidak lama lagi akan datang untuk mengiktiraf dalam pengaturcaraan,
hampir bila-bila masa anda memerlukan sesuatu untuk membungkus apa-apa,
modulus akan menjadi cara untuk melakukannya.
Jadi mengetahui bahawa, adakah sesiapa yang mahu cuba menjelaskan bahawa baris kod?
Ya, semua jawapan adalah diterima dan dialu-alukan.
PENONTON: Adakah anda bercakap dengan saya?
ANDI PENG: Ya.
PENONTON: Oh, tidak maaf.
ANDI PENG: OK, jadi mari kita berjalan melalui kod ini.
Oleh itu, apabila anda cuba untuk menambah sesuatu ke barisan,
dalam hal yang indah yang kepala berlaku menjadi di sini, ia sangat mudah untuk kita
hanya pergi ke akhir memasukkan sesuatu, bukan?
Tetapi titik keseluruhan barisan adalah bahawa kepala sebenarnya boleh secara dinamik
berubah bergantung kepada di mana kita mahu permulaan q kami menjadi,
dan oleh itu, ekor juga akan berubah.
>> Dan supaya membayangkan bahawa ini tidak adalah beratur, tetapi ini adalah barisan.
Katakan kepala adalah di sini.
Katakan barisan kami kelihatan seperti ini.
Jika kita mahu beralih di mana awal barisan adalah,
katakan kita beralih kepala cara ini dan saiz di sini.
>> Sekarang kita mahu menambah sesuatu untuk barisan ini, tetapi seperti yang anda semua boleh lihat,
ia tidak begitu mudah kerana hanya menambah apa sahaja adalah selepas saiz
kerana kita kehabisan batas-batas lokasi sebenar kami.
Di mana kita mahu benar-benar menambah ada di sini.
Itulah keindahan barisan ialah kepada kami, visual ia
kelihatan seperti garis pergi seperti ini, tetapi apabila disimpan dalam struktur data,
mereka memberikan sebagai seperti kitaran.
Ia jenis membaluti ke hadapan dengan cara yang sama
yang satu barisan juga boleh balut sekitar bergantung kepada mana sahaja yang anda
mahu awal barisan untuk menjadi.
Dan jadi jika kita mengambil melihat ke bawah di sini, mari kita
mengatakan bahawa kita mahu mencipta fungsi dipanggil enqueue.
Kami mahu menambah int n ke dalam q itu.
Jika q.size q-- kita akan memanggil bahawa data kami structure-- jika queue.size kami tidak
sama dengan kapasiti atau jika ia kurang daripada kapasiti,
q.strings adalah pelbagai dalam tempoh q kami.
Kami akan menetapkan yang sama dengan q.heads,
yang betul-betul di sini, ditambah q.size modulus oleh kapasiti, yang
membalut kita kembali di sini.
>> Jadi, dalam contoh ini, indeks kepala adalah 1, bukan?
Indeks saiz adalah 0, 1, 2, 3, 4.
Oleh itu, kita boleh lakukan 1 tambah 4 modulus dengan kemampuan kita iaitu 5.
Apa yang boleh kita dapat?
Apakah indeks yang keluar dari ini?
>> PENONTON: 0.
>> ANDI PENG: 0, yang berlaku untuk menjadi di sini,
dan dengan itu kita mahu dapat untuk memasukkan ke dalam di sini.
Dan sebagainya persamaan ini di sini baik hati hanya bekerja dengan mana-mana nombor
bergantung kepada di mana anda kepala dan saiz anda berada.
Jika anda tahu apa yang mereka perkara-perkara yang, anda tahu
betul-betul di mana anda mahu untuk memasukkan apa yang ada selepas baris gilir anda.
Adakah ini masuk akal untuk semua orang?
>> Saya tahu jenis otak teaser terutama kerana ini
datang dalam selepas kuiz anda.
Tetapi diharapkan semua orang kini boleh memahami
mengapa penyelesaian ini atau ini fungsi adalah cara yang ia adalah.
Sesiapa pun agak tidak jelas pada itu?
OKAY.
>> Dan sehingga kini, jika anda mahu dequeue, ini
adalah di mana kepala kita akan beralih kerana jika kita dequeue,
kita tidak mengambil dari hujung q.
Kami mahu menanggalkan kepala, bukan?
Jadi hasilnya, kepala akan berubah, dan itulah sebabnya apabila anda enqueue,
anda telah mendapat untuk mengesan di mana kepala dan saiz anda
yang dapat memasukkan ke dalam kedudukan yang betul.
>> Dan jadi apabila anda dequeue, Saya juga pseudokod keluar.
Jangan ragu untuk jika anda mahu untuk cuba pengekodan ini keluar.
Anda mahu untuk menggerakkan kepala, bukan?
Jika saya mahu dequeue, saya akan menggerakkan kepala ke atas.
Ini akan menjadi kepala.
>> Dan saiz semasa kami akan tolak kerana kita tidak lagi
mempunyai empat elemen dalam array.
Kami hanya mempunyai tiga, dan kemudian kita mahu untuk kembali apa sahaja yang disimpan di dalam
kepala kerana kita mahu mengambil ini nilai daripada jadi hampir sama dengan timbunan.
Hanya anda mengambil dari tempat yang berbeza,
dan anda perlu memberi semula penuding anda ke tempat yang berbeza sebagai hasilnya.
Secara logiknya, semua orang mengikuti?
Yang besar.
>> OK, jadi kita akan bercakap sedikit lebih mendalam mengenai senarai berkaitan
kerana mereka akan menjadi sangat, sangat berharga untuk anda dalam masa sebulan yang ini
psets.
Senarai berkaitan, kerana anda semua boleh ingat, semua mereka adalah
adalah nod yang nod tertentu nilai-nilai kedua-dua nilai dan penunjuk
yang dihubungkan bersama-sama oleh mereka petunjuk.
Dan sebagainya struct tentang bagaimana kita mewujudkan nod sini ialah kita
mempunyai int n, iaitu apa sahaja yang nilai di kedai atau tali n
atau apa sahaja yang anda mahu memanggilnya, char bintang n.
Struct bintang nod, yang merupakan penunjuk yang anda mahu dalam setiap nod,
anda akan mempunyai bahawa titik penunjuk arah depan.
Anda akan mempunyai kepala daripada senarai dikaitkan itulah
akan menunjukkan ke seluruh nilai sebagainya dan sebagainya
sehingga anda akhirnya mencapai akhir.
Dan simpulan terakhir ini hanya akan tidak mempunyai penunjuk.
Ia akan menunjukkan null, dan itulah apabila
anda tahu anda telah melanda akhir senarai dipautkan anda
adalah apabila penunjuk terakhir anda tidak menunjukkan apa-apa.
>> Oleh itu, kita akan pergi sedikit lebih dalam mendalam mengenai bagaimana seseorang akan mungkin
mencari senarai berpaut.
Ingat apa yang adalah sebahagian daripada kelemahan daripada senarai berkaitan
ayat-ayat pelbagai mengenai carian.
Antara yang anda boleh carian binari, tetapi mengapa tidak boleh anda melakukannya dalam senarai berpaut?
>> PENONTON: Kerana mereka semua yang berkaitan, tetapi anda tidak cukup tahu di mana
[Didengar].
>> ANDI PENG: Ya, betul-betul jadi ingat bahawa kecemerlangan array
adalah hakikat bahawa kita mempunyai ingatan capaian rawak di mana
jika saya mahu nilai dari indeks enam, saya hanya boleh berkata indeks enam,
memberi saya nilai itu.
Dan itu kerana tatasusunan yang disusun dalam ruang berdampingan memori
di satu tempat, manakala jenis senarai berkaitan
adalah secara rawak berselang di sekeliling, dan satu-satunya cara yang anda boleh mencari satu
adalah melalui penunjuk yang memberitahu anda alamat di mana nod seterusnya adalah.
>> Dan supaya hasilnya, satu-satunya cara untuk mencari melalui senarai berpaut
adalah carian linear.
Kerana saya tidak tahu di mana sebenarnya nilai ke-12 dalam senarai berkaitan adalah,
Saya perlu merentasi keseluruhan yang itu satu senarai berkaitan
demi satu dari kepala untuk nod pertama, kepada nod kedua, untuk nod ketiga,
semua jalan ke bawah sehingga saya akhirnya mendapatkan di mana nod saya cari adalah.
Dan sebagainya dalam hal ini, carian dalam senarai berpaut sentiasa n.
Ia sentiasa n.
Ia sentiasa Masa linear.
>> Dan sebagainya kod di mana kami melaksanakan ini, dan ini
agak baru untuk anda semua kerana anda semua telah tidak benar-benar bercakap tentang atau pernah
lihat petunjuk dalam bagaimana untuk mencari melalui petunjuk,
jadi kita akan berjalan melalui ini sangat, dengan perlahan-lahan.
Jadi carian bool, kanan, mari kita bayangkan kita mahu
untuk mewujudkan fungsi yang dipanggil carian yang mengembalikan benar
jika anda mendapati nilai dalam terpaut senarai, dan ia mengembalikan palsu sebaliknya.
Senarai nod bintang ini kini hanya penunjuk
untuk item pertama dalam senarai berpaut anda.
int n adalah nilai yang anda berada mencari dalam senarai itu.
>> Jadi penunjuk nod bintang sama senarai.
Ini bermakna kita menetapkan dan mewujudkan penunjuk
untuk nod pertama dalam senarai.
Semua orang dengan saya?
Jadi jika kita pergi kembali ke sini, saya perlu
dimulakan penunjuk yang menunjukkan ketua apa senarai yang.
>> Dan kemudian sekali anda turun di sini, manakala penunjuk tidak sama null,
jadi yang gelung di mana kita berada akan menjadi seterusnya menyeberangi
yang lain dalam senarai kami kerana apa yang berlaku apabila penunjuk sama null?
Kita tahu bahawa kita ada--
>> PENONTON: [didengar]
>> ANDI PENG: Tepat sekali, jadi kita tahu bahawa kami telah sampai ke penghujung senarai, bukan?
Jika anda pergi ke sini, setiap nod harus menunjuk kepada nod yang lain
dan sebagainya dan sebagainya sehingga anda memukul akhirnya
ekor senarai berpaut anda, yang mempunyai penunjuk yang hanya
tidak menunjukkan mana-mana selain daripada tiada.
Dan supaya anda pada dasarnya tahu bahawa senarai anda masih ada sehingga
sehingga penunjuk tidak sama null kerana sekali ia sama null,
anda tahu bahawa tidak ada lebih banyak barang.
>> Jadi itulah gelung di mana kita berada akan mempunyai carian yang sebenar.
Dan jika pointer-- kaulihatkah yang jenis anak panah fungsi di sana?
Jadi, jika mata penunjuk kepada n, jika penunjuk di n sama sama n,
jadi ini bermakna bahawa jika penunjuk bahawa anda
mencari pada akhir setiap nod sebenarnya adalah sama dengan nilai
anda cari, maka anda mahu untuk kembali benar.
Jadi, pada asasnya, jika anda berada di nod yang mempunyai nilai yang anda cari,
anda tahu bahawa anda telah dapat berjaya mencari.
>> Jika tidak, anda mahu untuk menetapkan penuding anda ke nod seterusnya.
Itulah yang baris itu di sini lakukan.
Penunjuk sama penunjuk akan datang.
Semua orang melihat bagaimana yang bekerja?
>> Dan pada dasarnya anda akan hanya merentasi keseluruhan senarai,
menetapkan semula penunjuk anda setiap masa sehingga anda akhirnya melanda akhir senarai.
Dan anda tahu bahawa tidak ada lebih nod untuk mencari melalui,
dan kemudian anda boleh kembali palsu kerana anda tahu bahawa, oh, baik,
jika saya telah dapat mencari melalui keseluruhan daripada senarai.
Jika dalam contoh ini, jika saya mahu untuk mencari nilai 10,
dan saya bermula dari kepala, dan Saya mencari semua jalan ke bawah,
dan saya akhirnya mendapat untuk ini, yang penunjuk yang menunjukkan batal,
Saya tahu bahawa, crap, saya rasa 10 tidak ada di dalam senarai ini kerana saya tidak dapat menemuinya.
Dan saya pada akhir senarai.
Dan di mana anda tahu Saya akan kembali palsu.
>> Biarkan yang rendam dalam untuk sedikit.
Ini akan menjadi cantik penting untuk pset anda.
Logik ia adalah sangat mudah, mungkin sintaksis hanya melaksanakannya.
Kalian ingin memastikan bahawa anda memahami.
Sejuk.
>> OK, jadi bagaimana kita akan memasukkan nod, betul,
ke dalam senarai kerana ingat apakah apa manfaat
mempunyai senarai berpaut berbanding pelbagai dari segi simpanan?
>> PENONTON: Ia adalah dinamik, supaya lebih mudah supaya-
>> ANDI PENG: Tepat sekali, supaya lebih dinamik, yang
bermakna bahawa ia boleh berkembang dan mengecut bergantung kepada keperluan pengguna.
Dan sebagainya, dalam hal ini, kita tidak perlu membuang memori yang tidak perlu kerana saya
jika saya tidak tahu berapa banyak nilai-nilai saya ingin ke kedai, ia tidak masuk akal bagi saya
untuk mewujudkan pelbagai kerana jika saya mahu menyimpan 10 nilai
dan saya membuat pelbagai 1000, itu banyak memori sia-sia, diperuntukkan.
Itulah sebabnya kita mahu menggunakan dikaitkan senarai dapat dinamik
menukar atau mengecilkan saiz kami.
>> Dan sebagainya yang menjadikan sisipan sedikit lebih rumit.
Oleh kerana kita tidak boleh secara rawak mengakses elemen dengan cara itu kita akan array.
Jika saya mahu memasukkan unsur ke dalam indeks yang ketujuh,
Saya hanya boleh masukkannya ke dalam indeks yang ketujuh.
Dalam senarai berpaut, ia tidak cukup bersenam dengan mudah,
dan jadi jika kita mahu memasukkan apa-apa yang di sini dalam senarai berkaitan,
visual, ia sangat mudah untuk melihat.
Kami hanya mahu masukkannya di sana, betul-betul di awal senarai,
selepas kepala.
>> Tetapi cara di mana kita perlu memberi semula petunjuk adalah agak berbelit
atau, secara logik, ia masuk akal, tetapi anda ingin memastikan bahawa anda mempunyai
sepenuhnya ke bawah kerana Perkara terakhir yang anda mahu
adalah untuk memberi semula penunjuk yang cara yang kita lakukan di sini.
Jika anda dereference yang penunjuk dari kepala hingga ke 1,
maka semua yang secara tiba-tiba seluruh senarai dipautkan anda
hilang kerana anda tidak benar-benar mempunyai mencipta apa-apa sementara.
Itu menunjukkan kepada 2.
Jika anda memberi semula penunjuk, maka seluruh senarai anda sama sekali hilang.
Jadi, anda mahu menjadi sangat, sangat berhati-hati di sini
terlebih dahulu menetapkan penunjuk dari apa sahaja yang anda
mahu masukkan ke dalam di mana sahaja yang anda mahu, dan kemudian anda
boleh dereference seluruh senarai anda.
>> Jadi ini terpakai kerana di mana sahaja anda cuba untuk memasukkan ke dalam.
Jika anda ingin memasukkan di kepala, jika anda mahu untuk menjawab di sini,
jika anda ingin memasukkan di Akhirnya, dengan baik, akhir saya
rasa anda akan hanya tidak mempunyai penunjuk, tetapi anda
ingin memastikan bahawa anda tidak kehilangan yang lain dalam senarai anda.
Anda sentiasa ingin memastikan nod baru anda menunjuk
terhadap apa sahaja yang anda mahu masukkan ke dalam,
dan kemudian anda boleh menambah chaining pada.
Semua orang jelas?
>> Ini akan menjadi salah satu isu yang sebenar.
Salah satu isu yang paling utama anda akan ada di pset anda
adalah bahawa anda akan cuba untuk membuat senarai berpaut dan perkara-perkara sisipan
tetapi kemudian hanya kehilangan seluruh senarai terkait dengannya.
Dan anda akan menjadi seperti, saya tidak tahu mengapa ini berlaku?
Dan ia sakit untuk pergi melalui dan mencari semua petunjuk anda.
>> Dan saya jamin anda di pset ini, menulis dan melukis nod ini keluar
akan menjadi sangat, sangat membantu.
Jadi, anda boleh benar-benar mengesan di mana semua petunjuk anda berada,
apa yang berlaku salah, di mana semua nod anda berada,
apa yang anda perlu lakukan untuk mencapai atau memasukkan atau memadam atau mana-mana daripada mereka.
Semua orang baik dengan itu?
Sejuk.
>> Jadi, jika kita mahu melihat kod?
Oh, saya tidak tahu jika kita boleh lihat OK the--, jadi
di atas semua itu adalah fungsi bernama memasukkan di mana kita mahu
untuk memasukkan int n ke dalam senarai berkaitan.
Kami akan berjalan melalui ini.
Ia banyak kod, banyak sintaks baru.
Kami akan menjadi OK.
>> Jadi sehingga di bahagian atas, bila-bila masa kita mahu membuat apa-apa
apa yang kita perlu lakukan, terutamanya jika anda mahu ia tidak disimpan pada timbunan
tetapi dalam timbunan itu?
Kami pergi ke malloc, bukan?
Jadi, kita akan mewujudkan penunjuk.
Node, penunjuk, setaraf baru malloc saiz nod
kerana kita mahu nod yang diwujudkan.
Kita mahu jumlah memori yang nod mengambil
yang akan diperuntukkan untuk penciptaan nod baru.
>> Dan kemudian kita akan menyemak untuk melihat jika setaraf baru sama null.
Ingat apa yang kita katakan?
Apa sahaja yang anda malloc, apa yang perlu anda sentiasa lakukan?
Anda mesti sentiasa memeriksa untuk melihat sama ada atau tidak itu adalah null.
>> Sebagai contoh, jika operasi anda sistem itu benar-benar penuh,
jika anda mempunyai memori tidak lebih di semua dan anda cuba untuk malloc,
ia akan kembali null untuk anda.
Dan jadi jika anda cuba untuk menggunakannya apabila ia menunjuk kepada batal,
anda tidak akan dapat untuk mengakses maklumat tersebut.
Dan sebagainya oleh itu, kami mahu membuat memastikan bahawa setiap kali anda mallocing,
anda sentiasa memeriksa untuk melihat jika memori yang diberikan kepada anda adalah null.
Dan jika tidak, maka kita boleh bergerak pada dengan seluruh kod kami.
>> Oleh itu, kita akan memulakan nod baru.
Kami akan lakukan n baru sama n.
Dan kemudian kita akan lakukan set baru penunjuk pada baru
untuk null kerana sekarang kita tidak mahu apa-apa untuk itu untuk menunjukkan.
Kami tidak tahu di mana ia akan meletakkan anda,
dan kemudian jika kita mahu masukkannya di kepala,
maka kita boleh memberi semula penunjuk kepada kepala.
Adakah semua orang ikut logik di mana yang yang berlaku?
>> Semua yang kita lakukan adalah mewujudkan yang baru nod, menetapkan penunjuk kepada batal,
dan kemudian, tetapkan semula kepada kepala jika kita
tahu kita mahu masukkannya di kepala.
Kemudian kepala akan menghala ke nod baru.
Semua orang OK dengan itu?
>> Jadi ia adalah satu proses dua langkah.
Anda perlu menyerahhakkan pertama apa sahaja yang anda buat.
Menetapkan bahawa penunjuk kepada rujukan, dan kemudian anda
boleh jenis dereference penunjuk pertama
dan menunjukkan ke arah nod baru.
Di mana sahaja anda mahu memasukkannya, logik yang akan memegang benar.
>> Ia adalah jenis seperti memberikan pembolehubah sementara.
Ingat, anda mempunyai memastikan bahawa anda
tidak kehilangan jejak jika anda bertukar-tukar.
Anda ingin memastikan bahawa anda mempunyai pembolehubah sementara yang jenis menyimpan
mengesan di mana perkara yang disimpan supaya anda
tidak kehilangan apa-apa nilai dalam perjalanan daripada seperti main-main dengannya.
>> OK, jadi kod akan berada di sini.
Kalian lihat selepas seksyen.
Ia akan berada di sana.
>> Jadi saya rasa bagaimana ini berbeza jika kita mahu
untuk memasukkan ke dalam bahagian tengah atau akhir?
Adakah sesiapa yang mempunyai idea tentang apa yang yang pseudokod sebagai rujukan logik
bahawa kami akan mengambil jika kita mahu untuk memasukkannya di tengah-tengah?
Jadi, jika kita mahu masukkannya di kepala, semua yang kita lakukan adalah mewujudkan nod baru.
Kami menetapkan penunjuk yang nod baru kepada apa sahaja kepala,
dan kemudian kita set kepala kepada nod baru, bukan?
Jika kita mahu masukkannya di tengah-tengah senarai, apa yang kita perlu lakukan?
>> PENONTON: Ia akan masih menjadi proses yang sama
daripada seperti memberikan penunjuk dan kemudian memberikan penunjuk yang,
tetapi kita perlu untuk mencari di sana.
>> ANDI PENG: Tepat sekali, jadi betul-betul proses yang sama kecuali anda
perlu mencari di mana sebenarnya anda mahu itu penunjuk baru untuk pergi ke dalam,
jadi jika saya mahu masukkan ke dalam pertengahan dikaitkan list-- OK,
mari kita mengatakan bahawa senarai berpaut kami.
Jika kita mahu masukkannya di sini, kita akan mewujudkan nod baru.
Kami akan malloc.
Kami akan mewujudkan nod baru.
Kita akan menyerahhakkan penunjuk nod ini di sini.
>> Tetapi masalah yang berbeza dari mana kepala adalah
ialah kita tahu betul-betul mana kepala itu.
Ia adalah betul-betul di pertama, bukan?
Tetapi di sini kita telah mendapat untuk mengesan di mana kita memasukkan ke dalam.
Jika kita memasukkan kami nod di sini, kami mempunyai
untuk memastikan bahawa satu sebelumnya kepada nod ini
adalah salah satu yang reassigns penunjuk.
Demikian maka anda perlu jenis mengesan dua perkara.
Jika anda menjejaki di mana ini nod kini sedang memasukkan ke dalam.
Anda juga perlu menjejaki di mana nod yang sebelumnya yang anda cari di
juga di sana.
Semua orang baik dengan itu?
OKAY.
>> Bagaimana pula memasukkan ke akhir?
Jika saya mahu menambah sini-- jika saya mahu untuk menambah nod baru ke akhir senarai,
bagaimana mungkin saya boleh pergi tentang melakukan perkara itu?
PENONTON: Jadi pada masa ini, menegaskan terkini untuk null.
ANDI PENG: Ya.
Tepat sekali, jadi yang satu ini kini sedang menunjuk kepada tahu,
dan saya rasa, dalam hal ini, ia sangat mudah untuk menambah ke akhir senarai.
Apa yang anda perlu lakukan adalah menetapkan sama dengan nol dan kemudian meledak.
Di sana, sangat mudah.
Sangat mudah.
>> Hampir sama dengan kepala, tetapi secara logik anda
ingin memastikan bahawa langkah-langkah anda ambil ke arah melakukan apa-apa itu,
anda ikuti bersama-sama.
Ia sangat mudah untuk, di tengah-tengah kod anda, terjebak pada,
oh, saya telah mendapat begitu banyak petunjuk.
Saya tidak tahu di mana apa-apa yang menunjuk ke.
Saya tidak tahu mana buku saya pada.
Apa yang berlaku?
>> Berehat, bertenang, tarik nafas dalam-dalam.
Menarik keluar senarai berpaut anda.
Jika anda berkata, saya tahu di mana sebenarnya Saya perlu memasukkan ini ke dalam
dan saya tahu bagaimana untuk memberi semula saya petunjuk, banyak, lebih mudah untuk gambar
out-- banyak, lebih mudah untuk tidak hilang dalam bug kod anda.
Semua orang OK dengan itu?
OKAY.
>> Jadi saya rasa satu konsep yang kita tidak mempunyai benar-benar bercakap tentang sebelum ini,
dan saya rasa anda mungkin tidak akan menghadapi banyak YET
ia adalah jenis yang concept-- maju adalah bahawa kita benar-benar mempunyai data
struktur dipanggil senarai duanya adalah terpakai dikaitkan.
Jadi seperti yang anda semua boleh lihat, semua yang kita lakukan adalah mewujudkan
nilai sebenar, tambahan penunjuk pada setiap nod kami
yang juga menunjukkan nod sebelumnya.
Jadi bukan sahaja kita perlu kami nod menunjukkan satu depan.
Mereka juga menunjukkan yang sebelumnya.
Saya akan mengabaikan kedua-dua sekarang.
>> Sebab itu anda mempunyai rantai yang boleh bergerak kedua-dua cara,
dan kemudian ia sedikit lebih mudah secara logik ikut bersama-sama.
Seperti di sini, bukan mengesan, oh, saya
perlu tahu bahawa nod ini adalah satu yang saya perlu menyerahhakkan semula,
Saya hanya boleh pergi di sini dan hanya tarik sebelumnya.
Kemudian saya tahu di mana iaitu, dan kemudian anda
tidak perlu merentasi keseluruhan daripada senarai berkaitan.
Ia agak mudah.
>> Tetapi oleh itu, anda mempunyai dua kali ganda jumlah petunjuk,
itu dua kali ganda jumlah ingatan.
Ia banyak petunjuk untuk mengesan.
Ia adalah sedikit lebih kompleks, tetapi ia sedikit lebih mesra pengguna bergantung
kepada apa yang anda cuba untuk mencapai.
>> Jadi ini jenis data struktur betul-betul wujud,
dan struktur adalah sangat, sangat mudah kecuali semua yang anda perlu adalah,
bukan hanya penunjuk kepada akan datang, anda juga mempunyai penunjuk kepada sebelumnya.
Itu semua perbezaan adalah.
Semua orang baik dengan itu?
Sejuk.
>> Baiklah, jadi sekarang saya untuk benar-benar menghabiskan mungkin
seperti 15 hingga 20 minit atau sebahagian besar negara lain di masa dalam seksyen
bercakap tentang jadual hash.
Berapa ramai daripada anda semua telah membaca pset5 spec?
Baiklah, baik.
Itulah yang lebih tinggi daripada 50% daripada biasa.
Tidak mengapa.
>> Jadi seperti yang anda semua lihat, anda berada cabaran dalam pset5
adalah untuk melaksanakan kamus yang di mana anda memuatkan lebih 140,000 perkataan
bahawa kami memberikan anda dan periksa ejaan ia terhadap semua teks.
Kami akan memberikan anda secara rawak bahan kempen.
Kami akan memberikan anda Odyssey.
Kami akan memberikan anda The Iliad.
Kami akan memberikan anda Austin Powers.
>> Dan cabaran anda adalah untuk periksa ejaan
setiap perkataan dalam semua dari orang-orang kamus
dasarnya dengan penyemak ejaan kami.
Dan jadi ada beberapa bahagian mewujudkan pset ini,
pertama yang anda mahu dapat benar-benar memuatkan
semua perkataan ke dalam anda kamus, dan kemudian anda
hendak dapat semak ejaan semua daripada mereka.
Dan sebagainya oleh itu, anda akan memerlukan struktur data yang boleh melakukan ini cepat
dan cekap dan dinamik.
>> Jadi saya rasa yang paling mudah cara untuk melakukan ini, anda
mungkin akan mewujudkan pelbagai, bukan?
Cara yang paling mudah penyimpanan adalah anda boleh membuat pelbagai 140,000 kata-kata
dan hanya meletakkan mereka semua di sana dan kemudian merentasi mereka dengan carian binari
atau oleh pilihan atau tidak-- maaf yang yang menyusun.
Anda boleh menyusun mereka dan kemudian mereka merentasi oleh carian binari atau carian hanya linear
dan hanya akhir perkataan, tetapi itu mengambil sejumlah besar memori,
dan ia bukan sangat cekap.
>> Dan dengan itu kita akan mula bercakap mengenai cara-cara membuat
masa kita berjalan lebih cekap.
Dan matlamat kami adalah untuk mendapatkan masa yang berterusan di mana
ia hampir seperti tatasusunan, di mana anda mempunyai akses serta-merta.
Jika saya mahu mencari apa-apa, Saya hendak dapat adil,
ledakan, merasa betul-betul, dan menariknya keluar.
Dan supaya struktur di mana kita akan menjadi sangat dekat
dapat mengakses berterusan masa, ini kaedah berpotensi suci
dalam pengaturcaraan pemalar masa dipanggil jadual hash.
Dan begitu Daud sebelum ini menyebut tentang [Didengar] sedikit dalam kuliah,
tetapi kita akan benar-benar menyelam di dalam minggu ini
di atas sekeping yang yang mengenai bagaimana jadual hash berfungsi.
>> Jadi cara yang hash kerja-kerja meja, sebagai contoh,
jika saya mahu menyimpan sekumpulan kata-kata, sekumpulan kata-kata dalam bahasa Inggeris,
Saya secara teori boleh meletakkan pisang, epal, kiwi, mangga, pasangan,
dan tembikai semua kepada hanya array.
Mereka semua dapat menyesuaikan diri dan dapat mencari.
Ia akan menjadi jenis sakit untuk mencari melalui dan akses,
tetapi cara yang lebih mudah untuk melakukan ini adalah bahawa kita boleh mewujudkan struktur yang sebenarnya
dipanggil jadual hash mana kita hash.
Kami menjalankan semua kunci kami melalui fungsi hash, persamaan,
yang mengubah mereka semua ke dalam beberapa jenis nilai yang
yang kemudian kita boleh simpan pada pada dasarnya pelbagai senarai berkaitan.
>> Dan sebagainya di sini, jika kita mahu untuk menyimpan perkataan Inggeris,
kita boleh berpotensi adil, saya tidak tahu, menukar semua huruf pertama
ke dalam beberapa jenis nombor.
Dan sebagainya, sebagai contoh, jika saya mahu A menjadi sinonim dengan apple--
atau dengan indeks 0, dan B menjadi sinonim dengan 1,
kita boleh mempunyai 26 penyertaan yang hanya boleh menyimpan
semua huruf daripada abjad bahawa kita akan memulakan dengan.
Dan kemudian kita boleh mempunyai epal di indeks 0.
Kita boleh mempunyai pisang di indeks 1, tembikai pada indeks 2,
dan sebagainya dan sebagainya.
Dan dengan itu jika saya mahu mencari hash meja dan akses epal saya,
Saya tahu epal bermula dengan A, dan saya tahu
bahawa ia mesti dan hash meja di indeks 0 kerana
fungsi yang diberikan sebelum ini.
>> Jadi, saya tidak tahu, kami program pengguna di mana
anda akan dikenakan bayaran dengan tidak arbitrarily-- sewenang-wenangnya,
dengan cuba untuk teliti berfikir persamaan baik
dapat menyebarkan keluar semua nilai-nilai anda
dengan cara yang mereka dengan mudah boleh mengakses kemudian di dengan seperti persamaan
bahawa anda, diri sendiri, tahu.
Jadi dalam erti kata yang jika saya mahu pergi ke mangga, saya tahu, oh, ia bermula dengan m.
Ia mesti sekurang-indeks 12.
Saya tidak perlu mencari melalui apa-apa.
Saya tahu exactly-- saya hanya boleh pergi ke indeks 12 dan tarik yang keluar.
>> Semua orang yang jelas mengenai bagaimana fungsi jadual hash ini berfungsi?
Ia adalah jenis hanya lokasi yang lebih kompleks.
Itu sahaja yang ia adalah.
OKAY.
>> Jadi saya rasa kita menghadapi isu ini daripada apa yang
berlaku jika anda mempunyai beberapa perkara yang yang memberikan indeks yang sama?
Jadi mengatakan fungsi kita, semua itu lakukan adalah mengambil surat pertama
dan menghidupkan yang menjadi masing-0 melalui 25 indeks.
Yang sama sekali baik jika anda hanya mempunyai satu masing-masing.
Tetapi kedua anda mula mempunyai lebih banyak, anda
akan mempunyai apa yang dipanggil perlanggaran.
>> Jadi, jika saya cuba untuk memasukkan ke dalam mengebumikan hash jadual yang sudah mempunyai pisang di atasnya,
apa yang akan berlaku apabila anda cuba untuk memasukkan itu?
Perkara-perkara buruk kerana pisang sudah wujud dalam indeks
yang ingin anda simpan ke dalam.
Berry jenis adalah seperti, ah, apa yang saya lakukan?
Saya tidak tahu ke mana hendak pergi.
Bagaimana saya boleh menyelesaikan ini?
>> Dan supaya anda semua jenis kehendaki di antara melihat kita melakukan perkara ini rumit
di mana kita boleh sejenis sebenarnya membuat senarai dikaitkan dalam tatasusunan kami.
Jadi cara yang paling mudah dan untuk berfikir tentang perkara ini,
semua jadual hash adalah pelbagai senarai berkaitan.
Dan sebagainya, dalam erti kata itu, anda perlu pelbagai ini indah petunjuk,
dan kemudian setiap penunjuk dalam nilai itu, dalam indeks itu,
sebenarnya boleh menunjukkan kepada perkara-perkara lain.
Dan supaya anda mempunyai semua yang berasingan rantai datang kira satu array besar.
>> Dan sebagainya di sini, jika saya mahu memasukkan berry,
Saya tahu, OK, saya akan input melalui fungsi hash saya.
Saya akan berakhir dengan indeks 1, dan kemudian saya akan dapat mempunyai
hanya subset yang lebih kecil ini gergasi kamus 140,000 perkataan.
Dan kemudian saya hanya boleh melihat melalui 1/26 itu.
>> Dan demikian maka saya hanya boleh memasukkan berry sama ada sebelum atau selepas pisang
dalam kes ini?
Selepas, bukan?
Dan supaya anda akan mahu untuk memasukkan nod ini selepas pisang,
dan supaya anda akan memasukkan di ekor bahawa senarai berkaitan.
Saya akan kembali untuk slaid ini sebelumnya,
supaya anda semua boleh lihat bagaimana fungsi hash berfungsi.
>> Jadi fungsi hash adalah persamaan ini bahawa anda menjalankan jenis input anda
melalui untuk mendapatkan apa sahaja indeks anda ingin gunakan ke arah.
Dan sebagainya, dalam contoh ini, semua yang kita mahu lakukan adalah mengambil surat pertama,
berubah itu ke dalam indeks, maka kita boleh menyimpan bahawa dalam fungsi hash kami.
Semua yang kita lakukan di sini adalah kami menukar huruf pertama.
Jadi keykey [0] hanya huruf pertama apa jua rentetan kita yang mempunyai,
kita lulus dalam.
Kami menukar bahawa untuk atas, dan kami menolak dengan huruf besar A,
jadi semua yang melakukan memberi kami nombor satu
di mana kita boleh hash nilai-nilai kita ke.
>> Dan kemudian kita akan kembali hash modulus SAIZ.
Menjadi sangat, sangat berhati-hati kerana, secara teori, di sini
nilai hash anda boleh menjadi tak terhingga.
Ia hanya boleh pergi pada dan pada dan pada.
Ia boleh menjadi beberapa benar-benar, benar-benar nilai besar,
tetapi kerana jadual hash anda yang anda telah membuat hanya mempunyai 26 indeks,
anda ingin memastikan anda modulusing supaya anda
tidak run-- ia adalah sama Perkara seperti queue-- anda
supaya anda tidak lari daripada bawah fungsi hash anda.
>> Anda mahu balut kembali sekitar cara yang sama dalam [didengar] apabila
anda mempunyai seperti yang sangat, surat sangat besar, anda
tidak mahu itu hanya berjalan melepasi hujung meja.
Perkara yang sama di sini, anda ingin memastikan ia tidak lari akhirnya dengan membalut
sekitar untuk bahagian atas meja.
Jadi ini adalah hanya sangat fungsi hash mudah.
Semua yang dilakukan adalah mengambil yang pertama surat apa-apa input kami adalah
dan menghidupkan itu ke dalam indeks yang kita boleh meletakkan ke dalam jadual hash kami.
>> Ya, dan sebagainya seperti yang saya katakan sebelum ini, cara kita menyelesaikan perlanggaran
dalam jadual hash kami menghadapi, apa yang kita panggil, chaining.
Jadi, jika anda cuba untuk memasukkan beberapa kata-kata yang bermula dengan perkara yang sama,
anda akan mempunyai satu nilai hash.
Avokado dan epal, jika anda telah menjalankannya melalui fungsi hash kami,
akan memberikan anda Bilangan yang sama, bilangan 0.
Dan begitu cara kita menyelesaikan yang bahawa kita boleh sebenarnya jenis menghubungkan mereka
bersama-sama melalui senarai berkaitan.
>> Dan sebagainya dalam hal ini, anda semua boleh melihat jenis
bagaimana struktur data yang kami telah menetapkan sebelumnya
seperti kismis dikaitkan senarai jenis daripada boleh datang bersama-sama ke dalam satu.
Dan kemudian anda boleh membuat jauh struktur data yang lebih cekap
yang boleh mengendalikan jumlah yang lebih besar data, yang secara dinamik mengubah saiz bergantung
kepada keperluan anda.
Semua orang jelas?
Jenis orang yang jelas kepada apa yang berlaku di sini?
>> Jika saya mahu insert-- apa yang a buah-buahan yang bermula dengan, saya tidak tahu,
B, selain beri, pisang.
>> PENONTON: Blackberry.
>> ANDI PENG: Blackberry, blackberry.
Di manakah blackberry pergi sini?
Nah, kita benar-benar tidak disusun ini lagi, tetapi secara teori
jika kita mahu mempunyai ini mengikut abjad,
di mana perlu BlackBerry pergi?
>> PENONTON: [didengar]
>> ANDI PENG: Tepat sekali, selepas di sini, bukan?
Tetapi oleh kerana ia amat sukar untuk reorder-- Saya rasa ia terpulang kepada anda semua.
Anda semua boleh sama sekali melaksanakan apa sahaja yang anda mahu.
Cara yang lebih cekap untuk berbuat demikian mungkin
adalah untuk menyusun dipautkan anda senarai ke dalam susunan abjad,
dan sebagainya apabila anda berada memasukkan sesuatu, anda mahu
untuk memastikan untuk memasukkan mereka ke dalam susunan abjad
supaya kemudian apabila anda berada cuba untuk mencari mereka,
anda tidak perlu merentasi segala-galanya.
Anda tahu di mana ia adalah, dan ia lebih mudah.
>> Tetapi jika anda jenis mempunyai perkara yang berselang secara rawak,
anda masih akan mempunyai untuk merentasi ia anyways.
Dan jadi jika saya mahu hanya memasukkan blackberry sini
dan saya mahu mencari , saya tahu, oh, blackberry
mesti bermula dengan indeks 1, jadi saya tahu serta-merta hanya mencari di 1.
Dan kemudian saya boleh jenis merentasi senarai berkaitan
sehingga saya dapat blackberry, dan then-- ya?
>> PENONTON: Jika anda cuba untuk create-- Saya rasa seperti ini adalah hash sangat mudah
fungsi.
Dan jika kita mahu lakukan pelbagai lapisan seperti itu,
OK, kita mahu untuk memisahkan ke dalam seperti semua huruf abjad
dan sekali lagi untuk suka set lain huruf abjad dalam masa itu,
kita meletakkan seperti hash meja dalam jadual hash,
atau seperti fungsi dalam satu majlis?
Atau adakah bahawa-
>> ANDI PENG: Jadi hash anda function-- jadual hash anda
boleh menjadi sebesar yang anda mahu ia.
Jadi dalam hal ini, saya fikir ia adalah sangat mudah, sangat
mudah untuk saya hanya jenis berdasarkan pada huruf perkataan pertama.
Dan sebagainya hanya ada 26 pilihan.
Saya hanya boleh mendapatkan 26 pilihan dari 0-25 kerana mereka hanya boleh
mula dari A ke Z. Tetapi Jika anda mahu untuk menambah, mungkin, lebih kompleks
atau lebih cepat masa berjalan untuk anda jadual hash, anda benar-benar
boleh melakukan pelbagai perkara.
Anda boleh membuat anda sendiri persamaan yang memberikan anda
agihan yang lebih dalam anda kata-kata, maka ketika anda mencari,
ia akan menjadi lebih cepat.
>> Ia benar-benar terpulang kepada anda semua bagaimana anda mahu untuk melaksanakan itu.
Fikirkan ia sebagai hanya baldi.
Jika saya mahu mempunyai 26 baldi, saya akan
untuk menyelesaikan sesuatu ke dalam orang-orang baldi.
Tetapi saya akan mempunyai sekumpulan barangan dalam setiap baldi,
jadi jika anda mahu membuat ia lebih cepat dan lebih cekap,
biarlah saya mempunyai seratus baldi.
>> Tetapi kemudian anda perlu memikirkan satu cara untuk menyelesaikan perkara-perkara supaya mereka
dalam baldi yang betul mereka seharusnya berada di dalam.
Tetapi apabila anda benar-benar mahu melihat baldi itu,
ia banyak lebih cepat kerana ada barangan yang kurang dalam setiap baldi.
Dan sebagainya, yeah, yang sebenarnya helah untuk anda semua dalam pset5
adalah bahawa anda akan menjadi dicabar untuk hanya membuat
apa yang paling berkesan fungsi yang boleh anda fikirkan untuk menjadi
dapat menyimpan dan memeriksa nilai-nilai ini.
>> Benar-benar terpulang kepada anda semua tetapi anda mahu untuk melakukannya,
tetapi itu adalah satu titik benar-benar baik.
Bahawa jenis logik anda mahu untuk mula berfikir tentang
adalah, baik, mengapa tidak saya membuat lebih banyak baldi.
Dan kemudian saya perlu mencari kurang sesuatu, dan mungkin saya
mempunyai fungsi hash yang berbeza.
>> Ya, terdapat banyak cara untuk melakukan ini Serangga, ada yang lebih cepat daripada yang lain.
Saya betul-betul akan hanya melihat bagaimana cepat adalah yang paling cepat anda semua akan
dapat untuk mendapatkan fungsi anda untuk bekerja.
OK, semua orang di baik chaining dan hash jadual?
Ia sebenarnya seperti yang sangat mudah konsep jika anda berfikir mengenainya.
Semua itu adalah apa sahaja yang memisahkan input anda adalah ke dalam baldi,
menyusun mereka, dan kemudian mencari menyenaraikan bahawa ada berkaitan dengan.
>> Sejuk.
Baiklah, sekarang kita mempunyai jenis yang berbeza struktur data yang dinamakan pokok.
Mari kita pergi pada dan bercakap tentang percubaan yang jelas berbeza,
tetapi dalam kategori yang sama.
Pada asasnya, semua pokok adalah sebaliknya menganjurkan data dengan cara yang linear
bahawa jadual hash does-- anda tahu, ia mendapat bahagian atas dan bawah yang
dan kemudian anda jenis menghubungkan kira kitab itu yang pokok mempunyai bahagian yang kamu seru akar,
dan kemudian ia mempunyai daun sekelilingnya.
>> Dan jadi apa yang anda ada di sini hanya nod bahagian
yang menunjuk ke nod lain, titik kepada lebih nod, dan sebagainya dan sebagainya.
Dan jadi anda hanya mempunyai cawangan berpisah.
Ia hanya cara yang berbeza dalam menganjurkan data, dan kerana kita memanggilnya pokok,
anda semua just-- ia hanya dimodelkan keluar kelihatan seperti pokok.
Itulah sebabnya kita memanggilnya pokok.
>> Jadual hash kelihatan seperti jadual.
Pokok hanya kelihatan seperti pokok.
Semua itu adalah yang berasingan cara mengatur nod
bergantung kepada apa keperluan anda.
>> Jadi, anda mempunyai akar dan maka anda mempunyai daun.
Cara yang kita boleh terutamanya berfikir tentang hal itu adalah pokok binari,
pokok binari hanya jenis tertentu pokok
di mana setiap nod hanya mata , sekurang-max, dua nod lain.
Dan sebagainya di sini anda perlu berbeza simetri dalam pokok anda
yang menjadikan ia lebih mudah untuk jenis melihat apa nilai anda kerana anda
mempunyai sentiasa kiri atau kanan.
Ada pernah seperti satu pertiga kiri dari kiri atau keempat dari kiri.
Ia hanya anda mempunyai kiri dan kanan yang dan anda boleh mencari sama ada kedua-dua.
Dan sebagainya mengapa ini berguna kepada anda?
Cara bahawa ini adalah berguna ialah jika anda sedang mencari
untuk mencari melalui nilai-nilai, bukan?
Daripada melaksanakan binari mencari dalam pelbagai kesilapan,
jika anda mahu menjadi mampu untuk memasukkan nod dan mengambil nod sesuka hati dan juga
memelihara carian kapasiti carian binari.
Jadi dengan cara ini, kami jenis tricking-- masih ingat ketika kami
berkata senarai berkaitan tidak boleh carian binari?
Kami sejenis mewujudkan struktur data bahawa helah itu ke dalam kerja.
>> Dan senarai demikian kerana dikaitkan adalah linear, mereka hanya menghubungkan satu demi satu.
Kita boleh jenis mempunyai jenis yang berbeza petunjuk
ketika itu untuk nod yang berbeza yang boleh membantu kami dengan carian.
Dan sebagainya di sini, jika saya mahu mempunyai pokok carian binari,
Saya tahu bahawa tengah saya jika 55.
Saya hanya akan membuat yang sebagai tengah saya, kerana akar saya,
dan kemudian saya akan mempunyai nilai berputar jauh daripada itu.
>> Jadi di sini, jika saya akan mencari nilai 66, saya boleh bermula pada 55.
Ia adalah 66 lebih besar daripada 55?
Ya, ia adalah, jadi saya tahu saya mus mencari i n penunjuk yang betul pokok ini.
Saya pergi ke 77.
OK, adalah 66 kurang daripada atau lebih daripada 77?
Ia adalah kurang daripada, supaya anda tahu, oh, yang telah menjadi nod kiri.
>> Dan jadi di sini kita jenis memelihara semua perkara yang menarik mengenai tatasusunan,
jadi seperti saiz semula dinamik objek, yang
dapat memasukkan dan memadam sesuka hati, tanpa perlu bimbang tentang tetap
jumlah ruang.
Kami masih mengekalkan semua perkara-perkara yang indah
di samping dapat mengekalkan log dan masa carian binari mencari
bahawa kami hanya sebelum ini mampu untuk mendapatkan frasa.
>> Struktur data sejuk, jenis kompleks untuk melaksanakan, nod.
Seperti yang anda lihat, semua itu adalah struct nod
adalah bahawa anda mempunyai kiri yang dan penunjuk yang betul.
Itu sahaja yang ia adalah.
Jadi, daripada hanya yang mempunyai x atau sebelumnya.
Anda mempunyai kiri atau kanan, dan kemudian anda boleh jenis menghubungkan mereka bersama-sama
Walau bagaimanapun anda supaya memilih.
>> OK, kita sebenarnya akan hanya mengambil masa beberapa minit.
Oleh itu, kita akan pergi ke sini.
Seperti yang saya katakan sebelum ini, Saya jenis menjelaskan
logik di sebalik bagaimana kita akan mencari melalui ini.
Kami akan cuba pseudocoding keluar ini untuk melihat
jika kita jenis boleh memohon Logik yang sama carian binari
jenis yang berbeza daripada struktur data.
Jika anda semua ingin mengambil seperti pasangan minit kepada hanya berfikir tentang perkara ini.
OKAY.
Baiklah, saya akan sebenarnya hanya memberikan anda the-- tidak,
kita akan bercakap tentang kod pseudo yang pertama.
Jadi adakah sesiapa yang mahu untuk memberi tikaman apa
perkara pertama yang anda mahu lakukan apabila anda memulakan pencarian itu?
Jika kita mencari nilai 66, apa yang
perkara pertama yang kita mahu lakukan jika kita mahu binari mencari pokok ini?
>> PENONTON: Anda mahu melihat ke kanan dan melihat kiri dan lihat [didengar]
jumlah yang lebih besar.
>> ANDI PENG: Ya, betul-betul.
Jadi, anda akan melihat akar anda.
Ada banyak cara anda boleh menghubungi ia, orang nod induk anda berkata.
Saya suka untuk mengatakan akar kerana yang seperti akar pokok.
Anda akan melihat nod akar anda, dan anda
akan lihat adalah 66 lebih besar daripada atau kurang daripada 55.
Dan jika ia lebih besar daripada, dengan baik, ia adalah lebih besar daripada, di mana kita mahu melihat?
Di manakah kita mahu mencari sekarang, bukan?
Kami mahu mencari separuh betul pokok ini.
>> Jadi kita mempunyai, mudah, yang penunjuk yang menunjuk ke kanan.
Dan demikian maka kita boleh menetapkan akar baru kami untuk menjadi 77.
Kami hanya boleh pergi ke mana sahaja yang penunjuk menunjuk.
Nah, oh, di sini kita bermula 77, dan kita boleh hanya
melakukannya secara berulang lagi dan lagi.
Dengan cara ini, anda jenis daripada mempunyai fungsi.
Anda mempunyai cara untuk mencari yang hanya boleh mengulangi berkali-kali,
bergantung di mana anda mahu melihat sehingga anda akhirnya sampai ke nilai
yang anda sedang mencari.
Masuk akal?
>> Saya akan menunjukkan kepada anda yang sebenar kod, dan ia banyak kod.
Tidak perlu dimarahi.
Kami akan bercakap melaluinya.
>> Sebenarnya, tidak.
Yang hanya kod pseudo.
OK, yang hanya pseudokod, yang agak kompleks,
tetapi ia benar-benar baik.
Semua orang berikut bersama-sama di sini?
Jika akar itu adalah batal, pulangan palsu kerana cara yang
anda tidak mempunyai apa-apa di sana.
>> Jika akar n adalah nilai, jadi jika ia berlaku untuk menjadi satu yang anda cari pada,
maka anda akan kembali benar kerana anda tahu anda menjumpainya.
Tetapi jika nilainya adalah kurang daripada akar n, anda berada
akan mencari kiri kanak-kanak atau daun kiri,
apa sahaja yang anda mahu panggil ia.
Dan jika nilai adalah lebih besar daripada akar, anda akan mencari pokok yang betul,
kemudian hanya menjalankan fungsi melalui carian lagi.
>> Dan jika akar adalah batal, yang yang bermakna anda telah mencapai akhir?
Ini bermakna anda tidak mempunyai lebih lebih daun untuk mencari,
maka anda tahu, oh, saya rasa ia bukan di sini
kerana selepas saya telah melihat melalui segala-galanya dan ia tidak ada di sini,
ia hanya tidak mungkin berada di sini.
>> Adakah ini masuk akal untuk semua orang?
Jadi ia adalah seperti carian binari memelihara keupayaan senarai berkaitan.
Sejuk, dan sebagainya jenis kedua struktur data anda semua
boleh cuba melaksanakan pada pset anda, anda hanya perlu memilih salah satu kaedah.
Tetapi mungkin satu kaedah alternatif untuk jadual hash adalah apa yang kita panggil indone a.
>> Semua yang indone adalah merupakan jenis tertentu pokok yang
mempunyai nilai-nilai yang pergi kepada nilai-nilai lain.
Jadi, daripada mempunyai binari pokok dalam erti kata bahawa hanya satu
Perkara yang boleh menunjuk kepada dua, anda boleh mempunyai mata satu perkara kepada ramai, banyak perkara.
Anda pada dasarnya mempunyai array di dalam yang anda simpan
petunjuk yang menunjukkan tatasusunan lain.
>> Jadi nod bagaimana kita akan menentukan indone a
ialah kita mahu mempunyai Boolean, c perkataan, bukan?
Jadi nod membolehkan Boolean seperti benar atau palsu,
pertama sekali di kepala pelbagai itu, adakah ini satu perkataan?
Kedua, anda mahu mempunyai petunjuk untuk apa sahaja yang lain daripada mereka berada.
Sebuah kompleks bit, abstrak bit, tetapi Saya akan menjelaskan apa yang segala cara.
>> Jadi di sini, di bahagian atas, jika anda mempunyai lokasi yang diisytiharkan sudah,
nod di mana anda perlu Boolean yang nilai yang disimpan di bahagian hadapan
yang memberitahu anda adalah ini perkataan?
Adakah ini bukan satu perkataan?
Dan kemudian anda mempunyai seluruh lokasi anda yang
sebenarnya menyimpan semua kemungkinan apa yang ia boleh.
Jadi, sebagai contoh, seperti di atas, anda mempunyai
perkara pertama yang berkata benar atau palsu, ya atau tidak, ini adalah perkataan.
>> Dan kemudian anda 0 melalui 26 huruf yang anda boleh menyimpan.
Jika saya mahu mencari di sini untuk kelawar, saya pergi ke bahagian atas
dan saya mencari B. Saya dapati B dalam saya pelbagai, dan saya tahu, OK, ialah B perkataan?
B bukanlah perkataan, jadi dengan itu Saya mesti menjaga carian.
Saya pergi dari B, dan saya melihat kepada penunjuk yang menunjuk ke arah B
dan saya melihat satu lagi pelbagai maklumat, struktur yang sama yang kita ada sebelum ini.
>> Dan sini-- oh, seterusnya surat di [didengar] adalah A.
Oleh itu, kita melihat di pelbagai itu.
Kami mencari nilai kelapan, dan kemudian kita melihat untuk melihat, oh,
hey, adalah bahawa perkataan, ialah B-A perkataan?
Ia bukan perkataan.
Kita mesti terus mencari.
>> Dan demikian maka kita melihat kepada mana penunjuk A mata,
dan ia menjurus kepada satu lagi cara di mana kita mempunyai lebih nilai disimpan.
Dan akhirnya, kita dapat B-A-T, yang merupakan satu perkataan.
Dan sebagainya pada masa akan datang anda melihat, anda akan
untuk mempunyai bahawa cek, ya, fungsi Boolean ini adalah benar.
Dan sebagainya dalam erti kata kita jenis yang mempunyai pokok dengan tatasusunan.
>> Sebab itu anda jenis boleh ke bawah.
Daripada hashing fungsi dan memberikan nilai dengan senarai bersambung,
anda hanya boleh melaksanakan indone yang mencari downwords.
Benar-benar, benar-benar rumit barangan.
Tidak mudah untuk berfikir tentang kerana saya seperti meludah begitu banyak struktur data daripada
pada anda, tetapi juga semua orang jenis memahami bagaimana logik ini berfungsi?
>> OK, sejuk.
Jadi B-A-T, dan kemudian anda akan mencari.
Masa depan anda akan untuk melihat, oh, hey, ia adalah benar,
dengan itu saya tahu ini mesti perkataan.
>> Perkara yang sama untuk zoo.
Jadi di sini adalah perkara yang betul sekarang, jika kita mahu mencari zoo, sekarang,
kini zoo bukan perkataan dalam kamus kami
kerana, seperti yang anda semua boleh lihat, tempat pertama yang kita ada Boolean yang
kembali benar adalah pada akhir zum.
Kami mempunyai Z-O-O-M.
>> Dan sebagainya di sini, kita tidak benar-benar mempunyai perkataan, zoo, dalam kamus kami
kerana kotak semak ini tidak dibendung.
Jadi komputer tidak tahu bahawa zoo adalah satu perkataan yang
kerana cara yang kita ada disimpannya, hanya zoom di sini
sebenarnya mempunyai nilai Boolean yang sudah menjadi kenyataan.
Jadi, jika kita mahu memasukkan perkataan, zoo, ke dalam kamus kita,
bagaimana kita akan pergi tentang melakukan perkara itu?
Apa yang kita perlu lakukan untuk memastikan kami komputer tahu bahawa Z-O-O adalah satu perkataan yang
dan bukan perkataan pertama adalah Z-O-O-M?
>> PENONTON: [didengar]
>> ANDI PENG: Tepat sekali, kita ingin memastikan bahawa ini
di sini, bahawa nilai Boolean adalah diperiksa bahawa itu benar.
Z-O-O, kemudian kita akan menyemak sama ada, jadi kita tahu, hey, zoo perkataan.
Saya akan memberitahu komputer bahawa itu perkataan yang begitu
bahawa apabila cek komputer, ia tahu bahawa zoo perkataan.
>> Kerana ingat semua data ini struktur, ia sangat mudah untuk kita
berkata, oh, kelawar yang perkataan.
Zoo yang perkataan.
Zoom adalah perkataan.
Tetapi apabila anda membina itu, komputer mempunyai idea.
>> Jadi, anda perlu memberitahu ia betul-betul pada titik ini adalah satu perkataan?
Pada peringkat bukankah perkataan?
Dan pada titik saya perlu kepada perkara-perkara mencari,
dan pada titik yang perlu saya pergi selepas ini?
Semua orang yang jelas itu?
Sejuk.
>> Dan demikian maka datang masalah bagaimana akan kita
pergi tentang memasukkan sesuatu yang sebenarnya tidak ada?
Jadi mari kita hanya mengatakan bahawa kita mahu memasukkan perkataan, mandi, ke indone kami.
Seperti yang anda semua boleh lihat seperti kini semua kita ada sekarang adalah B-A-T,
dan struktur data baru ini ada mempunyai satu pain yang
menunjuk kepada null kerana kita menganggap itu, oh, tidak ada kata-kata selepas B-A-T,
mengapa kita perlu menyimpan mempunyai perkara-perkara selepas T. yang
>> Tetapi masalah yang timbul jika kita adakah anda mahu mempunyai satu perkataan yang datang selepas
T-kanak.
Jika anda mempunyai mandi, anda berada akan mahu hak H.
Dan jadi cara kita akan berbuat demikian adalah kita akan mewujudkan nod yang berasingan.
Kami tidak memperuntukkan sebarang jumlah memori untuk pelbagai baru ini,
dan kita akan menyerahhakkan semula petunjuk.
>> Kita akan menyerahhakkan H, Pertama sekali, batal ini,
kita akan menyingkirkan.
Kita akan mempunyai ke bawah titik H.
Jika kita lihat H, kita mahu ia untuk pergi ke tempat lain.
>> Di sini, kita boleh memanggil satu ya.
Jika kita mencapai H selepas t, oh, maka kita tahu bahawa ini adalah perkataan.
Boolean akan kembali benar.
Semua orang yang jelas mengenai bagaimana yang berlaku?
OKAY.
>> Jadi pada asasnya, semua ini struktur data
yang kita telah pergi ke atas hari ini, saya telah pergi ke atas mereka benar-benar, benar-benar cepat
dan tidak masuk ke banyak terperinci, dan tidak apa-apa.
Sebaik sahaja anda memulakan main dengan itu, anda akan
mengesan di mana semua petunjuk adalah,
apa yang berlaku di dalam anda struktur data, dan sebagainya.
Mereka akan menjadi sangat berguna, dan ia terpulang kepada anda
seorang lelaki untuk benar-benar memikirkan bagaimana anda mahu untuk melaksanakan sesuatu.
>> Dan sebagainya pset4, sudah 5-- oh, itu adalah salah.
Pset5 adalah salah ejaan.
Seperti yang saya katakan sebelum ini, anda akan, sekali lagi, muat turun kod sumber dari kami.
Ada akan menjadi tiga utama perkara yang anda akan dapat memuat turun.
Anda akan memuat turun kamus, kers, dan teks.
>> Semua perkara-perkara yang boleh memuat kamus perkataan
yang kami mahu anda untuk memeriksa atau ujian maklumat
yang kami mahu anda untuk periksa ejaan.
Dan sebagainya kamus kami memberi anda akan
untuk memberikan kata-kata sebenar yang kita mahu anda menyimpan entah bagaimana dengan cara itulah
lebih cekap daripada array.
Dan kemudian teks-teks tersebut akan menjadi apa yang kita
meminta anda untuk semak ejaan memastikan semua perkataan terdapat kata-kata sebenar.
>> Dan sebagainya tiga blok program-program yang kami akan memberikan anda
dipanggil dictionary.c, dictionary.h dan speller.c.
Dan supaya semua dictionary.c tidak adalah apa yang anda diminta untuk dilaksanakan.
Ia memuatkan kata-kata.
Ia mengeja cek mereka, dan ia akan memastikan segala-galanya yang dimasukkan dengan betul.
>> diction.h hanya fail perpustakaan yang mengisytiharkan semua fungsi-fungsi itu.
Dan speller.c, kita akan memberi anda.
Anda tidak perlu mengubah suai apa-apa daripadanya.
Semua speller.c dilakukan adalah mengambil itu, beban itu, memeriksa kelajuan itu,
menguji penanda aras seperti bagaimana cepat anda mampu untuk melakukan sesuatu.
>> Ia ejaan a.
Hanya tidak kucar-kacir dengan itu, tetapi membuat bahawa anda memahami apa yang ia lakukan.
Kami menggunakan getrusage fungsi dipanggil bahawa menguji prestasi ejaan anda
pemeriksa.
Semua ia pada dasarnya menguji masa segala-galanya dalam kamus anda,
jadi pastikan anda memahaminya.
Berhati-hati untuk tidak kucar-kacir dengan atau perkara yang lain tidak akan berjalan dengan baik.
>> Dan sebahagian besar daripada cabaran ini adalah untuk anda semua untuk benar-benar mengubah suai dictionary.c.
Kami akan memberikan anda 140,000 kata-kata dalam kamus.
Kami akan memberikan anda teks fail yang mempunyai kata-kata,
dan kami mahu anda dapat menyusun mereka ke dalam jadual hash atau indone a
kerana apabila kami meminta anda untuk mengeja check-- bayangkan jika anda berada ejaan
memeriksa seperti Odyssey Homer.
Ia seperti, ujian besar yang besar ini.
>> Bayangkan jika setiap satu perkataan yang anda terpaksa mencari
melalui pelbagai 140000 nilai.
Yang akan mengambil selama-lamanya untuk mesin anda untuk menjalankan.
Sebab itu kita mahu menganjurkan kami data ke dalam struktur data yang lebih cekap
seperti jadual hash atau indone a.
Dan kemudian anda semua boleh jenis bila anda mencari akses
perkara yang lebih mudah dan lebih cepat.
>> Dan jadi berhati-hati untuk menyelesaikan pertembungan.
Anda akan mendapat sekumpulan daripada kata-kata yang bermula dengan A.
Anda akan mendapatkan kata-kata sekumpulan yang bermula dengan B. Sehingga anda
seorang lelaki bagaimana anda mahu untuk menyelesaikannya.
Mungkin ada lagi fungsi hash cekap
daripada hanya huruf pertama sesuatu, dan sebagainya itu terpulang kepada anda
lelaki untuk jenis melakukan apa sahaja yang anda mahu.
>> Mungkin anda mahu tambah semua huruf bersama-sama.
Mungkin anda mahu suka melakukan perkara-perkara yang pelik untuk mengambil kira bilangan huruf,
apa-apa sahajalah.
Sehingga anda semua bagaimana anda mahu lakukan.
Jika anda mahu lakukan jadual hash, jika anda ingin mencuba indone a, benar-benar terpulang kepada anda.
Aku akan menunjukkan kepada anda lebih awal daripada masa itu indone biasanya sedikit lebih sukar
hanya kerana ada banyak lebih banyak petua untuk mengesan.
Tetapi benar-benar terpulang kepada anda semua.
Ia jauh lebih cekap dalam kebanyakan kes.
Anda ingin benar-benar dapat mengekalkan mengesan semua petunjuk anda.
Suka melakukan perkara yang sama yang saya lakukan di sini.
Apabila anda cuba untuk memasukkan nilai-nilai ke dalam jadual hash atau memadam,
memastikan bahawa anda berada benar-benar mengesan
di mana segala-galanya adalah kerana ia benar-benar mudah untuk jika saya
cuba untuk memasukkan seperti perkataan, andy.
Mari kita katakan itu adalah satu perkataan yang benar, perkataan, andy,
ke dalam senarai gergasi A kata-kata.
>> Jika saya hanya berlaku menetapkannya semula yang salah penunjuk, oops,
hilanglah keseluruhan daripada yang lain dalam senarai dikaitkan saya.
Kini satu-satunya perkataan yang saya ada adalah andy, dan sekarang
semua perkataan lain dalam kamus telah hilang.
Dan supaya anda ingin memastikan anda mengesan semua petunjuk anda
atau lain anda akan mendapat masalah besar dalam kod anda.
Menarik perkara-perkara teliti langkah demi langkah.
Ia menjadikan ia lebih mudah untuk berfikir.
>> Dan akhir sekali, anda mahu dapat menguji prestasi anda program anda
di atas kapal besar.
Jika anda semua mengambil melihat CS50 sekarang,
kita ada apa yang dipanggil lembaga besar.
Ia adalah kira-kira skor yang paling cepat mengeja kali mendaftar di semua CS50
sekarang, saya rasa bahagian atas seperti 10 kali saya berfikir lapan daripada mereka adalah kakitangan.
Kami benar-benar mahu anda semua untuk mengalahkan kita.
>> Semua kita telah cuba untuk melaksanakan Kod yang paling cepat yang mungkin.
Kami mahu anda semua untuk cuba untuk mencabar kami dan melaksanakan lebih cepat daripada kita semua
boleh.
Dan sebagainya ini adalah benar-benar kali pertama kita
meminta anda semua untuk melakukan Serangga yang anda benar-benar boleh lakukan dalam apa jua kaedah
awak mahu.
>> Saya selalu berkata, ini adalah lebih mirip kepada penyelesaian yang sebenar, bukan?
Saya berkata, hey, saya memerlukan anda untuk melakukan ini.
Membina satu program yang melakukan ini untuk saya.
Adakah ia bagaimanapun anda mahu.
Saya hanya tahu bahawa saya mahu berpuasa.
Itulah cabaran anda untuk minggu ini.
Anda semua, kita akan untuk memberikan anda tugas.
Kami akan memberikan anda satu cabaran.
Dan kemudian ia terpulang kepada anda semua untuk benar-benar hanya memikirkan
apa yang paling cepat dan paling cara yang berkesan untuk melaksanakan ini.
Ya?
>> PENONTON: Adakah kita dibenarkan jika mahukan untuk menyelidik cara-cara yang lebih cepat
untuk melakukan jadual hash dalam talian, yang boleh kita lakukan itu dan memetik kod orang lain?
ANDI PENG: Ya, betul-betul halus.
Jadi jika anda semua membaca spec, ada garis
dalam spesifikasi yang mengatakan bahawa anda seorang lelaki benar-benar bebas untuk menyelidik hash
fungsi pada apakah beberapa fungsi hash lebih cepat
untuk menjalankan sesuatu melalui sebagai Selama anda memetik kod itu.
Jadi sesetengah orang telah pun digambarkan cara yang cepat
menjalankan dam ejaan, puasa cara untuk menyimpan maklumat.
Benar-benar terpulang kepada anda semua jika anda mahu hanya mengambil itu, bukan?
Pastikan anda memetik.
Cabaran di sini benar-benar bahawa kita cuba untuk menguji
adalah memastikan bahawa anda tahu jalan di sekitar petunjuk.
Sejauh yang anda melaksanakan fungsi hash sebenar
dan datang dengan seperti matematik untuk berbuat demikian,
anda semua boleh menyelidik apa sahaja kaedah dalam talian anda semua mahu.
Ya?
>> PENONTON: Bolehkah kita hanya memetik dengan menggunakan [didengar]?
>> ANDI PENG: Ya.
Anda boleh adil, dalam komen anda, anda boleh memetik seperti, oh,
diambil dari bla, bla, yada, fungsi hash.
Sesiapa yang mempunyai sebarang soalan?
Kami benar-benar mara melalui bahagian hari ini.
Saya akan duduk di menjawab soalan-soalan juga.
>> Juga, seperti yang saya katakan, pejabat waktu malam ini dan esok.
Spec minggu ini adalah benar-benar sangat mudah dan super pendek untuk dibaca.
Saya cadangkan mengambil melihat, hanya membaca keseluruhan daripadanya.
>> Dan Zamyla sebenarnya berjalan anda melalui setiap fungsi
anda perlu untuk melaksanakan, dan sebagainya itu sangat, sangat jelas bagaimana untuk melakukan segala-galanya.
Hanya untuk memastikan anda berada mengesan petunjuk.
Ini adalah pset sangat mencabar.
>> Ia tidak mencabar kerana seperti, oh, konsepnya ialah banyak lagi
sukar, atau anda perlu belajar begitu banyak sintaks baru cara
yang anda telah lakukan untuk pset terakhir.
Serangga ini adalah sukar kerana terdapat begitu banyak petunjuk,
dan kemudian ia adalah sangat, sangat mudah sekali anda mempunyai bug dalam kod anda tidak dapat
untuk mencari di mana bug yang.
>> Dan begitu lengkap dan iman gelita di dalam kamu lelaki untuk dapat mengalahkan kami [didengar]
ejaan.
Saya sebenarnya tidak mempunyai mana-mana lombong bertulis lagi, tetapi saya kira-kira untuk menulis saya.
Oleh itu, sambil anda menulis anda, saya akan menulis saya.
Saya akan cuba untuk membuat saya lebih cepat daripada anda.
Kami akan melihat siapa yang mempunyai salah satu yang paling cepat.
>> Dan yeah, saya akan melihat semua anda semua di sini pada Selasa.
Saya akan berjalan sejenis seperti bengkel pset.
Kesemua seksyen ini minggu adalah bengkel Serangga,
supaya anda lelaki itu mempunyai banyak peluang tolong, waktu pejabat seperti biasa,
dan saya benar-benar mengalu-alukan membaca semua kod lelaki anda.
Saya mempunyai kuiz di sini jika anda lelaki mahu datang mendapatkan mereka.
Itu sahaja.