>> SPEAKER 1: Baiklah, jadi kami kembali.
Selamat Datang CS50.
Ini adalah akhir minggu ketujuh.
Jadi ingat bahwa terakhir kali, kami mulai melihat sedikit lebih canggih
struktur data.
Karena sampai sekarang, semua kita telah benar-benar kita miliki adalah ini, sebuah array.
>> Tapi sebelum kita membuang array tidak semua yang menarik, yang memang
sebenarnya adalah, apa adalah beberapa Plus ini data sederhana
Struktur sejauh ini?
Apa itu baik?
Sejauh yang kita lihat?
Apa yang Anda punya?
Tidak ada.
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Apa itu?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: ukuran tetap.
OK, jadi mengapa ukuran tetap baik meskipun?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: OK, jadi efisien dalam arti bahwa Anda dapat mengalokasikan
jumlah yang tetap ruang, yang diharapkan justru sebanyak
ruang yang Anda inginkan.
Sehingga bisa jadi benar-benar plus.
>> Apa sisi atas yang lain dari sebuah array?
Ya?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Semua - maaf?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Semua kotak dalam memori atau di samping satu sama lain.
Dan itu membantu - mengapa?
Itu cukup benar.
Tapi bagaimana kita dapat memanfaatkan kebenaran itu?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Tepat, kita bisa melacak di mana segala sesuatu hanya dengan mengetahui
satu alamat, yaitu alamat byte pertama dari sepotong memori.
Atau dalam kasus string, alamat pertama
arang dalam string tersebut.
Dan dari sana, kita dapat menemukan akhir string.
Kita dapat menemukan elemen kedua, Unsur ketiga, dan sebagainya.
>> Dan jadi cara mewah untuk menggambarkan bahwa Fitur adalah bahwa array memberi kita
random access.
Hanya dengan menggunakan braket persegi notasi dan nomor, Anda dapat melompat ke
elemen tertentu dalam array dalam waktu yang konstan, O besar
dari satu, sehingga untuk berbicara.
>> Tapi sudah ada beberapa kerugian.
Apa array tidak melakukannya dengan sangat mudah?
Apa itu tidak baik?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Apa itu?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Memperluas ukuran.
Jadi kelemahan dari array adalah justru kebalikan dari apa yang
upsides adalah.
Jadi salah satu kerugian adalah bahwa itu adalah ukuran tetap.
Jadi Anda tidak bisa benar-benar tumbuh itu.
Anda dapat mengalokasikan sepotong besar dari memori, dan kemudian memindahkan unsur lama
ke array baru.
Dan kemudian bebas array yang lama, untuk Misalnya, dengan menggunakan malloc atau serupa
fungsi yang disebut realloc, yang direalokasi memori.
>> Realloc, sebagai samping, mencoba untuk memberikan memori yang sebelah array
yang sudah Anda miliki.
Tapi mungkin memindahkan sekitar sama sekali.
Tapi singkatnya, itu mahal, kan?
Karena jika Anda memiliki sepotong memori ukuran ini, tapi Anda benar-benar ingin satu
ukuran ini, dan Anda ingin mempertahankan unsur-unsur asli, Anda harus
kira-kira proses penyalinan waktu linier yang perlu terjadi dari
array yang lama ke yang baru.
Dan kenyataannya adalah meminta operasi sistem lagi dan lagi dan
lagi untuk potongan besar memori dapat mulai dikenakan biaya beberapa waktu juga.
Jadi baik berkat dan kutukan di menyamarkan, fakta bahwa array
adalah ukuran tetap.
Tetapi jika kita memperkenalkan bukan sesuatu seperti ini, yang kami sebut terkait
Daftar, kami mendapatkan beberapa keuntungan dan beberapa kelemahan di sini juga.
>> Jadi linked list hanyalah sebuah data yang Struktur terdiri dari C structs dalam
kasus, di mana sebuah struct, ingat, hanya wadah untuk satu atau lebih spesifik
jenis variabel.
Dalam hal ini, apa tipe data tampaknya dalam struct yang
terakhir kali kita disebut node?
Masing-masing persegi panjang ini adalah sebuah node.
Dan masing-masing persegi panjang kecil di dalamnya adalah tipe data.
Jenis apa yang kita katakan mereka pada hari Senin?
Ya?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Sebuah variabel dan pointer, atau lebih khusus, int, untuk n,
dan pointer di bagian bawah.
Kedua mereka akan terjadi 32 bit, pada setidaknya pada komputer seperti CS50 ini
Appliance, dan jadi mereka ditarik sama dalam ukuran.
>> Jadi apa yang menggunakan pointer meskipun untuk rupanya?
Mengapa menambahkan panah ini sekarang ketika array yang begitu bagus dan bersih dan sederhana?
Apa yang pointer lakukan untuk kita di setiap node ini?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Tepat.
Ini memberitahu Anda di mana yang berikutnya.
Jadi saya semacam menggunakan analogi menggunakan benang untuk semacam
benang node ini bersama-sama.
Dan itulah apa yang kita lakukan dengan pointer karena masing-masing
potongan memori mungkin atau mungkin tidak berdekatan, kembali ke belakang ke belakang
dalam RAM, karena setiap kali Anda memanggil malloc mengatakan, cukup memberikan
byte untuk sebuah node baru, itu mungkin berada di sini atau mungkin di sini.
Mungkin di sini.
Anda hanya tidak tahu.
>> Tetapi menggunakan pointer di alamat mereka node, Anda bisa menjahit mereka
bersama-sama dengan cara yang terlihat secara visual seperti daftar bahkan jika hal-hal ini
semua tersebar di seluruh satu atau dua atau empat Anda gigabyte RAM
dalam komputer Anda sendiri.
>> Jadi sisi negatifnya, maka, sebuah linked list adalah apa?
Apa harga kita rupanya membayar?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Lebih banyak ruang, kan?
Kami telah, dalam kasus ini, dua kali lipat jumlah ruang karena kita sudah
dari 32 bit untuk setiap node, untuk setiap int, jadi sekarang 64 bit karena kita harus
menjaga sekitar pointer juga.
Anda mendapatkan efisiensi lebih jika struct Anda lebih besar dari hal sederhana ini.
Jika Anda benar-benar memiliki mahasiswa dalam yang merupakan beberapa string untuk
Nama dan rumah, mungkin nomor ID, mungkin beberapa bidang lain sama sekali.
>> Jadi jika Anda memiliki cukup struct besar, maka mungkin biaya pointer
bukan masalah besar.
Ini adalah sedikit dari kasus sudut dalam kita menyimpan seperti primitif sederhana
dalam linked list.
Tapi intinya adalah sama.
Anda pasti menghabiskan lebih memori, tetapi Anda mendapatkan
fleksibilitas.
Karena sekarang jika saya ingin menambahkan elemen pada awal daftar ini,
Saya harus mengalokasikan node baru.
Dan saya harus hanya memperbarui kedua panah entah bagaimana dengan hanya menggerakkan
beberapa petunjuk sekitar.
>> Jika saya ingin memasukkan sesuatu ke dalam tengah daftar, saya tidak perlu
mendorong semua orang selain seperti yang kami lakukan di minggu terakhir 'dengan para sukarelawan yang
mewakili sebuah array.
Aku hanya bisa mengalokasikan node baru dan kemudian hanya menunjuk panah di
arah yang berbeda karena tidak harus tetap aktual
memori garis sejati seperti saya sudah ditarik di sini di layar.
>> Dan kemudian terakhir, jika Anda ingin menyisipkan sesuatu di akhir daftar, itu
bahkan lebih mudah.
Ini adalah semacam notasi sewenang-wenang, tapi 34 's pointer, mengambil menebak.
Apa nilai pointer yang paling kemungkinan semacam ditarik dari seperti tua
antena sekolah di sana?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Ini mungkin nol.
Dan memang itu adalah salah satu penulis representasi null.
Dan itu null karena Anda benar-benar perlu tahu di mana akhir linked
daftar adalah, jangan sampai Anda tetap berikut dan mengikuti dan mengikuti panah-panah ini
untuk beberapa nilai sampah.
Jadi nol akan menunjukkan bahwa tidak ada lebih node di sebelah kanan nomor 34,
dalam kasus ini.
>> Jadi kami mengusulkan bahwa kita dapat menerapkan node ini dalam kode.
Dan kami telah melihat semacam ini sintaks sebelumnya.
Typedef hanya mendefinisikan tipe baru untuk kita, memberi kita sinonim seperti
String adalah untuk char *.
Dalam kasus ini, itu akan memberi kita notasi singkat sehingga struct simpul
bisa bukan hanya ditulis sebagai node, yang jauh lebih bersih.
Ini jauh lebih sedikit verbose.
>> Di dalam sebuah node tampaknya int disebut n, dan kemudian struct simpul *
yang berarti persis apa yang kita ingin panah berarti, pointer yang lain
node persis tipe data yang sama.
Dan saya mengusulkan agar kita bisa menerapkan fungsi pencarian seperti ini, yang pada
Sepintas mungkin tampak sedikit rumit.
Tapi mari kita lihat dalam konteks.
>> Biarkan aku pergi ke alat sini.
Mari saya membuka sebuah file yang bernama Daftar nol dot h.
Dan itu hanya berisi definisi kita hanya melihat beberapa saat yang lalu untuk data ini
Jenis disebut node.
Jadi kita sudah menempatkan bahwa ke dalam sebuah file dot h.
>> Dan sebagai samping, meskipun ini program yang Anda lihat adalah
tidak semua yang kompleks, itu memang konvensi ketika menulis sebuah program untuk
menempatkan hal-hal seperti tipe data, untuk menarik konstanta kadang-kadang, dalam Anda
header file dan tidak harus dalam C file Anda, tentu ketika Anda
program lebih besar dan lebih besar, sehingga Anda tahu di mana mencarinya baik untuk
dokumentasi dalam beberapa kasus, atau untuk dasar-dasar seperti ini,
definisi dari beberapa jenis.
>> Jika sekarang saya membuka daftar nol dot c, perhatikan beberapa hal.
Ini termasuk file header sedikit, kebanyakan yang telah kita lihat sebelumnya.
Ini termasuk file header sendiri.
>> Dan sebagai samping, mengapa yang dua kali lipat kutipan di sini, sebagai lawan sudut
kurung pada baris yang Aku sudah disorot sana?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Ya jadi file lokal.
Jadi jika itu file lokal Anda sendiri di sini on line 15, misalnya, Anda menggunakan
tanda kutip ganda sebagai gantinya dari kurung siku.
>> Sekarang ini adalah jenis yang menarik.
Perhatikan bahwa saya telah menyatakan global variabel dalam program ini jalur 18
dipanggil pertama, gagasan ini akan menjadi pointer yang pertama
node dalam linked list saya, dan saya sudah diinisialisasi ke nol, karena saya sudah
tidak mengalokasikan aktual node dulu.
>> Jadi ini mewakili, pictorially, apa yang kita melihat beberapa saat yang lalu dalam gambar
bahwa pointer pada jauh meninggalkan sisi.
Jadi sekarang, pointer yang tidak memiliki panah.
Ini bukan hanya nol.
Tapi itu mewakili apa yang akan menjadi alamat sebenarnya pertama
node dalam daftar ini.
Jadi saya sudah menerapkan itu adalah global karena, seperti yang akan Anda lihat, semua ini
Program tidak dalam hidup adalah menerapkan linked list untuk saya.
>> Sekarang aku punya beberapa prototipe di sini.
Saya memutuskan untuk mengimplementasikan fitur seperti penghapusan, penyisipan, mencari, dan
traversal -
yang terakhir hanya menjadi berjalan melintasi Daftar, mencetak unsur-unsurnya.
Dan sekarang inilah rutinitas utama saya.
Dan kita tidak akan menghabiskan terlalu banyak waktu pada ini karena ini adalah semacam, mudah-mudahan
topi tua sekarang.
>> Aku akan melakukan hal berikut, sementara pengguna bekerja sama.
Jadi satu, aku akan mencetak out menu ini.
Dan aku sudah diformat sebagai bersih yang aku bisa.
Jika pengguna jenis dalam satu, yang berarti mereka ingin menghapus sesuatu.
Jika jenis pengguna dalam dua, itu berarti mereka ingin memasukkan sesuatu.
Dan lain sebagainya.
Aku akan kemudian meminta maka untuk perintah.
Dan kemudian aku akan menggunakan getInt.
>> Jadi ini adalah benar-benar sederhana menuing antarmuka di mana Anda hanya perlu mengetikkan
pemetaan nomor satu perintah-perintah.
Dan sekarang saya memiliki tombol bagus bersih Pernyataan itu akan mengaktifkan
apa pun pengguna diketik masuk
Dan jika mereka mengetik satu, aku akan panggil delete dan istirahat.
Jika mereka mengetik dua, aku akan panggilan menyisipkan dan istirahat.
>> Dan sekarang perhatikan saya menempatkan masing-masing ini pada baris yang sama.
Ini hanya keputusan gaya.
Biasanya kita telah melihat sesuatu seperti ini.
Tapi aku hanya memutuskan, terus terang, program saya tampak lebih mudah dibaca karena
itu hanya empat kasus untuk hanya daftar seperti ini.
Penggunaan benar-benar sah gaya.
Dan aku akan melakukan hal ini asalkan pengguna belum diketik nol, yang saya
memutuskan akan berarti mereka ingin berhenti.
>> Jadi sekarang perhatikan apa yang saya akan dilakukan di sini.
Aku akan membebaskan daftar rupanya.
Tapi lebih pada bahwa hanya dalam beberapa saat.
Mari kita pertama kali menjalankan program ini.
Jadi biarkan aku membuat terminal besar window, dot daftar slash 0.
Aku akan pergi ke depan dan masukkan oleh mengetik dua, nomor seperti 50, dan sekarang
Anda akan melihat daftar sekarang 50.
Dan teks saya hanya menggulir sedikit.
Jadi sekarang melihat daftar berisi nomor 50.
>> Mari kita melakukan insert lain dengan mengambil dua.
Mari kita mengetikkan nomor seperti satu.
Daftar sekarang salah satu, diikuti oleh 50.
Jadi ini hanyalah sebuah representasi tekstual daftar.
Dan mari kita masukkan nomor satu lebih seperti nomor 42, yang mudah-mudahan
akan berakhir di tengah, karena Program ini macam tertentu itu
elemen seperti memasukkan mereka.
Jadi ada yang kita miliki.
Program super sederhana yang bisa benar-benar telah menggunakan sebuah array, tapi saya
kebetulan menggunakan linked list supaya saya bisa secara dinamis
tumbuh dan menyusut itu.
>> Jadi mari kita lihat untuk pencarian, jika saya menjalankan perintah tiga, saya ingin mencari
untuk, misalnya, jumlah 43.
Dan tidak ada yang tampaknya ditemukan, karena aku kembali tidak ada jawaban.
Jadi mari kita lakukan ini lagi.
Cari.
Mari kita mencari 50, atau lebih tepatnya mencari untuk 42, yang memiliki bagus
sedikit makna halus.
Dan aku menemukan makna kehidupan di sana.
Nomor 42, jika Anda tidak tahu referensi, Google itu.
Baik.
Jadi apa yang telah dilakukan program ini untuk saya?
Itu hanya memungkinkan saya untuk memasukkan sehingga jauh dan mencari elemen.
>> Mari kita cepat maju, kemudian, untuk fungsi yang kita melirik
Senin sebagai teaser.
Jadi fungsi ini, saya menyatakan, mencari elemen dalam daftar dengan pertama
satu, mendorong pengguna dan kemudian memanggil GetInt untuk mendapatkan int aktual
bahwa Anda ingin mencari.
>> Kemudian melihat ini.
Aku akan membuat variabel sementara sejalan 188 disebut pointer -
PTR -
bisa disebut apa-apa.
Dan itu pointer ke node karena aku bilang simpul * sana.
Dan aku memulainya untuk menjadi sama dengan pertama sehingga saya efektif punya saya
jari, sehingga untuk berbicara, di bagian paling elemen pertama dari daftar.
Jadi, jika tangan kanan saya di sini adalah PTR aku menunjuk pada hal yang sama yang pertama
adalah menunjuk.
>> Jadi sekarang kembali dalam kode, apa yang terjadi berikutnya -
ini adalah paradigma umum ketika iterasi atas struktur seperti
linked list.
Aku akan lakukan hal berikut saat pointer tidak sama dengan null Jadi sementara
jari saya tidak menunjuk pada beberapa nol nilai, jika pointer panah n sama n.
Kita akan melihat pertama bahwa n adalah apa yang pengguna mengetik per GetInts panggilan di sini.
>> Dan pointer panah n berarti apa?
Nah jika kita kembali ke gambar di sini, jika saya memiliki jari menunjuk
bahwa node pertama yang berisi sembilan, yang panah dasarnya berarti pergi ke
simpul dan ambil nilai di lokasi n, dalam hal ini, data lapangan yang disebut n.
>> Sebagai samping - dan kami melihat ini pasangan minggu lalu ketika seseorang bertanya -
sintaks ini adalah baru, tetapi tidak memberi kita kekuatan yang kita
tidak sudah memiliki.
Apa kalimat ini setara dengan menggunakan dot notasi dan bintang pasangan
minggu lalu ketika kita kupas kembali lapisan ini sedikit prematur?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Tepat, itu adalah bintang, dan maka itu star dot n, dengan
kurung di sini, yang terlihat, terus terang, saya pikir banyak
lebih samar untuk membaca.
Tapi bintang pointer, seperti biasa, berarti pergi ke sana.
Dan sekali Anda berada di sana, data apa bidang yang Anda ingin mengakses?
Nah Anda menggunakan notasi titik untuk mengakses data lapangan structs, dan saya
khusus ingin n.
>> Terus terang, saya berpendapat ini hanya sulit untuk dibaca.
Lebih sulit untuk mengingat di mana jangan tanda kurung pergi, yang
bintang dan semua itu.
Jadi dunia mengadopsi beberapa sintaksis gula, sehingga untuk berbicara.
Hanya cara seksi mengatakan, ini setara, dan
mungkin lebih intuitif.
Jika pointer memang pointer, yang panah notasi cara pergi ke sana dan menemukan
lapangan dalam hal ini disebut n.
>> Jadi jika saya menemukan itu, perhatikan apa yang saya lakukan.
Aku hanya mencetak, saya menemukan persen i, menghubungkannya dengan nilai int itu.
Saya sebut tidur selama satu detik hanya untuk jenis hal jeda pada layar untuk
memberikan pengguna kedua untuk menyerap apa yang baru saja terjadi.
Dan kemudian saya istirahat.
Jika tidak, apa yang harus saya lakukan?
Saya update pointer ke sama pointer panah di sebelah.
>> Jadi hanya harus jelas, ini berarti pergi ada, menggunakan notasi tua-sekolah saya.
Jadi ini hanya berarti pergi ke apa Anda menunjuk, yang dalam sangat
Kasus pertama adalah aku tunjuk struct dengan sembilan di dalamnya.
Jadi aku sudah ada.
Dan kemudian notasi titik berarti, mendapatkan nilai di depan.
>> Tapi nilai, meskipun itu ditarik sebagai sempit, hanya nomor.
Ini adalah alamat numerik.
Jadi satu baris kode ini, apakah ditulis seperti ini, lebih samar
cara, atau seperti ini, sedikit lebih cara intuitif, hanya berarti menggerakkan tanganku
dari simpul pertama ke yang berikutnya, dan kemudian yang berikutnya, dan kemudian
yang berikutnya, dan sebagainya.
>> Jadi kita tidak akan diam di sisi lain implementasi menyisipkan dan menghapus
dan traversal, dua pertama dari yang cukup terlibat.
Dan saya pikir itu cukup mudah untuk mendapatkan hilang ketika melakukan secara lisan.
Tapi apa yang bisa kita lakukan di sini adalah mencoba untuk menentukan bagaimana
terbaik untuk melakukan ini secara visual.
Karena saya akan mengusulkan bahwa jika kita ingin memasukkan unsur-unsur ke dalam
daftar yang ada, yang memiliki lima unsur -
9, 17, 22, 26, dan 33 -
jika saya akan menerapkan ini dalam kode, saya harus mempertimbangkan bagaimana untuk pergi
melakukan hal ini.
>> Dan saya akan mengusulkan mengambil langkah-langkah bayi dimana, dalam hal ini maksud saya, apa yang
skenario yang mungkin bahwa kita mungkin menghadapi secara umum?
Ketika menerapkan insert untuk linked daftar, ini hanya terjadi menjadi
Contoh spesifik ukuran lima.
Nah jika Anda ingin menyisipkan angka, seperti mengatakan nomor satu, dan
menjaga ketertiban diurutkan, di mana jelas apakah nomor satu perlu
pergi dalam contoh khusus ini?
Seperti di awal.
>> Tapi apa yang menarik di sana adalah bahwa jika Anda ingin memasukkan satu ke ini
Daftar, apa pointer kebutuhan khusus harus diperbarui rupanya?
Pertama.
Jadi saya berpendapat, ini adalah kasus pertama bahwa kita mungkin ingin mempertimbangkan, sebuah
Skenario yang melibatkan memasukkan di awal daftar.
>> Mari kita merobek mungkin sebuah semudah atau bahkan kasus mudah, relatif berbicara.
Misalkan saya ingin memasukkan nomor 35 dalam rangka diurutkan.
Ini jelas milik sana.
Jadi apa pointer jelas akan harus diperbarui dalam skenario itu?
34 's pointer menjadi tidak null tapi alamat struct
berisi nomor 35.
Jadi itu yang terjadi dua.
Jadi sudah, aku agak mengkuantisasi berapa banyak pekerjaan yang harus saya lakukan di sini.
>> Dan akhirnya, kasus tengah jelas adalah memang, di tengah, jika saya ingin
memasukkan sesuatu seperti mengatakan 23, yang berlangsung antara 23 dan 26, tetapi
sekarang hal mendapatkan sedikit lebih terlibat karena apa
pointer perlu diubah?
Jadi 22 jelas perlu diubah karena ia tidak dapat menunjukkan 26 lagi.
Dia perlu untuk menunjuk ke simpul baru yang Aku harus mengalokasikan dengan menelepon
malloc atau setara.
>> Tapi kemudian saya juga membutuhkan node baru, 23 dalam hal ini, memiliki pointer
menunjuk siapa?
26.
Dan ada akan menjadi urutan operasi di sini.
Karena jika aku melakukan ini bodoh, dan saya misalnya mulai dari awal
daftar, dan tujuan saya adalah untuk memasukkan 23.
Dan saya cek, itu milik di sini, di dekat sembilan?
Tidak.
Apakah itu termasuk di sini, di samping 17?
Tidak.
Apakah itu milik di sini di samping 22?
Ya.
>> Sekarang jika saya bodoh di sini, dan tidak berpikir ini melalui, aku mungkin
mengalokasikan node baru saya untuk 23.
Aku mungkin memperbarui pointer dari node disebut 22, menunjuk
itu pada node baru.
Lalu apa yang harus saya harus memperbarui pointer node baru untuk menjadi?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Tepat.
Sambil menunjuk 26.
Tapi sialan jika aku tidak sudah memperbarui 22 itu pointer untuk menunjuk pada orang ini, dan
sekarang aku punya anak yatim, sisanya dari daftar, sehingga untuk berbicara.
Jadi urutan operasi di sini akan menjadi penting.
>> Untuk melakukan hal ini bisa saya mencuri, mengatakan, enam sukarelawan.
Dan mari kita lihat apakah kita tidak bisa melakukan ini visual bukan kode-bijaksana.
Dan kami memiliki beberapa stres yang indah bola untuk Anda hari ini.
OK, bagaimana kalau satu, dua, dalam kembali - di ujung sana.
tiga, empat, kalian berdua orang di ujungnya.
Dan lima, enam.
Tentu.
Lima dan enam.
Semua benar dan kami akan datang untuk kalian waktu berikutnya.
Baiklah, ayo bangun.
>> Baiklah, karena kau di sini pertama, Anda ingin menjadi orang yang canggung
di Google Kaca sini?
Baiklah, jadi, OK, Kaca, merekam video.
OK, Anda baik untuk pergi.
>> Baiklah, jadi jika kalian bisa datang di sini, saya telah dipersiapkan sebelumnya
beberapa angka.
Baiklah, ayo ke sini.
Dan kenapa tidak Anda pergi sedikit lanjut seperti itu.
Dan mari kita lihat, siapa namamu, dengan Google Glass?
>> SISWA: Ben.
>> SPEAKER 1: Ben?
OK, Ben, Anda akan menjadi yang pertama, secara harfiah.
Jadi kita akan mengirim Anda ke ujung panggung.
Baiklah, dan nama Anda?
>> SISWA: Jason.
>> SPEAKER 1: Jason, Anda akan OK menjadi nomor sembilan.
Jadi jika Anda ingin mengikuti Ben seperti itu.
>> SISWA: Jill.
>> SPEAKER 1: Jill, Anda akan menjadi 17, yang jika aku melakukan ini lebih
cerdas, aku akan dimulai di ujung lain.
Anda pergi ke arah sana.
22.
Dan Anda?
>> SISWA: Mary.
>> SPEAKER 1: Mary, Anda akan 22.
Dan nama Anda?
>> SISWA: Chris.
>> SPEAKER 1: Chris, Anda akan 26.
Dan kemudian terakhir.
>> SISWA: Diana.
>> SPEAKER 1: Diana, Anda akan 34.
Jadi kau datang ke sini.
>> Baiklah, jadi sempurna diurutkan memesan sudah.
Dan mari kita pergi ke depan dan melakukan hal ini sehingga kita benar-benar bisa -
Ben Anda hanya semacam mencari keluar ke mana-mana ada.
OK, jadi mari kita pergi ke depan dan menggambarkan ini menggunakan senjata, seperti aku, tepatnya,
apa yang terjadi.
Jadi pergi ke depan dan memberi dirimu kaki atau dua antara dirimu.
Dan pergi ke depan dan menunjuk dengan satu tangan untuk siapapun Anda harus menunjuk
berdasarkan ini.
Dan jika Anda hanya menunjukkan nol lurus ke bawah ke lantai.
OK, jadi baik.
>> Jadi sekarang kita memiliki sebuah linked list, dan biarkan aku mengusulkan bahwa saya akan memainkan peran
PTR, jadi saya tidak akan repot-repot membawa ini sekitar.
Dan kemudian - seseorang konvensi bodoh - Anda dapat memanggil apa ini yang Anda inginkan -
pendahulunya pointer, pointer pred -
itu hanya julukan kami berikan kode sampel kami ke tangan kiri saya.
Sisi lain yang akan menjaga melacak siapa yang di
mengikuti skenario.
>> Jadi misalkan, pertama, saya ingin merobek bahwa contoh pertama memasukkan, katakanlah
20, ke dalam daftar.
Jadi aku akan membutuhkan seseorang untuk mewujudkan nomor 20 bagi kita.
Jadi saya harus malloc seseorang dari penonton.
Ayo up.
Siapa nama Anda?
>> SISWA: Brian.
>> SPEAKER 1: Brian, baiklah, sehingga Anda akan menjadi node yang berisi 20.
Baiklah, ayo ke sini.
Dan jelas, mana apakah Brian milik?
Jadi, di tengah - sebenarnya, tunggu sebentar.
Kami melakukan ini rusak.
Kami membuat ini jauh lebih sulit daripada harus pada awalnya.
OK, kita akan bebas Brian dan realloc Brian lima.
>> OK, jadi sekarang kita ingin menyisipkan Brian lima.
Jadi datang ke sini di samping Ben untuk sesaat.
Dan Anda mungkin dapat memberitahu dimana kisah ini terjadi.
Tapi mari berpikir hati-hati tentang urutan operasi.
Dan itu justru visual ini itu akan berbaris
dengan kode contoh.
Jadi di sini saya telah PTR menunjuk awalnya tidak pada Ben, per se, tetapi pada apa pun
menghargai dia mengandung, yang dalam hal ini adalah - siapa namamu lagi?
>> SISWA: Jason.
>> SPEAKER 1: Jason, sehingga kedua aku dan Ben menunjuk Jason saat ini.
Jadi sekarang aku harus menentukan, dari mana Brian milik?
Jadi satu-satunya hal yang saya memiliki akses ke sekarang adalah n item data nya.
Jadi aku akan memeriksa, adalah Brian kurang dari Jason?
Jawabannya adalah benar.
>> Jadi apa yang sekarang perlu terjadi, dalam urutan yang benar?
Saya perlu memperbarui berapa banyak pointer secara total dalam cerita ini?
Dimana tanganku masih menunjuk Jason, dan tangan Anda - jika Anda ingin
meletakkan tangan Anda seperti, semacam, saya tidak tahu, tanda tanya.
OK, baik.
>> Baiklah, sehingga Anda memiliki beberapa calon.
Baik Ben maupun I atau Brian atau Jason atau orang lain, yang
pointer perlu berubah?
Berapa banyak total?
>> OK, jadi dua.
Pointer saya tidak benar-benar peduli lagi karena aku hanya sementara.
Jadi dua orang, mungkin, kedua Ben dan Brian.
Jadi biarkan saya mengusulkan agar kita memperbarui Ben, karena ia yang pertama.
Elemen pertama dari daftar ini sekarang akan menjadi Brian.
Jadi Ben titik di Brian.
OK, sekarang apa?
>> Siapa yang akan menunjuk siapa?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: OK jadi Brian memiliki untuk menunjuk Jason.
Tapi apakah saya kehilangan jejak pointer itu?
Apakah saya tahu di mana Jason?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: saya lakukan, karena aku pointer sementara.
Dan mungkin, saya belum berubah untuk menunjuk pada simpul baru.
Jadi kita hanya dapat memiliki Brian titik pada siapa aku tunjuk.
Dan kita sudah selesai.
Jadi satu kasus, penyisipan di awal daftar.
Ada dua langkah kunci.
Satu, kita harus memperbarui Ben, dan kemudian kita juga harus memperbarui Brian.
Dan kemudian aku tidak perlu repot-repot traipsing melalui sisa
daftar, karena kita sudah menemukan nya lokasi, karena dia milik
kiri dari elemen pertama.
>> Baiklah, jadi cukup sederhana.
Bahkan, rasanya kita sudah hampir membuat ini terlalu rumit.
Jadi mari kita merobek akhir daftar, dan melihat di mana
kompleksitas dimulai.
Jadi kalau sekarang, aku alokasi dari penonton.
Siapapun ingin bermain 55?
Baiklah, saya melihat tangan Anda terlebih dahulu.
Ayo up.
Ya.
Siapa nama Anda?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Habata.
OK, datang ke atas.
Anda akan menjadi nomor 55.
Jadi Anda, tentu saja, termasuk pada akhir daftar.
Jadi mari kita memutar ulang simulasi dengan saya menjadi PTR untuk sesaat.
Jadi aku pertama akan menunjuk pada apapun Ben menunjuk.
Kami berdua menunjuk sekarang di Brian.
Jadi 55 adalah tidak kurang dari lima.
Jadi aku akan memperbarui diri dengan menunjuk ke pointer berikutnya Brian, yang
sekarang tentu saja Jason.
55 tidak kurang dari sembilan, sehingga Aku akan memperbarui PTR.
Aku akan memperbarui PTR Aku akan memperbarui PTR.
Dan aku akan - hmm, apa Nama Anda lagi?
>> SISWA: Diana.
>> SPEAKER 1: Diana menunjuk, tentu saja, di nol dengan tangan kirinya.
Jadi bagaimana sebenarnya Habata milik jelas?
Di sebelah kiri, di sini.
Jadi bagaimana saya tahu untuk menempatkan dia di Sini Saya pikir saya sudah kacau.
Karena apa yang PTR seni saat ini dalam waktu?
Null.
Jadi meskipun, secara visual, kita bisa jelas melihat semua ini
orang di sini di atas panggung.
Aku sudah tidak terus melacak sebelumnya orang dalam daftar.
Saya tidak memiliki jari menunjuk keluar, dalam hal ini, node nomor 34.
>> Jadi mari kita benar-benar mulai selama ini.
Jadi sekarang aku benar-benar perlu sebuah variabel lokal kedua.
Dan ini adalah apa yang akan Anda lihat di sebenarnya contoh kode C, di mana saat aku pergi,
ketika saya memperbarui tangan kananku ke titik Jason, sehingga meninggalkan Brian belakang, saya
sebaiknya mulai menggunakan tangan kiri saya untuk memperbarui mana aku berada, sehingga saat aku pergi
melalui daftar ini -
lebih canggung daripada aku berniat sekarang di sini visual -
Aku akan sampai ke akhir daftar.
>> Tangan ini masih nol, yang cukup berguna, selain untuk menunjukkan
Aku jelas di akhir daftar, tapi sekarang setidaknya aku punya ini
pendahulunya pointer menunjuk sini, jadi sekarang apa tangan dan apa yang perlu pointer
harus diperbarui?
Tangan siapa yang Anda inginkan untuk mengkonfigurasi ulang pertama?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: OK, jadi Diana.
Di mana Anda ingin menunjukkan Pointer kiri Diana di?
Pada 55, mungkin, sehingga kami telah dimasukkan di sana.
Dan di mana harus 55 pointer pergi?
Bawah, mewakili nol.
Dan tangan saya, pada saat ini, jangan penting karena mereka hanya
variabel sementara.
Jadi sekarang kita sudah selesai.
>> Jadi kompleksitas tambahan di sana - dan itu tidak sulit untuk melaksanakan,
tetapi kita perlu variabel sekunder untuk membuat Pastikan bahwa sebelum aku pindah kananku
tangan, aku memperbarui nilai kiriku tangan, pointer pred dalam kasus ini, sehingga
bahwa saya memiliki pointer membuntuti untuk melacak di mana aku berada.
Sekarang sebagai samping, jika Anda berpikir ini melalui, ini terasa seperti itu
sedikit menjengkelkan harus tetap melacak tangan kiri ini.
>> Apa yang akan solusi lain untuk masalah ini telah?
Jika Anda harus mendesain ulang data struktur kita berbicara
melalui sekarang?
Jika ini jenis hanya dari terasa sedikit mengganggu untuk memiliki, seperti, dua pointer
akan melalui daftar, siapa lagi yang bisa telah, dalam dunia ideal, dipertahankan
informasi yang kita butuhkan?
Ya?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Tepat.
Tepat sehingga sebenarnya ada yang menarik kuman dari sebuah ide.
Dan ide ini dari sebuah pointer sebelumnya, menunjuk pada elemen sebelumnya.
Bagaimana jika saya hanya diwujudkan bahwa dalam daftar itu sendiri?
Dan itu akan menjadi sulit untuk memvisualisasikan ini tanpa semua kertas
jatuh ke lantai.
Tapi anggaplah bahwa orang-orang ini digunakan baik dari tangan mereka untuk memiliki sebelumnya
pointer, dan pointer berikutnya, sehingga menerapkan apa yang akan kita sebut ganda
linked list.
Yang akan memungkinkan saya untuk semacam mundur, jauh lebih mudah tanpa saya,
programmer, harus menjaga melacak secara manual -
benar-benar secara manual -
di mana saya telah sebelumnya dalam daftar.
Jadi kita tidak akan melakukan itu.
Kami akan tetap sederhana karena itulah akan datang pada harga, dua kali
banyak ruang untuk pointer, jika Anda ingin yang kedua.
Tapi itu memang umum struktur data yang dikenal sebagai
daftar ganda terkait.
>> Mari kita lakukan contoh terakhir di sini dan menaruh orang-orang ini keluar dari penderitaan mereka.
Jadi malloc 20.
Ayo naik dari lorong sana.
Baiklah, siapa namamu?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Maaf?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Demeron?
OK naiklah.
Anda harus 20.
Anda jelas akan milik antara 17 dan 22.
Jadi biarkan aku belajar pelajaran saya.
Aku akan memulai pointer menunjuk Brian.
Dan aku akan memiliki tangan kiriku hanya update ke Brian saat aku pindah ke
Jason, pemeriksaan tidak 20 kurang dari sembilan?
Tidak.
Adalah 20 kurang dari 17?
Tidak.
Adalah 20 kurang dari 22?
Ya.
Jadi apa pointer atau tangan perlu mengubah di mana mereka menunjuk sekarang?
>> Jadi kita bisa melakukan 17 menunjuk pada 20.
Jadi itu bagus.
Di mana kami ingin menunjukkan pointer Anda sekarang?
Pada 22.
Dan kita tahu di mana 22 adalah, sekali lagi terima kasih untuk pointer sementara saya.
Jadi kita OK ada.
Jadi karena penyimpanan sementara ini Aku terus melacak di mana setiap orang.
Dan sekarang Anda secara visual dapat pergi ke mana Anda milik, dan sekarang kami harus 1, 2, 3,
4, 5, 6, 7, 8, 9 bola stres, dan tepuk tangan untuk
orang-orang ini, jika kita bisa.
Baik dilakukan.
>> [Tepuk Tangan]
>> SPEAKER 1: Baiklah.
Dan Anda dapat menyimpan potongan-potongan kertas sebagai kenang-kenangan.
>> Baiklah, jadi, percayalah itu banyak mudah untuk berjalan melalui bahwa dengan
manusia daripada dengan kode aktual.
Tapi apa yang Anda akan menemukan hanya dalam beberapa saat sekarang, adalah bahwa sama - oh, terima kasih.
Terima kasih -
adalah bahwa Anda akan menemukan bahwa data yang sama struktur, linked list, dapat benar-benar
digunakan sebagai blok bangunan untuk lebih struktur data yang canggih.
>> Dan menyadari terlalu tema di sini adalah bahwa kita sudah benar-benar diperkenalkan lebih
kompleksitas dalam pelaksanaan algoritma ini.
Penyisipan, dan jika kami pergi melalui itu, penghapusan dan pencarian, sedikit
lebih rumit daripada adalah dengan array.
Tapi kita mendapatkan beberapa dinamisme.
Kami mendapatkan struktur data adaptif.
>> Tapi sekali lagi, kita membayar harga memiliki beberapa kompleksitas tambahan, baik dalam
mengimplementasikannya.
Dan kita diberi akses acak.
Dan jujur, tidak ada beberapa nice membersihkan geser saya bisa memberikan Anda bahwa
mengatakan di sini adalah mengapa sebuah linked list lebih baik dari array.
Dan berhenti di situ.
Karena tema reoccurring sekarang, bahkan lebih dalam beberapa minggu mendatang, adalah
bahwa tidak ada tentu jawaban yang benar.
>> Inilah sebabnya mengapa kita memiliki sumbu terpisah desain untuk set masalah.
Ini akan sangat sensitif konteks apakah Anda ingin menggunakan data ini
struktur atau yang satu, dan akan tergantung pada apa yang penting bagi Anda dalam hal
sumber daya dan kompleksitas.
>> Tapi biarkan aku mengusulkan bahwa data yang ideal struktur, grail suci, akan
sesuatu yang waktu yang konstan, terlepas dari berapa banyak barang yang
dalamnya, tidak akan menjadi luar biasa jika struktur data kembali jawaban dalam
waktu yang konstan.
Ya.
Kata ini dalam kamus besar Anda.
Atau tidak, kata ini tidak.
Atau masalah tersebut ada.
Nah mari kita lihat jika kita tidak bisa setidaknya mengambil langkah menuju itu.
>> Mari saya mengusulkan struktur data baru yang dapat digunakan untuk hal yang berbeda,
dalam hal ini disebut tabel hash.
Dan jadi kita benar-benar kembali ke melirik pada array, dalam kasus ini, dan
agak sewenang-wenang, saya sudah ditarik ini tabel hash sebagai array dengan semacam
array dua dimensi -
atau lebih tepatnya itu digambarkan di sini sebagai dua dimensi array - tapi ini hanya
array ukuran 26, sehingga jika kita memanggil tabel array, tabel braket
nol adalah persegi panjang di bagian atas.
Tabel braket 25 adalah persegi panjang di bagian bawah.
Dan ini adalah bagaimana saya bisa menggambar Data struktur di mana saya ingin menyimpan
nama orang.
>> Jadi misalnya, dan saya tidak akan menarik Semuanya di sini pada biaya overhead, jika saya
memiliki array ini, yang aku sekarang akan memanggil tabel hash, dan ini lagi
lokasi nol.
Ini di sini adalah lokasi satu, dan sebagainya.
Saya menyatakan bahwa saya ingin menggunakan data ini struktur, demi diskusi,
untuk menyimpan nama orang, Alice dan Bob dan Charlie dan nama-nama seperti lainnya.
Jadi pikirkan sekarang ini sebagai awal , katakanlah, kamus
dengan banyak kata-kata.
Mereka kebetulan nama dalam contoh kita di sini.
Dan ini semua terlalu erat, mungkin, untuk menerapkan pemeriksa ejaan, seperti yang kita
mungkin untuk masalah menetapkan enam.
>> Jadi jika kita memiliki sebuah array dari ukuran total 26 sehingga ini adalah lokasi-25
di bagian bawah, dan saya menyatakan bahwa Alice adalah kata pertama dalam kamus
nama yang saya ingin masukkan ke dalam RAM, ke dalam struktur data, dimana
naluri memberitahu Anda bahwa Alice Nama harus pergi dalam array ini?
>> Kami memiliki 26 pilihan.
Dimana kita ingin menempatkan dia?
Kami ingin dia di braket nol, kan?
A untuk Alice, mari kita sebut bahwa nol.
Dan B akan menjadi salah satu, dan C akan menjadi dua.
Jadi kita akan menulis Alice nama di sini.
Jika kita kemudian memasukkan Bob, nya Nama akan pergi di sini.
Charlie akan pergi di sini.
Dan sebagainya bawah melalui ini struktur data.
>> Ini adalah struktur data yang indah.
Kenapa?
Nah apa waktu berjalan memasukkan nama manusia ke dalam ini
struktur data sekarang?
Mengingat bahwa tabel ini diimplementasikan, benar-benar, sebagai array.
Yah sudah waktunya konstan.
Ini urutan satu.
Kenapa?
>> Nah bagaimana Anda menentukan di mana Alice milik?
Anda melihat di mana surat namanya?
Pertama.
Dan Anda bisa sampai di sana, jika string, dengan hanya melihat tali
braket nol.
Jadi karakter ke nol dari string.
Itu mudah.
Kami melakukan itu di kripto tugas minggu lalu.
Dan kemudian setelah Anda tahu bahwa Alice huruf modal, kita dapat mengurangi
off 65 atau modal A sendiri, yang memberi kita nol.
Jadi kita sekarang tahu bahwa Alice milik di lokasi nol.
>> Dan mengingat pointer ke data ini struktur, dari beberapa macam, berapa lama
itu membawa saya untuk menemukan lokasi nol dalam array?
Hanya satu langkah, tepat Ini waktu yang konstan karena akses acak kita
diusulkan adalah fitur dari sebuah array.
Jadi singkatnya, mencari tahu apa indeks nama Alice adalah, yang, dalam
kasus ini, adalah A, atau mari kita menyelesaikan bahwa untuk nol, dimana B adalah satu dan C adalah
dua, dengan pertimbangan bahwa keluar adalah waktu yang konstan.
Aku hanya harus melihat huruf pertama, mencari tahu di mana nol adalah
array juga waktu yang konstan.
Jadi secara teknis itu seperti dua langkah sekarang.
Tapi itu masih konstan.
Jadi kita sebut bahwa O besar satu, jadi kami sudah dimasukkan Alice ke dalam tabel ini dalam
waktu yang konstan.
>> Tapi tentu saja, aku sedang naif di sini, kan?
Bagaimana jika ada sebuah Harun di kelas?
Atau Alicia?
Atau nama lain dimulai dengan A. Dimana kita akan menempatkan
orang itu, kan?
Maksudku, sekarang hanya ada tiga orang di atas meja, jadi mungkin kita
harus menempatkan Aaron di lokasi nol satu dua tiga.
>> Benar, aku bisa menempatkan A di sini.
Tapi kemudian, jika kita mencoba untuk memasukkan David ke daftar ini, mana David pergi?
Sekarang sistem kami mulai melanggar bawah, kanan?
Karena sekarang David berakhir di sini jika Aaron sebenarnya di sini.
Dan sekarang ini seluruh ide memiliki struktur data bersih yang memberi kita
sisipan waktu yang konstan tidak lagi waktu yang konstan, karena saya harus
periksa, oh, sialan, seseorang sudah di lokasi Alice.
>> Biarkan aku menyelidiki sisa data ini struktur, mencari tempat untuk meletakkan
seseorang seperti nama Harun.
Dan itu juga mulai untuk mengambil waktu linier.
Apalagi, jika Anda sekarang ingin menemukan Harun dalam struktur data, dan Anda
cek, dan nama Harun tidak ada di sini.
Idealnya, Anda hanya akan mengatakan Harun tidak dalam struktur data.
Tapi jika Anda mulai membuat ruang untuk Aaron mana seharusnya ada D
atau E, Anda, kasus terburuk, harus memeriksa struktur data keseluruhan,
hal ini devolves menjadi sesuatu linear dalam ukuran meja.
>> Jadi baik-baik saja, saya akan memperbaiki ini.
Masalahnya di sini adalah bahwa saya punya 26 elemen dalam array ini.
Biarkan aku mengubahnya.
Whoops.
Biarkan aku mengubahnya sehingga agak kesejahteraan ukuran 26 secara total, perhatikan bagian bawah
Indeks akan berubah menjadi n dikurangi 1.
Jika 26 adalah jelas terlalu kecil bagi manusia ' nama, karena ada ribuan
nama dunia, mari kita membuat dalam 100 atau 1.000 atau 10.000.
Mari kita mengalokasikan lebih banyak ruang.
>> Nah itu tidak selalu menurun kemungkinan bahwa kita tidak akan memiliki dua
orang-orang dengan nama dimulai dengan A, dan demikian, Anda akan mencoba untuk menempatkan A
nama di lokasi nol masih.
Mereka masih akan bertabrakan, yang berarti kita masih perlu solusi untuk menempatkan
Alice dan Harun dan Alicia dan lainnya nama dimulai dengan tempat lain A.
Tapi berapa banyak dari masalah ini?
Apa probabilitas bahwa Anda memiliki tabrakan di data
Struktur seperti ini?
>> Nah, biarkan aku - kami akan kembali untuk pertanyaan itu di sini.
Dan lihat bagaimana kita mungkin menyelesaikannya terlebih dahulu.
Biarkan aku menarik usulan ini di sini.
Apa yang kita baru saja dijelaskan adalah algoritma, heuristik disebut linear
menyelidik dimana, jika Anda mencoba untuk memasukkan sesuatu di sini dalam data ini
struktur, yang disebut tabel hash, dan tidak ada ruang di sana, Anda
benar-benar menyelidiki struktur data memeriksa, apakah ini tersedia?
Apakah Tersedia ini tersedia ini?
Apakah ini tersedia?
Dan ketika akhirnya adalah, Anda memasukkan nama yang awalnya ditujukan
tempat lain di lokasi itu.
Tapi dalam kasus terburuk, satu-satunya tempat mungkin bagian paling bawah dari data
struktur, akhir array.
>> Jadi linear probing, dalam kasus terburuk, devolves ke algoritma linear dimana
Harun, jika ia kebetulan dimasukkan lalu dalam struktur data, ia mungkin
berbenturan dengan lokasi pertama ini, namun kemudian berakhir dengan nasib buruk di akhir.
Jadi ini bukan sebuah konstanta waktu grail suci bagi kita.
Pendekatan elemen memasukkan ke struktur data yang disebut hash
tabel tampaknya tidak menjadi waktu yang konstan setidaknya tidak dalam kasus umum.
Hal ini dapat berpindah ke sesuatu yang linear.
>> Jadi bagaimana jika kita menyelesaikan tabrakan agak berbeda?
Jadi, inilah yang lebih canggih pendekatan apa yang masih
disebut tabel hash.
Dan dengan hash, sebagai samping, apa Maksudku adalah indeks yang
Saya sebut sebelumnya.
Untuk sesuatu yang hash dapat dianggap sebagai kata kerja.
>> Jadi jika Anda hash Alice adalah nama, fungsi hash, sehingga untuk berbicara,
harus kembali nomor.
Dalam hal ini adalah nol jika dia milik di lokasi nol, satu jika dia milik di
lokasi satu, dan sebagainya.
Jadi fungsi hash saya sejauh ini telah super sederhana, hanya melihat
huruf pertama dalam nama seseorang.
Tapi fungsi hash mengambil sebagai masukan beberapa bagian dari data,
String, int, apa pun.
Dan meludah keluar biasanya nomor.
Dan nomor itu adalah di mana data elemen termasuk dalam struktur data
dikenal di sini sebagai tabel hash.
>> Jadi hanya intuitif, ini adalah konteks yang sedikit berbeda.
Ini sebenarnya adalah mengacu pada contoh melibatkan ulang tahun, di mana
mungkin ada sebanyak 31 hari dalam sebulan.
Tapi apa orang ini memutuskan untuk dilakukan jika terjadi tabrakan?
Konteks sekarang sedang, bukan tabrakan nama, tapi tabrakan ulang tahun,
jika dua orang memiliki ulang tahun yang sama pada tanggal 2 Oktober, misalnya.
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Ya, jadi di sini kita memiliki , mewarnai daftar terkait.
Jadi terlihat sedikit berbeda daripada kita menarik itu sebelumnya.
Tapi kita tampaknya harus array di sisi kiri.
Itulah salah satu indeks, karena tidak ada alasan tertentu.
Tapi itu masih array.
Ini sebuah array dari pointer.
Dan masing-masing unsur, masing-masing kalangan ini atau garis miring - slash
mewakili nol - masing-masing pointer rupanya menunjuk ke
apa struktur data?
Sebuah linked list.
>> Jadi sekarang kita memiliki kemampuan untuk kode keras ke dalam program kami
ukuran meja.
Dalam kasus ini, kita tahu tidak pernah ada lebih dari 31 hari dalam sebulan.
Jadi hard coding nilai seperti 31 adalah wajar dalam konteks itu.
Dalam konteks nama, hard coding 26 tidak masuk akal itu orang
hanya nama mulai dengan, misalnya, alfabet yang melibatkan A sampai Z.
>> Kita bisa menjejalkan mereka semua ke dalam data Struktur asalkan, ketika kita mendapatkan
tabrakan, kita tidak menempatkan nama di sini, kita malah memikirkan sel-sel
bukan sebagai string sendiri, tetapi sebagai pointer ke, misalnya, Alice.
Dan kemudian Alice dapat memiliki pointer lain ke nama lain dimulai dengan
A. Dan Bob benar-benar berjalan di sini.
>> Dan jika ada nama lain mulai dengan B, ia berakhir di sini.
Dan masing-masing unsur ini dua meja, jika kita merancang ini
sedikit lebih cerdik -
ayolah -
jika kita merancang ini lebih sedikit cerdik, sekarang menjadi data yang adaptif
struktur, di mana tidak ada batas keras pada berapa banyak elemen yang Anda dapat menyisipkan
ke dalamnya karena jika Anda memiliki tabrakan, itu bagus.
Hanya pergi ke depan dan menambahkan ke apa yang kita lihat sedikit lalu adalah
dikenal sebagai linked list.
>> Nah mari kita berhenti untuk sesaat.
Berapa probabilitas tabrakan di tempat pertama?
Benar, mungkin aku lebih berpikir, mungkin Aku di rekayasa masalah ini,
karena Anda tahu apa?
Ya, aku bisa datang dengan sewenang-wenang contoh dari atas kepalaku seperti
Allison dan Harun, tetapi dalam kenyataannya, diberi distribusi seragam
input, yaitu beberapa sisipan acak ke dalam struktur data, apa yang benar-benar
probabilitas tabrakan?
Nah ternyata, itu sebenarnya Super tinggi.
Mari saya menggeneralisasi ini masalah adalah seperti ini.
>> Jadi di ruang n CS50 siswa, apa probabilitas bahwa setidaknya
dua mahasiswa di ruang memiliki ulang tahun yang sama?
Jadi ada apa. sebuah Hund beberapa -
200, 300 orang di sini dan beberapa ratus orang di rumah hari ini.
Jadi jika Anda ingin bertanya kepada diri sendiri apa yang kemungkinan dua orang
di ruangan ini memiliki ulang tahun yang sama, kita bisa mengetahui ini.
Dan saya mengklaim sebenarnya ada dua orang dengan ulang tahun yang sama.
>> Misalnya, apakah ada memiliki ulang tahun hari ini?
Kemarin?
Besok?
Baiklah, jadi rasanya seperti aku akan harus melakukan ini 363 atau jadi lebih
kali untuk benar-benar mengetahui jika kita memiliki tabrakan.
Atau kita hanya bisa melakukan ini secara matematis daripada tediously
melakukan hal ini.
Dan mengusulkan berikut.
>> Jadi saya mengusulkan bahwa kita dapat memodelkan kemungkinan dua orang memiliki
ulang tahun yang sama sebagai probabilitas dari 1 minus probabilitas tidak ada yang memiliki
ulang tahun yang sama.
Jadi untuk mendapatkan ini, dan ini hanya cara mewah menulis ini, untuk
orang pertama di dalam ruangan, ia dapat memiliki satu dari kemungkinan
ulang tahun dengan asumsi 365 hari dalam setahun, dengan permintaan maaf kepada orang-orang dengan
tanggal 29 Februari ulang tahun.
>> Jadi orang pertama di ruangan ini gratis memiliki sejumlah umur
dari 365 kemungkinan sehingga kita akan melakukan itu 365 dibagi dengan 365,
yang merupakan salah satu.
Orang berikutnya dalam ruangan, jika tujuan adalah untuk menghindari tabrakan, hanya dapat
memiliki hari ulang tahunnya pada bagaimana banyak kemungkinan hari yang berbeda?
364.
Jadi istilah kedua dalam ungkapan ini dasarnya melakukan matematika untuk kita
dengan mengurangkan off satu hari mungkin.
Dan kemudian hari berikutnya, hari berikutnya, hari berikutnya ke jumlah
orang di ruangan.
>> Dan jika kita kemudian mempertimbangkan, lalu apa kemungkinan tidak semua orang memiliki
ulang tahun yang unik, tapi sekali lagi dikurangi 1 itu, apa yang kita dapatkan adalah sebuah ekspresi
yang dapat sangat fancifully terlihat seperti ini.
Tapi itu lebih menarik untuk melihat secara visual.
Ini adalah bagan mana pada sumbu-x adalah jumlah orang di ruangan,
jumlah ulang tahun.
Pada sumbu y adalah probabilitas tabrakan, dua orang
memiliki ulang tahun yang sama.
>> Dan takeaway dari kurva ini bahwa segera setelah Anda mendapatkan untuk seperti 40
siswa, kau sudah bangun pada probabilitas 90% combinatorically dua
orang atau lebih memiliki ulang tahun yang sama.
Dan sekali Anda mendapatkan untuk seperti 58 orang itu hampir 100% dari dua kesempatan
orang di ruangan itu akan memiliki ulang tahun yang sama, meskipun ada
365 atau 366 mungkin ember, dan hanya 58 orang di dalam ruangan.
Hanya statistik mungkin Anda mendapatkan tabrakan, yang singkatnya
memotivasi diskusi ini.
Itu bahkan jika kita mendapatkan mewah di sini, dan mulai memiliki rantai ini, kita masih
akan memiliki tabrakan.
>> Sehingga menimbulkan pertanyaan, apa biaya melakukan insersi dan penghapusan
ke dalam struktur data seperti ini?
Yah biarkan aku mengusulkan -
dan biarkan aku kembali ke layar atas sini - jika kita memiliki n elemen dalam
daftar, jadi jika kita mencoba untuk memasukkan n elemen, dan kami memiliki
berapa banyak jumlah ember?
Katakanlah 31 Total ember dalam kasus ulang tahun.
Apa panjang maksimum satu dari rantai ini berpotensi?
>> Jika lagi ada 31 mungkin ulang tahun pada bulan tertentu.
Dan kami hanya penggumpalan orang -
sebenarnya itu adalah contoh bodoh.
Mari kita lakukan 26 sebagai gantinya.
Jadi jika benar-benar memiliki orang yang namanya mulai dengan A sampai Z, sehingga memberikan
kami 26 kemungkinan.
Dan kita sedang menggunakan struktur data seperti yang kita hanya melihat, dimana kita memiliki
sebuah array dari pointer, yang masing-masing menunjuk ke sebuah linked list mana
Daftar pertama adalah orang dengan nama Alice.
Daftar kedua adalah setiap dengan nama dimulai dengan A, mulai
dengan B, dan sebagainya.
>> Apa panjang kemungkinan dari masing-masing daftar tersebut jika kita mengasumsikan bersih bagus
distribusi nama A sampai Z seluruh struktur data keseluruhan?
Ada orang n dalam struktur data dibagi dengan 26, jika mereka baik
tersebar di seluruh struktur data.
Jadi panjang dari masing-masing rantai adalah n dibagi dengan 26.
Namun dalam notasi O besar, apa itu?
Apa yang benar-benar?
Jadi itu benar-benar hanya n, kan?
Karena kita telah mengatakan di masa lalu, bahwa ugh Anda membagi dengan 26.
Ya, pada kenyataannya itu lebih cepat.
Tapi dalam teori, itu tidak mendasar semua yang cepat.
>> Jadi kita tampaknya tidak menjadi semua yang banyak lebih dekat ke grail suci ini.
Bahkan, ini hanya waktu linier.
Heck, pada titik ini, kenapa tidak kita hanya menggunakan satu linked list besar?
Kenapa tidak kita hanya menggunakan satu besar array untuk menyimpan nama-nama
semua orang di ruangan?
Nah, masih ada sesuatu yang menarik tentang tabel hash?
Apakah masih ada sesuatu yang menarik tentang struktur data
yang terlihat seperti ini?
Ini.
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Benar, dan lagi jika itu hanya algoritma waktu linier, dan
waktu linier struktur data, kenapa tidak saya hanya menyimpan nama semua orang di besar
array, atau dalam linked list besar?
Dan berhenti membuat CS begitu jauh lebih sulit selain itu perlu?
Apa yang menarik tentang ini, bahkan meskipun aku menggaruk itu?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Pemasangan tidak?
Mahal lagi.
Jadi sisipan berpotensi masih bisa menjadi waktu yang konstan, bahkan jika data Anda
Struktur seperti ini, array pointer, yang masing-masing menunjuk
berpotensi linked list.
Bagaimana bisa Anda mencapai konstan waktu penyisipan nama?
Tempelkan di depan, kan?
>> Jika kita mengorbankan tujuan desain dari sebelumnya, di mana kami ingin menjaga
nama semua orang, misalnya, diurutkan, atau semua nomor di atas panggung diurutkan,
misalkan kita memiliki disortir linked list.
Itu hanya biaya kami satu atau dua langkah, seperti dalam kasus Ben dan Brian
sebelumnya, untuk memasukkan unsur di awal daftar.
Jadi jika kita tidak peduli tentang menyortir semua dari nama dimulai dengan A atau semua
nama-nama yang diawali huruf B, kita masih bisa mencapai waktu yang konstan penyisipan.
Sekarang mencari Alice atau Bob atau nama apapun lebih umum masih apa?
Ini O besar n dibagi dengan 26, di kasus yang ideal di mana semua orang seragam
didistribusikan, di mana ada banyak A karena ada Z, yang mungkin
realistis.
Tapi itu masih linear.
>> Tapi di sini, kita kembali ke titik notasi asimtotik menjadi
secara teoritis benar.
Tapi di dunia nyata, jika saya menyatakan bahwa program saya dapat melakukan sesuatu 26 kali
lebih cepat dari Anda, yang programnya Anda akan lebih suka menggunakan?
Anda atau saya, yang adalah 26 kali lebih cepat?
Realistis, orang yang adalah 26 kali lebih cepat, bahkan jika secara teoritis
algoritma kami berjalan di sama asymptotic waktu berjalan.
>> Mari saya mengusulkan berbeda solusi sama sekali.
Dan jika ini tidak meniup pikiran Anda, kita keluar dari struktur data.
Jadi ini dia trie -
jenis nama bodoh.
Itu berasal dari retrievals, dan kata dieja trie, t-r-i-e, karena
pengambilan saja terdengar seperti trie.
Tapi itu sejarah dari trie kata.
>> Jadi trie memang beberapa jenis pohon, dan juga bermain pada kata itu.
Dan meskipun Anda tidak bisa melihatnya dengan visualisasi ini, trie adalah
pohon terstruktur, seperti pohon keluarga dengan satu nenek moyang di bagian atas dan banyak
cucu dan cicit seperti daun di bagian bawah.
Tetapi masing-masing node dalam trie adalah array.
Dan dalam sebuah array - dan mari kita menyederhanakan sejenak - itu adalah
array, dalam kasus ini, ukuran 26, di mana setiap node lagi adalah array dari ukuran
26, di mana unsur zeroth dalam array mewakili A, dan terakhir
unsur tiap seperti array mewakili Z.
>> Jadi saya mengusulkan, kemudian, bahwa data ini struktur, yang dikenal sebagai trie, bisa
digunakan juga untuk menyimpan kata-kata.
Kami melihat beberapa saat yang lalu bagaimana kita bisa menyimpan kata-kata, atau dalam hal ini nama kasus, dan kami
lihat sebelumnya bagaimana kita dapat menyimpan nomor, tetapi jika kita fokus pada nama atau string
di sini, perhatikan apa yang menarik.
Saya menyatakan bahwa nama Maxwell adalah dalam struktur data ini.
Di mana Anda melihat Maxwell?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Pada bagian kiri.
Jadi apa yang menarik dengan data ini Struktur ini bukan toko
String M-A-X-W-E-L-L backslash nol, semua contiguously, apa yang Anda lakukan sebagai gantinya
mengikuti.
Jika ini adalah trie seperti struktur data, masing-masing yang node lagi array,
dan Anda ingin menyimpan Maxwell, pertama Indeks dan sebagainya simpul akar, sehingga
untuk berbicara, simpul paling atas, di lokasi M, kanan, sehingga
kira-kira ke tengah.
Dan kemudian dari sana, Anda mengikuti pointer ke node anak, sehingga untuk berbicara.
Jadi dalam arti pohon keluarga, Anda mengikutinya ke bawah.
Dan yang menuntun Anda ke node lain di sebelah kiri ada, yang
hanya array lain.
>> Dan kemudian jika Anda ingin menyimpan Maxwell, Anda menemukan pointer yang mewakili
A, yang merupakan salah satu ini di sini.
Kemudian Anda pergi ke node berikutnya.
Dan perhatikan - ini adalah mengapa gambar itu sedikit menipu -
node ini terlihat super kecil.
Tapi di sebelah kanan ini adalah Y dan Z. Hanya saja penulis telah terpotong
gambar sehingga Anda benar-benar melihat hal-hal.
Jika gambar ini akan menjadi sangat lebar.
Jadi sekarang Anda indeks ke lokasi X, maka W, Lalu E, maka L, kemudian L. Lalu apa
keingintahuan ini?
>> Nah, jika kita menggunakan semacam ini baru mengambil tentang cara menyimpan string dalam
struktur data, Anda masih perlu dasarnya cek dalam data
struktur yang kata berakhir di sini.
Dengan kata lain, masing-masing node ini entah bagaimana harus ingat bahwa kita
benar-benar mengikuti semua petunjuk ini dan meninggalkan sedikit
remah roti di bagian bawah di sini ini Struktur untuk menunjukkan M-A-X-W-E-L-L
memang dalam struktur data.
>> Jadi kita bisa melakukan hal ini sebagai berikut.
Setiap node dalam gambar kita hanya gergaji memiliki satu, array ukuran 27.
Dan sekarang 27, karena dalam hal menetapkan enam, kita benar-benar akan memberikan apostrof,
sehingga kita bisa memiliki nama seperti O'Reilly dan lain-lain dengan apostrof.
Tapi ide yang sama.
Masing-masing elemen dalam Array menunjuk ke struct
node, jadi hanya sebuah simpul.
Jadi ini sangat mengingatkan dari linked list kami.
>> Dan kemudian aku punya Boolean, yang saya akan menyebut kata, yang hanya akan menjadi
benar jika kata berakhir ini node di pohon.
Secara efektif merupakan sedikit segitiga kami melihat beberapa saat yang lalu.
Jadi, jika sebuah kata berakhir pada simpul di pohon, bahwa field kata akan menjadi kenyataan,
yang secara konseptual mengecek, atau kita menggambar segitiga ini, ya ada
adalah kata di sini.
>> Jadi ini adalah trie.
Dan sekarang pertanyaannya adalah, apa yang adalah nya waktu berjalan?
Apakah O besar n?
Apakah itu sesuatu yang lain?
Nah, jika Anda memiliki n nama dalam data ini struktur, Maxwell menjadi salah satu
mereka, apa waktu berjalan memasukkan atau mencari Maxwell?
Apa waktu berjalan memasukkan Maxwell?
Jika ada n nama lain sudah di meja?
Ya?
>> SISWA: [Tak terdengar].
>> SPEAKER 1: Ya, itu panjang dari nama, kan?
Jadi M-a-x-w-e-l-l jadi rasanya seperti ini algoritma adalah O besar tujuh.
Sekarang, tentu saja, nama panjangnya bervariasi.
Mungkin itu nama pendek.
Mungkin itu nama lagi.
Tapi apa kunci di sini adalah bahwa itu nomor konstan.
Dan mungkin tidak benar-benar konstan, tapi Tuhan, jika realistis, dalam
kamus, mungkin ada beberapa batas pada jumlah huruf dalam
nama orang di negara tertentu.
>> Dan jadi kita bisa berasumsi bahwa Nilai adalah konstan.
Aku tidak tahu apa itu.
Ini mungkin lebih besar dari kami pikir itu adalah.
Karena selalu ada beberapa sudut kasus dengan nama yang panjang gila.
Jadi sebut saja k, tapi masih konstan mungkin, karena setiap
nama di dunia, setidaknya dalam negara tertentu, adalah bahwa panjang atau
pendek, jadi konstan.
Tapi ketika kita sudah mengatakan sesuatu yang besar O dari nilai konstan, apa itu
benar-benar setara dengan?
Itu benar-benar hal yang sama mengatakan waktu yang konstan.
>> Sekarang kita semacam kecurangan, kan?
Kami agak memanfaatkan beberapa teori sini untuk mengatakan bahwa baik, urutan k
benar-benar hanya memesan satu, dan itu waktu yang konstan.
Tapi itu benar-benar adalah.
Karena wawasan kunci di sini adalah bahwa jika kita memiliki n nama sudah dalam
struktur data, dan kami memasukkan Maxwell, adalah jumlah waktu yang dibutuhkan kita untuk
masukkan Maxwell sama sekali terpengaruh oleh berapa banyak orang lain
berada dalam struktur data?
Tampaknya tidak menjadi.
Jika saya punya miliar lebih elemen ini trie, dan kemudian memasukkan Maxwell, adalah
ia sama sekali terpengaruh?
Tidak.
Dan itu tidak seperti dari data hari struktur yang telah kita lihat sejauh ini, di mana
waktu berjalan dari algoritma Anda benar independen dari berapa banyak
hal ini atau belum dalam struktur data.
>> Dan dengan ini memberi Anda sekarang adalah kesempatan bagi p set enam, yang akan
lagi melibatkan menerapkan Anda sendiri spell checker, membaca di 150.000
kata-kata, cara terbaik untuk menyimpan bahwa belum tentu jelas.
Dan meskipun aku sudah bercita-cita untuk menemukan grail suci, saya tidak
mengklaim bahwa trie adalah.
Bahkan, tabel hash mungkin sangat baik terbukti jauh lebih efisien.
Tetapi mereka hanya -
itu hanya salah satu keputusan desain Anda akan harus membuat.
>> Namun dalam penutupan mari kita 50 atau lebih detik untuk mengintip apa yang ada di
depan minggu depan dan seterusnya kita transisi dari baris perintah ini
dunia jika program C untuk hal-hal web berbasis dan bahasa seperti PHP dan
JavaScript dan internet itu sendiri, protokol seperti HTTP, yang Anda sudah
diambil untuk diberikan selama bertahun-tahun sekarang, dan diketik paling setiap
hari, mungkin, atau dilihat.
Dan kita akan mulai mengupas lapisan apa internet.
Dan apa kode yang mendasari alat hari ini.
Jadi 50 detik teaser ini di sini.
Aku memberikan Laskar Net.
>> [VIDEO PEMUTARAN]
>> -Dia datang dengan pesan.
Dengan protokol semua sendiri.
Dia datang ke dunia firewall kejam, tidak peduli router, dan bahaya yang jauh
lebih buruk daripada kematian.
Dia cepat.
Dia kuat.
Dia TCPIP.
Dan dia punya alamat Anda.
Warriors of Net.
>> [END VIDEO PEMUTARAN]
>> SPEAKER 1: Itu adalah bagaimana internet akan bekerja pada minggu depan.