>> JASON Hirschhorn: Selamat Datang everyone ke Bagian Tujuh.
Kami berada dalam minggu tujuh kursus.
Dan Kamis mendatang adalah Halloween jadi saya
berpakaian seperti labu.
Saya tidak bisa membungkuk dan mengenakan sepatu saya, jadi itu sebabnya aku
hanya mengenakan kaus kaki.
Saya juga tidak mengenakan apa pun di bawah ini, jadi saya tidak bisa melepasnya jika itu
mengganggu Anda.
Saya mohon maaf sebelumnya untuk itu.
Anda tidak perlu membayangkan apa yang terjadi.
Saya memakai boxer.
Jadi itu semua baik.
>> Aku punya cerita panjang tentang mengapa aku berpakaian seperti labu, tapi aku akan
simpan itu untuk nanti dalam bagian ini karena saya ingin memulai.
Kami memiliki banyak hal yang menarik untuk pergi selama seminggu ini.
Kebanyakan dari mereka berhubungan langsung dengan ini minggu masalah set, salah ejaan.
Kita akan terjadi lebih terkait daftar dan tabel hash
untuk seluruh bagian.
Aku meletakkan daftar ini setiap minggu, daftar sumber daya bagi Anda untuk membantu Anda dengan
materi kursus ini.
Jika bingung atau jika mencari beberapa informasi lebih lanjut, memeriksa salah satu
sumber daya tersebut.
>> Sekali lagi, pset6 adalah salah eja, minggu ini pset.
Dan itu juga mendorong Anda, dan saya mendorong Anda, untuk menggunakan beberapa lainnya
sumber daya khusus untuk pset ini.
Secara khusus, tiga saya sudah terdaftar di layar -
gdb, yang kita sudah akrab dengan dan telah menggunakan untuk sementara waktu sekarang, adalah
akan sangat membantu minggu ini.
Jadi saya menempatkan bahwa di sini.
Tapi setiap kali Anda bekerja dengan C, Anda harus selalu menggunakan gdb untuk
men-debug program Anda.
Minggu ini juga Valgrind.
Apakah ada yang tahu apa yang Valgrind tidak?
>> AUDIENCE: Ia memeriksa kebocoran memori?
>> JASON Hirschhorn: Valgrind memeriksa kebocoran memori.
Jadi jika Anda malloc sesuatu dalam Anda Program, Anda meminta untuk memori.
Pada akhir program, Anda harus untuk menulis gratis pada semua yang anda sudah
malloced untuk memberikan memori kembali.
Jika Anda tidak menulis gratis di akhir dan program anda datang ke kesimpulan,
semuanya akan secara otomatis dibebaskan.
Dan untuk program kecil, itu tidak begitu besar kesepakatan.
Tetapi jika Anda sedang menulis berjalan lagi program yang tidak berhenti,
tentu, dalam beberapa menit atau beberapa detik, maka kebocoran memori
bisa menjadi masalah besar.
>> Jadi untuk pset6, harapan adalah bahwa Anda akan memiliki nol kebocoran memori dengan
program anda.
Untuk memeriksa kebocoran memori, jalankan Valgrind dan itu akan memberi Anda beberapa nice
Output membiarkan Anda tahu apakah atau tidak semuanya gratis.
Kita akan berlatih dengan nanti hari ini, mudah-mudahan.
>> Akhirnya, perintah diff.
Anda menggunakan sesuatu yang mirip dengan itu di pset5 dengan alat mengintip.
Memungkinkan Anda untuk melihat ke dalam.
Anda juga digunakan diff, juga, per masalah set spec.
Tapi dalam memungkinkan Anda untuk membandingkan dua file.
Anda bisa membandingkan file bitmap dan Info header dari solusi staf dan
solusi Anda dalam pset5 jika Anda memilih untuk menggunakannya.
Diff akan memungkinkan Anda untuk melakukan itu, juga.
Anda dapat membandingkan jawaban yang benar untuk masalah minggu ini diatur untuk jawaban Anda
dan melihat apakah itu garis atas atau lihat mana kesalahan.
>> Jadi mereka adalah tiga alat yang baik yang Anda harus menggunakan selama seminggu ini, dan
pasti memeriksa program Anda dengan tiga alat ini
sebelum berbalik masuk
Sekali lagi, seperti yang telah saya sebutkan setiap minggu, jika Anda memiliki umpan balik bagi saya - baik
positif dan konstruktif -
merasa bebas untuk menuju ke situs web di bagian bawah slide ini
dan masukan sana.
Saya sangat menghargai dan semua umpan balik.
Dan jika Anda memberi saya hal-hal tertentu yang Dapat saya lakukan untuk memperbaiki atau bahwa aku
baik-baik bahwa Anda ingin saya untuk terus, saya mengambil ke jantung dan
benar-benar berusaha keras untuk mendengarkan umpan balik Anda.
Saya tidak bisa menjanjikan saya akan melakukan segalanya, meskipun, seperti memakai
labu kostum setiap minggu.
>> Jadi kita akan menghabiskan sebagian besar bagian, seperti yang saya sebutkan, berbicara tentang
daftar terhubung dan tabel hash, yang akan langsung berlaku untuk
permasalahan yang minggu ini.
Daftar link kita akan pergi ke relatif cepat karena kita telah menghabiskan sedikit adil
waktu akan lebih dari itu dalam bagian.
Dan jadi kami akan mendapatkan langsung ke coding masalah untuk daftar terkait.
Dan kemudian pada akhirnya kita akan berbicara tentang hash tabel dan bagaimana mereka berlaku untuk ini
Masalah minggu ditetapkan.
>> Anda telah melihat kode ini sebelumnya.
Ini adalah sebuah struct, dan itu mendefinisikan sesuatu yang baru yang disebut node.
Dan di dalam sebuah node ada bilangan bulat di sini dan ada pointer ke
node lain.
Kami telah melihat ini sebelumnya.
Ini telah datang untuk beberapa minggu sekarang.
Ini menggabungkan pointer, yang kita sudah bekerja dengan, dan structs, yang memungkinkan
kita untuk menggabungkan dua berbeda hal menjadi satu jenis data.
>> Ada banyak hal yang terjadi di layar.
Tapi semua itu harus relatif akrab dengan Anda.
Pada baris pertama, kita menyatakan node baru.
Dan kemudian di dalam simpul baru, saya menetapkan integer dalam simpul tersebut ke salah satu.
Kita lihat pada baris berikutnya saya melakukan printf perintah, tapi aku sudah berwarna abu-abu
perintah printf karena benar-benar bagian penting adalah baris ini di sini -
new_node.n.
Apa arti titik?
>> AUDIENCE: Pergi ke node dan menilai nilai n untuk itu.
>> JASON Hirschhorn: Itu tepat.
Dot berarti mengakses bagian n node baru ini.
Baris berikutnya ini melakukan apa?
Michael.
>> AUDIENCE: Ini menciptakan node lain yang akan menunjuk ke simpul baru.
>> JASON Hirschhorn: Jadi tidak membuat node baru.
Ini menciptakan apa?
>> AUDIENCE: Sebuah pointer.
>> JASON Hirschhorn: Sebuah pointer ke node, seperti yang ditunjukkan oleh node ini * sini.
Jadi menciptakan pointer ke node.
Dan simpul yang itu menunjuk untuk, Michael?
>> AUDIENCE: simpul baru?
>> JASON Hirschhorn: simpul baru.
Dan itu menunjuk sana karena kita sudah diberikan alamat node baru.
Dan sekarang di baris ini kita melihat dua cara yang berbeda
mengungkapkan hal yang sama.
Dan saya ingin menunjukkan bagaimana dua hal yang sama.
Pada baris pertama, kita dereference pointer.
Jadi kami pergi ke node.
Itulah yang berarti bintang ini.
Kita telah melihat bahwa sebelum dengan pointer.
Pergi ke simpul tersebut.
Itu dalam tanda kurung.
Dan kemudian mengakses melalui operator dot elemen n dari simpul tersebut.
>> Jadi yang mengambil sintaks kami melihat di sini dan sekarang
menggunakannya dengan pointer.
Tentu saja, itu akan agak sibuk jika Anda sedang menulis mereka kurung -
bahwa bintang dan dot.
Ia mendapat sedikit sibuk.
Jadi kita memiliki beberapa gula sintaksis.
Dan baris ini di sini -
ptr_node-> n.
Yang melakukan hal yang persis sama.
Jadi dua baris kode yang setara dan akan melakukan
hal yang sama persis.
>> Tapi aku ingin menunjukkan mereka sebelum kita melangkah lebih jauh sehingga Anda memahami
yang benar-benar hal ini di sini adalah hanya sintaksis gula untuk dereferencing
pointer dan kemudian pergi ke n bagian dari struct itu.
Setiap pertanyaan tentang geser ini?
OK.
>> Jadi kita akan pergi melalui beberapa operasi yang dapat Anda lakukan pada
terkait daftar.
Sebuah linked list, ingat, adalah serangkaian node yang mengarah ke satu sama lain.
Dan kita biasanya mulai dengan pointer disebut kepala, umumnya, yang menunjuk ke
hal pertama dalam daftar.
Jadi pada baris pertama di sini, kita memiliki L asli pertama kami.
Jadi hal yang dapat Anda pikirkan - ini teks di sini Anda dapat anggap sebagai
hanya pointer kita sudah disimpan suatu tempat yang poin
ke elemen pertama.
Dan dalam linked list ini kami memiliki empat node.
Setiap node adalah sebuah kotak besar.
Semakin besar box dalam besar box adalah bagian integer.
Dan kemudian kita memiliki bagian pointer.
>> Kotak-kotak ini tidak tertarik pada skala karena seberapa besar
integer dalam byte?
Seberapa besar sekarang?
Empat.
Dan seberapa besar itu pointer?
Empat.
Jadi benar-benar, jika kita menggambar ini untuk skala kedua kotak
akan menjadi ukuran yang sama.
Dalam kasus ini, kita ingin menyisipkan sesuatu ke dalam linked list.
Sehingga Anda dapat melihat di sini kita memasukkan Kami melintasi lima melalui
linked list, menemukan di mana lima pergi, dan kemudian masukkan.
>> Mari kita memecah itu dan pergi sedikit lebih lambat.
Aku akan menunjuk ke papan tulis.
Jadi kita memiliki simpul kami lima yang kami telah dibuat dalam mallocs.
Mengapa semua orang tertawa?
Just kidding.
OK.
Jadi kita sudah malloced lima.
Kami telah membuat simpul ini tempat lain.
Kami memilikinya siap untuk pergi.
Kita mulai di depan daftar kami dengan dua.
Dan kita ingin menyisipkan secara terurut.
>> Jadi jika kita melihat dua dan kami ingin menempatkan dalam lima, apa yang kita lakukan ketika kita melihat
sesuatu yang kurang dari kami?
Apa?
Kami ingin memasukkan lima ke ini linked list, menjaganya agar tetap diurutkan.
Kita melihat nomor dua.
Jadi apa yang kita lakukan?
Marcus?
>> AUDIENCE: Call pointer ke node berikutnya.
>> JASON Hirschhorn: Dan mengapa kita pergi ke yang berikutnya?
>> AUDIENCE: Karena itu adalah node berikutnya dalam daftar.
Dan kita hanya tahu bahwa lokasi lain.
>> JASON Hirschhorn: Dan lima besar dari dua, pada khususnya.
Karena kami ingin tetap diurutkan.
Jadi lima lebih besar dari dua.
Jadi kita beralih ke yang berikutnya.
Dan sekarang kita mencapai empat.
Dan apa yang terjadi ketika kita mencapai empat?
>> Lima lebih besar dari empat.
Jadi kita terus berjalan.
Dan sekarang kita berada di enam.
Dan apa yang kita lihat di enam?
Ya, Carlos?
>> AUDIENCE: Enam lebih besar dari lima.
>> JASON Hirschhorn: Six adalah lebih dari lima.
Jadi, di sanalah kita inginkan untuk memasukkan lima.
Namun, perlu diingat bahwa jika kita hanya memiliki satu pointer di sini -
ini adalah pointer ekstra kami yang melintasi melalui daftar.
Dan kita menunjuk ke enam.
Kami sudah kehilangan jejak apa datang sebelum enam.
Jadi jika kita ingin memasukkan sesuatu ke daftar ini menjaga disortir, kita
mungkin perlu berapa banyak pointer?
>> AUDIENCE: Dua.
>> JASON Hirschorn: Dua.
Satu untuk melacak arus satu dan satu untuk melacak
sebelumnya.
Ini hanya sebuah daftar tunggal linked.
Ini hanya pergi satu arah.
Jika kita memiliki daftar ganda terkait, di mana semuanya menunjuk ke hal yang
setelah dan sebelum hal itu, maka kita tidak perlu melakukan itu.
Tapi dalam kasus ini kita tidak ingin kehilangan jejak dari apa yang datang sebelum kita dalam hal
kita harus memasukkan lima tempat di tengah.
Katakanlah kita memasukkan sembilan.
Apa yang akan terjadi ketika kita harus delapan?
>> AUDIENCE: Anda harus mendapatkan titik nol.
Alih-alih memiliki titik nol Anda akan memiliki untuk menambahkan elemen dan kemudian memiliki
menunjuk ke sembilan.
>> JASON Hirschorn: Tepat.
Jadi kita mendapatkan delapan.
Kami mencapai akhir daftar karena ini menunjuk ke null.
Dan sekarang, daripada harus menunjuk ke nol kita agar menunjuk ke simpul baru.
Dan kami mengatur pointer di node baru kami ke null.
Apakah Ada yang punya pertanyaan tentang memasukkan?
Bagaimana jika saya tidak peduli menjaga daftar diurutkan?
>> AUDIENCE: Tempelkan di awal atau akhir.
>> JASON Hirschorn: Tempelkan di awal atau akhir.
Mana yang harus kita lakukan?
Bobby?
Mengapa akhir?
>> AUDIENCE: Karena awal sudah diisi.
>> JASON Hirschorn: OK.
Awal sudah diisi.
Siapa yang ingin membantah Bobby.
Marcus.
>> AUDIENCE: Yah Anda mungkin ingin tongkat itu di awal karena
sebaliknya jika Anda menaruhnya di akhirnya Anda harus
melintasi seluruh daftar.
>> JASON Hirschorn: Tepat.
Jadi, jika kita berpikir tentang runtime, runtime memasukkan di akhir
akan n, ukuran ini.
Apa O runtime besar memasukkan di awal?
Waktu yang konstan.
Jadi, jika Anda tidak peduli tentang menjaga sesuatu yang diurutkan, jauh lebih baik untuk hanya
masukkan pada awal daftar ini.
Dan itu bisa dilakukan dalam waktu yang konstan.
>> OK.
Operasi berikutnya adalah menemukan, yang lain - kami telah diutarakan ini sebagai pencarian.
Tapi kita akan melihat melalui linked list untuk beberapa objek.
Kalian telah melihat kode untuk pencarian sebelumnya di kuliah.
Tapi kami semacam hanya melakukannya dengan memasukkan, atau setidaknya memasukkan
sesuatu yang diurutkan.
Anda melihat melalui, akan node dengan node, sampai Anda menemukan nomor yang Anda
cari.
Apa yang terjadi jika Anda mencapai akhir daftar?
Katakanlah Saya mencari sembilan dan saya mencapai akhir daftar.
Apa yang kita lakukan?
>> AUDIENCE: Kembali palsu?
>> JASON Hirschorn: Kembali palsu.
Kami tidak menemukan itu.
Jika Anda mencapai akhir daftar dan Anda tidak menemukan nomor Anda
mencari, itu tidak di sana.
Pertanyaan tentang menemukan?
Jika ini adalah daftar diurutkan, apa yang akan berbeda untuk pencarian kita?
Ya.
>> AUDIENCE: Ini akan menemukan nilai pertama yang lebih besar dari satu
Anda sedang mencari dan kemudian kembali palsu.
>> JASON Hirschorn: Tepat.
Jadi jika daftar diurutkan, jika kita bisa sesuatu yang lebih besar daripada apa
kita cari, kita tidak perlu terus ke akhir daftar.
Kita bisa pada saat itu kembali palsu karena kita tidak akan menemukannya.
Pertanyaannya sekarang, kita sudah bicara tentang menyimpan daftar diurutkan terkait,
menjaga mereka unsorted.
Itu akan menjadi sesuatu yang Anda mungkin akan harus berpikir tentang
ketika coding masalah menetapkan lima jika Anda memilih tabel hash dengan terpisah
chaining pendekatan, yang akan kita bicarakan nanti.
>> Tapi apakah itu layak untuk menjaga daftar disortir dan kemudian dapat mungkin memiliki
pencarian lebih cepat?
Atau lebih baik untuk cepat memasukkan sesuatu dalam runtime konstan tetapi kemudian
memiliki lagi mencari?
Itu tradeoff di sana bahwa Anda harus memutuskan apa yang lebih tepat
untuk masalah khusus Anda.
Dan ada belum tentu satu jawabannya benar.
Tapi itu pasti keputusan yang Anda dapatkan untuk membuat, dan mungkin baik untuk membela
bahwa dalam, katakanlah, satu atau dua komentar mengapa Anda memilih satu atas yang lain.
>> Akhirnya, menghapus.
Kami telah melihat menghapus.
Hal ini mirip dengan pencarian.
Kami mencari elemen.
Katakanlah kita mencoba untuk menghapus enam.
Jadi kita menemukan enam di sini.
Hal yang harus kita memastikan bahwa kita lakukan adalah bahwa apa pun yang menunjuk ke
enam - seperti yang kita lihat pada langkah dua di sini -
apa pun yang menunjuk ke enam kebutuhan untuk melewatkan enam sekarang dan diubah menjadi
apapun enam menunjuk ke.
Kami tidak ingin pernah yatim sisa daftar kami karena lupa untuk mengatur bahwa
pointer sebelumnya.
Dan kemudian kadang-kadang, tergantung pada program, mereka hanya akan
menghapus node ini sepenuhnya.
Kadang-kadang Anda akan ingin untuk kembali nilai yang ada di node ini.
Jadi itulah cara menghapus bekerja.
Setiap pertanyaan tentang menghapus?
>> AUDIENCE: Jadi, jika Anda akan menghapus itu, apakah Anda hanya menggunakan gratis karena
mungkin itu malloced?
>> JASON Hirschorn: Jika Anda ingin membebaskan sesuatu yang tepat dan Anda
malloced itu.
Katakanlah kita ingin mengembalikan nilai ini.
Kita mungkin kembali enam dan kemudian bebas node ini dan panggilan bebas di atasnya.
Atau kita mungkin akan menelepon bebas pertama dan kemudian kembali enam.
>> OK.
Jadi mari kita lanjutkan untuk berlatih coding.
Kita akan kode tiga fungsi.
Yang pertama disebut insert_node.
Jadi Anda memiliki kode yang saya email Anda, dan jika Anda menonton ini nantinya
Anda dapat mengakses kode dalam linked.c di situs CS50.
Namun dalam linked.c, ada beberapa kode kerangka yang sudah
telah ditulis untuk Anda.
Dan kemudian ada beberapa fungsi Anda perlu menulis.
>> Pertama kita akan menulis insert_node.
Dan apa insert_node tidak yaitu menyisipkan integer.
Dan Anda memberikan integer menjadi linked list.
Dan khususnya, Anda perlu untuk menjaga daftar diurutkan
dari terkecil hingga terbesar.
Juga, Anda tidak ingin menyisipkan duplikat.
Akhirnya, karena Anda dapat melihat insert_node mengembalikan bool.
Jadi kau harus membiarkan pengguna tahu apakah insert itu
sukses dengan kembali benar atau salah.
Pada akhir program ini -
dan untuk tahap ini Anda tidak perlu khawatir tentang membebaskan apa pun.
Jadi semua yang Anda lakukan adalah mengambil integer dan memasukkannya ke dalam daftar.
>> Itulah apa yang saya minta Anda lakukan sekarang.
Sekali lagi, di linked.c, yang Anda semua memiliki, adalah kode kerangka.
Dan Anda harus melihat ke bagian bawah fungsi sampel deklarasi.
Namun, sebelum masuk ke coding di C, saya sangat mendorong Anda untuk pergi
melalui langkah-langkah kami sudah berlatih setiap minggu.
Kami sudah melewati gambar ini.
Jadi, Anda harus memiliki beberapa pemahaman bagaimana ini bekerja.
Tapi saya akan mendorong Anda untuk menulis beberapa pseudocode sebelum menyelam masuk
Dan kita akan pergi ke pseudocode sebagai sebuah kelompok.
Dan kemudian setelah Anda telah menulis Anda pseudocode, dan setelah kami telah menulis kami
pseudocode sebagai sebuah kelompok, Anda dapat masuk ke coding di C.
>> Sebagai kepala, fungsi insert_node mungkin adalah paling sulit dari
tiga kita akan menulis karena saya menambahkan beberapa kendala tambahan untuk
pemrograman Anda, khususnya yang Anda tidak akan memasukkan setiap
duplikat dan bahwa daftar harus tetap diurutkan.
Jadi ini adalah program non-sepele bahwa Anda perlu kode.
Dan mengapa tidak Anda mengambil 5-7 menit hanya untuk mendapatkan bekerja pada
pseudocode dan kode.
Dan kemudian kita akan mulai akan sebagai sebuah kelompok.
Sekali lagi, jika Anda memiliki pertanyaan hanya mengangkat tangan Anda dan saya akan datang sekitar.
.
>> Kami juga umumnya melakukan ini -
atau saya tidak secara eksplisit mengatakan Anda dapat bekerja dengan orang-orang.
Tapi jelas, saya sangat mendorong Anda, jika Anda memiliki pertanyaan, meminta
tetangga duduk di samping Anda atau bahkan bekerja dengan seseorang
lain jika Anda ingin.
Ini tidak harus menjadi seorang individu Kegiatan diam.
>> Mari kita mulai dengan menulis beberapa pseudocode di papan tulis.
Siapa yang bisa memberi saya baris pertama pseudocode untuk program ini?
Untuk fungsi ini, agak - insert_node.
Alden?
>> AUDIENCE: Jadi, hal pertama yang saya lakukan adalah membuat pointer baru ke simpul dan saya
diinisialisasi itu menunjuk ke sama hal yang menunjuk ke daftar.
>> JASON Hirschorn: OK.
Jadi, Anda sedang menciptakan sebuah pointer baru ke dalam daftar, bukan ke node.
>> AUDIENCE: Benar.
Ya.
>> JASON Hirschorn: OK.
Dan kemudian apa yang kita ingin lakukan?
Apa setelah itu?
Bagaimana dengan node?
Kami tidak memiliki node.
Kami hanya memiliki nilai.
Jika kita ingin menyisipkan node, apa yang kita perlu melakukan terlebih dahulu sebelum kita bahkan dapat
berpikir tentang memasukkan itu?
>> AUDIENCE: Oh, maaf.
kita perlu malloc ruang untuk node.
>> JASON Hirschorn: Excellent.
Mari kita lakukan -
OK.
Tidak dapat mencapai tinggi itu.
OK.
Kita akan turun, dan kemudian kita menggunakan dua kolom.
Aku tidak bisa pergi itu -
OK.
Buat node baru.
Anda dapat membuat pointer lain untuk daftar atau Anda hanya dapat menggunakan daftar seperti yang ada.
Anda tidak benar-benar perlu melakukan itu.
>> Jadi kita membuat node baru.
Besar.
Itulah yang kami lakukan pertama.
Apa selanjutnya?
>> AUDIENCE: Tunggu.
Haruskah kita membuat node baru sekarang atau kita harus menunggu untuk memastikan bahwa
tidak ada duplikat dari node pada daftar sebelum kita menciptakannya?
>> JASON Hirschorn: Pertanyaan yang bagus.
Mari kita terus itu untuk nanti karena sebagian besar waktu kita akan menciptakan
node baru.
Jadi kita akan menjaga itu di sini.
Tapi itu pertanyaan yang bagus.
Jika kita menciptakannya dan kita menemukan duplikat, apa yang harus
kita lakukan sebelum kembali?
>> AUDIENCE: Bebaskan itu.
>> JASON Hirschorn: Ya.
Mungkin membebaskannya.
OK.
Apa yang kita lakukan setelah kita membuat node baru?
Annie?
>> AUDIENCE: Kami menempatkan nomor di node?
>> JASON Hirschorn: Tepat.
Kami menempatkan nomor - kita malloc ruang.
Aku akan meninggalkan semua sebagai satu baris.
Tapi kau benar.
Kami malloc ruang, dan kemudian kami menempatkan nomor masuk
Kita bahkan dapat mengatur pointer bagian dari itu ke null.
Itu tepat sekali.
Lalu bagaimana dengan setelah itu?
Kami menggambar gambar ini di papan tulis.
Jadi apa yang kita lakukan?
>> AUDIENCE: Kami pergi melalui daftar.
>> JASON Hirschorn: Pergi melalui daftar.
OK.
Dan apa yang kita periksa di setiap node.
Kurt, apa yang kita periksa untuk di setiap node?
>> AUDIENCE: Lihat apakah nilai n simpul yang lebih besar dari nilai n
node kami.
>> JASON Hirschorn: OK.
Aku akan lakukan -
yeah, OK.
Jadi n -
Aku akan mengatakan jika nilai lebih besar dari node ini, maka apa yang kita lakukan?
>> AUDIENCE: Nah, kemudian kita masukkan hal yang benar sebelum itu.
>> JASON Hirschorn: OK.
Jadi jika itu lebih besar dari ini, maka kita ingin menyisipkan.
Tapi kami ingin memasukkan dengan benar sebelum karena kami juga akan perlu
mencatat, kemudian, dari apa yang sebelumnya.
Jadi masukkan sebelumnya.
Jadi kita mungkin melewatkan sesuatu sebelumnya pada.
Kita mungkin perlu menjaga melacak apa yang terjadi.
Tapi kita akan kembali ke sana.
Jadi apa nilai kurang dari?
Kurt, apa yang kita lakukan jika nilai kurang dari?
>> AUDIENCE: Kemudian Anda hanya terus kecuali itu adalah yang terakhir.
>> JASON Hirschorn: aku seperti itu.
Jadi pergi ke node berikutnya.
Kecuali itu yang terakhir -
kita mungkin memeriksa untuk itu dalam hal kondisi.
Tapi ya, node berikutnya.
Dan yang terlalu rendah, jadi kami akan pindah ke sini.
Tapi jika -
bisa semua orang melihat ini?
Jika kita sama apa yang kita lakukan?
Jika nilai kita mencoba untuk memasukkan sama dengan nilai simpul ini?
Ya?
>> AUDIENCE: [Tak terdengar].
>> JASON Hirschorn: Ya.
Mengingat ini -
Marcus benar.
Kita bisa mungkin dilakukan sesuatu yang berbeda.
Tetapi mengingat bahwa kami telah menciptakannya, di sini kita harus membebaskan dan kemudian kembali.
Oh boy.
Apakah itu lebih baik?
Bagaimana itu?
OK.
Gratis dan kemudian apa yang kita kembali, [Tak terdengar]?
OK.
Apakah kita hilang apa?
Jadi di mana kita melacak dari node sebelumnya?
>> AUDIENCE: Saya pikir itu akan pergi setelah membuat node baru.
>> JASON Hirschorn: OK.
Jadi di awal kita akan mungkin -
yeah, kita dapat membuat pointer ke baru node, seperti simpul pointer sebelumnya dan
node pointer saat ini.
Jadi mari kita masukkan itu di sini.
Buat saat ini dan sebelumnya pointer ke node.
Tapi ketika kita menyesuaikan mereka pointer?
Di mana kita melakukan itu dalam kode?
Jeff?
>> AUDIENCE: - kondisi nilai?
>> JASON Hirschorn: Yang orang tertentu?
>> AUDIENCE: Aku hanya bingung.
Jika nilai lebih besar dari node ini, bukankah itu berarti bahwa Anda ingin pergi
ke simpul berikutnya?
>> JASON Hirschhorn: Jadi, jika nilai kita adalah lebih besar dari nilai node ini.
>> AUDIENCE: Ya, maka Anda akan ingin pergi lebih bawah garis, kan?
>> JASON Hirschhorn: Benar.
Jadi kita tidak memasukkannya di sini.
Jika nilai kurang dari node ini, maka kita pergi ke node berikutnya - atau kemudian kita
masukkan sebelumnya.
>> AUDIENCE: Tunggu, yang ini node dan yang nilai?
>> JASON Hirschhorn: Pertanyaan yang bagus.
Nilai per definisi fungsi ini adalah apa yang kita diberikan.
Jadi nilai adalah nomor kita diberikan.
Jadi jika nilai kurang dari ini node, kita perlu waktu untuk memasukkan.
Jika nilai lebih besar dari node ini, kita pergi ke node berikutnya.
Dan kembali ke pertanyaan awal, meskipun, di mana -
>> AUDIENCE: Jika nilai lebih besar dari node ini.
>> JASON Hirschhorn: Dan apa yang kita lakukan di sini?
Manis.
Itu benar.
Aku hanya akan menulis Update pointer.
Tapi ya, dengan yang sekarang Anda akan memperbaruinya ke
menunjuk ke yang berikutnya.
Ada lagi kita hilang?
Jadi aku akan mengetik ini kode ke gedit.
Dan sementara aku melakukan ini, Anda dapat memiliki beberapa menit lagi untuk bekerja pada coding
ini di C.
>> Jadi saya memiliki masukan pseudocode tersebut.
Sebuah catatan singkat sebelum kita mulai.
Kita mungkin tidak dapat sepenuhnya menyelesaikan ini dalam semua
tiga fungsi tersebut.
Ada solusi yang tepat untuk mereka bahwa saya akan mengirimkan email kepada kalian
setelah bagian, dan akan diposting pada CS50.net.
Jadi saya tidak mendorong Anda untuk pergi melihat bagian.
Saya mendorong Anda untuk mencoba ini pada Anda sendiri, dan kemudian menggunakan praktek
masalah untuk memeriksa jawaban Anda.
Ini semuanya telah dirancang untuk erat berhubungan dengan dan mematuhi apa
yang harus Anda lakukan pada set masalah.
Jadi saya mendorong Anda untuk berlatih ini Anda sendiri dan kemudian menggunakan kode untuk
memeriksa jawaban Anda.
Karena aku ingin pindah ke hash tabel di beberapa titik di bagian.
Jadi kita mungkin tidak mendapatkan melalui semua itu.
Tapi kita akan melakukan sebanyak yang kami bisa sekarang.
>> OK.
Mari kita mulai.
Asam, bagaimana kita membuat node baru?
>> AUDIENCE: Anda struct *.
>> JASON Hirschhorn: Jadi kita memiliki di sini.
Oh, maaf.
Kau mengatakan struct *.
>> AUDIENCE: Dan kemudian [? jenis?] node atau simpul c.
>> JASON Hirschhorn: OK.
Aku akan menyebutnya new_node jadi kita bisa tetap konsisten.
>> AUDIENCE: Dan Anda ingin mengatur bahwa untuk kepala, simpul pertama.
>> JASON Hirschhorn: OK.
Jadi sekarang ini untuk menunjuk - jadi ini belum membuat node baru belum.
Ini hanya menunjuk ke node pertama dalam daftar.
Bagaimana cara membuat simpul baru?
Jika saya perlu ruang untuk membuat node baru.
Malloc.
Dan seberapa besar?
>> AUDIENCE: Ukuran struct.
>> JASON Hirschhorn: The ukuran struct.
Dan apa yang disebut struct?
>> AUDIENCE: Node?
>> JASON Hirschhorn: Node.
Jadi malloc (sizeof (node)); memberi kita ruang.
Dan baris ini -
satu hal yang salah pada baris ini.
Apakah new_node pointer ke struct?
Itu nama generik.
Apa itu -
node, tepatnya.
Ini simpul *.
Dan apa yang kita lakukan setelah kami malloc sesuatu, Asan?
Apa hal pertama yang kita lakukan?
Bagaimana jika tidak bekerja?
>> AUDIENCE: Oh, periksa apakah menunjuk ke node?
>> JASON Hirschhorn: Tepat.
Jadi jika Anda new_node sama equals null, apa yang kita lakukan?
Ini mengembalikan sebuah bool, fungsi ini.
Tepat.
Terlihat bagus.
Apa saja untuk menambahkan ada?
Kami akan menambahkan hal-hal di akhir.
Tapi itu sejauh ini terlihat baik.
Buat pointer saat ini dan sebelumnya.
Michael, bagaimana saya melakukan ini?
>> AUDIENCE: Anda akan memiliki untuk melakukan simpul *.
Anda harus membuat satu tidak untuk new_node tetapi untuk
node sudah kita miliki.
>> JASON Hirschhorn: OK.
Jadi node saat kita berada di.
Aku akan menelepon Curr itu.
Baik.
Kami telah memutuskan kami ingin menjaga dua karena kita perlu tahu
apa sebelum.
Apa yang mereka bisa diinisialisasi?
>> AUDIENCE: Nilai mereka dalam daftar kami.
>> JASON Hirschhorn: Jadi apa Hal pertama pada daftar kami?
Atau bagaimana kita tahu mana awal daftar kami adalah?
>> AUDIENCE: Apakah tidak lulus ke dalam fungsi?
>> JASON Hirschhorn: Benar.
Ini disahkan pada di sini.
Jadi jika itu dilewatkan ke fungsi, mulai dari daftar, apa yang harus kita
mengatur arus yang sama ke?
>> AUDIENCE: Daftar.
>> JASON Hirschhorn: Daftar.
Itu tepat sekali.
Sekarang memiliki alamat awal daftar kami.
Dan bagaimana dengan sebelumnya?
>> AUDIENCE: Daftar minus satu?
>> JASON Hirschhorn: Ada apa-apa sebelumnya.
Jadi apa yang bisa kita lakukan untuk menunjukkan apa-apa?
>> AUDIENCE: Null.
>> JASON Hirschhorn: Ya.
Kedengarannya seperti ide yang baik.
Sempurna.
Terima kasih.
Pergi melalui daftar.
Constantine, berapa lama kita akan pergi untuk pergi melalui daftar?
>> AUDIENCE: Sampai Kita mencapai nol.
>> JASON Hirschhorn: OK.
Jadi jika, sementara, untuk loop.
Apa yang kita lakukan?
>> AUDIENCE: Mungkin untuk loop?
>> JASON Hirschhorn: Mari kita lakukan untuk loop.
OK.
>> AUDIENCE: Dan kita katakan untuk -
sampai pointer saat ini tidak sama dengan nol.
>> JASON Hirschhorn: Jadi jika kita tahu kondisi, bagaimana kita bisa menulis loop
didasarkan dari kondisi itu.
Apa jenis loop yang harus kita gunakan?
>> AUDIENCE: Sementara.
>> JASON Hirschhorn: Ya.
Itu lebih masuk akal berdasarkan off dari apa yang Anda katakan.
Jika kita hanya ingin pergi ke kita itu akan hanya tahu hal itu, akan membuat
akal untuk melakukan loop sementara.
Sementara saat ini tidak nol tidak sama, jika nilai kurang dari node ini.
Akshar, beri saya baris ini.
>> AUDIENCE: Jika saat ini-> n n kurang dari nilai.
Atau membalikkan itu.
Beralih braket itu.
>> JASON Hirschhorn: Maaf.
>> AUDIENCE: Mengubah braket.
>> JASON Hirschhorn: Jadi jika lebih besar dari nilai.
Karena itulah membingungkan dengan komentar di atas, aku akan melakukan itu.
Tapi ya.
Jika nilai kita kurang dari ini node, apa yang kita lakukan?
Oh.
Saya memilikinya di sini.
Masukkan sebelumnya.
OK.
Bagaimana kita melakukannya?
>> AUDIENCE: Apakah masih me?
>> JASON Hirschhorn: Ya.
>> AUDIENCE: Anda -
new_node-> berikutnya.
>> JASON Hirschhorn: Jadi apa itu akan sama?
>> AUDIENCE: Ini akan arus yang sama.
>> JASON Hirschhorn: Tepat.
Dan yang lain -
apa lagi yang kita perlu memperbarui?
>> AUDIENCE: Periksa apakah masa lalu sama dengan nol.
>> JASON Hirschhorn: Jika prev -
jadi jika prev sama dengan nol.
>> AUDIENCE: Itu berarti itu akan untuk menjadi kepala.
>> JASON Hirschhorn: Itu berarti itu menjadi kepala.
Jadi apa yang kita lakukan?
>> AUDIENCE: Kami melakukan kepala sama new_node.
>> JASON Hirschhorn: Kepala sama new_node.
Dan mengapa kepala di sini, tidak daftar?
>> AUDIENCE: Karena kepala global variabel, yang merupakan tempat awal.
>> JASON Hirschhorn: Manis.
OK.
Dan -
>> AUDIENCE: Maka Anda pun prev-> selanjutnya sama dengan new_node.
Dan kemudian Anda kembali benar.
>> JASON Hirschhorn: Di mana kami menetapkan new_node akhir?
>> AUDIENCE: Aku akan -
Saya menetapkan bahwa di awal.
>> JASON Hirschhorn: Jadi apa baris?
>> AUDIENCE: Setelah pernyataan jika memeriksa apakah itu dikenal.
>> JASON Hirschhorn: Di sini?
>> AUDIENCE: Saya akan melakukan new_node-> n sama dengan nilai.
>> JASON Hirschhorn: Kedengarannya bagus.
Mungkin masuk akal - kita tidak perlu tahu apa daftar kita berada di
karena kita hanya berurusan dengan satu daftar.
Jadi fungsi deklarasi yang lebih baik untuk ini hanya untuk menyingkirkan ini
sepenuhnya dan hanya memasukkan nilai ke kepala.
Kita bahkan tidak perlu tahu apa daftar kita masuk
Tapi aku akan tetap untuk saat ini dan kemudian mengubahnya setelah memperbarui
slide dan kode.
Sehingga terlihat bagus untuk saat ini.
Jika nilai - yang bisa melakukan baris ini?
Jika -
apa yang kita lakukan di sini, Noah.
>> AUDIENCE: Jika nilai lebih besar dari Curr-> n -
>> JASON Hirschhorn: Bagaimana kita pergi ke simpul berikutnya?
>> AUDIENCE: Curr-> n adalah sama dengan new_node.
>> JASON Hirschhorn: Jadi n adalah apa bagian dari struct?
Integer.
Dan new_node adalah pointer ke node.
Jadi apa bagian dari Curr harus kita update?
Jika tidak n, lalu apa bagian lain?
Noah, apa bagian lain.
>> AUDIENCE: Oh, berikutnya.
>> JASON Hirschhorn: Selanjutnya, tepatnya.
Tepat.
Berikutnya adalah yang benar.
Dan apa lagi yang kita butuhkan untuk memperbarui, Noah?
>> AUDIENCE: The pointer.
>> JASON Hirschhorn: Jadi kita diperbarui saat ini.
>> AUDIENCE: Sebelumnya-> berikutnya.
>> JASON Hirschhorn: Ya.
OK, kita akan berhenti.
Siapa yang dapat membantu kita di sini?
Manu, apa yang harus kita lakukan?
>> AUDIENCE: Anda harus mengatur itu sama dengan Curr-> berikutnya.
Tapi apakah itu sebelum baris sebelumnya.
>> JASON Hirschhorn: OK.
Ada lagi?
Akshar.
>> AUDIENCE: Saya tidak berpikir Anda dimaksudkan untuk mengubah Curr-> berikutnya.
Saya pikir Anda dimaksudkan untuk melakukan equals Curr Curr-> berikutnya untuk pergi ke simpul berikutnya.
>> JASON Hirschhorn: Jadi maaf, di mana?
Pada apa baris?
Baris ini?
>> AUDIENCE: Ya.
Membuat Curr sama Curr-> berikutnya.
>> JASON Hirschhorn: Jadi itu benar karena saat ini adalah
pointer ke node.
Dan kami ingin untuk menunjuk ke depan node yang semakin saat ini
menunjuk.
Curr sendiri memiliki berikutnya.
Tetapi jika kita untuk memperbarui curr.next, kita akan memperbarui catatan yang sebenarnya
sendiri, tidak di mana ini pointer menunjuk.
Bagaimana dengan baris ini, meskipun.
Avi?
>> AUDIENCE: Sebelumnya-> next sama Curr.
>> JASON Hirschhorn: Jadi sekali lagi, jika prev adalah pointer ke node, prev-> selanjutnya adalah
pointer yang sebenarnya dalam node.
Jadi ini akan memperbarui pointer dalam node ke Curr.
Kami tidak ingin memperbarui pointer dalam node.
Kami ingin memperbarui sebelumnya.
Jadi bagaimana kita melakukannya?
>> AUDIENCE: Ini hanya akan prev.
>> JASON Hirschhorn: Benar.
Sebelumnya adalah pointer ke node.
Sekarang kita mengubahnya ke pointer baru untuk node.
OK Mari kita bergerak turun.
Akhirnya, kondisi terakhir ini.
Jeff, apa yang kita lakukan di sini?
>> AUDIENCE: Jika nilai sama dengan Curr-> n.
>> JASON Hirschhorn: Maaf.
Oh ya ampun.
Apa?
Nilai == Curr-> n.
Apa yang kita lakukan?
>> AUDIENCE: Anda akan membebaskan new_node kami, dan kemudian Anda akan kembali palsu.
>> JASON Hirschhorn: Ini adalah apa yang kita tulis sejauh ini.
Apakah ada yang punya apa-apa menambahkan sebelum kita buat?
OK.
Mari kita coba.
Kontrol dapat mencapai akhir dari fungsi non-kekosongan.
Avi, apa yang terjadi?
>> AUDIENCE: Apakah Anda harus menempatkan kembali benar luar loop sementara?
>> JASON Hirschhorn: Saya tidak tahu.
Apakah kau ingin aku?
>> AUDIENCE: Sudahlah.
Tidak.
>> JASON Hirschhorn: Akshar?
>> AUDIENCE: Saya pikir Anda dimaksudkan untuk menempatkan return false pada akhir
dari while loop.
>> JASON Hirschhorn: Jadi di mana Anda ingin pergi?
>> AUDIENCE: Seperti luar loop sementara.
Jadi jika Anda keluar dari loop sementara yang berarti Anda telah mencapai akhir dan
tidak ada yang terjadi.
>> JASON Hirschhorn: OK.
Jadi apa yang kita lakukan di sini?
>> AUDIENCE: Anda kembali palsu ada juga.
>> JASON Hirschhorn: Oh, kami melakukannya di kedua tempat?
>> AUDIENCE: Ya.
>> JASON Hirschhorn: OK.
Haruskah kita pergi?
Oh ya ampun.
Maafkan aku.
Saya minta maaf atas layar.
Ini semacam panik pada kami.
Jadi pilih opsi.
Nol, per kode, berhenti program.
Satu menyisipkan sesuatu.
Mari kita memasukkan tiga.
Insert itu tidak berhasil.
Aku akan mencetak.
Saya tidak punya apa-apa.
OK.
Mungkin itu hanya kebetulan.
Masukkan satu.
Tidak berhasil.
OK.
Mari kita jalankan melalui GDB sangat cepat untuk memeriksa apa yang sedang terjadi.
>> Ingat gdb. / Nama Anda Program membuat kita menjadi GDB.
Apakah itu banyak untuk menangani?
The berkedip?
Mungkin.
Tutup mata Anda dan mengambil beberapa mendalam napas jika Anda bosan
untuk melihat hal itu.
Aku di GDB.
Apa hal pertama yang saya lakukan di GDB?
Kita harus mencari tahu apa yang terjadi di sini.
Mari kita lihat.
Kami memiliki enam menit untuk angka tahu apa yang terjadi.
Istirahat utama.
Lalu apa yang harus saya lakukan?
Carlos?
Jalankan.
OK.
Mari kita pilih opsi.
Dan apa N lakukan?
Berikutnya.
Ya.
>> AUDIENCE: Apakah Anda tidak menyebutkan -
kau tidak mengatakan bahwa kepala, itu diinisialisasi ke nol di awal.
Tapi kupikir kau bilang itu OK.
>> JASON Hirschhorn: Ayo - mari kita lihat di GDB, dan kemudian kita akan kembali.
Tapi kedengarannya seperti Anda sudah memiliki beberapa ide tentang apa yang terjadi.
Jadi kita ingin memasukkan sesuatu.
OK.
Kami telah memasukkan.
Silakan masukkan int.
Kami akan memasukkan tiga.
Dan kemudian aku di baris ini.
Bagaimana saya memulai debug insert dikenal fungsi?
Oh ya ampun.
Itu banyak.
Apakah itu panik banyak?
>> AUDIENCE: Oh, itu meninggal.
>> JASON Hirschhorn: Aku hanya menariknya keluar.
OK.
>> AUDIENCE: Mungkin itu adalah ujung kawat.
>> JASON Hirschhorn: Wow.
Jadi intinya -
apa yang kau katakan?
>> AUDIENCE: Aku berkata ironi teknis kesulitan dalam kelas ini.
>> JASON Hirschhorn: Aku tahu.
Kalau saja aku punya kendali atas bagian itu.
[Tak terdengar]
Kedengarannya bagus.
Kenapa tidak kalian mulai berpikir tentang apa yang bisa kita berbuat salah,
dan kami akan kembali dalam 90 detik.
>> Avica, aku akan meminta Anda bagaimana untuk pergi dalam insert_node untuk debug itu.
Jadi ini adalah di mana kita terakhir tinggalkan.
Bagaimana cara masuk ke dalam insert_node, Avica, untuk memeriksa apa yang terjadi?
Apa perintah GDB?
Istirahat tidak akan membawa saya ke dalam.
Apakah Marquise tahu?
>> AUDIENCE: Apa?
>> JASON Hirschhorn: Apa perintah GDB Saya gunakan untuk masuk ke dalam fungsi ini?
>> AUDIENCE: Langkah?
>> JASON Hirschhorn: Langkah via S. Yang membawa saya ke dalam.
OK.
New_node mallocing beberapa ruang.
Itu semua tampak seperti yang terjadi.
Mari kita periksa new_node.
Ini punya beberapa alamat memori.
Mari kita periksa -
itu semua benar.
Jadi semuanya di sini tampaknya bekerja dengan benar.
>> AUDIENCE: Apa bedanya antara P dan display?
>> JASON Hirschhorn: P singkatan dari print.
Dan sekarang anda bertanya apa perbedaan antara itu dan ini?
Dalam hal ini, tidak ada.
Namun umumnya ada beberapa perbedaan.
Dan Anda harus melihat di manual GDB.
Tapi dalam kasus ini, tidak ada.
Kita cenderung untuk menggunakan print, meskipun, karena kita tidak perlu melakukan lebih dari
mencetak nilai tunggal.
>> OK.
Jadi kita on line 80 kode kami, pengaturan simpul * Curr sama dengan daftar.
Mari kita mencetak Curr.
Ini sama dengan daftar.
Manis.
Tunggu.
Ini sama dengan sesuatu.
Itu tidak benar.
Di sana kami pergi.
Itu karena di GDB, benar, jika itu garis Anda di atasnya
belum dieksekusi belum.
Jadi, Anda harus benar-benar ketik berikutnya untuk mengeksekusi baris
sebelum melihat hasilnya.
Jadi di sini kita.
Kami hanya dieksekusi baris ini, sebelumnya sama null.
Jadi sekali lagi, jika kita mencetak sebelumnya kita tidak akan melihat sesuatu yang aneh.
Tetapi jika kita benar-benar melaksanakan itu line, maka kita akan melihat
bahwa garis yang bekerja.
>> Jadi kita memiliki Curr.
Mereka berdua baik.
Benar?
Sekarang kita berada di baris ini di sini.
Sementara Curr tidak nol sama.
Nah, apa Curr sama?
Kami hanya melihat itu setara null.
Kami mencetaknya.
Aku akan mencetaknya lagi.
Jadi adalah bahwa while loop akan mengeksekusi?
>> AUDIENCE: No
>> JASON Hirschhorn: Jadi ketika saya mengetik bahwa line, Anda lihat kami melompat sepanjang jalan
turun ke bawah, kembali palsu.
Dan kemudian kita akan kembali palsu dan kembali ke program kami dan
akhirnya mencetak, seperti yang kita lihat, insert itu tidak berhasil.
Jadi, ada yang punya ide tentang apa yang yang perlu kita lakukan untuk memperbaiki hal ini?
Aku akan menunggu sampai aku melihat beberapa tangan naik.
Kami tidak mengeksekusi ini.
Perlu diingat, ini adalah pertama hal yang kita lakukan.
Aku tidak akan melakukan beberapa.
Aku akan melakukan beberapa.
Karena pasangan berarti dua.
Aku akan menunggu selama lebih dari dua.
>> Penyisipan pertama, Curr, secara default sama dengan nol.
Dan lingkaran ini hanya mengeksekusi jika Curr tidak null.
Jadi bagaimana saya bisa mendapatkan sekitar ini?
Saya melihat tiga tangan.
Aku akan menunggu selama lebih dari tiga.
Marcus, apa yang Anda pikirkan?
>> AUDIENCE: Nah, jika Anda perlu untuk mengeksekusi lebih dari sekali, Anda hanya
mengubahnya ke loop do-while.
>> JASON Hirschhorn: OK.
Apakah yang memecahkan masalah kita, meskipun?
>> AUDIENCE: Dalam hal ini tidak ada karena fakta bahwa daftar kosong.
Jadi Anda mungkin hanya perlu menambahkan pernyataan bahwa jika keluar lingkaran
maka Anda harus berada di akhir daftar, di mana titik Anda
hanya bisa memasukkannya.
>> JASON Hirschhorn: aku seperti itu.
Itu masuk akal.
Jika loop keluar -
karena itu akan return false sini.
Jadi jika keluar lingkaran, maka kita berada di akhir daftar, atau mungkin
mulai dari daftar jika tidak ada di itu, yang sama dengan akhir.
Jadi sekarang kita ingin menyisipkan sesuatu di sini.
Jadi bagaimana kode yang terlihat, Marcus?
>> AUDIENCE: Jika Anda sudah punya node malloced, Anda hanya bisa mengatakan
new_node-> berikutnya sama dengan nol karena itu harus di akhir.
Atau new_node-> berikutnya sama dengan nol.
>> JASON Hirschhorn: OK.
Maaf.
New_node-> next sama dengan nol karena kita berada di akhir.
Itu tidak memasukkannya masuk
Bagaimana kita memasukkannya ke dalam daftar?
Benar.
Itu hanya pengaturan itu sama dengan.
Tidak bagaimana kita benar-benar memasukkannya ke dalam daftar?
Apa yang menunjuk ke akhir daftar?
>> AUDIENCE: Head.
>> JASON Hirschhorn: Maaf?
>> AUDIENCE: Kepala menunjuk ke akhir daftar.
>> JASON Hirschhorn: Jika tidak ada di daftar, kepala menunjuk ke
akhir daftar.
Sehingga akan bekerja untuk penyisipan pertama.
Bagaimana jika ada beberapa hal dalam daftar?
Daripada kita tidak ingin mengatur kepala sama dengan new_node.
Apa yang kita ingin lakukan di sana?
Ya?
Mungkin sebelumnya.
Apakah itu bekerja?
Ingat bahwa sebelumnya hanya pointer ke node.
Dan sebelumnya adalah variabel lokal.
Jadi baris ini akan menetapkan variabel lokal, sebelumnya, sama dengan atau
menunjuk ke node baru ini.
Itu tidak akan benar-benar memasukkannya dalam daftar kami, meskipun.
Bagaimana kita memasukkannya ke dalam daftar kami?
Akchar?
>> AUDIENCE: Saya pikir Anda lakukan saat ini-> berikutnya.
>> JASON Hirschhorn: OK.
Curr-> berikutnya.
Jadi sekali lagi, satu-satunya alasan kita turun di sini adalah, apa saat yang sama?
>> AUDIENCE: Sama null.
>> JASON Hirschhorn: Dan jadi apa terjadi jika kita melakukan null-> next?
Apa yang kita akan mendapatkan?
Kita akan mendapatkan kesalahan segmentasi.
>> AUDIENCE: Do Curr sama dengan nol.
>> JASON Hirschhorn: Itu hal yang sama sebagai prev, meskipun, karena ada
variabel lokal kami sedang menyiapkan sama dengan node baru ini.
Mari kita kembali ke gambar kami memasukkan sesuatu.
Katakanlah kita memasukkan pada akhir dari daftar, jadi di sini.
Kami memiliki pointer saat itu menunjuk ke nol dan titik sebelumnya
yang menunjuk ke 8.
Jadi apa yang kita perlu memperbarui, Avi?
>> AUDIENCE: Sebelumnya-> next?
>> JASON Hirschhorn: Sebelumnya-> berikutnya adalah apa kita ingin memperbarui karena
benar-benar akan masukkan di akhir daftar.
Kami masih memiliki satu bug, meskipun, bahwa kita akan mengalami.
Apa bug itu?
Ya?
>> AUDIENCE: Ini akan kembali palsu dalam kasus ini?
>> JASON Hirschhorn: Oh, ini adalah akan kembali palsu.
Tapi ada bug lain.
Jadi kita harus dimasukkan ke dalam return true.
>> AUDIENCE: Apakah masih sama sebelumnya nol di bagian atas daftar?
>> JASON Hirschhorn: masih Jadi sebelumnya sama dengan nol di awal.
Jadi bagaimana kita bisa mendapatkan lebih dari itu?
Ya?
>> AUDIENCE: Saya pikir Anda dapat melakukan pemeriksaan sebelum loop sementara untuk melihat apakah itu
daftar kosong.
>> JASON Hirschhorn: OK.
Jadi mari kita pergi di sini.
Lakukan cek.
Jika -
>> AUDIENCE: Jadi jika kepala sama sama null.
>> JASON Hirschhorn: Jika kepala sama sama nol -
yang akan memberitahu kita jika daftar kosong.
>> AUDIENCE: Dan kemudian Anda melakukan kepala sama baru.
>> JASON Hirschhorn: Kepala sama new_node?
Dan apa lagi yang perlu kita lakukan?
>> AUDIENCE: Dan kemudian Anda kembali benar.
>> JASON Hirschhorn: Tidak cukup.
Kami kehilangan satu langkah.
>> AUDIENCE: New_node berikutnya menunjuk ke nol.
>> JASON Hirschhorn: Tepat, Alden.
Dan kemudian kita bisa kembali benar.
OK.
Tapi itu masih ide yang baik untuk melakukan hal-hal pada akhir daftar, kan?
Baik.
Kami masih mungkin benar-benar mendapatkan ke akhir daftar.
Jadi kode ini baik-baik saja jika kita berada di akhir daftar dan ada beberapa
hal dalam daftar?
Benar?
Karena kita masih punya ide Marcus.
Kita mungkin keluar dari lingkaran ini karena kita berada di akhir daftar.
Jadi kita masih ingin ini kode di sini?
>> AUDIENCE: Ya.
>> JASON Hirschhorn: Ya.
Dan apa yang kita perlu mengubah ini?
Benar.
Apakah itu terdengar baik untuk semua orang sejauh ini?
Ada yang punya -
Avi, apakah Anda memiliki sesuatu untuk menambahkan?
>> AUDIENCE: No
>> JASON Hirschhorn: OK.
Jadi kami telah membuat beberapa perubahan.
Kami telah membuat cek ini sebelum kita masuk untuk daftar kosong.
Jadi kita sudah diurus daftar kosong.
Dan di sini kita merawat memasukkan sesuatu pada akhir daftar.
Jadi sepertinya while loop ini mengambil mengurus hal-hal di antara,
suatu tempat dalam daftar jika ada hal-hal dalam daftar.
>> OK.
Mari kita menjalankan program ini lagi.
Tidak berhasil.
>> AUDIENCE: Anda tidak berhasil.
>> JASON Hirschhorn: Oh, Aku tidak berhasil.
Good point, Michael.
Mari menambahkan make terkait.
Baris 87 ada kesalahan.
Baris 87.
Alden, ini adalah garis Anda memberi saya.
Apa yang salah?
>> AUDIENCE: Itu harus null.
>> JASON Hirschhorn: Excellent.
Tepat.
Ini harus nol.
Mari kita membuat lagi.
Kompilasi.
OK.
Mari kita memasukkan tiga.
Insert itu berhasil.
Mari kita mencetaknya.
Oh, kalau saja kita bisa memeriksa.
Tapi kita belum melakukan mencetak fungsi belum.
Mari kita masuk ke sesuatu yang lain.
Apa yang harus kita masukkan?
>> AUDIENCE: Tujuh.
>> JASON Hirschhorn: Seven?
>> AUDIENCE: Ya.
>> JASON Hirschhorn: Kami memiliki kesalahan seg.
Jadi kita punya satu, tapi kami jelas tidak bisa mendapatkan dua.
Ini adalah 05:07.
Jadi kita bisa debug ini selama tiga menit.
Tapi aku akan meninggalkan kami di sini dan beralih ke hash tabel.
Tapi sekali lagi, jawaban untuk kode ini Saya akan mengirimkan email kepada Anda dalam sedikit.
Kami sangat dekat dengan itu.
Saya sangat mendorong Anda untuk mencari tahu apa yang terjadi di sini dan memperbaikinya.
Jadi saya akan mengirimkan email kode ini sebagai baik ditambah solusinya -
mungkin solusi di kemudian hari.
Pertama kode ini.
>> Hal lain yang saya ingin lakukan sebelum kita finish adalah kita belum dibebaskan apa-apa.
Jadi saya ingin menunjukkan apa Valgrind terlihat seperti.
Jika kita menjalankan batas Valgrind pada program kami,. / terkait.
Sekali lagi, menurut slide ini, kami harus menjalankan Valgrind dengan beberapa jenis
pilihan, dalam hal ini - Kebocoran-cek = penuh.
Jadi mari kita menulis Valgrind - Kebocoran-cek = penuh.
Jadi ini akan menjalankan Valgrind pada program kami.
Dan sekarang program ini benar-benar berjalan.
Jadi kita akan menjalankannya seperti sebelumnya, menempatkan sesuatu masuk
Aku akan dimasukkan ke dalam tiga.
Yang bekerja.
Aku tidak akan mencoba untuk dimasukkan ke dalam sesuatu lain karena kita akan
mendapatkan palsu seg dalam kasus itu.
Jadi aku hanya akan berhenti.
>> Dan sekarang Anda lihat di sini bocor dan ringkasan tumpukan.
Ini adalah hal baik yang Anda ingin memeriksa.
Jadi ringkasan tumpukan - itu mengatakan, dalam penggunaan di pintu keluar - delapan byte dalam satu blok.
Itu satu blok adalah simpul kami malloced.
Michael, Anda katakan sebelumnya node adalah delapan gigitan karena memiliki integer
dan pointer.
Jadi itulah simpul kami.
Dan kemudian ia mengatakan kami menggunakan malloc tujuh kali dan kami dibebaskan
sesuatu enam kali.
Tapi kita tidak pernah disebut gratis, jadi saya tidak punya tahu apa ini bicarakan.
>> Tapi cukup untuk mengatakan bahwa ketika Anda Program berjalan, malloc sedang dipanggil
di beberapa tempat lain yang kita tidak perlu khawatir.
Jadi malloc mungkin disebut di beberapa tempat.
Kita tidak perlu khawatir di mana.
Tapi ini benar-benar kami.
Baris pertama ini adalah kita.
Kami meninggalkan blok itu.
Dan Anda dapat melihat bahwa di sini dalam ringkasan kebocoran.
Masih terjangkau -
delapan byte dalam satu blok.
Itu berarti memori yang -
kami telah bocor memori itu.
Pasti hilang -
ada sesuatu yang hilang untuk selamanya.
Umumnya, Anda tidak akan melihat apa-apa di sana.
Masih terjangkau umumnya mana Anda akan melihat hal-hal, di mana Anda akan ingin
untuk melihat untuk melihat apa kode harus Anda telah dibebaskan tetapi Anda lupa untuk membebaskan.
>> Dan kemudian jika ini tidak terjadi, jika kita melakukan segala sesuatu gratis,
kita dapat memeriksa bahwa.
Mari kita jalankan program tidak menempatkan dalam hal apa pun.
Anda akan melihat di sini digunakan di exit -
nol byte dalam blok nol.
Itu berarti kita punya apa-apa lagi ketika program ini keluar.
Jadi sebelum balik dalam pset6, menjalankan Valgrind dan pastikan Anda tidak memiliki
memori dengan kebocoran dalam program Anda.
Jika Anda memiliki pertanyaan dengan Valgrind, merasa bebas untuk menjangkau.
Tapi ini adalah bagaimana Anda menggunakannya.
Sangat sederhana - melihat apakah Anda harus digunakan di exit -
setiap byte dalam setiap blok.
>> Jadi kami bekerja pada insert simpul.
Aku punya dua fungsi lain di sini - mencetak node dan node gratis.
Sekali lagi, ini adalah fungsi yang akan menjadi baik bagi Anda untuk berlatih
karena mereka akan membantu Anda tidak hanya dengan ini latihan sampel tetapi juga
pada masalah ditetapkan.
Mereka memetakan cukup erat dengan hal-hal Anda akan harus melakukan di
masalah ditetapkan.
Tapi aku ingin memastikan kita menyentuh pada segala sesuatu.
Dan tabel hash juga penting untuk apa yang kita lakukan dalam bagian ini
minggu - atau di set masalah.
>> Jadi kita akan menyelesaikan bagian berbicara tentang tabel hash.
Jika Anda melihat saya membuat sedikit tabel hash.
Itu bukan apa yang kita bicarakan tentang, namun.
Kita berbicara tentang berbeda jenis tabel hash.
Dan pada intinya, sebuah tabel hash yang adalah tidak lebih dari sebuah
Array ditambah fungsi hash.
Kita akan berbicara sebentar hanya untuk pastikan semua orang mengerti apa yang
Fungsi hash adalah.
Dan aku bilang sekarang bahwa itu adalah tidak lebih dari dua hal -
array dan fungsi hash.
Dan di sini adalah langkah-langkah melalui yang ini beroperasi.
>> Ada array kita.
Ada fungsi kita.
Secara khusus, fungsi hash harus melakukan beberapa hal dengan hal ini.
Saya akan berbicara secara khusus tentang masalah ini ditetapkan.
Ini mungkin akan mengambil dalam string.
Dan apa itu akan kembali?
Apa tipe data?
Alden?
Fungsi hash Anda kembali?
Integer.
Jadi ini adalah apa hash Tabel terdiri dari -
tabel dalam bentuk array dan fungsi hash.
Bagaimana cara kerjanya?
Ia bekerja dalam tiga langkah.
Kami memberikan kunci.
Dalam hal ini, kami akan memberikan string.
Kami memanggil fungsi hash per satu langkah pada tombol tersebut dan kita mendapatkan nilai.
>> Secara khusus, kita akan mengatakan kita mendapatkan integer.
Integer yang ada sangat spesifik batas untuk apa integer yang dapat.
Dalam contoh ini, array kita adalah ukuran tiga.
Jadi apa yang dapat nomor integer yang menjadi.
Berapa kisaran nilai valid untuk integer yang, jenis kembalinya ini
hash fungsi?
Nol, satu dan dua.
Titik fungsi hash adalah untuk mengetahui tempat dalam array
di mana kunci kami akan.
Hanya ada tiga kemungkinan tempat di sini -
nol, satu, atau dua.
Jadi fungsi ini lebih baik kembali nol, satu, atau dua.
Beberapa Indice berlaku dalam array ini.
>> Dan kemudian tergantung di mana itu kembali, Anda dapat melihat ada array yang terbuka
braket nilai.
Itulah di mana kita meletakkan kunci.
Jadi kita melempar labu, kita keluar nol.
Pada berbagai bracket 0, kami menempatkan labu.
Kami melempar kucing, kita keluar satu.
Kami menempatkan kucing di salah satu.
Kami dimasukkan ke dalam laba-laba.
Kami mendapatkan dua.
Kami menempatkan laba-laba di berbagai braket dua.
Akan sangat baik jika itu bekerja seperti itu.
Tapi sayangnya, karena kami akan melihat, itu sedikit lebih rumit.
>> Sebelum kita sampai di sana, pertanyaan tentang hal ini dasar
set-up dari sebuah tabel hash?
Ini adalah gambar persis apa yang kita menarik di papan tulis.
Tapi karena kita menarik di papan, saya saya tidak akan pergi lebih jauh.
Pada dasarnya kunci, kotak hitam ajaib - atau dalam hal ini, kotak teal - dari
Fungsi hash menempatkan mereka dalam ember.
Dan dalam contoh ini kita tidak menempatkan nama.
Kami menempatkan terkait telepon jumlah nama dalam ember.
Tapi Anda bisa sangat baik hanya menempatkan nama dalam ember.
>> Ini hanya gambaran tentang apa kita menarik di papan tulis.
Kami memiliki perangkap potensial, meskipun.
Dan ada dua khususnya slide yang saya ingin pergi.
Yang pertama adalah tentang fungsi hash.
Jadi saya bertanya, apa membuat fungsi hash yang baik?
Saya memberikan dua jawaban.
Yang pertama adalah bahwa hal itu deterministik.
Dalam konteks fungsi hash, apa artinya ini?
Ya?
>> AUDIENCE: Hal ini dapat menemukan indeks dalam waktu yang konstan?
>> JASON Hirschhorn: Bahwa tidak apa artinya.
Tapi itu menebak yang baik.
Orang lain memiliki rasa apa artinya ini?
Bahwa fungsi hash yang baik adalah deterministik?
Annie?
>> AUDIENCE: Bahwa kunci hanya dapat dipetakan ke satu tempat dalam tabel hash.
>> JASON Hirschhorn: Itu tepat.
Setiap kali Anda masukkan ke dalam labu, selalu kembali nol.
Jika Anda dimasukkan ke dalam labu dan hash Anda fungsi mengembalikan nol namun memiliki
probabilitas kembali sesuatu lain lebih besar dari nol -
jadi mungkin itu bisa kembali satu kadang-kadang atau dua kali lainnya -
itu bukan fungsi hash yang baik.
Kau tepat.
Fungsi hash Anda harus mengembalikan bilangan bulat yang persis sama, dalam hal ini, untuk
string yang sama persis.
>> Mungkin ia mengembalikan bilangan bulat yang sama persis untuk string yang sama persis
terlepas dari kapitalisasi.
Tapi dalam kasus ini masih deterministik karena beberapa hal
dipetakan ke nilai yang sama.
Itu baik-baik saja.
Selama hanya ada satu output untuk masukan yang diberikan.
>> OK.
Hal kedua adalah bahwa hal itu mengembalikan indeks yang valid.
Kami dibesarkan bahwa sebelumnya.
Fungsi hash ini -
oh boy -
fungsi hash harus kembali indeks yang valid.
Jadi katakan -
mari kita kembali ke contoh ini.
Fungsi hash saya menghitung sampai huruf dalam kata.
Itulah fungsi hash.
Dan mengembalikan integer yang.
Jadi jika saya memiliki kata A, itu akan kembali satu.
Dan itu akan menempatkan A di sini.
Bagaimana jika saya dimasukkan ke dalam kelelawar kata?
Ini akan mengembalikan tiga.
Di mana kelelawar pergi?
>> Ini tidak cocok.
Tapi perlu pergi ke suatu tempat.
Ini adalah tabel hash saya setelah semua, dan semuanya harus pergi ke suatu tempat.
Jadi di mana kelelawar harus pergi?
Setiap pikiran?
Menebak?
Baik tebakan?
>> AUDIENCE: Zero.
>> JASON Hirschhorn: Mengapa nol?
>> AUDIENCE: Karena tiga modulo tiga adalah nol?
>> JASON Hirschhorn: Tiga modulo tiga adalah nol.
Itu adalah menebak besar, dan itu benar.
Jadi dalam hal ini seharusnya mungkin pergi dari nol.
Jadi cara yang baik untuk memastikan bahwa hash ini fungsi hanya mengembalikan indeks yang valid
untuk modulo dengan ukuran meja.
Jika Anda modulo apa ini kembali dengan ketiga, Anda akan selalu mendapatkan
sesuatu antara nol, satu, dan dua.
Dan jika hal ini selalu mengembalikan tujuh, dan Anda selalu Modulo oleh tiga, Anda
selalu akan mendapatkan hal yang sama.
>> Jadi masih deterministik jika Anda modulo.
Tapi itu akan memastikan bahwa Anda tidak pernah mendapatkan sesuatu -
industri yang tidak valid.
Umumnya, modulo yang harus terjadi dalam fungsi hash Anda.
Jadi Anda tidak perlu khawatir tentang hal ini.
Anda hanya dapat memastikan bahwa ini adalah Indice valid.
Setiap pertanyaan ini Potensi perangkap?
>> OK.
Dan di sana kita pergi.
Berikutnya potensi perangkap, dan ini adalah satu besar.
Bagaimana jika dua kunci peta dengan nilai yang sama?
Jadi ada dua cara untuk menangani hal ini.
Yang pertama disebut linear menyelidik, yang aku
tidak akan pergi ke.
Tapi Anda harus akrab dengan cara yang bekerja dan apa itu.
>> Yang kedua saya akan pergi ke karena itu adalah salah satu yang banyak
orang mungkin akan berakhir memutuskan untuk digunakan dalam set masalah mereka.
Tentu saja, Anda tidak perlu.
Tapi untuk set masalah, banyak orang cenderung memilih untuk membuat tabel hash
dengan chaining terpisah untuk melaksanakan kamus mereka.
Jadi kita akan membahas apa artinya untuk membuat tabel hash dengan
chaining terpisah.
>> Jadi saya dimasukkan ke dalam labu.
Ia mengembalikan nol.
Dan saya menempatkan labu di sini.
Kemudian saya dimasukkan ke dalam -
apa hal lain yang bertema Halloween?
>> AUDIENCE: Candy.
>> JASON Hirschhorn: Candy!
Itu salah besar.
Aku dimasukkan ke dalam permen, dan permen juga memberi saya nol.
Apa yang harus saya lakukan?
Ada gagasan?
Karena Anda semua jenis tahu apa chaining terpisah.
Jadi setiap ide apa yang harus dilakukan?
Ya.
>> AUDIENCE: Menempatkan string sebenarnya dalam tabel hash.
>> JASON Hirschhorn: Jadi kita akan menggambar ide yang baik di sini.
OK.
>> AUDIENCE: Memiliki hashtable [Tak terdengar]
pointer yang menunjuk ke awal daftar.
Dan kemudian telah labu menjadi nilai pertama dalam linked list dan permen menjadi
nilai kedua dalam linked list.
>> JASON Hirschhorn: OK.
Marcus, yang luar biasa.
Aku akan istirahat yang turun.
Marcus mengatakan tidak menimpa labu.
Itu akan buruk.
Jangan menaruh permen di tempat lain.
Kita akan menempatkan mereka berdua di nol.
Tapi kita akan berurusan dengan menempatkan mereka pada nol dengan
membuat daftar di nol.
Dan kita akan membuat daftar segala sesuatu yang dipetakan ke nol.
Dan cara terbaik kita belajar untuk membuat daftar yang dapat tumbuh dan menyusut
dinamis tidak berada dalam array lain.
Jadi bukan array multi-dimensi.
Tetapi untuk hanya membuat daftar link.
>> Jadi apa yang ia mengusulkan -
Aku akan mendapatkan yang baru -
adalah membuat sebuah array dengan pointer, array pointer.
OK.
Setiap ide atau petunjuk apa jenis pointer ini harus?
Marcus?
>> AUDIENCE: Pointer ke -
>> JASON Hirschhorn: Karena Anda kata sebuah linked list, sehingga -
>> AUDIENCE: Node pointer?
>> JASON Hirschhorn: Node pointer.
Jika hal-hal di terkait kami daftar node maka mereka
harus simpul pointer.
Dan apa yang mereka awalnya sama?
>> AUDIENCE: Null.
>> JASON Hirschhorn: Null.
Jadi ada hal kami kosong.
Kembali labu nol.
Apa yang kita lakukan?
Berjalan saya melalui itu?
Sebenarnya, Marcus sudah memberi saya.
Orang lain berjalan saya melalui itu.
Apa yang kita lakukan saat kita -
ini terlihat sangat mirip dengan apa yang kita hanya melakukan.
Avi.
>> AUDIENCE: Aku akan mengambil menebak.
Jadi, ketika Anda mendapatkan permen.
>> JASON Hirschhorn: Ya.
Nah, kita punya labu.
Mari kita mendapatkan satu pertama kami.
Kami punya labu.
>> AUDIENCE: OK.
Kembali labu nol.
Jadi Anda memasukkannya ke dalam itu.
Atau sebenarnya, Anda meletakkannya dalam linked list.
>> JASON Hirschhorn: Bagaimana kita memasukkannya ke dalam linked list?
>> AUDIENCE: Oh, sintaks yang sebenarnya?
>> JASON Hirschhorn: Hanya berjalan -
mengatakan lebih.
Apa yang kita lakukan?
>> AUDIENCE: Anda hanya memasukkan sebagai simpul pertama.
>> JASON Hirschhorn: OK.
Jadi kita memiliki simpul kami, labu.
Dan sekarang bagaimana cara memasukkannya?
>> AUDIENCE: Anda menetapkan untuk pointer.
>> JASON Hirschhorn: Yang pointer?
>> AUDIENCE: The pointer nol.
>> JASON Hirschhorn: Jadi di mana melakukan hal ini?
>> AUDIENCE: Untuk nol sekarang.
>> JASON Hirschhorn: Nah, itu menunjuk ke null.
Tapi aku meletakkan di labu.
Jadi di mana harus menunjuk?
>> AUDIENCE: Untuk labu.
>> JASON Hirschhorn: Untuk labu.
Tepat.
Jadi ini menunjuk ke labu.
Dan di mana tidak pointer ini di titik labu?
Untuk
>> AUDIENCE: Null.
>> JASON Hirschhorn: Untuk nol.
Tepat.
Jadi kita hanya dimasukkan sesuatu ke dalam linked list.
Kami hanya menulis kode ini untuk melakukan hal ini.
Hampir kami hampir mendapatkannya benar-benar retak.
Sekarang kita memasukkan permen.
Permen kami juga pergi ke nol.
Jadi apa yang kita lakukan dengan permen?
>> AUDIENCE: Hal ini tergantung pada apakah atau tidak kita berusaha untuk mengatasinya.
>> JASON Hirschhorn: Itu tepat.
Hal ini tergantung pada apakah atau tidak kita berusaha untuk mengatasinya.
Mari kita asumsikan kita tidak akan semacam itu.
>> AUDIENCE: Kalau begitu, seperti yang kita bahas sebelumnya, itu paling sederhana hanya untuk meletakkannya
tepat di awal sehingga pointer dari nol poin menjadi permen.
>> JASON Hirschhorn: OK.
Tunggu.
Mari saya membuat permen di sini.
Jadi pointer ini -
>> AUDIENCE: Ya, sekarang harus menunjuk ke permen.
Kemudian memiliki pointer dari titik permen untuk labu.
>> JASON Hirschhorn: Seperti itu?
Dan mengatakan kami mendapat lain hal untuk memetakan ke nol?
>> AUDIENCE: Nah, Anda hanya melakukan hal yang sama?
>> JASON Hirschhorn: Lakukan hal yang sama.
Jadi dalam hal ini, jika kita tidak ingin menyimpannya diurutkan
terdengar agak sederhana.
Kami mengambil pointer di Indice yang diberikan oleh fungsi hash kami.
Kami memiliki yang mengarah ke simpul baru.
Dan kemudian apa pun itu menunjuk untuk sebelumnya -
dalam hal ini null, dalam kasus kedua labu -
bahwa, apa pun itu menunjuk ke sebelumnya, kita tambahkan ke berikutnya
node baru kami.
Kami memasukkan sesuatu di awal.
Sebenarnya ini adalah jauh lebih sederhana daripada berusaha untuk menjaga daftar diurutkan.
Tetapi sekali lagi, pencarian akan lebih rumit di sini.
Kami akan selalu harus pergi ke akhir.
>> OK.
Setiap pertanyaan tentang chaining terpisah?
Bagaimana yang bekerja?
Silakan meminta mereka sekarang.
Aku benar-benar ingin memastikan Anda semua memahami hal ini sebelum kita kepala keluar.
>> AUDIENCE: Mengapa Anda menempatkan labu dan permen ke dalam yang sama
bagian dari tabel hash?
>> JASON Hirschhorn: Pertanyaan yang bagus.
Mengapa kita menempatkan mereka dalam yang sama bagian dari tabel hash?
Nah, dalam hal ini fungsi hash kami kembali nol bagi mereka berdua.
Jadi mereka harus pergi di Indice nol karena di situlah kita akan
mencari mereka jika kita pernah ingin melihat mereka.
Sekali lagi, dengan linear probing pendekatan kita tidak akan menempatkan mereka berdua di nol.
Tapi dalam pendekatan rantai terpisah, kita akan menempatkan mereka berdua di nol
dan kemudian membuat daftar dari nol.
>> Dan kita tidak ingin menimpa labu hanya untuk itu karena kemudian kita akan
berasumsi bahwa labu adalah tidak pernah dimasukkan.
Jika kita hanya menjaga satu hal dalam lokasi yang akan menjadi buruk.
Kemudian tidak akan ada kesempatan kita pernah -
jika kita pernah memiliki duplikat, maka kita hanya akan menghapus nilai awal kami.
Jadi itulah mengapa kita melakukan pendekatan ini.
Atau itu sebabnya kami memilih - tapi sekali lagi, kami memilih pendekatan chaining terpisah,
yang ada banyak pendekatan lain orang bisa memilih.
Apakah itu menjawab pertanyaan Anda?
>> OK.
Carlos.
Linear probing akan melibatkan -
jika kita menemukan tabrakan di nol, kita akan terlihat di tempat berikutnya untuk melihat apakah
itu terbuka dan meletakkannya di sana.
Dan kemudian kita melihat dalam olahraga berikutnya dan melihat apakah itu terbuka dan meletakkannya di sana.
Jadi kita menemukan tersedia berikutnya terbuka spot dan menaruhnya di sana.
Ada pertanyaan lain?
Ya, Avi.
>> AUDIENCE: Sebagai tindak lanjut itu, apa yang Anda maksud dengan tempat berikutnya?
Dalam tabel hash atau dalam linked list.
>> JASON Hirschhorn: Untuk linear pemrograman, tidak ada daftar terkait.
Titik berikutnya pada tabel hash.
>> AUDIENCE: OK.
Jadi tabel hash akan diinisialisasi dengan ukuran -
seperti jumlah string bahwa Anda memasukkan?
>> JASON Hirschhorn: Anda akan ingin menjadi benar-benar besar.
Ya.
Berikut adalah gambar dari apa yang kita hanya menggambar di papan tulis.
Sekali lagi, kami memiliki tabrakan di sini.
di 152.
Dan Anda akan melihat kita buat linked list dari itu.
Sekali lagi, tabel hash chaining terpisah Pendekatan ini bukan yang Anda
harus mengambil masalah ditetapkan enam tetapi adalah salah satu yang banyak
siswa cenderung untuk mengambil.
Jadi pada catatan itu, mari kita bicara sebentar sebelum kita kepala keluar tentang masalah enam,
dan kemudian saya akan berbagi cerita dengan Anda.
Kami memiliki tiga menit.
>> Masalah menetapkan enam.
Anda memiliki empat fungsi -
beban, cek, ukuran, dan membongkar.
Beban -
baik, kami sudah terjadi atas beban sekarang.
Kami menarik beban di papan tulis.
Dan kita bahkan mulai coding banyak memasukkan ke dalam linked list.
Jadi beban tidak lebih dari apa yang baru saja kita lakukan.
>> Periksa sekali Anda memiliki sesuatu yang dimuat.
Ini adalah proses yang sama seperti ini.
Sama pertama dua bagian di mana Anda membuang sesuatu ke dalam fungsi hash
dan mendapatkan nilainya.
Tapi sekarang kita tidak memasukkan itu.
Sekarang kami sedang mencari untuk itu.
Saya telah contoh kode yang ditulis untuk menemukan sesuatu dalam linked list.
Saya mendorong Anda untuk berlatih itu.
Tapi secara intuitif menemukan sesuatu yang sangat mirip dengan memasukkan sesuatu.
Memang, kita menarik gambaran menemukan sesuatu dalam linked list, bergerak
melalui sampai Anda sampai ke akhir.
Dan jika Anda punya sampai akhir dan tidak bisa menemukannya, maka itu tidak ada.
Jadi itulah cek, pada dasarnya.
>> Berikutnya adalah ukuran.
Mari kita melewatkan ukuran.
Akhirnya anda telah membongkar.
Unload adalah salah satu kami belum ditarik di papan atau kode belum.
Tapi saya mendorong Anda untuk mencoba coding dalam sampel kami linked list contoh.
Tapi membongkar intuitif mirip dengan gratis -
atau saya maksud adalah mirip dengan memeriksa.
Kecuali untuk saat ini setiap kali Anda akan melalui, Anda tidak hanya memeriksa untuk
melihat apakah Anda memiliki nilai Anda di sana.
Tapi kau mengambil simpul tersebut dan membebaskan, pada dasarnya.
Itulah yang membongkar meminta Anda untuk melakukan.
Gratis segala yang telah malloced.
Jadi Anda akan melalui seluruh daftar lagi, akan melalui seluruh hash
tabel lagi.
Kali ini tidak memeriksa untuk melihat apa yang ada.
Hanya membebaskan apa yang ada.
>> Dan akhirnya ukuran.
Ukuran harus dilaksanakan.
Jika Anda tidak menerapkan ukuran -
Aku akan mengatakannya seperti ini.
Jika Anda tidak menerapkan ukuran yang persis satu baris kode termasuk
pernyataan kembali, Anda melakukan ukuran benar.
Jadi pastikan ukuran, untuk desain penuh poin, Anda melakukannya di tepat satu
baris kode, termasuk pernyataan kembali.
>> Dan jangan berkemas lagi, Akchar.
Berang-berang bersemangat.
Saya ingin mengucapkan terima kasih guys untuk datang ke bagian.
Memiliki Happy Halloween.
Ini adalah kostum saya.
Aku akan memakai ini pada hari Kamis jika saya melihat Anda pada jam-jam kantor.
Dan jika Anda ingin tahu tentang lagi latar belakang untuk kostum ini, merasa
bebas untuk memeriksa 2.011 bagian untuk cerita tentang mengapa aku
mengenakan kostum labu.
Dan itu adalah kisah sedih.
Jadi pastikan Anda memiliki beberapa jaringan di dekatnya.
Tapi pada itu, jika Anda memiliki pertanyaan saya akan tetap sekitar
luar setelah bagian.
Good luck pada masalah menetapkan enam.
Dan seperti biasa, jika Anda memiliki pertanyaan, let me know.