SPEAKER 1: Baiklah, jadi ini adalah CS50 Ini adalah akhir minggu lima. Dan ingat bahawa Kali terakhir kami mula melihat data pelamun struktur yang mula menyelesaikan masalah, yang mula memperkenalkan masalah baru, tetapi kunci kepada ini adalah jenis threading yang kita mula melakukan dari nod ke nod. Jadi ini sudah tentu adalah senarai secara tunggal berkaitan. Dan dengan secara tunggal berkaitan, Maksud saya ada satu benang antara setiap orang-orang nod. Ternyata anda boleh lakukan pelamun perkara seperti senarai duanya adalah terpakai dikaitkan di mana anda mempunyai anak panah pergi dalam kedua-dua arah, yang boleh membantu dengan kecekapan tertentu. Tetapi ini menyelesaikan masalah? Apa masalah adakah ini menyelesaikan? Mengapa kita mengambil berat pada hari Isnin? Mengapa, dalam teori, adakah kita mengambil berat pada hari Isnin? Apa yang ia buat? 

PENONTON: Kami dinamik boleh mengubah saiz. 

SPEAKER 1: OK, jadi kita boleh dinamik mengubah saiz. Syabas anda berdua. Jadi, anda boleh mengubah saiz dinamik ini struktur data, manakala pelbagai, ingat, anda perlu tahu priori berapa banyak ruang yang anda mahu dan jika anda memerlukan lebih sedikit ruang, anda jenis daripada nasib. Anda perlu membuat pelbagai baru. Anda perlu untuk menggerakkan semua anda data dari satu kepada yang lain, akhirnya membebaskan array lama jika anda boleh, dan kemudian meneruskan. Yang hanya berasa sangat mahal dan sangat tidak cekap, dan sememangnya ia boleh. Tetapi ini tidak semua yang baik. Kami membayar harga yang, apa yang salah daripada harga yang lebih jelas kita membayar dengan menggunakan senarai berpaut? 

PENONTON: Kita perlu menggunakan ruang dua kali bagi setiap satu. SPEAKER 1: Ya, jadi kita perlu sekurang-kurangnya dua kali lebih banyak ruang. Malah, saya menyedari ini gambar ini walaupun sedikit mengelirukan, kerana pada CS50 IDE dalam banyak moden komputer, penunjuk atau alamat tidak sebenarnya empat bait. Ia amat sering ini hari lapan bait, yang bermakna yang paling bawah segi empat tepat terdapat dalam realiti adalah jenis dua kali besar seperti apa yang saya telah disediakan, yang bermaksud anda menggunakan tiga kali ruang yang banyak seperti yang kita mungkin mempunyai sebaliknya. Pada waktu yang sama, kami masih bercakap bait, bukan? Kita tidak semestinya bercakap megabait atau gigabait, kecuali data ini struktur mendapatkan besar. 

Dan sehingga hari ini kita mula mempertimbangkan bagaimana kita boleh meneroka data dengan lebih cekap jika dalam Malah data semakin besar. Tetapi mari kita cuba untuk canonicalize operasi pertama yang boleh anda lakukan di Syarikat- jenis struktur data. Jadi sesuatu seperti dikaitkan senarai umumnya menyokong operasi suka memadam, memasukkan, dan mencari. Dan apa yang saya maksudkan dengan itu? Yang hanya bermakna bahawa biasanya, jika orang yang menggunakan senarai bersambung, mereka atau orang lain telah melaksanakan fungsi seperti padam, masukkan, dan carian, jadi anda boleh benar-benar melakukan sesuatu berguna dengan struktur data. Jadi mari kita lihat cepat bagaimana kita mungkin melaksanakan beberapa kod untuk senarai berpaut seperti berikut. 

Jadi ini adalah hanya beberapa kod C, tidak ada satu program yang lengkap bahawa saya benar-benar cepat disebat. Ia bukan dalam talian dalam pengedaran kod, kerana ia tidak akan benar-benar berjalan. Tetapi notis saya baru sahaja dengan komen berkata, dot dot dot, ada sesuatu sana, dot dot dot, sesuatu di sana. Dan mari kita hanya melihat apa bahagian-bahagian yang berair berada. Jadi pada baris tiga, ingat bahawa ini kini kita dicadangkan mengisytiharkan nod lalu masa, salah satu daripada orang-orang objek segi empat tepat. Ia mempunyai int yang kita akan memanggil N, tetapi kita boleh memanggilnya apa-apa, dan kemudian bintang struct nod dipanggil datang. Dan hanya untuk menjadi jelas, kedua yang line, pada baris enam, apakah itu? Apa yang ia lakukan untuk kita? Kerana ia pasti kelihatan lebih samar daripada pembolehubah biasa kami. 

PENONTON: Ia menjadikan ia bergerak lebih daripada satu. 

SPEAKER 1: Ia menjadikan ia bergerak lebih daripada satu. Dan untuk lebih tepat, ia akan menyimpan alamat nod yang bertujuan untuk menjadi semantik sebelahnya, bukan? Oleh itu, ia tidak akan semestinya bergerak apa-apa. Ia hanya akan menyimpan nilai, yang merupakan akan menjadi alamat beberapa nod yang lain, dan itulah sebabnya kita telah berkata struct nod bintang, bintang yang melambangkan penunjuk atau alamat. OK, jadi sekarang jika anda menganggap bahawa kita mempunyai N ini ada pada kita, dan mari kita menganggap bahawa orang lain mempunyai dimasukkan sejumlah besar bilangan bulat ke dalam senarai berpaut. Dan bahawa senarai berkaitan adalah ditunjukkan oleh satu ketika pembolehubah dipanggil senarai itu diluluskan di sini sebagai parameter, bagaimana saya boleh pergi mengenai talian 14 melaksanakan carian? Dalam erti kata lain, jika saya melaksanakan fungsi yang tujuan dalam hidup adalah untuk mengambil int dan kemudian permulaan senarai berpaut, iaitu penunjuk kepada senarai berkaitan. Seperti pertama, yang saya fikir David adalah sukarela kami pada hari Isnin, dia menghala ke arah senarai keseluruhan mengaitkan, ia seolah-olah kita lulus David dalam sebagai hujah kami di sini. Bagaimana kita pergi tentang menyeberangi senarai ini? Nah, ternyata bahawa walaupun petunjuk yang agak baru sekarang kepada kami, kita boleh melakukan ini agak terus terang. 

Saya akan pergi ke depan dan mengisytiharkan pembolehubah sementara yang oleh konvensyen hanya akan untuk dipanggil penunjuk, atau PTR, tetapi anda boleh memanggil ia apa sahaja yang anda mahu. Dan saya akan memulakan untuk permulaan senarai. Jadi, anda boleh jenis berfikir ini seperti saya guru hari yang lain, jenis menunjuk pada seseorang di kalangan manusia kami sebagai sukarelawan. Jadi saya pembolehubah sementara itu hanya menunjuk pada perkara yang sama yang kami secara kebetulan bernama sukarelawan Daud juga menunjuk keluar. Sekarang sementara penunjuk adalah tidak batal, kerana ingat null iaitu beberapa nilai sentinel khas yang demarcates akhir senarai, jadi sementara saya tidak menunjuk pada tanah seperti sukarelawan terakhir kami adalah, mari kita pergi ke depan dan melakukan yang berikut. Jika pointer-- dan sekarang saya jenis mahu untuk melakukan apa yang kita lakukan dengan pelajar structure-- jika penunjuk dot seterusnya equals-- sebaliknya, jika penunjuk dot N sama sama pembolehubah N, hujah yang sudah diluluskan pada, maka saya ingin teruskan dan berkata kembali benar. Saya mendapati N beberapa bahagian dalam salah satu daripada nod senarai dikaitkan saya. Tetapi titik tidak lagi berfungsi dalam konteks ini, kerana penunjuk, PTR, adalah sesungguhnya penunjuk, alamat, kita benar-benar boleh hebat menggunakan akhirnya sekeping sintaks yang jenis jenama rasa intuitif dan benar-benar menggunakan panah ke, yang bermaksud pergi dari bahawa alamat kepada integer sana dalam. Jadi ia adalah hampir sama dalam semangat kepada pengendali titik, tetapi kerana penunjuk tidak penunjuk dan bukan struct sebenar itu sendiri, kita hanya menggunakan anak panah. 

Jadi, jika nod semasa bahawa Aku, pembolehubah sementara, sedang menghala ke arah tidak N, apa yang saya mahu lakukan? Nah, dengan sukarelawan manusia saya kalau kita ada di sini pada hari yang lain, jika manusia pertama saya bukan salah satu I mahu, dan mungkin manusia yang kedua tidak yang saya mahu, dan ketiga, saya perlu menyimpan secara fizikal bergerak. Seperti bagaimana saya melangkah melalui senarai? Apabila kita mempunyai array, anda hanya melakukan seperti saya plus plus. Tetapi dalam kes ini, ia mencukupi untuk melakukan penunjuk, mendapat, penunjuk, yang akan datang. Dengan kata lain, bidang yang akan datang adalah seperti semua daripada tangan kiri sukarelawan manusia pada hari Isnin telah menggunakan untuk menunjukkan pada satu nod lain. Mereka adalah jiran mereka seterusnya. 

Jadi, jika saya mahu melangkah melalui senarai ini, Saya tidak boleh hanya saya plus plus lagi, Saya bukannya katakan I, penunjuk, akan untuk menyamai apa sahaja bidang yang akan datang adalah, bidang yang akan datang adalah, bidang yang akan datang adalah, berikut semua orang-orang tangan kiri kalau kita ada di atas pentas menunjuk untuk beberapa nilai berikutnya. Dan jika saya mendapatkan melalui bahawa lelaran keseluruhan, dan akhirnya, saya memukul null tidak mempunyai mendapati N lagi, saya hanya kembali palsu. Jadi sekali lagi, semua yang kita lakukan di sini, seperti gambar di masa yang lalu, bermula dengan menunjuk pada permulaan senarai mungkin. Dan kemudian saya memeriksa, adalah nilai Saya sedang mencari sama dengan sembilan? Jika ya, saya kembali benar dan saya dilakukan. Jika tidak, saya mengemas kini tanganku, AKA penunjuk, untuk menunjukkan di lokasi anak panah di sebelah, dan maka lokasi anak panah depan, dan seterusnya. Saya hanya berjalan melalui pelbagai ini. 

Jadi sekali lagi, yang peduli? Seperti apa yang ini merupakan ramuan untuk? Nah, ingat bahawa kita diperkenalkan tanggapan timbunan, yang merupakan data abstrak menaip setakat yang ia bukan satu perkara yang C, ia bukan satu perkara yang CS50, ia adalah satu idea yang abstrak, idea ini menyusun perkara-perkara di atas satu sama lain yang boleh dilaksanakan dalam tandan cara yang berbeza. Dan satu cara kita dicadangkan adalah dengan pelbagai, atau dengan senarai berpaut. Dan ternyata bahawa canonically, yang timbunan menyokong sekurang-kurangnya dua operasi. Dan perkataan buzz yang menolak, untuk menolak sesuatu ke dalam tindanan, seperti dulang baru dalam dewan makan, atau pop, yang bermaksud untuk membuang yang paling atas dulang dari timbunan di makan dewan, dan kemudian mungkin beberapa operasi lain juga. Jadi bagaimana kita boleh menentukan struktur bahawa kita kini memanggil timbunan? 

Nah, kita mempunyai semua syarat yang sintaks di tangan kita dalam C. Saya berkata, memberi saya definisi jenis struct di dalam timbunan, Saya akan katakan adalah pelbagai, daripada sejumlah besar nombor dan kemudian saiz. Jadi dalam erti kata lain, jika saya mahu untuk melaksanakan ini dalam kod, biarlah saya pergi dan hanya jenis menarik apa ini mengatakan. Jadi ini mengatakan, memberi saya struktur itu mendapat pelbagai, dan saya tidak tahu apa kapasiti adalah, ia nampaknya beberapa berterusan yang saya telah ditakrifkan di tempat lain, dan itulah denda. Tetapi menganggap ia hanya satu, dua, tiga, empat, lima. Jadi kapasiti 5. Elemen di dalam saya struktur akan dipanggil nombor. Dan kemudian saya memerlukan satu pemboleh ubah lain nampaknya dipanggil saiz yang pada mulanya saya akan menetapkan ini dimulakan dengan sifar. Jika ada apa-apa dalam timbunan, saiz adalah sifar, dan ia adalah nilai sampah di nombor. Saya tidak tahu apa yang ada di sana hanya lagi. 

Jadi, jika saya mahu untuk menolak sesuatu ke dalam tindanan, kira saya memanggil push fungsi, dan Aku berkata menolak 50, seperti nombor 50, di mana anda akan mencadangkan Saya menarik dalam pelbagai ini? Ada lima jawapan yang berbeza mungkin. Di manakah anda mahu untuk menolak jumlah 50? Jika matlamat di sini, sekali lagi, hubungi push fungsi, lulus dalam pertengkaran 50, di mana saya meletakkan ia? Lima possible-- 20% peluang meneka dengan betul. Ya? 

PENONTON: Far betul. 

SPEAKER 1: Far betul. Kini terdapat peluang 25% meneka dengan betul. Jadi yang benar-benar akan menjadi baik. Mengikut konvensyen, saya akan mengatakan dengan array, kita biasanya akan bermula pada sebelah kiri, tetapi kita boleh pasti bermula dari kanan. Jadi spoiler di sini akan saya mungkin akan membawa ia di sebelah kiri, sama seperti dalam pelbagai biasa di mana Saya mula akan ke kiri ke kanan. Tetapi jika anda boleh flip aritmetik, denda. Ia hanya tidak konvensional. OK, saya perlu membuat satu perubahan lebih walaupun. Sekarang saya telah menolak sesuatu ke dalam tindanan, apa yang akan datang? 

Baiklah, saya perlu kenaikan saiz. Jadi biarlah saya pergi ke hadapan dan hanya kini ini, yang sifar. Dan bukannya sekarang, saya akan untuk dimasukkan ke dalam nilai satu. Dan kini kira saya menolak lagi nombor ke dalam tindanan, seperti 51. Well, saya perlu membuat satu lagi perubahan, yang adalah saiz kedua-dua. Dan kemudian kira saya menolak satu lagi nombor ke dalam tindanan seperti 61, sekarang saya perlu mengemas kini saiz satu lagi masa, dan mendapatkan nilai 3 sebagai saiz. Dan kini kira saya memanggil pop. Sekarang pop, oleh konvensyen, tidak mengambil hujah. Dengan timbunan, keseluruhannya titik metafora dulang adalah bahawa anda tidak mempunyai budi bicara pergi mendapatkan dulang itu, semua yang boleh anda lakukan adalah pop satu paling atas dari timbunan, hanya kerana. Itulah yang struktur data ini tidak. 

Jadi dengan logik bahawa jika saya mengatakan pop dan apa yang keluar? Jadi 61. Jadi apa yang sebenarnya adalah komputer akan lakukan dalam ingatan? Apakah kod saya perlu lakukan? Apa yang anda akan mencadangkan kita berubah pada skrin? Apakah yang perlu berubah? Maaf? Oleh itu, kita menghilangkan 61. Jadi saya pasti boleh melakukannya. Dan saya boleh menghilangkan 61. Dan kemudian apa yang lain perubahan yang perlu berlaku? Saiz mungkin mempunyai untuk kembali ke dua. Dan sebagainya itulah denda. Tetapi tunggu satu minit, saiz masa lalu adalah tiga. Mari kita hanya melakukan pemeriksaan kewarasan cepat. Bagaimana kita tahu bahawa kita mahukan untuk menghilangkan 61? Kerana kita pop. Oleh itu, saya mempunyai saiz hartanah ini kedua. 

Tunggu satu minit, Saya memikirkan kembali dua minggu apabila kita mula bercakap tentang tatasusunan, di mana ini merupakan lokasi sifar, ini adalah salah satu lokasi, ini adalah lokasi dua, ini adalah lokasi tiga, empat, ia kelihatan seperti hubungan antara saiz dan elemen yang saya mahu mengeluarkan dari pelbagai nampaknya hanya menjadi apa? Saiz tolak satu. Dan sebagainya itu bagaimana sebagai manusia kita tahu 61 yang terdahulu. Bagaimana dengan komputer akan tahu? Apabila kod anda, di mana anda mungkin mahu lakukan saiz tolak satu, jadi tiga tolak satu adalah dua, dan yang bermakna kita mahu menghapuskan 61. Dan kemudian kita memang boleh mengemas kini saiz jadi saiz yang kini pergi daripada tiga kepada dua. Dan hanya untuk bengah, saya akan untuk mencadangkan bahawa saya sudah selesai, bukan? Anda dicadangkan intuitif betul saya perlu menghilangkan 61. Tetapi belum saya jenis semacam mendapat menghilangkan 61? Saya terlupa berkesan bahawa ia sebenarnya di sana. Dan berfikir kembali ke PSET4, jika anda telah membaca artikel mengenai forensik, PDF bahawa kita mempunyai anda semua membaca, atau anda akan membaca minggu ini untuk PSET4. Ingat bahawa ini adalah benar-benar germane untuk idea keseluruhan forensik komputer. Apa komputer yang secara umumnya tidak adalah ia hanya lupa mana sesuatu itu, tetapi ia tidak masuk dan seperti cuba menggaru ia keluar atau mengatasi bit-bit dengan sifar dan satu atau beberapa corak rawak lain melainkan anda sendiri berbuat demikian sengaja. Jadi gerak hati anda adalah Baiklah, mari kita buang 61. Tetapi dalam realiti, kita tidak perlu bersusah payah. Kita hanya perlu lupa bahawa ianya ada dengan menukar saiz kami. 

Sekarang ada masalah dengan timbunan ini. Jika saya terus menolak perkara-perkara ke dalam tindanan, apa yang jelas akan berlaku hanya dalam masa beberapa ketika? Kita akan kehabisan ruang. Dan apa yang kita lakukan? Kami sejenis diskru. Pelaksanaan ini tidak membiarkan kami mengubah saiz array, kerana menggunakan sintaks ini, jika anda berfikir kembali ke minggu dua, sebaik sahaja anda telah diisytiharkan saiz pelbagai, kami tidak melihat mekanisme lagi di mana anda boleh menukar saiz array. Dan sesungguhnya C tidak mempunyai ciri-ciri itu. Jika anda mengatakan memberi saya lima Nths, merujuk kepada mereka nombor, itu sahaja anda akan mendapatkannya. Oleh itu, kita lakukan sekarang pada hari Isnin, mempunyai keupayaan untuk menyatakan penyelesaian walaupun, kita hanya perlu untuk tweak takrif timbunan kami untuk tidak beberapa pelbagai berkod keras, tetapi hanya untuk menyimpan alamat. 

Sekarang mengapa ini? Sekarang kita hanya perlu untuk menjadi selesa dengan hakikat bahawa apabila program saya berjalan, Saya mungkin akan perlu bertanya kepada manusia, berapa banyak nombor yang anda mahu simpan? Jadi input yang perlu datang dari suatu tempat. Tetapi apabila saya tahu bahawa nombor, maka saya boleh hanya menggunakan apa yang berfungsi untuk memberi saya sebahagian memori? Saya boleh menggunakan malloc. Dan saya boleh mengatakan apa-apa bilangan bait Saya hendak kembali untuk Nths ini. Dan apa yang saya perlu simpan di nombor berubah-ubah di sini di dalam struct ini perlu apa? Apa yang sebenarnya masuk ke dalam nombor dalam senario ini? Ya, penunjuk kepada orang pertama bait yang sebahagian memori, atau lebih khusus, alamat daripada orang yang awal pertama bait. Tidak kira sama ada ia adalah salah satu bait atau satu bilion bait, Saya hanya perlu untuk mengambil berat tentang yang pertama. Kerana apa jaminan malloc dan jaminan sistem operasi saya, adalah bahawa sebahagian memori saya mendapatkan, ia akan menjadi yang berhampiran. Ada tidak akan menjadi jurang. Jadi, jika saya telah meminta 50 bait atau 1,000 bait, mereka semua akan menjadi kembali ke belakang untuk kembali. Dan selagi saya masih ingat berapa besar, berapa banyak saya meminta, semua yang saya perlu tahu adalah alamat sedemikian yang pertama. 

Jadi sekarang kita mempunyai keupayaan dalam kod. Walaupun, ia akan membawa kita lebih banyak masa untuk menulis ini ke atas, kita kini boleh mengagihkan semula memori dengan hanya menyimpan alamat yang berbeza di sana jika kita mahu yang lebih besar atau sebahagian yang lebih kecil daripada ingatan. Jadi di sini kepada keseimbangan. Sekarang kita mendapat dinamik. Kami masih mempunyai contiguousness saya mendakwa. Kerana malloc akan memberikan kita sebahagian berdampingan memori. Tetapi ini akan menjadi sakit di leher untuk kita, pengaturcara, untuk benar-benar memberi kod up. Ia adalah kerja hanya lebih. Kami memerlukan kod yang serupa dengan apa yang saya terhantuk keluar hanya sebentar tadi. Sangat boleh dilakukan, tetapi ia menambah kerumitan. Dan jadi masa pemaju, programmer masa lagi sumber lain bahawa kita mungkin perlu menghabiskan sedikit masa untuk mendapatkan ciri-ciri baru. Kemudian sudah tentu ada barisan. Kami tidak akan pergi ke ini satu secara terperinci banyak. Tetapi ia adalah hampir sama dalam semangat. Saya boleh melaksanakan barisan, dan operasi yang sepadan dengannya, enqueue atau dequeue, seperti menambah atau mengeluarkan, ia hanya cara yang pelamun untuk mengatakan ini, enqueue atau dequeue, seperti berikut. Saya hanya boleh memberikan diri saya struct itu lagi mempunyai pelbagai beberapa kanak, itu lagi mempunyai saiz yang, tetapi mengapa saya kini perlu untuk mengesan bahagian depan barisan? Saya tidak perlu tahu hadapan timbunan saya. Nah, jika saya sekali lagi untuk queue-- mari kita keras kod itu sebagai mempunyai seperti lima bilangan bulat di sini berpotensi. Jadi ini adalah sifar, satu, dua, tiga, empat. Ini akan menjadi dipanggil nombor lagi. Dan ini akan dipanggil saiz. 

Mengapa ia tidak mencukupi untuk mempunyai hanya saiz? Nah, mari kita tolak nombor-nombor sama pada. Jadi saya pushed-- Saya enqueued, atau ditolak. Sekarang saya akan enqueue 50, dan kemudian 51, dan kemudian 61, dan dot dot dot. Jadi itulah enqueue. Saya enqueued 50, kemudian 51, kemudian 61. Dan itu kelihatan sama untuk timbunan setakat ini, kecuali saya perlu membuat satu perubahan. Saya perlu mengemaskinikan saiz ini, jadi saya pergi dari sifar kepada satu kepada dua hingga tiga sekarang. Bagaimana saya dequeue? Apa yang berlaku dengan dequeue? Siapa yang patut terkeluar senarai ini pertama jika ia barisan di Kedai Apple? Jadi 50. Jadi ia adalah jenis sukar kali ini. Sedangkan masa lalu, ia adalah super mudah untuk hanya melakukan saiz tolak satu, Saya sampai ke akhir array saya dengan berkesan mana nombor-nombor itu, ia membuang 61. Tetapi saya tidak mahu mengeluarkan 61. Saya ingin mengambil 50, yang berada di sana pada 05:00 untuk beratur untuk iPhone baru atau barang kecil. Dan sebagainya untuk menghilangkan 50, saya tidak boleh melakukan ini, bukan? Saya boleh batalkan 50. Tetapi kita hanya berkata kita tidak perlu menjadi begitu dubur untuk menggaru atau menyembunyikan data. Kami hanya boleh lupa di mana ia. 

Tetapi jika saya menukar saiz saya sekarang untuk dua, maklumat yang mencukupi ini untuk mengetahui apa yang sedang berlaku di dalam giliran saya? Tidak benar-benar. Seperti saiz saya ialah dua, tetapi di manakah barisan memulakan, terutamanya jika saya masih mempunyai nombor-nombor yang sama dalam ingatan. 50, 51, 61. Jadi saya perlu ingat sekarang di mana hadapan adalah. Dan supaya saya mencadangkan sehingga di sana, kita akan telah hanya dipanggil Depan ke-n, yang awal nilai sepatutnya apa? Zero, hanya permulaan senarai. Tetapi sekarang sebagai tambahan kepada decrementing saiz, kita hanya kenaikan hadapan. Sekarang ada masalah lain. Jadi apabila saya terus pergi. Katakan ini ialah bilangan seperti 121, 124, dan kemudian, celaka, Saya keluar dari ruang. Tetapi tunggu satu minit, saya tidak. Jadi pada ketika ini dalam cerita, menganggap bahawa saiz adalah satu, dua, tiga, empat, sehingga mengira bahawa saiz adalah empat, depan adalah satu, jadi 51 adalah di bahagian hadapan. Saya mahu meletakkan nombor lain di sini, tetapi, celaka, saya keluar dari ruang. Namun, saya tidak benar-benar, betul-betul? Di mana saya boleh meletakkan beberapa nilai tambahan, seperti 171? Ya, saya boleh hanya jenis kembali ke sana, bukan? Dan kemudian batalkan 50, atau hanya menimpa dengan 171. Dan jika anda tertanya-tanya mengapa nombor kami mendapat begitu rawak, ini biasanya diambil komputer kursus sains di Harvard selepas CS50. Tetapi itu adalah pengoptimuman yang baik, kerana sekarang saya tidak membazirkan ruang. Saya masih perlu ingat betapa besar perkara ini adalah jumlah. Ia adalah lima jumlah. Kerana saya tidak mahu mula menulis ganti 51. Jadi sekarang saya masih di luar ruang, supaya masalah yang sama seperti sebelum ini. Tetapi anda boleh lihat bagaimana sekarang dalam kod anda, anda mungkin perlu menulis sedikit lebih kerumitan untuk membuat yang berlaku. Dan sebenarnya, pengendali apa dalam C mungkin membolehkan anda ajaib cookies bundar itu? Yeah pengendali modulo itu, tanda peratus. Jadi apa jenis sejuk tentang barisan, walaupun kita menyimpan lukisan tatasusunan kerana ini garis lurus seperti, jika anda jenis berfikir tentang perkara ini melengkung sekitar sebagai satu bulatan, maka hanya intuitif ia jenis kerja-kerja mental Saya rasa sedikit lebih bersih. Anda masih perlu melaksanakan bahawa model mental dalam kod. Jadi tidak sukar, akhirnya, untuk melaksanakan, tetapi kita masih kehilangan size-- sebaliknya, keupayaan untuk mengubah saiz, melainkan jika kita melakukan ini. 

Kita perlu menghilangkan array, kita menggantikannya dengan penunjuk tunggal, dan kemudian di suatu tempat di kod saya saya telah mendapat yang memanggil apa yang berfungsi untuk benar-benar membuat array dipanggil nombor? Malloc, atau sama fungsi, betul-betul. Sebarang pertanyaan mengenai susunan atau beratur. Ya? Soalan yang baik. Apa modulo anda akan menggunakan di sini. Jadi secara umumnya, apabila menggunakan mod, anda akan melakukannya dengan saiz struktur data keseluruhan. Jadi sesuatu seperti lima atau kapasiti, jika ia berterusan, yang mungkin terlibat. Tetapi hanya melakukan modulo lima mungkin tidak mencukupi, kerana kita perlu tahu kita membungkus sini atau di sini atau di sini. Jadi anda mungkin juga akan mahu melibatkan saiz benda itu, atau berubah-depan juga. Jadi ia hanya ini yang agak ungkapan aritmetik mudah, tetapi modulo akan menjadi bahan utama. 

Filem begitu pendek jika anda akan. Animasi bahawa beberapa Penduduk di universiti lain meletakkan bersama-sama yang kita ada disesuaikan untuk perbincangan ini. Ia melibatkan Jack pembelajaran fakta tentang barisan dan statistik. 

FILEM: Pada suatu masa dahulu, ada seorang lelaki bernama Jack. Apabila ia datang untuk membuat kawan-kawan, Jack tidak mempunyai cukup pengetahuan. Jadi Jack pergi ke bercakap dengan Lelaki yang paling popular dia tahu. Dia pergi ke Lou dan bertanya: Apa yang perlu saya lakukan? Lou melihat bahawa kawannya benar-benar bermasalah. Well, dia mula, hanya melihat bagaimana anda berpakaian. Apakah kamu tidak mempunyai apa-apa pakaian dengan wajah yang berbeza? Ya, kata Jack. Saya pasti lakukan. Datang ke rumah saya dan Saya akan menunjukkan kepada anda. Lalu mereka pergi kepada Jack. Dan Jack menunjukkan Lou kotak di mana beliau melindungi segala baju beliau, dan seluarnya, dan khuf. Lou berkata, saya melihat anda mempunyai semua pakaian anda dalam longgokan. Mengapa tidak anda memakai beberapa lain sekali dalam seketika? 

Jack berkata, dengan baik, apabila saya mengeluarkan pakaian dan sarung kaki, Saya mencuci mereka dan meletakkan mereka jauh di dalam kotak. Kemudian datang seterusnya pagi, dan ke atas hop. Saya pergi ke kotak dan mendapatkan pakaian saya atas. Lou cepat sedar masalah dengan Jack. Dia memelihara pakaian, CD, dan buku-buku dalam timbunan. Apabila dia sampai untuk sesuatu untuk membaca atau untuk dipakai, dia akan memilih buku atas atau seluar dalam. Kemudian apabila dia telah dilakukan, dia akan meletakkan ia segera kembali. Kembali ia akan pergi, di atas timbunan. Saya tahu penyelesaian, kata seorang Loud berjaya. Anda perlu belajar untuk mula menggunakan barisan. Lou mengambil pakaian Jack dan digantung mereka di dalam almari. Dan apabila dia telah dikosongkan kotak, dia hanya melepaskannya. 

Kemudian dia berkata, kini Jack, pada akhir hari, meletakkan pakaian anda di sebelah kiri apabila anda meletakkan mereka pergi. Maka esok pagi apabila anda melihat cahaya matahari, dapatkan pakaian anda di sebelah kanan, dari akhir baris. Adakah anda tidak melihat? kata Lou. Ia akan menjadi begitu baik. Anda akan memakai segala-galanya sekali sebelum anda memakai sesuatu yang dua kali. Dan dengan segala-galanya dalam barisan dalam almari dan rak-Nya, Jack mula berasa pasti dirinya. Semua terima kasih kepada Lou dan barisan yang indah beliau. SPEAKER 1: Baiklah, ia adalah comel. Jadi apa yang telah benar-benar berlaku di bawah hood sekarang? Yang kita ada petunjuk, yang kita ada malloc, yang kita ada keupayaan untuk mewujudkan ketulan memori untuk diri kita sendiri dinamik. Jadi ini adalah satu kita gambar celah hanya pada hari yang lain. Kami tidak benar-benar kekal di atasnya, tetapi gambar ini mempunyai telah berlaku di bawah bonet selama beberapa minggu sekarang. Dan hal ini mewakili, hanya segi empat tepat yang kita telah disediakan, memori komputer anda. Dan mungkin komputer anda, atau CS50 ID, mempunyai gigabit memori atau RAM atau dua gigabait atau empat. Ia tidak benar-benar perkara itu. Sistem operasi anda Windows atau Mac OS atau Linux, dasarnya membolehkan program anda untuk berfikir bahawa ia mempunyai akses kepada keseluruhan memori komputer anda, walaupun anda mungkin berjalan pelbagai program pada satu masa. Jadi pada hakikatnya, itu tidak benar-benar berkesan. Tetapi ia adalah jenis ilusi diberikan kepada semua program anda. Jadi, jika anda mempunyai dua gig RAM, ini adalah bagaimana komputer mungkin berfikir. 

Sekarang kebetulan, salah satu daripada perkara, salah satu daripada segmen memori, dipanggil timbunan. Dan sesungguhnya bila-bila masa setakat ini dalam menulis kod bahawa anda telah dipanggil fungsi, sebagai contoh utama. Ingat bahawa bila-bila masa saya telah memori komputer disediakan ini, Saya sentiasa menarik semacam separuh daripada segi empat tepat di sini dan tidak mengganggu bercakap tentang apa yang ada di atas. Kerana apabila utama dipanggil, saya menuntut yang anda dapat sekerat ini memori yang turun di sini. Dan jika utama dipanggil fungsi seperti pertukaran, baik pertukaran pergi sini. Dan ternyata, itu di mana ia berakhir. Pada sesuatu yang dipanggil timbunan dalam memori komputer anda. Sesudah lewat hari, ini hanya menangani. Ia seperti bait sifar, bait satu, bait 2 bilion. Tetapi jika anda berfikir tentang hal itu sebagai objek segi empat tepat ini, semua yang kita lakukan setiap kali kita memanggil fungsi adalah lapisan sepotong baru memori. Kami memberikan fungsi yang bahagian yang memori sendiri untuk bekerja dengan. 

Dan ingat kini bahawa ini adalah penting. Kerana jika kita mempunyai sesuatu seperti pertukaran dan dua pembolehubah tempatan seperti A dan B dan kita menukar nilai-nilai dari satu dan dua dua dan satu, ingat bahawa apabila pertukaran kembali, ia seolah-olah keping ini memori hanya hilang. Pada hakikatnya, ia masih terdapat forensik. Dan sesuatu yang masih benar-benar di sana. Tetapi dari segi konsep, ia seolah- walaupun ia benar-benar hilang. Dan sebagainya utama tidak tahu apa-apa kerja yang telah dilakukan dalam fungsi swap, melainkan jika ia sebenarnya diluluskan pada mereka hujah-hujah oleh penunjuk atau rujukan. Kini, penyelesaian asas itu masalah dengan pertukaran berlalu perkara dalam dengan alamat. Tetapi ternyata, juga, apa yang telah berlaku di atas bahagian itu segi empat tepat selama ini adalah belum ada lebih banyak memori di sana. Dan apabila anda secara dinamik memperuntukkan ingatan, sama ada di dalam GetString, yang yang kita telah lakukan untuk anda dalam CS50 perpustakaan, atau jika anda seorang lelaki memanggil malloc dan meminta sistem yang beroperasi untuk sebahagian daripada ingatan, ia tidak datang dari timbunan. Ia datang dari tempat lain dalam memori komputer anda yang dinamakan timbunan itu. Dan itu bukan apa-apa yang berbeza. Ia RAM yang sama. Ia memori yang sama. Ia hanya RAM itu terpulang ada dan bukannya di bawah ini. 

Dan jadi apa maksudnya? Nah, jika komputer anda mempunyai jumlah yang terhad memori dan timbunan membesar, jadi untuk bercakap, dan timbunan itu, menurut untuk anak panah ini, berkembang ke bawah. Dalam erti kata lain, setiap kali anda memanggil malloc, anda diberi bahagian yang memori dari atas, maka mungkin sedikit lebih rendah, maka sedikit yang lebih rendah, setiap kali anda memanggil malloc, timbunan itu, ia adalah penggunaan, adalah jenis yang semakin meningkat, semakin dekat dan lebih dekat kepada apa? The timbunan. Jadi adakah ini kelihatan seperti idea yang baik? Maksud saya, di mana ia tidak benar-benar jelas apa lagi yang boleh anda lakukan jika anda hanya mempunyai jumlah yang terbatas memori. Tetapi ini sudah tentu tidak baik. Kedua-dua anak-anak panah pada crash kursus untuk satu sama lain. 

Dan ternyata bahawa lelaki yang tidak baik, orang yang adalah sangat baik dengan program, dan cuba untuk menggodam komputer, boleh mengeksploitasi realiti ini. Malah, mari kita mempertimbangkan coretan sedikit. Jadi ini adalah satu contoh, anda boleh membaca mengenai dengan lebih terperinci di Wikipedia. Kami akan menunjukkan anda di artikel jika ingin tahu. Tetapi ada serangan umumnya dikenali sebagai buffer overflow yang telah wujud selagi manusia mempunyai keupayaan untuk memanipulasi memori komputer, terutamanya di C. Jadi ini adalah satu program yang sangat sewenang-wenangnya, tetapi mari kita baca dari bawah ke atas. Utama ke argc char bintang argv. Jadi ia adalah satu program yang mengambil hujah baris arahan. Dan semua utama tidak nampaknya adalah panggilan fungsi, memanggilnya F untuk kesederhanaan. Dan ia berlalu dalam apa? Argv satu. Jadi ia mengalir ke dalam F apa sahaja perkataan ini adalah bahawa pengguna ditaip di prompt selepas nama program ini sama sekali. Begitu banyak seperti Caesar atau Vigenere, yang anda mungkin ingat lakukan dengan argv. 

Jadi apa F? F mengambil masa dalam rentetan sebagai hujah bicara mutlaknya, AKA bintang char, sama perkara, sebagai rentetan. Dan ia dipanggil sewenang-wenangnya bar dalam contoh ini. Dan kemudian char c 12, sahaja dari segi orang biasa itu, apa yang char c kurungan 12 lakukan untuk kita? Apa yang ia buat? Memperuntukkan ingatan, khusus 12 bait untuk 12 aksara. Tepat sekali. Dan kemudian barisan terakhir, kacau dan menyalin, anda mungkin tidak dapat dilihat. Ini adalah salinan rentetan fungsi yang tujuan dalam hidup adalah untuk menyalin hujah kedua ke dalam hujah pertama, tetapi hanya sehingga sebilangan bait. Jadi pendapat ketiga tadi berkata, berapa banyak bait anda perlu menyalin? Panjang bar, apa pengguna ditaip. Dan kandungan menggalang, tali itu, adalah disalin ke dalam ingatan menunjuk pada di C. 

Jadi ini seolah-olah jenis bodoh, lalu menjadilah ia. Ia adalah satu contoh tersusun, tetapi ia adalah wakil daripada kelas vektor serangan, cara menyerang program. Semua adalah baik dan baik jika pengguna jenis dalam satu perkataan itu 11 aksara atau kurang, ditambah backslash sifar. Bagaimana jika jenis pengguna di lebih daripada 11 atau 12 atau 20 atau 50 aksara? Apa yang program ini akan lakukan? Kesalahan berpotensi seg. Ia akan membuta tuli menyalin segala-galanya dalam bar sehingga panjang, yang merupakan benar-benar segala-galanya dalam bar, ke alamat menunjuk pada C. Tetapi C hanya preemptively diberikan sebagai 12 bait. Tetapi tidak ada daftar tambahan. Tidak ada jika keadaan. Tidak ada ralat memeriksa di sini. 

Dan supaya apa yang program ini adalah akan lakukan ialah hanya membuta tuli menyalin satu perkara yang lain. Dan jadi jika kita menarik ini sebagai gambar, di sini adalah hanya sekerat ruang memori. Jadi notis di bahagian bawah, kita mempunyai bar pembolehubah tempatan. Supaya penunjuk yang akan store-- sebaliknya hujah tempatan itu akan menyimpan bar tali. Dan kemudian melihat hanya di atasnya dalam timbunan, kerana setiap kali anda bertanya untuk ingatan pada timbunan, ia pergi sedikit di atasnya bergambar, notis bahawa kita telah mendapat 12 bait sana. Yang kiri atas ialah C kurungan sifar dan satu kanan bawah adalah C kurungan 11. Itu hanya bagaimana komputer akan meletakkan ia keluar. Jadi hanya intuitif, jika bar mempunyai lebih daripada 12 aksara dalam jumlah, termasuk garis miring sifar, di mana adalah 12 atau kurungan C 12 akan pergi? Atau sebaliknya mana-12 watak atau watak-13, watak seratus akan berakhir di dalam gambar? Atas atau di bawah? 

Betul, kerana walaupun timbunan itu sendiri tumbuh ke atas, sebaik sahaja anda telah meletakkan barangan di ia, atas sebab-sebab reka bentuk, meletakkan ingatan dari atas ke bawah. Jadi, jika anda mempunyai lebih daripada 12 bait, anda akan mula menulis ganti bar. Sekarang ini pepijat, tetapi ia tidak benar-benar masalah besar. Tetapi ia adalah masalah besar, kerana ada lebih banyak bahan yang berlaku di dalam ingatan. Jadi di sini adalah bagaimana kita mungkin meletakkan hello, menjadi jelas. Jika saya ditaip hello di prompt. Garis miring sifar H-E-L-L-O, berakhir dalam mereka 12 bait, dan kami super selamat. Semuanya berjalan dengan lancar. Tetapi jika saya menaip sesuatu lagi, yang berpotensi itu akan menjalar ke dalam ruang bar. Tetapi lebih teruk lagi, ia ternyata sepanjang masa ini, walaupun kita tidak pernah bercakap tentang ia, timbunan itu digunakan untuk perkara lain. Ia bukan hanya pembolehubah tempatan. 

C ialah bahasa tahap yang sangat rendah. Dan ia semacam rahsia menggunakan tindanan juga ingat apabila fungsi dipanggil, apa alamat adalah fungsi sebelumnya, jadi ia boleh melompat ke belakang dengan fungsi itu. Oleh itu, apabila panggilan utama swap, antara perkara-perkara yang ditolak ke dalam tindanan tidak hanya swap pembolehubah tempatan, atau hujah-hujah, juga diam-diam ditolak ke dalam tindanan yang diwakili oleh keping merah di sini, adalah alamat utama fizikal dalam memori komputer anda, supaya apabila pertukaran dilakukan, komputer tahu saya perlu kembali ke utama dan menyelesaikan melaksanakan fungsi utama. Jadi ini adalah berbahaya sekarang, kerana jika jenis pengguna dalam juga lebih daripada hello, apa-apa yang input pengguna clobbers atau menulis ganti bahawa seksyen merah, secara logik jika komputer hanya akan membuta tuli menganggap bahawa bait dalam sepotong merah alamat di mana ia harus kembali, bagaimana jika musuh yang cukup pintar atau bernasib baik untuk meletakkan urutan bait ada yang kelihatan seperti alamat, tetapi ia adalah alamat kod bahawa dia atau dia mahu komputer untuk melaksanakan dan bukan utama? 

Dalam erti kata lain, jika apa yang pengguna sedang menaip pada yang cepat, bukan sahaja sesuatu seperti tidak berbahaya hello, tetapi ia sebenarnya kod yang bersamaan untuk memadam semua fail pengguna ini? Atau e-mel kata laluan mereka kepada saya? Atau memulakan pembalakan mereka ketukan kekunci, bukan? Terdapat cara yang, mari kita menetapkan hari ini, bahawa mereka boleh masuk ke dalam bukan sahaja hello dunia atau nama mereka, mereka boleh pada dasarnya lulus dalam kod, sifar dan yang, bahawa komputer kesilapan untuk kedua-dua kod dan alamat. Jadi walaupun agak abstrak, jika jenis pengguna dalam cukup kod pertentangan bahawa kita akan umum di sini kerana A. A adalah serangan atau musuh. Barangan Jadi hanya tidak baik. Kami tidak mengambil berat tentang nombor atau sifar atau orang-orang hari ini, seperti yang anda berakhir penggantian seksyen yang merah, melihat bahawa jujukan bait. O 835 C sifar lapan sifar. Dan kini sebagai artikel Wikipedia di sini telah dicadangkan, jika anda kini benar-benar memulakan melabel bait dalam komputer anda ingatan, apa yang artikel Wikipedia adalah mencadangkan ialah, bagaimana jika alamat itu bait kiri atas adalah 80 C 0 3508. 

Dalam erti kata lain, jika lelaki yang buruk adalah bijak dengan kod nya untuk benar-benar meletakkan nombor di sini bahawa sepadan dengan alamat kod di dia disuntik ke dalam komputer, anda boleh menipu komputer ke dalam melakukan apa-apa. Menghapuskan fail, menghantar e-mel perkara, menghidu trafik anda, apa sahaja yang boleh menjadi disuntik ke dalam komputer. Dan kerana itu suatu buffer overflow serangan pada terasnya hanya bodoh, bodoh lebih penting dari array yang tidak mempunyai sempadannya diperiksa. Dan ini adalah apa yang super berbahaya dan pada masa yang sama super kuat dalam C ialah kita memang mempunyai akses kepada mana-mana sahaja dalam memori. Terpulang kepada kita, pengaturcara, yang menulis kod asal untuk memeriksa panjang darn mana-mana tatasusunan bahawa kita memanipulasi. Jadi untuk menjadi jelas, apa yang menetapkan? Jika kita melancarkan kembali ini kod, saya tidak perlu hanya menukar panjang bar, apa lagi yang perlu saya dapat check? Apa lagi yang perlu saya lakukan untuk mengelakkan serangan ini sepenuhnya? Saya tidak mahu hanya membuta tuli mengatakan bahawa anda perlu menyalin sebanyak bait seperti yang panjang bar. Saya ingin mengatakan, salinan sebagai banyak bait yang pada bar sehingga yang diperuntukkan memori, atau 12 maksima. Jadi saya perlu beberapa jenis jika keadaan yang tidak menyemak panjang bar, tetapi jika ia melebihi 12, kita Kod hanya sukar 12 jarak maksimum yang mungkin. Jika tidak penampan yang dipanggil serangan limpahan boleh berlaku. Di bahagian bawah slaid, jika anda ingin tahu untuk membaca lebih adalah artikel asal yang sebenar jika anda ingin lihat. 

Tetapi sekarang, antara harga dibayar di sini adalah ketidakcekapan. Sehingga adalah cepat rupa paras rendah pada apa masalah boleh timbul sekarang kita yang mempunyai akses kepada memori komputer. Tetapi satu lagi masalah kita telah tersandung pada Isnin hanya ketidakcekapan daripada senarai berpaut. Kita kembali ke semasa linear. Kita tidak lagi mempunyai pelbagai yang berhampiran. Kami tidak mempunyai capaian rawak. Kita tidak boleh menggunakan notasi kurungan persegi. Kami benar-benar perlu menggunakan gelung sementara seperti yang saya tulis sebentar tadi. Tetapi pada hari Isnin, kita mendakwa bahawa kita boleh merayap kembali ke alam kecekapan mencapai sesuatu yang logaritma mungkin, atau terbaik lagi, mungkin juga sesuatu yang apa yang dikenali sebagai masa yang berterusan. Jadi bagaimana kita boleh berbuat demikian dengan menggunakan ini baru alat, alamat-alamat ini, petunjuk ini, dan threading perkara-perkara yang kita sendiri? Nah, katakan di sini, ini adalah sekumpulan nombor yang kita mahu menyimpan dalam struktur data dan carian cekap. Kami benar-benar boleh putar balik ke minggu dua, membuang ini ke dalam array, dan mencari mereka menggunakan carian binari. Pecah dan perintah. Dan sebenarnya anda menulis carian binari dalam PSET3, di mana anda melaksanakan program yang dicari. Tetapi anda tahu apa. Ada jenis yang lebih cara bijak untuk berbuat demikian. Ia lebih sedikit canggih dan ia mungkin membolehkan kita untuk melihat mengapa binari carian adalah begitu banyak lebih cepat. Pertama, mari kita memperkenalkan tanggapan pokok. Yang walaupun dalam pokok realiti sejenis tumbuh seperti ini, dalam dunia komputer sains mereka sejenis tumbuh ke bawah seperti pokok keluarga, di mana anda perlu datuk nenek atau datuk dan nenek yang hebat atau barang kecil di bahagian atas, bapa leluhur kita, dan ibu pemimpin keluarga, hanya satu yang dipanggil akar, nod, di bawah yang anak-anak mereka, di bawah yang adalah anak-anak, atau keturunannya amnya. Dan sesiapa yang tergantung dari bahagian bawah keluarga pokok, selain menjadi bongsu dalam keluarga, juga boleh hanya menjadi generik dipanggil daun pokok itu. 

Jadi ini adalah hanya sekumpulan perkataan dan definisi untuk sesuatu yang dipanggil pokok dalam komputer sains, sama seperti pohon keluarga. Tetapi ada jelmaan pelamun pokok, satu daripadanya dipanggil pokok carian binari. Dan anda boleh jenis menggoda selain apa yang perkara ini tidak. Nah, itu binari dalam apa rasa? Di manakah binari datang dari sini? Maaf? Ia tidak begitu banyak sama ada atau. Ia lebih bahawa setiap satu daripada nod tidak mempunyai lebih daripada dua kanak-kanak, seperti yang kita lihat di sini. Secara umum, tree-- dan ibu bapa dan datuk dan nenek anda boleh mempunyai banyak anak-anak atau cucu kerana mereka benar-benar mahu, dan sebagainya misalnya di sana kami mempunyai tiga anak luar bahawa nod tangan kanan, tetapi di pokok binari, nod mempunyai sifar, satu, atau dua kanak-kanak maksima. Dan itu yang terletak di, kerana jika ia dihadkan oleh dua, kita akan dapat mendapatkan asas log sedikit dua tindakan berlaku di sini akhirnya. Oleh itu, kita mempunyai sesuatu logaritma. Tetapi lebih kepada yang dalam seketika. Pokok carian bermakna bahawa nombor-nombor disediakan supaya kanak-kanak sayap kiri nilai lebih besar daripada akar. Dan kanak-kanak haknya adalah lebih besar daripada akar. Dalam erti kata lain, jika anda mengambil mana-mana daripada nod, bulatan dalam gambar ini, dan melihat kirinya kanak-kanak dan kanak-kanak kanan, pertama hendaklah tidak kurang daripada, kedua harus lebih besar daripada. Jadi kewarasan menyemak 55. Ia meninggalkan kanak-kanak adalah 33. Ia adalah kurang daripada. 55, kanak-kanak haknya adalah 77. Ia adalah lebih besar daripada. Dan itu adalah satu definisi rekursi. Kita boleh memeriksa setiap salah seorang daripada mereka nod dan corak yang sama akan tahan. 

Jadi apa yang baik dalam pokok carian binari, adalah yang satu, ia dapat dilaksanakan dengan struct, sama seperti ini. Dan walaupun kita membuang banyak struktur di anda, mereka agak intuitif sekarang mudah-mudahan. Sintaks ini masih sukar difahami yang pasti, tetapi kandungan nod dalam ini context-- dan kami terus menggunakan nod perkataan, sama ada ia adalah segi empat tepat pada skrin atau bulatan, ia hanya beberapa bekas generik, dalam kes ini pokok, seperti yang yang kita lihat, kita memerlukan integer Setiap nod dan kemudian saya memerlukan dua petunjuk menunjuk kepada kanak-kanak di sebelah kiri dan kanak-kanak yang betul, masing-masing. Jadi itulah bagaimana kita mungkin melaksanakan bahawa dalam struct. Dan bagaimana aku dapat melaksanakannya dalam kod? Nah, mari kita cepat melihat contoh kecil ini. Ia tidak berfungsi, tetapi saya telah disalin dan ditampal struktur tersebut. Dan jika fungsi saya untuk binari pokok carian dipanggil carian, dan ini mengambil masa dua hujah, yang N integer dan penunjuk untuk nod, jadi penunjuk kepada pokok atau penunjuk kepada akar pokok, bagaimana saya boleh pergi tentang mencari N? Well, pertama, kerana saya berurusan dengan petunjuk, Saya akan melakukan pemeriksaan kewarasan. Jika setaraf pokok sama null, ialah N dalam pokok ini atau tidak dalam pokok ini? Ia tidak boleh, bukan? Jika saya lalu null, tiada apa-apa di sana. Saya mungkin juga hanya membuta tuli mengatakan kembali palsu. Jika anda memberi saya apa-apa, saya pasti tidak boleh mencari mana-mana nombor N. Jadi apa lagi yang mungkin saya periksa sekarang? Saya akan mengatakan dengan baik lagi kalau N adalah kurang daripada apa yang ada pada nod pokok bahawa saya telah menyerahkan nilai N. Dalam erti kata lain, jika bilangan Saya cari, N, adalah kurang daripada nod yang saya lihat. Dan nod Saya sedang di dipanggil pokok, dan ingat dari contoh sebelumnya untuk mendapatkan sekurang-nilai dalam penunjuk, Saya menggunakan anak panah notasi. Jadi, jika N adalah kurang daripada pokok anak panah N, saya mahu dari segi konsep pergi kiri. Bagaimana saya daftar mencari kiri? Untuk menjadi jelas, jika ini adalah gambar yang berkenaan, dan saya telah diluluskan yang paling atas arrow yang menunjuk ke bawah. Itulah penunjuk pokok saya. Saya menunjuk pada akar pokok. Dan saya tidak katakan, untuk nombor 44, sewenang-wenangnya. 44 kurang daripada atau lebih besar daripada 55 jelas? Jadi ia adalah kurang daripada. Dan hal ini jika keadaan terpakai. Jadi dari segi konsep, apa yang saya mahu mencari depan jika Saya mencari 44? Ya? 

Tepat sekali, saya ingin mencari kanak-kanak itu kiri, atau sub-pokok kiri gambar ini. Dan sebenarnya, saya melalui gambar di bawah ini hanya untuk seketika, kerana Saya tidak boleh calar ini keluar. Jika saya bermula di sini pada 55 dan Saya tahu bahawa nilai 44 Saya sedang mencari adalah untuk kiri, ia adalah jenis daripada seperti mengoyak buku telefon di separuh atau mengoyak pokok pada separuh. Saya tidak lagi perlu mengambil berat tentang keseluruhan separuh ini pokok itu. Dan lagi, ingin tahu dari segi struktur, perkara ini di sini bahawa bermula dengan 33, itu sendiri adalah pokok carian binari. Saya berkata perkataan rekursi sebelum ini kerana sesungguhnya ini adalah struktur data yang mengikut definisi adalah rekursif. Anda mungkin mempunyai pokok yang ini besar, tetapi setiap seorang daripada anak-anak mereka mewakili pokok hanya sedikit lebih kecil. Sebaliknya ia menjadi datuk atau nenek, kini ia hanya ibu or-- Saya tidak boleh tidak iaitu- ibu atau ayah, yang akan menjadi pelik. Sebaliknya kedua-dua kanak-kanak terdapat akan menjadi seperti abang dan adik-beradik. Generasi baru pokok keluarga. Tetapi dari segi struktur, ia adalah idea yang sama. Dan ternyata saya mempunyai fungsi yang yang aku boleh gelintaran perduaan pokok. Ia dipanggil carian. Saya mencari N di pokok panah kiri lain jika N adalah lebih besar daripada nilai bahawa saya kini di. 55 dalam cerita sebentar tadi. Saya mempunyai fungsi yang dipanggil carian bahawa saya boleh hanya lulus N ini dan secara rekursif mencari sub-pokok dan pulangan hanya apa jawapan itu. Lagi yang saya telah mendapat beberapa kes asas akhir di sini. 

Apa halnya akhir? Pokok sama ada null. Nilai saya memuat cari adalah kurang daripada atau lebih besar daripada itu atau sama dengannya. Dan saya boleh katakan sama sama, tetapi secara logik ia bersamaan dengan hanya mengatakan lagi di sini. Jadi benar adalah bagaimana saya mencari sesuatu. Jadi mudah-mudahan ini adalah satu walaupun contoh yang lebih menarik daripada fungsi sigma bodoh kami menjalankan kuliah ke belakang, di mana ia hanya sebagai mudah untuk digunakan gelung untuk mengira semua nombor dari satu N. Di sini dengan struktur data itu sendiri adalah secara rekursif jelas dan secara rekursif dikeluarkan, sekarang kita mempunyai keupayaan untuk menyatakan diri kita sendiri kod itu sendiri adalah rekursif. Jadi ini adalah kod yang tepat sama di sini. 

Jadi apa masalah lain yang kita boleh menyelesaikan? Jadi langkah yang cepat dari pokok hanya untuk seketika. Di sini ialah, berkata, bendera Jerman. Dan ada jelas corak untuk bendera ini. Dan ada banyak bendera di dunia yang adalah semudah ini dari segi warna dan corak mereka. Tetapi menganggap bahawa ini disimpan sebagai GIF atau JPEG, atau bitmap, atau ping, mana-mana format fail grafik yang anda sudah biasa, ada yang kami bermain dengan di PSET4. Ini nampaknya tidak berbaloi untuk menyimpan pixel hitam, hitam piksel, piksel hitam, dot, dot, dot, sejumlah besar piksel hitam untuk scanline pertama, atau berturut-turut, maka sejumlah besar sama, maka sekumpulan keseluruhan daripadanya, dan kemudian sejumlah besar piksel merah, piksel merah, piksel merah, maka keseluruhan sekumpulan piksel kuning, kuning, bukan? 

Ada ketidakcekapan seperti di sini. Bagaimana anda intuitif memampatkan bendera Jerman jika melaksanakannya sebagai fail? Seperti apa maklumat boleh kita tidak mengganggu menyimpan dalam cakera dalam rangka untuk mengurangkan saiz fail kami seperti megabait kepada kilobait, sesuatu lebih kecil? Di mana terletak lebihan yang di sini untuk menjadi nyata? Apa yang anda boleh lakukan? Ya? Tepat sekali. Mengapa tidak bukannya ingat warna setiap piksel darn sama seperti yang anda lakukan dalam PSET4 dengan format fail bitmap, mengapa tidak anda hanya mewakili ruangan paling kiri piksel, misalnya sekumpulan piksel hitam, sekumpulan merah, dan mempunyai banyak kuning, dan kemudian hanya entah bagaimana mengekod idea berulang 100 kali atau mengulangi ini 1000 kali? Di mana 100 atau 1000 adalah hanya integer, supaya anda boleh pergi dengan hanya satu nombor bukannya beratus-ratus atau beribu-ribu piksel tambahan. Dan sesungguhnya, itulah bagaimana kita boleh memampatkan bendera Jerman. Dan Sekarang bagaimana pula dengan bendera Perancis? Dan beberapa jenis kecil latihan mental, yang bendera boleh dimampatkan lanjut mengenai cakera? Bendera Jerman atau Perancis bendera, jika kita mengambil pendekatan itu? Bendera Jerman, kerana ada lebihan lebih mendatar. Dan dengan reka bentuk, banyak fail grafik format memang bekerja sebagai garis imbasan melintang. Mereka boleh bekerja menegak, hanya manusia tahun telah memilih yang lalu bahawa kita akan umumnya memikirkan perkara-perkara berturut-turut oleh baris dan bukannya lajur oleh tiang. Maka sesungguhnya jika kamu untuk melihat fail Saiz bendera Jerman dan Perancis bendera, selagi resolusi adalah sama, lebar yang sama dan tinggi, yang satu ini di sini akan menjadi lebih besar, kerana anda perlu mengulangi diri anda tiga kali. Anda perlu nyatakan biru, ulang diri sendiri, putih, ulang diri, merah, mengulangi diri sendiri. Anda tidak boleh hanya pergi semua jalan ke kanan. Dan sebagai diketepikan, untuk membuat membersihkan mampatan mana-mana, jika ini adalah empat bingkai dari video-- yang anda mungkin ingat bahawa filem atau video umumnya seperti 29 atau 30 bingkai sesaat. Ia seperti sebuah buku flip kecil di mana anda hanya melihat imej, imej, gambar, imej, imej hanya super cepat supaya ia kelihatan seperti pelakon pada skrin bergerak. Berikut adalah lebah keliru pada atas sekumpulan bunga. Dan walaupun ia mungkin sejenis sukar untuk melihat pada pandangan pertama, satu-satunya perkara yang bergerak dalam filem ini adalah lebah. 

Apa yang bodoh tentang menyimpan video yang tidak dimampatkan? Ia adalah jenis satu pembaziran untuk menyimpan video empat imej hampir sama yang berbeza hanya setakat yang mana lebah itu. Anda boleh buang paling maklumat yang dan ingat sahaja, misalnya, bingkai pertama dan rangka yang lalu, kerangka utama jika anda telah pernah mendengar perkataan, dan hanya menyimpan dalam pertengahan di mana lebah itu. Dan anda tidak perlu menyimpan semua merah jambu, dan biru, dan nilai-nilai hijau juga. Jadi ini adalah untuk hanya mengatakan bahawa mampatan di mana-mana. Ia adalah satu teknik kita sering menggunakan atau mengambil mudah hari ini. 

Tetapi bagaimana anda memampatkan teks? Bagaimana anda pergi tentang memampatkan teks? Well, setiap satu daripada watak-watak dalam Ascii adalah salah satu bait, atau lapan bit. Dan itulah jenis bodoh, bukan? Kerana anda mungkin jenis A dan E dan I dan O dan U banyak lebih kerap daripada seperti W atau Q atau Z, bergantung kepada bahasa yang anda menulis pasti. Dan jadi kenapa kita menggunakan lapan bit untuk setiap surat, termasuk kurangnya huruf popular, bukan? Mengapa tidak menggunakan kurang bit untuk huruf super popular, seperti E, perkara yang anda rasa pertama di Wheel of Fortune, dan menggunakan lebih banyak bit untuk huruf kurang popular? Mengapa? Kerana kita hanya akan menggunakan mereka kurang kerap. 

Nah, ternyata bahawa ada mempunyai cubaan dibuat untuk melakukan ini. Dan jika anda ingat dari gred sekolah atau sekolah tinggi, kod Morse. Kod Morse mempunyai titik dan sengkang yang boleh dihantar bersama-sama dawai sebagai bunyi atau isyarat sejenis. Tetapi kod Morse adalah super bersih. Ia adalah jenis sistem binari dalam bahawa anda mempunyai titik atau sengkang. Tetapi jika anda lihat, misalnya, dua titik. Atau jika anda berfikir kembali kepada pengendali yang pergi seperti bip, bip, bip, bip, memukul pencetus sedikit yang menghantar isyarat, jika anda, penerima, menerima dua titik, apa mesej yang anda terima? Benar-benar sewenang-wenangnya. 

I? I? Atau about-- atau saya? Mungkin ia adalah hanya dua kanan E? Jadi ada masalah ini daripada decodability dengan Morse kod, di mana melainkan jika orang menghantar anda mesej sebenarnya berhenti seketika supaya anda boleh menyusun daripada melihat atau mendengar jurang antara huruf, ia tidak mencukupi hanya untuk menghantar aliran sifar dan satu, atau titik dan sengkang, kerana ada kekaburan. E ialah titik tunggal, jadi jika anda melihat dua titik atau mendengar dua titik, mungkin ia dua E atau mungkin ia adalah salah I. Oleh itu, kita memerlukan sistem itu adalah satu sedikit lebih pandai daripada itu. Jadi seorang lelaki bernama Huffman tahun lalu datang dengan betul-betul ini. Oleh itu, kita hanya akan mengambil pandangan yang cepat bagaimana pokok-pokok germane kepada ini. Katakan bahawa ini adalah beberapa mesej bodoh yang anda hendak hantar, terdiri daripada hanya A, B, C D dan E, tetapi ada banyak lebihan di sini. Ia tidak bertujuan untuk menjadi bahasa Inggeris. Ia tidak disulitkan. Ia hanya satu mesej bodoh dengan banyak pengulangan. Jadi, jika anda benar-benar menghitung semua A, B, C, D, dan E, di sini adalah kekerapan. 20% daripada huruf A, 45% daripada huruf adalah E, dan tiga frekuensi lain. Kami dikira di sana secara manual dan hanya melakukan matematik. 

Jadi ia ternyata bahawa Huffman, sedikit masa lalu, menyedari bahawa, anda tahu apa, jika saya mula membina pokok, atau hutan pokok, jika anda akan, seperti berikut, saya boleh melakukan perkara berikut. Saya akan memberikan kepada setiap nod surat-surat yang saya sayang dan saya akan menyimpan di dalam nod yang frekuensi sebagai titik terapung nilai, atau anda boleh menggunakan ia sebagai N, juga, tetapi kita hanya akan menggunakan apungan di sini. Dan algoritma yang beliau mencadangkan ialah anda mengambil hutan ini nod tunggal pokok-pokok, pokok-pokok supaya super pendek, dan anda mula menghubungkan mereka dengan kumpulan baru, ibu bapa baru, jika anda akan. Dan anda melakukan ini dengan memilih dua frekuensi paling kecil pada satu masa. Jadi saya mengambil 10% dan 10%. Saya mewujudkan nod baru. Aku mengajak nod baru 20%. 

Yang dua nod saya menggabungkan seterusnya? Ia sedikit kabur. Jadi ada beberapa kes sudut untuk mempertimbangkan, tetapi untuk menjaga perkara-perkara yang cantik, Saya akan memilih 20% - Saya kini mengabaikan kanak-kanak. Saya akan memilih 20% dan 15% dan menarik dua tepi baru. Dan sekarang yang dua nod saya secara logik bergabung? Abaikan semua kanak-kanak, semua cucu, hanya melihat akar sekarang. Yang dua nod saya mengikat bersama-sama? Point dua dan 0.35. Jadi biarlah saya menarik dua tepi baru. Dan kemudian saya hanya mendapat satu kiri. Jadi di sini adalah pokok. Dan ia telah ditarik sengaja untuk melihat jenis cantik, tetapi notis bahawa tepi mempunyai juga telah dilabel sifar dan satu. Jadi semua tepi kiri adalah sifar sewenang-wenangnya, tetapi konsisten. Semua tepi kanan adalah orang-orang. 

Dan jadi apa Hoffman dicadangkan iaitu, jika anda mahu untuk mewakili B, bukannya mewakili nombor 66 sebagai yang Ascii yang adalah lapan keseluruhan bit, anda tahu apa, hanya kedai corak sifar, sifar, sifar, sifar, kerana itulah jalan yang dari pokok saya, pokok Encik Huffman-kanak, kepada daun dari akar. Jika anda ingin menyimpan E, sebaliknya, tidak menghantar lapan bit yang mewakili E. Sebaliknya, menghantar apa corak bit? One. Dan apa yang baik tentang ini adalah bahawa E adalah surat yang paling popular, dan anda menggunakan kod singkat untuk itu. Seterusnya yang paling popular surat kelihatan seperti ia adalah A. Dan berapa banyak bit dia mencadangkan menggunakan untuk itu? Sifar, satu. 

Dan kerana ia dilaksanakan sebagai pokok ini, buat masa ini biarlah saya menetapkan ada tiada kekaburan dalam Morse kod, kerana semua huruf yang anda mengambil berat tentang adalah pada akhir pinggir ini. Jadi itu hanya salah satu permohonan pokok. Ini is-- dan saya akan melambai tangan saya ini bagaimana anda mungkin melaksanakan ini sebagai struktur C. Kita hanya perlu menggabungkan simbol, seperti char, dan kekerapan dalam kiri dan kanan. Tetapi mari kita lihat dua contoh terakhir yang anda akan mendapatkan cukup akrab dengan selepas kuiz sifar dalam masalah menetapkan lima. 

Jadi ada struktur data dikenali sebagai meja hash. Dan jadual hash adalah jenis sejuk kerana ia mempunyai baldi. Dan andaikan ada empat baldi di sini, hanya empat ruang kosong. Berikut adalah satu set kad, dan di sini adalah kelab, spade, kelab, berlian, kelab, berlian, kelab, berlian, clubs-- jadi ini adalah rawak. Hati, hearts-- jadi saya bucketizing semua input di sini. Dan keperluan jadual hash melihat input anda, dan kemudian memasukkannya ke dalam yang tertentu meletakkan berdasarkan apa yang anda lihat. Ia algoritma. Dan saya menggunakan super yang algoritma visual mudah. Bahagian paling sukar yang merupakan mengingati apa gambar-gambar yang telah. Dan kemudian ada empat jumlah sesuatu. 

Adapun susunan telah semakin meningkat, yang adalah satu perkara yang reka bentuk yang sengaja di sini. Tetapi apa lagi yang mungkin saya lakukan? Jadi sebenarnya di sini kita mempunyai sekumpulan buku peperiksaan sekolah lama. Katakan sekumpulan nama pelajar di sini. Berikut adalah jadual hash yang lebih besar. Daripada empat baldi, Saya telah, katakan 26. Dan kita tidak mahu pergi meminjam 26 perkara-perkara dari luar [? Annenberg?], Jadi di sini adalah lima yang mewakili A hingga Z. Dan jika saya melihat seorang pelajar yang namanya bermula dengan A, Saya akan meletakkan atau kuiz di sana. Jika seseorang yang bermula dengan C, di sana, A-- sebenarnya, tidak mahu berbuat demikian. B pergi di sini. Jadi saya telah mendapat A dan B dan C. Dan sekarang di sini adalah satu lagi pelajar. Tetapi jika jadual hash ini adalah dilaksanakan dengan array, Saya jenis diskrukan pada ketika ini, bukan? Saya jenis perlu meletakkan suatu tempat ini. 

Jadi salah satu cara saya boleh menyelesaikan masalah ini, semua betul, A sibuk, B sibuk, C sibuk. Saya akan memasukkannya ke dalam D. Jadi pada pertama, saya mempunyai akses segera rawak kepada setiap baldi untuk pelajar. Tetapi sekarang ia adalah jenis diturunkan menjadi sesuatu yang linear, kerana jika saya mahu untuk mencari seseorang nama yang bermula dengan A, saya semak di sini. Tetapi jika ini bukan satu-A pelajar saya cari, Saya jenis perlu bermula memeriksa baldi, kerana apa yang saya lakukan adalah jenis linear menyiasat struktur data. Cara yang bodoh untuk mengatakan hanya melihat untuk membuka yang pertama boleh, dan meletakkan sebagai pelan B, boleh dikatakan, atau pelan D dalam kes ini, nilai di lokasi yang sebaliknya. Ini hanyalah supaya jika anda telah mendapat 26 lokasi dan tiada pelajar dengan nama Q atau Z, atau sesuatu seperti bahawa, sekurang-kurangnya anda menggunakan ruang. 

Tetapi kita telah pun melihat lebih penyelesaian yang bijak di sini, bukan? Apa yang akan anda lakukan dan bukannya jika anda mempunyai perlanggaran? Jika dua orang mempunyai nama A, apa yang akan telah lebih yang lebih bijak atau penyelesaian intuitif daripada hanya meletakkan A di mana D sepatutnya? Kenapa saya tidak hanya pergi luar [? Annenberg?], seperti malloc, nod yang lain, meletakkan ia sini, dan kemudian meletakkan bahawa Seorang pelajar di sini. Supaya saya pada dasarnya mempunyai beberapa jenis pelbagai, atau mungkin lebih elegan kerana kami mula melihat senarai berpaut. 

Dan sebagainya jadual hash adalah struktur yang yang boleh kelihatan seperti ini, tetapi yang lebih bijak, anda sesuatu yang dinamakan chaining berasingan, di mana jadual hash cukup hanya adalah pelbagai, setiap yang unsur-unsur bukan nombor, itu sendiri senarai berpaut. Supaya anda mendapat akses super cepat membuat keputusan di mana untuk hash nilai ke. Sama seperti dengan contoh kad, Saya membuat keputusan super cepat. Hati pergi sini, berlian pergi sini. Sama di sini, A pergi sini, D pergi sini, B pergi sini. Jadi super cepat melihat-up, dan jika anda berlaku untuk menghadapi kes perlanggaran di mana anda mempunyai dua orang yang mempunyai nama yang sama, dan kemudian anda hanya mula menghubungkan mereka bersama-sama. Dan mungkin anda menjaga mereka disusun mengikut abjad, mungkin anda tidak. Tetapi sekurang-kurangnya sekarang kita mempunyai dinamisme. Jadi di satu pihak kita ada super cepat masa yang berterusan, dan jenis masa linear terlibat jika ini senarai berkaitan mula mendapat sedikit panjang. 

Jadi ini jenis yang bodoh, tahun jenaka geeky lalu. Pada CS50 hack-a-thon, apabila pelajar mendaftar masuk, beberapa TF atau CA setiap tahun difikirkan ia melucukan untuk bersabar tanda seperti ini, di mana ia hanya bermakna jika nama anda bermula dengan A, pergi dengan cara ini. Jika nama anda bermula dengan B, pergi this-- OK, ia melucukan mungkin kemudian pada semester tersebut. Tetapi ada satu lagi cara untuk berbuat demikian juga. Kembali kepada itu. 

Jadi ada struktur ini. Dan ini adalah terakhir kami struktur untuk hari ini, yang merupakan sesuatu yang dinamakan indone a. T-R-I-E, yang atas sebab tertentu adalah pendek untuk mendapatkan semula, tetapi ia dipanggil indone. Jadi indone adalah pilihan yang menarik amalgam banyak idea-idea ini. Ia adalah satu pokok, yang kita lihat sebelum ini. Ia bukan satu pokok carian binari. Ia adalah pokok dengan apa-apa bilangan kanak-kanak, tetapi setiap daripada kanak-kanak di indone a adalah pelbagai. Pelbagai saiz, katakan, 26 atau mungkin 27 jika anda mahu untuk menyokong nama ditulis dgn tanda penghubung atau koma dalam nama-nama rakyat. 

Dan sebagainya ini adalah struktur data. Dan jika anda melihat dari atas ke bawah, seperti jika anda melihat nod atas ada, M, adalah menunjuk kepada perkara yang paling kiri di sana, yang kemudian A, X, W, E, L, L. Ini hanya satu struktur data yang sewenang-wenangnya ialah menyimpan nama-nama rakyat. Dan Maxwell disimpan dengan hanya mengikuti jalan yang mudah untuk pelbagai untuk pelbagai. Tetapi apa yang menakjubkan tentang indone adalah itu, manakala senarai berpaut dan juga array, yang terbaik kita pernah mendapat adalah masa linear atau masa logaritma mencari seseorang sehingga. Dalam struktur data ini indone, jika struktur data saya mempunyai satu nama di dalamnya dan saya mencari untuk Maxwell, Saya akan mencari dia cukup cepat. Saya hanya mencari M-A-X-W-E-L-L. Jika struktur data ini, sebaliknya, jika N adalah satu juta, jika ada juta nama dalam struktur data ini, Maxwell masih akan menjadi ditemui selepas hanya M-A-X-W-E-L-L langkah. Dan David-- D-A-V-I-D langkah. Dengan kata lain, dengan membina struktur data itu mendapat semua array ini, semua yang diri mereka menyokong capaian rawak, Saya boleh mula melihat ke atas rakyat menamakan menggunakan jumlah masa itulah berkadar dengan tidak jumlah perkara dalam struktur data, seperti satu juta nama yang sedia ada. Jumlah masa yang diperlukan saya untuk mencari M-A-X-W-E-L-L dalam struktur data ini adalah berkadar tidak kepada saiz struktur data, tetapi dengan panjang nama. Dan realistik yang nama-nama kita melihat ke atas tidak pernah akan menjadi gila panjang. Mungkin seseorang mempunyai ciri-ciri 10 nama, 20 nama watak. Ia sudah tentu terhad, bukan? Terdapat manusia di Bumi yang mempunyai nama yang paling lama mungkin, tetapi nama itu adalah pemalar panjang nilai, bukan? Ia tidak berbeza dari segi akal. Jadi dengan cara ini, kami telah mencapai struktur data iaitu masa yang berterusan melihat-up. Ia mengambil beberapa langkah bergantung kepada tempoh input, tetapi bukan bilangan nama dalam struktur data. Jadi, jika kita menggandakan jumlah nama tahun depan daripada satu bilion dua bilion, Penemuan Maxwell akan mengambil nombor yang sama dalam tujuh langkah untuk mencari beliau. Dan dengan itu kita seolah-olah telah dicapai kaedah berpotensi suci kita masa berjalan. 

Jadi beberapa pengumuman yang cepat. Kuiz sifar akan datang. Lebih kepada yang di laman web kursus ini sejak beberapa hari akan datang. Isnin lecture-- itu bercuti di sini di Harvard pada hari Isnin. Ia bukan di New Haven, jadi kami mengambil kelas untuk Haven baru untuk kuliah pada hari Isnin. Semuanya akan difilemkan dan secara langsung seperti biasa, tetapi mari kita berakhir hari ini dengan klip 30 saat dipanggil "Pemikiran Deep" oleh Daven Farnham, yang telah diilhamkan tahun lalu oleh Sabtu Night Live "Pemikiran Deep" oleh Jack Handy, yang kini perlu masuk akal. 

FILEM: Dan kini, "Deep Pemikiran "oleh Daven Farnham. Jadual hash. 

SPEAKER 1: Baiklah, itu sahaja buat masa ini. Kita akan melihat lagi minggu depan. 

DOUG: Untuk melihat ia dalam tindakan. Oleh itu, mari kita lihat pada yang sekarang. Jadi di sini, kita mempunyai pelbagai terisih. 

IAN: Doug, boleh anda pergi ke hadapan dan mulakan semula ini kerana hanya satu saat, sila. Baiklah, kamera rolling, supaya tindakan apabila anda sudah bersedia, Doug, OK? DOUG: Baiklah, jadi apa yang kita ada di sini adalah pelbagai terisih. Dan saya telah berwarna semua unsur-unsur merah untuk menunjukkan bahawa ia adalah, sebenarnya, Unsorted. Jadi ingat bahawa perkara pertama yang kami lakukan adalah kita menyusun separuh meninggalkan array. Kemudian kami menyusun kanan separuh daripada array. Dan ya-da, ya-da, ya-da, kita menggabungkan mereka bersama-sama. Dan kita mempunyai keselesaan dan kemudahan sepenuhnya disusun. Jadi itulah bagaimana bergabung apapun berfungsi. 

IAN: Wah, wah, wah, potong, potong, potong, dipotong. Doug, anda tidak boleh hanya ya-da, ya-da, ya-da, jalan anda melalui jenis merge. 

DOUG: Saya hanya lakukan. Tidak mengapa. Kita baik untuk pergi. Mari kita hanya menyimpan rolling. Jadi anyway, 

IAN: Anda perlu menjelaskan ia lebih sempurna daripada itu. Itu hanya tidak cukup. DOUG: Ian, kita tidak perlu kembali kepada satu. Tidak mengapa. Jadi anyway, jika kita terus dengan merge-- Ian, kami di pertengahan penggambaran. 

IAN: Saya tahu. Dan kita tidak boleh hanya ya-da, ya-da, ya-da, melalui proses keseluruhan. Anda perlu menjelaskan bagaimana kedua-dua pihak mendapat digabungkan bersama-sama. 

DOUG: Tetapi kami telah pun menjelaskan bagaimana sides-- dua 

IAN: Anda baru sahaja ditunjukkan mereka pelbagai merge. DOUG: Mereka tahu proses. Mereka halus. Kami telah pergi ke atasnya sepuluh kali. 

IAN: Anda hanya dilangkau hak ke atasnya. Kita akan kembali kepada salah satu, anda tidak boleh anda ya-da, ya-da ke atasnya. Baiklah, kembali kepada satu. 

DOUG: Saya perlu kembali melalui semua slaid? Tuhan saya. Ia seperti kali keenam, Ian. Tidak mengapa. 

IAN: Baiklah. Anda bersedia? Yang besar. Tindakan.