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