Doug LLOYD: Jadi di CS50, kita telah membahas banyak struktur data yang berbeda, benar? Kami telah melihat array, dan terkait daftar, dan tabel hash, dan mencoba, tumpukan dan antrian. Kami juga akan belajar sedikit tentang pohon dan tumpukan, tapi benar-benar ini semua hanya berakhir sampai menjadi variasi pada tema. Benar-benar ada ini jenis empat ide dasar bahwa segala sesuatu yang lain dapat mendidih ke. Array, daftar link, tabel hash, dan mencoba. Dan seperti saya katakan, ada variasi pada mereka, tapi ini cukup banyak terjadi untuk meringkas segala sesuatu yang kita akan berbicara tentang di kelas ini dalam hal C. Tapi bagaimana ini semua ukuran, kan? Kami telah berbicara tentang pro dan kontra masing-masing dalam video terpisah pada mereka, tapi ada banyak nomor mendapatkan dilemparkan sekitar. Ada banyak umum pikiran mendapatkan dilemparkan sekitar. Mari kita coba dan mengkonsolidasikan menjadi hanya satu tempat. Mari kita menimbang pro terhadap kontra, dan mempertimbangkan yang struktur data mungkin data yang benar struktur untuk situasi khusus Anda, apa pun jenis data yang Anda menyimpan. Anda tidak perlu selalu perlu menggunakan penyisipan super cepat, penghapusan, dan pencarian dari trie jika Anda benar-benar tidak peduli tentang memasukkan dan menghapus terlalu banyak. Jika Anda hanya perlu cepat acak Akses, mungkin array lebih baik. Jadi mari kita menyaring itu. Mari kita bicara tentang masing-masing empat jenis utama dari struktur data yang kita bicarakan, dan hanya melihat ketika mereka mungkin baik, dan ketika mereka mungkin tidak begitu baik. Jadi mari kita mulai dengan array. Jadi penyisipan, itu semacam buruk. 

Penyisipan pada akhir array adalah OK, jika kita sedang membangun sebuah array seperti yang kita pergi. Tetapi jika kita harus memasukkan unsur ke tengah, berpikir kembali ke penyisipan macam, ada banyak pergeseran untuk menyesuaikan elemen di sana. Dan jadi jika kita akan memasukkan mana saja tapi akhir array, itu mungkin tidak begitu besar. 

Demikian pula, penghapusan, kecuali kami menghapus dari akhir array, mungkin juga tidak begitu besar jika kita tidak ingin meninggalkan celah kosong, yang biasanya kita lakukan tidak. Kami ingin menghapus elemen, dan maka semacam membuatnya snug lagi. Dan menghapus elemen dari array, juga tidak begitu besar. 

Lookup, meskipun, adalah besar. Kami memiliki akses random, konstan lookup waktu. Kami hanya mengatakan tujuh, dan kami pergi array relokasi tujuh. Kita mengatakan 20, dengan pergi ke Array relokasi 20. Kami tidak perlu iterate seluruh. Itu cukup bagus. 

Array juga relatif mudah untuk menyortir. Setiap kali kita berbicara tentang pemilahan sebuah algoritma, seperti pemilihan semacam, insertion sort, bubble sort, menggabungkan semacam, kami selalu menggunakan array untuk melakukannya, karena array cukup mudah untuk semacam, relatif terhadap struktur data kita lihat sejauh ini. 

Mereka juga relatif kecil. Tidak ada banyak ruang ekstra. Anda hanya menyisihkan persis sebanyak yang Anda butuhkan untuk menyimpan data Anda, dan itu cukup banyak itu. Jadi mereka cukup kecil dan efisien dengan cara itu. Tapi downside lain, meskipun, adalah bahwa mereka tetap dalam ukuran. Kita harus menyatakan persis bagaimana besar kita ingin array kita menjadi, dan kami hanya punya satu kesempatan itu. Kita tidak dapat tumbuh dan menyusut. 

Jika kita perlu tumbuh atau menyusut itu, kami perlu mendeklarasikan array yang sama sekali baru, menyalin semua elemen dari pertama array ke dalam array kedua. Dan jika kita salah perhitungan yang waktu, kita perlu melakukannya lagi. Tidak begitu besar. Jadi array tidak memberikan fleksibilitas untuk memiliki nomor variabel elemen. 

Dengan linked list, penyisipan cukup mudah. Kami hanya taktik ke depan. Penghapusan ini juga cukup mudah. Kita harus menemukan unsur-unsur. Yang melibatkan beberapa pencarian. 

Tetapi sekali Anda telah menemukan elemen Anda sedang mencari, semua yang perlu Anda lakukan adalah mengubah pointer, mungkin dua jika Anda memiliki a terkait list-- sebuah ganda linked list, rather-- dan kemudian Anda hanya dapat membebaskan node. Anda tidak perlu menggeser segala sesuatu di sekitar. Anda hanya mengubah dua pointer, jadi itu cukup cepat. 

Lookup buruk sekalipun, kan? Agar kita untuk menemukan elemen dalam linked list, apakah tunggal atau ganda terkait, kita harus linier mencari itu. Kita harus mulai dari awal dan bergerak akhirnya, atau mulai bergerak akhir ke awal. Kami tidak memiliki akses acak lagi. Jadi jika kita melakukan banyak pencarian, mungkin linked list tidak begitu baik bagi kita. 

Mereka juga benar-benar sulit untuk memilah, kan? Satu-satunya cara Anda bisa benar-benar memilah linked list adalah untuk mengatasinya seperti yang Anda membangun itu. Tetapi jika Anda mengatasinya seperti yang Anda membangun itu, Anda tidak lagi membuat sisipan cepat lagi. Anda tidak hanya memaku hal ke depan. Anda harus menemukan tempat yang tepat untuk meletakkannya, dan kemudian penyisipan Anda menjadi hanya tentang buruknya sebagai memasukkan ke dalam sebuah array. Jadi daftar terkait tidak begitu besar untuk menyortir data. 

Mereka juga cukup kecil, ukuran-bijaksana. Ganda terkait daftar sedikit lebih besar dari daftar tunggal terkait, yang sedikit lebih besar dari array, tapi tidak sejumlah besar ruang kosong. Jadi jika ruang adalah pada premium, tapi bukan premium benar-benar intens, ini mungkin menjadi cara yang tepat untuk pergi. 

Tabel hash. Penyisipan ke dalam tabel hash cukup mudah. Ini adalah proses dua langkah. Pertama kita perlu menjalankan data kami melalui fungsi hash untuk mendapatkan kode hash, dan kemudian kita memasukkan unsur ke dalam tabel hash pada lokasi kode hash. 

Penghapusan, mirip dengan linked list, mudah setelah Anda menemukan elemen. Anda harus menemukan pertama, tapi kemudian ketika Anda menghapusnya, Anda hanya perlu untuk bertukar beberapa pointer, jika Anda menggunakan chaining terpisah. Jika Anda menggunakan menyelidik, atau jika Anda tidak menggunakan chaining sama sekali dalam tabel hash Anda, penghapusan sebenarnya sangat mudah. Yang perlu Anda lakukan adalah hash data, dan kemudian pergi ke lokasi tersebut. Dan dengan asumsi Anda tidak memiliki tabrakan, Anda akan dapat menghapus sangat cepat. 

Sekarang, lookup mana hal-hal mendapatkan sedikit lebih rumit. Ini rata-rata yang lebih baik dari daftar terkait. Jika Anda menggunakan chaining, Anda masih memiliki daftar link, yang berarti Anda masih memiliki pencarian merugikan linked list. Tetapi karena Anda mengambil terkait Anda daftar dan memisahkan lebih dari 100 atau 1000 atau n elemen dalam tabel hash Anda, Anda daftar terkait semua adalah satu-n ukuran. Mereka semua secara substansial lebih kecil. Anda telah n terkait daftar bukannya dari salah satu daftar link dari ukuran n. 

Dan begitu nyata-dunia ini konstan faktor, yang we umumnya tidak berbicara tentang kompleksitas waktu, tidak benar-benar membuat perbedaan di sini. Jadi lookup masih linear pencarian jika Anda menggunakan chaining, tapi panjang daftar Anda mencari melalui sangat, sangat singkat dengan perbandingan. Sekali lagi, jika Anda adalah pemilahan tujuan di sini, tabel hash ini mungkin bukan cara yang tepat untuk pergi. Hanya menggunakan sebuah array jika pemilahan benar-benar penting bagi Anda. 

Dan mereka dapat menjalankan keseluruhan dari ukuran. Sulit untuk mengatakan apakah tabel hash kecil atau besar, karena itu benar-benar tergantung pada seberapa besar tabel hash Anda. Jika Anda hanya akan menyimpan lima unsur dalam tabel hash Anda, dan Anda memiliki tabel hash dengan 10.000 elemen di dalamnya, Anda mungkin membuang-buang banyak ruang. Kontras yang Anda dapat juga memiliki tabel hash sangat kompak, tapi tabel hash Anda lebih kecil mendapat, yang masing-masing terhubung daftar lagi mendapat. Dan sehingga benar-benar ada cara untuk mendefinisikan persis ukuran tabel hash, tapi mungkin aman mengatakan itu umumnya akan menjadi lebih besar dari yang terkait Daftar menyimpan data yang sama, tetapi lebih kecil dari trie. 

Dan mencoba adalah keempat struktur ini bahwa kita telah berbicara tentang. Memasukkan ke dalam trie adalah kompleks. Ada banyak dinamis alokasi memori, terutama di awal, karena Anda mulai membangun. Tapi itu waktu yang konstan. Ini hanya unsur manusia di sini yang membuatnya rumit. Harus menghadapi pointer null, malloc ruang, pergi ke sana, ruang mungkin malloc dari sana lagi. Semacam faktor intimidasi dari pointer di alokasi memori dinamis adalah rintangan untuk menghapus. Tapi setelah Anda sudah membersihkan itu, penyisipan sebenarnya berasal cukup sederhana, dan tentu waktu yang konstan. 

Penghapusan mudah. Yang perlu Anda lakukan adalah menavigasi turun beberapa petunjuk dan bebas node, jadi itu cukup bagus. Lookup juga cukup cepat. Itu hanya berdasarkan panjang data Anda. Jadi, jika semua data Anda lima senar karakter, misalnya, Anda menyimpan lima karakter string dalam trie Anda, hanya membutuhkan waktu lima langkah untuk menemukan apa yang Anda cari. Lima hanyalah faktor konstan, sehingga lagi, penyisipan, penghapusan, dan lookup di sini adalah semua waktu yang konstan, secara efektif. 

Hal lain adalah bahwa trie Anda sebenarnya jenis yang sudah disortir, kan? Berdasarkan bagaimana kami memasukkan unsur-unsur, dengan pergi huruf demi huruf dari kunci, atau digit dengan digit kunci, biasanya, trie Anda akhirnya menjadi jenis diurutkan sebagai Anda membangun itu. Itu tidak benar-benar membuat akal untuk berpikir tentang pemilahan dengan cara yang sama kita berpikir tentang dengan array, atau daftar link, atau tabel hash. Tapi dalam beberapa hal, Anda trie diurutkan sebagai Anda pergi. 

Sisi negatifnya, tentu saja, adalah bahwa trie cepat menjadi besar. Dari setiap titik persimpangan, Anda mungkin have-- jika kunci Anda terdiri dari digit, Anda memiliki 10 lainnya tempat Anda bisa pergi, yang berarti bahwa setiap simpul berisi informasi tentang data yang Anda ingin menyimpan pada saat itu node, ditambah 10 pointer. Yang, pada CS50 IDE, adalah 80 byte. Jadi itu setidaknya 80 byte untuk setiap node yang Anda buat, dan itu bahkan tidak menghitung data. Dan jika node Anda huruf bukan angka, sekarang Anda memiliki 26 pointer dari setiap lokasi. Dan 26 kali 8 mungkin 200 byte, atau sesuatu seperti itu. Dan Anda memiliki modal dan lowercase-- Anda dapat melihat di mana aku akan dengan ini, kan? Node Anda bisa benar-benar besar, dan trie itu sendiri, secara keseluruhan, bisa mendapatkan benar-benar besar, juga. Jadi jika ruang adalah pada tinggi premi pada sistem Anda, trie mungkin bukan cara yang tepat untuk pergi, meskipun manfaat lainnya ikut bermain. Aku Doug Lloyd. Ini adalah CS50.