[Powered by Google Translate] [Minggu 6, Sambungan]
[David J. Malan] [Universiti Harvard]
[Ini adalah CS50.] [CS50.TV]
Ini adalah CS50 dan ini adalah akhir 6 minggu.
Jadi CS50x, salah satu kursus pertama Harvard yang terlibat dalam inisiatif EDX
memang memulakan kerjaya pada hari Isnin lalu.
Jika anda ingin mendapatkan gambaran tentang apa yang orang lain di Internet
kini mengikuti bersama-sama dengan, anda boleh menuju kepada x.cs50.net.
Itu akan mengarahkan anda ke tempat yang sesuai pada edx.org,
yang mana ini dan kursus-kursus lain dari MIT dan Berkeley kini hidup.
Anda perlu mendaftar untuk akaun, anda akan mendapati bahawa bahan adalah sebahagian besarnya sama
kerana anda telah semester ini, walaupun beberapa minggu ditangguhkan, kerana kita akan mendapat segala-galanya yang bersedia.
Tetapi apa yang pelajar di CS50x sekarang akan melihat adalah satu antara muka agak seperti yang satu ini.
Ini, misalnya, adalah Zamyla memimpin Walkthrough untuk menetapkan masalah 0.
Apabila pembalakan di untuk edx.org, seorang pelajar CS50x melihat pelbagai perkara
anda akan mengharapkan untuk melihat dalam kursus: kuliah untuk Isnin,
ceramah untuk Rabu, seluar pendek, pelbagai set masalah, walkthroughs, PDF.
Di samping itu, seperti yang anda lihat di sini mesin terjemahan,
transkrip bahasa Inggeris ke dalam bahasa Cina, Jepun, Sepanyol, Itali,
dan sekumpulan seluruh bahasa-bahasa lain yang pastinya akan menjadi tidak sempurna
seperti yang kita melancarkan mereka keluar programatik menggunakan sesuatu yang dipanggil API,
atau antara muka pemprograman aplikasi, dari Google
yang membolehkan kita untuk menukar bahasa Inggeris kepada bahasa-bahasa lain.
Tetapi terima kasih kepada semangat indah beberapa sukarelawan yang seratus-campur,
orang rawak di Internet yang telah sila ditawarkan untuk terlibat
dalam projek ini, kita secara beransur-ansur akan meningkatkan kualiti terjemahan mereka
dengan mempunyai manusia membetulkan kesilapan yang komputer kita telah dibuat.
>> Jadi ia bertukar keluar kita telah beberapa ramai pelajar muncul pada hari Isnin daripada kita mulanya dijangka.
Malah, kini CS50x mempunyai 100,000 orang yang mengikuti bersama-sama di rumah.
Jadi menyedari anda semua adalah sebahagian daripada ini kelas sulung membuat kursus ini dalam bidang sains komputer
pendidikan lebih amnya, lebih meluas, diakses.
Dan realitinya kini, dengan beberapa kursus-kursus dalam talian secara besar-besaran,
mereka semua bermula dengan nombor-nombor yang sangat tinggi, seperti yang kita seolah-olah telah dilakukan di sini.
Tetapi matlamat, akhirnya, untuk CS50x adalah benar-benar untuk mendapatkan seberapa banyak orang ke garisan penamat mungkin.
Oleh reka bentuk, CS50x akan ditawarkan daripada ini hari Isnin yang lepas
sepanjang jalan melalui April 15, 2013, supaya orang yang mempunyai komitmen sekolah di tempat lain,
kerja, keluarga, konflik lain dan sebagainya, mempunyai fleksibiliti sedikit lebih
dengan yang menyelam ke dalam kursus ini, yang mencukupi untuk mengatakan,
agak ambitiously dilakukan jika hanya sepanjang hanya tiga bulan pada semester biasa.
Tetapi pelajar-pelajar ini akan menangani set masalah yang sama, melihat kandungan yang sama,
mempunyai akses ke seluar sama dan sebagainya.
Jadi sedar bahawa kita semua adalah benar-benar bersama-sama ini.
Dan salah satu daripada matlamat akhir CS50x tidak hanya untuk mendapatkan seberapa banyak orang
ke garisan penamat dan memberi mereka ini pemahaman barunya sains komputer
dan pengaturcaraan tetapi juga mempunyai mereka mempunyai pengalaman ini bersama.
Salah satu ciri-ciri yang menentukan 50 di kampus, kita berharap,
telah jenis ini pengalaman perkauman, untuk lebih baik atau untuk lebih teruk, kadang-kadang,
tetapi mempunyai orang-orang ini untuk berpaling ke kiri dan ke kanan,
pejabat jam dan dan hackathon dan saksama.
Ia agak sukar untuk berbuat demikian dalam orang dengan orang dalam talian,
tetapi CS50x akan membuat kesimpulan pada bulan April dengan pertama kalinya Ekspo CS50,
yang akan menjadi adaptasi talian idea kami saksama
di mana beribu-ribu pelajar semua akan dijemput untuk mengemukakan 1 - 2-minit video,
sama ada screencast projek akhir mereka atau video mereka melambai hello
dan bercakap tentang projek mereka dan demoing ia,
banyak seperti pendahulunya anda telah dilakukan di sini di kampus adil,
supaya menjelang akhir semester ini, harapan untuk mempunyai pameran global
projek akhir pelajar CS50x ', sama seperti itu yang menanti anda Disember ini di sini di kampus.
Jadi lanjut mengenai bahawa dalam bulan-bulan akan datang.
>> Dengan 100,000 pelajar, walaupun, datang keperluan untuk CA lebih sedikit.
Memandangkan bahawa anda semua terik laluan di sini dan mengambil CS50
beberapa minggu terlebih dahulu melepaskan bahan ini kepada penduduk di EDX,
sedar kita akan suka untuk melibatkan seberapa banyak pelajar kita sendiri yang mungkin dalam inisiatif ini,
semasa semester serta musim sejuk ini dan ini musim bunga akan datang.
Jadi, jika anda mahu untuk mendapatkan terlibat dalam CS50x,
terutamanya menyertai dalam pada Bincangkan CS50x, versi EDX CS50 Bincangkan,
yang ramai daripada anda telah menggunakan di kampus, papan buletin dalam talian,
sila lakukan menuju ke URL yang, marilah kita tahu siapa anda,
kerana kita suka untuk membina satu pasukan pelajar dan kakitangan dan fakulti sama
di kampus yang hanya bermain bersama-sama dan membantu keluar.
Dan apabila mereka melihat satu soalan yang biasa kepada mereka,
anda mendengar seorang pelajar melaporkan pepijat beberapa tempat di luar sana di beberapa negara di Internet,
dan bahawa cincin loceng kerana anda juga mempunyai bahawa isu yang sama
dalam d-dewan sedikit masa lalu, diharapkan maka anda boleh berbunyi di dalam dan berkongsi pengalaman anda sendiri.
Jadi jangan mengambil bahagian jika anda mahu.
>> Kursus sains komputer di Universiti Harvard mempunyai sedikit tradisi,
CS50 kalangan mereka, mempunyai beberapa pakaian, beberapa pakaian, yang anda boleh memakai bangganya
pada akhir semester ini, berkata agak bangganya bahawa anda selesai CS50
dan mengambil CS50 dan sebagainya, dan kami sentiasa cuba untuk melibatkan pelajar
dalam proses ini seberapa banyak yang mungkin, di mana kami menjemput,
sekitar masa ini semester, pelajar untuk mengemukakan reka bentuk
menggunakan Photoshop, atau apa jua alat pilihan anda ingin menggunakan
jika anda seorang pereka, untuk mengemukakan reka bentuk untuk T-shirt dan sweatshirts
dan payung dan bandanas sedikit untuk anjing kita kini mempunyai dan sebagainya.
Dan segala-galanya adalah kemudian - pemenang setiap tahun kemudiannya dipamerkan
di laman web kursus di store.cs50.net.
Semuanya dijual pada kos di sana, tetapi laman web hanya berjalan sendiri
dan membolehkan orang ramai untuk memilih warna dan reka bentuk yang mereka suka.
Jadi saya fikir kita hanya akan berkongsi beberapa reka bentuk tahun lepas
yang berada di laman web selain dari yang satu ini di sini, yang merupakan tradisi tahunan.
"Setiap Hari Saya SEG Faultn" adalah salah satu daripada penghujahan tahun lepas,
yang masih ada di sana untuk alumni.
Kami mempunyai satu ini, "CS50, Ditubuhkan 1989."
Salah satu Bowdens kami, Rob, adalah sangat popular pada tahun lepas.
"Pasukan Bowden" dilahirkan, reka bentuk ini telah dikemukakan, antara penjual utama.
Seperti yang satu ini di sini. Ramai orang mempunyai "Demam Bowden" mengikut log jualan.
Sedarlah bahawa kini boleh menjadi reka bentuk anda di sana, di Internet.
Maklumat lanjut mengenai ini dalam masalah seterusnya set datang.
>> Salah satu alat yang lebih: anda mempunyai beberapa pendedahan dan diharapkan kini
beberapa pengalaman hands-on dengan GDB,
yang, sememangnya, penyahpepijat dan membolehkan anda untuk memanipulasi
program anda pada tahap yang agak rendah, melakukan apa jenis perkara?
Apakah GDB membiarkan anda lakukan?
Yeah? Berikan saya sesuatu. [Pelajar jawapan, difahami]
Baik. Langkah ke fungsi, supaya anda tidak hanya perlu menaip menjalankan
dan mempunyai program tamparan menerusi keseluruhannya, mencetak perkara output standard.
Sebaliknya, anda boleh melangkah melalui talian ia demi baris, sama ada menaip seterusnya
untuk pergi baris demi baris demi baris atau langkah untuk menyelam ke dalam fungsi, biasanya satu yang anda menulis.
Apa lagi yang tidak GDB membiarkan anda lakukan? Yeah? [Pelajar jawapan, difahami]
Cetak pembolehubah. Jadi jika anda mahu untuk melakukan introspeksi sedikit dalam program anda
tanpa perlu mengambil jalan untuk menulis pernyataan printf seluruh tempat,
anda hanya boleh mencetak pembolehubah atau memaparkan pembolehubah.
Apa lagi yang anda boleh lakukan dengan penyahpepijat seperti GDB?
[Pelajar jawapan, difahami]
Tepat sekali. Anda boleh menetapkan titik putus, anda boleh mengatakan pelaksanaan rehat
pada fungsi utama atau fungsi foo.
Anda boleh mengatakan pelaksanaan berehat di garisan 123.
Dan titik putus adalah satu teknik yang benar-benar kuat
kerana jika anda mempunyai pemahaman yang umum di mana masalah anda
mungkin, anda tidak perlu membuang masa melangkah melalui keseluruhan program ini.
Anda asasnya boleh melompat di sana dan kemudian mula menaip -
melangkah melaluinya dengan langkah atau seterusnya atau sebagainya.
Tetapi tangkapan dengan sesuatu seperti GDB adalah bahawa ia membantu anda, manusia,
mencari masalah anda dan mencari pepijat anda.
Ia tidak semestinya mencari mereka begitu banyak untuk anda.
>> Jadi kita memperkenalkan style50 hari lain, yang merupakan alat baris arahan pendek
yang cuba untuk menyesuaikan dgn mode kod anda sedikit lebih bersih daripada anda, manusia, mungkin perlu dilakukan.
Tetapi itu juga, adalah benar-benar hanya satu perkara yang estetik.
Tetapi ternyata ada alat ini lain dipanggil Valgrind yang adalah sedikit lebih batin untuk digunakan.
Output adalah atrociously samar pada pandangan pertama.
Tetapi ia adalah hebat berguna, terutama sekarang bahawa kita berada di bahagian istilah
di mana anda mula menggunakan malloc dan peruntukan memori dinamik.
Perkara yang boleh pergi benar-benar, benar-benar salah dengan cepat.
Kerana jika anda lupa untuk membebaskan memori anda, atau anda dereference beberapa penunjuk NULL,
atau anda dereference beberapa penunjuk sampah, apa yang biasanya gejala yang keputusan?
Seg bersalah. Dan anda mendapat fail ini teras bilangan beberapa kilobait atau megabait
yang mewakili negeri memori program anda apabila ia terhempas,
tetapi program anda akhirnya seg kesilapan, kesalahan segmentasi,
yang bermaksud sesuatu yang buruk berlaku hampir sentiasa berkaitan
kepada kesilapan yang berkaitan dengan ingatan bahawa anda membuat suatu tempat.
Jadi Valgrind membantu anda mencari perkara-perkara seperti ini.
Ia adalah satu alat yang anda menjalankan, seperti GDB, selepas anda telah disusun program anda,
tetapi bukannya menjalankan program anda secara langsung, anda menjalankan Valgrind
dan anda lulus program anda, sama seperti anda lakukan dengan GDB.
Kini, penggunaan, untuk mendapatkan jenis pengeluaran terbaik,
sedikit panjang, jadi di sana di atas skrin anda akan melihat Valgrind-v.
"V" hampir universal bermakna lantung apabila anda menggunakan program komputer Linux.
Jadi ia bermakna meludah keluar lebih banyak data daripada anda mungkin secara lalai.
"- Kebocoran periksa = penuh." Ini hanya mengatakan cek semua kebocoran memori yang mungkin,
kesilapan yang saya mungkin telah dibuat. Ini juga, adalah satu paradigma yang biasa dengan program-program Linux.
Secara umumnya, jika anda mempunyai hujah baris arahan yang "suis",
yang sepatutnya untuk mengubah tingkah laku program ini, dan ia adalah surat tunggal,
ia-v, tetapi jika itu dihidupkan, hanya dengan reka bentuk pengaturcara,
perkataan penuh atau siri perkataan, hujah baris arahan bermula dengan.
Ini adalah hanya konvensyen manusia, tetapi anda akan melihat mereka semakin.
Dan kemudian, akhirnya, "a.out" adalah nama sewenang-wenangnya untuk program dalam contoh ini tertentu.
Dan di sini adalah beberapa output wakil.
>> Sebelum kita melihat apa yang mungkin bermakna, biarlah saya pergi ke coretan kod di sini.
Dan biarlah saya bergerak ini keluar daripada cara itu, akan datang,
dan mari kita melihat memory.c, yang ini contoh ringkas di sini.
Jadi dalam program ini, izinkan saya mengezum masuk pada fungsi dan soalan.
Kami mempunyai fungsi utama yang memanggil fungsi, f,
dan kemudian apakah f meneruskan untuk berbuat demikian, dalam Bahasa Inggeris sedikit teknikal?
Apakah f meneruskan lakukan?
Bagaimana pula saya akan bermula dengan garis 20, dan lokasi bintang tidak kira,
tetapi saya hanya akan menjadi konsisten sini dengan kuliah terakhir.
Apa garis 20 adakah untuk kita? Pada sebelah kiri. Kami akan memecahkan ia menurunkan lagi.
Int * x: apakah yang lakukan?
Okay. Ia mengisytiharkan penunjuk, dan sekarang mari kita menjadi lebih teknikal.
Apakah ia bermakna, sangat kukuh, untuk mengisytiharkan penunjuk? Orang lain?
Yeah? [Pelajar jawapan, difahami] Terlalu jauh.
Jadi anda membaca untuk sebelah kanan tanda yang sama.
Mari kita memberi tumpuan hanya pada sebelah kiri, hanya pada int * x.
Ini tidak "mengisytiharkan" penunjuk, tetapi sekarang mari menyelam di lebih mendalam kepada takrif itu.
Apakah yang kukuh, teknikal maksudkan? Yeah?
[Pelajar jawapan, difahami]
Okay. Ia bersedia untuk menyelamatkan alamat dalam ingatan.
Baik. Dan mari kita mengambil langkah ini satu lagi, ia mengisytiharkan pembolehubah, x, yang 32-bit.
Dan saya tahu ia adalah 32 bit kerana -?
Ia bukan kerana ia adalah int, kerana ia adalah satu penunjuk dalam kes ini.
Kebetulan bahawa ia adalah satu dan sama dengan int,
tetapi hakikat bahawa terdapat bintang di sana bermakna ini adalah penunjuk
dan perkakas, seperti dengan komputer banyak, tetapi tidak semua, petunjuk adalah 32 bit.
Pada perkakasan yang lebih moden seperti Mac terbaru, PC terbaru, anda mungkin mempunyai petunjuk 64-bit,
tetapi dalam perkakas, perkara-perkara ini adalah 32-bit.
Jadi kita akan menyeragamkan pada itu. Lebih kukuh, cerita pergi seperti berikut:
Kami "mengisytiharkan" penunjuk; apakah itu bermakna?
Kami bersedia untuk menyimpan alamat memori.
Apa maksudnya?
Kami mencipta pembolehubah x dipanggil yang mengambil sehingga 32 bit
yang tidak lama lagi akan menyimpan alamat integer.
Dan itulah mungkin kira-kira sebagai tepat kerana kita boleh mendapatkan.
Ia adalah denda bergerak ke hadapan untuk memudahkan dunia dan hanya mengatakan mengisytiharkan penunjuk dipanggil x.
Isytiharkan penunjuk, tetapi menyedari dan memahami apa yang sebenarnya berlaku di
walaupun dalam beberapa watak.
>> Sekarang, yang satu ini hampir sedikit lebih mudah, walaupun ia adalah satu ungkapan yang lebih lama.
Jadi apa ini lakukan, yang diketengahkan kini: "malloc (10 * sizeof (int));" Ya?
[Pelajar jawapan, difahami]
Baik. Dan saya akan mengambil ia di sana. Ia memperuntukkan sebahagian memori selama sepuluh integer.
Dan sekarang mari kita menyelam di sedikit lebih mendalam, ia memperuntukkan sebahagian memori selama sepuluh integer.
Apa yang malloc kemudian kembali?
Alamat bahawa sebahagian, atau, lebih kukuh, alamat bait pertama sebahagian yang.
Bagaimana pula saya, pengaturcara, tahu di mana bahawa sebahagian berakhir memori?
Saya tahu bahawa ia adalah berdampingan. Malloc, mengikut definisi, akan memberi anda sebahagian memori yang berdampingan.
Tiada jurang di dalamnya. Anda mempunyai akses kepada bait dalam setiap Sebahagian bahawa,
kembali ke belakang ke belakang, tetapi bagaimana saya tahu di mana akhir ini sebahagian daripada memori?
Apabila anda menggunakan malloc? [Pelajar jawapan, difahami].
Anda tidak lakukan. Anda perlu ingat.
Saya perlu ingat bahawa saya menggunakan nilai 10, dan saya tidak seolah-olah telah dilakukan di sini.
Tetapi tanggungjawab sepenuhnya kepada saya. Strlen, yang kita telah menjadi sedikit bergantung pada tali,
hanya berfungsi kerana konvensyen ini mempunyai \ 0
atau ini aksara khas nul, NUL, pada akhir rentetan.
Yang tidak tahan untuk hanya ketulan sewenang-wenangnya memori.
Ia terpulang kepada anda. Jadi line 20, maka, memperuntukkan sebahagian memori
yang boleh menyimpan sepuluh integer, dan ia menyimpan alamat bait pertama
Sebahagian yang memori dalam x ubah dipanggil.
Ergo, yang merupakan penunjuk. Jadi line 21, malangnya, adalah satu kesilapan.
Tetapi pertama, apa yang ia lakukan? Ia mengatakan kedai di lokasi 10, 0 diindeks,
sebahagian memori yang dikenali sebagai x 0 nilai.
>> Jadi notis beberapa perkara yang berlaku.
Walaupun x adalah penunjuk, ingat dari beberapa minggu yang lalu
bahawa anda masih boleh menggunakan pelbagai gaya notasi kurungan persegi.
Kerana itulah sebenarnya trengkas notasi untuk aritmetik penunjuk yang lebih samar-cari.
di mana kita akan melakukan sesuatu seperti ini: Ambil x alamat, bergerak 10 tempat lebih,
kemudian pergi ke sana untuk apa sahaja alamat yang disimpan di lokasi tersebut.
Tetapi terus-terang, ini adalah hanya kejam untuk membaca dan mendapatkan selesa dengan.
Jadi dunia biasanya menggunakan kurungan persegi hanya kerana ia begitu lebih mesra manusia untuk membaca.
Tetapi itulah apa yang benar-benar berlaku di bawah hood;
x adalah alamat, tidak array, per se.
Jadi ini menyimpan 0 di lokasi 10 dalam x.
Mengapa ini buruk? Yeah?
[Pelajar jawapan, difahami] Tepat sekali.
Kami hanya memperuntukkan sepuluh ints, tetapi kita mengira dari 0 apabila pengaturcaraan dalam C,
jadi anda mempunyai akses kepada 0 10 1 2 3 4 5 6 7 8 9, tetapi tidak.
Jadi sama ada program ini akan kesalahan seg atau ia tidak.
Tetapi kita tidak benar-benar tahu; ini adalah jenis tingkah laku nondeterministic.
Ia benar-benar bergantung kepada sama ada kita mendapat bertuah.
Jika ia ternyata bahawa sistem operasi tidak keberatan jika saya menggunakan bahawa bait tambahan,
walaupun ia telah tidak diberikan kepada saya, program saya tidak mungkin kemalangan.
Ia adalah mentah, ia adalah kereta, tetapi anda mungkin tidak melihat gejala yang,
atau anda mungkin melihat ia hanya sekali-sekala.
Tetapi realitinya adalah bahawa pepijat adalah, sebenarnya, ada.
Dan ia adalah benar-benar bermasalah jika anda telah menulis satu program yang anda mahu betul,
bahawa anda telah dijual program yang orang menggunakan bahawa setiap sekali-sekala kemalangan
kerana, sudah tentu, ini tidak baik. Malah, jika anda mempunyai telefon Android atau iPhone
dan anda memuat turun aplikasi pada hari ini, jika anda pernah mempunyai app hanya berhenti,
tiba-tiba ia hilang, yang hampir selalu disebabkan beberapa isu yang berkaitan dengan ingatan,
mana pengaturcara diskrukan sehingga dan dereferenced penunjuk
bahawa dia tidak harus mempunyai, dan hasil daripada IOS atau Android adalah hanya membunuh program ini sama sekali
bukannya kelakuan risiko undefined atau beberapa jenis kompromi keselamatan.
>> Ada satu pepijat lain dalam program ini selain yang satu ini.
Apa lagi yang telah saya diskrukan sehingga dalam program ini?
Saya tidak diamalkan apa yang saya telah diajar. Yeah?
[Pelajar jawapan, difahami].
Saya telah tidak dibebaskan memori. Jadi kemestian sekarang
telah menjadi bila-bila masa anda memanggil malloc, anda mesti menghubungi percuma apabila anda telah selesai menggunakan memori yang.
Kini, apabila saya mahu untuk membebaskan memori ini?
Mungkin andaian ini baris pertama adalah betul, saya mahu untuk melakukannya di sini.
Kerana saya tidak boleh, misalnya, adakah ia turun di sini. Mengapa?
Hanya keluar skop. Jadi, walaupun kita sedang bercakap mengenai petunjuk,
ini adalah seminggu 2 atau 3 isu, di mana x ialah hanya dalam skop di dalam pendakap kerinting yang mana ia telah diisytiharkan.
Jadi, anda pasti tidak dapat membebaskan sana. Satunya peluang saya untuk membebaskan ia adalah kira-kira selepas baris 21.
Ini adalah satu program yang agak mudah, ia adalah agak mudah sebaik sahaja anda jenis dibalut fikiran anda
sekitar apa program lakukan, mana kesilapan.
Dan walaupun jika anda tidak melihat ia pada mulanya, mudah-mudahan ia sedikit jelas sekarang
bahawa kesilapan-kesilapan ini cukup mudah diselesaikan dan mudah dibuat.
Tetapi apabila program adalah lebih daripada 12 baris panjang, ia adalah 50 baris panjang, 100 barisan panjang,
berjalan melalui talian kod anda demi baris, pemikiran melalui logiknya,
adalah mungkin tetapi tidak terutamanya yang menyeronokkan untuk dilakukan, sentiasa mencari pepijat,
dan ia juga sukar untuk berbuat demikian, dan itulah sebabnya alat seperti Valgrind wujud.
Biar saya pergi ke hadapan dan melakukan ini: izinkan saya membuka tetingkap terminal saya,
dan biarlah saya bukan hanya menjalankan memori, kerana memori nampaknya baik.
Saya mendapat bertuah. Melangkah ke bait yang tambahan pada akhir array
nampaknya tidak menjadi terlalu bermasalah.
Tetapi biarlah saya, walau bagaimanapun, melakukan pemeriksaan kewarasan, yang hanya bermakna untuk memeriksa
sama ada atau tidak ini adalah sebenarnya betul.
>> Jadi mari kita buat valgrind-v - bocor menyemak = penuh,
dan kemudian nama program dalam kes ini adalah ingatan, tidak a.out.
Jadi biarlah saya pergi ke hadapan dan melakukan ini. Tekan Enter.
Dear Allah. Ini adalah output, dan ini adalah apa yang saya dirujuk kepada awal.
Tetapi, jika anda belajar untuk membaca melalui semua karut di sini,
kebanyakan ini hanya output diagnostik yang tidak yang menarik.
Apa mata anda benar-benar mahu mencari apa-apa sebutan ralat atau tidak sah.
Perkataan yang mencadangkan masalah.
Dan sesungguhnya, mari kita lihat apa yang berlaku salah turun di sini.
Saya mempunyai ringkasan beberapa jenis, "digunakan pada keluar:. 40 bait dalam 1 blok"
Saya tidak benar-benar pasti apa yang blok lagi, tetapi 40 bytes
sebenarnya berasa seperti saya dapat memikirkan mana yang datang dari.
40 bait. Mengapa 40 bait dalam penggunaan di bahagian keluar?
Dan lebih khusus, jika kita tatal ke sini,
mengapa saya pasti kehilangan 40 bytes? Yeah?
[Pelajar jawapan, difahami] Perfect. Ya, sebenarnya.
Terdapat sepuluh integer, dan setiap orang adalah saiz 4, atau 32 bit,
jadi saya telah hilang tepat 40 bait kerana, seperti yang dicadangkan, saya telah tidak dipanggil percuma.
Itulah satu pepijat, dan sekarang mari kita melihat ke bawah sedikit lagi dan lihat sebelah ini,
"Tidak sah menulis 4 saiz." Sekarang apakah ini?
Alamat ini dinyatakan apa notasi asas, nampaknya?
Ini adalah perenambelasan, dan bila-bila masa anda melihat nombor yang bermula dengan 0x,
ia bermakna perenambelasan, yang kita lakukan perjalanan pulang, saya fikir, seksyen pset 0 soalan,
yang hanya melakukan satu latihan warmup, menukar perpuluhan hex binari dan sebagainya.
Perenambelasan, hanya dengan konvensyen manusia, biasanya digunakan untuk mewakili petunjuk
atau lebih amnya, alamat. Ia hanya konvensyen,
kerana ia sedikit lebih mudah untuk dibaca, ia adalah sedikit lebih padat daripada sesuatu seperti perpuluhan,
dan binari adalah sia-sia bagi kebanyakan manusia untuk menggunakan.
Jadi sekarang apa maknanya? Nah, ia kelihatan seperti ada menulis tidak sah
4 saiz on line 21 daripada memory.c.
Jadi mari kita kembali kepada 21 baris, dan sesungguhnya, di sini adalah bahawa menulis tidak sah.
Jadi Valgrind tidak akan benar-benar memegang tangan saya dan beritahu saya apa yang menetapkan,
tetapi ia mengesan bahawa saya melakukan sesuatu menulis tidak sah.
Saya menyentuh 4 bait bahawa saya tidak perlu, dan nampaknya itulah kerana,
kerana anda berkata, saya lakukan [10] bukan [9] maksima
atau [0] atau sesuatu di antara.
Dengan Valgrind, menyedari bila-bila masa anda sedang menulis program
yang menggunakan petunjuk dan menggunakan memori, dan malloc lebih khusus,
pasti masuk ke dalam tabiat berjalan ini lama
tetapi sangat mudah disalin dan ditampal perintah Valgrind
untuk melihat jika terdapat beberapa kesilapan di sana.
Dan ia akan menjadi hangat setiap kali anda melihat output,
tetapi hanya menghurai melalui visual semua output dan lihat jika anda lihat menyebut kesilapan
atau amaran atau tidak sah atau hilang.
Mana-mana perkataan yang bunyi seperti anda diskrukan sehingga tempat.
Jadi sedar bahawa alat baru dalam Kit anda.
>> Sekarang pada hari Isnin, kami mempunyai sekumpulan keseluruhan orang datang sini
dan mewakili tanggapan senarai berkaitan.
Dan kita memperkenalkan senarai yang dikaitkan sebagai penyelesaian kepada apa masalah?
Yeah? [Pelajar jawapan, difahami].
Tatasusunan tidak boleh mempunyai memori ditambah kepada mereka.
Jika anda memperuntukkan pelbagai bersaiz 10, itu semua yang anda dapatkan.
Anda boleh memanggil fungsi seperti realloc jika anda pada mulanya dipanggil malloc,
dan yang boleh cuba untuk berkembang array jika ada ruang ke arah akhir ia
bahawa tidak ada orang lain menggunakan, dan jika tidak, ia hanya akan mencari anda sebahagian besar di tempat lain.
Tetapi maka ia akan menyalin semua bytes mereka ke array baru.
Ini bunyi seperti penyelesaian yang sangat betul.
Mengapa ini tidak menarik?
Maksud saya ia berfungsi, manusia telah menyelesaikan masalah ini.
Mengapa kita perlu untuk menyelesaikan ia pada hari Isnin dengan senarai yang dikaitkan? Yeah?
[Jawapan Pelajar, difahami] Ia boleh mengambil masa yang lama.
Malah, bila-bila masa yang anda memanggil malloc atau realloc atau calloc, yang lagi satu sama lain,
bila-bila masa anda, program ini, bercakap kepada sistem operasi,
anda cenderung untuk memperlahankan program turun.
Dan jika anda melakukan ini jenis perkara dalam gelung, anda benar-benar melambatkan perkara turun.
Anda tidak akan notis ini mudah "hello dunia" jenis program,
tetapi dalam program-program yang lebih besar, meminta sistem operasi sekali lagi dan sekali lagi untuk ingatan
atau memberikan ia kembali lagi dan lagi cenderung untuk tidak menjadi satu perkara yang baik.
Plus, ia hanya jenis intelektual - ia adalah sisa lengkap masa.
Mengapa memperuntukkan memori lebih dan lebih, risiko menyalin segala-galanya ke array baru,
jika anda mempunyai alternatif yang membolehkan anda memperuntukkan memori hanya sebagai banyak seperti yang anda sebenarnya perlu?
Jadi ada plus dan kemudaratan di sini.
Salah satu plus sekarang adalah bahawa kita mempunyai dinamisme.
Tidak kira di mana ketulan memori yang bebas,
Saya hanya boleh menyusun mencipta serbuk roti melalui petunjuk
rentetan senarai keseluruhan saya dikaitkan bersama-sama.
Tetapi saya membayar sekurang-kurangnya satu harga.
>> Apa yang saya perlu untuk berputus asa dalam mendapatkan dikaitkan senarai?
Yeah? [Pelajar jawapan, difahami].
Anda perlu memori lebih. Sekarang saya perlu ruang bagi petunjuk,
dan dalam kes senarai ini sangat mudah dikaitkan
yang hanya cuba untuk menyimpan integer, yang 4 bait, kita terus katakan
baik, penunjuk 4 bait, jadi sekarang saya telah benar-benar dua kali ganda
jumlah memori yang saya perlukan hanya untuk menyimpan senarai ini.
Tetapi sekali lagi, ini adalah tradeoff yang berterusan dalam bidang sains komputer
antara masa dan ruang dan pembangunan, usaha dan sumber-sumber lain.
Apa lagi Kelemahan menggunakan senarai yang dikaitkan? Yeah?
[Pelajar jawapan, difahami]
Baik. Tidak seperti mudah untuk akses. Kita tidak lagi boleh memanfaatkan
minggu 0 prinsip seperti membahagi dan menakluk.
Dan lebih khusus, carian dedua. Kerana walaupun kita manusia
boleh melihat kira-kira di mana pertengahan senarai ini adalah,
komputer hanya tahu bahawa senarai ini dikaitkan bermula di alamat dipanggil 1.
Dan itulah 0x123 atau sesuatu seperti itu.
Dan satu-satunya cara program ini boleh mencari elemen tengah
sebenarnya adalah untuk mencari senarai keseluruhan.
Dan walaupun itu, ia benar-benar mempunyai untuk mencari senarai keseluruhan kerana
walaupun sekali anda mencapai elemen tengah dengan mengikuti petunjuk,
anda, program ini, tidak mempunyai idea berapa lama senarai ini, berpotensi,
sehingga anda memukul akhir ia, dan bagaimana anda tahu programatik
bahawa anda berada di akhir senarai dikaitkan?
Ada penunjuk khas NULL, jadi lagi, konvensyen.
Bukannya menggunakan penunjuk ini, kita pasti tidak mahu ia menjadi beberapa nilai sampah
menunjukkan dari pentas tempat, kita mahu ia menjadi tangan ke bawah, NULL,
supaya kita mempunyai perhentian ini dalam struktur data ini supaya kita tahu di mana ia berakhir.
>> Bagaimana jika kita ingin memanipulasi ini?
Kami melakukan kebanyakan ini visual, dan dengan manusia,
tetapi apa yang jika kita mahu melakukan kemasukan?
Jadi senarai asal adalah 9, 17, 20, 22, 29, 34.
Bagaimana jika kita kemudian mahu ruang malloc untuk 55 nombor, nod untuk ia,
dan kemudian kita mahu untuk memasukkan 55 ke dalam senarai hanya seperti yang kita lakukan pada hari Isnin?
Bagaimana kita melakukan ini? Nah, Anita datang dan dia asasnya berjalan senarai.
Beliau memulakan pada unsur pertama, maka seterusnya, seterusnya, seterusnya, seterusnya, seterusnya.
Akhirnya melanda kiri sepanjang jalan turun
dan menyedari oh, ini adalah NULL. Jadi apa manipulasi penunjuk yang perlu dilakukan?
Orang yang berada di akhir, nombor 34, yang diperlukan tangan kirinya dibangkitkan
untuk menunjukkan pada usia 55 tahun, 55 diperlukan lengan kiri mereka menunjuk ke menjadi NULL terminator baru. Selesai.
Cukup mudah untuk memasukkan 55 ke dalam senarai diisih.
Dan bagaimana ini mungkin kelihatan?
>> Biar saya pergi ke hadapan dan membuka beberapa contoh kod di sini.
Saya akan membuka gedit, dan biarlah saya membuka dua fail pertama.
Satu adalah list1.h, dan biarlah saya hanya mengingatkan bahawa ini adalah sebahagian kod
bahawa kita digunakan untuk mewakili nod.
Nod A mempunyai kedua-dua int dipanggil n dan penunjuk dipanggil seterusnya bahawa hanya mata untuk perkara yang seterusnya dalam senarai.
Yang kini dalam fail. H. Mengapa?
Ada konvensyen ini, dan kami tidak mengambil kesempatan ini sejumlah besar diri,
tetapi orang yang menulis fungsi printf dan lain-lain
memberikan sebagai hadiah kepada dunia semua fungsi-fungsi dengan menulis fail dipanggil stdio.h.
Dan kemudian ada string.h, dan kemudian ada map.h, dan ada semua ini h fail
bahawa anda mungkin telah melihat atau digunakan sepanjang jangka yang ditulis oleh orang lain.
Biasanya dalam mereka. Fail h adalah perkara-perkara sahaja seperti typedefs
atau pengisytiharan jenis adat atau pengisytiharan pemalar.
Anda tidak meletakkan pelaksanaan fungsi 'dalam fail header.
Anda meletakkan, sebaliknya, hanya prototaip mereka.
Anda meletakkan perkara yang anda ingin berkongsi dengan dunia apa yang mereka perlukan
dalam usaha untuk menyusun kod mereka. Jadi hanya untuk masuk ke dalam tabiat ini,
kami mengambil keputusan untuk melakukan perkara yang sama. Tidak banyak di list1.h,
tetapi kita telah meletakkan sesuatu yang mungkin menarik minat kepada orang-orang di dunia
yang mahu menggunakan pelaksanaan senarai berpaut kami.
Sekarang, list1.c, saya tidak akan pergi melalui perkara ini keseluruhan
kerana ia agak panjang, program ini, tetapi mari kita berlari ia sebenar cepat di prompt.
Izinkan saya menyusun Senarai1, izinkan saya kemudian berjalan Senarai1, dan apa yang anda akan lihat adalah
kita telah simulasi program mudah sedikit di sini
yang akan membolehkan saya untuk menambah dan membuang nombor ke senarai.
Jadi biarlah saya pergi ke hadapan dan taipkan 3 bagi 3 pilihan menu.
Saya mahu untuk memasukkan nombor - mari kita buat nombor pertama, yang adalah 9,
dan sekarang saya diberitahu senarai kini 9.
Biar saya pergi ke hadapan dan melakukan kemasukan lain, jadi saya melanda pilihan menu 3.
Apakah nombor yang saya mahu untuk memasukkan? 17.
Enter. Dan saya akan melakukan hanya satu lagi.
Biar saya memasukkan nombor 22.
Jadi kita mempunyai permulaan senarai dikaitkan bahawa kita mempunyai dalam bentuk slaid seketika lalu.
Bagaimana kemasukan ini sebenarnya berlaku?
Malah, 22 kini di akhir senarai.
Jadi cerita kita memberitahu di atas pentas pada hari Isnin dan recapped tadi
sebenarnya mesti berlaku dalam kod.
Mari kita lihat. Biarkan saya tatal ke bawah dalam fail ini.
Kami akan menyembunyikan beberapa fungsi,
tetapi kita akan pergi ke, berkata, fungsi insert.
>> Mari kita lihat bagaimana kita pergi tentang memasukkan nod baru ke dalam senarai ini dikaitkan.
Di manakah senarai diisytiharkan? Nah, mari kita tatal sepanjang jalan sehingga di atas,
dan notis bahawa senarai saya dikaitkan asasnya adalah diisytiharkan sebagai penunjuk tunggal yang mulanya NULL.
Jadi saya menggunakan pembolehubah global di sini, yang secara umum kita telah ajarannya menentang
kerana ia membuatkan kod anda kemas sedikit untuk mengekalkan,
ia adalah jenis malas, biasanya, tetapi ia tidak malas dan ia tidak salah dan ia tidak buruk
jika tujuan program anda dalam kehidupan adalah untuk mensimulasikan satu senarai berpaut.
Yang betul-betul apa yang kita lakukan.
Jadi, bukannya mengisytiharkan ini utama dan kemudian perlu lulus untuk setiap fungsi
kita telah ditulis dalam program ini, kita bukannya sedar oh, mari kita hanya membuat ia global
kerana keseluruhan tujuan program ini adalah untuk menunjukkan satu dan hanya satu senarai dikaitkan.
Jadi yang merasakan okay. Berikut adalah prototaip saya, dan kita tidak akan pergi melalui semua ini,
tetapi saya menulis fungsi padam, fungsi mencari, fungsi insert, dan fungsi traverse.
Tetapi mari kita kini kembali turun kepada fungsi memasukkan
dan lihat bagaimana satu ini bekerja di sini.
Sisipan adalah on-line - di sini kita pergi.
Memasukkan. Jadi ia tidak mengambil apa-apa hujah, kerana kita hendak bertanya
dalam pengguna fungsi ini untuk bilangan mereka mahu masukkan.
Tetapi pertama, kita bersedia untuk memberi mereka ruang.
Ini adalah jenis copy dan paste dari contoh lain.
Dalam kes itu, kita telah memperuntukkan int, masa ini kita memperuntukkan nod.
Saya tidak ingat berapa banyak bait nod, tetapi itulah denda.
Sizeof boleh memahami bahawa bagi saya.
Dan mengapa saya memeriksa NULL di baris 120?
Apa yang boleh pergi salah di 119 baris? Yeah?
[Pelajar jawapan, difahami]
Baik. Hanya boleh menjadi kes bahawa saya telah diminta untuk memori yang terlalu banyak
atau sesuatu yang salah dan sistem operasi tidak mempunyai bait yang cukup untuk memberi saya,
jadi ia isyarat sebanyak dengan mengembalikan NULL, dan jika saya tidak mendaftar untuk itu
dan saya hanya membuta tuli meneruskan untuk menggunakan alamat kembali, ia boleh menjadi NULL.
Ia boleh menjadi beberapa nilai yang tidak diketahui; bukan satu perkara yang baik kecuali saya -
sebenarnya tidak akan menjadi nilai yang tidak diketahui. Ia boleh menjadi NULL, jadi saya tidak mahu
penyalahgunaan dan risiko dereferencing ia.
Jika itu berlaku, saya hanya kembali dan kami akan berpura-pura seperti saya tidak mendapatkan kembali memori apa-apa pada semua.
>> Jika tidak, saya memberitahu pengguna memberikan saya nombor untuk memasukkan, saya menyeru kawan lama kami GetInt,
dan maka ini adalah sintaks baru kami memperkenalkan pada hari Isnin.
'Newptr-> n' bermakna mengambil alamat yang anda telah diberikan oleh malloc
yang mewakili bait pertama objek nod baru,
dan kemudian pergi ke bidang yang dipanggil n.
Satu soalan trivia sedikit: Ini adalah bersamaan kepada barisan lebih samar kod?
Bagaimana lagi boleh saya telah menulis ini? Mahu mengambil menikam?
[Pelajar jawapan, difahami]
Baik. Menggunakan n, tetapi ia tidak cukup semudah ini.
Apa yang saya perlu lakukan? [Pelajar jawapan, difahami]
Baik. Perlu saya lakukan newptr.n *.
Jadi ini mengatakan penunjuk baru jelas alamat. Mengapa?
Kerana ia telah dikembalikan oleh malloc. * Newptr mengatakan "pergi ke sana,"
dan kemudian apabila anda berada di sana, maka anda boleh menggunakan lebih biasa. n,
tetapi ini hanya kelihatan sedikit hodoh, terutamanya jika kita manusia akan
menarik petunjuk dengan anak panah sepanjang masa; dunia mempunyai standard pada notasi arrow ini,
yang tidak perkara yang sama.
Jadi, anda hanya gunakan -> notasi apabila perkara di sebelah kiri adalah penunjuk.
Jika tidak, jika ia adalah satu struct sebenar, menggunakan n..
Dan kemudian ini: Mengapa saya memulakan newptr> di sebelah null?
Kita tidak mahu tangan kiri tergantung kira akhir pentas.
Kami mahu ia menunjuk lurus ke bawah, yang bermaksud akhir senarai ini
berpotensi menjadi di nod ini, jadi kami lebih baik pastikan ia adalah NULL.
Dan, secara amnya, Memulakan pembolehubah anda atau ahli data anda dan structs
kepada sesuatu hanya amalan yang baik.
Hanya membiarkan sampah wujud dan terus wujud secara mendapat anda dalam kesusahan
jika anda terlupa untuk melakukan sesuatu yang kemudian.
>> Berikut adalah beberapa kes. Ini, sekali lagi, adalah fungsi memasukkan,
dan perkara pertama yang saya menyemak adalah jika pembolehubah dipanggil pertama kali,
bahawa pembolehubah global NULL, yang bermaksud tidak ada senarai dikaitkan.
Kami telah tidak dimasukkan apa-apa nombor, jadi ia adalah remeh untuk memasukkan nombor ini semasa
ke dalam senarai, kerana ia hanya tergolong pada permulaan senarai.
Jadi ini adalah apabila Anita hanya berdiri di sini sahaja, berpura-pura
tidak ada orang lain di sini di atas pentas sehingga kita memperuntukkan nod,
maka dia boleh mengangkat tangan beliau untuk kali pertama,
jika orang lain telah tampil di atas pentas selepas itu pada hari Isnin.
Sekarang di sini, ini adalah cek yang sedikit di mana saya katakan jika nilai nod baru n
<nilai n dalam nod pertama semasa,
yang bermakna terdapat senarai yang berkaitan itu bermula.
Terdapat sekurang-kurangnya satu nod dalam senarai, tetapi lelaki ini baru
kepunyaan sebelum ia, jadi kita perlu bergerak perkara di sekeliling.
Dalam erti kata lain, jika senarai telah bermula hanya dengan, katakan,
hanya nombor 17, itulah - sebenarnya, kita boleh melakukan ini dengan lebih jelas.
Jika kita mula cerita kita dengan penunjuk di sini dipanggil 1,
dan pada mulanya ia NULL, dan kita memasukkan nombor 9,
bilangan 9 jelas tergolong pada permulaan senarai.
Jadi mari kita berpura-pura kita hanya malloced alamat atau nombor 9 dan meletakkan ia di sini.
Jika pertama adalah 9 secara lalai, senario pertama kami membincangkan hanya bermaksud titik mari kita lelaki ini di sini,
meninggalkan ini sebagai NULL; kini kita mempunyai bilangan 9.
Nombor seterusnya yang kita mahu memasukkan ialah 17.
17 tergolong di sini, jadi kita akan perlu melakukan beberapa loncatan logik melalui ini.
Jadi mari kita sebaliknya, sebelum kita berbuat demikian, mari kita berpura-pura bahawa kita mahu memasukkan nombor 8.
>> Jadi hanya demi kemudahan ini, saya akan menarik di sini.
Tetapi ingat, malloc boleh meletakkan ia paling mana-mana.
Tetapi demi lukisan ini, saya akan meletakkan ia di sini.
Jadi berpura-pura saya hanya memperuntukkan nod bagi bilangan 8; ini adalah NULL secara lalai.
Apa yang kini telah berlaku? Beberapa perkara.
Kami membuat kesilapan ini di atas pentas pada hari Isnin di mana kita dikemaskini penunjuk seperti ini,
kemudian melakukan ini, dan kemudian kita mendakwa kami yatim orang lain di atas pentas.
Kerana anda can't - perintah operasi di sini adalah penting,
kerana sekarang kita telah hilang 9 ini nod yang hanya jenis terapung di angkasa.
Jadi ini bukanlah pendekatan yang betul pada hari Isnin.
Kita perlu melakukan sesuatu yang lain.
Keadaan dunia kelihatan seperti ini. Pada mulanya, 8 telah diperuntukkan.
Apa yang akan menjadi cara yang lebih baik memasukkan 8?
Sebaliknya mengemaskini penunjuk pertama ini, hanya mengemaskini satu ini di sini sebaliknya.
Jadi kita memerlukan baris kod yang akan menjadikan ini watak NULL
ke penunjuk sebenar yang menunjuk pada nod 9,
dan kemudian kita selamat boleh menukar pertama untuk menunjukkan pada lelaki ini di sini.
Sekarang kita mempunyai senarai, senarai yang berkaitan, daripada dua unsur.
Dan apakah ini sebenarnya kelihatan seperti sini?
Jika kita melihat kod, notis bahawa saya telah melakukan yang tepat.
Saya telah berkata newptr, dan dalam cerita ini, newptr menunjuk pada lelaki ini.
>> Jadi biarlah saya menarik satu lagi perkara, dan perlu saya telah meninggalkan bilik lebih sedikit untuk ini.
Jadi memaafkan lukisan sedikit kecil.
Lelaki ini dipanggil newptr.
Itu adalah pembolehubah kita mengisytiharkan beberapa baris sebelumnya, sejajar - hanya melebihi 25.
Dan ia menunjuk kepada 8. Jadi, apabila saya mengatakan newptr> di sebelah, yang bermakna pergi untuk struct
itu sedang menunjukkan di oleh newptr, jadi di sini kita, pergi ke sana.
Kemudian anak panah mengatakan mendapatkan bidang seterusnya, dan kemudian = mengatakan meletakkan apa nilai di sana?
Nilai yang pertama; apa nilai adalah pertama?
Pertama telah menunjuk pada nod ini, jadi yang bermakna ini kini perlu menunjukkan di nod ini.
Dalam erti kata lain, apa yang kelihatan walaupun keadaan huru-hara yang tidak masuk akal dengan tulisan tangan saya,
apa idea yang mudah hanya bergerak panah ini sekitar
diterjemahkan kepada kod dengan hanya pelapik yang satu ini.
Menyimpan apa yang pertama dalam bidang seterusnya dan kemudian mengemas apa yang sebenarnya adalah 1.
Mari kita pergi ke hadapan dan pantas ke hadapan melalui beberapa ini,
dan kelihatan hanya di sisipan ekor ini buat masa sekarang.
Katakan saya mendapat ke titik di mana saya mendapati bahawa bidang seterusnya nod beberapa NULL.
Dan pada ketika ini dalam cerita, terperinci bahawa saya glossing atas
adalah bahawa saya telah diperkenalkan penunjuk lain di sini di baris 142, penunjuk sebelumnya.
Pada asasnya, pada ketika ini dalam cerita, sekali senarai mendapat lama,
Saya jenis perlu berjalan dengan dua jari kerana jika saya pergi terlalu jauh,
ingat dalam senarai panjang tunggal, anda tidak boleh pergi ke belakang.
Jadi ini idea predptr jari kiri saya, dan newptr - tidak newptr.
Satu lagi penunjuk yang di sini adalah jari saya yang lain, dan saya hanya jenis berjalan senarai.
Itulah mengapa yang wujud. Tetapi mari kita hanya mempertimbangkan salah satu daripada kes-kes yang lebih mudah di sini.
Jika medan seterusnya bahawa penunjuk adalah NULL, apa implikasi logik?
Jika anda sedang menyeberangi senarai ini dan anda memukul penunjuk NULL?
Anda berada di akhir senarai, dan sebagainya kod kemudian melampirkan ini elemen tambahan
jenis intuitif akan mengambil nod yang seterusnya penunjuk adalah NULL,
jadi ini adalah kini NULL, dan mengubahnya, walaupun, untuk menjadi alamat nod baru.
Jadi kita hanya lukisan dalam kod anak panah yang kita menarik di atas pentas dengan mengangkat tangan kiri seseorang.
>> Dan kes yang saya akan melambai tangan saya di buat masa sekarang,
hanya kerana saya fikir ia adalah mudah untuk mendapatkan hilang apabila kita lakukan dalam jenis ini alam sekitar,
memeriksa kemasukan pada pertengahan senarai.
Tetapi hanya intuitif, apa yang perlu berlaku jika anda mahu untuk memikirkan
di mana beberapa beberapa tergolong di tengah-tengah adalah anda tidak perlu berjalan
dengan lebih daripada satu jari, lebih daripada satu penunjuk,
memikirkan di mana ia tergolong oleh semakan adalah elemen <satu semasa,
> Semasa, dan apabila anda mencari tempat itu,
maka anda perlu melakukan ini jenis permainan shell di mana anda menggerakkan petunjuk di sekeliling sangat berhati-hati.
Dan jawapan itu, jika anda ingin sebab melalui ini di rumah anda sendiri,
bisul hanya untuk kedua-dua baris kod, tetapi perintah orang-orang garisan adalah sangat penting.
Kerana jika anda menggugurkan tangan seseorang dan menaikkan orang lain dalam perintah itu salah,
sekali lagi, anda boleh berakhir sehingga anak yatim senarai.
Untuk meringkaskan lebih konsepnya, kemasukan di ekor adalah agak mudah.
Kemasukan di kepala juga agak mudah,
tetapi anda perlu untuk mengemaskini penunjuk tambahan masa ini
memerah nombor 5 ke dalam senarai di sini,
dan kemudian memasukkan di tengah-tengah melibatkan usaha lebih,
sangat berhati-hati memasukkan nombor 20 dalam lokasi yang betul,
yang berumur antara 17 dan 22.
Jadi, anda perlu melakukan sesuatu seperti mempunyai nod baru 20 mata kepada 22,
dan kemudian, penunjuk yang nod ini perlu dikemaskini terakhir?
Ia adalah 17, sebenarnya memasukkan ia.
Jadi sekali lagi, saya akan menangguhkan kod sebenar bagi pelaksanaan yang tertentu.
>> Pada pandangan pertama, ia sedikit hangat, tetapi ia adalah benar-benar hanya gelung tak terhingga
itu gelung, gelung, gelung, gelung, dan berbuka dengan seberapa segera seperti yang anda memukul penunjuk NULL,
di mana titik anda boleh melakukan kemasukan yang diperlukan.
Ini, maka, adalah wakil senarai kemasukan dikaitkan kod.
Itu adalah jenis banyak, dan ia berasa seperti kita telah menyelesaikan satu masalah,
tetapi kita telah memperkenalkan satu lain secara keseluruhan. Terus terang, kami telah menghabiskan semua masa ini
O besar dan Ω dan berjalan masa, cuba untuk menyelesaikan masalah dengan lebih cepat,
dan di sini kita mengambil langkah besar ke belakang, rasanya.
Dan lagi, jika matlamatnya adalah untuk menyimpan data,
rasanya Holy Grail, seperti yang kita berkata pada hari Isnin, benar-benar akan menjadi
untuk menyimpan perkara-perkara serta-merta.
>> Malah, menganggap bahawa kita melakukan senarai yang diketepikan dihubungkan untuk seketika
dan kita bukannya memperkenalkan tanggapan jadual.
Dan mari kita hanya berfikir jadual untuk seketika sebagai array.
Ini pelbagai dan kes ini di sini mempunyai kira-kira 26 unsur, 0 hingga 25,
dan menganggap bahawa anda memerlukan beberapa sebahagian simpanan untuk nama:
Alice dan Bob dan Charlie dan sebagainya.
Dan anda perlu beberapa struktur data untuk menyimpan nama-nama.
Nah, anda boleh menggunakan sesuatu seperti senarai berkaitan
dan anda boleh berjalan senarai memasukkan Alice sebelum Bob dan Charlie selepas Bob dan sebagainya.
Dan, sebenarnya, jika anda mahu untuk melihat kod seperti itu sebagai diketepikan,
tahu bahawa di list2.h, kita lakukan betul-betul bahawa.
Kami tidak akan pergi melalui kod ini, tetapi ini adalah satu varian contoh pertama
yang memperkenalkan satu struct lain kita telah melihat sebelum pelajar dipanggil,
dan kemudian apa yang ia sebenarnya menyimpan dalam senarai berpaut adalah penunjuk kepada struktur pelajar
bukannya mudah integer sedikit, n.
Jadi sedar ada kod sana yang melibatkan rentetan sebenar,
tetapi jika matlamat di tangan benar-benar kini adalah untuk menangani masalah kecekapan,
ia tidak akan menjadi baik jika kita diberi satu objek yang dipanggil Alice,
kita mahu meletakkan beliau ke lokasi yang betul dalam struktur data,
ia berasa seperti ia akan menjadi benar-benar baik untuk hanya meletakkan Alice,
yang namanya bermula dengan A, di lokasi pertama.
Dan Bob, yang namanya bermula dengan B, lokasi kedua.
Dengan pelbagai, atau mari kita mulakan ia memanggil jadual, jadual hash pada itu,
kita boleh melakukan yang tepat. Jika kita diberikan nama seperti Alice,
rentetan seperti Alice, di manakah anda meletakkan A-l-i-c-e?
Kita perlu hueristic. Kita perlu fungsi untuk mengambil beberapa input seperti Alice
dan kembali jawapan, "Letakkan Alice di lokasi ini."
Dan fungsi ini, ini kotak hitam, akan dipanggil fungsi hash.
>> Satu fungsi hash adalah sesuatu yang mengambil input, seperti "Alice",
dan pulangan kepada anda, biasanya, lokasi angka dalam beberapa struktur data mana Alice kepunyaan.
Dalam kes ini, fungsi hash kami harus agak mudah.
Fungsi hash kita harus mengatakan, jika anda diberikan "Alice", watak yang saya harus mengambil berat tentang?
Yang pertama. Jadi saya melihat [0], dan kemudian saya mengatakan jika [0] watak A, kembalikan nombor 0.
Jika ia adalah B, kembali 1. Jika C ia, kembali 2, dan sebagainya.
Semua indeks 0, dan yang akan membolehkan saya untuk memasukkan Alice dan kemudian Bob dan kemudian Charlie dan sebagainya
ke dalam struktur data ini. Tetapi ada masalah.
Bagaimana jika Anita datang bersama-sama lagi?
Di manakah kita meletakkan Anita? Namanya juga, bermula dengan huruf A,
dan ia merasakan seperti yang kita telah membuat keadaan kucar-kacir yang lebih besar daripada masalah ini.
Kami kini mempunyai kemasukan serta-merta, kemasukan pemalar masa, ke dalam struktur data
bukannya teruk kes-linear,
tetapi apa yang kita boleh lakukan dengan Anita dalam kes ini?
Apakah kedua-dua pilihan, benar-benar? Yeah?
[Pelajar jawapan, difahami] Okay, jadi kita boleh mempunyai dimensi lain.
Itulah baik. Jadi kita boleh membina perkara keluar dalam 3D seperti kita bercakap tentang secara lisan pada hari Isnin.
Kita boleh menambah akses lain di sini, tetapi menganggap bahawa tiada, saya cuba untuk menyimpan ini mudah.
Matlamat keseluruhan di sini adalah untuk mempunyai masa malar akses serta-merta,
supaya menambah kerumitan terlalu banyak.
Apakah pilihan lain apabila cuba untuk memasukkan Anita ke dalam struktur data ini? Yeah?
[Pelajar jawapan, difahami]. Jadi, kita boleh menggerakkan orang lain ke bawah,
seperti Charlie nudges turun Bob dan Alice, dan kemudian kita meletakkan Anita mana dia benar-benar mahu menjadi.
>> Sudah tentu, sekarang, terdapat kesan sampingan ini.
Ini struktur data mungkin berguna bukan kerana kita mahu untuk memasukkan orang sekali
tetapi kerana kita mahu untuk memeriksa jika ia berada di sana kemudian
jika kita ingin mencetak keluar semua nama dalam struktur data.
Kami akan melakukan sesuatu dengan data ini akhirnya.
Jadi sekarang kita telah jenis diskru lebih Alice, yang tidak lagi di mana dia sepatutnya.
Nor adalah Bob, mahupun Charlie.
Jadi mungkin ini tidak seperti idea yang baik.
Tetapi sesungguhnya, ini adalah satu pilihan. Kita boleh beralih semua orang turun,
atau palang pintu, Anita datang lewat untuk permainan, mengapa tidak kita hanya meletakkan Anita
bukan di sini, bukan di sini, bukan di sini, mari kita hanya meletakkan beliau sedikit lebih rendah dalam senarai.
Tetapi maka masalah ini mula diturunkan lagi.
Anda mungkin dapat mencari Alice serta-merta, berdasarkan nama pertama beliau.
Dan Bob serta-merta, dan Charlie. Tetapi kemudian anda mencari Anita,
dan anda lihat, hmm, Alice di jalan.
Baiklah, biar saya cek di bawah Alice. Bob bukan Anita.
Charlie tidak Anita. Oh, ada Anita.
Dan jika anda terus bahawa kereta api logik sepanjang jalan,
apa masa kes terburuk berjalan mencari atau memasukkan Anita ke dalam struktur data ini baru?
Ia O (n), betul-betul?
Kerana dalam kes terburuk, ada Alice, Bob, Charlie. . .
sepanjang jalan turun kepada seseorang yang bernama "Y", jadi hanya ada satu tempat ke kiri.
Syukurlah, kita tidak mempunyai satu dipanggil "Z", jadi kita meletakkan Anita di bahagian paling bawah.
>> Kami telah tidak benar-benar menyelesaikan masalah itu.
Jadi mungkin kita perlu untuk memperkenalkan dimensi ketiga.
Dan ternyata, jika kita memperkenalkan dimensi ketiga,
kita tidak boleh melakukan ini dengan sempurna, tetapi Holy Grail akan mendapat
kemasukan malar masa dan sisipan dinamik supaya
kita tidak perlu keras kod pelbagai saiz sebanyak 26.
Kita boleh memasukkan sebagai banyak nama seperti yang kita mahu, tetapi mari kita rehat 5-minit kami di sini
dan kemudian lakukan yang betul.
Semua hak. Saya menetapkan cerita sehingga cukup buatan sana
dengan memilih Alice dan Bob dan kemudian kemudian Charlie dan kemudian Anita,
yang namanya telah jelas akan bertembung dengan Alice.
Tetapi soalan yang kita berakhir pada hari Isnin dengan betapa kemungkinan ia
bahawa anda akan mendapat jenis-jenis perlanggaran? Dalam erti kata lain,
jika kita mula menggunakan struktur jadual, yang benar-benar hanya pelbagai,
dalam kes ini, sebanyak 26 lokasi,
apa jika input kami bukannya teragih seragam?
Ia bukan buatan Alice dan Bob dan Charlie dan David dan sebagainya mengikut abjad,
ia teragih seragam A hingga Z.
>> Mungkin kita hanya akan mendapat bernasib baik dan kita tidak akan mempunyai dua A atau dua B
dengan kebarangkalian yang sangat tinggi, tetapi sebagai seseorang menegaskan,
jika kita umum masalah ini dan tidak melakukan 0-25
tetapi, katakan, 0 hingga 364 atau 65, sering bilangan hari dalam tahun yang biasa,
dan bertanya soalan, "Apakah kebarangkalian bahawa dua daripada kita di dalam bilik ini mempunyai ulang tahun yang sama?"
Letakkan ia cara yang lain, apakah kebarangkalian bahawa dua daripada kita mempunyai nama yang bermula dengan A?
Jenis soalan adalah sama, tetapi ini ruang alamat,
ini ruang carian, adalah lebih besar dalam kes hari lahir,
kerana kita mempunyai begitu banyak hari lagi dalam tahun daripada huruf dalam abjad.
Apakah kebarangkalian perlanggaran?
Nah, kita boleh berfikir ini dengan memikirkan matematik dengan cara yang bertentangan.
Apakah kebarangkalian tiada perlanggaran?
Nah, ini ungkapan di sini mengatakan bahawa apa yang kebarangkalian
jika terdapat hanya satu orang di dalam bilik ini, bahawa mereka mempunyai harijadi yang unik?
Ia adalah 100%. Kerana jika terdapat hanya satu orang di dalam bilik,
atau ulang tahun beliau boleh menjadi apa-apa daripada 365 hari daripada tahun.
Jadi pilihan yang 365/365 memberikan saya nilai 1.
Jadi kebarangkalian dalam soalan pada masa ini adalah hanya 1.
Tetapi jika ada orang kedua di dalam bilik,
apakah kebarangkalian bahawa hari lahir mereka adalah berbeza?
Terdapat hanya 364 hari mungkin, mengabaikan tahun lompat,
untuk hari jadi mereka tidak bertembung dengan orang lain.
Jadi 364/365. Jika orang ketiga datang dalam, ia adalah 363/365, dan sebagainya.
Jadi kita menyimpan mendarabkan bersama pecahan ini, yang mendapat lebih kecil dan lebih kecil,
untuk memikirkan apakah kebarangkalian bahawa kita semua mempunyai tarikh lahir yang unik?
Tetapi maka kita boleh, sudah tentu, hanya mengambil jawapan itu dan flip sekeliling
dan melakukan 1 tolak semua itu, satu ungkapan yang akhirnya kita akan mendapat
jika anda ingat kembali buku-buku matematik anda, ia kelihatan sesuatu yang kecil seperti ini,
yang lebih mudah ditafsirkan grafik.
Dan ini grafik sini mempunyai pada paksi x bilangan hari lahir,
atau bilangan orang dengan hari lahir, dan pada paksi y adalah kebarangkalian perlawanan.
Dan apa ini mengatakan adalah bahawa jika anda mempunyai, katakan, walaupun,
mari kita memilih sesuatu seperti 22, 23.
Jika ada 22 atau 23 orang di dalam bilik,
kebarangkalian bahawa dua orang-orang yang sangat sedikit akan mempunyai hari lahir yang sama
sebenarnya tinggi super, combinatorially.
50% kemungkinan bahawa dalam kelas hanya 22 orang, seminar, praktikal,
2 orang-orang akan mempunyai hari lahir yang sama.
Kerana terdapat banyak cara di mana anda boleh mempunyai hari lahir yang sama.
Lebih buruk lagi, jika anda melihat di sebelah kanan carta,
pada masa anda mempunyai kelas dengan 58 orang pelajar di dalamnya,
kebarangkalian 2 orang yang mempunyai hari lahir adalah super, tinggi super, hampir 100%.
Sekarang, itulah jenis fakta yang menyeronokkan tentang kehidupan sebenar.
>> Tetapi implikasi, sekarang, untuk struktur data dan menyimpan maklumat
bermakna bahawa hanya menganggap anda mempunyai bagus, bersih, pengagihan seragam data
dan anda mempunyai pelbagai cukup besar untuk memuatkan sejambak perkara
tidak bermakna anda akan mendapatkan orang ramai di lokasi-lokasi yang unik.
Anda akan mempunyai perlanggaran. Jadi ini tanggapan hashing, kerana ia dipanggil,
mengambil input seperti "Alice" dan mengurut ia dalam beberapa cara
dan kemudian mendapatkan kembali jawapan seperti 0 atau 1 atau 2.
Mendapatkan kembali beberapa output dari fungsi yang dibelenggu oleh kebarangkalian ini perlanggaran.
Jadi bagaimana kita boleh mengendalikan orang-orang perlanggaran?
Nah, dalam satu kes, kita boleh mengambil idea yang telah dicadangkan.
Kami hanya boleh beralih ke bawah, atau mungkin, lebih sedikit semata-mata,
bukan daripada orang bergerak lagi, mari kita hanya bergerak Anita ke bawah tempat ada.
Jadi jika Alice adalah dalam 0, Bob adalah dalam 1, Charlie adalah dalam 2,
kita hanya akan meletakkan Anita di lokasi 3.
Dan ini adalah satu teknik dalam struktur data dipanggil linear menyelesaikan sesuatu.
Linear kerana anda hanya berjalan baris ini, dan anda jenis menyelesaikan sesuatu
bintik didapati dalam struktur data.
Sudah tentu, ini turun ke O (n).
Jika struktur data yang benar-benar penuh, terdapat 25 orang di dalamnya sudah,
dan kemudian Anita datang bersama-sama, dia akan berakhir pada apa yang akan menjadi lokasi Z, dan itulah denda.
Dia masih sesuai, dan kita boleh mencari beliau kemudian.
>> Tetapi ini adalah bertentangan dengan matlamat mempercepatkan perkara.
Jadi apa jika kita bukannya memperkenalkan dimensi ketiga?
Bahawa teknik secara umumnya dipanggil chaining berasingan, atau mempunyai rantaian.
Dan apa jadual hash kini, struktur jadual,
jadual anda hanya pelbagai petunjuk.
Tetapi apa yang mereka menunjukkan petunjuk untuk meneka apa?
Satu senarai yang dipautkan. Jadi apa jika kita mengambil yang terbaik daripada kedua-dua dunia ini?
Kami menggunakan tatasusunan untuk indeks awal
ke dalam struktur data supaya kita serta-merta boleh pergi ke [0] [1], [30] atau sebagainya,
tetapi supaya kita mempunyai beberapa fleksibiliti dan kita boleh memuatkan Anita dan Alice dan Adam
dan apa-apa nama lain,
kami bukannya membiarkan paksi lain berkembang secara sewenang-wenangnya.
Dan kita akhirnya, hari Isnin, mempunyai keupayaan yang ekspresif dengan senarai berpaut.
Kita boleh berkembang struktur data dengan sewenang-wenangnya.
Selain itu, kita hanya boleh membuat pelbagai besar 2-dimensi,
tetapi itu akan menjadi situasi yang buruk jika salah satu baris dalam pelbagai 2-dimensi
tidak cukup besar bagi orang tambahan yang namanya berlaku untuk memulakan dengan A.
Dubilah kita perlu mengagihkan semula besar 2-dimensi struktur
hanya kerana terdapat begitu ramai orang yang dinamakan sebagai A,
terutamanya apabila terdapat begitu beberapa orang bernama Z sesuatu.
Ia hanya akan menjadi satu struktur data yang sangat jarang.
Jadi ia tidak sesuai dengan apa-apa cara, tetapi sekarang kita sekurang-kurangnya mempunyai keupayaan
untuk segera mencari mana Alice atau Anita kepunyaan,
sekurang-kurangnya dari segi paksi menegak,
dan kemudian kita hanya perlu untuk membuat keputusan di mana untuk meletakkan Anita atau Alice dalam senarai ini dikaitkan.
Jika kita tidak mengambil berat tentang perkara sorting, berapa cepat kita boleh memasukkan Alice ke dalam struktur seperti ini?
Ia adalah masa yang berterusan. Kami indeks ke [0], dan jika terdapat tiada siapa,
Alice pergi pada permulaan senarai yang dikaitkan.
Tetapi itu bukan satu perjanjian yang besar. Kerana jika Anita kemudian datang bersama-sama
beberapa beberapa langkah kemudian, di mana tidak Anita tergolong?
Nah, [0]. Oop. Alice sudah dalam senarai itu dikaitkan.
>> Tetapi jika kita tidak mengambil berat tentang mengasingkan nama-nama ini,
kita hanya boleh bergerak Alice atas, memasukkan Anita, tetapi walaupun yang pemalar masa.
Walaupun terdapat Alice dan Adam dan semua ini lain nama,
ia tidak benar-benar beralih mereka secara fizikal. Mengapa?
Kerana kita hanya lakukan di sini dengan senarai yang berkaitan, siapa tahu nod ini adalah anyway?
Semua yang anda perlu lakukan adalah menggerakkan serbuk roti.
Gerakkan anak panah di sekeliling, anda tidak mempunyai fizikal bergerak sebarang data di sekeliling.
Jadi kita boleh memasukkan Anita, dalam kes itu, dengan serta-merta. Pemalar masa.
Jadi kita mempunyai masa malar lookup, dan masa malar memasukkan seseorang seperti Anita.
Tetapi jenis oversimplifying dunia.
Apakah jika kita kemudian mahu untuk mencari Alice?
Berapa banyak langkah-langkah yang akan mengambil?
[Pelajar jawapan, difahami]
Tepat sekali. Bilangan orang yang sebelum Alice dalam senarai berkaitan.
Jadi ia tidak cukup sempurna, kerana struktur data kami, sekali lagi, mempunyai akses ini menegak
dan kemudian ia mempunyai senarai ini berkaitan tergantung - sebenarnya, mari kita tidak menarik ia pelbagai.
Ia telah senarai ini dikaitkan tergantung kira ia yang kelihatan sesuatu yang sedikit seperti ini.
Tetapi masalahnya ialah jika Alice dan Adam dan semua ini lain nama
akhirnya lebih dan lebih di sana,
mencari seseorang yang boleh berakhir sehingga mengambil sekumpulan langkah-langkah,
bcause anda perlu merentasi senarai berpaut,
yang merupakan operasi linear.
Jadi benar-benar, maka, masa kemasukan akhirnya adalah O (n), di mana n adalah bilangan elemen dalam senarai.
Dibahagikan dengan, mari kita sewenang-wenangnya memanggil ia m, di mana m adalah bilangan senarai berkaitan
bahawa kita mempunyai dalam paksi ini menegak.
Dalam erti kata lain, jika kita benar-benar menganggap pengagihan seragam nama,
sama sekali tidak realistik. Terdapat jelas lebih beberapa surat daripada yang lain.
>> Tetapi jika kita menganggap seketika pengagihan seragam,
dan kami telah n rakyat keseluruhan, dan m rantaian jumlah
ada pada kita, maka panjang setiap rangkaian
agak hanya akan menjadi jumlah, n dibahagikan dengan bilangan rantai.
Jadi n / m. Tetapi di sini adalah di mana kita boleh menjadi semua pandai matematik.
m ialah pemalar, kerana ada beberapa yang tetap ini.
Anda akan mengisytiharkan array anda pada permulaan,
dan kita tidak saiz semula paksi menegak. Dengan definisi, yang tetap tetap.
Ia hanya paksi mendatar, jadi untuk bercakap, yang mengubah.
Jadi secara teknikal, ini adalah satu pemalar. Jadi sekarang, masa kemasukan
adalah cukup banyak O (n).
Supaya tidak merasa semua yang jauh lebih baik.
Tetapi apa kebenaran di sini? Nah, semua masa ini, untuk minggu,
kita telah mengatakan O (n ²). O (n), 2 x n ², - n, dibahagikan dengan 2. . . ECH.
Ia hanya ² n. Tetapi sekarang, dalam bahagian ini semester,
kita boleh mula bercakap tentang dunia sebenar lagi.
Dan n / m sememangnya lebih cepat daripada hanya n sahaja.
Jika anda mempunyai seribu nama, dan anda memecahkan mereka ke dalam baldi pelbagai
supaya anda mempunyai hanya sepuluh nama dalam setiap rangkaian,
benar-benar mencari sepuluh perkara akan menjadi lebih cepat daripada seribu perkara.
Dan sebagainya salah satu set masalah yang akan datang akan mencabar anda
untuk berfikir tentang tepat bahawa walaupun, yeah,
berasimptot dan matematik, ini masih hanya linear,
yang menghisap secara umum apabila cuba untuk mencari perkara-perkara.
Dalam realiti, ia akan menjadi lebih cepat daripada yang
kerana pembahagi ini.
Dan sebagainya ada lagi akan menjadi trade-off ini
dan ini konflik antara teori dan realiti,
dan salah satu tombol akan mula buka pada ketika ini dalam semester
adalah lebih daripada satu realiti seperti yang kita jenis bersedia untuk akhir semster,
seperti yang kita memperkenalkan dunia pengaturcaraan web,
mana benar-benar, prestasi akan untuk dikira kerana pengguna anda akan
mula merasa dan menghargai keputusan reka bentuk yang miskin.
>> Jadi bagaimana anda pergi tentang melaksanakan berkaitan - jadual hash dengan 31 unsur?
Dan contoh sebelumnya adalah sewenang-wenangnya tentang hari lahir.
Jika seseorang mempunyai hari lahir 1 Januari atau Februari 1, kami akan meletakkan mereka dalam baldi ini.
Jika ia Januari 2, February 2, 2 Mac, kami akan meletakkan mereka dalam baldi ini.
Itulah sebabnya ia adalah 31. Bagaimana anda mengisytiharkan jadual hash?
Ia boleh agak mudah, jadual * nod adalah nama saya sewenang-wenangnya untuk itu, [31].
Ini memberikan saya 31 petunjuk untuk nod,
dan yang membolehkan saya untuk mempunyai 31 petunjuk untuk senarai yang dikaitkan
walaupun orang-orang rantaian mulanya NULL.
Apa yang saya ingin meletakkan jika saya mahu menyimpan "Alice," "Bob", "Charlie"?
Nah, kita perlu untuk membalut perkara-perkara dalam struktur
kerana kita perlu Alice untuk menunjukkan kepada Bob, untuk menunjukkan Charlie, dan sebagainya.
Kita tidak boleh hanya mempunyai nama sahaja, jadi saya boleh mencipta satu struktur baru yang dipanggil nod sini.
>> Apakah nod sebenar? Apakah nod dalam senarai baru ini dikaitkan?
Perkara pertama, dipanggil perkataan, adalah untuk nama orang itu.
LENGTH, mungkin, berkaitan dengan panjang maksimum nama manusia,
apa yang, 20, 30, 40 watak-watak dalam kes sudut gila,
dan +1 adalah untuk apa? Ia hanya watak NULL tambahan, \ 0.
Jadi nod ini membungkus "sesuatu" di dalam sendirinya,
tetapi ia juga mengisytiharkan penunjuk dipanggil seterusnya
supaya kita dapat rantaian Bob Alice Charlie dan sebagainya.
Boleh NULL tetapi tidak semestinya perlu.
Sebarang pertanyaan mengenai jadual ini hash? Yeah?
[Pelajar bertanya soalan, difahami] Pelbagai - soalan yang baik.
Mengapa perkataan ini char dalam pelbagai bukannya hanya * char?
Dalam contoh ini agak sewenang-wenangnya, saya tidak mahu perlu mengambil jalan keluar
malloc untuk setiap nama asal.
Saya mahu mengisytiharkan jumlah maksimum memori untuk tali
supaya saya boleh menyalin ke dalam struktur Alice \ 0 dan tidak perlu berurusan dengan malloc dan bebas dan sebagainya.
Tetapi saya boleh melakukannya jika saya mahu menjadi lebih sedar penggunaan ruang. Soalan yang baik.
Jadi mari kita cuba untuk umum dari ini
dan memberi tumpuan baki hari ini pada struktur data lebih amnya
dan masalah-masalah lain yang kita boleh selesaikan dengan menggunakan asas-asas yang sama
walaupun struktur data sendiri mungkin berbeza dalam butir-butir mereka.
>> Jadi ia ternyata dalam bidang sains komputer, pokok-pokok yang sangat biasa.
Dan anda boleh berfikir apapun pokok seperti pokok keluarga,
di mana terdapat beberapa akar, beberapa ibu pemimpin keluarga atau bapa,
nenek atau datuk atau awal kembali,
yang mengalir di bawahnya adalah ibu dan ayah atau adik-beradik yang pelbagai atau sebagainya.
Jadi struktur pokok mempunyai nod dan ia mempunyai anak-anak,
biasanya 0 atau lebih kanak-kanak untuk setiap nod.
Dan beberapa istilah yang anda lihat dalam gambar ini di sini
adalah mana-mana anak-anak atau grandkids sedikit di tepi
yang tidak mempunyai anak panah yang berpunca daripada mereka,
mereka adalah daun kononnya, dan sesiapa sahaja di dalam
merupakan nod dalaman; anda boleh memanggilnya apa-apa sepanjang mereka baris.
Tetapi struktur ini adalah agak biasa. Satu ini sedikit sewenang-wenangnya.
Kami mempunyai seorang kanak-kanak di sebelah kiri, kita mempunyai tiga kanak-kanak di sebelah kanan,
dua kanak-kanak di bawah kiri.
Supaya kita boleh mempunyai pokok-pokok bersaiz berbeza-, tetapi jika kita mula untuk menyeragamkan perkara,
dan anda mungkin ingat ini dari Patrick video pada carian binari dari pendek sebelumnya
talian, gelintaran perduaan tidak perlu dilaksanakan dengan pelbagai
atau keping kertas di papan hitam.
Katakan yang anda ingin menyimpan nombor anda dalam struktur data yang lebih canggih.
Anda boleh membuat pokok seperti ini.
Anda boleh mempunyai nod yang diisytiharkan dalam C, dan nod yang boleh mempunyai sekurang-kurangnya dua unsur di dalamnya.
Salah satu adalah nombor yang anda mahu untuk menyimpan, dan lain-lain - baik, kita perlu satu lagi.
Yang lain adalah anak-anak itu.
Jadi di sini adalah satu lagi struktur data. Masa ini, nod ditakrifkan sebagai menyimpan nombor n
dan kemudian dua petunjuk; anak kiri dan kanak-kanak yang betul.
Dan mereka tidak sewenang-wenangnya. Apa yang menarik tentang pokok ini?
>> Apakah corak dalam bagaimana kita telah dibentangkan ini keluar atau bagaimana Patrick meletakkan ia keluar dalam video itu?
Ia adalah jenis jelas bahawa terdapat beberapa sorting berlaku di sini,
tetapi apa peraturan yang mudah? Yeah?
[Pelajar jawapan, difahami]
Sempurna. Jika anda pandang pada ini, anda melihat nombor kecil di sebelah kiri,
nombor besar di sebelah kiri, tetapi itulah benar bagi setiap nod.
Bagi setiap nod, anak kiri kurang daripada itu, dan anak kanan lebih besar daripada itu.
Apakah ini bermakna sekarang adalah jika saya ingin mencari struktur data untuk, katakan, bilangan 44,
Saya perlu bermula pada akar, kerana sebagai dengan semua ini struktur data yang lebih kompleks sekarang,
kita hanya mempunyai penunjuk kepada satu perkara, permulaan.
Dan dalam kes ini, permulaan adalah akar. Ia bukan akhir kiri,
ia adalah akar struktur ini. Jadi saya lihat di sini adalah 55, dan saya mencari untuk 44.
Arah mana saya mahu pergi?
Well, saya mahu pergi ke kiri, kerana jelas, ke kanan akan menjadi terlalu besar.
Jadi notis di sini, anda jenis konsep mencincang pokok dalam separuh
kerana anda pernah pergi ke sebelah kanan.
Jadi sekarang saya pergi dari 55 kepada 33. Ia adalah terlalu kecil nombor.
Saya mencari 44, tetapi sekarang saya tahu jika 44 adalah dalam pokok ini, saya boleh pergi jelas ke kanan.
Jadi sekali lagi, saya pemangkasan pokok di separuh.
Ia adalah cukup banyak sama konsepnya kepada buku telefon.
Ia adalah serupa dengan apa yang kita lakukan dengan kertas di papan hitam,
tetapi ia adalah struktur yang lebih canggih yang membolehkan kita untuk benar-benar melakukan
ini membahagi dan menakluk oleh reka bentuk algoritma,
dan pada hakikatnya, menyeberangi satu struktur seperti ini - Oop.
Menyeberangi struktur seperti ini, di mana ia hanya "pergi cara ini atau pergi dengan cara itu,"
ertinya semua bahawa kod yang bengkok fikiran anda pada mulanya apabila melaksanakan dalam seksyen
atau berjalan melalui di rumah, untuk carian binari, menggunakan rekursi atau lelaran,
ia adalah sakit di leher. Cari elemen tengah, kemudian melakukan pembundaran anda ke atas atau ke bawah.
>> Ada kecantikan ini kerana kita kini boleh menggunakan rekursi lagi,
tetapi lebih bersih. Malah, jika anda berada di nombor 55 tahun dan anda ingin mencari 44,
anda pergi kiri dalam kes ini, maka apa yang anda lakukan? Anda menjalankan algoritma yang sama yang tepat.
Anda menyemak nilai nod, maka anda pergi kiri atau kanan.
Kemudian anda memeriksa nilai nod, pergi kiri atau kanan.
Ini amat sesuai untuk rekursi.
Jadi walaupun pada masa lalu kita telah melakukan beberapa contoh yang agak sewenang-wenangnya melibatkan rekursi
yang tidak perlu menjadi rekursi, dengan stuctures data,
terutama pokok, ia adalah satu permohonan sempurna idea ini mengambil masalah,
mengecut, dan kemudian menyelesaikan jenis yang sama, tetapi lebih kecil, program.
>> Jadi ada satu lagi struktur data yang kita boleh memperkenalkan.
Yang satu ini direka pada pandangan pertama kelihatan samar, tetapi yang satu ini menakjubkan.
Jadi ini adalah satu struktur data dipanggil indone, indone, yang diwarisi dari semula perkataan,
yang tidak disebut semula cuba-Val, tetapi itulah apa yang dunia panggilan perkara-perkara ini. Cuba. T-r-i-e.
Ia merupakan struktur pokok beberapa jenis, tetapi setiap nod dalam indone
muncul untuk menjadi apa? Dan ini adalah agak mengelirukan kerana ia adalah jenis singkatan.
Tetapi ia kelihatan seperti setiap nod di indone ini adalah sebenarnya array.
Dan walaupun pengarang gambarajah ini telah tidak menunjukkan ia,
dalam kes ini, indone ini adalah struktur data yang tujuan dalam kehidupan adalah untuk menyimpan perkataan
seperti A-l-i-c-e atau B-o-b.
Dan cara di mana data ini kedai Alice dan Bob dan Charlie dan Anita dan sebagainya
ia menggunakan array mana untuk menyimpan Alice in indone satu,
kita mula pada nod akar yang kelihatan seperti array,
dan ia telah ditulis dalam notasi trengkas.
Penulis ditinggalkan ABCDEFG kerana tidak ada nama dengan itu.
Mereka hanya menunjukkan M dan P dan T, tetapi dalam kes ini,
mari kita bergerak jauh dari Alice dan Bob dan Charlie untuk beberapa nama-nama yang berada di sini.
Maxwell sebenarnya dalam gambar rajah ini.
Jadi bagaimana pula kedai pengarang M-x-w-e-l-l?
Beliau bermula pada nod akar, dan pergi ke [M], jadi kira-kira 13, lokasi ke-13 dalam array.
Kemudian dari situ, terdapat penunjuk.
Satu penunjuk yang membawa kepada pelbagai lain.
Dari situ penulis diindeks ke dalam tatasusunan yang di lokasi A, seperti yang digambarkan terdapat di sebelah kiri atas,
dan kemudian dia diikuti penunjuk bahawa kepada pelbagai yang lain,
dan pergi ke penunjuk di lokasi X.
Kemudian di lokasi array seterusnya W, E, L, L, dan sebagainya,
dan akhirnya, mari kita sebenarnya cuba untuk meletakkan gambar ini.
Apakah lihat nod seperti dalam kod?
Satu nod dalam indone mengandungi pelbagai petunjuk ke nodus lebih.
Tetapi ada juga mendapat menjadi beberapa jenis nilai boolean, sekurang-kurangnya dalam pelaksanaan ini.
Saya berlaku memanggilnya is_word. Mengapa?
Kerana apabila anda memasukkan, Maxwell, anda tidak memasukkan
apa-apa ke dalam struktur data ini.
Anda tidak menulis M. Anda tidak menulis X.
Semua yang anda lakukan adalah mengikuti petunjuk.
Penunjuk yang mewakili M, maka penunjuk yang mewakili A,
maka penunjuk yang mewakili X, maka W, E, L, L,
tetapi apa yang perlu anda lakukan pada akhir adalah jenis pergi, memeriksa, saya sampai ke lokasi ini.
Ada satu perkataan yang berakhir di sini dalam struktur data.
>> Jadi apa indone adalah benar-benar dipenuhi dengan dan penulis memilih untuk mewakili
ini terminuses dengan segitiga sedikit.
Ini hanya bermakna bahawa fakta segitiga ini di sini, ini nilai boolean benar
bermakna jika anda pergi ke belakang di pokok itu,
yang bermaksud perkataan yang bernama Maxwell merupakan dalam hal ini.
Tetapi perkataan foo, misalnya,
tidak di pokok itu, kerana jika saya bermula pada nod akar sehingga di sini di atas,
Tiada penunjuk f, tiada penunjuk o, tiada penunjuk o. Foo bukan nama dalam kamus ini.
Tetapi sebaliknya, kapan, t-u-r-i-n-g. Sekali lagi, saya tidak menyimpan t atau u atau r atau i atau n atau g.
Tetapi saya tidak kedai dalam struktur data ini nilai jalan yang sebenar turun di sini di nod ini - di pokok itu
dengan menetapkan nilai boolean ini is_word benar.
Jadi indone adalah jenis ini struktur meta sangat menarik,
di mana anda tidak benar-benar menyimpan perkataan diri untuk jenis ini kamus.
Untuk menjadi jelas, anda hanya menyimpan ya atau tidak, ada satu perkataan yang berakhir di sini.
>> Sekarang apa implikasinya?
Jika anda mempunyai 150,000 perkataan dalam kamus yang anda cuba untuk menyimpan dalam ingatan
menggunakan sesuatu seperti senarai berkaitan,
anda akan mempunyai 150,000 nod dalam senarai dikaitkan anda.
Dan mencari salah satu daripada kata-kata abjad boleh mengambil masa O (n).
Masa linear. Tetapi dalam kes sini indone satu,
apa masa berjalan mencari perkataan?
Ia ternyata keindahan di sini adalah bahawa walaupun anda mempunyai 149.999 kata-kata sudah dalam kamus ini,
seperti yang dilaksanakan dengan struktur data ini,
berapa banyak masa ia mengambil masa untuk mencari atau memasukkan seseorang yang lebih kepada yang lain, seperti Alice, Alice?
Nah, itu hanya 5, mungkin 6 langkah-langkah untuk watak mengekori.
Kerana presense nama-nama lain dalam struktur
tidak mendapat dengan cara memasukkan Alice.
Selain itu, mencari Alice sekali terdapat 150,000 perkataan dalam kamus ini
tidak mendapat dalam cara anda mencari Alice pada semua,
kerana Alice. . . . . di sini, kerana saya mendapati nilai boolean.
Dan jika tiada boolean benar, maka Alice tidak dalam struktur data ini kata-kata.
Dalam erti kata lain, masa berjalan mencari perkara dan memasukkan sesuatu ke dalam baru ini
struktur data indone O - ia tidak n.
Kerana presense 150,000 orang tidak mempunyai kesan ke atas Alice, ia seolah-olah.
Jadi mari kita memanggilnya k, di mana k adalah panjang maksimum perkataan dalam bahasa Inggeris
yang biasanya tidak lebih daripada 20-sesuatu watak.
Jadi k ialah pemalar. Jadi Holy Grail kita seolah-olah telah menemui sekarang
adalah bahawa masa indone, berterusan untuk memasukkan, untuk lookup, untuk pemotongan.
Kerana bilangan perkara sudah dalam struktur,
yang tidak walaupun fizikal sana. Sekali lagi, mereka hanya jenis diperiksa, ya atau tidak,
tidak mempunyai kesan ke atas masa masa depannya berjalan.
>> Tetapi ada mendapat menjadi tangkapan, jika tidak, kita tidak akan membazirkan begitu banyak masa
pada semua struktur data lain hanya untuk akhirnya sampai ke satu rahsia yang menakjubkan.
Jadi apa harga kita membayar untuk mencapai kebesaran ini di sini? Angkasa.
Perkara ini adalah besar-besaran. Dan sebab-sebab yang penulis
tidak hadir di sini, melihat bahawa semua perkara-perkara yang kelihatan seperti tatasusunan,
dia tidak menarik seluruh pokok itu, seluruh indone yang,
kerana mereka hanya tidak relevan kepada cerita.
Tetapi semua ini nod adalah sangat luas, dan setiap nod dalam pokok itu mengambil
26 atau sebenarnya, boleh menjadi 27 aksara kerana dalam kes ini, saya telah termasuk ruang untuk apostrofi
supaya kita boleh mempunyai perkataan apostrophized.
Dalam kes ini, ini adalah array yang luas. Jadi walaupun mereka tidak picutured,
ini mengambil sejumlah besar RAM.
Yang mungkin halus, especilly dalam perkakasan moden,
tetapi itulah tradeoff. Kita mendapat masa yang kurang dengan menghabiskan lebih banyak ruang.
Jadi di mana ini semua akan?
Nah, mari kita lakukan - mari kita lihat di sini.
Mari kita melakukan lompatan kepada lelaki ini di sini.
>> Percaya atau tidak, seronok dengan C telah untuk beberapa waktu kini,
kita mencapai titik pada semester di mana ia adalah masa untuk peralihan kepada perkara-perkara yang lebih moden.
Perkara di tahap yang lebih tinggi. Dan walaupun untuk beberapa minggu akan datang
kita masih akan terus untuk melibatkan diri dalam dunia petunjuk dan pengurusan ingatan
untuk mendapatkan keselesaan yang kita boleh membina,
permainan akhir akhirnya untuk memperkenalkan, ironinya, tidak bahasa ini.
Kami akan menghabiskan, seperti 10 minit bercakap tentang HTML.
Semua HTML adalah bahasa markup, dan apa bahasa markup adalah
-siri kurungan terbuka dan kurungan tertutup yang mengatakan 'membuat ini berani'
'Membuat ini italik' membuat berpusatkan ini. '
Ia bukan semua yang intelektual yang menarik, tetapi ia sangat berguna.
Dan ia sudah tentu kehadiran hari ini.
Tetapi apa yang berkuasa tentang dunia HTML, dan pengaturcaraan web lebih amnya,
membina perkara-perkara yang dinamik, menulis kod dalam bahasa seperti PHP atau Python atau Ruby atau Java atau C #.
Betul, apa bahasa pilihan anda, dan menjana HTML dinamik.
Menjana sesuatu yang dipanggil CSS dinamik.
Lembaran gaya Cascading, yang juga tentang estetika.
Dan sebagainya walaupun, hari ini, jika saya pergi ke beberapa laman web seperti Google.com yang biasa,
dan saya pergi untuk melihat, pemaju, pandangan sumber, yang mungkin anda telah dilakukan sebelum,
tetapi akan untuk melihat sumber, barangan ini mungkin kelihatan agak samar-samar.
Tetapi ini adalah kod asas yang melaksanakan Google.com.
Pada akhir hadapan. Dan sebenarnya semua ini adalah kembang barangan estetika.
Ini adalah CSS di sini. Jika saya menyimpan menatal ke bawah, kita akan mendapat beberapa barangan berkod warna.
Ini adalah HTML. Kod Google kelihatan seperti keadaan kucar-kacir, tetapi jika saya benar-benar membuka tetingkap yang berbeza,
kita boleh melihat beberapa struktur ini.
Jika saya membuka ini, notis di sini, ia adalah sedikit lebih mudah dibaca.
Kita akan lihat sebelum lama tag ini, [perkataan] tag,
HTML, kepala, badan, span, skrip, kawasan teks, span, tengah, div.
Dan ini juga menyusun samar-cari pada pandangan pertama,
tetapi semua keadaan kucar-kacir ini mengikuti corak tertentu, dan corak berulang,
supaya apabila kita mendapatkan asas-asas ke bawah, anda akan dapat untuk menulis kod seperti ini
dan kemudian memanipulasi kod seperti ini menggunakan satu lagi bahasa, yang dipanggil JavaScript.
Dan JavaScript adalah bahasa yang berjalan di dalam pelayar
hari ini yang kita gunakan pada Harvard kursus, untuk alat membeli-belah kursus bahawa Google maps menggunakan
untuk memberi anda sekumpulan keseluruhan dinamisme, Facebook memberikan anda untuk menunjukkan kemaskini status segera,
Twitter menggunakan ia untuk menunjukkan kepada anda tweet serta-merta.
Semua ini kita akan mula untuk melibatkan diri masuk
Tetapi untuk sampai ke sana, kita perlu memahami sesuatu yang sedikit tentang Internet.
Klip ini di sini adalah hanya satu minit panjang, dan mari kita andaikan untuk sekarang ini adalah, sebenarnya,
bagaimana Internet berfungsi sebagai memujuknya untuk apa yang kira-kira akan datang. Saya memberi anda "Pahlawan Bersih."
>> [♫ korus muzik perlahan ♫]
[Perawi Lelaki] Dia datang dengan mesej.
Dengan protokol semua sendiri.
[♫ lebih cepat muzik-muzik elektronik ♫]
Dia datang ke dunia firewall sejuk, peduli router,
dan bahaya yang jauh lebih buruk daripada kematian.
Dia cepat. Dia kuat. Dia TCP / IP, dan dia mendapat alamat anda.
Pahlawan Net.
[Malan] Minggu depan, maka. Internet. Pengaturcaraan web. Ini adalah CS50.
[CS50.TV]