>> KEVIN Schmid: Kadang-kadang, apabila membina sebuah program, anda mungkin mahu untuk menggunakan
struktur data yang dikenali sebagai kamus.
Satu peta kamus kunci, yang biasanya tali, untuk nilai-nilai, Ints,
aksara, penunjuk kepada beberapa objek, apa sahaja yang kita mahu.
Ia hanya seperti kamus biasa peta yang kata-kata melalui definisi.
>> Kamus menyediakan kami dengan keupayaan untuk menyimpan maklumat
berkaitan dengan sesuatu dan melihat ia kemudian.
Jadi bagaimana kita sebenarnya melaksanakan kamus, katakanlah, kod C yang kita boleh
digunakan dalam salah satu program kita?
Well, ada banyak cara yang saya melaksanakannya kamus.
>> Untuk satu, kita boleh menggunakan array yang kita saiz semula secara dinamik atau kita boleh menggunakan
senarai bersambung, jadual hash atau pokok binari.
Tetapi apa sahaja yang kita pilih, kita harus prihatin terhadap kecekapan dan
prestasi pelaksanaan.
Kami perlu memikirkan algoritma yang digunakan untuk memasukkan dan mencari item ke dalam
struktur data kami.
>> Buat masa ini, mari kita andaikan kita yang mahu menggunakan tali sebagai kunci.
Mari kita bercakap tentang satu kemungkinan, struktur data dipanggil indone a.
Jadi inilah perwakilan visual daripada indone a.
>> Seperti gambar mencadangkan, indone yang adalah struktur data pokok yang
nod dihubungkan bersama-sama.
Kami melihat bahawa terdapat dengan jelas akar nod dengan beberapa pautan untuk melanjutkan
nod lain.
Tetapi apakah setiap nod terdiri daripada?
Jika kita menganggap bahawa kita menyimpan kunci dengan hanya aksara abjad, dan
kita tidak mengambil berat tentang permodalan, inilah definisi nod yang
memadai.
>> Satu objek yang jenis adalah struct nod mempunyai dua bahagian
dipanggil data dan kanak-kanak.
Kami telah meninggalkan sebahagian data sebagai komen diganti oleh komponen
pengisytiharan apabila nod struct adalah yang diperbadankan di program C.
Bahagian data nod mungkin Nilai boolean untuk menunjukkan sama ada atau
tidak nod mewakili siap daripada kunci kamus atau ia mungkin
string mewakili definisi sebuah kata dalam kamus.
>> Kami akan menggunakan muka senyum untuk menunjukkan apabila data adalah di dalam nod.
Terdapat 26 elemen dalam kami anak-anak pelbagai, satu indeks
setiap watak abjad.
Kami akan melihat kepentingan ini tidak lama lagi.
>> Mari kita melihat dengan lebih dekat nod akar dalam rajah kami, yang tidak mempunyai data
yang dikaitkan dengannya, seperti yang ditunjukkan oleh ketiadaan muka senyum dalam
bahagian data.
Anak panah bermula dari bahagian-bahagian array kanak-kanak mewakili bukan nod-
petunjuk untuk nod lain.
Sebagai contoh, anak panah bermula dari elemen kedua kanak-kanak
mewakili huruf B yang dalam kunci kamus.
Dan dalam gambar rajah yang lebih besar kita labelkan ia dengan B.
>> Perhatikan bahawa dalam gambar rajah yang lebih besar, apabila kita menarik penunjuk kepada nod yang lain, ia
Tidak kira di mana mata panah memenuhi nod yang lain.
Indone sampel kamus kami mengandungi dua perkataan, itu dan zum.
Mari kita berjalan melalui satu contoh melihat ke atas data untuk kunci.
>> Katakan kita mahu mencari yang nilai yang sepadan untuk mandi utama.
Kami akan mula kelihatan kami sehingga pada nod akar.
Maka kita akan mengambil huruf pertama kami utama, B, dan mencari yang sepadan
melihat pada kanak-kanak pelbagai kami.
Perhatikan bahawa ada hanya 26 tempat dalam array, satu untuk setiap huruf
abjad.
Dan kami akan mempunyai tempat mewakili huruf abjad teratur.
>> Kita akan melihat indeks kedua kemudian, indeks satu, untuk B. Secara umum, jika kita
mempunyai beberapa abjad watak C kita boleh menentukan tempat yang sama
dalam pelbagai kanak-kanak yang menggunakan pengiraan seperti ini.
Kami boleh menggunakan kanak-kanak yang lebih besar array jika kita mahu menawarkan kelihatan daripada
kunci dengan pelbagai rangkaian aksara, seperti keseluruhan
Watak ASCII ditetapkan.
>> Dalam kes ini, penunjuk pada kanak-kanak pelbagai kami di
indeks seseorang tidak batal.
Oleh itu, kita akan terus mencari sehingga mandi utama.
Jika kita pernah dihadapi penunjuk null di tempat yang betul dalam kanak-kanak
array sementara kami dilalui nod, maka kita akan katakan kita yang
tidak dapat mencari apa-apa untuk utama yang.
>> Sekarang, kita akan mengambil surat kedua utama kami, A, dan terus mengikuti
petunjuk dengan cara ini sehingga kita sampai ke akhir utama kami.
Jika kita sampai ke akhir kunci tanpa memukul apa-apa buntu, petunjuk batal,
seperti yang berlaku di sini, maka kita hanya perlu menyemak satu lagi perkara.
Adalah kunci ini sebenarnya di dalam kamus?
>> Jika demikian, kita perlu mencari nilai, baik yang icon muka senyum dalam rajah kami di mana
perkataan berakhir.
Jika ada sesuatu yang lain disimpan dengan data, maka kita boleh kembali.
Sebagai contoh, zoo utama tidak dalam kamus, walaupun kita boleh mempunyai
sampai ke penghujung kunci ini tanpa memukul penunjuk batal, sementara kami
melelar melalui indone itu.
>> Jika kita cuba untuk mencari mandi utama, kedua untuk pelbagai indeks nod lepas,
sepadan dengan huruf H, akan memegang penunjuk null.
Jadi mandi tidak ada di dalam kamus.
Dan sebagainya indone adalah unik kerana kunci tidak pernah jelas disimpan di dalam
struktur data.
Jadi bagaimana kita memasukkan sesuatu ke indone satu?
>> Mari kita memasukkan kunci zoo ke dalam indone kami.
Ingat bahawa muka senyum pada satu nod boleh sesuai dalam kod untuk mudah
Nilai boolean untuk menunjukkan zoo yang di dalam kamus atau ia boleh
sesuai dengan maklumat lanjut yang kita ingin kaitkan dengan zoo utama,
seperti definisi perkataan atau sesuatu yang lain.
Dalam beberapa cara, proses untuk memasukkan sesuatu ke dalam indone yang adalah sama dengan
melihat ke atas sesuatu di indone a.
>> Kami akan bermula dengan nod akar sekali lagi, petunjuk berikut bersamaan dengan
huruf utama kami.
Nasib baik, kami dapat mengikuti petunjuk sepanjang jalan sehingga kita mencapai
akhir kunci.
Sejak zoo adalah awalan perkataan zoom, yang merupakan ahli
kamus, kita tidak perlu memperuntukkan sebarang nod baru.
>> Kita boleh mengubah nod untuk menandakan bahawa jalan watak-watak utama untuk
ia merupakan penting dalam kamus kami.
Sekarang, mari kita cuba memasukkan MANDI utama ke indone itu.
Kita bermula pada nod akar dan ikuti petunjuk lagi.
Tetapi dalam keadaan ini, kita mencapai mati seorang berakhir sebelum kita dapat sampai ke
akhir kunci.
Sekarang, kita perlu memperuntukkan beberapa baru nod perlu memperuntukkan yang baru
nod bagi setiap baki surat utama kami.
>> Dalam kes ini, kita hanya perlu untuk memperuntukkan satu nod baru.
Maka kita perlu membuat indeks H rujukan nod baru ini.
Sekali lagi, kami boleh mengubah suai nod untuk menunjukkan bahawa laluan aksara
yang membawa kepada ia merupakan utama dalam kamus kami.
Mari kita sebab tentang asimptot kerumitan prosedur kami bagi
dua operasi.
>> Kami melihat bahawa kedua-dua kes bilangan daripada langkah algoritma kami mengambil masa telah
berkadar dengan bilangan huruf dalam kata kunci.
Betul.
Apabila anda mahu mencari perkataan dalam indone anda hanya perlu melelar melalui
huruf satu demi satu sehingga anda sama ada sampai ke akhir perkataan atau
menemui jalan buntu di indone itu.
>> Dan apabila anda ingin memasukkan kunci yang pasangan nilai ke indone yang menggunakan
prosedur yang kita dibincangkan, kes yang paling teruk akan anda memperuntukkan nod baru
untuk setiap huruf.
Dan kita akan menganggap peruntukan yang adalah operasi masa yang sama.
Jadi, jika kita menganggap bahawa panjang utama adalah disempadani oleh yang tetap tetap, kedua-dua
kemasukan dan mencari adalah malar operasi masa untuk indone a.
>> Jika kita tidak membuat andaian ini yang panjang utama disempadani oleh tetap
berterusan, maka lampiran dan mencari, dalam kes paling teruk, adalah linear dalam
Panjang kunci.
Perhatikan bahawa bilangan item yang disimpan di indone tidak menjejaskan rupa sehingga
atau masa kemasukan.
Ia hanya kesan daripada Panjang kunci.
>> Sebaliknya, menambah catatan untuk, katakan, jadual hash cenderung untuk membuat
masa depan mencari lebih perlahan.
Manakala ini mungkin berbunyi menarik pada mulanya, kita harus ingat bahawa
kerumitan asimptot baik tidak bermakna dalam amalan data yang
struktur semestinya luar teguran.
Kami juga perlu mengambil kira bahawa untuk menyimpan perkataan dalam indone kita perlukan, yang paling teruk
kes, beberapa nod berkadar dengan panjang perkataan itu sendiri.
>> Percubaan yang cenderung untuk menggunakan banyak ruang.
Itu berbeza dengan jadual hash, di mana kita hanya perlu satu nod baru untuk
menyimpan beberapa pasangan nilai utama.
Kini, sekali lagi dalam teori, ruang yang besar penggunaan tidak kelihatan seperti yang besar
berurusan, terutamanya yang moden komputer mempunyai gigabait dan
gigabait memori.
Tetapi ternyata bahawa kita masih mempunyai bimbang tentang penggunaan memori dan
organisasi demi Prestasi, kerana komputer moden
mempunyai mekanisme di tempat di bawah hud untuk mempercepatkan akses ingatan.
>> Tetapi mekanisme ini berfungsi terbaik apabila Akses tak memori dibuat padat
kawasan atau kawasan-kawasan.
Dan nod indone yang boleh tinggal mana-mana sahaja dalam timbunan itu.
Tetapi ini adalah keseimbangan bahawa kita perlu mengambil kira.
>> Ingat bahawa, apabila memilih data yang struktur untuk tugas tertentu, kita
perlu memikirkan apa jenis operasi struktur data yang perlu
sokongan dan berapa banyak prestasi setiap mereka
perkara-perkara operasi kepada kami.
Operasi-operasi ini mungkin juga melampaui hanya
lihat asas dan sisipan.
Katakan kita mahu melaksanakan jenis yang fungsi auto-lengkap, banyak
seperti enjin carian Google tidak.
Iaitu, kembali semua kunci dan nilai-nilai yang berpotensi
mempunyai awalan yang diberikan.
>> Indone adalah unik berguna untuk operasi ini.
Ia mudah untuk melelar melalui yang indone bagi setiap watak
awalan.
Sama seperti operasi mencari, kita boleh mengikuti petunjuk
watak oleh watak.
Kemudian, apabila kita tiba di akhir awalan, kita boleh melelar melalui
baki bahan struktur data sejak mana-mana kekunci di luar
ketika ini mempunyai awalan.
>> Ia juga mudah untuk mendapatkan penyenaraian ini mengikut abjad sejak
unsur-unsur pelbagai kanak-kanak yang yang diperintahkan mengikut abjad.
Jadi mudah-mudahan anda akan mempertimbangkan pemberian cuba cuba.
Saya Kevin Schmid, dan ini adalah CS50.
>> Ah, ini adalah permulaan penurunan.
Saya minta maaf.
Maaf.
>> Menyerang empat.
Aku keluar.
Maaf.
Maaf untuk membuat orang yang telah menyunting laman ini pergi gila.
>> Maaf.
Maaf.
>> SPEAKER 1 Syabas.
Yang benar-benar dilakukan dengan baik.