DAVID Malan: Baiklah, selamat datang kembali. Ini adalah CS50. Ini adalah awal minggu ketujuh. Jadi sudah lama, jadi saya pikir kami akan mengambil tur angin puyuh di mana kita tinggalkan dan di mana kita sekarang pergi. Jadi hal ini di sini mungkin menyebabkan beberapa kecemasan pada awalnya. Tapi mudah-mudahan, Anda mulai menyesuaikan diri dengan apa menunjukkan di sini - star mewakili pointer, yang apa, dalam istilah yang lebih awam? Jadi alamat. Jadi alamat sesuatu dalam memori. Dan kami mulai mengupas lapisan-lapisan beberapa minggu yang lalu, hal-hal seperti GetString dan fungsi lainnya seperti selama ini telah kembali alamat hal dalam memori, seperti alamat dari karakter pertama dalam beberapa urutan. Jadi kami juga memperkenalkan Valgrind, yang Anda akan mulai digunakan untuk masalah ini ditetapkan, terutama untuk selanjutnya Masalah ditetapkan juga. Dan Valgrind melakukan apa bagi kita? Ia memeriksa kebocoran memori, dan juga memeriksa penyalahgunaan memori. Hal ini dapat, dengan beberapa probabilitas, mendeteksi jika kode Anda akan menyentuh memori bahwa itu hanya tidak seharusnya. Jadi belum tentu kebocoran, tetapi jika Anda melampaui batas-batas beberapa array, dan Anda benar-benar menjalankan valgrind dan mendorong perilaku bahwa sementara Valgrind berjalan dalam program anda adalah berjalan di dalamnya, Anda akan mendapatkan pesan seperti ini - "tidak valid menulis dari ukuran 4, "yang, mengingat beberapa minggu lalu berarti bahwa aku sengaja seperti pada satu int terlalu jauh melampaui batas-batas array. Dan sehingga ukuran 4 berarti di sini ukuran itu int tertentu. Jadi mengambil kepastian dalam kenyataan bahwa Output Valgrind, format itu, hanya mengerikan. Ini benar-benar sulit untuk melihat melalui kekacauan untuk informasi menarik. Jadi apa yang kami lakukan di sini hanya kutipan beberapa beberapa lebih garis menarik. Tapi menyadari bahwa 80% dari Valgrind ini output akan menjadi sedikit gangguan. Hanya mencari pola seperti ini - valid benar, valid baca, 40 byte dan beberapa jumlah blok yang pasti hilang, kata kunci seperti itu. Dan apa yang Anda mudah-mudahan akan melihat beberapa jenis jejak apa fungsi yang kesalahan sebenarnya masuk Dalam hal ini di sini, dalam apa garis kode saya adalah kesalahan rupanya? 26 dalam sebuah file bernama memory.c, yang contoh kami bermain dengan pada saat itu. Jadi mungkin tidak dalam malloc. Itu mungkin dalam kode saya sebaliknya. Jadi kita akan melihat ini lagi dan sekali lagi sebelum lama. Jadi scanf, ini datang dalam beberapa bentuk sejauh ini. Kami melihat sscanf sebentar. Itu adalah sesuatu yang sejumlah Anda menyelam ke dalam Anda persiapan untuk kuis. Dan scanf sebenarnya apa CS50 perpustakaan telah menggunakan bawah hood untuk beberapa waktu dalam rangka untuk mendapatkan input dari user. Misalnya, jika saya pindah ke CS50 alat di sini, biarkan aku membuka sebuah Misalnya hari ini yang disebut-scanf 0.c Dan itu super sederhana. Ini hanya beberapa baris kode. Tapi itu menunjukkan benar-benar bagaimana getInt telah bekerja sepanjang waktu ini. Dalam program ini di sini, di baris 16 , Perhatikan bahwa saya menyatakan int. Jadi tidak ada pointer, tidak ada yang ajaib di sana, hanya sebuah int. Kemudian pada baris 17, saya meminta pengguna untuk nomor, silakan. Kemudian pada akhir 18, saya menggunakan scanf sini. Dan saya ditentukan, jenis seperti printf, bahwa aku mengharapkan kutipan tanda kutip persen i. Jadi persen i, tentu saja, menunjukkan sebuah int. Tapi perhatikan apa yang kedua argumen ke scanf adalah. Bagaimana Anda menggambarkan kedua Argumen setelah koma? Apa itu? Ini alamat x. Jadi ini adalah berguna karena dengan memberikan scanf dengan alamat x, apa yang memberdayakan fungsi yang harus dilakukan? Tidak hanya pergi ke sana, tetapi juga melakukan apa? Membuat perubahan untuk itu. Karena Anda dapat pergi ke sana, itu semacam seperti peta ke lokasi dalam memori. Dan selama Anda memberikan scanf, atau fungsi apapun dengan peta tersebut, bahwa Fungsi bisa pergi ke sana, dan tidak hanya melihat nilai, tetapi juga dapat mengubah nilai yang, yang berguna jika tujuan dalam hidup adalah untuk scanf memindai masukan dari pengguna, khususnya dari keyboard. Dan f menunjukkan diformat, seperti printf, f menunjukan suatu diformat string yang akan dicetak. Jadi singkatnya, baris ini 18 hanya mengatakan, mencoba untuk membaca int dari pengguna keyboard dan menyimpannya dalam x, pada alamat apapun x kebetulan tinggal di. Dan kemudian terakhir, baris 19 hanya mengatakan, terima kasih untuk int, dalam kasus ini. Jadi biarkan aku pergi ke depan dan membuat ini. Jadi membuat scanf 0. Biarkan aku pergi ke depan dan zoom in Aku akan pergi dan menjalankan ini dengan titik memangkas scanf 0. Nomor, please? 50. Terima kasih untuk 50. Jadi itu cukup sederhana. Sekarang apa yang tidak lakukan? Ini tidak melakukan seluruh bunch dari pengecekan error. Misalnya, jika saya tidak bekerja sama, dan saya tidak mengetikkan nomor, tetapi bukannya saya menulis sesuatu seperti "halo," itu hanya semacam aneh. Dan salah satu hal yang CS50 perpustakaan telah melakukan bagi kita untuk beberapa adalah reprompting yang dan reprompting. Coba lagi ingat frase berada di cs50.c, dan itulah alasan bahwa getInt di perpustakaan CS50 sebenarnya keseluruhan sekelompok garis panjang, karena kita memeriksa hal-hal bodoh seperti ini. Apakah pengguna tidak memberikan kita, pada kenyataannya, int? Apakah dia memberi kita sesuatu seperti surat abjad? Jika demikian, kita ingin mendeteksi itu dan berteriak pada mereka. Tapi hal-hal mendapatkan lebih menarik dalam contoh berikut ini. Jika saya pergi ke scanf-1.c, apa yang hal yang berubah secara fundamental dalam ini contoh berikut ini? Saya menggunakan char *, tentu saja, bukannya int. Jadi ini menarik, karena char *, ingat, benar-benar hanya Hal yang sama sebagai string. Jadi rasanya mungkin ini adalah super implementasi sederhana dari GetString. Tapi aku sudah dikupas kembali layer dari CS50 perpustakaan, jadi saya menyebutnya char * sekarang. Jadi mari kita lihat di mana, jika di mana saja, kami salah. Baris 17 - Lagi saya katakan, tolong beri saya sesuatu, dalam hal ini, string. Dan kemudian di baris berikutnya, saya sebut scanf, lagi, memberikan kode format, tapi ini persen waktu s. Dan kemudian saat ini, aku memberikan penyangga. Sekarang perhatikan, aku tidak menggunakan ampersand. Tapi kenapa begitu mungkin OK di sini? Karena apa yang sudah penyangga? Ini sudah pointer. Ini sudah alamat. Dan mari kita kata ini "membingungkan," biarkan aku sebut saja s, misalnya, untuk kesederhanaan. Tapi aku menyebutnya penyangga karena dalam umum, dalam pemrograman, jika Anda memiliki sepotong memori, yang string benar hanya itu, Anda mungkin menyebutnya buffer. Ini adalah tempat untuk menyimpan informasi. Serupa dengan hal-hal seperti YouTube, ketika mereka buffering, sehingga untuk berbicara, bahwa hanya berarti itu men-download bit dari internet dan menyimpannya dalam array yang lokal, sepotong lokal memori sehingga bahwa Anda dapat melihatnya kemudian tanpa itu melompat-lompat atau tergantung di Anda saat bermain kembali. Jadi ada masalah di sini meskipun, karena aku mengatakan scanf, mengharapkan string dari pengguna. Berikut alamat sepotong memori. Masukan string di sana. Kenapa begitu terikat memberikan kami kesulitan, meskipun? Apa itu? Apakah saya diizinkan untuk mengakses bagian dari memori? Kau tahu, aku tidak tahu. Karena telah penyangga diinisialisasi apa-apa? Tidak benar-benar. Dan jadi apa yang kita telah memanggil nilai sampah, yang bukan kata formal. Itu hanya berarti kita tidak tahu apa bit yang dalam empat byte yang Saya telah dialokasikan sebagai penyangga. Saya tidak menelepon malloc. Aku sudah pasti tidak disebut GetString. Jadi siapa yang tahu apa yang sebenarnya dalam buffer? Namun mengatakan scanf membabi buta, pergi ke sana dan menempatkan apa pun pengguna mengetik. Jadi apa yang mungkin menyebabkan dalam kode kita jika kita menjalankannya? Mungkin segfault. Mungkin tidak, tapi mungkin segfault. Dan saya mengatakan mungkin bukan karena kadang-kadang Anda lakukan, kadang-kadang Anda tidak mendapatkan segfault. Kadang-kadang Anda hanya beruntung, tapi itu tetap akan menjadi bug di program kami. Jadi biarkan aku pergi ke depan dan kompilasi ini. Aku akan melakukannya dengan cara lama sekolah. Jadi dentang dasbor 0, scanf-1, scanf-1.c, Enter. Ups, sekolah terlalu tua. Mari kita lihat. Mana aku pergi? Oh, char * buffer. Oh, terima kasih - Simpan, OK - sekolah sangat tua. Baiklah, itu sudah lama. Jadi saya baru saja menyimpan file setelah keputusan yang sementara mengubah beberapa saat yang lalu. Dan sekarang aku telah dikompilasi manual dengan dentang. Dan sekarang aku akan pergi ke depan dan menjalankan scanf-1, Enter. String silakan. Aku akan mengetik "halo." Dan sekarang, di sinilah, terus terang, printf dapat sedikit mengganggu. Ini tidak benar-benar akan segfault dalam kasus ini. Printf sedikit istimewa karena itu begitu super yang biasa digunakan printf dasarnya adalah melakukan kami mendukung dan menyadari, itu bukan pointer yang valid. Biarkan aku mengambil itu atas diri untuk hanya mencetak dalam kurung nol, bahkan meskipun tidak selalu apa kita sendiri diharapkan. Jadi kita tidak bisa benar-benar mudah menginduksi segfault dengan ini, tapi jelas ini bukanlah perilaku yang saya inginkan. Jadi apa solusi sederhana? Nah, dalam scanf-2, saya mengusulkan bahwa bukan benar-benar hanya mengalokasikan char *, biarkan aku menjadi sedikit lebih cerdas tentang ini, dan biarkan aku mengalokasikan buffer sebagai urutan 16 karakter. Jadi saya bisa melakukan ini dalam beberapa cara. Aku benar-benar bisa menggunakan malloc. Tapi aku bisa kembali ke dua minggu ketika Aku hanya perlu sejumlah besar karakter. Itu hanya sebuah array. Jadi biarkan saya bukan mendefinisikan penyangga menjadi sebuah array dari 16 karakter. Dan sekarang, ketika saya melewati buffer - dan ini adalah sesuatu yang kita tidak berbicara tentang dalam dua minggu - tetapi Anda dapat memperlakukan sebuah array sebagai meskipun itu alamat. Secara teknis, seperti yang kita lihat, mereka sedikit berbeda. Tapi scanf tidak akan keberatan jika Anda lulus nama array, karena apa yang Dentang akan lakukan untuk kita pada dasarnya memperlakukan nama array sebagai alamat sepotong 16 byte. Jadi ini lebih baik. Ini berarti sekarang aku bisa diharapkan lakukan hal berikut. Mari saya zoom out sejenak dan melakukan make scanf-2, dikompilasi OK. Sekarang mari saya lakukan mendapat slash scanf-2. String silakan. "Halo." Dan tampaknya bekerja saat ini. Tapi bisa seseorang mengusulkan skenario di mana tidak mungkin masih bekerja? Ya? Sesuatu lebih panjang dari 16 karakter. Dan sebenarnya, kita bisa sedikit lebih tepat. Sesuatu lagi maka 15 karakter, karena memang kita perlu diingat bahwa kita membutuhkan backslash nol implisit pada akhir string, yang merupakan samping scanf biasanya akan mengurus bagi kita. Jadi biarkan aku melakukan sesuatu seperti - kadang-kadang kita bisa hanya biarkan seperti itu. OK, jadi sekarang kami telah diinduksi segmentasi kesalahan kita. Kenapa? Karena aku mengetik lebih dari 15 karakter, dan jadi kita sudah benar-benar menyentuh memori yang saya benar-benar tidak seharusnya. Jadi apa yang benar-benar solusi di sini? Nah, bagaimana jika kita membutuhkan string lagi? Yah, mungkin kita membuat 32 byte. Nah, bagaimana jika itu tidak cukup lama? Bagaimana sekitar 64 byte? Bagaimana jika itu tidak cukup lama? Bagaimana sekitar 128 atau 200 byte? Yang benar-benar adalah solusi di sini di kasus umum, jika kita tidak tahu memajukan apa pengguna akan mengetik? Ini hanya semacam sakit besar di pantat, harus jujur, itulah sebabnya mengapa CS50 perpustakaan memiliki beberapa lusin baris dari kode yang secara kolektif menerapkan GetString string dalam cara yang kita tidak harus tahu terlebih dahulu apa yang pengguna akan mengetik. Secara khusus, jika Anda melihat kembali cs50.c dari dua minggu lalu, Anda akan melihat GetString yang sebenarnya tidak menggunakan scanf dengan cara ini. Sebaliknya, ia membaca satu karakter pada suatu waktu. Karena satu hal yang menyenangkan tentang membaca satu karakter adalah kita bisa menjamin diri kita untuk selalu memiliki setidaknya satu char. Aku hanya bisa mendeklarasikan char, dan kemudian mengambil langkah-langkah yang benar-benar bayi hanya membaca satu karakter di di waktu dari keyboard. Dan kemudian, apa yang Anda akan melihat GetString dilakukan adalah setiap kali kehabisan, mengatakan, 16 byte memori, menggunakan malloc, atau sepupu daripadanya, untuk mengalokasikan lebih banyak memori, menyalin tua memori ke yang baru, dan kemudian merangkak bersama, mendapatkan satu karakter pada satu waktu, dan ketika berjalan keluar dari itu sepotong memori, membuangnya, diperebutkan sepotong besar memori, salinan tua ke yang baru, dan mengulangi. Dan itu benar-benar sakit untuk benar-benar menerapkan sesuatu yang sederhana seperti mendapatkan masukan dari pengguna. Sehingga Anda dapat menggunakan scanf. Anda dapat menggunakan fungsi serupa lainnya. Dan banyak buku dan online contoh lakukan, tapi mereka semua rentan terhadap masalah seperti ini. Dan akhirnya, mendapatkan segfault adalah jenis menjengkelkan. Ini tidak baik bagi pengguna. Tapi dalam kasus terburuk, apa itu dasarnya menempatkan Anda Kode beresiko? Beberapa jenis serangan, berpotensi. Kami berbicara tentang satu serangan tersebut - meluap stack. Tapi secara umum, jika Anda diperbolehkan untuk buffer overflow, seperti yang kita melakukan beberapa minggu yang lalu, dengan hanya menulis lebih dari "halo" di stack, Anda memang bisa mengambil alih, berpotensi, komputer, atau setidaknya mendapatkan data yang bukan milik Anda. Jadi singkatnya, ini adalah mengapa kita memiliki mereka roda pelatihan. Tapi sekarang, kita mulai mengambil mereka pergi, sebagai program kami tidak perlu lagi, tentu, masukan dari pengguna. Tapi dalam kasus masalah menetapkan enam, masukan Anda akan datang dari besar kamus berkas dengan 150 beberapa aneh seribu kata. Jadi Anda tidak perlu khawatir tentang sewenang-wenang input pengguna. Kami akan memberikan beberapa asumsi tentang file itu. Setiap pertanyaan tentang pointer atau scanf atau input pengguna pada umumnya? Baiklah, jadi sekilas kemudian pada satu mengikuti topik dari dua minggu lalu. Dan itu gagasan ini struct. Bukan berarti - ini gagasan struct, yang adalah apa? Apa struct lakukan untuk kita? Tentukan - maaf? Tentukan jenis variabel. Jadi semacam. Kami benar-benar menggabungkan dua topik. Jadi dengan typedef, ingat bahwa kita bisa menyatakan jenis kita sendiri, seperti sinonim, seperti string char *. Tetapi menggunakan typedef struct dan, kita bisa membuat struktur data yang benar-benar kita sendiri. Misalnya, jika saya kembali ke gedit di sini untuk sesaat, dan aku pergi ke depan dan melakukan sesuatu seperti, membiarkan saya menyimpan ini sebagai, katakanlah, structs.c sementara, aku hanya akan untuk terus maju dan termasuk standardio.h, void main int. Dan kemudian di sini, anggaplah bahwa saya ingin untuk menulis sebuah program yang menyimpan beberapa mahasiswa dari beberapa rumah, misalnya. Jadi seperti registrarial Database dari beberapa macam. Jadi jika saya membutuhkan satu siswa nama, saya mungkin melakukan sesuatu seperti nama * char, dan saya akan melakukan sesuatu seperti - sebenarnya, mari kita gunakan CS50 perpustakaan untuk sesaat untuk membuat ini sedikit lebih sederhana, sehingga kami dapat meminjam mereka puluhan baris kode. Dan mari saja tetap sederhana. Kami akan tetap tali, dan sekarang getString. Jadi saya mengklaim sekarang bahwa saya telah disimpan nama beberapa mahasiswa, dan rumah beberapa siswa, hanya menggunakan variabel seperti yang kita lakukan dan dalam satu minggu. Tapi bagaimana kalau sekarang saya ingin mendukung beberapa siswa. Baiklah, jadi naluri saya lakukan String name2, mendapat GetString, tali house2 mendapat GetString. Dan kemudian mahasiswa ketiga kami, mari kita lakukan name3 GetString. Baiklah, jadi ini mudah-mudahan mencolok Anda sebagai agak bodoh, karena proses ini benar-benar tidak pernah akan berakhir, dan itu hanya akan membuat kode saya terlihat buruk dan lebih buruk dan lebih buruk. Tapi kita memecahkan ini juga dalam dua minggu. Apa solusi kami relatif bersih ketika kami memiliki beberapa variabel dari sama tipe data yang semuanya berhubungan, tetapi kami tidak ingin kekacauan ini mengerikan variabel bernama sama? Apa yang kita lakukan, bukan? Jadi saya pikir saya mendengar beberapa tempat. Kami memiliki sebuah array. Jika Anda ingin beberapa contoh sesuatu, kenapa tidak kita membersihkan semua ini dan hanya mengatakan, beri saya array disebut nama? Dan untuk saat ini, mari kita 3 kode keras. Dan kemudian memberikan array lain disebut rumah, dan biarkan aku untuk sekarang kode keras 3. Dan aku besar-besaran merapikan mengacaukan yang saya buat. Sekarang, aku masih sulit kode 3, tapi bahkan 3 secara dinamis bisa datang dari pengguna, atau argv, atau sejenisnya. Jadi ini sudah bersih. Tapi apa yang menjengkelkan tentang ini adalah bahwa sekarang, nama meskipun entah bagaimana fundamental terkait dengan rumah siswa - itu adalah mahasiswa yang benar-benar ingin mewakili - Saya sekarang memiliki dua array yang sejajar dalam arti bahwa mereka adalah ukuran yang sama, dan nama braket 0 mungkin peta ke rumah braket 0, dan nama braket 1 peta ke rumah braket 1. Dengan kata lain, hidup mahasiswa bahwa dalam rumah itu, dan bahwa siswa lainnya hidup dalam rumah yang lain. Tapi tentunya ini bisa menjadi dilakukan bahkan lebih bersih. Yah, itu bisa, pada kenyataannya. Dan biarkan aku pergi ke depan dan membuka up structs.h, dan Anda akan melihat ide ini di sini. Perhatikan bahwa saya telah menggunakan typedef, karena Anda menyinggung beberapa saat yang lalu untuk menyatakan kami sendiri tipe data. Tapi aku juga menggunakan kata kunci ini lain disebut struct yang memberikan saya baru struktur data. Dan ini struktur data saya mengklaim akan memiliki dua hal dalam itu - string disebut nama, dan string disebut rumah. Dan nama saya akan memberikan kepada ini struktur data akan untuk disebut mahasiswa. Saya bisa menyebutnya apa pun yang saya inginkan, tapi ini membuat semantik akal untuk saya dalam pikiran saya. Jadi sekarang, jika saya membuka versi yang lebih baik dari program saya mulai menulis ada, biarkan aku gulir ke atas. Dan ada baris lagi kode di sini, tapi biarkan aku fokus untuk saat pada satu. Saya telah menyatakan apa yang disebut siswa konstan dan sulit kode 3 untuk saat ini. Tapi sekarang, perhatikan bagaimana bersih kode saya mulai mendapatkan. Sejalan 22, saya menyatakan array siswa. Dan melihat bahwa siswa ternyata sekarang tipe data. Karena pada bagian atas file ini, perhatikan Saya telah menyertakan file header bahwa saya berhenti beberapa saat yang lalu. Dan bahwa file header cukup hanya memiliki definisi mahasiswa. Jadi sekarang, saya telah membuat data kustom saya sendiri jenis yang penulis C tahun lalu tidak memikirkan di muka. Tapi tidak ada masalah. Aku bisa membuat sendiri. Jadi ini adalah sebuah array disebut siswa, masing-masing anggota yang adalah struktur siswa. Dan saya ingin tiga dari mereka dalam array. Dan sekarang, apa sisanya program ini lakukan? Aku butuh sesuatu yang sedikit sewenang-wenang. Jadi dari online 24 dan seterusnya, Aku iterate 0-3. Saya kemudian meminta pengguna untuk nama siswa. Dan kemudian saya menggunakan getString seperti sebelumnya. Kemudian saya meminta rumah siswa, dan saya menggunakan getString seperti sebelumnya. Tetapi perhatikan - sedikit baru sepotong sintaks - Aku masih bisa indeks kepada siswa-i, tapi bagaimana saya mendapatkan data spesifik dalam bidang struct? Nah, apa yang tampaknya bagian baru dari sintaks? Ini hanya dot operator. Kami telah benar-benar melihat ini sebelumnya. Anda sudah melihatnya di pset lima jika Anda sudah menyelam di sudah dengan file bitmap. Tapi titik hanya berarti dalam hal ini struct atau beberapa bidang, berikan dot nama, atau memberi saya dot rumah. Itu berarti masuk ke dalam struct dan bidang-bidang tertentu. Apa sisa program ini lakukan? Ini tidak semua yang seksi. Perhatikan bahwa saya iterate 0-3 lagi, dan aku hanya membuat Inggris frase seperti begitu dan begitu juga sedemikian dan rumah tersebut, lewat di nama dot dari mahasiswa-i dan mereka rumah juga. Dan kemudian terakhir, sekarang kita akan mulai untuk mendapatkan anal tentang ini, sekarang kita akrab dengan apa malloc dan fungsi lainnya telah lakukan selama ini. Mengapa saya harus membebaskan kedua nama dan rumah, meskipun saya tidak menelepon malloc? GetString lakukan. Dan itu adalah rahasia kecil yang kotor untuk beberapa minggu, tapi GetString memiliki telah bocor memori seluruh menempatkan semua semester sejauh ini. Dan Valgrand akan akhirnya mengungkapkan hal ini kepada kami. Tapi itu bukan masalah besar, karena saya tahu bahwa saya hanya bisa membebaskan nama dan rumah, meskipun secara teknis, untuk menjadi super, super aman, saya harus melakukan beberapa pengecekan error di sini. Apa yang naluri Anda memberitahu Anda? Apa yang harus saya memeriksa sebelum saya membebaskan apa itu String, alias yang char *? Aku benar-benar harus memeriksa apakah siswa braket i dot nama tidak nol sama. Kemudian akan OK untuk terus maju dan bebas pointer itu, dan yang sama atau yang lain satu juga. Jika siswa braket i dot rumah tidak sama dengan nol, sekarang ini akan melindungi terhadap kasus sudut di mana GetString mengembalikan sesuatu seperti null. Dan kami melihat beberapa saat yang lalu, printf akan melindungi kita di sini dengan hanya mengatakan null, yang akan terlihat aneh. Tapi setidaknya itu tidak akan segfault, sebagaimana telah kita lihat. Nah, biarkan aku melakukan satu hal lain di sini. structs-0 adalah jenis program yang bodoh karena saya memasukkan semua data ini, dan kemudian itu hilang setelah program berakhir. Tapi biarkan aku pergi ke depan dan melakukan hal ini. Mari saya membuat terminal jendela sedikit lebih besar. Mari saya membuat structs-1, yang adalah versi baru ini. Aku akan memperbesar sedikit. Dan sekarang biarkan aku menjalankan dot slash structs-1. Nama siswa - David Mather, mari kita lakukan Rob Kirkland, mari kita lakukan Lauren Leverett. Yang menarik sekarang adalah pemberitahuan - dan aku hanya tahu ini karena Aku menulis program - ada file sekarang saat saya direktori bernama students.csv. Beberapa dari Anda mungkin telah melihat ini di dunia nyata. Apa file CSV? Comma-separated values. Ini semacam seperti orang miskin versi dari file Excel. Ini adalah tabel baris dan kolom yang Anda dapat membuka dalam program seperti Excel, atau Nomor pada Mac. Dan jika saya membuka file ini di sini di gedit, pemberitahuan - dan nomor tidak ada. Itu hanya gedit memberitahu saya nomor baris. Perhatikan pada baris pertama dari file David dan Mather. Baris berikutnya adalah Rob koma Kirkland. Dan baris ketiga adalah Lauren koma Leverett. Jadi apa yang telah saya buat? Sekarang saya telah menulis sebuah program C yang efektif dapat menghasilkan spreadsheet yang dapat dibuka di program seperti Excel. Tidak semua yang menarik satu set data, tetapi jika Anda memiliki potongan yang jauh lebih besar data yang Anda benar-benar ingin memanipulasi dan membuat grafik dan suka, ini mungkin salah satu cara untuk membuat data. Selain itu, CSVs sebenarnya super umum hanya untuk menyimpan data sederhana - Yahoo Finance, misalnya, jika Anda mendapatkan harga saham melalui disebut-mereka API, layanan gratis yang memungkinkan Anda mendapatkan arus saham up-to-the-date penawaran untuk perusahaan, mereka memberikan data kembali di Super format CSV sederhana. Jadi bagaimana kita melakukannya? Nah perhatikan, sebagian besar program ini hampir sama. Tapi perhatikan di sini, daripada cetak siswa keluar, on line 35 selanjutnya, saya menyatakan bahwa saya menyimpan siswa ke disk, sehingga menyimpan file. Jadi perhatikan aku mendeklarasikan FILE * - sekarang, ini adalah jenis anomali dalam C. Untuk alasan apapun, FILE adalah semua topi, yang tidak seperti kebanyakan tipe data lain dalam C. Tapi ini adalah built-in tipe data, FILE *. Dan aku menyatakan pointer ke file, adalah bagaimana Anda bisa memikirkan itu. fopen berarti file yang terbuka. File apa yang Anda ingin buka? Saya ingin membuka file yang saya akan sewenang-wenang memanggil students.csv. Aku bisa menelepon bahwa apapun yang saya inginkan. Dan kemudian mengambil menebak. Apa argumen kedua untuk fopen mungkin berarti? Benar, w untuk write, bisa menjadi r untuk read. Ada untuk append jika Anda ingin menambahkan baris dan tidak menimpa semuanya. Tapi aku hanya ingin membuat file ini sekali, jadi saya akan menggunakan kutipan tanda kutip w. Dan aku tahu bahwa hanya dari setelah membaca dokumentasi, atau halaman manual. Jika file tidak nol - dengan kata lain, jika ada yang tidak beres di sana - biarkan aku iterate atas siswa berumur 0 sampai 3. Dan sekarang melihat ada sesuatu pernah jadi sedikit berbeda tentang line 41 di sini. Ini tidak printf. Ini fprintf file printf. Jadi itu akan menulis ke file. Mana file? Satu yang pointer Anda tentukan sebagai argumen pertama. Kemudian kita tentukan format string. Kemudian kita menentukan apa string yang kita ingin plug in untuk pertama persen s, dan maka variabel lain atau persen kedua s. Kemudian kita menutup file dengan fclose. Daripada aku membebaskan memori seperti sebelumnya, meskipun Aku harus kembali dan menambahkan beberapa pemeriksaan untuk null. Dan itu saja. fopen, fprintf, fclose memberi saya kemampuan untuk membuat file teks. Sekarang, Anda akan melihat dalam masalah set lima, yang melibatkan gambar, Anda akan menggunakan file biner sebagai gantinya. Tapi pada dasarnya, idenya adalah sama, meskipun fungsi Anda akan lihat adalah sedikit berbeda. Jadi tur angin puyuh, tetapi Anda akan mendapatkan semua terlalu akrab dengan berkas I/O-- input dan output - dengan pset lima. Dan pertanyaan tentang dasar-dasar awal di sini? Ya? Bagaimana jika Anda mencoba untuk membebaskan nilai null? Saya percaya, kecuali gratis telah mendapat sedikit lebih user-friendly, Anda dapat berpotensi segfault. Lewat nol buruk karena saya tidak percaya bebas mengganggu untuk memeriksa Anda, karena berpotensi akan sia-sia waktu untuk itu untuk melakukan itu sendiri untuk semua orang di dunia. Pertanyaan bagus, meskipun. Baiklah, jadi ini semacam mendapat kita untuk topik yang menarik. Tema masalah set lima adalah forensik. Setidaknya itulah porsi dari sejumlah masalah. Forensik umumnya mengacu pada pemulihan informasi yang mungkin atau mungkin belum dihapus sengaja. Dan jadi saya pikir saya akan memberi Anda cepat rasa apa yang sebenarnya terjadi pada semua kali ini di bawah kap komputer Anda. Misalnya, jika Anda memiliki dalam Anda laptop atau komputer desktop Anda hard drive, itu baik mekanik perangkat yang benar-benar berputar - ada hal-hal melingkar yang disebut platter yang terlihat cukup seperti apa yang saya baru saja di layar di sini, meskipun ini sekolah semakin tua. Ini adalah tiga-dan-a-setengah inci hard drive. Dan tiga setengah inci mengacu dari dengan satu hal ketika Anda menginstalnya dalam komputer. Banyak dari kalian di laptop Anda sekarang memiliki solid-state drive, atau SSD, yang memiliki bagian yang bergerak. Mereka lebih seperti RAM dan kurang seperti perangkat ini mekanik. Tapi ide masih sama, tentu karena terkait masalah set lima. Dan jika Anda berpikir tentang sekarang hard drive merupakan menjadi sebuah lingkaran, yang Aku akan menggambar seperti ini di sini. Bila Anda membuat file di komputer Anda, apakah itu sebuah SSD, atau kasus ini, sebuah sekolah hard drive yang lebih tua, file itu terdiri dari beberapa bit. Mari kita mengatakan bahwa itu ini 0 dan 1, sejumlah besar 0s dan 1s. Jadi ini adalah seluruh hard drive saya. Hal ini tampaknya merupakan file yang cukup besar. Dan itu adalah menggunakan up 0s dan 1s pada saat itu bagian dari piring fisik. Nah, apa itu bagian fisik? Nah, ternyata pada hard drive, setidaknya jenis ini, ada kecil partikel-partikel magnetik kecil. Dan mereka pada dasarnya memiliki utara dan kutub selatan mereka, sehingga jika Anda mengubah salah satu partikel magnetik cara ini, Anda mungkin mengatakan bahwa itu mewakili 1. Dan jika itu terbalik selatan ke utara, Anda mungkin mengatakan bahwa itu mewakili 0. Jadi dalam dunia fisik yang nyata, itu bagaimana Anda bisa mewakili sesuatu dalam biner keadaan 0 dan 1. Jadi itu semua file adalah. Ada sejumlah besar magnetik partikel yang mereka dengan cara ini atau cara ini, menciptakan pola 0s dan 1s. Tapi ternyata ketika Anda menyimpan file, beberapa informasi disimpan secara terpisah. Jadi ini adalah meja kecil, direktori, sehingga untuk berbicara. Dan saya akan menyebutnya nama kolom, dan Aku akan menelepon kolom ini lokasi. Dan aku akan mengatakan, misalkan ini adalah resume saya. Resume.doc saya disimpan pada lokasi, katakanlah 123. Aku selalu pergi untuk nomor itu. Tapi cukup untuk mengatakan bahwa sama seperti dalam RAM, Anda dapat mengambil hard drive itu adalah gigabyte atau 200 gigabyte atau terabyte, dan Anda dapat jumlah semua byte. Anda dapat nomor semua potongan 8 bit. Jadi kita akan mengatakan bahwa ini adalah lokasi 123. Jadi direktori ini dalam operasi saya sistem ingat bahwa saya Resume adalah di lokasi 123. Tapi akan menarik ketika Anda menghapus file. Jadi misalnya - dan untungnya, sebagian besar dunia memiliki tertangkap ke ini - apa yang terjadi ketika Anda menyeret file ke Mac OS Sampah atau Anda Windows Recycle Bin? Apa tujuan melakukan hal itu? Ini jelas untuk menyingkirkan file, tapi apa tindakan menyeret dan menjatuhkan ke Sampah atau Anda Recycle Bin lakukan pada komputer? Benar-benar tidak, benar-benar. Ini seperti folder. Ini adalah folder khusus, untuk memastikan. Tapi apakah itu benar-benar menghapus file? Yah, tidak, karena beberapa dari Anda mungkin telah seperti, oh sialan, Anda tidak bermaksud melakukan itu. Jadi Anda klik dua kali Sampah atau Recycle Bin. Anda sudah menjulurkan sekitar dan Anda telah pulih file hanya dengan menyeretnya keluar dari sana. Jadi jelas, hal itu belum tentu menghapusnya. OK, Anda lebih cerdas dari itu. Anda tahu bahwa hanya menyeret ke dalam Sampah atau Recycle Bin tidak berarti Anda mengosongkan tempat sampah. Jadi Anda pergi ke menu, dan Anda katakan Sampah Kosong atau Empty Recycle Bin. Lalu apa yang terjadi? Ya, jadi dihapus lebih. Tapi semua yang terjadi adalah ini. Komputer lupa di mana resume.doc itu. Tapi apa yang tidak berubah rupanya dalam gambar? Bit, 0s dan 1s yang saya klaim yang di situs dari beberapa aspek fisik perangkat keras. Mereka masih ada. Ini hanya komputer memiliki lupa apa yang mereka. Jadi itu dasarnya membebaskan file bit sehingga mereka dapat digunakan kembali. Tapi tidak sampai Anda menciptakan lebih banyak file, dan lebih file, dan lebih banyak file akan probabilistically, mereka 0s dan 1s, partikel-partikel magnetik, digunakan kembali, terbalik atau kanan sisi atas, untuk file lainnya, 0s dan 1s. Jadi Anda memiliki jendela waktu ini. Dan itu bukan dari diprediksi panjang, benar-benar. Hal ini tergantung pada ukuran hard drive dan berapa banyak file yang Anda miliki dan seberapa cepat Anda membuat yang baru. Tapi ada jendela ini waktu selama mana file yang masih sempurna dipulihkan. Jadi, jika Anda pernah menggunakan program seperti McAfee atau Norton untuk mencoba untuk memulihkan data, semua yang mereka lakukan adalah mencoba untuk memulihkan ini disebut direktori mencari tahu di mana file Anda itu. Dan kadang-kadang Norton dan akan berkata, file 93% dapat dipulihkan. Nah, apa artinya? Itu hanya berarti bahwa beberapa file lain kebetulan akhirnya menggunakan, katakanlah, mereka bit dari file asli Anda. Jadi apa yang sebenarnya terlibat dalam memulihkan data? Nah, jika Anda tidak memiliki sesuatu seperti Norton pra-instal pada komputer Anda, yang terbaik Anda kadang-kadang bisa lakukan adalah melihat di seluruh hard drive mencari pola bit. Dan salah satu tema masalah set lima adalah bahwa Anda akan mencari setara dengan hard drive, forensik gambar kartu compact flash dari kamera digital, mencari 0s dan 1s yang biasanya, dengan tinggi probabilitas, mewakili mulai dari gambar JPEG. Dan kalian bisa memulihkan gambar dengan dengan asumsi, jika saya melihat pola bit pada gambar forensik, dengan probabilitas tinggi, yang menandai awal dari JPEG. Dan jika saya melihat pola yang sama lagi, yang mungkin menandai dimulainya lain JPEG, dan lain JPEG, JPEG dan lain. Dan ini biasanya bagaimana data recovery akan bekerja. Apa yang baik tentang JPEG adalah meskipun format file itu sendiri agak kompleks, setiap awal seperti File sebenarnya cukup diidentifikasi dan sederhana, karena Anda akan melihat, kalau udah belum. Jadi mari kita lihat lebih dekat di bawahnya kap untuk apa sudah terjadi, dan apa ini 0s dan 1s adalah, untuk memberikan sedikit lebih dari konteks untuk tantangan ini. [VIDEO PEMUTARAN] Dimana-PC menyimpan sebagian data tetapnya. Untuk melakukan itu, data perjalanan dari RAM bersama dengan sinyal perangkat lunak yang memberitahu hard drive bagaimana untuk menyimpan data. Rangkaian hard drive menerjemahkan sinyal tersebut menjadi tegangan fluktuasi. Ini, pada gilirannya, mengontrol hard drive bagian yang bergerak, beberapa beberapa bagian yang bergerak tersisa di komputer modern. Beberapa sinyal kontrol motor yang berputar piring-piring berlapis logam. Data Anda sebenarnya disimpan pada piring-piring ini. Sinyal lain memindahkan membaca / menulis kepala untuk membaca atau menulis data pada piring-piring. Mesin ini sangat tepat bahwa manusia rambut bahkan tidak bisa melewati antara kepala dan berputar piring. Namun, semuanya bekerja pada kecepatan yang hebat. [END VIDEO PEMUTARAN] DAVID Malan: Zoom in sedikit lebih sekarang di apa benar-benar pada piring-piring. [VIDEO PEMUTARAN] -Mari kita lihat apa yang kita hanya melihat dalam gerakan lambat. Ketika pulsa singkat listrik dikirim ke membaca / menulis kepala, jika membalik pada elektromagnetik kecil untuk sepersekian detik. Magnet menciptakan medan, yang perubahan polaritas kecil, kecil bagian dari partikel logam yang melapisi setiap permukaan platter. Serangkaian pola kecil ini, dibebankan-up area pada disk mewakili satu bit data dalam bilangan biner sistem yang digunakan oleh komputer. Sekarang, jika saat ini dikirim satu arah melalui membaca / menulis kepala, daerah terpolarisasi dalam satu arah. Jika saat ini dikirim dalam arah sebaliknya, polarisasi terbalik. Bagaimana Anda mendapatkan data dari hard disk? Hanya membalik proses tersebut. Jadi partikel pada disk yang mendapatkan arus di membaca / menulis kepala bergerak. Mengumpulkan jutaan ini segmen magnet, dan Anda punya file. Sekarang, potongan-potongan dari file tunggal mungkin tersebar di seluruh drive yang piring-piring, jenis seperti kekacauan kertas di meja Anda. Jadi file tambahan khusus melacak di mana semuanya. Jangan Anda berharap Anda memiliki sesuatu seperti itu? [END VIDEO PEMUTARAN] DAVID Malan: OK, mungkin tidak. Jadi berapa banyak dari kalian dibesarkan dengan ini? OK, jadi semakin sedikit tangan setiap tahun. Tapi aku senang kau setidaknya akrab dengan mereka, karena ini dan kita sendiri Buku demo, sayangnya, sekarat sangat memperlambat kematian sini keakraban. Tapi ini adalah apa yang saya, setidaknya, kembali SMA, penggunaan digunakan untuk backup. Dan itu sangat mengagumkan, karena Anda bisa menyimpan 1,4 megabyte pada khusus ini disk yang. Dan ini adalah versi kepadatan tinggi, seperti yang ditunjukkan oleh HD, yang memiliki artinya sebelum video HD saat ini. Kepadatan standar adalah 800 kilobyte. Dan sebelum itu, ada Disk 400-kilobyte. Dan sebelum itu, ada 5 dan 1/4 inch disk, yang benar-benar floppy, dan sedikit lebih lebar dan lebih tinggi dari hal-hal di sini. Tapi Anda benar-benar dapat melihat apa yang disebut Aspek floppy disk ini. Dan fungsional, mereka benar-benar sangat mirip dengan hard drive di Setidaknya jenis ini. Sekali lagi, SSD dalam komputer baru bekerja sedikit berbeda. Tetapi jika Anda memindahkan bahwa tab logam kecil, Anda benar-benar dapat melihat kue kecil, atau piring. Ini bukan logam seperti ini. Yang satu ini benar-benar beberapa murah bahan plastik. Dan Anda dapat jenis menggoyangkan itu. Dan kau trully hanya dihapus beberapa jumlah bit atau partikel magnetik dari disk ini. Jadi untungnya, tidak ada di atasnya. Jika hal itu dalam cara - dan mencakup mata Anda dan orang-orang dari tetangga Anda - Anda dapat hanya semacam tarik ini selubung seluruh off seperti itu. Tapi ada sedikit air, jadi menyadari bahwa dengan mata Anda. Jadi sekarang Anda telah benar-benar floppy disk. Dan apa yang luar biasa tentang hal ini adalah bahwa dalam sebanyak ini adalah representasi skala kecil dari yang lebih besar hard drive, hal-hal yang super, super sederhana. Jika Anda mencubit bagian bawah itu, sekarang hal logam batal, dan kupas mereka terbuka, semua yang ada adalah dua potong dirasakan dan yang disebut disket dengan sepotong logam di dalam. Dan ada pergi setengah dari isi disk saya itu. Ada pergi setengah lagi dari mereka. Tapi itu semua yang berputar di dalam dari komputer Anda dalam tadi. Dan sekali lagi, untuk menempatkan ini dalam perspektif, seberapa besar adalah sebagian besar dari Anda hard drive hari ini? 500 gigabyte, terabyte, mungkin dalam sebuah komputer desktop, 2 terabyte, 3 terabyte, 4 terabyte, kan? Ini adalah salah satu megabyte, memberi atau mengambil, yang bahkan tidak bisa cocok dengan MP3 khas lagi hari ini, atau beberapa File musik yang serupa. Jadi suvenir kecil untuk Anda hari ini, dan juga untuk membantu mengontekstualisasikan apa kita akan mengambil untuk diberikan sekarang dalam masalah set lima. Jadi mereka adalah milik Anda. Jadi biar transisi ke mana akan menghabiskan pset berikutnya juga. Jadi sekarang kita telah menetapkan halaman ini untuk - oh, beberapa pengumuman cepat. Jumat ini, jika Anda ingin bergabung CS50 untuk makan siang, pergi ke tempat biasa, cs50.net/rsvp. Dan tugas akhir - sehingga per silabus, kami telah diposting spesifikasi tugas akhir sudah. Sadarilah bahwa itu tidak berarti itu karena sangat segera. Ini diposting, benar-benar, hanya untuk mendapatkan kalian berpikir tentang hal itu. Dan memang, yang signifikan Super persentase Anda akan menangani proyek akhir tentang materi yang kita bahkan belum mendapatkan dalam kelas, tapi akan sebagai awal minggu depan. Perhatikan, meskipun, bahwa spec panggilan untuk beberapa komponen yang berbeda dari tugas akhir. Yang pertama, dalam beberapa minggu, adalah pra-proposal, email cukup santai untuk TF Anda untuk memberitahu dia atau apa yang Anda memikirkan untuk proyek Anda, dengan ada komitmen. Proposal akan khusus Anda komitmen, mengatakan, di sini, ini adalah apa yang Saya ingin lakukan untuk proyek saya. Bagaimana menurut Anda? Terlalu besar? Terlalu kecil? Apakah itu dikelola? Dan Anda lihat spec untuk lebih jelasnya. Beberapa minggu setelah itu adalah status Laporan, yang merupakan sama email kasual untuk TF Anda untuk mengatakan betapa jauh di belakang Anda berada di akhir Anda pelaksanaan proyek, diikuti oleh yang CS50 Hackathon yang semua orang adalah diundang, yang akan menjadi acara dari 20:00 pada satu malam sampai 7:00 Pagi berikutnya. Pizza, seperti yang saya mungkin telah disebutkan dalam seminggu nol, wil disajikan di 9:00, Makanan Cina at 1:00 AM. Dan jika Anda masih terjaga di 05:00, kami akan mengarahkan Anda ke IHOP untuk sarapan. Jadi Hackathon adalah salah satu yang lebih pengalaman mengesankan di kelas. Kemudian pelaksanaannya jatuh tempo, dan maka klimaks CS50 Fair. Rincian lebih lanjut tentang semua ini dalam minggu-minggu yang akan datang. Tapi mari kita kembali ke sesuatu sekolah tua - lagi, array. Jadi array itu bagus, karena memecahkan masalah seperti yang kita lihat hanya saat yang lalu dengan struktur siswa mendapatkan sedikit keluar dari kontrol jika kita ingin memiliki siswa satu, dua mahasiswa, mahasiswa tiga, mahasiswa dot dot dot, beberapa nomor sewenang-wenang siswa. Jadi array, beberapa minggu yang lalu, menukik dan memecahkan semua masalah kami tidak mengetahui lebih dulu berapa banyak hal dari beberapa jenis mungkin kita inginkan. Dan kami telah melihat bahwa structs dapat membantu kita lebih mengatur kode kita dan menjaga variabel konseptual mirip, seperti nama dan rumah, bersama-sama, sehingga kita dapat memperlakukan mereka sebagai satu kesatuan, di dalam yang ada potongan-potongan kecil. Tapi array memiliki beberapa kelemahan. Apa adalah beberapa kelemahan kami temui dengan array sejauh ini? Apa itu? Ukuran tetap - jadi meskipun Anda mungkin dapat mengalokasikan memori untuk array, setelah Anda tahu berapa banyak siswa Anda miliki, berapa banyak karakter yang Anda miliki dari pengguna, setelah Anda dialokasikan array, Anda jenis dicat diri ke sudut. Karena Anda tidak bisa memasukkan unsur-unsur baru ke tengah-tengah array. Anda tidak dapat memasukkan lebih elemen pada akhir array. Sungguh, Anda harus resor untuk menciptakan array baru keseluruhan, seperti yang telah kita bahas, menyalin lama ke yang baru. Dan lagi, yaitu sakit kepala yang GetString berurusan dengan untuk Anda. Tapi sekali lagi, Anda bahkan tidak bisa memasukkan sesuatu ke tengah array jika angka ini tidak sepenuhnya diisi. Misalnya, jika array ini di sini ukuran enam hanya memiliki lima hal di dalamnya, baik, Anda bisa saja taktik sesuatu ke akhir. Tetapi bagaimana jika Anda ingin memasukkan sesuatu ke tengah array, meskipun mungkin memiliki lima dari enam hal di dalamnya? Nah, apa yang kita lakukan ketika kita memiliki semua sukarelawan manusia panggung di minggu terakhir? Jika kita ingin menempatkan seseorang di sini, baik orang-orang bagaimana untuk memindahkan cara, atau orang-orang bagaimana untuk memindahkan cara, dan yang menjadi mahal. Pergeseran orang di dalam suatu Array akhirnya menambahkan dan biaya kami waktu, maka banyak n kuadrat kami berjalan saat seperti insertion sort, untuk Misalnya, dalam kasus terburuk. Jadi array yang besar, tetapi Anda harus mengetahui terlebih dahulu seberapa besar Anda ingin mereka. Jadi OK, inilah solusi. Jika saya tidak tahu sebelumnya berapa banyak siswa saya mungkin memiliki, dan aku tahu sekali Saya memutuskan, meskipun, aku terjebak dengan itu banyak siswa, kenapa tidak aku hanya selalu mengalokasikan dua kali lebih banyak ruang karena saya mungkin berpikir saya butuhkan? Apakah itu bukan solusi yang masuk akal? Realistis, saya tidak berpikir bahwa kita akan membutuhkan lebih dari 50 slot dalam sebuah array untuk kelas menengah, jadi mari kita mengumpulkan. Aku akan membuat 100 slot di array saya, hanya sehingga kita pasti bisa mendapatkan jumlah siswa saya berharap untuk dalam beberapa kelas menengah. Jadi, mengapa tidak mengumpulkan dan mengalokasikan lebih banyak memori, biasanya, untuk array dari yang Anda pikir Anda mungkin bahkan perlu? Apa ini pushback sederhana ide itu? Kau hanya membuang-buang memori. Secara harfiah setiap program yang Anda tulis kemudian ini mungkin menggunakan dua kali lebih banyak memori Anda benar-benar perlu. Dan itu hanya tidak merasa seperti khususnya solusi elegan. Selain itu, itu hanya menurunkan kemungkinan masalah. Jika Anda kebetulan memiliki program populer satu semester dan Anda memiliki 101 siswa, program Anda masih fundamental menghadapi masalah yang sama. Jadi untungnya, ada solusi untuk Iklan ini semua masalah kita dalam bentuk struktur data yang lebih kompleks daripada yang kita lihat sejauh ini. Ini, saya menyatakan, adalah linked list. Ini adalah daftar nomor - 9, 17, 22, 26, dan 34 - yang telah terhubung bersama-sama dengan cara dari apa yang saya sudah ditarik sebagai panah. Dengan kata lain, jika saya ingin untuk mewakili array, aku bisa melakukan sesuatu seperti ini. Dan aku akan menempatkan ini di biaya overhead hanya dalam beberapa saat. Aku bisa melakukan - halo, baiklah. Stand by. Komputer baru di sini, jelas - baik-baik saja. Jadi jika saya memiliki angka-angka ini dalam array - 9, 17, 22, 26, 24 - belum tentu untuk skala. Baiklah, jadi di sini adalah array saya - oh my god. Baiklah, jadi di sini adalah array saya. Oh my god. [Tertawa] DAVID Malan: Berpura-pura. Ini terlalu banyak usaha untuk kembali dan memperbaikinya, sehingga ada - 26. Jadi kita memiliki ini array 9, 17, 22, 26, dan 34. Bagi Anda bisa melihat kesalahan yang memalukan Aku hanya membuat, ada itu. Jadi saya mengklaim bahwa ini adalah solusi yang sangat efisien. Aku sudah dialokasikan sebanyak ints sebagai Saya perlu - satu, dua, tiga, empat, lima, atau enam - dan aku kemudian disimpan nomor dalam array ini. Tapi bagaimana, kemudian, saya ingin memasukkan nilai seperti angka 8? Nah, mana pergi? Misalkan saya ingin menyisipkan nomor seperti 20. Nah, mana pergi? Di suatu tempat ada di tengah, atau nomor 35 harus pergi di suatu tempat di akhir. Tapi aku semua keluar dari ruang. Dan jadi ini adalah tantangan mendasar array yang tidak adalah solusinya. Saya mengklaim beberapa saat yang lalu, getString memecahkan masalah ini. Jika Anda ingin memasukkan nomor keenam ke dalam array ini, apa setidaknya satu solusi yang Anda dapat jatuh kembali untuk yakin, seperti yang kita lakukan dengan GetString? Apa itu? Nah, membuatnya lebih besar adalah mudah diucapkan daripada dilakukan. Kita tidak bisa selalu membuat array lebih besar, tapi apa yang bisa kita lakukan? Membuat array baru yang lebih besar, ukuran 6, atau mungkin ukuran 10, jika kita ingin untuk maju hal, dan kemudian salin array yang lama ke yang baru, dan kemudian membebaskan array yang lama. Tapi apa waktu berjalan sekarang proses itu? Ini O besar n, karena penyalinan akan dikenakan biaya beberapa unit waktu, jadi tidak begitu ideal jika kita harus mengalokasikan sebuah array baru, yang akan mengkonsumsi dua kali lebih banyak memori sementara. Kopi lama ke yang baru - Maksudku, itu hanya sakit kepala, yang adalah, sekali lagi, mengapa kita menulis GetString untuk Anda. Jadi apa yang bisa kita lakukan? Nah, bagaimana jika struktur data kami sebenarnya memiliki kesenjangan di dalamnya? Misalkan saya rileks tujuan saya memiliki potongan memori yang berdekatan di mana 9 tepat di sebelah 17, yang tepat di sebelah 22, dan seterusnya. Dan anggaplah bahwa 9 bisa di sini di RAM, dan 17 dapat over sini dalam RAM, dan 22 dapat over sini dalam RAM. Dengan kata lain, saya tidak membutuhkan mereka bahkan kembali ke belakang lagi. Aku hanya harus entah bagaimana benang jarum melalui masing-masing nomor, atau masing-masing node ini, karena kami akan memanggil persegi panjang seperti yang telah saya ditarik mereka, ingat bagaimana untuk sampai ke terakhir simpul tersebut dari yang pertama. Jadi apa pemrograman membangun kami telah melihat cukup baru-baru ini yang saya dapat menerapkan thread itu, atau ditarik di sini, yang saya bisa mengimplementasikan panah? Pointer Jadi, kan? Jika saya mengalokasikan bukan hanya int, tapi simpul - dan dengan node, saya hanya berarti wadah. Dan visual, maksudku persegi panjang. Jadi node tampaknya perlu mengandung dua nilai - int sendiri, dan kemudian, seperti yang tersirat oleh bagian bawah persegi panjang, cukup ruang untuk int. Jadi hanya berpikir ke depan di sini, seberapa besar node ini, ini kontainer tersebut? Berapa banyak byte untuk int? Agaknya 4, jika sama seperti biasa. Dan kemudian berapa banyak byte untuk pointer? 4. Jadi wadah ini, atau node ini, adalah akan menjadi struktur 8-byte. Oh, dan itu suatu kebetulan senang bahwa kami hanya memperkenalkan gagasan ini struct, atau struktur C. Jadi saya menyatakan bahwa saya ingin mengambil langkah arah ini lebih canggih pelaksanaan daftar nomor, a linked list nomor, saya perlu melakukan sedikit lebih berpikir ke depan dan menyatakan bukan hanya sebuah int tetapi struct bahwa saya akan menelepon, konvensional sini, simpul. Kita bisa menyebutnya apa pun yang kita inginkan, tetapi node akan tematik dalam banyak satu hal yang kita mulai melihat sekarang. Di dalam simpul yang merupakan n int. Dan kemudian sintaks ini, sedikit aneh pada pandangan pertama - struct simpul * berikutnya. Nah pictorially, apa itu? Itulah bagian bawah persegi panjang yang kami lihat beberapa saat yang lalu. Tapi mengapa saya katakan struct simpul * sebagai lawan hanya simpul *? Karena jika pointer yang menunjuk di node lain, itu hanya alamat node. Itu konsisten dengan apa yang kita sudah dibahas tentang pointer sejauh ini. Tapi mengapa, jika saya mengklaim struktur ini disebut node, saya harus mengatakan struct simpul dalam sini? Tepat. Ini semacam realitas bodoh C. Typedef, sehingga untuk berbicara, belum belum terjadi. C adalah SUPER literal. Bunyinya atas kode Anda bawah, kiri ke kanan. Dan sampai hits koma yang pada Intinya, tebak apa yang tidak ada sebagai tipe data? Node, kutipan tanda kutip simpul. Tetapi karena lebih verbose deklarasi saya lakukan pada baris pertama - typedef struct simpul - karena yang datang terlebih dahulu, sebelum kurung kurawal, itu semacam pra-mendidik dentang itu, Anda tahu apa, beri saya struct disebut struct simpul. Terus terang, saya tidak suka hal-hal yang menelepon struct node, struct simpul semua seluruh kode saya. Tapi saya hanya akan menggunakannya sekali, hanya di dalam, sehingga saya dapat secara efektif membuat semacam referensi melingkar, tidak pointer untuk diriku sendiri per se, tetapi pointer ke lain jenis identik. Jadi ternyata bahwa pada struktur data seperti ini, ada beberapa operasi yang mungkin menarik bagi kami. Kita mungkin ingin memasukkan ke dalam daftar seperti ini. Kita mungkin ingin menghapus dari daftar seperti ini. Kita mungkin ingin mencari daftar untuk nilai, atau lebih umum, melintasi. Dan melintasi adalah cara mewah mengatakan mulai kiri dan memindahkan semua jalan ke kanan. Dan perhatikan, bahkan dengan sedikit lebih struktur data yang canggih, biarkan saya mengusulkan agar kita bisa meminjam beberapa ide-ide dari dua minggu terakhir dan melaksanakan fungsi yang disebut pencarian seperti ini. Ini akan kembali benar atau palsu, menunjukkan, ya atau tidak, n dalam daftar. Argumen kedua adalah pointer ke daftar itu sendiri, sehingga pointer ke node. Semua aku akan kemudian lakukan adalah menyatakan variabel sementara. Kita akan menyebutnya ptr oleh konvensi, untuk pointer. Dan saya menetapkan sama dengan awal daftar. Dan sekarang melihat loop sementara. Selama pointer tidak sama null, aku akan memeriksa. Apakah pointer panah n sama dengan n yang disahkan pada? Dan tunggu dulu - baru sepotong sintaks. Apa panah tiba-tiba? Ya? Tepat. Jadi sedangkan beberapa menit yang lalu, kami menggunakan dot notasi untuk mengakses sesuatu dalam sebuah struct, jika variabel Anda tidak struct sendiri, tetapi pointer ke struct, Untungnya, sepotong sintaks yang akhirnya masuk akal intuitif. Panah berarti mengikuti pointer, seperti panah kami biasanya berarti pictorially, dan pergi data di dalam lapangan. Jadi panah adalah hal yang sama seperti titik, tapi Anda menggunakannya ketika Anda memiliki pointer. Jadi hanya untuk rekap kemudian, jika bidang n dalam struct disebut pointer sama sama n, kembali benar. Jika tidak, baris ini di sini - pointer sama dengan pointer berikutnya. Jadi apa ini yang dilakukan, pemberitahuan, jika saya saya sedang menunjuk pada struct mengandung 9, dan 9 tidak nomor Saya mencari - kira saya sedang mencari untuk n sama dengan 50 - Aku akan memperbarui pointer sementara saya untuk tidak menunjuk pada simpul ini lagi, tapi pointer panah di sebelah, yang akan menempatkan saya di sini. Sekarang, saya menyadari adalah angin puyuh pengantar. Pada hari Rabu, kita benar-benar akan melakukan ini dengan beberapa manusia dan dengan beberapa lebih kode lebih lambat. Tetapi menyadari, kita sekarang membuat data kami struktur yang lebih kompleks sehingga kami algoritma bisa lebih efisien, yang akan menjadi prasyarat bagi pset enam, ketika kita memuat dalam, sekali lagi, mereka 150.000 kata, tapi harus melakukannya efisien, dan idealnya, membuat Program yang berjalan selama pengguna kami tidak linear, tidak n kuadrat, tetapi dalam waktu yang konstan, dalam ideal. Kita akan melihat Anda pada hari Rabu. SPEAKER: Pada CS50 berikutnya, David lupa kasus basisnya. DAVID Malan: Dan itulah bagaimana Anda mengirim pesan teks dengan C. Apa yang - [BERBAGAI PESAN TEKS PEMBERITAHUAN SOUNDS]