[MUSIC PLAYING]
DAVID J. Malan: Baiklah.
Ini adalah CS50.
Ini adalah minggu lima terus, dan kami punya kabar baik dan kabar buruk.
Jadi Kabar baiknya adalah bahwa CS50 meluncurkan Jumat ini.
Jika Anda ingin bergabung dengan kami, kepala ke URL yang biasa di sini.
Berita lebih baik, tidak ada kuliah ini datang Senin tanggal 13.
Sedikit kurang berita yang lebih baik, kuis nol Rabu depan.
Lebih detail dapat ditemukan di URL ini di sini.
Dan selama beberapa hari ke depan kita akan mengisi kekosongan
berkaitan dengan kamar bahwa kita akan telah memesan.
Kabar baik adalah bahwa ada akan menjadi review program-wide
sesi ini datang Senin di malam hari.
Tetaplah kursus ini website untuk lokasi dan rincian.
Bagian, meskipun itu adalah liburan, juga akan bertemu juga.
Berita Terbaik, kuliah Jumat depan.
Jadi ini adalah kita tradisi memiliki, sesuai silabus.
Hanya-- itu akan menjadi luar biasa.
Anda akan melihat hal-hal seperti struktur data waktu yang konstan
dan tabel hash dan pohon-pohon dan mencoba.
Dan kita akan berbicara tentang masalah ulang tahun.
Seluruh banyak barang menanti Jumat depan.
OK.
Bagaimanapun.
>> Jadi ingat bahwa kita sudah berfokus pada gambar ini apa
dalam memori komputer kita.
Jadi memori atau RAM adalah tempat program ada saat Anda sedang menjalankan mereka.
Jika Anda klik dua kali-an icon untuk menjalankan beberapa program yang
atau klik dua kali-an icon untuk membuka beberapa berkas,
itu dimuat dari hard Anda drive atau solid state drive
ke dalam RAM, Random Access Memory, di mana ia hidup sampai listrik padam,
tutup laptop ditutup, atau Anda keluar dari program.
>> Sekarang memori yang, dari yang Anda mungkin memiliki
1 gigabyte hari ini, 2 gigabyte, atau bahkan lebih,
umumnya diletakkan untuk program tertentu
dalam jenis persegi panjang model konseptual
dimana kita memiliki tumpukan di bagian bawah dan banyak hal lain di bagian atas.
Hal di atas sangat kita lihat pada gambar ini
sebelum tapi tidak pernah berbicara tentang adalah apa yang disebut segmen teks.
Segmen teks adalah cara mewah mengatakan nol dan orang-orang yang
menyusun program yang dikompilasi Anda yang sebenarnya.
>> Jadi, ketika Anda double-klik Microsoft Word pada Mac atau PC,
atau ketika Anda menjalankan dot slash Mario pada Komputer Linux di jendela terminal Anda,
nol dan orang-orang yang membentuk Word atau Mario disimpan sementara
dalam RAM komputer Anda dalam apa yang disebut the Segmen teks untuk program tertentu.
Di bawah yang berlangsung diinisialisasi dan data diinisiasi.
Ini adalah hal-hal seperti variabel global, bahwa kita sudah tidak digunakan banyak,
namun pada kesempatan kami telah memiliki variabel global
atau statis didefinisikan string yang sulit dikodekan kata-kata seperti "halo"
yang tidak diambil dari pengguna yang keras-kode ke dalam program Anda.
>> Sekarang, turun di bawah kita memiliki apa yang disebut stack.
Dan tumpukan, sejauh ini, kami sudah gunakan untuk jenis apa tujuan?
Apa stack digunakan untuk?
Ya?
>> AUDIENCE: Fungsi.
>> DAVID J. Malan: Untuk fungsi?
Dalam arti untuk fungsi?
>> AUDIENCE: Ketika Anda memanggil fungsi, yang argumen disalin ke stack.
>> DAVID J. Malan: Tepat.
Ketika Anda memanggil fungsi, yang argumen disalin ke stack.
Jadi setiap X atau Y atau A atau B bahwa Anda melewati ke dalam fungsi
untuk sementara memakai yang disebut stack,
seperti salah satu Annenberg makan nampan hall, dan juga hal-hal
seperti variabel lokal.
Jika fungsi foo atau swap fungsi memiliki variabel lokal,
seperti suhu, kedua berakhir pada stack.
Sekarang, kita tidak akan berbicara terlalu banyak tentang mereka, tetapi variabel lingkungan ini
di bagian bawah kami melihat beberapa waktu lalu ketika Aku futzing di keyboard satu hari
dan aku mulai mengakses hal-hal seperti argv 100 atau argv 1.000,
hanya elements-- saya lupa yang Numbers tapi itu
tidak seharusnya diakses oleh saya.
Kami mulai melihat beberapa simbol yang funky di layar.
Mereka adalah yang disebut variabel lingkungan
seperti pengaturan global untuk saya program atau untuk komputer saya, tidak
tidak terkait dengan baru-baru ini bug yang kita bahas,
SHELLSHOCK, yang sudah mengganggu beberapa komputer.
>> Sekarang terakhir, fokus saat ini kami akhirnya akan berada di heap.
Ini adalah potongan lain dari memori.
Dan pada dasarnya semua ini memori adalah hal yang sama.
Ini adalah perangkat keras yang sama.
Kami hanya semacam mengobati cluster yang berbeda
dari byte untuk tujuan yang berbeda.
Tumpukan ini juga akan menjadi tempat variabel dan memori yang Anda meminta
dari sistem operasi disimpan sementara.
>> Tapi ada semacam masalah di sini, seperti gambar menyiratkan.
Kami semacam memiliki dua kapal akan bertabrakan.
Karena ketika Anda menggunakan lebih banyak tumpukan, dan seperti yang kita lihat hari ini
selanjutnya, karena Anda menggunakan lebih dan lebih dari heap, pasti hal-hal buruk yang mungkin terjadi.
Dan memang, kita dapat menginduksi yang sengaja atau tidak sengaja.
Jadi cliffhanger terakhir Waktu itu program ini,
yang tidak melayani setiap fungsional tujuan lain selain untuk menunjukkan
bagaimana Anda sebagai orang jahat benar-benar dapat mengambil keuntungan dari bug dalam program seseorang
dan mengambil alih sebuah program atau bahkan sistem komputer secara keseluruhan atau server.
Jadi hanya melirik sebentar, Anda melihat bahwa utama di bagian bawah
mengambil di baris perintah argumen, sesuai argv.
Dan memiliki panggilan ke fungsi f, dasarnya fungsi tanpa nama yang disebut
f, dan itu lewat di argv [1].
>> Jadi kata apa pun jenis pengguna dalam di prompt setelah nama program ini,
dan kemudian ini fungsi sewenang-wenang atas atas, f, mengambil dalam sebuah string, AKA char *,
seperti yang telah kita mulai membahas, dan hanya menyebutnya "bar."
Tapi kita bisa menyebutnya apa pun.
Dan kemudian menyatakan, dalam dari f, sebuah array karakter
disebut c-- 12 karakter tersebut.
>> Sekarang, berdasarkan cerita saya mengatakan beberapa saat yang lalu, di mana dalam memori
adalah c, atau orang-orang 12 karakter akan berakhir?
Hanya untuk menjadi jelas.
Ya?
>> AUDIENCE: Pada stack.
>> DAVID J. Malan: Pada stack.
Jadi c adalah variabel lokal.
Kami minta 12 karakter atau 12 byte.
Mereka akan berakhir pada apa yang disebut stack.
Sekarang akhirnya adalah fungsi lain ini itu sebenarnya cukup berguna,
tapi kami tidak benar-benar digunakan diri kita sendiri, strncopy.
Ini berarti string copy, tapi hanya n huruf, n karakter.
Jadi n karakter akan disalin dari bar ke c.
Dan berapa banyak?
Panjang bar.
Jadi dengan kata lain, bahwa satu baris, strncopy,
akan menyalin efektif bar untuk c.
>> Sekarang, hanya untuk jenis mengantisipasi moral dari cerita ini,
apa yang berpotensi bermasalah di sini?
Meskipun kita sedang memeriksa panjang bar dan menyerahkannya ke strncopy,
apa usus Anda memberitahu Anda adalah masih rusak tentang program ini?
Ya?
>> AUDIENCE: Tidak termasuk ruang untuk karakter null.
DAVID J. Malan: Tidak termasuk ruang untuk karakter null.
Berpotensi, tidak seperti di praktek masa lalu kita bahkan tidak
memiliki begitu banyak sebagai plus 1 mengakomodasi karakter null.
Tapi itu bahkan lebih buruk dari itu.
Apa lagi yang kita gagal lakukan?
Ya?
>> AUDIENCE: [Tak terdengar]
DAVID J. Malan Perfect.
Kami telah dikodekan keras 12 cukup sewenang-wenang.
Itu tidak begitu banyak masalah, tapi kenyataan
bahwa kita tidak memperhatikan apakah panjang bar kurang dari 12,
dalam hal ini akan menjadi aman untuk memasukkannya ke dalam memori
disebut c yang telah kita dialokasikan.
Memang, jika bar seperti 20 karakter,
fungsi ini tampaknya menyalin 20 karakter dari bar ke c, demikian
mengambil setidaknya 8 byte bahwa itu tidak boleh.
Itulah implikasi di sini.
>> Jadi singkatnya, program yang rusak.
Tidak masalah besar.
Mungkin Anda mendapatkan kesalahan segmentasi.
Kita semua sudah memiliki bug dalam program.
Kita semua mungkin memiliki bug dalam program sekarang.
Tapi apa implikasinya?
Nah, di sini adalah versi zoom-in dari bahwa gambar memori komputer saya.
Ini adalah bagian bawah tumpukan saya.
Dan memang, di bagian paling bawah adalah apa yang disebut tumpukan rutin orang tua, cara mewah
mengatakan itu utama.
Sehingga siapa pun yang disebut fungsi f yang kita bicarakan.
Jadi, ini adalah bagian bawah tumpukan.
Alamat pengirim adalah sesuatu yang baru.
Itu selalu ada, selalu di foto itu.
Kami tidak pernah meminta perhatian untuk itu.
Karena ternyata cara kerjanya adalah c bahwa ketika salah satu fungsi panggilan lain,
tidak hanya melakukan argumen untuk itu Fungsi bisa didorong ke stack,
tidak hanya melakukan fungsi yang lokal variabel mendapatkan didorong ke stack,
sesuatu yang disebut alamat pengirim juga akan dimasukkan ke dalam stack.
Secara khusus, jika panggilan utama foo, ini utama alamat sendiri dalam memori, sapi sesuatu,
efektif akan dimasukkan ke stack sehingga ketika f dilakukan mengeksekusinya
tahu di mana untuk melompat kembali ke dalam teks segmen untuk terus menjalankan.
>> Jadi jika kita berada di sini konseptual, di utama, maka f dipanggil.
Bagaimana f tahu siapa untuk kontrol tangan kembali?
Nah, ini sedikit breadcrumb merah di sini,
disebut alamat pengirim, hanya cek, apa itu alamat pengirim?
Oh, biarkan aku melompat kembali ke utama di sini.
Dan itu sedikit suatu penyederhanaan yang berlebihan,
karena nol dan satu untuk utama secara teknis
di sini di segmen teknologi.
Tapi itu ide. f hanya harus tahu apa
ke tempat kontrol akhirnya kembali.
>> Tapi cara komputer telah lama ditata hal
seperti variabel lokal dan argumen seperti ini.
Jadi di bagian atas gambar ini di biru stack frame untuk f, sehingga semua
memori yang f khusus adalah menggunakan.
Jadi sesuai, perhatikan bahwa bar di foto ini.
Bar adalah argumen.
Dan kami menyatakan bahwa argumen untuk fungsi mendapatkan didorong ke stack.
Dan c, tentu saja, adalah juga di foto ini.
>> Dan hanya untuk tujuan notasi, perhatikan di bagian atas pojok kiri
adalah apa yang akan c braket 0 dan kemudian sedikit ke kanan
adalah c braket 11.
Jadi dengan kata lain, Anda bisa membayangkan bahwa ada kotak byte
ada, pertama adalah kiri atas, bawah yang
adalah yang terakhir dari mereka 12 byte.
>> Tapi sekarang coba untuk maju cepat.
Apa yang akan terjadi jika kita melewati dalam string bar yang lebih panjang dari c?
Dan kita tidak memeriksa apakah itu memang lebih dari 12.
Bagian mana dari gambar ini akan mendapatkan ditimpa oleh byte 0, 1, 2, 3,
dot dot dot, 11, dan kemudian buruk, 12, 13 sampai 19?
Apa yang akan terjadi di sini, jika Anda menyimpulkan dari pengurutan
bahwa c braket 0 adalah di atas dan c bracket 11 adalah semacam turun
ke kanan?
Ya?
>> AUDIENCE: Yah, itu akan untuk menimpa char * bar.
>> DAVID J. Malan: Ya, sepertinya Anda akan menimpa char * bar.
Dan lebih buruk lagi, jika Anda mengirim dalam sangat panjang String, Anda bahkan mungkin menimpa apa?
Alamat pulang.
Yang sekali lagi, adalah seperti breadcrumb untuk memberitahu program mana
untuk kembali ke saat f dilakukan dipanggil.
>> Jadi apa yang biasanya dilakukan orang jahat adalah jika mereka menemukan sebuah program
bahwa mereka penasaran apakah adalah dieksploitasi, kereta sedemikian rupa
bahwa ia dapat mengambil keuntungan dari bug itu,
umumnya mereka tidak mendapatkan hak ini pertama kalinya.
Mereka hanya mulai mengirim, misalnya, string acak ke dalam program Anda,
apakah di keyboard, atau terus terang mereka mungkin
menulis sebuah program kecil untuk hanya secara otomatis menghasilkan string,
dan mulai menggedor program anda dengan mengirimkan banyak input yang berbeda
pada panjang yang berbeda.
>> Segera setelah crash program Anda, itu suatu hal yang luar biasa.
Karena itu berarti dia atau dia telah menemukan
apa yang mungkin memang bug.
Dan kemudian mereka bisa mendapatkan lebih pintar dan mulai fokus lebih sempit
tentang bagaimana memanfaatkan bug tersebut.
Secara khusus, apa yang dia mungkin lakukan adalah mengirim, dalam kasus terbaik, halo.
Bukan masalah besar.
Ini string yang cukup singkat.
Tapi bagaimana kalau dia mengirim, dan kami akan generalisasi sebagai,
Serangan code-- sehingga nol dan orang-orang yang melakukan hal-hal
seperti rm-rf, yang menghapus segala sesuatu dari hard drive atau mengirim spam
atau entah bagaimana menyerang mesin?
>> Jadi jika masing-masing huruf A hanya mewakili,
konseptual, menyerang, menyerang, serangan, serangan, beberapa kode yang buruk
bahwa orang lain menulis, tetapi jika seseorang yang cukup pintar
untuk tidak hanya mencakup semua mereka rm-RFS, tetapi juga
memiliki beberapa byte terakhir nya menjadi nomor yang sesuai
ke alamat nya atau kode serangan sendiri
bahwa ia lulus hanya dengan menyediakan pada prompt,
Anda dapat secara efektif trik komputer dalam memperhatikan ketika f dilakukan mengeksekusi,
oh, sudah waktunya bagi saya untuk melompat kembali ke alamat pengirim merah.
Tetapi karena ia memiliki entah bagaimana tumpang tindih bahwa alamat pengirim
dengan nomor mereka sendiri, dan mereka cukup pintar
telah dikonfigurasi bahwa nomor untuk merujuk, karena Anda
lihat di super top kiri pojok sana,
alamat yang sebenarnya di komputer memori dari beberapa kode serangan mereka,
orang jahat dapat trik komputer dalam mengeksekusi kode sendiri.
>> Dan kode itu, sekali lagi, bisa apa saja.
Ini umumnya disebut kode shell, yang hanya
cara untuk mengatakan bahwa itu bukan umumnya sesuatu yang sederhana seperti rm-rf.
Ini sebenarnya sesuatu seperti Bash, atau program yang sebenarnya yang memberinya
atau kontrol program nya untuk mengeksekusi apa pun yang mereka ingin.
Jadi singkatnya, ini semua berasal dari fakta sederhana
bahwa bug ini melibatkan tidak memeriksa batas-batas array.
Dan karena cara komputer bekerja adalah bahwa mereka
menggunakan tumpukan dari efektif, secara konseptual,
bawah ke atas, tapi kemudian unsur-unsur Anda mendorong ke stack tumbuh atas ke bawah,
ini sangat bermasalah.
Sekarang, ada cara untuk bekerja di sekitar ini.
Dan terus terang, ada bahasa yang dapat digunakan untuk bekerja di sekitar ini.
Java kebal, misalnya, untuk isu ini.
Karena mereka tidak memberikan petunjuk.
Mereka tidak memberikan alamat memori langsung.
Jadi dengan kekuatan ini yang kita miliki menyentuh apa pun di memori
kami ingin datang, diakui, risiko besar.
>> Jadi mengawasi keluar.
Jika, terus terang, pada bulan-bulan atau tahun-tahun mendatang, kapan saja
Anda membaca tentang beberapa eksploitasi program atau server,
jika Anda pernah melihat sedikit sesuatu seperti serangan buffer overflow,
atau stack overflow adalah jenis lain serangan, serupa semangatnya,
sebanyak mengilhami website nama, jika Anda tahu itu,
itu semua hanya berbicara tentang meluap ukuran beberapa karakter
array atau beberapa array yang lebih umum.
Semua pertanyaan, kemudian, dalam hal ini?
Jangan coba ini di rumah.
>> Baiklah.
Jadi malloc sejauh ini telah baru kami teman bahwa kita dapat mengalokasikan memori
bahwa kita tidak perlu tahu di maju yang kita inginkan sehingga kita tidak memiliki
kode keras ke kami nomor program seperti 12.
Setelah pengguna memberitahu kita berapa banyak Data yang dia inginkan untuk input,
kita dapat malloc yang banyak memori.
>> Jadi malloc ternyata, untuk sejauh kita sudah menggunakannya,
eksplisit terakhir kali, dan kemudian kalian telah menggunakannya
untuk getString sadar untuk beberapa minggu, semua memori malloc ini
berasal dari apa yang disebut tumpukan.
Dan inilah mengapa GetString, misalnya, dapat mengalokasikan memori dinamis
tanpa mengetahui apa yang Anda akan mengetik di muka,
tangan Anda kembali pointer ke memori yang, dan memori yang masih milik Anda,
bahkan setelah getString kembali.
Karena ingat setelah semua bahwa stack terus akan naik dan turun,
atas dan ke bawah.
Dan segera setelah ia pergi bawah, itu berarti memori setiap
fungsi ini digunakan harus tidak digunakan oleh orang lain.
Itu nilai sampah sekarang.
>> Tapi tumpukan sampai di sini.
Dan apa yang bagus tentang malloc adalah bahwa ketika malloc mengalokasikan memori di sini,
itu tidak berdampak, untuk sebagian, oleh stack.
Jadi fungsi apapun dapat mengakses memori yang telah malloc'd,
bahkan oleh fungsi seperti GetString, bahkan setelah itu dikembalikan.
>> Sekarang, kebalikan dari malloc gratis.
Dan memang, aturan Anda harus mulai mengadopsi
adalah, setiap, setiap kali Anda menggunakan malloc Anda harus sendiri menggunakan bebas, akhirnya,
pada yang pointer yang sama.
Selama ini kita telah menulis buggy, kode kereta, karena berbagai alasan.
Tapi salah satu yang telah menggunakan perpustakaan CS50, yang
itu sendiri sengaja buggy, kebocoran memori.
Setiap kali Anda menelepon GetString selama beberapa minggu terakhir
kami meminta operasi sistem, Linux, untuk memori.
Dan Anda tidak pernah sekali diberikan kembali.
Dan ini tidak, dalam berlatih, hal yang baik.
>> Dan Valgrind, salah satu alat diperkenalkan pada PSET 4,
adalah semua tentang membantu Anda sekarang menemukan bug seperti itu.
Tapi untungnya untuk PSET 4 Anda tidak perlu untuk menggunakan perpustakaan CS50 atau GetString.
Jadi setiap bug yang berhubungan dengan memori akhirnya akan menjadi Anda sendiri.
>> Jadi malloc lebih dari sekedar nyaman untuk tujuan ini.
Kami benar-benar dapat memecahkan sekarang masalah fundamental berbeda,
dan fundamental memecahkan masalah yang lebih efektif sesuai janji minggu nol ini.
Sejauh ini terseksi struktur data kami sudah.
Dan dengan struktur data saya hanya berarti cara konseptualisasi memori
dengan cara yang melampaui hanya mengatakan, ini adalah int, ini adalah char.
Kita bisa mulai dengan hal-hal klaster bersama-sama.
>> Jadi array tampak seperti ini.
Dan apa kunci dalam tentang Array adalah bahwa hal itu memberi Anda
back-to-back potongan memori, yang masing-masing
akan menjadi dari jenis yang sama, int, int, int, int, atau char, char, char,
arang.
Tapi ada beberapa kelemahan.
Hal ini misalnya, adalah array ukuran enam.
Misalkan Anda mengisi array ini dengan enam nomor dan kemudian, untuk alasan apa pun,
pengguna Anda ingin memberikan Anda sejumlah ketujuh.
Di mana Anda menempatkan itu?
>> Apa solusinya jika Anda memiliki menciptakan sebuah array di stack,
misalnya, hanya dengan minggu dua notasi yang kita diperkenalkan,
kurung persegi dengan jumlah dalam?
Nah, Anda punya enam angka dalam kotak-kotak ini.
Apa yang akan naluri Anda menjadi?
Di mana Anda ingin menempatkan itu?
>> AUDIENCE: [Tak terdengar]
>> DAVID J. Malan: Maaf?
>> AUDIENCE: Taruh di akhir.
>> DAVID J. Malan: Taruh di akhir.
Jadi hanya ke kanan, luar kotak ini.
Yang akan menyenangkan, tetapi ternyata Anda tidak bisa melakukan itu.
Karena jika Anda tidak diminta untuk potongan ini memori,
bisa juga dengan kebetulan bahwa ini sedang digunakan oleh beberapa variabel lain
sama sekali.
Pikirkan kembali seminggu atau jadi ketika kita meletakkan nama-nama Zamyla dan Davin dan Gabe
dalam memori.
Mereka benar-benar kembali untuk kembali ke belakang.
Jadi kita tidak bisa serta merta percaya bahwa dunia apapun
di sini tersedia bagi saya untuk menggunakan.
>> Jadi apa lagi yang mungkin Anda lakukan?
Nah, setelah menyadari Anda membutuhkan sebuah array ukuran tujuh,
Anda hanya bisa membuat array ukuran tujuh kemudian gunakan
untuk loop atau loop sementara, menyalinnya ke array baru,
dan kemudian entah bagaimana hanya menyingkirkan array ini atau hanya berhenti menggunakannya.
Tapi itu tidak terlalu efisien.
Singkatnya, array jangan biarkan Anda dinamis mengubah ukuran.
>> Jadi di satu sisi Anda mendapatkan akses acak, yang menakjubkan.
Karena itu mari kita melakukan hal-hal seperti membagi dan menaklukkan,
pencarian biner, semua yang kita sudah berbicara tentang pada layar di sini.
Tapi Anda cat sendiri ke sudut.
Segera setelah Anda menekan akhir array Anda,
Anda harus melakukan yang sangat operasi yang mahal
atau menulis sejumlah besar kode sekarang menangani masalah itu.
>> Jadi bagaimana jika sebaliknya kita punya sesuatu yang disebut daftar,
atau linked list pada khususnya?
Bagaimana jika daripada harus persegi panjang kembali ke belakang ke belakang,
kami memiliki empat persegi panjang yang meninggalkan sedikit sedikit ruang gerak di antara mereka?
Dan meskipun aku sudah ditarik ini gambar atau diadaptasi gambar ini
dari salah satu teks di sini untuk kembali ke kembali ke belakang sangat tertib, pada kenyataannya,
salah satu persegi panjang bisa sampai di sini dalam memori.
Salah satunya bisa sampai di sini.
Salah satunya bisa sampai di sini, di sini, dan sebagainya.
>> Tapi bagaimana kalau kita menarik, dalam hal ini, panah
yang entah bagaimana menghubungkan ini persegi panjang bersama-sama?
Memang, kami telah melihat teknis inkarnasi panah.
Apa yang telah kita digunakan dalam baru-baru ini hari itu, di bawah tenda,
merupakan perwakilan dari panah?
Sebuah pointer, kan?
>> Jadi bagaimana jika, bukannya hanya menyimpan angka-angka,
seperti 9, 17, 22, 26, 34, bagaimana jika kita disimpan tidak
hanya sejumlah tapi pointer di samping setiap nomor tersebut?
Sehingga banyak seperti Anda akan thread jarum melalui sejumlah kain,
hal entah bagaimana mengikat bersama-sama, sama bisa
kita dengan pointer, seperti menjelma oleh panah di sini,
jenis menenun bersama-sama ini persegi panjang individu
dengan secara efektif menggunakan pointer di sebelah setiap nomor yang
menunjuk ke beberapa nomor berikutnya, yang menunjukkan, pada gilirannya, beberapa nomor berikutnya?
Jadi dengan kata lain, apa yang jika kita benar-benar ingin
untuk melaksanakan sesuatu seperti ini?
Nah sayangnya, persegi panjang ini, setidaknya satu dengan 9, 17, 22,
dan sebagainya, ini tidak lagi kotak bagus dengan nomor tunggal.
Bagian bawah, persegi panjang di bawah 9, misalnya,
mewakili apa yang harus menjadi pointer, 32 bit.
Sekarang, aku belum mengetahui adanya tipe data di C yang memberikan Anda tidak hanya int
tapi pointer sama sekali.
>> Jadi apa solusinya jika kita ingin menciptakan jawaban kita sendiri untuk ini?
Ya?
>> AUDIENCE: [Tak terdengar]
>> DAVID J. Malan: Apa itu?
>> AUDIENCE: Struktur baru.
>> DAVID J. Malan: Ya, jadi mengapa kita tidak membuat struktur baru,
atau di C, struct?
Kami telah melihat struct sebelumnya, jika sebentar, di mana kita berurusan dengan struktur mahasiswa
seperti ini, yang memiliki nama dan rumah.
Dalam PSET 3 breakout Anda menggunakan seluruh sekelompok GRect structs-- dan GOvals
bahwa Stanford diciptakan untuk Informasi klaster bersama-sama.
Jadi bagaimana jika kita mengambil ini ide yang sama kata kunci "typedef" dan "struct,"
dan kemudian beberapa hal spesifik-siswa, dan berkembang ini menjadi sebagai berikut:
typedef struct node-- dan node hanya ilmu komputer sangat generik
istilah untuk sesuatu dalam struktur data, wadah dalam struktur data.
Sebuah node saya mengklaim akan memiliki n int, benar-benar mudah,
dan kemudian sedikit lebih samar, baris kedua ini, struct simpul * berikutnya.
Namun dari segi teknis kurang, apa itu baris kedua
kode dalam kurung kurawal?
Ya?
>> AUDIENCE: [Tak terdengar]
DAVID J. Malan: A pointer ke node lain.
Jadi memang, sintaks sedikit samar.
Tapi jika Anda membaca secara harfiah, berikutnya adalah nama variabel.
Apa jenis datanya?
Ini adalah verbose sedikit waktu ini, tapi itu tipe struct simpul *.
Setiap kali kita telah melihat sesuatu star, yang berarti itu adalah pointer ke tipe data.
Jadi berikutnya adalah rupanya pointer ke struct simpul.
>> Sekarang, apa itu struct simpul?
Nah, melihat Anda melihat orang-orang kata yang sama di kanan atas.
Dan memang, Anda juga melihat kata "Node" di sini di bagian kiri bawah.
Dan ini sebenarnya hanya kenyamanan.
Perhatikan bahwa dalam definisi mahasiswa ada kata "mahasiswa" hanya sekali.
Dan itu karena mahasiswa objek tidak self-referensial.
Tidak ada dalam mahasiswa yang perlu untuk menunjuk ke siswa lain,
persay.
Itu akan semacam aneh di dunia nyata.
>> Tapi dengan simpul di terkait daftar, kita ingin node
menjadi referensial ke objek yang sama.
Dan begitu melihat perubahan di sini tidak hanya apa yang ada di dalam kurung kurawal.
Tapi kami menambahkan kata "node" di atas serta
menambahkannya ke bawah sebagai pengganti "mahasiswa."
Dan ini hanya detail teknis sehingga, sekali lagi, struktur data Anda
dapat self-referensial, sehingga node dapat menunjuk ke node lain seperti.
>> Jadi apa ini akhirnya akan berarti bagi kita?
Nah, satu, hal ini dalam adalah isi dari simpul kami.
Hal ini di sini, kanan atas, hanya begitu
itu, sekali lagi, kita bisa lihat diri kita sendiri.
Dan kemudian hal-hal terluar, meskipun simpul adalah istilah baru,
mungkin, itu masih sama seperti mahasiswa dan apa
adalah di bawah kap di SPL.
>> Jadi jika sekarang kita ingin memulai menerapkan linked list ini,
bagaimana mungkin kita menerjemahkan sesuatu seperti ini untuk kode?
Nah, mari kita melihat contoh program yang
benar-benar menggunakan linked list.
Di antara kode distribusi hari ini adalah sebuah program yang disebut Daftar Zero.
Dan jika saya menjalankan ini saya buat super GUI sederhana, Graphical User Interface,
tapi itu benar-benar hanya printf.
Dan sekarang aku sudah memberikan diriku beberapa menu options-- Hapus, Insert, Search,
dan Traverse.
Dan Keluar.
Ini adalah operasi hanya umum pada struktur data yang dikenal sebagai daftar link.
>> Sekarang, Hapus akan menghapus nomor dari daftar.
Insert akan menambahkan nomor ke dalam daftar.
Cari akan terlihat nomor dalam daftar.
Dan melintasi adalah cara mewah mengatakan, berjalan melalui daftar,
mencetaknya, tapi itu saja.
Jangan mengubahnya dengan cara apapun.
>> Jadi mari kita coba ini.
Mari kita pergi ke depan dan tipe 2.
Dan kemudian aku akan masukkan nomor tersebut, mengatakan 9.
Enter.
Dan sekarang program saya hanya diprogram untuk mengatakan, daftar sekarang 9.
Sekarang, jika saya pergi ke depan dan jangan Masukkan lagi, biarkan
aku pergi ke depan dan zoom out dan ketik 17.
Sekarang daftar saya adalah 9, maka 17.
Jika saya melakukan memasukkan lagi, mari kita melewatkan satu.
Alih-alih 22, sesuai gambar yang kita sudah telah melihat di sini, biarkan aku melompat ke depan
dan masukkan 26 berikutnya.
Jadi aku akan mengetik 26.
Daftar ini seperti yang saya harapkan.
Tapi sekarang, hanya untuk melihat apakah kode ini akan menjadi fleksibel, biarkan aku sekarang
Jenis 22, yang setidaknya konseptual, jika kita
menjaganya agar ini diurutkan, yang memang akan menjadi tujuan lain sekarang,
harus pergi di antara 17 dan 26.
Jadi saya tekan Enter.
Memang, yang bekerja.
Dan sekarang biarkan aku memasukkan terakhir, per gambar, 34.
>> Baiklah.
Jadi untuk saat ini biarkan aku menetapkan bahwa Hapus dan Traverse dan Cari lakukan,
pada kenyataannya, bekerja.
Bahkan, jika saya menjalankan Search, mari kita mencari nomor 22, Enter.
Ditemukan 22.
Jadi itulah yang ini Program Daftar Nol tidak.
>> Tapi apa yang sebenarnya terjadi pada yang menerapkan ini?
Yah, pertama saya mungkin memiliki, dan memang Saya punya file yang disebut list0.h.
Dan suatu tempat di sana adalah ini line, typedef, struct node,
maka saya memiliki kawat gigi keriting saya, int n, dan kemudian struct-- apa definisi?
Struct node berikutnya.
Jadi kita perlu bintang.
Sekarang kita masuk ke teknis kebiasaan menggambar di sini.
Anda mungkin melihat buku pelajaran dan referensi online melakukannya di sana.
Ini fungsional setara.
Bahkan, ini sedikit lebih khas.
Tapi aku akan konsisten dengan apa kami lakukan terakhir kali dan melakukan hal ini.
Dan kemudian terakhir, aku akan melakukan hal ini.
>> Jadi dalam file header di suatu tempat, di list0.h
hari ini adalah definisi struct ini, dan mungkin beberapa hal lain.
Sementara itu di list0c ada akan beberapa hal.
Tapi kita akan hanya memulai dan tidak selesai ini.
List0.h adalah file yang saya inginkan untuk menyertakan dalam file C saya.
Dan kemudian di beberapa titik saya akan memiliki int, utama, membatalkan.
Dan kemudian aku akan memiliki beberapa agenda di sini.
Saya juga akan memiliki prototipe seperti batal, search, int,
n, tujuan yang dalam hidup adalah untuk mencari suatu elemen.
Dan kemudian di sini saya menyatakan di kode hari ini, batal, pencarian, int, n,
tidak ada titik koma tetapi kurung kurawal terbuka.
Dan sekarang saya ingin entah bagaimana mencari untuk sebuah elemen dalam daftar ini.
Tapi kita tidak memiliki cukup informasi di layar belum.
Aku belum benar-benar mewakili daftar itu sendiri.
Jadi salah satu cara kita bisa menerapkan linked list dalam program
adalah saya agak ingin melakukan sesuatu seperti mendeklarasikan linked list di sini.
Untuk mempermudah, saya akan membuat global ini, meskipun di kita umum
tidak harus melakukan ini terlalu banyak.
Tapi itu akan menyederhanakan contoh ini.
Jadi saya ingin menyatakan linked list di sini.
Sekarang, bagaimana aku bisa melakukan itu?
>> Berikut gambar dari sebuah linked list.
Dan aku tidak benar-benar tahu saat ini bagaimana
Aku akan pergi tentang mewakili begitu banyak hal hanya dengan satu
variabel dalam memori.
Tapi pikirkan kembali sejenak.
Selama ini kami sudah string, yang kita kemudian
diturunkan menjadi array dari karakter, yang kita kemudian
diturunkan hanya menjadi pointer ke karakter pertama
dalam berbagai karakter yang null diakhiri.
Jadi dengan logika itu, dan dengan ini jenis gambar pembibitan pikiran Anda,
apa perlu kita benar-benar menulis di kami kode untuk mewakili sebuah linked list?
Berapa banyak dari informasi ini kita perlu untuk menangkap dalam kode C, yang akan Anda katakan?
Ya?
>> AUDIENCE: Kita perlu pointer ke node.
DAVID J. Malan: Sebuah pointer ke node.
Secara khusus, yang simpul akan Anda naluri adalah untuk menyimpan pointer ke?
>> AUDIENCE: The simpul pertama.
>> DAVID J. Malan: Ya, mungkin hanya yang pertama.
Dan perhatikan, yang pertama node bentuk yang berbeda.
Ini hanya setengah ukuran struct, karena memang hanya pointer.
Jadi apa yang Anda benar-benar dapat Anda lakukan adalah menyatakan linked list untuk menjadi tipe node *.
Dan mari kita sebut dulu dan menginisialisasi ke null.
Jadi nol, sekali lagi, adalah datang ke dalam gambar di sini.
Tidak hanya nol digunakan sebagai seperti khusus nilai kembali untuk hal-hal seperti GetString
dan malloc, null juga nol pointer, kurangnya pointer,
jika Anda mau.
Ini hanya berarti tidak ada yang belum di sini.
Sekarang pertama, saya bisa saja disebut apa-apa ini.
Aku bisa menyebutnya "daftar" atau banyak hal lainnya.
Tapi aku menyebutnya "pertama" sehingga garis itu dengan gambar ini.
Jadi sama seperti string dapat direpresentasikan dengan alamat byte pertama,
sehingga dapat linked list.
Dan kita akan melihat data lain struktur diwakili
dengan hanya satu pointer, 32-bit panah, menunjuk
di node pertama dalam struktur.
>> Tapi sekarang mari kita mengantisipasi masalah.
Jika saya hanya mengingat dalam program saya alamat
dari node pertama, yang pertama persegi panjang dalam struktur data,
apa yang lebih baik menjadi kasus tentang pelaksanaan sisa daftar saya?
Apa detail kunci yang akan untuk memastikan hal ini benar-benar bekerja?
Dan dengan "benar-benar bekerja" Saya Maksudku, seperti string,
memungkinkan kita pergi dari karakter pertama nama Davin untuk kedua,
untuk yang ketiga, untuk keempat, sampai akhir,
bagaimana kita tahu ketika kita berada di akhir dari linked list yang terlihat seperti ini?
Ketika itu null.
Dan aku sudah mewakili semacam ini sebagai seperti kekuatan insinyur listrik,
dengan landasan kecil simbol, macam.
Tapi itu hanya berarti nol dalam kasus ini.
Anda bisa menggambar sejumlah cara, namun penulis ini
terjadi untuk menggunakan simbol ini di sini.
>> Selama kita merangkai semua node ini bersama-sama,
hanya mengingat di mana yang pertama adalah, begitu lama
seperti yang kita menempatkan simbol khusus di node yang terakhir dalam daftar,
dan kita akan menggunakan null, karena itulah apa yang kita miliki tersedia bagi kita,
daftar ini selesai.
Dan bahkan jika saya hanya memberikan pointer ke elemen pertama, Anda, programmer,
tentu dapat mengakses sisanya.
Tapi mari kita membiarkan pikiran Anda berjalan sedikit,
jika mereka tidak sudah cukup wandered-- apa
akan menjadi waktu berjalan dari menemukan sesuatu dalam daftar ini?
Sialan, itu O besar n, yang tidak buruk, dalam keadilan.
Tapi itu adalah linear.
Kami sudah menyerah apa fitur array dengan memindahkan lebih
terhadap gambar ini dinamis dijalin bersama atau terkait node?
Kami telah memberikan akses acak.
Array bagus karena matematis segalanya
kembali untuk kembali ke belakang ke belakang.
Meskipun gambar ini terlihat cantik, dan bahkan
meskipun tampak seperti node ini baik spasi terpisah, pada kenyataannya
mereka bisa di mana saja.
OX1, Ox50, Ox123, Ox99, ini node bisa di mana saja.
Karena malloc tidak mengalokasikan memori dari tumpukan, tetapi di mana saja di tumpukan.
Anda tidak perlu tahu bahwa itu akan kembali untuk kembali ke belakang.
Jadi gambar ini dalam kenyataannya ini tidak akan cukup cantik.
>> Jadi itu akan mengambil sedikit bekerja untuk melaksanakan fungsi ini.
Jadi mari kita menerapkan pencari sekarang.
Dan kita akan melihat semacam cara cerdas untuk melakukan hal ini.
Jadi jika saya fungsi pencarian dan Aku diberi variabel, integer n
untuk mencari, saya perlu tahu sintaks baru untuk mencari di dalam
dari struktur yang menunjuk, untuk menemukan n.
Jadi mari kita lakukan ini.
>> Jadi pertama aku akan pergi depan dan menyatakan node *.
Dan aku akan menyebutnya pointer, hanya dengan konvensi.
Dan aku akan menginisialisasi terlebih dahulu.
Dan sekarang aku bisa melakukan ini dalam beberapa cara.
Tapi aku akan mengambil pendekatan yang sama.
Sementara pointer tidak sama dengan null, dan itu sintaks yang valid.
Dan itu hanya berarti melakukan hal berikut, sehingga Selama Anda tidak menunjuk pada apa-apa.
Apa yang ingin saya lakukan?
>> Jika pointer dot n, biarkan aku kembali itu, equals-- sama apa?
Apa nilai yang saya cari?
N aktual yang disahkan dalam.
Jadi, inilah fitur lain C dan banyak bahasa.
Meskipun struktur yang disebut simpul memiliki n nilai, benar-benar sah
juga memiliki argumen lokal atau variabel yang disebut n.
Karena bahkan kita, dengan mata manusia, dapat membedakan
bahwa n ini mungkin berbeda dari n ini.
Karena sintaks yang berbeda.
Anda punya dot dan pointer, sedangkan yang satu ini tidak memiliki hal seperti itu.
Jadi ini adalah OK.
Tidak apa-apa untuk memanggil mereka hal yang sama.
>> Kalau aku Anda menemukan ini, aku akan ingin melakukan sesuatu
seperti mengumumkan bahwa kami menemukan n.
Dan kita akan meninggalkan bahwa sebagai komentar atau kode pseudo.
Lain, dan inilah bagian yang menarik, apa yang
yang ingin saya lakukan jika node saat ini tidak mengandung n yang saya peduli?
Bagaimana cara mencapai berikut ini?
Jika jari saya di saat ini PTR, dan itu
menunjuk apa pun pertama menunjuk,
bagaimana cara menggerakkan jari saya ke node berikutnya dalam kode?
Nah, apa breadcrumb kami akan mengikuti dalam kasus ini?
AUDIENCE: [Tak terdengar].
DAVID J. Malan: Ya, jadi lain kali.
Jadi jika saya kembali ke saya kode di sini, memang, aku
akan pergi ke depan dan berkata pointer, yang hanya variable-- sementara itu
nama yang aneh, ptr, tetapi itu hanya seperti temp--
Aku akan mengatur pointer sama dengan apa pun pointer Ini--
dan sekali lagi, ini akan menjadi sedikit kereta untuk titik moment-- berikutnya.
Dengan kata lain, aku akan mengambil saya jari yang menunjuk pada simpul ini
di sini dan aku akan berkata, Anda tahu apa, kita lihat kolom berikutnya
dan gerakkan jari Anda ke apa pun itu menunjuk.
Dan ini akan ulangi, ulangi, ulangi.
Tapi ketika melakukan jari saya berhenti melakukan apa-apa?
Begitu apa baris kode tendangan?
AUDIENCE: [Tak terdengar]
DAVID J. Malan: Jika titik sementara pointer tidak sama dengan nol.
Di beberapa titik jari saya akan menunjuk nol
dan aku akan menyadari itulah akhir dari daftar ini.
Sekarang, ini sedikit kebohongan putih untuk kesederhanaan.
Ternyata bahwa meskipun kita hanya belajar notasi dot ini
untuk struktur, pointer tidak struct.
ptr adalah apa?
Hanya untuk menjadi lebih nitpicky.
Ini adalah pointer ke node.
Ini bukan node itu sendiri.
Jika saya tidak punya bintang di sini, pointer absolutely-- itu node.
Ini seperti satu minggu deklarasi variabel,
meskipun kata "simpul" yang baru.
>> Tapi segera setelah kami memperkenalkan Bintang, sekarang pointer ke node.
Dan sayangnya Anda tidak dapat menggunakan notasi titik untuk pointer.
Anda harus menggunakan panah notasi, yang, mencolok,
adalah pertama kalinya potongan apapun sintaksis terlihat intuitif.
Ini benar-benar terlihat seperti anak panah.
Dan itulah hal yang baik.
Dan di sini benar-benar terlihat seperti anak panah.
Jadi saya pikir itulah la-- saya tidak pikir aku over-melakukan di sini-aku
pikir itu bagian baru terakhir sintaksis kita akan melihat.
Dan untungnya, itu memang sedikit lebih intuitif.
>> Sekarang, bagi anda yang mungkin lebih suka cara lama,
Anda masih dapat menggunakan notasi titik.
Tapi seperti per Senin percakapan, pertama-tama kita
perlu untuk pergi ke sana, pergi ke yang alamat, dan kemudian mengakses lapangan.
Jadi ini juga benar.
Dan terus terang, ini adalah sedikit lebih bertele-tele.
Kau benar-benar mengatakan, dereference pointer dan pergi ke sana.
Kemudian ambil .n, lapangan disebut n.
Tapi terus terang, tidak ada yang mau untuk mengetik atau membaca ini.
Jadi dunia diciptakan notasi panah, yang
setara, identik, itu hanya sintaksis gula.
Jadi cara mewah untuk mengatakan ini terlihat lebih baik, atau terlihat lebih sederhana.
>> Jadi sekarang aku akan melakukan satu hal lain.
Aku akan mengatakan "istirahat" setelah saya sudah menemukan itu jadi saya tidak terus mencari untuk itu.
Tapi ini intinya dari fungsi pencarian.
Tapi itu jauh lebih mudah, dalam end, tidak berjalan melalui kode.
Ini memang pelaksanaan resmi pencarian dalam kode distribusi hari ini.
Saya berani mengatakan insert yang tidak terutama menyenangkan untuk berjalan melalui
visual, juga tidak menghapus, bahkan meskipun pada akhir hari
mereka mendidih hingga cukup heuristik sederhana.
>> Jadi mari kita lakukan ini.
Jika Anda akan humor saya di sini, saya lakukan membawa sekelompok bola stres.
Aku membawa sekelompok angka.
Dan bisa kita dapatkan hanya beberapa relawan untuk mewakili 9, 17, 20, 22, 29, dan 34?
Jadi pada dasarnya semua orang siapa di sini hari ini.
Itu satu, dua, tiga, empat, lima, enam orang.
Dan aku telah diminta untuk go-- lihat, tidak ada satu di belakang menimbulkan tangan mereka.
OK, satu, dua, tiga, empat, five-- biarkan aku memuat balance-- enam.
OK, Anda enam datang ke atas.
Kita akan membutuhkan orang lain.
Kami membawa bola stres tambahan.
Dan jika Anda bisa, untuk hanya sesaat, baris
dirimu sendiri hanya seperti gambar ini di sini.
>> Baiklah.
Mari kita lihat, siapa namamu?
>> AUDIENCE: Andrew.
>> DAVID J. Malan: Andrew, Anda nomor 9.
Senang bertemu Anda.
Di sini Anda pergi.
AUDIENCE: Jen.
DAVID J. Malan: Jen.
David.
Nomor 17.
Ya?
>> AUDIENCE: Aku Julia.
>> DAVID J. Malan: Julia, David.
Nomor 20.
AUDIENCE: Kristen.
DAVID J. Malan: Kristen, David.
Nomor 22.
Dan?
>> AUDIENCE: JP.
DAVID J. Malan: JP.
Nomor 29.
Jadi pergi ke depan dan mendapatkan in-- Uh oh.
Uh oh.
Standby.
20.
Apakah ada yang punya spidol?
AUDIENCE: Aku punya Sharpie.
DAVID J. Malan: Anda punya Sharpie?
OK.
Dan apakah ada yang punya selembar kertas?
Simpan kuliah.
Ayo.
AUDIENCE: Kita punya itu.
DAVID J. Malan: Kami mendapatkannya?
Baiklah, terima kasih.
Di sini kita pergi.
Apakah ini dari Anda?
Anda hanya menyelamatkan hari.
Jadi 29.
Baiklah.
Saya salah eja 29, tapi OK.
Silakan.
Baiklah, aku akan memberikan pena Anda kembali sesaat.
Jadi kita memiliki orang-orang ini di sini.
Mari kita memiliki satu lainnya.
Gabe, apakah Anda ingin bermain elemen pertama di sini?
Kita akan membutuhkan Anda untuk menunjuk di orang-orang baik.
Jadi 9, 17, 20, 22, mengurutkan dari 29, dan kemudian 34.
Apakah kita kehilangan seseorang?
Saya punya 34.
Dimana did-- OK, yang ingin menjadi 34?
OK, datang ke atas, 34.
Baiklah, ini akan menjadi layak klimaks.
Siapa nama Anda?
>> AUDIENCE: Peter.
>> DAVID J. Malan: Peter, ayolah up.
Baiklah, jadi di sini adalah Seluruh sekelompok node.
Masing-masing kalian merupakan salah satu persegi panjang ini.
Dan Gabe, sedikit aneh manusia keluar, mewakili pertama.
Jadi pointer nya sedikit lebih kecil pada layar daripada orang lain.
Dan dalam hal ini, masing-masing kiri tangan akan baik titik bawah,
demikian mewakili nol, sehingga hanya tidak adanya pointer,
atau itu akan menunjuk pada node di sebelah Anda.
>> Jadi sekarang jika Anda menghiasi dirimu seperti gambar
di sini, pergi ke depan dan titik satu sama lain, dengan Gabe
di menunjuk tertentu pada nomor 9 untuk mewakili daftar.
OK, dan nomor 34, tangan kiri hanya harus menunjuk lantai.
>> OK, jadi ini adalah linked list.
Jadi ini adalah skenario yang bersangkutan.
Dan memang, ini adalah wakil dari kelas masalah
bahwa Anda mungkin mencoba untuk memecahkan dengan kode.
Anda ingin akhirnya memasukkan elemen baru ke dalam daftar.
Dalam hal ini, kita akan coba memasukkan nomor 55.
Tapi ada akan menjadi kasus yang berbeda untuk dipertimbangkan.
Dan memang, ini akan menjadi salah satu dari gambaran besar takeaways di sini, adalah,
apa kasus yang berbeda.
Apa yang berbeda jika kondisi atau cabang bahwa program Anda mungkin memiliki?
>> Nah, nomor yang Anda coba insert, yang kita tahu sekarang menjadi 55,
tetapi jika Anda tidak tahu di muka, aku yakin
jatuh ke setidaknya tiga kemungkinan situasi.
Dimana mungkin elemen baru itu?
AUDIENCE: Dan akhir atau tengah.
DAVID J. Malan: Pada akhirnya, di tengah, atau di awal.
Jadi saya mengklaim ada setidaknya tiga masalah yang perlu kita selesaikan.
Mari kita memilih apa yang mungkin bisa dibilang sederhana
satu, di mana unsur baru milik di awal.
Jadi aku akan memiliki kode cukup seperti mencari, yang saya baru saja menulis.
Dan aku akan memiliki ptr, yang Aku akan mewakili di sini dengan jari saya,
seperti biasa.
>> Dan ingat, apa nilai Apakah kita menginisialisasi ptr ke?
Jadi kami diinisialisasi ke null awalnya.
Tapi kemudian apa yang kita lakukan setelah kami berada di dalam fungsi pencarian kita?
Kami mengaturnya sama dengan dulu, yang tidak berarti melakukan hal ini.
Jika saya menetapkan ptr sama dengan pertama, apa harus tanganku benar-benar menunjuk?
Benar.
Jadi jika Gabe dan saya akan sebagai nilai-nilai yang sama di sini,
kita perlu kedua titik di nomor 9.
>> Jadi ini adalah awal dari cerita kita.
Dan sekarang ini hanya sederhana, meskipun sintaks baru.
Secara konseptual ini hanya pencarian linear.
Apakah 55 sama dengan 9?
Atau lebih tepatnya, katakanlah kurang dari 9.
Karena saya sedang mencoba untuk mencari tahu di mana untuk menempatkan 55.
Kurang dari 9, kurang dari 17, kurang dari 20, kurang dari 22, kurang dari 29,
kurang dari 34, tidak ada.
Jadi sekarang kita dalam kasus salah satu dari setidaknya tiga.
>> Jika saya ingin memasukkan 55 di sini, apa yang baris kode perlu dijalankan?
Bagaimana gambaran tentang manusia harus berubah?
Apa yang harus saya lakukan dengan tangan kiri saya?
Ini harus nol pada awalnya, karena aku pada akhir daftar.
Dan apa yang harus terjadi di sini dengan Peter, apakah itu?
Dia jelas akan menunjukkan kepada saya.
Jadi saya mengklaim ada setidaknya dua baris kode dalam kode contoh dari hari ini
yang akan menerapkan ini skenario menambahkan 55 di ekor.
Dan bisa saya memiliki seseorang hop dan hanya mewakili 55?
Baiklah, Anda adalah baru 55.
>> Jadi sekarang bagaimana jika selanjutnya Skenario datang,
dan kami ingin memasukkan di awal atau kepala daftar ini?
Dan siapa namamu, nomor 55?
>> AUDIENCE: Jack.
>> DAVID J. Malan: Jack?
OK, senang bertemu Anda.
Welcome aboard.
Jadi sekarang kita akan menyisipkan, misalnya, nomor 5.
Berikut kasus kedua tiga kami datang dengan sebelumnya.
Jadi, jika 5 milik di awal, mari kita lihat bagaimana kita mengetahui hal itu.
Aku menginisialisasi ptr saya pointer ke nomor 9 lagi.
Dan saya menyadari, oh, 5 kurang dari 9.
Jadi memperbaiki gambar ini untuk kita.
Yang tangannya, Gabe atau David atau-- apa nama nomor 9 itu?
>> AUDIENCE: Jen.
>> DAVID J. Malan: hands-- Jen yang tangan kita perlu mengubah?
OK, jadi Gabe poin apa sekarang?
Pada saya.
Saya node baru.
Jadi aku hanya akan jenis bergerak sini untuk melihat secara visual.
Dan sementara itu apa yang harus saya menunjuk itu?
Masih mana aku menunjuk.
Jadi itu saja.
Jadi hanya benar-benar satu baris kode perbaikan isu ini, tampaknya.
Baiklah, jadi itu bagus.
Dan bisa seseorang menjadi tempat untuk 5?
Ayo up.
Kami akan membuat Anda waktu berikutnya.
>> Baiklah, jadi sekarang-- dan sebagai samping, nama-nama
Aku tidak membuat pernyataan tegas dari kanan sekarang, Kt prediktif brikut pointer, pointer pendahulunya
dan pointer baru, itu hanya nama yang diberikan
dalam kode contoh ke pointer atau tangan saya yang agak menunjuk sekitar.
Siapa nama Anda?
>> AUDIENCE: Christine.
>> DAVID J. Malan: Christine.
Welcome aboard.
Baiklah, jadi mari kita pertimbangkan sekarang skenario yang sedikit lebih menjengkelkan,
dimana saya ingin memasukkan sesuatu seperti 26 ke dalam ini.
20?
Apa?
Ini are-- hal baik yang kita miliki pena ini.
Baiklah, 20.
Jika seseorang bisa mendapatkan sepotong kertas siap, hanya dalam case-- baik-baik.
Oh, menarik.
Nah ini adalah contoh bug kuliah.
OK jadi apa nama Anda lagi?
AUDIENCE: Julia.
DAVID J. Malan: Julia, dapat Anda pop dan berpura-pura Anda tidak pernah ada?
OK, ini tidak pernah terjadi.
Terima kasih.
Jadi misalkan kita ingin memasukkan Julia ke linked list ini.
Dia adalah nomor 20.
Dan tentu saja dia akan termasuk di
begin-- tidak menunjuk pada apa pun.
Jadi tangan Anda bisa menjadi jenis bawah nol atau nilai sampah.
Mari kita menceritakan kisah cepat.
Aku menunjuk angka 5 saat ini.
Kemudian saya cek 9.
Kemudian saya cek 17.
Kemudian saya cek 22.
Dan saya menyadari, ooh, Julia perlu untuk pergi sebelum 22.
Jadi apa yang harus terjadi?
Yang tangannya harus berubah?
Julia, tambang, atau-- siapa namamu lagi?
>> AUDIENCE: Kristen.
>> DAVID J. Malan: Kristen atau?
>> AUDIENCE: Andy.
>> DAVID J. Malan: Andy.
Kristen atau Andy?
Andy harus menunjuk?
Julia.
Baiklah.
Jadi Andy, apakah Anda ingin untuk menunjuk Julia?
Tapi tunggu dulu.
Dalam cerita sejauh ini, Aku semacam satu
yang bertanggung jawab, dalam arti bahwa pointer adalah hal yang
bergerak melalui daftar.
Kami mungkin memiliki nama untuk Andy, tapi tidak ada variabel yang disebut Andy.
Satu-satunya variabel lain yang kami miliki adalah pertama, siapa yang diwakili oleh Gabe.
>> Jadi ini sebenarnya mengapa demikian jauh kita sudah tidak diperlukan ini.
Tapi sekarang di layar ada menyebutkan lagi dari pointer pred.
Jadi biarkan aku menjadi lebih eksplisit.
Jika ini adalah pointer, aku lebih baik mendapatkan sedikit lebih cerdas
tentang iterasi saya.
Jika Anda tidak keberatan saya akan melalui sini lagi, menunjuk di sini, menunjuk di sini.
Tetapi saya memiliki pointer pred, pendahulunya pointer, itu
jenis menunjuk pada Unsur Aku hanya di.
Jadi ketika saya pergi di sini, sekarang saya update tangan kiri.
Ketika saya pergi di sini update tangan kiriku.
Dan sekarang aku tidak hanya pointer ke elemen yang pergi setelah Julia,
Saya masih memiliki pointer ke Andy, elemen sebelumnya.
Jadi Anda memiliki akses, pada dasarnya, remah roti, jika Anda mau,
untuk semua pointer yang diperlukan.
>> Jadi jika aku tunjuk Andy dan aku juga menunjuk
di Christian, yang tangannya sekarang harus menunjuk tempat lain?
Jadi Andy sekarang dapat menunjuk Julia.
Julia kini dapat menunjuk Kristen.
Karena dia dapat menyalin saya pointer tangan kanan itu.
Dan yang secara efektif menempatkan Anda kembali ke tempat ini di sini.
Jadi singkatnya, meskipun ini membawa kita jenis selamanya
untuk benar-benar memperbarui linked list, menyadari
bahwa operasi relatif sederhana.
Ini dari satu, dua, tiga baris kode pada akhirnya.
Tapi melilit mereka baris kode mungkin
adalah sedikit logika yang efektif mengajukan pertanyaan, di mana kita?
Apakah kita di awal, tengah, atau akhir?
>> Sekarang, tentu ada beberapa lainnya operasi kita mungkin diterapkan.
Dan foto-foto ini di sini hanya menggambarkan apa yang kita hanya melakukan dengan manusia.
Bagaimana dengan penghapusan?
Jika saya ingin, misalnya, menghapus nomor 34 atau 55,
Saya mungkin memiliki jenis yang sama dari kode, tapi aku akan membutuhkan satu atau dua langkah.
Karena Apa yang baru?
Jika saya menghapus seseorang di akhir, seperti nomor 55 dan kemudian 34,
apa juga harus berubah seperti yang saya lakukan itu?
Aku harus tidak evict-- siapa namamu lagi?
>> AUDIENCE: Jack.
>> DAVID J. Malan: Jack.
Aku harus tidak hanya evict-- gratis Jack, sehingga benar-benar panggilan gratis Jack, atau setidaknya
pointer di sana juga, tapi sekarang apa yang perlu diubah dengan Peter?
Tangannya lebih baik mulai mengarah ke bawah.
Karena begitu saya sebut gratis di Jack, jika Petrus masih menunjuk Jack
dan karena itu saya terus melintasi daftar dan akses pointer ini,
saat itulah teman segmentasi lama kita kesalahan mungkin benar-benar menendang.
Karena kita telah diberi memori kembali ke Jack.
>> Anda dapat tinggal di sana canggung untuk sesaat.
Karena kita memiliki hanya beberapa operasi akhir untuk dipertimbangkan.
Melepaskan kepala daftar, atau beginning-- dan satu ini
sedikit mengganggu.
Karena kita harus tahu bahwa Gabe adalah jenis khusus dalam program ini.
Karena memang, ia memiliki pointer sendiri.
Dia tidak hanya menjadi menunjuk, seperti hampir semua orang di sini.
>> Jadi, ketika kepala daftar adalah dihapus, yang tangannya harus berubah sekarang?
Siapa nama Anda lagi?
>> AUDIENCE: Christine.
>> DAVID J. Malan: Aku mengerikan pada nama, rupanya.
Jadi Christine dan Gabe, yang tangannya perlu mengubah
ketika kita mencoba untuk menghapus Christine, nomor 5, dari gambar?
OK, jadi mari kita lakukan Gabe.
Gabe akan menunjuk, mungkin, di nomor 9.
Tapi apa yang selanjutnya harus terjadi?
AUDIENCE: Christine harus null [Tak terdengar].
DAVID J. Malan: OK, kita harus mungkin make-- Aku mendengar "null" di suatu tempat.
AUDIENCE: Null dan bebas nya.
DAVID J. Malan: Null apa?
AUDIENCE: Null dan bebas nya.
DAVID J. Malan: Null dan bebas nya.
Jadi ini sangat mudah.
Dan itu sempurna bahwa Anda sekarang semacam berdiri di sana, tidak memiliki.
Karena Anda sudah dipisahkan dari daftar.
Kau sudah efektif yatim piatu dari daftar.
Jadi kita lebih baik panggilan gratis sekarang Christine untuk memberikan memori yang kembali.
Jika setiap kali kita menghapus node dari daftar
kita mungkin akan membuat daftar pendek, tetapi tidak benar-benar menurun
ukuran dalam memori.
Dan jadi jika kita terus menambahkan dan menambahkan, menambahkan hal-hal ke dalam daftar,
komputer saya mungkin akan lebih lambat dan lebih lambat dan lebih lambat,
karena aku kehabisan memori, bahkan jika aku tidak benar-benar
menggunakan byte Christine memori lagi.
>> Jadi pada akhirnya ada yang lain skenario, penghapusan course--
di tengah, penghapusan di akhir, seperti yang kita lihat.
Tapi yang lebih menarik Tantangan saat ini adalah
akan mempertimbangkan persis apa waktu berjalan adalah.
Jadi tidak hanya bisa Anda tetap Anda potongan kertas, jika, Gabe,
Anda tidak akan keberatan memberikan semua orang bola stres.
Terima kasih banyak untuk linked list kami relawan di sini, jika Anda bisa.
>> [Tepuk Tangan]
>> DAVID J. Malan: Baiklah.
Jadi beberapa analisis pertanyaan kemudian, jika aku bisa.
Kami telah melihat notasi ini sebelumnya, O besar dan omega, batas atas
dan batas bawah pada waktu berjalan beberapa algoritma.
Jadi mari kita pertimbangkan hanya beberapa pertanyaan.
>> Satu, dan kami mengatakan itu sebelumnya, apa yang sedang berjalan
waktu pencarian untuk daftar dalam hal O besar?
Apakah yang dimaksud dengan batas atas yang sedang berjalan saat mencari sebuah linked list
seperti yang diterapkan oleh relawan kami di sini?
Ini O besar n, linier.
Karena dalam kasus terburuk, elemen, seperti 55,
kita mungkin akan mencari mungkin di mana Jack, semua jalan di akhir.
Dan sayangnya, tidak seperti array kita tidak bisa mendapatkan mewah saat ini.
Meskipun semua manusia kami yang diurutkan dari elemen-elemen kecil, 5,
sepanjang jalan sampai ke elemen yang lebih besar, 55, yang biasanya hal yang baik.
Tapi apa asumsi bahwa tidak lagi memungkinkan kita untuk melakukan?
AUDIENCE: [Tak terdengar]
DAVID J. Malan: Katakanlah lagi?
AUDIENCE: Akses Acak.
DAVID J. Malan: Random access.
Dan pada gilirannya itu berarti kita tidak bisa lagi menggunakan angka nol yang lemah, intuisi,
dan kejelasan menggunakan biner Cari dan membagi dan menaklukkan.
Karena meskipun kami manusia bisa jelas
melihat bahwa Andy atau Kristen yang kira-kira di tengah-tengah daftar,
kita hanya tahu bahwa sebagai komputer dengan menggelapkan daftar
dari awal.
Jadi kita sudah menyerah bahwa akses acak.
>> O begitu besar dari n sekarang adalah atas terikat pada waktu pencarian kami.
Bagaimana omega pencarian kita?
Apa batas bawah pada pencarian untuk beberapa nomor dalam daftar ini?
AUDIENCE: [Tak terdengar]
DAVID J. Malan: Katakanlah lagi?
AUDIENCE: Satu.
DAVID J. Malan: Satu.
Jadi waktu konstan.
Dalam kasus terbaik, Christine adalah memang pada awal daftar.
Dan kami sedang mencari nomor 5, jadi kami menemukannya.
Jadi bukan masalah besar.
Tapi dia harus berada di awal dari daftar dalam kasus ini.
Bagaimana sesuatu seperti Hapus?
Bagaimana jika Anda ingin menghapus elemen?
Apa batas atas dan batas bawah tentang penghapusan sesuatu dari terkait
daftar?
AUDIENCE: [Tak terdengar]
DAVID J. Malan: Katakanlah lagi?
AUDIENCE: n.
DAVID J. Malan: n adalah memang batas atas.
Karena dalam kasus terburuk kami mencoba untuk menghapus Jack, seperti baru saja kita lakukan.
Dia semua jalan di akhir.
Membawa kita selamanya, atau n langkah-langkah untuk menemukannya.
Jadi itulah batas atas.
Itu linear, yakin.
Dan kasus terbaik waktu berjalan, atau batas bawah dalam kasus terbaik
akan waktu yang konstan.
Karena mungkin kita mencoba untuk menghapus Christine, dan kami hanya beruntung
dia di awal.
Sekarang tunggu sebentar.
Gabe juga di awal, dan kami juga harus memperbarui Gabe.
Jadi itu bukan hanya satu langkah.
Jadi, apakah itu memang konstan waktu, dalam kasus terbaik,
untuk menghapus elemen terkecil?
Hal ini, meskipun mungkin dua, tiga, atau bahkan 100 baris kode,
jika jumlah yang sama garis, tidak dalam beberapa lingkaran,
dan independen dari ukuran dari daftar, benar-benar.
Menghapus elemen pada awal daftar,
bahkan jika kita harus berurusan dengan Gabe, masih waktu yang konstan.
>> Jadi ini tampaknya seperti Langkah besar mundur.
Dan apa buang-buang waktu jika, dalam satu minggu dan minggu
nol kita tidak hanya kode pseudo tetapi kode aktual
untuk menerapkan sesuatu yang log dasar n, atau log, lebih tepatnya, dari n, basis 2,
dalam hal waktu yang berjalan.
Jadi mengapa sih akan kita ingin memulai menggunakan sesuatu seperti sebuah linked list?
Ya.
>> AUDIENCE: Jadi Anda dapat menambahkan elemen ke array.
DAVID J. Malan: Jadi Anda bisa menambahkan elemen ke array.
Dan ini juga adalah tematik.
Dan kita akan terus melihat ini, ini trade-off, banyak
seperti kita telah melihat trade-off dengan merge sort.
Kami benar-benar bisa mempercepat pencarian atau pengurutan, lebih tepatnya,
jika kita menghabiskan sedikit lebih banyak ruang dan memiliki potongan tambahan memori
atau sebuah array untuk merge sort.
Tapi kita menghabiskan lebih banyak ruang, tapi kami menghemat waktu.
Dalam hal ini, kami tidak memberikan waktu tapi kami
mendapatkan fleksibilitas, dinamisme jika Anda mau,
yang ini bisa dibilang fitur yang positif.
>> Kami juga menghabiskan ruang.
Dalam arti adalah terkait daftar lebih mahal
dalam hal ruang dari array?
Dimana ruang ekstra berasal?
Ya?
>> AUDIENCE: [Tak terdengar] pointer.
>> DAVID J. Malan: Ya, kami juga memiliki pointer.
Jadi ini minorly menjengkelkan di yang tidak lagi am
Aku menyimpan hanya int untuk mewakili int.
Aku menyimpan sebuah int dan pointer, yang juga 32 bit.
Jadi aku benar-benar dua kali lipat jumlah ruang yang terlibat.
Jadi itu adalah trade-off, namun itu dalam kasus int.
Misalkan Anda tidak menyimpan int, tapi kira setiap persegi panjang tersebut
atau masing-masing manusia ini mewakili kata, kata dalam bahasa Inggris yang
mungkin lima karakter, 10 karakter, bahkan mungkin lebih.
Kemudian menambahkan hanya 32 bit lebih mungkin kurang dari masalah besar.
>> Bagaimana jika masing-masing siswa dalam demonstrasi
secara harfiah struct mahasiswa yang memiliki nama dan rumah dan mungkin
nomor telepon dan Twitter menangani dan sejenisnya.
Jadi semua bidang kita mulai berbicara tentang hari,
apalagi dari masalah besar karena node kami mendapatkan lebih menarik
dan besar untuk belanja, eh, tambahan pointer hanya untuk menghubungkan mereka bersama-sama.
Tapi memang, itu adalah trade-off.
Dan memang, kode ini lebih kompleks, seperti yang Anda akan
melihat dengan menggelapkan melalui bahwa contoh tertentu.
Tapi bagaimana jika ada beberapa grail suci sini.
Bagaimana jika kita tidak mengambil langkah mundur tapi langkah besar ke depan
dan menerapkan data struktur melalui mana kita
dapat menemukan unsur-unsur seperti Jack atau Christine atau unsur-unsur lain
dalam array ini dalam waktu yang konstan benar?
Cari konstan.
Hapus konstan.
Insert konstan.
Semua operasi ini adalah konstan.
Itu akan menjadi grail suci kita.
Dan itulah di mana kami akan mengambil waktu berikutnya.
Sampai jumpa.