>> DAVID MALAN: Baiklah.
Selamat kembali ke CS50.
Ini adalah permulaan minggu 8.
Dan ingat bahawa set masalah 5 berakhir dengan sedikit cabaran.
Jadi andaian anda pulih semua anda Felo pengajaran dan gambar-gambar CA
dalam fail card.raw, anda layak kini mencari semua orang-orang, dan
seorang pemenang bertuah akan berjalan kaki ke rumah dengan satu perkara-perkara ini, gerakan lompat
alat yang boleh anda gunakan untuk akhir projek, misalnya.
>> Ini, setiap tahun, membawa kepada sedikit creepiness.
Dan supaya apa yang saya fikir saya akan lakukan ialah berkongsi dengan anda beberapa nota yang mempunyai
pergi dan balik ke atas senarai kakitangan lewat.
Sebagai contoh, hanya malam tadi, quote unquote, dari salah seorang kakitangan
anggota, "Saya hanya mempunyai ketukan pelajar di pintu saya untuk mengambil gambar dengan saya.
Stalkers, saya memberitahu anda. "Bermula dari agak deskriptif dan kemudian kami berpindah
ke, satu jam atau lebih kemudian, "Saya mempunyai pelajar menunggu saya selepas seksyen
dan dia mempunyai semua nama-nama dan gambar kami pada beberapa keping kertas. "Baiklah.
Jadi dianjurkan, tetapi tidak semua yang menyeramkan yet.
>> Kemudian, "Saya berada di luar bandar hujung minggu ini, dan apabila saya kembali, terdapat satu dalam
saya
bilik tidur. "[Ketawa]
DAVID MALAN: quote Next daripada kakitangan anggota, "seorang pelajar datang ke rumah saya di
Somerville pada 4:00 pagi ini. "Next kakitangan, "saya mendapat ke hotel saya di San
Francisco dan pelajar yang sedang menunggu saya di lobi dengan tiga DSLRs. "
Jenis kamera.
"Saya tidak walaupun pada kakitangan semester ini, tetapi pelajar memecah masuk ke rumah saya ini
pagi dan merekodkan segala-galanya dengan Google Glass. "Dan kemudian akhir sekali,
"Sekurang-kurangnya 12 orang telah bersungguh-sungguh menunggu bagi saya apabila saya keluar dari saya
limousin, dan kemudian saya
bangun. "Baiklah.
Jadi antara gambar-gambar, seperti yang anda boleh ingat, adalah rakan-rakan ini di sini, yang anda
mungkin dikenali sebagai Milo Pisang, yang tinggal dengan Lauren Carvalho, kepala kita
Fellow pengajaran.
Milo, Milo, datang ke sini lelaki.
Milo.
Minda anda, dia memakai Google Glass, jadi kami akan menunjukkan kepada anda semua ini selepas.
Jadi ini adalah Milo jika anda ingin mengambil gambar dengan dia selepas itu.
Jika anda ingin untuk melihat keluar pada penonton di sana.
OK.
Itulah rakaman yang baik.
Nah, Milo Pisang.
Oh, tidak berbuat demikian.
>> [Ketawa]
>> OK.
Jadi perkataan kemudian apa yang akan berlaku, kerana seperti yang kita mula peralihan,
minggu ini khususnya, daripada C dalam persekitaran baris arahan untuk PHP dan
JavaScript dan SQL dan HTML dan CSS dalam persekitaran berasaskan web, kami akan
melengkapkan anda dengan semua lebih banyak pengetahuan untuk
potensi projek akhir.
Ke arah itu, tentu mempunyai tradisi mengadakan seminar yang
adalah mengenai topik-topik yang menyeleweng untuk kursus.
Sangat banyak yang berkaitan dengan pengaturcaraan dan pembangunan aplikasi dan sebagainya, tetapi
tidak semestinya diterokai oleh sukatan pelajaran kursus sendiri.
>> Jadi, jika anda mungkin berminat dalam satu atau lebih seminar tahun ini,
mendaftar di cs50.net/seminar.
Terdapat seminar lebih tua di cs50.net/seminars.
Dan dalam jadual setakat ini untuk tahun ini adalah Amazing Web Apps dengan Ruby on
Rails, yang merupakan alternatif bahasa untuk PHP.
Linguistik pengiraan.
Pengenalan kepada IOS, yang merupakan platform yang digunakan untuk iPhone dan
pembangunan iPad.
JavaScript untuk Web Apps, kami akan meliputi itu, tetapi dalam seminar ini, anda akan pergi
ke lebih terperinci.
>> Melompat Motion, jadi kita benar-benar akan mempunyai beberapa rakan-rakan kami dari Usul Leap,
syarikat itu sendiri, menyertai kami.
Esok, sebenarnya, untuk memberikan hands-on seminar, jika
menarik minat anda.
Meteor.js, teknik alternatif bagi menggunakan JavaScript tidak dalam pelayar,
tetapi pada pelayan.
Node.js, yang sangat banyak dalam urat itu juga.
Anggun Android Design.
Android menjadi alternatif yang sangat popular untuk IOS dan Telefon Windows
dan platform mudah alih yang lain.
Dan Web Keselamatan Pertahanan Aktif.
>> Jadi pada hakikatnya, jika anda ingin untuk melibatkan diri dalam hal ini, izinkan saya
membuat nota ini.
Kami amat gembira untuk mengatakan bahawa rakan-rakan kami di Leap
Gerakan, yang merupakan permulaan -
peranti ini benar-benar hanya datang keluar beberapa bulan lalu -
telah anggun menderma 30 peranti sedemikian dalam kelas sebagai ramai pelajar, jika
anda ingin meminjam perkakasan penghujung semester dan menggunakannya untuk
projek akhir sebenar.
Mereka menyokong beberapa bahasa.
Tiada seorang pun daripada mereka C, tiada mereka PHP, jadi sedar satu atau lebih daripada seminar ini
mungkin membuktikan kepentingan.
Dan semua mereka akan difilemkan di Sekiranya anda tidak dapat
untuk hadir.
Jadual ini akan diumumkan melalui e-mel seperti yang kita mengukuhkan bilik.
>> Dan akhir sekali, jika anda pergi ke projects.cs.50.net, ini adalah laman web
kami mengekalkan setiap tahun bahawa kami menjemput orang dari masyarakat, fakulti,
jabatan, kakitangan, dan kedua-dua di luar CS50 untuk
mencadangkan idea-idea projek.
Perkara yang menarik minat kumpulan pelajar.
Perkara yang menarik untuk jabatan.
Jadi jangan menjadikan di sana jika anda berjuang dengan ketidaktentuan tentang apa yang anda
diri anda ingin untuk menangani.
>> Jadi masa lepas, kita memperkenalkan dikatakan struktur data yang lebih kompleks daripada kita akan
dilihat dalam beberapa minggu lalu.
Kami akan telah menggunakan array cukup gembira sebagai berguna jika
struktur data mudah.
Kemudian kami memperkenalkan ini, yang sudah tentu dikaitkan senarai.
Dan apa yang merupakan salah satu motivasi untuk memperkenalkan struktur data ini?
Ya?
Apa itu?
>> PENONTON: saiz Dinamik.
>> DAVID MALAN: saiz Dinamik.
Jadi, manakala dalam pelbagai, anda perlu tahu saiz terlebih dahulu apabila
anda memperuntukkan itu.
Dalam senarai berkaitan, anda tidak perlu tahu bahawa.
Anda boleh hanya malloc, atau lebih amnya, peruntukan tambahan
nod, jadi untuk bercakap, bila-bila masa anda mahu masukkan lebih banyak data.
Dan nod tidak mempunyai ditentukan makna.
Ia hanya istilah generik menggambarkan beberapa jenis bekas yang kami
menggunakan dalam struktur data kami untuk menyimpan beberapa perkara yang menarik, yang ini
kes berada integer.
>> Tetapi selalu ada tradeoff a.
Jadi kita mendapatkan saiz dinamik data struktur, tetapi apakah harga yang kita bayar?
Apa keburukan senarai berkaitan?
Ya?
>> PENONTON: Memerlukan memori yang lebih.
>> DAVID MALAN: Ia memerlukan lebih ingatan, bagaimana sebenarnya?
>> PENONTON: [didengar].
>> DAVID MALAN: Tepat sekali.
Jadi sekarang kita telah mengambil petunjuk memori tambahan yang kita sebelum ini
tidak perlu, kerana kelebihan sebuah array, sudah tentu, adalah bahawa
segala-galanya berdampingan, belakang untuk kembali ke belakang, yang
memberikan anda akses secara rawak.
Kerana hanya dengan menggunakan kurungan persegi notasi, atau lebih teknikal penunjuk
aritmetik, tambahan yang sangat mudah, anda boleh mengakses mana-mana
elemen dalam masa yang sama.
Dan sebenarnya, itu jenis membayangkan pada harga lain yang kita membayar dengan
senarai berkaitan.
>> Apa yang berlaku kepada masa perjalanan sesuatu seperti Search, jika saya ingin
mencari nilai dan di dalam senarai yang dikaitkan?
Apakah masa saya berjalan menjadi?
Big O n.
Jika ia disusun?
Bagaimana jika struktur data yang disusun?
Bolehkah saya melakukan lebih baik daripada yang besar O n untuk mencari?
Tidak, kerana dalam kes paling teruk ia mungkin baik boleh disusun, tetapi bilangan
yang anda cari mungkin besar.
Ia mungkin menjadi nombor 100, yang mungkin berlaku untuk semua
cara pada akhir.
Dan kerana anda hanya boleh mengakses berkaitan senarai dalam pelaksanaan ini dengan
cara nod pertama, anda masih jenis daripada nasib.
Anda perlu merentasi segala-galanya dari pertama berlangsung untuk mencari
bahawa nilai besar seperti 100.
Atau untuk menentukan sama ada ia tidak walaupun di sana.
>> Jadi kita tidak boleh melakukan apa algoritma dalam data struktur yang kelihatan seperti ini?
Kita tidak boleh melakukan carian binari, kerana carian binari diperlukan bahawa kita mempunyai
akses rawak.
Kita hanya boleh melompat dari lokasi ke lokasi tanpa perlu mengikuti
ini serbuk roti dalam bentuk semua ini petunjuk.
>> Sekarang, bagaimana kita melaksanakan ini?
Nah, jika kita pergi ke skrin di sini, jika kita boleh dengan cepat reimplement data ini
struktur -
tulisan tangan saya tidak semua yang yang besar di sini, tetapi kita akan cuba.
Struct Jadi typedef, dan apa yang tidak saya mahu memanggil perkara ini di sini?
Nod.
Jadi saya akan mendapatkan kami bermula.
Dan kini, apa yang perlu dalam struktur data untuk itu tunggal
senarai dikaitkan?
Berapa banyak bidang?
>> Jadi kedua-duanya.
Satu adalah cukup mudah.
Jadi int n.
Dan kita boleh memanggil n apa-apa yang kita mahu, tetapi ia perlu int jika kami
melaksanakan senarai dikaitkan untuk Ints.
Dan kini apakah kedua bidang perlu?
Struct nod *.
Jadi, jika saya lakukan struct nod *, dan kemudian saya boleh memanggil ini juga apa yang saya mahu,
tetapi hanya jelas saya akan memanggil ia akan datang, seperti yang kita telah lakukan.
Dan kemudian saya akan menutup pendakap kerinting saya.
>> Dan sekarang, kerana masa lalu, Saya meletakkan nod di sini.
Tetapi jika saya mengisytiharkan ini adalah sebagai nod, kenapa saya bersusah payah begitu
lantung di sini mengisytiharkan struct nod * akan datang, berbanding
hanya nod * seterusnya?
Ya?
>> PENONTON: [didengar].
>> DAVID MALAN: Tepat sekali.
Tepat sekali.
Kerana C benar-benar akan membawa anda secara literal dan hanya melihat definisi nod
cara turun di sini, anda tidak boleh merujuk kepada di sini.
Jadi kita mempunyai jenis ini terlebih dahulu perisytiharan di sini, yang diakui
lebih lantung.
Struct nod, yang bermakna kita kini boleh mengakses
dalam struktur data.
>> Dan sebagai diketepikan, kerana ini adalah menjadi sedikit lebih subjektif sekarang,
bintang teknikal boleh pergi di sini, ia boleh pergi di sini, ia boleh
walaupun pergi di tengah-tengah.
Kami telah diterima pakai, dalam panduan gaya untuk kursus, konvensyen meletakkan
bintang di sebelah kanan kepada data jenis, yang dalam kes ini,
akan struct nod.
Tetapi sedar dalam banyak buku teks dan rujukan dalam talian, anda mungkin memang
lihat di sebelah yang lain.
Tetapi hanya menyedari bahawa kedua-dua sebenarnya akan bekerja dan anda hanya perlu
konsisten.
>> Baiklah.
Jadi itu adalah pengakuan kita struct nod.
Tetapi kemudian kami mula melakukan lebih perkara-perkara yang canggih.
Sebagai contoh, kami mengambil keputusan untuk memperkenalkan sesuatu seperti jadual hash.
Jadi di sini adalah jadual hash n saiz, diindeks dari 0 di sebelah kiri untuk n
tolak 1 di bahagian bawah kiri.
Ini boleh menjadi hash jadual untuk apa-apa.
Tetapi apa jenis perkara yang kita bercakap kira-kira menggunakan jadual hash untuk?
Menyimpan apa?
>> Nama.
Kita boleh melakukan nama-nama seperti kita lakukan masa lalu.
Dan benar-benar, anda boleh menyimpan apa-apa.
Dan kita akan melihat ini sekali lagi di PHP dan JavaScript.
Satu jadual hash adalah sejenis bagus Swiss Pisau tentera yang membolehkan anda untuk menyimpan
cukup banyak apa sahaja yang anda mahu dalam ia dengan mengaitkan dengan nilai-nilai kunci.
Kunci dengan nilai.
>> Sekarang dalam kes ini mudah, kami kunci hanya nombor.
Kami melaksanakan hash meja sebagai array.
Dan sebagainya kekunci 0, 1, 2, dan sebagainya.
Dan supaya kita, sebagai manusia, memutuskan lepas minggu yang anda tahu apa, jika kita
akan menyimpan nama, mari kita hanya sewenang-wenangnya, tetapi cukup munasabah,
menganggap bahawa Alice, nama A, hanya akan diindeks ke 0.
Dan Bob, nama B, akan diindeks ke 1, dan sebagainya.
Jadi kita mempunyai pemetaan antara input, yang tali, dan hash
lokasi, yang nombor.
>> Jadi proses yang secara amnya dikenali sebagai fungsi hash, dan anda boleh benar-benar
melaksanakannya dalam kod.
Jika saya mahu untuk melaksanakan fungsi hash yang tidak betul-betul apa yang kita
hanya diterangkan dari masa lalu, saya mungkin mengisytiharkan fungsi yang diperlukan, sebagai
input misalnya -
dan mari kita melakukan ini pada ini skrin di sini.
Jika saya mahu melaksanakan hash fungsi, saya mungkin berkata
sesuatu seperti ini.
>> Ia akan kembali int an.
Ia akan dipanggil hash, dan ia akan menerima sebagai hujah yang
tali, atau kita boleh menjadi lebih betul sekarang, dan berkata char *, kami akan memanggilnya s.
Dan kemudian semua fungsi ini telah lakukan, akhirnya, adalah kembali int an.
Sekarang, bagaimana ia yang mungkin tidak begitu jelas.
Saya akan melaksanakan ini tanpa apa-apa membentuk kesilapan memeriksa sekarang.
Saya hanya akan buta berkata, kembali apa yang ada pada s kurungan 0, tolak,
katakan, modal koma bertitik A.
>> Benar-benar rosak.
Ia tidak sempurna kerana satu, bagaimana jika s adalah batal?
Perkara-perkara buruk yang akan berlaku.
Kedua, apa yang jika huruf yang pertama dalam nama bukan huruf besar?
Itu tidak akan berubah dengan baik sama ada.
Ia mungkin menjadi huruf kecil atau tidak surat pada semua.
Jadi benar-benar ruang untuk penambahbaikan di sini, tetapi ini adalah idea asas.
>> Apa yang kita diterangkan minggu lepas secara lisan sebagai hanya satu proses pemetaan Alice untuk
0 dan Bob 1 boleh dinyatakan pastinya lebih formulaically sebagai C
berfungsi di sini.
Dipanggil lagi hash, mengambil tali sebagai input, dan kemudian entah bagaimana melakukan sesuatu
dengan input untuk menghasilkan output.
Tidak seperti Penerangan kotak hitam kami yang kita telah lama dilakukan.
Saya tidak tahu bagaimana ini mungkin bekerja di bawah hood.
>> Untuk set masalah 6, salah satu cabaran adalah untuk anda untuk memutuskan apa yang
fungsi hash anda akan?
Apa yang akan menjadi bahagian dalam yang hitam kotak, dan mungkin, ia akan menjadi
sedikit lebih menarik daripada ini, dan pasti lebih terdedah kepada kesilapan
memeriksa daripada ini tertentu pelaksanaan.
>> Tetapi masalah boleh timbul, bukan?
Jika kita mempunyai struktur data seperti ini satu, apa yang salah satu masalah
anda boleh menghadapi masa ke masa sebagai anda memasukkan lebih banyak nama-nama ke
jadual hash?
Anda mendapat perlanggaran, bukan?
Bagaimana jika anda mempunyai Alice dan Harun, dua orang yang nama mereka berlaku
bermula dengan A?
Yang menimbulkan persoalan, di mana anda meletakkan kedua seperti nama A?
>> Nah, anda mungkin naif hanya meletakkan ia di mana Bob milik, tetapi kemudian Bob
jenis diskru jika anda cuba untuk memasukkan nama beliau akan datang dan
tidak ada ruang untuk beliau.
Jadi, anda mungkin meletakkan Bob di mana Charlie adalah, dan anda boleh bayangkan ini sangat cepat
devolving ke dalam sedikit kacau-bilau.
Sesuatu linear pada akhirnya, di mana anda hanya perlu untuk mencari segala-galanya
mencari Alice atau Bob atau Harun atau Charlie.
>> Jadi, kami mencadangkan, bukan hanya linear menyelesaikan sesuatu kawasan lapang
dan plopping nama-nama di sana, kami mencadangkan pendekatan yang penjaga.
Satu jadual hash masih dilaksanakan dengan pelbagai indeks, tetapi jenis data
mereka kini adalah indeks petunjuk.
Petunjuk untuk apa?
Petunjuk untuk senarai berkaitan.
>> Kerana ingat bahawa senarai yang dikaitkan adalah benar-benar hanya penunjuk kepada nod, dan
nod mempunyai bidang yang akan datang, dan nod yang mempunyai bidang yang akan datang, dan sebagainya.
Jadi, anda kini boleh memikirkan pelbagai ini pada sebelah kiri jadual hash sebagai
membawa kepada senarai yang berkaitan.
Kelebihan yang jika anda mendapat pertembungan antara Alice dan Harun,
apa yang anda lakukan dengan orang kedua seperti itu?
Anda hanya melampirkan kepadanya untuk yang akhir, malah awal
senarai yang berkaitan.
>> Dan sebenarnya, mari kita hanya mi melalui yang hanya kedua.
Di mana akan masuk akal yang paling?
Jika saya memasukkan Alice dan dia berakhir di lokasi pertama, maka saya cuba untuk
memasukkan nama Harun, dan ada jelas perlanggaran, saya perlu meletakkan
beliau pada mulanya senarai dikaitkan?
Itulah di lokasi yang pertama, atau pada akhir?
>> PENONTON: [didengar].
>> DAVID MALAN: OK.
Saya dengar bermula.
Mengapa pada permulaan?
>> PENONTON: [didengar].
>> DAVID MALAN: OK.
Ia abjad, supaya baik.
Itulah harta yang baik.
Ia akan menyelamatkan saya sedikit masa yang mungkin.
Ia tidak akan membiarkan saya melakukan carian binari, tetapi saya mungkin sekurang-kurangnya dapat keluar
gelung jika saya sedar, baik, saya cara lepas adalah Harun akan berada di dalam ini
disusun senarai berkaitan.
Saya tidak perlu membuang masa saya mencari sepanjang jalan ke akhir.
Jadi itulah yang munasabah.
Mengapa lagi anda mungkin mahu untuk memasukkan nama berlanggar di
awal senarai?
Apa itu?
>> PENONTON: [didengar].
>> DAVID MALAN: Ia boleh mengambil masa yang lama untuk sampai ke akhir senarai.
Dan sebenarnya, lagi dan lagi.
Lebih banyak nama-nama yang anda memasukkan bermula dengan A, yang lebih panjang
rantaian akan mendapatkan.
Semakin lama yang dikaitkan senarai akan mendapatkan.
Jadi anda benar-benar hanya membuang masa anda.
Mungkin anda lebih baik mengekalkan masa kemasukan berterusan, besar O 1,
dengan sentiasa meletakkan nama berlanggar di permulaan senarai berkaitan,
dan tidak perlu bimbang kerana banyak tentang sorting.
>> Apakah jawapan yang terbaik?
Ia adalah tidak jelas.
Ia jenis bergantung kepada apa yang pengedaran, apa corak adalah
nama-nama yang anda memasukkan.
Ia tidak semestinya jawapan yang jelas.
Tetapi di sini untuk, sekali lagi, adalah peluang reka bentuk.
>> Jadi kita kemudian melihat perkara ini, yang adalah benar-benar peluang besar lain
untuk p-set 6.
Dan sedar, jika anda tidak mempunyai sudah, Zamyla selam ke dalam kedua-dua, hash
jadual dan cuba, dengan lebih terperinci.
Dan Walkthrough video tertanam dalam p-set spec.
Ini adalah indone a -
T-R-I-E. Dan apa yang menarik tentang ini adalah bahawa masa berjalan
mencari nama, seperti Maxwell Kali terakhir, adalah besar O apa?
Apa itu?
>> PENONTON: Bilangan huruf.
>> DAVID MALAN Bilangan huruf.
Saya mendengar dua perkara.
Bilangan surat dan masa yang berterusan.
Jadi mari kita pergi dengan yang pertama.
Bilangan huruf.
Nah, struktur data ini, ingat, adalah seperti pokok, pokok keluarga, setiap
nod yang terdiri daripada tatasusunan.
Dan orang-orang barisan adalah petunjuk untuk nod lain itu, atau lain-lain seperti
array di pokok itu.
>> Jadi, jika kita mahu kemudian menentukan sama ada Maxwell adalah di sini, saya boleh pergi
kepada pelbagai pertama, di bahagian paling atas pokok, akar yang kononnya, atas
indone, dan kemudian ikut penunjuk m, maka penunjuk, maka x,
w, e, l, l.
Dan kemudian apabila saya melihat beberapa simbol khas, ditandakan di sini sebagai segi tiga.
Dalam kod anda akan melihat kami mencadangkan bahawa anda dilaksanakan sebagai bool, hanya berkata ya
atau tidak, perkataan berhenti di sini.
>> Nah, sebaik sahaja kami telah pergi ke M-A-X-W-E-L-L, rasanya tujuh, mungkin
lapan jika kita pergi satu masa lalu itu, lapan langkah-langkah untuk mencari Maxwell.
Atau mari kita memanggilnya K. Tetapi ingat lepas masa, saya berpendapat bahawa jika ada
realistik panjang maksimum pada perkataan, seperti watak-watak 40-beberapa-ganjil, yang
maksimum panjang membayangkan nilai yang berterusan.
Jadi benar-benar, ya, ia adalah O teknikal besar 8 atau 7, atau benar-benar besar O K. Tetapi
jika ada topi terbatas kepada apa yang K boleh, ia adalah tetap.
Dan supaya ia besar O 1 pada akhir hari.
>> Tidak dalam dunia sebenar.
Tidak apabila anda sebenarnya mula menonton jam anda sebagai menjalankan program anda.
Ia benar-benar akan menjadi sedikit lebih perlahan daripada yang benar-benar berterusan
masa dengan satu langkah.
Ia akan menjadi tujuh atau lapan langkah-langkah, tetapi masih yang jauh, jauh lebih baik
daripada algoritma seperti besar O n yang bergantung kepada saiz apa yang di
struktur data.
>> Notis terbalik di sini ialah kita boleh memasukkan satu juta nama lagi ke ini
struktur data, tetapi berapa banyak lagi langkah-langkah yang ia akan membawa kita untuk mencari
Maxwell dalam kes itu?
Tiada.
Dia tidak terjejas.
Dan sehingga kini, saya tidak fikir kita telah melihat contoh struktur data atau
algoritma yang benar-benar terjejas oleh luar
tingkah laku seperti itu.
Tetapi ini tidak boleh menjadi yang menakjubkan.
Ini tidak boleh menjadi satu-satunya penyelesaian untuk p-set
>> Dan ia tidak.
Ini tidak semestinya data struktur yang perlu anda tertarik kepada,
kerana seperti jadual hash, kompromi.
Apakah harga yang anda bayar di sini?
Ingatan.
Maksud saya, ini adalah satu kejam Jumlah ingatan.
Dan anda tidak boleh agak lihat di sini kerana pengarang gambar ini
jelas dipenggal semua array, dan kami tidak melihat banyak A dan
B dan C dan Q dan Y itu dan ini Z dalam tatasusunan.
Tetapi mereka berada di sana.
>> Setiap nod ini adalah pelbagai keseluruhan beberapa 26 atau lebih bait, setiap
yang mewakili surat.
27 dalam kes ini, supaya kita boleh menyokong apostrofi dalam set masalah.
Jadi struktur data ini adalah benar-benar, benar-benar tebal dan lebar.
Dan itu sahaja mungkin berakhir dengan perlahan perkara ke bawah, atau sekurang-kurangnya berharga anda
lebih banyak ruang.
Tetapi sekali lagi, kita boleh membuat perbandingan di sini.
>> Ingat manakala belakang, kita mencapai banyak masa berjalan lebih menarik dalam menyusun
apabila kita menggunakan merge jenis, tetapi harga kita dibayar untuk mencapai n log n untuk merge
apapun yang dikehendaki yang kita belanjakan lebih apa sumber?
Lebih banyak ruang.
Kami memerlukan pelbagai menengah menyalin orang ke dalam, seperti
yang kami lakukan di sini di atas pentas.
Jadi sekali lagi, ada pemenang yang jelas, tetapi hanya reka bentuk subjektif
keputusan dibuat.
>> Baiklah.
Jadi bagaimana tentang perkara ini?
Sesiapa yang mengenali D-Dewan?
OK.
Jadi kami bertiga lakukan.
Mather House.
Jadi ini adalah untuk makan Mather ini.
Saya rasa semua dewan makan mempunyai susunan dulang seperti ini.
Dan ini adalah benar-benar wakil sesuatu yang kita telah
jelas dilihat sudah.
Kami menyeru ia benar-benar timbunan.
Dan timbunan, dari segi anda memori komputer, di mana data pergi
manakala fungsi dipanggil.
>> Sebagai contoh, apa jenis perkara yang pergi pada timbunan berkenaan dengan
susun atur memori yang kita telah dibincangkan dalam beberapa minggu yang lalu?
Apa itu?
>> PENONTON: Panggilan ke fungsi.
>> DAVID MALAN: Saya minta maaf.
>> PENONTON: Panggilan ke fungsi.
>> DAVID MALAN: Panggilan ke fungsi, tetapi khusus, apa yang di dalam setiap
mereka bingkai?
Apakah jenis perkara?
Yeah.
Jadi pembolehubah tempatan.
Bila-bila masa kita perlu ada simpanan tempatan, seperti hujah, atau int saya, atau int
suhu, atau apa sahaja tempatan ubah, kita telah
meletakkan bahawa dalam timbunan.
Dan kita panggil ia timbunan kerana itu idea lapisan.
Hanya jenis perlawanan dengan realiti, konsep tersebut.
>> Tetapi ternyata bahawa timbunan juga boleh dilihat sebagai satu struktur data,
alternatif kepada array, alternatif untuk senarai yang berkaitan.
Sesuatu konsep yang lebih menarik yang masih boleh
dilaksanakan dengan menggunakan salah satu daripada orang-orang perkara, tetapi ia adalah jenis yang berbeza
struktur data sokongan, benar-benar, hanya dua operasi.
Tetapi, anda boleh menambah penjaga ciri-ciri daripada ini.
Tetapi ini adalah asas -
menolak dan pop.
>> Dan idea dengan timbunan adalah bahawa jika saya ada di sini, dengan atau tanpa Annenberg
mengetahui, dulang dari sebelah dengan nombor 9 di atasnya.
Jadi hanya int an.
Dan saya mahu untuk menolak ini ke data struktur, yang kini kosong.
Pertimbangkan ini bahagian bawah timbunan.
Saya akan menolak jumlah ini 9 ke timbunan, dan kini ia di sana.
>> Tetapi perkara yang menarik tentang timbunan adalah bahawa jika saya kini mahu untuk menolak
beberapa nilai lain, seperti 17, dan saya menolak ini ke tepi, saya akan melakukan
satu-satunya perkara intuitif, saya hanya akan untuk meletakkan ia tepat di mana kita manusia
akan cenderung untuk meletakkan ia, di atas.
Tetapi apa yang menarik kini ialah, bagaimana saya boleh mendapatkan sekurang-9?
Anda tahu, saya tidak tanpa usaha beberapa.
>> Jadi apa yang menarik tentang timbunan ialah dengan reka bentuk,
ia adalah satu struktur data LIFO.
Cara bodoh untuk menggambarkan terakhir dalam, mula-mula keluar.
Jadi nombor terakhir dalam pada masa ini adalah 17.
Jadi jika saya mahu pop sesuatu dari tepi, ia hanya boleh menjadi 17.
Jadi ada suatu perintah mandatori operasi di sini, di mana item yang lalu
dalam telah menjadi salah satu yang pertama keluar.
Oleh itu singkatan, LIFO.
>> Jadi mengapa ini mungkin berguna?
Adakah mereka dalam konteks yang anda lebih mahu struktur data yang seperti ini?
Nah, ia sememangnya menjadi berguna di dalam komputer.
Jadi sistem beroperasi dengan jelas menggunakan ini jenis struktur data untuk susunan.
Kita juga akan melihat idea yang sama apabila ia datang ke laman web.
Jadi minggu ini dan minggu depan dan seterusnya, dan seperti yang anda mula melaksanakan web
halaman dalam bahasa yang dikenali sebagai HTML, anda boleh sebenarnya menggunakan struktur data seperti
ini untuk menentukan jika halaman adalah diformat dengan betul.
Kerana kita akan melihat semua laman web ikuti sejenis hierarki, lekukan sesuatu
yang akan, pada akhir hari, menjadi struktur pokok di bawah hood.
Jadi lebih pada itu dalam hanya sedikit.
>> Tetapi untuk sekarang, mari kita mencadangkan untuk masa, bagaimana kita boleh pergi kira-kira
mewakili apa timbunan itu?
Biar saya mencadangkan supaya kita melaksanakan timbunan dengan kod seperti ini.
Jadi timbunan akan mempunyai di dalamnya dua perkara, array, yang dipanggil dulang,
hanya untuk menjadi selaras dengan demo.
Dan setiap item dalam array yang akan menjadi int jenis.
Dan kapasiti mungkin apa?
Kerana saya tidak bertulis definisi penuh di sini.
>> Ia mungkin maksimum saiz array.
Dan ia mungkin diisytiharkan sebagai tajam menentukan di bahagian atas fail, beberapa
jenis yang berterusan seperti yang dibayangkan oleh permodalan semata-mata.
Jadi tempat keupayaan ditakrifkan sebagai saiz maksimum.
Sementara itu, di dalam struktur data dikenali sebagai timbunan ada akan
menjadi integer hanya dikenali hanya sebagai saiz.
>> Jadi, jika saya adalah untuk mewakili ini sekarang bergambar, mari kita andaikan bahawa ini
kotak hitam mewakili seluruh timbunan saya.
Di dalam ia adalah dua pembolehubah.
Jadi saya akan untuk menarik Yang pertama seperti saiz.
Dan yang kedua saya akan untuk menarik sebagai array.
>> Tetapi hanya untuk menjaga perkara-perkara yang teratur, biasanya saya akan menarik array seperti
ini, tetapi ia jenis nice jika kita sepadan dengan realiti, atau
perlawanan model mental.
Jadi biarlah saya bukannya membuat pelbagai menegak, yang hanya, sekali lagi,
rendition artis.
Adakah benar-benar perkara apa yang ia adalah di bawah hood.
Dan kita akan mengatakan bahawa, secara lalai, kapasiti akan menjadi tiga.
Jadi ini akan menjadi lokasi 0, ini akan menjadi lokasi 1, ini
akan menjadi lokasi 2.
>> Jika saya rasuah dengan bola tekanan, akan orang suka datang dan menjalankan
menaiki di sini untuk seketika?
OK, menyaksikan tangan pertama.
Ayuh up.
Baiklah.
Jadi saya percaya ia adalah Steven.
Ayuh up.
Baiklah.
>> Tetapi sekarang kita andaikan memundurkan untuk permulaan keadaan dunia di mana saya
baru sahaja mengisytiharkan timbunan, dan ia akan menjadi kapasiti tiga.
Tetapi saiz masih belum ditentukan.
Dulang belum ditentukan.
Jadi beberapa soalan pertama.
Dan biarlah saya memberikan mikrofon supaya anda boleh mengambil bahagian secara lebih aktif dalam hal ini.
>> Jadi apa yang ada di dalam saiz pada masa ini dalam masa jika semua yang saya lakukan adalah
diisytiharkan timbunan dengan satu baris kod?
>> STEVEN: Not much.
>> DAVID MALAN: OK, tidak banyak.
Adakah kita tahu apa yang di dalam saiz, adakah kita tahu apa yang di dalam
array ini di sini?
>> STEVEN: Hanya kod rawak, bukan?
Just -
>> DAVID MALAN: Ya, saya akan memanggilnya kod, tetapi rawak -
>> STEVEN: Perkara.
>> DAVID MALAN: Perkara seperti rawak
>> STEVEN: Bit.
>> DAVID MALAN: Bits, bukan?
Jadi nilai sampah, bukan?
Jadi pilih atur ini 0 dan 1 ini.
Sisa-sisa kelaziman sebelumnya memori ini.
Dan kita tidak benar-benar tahu apa nilai-nilai adalah, jadi kita biasanya menarik mereka
sebagai tanda tanya.
>> Jadi perkara pertama yang kita mungkin akan mahu lakukan di sini -
dan biarlah saya memberikan bidang ini di dalam dari sana nama - dulang.
Apa yang perlu kita mungkin memulakan saiz jika kita mahu
mula menggunakan timbunan ini?
>> STEVEN: Dulang adalah sub 3.
>> DAVID MALAN: Jadi, OK.
Untuk menjadi jelas, kapasiti diisytiharkan tempat lain seperti tiga.
Dan itulah yang saya telah menggunakan memperuntukkan array.
Saiz akan merujuk kepada berapa banyak dulang kini pada timbunan.
>> STEVEN: Zero.
>> DAVID MALAN: Jadi ia perlu sifar.
Oleh itu, pergilah ke hadapan, dan dengan mana-mana jari, menarik sifar dalam saiz.
Baiklah.
Jadi sekarang, apa yang di dalam ini di sini, kami tidak tahu.
Ini adalah benar-benar nilai-nilai sampah sahaja.
Oleh itu, kita boleh menarik tanda tanya, tetapi mari kita menyimpan lembaga bersih kini
kerana ia tidak kira apa yang ada.
Kita tidak perlu untuk memulakan pelbagai apa-apa, kerana jika kita tahu bahawa
saiz timbunan adalah sifar, baik, kami tidak perlu melihat apa-apa dalam
pelbagai ini pula di masa ini.
>> Jadi sekarang menganggap bahawa saya menolak nombor 9 ke dalam tindanan.
Bagaimana kita harus mengemas kini struktur data dalam kotak hitam ini?
Apakah nilai-nilai yang perlu berubah?
>> STEVEN: Dalam -
saiz?
>> DAVID MALAN: OK.
Saiz harus menjadi apa?
>> STEVEN: Saiz akan menjadi salah.
>> DAVID MALAN: OK.
Jadi saiz harus menjadi satu.
Jadi, anda boleh melakukan ini dalam beberapa cara.
Biar saya memberi anda, kini anda jari adalah pemadam.
Baiklah.
Maka sekarang jari anda berus.
Baiklah.
Dan kini apa lagi yang telah berubah, jelas, dalam struktur data?
>> STEVEN: Kami pergi dari bawah ke atas hingga 9.
>> DAVID MALAN: 9.
OK, yang baik.
Jadi masih tidak kira apa yang di lokasi satu atau dua kerana mereka
nilai-nilai sampah, tetapi kita tidak perlu bersusah payah mencari di sana kerana saiz adalah
memberitahu kita bahawa hanya Elemen pertama sebenarnya yang sah.
Jadi sekarang saya menolak 17 ke senarai.
Apa yang berlaku kepada gambar ini?
>> STEVEN: Jadi saiz akan pergi ke dua.
>> DAVID MALAN: OK.
Anda pemadam -
oops.
Anda pemadam.
>> STEVEN: Pemadam.
>> DAVID MALAN: Anda berus.
>> STEVEN: Brush.
>> DAVID MALAN: OK.
Dan apa lagi?
>> STEVEN: Dan kemudian kita -
>> DAVID MALAN: Kami menolak 17.
>> STEVEN: Kami berpegang 17 di atas, jadi -
>> DAVID MALAN: OK, baik.
>> STEVEN: - jatuh ke bawah.
>> DAVID MALAN: Baiklah.
Ia semakin mudah.
Saya tidak akan membantu anda masa ini.
Tolak 22.
>> STEVEN: Selesai.
Menjadi pemadam.
Saya menjadi berus.
Dan kemudian saya meletakkan 22.
>> DAVID MALAN: 22.
Excellent.
Jadi sekali lagi.
Saya kini akan menolak ke timbunan 26.
>> STEVEN: Ooh.
Oh cuilah.
Anda benar-benar ditangkap saya tidak bersedia.
>> DAVID MALAN: Anda tidak melihat ini datang?
>> STEVEN: Saya tidak melihat ini akan datang.
Bolehkah kita keupayaan semula awal?
>> DAVID MALAN: Itu satu soalan yang baik.
Jadi kami jenis dicat diri di satu sudut di sini.
Ada benar-benar tidak keluar baik untuk Steven kerana kita telah memperuntukkan pelbagai ini
statik, jadi untuk bercakap, di dalam struktur data.
Dan kita telah dikodkan dasarnya keras ia menjadi saiz tiga.
Jadi kita tidak boleh benar-benar mengagihkan semula ia.
>> Kita boleh jika kita kembali, kami ditakrifkan semula dulang untuk menjadi penunjuk bahawa
kita kemudian gunakan malloc ke memori tangan untuk.
Kerana jika kita mendapat memori daripada timbunan melalui malloc, kita
kemudian boleh membebaskannya.
Tetapi sebelum membebaskan, kita boleh mengagihkan semula sebahagian yang lebih besar memori,
mengemaskini penunjuk, dan sebagainya.
Tetapi untuk sekarang, ini adalah benar-benar yang terbaik yang boleh kita lakukan.
Menolak dan pop yang mungkin akan perlu menunjukkan sedikit kesilapan.
>> Jadi untuk contoh, pelaksanaan kami daripada usaha boleh mengembalikan bool yang
sebelum kembali benar, benar, benar.
Tetapi kali keempat, ia akan mempunyai untuk kembali palsu, misalnya.
Baiklah.
Sangat baik dilakukan.
Tahniah.
Anda telah memperoleh bola tekanan anda hari ini.
>> [Tepuk tangan]
>> STEVEN: Terima kasih.
>> DAVID MALAN: Terima kasih.
OK, jadi ini seolah-olah tidak banyak satu langkah ke hadapan, bukan?
Kami diterangkan struktur data ini.
Ia adalah menarik, bukan?
Sistem operasi seperti itu.
Rupa-rupanya web boleh menggunakan ini, dan aplikasi lain masih.
Tetapi apa yang had bodoh yang kami kembali ke jenis dua minggu had
di mana kita telah ditetapkan array saiz.
>> Jadi memang ada beberapa cara kita boleh menyelesaikan masalah ini.
Kami dinamik boleh memperuntukkan pelbagai, bukan dengan keras kod kerana saya telah
dilakukan di sini, tetapi sebaliknya-mengisytiharkan semula ini, hanya perlu jelas, sebagai
sesuatu seperti ini.
* Dulang Int, tidak membuat keputusan atas kapasiti yet.
Tetapi apabila saya mengisytiharkan timbunan di tempat lain dalam kod saya, maka saya boleh memanggil malloc,
mendapatkan alamat sebahagian daripada ingatan, dan saya boleh memberikan
alamat untuk dulang.
>> Dan kemudian, kerana ia hanya sebahagian daripada ingatan, saya boleh terus menggunakan persegi
notasi kurungan dalam cara yang biasa.
Kerana sekali lagi, ada jenis ini bersamaan fungsi tatasusunan dan
ketulan memori yang datang kembali dari malloc.
Kita boleh merawat satu dengan yang lain menggunakan aritmetik penunjuk atau
notasi kurungan persegi.
Jadi itulah satu pendekatan.
>> Tetapi bagaimana lagi kita boleh melaksanakan ini struktur data yang sama, yang berpotensi?
Betul?
Saya rasa seperti kita ini diselesaikan masalah seperti minggu lalu.
Apakah penyelesaian kepada masalah ini bahawa Steven berlari ke?
Senarai Jadi dikaitkan, betul.
>> Jika masalah ini ialah bahawa kita lukisan diri kita ke satu sudut dengan memperuntukkan
terlebih dahulu memori yang terlalu kecil yang kita kemudian telah entah bagaimana berurusan dengan, baik,
mengapa tidak hanya mengelakkan bahawa mengeluarkan sama sekali?
Mengapa tidak hanya mengisytiharkan dulang untuk menjadi penunjuk kepada nod, ergo senarai berkaitan,
dan kemudian hanya memperuntukkan nod baru setiap kali Steven diperlukan untuk dimuatkan
nombor ke dalam struktur data.
>> Jadi gambar tersebut akan perlu berubah.
Ia tidak akan menjadi seperti yang bersih dan sebagai semudah hanya pelbagai tiga Ints.
Kini ia akan menjadi penunjuk kepada struct, dan struct yang akan
mempunyai int dan penunjuk akan datang.
Ia akan membawa melalui penunjuk bahawa yang lain struct itu
lain struct itu.
Jadi gambar yang akan benar-benar mendapatkan Messier bit.
Dan kita telah mengikat anak panah semua bersama-sama.
>> Tetapi itu halus, betul, kerana kita telah melihat bagaimana untuk melakukan ini.
Dan apabila anda mendapatkan selesa melaksanakan sesuatu seperti berkaitan
senarai, yang anda perlu lakukan jika anda memilih untuk melaksanakan jadual hash dengan
chaining berasingan untuk p-set 6, anda boleh menggunakannya sebagai blok bangunan, atau
bahan, atau dalam Scratch bercakap, satu prosedur, sesuatu yang anda meletakkan, anda
mencipta sekeping teka-teki anda sendiri bahawa anda boleh menggunakan semula.
Melepas begitu, tetapi penyelesaian yang berpotensi bahawa kita telah benar-benar dilihat sebelum ini.
>> Jadi agak kerap, anda lihat ini setiap atau dua tahun apabila Apple siaran
sesuatu yang baru, dan semua orang gila beratur di luar Apple
menyimpan untuk membeli kecil mereka menaik taraf pada perkakasan.
Saya katakan ini, ia adalah OK, kerana Saya salah seorang daripada orang-orang.
Jadi apa jenis struktur data mungkin mewakili realiti ini?
>> Nah, mari kita memanggil ia satu barisan, satu barisan.
Jadi British akan memanggil ia biasanya beratur anyway, jadi ia nama yang bagus.
Dan kedua-dua operasi yang beratur akan menyokong kami akan memanggil enqueue a
operasi dan operasi dequeue, yang serupa dalam
semangat untuk menolak dan pop.
Ia hanya jenis yang berbeza dalam konvensyen, apa yang kita memanggil ini.
Tetapi untuk enqueue sesuatu yang bermakna untuk menambah atau memasukkan kepada struktur data.
Untuk dequeue bermakna untuk mengeluarkannya.
Tetapi manakala timbunan adalah data yang LIFO struktur, beratur adalah dalam pertama,
pertama daripada struktur data.
>> Jika anda adalah orang yang pertama dalam talian, anda akan menjadi orang yang pertama untuk mendapatkan
keluar dari barisan dan membeli peranti baru anda.
Bayangkan bagaimana perut orang-orang ini akan menjadi jika Apple sebaliknya digunakan timbunan, untuk
contoh, untuk melaksanakan memetik daripada mainan baru anda.
Jadi beratur masuk akal, sudah tentu, dan kita boleh berfikir semua jenis
aplikasi, mungkin, untuk beratur, terutama apabila anda mahu keadilan.
Jadi bagaimana kita boleh melaksanakan ini sebagai struktur data?
>> Well, saya mencadangkan supaya kita mungkin perlu melakukannya dengan cara ini.
Jadi saya akan kini mempunyai nombor.
Oleh itu, kita akan memastikan ia mudah dan tidak semestinya bercakap dari segi dulang.
Hanya nombor yang rakyat mendapat.
Kapasiti akan, sekali lagi, menetapkan jumlah bilangan orang-orang yang boleh di
baris ini, seperti tiga atau apa nilai lain.
>> Tetapi saya mencadangkan bahawa saya perlu untuk mengesan bukan sahaja saiz
beratur, berapa banyak perkara-perkara yang di dalamnya.
Jadi saiz adalah saiz semasa, kapasiti adalah saiz maksimum.
Hanya sekali lagi, tatanama oleh konvensyen.
Kenapa saya perlu int tambahan di dalam satu barisan untuk mengesan yang dalam
hadapan baris?
Kenapa saya perlu untuk berbuat demikian dalam kes ini?
>> Nah, bagaimana gambar ini akan berubah?
Saya mungkin boleh menggunakan semula yang paling gambar ini.
Biar saya pergi ke hadapan dan memadam apa yang di sini.
Kami akan memberikan ini yang sedikit nama yang berbeza di sini.
Mari kita menghilangkan 17, mari kita menghilangkan daripada 9, mari kita menghilangkan 3.
Dan mari kita menambah satu perkara yang lain.
Saya mencadangkan bahawa saya perlu untuk mengesan hadapan senarai, yang hanya
akan menjadi int an juga.
Dan kita akan pastikan ia mudah.
Tiada senarai dikaitkan buat masa sekarang.
>> Kami akan mengakui bahawa kita akan benjolan sehingga terhadap had ini.
Tetapi apa yang saya mahu melihat berlaku pada masa ini?
Jadi rasa saya pergi ke hadapan dan yang pertama orang yang datang dalam talian, dan
ia adalah nombor 9.
Kami mempunyai bola tekanan.
Bolehkah saya mencuri, berkata, dua atau tiga orang?
Satu, dua, tiga?
Ayuh up.
Hak dari depan, kerana kami akan membuat satu ini cepat.
>> Setiap satu daripada anda kini akan menjadi seorang budak peminat dalam talian di Apple.
Anda tidak akan menerima perkakasan Apple pada akhir walaupun ini.
Baiklah.
Jadi anda nombor 9, anda nombor 17, nombor 22.
Ini adalah nombor sewenang-wenangnya, seperti ID pelajar atau barang kecil.
Dan hanya seketika, mari kita mulakan untuk mula menambah perkara.
Dan saya akan berjalan lembaga di sini kali ini.
>> Jadi dalam kes ini, saya telah dimulakan hadapan supaya menjadi -
Saya sebenarnya tidak benar-benar peduli apa yang depan, kerana saiz adalah sifar.
Jadi ini mungkin juga hanya menjadi tanda tanya.
Ini semua adalah tanda tanya.
Jadi sekarang kita akan mula untuk benar-benar melihat beberapa orang beratur di kedai.
>> Jadi, jika nombor 9, anda yang pertama di sana pada 05:00, teruskan dan beratur,
atau malam sebelum.
OK.
Jadi sekarang 9 di sini.
Jadi 9 adalah di hadapan senarai.
Jadi, saya akan pergi ke hadapan dan mengemaskini saiz data ini semasa
struktur tidak 0 lagi, tetapi untuk menjadi 1.
Saya akan meletakkan di 9 hadapan senarai.
Biar saya pergi ke hadapan dan bertukar-tukar skrin supaya kita boleh melihat masa lalu kami di sini.
>> Dan kini apa yang saya mahu untuk meletakkan di hadapan?
Saya akan mengesan bahawa hadapan barisan sekarang
adalah di lokasi 0.
Kerana apa yang akan datang akan berlaku?
Nah, sekarang saya rasa enqueue 17 juga.
Jadi melompat dalam talian di sana.
Dan sekali lagi, jenis pintu kepada kedai akan berada di sini.
Jadi sekarang saya telah menambah 17.
Dan walaupun lelaki ini telah menyekat skrin, itu OK,
kerana kita boleh lihat di sini.
Maaf.
>> PENONTON: Kita boleh bergerak -
>> DAVID MALAN: Tidak, itu OK.
Ia besar di sana.
Jadi 17 kini dalam barisan.
Saya perlu mengemaskinikan yang bidang kini walaupun?
OK, pasti saiz.
Dan bagaimana pula depan?
OK, tidak.
Hadapan tidak berubah, kerana tidak seperti timbunan, kita
mahu mengekalkan keadilan.
Jadi, jika 9 datang pertama, kami mahu 9 akan keluar pertama baris
dan ke dalam kedai.
>> Malah, mari kita lihat itu.
Sebelum kita memasukkan 22, mari kita teruskan dan dequeue 9.
Apa nama anda lagi?
>> PENONTON: Jake.
>> DAVID MALAN: Jake akan untuk dequeued sekarang.
Jadi anda boleh berjalan kaki ke kedai.
Dan berpura-pura bahawa kedai ada di sana.
Jadi sekarang apa yang perlu - dit-dit-dit!
Apa yang perlu berlaku sekarang?
Keputusan reka bentuk.
Jadi tidak naluri buruk, tetapi - apa nama anda lagi?
>> PENONTON: David.
>> DAVID MALAN: David.
Jadi apakah Nabi Daud lakukan?
Dia cuba untuk menyusun daripada menetapkan data struktur dan bergerak dari lokasi beliau
ke bekas lokasi Jake.
Dan yang baik jika kita sanggup untuk menerima bahawa sebagai
detail pelaksanaan.
Tetapi pertama, mari kita mengemas kini data struktur sebelum kita berbuat demikian.
Kerana saya tidak suka idea semua rakyat beralih di dalam bidang ini.
>> Ia tidak masalah besar jika David tidak dengan satu langkah, tetapi sekali lagi, berfikir kembali ke
apabila kita telah mempunyai lapan sukarelawan pada pentas dan kita telah dilakukan seperti memasukkan
jenis, di mana kita terpaksa bermula bergerak semua orang di sekeliling.
Yang mendapat mahal, kan?
Yang membuatkan saya merasa jijik tentang besar O n, besar O n kuasa dua lagi.
Ia tidak berasa seperti hasil yang ideal.
>> Jadi mari kita hanya mengemaskini ini.
Jadi saiz barisan tidak lagi 2.
Ia kini hanya 1.
Tetapi sekarang saya boleh mengemas kini sesuatu Saya tidak mengemas kini sebelum ini,
hadapan senarai.
Saya hanya boleh berkata, adalah lokasi yang 1?
Jadi sekarang kita mempunyai nilai sampah di sini, nilai sampah di sini, dan Daud dalam
tengah-tengah sampah ini.
Tetapi struktur data masih utuh.
>> Dan sebenarnya, saya tidak perlu menukar bekas pemain nombor Jake
9, kerana yang peduli.
Saya mempunyai maklumat yang cukup sekarang dalam saiz yang saya tahu ada satu orang
beratur ini.
Dan saya tahu bahawa orang itu adalah di lokasi 1, tidak 0.
Saya tidak mengira.
Jadi 1 juga.
Jadi struktur data masih OK.
>> Nah, apa yang berlaku seterusnya?
Mari enqueue -
apa nama anda?
>> PENONTON: Callen.
>> DAVID MALAN: Callen.
Mari kita enqueue a Callen, dan 22 kini dalam barisan.
Jadi sekarang apa yang telah berubah di sini?
Hadapan tidak akan berubah, jelas.
Saiz akan berubah menjadi 2 lagi.
Dan 22 berakhir di sini, 9 masih ada, tetapi ia berkesan yang
nilai sampah sekarang.
Ia hanya sisa Jake lalu.
>> Jadi sekarang apa yang berlaku jika Saya dequeue Daud?
Satu operasi lepas, dequeue Daud.
Kita boleh berubah, tetapi saya mencadangkan mari lakukan sebagai kerja sedikit yang mungkin.
Sekarang struktur data saya pergi menyokong saiz dari 2 kepada 1.
Tetapi hadapan barisan kini menjadi 2.
Saya tidak perlu menukar nombor-nombor sahaja lagi, kerana mereka
hanya nilai-nilai sampah.
>> Tetapi sekarang apa yang berlaku?
Katakan saya enqueue diri saya sendiri, 26?
Saya rasa seperti saya tergolong di sini.
Jadi saya sedang enqueued.
Jadi saya jenis tergolong di sini.
Dan walaupun anda tidak berapa menghargai ini visual di atas pentas,
kerana kita mempunyai banyak ruang, saya perlu tidak akan berdiri di sini, mengapa?
>> PENONTON: Anda berada di luar batas.
>> DAVID MALAN: Betul.
Saya keluar dari batas.
Saya telah diindeks di luar batas array ini.
Saya benar-benar seharusnya berada di dalam salah satu tiga lokasi mungkin.
Sekarang, mana yang paling semula jadi untuk pergi?
Saya mencadangkan kita dimanfaatkan seminggu satu helah.
Pengendali mod, peratusan.
Kerana saya teknikal berdiri di lokasi 3, tetapi saya 3 kapasiti mod,
jadi 3, tanda peratus, 3 -
kapasiti adalah 3.
Apa itu?
Apa yang selebihnya apabila anda membahagikan 3 oleh 3?
0.
>> Supaya meletakkan saya telah Jake adalah, yang sebenarnya baik.
Jadi sekarang pelaksanaan perkara ini akan
menjadi sedikit sakit kepala.
Ia benar-benar hanya satu baris sakit kepala, kod.
Tetapi sekurang-kurangnya kini terdapat sampah nilai di sini, tetapi terdapat dua
Ints sah di sini.
Dan mendakwa saya bahawa sekarang kita telah dilakukan apa yang perlu kita lakukan selagi
kita mengubah apa yang Jake nilai adalah untuk menjadi 26.
>> Kami kini mempunyai maklumat yang cukup masih untuk mengekalkan integriti
struktur data ini.
Kami masih jenis daripada nasib apabila kita mahu memasukkan empat atau lebih jumlah
unsur-unsur, tetapi saya boleh sekurang-kurangnya membuat cantik kecekapan penggunaan ini berterusan
masa, sebenarnya.
Saya tidak perlu bimbang tentang peralihan semua orang, kerana kecenderungan Daud adalah.
>> Mana-mana soalan mengenai susunan, atau barisan ini?
>> PENONTON: Apakah sebab mengapa anda memerlukan saiz supaya anda tahu
di mana untuk mempunyai seseorang?
>> DAVID MALAN: Tepat sekali.
Saya perlu tahu saiz array kerana saya perlu tahu bagaimana
banyak nilai-nilai yang sah, dan supaya saya boleh mencari di mana untuk meletakkan
orang yang akan datang.
Tepat sekali.
Saiz adalah -
sebenarnya, kami tidak mengemaskini ini.
Saya tambah diri saya 26.
Saiz adalah sekarang, bukan 1, tetapi 2.
Jadi sekarang ini memang membantu saya mencari ketua senarai, yang bukan 0, bukan
1, tetapi 2.
Hadapan senarai memang nombor 22.
Kerana dia datang pertama, jadi dia perlu dibenarkan masuk ke dalam kedai sebelum saya,
walaupun visual saya berdiri dekat dengan kedai.
>> Semua betul?
Satu pusingan tepukan untuk lelaki ini dan kami akan membiarkan mereka keluar dari sana.
>> [Tepuk tangan]
>> DAVID MALAN: Saya boleh membiarkan anda menyimpan dulang.
Kita boleh melihat apa yang berlaku jika anda mahu, tetapi mungkin tidak.
Baiklah.
Jadi apa yang sekarang bagaimana dengan kita?
Baiklah, biar saya mencadangkan bahawa terdapat beberapa struktur data yang lain kita boleh
mula menambah kepada kit alat kita yang akan sebenarnya agak, agak relevan
kita menyelam ke dalam barangan web.
Yang sekali lagi, mempunyai beberapa jenis sambungan pokok-pokok dalam bentuk
sesuatu yang dinamakan DOM, dokumen model objek.
Tetapi kita akan melihat lebih banyak yang tidak lama lagi.
>> Biar saya mencadangkan bahawa kita definitionally memanggil pokok kini apa yang anda mungkin tahu sebagai
lebih daripada pokok keluarga, di mana anda mempunyai beberapa moyang di
akar pokok itu.
A ibu pemimpin keluarga patriarki atau di bahagian paling atas pokok.
Tanpa pasangan mereka, dalam kes ini.
Tetapi sekarang kita mempunyai apa yang kita akan memanggil kanak-kanak, iaitu nod yang menggantung
off kanak-kanak itu kiri atau kanak-kanak yang betul, anak panah seperti yang digambarkan di sini.
>> Dalam erti kata lain, dalam struktur data pokok dalam komputer, pokok telah sifar
atau lebih nod.
Jika ia mempunyai sekurang-kurangnya satu nod, yang dinamakan akar.
Ia adalah perkara-perkara yang visual kami menarik di atas.
Dan simpulan bahawa, seperti mana-mana nod lain, boleh mempunyai sifar, satu, atau dua, atau tiga,
atau bagaimanapun ramai kanak-kanak yang struktur data menyokong.
Dalam kes ini, akar, menyimpan nilai satu, mempunyai dua orang anak, 2 dan 3,
jadi kita biasanya memanggil 2 kiri kanak-kanak dan 3 kanak-kanak yang betul.
>> Dan kemudian apabila kita pergi ke 5, 6, dan 7, 6 akan dipanggil anak tengah.
Jika anda mempunyai empat orang anak, ia mendapat mengelirukan.
Jadi kita berhenti menggunakan jenis yang jalan pintas secara lisan.
Tetapi ia adalah benar-benar hanya pohon keluarga.
Dan daun di sini adalah nod yang diri mereka tidak mempunyai anak.
Mereka menggantung dari bahagian bawah pokok itu.
>> Jadi bagaimana kita boleh melaksanakan pokok yang mempunyai hanya dua kanak-kanak maksima?
Kami akan memanggilnya pokok binari.
Bi lagi bermakna dua, dalam kes, seperti dengan binari.
Dan supaya ia boleh mempunyai sifar, satu, atau dua kanak-kanak maksima.
>> Saya akan mencadangkan supaya kita melaksanakan nod untuk struktur yang dengan int n,
dan kemudian dua petunjuk, satu dipanggil kiri, satu dipanggil betul.
Tetapi orang-orang yang hanya baik konvensyen sewenang-wenangnya.
Dan apa yang baik sekarang, terutamanya jika anda jenis berjuang dengan konsep
rekursi, atau berfikir bahawa ia tidak benar-benar satu penyelesaian kepada apa-apa,
terutamanya jika anda boleh kehabisan memori.
Sekarang kita bercakap tentang data struktur dan algoritma yang membolehkan
kita merentasi dan memanipulasi mereka, ternyata bahawa rekursi datang kembali
yang lebih menarik jika tidak cara yang indah.
>> Jadi ini saya mencadangkan adalah pelaksanaan daripada fungsi Cari.
Memandangkan dua input -
jadi berfikir ini sebagai kotak hitam.
Memandangkan dua input, n, int, dan satu penunjuk kepada pokok, penunjuk kepada
nod, atau benar-benar akar pokok, saya tuntutan bahawa fungsi ini boleh kembali
benar atau palsu, bahawa nilai n berada di dalam pokok ini.
>> Apa yang di dalam kotak hitam ini?
Nah, empat cawangan.
Hanya cek pertama.
Jika pokok adalah batal, hanya kembali palsu.
Jika tiada nod, tidak ada n, tidak ada nombor, hanya kembali palsu.
Jika walaupun, n, nilai yang anda sedang mencari untuk, adalah kurang daripada pokok arrow n, dan
hanya untuk menjadi jelas, apa maknanya apabila Saya menulis pokok dan kemudian anak panah
notasi, n?
Tepat sekali.
Ini bermakna bahawa dereference penunjuk dipanggil pokok.
Pergi ke sana, dan kemudian masuk ke dalam itu nod dan mendapatkan bidang yang dipanggil n.
Dan kemudian membandingkan n sebenar yang dipindahkan ke dalam Search terhadapnya.
>> Jadi, jika n adalah kurang daripada, nilai n nod dalam pokok itu sendiri, baik,
apa maksudnya?
Ini bermakna apa-apa pada pandangan pertama.
Betul?
Sama seperti apabila anda mempunyai pelbagai nilai, anda mungkin ingin memohon binari
mencari sebagai satu bentuk jurang dan menakluk.
Tetapi apa andaian yang kita perlu membuat carian binari untuk bekerja di semua
di dalam buku telefon dan contoh awal?
>> Bagaimana untuk diselesaikan.
Jadi mari kita menghalusi takrif pokok di sini tidak hanya pokok, yang boleh
mempunyai beberapa kanak-kanak.
Bukan sahaja pokok binari, yang boleh mempunyai 0, 1, 2 atau maksima.
Tetapi sebagai pokok carian binari, atau BST, yang hanya satu cara yang mewah untuk mengatakan yang
pokok binari itu bahawa setiap nod yang anak kiri, jika ada, adalah
kurang daripada nod.
Dan kanak-kanak yang betul setiap nod itu, jika ada, adalah lebih besar
daripada nod itu sendiri.
>> Jadi, dalam erti kata lain, jika anda adalah untuk menarik keluar pokok, semua nombor-nombor
seimbang dengan berhati-hati seperti ini supaya jika anda mempunyai 55 sebagai akar, 33 boleh pergi
ke kiri kerana ia kurang daripada 55 tahun.
77 boleh pergi ke kanan kerana ia adalah lebih daripada 55 tahun.
Tetapi sekarang notis, definisi yang sama, ia adalah satu definisi rekursi lisan,
telah memohon 33.
Anak kiri 33 mestilah kurang daripada itu, dan kanak-kanak yang betul 33-an, 44, mesti
lebih besar daripada itu.
>> Jadi ini adalah satu pokok carian binari, dan Saya mencadangkan, dengan menggunakan sedikit
rekursi, kini kita boleh mencari n.
Jadi, jika n adalah kurang daripada n nilai itu nod semasa, saya akan pergi
hadapan dan menyepak bola, jadi untuk bercakap, dan hanya kembali apa sahaja jawapannya adalah
mencari n pada anak kiri pokok itu.
Perhatikan lagi, fungsi ini hanya menjangka bintang nod, yang
penunjuk kepada nod.
Jadi sesungguhnya aku hanya boleh melakukan pokok panah kiri, yang akan membawa
saya ke nod yang lain.
Tetapi apa yang nod itu?
>> Nah, menurut pengisytiharan ini, kiri hanya penunjuk, supaya hanya
bermakna saya berpindah kepada fungsi carian penunjuk yang berbeza, iaitu
satu yang mewakili anak pokok kiri saya.
Jadi dalam kes ini, penunjuk kepada 33, jika ini adalah input sampel kami Sementara itu, jika
n lebih besar daripada n nilai di nod semasa di pokok itu, maka saya
akan pergi ke hadapan dan menyepak bola di lain-lain arahan dan hanya berkata, saya tidak
tahu jika ini n nilai adalah di pokok itu, tetapi saya tahu jika ia adalah, ia turun saya
cawangan yang betul, jadi untuk bercakap.
Jadi biarlah saya panggilan rekursif mencari, lulus n satu lagi, tetapi lulus dalam
penunjuk kepada kanak-kanak kanan saya.
>> Dalam erti kata lain, jika saya kini pada 55 dan saya mencari untuk 99, saya tahu bahawa 99
adalah lebih besar daripada 55, jadi hanya seperti saya mengoyakkan minggu-minggu buku telefon yang lalu dan kita
pergi kanan, begitu juga kita akan pergi di sini.
Dan saya tidak tahu jika ia di sebelah kanan saya kanak-kanak, dan ia tidak, 77 ada, tetapi
Saya tahu ia adalah ke arah itu.
Jadi saya menyeru carian pada anak kanan saya, 77, dan membiarkan angka carian dari
jika terdapat 99 dalam sewenang-wenangnya contoh adalah sebenarnya di sana.
>> Yang lain, apa yang mana-mana yang terakhir?
Jika pokok adalah batal adalah satu kes.
Jika n adalah kurang daripada nod semasa nilai adalah kes yang lain.
Jika n adalah lebih besar daripada semasa nilai nod ini adalah kes ketiga.
Apa kes keempat dan terakhir?
Saya fikir kita berada di luar kes, betul?
Ia mesti yang n dalam nod semasa yang saya pada.
>> Jadi, jika saya mencari 55 pada ketika ini dalam cerita, yang cawangan
pokok akan kembali benar.
Jadi apa yang menarik di sini ialah kita sebenarnya, tidak seperti minggu lalu, kita jenis
daripada mempunyai dua kes asas.
Dan mereka tidak perlu menjadi semua di atas.
Atas adalah kes asas kerana jika pokok adalah batal, tiada apa-apa yang perlu dilakukan.
Hanya kembali berkod keras nilai palsu.
>> Cawangan bawah adalah jenis yang lalai, di mana jika kita telah diperiksa untuk
null, kami telah diperiksa jika ia harus kiri, tetapi ia tidak sepatutnya, kita kena
diperiksa jika ia harus betul, tetapi ia tidak perlu, jelas ia telah menjadi
betul di mana kita berada.
Itulah kes asas.
Jadi ada dua kes rekursi adalah diapit di sana di tengah-tengah.
Tetapi saya boleh telah menulis ini di mana-mana perintah.
Saya hanya fikir ia jenis berasa semula jadi terlebih dahulu menyemak kesilapan yang mungkin,
kemudian memeriksa kiri, kemudian memeriksa betul, maka menganggap bahawa anda berada di nod
anda sebenarnya cari.
>> Jadi mengapa ini mungkin berguna?
Jadi ia ternyata -
dan biarlah saya melompat untuk memujuknya di sini bahawa dalam web.
Kami akan mula menggunakan bukan bahasa pengaturcaraan pada mulanya, tetapi
bahasa markup.
Sebuah bahasa markup yang satu itu serupa dalam semangat kepada pengaturcaraan
bahasa, tetapi ia tidak memberi anda keupayaan untuk meluahkan diri anda secara logik.
Ia hanya memberikan anda keupayaan untuk menyatakan diri struktur.
>> Di manakah anda ingin meletakkan sesuatu pada halaman, laman web ini?
Warna apa yang anda mahu menjadikan ia?
Apa saiz font yang anda mahu untuk membuat ia?
Apa perkataan yang anda sebenarnya mahu di laman web?
Jadi itu adalah satu bahasa markup.
Tetapi kita dengan cepat akan memperkenalkan JavaScript, yang merupakan sepenuhnya
bahasa pengaturcaraan.
Sangat serupa sintaksis dalam penampilan kepada C, tetapi ia akan mempunyai beberapa
baik, lebih kuat, lebih ciri-ciri mesra pengguna.
>> Dan salah satu daripada kekecewaan di titik dalam semester adalah bahawa kita akan
segera melaksanakan ejaan yang jauh lebih kecil baris kod dengan menggunakan bahasa-bahasa lain
daripada C sendiri membenarkan, tetapi atas sebab ini kita tidak lama lagi akan faham.
Ini akan menjadi yang pertama laman web itu.
Ia akan benar-benar underwhelming, yang pertama yang kita buat.
Ia hanya akan berkata, hello dunia.
Tetapi jika anda tidak pernah melihat ia sebelum ini, ini adalah HTML,
Hiperteks Markup Language.
>> Jika anda pergi ke pilihan menu tertentu dalam mana-mana pelayar yang paling, di mana-mana laman web di
internet, anda boleh melihat HTML bahawa beberapa orang telah menulis kepada
mewujudkan bahawa laman web.
Dan ia mungkin tidak kelihatan seperti ringkas atau kemas seperti ini.
Tetapi ia akan mengikuti corak ini kurungan terbuka dan garis condong dan
surat dan berpotensi nombor.
>> Saya fikir saya akan memberikan anda memujuknya apa yang anda akan dapat melakukan
selepas mengambil CS50.
Biar saya pergi ke cs.harvard.edu / merompak, Laman Rob kita sendiri Bowden itu.
Dia menjadikan ini untuk kita.
Jadi, anda tidak lama lagi akan dapat berbuat demikian.
Dan juga, apa yang anda dengar pagi ini -
apa yang anda mendengar pagi ini -
>> [Hamster DANCE MUSIC]
>> - Karena dapat membuat ini.
Yang menanti kita pada hari Rabu.
Kita akan melihat anda kemudian.
>> [Hamster DANCE MUSIC]
DAVID MALAN: Pada CS50 seterusnya -