>> 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]