DOUG LLOYD: Belə ki, CS50, biz əhatə etdik müxtəlif data strukturları bir çox, sağ? Biz Diziler görünür və bağlı etdik siyahıları, və hash masalar, və çalışır, bacalar və sıralarında. Biz də bir az öyrənmək lazımdır ağac və vaxt haqqında lakin, həqiqətən, bu bütün yalnız son up mövzusunda varyasyonları olan. Həqiqətən var bu dörd əsas fikir cür başqa hər şey aşağı qaynatmaq bilər. Diziler, bağlı siyahıları, hash masalar və çalışır. Və kimi orada ifadə edərək, onlara varyasyonları, lakin bu olduqca qədər yekunlaşdırmaq niyyətində hər şey danışmaq olacaq C. baxımından bu sinif haqqında Amma necə bu doğru, bütün tədbir up edirsiniz? Biz lehte ve eksiklikleri haqqında söhbət etdik onlara ayrı-ayrı video hər, lakin nömrələri bir çox var ətrafında atılan almaq. Ümumi bir çox var fikirlər ətrafında atılan almaq. Nin cəhd və birləşdirmək edək yalnız bir yerdə. Nin qarşı müsbət çəkin edək eksiklikleri, və hesab olan data structure Sağ data ola bilər xüsusi vəziyyət üçün strukturu, məlumatların nə cür saxlanılması edirik. Siz mütləq həmişə ehtiyac yoxdur , super sürətli durub, silinməsi istifadə bir trie və axtarış əgər həqiqətən daxil və silmə haqqında qayğı yoxdur həddindən artıq çox. Yalnız tez təsadüfi ehtiyac varsa giriş, bəlkə bir sıra daha yaxşıdır. Belə ki, çəkmək edək. Dörd hər biri haqqında danışmaq edək data strukturları əsas növ biz danışdıq və etdik ki, Onlar yaxşı ola bilər zaman yalnız görmək, və onlar belə yaxşı ola bilər. Belə ki, Diziler ilə başlamaq edək. Durub Belə ki, bu cür pis. 

Bir sıra sonunda durub, OK biz getmək kimi biz bir sıra tikinti edirsinizsə. Amma biz daxil etmək lazımdır, əgər orta elementləri, durub geri edirəm sort, bir çox var orada bir element uyğun dəyişir. Və biz daxil olacaq əgər hər hansı lakin bir sıra sonu, yəqin ki, belə böyük deyil. 

Eynilə, silinməsi, əgər biz istəyirik bir sıra sonunda silmə, yəqin ki, həmçinin əgər belə böyük deyil biz boş boşluqları tərk etmək istəmirəm, adətən biz deyil. Biz bir element aradan qaldırılması istəyirsinizsə, və sonra sort yenidən rahat edir. Və belə elementləri silmə bir sıra da o qədər də böyük deyil. 

Axtarış, baxmayaraq ki, böyükdür. Biz təsadüfi imkanı var, daimi vaxt Sistemi. Biz yalnız yeddi demək, və biz getmək array köçürülməsi yeddi. Biz yolda ilə 20 demək array köçürülməsi 20. Biz arasında təkrarlamaq yoxdur. Bu olduqca yaxşı. 

Diziler də düzmək üçün nisbətən asandır. Biz çeşidlənməsi haqqında danışdı Hər zaman Belə seçim sort kimi alqoritm, durub sort, bubble sort, birləşməsi sort, biz həmişə bunu Diziler istifadə Diziler olduqca asandır, çünki data strukturları nisbətən sort, Biz bu günə qədər gördüm. 

Onlar həmçinin nisbətən kiçik istəyirik. Əlavə yer bir çox deyil. Siz yalnız tam olaraq çox kənara sizin data keçirmək lazımdır ki, və bu olduqca çox var. Belə ki, onlar olduqca kiçik istəyirik, və o şəkildə səmərəli. Amma başqa İşin mənfi tərəfi odur, baxmayaraq ki, Onlar ölçüsü müəyyən olunur. Biz necə dəqiq elan var big biz array olmaq istəyirəm və biz yalnız bir shot almaq. Biz inkişaf və shrink bilməz. 

Biz bunu inkişaf və ya shrink ehtiyac varsa, biz tamamilə yeni array bəyan etmək lazımdır, elementlərinin bütün surəti ikinci sıra ilk array. Və biz miscalculated əgər vaxt, biz yenə bunu etmək lazımdır. Belə böyük deyil. Belə ki, seriallarda, bizə rahatlıq vermir elementlərin dəyişən nömrələri var. 

Bir bağlı siyahı ilə, durub olduqca asandır. Biz yalnız qarşısında üzərinə tack. Deletion də olduqca asandır. Biz elementləri tapmaq lazımdır. Ki, bir axtarış daxildir. 

Amma element gördük Siz nə etmək lazımdır Bütün aradığınız bir göstərici dəyişdirmək deyil, bəlkə iki varsa bir ikiqat list-- bağlıdır bağlı siyahısı, rather-- və sonra yalnız node azad edə bilər. Siz keçmək yoxdur ətrafında hər şey. Siz yalnız iki göstəricilərinə dəyişə belə ki, olduqca sürətli var. 

Axtarış doğru olsa pis? Bizə bir tapmaq üçün üçün bir bağlı siyahısında element, olub story və ya ikiqat, bağlı biz axtarış xətti var. Biz əvvəlində başlamaq lazımdır və son hərəkət, və ya son hərəkət-da başlayacaq əvvəlinə. Biz artıq təsadüfi çıxışı yoxdur. Biz edirik Belə ki axtarış çox, bəlkə bir bağlı siyahısı deyil bizim üçün kifayət qədər yaxşı. 

Onlar, həqiqətən, də istəyirik düzmək üçün çətin, sağ? yeganə yolu siz həqiqətən bağlı siyahı düzmək Siz onu tikmək kimi düzmək üçün. Amma sizin kimi bu sort əgər onu tikintisi, artıq istəyirik Artıq tez insertions edilməsi. Siz yalnız tacking deyilik qarşısında üzərinə şeylər. Siz tapmaq lazımdır sağ spot qoymaq üçün, və sonra durub yalnız pis olur bir sıra daxil daxil kimi. Belə ki, bağlı siyahıları deyil məlumat çeşidlənməsi üçün belə böyük. 

Onlar həmçinin olduqca kiçik, ölçüsü-müdrik istəyirik. Ikiqat az siyahısını bağlıdır story bağlı siyahıları daha böyük, olan qədər böyük Diziler daha lakin bu deyil sərf kosmik böyük məbləği. Belə ki, əgər yer bir mükafat, lakin Biz, həqiqətən sıx premium, Bu getmək üçün doğru yol ola bilər. 

Hash masalar. Bir hash masa durub kifayət qədər sadə deyil. Bu iki addım prosesi var. Birinci biz vasitəsilə data run lazımdır bir hash funksiyası hash kodu almaq üçün, və sonra daxil element daxil ki, hash kodu yerdə hash masa. 

Bağlı siyahı oxşar Deletion, Siz element tapmaq bir dəfə asandır. Siz ilk tapmaq lazımdır lakin sonra onu silmək zaman, Yalnız mübadiləsi etmək lazımdır göstəricilərinə bir neçə Əgər ayrı-ayrı chaining istifadə edirik. Siz probing istifadə edirsinizsə, və ya değilseniz istifadə edərək, bütün chaining Sizin hash masa, silinməsi, həqiqətən, həqiqətən asandır. Siz nə etmək lazımdır Bütün hash edir data, sonra yere gedin. Və fərz siz deyil Hər hansı bir toqquşma var çox tez silmək mümkün olacaq. 

İndi axtarış harada şeyi edir bir az daha mürəkkəb almaq. Bu daha yaxşı orta hesabla var bağlı siyahıları çox. Siz zəncirləmə istifadə edirsinizsə, Siz hələ bir bağlı siyahı var, siz hələ var deməkdir Axtarış bağlı siyahı zərərinə. Siz alaraq edirik, çünki ancaq bağlıdır siyahısı və 100 və ya 1000-dən artıq parçalanması və ya n sizin hash cədvəldə elementləri, etdiyiniz bağlı siyahıları ölçüsü nth bütün biridir. Onlar bütün əhəmiyyətli dərəcədə kiçik istəyirik. Siz n əvəzinə siyahıları bağlıdır ölçüsü n biri bağlı siyahı. 

Və bu real-dünya daimi Ümumiyyətlə, biz amil, vaxt mürəkkəbliyi haqqında danışmaq deyil, onu həqiqətən, burada bir fərq yoxdur. Belə ki, axtarış hələ xətti Siz zəncirləmə kullanıyorsanız axtarış lakin siyahısı uzunluğu Siz vasitəsilə axtarış edirik Müqayisə çox, çox qısa. Yenə çeşidlənməsi əgər Burada məqsəd, hash table nin yəqin ki, doğru yol getmək üçün deyil. Çeşidlənməsi, yalnız bir sıra istifadə sizin üçün həqiqətən vacibdir. 

Onlar ölçüsü gamut çalıştırabilirsiniz. Bu söyləmək çətindir hash table, kiçik və ya böyük bu, həqiqətən asılıdır necə böyük sizin hash masa. Yalnız saxlanılması olacaq edirsinizsə Sizin hash masa beş elementləri, və bir hash masa var bu 10.000 elementləri ilə, Siz yəqin ki, yer çox israf edirik. Kontrast də bilər olan , çox yığcam hash masalar var lakin kiçik Sizin hash masa olur bu bağlı siyahıları hər artıq olur. Və belə ki, həqiqətən müəyyən etmək üçün heç bir yol var dəqiq bir hash masa ölçüsü, lakin yəqin ki, güvenli ümumiyyətlə demək Bir bağlı daha böyük olacaq Eyni data saxlanılması siyahısı bir trie daha lakin kiçik. 

Və çalışır dördüncü var bu strukturların ki, biz söhbət etdik. Bir trie daxil daxil mürəkkəbdir. Dinamik bir çox var yaddaş ayrılması, xüsusilə əvvəlində, Siz qurmaq üçün başlanğıc etdiyiniz kimi. Amma bu, daimi vaxt var. Bu, yalnız insan element var burada çətin ki. Null göstərici qarşılaşmağa olan malloc space, bəlkə malloc yer getmək oradan yenidən. qorxudulması amilinin sort dinamik yaddaş ayrılması göstəricilər sil mane deyil. Amma siz bunu tip sonra, durub həqiqətən, olduqca sadə gəlir və əlbəttə ki, daimi vaxt. 

Deletion asandır. Siz nə etmək lazımdır Bütün aşağı gedin bir göstəricilər və node neçə, belə ki, olduqca yaxşı. Lookup də olduqca sürətli edir. Bu, yalnız əsasında Sizin data uzunluğu. Sizin data bütün əgər Belə ki, Beş xarakter strings, məsələn, beş saxlanılması edirik Sizin trie xarakter strings, yalnız beş addımlar atır Aradığınız nə tapa bilərsiniz. Beş, belə ki, yalnız bir sabit amildir yenə durub, silinməsi, və axtarış burada səmərəli, bütün daimi zaman var. 

Başqa bir şey sizin trie olduğunu həqiqətən cür artıq sağ, sıralanır? Biz ne əsasında daxil elementləri, bir məktub məktubu gedən əsas pillə əsas və ya rəqəmli, adətən, sizin trie olan qədər başa Siz qurmaq kimi cür sıralanır. Bu, həqiqətən edir deyil mənada çeşidlənməsi haqqında düşünmək eyni şəkildə biz düşünmək Bu serialların və ya bağlı siyahıları ilə, və ya hash masalar. Lakin bəzi mənada, sizin Siz getmək kimi trie çeşidlənir. 

İşin mənfi tərəfi odur, əlbəttə ki, bir trie sürətlə böyük olur. Hər qovşağında baxımdan, siz bilər əsas rəqəmdən ibarətdir əgər yaxşıdır, digər 10 var yerlərdə getmək bilər ki, hər node o deməkdir ki, məlumat var məlumatların saxlamaq istəyirəm ki node, plus 10 göstəricilər də. Hansı CS50 IDE on 80 bayt edir. Belə ki, ən azı 80 bayt var Yaratmaq hər node, və hətta data sayılması deyil. Və qovşaqlarının, əgər əvəzinə rəqəm məktublar, indi 26 göstəricilərinə var hər yerdən. Və 26 dəfə 8 yəqin ki, 200 bytes, və ya kimi bir şey. Və kapitalı var və siz lowercase-- Mən bu ilə gedirəm harada sağ, görmək? Sizin qovşaqlarının həqiqətən əldə edə bilərsiniz böyük və belə trie özü, ümumi, bilərsiniz çox, həqiqətən böyük almaq. Space yüksək olduğu halda belə sistem mükafat, bir trie doğru yol ola bilər hətta digər faydaları olsa da, getmək oyun minir. Mən Doug Lloyd edirəm. Bu CS50 edir.