[MUSIK BERMAIN] DAVID MALAN: Ini adalah CS50. Dan ini adalah kedua-dua awal dan end-- seperti literally-- hampir akhirnya dari minggu ke enam. 

Saya fikir saya akan berkongsi sedikit dari fakta yang menyenangkan. Saya telah ditarik ke atas ini dari data semester terakhir ini ditetapkan. Anda mungkin ingat bahawa kami meminta anda pada setiap p bentuk set jika anda telah melihat dalam talian atau jika anda telah menghadiri secara peribadi. Dan di sini adalah data. Jadi hari ini adalah sangat diramalkan. Tapi kami ingin menghabiskan sedikit waktu dengan Anda tetap. Apakah ada yang mau menduga mengapa ini grafik sangat bergerigi, naik turun, naik turun, secara konsisten? Apa yang setiap satu daripada puncak dan palung mewakili? 

PENONTON: [didengar] DAVID MALAN: Memang. Dan yang lebih lucu, Allah melarang, kita memegang satu ceramah pada hari Jumaat pada awal semester, itulah yang kita lihat berlaku. Jadi hari ini, kita mengambil dalam sedikit lebih lanjut mengenai struktur data. Dan untuk memberikan anda lebih banyak dari yang kukuh model mental untuk masalah di lima, yang kini keluar. Salah ejaan, di mana, kita akan menyerahkan fail teks beberapa 100,000 ditambah kata-kata bahasa Inggeris, dan Anda akan mempunyai untuk memikirkan bagaimana untuk cerdik beban mereka ke dalam memori, ke dalam RAM, menggunakan beberapa data struktur pilihan anda. 

Sekarang satu struktur data tersebut boleh berkenaan, tetapi mungkin tidak boleh, senarai yang agak mudah dikaitkan, yang kami memperkenalkan masa lalu. Dan senarai yang dikaitkan mempunyai sekurang-kurangnya satu kelebihan berbanding array. Apa yang salah satu keuntungan dari senarai berpaut boleh dikatakan? 

PENONTON: Pemasukan. 

DAVID MALAN: Pemasukan. Apa yang kamu maksudkan dengan itu? 

PENONTON: Di mana-mana bersama-sama senarai [terdengar]. 

DAVID MALAN: Baik. Oleh itu, anda boleh memasukkan elemen di mana sahaja anda mahu di tengah-tengah senarai tanpa perlu shuffle apa-apa, mana kita membuat kesimpulan, dalam pengasingan kami perbincangan, bukan semestinya satu perkara yang baik, kerana ia mengambil masa untuk benar-benar bergerak semua jenis manusia yang kiri atau kanan. Dan sebagainya dengan senarai yang disambungkan, anda boleh hanya memperuntukkan dengan malloc, nod baru, dan kemudian mengemas beberapa pointers-- dua, tiga operasi max-- dan kita mampu untuk slot seseorang di mana-mana sahaja dalam senarai. 

Apa lagi yang berfaedah tentang senarai berpaut? Ya? 

PENONTON: [didengar] DAVID MALAN: Perfect. Sempurna. Ia benar-benar dinamik. Dan bahawa anda tidak melakukan, terlebih dahulu, untuk beberapa ukuran yang tetap sebahagian memori, seperti anda akan mempunyai untuk dengan array, terbalik di mana adalah bahawa anda boleh memperuntukkan nod hanya pada permintaan itu dengan hanya menggunakan lebih banyak ruang kerana anda benar-benar perlu. Sebaliknya dengan array, anda mungkin sengaja memperuntukkan terlalu sedikit. Dan kemudian ia hanya akan menjadi sakit di leher mengagihkan semula lokasi baru yang lebih besar, menyalin semuanya berakhir, membebaskan array lama, dan kemudian bergerak perniagaan anda. Atau lebih teruk lagi, anda mungkin memperuntukkan cara memori lebih daripada yang anda benar-benar perlu, dan supaya anda akan mempunyai sangat pelbagai jarang penduduknya, boleh dikatakan. 

Jadi senarai berpaut memberi anda ini kelebihan dan memberi fleksibiliti dengan sisipan dan penghapusan kata. Tapi tentunya mesti ada harga yang harus dibayar. Malah, salah satu tema dijelajahi dengan kuiz sifar adalah beberapa trade-off kita telah melihat setakat ini. Jadi apa harga yang telah dibayar atau yang downside dari senarai berpaut? Yeah. 

PENONTON: Tiada akses rawak. 

DAVID MALAN: Tiada akses rawak. Tapi siapa yang peduli? Capaian rawak tidak bunyi yang menarik. 

PENONTON: [didengar] DAVID MALAN: Tepat sekali. Jika anda ingin mempunyai yang algorithm-- tertentu dan biarkan aku sebenarnya mencadangkan carian binari khususnya, yang adalah salah satu kami telah digunakan agak bit-- yang jika anda tidak mempunyai akses rawak, Anda tidak boleh melakukan itu aritmetik mudah mencari elemen seperti tengah dan melompat hak untuk itu. Anda malah harus bermula yang pertama elemen dan linear mencari dari kiri ke kanan jika anda mahu untuk mencari tengah atau sebarang unsur lain. 

PENONTON: Ia mungkin mengambil masa lebih banyak memori. 

DAVID MALAN: Membawa lebih banyak memori. Di mana ialah tambahan biaya yang berasal dari dalam ingatan? 

PENONTON: [didengar] DAVID MALAN: Tepat sekali. Dalam kes ini di sini, kami mempunyai daftar link untuk bilangan bulat, tetapi kita dua kali ganda jumlah memori kita perlu dengan juga menyimpan pointer ini. Sekarang kurang dari masalah besar seperti struct anda mendapatkan yang lebih besar dan anda menyimpan bukan angka tetapi mungkin seorang pelajar atau beberapa objek lain. Tapi yang pasti tetap. Dan sebagainya beberapa operasi pada daftar terkait dipanggil adalah O besar linear n--. Hal-hal seperti penyisipan atau carian atau penghapusan dalam hal unsur kebetulan berada di akhir sangat daftar apakah itu disusun atau tidak. 

Kadang-kadang anda mungkin beruntung dan di batas sehingga lebih rendah pada operasi ini juga mungkin masa yang berterusan jika anda selalu melihat elemen yang pertama, misalnya. Tetapi pada akhirnya, kita berjanji untuk mencapai kaedah berpotensi suci struktur data, atau beberapa daripadanya perkiraan, dengan cara masa yang sama. Bolehkah kita dapati unsur-unsur atau menambah unsur-unsur atau mengeluarkan unsur-unsur dari senarai? Kita akan lihat tidak lama lagi. Dan ternyata yang satu mekanisme kami akan mula menggunakan hari ini, penggunaan tahunan p meletakkan lima, sebenarnya cukup akrab. Sebagai contoh, jika ini adalah sekumpulan buku ujian, yang masing-masing mempunyai pelajar pertama nama dan nama akhir di atasnya, dan saya menjemput mereka dari pada akhir peperiksaan, dan mereka semua cukup banyak dalam susunan rawak, dan kami mahu pergi tentang menyortir ini ujian sehingga setelah dinilai ia hanya lebih mudah dan lebih cepat untuk menyerahkan mereka kembali kepada pelajar-pelajar mengikut abjad. Apa yang akan menjadi naluri anda untuk timbunan ujian seperti ini? 

Nah, jika anda seperti saya, anda mungkin akan melihat bahawa ini adalah m, jadi saya akan ke semacam meletakkan ini ke dalam, jika ini adalah meja saya atau lantai di mana Saya menyebarkan perkara out-- atau array saya really-- Saya mungkin meletakkan semua Cik di sana. Oh. Berikut adalah gred A. Jadi saya mungkin meletakkan Seperti di sini. Oh. Berikut adalah satu lagi A. Saya akan untuk meletakkan bahawa di sini. Berikut adalah Z. yang Di sini adalah satu lagi M. Dan sebagainya Saya mungkin mula membuat tumpukan seperti ini. Dan kemudian mungkin saya akan pergi nanti dan semacam sangat nitpicky-ly semacam buasir individu. Tapi yang penting saya akan melihat di input yang saya tangan dan saya akan membuat beberapa dikira keputusan berdasarkan input itu. Jika ia bermula dengan A, meletakkan ia di sana. Jika ia bermula dengan Z, meletakkannya di di sana, dan segala sesuatu di antara. 

Jadi ini adalah satu teknik yang umumnya dikenali sebagai hashing-- H-A-S-H-- yang secara umum berarti mengambil sebagai input dan menggunakan input itu untuk menghitung nilai, umumnya nombor, dan bahawa jumlah adalah indeks ke dalam simpanan yang bekas, seperti array. Jadi dengan kata lain, saya mungkin mempunyai fungsi hash, seperti yang saya lakukan dalam kepala saya, bahawa jika saya melihat seseorang yang nama yang bermula dengan A, Saya akan peta yang kepada sifar dalam kepala saya. Dan jika saya melihat seseorang dengan Z, saya akan peta yang ke 25 di kepala saya dan kemudian memasukkan ke dalam tumpukan terakhir paling. 

Sekarang, jika anda berfikir tentang tidak otak saya tetapi program C, apa nombor boleh anda bergantung kepada untuk mencapai keputusan yang sama? Dengan kata lain, jika anda mempunyai karakter ASCII A, bagaimana anda menentukan apa baldi untuk memasukkannya ke dalam? Anda mungkin tidak mahu memasukkannya ke dalam baldi 65, yang akan menjadi seperti di sana tanpa alasan yang baik. Di mana anda mahu meletakkan A dari segi nilai ASCII? Di manakah anda mahu lakukan untuk ASCII nilai untuk datang dengan baldi yang lebih pintar untuk memasukkannya ke dalam? 

PENONTON: Minus A. 

DAVID MALAN: Ya. Jadi tolak A atau tolak khususnya 65 jika ia A. modal Atau 98 jika itu adalah huruf kecil a. Dan sebagainya yang akan membolehkan kita untuk, sangat sederhana dan sangat deret hitung, memasukkan sesuatu ke dalam baldi seperti itu. Jadi ternyata kita sebenarnya ini juga walaupun dengan kuiz. 

Jadi, anda mungkin ingat anda dilingkari anda Nama mengajar rakan-rakan yang di sampulnya. Dan nama-nama yang TF telah dianjurkan ke dalam ruangan ini mengikut abjad, baik, percaya atau tidak, apabila semua 80 ditambah daripada kita bersama-sama malam yang lain untuk kelas, langkah terakhir dalam proses penilaian kami adalah untuk hash kuis menjadi besar ruang lantai di [terdengar] dan untuk meletakkan kuiz semua orang daripada betul-betul perintah TF mereka nama-nama di kulit, kerana maka ia lebih mudah untuk kita untuk mencari yang menggunakan linear mencari atau beberapa jenis kepintaran untuk TF untuk mencari atau kuiz penuntutnya. 

Jadi idea ini dari hashing yang anda akan lihat adalah cukup kuat sebenarnya cukup perkara biasa dan sangat intuitif, seperti mungkin membahagi dan menakluk adalah pada minggu sifar. Saya cepat ke depan untuk hackathon yang beberapa tahun yang lalu. Ini adalah Zamyla dan beberapa lain pelajar ucapan kakitangan kerana mereka masuk. Dan kami mempunyai sejumlah besar lipat meja ada dengan tag nama. Dan kami telah tag nama yang dianjurkan dengan seperti Seperti di sana dan Zs di sana. Dan jadi salah satu TF sangat cerdik menulis ini sebagai petunjuk untuk hari itu. Dan pada minggu ke-12 semester ini semua masuk akal dan semua orang tahu apa yang perlu dilakukan. Tapi bila-bila masa anda mempunyai antri dengan cara yang sama, Anda melaksanakan tanggapan yang sama hash. Jadi mari kita merumuskan ia sedikit. Berikut adalah array. Ia tertarik dengan sedikit lebar hanya untuk menggambarkan, secara visual, supaya kita meletakkan tali dalam hal seperti ini. Dan mudah ini jelas dari saiz 26 jumlah. Dan perkara yang disebut meja sewenang-wenangnya. Tapi ini hanya rendition artis apa jadual hash mungkin. 

Jadi jadual hash sekarang akan menjadi struktur data tahap yang lebih tinggi. Pada akhir hari kita akan melihat bahawa anda boleh melaksanakan jadual hash, yang jauh seperti talian check-in pada hackathon seperti ini meja digunakan untuk pengisihan buku peperiksaan. Tetapi jadual hash semacam tingkat tinggi konsep yang boleh menggunakan array di bawah tenda untuk melaksanakannya, atau bisa menggunakan senarai panjang, atau bahkan mungkin beberapa lain-lain struktur data. Dan sekarang itu pengambilan theme-- beberapa bahan-bahan asas seperti array dan bangunan ini menghalang sekarang daripada senarai panjang dan melihat apa lagi yang kita boleh membina di atas mereka, seperti bahan-bahan ke dalam resipi, membuat lebih banyak hasil akhir yang menarik dan berguna. 

Jadi dengan jadual hash kita mungkin melaksanakannya dalam memori bergambar seperti ini, tetapi bagaimana mungkin ia sebenarnya dikodkan sehingga? Yah, mungkin hanya sebagai adalah ini. Jika KEUPAYAAN dalam semua topi, hanya beberapa constant-- misalnya 26, untuk 26 huruf alphabet-- yang Saya sebut meja variabel saya, dan saya mungkin mendakwa bahawa saya akan meletakkan bintang arang di sana, atau tali. Jadi ia semudah ini jika anda ingin menerapkan jadual hash. Namun, ini adalah benar-benar hanya array. Tetapi sekali lagi, hash meja kini apa yang kita akan memanggil jenis data abstrak itu hanya semacam lapisan konseptual di atas sesuatu yang lebih biasa sekarang seperti array. 

Sekarang, bagaimana kita pergi mengenai menyelesaikan masalah? Nah, sebelum ini saya mempunyai mewah mempunyai ruang meja yang cukup di sini supaya saya dapat meletakkan kuiz mana-mana sahaja yang saya mahu. Jadi Seperti yang pergi di sini. Zs mungkin pergi di sini. Cik boleh pergi di sini. Dan kemudian saya mempunyai beberapa ruang tambahan. Tetapi ini adalah sedikit hak menipu sekarang kerana jadual ini, jika saya benar-benar menganggapnya sebagai array, hanya akan menjadi dari beberapa saiz tetap. 

Jadi secara teknikal, jika saya menarik sehingga kuiz lain pelajar dan melihat, oh, orang ini nama bermula dengan A juga, Aku agak mahu meletakkan ia di sana. Tetapi sebaik sahaja saya meletakkan di sana, jika jadual ini sememangnya merupakan array, Saya akan dapat mengatasi atau clobbering sesiapa kuiz ini adalah pelajar. Betul? Jika ini adalah array, hanya satu hal boleh pergi dalam setiap sel-sel atau elemen. Oleh itu, saya jenis mempunyai untuk memilih dan memilih. 

Sekarang sebelum saya jenis menipu dan melakukan ini atau saya hanya jenis disusun mereka di atas satu sama lain. Tetapi itu tidak akan terbang dalam kod. Jadi, di mana saya boleh meletakkan pelajar kedua yang namanya adalah A jika semua saya harus ialah ruang jadual yang sedia ada? Dan saya telah menggunakan tiga slot dan ia kelihatan seperti hanya ada beberapa orang lain. Apa yang anda boleh lakukan? PENONTON: [didengar] DAVID MALAN: Ya. Mungkin mari kita tetap sederhana. Betul? Ia tidak sesuai di mana saya mahu meletakkannya. Jadi, saya akan meletakkan ia dari segi teknikal di mana B akan pergi. Sekarang, tentu saja, saya mula melukis diri saya ke sudut. Jika saya mendapat kepada pelajar yang mana nama sebenarnya B, sekarang B akan dipindahkan sedikit ke hadapan, sebagai mungkin berlaku, ya, jika ini adalah a, kini ia mempunyai pergi di sini. 

Dan jadi ini dengan cepat boleh menjadi bermasalah, tapi teknik yang benar-benar disebut sebagai linear menyelidik, di mana anda hanya menganggap anda array untuk menjadi sepanjang garis. Dan anda hanya jenis menyiasat atau memeriksa setiap elemen yang ada mencari tempat yang tersedia. Dan sebaik sahaja anda mencari satu, anda menjatuhkannya di sana. 

Sekarang, harga yang dibayar sekarang untuk penyelesaian ini adalah apa? Kami mempunyai pelbagai saiz tetap, dan apabila saya memasukkan nama ke dalamnya, sekurang-kurangnya pada peringkat awal, apa yang waktu berjalan penyisipan untuk menempatkan pelajar kuiz dalam baldi yang betul? Big O dari apa? 

PENONTON: n. DAVID MALAN: Aku mendengar O besar n. Tidak benar. Tapi kita akan mengusik selain mengapa hanya dalam beberapa saat. Apa lagi yang mungkin? 

PENONTON: [didengar] DAVID MALAN: Dan biarkan aku melakukannya secara visual. Jadi kira ini adalah surat yang S. 

PENONTON: Ia adalah salah. DAVID MALAN: Ini salah satu. Betul? Ini adalah sebuah array, yang bermakna kita mempunyai akses rawak. Dan jika kita berfikir tentang ini sebagai sifar dan kerana ini 25, dan kita sedar bahawa, oh, inilah input S saya, Saya pasti boleh menukar S, karakter ASCII, ke nombor yang sama antara sifar dan 25 dan kemudian dengan serta-merta meletakkannya di tempatnya. 

Tapi tentu saja, sebaik sahaja saya sampai ke orang kedua yang memiliki nama adalah A atau B atau C akhirnya, jika saya telah menggunakan linear menyelesaikan sesuatu sebagai penyelesaian saya, masa yang berjalan dari sisipan dalam kes yang paling teruk sebenarnya akan berpindah ke apa? Dan aku mendengarnya di sini betul awal. PENONTON: [didengar] DAVID MALAN: Jadi adalah n memang sekali anda mempunyai satu set data yang cukup besar. Jadi, dalam satu tangan, jika array cukup besar dan data anda jarang cukup, Anda mendapatkan waktu ini tetap indah. Tetapi sebaik sahaja anda mula mendapatkan lebih banyak dan lebih banyak elemen, dan hanya statistik anda mendapat lebih ramai orang dengan huruf A sebagai nama atau huruf B, ia boleh berpotensi berpindah ke sesuatu yang lebih linear. Jadi tidak cukup sempurna. Oleh itu, kita boleh melakukan yang lebih baik? 

Nah, apa yang kami penyelesaian sebelum apabila kita ingin mempunyai dinamisme lebih daripada sesuatu seperti array dibenarkan? PENONTON: [didengar] DAVID MALAN: Apa yang kami memperkenalkan? Yeah. Jadi senarai berpaut. Nah, mari kita lihat apa yang terkait senarai mungkin lakukan untuk kita sebagai gantinya. Baiklah, biar saya mencadangkan kita bahawa menarik gambar seperti berikut. Sekarang ini adalah berbeza gambar dari contoh daripada teks yang berbeza, sebenarnya, yang adalah benar-benar menggunakan pelbagai saiz 31. Dan penulis ini hanya memutuskan untuk hash tali tidak berdasarkan nama orang itu, tetapi berdasarkan tarikh lahir mereka. Tanpa mengira bulan, mereka membuat kesimpulan jika anda dilahirkan pada tanggal satu bulan yang atau 31 bulan, penulis akan hash berdasarkan nilai itu, untuk menyebarkan nama keluar sedikit lebih daripada 26 tempat-tempat mungkin mengizinkan. Dan mungkin itu seragam yang lebih sedikit daripada pergi dengan huruf abjad, kerana sudah tentu ada mungkin lebih ramai orang di dunia dengan nama-nama yang awal dengan A daripada pasti beberapa huruf lain abjad. Jadi mungkin ini adalah sedikit seragam lebih, dengan asumsi taburan seragam bayi di dalam sebulan. 

Tetapi, sudah tentu, ini masih tidak sempurna. Betul? Kami mengalami perlanggaran. Beberapa orang dalam struktur data masih mempunyai tarikh lahir yang sama sekurang-kurangnya anda tidak kira bulan. Tetapi apa yang telah penulis lakukan? Nah, ia kelihatan seperti kita mempunyai array di sebelah kiri ditarik menegak, tapi itu hanya persembahan artis. Tidak peduli ke arah mana anda menarik array, ia masih array. Apa ini pelbagai rupanya? 

PENONTON: Senarai Berkaitan. 

DAVID MALAN: Ya. Ia kelihatan seperti ini merupakan array linked list. Jadi sekali lagi, hingga saat ini semacam menggunakan struktur data sekarang sebagai bahan untuk lebih penyelesaian yang menarik, Anda benar-benar boleh mengambil asas, seperti array, dan kemudian mengambil sesuatu yang lebih menarik seperti senarai berpaut dan bahkan menggabungkan mereka ke dalam yang lebih struktur data yang lebih menarik. Dan sesungguhnya, ini juga akan dipanggil jadual hash, mana array adalah benar-benar jadual hash, tetapi jadual hash ini rantai, boleh dikatakan, yang boleh membesar atau mengecilkan berdasarkan beberapa elemen yang anda mahu masukkan. 

Sekarang, dengan itu, apa yang masa yang berjalan sekarang? Jika saya ingin memasukkan seseorang yang ulang tahun adalah 31 Oktober, di mana ia tidak pergi? Baik. Di bahagian paling bawah di mana dikatakan 31. Dan itu sempurna. Itu adalah masa yang berterusan. Tapi bagaimana kalau kita mencari orang lain yang ulang tahun ini, mari kita lihat, Oktober, November, 31 Disember? Di mana yang dia akan pergi? Hal yang sama. Dua langkah walaupun. Itu yang berterusan walaupun bukan? Baik. Pada masa ini ia adalah. Tetapi dalam kes umum, semakin banyak orang yang kita menambah, probabilistically, kita akan untuk mendapatkan lebih banyak dan lebih perlanggaran. 

Ini adalah sedikit lebih baik kerana dari segi teknikal sekarang rantai saya boleh berada di dalam kes terburuk berapa lama? Jika saya memasukkan n orang ke dalam ini lebih struktur data yang canggih, n orang, dalam kes yang paling teruk ia akan menjadi n. Mengapa? 

PENONTON: Kerana jika semua orang mempunyai hari jadi yang sama, mereka akan menjadi satu baris. DAVID MALAN: Perfect. Mungkin sedikit dibuat-buat, tetapi benar-benar dalam kes paling teruk, jika semua orang mempunyai hari jadi yang sama, diberi input yang anda miliki, Anda akan mempunyai rangkaian secara besar-besaran yang lama. Dan sebagainya, anda boleh menyebutnya hash table, tapi sebenarnya itu hanya daftar besar dikaitkan dengan banyak keseluruhan ruang kosong. Tetapi secara umum, jika kita menganggap bahawa sekurang-kurangnya hari lahir adalah uniform-- dan mungkin tidak. Saya sedang membuat hal itu. Tetapi jika kita mengambil alih, untuk kepentingan diskusi bahwa mereka, maka secara teori, jika ini adalah perwakilan menegak array, baik maka mudah-mudahan anda akan mendapatkan rantaian yang, anda tahu, kira-kira sama panjang di mana masing-masing ini merupakan hari bulan. 

Sekarang jika terdapat 31 hari dalam bulan ini, itu berarti masa saya berjalan benar-benar adalah O besar n lebih dari 31, yang merasa lebih baik daripada linear. Tetapi apa yang adalah salah satu daripada kami komitmen beberapa minggu yang lalu apabila ia datang untuk menyatakan masa yang berjalan dari algoritma? Hanya hanya melihat perkataan perintah yang tinggi. Betul? 31 adalah pasti membantu. Tapi ini masih O besar n. Tetapi salah satu tema dari permasalahan yang lima akan menjadi untuk mengakui bahawa benar-benar, asimtotik, secara teori struktur data ini tidak lebih baik daripada hanya satu senarai yang besar yang berkaitan. Dan memang, dalam kes paling teruk, ini jadual hash mungkin turun ke dalam. 

Tetapi dalam dunia nyata, dengan kita manusia bahwa Mac sendiri atau komputer peribadi atau apa sahaja dan menjalankan dunia nyata perisian data dari dunia nyata, yang algoritma yang anda akan lebih suka? Salah satu yang mengambil langkah-langkah akhir atau salah satu yang mengambil n dibahagikan dengan 31 langkah untuk mencari sedikit data atau untuk mencari beberapa maklumat? Maksud saya, benar-benar 31 jenama perbezaan dalam dunia sebenar. Ia adalah 31 kali lebih cepat. Dan kita manusia pasti akan menghargai itu. 

Jadi mewujudkan dikotomi ada antara benar-benar bercakap tentang hal-hal secara teori dan asimptot yang pasti mempunyai nilai seperti yang kita lihat, tapi dalam dunia sebenar, jika anda mengambil berat tentang hanya membuat bahagia manusia untuk input umum, Anda sangat baik mungkin mahu menerima hakikat bahawa, ya, ini adalah linear, tetapi ia 31 kali lebih cepat linear mungkin. Dan lebih baik lagi, kita tidak hanya perlu melakukan sesuatu sewenang-wenang seperti tarikh lahir yang, kita boleh menghabiskan sedikit lebih banyak masa dan kepandaian dan berfikir tentang apa yang kita boleh lakukan, diberi nama seseorang dan mungkin tarikh lahir mereka untuk menggabungkan bahan-bahan untuk mencari tahu sesuatu yang benar-benar lebih seragam dan kurang bergerigi, boleh dikatakan dari gambar ini kini menunjukkan ia mungkin. Bagaimana kita boleh melaksanakan ini dalam kod? Baiklah, biar saya mencadangkan kita bahawa hanya meminjam sintaks kami telah digunakan beberapa kali setakat ini. Dan saya akan mendefinisikan nod, yang sekali lagi adalah istilah generik untuk hanya beberapa bekas untuk beberapa struktur data. Saya akan mencadangkan supaya string akan di sana. Tetapi kita akan mula mengambil mereka latihan roda off sekarang. 

Tidak ada perpustakaan CS50 lebih benar-benar, melainkan jika anda mahu menggunakannya untuk akhir anda Projek ini, yang baik-baik saja, tetapi sekarang kita akan menarik kembali tirai dan berkata ia hanya satu bintang arang. Jadi perkataan ada akan menjadi nama orang yang bersangkutan. Dan sekarang saya mempunyai link di sini untuk nod seterusnya sehingga ini mewakili setiap satu daripada nod dalam rantai, berpotensi, senarai berpaut. 

Dan sekarang bagaimana saya menyatakan jadual hash itu sendiri? Bagaimana saya mengisytiharkan seluruh struktur ini? Nah, benar-benar, sama seperti saya menggunakan pointer hanya elemen pertama dari senarai sebelum ini, juga boleh saya katakan Aku hanya perlu sekelompok pointer untuk melaksanakan jadual ini hash keseluruhan. Saya akan mempunyai array dipanggil jadual untuk jadual hash. Ia akan menjadi kapasiti saiz. Itu berapa banyak elemen boleh muat di dalamnya. Dan masing-masing dari elemen-elemen dalam array akan menjadi bintang nod. Mengapa? Well, setiap gambar ini, apa yang saya melaksanakan jadual hash sebagai berkesan pada awalnya adalah hanya array ini yang kita gambarkan secara menegak, setiap kotak yang mewakili pointer. Itulah orang-orang yang mempunyai garis condong melalui mereka hanya null. Dan orang-orang yang mempunyai anak panah akan ke kanan adalah petunjuk yang sebenarnya untuk nod yang sebenarnya, ergo permulaan senarai berpaut. 

Jadi di sini, kemudian, adalah bagaimana kita mungkin melaksanakan jadual hash yang melaksanakan chaining berasingan. Sekarang kita boleh melakukan yang lebih baik? Baiklah saya berjanji Kali terakhir kita boleh mencapai masa yang sama. Dan aku agak memberikan anda masa tetap di sini, tetapi kemudian tidak berkata benar-benar masa tetap kerana ia masih bergantung kepada jumlah beberapa elemen anda memasukkan ke dalam struktur data. Tetapi sekiranya kita melakukan ini. Mari kita kembali ke layar di sini. Kini saya akan projek ini di sini, jelas skrin, dan kira saya melakukan ini. Penulis ingin memasukkan nama Daven di dalam struktur data saya. 

Jadi saya ingin memasukkan string Daven ke dalam struktur data. Bagaimana jika saya tidak menggunakan hash meja, tetapi saya menggunakan sesuatu yang lebih seperti pohon seperti pohon keluarga, di mana anda mempunyai beberapa akar di node atas dan kemudian dan daun yang pergi ke bawah dan ke luar. Katakan itu, saya yang ingin memasukkan ini Daven ke dalam apa yang saat ini senarai main kosong. Saya akan melakukan perkara-perkara berikut: Saya akan mewujudkan nod dalam keluarga ini seperti pohon struktur data yang kelihatan sedikit seperti ini, yang masing-masing persegi panjang telah, katakan, untuk saat 26 unsur-unsur di dalamnya. Dan setiap sel-sel dalam array ini akan untuk mewakili huruf abjad itu. 

Secara khusus, saya akan merawat ini adalah A, maka B, maka C, maka D, satu ini di sini. Jadi ini akan berkesan mewakili huruf D. Tetapi untuk memasukkan semua ini Daven nama saya lakukan sedikit lebih. Jadi, saya terlebih dahulu ke hash, jadi untuk bercakap. Saya akan melihat huruf pertama di Daven yang jelas D, dan saya akan memperuntukkan nod yang kelihatan seperti this-- sebuah segiempat tepat yang besar besar cukup agar sesuai dengan seluruh abjad. 

Sekarang D dilakukan. Kini A. D-A-V-E-N adalah tujuan. Jadi sekarang apa yang akan saya lakukan adalah ini. Sebaik sahaja saya mula notis D tidak ada penunjuk sana. Ia adalah nilai-nilai sampah pada masa ini, atau saya mungkin memulakan ke null. Tetapi saya terus berjalan dengan idea ini membina pokok. Biar saya mengalokasikan lagi salah satu daripada nod yang mempunyai 26 unsur-unsur di dalamnya. 

Dan anda tahu apa? Jika ini hanya nod dalam memori yang Saya buat dengan malloc, menggunakan struct seperti yang kita akan melihat, Saya akan melakukan this-- Aku akan menarik anak panah dari perkara yang diwakili D ke bawah untuk nod baru ini. Dan sekarang, pertama yang akan datang surat atas nama Daven ini, V-- D-A-V-- saya akan pergi ke depan dan menarik nod lain seperti ini, di mana, unsur-unsur V di sini, yang kami akan menarik untuk ups instance--. Kami tidak akan menarik di sana. Ia akan pergi di sini. 

Kemudian kita akan menganggap hal ini menjadi V. Dan kemudian di sini kita akan indeks turun dari V menjadi apa yang kita akan mempertimbangkan E. Dan kemudian dari sini kita akan pergi mempunyai salah satu daripada nod ini di sini. Dan sekarang kita mempunyai soalan untuk menjawab. Saya perlu entah bagaimana menunjukkan bahawa kita berada di akhir string Daven itu. Jadi saya hanya boleh meninggalkan ia null. 

Tapi bagaimana kalau kita mempunyai ini Daven nama penuh juga, yang adalah, seperti yang kita katakan, Davenport? Jadi apa jika Daven adalah sebenarnya substring, awalan tali yang lebih lama? Kita tidak boleh hanya secara kekal mengatakan apa-apa yang sedang berlaku untuk pergi ke sana, kerana kita boleh pernah memasukkan kata seperti Davenport ke dalam Struktur data ini 

Jadi apa yang kita boleh lakukan sebagai gantinya adalah merawat setiap elemen-elemen ini sebagai mungkin mempunyai dua unsur-unsur dalam diri mereka. Salah satunya adalah pointer, memang, seperti yang saya telah lakukan. Jadi setiap kotak-kotak bukan hanya satu sel. Tetapi bagaimana jika atas satu-- satu bahagian bawah ini akan menjadi batal, karena tidak ada Davenport dulu. Bagaimana jika orang yang atas beberapa nilai khas? Dan ia akan menjadi sedikit keras untuk menarik itu ukuran ini. Tapi rasa itu hanya tanda semak. Semak. D-A-V-E-N adalah rentetan dalam struktur data ini. 

Sementara itu, jika saya mempunyai lebih banyak ruang di sini, saya boleh melakukan P-O-R-T, dan saya boleh meletakkan cek di nod yang mempunyai huruf T pada akhir sangat. Jadi ini adalah secara besar-besaran kompleks yang berpandangan struktur data. Dan tulisan tangan saya tentu tidak membantu. Tetapi jika saya ingin memasukkan sesuatu lain, pertimbangkan apa yang kita akan lakukan. Jika kita mahu meletakkan Daud dalam, kita suka mengikut logik yang sama, D-A-V, tapi sekarang saya akan menunjukkan di akhirat unsur bukan dari E, tetapi dari I hingga D. Jadi tidak akan menjadi lebih nod dalam pokok ini. Kita akan mempunyai panggilan malloc lanjut. Tetapi saya tidak mahu membuat keadaan huru-hara lengkap gambar ini. Jadi mari kita bukan melihat satu yang telah pra-dirumuskan seperti ini dengan tidak dot, dot, titik, tetapi array hanya singkatan. Tetapi setiap satu daripada nod dalam pokok ini di sini mewakili thing-- yang sama array Ray dari saiz 26. 

Atau jika kita mahu menjadi sekarang benar-benar betul, apa yang jika nama seseorang sebagai apostrofe, mari kita menganggap bahawa setiap nod sebenarnya mempunyai seperti 27 indeks di dalamnya, bukan sahaja 26. Jadi ini sekarang akan menjadi data yang struktur dipanggil trie-- T-R-saya-E. A indone, yang diduga sejarah nama pintar untuk pokok yang mengoptimumkan pengambilan, yang sudah tentu, dieja dengan I-E supaya ia indone. Tetapi itu adalah sejarah trie. 

Jadi indone adalah data seperti pohon ini struktur seperti pohon keluarga yang pada akhirnya berkelakuan seperti itu. Dan di sini adalah hanya satu lagi contoh sejumlah besar nama-nama orang lain. Tapi pertanyaannya sekarang di tangan adalah apa yang kami memperoleh dengan memperkenalkan dikatakan lebih struktur data yang rumit, dan satu, terus terang, yang menggunakan banyak memori. 

Kerana walaupun, pada masa ini, saya hanya menggunakan penunjuk D dan A dan V dan Es dan Ns, Saya membuang palang pintu dari banyak memori. Tetapi di mana saya menghabiskan satu sumber, Saya cenderung untuk mendapatkan kembali yang lain. Jadi jika saya menghabiskan lebih banyak ruang, apa yang mungkin harapan? Bahawa saya menghabiskan kurang apa? PENONTON: Kurang masa. DAVID MALAN: Masa. Sekarang mengapa yang mungkin? Nah, apa yang pemasukan masa, dari segi O besar sekarang, dari nama seperti Daven atau Davenport atau Daud? Nah, Daven adalah lima langkah. Davenport akan sembilan langkah, jadi ia akan menjadi beberapa langkah. Daud akan menjadi lima langkah juga. Jadi mereka adalah konkrit nombor, tapi pasti ada had atas pada panjang nama seseorang. Dan memang, dalam masalah set lima spesifikasi, kita akan mencadangkan bahawa itu sesuatu itulah aksara 40-beberapa-aneh. 

Realistik, tidak ada seorang pun nama panjang tak terhingga, yang mengatakan bahawa panjang yang nama atau panjang tali yang kita mungkin mempunyai tertentu keadaan struktur ini boleh dibilang apa? Ia adalah malar. Betul? Mungkin yang tetap besar seperti 40-an, tetapi ia adalah tetap. Dan ia tidak mempunyai pergantungan kepada berapa banyak nama-nama lain adalah di dalam struktur data ini. Dalam erti kata lain, jika saya ingin memasukkan sekarang Colton atau Jibril atau Rob atau Zamyla atau Alison atau Belinda atau mana-mana nama-nama lain daripada kakitangan ke dalam data ini struktur, adalah masa yang berjalan memasukkan nama-nama lain akan berada di semua kesan oleh berapa banyak elemen lain dalam struktur data yang sudah? Ia bukan. Betul? Karena kita berkesan dengan menggunakan ini jadual hash multi-layer. Dan masa yang berjalan dari mana-mana operasi ini tidak bergantung kepada bilangan unsur-unsur yang ada dalam struktur data atau yang akhirnya akan berada dalam struktur data, tetapi pada panjang apa yang secara khusus? 

Rentetan menjadi dimasukkan, yang tidak membuat ini asimtotik berterusan O besar time-- satu. Dan terus terang, kalau- dunia sebenar, ini ertinya memasukkan nama Daven ini mengambil seperti lima langkah, atau Davenport sembilan langkah-langkah, atau David lima langkah. Itu cukup darn masa kecil berjalan. Dan, memang, itu yang sangat perkara yang baik, terutama ketika ia tidak bergantung kepada jumlah beberapa elemen di sana. Jadi bagaimana kita boleh melaksanakan ini jenis struktur dalam kod? Ini lebih sedikit kompleks, tetapi masih ia hanya permohonan dari blok binaan asas. Saya akan mentakrifkan semula nod kami seperti berikut: bool disebut word-- dan ini boleh dipanggil apa-apa. Tetapi bool mewakili apa yang saya menarik sebagai tanda semak. Ya. Ini adalah akhir dari rentetan dalam struktur data ini. 

Dan, sudah tentu, bintang nod terdapat adalah merujuk kepada kanak-kanak. Dan, memang, hanya suka pohon keluarga, anda akan mempertimbangkan nod yang menggantung dari bahagian bawah ibu bapa beberapa elemen untuk menjadi kanak-kanak. Karena itu, anak akan menjadi array 27, yang ke-27 hanya menjadi untuk tanda kutip. Kami akan menyusun kes khas itu. Jadi, anda boleh mempunyai beberapa nama dengan apostrof. Mungkin bahkan sempang harus masuk ke sana, tetapi anda akan lihat dalam p set 5 kita hanya penjagaan tentang huruf dan tanda baca. 

Kemudian bagaimana anda mewakili struktur data itu sendiri? Bagaimana anda mewakili akar dari indone ini, boleh dikatakan? Yah, hanya suka dengan senarai yang disambungkan, anda memerlukan pointer ke elemen pertama. Dengan indone a, anda perlu satu pointer ke akar indone ini. Dan dari sana anda boleh hash cara anda ke bawah yang lebih mendalam dan lebih mendalam kepada setiap nod yang lain dalam struktur. Jadi hanya dengan dapat ini kami mewakili struct. 

Sekarang Meanwhile-- Oh, soalan. 

PENONTON: Apa kata bool? 

DAVID MALAN: Kata Bool adalah hanya penjelmaan C ini dari apa yang saya jelaskan di ruang ini di sini, ketika Saya mula membelah setiap satu daripada unsur dan ini menjadi dua bagian. Satu adalah pointer ke nod seterusnya. Yang lain harus menjadi sesuatu seperti kotak semak untuk mengatakan ya, ada Daven perkataan yang berakhir di sini, kerana kita tidak mahu, pada masa ini, Dave. 

Walaupun Dave akan menjadi kata yang sah, ia tidak dalam trie lagi. Dan D bukan perkataan. Dan D-A bukan perkataan atau nama. Jadi tanda cek menunjukkan hanya sekali anda memukul nod ini adalah jalur sebelumnya aksara sebenarnya rentetan yang anda telah dimasukkan. Jadi itu sahaja bool ada lakukan untuk kita. 

Sebarang pertanyaan lain di cuba? Yeah. 

PENONTON: Apa yang tumpang tindih? Bagaimana jika anda mempunyai Dave dan Daven? DAVID MALAN: Perfect. Bagaimana jika anda mempunyai Dave dan Daven? Jadi, jika kita memasukkan, berkata nama panggilan, untuk David-- Dave-- D-A-V-E? Ini sebenarnya adalah super mudah. Oleh itu, kita hanya akan mengambil empat langkah. D-A-V-E. Dan apa yang saya perlu lakukan setelah saya menekan bahwa nod keempat? Hanya pergi untuk memeriksa. Kita sudah baik untuk pergi. Selesai. Empat langkah. Pemalar masa asimtotik. Dan sekarang kita telah menunjukkan bahawa kedua-dua Dave dan Daven adalah wayang dalam struktur. Jadi tidak menjadi masalah. Dan perhatikan bagaimana kehadiran dari Daven tidak berjaya mengambil masa lebih kurang masa untuk Dave dan sebaliknya. 

Jadi apa lagi yang boleh kita lakukan? Kami telah menggunakan metafora ini sebelum dulang yang mewakili sesuatu. Tetapi ternyata bahawa tumpukan dulang sebenarnya demonstratif yang lain data abstrak type-- struktur data tahap yang lebih tinggi bahawa pada akhir hari itu hanya seperti array atau senarai berpaut atau sesuatu yang lebih biasa. Tetapi ia lebih menarik konsep konsep. Tumpukan, seperti ini baki di sini di Mather, umumnya disebut hanya bahawa- tumpukan. 

Dan dalam jenis struktur data anda mempunyai dua operations-- anda mempunyai satu yang disebut dorongan untuk menambahkan sesuatu ke tepi, seperti meletakkan dulang lain belakang pada bahagian atas tindanan. Dan kemudian pop, yang bermakna anda mengambil baki off paling atas. Tetapi apa yang penting tentang tumpukan ialah itu punya ciri-ciri ingin tahu ini. Sebagai staf dewan makan adalah menyusun semula baki untuk makan seterusnya, apa yang akan menjadi benar tentang bagaimana pelajar berinteraksi dengan struktur data ini? PENONTON: Mereka akan muncul satu-satunya. DAVID MALAN: Mereka akan pop hanya satu-satunya, mudah-mudahan atas. Jika tidak, ia hanya semacam bodoh untuk pergi sepanjang jalan ke bawah. Betul? Struktur data tidak benar-benar membolehkan Anda untuk mengambil baki bahagian bawah sekurang-kurangnya dengan mudah. Jadi ada ini ingin tahu harta kepada tumpukan bahawa perkara yang terakhir dalam adalah akan menjadi pertama keluar itu. Dan ahli-ahli sains komputer memanggil ini LIFO-- bertahan, keluar pertama. Dan ia benar-benar tidak mempunyai aplikasi menarik. Ia tidak semestinya jelas seperti beberapa orang lain, tetapi ia boleh, memang, bermanfaat, dan ia boleh, memang, dilaksanakan dalam beberapa cara yang berbeza. 

Jadi satu, dan benar-benar, biarlah saya untuk tidak menyelam ke dalam. Mari kita buat ini sebagai gantinya. Mari kita lihat satu yang hampir Idea yang sama, tetapi ia lebih adil sedikit. Betul? Jika anda salah seorang dari anak-anak peminat atau kanak-kanak perempuan yang benar-benar suka produk Apple dan anda bangun pada 3:00 AM untuk beratur di beberapa kedai untuk mendapatkan iPhone yang terkini, anda mungkin beratur seperti ini. 

Sekarang giliran sangat sengaja dinamakan. Ini garis kerana ada beberapa keadilan kepadanya. Betul? Ia jenis akan disedut jika anda mempunyai sampai di sana pertama di Kedai Apple tetapi anda secara efektif paling bawah yang dulang kerana pekerja Apple kemudian pop orang yang terakhir benar-benar mendapat dalam talian. Jadi tumpukan dan beratur, walaupun fungsi mereka agak same-- yang ia hanya koleksi ini sumber yang akan tumbuh dan shrink-- ada yang aspek keadilan ini kepadanya, sekurang-kurangnya dalam dunia sebenar, di mana operasi anda bersenam pada dasarnya berbeza. A stack-- antrian rather-- dikatakan mempunyai dua operasi: n barisan dan d barisan. Atau anda boleh menghubungi mereka mana-mana beberapa perkara. Tetapi anda hanya ingin menangkap tanggapan bahawa seseorang itu menambah dan seseorang itu akhirnya menolak. 

Sekarang di bawah hood, kedua-dua tindanan dan barisan yang boleh dilaksanakan bagaimana? Kami tidak akan masuk ke dalam kod ia kerana tahap yang lebih tinggi idea adalah semacam lebih jelas. Maksud saya, apa yang manusia lakukan? Jika saya seorang yang pertama di Apple Simpan dan ini adalah pintu depan, Anda tahu, saya akan berdiri di sini. Dan orang yang depan akan berdiri di sini. Dan orang yang depan akan berdiri di sini. Jadi apa struktur data cocok untuk beratur? 

PENONTON: Sebuah antrian. DAVID MALAN: Baik, antrian. Tentu. Apa lagi? 

PENONTON: Senarai berkaitan. 

DAVID MALAN: A dikaitkan daftar anda boleh melaksanakan. Dan senarai berpaut adalah bagus kerana selepas itu ia boleh membesar secara sewenang-wenangnya panjang yang bertentangan untuk mempunyai beberapa jumlah tetap orang di kedai. Tetapi mungkin beberapa tetap tempat-tempat yang sah. Kerana jika mereka hanya mempunyai seperti 20 iPhone pada hari pertama, mungkin mereka hanya perlu pelbagai saiz 20 sebagai menggambarkan yang antrian, yang hanya untuk mengatakan sekarang setelah kami mula bercakap mengenai masalah yang lebih tinggi, anda boleh melaksanakannya dalam mana-mana cara. Dan ada mungkin hanya akan menjadi trade off dalam ruang dan waktu atau hanya dalam kerumitan kod anda sendiri. 

Bagaimana stack? Nah, tumpukan, kita telah melihat terlalu hanya boleh menjadi dulang ini. Dan anda boleh melaksanakan ini array. Tetapi pada satu masa nanti jika anda menggunakan array, apa yang akan berlaku kepada baki anda cuba untuk meletakkan? Baik. Anda hanya akan dapat pergi begitu tinggi. Dan saya fikir dalam Mather mereka sebenarnya tersembunyi dalam pembukaan itu. Jadi sesungguhnya, hampir seperti Mather menggunakan pelbagai saiz tetap, kerana anda hanya boleh memasang sedemikian banyak dulang di yang dibuka pada dinding di bawah lutut rakyat. Dan sebagainya yang mungkin dikatakan array, tetapi kita boleh melaksanakan yang lebih umum dengan senarai berpaut. 

Nah, bagaimana struktur data yang lain? Izinkan saya menarik yang lain dengar sini. Sesuatu seperti bagaimana kira-kira satu ini di sini? Mengapa hal ini mungkin berguna untuk tidak mempunyai sesuatu yang mewah sebagai indone, yang kami melihat memiliki nod ini sangat luas, yang masing-masing dalam array? Tapi bagaimana kalau kita melakukan sesuatu yang lebih sederhana, seperti pohon keluarga sekolah lama, setiap yang node di sini hanya menyimpan nombor. Sebagai ganti nama atau keturunan yang hanya menyimpan beberapa seperti ini. 

Nah, jargon yang kita gunakan dalam struktur data adalah kedua-dua negara- dan pokok-pokok, di mana trie, sekali lagi, adalah hanya satu yang node array, masih apa yang anda mungkin gunakan dari sekolah dasar apabila anda membuat keluarga yang daun tree-- dan punca kuasa pohon dan kanak-kanak daripada ibu bapa dan adik-beradik itu. Dan kita mungkin melaksanakan pokok, misalnya, sebagai hanya kerana ini. Pokok A, jika sebagai nod, salah satu ini kalangan yang mempunyai nombor, ia tidak akan mempunyai satu penunjuk, tetapi dua. Dan sebaik sahaja anda menambah pointer kedua, anda sebenarnya kini boleh membuat semacam data dua dimensi struktur dalam ingatan. Sama seperti a-dua dimensi array, anda boleh mempunyai jenis dua dimensi daftar terkait tetapi yang yang mengikuti corak yang di mana tidak ada kitaran. Ini benar-benar pohon dengan satu cara nenek di sini dan kemudian beberapa orang tua dan kanak-kanak dan cucu dan cicit. dan sebagainya. 

Tetapi apa yang benar-benar rapi tentang ini juga, hanya untuk menggoda anda dengan sedikit kod, recall rekursi daripada beberapa waktu yang lalu, di mana Anda menulis fungsi yang memanggil dirinya sendiri. Ini adalah kesempatan yang indah untuk melaksanakan sesuatu seperti rekursi, kerana menganggap ini. 

Ini adalah pokok. Dan Aku sudah menjadi dubur kecil dengan cara Aku meletakkan bilangan bulat ke jalan. Sehingga ia mempunyai khas name-- pokok carian binari. Sekarang kita telah mendengar dari binari mencari, tetapi anda boleh bekerja ke belakang dari nama ini perkara ini? Bagaimana pola tentang bagaimana saya dimasukkan integer ke dalam pokok ini? Ia bukan sewenang-wenang. Ada beberapa corak. Yeah. 

PENONTON: orang-orang yang lebih kecil di sebelah kiri. 

DAVID MALAN: Ya. Orang-orang yang lebih kecil di sebelah kiri. Yang lebih besar adalah di sebelah kanan. Sehingga pernyataan yang benar adalah orang tua adalah lebih besar daripada anak kiri, tetapi kurang daripada kanak-kanak yang benar. Dan itu saja bahkan ada definisi lisan rekursif kerana anda boleh memohon supaya logik yang sama untuk setiap nod dan hanya bahagian bawah keluar, kasus dasar jika anda akan, ketika anda menekan salah satu daun, boleh dikatakan, jika kebenaran yang tidak mempunyai anak-anak lagi. 

Sekarang bagaimana anda boleh mendapatkan nombor 44? Anda akan bermula pada akar dan berkata, hm. 55 bukan 44 Jadi saya mahu pergi hak atau yang ingin saya ke kiri? Nah, jelas anda mahu pergi kiri. Dan sebagainya itu hanya seperti telefon buku contoh dalam pencarian binari secara lebih umum. Tapi kami melaksanakannya sekarang sedikit lebih dinamik daripada array mungkin mengizinkan. Dan sebenarnya, jika anda ingin melihat kode tersebut, pada pandangan pertama pasti. Ia kelihatan seperti sejumlah besar garis. Tapi itu indah sederhana. Jika anda ingin untuk melaksanakan fungsi disebut carian yang tujuannya dalam kehidupan adalah untuk mencari nilai yang seperti n, integer, dan anda berlalu dalam pointer-- satu pointer ke nod akar, sebaliknya, pokok yang yang Anda boleh mengakses segala sesuatu yang lain, perhatikan bagaimana lugas anda boleh melaksanakan logik. Jika pokok adalah tidak sah, Jelas sekali ia tidak ada di sana. Mari kita kembali palsu. Betul? Jika anda serahkan apa-apa, ada apa-apa di sana. 

Yang lain, jika n adalah kurang daripada pokok panah n-- sekarang arrow n, ingat kami memperkenalkan super secara ringkas pada hari yang lain, dan itu hanya berarti de-rujukan penunjuk dan melihat bidang yang disebut n. Jadi ia bermakna pergi ke sana dan melihat bidang yang disebut n. Jadi, jika n, nilai yang anda diberikan, adalah kurang daripada nilai integer di pokok itu, di mana anda mahu pergi? Ke kiri. 

Jadi melihat rekursi. Saya returning-- tidak benar. Tidak palsu. Aku kembali apa sahaja jawapan adalah dari panggilan kepada diri saya sendiri, lulus n lagi, yang berlebihan, tetapi apa yang sedikit berbeza ini? Bagaimana saya membuat masalah yang lebih kecil? Saya lulus sebagai yang kedua hujah, bukan akar pokok itu, tetapi kanak-kanak di sebelah kiri dalam kes ini. Jadi, saya lulus dalam kanak-kanak di sebelah kiri. 

Sementara itu, jika n lebih besar daripada nod saya sedang melihat, Saya mencari sebelah kanan. Yang lain, jika pokok itu tidak batal, dan jika elemen bukan ke kiri dan ia bukan ke kanan, apa yang hebat berlaku? Kami telah benar-benar menemukan nod di pertanyaan, dan dengan itu kita kembali benar. 

Oleh itu, kita baru sahaja tercalar permukaan sekarang beberapa struktur data. Dalam masalah meletakkan lima anda akan meneroka ini belum lagi, dan anda akan diberikan reka bentuk anda pilihan bagaimana untuk pergi tentang ini. Apa yang saya ingin membuat kesimpulan mengenai hanya 30 teaser kedua dari apa yang menanti minggu depan dan seterusnya. 

Seperti yang kita begin-- bersyukur kerana anda mungkin think-- transisi kita perlahan-lahan dari dunia C dan lebih rendah rincian pelaksanaan peringkat, untuk sebuah dunia di mana kita boleh mengambil untuk diberikan bahawa orang lain mempunyai akhirnya dilaksanakan data ini struktur bagi kita, dan kami akan mula memahami dunia nyata berarti melaksanakan program berasaskan web dan laman web yang lebih umum dan juga keselamatan sangat implikasi yang kita baru mula menggores permukaan. Berikut adalah apa yang menanti kita pada hari-hari yang akan datang. 

[VIDEO MAIN SEMULA] 

-Dia Datang dengan mesej, dengan protokol yang semua sendiri. Dia datang ke dunia yang kejam firewall, router tidak peduli, dan bahaya yang jauh lebih buruk daripada kematian. Dia cepat. Dia kuat. Dia TCP / IP, dan dia punya alamat anda. "Laskar yang bersih." [AKHIR VIDEO MAIN SEMULA] DAVID MALAN: Bakal minggu depan. Kami akan melihat anda kemudian. [VIDEO MAIN SEMULA] -Dan Sekarang, "Pemikiran Deep" oleh Daven Farnham. -David Selalu dimulai kuliah dengan, "Baiklah." Mengapa tidak, "Inilah penyelesaian untuk set masalah "minggu ini atau "Kami memberikan anda semua A?" [TERTAWA] [AKHIR VIDEO MAIN SEMULA]