[Powered by Google Translate] [Minggu 4]
[David J. Malan] [Harvard University]
[Ini adalah CS50.] [CS50.TV]
>> Baiklah, ini adalah CS50, dan ini adalah awal minggu 4,
dan ini adalah salah satu algoritma penyortiran paling lambat mungkin.
Yang satu adalah bahwa kita hanya menyaksikan sana?
Itu semacam gelembung, dalam rangka big O (n ^ 2) + sum,
dan memang kita tidak satu-satunya di dunia ini untuk tampaknya tahu
macam apa gelembung atau waktu yang berjalan.
Memang, ini adalah sebuah wawancara dengan Eric Schmidt dari Google
dan mantan senator Barack Obama hanya beberapa tahun yang lalu.
>> Sekarang, Senator, kau di sini di Google,
dan saya suka berpikir kepresidenan sebagai wawancara kerja.
Sekarang, sulit untuk mendapatkan pekerjaan sebagai presiden, dan Anda akan melalui kerasnya sekarang.
Ini juga sulit untuk mendapatkan pekerjaan di Google.
Kami memiliki pertanyaan, dan kami meminta kandidat kami pertanyaan,
dan yang satu ini adalah dari Larry Schwimmer.
Kalian pikir aku bercanda? Ada di sini.
Apa cara yang paling efisien untuk menyortir satu juta 32-bit bilangan bulat?
[Tertawa]
Nah-
Maafkan aku >> Tidak, tidak, tidak, tidak..
Saya pikir bubble sort akan menjadi cara yang salah untuk pergi.
>> Ayo, yang mengatakan kepadanya ini?
Pekan lalu mengingat kami mengambil istirahat dari kode, setidaknya untuk satu hari,
dan mulai fokus pada beberapa ide tingkat yang lebih tinggi dan pemecahan masalah yang lebih umum
dalam konteks pencarian dan menyortir,
dan kami memperkenalkan sesuatu yang kita tidak menampar nama ini pada pekan lalu,
tapi asimtotik notasi, Big O, Omega Big,
dan kadang-kadang notasi Big Theta, dan ini hanyalah cara
menggambarkan waktu berjalan dari algoritma,
berapa banyak waktu yang diperlukan untuk algoritma untuk menjalankan.
>> Dan Anda mungkin ingat bahwa Anda berbicara tentang waktu berjalan dalam hal ukuran
dari input, yang biasanya kita sebut n, apapun masalahnya mungkin,
di mana n adalah jumlah orang di dalam ruangan,
jumlah halaman dalam buku telepon, dan kami mulai menulis hal-hal
seperti O (n ^ 2) atau O (n) atau O (n log n),
dan bahkan ketika matematika tidak cukup berhasil dengan sempurna
dan itu adalah n ² - n / 2 atau sesuatu seperti itu
kita malah akan hanya membuang beberapa istilah orde yang lebih rendah,
dan motivasi ada adalah bahwa kita benar-benar ingin
macam cara obyektif mengevaluasi
kinerja program atau kinerja algoritma
bahwa pada akhir hari tidak ada hubungannya, misalnya,
dengan kecepatan komputer Anda hari ini.
>> Misalnya, jika Anda menerapkan bubble sort,
atau Anda menerapkan menggabungkan semacam jenis atau seleksi pada komputer saat ini,
2 GHz komputer, dan Anda menjalankannya,
dan dibutuhkan beberapa jumlah detik, tahun depan ada 3 GHz
atau komputer 4 GHz, dan Anda mungkin kemudian mengklaim bahwa "Wow, algoritma saya
kini dua kali lebih cepat, "padahal itu jelas tidak terjadi.
Ini hanya perangkat keras telah mendapat lebih cepat, tetapi komputer Anda
belum, dan jadi kita benar-benar ingin membuang hal-hal seperti
kelipatan 2 atau kelipatan 3 ketika datang untuk menggambarkan
seberapa cepat atau seberapa lambat algoritma adalah dan benar-benar hanya fokus
pada n atau beberapa faktor daripadanya,
listrik beberapa daripadanya seperti dalam kasus macam dari minggu lalu.
Dan ingat bahwa dengan bantuan semacam merge
kami mampu melakukannya jauh lebih baik daripada bubble sort dan selection sort
dan bahkan penyisipan semacam.
>> Kami turun ke n log n, dan sekali lagi,
ingat bahwa log n umumnya mengacu pada sesuatu yang tumbuh
lebih lambat maka n, maka n log n sejauh itu baik
karena itu kurang dari ² n.
Tetapi untuk mencapai n log n dengan gabungan semacam
apa kuman dasar ide bahwa kita harus memanfaatkan
bahwa kita juga memanfaatkan kembali dalam seminggu 0?
Bagaimana kita mengatasi masalah menyortir cerdik dengan gabungan semacam?
Apa wawasan kunci, mungkin?
Siapapun sama sekali.
Oke, mari kita mengambil langkah mundur.
Jelaskan menggabungkan semacam kata-kata Anda sendiri.
Bagaimana cara kerjanya?
Oke, kita akan mendayung kembali ke 0 minggu.
Oke, yeah.
[Tak terdengar-murid]
Oke, baik, jadi kami membagi array angka menjadi 2 bagian.
Kami diurutkan masing-masing potongan, dan kemudian kami bergabung mereka,
dan kami telah melihat ide ini sebelum mengambil suatu masalah yang besar ini
dan memotong itu menjadi masalah yang ini besar atau sebesar ini.
>> Ingat contoh buku telepon.
Ingat algoritma self-menghitung dari minggu lalu,
semacam itu sehingga menggabungkan diringkas oleh pseudocode sini.
Bila Anda diberi n elemen, pertama itu kewarasan cek.
Jika n <2 maka jangan melakukan apa-apa
karena jika n <2 maka n jelas 0 atau 1,
dan jadi jika itu baik 0 atau 1 tidak ada yang perlu menyortir.
Anda sudah selesai.
Daftar Anda sudah sepele diurutkan.
Tapi sebaliknya jika Anda punya 2 atau lebih elemen pergi ke depan dan membagi mereka
menjadi 2 bagian, kiri dan kanan.
Urutkan masing-masing bagian, dan kemudian menggabungkan bagian diurutkan.
Namun masalah di sini adalah bahwa pada pandangan pertama ini terasa seperti kita punting.
Ini adalah definisi melingkar dalam bahwa jika saya meminta Anda untuk mengurut elemen n
dan kau bilang "Oke, baiklah, kita akan mengurutkan unsur-unsur n / 2 dan mereka n / 2,"
maka pertanyaan berikutnya akan menjadi "Baik, bagaimana Anda menyortir n / 2 elemen?"
>> Tetapi karena struktur program ini,
karena ada kasus ini dasar, sehingga untuk berbicara,
ini kasus khusus yang mengatakan jika n <beberapa nilai tetap seperti 2 kembali segera.
Jangan menanggapi dengan jawaban melingkar yang sama.
Proses ini, cyclicity ini akhirnya akan berakhir.
Jika saya meminta Anda "Urutkan unsur-unsur n," dan Anda berkata, "Baik, menyortir n / 2,"
maka Anda berkata, "Baik, semacam ini n / 4, n / 8, n/16,"
akhirnya Anda akan membagi dengan jumlah yang cukup besar
bahwa Anda akan memiliki hanya 1 kiri elemen, di titik mana Anda dapat mengatakan,
"Di sini, di sini adalah elemen tunggal diurutkan."
Kemudian kecemerlangan algoritma ini di sini adalah untuk berasal dari kenyataan
bahwa setelah Anda memiliki semua daftar individual diurutkan,
yang semuanya ukuran 1, yang tampaknya akan sia-sia,
setelah Anda mulai menggabungkan mereka dan menggabungkan mereka
Anda membangun akhirnya sebagai Rob lakukan dalam video daftar akhirnya diurutkan.
>> Tapi ide ini jauh melebihi penyortiran.
Ada ide ini tertanam dalam program ini dikenal sebagai rekursi,
gagasan dimana Anda program,
dan untuk memecahkan beberapa masalah Anda menyebut diri Anda,
atau dimasukkan ke dalam konteks bahasa pemrograman Anda fungsi,
dan dalam rangka memecahkan masalah, Anda fungsi menyebut diri
lagi dan lagi dan lagi, tetapi Anda fungsi
tidak bisa menyebut diri kali tak terhingga banyaknya.
Akhirnya Anda harus keluar bawah, sehingga untuk berbicara,
dan memiliki beberapa kondisi keras-kode dasar yang mengatakan
pada titik ini berhenti menyebut diri Anda sehingga seluruh proses
akhirnya tidak pada kenyataannya berhenti.
Apa ini benar-benar berarti, untuk recurse?
>> Mari kita lihat, jika kita bisa melakukan contoh sederhana, sepele dengan, katakanlah,
3 orang dengan saya di sini di atas panggung, jika seseorang nyaman.
1, ayolah up, 2 dan 3.
Jika Anda ingin 3 datang ke sini.
Jika Anda ingin berdiri tepat di samping saya di sini dalam satu garis, misalkan bahwa masalah yang dihadapi
sangat sepele menghitung jumlah orang yang ada di sini.
Tapi terus terang, aku lelah dari semua contoh menghitung.
Ini akan memakan waktu, 1, 2, dan titik, titik, titik.
Ini akan mengambil selamanya.
Saya lebih suka hanya tendangan masalah ini sama sekali dengan bantuan-siapa namamu?
Sara. >> Sara, baik-baik saja.
Kelly. >> Kelly dan?
>> Willy. >> Willy, Sara, Kelly, dan Willy.
Sekarang saya telah diminta pertanyaan oleh seseorang
berapa banyak orang yang sampai pada tahap ini, dan saya tidak tahu.
Ini adalah daftar sangat panjang, dan jadi bukannya aku akan melakukan trik ini.
Aku akan meminta orang di sebelah saya untuk melakukan sebagian besar pekerjaan,
dan sekali dia selesai melakukan sebagian besar pekerjaan
Aku akan melakukan sedikitnya jumlah pekerjaan mungkin dan hanya menambahkan 1
apa pun jawabannya adalah, jadi di sini kita pergi.
Saya telah bertanya berapa banyak orang berada di atas panggung.
Berapa banyak orang di atas panggung di sebelah kiri Anda?
Sebelah kiri saya >> Oke?, Tapi jangan menipu.
Itu bagus, itu benar, tetapi jika kita ingin melanjutkan logika ini
mari kita asumsikan bahwa Anda sama ingin menyepak bola masalah ini di sebelah kiri Anda,
jadi daripada jawaban langsung pergi ke depan dan hanya lulus uang.
Oh, berapa banyak orang yang di sebelah kiri saya?
Berapa banyak orang yang ke kiri?
1.
[Tertawa]
Oke, jadi 0, jadi apa sekarang Willy telah dilakukan
adalah Anda telah kembali jawaban Anda ini arah mengatakan 0.
Sekarang, apa yang harus Anda lakukan? >> 1.
Oke, jadi kau 1, sehingga Anda mengatakan, "Baiklah, aku akan menambahkan 1
untuk apa pun jumlah Willy adalah, "sehingga 1 + 0.
Anda sekarang 1 sehingga jawaban Anda ke kanan sekarang-
1. >> Dan saya akan menjadi 2.
Baik, jadi Anda mengambil jawaban sebelumnya 1,
menambahkan jumlah minimal pekerjaan yang ingin Anda lakukan, yaitu +1.
Anda sekarang memiliki 2, dan Anda kemudian tangan saya yang nilai?
3, maksudku, maaf, 2.
Baik.
>> Nah, kami memiliki 0 ke kiri.
Kemudian kami memiliki 1, dan kemudian kita tambahkan 2,
dan sekarang kau menyodorkan nomor 2,
dan jadi aku katakan, oke, +1, 3.
Ada memang 3 orang berdiri di samping saya di tahap ini,
sehingga kita bisa melakukan ini jelas sangat linear,
sangat banyak dengan cara yang jelas, tapi apa yang kita benar-benar lakukan?
Kami mengambil masalah ukuran 3 awalnya.
Kami kemudian pecah itu ke dalam masalah ukuran 2,
maka masalah ukuran 1, dan akhirnya kasus dasar
benar-benar, oh, tidak ada seorang pun di sana,
di mana titik Willy kembali efektif jawaban keras-kode beberapa kali,
dan yang kedua kemudian menggelegak, menggelegak, menggelegak,
dan kemudian dengan menambahkan dalam 1 satu tambahan
kami telah menerapkan ide dasar dari rekursi.
>> Sekarang, dalam hal ini tidak benar-benar memecahkan masalah
lagi efektif maka kita telah melihat sejauh ini.
Tapi pikirkan tentang algoritma yang kami lakukan di atas panggung sejauh ini.
Kami memiliki 8 potongan kertas di papan tulis,
video saat Sean sedang mencari nomor 7, dan apa yang dia benar-benar?
Yah, dia tidak melakukan apapun membagi dan menaklukkan.
Dia tidak melakukan apapun rekursi.
Sebaliknya dia hanya melakukan ini algoritma linier.
Tetapi ketika kita memperkenalkan ide nomor diurutkan di atas panggung hidup minggu lalu
maka kita punya naluri untuk pergi ke tengah,
di mana titik kami memiliki daftar yang lebih kecil dari ukuran 4 atau daftar lain ukuran 4,
dan kemudian kami memiliki masalah yang sama, jadi kami mengulangi, diulang, diulang.
Dengan kata lain, kita recursed.
Terima kasih banyak untuk 3 relawan kami di sini untuk menunjukkan rekursi dengan kami.
>> Mari kita lihat apakah kita tidak bisa membuat ini sekarang beton sedikit lebih,
memecahkan masalah yang lagi kita bisa lakukan cukup mudah,
tapi kami akan menggunakannya sebagai batu loncatan untuk menerapkan ide dasar.
Jika saya ingin menghitung penjumlahan dari sekelompok angka,
Misalnya, jika Anda lulus dalam nomor 3,
Saya ingin memberikan nilai sigma 3,
jadi jumlah 3 + 2 + 1 + 0.
Saya ingin mendapatkan kembali jawaban 6,
jadi kita akan menerapkan fungsi sigma, fungsi penjumlahan
itu, sekali lagi, mengambil input, dan kemudian kembali penjumlahan
dari jumlah tersebut semua jalan ke 0.
Kita bisa melakukan ini cukup sederhana, kan?
Kita bisa melakukan ini dengan beberapa jenis struktur perulangan,
jadi biarkan aku pergi ke depan dan mendapatkan ini dimulai.
>> Sertakan stdio.h.
Biarkan saya mendapatkan diri ke utama untuk bekerja dengan di sini.
Mari kita simpan ini sebagai sigma.c.
Lalu aku akan pergi di sini, dan aku akan mendeklarasikan int n,
dan aku akan melakukan hal berikut saat pengguna tidak bekerja sama.
Sementara pengguna tidak memberi saya angka positif
biarkan aku pergi ke depan dan meminta mereka untuk GetInt = n,
dan biarkan aku memberi mereka beberapa petunjuk untuk apa yang harus dilakukan,
sehingga printf ("bilangan bulat positif silahkan").
Sama relatif sederhana seperti ini sesuatu sehingga pada saat kita memukul baris 14
kita sekarang memiliki bilangan bulat positif mungkin dalam n.
>> Sekarang mari kita melakukan sesuatu dengan itu.
Biarkan aku pergi ke depan dan menghitung penjumlahan, sehingga int sum = sigma (n).
Sigma hanya penjumlahan, jadi aku hanya menulis dengan cara yang lebih menarik.
Kami hanya akan menyebutnya sigma ada.
Itulah jumlah itu, dan sekarang aku akan mencetak hasilnya,
printf ("Jumlahnya adalah% d, \ n", sum).
Dan kemudian aku akan kembali 0 untuk mengukur baik.
Kami telah melakukan segala sesuatu yang program ini membutuhkan kecuali bagian yang menarik,
yang sebenarnya adalah untuk mengimplementasikan fungsi sigma.
>> Biarkan aku pergi ke sini ke bawah, dan biarkan aku mendeklarasikan fungsi sigma.
Ini harus mengambil variabel yang bertipe integer,
dan apa tipe data yang saya ingin kembali mungkin dari sigma?
Int, karena saya ingin mencocokkan harapan saya on line 15.
Di sini biarkan aku pergi ke depan dan menerapkan ini
dengan cara yang cukup sederhana.
>> Mari kita pergi ke depan dan mengatakan jumlah int = 0,
dan sekarang aku akan pergi memiliki sedikit untuk loop di sini
itu akan mengatakan sesuatu seperti ini,
for (int i = 0; I <= nomor; i + +) jumlah + = i.
Dan kemudian aku akan kembali sum.
Saya bisa menerapkan ini dalam berbagai cara.
Saya bisa menggunakan loop sementara.
Saya bisa dilewati dengan menggunakan variabel jumlah jika saya benar-benar ingin,
tetapi dalam waktu singkat, kita hanya memiliki fungsi bahwa jika saya tidak menyia-nyiakan menyatakan jumlah adalah 0.
Kemudian iterates dari 0 ke atas melalui nomor,
dan pada setiap iterasi ia menambahkan bahwa nilai saat ini untuk jumlah dan kemudian kembali sum.
>> Sekarang, ada optimasi sedikit di sini.
Ini mungkin langkah sia-sia, tapi begitu baik. Itu baik untuk saat ini.
Kami setidaknya menjadi menyeluruh dan akan 0 semua jalan ke atas.
Tidak terlalu keras dan cukup sederhana,
tapi ternyata bahwa dengan fungsi sigma kita memiliki kesempatan yang sama
seperti yang kita lakukan di sini di atas panggung.
Di atas panggung kita hanya menghitung berapa banyak orang yang di samping saya,
tetapi jika kita ingin menghitung jumlah 3 + 2 + 1
pada turun ke 0 kita bisa sama menyepak bola ke fungsi
bahwa saya bukan akan menjelaskan sebagai rekursif.
Berikut mari kita lakukan sebuah kewarasan cepat memeriksa dan memastikan aku tidak menyia-nyiakan.
>> Saya tahu ada setidaknya satu hal dalam program ini yang aku lakukan salah.
Ketika saya tekan enter aku akan mendapatkan jenis berteriak padaku?
Apa yang saya akan berteriak tentang?
Ya, saya lupa prototipe, jadi aku menggunakan fungsi yang disebut sigma on line 15,
tapi itu tidak dideklarasikan sampai garis 22, jadi aku paling proaktif pergi di sini
dan menyatakan prototipe, dan saya akan mengatakan int sigma (int number), dan hanya itu.
Ini diterapkan di bagian bawah.
>> Atau cara lain saya bisa memecahkan masalah ini,
Saya bisa memindahkan fungsi di atas sana, yang tidak buruk,
tapi setidaknya ketika program Anda mulai mendapatkan panjang, terus terang,
Saya pikir ada beberapa nilai dalam selalu memiliki utama di bagian atas
sehingga Anda pembaca dapat membuka file tersebut dan kemudian segera melihat
program apa yang dilakukan tanpa harus mencari melalui itu
mencari fungsi utama.
Mari kita pergi ke jendela terminal saya di sini, cobalah membuat sigma membuat sigma,
dan saya kacau di sini juga.
Deklarasi implisit dari fungsi GetInt berarti saya sudah lupa untuk melakukan apa lagi?
[Tak terdengar-murid]
Baik, begitu rupanya kesalahan umum, jadi mari kita memasang ini di sini,
cs50.h, dan sekarang mari kita kembali ke jendela terminal saya.
>> Aku akan membersihkan layar, dan aku akan jalankan kembali membuat sigma.
Ini tampaknya telah disusun. Sekarang saya jalankan sigma.
Saya akan mengetikkan nomor 3, dan aku mendapatkan 6, sehingga tidak cek ketat,
tapi setidaknya itu tampaknya akan bekerja pada pandangan pertama, tapi sekarang mari kita robek itu terpisah,
dan mari kita benar-benar memanfaatkan gagasan rekursi, sekali lagi,
dalam konteks yang sangat sederhana sehingga dalam waktu beberapa minggu '
ketika kita mulai mengeksplorasi struktur data lebih menarik daripada array
kita memiliki alat lain dalam toolkit yang dapat digunakan untuk
memanipulasi struktur data tersebut seperti yang akan kita lihat.
Ini adalah pendekatan iteratif, pendekatan loop berbasis.
>> Biarkan aku bukan sekarang melakukan hal ini.
Biarkan saya bukan mengatakan bahwa penjumlahan nomor
pada turun ke 0 adalah benar-benar hal yang sama seperti
nomor + sigma (nomor - 1).
Dengan kata lain, sama seperti di atas panggung saya punted untuk masing-masing orang di sebelah saya,
dan mereka pada gilirannya terus punting sampai kami akhirnya dipercaya keluar di Willy,
yang harus kembali jawaban yang keras-kode seperti 0.
Disini sekarang kita sama punting ke sigma
fungsi yang sama seperti yang awalnya disebut, tetapi wawasan kunci di sini
adalah bahwa kita tidak menelepon sigma identik.
Kami tidak lewat di n.
Kami jelas lewat di nomor - 1,
sehingga masalah yang sedikit lebih kecil, masalah yang sedikit lebih kecil.
>> Sayangnya, hal ini tidak cukup solusi belum, dan sebelum kita memperbaiki
apa yang mungkin melompat keluar sebagai jelas pada beberapa dari Anda
biarkan aku pergi ke depan dan menjalankan kembali membuat.
Tampaknya untuk mengkompilasi baik-baik saja.
Mari saya memutarkan sigma dengan 6.
Whoops, biarkan aku memutarkan sigma dengan 6.
Kita telah melihat ini sebelumnya, meskipun waktu sengaja terakhir juga.
Mengapa saya mendapatkan kesalahan segmentasi samar? Ya.
[Tak terdengar-murid]
Tidak ada base case, dan lebih khusus lagi, apa yang mungkin terjadi?
Ini adalah gejala dari apa perilaku?
Katakanlah sedikit lebih keras.
[Tak terdengar-murid]
Ini loop tak terbatas secara efektif, dan masalah dengan loop tak terbatas
ketika mereka melibatkan rekursi dalam kasus ini, fungsi menamakan dirinya,
apa yang terjadi setiap kali Anda memanggil fungsi?
Nah, pikirkan kembali bagaimana kita meletakkan keluar memori di komputer.
Kami mengatakan bahwa ada ini sepotong memori yang disebut tumpukan yang di bagian bawah,
dan setiap kali Anda memanggil fungsi memori sedikit lebih akan dimasukkan
pada tumpukan disebut mengandung variabel lokal bahwa fungsi atau parameter,
jadi jika sigma panggilan panggilan sigma sigma panggilan sigma
panggilan sigma mana hal ini akhir ceritanya?
>> Nah, akhirnya overruns jumlah total
memori yang telah tersedia ke komputer Anda.
Anda dibanjiri segmen yang Anda seharusnya tinggal di dalam,
dan Anda mendapatkan kesalahan segmentasi, inti dibuang,
dan apa inti dibuang berarti bahwa saya sekarang memiliki sebuah file yang bernama inti
yang merupakan file yang berisi nol dan satu
bahwa sebenarnya di masa depan akan diagnosa berguna.
Jika tidak jelas bagi Anda di mana Anda adalah bug
Anda benar-benar dapat melakukan sedikit analisis forensik, sehingga untuk berbicara,
pada file dump inti, yang, sekali lagi, hanya sejumlah besar nol dan satu
yang pada dasarnya merupakan keadaan program Anda dalam memori
saat itu jatuh dengan cara ini.
>> Cara mengatasinya di sini adalah bahwa kita tidak bisa hanya membabi buta kembali sigma,
jumlah + sigma dari masalah yang sedikit lebih kecil.
Kita perlu memiliki semacam kasus dasar di sini,
dan apa yang harus kasus dasar mungkin akan?
[Tak terdengar-murid]
Oke, asalkan jumlah tersebut secara positif kita benar-benar harus kembali ini,
atau dengan kata lain, jika nomor adalah, katakanlah, <= 0 untuk
Anda tahu apa, saya akan pergi ke depan dan kembali 0,
seperti Willy lakukan, dan yang lain, aku akan pergi ke depan
dan kembali ini, sehingga tidak yang jauh lebih pendek
dari versi iteratif bahwa kita melecut pertama menggunakan untuk loop,
tetapi perhatikan bahwa ada semacam ini keanggunan untuk itu.
Alih-alih kembali beberapa nomor dan melakukan semua matematika ini
dan menambahkan hal-hal dengan variabel lokal
Anda malah berkata "Oke, jika ini adalah masalah super mudah,
seperti nomor adalah <0, biarkan aku segera kembali 0. "
>> Kita tidak akan repot-repot angka negatif pendukung,
jadi aku pergi ke kode keras nilai 0.
Tapi sebaliknya, untuk melaksanakan gagasan ini menjumlahkan
semua angka bersama Anda secara efektif dapat mengambil gigitan kecil
keluar dari masalah, seperti yang kita lakukan di sini di atas panggung,
maka punt sisa masalah kepada orang berikutnya,
tetapi dalam hal ini orang berikutnya adalah diri Anda sendiri.
Ini adalah fungsi bernama identik.
Hanya lulus masalah kecil dan lebih kecil dan lebih kecil setiap kali,
dan meskipun kami belum diformalkan dalam hal cukup kode di sini
ini adalah apa yang terjadi di minggu 0 dengan buku telepon.
Ini adalah persis apa yang terjadi dalam beberapa pekan terakhir dengan Sean
dan dengan demonstrasi kami mencari angka.
Ini mengambil masalah dan membaginya lagi dan lagi.
>> Dengan kata lain, ada cara sekarang menerjemahkan
ini membangun dunia nyata, ini membangun tingkat yang lebih tinggi
dari membagi dan menaklukkan dan melakukan sesuatu lagi dan lagi
dalam kode, jadi ini adalah sesuatu yang kita akan melihat lagi dari waktu ke waktu.
Sekarang, sebagai samping, jika Anda baru untuk rekursi Anda harus setidaknya mengerti sekarang
mengapa hal ini lucu.
Aku akan pergi ke google.com,
dan aku akan mencari beberapa tips dan trik rekursi, masukkan.
Beritahu orang di sebelah Anda jika mereka tidak tertawa sekarang.
Apakah maksud Anda rekursi?
Apakah maksud Anda-ah, di sana kita pergi.
Oke, sekarang itu sisa orang.
Sebuah telur Paskah kecil tertanam di suatu tempat ada di Google.
Sebagai samping, salah satu link yang kita pasang di web kursus ini
untuk hari ini hanya ini grid algoritma pemilahan berbagai,
beberapa di antaranya kita melihat pekan lalu, tapi apa yang baik tentang visualisasi ini
ketika Anda mencoba untuk membungkus pikiran Anda sekitar berbagai hal yang berkaitan dengan algoritma
tahu bahwa Anda dapat dengan mudah sekarang mulai dengan berbagai jenis input.
Masukan semua terbalik, masukan sebagian besar diurutkan, input acak dan sebagainya.
Ketika Anda mencoba untuk, sekali lagi, membedakan hal-hal ini dalam pikiran Anda
menyadari bahwa URL ini di website kursus pada halaman Kuliah
dapat membantu Anda melalui beberapa alasan dari mereka.
>> Hari ini kita akhirnya bisa memecahkan masalah ini dari beberapa waktu lalu,
yang adalah bahwa fungsi swap ini hanya tidak bekerja,
dan apa masalah mendasar dengan pertukaran fungsi,
tujuan yang, sekali lagi, untuk bertukar nilai di sini dan di sini
sehingga hal ini terjadi?
Hal ini tidak benar-benar bekerja. Kenapa?
Ya.
[Tak terdengar-murid]
Tepat, penjelasan untuk bugginess ini
hanya karena ketika Anda menelepon fungsi dalam C
dan fungsi-fungsi mengambil argumen, seperti a dan b di sini,
Anda lewat di salinan nilai apa pun yang Anda berikan untuk fungsi itu.
Anda tidak memberikan nilai-nilai asli sendiri,
jadi kami melihat ini dalam konteks buggyc,
buggy3.c, yang tampak sedikit sesuatu seperti ini.
>> Ingatlah bahwa kita memiliki x dan y diinisialisasi ke 1 dan 2, masing-masing.
Kami kemudian dicetak apa yang mereka.
Saya kemudian mengklaim bahwa saya menukar mereka dengan memanggil swap x, y.
Tapi masalahnya adalah bahwa swapping bekerja,
tetapi hanya dalam lingkup swap berfungsi sendiri.
Segera setelah kita memukul garis 40 nilai-nilai bertukar
yang dibuang, sehingga tidak ada
dalam fungsi utama asli sebenarnya berubah sama sekali,
jadi jika Anda berpikir waktu itu seperti apa ini terlihat seperti dalam hal memori kami
jika sisi kiri papan mewakili-
dan saya akan melakukan yang terbaik untuk semua orang untuk melihat ini-jika sisi kiri dari papan
mewakili, katakanlah, RAM Anda, dan stack akan tumbuh di atas cara ini,
dan kami memanggil fungsi seperti main, dan utama memiliki 2 variabel lokal, x dan y,
mari kita menggambarkan mereka sebagai x di sini, dan mari kita menjelaskan ini sebagai y di sini,
dan mari kita dimasukkan ke dalam nilai-nilai 1 dan 2, jadi ini di sini adalah utama,
dan ketika utama memanggil fungsi swap sistem operasi
memberikan fungsi swap petak sendiri memori di stack,
bingkai sendiri di stack, sehingga untuk berbicara.
Hal ini juga mengalokasikan 32 bit untuk ints tersebut.
Hal ini terjadi untuk memanggil mereka dan b, tapi itu benar-benar sewenang-wenang.
Ini bisa menyebut mereka apapun yang diinginkan, tapi apa yang terjadi ketika main
panggilan swap dibutuhkan ini 1, menempatkan salinan sana, menempatkan salinan sana.
>> Ada 1 variabel lokal lainnya di swap, meskipun, disebut apa? Tmp >>.
Tmp, jadi biarkan aku memberi diriku lagi 32 bit di sini,
dan apa yang saya lakukan dalam fungsi ini?
Aku berkata tmp int mendapat, sehingga memiliki 1, jadi saya melakukan ini ketika kami terakhir bermain dengan contoh ini.
Kemudian mendapat b, sehingga b adalah 2, jadi sekarang ini menjadi 2,
dan sekarang b mendapat suhu, sehingga suhu adalah 1,
jadi sekarang ini menjadi b.
Itu bagus. Ini bekerja.
Tapi kemudian segera setelah kembali fungsi
memori swap secara efektif menghilang sehingga dapat digunakan kembali
oleh beberapa fungsi lain di masa depan, dan utama adalah jelas benar-benar berubah.
Kita perlu cara fundamental memecahkan masalah ini,
dan hari ini kita akhirnya akan memiliki cara untuk melakukan hal ini dimana
kita dapat memperkenalkan sesuatu yang disebut pointer.
Ternyata bahwa kita bisa memecahkan masalah ini
bukan dengan lewat di salinan x dan y
melainkan dengan melewati dalam apa, apakah Anda berpikir, fungsi swap?
Ya, bagaimana dengan alamat?
Kami belum benar-benar berbicara tentang alamat di banyak detail,
tetapi jika papan ini merupakan memori komputer saya
kita pasti bisa memulai penomoran byte dalam RAM saya
dan mengatakan ini adalah byte # 1, ini adalah byte # 2, # 3 byte,
byte # 4, # byte ... 2 miliar jika saya memiliki 2 gigabyte RAM,
jadi kita pasti bisa datang dengan beberapa skema penomoran sewenang-wenang
untuk semua byte individu dalam memori komputer saya.
>> Bagaimana jika sebaliknya ketika saya sebut pertukaran
daripada lulus dalam salinan x dan y
kenapa tidak saya malah lulus dalam alamat dari x di sini,
alamat y di sini, pada dasarnya alamat pos
x dan y karena kemudian swap, jika dia memberitahu
dari alamat dalam memori dari x dan y,
kemudian swap, jika kita melatihnya sedikit,
ia berpotensi bisa mengarahkan ke alamat tersebut, sehingga untuk berbicara,
x, dan mengubah nomor di sana, kemudian pergi ke alamat y,
mengubah nomor di sana, bahkan ketika tidak benar-benar mendapatkan salinan dari nilai-nilai sendiri,
jadi meskipun kita bicarakan ini sebagai memori utama yang
dan ini Swap sebagai memori yang kuat dan bagian berbahaya dari C
adalah bahwa fungsi apapun dapat menyentuh memori di mana saja di komputer,
dan ini sangat kuat dalam bahwa Anda dapat melakukan hal-hal yang sangat mewah dengan program komputer di C.
Hal ini berbahaya karena Anda juga dapat mengacaukan sangat mudah.
Bahkan, salah satu cara yang paling umum untuk program hari ini untuk dimanfaatkan
masih untuk programmer tidak menyadari
bahwa ia adalah memungkinkan data
yang akan ditulis dalam sebuah lokasi di memori yang tidak dimaksudkan.
>> Misalnya, ia menyatakan sebuah array ukuran 10
tapi kemudian sengaja mencoba untuk menempatkan 11 byte ke dalam array memori,
dan Anda mulai menyentuh bagian-bagian dari memori yang tidak lagi berlaku.
Hanya untuk kontekstual ini, beberapa dari Anda mungkin tahu bahwa
perangkat lunak sering meminta Anda untuk nomor seri atau kunci pendaftaran,
Photoshop dan Word dan program-program seperti ini.
Ada ada retakan, karena beberapa dari Anda tahu, online di mana Anda dapat menjalankan program kecil,
dan voila, tidak ada permintaan lebih untuk nomor seri.
Bagaimana itu bekerja?
Dalam banyak kasus hal-hal ini hanya menemukan di komputer
teks segmen di nol sebenarnya komputer dan yang
mana adalah bahwa fungsi di mana nomor seri yang diminta,
dan Anda menimpa ruang itu, atau saat program sedang berjalan
Anda dapat mencari tahu di mana kunci sebenarnya disimpan
menggunakan sesuatu yang disebut debugger, dan Anda dapat crack software seperti itu.
Ini bukan untuk mengatakan bahwa ini adalah tujuan kami untuk beberapa hari,
tetapi memiliki sangat nyata-dunia konsekuensi.
Yang satu terjadi untuk melibatkan pencurian perangkat lunak,
tapi ada juga kompromi mesin keseluruhan.
>> Bahkan, ketika website hari ini dieksploitasi
dan dikompromikan dan data bocor dan password yang dicuri
ini sangat sering berhubungan dengan manajemen yang buruk dari memori seseorang,
atau, dalam kasus database, kegagalan untuk mengantisipasi
permusuhan masukan, sehingga lebih pada bahwa dalam minggu-minggu yang akan datang,
tapi untuk sekarang hanya sneak preview dari jenis kerusakan yang dapat Anda lakukan
dengan tidak cukup memahami bagaimana segala sesuatu bekerja di bawah tenda.
Mari kita pergi tentang memahami mengapa ini rusak
dengan alat yang akan menjadi lebih dan lebih berguna
program-program kami mendapatkan lebih kompleks.
Sejauh ini ketika Anda sudah bug dalam program Anda
bagaimana anda pergi tentang debugging?
Apa yang telah Anda teknik telah sejauh ini, apakah diajarkan oleh TF Anda
atau hanya otodidak?
[Mahasiswa] printf.
Printf, sehingga printf mungkin telah teman Anda dalam bahwa jika Anda ingin melihat
apa yang terjadi dalam program Anda
Anda hanya menempatkan printf sini, printf sini, printf sini.
Kemudian Anda menjalankannya, dan Anda mendapatkan sejumlah besar barang-barang di layar
yang dapat Anda gunakan untuk kemudian menyimpulkan apa yang sebenarnya terjadi salah dalam program Anda.
>> Printf cenderung menjadi hal yang sangat kuat,
tapi itu sebuah proses yang sangat manual.
Anda harus menempatkan printf sini, printf sini,
dan jika Anda memasukkannya ke dalam loop mungkin anda akan mendapatkan 100 baris
output yang kemudian harus menyaring.
Ini bukan mekanisme user-friendly atau interaktif yang sangat untuk program debugging,
tapi untungnya ada ada alternatif.
Ada sebuah program, misalnya, disebut GDB, GNU Debugger,
yang merupakan rahasia sedikit bagaimana Anda menggunakannya.
Ini sedikit rumit, tapi terus terang,
ini adalah salah satu hal di mana jika Anda masukkan ke dalam minggu ini dan berikutnya
jam tambahan untuk memahami sesuatu seperti GDB
itu akan menghemat mungkin puluhan jam dalam jangka panjang,
sehingga dengan itu, izinkan saya memberi Anda sebuah teaser tentang bagaimana hal ini bekerja.
>> Saya di jendela terminal saya.
Biarkan aku pergi ke depan dan mengkompilasi program ini, buggy3.
Ini sudah up to date.
Mari saya menjalankannya seperti yang kami lakukan beberapa waktu lalu, dan memang, itu rusak.
Tapi mengapa ini? Mungkin aku mengacaukan fungsi swap.
Mungkin itu a dan b. Saya tidak cukup memindahkan mereka sekitar dengan benar.
Biarkan aku pergi ke depan dan melakukan hal ini.
Daripada hanya menjalankan buggy3 biarkan aku bukannya menjalankan GDB program,
dan aku akan mengatakan itu untuk menjalankan buggy3,
dan aku akan menyertakan sebuah argumen baris perintah,-tui,
dan kami akan menempatkan ini dalam masalah masa depan di spec untuk mengingatkan.
Dan sekarang ini antarmuka hitam dan putih muncul itu, sekali lagi,
adalah sedikit berlebihan pada awalnya karena ada semua ini
Informasi garansi di sini, tapi setidaknya ada sesuatu yang akrab.
Di bagian atas jendela adalah kode yang sebenarnya,
dan jika saya gulir di sini biarkan aku gulir ke bagian paling atas dari file saya,
dan memang, ada buggy3.c, dan perhatikan di bagian bawah jendela ini
Aku punya cepat GDB.
>> Ini tidak sama seperti biasa saya Harvard John prompt.
Ini adalah sebuah prompt yang akan memungkinkan saya untuk mengontrol GDB.
GDB adalah debugger.
Debugger adalah program yang memungkinkan Anda berjalan melalui
pelaksanaan program baris dengan baris demi baris,
sepanjang jalan melakukan apa pun yang Anda ingin program ini,
bahkan memanggil fungsi, atau mencari, yang lebih penting,
pada nilai variabel berbagai s.
Mari kita pergi ke depan dan melakukan hal ini.
Aku akan pergi ke depan dan ketik dalam jangka pada prompt GDB itu,
jadi perhatikan di bagian bawah kiri layar aku mengetik dijalankan,
dan aku sudah tekan enter, dan apa yang mereka lakukan?
Ini benar-benar berlari program saya, tapi saya tidak benar-benar melihat banyak pergi di sini
karena saya belum benar-benar mengatakan debugger
untuk berhenti pada suatu saat tertentu.
Hanya mengetik run menjalankan program.
Saya tidak benar-benar melihat apa-apa. Saya tidak bisa memanipulasinya.
>> Alih-alih membiarkan saya melakukan hal ini.
Pada prompt GDB biarkan aku bukan tipe istirahat, masukkan.
Itu bukan apa yang saya dimaksudkan untuk mengetik.
Mari kita bukannya mengetik istirahat utama.
Dengan kata lain, saya ingin mengatur sesuatu yang disebut breakpoint,
yang aptly bernama karena akan istirahat atau jeda
pelaksanaan program anda di tempat tertentu.
Main adalah nama fungsi saya.
Perhatikan bahwa GDB cukup pintar.
Ini tahu bahwa utama terjadi mulai kira-kira pada baris 18
dari buggy3.c, dan kemudian melihat di sini di sebelah kiri atas
b + tepat di sebelah garis 18.
Itu mengingatkan saya bahwa saya telah menetapkan breakpoint pada baris 18.
Kali ini ketika saya mengetik lari, aku akan menjalankan program saya
sampai hits breakpoint itu,
sehingga program akan berhenti untuk saya pada baris 18.
Di sini kita pergi, jalankan.
Tidak ada yang tampaknya telah terjadi, tapi perhatikan di bagian kiri bawah
memulai program, buggy3, breakpoint 1 di utama pada baris buggy3.c 18.
Apa yang bisa saya lakukan sekarang?
>> Perhatikan saya bisa mulai mengetik hal-hal seperti cetak,
tidak printf, x cetak, dan sekarang itu aneh.
$ 1 hanya rasa ingin tahu, seperti yang kita akan melihat
setiap kali Anda mencetak sesuatu Anda mendapatkan nilai $ baru.
Itu sehingga Anda dapat merujuk kembali ke nilai sebelumnya hanya dalam kasus,
tapi untuk sekarang apa cetak mengatakan saya adalah bahwa nilai x pada titik ini dalam cerita
ternyata 134.514.032.
Apa? Mana yang bahkan datang dari?
[Tak terdengar-murid]
Memang, ini adalah apa yang kita sebut nilai sampah, dan kami sudah tidak membicarakan hal ini belum,
tetapi alasan bahwa Anda menginisialisasi variabel
jelas sehingga mereka memiliki beberapa nilai yang Anda ingin mereka miliki.
Tapi tangkapan ingat bahwa Anda dapat mendeklarasikan variabel
seperti yang saya lakukan beberapa saat yang lalu dalam contoh sigma saya
tanpa benar-benar memberi mereka nilai.
Ingat apa yang saya lakukan di sini di sigma.
Saya menyatakan n, tapi apa nilai yang saya berikan?
Tidak ada, karena saya tahu bahwa dalam beberapa baris berikutnya
GetInt akan mengurus masalah menempatkan nilai dalam n.
>> Tapi pada titik ini dalam kisah baris 11
dan garis 12 dan baris 13 dan baris 14
seluruh garis beberapa berapakah nilai dari n?
Dalam C Anda hanya tidak tahu.
Itu umumnya beberapa nilai sampah, beberapa nomor benar-benar acak
yang tersisa pada dasarnya dari beberapa fungsi sebelumnya
yang telah dijalankan, sehingga program Anda berjalan
ingat bahwa fungsi mendapatkan fungsi, fungsi, fungsi.
Semua frame bisa memakai memori, dan kemudian mereka kembali fungsi,
dan seperti saya menyarankan dengan penghapus memori mereka akhirnya digunakan kembali.
Nah, kebetulan bahwa variabel x dalam program ini
tampaknya telah mengandung beberapa nilai seperti sampah 134514032
dari beberapa fungsi sebelumnya, tak satu pun yang saya tulis.
Ini bisa menjadi sesuatu yang datang secara efektif dengan sistem operasi,
beberapa fungsi di bawah tenda.
>> Oke, itu bagus, tetapi mari kita sekarang maju ke baris berikutnya.
Jika saya ketik "berikutnya" pada saya GDB prompt dan saya tekan enter,
melihat bahwa menyoroti bergerak ke baris 19,
tetapi implikasi logis adalah bahwa garis 18
kini telah selesai mengeksekusi, jadi jika saya kembali ketik "print x"
Sekarang saya akan melihat 1, dan memang, saya lakukan.
Sekali lagi, hal-hal $ adalah cara GDB mengingatkan Anda
apa sejarah cetak adalah bahwa Anda lakukan.
Sekarang biarkan aku pergi ke depan dan mencetak y, dan memang, y adalah beberapa nilai gila juga,
tapi bukan masalah besar karena di baris 19 kita akan menetapkan
nilai 2, jadi biar ketik "next" lagi.
Dan sekarang kita berada di garis printf.
Biarkan aku melakukan x cetak.
Biarkan aku melakukan y cetak. Terus terang, saya mendapatkan sedikit lelah pencetakan ini.
Biarkan saya bukan ketik "display x" dan "y layar,"
dan sekarang setiap kali saya ketik perintah di masa depan
Aku akan teringat apa x dan y, apa x dan y, apa x dan y.
>> Saya juga dapat, sebagai tipe samping, dalam "penduduk setempat info."
Info adalah perintah khusus.
Penduduk setempat berarti itu menunjukkan saya variabel lokal.
Hanya dalam kasus saya lupa atau ini adalah fungsi, gila rumit
bahwa saya atau orang lain menulis penduduk setempat Info akan memberitahu Anda
apa semua variabel lokal dalam fungsi lokal
bahwa Anda mungkin peduli jika Anda ingin melihat-lihat.
Sekarang, printf adalah untuk mengeksekusi, jadi biarkan aku pergi ke depan dan ketikkan "berikutnya."
Karena kita berada di lingkungan ini kita tidak benar-benar melihatnya
mengeksekusi di sini, tapi perhatikan itu semakin sedikit hancur di sini.
Tapi perhatikan itu override layar ada,
jadi bukan program yang sempurna di sini, tapi tidak apa-apa karena saya selalu bisa menyodok sekitar
menggunakan print jika saya ingin.
>> Mari saya ketik next lagi, dan sekarang inilah bagian yang menarik.
Pada titik ini dalam cerita y adalah 2, dan x adalah 1,
seperti yang disarankan di sini, dan lagi,
alasan ini secara otomatis menampilkan sekarang adalah karena saya menggunakan perintah
display x dan y layar, sehingga saat aku mengetik berikutnya
dalam teori x dan y harus menjadi bertukar.
Sekarang, kita sudah tahu itu tidak akan terjadi,
tapi kita akan lihat sebentar lagi bagaimana kita bisa menyelam lebih dalam untuk mencari tahu mengapa itu benar.
Selanjutnya, dan sayangnya, y masih 2 dan x masih 1, dan saya bisa mengkonfirmasikan sebanyak.
Cetak x, y cetak.
Memang, tidak ada swapping sebenarnya telah terjadi, jadi mari kita mulai hal ini.
Jelas swap rusak.
Mari kita bukan ketik "run" lagi.
Izinkan saya mengatakan ya, saya ingin memulai kembali dari awal, masukkan.
>> Sekarang aku kembali pada baris 18.
Sekarang perhatikan x dan y adalah nilai-nilai sampah lagi.
Selanjutnya, berikutnya, berikutnya, berikutnya.
Jika saya bosan saya juga bisa cukup ketik n untuk selanjutnya.
Anda dapat menyingkatnya dengan urutan sesingkat mungkin karakter.
Swap sekarang rusak.
Mari selami, sehingga bukannya mengetik berikutnya,
sekarang aku akan mengetik langkah sehingga saya melangkah di dalam fungsi ini
sehingga saya dapat berjalan melalui itu, jadi aku memukul langkah dan kemudian enter.
Perhatikan bahwa melompat menyoroti turun lebih rendah dalam program saya ke baris 36.
Sekarang apa variabel lokal?
Info penduduk setempat.
Tidak hanya namun karena kita sudah tidak mendapatkan ke baris tersebut,
jadi mari kita pergi ke depan dan berkata "selanjutnya."
Sekarang kita tampaknya memiliki tmp, tmp cetak.
Nilai sampah, kan? Saya kira begitu.
Bagaimana mencetak, print b, 1 dan 2?
Dalam beberapa saat, segera setelah saya ketik next lagi
tmp akan mengambil nilai 1, mudah-mudahan,
karena tmp akan diberi nilai dari.
>> Sekarang mari kita lakukan mencetak b, cetak,
tapi sekarang mencetak tmp, dan itu memang 1.
Biarkan saya lakukan selanjutnya. Biarkan saya lakukan selanjutnya.
Aku sudah selesai fungsi swap.
Aku masih di dalamnya di baris 40, jadi biar mencetak,
print b, dan aku tidak peduli apa yang tmp.
Sepertinya swap adalah benar ketika datang untuk swapping dan b.
Tapi kalau aku sekarang ketik berikutnya, saya melompat kembali ke baris 25,
dan tentu saja, jika saya ketik x dan y cetak
mereka masih tidak berubah, jadi kita belum tetap masalah.
Tapi diagnosa sekarang mungkin dengan program GDB
kami telah mendapatkan setidaknya satu langkah lebih dekat untuk memahami
apa yang salah tanpa harus serasah kode kita dengan meletakkan printf sini,
printf sini, printf sini dan kemudian berjalan lagi dan lagi
mencoba untuk mencari tahu apa yang salah.
>> Aku akan pergi ke depan dan berhenti keluar dari ini sama sekali dengan berhenti.
Ini akan kemudian berkata, "Keluar sih?" Ya.
Sekarang aku kembali pada prompt normal saya, dan saya sudah selesai menggunakan GDB.
Sebagai samping, Anda tidak perlu menggunakan ini-tui bendera.
Bahkan, jika Anda menghilangkan itu Anda mendapatkan dasarnya bagian bawah layar.
Jika saya kemudian ketik istirahat utama dan kemudian jalankan
Saya masih bisa menjalankan program saya, tapi apa yang akan dilakukan adalah lebih tekstual
hanya menunjukkan satu baris saat ini pada satu waktu.
The-tui, antarmuka pengguna tekstual,
hanya menunjukkan Anda lebih dari program sekaligus, yang mungkin sedikit lebih mudah konseptual.
Tapi memang, saya hanya bisa lakukan selanjutnya, next, next,
dan aku akan melihat satu baris pada satu waktu, dan jika saya benar-benar ingin melihat apa yang terjadi
Saya bisa mengetik daftar dan melihat sejumlah besar baris tetangga.
>> Ada video yang kita telah meminta bahwa Anda menonton untuk masalah set 3
di mana Nate mencakup beberapa seluk-beluk GDB,
dan ini adalah salah satu hal, jujur, di mana beberapa persentase non-sepele Anda
tidak akan pernah menyentuh GDB, dan itu akan menjadi hal yang buruk
karena secara harfiah Anda akan berakhir menghabiskan lebih banyak waktu nanti semester ini
memburu bug maka Anda akan jika anda menaruh di setengah jam / jam
minggu ini dan belajar berikutnya untuk mendapatkan nyaman dengan GDB.
Printf adalah teman Anda.
GDB sekarang harus menjadi teman Anda.
>> Setiap pertanyaan tentang GDB?
Dan di sini adalah daftar singkat dari beberapa perintah yang paling kuat dan berguna.
Ya. >> Dapatkah Anda mencetak string?
Dapatkah Anda mencetak string? Tentu saja.
Ini tidak harus hanya menjadi bilangan bulat.
Jika variabel s adalah string ketik saja s cetak.
Ini akan menunjukkan kepada Anda apa yang variabel string adalah.
[Tak terdengar-murid]
Ini akan memberi Anda alamat dan string itu sendiri.
Ini akan menunjukkan Anda berdua.
Dan satu hal lagi, hanya karena ini adalah baik untuk mengetahui juga.
Backtrace dan frame, biarkan aku menyelam ke dalam kali ini yang terakhir,
sama program dengan GDB.
Biarkan aku pergi ke depan dan menjalankan versi antarmuka pengguna tekstual,
istirahat utama.
Biarkan aku pergi ke depan dan berjalan lagi. Aku di sini.
Sekarang biarkan aku pergi next, next, next, next, selanjutnya, langkah, masukkan.
>> Dan sekarang kira aku sekarang di swap sengaja, tapi aku seperti "Sialan, apa nilai x?"
Saya tidak bisa melakukan x lagi.
Saya tidak bisa melakukan y karena mereka tidak dalam lingkup.
Mereka tidak dalam konteks, tapi tidak ada masalah.
Saya bisa mengetik backtrace.
Itu menunjukkan saya semua fungsi yang telah dieksekusi sampai dengan titik waktu ini.
Perhatikan bahwa satu di bawah, utama, jalur utama dengan
berada di bawah gambar kami di sini.
Fakta bahwa swap adalah di atasnya berbaris dengan swap berada di atas dalam memori di sini,
dan jika saya ingin kembali ke utama sementara bisa saya katakan "frame."
Nomor berapa? Main bingkai # 1.
Aku akan pergi ke depan dan berkata "frame 1."
>> Sekarang aku kembali main, dan saya bisa mencetak x, dan saya dapat mencetak y,
tapi aku tidak bisa mencetak b atau.
Tapi aku bisa jika saya mengatakan, "Oke, tunggu sebentar Dimana swap?."
Biarkan aku pergi ke depan dan berkata "0 frame."
Sekarang aku kembali di mana saya ingin menjadi, dan sebagai samping,
ada perintah lain juga, seperti jika Anda benar-benar mendapatkan mengetik bosan next, next, next, next,
biasanya Anda bisa mengatakan hal-hal seperti "10 berikutnya," dan itu akan melangkah melalui 10 baris berikutnya.
Anda juga dapat menulis "lanjutkan" ketika Anda benar-benar mendapatkan muak dengan melangkah melewatinya.
Lanjutkan akan menjalankan program Anda tanpa gangguan sampai hits breakpoint lain,
apakah dalam satu lingkaran atau menurunkan bawah dalam program Anda.
>> Dalam hal ini kami terus sampai akhir, dan program keluar secara normal.
Ini adalah cara yang mewah, proses rendah.
Hanya program anda keluar secara normal.
Lagi di dalam video dan debugging sesi yang akan datang.
Itu banyak.
Mari kita 5 menit istirahat kami di sini, dan kami akan kembali dengan structs dan file.
>> Jika Anda telah menyelam ke pset minggu ini sudah
Anda akan tahu bahwa kita gunakan dalam kode distribusi,
sumber kode yang kami sediakan untuk Anda sebagai titik awal, beberapa teknik baru.
Secara khusus, kami memperkenalkan kata kunci baru yang disebut struct, untuk struktur,
sehingga kita dapat membuat variabel disesuaikan macam.
Kami juga memperkenalkan konsep file I / O, file input dan output,
dan ini adalah agar kita dapat menyelamatkan negara
dewan Scramble Anda ke file pada disk
sehingga rekan-rekan mengajar dan aku bisa mengerti
apa yang terjadi di dalam program Anda tanpa harus bermain secara manual
puluhan permainan Scramble.
Kita bisa melakukan ini lebih automatedly.
>> Ini ide struct memecahkan masalah yang cukup menarik.
Misalkan kita ingin menerapkan beberapa program
yang entah bagaimana melacak informasi pada siswa,
dan mahasiswa mungkin, misalnya, ID, nama
dan sebuah rumah di tempat seperti Harvard, jadi ini adalah 3 potongan informasi
kami ingin menjaga sekitar, jadi biarkan aku pergi ke depan dan mulai menulis sebuah program kecil di sini,
termasuk stdio.h.
Biarkan aku melakukan termasuk cs50.h.
Dan kemudian mulai fungsi utama saya.
Aku tidak akan repot-repot dengan argumen baris perintah,
dan di sini saya ingin memiliki mahasiswa, jadi aku akan mengatakan
siswa memiliki nama, jadi aku akan mengatakan "string name."
Lalu aku akan mengatakan mahasiswa juga memiliki ID, id sehingga int,
dan mahasiswa memiliki rumah, jadi aku juga akan mengatakan "rumah string."
Lalu aku akan memesan ini sedikit lebih bersih seperti ini.
Oke, sekarang aku punya 3 variabel yang dapat digunakan untuk mewakili mahasiswa, jadi "mahasiswa."
>> Dan sekarang saya ingin mengisi nilai-nilai, jadi biarkan aku pergi ke depan dan mengatakan sesuatu seperti
"Id = 123."
Nama akan mendapatkan David.
Katakanlah rumah akan mendapatkan Mather,
dan kemudian aku akan melakukan sesuatu yang sewenang-wenang seperti printf ("% s,
mana ID adalah% d, tinggal di s%.
Dan sekarang, apa yang ingin saya pasang di sini, satu demi satu?
Nama, id, rumah, kembali 0.
Oke, kecuali aku kacau di suatu tempat di sini
Saya pikir kami memiliki program yang cukup bagus yang menyimpan satu siswa.
Tentu saja, hal ini tidak semua yang menarik. Bagaimana jika saya ingin memiliki 2 siswa?
Itu bukan masalah besar. Saya dapat mendukung 2 orang.
Biarkan aku pergi ke depan dan menyorot ini dan pergi ke sini,
dan saya dapat mengatakan "id = 456" untuk seseorang seperti Rob yang tinggal di Kirkland.
>> Oke, tunggu, tapi aku tidak bisa menyebutnya hal yang sama,
dan sepertinya aku akan harus menyalin ini,
jadi saya katakan bahwa ini akan menjadi variabel Daud,
dan biarkan aku mendapatkan beberapa salinan ini untuk Rob.
Kita akan menyebutnya Rob tapi ini tidak akan bekerja sekarang
karena saya telah menunggu-, mari kita mengubah saya untuk id1, name1 dan House1.
Rob akan menjadi 2, 2.
Aku harus mengubah ini di sini, sini, sini, sini, sini, sini.
Tunggu, bagaimana dengan Tommy? Mari kita lakukan ini lagi.
Tentunya jika Anda masih berpikir ini adalah cara yang baik untuk melakukan hal ini, itu tidak,
jadi copy / paste buruk.
Tapi kita memecahkan ini seminggu yang lalu.
>> Apa solusi kami ketika kita ingin memiliki beberapa contoh dari tipe data yang sama?
[Siswa] Array.
Array, jadi saya mencoba untuk membersihkan ini.
Mari saya membuat beberapa ruang untuk diriku sendiri di bagian atas, dan biarkan aku bukan melakukannya di sini.
Kami akan memanggil orang-orang ini, dan sebagai gantinya aku akan mengatakan "id int,"
dan aku akan mendukung 3 dari kita untuk saat ini.
Aku akan mengatakan "nama string," dan aku akan mendukung 3 dari kita,
dan kemudian aku akan mengatakan "rumah string," dan aku akan mendukung 3 dari kita.
Sekarang di sini bukannya Daud mendapatkan variabel sendiri lokal
kita bisa menyingkirkan mereka.
Itu terasa baik bahwa kita membersihkan ini up.
Saya kemudian bisa mengatakan Daud akan menjadi [0] dan nama [0]
dan rumah-rumah [0].
Dan kemudian Rob kita sama dapat menghemat ini.
Mari kita menempatkan ini di sini, jadi dia akan menjadi sewenang-wenang id [1].
Dia akan menjadi nama [1],
dan kemudian terakhir, rumah [1].
>> Masih sedikit membosankan, dan sekarang aku harus memikirkan hal ini,
jadi mari kita katakan "nama [0], id [0], rumah [0],
dan mari kita mempluralkan ini.
Id, id, id.
Dan lagi, aku melakukannya, jadi sekali lagi, saya sudah beralih ke copy / paste lagi,
sehingga kemungkinan besar ada solusi lain di sini.
Aku mungkin bisa membersihkan ini lebih lanjut dengan loop atau sesuatu seperti itu,
sehingga singkatnya, itu sedikit lebih baik tapi masih terasa seperti
Saya beralih untuk copy / paste, tapi bahkan ini, saya menyatakan,
tidak benar-benar fundamental solusi yang tepat karena
bagaimana jika suatu saat kita memutuskan Anda tahu apa?
Kami benar-benar harus telah menyimpan alamat email untuk David dan Rob
dan semua orang di program ini.
Kita juga harus menyimpan nomor telepon.
Kita juga harus menyimpan nomor kontak darurat.
Kami memiliki semua potongan-potongan dari data yang ingin kita simpan,
jadi bagaimana Anda pergi untuk melakukan itu?
>> Anda mendeklarasikan array lain di bagian atas, dan kemudian Anda tambahkan secara manual
alamat email [0], alamat email [1]
untuk David dan Rob dan sebagainya.
Tapi ada benar-benar hanya sebuah asumsi yang mendasari desain ini
bahwa saya menggunakan sistem kehormatan untuk mengetahui bahwa
[I] di setiap susunan beberapa
hanya begitu terjadi untuk merujuk pada orang yang sama,
sehingga [0] di id adalah nomor 123,
dan aku akan berasumsi bahwa nama [0]
adalah orang yang sama nama dan rumah [0]
adalah rumah orang yang sama dan sebagainya untuk semua array berbagai yang saya buat.
Tapi perhatikan bahwa tidak ada hubungan mendasar
di antara mereka 3 potongan informasi, nama id, dan rumah,
meskipun badan kita mencoba untuk model dalam program ini bukan array.
Array hanya ini cara program untuk melakukan hal ini.
Apa yang kita benar-benar ingin model dalam program kami adalah orang
seperti Daud, orang seperti Rob yang di dalamnya
atau encapsulating adalah nama dan ID dan rumah.
>> Bisakah kita entah bagaimana mengekspresikan ide enkapsulasi
dimana seseorang memiliki ID, nama dan rumah
dan tidak resor untuk benar-benar hack ini dimana kita hanya
percaya bahwa sesuatu braket
mengacu pada entitas manusia yang sama di masing-masing array yang berbeda?
Kami benar-benar bisa melakukan ini.
Biarkan aku pergi di atas utama untuk saat ini, dan biarkan aku membuat tipe sendiri Data
untuk benar-benar pertama kalinya.
Kami menggunakan teknik ini dalam Scramble,
tapi di sini aku akan pergi ke depan dan menciptakan tipe data,
dan kau tahu apa, aku akan menyebutnya siswa atau orang,
dan aku akan menggunakan typedef untuk mendefinisikan tipe.
Aku akan mengatakan bahwa ini adalah struktur,
dan kemudian struktur ini akan menjadi siswa jenis, kita akan mengatakan,
meskipun itu sedikit tanggal sekarang bagi saya.
Kami akan mengatakan "int id."
Kami akan mengatakan "string name."
Kemudian kita akan mengatakan "Rumah string,"
jadi sekarang pada akhir dari beberapa baris kode
Saya baru saja mengajarkan dentang bahwa ada
tipe data selain ints, selain string, selain ganda, selain mengapung.
>> Sampai saat ini dalam garis waktu 11, sekarang ada tipe data baru yang disebut mahasiswa,
dan sekarang saya bisa mendeklarasikan variabel mahasiswa mana saja aku ingin,
jadi biar scroll ke bawah sini untuk orang.
Sekarang saya bisa menyingkirkan ini, dan saya bisa kembali ke sini David,
dan untuk David saya benar-benar dapat mengatakan bahwa David,
kita benar-benar dapat nama variabel setelah diriku sendiri,
akan menjadi mahasiswa tipe.
Ini mungkin terlihat sedikit aneh, tapi ini tidak semua yang berbeda
dari menyatakan sesuatu sebagai int atau string atau pelampung.
Kebetulan dipanggil mahasiswa sekarang,
dan jika saya ingin menempatkan sesuatu di dalam struktur ini
Saya sekarang harus menggunakan sepotong baru sintaks, tapi itu cukup sederhana,
david.id = 123, david.name = "David" di ibukota D,
dan david.house = "Mather,"
dan sekarang saya bisa menyingkirkan barang-barang ini di sini.
Pemberitahuan sekarang kami telah didesain ulang program kami di benar-benar cara yang lebih baik
dalam program kami sekarang mencerminkan dunia nyata.
>> Ada gagasan dunia nyata dari seseorang atau mahasiswa.
Di sini kita miliki sekarang versi C dari seseorang atau lebih khusus mahasiswa.
Di dalam orang yang karakteristik yang relevan,
ID, nama dan rumah, sehingga Rob dasarnya menjadi hal yang sama di sini,
sehingga mahasiswa rob, dan sekarang rob.id = 456,
rob.name = "Rob."
Fakta bahwa variabel disebut Rob adalah semacam berarti.
Kita bisa menyebutnya x atau y atau z.
Kami hanya menamakannya Rob menjadi semantis konsisten,
tapi benar-benar nama adalah dalam bidang tersebut sendiri,
jadi sekarang aku punya ini.
Hal ini juga tidak merasa seperti desain terbaik dalam bahwa saya telah keras kode David.
Saya sudah keras kode Rob.
Dan aku masih harus resor untuk copy dan paste beberapa setiap kali saya ingin variabel baru.
Selain itu, saya harus memberikan rupanya masing-masing variabel nama,
meskipun saya lebih suka mendeskripsikan variabel-variabel
lebih umum sebagai siswa.
>> Sekarang kita dapat menggabungkan ide-ide yang telah bekerja dengan baik bagi kami
dan bukannya mengatakan, "Kau tahu apa, beri saya siswa disebut variabel,
dan mari kita memilikinya menjadi ukuran 3, "jadi sekarang aku bisa memperbaiki ini lebih lanjut,
menyingkirkan David manual menyatakan,
dan saya malah dapat mengatakan sesuatu seperti siswa [0] di sini.
Saya kemudian bisa mengatakan siswa [0] di sini,
siswa [0] di sini, dan sebagainya, dan aku bisa pergi sekitar
dan membersihkan bahwa untuk Rob.
Saya juga bisa pergi tentang sekarang mungkin menambahkan loop
dan menggunakan GetString dan GetInt untuk benar-benar mendapatkan nilai-nilai dari pengguna.
Aku bisa pergi tentang menambahkan konstan karena ini umumnya praktik buruk
untuk kode keras beberapa nomor sewenang-wenang seperti 3 di sini
dan kemudian hanya ingat bahwa Anda harus menempatkan tidak lebih dari 3 siswa di dalamnya.
Mungkin akan lebih baik untuk menggunakan # define di bagian atas file saya
dan faktor yang keluar, sehingga memang, biarkan aku pergi ke depan dan generalisasi ini.
>> Mari saya membuka sebuah contoh yang salah hari ini
contoh di muka, structs1.
Ini merupakan program yang lebih lengkap yang menggunakan # define di sini
dan mengatakan kita akan memiliki 3 siswa secara default.
Di sini saya menyatakan senilai kelas siswa,
sehingga kelas siswa, dan sekarang saya menggunakan loop
hanya untuk membuat kode sedikit lebih elegan, mengisi kelas
dengan input pengguna, jadi iterate dari i = 0 pada hingga mahasiswa, yaitu 3.
Dan kemudian saya meminta pengguna dalam versi ini
apa ID siswa, dan saya mendapatkannya dengan GetInt.
Siapa nama siswa, dan kemudian saya mendapatkannya dengan GetString.
Apa rumah siswa? Saya mendapatkannya dengan GetString.
Dan kemudian di bagian bawah di sini saya hanya memutuskan untuk mengubah
bagaimana aku mencetak tersebut keluar dan benar-benar menggunakan loop,
dan yang saya mencetak?
Menurut komentar saya mencetak siapa pun di Mather,
dan itu begitu Rob dan Tommy dan sebagainya-sebenarnya Tommy di Mather.
Tommy dan David akan dicetak dalam kasus ini, tapi bagaimana ini bekerja?
Kami belum melihat fungsi ini sebelumnya, tetapi mengambil menebak untuk apa hal ini.
Membandingkan string.
>> Ini agak tidak jelas bagaimana membandingkan string karena ternyata
jika ia mengembalikan 0 yang berarti string adalah sama.
Jika ia mengembalikan -1 yang berarti satu abjad datang sebelum yang lain,
dan jika ia mengembalikan +1 yang berarti kata lain datang abjad
sebelum yang lain, dan Anda dapat melihat secara online atau di halaman manual
untuk melihat secara tepat jalan mana mana, tapi semua ini lakukan sekarang ini itu mengatakan
jika [i]. rumah adalah sama dengan "Mather"
kemudian pergi ke depan dan mencetak begitu dan begitu berada di Mather.
Tapi di sini sesuatu yang kita belum melihat sebelumnya, dan kami akan kembali ke ini.
Saya tidak ingat pernah memiliki untuk melakukan hal ini dalam salah satu program saya.
Gratis ini rupanya mengacu pada memori, membebaskan memori,
tapi apa memori saya tampaknya membebaskan dalam lingkaran ini di bagian bawah program ini?
Sepertinya aku membebaskan nama seseorang
dan rumah seseorang, tapi kenapa begitu?
>> Ternyata semua minggu yang Anda telah menggunakan GetString
kita jenis telah memperkenalkan bug ke dalam setiap salah satu dari program Anda.
GetString oleh memori desain mengalokasikan sehingga bisa kembali kepada Anda string,
seperti Daud, atau Rob, dan Anda kemudian dapat melakukan apapun yang Anda inginkan
dengan string dalam program anda karena kami telah disediakan memori untuk Anda.
Masalahnya adalah selama ini setiap kali Anda menelepon GetString
kita, penulis GetString, telah meminta sistem operasi
untuk memberi kami sedikit RAM untuk string ini.
Beri kami sedikit RAM untuk string berikutnya.
Beri kami RAM lagi untuk string berikutnya.
Apa yang Anda, programmer, belum pernah melakukan
memberikan kita itu kembali memori,
jadi untuk beberapa minggu ini semua program yang sudah Anda tulis
memiliki apa yang disebut lompatan memori dimana mereka tetap menggunakan
memori lebih dan lebih setiap kali Anda menelepon GetString, dan itu baik-baik saja.
Kami sengaja melakukan itu pada minggu-minggu pertama karena itu tidak menarik
harus khawatir tentang di mana string berasal.
Semua yang Anda inginkan adalah kata Rob kembali bila pengguna jenis itu masuk
>> Tapi bergerak maju sekarang kita harus mulai mendapatkan lebih canggih tentang hal ini.
Setiap kali kita mengalokasikan memori lebih baik kita akhirnya menyerahkannya kembali.
Jika di dunia nyata pada Mac atau PC Anda mungkin memiliki sesekali mengalami
gejala di mana komputer Anda adalah penggilingan berhenti pada akhirnya
atau bola pantai bodoh berputar hanya menempati komputer
seluruh perhatian dan Anda tidak bisa melakukan hal-hal.
Yang dapat dijelaskan oleh sejumlah bug, tetapi di antara mereka kemungkinan bug
adalah hal-hal yang disebut kebocoran memori dimana seseorang yang menulis bahwa software
Anda menggunakan tidak ingat untuk membebaskan memori
bahwa ia meminta sistem operasi untuk,
tidak menggunakan GetString, karena itu hal yang CS50, tetapi menggunakan fungsi yang sama
yang meminta sistem operasi untuk memori.
Jika Anda atau mereka mengacaukan dan tidak pernah benar-benar kembali memori yang
merupakan gejala yang dapat bahwa program melambat dan memperlambat dan memperlambat
kecuali Anda ingat untuk panggilan gratis.
>> Kami akan kembali ke kapan dan mengapa Anda akan panggilan gratis,
tapi mari kita pergi ke depan hanya untuk mengukur baik dan mencoba menjalankan program tertentu.
Ini disebut structs1, masukkan.
Biarkan aku pergi ke depan dan menjalankan structs1, 123, David Mather,
456, Rob Kirkland, 789,
Tommy Mather, dan kita melihat David di Mather, Tommy di Mather.
Ini hanya cek kewarasan sedikit bahwa program ini bekerja.
Sekarang, sayangnya, program ini adalah sedikit frustrasi dalam
Saya melakukan semua pekerjaan itu, saya mengetik 9 string yang berbeda, tekan enter,
diberitahu yang berada di Mather, namun jelas saya tahu yang berada di Mather sudah karena saya mengetik itu.
Ini akan setidaknya baik jika program ini adalah lebih seperti database
dan itu benar-benar ingat apa yang saya telah mengetik
jadi saya tidak lagi harus memasukkan catatan siswa.
Mungkin seperti sistem registrarial.
>> Kita bisa melakukan ini dengan menggunakan teknik ini dikenal sebagai file I / O, file input dan output,
cara yang sangat generik mengatakan setiap kali Anda ingin membaca file atau menulis file
Anda dapat melakukan ini dengan satu set tertentu dari fungsi.
Biarkan aku pergi ke depan dan membuka structs2.c contoh,
yang hampir sama, tapi mari kita lihat apa yang dilakukannya sekarang.
Pada bagian atas file saya menyatakan kelas siswa.
Saya kemudian mengisi kelas dengan input pengguna,
sehingga mereka baris kode yang persis seperti sebelumnya.
Lalu jika saya scroll ke bawah di sini saya mencetak semua orang yang ada di Mather sewenang-wenang seperti sebelumnya,
tapi ini adalah fitur baru yang menarik.
Ini baris kode yang baru, dan mereka memperkenalkan sesuatu di sini,
FILE, semua topi, dan memiliki * di sini juga.
Biarkan saya bergerak ini di sini, * di atas sini juga.
>> Fungsi ini kita belum melihat sebelumnya, fopen,
tapi itu berarti file yang terbuka, jadi mari kita skim melalui,
dan ini adalah sesuatu yang kita akan kembali ke dalam psets masa depan,
namun baris ini di sini pada dasarnya membuka sebuah file yang bernama database,
dan secara khusus membuka sedemikian rupa sehingga dapat melakukan apa untuk itu?
[Tak terdengar-murid]
Benar, jadi "w" hanya berarti itu mengatakan sistem operasi
buka file ini sedemikian rupa sehingga saya bisa menulis untuk itu.
Saya tidak ingin membacanya. Saya tidak ingin hanya melihat itu.
Saya ingin mengubah dan menambahkan hal-hal yang berpotensi untuk itu,
dan file tersebut akan disebut database.
Ini bisa disebut apa-apa.
Ini bisa menjadi database.txt. Ini bisa jadi. Db.
Ini bisa menjadi kata seperti foo, tapi saya sewenang-wenang memilih untuk nama file database.
Ini adalah cek kewarasan kecil yang kita akan kembali ke dalam rinci dari waktu ke waktu,
jika fp, untuk pointer file, tidak NULL sama yang berarti semuanya baik-baik.
>> Singkat cerita, fungsi seperti fopen kadang-kadang gagal.
Mungkin file tidak ada. Mungkin Anda keluar dari ruang disk.
Mungkin Anda tidak memiliki izin untuk folder itu,
jadi jika fopen kembali sesuatu yang buruk terjadi nol.
Sebaliknya, jika fopen tidak kembali nol semua baik
dan saya bisa mulai menulis ke file ini.
Berikut ini adalah trik baru.
Ini adalah sebuah loop untuk iterasi yang masing-masing mahasiswa saya,
dan ini terlihat sangat mirip dengan apa yang kami lakukan sebelumnya,
namun fungsi ini adalah sepupu dari printf disebut fprintf untuk file printf,
dan perhatikan itu berbeda hanya dalam 2 cara.
Satu, itu dimulai dengan f bukan p,
tapi kemudian argumen pertama ternyata apa?
[Siswa] file. >> Ini file.
Hal ini disebut fp, yang pada akhirnya kita akan menggoda selain apa pointer file,
tapi untuk saat ini fp hanya merupakan file yang saya telah dibuka,
sehingga fprintf sini mengatakan cetak ID pengguna ini ke file, bukan ke layar.
Cetak nama pengguna ke file, bukan ke layar,
rumah ke file tersebut, bukan ke layar, dan kemudian turun di sini, jelas,
menutup file, dan kemudian turun di sini gratis memori.
>> Satu-satunya perbedaan antara versi 2 dan versi 1
adalah pengenalan fopen dan ini FILE dengan *
dan ini gagasan fprintf, jadi mari kita lihat apa hasil akhirnya adalah.
Biarkan aku pergi ke jendela terminal saya.
Biarkan saya jalankan structs2, masukkan.
Sepertinya semuanya baik-baik. Mari kita jalankan kembali structs2.
123, David Mather, 456, Rob Kirkland,
789, Tommy Mather, masukkan.
Tampak seperti itu berperilaku sama, tetapi jika aku lakukan sekarang ls
perhatikan apa file di sini antara semua kode saya, database,
jadi mari kita buka, gedit database, dan melihat itu.
Ini bukan terseksi dari format file.
Ini benar-benar adalah salah satu bagian dari baris data per baris per baris,
namun anda yang menggunakan file Excel atau CSV, nilai terpisah koma,
Aku pasti bisa menggunakan fprintf untuk bukan mungkin melakukan sesuatu seperti ini
sehingga saya benar-benar bisa menciptakan setara dari file Excel
dengan memisahkan hal-hal dengan koma, bukan hanya baris baru.
>> Dalam hal ini jika aku malah digunakan koma bukan baris baru
Aku benar-benar bisa membuka file database di Excel jika saya bukan membuatnya terlihat seperti ini.
Singkatnya, sekarang bahwa kita memiliki kekuatan untuk menulis ke file
sekarang kita dapat mulai data yang bertahan, menjaga di sekitar pada disk
sehingga kita dapat menyimpan informasi sekitar lagi dan lagi.
Perhatikan beberapa hal lain yang sekarang sedikit lebih akrab.
Pada bagian atas file ini C kita memiliki typedef
karena kami ingin menciptakan sebuah tipe data yang mewakili kata,
sehingga jenis ini disebut kata, dan dalam struktur ini
itu sedikit lebih menarik sekarang.
Mengapa kata terdiri dari tampaknya array?
Apa kata hanya intuitif?
>> Ini adalah array karakter.
Ini adalah urutan karakter kembali ke belakang ke belakang.
SURAT dalam semua topi kebetulan kita sewenang-wenang mengatakan panjang maksimum
dari setiap kata dalam kamus yang kita gunakan untuk Scramble.
Mengapa saya memiliki +1?
Karakter null.
Ingatlah ketika kita melakukan contoh Bananagrams kami membutuhkan nilai khusus
pada akhir kata untuk melacak
dari mana kata-kata benar-benar berakhir, dan sebagai spesifikasi sejumlah masalah mengatakan
di sini kita bergaul dengan kata yang diberikan nilai boolean,
bendera, sehingga untuk berbicara, benar atau salah.
Apakah Anda menemukan kata ini sudah, karena kami menyadari
kita benar-benar membutuhkan cara mengingat tidak hanya apa kata dalam Scramble
tapi apakah atau tidak Anda, manusia, telah menemukan itu
sehingga jika Anda menemukan kata "yang" Anda tidak bisa hanya mengetik, masuk,, masuk,, masukkan
dan mendapatkan 3 poin, 3 poin, 3 poin, 3 poin.
Kami ingin bisa di blacklist kata itu dengan menetapkan bool
true jika Anda sudah menemukannya, dan jadi itu sebabnya kita
dikemas dalam struktur ini.
>> Sekarang, di sini di Scramble ada ini struct lain yang disebut kamus.
Absen di sini adalah kata typedef karena dalam kasus ini
kami perlu untuk merangkum gagasan kamus,
dan kamus berisi sejumlah kata-kata,
seperti yang tersirat oleh array ini, dan berapa banyak dari kata-kata yang ada?
Nah, apa pun ukuran ini disebut variabel kata.
Tapi kami hanya perlu satu kamus.
Kita tidak membutuhkan tipe data yang disebut kamus.
Kita hanya perlu salah satu dari mereka, jadi ternyata di C
bahwa jika Anda tidak mengatakan typedef, Anda hanya mengatakan struct, kemudian di dalam kurung kurawal
Anda menempatkan variabel Anda, maka Anda menempatkan nama.
Hal ini menyatakan salah satu variabel yang disebut kamus
yang terlihat seperti ini.
Sebaliknya, garis-garis ini menciptakan struktur data dapat digunakan kembali disebut kata
bahwa Anda dapat membuat beberapa salinan, seperti yang kita buat
beberapa salinan siswa.
>> Apa artinya ini pada akhirnya memungkinkan kita untuk melakukan?
Biarkan aku pergi kembali ke, katakanlah, contoh sederhana dari zaman sederhana,
dan biarkan aku membuka, katakanlah, compare1.c.
Masalahnya di sini di tangan adalah untuk benar-benar mengupas
lapisan string dan mulai melepas roda pelatihan ini
karena ternyata string sepanjang waktu ini
adalah seperti yang kita dijanjikan dalam minggu 1 benar-benar hanya nama panggilan,
sinonim dari perpustakaan CS50 untuk sesuatu yang terlihat sedikit lebih samar,
char *, dan kita telah melihat bintang ini sebelumnya.
Kami melihatnya dalam konteks file.
>> Mari kita sekarang melihat mengapa kita telah menyembunyikan detail ini untuk beberapa waktu sekarang.
Berikut ini adalah sebuah file yang bernama compare1.c,
dan itu tampaknya meminta pengguna untuk 2 string, s dan t,
dan kemudian mencoba untuk membandingkan string untuk kesetaraan di baris 26,
dan jika mereka sama dikatakan, "Anda mengetik hal yang sama,"
dan jika mereka tidak sama dikatakan, "Anda mengetik hal yang berbeda."
Biarkan aku pergi ke depan dan menjalankan program ini.
Biarkan aku pergi ke direktori sumber saya, membuat compare1 a. Dikompilasi oke.
Biarkan saya menjalankan compare1.
Saya akan memperbesar, masukkan.
Katakan sesuatu. HELLO.
Aku akan mengatakan sesuatu lagi. HELLO.
Saya pasti tidak mengetik hal yang berbeda.
>> Mari saya coba ini lagi. BYE BYE.
Jelas tidak berbeda, jadi apa yang terjadi di sini?
Nah, apa yang sebenarnya sedang dibandingkan di baris 26?
[Tak terdengar-murid]
Ya, jadi ternyata string, tipe data, adalah jenis kebohongan putih.
Sebuah string adalah char *, tapi apa adalah char *?
Sebuah char *, seperti yang mereka katakan, adalah pointer,
dan pointer secara efektif alamat,
lokasi sum dalam memori, dan jika Anda kebetulan telah mengetik kata seperti HELLO,
ingat dari diskusi masa lalu string
ini seperti kata HELLO.
Ingatlah bahwa kata seperti HELLO dapat direpresentasikan
sebagai array dari karakter seperti ini
dan kemudian dengan karakter khusus pada akhirnya disebut karakter null,
sebagai menandakan \.
Apa yang sebenarnya string?
Perhatikan bahwa ini adalah beberapa bagian dari memori,
dan pada kenyataannya, akhir itu hanya dikenal setelah Anda melihat melalui seluruh string
mencari karakter null khusus.
Tapi jika ini adalah sepotong memori dari memori komputer saya,
mari kita sewenang-wenang mengatakan bahwa string ini hanya beruntung,
dan itu bisa ditempatkan di awal RAM komputer saya.
Ini adalah byte 0, 1, 2, 3, 4, 5, 6 ...
>> Ketika saya mengatakan sesuatu seperti GetString dan saya lakukan string s = GetString
apa yang sebenarnya dikembalikan?
Untuk beberapa minggu terakhir, apa yang sebenarnya disimpan di s
bukan string per se, tetapi dalam kasus ini apa yang disimpan adalah
angka 0 karena apa sebenarnya GetString
yang tidak secara fisik kembali string.
Itu bahkan tidak benar-benar masuk akal konseptual.
Apa yang kembali adalah nomor.
Angka itu adalah alamat dari HELLO di memori,
dan string s kemudian, jika kita mengupas lapisan ini, string tidak benar-benar ada.
Ini hanya penyederhanaan dalam perpustakaan CS50.
>> Ini benar-benar adalah sesuatu yang disebut * char.
Char masuk akal karena apa kata, seperti HALO?
Nah, itu adalah serangkaian karakter, serangkaian karakter.
* Char berarti alamat karakter,
jadi apa artinya untuk mengembalikan string?
A, baik cara sederhana untuk kembali string
ini daripada mencoba untuk mencari tahu bagaimana saya kembali ke 5 atau 6 byte yang berbeda
biarkan aku kembali ke alamat yang byte?
Yang pertama.
Dengan kata lain, izinkan saya memberi Anda alamat sebuah karakter dalam memori.
Itulah yang char * mewakili, alamat satu karakter tunggal dalam memori.
Menyebut bahwa variabel s.
Store di s alamat tertentu, yang saya katakan adalah sewenang-wenang 0,
hanya untuk menjaga hal-hal sederhana, tetapi dalam kenyataannya itu umumnya jumlah yang lebih besar.
>> Tunggu sebentar.
Jika Anda hanya memberi saya alamat karakter pertama, bagaimana saya tahu apa alamat itu
dari karakter kedua, ketiga, keempat dan kelima?
[Tak terdengar-murid]
Anda hanya tahu di mana akhir dari string adalah dengan cara ini trik praktis,
jadi ketika Anda menggunakan sesuatu seperti printf, apa printf harfiah mengambil sebagai argumen,
ingat bahwa kita menggunakan placeholder ini% s, dan kemudian Anda lulus dalam
variabel yang menyimpan string.
Apa yang Anda benar-benar melewati adalah alamat dari karakter pertama dari string itu.
Printf kemudian menggunakan untuk loop atau loop sementara setelah menerima alamat tersebut,
Misalnya, 0, jadi biarkan aku melakukan ini sekarang,
printf ("% s \ n," s);
Ketika saya sebut printf ("% s \ n," s), apa yang saya benar-benar memberikan printf dengan
adalah alamat dari karakter pertama dalam s, yang dalam hal ini adalah sewenang-wenang H.
>> Bagaimana printf tahu persis apa yang akan ditampilkan pada layar?
Orang yang diimplementasikan printf menerapkan loop sementara atau untuk loop
yang mengatakan tidak karakter ini sama dengan karakter null khusus?
Jika tidak, mencetaknya. Bagaimana dengan yang satu ini?
Jika tidak mencetaknya, mencetaknya, mencetaknya, mencetaknya.
Oh, yang satu ini khusus. Berhenti mencetak dan kembali ke pengguna.
Dan itu benar-benar semua yang telah terjadi di bawah tenda,
dan itu banyak untuk mencerna di hari pertama kelas,
tapi untuk saat itu benar-benar blok bangunan dari segala pemahaman
yang telah terjadi di dalam memori komputer kita,
dan akhirnya kita akan menggoda ini terpisah dengan sedikit bantuan
dari salah satu teman-teman kita di Stanford.
>> Profesor Nick Parlante di Stanford telah melakukan ini urutan video indah
dari segala macam bahasa yang berbeda yang diperkenalkan
Binky ini sedikit karakter Claymation.
Suara Anda akan mendengar hanya dalam sneak preview beberapa detik
adalah bahwa seorang profesor dari Stanford, dan Anda mendapatkan
hanya 5 atau 6 detik dari sekarang ini,
tapi ini adalah catatan di mana kita akan menyimpulkan hari
dan dimulai pada hari Rabu.
Saya memberikan Fun Pointer dengan Binky, pratinjau.
[♪ ♪ Musik] [Profesor Parlante] Hei, Binky.
Bangun. Sudah waktunya untuk bersenang-senang pointer.
[Binky] Apa itu? Pelajari tentang pointer?
Oh, goody!
>> Kami akan melihat Anda pada hari Rabu.
[CS50.TV]