>> DAVID J. Malan: Baiklah.
Jadi selamat datang untuk pertama kalinya CS50 postmortem untuk kuis.
Kami pikir kami akan meresmikan tradisi ini tahun ini.
Dan ini akan menjadi kesempatan berjalan melalui
solusi untuk kuis.
Dan kami akan mempercepat atau memperlambat berbasis pada kepentingan orang-orang di sini.
>> Jadi Anda mungkin di sini karena kau tertarik pada bagaimana Anda bisa memiliki atau
harus menjawab beberapa masalah ini.
Jadi kenapa tidak kita lihat pada bagian ini terlebih dahulu?
Sehingga mendapatkan string.
Ini memberi Anda tiga versi yang berbeda dari program itu, pada akhirnya,
dimaksudkan untuk mendapatkan string dari pengguna.
Apakah atau tidak itu yang diserahkan kepada Anda untuk menentukan.
>> Dan kami bertanya Pertanyaan 0, anggaplah bahwa versi 1 adalah
dikompilasi dan dijalankan.
Mengapa mungkin program segfault?
Pada pandangan pertama, ada saran mengapa?
Ya.
>> AUDIENCE: Jadi saya ingat melihat ini dalam contoh sebelumnya melihat
char * s dan melihat scan dari s dan melihat karena pointer, bagaimana
apakah itu mempengaruhi apa yang Anda discan dalam?
Apakah itu s atau alamat s?
>> DAVID J. Malan: OK.
Baik.
Jadi akhirnya, sumber masalah ini mungkin akan mengurangi
dengan variabel s.
Dan itu memang variabel.
Tipe data dari variabel yang char *, yang berarti itu akan
berisi alamat dari karakter.
Dan di situlah letak wawasan.
Ini akan berisi alamat dari karakter atau, lebih umum,
alamat karakter pertama di seluruh blok karakter.
>> Tapi menangkap adalah bahwa pemindaian s, tujuan dalam hidup, diberi alamat dan diberikan
kode format, seperti% s, baca string ke dalam sepotong
memori di alamat itu.
Tapi karena tidak ada tanda sama sebelum bahwa titik koma pada pertama
baris kode, karena kita tidak benar-benar mengalokasikan memori dengan
malloc, karena tidak benar-benar mengalokasikan sebuah array dari beberapa ukuran, semua
Anda lakukan adalah membaca pengguna input keyboard ke dalam beberapa lengkap
nilai sampah, yang adalah default.
Jadi kemungkinan yang Anda akan segfault jika alamat yang tidak hanya begitu terjadi
menjadi nilai yang Anda bisa, pada kenyataannya, menulis.
Begitu buruk tidak mengalokasikan memori Anda di sana.
>> Jadi dalam pertanyaan 1, kita bertanya, anggaplah bahwa versi 2
dikompilasi dan dijalankan.
Mengapa mungkin program ini segfault?
Jadi yang satu ini kurang buggy.
Dan benar-benar hanya satu cara yang jelas di mana Anda dapat
memicu segfault di sini.
Dan ini adalah tematik.
Setiap kali kita menggunakan c dalam memori, apa Anda bisa lakukan untuk menginduksi segfault
dengan versi 2?
>> AUDIENCE: Jika Anda menggunakan masukan bahwa dalam string yang lebih panjang dari 49
karakter.
>> DAVID J. Malan: Tepat.
Setiap kali Anda melihat sesuatu yang tetap panjang ketika datang ke array, Anda
radar harus pergi bahwa ini bisa menjadi bermasalah jika Anda tidak memeriksa
batas-batas array.
Dan itulah masalahnya di sini.
Kami masih menggunakan scanf.
Kami masih menggunakan% s, yang berarti mencoba untuk membaca string dari pengguna.
Itu akan dibaca ke s, yang, pada saat ini, secara efektif
alamat sepotong memori atau setara.
Ini adalah nama dari array karakter dari memori.
>> Tapi hal itu, jika Anda membaca string yang lebih panjang dari 49 karakter, 49
karena Anda membutuhkan ruang untuk backslash 0, Anda akan meluap
buffer.
Dan Anda mungkin beruntung dan dapat menulis karakter ke-51, ke-52, ke-53.
Namun di beberapa titik, OS akan mengatakan, tidak ada.
Ini jelas bukan memori Anda diperbolehkan untuk menyentuh.
Dan program ini akan segfault.
>> Jadi ada, heuristik boleh ada Anda punya waktu panjang tetap, Anda memiliki
untuk memastikan Anda memeriksa panjang dari apa pun yang Anda mencoba
untuk membaca ke dalamnya.
>> AUDIENCE: Jadi untuk mengatasi itu, Anda bisa memiliki pernyataan memeriksa sebenarnya
adalah panjang yang lebih besar dari atau kurang dari?
>> DAVID J. Malan: Tentu saja.
Anda hanya memiliki kondisi yang mengatakan, jika -
atau lebih tepatnya Anda tidak perlu tahu di muka berapa banyak karakter yang
pengguna akan mengetik, karena Anda memiliki ayam dan telur.
Tidak sampai Anda sudah membacanya dengan scanf Anda dapat mengetahui berapa lama itu.
Tapi pada saat itu, sudah terlambat, karena Anda sudah membaca ke
beberapa blok memori.
Jadi sebagai samping, hindari perpustakaan CS50 masalah ini sama sekali, mengingat
dengan menggunakan fgetc.
Dan membaca satu karakter pada satu waktu, tip-toeing bersama, mengetahui bahwa Anda
tidak bisa meluap karakter jika Anda membaca satu per satu.
>> Menangkap adalah dengan GetString recall adalah bahwa kita harus terus-menerus kembali ukuran
bahwa sepotong memori, yang hanya sakit.
Ini banyak baris kode untuk melakukan itu.
Jadi pendekatan lain akan benar-benar menggunakan sepupu, sehingga
untuk berbicara, dari scanf.
Ada varian banyak ini fungsi yang benar-benar memeriksa
panjang berapa banyak karakter Anda mungkin membaca secara maksimal.
Dan Anda bisa menentukan, tidak membaca lebih dari 50 karakter.
Sehingga akan menjadi pendekatan lain tetapi kurang akomodatif input yang lebih besar.
>> Jadi pertanyaan 2 bertanya, misalkan versi yang 3 dikompilasi dan dieksekusi.
Mengapa mungkin program yang segfault?
Jadi yang satu ini sebenarnya sama menjawab, meskipun
terlihat sedikit lebih menarik.
Kami menggunakan malloc, yang terasa seperti kita memberikan diri kita lebih banyak pilihan.
Dan kemudian kita membebaskan bahwa memori di akhir.
Ini masih hanya 50 byte memori.
Jadi kita mungkin masih mencoba untuk membaca di 51, 52, 1.000 bytes.
Itu akan segfault untuk alasan yang sama persis.
>> Tapi ada alasan lain juga.
Apa lagi yang bisa malloc kembali selain alamat sepotong memori?
Ini bisa kembali null.
Dan karena kita tidak memeriksa itu, kita mungkin akan melakukan sesuatu
bodoh karena alasan lain, yaitu bahwa kita mungkin akan mengatakan scanf, baca
input pengguna dari keyboard menjadi 0 lokasi, AKA null.
Dan itu juga, pasti akan memicu segfault.
Jadi untuk tujuan kuis, kita akan telah menerima salah satu dari mereka sebagai
alasan yang sah.
Salah satunya adalah identik.
Salah satunya adalah sedikit lebih bernuansa.
>> Terakhir, sehubungan dengan program penggunaan memori, bagaimana versi 2 dan
versi 3 berbeda?
Jadi untuk apa itu layak, kita melihat pasokan tampaknya tak berujung mungkin
jawaban ini.
Dan di antara jawaban orang, apa yang kami harapkan, tapi kami menerima lain
hal, beberapa menyebutkan Fakta bahwa versi 2 menggunakan
yang disebut stack.
Versi 3 menggunakan heap.
Dan secara fungsional, ini tidak benar-benar membuat semua yang banyak perbedaan.
Pada akhir hari, kita masih hanya mendapatkan 50 byte memori.
>> Tapi itu salah satu kemungkinan jawaban bahwa kita sedang melihat.
Tapi Anda akan melihat, karena Anda mendapatkan kuis Anda kembali dari TF, yang kami lakukan
menerima diskusi lain mereka penggunaan yang berbeda dari memori juga.
Tapi stack dan heap akan jawaban yang mudah untuk pergi bersama.
Ada pertanyaan?
Saya memberikan Rob.
>> ROB Bowden: Jadi masalah 4.
Ini adalah salah satu di mana Anda harus mengisi dalam jumlah byte dari semua
jenis yang berbeda digunakan.
Jadi hal pertama yang kita lihat.
Asumsikan arsitektur 32-bit, seperti alat CS50 ini.
Jadi salah satu hal mendasar tentang Arsitektur 32-bit, yang memberitahu kita
persis seberapa besar pointer akan berada di arsitektur.
>> Jadi segera, kita tahu bahwa setiap pointer Jenis adalah 32-bit atau 4 byte.
Jadi melihat tabel ini, simpul * adalah jenis pointer.
Itu akan menjadi 4 byte.
Struct simpul *, yang secara harfiah identik dengan bintang simpul.
Dan sehingga akan menjadi 4 byte.
String, sehingga tidak terlihat seperti pointer, tapi typedef, a
string hanya char *, yang adalah jenis pointer.
Sehingga akan menjadi 4 byte.
>> Jadi ketiganya adalah semua 4 byte.
Sekarang, node dan mahasiswa yang sedikit lebih rumit.
Jadi melihat simpul dan mahasiswa, kita melihat node sebagai integer dan pointer.
Dan mahasiswa adalah dua pointer di dalamnya.
Jadi setidaknya untuk kasus kami di sini, jalan bahwa kita akhirnya menghitung ukuran
struct ini hanya menambahkan semuanya yang ada di dalam struct.
>> Jadi untuk node, kita memiliki sebuah integer, yang 4 byte.
Kami memiliki pointer, yang adalah 4 byte.
Dan satu node akan untuk mengambil 8 byte.
Dan juga untuk mahasiswa, kita memiliki pointer yang 4 byte dan lain
pointer yang 4 byte.
Sehingga akan berakhir up menjadi 8 byte.
Jadi simpul dan mahasiswa adalah 8 byte.
Dan tiga ini semua 4 byte.
Pertanyaan itu?
Ya.
>> AUDIENCE: Apakah itu adalah 64-bit arsitektur, alangkah baiknya
menggandakan semua dari mereka?
>> ROB Bowden: Ini tidak akan dua kali lipat mereka semua.
Jadi arsitektur 64-bit, itu, sekali lagi, perubahan yang hal mendasar bahwa
pointer sekarang 64 bit.
Ya.
Jadi pointer adalah 8 byte.
Jadi ini yang 4 byte akan menjadi 8 byte.
Seorang mahasiswa, yang dua pointer, baik, sekarang akan
menjadi 8 byte, 8 byte.
Ini akan membuat 16 byte.
>> Tapi simpul masih 4 byte.
Jadi pointer ini akan menjadi 8 byte.
Ini adalah 4 byte.
Jadi node hanya akan menjadi 12 byte.
Ada pertanyaan lain yang satu itu?
Jadi yang berikutnya, ini adalah kode status HTTP.
Dan Anda harus menggambarkan keadaan di mana kekuatan ini
dikembalikan kepada Anda.
satu masalah yang saya dengar beberapa siswa adalah bahwa mereka mencoba untuk membuat
kesalahan berada di ujung klien.
Jadi ketika kita mencoba untuk membuat permintaan ke server, sesuatu yang
salah pada akhir kami.
Tapi pada umumnya, kode-kode ini dikembalikan oleh server.
Jadi kami ingin mencari tahu apa yang terjadi salah atau benar pada server yang
menyebabkan hal-hal ini harus dikembalikan.
Jadi mengapa mungkin sebuah server mengembalikan kode status 200?
Setiap pikiran?
>> Ya.
Jadi sesuatu tentang sukses permintaan pergi melalui.
Dan mereka dapat kembali apa pun yang Anda minta.
Jadi semuanya baik-baik saja.
Bagaimana dengan 302 ditemukan?
Ya.
>> AUDIENCE: Server sedang mencari untuk apa yang Anda minta.
Tapi itu tidak bisa menemukannya.
Jadi ada kesalahan.
>> ROB Bowden: Jadi server adalah mencari apa yang Anda inginkan.
Jadi hanya mencari di sini, 302 ditemukan, itu dapat menemukannya.
>> AUDIENCE: Maafkan aku.
Ditemukan berarti bahwa mereka tidak menemukan itu.
Maaf.
>> ROB Bowden: Jadi 302 ditemukan.
Server dapat menemukan apa yang Anda inginkan.
>> AUDIENCE: Tapi itu tidak menampilkan itu?
>> ROB Bowden: Perbedaan antara ini 302 dan 200 adalah bahwa hal itu
tahu apa yang Anda inginkan.
Tapi itu tidak persis di mana Anda ingin bertanya.
Jadi 302 adalah redirect khas.
Jadi Anda meminta halaman.
Ia tahu, oh, aku ingin untuk kembali padamu.
Tapi ini di URL yang berbeda.
Jadi hey, Anda benar-benar ingin ini.
>> DAVID J. Malan: Ini adalah bagian yang mengatakan bahwa kami memberi kalian redirect
fungsi yang menggunakan fungsi kepala yang, pada gilirannya, dicetak lokasi,
usus besar, dan kemudian URL yang Anda ingin menolak pengguna.
Meskipun Anda tidak melihat 302 eksplisit ada, itulah yang PHP
akan ajaib masukkan sebagai header mengatakan apa yang Rob mengatakan ada -
ditemukan.
Tapi pergi di sini sebagai gantinya.
>> ROB Bowden: OK.
Jadi bagaimana dengan 403 dilarang?
>> AUDIENCE: Saya pikir itu bahwa server pada dasarnya mengatakan bahwa klien
tidak dapat mengakses halaman rumah.
>> ROB Bowden: Jadi ya.
Nah, jawaban khas kami mengharapkan sesuatu seperti, file
tidak chmodded tepat.
Itu mungkin dalam keadaan apa Anda melihat mereka.
Tapi ada alasan bahwa klien bisa salah di sini.
Sebenarnya ada kode status lain -
401.
Jadi ini sangat mirip.
>> 401 adalah tidak sah.
Dan 403 dilarang.
Dan tidak sah Anda secara eksklusif dapatkan jika Anda tidak login
Tapi log in mungkin berarti bahwa Anda berwenang.
Tapi jika Anda sudah login dan Anda masih tidak memiliki izin, maka
Anda juga bisa mendapatkan terlarang.
Jadi jika Anda login dan tidak memiliki izin, dilarang juga
sesuatu yang bisa Anda dapatkan.
>> DAVID J. Malan: Dan mekanisme yang masalah ini biasanya
dipecahkan pada server adalah melalui perintah apa?
Chmod, jika itu, memang, izin masalah pada file atau direktori.
>> ROB Bowden: Lalu 404 tidak ditemukan.
Ya.
Jadi tidak seperti 302 di mana itu tidak persis di mana Anda bertanya tapi ia tahu apa
Anda inginkan, ini, itu hanya memiliki tidak tahu apa yang Anda inginkan.
Dan Anda tidak meminta sesuatu yang valid.
418 Aku teko dan kemudian 500 internal server.
Jadi mengapa Anda mungkin mendapatkan itu?
>> Jadi segfault -
Aku benar-benar tidak tahu grading standar untuk ini.
Tetapi jika kode PHP Anda memiliki sesuatu salah di dalamnya, secara teori, hal itu bisa
sebenarnya segfault, dalam hal ini, ini 500 internal server error, sesuatu
yang salah dengan server Anda konfigurasi.
Atau ada kesalahan sintaks dalam kode PHP Anda.
Atau sesuatu yang buruk sedang terjadi.
>> DAVID J. Malan: Kita memang melihat segfault antara jawaban beberapa orang.
Dan secara teknis, itu bisa terjadi.
Tapi itu akan menjadi PHP, program ditulis oleh orang lain, sebenarnya
segfaulted, yang hanya jika orang-orang mengacaukan dan menulis kode buggy di
penerjemah mereka akan PHP sendiri segfault.
Jadi meskipun 500 adalah seperti segfault dalam roh, itu hampir selalu
hasil dari masalah file konfigurasi dengan web server atau, seperti kata Rob,
kesalahan sintaks, seperti Anda tidak menutup penawaran.
Atau Anda kehilangan titik koma di suatu tempat.
>> AUDIENCE: Jadi untuk pset Shuttle, saya pikir ketika saya melakukannya sekali saya mengklik
Browser, tapi tidak ada yang datang, apa yang mereka sebut halaman putih.
Tapi itu karena kode.
Saya pikir itu JavaScript, kan?
>> ROB Bowden: Ya.
>> AUDIENCE: Akankah kesalahan yang masih muncul?
>> ROB Bowden: Jadi, Anda tidak akan mendapatkan kesalahan ini karena semuanya
dari perspektif web server benar-benar baik-baik saja.
Tapi Anda minta index.html.
Anda meminta shuttle.js dan service.js.
Dan itu berhasil kembali untuk semua hal-hal -
200.
OK.
Hanya ketika browser Anda mencoba menginterpretasikan kode JavaScript yang
itu seperti, tunggu, ini bukan error JavaScript valid.
Ada pertanyaan lain?
Baik.
>> DAVID J. Malan: Jadi berikutnya up adalah nomor 11.
Dan 11 adalah paling menakutkan untuk banyak orang.
Jadi hal yang paling penting untuk dicatat di sini adalah bahwa ini adalah, memang, sekitar
daftar ganda terkait.
Tapi ini tidak sama dengan tahun lalu ganda terkait masalah daftar,
yang tidak memberikan peringatan bahwa daftar bisa, pada kenyataannya, menjadi unsorted.
>> Jadi fakta bahwa daftar itu unsorted dan fakta bahwa kata itu
digarisbawahi ada dimaksudkan untuk menyampaikan bahwa ini sebenarnya penyederhanaan
apa kalau tidak pasti masalah yang lebih menantang
dan satu lagi.
Jadi kesalahan umum di sini adalah telah menempatkan solusi tahun lalu pada satu Anda
pager dan kemudian hanya membabi buta menyalin bahwa turun sebagai jawaban, yang merupakan hak
menjawab pertanyaan yang berbeda serupa semangatnya.
Tapi kehalusan sini adalah sebagai berikut.
>> Jadi satu, kami telah menyatakan node dan didefinisikan dalam cara yang biasa di sini.
Kemudian kita mendefinisikan daftar menjadi global pointer diinisialisasi ke null.
Kemudian ternyata, ada dua fungsi kita memiliki prototipe untuk di sini, insert
dan menghapus.
Dan kemudian kita memiliki beberapa contoh kode di sini melakukan banyak sisipan.
Dan kemudian kami meminta Anda untuk menyelesaikan pelaksanaan insert bawah sedemikian
dengan cara yang memasukkan n ke dalam daftar dalam waktu yang konstan, juga menggarisbawahi,
bahkan jika sudah ada.
>> Jadi keindahan mampu menyisipkan dalam waktu yang konstan adalah bahwa ia menyiratkan
bahwa Anda harus memasukkan node baru di mana?
Ke depan.
Jadi menghilangkan, untungnya, setidaknya salah satu kasus yang digunakan untuk meminta
baris bahkan lebih kode, seperti itu tahun lalu dan bahkan di kelas ketika kita
berbicara melalui hal semacam ini dengan manusia dan dengan beberapa
pseudo kode verbal.
Jadi dalam larutan sini, mari kita melewatkan itu hanya untuk memiliki visual yang pada
layar.
>> Perhatikan bahwa kita sedang melakukan hal berikut.
Dan juga perhatikan penyederhanaan lain adalah bahwa bahkan jika itu
sudah ada, jadi ini berarti bahkan jika nomor sudah ada, Anda dapat
hanya membabi buta memasukkan lain salinannya.
Dan itu juga, dimaksudkan untuk menjadi penyederhanaan, sehingga Anda bisa
fokus pada, benar-benar, beberapa lebih Bagian yang menarik secara intelektual dan
bukan hanya beberapa pengecekan error tambahan mengingat waktu yang terbatas.
>> Jadi dalam larutan sampel ini, kami mengalokasikan pointer di kiri
sisi sini untuk node.
Sekarang, menyadari bahwa pointer, seperti Rob mengatakan, hanya 32 bit.
Dan itu tidak benar-benar mengandung alamat sampai Anda
menetapkan alamat.
Dan kami melakukannya di kanan side via malloc.
Seperti warga negara yang baik, kami memeriksa bahwa malloc tidak, pada kenyataannya, null, sehingga
kita tidak sengaja membuat sebuah segfault sini.
Dan setiap kali Anda menggunakan malloc dalam hidup, Anda harus memeriksa null, jangan
Anda memiliki bug halus.
>> Kemudian kita menginisialisasi nol bahwa dengan menugaskan n dan sebelumnya dan berikutnya.
Dan dalam hal ini di sini, saya diinisialisasi sebelumnya untuk null, karena ini baru
node akan menjadi baru mulai dari daftar saya.
Jadi ada akan menjadi apa-apa sebelumnya.
Dan saya ingin dasarnya menambahkan daftar yang ada ke node baru
pengaturan berikutnya sama dengan daftar sendiri.
Tapi aku tidak dilakukan dulu.
Jadi jika daftar itu sendiri sudah ada, dan ada setidaknya satu simpul
sudah di tempat, jika ini adalah daftar di sini dan saya menyisipkan node baru di sini, saya
perlu memastikan bahwa mantan simpul saya menunjuk ke belakang untuk node baru saya,
karena ini adalah, sekali lagi, daftar ganda terkait.
>> Jadi kita melakukan pemeriksaan kewarasan.
Jika daftar tidak null, jika sudah ada satu atau lebih node di sana, kemudian
menambahkan bahwa kembali referensi sehingga untuk berbicara.
Dan kemudian hal terakhir yang kita butuhkan lakukan adalah benar-benar memperbarui global
daftar variabel itu sendiri ke titik dengan node baru.
Ya.
>> AUDIENCE: Dalam pointer panah [Tak terdengar] sama dengan nol, apakah itu
berurusan dengan daftar karena daftar adalah null?
>> DAVID J. Malan: Tidak.
Itu hanya saya menjadi proaktif hati-hati, karena jika ini adalah saya
daftar asli dengan mungkin beberapa node lebih di sini dan aku memasukkan saya
node baru di sini, ada akan menjadi apa-apa di sini.
Dan aku ingin menangkap gagasan bahwa dengan menetapkan sebelumnya untuk
null pada node baru.
Dan mungkin, jika kode saya benar dan tidak ada cara lain untuk memasukkan
node selain fungsi ini, mungkin, bahkan jika daftar telah memiliki
satu atau lebih node di dalamnya, agaknya list, simpul pertama, akan memiliki
pointer sebelumnya nol itu sendiri.
>> AUDIENCE: Dan hanya tindak lanjut.
Alasan Anda meletakkan pointer equals berikutnya list Anda membuat pointer
sebelum daftar dalam bahwa itu menunjuk ke depan, saya kira -
Aku tidak -
hanya daftar?
>> DAVID J. Malan: Tepat.
Dan jadi mari kita benar-benar mempertimbangkan dua kasus sini benar-benar, meskipun
Agar kami akan menganggap mereka tidak persis sama seperti kode.
Tetapi pada tingkat tinggi, apakah ini merupakan daftar dan ini adalah 32-bit
pointer, skenario yang paling sederhana adalah bahwa ini adalah nol secara default.
Dan misalkan saya ingin memasukkan nomor 50 adalah nomor pertama.
Jadi aku akan pergi ke depan dan mengalokasikan node, yang akan berisi
tiga bidang -
n, sebelumnya, dan berikutnya.
>> Aku akan menempatkan nomor 50 di sini, karena ini akan menjadi n.
Ini akan berikutnya.
Dan ini akan menjadi sebelumnya.
Jadi apa yang harus saya lakukan dalam kasus ini?
Yah, aku baru saja dilakukan baris 1 di sini.
Pointer n mendapat n.
Saya kemudian mengatakan, sebelumnya harus mendapatkan null.
Jadi ini akan menjadi nol.
Kemudian aku akan katakan selanjutnya akan mendapatkan daftar.
>> Dan ini hanya bekerja dengan baik.
Ini adalah null.
Dan saya katakan, node baru berikutnya lapangan harus mendapatkan apa pun ini.
Sehingga menempatkan nol lain di sana.
Dan kemudian hal terakhir Saya adalah memeriksa di sini.
Jika daftar tidak sama dengan nol, tetapi sama dengan nol, jadi kami melewatkan itu
sama sekali.
Jadi semua saya lakukan selanjutnya adalah daftar mendapat pointer, yang pictorially menghasilkan
gambar seperti itu.
Jadi itu satu skenario.
>> Dan salah satu yang Anda bertanya tentang khusus adalah situasi seperti ini,
di mana kita sudah memiliki daftar satu-node.
Dan jika aku kembali di aslinya pernyataan masalah, berikutnya kita akan
masukkan mengatakan adalah 34, hanya untuk kepentingan diskusi.
Jadi aku akan hanya nyaman menarik bahwa di sini.
Saya baru saja malloced.
Mari kita berasumsi aku memeriksa null.
>> Sekarang, aku akan menginisialisasi n menjadi 34.
Dan ini akan menjadi n.
Ini akan berikutnya.
Dan ini akan menjadi sebelumnya.
Mari kita pastikan saya tidak mendapatkan ini mundur.
Sebelumnya datang pertama dalam definisi.
Biarkan saya memperbaiki ini.
Hal ini sebelumnya.
Ini berikutnya.
Meskipun ini adalah identik, mari kita tetap konsisten.
>> Sebelumnya.
Ini berikutnya.
Jadi saya baru saja malloced catatan saya, diperiksa for null, ditugaskan ke 34 node.
Sebelumnya mendapat null.
Sehingga memberi saya itu.
Berikutnya mendapatkan daftar.
Jadi daftar yang ini.
Jadi ini adalah sama sekarang seperti gambar ini panah, sehingga mereka menunjuk ke satu
dalam hal yang sama.
Dan kemudian aku memeriksa jika daftar tidak sama dengan nol.
Dan itu bukan kali ini.
Lalu aku akan melakukan daftar sebelumnya mendapat pointer.
>> Jadi daftar sebelumnya mendapat PTR.
Jadi ini memiliki efek menempatkan panah grafis di sini.
Dan itu semakin sedikit yang bergelombang, garis-garis.
Dan kemudian, akhirnya, saya memperbarui daftar untuk menunjuk ke pointer.
Jadi sekarang ini menunjuk ke orang ini.
Dan sekarang, mari kita lakukan cepat kewarasan cek.
>> Berikut ini daftar, yang variabel global.
Simpul pertama adalah, memang, 34, karena Aku mengikuti panah itu.
Dan itu benar karena saya ingin masukkan pada awal daftar
semua node baru.
Bidangnya berikutnya membuat saya orang ini.
Jika aku terus, aku memukul selanjutnya adalah null.
Jadi tidak ada lagi daftar.
Jika aku memukul sebelumnya, saya mendapatkan kembali di mana saya harapkan.
>> Jadi masih ada beberapa petunjuk, jelas, untuk memanipulasi.
Tapi fakta bahwa Anda diberitahu untuk melakukan ini dalam waktu yang konstan berarti Anda hanya
memiliki jumlah terbatas hal-hal Anda diperbolehkan untuk dilakukan.
Dan apa nomor itu?
Mungkin satu langkah.
Mungkin dua.
Mungkin 1.000 langkah.
Tapi itu terbatas, yang berarti Anda tidak bisa telah segala jenis looping terjadi
sini, tidak ada rekursi, tidak ada loop.
Hanya saja harus menjadi garis keras-kode kode seperti yang kita miliki dalam sampel ini.
>> Jadi masalah berikutnya 12 meminta kami untuk menyelesaikan implementasi remove
bawah sedemikian rupa sehingga menghilangkan n dari daftar dalam waktu linier.
Jadi, Anda harus sedikit lebih ruang gerak sekarang.
Anda mungkin menganggap bahwa n, jika ada dalam daftar, akan hadir
tidak lebih dari sekali.
Dan itu juga dimaksudkan untuk menjadi berbasis kuis asumsi menyederhanakan, sehingga
bahwa jika Anda menemukan nomor 50 di suatu tempat dalam daftar, Anda tidak juga
perlu khawatir tentang terus iterate, mencari setiap kemungkinan
salinan 50, yang hanya akan menyerahkan ke beberapa minutia dalam waktu yang terbatas.
>> Jadi dengan menghapus, satu ini pasti lebih menantang dan lebih
kode untuk menulis.
Tapi pada pandangan pertama, terus terang, itu mungkin terlihat luar biasa dan seperti
tidak ada cara Anda bisa memiliki datang dengan pada kuis.
Tetapi jika kita fokus pada langkah-langkah individu, mudah-mudahan, itu akan tiba-tiba
menyerang Anda bahwa masing-masing individu tersebut langkah masuk akal yang jelas
dalam retrospeksi.
Jadi mari kita lihat.
>> Jadi pertama, kita menginisialisasi pointer menjadi daftar sendiri.
Karena aku ingin waktu linier, artinya Aku akan memiliki beberapa lingkaran.
Dan cara yang umum untuk beralih di atas node dalam struktur daftar atau apapun
struktur iteratif adalah untuk mengambil pointer ke depan data
struktur dan kemudian hanya mulai memperbarui dan berjalan jalan
melalui struktur data.
Jadi aku akan melakukan hal itu.
>> Sementara pointer, variabel sementara saya, tidak sama dengan nol, mari kita
pergi ke depan dan memeriksa.
Apakah saya beruntung?
Adalah bidang n di node Saat ini saya melihat sama dengan
Nomor Saya mencari?
Dan jika demikian, mari kita lakukan sesuatu.
Sekarang, melihat ini jika kondisi mengelilingi seluruh yang
berikut baris kode.
Ini adalah satu-satunya hal yang saya pedulikan - menemukan nomor tersebut.
Jadi tidak ada yang lain, yang menyederhanakan hal-hal konseptual sedikit.
>> Tapi sekarang, aku sadar, dan Anda mungkin memiliki hanya menyadari hal ini setelah berpikir
melalui sedikit, ada sebenarnya dua kasus di sini.
Salah satunya adalah di mana node adalah di mulai dari daftar, yang merupakan
sedikit mengganggu, karena itu adalah kasus khusus, karena Anda harus berurusan
dengan hal ini, yang adalah satu-satunya anomali.
Di tempat lain dalam daftar, itu hal yang sama.
Ada simpul sebelumnya dan berikutnya node, simpul sebelumnya, node berikutnya.
Tapi orang ini adalah sedikit khusus jika dia di awal.
>> Jadi jika pointer sama dengan daftar sendiri, jadi jika saya di awal
daftar dan saya telah menemukan n, saya perlu untuk melakukan beberapa hal.
Satu, saya perlu mengubah daftar ke menunjuk ke kolom berikutnya, 50.
Jadi anggaplah bahwa saya sedang mencoba untuk menghapus 34.
Jadi orang ini harus pergi pergi hanya dalam beberapa saat.
>> Jadi aku akan mengatakan, daftar mendapat pointer berikutnya.
Nah, ini adalah pointer.
Selanjutnya menunjuk di sini.
Jadi ini adalah mengubah panah kanan ini sekarang untuk menunjuk ke orang ini di sini.
Sekarang, ingat, kita memiliki variabel sementara.
Jadi kami belum yatim setiap node, karena saya juga memiliki orang ini di saya
pelaksanaan remove.
Jadi sekarang, jika daftar itu sendiri tidak null, Aku harus memperbaiki sesuatu yang kecil.
>> Saya perlu sekarang pastikan bahwa panah ini, yang sebelumnya menunjuk
50-34, ini harus pergi, karena jika saya sedang mencoba untuk menyingkirkan
dari 34, 50 sebaiknya tidak memelihara jenis kembali referensi untuk itu sebagai
panah disarankan.
Jadi saya hanya melakukan baris ini.
Jadi aku sudah selesai.
Kasus itu sebenarnya cukup mudah.
Memenggal kepala daftar relatif mudah.
>> Sayangnya, ada ini menjengkelkan lain blok.
Jadi sekarang, saya harus mempertimbangkan kasus di mana ada sesuatu di tengah.
Tapi itu tidak terlalu mengerikan, kecuali untuk sintaks seperti ini.
Jadi jika aku tidak di awal daftar, aku di suatu tempat di tengah.
Dan baris ini di sini mengatakan, mulai pada node apa pun yang Anda berada di.
Pergi ke kolom berikutnya node sebelumnya dan menunjukkan bahwa pada pointer.
>> Mari kita lakukan ini pictorially.
Yang semakin rumit.
Jadi jika saya memiliki bidang sebelumnya di sini - mari kita lakukan ini - bidang berikutnya di sini.
Aku akan menyederhanakan pointer saya agak daripada menarik sejumlah besar
hal bolak-balik malang-melintang satu sama lain.
Dan sekarang, mari kita mengatakan ini adalah 1, 2, 3 untuk kepentingan diskusi, bahkan
meskipun itu tidak sejalan dengan masalah yang bersangkutan.
>> Jadi, inilah daftar link saya.
Saya mencoba untuk menghapus dua dalam hal ini versi tertentu dari cerita.
Jadi saya telah memperbarui pointer ke menunjuk ke orang ini.
Jadi ini adalah PTR.
Dia menunjuk di sini.
Ini adalah daftar yang ada global seperti sebelumnya.
Dan dia menunjuk di sini tidak peduli apa.
Dan sekarang, saya sedang mencoba untuk menghapus dua.
>> Jadi jika pointer menunjuk sini, aku akan mengikuti, tampaknya,
pointer sebelumnya, yang menempatkan saya pada 1.
Saya kemudian akan mengatakan bahwa ke depan lapangan, yang membawa saya ke ini
kotak di sini, akan pointer yang sama berikutnya.
Jadi jika pointer ini, ini berikutnya.
Itu berarti bahwa ini panah kebutuhan untuk menunjuk ke orang ini.
>> Jadi apa yang baris kode baru saja dilakukan adalah sedikit ini.
Dan sekarang, ini tampak seperti langkah ke arah yang benar.
Kami pada dasarnya ingin snip 2 keluar dari tengah 1 dan 3.
Jadi masuk akal bahwa kita ingin rute pointer ini di sekitarnya.
Jadi baris berikutnya ini memeriksa apakah pointer selanjutnya tidak null, ada
memang seseorang di sebelah kanan 2, itu berarti kita juga harus melakukan
sedikit snip sini.
>> Jadi sekarang saya harus mengikuti pointer ini dan memperbarui pointer sebelumnya pada
orang ini untuk melakukan sedikit dari Workaround sini titik di sini.
Dan sekarang, secara visual ini bagus.
Ini sedikit berantakan di bahwa ada tidak ada yang menunjuk pada 2 lagi.
2 menunjuk ke kiri.
Dan 2 menunjuk ke kanan.
Tapi dia bisa melakukan apapun yang dia inginkan, karena dia akan mendapatkan dibebaskan.
Dan tidak peduli apa nilai-nilai tersebut lagi.
>> Yang penting adalah bahwa sisa orang routing atas
dan di bawahnya sekarang.
Dan memang, itulah yang kita lakukan selanjutnya.
Kami pointer gratis, yang berarti kita memberitahu sistem operasi, Anda dipersilakan
untuk merebut kembali ini.
Dan kemudian terakhir, kita kembali.
Lain implisit, jika kita tidak kembali lagi,
kita harus terus mencari.
Jadi pointer sama dengan pointer berikutnya hanya berarti memindahkan orang ini di sini.
Pindahkan orang ini di sini.
Pindahkan orang ini di sini jika, pada kenyataannya, kami tidak menemukan nomor
kita cari belum.
>> Jadi terus terang, itu terlihat benar-benar luar biasa, saya pikir, pada awalnya
sekilas, terutama jika Anda berjuang dengan ini selama kuis kemudian melihat
sesuatu seperti ini.
Dan Anda menepuk diri di bagian belakang.
Nah, tidak ada cara saya bisa datang dengan bahwa pada kuis.
Tapi saya berpendapat, Anda dapat jika Anda istirahat itu ke dalam individu tersebut
kasus dan hanya berjalan melalui itu hati-hati, meskipun, diakui, di bawah
keadaan stres.
>> Untungnya, gambar dibuat semuanya bahagia.
Anda bisa menarik ini berbagai cara.
Anda tidak perlu melakukan saling silang yang hal di sini.
Anda bisa melakukannya dengan lurus baris seperti ini.
Tapi inti dari masalah ini, di umum, adalah untuk menyadari bahwa
gambar pada akhirnya akan terlihat sedikit sesuatu seperti ini, karena
waktu konstan tersirat bahwa Anda tetap kemacetan dan kemacetan dan kemacetan
node baru di awal daftar.
Ada pertanyaan?
Mungkin yang paling menantang tentu pertanyaan coding.
>> AUDIENCE: Jadi ini adalah daftar serupa dengan kepala dalam contoh sebelumnya.
>> DAVID J. Malan: Tepat, persis.
Hanya nama yang berbeda untuk variabel global.
World wide apa?
>> ROB Bowden: OK.
Jadi ini adalah satu di mana Anda harus menulis paragraf.
Beberapa orang menulis esai untuk pertanyaan ini.
Tapi Anda hanya perlu menggunakan enam istilah ini untuk menggambarkan apa yang terjadi ketika
Anda mencoba untuk menghubungi facebook.com.
Jadi saya hanya akan berbicara melalui proses menggunakan semua istilah-istilah ini.
Jadi di browser kita, kita ketik facebook.com dan tekan Enter.
Jadi browser kita akan membangun sebuah HTTP meminta bahwa itu akan mengirim
melalui beberapa proses untuk Facebook untuk Facebook untuk menanggapi kami dengan
HTML halaman.
>> Jadi apa adalah proses yang permintaan HTTP
benar-benar sampai ke Facebook?
Jadi pertama, kita perlu menerjemahkan Facebook.com.
Jadi hanya diberi nama Facebook.com, di mana sebenarnya permintaan HTTP
harus pergi?
Jadi kita perlu menerjemahkan Facebook.com ke alamat IP, yang unik
mengidentifikasi mesin apa kita benar-benar ingin mengirim permintaan ini.
Laptop Anda memiliki alamat IP.
Apa pun yang terhubung ke internet memiliki alamat IP.
>> Jadi DNS, Domain Name System, yaitu apa yang akan menangani terjemahan
dari facebook.com ke alamat IP yang Anda benar-benar ingin menghubungi.
Jadi kami menghubungi server DNS dan mengatakan, apa facebook.com?
Ia mengatakan, oh, itu alamat IP 190,212 sesuatu, sesuatu, sesuatu.
Baik.
Sekarang, aku tahu apa mesin Saya hanya mau menghubungi.
>> Jadi Anda mengirim permintaan HTTP Anda ke mesin itu.
Jadi bagaimana cara mendapatkan mesin itu?
Nah, permintaan pergi dari router ke router memantul.
Ingat contoh di kelas, di mana kita benar-benar melihat rute bahwa
paket mengambil ketika kami mencoba untuk berkomunikasi.
Kami melihatnya melompati Atlantik Laut pada satu titik atau apa pun.
>> Jadi port musim lalu.
Jadi sekarang ini adalah pada komputer Anda.
Anda dapat memiliki beberapa hal yang saat ini berkomunikasi dengan internet.
Jadi saya bisa berjalan, katakanlah, Skype.
Saya mungkin memiliki web browser open.
Saya mungkin memiliki sesuatu yang torrenting file.
Jadi semua hal-hal ini berkomunikasi dengan
internet dalam beberapa cara.
>> Jadi, ketika komputer Anda menerima beberapa data dari internet, bagaimana melakukannya
tahu aplikasi apa yang sebenarnya menginginkan data?
Bagaimana cara mengetahui apakah ini khusus Data dimaksudkan untuk
torrenting aplikasi sebagai lawan ke web browser?
Jadi ini adalah tujuan dari pelabuhan dalam semua aplikasi ini memiliki
mengklaim sebuah port pada komputer Anda.
Jadi web browser Anda berkata, hey, Aku mendengarkan pada port 1000.
Dan Program torrenting Anda katakan, Aku mendengarkan pada port 3000.
Dan Skype mengatakan, saya menggunakan port 4000.
>> Jadi, ketika Anda mendapatkan beberapa data yang dimiliki ke salah satu aplikasi, data
ditandai dengan port yang sebenarnya harus dikirim bersama untuk.
Jadi ini mengatakan, oh, saya milik ke port 1000.
Aku tahu maka saya harus meneruskan ini bersama untuk browser web saya.
Jadi alasan itu relevan di sini adalah bahwa server web cenderung
mendengarkan pada port 80.
Jadi ketika saya menghubungi Facebook.com, aku berkomunikasi dengan beberapa mesin.
Tapi aku harus mengatakan yang port yang mesin saya ingin berkomunikasi dengan.
Dan server web cenderung mendengarkan pada port 80.
>> Jika mereka ingin, mereka bisa mengaturnya up sehingga daftar sebagai pada port 7000.
Dan kemudian di browser web, aku bisa manual ketik Facebook.com: 7000 untuk
mengirim permintaan ke port 7000 dari server web Facebook.
>> DAVID J. Malan: Dan dalam hal ini, bahkan meskipun kami tidak mengharuskan orang
menyebutkan hal ini, dalam hal ini, apa port akan permintaan benar-benar pergi ke?
Coba lagi.
Tepat.
Tidak mencari itu, tapi kehalusan sebuah yang ada tidak ada yang terakhir.
>> ROB Bowden: Jadi HTTPS, karena itu mendengarkan khusus untuk
dienkripsi, itu pada port 4430.
>> AUDIENCE: Dan email adalah 25, kan?
>> DAVID J. Malan: Outbound email, 25, yep.
>> ROB Bowden: Aku bahkan tidak tahu sebagian besar - semua yang lebih rendah cenderung
disediakan untuk hal-hal.
Saya pikir segala sesuatu di bawah 1024 dicadangkan.
>> AUDIENCE: Mengapa Anda mengatakan 3 adalah nomor yang salah?
>> ROB Bowden: Karena dalam sebuah alamat IP, ada empat kelompok angka.
Dan mereka dari 0 sampai 255.
Jadi 192.168.2.1 adalah umum alamat IP jaringan lokal.
Perhatikan semua dari mereka adalah kurang dari 255.
Jadi ketika saya mulai dengan 300, yang tidak mungkin memiliki
menjadi salah satu nomor.
>> DAVID J. Malan: Tapi itu klip konyol dari - apakah itu CSI, di mana mereka memiliki
jumlah yang terlalu besar untuk alamat IP.
>> ROB Bowden: Setiap pertanyaan tentang ini?
Yang berikutnya, perubahan begitu lengkap dalam topic, tapi kami memiliki array yang ini PHP untuk
rumah-rumah di quad.
Dan kami memiliki daftar unordered.
Dan kita ingin mencetak setiap item daftar hanya berisi nama rumah.
Jadi kita memiliki loop foreach.
Jadi ingat, sintaks foreach array sebagai item dalam array.
Jadi melalui setiap iterasi dari loop, rumah akan mengambil salah satu
nilai-nilai dalam array.
>> Pada iterasi pertama, rumah akan Cabot House.
Pada iterasi kedua, rumah akan menjadi Courier rumah dan sebagainya.
Jadi untuk setiap quad sebagai rumah, kami hanya akan mencetak -
Anda juga bisa bergema -
item daftar dan kemudian nama rumah itu dan kemudian tutup item daftar.
Kurung kurawal adalah opsional di sini.
>> Dan kemudian kita juga mengatakan dalam pertanyaan sendiri, ingatlah untuk menutup
unordered tag daftar.
Jadi kita perlu untuk keluar dari mode PHP dalam rangka untuk melakukan hal ini.
Atau kita bisa menggemakan menutup unordered daftar tag.
>> DAVID J. Malan: Juga baik saja di sini akan telah menggunakan sekolah tua untuk
loop dengan $ i = 0 0 dan menggunakan jumlah untuk mengetahui panjang dari sinar.
Benar-benar baik juga, hanya a wordier sedikit.
>> AUDIENCE: Jadi, jika Anda akan [Tak terdengar], yang akan Anda lakukan -
Aku lupa apa loop [Tak terdengar] adalah.
Apakah Anda $ quad braket i?
>> DAVID J. Malan: Tepat.
Ya, persis.
>> ROB Bowden: Ada lagi?
>> DAVID J. Malan: Baiklah.
Trade-offs.
Jadi ada tandan jawaban mungkin bagi masing-masing.
Kami benar-benar hanya mencari sesuatu yang menarik untuk terbalik dan
kerugian.
Dan nomor 16 bertanya, memvalidasi pengguna ' masukan client-side, seperti JavaScript,
bukan server-side, seperti PHP.
Jadi apa terbalik dari melakukan client-side?
>> Nah, salah satu hal yang kami usulkan adalah bahwa Anda mengurangi latency, karena Anda
tidak perlu repot menghubungi server, yang mungkin memakan waktu beberapa
milidetik atau bahkan beberapa detik dengan menghindari itu dan hanya
memvalidasi pengguna masukan client-side oleh memicu handler on-mengirimkan dan
hanya memeriksa, apakah mereka ketik sesuatu dalam nama?
Apakah mereka mengetik sesuatu di alamat email?
Apakah mereka memilih asrama dari menu drop-down?
>> Anda dapat memberi mereka umpan balik seketika menggunakan komputer gigahertz
atau apapun yang mereka miliki itu benar-benar di meja mereka.
Jadi itu hanya pengguna yang lebih baik mengalami biasanya.
Tapi downside melakukan client-side validasi, jika Anda melakukannya tanpa juga
melakukan validasi server-side adalah bahwa kebanyakan orang keluar dari CS50 tahu
bahwa Anda hanya dapat mengirim data apapun yang Anda inginkan ke server berbagai cara.
Terus terang, di sebagian besar browser apapun, Anda dapat klik di dalam pengaturan dan hanya
mematikan JavaScript, yang akan, Oleh karena itu, menonaktifkan segala bentuk
validasi.
>> Tapi Anda juga mungkin ingat bahwa bahkan aku melakukan beberapa hal misterius di kelas menggunakan
telnet dan benar-benar berpura-pura menjadi browser dengan mengirimkan get
permintaan ke server.
Dan itu tentu tidak menggunakan JavaScript.
Itu hanya saya mengetik perintah pada keyboard.
Jadi benar-benar, setiap programmer dalam cukup kenyamanan dengan web dan HTTP
bisa mengirim data apa pun yang dia inginkan ke server tanpa validasi.
Dan jika server Anda tidak juga memeriksa, mereka memberi saya sebuah nama, adalah
ini benar-benar alamat email yang valid, melakukan mereka memilih asrama, Anda mungkin berakhir
up memasukkan palsu atau hanya data yang kosong ke dalam database Anda, yang mungkin
tidak akan menjadi hal yang baik jika Anda asumsi itu ada di sana.
>> Jadi ini merupakan realitas menjengkelkan.
Tapi secara umum, client-side validasi besar.
Tapi itu berarti dua kali lebih banyak pekerjaan.
Meskipun ada memang ada berbagai perpustakaan, perpustakaan JavaScript untuk
Misalnya, yang membuat ini banyak, apalagi sakit kepala.
Dan Anda dapat menggunakan kembali beberapa kode server-side, client-side.
Tapi jangan menyadari bahwa itu biasanya pekerjaan tambahan.
Ya.
>> AUDIENCE: Jadi jika kita hanya mengatakan kurang aman -
>> DAVID J. Malan: [TERTAWA]
Ugh.
Mereka adalah selalu sulit yang mengadili.
>> ROB Bowden: Itu akan telah diterima.
>> DAVID J. Malan: Apa?
>> ROB Bowden: saya buat masalah ini.
Itu akan telah diterima.
>> DAVID J. Malan: Ya.
>> AUDIENCE: Cool.
>> ROB Bowden: Tapi kita tidak menerima untuk pertama -
baik, apa yang kita cari adalah sesuatu seperti Anda tidak perlu
berkomunikasi dengan server.
Kami tidak menerima hanya lebih cepat.
>> AUDIENCE: Bagaimana tidak kembali halaman?
>> ROB Bowden: Ya.
Itu adalah jawaban yang diterima.
>> DAVID J. Malan: Apa pun di mana kami merasa itu lebih mungkin daripada tidak mungkin
bahwa Anda tahu apa yang Anda mengatakan, yang sulit
line untuk menarik kadang-kadang.
Menggunakan linked list sebagai gantinya array untuk mempertahankan
diurutkan daftar bilangan bulat.
Jadi terbalik kita sering mengutip dengan dihubungkan daftar yang memotivasi seluruh mereka
pengantar adalah Anda mendapatkan dinamisme.
Mereka bisa tumbuh.
Mereka dapat menyusut.
Jadi Anda tidak harus melompat melalui lingkaran untuk benar-benar membuat lebih banyak memori
dengan array.
Atau Anda tidak perlu hanya mengatakan, maaf, pengguna.
Array diisi.
Pertumbuhan sangat dinamis dari daftar.
Sebuah Kelemahan meskipun dari daftar terkait?
>> AUDIENCE: Ini linear.
Pencarian di linked list adalah linier bukan apa yang Anda log in
>> DAVID J. Malan: Tepat.
Mencari pada linked list adalah linier, bahkan jika itu diurutkan, karena Anda dapat
hanya mengikuti remah roti ini, ini pointer, dari awal daftar
sampai akhir.
Anda tidak dapat memanfaatkan akses acak dan, dengan demikian, pencarian biner, bahkan jika itu
diurutkan, bahwa Anda bisa lakukan dengan array.
Dan ada juga biaya lain.
Ya.
>> AUDIENCE: Memory tidak efisien?
>> DAVID J. Malan: Ya.
Yah, aku tidak akan selalu mengatakan tidak efisien.
Tapi itu biaya lebih banyak memori, karena Anda perlu 32 bit untuk setiap
node untuk pointer tambahan, di setidaknya untuk daftar tunggal linked.
Sekarang, jika Anda hanya menyimpan bilangan bulat dan Anda menambahkan pointer, itu
sebenarnya jenis non-sepele.
Ini dua kali lipat jumlah memori.
Namun pada kenyataannya, jika Anda menyimpan linked list dari structs yang mungkin memiliki
8 byte, 16 byte, bahkan lebih Selain itu, mungkin itu kurang
dari biaya marjinal.
Tapi itu biaya tetap.
Jadi salah satu dari mereka akan sudah baik-baik saja sebagai kerugian.
>> 18.
Menggunakan PHP bukannya C untuk menulis program baris perintah.
Jadi di sini, sering lebih cepat untuk menggunakan bahasa seperti PHP atau Ruby atau Python.
Anda hanya cepat membuka up editor teks.
Anda memiliki lebih banyak fungsi tersedia untuk Anda.
PHP memiliki wastafel dapur fungsi, sedangkan di C, Anda
memiliki sangat, sangat sedikit.
Bahkan, orang-orang yang tahu cara yang keras bahwa Anda tidak memiliki tabel hash.
Anda tidak mengaitkan daftar.
Jika Anda ingin orang-orang, Anda harus menerapkannya sendiri.
>> Jadi salah satu terbalik PHP atau benar-benar ada bahasa ditafsirkan adalah kecepatan yang
dengan mana Anda dapat menulis kode.
Tapi sisi negatifnya, kami melihat ini ketika saya cepat melecut misspeller a
implementasi dalam kuliah menggunakan PHP, adalah bahwa menggunakan bahasa ditafsirkan
biasanya lebih lambat.
Dan kita melihat bahwa terbukti dengan peningkatan waktu dari 0,3 detik sampai 3
detik, karena penafsiran yang benar-benar terjadi.
>> Terbalik lain adalah bahwa Anda tidak perlu melakukan kompilasi.
Jadi juga mempercepat pembangunan kebetulan, karena Anda tidak memiliki
dua langkah untuk menjalankan program.
Anda hanya memiliki satu.
Dan itu cukup menarik juga.
Menggunakan database SQL bukan file CSV untuk menyimpan data.
Database Jadi SQL digunakan untuk pset7.
File CSV Anda tidak menggunakan banyak.
Tapi Anda menggunakannya secara tidak langsung dalam pset7 sebagai baik dengan berbicara dengan Yahoo Finance.
>> Tapi CSV adalah seperti file Excel namun super sederhana, di mana kolom yang
hanya ditandai saja dengan koma dalam dari file text sebaliknya.
Dan menggunakan database SQL sedikit lebih menarik.
Ini terbalik, karena Anda mendapatkan sesuatu seperti memilih dan menyisipkan dan menghapus.
Dan Anda mendapatkan, mungkin, indeks yang MySQL dan database lainnya, seperti
Oracle, membangun untuk Anda dalam memori, yang berarti pilih Anda mungkin tidak
akan linear atas ke bawah.
Ini benar-benar akan menjadi sesuatu seperti pencarian biner atau sesuatu
serupa semangatnya.
Jadi mereka biasanya lebih cepat.
>> Tapi sisi negatifnya adalah bahwa itu hanya lebih banyak pekerjaan.
Ini lebih banyak usaha.
Anda harus memahami database.
Anda harus mengaturnya.
Anda memerlukan server untuk menjalankan bahwa database on.
Anda perlu memahami cara mengkonfigurasinya.
Jadi ini hanya ini macam trade-offs.
Sedangkan file CSV, Anda dapat menciptakannya dengan gedit.
Dan Anda baik untuk pergi.
Tidak ada kompleksitas di luar itu.
>> Menggunakan trie bukan tabel hash dengan chaining terpisah untuk menyimpan
kamus kata-kata mengingatkan dari pset5.
Jadi mencoba terbalik, dalam teori setidaknya, adalah apa?
Waktu yang konstan, setidaknya jika Anda hashing pada masing-masing individu
huruf dalam kata, seperti Anda mungkin untuk pset5.
Yang mungkin lima hash, enam hash jika ada lima atau enam
huruf dalam kata.
Dan itu cukup bagus.
Dan jika ada batas atas bagaimana panjang kata-kata Anda mungkin, itu
waktu memang asimtotik konstan.
>> Sedangkan tabel hash dengan terpisah chaining, masalahnya di sana dengan yang
jenis struktur data adalah bahwa kinerja algoritma Anda biasanya
tergantung pada beberapa hal sudah dalam struktur data.
Dan itu pasti terjadi dengan rantai, dimana lebih banyak barang yang Anda masukkan
ke dalam tabel hash, semakin lama mereka rantai pergi, yang berarti di terburuk
kasus, hal yang Anda mungkin akan mencari adalah sepanjang jalan di ujung salah satu
dari orang-orang rantai, yang secara efektif devolves menjadi sesuatu yang linear.
>> Sekarang, dalam prakteknya, itu bisa benar-benar menjadi kasus bahwa tabel hash dengan
rantai lebih cepat dari yang sesuai implementasi trie.
Tapi itu karena berbagai alasan, antara yang mencoba menggunakan seluruh banyak
memori yang dapat, pada kenyataannya, hal-hal yang lambat down, karena Anda tidak mendapatkan bagus
manfaat sesuatu yang disebut caching, di mana hal-hal yang berdekatan
dalam memori dapat diakses sering lebih cepat.
Dan kadang-kadang Anda bisa datang dengan fungsi hash yang benar-benar baik.
Bahkan jika Anda perlu membuang sedikit memori, Anda mungkin, memang, dapat
menemukan hal-hal yang cepat dan tidak seburuk linear.
>> Jadi singkatnya, tidak ada tentu dengan salah satu satu atau bahkan dua
hal-hal tertentu yang kita cari.
Benar-benar sesuatu yang persuasif sebagai terbalik dan downside
umumnya tertangkap mata kita.
>> ROB Bowden: Jadi untuk terbalik, kita lakukan tidak menerima sendiri "lebih cepat." Anda
harus mengatakan sesuatu tentang hal itu.
Bahkan jika Anda mengatakan secara teoritis lebih cepat, kami tahu bahwa Anda jenis dipahami
bahwa itu 0 dari 1.
Dan tabel hash, dalam teori, tidak 0 dari 1.
Menyebutkan apa-apa tentang runtime umumnya punya Anda poin.
Tapi "lebih cepat," sebagian besar solusi pada papan besar yang mencoba yang
obyektif lambat dari solusi yang tabel hash.
Jadi lebih cepat dalam dan dari dirinya sendiri tidak sepenuhnya benar.
>> DAVID J. Malan: Dom dom dom de.
Saya mungkin satu-satunya yang menyadari itulah cara yang seharusnya
diucapkan, kan?
>> ROB Bowden: aku benar-benar tidak tahu.
>> DAVID J. Malan: Itu membuat akal di kepala saya.
>> ROB Bowden: Aku melakukan yang satu ini.
OK.
Jadi ini adalah satu di mana Anda harus menarik diagram yang mirip dengan Anda mungkin
telah melihat di masa lalu ujian.
Jadi mari kita lihat ini.
Jadi dari node HTML, kita memiliki dua anak-anak, kepala dan tubuh.
Jadi kita cabang - kepala dan tubuh.
Kepala memiliki tag judul.
Jadi kita memiliki judul.
>> Sekarang, satu hal yang banyak orang lupa adalah bahwa node teks ini
elemen-elemen dalam pohon ini.
Jadi di sini kita terjadi untuk menarik mereka sebagai oval untuk membedakan mereka dari ini
jenis node.
Tapi perhatikan juga di sini kita memiliki top, tengah, dan bawah akan berakhir menjadi
node teks.
Jadi lupa mereka agak dari kesalahan umum.
>> Tubuh memiliki tiga anak - tiga divs.
Jadi div, div, div dan kemudian teks anak simpul tersebut divs.
Itu cukup banyak itu untuk itu pertanyaan.
>> DAVID J. Malan: Dan perlu dicatat, meskipun kita tidak memikirkan ini
rincian dalam waktu yang kita habiskan untuk JavaScript, bahwa perintah tersebut tidak, dalam
Bahkan, masalah teknis.
Jadi jika kepala datang sebelum tubuh dalam HTML, maka akan muncul ke
meninggalkan tubuh dalam DOM yang sebenarnya.
Bahwa itu adalah, pada umumnya, hanya FYI, sesuatu yang disebut urutan dokumen, di mana
itu penting.
Dan jika Anda menerapkan parser, sebuah program yang membaca HTML di gedung
atas pohon dalam memori, jujur, yang intuitif mungkin apa yang Anda
melakukan pula - atas ke bawah, kiri ke kanan.
>> ROB Bowden: Pertanyaan itu?
Yang harus saya lakukan berikutnya?
>> DAVID J. Malan: Tentu.
>> ROB Bowden: OK.
Jadi ini adalah buffer overrun Pertanyaan serangan.
Hal utama untuk mengenali sini adalah, baik, bagaimana mungkin trik musuh
program ini ke dalam mengeksekusi kode sewenang-wenang?
Jadi argv1, baris perintah pertama argumen untuk program ini, yang dapat
sewenang-wenang panjang.
Tapi di sini kita menggunakan memcpy untuk menyalin argv1, yang di sini adalah bar.
Kami melewati sebagai argumen.
Dan itu berlangsung pada nama bar.
>> Jadi kita memcpying bar ke dalam buffer ini c.
Berapa banyak byte yang kita menyalin?
Nah namun banyak byte bar terjadi menggunakan, panjang argumen itu.
Tapi c hanya 12 byte lebar.
Jadi jika kita ketik argumen baris perintah itu lebih dari 12 byte, kita
akan meluap ini penyangga tertentu.
Sekarang, bagaimana mungkin musuh mengelabui program ke mengeksekusi kode sewenang-wenang?
>> Jadi ingat bahwa di sini utama memanggil foo.
Dan kemudian panggilan utama foo.
Mari kita menggambar ini.
Jadi kita memiliki tumpukan kami.
Dan utama memiliki stack frame di bagian bawah.
Pada titik tertentu, panggilan utama foo.
Nah, segera, panggilan utama foo.
Dan foo mendapat stack frame sendiri.
>> Sekarang, di beberapa titik, foo akan kembali.
Dan pergi kembali foo, kita perlu tahu di apa baris kode dalam kita utama
adalah untuk mengetahui di mana kita harus melanjutkan dalam utama.
Kita bisa memanggil foo dari keseluruhan banyak tempat yang berbeda.
Bagaimana kita tahu di mana untuk kembali?
Nah, kita perlu menyimpan tempat itu.
>> Jadi suatu tempat yang benar di sini, kami menyimpan di mana kita harus kembali untuk sekali
kembali foo.
Dan ini adalah alamat pengirim.
Jadi bagaimana musuh mungkin mengambil keuntungan ini adalah kenyataan bahwa
penyangga ini c disimpan, mari kita mengatakan, di sini adalah c.
Jadi kita punya 12 byte untuk c.
Ini adalah c.
Dan ini adalah tumpukan cincin foo itu.
Jadi, jika pengguna jahat masuk lebih byte dari 12 atau mereka memasukkan perintah
argumen baris yang lebih dari 12 karakter, maka kita akan
meluap penyangga ini.
>> Kita bisa terus berjalan.
Dan di beberapa titik, kita pergi jauh cukup bahwa kita mulai
Timpa alamat pengirim ini.
Jadi sekali kita menimpa alamat pengirim, ini berarti bahwa ketika foo
kembali, kita kembali ke mana pun pengguna berbahaya memberitahu untuk oleh
nilai apa pun itu masuk, dengan cara apa pun karakter pengguna masuk.
Dan jadi jika pengguna jahat sedang sangat cerdas, ia dapat memiliki ini
kembali ke suatu tempat di printDef fungsi atau suatu tempat di malloc
fungsi, hanya di mana saja sewenang-wenang.
>> Tetapi bahkan lebih pintar adalah bagaimana jika ia memiliki pengguna kembali ke sini.
Dan kemudian Anda mulai menjalankan ini sebagai baris kode.
Jadi pada saat itu, pengguna dapat memasukkan apapun yang dia inginkan ke wilayah ini.
Dan ia memiliki kontrol penuh atas program Anda.
Pertanyaan itu?
Jadi pertanyaan berikutnya adalah lengkap implementasi ulang dari foo sedemikian rupa
bahwa itu tidak lagi rentan.
>> Jadi ada beberapa cara Anda bisa melakukan ini.
Kami masih memiliki c hanya menjadi panjang 12.
Anda bisa mengubah ini sebagai bagian dari solusi Anda.
Kami juga menambahkan cek untuk membuat yakin bar tidak null.
Meskipun Anda tidak perlu bahwa untuk kredit penuh.
Jadi kita memeriksa pertama panjang string dari bar.
Jika itu lebih besar dari 12, maka tidak benar-benar melakukan salin.
Jadi itulah salah satu cara untuk memperbaikinya.
>> Cara lain untuk memperbaiki itu bukan memiliki c hanya menjadi panjang 12, memilikinya
menjadi panjang strlen (bar).
Cara lain untuk memperbaiki itu untuk benar-benar hanya kembali.
Jadi jika Anda baru saja sudah menyingkirkan semua ini, jika Anda baru saja menghapus semua
baris kode, Anda akan mendapatkan kredit penuh, karena fungsi ini
tidak benar-benar mencapai apa-apa.
Ini menyalin baris perintah Argumen ke dalam beberapa array dalam
stack frame lokalnya.
Dan kemudian hal itu kembali.
Dan apa pun yang dicapai hilang.
Jadi kembali juga cukup cara mendapatkan kredit penuh.
>> DAVID J. Malan: Tidak cukup semangat dari pertanyaan tetapi dapat diterima per
spek tetap.
>> ROB Bowden: Pertanyaan tentang semua itu?
Satu hal yang Anda setidaknya diperlukan untuk memiliki kode kompilasi.
Jadi meskipun secara teknis Anda tidak rentan jika kode Anda tidak
kompilasi, kami tidak menerima itu.
Tidak ada pertanyaan?
OK.
>> DAVID J. Malan: Apakah Anda ingin mengatakan judul ini?
>> ROB Bowden: No
>> DAVID J. Malan: Jadi dalam satu ini, ini entah kabar baik atau kabar buruk.
Ini adalah benar-benar masalah yang sama sebagai kuis pertama.
Dan itu hampir sama masalah seperti pset1.
Tapi itu memang sengaja disederhanakan menjadi piramida sederhana, salah satu yang dapat
dipecahkan dengan sedikit iterasi sederhana.
Dan sungguh, apa yang kita mendapatkan di di sini tidak begitu banyak logika,
karena mungkin, pada titik ini, Anda lebih nyaman daripada Anda
dalam satu minggu dengan untuk loop atau mengapa loop, tapi benar-benar untuk menggoda selain yang
Anda sedikit nyaman dengan gagasan bahwa PHP tidak hanya tentang apa yang
pemrograman.
Hal ini sebenarnya dapat digunakan sebagai bahasa untuk menulis program baris perintah.
>> Dan memang, itulah yang kita mencoba untuk menarik perhatian Anda untuk.
Ini adalah program baris perintah PHP.
Jadi kode C di sini, sementara yang benar di C, tidak benar untuk PHP.
Tapi kode yang benar-benar sama.
Jika Anda membandingkan solusi untuk Quiz 0 melawan Quiz 1, Anda akan menemukan bahwa
itu hampir sama, kecuali untuk beberapa tanda-tanda dolar dan untuk
tidak adanya tipe data.
Secara khusus, jika kita lihat di sini, Anda akan melihat bahwa kita iterate, dalam hal ini
kasus, dari 1 sampai sampai 7.
>> Kita bisa melakukannya 0 indeks.
Tapi kadang-kadang, saya pikir itu hanya mental lebih mudah untuk berpikir tentang hal-hal
dari 1 sampai 7.
Jika Anda ingin satu blok, kemudian dua blok, lalu tiga, lalu
dot, dot, dot tujuh.
Kami telah j diinisialisasi ke 1 dan kemudian mengandalkan hingga i.
Dan semuanya di sini dinyatakan identik.
Tapi patut dicatat adalah beberapa hal.
Kami memberikan dua baris, ini pertama satu, tolol disebut sebagai peristiwa yang
untuk tajam Bang.
Dan itu hanya menentukan jalan, yang folder, di mana sebuah program dapat
menemukan bahwa Anda ingin menggunakan untuk menafsirkan file ini.
>> Dan kemudian garis setelah itu, dari Tentu saja, berarti masuk ke mode PHP.
Dan garis di bagian paling bawah berarti modus exit PHP.
Dan ini bekerja, secara umum, dengan menafsirkan bahasa.
Ini semacam menjengkelkan jika Anda menulis Program dalam sebuah file bernama foo.php.
Dan kemudian pengguna harus hanya ingat, OK, untuk menjalankan program ini, saya
harus mengetik "ruang php foo.php." Jenis menjengkelkan jika tidak ada lagi.
Dan itu juga mengungkapkan bahwa program anda ditulis dalam PHP, yang tidak semua
yang menerangi bagi pengguna.
>> Jadi, Anda dapat menghapus php. Sama sekali ingat dari kuliah.
Dan Anda benar-benar bisa melakukannya. / Foo jika Anda telah chmodded itu dengan membuat
executable.
Jadi chmod a + x foo akan melakukan itu.
Dan jika Anda juga menambahkan peristiwa di sini.
Tapi sungguh, masalah mulai di mencetak sesuatu seperti ini.
Tidak ada HTML, tidak ada C-kode tentu, hanya beberapa PHP.
Jadi Milo kemudian dikembalikan dalam masalah 25.
Dan pada 25, Anda diberi berikut kode kerangka, yang merupakan
Halaman web cukup sederhana.
Dan bagian berair HTML-bijaksana turun di sini, di mana kita memiliki di dalam tubuh
bentuk yang memiliki ID unik input dalam yang dua input, satu
dengan ide nama, salah satu dengan ide tombol.
>> Yang pertama adalah jenis teks, kedua tipe kirimkan.
Dan jadi kami memberi Anda, sebenarnya, lebih bahan dari yang Anda butuhkan, hanya begitu
kalian punya pilihan dengan yang untuk memecahkan masalah ini.
Anda tidak benar-benar perlu semua ID ini.
Tetapi memungkinkan Anda untuk memecahkan dengan cara yang berbeda.
Dan di atas, perhatikan bahwa tujuannya adalah untuk memicu
jendela seperti ini -
Halo, Milo -
untuk pop up di browser menggunakan super sederhana, jika
tidak jelek, fungsi alert.
Jadi, pada akhirnya, ini bermuara konseptual entah bagaimana mendengarkan
pengiriman dari client-side bentuk , Bukan server-side, entah bagaimana
menanggapi pengajuan tersebut dengan meraih nilai bahwa pengguna mengetik
di ke kolom nama, dan kemudian menampilkannya dalam tubuh peringatan.
>> Jadi salah satu cara yang dapat Anda lakukan adalah dengan jQuery, yang terlihat sedikit
sintaksis membingungkan pada awalnya.
Anda dapat melakukan ini dengan kode DOM murni - document.getelement oleh ID.
Tapi mari kita lihat versi ini.
Saya memiliki beberapa penting baris pertama.
Jadi salah satu, kita memiliki baris ini, yang merupakan identik dengan apa yang Anda mungkin telah melihat
dalam, saya percaya, form2.html dari kelas di minggu 9.
Dan ini hanya mengatakan, jalankan kode berikut ketika
dokumen siap.
Hal ini menjadi penting hanya karena Halaman HTML dibaca atas ke
bawah, kiri ke kanan.
>> Dan karena itu, jika Anda mencoba untuk melakukan sesuatu dalam kode di sini beberapa DOM
elemen, beberapa tag HTML, itu turun di sini, Anda melakukannya terlalu cepat,
karena ini bahkan tidak memiliki telah dibaca ke dalam memori.
Jadi dengan mengatakan document.ready ini line, kami katakan,
inilah beberapa kode, peramban.
Tapi jangan mengeksekusi ini sampai keseluruhan dokumen sudah siap, yaitu DOM
pohon ada dalam memori.
Yang satu ini sedikit lebih sederhana, jika sebuah sintaksis
sedikit berbeda, di mana saya katakan, ambil elemen HTML yang unik
identifier adalah input.
Itulah yang tag hash menunjukkan, ID unik.
Dan kemudian aku menelepon. Kirimkan.
>> Jadi. Mengirimkannya disini adalah fungsi, jika tidak dikenal sebagai sebuah metode, yang
dalam obyek di kiri sisi ada yang saya tidak menyorot.
Jadi jika Anda berpikir input sebagai obyek dalam memori - dan memang itu.
Ini adalah simpul di pohon -
. Menyerahkan berarti ketika formulir ini dengan ID ini disampaikan, jalankan
kode berikut.
Saya tidak peduli apa nama Fungsi adalah aku mengeksekusi.
Jadi di sini saya menggunakan, seperti sebelumnya, apa disebut fungsi lambda atau
fungsi anonim.
Ini sama sekali tidak intelektual menarik selain tidak memiliki nama,
yang baik-baik saja jika Anda hanya pernah akan menyebutnya sekali.
Dan di dalam sana saya benar-benar menangani penyerahan formulir.
Saya pertama kali mendeklarasikan variabel disebut nilai.
Dan kemudian apa efek ini disorot porsi di sini sekarang?
Apa yang melakukan pada tingkat tinggi untuk saya?
>> AUDIENCE: Ia mendapat nilai yang pengguna tidak dalam HTML di bawah ini.
Ia mendapat ID itu dan kemudian menemukan nilai itu.
>> DAVID J. Malan: Tepat.
Ini meraih node, yang unik identifier adalah nama.
Ia mendapat nilai di dalamnya, yang adalah, mungkin, apa yang user
diketik dirinya sendiri.
Dan kemudian menyimpan bahwa dalam variabel yang disebut nilai.
Sebagai samping, Anda bisa memiliki juga melakukan ini sedikit berbeda.
Benar-benar dapat diterima dengan melakukan sesuatu Nilai kebohongan var mendapat
document.getElementById.
Dan inilah mengapa itu sedikit membosankan untuk tidak menggunakan jQuery.
"Nama" value..
Jadi benar-benar diterima.
Berbagai cara untuk melakukan hal ini. jQuery hanya cenderung menjadi sedikit lebih ringkas dan
pasti lebih populer antara programmer.
>> Sekarang, aku melakukan sedikit kewarasan cek, karena dalam masalah
Pernyataan kita secara eksplisit mengatakan, jika pengguna belum mengetik nya
nama, tidak menunjukkan tanda.
Tapi Anda dapat memeriksa untuk itu, dengan hanya memeriksa string kosong untuk
kutipan-tanda kutip jika ada tidak benar-benar ada.
Tapi kalau itu tidak sama dengan kutipan-tanda kutip, Saya ingin menelepon alert.
Dan bagian yang menarik di sini adalah bahwa kita sedang menggunakan operator plus, yang
melakukan apa di JavaScript?
Menggabungkan.
Jadi seperti PHPs dot operator.
Ide yang sama, sintaks yang sedikit berbeda.
Dan aku hanya membuat string yang Anda lihat di screen shot -
Halo, begitu dan begitu.
>> Dan kemudian detail terakhir adalah ini.
Mengapa saya kembali dalam palsu fungsi anonim ini?
>> AUDIENCE: Tidak ada nilai.
Anda memasukkannya ke dalam form.
Ini hanya mengatakan, jika nilai tidak sama dengan kosong, maka lakukanlah.
Ada kosong dalam pengajuan itu.
>> DAVID J. Malan: OK.
Hati-hati sekalipun.
Tidak ada orang lain di sini.
Dan bahwa return false luar dari jika kondisi.
Jadi ini menyoroti jalur, kembali palsu, mengeksekusi apa pun ketika
formulir tersebut diajukan.
Apa kembali dalam palsu ini event handler, seperti disebut,
acara tersebut menjadi penyerahan?
>> AUDIENCE: Karena hanya terjadi sekali.
>> DAVID J. Malan: Hanya terjadi sekali.
Tidak cukup.
Ya?
>> AUDIENCE: Ini mencegah bentuk dari mengirimkan ke perilaku default,
yang akan membuat halaman reload.
>> DAVID J. Malan: Tepat.
Jadi aku overloading istilah mengirimkannya disini, karena saya katakan, bentuknya adalah
yang diajukan.
Tapi seperti yang Anda sarankan, itu sebenarnya tidak telah disampaikan dengan cara yang benar HTTP.
Ketika Anda klik Submit, karena kami handler onSubmit, kami mencegat
bahwa pengiriman formulir sehingga untuk berbicara.
Kami kemudian melakukan hal yang kita dengan kode JavaScript.
Tapi aku sengaja kembali palsu, karena apa yang saya tidak ingin terjadi suatu
Sepersekian detik kemudian adalah untuk bentuk keseluruhan sendiri untuk diserahkan ke web
Server dengan pasangan nilai kunci dengan mengubah URL menjadi sesuatu seperti
q = kucing atau apa pun yang kita lakukan, misalnya, di kelas.
Saya tidak ingin hal itu terjadi, karena tidak ada server yang mendengarkan untuk ini
membentuk pengajuan.
Ini murni dilakukan dalam kode JavaScript.
Dan itulah mengapa saya bahkan tidak memiliki tindakan atribut pada formulir saya, karena saya
tidak berniat untuk ini pernah pergi ke server.
>> Jadi itu sedang diajukan.
Tapi kami mencegat bentuk yang pengajuan dan mencegah default
perilaku, yang sebenarnya adalah untuk pergi semua jalan ke server.
>> AUDIENCE: Jadi menjaga sisi klien.
>> DAVID J. Malan: Menjaga itu client-side.
Tepat.
Berikutnya adalah saya oh MySQL.
>> ROB Bowden: OK.
Jadi pertanyaan pertama ini umumnya kasar bagi orang-orang.
Meskipun yang kemudian pergi lebih baik.
Jadi Anda harus memilih data yang benar jenis untuk kedua kolom ini.
Dan kedua hal ini memiliki beberapa hal-hal tentang mereka yang
membuat pilihan sulit.
Jadi int tidak valid ketik nomor.
Alasannya karena rekening 12 digit jumlah, int tidak cukup besar untuk
menyimpan jumlah digit.
Jadi pilihan yang valid akan menjadi besar int jika Anda kebetulan tahu itu.
Pilihan lain bisa saja bidang char panjang 12.
Jadi salah satu dari mereka akan bekerja.
Int tidak.
>> Sekarang, keseimbangan, pikirkan kembali pset7.
Jadi kami secara khusus digunakan untuk desimal menyimpan nilai saham atau -
>> DAVID J. Malan: Cash.
>> ROB Bowden: Cash.
Kami menggunakan desimal untuk menyimpan jumlah kas bahwa pengguna saat ini memiliki.
Jadi alasan kita melakukan itu adalah karena, ingat, mengapung.
Ada floating point dalam presisi.
Hal ini tidak bisa tepat menyimpan uang tunai nilai-nilai seperti yang kita inginkan di sini.
Jadi desimal mampu tepatnya toko sesuatu untuk, katakanlah, dua tempat desimal.
Itu sebabnya keseimbangan, kita inginkan menjadi desimal dan tidak mengambang.
>> DAVID J. Malan: Dan juga, juga, meskipun mungkin telah pintar dalam lainnya
konteks untuk berpikir, mungkin ini adalah kesempatan untuk int.
Aku hanya akan melacak hal dalam uang.
Karena kita secara eksplisit menunjukkan default nilai menjadi 100,00, yang
berarti itu hanya bisa menjadi int.
Dan kehalusan lain juga dengan nomor adalah bahwa hal itu tidak dimaksudkan
menjadi pertanyaan jebakan.
Tapi ingat bahwa int di MySQL, seperti di C, setidaknya dalam
alat, adalah 32-bit.
Dan meskipun kami tidak mengharapkan Anda untuk tahu persis berapa banyak digit yang
berarti, ingat bahwa jumlah terbesar Anda dapat mewakili berpotensi
dengan nomor 32-bit kira-kira apa?
>> Nomor berapa yang kita selalu katakan?
2 ke 32, yang adalah apa kira-kira?
Anda tidak perlu tahu persis.
Tapi kira-kira sangat membantu dalam kehidupan.
Ini kira-kira 4 miliar.
Jadi kami mengatakan bahwa beberapa kali.
Aku tahu aku telah mengatakan bahwa beberapa kali.
Dan itu adalah sekitar 4 miliar.
Dan itu adalah aturan yang baik praktis untuk mengetahui.
Jika Anda memiliki 8 bit, 256 adalah angka ajaib.
Jika Anda memiliki 32 bit, 4 miliar memberi atau mengambil.
Jadi jika Anda hanya menuliskan 4 miliar, Anda akan melihat bahwa itu lebih sedikit dibandingkan angka
12, yang berarti itu jelas tidak cukup ekspresif untuk menangkap
Nomor rekening 12 digit.
>> ROB Bowden: OK.
Jadi yang lain pergi lebih baik.
Jadi misalkan bahwa bank membebankan $ 20 per bulan
Biaya pemeliharaan pada semua account.
Dengan apa SQL query bisa bank memotong $ 20 dari setiap hitungan, bahkan jika
itu menghasilkan beberapa saldo negatif?
Jadi pada dasarnya, ada empat jenis utama dari pertanyaan -
menyisipkan, pilih, update, dan menghapus.
Jadi apa yang kita pikir kita akan menggunakan di sini?
Perbarui.
>> Jadi mari kita lihat.
Jadi di sini kita update.
Apa tabel kita memperbarui account?
Jadi memperbarui account.
Dan kemudian sintaks mengatakan, apa yang dalam rekening kita memperbarui?
Nah, kita sedang menyiapkan keseimbangan sama dengan nilai saat ini keseimbangan minus 20.
Jadi ini akan memperbarui semua baris account, mengurangkan
$ 20 dari keseimbangan.
>> DAVID J. Malan: Sebuah kesalahan umum di sini, meskipun kadang-kadang kita memaafkan itu,
adalah untuk benar-benar memiliki kode PHP di sini memanggil fungsi permintaan atau menempatkan
tanda kutip segala sesuatu yang tidak perlu berada di sana.
>> ROB Bowden: Ingat bahwa MySQL adalah bahasa terpisah dari PHP.
Kami kebetulan menulis MySQL di PHP.
Dan PHP kemudian mengirimkannya ke server MySQL.
Tapi Anda tidak perlu PHP untuk berkomunikasi dengan server MySQL.
>> DAVID J. Malan: Tepat.
Jadi tidak ada variabel dengan tanda dolar harus dalam konteks ini.
Itu hanya dapat melakukan semua matematika dalam database itu sendiri.
>> ROB Bowden: OK.
Jadi yang berikutnya.
Apakah ini yang berikutnya?
Ya.
Jadi dengan apa SQL query bisa bank mengambil nomor rekening nya
pelanggan terkaya, orang-orang dengan saldo lebih dari 1.000?
Jadi yang dari empat jenis utama kita akan inginkan di sini?
Pilih.
Jadi kita ingin memilih.
Apa yang kita ingin memilih?
Apa kolom yang ingin kita pilih?
Kami akan secara khusus ingin untuk memilih nomor.
Tetapi jika Anda berkata star, kita juga menerima.
>> Jadi memilih nomor dari apa meja?
Account.
Dan kemudian kondisi yang kita inginkan?
Dimana keseimbangan yang lebih besar dari 1.000.
Kami juga diterima lebih besar dari atau sama.
Yang terakhir.
Dengan apa SQL query bisa bank dekat, yaitu, menghapus setiap account yang
memiliki saldo $ 0?
Jadi yang dari empat kita akan ingin untuk digunakan?
Hapus.
Jadi sintaks untuk itu?
Hapus dari apa meja?
Account.
Dan kemudian kondisi yang kita ingin menghapus -
di mana keseimbangan sama dengan nol.
Jadi menghapus semua baris dari rekening di mana keseimbangan adalah nol.
Pertanyaan pada salah satu?
Ingin antrian?
>> DAVID J. Malan: panduan Queue.
Jadi dalam satu ini, kami memberikan Anda agak Struktur akrab yang kami menjelajahi
bit di kelas bersama structs, yang data
struktur terkait dalam roh.
Perbedaan meskipun dengan antrian adalah bahwa kita harus entah bagaimana mengingat siapa
berada di depan antrian, dalam jumlah besar bagian sehingga kita bisa membuat lebih
efisiensi penggunaan memori, setidaknya jika kita menggunakan array.
>> Karena ingat, jika kita memiliki sebuah array, jika, misalnya, ini adalah bagian depan
antrian, jika saya masuk ke antrian di sini, dan kemudian seseorang akan sejalan
di belakang saya, di belakang saya, di belakang saya, dan satu orang melangkah keluar dari garis, Anda
bisa, seperti yang kita lihat beberapa manusia relawan di kelas, memiliki semua orang
pergeseran cara ini.
Tapi secara umum, setelah semua orang melakukannya sesuatu yang tidak penggunaan terbaik dari waktu
dalam sebuah program, karena itu berarti Anda algoritma berjalan dalam apa
waktu berjalan asimtotik?
Ini linear.
>> Dan aku merasa seperti itu agak bodoh.
Jika orang berikutnya sejalan adalah berikutnya orang yang seharusnya masuk ke
toko, mereka tidak semua memiliki untuk bergerak bersama-sama.
Biarkan orang itu dicabut off ketika saatnya tiba, misalnya.
Jadi kita bisa menghemat sedikit waktu di sana.
Dan untuk melakukan itu meskipun, berarti bahwa bahwa kepala antrian atau
depan antrian akan semakin bergerak lebih dalam dan lebih
ke dalam array dan akhirnya mungkin benar-benar membungkus jika kita menggunakan
array untuk menyimpan orang-orang dalam antrian ini.
Jadi Anda hampir dapat memikirkan array sebagai data melingkar
struktur dalam arti itu.
>> Jadi Anda entah bagaimana harus melacak ukuran itu atau benar-benar akhir itu
dan kemudian di mana awal itu.
Jadi kami mengusulkan bahwa Anda mendeklarasikan satu antrian tersebut, panggilan
q itu, hanya satu huruf.
Kemudian kami mengusulkan bahwa depan menjadi diinisialisasi ke nol dan bahwa ukuran
diinisialisasi ke nol.
>> Jadi sekarang, tidak ada dalam antrian itu.
Dan kami meminta Anda untuk menyelesaikan pelaksanaan enqueue di bawah ini dalam
sedemikian rupa sehingga fungsi menambahkan n untuk akhir q dan kemudian kembali benar.
Tetapi jika q penuh atau negatif, Fungsi malah harus kembali palsu.
Dan kami memberikan Anda beberapa asumsi.
Tapi mereka tidak benar-benar fungsional relevan, hanya bool yang ada,
karena, secara teknis, bool tidak ada di C kecuali jika Anda menyertakan
file header tertentu.
Sehingga hanya pastikan ada yang ada apakah ini trik
pertanyaan semacam itu.
>> Jadi enqueue, kami mengusulkan dalam sampel solusi untuk mengimplementasikan sebagai berikut.
Satu, kita periksa dulu kemudahan, buah tergantung rendah.
Jika antrian penuh atau nomor yang Anda mencoba untuk memasukkan kurang
dari nol, yang kami katakan dalam spesifikasi masalah harus
tidak diperbolehkan, karena kami hanya ingin nilai-nilai non-negatif, maka Anda harus
hanya return false segera.
Jadi beberapa relatif mudah kesalahan memeriksa.
Jika meskipun Anda ingin menambahkan bahwa sebenarnya nomor, Anda harus melakukan sedikit
berpikir di sini.
Dan ini adalah di mana itu sedikit mengganggu mental, karena Anda harus
mencari cara untuk menangani sampul.
>> Tapi kuman gagasan di sini itu dari menarik bagi kami adalah sampul yang
sering menyiratkan aritmatika modular dan operator mod, sisi persen,
di mana Anda dapat pergi dari nilai yang lebih besar kembali ke nol dan kemudian satu dan dua dan
tiga dan kemudian kembali sekitar ke nol, satu dan dua dan tiga dan sebagainya
lagi dan lagi.
Jadi cara kita mengusulkan melakukan hal ini adalah bahwa kita ingin indeks ke dalam
array disebut nomor mana bilangan bulat kita berbohong.
Tapi untuk sampai ke sana, pertama kita ingin lakukan apapun ukuran antrian tapi
kemudian menambahkan bahwa apapun depan daftar adalah.
Dan efek dari itu adalah untuk menempatkan kita di posisi yang tepat dalam antrian dan
tidak berasumsi bahwa orang pertama di baris adalah di awal, yang ia atau
dia benar-benar bisa jika kita juga menggeser semua orang.
Tapi kami hanya menciptakan pekerjaan untuk diri kita sendiri jika kita mengambil
bahwa jalan tertentu.
>> Jadi kita bisa tetap relatif sederhana.
Kami harus ingat bahwa kita hanya menambahkan int ke antrian.
Dan kemudian kita hanya kembali benar.
Sementara itu, dalam dequeue, kami bertanya Anda melakukan hal berikut.
Menerapkannya sedemikian rupa sehingga dequeues, yaitu menghapus dan kembali,
int di bagian depan antrian.
Untuk menghapus int, itu sudah cukup melupakannya.
Anda tidak perlu untuk menimpa bit nya.
Jadi itu masih benar-benar ada.
Sama seperti data pada hard drive, kami hanya mengabaikan fakta
bahwa itu sekarang ada.
Dan jika q kosong, kita harus bukannya kembali negatif 1.
Jadi ini terasa sewenang-wenang.
Mengapa kembali negatif 1 bukannya palsu?
Ya.
>> AUDIENCE: Q adalah menyimpan nilai-nilai positif.
Karena Anda hanya menyimpan nilai-nilai positif di q, negatif adalah kesalahan.
>> DAVID J. Malan: OK, benar.
Jadi karena kita hanya menyimpan positif nilai-nilai atau nol, maka tidak apa-apa untuk
mengembalikan nilai negatif sebagai sentinel a nilai, simbol khusus.
Tapi kau menulis ulang sejarah di sana, karena alasan kita hanya
kembali nilai-nilai non-negatif karena kita ingin
memiliki nilai sentinel.
Jadi lebih khusus, mengapa tidak hanya return false dalam kasus kesalahan?
Ya.
>> AUDIENCE: Anda telah gagal untuk kembali integer.
>> DAVID J. Malan: Tepat.
Dan ini adalah di mana C mendapat cukup menghambat.
Jika Anda mengatakan Anda akan untuk mengembalikan int, Anda punya
untuk mengembalikan int.
Anda tidak bisa mendapatkan mewah dan mulai kembali bool atau float atau
string atau sesuatu seperti itu.
Sekarang, sementara itu, JavaScript dan PHP dan beberapa bahasa lain bisa, pada kenyataannya,
Anda telah kembali berbeda jenis nilai.
Dan yang benar-benar dapat berguna, di mana Anda bisa kembali ints positif, nol,
ints negatif, atau salah atau null bahkan untuk menandakan kesalahan.
Tapi kita tidak memiliki fleksibilitas dalam C.
>> Jadi dengan dequeue, apa yang kita mengusulkan untuk lakukan adalah -
>> ROB Bowden: Anda dapat kembali palsu.
Hanya saja yang palsu adalah hash mendefinisikan palsu ke nol.
Jadi jika Anda kembali palsu, Anda kembali nol.
Dan nol adalah hal yang sah dalam antrian kami, sedangkan negatif 1 tidak jika
palsu kebetulan negatif 1.
Tapi Anda tidak harus bahkan perlu tahu itu.
>> DAVID J. Malan: Itu mengapa aku tidak mengatakannya.
>> ROB Bowden: Tapi itu tidak benar bahwa Anda tidak dapat kembali palsu.
>> DAVID J. Malan: Tentu.
Jadi dequeue, perhatikan kita menerima membatalkan sebagai argumen.
Dan itu karena kita tidak melewati sesuatu masuk
Kami hanya ingin menghapus elemen di bagian depan antrian.
Jadi bagaimana mungkin kita pergi untuk melakukan ini?
Yah, pertama, mari kita lakukan ini cek kewarasan cepat.
Jika ukuran antrian adalah 0, ada tidak ada pekerjaan yang harus dilakukan.
Kembali negatif 1.
Selesai.
Jadi itulah beberapa baris program saya.
Jadi hanya empat baris tetap.
>> Jadi di sini saya memutuskan untuk pengurangan ukuran.
Dan decrementing ukuran efektif berarti bahwa aku lupa
sesuatu di sana.
Tapi saya juga harus memperbarui mana depan nomor tersebut.
Jadi untuk melakukan itu, saya perlu untuk melakukan dua hal.
Saya pertama kali perlu mengingat apa nomor berada di depan antrian,
karena saya perlu kembali hal itu.
Jadi saya tidak ingin sengaja lupa tentang hal itu dan kemudian menimpa itu.
Aku hanya akan mengingat dalam int.
>> Dan sekarang, saya ingin memperbarui q.front untuk q.front +1.
Jadi jika ini adalah orang pertama di line, sekarang, saya ingin melakukan ditambah 1
menunjuk pada orang di baris berikutnya.
Tapi aku harus menangani sampul itu.
Dan jika kapasitas adalah konstanta global, yang akan memungkinkan saya untuk memastikan
seperti yang saya menunjuk ke orang yang sangat terakhir di line, operasi modulo akan membawa
saya kembali ke nol pada depan antrian.
Dan yang menangani sampul di sini.
Dan kemudian saya lanjutkan kembali n.
>> Sekarang, tegasnya, saya tidak harus menyatakan n.
Saya tidak harus mengambil dan menyimpannya sementara, karena nilai adalah
masih ada.
Jadi saya hanya bisa melakukan aritmatika yang tepat untuk mengembalikan mantan kepala
antrian.
Tapi aku hanya merasa bahwa ini adalah lebih jelas untuk benar-benar mengambil int, taruh
n, dan kemudian kembali bahwa demi kejelasan, tetapi
tidak benar-benar diperlukan.
Psst.
Mereka semua diucapkan di kepala saya.
>> ROB Bowden: Pertanyaan Jadi pertama adalah masalah pohon biner.
Jadi pertanyaan pertama adalah, kita diberikan angka-angka ini.
Dan kami ingin entah bagaimana memasukkan mereka ke dalam node ini sedemikian rupa sehingga merupakan
valid pohon pencarian biner.
Jadi satu hal yang perlu diingat tentang pohon pencarian biner adalah bahwa hal itu tidak
Hanya saja hal ke kiri kurang dan hal untuk
kanan lebih besar.
Perlu bahwa seluruh pohon ke kiri kurang, dan seluruh pohon
ke kanan lebih besar.
>> Jadi jika saya menempatkan 34 di sini di bagian atas, dan kemudian Aku meletakkan 20 di sini, jadi itu valid sehingga
jauh, karena 34 sampai di sini.
20 akan ke kiri.
Jadi yang kurang.
Tapi aku tidak bisa kemudian dimasukkan 59 di sini, karena meskipun 59 adalah di sebelah kanan 20,
itu masih di sebelah kiri 34.
Jadi dengan itu kendala dalam pikiran, cara termudah mungkin memecahkan ini
Masalahnya adalah hanya semacam dari angka-angka ini -
jadi 20, 34, 36, 52, 59, 106.
Dan kemudian memasukkan mereka dari kiri ke kanan.
>> Jadi 20 terjadi di sini.
34 terjadi di sini.
36 terjadi di sini.
52, 59, 106.
Dan Anda juga bisa tahu dengan beberapa mencolokkan dan menyadari,
oh, tunggu, saya tidak memiliki jumlah yang cukup untuk mengisi ini di sini.
Jadi saya harus reshift apa saya rute catatan akan menjadi.
Tetapi perhatikan bahwa di final tiga, jika Anda membaca dari kiri ke kanan, itu adalah dalam
urutan yang meningkat.
>> Jadi sekarang, kami ingin menyatakan apa yang struct akan menjadi untuk
node dalam pohon ini.
Jadi apa yang kita butuhkan dalam sebuah pohon biner?
Jadi kita memiliki nilai tipe int, sehingga beberapa nilai int.
Aku tidak tahu apa yang kami sebut dalam larutan -
int n.
Kita perlu pointer ke anak kiri dan pointer ke anak kanan.
Jadi itu akan terlihat seperti ini.
Dan itu benar-benar akan melihat sebelum kapankah-linked ganda
Daftar barang-barang, sehingga pemberitahuan -
Aku akan harus gulir semua cara kembali ke masalah 11.
>> Jadi melihat hal itu terlihat identik dengan ini, kecuali kami hanya terjadi untuk menyebutnya
nama yang berbeda.
Kami masih memiliki integer nilai dan dua pointer.
Hanya saja bahwa alih-alih mengobati pointer sebagai menunjuk ke hal berikutnya
dan hal sebelumnya, kita memperlakukan pointer untuk menunjuk ke anak kiri
dan anak kanan.
OK.
Jadi itulah struct simpul kami.
Dan sekarang, satu-satunya fungsi kita perlu menerapkan untuk ini adalah melintasi, yang
kami ingin pergi ke pohon, pencetakan keluar nilai pohon dalam rangka.
>> Jadi mencari di sini, kita ingin mencetak keluar 20, 34, 36, 52, 59, dan 106.
Bagaimana kita mencapai itu?
Jadi itu sangat mirip.
Jika Anda melihat di ujian terakhir masalah bahwa Anda ingin mencetak
seluruh pohon dengan koma di antara segala sesuatu, itu benar-benar bahkan
lebih mudah dari itu.
Jadi di sini adalah solusinya.
Ini secara signifikan lebih mudah jika Anda melakukannya secara rekursif.
Saya tidak tahu apakah ada yang mencoba untuk melakukannya iteratif.
>> Tapi pertama-tama, kita memiliki kasus dasar kami.
Bagaimana jika akar adalah nol?
Kemudian kita hanya akan kembali.
Kami tidak ingin mencetak apa pun.
Lain kita akan melintasi rekursif bawah.
Cetak seluruh subtree kiri.
Jadi mencetak segala sesuatu yang kurang dari nilai saya saat ini.
Dan kemudian aku akan mencetak sendiri.
Dan kemudian aku akan recurse turun saya seluruh subtree kanan, jadi semuanya
lebih besar dari nilai saya.
Dan ini akan mencetak segala sesuatu dalam rangka.
Pertanyaan tentang bagaimana hal ini benar-benar menyelesaikan itu?
>> AUDIENCE: Saya punya pertanyaan pada [Tak terdengar].
>> ROB Bowden: Jadi salah satu cara untuk mendekati masalah rekursif adalah untuk hanya berpikir
tentang hal itu seperti Anda harus berpikir tentang semua kasus sudut.
Jadi menganggap bahwa kita ingin mencetak seluruh pohon ini.
Jadi semua kita akan fokus pada adalah simpul tertentu -
36.
Panggilan rekursif, kita berpura-pura mereka hanya bekerja.
Jadi di sini, panggilan ini rekursif untuk traverse, kita bahkan tanpa berpikir
tentang hal itu, hanya melintasi kiri tiga, bayangkan yang sudah mencetak 20
dan 34 bagi kita.
Dan kemudian ketika kita akhirnya rekursif memanggil melintasi pada
benar, yang benar akan mencetak 52, 59, dan 106 bagi kita.
>> Jadi mengingat bahwa ini dapat mencetak 20, 34, dan yang lain dapat mencetak 52, 59, 108,
semua yang kita butuhkan untuk dapat lakukan adalah mencetak diri di tengah-tengah itu.
Jadi mencetak segala sesuatu sebelum kita.
Cetak diri mereka sendiri, sehingga node cetak saat ini 36, printf biasa, dan kemudian
mencetak semuanya setelah kita.
>> DAVID J. Malan: Ini adalah di mana rekursi akan benar-benar indah.
Ini lompatan luar biasa ini iman mana Anda melakukan sedikit terkecil pekerjaan.
Dan kemudian Anda membiarkan orang lain melakukan sisanya.
Dan bahwa orang lain adalah, ironisnya, Anda.
Jadi untuk poin brownies serius, jika Anda gulir ke atas pada pertanyaan -
>> ROB Bowden: Pada pertanyaan?
>> DAVID J. Malan: Dan turun sedikit untuk angka, tidak ada yang tahu di mana
angka-angka ini berasal?
>> ROB Bowden: Saya telah benar-benar tidak tahu.
>> DAVID J. Malan: Mereka muncul seluruh kuis.
>> AUDIENCE: Apakah mereka nomor yang sama?
>> DAVID J. Malan: Angka-angka.
Sebuah telur Paskah kecil.
Jadi bagi anda menonton online di rumah, jika Anda dapat memberitahu kami melalui email ke
heads@CS50.net apa signifikansi dari enam nomor yang berulang
seluruh Quiz 1, kami akan mandi Anda dengan perhatian yang luar biasa di final
kuliah dan bola stres.
Nice, halus.
>> ROB Bowden: Pertanyaan terakhir tentang apa pun pada kuis?