>> DAVID Malan: Baiklah.
Selamat datang kembali ke CS50.
Ini adalah awal minggu 8.
Dan mengingat bahwa masalah set 5 berakhir dengan sedikit tantangan.
Jadi asumsi Anda pulih semua Anda Fellows pengajaran dan foto CA
dalam file card.raw, Anda berhak sekarang semua orang-orang, dan
salah satu pemenang yang beruntung akan berjalan pulang dengan satu hal ini, gerakan lompatan
perangkat yang dapat Anda gunakan untuk akhir proyek, misalnya.
>> Ini, setiap tahun, menyebabkan sedikit keanehan.
Dan apa yang saya pikir saya akan lakukan adalah berbagi dengan Anda beberapa catatan yang memiliki
pergi bolak-balik atas daftar staf terlambat.
Misalnya, hanya semalam, kutipan tanda kutip, dari salah satu staf
anggota, "Saya hanya memiliki ketukan mahasiswa pintu untuk mengambil foto dengan saya.
Penguntit, Aku berkata kepadamu. "Dimulai cukup deskriptif dan kemudian kami pindah
pada, satu jam atau lebih kemudian, "Aku punya mahasiswa menunggu saya setelah bagian
dan dia memiliki semua nama dan foto pada beberapa lembar kertas. "Baiklah.
Jadi terorganisir, tetapi tidak semua yang belum menyeramkan.
>> Lalu, "Saya berada di luar kota akhir pekan ini, dan ketika aku kembali, ada satu di
saya
kamar tidur. "[Tertawa]
DAVID Malan: kutipan berikutnya dari staf anggota, "seorang siswa datang ke rumah saya di
Somerville at 4:00 pagi ini. "Berikutnya staf, "aku ke hotel saya di San
Francisco dan mahasiswa sedang menunggu saya di lobi dengan tiga DSLR. "
Jenis kamera.
"Aku bahkan tidak pada staf semester ini, tapi mahasiswa masuk ke rumah saya ini
pagi dan mencatat semuanya dengan Google Glass. "Dan kemudian terakhir,
"Setidaknya 12 orang yang penuh semangat menunggu untuk saya ketika aku keluar dari saya
limo, dan kemudian aku
bangun. "Baiklah.
Jadi di antara foto-foto, karena Anda mungkin ingat, sesama ini di sini, siapa Anda
mungkin tahu seperti Milo Banana, yang tinggal dengan Lauren Carvalho, kepala kita
mengajar Fellow.
Milo Milo, datang ke sini anak.
Milo.
Pikiran Anda, dia memakai Google Glass, sehingga kami akan menunjukkan semua ini setelah.
Jadi ini adalah Milo jika Anda ingin mengambil foto dengan dia sesudahnya.
Jika Anda ingin melihat keluar pada penonton di sana.
OK.
Itu rekaman yang baik.
Nah, Milo Banana.
Oh, jangan lakukan itu.
>> [Tertawa]
>> OK.
Jadi kata itu pada apa yang ada di depan, karena seperti yang kita mulai transisi,
minggu ini khusus, dari C dalam lingkungan perintah line untuk PHP dan
JavaScript dan SQL dan HTML dan CSS dalam lingkungan berbasis web, kami akan
melengkapi Anda dengan semua pengetahuan lebih untuk
potensi proyek akhir.
Menjelang itu, tentu saja memiliki tradisi mengadakan seminar yang
berada di topik tangensial untuk kursus.
Sangat banyak terkait dengan program dan pengembangan aplikasi dan sebagainya, tapi
tidak selalu dieksplorasi oleh silabus kursus sendiri.
>> Jadi, jika Anda mungkin tertarik dalam satu atau lebih seminar tahun ini,
mendaftar di cs50.net/seminar.
Ada seminar tua di cs50.net/seminars.
Dan di daftar sejauh ini untuk tahun ini adalah Web Apps yang menakjubkan dengan Ruby on
Rails, yang merupakan alternatif bahasa PHP.
Komputasi Linguistik.
Pengantar IOS, yang merupakan Platform yang digunakan untuk iPhone dan
pengembangan iPad.
JavaScript untuk Web Apps, kita akan membahas itu, tetapi dalam seminar ini, Anda akan pergi
ke lebih rinci.
>> Leap Gerak, jadi kita akan benar-benar memiliki beberapa teman-teman kita dari Leap Gerak,
perusahaan itu sendiri, bergabung dengan kami.
Besok, pada kenyataannya, untuk memberikan tangan-seminar, jika
menarik bagi Anda.
Meteor.js, suatu teknik alternatif untuk menggunakan JavaScript tidak dalam browser,
tetapi pada server.
Node.js, yang sangat banyak dalam vena juga.
Desain Android ramping.
Android menjadi alternatif yang sangat populer untuk iOS dan Windows Phone
dan platform mobile lainnya.
Dan Web Security Aktif Pertahanan.
>> Jadi sebenarnya, jika Anda ingin untuk terlibat dalam hal ini, biarkan aku
membuat catatan ini.
Kami sangat senang untuk mengatakan bahwa teman-teman kita di Leap
Gerak, yang merupakan startup -
perangkat ini benar-benar hanya datang keluar beberapa bulan yang lalu -
telah anggun menyumbangkan 30 perangkat tersebut ke kelas untuk banyak siswa, jika
Anda ingin meminjam perangkat keras menjelang akhir semester dan menggunakannya untuk
proyek akhir yang sebenarnya.
Mereka mendukung beberapa bahasa.
Tidak satupun dari mereka C, tidak satupun dari mereka PHP, sehingga menyadari satu atau lebih dari seminar ini
mungkin terbukti menarik.
Dan mereka semua akan difilmkan di Apabila Anda tidak dapat
untuk menghadiri secara pribadi.
Jadwal diumumkan melalui email saat kami memperkuat kamar.
>> Dan terakhir, jika Anda pergi ke projects.cs.50.net, ini adalah sebuah situs web
kita mempertahankan setiap tahun yang kami mengundang orang-orang dari masyarakat, fakultas,
departemen, staf, dan keduanya di luar CS50 untuk
mengusulkan ide-ide proyek.
Hal yang menarik bagi kelompok-kelompok mahasiswa.
Hal yang menarik bagi departemen.
Jadi jangan mengubah ada jika Anda berjuang dengan ketidakpastian apa yang Anda
sendiri ingin mengatasi.
>> Jadi terakhir kali kami memperkenalkan dibilang struktur data yang lebih kompleks daripada yang kita
terlihat pada minggu terakhir.
Kami telah menggunakan array cantik bahagia sebagai berguna jika
sederhana struktur data.
Kemudian kami memperkenalkan ini, yang tentu saja terkait daftar.
Dan apa yang salah satu motivasi untuk memperkenalkan struktur data?
Ya?
Apa itu?
>> AUDIENCE: Ukuran Dinamis.
>> DAVID Malan: Ukuran Dinamis.
Jadi sedangkan dalam array, Anda harus tahu ukurannya di muka ketika
Anda mengalokasikan itu.
Dalam linked list, Anda tidak harus tahu itu.
Anda hanya dapat malloc, atau lebih umum, mengalokasikan tambahan
node, sehingga untuk berbicara, setiap kali Anda ingin memasukkan lebih banyak data.
Dan simpul tidak memiliki makna yang telah ditentukan.
Ini hanya istilah generik yang menggambarkan semacam wadah yang kita
menggunakan struktur data kami untuk menyimpan beberapa item yang menarik, yang dalam hal ini
Kasus kebetulan bilangan bulat.
>> Tapi selalu ada tradeoff.
Jadi kita mendapatkan ukuran dinamis dari data struktur, tapi berapa harga yang kita bayar?
Apa Kelemahan dari daftar terkait?
Ya?
>> AUDIENCE: Membutuhkan lebih banyak memori.
>> DAVID Malan: Hal ini membutuhkan lebih memori, bagaimana sebenarnya?
>> AUDIENCE: [Tak terdengar].
>> DAVID Malan: Tepat.
Jadi sekarang kita telah mengambil pointer memori tambahan yang kami sebelumnya
tidak perlu, karena keuntungan dari sebuah array, tentu saja, adalah bahwa
semuanya berdekatan, kembali untuk kembali ke belakang, yang
memberi Anda akses acak.
Karena hanya dengan menggunakan braket persegi notasi, atau lebih teknis pointer
aritmatika, tambahan yang sangat sederhana, Anda dapat mengakses
elemen dalam waktu konstan.
Dan pada kenyataannya, itu semacam mengisyaratkan harga lain yang kita membayar dengan
linked list.
>> Apa yang terjadi pada saat menjalankan Cari sesuatu seperti, jika saya ingin
menemukan beberapa nilai dan dalam dari linked list?
Apa waktu saya berjalan menjadi?
Big O n.
Jika itu diurutkan ke?
Bagaimana jika struktur data yang diurutkan?
Aku bisa melakukan lebih baik daripada besar O n untuk mencari?
Tidak, karena dalam kasus terburuk itu mungkin sangat baik akan diurutkan, namun jumlah tersebut
Anda sedang mencari mungkin besar.
Mungkin nomor 100, yang mungkin kebetulan semua
cara di akhir.
Dan karena Anda hanya dapat mengakses linked daftar dalam pelaksanaan ini dengan
cara simpul pertama, Anda masih agak kurang beruntung.
Anda harus melintasi seluruh hal dari awal sampai akhir untuk menemukan
bahwa nilai besar seperti 100.
Atau untuk menentukan apakah itu bahkan tidak ada.
>> Jadi kita tidak bisa melakukan apa algoritma dalam data struktur yang terlihat seperti ini?
Kita tidak dapat melakukan pencarian biner, karena pencarian biner diperlukan bahwa kita memiliki
random access.
Kami hanya bisa melompat dari lokasi ke lokasi tanpa harus mengikuti
ini remah-remah roti dalam bentuk semua petunjuk ini.
>> Sekarang, bagaimana kita menerapkan ini?
Nah, jika kita pergi ke layar di sini, jika kita dapat dengan cepat reimplement Data ini
Struktur -
tulisan tangan saya tidak semua yang besar di sini, tapi kami akan mencoba.
Struct typedef Jadi, dan apa yang saya ingin menelepon hal ini di sini?
Node.
Jadi aku akan mendapatkan kita mulai.
Dan sekarang, apa yang perlu dalam struktur data untuk tunggal
linked list?
Berapa banyak bidang?
>> Jadi dua.
Salah satunya adalah cukup mudah.
Jadi int n.
Dan kita bisa menyebut n apapun yang kita inginkan, tetapi harus menjadi int jika kita
menerapkan linked list untuk ints.
Dan sekarang apa yang kedua lapangan harus?
Struct simpul *.
Jadi jika saya lakukan struct simpul *, dan kemudian saya dapat menyebut ini juga apapun yang saya inginkan,
tetapi hanya harus jelas aku akan menelepon di samping, seperti yang telah kita lakukan.
Dan kemudian aku akan menutup kurung kurawal saya.
>> Dan sekarang, seperti terakhir kali, Aku meletakkan simpul di sini.
Tapi kalau aku menyatakan ini sebagai node, kenapa aku repot-repot begitu
verbose sini dalam menyatakan struct simpul * berikutnya, sebagai lawan
hanya simpul * berikutnya?
Ya?
>> AUDIENCE: [Tak terdengar].
>> DAVID Malan: Tepat.
Tepat.
Karena C benar-benar membawa Anda secara harfiah dan hanya melihat definisi simpul
cara ke sini, Anda tidak bisa lihat itu di sini.
Jadi kita memiliki semacam ini preemptive deklarasi di sini, yang diakui
lebih verbose.
Struct node, yang berarti kita sekarang dapat mengaksesnya
dalam struktur data.
>> Dan sebagai samping, karena ini adalah menjadi sedikit lebih subyektif sekarang,
Bintang secara teknis bisa pergi di sini, itu bisa pergi di sini, dapat
bahkan pergi di tengah.
Kami telah diadopsi, di buku gaya untuk kursus, konvensi menempatkan
bintang tepat di sebelah data jenis, yang dalam hal ini,
akan struct simpul.
Tapi menyadari dalam banyak buku teks dan referensi online, Anda mungkin memang
melihatnya di sisi lain.
Tapi menyadari bahwa kedua akan benar-benar bekerja dan Anda hanya harus
konsisten.
>> Baik.
Jadi itu deklarasi kami struct simpul.
Tapi kemudian kami mulai melakukan lebih hal canggih.
Misalnya, kami memutuskan untuk memperkenalkan sesuatu seperti tabel hash.
Jadi di sini adalah tabel hash berukuran n, diindeks dari 0 di kiri atas ke n
dikurangi 1 di kiri bawah.
Ini bisa menjadi hash meja untuk apa pun.
Tapi apa hal-hal yang kita bicarakan tentang menggunakan tabel hash untuk?
Menyimpan apa?
>> Nama.
Kita bisa melakukan nama seperti kami lakukan terakhir kali.
Dan benar-benar, Anda dapat menyimpan apa-apa.
Dan kita akan melihat ini lagi di PHP dan JavaScript.
Sebuah tabel hash adalah semacam bagus Swiss Army pisau yang memungkinkan Anda untuk menyimpan
cukup banyak apa pun yang Anda inginkan dalam dengan menghubungkan kunci dengan nilai-nilai.
Kunci dengan nilai-nilai.
>> Sekarang dalam kasus sederhana ini, kami kunci hanya angka.
Kami menerapkan hash tabel sebagai array.
Dan kunci adalah 0, 1, 2, dan sebagainya.
Dan kita, sebagai manusia, memutuskan lalu minggu bahwa Anda tahu apa, jika kita
akan menyimpan nama, mari kita sewenang-wenang, tapi cukup cukup,
mengasumsikan bahwa Alice, nama A, hanya akan diindeks ke 0.
Dan Bob, nama B, akan diindeks menjadi 1, dan sebagainya.
Jadi, kami punya pemetaan antara input, yang adalah string, dan hash
lokasi, yang nomor.
>> Jadi proses yang umumnya dikenal sebagai fungsi hash, dan Anda dapat benar-benar
menerapkannya dalam kode.
Jika saya ingin menerapkan fungsi hash yang tidak persis apa yang kita
hanya dijelaskan dari waktu terakhir, aku mungkin mendeklarasikan fungsi yang mengambil, sebagai
masukan misalnya -
dan mari kita lakukan ini tentang hal ini layar di sini.
Jika saya ingin menerapkan hash fungsi, saya mungkin mengatakan
sesuatu seperti ini.
>> Ini akan mengembalikan int.
Ini akan disebut hash, dan itu akan menerima sebagai argumen
tali, atau kita bisa lebih tepat sekarang, dan berkata char *, kita akan menyebutnya s.
Dan kemudian semua fungsi ini harus dilakukan, akhirnya, adalah mengembalikan int.
Sekarang, bagaimana melakukan itu mungkin tidak begitu jelas.
Aku akan menerapkan ini tanpa membentuk memeriksa kesalahan sekarang.
Aku hanya akan mengatakan membabi buta, kembali apa pun yang di s braket 0, dikurangi,
katakanlah, modal koma A.
>> Benar-benar rusak.
Ini tidak sempurna karena satu, bagaimana jika s adalah null?
Hal-hal buruk yang akan terjadi.
Dua, bagaimana jika huruf pertama dalam Nama bukan huruf kapital?
Itu tidak akan mengubah dengan baik baik.
Mungkin huruf kecil atau tidak surat sama sekali.
Jadi benar-benar ruang untuk perbaikan di sini, tapi ini adalah ide dasar.
>> Apa yang kita dijelaskan minggu lalu secara verbal hanya proses pemetaan Alice
0 dan Bob 1 dapat dinyatakan pasti lebih formulaically sebagai C
berfungsi di sini.
Menelepon lagi hash, mengambil string sebagai masukan, dan kemudian entah bagaimana melakukan sesuatu
dengan masukan untuk menghasilkan output.
Tidak seperti deskripsi kotak hitam kami bahwa kita sudah lama dilakukan.
Saya tidak tahu bagaimana ini mungkin bekerja di bawah tenda.
>> Untuk masalah set 6, salah satu tantangan adalah bagi Anda untuk memutuskan apa
akan fungsi hash Anda?
Apa yang akan menjadi bagian dalam yang berwarna hitam kotak, dan mungkin, itu akan menjadi
sedikit lebih menarik daripada ini, dan pasti lebih rentan terhadap kesalahan
memeriksa dari ini khusus implementasi.
>> Namun masalah dapat muncul, kan?
Jika kita memiliki struktur data seperti ini satu, apa salah satu masalah
Anda bisa lari ke dari waktu ke waktu seperti yang Anda masukkan nama yang lebih dan lebih ke dalam
tabel hash?
Anda mendapatkan tabrakan, kan?
Bagaimana jika Anda memiliki Alice dan Harun, dua orang yang namanya terjadi
untuk memulai dengan A?
Itu menimbulkan pertanyaan, di mana Anda menempatkan kedua seperti nama A?
>> Nah, Anda naif mungkin hanya menaruhnya di mana Bob milik, tapi kemudian Bob
jenis kacau jika Anda mencoba untuk masukkan namanya berikutnya dan
tidak ada ruang baginya.
Jadi Anda mungkin menempatkan Bob mana Charlie, dan Anda bisa bayangkan ini sangat cepat
mengalihkan menjadi sedikit berantakan.
Sesuatu linear pada akhirnya, di mana Anda hanya perlu mencari semuanya
mencari Alice atau Bob atau Harun atau Charlie.
>> Jadi, bukannya kami mengusulkan, bukan hanya linear probing untuk ruang terbuka
dan plopping nama-nama di sana, kami mengusulkan pendekatan pelamun.
Sebuah tabel hash dilaksanakan masih dengan array indeks, tetapi tipe data
mereka indeks sekarang adalah pointer.
Pointer ke apa?
Pointer ke daftar terhubung.
>> Karena ingat bahwa linked list benar-benar hanya pointer ke node, dan
node memiliki kolom berikutnya, dan simpul tersebut memiliki kolom berikutnya, dan sebagainya.
Jadi sekarang Anda bisa memikirkan array ini pada sisi kiri dari sebuah tabel hash sebagai
mengarah ke linked list.
Keuntungan dari yang jika Anda mendapatkan tabrakan antara Alice dan Harun,
apa yang Anda lakukan dengan kedua orang tersebut?
Anda tinggal memasang dia ke akhir, atau bahkan awal
itu linked list.
>> Dan sebenarnya, mari kita mie melalui yang sesaat.
Dimana akan membuat paling masuk akal?
Jika saya memasukkan Alice dan dia berakhir di lokasi pertama, maka saya mencoba untuk
masukkan nama Harun, dan ada jelas tabrakan, harus saya masukkan
dia di awal dari linked list?
Itu pada saat itu lokasi pertama, atau di akhir?
>> AUDIENCE: [Tak terdengar].
>> DAVID Malan: OK.
Aku mendengar dimulai.
Mengapa di awal?
>> AUDIENCE: [Tak terdengar].
>> DAVID Malan: OK.
Ini abjad, jadi itu bagus.
Itu properti baik.
Ini akan menyelamatkan saya beberapa waktu berpotensi.
Ini tidak akan membiarkan saya melakukan pencarian biner, tapi aku mungkin setidaknya dapat untuk keluar
loop jika saya menyadari, well, aku cara masa lalu adalah Aaron akan berada di ini
diurutkan linked list.
Saya tidak perlu membuang waktu saya melihat semua jalan sampai akhir.
Jadi itu wajar.
Mengapa lagi yang mungkin ingin Anda masukkan nama bertabrakan di
awal daftar?
Apa itu?
>> AUDIENCE: [Tak terdengar].
>> DAVID Malan: Ini bisa memakan waktu yang lama untuk sampai ke akhir daftar.
Dan pada kenyataannya, lagi dan lagi.
Semakin banyak Anda memasukkan nama yang mulai dengan A, semakin lama
rantai akan mendapatkan.
Semakin lama yang terkait Daftar akan mendapatkan.
Jadi Anda benar-benar hanya membuang-buang waktu Anda.
Mungkin Anda lebih baik mempertahankan waktu penyisipan konstan, O besar dari 1,
dengan selalu menempatkan nama bertabrakan di awal linked list,
dan tidak khawatir sebanyak tentang menyortir.
>> Apa jawaban terbaik?
Tidak jelas.
Ini semacam tergantung pada apa yang distribusi adalah, apa pola
nama-nama Anda memasukkan.
Ini tidak selalu jawaban yang jelas.
Tapi di sini, sekali lagi, adalah kesempatan desain.
>> Jadi kita kemudian melihat hal ini, yang benar-benar kesempatan besar lainnya
untuk p-set 6.
Dan menyadari, jika Anda belum melakukannya, Zamyla menyelam ke kedua, hash
tabel dan mencoba, lebih terinci.
Dan walkthrough video tertanam dalam p-set spesifikasi.
Ini adalah trie -
T-R-I-E. Dan apa yang menarik tentang ini adalah bahwa waktu berjalan
untuk mencari nama, seperti Maxwell terakhir kali, adalah O besar dari apa?
Apa itu?
>> AUDIENCE: Jumlah huruf.
>> DAVID Malan: Jumlah huruf.
Aku mendengar dua hal.
Jumlah surat dan waktu yang konstan.
Jadi mari kita pergi dengan yang pertama kali.
Jumlah huruf.
Nah, ini struktur data, ingat, adalah seperti pohon, pohon keluarga, masing-masing
yang node terdiri dari array.
Dan orang-orang array pointer ke node seperti lainnya, atau lainnya seperti
array di pohon.
>> Jadi jika kita ingin kemudian menentukan apakah Maxwell ada di dalam sini, aku bisa pergi
ke array pertama, di bagian paling atas dari pohon, yang disebut akar, atas
dengan trie, kemudian ikuti pointer m, maka pointer, maka x,
w, e, l, l.
Dan kemudian ketika saya melihat beberapa simbol khusus, dilambangkan di sini sebagai segitiga.
Dalam kode Anda akan melihat kami mengusulkan agar Anda diimplementasikan sebagai bool, hanya mengatakan ya
atau tidak, kata berhenti di sini.
>> Nah, setelah kami telah pergi ke M-A-X-W-E-L-L, terasa seperti tujuh, mungkin
delapan jika kita pergi satu melewatinya, delapan langkah-langkah untuk menemukan Maxwell.
Atau sebut saja K. Tapi ingat terakhir waktu, saya berpendapat bahwa jika ada
realistis panjang maksimum pada kata, seperti tokoh-tokoh 40-beberapa-aneh, a
panjang maksimum menyiratkan nilai konstan.
Jadi benar-benar, ya, itu O teknis besar 8 atau 7, atau O benar-benar besar dari K. Tapi
jika ada topi terbatas pada apa yang K bisa, itu adalah konstan.
Dan jadi O besar 1 di akhir hari.
>> Tidak di dunia nyata.
Tidak ketika Anda benar-benar mulai menonton Jam Anda sebagai berjalan program anda.
Ini benar-benar akan menjadi sedikit lebih lambat dari yang benar-benar konstan
waktu dengan satu langkah.
Ini akan menjadi tujuh atau delapan langkah, tapi masih itu jauh, jauh lebih baik
dari sebuah algoritma seperti O besar n yang tergantung pada ukuran apa yang ada di
struktur data.
>> Perhatikan terbalik di sini adalah kita dapat menyisipkan satu juta nama lebih ke ini
struktur data, tapi berapa banyak langkah itu akan membawa kita untuk menemukan
Maxwell dalam kasus itu?
Tidak ada.
Dia tidak terpengaruh.
Dan sampai saat ini, saya tidak berpikir kami telah melihat contoh struktur data atau
algoritma yang benar-benar terpengaruh oleh eksternal
perilaku seperti itu.
Tapi ini tidak bisa menjadi luar biasa.
Ini tidak bisa menjadi satu-satunya solusi untuk p-set
>> Dan itu tidak.
Hal ini belum tentu data struktur Anda harus tertarik ke,
karena seperti tabel hash, tradeoff.
Apa harga yang Anda bayar di sini?
Memori.
Maksudku, ini adalah mengerikan jumlah memori.
Dan Anda tidak bisa melihatnya di sini karena penulis gambar ini
jelas terpotong semua array, dan kami tidak melihat banyak A dan
B dan C dan Q dan Y dan Z dalam array.
Tapi mereka ada.
>> Masing-masing node ini adalah seluruh array dari sekitar 26 atau lebih byte, masing-masing
yang merupakan surat.
27 dalam kasus kami, sehingga kami dapat mendukung apostrof dalam sejumlah masalah.
Jadi ini benar-benar struktur data, benar-benar padat dan lebar.
Dan itu saja mungkin berakhir memperlambat segalanya, atau setidaknya biaya Anda
lebih banyak ruang.
Tapi sekali lagi, kita dapat menarik perbandingan di sini.
>> Ingat beberapa waktu lalu, kita mencapai banyak waktu berjalan lebih menarik dalam memilah
ketika kita menggunakan merge sort, tapi harga kita dibayar untuk mencapai n log n untuk penggabungan
semacam diperlukan bahwa kita menghabiskan lebih apa sumber daya?
Lebih banyak ruang.
Kami membutuhkan array sekunder untuk menyalin orang dalam, seperti
kita lakukan di sini di atas panggung.
Jadi sekali lagi, tidak ada pemenang yang jelas, tapi hanya desain subjektif
keputusan yang harus dibuat.
>> Baik.
Jadi bagaimana ini?
Siapapun mengenali D-Hall?
OK.
Jadi kami bertiga lakukan.
Mather House.
Jadi ini adalah untuk makan Mather.
Saya berani bertaruh semua ruang makan memiliki tumpukan nampan seperti ini.
Dan ini sebenarnya perwakilan dari sesuatu yang kita sudah
jelas terlihat sudah.
Kami menyebutnya harfiah stack.
Dan stack, dalam hal Anda memori komputer, di mana data berjalan
sementara fungsi dipanggil.
>> Misalnya, apa hal-hal pergi pada tumpukan sehubungan dengan
tata letak memori kita bahas di minggu terakhir?
Apa itu?
>> AUDIENCE: Panggilan ke fungsi.
>> DAVID Malan: Maafkan aku.
>> AUDIENCE: Panggilan ke fungsi.
>> DAVID Malan: Panggilan ke fungsi, tetapi khusus, apa yang di dalam masing-masing
frame tersebut?
Apa macam hal?
Ya.
Jadi variabel lokal.
Kapan saja kita membutuhkan beberapa penyimpanan lokal, seperti sebuah argumen, atau int I, atau int
temp, atau apa pun lokal variabel, kita sudah
menempatkan bahwa pada stack.
Dan kami menyebutnya setumpuk karena itu ide layering.
Hanya jenis pertandingan dengan realitas, konsep tersebut.
>> Tapi ternyata bahwa tumpukan juga bisa dilihat sebagai struktur data,
alternatif untuk array, alternatif ke linked list.
Sesuatu konseptual lebih menarik yang masih bisa
diimplementasikan menggunakan salah satu dari mereka hal, tapi itu jenis yang berbeda
struktur data pendukung, benar-benar, hanya dua operasi.
Tapi Anda dapat menambahkan pada pelamun fitur dari ini.
Tetapi ini adalah dasar -
mendorong dan pop.
>> Dan ide dengan tumpukan adalah bahwa jika saya miliki di sini, dengan atau tanpa Annenberg
mengetahui, nampan dari sebelah dengan nomor 9 di atasnya.
Jadi hanya sebuah int.
Dan saya ingin mendorong ini ke data struktur, yang saat ini kosong.
Pertimbangkan ini bagian bawah tumpukan.
Saya akan mendorong nomor ini ke 9 menumpuk, dan sekarang itu ada di sana.
>> Tapi yang menarik tentang tumpukan adalah bahwa jika saya sekarang ingin mendorong
beberapa nilai lainnya, seperti 17, dan saya mendorong ini ke stack, aku akan melakukan
satu-satunya hal yang intuitif, aku hanya akan untuk menempatkan tepat di mana kita manusia
akan cenderung untuk meletakkannya, di atas.
Tapi apa yang menarik sekarang adalah, bagaimana saya mendapatkan jam 9?
Kau tahu, aku tidak tanpa usaha.
>> Jadi apa yang menarik tentang stack adalah bahwa dengan desain,
itu adalah struktur data LIFO.
Cara konyol untuk menggambarkan terakhir, keluar pertama.
Jadi nomor terakhir di saat ini adalah 17.
Jadi jika saya ingin pop sesuatu dari tumpukan, itu hanya bisa 17.
Jadi ada perintah wajib operasi di sini, di mana item terakhir
di harus menjadi yang pertama keluar.
Oleh karena itu singkatan, LIFO.
>> Jadi mengapa hal ini menjadi berguna?
Apakah konteks mereka di mana kau lebih menginginkan sebuah struktur data seperti ini?
Yah, itu pasti telah berguna dalam komputer.
Jadi sistem operasi jelas menggunakan ini jenis struktur data untuk tumpukan.
Kita juga akan melihat ide yang sama ketika datang ke halaman web.
Jadi minggu ini dan minggu depan dan seterusnya, dan ketika Anda mulai menerapkan web
halaman dalam bahasa yang disebut HTML, Anda dapat benar-benar menggunakan struktur data seperti
ini untuk menentukan apakah halaman adalah diformat dengan benar.
Karena kita akan melihat semua halaman web mengikuti semacam hirarki, lekukan
yang akan, pada akhir hari, menjadi struktur pohon bawah tenda.
Jadi lebih pada bahwa dalam hanya sedikit.
>> Tapi untuk saat ini, mari kita mengusulkan untuk saat, bagaimana kita bisa pergi tentang
mewakili apa stack?
Mari saya mengusulkan agar kita menerapkan tumpukan dengan kode seperti ini.
Jadi tumpukan akan memiliki di dalamnya dua hal, sebuah array, yang disebut nampan,
hanya untuk konsisten dengan demo.
Dan masing-masing item dalam array yang akan menjadi tipe int.
Dan kapasitas diduga apa?
Karena saya sudah tidak menulis Definisi lengkap di sini.
>> Ini mungkin maksimal ukuran array.
Dan itu mungkin dinyatakan sebagai tajam mendefinisikan di bagian atas file, beberapa
jenis konstan seperti yang tersirat oleh kapitalisasi belaka.
Jadi suatu kapasitas didefinisikan sebagai kemungkinan ukuran maksimum.
Sementara itu, dalam struktur data dikenal sebagai tumpukan akan ada
menjadi integer hanya dikenal hanya sebagai ukuran.
>> Jadi jika saya untuk mewakili sekarang pictorially, mari kita anggap bahwa ini
Seluruh kotak hitam menunjukkan tumpukan saya.
Di dalamnya adalah dua variabel.
Jadi aku akan menggambar pertama sebagai ukuran.
Dan yang kedua aku akan menggambar sebagai array.
>> Tapi hanya untuk menjaga hal-hal yang teratur, biasanya aku akan menggambar sebuah array seperti
ini, tapi itu jenis yang baik jika kita sesuai dengan kenyataan, atau
cocok model mental.
Jadi biarkan aku malah menggambar array vertikal, yang hanya, sekali lagi,
membawakan lagu artis.
Tidak terlalu penting apa adalah di bawah tenda.
Dan kami akan mengatakan bahwa, secara default, kapasitas akan menjadi tiga.
Jadi ini akan menjadi lokasi 0, ini akan menjadi lokasi 1, ini
akan menjadi lokasi 2.
>> Jika saya menyuap dengan bola stres, akan seseorang ingin datang dan menjalankan
naik di sini untuk sesaat?
OK, melihat tangan Anda terlebih dahulu.
Ayo up.
Baik.
Jadi saya percaya itu adalah Steven.
Ayo up.
Baik.
>> Tapi misalkan sekarang kita mundur ke awal keadaan dunia di mana aku
baru saja mengumumkan stack, dan itu akan kapasitas tiga.
Tapi ukuran belum ditentukan.
Nampan belum ditentukan.
Jadi beberapa pertanyaan pertama.
Dan izinkan saya memberi Anda mic sehingga Anda dapat turut lebih aktif dalam hal ini.
>> Jadi apa yang ada dalam ukuran saat ini dalam waktu jika semua yang saya lakukan adalah
menyatakan tumpukan dengan satu baris kode?
>> STEVEN: Tidak banyak.
>> DAVID Malan: OK, tidak banyak.
Apakah kita tahu apa yang ada dalam ukuran, kita tahu apa yang ada di dalamnya
array ini di sini?
>> STEVEN: Hanya kode acak, kan?
Hanya -
>> DAVID Malan: Ya, aku akan menyebutnya kode, tapi acak -
>> STEVEN: Hal.
>> DAVID Malan: Hal-hal seperti acak
>> STEVEN: Bits.
>> DAVID Malan: Bits, kan?
Jadi nilai-nilai sampah, kan?
Jadi permutasi dari 0 dan 1.
Sisa-sisa penggunaan sebelumnya memori ini.
Dan kita tidak benar-benar tahu apa nilai-nilai yang, jadi kami biasanya menarik mereka
sebagai tanda tanya.
>> Jadi hal pertama yang kita mungkin akan ingin lakukan di sini -
dan biarkan aku memberikan bidang ini dalam dari ada nama - nampan.
Apa yang harus kita mungkin menginisialisasi ukuran jika kita ingin
mulai menggunakan tumpukan ini?
>> STEVEN: Baki adalah sub 3.
>> DAVID Malan: Jadi, OK.
Untuk menjadi jelas, kapasitas dinyatakan tempat lain sebagai tiga.
Dan itulah yang saya gunakan untuk mengalokasikan array.
Ukuran akan mengacu pada berapa banyak nampan saat ini di stack.
>> STEVEN: Nol.
>> DAVID Malan: Jadi harus nol.
Jadi silakan, dan dengan jari apapun, menggambar nol dalam ukuran.
Baik.
Jadi sekarang, apa yang ada di dalam ini di sini, kita tidak tahu.
Ini benar-benar hanya nilai sampah.
Jadi kita bisa menggambar tanda tanya, tapi mari kita menjaga papan bersih untuk saat ini
karena tidak peduli apa yang ada.
Kita tidak perlu menginisialisasi array apa-apa, karena jika kita tahu bahwa
ukuran stack adalah nol, well, kita seharusnya tidak melihat apa pun di
array ini pula pada titik waktu ini.
>> Jadi sekarang mengira bahwa aku mendorong nomor 9 ke stack.
Bagaimana kita harus memperbarui struktur data dalam kotak hitam ini?
Nilai-nilai apa yang perlu berubah?
>> STEVEN: Dalam -
ukuran?
>> DAVID Malan: OK.
Ukuran harus menjadi apa?
>> STEVEN: Ukuran akan menjadi salah satu.
>> DAVID Malan: OK.
Sehingga ukuran harus menjadi satu.
Sehingga Anda dapat melakukan ini dalam beberapa cara.
Mari saya beri, sekarang Anda jari penghapus.
Baik.
Maka sekarang jari Anda adalah kuas.
Baik.
Dan sekarang apa lagi harus berubah, jelas, dalam struktur data?
>> STEVEN: Kita akan dari bottom up sampai 9.
>> DAVID Malan: 9.
OK, baik.
Jadi masih tidak peduli apa yang di lokasi satu atau dua karena mereka
nilai sampah, tapi kita tidak perlu repot-repot mencari sana karena ukuran
mengatakan kepada kita bahwa hanya elemen pertama sebenarnya sah.
Jadi sekarang aku mendorong 17 ke daftar.
Apa yang terjadi dengan gambar ini?
>> STEVEN: Jadi ukuran akan pergi ke dua.
>> DAVID Malan: OK.
Kau penghapus -
oops.
Kau penghapus.
>> STEVEN: Eraser.
>> DAVID Malan: Kau kuas.
>> STEVEN: Brush.
>> DAVID Malan: OK.
Dan apa lagi?
>> STEVEN: Dan kemudian kita -
>> DAVID Malan: Kami mendorong 17.
>> STEVEN: Kami tetap di atas 17, sehingga -
>> DAVID Malan: OK, baik.
>> STEVEN: - menjatuhkannya ke bawah.
>> DAVID Malan: Baiklah.
Sudah mulai mudah.
Aku tidak akan membantu Anda saat ini.
Dorong 22.
>> STEVEN: Selesai.
Menjadi penghapus.
Aku menjadi kuas.
Dan kemudian saya menempatkan 22.
>> DAVID Malan: 22.
Luar biasa.
Jadi sekali lagi.
Saya sekarang akan mendorong ke tumpukan 26.
>> STEVEN: Ooh.
Oh gosh.
Anda benar-benar menangkap saya lengah.
>> DAVID Malan: Anda tidak melihat ini datang?
>> STEVEN: Saya tidak melihat ini datang.
Bisakah kita kapasitas re-awal?
>> DAVID Malan: Itu pertanyaan yang bagus.
Jadi kita semacam dicat diri di sudut sini.
Benar-benar ada keluar yang baik untuk Steven karena kita telah dialokasikan array ini
statis, sehingga untuk berbicara, di dalam dari struktur data.
Dan kami telah dasarnya sulit kode itu menjadi ukuran tiga.
Jadi kita tidak bisa benar-benar mengalokasikan itu.
>> Kita bisa jika kita kembali, kita didefinisikan ulang nampan menjadi pointer yang
kita kemudian menggunakan malloc ke memori tangan untuk.
Karena jika kita punya memori dari tumpukan melalui malloc, kami
kemudian bisa membebaskannya.
Tapi sebelum membebaskan, kita bisa mengalokasikan sepotong besar memori,
memperbarui pointer, dan sebagainya.
Tetapi untuk sekarang, ini benar-benar yang terbaik yang bisa kita lakukan.
Mendorong dan pop yang mungkin akan harus sinyal beberapa error.
>> Jadi misalnya, implementasi kami push bisa kembali bool yang
sebelumnya kembali benar, benar, benar.
Tapi keempat kalinya, itu akan memiliki untuk kembali palsu, misalnya.
Baik.
Sangat baik dilakukan.
Selamat.
Anda telah menerima bola stres Anda hari ini.
>> [Tepuk Tangan]
>> STEVEN: Terima kasih.
>> DAVID Malan: Terima kasih.
OK, jadi ini tampaknya tidak banyak dari langkah maju, kan?
Kami menggambarkan struktur data ini.
Sudah menarik, kan?
Sistem operasi seperti itu.
Rupanya web dapat memanfaatkan ini, dan aplikasi lain masih.
Tapi apa batasan bodoh bahwa kita kembali ke semacam dua minggu batas
di mana kita telah tetap ukuran array.
>> Jadi memang ada beberapa cara kita bisa memecahkan masalah ini.
Kita bisa secara dinamis mengalokasikan array, tidak dengan dikodekan itu seperti yang telah saya
dilakukan di sini, tapi malah kembali mendeklarasikan ini, hanya harus jelas, seperti
sesuatu seperti ini.
Int * nampan, tidak memutuskan pada kapasitas belum.
Tapi ketika saya menyatakan stack tempat lain dalam kode saya, saya kemudian bisa menelepon malloc,
mendapatkan alamat dari sepotong memori, dan aku bisa menetapkan
alamat ke nampan.
>> Dan kemudian, karena itu hanya sepotong memori, saya bisa terus menggunakan persegi
notasi braket dengan cara biasa.
Karena sekali lagi, ada semacam ini setara fungsional array dan
potongan memori yang datang kembali dari malloc.
Kita dapat memperlakukan satu dengan yang lain menggunakan pointer aritmetika atau
persegi notasi braket.
Jadi itu salah satu pendekatan.
>> Tapi bagaimana lagi kita bisa menerapkan ini struktur data yang sama, berpotensi?
Benar?
Saya merasa seperti baru saja kita selesaikan ini masalah seperti tahun lalu.
Apa solusi untuk masalah ini bahwa Steven berlari ke?
Jadi daftar terkait, benar.
>> Jika masalahnya adalah bahwa kita melukis diri ke sudut dengan mengalokasikan
di muka memori terlalu sedikit yang kita kemudian harus entah bagaimana berurusan dengan, baik,
mengapa tidak hanya menghindari menerbitkan sama sekali?
Mengapa tidak hanya menyatakan nampan menjadi pointer ke node, ergo sebuah linked list,
dan kemudian hanya mengalokasikan node baru setiap kali Steven yang dibutuhkan untuk memenuhi
nomor ke dalam struktur data.
>> Jadi gambar harus berubah.
Ini tidak akan menjadi sebagai bersih dan sederhana seperti hanya sebuah array dari tiga ints.
Sekarang akan menjadi pointer ke struct, dan struct yang akan
memiliki int dan pointer berikutnya.
Ini akan memimpin melalui pointer yang lain struct tersebut untuk
lain struct tersebut.
Jadi gambar akan benar-benar mendapatkan berantakan sedikit.
Dan kita akan panah mengikat segalanya bersama-sama.
>> Tapi itu baik-baik saja, kan, karena kita telah melihat bagaimana melakukan ini.
Dan setelah Anda merasa nyaman menerapkan sesuatu seperti linked
Daftar, yang Anda harus lakukan jika Anda memilih untuk menerapkan tabel hash dengan
chaining terpisah untuk p-set 6, Anda dapat menggunakannya sebagai sebuah blok bangunan, atau
bahan, atau dalam Scratch berbicara, prosedur, sesuatu yang Anda menempatkan, Anda
menciptakan potongan puzzle Anda sendiri yang kemudian dapat digunakan kembali.
Jadi pengorbanan, tetapi solusi potensial bahwa kita sudah benar-benar terlihat sebelumnya.
>> Jadi cukup sering, Anda melihat ini setiap atau dua tahun ketika Apple rilis
sesuatu yang baru, dan semua orang yang gila berbaris di luar dari Apple
menyimpan untuk membeli marjinalnya upgrade pada hardware.
Saya mengatakan ini, itu OK, karena Aku salah satu dari orang-orang.
Jadi, apa jenis struktur data mungkin mewakili kenyataan ini?
>> Yah, sebut saja antrian, garis.
Jadi Inggris akan menyebutnya biasanya antrian, jadi itu adalah nama yang bagus.
Dan dua operasi yang antrian harus mendukung kami akan menelepon enqueue sebuah
operasi dan operasi dequeue, yang serupa dalam
semangat untuk mendorong dan pop.
Ini hanya semacam berbeda dalam konvensi, apa yang kita panggil ini.
Tetapi untuk enqueue sesuatu berarti menambah atau masukkan ke struktur data.
Untuk dequeue berarti untuk menghapusnya.
Namun, sementara tumpukan adalah data LIFO struktur, antrian adalah di pertama,
pertama keluar struktur data.
>> Jika Anda adalah orang di baris pertama, Anda akan menjadi orang pertama untuk mendapatkan
keluar dari barisan dan membeli perangkat baru.
Bayangkan betapa sedih orang-orang ini akan jika Apple malah menggunakan stack, untuk
Misalnya, untuk melaksanakan memilih yang up mainan baru Anda.
Jadi antrian masuk akal, tentu, dan kita bisa memikirkan segala macam
aplikasi, mungkin, untuk antrian, terutama bila Anda ingin keadilan.
Jadi bagaimana mungkin kita menerapkan sebagai struktur data?
>> Nah, saya mengusulkan bahwa kita mungkin perlu melakukannya dengan cara ini.
Jadi aku akan sekarang memiliki nomor.
Jadi kita akan tetap sederhana dan tidak selalu berbicara dalam hal nampan.
Hanya angka yang orang mendapatkan.
Kapasitas akan, sekali lagi, memperbaiki jumlah orang yang dapat di
baris ini, sebagai tiga atau apapun lainnya nilai.
>> Tapi saya mengusulkan bahwa saya perlu untuk melacak tidak hanya dari ukuran
antrian, berapa banyak hal di dalamnya.
Jadi ukuran adalah ukuran saat ini, kapasitas adalah ukuran maksimum.
Hanya lagi, nomenklatur dengan konvensi.
Mengapa saya perlu sebuah int tambahan di dalam dari antrian untuk melacak siapa yang
garis depan?
Mengapa saya harus melakukan itu dalam kasus ini?
>> Nah, bagaimana gambar ini akan berubah?
Saya mungkin dapat menggunakan kembali sebagian gambar ini.
Biarkan aku pergi ke depan dan menghapus apa yang ada di sini.
Kami akan memberikan ini sedikit nama yang berbeda di sini.
Mari kita menyingkirkan 17, mari kita menyingkirkan dari 9, mari kita menyingkirkan 3.
Dan mari kita tambahkan satu hal lain.
Saya mengusulkan bahwa saya perlu untuk melacak depan daftar, yang hanya
akan menjadi int juga.
Dan kita akan tetap sederhana.
Tidak ada linked list untuk saat ini.
>> Kita akan mengakui bahwa kita akan benjolan melawan batas ini.
Tapi apa yang saya ingin melihat terjadi saat ini?
Jadi misalkan saya pergi ke depan dan yang pertama orang muncul sejalan, dan
itu adalah nomor 9.
Kami memiliki bola stres.
Dapatkah saya mencuri, katakanlah, dua atau tiga orang?
Satu, dua, tiga?
Ayo up.
Kanan dari depan, karena kami akan membuat satu ini cepat.
>> Anda masing-masing sekarang akan menjadi seorang anak penggemar di baris di Apple.
Anda tidak akan menerima hardware Apple pada akhir meskipun hal ini.
Baik.
Jadi kau nomor 9, Anda nomor 17, nomor 22.
Ini adalah nomor sewenang-wenang, seperti mahasiswa ID atau entah apa lagi.
Dan hanya dalam beberapa saat, mari kita mulai untuk mulai menambahkan sesuatu.
Dan aku akan menjalankan papan di sini saat ini.
>> Jadi dalam hal ini, saya telah diinisialisasi depan untuk menjadi -
Aku sebenarnya tidak benar-benar peduli apa yang depan, karena ukurannya adalah nol.
Jadi ini mungkin juga hanya menjadi tanda tanya.
Ini semua adalah tanda tanya.
Jadi sekarang kita akan mulai untuk benar-benar melihat beberapa orang berbaris di toko.
>> Jadi jika nomor 9, kau yang pertama ada pada 05:00, maju dan berbaris,
atau malam sebelumnya.
OK.
Jadi sekarang 9 di sini.
Jadi 9 adalah di depan daftar.
Jadi aku akan pergi ke depan dan memperbarui ukuran ini data saat
struktur untuk tidak menjadi 0 lagi, tetapi untuk menjadi 1.
Aku akan menempatkan 9 di depan daftar.
Biarkan aku pergi ke depan dan beralih layar sehingga kita bisa melihat masa lalu kita di sini.
>> Dan sekarang apa yang saya inginkan untuk diletakkan di depan?
Aku akan melacak bahwa depan antrian sekarang
adalah di lokasi 0.
Karena apa yang selanjutnya akan terjadi?
Nah, misalkan sekarang saya enqueue 17 juga.
Jadi hop sejalan sana.
Dan lagi, semacam pintu ke toko akan berada di sini.
Jadi sekarang saya telah menambahkan 17.
Dan meskipun orang-orang yang menghalangi layar, itu OK,
karena kita bisa melihatnya di sini.
Maaf.
>> AUDIENCE: Kita bisa bergerak -
>> DAVID Malan: Tidak, itu OK.
Ini sangat besar di sana.
Jadi 17 sekarang dalam antrian.
Saya perlu memperbarui yang bidang sekarang meskipun?
OK, pasti ukuran.
Dan bagaimana depan?
OK, tidak ada.
Depan tidak harus berubah, karena seperti tumpukan, kita
ingin mempertahankan keadilan.
Jadi jika 9 datang pertama, kami ingin 9 menjadi pertama kali keluar dari garis
dan masuk ke toko.
>> Bahkan, mari kita lihat itu.
Sebelum kita memasukkan 22, mari kita pergi ke depan dan dequeue 9.
Apa nama Anda lagi?
>> AUDIENCE: Jake.
>> DAVID Malan: Jake akan untuk dequeued sekarang.
Jadi Anda bisa berjalan ke toko.
Dan berpura-pura bahwa toko ada di sana.
Jadi sekarang apa yang perlu - dit-dit-dit!
Apa yang harus terjadi sekarang?
Desain keputusan.
Jadi bukan insting buruk, tapi - apa nama Anda lagi?
>> AUDIENCE: David.
>> DAVID Malan: David.
Jadi apa yang Daud lakukan?
Dia mencoba untuk semacam memperbaiki data struktur dan bergerak dari lokasi nya
ke bekas lokasi Jake.
Dan itu baik jika kita bersedia untuk menerima bahwa sebagai
implementasi detail.
Tapi pertama-tama, mari kita update data Struktur sebelum kita melakukan itu.
Karena aku tidak menyukai ide dari semua orang-orang pergeseran di baris ini.
>> Ini bukan masalah besar jika David melakukannya dengan satu langkah, tapi sekali lagi, pikirkan kembali
ketika kita punya delapan relawan di panggung dan kami telah dilakukan seperti penyisipan
semacam, di mana kita harus memulai bergerak semua orang di sekitar.
Yang mendapat mahal, kan?
Itu membuat saya merasa ngeri tentang O besar n, O besar n kuadrat lagi.
Ini tidak merasa seperti hasil yang ideal.
>> Jadi mari kita update ini.
Jadi ukuran antrian tidak lagi 2.
Ini sekarang hanya 1.
Tapi saya sekarang dapat memperbarui sesuatu Aku tidak memperbarui sebelumnya,
depan daftar.
Aku hanya bisa mengatakan, adalah lokasi itu 1?
Jadi sekarang kita memiliki nilai sampah di sini, nilai sampah di sini, dan David di
tengah sampah ini.
Tapi struktur data masih utuh.
>> Dan pada kenyataannya, aku bahkan tidak perlu mengubah nomor mantan Jake
9, karena siapa yang peduli.
Saya memiliki cukup informasi sekarang dalam ukuran yang saya tahu ada satu orang di
antrian ini.
Dan saya tahu bahwa orang itu berada di lokasi 1, bukan 0.
Aku tidak menghitung.
Jadi 1 juga.
Jadi struktur data masih OK.
>> Nah, apa yang terjadi selanjutnya?
Mari kita enqueue -
siapa namamu?
>> AUDIENCE: Callen.
>> DAVID Malan: Callen.
Mari kita enqueue sebuah Callen, dan 22 sekarang dalam antrian.
Jadi sekarang apa yang harus berubah di sini?
Depan tidak akan berubah, jelas.
Ukuran akan berubah menjadi 2 lagi.
Dan 22 berakhir di sini, 9 masih ada, tapi itu efektif
nilai sampah sekarang.
Ini hanya sisa-sisa masa lalu Jake.
>> Jadi sekarang apa yang terjadi jika Saya dequeue David?
Salah satu operasi terakhir, dequeue David.
Kita bisa bergeser, tapi saya mengusulkan mari kita melakukan pekerjaan sesedikit mungkin.
Sekarang struktur data saya pergi kembali dalam ukuran 2-1.
Tapi depan antrian kini menjadi 2.
Saya tidak perlu mengubah angka-angka ini dulu, karena mereka
hanya nilai sampah.
>> Tapi sekarang apa yang terjadi?
Misalkan saya enqueue diriku, 26?
Saya merasa seperti saya milik di sini.
Jadi aku sedang enqueued.
Jadi aku agak berada di sini.
Dan meskipun Anda tidak cukup menghargai ini secara visual di atas panggung,
karena kita memiliki banyak ruang, aku harus tidak bisa berdiri di sini, mengapa?
>> AUDIENCE: Anda di luar batas.
>> DAVID Malan: Benar.
Aku di luar batas.
Aku sudah diindeks di luar batas-batas array ini.
Aku benar-benar harus di salah satu tiga lokasi mungkin.
Sekarang, mana yang paling alami untuk pergi?
Saya mengusulkan kita leveraged satu minggu trik.
Mod operator, persentase.
Karena aku secara teknis berdiri di Lokasi 3, tapi aku 3 kapasitas mod,
jadi 3, tanda persen, 3 -
kapasitas adalah 3.
Apa itu?
Apa sisanya ketika Anda membagi 3 dengan 3?
0.
>> Sehingga menempatkan saya sedang Jake adalah, yang benar-benar baik.
Jadi sekarang pelaksanaan hal ini akan
menjadi sedikit sakit kepala.
Ini benar-benar hanya satu baris sakit kepala, kode.
Tapi setidaknya sekarang ada sampah nilai di sini, tapi ada dua
ints sah sini.
Dan saya menyatakan bahwa sekarang kami telah melakukan apa yang harus kita lakukan asalkan
kita mengubah apa yang Jake nilai adalah menjadi 26.
>> Kami sekarang memiliki informasi yang cukup masih untuk mempertahankan integritas
dari struktur data.
Kami masih agak kurang beruntung ketika kita ingin memasukkan empat atau lebih Total
elemen, tapi aku setidaknya bisa membuat cantik efisiensi penggunaan konstan ini
waktu, sebenarnya.
Saya tidak perlu khawatir tentang pergeseran semua orang, sebagai kecenderungan David adalah.
>> Setiap pertanyaan pada tumpukan, atau antrian ini?
>> AUDIENCE: Apakah alasan mengapa Anda membutuhkan ukuran sehingga Anda tahu
mana untuk seseorang?
>> DAVID Malan: Tepat.
Aku perlu tahu ukuran array karena saya perlu tahu persis bagaimana
banyak nilai-nilai yang sah, dan agar saya dapat menemukan tempat untuk meletakkan
orang berikutnya.
Tepat.
Ukurannya -
sebenarnya, kita tidak update ini.
Saya menambahkan sendiri di 26.
Ukurannya sekarang, tidak 1, tapi 2.
Jadi sekarang ini memang membantu saya menemukan kepala daftar, yang tidak 0, tidak
1, tapi 2.
Bagian depan daftar memang nomor 22.
Karena dia datang pertama, jadi dia harus akan diizinkan masuk ke toko sebelum saya,
meskipun secara visual aku berdiri lebih dekat ke toko.
>> Baiklah?
Sebuah tepuk tangan untuk orang-orang dan kami akan membiarkan mereka keluar dari sana.
>> [Tepuk Tangan]
>> DAVID Malan: aku bisa membiarkan Anda tetap baki.
Kita bisa melihat apa yang terjadi jika Anda inginkan, tapi mungkin tidak.
Baik.
Jadi apa sekarang yang meninggalkan kita?
Nah, biarkan aku mengusulkan bahwa ada Beberapa struktur data lainnya kita bisa
mulai menambah tool kit kami yang akan sebenarnya cukup, cukup relevan sebagai
kita menyelam ke web hal.
Yang sekali lagi, memiliki beberapa jenis koneksi pohon-pohon dalam bentuk
sesuatu yang disebut DOM, dokumen model objek.
Tapi kita akan melihat lebih banyak bahwa sebelum lama.
>> Mari saya mengusulkan bahwa kita definitionally menyebut pohon sekarang apa yang mungkin Anda kenal sebagai
lebih dari sebuah pohon keluarga, di mana Anda memiliki beberapa leluhur di
akar pohon.
Sebuah ibu pemimpin patriarki atau di bagian paling atas pohon.
Tanpa pasangan mereka, dalam kasus ini.
Tapi kita sekarang memiliki apa yang akan kita sebut anak-anak, yang merupakan node yang menggantung
dari anak kiri atau anak kanan, panah seperti yang digambarkan di sini.
>> Dengan kata lain, dalam struktur data pohon di komputer, sebuah pohon memiliki nol
atau lebih node.
Jika memiliki setidaknya satu simpul, itu disebut akar.
Hal-hal yang visual kita menarik di bagian atas.
Dan simpul tersebut, seperti node lain, bisa memiliki nol, satu, atau dua, atau tiga,
atau namun banyak anak-anak struktur data mendukung.
Dalam kasus ini, akar, menyimpan nilai satu, memiliki dua anak, 2 dan 3,
jadi kita umumnya memanggil 2 kiri anak dan 3 anak kanan.
>> Dan kemudian ketika kita turun ke 5, 6, dan 7, 6 bisa disebut anak tengah.
Jika Anda memiliki empat anak, itu akan membingungkan.
Jadi kita berhenti menggunakan jenis yang shortcut verbal.
Tapi itu benar-benar hanya pohon keluarga.
Dan daun sini adalah node yang sendiri tidak memiliki anak.
Mereka menggantung dari bawah pohon.
>> Jadi bagaimana mungkin kita menerapkan pohon yang memiliki hanya dua anak maksimal?
Kita akan menyebutnya sebuah pohon biner.
Bi berarti dua lagi, dalam hal ini kasus, seperti dengan biner.
Dan sehingga dapat memiliki nol, satu, atau dua anak maksimal.
>> Saya akan mengusulkan agar kita menerapkan node untuk itu struktur dengan n int,
dan kemudian dua pointer, satu disebut kiri, yang disebut benar.
Tetapi mereka hanya bagus konvensi sewenang-wenang.
Dan apa yang bagus sekarang, terutama jika Anda jenis berjuang konseptual dengan
rekursi, atau berpikir bahwa itu bukan benar-benar solusi untuk apa pun,
terutama jika Anda bisa kehabisan memori.
Sekarang bahwa kita sedang berbicara tentang data struktur dan algoritma yang memungkinkan
kita untuk melintasi dan memanipulasi mereka, Ternyata rekursi datang kembali
yang jauh lebih menarik jika tidak dengan cara yang indah.
>> Jadi ini saya usulkan adalah pelaksanaan dari fungsi Search.
Mengingat dua input -
jadi menganggap ini sebagai kotak hitam.
Mengingat dua masukan, n, int, dan pointer ke pohon, pointer ke
node, atau benar-benar akar pohon, saya menyatakan bahwa fungsi ini dapat kembali
benar atau salah, bahwa nilai n di dalam pohon ini.
>> Apa yang ada didalam kotak hitam ini?
Nah, empat cabang.
Pertama hanya memeriksa.
Jika pohon null, hanya kembali palsu.
Jika tidak ada simpul, tidak ada n, tidak ada nomor, hanya kembali palsu.
Jika meskipun, n, nilai yang Anda cari untuk, kurang dari pohon panah n, dan
hanya harus jelas, apa artinya bila Saya menulis pohon dan kemudian panah
notasi, n?
Tepat.
Ini berarti bahwa dereference pointer disebut pohon.
Pergi ke sana, dan kemudian masuk ke dalam itu simpul dan lapangan yang disebut n.
Dan kemudian membandingkan n aktual yang dilewatkan ke Cari menentangnya.
>> Jadi jika n kurang dari, nilai n di node pohon itu sendiri, baik,
apa artinya?
Itu berarti apa-apa pada pandangan pertama.
Benar?
Sama seperti ketika Anda memiliki sebuah array nilai-nilai, Anda mungkin ingin menerapkan biner
pencarian sebagai bentuk membagi dan menaklukkan.
Tapi apa asumsi yang kita perlu membuat untuk pencarian biner untuk bekerja sama sekali
dalam buku telepon dan contoh sebelumnya?
>> Bagaimana akan diurutkan.
Jadi mari kita memperbaiki definisi pohon di sini tidak hanya pohon, yang dapat
memiliki sejumlah anak.
Tidak hanya pohon biner, yang dapat memiliki 0, 1, atau 2 maksimal.
Tapi sebagai pohon pencarian biner, atau BST, yang hanya cara mewah untuk mengatakan suatu
pohon biner sehingga setiap node anak kiri, jika ada, adalah
kurang dari node.
Dan anak kanan setiap node, jika ada, lebih besar
dari simpul itu sendiri.
>> Jadi dengan kata lain, jika Anda adalah untuk menarik pohon keluar, semua nomor yang
hati-hati seimbang seperti ini sehingga jika Anda memiliki 55 sebagai root, 33 bisa pergi
ke kiri karena itu kurang dari 55.
77 bisa pergi ke kanan karena itu lebih besar dari 55.
Tapi sekarang perhatikan, definisi yang sama, itu adalah definisi rekursif secara lisan,
harus mengajukan 33.
Anak kiri 33 itu harus kurang dari itu, dan anak kanan 33 itu, 44, harus
lebih besar dari itu.
>> Jadi ini adalah sebuah pohon pencarian biner, dan Saya mengusulkan, menggunakan sedikit
rekursi, kita sekarang dapat menemukan n.
Jadi jika n kurang dari nilai n yang node saat ini, aku akan pergi
depan dan menyepak bola, sehingga untuk berbicara, dan hanya kembali apa jawabannya adalah
mencari n pada anak kiri pohon.
Perhatikan lagi, fungsi ini hanya mengharapkan bintang node, sebuah
pointer ke node.
Jadi pasti aku hanya bisa melakukan pohon panah kiri, yang akan menyebabkan
saya ke node lain.
Tapi apa simpul itu?
>> Nah, menurut deklarasi ini, kiri adalah hanya pointer, sehingga hanya
berarti aku melewati ke fungsi pencarian pointer yang berbeda, yaitu
salah satu yang mewakili Pohon anak kiri saya.
Jadi dalam hal ini, pointer ke 33, jika ini adalah masukan sampel kami Sementara itu, jika
n lebih besar dari nilai n di node saat ini di pohon, maka aku
akan pergi ke depan dan menyepak bola yang lain arah dan hanya mengatakan, saya tidak
tahu apakah nilai ini n adalah di pohon, tapi aku tahu apakah itu, itu saya turun
cabang kanan, sehingga untuk berbicara.
Jadi biarkan saya panggilan rekursif mencari, melewati n lagi, tapi lewat di
pointer ke anak kanan saya.
>> Dengan kata lain, jika aku saat ini di 55 dan saya sedang mencari 99, saya tahu bahwa 99
lebih besar dari 55, jadi seperti aku merobek minggu buku telepon lalu dan kami
pergi kanan, sama kita akan pergi di sini.
Dan aku tidak tahu apakah itu di sebelah kanan saya anak, dan itu tidak, 77 ada, tapi
Aku tahu itu ke arah itu.
Jadi saya sebut pencarian di anak kanan saya, 77, dan biarkan angka pencarian keluar dari
sana jika 99 di sewenang-wenang ini contoh adalah sebenarnya ada.
>> Lain, apa kasus terakhir?
Jika pohon null adalah salah satu kasus.
Jika n kurang dari simpul saat ini yang Nilai adalah kasus lain.
Jika n lebih besar dari saat ini Nilai node adalah kasus ketiga.
Apa kasus keempat dan terakhir?
Saya pikir kita keluar dari kasus, kan?
Harus bahwa n adalah di node saat ini bahwa aku di.
>> Jadi jika saya mencari 55 pada saat ini dalam cerita, bahwa cabang
pohon akan kembali benar.
Jadi apa yang menarik di sini adalah bahwa kita sebenarnya, tidak seperti minggu terakhir, kita jenis
dari memiliki dua kasus dasar.
Dan mereka tidak perlu menjadi semua di atas.
Atas adalah kasus dasar karena jika pohon adalah nol, tidak ada yang dapat dilakukan.
Hanya mengembalikan kode keras nilai palsu.
>> Bagian bawah cabang adalah semacam default, dimana jika kita sudah diperiksa untuk
null, kami telah memeriksa jika harus kiri, tapi itu tidak boleh, kami telah
diperiksa jika harus tepat, tetapi tidak boleh, jelas itu harus
tepat di mana kita berada.
Itu kasus dasar.
Jadi ada dua kasus rekursif terjepit ada di tengah.
Tapi aku bisa menulis ini dalam urutan apapun.
Saya hanya berpikir itu agak merasa alami untuk pertama memeriksa untuk kesalahan yang mungkin,
kemudian memeriksa kiri, kemudian memeriksa kanan, kemudian berasumsi bahwa Anda berada di node
Anda benar-benar mencari.
>> Jadi mengapa hal ini menjadi berguna?
Jadi ternyata -
dan biarkan aku melompat ke teaser di sini yang ada di web.
Kita akan mulai menggunakan bukan bahasa pemrograman pada awalnya, tetapi
markup language.
Sebuah bahasa markup menjadi salah satu yang semangat yang sama pemrograman
bahasa, tetapi tidak memberikan kemampuan untuk mengekspresikan diri secara logis.
Ini hanya memberi Anda kemampuan untuk mengekspresikan diri secara struktural.
>> Di mana Anda ingin menempatkan sesuatu pada halaman, halaman web?
Warna apa yang Anda ingin membuatnya?
Apa ukuran font yang Anda ingin membuatnya?
Apa kata-kata yang Anda benar-benar inginkan pada halaman web?
Jadi itulah bahasa markup.
Tapi kemudian kami akan sangat cepat memperkenalkan JavaScript, yang merupakan penuh
bahasa pemrograman.
Sangat mirip dalam penampilan sintaktis ke C, tapi itu akan memiliki beberapa
bagus, lebih kuat, lebih fitur ramah pengguna.
>> Dan salah satu frustrasi ini titik dalam semester adalah bahwa kita akan
segera menerapkan ejaan dalam jauh lebih sedikit baris kode menggunakan bahasa lain
daripada C sendiri memungkinkan, tapi untuk alasan yang kita akan segera mengerti.
Ini akan menjadi yang pertama halaman web tersebut.
Ini akan benar-benar underwhelming, yang pertama kita buat.
Ini hanya akan berkata, hello world.
Tetapi jika Anda belum pernah melihatnya sebelumnya, ini adalah HTML,
HyperText Markup Language.
>> Jika Anda pergi ke opsi menu tertentu dalam kebanyakan browser, pada setiap halaman web pada
internet, Anda dapat melihat HTML bahwa beberapa orang menulis kepada
membuat halaman web.
Dan mungkin tidak terlihat sebagai singkat atau serapi ini.
Tapi itu akan mengikuti pola ini kurung terbuka dan garis miring dan
huruf dan angka berpotensi.
>> Saya pikir saya akan memberikan menggoda Anda dari apa yang Anda akan mampu melakukan
setelah mengambil CS50.
Biarkan aku pergi ke cs.harvard.edu / rob, homepage kita sendiri Rob Bowden ini.
Dia membuat ini untuk kita.
Jadi, Anda akan segera dapat melakukan itu.
Dan juga, apa yang Anda dengar pagi ini -
apa yang Anda dengar pagi ini -
>> [HAMSTER DANCE MUSIC]
>> - Anda dapat membuat ini.
Yang menanti kita pada hari Rabu.
Kita akan melihat Anda kemudian.
>> [HAMSTER DANCE MUSIC]
DAVID Malan: Pada CS50 berikutnya -