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. Maaf. Maaf. 

Menyerang empat. Aku keluar. Maaf. Maaf. Maaf. Maaf untuk membuat orang yang telah menyunting laman ini pergi gila. 

Maaf. Maaf. Maaf. Maaf. 

SPEAKER 1 Syabas. Yang benar-benar dilakukan dengan baik.