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