SPEAKER 1: Baiklah, jadi ini adalah CS50 ini adalah akhir minggu lima. Dan ingat bahwa terakhir kali kita mulai melihat data pengujian struktur yang mulai memecahkan masalah, yang mulai memperkenalkan masalah baru, tapi kunci untuk ini adalah semacam threading yang kita mulai melakukan dari node ke node. Jadi ini tentu saja adalah daftar sendiri-sendiri terkait. Dan oleh tunggal terkait, Maksud saya hanya ada satu benang antara masing-masing node. Ternyata keluar yang dapat Anda lakukan pengujian hal-hal seperti daftar ganda terkait dimana Anda memiliki panah akan di kedua arah, yang dapat membantu dengan efisiensi tertentu. Tapi ini memecahkan masalah? Apa masalah itu ini memecahkan? Mengapa kita peduli pada hari Senin? Mengapa, dalam teori, yang kita peduli pada hari Senin? Apa fungsinya? 

AUDIENCE: Kami secara dinamis dapat mengubah ukurannya. 

SPEAKER 1: OK, jadi kita bisa dinamis mengubah ukurannya. Dilakukan dengan baik Anda berdua. Jadi Anda secara dinamis dapat mengubah ukuran ini struktur data, sedangkan array, ingat, Anda harus tahu priori berapa banyak ruang yang Anda inginkan dan jika Anda membutuhkan sedikit lebih ruang, Anda jenis kurang beruntung. Anda harus membuat array baru. Anda harus memindahkan semua Anda data dari satu ke yang lain, akhirnya membebaskan array tua jika Anda bisa, dan kemudian lanjutkan. Yang hanya merasa sangat mahal dan sangat tidak efisien, dan memang bisa. Tapi ini tidak semua baik. Kami membayar harga, apa yang salah dari harga lebih jelas kami membayar dengan menggunakan linked list? 

AUDIENCE: Kita harus menggunakan ruang ganda untuk masing-masing. SPEAKER 1: Ya, jadi kita perlu setidaknya dua kali lebih banyak ruang. Bahkan, saya menyadari gambar ini bahkan sedikit menyesatkan, karena pada CS50 IDE di banyak modern komputer, pointer atau alamat tidak sebenarnya empat byte. Ini sangat sering ini hari delapan byte, yang berarti bagian bawah yang paling persegi panjang ada dalam realitas adalah jenis dua kali besar seperti apa yang saya ditarik, yang berarti Anda menggunakan tiga kali banyak ruang seperti yang kita sebaliknya. Sekarang pada saat yang sama, kami masih berbicara byte, kan? Kami tidak harus berbicara megabyte atau gigabyte, kecuali struktur data mendapatkan besar. 

Dan jadi hari ini kita mulai untuk mempertimbangkan bagaimana kita bisa mengeksplorasi data lebih efisien jika di Bahkan data akan lebih besar. Tapi mari kita coba canonicalize operasi pertama yang dapat Anda lakukan pada ini jenis struktur data. Jadi sesuatu seperti terkait daftar umumnya mendukung operasi seperti menghapus, masukkan, dan mencari. Dan apa yang saya maksud dengan itu? Itu hanya berarti bahwa biasanya, jika orang yang menggunakan linked list, mereka atau orang lain telah menerapkan fungsi seperti menghapus, menyisipkan, dan pencarian, sehingga Anda dapat benar-benar melakukan sesuatu berguna dengan struktur data. Jadi mari kita lihat bagaimana kita bisa menerapkan beberapa kode untuk sebuah linked list sebagai berikut. 

Jadi ini hanya beberapa kode C, bahkan bukan program lengkap bahwa saya benar-benar cepat melecut. Ini tidak online dalam distribusi kode, karena tidak akan benar-benar menjalankan. Tapi melihat aku baru saja dengan komentar mengatakan, dot dot dot, ada sesuatu ada, dot dot dot, sesuatu di sana. Dan mari kita lihat saja apa bagian juicy. Jadi pada baris ketiga, ingat bahwa ini adalah sekarang kami mengusulkan mendeklarasikan node terakhir waktu, salah satu dari mereka objek persegi panjang. Ini memiliki int yang akan kita sebut N, tapi kita bisa menyebutnya apa-apa, dan kemudian bintang struct simpul disebut berikutnya. Dan hanya harus jelas, bahwa kedua line, on line enam, apa itu? Apa itu lakukan bagi kita? Karena pasti terlihat lebih samar dari variabel kami biasa. 

AUDIENCE: Itu membuat pindah satu. 

SPEAKER 1: Itu membuat pindah satu. Dan untuk lebih tepatnya, itu akan menyimpan alamat dari node yang dimaksudkan untuk menjadi semantis sebelahnya, kan? Sehingga tidak akan tentu memindahkan apapun. Ini hanya akan menyimpan nilai, yang akan menjadi alamat dari beberapa simpul lainnya, dan itulah sebabnya kami telah mengatakan struct Bintang node, bintang yang menunjukkan pointer atau alamat. OK, jadi sekarang jika Anda menganggap bahwa kita memiliki N ini tersedia bagi kita, dan mari kita berasumsi bahwa orang lain memiliki dimasukkan sejumlah besar bilangan bulat menjadi linked list. Dan yang linked list adalah ditunjukkan oleh beberapa titik variabel yang disebut daftar yang disahkan pada di sini sebagai parameter, bagaimana aku pergi tentang garis 14 melaksanakan pencarian? Dengan kata lain, jika saya menerapkan Fungsi yang tujuan dalam hidup adalah mengambil int dan kemudian mulai dari linked list, yang merupakan pointer ke linked list. Seperti pertama, yang saya pikir David adalah relawan kami pada Senin, ia menunjuk Seluruh terkait daftar, itu seolah-olah kita sedang melewati David sebagai argumen kami di sini. Bagaimana kita pergi tentang melintasi daftar ini? Nah, ternyata bahwa meskipun pointer relatif baru sekarang untuk kami, kita bisa melakukan ini relatif tedeng aling-aling. 

Aku akan pergi ke depan dan mendeklarasikan variabel sementara yang dengan konvensi hanya akan disebut pointer, atau PTR, tapi Anda bisa menyebutnya apa pun yang Anda inginkan. Dan aku akan menginisialisasi untuk awal daftar. Sehingga Anda dapat jenis menganggap ini seperti saya guru hari lain, jenis menunjuk seseorang antara manusia kami sebagai relawan. Jadi aku variabel sementara itu hanya menunjuk pada hal yang sama bahwa kami kebetulan bernama relawan David juga menunjukkan. Sekarang sementara pointer tidak nol, karena ingat nol yang beberapa nilai sentinel khusus demarcates akhir daftar, jadi sementara saya tidak menunjuk pada tanah seperti relawan terakhir kami adalah, mari kita pergi ke depan dan melakukan hal berikut. Jika pointer-- dan sekarang aku agak ingin untuk melakukan apa yang kita lakukan dengan siswa structure-- jika pointer dot berikutnya equals-- bukan, jika pointer dot N sama sama dengan variabel N, Argumen yang telah disahkan pada, maka saya ingin pergi ke depan dan mengatakan kembali benar. Saya telah menemukan jumlah N dalam salah satu simpul dari linked list saya. Tapi titik tidak lagi bekerja dalam konteks ini, karena pointer, PTR, adalah memang pointer, alamat, kita benar-benar bisa mengagumkan menggunakan akhirnya sepotong sintaks jenis merek intuisi dan benar-benar menggunakan panah di sini, yang berarti pergi dari alamat ke integer ada di. Jadi itu sangat mirip dalam semangat untuk operator dot, tetapi karena pointer tidak pointer dan bukan struct itu sendiri, kita hanya menggunakan panah. 

Jadi jika node saat bahwa Aku, variabel sementara, saya menunjuk tidak N, apa yang ingin saya lakukan? Nah, dengan relawan manusia saya yang kita miliki di sini hari yang lain, jika manusia pertama saya adalah tidak yang saya inginkan, dan mungkin manusia kedua tidak yang saya inginkan, dan yang ketiga, saya perlu menjaga fisik bergerak. Seperti bagaimana aku melangkah melalui daftar? Ketika kita memiliki sebuah array, Anda hanya melakukan seperti saya plus plus. Tapi dalam kasus ini, itu sudah cukup untuk melakukan pointer, mendapat, pointer, berikutnya. Dengan kata lain, kolom berikutnya seperti semua tangan kiri bahwa relawan kami pada Senin yang menggunakan untuk menunjuk pada beberapa simpul lainnya. Mereka adalah tetangga mereka berikutnya. 

Jadi jika saya ingin melangkah melalui daftar ini, Aku tidak bisa hanya melakukan saya plus plus lagi, Saya bukannya harus mengatakan Aku, pointer, akan untuk sama apa pun bidang berikutnya adalah, bidang berikutnya, kolom berikutnya adalah, berikut semua orang tangan kiri yang kita miliki di panggung menunjuk untuk beberapa nilai berikutnya. Dan jika saya melewati bahwa seluruh iterasi, dan akhirnya, aku memukul nol tidak memiliki ditemukan N belum, aku hanya kembali palsu. Jadi sekali lagi, semua yang kita lakukan di sini, sesuai gambar saat yang lalu, mulai dengan menunjuk pada mulai dari daftar mungkin. Dan kemudian saya cek, adalah nilai Saya mencari sama dengan sembilan? Jika demikian, saya kembali benar dan aku sudah selesai. Jika tidak, saya update tanganku, AKA pointer, untuk menunjuk di lokasi panah depan, dan maka lokasi panah depan, dan berikutnya. Aku hanya berjalan melalui array ini. 

Jadi sekali lagi, siapa yang peduli? Seperti apa ini bahan untuk? Nah, ingat bahwa kami memperkenalkan gagasan stack, yang adalah data abstrak ketik sejauh itu bukan hal C, itu bukan hal yang CS50, itu ide yang abstrak, ide ini susun hal-hal di atas satu sama lain yang dapat diterapkan di tandan cara yang berbeda. Dan salah satu cara kita diusulkan adalah dengan array, atau dengan linked list. Dan ternyata kanonis, sebuah tumpukan mendukung setidaknya dua operasi. Dan kata-kata buzz push, untuk mendorong sesuatu ke stack, seperti nampan baru di ruang makan, atau pop, yang berarti untuk menghapus paling atas baki dari tumpukan di makan aula, dan kemudian mungkin beberapa operasi lain juga. Jadi bagaimana mungkin kita mendefinisikan struktur bahwa kita sekarang sedang menelepon stack? 

Nah, kita memiliki semua yang diperlukan dalam sintaks yang kita miliki di C. saya katakan, memberikan definisi jenis struct dalam stack, Aku akan katakan adalah array, dari Seluruh sekelompok angka dan kemudian ukuran. Jadi dengan kata lain, jika saya ingin untuk menerapkan ini dalam kode, biarkan aku pergi dan hanya jenis menggambar apa ini mengatakan. Jadi ini mengatakan, beri saya Struktur yang punya array, dan saya tidak tahu apa kapasitas, itu tampaknya beberapa konstan bahwa saya telah didefinisikan di tempat lain, dan itu baik-baik saja. Tapi rasa itu hanya satu, dua, tiga, empat, lima. Jadi kapasitas 5. Unsur ini dalam saya struktur akan disebut nomor. Dan kemudian saya perlu satu variabel lain rupanya disebut ukuran yang awalnya aku akan menetapkan diinisialisasi ke nol. Jika tidak ada di stack, ukuran adalah nol, dan itu nilai-nilai sampah dalam jumlah. Aku tidak tahu apa yang ada di sana hanya belum. 

Jadi jika saya ingin mendorong sesuatu ke stack, kira saya sebut mendorong fungsi, dan Saya katakan mendorong 50, seperti nomor 50, di mana akan Anda usulkan Aku menarik dalam array ini? Ada lima kemungkinan jawaban yang berbeda. Di mana Anda ingin mendorong jumlah 50? Jika tujuan di sini, sekali lagi, sebut fungsi push, lulus dalam argumen 50, di mana saya menaruhnya? Lima possible-- 20% kemungkinan menebak dengan benar. Iya nih? 

AUDIENCE: Jauh tepat. 

SPEAKER 1: Jauh tepat. Sekarang ada kesempatan 25% menebak dengan benar. Jadi yang benar-benar akan baik-baik. Dengan konvensi, saya akan mengatakan dengan sebuah array, kita umumnya akan mulai di sebelah kiri, tapi kita bisa pasti mulai dari kanan. Jadi spoiler di sini akan saya mungkin akan menggambar di sebelah kiri, sama seperti di array normal di mana Saya mulai dari kiri ke kanan. Tapi jika Anda dapat flip aritmatika, baik. Hanya saja tidak konvensional. OK, saya harus membuat satu lebih banyak perubahan meskipun. Sekarang aku sudah mendorong sesuatu ke stack, apa berikutnya? 

Baiklah, saya harus kenaikan ukuran. Jadi biarkan aku pergi ke depan dan hanya memperbarui ini, yang nol. Dan bukannya sekarang, aku akan untuk dimasukkan ke dalam nilai satu. Dan sekarang kira saya mendorong lain nomor ke stack, seperti 51. Yah, aku harus membuat satu lagi perubahan, yang hingga ukuran dua. Dan kemudian kira saya mendorong satu lagi nomor ke dalam stack seperti 61, sekarang saya harus memperbarui ukuran yang lebih waktu, dan mendapatkan nilai 3 sebagai ukuran. Dan sekarang kira saya sebut pop. Sekarang pop, dengan konvensi, tidak mengambil argumen. Dengan tumpukan, keseluruhan titik metafora tray adalah bahwa Anda tidak memiliki kebijaksanaan pergi mendapatkan nampan itu, semua dapat Anda lakukan adalah pop yang paling atas dari stack, hanya karena. Itulah yang ini struktur data tidak. 

Jadi dengan logika bahwa jika saya mengatakan pop, apa yang datang dari? Jadi 61. Jadi apa yang sebenarnya adalah komputer akan dilakukan di memori? Apa memiliki kode saya lakukan? Apa yang akan Anda usulkan kita mengubah di layar? Apa yang harus berubah? Maaf? Jadi kita menyingkirkan 61. Jadi saya pasti bisa melakukan itu. Dan saya dapat menyingkirkan 61. Dan kemudian apa yang lainnya perubahan harus terjadi? Ukuran mungkin harus kembali ke dua. Dan jadi itu baik-baik saja. Tapi tunggu dulu, ukuran beberapa saat yang lalu adalah tiga. Mari kita hanya melakukan sebuah pemeriksaan cepat. Bagaimana kita tahu bahwa kita diinginkannya untuk menyingkirkan 61? Karena kita muncul. Dan jadi saya memiliki ukuran properti kedua ini. 

Tunggu sebentar, aku berpikir kembali ke minggu kedua ketika kita mulai berbicara tentang array, di mana ini adalah lokasi nol, ini adalah lokasi satu, ini adalah lokasi dua, ini adalah lokasi tiga, empat, sepertinya hubungan antara ukuran dan elemen yang saya ingin menghapus dari array tampaknya hanya menjadi apa? Ukuran minus satu. Dan itulah bagaimana sebagai manusia kita tahu 61 datang pertama. Bagaimana komputer akan tahu? Ketika kode Anda, di mana Anda mungkin ingin melakukan ukuran minus satu, jadi tiga minus satu adalah dua, dan yang berarti kita ingin menyingkirkan 61. Dan kemudian kita memang bisa memperbarui ukuran sehingga ukuran yang sekarang pergi dari tiga sampai hanya dua. Dan hanya untuk menjadi bertele-tele, aku akan mengusulkan bahwa aku sudah selesai, kan? Anda diusulkan intuitif benar aku harus menyingkirkan 61. Tapi belum saya jenis semacam menyingkirkan 61? Saya lupa efektif bahwa itu benar-benar ada. Dan berpikir kembali ke PSET4, jika Anda sudah membaca artikel tentang forensik, PDF bahwa kita harus kalian baca, atau Anda akan membaca minggu ini untuk PSET4. Ingat bahwa ini sebenarnya erat dengan seluruh ide dari komputer forensik. Apa komputer umumnya dilakukan adalah itu hanya lupa di mana sesuatu adalah, tetapi tidak masuk dan seperti mencoba untuk menggaruknya keluar atau menimpa mereka bit dengan nol dan satu atau pola acak lainnya kecuali Anda sendiri melakukannya dengan sengaja. Jadi intuisi Anda adalah Baiklah, mari kita menyingkirkan 61. Namun dalam kenyataannya, kita tidak perlu repot-repot. Kita hanya perlu lupa bahwa itu ada dengan mengubah ukuran kami. 

Sekarang ada masalah dengan tumpukan ini. Jika saya terus mendorong hal-hal ke stack, apa jelas akan terjadi hanya dalam waktu beberapa saat? Kita akan kehabisan ruang. Dan apa yang kita lakukan? Kami jenis kacau. Implementasi ini tidak membiarkan kita mengubah ukuran array, karena menggunakan sintaks ini, jika Anda berpikir kembali ke minggu kedua, setelah Anda dinyatakan ukuran array, kami belum melihat mekanisme belum mana Anda dapat mengubah ukuran array. Dan memang C tidak memiliki fitur itu. Jika Anda mengatakan memberi saya lima Nths, menyebut mereka nomor, itu semua Anda akan mendapatkannya. Jadi kita lakukan sekarang pada hari Senin, memiliki kemampuan untuk mengekspresikan solusi meskipun, kita hanya perlu tweak definisi tumpukan kami untuk tidak menjadi beberapa array yang keras-kode, tapi hanya untuk menyimpan alamat. 

Sekarang mengapa ini? Sekarang kita hanya harus nyaman dengan fakta bahwa ketika program saya berjalan, Saya mungkin akan harus meminta manusia, berapa banyak nomor yang Anda ingin menyimpan? Jadi input harus datang dari suatu tempat. Tapi setelah saya tahu bahwa nomor, maka saya hanya bisa menggunakan apa fungsi untuk memberikan saya sepotong memori? Saya bisa menggunakan malloc. Dan saya dapat mengatakan sejumlah bytes Saya ingin kembali untuk nths ini. Dan semua saya harus menyimpan dalam jumlah variabel di sini dalam struct ini harus apa? Apa yang sebenarnya masuk ke dalam angka dalam skenario ini? Ya, pointer ke pertama byte yang sepotong memori, atau lebih khusus, alamat dari yang pertama dari mereka byte. Tidak masalah jika itu salah satu byte atau satu miliar byte, Aku hanya perlu peduli tentang pertama. Karena apa jaminan malloc dan saya jaminan sistem operasi, adalah bahwa sepotong memori saya mendapatkan, itu akan menjadi bersebelahan. Ada tidak akan menjadi celah. Jadi jika saya sudah meminta 50 byte atau 1000 byte, mereka semua akan menjadi kembali ke belakang ke belakang. Dan selama saya ingat seberapa besar, seberapa banyak saya minta, semua saya perlu tahu adalah alamat yang pertama. 

Jadi sekarang kita memiliki kemampuan dalam kode. Meskipun, itu akan membawa kita lebih banyak waktu untuk menulis ini up, kita sekarang bisa mengalokasikan memori yang oleh hanya menyimpan alamat yang berbeda ada jika kita ingin lebih besar atau bahkan sepotong kecil dari memori. Jadi di sini untuk off perdagangan. Sekarang kita mendapatkan dinamisme. Kami masih memiliki contiguousness Aku mengklaim. Karena malloc akan memberi kita sepotong memori yang berdekatan. Tapi ini akan menjadi sakit di leher bagi kita, programmer, untuk benar-benar kode up. Hanya saja lebih banyak pekerjaan. Kita perlu kode mirip dengan apa yang saya membenturkan keluar beberapa saat yang lalu. Sangat bisa dilakukan, tetapi hal itu menambah kompleksitas. Dan waktu pengembang, programmer Waktu belum sumber lain bahwa kita mungkin perlu untuk menghabiskan beberapa waktu untuk mendapatkan fitur baru. Dan tentu saja ada antrian. Kami tidak akan masuk ke ini satu di banyak detail. Tapi itu sangat mirip dalam roh. Saya bisa menerapkan antrian, dan operasinya sesuai, enqueue atau dequeue, seperti menambah atau menghapus, itu hanya cara pengujian mengatakan itu, enqueue atau dequeue, sebagai berikut. Saya hanya bisa memberi diriku struct itu lagi memiliki berbagai nomor ini, itu lagi memiliki ukuran, tapi mengapa saya sekarang perlu untuk melacak depan antrian? Saya tidak perlu tahu depan tumpukan saya. Nah, jika saya lagi untuk queue-- mari kita sulit kode itu sebagai memiliki seperti lima bilangan bulat di sini berpotensi. Jadi ini adalah nol, satu, dua, tiga, empat. Ini akan menjadi disebut nomor lagi. Dan ini akan disebut ukuran. 

Mengapa tidak cukup untuk memiliki hanya ukuran? Nah, mari kita mendorong angka-angka yang sama pada. Jadi saya pushed-- saya enqueued, atau didorong. Sekarang saya akan enqueue 50, dan kemudian 51, dan kemudian 61, dan dot dot dot. Jadi itu enqueue. Aku enqueued 50, kemudian 51, kemudian 61. Dan yang terlihat identik untuk stack sejauh ini, kecuali saya perlu membuat satu perubahan. Saya perlu memperbarui ukuran ini, jadi saya pergi dari nol ke satu dua sampai tiga sekarang. Bagaimana cara dequeue? Apa yang terjadi dengan dequeue? Siapa yang harus datang dari daftar ini pertama jika garis di Apple Store? Jadi 50. Jadi itu semacam rumit saat ini. Sedangkan terakhir kali itu super mudah untuk hanya melakukan ukuran minus satu, Aku sampai ke akhir array saya secara efektif di mana jumlahnya, ia bisa menghilangkan 61. Tapi aku tidak ingin menghapus 61. Saya ingin mengambil 50, yang ada di sana pada 05:00 untuk berbaris untuk iPhone baru atau yang lainnya. Dan untuk menyingkirkan 50, saya tidak bisa melakukan ini, kan? Saya bisa mencoret 50. Tapi kami hanya berkata kita tidak harus begitu anal untuk mencakar atau menyembunyikan data. Kami hanya dapat lupa di mana itu. 

Tapi jika saya mengubah ukuran saya sekarang untuk dua, adalah informasi yang memadai ini untuk mengetahui apa yang terjadi di dalam antrian saya? Tidak juga. Seperti ukuran saya adalah dua, tapi mana antrian mulai, terutama jika saya masih memiliki angka-angka yang sama di memori. 50, 51, 61. Jadi saya perlu mengingat sekarang di mana bagian depan. Dan sehingga saya mengusulkan up ada, kita akan baru saja disebut N depan, yang awal nilai seharusnya apa? Nol, hanya awal daftar. Tapi sekarang selain decrementing ukuran, kami hanya selisih depan. Sekarang inilah masalah lain. Jadi sekali aku terus. Kira ini adalah jumlah seperti 121, 124, dan kemudian, sialan, Aku keluar dari ruang. Tapi tunggu dulu, aku tidak. Jadi pada titik ini dalam cerita, misalkan ukuran adalah salah satu, dua, tiga, empat, sehingga menganggap bahwa ukuran empat, depan adalah salah satu, jadi 51 adalah di depan. Saya ingin menempatkan nomor lain di sini, tapi, sialan, aku keluar dari ruang. Tapi aku tidak benar-benar, benar? Dimana saya bisa menaruh beberapa nilai tambah, seperti 171? Ya, aku bisa hanya jenis kembali ke sana, kan? Dan kemudian mencoret 50, atau hanya menimpa dengan 171. Dan jika Anda bertanya-tanya mengapa nomor kami punya begitu acak, ini umumnya diambil komputer kursus ilmu di Harvard setelah CS50. Tapi itu optimasi yang baik, karena sekarang aku tidak membuang-buang ruang. Saya masih harus ingat seberapa besar hal ini total. Ini total lima. Karena saya tidak ingin mulai Timpa 51. Jadi sekarang saya masih di luar ruang, sehingga masalah yang sama seperti sebelumnya. Tapi Anda bisa melihat bagaimana sekarang dalam kode Anda, Anda mungkin harus menulis sedikit lebih kompleksitas untuk membuat itu terjadi. Dan pada kenyataannya, operator apa di C mungkin memungkinkan Anda ajaib melakukan ini bundar itu? Ya operator Modulo, tanda persen. Jadi apa jenis dingin tentang antrian, meskipun kami terus menggambar array karena ini garis lurus seperti, jika Anda jenis berpikir tentang hal ini sebagai melengkung sekitar sebagai lingkaran, kemudian hanya intuitif itu jenis bekerja mental Saya berpikir sedikit lebih bersih. Anda masih akan harus melaksanakan bahwa model mental dalam kode. Jadi tidak sulit, akhirnya, untuk melaksanakan, tapi kami masih kehilangan size-- lebih tepatnya, kemampuan untuk mengubah ukuran, kecuali kita melakukan ini. 

Kita harus menyingkirkan array, kita menggantinya dengan pointer tunggal, dan kemudian di suatu tempat di kode saya, saya punya panggilan apa fungsi untuk benar-benar membuat array nomor disebut? Malloc, atau sejenis fungsi, persis. Pertanyaan tumpukan atau antrian. Ya? Pertanyaan bagus. Apa modulo yang akan Anda gunakan di sini. Jadi secara umum, bila menggunakan mod, Anda akan melakukannya dengan ukuran seluruh struktur data. Jadi sesuatu seperti lima atau kapasitas, jika itu konstan, mungkin terlibat. Tapi hanya melakukan modulo lima mungkin tidak cukup, karena kita perlu tahu kita membungkus sini atau di sini atau di sini. Jadi Anda mungkin juga akan ingin melibatkan ukuran hal, atau variabel depan juga. Jadi itu hanya ini relatif ekspresi aritmatika sederhana, tapi Modulo akan menjadi bahan utama. 

Film begitu singkat jika Anda mau. Animasi bahwa beberapa Orang-orang di universitas lain mengumpulkan bahwa kita sudah diadaptasi untuk diskusi ini. Ini melibatkan Jack belajar fakta tentang antrian dan statistik. 

FILM: Sekali waktu, ada seorang pria bernama Jack. Ketika datang untuk membuat teman-teman, Jack tidak memiliki bakat. Jadi Jack pergi untuk berbicara dengan paling pria yang populer dia tahu. Ia pergi ke Lou dan bertanya, Apa yang harus saya lakukan? Lou melihat bahwa temannya benar-benar tertekan. Nah, dia mulai, hanya melihat bagaimana Anda berpakaian. Apakah Anda tidak memiliki pakaian apapun dengan tampilan yang berbeda? Ya, kata Jack. Saya yakin tidak. Datang ke rumah saya dan Aku akan menunjukkan kepada Anda. Jadi mereka pergi ke Jack. Dan Jack menunjukkan Lou kotak di mana ia menyimpan semua kemeja nya, dan celananya, dan kaus kaki. Lou mengatakan, saya melihat Anda memiliki semua pakaian Anda dalam tumpukan. Mengapa Anda tidak memakai beberapa lain sesekali? 

Jack mengatakan, baik, ketika saya menghapus pakaian dan kaus kaki, Aku mencuci mereka dan menempatkan mereka pergi di dalam kotak. Kemudian datang berikutnya pagi, dan sampai aku hop. Aku pergi ke kotak dan mendapatkan pakaian saya dari atas. Lou cepat menyadari masalah dengan Jack. Dia terus pakaian, CD, dan buku dalam tumpukan. Ketika ia meraih sesuatu untuk dibaca atau memakai, ia akan memilih buku atas atau pakaian. Kemudian ketika ia selesai, ia akan meletakkannya segera kembali. Kembali itu akan pergi, di atas tumpukan. Saya tahu solusinya, kata seorang kemenangan keras. Anda perlu belajar untuk mulai menggunakan antrian. Lou mengambil pakaian Jack dan menggantung mereka di dalam lemari. Dan ketika ia telah mengosongkan kotak, ia hanya melemparkan itu. 

Lalu dia berkata, sekarang Jack, pada akhir hari, meletakkan pakaian Anda di sebelah kiri ketika Anda menempatkan mereka pergi. Maka besok pagi ketika Anda melihat sinar matahari, mendapatkan pakaian Anda di sebelah kanan, dari akhir baris. Apakah Anda tidak melihat? kata Lou. Itu akan sangat bagus. Anda akan memakai segala sesuatu sekali sebelum Anda memakai sesuatu dua kali. Dan dengan segala sesuatu dalam antrian di lemari dan rak-nya, Jack mulai merasa cukup yakin pada dirinya sendiri. Semua berkat Lou dan antrian indah nya. SPEAKER 1: Baiklah, itu menggemaskan. Jadi apa yang telah benar-benar akan di bawah kap sekarang? Bahwa kita memiliki pointer, bahwa kita memiliki malloc, bahwa kita memiliki kemampuan untuk membuat potongan memori untuk diri kita sendiri dinamis. Jadi ini adalah kita gambar sekilas hanya beberapa hari. Kami tidak benar-benar tinggal di atasnya, tapi gambar ini memiliki telah terjadi di bawah kap untuk minggu sekarang. Dan jadi ini merupakan, hanya persegi panjang yang kita sudah ditarik, memori komputer Anda. Dan mungkin komputer Anda, atau CS50 ID, memiliki gigabyte memori atau RAM atau dua gigabyte atau empat. Itu tidak terlalu penting. Sistem operasi Anda Windows atau Mac OS atau Linux, dasarnya memungkinkan program Anda berpikir bahwa ia memiliki akses untuk keseluruhan memori komputer Anda, meskipun Anda mungkin akan berjalan beberapa program sekaligus. Jadi dalam kenyataannya, yang tidak benar-benar bekerja. Tapi itu semacam ilusi diberikan ke semua program Anda. Jadi, jika Anda memiliki dua gigs RAM, ini adalah bagaimana komputer mungkin berpikir itu. 

Sekarang kebetulan, salah satu dari ini hal, salah satu segmen memori, disebut stack. Dan memang setiap saat sejauh dalam menulis kode bahwa Anda telah disebut fungsi, misalnya utama. Ingat bahwa setiap kali saya sudah memori ditarik komputer, Saya selalu menarik semacam setengah dari persegi panjang di sini dan tidak repot-repot berbicara tentang apa yang di atas. Karena ketika utama disebut, saya mengklaim bahwa Anda mendapatkan sepotong ini memori yang turun di sini. Dan jika utama yang disebut fungsi seperti swap, juga pertukaran goes here. Dan ternyata, itu mana itu berakhir. Pada sesuatu yang disebut stack dalam memori komputer Anda. Sekarang di akhir hari, ini hanya membahas. Ini seperti byte nol, byte satu, byte 2 miliar. Tapi jika Anda berpikir tentang hal itu sebagai objek persegi panjang ini, semua yang kita lakukan setiap saat kita memanggil fungsi adalah layering sepotong baru memori. Kami memberikan fungsi yang sepotong memori sendiri untuk bekerja dengan. 

Dan ingat sekarang bahwa ini penting. Karena jika kita memiliki sesuatu seperti pertukaran dan dua variabel lokal seperti A dan B dan kita mengubah nilai-nilai dari satu dan dua dua dan satu, ingat bahwa ketika Swap kembali, itu seolah-olah ini sepotong memori hanya pergi. Pada kenyataannya, itu masih ada forensik. Dan ada sesuatu yang masih benar-benar ada. Tetapi secara konseptual, itu seperti meskipun itu benar-benar hilang. Dan utama tidak tahu pekerjaan yang dilakukan dalam fungsi swap, kecuali itu benar-benar disahkan pada mereka argumen dengan pointer atau referensi. Sekarang, solusi mendasar itu masalah dengan Swap lewat hal-hal di berdasarkan alamat. Tapi ternyata, juga, apa telah terjadi di atas bagian yang dari persegi panjang selama ini adalah Belum ada lebih banyak memori di sana. Dan ketika Anda secara dinamis mengalokasikan memori, apakah itu dalam GetString, yang kami sudah melakukan untuk Anda di CS50 perpustakaan, atau jika kalian memanggil malloc dan meminta sistem operasi untuk sepotong memori, itu tidak datang dari stack. Itu berasal dari tempat lain dalam memori komputer Anda yang disebut tumpukan. Dan itu tidak berbeda. Ini adalah RAM yang sama. Ini adalah memori yang sama. Itu hanya RAM itu terserah ada bukannya di sini. 

Dan apa artinya? Nah, jika komputer Anda memiliki jumlah terbatas memori dan stack yang tumbuh, sehingga untuk berbicara, dan heap, menurut panah ini, tumbuh ke bawah. Dengan kata lain, setiap kali Anda memanggil malloc, Anda diberi sepotong memori dari atas, maka mungkin sedikit lebih rendah, kemudian sedikit lebih rendah, setiap kali Anda memanggil malloc, heap, itu penggunaan, adalah jenis tumbuh, tumbuh lebih dekat dan lebih dekat dengan apa? Tumpukan. Jadi apakah ini tampak seperti ide yang baik? Maksudku, di mana itu tidak benar-benar jelas apa lagi yang bisa Anda lakukan jika Anda hanya memiliki jumlah terbatas memori. Tapi ini pasti buruk. Kedua anak panah adalah pada kecelakaan saja untuk satu sama lain. 

Dan ternyata orang jahat, orang-orang yang sangat baik dengan pemrograman, dan mencoba untuk hack ke komputer, dapat memanfaatkan kenyataan ini. Bahkan, mari kita pertimbangkan potongan kecil. Jadi ini adalah contoh Anda dapat membaca sekitar secara lebih rinci di Wikipedia. Kami akan mengarahkan Anda pada artikel jika penasaran. Tapi ada serangan umum dikenal sebagai buffer overflow yang telah ada selama manusia telah memiliki kemampuan untuk memanipulasi memori komputer, terutama dalam C. Jadi ini adalah program yang sangat sewenang-wenang, tapi mari kita membacanya dari bawah ke atas. Utama ke bintang argc arang argv. Jadi itu program yang mengambil argumen baris perintah. Dan semua utama yang tampaknya adalah panggilan fungsi, menyebutnya F untuk kesederhanaan. Dan melewati apa? Argv satu. Sehingga masuk ke dalam F apapun kata adalah bahwa pengguna mengetik pada prompt setelah Nama program sama sekali. Begitu banyak seperti Caesar atau Vigenere, yang Anda mungkin ingat lakukan dengan argv. 

Jadi apa yang F? F mengambil dalam sebuah string sebagai argumen sendiri, AKA bintang char, yang sama hal, sebagai string. Dan itu disebut sewenang-wenang bar dalam contoh ini. Dan kemudian arang c 12, hanya dalam istilah awam, apa Char c braket 12 melakukan bagi kita? Apa yang ia lakukan? Mengalokasikan memori, khususnya 12 byte untuk 12 karakter. Tepat. Dan kemudian baris terakhir, aduk dan copy, Anda mungkin tidak melihat. Ini adalah salinan string yang Fungsi yang tujuan dalam hidup adalah untuk menyalin argumen kedua dalam argumen pertama, tapi hanya sampai sejumlah byte. Jadi argumen ketiga mengatakan, berapa banyak byte yang harus Anda menyalin? Panjang bar, apapun pengguna mengetik. Dan isi bar, string yang, yang disalin ke dalam memori menunjuk pada C. 

Jadi ini tampaknya agak bodoh, dan itu. Ini adalah contoh buat, tapi itu perwakilan dari kelas vektor serangan, cara menyerang sebuah program. Semua baik-baik saja dan baik jika pengguna jenis dalam sebuah kata yang 11 karakter atau lebih sedikit, ditambah backslash nol. Bagaimana jika jenis pengguna di lebih dari 11 atau 12 atau 20 atau 50 karakter? Apa program ini lakukan? Kesalahan berpotensi seg. Ini akan untuk membuta menyalin segala sesuatu di bar sampai panjangnya, yang harfiah semuanya di bar, ke alamat menunjuk C. Tapi C hanya Terlebih Dahulu diberikan sebagai 12 byte. Tapi tidak ada pemeriksaan tambahan. Tidak ada jika kondisi. Tidak ada pengecekan sini kesalahan. 

Dan jadi apa program ini adalah akan lakukan adalah hanya membabi buta menyalin satu hal ke yang lain. Dan jadi jika kita menggambar ini sebagai gambar, inilah hanya sepotong ruang memori. Jadi perhatikan di bagian bawah, kita memiliki bar variabel lokal. Sehingga pointer itu akan store-- bukan bahwa argumen lokal yang akan menyimpan string bar. Dan kemudian melihat hanya di atasnya dalam tumpukan, karena setiap kali Anda meminta untuk memori di stack, ia pergi sedikit di atas itu pictorially, pemberitahuan bahwa kita punya 12 bytes ada. Yang kiri atas adalah C braket nol dan yang kanan bawah adalah C braket 11. Itu hanya bagaimana komputer akan berbaring keluar. Jadi hanya intuitif, jika bar memiliki lebih dari 12 karakter secara total, termasuk backslash nol, di mana adalah 12 atau braket C 12 akan pergi? Atau lebih tepatnya di mana-12 karakter atau karakter-13, karakter keseratus akan berakhir dalam gambar? Atas atau di bawah? 

Benar, karena meskipun tumpukan itu sendiri tumbuh ke atas, setelah Anda meletakkan barang-barang di itu, untuk alasan desain, menempatkan memori dari atas ke bawah. Jadi jika Anda punya lebih dari 12 byte, Anda akan mulai menimpa bar. Nah, itu bug, tapi itu tidak benar-benar masalah besar. Tapi itu adalah masalah besar, karena ada lebih banyak barang yang terjadi di memori. Jadi, inilah bagaimana kita mungkin menempatkan halo, harus jelas. Jika saya mengetik di halo pada prompt. H-E-L-L-O backslash nol, berakhir dalam mereka 12 byte, dan kami super aman. Semua baik-baik saja. Tetapi jika saya ketik sesuatu lagi, berpotensi itu akan menyusup ke ruang bar. Tapi lebih buruk lagi, ternyata sepanjang waktu ini, meskipun kami tidak pernah berbicara tentang itu, tumpukan digunakan untuk hal-hal lain. Ini bukan hanya variabel lokal. 

C adalah bahasa tingkat yang sangat rendah. Dan itu semacam diam-diam menggunakan stack juga ingat ketika fungsi disebut, apa alamat adalah dari fungsi sebelumnya, sehingga dapat melompat kembali ke fungsi itu. Jadi ketika panggilan utama menukar antara hal didorong ke stack tidak hanya swap variabel lokal, atau argumen, juga diam-diam mendorong ke stack yang diwakili dengan potongan merah di sini, adalah alamat utama secara fisik dalam memori komputer Anda, sehingga ketika swap dilakukan, komputer tahu saya harus kembali ke utama dan menyelesaikan melaksanakan fungsi utama. Jadi ini berbahaya sekarang, karena jika jenis pengguna di sumur lebih dari halo, sehingga input pengguna clobbers atau menimpa yang bagian merah, logis jika komputer hanya akan membabi buta menganggap bahwa byte dalam irisan merah alamat yang harus kembali, bagaimana jika musuh cukup pintar atau cukup beruntung untuk menempatkan urutan byte ada yang terlihat seperti alamat, tapi itu alamat kode bahwa dia ingin komputer untuk mengeksekusi bukan main? 

Dengan kata lain, jika apa yang pengguna mengetik di prompt, bukan hanya sesuatu seperti tidak berbahaya halo, tapi itu sebenarnya kode yang sama untuk menghapus semua file pengguna ini? Atau email kata sandi mereka kepada saya? Atau mulai penebangan mereka keystrokes, kan? Ada cara, mari kita menetapkan hari ini, bahwa mereka bisa mengetikkan bukan hanya halo dunia atau nama mereka, mereka pada dasarnya bisa lulus dalam kode, nol dan orang, bahwa komputer kesalahan untuk kedua kode dan alamat. Jadi meskipun agak abstrak, jika jenis pengguna dalam kode cukup permusuhan bahwa kita akan menggeneralisasi di sini sebagai A. A adalah serangan atau musuh. Hal sehingga hanya buruk. Kami tidak peduli tentang nomor atau nol atau yang hari ini, sehingga Anda berakhir Timpa bahwa bagian merah, melihat bahwa urutan byte. O 835 C nol delapan nol. Dan sekarang sebagai artikel Wikipedia di sini telah mengusulkan, jika Anda benar-benar mulai sekarang label byte di komputer Anda memori, apa artikel Wikipedia adalah mengusulkan adalah bahwa, bagaimana jika alamat itu byte kiri atas adalah 80 C 0 3508. 

Dengan kata lain, jika orang jahat adalah cukup pintar dengan kode nya untuk benar-benar menempatkan nomor di sini bahwa sesuai dengan alamat kode ia disuntikkan ke dalam komputer, Anda dapat trik komputer dalam melakukan sesuatu. Menghapus file, email hal, mengendus lalu lintas, secara harfiah apa pun bisa disuntikkan ke dalam komputer. Dan jadi buffer overflow Serangan pada intinya hanya bodoh, bodoh utama dari sebuah array yang tidak memiliki batas-batasnya diperiksa. Dan ini adalah apa yang super berbahaya adalah dan secara bersamaan super kuat di C adalah bahwa kita memang memiliki akses ke mana saja di memori. Terserah kita, programmer, yang menulis kode asli untuk memeriksa panjang sialan dari setiap array yang kita memanipulasi. Jadi harus jelas, apa memperbaiki? Jika kita memutar kembali ke ini kode, saya seharusnya tidak hanya mengubah panjang bar, apa lagi yang harus saya memeriksa? Apa lagi yang harus saya lakukan untuk mencegah serangan ini seluruhnya? Saya tidak ingin hanya membabi buta mengatakan Anda menyalin banyak byte seperti panjang bar. Saya ingin mengatakan, copy sebagai banyak byte seperti di bar sampai dialokasikan memori, atau 12 secara maksimal. Jadi saya perlu beberapa jenis jika kondisi yang tidak memeriksa panjang bar, tetapi jika melebihi 12, kami hanya sulit kode 12 sebagai jarak maksimum yang mungkin. Jika tidak disebut penyangga Serangan meluap bisa terjadi. Di bagian bawah mereka slide, jika Anda penasaran untuk membaca lebih lanjut adalah artikel asli yang sebenarnya jika Anda ingin melihat. 

Tapi sekarang, di antara harga dibayar di sini adalah inefisiensi. Jadi itu cepat rendah tingkat melihat apa masalah bisa muncul sekarang kita bahwa memiliki akses ke memori komputer. Tapi masalah lain kita sudah tersandung pada Senin hanya inefisiensi dari linked list. Kami kembali ke waktu linier. Kami tidak lagi memiliki array berdekatan. Kami tidak memiliki akses acak. Kita tidak bisa menggunakan notasi braket persegi. Kami benar-benar harus menggunakan loop sementara seperti yang saya tulis beberapa saat yang lalu. Tapi pada hari Senin, kami menyatakan bahwa kita dapat merayap kembali ke ranah efisiensi mencapai sesuatu yang logaritmik mungkin, atau terbaik namun, bahkan mungkin sesuatu yang disebut konstanta waktu. Jadi bagaimana kita bisa melakukannya dengan menggunakan ini baru alat, alamat ini, pointer ini, dan threading hal kita sendiri? Nah, misalkan di sini, ini adalah a bunch angka yang ingin kita simpan dalam struktur data dan pencarian efisien. Kami benar-benar dapat mundur ke minggu dua, melempar ini ke dalam sebuah array, dan mencari mereka menggunakan pencarian biner. Membagi dan menaklukkan. Dan sebenarnya Anda menulis pencarian biner di PSET3, di mana Anda menerapkan program find. Tapi kau tahu apa. Ada jenis yang lebih cara cerdas untuk melakukan hal ini. Ini sedikit lebih canggih dan mungkin memungkinkan kita untuk melihat mengapa biner pencarian jauh lebih cepat. Pertama, mari kita memperkenalkan gagasan pohon. Yang meskipun di pohon realitas jenis tumbuh seperti ini, dalam dunia komputer ilmu mereka jenis tumbuh ke bawah seperti pohon keluarga, di mana Anda memiliki kakek atau kakek-nenek besar atau entah apa lagi di bagian atas, patriark dan ibu pemimpin keluarga, hanya satu disebut akar, node, di bawah yang anak-anaknya, bawah yang anak-anaknya, atau keturunan yang lebih umum. Dan siapa pun menggantung bagian bawah keluarga pohon, selain itu termuda dalam keluarga, bisa juga hanya menjadi generik disebut daun pohon. 

Jadi ini hanya a bunch kata-kata dan definisi untuk sesuatu yang disebut pohon di komputer ilmu, seperti pohon keluarga. Tapi ada inkarnasi pengujian pohon, salah satunya disebut pohon pencarian biner. Dan Anda bisa jenis menggoda selain apa hal ini tidak. Yah, itu biner dalam arti apa? Dari mana biner datang dari sini? Maaf? Ini tidak begitu banyak baik atau. Ini lebih bahwa setiap node memiliki lebih dari dua anak, seperti yang kita lihat di sini. Secara umum, tree-- dan orang tua dan kakek-nenek dapat memiliki banyak anak-anak atau cucu-cucu mereka benar-benar ingin, dan jadi misalnya ada kami memiliki tiga anak-anak dari simpul tangan kanan, tetapi dalam pohon biner, sebuah node memiliki nol, satu, atau dua anak maksimal. Dan itu adalah properti yang bagus, karena jika itu dibatasi oleh dua, kita akan dapat mendapatkan log basis sedikit dua tindakan yang terjadi di sini pada akhirnya. Jadi kita memiliki sesuatu logaritmik. Tapi lebih pada suatu saat. Pohon pencarian berarti bahwa angka-angka tersebut diatur sedemikian rupa sehingga anak kiri ini nilai lebih besar dari akar. Dan anak kanan adalah lebih besar dari akar. Dengan kata lain, jika Anda mengambil salah satu node, lingkaran dalam gambar ini, dan melihat kiri anak dan anak kanan, pertama harus kurang dari, kedua harus lebih besar dari. Jadi kewarasan memeriksa 55. Ini meninggalkan anak adalah 33. Ini kurang dari. 55, anak kanan adalah 77. Ini lebih besar dari. Dan itu definisi rekursif. Kita bisa memeriksa setiap salah satu dari mereka node dan pola yang sama akan terus. 

Jadi apa yang bagus di pohon pencarian biner, adalah satu itu, kita dapat menerapkannya dengan struct, hanya seperti ini. Dan meskipun kita membuang banyak struktur di Anda, mereka agak intuitif sekarang mudah-mudahan. Sintaks masih misterius pasti, tapi isi node dalam context-- dan kami tetap menggunakan node kata, apakah itu persegi panjang pada layar atau lingkaran, itu hanya beberapa wadah generik, dalam hal ini pohon, seperti yang kita melihat, kita perlu integer di setiap node dan kemudian saya perlu dua pointer menunjuk ke anak kiri dan anak kanan, masing-masing. Jadi itulah bagaimana kita mungkin menerapkan bahwa dalam struct. Dan bagaimana mungkin aku menerapkannya dalam kode? Nah, mari kita cepat lihat contoh kecil ini. Ini tidak fungsional, tapi aku disalin dan disisipkan struktur itu. Dan jika fungsi saya untuk biner pohon pencarian disebut pencarian, dan ini membutuhkan dua argumen, integer N dan pointer ke node, sehingga pointer ke pohon atau pointer ke akar pohon, bagaimana aku pergi tentang mencari N? Yah, pertama, karena aku berurusan dengan pointer, Aku akan melakukan pemeriksaan kewarasan. Jika sama dengan pohon sama dengan nol, adalah N di pohon ini atau tidak di pohon ini? Hal ini tidak bisa, kan? Jika saya melewati null, tidak ada di sana. Aku mungkin juga hanya membabi buta mengatakan kembali palsu. Jika Anda memberi saya apa-apa, saya pasti tidak bisa menemukan nomor N. Jadi apa lagi mungkin aku cek sekarang? Aku akan mengatakan baik lain jika N adalah kurang dari apa pun yang pada node pohon bahwa saya telah menyerahkan nilai N. Dengan kata lain, jika nomor saya mencari, N, kurang dari node bahwa saya sedang melihat. Dan node yang saya cari di disebut pohon, dan ingat dari contoh sebelumnya untuk mendapatkan nilai di pointer, Saya menggunakan notasi panah. Jadi jika N kurang dari pohon panah N, saya ingin konseptual pergi kiri. Bagaimana cara mengungkapkan searching meninggalkan? Untuk menjadi jelas, apakah ini gambar tersebut, dan saya sudah melewati yang paling atas panah yang menunjuk ke bawah. Itu pointer pohon saya. Aku menunjuk pada akar pohon. Dan aku mencari katakanlah, untuk jumlah 44, sewenang-wenang. Apakah 44 kurang dari atau lebih besar dari 55 jelas? Jadi itu kurang dari. Dan jadi ini jika kondisi berlaku. Jadi secara konseptual, apa yang ingin saya mencari berikutnya jika saya sedang mencari 44? Ya? 

Tepat, saya ingin mencari anak kiri, atau meninggalkan sub-pohon gambar ini. Dan pada kenyataannya, biarkan aku melalui gambar di sini untuk sesaat, karena Saya tidak bisa menggaruk ini. Jika saya mulai di sini di 55, dan Saya tahu bahwa nilai 44 Saya mencari adalah untuk kiri, itu semacam seperti merobek buku telepon di setengah atau merobek pohon di setengah. Saya tidak lagi harus peduli Seluruh setengah ini pohon. Namun, anehnya dalam hal struktur, hal ini di sini bahwa dimulai dengan 33, yang itu sendiri adalah pohon pencarian biner. Aku mengatakan kata rekursif sebelumnya karena memang ini adalah struktur data yang menurut definisi adalah rekursif. Anda mungkin memiliki pohon yang ini besar, tapi setiap salah satu dari anak-anaknya merupakan pohon hanya sedikit lebih kecil. Bukannya itu menjadi kakek atau nenek, sekarang itu hanya ibu or-- Saya tidak bisa say-- tidak ibu atau ayah, yang akan menjadi aneh. Sebaliknya dua anak-anak ada akan seperti kakak dan saudara. Sebuah generasi baru dari pohon keluarga. Tapi secara struktural, itu ide yang sama. Dan ternyata saya memiliki fungsi dengan yang saya dapat mencari pencarian biner pohon. Hal ini disebut pencarian. Saya mencari N di pohon panah kiri lain jika N lebih besar dari nilai bahwa aku saat ini di. 55 dalam kisah beberapa saat yang lalu. Saya memiliki fungsi yang disebut pencari yang aku hanya bisa lulus N ini dan secara rekursif mencari sub-pohon dan hanya pulang apapun jawaban itu. Lain saya punya beberapa kasus dasar akhir di sini. 

Apa yang terjadi akhir? Pohon baik null. Nilai saya baik cari adalah kurang dari itu atau lebih besar dari itu atau sama dengan itu. Dan saya bisa mengatakan yang sama sama, tapi secara logis itu setara dengan hanya mengatakan yang lain di sini. Jadi yang benar adalah bagaimana saya menemukan sesuatu. Jadi mudah-mudahan ini adalah bahkan contoh yang lebih menarik dari fungsi sigma bodoh kami melakukan beberapa kuliah kembali, di mana itu hanya sebagai mudah untuk menggunakan loop untuk menghitung semua angka dari satu N. Berikut dengan struktur data itu sendiri adalah rekursif didefinisikan secara rekursif dan ditarik, sekarang kita memiliki kemampuan untuk mengekspresikan diri dalam kode itu sendiri adalah rekursif. Jadi ini adalah tepat kode yang sama di sini. 

Jadi apa masalah lain yang bisa kita memecahkan? Jadi langkah cepat dari pohon untuk sesaat. Di sini adalah, mengatakan, bendera Jerman. Dan ada jelas pola bendera ini. Dan ada banyak bendera di dunia yang adalah sebagai sederhana seperti ini dalam hal warna dan pola mereka. Tapi anggaplah bahwa ini disimpan sebagai .GIF, Atau JPEG, atau bitmap, atau ping, format file grafis dengan yang Anda kenal, beberapa di antaranya kami bermain dengan di PSET4. Ini tampaknya tidak berharga untuk menyimpan pixel hitam, piksel hitam, pixel hitam, dot, dot, dot, sejumlah besar piksel hitam untuk scanline pertama, atau baris, kemudian sejumlah besar sama, maka seluruh kelompok itu yang sama, dan kemudian Seluruh sekelompok piksel merah, piksel merah, piksel merah, maka keseluruhan sekelompok piksel kuning, kuning, kan? 

Ada inefisiensi seperti di sini. Bagaimana Anda secara intuitif kompres bendera Jerman jika mengimplementasikannya sebagai file? Seperti informasi apa yang bisa kita tidak repot-repot menyimpan pada disk agar untuk mengurangi ukuran file kita dari seperti megabyte untuk kilobyte, sesuatu lebih kecil? Dimana terletak redundansi di sini harus jelas? Apa yang bisa Anda lakukan? Ya? Tepat. Mengapa tidak bukan ingat warna setiap pixel menisik seperti yang Anda lakukan di PSET4 dengan format file bitmap, kenapa tidak Anda hanya mewakili kolom paling kiri piksel, misalnya sekelompok piksel hitam, a bunch merah, dan sekelompok kuning, dan kemudian hanya entah bagaimana mengkodekan Ide ulangi ini 100 kali atau mengulang ini 1.000 kali? Di mana 100 atau 1000 adalah hanya sebuah integer, sehingga Anda bisa lolos dengan hanya satu nomor bukannya ratusan atau ribuan piksel tambahan. Dan memang, itulah bagaimana kami bisa memampatkan bendera Jerman. Dan Sekarang bagaimana dengan bendera Prancis? Dan sedikit semacam latihan mental, yang bendera dapat dikompresi lebih pada disk? Bendera Jerman atau Perancis bendera, jika kita mengambil pendekatan itu? Jerman bendera, karena ada lebih redundansi horizontal. Dan dengan desain, banyak berkas grafis format memang bekerja sebagai garis pemindaian horizontal. Mereka bisa bekerja vertikal, hanya manusia tahun lalu memutuskan bahwa kami akan umumnya memikirkan hal-hal baris demi baris bukan kolom dengan kolom. Jadi memang jika Anda untuk melihat file ukuran bendera Jerman dan Perancis bendera, asalkan resolusi sama, lebar yang sama dan tinggi, yang satu ini di sini akan menjadi lebih besar, karena Anda harus mengulang sendiri tiga kali. Anda harus menentukan biru, ulangi sendiri, putih, ulangi diri, merah, ulangi diri. Anda tidak bisa hanya pergi semua cara ke kanan. Dan sebagai samping, untuk membuat jelas kompresi di mana-mana, jika ini empat frame dari video-- kamu mungkin ingat bahwa film atau video umumnya seperti 29 atau 30 frame per detik. Ini seperti sebuah buku flip kecil di mana Anda hanya melihat gambar, gambar, foto, gambar, gambar hanya super cepat sehingga terlihat seperti aktor di layar bergerak. Berikut adalah lebah di atas seikat bunga. Dan meskipun mungkin jenis sulit untuk melihat pada pandangan pertama, satu-satunya hal yang bergerak di film ini adalah lebah. 

Apa yang bodoh tentang menyimpan Video terkompresi? Ini semacam limbah untuk menyimpan video yang empat gambar hampir identik yang hanya berbeda sejauh mana lebah adalah. Anda dapat membuang sebagian informasi yang dan ingat saja, misalnya, frame pertama dan frame terakhir, frame kunci jika Anda sudah pernah mendengar kata, dan hanya menyimpan di tengah di mana lebah tersebut. Dan Anda tidak perlu menyimpan semua merah muda, dan biru, dan nilai-nilai hijau juga. Jadi ini hanya mengatakan bahwa kompresi di mana-mana. Ini adalah teknik kita sering menggunakan atau mengambil untuk diberikan hari ini. 

Tapi bagaimana Anda kompres teks? Bagaimana Anda pergi tentang mengompresi teks? Nah, masing-masing karakter dalam Ascii adalah satu byte, atau delapan bit. Dan itu semacam bodoh, kan? Karena Anda mungkin tipe A dan E dan I dan O dan U banyak lebih sering daripada seperti W atau Q atau Z, tergantung pada bahasa yang Anda sedang menulis pasti. Dan jadi mengapa kita menggunakan delapan bit untuk setiap huruf, termasuk yang paling surat populer, kan? Mengapa tidak menggunakan bit yang lebih sedikit untuk huruf super populer, seperti E, hal-hal yang Anda menebak pertama di Wheel of Fortune, dan menggunakan lebih banyak bit untuk huruf kurang populer? Mengapa? Karena kita hanya akan menggunakannya lebih jarang. 

Nah, ternyata ada memiliki telah membuat upaya untuk melakukan hal ini. Dan jika Anda ingat dari kelas sekolah atau sekolah tinggi, kode Morse. Kode Morse memiliki titik dan garis yang dapat ditransmisikan sepanjang kawat sebagai suara atau sinyal dari beberapa macam. Tetapi kode Morse adalah super bersih. Ini semacam sistem biner di bahwa Anda memiliki titik-titik atau tanda hubung. Tetapi jika Anda melihat, misalnya, dua titik. Atau jika Anda berpikir kembali ke operator yang berjalan seperti bip, bip, bip, bip, memukul pemicu sedikit yang mengirimkan sinyal, jika Anda, penerima, menerima dua titik, apa pesan yang Anda terima? Benar-benar sewenang-wenang. 

Saya? Saya? Atau apa about-- atau aku? Mungkin itu hanya dua E kan? Jadi ada masalah ini dari decodability dengan Morse kode, dimana kecuali orang yang mengirim Anda pesan sebenarnya berhenti sehingga Anda dapat mengurutkan dari melihat atau mendengar kesenjangan antara huruf, itu tidak cukup hanya untuk mengirim sungai dari nol dan satu, atau titik dan garis, karena ada ambiguitas. E adalah satu titik, jadi jika Anda melihat dua titik atau mendengar dua titik, mungkin itu dua E atau mungkin itu salah satu I. Jadi kita perlu sistem yang merupakan sedikit lebih pintar dari itu. Jadi seorang pria bernama Huffman tahun lalu datang dengan persis ini. Jadi kita hanya akan untuk mengambil sekilas bagaimana pohon erat dengan ini. Misalkan ini adalah beberapa Pesan bodoh Anda ingin mengirim, terdiri dari hanya A, B, C D's dan E, tapi ada banyak redundansi di sini. Ini tidak dimaksudkan untuk menjadi bahasa Inggris. Itu tidak dienkripsi. Ini hanya pesan bodoh dengan banyak pengulangan. Jadi jika Anda benar-benar menghitung semua A, B, C, D, dan E, inilah frekuensi. 20% dari surat-surat yang A, 45% dari huruf adalah E, dan tiga frekuensi lainnya. Kami menghitung di sana secara manual dan hanya melakukan matematika. 

Jadi ternyata bahwa Huffman, beberapa waktu lalu, menyadari bahwa, Anda tahu apa, jika saya mulai membangun pohon, atau hutan pohon, jika Anda mau, sebagai berikut, saya dapat melakukan hal berikut. Aku akan memberikan node ke setiap dari surat-surat yang saya peduli dan aku akan menyimpan dalam simpul yang frekuensi sebagai floating point nilai, atau Anda bisa menggunakannya N, juga, tapi kita hanya akan menggunakan pelampung di sini. Dan algoritma yang ia mengusulkan adalah bahwa Anda mengambil hutan ini dari node tunggal pohon, pohon jadi super pendek, dan Anda mulai menghubungkan mereka dengan kelompok baru, orang tua baru, jika Anda mau. Dan Anda melakukan ini dengan memilih dua frekuensi terkecil pada suatu waktu. Jadi saya mengambil 10% dan 10%. Saya membuat node baru. Dan saya sebut node baru 20%. 

Yang dua node saya menggabungkan berikutnya? Ini sedikit ambigu. Jadi ada beberapa kasus sudut untuk mempertimbangkan, tetapi untuk menjaga hal-hal yang cukup, Aku akan memilih 20% - Sekarang saya mengabaikan anak-anak. Aku akan memilih 20% dan 15% dan menarik dua sisi yang baru. Dan sekarang yang dua node saya logis menggabungkan? Mengabaikan semua anak, semua cucu, hanya melihat akar sekarang. Yang dua node saya mengikat bersama? Titik dua dan 0,35. Jadi biarkan aku menggambar dua sisi baru. Dan kemudian aku hanya punya satu kiri. Jadi, inilah pohon. Dan itu sudah ditarik sengaja untuk melihat jenis cantik, tapi melihat bahwa tepi memiliki juga telah diberi label nol dan satu. Jadi semua tepi kiri adalah nol sewenang-wenang, tetapi secara konsisten. Semua tepi kanan adalah orang-orang. 

Dan jadi apa Hoffman diusulkan adalah, jika Anda ingin mewakili B, bukan merupakan jumlah 66 sebagai sebuah Ascii yang delapan seluruh bit, Anda tahu apa, hanya toko pola nol, nol, nol, nol, karena itulah jalan dari pohon saya, pohon Mr. Huffman, dengan daun dari akar. Jika Anda ingin menyimpan E, sebaliknya, tidak mengirim delapan bit yang mewakili suatu E. Sebaliknya, mengirim apa pola bit? Satu. Dan apa yang baik tentang ini bahwa E adalah huruf yang paling populer, dan Anda menggunakan kode terpendek untuk itu. Berikutnya yang paling populer Surat terlihat seperti itu adalah A. Dan begitu berapa banyak bit dia mengusulkan menggunakan untuk itu? Nol, satu. 

Dan karena itu diimplementasikan pohon ini, untuk saat ini biarkan aku menetapkan ada tidak ada ambiguitas seperti dalam Morse kode, karena semua surat Anda peduli adalah pada akhir tepi ini. Jadi itu hanya satu penerapan pohon. Ini is-- dan aku akan gelombang tanganku di bagaimana Anda mungkin menerapkan ini sebagai struktur C. Kita hanya perlu untuk menggabungkan simbol, seperti char, dan frekuensi di kiri dan kanan. Tapi mari kita lihat dua contoh terakhir yang Anda akan mendapatkan cukup akrab dengan setelah kuis nol dalam masalah mengatur lima. 

Jadi ada struktur data dikenal sebagai tabel hash. Dan tabel hash adalah jenis dingin dalam hal ini memiliki ember. Dan misalkan ada empat ember di sini, hanya empat ruang kosong. Berikut setumpuk kartu, dan di sini adalah klub, sekop, klub, berlian, klub, berlian, klub, berlian, clubs-- jadi ini adalah acak. Hati, hearts-- jadi aku bucketizing semua input di sini. Dan kebutuhan tabel hash untuk melihat masukan Anda, dan kemudian memasukkannya ke dalam tertentu menempatkan berdasarkan apa yang Anda lihat. Ini adalah algoritma. Dan saya menggunakan super algoritma visual yang sederhana. Bagian tersulit dari yang mengingat apa foto-foto itu. Dan kemudian ada jumlah empat hal. 

Sekarang tumpukan tumbuh, yang adalah desain hal yang disengaja di sini. Tapi apa lagi yang mungkin saya lakukan? Jadi sebenarnya di sini kita memiliki sekelompok buku ujian sekolah tua. Misalkan sekelompok nama siswa di sini. Berikut adalah tabel hash yang lebih besar. Bukan empat ember, Saya telah, katakanlah 26. Dan kami tidak ingin pergi meminjam 26 hal dari luar [? Annenberg?], Jadi inilah lima yang mewakili A sampai Z. Dan jika saya melihat seorang mahasiswa yang namanya dimulai dengan A, Aku akan menaruh atau kuis di sana. Jika seseorang mulai dengan C, di sana, A-- sebenarnya, tidak ingin melakukan itu. B berjalan di atas sini. Jadi saya punya A dan B dan C. Dan sekarang inilah Seorang siswa lain. Tetapi jika tabel hash ini diimplementasikan dengan array, Aku agak kacau pada titik ini, kan? Aku agak perlu menempatkan tempat ini. 

Jadi salah satu cara saya bisa memecahkan ini, semua benar, A sibuk, B sibuk, C sibuk. Aku akan menempatkan dia di D. Jadi pada pertama, saya memiliki akses cepat random untuk masing-masing ember untuk siswa. Tapi sekarang itu semacam didesentralisasikan menjadi sesuatu yang linear, karena jika saya ingin mencari seseorang Nama yang dimulai dengan A, saya cek di sini. Tapi jika ini bukan A student Saya mencari, Aku agak harus mulai memeriksa ember, karena apa yang saya lakukan adalah semacam linear menyelidiki struktur data. Sebuah cara yang bodoh untuk mengatakan hanya melihat untuk pembukaan tersedia pertama, dan menempatkan sebagai rencana B, sehingga untuk berbicara, atau rencana D dalam hal ini, nilai di lokasi itu sebagai gantinya. Ini hanyalah sehingga jika Anda sudah mendapat 26 lokasi dan tidak ada siswa dengan nama Q atau Z, atau sesuatu seperti itu, setidaknya Anda menggunakan ruang. 

Tapi kami sudah melihat lebih solusi pintar di sini, kan? Apa yang akan Anda lakukan sebagai gantinya jika Anda memiliki tabrakan? Jika dua orang memiliki nama A, apa yang akan telah cerdas atau lebih solusi intuitif dari sekedar menempatkan A di mana D seharusnya? Kenapa tidak aku hanya pergi luar [? Annenberg?], seperti malloc, node lain, meletakkannya di sini, dan kemudian menempatkan bahwa Seorang mahasiswa di sini. Sehingga saya pada dasarnya memiliki semacam array, atau mungkin lebih elegan seperti kita mulai melihat sebuah linked list. 

Dan tabel hash adalah struktur yang bisa terlihat seperti ini, tetapi lebih cerdik, Anda sesuatu yang disebut chaining terpisah, dimana tabel hash cukup sederhana adalah array, masing-masing yang unsur bukan angka, sendiri merupakan linked list. Sehingga Anda mendapatkan akses super cepat memutuskan mana untuk hash nilai untuk. Sama seperti dengan contoh kartu, Saya membuat keputusan super cepat. Hati goes here, berlian goes here. Sama di sini, A goes here, D goes here, B goes here. Jadi super cepat look-up, dan jika Anda kebetulan mengalami kasus tabrakan di mana Anda punya, dua orang dengan nama yang sama, baik maka Anda hanya mulai menghubungkan mereka bersama-sama. Dan mungkin Anda menjaga mereka diurutkan abjad, mungkin Anda tidak. Tapi setidaknya sekarang kita memiliki dinamika tersebut. Jadi di satu sisi kita memiliki super cepat waktu yang konstan, dan jenis waktu linear terlibat jika ini daftar terkait mulai mendapatkan sedikit lama. 

Jadi semacam ini konyol, lelucon tahun culun lalu. Pada CS50 hack-a-thon, ketika siswa check-in, beberapa TF atau CA setiap tahun berpikir itu lucu untuk memasang tanda seperti ini, di mana ia hanya berarti jika nama Anda dimulai dengan A, pergi dengan cara ini. Jika nama Anda dimulai dengan B, pergi this-- OK, itu lucu mungkin nanti di semester. Tapi ada yang lain cara untuk melakukan hal ini, juga. Kembali ke itu. 

Jadi ada struktur ini. Dan ini adalah terakhir kami struktur untuk hari ini, yang merupakan sesuatu yang disebut trie. T-R-I-E, yang untuk beberapa alasan pendek untuk pengambilan, tapi itu disebut trie. Jadi trie menarik lain campuran dari banyak ide-ide ini. Ini adalah pohon, yang telah kita lihat sebelumnya. Ini bukan pohon pencarian biner. Ini pohon dengan sejumlah anak-anak, tetapi masing-masing dari anak-anak di trie adalah array. Array ukuran, mengatakan, 26 atau mungkin 27 jika Anda ingin mendukung nama ditulis dgn tanda penghubung atau apostrof di nama orang. 

Dan jadi ini adalah struktur data. Dan jika Anda melihat dari atas ke bawah, seperti jika Anda melihat simpul atas sana, M, adalah menunjuk ke hal paling kiri di sana, yang kemudian A, X, W, E, L, L. Ini hanya struktur data yang sewenang-wenang adalah menyimpan nama orang. Dan Maxwell disimpan dengan hanya mengikuti jalur array ke array ke array. Tapi apa yang menakjubkan tentang trie adalah itu, sedangkan linked list dan bahkan array, yang terbaik yang pernah kita mendapatkan adalah waktu linear atau waktu logaritmik mencari seseorang. Dalam struktur data trie, jika struktur data saya memiliki satu nama di dalamnya dan saya sedang mencari Maxwell, aku akan menemukannya cukup cepat. Saya hanya mencari M-A-X-W-E-L-L. Jika struktur data, sebaliknya, jika N adalah satu juta, jika ada juta nama dalam struktur data, Maxwell masih akan menjadi ditemukan setelah hanya M-A-X W-E-L-L langkah. Dan langkah-langkah David-- D-A-V-I-D. Dengan kata lain, dengan membangun struktur data yang mendapat semua array ini, yang semuanya sendiri mendukung akses acak, Aku bisa mulai mencari orang nama menggunakan jumlah waktu yang sebanding dengan jumlah tidak hal dalam struktur data, seperti satu juta nama yang ada. Jumlah waktu yang dibutuhkan saya untuk menemukan M-A-X W-E-L-L dalam struktur data proporsional tidak dengan ukuran struktur data, tetapi dengan panjang nama. Dan realistis nama kita melihat ke atas tidak pernah akan menjadi gila panjang. Mungkin seseorang memiliki 10 karakter nama, 20 nama karakter. Ini tentu terbatas, kan? Ada manusia di bumi yang memiliki nama terpanjang mungkin, tapi nama itu adalah konstan panjang nilai, kan? Ini tidak berbeda di akal. Jadi dengan cara ini, kita sudah mencapai struktur data yang waktu konstan look-up. Ini tidak mengambil sejumlah langkah tergantung pada panjang input, tapi bukan jumlah nama dalam struktur data. Jadi jika kita melipatgandakan jumlah nama tahun depan dari satu miliar untuk dua miliar, Temuan Maxwell akan mengambil jumlah yang sama persis dari tujuh langkah untuk menemukannya. Dan kita tampaknya telah mencapai grail suci kami berjalan waktu. 

Jadi beberapa pengumuman cepat. Kuis nol akan datang. Lebih pada pada website ini saja selama beberapa hari. Senin lecture-- itu libur di sini di Harvard, Senin. Hal ini tidak di New Haven, jadi kita mengambil kelas ke New Haven untuk kuliah pada hari Senin. Semuanya akan difilmkan dan disiarkan secara langsung seperti biasa, tapi mari kita berakhir hari ini dengan klip 30 detik disebut "Deep Thoughts" oleh Daven Farnham, yang terinspirasi tahun lalu oleh Sabtu "Deep Thoughts" Night Live ini oleh Jack Berguna, yang sekarang harus masuk akal. 

FILM: Dan sekarang, "Jauh Pikiran "oleh Daven Farnham. Tabel hash. 

SPEAKER 1: Baiklah, itu saja untuk saat ini. Kita akan melihat Anda minggu depan. 

Doug: Untuk melihat dalam tindakan. Jadi mari kita lihat yang sekarang. Jadi di sini, kami memiliki sebuah array disortir. 

IAN: Doug, Anda dapat pergi ke depan dan me-restart ini hanya satu detik, silahkan. Baiklah, kamera bergulir, sehingga tindakan kapan pun Anda siap, Doug, OK? Doug: Baiklah, jadi apa yang kita miliki di sini adalah array disortir. Dan aku sudah berwarna semua elemen merah untuk menunjukkan bahwa itu adalah, pada kenyataannya, disortir. Jadi ingat bahwa hal pertama yang kita lakukan adalah kita mengurutkan setengah kiri dari array. Kemudian kita memilah kanan setengah dari array. Dan ya-da, ya-da, ya-da, kami menggabungkan mereka bersama-sama. Dan kami memiliki array sepenuhnya diurutkan. Jadi itulah cara menggabungkan semacam bekerja. 

IAN: Whoa, whoa, whoa, potong, potong, potong, potong. Doug, Anda tidak bisa hanya ya-da, ya-da, ya-da, jalan Anda melalui merge sort. 

Doug: Aku hanya melakukan. Tidak apa-apa. Kami baik untuk pergi. Mari kita terus bergulir. Jadi, 

IAN: Anda harus menjelaskan lebih lengkap dari itu. Itu tidak cukup. Doug: Ian, kita tidak harus kembali ke satu. Tidak apa-apa. Jadi, jika kita terus dengan merge-- Ian, kita berada di tengah-tengah syuting. 

IAN: Saya tahu. Dan kita tidak bisa hanya ya-da, ya-da, ya-da, melalui seluruh proses. Anda harus menjelaskan bagaimana kedua belah pihak bisa bergabung bersama-sama. 

Doug: Tapi kita sudah sudah menjelaskan bagaimana dua sides-- 

IAN: Anda baru saja ditampilkan mereka array merge. Doug: Mereka tahu proses. Mereka baik-baik saja. Kami sudah lebih dari sepuluh kali. 

IAN: Anda hanya melewatkan tepat di atasnya. Kita akan kembali ke satu, Anda Anda tidak bisa ya-da, ya-da di atasnya. Baiklah, kembali ke satu. 

Doug: Saya harus kembali melalui semua slide? Tuhanku. Ini seperti keenam kalinya, Ian. Tidak apa-apa. 

IAN: Baiklah. Anda siap? Besar. Aksi.