>> SPEAKER 1: Baiklah, jadi kita balik.
Selamat datang ke CS50.
Ini adalah hujung minggu tujuh.
Jadi ingat bahawa masa lalu, kami mula melihat yang lebih canggih
struktur data.
Sejak sehingga kini, semua kita telah benar-benar di tangan kita adalah ini, array.
>> Tetapi sebelum kita membuang pelbagai tidak apa yang menarik, yang sememangnya ia
sebenarnya, apa yang adalah sebahagian daripada plus ini data mudah
struktur setakat ini?
Apakah ia baik?
Setakat yang kita lihat?
Apa yang anda dapat?
Tiada apa-apa.
>> PELAJAR: [didengar].
>> SPEAKER 1: Apakah itu?
>> PELAJAR: [didengar].
>> SPEAKER 1 saiz tetap.
OK, jadi mengapa adalah saiz tetap baik walaupun?
>> PELAJAR: [didengar].
>> SPEAKER 1: OK, jadi ia berkesan dalam erti kata bahawa anda boleh memperuntukkan
jumlah tetap ruang, yang diharapkan adalah tepat sebanyak
ruang yang anda mahu.
Jadi yang boleh menjadi benar-benar ditambah.
>> Apa lagi sampingan daripada array?
Ya?
>> PELAJAR: [didengar].
>> SPEAKER 1: Semua - maaf?
>> PELAJAR [didengar].
>> SPEAKER 1: Semua tempat dalam ingatan atau di sebelah satu sama lain.
Dan yang membantu - mengapa?
Itu agak benar.
Tetapi bagaimana kita boleh mengeksploitasi kebenaran itu?
>> PELAJAR: [didengar].
>> SPEAKER 1: Tepat sekali, kita dapat mengesan di mana segala-galanya hanya dengan mengetahui
satu alamat, iaitu alamat bait pertama yang sebahagian memori.
Atau dalam kes tali, alamat yang pertama
char dalam rentetan itu.
Dan dari situ, kita boleh mencari hujung tali.
Kita boleh mencari unsur kedua, Elemen ketiga, dan sebagainya.
>> Dan sebagainya cara mewah untuk menggambarkan bahawa ciri adalah yang memberikan kita array
capaian rawak.
Hanya dengan menggunakan kurungan persegi makluman dan nombor, anda boleh melompat ke
elemen tertentu dalam pelbagai dalam masa yang berterusan, besar O
satu, jadi untuk bercakap.
>> Tetapi ada beberapa kelemahan.
Apa array tidak sangat mudah?
Apakah ia tidak baik pada?
>> PELAJAR: [didengar].
>> SPEAKER 1: Apakah itu?
>> PELAJAR [didengar].
>> SPEAKER 1: Mengembangkan dalam saiz.
Jadi kelemahan pelbagai adalah tepat bertentangan dengan apa yang
upsides berada.
Jadi salah satu kelemahan adalah bahawa ia adalah saiz yang tetap.
Jadi anda tidak boleh benar-benar ia berkembang.
Anda boleh mengagihkan semula sebahagian yang lebih besar ingatan, dan kemudian bergerak unsur-unsur lama
ke array baru.
Dan kemudian bebas pelbagai lama, untuk Contohnya, dengan menggunakan malloc atau serupa
fungsi dipanggil realloc, yang ingatan reallocates.
>> Realloc, sebagai diketepikan, cuba untuk memberikan anda memori yang bersebelahan pelbagai
yang anda sudah mempunyai.
Tetapi ia mungkin perkara-perkara yang bergerak sekitar sama sekali.
Tetapi dalam jangka pendek, itu mahal, kan?
Kerana jika anda mempunyai sebahagian daripada ingatan saiz ini, tetapi anda benar-benar mahu satu
saiz ini, dan anda mahu mengekalkan unsur-unsur asal, anda perlu
kira-kira satu masa proses penyalinan linear yang perlu berlaku dari
pelbagai lama ke baru.
Dan realiti meminta operasi sistem lagi dan lagi dan
lagi untuk ketulan besar memori boleh memulakan kos anda sedikit masa juga.
Jadi ia adalah kedua-dua satu rahmat dan kutuk di menyamar, hakikat bahawa array
mempunyai saiz tetap.
Tetapi jika kita memperkenalkan dan bukannya sesuatu seperti ini, yang kita dipanggil berkaitan
senarai, kita akan mendapat upsides dan beberapa satu kelemahan beberapa di sini juga.
>> Jadi senarai yang dikaitkan hanya satu data struktur terdiri daripada C structs dalam
kes, di mana struct, ingat, hanya bekas untuk satu atau lebih khusus
jenis pembolehubah.
Dalam kes ini, apa yang jenis data kelihatan dalam struct yang
Kali terakhir kita dipanggil nod?
Setiap segi empat tepat adalah nod.
Dan setiap segi empat tepat kecil di dalamnya adalah sejenis data.
Apakah jenis-jenis yang kita katakan mereka pada hari Isnin?
Ya?
>> PELAJAR: [didengar].
>> SPEAKER 1: A berubah dan penunjuk, atau lebih khusus, int, bagi n,
dan penunjuk di bahagian bawah.
Kedua-dua mereka berada 32 bit, pada kurangnya pada komputer seperti ini CS50
Perkakas, dan supaya mereka berada disediakan sama dalam saiz.
>> Jadi apa yang menggunakan penunjuk walaupun untuk nampaknya?
Mengapa menambah arrow ini sekarang apabila array adalah begitu baik dan bersih, dan mudah?
Apakah penunjuk lakukan untuk kita dalam setiap nod ini?
>> PELAJAR: [didengar].
>> SPEAKER 1: Tepat sekali.
Ia memberitahu anda di mana yang seterusnya adalah.
Jadi saya jenis menggunakan analogi menggunakan benang untuk menyusun daripada
thread nod ini bersama-sama.
Dan itulah apa yang kami lakukan dengan petunjuk kerana masing-masing
ketulan memori mungkin atau mungkin tidak berdampingan, kembali ke belakang untuk menyokong
dalam RAM, kerana setiap kali anda memanggil malloc berkata, memberikan saya cukup
bait untuk nod baru, ia mungkin berada di sini atau ia mungkin berada di sini.
Ia mungkin berada di sini.
Anda hanya tidak tahu.
>> Tetapi menggunakan petunjuk di alamat mereka nod, anda boleh menjahit mereka
bersama-sama dengan cara yang kelihatan visual seperti senarai walaupun perkara-perkara ini adalah
semua tersebar di seluruh satu atau anda dua atau empat gigabait anda RAM
di dalam komputer anda sendiri.
>> Jadi keburukan, maka, daripada senarai yang dikaitkan adalah apa?
Apakah harga yang kami nampaknya membayar?
>> PELAJAR: [didengar].
>> SPEAKER 1: Lebih banyak ruang, bukan?
Kami telah, dalam kes ini, dua kali ganda jumlah ruang kerana kita telah pergi
daripada 32 bit untuk setiap nod, bagi setiap int, jadi sekarang 64 bit sebab kita perlu
menyimpan sekitar penunjuk juga.
Anda mendapatkan kecekapan yang lebih jika anda struct adalah lebih besar daripada perkara ini mudah.
Jika anda benar-benar mempunyai pelajar di dalam yang merupakan beberapa rentetan untuk
nama dan rumah, mungkin nombor ID, mungkin beberapa bidang lain sama sekali.
>> Jadi, jika anda mempunyai struct cukup besar, maka mungkin kos penunjuk adalah
tidak apa-apa masalah besar.
Ini adalah sedikit kes sudut dalam yang kita menyimpan apa-apa yang mudah primitif
dalam senarai berkaitan.
Tetapi persoalannya adalah sama.
Sedang anda pasti berbelanja lebih memori, tetapi anda mendapat
fleksibiliti.
Kerana sekarang jika saya ingin menambah satu elemen pada awal senarai ini,
Saya perlu memperuntukkan nod baru.
Dan saya hanya perlu mengemas kini panah entah bagaimana dengan hanya bergerak
beberapa petunjuk sekitar.
>> Jika saya ingin memasukkan sesuatu ke dalam tengah-tengah senarai, saya tidak perlu
menolak semua orang selain seperti yang kita lakukan pada lepas minggu dengan sukarelawan kita yang
diwakili array.
Saya hanya boleh memperuntukkan nod baru dan kemudian hanya menunjukkan anak panah dalam
arah yang berbeza kerana ia tidak perlu kekal dalam sebenar
memori talian benar seperti saya telah disediakan di sini pada skrin.
>> Kemudian akhir sekali, jika anda mahu untuk memasukkan sesuatu yang pada akhir senarai, ia
lebih mudah.
Ini adalah sejenis notasi sewenang-wenangnya, tetapi penunjuk 34 ini, mengambil tekaan.
Apakah nilai penunjuk yang paling apapun yang mungkin dilukis seperti lama
antena sekolah di sana?
>> PELAJAR: [didengar].
>> SPEAKER 1: Ia mungkin null.
Dan sesungguhnya yang merupakan salah satu pengarang perwakilan null.
Dan ia batal kerana anda benar-benar perlu tahu di mana hujung berkaitan
senarai adalah, supaya anda menyimpan berikut dan mengikuti dan mengikuti anak panah
untuk beberapa nilai sampah.
Jadi null akan menandakan bahawa tidak ada lebih nod di sebelah kanan nombor 34,
dalam kes ini.
>> Jadi kita mencadangkan supaya kita boleh melaksanakan nod ini dalam kod.
Dan kita telah melihat ini jenis sintaks sebelum ini.
Typedef hanya mentakrifkan jenis baru untuk kita, memberikan kita sinonim seperti
tali adalah untuk char *.
Dalam kes ini, ia akan memberi kita notasi trengkas supaya nod struct
boleh bukan hanya ditulis sebagai nod, yang lebih bersih banyak.
Ia banyak kurang lantung.
>> Di dalam nod nampaknya int dipanggil n, dan kemudian nod struct *
yang bermaksud apa yang kita mahu anak panah untuk bermakna, penunjuk yang lain
nod yang tepat jenis data yang sama.
Dan saya mencadangkan supaya kita boleh melaksanakan fungsi carian seperti ini, yang pada
pandangan pertama mungkin kelihatan kompleks sedikit.
Tetapi mari kita lihat dalam konteks.
>> Biar saya pergi ke perkakas di sini.
Izinkan saya membuka fail yang dipanggil senarai sifar dot h.
Dan itu hanya mengandungi definisi yang kita hanya melihat masa lalu untuk data ini
Jenis dipanggil nod.
Jadi kami telah meletakkan ke dalam titik h fail.
>> Dan sebagai diketepikan, walaupun ini program yang anda kira-kira untuk melihat adalah
tidak semua kompleks itu, ia memang konvensyen semasa menulis program untuk
meletakkan perkara-perkara seperti jenis data, untuk menarik pemalar kadang-kadang, di dalam anda
file kepala dan tidak semestinya dalam file C anda, sudah tentu apabila anda
program mendapatkan yang lebih besar dan lebih besar, supaya anda tahu di mana untuk melihat kedua-dua
dokumentasi dalam kes-kes tertentu, atau untuk asas-asas seperti ini,
definisi jenis tertentu.
>> Jika saya kini membuka senarai sifar dot c, perhatikan beberapa perkara.
Ia termasuk beberapa fail header, kebanyakan yang kita lihat sebelum ini.
Ia termasuk fail header sendiri.
>> Dan sebagai diketepikan, mengapa itu dua sebut di sini, berbanding dengan sudut
kurungan pada baris yang Saya menekankan di sana?
>> PELAJAR: [didengar].
>> SPEAKER 1: Ya, jadi ini adalah fail tempatan.
Jadi, jika ia adalah fail tempatan anda sendiri di sini on line 15, misalnya, anda menggunakan
petikan berganda bukannya daripada kurungan sudut.
>> Sekarang ini adalah jenis yang menarik.
Perhatikan bahawa saya telah mengisytiharkan global berubah-ubah dalam program ini on line 18
dipanggil pertama, idea itu ini akan menjadi penunjuk kepada yang pertama
nod dalam senarai berkaitan saya, dan saya dimulakan untuk menyeimbangkan, kerana saya telah
tidak diperuntukkan mana-mana sebenar nod hanya lagi.
>> Jadi ini merupakan, bergambar, apa yang kita melihat masa lalu di gambar sebagai
bahawa penunjuk di hujung bahagian kiri.
Jadi sekarang, penunjuk yang tidak mempunyai anak panah.
Ia bukan hanya null.
Tetapi ia mewakili apa yang akan menjadi alamat pertama yang sebenarnya
nod dalam senarai ini.
Jadi saya telah dilaksanakan ia adalah global kerana, seperti yang anda akan lihat, semua ini
program tidak dalam hidup adalah melaksanakan senarai dikaitkan bagi saya.
>> Sekarang saya telah mendapat beberapa prototaip sini.
Saya membuat keputusan untuk melaksanakan ciri-ciri seperti penghapusan, memasukkan, mencari, dan
traversal -
lalu hanya menjadi berjalan di seluruh senarai, mencetak unsur-unsur.
Dan kini di sini adalah rutin utama saya.
Dan kita tidak akan menghabiskan terlalu banyak masa pada ini kerana ini adalah jenis, mudah-mudahan
topi lama oleh sekarang.
>> Saya akan melakukan yang berikut, sementara pengguna bekerjasama.
Jadi, satu, saya akan mencetak daripada menu ini.
Dan saya telah diformat sebagai bersih seperti yang saya boleh.
Jika jenis pengguna dalam satu, ini bermakna mereka mahu memadam sesuatu.
Jika jenis pengguna dalam dua, yang bermakna mereka mahu untuk memasukkan sesuatu.
Dan sebagainya.
Saya akan kemudian meminta maka untuk perintah.
Dan kemudian saya akan menggunakan GetInt.
>> Jadi ini adalah benar-benar mudah menuing muka di mana anda hanya perlu menaip
pemetaan nombor untuk satu mereka arahan.
Dan kini saya mempunyai suis yang bersih baik kenyataan yang akan menghidupkan
apa pengguna ditaip masuk
Dan jika mereka ditaip satu demi satu, saya akan memanggil memadam dan pecah.
Jika mereka ditaip dua, saya akan memanggil memasukkan dan pecah.
>> Dan kini notis saya telah setiap ini di barisan yang sama.
Ini adalah satu keputusan yang gaya.
Biasanya kita telah melihat sesuatu seperti ini.
Tetapi saya hanya membuat keputusan, terus-terang, program saya kelihatan lebih mudah dibaca kerana
ia adalah hanya empat kes untuk hanya senarai ia seperti ini.
Penggunaan sepenuhnya sah gaya.
Dan saya akan melakukan ini selagi pengguna tidak ditaip sifar, yang saya
memutuskan akan bermakna mereka mahu berhenti.
>> Jadi sekarang melihat apa yang saya akan dilakukan di sini.
Saya akan membebaskan senarai nampaknya.
Tetapi lebih kepada yang dalam hanya seketika.
Mari kita mula-mula menjalankan program ini.
Jadi biarlah saya membuat terminal yang lebih besar tingkap, dot slash senarai 0.
Saya akan pergi ke hadapan dan memasukkan oleh menaip dua, beberapa seperti 50, dan kini
anda akan melihat senarai kini 50.
Dan teks saya hanya menatal sedikit.
Jadi sekarang melihat senarai mengandungi nombor 50.
>> Mari kita buat memasukkan satu lagi dengan mengambil dua.
Mari menaip nombor seperti satu.
Senarai kini merupakan salah satu, diikuti oleh 50.
Jadi ini adalah hanya perwakilan teks senarai.
Dan mari kita memasukkan nombor satu lebih seperti nombor 42, yang diharapkan
akan berakhir di tengah-tengah, kerana program ini dalam pelbagai tertentu ia
unsur-unsur kerana ia memasukkan mereka.
Jadi kita ada.
Program Super mudah yang boleh benar-benar telah menggunakan pelbagai, tetapi saya
berlaku untuk menggunakan senarai yang berkaitan hanya jadi saya boleh dinamik
berkembang dan mengecut ia.
>> Jadi mari kita lihat carian, jika saya menjalankan arahan tiga, saya mahu mencari
untuk, katakan, nombor 43.
Dan tiada apa yang nampaknya dijumpai, kerana saya pulang tiada jawapan.
Jadi mari kita buat ini lagi.
Mencari.
Mari kita cari 50, atau lebih tepat mencari 42, yang mempunyai yang bagus
makna halus sedikit.
Dan saya dapati makna kehidupan di sana.
Bilangan 42, jika anda tidak tahu rujukan, Google ia.
Baiklah.
Jadi apa yang program ini dilakukan untuk saya?
Ia hanya membenarkan saya untuk memasukkan itu jauh dan mencari unsur-unsur.
>> Mari kita cepat ke hadapan, kemudian, untuk bahawa fungsi kita memandang pada
pada hari Isnin sebagai memujuknya.
Jadi fungsi ini, saya menuntut, mencari satu elemen dalam senarai dengan terlebih dahulu
satu, menyebabkan pengguna dan kemudian memanggil GetInt untuk mendapatkan int sebenar
yang anda mahu mencari.
>> Kemudian notis ini.
Saya akan membuat ubah sementara sejajar 188 dipanggil penunjuk -
PTR -
boleh memanggilnya apa-apa.
Dan ia adalah penunjuk kepada nod kerana saya berkata nod * sana.
Dan saya Memulakan ia menjadi sama dengan terlebih dahulu supaya saya berkesan mempunyai saya
jari, jadi untuk bercakap, di sangat Elemen pertama dalam senarai itu.
Jadi, jika tangan kanan saya di sini adalah PTR Saya menghala ke arah perkara yang sama yang pertama
yang menghala ke arah.
>> Jadi kini kembali kod, apa yang berlaku seterusnya -
ini adalah paradigma biasa apabila iterating atas struktur seperti
senarai berkaitan.
Saya akan melakukan perkara berikut semasa penunjuk tidak sama untuk menyeimbangkan itu, sambil
jari saya tidak menghala ke arah beberapa null nilai, jika penunjuk arrow n sama n.
Kami akan notis pertama yang n adalah apa yang pengguna ditaip dalam setiap GetInts hubungi di sini.
>> Dan penunjuk arrow n bermaksud apa?
Baik jika kita kembali kepada gambar di sini, jika saya mempunyai jari menghala ke arah
nod yang pertama yang mengandungi sembilan, yang arrow asasnya bermakna pergi ke bahawa
nod dan merebut nilai di lokasi n, dalam hal ini, medan data yang dipanggil n.
>> Sebagai mengetepikan - dan kita melihat ini pasangan minggu lalu apabila seseorang bertanya -
sintaks ini adalah baru, tetapi ia tidak memberi kita kuasa yang kita
tidak sudah mempunyai.
Apakah ungkapan ini bersamaan dengan menggunakan dot makluman dan bintang pasangan
minggu lalu apabila kita dikupas kembali lapisan ini agak terlalu awal?
>> PELAJAR: [didengar].
>> SPEAKER 1: Tepat sekali, ia adalah bintang, dan maka ia adalah bintang dot n, dengan
kurungan di sini, yang kelihatan, terus-terang, saya berfikir banyak
lebih samar untuk dibaca.
Tetapi penunjuk bintang, seperti biasa, cara pergi ke sana.
Dan apabila anda berada di sana, apa yang data bidang yang anda mahu untuk mengakses?
Baik anda menggunakan notasi dot untuk mengakses medan data structs, dan saya
khusus mahu n.
>> Terus terang, saya akan berhujah ini hanya sukar untuk dibaca.
Ia adalah sukar untuk ingat di mana jangan kurungan pergi,
bintang dan semua itu.
Jadi dunia telah menerima pakai beberapa sintaktik gula, jadi untuk bercakap.
Hanya satu cara seksi berkata, ini adalah setaraf, dan
mungkin lebih intuitif.
Jika penunjuk merupakan penunjuk, yang arrow notasi cara pergi ke sana dan mendapati
bidang dalam kes ini dipanggil n.
>> Jadi jika saya merasa, melihat apa yang saya lakukan.
Saya hanya mencetak, saya mendapati peratus i, memasang dalam nilai untuk int itu.
Saya menyeru tidur untuk kedua hanya untuk jenis perkara yang berhenti pada skrin untuk
memberi pengguna kedua untuk menyerap apa sahaja yang berlaku.
Dan kemudian saya memecahkan.
Jika tidak, apa yang saya lakukan?
Saya kini penunjuk kepada sama penunjuk arrow depan.
>> Jadi hanya perlu jelas, ini bermakna pergi ada, dengan menggunakan notasi lama sekolah saya.
Jadi ini hanya bermaksud untuk pergi ke apa-apa anda menghala ke arah, yang sangat
Kes pertama adalah saya menghala ke arah struct dengan sembilan di dalamnya.
Jadi saya telah pergi ke sana.
Dan kemudian notasi dot bermakna, mendapat nilai di depan.
>> Tetapi nilai itu, walaupun ia telah disediakan sebagai sempit, hanya nombor.
Ia adalah satu alamat angka.
Jadi garis ini satu kod, sama ada ditulis begini, lebih samar
cara, atau seperti ini, lebih sedikit cara intuitif, hanya bermaksud menggerakkan tangan saya
dari nod pertama yang akan datang, dan kemudian yang seterusnya, dan kemudian
datang satu, dan sebagainya.
>> Oleh itu, kita tidak akan kekal di pihak yang lain perlaksanaan memasukkan dan memadam
dan traversal, kedua-dua pertama yang terlibat secara adil.
Dan saya fikir ia agak mudah untuk mendapatkan hilang apabila melakukannya secara lisan.
Tetapi apa yang kita boleh lakukan di sini adalah cuba untuk menentukan bagaimana
terbaik untuk melakukan ini secara visual.
Kerana saya akan mencadangkan bahawa jika kita mahu memasukkan unsur-unsur ini ke dalam
senarai yang sedia ada, yang mempunyai lima unsur -
9, 17, 22, 26, dan 33 -
jika saya telah pergi untuk melaksanakan ini dalam kod, saya perlu memikirkan bagaimana untuk pergi
melakukan ini.
>> Dan saya akan mencadangkan mengambil langkah-langkah bayi di mana, dalam kes ini saya maksudkan, apakah
senario yang mungkin kita mungkin menghadapi secara umum?
Apabila melaksanakan memasukkan untuk berkaitan senarai, ini hanya berlaku untuk menjadi
contoh khusus saiz lima.
Baik jika anda ingin memasukkan nombor, suka mengatakan nombor satu, dan
mengekalkan perintah disusun, di mana jelas tidak nombor satu perlu
pergi dalam contoh ini tertentu?
Seperti pada permulaan.
>> Tetapi apa yang menarik ada yang jika anda mahu untuk memasukkan satu ke dalam ini
senarai, apa penunjuk khas perlu perlu dikemaskini nampaknya?
Pertama.
Jadi, saya akan berhujah, ini adalah kes pertama bahawa kita mungkin mahu mempertimbangkan, satu
senario yang melibatkan memasukkan di permulaan senarai.
>> Mari kita memetik bulir mungkin satu yang mudah atau kes lebih mudah, secara relatif.
Katakan saya mahu memasukkan nombor 35 untuk disusun.
Ia jelas tergolong di sana.
Jadi apa penunjuk jelas akan perlu dikemaskini dalam senario itu?
34 penunjuk ini tidak menjadi batal tetapi alamat struct itu
yang mengandungi nombor 35.
Itulah kes dua.
Jadi sudah, saya jenis quantizing berapa banyak kerja yang saya lakukan di sini.
>> Dan akhirnya, kes tengah jelas adalah sesungguhnya, di tengah-tengah, jika saya mahu
memasukkan sesuatu seperti berkata 23, yang pergi antara 23 dan 26, tetapi
kini perkara-perkara mendapatkan lebih sedikit yang terlibat kerana apa yang
petunjuk perlu berubah?
Jadi 22 jelas perlu berubah kerana dia tidak boleh menunjukkan kepada 26 lagi.
Dia perlu menunjukkan nod baru yang Saya akan mempunyai untuk memperuntukkan dengan menghubungi
malloc atau setaraf beberapa.
>> Tetapi saya juga perlu bahawa nod baru, 23 dalam kes ini, mempunyai penunjuk yang
menghala ke arah siapa?
26.
Dan ada akan menjadi satu perintah operasi di sini.
Kerana jika saya lakukan ini bodoh, dan saya untuk permulaan contoh pada awal
senarai, dan matlamat saya adalah untuk memasukkan 23.
Dan saya lihat, adakah ia tergolong di sini, berhampiran sembilan?
No
Adakah ia tergolong di sini, bersebelahan dengan 17?
No
Adakah ia tergolong di sini bersebelahan dengan 22?
Ya.
>> Sekarang, jika saya bodoh di sini, dan tidak berfikir ini melalui, saya mungkin
memperuntukkan nod baru saya untuk 23.
Saya mungkin mengemas kini penunjuk dari nod yang dipanggil 22, menunjuk
ia pada nod baru.
Dan kemudian apa yang saya perlu mengemaskini penunjuk nod baru boleh?
>> PELAJAR: [didengar].
>> SPEAKER 1: Tepat sekali.
Menghala ke arah 26.
Tetapi keparat jika saya tidak mengemas kini sudah 22 penunjuk untuk menunjukkan pada lelaki ini, dan
kini saya mempunyai anak-anak yatim, yang lain senarai, jadi untuk bercakap.
Jadi perintah operasi di sini akan menjadi penting.
>> Untuk melakukan ini saya boleh mencuri, berkata, enam sukarelawan.
Dan mari kita lihat jika kita tidak boleh melakukan ini visual dan bukannya kod yang bijak.
Dan kita mempunyai beberapa tekanan yang indah bola untuk anda hari ini.
OK, bagaimana kira-kira satu, dua, dalam kembali - di hujung sana.
tiga, empat, kedua-dua anda lelaki di akhir.
Dan lima, enam.
Pasti.
Lima dan enam.
Semua hak dan kami akan datang kepada anda semua masa akan datang.
Baiklah, datang ke atas.
>> Baiklah, kerana anda di sini pertama, anda ingin menjadi salah satu canggung
in Google Kaca di sini?
Baiklah, jadi, OK, Kaca, merakam video.
OK, anda baik untuk pergi.
>> Baiklah, jadi jika anda semua boleh datang di sini, saya telah disediakan terlebih dahulu
beberapa nombor.
Baiklah, datang di sini.
Dan mengapa tidak anda pergi sedikit lagi cara itu.
Dan mari kita lihat, apa nama, dengan Kaca Google?
>> PELAJAR: Ben.
>> SPEAKER 1: Ben?
OK, Ben, anda akan menjadi yang pertama, secara literal.
Jadi, kita akan menghantar anda hingga akhir pentas.
Baiklah, dan nama anda?
>> PELAJAR: Jason.
>> SPEAKER 1: Jason, OK anda akan menjadi nombor sembilan.
Jadi, jika anda ingin mengikuti Ben cara itu.
>> PELAJAR: Jill.
>> SPEAKER 1: Jill anda akan menjadi 17, yang jika saya melakukan ini lebih
bijak, saya akan bermula pada hujung yang lain.
Anda pergi cara itu.
22.
Dan anda?
>> PELAJAR: Mary.
>> SPEAKER 1: Mary, anda akan 22.
Dan nama anda?
>> PELAJAR: Chris.
>> SPEAKER 1: Chris, anda akan 26.
Dan kemudian akhirnya.
>> PELAJAR: Diana.
>> SPEAKER 1: Diana, anda akan 34.
Jadi anda datang ke sini.
>> Baiklah, jadi sempurna disusun memerintahkan sudah.
Dan mari kita pergi ke hadapan dan melakukan ini supaya kita dapat benar-benar -
Ben anda hanya jenis mencari keluar ke mana-mana tempat di sana.
OK, jadi mari kita pergi ke hadapan dan menggambarkan ini menggunakan senjata, sama seperti saya adalah, sebenarnya,
apa yang berlaku.
Oleh itu, pergilah ke hadapan dan memberi diri yang kaki atau dua di antara kamu.
Dan pergi ke hadapan dan menunjukkan dengan satu tangan untuk sesiapa yang anda perlu menghala ke arah
berdasarkan ini.
Dan jika anda hanya menunjukkan null lurus ke bawah ke lantai.
OK, jadi yang baik.
>> Jadi sekarang kita mempunyai senarai yang berkaitan, dan biarlah saya mencadangkan bahawa saya akan memainkan peranan
PTR, jadi saya tidak akan mengganggu menjalankan ini sekitar.
Dan kemudian - konvensyen bodoh seseorang - anda boleh memanggil apa-apa ini yang anda mahu -
penunjuk sebelumnya, penunjuk Pred -
ia hanya nama samaran kami mengalah contoh kod untuk tangan kiri saya.
Sebaliknya yang akan menjaga menjejaki yang yang di
berikutan senario.
>> Jadi rasa, pertama, saya ingin memetik bulir bahawa contoh pertama memasukkan, berkata
20, ke dalam senarai.
Jadi saya akan memerlukan seseorang untuk merangkumi nombor 20 untuk kita.
Jadi saya perlu malloc seseorang daripada penonton.
Ayuh up.
Apa nama anda?
>> PELAJAR: Brian.
>> SPEAKER 1: Brian, semua betul, jadi anda hendaklah nod yang mengandungi 20.
Baiklah, datang di sini.
Dan jelas, di mana adakah Brian tergolong?
Jadi, di tengah-tengah - sebenarnya, tunggu satu minit.
Kami melakukan ini daripada perintah.
Kami membuat ini jauh lebih sukar daripada ia perlu pada mulanya.
OK, kita akan bebas Brian dan realloc Brian sebagai lima.
>> OK, jadi sekarang kita mahu memasukkan Brian sebagai lima.
Jadi datang ke sini di sebelah Ben hanya seketika.
Dan anda mungkin boleh memberitahu di mana cerita ini berterusan.
Tetapi mari kita berfikir dengan teliti tentang perintah operasi.
Dan ia adalah tepat ini visual itu akan beratur
dengan kod sampel.
Jadi di sini saya telah PTR menunjuk pada mulanya tidak pada Ben, per se, tetapi pada apa sahaja
menghargai dia mengandungi, yang dalam kes ini adalah - apa nama anda lagi?
>> PELAJAR: Jason.
>> SPEAKER 1: Jason, supaya kedua-dua Ben dan saya menghala ke arah Jason pada masa ini.
Jadi sekarang saya perlu ditentukan, di mana tidak Brian tergolong?
Jadi satu-satunya perkara saya mempunyai akses kepada sekarang adalah perkara data n beliau.
Jadi saya akan menyemak, adalah Brian kurang daripada Jason?
Jawapannya adalah benar.
>> Jadi apa yang kini perlu berlaku, dalam susunan yang betul?
Saya perlu mengemaskinikan berapa banyak petunjuk dalam jumlah di dalam cerita ini?
Di mana tangan saya masih menghala ke arah Jason, dan tangan anda - jika anda mahu
meletakkan tangan anda seperti, jenis, saya tidak tahu, tanda tanya.
OK, baik.
>> Baiklah, jadi anda perlu calon-calon ini.
Sama ada Ben atau saya atau Brian atau Jason atau orang lain, yang
petunjuk perlu berubah?
Berapa ramai dalam jumlah?
>> OK, jadi dua.
Penunjuk saya tidak benar-benar perkara lagi kerana saya hanya sementara.
Jadi ia adalah kedua-dua lelaki itu, mungkin, kedua-dua Ben dan Brian.
Jadi biarlah saya mencadangkan supaya kita kini Ben, kerana dia pertama.
Elemen pertama dalam senarai ini kini akan menjadi Brian.
Jadi Ben titik di Brian.
OK, sekarang apa?
>> Yang mendapat menunjuk ke arah siapa?
>> PELAJAR: [didengar].
>> SPEAKER 1: OK jadi Brian mempunyai ke titik di Jason.
Tetapi saya hilang mengesan penunjuk itu?
Saya tahu di mana Jason?
>> PELAJAR: [didengar].
>> SPEAKER 1: saya lakukan, kerana saya penunjuk sementara.
Dan mungkin, saya tidak berubah untuk menunjukkan pada nod baru.
Oleh itu, kita hanya boleh mempunyai titik Brian pada sesiapa yang saya menghala ke arah.
Dan kita selesai.
Jadi mana-mana satu, kemasukan di awal senarai.
Terdapat dua langkah utama.
Pertama, kita perlu mengemaskini Ben, dan kemudian kita juga perlu mengemaskini Brian.
Dan maka saya tidak perlu bersusah payah traipsing melalui seluruh
senarai, kerana kita sudah menemui beliau lokasi, kerana dia milik
meninggalkan unsur yang pertama.
>> Baiklah, jadi agak mudah.
Malah, rasanya kita sudah hampir membuat ini terlalu rumit.
Jadi mari kita kini memetik off akhir senarai, dan melihat di mana
kerumitan bermula.
Jadi, jika kini, saya alloc dari penonton.
Sesiapa yang mahu bermain 55?
Baiklah, saya melihat tangan pertama.
Ayuh up.
Yeah.
Apa nama anda?
>> PELAJAR: [didengar].
>> SPEAKER 1 Habata.
OK, datang ke atas.
Anda akan menjadi nombor 55.
Jadi anda, sudah tentu, kepunyaan pada akhir senarai.
Jadi mari kita memainkan simulasi dengan saya menjadi PTR untuk seketika.
Jadi, saya mula-mula pergi ke titik di apa Ben yang menghala ke arah.
Kami kedua-dua menunjuk di Brian.
Jadi 55 tidak kurang daripada lima.
Jadi, saya akan mengemas kini diri dengan menunjuk kepada penunjuk seterusnya Brian, yang
kini sudah tentu Jason.
55 tidak kurang daripada sembilan, jadi Saya akan mengemas kini PTR.
Saya akan mengemas kini PTR Saya akan mengemaskini PTR.
Dan saya akan - hmm, apa nama anda lagi?
>> PELAJAR: Diana.
>> SPEAKER 1: Diana menunjukkan, sudah tentu, di batal dengan tangan kirinya.
Oleh itu, bagaimana sebenarnya Habata tergolong dengan jelas?
Di sebelah kiri, di sini.
Jadi bagaimana saya tahu untuk meletakkan beliau sini Saya rasa saya telah kacau sehingga.
Kerana apa yang PTR seni masa ini dalam masa?
Menyeimbangkan.
Jadi, walaupun, visual, kita boleh jelas melihat semua ini
lelaki di sini di atas pentas.
Saya tidak disimpan mengesan sebelumnya orang di dalam senarai.
Saya tidak mempunyai jari menunjuk keluar, dalam kes ini, bilangan nod 34.
>> Jadi mari kita benar-benar bermula lebih ini.
Jadi sekarang saya sebenarnya perlu pembolehubah tempatan kedua.
Dan ini adalah apa yang anda akan lihat di sebenar sampel kod C, di mana seperti yang saya pergi,
apabila saya mengemaskini tangan kanan saya untuk menunjukkan Jason, dengan itu meninggalkan Brian belakang, saya
lebih baik mula menggunakan tangan kiri saya untuk mengemas kini mana saya berada, supaya apabila saya pergi
melalui senarai ini -
lebih canggung daripada saya bertujuan sekarang di sini visual -
Saya akan mendapatkan kepada akhir senarai.
>> Tangan ini masih sah, yang cukup tidak berguna, selain daripada untuk menunjukkan
Saya dengan jelas pada akhir senarai, tetapi kini sekurang-kurangnya saya mempunyai ini
penunjuk sebelumnya menunjuk di sini, jadi kini apa yang tangan dan apa yang perlu petunjuk
akan dikemas kini?
Yang tangan yang anda mahu untuk menyusun semula pertama?
>> PELAJAR: [didengar].
>> SPEAKER 1: OK, jadi ini Diana.
Di manakah anda mahu menunjukkan Penunjuk kiri Diana di?
Pada 55, mungkin, supaya kami telah dimasukkan di sana.
Dan di mana 55 penunjuk harus pergi?
Down, mewakili null.
Dan tangan saya, pada masa ini, tidak masalah kerana mereka hanya
pembolehubah sementara.
Jadi sekarang kita sedang dilakukan.
>> Jadi kerumitan tambahan yang ada - dan ia tidak begitu sukar untuk melaksanakan,
tetapi kita perlu berubah-ubah menengah untuk membuat memastikan bahawa sebelum saya bergerak kanan saya
tangan, saya mengemaskini nilai kiri saya Sebaliknya, penunjuk Pred dalam kes ini, jadi
bahawa saya mempunyai penunjuk ketinggalan untuk menjejaki di mana saya berada.
Sekarang sebagai diketepikan, jika anda berfikir ini melalui, ini berasa seperti ia adalah
sedikit menjengkelkan perlu menyimpan mengesan tangan kiri ini.
>> Apa yang akan penyelesaian lain kepada masalah ini berlaku?
Jika anda mendapat untuk mereka bentuk semula data struktur kita berbicara
melalui sekarang?
Jika jenis ini hanya daripada merasakan sedikit menjengkelkan untuk mempunyai, suka, dua petunjuk
melalui senarai itu, siapa lagi yang boleh telah, dalam dunia yang ideal, dikekalkan
maklumat yang kita perlukan?
Ya?
>> PELAJAR: [didengar].
>> SPEAKER 1: Tepat sekali.
Betul supaya ada sebenarnya yang menarik kuman idea.
Dan idea ini penunjuk sebelumnya, menghala ke arah elemen sebelumnya.
Bagaimana jika saya hanya termaktub bahawa di dalam senarai itu sendiri?
Dan ia akan menjadi sukar untuk menggambarkan ini tanpa semua kertas
jatuh ke lantai.
Tetapi menganggap bahawa lelaki yang digunakan kedua-dua tangan mereka mempunyai sebelumnya
penunjuk, dan penunjuk akan datang, sekali gus melaksanakan apa yang kita akan memanggil duanya adalah terpakai
senarai berkaitan.
Yang akan membolehkan saya untuk menyusun daripada memutar balik, lebih mudah tanpa saya,
programmer, perlu menyimpan menjejaki secara manual -
benar-benar secara manual -
di mana saya telah sebelum ini dalam senarai.
Jadi kita tidak akan berbuat demikian.
Kami akan memastikan ia mudah kerana itulah akan datang pada harga, dua kali ganda
banyak ruang untuk petunjuk, jika anda mahu yang kedua.
Tetapi itulah sesungguhnya yang sama struktur data yang dikenali sebagai
senarai duanya adalah terpakai dikaitkan.
>> Mari kita buat contoh terakhir di sini dan meletakkan lelaki ini keluar daripada kesengsaraan mereka.
Jadi malloc 20.
Ayuh dari lorong di sana.
Baiklah, apa nama anda?
>> PELAJAR: [didengar].
>> SPEAKER 1: Maaf?
>> PELAJAR: [didengar].
>> SPEAKER 1 Demeron?
OK datang di atas.
Anda hendaklah 20.
Anda jelas akan tergolong di antara 17 dan 22.
Jadi biarlah saya belajar pelajaran saya.
Saya akan memulakan penunjuk menghala ke arah Brian.
Dan saya akan mempunyai tangan kiri saya hanya mengemaskini kepada Brian kerana saya berpindah ke
Jason, pemeriksaan tidak 20 kurang daripada sembilan?
No
Ialah 20 kurang daripada 17?
No
Ialah 20 kurang daripada 22?
Ya.
Jadi apa petunjuk atau tangan perlu menukar di mana mereka menunjuk sekarang?
>> Oleh itu, kita boleh melakukan 17 menghala ke arah 20.
Jadi itulah denda.
Jika kita mahu untuk menunjukkan penunjuk anda sekarang?
Pada 22.
Dan kita tahu di mana 22 adalah, sekali lagi terima kasih untuk penunjuk sementara saya.
Jadi kita OK di sana.
Jadi kerana penyimpanan sementara ini Saya telah disimpan mengesan di mana semua orang.
Dan sekarang anda visual boleh pergi ke mana anda tergolong, dan kini kita perlu 1, 2, 3,
4, 5, 6, 7, 8, 9 bola tekanan, dan pusingan tepukan untuk
lelaki ini, jika kita boleh.
Baik dilakukan.
>> [Tepuk tangan]
>> SPEAKER 1: Baiklah.
Dan anda boleh menyimpan keping kertas sebagai tanda mata.
>> Baiklah, jadi, amanah saya ia banyak lebih mudah untuk berjalan melalui dengan
manusia daripada ia adalah dengan kod sebenar.
Tetapi apa yang anda akan dapati di seketika kini, adalah yang sama - oh, terima kasih.
Terima kasih -
adalah bahawa anda akan mendapati bahawa data yang sama struktur, senarai yang berkaitan, boleh sebenarnya
digunakan sebagai blok bangunan untuk lebih struktur data yang canggih.
>> Dan menyedari terlalu tema di sini ialah kita telah benar-benar memperkenalkan lebih
kerumitan dalam pelaksanaan algoritma ini.
Kemasukan, dan jika kita pergi melaluinya, penghapusan dan mencari, adalah sedikit
lebih rumit daripada ia adalah dengan array.
Tetapi kita mendapat beberapa dinamik.
Kami mendapat satu struktur data penyesuaian.
>> Tetapi sekali lagi, kita membayar harga yang mempunyai beberapa kerumitan tambahan, dalam kedua-dua
melaksanakannya.
Dan kita berputus asa akses rawak.
Dan untuk bersikap jujur, tidak ada beberapa nice membersihkan slaid saya boleh memberi anda bahawa
mengatakan di sini ialah mengapa senarai dikaitkan adalah lebih baik daripada array.
Dan tinggalkan ia pada itu.
Kerana tema yang sering muncul sekarang, walaupun lebih-lebih lagi pada minggu-minggu akan datang, adalah
bahawa tidak semestinya jawapan yang betul.
>> Inilah sebabnya mengapa kita mempunyai paksi yang berasingan reka bentuk untuk set masalah.
Ia akan menjadi sangat peka konteks sama ada anda mahu menggunakan data ini
struktur atau yang satu, dan ia akan bergantung kepada apa yang penting kepada anda dari segi
sumber dan kerumitan.
>> Tetapi biarlah saya mencadangkan bahawa data yang sesuai struktur, kaedah berpotensi suci, akan menjadi
sesuatu yang masa yang berterusan, tanpa mengira berapa banyak barangan adalah
di dalamnya, ia tidak akan menjadi hebat jika struktur data kembali jawapan dalam
masa yang sama.
Ya.
Perkataan ini di dalam kamus yang besar anda.
Atau tidak, perkataan ini tidak.
Atau mana-mana masalah itu di sana.
Nah mari kita lihat jika kita tidak boleh sekurang-kurangnya mengambil satu langkah ke arah itu.
>> Biar saya mencadangkan satu struktur data baru yang boleh digunakan untuk perkara-perkara yang berbeza,
dalam kes ini dipanggil jadual hash.
Dan jadi kita sebenarnya kembali kepada mengerling di pelbagai, dalam kes ini, dan
agak sewenang-wenangnya, saya telah disediakan ini jadual hash sebagai array dengan jenis yang
dua dimensi pelbagai -
atau sebaliknya ia digambarkan di sini sebagai dua dimensi pelbagai - tetapi ini hanya
pelbagai saiz 26, apa-apa jika kita hubungi meja pelbagai, kurungan jadual
sifar adalah segi empat tepat di atas.
Jadual kurungan 25 adalah segi empat tepat di bahagian bawah.
Dan ini adalah bagaimana saya boleh menarik data struktur di mana saya mahu menyimpan
orang nama.
>> Jadi sebagai contoh, dan saya tidak akan menarik segala-galanya di sini di atas, jika saya
mempunyai pelbagai ini, yang saya kini akan memanggil jadual hash, dan ini sekali lagi
lokasi sifar.
Ini di sini adalah lokasi satu, dan sebagainya.
Saya mendakwa bahawa saya ingin menggunakan data ini struktur, demi perbincangan,
untuk menyimpan nama-nama orang, Alice dan Bob dan Charlie dan lain-lain nama-nama itu.
Jadi berfikir ini sekarang sebagai permulaan , berkata, kamus
dengan banyak perkataan.
Mereka berlaku adalah nama-nama dalam contoh kita di sini.
Dan ini adalah semua terlalu yg, mungkin, untuk melaksanakan pemeriksa ejaan, seperti yang kita
mungkin bagi masalah yang ditetapkan enam.
>> Jadi, jika kita mempunyai pelbagai jumlah saiz 26 supaya ini adalah lokasi ke-25
di bahagian bawah, dan saya mendakwa bahawa Alice perkataan pertama di kamus
nama-nama yang saya mahu masukkan ke dalam RAM, ke dalam struktur data ini, di mana
naluri memberitahu anda bahawa Alice Nama harus pergi dalam barisan ini?
>> Kami mempunyai 26 pilihan.
Di mana kita mahu meletakkan dia?
Kami mahu dia dalam kurungan sifar, bukan?
A untuk Alice, mari kita memanggilnya yang sifar.
And B akan menjadi salah satu, dan C akan menjadi dua.
Jadi, kita akan menulis Nama Alice di sini.
Jika kita kemudian memasukkan Bob, beliau nama akan pergi sini.
Charlie akan pergi di sini.
Dan sebagainya ke bawah melalui ini struktur data.
>> Ini adalah satu struktur data yang indah.
Mengapa?
Nah apakah masa perjalanan memasukkan nama manusia ke dalam ini
data struktur sekarang?
Memandangkan jadual ini dilaksanakan, benar-benar, seperti array.
Baik ia adalah masa yang berterusan.
Ia adalah untuk satu.
Mengapa?
>> Nah bagaimana anda menentukan di mana Alice milik?
Anda melihat di mana surat namanya?
Pertama.
Dan anda boleh sampai ke sana, jika ia rentetan, dengan hanya melihat rentetan
kurungan sifar.
Jadi watak sifar tali.
Yang mudah.
Kami melakukan bahawa dalam kripto tugasan minggu lalu.
Dan kemudian sekali anda tahu bahawa ini Alice huruf modal, kita boleh tolak
kira 65 atau modal A sendiri, yang memberikan kita sifar.
Oleh itu, kita kini tahu bahawa Alice kepunyaan di lokasi sifar.
>> Dan memberi penunjuk kepada data ini struktur, beberapa jenis, berapa lama
ia membawa saya untuk mencari lokasi sifar dalam array?
Hanya satu langkah, betul Ia adalah masa yang berterusan kerana akses rawak kami
dicadangkan adalah ciri-ciri array.
Jadi dalam jangka pendek, memikirkan apa yang indeks nama Alice adalah, yang adalah, dalam
kes ini, adalah A, atau mari kita hanya menyelesaikan yang kepada sifar, di mana B adalah salah dan C ialah
dua, memikirkan bahawa daripada adalah masa yang berterusan.
Saya hanya perlu melihat surat pertama, memikirkan mana sifar adalah satu
pelbagai juga merupakan masa yang berterusan.
Jadi secara teknikal itu seperti dua langkah sekarang.
Tetapi itu masih berterusan.
Jadi kita panggil yang O besar satu, jadi kami telah Alice dimasukkan ke dalam jadual ini
masa yang sama.
>> Tetapi sudah tentu, saya menjadi naif di sini, bukan?
Bagaimana jika terdapat satu Harun di dalam kelas?
Atau Alicia?
Atau mana-mana nama-nama lain bermula dengan A. Di manakah kita akan meletakkan
orang itu, bukan?
Maksud saya, sekarang hanya terdapat tiga orang-orang di atas meja, jadi mungkin kita
Harun harus meletakkan di lokasi sifar satu dua tiga.
>> Betul, saya boleh meletakkan A di sini.
Tetapi, jika kita cuba untuk memasukkan ke dalam David senarai ini, di mana tidak David pergi?
Sekarang sistem kita mula berbuka ke bawah, bukan?
Kerana kini David berakhir di sini jika Harun sebenarnya di sini.
Dan sekarang ini idea keseluruhan yang mempunyai struktur data yang bersih yang memberikan kita
sisipan masa berterusan tidak lagi masa yang berterusan, kerana saya perlu
memeriksa, oh, damnit, seseorang sudah di lokasi Alice.
>> Biar saya menyiasat seluruh data ini struktur, mencari tempat untuk meletakkan
seseorang seperti nama Harun.
Dan sebagainya yang terlalu bermula mengambil masa linear.
Selain itu, jika anda kini mahu mencari Harun dalam struktur data ini, dan anda
memeriksa, dan nama Harun tidak ada di sini.
Sebaik-baiknya, anda hanya akan mengatakan Harun tidak dalam struktur data.
Tetapi jika anda mula membuat ruang untuk Harun di mana sepatutnya ada D
atau, anda, kes E teruk, perlu menyemak struktur data keseluruhan,
mana ia anaknya itu adalah turun ke dalam sesuatu linear dalam saiz meja.
>> Jadi semua betul, saya akan menetapkan ini.
Masalah di sini adalah bahawa saya telah 26 elemen dalam array ini.
Biar saya mengubahnya.
Whoops.
Izinkan saya mengubah supaya agak kesejahteraan saiz 26 dalam jumlah, notis bawah
indeks akan berubah n tolak 1.
Jika 26 adalah jelas terlalu kecil untuk manusia ' nama, kerana terdapat beribu-ribu
nama-nama di dunia, mari kita hanya membuat 100 atau 1,000 atau 10,000.
Mari kita memperuntukkan lebih banyak ruang.
>> Well yang tidak semestinya mengurangkan kebarangkalian bahawa kita tidak akan mempunyai dua
orang dengan nama-nama yang bermula dengan A, dan demikian, anda akan cuba untuk meletakkan A
nama-nama pada sifar lokasi masih.
Mereka masih akan berlanggar, yang bermakna kita masih memerlukan penyelesaian untuk meletakkan
Alice dan Harun dan Alicia dan lain-lain nama-nama yang bermula dengan A di tempat lain.
Tetapi berapa banyak masalah ini?
Apakah kebarangkalian bahawa anda mempunyai perlanggaran dalam data
Struktur seperti ini?
>> Baiklah, biar saya - kita akan kembali kepada soalan itu di sini.
Dan melihat bagaimana kita mungkin menyelesaikan terlebih dahulu.
Biar saya tarik sehingga cadangan ini di sini.
Apa yang kita hanya digambarkan adalah satu algoritma, heuristik yang dipanggil linear
menyelesaikan sesuatu di mana, jika anda cuba untuk memasukkan sesuatu di sini dalam data ini
struktur yang dipanggil jadual hash, dan terdapat tiada ruang di sana, anda
benar-benar menyiasat struktur data memeriksa, adakah ini boleh didapati?
Adakah ini yang ada ialah ini boleh didapati?
Adakah ini boleh didapati?
Dan apabila ia akhirnya adalah, anda memasukkan nama yang anda asalnya bertujuan
di tempat lain di lokasi tersebut.
Tetapi dalam kes paling teruk, satu-satunya tempat mungkin bahagian paling bawah data
struktur, akhir sangat pelbagai.
>> Jadi linear menyelesaikan sesuatu, dalam kes paling teruk, anaknya itu adalah turun ke dalam algoritma linear di mana
Harun, jika dia berlaku akan dimasukkan lepas dalam struktur data ini, dia mungkin
bertembung dengan lokasi pertama ini, tetapi kemudian berakhir dengan nasib malang pada akhir sangat.
Jadi ini bukan berterusan masa suci kaedah berpotensi untuk kita.
Pendekatan memasukkan unsur-unsur ke struktur data yang dipanggil hash
jadual nampaknya tidak menjadi masa yang berterusan sekurang-kurangnya tidak dalam kes umum.
Ia boleh menjadi sesuatu yang diturunkan linear.
>> Jadi apa jika kita menyelesaikan pertembungan agak berbeza?
Jadi di sini adalah yang lebih canggih pendekatan untuk apa yang masih
dipanggil jadual hash.
Dan dengan hash, sebagai diketepikan, apa yang Yang saya maksudkan adalah indeks yang
Saya disebut lebih awal.
Untuk sesuatu hash boleh dianggap sebagai kata kerja.
>> Jadi, jika anda hash Alice adalah nama, fungsi hash, jadi untuk bercakap,
perlu kembali nombor.
Dalam kes ini adalah sifar jika dia tergolong di lokasi sifar, satu jika dia tergolong di
lokasi satu, dan sebagainya.
Jadi fungsi hash saya setakat ini telah sangat mudah, hanya melihat
huruf pertama dalam nama seseorang.
Tetapi fungsi hash mengambil sebagai input beberapa keping data,
tali, int an, apa sahaja.
Dan ia memuntahkannya keluar biasanya nombor.
Dan bilangan yang mana data unsur tergolong dalam struktur data
dikenali di sini sebagai sebuah jadual hash.
>> Jadi hanya intuitif, ini adalah satu konteks yang sedikit berbeza.
Ini sebenarnya adalah merujuk kepada contoh melibatkan hari lahir, di mana
mungkin terdapat sebanyak 31 hari dalam bulan tersebut.
Tetapi apa yang orang ini memutuskan untuk dilakukan sekiranya berlaku perlanggaran?
Konteks kini sedang, bukan perlanggaran nama, tetapi perlanggaran hari lahir,
jika dua orang mempunyai hari jadi yang sama pada ke-2 Oktober, misalnya.
>> PELAJAR: [didengar].
>> SPEAKER 1: Ya, jadi di sini kita mempunyai yang memanfaatkan senarai berkaitan.
Jadi ia kelihatan sedikit berbeza dari kita menarik ia awal.
Tetapi kita nampaknya perlu array di sebelah kiri.
Itulah salah satu indeks, tanpa sebab tertentu.
Tetapi ia masih array.
Ia adalah pelbagai petunjuk.
Dan setiap unsur-unsur, setiap golongan-golongan ini atau garis condong - tanda palang
mewakili null - masing-masing petunjuk nampaknya menunjuk ke
apa struktur data?
Satu senarai berkaitan.
>> Jadi sekarang kita mempunyai keupayaan untuk kod keras ke dalam program kami
saiz meja.
Dalam hal ini, kita tahu ada tidak pernah lebih daripada 31 hari dalam sebulan.
Begitu sukar pengekodan nilai seperti 31 adalah munasabah dalam konteks itu.
Dalam konteks nama, keras pengekodan 26 tidak munasabah ia rakyat
nama-nama yang hanya bermula dengan, misalnya, abjad melibatkan A hingga Z.
>> Kami boleh mengasak mereka semua ke dalam data struktur selagi, apabila kita mendapat
perlanggaran, kita tidak meletakkan nama-nama di sini, kita bukannya berfikir sel-sel
tidak seperti tali diri mereka sendiri, tetapi sebagai petunjuk untuk, misalnya, Alice.
Dan kemudian Alice boleh mempunyai penunjuk lain kepada nama lain bermula dengan
A. Dan Bob sebenarnya berlaku di sini.
>> Dan jika ada nama lain bermula dengan B, dia berakhir di sini.
Dan sebagainya setiap elemen ini jadual dua, jika kita direka ini
sedikit lebih bijak -
datang pada -
jika kita direka ini lebih sedikit bijak, kini menjadi data penyesuaian
struktur, di mana tidak ada had keras kepada berapa banyak unsur-unsur anda boleh memasukkan
ke dalam kerana jika anda mempunyai perlanggaran, itulah denda.
Hanya pergi ke hadapan dan menambah kepada apa yang kita lihat sedikit lalu adalah
dikenali sebagai senarai yang berkaitan.
>> Nah mari kita berhenti untuk seketika.
Apakah kebarangkalian perlanggaran di tempat pertama?
Betul, mungkin saya lebih berfikir, mungkin Saya lebih kejuruteraan masalah ini,
kerana anda tahu apa?
Ya, saya boleh datang dengan sewenang-wenangnya contoh dari bahagian atas kepala saya seperti
Allison dan Harun, tetapi dalam realiti, diberi taburan seragam
input, iaitu beberapa sisipan rawak ke dalam struktur data, apa yang benar-benar
kebarangkalian perlanggaran?
Nah ternyata, ia sebenarnya super tinggi.
Biar saya umum ini masalah adalah seperti ini.
>> Jadi di dalam bilik n CS50 pelajar, apa yang kebarangkalian bahawa sekurang-kurangnya
dua pelajar di dalam bilik mempunyai hari jadi yang sama?
Jadi ada apa. anjing yang sedikit -
200, 300 orang di sini dan beberapa ratus orang di rumah hari ini.
Jadi, jika anda mahu bertanya kepada diri sendiri apa yang kebarangkalian dua orang
di dalam bilik ini mempunyai hari jadi yang sama, kita boleh memikirkan ini.
Dan saya benar-benar mendakwa terdapat dua orang-orang yang lahir yang sama.
>> Sebagai contoh, adakah sesiapa mempunyai hari jadi hari ini?
Semalam?
Esok?
Baiklah, jadi ia berasa seperti saya akan perlu melakukan ini 363 atau lebih lebih
masa untuk benar-benar memahami jika kita mempunyai perlanggaran.
Atau kita hanya boleh melakukan ini secara matematik bukannya tediously
berbuat demikian.
Dan mencadangkan yang berikut.
>> Jadi, saya mencadangkan supaya kita boleh model Kebarangkalian dua orang yang mempunyai
ulang tahun yang sama dengan kebarangkalian 1 tolak kemungkinan tiada siapa yang mempunyai
hari lahir yang sama.
Jadi untuk mendapatkan ini, dan ini hanya cara mewah untuk menulis ini, bagi
orang pertama di dalam bilik, dia boleh mempunyai mana-mana satu yang mungkin
hari lahir dengan andaian 365 hari dalam tahun ini, dengan memohon maaf kepada orang-orang dengan
hari lahir 29 Februari.
>> Jadi orang pertama di dalam bilik ini adalah percuma mempunyai apa-apa bilangan hari lahir
daripada kemungkinan 365 supaya kami akan berbuat demikian 365 dibahagikan dengan 365,
yang merupakan salah satu.
Orang yang akan datang di dalam bilik, jika matlamat adalah untuk mengelakkan perlanggaran, hanya boleh
mempunyai atau hari jadi beliau tentang bagaimana beberapa hari yang berbeza mungkin?
364.
Jadi penggal kedua dalam ungkapan ini adalah dasarnya melakukan matematik yang bagi kami
dengan menolak off satu hari mungkin.
Dan kemudian pada hari berikutnya, hari akan datang, hari berikutnya ke jumlah
orang di dalam bilik.
>> Dan jika kita kemudian pertimbangkan, apakah cara kemungkinan tidak semua orang mempunyai
hari lahir yang unik, tetapi sekali lagi 1 tolak itu, apa yang kita dapat adalah ungkapan
yang boleh sangat fancifully kelihatan seperti ini.
Tetapi ia lebih menarik melihat visual.
Ini adalah carta di mana di paksi-x ialah jumlah orang di dalam bilik itu,
beberapa hari lahir.
Pada paksi-y kebarangkalian perlanggaran, dua orang
mempunyai hari jadi yang sama.
>> Dan bawa pulang dari keluk ini bahawa sebaik sahaja anda mendapat seperti 40
pelajar, anda sehingga pada kebarangkalian 90% combinatorically dua
orang atau lebih mempunyai hari lahir yang sama.
Dan apabila anda mendapat 58 orang suka ia hampir 100% dari peluang kedua-dua
orang di dalam bilik akan mempunyai hari jadi yang sama, walaupun terdapat
365 atau 366 baldi mungkin, dan hanya 58 orang di dalam bilik.
Hanya statistik anda mungkin mendapatkan perlanggaran, yang pendek
mendorong perbincangan ini.
Bahawa walaupun kita mendapatkan mewah di sini, dan mula mempunyai rantaian ini, kita masih
akan mempunyai pertembungan.
>> Jadi yang menimbulkan persoalan, apakah kos menjalankan sisipan dan pemotongan
ke dalam struktur data yang seperti ini?
Nah biar saya mencadangkan -
dan biarlah saya kembali ke skrin di atas di sini - jika kita mempunyai n unsur dalam
senarai, jadi jika kita cuba untuk memasukkan n elemen, dan kami mempunyai
berapa jumlah baldi?
Katakan 31 jumlah baldi dalam hal lahir.
Apakah panjang maksimum satu ini rantaian berpotensi?
>> Jika ada lagi 31 mungkin hari lahir pada bulan tertentu.
Dan kami hanya pembungkusan materi semua orang -
sebenarnya itu adalah satu contoh bodoh.
Mari kita buat 26 sebaliknya.
Jadi, jika benar-benar orang-orang yang mempunyai nama-nama bermula dengan A hingga Z, dengan itu memberi
kita 26 kemungkinan.
Dan kita menggunakan struktur data seperti yang kita hanya melihat, di mana kita mempunyai
pelbagai petunjuk, yang mana setiap mata kepada senarai yang berkaitan di mana
Senarai pertama adalah semua orang dengan nama Alice.
Senarai kedua ialah setiap dengan nama bermula dengan A, bermula
dengan B, dan sebagainya.
>> Apa yang panjang mungkin setiap senarai mereka jika kita andaikan yang bersih baik
pengedaran nama A hingga Z seluruh struktur data keseluruhan?
Ada n orang dalam struktur data dibahagikan dengan 26, jika mereka baik
tersebar di seluruh struktur data.
Jadi panjang masing-masing rantaian adalah n dibahagikan dengan 26.
Tetapi dalam O notasi besar, apakah itu?
Apa yang benar-benar?
Jadi ia adalah benar-benar hanya n, bukan?
Kerana kita telah berkata pada masa lalu, ugh bahawa anda membahagikan sebanyak 26.
Ya, dalam realiti, ia adalah lebih cepat.
Tetapi dalam teori, ia bukan asasnya semua yang lebih cepat.
>> Oleh itu, kita seolah-olah tidak menjadi semua yang banyak dekat dengan kaedah berpotensi suci ini.
Malah, ini adalah hanya masa linear.
Heck, pada ketika ini, mengapa tidak kita hanya menggunakan satu senarai dikaitkan besar?
Mengapa kita tidak hanya menggunakan satu besar pelbagai untuk menyimpan nama-nama
semua orang di dalam bilik?
Nah, ada sesuatu yang masih menarik tentang jadual hash?
Masih terdapat sesuatu yang menarik mengenai struktur data
yang kelihatan seperti ini?
Ini.
>> PELAJAR: [didengar].
>> SPEAKER 1: Hak, dan sekali lagi jika ia hanya algoritma masa linear, dan
struktur data masa linear, mengapa tidak saya hanya menyimpan nama semua orang dalam yang besar
pelbagai, atau dalam senarai yang besar dikaitkan?
Dan berhenti membuat CS begitu jauh lebih sukar dari ia perlu?
Apa yang menarik tentang perkara ini, walaupun walaupun saya tercalar ia keluar?
>> PELAJAR: [didengar].
>> SPEAKER 1 sisipan tidak?
Mahal lagi.
Jadi sisipan berpotensi masih boleh masa yang berterusan, walaupun data anda
struktur kelihatan seperti ini, pelbagai petunjuk, setiap yang menghala ke arah
berpotensi senarai berkaitan.
Bagaimana anda boleh mencapai berterusan memasukkan masa nama?
Melekat di hadapan, bukan?
>> Jika kita mengorbankan matlamat reka bentuk daripada sebelum ini, di mana kita mahu menyimpan
nama semua orang, misalnya, disusun, atau semua nombor di atas pentas disusun,
menganggap bahawa kita mempunyai senarai dikaitkan Unsorted.
Ia hanya kos kami satu atau dua langkah, seperti dalam kes Ben dan Brian
sebelum ini, untuk memasukkan elemen di permulaan senarai.
Jadi, jika kita tidak mengambil berat tentang menyusun semua nama-nama yang bermula dengan A atau semua
nama-nama yang bermula dengan B, kita masih boleh mencapai memasukkan masa yang berterusan.
Kini melihat ke atas Alice atau Bob atau apa-apa nama secara umum masih apa?
Ia adalah besar O n dibahagikan dengan 26, pada kes yang sesuai di mana semua orang adalah seragam
diedarkan, di mana terdapat banyak A kerana ada yang Z, yang mungkin
tidak realistik.
Tetapi itu masih linear.
>> Tetapi di sini, kami datang kembali ke titik notasi asimptot menjadi
teorinya benar.
Tetapi dalam dunia sebenar, jika saya mengatakan bahawa program saya boleh melakukan sesuatu yang 26 kali
lebih cepat daripada anda, yang mana program anda akan lebih suka menggunakan?
Anda atau saya, yang adalah 26 kali lebih cepat?
Realistik, orang yang ialah 26 kali lebih cepat, walaupun secara teori
algoritma kami berjalan di yang sama asimptot berjalan masa.
>> Biar saya mencadangkan yang berbeza penyelesaian sama sekali.
Dan jika ini tidak meniup fikiran anda, kita berada di luar struktur data.
Jadi ini adalah ia indone a -
jenis nama bodoh.
Ia datang daripada dapatan, dan perkataan dieja indone, t-r-i-e, kerana
kursus semula bunyi seperti indone.
Tetapi itu sejarah daripada indone perkataan.
>> Jadi indone yang memang beberapa jenis pokok, dan ia juga yang bermain di perkataan itu.
Dan walaupun anda tidak boleh agak melihatnya dengan visualisasi ini, indone adalah
pokok berstruktur, seperti pokok kekeluargaan dengan satu moyang di atas dan banyak
cucu dan cicit seperti daun di bahagian bawah.
Tetapi setiap nod dalam indone adalah array.
Dan ia adalah dalam array - dan mari menggampangkan seketika - ia adalah satu
pelbagai, dalam hal ini, saiz 26, di mana setiap nod lagi adalah pelbagai saiz
26, di mana unsur sifar dalam itu pelbagai mewakili A, dan yang terakhir
elemen dalam setiap apa-apa pelbagai mewakili Z.
>> Jadi saya mencadangkan, kemudian, bahawa data ini struktur, yang dikenali sebagai indone, boleh menjadi
juga digunakan untuk menyimpan kata-kata.
Kita melihat masa lalu bagaimana kita boleh menyimpan kata-kata, atau dalam kes ini nama-nama, dan kami
lihat sebelum ini bagaimana kita boleh menyimpan nombor, tetapi jika kita memberi tumpuan kepada nama atau tali
di sini, melihat apa yang menarik.
Saya menuntut bahawa nama Maxwell adalah dalam struktur data ini.
Di manakah anda melihat Maxwell?
>> PELAJAR: [didengar].
>> SPEAKER 1: Di sebelah kiri.
Jadi apa yang menarik dengan data ini struktur adalah bukannya kedai
rentetan M-A-X-W-E-L-L backslash sifar, semua contiguously, apa yang anda lakukan dan bukannya
sedang mengikuti.
Jika ini adalah indone seperti struktur data, setiap nod yang sekali lagi array,
dan anda mahu menyimpan Maxwell, anda indeks dan sebagainya nod akar, jadi
untuk bercakap, nod yang paling atas, di lokasi M, betul, jadi
kira-kira ke tengah-tengah.
Dan kemudian dari sana, anda mengikuti penunjuk kepada nod kanak-kanak, jadi untuk bercakap.
Jadi, dalam erti kata pokok keluarga, anda mengikutinya ke bawah.
Dan yang membawa anda ke nod yang lain di sebelah kiri ada, yang
hanya pelbagai yang lain.
>> Dan kemudian jika anda mahu menyimpan Maxwell, anda mencari penunjuk yang mewakili
A, yang merupakan salah satu ini di sini.
Kemudian anda pergi ke nod seterusnya.
Dan notis - ini adalah mengapa gambar ini yang terpedaya sedikit -
nod ini kelihatan super kecil.
Tetapi di sebelah kanan ini adalah Y dan Z. Ia hanya penulis telah dipenggal yang
gambar supaya anda benar-benar melihat sesuatu.
Jika gambar ini akan menjadi sangat luas.
Jadi sekarang anda index ke lokasi X, maka W, E Kemudian, maka L, maka L. Kemudian apa
rasa ingin tahu ini?
>> Nah, jika kita menggunakan jenis ini baru mengambil bagaimana untuk menyimpan tali dalam
struktur data, anda masih perlu asasnya memeriksa dalam data
struktur yang perkataan yang berakhir di sini.
Dalam erti kata lain, setiap nod ini entah bagaimana harus ingat bahawa kita
sebenarnya diikuti semua petunjuk dan meninggalkan sedikit
remah roti di bahagian bawah di sini ini struktur untuk menunjukkan M-A-X-W-E-L-L adalah
memang dalam struktur data ini.
>> Oleh itu, kita boleh melakukan ini seperti berikut.
Setiap satu daripada nod dalam gambar kita hanya saw mempunyai satu, pelbagai saiz 27.
Dan kini ia 27, kerana dalam p yang ditetapkan enam, kita benar-benar akan memberikan anda apostrofe,
supaya kita boleh mempunyai nama-nama seperti O'Reilly dan lain-lain dengan apostrofi.
Tetapi idea sama.
Setiap satu daripada unsur-unsur dalam mata untuk pelbagai struct a
nod, jadi hanya nod.
Jadi ini adalah sangat mengingatkan senarai berkaitan kami.
>> Dan kemudian saya mempunyai Boolean, yang saya akan memanggil perkataan, yang hanya akan menjadi
benar jika perkataan yang berakhir di nod dalam pokok itu.
Ia berkesan mewakili sedikit segi tiga yang kita lihat sebentar tadi.
Jadi, jika satu perkataan yang bermula pada nod dalam pokok, bahawa bidang perkataan akan menjadi kenyataan,
yang konsep memeriksa off, atau kita melukis segi tiga ini, ya ada
adalah perkataan di sini.
>> Jadi ini adalah indone a.
Dan kini persoalannya ialah, apa yang sedang berjalan itu masa?
Adakah ia besar O n?
Adakah ia sesuatu yang berlainan?
Nah, jika anda mempunyai n nama dalam data ini struktur, Maxwell menjadi hanya salah satu daripada
mereka, apakah masa perjalanan memasukkan atau mencari Maxwell?
Apa masa larian memasukkan Maxwell?
Jika ada n nama-nama lain sudah dalam jadual?
Ya?
>> PELAJAR: [didengar].
>> SPEAKER 1: Ya, ia adalah panjang nama, bukan?
Jadi M-a-x-w-e-l-l jadi ia berasa seperti ini algoritma adalah besar O tujuh.
Kini, sudah tentu, nama akan berbeza-beza.
Mungkin ia adalah nama yang singkat.
Mungkin ia adalah nama yang lebih panjang.
Tetapi apa yang penting di sini ialah bahawa ia adalah satu jumlah yang tetap.
Dan mungkin ia tidak benar-benar berterusan, tetapi tuhan, jika realistik, dalam
kamus, ada mungkin beberapa had kepada bilangan huruf dalam
nama orang itu dalam negara tertentu.
>> Dan supaya kita boleh mengandaikan bahawa nilai adalah satu pemalar.
Saya tidak tahu apa yang ada.
Ia mungkin lebih besar daripada kita fikir ia.
Kerana selalu ada beberapa sudut kes dengan nama yang panjang gila.
Jadi mari kita memanggilnya k, tetapi ia masih berterusan mungkin, kerana setiap
nama di dunia, sekurang-kurangnya dalam negara tertentu, adalah panjang yang atau
pendek, jadi ia tetap.
Tetapi apabila kita telah berkata sesuatu yang besar O nilai yang tetap, apa yang
benar-benar sama dengan?
Itu benar-benar perkara yang sama sebagai berkata masa yang berterusan.
>> Sekarang kita jenis penipuan, bukan?
Kami jenis memanfaatkan teori beberapa di sini untuk mengatakan yang baik, perintah k ialah
benar-benar hanya memerintahkan satu, dan ia adalah masa yang berterusan.
Tetapi ia benar-benar adalah.
Kerana wawasan utama di sini adalah bahawa jika kita mempunyai n nama pun dalam
struktur data, dan kami memasukkan Maxwell, ialah jumlah masa yang membawa kita ke
memasukkan Maxwell pada semua yang terlibat dengan berapa ramai orang lain
adalah dalam struktur data?
Nampaknya tidak menjadi.
Jika saya mempunyai satu bilion lebih unsur ini indone, dan kemudian memasukkan Maxwell, adalah
beliau pada semua yang terlibat?
No
Dan yang tidak seperti mana-mana data hari struktur yang kita lihat setakat ini, di mana
masa berjalan algoritma anda benar-benar bebas daripada berapa banyak
barangan atau tidak sudah dalam struktur data.
>> Dan sebagainya dengan ini mampu anda sekarang adalah peluang untuk p set enam, yang akan
sekali lagi melibatkan melaksanakan anda sendiri pemeriksa ejaan, membaca dalam 150,000
kata-kata, cara terbaik untuk menyimpan yang tidak semestinya jelas.
Dan walaupun saya telah bercita-cita untuk mencari kaedah berpotensi suci, saya tidak
mendakwa bahawa indone adalah.
Malah, satu jadual hash boleh sangat baik membuktikan untuk menjadi lebih cekap.
Tetapi mereka hanya -
itu hanya salah satu daripada keputusan reka bentuk anda akan mempunyai untuk membuat.
>> Tetapi dalam menutup mari kita 50 atau lebih saat untuk mengambil mengintip pada apa yang terletak di
seminggu sebelum datang dan seterusnya kita peralihan daripada baris arahan ini
dunia jika program C kepada perkara-perkara web berdasarkan dan bahasa seperti PHP dan
JavaScript dan internet itu sendiri, protokol seperti HTTP, yang anda telah
diambil untuk diberikan selama bertahun-tahun sekarang, dan yang paling ditaip setiap
hari, mungkin, atau dilihat.
Dan kita akan mula mengupas kembali lapisan apa yang internet.
Dan apa kod yang mendasari alat hari ini.
Jadi 50 saat penggoda ini di sini.
Saya memberi anda Warriors of Internet.
>> [MAIN SEMULA VIDEO]
>> -Beliau datang dengan mesej.
Dengan protokol semua sendiri.
Dia datang ke dunia firewall kejam, peduli router, dan bahaya yang jauh
lebih teruk daripada kematian.
Dia cepat.
Dia kuat.
Dia TCPIP.
Dan dia mendapat alamat anda.
Warriors of Internet.
>> [AKHIR VIDEO MAIN SEMULA]
>> SPEAKER 1: Itu adalah bagaimana internet boleh bekerja pada minggu depan.