DOUG LLOYD: Jadi dalam CS50, kami telah dilindungi banyak struktur data yang berbeza, bukan? Kami telah melihat array, dan dikaitkan senarai dan jadual hash, dan percubaan, susunan dan beratur. Kami juga akan belajar sedikit mengenai pokok dan timbunan, tetapi benar-benar ini semua hanya berakhir sehingga menjadi variasi pada tema. Ada benar-benar ini jenis empat idea-idea asas semua yang lain boleh mendidih ke. Tatasusunan, senarai berkaitan, jadual hash, dan cuba. Dan seperti yang saya katakan, terdapat variasi kepada mereka, tetapi ini adalah cukup banyak berlaku untuk meringkaskan semua yang kita akan bercakap kira-kira dalam kelas ini dari segi C. Tetapi bagaimana ini semua langkah, bukan? Kami telah berbincang mengenai kebaikan dan keburukan setiap dalam video berasingan ke atas mereka, tetapi ada banyak nombor mendapat dibuang di sekitar. Ada banyak umum Pemikiran mendapat dibuang di sekitar. Mari kita cuba dan menyatukan ia ke dalam hanya satu tempat. Mari kita menimbang kebaikan terhadap kontra, dan mempertimbangkan mana struktur data mungkin data yang betul struktur bagi keadaan tertentu anda, apa jua jenis data anda menyimpan. Anda tidak semestinya sentiasa perlu menggunakan pemasukan super cepat, penghapusan, dan lookup daripada indone jika anda benar-benar tidak mengambil berat tentang memasukkan dan memotong terlalu banyak. Jika anda perlukan hanya cepat rawak akses, mungkin array adalah lebih baik. Jadi mari kita menyuling itu. Mari kita bercakap tentang setiap satu daripada empat jenis utama struktur data bahawa kita telah bercakap tentang, dan hanya melihat ketika mereka mungkin baik, dan apabila mereka mungkin tidak begitu baik. Jadi mari kita mulakan dengan pameran. Jadi kemasukan, itu jenis yang tidak baik. 

Insertion pada akhir array OK, jika kita membina array seperti yang kita pergi. Tetapi jika kita perlu memasukkan unsur-unsur ke tengah, berfikir kembali kepada sisipan jenis, ada banyak beralih untuk muat unsur di sana. Dan jadi jika kita akan memasukkan mana-mana sahaja tetapi akhir array, itu mungkin tidak begitu besar. 

Begitu juga, penghapusan, kecuali kita memotong dari akhir array, mungkin juga tidak begitu besar jika kita tidak mahu meninggalkan jurang kosong, yang biasanya kita tidak. Kami mahu mengeluarkan elemen, dan maka jenis yang nyaman lagi. Dan supaya memotong unsur-unsur dari pelbagai, juga tidak begitu besar. 

Lookup, walaupun, adalah besar. Kami mempunyai akses rawak, masa pencarian yang berterusan. Kami hanya mengatakan tujuh, dan kita pergi kepada pelbagai penempatan semula tujuh. Kita katakan 20, dengan pergi ke lokasi penempatan semula 20. Kami tidak mempunyai untuk melelar seluruh. Yang cukup baik. 

Tatasusunan adalah juga agak mudah untuk menyelesaikan. Setiap kali kita bercakap tentang isihan yang algoritma, seperti jenis pemilihan, jenis kemasukan, jenis gelembung, bergabung jenis, kita sentiasa menggunakan tatasusunan untuk melakukannya, kerana tatasusunan adalah agak mudah untuk jenis, relatif kepada struktur data kita lihat setakat ini. 

Mereka juga agak kecil. Tidak ada banyak ruang tambahan. Anda hanya mengetepikan tepat seperti yang banyak kerana anda perlu untuk memegang data anda, dan itu cukup banyak ia. Jadi mereka cukup kecil dan cekap dengan cara itu. Tetapi Kelemahan lain, walaupun, adalah bahawa mereka tetap dalam saiz. Kita perlu mengisytiharkan tepat bagaimana besar kita mahu pelbagai kami menjadi, dan kami hanya mendapatkan satu pukulan di dalamnya. Kita tidak boleh berkembang dan mengecut ia. 

Jika kita perlu berkembang atau mengecut, kita perlu mengisytiharkan pelbagai yang baru, menyalin semua unsur-unsur lokasi pertama ke lokasi kedua. Dan jika kita salah mengira bahawa masa, kita perlu melakukannya sekali lagi. Tidak begitu besar. Jadi tatasusunan tidak memberikan kita fleksibiliti untuk mempunyai nombor berubah unsur-unsur. 

Dengan senarai berpaut, kemasukan adalah agak mudah. Kami hanya jelujur ke hadapan. Penghapusan adalah juga agak mudah. Kita perlu mencari unsur-unsur. Yang melibatkan beberapa pencarian. 

Tetapi sebaik sahaja anda memperolehi unsur anda cari, semua yang perlu anda lakukan adalah menukar penunjuk, mungkin dua jika anda mempunyai berpaut list-- duanya adalah terpakai senarai bersambung, rather-- dan kemudian anda hanya boleh membebaskan nod. Anda tidak perlu untuk beralih segala-galanya di sekeliling. Anda hanya menukar dua petunjuk, jadi itu agak cepat. 

Lookup tidak baik walaupun, bukan? Dalam usaha untuk kita untuk mencari elemen dalam senarai berpaut, sama ada secara tunggal atau ganda berkaitan, kita perlu linear mencari ia. Kita perlu bermula pada awal dan bergerak tamat, atau bermula dari langkah akhir untuk permulaan. Kami tidak mempunyai capaian rawak lagi. Jadi, jika kita sedang melakukan banyak mencari, mungkin senarai berpaut tidak begitu baik untuk kita. 

Mereka juga benar-benar sukar untuk menyelesaikan, bukan? Satu-satunya cara yang anda boleh benar-benar menyusun senarai berpaut adalah untuk menyusun ia seperti yang anda membina ia. Tetapi jika anda menyusun ia seperti yang anda membina, anda tidak lagi membuat sisipan cepat lagi. Anda tidak hanya tacking perkara ke hadapan. Anda perlu mencari tempat yang betul untuk meletakkan ia, dan kemudian memasukkan anda menjadi hanya kira-kira sebagai lapuk seperti memasukkan ke dalam array. Jadi senarai berkaitan tidak begitu besar untuk menyusun data. 

Mereka juga agak kecil, saiz Bijaksana. Senarai duanya adalah terpakai dikaitkan sedikit lebih besar daripada senarai secara tunggal berkaitan, yang lebih besar daripada tatasusunan, tetapi ia tidak sejumlah besar ruang sia-sia. Jadi, jika ruang adalah pada premium, tetapi tidak premium yang benar-benar kuat, mungkin ini cara yang betul untuk pergi. 

Jadual hash. Memasukkan ke dalam jadual hash adalah agak mudah. Ia adalah satu proses dua langkah. Mula-mula kita perlu untuk menjalankan data kami melalui fungsi hash untuk mendapatkan kod hash, dan kemudian kita memasukkan elemen ke dalam jadual hash di lokasi itu kod hash. 

Penghapusan, sama dengan senarai bersambung, mudah sebaik sahaja anda mencari unsur. Anda perlu mencari ia pertama, tetapi kemudian apabila anda memadamnya, anda hanya perlu untuk bertukar-tukar beberapa petunjuk, jika anda menggunakan chaining berasingan. Jika anda menggunakan menyelesaikan sesuatu, atau jika anda tidak menggunakan chaining di semua dalam jadual hash anda, penghapusan adalah benar-benar sangat mudah. Semua yang anda perlu lakukan adalah hash yang data, dan kemudian pergi ke lokasi tersebut. Dan menganggap anda tidak mempunyai apa-apa perlanggaran, anda boleh memadam dengan cepat. 

Sekarang, lookup adalah di mana perkara mendapatkan sedikit lebih rumit. Ia adalah secara purata lebih baik daripada senarai berkaitan. Jika anda menggunakan chaining, anda masih mempunyai senarai berpaut, yang bermakna anda masih mempunyai carian merugikan senarai berpaut. Tetapi oleh kerana anda mengambil dipautkan anda senarai dan membelah ia lebih 100 atau 1,000 atau n unsur-unsur dalam jadual hash anda, anda berada senarai berkaitan semua adalah satu-n saiz. Mereka semua dengan ketara lebih kecil. Anda telah n dikaitkan senarai sebaliknya satu senarai berpaut bersaiz n. 

Dan sebagainya dunia nyata ini berterusan faktor, yang kita umumnya tidak bercakap tentang dalam kerumitan masa, ia tidak benar-benar membuat perbezaan di sini. Jadi lookup masih linear mencari jika anda menggunakan chaining, tetapi panjang senarai anda sedang mencari melalui adalah sangat, sangat pendek oleh perbandingan. Sekali lagi, jika pengasingan adalah anda Matlamat di sini, hash meja itu mungkin bukan cara yang betul untuk pergi. Hanya menggunakan array jika menyusun adalah benar-benar penting kepada anda. 

Dan mereka boleh menjalankan gamut saiz. Adalah sukar untuk mengatakan sama ada yang jadual hash adalah kecil atau besar, kerana ia benar-benar bergantung kepada berapa besar jadual hash anda. Jika anda hanya akan menyimpan lima elemen dalam jadual hash anda, dan anda mempunyai jadual hash dengan 10,000 unsur-unsur di dalamnya, anda mungkin membuang banyak ruang. Kontras yang anda juga boleh mempunyai jadual hash sangat padat, tetapi jadual hash anda yang lebih kecil mendapat, semakin lama setiap orang-orang senarai berkaitan mendapat. Dan sebagainya ada benar-benar ada cara untuk menentukan tepat saiz jadual hash, tetapi ia mungkin selamat untuk mengatakan ia biasanya akan menjadi lebih besar daripada yang dikaitkan senarai menyimpan data yang sama, tetapi lebih kecil daripada indone a. 

Dan cuba yang keempat struktur ini yang kita telah bercakap tentang. Memasukkan ke dalam indone adalah kompleks. Ada banyak yang dinamik peruntukan memori, terutama di awal, kerana anda mula membina. Tetapi ia adalah masa yang berterusan. Ia hanya elemen manusia di sini yang menjadikan ia rumit. Mempunyai untuk menghadapi penunjuk null, malloc ruang, pergi ke sana, ruang mungkin malloc dari sana lagi. Jenis faktor ugutan petunjuk dalam peruntukan memori dinamik adalah halangan untuk membersihkan. Tetapi sebaik sahaja anda telah dibersihkan itu, kemasukan sebenarnya datang agak mudah, dan sudah pasti masa yang berterusan. 

Penghapusan adalah mudah. Semua yang anda perlu lakukan adalah mengemudi ke bawah beberapa petunjuk dan bebas nod, jadi itu cukup baik. Lookup juga cukup cepat. Ia hanya berdasarkan panjang data anda. Jadi, jika semua data anda lima rentetan aksara, sebagai contoh, anda menyimpan lima rentetan aksara di indone anda, ia hanya mengambil masa lima langkah untuk mencari apa yang anda cari. Lima hanya faktor yang tetap, jadi lagi, kemasukan, penghapusan, dan pencarian di sini adalah semua masa yang berterusan, berkesan. 

Satu lagi perkara ialah indone anda sebenarnya jenis sudah disusun, bukan? Menurut bagaimana kami memasukkan unsur-unsur, dengan pergi surat melalui surat daripada utama, atau digit dengan digit kunci, biasanya, indone anda berakhir menjadi jenis disusun seperti yang anda membinanya. Ia tidak benar-benar membuat akal untuk berfikir tentang menyusun dengan cara yang sama kita berfikir tentang dengan tatasusunan atau senarai berkaitan, atau jadual hash. Tetapi dalam erti kata lain, anda indone disusun sebagai anda pergi. 

Kekangan yang timbul, sudah tentu, adalah bahawa indone yang berkembang menjadi besar. Dari setiap titik persimpangan, anda mungkin ada-- jika kunci anda terdiri daripada digit, anda mempunyai 10 lain tempat-tempat yang anda boleh pergi, yang bermakna setiap nod mengandungi maklumat mengenai data yang anda mahu untuk menyimpan di nod, ditambah 10 petunjuk. Yang, pada IDE CS50, adalah 80 bait. Jadi ia adalah sekurang-kurangnya 80 bait untuk setiap nod yang anda buat, dan itu tidak mengira data. Dan jika nod anda adalah surat dan bukannya angka, kini anda mempunyai 26 petunjuk dari setiap lokasi. Dan 26 kali 8 mungkin 200 bait, atau sesuatu seperti itu. Dan anda mempunyai modal dan lowercase-- anda boleh melihat di mana saya akan dengan ini, bukan? Nod anda boleh mendapatkan benar-benar besar, dan sebagainya indone yang sendiri, secara keseluruhan, boleh mendapatkan benar-benar besar, terlalu. Jadi, jika ruang adalah pada paras tertinggi premium pada sistem anda, indone yang mungkin tidak cara yang betul untuk pergi, walaupun manfaatnya lain mula bermain. Saya Doug Lloyd. Ini adalah CS50.