[MUZIK bermain] DAVID J. MALAN: Baiklah. Ini adalah CS50. Ini adalah lima minggu berterusan, dan kita mempunyai beberapa berita baik dan ada berita buruk. Jadi berita baik ialah CS50 melancarkan Jumaat ini. Jika anda ingin menyertai kami, menuju ke URL yang biasa di sini. Berita yang lebih baik, tidak ada kuliah ini Isnin ke-13 akan datang. Kurang sedikit berita yang lebih baik, kuiz sifar adalah Rabu depan. Maklumat lanjut boleh didapati di URL ini di sini. Dan sejak beberapa hari akan datang kami akan mengisi tempat kosong berkaitan dengan bilik-bilik bahawa kita akan terpelihara. Berita yang lebih baik adalah bahawa ada akan menjadi kajian kursus seluruh sesi akan datang Isnin petang. Tunggu untuk kursus ini laman web untuk lokasi dan butiran. Bahagian, walaupun ia adalah satu bercuti, juga akan bertemu juga. Berita terbaik, kuliah Jumaat depan. Jadi ini adalah satu tradisi kita mempunyai, seperti sukatan pelajaran. Just-- ia akan menjadi luar biasa. Anda akan melihat perkara-perkara seperti struktur data pemalar masa dan jadual hash dan pokok-pokok dan cuba. Dan kita akan bercakap mengenai masalah hari jadi. A sejumlah besar barangan menanti Jumaat depan. OK. Bagaimanapun. Jadi ingat bahawa kita telah memberi tumpuan kepada gambar ini daripada apa yang di dalam memori komputer kita. Jadi memori atau RAM adalah di mana program-program wujud semasa anda berjalan mereka. Jika anda klik dua kali satu icon untuk menjalankan beberapa program atau klik dua kali satu icon untuk membuka beberapa fail, ia dimuatkan dari keras anda memandu atau pemacu keadaan pepejal ke dalam RAM, Random Access Memory, di mana ia hidup sehingga kuasa terpadam, penutup komputer riba ditutup, atau anda berhenti program ini. 

Sekarang memori itu, daripada yang anda mungkin mempunyai 1 gigabyte hari ini, 2 gigabait, malah banyak lagi, biasanya diletakkan untuk program tertentu dalam jenis ini segi empat tepat model konsep mana kita mempunyai stack di bahagian bawah dan mempunyai banyak barangan lain di bahagian atas. Perkara di bahagian paling atas kita lihat pada gambar ini sebelum ini tetapi tidak pernah bercakap tentang adalah segmen teks yang kononnya. Segmen teks adalah cara yang mewah mengatakan sifar dan orang-orang yang mengarang program sebenar anda disusun. 

Oleh itu, apabila anda klik dua kali Microsoft Word pada Mac atau PC anda, atau apabila anda menjalankan dot mengurangkan Mario pada Komputer Linux di tetingkap terminal anda, sifar dan orang-orang yang mendirikan Perkataan atau Mario disimpan sementara dalam RAM komputer anda dalam apa yang dikenali sebagai segmen teks untuk sesuatu program. Di bawah yang pergi dimulakan dan data tidak diisytiharkan. Ini adalah barangan seperti pembolehubah global, bahawa kami telah tidak digunakan banyak, tetapi kadang-kadang kita kena mempunyai pembolehubah global atau statik tali yang ditakrifkan adalah keras berkod kata-kata seperti "hello" yang tidak diambil daripada pengguna yang keras berkod ke dalam program anda. 

Sekarang, ke bawah di bahagian bawah kita mempunyai timbunan yang dipanggil. Dan tindanan, setakat ini, kita telah menggunakan untuk apa jenis tujuan? Apa yang tindanan telah digunakan untuk? Yeah? 

PENONTON: Fungsi. 

DAVID J. MALAN: Untuk fungsi? Dalam apa rasa untuk fungsi? 

PENONTON: Apabila anda memanggil fungsi, yang hujah-hujah yang disalin ke dalam tindanan. 

DAVID J. MALAN: Tepat sekali. Apabila anda memanggil fungsi, yang hujah-hujah yang disalin ke dalam tindanan. Jadi mana-mana X atau Y atau A atau B bahawa anda lulus ke fungsi buat sementara waktu memakai timbunan yang dipanggil, seperti salah satu daripada Annenberg dulang dewan makan, dan juga perkara-perkara seperti pembolehubah tempatan. Jika fungsi foo atau swap anda fungsi mempunyai pembolehubah tempatan, seperti suhu, kedua-dua berakhir pada tindanan. Sekarang, kita tidak akan bercakap terlalu banyak tentang mereka, tetapi ini pembolehubah persekitaran di bahagian bawah yang kita lihat tadi apabila Saya futzing di papan kekunci satu hari dan saya mula mengakses perkara seperti argv 100 atau argv 1,000, hanya elements-- saya terlupa yang numbers-- tetapi tidak sepatutnya diakses oleh saya. Kami mula melihat beberapa Simbol funky pada skrin. Mereka itulah yang dipanggil pembolehubah persekitaran seperti tetapan global untuk saya program atau komputer saya, tidak tidak berkaitan dengan baru-baru ini bug yang kita dibincangkan, Shellshock, itu menjadi yang melanda cukup beberapa komputer. 

Sekarang akhir sekali, tumpuan hari ini kita akhirnya akan berada di timbunan itu. Ini merupakan satu lagi sebahagian daripada ingatan. Dan pada dasarnya semua ini ingatan adalah barangan yang sama. Ia perkakasan yang sama. Kami hanya semacam merawat kelompok yang berbeza daripada bait untuk tujuan yang berlainan. Timbunan itu juga akan menjadi di mana pembolehubah dan memori yang anda meminta daripada sistem operasi disimpan buat sementara waktu. 

Tetapi ada jenis masalah di sini, kerana gambar bermakna. Kami jenis mempunyai dua kapal akan berlanggar. Kerana seperti anda menggunakan lebih dan lebih tepi, dan seperti yang kita lihat hari ini seterusnya, kerana anda menggunakan lebih banyak dan lebih daripada timbunan, sesungguhnya perkara-perkara buruk mungkin berlaku. Dan sesungguhnya, kita boleh menyebabkan bahawa sengaja atau tidak sengaja. Jadi cliffhanger yang lalu masa adalah program ini, yang tidak memenuhi mana-mana fungsi tujuan selain daripada untuk menunjukkan bagaimana anda sebagai lelaki yang tidak baik sebenarnya boleh mengambil kelebihan pepijat dalam program seseorang dan mengambil alih program ataupun sistem komputer keseluruhan atau pelayan. Jadi hanya untuk pandangan secara ringkas, anda notis utama yang di bahagian bawah mengambil dalam baris arahan hujah, seperti argv. Dan ia mempunyai panggilan kepada fungsi f, asasnya fungsi bernama dipanggil f, dan ia lulus dalam argv [1]. 

Jadi apa sahaja perkataan jenis pengguna dalam sekurang- segera selepas nama ini program ini, dan kemudian fungsi ini sewenang-wenangnya sehingga atas, f, mengambil dalam tali, AKA char *, seperti yang kita telah mula berbincang, dan ia hanya panggilan "bar." Tetapi kita boleh memanggilnya apa-apa. Dan kemudian ia menyatakan, di dalam f, pelbagai watak dipanggil c-- 12 aksara tersebut. 

Kini, dengan kisah yang saya memberitahu masa yang lalu, di mana dalam ingatan adalah c, atau orang-orang 12 aksara akan berakhir? Hanya untuk jelas. Yeah? 

PENONTON: Pada tindanan. 

DAVID J. MALAN: Pada tindanan. Jadi c adalah pembolehubah tempatan. Kami meminta 12 aksara atau 12 bait. Mereka akan berakhir pada timbunan yang dipanggil. Kini akhirnya adalah fungsi lain ini itu sebenarnya cukup berguna, tetapi kita tidak benar-benar digunakan itu diri kita sendiri, strncopy. Ini bermakna tali menyalin, tetapi hanya n huruf, n aksara. Jadi n aksara akan disalin dari bar ke dalam c. Dan berapa banyak? Panjang bar. Jadi dalam erti kata lain, yang satu baris, strncopy, akan menyalin berkesan ke bar di c. 

Sekarang, hanya untuk jenis menjangka moral cerita ini, apa yang berpotensi bermasalah di sini? Walaupun kami memeriksa panjang bar dan lulus ke strncopy, apa yang usus anda memberitahu anda adalah masih dipecahkan mengenai program ini? Yeah? 

PENONTON: Tidak termasuk ruang untuk watak null. DAVID J. MALAN: Tidak termasuk ruang untuk watak null. Berpotensi, tidak seperti di amalan masa lalu kita tidak walaupun mempunyai begitu banyak sebagai campur 1 untuk menempatkan bahawa watak null. Tetapi ia lebih teruk daripada itu. Apa lagi yang kita gagal lakukan? Yeah? 

PENONTON: [didengar] DAVID J. MALAN: Perfect. Kami telah keras berkod 12 cukup sewenang-wenangnya. Yang tidak begitu banyak yang masalah, tetapi hakikatnya bahawa kita tidak memeriksa jika panjang bar adalah kurang daripada 12, di mana ia akan menjadi selamat untuk meletakkan ia ke dalam ingatan c dipanggil bahawa kami telah diperuntukkan. Malah, jika bar adalah seperti 20 aksara, fungsi ini kelihatan menyalin 20 aksara dari bar ke dalam c, dengan itu mengambil sekurang-kurangnya 8 bytes bahawa ia tidak harus. Itulah implikasi di sini. 

Jadi ringkasnya program, patah. Tidak apa-apa masalah besar. Mungkin anda mendapat kesalahan segmentasi. Kami semua mempunyai pepijat dalam program. Kita semua mungkin mempunyai pepijat dalam program-program sekarang. Tetapi apa yang implikasi? Nah, di sini adalah versi yang dizum dalam daripada bahawa gambar memori komputer saya. Ini adalah bahagian bawah timbunan saya. Dan sesungguhnya, di bahagian paling bawah adalah apa yang dipanggil timbunan rutin ibu bapa, cara mewah mengatakan itu utama. Supaya sesiapa yang dipanggil fungsi f yang kita bercakap tentang. Jadi ini adalah bahagian bawah tindanan. Alamat kembali adalah sesuatu yang baru. Ia sentiasa berada di sana, sentiasa di dalam gambar itu. Kami tidak pernah menarik perhatian kepadanya. Kerana ia ternyata cara c kerja-kerja adalah bahawa apabila satu fungsi panggilan yang lain, tidak sahaja hujah-hujah dengan fungsi dapat ditolak ke tepi, bukan sahaja melakukan tempatan fungsi ini pembolehubah dapat ditolak ke tepi, sesuatu yang dipanggil alamat kembali juga mendapat diletakkan ke dalam tindanan. Secara khusus, jika panggilan utama foo, yang utama alamat sendiri dalam ingatan, lembu sesuatu, berkesan mendapat meletakkan ke dalam tindanan supaya apabila f dilakukan menyempurnakannya tahu di mana untuk melompat kembali ke dalam teks segmen untuk terus melaksanakan. 

Jadi, jika kita di sini dari segi konsep, dalam utama, kemudian f mendapat dipanggil. Bagaimana f tahu yang dengan kawalan tangan kembali? Nah, ini sedikit nota singkat yang berwarna merah di sini, dipanggil alamat kembali, ia hanya cek, apa yang alamat kembali? Oh, saya melompat kembali ke utama di sini. Dan itu sedikit daripada melampaui batas satu, kerana sifar dan orang-orang utama adalah untuk teknikal di sini dalam segmen teknologi. Tetapi itu idea. f hanya perlu tahu apa yang di mana kawalan akhirnya kembali. 

Tetapi cara komputer telah lama diletakkan perkara seperti pembolehubah tempatan dan hujah-hujah seperti ini. Jadi di bahagian atas gambar ini di biru bingkai tindanan untuk f, sehingga semua memori yang f khusus adalah dengan menggunakan. Jadi dengan itu, notis yang bar adalah dalam gambar ini. Bar adalah hujahnya. Dan kita mendakwa hujah untuk fungsi mendapatkan ditolak ke dalam tindanan. Dan c, sudah tentu, adalah juga di dalam gambar ini. 

Dan hanya untuk tujuan notasi, notis di bahagian atas sudut kiri sebelah adalah apa yang akan menjadi c kurungan 0 dan kemudian sedikit ke bawah ke kanan adalah c kurungan 11. Jadi dalam erti kata lain, anda boleh bayangkan bahawa ada grid bytes di sana, pertama yang kiri atas, bahagian bawah yang adalah yang terakhir dari orang-orang 12 bait. 

Tetapi sekarang cuba untuk maju pantas. Apa yang akan berlaku jika kita lulus di bar tali itu lebih lama daripada c? Dan kami tidak memeriksa jika ia memang lebih lama daripada 12. Bahagian manakah gambar ini akan mendapatkan ditulis ganti dengan bait 0, 1, 2, 3, dot dot dot, 11, dan kemudian buruk, 12, 13 hingga 19? Apa yang akan berlaku di sini, jika anda membuat kesimpulan dari pesanan yang c kurungan 0 adalah di atas dan c pendakap 11 adalah semacam turun ke kanan? Yeah? 

PENONTON: Nah, ia akan untuk menulis semula bar char *. 

DAVID J. MALAN: Ya, ia kelihatan seperti anda akan menulis ganti * bar char. Dan lebih teruk lagi, jika anda menghantar dalam benar-benar panjang rentetan, anda mungkin menulis ganti apa? Alamat balasan. Yang sekali lagi mereka adalah seperti yang nota singkat untuk memberitahu program di mana untuk kembali ke apabila f dilakukan dipanggil. 

Jadi apa yang orang jahat biasanya melakukan adalah jika mereka mencari satu program yang bahawa mereka ingin tahu sama ada adalah eksploitasi, kereta dalam apa-apa cara yang bahawa dia boleh mengambil kelebihan pepijat itu, biasanya mereka tidak mendapat hak ini kali pertama. Mereka hanya mula menghantar, misalnya, tali rawak ke dalam program anda, sama ada di papan kekunci, atau terus-terang mereka mungkin menulis program kecil hanya secara automatik menjana tali, dan mula terhantuk pada program anda dengan menghantar banyak input yang berbeza di panjang yang berbeza. 

Sebaik sahaja crash program anda, itulah satu perkara yang menakjubkan. Kerana ia bermakna dia atau dia telah menemui apa yang mungkin memang pepijat. Dan kemudian mereka boleh mendapatkan lebih banyak pandai dan mula memberi tumpuan lebih sempit bagaimana untuk mengeksploitasi pepijat itu. Khususnya, apa yang dia mungkin lakukan adalah menghantar, dalam kes ini, hello. Tiada masalah besar. Ia rentetan itu cukup pendek. Tetapi bagaimana jika dia menghantar, dan kami akan umum sebagai, serangan code-- jadi sifar dan orang-orang yang melakukan perkara-perkara seperti rm-rf, yang mengeluarkan segala-galanya dari cakera keras atau menghantar spam atau entah bagaimana menyerang mesin? 

Jadi, jika setiap satu daripada huruf A hanya mewakili, dari segi konsep, serangan, serangan, serangan, serangan, beberapa kod buruk bahawa orang lain telah menulis, tetapi jika orang yang bijak bukan sahaja merangkumi semua dari orang-rm-RFS, tetapi juga mempunyai nya beberapa bait lepas menjadi nombor yang sepadan ke alamat beliau atau kod serangan sendiri bahawa dia meninggal dalam hanya dengan menyediakan ia pada yang cepat, anda berkesan boleh menipu komputer ke perasan apabila f dilakukan melaksanakan, oh, sudah tiba masanya bagi saya untuk melompat kembali ke alamat kembali merah. Tetapi kerana dia mempunyai entah bagaimana bertindan bahawa alamat kembali dengan nombor mereka sendiri, dan mereka bijak telah dikonfigurasikan yang nombor untuk merujuk, kerana anda lihat di bahagian atas super sudut kiri sebelah sana, alamat sebenar dalam komputer ini memori beberapa kod serangan mereka, lelaki yang tidak baik boleh menipu komputer dalam melaksanakan kod sendiri. 

Dan kod yang, sekali lagi, boleh jadi apa sahaja. Ia biasanya dipanggil kod shell, yang hanya cara untuk mengatakan bahawa ia bukan biasanya sesuatu yang mudah seperti rm-rf. Ini sebenarnya sesuatu seperti Bash, atau program sebenar yang memberikan beliau atau kawalan perancangan beliau untuk melaksanakan apa sahaja yang mereka mahu. Jadi ringkasnya, ini semua berasal dari fakta mudah bahawa bug ini tidak terlibat memeriksa sempadan array anda. Dan kerana cara komputer kerja adalah bahawa mereka menggunakan tindanan dari berkesan dari segi konsep, bawah pada, tetapi kemudian unsur-unsur anda menolak ke dalam tindanan berkembang atas ke bawah, ini adalah sangat bermasalah. Kini, ada cara untuk bekerja di sekitar ini. Dan terus-terang, terdapat bahasa dengan yang bekerja di sekitar ini. Java adalah imun, misalnya, dengan isu ini khususnya. Oleh kerana mereka tidak memberikan petunjuk. Mereka tidak memberikan alamat memori langsung. Jadi dengan kuasa ini bahawa kita mempunyai menyentuh apa-apa dalam memori kami mahu datang, diakui, risiko yang besar. 

Jadi memerhatikan keluar. Jika, terus-terang, pada bulan-bulan atau tahun akan datang, bila-bila masa anda membaca tentang beberapa eksploitasi program atau pelayan, jika anda pernah melihat tanda-tanda bahawa sesuatu seperti serangan buffer overflow, atau timbunan limpahan adalah jenis lain serangan, sama dalam semangat, sebanyak memberi inspirasi kepada laman web ini menamakan, jika anda tahu, itu semua bercakap tentang hanya melimpah saiz beberapa watak pelbagai atau beberapa pelbagai amnya. Apa-apa soalan, maka, pada ini? Jangan cuba ini di rumah. 

Baiklah. Jadi malloc setakat ini baru kami rakan dalam kita dapat memperuntukkan memori bahawa kita tidak semestinya kenal memajukan yang kita mahu jadi kami tidak mempunyai untuk kod keras ke kami nombor program seperti 12. Apabila pengguna memberitahu kita berapa banyak data dia mahu input, kita boleh malloc bahawa memori banyak. 

Jadi malloc ternyata, kepada sejauh mana kita telah menggunakannya, jelas masa lalu, dan kemudian kalian telah menggunakannya untuk getstring tidak sedar untuk beberapa minggu, kesemua memori malloc ini datang dari timbunan itu kononnya. Dan ini adalah mengapa getstring, misalnya, boleh memperuntukkan memori dinamik tanpa mengetahui apa yang anda akan menaip terlebih dahulu, tangan anda kembali pointer ke ingatan itu, dan memori yang masih milik anda simpan, walaupun selepas getstring pulangan. Kerana ingat selepas semua bahawa stack sentiasa naik dan turun, naik dan turun. Dan sebaik sahaja ia pergi ke bawah, ini bermakna apa-apa memori fungsi ini digunakan sekiranya tidak digunakan oleh orang lain. Ia nilai-nilai sampah sekarang. 

Tetapi timbunan itu di sini. Dan apa yang baik tentang malloc ialah apabila malloc memperuntukkan memori di sini, ia tidak memberi kesan, untuk kebanyakan keadaan, oleh tindanan. Dan apa-apa fungsi boleh mengakses memori yang telah malloc'd, walaupun oleh fungsi seperti getstring, walaupun selepas ia dikembalikan. 

Sekarang, akas bagi malloc adalah percuma. Dan sesungguhnya, peraturan yang anda perlu mula mengguna pakai apa-apa, mana-mana, bila-bila masa anda menggunakan malloc anda sendiri mesti menggunakan percuma, akhirnya, pada penunjuk yang sama. Selama ini kami telah menulis kereta, kod kereta, kerana banyak sebab. Tetapi salah satu yang telah menggunakan perpustakaan CS50, yang itu sendiri adalah sengaja kereta, kebocoran memori. Bila-bila masa anda dipanggil getstring sejak beberapa minggu yang lalu kami meminta operasi sistem, Linux, untuk ingatan. Dan anda tidak pernah sekali diberikan kembali. Dan ini tidak, dalam amalan, sesuatu yang baik. 

Dan Valgrind, salah satu alat diperkenalkan pada Serangga 4, adalah semua tentang membantu anda kini mendapati pepijat seperti itu. Tetapi bersyukur untuk Serangga 4 anda tidak perlu untuk menggunakan perpustakaan CS50 atau getstring. Jadi apa-apa bug yang berkaitan dengan ingatan adalah akhirnya akan menjadi anda sendiri. 

Jadi malloc adalah lebih daripada hanya sesuai bagi maksud ini. Kita boleh sebenarnya kini menyelesaikan masalah berbeza, dan asasnya menyelesaikan masalah yang lebih berkesan seperti janji minggu sifar. Setakat ini adalah paling seksi yang struktur data kami mempunyai. Dan oleh struktur data saya hanya bermakna cara memori konsepnya, dengan cara yang melampaui hanya mengatakan, ini adalah int, ini adalah char a. Kita boleh mula perkara kelompok bersama-sama. 

Jadi array kelihatan seperti ini. Dan apa yang penting dalam kira-kira array adalah bahawa ia memberi anda back-to-back ketulan memori, setiap yang akan menjadi jenis yang sama, int, int, int, int, char atau, char, char, char. Tetapi ada beberapa kelemahan. Ini misalnya, adalah pelbagai saiz enam. Katakan anda mengisi pelbagai ini dengan enam nombor dan kemudian, atas apa jua sebab, pengguna anda mahu memberikan anda beberapa ketujuh. Di mana anda meletakkannya? 

Apakah penyelesaian jika anda mempunyai mencipta array pada timbunan, misalnya, hanya dengan minggu dua notasi yang kami memperkenalkan, kurungan persegi dengan beberapa di dalam? Nah, anda telah mendapat enam nombor dalam kotak-kotak. Apa yang akan menjadi naluri anda? Di mana anda akan mahu untuk meletakkan ia? 

PENONTON: [didengar] 

DAVID J. MALAN: Maaf? 

PENONTON: Letakkan ia pada akhirnya. 

DAVID J. MALAN: Letakkan ia pada akhirnya. Jadi, ke kanan, di luar kotak ini. Yang akan menjadi baik, tetapi ia ternyata anda tidak boleh berbuat demikian. Kerana jika anda tidak meminta untuk sebahagian ini ingatan, ia boleh menjadi secara kebetulan bahawa ini sedang digunakan oleh beberapa pemboleh ubah lain sama sekali. Fikirkan kembali seminggu atau jadi apabila kita meletakkan keluar Zamyla dan Davin dan Gabe itu nama-nama dalam ingatan. Mereka benar-benar kembali ke belakang ke belakang. Oleh itu, kita tidak boleh semestinya mempercayai bahawa apa sahaja yang di sini boleh didapati dengan saya untuk digunakan. 

Jadi apa lagi yang boleh anda lakukan? Nah, sekali anda menyedari memerlukan pelbagai saiz tujuh, anda hanya boleh membuat pelbagai saiz tujuh kemudian gunakan untuk gelung atau gelung sementara, menyalinnya ke dalam array baru, dan kemudian entah bagaimana hanya menghapuskan array ini atau hanya berhenti menggunakannya. Tetapi itu bukan terutamanya cekap. Pendek kata, tatasusunan jangan biarkan anda secara dinamik mengubah saiz. 

Maka pada satu tangan anda akses rawak, yang luar biasa. Kerana ia membolehkan kita melakukan perkara-perkara seperti pecah dan, carian binari, semua yang kita kena bercakap pada skrin di sini. Tetapi anda mengecat diri anda ke satu sudut. Sebaik sahaja anda melanda akhir array anda, anda perlu melakukan yang sangat operasi mahal atau menulis sejumlah besar kod kini menangani masalah itu. 

Jadi apa jika sebaliknya kita mempunyai sesuatu yang dinamakan senarai, atau senarai dikaitkan khususnya? Bagaimana jika daripada harus segi empat tepat belakang untuk kembali ke belakang, kita mempunyai segi empat tepat yang meninggalkan sedikit sedikit bilik hal bergoyang di antara mereka? Dan walaupun saya telah disediakan ini gambar atau disesuaikan gambar ini dari salah satu daripada teks di sini untuk kembali ke kembali ke belakang sangat teratur, pada hakikatnya, salah satu segi empat tepat boleh di sini dalam ingatan. Salah seorang daripada mereka boleh di sini. Salah seorang daripada mereka boleh di sini, di sini, dan sebagainya. 

Tetapi bagaimana jika kita menarik, dalam kes ini, anak panah yang entah bagaimana menghubungkan ini segi empat tepat bersama-sama? Sesungguhnya, yang kita lihat teknikal penjelmaan anak panah. Apa yang telah kita baru-baru ini digunakan dalam hari itu, di bawah hood, mewakili anak panah? Penunjuk A, bukan? 

Jadi apa jika, bukannya hanya menyimpan nombor, seperti 9, 17, 22, 26, 34, bagaimana jika kita tidak disimpan hanya sebilangan tetapi penunjuk di sebelah setiap nombor itu? Supaya sama seperti anda akan benang yang jarum melalui sejumlah besar kain, perkara yang entah bagaimana mengikat bersama-sama, juga boleh kami dengan petunjuk, sebagai dijelmakan oleh anak panah di sini, jenis menenun bersama-sama segi empat tepat ini individu dengan berkesan menggunakan penunjuk di sebelah setiap nombor yang menunjuk ke beberapa nombor yang akan datang, yang menunjuk kepada, seterusnya, beberapa nombor yang akan datang? Jadi dalam erti kata lain, apa yang jika kita benar-benar mahu untuk melaksanakan sesuatu seperti ini? Baik malangnya, segi empat tepat ini, sekurang-kurangnya satu dengan 9, 17, 22, dan sebagainya, ini tidak lagi dataran yang bagus dengan nombor tunggal. Bahagian bawah, segi empat tepat di bawah 9, misalnya, mewakili apa yang perlu menjadi penunjuk, 32 bit. Kini, saya tidak lagi sedar apa-apa jenis data dalam C yang memberikan anda bukan sahaja int satu tetapi penunjuk sama sekali. 

Jadi apa penyelesaian jika kita mahu mencipta jawapan kita sendiri untuk ini? Yeah? 

PENONTON: [didengar] 

DAVID J. MALAN: Apakah itu? 

PENONTON: struktur baru. 

DAVID J. MALAN: Yeah, jadi mengapa tidak kita mencipta struktur baru, atau C, struct yang? Kami telah melihat sebelum structs, jika secara ringkas, di mana kita diuruskan dengan struktur pelajar seperti ini, yang mempunyai nama dan sebuah rumah. Dalam Serangga 3 pelarian anda menggunakan keseluruhan sekumpulan GRect structs-- dan GOvals Stanford yang diwujudkan untuk maklumat kelompok bersama-sama. Jadi apa jika kita mengambil idea ini sama kata kunci "typedef" dan "struct," dan kemudian beberapa barangan tertentu pelajar, dan berkembang ini kepada yang berikut: typedef struct node-- dan simpulan adalah hanya sains komputer yang sangat generik jangka sesuatu dalam struktur data, bekas dalam struktur data. A nod saya menuntut akan mempunyai n int, benar-benar mudah, dan kemudian sedikit lebih cryptically, barisan kedua ini, nod struct * seterusnya. Tetapi dari segi kurang teknikal, apa ialah baris kedua kod di dalam pendakap kerinting? Yeah? 

PENONTON: [didengar] DAVID J. MALAN: A penunjuk kepada nod yang lain. Jadi diakui, sintaksis sedikit samar. Tetapi jika anda membacanya secara literal, seterusnya adalah nama pembolehubah. Apakah jenis data? Ia satu verbose sedikit masa ini, tetapi ia dari jenis nod struct *. Bila-bila masa yang kita lihat sesuatu bintang, yang bermakna ia penunjuk dengan jenis data. Jadi seterusnya adalah nampaknya penunjuk kepada nod struct. 

Kini, apa yang nod struct? Nah, notis anda melihat orang-orang perkataan yang sama di sebelah kanan atas. Dan sesungguhnya, anda juga melihat perkataan "Nod" turun di sini di sebelah kiri bahagian bawah. Dan ini adalah benar-benar hanya satu kemudahan. Perhatikan bahawa dalam definisi pelajar kita ada perkataan "pelajar" hanya sekali. Dan itu kerana pelajar objek tidak sendiri rujukan. Tiada apa-apa bahagian dalam pelajar yang perlu untuk menunjukkan kepada pelajar lain, persay. Yang akan menjadi semacam pelik dalam dunia sebenar. 

Tetapi dengan nod dalam dikaitkan senarai, kita mahu nod menjadi rujukan kepada objek yang sama. Dan sebagainya notis perubahan di sini tidak hanya apa yang di dalam pendakap kerinting. Tetapi kita menambah perkataan "nod" di bahagian atas dan juga menambah ia ke bawah sebagai ganti "pelajar." Dan ini hanya butiran teknikal supaya, sekali lagi, struktur data anda boleh sendiri rujukan, supaya nod boleh menunjukkan kepada yang lain nod tersebut. 

Jadi apa ini akhirnya akan bermakna untuk kita? Nah, satu, barangan ini di dalam adalah kandungan nod kami. Perkara ini di sini, kanan atas, adalah hanya supaya yang, sekali lagi, kita boleh merujuk kepada diri kita sendiri. Dan kemudian barangan yang paling luar, walaupun nod adalah satu istilah yang baru, mungkin, ianya masih menjadi sama seperti pelajar dan apa yang adalah di bawah hud di SPL. 

Jadi, jika kita ingin memulakan melaksanakan senarai ini dikaitkan, bagaimana mungkin kita menterjemahkan sesuatu seperti ini untuk kod? Nah, mari kita melihat contoh program yang sebenarnya menggunakan senarai berpaut. Antara kod pengedaran hari ini adalah program yang dikenali sebagai Senarai Zero. Dan sekiranya saya ini saya mencipta super yang GUI yang mudah, Antara Muka Pengguna grafik, tetapi ia benar-benar hanya printf. Dan sekarang saya telah memberikan diri saya beberapa menu options-- Padam, Masukkan, Search, dan Traverse. Dan Henti. Ini adalah operasi hanya biasa pada struktur data yang dikenali sebagai senarai link. 

Sekarang, Padam akan memadam nombor daripada senarai. Insert yang akan menambah nombor kepada senarai. Carian akan kelihatan untuk nombor dalam senarai. Dan traverse hanya cara yang mewah mengatakan, berjalan melalui senarai, mencetak, tetapi itu sahaja. Tidak berubah dalam apa-apa cara. 

Jadi mari kita cuba ini. Mari kita pergi ke hadapan dan taip 2. Dan kemudian saya akan memasukkan nombor, katakan 9. Enter. Dan kini program saya hanya diprogramkan untuk berkata, senarai kini 9. Sekarang, jika saya pergi ke depan dan adakah Masukkan sekali lagi, marilah saya pergi ke hadapan dan zum keluar dan taip 17. Sekarang saya adalah senarai 9, kemudian 17. Jika saya memasukkan lagi, mari kita skip satu. Bukan 22, seperti gambar di kita kena telah melihat di sini, saya melompat ke hadapan dan masukkan 26 akan datang. Jadi saya akan menaip 26. Senarai ini adalah seperti yang saya harapkan. Tetapi sekarang, hanya untuk melihat kod ini akan menjadi fleksibel, saya kini Jenis 22, yang sekurang-kurangnya dari segi konsep, jika kita Menyimpan ini disusun, yang memang akan menjadi matlamat lain sekarang, perlu pergi di antara 17 dan 26. Jadi saya tekan Enter. Sesungguhnya, yang bekerja. Dan jadi sekarang biar saya memasukkan lepas, gambar di, 34. 

Baiklah. Jadi buat masa ini biarlah saya menetapkan bahawa Padam dan Traverse dan Cari lakukan, sebenarnya, bekerja. Malah, jika saya menjalankan Cari, mari mencari nombor 22, Enter. Ia menemui 22. Jadi itulah yang ini Senarai program Zero tidak. 

Tetapi apa yang sebenarnya akan pada yang melaksanakan ini? Well, pertama saya mungkin, dan sesungguhnya Saya mempunyai, fail yang dipanggil list0.h. Dan di suatu tempat di sana adalah ini talian, typedef, struct nod, maka saya mempunyai pendakap kerinting saya, int n, dan kemudian struct-- apa definisi? Struct nod seterusnya. Oleh itu, kita perlu bintang. Sekarang teknikal kita masuk ke dalam tabiat melukis di sini. Anda mungkin melihat buku-buku teks dan rujukan dalam talian melakukannya di sana. Ia berfungsi sama. Malah, ini adalah sedikit lebih biasa. Tetapi saya akan konsisten dengan apa yang yang kita lakukan masa lalu dan melakukan ini. Kemudian akhir sekali, saya akan melakukan ini. 

Jadi dalam fail header di suatu tempat, dalam list0.h hari ini adalah definisi struct ini, dan mungkin beberapa barangan lain. Sementara itu di list0c ada akan beberapa perkara. Tetapi kita akan hanya bermula dan tidak selesai ini. List0.h adalah fail saya mahu untuk dimasukkan ke dalam fail C saya. Kemudian pada satu ketika saya akan mempunyai int, utama, tidak sah. Dan kemudian saya akan mempunyai beberapa tugasan di sini. Saya juga akan mempunyai prototaip, seperti tidak sah, carian, int, n, tujuan yang dalam hidup adalah untuk mencari unsur. Dan kemudian turun di sini saya menuntut di kod hari ini, tidak sah, carian, int, n, tidak koma bertitik tetapi pendakap kerinting terbuka. Dan sekarang saya ingin mencari entah bagaimana kepada satu unsur dalam senarai ini. Tetapi kita tidak mempunyai cukup maklumat pada skrin lagi. Saya tidak benar-benar diwakili senarai itu sendiri. Jadi salah satu cara kita boleh melaksanakan senarai dikaitkan dalam program yang adalah saya jenis mahu melakukan sesuatu seperti mengisytiharkan senarai dikaitkan di sini. Untuk memudahkan, saya akan membuat ini dunia, walaupun dalam kita umum tidak perlu melakukan ini terlalu banyak. Tetapi ia akan memudahkan contoh ini. Jadi saya mahu untuk mengisytiharkan senarai berpaut di sini. Sekarang, bagaimana saya boleh berbuat demikian? 

Berikut adalah gambar senarai berpaut. Dan saya tidak benar-benar tahu pada masa ini bagaimana Saya akan pergi kira-kira mewakili begitu banyak perkara dengan hanya satu berubah-ubah dalam ingatan. Tetapi berfikir kembali seketika. Selama ini kita telah mempunyai tali, yang kita kemudian didedahkan sebagai tatasusunan aksara, yang kemudiannya kami diturunkan kepada hanya menjadi penunjuk dengan watak yang pertama dalam pelbagai watak yang yang batal ditamatkan. Jadi dengan logik itu, dan dengan ini jenis gambar pembenihan pemikiran anda, apa yang perlu kita sebenarnya menulis dalam kami kod untuk mewakili senarai berpaut? Berapa banyak maklumat ini kita perlu untuk menangkap kod C, anda akan berkata? Yeah? 

PENONTON: Kita perlu penunjuk kepada nod. DAVID J. MALAN: Satu penunjuk kepada nod. Khususnya, yang nod akan anda naluri adalah untuk memastikan penunjuk ke? 

PENONTON: Nod pertama. 

DAVID J. MALAN: Ya, mungkin hanya pertama. Dan notis itu, yang pertama nod adalah bentuk yang berbeza. Ia hanya separuh saiz struct itu, kerana ia sememangnya hanya penunjuk. Jadi apa yang anda memang boleh lakukan adalah mengisytiharkan senarai dikaitkan dengan menjadi nod Jenis *. Dan mari kita memanggilnya pertama dan memulakan kepada null. Jadi null, sekali lagi, adalah datang ke dalam gambar di sini. Bukan sahaja null digunakan sebagai seperti khas nilai pulangan untuk perkara-perkara seperti getstring dan malloc, batal juga sifar penunjuk, kekurangan penunjuk, jika anda akan. Ia hanya bermakna apa-apa lagi di sini. Sekarang pertama, saya boleh telah dikenali sebagai apa-apa ini. Saya boleh memanggilnya "senarai" atau mana-mana beberapa perkara lain. Tetapi saya memanggil "pertama" supaya ia garisan dengan gambar ini. Jadi seperti rentetan boleh diwakili dengan alamat bait pertama, jadi boleh senarai berpaut. Dan kita akan melihat data lain struktur diwakili dengan hanya satu penunjuk, 32-bit anak panah, menunjuk pada nod yang pertama di dalam struktur. 

Tetapi sekarang mari kita menjangka masalah. Jika saya hanya mengingati dalam program saya alamat nod yang pertama, yang pertama segi empat tepat dalam struktur data ini, apa yang mempunyai yang lebih baik kes itu tentang pelaksanaan seluruh senarai saya? Apakah yang dimaksudkan dengan terperinci penting yang berlaku untuk memastikan ini benar-benar berfungsi? Dan dengan "benar-benar bekerja" Saya bermakna, sama seperti tali, mari kita pergi dari watak pertama nama Davin untuk yang kedua, untuk ketiga, kepada keempat, hingga ke akhir sangat, bagaimana kita tahu apabila kita berada di hujung senarai berpaut yang kelihatan seperti ini? Apabila tiba null. Dan saya telah diwakili seperti ini sebagai seperti kekuatan seorang jurutera elektrik, dengan asas yang kecil simbol, kejayaannya. Tetapi itu hanya bermakna batal dalam kes ini. Anda boleh menarik ia apa-apa bilangan cara, tetapi pengarang ini berlaku untuk menggunakan simbol ini di sini. 

Selagi kita stringing semua nod ini bersama-sama, hanya mengingati di mana yang pertama adalah, selagi seperti yang kita meletakkan simbol khas di nod yang terakhir dalam senarai, dan kami akan menggunakan batal, kerana itulah apa yang kita ada untuk kita, senarai ini selesai. Dan walaupun saya hanya memberi penunjuk kepada elemen pertama, anda, pengaturcara, tentu boleh mengakses seluruh ia. Tetapi mari kita biarkan fikiran anda bersiar-siar sedikit, jika mereka tidak sudah agak wandered-- apa yang akan menjadi masa yang berjalan dari mencari apa-apa dalam senarai ini? Damn, ia adalah O besar n, yang tidak buruk, dalam keadilan. Tetapi ia adalah linear. Kami telah diberikan sehingga apa ciri array dengan bergerak lebih ke arah gambar ini secara dinamik ditenun bersama-sama atau dikaitkan nod? Kami telah diberi Akses rawak. Pelbagai bagus kerana segala sesuatu secara matematik kembali ke belakang untuk kembali ke belakang. Walaupun gambar ini kelihatan cantik, malah walaupun ia kelihatan seperti nod ini adalah baik dijarakkan selain, pada hakikatnya mereka boleh berada di mana sahaja. Ox1, Ox50, Ox123, Ox99, ini nod boleh berada di mana sahaja. Kerana malloc tidak memperuntukkan memori dari timbunan itu, tetapi mana-mana sahaja dalam timbunan itu. Anda tidak semestinya tahu bahawa itu akan kembali ke belakang ke belakang. Dan gambar ini pada hakikatnya ini tidak akan menjadi agak ini cantik. 

Jadi ia akan mengambil sedikit bekerja untuk melaksanakan fungsi ini. Jadi mari kita melaksanakan carian sekarang. Dan kita akan melihat jenis yang cara bijak untuk berbuat demikian. Jadi, jika saya satu fungsi carian dan Saya diberi berubah-ubah, integer n untuk mencari, saya perlu tahu sintaks baru untuk mencari di dalam struktur itu menunjuk kepada, untuk mencari n. Jadi mari kita buat ini. 

Oleh itu saya akan pergi hadapan dan mengisytiharkan nod *. Dan saya akan memanggilnya pointer, hanya dengan konvensyen. Dan saya akan memulakan ia terlebih dahulu. Dan sekarang saya boleh melakukan ini dalam beberapa cara. Tetapi saya akan mengambil pendekatan yang sama. Walaupun pointer tidak sama dengan batal, dan itu sintaks sah. Dan ia hanya bermaksud melakukan yang berikut, jadi selagi anda tidak menghala ke arah apa-apa. Apa yang saya mahu lakukan? 

Jika penunjuk dot n, biarlah saya kembali itu, equals-- sama apa? Apa nilai saya cari? N sebenar yang telah diluluskan pada. Jadi di sini adalah satu lagi ciri C dan banyak bahasa. Walaupun struktur dipanggil nod mempunyai nilai n, benar-benar sah juga mempunyai hujah tempatan atau pembolehubah dipanggil n. Kerana walaupun kita, dengan mata manusia, boleh membezakan n ini mungkin berbeza daripada n ini. Kerana sintaksis adalah berbeza. Anda perlu titik dan penunjuk, manakala yang satu ini tidak mempunyai benda itu. Jadi ini adalah OK. Itulah OK untuk memanggil mereka perkara yang sama. 

Jika saya anda mencari ini, saya akan mahu melakukan sesuatu seperti mengumumkan bahawa kami dapati n. Dan kita akan meninggalkan bahawa sebagai komen atau kod kod pseudo. Yang lain, dan di sini yang bahagian yang menarik, apa yang saya mahu lakukan jika nod semasa tidak mengandungi n bahawa saya mengambil berat tentang? Bagaimana saya mencapai yang berikut? Jika jari saya di masa adalah PTR, dan ia menghala ke arah apa sahaja pertama menghala ke arah, bagaimana saya boleh bergerak jari saya untuk nod seterusnya dalam kod? Nah, apa yang nota singkat yang kami akan mengikuti dalam kes ini? PENONTON: [didengar]. DAVID J. MALAN: Yeah, jadi seterusnya. Jadi, jika saya kembali kepada saya kod sini, sesungguhnya, saya akan pergi ke depan dan berkata penunjuk, yang hanya variable-- sementara ia nama pelik, ptr, tetapi ia seperti temp-- Saya akan set penunjuk sama dengan apa penunjuk is-- dan sekali lagi, ini akan menjadi satu sedikit buggy untuk dot moment-- depan. Dalam erti kata lain, saya akan mengambil saya jari yang yang menunjuk pada nod ini di sini dan saya akan berkata, anda tahu apa, kita lihat pada bidang seterusnya dan bergerak jari anda untuk apa sahaja yang ia menghala ke arah. Dan ini akan ulangi, ulangi, ulangi. Tetapi apabila tidak jari saya berhenti melakukan apa-apa pun? Sebaik sahaja apa garis tendangan kod di? PENONTON: [didengar] DAVID J. MALAN: Jika mata manakala penunjuk tidak sama dengan nol. Pada beberapa titik jari saya akan menghala ke arah null dan saya akan menyedari itulah akhir senarai ini. Sekarang, ini adalah sedikit dusta putih untuk kesederhanaan. Ia ternyata bahawa walaupun kita baru belajar notasi dot ini untuk struktur, penunjuk tidak struct a. ptr adalah apa? Hanya untuk menjadi lebih nitpicky. Ia adalah penunjuk kepada nod. Ia bukan satu nod sendiri. Jika saya tidak mempunyai bintang di sini, penunjuk absolutely-- ia nod. Ini seperti satu minggu pengisytiharan pembolehubah, walaupun perkataan "nod" yang baru. 

Tetapi sebaik sahaja kami memperkenalkan bintang, ia kini merupakan penunjuk kepada nod. Dan malangnya anda tidak boleh menggunakan notasi titik untuk penunjuk. Anda perlu menggunakan anak panah notasi, yang, sungguh menarik, adalah kali pertama mana-mana bahagian sintaksis kelihatan intuitif. Ini benar-benar kelihatan seperti anak panah. Dan itu adalah satu perkara yang baik. Dan turun di sini secara literal kelihatan seperti anak panah. Jadi saya fikir itu la-- yang saya tidak fikir saya lebih-melakukan here-- saya fikir itu sekeping baru yang lalu sintaksis kita akan lihat. Dan bersyukur kerana, ia memang sedikit lebih intuitif. 

Sekarang, untuk anda yang mungkin lebih suka cara lama, anda masih boleh menggunakan notasi titik. Tetapi seperti semalam perbualan, kami pertama perlu ke sana, pergi ke menangani, dan kemudian mengakses padang. Jadi ini juga betul. Dan terus terang, ini adalah sedikit lebih pedantik. Anda benar-benar berkata, dereference penunjuk dan pergi ke sana. Kemudian merebut .n, bidang yang dipanggil n. Tetapi terus-terang, tidak ada yang mahu menaip atau membaca ini. Dan dunia dicipta notasi anak panah, yang adalah bersamaan, sama, ia hanya gula sintaksis. Jadi cara yang mewah untuk mengatakan ini kelihatan lebih baik, atau kelihatan lebih mudah. 

Jadi sekarang saya akan melakukan satu perkara yang lain. Saya akan berkata "break" sekali saya telah mendapati ia jadi saya tidak terus mencari untuk itu. Tetapi ini adalah inti yang daripada fungsi carian. Tetapi ia lebih mudah, dalam akhir, tidak berjalan melalui kod. Ini merupakan pelaksanaan rasmi carian dalam kod pengedaran hari ini. Saya berani mengatakan sisipan yang tidak terutamanya menyeronokkan untuk berjalan melalui visual, juga memadam, walaupun walaupun pada akhir hari mereka mendidih ke agak heuristik mudah. 

Jadi mari kita buat ini. Jika anda akan humor saya di sini, saya membawa sekumpulan bola tekanan. Saya membawa sekumpulan nombor. Dan boleh kita mendapatkan hanya beberapa sukarelawan untuk mewakili 9, 17, 20, 22, 29, dan 34? Jadi pada dasarnya semua orang yang di sini hari ini. Itu adalah satu, dua, tiga, empat, lima, enam orang. Dan saya telah diminta untuk go-- lihat, tidak satu di belakang menimbulkan tangan mereka. OK, satu, dua, tiga, empat, five-- biarlah saya memuatkan balance-- enam. OK, anda enam datang di atas. Kami akan memerlukan orang lain. Kami membawa bola tekanan tambahan. Dan jika anda boleh, untuk hanya seketika, talian diri sehingga hanya seperti gambar ini di sini. 

Baiklah. Mari kita lihat, apa nama anda? 

PENONTON: Andrew. 

DAVID J. MALAN: Andrew, anda bilangan 9. Nice untuk bertemu dengan kamu. Di sini anda pergi. PENONTON: Jen. DAVID J. MALAN: Jen. Daud. Number 17. Ya? 

PENONTON: Saya Julia. 

DAVID J. MALAN: Julia, David. Nombor 20. PENONTON: Kristian. DAVID J. MALAN: Christian, David. Nombor 22. Dan? 

PENONTON: JP. DAVID J. MALAN: JP. Nombor 29. Oleh itu, pergilah ke hadapan dan mendapatkan dalam- Uh oh. Uh oh. Siap sedia. 20. Adakah sesiapa yang mempunyai penanda? PENONTON: Saya ada Sharpie. DAVID J. MALAN: Anda mendapat Sharpie? OK. Dan tidak sesiapa yang mempunyai sehelai kertas? Jimat kuliah. Datang pada. PENONTON: Kami telah mendapat ia. DAVID J. MALAN: Kami mendapat ia? Baiklah, terima kasih. Di sini kita pergi. Adakah ini daripada anda? Anda hanya menyelamatkan hari. Jadi 29. Baiklah. Saya silap eja 29, tetapi OK. Teruskan. Baiklah, saya akan memberikan anda pen anda kembali seketika. Jadi kita mempunyai orang ini di sini. Mari kita mempunyai satu yang lain. Gabe, adakah anda mahu bermain elemen pertama di sini? Kami akan memerlukan anda untuk menunjukkan pada ini orang halus. Jadi 9, 17, 20, 22, semacam 29, dan kemudian 34. Adakah kita kehilangan seseorang? Saya mempunyai 34. Di mana OK did--, yang mahu menjadi 34? OK, datang ke atas, 34. Baiklah, ini akan menjadi berbaloi kemuncak. Apa nama anda? 

PENONTON: Peter. 

DAVID J. MALAN: Peter, datang ke atas sehingga. Baiklah, jadi di sini adalah sejumlah besar nod. Setiap satu daripada anda semua mewakili salah satu segi empat tepat ini. Dan Gabe, sedikit ganjil manusia keluar, mewakili pertama. Jadi penunjuk beliau adalah sedikit lebih kecil pada skrin dari orang lain. Dan dalam kes ini, setiap satu daripada anda meninggalkan tangan akan menunjukkan sama ada ke bawah, dengan itu mewakili batal, jadi hanya ketiadaan penunjuk, atau ia akan menunjuk pada nod yang bersebelahan dengan anda. 

Jadi sekarang jika anda menghiasi kamu seperti gambar di sini, pergi ke depan dan mata di antara satu sama lain, dengan Gabe dalam menunjuk tertentu di bilangan 9 untuk mewakili senarai. OK, dan nombor 34, tangan kiri anda seharusnya hanya akan menghala ke arah lantai. 

OK, jadi ini adalah senarai yang dipautkan. Jadi, ini adalah senario yang berkenaan. Dan sesungguhnya, ini adalah wakil daripada kelas masalah bahawa anda mungkin cuba untuk menyelesaikan dengan kod. Anda mahu akhirnya memasukkan elemen baru ke dalam senarai. Dalam kes ini, kita akan cuba memasukkan bilangan 55. Tetapi ada akan menjadi kes-kes yang berbeza untuk dipertimbangkan. Dan sesungguhnya, ini akan menjadi satu daripada yang besar-gambar bawa pulang di sini, adalah, apakah kes-kes yang berbeza. Apakah berbeza jika syarat atau cawangan yang program anda mungkin mempunyai? 

Nah, nombor yang anda cuba untuk insert, yang kita tahu sekarang menjadi 55, tetapi jika anda tidak tahu terlebih dahulu, saya berani mengatakan jatuh ke dalam sekurang-kurangnya tiga keadaan mungkin. Di mana mungkin elemen baru menjadi? PENONTON: Dan akhir atau pertengahan. DAVID J. MALAN: Pada akhirnya, dalam tengah-tengah, atau pada awal. Jadi saya mendakwa ada sekurang-kurangnya tiga masalah yang kita perlu menyelesaikan. Mari kita memilih apa yang mungkin boleh dikatakan yang paling mudah satu, di mana elemen baru milik pada permulaan. Jadi saya akan mempunyai kod agak seperti mencari, yang saya hanya menulis. Dan saya akan mempunyai ptr, yang Saya akan mewakili sini dengan jari saya, seperti biasa. 

Dan ingat, apa nilai yang kita memulakan ptr ke? Oleh itu, kita dimulakan untuk null mulanya. Tetapi apakah yang kita lakukan sebaik sahaja kami berada di dalam fungsi carian kami? Kami menetapkan ia sama dengan yang pertama, yang tidak bermakna melakukan ini. Jika saya menetapkan ptr sama dengan yang pertama, apa yang perlu tangan saya benar-benar menjadi menghala ke arah? Betul. Jadi jika Gabe dan saya akan menjadi nilai-nilai yang sama di sini, kita perlu kedua-dua titik di nombor 9. 

Jadi ini adalah permulaan cerita kita. Dan sekarang ini hanya terus-terang, walaupun sintaks baru. Dari segi konsep ini hanyalah carian linear. 55 bersamaan dengan 9? Atau sebaliknya, katakan kurang daripada 9. Oleh kerana saya cuba untuk memikirkan di mana untuk meletakkan 55. Kurang daripada 9, kurang daripada 17, kurang daripada 20, kurang daripada 22, kurang daripada 29, kurang daripada 34, tidak. Jadi sekarang kita berada dalam kes salah satu daripada sekurang-kurangnya tiga. 

Jika saya mahu memasukkan 55 di sini, apa yang baris kod keperluan untuk mendapatkan dilaksanakan? Bagaimana gambar ini manusia perlu berubah? Apa yang saya buat dengan tangan kiri saya? Ini perlu batal pada mulanya, kerana saya pada akhir senarai. Dan apa yang sepatutnya berlaku di sini dengan Peter, adakah? Dia jelas akan menunjukkan kepada saya. Jadi saya mendakwa ada sekurang-kurangnya dua baris kod kod sampel dari hari ini perkara yang berlaku untuk melaksanakan ini senario menambah 55 di ekor. Dan boleh saya hop seseorang dan hanya mewakili 55? Baiklah, anda baru 55. 

Jadi sekarang apa yang jika seterusnya senario datang bersama-sama, dan kami mahu memasukkan di bermula atau ketua senarai ini? Dan apa nama, nombor 55? 

PENONTON: Jack. 

DAVID J. MALAN: Jack? OK, baik untuk bertemu dengan kamu. Selamat Datang. Jadi sekarang kita akan memasukkan, katakan, nombor 5. Berikut adalah kes kedua tiga kami datang dengan sebelum. Jadi, jika 5 milik pada permulaan, mari kita lihat bagaimana kita dapati bahawa daripada. Saya memulakan ptr saya penunjuk kepada nombor 9 lagi. Dan saya sedar, oh, 5 adalah kurang dari 9. Jadi menetapkan gambar ini untuk kita. Yang tangan, ini Gabe atau Daud or-- apa nama bilangan 9 ini? 

PENONTON: Jen. 

DAVID J. MALAN: hands-- Jen ini yang tangan kita perlu berubah? OK, jadi Gabe menunjukkan apa sekarang? Pada saya. Saya nod baru. Jadi saya akan hanya jenis daripada langkah di sini untuk melihatnya secara visual. Dan sementara itu apa yang saya menunjukkan bahawa? Masih di mana saya menunjuk. Jadi itu sahaja. Jadi, benar-benar satu baris perbaikan kod isu ini tertentu, ia akan kelihatan. Baiklah, jadi itulah yang baik. Dan seseorang boleh menjadi pemegang tempat selama 5? Marilah naik. Kami akan membawa anda masa depan. 

Baiklah, jadi now-- dan sebagai diketepikan, nama-nama Saya tidak membuat sebutan yang jelas hak sekarang, penunjuk pred, sebelumnya penunjuk dan penunjuk baru, itu hanya nama-nama yang diberikan dalam kod sampel kepada petunjuk atau tangan saya yang yang jenis menunjuk sekitar. Apa nama anda? 

PENONTON: Christine. 

DAVID J. MALAN: Christine. Selamat Datang. Baiklah, jadi mari kita mempertimbangkan kini senario sedikit lebih menjengkelkan, di mana saya mahu memasukkan sesuatu seperti 26 ke dalam ini. 20? Apa? Ini are-- perkara yang baik kita mempunyai pen ini. Baiklah, 20. Jika seseorang boleh mendapatkan satu lagi kertas bersedia, hanya dalam case-- semua betul. Oh, menarik. Nah ini adalah satu contoh daripada pepijat kuliah. OK jadi apa nama anda lagi? PENONTON: Julia. DAVID J. MALAN: Julia, anda boleh pop keluar dan berpura-pura anda tidak hadir? OK, ini tidak pernah berlaku. Terima kasih. Jadi andaikan kita mahu memasukkan Julia ke dalam senarai ini yang berkaitan. Beliau adalah nombor 20. Dan sudah tentu dia akan tergolong di begin-- tidak menunjuk ke arah apa-apa lagi. Jadi tangan anda jenis boleh turun null atau beberapa nilai sampah. Mari kita bercerita cepat. Saya menghala ke arah nombor 5 kali ini. Kemudian saya menyemak 9. Kemudian saya memeriksa 17. Kemudian saya memeriksa 22. Dan saya sedar, aduh, Julia perlu pergi sebelum 22. Jadi apa yang perlu berlaku? Yang tangan perlu berubah? Julia, saya, or-- apa nama anda lagi? 

PENONTON: Kristian. 

DAVID J. MALAN: Kristian atau? 

PENONTON: Andy. 

DAVID J. MALAN: Andy. Kristian atau Andy? Andy perlu menunjuk ke arah? Julia. Baiklah. Jadi Andy, adakah anda mahu untuk menunjukkan pada Julia? Tetapi tunggu satu minit. Dalam cerita ini setakat ini, Saya jenis satu yang bertanggungjawab, dalam erti kata bahawa penunjuk adalah perkara itu bergerak melalui senarai. Kita mungkin mempunyai nama untuk Andy, tetapi tidak ada ubah dikenali sebagai Andy. Satu-satunya pembolehubah lain yang kami ada adalah pertama, siapa yang diwakili oleh Gabe. 

Jadi ini adalah benar-benar mengapa itu ini kita telah tidak diperlukan ini. Tetapi sekarang pada skrin terdapat menyebut lagi penunjuk pred. Jadi biarlah saya menjadi lebih jelas. Jika ini adalah penunjuk, saya mempunyai yang lebih baik mendapatkan sedikit lebih pintar mengenai lelaran saya. Jika anda tidak keberatan saya melalui sini sekali lagi, menunjukkan di sini, menunjukkan di sini. Tetapi saya mempunyai penunjuk pred, penunjuk sebelumnya, itu jenis menghala ke arah yang elemen Saya hanya di. Oleh itu, apabila saya pergi di sini, kini kemas kini tangan kiri saya. Apabila saya pergi sini kemas kini tangan kiri saya. Dan sekarang saya bukan sahaja penunjuk kepada elemen yang masuk selepas Julia, Saya masih mempunyai penunjuk kepada Andy, elemen sebelumnya. Jadi, anda mempunyai akses, pada dasarnya, serbuk roti, jika anda akan, kepada semua petunjuk yang diperlukan. 

Jadi, jika saya menghala ke arah Andy dan saya juga menunjuk di Kristian, yang tangan kini perlu ditegaskan di tempat lain? Jadi Andy kini boleh menunjuk ke arah Julia. Julia kini boleh menunjuk ke arah Kristian. Kerana dia boleh menyalin saya penunjuk tangan kanan itu. Dan yang berkesan meletakkan anda kembali ke tempat ini di sini. Jadi ringkasnya, walaupun ini membawa kita jenis buat selama-lamanya untuk benar-benar mengemaskini senarai dikaitkan, menyedari bahawa operasi adalah agak mudah. Ia satu, dua, tiga baris kod akhirnya. Tetapi dibalut di sekeliling mereka baris kod mungkin adalah sedikit logik yang berkesan bertanya soalan, di mana kita? Adakah kita pada permulaan, tengah-tengah, atau akhir? 

Sekarang, terdapat pasti beberapa lain operasi kita mungkin melaksanakan. Dan gambar-gambar ini di sini hanya menggambarkan apa yang kita lakukan dengan manusia. Bagaimana pula dengan penyingkiran? Jika saya mahu, contohnya, mengeluarkan nombor 34 atau 55, Saya mungkin mempunyai jenis yang sama kod, tetapi saya akan memerlukan satu atau dua langkah. Oleh kerana apa yang baru? Jika saya mengeluarkan seseorang pada akhirnya, seperti nombor 55 dan kemudian 34, apa juga perlu berubah apabila saya berbuat demikian? Saya tidak evict-- apa nama anda lagi? 

PENONTON: Jack. 

DAVID J. MALAN: Jack. Saya bukan sahaja evict-- percuma Jack, jadi literal panggilan percuma Jack, atau sekurang-kurangnya penunjuk sana juga, tetapi sekarang apa yang perlu berubah dengan Peter? Tangannya lebih baik mula menunjuk ke bawah. Kerana sebaik sahaja saya menyeru percuma di Jack, jika Peter masih menghala ke arah Jack dan saya dengan itu menyimpan menyeberangi senarai dan akses penunjuk ini, itulah apabila rakan segmentasi lama kesalahan sebenarnya mungkin menendang. Oleh kerana kita telah diberi ingatan kembali kepada Jack. 

Anda boleh tinggal di sana canggung untuk hanya seketika. Kerana kita mempunyai hanya pasangan operasi terakhir yang perlu dipertimbangkan. Mengeluarkan ketua senarai, atau beginning-- dan ini yang sedikit menjengkelkan. Kerana kita perlu tahu bahawa Gabe adalah jenis khas dalam program ini. Kerana sesungguhnya, dia mempunyai penunjuk sendiri. Dia bukan sahaja diacukan pada, kerana hampir semua orang di sini. 

Oleh itu, apabila ketua senarai adalah dikeluarkan, yang tangan perlu menukar sekarang? Apa nama anda lagi? 

PENONTON: Christine. 

DAVID J. MALAN: Saya mengerikan pada nama, nampaknya. Jadi Christine dan Gabe, yang tangan perlu menukar apabila kita cuba untuk membuang Christine, nombor 5, dari gambar? OK, jadi mari kita buat Gabe. Gabe yang akan menunjukkan, mungkin, di nombor 9. Tetapi apa yang akan datang harus berlaku? PENONTON: Christine perlu batal [didengar]. DAVID J. MALAN: OK, kita harus mungkin make-- saya dengar "null" suatu tempat. PENONTON: Null dan bebas itu. DAVID J. MALAN: null apa? PENONTON: Null dan bebas itu. DAVID J. MALAN: Null dan bebas itu. Jadi ini adalah sangat mudah. Dan ia sempurna yang anda kini semacam berdiri di sana, yang bukan kepunyaan. Oleh kerana anda telah terpisah dari senarai. Anda telah berkesan telah yatim dari senarai. Dan kami lebih baik memanggil percuma sekarang Christine memberi ingatan yang kembali. Jika tidak setiap kali kita memadam nod dari senarai kita boleh membuat senarai lebih pendek, tetapi tidak benar-benar mengurangkan saiz dalam ingatan. Dan jadi jika kita terus menambah dan menambah, sambil menambah perkara-perkara ke dalam senarai, komputer saya mungkin akan mendapat lebih perlahan dan perlahan dan perlahan, kerana saya kehabisan ingatan, walaupun saya tidak benar-benar menggunakan bytes Christine memori lagi. 

Jadi pada akhirnya terdapat lain senario, penyingkiran course-- di tengah-tengah, pembuangan pada akhirnya, seperti yang kita lihat. Tetapi yang lebih menarik Cabaran sekarang ialah akan mempertimbangkan dengan tepat apa masa yang berjalan adalah. Jadi bukan sahaja anda boleh menyimpan anda keping kertas, jika, Gabe, anda tidak keberatan memberi semua orang bola tekanan. Terima kasih banyak untuk senarai dikaitkan kami sukarelawan di sini, jika anda boleh. 

[Tepuk tangan] 

DAVID J. MALAN: Baiklah. Jadi beberapa analisis soalan itu, jika saya boleh. Kami telah melihat notasi ini sebelum, O besar dan omega, batas atas ganda lebih rendah pada berjalan masa beberapa algoritma. Jadi mari kita mempertimbangkan hanya beberapa soalan. 

Satu, dan kami berkata sebelum ini, apa yang berjalan dengan masa carian untuk senarai dari segi O besar? Apakah had atas pada berjalan masa mencari senarai berpaut seperti yang dilaksanakan oleh sukarelawan kami di sini? Ia O besar n, linear. Kerana dalam kes yang paling teruk, unsur, seperti 55, kita boleh mencari di mana mungkin Jack adalah, semua cara di akhir. Malangnya, tidak seperti array kita tidak boleh mendapatkan mewah masa ini. Meskipun semua manusia kita adalah disusun dari unsur-unsur kecil, 5, sepanjang jalan sehingga kepada unsur yang lebih besar, 55, itu biasanya sesuatu yang baik. Tetapi apakah andaian bahawa tidak lagi membolehkan kita lakukan? PENONTON: [didengar] DAVID J. MALAN: Katakanlah lagi? PENONTON: Akses Rawak. DAVID J. MALAN: Akses Rawak. Dan seterusnya yang bermakna kita boleh tidak lagi menggunakan sifar lemah, gerak hati, dan obviousness menggunakan binari mencari dan membahagi dan menakluk. Kerana walaupun kita manusia boleh jelas melihat bahawa Andy atau Kristian secara kasar di tengah-tengah senarai, kita hanya tahu bahawa sebagai komputer oleh penyiring senarai dari awal. Oleh itu, kita telah mengaku kalah bahawa akses secara rawak. 

O begitu besar n sekarang adalah atas terikat pada masa carian kami. Bagaimana Omega carian kami? Apa yang lebih rendah terikat pada mencari untuk beberapa nombor dalam senarai ini? PENONTON: [didengar] DAVID J. MALAN: Katakanlah lagi? PENONTON: Satu. DAVID J. MALAN: Satu. Jadi masa yang berterusan. Dalam kes ini, Christine adalah sesungguhnya pada permulaan senarai. Dan yang kami cari nombor 5, maka kami mendapati beliau. Jadi tidak ada masalah besar. Tetapi dia mendapat untuk berada di bermula daripada senarai dalam kes ini. Bagaimana pula sesuatu seperti Padam? Bagaimana jika anda mahu memadam unsur? Apakah batas atas dan batas yang lebih rendah pada memotong sesuatu dari yang dikaitkan senaraikan? PENONTON: [didengar] DAVID J. MALAN: Katakanlah lagi? PENONTON: n. DAVID J. MALAN: n adalah sesungguhnya atas terikat. Kerana dalam kes yang paling teruk kita cuba memadam Jack, seperti kita lakukan. Dia sepanjang jalan pada akhir. Membawa kita selama-lamanya, atau n langkah-langkah untuk mencari beliau. Jadi itulah had atas. Itulah linear, pasti. Dan mana-mana yang terbaik berjalan masa, atau batas-batas yang lebih rendah di mana-mana yang terbaik akan menjadi masa yang berterusan. Kerana mungkin kita cuba untuk memadam Christine, dan kami hanya mendapat bertuah dia pada mulanya. Sekarang tunggu sebentar. Gabe juga pada permulaan, dan kami juga terpaksa mengemaskini Gabe. Supaya bukan sahaja satu langkah. Begitu juga ia memang tetap masa, di mana-mana yang terbaik, untuk menghapuskan unsur yang paling kecil? Ia adalah, walaupun ia mungkin dua, tiga, atau 100 baris kod, jika ia jumlah yang sama garis, tidak dalam beberapa gelung, dan bebas daripada saiz senarai itu, benar-benar. Memadam elemen di permulaan senarai, walaupun kita perlu berurusan dengan Gabe, masih masa yang berterusan. 

Jadi ini kelihatan seperti langkah besar ke belakang. Dan apa yang membuang masa jika, pada minggu satu dan minggu sifar kita bukan sahaja kod pseudokod tetapi kod sebenar untuk melaksanakan sesuatu yang log asas n, atau log masuk, sebaliknya, n, asas 2, dari segi masa larian itu. Jadi mengapa palang pintu yang kita mahu untuk memulakan menggunakan sesuatu seperti senarai berpaut? Yeah. 

PENONTON: Jadi anda boleh menambah unsur-unsur untuk array. DAVID J. MALAN: Jadi, anda boleh menambah unsur-unsur untuk array. Dan ini juga adalah bertema. Dan kita akan terus menyaksikan ini, ini keseimbangan, banyak seperti yang kita lihat yang keseimbangan dengan jenis merge. Kami benar-benar boleh mempercepatkan mencari atau sorting, sebaliknya, jika kita menghabiskan ruang sedikit lebih dan mempunyai sebahagian tambahan memori yang atau pelbagai jenis untuk merge. Tetapi kita menghabiskan lebih banyak ruang, tetapi kita menjimatkan masa. Dalam kes ini, kami menyerahkan masa tetapi kami mendapat fleksibiliti, dinamik jika anda akan, yang boleh dikatakan ciri yang positif. 

Kami juga menghabiskan ruang. Dalam apa rasa adalah berkait menyenaraikan lebih mahal dari segi ruang daripada array? Di manakah ruang tambahan yang datang dari? Yeah? 

PENONTON: [didengar] pointer. 

DAVID J. MALAN: Ya, kita juga mempunyai penunjuk. Jadi ini adalah minorly menjengkelkan dalam yang tidak lagi berasa Saya menyimpan hanya satu int untuk mewakili sebuah int. Saya menyimpan satu int dan penunjuk, yang juga 32 bit. Jadi, saya secara literal dua kali ganda jumlah ruang yang terlibat. Jadi itulah keseimbangan, tetapi yang dalam kes int. Katakan anda tidak menyimpan int, tetapi andaikan setiap segi empat tepat ini atau setiap manusia ini mewakili satu perkataan, perkataan Inggeris yang mungkin lima watak, 10 aksara, mungkin lebih. Kemudian sambil menambah hanya 32 lebih bit mungkin kurang daripada satu masalah besar. 

Bagaimana jika setiap pelajar dalam demonstrasi adalah benar-benar structs pelajar yang mempunyai nama dan rumah-rumah dan mungkin nombor telefon dan Twitter mengendalikan dan sebagainya. Jadi semua bidang kami mula bercakap tentang hari lain, lebih kurang masalah besar sebagai nod kami mendapatkan lebih banyak menarik dan besar untuk berbelanja, eh, tambahan penunjuk hanya untuk menghubungkan mereka bersama-sama. Tetapi sesungguhnya, ia adalah keseimbangan. Dan sesungguhnya, kod adalah kompleks lebih, kerana anda akan lihat dengan penyiring melalui bahawa contoh tertentu. Tetapi bagaimana jika terdapat beberapa kaedah berpotensi suci di sini. Bagaimana jika kita tidak mengambil langkah yang ke belakang tetapi satu langkah besar ke hadapan dan melaksanakan data yang struktur melalui mana kita mempunyai unsur-unsur seperti Jack atau Christine atau mana-mana elemen-elemen lain dalam tatasusunan ini dalam masa yang tetap benar? Cari adalah tetap. Padam adalah tetap. Masukkan adalah tetap. Semua operasi ini adalah malar. Itu adalah kaedah berpotensi suci kita. Dan di situlah kita akan mengambil masa yang akan datang. Jumpa anda kemudian.