>> JASON Hirschhorn: Selamat datang semua orang kepada Seksyen Tujuh.
Kita berada dalam minggu tujuh kursus.
Dan ini Khamis akan datang adalah Halloween jadi saya
berpakaian seperti labu a.
Saya tidak dapat membengkok dan memakai kasut saya, jadi itu sebabnya saya
hanya memakai sarung kaki.
Saya juga tidak memakai apa-apa di bawah ini, jadi saya tidak boleh mengambil ia di luar jika ia
mengganggu kepada anda.
Saya memohon maaf terlebih dahulu untuk itu.
Anda tidak perlu untuk membayangkan apa yang berlaku.
Saya pakai peninju.
Jadi itu semua baik.
>> Saya mempunyai cerita yang lebih panjang tentang mengapa saya berpakaian seperti labu, tetapi saya akan
kecuali bahawa untuk masa lain dalam seksyen ini kerana saya ingin memulakan.
Kami mempunyai banyak perkara yang menarik untuk pergi ke minggu ini.
Kebanyakan mereka adalah berkaitan secara langsung kepada ini set masalah minggu ini, salah ejaan.
Kita akan pergi lebih dikaitkan senarai dan jadual hash
untuk seluruh bahagian itu.
Saya meletakkan senarai ini setiap minggu, satu senarai sumber bagi anda untuk membantu anda dengan
bahan di kursus ini.
Jika rugi atau jika sedang mencari beberapa maklumat lanjut, lihat salah satu
sumber-sumber ini.
>> Sekali lagi, pset6 adalah salah ejaan, Serangga minggu ini.
Dan ia juga menggalakkan anda, dan saya menggalakkan anda, untuk menggunakan beberapa lain
sumber khusus untuk Serangga ini.
Khususnya, tiga saya telah disenaraikan di skrin -
Pra-Pemasangan, yang kita telah biasa dengan dan telah menggunakan untuk seketika kini, adalah
akan sangat membantu minggu ini.
Jadi saya meletakkan bahawa di sini.
Tetapi apabila anda bekerja dengan C, anda perlu sentiasa menggunakan Pra-Pemasangan untuk
debug program anda.
Minggu ini juga valgrind.
Adakah sesiapa tahu apa valgrind tidak?
>> PENONTON: Ia memeriksa kebocoran memori?
>> JASON Hirschhorn: Valgrind cek kebocoran memori.
Jadi, jika anda sesuatu malloc dalam anda program, anda meminta untuk ingatan.
Pada akhir program anda, anda perlu untuk menulis percuma pada semua yang anda telah
malloced untuk memberi ingatan belakang.
Jika anda tidak menulis percuma pada akhir dan program anda datang membuat kesimpulan,
segala-galanya akan secara automatik dibebaskan.
Dan bagi program kecil, ia tidak yang besar perjanjian.
Tetapi jika anda menulis berjalan yang lebih lama program yang tidak berhenti,
semestinya, dalam beberapa minit atau beberapa saat, maka memori bocor
boleh menjadi satu perjanjian yang besar.
>> Jadi untuk pset6, jangkaan ialah anda akan mempunyai kebocoran memori sifar dengan
program anda.
Untuk menyemak kebocoran memori, valgrind menjalankan dan ia akan memberikan anda beberapa bagus
output membiarkan anda tahu sama ada atau tidak semuanya percuma.
Kami akan mengamalkan dengannya kemudian hari ini, mudah-mudahan.
>> Akhirnya, arahan beza.
Anda digunakan sesuatu yang serupa dengan ia dalam pset5 dengan alat mengintip itu.
Dibenarkan anda untuk melihat bahagian dalam.
Anda juga digunakan beza juga, bagi setiap masalah yang ditetapkan spec.
Tetapi dalam membolehkan anda untuk membandingkan dua fail.
Anda boleh membandingkan fail bitmap dan header info penyelesaian kakitangan dan
penyelesaian anda di pset5 jika anda memilih untuk menggunakannya.
Beza akan membolehkan anda untuk berbuat demikian, juga.
Anda boleh bandingkan jawapan yang betul bagi masalah minggu ini bersedia untuk jawapan anda
dan lihat jika ia garisan atas atau lihat di mana kesilapan yang.
>> Jadi mereka adalah tiga alat yang baik yang anda perlu menggunakan untuk minggu ini, dan
pasti menyemak program anda dengan ketiga-tiga alat
sebelum membelok ia masuk
Sekali lagi, seperti yang telah saya sebutkan setiap minggu, jika anda mempunyai sebarang maklum balas bagi saya - kedua-dua
positif dan membina -
berasa bebas untuk menuju ke laman web ini di bahagian bawah slaid ini
dan input di sana.
Saya benar-benar menghargai apa-apa dan semua maklum balas.
Dan jika anda memberikan saya perkara-perkara tertentu yang Yang boleh saya lakukan untuk memperbaiki atau bahawa saya
dengan baik yang anda ingin saya untuk meneruskan, saya mengambil bahawa ke jantung dan
benar-benar berusaha untuk mendengar untuk maklum balas anda.
Saya tidak boleh berjanji saya akan lakukan segala-galanya, walaupun, seperti memakai
labu pakaian setiap minggu.
>> Jadi kita akan membelanjakan sebahagian besar daripada seksyen, seperti yang saya katakan, bercakap tentang
senarai dikaitkan dan jadual hash, yang akan secara langsung berkaitan dengan
masalah minggu ini dilaporkan.
Senarai Berkaitan kita akan pergi ke agak cepat kerana kita telah menghabiskan sedikit saksama
masa akan lebih dalam seksyen.
Dan dengan itu kita akan mendapat terus ke pengekodan masalah untuk senarai berkaitan.
Dan kemudian akhirnya kami akan bercakap mengenai hash meja dan bagaimana ia terpakai bagi ini
masalah minggu ini ditetapkan.
>> Anda telah melihat kod ini sebelum ini.
Ini adalah struct, dan ia menentukan sesuatu yang baru yang dikenali sebagai nod.
Dan di dalam nod terdapat integer di sini dan terdapat penunjuk kepada
nod yang lain.
Kami telah melihat ini sebelum ini.
Ini telah datang untuk beberapa minggu sekarang.
Ia menggabungkan petunjuk, yang kita telah bekerja dengan, dan structs, yang membolehkan
kita untuk menggabungkan dua yang berbeza sesuatu ke dalam satu jenis data.
>> Ada banyak berlaku pada skrin.
Tetapi semua itu sepatutnya menjadi akrab dengan anda.
Pada baris pertama, kami mengisytiharkan nod baru.
Dan kemudian di dalam nod baru, saya menetapkan integer dalam nod yang kepada satu.
Kita lihat pada baris berikutnya saya melakukan printf arahan, tetapi saya telah dikelabukan
arahan printf kerana yang benar-benar bahagian penting adalah baris ini di sini -
new_node.n.
Apakah dot min?
>> PENONTON: Pergi ke nod dan menilai nilai n untuk itu.
>> JASON Hirschhorn: Itu betul-betul betul.
Dot bermakna mengakses n bahagian nod baru ini.
Ini sejajar seterusnya melakukan apa?
Michael.
>> PENONTON: Ia mewujudkan nod yang lain yang akan menunjukkan kepada nod baru.
>> JASON Hirschhorn: Jadi ia tidak mewujudkan nod baru.
Ia menciptakan apa yang?
>> PENONTON: penunjuk A.
>> JASON Hirschhorn: Satu penunjuk kepada nod, seperti yang ditunjukkan oleh nod * ini di sini.
Jadi ia mewujudkan penunjuk kepada nod.
Dan yang node ia menunjuk kepada, Michael?
>> PENONTON: Nod Baru?
>> JASON Hirschhorn: Nod Baru.
Dan ia menunjuk sana kerana kita telah diberikan ia alamat nod baru.
Dan kini di baris ini kita lihat dua cara yang berbeza
menyatakan perkara yang sama.
Dan saya mahu untuk menunjukkan bagaimana dua perkara yang sama.
Dalam baris pertama, kita dereference penunjuk.
Jadi kita pergi ke nod.
Itulah yang bintang ini bermakna.
Kami telah melihat yang sebelum ini dengan petunjuk.
Pergi dengan node itu.
Itu di dalam kurungan.
Dan kemudian mengakses melalui pengendali titik unsur n nod itu.
>> Jadi yang yang mengambil sintaks kita lihat di sini dan kini
menggunakannya dengan penunjuk.
Sudah tentu, ia mendapat jenis sibuk jika anda menulis mereka kurungan -
bahawa bintang dan dot itu.
Ia mendapat sedikit sibuk.
Oleh itu, kita minta gula sintaktik.
Dan garis ini di sini -
ptr_node-> n.
Yang melakukan perkara yang tepat sama.
Jadi kedua-dua baris kod adalah setaraf dan akan melakukan
perkara sama.
>> Tetapi saya mahu menunjukkan mereka keluar sebelum kita pergi mana-mana lagi supaya anda memahami
yang benar-benar perkara ini di sini adalah hanya gula sintaksis untuk penyahrujukan
penunjuk dan kemudian akan n bahagian daripada struct itu.
Apa-apa soalan mengenai slaid ini?
OK.
>> Jadi, kita akan melalui pasangan operasi yang anda boleh lakukan pada
senarai berkaitan.
Senarai dikaitkan, ingat, adalah satu siri nod yang menunjuk kepada satu sama lain.
Dan kita biasanya bermula dengan penunjuk dipanggil kepala, secara amnya, yang menunjuk kepada
perkara pertama dalam senarai.
Jadi pada baris pertama di sini, kita mempunyai L asal kami pertama.
Jadi perkara yang boleh anda fikirkan - ini teks di sini yang boleh anda fikirkan sebagai
hanya penunjuk yang kami disimpan di suatu tempat yang titik
kepada elemen pertama.
Dan dalam senarai ini dikaitkan kami mempunyai empat nod.
Setiap nod adalah kotak besar.
Kotak yang lebih besar di dalam besar peti adalah bahagian integer.
Dan maka kita mempunyai sebahagian penunjuk.
>> Kotak-kotak tidak dilukis mengikut skala kerana berapa besar adalah
integer dalam bait?
Bagaimana besar sekarang?
Empat.
Dan bagaimana besar adalah penunjuk?
Empat.
Jadi benar-benar, jika kita untuk menarik ini untuk menskalakan kedua kotak
akan menjadi saiz yang sama.
Dalam kes ini, kita mahu untuk memasukkan sesuatu ke dalam senarai yang dipautkan.
Jadi anda boleh melihat ke bawah di sini kita memasukkan lima Kami merentasi melalui
senarai bersambung, mencari di mana lima pergi, dan kemudian memasukkannya.
>> Mari kita memecahkan itu dan pergi sedikit lebih perlahan.
Saya akan menunjukkan kepada lembaga.
Jadi kita mempunyai nod kita lima yang kami telah diwujudkan dalam mallocs.
Mengapa semua orang ketawa?
Hanya bergurau.
OK.
Jadi kami malloced lima.
Kami telah mencipta nod ini di tempat lain.
Kita ada bersedia untuk pergi.
Kami bermula di hadapan senarai kami dengan dua.
Dan kita mahu memasukkan dengan cara yang disusun.
>> Jadi, jika kita melihat dua dan kami mahu meletakkan dalam lima, apa yang kita lakukan apabila kita melihat
sesuatu yang kurang daripada kita?
Apa?
Kami mahu memasukkan ke dalam lima ini senarai bersambung, menyimpan ia disusun.
Kita melihat nombor dua.
Jadi apa yang kita lakukan?
Marcus?
>> PENONTON: Hubungi penunjuk ke nod seterusnya.
>> JASON Hirschhorn: Dan mengapa kita pergi ke yang berikutnya?
>> PENONTON: Kerana ia adalah nod seterusnya dalam senarai.
Dan kita hanya tahu lokasi yang lain.
>> JASON Hirschhorn: Dan lima adalah lebih besar dari seorang, khususnya.
Kerana kita mahu untuk memastikan ia disusun.
Jadi lima adalah lebih besar daripada dua.
Oleh itu, kita beralih kepada yang seterusnya.
Dan sekarang kita mencapai empat.
Dan apa yang berlaku apabila kita mencapai empat?
>> Lima adalah lebih besar daripada empat.
Oleh itu, kita teruskan.
Dan sekarang kita berada di enam.
Dan apa yang kita lihat di enam?
Ya, Carlos?
>> PENONTON: Enam adalah lebih besar daripada lima.
>> JASON Hirschhorn: Enam adalah lebih besar daripada lima.
Supaya di mana kita mahu untuk memasukkan lima.
Walau bagaimanapun, perlu diingat bahawa jika kita hanya mempunyai satu penunjuk di sini -
ini adalah penunjuk tambahan kami itulah menyeberangi melalui senarai.
Dan kita menunjuk kepada enam.
Kita telah kehilangan mengesan apa datang sebelum enam.
Jadi, jika kita mahu untuk memasukkan sesuatu ke dalam senarai ini menyimpan ia disusun, kita
mungkin perlu berapa banyak petunjuk?
>> PENONTON: Dua.
>> JASON HIRSCHORN: Dua.
Satu untuk mengesan arus satu dan satu untuk mengesan
yang sebelumnya.
Ini adalah hanya senarai secara tunggal dikaitkan.
Ia hanya pergi satu arah.
Jika kita mempunyai senarai duanya adalah terpakai dikaitkan, di mana semuanya menunjuk kepada perkara yang
selepas ia dan perkara yang di hadapannya, maka kita tidak perlu untuk berbuat demikian.
Tetapi dalam kes ini kita tidak mahu kehilangan mengesan apa mendahului kami dalam kes
kita perlu memasukkan lima tempat di tengah-tengah.
Katakanlah kita telah memasukkan sembilan.
Apa yang akan berlaku apabila kami mendapat lapan?
>> PENONTON: Anda harus mendapatkan mata null.
Sebaliknya mempunyai titik null anda dapati untuk menambah satu elemen dan kemudian mempunyai
ia menunjukkan kepada sembilan.
>> JASON HIRSCHORN: Tepat sekali.
Oleh itu, kita mendapat lapan.
Kami sampai ke akhir senarai kerana ini menunjuk ke nol.
Dan kini, bukannya mempunyai ia menunjukkan null kita ada menunjukkan nod baru kami.
Dan kami menetapkan penunjuk di nod baru kami untuk nol.
Adakah sesiapa mempunyai apa-apa soalan kira-kira memasukkan?
Bagaimana jika saya tidak mengambil berat tentang menjaga senarai disusun?
>> PENONTON: Stick ia di bermula atau akhir.
>> JASON HIRSCHORN: Stick ia di permulaan atau akhir.
Yang mana satu patut kita buat?
Bobby?
Mengapa akhir?
>> PENONTON: Kerana awal sudah diisi.
>> JASON HIRSCHORN: OK.
Permulaan sudah diisi.
Siapa yang mahu untuk berhujah terhadap Bobby.
Marcus.
>> PENONTON: Baik anda mungkin mahu melekat pada permulaan kerana
sebaliknya jika anda meletakkan ia di Akhirnya anda akan perlu
merentasi seluruh senarai.
>> JASON HIRSCHORN: Tepat sekali.
Jadi, jika kita berfikir tentang runtime, yang runtime memasukkan di hujung
akan n, saiz ini.
Apakah O runtime besar memasukkan pada permulaan?
Masa yang sama.
Jadi, jika anda tidak mengambil berat tentang menjaga sesuatu yang disusun, lebih baik untuk hanya
memasukkan pada awal senarai ini.
Dan yang boleh dilakukan dalam masa yang sama.
>> OK.
Operasi akan datang mencari, yang lain - kami telah diungkap ini sebagai carian.
Tetapi kita akan melihat melalui senarai bersambung untuk beberapa objek.
Anda semua telah melihat kod untuk mencari sebelum di kuliah.
Tetapi kita semacam hanya ia lakukan dengan memasukkan, atau sekurang-kurangnya memasukkan
sesuatu yang disusun.
Anda melihat melalui, pergi nod dengan nod, sehingga anda boleh mendapatkan nombor yang anda
cari.
Apakah yang akan berlaku jika anda mencapai akhir senarai?
Katakanlah saya mencari sembilan dan saya sampai ke akhir senarai.
Apa yang kami lakukan?
>> PENONTON: Kembali palsu?
>> JASON HIRSCHORN: Kembali palsu.
Kami tidak menemuinya.
Jika anda sampai ke akhir senarai dan anda tidak mencari nombor anda
cari, ia bukan di sana.
Apa-apa soalan mengenai mencari?
Jika ini adalah senarai disusun, apa yang akan berbeza untuk mencari kami?
Yeah.
>> PENONTON: Ia akan mencari nilai yang pertama itulah yang lebih besar daripada yang
anda sedang mencari dan kemudian kembali palsu.
>> JASON HIRSCHORN: Tepat sekali.
Jadi, jika ia adalah senarai disusun, jika kita dapat sesuatu yang lebih besar daripada apa yang
kita cari, kita tidak perlu menyimpan pergi ke akhir senarai.
Kami boleh pada ketika itu pulangan palsu kerana kita tidak akan menemuinya.
Persoalannya kini, kita telah berbincang mengenai menjaga senarai dikaitkan disusun,
menjaga mereka Unsorted.
Itu akan menjadi sesuatu yang anda mungkin akan perlu berfikir tentang
apabila masalah pengekodan meletakkan lima jika anda memilih jadual hash dengan berasingan
pendekatan chaining, yang kita akan bercakap tentang kemudian.
>> Tetapi adakah ia berbaloi untuk menyimpan senarai disusun dan kemudian dapat mungkin mempunyai
carian lebih cepat?
Atau adakah ia lebih baik untuk cepat memasukkan sesuatu dalam runtime berterusan tetapi
mempunyai lagi mencari?
Itulah tradeoff hak sana yang anda mendapatkan untuk memutuskan apa yang lebih sesuai
untuk masalah khusus anda.
Dan tidak semestinya satu jawapan-benar betul.
Tetapi ia sudah tentu keputusan anda mendapat untuk membuat, dan mungkin baik untuk mempertahankan
bahawa dalam, katakan, komen atau dua mengapa anda memilih berbanding dengan yang lain.
>> Akhir sekali, memotong.
Kami telah melihat memotong.
Ini serupa dengan mencari.
Kami mencari elemen.
Katakanlah kita sedang cuba untuk memadamkan enam.
Oleh itu, kita mendapati enam di sini.
Perkara yang kita perlu untuk memastikan kita lakukan ialah bahawa apa sahaja yang menunjuk ke
enam - seperti yang kita lihat dalam langkah dua turun di sini -
apa sahaja yang menunjuk kepada enam keperluan untuk skip enam sekarang dan ditukar kepada
apa sahaja enam orang menunjuk ke.
Kita tidak mahu yang pernah anak yatim seluruh senarai kami dengan melupakan untuk menetapkan bahawa
penunjuk sebelumnya.
Dan kemudian kadang-kadang, bergantung tentang program ini, mereka akan hanya
memadam nod ini sepenuhnya.
Kadang-kadang anda akan mahu kembali nilai yang di nod ini.
Jadi itu bagaimana memotong kerja-kerja.
Soalan mengenai memadam?
>> PENONTON: Jadi, jika anda akan memadam ia, akan anda hanya menggunakan percuma kerana
mungkin ia malloced?
>> JASON HIRSCHORN: Jika anda mahu untuk membebaskan sesuatu yang betul-betul betul dan anda
malloced ia.
Katakanlah kita mahu kembali nilai ini.
Kita mungkin kembali enam dan kemudian bebas nod ini dan panggilan percuma di atasnya.
Atau kita mungkin akan memanggil percuma pertama dan kemudian kembali enam.
>> OK.
Jadi mari kita beralih kepada amalan pengkodan.
Kami akan memberi kod kepada tiga fungsi.
Yang pertama dipanggil insert_node.
Jadi anda mempunyai kod yang saya melalui e-mel anda, dan jika anda menonton ini kemudian
anda boleh mengakses kod di linked.c di laman web CS50 itu.
Tetapi dalam linked.c, ada beberapa kod rangka yang sudah
telah ditulis untuk anda.
Dan kemudian ada beberapa fungsi anda perlu untuk menulis.
>> Pertama kita akan menulis insert_node.
Dan apa yang tidak insert_node Adakah memasukkan integer.
Dan anda memberikan integer ke dalam senarai berpaut.
Dan khususnya, anda perlu untuk menyimpan senarai disusun
dari kecik hingga besar.
Juga, anda tidak mahu memasukkan apa-apa salinan.
Akhir sekali, seperti yang anda lihat insert_node kembali bool a.
Jadi anda sepatutnya membenarkan pengguna yang tahu sama ada atau tidak memasukkan itu
berjaya dengan mengembalikan benar atau palsu.
Pada akhir program ini -
dan untuk peringkat ini anda tidak perlu bimbang tentang membebaskan apa-apa.
Jadi semua yang anda lakukan adalah mengambil integer dan memasukkan ke dalam senarai.
>> Itulah apa yang saya meminta anda lakukan sekarang.
Sekali lagi, dalam linked.c, yang anda semua ada, adalah kod tulang.
Dan anda akan melihat ke arah bahagian bawah fungsi akuan sampel.
Walau bagaimanapun, sebelum pergi ke pengekodan ia dalam C, saya sangat menggalakkan anda untuk pergi
melalui langkah-langkah kita telah mengamalkan setiap minggu.
Kami telah melalui gambar ini.
Jadi, anda perlu mempunyai sedikit pemahaman bagaimana ini berfungsi.
Tetapi saya akan menggalakkan anda untuk menulis beberapa kod pseudo sebelum menyelam masuk
Dan kita akan pergi ke atas pseudokod sebagai satu kumpulan.
Dan kemudian sekali anda tulis anda kod pseudo, dan sebaik sahaja kami telah menulis kami
pseudokod sebagai satu kumpulan, anda boleh pergi ke pengekodan dalam C.
>> Sebagai ekor, fungsi insert_node mungkin adalah trickiest
tiga kita akan menulis kerana saya menambah beberapa kekangan tambahan untuk
pengaturcaraan anda, khususnya yang anda tidak akan memasukkan apa-apa
salinan dan bahawa senarai harus kekal disusun.
Jadi ini adalah satu program bukan remeh yang perlu anda kod.
Dan mengapa kamu tidak mengambil 5-7 minit hanya untuk bekerja di
kod pseudo dan kod.
Dan kemudian kita akan mula akan sebagai satu kumpulan.
Sekali lagi, jika anda mempunyai sebarang soalan hanya mengangkat tangan anda dan saya akan datang sekitar.
.
>> Kami juga pada amnya melakukan ini -
atau saya tidak tegas mengatakan anda boleh bekerja dengan orang.
Tetapi jelas, saya sangat menggalakkan anda, jika anda mempunyai soalan, untuk meminta
jiran duduk di sebelah anda atau bekerja dengan seseorang
lain jika anda mahu.
Ini tidak perlu menjadi individu aktiviti senyap.
>> Mari kita mulakan dengan menulis beberapa kod pseudo di papan.
Yang boleh memberikan saya baris pertama kod pseudo untuk program ini?
Bagi fungsi ini, dan bukan - insert_node.
Alden?
>> PENONTON: Jadi perkara pertama yang saya lakukan ialah mewujudkan penunjuk baru kepada nod dan saya
dimulakan ia menunjuk ke yang sama perkara yang senarai adalah menunjuk ke.
>> JASON HIRSCHORN: OK.
Jadi anda mewujudkan penunjuk baru ke dalam senarai, tidak nod.
>> PENONTON: Betul.
Yeah.
>> JASON HIRSCHORN: OK.
Dan kemudian apa yang kita mahu lakukan?
Apakah selepas itu?
Bagaimana pula nod?
Kami tidak mempunyai satu nod.
Kita hanya perlu nilai.
Jika kita mahu memasukkan nod, apa yang kita perlu lakukan pertama sebelum kita juga boleh
berfikir tentang memasukkan ia?
>> PENONTON: Oh, maaf.
kita perlu malloc ruang untuk satu nod.
>> JASON HIRSCHORN: Cemerlang.
Mari kita lakukan -
OK.
Tidak boleh mencapai tinggi itu.
OK.
Kita akan turun ke bawah, dan kemudian kita menggunakan dua tiang.
Saya tidak boleh pergi yang -
OK.
Buat nod baru.
Anda boleh membuat penunjuk lain untuk menyenaraikan atau anda hanya boleh menggunakan senarai yang wujud.
Anda tidak benar-benar perlu untuk berbuat demikian.
>> Oleh itu, kita mewujudkan nod baru.
Besar.
Itulah apa yang kita lakukan pertama.
Apa yang akan datang?
>> PENONTON: Tunggu.
Sekiranya kita mewujudkan nod baru sekarang atau kita perlu menunggu untuk memastikan bahawa
tidak ada salinan nod dalam senarai itu sebelum kita menciptakannya?
>> JASON HIRSCHORN: Soalan yang baik.
Mari kita berpegang bahawa untuk masa lain kerana majoriti masa kita akan mewujudkan
nod baru.
Oleh itu, kita akan memastikan bahawa di sini.
Tetapi itu adalah satu soalan yang baik.
Jika kita menciptakannya dan kita dapati salinan, apa perlu
kita lakukan sebelum kembali?
>> PENONTON: Percuma ia.
>> JASON HIRSCHORN: Yeah.
Mungkin membebaskannya.
OK.
Apa yang kami lakukan selepas kami mewujudkan nod baru?
Annie?
>> PENONTON: Kami meletakkan nombor dalam nod?
>> JASON HIRSCHORN: Tepat sekali.
Kami meletakkan nombor - kami malloc ruang.
Saya akan meninggalkan bahawa semua sebagai satu baris.
Tetapi anda betul.
Kami malloc ruang, dan kemudian kita meletakkan nombor masuk
Kami juga boleh menetapkan penunjuk sebahagian daripadanya untuk nol.
Itu betul-betul betul.
Dan kemudian bagaimana pula selepas itu?
Kami menarik gambar ini di atas kapal.
Jadi apa yang kita lakukan?
>> PENONTON: Kita melalui senarai.
>> JASON HIRSCHORN: Pergi melalui senarai.
OK.
Dan apa yang kita periksa di setiap nod.
Kurt, apa yang kita lihat untuk di setiap nod?
>> PENONTON: Lihat sama ada nilai n nod yang lebih besar daripada nilai n
nod kami.
>> JASON HIRSCHORN: OK.
Saya akan lakukan -
yeah, OK.
Jadi ia n -
Saya akan mengatakan jika nilai yang lebih besar daripada nod ini, maka apa yang kita lakukan?
>> PENONTON: Nah, maka kita memasukkan perkara yang betul sebelum itu.
>> JASON HIRSCHORN: OK.
Jadi, jika ia lebih besar daripada ini, maka kita mahu masukkan.
Tetapi kita mahu untuk memasukkan dengan betul sebelum kerana kita juga perlu menjadi
mengesan, maka, daripada apa yang sebelum ini.
Jadi memasukkan sebelum ini.
Oleh itu, kita mungkin terlepas sesuatu sebelum ini.
Kita mungkin perlu menjaga menjejaki apa yang berlaku.
Tetapi kami akan kembali di sana.
Jadi apa nilai kurang daripada?
Kurt, apa yang kita lakukan jika nilai adalah kurang daripada?
>> PENONTON: Kemudian anda hanya menyimpan pergi melainkan jika ia yang terakhir.
>> JASON HIRSCHORN: Saya suka itu.
Oleh itu, pergilah ke nod seterusnya.
Melainkan jika ia yang terakhir -
kita mungkin tertanya-memeriksa bahawa dalam terma syarat.
Tetapi yeah, nod akan datang.
Dan itu terlalu rendah, jadi kita akan bergerak di sini.
Tetapi jika -
boleh semua orang melihat perkara ini?
Jika kita sama apa yang kita lakukan?
Jika nilai yang kami cuba untuk memasukkan adalah sama dengan nilai ini nod ini?
Yeah?
>> PENONTON: [didengar].
>> JASON HIRSCHORN: Yeah.
Memandangkan ini -
Marcus yang tepat.
Kita boleh mungkin dilakukan sesuatu yang berbeza.
Tetapi memandangkan kita telah menciptanya, di sini kita harus membebaskan dan kemudian kembali.
Oh lelaki.
Adakah itu lebih baik?
Bagaimana bahawa?
OK.
Percuma dan kemudian apa yang kita kembali, [didengar]?
OK.
Adakah kita hilang apa-apa?
Jadi di mana kita mengesan nod sebelumnya?
>> PENONTON: Saya fikir ia akan pergi selepas mewujudkan nod baru.
>> JASON HIRSCHORN: OK.
Jadi pada mulanya kita akan mungkin -
yeah, kita boleh membuat penunjuk kepada yang baru nod, seperti penunjuk nod sebelumnya dan
penunjuk nod semasa.
Jadi mari kita memasukkan bahawa di sini.
Membuat semasa dan sebelumnya petunjuk untuk nod.
Tetapi apabila kita menyesuaikan mereka petunjuk?
Di mana kita melakukannya dalam kod?
Jeff?
>> PENONTON: - syarat nilai?
>> JASON HIRSCHORN: Yang satu dalam tertentu?
>> PENONTON: Saya hanya keliru.
Jika nilai adalah lebih besar daripada nod ini, tidak bermakna bahawa anda mahu pergi
ke nod seterusnya?
>> JASON Hirschhorn: Jadi jika nilai kami adalah lebih besar daripada nilai nod ini.
>> PENONTON: Ya, maka anda akan mahu pergi lebih jauh ke bawah garisan, bukan?
>> JASON Hirschhorn: Betul.
Maka itu kita tidak memasukkan di sini.
Jika nilai adalah kurang daripada nod ini, maka kita pergi ke nod seterusnya - atau maka kita
memasukkan sebelum ini.
>> PENONTON: Tunggu, yang ini nod dan yang nilai?
>> JASON Hirschhorn: Soalan yang baik.
Nilai definisi fungsi ini inilah yang kita diberikan.
Jadi nilai adalah nombor kami diberikan.
Jadi, jika nilainya adalah kurang daripada ini nod, kita memerlukan masa untuk memasukkan.
Jika nilai adalah lebih besar daripada nod ini, kita pergi ke nod seterusnya.
Dan kembali kepada soalan asal, walaupun, di mana -
>> PENONTON: Jika nilai adalah lebih besar daripada nod ini.
>> JASON Hirschhorn: Dan sebagainya apa yang kita lakukan di sini?
Manis.
Itu betul.
Saya hanya akan menulis petunjuk kemas kini.
Tetapi ya, dengan satu semasa anda akan mengemas kini kepada
menunjuk kepada yang seterusnya.
Apa-apa lagi kita hilang?
Jadi saya akan menaip ini kod ke dalam gedit.
Dan semasa saya melakukan ini, anda boleh mempunyai pasangan minit untuk bekerja pada pengekodan
ini di C.
>> Jadi saya mempunyai input kod pseudo yang.
Nota ringkas sebelum kita bermula.
Kita mungkin tidak dapat sepenuhnya selesai ini dalam semua
tiga daripada fungsi-fungsi ini.
Terdapat penyelesaian yang betul kepada mereka bahawa saya akan menghantar e-mel kepada anda semua
selepas seksyen, dan ia akan dipaparkan di CS50.net.
Jadi, saya tidak menggalakkan anda untuk pergi melihat bahagian.
Saya menggalakkan anda untuk mencuba ini pada anda memiliki, dan kemudian menggunakan amalan yang
masalah untuk menyemak jawapan anda.
Kesemua ini telah direka untuk rapat berkaitan dengan dan mematuhi apa
yang anda perlu lakukan pada masalah yang ditetapkan.
Jadi, saya menggalakkan anda untuk amalan ini sendiri dan kemudian gunakan kod untuk
menyemak jawapan anda.
Kerana saya mahu bergerak untuk hash jadual pada satu ketika dalam seksyen itu.
Oleh itu, kita tidak mungkin akan melaluinya semua.
Tetapi kita akan melakukan sebanyak kita boleh sekarang.
>> OK.
Mari kita mulakan.
Asam, bagaimana kita mewujudkan nod baru?
>> PENONTON: Anda struct *.
>> JASON Hirschhorn: Oleh itu, kita ada yang di sini.
Oh, maaf.
Anda telah berkata struct *.
>> PENONTON: Dan kemudian [? jenis?] nod atau c nod.
>> JASON Hirschhorn: OK.
Saya akan memanggilnya new_node jadi kita boleh tinggal konsisten.
>> PENONTON: Dan anda mahu menetapkan bahawa untuk mengetuai, nod pertama.
>> JASON Hirschhorn: OK.
Jadi sekarang ini untuk menunjuk - jadi ini tidak mencipta nod baru lagi.
Ini hanya menunjuk ke nod pertama dalam senarai.
Bagaimana untuk saya mencipta nod baru?
Jika saya perlukan ruang untuk mewujudkan nod baru.
Malloc.
Dan berapa besar?
>> PENONTON: Saiz struct itu.
>> JASON Hirschhorn: The Saiz struct itu.
Dan apa yang struct yang dipanggil?
>> PENONTON: Nod?
>> JASON Hirschhorn: Nod.
Jadi malloc (sizeof (nod)); memberikan kita ruang.
Dan adalah baris ini -
satu perkara yang tidak betul pada baris ini.
Adalah new_node penunjuk kepada struct satu?
Itu merupakan nama generik.
Apakah ia -
nod, betul-betul.
Ia nod *.
Dan apa yang kita lakukan selepas kita malloc sesuatu, Asan?
Apakah perkara pertama yang kita buat?
Bagaimana jika ia tidak berfungsi?
>> PENONTON: Oh, memeriksa jika ia menunjuk kepada nod?
>> JASON Hirschhorn: Tepat sekali.
Jadi, jika anda new_node sama setaraf batal, apa yang kita lakukan?
Ini mengembalikan bool, fungsi ini.
Tepat sekali.
Kelihatan baik.
Apa-apa untuk menambah di sana?
Kami akan menambah perkara-perkara pada akhir.
Tetapi setakat ini kelihatan baik.
Mewujudkan petunjuk semasa dan sebelumnya.
Michael, bagaimana saya melakukan ini?
>> PENONTON: Anda perlu untuk melakukan nod *.
Anda harus membuat satu tidak untuk new_node tetapi untuk
nod kita sudah mempunyai.
>> JASON Hirschhorn: OK.
Jadi nod semasa kita berada di.
Saya akan panggil curr itu.
Baiklah.
Kami telah memutuskan kami mahu mengekalkan dua kerana kita perlu tahu
apa yang di hadapannya.
Apa yang mereka mendapatkan dimulakan untuk?
>> PENONTON: nilai mereka dalam senarai kami.
>> JASON Hirschhorn: Jadi apakah Perkara pertama dalam senarai kami?
Atau bagaimana kita tahu di mana permulaan senarai kami adalah?
>> PENONTON: Adakah ia tidak diluluskan ke dalam majlis itu?
>> JASON Hirschhorn: Betul.
Ia telah diluluskan pada di sini.
Jadi, jika ia diluluskan ke dalam majlis itu, yang memulakan senarai, apa yang perlu kita
ditetapkan semasa sama dengan?
>> PENONTON: Senarai.
>> JASON Hirschhorn: Senarai.
Itu betul-betul betul.
Kini ia mempunyai alamat permulaan senarai kami.
Dan apa yang kira-kira yang dahulu?
>> PENONTON: Senarai tolak satu?
>> JASON Hirschhorn: Ada apa-apa di hadapannya.
Jadi apa yang boleh kita lakukan untuk menandakan apa-apa?
>> PENONTON: Null.
>> JASON Hirschhorn: Yeah.
Yang berbunyi seperti idea yang baik.
Perfect.
Terima kasih.
Pergi melalui senarai.
Constantine, berapa lama kita akan melalui senarai?
>> PENONTON: Sehingga apabila Kami mencapai null.
>> JASON Hirschhorn: OK.
Jadi, jika, manakala, bagi gelung.
Apa yang kita lakukan?
>> PENONTON: Mungkin untuk gelung?
>> JASON Hirschhorn: Mari kita buat untuk gelung.
OK.
>> PENONTON: Dan kita katakan untuk -
sehingga penunjuk semasa tidak sama dengan nol.
>> JASON Hirschhorn: Jadi, jika kita tahu syarat, bagaimana kita boleh menulis gelung
berdasarkan dari keadaan itu.
Apakah jenis gelung kita harus digunakan?
>> PENONTON: Walaupun.
>> JASON Hirschhorn: Yeah.
Yang masuk akal lebih berasaskan kira apa yang anda kata.
Jika kita hanya mahu pergi ke dalam kita ia akan hanya tahu perkara itu, ia akan membuat
akal untuk melakukan gelung sementara.
Walaupun semasa tidak sama batal, jika nilai kurang daripada nod ini.
Akshar, memberikan saya garis ini.
>> PENONTON: Jika semasa-> n n kurang daripada nilai.
Atau terbalik itu.
Tukar kurungan itu.
>> JASON Hirschhorn: Maaf.
>> PENONTON: Tukar pendakap.
>> JASON Hirschhorn: Jadi, jika ia lebih besar daripada nilai.
Kerana itulah mengelirukan dengan comment di atas, saya akan berbuat demikian.
Tetapi ya.
Jika nilai kita adalah kurang daripada ini nod, apa yang kita lakukan?
Oh.
Saya ada di sini.
Masukkan sebelum ini.
OK.
Bagaimana kita berbuat demikian?
>> PENONTON: Adakah ia masih saya?
>> JASON Hirschhorn: Yeah.
>> PENONTON: Anda -
new_node-> seterusnya.
>> JASON Hirschhorn: Jadi apa yang yang akan sama?
>> PENONTON: Ia akan semasa sama.
>> JASON Hirschhorn: Tepat sekali.
Dan sebagainya yang lain -
apa lagi yang kita perlu mengemaskini?
>> PENONTON: Semak jika lalu sama null.
>> JASON Hirschhorn: Jika prev -
jadi jika prev sama null.
>> PENONTON: Ini bermakna ia akan untuk menjadi kepala.
>> JASON Hirschhorn: Ini bermakna ia menjadi kepala.
Jadi maka apa yang kita lakukan?
>> PENONTON: Kami kepala sama new_node.
>> JASON Hirschhorn: Ketua sama new_node.
Dan mengapa kepala di sini, tidak menyenaraikan?
>> PENONTON: Kerana kepala adalah global berubah-ubah, yang merupakan tempat permulaan.
>> JASON Hirschhorn: Sweet.
OK.
Dan -
>> PENONTON: Kemudian anda lagi prev-> seterusnya sama new_node.
Dan kemudian anda kembali benar.
>> JASON Hirschhorn: Di manakah kita menetapkan akhir new_node?
>> PENONTON: Saya akan -
Saya menetapkan bahawa pada permulaan.
>> JASON Hirschhorn: Jadi apa talian?
>> PENONTON: Selepas jika kenyataan memeriksa jika ia diketahui.
>> JASON Hirschhorn: Hak di sini?
>> PENONTON: aku akan melakukannya new_node-> n sama nilai.
>> JASON Hirschhorn: Bunyi yang baik.
Mungkin ia masuk akal - kita tidak perlu tahu apa senarai kami pada
kerana kita hanya berurusan dengan satu senarai.
Jadi fungsi akuan yang lebih baik untuk ini hanya untuk menghilangkan ini
sepenuhnya dan hanya memasukkan nilai ke dalam kepala.
Kita tidak perlu tahu apa yang senarai kita masuk
Tetapi saya akan menyimpannya untuk sekarang dan kemudian mengubahnya setelah mengemaskini
slaid dan kod.
Jadi yang kelihatan baik untuk sekarang.
Jika nilai - yang boleh melakukan talian ini?
Jika -
apa yang kita lakukan di sini, Nuh.
>> PENONTON: Jika nilai adalah lebih besar daripada curr-> n -
>> JASON Hirschhorn: Bagaimana kita pergi ke nod seterusnya?
>> PENONTON: Curr-> n sama dengan new_node.
>> JASON Hirschhorn: Jadi n apa yang sebahagian daripada struct itu?
Integer.
Dan new_node adalah penunjuk kepada nod.
Jadi apa yang sebahagian daripada curr yang patut kita mengemaskini?
Jika tidak n, maka apa yang sebahagian yang lain?
Nuh, apa yang pihak yang lain.
>> PENONTON: Oh, akan datang.
>> JASON Hirschhorn: Seterusnya, betul-betul.
Tepat sekali.
Seterusnya adalah yang betul.
Dan apa lagi yang kita perlu untuk mengemas kini, Nuh?
>> PENONTON: The petunjuk.
>> JASON Hirschhorn: Jadi kita dikemaskini semasa.
>> PENONTON: Sebelum-> seterusnya.
>> JASON Hirschhorn: Yeah.
OK, kita akan berhenti sejenak.
Siapa yang boleh membantu kita di sini?
Manu, apa yang patut kita buat?
>> PENONTON: Anda perlu untuk menetapkan ia sama dengan curr-> seterusnya.
Tetapi melakukannya sebelum baris sebelumnya.
>> JASON Hirschhorn: OK.
Apa-apa lagi?
Akshar.
>> PENONTON: Saya tidak fikir anda bertujuan untuk menukar curr-> seterusnya.
Saya rasa anda bertujuan untuk melakukan setaraf curr curr-> sebelah pergi ke nod seterusnya.
>> JASON Hirschhorn: Jadi maaf, di mana?
Kepada apa talian?
Keturunan ini?
>> PENONTON: Yeah.
Buat curr sama curr-> seterusnya.
>> JASON Hirschhorn: Jadi, itu betul kerana semasa adalah
penunjuk kepada nod.
Dan kami mahu ia untuk menunjukkan seterusnya nod apa yang mendapat pada masa ini
menunjuk kepada.
Curr itu sendiri mempunyai depan.
Tetapi jika kita mengemaskini curr.next, kami akan mengemas kini nota sebenar
sendiri, tidak di mana ini penunjuk telah menunjuk.
Apa kira-kira garis ini, walaupun.
Avi?
>> PENONTON: Sebelum-> seterusnya sama curr.
>> JASON Hirschhorn: Jadi sekali lagi, jika prev adalah penunjuk kepada nod, prev-> seterusnya adalah
penunjuk sebenar dalam nod.
Jadi ini akan mengemas kini penunjuk dalam nod ke curr.
Kita tidak mahu untuk mengemaskini penunjuk dalam satu nod.
Kami ingin mengemaskini sebelumnya.
Jadi bagaimana kita berbuat demikian?
>> PENONTON: Ia hanya akan prev.
>> JASON Hirschhorn: Betul.
Prev adalah penunjuk kepada nod.
Sekarang kita menukar kepada yang penunjuk baru kepada satu nod.
OK Marilah kita bergerak ke bawah.
Akhir sekali, keadaan terakhir ini.
Jeff, apa yang kita lakukan di sini?
>> PENONTON: Jika nilai adalah sama dengan curr-> n.
>> JASON Hirschhorn: Maaf.
Oh kebaikan saya.
Apa?
Nilai == curr-> n.
Apa yang kami lakukan?
>> PENONTON: Anda akan membebaskan new_node kami, dan kemudian anda akan pulangan palsu.
>> JASON Hirschhorn: Inilah yang kita telah menulis setakat ini.
Adakah sesiapa mempunyai apa-apa untuk menambah sebelum kita membuat?
OK.
Mari kita mencubanya.
Kawalan boleh mencapai akhir daripada fungsi bukan tidak sah.
Avi, apa yang berlaku?
>> PENONTON: Adakah anda sepatutnya meletakkan kembali benar di luar gelung sementara?
>> JASON Hirschhorn: Saya tidak tahu.
Adakah anda mahu saya?
>> PENONTON: Jangan sekali-kali fikiran.
No
>> JASON Hirschhorn: Akshar?
>> PENONTON: Saya rasa anda bertujuan untuk meletakkan pulangan palsu di hujung
gelung sementara.
>> JASON Hirschhorn: Jadi di mana adakah anda mahu pergi?
>> PENONTON: Seperti di luar gelung sementara.
Jadi, jika anda keluar gelung manakala yang cara bahawa anda telah sampai akhir dan
apa-apa yang berlaku.
>> JASON Hirschhorn: OK.
Jadi, apa yang kita lakukan di sini?
>> PENONTON: Anda pulangan palsu di sana juga.
>> JASON Hirschhorn: Oh, kami melakukannya dalam kedua-dua tempat?
>> PENONTON: Yeah.
>> JASON Hirschhorn: OK.
Sekiranya kita pergi?
Oh kebaikan saya.
Saya minta maaf.
Saya memohon maaf kerana skrin.
Ia jenis freaking kepada kami.
Jadi, pilih pilihan.
Zero, setiap kod, berhenti program ini.
Satu memasukkan sesuatu.
Mari kita memasukkan tiga.
Sisip tidak berjaya.
Saya akan mencetak.
Saya tidak mempunyai apa-apa.
OK.
Mungkin itu hanya suatu penipuan.
Masukkan satu.
Tidak berjaya.
OK.
Mari kita berjalan melalui GDB benar-benar cepat untuk menyemak apa yang sedang berlaku.
>> Ingat Pra-Pemasangan. / Nama anda program mendapat kita ke dalam GDB.
Adakah itu banyak untuk mengendalikan?
Berkelip?
Mungkin.
Tutup mata anda dan mengambil beberapa mendalam nafas jika anda bosan
melihat ia.
Saya dalam GDB.
Apakah perkara pertama yang saya lakukan dalam GDB?
Kita mesti memikirkan apa yang berlaku di sini.
Mari kita lihat.
Kami mempunyai enam minit untuk angka apa yang sedang berlaku.
Cuti utama.
Dan kemudian apa yang saya lakukan?
Carlos?
Berjalan.
OK.
Mari kita memilih pilihan.
Dan apa yang N buat?
Seterusnya.
Yeah.
>> PENONTON: Adakah anda tidak lagi -
adakah anda tidak mengatakan bahawa kepala, ia adalah dimulakan untuk null pada permulaan.
Tetapi saya fikir anda berkata bahawa adalah OK.
>> JASON Hirschhorn: Mari kita pergi - mari kita lihat dalam GDB, dan kemudian kami akan kembali.
Tetapi ia kedengaran seperti anda sudah mempunyai beberapa idea tentang apa yang berlaku.
Jadi, kami ingin memasukkan sesuatu.
OK.
Kami telah memasukkan.
Sila masukkan int satu.
Kami akan memasukkan tiga.
Dan kemudian saya di baris ini.
Bagaimana saya boleh pergi memulakan debugging sisip dikenali fungsi?
Oh kebaikan saya.
Itulah banyak.
Adakah itu freaking keluar banyak?
>> PENONTON: Oh, ia meninggal dunia.
>> JASON Hirschhorn: Saya hanya ditarik keluar.
OK.
>> PENONTON: Mungkin ia adalah Hujung wayar.
>> JASON Hirschhorn: Wow.
Jadi garis bawah -
apa yang kamu katakan?
>> PENONTON: Saya berkata Ironinya teknikal kesukaran di dalam kelas ini.
>> JASON Hirschhorn: Saya tahu.
Kalaulah saya mempunyai kawalan ke atas bahagian itu.
[Didengar]
Yang berbunyi besar.
Mengapa tidak anda semua mula berfikir tentang apa yang kita boleh lakukan salah,
dan kami akan kembali dalam 90 saat.
>> Avica, saya akan bertanya kepada anda bagaimana untuk insert_node dalam untuk debug ia.
Jadi ini adalah di mana kita lepas berhenti.
Bagaimana saya masuk ke dalam insert_node, Avica, untuk memeriksa apa yang berlaku?
Apa arahan GDB?
Cuti tidak akan membawa saya di dalam.
Adakah Marquise tahu?
>> PENONTON: Apa?
>> JASON Hirschhorn: Apa arahan GDB Saya gunakan untuk masuk ke dalam fungsi ini?
>> PENONTON: Langkah?
>> JASON Hirschhorn: Langkah melalui S. Yang mengambil saya di dalam.
OK.
New_node mallocing sedikit ruang.
Bahawa semua nampaknya jualan.
Mari kita meneliti new_node.
Ia mendapat beberapa alamat ingatan.
Mari kita semak -
yang semuanya betul.
Jadi semuanya di sini nampaknya akan berfungsi dengan betul.
>> PENONTON: Apakah perbezaan di antara P dan paparan?
>> JASON Hirschhorn: P bermaksud cetak.
Dan supaya anda meminta apa yang Perbezaan di antara itu dan ini?
Dalam kes ini, apa-apa.
Tetapi secara amnya terdapat beberapa perbezaan.
Dan anda perlu mencari di manual GDB itu.
Tetapi dalam kes ini, apa-apa.
Kita cenderung untuk menggunakan cetak, walaupun, kerana kita tidak perlu untuk melakukan lebih daripada
mencetak satu nilai.
>> OK.
Oleh itu, kita berada di barisan 80 kod kami, menetapkan nod * curr sama dengan senarai.
Marilah kita mencetak curr.
Ia sama senarai.
Manis.
Tunggu.
Ia sama sesuatu.
Yang nampaknya tidak betul.
Di sana kami pergi.
Ini kerana dalam GDB, betul, jika ia garis anda di atasnya
telah tidak dilaksanakan lagi.
Jadi, anda perlu benar-benar menaip seterusnya untuk melaksanakan garis
sebelum melihat hasilnya.
Jadi di sini kita.
Kami hanya dilaksanakan baris ini, sebelumnya sama null.
Jadi sekali lagi, jika kita cetak sebelumnya kita tidak akan melihat apa-apa yang pelik.
Tetapi jika kita benar-benar melaksanakan yang line, maka kita akan melihat
bahawa garis yang bekerja.
>> Jadi kita mempunyai curr.
Mereka kedua-duanya baik.
Betul?
Kini kita sudah membuat baris ini di sini.
Walaupun curr tidak sama null.
Nah, apakah curr sama?
Kami hanya melihat ia equaled null.
Kami dicetak keluar.
Saya akan mencetak semula.
Jadi adalah bahawa manakala gelung akan melaksanakan?
>> PENONTON: No
>> JASON Hirschhorn: Oleh itu, apabila saya menaip yang talian, anda melihat kita melompat sepanjang jalan
turun ke bawah, pulangan palsu.
Dan kemudian kita akan pulangan palsu dan kembali ke program kami dan
akhirnya mencetak, seperti yang kita lihat, sisip tidak berjaya.
Jadi, sesiapa mempunyai apa-apa idea mengenai apa yang yang perlu kita lakukan untuk menetapkan ini?
Saya akan menunggu sehingga saya melihat beberapa tangan naik.
Kami tidak melaksanakan ini.
Perlu diingat, ini adalah yang pertama perkara yang kita lakukan.
Saya tidak akan melakukan pasangan.
Saya akan melakukan beberapa.
Kerana pasangan bermakna dua.
Saya akan menunggu lebih daripada dua orang.
>> Kemasukan pertama, curr, secara lalai sama null.
Dan gelung ini hanya melaksanakan jika curr tidak null.
Jadi bagaimana saya boleh mendapatkan sekitar ini?
Saya melihat tiga tangan.
Saya akan menunggu lebih daripada tiga.
Marcus, apa yang anda berfikir?
>> PENONTON: Nah, jika anda memerlukannya untuk melaksanakan lebih dari sekali, anda hanya
mengubahnya dengan gelung do-sementara.
>> JASON Hirschhorn: OK.
Yang akan menyelesaikan masalah kita, walaupun?
>> PENONTON: Dalam kes ini tidak kerana hakikat bahawa senarai adalah kosong.
Jadi maka anda mungkin hanya perlu menambah kenyataan bahawa jika pintu keluar gelung
maka anda perlu berada di akhir senarai, di mana titik anda
hanya boleh memasukkannya.
>> JASON Hirschhorn: Saya suka itu.
Yang masuk akal.
Jika gelung keluar -
kerana ia akan pulangan palsu di sini.
Jadi, jika pintu keluar gelung, maka kita berada di akhir senarai, atau mungkin
bermula daripada senarai jika tiada apa-apa dalam ia, yang adalah sama seperti akhir.
Jadi sekarang kita mahu untuk memasukkan sesuatu di sini.
Jadi bagaimana kod yang kelihatan, Marcus?
>> PENONTON: Jika anda sudah mendapat nod malloced, anda hanya boleh mengatakan
new_node-> seterusnya sama null kerana ia perlu pada akhir.
Atau new_node-> seterusnya sama null.
>> JASON Hirschhorn: OK.
Maaf.
New_node-> seterusnya sama null kerana kita pada akhir.
Yang tidak meletakkan ia masuk
Bagaimana kita memasukkannya ke dalam senarai?
Betul.
Itu hanya menetapkan ia sama dengan.
Tiada bagaimana kita sebenarnya memasukkannya ke dalam senarai?
Apa yang menunjuk ke akhir senarai?
>> PENONTON: Ketua.
>> JASON Hirschhorn: Maaf?
>> PENONTON: Ketua menghala ke akhir senarai.
>> JASON Hirschhorn: Jika tiada apa-apa dalam senarai, kepala menunjuk ke
akhir senarai.
Jadi yang akan bekerja untuk kemasukan pertama.
Bagaimana pula jika ada pasangan perkara dalam senarai?
Daripada kita tidak mahu untuk menetapkan kepala sama dengan new_node.
Apa yang kami mahu lakukan di sana?
Yeah?
Mungkin sebelumnya.
Yang akan bekerja?
Ingat bahawa sebelum ini hanya penunjuk kepada nod.
Dan sebelumnya adalah pembolehubah tempatan.
Jadi baris ini akan menetapkan pembolehubah tempatan, sebelum ini, sama dengan atau
menunjuk kepada nod baru ini.
Itu tidak akan benar-benar meletakkan ia dalam senarai kami, walaupun.
Bagaimana kita memasukkannya ke dalam senarai kami?
Akchar?
>> PENONTON: Saya rasa anda lakukan semasa-> seterusnya.
>> JASON Hirschhorn: OK.
curr-> seterusnya.
Jadi sekali lagi, satu-satunya sebab kita turun di sini ialah, apakah semasa sama?
>> PENONTON: Sama null.
>> JASON Hirschhorn: Dan jadi apa berlaku jika kita melakukan null-> akan datang?
Apa yang kita akan dapat?
Kami akan mendapat kesalahan segmentasi.
>> PENONTON: Do curr sama null.
>> JASON Hirschhorn: Itu perkara yang sama sebagai prev, walaupun, kerana ada
pembolehubah tempatan kita menetapkan sama dengan nod baru ini.
Mari kita kembali kepada gambar kami memasukkan sesuatu.
Katakanlah kita sedang memasukkan di hujung senarai, jadi di sini.
Kami mempunyai penunjuk semasa itu menunjuk ke nol dan titik sebelumnya
itu menunjuk ke 8.
Jadi, apa yang kita perlu untuk mengemas kini, Avi?
>> PENONTON: Sebelum-> akan datang?
>> JASON Hirschhorn: Sebelum-> seterusnya adalah apa yang kita mahu untuk mengemaskini kerana itu
sebenarnya akan memasukkan ia di akhir senarai.
Kami masih mempunyai satu bug, walaupun, bahawa kita akan menghadapi.
Apakah pepijat itu?
Yeah?
>> PENONTON: Ia akan kembali palsu dalam kes ini?
>> JASON Hirschhorn: Oh, adalah adalah akan kembali palsu.
Tetapi ada bug yang lain.
Oleh itu, kita perlu untuk dimasukkan ke dalam pulangan benar.
>> PENONTON: Adakah sebelum ini masih sama null di bahagian atas senarai?
>> JASON Hirschhorn: masih Jadi sebelumnya sama null pada awal-awal.
Jadi bagaimana kita boleh mendapatkan lebih itu?
Yeah?
>> PENONTON: Saya rasa anda boleh buat cek sebelum gelung sementara untuk melihat jika ia
senarai main kosong.
>> JASON Hirschhorn: OK.
Jadi mari kita pergi sini.
Adakah cek.
Jika -
>> PENONTON: Jadi, jika kepala sama sama null.
>> JASON Hirschhorn: Jika kepala sama sama null -
yang akan memberitahu kita jika ia adalah satu senarai kosong.
>> PENONTON: Dan kemudian anda melakukan kepala sama baru.
>> JASON Hirschhorn: Ketua sama new_node?
Dan apa lagi yang perlu kita lakukan?
>> PENONTON: Dan kemudian anda kembali benar.
>> JASON Hirschhorn: Tidak cukup.
Kami hilang satu langkah.
>> PENONTON: New_node seterusnya mempunyai untuk menunjuk kepada nol.
>> JASON Hirschhorn: Tepat, Alden.
Dan kemudian kita boleh kembali benar.
OK.
Tetapi ia masih idea yang baik untuk melakukan perkara-perkara di akhir senarai, bukan?
Baiklah.
Kita masih sebenarnya mungkin mendapatkan ke akhir senarai.
Jadi adalah baik kod ini jika kita di berakhir senarai dan terdapat beberapa
perkara dalam senarai?
Betul?
Kerana kita masih mempunyai idea Marcus ini.
Kita mungkin keluar gelung ini kerana kami pada akhir senarai.
Jadi kita masih mahu ini kod turun di sini?
>> PENONTON: Ya.
>> JASON Hirschhorn: Yeah.
Dan apa yang kita perlu menukar ini kepada?
Benar.
Adakah yang baik bunyi kepada semua orang setakat ini?
Sesiapa mempunyai apa-apa -
Avi, adakah anda mempunyai sesuatu untuk menambah?
>> PENONTON: No
>> JASON Hirschhorn: OK.
Oleh itu, kita telah membuat beberapa perubahan.
Kami telah membuat semak ini sebelum kita masuk untuk senarai main kosong.
Oleh itu, kita dijaga senarai main kosong.
Dan di sini kita menjaga memasukkan sesuatu yang pada akhir senarai.
Jadi ia kelihatan seperti ini pengambilan gelung sementara menjaga perkara-perkara di antara,
di suatu tempat dalam senarai jika terdapat adalah perkara-perkara dalam senarai.
>> OK.
Marilah kita menjalankan program ini sekali lagi.
Tidak berjaya.
>> PENONTON: Anda tidak berjaya.
>> JASON Hirschhorn: Oh, Saya tidak berjaya.
Titik yang baik, Michael.
Mari kita menambah make dikaitkan.
Talian 87 ada ralat.
Talian 87.
Alden, ini adalah baris yang anda memberikan saya.
Apa yang salah?
>> PENONTON: Ia perlu untuk nol.
>> JASON Hirschhorn: Cemerlang.
Tepat betul.
Ia harus null.
Mari kita membuat semula.
Menyusun.
OK.
Mari kita memasukkan tiga.
Insert telah berjaya.
Mari kita mencetak.
Oh, jika hanya kita boleh cek.
Tetapi kita telah tidak dilakukan yang mencetak fungsi yet.
Mari kita memasukkan sesuatu yang lain.
Apa yang patut kita masukkan?
>> PENONTON: Tujuh.
>> JASON Hirschhorn: Tujuh?
>> PENONTON: Ya.
>> JASON Hirschhorn: Kami mempunyai kesalahan seg.
Oleh itu, kita mendapat satu, namun jelas tidak boleh mendapatkan dua.
Ia adalah 05:07.
Jadi kita boleh debug ini selama tiga minit.
Tetapi saya akan meninggalkan kita di sini dan bergerak ke hash jadual.
Tetapi sekali lagi, jawapan untuk kod ini Saya akan email kepada anda dalam sedikit.
Kami amat hampir dengannya.
Saya sangat menggalakkan anda untuk memikirkan apa yang berlaku di sini dan membaikinya.
Jadi saya akan e-mel kepada anda kod ini sebagai juga ditambah penyelesaian -
mungkin penyelesaian di kemudian hari.
Pertama kod ini.
>> Perkara lain yang saya mahu lakukan sebelum kita penamat adalah kami tidak dibebaskan apa-apa.
Jadi saya mahu menunjukkan kepada anda apa valgrind kelihatan seperti.
Jika kita menjalankan sempadan valgrind program kami,. / berkaitan.
Sekali lagi, menurut slaid ini, kita perlu menjalankan valgrind dengan beberapa jenis
pilihan, dalam kes ini - Kebocoran-cek = penuh.
Jadi mari kita menulis valgrind - Kebocoran-cek = penuh.
Jadi ini akan berjalan valgrind pada program kami.
Dan kini program ini benar-benar berjalan.
Jadi kita akan menjalankannya seperti sebelum ini, meletakkan sesuatu masuk
Saya akan dimasukkan ke dalam tiga.
Bahawa kerja-kerja.
Saya tidak akan cuba untuk dimasukkan ke dalam sesuatu lain kerana kita akan
mendapatkan palsu seg dalam kes itu.
Jadi, saya hanya akan berhenti.
>> Dan sekarang anda melihat ke bawah di sini bocor dan ringkasan timbunan.
Ini adalah perkara-perkara yang baik yang anda mahu lihat.
Jadi ringkasan timbunan - ia berkata, digunakan di pintu keluar - lapan bait dalam satu blok.
Yang satu blok adalah nod kita malloced.
Michael, anda berkata sebelum nod adalah lapan gigitan kerana ia mempunyai integer
dan penunjuk.
Jadi, itu nod kami.
Dan kemudian ia mengatakan kita digunakan malloc tujuh kali dan kami dibebaskan
sesuatu enam kali.
Tapi kami tidak pernah dipanggil percuma, jadi saya tidak mempunyai idea apa ini sedang bercakap tentang.
>> Tetapi cukuplah untuk mengatakan bahawa apabila anda berjalan program, malloc yang disebut
di beberapa tempat lain yang kami tidak perlu bimbang.
Jadi malloc telah mungkin dipanggil di beberapa tempat.
Kita tidak perlu bimbang di mana.
Tetapi ini adalah benar-benar kami.
Ini sejajar pertama adalah kita.
Kami meninggalkan blok itu.
Dan anda boleh melihat bahawa di sini dalam ringkasan kebocoran.
Masih dapat dihubungi -
lapan bait dalam satu blok.
Ini bermakna memori yang -
kami telah bocor memori itu.
Pasti hilang -
sesuatu yang hilang selama-lamanya.
Secara umumnya, anda tidak akan melihat apa-apa di sana.
Masih dapat dihubungi secara umumnya di mana anda akan melihat perkara-perkara, di mana anda akan mahu
untuk melihat untuk melihat apa kod sekiranya anda telah dibebaskan tetapi anda terlupa untuk membebaskan.
>> Dan kemudian jika ini tidak berlaku, jika kita lakukan segala-galanya percuma,
kita boleh pastikan.
Mari kita menjalankan program ini tidak meletakkan dalam apa-apa.
Anda akan melihat ke bawah di sini digunakan di pintu keluar -
sifar sifar bait dalam blok.
Ini bermakna kita mempunyai apa yang tinggal apabila program ini keluar.
Jadi sebelum perubahan dalam pset6, jalankan valgrind dan pastikan anda tidak mempunyai
apa-apa memori bocor dalam program anda.
Jika anda mempunyai sebarang soalan dengan valgrind, berasa bebas untuk mendekati.
Tetapi ini adalah bagaimana anda menggunakannya.
Sangat mudah - lihat jika anda mempunyai digunakan di pintu keluar -
apa-apa dalam mana-mana bait blok.
>> Oleh itu, kita telah bekerja di nod memasukkan.
Saya mempunyai dua fungsi lain di sini - mencetak nod nod dan percuma.
Sekali lagi, ini adalah fungsi yang akan menjadi baik untuk anda berlatih
kerana mereka akan membantu anda bukan sahaja dengan senaman ini sampel tetapi juga
kepada masalah yang ditetapkan.
Mereka map di agak rapat kepada perkara-perkara anda akan perlu lakukan dalam
masalah ditetapkan.
Tetapi saya ingin memastikan kita sentuh pada segala-galanya.
Dan jadual hash juga penting untuk apa yang kita lakukan dalam bahagian ini
minggu - atau dalam masalah yang ditetapkan.
>> Jadi, kita akan untuk menyelesaikan bahagian bercakap tentang jadual hash.
Jika anda perasan saya membuat jadual hash sedikit.
Itu bukan apa yang kita bercakap kira-kira, namun.
Kita bercakap tentang yang berbeza jenis jadual hash.
Dan pada teras, meja hash yang adalah tidak lebih daripada satu
array ditambah dengan fungsi hash.
Kami akan bercakap untuk sedikit hanya untuk membuat semua orang pasti memahami apa yang
fungsi hash adalah.
Dan saya memberitahu anda sekarang bahawa ia adalah tidak lebih daripada dua perkara -
pelbagai dan fungsi hash.
Dan di sini adalah langkah-langkah melalui yang ini beroperasi.
>> Ada pelbagai kami.
Ada fungsi kami.
Khususnya, fungsi hash perlu melakukan beberapa perkara dengan ini.
Saya akan bercakap secara khusus tentang masalah ini ditetapkan.
Ia mungkin akan mengambil rentetan.
Dan apa yang ia akan kembali?
Apakah jenis data?
Alden?
Fungsi hash anda kembali?
Integer.
Jadi ini adalah apa hash meja terdiri daripada -
jadual dalam bentuk array dan fungsi hash.
Bagaimana ia berfungsi?
Ia berfungsi dalam tiga langkah.
Kami memberikan kunci.
Dalam kes ini, kami akan memberikan rentetan.
Kami menyeru fungsi hash per satu langkah pada kekunci yang dan kita mendapat nilai.
>> Secara khusus, kami akan mengatakan kita akan mendapat integer.
Integer itu, terdapat sangat khusus had kepada apa yang integer yang boleh.
Dalam contoh ini, pelbagai kami adalah saiz tiga.
Jadi apa nombor boleh integer yang berkenaan.
Apakah julat nilai yang sah untuk integer yang, jenis pulangan ini
hash fungsi?
Zero, satu dan dua.
Titik fungsi hash ini adalah untuk memikirkan tempat dalam array
di mana utama kami akan.
Terdapat hanya tiga mungkin tempat-tempat di sini -
sifar, satu, atau dua.
Jadi fungsi ini lebih baik pulangan sifar, satu, atau dua.
Sesetengah indice sah dalam pelbagai ini.
>> Dan kemudian bergantung di mana ia kembali, anda boleh lihat ada pelbagai terbuka
braket nilai.
Itulah di mana kita meletakkan kunci.
Oleh itu, kita buang dalam labu, kita keluar sifar.
Pada pelbagai kurungan 0, kita meletakkan labu.
Kita buang dalam kucing, kita keluar satu.
Kami meletakkan kucing di satu.
Kami dimasukkan ke dalam labah-labah.
Kita keluar dua.
Kami meletakkan labah-labah di pelbagai kurungan dua.
Ia akan menjadi begitu baik jika ia bekerja seperti itu.
Tetapi malangnya, seperti yang kita akan lihat, ia agak lebih rumit.
>> Sebelum kita sampai ke sana, apa-apa soalan mengenai asas ini
set-up jadual hash?
Ini adalah imej betul-betul apa yang kita menarik di papan.
Tetapi oleh kerana kita menarik ke atas pesawat, saya saya tidak akan pergi ke dalamnya lanjut.
Pada dasarnya kunci, kotak hitam ajaib - atau dalam kes ini, kotak Teal - daripada
fungsi hash meletakkan mereka dalam baldi.
Dan dalam contoh ini kita tidak meletakkan nama.
Kami meletakkan telefon yang bersekutu beberapa nama dalam baldi.
Tetapi anda boleh dengan baik hanya meletakkan nama dalam baldi.
>> Ini hanya gambaran apa kita menarik di papan.
Kami mempunyai kesulitan yang berpotensi, walaupun.
Dan terdapat dua khususnya slaid yang saya mahu pergi ke.
Yang pertama adalah kira-kira fungsi hash.
Jadi saya bertanya, apa yang membuat fungsi hash yang baik?
Saya memberi dua jawapan.
Yang pertama adalah bahawa ia berketentuan.
Dalam konteks fungsi hash, apakah ini bermakna?
Ya?
>> PENONTON: Ujian ini dapat mengesan indeks dalam masa berterusan?
>> JASON Hirschhorn: Itu bukan apa yang dimaksudkan.
Tetapi itu tekaan yang baik.
Orang lain mempunyai meneka untuk apa ini bermakna?
Bahawa fungsi hash yang baik adalah berketentuan?
Annie?
>> PENONTON: Bahawa kunci hanya boleh dipetakan ke satu tempat dalam jadual hash.
>> JASON Hirschhorn: Itu betul-betul betul.
Setiap kali anda masukkan ke dalam labu, ia sentiasa kembali sifar.
Jika anda masukkan ke dalam labu dan hash anda mengembalikan sifar tetapi mempunyai
kebarangkalian kembali sesuatu lain yang lebih besar daripada sifar -
jadi mungkin ia boleh kembali satu kadang-kadang atau dua waktu yang lain -
yang tidak fungsi hash yang baik.
Anda betul-betul betul.
Fungsi hash anda perlu mengembalikan integer tepat sama, dalam kes ini, untuk
rentetan tepat sama.
>> Mungkin ia mengembalikan integer yang tepat sama rentetan yang sama tepat
tanpa mengira permodalan.
Tetapi dalam kes itu ia masih berketentuan kerana pelbagai perkara
dipetakan ke nilai yang sama.
Itu denda.
Selagi hanya ada satu output input yang diberikan.
>> OK.
Perkara kedua ialah ia mengembalikan indeks sah.
Kami dibesarkan yang lebih awal.
Fungsi hash -
oh boy -
fungsi hash perlu kembali indeks sah.
Supaya berkata -
mari kita kembali ke contoh ini.
Fungsi hash saya yang diambil kira sehingga huruf dalam perkataan.
Itulah fungsi hash.
Dan mengembalikan integer itu.
Jadi jika saya mempunyai perkataan A, ia akan kembali satu.
Dan ia akan meletakkan A di sini.
Bagaimana jika saya dimasukkan ke dalam kelawar perkataan?
Ia akan kembali tiga.
Di manakah kelawar pergi?
>> Ia tidak patut.
Tetapi ia perlu pergi ke suatu tempat.
Ini adalah jadual hash saya selepas semua, dan semua perlu pergi ke suatu tempat.
Jadi di mana kelawar harus pergi?
Mana-mana pemikiran?
Meneka?
Tekaan yang baik?
>> PENONTON: Zero.
>> JASON Hirschhorn: Kenapa sifar?
>> PENONTON: Kerana tiga modulo tiga adalah sifar?
>> JASON Hirschhorn: Tiga modulo tiga adalah sifar.
Itu adalah tekaan yang besar, dan itulah yang betul.
Jadi dalam kes ini sepatutnya mungkin pergi pada sifar.
Jadi cara yang baik untuk memastikan bahawa hash ini fungsi hanya mengembalikan indeks sah
untuk modulo ia oleh saiz meja.
Jika anda modulo apa pulangan ini dengan tiga, anda sentiasa akan mendapat
sesuatu antara sifar, satu, dan dua.
Dan jika ini sentiasa mengembalikan tujuh, dan anda sentiasa modulo oleh tiga, anda
sentiasa akan mendapat perkara yang sama.
>> Jadi ia masih berketentuan jika anda modulo.
Tetapi yang akan memastikan bahawa anda tidak pernah mendapat sesuatu -
industri tidak sah.
Secara amnya, modulo yang sepatutnya berlaku dalam fungsi hash anda.
Jadi anda tidak perlu bimbang tentang perkara ini.
Anda hanya boleh memastikan bahawa ini adalah indice yang sah.
Sebarang pertanyaan mengenai perkara ini potensi perangkap?
>> OK.
Dan ada kita pergi.
Seterusnya perangkap yang berpotensi, dan ini adalah salah satu yang besar.
Bagaimana jika dua kunci peta kepada nilai yang sama?
Jadi, terdapat dua cara untuk menguruskannya.
Yang pertama dipanggil linear menyelesaikan sesuatu, yang saya
tidak akan pergi ke atas.
Tetapi anda perlu biasa dengan bagaimana yang bekerja dan apa yang.
>> Yang kedua saya akan pergi ke atas kerana itu adalah salah satu yang ramai
orang mungkin akan berakhir membuat keputusan untuk digunakan dalam set masalah mereka.
Sudah tentu, anda tidak perlu.
Tetapi bagi set masalah, ramai orang cenderung untuk memilih untuk membuat jadual hash
dengan chaining berasingan untuk melaksanakan kamus mereka.
Jadi, kita akan kembali apa yang ia bermakna untuk membuat jadual hash dengan
chaining berasingan.
>> Jadi saya dimasukkan ke dalam labu.
Ia akan kembali sifar.
Dan saya meletakkan labu di sini.
Kemudian saya dimasukkan ke dalam -
apa yang satu lagi perkara Halloween bertemakan?
>> PENONTON: Gula-gula.
>> JASON Hirschhorn: Gula-gula!
Itulah salah satu yang besar.
Saya dimasukkan ke dalam gula-gula, dan gula-gula juga memberi saya sifar.
Apa yang saya buat?
Apa-apa idea?
Kerana anda semua jenis tahu apa chaining berasingan.
Jadi apa-apa idea apa yang perlu dilakukan?
Yeah.
>> PENONTON: Meletakkan tali sebenarnya dalam jadual hash.
>> JASON Hirschhorn: Jadi kita akan menarik idea yang baik di sini.
OK.
>> PENONTON: Ada hashtable yang [Didengar]
penunjuk yang menunjuk ke permulaan senarai.
Dan kemudian telah menjadi labu nilai pertama dalam senarai dikaitkan dan gula-gula menjadi
nilai kedua dalam senarai berkaitan.
>> JASON Hirschhorn: OK.
Marcus, yang cemerlang.
Saya akan memecahkan bahawa ke bawah.
Marcus berkata tidak menulis ganti labu.
Itu akan menjadi buruk.
Jangan letakkan gula-gula di tempat lain.
Kami akan meletakkan mereka di kedua-dua sifar.
Tetapi kita akan menangani meletakkan mereka pada sifar oleh
mewujudkan satu senarai pada sifar.
Dan kita akan membuat senarai semua yang dipetakan kepada sifar.
Dan cara terbaik kita belajar untuk mewujudkan senarai yang boleh membesar dan mengecut
dinamik tidak termasuk dalam pelbagai lain.
Jadi bukan pelbagai multi-dimensi.
Tetapi untuk hanya membuat senarai berpaut.
>> Jadi apa yang dicadangkan -
Saya akan mendapatkan yang baru -
adalah mewujudkan pelbagai dengan petunjuk, pelbagai petunjuk.
OK.
Apa-apa idea atau bayangan apa jenis yang petunjuk ini harus?
Marcus?
>> PENONTON: Penunjuk untuk -
>> JASON Hirschhorn: Kerana anda berkata senarai berpaut, jadi -
>> PENONTON: petunjuk Node?
>> JASON Hirschhorn: petunjuk Nod.
Jika perkara-perkara dalam kita dikaitkan senarai adalah nod maka mereka
harus petunjuk nod.
Dan apa yang mereka menyamai mulanya?
>> PENONTON: Null.
>> JASON Hirschhorn: Null.
Jadi ada perkara kosong kami.
Pulangan Labu sifar.
Apa yang kami lakukan?
Berjalan saya melaluinya?
Sebenarnya, Marcus telah memberikan saya.
Orang lain berjalan saya melaluinya.
Apa yang kita lakukan apabila kita -
ini kelihatan hampir sama dengan apa yang kita hanya melakukan.
Avi.
>> PENONTON: saya akan mengambil tekaan.
Oleh itu, apabila anda mendapat gula-gula.
>> JASON Hirschhorn: Yeah.
Nah, kita mendapat labu.
Mari kita mendapat satu pertama kami.
Kami mendapat labu.
>> PENONTON: OK.
Pulangan Labu sifar.
Jadi anda meletakkannya dalam itu.
Atau sebenarnya, anda meletakkannya dalam senarai yang dipautkan.
>> JASON Hirschhorn: Bagaimana kita memasukkannya ke dalam senarai dikaitkan?
>> PENONTON: Oh, syntax?
>> JASON Hirschhorn: Hanya berjalan -
berkata lebih.
Apa yang kami lakukan?
>> PENONTON: Anda hanya memasukkan sebagai nod pertama.
>> JASON Hirschhorn: OK.
Jadi kita mempunyai nod kami, labu.
Dan sekarang bagaimana saya memasukkan ia?
>> PENONTON: Anda menyerahhakkan kepada penunjuk.
>> JASON Hirschhorn: Yang pointer?
>> PENONTON: Penunjuk pada sifar.
>> JASON Hirschhorn: Jadi di mana tidak ketika ini?
>> PENONTON: Untuk nol sekarang.
>> JASON Hirschhorn: Baiklah, ia menunjuk ke nol.
Tetapi saya meletakkan dalam labu.
Jadi di mana ia perlu menunjukkan?
>> PENONTON: Untuk labu.
>> JASON Hirschhorn: Untuk labu.
Tepat sekali.
Jadi ini menunjukkan kepada labu.
Dan di mana tidak penunjuk ini di titik labu?
Untuk
>> PENONTON: Null.
>> JASON Hirschhorn: Untuk nol.
Tepat sekali.
Jadi kita hanya dimasukkan sesuatu ke dalam senarai yang dipautkan.
Kami hanya menulis kod ini untuk melakukan ini.
Hampir kita hampir mendapat retak sepenuhnya.
Sekarang kita memasukkan gula-gula.
Gula-gula kami turut diberikan kepada sifar.
Jadi apa yang kami lakukan dengan gula-gula?
>> PENONTON: Ia bergantung kepada sama ada atau tidak kita cuba untuk mengatasinya.
>> JASON Hirschhorn: Itu betul-betul betul.
Ia bergantung kepada sama ada atau tidak kita cuba untuk mengatasinya.
Mari kita andaikan kita tidak akan mengatasinya.
>> PENONTON: Kalau begitu, seperti yang kita bincangkan sebelum ini, ia paling mudah hanya untuk meletakkannya
betul-betul di permulaan supaya penunjuk dari sifar mata kepada gula-gula.
>> JASON Hirschhorn: OK.
Berpegang.
Izinkan saya membuat gula-gula di sini.
Jadi penunjuk ini -
>> PENONTON: Ya, perlu sekarang akan menunjuk ke gula-gula.
Kemudian mempunyai penunjuk dari titik gula-gula kepada labu.
>> JASON Hirschhorn: Seperti yang?
Dan mengatakan kita mendapat satu lagi perkara untuk peta ke sifar?
>> PENONTON: Nah, anda hanya melakukan perkara yang sama?
>> JASON Hirschhorn: Adakah perkara yang sama.
Jadi dalam kes ini, jika kita tidak hendak simpan ia disusun ia
bunyi agak mudah.
Kami mengambil penunjuk di indice yang diberikan oleh fungsi hash kami.
Kami mempunyai ketika itu untuk nod baru kami.
Dan kemudian apa sahaja ia menunjuk sebelum ini -
dalam ini null kes, dalam kes kedua labu -
bahawa, apa sahaja yang ia menunjuk ke sebelum ini, kami menambah ke dalam seterusnya
nod baru kami.
Kami memasukkan sesuatu pada mulanya.
Sebenarnya ini adalah lebih mudah daripada cuba untuk menjaga senarai disusun.
Tetapi sekali lagi, pencarian akan menjadi lebih rumit di sini.
Kami akan sentiasa perlu pergi ke akhirnya.
>> OK.
Apa-apa soalan mengenai chaining berasingan?
Bagaimana yang bekerja?
Sila tanya mereka sekarang.
Saya benar-benar ingin memastikan anda semua memahami perkara ini sebelum kita menuju keluar.
>> PENONTON: Kenapa anda meletakkan labu dan gula-gula ke dalam yang sama
sebahagian daripada jadual hash?
>> JASON Hirschhorn: Soalan yang baik.
Mengapa kita memasukkannya ke dalam yang sama sebahagian daripada jadual hash?
Nah, dalam kes ini fungsi hash kami pulangan sifar untuk kedua-dua mereka.
Jadi mereka perlu pergi di indice sifar kerana itulah di mana kita akan
mencari mereka jika kita pernah mahu melihat mereka.
Sekali lagi, dengan pendekatan linear menyelesaikan sesuatu kita tidak akan meletakkan mereka di kedua-dua sifar.
Tetapi dalam pendekatan rantaian yang berasingan, kita akan meletakkan mereka di kedua-dua sifar
dan kemudian buat satu senarai kira sifar.
>> Dan kita tidak mahu menulis ganti labu semata-mata untuk itu kerana maka kita akan
menganggap bahawa labu adalah tidak pernah dimasukkan.
Jika kita hanya menyimpan satu perkara dalam lokasi yang akan menjadi buruk.
Kemudian tidak akan ada peluang kita pernah -
jika kita pernah mempunyai salinan, maka kita hanya akan memadam nilai awal kami.
Jadi itulah sebabnya kami melakukan pendekatan ini.
Atau itulah sebabnya kami memilih - tetapi sekali lagi, kita memilih pendekatan rantaian yang berasingan,
mana terdapat banyak pendekatan yang lain salah satu boleh memilih.
Adakah yang menjawab soalan anda?
>> OK.
Carlos.
Linear menyelesaikan sesuatu akan melibatkan -
jika kami mendapati perlanggaran pada sifar, kita akan kelihatan di tempat yang seterusnya untuk melihat jika
ia terbuka dan meletakkannya di sana.
Dan kemudian kita lihat dalam sukan akan datang dan melihat jika yang terbuka dan meletakkannya di sana.
Jadi kita dapati yang ada seterusnya tempat terbuka dan meletakkannya di sana.
Apa-apa soalan lain?
Ya, Avi.
>> PENONTON: Sebagai susulan itu, apa yang anda maksudkan dengan tempat akan datang?
Dalam jadual hash atau dalam senarai berpaut.
>> JASON Hirschhorn: Untuk linear pengaturcaraan, tiada senarai berkaitan.
Tempat yang seterusnya di atas meja hash.
>> PENONTON: OK.
Jadi jadual hash akan dimulakan dengan saiz -
seperti bilangan tali bahawa anda telah memasukkan?
>> JASON Hirschhorn: Anda akan mahu ia menjadi benar-benar besar.
Ya.
Di bawah ialah gambar daripada apa yang kita hanya menarik di papan.
Sekali lagi, kita mempunyai perlanggaran di sini.
pada 152.
Dan anda akan melihat kita dicipta senarai berpaut jauh daripada itu.
Sekali lagi, jadual hash chaining berasingan pendekatan bukan yang anda
perlu mengambil masalah yang dibentuk enam tetapi adalah salah satu yang banyak
pelajar cenderung untuk mengambil.
Maka pada nota itu, marilah kita bercakap secara ringkas sebelum kita kepala keluar tentang masalah enam,
dan kemudian saya akan berkongsi cerita dengan anda.
Kami mempunyai tiga minit.
>> Masalah ditetapkan enam.
Anda mempunyai empat fungsi -
beban, daftar, saiz, dan memunggah.
Beban -
baik, kami telah pergi lebih beban tadi.
Kami menarik beban di atas kapal.
Dan kami pun mula pengekodan banyak memasukkan ke dalam senarai berpaut.
Jadi beban tidak lebih daripada apa yang kita baru sahaja telah lakukan.
>> Semak sekali anda mempunyai sesuatu yang dimuatkan.
Ia proses yang sama seperti ini.
Yang sama dua bahagian pertama di mana anda membuang sesuatu ke dalam fungsi hash
dan mendapatkan nilainya.
Tetapi sekarang kita tidak memasukkan ia.
Sekarang kita sedang mencari untuk itu.
Saya contoh kod bertulis untuk mencari sesuatu dalam senarai berpaut.
Saya menggalakkan anda untuk mengamalkan itu.
Tetapi gerak hati mencari sesuatu yang agak serupa dengan memasukkan sesuatu.
Malah, kami menarik gambar mencari sesuatu dalam senarai berpaut, bergerak
melalui sehingga anda sampai ke akhir.
Dan jika anda mendapat ke akhir dan tidak dapat merasa, maka ia bukan di sana.
Jadi, itu cek, pada asasnya.
>> Seterusnya adalah saiz.
Mari kita skip saiz.
Akhir sekali, anda telah memunggah.
Memunggah adalah salah satu kami tidak disediakan di papan atau dikod yet.
Tetapi saya menggalakkan anda untuk mencuba pengekodan ia dalam sampel dikaitkan contoh senarai kami.
Tetapi memunggah intuitif adalah sama dengan percuma -
atau Maksud saya adalah sama dengan cek.
Kecuali sekarang setiap kali anda akan melalui, anda tidak hanya memeriksa untuk
melihat jika anda mempunyai nilai anda di sana.
Tetapi anda mengambil nod itu dan membebaskan ia, pada asasnya.
Itulah yang memunggah meminta anda melakukan.
Segala-galanya percuma anda malloced.
Jadi, anda akan melalui seluruh senarai sekali lagi, melalui seluruh hash
meja lagi.
Kali ini tidak menyemak untuk melihat apa yang ada.
Hanya membebaskan apa yang ada.
>> Dan akhirnya saiz.
Saiz perlu dilaksanakan.
Jika anda tidak melaksanakan saiz -
Saya akan mengatakan ia seperti ini.
Jika anda tidak melaksanakan saiz betul-betul satu baris kod termasuk
kembali pernyataan, anda melakukan saiz dengan tidak betul.
Oleh itu, saiz pasti, bagi reka bentuk penuh mata, anda melakukannya betul-betul satu
baris kod, termasuk penyata pulangan.
>> Dan tidak berkemas lagi, Akchar.
Memerang bersemangat.
Saya mahu mengucapkan terima kasih guys untuk datang ke bahagian.
Mempunyai Happy Halloween.
Ini adalah pakaian saya.
Saya akan memakai ini pada hari Khamis jika saya melihat anda pada waktu pejabat.
Dan jika anda ingin tahu tentang beberapa lebih latar belakang untuk pakaian ini, berasa
bebas untuk menyemak 2011 seksyen untuk cerita mengenai kenapa saya
memakai pakaian labu.
Dan ia adalah satu cerita sedih.
Jadi pastikan anda mempunyai beberapa tisu berdekatan.
Tetapi pada itu, jika anda mempunyai sebarang soalan saya akan melekat di sekeliling
di luar selepas seksyen.
Nasib baik pada masalah set enam.
Dan seperti biasa, jika anda mempunyai sebarang soalan, beritahu saya.