[MUSIC PLAYING] [VIDEO PLAYBACK] -Dia berbohong. -Mengenai apa? -Aku Tidak tahu. -Jadi Apa yang kita ketahui? -yaitu Di 09:15, Ray Santoya berada di ATM. Yeah. Jadi pertanyaannya adalah, apa yang yang dia lakukan di 9:16? -Shooting 9 milimeter sesuatu. Mungkin dia melihat penembak jitu. -atau Bekerja dengan dia. -Tunggu. Kembali satu. -Apa yang kamu lihat? -Bawa Wajahnya hingga layar penuh. Gelas -Tinjauan. -Ada Refleksi. -Ini Tim bisbol Nuevitas. Itu logo mereka. -dan Dia berbicara dengan siapa pun yang mengenakan jaket itu. [END PLAYBACK] DAVID Malan: Baiklah. Ini adalah CS50 dan ini sedikit lebih dari [tak terdengar] dengan yang Anda berkecimpung dengan masalah menetapkan empat. Hari ini kita mulai melihat sedikit lebih mendalam hal-hal ini disebut pointer, yang meskipun itu topik yang cukup misterius, ternyata bahwa itu akan menjadi sarana yang kita bisa mulai membangun dan perakitan program jauh lebih canggih. Tapi kami melakukannya pada hari Rabu terakhir dengan cara beberapa claymation pertama. Jadi ini, ingat, adalah Binky dan kami menggunakan dia untuk melihat pada program yang tidak benar-benar melakukan sesuatu yang menarik, tapi itu mengungkapkan beberapa masalah. Jadi untuk memulai hari, mengapa kita tidak berjalan cepat melalui beberapa langkah-langkah ini, mencoba untuk menyaring ke dalam istilah manusia persis apa yang terjadi di sini dan mengapa ini buruk, dan kemudian beralih dan benar-benar mulai membangun sesuatu dengan teknik ini? Jadi ini adalah yang pertama dua baris dalam program ini dan dalam istilah awam, apa adalah dua baris ini lakukan? Seseorang yang cukup nyaman dengan apa yang dinyatakan di layar? Apa dua baris lakukan? Ini tidak semua yang berbeda dari satu minggu, tapi ada beberapa simbol khusus baru. Ya? Kembali ke sana. AUDIENCE: Mendeklarasikan pointer? DAVID Malan: Katakanlah lagi? AUDIENCE: Mendeklarasikan pointer? DAVID Malan: Mendeklarasikan pointer dan mari kita memperbaikinya sedikit lebih. AUDIENCE: [tidak terdengar] alamat x dan kemudian y. DAVID Malan: Dan kemudian mengatasi. Jadi secara spesifik apa yang kita lakukan adalah kita mendeklarasikan dua variabel. Variabel ini, meskipun, akan menjadi tipe bintang int, yang lebih khusus berarti mereka akan menyimpan alamat int, masing-masing, x dan y. Sekarang apakah ada nilai-nilai? Apakah ada alamat yang sebenarnya di ini dua variabel pada saat ini dalam waktu? Tidak. Ini disebut hanya nilai-nilai sampah. Jika Anda tidak benar-benar menetapkan variabel, apa pun yang di RAM sebelumnya akan mengisi dengan nol dan yang kedua variabel tersebut. Tapi kita belum tahu apa yang mereka dan itulah akan menjadi kunci untuk mengapa Binky kehilangan kepalanya pekan lalu. Jadi ini adalah claymation yang inkarnasi ini dimana Anda hanya memiliki dua variabel, sedikit potongan melingkar dari tanah liat, yang dapat menyimpan variabel, tetapi sebagai panah dibungkus menyarankan, mereka tidak benar-benar menunjuk ke mana saja dikenal. Jadi kami harus baris ini, dan ini baru minggu lalu, malloc untuk memori alokasi, yang hanya cara mewah memberitahu sistem operasi, Linux atau Mac OS atau Windows, hey, memberi saya beberapa memori, dan semua Anda harus memberitahu sistem operasi adalah apa ketika meminta untuk memori. Ini tidak akan peduli apa Anda akan lakukan dengan itu, tetapi Anda perlu memberitahu operasi sistem apa dengan cara malloc. Ya? AUDIENCE: Berapa banyak? DAVID Malan: Berapa banyak? Berapa banyak dalam byte, dan sebagainya, ini, lagi, contoh buat, hanya mengatakan, memberikan ukuran sebuah int. Sekarang, ukuran sebuah int adalah empat byte atau 32 bit. Jadi ini hanyalah sebuah cara mengatakan, hei, sistem operasi, memberi saya empat byte memori yang dapat saya gunakan di pembuangan saya, dan secara khusus, apa kembali malloc dengan hormat itu sepotong empat byte? AUDIENCE: Alamat? DAVID Malan: Alamat. Alamat yang sepotong empat byte. Tepat. Dan itulah yang disimpan pada akhirnya di x dan itulah mengapa kita tidak benar-benar peduli apa jumlah yang alamat adalah, apakah itu OX1 atau OX2 atau beberapa alamat heksadesimal samar. Kami hanya peduli pictorially bahwa variabel x sekarang menunjuk ke sepotong memori. Jadi panah merupakan pointer, atau lebih khusus, alamat memori. Tapi sekali lagi, kita tidak biasanya peduli apa alamat tersebut sebenarnya. Sekarang, baris ini mengatakan apa yang dalam istilah awam? Bintang x mendapat 42 titik koma. Apa artinya ini? Anda ingin pergi? Jangan menggaruk leher Anda. AUDIENCE: Alamat x adalah pada 42. DAVID Malan: Alamat x di 42. Tidak terlalu. Begitu dekat, tapi tidak cukup, karena ada bintang yang awalan x ini. Jadi kita perlu tweak sedikit. Ya? AUDIENCE: Nilai bahwa pointer x menunjuk ke adalah 42. DAVID Malan: OK. Nilai bahwa pointer x adalah menunjuk ke, katakanlah, harus 42, atau dengan kata lain, bintang x mengatakan, pergi ke alamat apapun adalah x, apakah itu 1 Oxford Jalan atau 33 Oxford Street atau OX1 atau OX33, apa pun alamat numerik adalah, Bintang x adalah dereferencing x. Jadi pergi ke alamat itu dan kemudian memasukkan nomor 42 ada. Sehingga akan menjadi Cara setara mengatakan bahwa. Jadi itu semua baik-baik saja dan kemudian kita akan mewakili gambar sebagai berikut di mana kami telah menambahkan 42 untuk yang sepotong empat byte di sisi kanan, tetapi baris ini adalah di mana hal-hal berjalan kacau dan kepala Binky ini muncul off pada saat ini, karena hal-hal buruk terjadi ketika Anda dereference nilai sampah atau Anda dereference valid pointer, dan saya mengatakan tidak valid karena pada titik ini dalam cerita, apa yang ada dalam y? Apa nilai y berdasarkan pada beberapa langkah terakhir? Ya? Apa itu? AUDIENCE: Sebuah alamat. DAVID Malan: Sebuah alamat. Ini harus alamat tetapi saya diinisialisasi itu? Jadi saya belum. Jadi apa yang dikenal berada di sana? Ini hanya beberapa nilai sampah. Ini bisa menjadi alamat dari nol sampai 2 miliar jika Anda memiliki dua gigs RAM, atau nol sampai 4 miliar jika Anda sudah punya empat gigabyte RAM. Ini beberapa nilai sampah, tapi masalahnya adalah bahwa sistem operasi, jika tidak memberi kamu yang sepotong memori khusus bahwa Anda sedang berusaha untuk pergi ke, itu umumnya akan menyebabkan apa kita lihat sebagai kesalahan segmentasi. Jadi sebenarnya, ada di antara kalian yang memiliki berjuang di masalah di jam kantor atau dalam masalah yang lebih umumnya dengan mencoba untuk mencari tahu kesalahan segmentasi, yang umumnya berarti Anda menyentuh segmen memori yang Anda tidak seharusnya. Anda menyentuh memori yang sistem operasi belum memungkinkan Anda untuk menyentuh, apakah itu dengan pergi terlalu jauh dalam array atau mulai sekarang, apakah itu karena Anda menyentuh memori yang hanya beberapa nilai sampah. Jadi melakukan star x sini semacam perilaku undefined. Anda tidak harus melakukannya karena peluang yang, program hanya akan crash, karena kau mengatakan, pergi ke alamat ini dan Anda tidak tahu di mana alamat yang benar-benar adalah. Jadi sistem operasi kemungkinan akan crash program Anda sebagai hasil dan memang, itu apa yang terjadi di sana untuk Binky. Jadi pada akhirnya, Binky tetap masalah ini dengan ini. Sehingga program itu sendiri itu cacat. Tapi jika Anda semacam maju dan mengeksekusi baris ini sebaliknya, y sama dengan x hanya berarti apapun Alamat adalah x, juga memasukkannya ke dalam y. Dan pictorially, kami telah diwakili dengan dua panah dari x dan y dari menunjuk ke tempat yang sama. Jadi semantik, x sama untuk y karena kedua orang menyimpan sama alamat, ergo menunjuk 42, dan sekarang, ketika Anda mengatakan star y, pergi ke alamat di y, ini memiliki efek samping yang menarik. Jadi alamat di y adalah hal yang sama seperti alamat di x. Jadi jika Anda mengatakan pergi ke alamat di y dan ubah nilainya menjadi 13, siapa lagi yang terpengaruh? X, titik D, sehingga untuk berbicara, harus terpengaruh juga. Dan memang, bagaimana Nick menggambar gambar ini di claymation adalah persis seperti itu. Meskipun kita mengikuti pointer y, kami berakhir di tempat yang sama, dan jadi jika kami mencetak keluar x atau y yang pointee, maka kita akan melihat nilai 13. Sekarang, saya katakan pointee menjadi konsisten dengan video. Programmer, untuk saya pengetahuan, pernah benar-benar mengatakan pointee kata, bahwa yang runcing di, tapi untuk konsistensi dengan video, menyadari itu semua yang berarti dalam situasi itu. Jadi pertanyaan pada claymation atau pointer atau malloc dulu? Tidak? Baiklah. Jadi tanpa lebih lanjut ado, mari kita lihat di mana ini sebenarnya telah telah digunakan untuk beberapa waktu. Jadi kami sudah perpustakaan CS50 ini yang punya semua fungsi ini. Kami telah menggunakan getInt banyak, GetString, mungkin GetLongLong sebelumnya di PSet saya satu atau lebih, tetapi apa yang sebenarnya terjadi? Nah, mari kita lihat bawah kap di program yang mengilhami mengapa kami memberikan Anda CS50 perpustakaan, dan memang pada pekan lalu, kami mulai mengambil mereka roda pelatihan off. Jadi ini sekarang diurutkan dari postmortem dari apa memiliki sudah berlangsung dalam perpustakaan CS50, meskipun kita sekarang akan mulai bergerak jauh dari itu untuk sebagian besar program. Jadi ini adalah sebuah program yang disebut scanf 0. Ini super pendek. Itu hanya memiliki garis-garis ini, tetapi memperkenalkan fungsi yang disebut scanf bahwa kita benar-benar akan melihat di saat di dalam perpustakaan CS50, meskipun dalam bentuk yang sedikit berbeda. Jadi program ini pada baris 16 adalah mendeklarasikan variabel x. Jadi memberi saya empat byte untuk int. Sudah pengguna mengatakan, nomor silakan, dan kemudian ini adalah garis yang menarik yang sebenarnya mengikat bersama-sama minggu lalu dan ini. Scanf, dan kemudian melihat dibutuhkan format string, seperti printf, % i berarti int, dan kemudian dibutuhkan Argumen kedua yang terlihat sedikit funky. Ini ampersand x, dan untuk mengingat, kita hanya melihat minggu sekali lalu ini. Apa ampersand x mewakili? Apa ampersand lakukan di C? Ya? AUDIENCE: Alamat. DAVID Malan: Alamat. Jadi sebaliknya operator bintang, sedangkan operator bintang mengatakan, pergi ke alamat ini, operator ampersand mengatakan, mengetahui alamat variabel ini, dan jadi ini adalah kunci, karena Tujuan scanf dalam kehidupan adalah untuk memindai pengguna input dari keyboard, tergantung pada apa pun yang dia jenis, dan kemudian membaca masukan yang pengguna menjadi variabel, tapi kami melihat dalam dua minggu terakhir bahwa fungsi swap kami mencoba mudah untuk menerapkan hanya rusak. Ingat bahwa dengan fungsi swap, jika kita hanya menyatakan A dan B sebagai int, kami berhasil menukar dua variabel dalam swap hanya ingin dengan susu dan OJ, tetapi segera sebagai swap kembali, apa hasil dengan hormat untuk x dan y, nilai-nilai asli? Tidak ada. Ya. Tidak ada yang terjadi saat itu, karena swap mengubah hanya salinan lokal, yang mengatakan, semua kali ini, setiap kali kita sudah telah melewati dalam argumen fungsi, kami hanya lewat salinan argumen-argumen. Anda dapat melakukan dengan itu apapun yang Anda inginkan dengan mereka, tapi mereka akan memiliki efek pada nilai-nilai asli. Jadi ini bermasalah jika Anda ingin memiliki fungsi seperti scanf dalam kehidupan, yang tujuannya adalah untuk memindai masukan pengguna dari keyboard dan kemudian mengisi kekosongan, sehingga untuk berbicara, yaitu, memberikan variabel seperti x nilai, karena jika saya hanya lulus x untuk scanf, jika Anda mempertimbangkan logika terakhir Minggu, scanf dapat melakukan apapun yang diinginkan dengan salinan x, tetapi tidak bisa permanen mengubah x kecuali kita memberi scanf peta harta karun, sehingga untuk berbicara, di mana x menandai tempat, dimana kita lulus dalam alamat x sehingga scanf dapat pergi ke sana dan benar-benar perubahan nilai x. Dan memang, semua bahwa program ini tidak jika saya membuat scanf 0, di sumber saya Direktori 5m, membuat scanf 0, dot slash scanf, jumlah silahkan 50, terima kasih atas 50. Sehingga tidak semua yang menarik, tapi apa memang terjadi adalah bahwa segera setelah saya sebut scanf sini, nilai x sedang secara permanen berubah. Sekarang, ini tampaknya bagus dan baik, dan pada kenyataannya, itu Sepertinya kita tidak benar-benar membutuhkan perpustakaan CS50 sekali lagi. Misalnya, mari kita jalankan ini sekali lagi di sini. Biarkan saya buka kembali untuk kedua. Mari kita coba nomor silakan dan bukannya mengatakan 50 seperti sebelumnya, mari kita hanya mengatakan tidak. OK, itu sedikit aneh. OKE. Dan hanya omong kosong di sini. Sehingga tampaknya tidak menangani situasi yang salah. Jadi kita perlu minimal awal menambahkan beberapa pengecekan error memastikan bahwa pengguna memiliki diketik dalam jumlah sebenarnya seperti 50, karena rupanya mengetik kata-kata tidak terdeteksi sebagai bermasalah, tapi mungkin seharusnya. Mari kita lihat versi ini sekarang itu upaya saya untuk reimplement GetString. Jika scanf memiliki semua ini fungsi built in, mengapa kita telah berkecimpung dengan ini roda pelatihan seperti GetString? Nah, di sini adalah mungkin saya sendiri versi sederhana dari GetString dimana seminggu yang lalu, saya mungkin telah mengatakan, memberi saya string dan menyebutnya penyangga. Hari ini, aku akan mulai hanya mengatakan bintang char, yang, ingat, itu hanya identik. Ini terlihat menakutkan tapi itu hal yang sama persis. Jadi memberi saya sebuah variabel disebut buffer itu akan menyimpan string, memberitahu string pengguna tolong, dan kemudian, seperti sebelumnya, mari kita coba untuk meminjam pelajaran ini scanf % s saat ini dan kemudian lulus dalam buffer. Sekarang, sebuah pemeriksaan cepat. Mengapa aku tidak mengatakan ampersand penyangga saat ini? Menyimpulkan dari contoh sebelumnya. AUDIENCE: Bintang Char adalah pointer. DAVID Malan: Tepat, karena saat ini, char Bintang sudah pointer, alamat, oleh definisi bahwa bintang berada di sana. Dan jika scanf mengharapkan alamat, itu sudah cukup hanya untuk lulus dalam buffer. Saya tidak perlu mengatakan ampersand penyangga. Bagi yang penasaran, Anda bisa melakukan sesuatu seperti ini. Ini akan memiliki arti yang berbeda. Ini akan memberi Anda pointer untuk pointer, yang sebenarnya hal yang valid di C, tapi untuk sekarang, mari kita tetap sederhana dan menjaga cerita konsisten. Aku hanya akan lulus dalam buffer dan itu benar. Masalahnya meskipun adalah ini. Biarkan aku pergi ke depan dan menjalankan ini Program setelah mengkompilasinya. Membuat scanf 1. Sialan, compiler saya menangkap kesalahan saya. Beri aku satu detik. Dentang. Katakanlah scanf-1.c. OKE. Di sana kami pergi. Aku membutuhkannya. CS50 ID memiliki berbagai pengaturan konfigurasi yang melindungi Anda terhadap diri Anda sendiri. Saya perlu menonaktifkan mereka dengan menjalankan dentang manual saat ini. Jadi tali silakan. Aku akan pergi ke depan dan ketik di dunia halo favorit saya. OK, null. Itu bukan apa yang saya ketik. Jadi indikasi sesuatu yang salah. Biarkan aku pergi ke depan dan ketik dalam serangkaian sangat panjang. Terima kasih untuk nol dan saya tidak tahu apakah aku akan mampu untuk kecelakaan itu. Mari kita coba salinan sedikit menyisipkan dan melihat apakah ini membantu. Hanya menyisipkan banyak ini. Ini jelas lebih besar tali dari biasanya. Mari kita hanya benar-benar menulis itu. Tidak. Kurang ajar. Perintah tidak ditemukan. Jadi itu tidak berhubungan. Itu karena aku disisipkan beberapa karakter yang buruk, tapi ini ternyata tidak akan bekerja. Mari kita coba ini sekali lagi, karena itu lebih menyenangkan jika kita benar-benar kecelakaan itu. Mari kita ketik ini dan sekarang, aku akan menyalin string yang sangat panjang dan sekarang mari kita lihat apakah kita dapat crash hal ini. Perhatikan saya dihilangkan spasi dan baris baru dan titik koma dan semua karakter yang funky. Masukkan. Dan sekarang jaringan hanya menjadi lambat. Saya ditekan Command-V terlalu lama, jelas. Kurang ajar! Perintah tidak ditemukan. OKE. Nah, intinya adalah tetap berikut. Jadi apa yang sebenarnya terjadi pada dengan deklarasi ini dari bintang char buffer on line 16? Jadi apa yang aku mendapatkan ketika saya menyatakan pointer? Semua aku mendapatkan adalah nilai empat byte disebut buffer, tapi apa di dalamnya saat ini? Ini hanya beberapa nilai sampah. Karena setiap kali Anda mendeklarasikan variabel di C, itu hanya beberapa nilai sampah, dan kita mulai perjalanan atas realitas ini. Sekarang, ketika saya memberitahu scanf, pergi ke alamat ini dan menempatkan apapun jenis pengguna di. Jika jenis pengguna di halo dunia, baik, di mana saya menaruhnya? Buffer adalah nilai sampah. Jadi itu jenis seperti panah yang menunjuk siapa yang tahu di mana. Mungkin itu menunjuk di sini dalam ingatanku. Dan jadi ketika pengguna jenis di dunia halo, program mencoba untuk menempatkan String hello world backslash 0 dalam sepotong memori. Tapi dengan probabilitas tinggi, tapi jelas tidak probabilitas 100%, komputer akan kemudian crash program karena ini bukan memori saya harus diizinkan untuk menyentuh. Jadi singkatnya, program ini adalah cacat untuk persis alasan itu. Aku dasarnya tidak melakukan apa? Langkah-langkah apa yang harus saya dihilangkan, seperti kita dihilangkan dengan contoh pertama Binky ini? Ya? AUDIENCE: alokasi memori? DAVID Malan: alokasi memori. Saya belum benar-benar dialokasikan setiap memori untuk string. Jadi kita bisa memperbaiki ini dalam beberapa cara. Satu, kita bisa tetap sederhana dan pada kenyataannya, sekarang kau akan mulai melihat kabur sebuah garis antara apa array adalah, apa string adalah, sebuah apa Bintang arang adalah, apa array karakter aku s. Berikut adalah contoh kedua melibatkan string dan pemberitahuan semua yang telah saya lakukan pada baris 16 adalah, bukannya mengatakan buffer yang akan menjadi char bintang, pointer ke sepotong memori, Aku akan sangat proaktif memberikan diriku buffer untuk 16 karakter, dan pada kenyataannya, jika Anda terbiasa dengan penyangga istilah, mungkin dari dunia video, mana video buffering, buffering, buffering. Nah, apa koneksi di sini? Nah, dalam YouTube dan dalam video player umumnya adalah array yang lebih besar dari 16. Mungkin array ukuran satu megabyte, mungkin 10 megabyte, dan ke dalam array yang melakukan browser Anda men-download sejumlah byte, sejumlah megabyte video, dan pemutar video, YouTube atau siapa pun yang, dimulai membaca byte dari array, dan setiap kali Anda melihat kata buffering, buffering, yang berarti pemain memiliki sampai pada akhir array itu. Jaringan ini begitu lambat bahwa ia memiliki tidak diisi ulang array dengan lebih byte dan begitu Anda keluar dari bit untuk menampilkan kepada pengguna. Jadi penyangga adalah istilah yang tepat di sini di yang itu hanya sebuah array, sepotong memori. Dan ini akan memperbaikinya karena ternyata Anda dapat mengobati array seakan mereka alamat, meskipun penyangga hanya simbol, itu adalah urutan karakter, penyangga, itu berguna bagi saya, programmer, Anda dapat melewati nama sekitar seolah-olah itu adalah pointer, seolah-olah itu adalah alamat sepotong memori untuk 16 karakter. Jadi itu mengatakan, saya bisa lulus scanf kata yang tepat dan jadi sekarang, jika saya membuat program ini, membuat scanf 2, dot slash scanf 2, dan ketik halo dunia, Masukkan, time-- yang Hmm, apa yang terjadi? String silakan. Apa kesalahan yang telah aku perbuat? Halo dunia, penyangga. Halo Dunia. Ah, aku tahu apa yang dilakukannya. OKE. Jadi itu membaca sampai ruang pertama. Jadi mari kita menipu untuk sesaat dan mengatakan saya hanya ingin mengetik sesuatu sangat panjang seperti ini adalah kalimat yang panjang itu salah satu, dua, tiga, empat, lima, enam, tujuh, delapan, sembilan, 10, 11, 12, 13, 14, 15, 16. OKE. Sungguh suatu kalimat panjang. Jadi kalimat ini lebih panjang dari 16 karakter dan jadi ketika saya tekan Enter, apa yang akan terjadi? Nah, dalam hal ini dari cerita, saya telah menyatakan penyangga untuk benar-benar menjadi sebuah array dengan 16 karakter siap untuk pergi. Jadi satu, dua, tiga, empat, lima, enam, tujuh, delapan, sembilan, 10, 11, 12, 13, 14, 15, 16. Jadi 16 karakter, dan sekarang, ketika saya membaca sesuatu seperti ini adalah panjang kalimat, apa yang akan terjadi adalah bahwa aku akan membaca dalam hal ini adalah panjang S-E-N-T-E-N-C-E, kalimat. Jadi ini sengaja hal yang buruk yang saya terus menulis di luar batas-batas array saya, melampaui batas-batas buffer saya. Aku bisa beruntung dan program akan terus berjalan dan tidak peduli, tapi secara umum, ini memang akan crash program saya, dan itu adalah bug di saya kode saat aku melangkah melampaui batas-batas array itu, karena saya tidak tahu apakah itu tentu akan crash atau jika aku hanya akan beruntung. Jadi ini bermasalah karena dalam kasus ini, itu tampaknya untuk bekerja dan mari kita mencobai nasib di sini, meskipun IDE tampaknya mentolerir sedikit of-- Di sana kami pergi. Akhirnya. Jadi aku satu-satunya yang dapat melihat ini. Jadi aku hanya memiliki banyak menyenangkan mengetik sebuah frase yang sebenarnya sangat panjang bahwa itu pasti melebihi 16 byte, karena saya mengetik panjang multi-line ini gila frase, dan kemudian melihat apa yang terjadi. Program ini mencoba mencetaknya dan kemudian mendapat kesalahan segmentasi dan kesalahan segmentasi adalah ketika sesuatu seperti ini terjadi dan sistem operasi mengatakan tidak ada, tidak bisa menyentuh memori itu. Kita akan membunuh program sama sekali. Jadi ini tampaknya bermasalah. Aku telah menyempurnakan program dimana setidaknya memiliki beberapa memori, tapi ini tampaknya akan membatasi fungsi GetString untuk mendapatkan string dari beberapa panjang hingga 16. Jadi jika Anda ingin mendukung lagi kalimat dari 16 karakter, Apa yang kamu kerjakan? Nah, Anda dapat meningkatkan ukuran buffer ini untuk 32 atau yang tampaknya agak pendek. Mengapa kita tidak hanya membuat itu 1.000 tetapi mendorong kembali. Apa respon intuitif dari hanya menghindari masalah ini dengan membuat penyangga saya lebih besar, seperti 1.000 karakter? Dengan menerapkan GetString cara ini. Apa yang baik atau buruk di sini? Ya? AUDIENCE: Jika Anda mengikat banyak ruang dan Anda tidak menggunakannya, maka Anda tidak dapat mengalokasikan ruang itu. DAVID Malan: Absolutely. Ini boros sepanjang jika Anda tidak benar-benar membutuhkan 900 orang byte namun Anda meminta 1000 total pula, Anda hanya mengkonsumsi lebih banyak memori pada komputer pengguna dari yang Anda butuhkan untuk, dan setelah semua, beberapa Anda sudah ditemui dalam hidup ketika Anda menjalankan banyak program dan mereka makan sampai banyak memori, ini benar-benar dapat mempengaruhi kinerja dan pengalaman pengguna di komputer. Jadi itu semacam solusi malas, pasti, dan sebaliknya, itu tidak hanya boros, masalah apa masih tetap, bahkan jika saya membuat penyangga saya 1.000? Ya? AUDIENCE: string adalah panjang 1.001. DAVID Malan: Tepat. Jika string Anda adalah panjang 1001, Anda memiliki masalah yang sama, dan oleh argumen saya, saya akan hanya kemudian membuatnya tahun 2000, tetapi Anda tidak tahu di memajukan seberapa besar itu harus, namun, saya harus mengkompilasi program saya sebelum membiarkan orang menggunakan dan men-download saya t. Jadi ini adalah persis jenis hal-hal yang perpustakaan mencoba CS50 untuk membantu kami dengan dan kami akan hanya sekilas di beberapa implementasi yang mendasari di sini, tapi ini adalah CS50 dot C. Ini adalah file yang sudah di CS50 IDE semua minggu ini bahwa Anda telah menggunakan. Ini pra-disusun dan Anda sudah telah menggunakan secara otomatis oleh sifat memiliki lari L CS50 bendera dengan dentang, tapi jika saya gulir ke bawah melalui semua fungsi-fungsi ini, inilah GetString, dan hanya untuk memberi Anda rasa apa yang terjadi, mari kita cepat melihat kompleksitas relatif. Ini bukan super panjang fungsi, tapi kami tidak harus berpikir keras tentang semua bagaimana cara mendapatkan string. Jadi, inilah penyangga saya dan saya rupanya menginisialisasi ke null. Ini, tentu saja, adalah hal yang sama seperti bintang char, tapi aku memutuskan di menerapkan perpustakaan CS50 bahwa jika kita akan benar-benar dinamis, Saya tidak tahu sebelumnya seberapa besar dari pengguna string yang akan ingin mendapatkan. Jadi aku akan mulai hanya dengan string kosong dan aku akan membangun sebanyak memori yang saya butuhkan untuk menyesuaikan string pengguna dan jika saya tidak memiliki cukup, aku akan meminta sistem operasi untuk lebih banyak memori. Aku akan memindahkan tali mereka ke dalam bongkahan besar memori dan aku akan melepaskan atau membebaskan potongan kurang besar memori dan kami hanya akan untuk melakukan hal ini iteratif. Jadi sekilas, di sini hanya variabel dengan yang aku akan melacak dari kapasitas buffer saya. Berapa banyak byte saya bisa cocok? Berikut adalah n variabel dengan yang aku akan terus melacak berapa banyak byte yang sebenarnya di buffer atau bahwa pengguna telah diketik. Jika Anda sudah tidak melihat ini sebelumnya, Anda dapat menentukan bahwa variabel seperti int adalah unsigned, yang seperti namanya, berarti itu non-negatif, dan mengapa Saya pernah ingin mengganggu menspesifikasikan yang int bukan hanya int, tapi itu unsigned int? Ini adalah int non-negatif. Apa [tidak terdengar] berarti? AUDIENCE: Ini menggambarkan jumlah memori yang dapat [tidak terdengar]. DAVID Malan: Ya. Jadi jika saya mengatakan unsigned, ini sebenarnya memberikan Anda satu bit memori tambahan dan tampaknya konyol, tetapi jika Anda memiliki satu bit memori tambahan, yang berarti Anda memiliki dua kali lebih banyak nilai yang Anda dapat mewakili, karena bisa menjadi 0 atau 1. Jadi secara default, int secara kasar dapat 2 miliar negatif sepanjang jalan hingga positif 2 miliar. Mereka adalah rentang besar, tetapi itu masih semacam boros jika Anda hanya peduli tentang ukuran, yang hanya secara intuitif harus non-negatif atau positif atau 0, baik maka, mengapa kau buang 2 miliar nilai yang mungkin untuk angka negatif jika Anda tidak akan menggunakannya? Jadi dengan mengatakan unsigned, sekarang saya bisa int antara 0 dan kira-kira 4 miliar. Jadi di sini hanya sebuah int C untuk alasan kita tidak akan masuk ke dalam sekarang sebagai mengapa itu int bukan char, tapi di sini adalah intisari dari apa yang terjadi pada, dan beberapa dari Anda mungkin menggunakan, misalnya, Fungsi fgetc bahkan di PSet empat atau setelahnya, kita akan melihatnya lagi di masalah set lima, fgetc bagus karena sebagai nama jenis, semacam arcanely menunjukkan, itu fungsi yang mendapat karakter dan sebagainya, apa fundamental berbeda tentang apa yang kita lakukan di GetString adalah kita tidak menggunakan scanf dengan cara yang sama. Kami hanya merayap di sepanjang langkah-demi-langkah lebih apa pun pengguna telah diketik di, karena kita selalu dapat mengalokasikan satu char, dan jadi kita bisa selalu aman melihat satu char pada satu waktu, dan keajaiban mulai terjadi di sini. Aku akan gulir ke bawah untuk tengah fungsi ini hanya untuk memperkenalkan fungsi ini secara singkat. Seperti ada Fungsi malloc, ada fungsi realloc mana realloc memungkinkan Anda mengalokasikan sepotong memori dan membuatnya lebih besar atau lebih kecil. Cerita begitu panjang pendek dan dengan gelombang tangan saya untuk hari ini, tahu bahwa apa yang GetString melakukan itu semacam dari ajaib tumbuh atau menyusut buffer sebagai pengguna jenis dalam nya tali. Jadi jika pengguna jenis tali pendek, kode ini hanya mengalokasikan cukup memori untuk menyesuaikan string. Jika pengguna terus mengetik seperti yang saya lakukan itu lagi dan lagi dan lagi, baik, jika buffer awalnya ini besar dan program menyadari, untuk tunggu sebentar, aku keluar dari ruang, itu akan dua kali lipat ukuran buffer dan kemudian dua kali lipat ukuran buffer dan kode yang melakukan penggandaan tersebut, jika kita melihat di sini, itu hanya ini pintar satu-kapal. Anda tidak mungkin telah melihat sintaks ini sebelumnya, tapi jika Anda mengatakan star sama, ini adalah hal yang sama seperti mengatakan kapasitas kali 2. Jadi itu hanya terus menggandakan kapasitas buffer dan kemudian memberitahu realloc untuk memberikan itu sendiri yang jauh lebih banyak memori. Sekarang, sebagai samping, ada fungsi lain di sini bahwa kita tidak akan melihat ke dalam setiap detail selain untuk menunjukkan di getInt, kita menggunakan GetString di getInt. Kami memeriksa bahwa itu bukan null, yang, ingat, adalah nilai khusus yang berarti ada yang tidak beres. Kami keluar dari memori. Lebih baik periksa untuk itu. Dan kita kembali nilai sentinel. Tapi aku akan tunduk kepada komentar untuk mengapa dan kemudian kita menggunakan saudara sepupu ini scanf disebut sscanf dan ternyata yang sscanf, atau tali scanf, memungkinkan Anda melihat pada garis yang pengguna telah diketik dalam dan membiarkan Anda menganalisis dasarnya dan apa yang saya lakukan di sini adalah saya memberitahu sscanf, menganalisis apa pengguna memiliki diketik dan pastikan% i, ada bilangan bulat di dalamnya, dan kami tidak akan masuk ke hari ini persis mengapa ada juga a% c sini, tapi itu singkatnya memungkinkan kita untuk mendeteksi jika pengguna telah diketik dalam sesuatu palsu setelah nomor. Jadi alasan bahwa getInt dan GetString memberitahu Anda untuk mencoba lagi, coba lagi, coba lagi adalah karena semua bahwa kode kita sudah ditulis, itu semacam melihat masukan pengguna dalam memastikan itu sepenuhnya numerik atau ini merupakan floating aktual nilai titik atau sejenisnya, tergantung pada apa nilai berfungsi Anda gunakan. Whew. OKE. Itu adalah seteguk tapi intinya di sini adalah bahwa alasan kami memiliki mereka roda pelatihan karena pada tingkat terendah, ada begitu banyak hal yang bisa salah bahwa kami ingin untuk menangani preemptively hal-hal pasti dalam minggu awal kelas, tapi sekarang dengan PSet empat dan lima PSet dan luar akan Anda melihat bahwa itu lebih kepada Anda tetapi juga Anda lebih mampu pemecahan yang macam masalah sendiri. Pertanyaan GetString atau getInt? Ya? AUDIENCE: Mengapa Anda akan berlipat ganda kapasitas buffer bukan hanya meningkatkan dengan jumlah yang tepat? DAVID Malan: Pertanyaan yang bagus. Mengapa kita akan menggandakan kapasitas buffer yang bertentangan hanya meningkatkan itu oleh beberapa nilai konstan? Itu adalah keputusan desain. Kami hanya memutuskan bahwa karena cenderung sedikit mahal waktu-bijaksana untuk meminta sistem operasi untuk memori, kami tidak ingin berakhir masuk ke situasi untuk string besar bahwa kami meminta OS lagi dan lagi dan lagi dan lagi di suksesi cepat untuk memori. Jadi kami hanya memutuskan, agak sewenang-wenang tapi kami berharap cukup, bahwa, Anda tahu apa, mari kita mencoba untuk maju dari diri kita sendiri dan terus menggandakan sehingga kami meminimalkan jumlah kali kita harus memanggil malloc atau realloc, tapi penilaian Total sebut dalam ketiadaan mengetahui apa yang pengguna mungkin ingin ketik. Kedua cara bisa diperdebatkan. Bisa dibilang baik. Jadi mari kita lihat beberapa efek samping lain dari memori, hal-hal yang bisa salah dan alat-alat yang dapat Anda gunakan untuk menangkap jenis-jenis kesalahan. Ternyata kalian semua, meskipun check50 tidak bilang banyak, telah menulis kereta Kode sejak pekan satu, bahkan jika semua tes yang check50 berlalu, dan bahkan jika Anda dan TF Anda super yakin bahwa kode Anda bekerja sebagaimana dimaksud. Kode Anda telah kereta atau cacat dalam bahwa semua Anda, dalam menggunakan perpustakaan CS50, telah bocor memori. Anda telah meminta sistem operasi untuk memori di sebagian besar program Anda sudah menulis, tapi kau pernah benar-benar diberikan kembali. Anda sudah disebut GetString dan getInt dan GetFloat, tetapi dengan GetString, Anda sudah tidak pernah disebut unGetString atau Berikan String Kembali atau sejenisnya, tapi kami telah melihat yang GetString tidak mengalokasikan memori dengan cara malloc atau ini fungsi realloc, yang hanya sangat mirip dalam roh, namun, kami sudah meminta sistem operasi untuk memori dan memori lagi dan lagi tetapi tidak pernah memberikan kembali. Sekarang, sebagai samping, ternyata ketika sebuah program berhenti, semua memori secara otomatis dibebaskan. Jadi itu tidak menjadi masalah besar. Itu tidak akan memecahkan IDE atau hal-hal memperlambat, tapi ketika program melakukan umumnya kebocoran memori dan mereka menjalankan untuk waktu yang lama. Jika Anda pernah melihat sedikit bodoh bola pantai di Mac OS atau jam pasir pada Windows mana itu jenis memperlambat atau berpikir atau berpikir atau hanya benar-benar dimulai untuk memperlambat merangkak, sangat mungkin bisa hasil dari kebocoran memori. Programmer yang menulis perangkat lunak yang Anda gunakan meminta sistem operasi untuk memori setiap beberapa menit, setiap jam. Tetapi jika Anda menjalankan software, bahkan jika itu diminimalkan di komputer Anda selama berjam-jam atau berhari-hari, Anda mungkin bertanya untuk lebih dan lebih memori dan tidak pernah benar-benar menggunakannya dan kode Anda mungkin, atau program mungkin bocor memori, dan jika Anda mulai bocor memori, ada sedikit memori untuk program lain, dan efeknya adalah untuk memperlambat semuanya. Sekarang, ini adalah jauh salah satu program yang paling mengerikan Anda akan memiliki kesempatan berjalan di sepanjang CS50 sebagai output bahkan lebih esoteris dari dentang atau membuat atau apapun perintah program baris kami sudah dijalankan sebelum tapi untungnya, tertanam dalam output adalah beberapa tips yang super membantu akan berguna baik untuk PSet empat atau pasti PSet lima. Jadi valgrind adalah alat yang dapat digunakan untuk melihat kebocoran memori dalam program Anda. Ini relatif sederhana untuk menjalankan. Anda menjalankan valgrind dan kemudian, bahkan meskipun itu adalah verbose sedikit, dasbor dasbor kebocoran cek sama penuh, dan kemudian dot tebang dan nama program Anda. Jadi valgrind kemudian akan menjalankan program Anda dan di akhir program Anda berjalan sebelum berhenti dan memberi Anda cepat lain, itu akan menganalisis Anda Program sementara itu sudah berjalan dan memberitahu Anda apakah Anda bocor setiap memori dan lebih baik lagi, apakah Anda menyentuh memori yang bukan milik Anda? Hal ini tidak bisa menangkap semuanya, tapi itu cukup baik menangkap banyak hal. Jadi, inilah contoh saya memiliki run program ini, memiliki jangka valgrind, pada program yang disebut memori, dan aku akan untuk menyoroti garis yang akhirnya menarik bagi kami. Jadi ada bahkan lebih gangguan bahwa saya telah dihapus dari slide. Tapi mari kita lihat apa ini Program ini mampu memberitahu kita. Ini mampu menceritakan hal-hal seperti menulis valid ukuran 4. Dengan kata lain, jika Anda menyentuh memori, khusus 4 byte memori bahwa Anda tidak harus memiliki, valgrind dapat memberitahu Anda bahwa. Menulis tidak valid ukuran 4. Anda menyentuh empat byte bahwa Anda tidak harus memiliki. Di mana Anda melakukan itu? Ini adalah keindahan. Memori dot c line 21 adalah di mana Anda kacau dan itulah mengapa itu membantu. Banyak seperti GDB itu, dapat membantu mengarahkan Anda pada kesalahan yang sebenarnya. Sekarang, yang satu ini lebih sedikit verbose, jika tidak membingungkan. 40 byte dalam 1 blok pasti hilang dalam catatan hilangnya 1 dari 1. Maksudnya itu apa? Nah, itu hanya berarti Anda meminta 40 byte dan Anda tidak pernah memberikannya kembali. Anda disebut malloc atau Anda disebut GetString dan sistem operasi memberi Anda 40 bytes, tapi Anda tidak pernah dibebaskan atau dilepaskan bahwa memori, dan untuk menjadi adil, kita tidak pernah menunjukkan Anda bagaimana untuk memberikan kembali memori. Ternyata ada super fungsi sederhana yang disebut bebas. Mengambil satu argumen, hal yang Anda ingin membebaskan atau memberikan kembali, tapi 40 byte, tampaknya, dalam program ini telah hilang pada baris 20 memori dot c. Jadi mari kita lihat program ini. Ini super berguna. Ini hanya menunjukkan kesalahan tertentu. Jadi mari kita lihat. Berikut adalah utama dan utama, pemberitahuan, panggilan fungsi disebut f dan kemudian kembali. Jadi tidak semua yang menarik. Apa f lakukan? Perhatikan Aku tidak repot-repot dengan prototipe. Saya ingin menjaga kode seminimal mungkin. Jadi saya menempatkan f diatas utama dan itu bagus, tentu, untuk program singkat seperti ini. Jadi f tidak kembali apa-apa dan tidak tidak mengambil apa-apa, tetapi tidak melakukan hal ini. Ini menyatakan, seperti dalam contoh Binky, pointer disebut x yang akan untuk menyimpan alamat int. Jadi itulah sisi kiri. Dalam bahasa Inggris, apa sisi melakukan kanan? Siapapun? Apa ini lakukan untuk kita? Ya? AUDIENCE: [tidak terdengar] kali ukuran sebuah int yang merupakan 10 kali [tidak terdengar] DAVID Malan: Baik dan biarkan saya meringkas. Jadi mengalokasikan cukup ruang untuk 10 bilangan bulat atau 10, apa ukuran int, itu empat byte, jadi 10 kali 4 adalah 40, sehingga sisi kanan bahwa saya telah disorot adalah memberi saya 40 byte dan menyimpan alamat dari byte pertama ke x. Dan sekarang terakhir, dan di sinilah program ini adalah kereta, apa salah dengan line 21 berdasarkan logika itu? Apa yang salah dengan line 21? Ya? AUDIENCE: Anda tidak bisa indeks ke x [tidak terdengar]. DAVID Malan: Ya. Saya tidak harus indeks ke x seperti itu. Jadi sintaksis, itu OK. Apa yang baik adalah, seperti Anda dapat mengobati nama array seolah itu pointer, sama dapat Anda memperlakukan pointer seolah itu array, dan jadi saya bisa sintaksis mengatakan x braket sesuatu, x braket i, tapi 10 bermasalah. Mengapa? AUDIENCE: Karena itu tidak di dalam. DAVID Malan: Ini tidak dalam yang sepotong memori. Apa nilai terbesar saya harus menempatkan pada mereka kurung? 9, 0 sampai 9. Karena nol pengindeksan. Jadi 0 sampai 9 akan baik-baik saja. Bracket 10 tidak baik dan tapi, ingat meskipun, setiap kali Saya tampaknya mencoba untuk membuat CS50 IDE kecelakaan dengan mengetikkan nilai palsu, itu tidak selalu bekerja sama, dan memang, Anda sering beruntung hanya karena sistem operasi tidak melihat bahwa Anda pernah jadi sedikit melewati beberapa sepotong memori, karena Anda tinggal dalam teknis segmen Anda, tetapi lebih pada di kelas sistem operasi, dan jadi sesuatu seperti ini bisa sangat mudah terdeteksi. Program Anda tidak akan pernah kecelakaan konsisten tapi mungkin sesekali. Dan mari kita coba valgrind ini, dan inilah di mana kita akan mendapatkan kewalahan oleh output sesaat. Sehingga membuat memori valgrind kebocoran cek sama penuh memori dot slash. Dan inilah mengapa saya berjanji ini akan membanjiri. Inilah yang valgrind, inilah yang programmer, beberapa tahun yang lalu- memutuskan itu akan menjadi ide yang baik untuk output terlihat seperti. Jadi mari kita memahami ini. Jadi semua jalan di kiri sisi tanpa alasan adalah proses ID dari program kita hanya menjalankan, pengenal unik untuk program kami hanya berlari. Kami dihapus bahwa dari slide, tetapi ada adalah beberapa informasi yang berguna di sini. Mari kita gulir ke atas ke bagian paling atas. Di sinilah kita mulai. Sehingga tidak semua yang banyak output. Berikut yang menulis valid ukuran 4 on line 21. Nah, apa line 21? Line 21 adalah persis ini dan itu masuk akal bahwa aku di sah menulis 4 byte karena aku mencoba untuk menempatkan bilangan bulat ini, yang bisa apa saja, itu hanya kebetulan nol, tapi aku berusaha untuk meletakkannya di lokasi yang bukan milik saya. Selain itu, di sini, 40 byte dalam satu blok pasti hilang dalam catatan 1. Itu karena ketika saya sebut malloc di sini, saya pernah benar-benar membebaskan memori. Jadi bagaimana kita bisa memperbaiki ini? Biarkan aku pergi ke depan dan menjadi sedikit lebih aman dan melakukan 9 di sana dan biarkan aku di sini gratis x. Ini adalah fungsi baru untuk hari ini. Jika saya sekarang jalankan kembali membuat memori dot slash, mari kita jalankan valgrind di atasnya lagi, memaksimalkan jendela dan tekan Enter. Sekarang, itu baik. Mereka mengubur kabar baik di semua output ini. Semua blok tumpukan bebas. Kami akan kembali ke apa heap , tapi tidak ada kebocoran yang mungkin. Jadi ini hanyalah alat untuk tool kit Anda dengan mana Anda dapat mulai untuk menemukan sekarang kesalahan seperti itu. Tapi mari kita lihat apa lebih bisa salah di sini. Mari transisi sekarang untuk benar-benar memecahkan masalah. Sebagai samping, apakah ini akan meredakan sedikit kebingungan atau ketegangan, ini sekarang lucu. Ya. Itu cukup bagus. Karena pointer alamat dan alamat umumnya dengan konvensi ditulis dengan heksadesimal. Ha, ha, ini lucu sekarang. Bagaimanapun, jadi mari kita sekarang benar-benar memecahkan masalah. Ini telah super, Super tingkat rendah sejauh ini, dan kita benar-benar bisa melakukan berguna hal dengan rincian tingkat rendah ini. Jadi kami memperkenalkan beberapa minggu lalu gagasan array. Array bagus karena sulit untuk membersihkan kode kita karena jika kita ingin menulis Program dengan beberapa siswa atau beberapa nama dan rumah dan asrama dan perguruan tinggi dan semua itu, kita bisa menyimpan segala sesuatu lebih bersih dalam array. Tapi mengusulkan satu kelemahan array sejauh ini. Bahkan jika Anda sudah tidak mengalami sendiri dalam sebuah program, hanya naluriah, apa adalah hal yang buruk tentang array, mungkin? Saya mendengar beberapa murmur. AUDIENCE: Sulit untuk mengubah ukuran. DAVID Malan: Sulit untuk mengubah ukuran. Anda tidak dapat mengubah ukuran array, pada kenyataannya, per se di C. Anda dapat mengalokasikan array lain, memindahkan segala sesuatu dari yang lama ke dalam baru, dan sekarang memiliki beberapa ruang tambahan, tapi itu tidak seperti bahasa seperti Java atau Python atau sejumlah lainnya bahasa dengan yang sebagian dari Anda mungkin akrab di mana Anda hanya bisa terus menambahkan hal-hal memuakkan ke akhir array. Bila Anda memiliki sebuah array ukuran 6, yaitu ukurannya, dan begitu banyak seperti ide awal memiliki buffer dengan ukuran tertentu, Anda harus menebak keluar dari gerbang apa ukuran yang Anda inginkan? Jika Anda menebak terlalu besar, Anda membuang-buang ruang. Jika Anda menebak terlalu kecil, Anda tidak bisa menyimpan data itu, setidaknya tanpa banyak pekerjaan lebih. Jadi hari ini, berkat pointer, kita bisa mulai menjahit kustom kita sendiri struktur data, dan di Bahkan, di sini adalah sesuatu yang terlihat sedikit lebih samar pada pandangan pertama, tapi ini adalah apa yang akan kita sebut terkait daftar, dan jenis namanya merangkum saya t. Ini daftar nomor, atau di kasus ini, daftar nomor, tapi bisa daftar apa-apa, tapi itu dihubungkan bersama dengan cara panah, dan hanya mengambil menebak dengan teknik apa kita akan dapat untuk menjahit bersama, semacam seperti popcorn dengan benang, sebuah linked list persegi panjang di sini? Jumlahnya? Apa fitur bahasa yang mendasari? AUDIENCE: Sebuah pointer. DAVID Malan: Sebuah pointer. Jadi setiap anak panah ini di sini mewakili pointer atau hanya alamat. Jadi dengan kata lain, jika saya ingin untuk menyimpan daftar nomor, Aku tidak bisa hanya menyimpannya jika saya ingin kemampuan untuk tumbuh dan menyusut struktur data saya dalam array. Jadi saya harus memiliki sedikit lebih kecanggihan, tapi melihat bahwa ini gambar jenis menyarankan bahwa jika Anda baru saja benang sedikit menghubungkan segala sesuatu bersama-sama, mungkin tidak sulit untuk membuat ruang di antara dua dari mereka persegi panjang atau dua dari mereka node, seperti yang kita akan mulai memanggil mereka, dimasukkan ke dalam simpul baru, dan kemudian dengan beberapa thread baru, hanya parit tiga node bersama-sama, yang pertama, yang terakhir, dan satu bahwa Anda hanya dimasukkan ke tengah. Dan memang sebuah linked list, tidak seperti array, bersifat dinamis. Hal ini dapat tumbuh dan itu bisa menyusut dan Anda tidak harus tahu atau peduli terlebih dahulu bagaimana banyak data Anda akan menyimpan, tapi ternyata kami harus sedikit hati-hati tentang bagaimana melaksanakan ini. Jadi pertama mari kita mempertimbangkan bagaimana kita menerapkan salah satu persegi panjang kecil. Sangat mudah untuk menerapkan int. Anda hanya mengatakan int n dan kemudian Anda mendapatkan 4 byte untuk int, tapi bagaimana saya mendapatkan int, sebut saja n, dan kemudian pointer, sebut saja berikutnya. Kita bisa menyebutnya hal apa pun yang kita inginkan tapi aku butuh struktur data kustom. Ya? AUDIENCE: Ampersand [tak terdengar]. DAVID Malan: Jadi ampersand akan kita gunakan untuk mendapatkan alamat dari simpul yang berpotensi. Tapi kita perlu lain Fitur dari C dalam rangka untuk memberikan kemampuan untuk membuat persegi panjang kebiasaan ini, kebiasaan ini variabel jika Anda mau, dalam memori. AUDIENCE: Sebuah struct. DAVID Malan: Sebuah struct. Ingat dari minggu lalu, kami memperkenalkan struct, kata kunci yang relatif sederhana ini yang memungkinkan kami melakukan hal-hal seperti ini. C tidak datang dengan data struktur disebut mahasiswa. Muncul dengan int dan mengambang dan char dan seperti itu, tapi itu tidak datang dengan siswa, tapi kita dapat membuat tipe data siswa, struktur siswa, dengan sintaks ini sini. Dan Anda akan melihat ini lagi dan lagi. Jadi jangan khawatir tentang menghafal kata kunci, tapi kata kunci yang penting adalah hanya fakta bahwa kita mengatakan struct dan kemudian kami menyebutnya mahasiswa dan di dalam siswa adalah nama dan rumah atau asrama atau sejenisnya. Dan jadi sekarang hari ini, mari kita mengusulkan ini. Saya telah menambahkan beberapa kata, tapi jika saya ingin untuk melaksanakan persegi panjang ini yang mendapat kedua int dan pointer, Anda tahu apa, aku akan mendeklarasikan struct disebut simpul. Saya juga, di dalamnya, akan mengatakan bahwa node, persegi panjang ini, memiliki int dan kami akan menyebutnya n dan memiliki pointer berikutnya. Dan ini sedikit verbose, tetapi jika Anda berpikir tentang hal itu, panah yang berada di gambar beberapa saat yang lalu adalah apa tipe data? Di mana masing-masing anak panah menunjuk untuk apa jenis struktur data? Ini tidak menunjuk hanya untuk int per se. Ini menunjuk ke Semuanya persegi panjang dan bahwa hal persegi panjang, kami katakan, disebut node. Dan jadi kita semacam harus rekursif menentukan ini seperti bahwa sebuah node, kita akan berkata, akan berisi int disebut n dan pointer disebut depan dan jenis struktur data yang yang poin pointer tampaknya akan menjadi struct simpul. Jadi ini mengganggu verbose dan hanya untuk menjadi bertele-tele, alasan mengapa kita tidak bisa hanya mengatakan ini, yang terus terang tampak jauh lebih mudah dibaca, karena ingat bahwa C baca hal atas ke bawah, kiri ke kanan. Ini tidak sampai kita mendapatkan titik koma bahwa simpul kunci benar-benar ada. Jadi jika kita ingin memiliki semacam ini referensi siklus dalam data struktur, kita harus melakukan ini, di mana kita katakan struct simpul di bagian atas, yang memberi kita cara yang lebih menggambarkan ini hal, kemudian di dalam kita katakan struct node, dan kemudian di garis yang terakhir kita katakan, baiklah, C, dengan cara, hanya memanggil seluruh sialan ini Hal node dan berhenti menggunakan struct kata kunci sama sekali. Jadi ini hanya semacam sintaksis trik yang pada akhirnya memungkinkan kita buat sesuatu yang tampak persis seperti ini. Jadi jika kita asumsikan sekarang kita bisa menerapkan hal ini di C, bagaimana kita benar-benar mulai melintasi ini? Nah, pada kenyataannya, yang harus kita lakukan adalah iterate dari kiri ke kanan dan hanya jenis menyisipkan node atau menghapus node atau mencari hal-hal di mana pun kita inginkan, tapi untuk melakukan hal ini, mari kita pergi ke depan dan membuat sesuatu yang sedikit lebih nyata karena ini telah super rendah tingkat sejauh ini. Apakah ada yang benar-benar ingin menjadi yang pertama? OKE. Ayo up. Siapa namamu? DAVID: David. DAVID Malan: David. Senang berjumpa dengan mu. Saya juga. Baiklah. Dan kita membutuhkan nomor 9. Tidak sebagus pertama, mungkin. OK, nomor 9. Sejumlah 17, silakan. Biarkan aku kembali sedikit lebih jauh. Nomor 22, silahkan, dan bagaimana jauh kembali jika saya bisa melihat tangan dengan semua cahaya atau tidak. Seseorang sedang mengajukan diri di sana. Apakah Anda ingin datang? Lengan Anda paksa naik. OK, 17. 22. 26 yang turun. Akan ada orang lain ingin forcefully-- Ayo up. Relawan yang sebenarnya. Jadi sangat cepat, jika kalian bisa mengatur dirimu hanya ingin node pada layar. Terima kasih. Dan Anda akan 26. Baiklah dan cepat perkenalan. Jadi aku David dan Anda juga? DAVID: David. DAVID Malan: Dan Anda? Jake: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID Malan: Taylor. Sangat baik. Jadi ini adalah sukarelawan kami untuk hari ini dan pergi ke depan dan bergeser sedikit seperti itu, dan hanya pergi ke depan dan tetap memegang nomor Anda seperti Anda atau Anda Tanda pertama dan menggunakan tangan kiri Anda, pergi ke depan dan hanya menerapkan panah tersebut, hanya sehingga tangan kiri Anda secara harfiah menunjuk pada apa pun yang Anda harus menunjukkan di, dan memberikan diri Anda beberapa ruang sehingga kita secara visual dapat melihat lengan Anda benar-benar menunjuk, dan Anda hanya bisa mengarahkan semacam di tanah baik-baik saja. Jadi di sini kita memiliki daftar link dari satu, dua, tiga, empat, lima node awalnya, dan perhatikan kami memiliki khusus ini pointer pada awal siapa kunci karena kita harus melacak daftar panjang keseluruhan entah bagaimana. Orang-orang ini, meskipun mereka meninggalkan ke kanan, kembali ke belakang dalam memori, mereka benar-benar dapat di mana saja di memori komputer. Jadi orang-orang ini bisa menjadi berdiri di mana saja di atas panggung dan itu bagus, asalkan mereka sebenarnya menunjuk satu sama lain, tetapi untuk menjaga hal-hal bersih dan sederhana, kami akan hanya menarik mereka kiri ke kanan seperti ini, namun mungkin ada kesenjangan besar di antara mereka node. Sekarang, jika saya ingin benar-benar memasukkan beberapa nilai baru, mari kita pergi ke depan dan melakukan hal ini. Kami memiliki kesempatan sekarang untuk memilih node lain. Mengatakan mari kita mulai dengan mallocing 55. Apakah seseorang keberatan malloc? OK, datang ke atas. Siapa namamu? RAINBOW: Rainbow. DAVID Malan: Rainbow? Baiklah. Malloc Rainbow. Ayo up. Jadi sekarang kita harus bertanya pada diri sendiri algorithmically mana kita dapat menempatkan 55. Jadi kita semua tahu, jelas, mana mungkin dia milik jika kita mencoba untuk menjaga ini diurutkan dan jika kalian bisa mengambil satu melangkah mundur sehingga kita tidak jatuh panggung, yang akan menjadi besar. Jadi sebenarnya, Rainbow, mulai di sini dengan saya, karena kita sebagai komputer sekarang dapat hanya melihat satu variabel pada suatu waktu. Jadi jika ini adalah simpul pertama. Perhatikan dia tidak node, dia hanya pointer, dan itulah sebabnya dia ditarik menjadi hanya ukuran pointer, tidak salah satu persegi panjang penuh. Jadi kita akan memeriksa pada setiap iterasi adalah 55 kurang dari 9? Tidak. Apakah 55 kurang dari 17? Tidak. Kurang dari 22? Kurang dari 26? Kurang dari 34? Dan sekarang, jelas Rainbow milik di akhir. Jadi harus jelas, dan apa adalah nama Anda, Taylor? TAYLOR: Taylor. DAVID Malan: Jadi antara Taylor tangan kiri dan tangan Rainbow di sini, tangan yang perlu untuk menunjuk pada apa yang di memesan untuk memasukkan ke dalam daftar 55 ini? Apa yang perlu kita lakukan? Ya? AUDIENCE: tangan Taylor perlu untuk menunjuk kiri. DAVID Malan: Tepat. Jadi memasukkan node ke akhir daftar cukup sederhana karena hanya Taylor harus menunjuk, bukan di tanah atau kita akan menyebutnya nol, nol adalah semacam ketidakhadiran dari pointer atau khusus nol pointer, Anda akan menunjukkan dengan kiri Anda tangan di Rainbow dan kemudian Rainbow, di mana harus kiri Anda tangan mungkin menunjuk? Down. Ini tidak baik jika tangannya adalah semacam menunjuk off di sini atau semacam apapun jalan yang mana. Yang akan dianggap nilai sampah, tetapi jika ia menunjuk ke beberapa nilai yang dikenal, kita akan menyebutnya nol atau nol, itu OK karena kita memiliki istilah dalam ini dan kita tahu daftar sekarang selesai. Jadi apa lagi kasus yang relatif sederhana? Bisakah kita malloc 5? Ayo up. Siapa namamu? TIFFANY: Tiffany. DAVID Malan: Maaf? TIFFANY: Tiffany. DAVID Malan: Tiffany. Baiklah. Tiffany telah malloced dengan nilai 5. Ayo up. Yang satu ini relatif mudah juga, tapi mari kita mempertimbangkan urutan operasi sekarang. Itu cukup mudah dengan Taylor di akhir. Nomor 5 ini tentu saja kurang dari 9, dan jadi kita harus David, kita memiliki Tiffany, dan apa nama Anda? Jake: Jake. DAVID Malan: Jake. Tiffany, Jake, dan David. Yang tangan harus diperbarui pertama? Apa yang Anda ingin lakukan di sini? Ada beberapa cara yang mungkin, tapi ada juga satu atau cara yang lebih salah. AUDIENCE: Mulailah dengan yang paling kiri. DAVID Malan: Mulailah dengan yang paling kiri. Siapa paling kiri di sini? AUDIENCE: Pertama. DAVID Malan: OK. Jadi mulai dengan pertama dan mana Anda ingin memperbarui tangan Daud menjadi? AUDIENCE: Menjelang 5. DAVID Malan: OK. Jadi David, titik di lima atau Tiffany sini, dan sekarang? AUDIENCE: Tiffany menunjuk ke 9? DAVID Malan: Sempurna, kecuali Binky ini kepala hanya jenis jatuh, kan? Karena apa yang salah dengan gambar ini benar? AUDIENCE: Tidak ada yang menunjuk. DAVID Malan: Tidak ada yang menunjuk ke Jake sekarang. Kami telah benar-benar yatim 9 dan 17, dan kami sudah benar bocor semua memori ini, karena dengan memperbarui tangan David pertama, yang baik sejauh itu benar menunjuk Tiffany sekarang, tetapi jika tidak ada yang memiliki kejelian untuk menunjuk Jake, maka kita telah kehilangan keseluruhan daftar itu. Jadi mari kita batalkan. Jadi itu hal yang baik untuk tersandung tapi mari kita perbaiki sekarang. Apa yang harus kita lakukan pertama bukan? Ya? AUDIENCE: Tiffany harus menunjuk pada 9? DAVID Malan: Saya tidak bisa mendapatkan yang dekat dengan Anda. Siapa yang harus menunjuk pada 9? AUDIENCE: Tiffany. DAVID Malan: Baiklah. Jadi Tiffany harus titik pertama di 9. Jadi Tiffany harus mengambil pada nilai yang identik David, yang tampaknya berlebihan sesaat, tapi itu baik-baik saja karena sekarang, kedua langkah, kita dapat memperbarui tangan David untuk menunjuk Tiffany, dan kemudian jika kita hanya jenis bersih segalanya seolah-olah ini adalah jenis semi-seperti, sekarang itu pemasangan yang benar. Jadi sangat baik. Jadi sekarang kita sudah hampir sampai. Mari kita memasukkan satu akhir nilai seperti nilai 20. Jika kita bisa malloc satu relawan akhir? Ayo up. Jadi yang satu ini sedikit lebih rumit. Tapi benar-benar, kode kami menulis, meskipun secara lisan, adalah seperti memiliki a bunch dari jika kondisi sekarang, kan? Kami memiliki kondisi memeriksa apakah itu milik pada akhir, mungkin awal. Kami memerlukan beberapa jenis loop untuk menemukan tempat di tengah. Jadi mari kita melakukannya dengan siapa namamu? ERIC: Eric. DAVID Malan: Eric? Eric. Senang berjumpa dengan mu. Jadi kita memiliki 20. Kurang dari lima? Tidak. Kurang dari sembilan? Tidak. Kurang dari 17? Tidak. OKE. Dia berada di sini dan Nama Anda lagi adalah? SUE: Sue. DAVID Malan: Sue. ALEX: Alex. DAVID Malan: Sue, Alex, dan? ERIC: Eric. DAVID Malan: Eric. Tangan yang perlu mendapatkan update pertama? AUDIENCE: Eric. OKE. Jadi Eric harus menunjuk di mana? Pada 22. Baik. Dan sekarang apa berikutnya? Sue kemudian dapat menunjuk Eric dan sekarang, jika kalian hanya membuat beberapa kamar, yang baik-baik saja visual, sekarang kita sudah melakukan penyisipan. Jadi mari kita sekarang mempertimbangkan pertanyaan tapi terima kasih banyak untuk relawan kami. Bagus sekali. Anda dapat menjaga mereka, jika Anda suka. Dan kami memiliki hadiah perpisahan indah jika Anda akan setiap ingin mengambil bola stres. Mari saya hanya lulus ini turun. Jadi apa adalah takeaway dari ini? Hal ini tampaknya menjadi luar biasa sejauh yang kita miliki sekarang memperkenalkan alternatif untuk sebuah Array yang tidak begitu terbatas ke array beberapa ukuran tetap. Mereka dapat tumbuh secara dinamis. Tapi seperti yang telah kita lihat dalam beberapa pekan masa lalu, kita tidak pernah mendapatkan sesuatu secara gratis, seperti pasti ada trade-off di sini. Jadi dengan terbalik dari terkait daftar, adalah dinamisme ini? Kemampuan untuk tumbuh dan terus terang, kita bisa melakukan hapus dan kita bisa menyusut sesuai kebutuhan. Berapa harga yang kita bayar? Dua kali lebih banyak ruang, pertama-tama. Jika Anda melihat gambar, tidak lagi aku menyimpan daftar bilangan bulat. Aku menyimpan daftar bilangan bulat ditambah pointer. Jadi aku menggandakan jumlah ruang. Sekarang, mungkin itu tidak seperti masalah besar 4 byte, 8 byte, tapi itu pasti bisa menambahkan untuk set data yang besar. Apa downside lain? Ya? AUDIENCE: Kita harus melintasi mereka satu-per-satu. DAVID Malan: Ya. Kami harus melintasi mereka satu-per-satu. Anda tahu apa, kita menyerah super fitur yang mudah dari braket persegi notasi, lebih tepat dikenal sebagai akses acak, di mana kita hanya bisa melompat untuk elemen individual tapi sekarang jika saya masih memiliki relawan saya di sini, jika saya ingin menemukan nomor 22, saya tidak bisa hanya melompat ke braket sesuatu sesuatu. Saya harus melihat daftar itu, banyak seperti contoh pencarian kami linear, untuk menemukan nomor 22. Jadi kita tampaknya telah membayar harga di sana. Tapi kita bisa tetap memecahkan masalah lainnya. Bahkan, izinkan saya memperkenalkan hanya beberapa visual. Jadi jika Anda sudah pernah ke Mather Dining Hall baru, Anda akan ingat bahwa mereka tumpukan nampan seperti ini, kami meminjam ini dari Annenberg sebelum kelas. Jadi tumpukan ini nampan, meskipun, adalah perwakilan sebenarnya dari struktur data ilmu komputer. Ada struktur data dalam ilmu komputer dikenal sebagai stack yang sangat baik cocok untuk persis ini visual. Jadi jika masing-masing nampan tersebut bukan baki tapi seperti nomor dan saya ingin untuk menyimpan nomor, saya bisa menempatkan satu di sini, dan aku bisa meletakkan lain di sini, dan terus menumpuk nomor di atas satu sama lain, dan apa yang berpotensi membantu tentang ini adalah bahwa apa implikasinya dari struktur data? Yang nomor dapat saya tarik keluar pertama yang paling mudah? Yang paling baru-baru ini salah satu put di sana. Jadi ini adalah apa yang kita sebut di ilmu komputer struktur data LIFO. Bertahan di, keluar pertama. Dan kita akan melihat tak lama mengapa yang mungkin berguna tetapi untuk sekarang, hanya mempertimbangkan properti. Dan itu agak bodoh jika Anda berpikir tentang bagaimana ruang makan melakukannya. Setiap kali mereka nampan bersih dan menempatkan orang-orang segar di atas, Anda bisa memiliki sebelumnya bersih tapi akhirnya sangat kotor dan berdebu baki di bagian paling bawah jika Anda pernah benar-benar sampai ke bawah yang stack, karena Anda hanya tetap menempatkan yang baru dan yang bersih di atasnya. Hal yang sama mungkin terjadi di supermarket juga. Jika Anda memiliki kasus layar susu dan setiap kali CVS atau siapa pun yang mendapatkan lebih banyak susu, Anda hanya mendorong para susu Anda sudah harus kembali dan Anda menempatkan yang baru di depan, Anda akan memiliki beberapa cukup menjijikkan susu pada akhir struktur data, karena selalu di bagian bawah atau ekuivalen itu selalu di belakang. Tapi ada cara lain untuk berpikir tentang berbaris data dan misalnya, ini. Jika Anda salah satu dari orang-orang yang suka berbaris di luar toko-toko Apple ketika sebuah produk baru datang keluar, Anda mungkin tidak menggunakan data tumpukan struktur karena Anda akan mengasingkan orang lain yang berbaris untuk membeli beberapa mainan baru. Sebaliknya, Anda mungkin menggunakan jenis struktur data atau apa jenis sistem di dunia nyata? Mudah-mudahan itu garis, atau lebih benar atau lebih British-seperti, antrian. Dan ternyata antrian juga struktur data dalam ilmu komputer, tapi antrian memiliki sangat properti yang berbeda. Ini bukan LIFO. Bertahan di, keluar pertama. Amit-amit. Ini bukan FIFO. Pertama masuk pertama keluar. Dan itu adalah hal yang baik untuk 'demi keadilan tentu ketika Anda lapisan super awal di pagi hari. Jika Anda sampai di sana pertama, Anda ingin keluar pertama juga. Dan semua data ini struktur, antrian dan tumpukan dan tandan lain, ternyata Anda dapat menganggap ini sebagai hanya sebuah array. Ini adalah sebuah array, mungkin ukuran tetap 4, tapi itu akan menjadi baik jika kita hanya bisa menumpuk nampan hampir tak terhingga tinggi jika kita memiliki banyak nampan atau angka. Jadi mungkin kita ingin menggunakan daftar link di sini, tapi trade-off akan menjadi berpotensi bahwa kita membutuhkan lebih banyak memori, Dibutuhkan sedikit lebih banyak waktu, tapi kami tidak membatasi ketinggian tumpukan, seperti etalase Mather mungkin membatasi ukuran stack, dan jadi ini adalah keputusan desain atau pilihan yang tersedia bagi kita akhirnya. Jadi dengan data ini struktur, kita sudah mulai melihat batas atas baru berpotensi pada apa yang sebelumnya adalah super cepat dan di mana kita akan meninggalkan off hari ini dan di mana kita akan berharap untuk mendapatkan adalah pada hari Rabu, kami akan mulai melihat data struktur yang memungkinkan kita mencari melalui data dalam log waktu akhir lagi. Dan kita melihat bahwa, mengingat, dalam seminggu nol dan satu dengan pencarian biner atau membagi dan menaklukkan. Itu datang kembali dan lebih baik lagi, grail suci untuk Rabu ini akan datang dengan struktur data yang berjalan benar-benar atau secara teoritis di waktu yang konstan, dimana tidak peduli berapa banyak jutaan atau milyaran hal kita miliki dalam struktur data, maka akan membawa kita waktu yang konstan, mungkin satu langkah atau dua langkah atau 10 langkah, tetapi jumlah konstan langkah untuk mencari melalui struktur data. Bahwa memang akan menjadi holy grail tetapi lebih pada Rabu. Lihat ya kemudian. [MUSIC PLAYING]