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