[Powered by Google Translate] [Review] [Kuiz 0]
>> [Lexi Ross, Tommy MacWilliam, Lucas Freitas, Joseph Ong] [Universiti Harvard]
>> [Ini adalah CS50.] [CS50.TV]
>> Hei, semua.
Selamat datang ke sesi kajian untuk Kuiz 0, yang sedang berlaku hari Rabu ini.
Apa yang kita akan lakukan malam, saya dengan 3 TFS lain,
dan bersama-sama kita akan pergi melalui kajian apa yang kami lakukan dalam kursus setakat ini.
Ia tidak akan menjadi 100% menyeluruh, tetapi ia harus memberi anda idea yang lebih baik
apa yang anda sudah mempunyai dan apa yang anda masih perlu belajar sebelum Rabu.
Dan berasa bebas untuk mengangkat tangan anda dengan soalan-soalan seperti yang kita pergi bersama-sama,
tetapi perlu diingat bahawa kita juga akan mempunyai sedikit masa di akhir-
jika kita dapat melalui dengan beberapa minit untuk ganti-untuk melakukan soalan umum,
supaya menyimpan bahawa dalam fikiran, dan sebagainya kita akan bermula pada awal dengan 0 Minggu.
>> [Kuiz 0 Kajian!] [Bahagian 0] [Lexi Ross] Tetapi sebelum kita lakukan yang membolehkan bercakap tentang
logistik kuiz.
>> [Logistics] [Kuiz berlaku pada hari Rabu 10/10 sebagai ganti kuliah]
>> [(Lihat http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf untuk mendapatkan butiran)] Ia adalah pada Wednesday, October 10th.
>> Itulah hari Rabu ini, dan jika anda pergi ke URL ini di sini,
yang juga boleh diakses dari pautan ke CS50.net-ada 's-
anda boleh melihat maklumat tentang di mana untuk pergi berdasarkan
nama akhir anda atau gabungan sekolah serta
ia menceritakan tentang apa kuiz akan meliputi dan jenis soalan yang anda akan mendapat.
Perlu diingat bahawa anda juga akan mempunyai peluang untuk mengkaji semula untuk kuiz dalam seksyen,
jadi TFS anda perlu pergi ke atas beberapa masalah amalan,
dan itulah satu lagi peluang yang baik untuk melihat di mana anda masih perlu belajar untuk kuiz.
Mari kita mulakan pada awal dengan Bytes 'n' Bit.
Ingat sedikit adalah hanya 0 atau 1,
dan satu bait adalah koleksi 8 bit-bit.
Mari kita lihat di koleksi ini bit yang betul di sini.
Kita harus dapat mengetahui berapa banyak bit yang terdapat.
Jika kita mengira terdapat hanya 8 daripada mereka, lapan 0 atau 1 unit.
Dan sejak ada 8 bit, itulah 1 bait,
dan mari kita menukar kepada perenambelasan.
Perenambelasan adalah asas 16, dan ia adalah agak mudah untuk menukar
nombor perduaan, yang adalah apa yang, untuk beberapa dalam perenambelasan.
Apa yang kita lakukan ialah kita melihat kumpulan 4,
dan kita menukar mereka untuk digit perenambelasan yang sesuai.
Kita mulakan dengan kumpulan paling kanan 4, jadi 0011.
Itu akan menjadi satu 1 dan satu 2, jadi bersama-sama yang membuat 3.
Dan kemudian mari kita melihat blok lain 4.
1101. Itu akan menjadi satu 1, satu 4, dan satu 8.
Bersama yang akan menjadi 13, yang menjadikan D.
Dan kita akan ingat bahawa dalam perenambelasan kita tidak hanya pergi 0 hingga 9.
Kami pergi 0 melalui F, jadi selepas 9, 10 bersamaan kepada A,
11 kepada B, dan sebagainya di mana F adalah 15.
Berikut 13 ialah D,
jadi untuk menukar ia kepada perpuluhan semua yang kita lakukan adalah kita sebenarnya
merawat setiap kedudukan sebagai kuasa 2.
Itulah satu 1, satu 2, sifar 4s, sifar 8s, satu 16, dan sebagainya,
dan ia sedikit sukar untuk mengira dalam kepala anda, tetapi jika kita pergi ke slaid seterusnya
kita boleh lihat jawapan itu.
>> Pada dasarnya kita akan merentasi dari kanan kembali ke kiri,
dan kita mendarabkan setiap angka dengan kuasa yang sama 2.
Dan ingat, perenambelasan kita menandakan nombor-nombor ini dengan 0x pada permulaan
supaya kita tidak mengelirukan ia dengan nombor perpuluhan.
Berterusan ke atas, ini adalah Jadual ASCII,
dan apa yang kita gunakan ASCII bagi adalah untuk memetakan dari watak-watak kepada nilai-nilai berangka.
Ingat dalam pset kriptografi kita membuat penggunaan meluas Jadual ASCII
dalam usaha untuk menggunakan pelbagai kaedah kriptografi,
Caesar dan cipher Vigenère, untuk menukar huruf yang berbeza
dalam rentetan mengikut kunci yang diberikan oleh pengguna.
Mari kita melihat sedikit matematik ASCII.
Melihat 'P' + 1, dalam bentuk watak yang akan menjadi Q,
dan ingat bahawa ''5 ≠ 5.
Dan bagaimana sebenarnya kita akan menukar antara 2 bentuk mereka?
Ia sebenarnya tidak terlalu keras.
Dalam usaha untuk mendapatkan 5 kita tolak '0 '
kerana terdapat 5 tempat antara '0 'dan '5'.
Dalam usaha untuk pergi cara lain kita hanya menambah 0,,
jadi ia adalah jenis seperti aritmetik tetap.
Hanya ingat bahawa apabila sesuatu mempunyai petikan sekelilingnya ia adalah watak
dan dengan itu sepadan dengan nilai dalam jadual ASCII.
Melangkah ke topik sains komputer yang lebih umum.
Kami belajar apa algoritma dan bagaimana kita menggunakan pengaturcaraan
untuk melaksanakan algoritma.
Beberapa contoh algoritma adalah sesuatu yang benar-benar mudah seperti
memeriksa sama ada nombor adalah genap atau ganjil.
Untuk itu ingat kita MOD nombor dengan 2 dan memeriksa jika hasilnya adalah 0.
Jika ya, ia adalah lebih. Jika tidak, ia adalah ganjil.
Dan itulah satu contoh algoritma yang benar-benar asas.
>> Sedikit lebih terlibat adalah carian binari,
yang kita akan pergi lebih lewat dalam sesi kajian.
Dan pengaturcaraan adalah istilah yang kita gunakan untuk mengambil algoritma
dan menukar kod komputer boleh membaca.
2 contoh pengaturcaraan Scratch,
yang adalah apa yang kita lakukan di titik 0 Minggu.
Walaupun kita tidak sebenarnya menaip kod, ia adalah satu cara melaksanakan
ini algoritma, yang mencetak nombor 1-10,
dan di sini kita melakukan perkara yang sama dalam bahasa pengaturcaraan C.
Ini adalah fungsi setara, hanya ditulis dalam bahasa yang berbeza atau sintaks.
Kami kemudian belajar tentang ungkapan boolean,
dan boolean adalah nilai yang sama ada benar atau palsu,
dan ungkapan di sini sering kali boolean
pergi di dalam keadaan, jadi jika (x ≤ 5),
baik, kita sudah ditetapkan x = 5, jadi keadaan yang akan menilai kepada true.
Dan jika ia benar, apa-apa kod di bawah keadaan
akan dinilai oleh komputer, jadi rentetan yang akan dicetak
output standard, dan istilah keadaan
merujuk kepada apa yang ada di dalam kurungan kenyataan jika.
Ingat semua operator.
Ingat && dan | | apabila kita sedang berusaha untuk menggabungkan 2 atau lebih keadaan,
== Tidak = untuk memeriksa sama ada 2 perkara adalah sama.
Ingatlah bahawa = adalah untuk tugasan sedangkan == operator boolean.
≤, ≥ dan kemudian 2 akhir adalah jelas dengan sendirinya.
Satu kajian umum logik boolean di sini.
Dan ungkapan boolean juga penting dalam gelung,
yang kita akan pergi lebih sekarang.
Kami belajar tentang 3 jenis gelung setakat pada CS50,, manakala, dan lakukan semasa.
Dan ia adalah penting untuk mengetahui bahawa manakala bagi kebanyakan tujuan
kita sebenarnya boleh menggunakan apa-apa jenis gelung umumnya
terdapat jenis tertentu tujuan atau corak biasa
dalam pengaturcaraan yang khusus memanggil satu ini gelung
yang menjadikan ia paling berkesan atau elegan untuk kod dengan cara itu.
Mari kita pergi ke setiap apa-gelung cenderung untuk digunakan bagi paling sering.
>> Dalam gelung untuk kita umumnya sudah tahu berapa kali kita mahu melelar.
Itulah apa yang kita masukkan ke dalam keadaan.
Kerana, i = 0, i <10, sebagai contoh.
Kita sudah tahu bahawa kita mahu melakukan sesuatu yang 10 kali.
Sekarang, bagi gelung sementara, umumnya kita tidak semestinya
tahu berapa kali kita mahu gelung untuk menjalankan.
Tetapi kita tahu beberapa jenis keadaan yang kita mahu ia
sentiasa menjadi benar atau sentiasa menjadi palsu.
Sebagai contoh, semasa ditetapkan.
Mari kita mengatakan bahawa adalah satu pemboleh ubah boolean.
Walaupun yang benar kita mahu kod untuk menilai,
jadi sedikit lebih extensible, sedikit lebih umum daripada gelung,
tetapi apa-apa untuk gelung juga boleh ditukar kepada gelung sementara.
Akhirnya, lakukan manakala gelung, yang mungkin menjadi trickiest untuk memahami merta,
sering digunakan apabila kita mahu menilai kod yang pertama
sebelum kali pertama kita memeriksa keadaan.
Satu kes biasa digunakan untuk buat gelung while
apabila anda mahu untuk mendapatkan input pengguna, dan anda tahu anda mahu untuk meminta pengguna
untuk input sekurang-kurangnya sekali, tetapi jika mereka tidak memberi anda input yang baik segera
anda mahu menyimpan meminta mereka sehingga mereka memberi anda input yang baik.
Itulah penggunaan yang paling biasa melakukan gelung while,
dan mari kita melihat struktur sebenar ini gelung.
Mereka biasanya sentiasa cenderung untuk mengikuti pola-pola ini.
>> Pada gelung untuk bahagian anda mempunyai 3 komponen:
pengawalan, biasanya sesuatu seperti int i = 0 mana i ialah kaunter,
keadaan, di mana kita mahu mengatakan menjalankan ini untuk gelung sebagai selagi keadaan ini masih memegang,
seperti i <10, dan kemudian akhirnya, update, yang adalah bagaimana kita kenaikan
pembolehubah kaunter di setiap titik di dalam gelung.
Satu perkara biasa untuk melihat di sana hanya i + +,
yang bermaksud kenaikan i sebanyak 1 setiap masa.
Anda juga boleh melakukan sesuatu seperti i + = 2,
yang bermaksud tambahkan 2 kepada i setiap kali anda pergi melalui gelung.
Dan kemudian melakukan ini hanya merujuk kepada mana-mana kod yang sebenarnya berjalan sebagai sebahagian daripada gelung.
Dan untuk gelung sementara, masa ini kita sebenarnya mempunyai pengawalan luar gelung,
demikian bagi contoh, katakan kita sedang berusaha untuk melakukan jenis yang sama gelung kerana saya hanya diterangkan.
Kita akan mengatakan int i = 0 sebelum gelung bermula.
Kemudian kita boleh mengatakan manakala i <10 melakukan ini,
jadi blok sama kod seperti sebelum ini,
dan masa ini bahagian mengemaskini kod, contohnya, i + +,
sebenarnya berlaku di dalam gelung.
Dan akhirnya, untuk lakukan semasa, ia adalah serupa dengan gelung sementara,
tetapi kita perlu ingat bahawa kod akan menilai sekali
sebelum keadaan diperiksa, jadi ia masuk akal yang lebih banyak
jika anda melihat di perintah atas ke bawah.
Dalam, lakukan manakala gelung kod menilai sebelum anda melihat keadaan sementara
manakala gelung sementara, ia cek pertama.
Penyata dan pembolehubah.
Apabila kita hendak mewujudkan satu pembolehubah baru kita mahu untuk memulakan ia.
>> Sebagai contoh, bar int initializes bar berubah-ubah,
tetapi ia tidak memberikan nilai, jadi apakah nilai bar sekarang?
Kita tidak tahu.
Ia boleh menjadi beberapa nilai sampah yang sebelum ini disimpan di dalam memori di sana,
dan kita tidak mahu menggunakan pembolehubah yang
sehingga kita benar-benar memberi nilai,
jadi kita mengisytiharkan ia di sini.
Kemudian kami memulakan ia menjadi 42 bawah.
Kini, sudah tentu, kita tahu ini boleh dilakukan dalam satu baris, int bar = 42.
Tetapi hanya untuk membersihkan pelbagai langkah-langkah yang sedang berlaku,
pengisytiharan dan pengawalan yang berlaku secara berasingan di sini.
Ia berlaku pada satu langkah, dan satu depan, int Baz = bar + 1,
kenyataan ini di bawah, bahawa Baz kenaikan, jadi pada akhir blok kod ini
jika kita adalah untuk mencetak nilai Baz ia akan menjadi 44
kerana kita mengaku dan memulakan ia menjadi 1> bar,
dan kemudian kita kenaikan sekali lagi dengan + +.
Kami pergi ke sebentar cantik ini, tetapi ia adalah baik untuk mempunyai umum
memahami apa benang dan acara.
Kami melakukan ini terutamanya dalam Gores,
supaya anda boleh berfikir benang sebagai urutan pelbagai kod
berjalan pada masa yang sama.
Dalam kenyataannya, ia mungkin tidak berjalan pada masa yang sama,
tetapi jenis abstrak kita boleh berfikir ia dengan cara itu.
>> Di Awal, sebagai contoh, kita mempunyai sprites berganda.
Ia boleh melaksanakan kod yang berbeza pada masa yang sama.
Satu boleh berjalan manakala yang lain mengatakan sesuatu
dalam bahagian yang berbeza skrin.
Peristiwa adalah satu lagi cara yang memisahkan logik
antara unsur-unsur yang berlainan kod anda,
dan dalam Gores kita mampu untuk mensimulasikan peristiwa menggunakan Penyiaran,
dan itulah sebenarnya Apabila Saya Menerima, tidak Apabila saya Dengar,
tetapi pada dasarnya ia adalah satu cara untuk menghantar maklumat
dari satu bidadari yang lain.
Sebagai contoh, anda mungkin mahu untuk menghantar permainan lebih,
dan apabila bidadari lain menerima permainan lebih,
ia bertindak balas dengan cara yang tertentu.
Ia adalah satu model yang penting untuk memahami untuk pengaturcaraan.
Hanya untuk pergi ke Minggu asas 0, apa yang kita telah pergi setakat ini,
mari kita melihat program ini mudah C.
Teks ini mungkin sedikit kecil dari sini, tetapi saya akan pergi ke ia benar-benar cepat.
Kami termasuk 2 fail header di atas, cs50.h dan stdio.h.
Kami kemudian menentukan had berterusan dipanggil untuk menjadi 100.
Kami kemudian melaksanakan fungsi utama kami.
Oleh kerana kita tidak menggunakan hujah baris arahan di sini, kita perlu meletakkan sah
sebagai hujah untuk utama.
Kita lihat int utama di atas. Itulah jenis pulangan, maka kembali 0 di bawah.
Dan kita menggunakan CS50 perpustakaan fungsi mendapatkan int
untuk meminta pengguna untuk input, dan kita menyimpannya dalam x ini berubah-ubah,
jadi kita mengisytiharkan x di atas, dan kami memulakan dengan x = GetInt.
>> Kami kemudian memeriksa untuk melihat jika pengguna memberikan kita input yang baik.
Jika ia HAD ≥ kita mahu untuk kembali kod ralat 1 dan mencetak mesej ralat.
Dan akhirnya, jika pengguna telah memberikan kita input yang baik
kita akan persegi nombor dan mencetak hasil itu.
Hanya untuk memastikan bahawa orang-orang rumah melanda semua
anda boleh melihat label bahagian yang berlainan kod di sini.
Saya sebutkan berterusan, fail header.
Oh, int x. Pastikan untuk ingat bahawa pembolehubah tempatan.
Itu berbeza dari pembolehubah global, yang kita akan bercakap tentang
sedikit kemudian dalam sesi kajian,
dan kita memanggil fungsi perpustakaan printf,
jadi jika kita tidak dimasukkan fail header stdio.h
kita tidak akan mampu untuk memanggil printf.
Dan saya percaya anak panah yang mendapat terputus sini menunjuk ke% d,
yang merupakan rentetan format dalam printf.
Ia mengatakan mencetak pembolehubah ini sebagai nombor,% d.
Dan bahawa ia adalah untuk 0 Minggu.
Sekarang Lucas akan terus.
Hey, guys. Nama saya ialah Lucas.
Saya seorang mahasiswa tingkat kedua di rumah terbaik di kampus, Mather,
dan saya akan bercakap sedikit tentang Minggu 1 dan 2.1.
[Minggu 1 dan 2.1!] [Lucas Freitas]
Sebagai Lexi telah berkata, apabila kita mula menterjemahkan kod anda dari Gores kepada C
salah satu perkara yang kita perhatikan adalah bahawa anda tidak boleh hanya
menulis kod anda dan jalankan ia menggunakan bendera hijau lagi.
Sebenarnya, anda perlu menggunakan beberapa langkah-langkah untuk membuat aturcara C anda
menjadi fail boleh laku.
Pada asasnya apa yang anda lakukan apabila anda sedang menulis program adalah bahawa
anda menterjemahkan idea anda ke dalam bahasa yang pengkompil boleh memahami,
jadi apabila anda menulis program dalam C
apa yang anda lakukan sebenarnya menulis sesuatu yang pengkompil anda akan memahami,
dan kemudian pengkompil akan menterjemahkan kod yang
ke dalam sesuatu yang komputer anda akan memahami.
>> Dan perkara, komputer anda sebenarnya sangat bodoh.
Komputer anda hanya boleh memahami 0 dan 1s,
begitu sebenarnya dalam komputer pertama orang biasanya diprogramkan
menggunakan 0 dan 1s, tetapi tidak lagi, terima Allah.
Kita tidak perlu menghafal urutan 0 dan 1s
untuk bagi gelung atau untuk gelung sementara dan sebagainya.
Itulah sebabnya kita mempunyai pengkompil.
Apa pengkompil tidak adalah ia pada asasnya menterjemahkan kod C,
dalam kes ini, kepada bahasa yang komputer anda akan faham,
yang merupakan kod objek, dan pengkompil yang kita gunakan
dipanggil dilafaz, jadi ini adalah sebenarnya simbol untuk dilafaz.
Apabila anda mempunyai program anda, anda perlu melakukan 2 perkara.
Pertama, anda perlu untuk menyusun program anda, dan kemudian anda pergi untuk menjalankan program anda.
Untuk menyusun program anda, anda mempunyai banyak pilihan untuk berbuat demikian.
Yang pertama adalah untuk melakukan program.c dilafaz
di mana program adalah nama program anda.
Dalam kes ini, anda boleh melihat mereka hanya berkata "Hei, menyusun program saya."
Anda tidak mengatakan "Saya mahu ini nama untuk program saya" atau apa-apa.
>> Pilihan kedua memberi nama untuk program anda.
Anda boleh mengatakan dilafaz-o dan kemudian nama yang anda mahu
fail boleh laku yang akan dinamakan dan kemudian program.c.
Dan anda juga boleh lakukan membuat program, dan melihat bagaimana dalam 2 kes pertama
Saya meletakkan c, dan dalam salah satu ketiga saya hanya mempunyai program?
Ya, anda sebenarnya tidak perlu meletakkan c apabila anda menggunakan membuat.
Jika tidak, pengkompil sebenarnya akan menjerit pada anda.
Dan juga, saya tidak tahu jika anda semua ingat,
tetapi banyak kali kita juga digunakan lcs50 atau lm.
Yang dipanggil menghubungkan.
Ia hanya memberitahu pengkompil bahawa anda akan menggunakan perpustakaan mereka di sana,
jadi jika anda mahu menggunakan cs50.h anda sebenarnya perlu menaip
program.c dilafaz-lcs50.
Jika anda tidak berbuat demikian, pengkompil tidak akan tahu
bahawa anda menggunakan fungsi-fungsi dalam cs50.h.
Dan apabila anda mahu untuk menjalankan program anda, anda mempunyai 2 pilihan.
Jika anda lakukan program.c dilafaz anda tidak memberi nama untuk program anda.
Anda perlu untuk menjalankan ia menggunakan / a.out.
A.out adalah nama standard yang dilafaz memberikan program anda jika anda tidak memberikan nama.
Jika tidak, anda akan lakukan. / Program jika anda memberikan nama untuk program anda,
dan juga jika anda tidak membuat program nama program akan mendapat
sudah akan diprogramkan nama yang sama seperti fail c.
Kemudian kita bercakap tentang jenis data dan data.
>> Pada asasnya jenis data adalah perkara yang sama seperti kotak kecil yang mereka gunakan
untuk menyimpan nilai, jadi jenis data adalah sebenarnya seperti Pokémons.
Mereka datang dalam pelbagai saiz dan jenis.
Saya tidak tahu jika analogi yang masuk akal.
Saiz data sebenarnya bergantung pada seni bina mesin.
Semua data saiz yang saya akan menunjukkan di sini
sebenarnya untuk mesin 32-bit, yang merupakan kes perkakas kami,
tetapi jika anda sebenarnya pengekodan Mac anda atau dalam Windows juga
mungkin anda akan mempunyai mesin 64-bit,
jadi ingat bahawa saiz data yang saya akan menunjukkan di sini
adalah untuk mesin 32-bit.
Yang pertama yang kita lihat adalah int,
yang agak mudah.
Anda menggunakan int untuk menyimpan integer.
Kami juga melihat watak, char.
Jika anda mahu menggunakan surat atau simbol sedikit anda mungkin akan menggunakan char.
Char A mempunyai 1 bait, yang bermaksud 8 bit, seperti Lexi berkata.
Pada asasnya kita mempunyai Jadual ASCII yang mempunyai 256
kemungkinan kombinasi 0 dan 1s,
dan kemudian apabila anda menaip satu char ia akan menterjemahkan
watak bahawa input anda nombor yang anda ada dalam jadual ASCII, seperti Lexi berkata.
Kami juga mempunyai apungan, yang kita gunakan untuk menyimpan nombor perpuluhan.
Jika anda ingin memilih 3,14, sebagai contoh, anda akan menggunakan apungan
atau dua yang mempunyai lebih tepat.
Apungan A mempunyai 4 bait.
Double A mempunyai 8 bait, jadi perbezaan hanya ialah ketepatan.
Kami juga mempunyai panjang yang digunakan untuk integer,
dan anda boleh melihat untuk mesin 32-bit int dan lama mempunyai saiz yang sama,
jadi ia tidak benar-benar masuk akal untuk menggunakan lama dalam mesin 32-bit.
>> Tetapi jika anda menggunakan mesin Mac dan 64-bit, sebenarnya yang lama mempunyai saiz 8,
jadi ia benar-benar bergantung kepada seni bina.
Bagi mesin 32-bit ia tidak masuk akal untuk menggunakan panjang benar-benar.
Dan kemudian yang lama, di sisi lain, mempunyai 8 bait,
jadi ia adalah sangat baik jika anda mahu mempunyai integer lagi.
Dan akhirnya, kita mempunyai tali, yang sebenarnya * char,
yang merupakan penunjuk kepada char.
Ia amat mudah untuk berfikir bahawa saiz tali akan menjadi seperti
bilangan aksara yang anda telah ada,
tetapi sebenarnya * char sendiri
mempunyai saiz penunjuk kepada char, yang adalah 4 bait.
Saiz * char 4 bait.
Ia tidak kira jika anda mempunyai satu perkataan kecil atau surat atau apa-apa.
Ia akan menjadi 4 bait.
Kami juga belajar sedikit tentang pemutus,
jadi seperti yang anda boleh lihat, jika anda mempunyai, sebagai contoh, satu program yang mengatakan
int x = 3 dan kemudian printf ("% d", x / 2)
adakah anda semua tahu apa yang ia akan mencetak pada skrin?
>> Seseorang? >> [Pelajar] 2.
1. >> 1, yeah.
Apabila anda melakukan 3/2 ia akan mendapat 1,5,
tetapi kerana kita sedang menggunakan integer ia akan mengabaikan bahagian perpuluhan,
dan anda akan mempunyai 1.
Jika anda tidak mahu itu berlaku apa yang anda boleh lakukan, sebagai contoh,
adalah mengisytiharkan apungan y = x.
Maka x yang digunakan untuk menjadi 3 kini akan menjadi 3,000 dalam y.
Dan kemudian anda boleh mencetak y / 2.
Sebenarnya, saya harus mempunyai 2 a. di sana.
Ia akan melakukan 3.00/2.00,
dan anda akan dapat 1.5.
Dan kita mempunyai f 0,2 ini hanya untuk meminta 2 unit perpuluhan dalam bahagian perpuluhan.
Jika anda mempunyai 0,3 f ia akan sebenarnya mempunyai 1,500.
Jika ia adalah 2 ia akan menjadi 1,50.
Kami juga mempunyai kes ini di sini.
Jika anda melakukan apungan x = 3.14 dan kemudian anda x printf
anda pergi untuk mendapatkan 3,14.
Dan jika anda lakukan x = int x,
yang bermaksud merawat x sebagai int dan anda mencetak x kini
anda akan mempunyai 3,00.
Adakah yang masuk akal?
Kerana anda first merawat x sebagai integer, maka anda mengabaikan bahagian perpuluhan,
dan kemudian anda mencetak x.
Dan akhirnya, anda juga boleh melakukan ini,
int x = 65, dan kemudian anda mengisytiharkan char c = x,
dan kemudian jika anda mencetak c anda sebenarnya akan mendapat
A, jadi pada dasarnya apa yang anda lakukan di sini
menterjemahkan integer ke dalam watak,
seperti Jadual ASCII tidak.
Kami juga bercakap tentang pengendali matematik.
Kebanyakan mereka adalah agak mudah, jadi +, -, *, /,
dan juga kita bercakap tentang arena, yang merupakan baki bahagian 2 nombor.
Jika anda mempunyai 10% 3, sebagai contoh,
ia bermakna membahagikan 10 dengan 3, dan apa yang selebihnya?
Ia akan menjadi 1, jadi ia sebenarnya amat berguna untuk banyak program.
Untuk Vigenère dan Caesar Saya agak pasti bahawa semua kalian yang digunakan arena.
Mengenai operator matematik, berhati-hati apabila menggabungkan * dan /.
>> Sebagai contoh, jika anda melakukan (3/2) * 2 apa yang anda akan mendapat?
[Pelajar] 2.
Ya, 2, kerana 3/2 akan ialah 1.5,
tetapi kerana anda sedang melakukan operasi antara 2 integer
anda sebenarnya hanya akan untuk mempertimbangkan 1,
dan kemudian 1 * 2 akan menjadi 2, jadi sangat, sangat berhati-hati
apabila melakukan aritmetik dengan integer kerana
anda mungkin akan mendapat bahawa 2 = 3, dalam kes itu.
Dan juga menjadi sangat berhati-hati tentang keutamaan.
Anda biasanya perlu menggunakan kurungan untuk memastikan bahawa anda tahu apa yang anda lakukan.
Beberapa pintasan berguna, sudah tentu, seseorang itu i + + atau i + = 1
atau menggunakan + =.
Itu adalah perkara yang sama seperti melakukan i = i + 1.
Anda juga boleh melakukan i - atau i - = 1,
yang merupakan perkara yang sama seperti i = i -1,
sesuatu yang anda lelaki menggunakan banyak dalam gelung, sekurang-kurangnya.
Juga, untuk *, jika anda menggunakan * = dan jika anda lakukan, sebagai contoh,
i * = 2 adalah perkara yang sama sebagai berkata i = i * 2,
dan perkara yang sama untuk bahagian.
Jika anda lakukan i / = 2 ia adalah perkara yang sama seperti i = i / 2.
>> Sekarang tentang fungsi.
Kalian tahu bahawa fungsi adalah satu strategi yang sangat baik untuk menyelamatkan kod
semasa anda pengaturcaraan, jadi jika anda mahu untuk melaksanakan tugas yang sama.
dalam kod sekali lagi dan sekali lagi, mungkin anda mahu menggunakan fungsi
hanya jadi anda tidak perlu copy dan paste kod berulang-ulang kali.
Sebenarnya, utama adalah fungsi, dan apabila saya menunjukkan kepada anda format fungsi
anda akan melihat bahawa itu adalah cukup jelas.
Kami juga menggunakan fungsi dari beberapa perpustakaan,
sebagai contoh, printf, GetIn, yang adalah dari perpustakaan CS50,
dan fungsi lain seperti toupper.
Semua fungsi-fungsi sebenarnya dilaksanakan di perpustakaan lain,
dan apabila anda meletakkan fail-fail menambat di awal program anda
anda mengatakan anda boleh sila berikan saya kod untuk fungsi-fungsi
jadi saya tidak perlu untuk melaksanakan mereka dengan diri sendiri?
Dan anda juga boleh menulis fungsi-fungsi anda sendiri, jadi apabila anda mulakan program
anda sedar bahawa perpustakaan tidak mempunyai segala fungsi yang anda perlukan.
Untuk pset terakhir, sebagai contoh, kita menulis menarik, perebutan, dan lookup,
dan ia adalah amat penting untuk dapat untuk menulis fungsi
kerana mereka adalah berguna, dan kita menggunakannya sepanjang masa dalam pengaturcaraan,
dan ia menjimatkan banyak kod.
Format fungsi adalah salah satu ini.
Kami mempunyai jenis pulangan pada mulanya. Apakah jenis pulangan?
Ia hanya apabila fungsi anda akan kembali.
Jika anda mempunyai fungsi, sebagai contoh, faktorial,
yang akan mengira faktorial integer,
mungkin ia akan kembali integer juga.
Kemudian jenis pulangan akan menjadi int.
Printf sebenarnya mempunyai kekosongan jenis pulangan
kerana anda tidak kembali apa-apa.
Anda hanya mencetak perkara untuk skrin
dan berhenti fungsi selepas itu.
Kemudian anda mempunyai nama fungsi yang anda boleh memilih.
Anda perlu sedikit munasabah, seperti tidak memilih nama seperti xyz
atau seperti x2f.
Cuba untuk membuat nama yang masuk akal.
>> Sebagai contoh, jika ia faktorial, katakan faktorial.
Jika ia merupakan satu fungsi yang akan melukis sesuatu, namakan ia menarik.
Dan kemudian kita mempunyai parameter, yang juga dipanggil hujah,
yang adalah seperti sumber yang berfungsi anda perlu
dari kod anda untuk melaksanakan tugasnya.
Jika anda ingin mengira faktorial nombor
mungkin anda perlukan untuk memiliki nombor untuk mengira faktorial.
Salah satu hujah bahawa anda akan mempunyai bilangan itu sendiri.
Dan kemudian ia akan melakukan sesuatu dan kembali nilai pada akhir
melainkan jika ia adalah fungsi yang tidak sah.
Mari kita lihat satu contoh.
Jika saya mahu menulis fungsi yang jumlah wang semua nombor dalam pelbagai integer,
pertama sekali, jenis pulangan akan menjadi int
kerana saya mempunyai pelbagai integer.
Dan kemudian saya akan mempunyai nama yang berfungsi seperti sumArray,
dan kemudian ia akan mengambil pelbagai itu sendiri, untuk nums int,
dan kemudian panjang array jadi saya tahu berapa banyak nombor saya untuk meringkaskannya.
Kemudian saya perlu untuk memulakan sejumlah pembolehubah yang dipanggil, sebagai contoh, kepada 0,
dan setiap kali saya melihat satu elemen dalam array saya perlu menambah kepada jumlah, jadi saya lakukan untuk gelung.
Sama seperti Lexi berkata, anda lakukan int i = 0, i <panjang dan i + +.
Dan bagi setiap elemen dalam array saya lakukan jumlah + = nums [i],
dan kemudian saya kembali jumlah, jadi ia adalah sangat mudah, dan ia menjimatkan banyak kod
jika anda menggunakan fungsi ini banyak kali.
Kemudian kami mengambil melihat pada keadaan.
Kami mempunyai jika, lain, dan lain jika.
Mari kita lihat apakah perbezaan di antara mereka.
Ambil melihat ini 2 kod. Apakah perbezaan antara mereka?
Yang pertama telah pada dasarnya kod mahu anda untuk memberitahu
jika nombor adalah +, -, atau 0.
Yang pertama mengatakan jika ia> 0, maka ia adalah positif.
Jika ia = kepada 0, maka ia adalah 0, dan jika ia adalah <0, maka ia adalah negatif.
>> Dan satu lagi melakukan jika, else if, lain.
Perbezaan antara kedua-dua adalah bahawa satu ini sebenarnya akan
memeriksa jika> 0 <0 atau = 0 tiga kali,
jadi jika anda mempunyai nombor 2, sebagai contoh, ia akan datang ke sini dan mengatakan
jika (x> 0), dan ia akan berkata ya, jadi saya hendak mencetak positif.
Tetapi walaupun saya tahu bahawa ia adalah> 0 dan ia tidak akan menjadi 0 atau <0
Saya masih akan lakukan ialah 0, ia <0,
jadi saya sebenarnya berlaku di dalam IFS bahawa saya tidak perlu
kerana saya sudah tahu bahawa ia tidak akan memenuhi mana-mana syarat-syarat ini.
Saya boleh menggunakan jika, else if, else.
Ia pada dasarnya mengatakan jika x = 0 saya hendak mencetak positif.
Jika tidak, saya akan juga menguji ini.
Jika ia adalah 2 tidak saya akan melakukan ini.
Pada asasnya jika saya terpaksa x = 2 anda akan mengatakan
jika (x> 0), ya, jadi mencetak ini.
Sekarang saya tahu bahawa ia adalah> 0 dan bahawa ia berpuas pertama jika
Saya tidak akan menjalankan kod ini.
Kod berjalan lebih cepat, sebenarnya, 3 kali lebih cepat jika anda menggunakan ini.
Kami juga belajar tentang dan atau.
Saya tidak akan pergi melalui ini kerana Lexi sudah bercakap tentang mereka.
Ia hanya && dan | pengendali |.
>> Satu-satunya perkara yang saya akan katakan adalah berhati-hati apabila anda mempunyai 3 keadaan.
Gunakan kurungan kerana ia adalah sangat mengelirukan apabila anda mempunyai keadaan
dan satu lagi atau satu lagi.
Gunakan kurungan hanya untuk memastikan bahawa keadaan anda masuk akal
kerana dalam kes itu, sebagai contoh, anda boleh membayangkan bahawa
ia boleh menjadi syarat pertama dan satu atau yang lain
atau 2 syarat yang digabungkan dalam dan
atau satu pertiga, jadi berhati-hati.
Dan akhirnya, kita bercakap tentang suis.
Suis adalah sangat berguna apabila anda mempunyai pembolehubah.
Mari kita mengatakan bahawa anda mempunyai pembolehubah seperti n
yang boleh menjadi 0, 1, atau 2, dan bagi setiap kes-kes
anda akan melaksanakan tugas.
Anda boleh mengatakan menukar pembolehubah, dan ia menunjukkan bahawa
nilai itu adalah seperti nilai1 saya akan berbuat demikian,
dan kemudian saya memecahkan, yang bermakna saya tidak akan kelihatan di mana-mana kes-kes lain
kerana kita sudah berpuas hati kes itu
dan kemudian nilai2 dan sebagainya, dan saya juga boleh mempunyai suis lalai.
Ini bermakna jika ia tidak memenuhi mana-mana kes-kes yang saya telah
bahawa saya akan melakukan sesuatu yang lain, tetapi itulah pilihan.
Itu semua bagi saya. Sekarang mari kita Tommy.
Baiklah, ini akan menjadi Minggu 3-ish.
Ini adalah beberapa topik yang kita akan meliputi, kripto, skop, tatasusunan, dan sebagainya.
Hanya satu perkataan yang cepat pada kripto. Kami tidak akan tukul rumah ini.
>> Kami melakukan ini dalam pset 2, tetapi untuk kuiz pastikan anda tahu perbezaan
antara cipher Caesar dan cipher Vigenère,
bagaimana kedua-dua kerja sifer mereka dan apa yang ia seperti untuk menyulitkan
dan teks menyahsulit menggunakan mereka 2 sifer.
Ingat, cipher Caesar hanya berputar watak masing-masing dengan jumlah yang sama,
memastikan anda arena oleh bilangan huruf dalam abjad.
Dan cipher Vigenère, di sisi lain, berputar setiap aksara
dengan jumlah yang berbeza, jadi bukannya mengatakan
setiap diputar watak oleh 3 Vigenère akan memutarkan setiap aksara
oleh jumlah yang berbeza bergantung pada kata kunci tertentu
di mana setiap huruf dalam kata kunci mewakili beberapa jumlah yang berbeza
untuk memutar teks yang jelas oleh.
Mari kita bercakap pertama mengenai skop pembolehubah.
Terdapat 2 jenis pembolehubah.
Kami mempunyai pembolehubah tempatan, dan ini akan ditakrifkan
luar utama atau di luar mana-mana fungsi atau blok,
dan ini akan boleh diakses di mana-mana dalam program anda.
Jika anda mempunyai fungsi dan dalam fungsi itu adalah gelung sementara
pembolehubah global yang besar boleh diakses di mana-mana.
Satu pembolehubah tempatan, di sisi lain, adalah scoped ke tempat di mana ia ditakrifkan.
>> Jika anda mempunyai fungsi di sini, sebagai contoh, kita mempunyai ini fungsi g,
dan di dalam g terdapat pembolehubah yang di sini dipanggil y,
dan ini bermakna bahawa ini adalah satu pemboleh ubah tempatan.
Walaupun pembolehubah ini dipanggil y
dan berubah-ubah ini dipanggil y 2 fungsi
tidak mempunyai idea apa pembolehubah tempatan antara satu sama lain.
Sebaliknya, di sini kita katakan int x = 5,
dan ini adalah di luar skop fungsi mana-mana.
Ia adalah di luar skop utama, jadi ini adalah satu pemboleh ubah global.
Ini bermakna bahawa dalam 2 fungsi ini apabila saya mengatakan x - atau x + +
Saya mengakses x sama di mana ini y dan y ini adalah pembolehubah yang berbeza.
Itulah perbezaan antara pemboleh ubah global dan pembolehubah tempatan.
Setakat reka bentuk berkenaan, kadang-kadang ia mungkin idea yang lebih baik
untuk memastikan pembolehubah tempatan apabila anda mungkin boleh
sejak mempunyai sekumpulan pembolehubah global boleh mendapatkan benar-benar mengelirukan.
Jika anda mempunyai sekumpulan fungsi semua mengubah perkara yang sama
anda mungkin lupa bagaimana jika fungsi ini sengaja mengubah global ini,
dan fungsi ini lain tidak tahu tentang hal itu,
dan ia tidak mendapatkan cukup mengelirukan kerana anda mendapatkan kod yang lebih.
Mengekalkan pembolehubah tempatan apabila anda mungkin boleh
adalah reka bentuk sahaja baik.
Tatasusunan, ingat, hanya senarai unsur-unsur jenis yang sama.
Dalam CI tidak boleh mempunyai senarai seperti 1, 2.0, hello.
Kita tidak boleh berbuat demikian.
>> Apabila kita mengisytiharkan array dalam C semua unsur-unsur perlu untuk menjadi jenis yang sama.
Di sini saya mempunyai pelbagai daripada 3 integer.
Di sini saya mempunyai panjang array, tetapi jika saya hanya mengisytiharkan ia dalam sintaks ini
mana saya nyatakan apa yang semua unsur-unsur Saya tidak teknikal memerlukan 3 ini.
Pengkompil adalah cukup bijak untuk memikirkan bagaimana besar array perlu.
Sekarang apabila saya ingin mendapatkan atau menetapkan nilai array
ini adalah sintaks untuk berbuat demikian.
Ini sebenarnya akan mengubah elemen kedua array kerana, ingat,
penomboran bermula pada 0, bukan pada 1.
Jika saya mahu untuk membaca nilai yang saya boleh mengatakan sesuatu seperti int x = array [1].
Atau jika saya ingin menetapkan nilai itu, seperti yang saya lakukan di sini,
Boleh saya katakan pelbagai [1] = 4.
Itu masa mengakses elemen oleh indeks mereka
atau kedudukan mereka atau di mana mereka berada dalam array,
dan penyenaraian yang bermula pada 0.
Kita juga boleh mempunyai tatasusunan array,
dan ini dipanggil pelbagai multi-dimensi.
Apabila kita mempunyai pelbagai pelbagai dimensi
yang bermakna kita boleh mempunyai sesuatu seperti baris dan lajur,
dan ini adalah hanya satu cara menggambarkan ini atau memikirkan ia.
Apabila saya mempunyai pelbagai multi-dimensi yang bermakna saya akan mula memerlukan
lebih daripada 1 indeks kerana jika saya mempunyai grid
hanya mengatakan apa berturut-turut anda berada dalam tidak memberi kita nombor satu.
Itu benar-benar hanya akan memberikan kita senarai nombor.
Katakan saya mempunyai array ini di sini.
Saya mempunyai pelbagai dipanggil grid, dan saya mengatakan baris 2 itu dan 3 lajur,
dan jadi ini adalah salah satu cara menggambarkan ia.
Apabila saya katakan saya mahu untuk mendapatkan elemen pada [1] [2]
yang bererti bahawa oleh kerana ini adalah baris pertama dan kemudian lajur
Saya akan melompat untuk berdayung 1 sejak saya berkata 1.
>> Kemudian saya akan datang ke sini untuk lajur 2, dan saya akan mendapatkan nilai 6.
Masuk akal?
Tatasusunan Multi-dimensi, ingat, teknikal hanya pelbagai tatasusunan.
Kita boleh mempunyai tatasusunan tatasusunan array.
Kita boleh terus pergi, tetapi benar-benar salah satu cara untuk berfikir tentang
bagaimana ini sedang dibentangkan dan apa yang berlaku adalah untuk menggambarkan
dalam grid seperti ini.
Apabila kita meninggal tatasusunan kepada fungsi, mereka akan berkelakuan
sedikit berbeza daripada apabila kita meninggal pembolehubah tetap untuk fungsi
seperti melepaskan int atau apungan.
Apabila kita lulus dalam jenis int atau char atau mana-mana data lain
kita hanya mengambil melihat jika fungsi mengubah
nilai pembolehubah bahawa bahawa perubahan tidak akan membiakkan
kepada fungsi memanggil.
Dengan pelbagai, di sisi lain, yang akan berlaku.
Jika saya lulus dalam pelbagai untuk beberapa fungsi dan fungsi yang mengubah beberapa elemen,
apabila saya datang kembali ke fungsi yang dipanggil
pelbagai saya kini akan menjadi berbeza, dan perbendaharaan kata untuk itu
tatasusunan adalah diluluskan oleh rujukan, seperti yang kita akan lihat nanti.
Ini adalah berkaitan dengan bagaimana kerja petunjuk, di mana ini jenis data asas,
Sebaliknya, yang diluluskan oleh nilai.
>> Kita boleh berfikir bahawa seperti membuat salinan pembolehubah beberapa dan kemudian lulus dalam salinan.
Ia tidak kira apa yang kita lakukan dengan pembolehubah yang.
Fungsi panggilan tidak akan sedar bahawa ia telah berubah.
Tatasusunan adalah hanya sedikit berbeza dalam hal itu.
Sebagai contoh, kerana kita hanya melihat, utama ialah hanya fungsi
yang boleh mengambil dalam 2 hujah.
Hujah pertama untuk fungsi utama adalah argc, atau bilangan hujah,
dan hujah kedua dipanggil argv,
dan mereka adalah nilai sebenar mereka hujah.
Katakan saya mempunyai satu program yang dipanggil this.c,
dan saya katakan membuat ini, dan saya akan menjalankannya pada baris arahan.
Sekarang untuk lulus dalam beberapa hujah untuk program saya dipanggil ini,
Saya boleh mengatakan sesuatu seperti. / Ini adalah cs 50.
Ini adalah apa yang kita bayangkan Daud untuk melakukan setiap hari di terminal.
Tetapi kini fungsi utama dalam program itu
mempunyai nilai-nilai ini, jadi argc ialah 4.
Ia mungkin sedikit mengelirukan kerana benar-benar kita hanya lulus dalam cs 50.
Itu hanya 3.
Tetapi ingat bahawa elemen pertama argv atau hujah pertama
adalah nama fungsi itu sendiri.
Jadi ini bermakna bahawa kita mempunyai 4 perkara di sini,
dan elemen pertama akan menjadi. / ini.
Dan ini akan diwakili sebagai rentetan.
Kemudian unsur-unsur yang selebihnya adalah apa yang kita ditaip dalam selepas nama program.
Jadi hanya sebagai diketepikan, kerana kita mungkin melihat di pset 2,
ingat bahawa rentetan 50 ≠ 50 integer.
Jadi kita tidak boleh mengatakan sesuatu seperti, 'int x = argv 3.'
>> Itu hanya tidak akan masuk akal, kerana ini adalah rentetan, dan ini adalah integer.
Jadi jika anda mahu untuk menukar antara 2, ingat, kita akan
mempunyai fungsi ini sihir dipanggil atoi.
Itu mengambil rentetan dan mengembalikan integer yang diwakili di dalam rentetan itu.
Jadi itulah kesilapan mudah untuk membuat kuiz,
hanya memikirkan bahawa ini secara automatik akan menjadi jenis yang betul.
Tetapi hanya tahu bahawa ini akan sentiasa menjadi rentetan
walaupun rentetan hanya mengandungi integer atau watak atau apungan.
Jadi sekarang mari kita bercakap tentang masa berjalan.
Apabila kita mempunyai semua algoritma ini yang melakukan semua perkara-perkara ini gila,
ia menjadi benar-benar berguna untuk bertanya soalan, "Berapa lama mereka mengambil?"
Kami mewakili bahawa dengan sesuatu yang dipanggil notasi asimptot.
Jadi ini bermakna - baik, mari kita mengatakan bahawa kita memberikan algoritma kami
beberapa input yang benar-benar, benar-benar, benar-benar besar.
Kami mahu bertanya soalan, "Berapa lama ia akan mengambil?
Berapa banyak langkah-langkah yang ia akan mengambil algoritma kami untuk menjalankan
sebagai fungsi saiz input? "
Jadi Cara pertama kita boleh menggambarkan masa berjalan dengan besar O.
Dan ini adalah masa terburuk berjalan kami.
Jadi, jika kita mahu untuk menyelesaikan array, dan kita memberi algoritma kami array
itulah dalam turutan menurun apabila ia perlu berada dalam usaha menaik,
yang akan menjadi kes terburuk.
Ini adalah atas kami terikat dalam panjang maksimum masa algoritma kami akan mengambil.
Sebaliknya, ini Ω akan untuk menggambarkan kes terbaik masa berjalan.
Jadi, jika kita memberi pelbagai yang sudah disusun algoritma sorting,
berapa lama ia akan mengambil masa untuk mengatasinya?
Dan ini, maka, menerangkan lebih rendah terikat pada menjalankan masa.
Jadi di sini adalah hanya beberapa perkataan yang menggambarkan beberapa kali berjalan biasa.
Ini adalah dalam tertib menaik.
Masa terpantas berjalan kita ada dipanggil malar.
>> Ini bermakna tidak kira berapa banyak elemen yang kita berikan algoritma kami,
tidak kira berapa besar pelbagai kami, sorting
atau melakukan apa sahaja yang kita lakukan kepada array akan sentiasa mengambil jumlah masa yang sama.
Jadi, kita boleh menyatakan bahawa hanya dengan 1, yang adalah pemalar.
Kami juga melihat pada masa jangka logaritma.
Jadi sesuatu seperti carian binari adalah logaritma,
di mana kita mengurangkan masalah pada separuh masa setiap
dan kemudian perkara yang hanya mendapat yang lebih tinggi dari sana.
Dan jika anda pernah menulis O mana-mana algoritma faktorial,
anda mungkin tidak perlu menganggap ini sebagai kerja hari anda.
Apabila kita bandingkan menjalankan kali ia adalah penting untuk ingat perkara-perkara ini.
Jadi jika saya mempunyai algoritma yang O (n), dan orang lain
telah algoritma O (2n) ini adalah sebenarnya berasimptot bersamaan.
Jadi, jika kita dapat n untuk menjadi nombor besar seperti eleventy bilion:
jadi apabila kita membandingkan eleventy bilion kepada sesuatu seperti eleventy bilion + 3,
tiba-tiba 3 yang tidak benar-benar membuat perbezaan yang besar lagi.
Itulah sebabnya kita akan mula mempertimbangkan perkara-perkara ini untuk menjadi setaraf.
Jadi perkara seperti ini pemalar di sini, terdapat 2 x ini, atau menambah 3,
ini adalah hanya pemalar, dan ini akan jatuh.
Jadi itulah sebabnya semua 3 daripada masa-masa yang dikendalikan adalah sama seperti mengatakan mereka berada O (n).
Begitu juga, jika kita mempunyai 2 jangka masa yang lain, katakan O (n ³ + 2n ²), kita boleh menambah
+ N, + 7, dan kemudian kita mempunyai satu masa yang lain jangka yang hanya O (n ³).
sekali lagi, ini adalah perkara yang sama kerana ini - ini tidak sama.
Ini adalah perkara yang sama, maaf. Jadi ini adalah sama kerana
³ n ini akan menguasai ² 2n.
>> Apa yang tidak perkara yang sama jika kita telah menjalankan kali seperti O (n ³) dan O (n ²)
kerana ³ n ini adalah lebih besar daripada ² n ini.
Jadi jika kita mempunyai atlet, tiba-tiba ini bermula kira,
tetapi apabila kita hanya berurusan dengan faktor-faktor seperti kita di sini,
maka ia tidak akan perkara kerana mereka hanya akan terkeluar.
Mari kita lihat di beberapa algoritma yang telah kita lihat setakat
dan bercakap tentang masa larian mereka.
Cara pertama mencari bilangan dalam senarai, yang kita lihat, carian linear.
Dan pelaksanaan carian linear adalah super mudah.
Kami hanya mempunyai senarai, dan kita akan melihat setiap elemen tunggal dalam senarai
sehingga kita dapati nombor kita sedang mencari.
Supaya bermakna bahawa dalam kes terburuk, O (n).
Dan kes terburuk di sini boleh menjadi jika elemen
elemen terakhir, kemudian menggunakan carian linear kita perlu melihat setiap elemen tunggal
sehingga kita sampai ke satu yang terakhir untuk mengetahui bahawa ia adalah sebenarnya dalam senarai.
Kita tidak boleh hanya memberikan separuh dan mengatakan, "Ia mungkin tidak ada."
Dengan carian linear, kita perlu melihat perkara keseluruhan.
Masa berjalan kes terbaik, di sisi lain, adalah malar
kerana dalam kes terbaik elemen yang kita sedang mencari hanya yang pertama dalam senarai.
Jadi ia akan membawa kita sebenarnya langkah 1, tidak kira berapa besar senarai
jika kita sedang mencari elemen pertama setiap masa.
>> Jadi apabila anda mencari, ingat, ia tidak memerlukan bahawa senarai kami perlu diselesaikan.
Kerana kita hanya akan melihat lebih setiap elemen tunggal, dan ia tidak benar-benar perkara
apakah perintah mereka adalah elemen masuk
Sebuah algoritma carian yang lebih bijak adalah sesuatu seperti carian binari.
Ingat, pelaksanaan carian binari adalah apabila anda hendak
terus mencari di tengah-tengah senarai.
Dan kerana kita sedang mencari di tengah-tengah, kita memerlukan senarai diisih
atau lain kita tidak tahu mana tengah-tengah, dan kita perlu untuk melihat lebih
senarai keseluruhan untuk mencari ia, dan kemudian pada ketika itu kita hanya membuang masa.
Jadi jika kita mempunyai senarai yang disusun dan kita dapati tengah-tengah, kita akan membandingkan tengah
kepada elemen kita sedang mencari.
Jika ia terlalu tinggi, maka kita boleh melupakan separuh yang betul
kerana kita tahu bahawa jika unsur kami sudah terlalu tinggi
dan segala-galanya hak unsur ini adalah lebih tinggi,
maka kita tidak perlu melihat ada lagi.
Jika di sisi lain, jika elemen kami adalah terlalu rendah,
kita tahu segala-galanya ke kiri elemen itu adalah juga terlalu rendah,
jadi ia tidak benar-benar masuk akal untuk melihat di sana, sama ada.
Dengan cara ini, dengan setiap langkah dan setiap kali kita melihat titik tengah senarai,
kita pergi untuk mengurangkan masalah kami pada separuh kerana tiba-tiba kita tahu
keseluruhan sekumpulan nombor yang tidak boleh menjadi salah satu yang kita cari.
>> Dalam pseudokod ini akan melihat sesuatu seperti ini,
dan kerana kita sedang memotong senarai pada separuh masa setiap satu,
melompat kes terburuk masa jangka kami daripada linear kepada logaritma.
Jadi tiba-tiba kita mempunyai log dalam langkah-langkah untuk mencari satu elemen dalam senarai.
Masa berjalan kes terbaik, walaupun, masih berterusan
kerana sekarang, mari kita hanya mengatakan bahawa elemen yang kita cari adalah
sentiasa pertengahan tepat senarai asal.
Jadi, kita boleh mengembangkan senarai kami sebagai besar seperti yang kita mahu, tetapi jika elemen yang kita cari adalah di tengah-tengah,
maka ia hanya akan membawa kita langkah 1.
Jadi itulah sebabnya kita O (log n) dan Ω (1) atau berterusan.
Mari kita sebenarnya menjalankan carian binari dalam senarai ini.
Jadi mari kita mengatakan bahawa kita sedang mencari elemen 164.
Perkara pertama yang kita akan lakukan adalah mencari titik tengah senarai ini.
Ia hanya kebetulan bahawa titik tengah akan jatuh di antara 2 nombor,
jadi mari kita hanya sewenang-wenangnya berkata, setiap kali titik tengah jatuh antara 2 nombor,
mari kita hanya pusingan.
Kita hanya perlu pastikan yang kita lakukan ini setiap langkah perjalanan.
Jadi kami pergi ke pusingan sehingga, dan kita akan mengatakan bahawa 161 adalah pertengahan senarai kami.
Jadi 161 <164, dan setiap elemen ke kiri daripada 161
juga <164, jadi kita tahu bahawa ia tidak akan membantu kita pada semua
untuk mula mencari di sini kerana unsur kita cari tidak boleh berada di sana.
Jadi apa yang kita boleh lakukan ialah kita hanya boleh melupakan separuh bahawa keseluruhan kiri senarai,
dan kini hanya mempertimbangkan dari kanan seterusnya 161.
>> Jadi sekali lagi, ini adalah titik tengah, mari kita hanya pusingan.
Sekarang 175 adalah terlalu besar.
Jadi kita tahu ia tidak akan membantu kita mencari di sini atau di sini,
jadi kita hanya boleh membuang yang jauh, dan akhirnya kita akan mencecah 164.
Sebarang pertanyaan pada carian binari?
Mari kita beralih daripada mencari melalui senarai yang sudah disusun
untuk benar-benar mengambil senarai nombor dalam mana-mana perintah
dan membuat senarai itu dalam tertib menaik.
Algoritma pertama kita melihat dipanggil isih gelembung.
Dan ini akan menjadi mudah algoritma yang kita lihat.
Isih gelembung mengatakan bahawa apabila mana-mana 2 elemen di dalam senarai adalah keluar dari tempat,
bermakna terdapat beberapa yang lebih tinggi ke kiri bilangan yang lebih rendah,
maka kita pergi untuk menukar mereka, kerana itu bermakna bahawa senarai ini akan menjadi
"Lebih disusun" berbanding sebelum ia.
Dan kami hanya akan meneruskan proses ini sekali lagi dan lagi dan lagi
sehingga akhirnya jenis unsur gelembung ke lokasi yang betul mereka dan kami mempunyai senarai yang disusun.
>> Jangka masa ini akan menjadi O (n ²). Mengapa?
Nah, kerana dalam kes terburuk, kita akan mengambil setiap elemen, dan
kita akan berakhir membandingkan kepada setiap elemen lain dalam senarai.
Tetapi dalam kes yang terbaik, kita mempunyai senarai yang sudah disusun, gelembung apapun
hanya akan pergi melalui sekali, katakan "Nope, saya tidak membuat apa-apa pertukaran, jadi saya lakukan."
Jadi kita mempunyai masa terbaik kes berjalan Ω (n).
Mari kita menjalankan apapun gelembung pada senarai.
Atau pertama, mari kita hanya melihat pseudokod beberapa benar-benar cepat.
Kami mahu mengatakan bahawa kita mahu menjejaki, dalam setiap lelaran gelung,
menjejaki sama ada atau tidak kita mengubah sebarang unsur-unsur.
Jadi sebab bagi yang demikian, kita akan berhenti apabila kita telah tidak bertukar mana-mana elemen.
Jadi pada permulaan gelung kita kita tidak bertukar apa-apa, jadi kita akan mengatakan itu palsu.
Sekarang, kita akan pergi melalui senarai dan bandingkan unsur i elemen i + 1
dan jika ia adalah kes bahawa terdapat beberapa yang lebih besar ke kiri bilangan yang lebih kecil,
maka kita hanya akan menukar mereka.
>> Dan kemudian kita akan ingat bahawa kita bertukar unsur.
Ini bermakna bahawa kita perlu pergi melalui senarai sekurang-kurangnya 1 lagi masa
kerana keadaan di mana kita berhenti apabila senarai keseluruhan sudah disusun,
bermakna kita telah tidak membuat apa-apa pertukaran.
Jadi itulah sebabnya keadaan kita turun di sini adalah 'manakala beberapa elemen telah bertukar.'
Jadi sekarang mari kita hanya melihat ini berjalan pada senarai.
Saya mempunyai senarai 5,0,1,6,4.
Isih gelembung akan bermula sepanjang jalan di sebelah kiri, dan ia akan membandingkan
unsur-unsur i, jadi 0 hingga i + 1, yang adalah elemen 1.
Ia akan berkata, baik 5> 0, tetapi sekarang 5 adalah ke kiri,
jadi saya perlu untuk menukar 5 dan 0.
Apabila saya menukar mereka, tiba-tiba saya mendapatkan senarai ini yang berbeza.
Sekarang 5> 1, jadi kita pergi untuk menukar mereka.
5 tidak> 6, jadi kita tidak perlu untuk berbuat apa-apa di sini.
Tetapi 6> 4, jadi kita perlu untuk menukar.
Sekali lagi, kita perlu untuk menjalankan melalui senarai keseluruhan akhirnya menemui
bahawa ini adalah daripada perintah; kita menukar mereka,
dan pada ketika ini kita perlu untuk menjalankan melalui senarai masa 1 more
untuk memastikan bahawa segala-galanya dalam perintahnya, dan pada apapun gelembung titik ini telah selesai.
Sebuah algoritma yang berbeza untuk mengambil beberapa elemen dan menyusun mereka adalah jenis pemilihan.
Idea di sebalik apapun pemilihan adalah bahawa kita akan membina sebahagian disusun senarai
1 elemen pada satu-satu masa.
>> Dan cara kita pergi untuk berbuat demikian adalah dengan membina segmen kiri senarai.
Dan pada dasarnya, setiap pada setiap langkah, kita akan mengambil elemen terkecil kita telah meninggalkan
yang belum diselesaikan lagi, dan kita akan bergerak ke dalam segmen yang disusun.
Ini bermakna kita perlu sentiasa mencari elemen Unsorted minimum
dan kemudian mengambil elemen minimum dan swap dengan apa jua
kiri paling elemen yang tidak disusun.
Masa berjalan ini akan menjadi O (n ²) kerana dalam kes terburuk
kita perlu untuk membandingkan setiap elemen tunggal untuk setiap elemen lain.
Kerana kita mengatakan bahawa jika kita mula di separuh kiri senarai, kita perlu
untuk pergi melalui keseluruhan segmen yang betul untuk mencari elemen terkecil.
Dan kemudian, sekali lagi, kita perlu untuk pergi ke segmen yang betul keseluruhan dan
terus pergi ke bahawa lebih dan lebih dan lebih lagi.
Itu akan menjadi ² n. Kami akan perlu untuk di dalam gelung yang lain untuk gelung
yang mencadangkan ² n.
Dalam pemikiran kes terbaik, mari kita mengatakan bahawa kita memberikan ia satu senarai yang sudah disusun;
kita sebenarnya tidak melakukan apa-apa lebih baik daripada ² n.
Kerana apapun pemilihan tidak mempunyai cara untuk mengetahui bahawa
elemen minimum hanya satu saya berlaku untuk melihat.
Ia masih perlu untuk memastikan bahawa ini sebenarnya adalah minimum.
>> Dan satu-satunya cara untuk memastikan bahawa ia adalah minimum, menggunakan algoritma ini,
adalah untuk melihat pada setiap elemen tunggal lagi.
Jadi benar-benar, jika anda memberikan ia - jika anda memberikan apapun pemilihan senarai sudah disusun,
ia tidak akan melakukan apa-apa yang lebih baik daripada memberikan senarai yang tidak diselesaikan lagi.
By the way, jika ia berlaku untuk kes bahawa sesuatu adalah O (sesuatu)
dan omega sesuatu, kita hanya boleh mengatakan lebih ringkas bahawa ia adalah θ sesuatu.
Jadi, jika anda melihat yang tampil di mana-mana, bahawa apa yang hanya bermakna.
>> Jika sesuatu theta n ², ia adalah kedua-dua O besar (n ²) dan Ω (n ²).
Jadi kes terbaik dan kes terburuk, ia tidak membuat perbezaan,
algoritma akan melakukan perkara yang sama setiap kali.
Jadi ini adalah apa pseudokod untuk menyelesaikan pemilihan boleh kelihatan seperti.
Kami pada dasarnya akan mengatakan bahawa saya mahu untuk melelar senarai
dari kiri ke kanan, dan pada setiap lelaran gelung, saya akan bergerak
elemen minimum ke bahagian ini disusun senarai.
Dan apabila saya memindahkan sesuatu di sana, saya tidak perlu untuk melihat bahawa elemen lagi.
Kerana, ia disusun sebaik sahaja saya menukar elemen dalam segmen kiri senarai
kerana kita sedang melakukan segala-galanya dalam tertib menaik dengan menggunakan minimum.
Jadi kita berkata, okay, kita berada pada kedudukan i, dan kita perlu melihat semua elemen
kepada hak i untuk mencari minimum.
Jadi itu bermakna kita mahu melihat dari i + 1 akhir senarai.
Dan kini, jika elemen bahawa kita sedang melihat adalah kurang daripada minimum kami setakat ini,
yang, ingat, kita bermula dari minimum untuk hanya menjadi
apa jua unsur yang kita berada pada masa ini, saya akan menganggap itulah minimum.
Jika saya dapati elemen yang lebih kecil daripada itu, maka saya akan katakan, okay,
baik, saya telah mendapati minimum baru.
Saya akan ingat di mana minimum yang.
>> Jadi sekarang, apabila saya telah pergi melalui segmen yang Unsorted kanan,
Yang boleh saya katakan saya akan menukar elemen minimum dengan unsur yang berada dalam kedudukan i.
Itu akan untuk membina senarai saya, bahagian saya disusun senarai dari kiri ke kanan,
dan kita tidak pernah perlu untuk melihat unsur lagi apabila ia adalah di bahagian itu.
Apabila kita telah bertukar.
Jadi mari kita menjalankan apapun pemilihan dalam senarai ini.
Elemen biru di sini akan menjadi i, dan elemen merah akan menjadi elemen minimum.
Jadi saya bermula sepanjang jalan di sebelah kiri senarai, jadi pada 5.
Sekarang kita perlu mencari elemen Unsorted minimum.
Jadi kita katakan 0 <5, jadi 0 adalah minimum baru saya.
>> Tetapi saya tidak boleh berhenti di situ, kerana walaupun kita boleh mengiktiraf bahawa 0 adalah yang terkecil,
kita perlu untuk menjalankan melalui setiap elemen lain senarai untuk pastikan.
Jadi 1 adalah lebih besar, 6 adalah lebih besar, 4 adalah lebih besar.
Ini bermakna bahawa selepas melihat semua elemen-elemen ini, saya telah berazam 0 adalah yang paling kecil.
Jadi saya akan menukar 5 dan 0.
Apabila saya menukar itu, saya akan mendapatkan senarai baru, dan saya tahu bahawa saya tidak perlu untuk melihat bahawa 0 lagi
kerana sekali saya telah bertukar ia, saya telah disusun dan kami sudah selesai.
Kini ia hanya kebetulan bahawa elemen biru sekali lagi 5,
dan kita perlu melihat pada 1, 6 dan 4 untuk menentukan bahawa 1
adalah elemen minimum terkecil, jadi kami akan menukar 1 dan 5.
Sekali lagi, kita perlu melihat - bandingkan 5 dengan 6 dan 4,
dan kami akan menukar 4 dan 5, dan akhirnya, bandingkan
mereka 2 nombor dan swap mereka sehingga kita mendapat senarai kami disusun.
Sebarang pertanyaan mengenai apapun pemilihan?
Okay. Mari kita beralih ke topik terakhir di sini, dan yang rekursi.
>> Rekursi, ingat, perkara ini benar-benar meta mana fungsi
berkali-kali panggilan itu sendiri.
Jadi, pada satu ketika, manakala fuction kami berkali-kali memanggil sendiri,
perlu ada beberapa titik di mana kita berhenti memanggil diri.
Kerana jika kita tidak berbuat demikian, maka kita hanya akan terus melakukan ini selama-lamanya,
dan program kami hanya tidak akan menamatkan.
Kami menyeru ini keadaan kes asas.
Dan kes asas mengatakan, bukannya memanggil fungsi lagi,
Saya hanya akan kembali beberapa nilai.
Jadi apabila kita telah kembali nilai, kami telah menghentikan memanggil diri,
dan selebihnya panggilan kami telah dibuat setakat ini juga boleh kembali.
Bertentangan dengan kes asas adalah kes rekursi.
Dan ini adalah apabila kita hendak membuat panggilan lain untuk fungsi bahawa kita kini masuk
Dan kita mungkin, walaupun tidak selalu, mahu menggunakan hujah-hujah yang berbeza.
>> Jadi, jika kita mempunyai satu fungsi yang dipanggil f, dan f hanya dipanggil mengambil 1 hujah,
dan kita hanya menyimpan memanggil f (1), f (1), f (1), dan ia hanya kebetulan bahawa
hujah 1 jatuh ke dalam kes rekursi, kita masih tidak akan berhenti.
Malah jika kita mempunyai kes asas, kita perlu memastikan bahawa akhirnya kita akan melanda bahawa kes asas.
Kami tidak hanya menyimpan tinggal dalam kes ini rekursi.
Secara umumnya, apabila kita panggil diri kita, kita mungkin akan mempunyai hujah yang berbeza setiap kali.
Berikut adalah fungsi rekursi yang benar-benar mudah.
Jadi, ini akan mengira faktoran nombor.
Sehingga top sini kita mempunyai kes asas kami.
Dalam kes bahawa n ≤ 1, kita tidak akan memanggil faktorial lagi.
Kita akan berhenti, kita hanya akan kembali beberapa nilai.
Jika ini tidak benar, maka kita pergi untuk memukul kes rekursi kami.
Notis di sini bahawa kita tidak hanya memanggil faktorial (n), kerana itu tidak akan sangat membantu.
Kami akan memanggil faktorial sesuatu yang lain.
>> Dan supaya anda boleh lihat, akhirnya jika kita lulus sesuatu faktorial (5) atau,
kita akan memanggil faktorial (4) dan sebagainya, dan akhirnya kita akan melanda kes ini asas.
Jadi ini kelihatan baik. Mari kita lihat apa yang berlaku apabila kita sebenarnya menjalankan ini.
Ini adalah timbunan, dan mari kita mengatakan bahawa utama akan memanggil fungsi ini dengan hujah (4).
Jadi sekali faktorial melihat dan = 4, faktoran akan memanggil dirinya.
Sekarang, tiba-tiba, kita mempunyai faktorial (3).
Jadi fungsi-fungsi ini akan terus berkembang sehingga akhirnya kita melanda kes asas kami.
Pada ketika ini, nilai pulangan ini adalah pulangan (nx nilai pulangan ini),
nilai pulangan ini adalah nx nilai pulangan ini.
Akhirnya kita perlu untuk memukul beberapa nombor.
Di atas sini, kita katakan pulangan 1.
Ini bermakna bahawa apabila kita kembali nombor yang, kita boleh pop ini off timbunan.
Jadi ini faktorial (1) dilakukan.
Apabila 1 pulangan, ini faktorial (1) pulangan, ini kembali kepada 1.
Nilai pulangan ini, ingat, adalah nx nilai pulangan ini.
Jadi, tiba-tiba, lelaki ini tahu bahawa saya mahu kembali 2.
>> Jadi ingat, memulangkan nilai ini adalah hanya nx nilai kembali di sini.
Jadi sekarang kita boleh mengatakan 3 x 2, dan akhirnya, di sini kita boleh mengatakan
ini hanya akan menjadi 4 x 3 x 2.
Dan sekali ini pulangan, kita akan mendapat ke dalam integer tunggal utama.
Sebarang pertanyaan pada rekursi?
Semua hak. Jadi ada lebih banyak masa untuk soalan di hujung,
tetapi kini Yusuf akan meliputi topik yang selebihnya.
>> [Joseph Ong] Baiklah. Jadi sekarang bahawa kita telah bercakap tentang recursions,
mari kita bercakap sedikit tentang apa bergabung apapun adalah.
Gabung apapun pada asasnya cara lain menyusun senarai nombor.
Dan bagaimana ia berfungsi, dengan jenis merge anda mempunyai senarai, dan apa yang kita lakukan adalah
kita katakan, mari kita berpecah ini kepada 2 bahagian.
Kami pertama akan menjalankan bergabung apapun sekali lagi di separuh kiri,
maka kami akan menjalankan menggabungkan jenis di separuh kanan,
dan yang memberikan kami sekarang 2 bahagian yang disusun, dan kini kami akan untuk menggabungkan mereka dua bersama-sama.
Ia agak sukar untuk melihat tanpa contoh, jadi kita akan pergi melalui usul dan lihat apa yang berlaku.
Jadi anda mula dengan senarai ini, kita berpecah kepada 2 bahagian.
Kami menjalankan bergabung jenis di separuh kiri pertama.
Jadi itulah separuh kiri, dan kini kita berjalan mereka melalui senarai ini sekali lagi
yang mendapat berlalu ke dalam apapun merge, dan kemudian kita melihat, sekali lagi,
di sebelah kiri senarai ini dan kami menjalankan menggabungkan jenis di atasnya.
Sekarang, kita akan mendapat ke senarai 2 nombor,
dan kini separuh kiri hanya 1 elemen panjang, dan kita tidak boleh
berpecah senarai itu hanya 1 elemen ke dalam separuh, jadi kita hanya mengatakan, apabila kita mempunyai 50,
yang hanya 1 elemen, ia sudah disusun.
>> Apabila kita sedang dilakukan dengan itu, kita dapat melihat bahawa kita boleh
bergerak ke separuh kanan senarai ini,
dan 3 juga disusun, dan jadi sekarang bahawa kedua-dua bahagian senarai ini disusun
kita boleh menyertai nombor-nombor ini kembali bersama-sama.
Jadi kita melihat pada 50 dan 3; 3 adalah lebih kecil daripada 50, jadi ia pergi pertama dan kemudian 50 datang masuk
Sekarang, yang dilakukan, kita kembali kepada senarai itu dan apapun ia adalah separuh betul.
42 adalah nombor itu sendiri, jadi ia sudah disusun.
Jadi sekarang kita bandingkan ini 2 dan 3 adalah lebih kecil daripada 42, jadi yang mendapat dimasukkan ke dalam mulanya,
kini 42 mendapat dimasukkan ke dalam, dan 50 mendapat meletakkan masuk
Sekarang, itu diselesaikan, kita pergi sepanjang jalan kembali ke atas, 1337 dan 15.
Nah, sekarang kita melihat separuh kiri senarai ini, 1337 adalah dengan sendirinya jadi ia disusun dan sama dengan 15.
Jadi sekarang kita menggabungkan kedua-2 nombor untuk menyelesaikan bahawa senarai asal, 15 <1337,
jadi ia pergi pertama, maka 1337 pergi masuk
Dan sekarang kita disusun kedua-dua bahagian senarai asal top up.
Dan semua yang perlu kita lakukan adalah menggabungkan kedua.
Kami melihat 2 nombor pertama senarai ini, 3 <15, jadi ia pergi ke dalam pelbagai jenis yang pertama.
15 <42, jadi ia pergi masuk Sekarang, 42 <1337, yang pergi masuk
50 <1337, jadi ia pergi masuk Dan melihat bahawa kita hanya mengambil 2 nombor dari senarai ini.
Jadi kita tidak hanya seli antara 2 senarai.
Kami hanya mencari pada mulanya, dan kita sedang mengambil elemen
yang lebih kecil dan kemudian meletakkan ia ke dalam pelbagai kami.
Sekarang kita telah digabungkan semua bahagian dan kami sudah selesai.
>> Sebarang pertanyaan tentang bergabung apapun? Ya?
[Pelajar] Jika ia berpecah kepada kumpulan-kumpulan yang berbeza, mengapa tidak mereka hanya berpecah sekali
dan anda mempunyai 3 dan 2 dalam satu kumpulan? [Rehat yang tidak bijaksana yang soalan]
Sebab - jadi persoalannya ialah, mengapa tidak boleh kita hanya bergabung mereka pada langkah yang pertama selepas kita mempunyai mereka?
Sebab kita boleh lakukan ini, bermula pada elemen-elemen yang paling kiri kedua-dua pihak,
dan kemudian mengambil satu yang lebih kecil dan memasukkannya ke dalam, adalah bahawa kita tahu bahawa ini
senarai individu dalam pesanan disusun.
Jadi jika saya melihat elemen-elemen yang paling kiri kedua-dua bahagian,
Saya tahu mereka akan menjadi elemen terkecil senarai.
Jadi saya boleh meletakkan mereka ke tempat elemen terkecil senarai ini besar.
Sebaliknya, jika saya melihat mereka 2 senarai di peringkat kedua di sana,
50, 3, 42, 1337 dan 15, mereka tidak diselesaikan.
Jadi jika saya melihat 50 dan 1337, saya akan meletakkan 50 ke dalam senarai saya pertama.
Tetapi itu tidak benar-benar masuk akal, kerana 3 adalah elemen terkecil daripada semua orang.
Jadi sebab sahaja yang boleh kita lakukan langkah ini menggabungkan adalah kerana senarai kami sudah disusun.
Itulah sebabnya kita perlu untuk mendapatkan sepanjang jalan ke bawah
kerana apabila kita mempunyai hanya satu nombor, anda tahu bahawa nombor tunggal
dalam dan dengan sendirinya sudah senarai yang disusun.
>> Apa-apa soalan? Tidak?
Kerumitan? Nah, anda boleh melihat bahawa pada setiap langkah ada nombor akhir,
dan kita boleh membahagikan senarai dalam log separuh n kali,
yang mana kita akan mendapat ini log n x n kerumitan.
Dan anda akan melihat kes yang terbaik untuk menyelesaikan merge n log n, dan ia hanya kebetulan
bahawa kes terburuk, atau Ω di sana, juga n log n.
Sesuatu yang perlu diingat.
Bergerak ke atas, mari kita pergi ke beberapa fail super asas I / O.
Jika anda melihat Kacau, anda akan melihat kita mempunyai beberapa jenis sistem
di mana anda boleh menulis ke fail log jika anda membaca melalui kod.
Mari kita lihat bagaimana anda boleh berbuat demikian.
Nah, kita mempunyai fprintf, yang anda boleh berfikir sebagai hanya printf,
tetapi hanya mencetak ke fail sebaliknya, dan seterusnya f pada permulaan.
Ini jenis kod di sini, apa yang ia adalah, seperti yang anda mungkin telah dilihat dalam Kacau,
ia pergi melalui percetakan 2-dimensi pelbagai anda keluar baris demi baris apa nombor.
Dalam kes ini, printf mencetak keluar ke terminal anda atau apa yang kita panggil output standard seksyen.
>> Dan kini, dalam kes ini, semua yang perlu kita lakukan adalah menggantikan printf dengan fprintf,
beritahu apa fail yang anda mahu untuk mencetak, dan dalam kes ini ia hanya mencetak ia keluar untuk fail yang
bukannya mencetak ia keluar ke terminal anda.
Nah, maka menimbulkan persoalan: Di manakah kita mendapatkan fail jenis ini dari, betul-betul?
Kami diluluskan log masuk untuk fuction ini fprintf tetapi kita tidak tahu dari mana ia datang.
Nah, awal dalam kod, apa yang kita terpaksa ini sebahagian kod di sini,
yang pada dasarnya mengatakan bahawa fail terbuka panggilan log.txt.
Apa yang kita lakukan selepas itu adalah kita perlu memastikan bahawa fail sebenarnya membuka berjaya.
Jadi, ia mungkin gagal atas sebab-sebab yang pelbagai, anda tidak mempunyai ruang yang cukup di dalam komputer anda, sebagai contoh.
Jadi ia sentiasa penting sebelum anda melakukan apa-apa operasi dengan fail
bahawa kita memeriksa sama ada fail tersebut telah dibuka dengan jayanya.
Jadi apa yang, itulah hujah untuk fopen, baik, kita boleh membuka fail dalam banyak cara.
Apa yang kita boleh lakukan ialah, kita boleh lulus ia w, yang bermaksud mengatasi fail jika ia keluar sudah,
Kita boleh lulus, yang mereka melampirkan pada akhir fail dan bukannya mengatasi ia,
atau kita boleh menentukan r, yang bermaksud, mari kita membuka fail sebagai baca sahaja.
Jadi, jika program ini cuba untuk membuat apa-apa perubahan kepada fail,
menjerit pada mereka dan jangan biarkan mereka melakukannya.
Akhirnya, apabila kita sedang dilakukan dengan fail, selesai melakukan operasi di atasnya,
kita perlu pastikan kita menutup fail.
Dan demikian pada akhir program anda, anda akan lulus mereka lagi
fail ini bahawa anda dibuka, dan hanya menutup.
Jadi ini adalah sesuatu yang penting yang anda perlu pastikan anda melakukan.
Jadi ingat anda boleh membuka fail, maka anda boleh menulis ke fail,
melakukan operasi dalam fail, tetapi kemudian anda perlu untuk menutup fail di akhir.
>> Sebarang soalan pada fail asas I / O? Ya?
[Pelajar soalan, difahami]
Hak di sini. Persoalannya, di manakah fail ini log.txt muncul?
Nah, jika anda hanya memberi log.txt, ia mewujudkan dalam direktori yang sama sebagai executable.
Jadi jika you're - >> [Pelajar soalan, difahami]
Ya. Dalam folder yang sama, atau dalam direktori yang sama, seperti yang anda memanggilnya.
Sekarang ingatan, timbunan, dan timbunan.
Jadi bagaimana memori dibentangkan dalam komputer?
Nah, anda boleh bayangkan memori sebagai jenis blok ini di sini.
Dan dalam ingatan kita mempunyai apa yang dipanggil timbunan yang terperangkap di sana, dan timbunan yang di bawah sana.
Dan timbunan tumbuh ke bawah dan timbunan tumbuh ke atas.
Jadi sebagai Tommy menyebut - oh, baik, dan kita mempunyai ini 4 segmen lain yang saya akan sampai ke dalam kedua -
Sebagai Tommy berkata sebelum ini, anda tahu bagaimana fungsi beliau memanggil diri mereka dan memanggil antara satu sama lain?
Mereka membina ini jenis bingkai tindanan.
Nah, jika panggilan utama foo, foo mendapat diletakkan pada timbunan.
Foo panggilan bar, bar mendapatkan kita meletakkan pada timbunan, dan yang mendapat dimasukkan pada timbunan selepas.
Dan kerana mereka kembali, mereka masing-masing mendapat diambil kira timbunan.
Apa yang setiap lokasi ini dan ingatan memegang?
Nah, atas, yang merupakan segmen teks, mengandungi program itu sendiri.
Jadi kod mesin, yang ada, sebaik sahaja anda menyusun program anda.
Seterusnya, apa-apa dimulakan pembolehubah global.
>> Jadi anda mempunyai pembolehubah global dalam program anda, dan anda mengatakan seperti, a 5 =,
yang mendapat dimasukkan ke dalam segmen itu, dan betul-betul di bawah itu,
anda mempunyai apa-apa data yang tidak diisytiharkan global, yang hanya int,
tetapi anda tidak mengatakan ia adalah sama dengan apa-apa.
Sedarlah ini adalah pembolehubah global, jadi mereka berada di luar utama.
Jadi ini bermakna sebarang pembolehubah global yang diisytiharkan tetapi tidak dimulakan.
Jadi apa dalam timbunan? Memori diperuntukkan menggunakan malloc, yang kita akan sampai ke dalam sedikit.
Dan akhirnya, dengan timbunan anda mempunyai sebarang pembolehubah tempatan
dan apa-apa fungsi yang anda mungkin memanggil mana-mana parameter mereka.
Perkara yang lepas, anda tidak benar-benar perlu tahu apa pembolehubah persekitaran lakukan,
tetapi apabila anda menjalankan program, adalah sesuatu yang berkaitan, seperti
ini adalah username orang yang berlari program.
Dan yang akan menjadi jenis di bawah.
Dari segi alamat ingatan, yang adalah nilai perenambelasan,
nilai pada permulaan atas pada 0, dan mereka pergi sepanjang jalan ke bawah.
Dalam kes ini, jika anda pada sistem 32-bit,
alamat di bawah akan menjadi 0x, diikuti oleh af, kerana itulah 32 bit,
yang merupakan 8 bait, dan dalam kes ini 8 bytes sepadan dengan 8 digit perenambelasan.
Jadi turun di sini anda akan mempunyai, seperti, 0xffffff, dan di sana anda akan mempunyai 0.
Jadi apa yang adalah petunjuk? Sebahagian daripada anda mungkin tidak telah dilindungi ini dalam seksyen sebelum ini.
tetapi kita tidak pergi ke kuliah, jadi penunjuk adalah hanya jenis data
mana kedai, bukannya sejenis nilai seperti 50, ia menyimpan alamat beberapa lokasi dalam ingatan.
Seperti memori yang [tidak bijaksana yang].
Jadi dalam kes ini, apa yang telah kita adalah, kita mempunyai satu penuding kepada integer atau * int,
dan ia mengandungi alamat perenambelasan 0xDEADBEEF.
>> Jadi apa yang kita ada sekarang, ini mata penunjuk di beberapa lokasi dalam ingatan,
dan itulah hanya, nilai 50 adalah di lokasi memori ini.
Pada sesetengah sistem 32-bit, ke atas semua sistem 32-bit, petunjuk mengambil bit 32 atau 4 bait.
Tetapi, sebagai contoh, pada sistem 64-bit, petunjuk adalah 64-bit.
Jadi itulah sesuatu yang anda akan mahu ingat.
Jadi pada sistem akhir-bit, penunjuk adalah bit akhir panjang.
Penunjuk adalah jenis sukar untuk dihadam tanpa perkara-perkara tambahan,
jadi mari kita pergi melalui contoh peruntukan memori dinamik.
Apa memori peruntukan dinamik tidak untuk anda, atau apa yang kita panggil malloc
ia membolehkan anda memperuntukkan beberapa jenis data di luar set.
Jadi data ini adalah jenis lebih kekal bagi tempoh program.
Kerana seperti yang anda tahu, jika anda mengisytiharkan x di dalam fungsi, dan bahawa pulangan fungsi,
anda tidak lagi mempunyai akses kepada data yang telah disimpan dalam x.
Apa petunjuk marilah kita lakukan adalah mereka marilah kita menyimpan ingatan atau nilai-nilai kedai
dalam segmen yang berbeza ingatan, iaitu timbunan itu.
Sekarang apabila kita kembali fungsi, selagi kita mempunyai penunjuk
ke lokasi tersebut dalam ingatan, maka apa yang boleh kita lakukan ialah kita hanya boleh melihat nilai di sana.
Mari kita melihat contoh: Ini adalah susun atur ingatan kita lagi.
Dan kita mempunyai fungsi ini, utama.
Apa yang ia adalah - okay, begitu mudah, betul - int x = 5, itu hanya pembolehubah pada timbunan utama.
>> Sebaliknya, sekarang kita mengisytiharkan satu penunjuk yang memanggil giveMeThreeInts fungsi.
Dan jadi sekarang kita pergi ke fungsi ini dan kita mewujudkan bingkai tindanan baru untuk itu.
Walau bagaimanapun, dalam bingkai tindanan ini, kita mengisytiharkan int * menggoda,
yang dalam mallocs 3 integer untuk kita.
Jadi saiz int akan memberi kita berapa banyak bait int ini adalah,
dan malloc memberikan kita bahawa bait banyak ruang pada timbunan itu.
Jadi dalam kes ini, kita telah mencipta ruang yang cukup untuk 3 integer,
dan timbunan itu adalah cara di sana, itulah sebabnya saya telah ditarik ia lebih tinggi.
Apabila kita sedang dilakukan, kita kembali di sini, anda hanya perlu 3 ints dikembalikan,
dan ia kembali alamat, dalam kes ini lebih di mana memori yang.
Dan kita menetapkan pointer = suis, dan di sana kita mempunyai hanya satu lagi penunjuk.
Tetapi apa yang bahawa pulangan fungsi disusun di sini dan hilang.
Jadi sementara hilang, tetapi kita masih mengekalkan alamat di mana
mereka 3 integer dalam sesalur.
Jadi dalam set ini, petunjuk scoped tempatan untuk bingkai disusun,
tetapi memori yang mereka rujuk adalah dalam timbunan.
>> Adakah yang masuk akal?
[Pelajar] Bolehkah anda mengulangi bahawa? >> [Yusuf] Ya.
Jadi jika saya kembali hanya sedikit, anda lihat bahawa menggoda diperuntukkan
beberapa memori pada timbunan sehingga sana.
Jadi, apabila fungsi ini, giveMeThreeInts pulangan, ini timbunan sini akan hilang.
Dan dengan mana-mana pembolehubah, dalam kes ini, ini penunjuk yang telah diperuntukkan dalam bingkai disusun.
Yang akan hilang, tetapi sejak kami kembali menggoda
dan kita menetapkan penunjuk = menggoda, penunjuk yang kini akan menunjukkan memori yang sama lokasi sebagai menggoda adalah.
Jadi sekarang, walaupun kita kehilangan sementara, bahawa penunjuk tempatan,
kita masih mengekalkan alamat ingatan apa yang ia menunjuk ke dalam penunjuk yang berubah-ubah.
Soalan? Yang boleh jenis topik mengelirukan jika anda tidak pergi ke atasnya dalam seksyen.
Kita boleh, TF anda pasti akan pergi lebih dan sudah tentu kita boleh menjawab soalan-soalan
pada akhir sesi kajian ini.
Tetapi ini adalah jenis topik yang kompleks, dan saya mempunyai lebih banyak contoh yang akan muncul
yang akan membantu menjelaskan apa petunjuk sebenarnya.
>> Dalam kes ini, petunjuk adalah bersamaan dengan array,
jadi saya hanya boleh menggunakan penunjuk ini sebagai perkara yang sama seperti pelbagai int.
Jadi saya mengindeks ke 0, dan menukar integer yang pertama untuk 1,
menukar integer kedua kepada 2, dan integer 3 hingga 3.
Jadi lanjut mengenai petunjuk. Nah, ingat Binky.
Dalam kes ini kita telah diperuntukkan penunjuk, atau kita mengisytiharkan penunjuk,
tetapi pada mulanya, apabila saya hanya mengisytiharkan penunjuk, ia bukan menunjuk ke mana-mana sahaja dalam ingatan.
Ia hanya nilai sampah di dalamnya.
Jadi saya tidak tahu di mana penunjuk ini menunjuk ke.
Ia mempunyai alamat yang hanya dipenuhi dengan 0 dan 1 di mana ia pada mulanya diisytiharkan.
Saya tidak boleh berbuat apa-apa dengan ini sehingga saya memanggil malloc di atasnya
dan kemudian ia memberikan saya sedikit ruang pada timbunan di mana saya boleh meletakkan nilai-nilai di dalam.
Kemudian lagi, saya tidak tahu apa yang di dalam memori ini.
Jadi perkara pertama yang saya perlu lakukan adalah memeriksa sama ada sistem mempunyai memori yang cukup
untuk memberikan saya kembali 1 integer di tempat pertama, itulah sebabnya saya lakukan ini memeriksa.
Jika penunjuk adalah batal, yang bermakna bahawa ia tidak mempunyai ruang yang cukup atau beberapa kesilapan lain berlaku,
jadi saya harus keluar daripada program saya.
Tetapi jika ia tidak berjaya, kini saya boleh menggunakan penunjuk bahawa
dan apa penunjuk * tidak adalah ia mengikuti mana alamat
di mana nilai itu, dan ia menyatakan ia sama dengan 1.
Jadi di sini, kita sedang memeriksa jika memori yang wujud.
>> Sebaik sahaja anda tahu ia wujud, anda boleh meletakkan ke dalamnya
apakah nilai yang anda mahu dimasukkan ke dalam ia, dalam kes ini 1.
Apabila kita sedang dilakukan dengan itu, anda perlu untuk membebaskan bahawa penunjuk
kerana kita perlu kembali kepada sistem bahawa memori yang anda meminta di tempat pertama.
Kerana komputer tidak tahu apabila kita hendak dilakukan dengan ia.
Dalam kes ini kita jelas memberitahu ia, okay, kita dilakukan dengan memori itu.
Jika beberapa proses lain perlu, beberapa program lain yang memerlukannya, berasa bebas untuk pergi ke hadapan dan mengambil ia.
Apa yang kita juga boleh lakukan ialah kita hanya boleh mendapatkan alamat pembolehubah tempatan di set.
X Begitu int dalam bingkai disusun daripada utama.
Dan apabila kita menggunakan #: glib ini, ini dan pengendali, apa yang ia adalah
ia mengambil masa x, dan x ialah hanya beberapa data dalam memori, tetapi ia mempunyai alamat.
Ia terletak di suatu tempat. Jadi dengan memanggil & x, apakah ini tidak adalah ia memberikan kita alamat x.
Dengan cara ini, kita sedang membuat titik penunjuk di mana x adalah dalam ingatan.
Sekarang kita hanya melakukan sesuatu seperti * x, kita akan mendapat 5 kembali.
Bintang itu dipanggil dereferencing ia.
Anda mengikuti alamat dan anda mendapat nilai yang disimpan di sana.
>> Apa-apa soalan? Ya?
[Pelajar] Jika anda tidak melakukan perkara yang bermata 3-, adakah ia masih menyusun?
Ya. Jika anda tidak melakukan perkara 3-penunjuk, ia masih akan menyusun,
tetapi saya akan menunjukkan kepada anda apa yang berlaku dalam kedua, dan tanpa berbuat demikian,
itulah apa yang kita panggil kebocoran memori. Anda tidak memberikan sistem
menyokong memori, jadi selepas manakala program akan berkumpul
memori yang ia tidak menggunakan, dan apa-apa lagi boleh menggunakannya.
Jika anda pernah melihat Firefox 1.5 juta kilobytes pada komputer anda,
dalam pengurus tugas, itulah apa yang berlaku.
Anda mempunyai kebocoran memori dalam program ini bahawa mereka tidak mengendalikan.
Jadi bagaimana penunjuk aritmetik kerja?
Nah, aritmetik penunjuk adalah jenis pengindeksan seperti ke dalam array.
Dalam kes ini, saya mempunyai penunjuk, dan apa yang saya lakukan ialah saya membuat titik penunjuk kepada elemen pertama
array ini 3 integer bahawa saya telah diperuntukkan.
Jadi sekarang apa yang saya lakukan, penunjuk bintang hanya menukar elemen pertama dalam senarai.
Bintang pointer +1 mata di sini.
Jadi penunjuk adalah di sini, penunjuk +1 adalah di sini, penunjuk 2 adalah di sini.
>> Jadi hanya menambah 1 adalah perkara yang sama seperti bergerak di sepanjang array ini.
Apa yang kita lakukan ialah, apabila kita melakukan penunjuk 1 anda mendapat alamat di sini,
dan dalam usaha untuk mendapatkan nilai di sini, anda meletakkan bintang dari seluruh ungkapan
untuk dereference.
Jadi, dalam kes ini, saya menetapkan lokasi pertama dalam pelbagai ini kepada 1,
lokasi kedua kepada 2, dan lokasi ketiga hingga 3.
Kemudian apa yang saya lakukan di sini adalah saya mencetak penunjuk kami 1,
yang hanya memberikan saya 2.
Sekarang saya incrementing penunjuk, jadi penunjuk sama pointer 1,
yang bergerak ke hadapan.
Dan jadi sekarang jika saya hendak mencetak keluar 1 penunjuk, penunjuk +1 adalah kini 3,
yang dalam kes ini mencetak keluar 3.
Dan untuk sesuatu yang percuma, penunjuk bahawa saya memberikan
mesti menunjuk pada permulaan array yang saya pulang dari malloc.
Jadi, dalam kes ini, jika saya adalah untuk memanggil 3 di sini, ini tidak akan menjadi betul,
kerana ia adalah di tengah-tengah array.
Saya perlu tolak untuk sampai ke lokasi asal
tempat pertama awal sebelum saya boleh membebaskan.
Jadi, di sini adalah satu contoh yang lebih terlibat.
Dalam kes ini, kita memperuntukkan 7 watak-watak dalam pelbagai watak.
>> Dan dalam kes ini apa yang kita lakukan ialah kita menggelung lebih 6 pertama mereka,
dan kita menetapkan mereka ke Z.
Jadi, bagi int i = 0, i> 6, i + +,
Jadi, penunjuk + i hanya akan memberikan kita, dalam hal ini,
penunjuk, penunjuk +1, penunjuk 2, penunjuk +3, dan sebagainya dan sebagainya di dalam gelung.
Apa yang ia akan lakukan ialah ia mendapat alamat itu, dereferences untuk mendapatkan nilai,
dan perubahan yang nilai kepada seorang Z.
Kemudian pada akhir ingat ini adalah rentetan, kan?
Semua rentetan mempunyai berakhir dengan watak nol menamatkan.
Jadi, apa yang saya lakukan adalah dalam pointer 6 saya meletakkan watak null masuk
Dan kini apa yang saya pada dasarnya lakukan di sini sedang melaksanakan printf untuk rentetan, kan?
>> Jadi, bilakah printf sekarang apabila ia sampai ke penghujung rentetan?
Apabila ia mencecah watak nol menamatkan.
Jadi, dalam kes ini, asal mata penunjuk saya ke permulaan array ini.
Saya hendak mencetak aksara pertama keluar. Saya bergerak lebih daripada satu.
Saya mencetak watak yang keluar. Saya memindahkan ia lebih.
Dan saya terus melakukan ini sehingga saya mencapai akhir.
Dan kini penunjuk akhir * akan dereference ini dan mendapatkan watak nol menamatkan kembali.
Dan begitu gelung sementara saya berjalan hanya apabila nilai yang tidak adalah watak nol menamatkan.
Jadi, sekarang saya keluar daripada gelung ini.
Dan jadi jika saya tolakkan 6 daripada penunjuk ini,
Saya kembali semua cara untuk permulaan.
Ingat, saya lakukan ini kerana saya perlu pergi ke permulaan dalam usaha untuk membebaskan.
>> Jadi, saya tahu yang banyak. Adakah terdapat apa-apa soalan?
Tolong, ya?
[Pelajar tidak bijaksana yang soalan]
Anda boleh mengatakan bahawa lebih kuat? Maaf.
[Pelajar] Pada slaid terakhir sejurus sebelum anda membebaskan penunjuk,
di mana anda sebenarnya mengubah nilai penunjuk?
[Yusuf] Jadi, di sini. >> [Pelajar] Oh, okay.
[Yusuf] Jadi, saya mempunyai penunjuk tolak tolak, hak,
yang bergerak perkara siapa yang menyangka, dan kemudian saya membebaskannya,
kerana penunjuk ini mempunyai untuk menunjukkan permulaan array.
[Pelajar] Tetapi itu tidak akan diperlukan telah anda berhenti selepas garis itu.
[Joseph] Jadi, jika saya telah berhenti selepas ini, ini akan dianggap kebocoran memori,
kerana saya tidak menjalankan percuma.
[Pelajar] I [] yang tidak bijaksana yang selepas tiga baris pertama di mana anda mempunyai penunjuk 1 [difahami].
[Yusuf] Uh-huh. Jadi, apa soalan di sana?
Maaf. Tidak, tidak. Pergi, pergi, sila.
[Pelajar] Jadi, anda tidak mengubah nilai petunjuk.
Anda tidak akan mempunyai untuk melakukan penunjuk tolak tolak.
[Yusuf] Ya, betul-betul.
Jadi, apabila saya melakukan +1 penunjuk dan pointer 2,
Saya tidak melakukan penunjuk sama pointer 1.
Jadi, penunjuk hanya tetap menunjuk pada permulaan array.
Ia hanya apabila saya melakukan ditambah ditambah bahawa ia menetapkan nilai kembali di dalam penunjuk,
bahawa ia sebenarnya bergerak ini bersama-sama.
Semua hak.
Lebih banyak soalan?
>> Sekali lagi, jika ini adalah jenis hangat, ini akan dibincangkan dalam sesi.
Tanya rakan-rakan mengajar anda tentang ia, dan kita boleh menjawab soalan-soalan di akhir.
Dan biasanya kita tidak suka untuk melakukan perkara ini tolak.
Ini memerlukan saya mengesan berapa banyak saya telah diimbangi dalam array.
Jadi, secara umum, ini adalah hanya untuk menjelaskan bagaimana kerja-kerja aritmetik penunjuk.
Tetapi apa yang kita biasanya suka lakukan ialah kita suka untuk membuat salinan penunjuk,
dan kemudian kita akan menggunakan salinan itu apabila kita sedang bergerak dalam string.
Jadi, dalam kes ini anda menggunakan salinan untuk mencetak rentetan keseluruhan,
tetapi kita tidak perlu untuk melakukan seperti penunjuk tolak 6 atau menjejaki berapa banyak kita bergerak dalam hal ini,
hanya kerana kita tahu bahawa titik asal kita masih menunjukkan permulaan senarai
dan semua yang kita diubah adalah salinan ini.
Jadi, secara umum, mengubah salinan penunjuk asal anda.
Jangan cuba untuk menyelesaikan seperti - Don 't mengubah salinan asal.
Cuba untuk mengubah hanya salinan asal anda.
Jadi, anda notis apabila kita lulus rentetan ke printf
anda tidak perlu untuk meletakkan bintang di hadapan seperti yang kita lakukan dengan semua dereferences lain, kan?
Jadi, jika anda mencetak% keseluruhan rentetan s menjangka adalah alamat,
dan dalam kes ini penunjuk atau dalam kes ini seperti pelbagai watak.
>> Watak, char * s, dan array adalah perkara yang sama.
Pointer adalah untuk watak-watak, dan barisan watak adalah perkara yang sama.
Dan sebagainya, semua yang perlu kita lakukan adalah lulus dalam penunjuk.
Kami tidak mempunyai untuk lulus dalam * seperti penunjuk atau apa-apa seperti itu.
Jadi, tatasusunan dan petunjuk adalah perkara yang sama.
Apabila anda melakukan sesuatu seperti x [y] di sini untuk pelbagai,
apa yang ia lakukan di bawah hud ia berkata, okay, ia adalah pelbagai watak,
jadi ia adalah penunjuk.
Dan sebagainya x adalah perkara yang sama,
dan sebagainya apa yang ia adalah ia menambah y x,
yang merupakan perkara yang sama seperti bergerak ke hadapan dalam ingatan yang banyak.
Dan sekarang x + y memberikan kita beberapa jenis alamat,
dan kita dereference alamat atau ikut anak panah
mana bahawa lokasi dalam ingatan dan kita mendapat nilai daripada lokasi tersebut dalam ingatan.
Jadi, jadi kedua-dua adalah perkara yang sama.
Ia hanya gula sintaktik.
Mereka melakukan perkara yang sama. Mereka hanya syntactics yang berbeza antara satu sama lain.
>> Jadi, apa yang boleh pergi salah dengan petunjuk? Seperti, banyak. Okay. Jadi, perkara-perkara buruk.
Beberapa perkara-perkara buruk yang boleh anda lakukan tidak memeriksa jika panggilan malloc anda kembali batal, betul-betul?
Dalam kes ini, saya meminta sistem untuk memberikan saya - apakah nombor itu?
Seperti 2 bilion kali 4, kerana saiz integer adalah 4 bait.
Saya meminta untuk seperti 8000000000 bait.
Sudah tentu komputer saya tidak akan dapat memberikan saya yang kembali memori banyak.
Dan kita tidak memeriksa jika ini adalah batal, jadi apabila kita cuba untuk dereference di sana -
mengikuti anak panah ke mana ia akan - kita tidak mempunyai memori yang.
Ini adalah apa yang kita panggil dereferencing penunjuk nol.
Dan ini pada dasarnya menyebabkan anda segfault.
Ini adalah salah satu cara anda boleh segfault.
Lain-lain perkara-perkara buruk yang boleh anda lakukan - oh baik.
Itu dereferencing penunjuk nol. Okay.
Lain-lain perkara yang buruk - baik, untuk menetapkan bahawa anda hanya meletakkan cek di sana
yang memeriksa sama ada penunjuk adalah batal
dan keluar daripada program ini jika ia berlaku bahawa malloc mengembalikan penunjuk nol.
Itulah komik xkcd. Orang faham sekarang. Susun.
>> Jadi, ingatan. Dan saya pergi lebih ini.
Kami memanggil malloc dalam gelung, tetapi setiap kali kita memanggil malloc
kita kehilangan mengesan di mana penunjuk ini menunjuk ke,
kerana kita sedang clobbering ia.
Jadi, panggilan awal untuk malloc memberi saya ingatan di sini.
Penunjuk penunjuk saya ini.
Sekarang, saya tidak membebaskan, jadi sekarang saya panggil malloc lagi.
Kini ia menunjuk ke sini. Sekarang ingatan saya menunjuk ke sini.
Menunjuk ke sini. Menunjuk ke sini.
Tetapi saya telah hilang mengesan alamat semua memori di sini bahawa saya memperuntukkan.
Dan sebagainya sekarang saya tidak mempunyai apa-apa rujukan kepada mereka lagi.
Jadi, saya tidak boleh membebaskan mereka di luar gelung ini.
Dan sebagainya untuk menetapkan sesuatu seperti ini,
jika anda lupa untuk memori percuma dan anda mendapatkan ini kebocoran memori,
Anda perlu untuk membebaskan memori di dalam gelung ini sebaik sahaja anda selesai dengan ia.
Nah, ini adalah apa yang berlaku. Saya tahu banyak anda benci ini.
Tetapi sekarang - Yay! Anda akan mendapat seperti 44.000 kilobytes.
Jadi, anda bebas pada akhir gelung,
dan perkara yang berlaku hanya membebaskan memori setiap masa.
Pada asasnya, program anda tidak mempunyai kebocoran memori lagi.
>> Dan kini sesuatu yang lain yang boleh anda lakukan adalah membebaskan beberapa memori yang anda telah diminta untuk dua kali.
Dalam kes ini, anda malloc sesuatu, anda menukar nilainya.
Anda bebas sekali kerana anda berkata anda telah dilakukan dengan ia.
Tetapi kemudian kita dibebaskan sekali lagi.
Ini adalah sesuatu yang cukup buruk.
Ia tidak akan pada mulanya segfault,
tetapi selepas itu apa ini tidak berganda membebaskan ini merosakkan struktur timbunan anda,
dan anda akan belajar sedikit lebih lanjut mengenai ini jika anda memilih untuk mengambil kelas seperti CS61.
Tetapi pada dasarnya selepas manakala komputer anda akan terkeliru
tentang apa lokasi ingatan di mana dan di mana ia disimpan -
di mana data disimpan dalam ingatan.
Dan supaya membebaskan penunjuk dua kali adalah satu perkara yang buruk yang anda tidak mahu lakukan.
>> Perkara-perkara lain yang boleh pergi salah tidak menggunakan sizeof.
Jadi, dalam kes ini anda malloc 8 bait,
dan itulah perkara yang sama sebagai dua integer, betul-betul?
Jadi, itulah selamat, tetapi ia?
Nah, sebagai Lucas bercakap tentang seni bina yang berbeza,
integer panjang yang berbeza.
Jadi, pada perkakas yang anda gunakan, integer adalah kira-kira 4 bait,
tetapi pada sistem lain mereka mungkin 8 bait atau mereka mungkin 16 bait.
Jadi, jika saya hanya menggunakan nombor ini di sini,
program ini mungkin bekerja pada perkakas,
tetapi ia tidak akan memperuntukkan memori yang cukup pada sistem lain.
Dalam kes ini, ini adalah apa pengendali sizeof digunakan untuk.
Apabila kita panggil sizeof (int), apa ini tidak
ia memberikan kita saiz integer pada sistem bahawa program ini berjalan.
Jadi, dalam kes ini, sizeof (int) akan kembali 4 pada sesuatu seperti perkakas,
dan sekarang ini kehendak 4 * 2, iaitu 8,
yang hanya jumlah ruang yang perlu bagi dua integer.
Pada sistem yang berbeza, jika int adalah seperti 16 bait atau 8 bait,
ia hanya akan kembali bait yang cukup untuk menyimpan sejumlah itu.
>> Dan akhirnya, structs.
Jadi, jika anda mahu untuk menyimpan papan Sudoku dalam ingatan, bagaimana kita mungkin melakukan ini?
Anda mungkin berfikir seperti pembolehubah untuk perkara yang pertama,
pembolehubah bagi perkara yang kedua, ubah bagi perkara ketiga,
pembolehubah untuk perkara keempat - buruk, betul?
Jadi, salah satu penambahbaikan anda boleh membuat di atas ini adalah untuk membuat pelbagai 9 x 9.
Itu baik, tetapi bagaimana jika anda mahu untuk mengaitkan perkara-perkara lain dengan lembaga Sudoku
seperti apa kesukaran lembaga,
atau, sebagai contoh, apa yang skor anda, atau berapa banyak masa ia diambil anda untuk menyelesaikan lembaga ini?
Nah, apa yang anda boleh lakukan ialah anda boleh membuat struct.
Apa yang saya pada dasarnya mengatakan saya menentukan struktur ini di sini,
dan saya menentukan suatu lembaga Sudoku yang terdiri daripada lembaga yang 9 x 9.
>> Dan apa yang ia mempunyai ia mempunyai petunjuk untuk nama peringkat.
Ia juga mempunyai x dan y, yang koordinat di mana saya sekarang.
Ia juga telah menghabiskan masa [difahami], dan ia mempunyai jumlah langkah-langkah yang saya telah dimasukkan setakat.
Dan sebagainya dalam kes ini, saya boleh mengumpulkan sekumpulan keseluruhan data ke hanya satu struktur
bukannya mempunyai ia seperti terbang di sekitar seperti pembolehubah yang berbeza
bahawa saya tidak boleh benar-benar menjejaki.
Dan ini membolehkan kita mempunyai hanya sintaks bagus untuk jenis rujukan perkara yang berbeza di dalam struct ini.
Saya hanya boleh melakukan board.board, dan saya mendapat lembaga Sudoku kembali.
Board.level, saya mendapat bagaimana sukar ia adalah.
Board.x dan board.y memberi saya koordinat di mana saya mungkin dalam lembaga.
Dan jadi saya mengakses apa yang kita panggil bidang dalam struct.
Ini mentakrifkan sudokuBoard, yang merupakan jenis yang saya ada.
Dan sekarang kita berada di sini. Saya mempunyai pembolehubah yang dipanggil "lembaga" sudokuBoard jenis.
Dan jadi sekarang saya boleh mengakses semua bidang yang membentuk struktur ini di sini.
>> Sebarang pertanyaan tentang structs? Ya?
[Pelajar] Untuk int x, y, anda mengisytiharkan kedua-duanya dalam satu baris? >> [Yusuf] Uh-huh.
[Pelajar] Jadi, boleh anda hanya berbuat demikian dengan mereka semua?
Seperti di x, y koma kali bahawa jumlah?
[Yusuf] Ya, anda pasti dapat berbuat demikian, tetapi sebab saya meletakkan x dan y pada baris yang sama -
dan persoalannya ialah mengapa kita hanya boleh melakukan ini pada baris yang sama?
Mengapa tidak kita hanya meletakkan semua ini pada baris yang sama adalah
x dan y adalah berkaitan antara satu sama lain,
dan ini hanya stylistically lebih tepat, dalam erti kata,
kerana ia kumpulan dua perkara pada baris yang sama
yang jenis seperti berkaitan dengan perkara yang sama.
Dan saya hanya berpecah ini selain. Ia hanya satu perkara yang gaya.
Ia berfungsi membuat tiada perbezaan jua.
Mana-mana soalan-soalan lain pada structs?
Anda boleh menentukan Pokédex dengan struct.
Satu Pokémon mempunyai nombor dan ia mempunyai surat, pemilik, jenis.
Dan kemudian jika anda mempunyai pelbagai Pokémon, anda boleh membuat sehingga Pokédex, betul-betul?
Okay, sejuk. Jadi, soalan pada structs. Mereka adalah berkaitan dengan structs.
>> Akhirnya, GDB. Apakah GDB membiarkan anda lakukan? Ia membolehkan anda debug program anda.
Dan jika anda telah tidak digunakan GDB, saya akan disyorkan menonton pendek
dan hanya akan atas apa yang GDB adalah, bagaimana anda bekerja dengan, bagaimana anda mungkin menggunakan,
dan menguji program.
Dan jadi apa GDB membolehkan anda lakukan adalah ia membolehkan menjedakan [difahami] program anda
dan garis praktikal.
Sebagai contoh, saya mahu pelaksanaan jeda pada seperti baris 3 program saya,
dan semasa saya di baris 3 saya boleh mencetak keluar semua nilai-nilai yang terdapat.
Dan supaya apa yang kita panggil seperti berhenti dalam satu barisan
kita panggil ini meletakkan titik putus di garis yang
dan kemudian kita boleh mencetak pembolehubah di negeri program pada masa itu.
>> Kita boleh kemudian dari sana melangkah melalui program garis-oleh-line.
Dan kemudian kita boleh melihat negeri timbunan pada masa itu.
Dan sebagainya untuk menggunakan GDB, apa yang kita lakukan adalah kita panggil dilafaz pada fail C,
tetapi kita perlu untuk lulus ia bendera ggdb-.
Dan apabila kita sudah selesai dengan itu kita hanya menjalankan Pra-Pemasangan pada fail output yang terhasil.
Dan supaya anda mendapat beberapa jisim seperti teks seperti ini,
tetapi benar-benar semua yang anda perlu lakukan adalah menaip arahan pada permulaan.
Cuti utama meletakkan titik putus di utama.
Senarai 400 menyenaraikan baris kod sekitar 400 baris.
Dan sebagainya dalam kes ini anda hanya boleh melihat sekeliling dan berkata, oh,
Saya mahu untuk menetapkan titik putus di garisan 397, yang adalah baris ini,
dan kemudian program anda berjalan ke dalam langkah itu dan ia akan pecah.
Ia akan berhenti seketika di sana, dan anda boleh mencetak, sebagai contoh, nilai rendah atau tinggi.
Dan sebagainya terdapat sekumpulan arahan yang anda perlu tahu,
dan tayangan gambar ini akan naik di laman web,
jadi jika anda hanya mahu untuk rujukan ini atau ingin meletakkan mereka pada kepingan anda menipu, berasa bebas.
>> Sejuk. Itu adalah Kuiz Kajian 0, dan kita akan melekat di sekeliling jika anda mempunyai sebarang soalan.
Semua hak.
>> [Tepukan]
>> [CS50.TV]