[MUSIC PLAYING]
>> DAVID MALAN: Bu CS50 edir.
Bu başlanğıc və həm də sanki demək olar ki, sonuna kimi lazımdır, çünki
Həftə altı.
>> Mən bölüşmək istədiyiniz düşündüm bir əyləncə fakt az.
Mən bu qədər çıxardı etdik Son semestr data seçin.
Biz hər sizi xahiş ki geri bilər p set form online seyr etdik əgər
və ya şəxs iştirak etdik, əgər.
Və burada data deyil.
Belə ki, bu gün çox gözlənilən idi.
Amma biz bir az sərf istədi zaman sizinlə yenə.
Niyə hər kəs bu zənn istəyirsiniz graph, aşağı, aşağı, belə jaggy edir
belə ardıcıl?
Nə zirvələri hər şeyi və çökəkliklər təmsil edir?
>> Auditoriya: [işitilemez]
DAVID MALAN: Həqiqətən.
Və daha çox gülməli, Allah qorusun, biz bir cümə günü bir mühazirə
semestr əvvəlində, ki, biz nə görürük budur.
Belə ki, bu gün biz bir az iştirak data strukturları haqqında daha çox.
Və bir bərk daha vermək beş problemlərin ruhi model,
indi deyil.
Bad yazımlar, orada, biz will bir mətn faylı əl bəzi 100,000
plus İngilis dili sözlər, və Siz olacaq
Ağılla onları yüklemek üçün necə anlamaq üçün yaddaş daxil, RAM, bəzi data istifadə edərək,
Seçdiyiniz strukturu.
>> İndi belə bir data strukturu bilər olmamalıdır yəqin ki, lakin,
Bu kifayət qədər sadə bağlı siyahı, biz son dəfə təqdim etdi.
Və bir bağlı siyahı azı idi bir sıra üzərində bir üstünlüyü.
Bir üstünlüyü nədir arguably bir bağlı siyahı?
>> Auditoriya: Insertion.
>> DAVID MALAN: Insertion.
Siz nə deməkdir?
>> Auditoriya: Yerdə boyunca siyahısı [Işitilemez].
>> DAVID MALAN: Yaxşı.
Belə ki, bir element yerdə əlavə edə bilərsiniz Siz siyahısı ortasında istəyirik
bir şey shuffle olmadan, Hansı ki, biz sıralayaraq, bağlanmış
müzakirələr deyil mütləq yaxşı bir şey,
Bu vaxt tələb edir, çünki həqiqətən hərəkət bu insan bütün sol və ya sağ.
Və belə bir bağlı siyahısı ilə, siz yalnız malloc ilə ayrılması, yeni node,
və sonra bir neçə yeniləmə göstəricilərinə iki, üç əməliyyatlar max--
və biz kimsə slot edirik siyahısına daxil hər yerdə.
>> Nə sərfəli idi bir bağlı siyahısı haqqında?
Bəli?
>> Auditoriya: [işitilemez]
DAVID MALAN: Perfect.
Perfect.
Bu, həqiqətən dinamik.
Və törətməkdə deyilik ki, əvvəlcədən bəzi sabit ölçüsü
yaddaş yığın, kimi olardı bir sıra ilə, alt üçün olan
Siz yalnız qovşaqlarının ayıra bilər ki, tələb bununla yalnız çox yer istifadə
Siz, həqiqətən, ehtiyac kimi.
Bir sıra fərqli olaraq, siz bilər təsadüfən çox az ayrılması.
Və o, yalnız gedir boyun bir ağrı olmaq
yeni böyük bir sıra təkrar bölüşdürə, surəti hər şey üzərində, köhnə array pulsuz
və sonra iş haqqında hərəkət.
Və ya pis, siz yol ayrılması bilər Siz, həqiqətən, ehtiyac daha çox yaddaş,
və belə bir çox olacaq belə danışmaq, array seyrək əhalinin.
>> Belə ki, bir bağlı siyahı bu verir dinamizm və rahatlıq üstünlükləri
insertions və silme ilə.
Amma şübhəsiz ki, ödənilən qiymət olmalıdır.
Mövzular əslində, bir viktorina sıfır tədqiq
idi ticarət-off bir neçə biz belə uzaq gördüm.
Belə ki, bir ödənişli qiyməti və ya nə bir bağlı siyahı aşağı istiqamətli?
Bəli.
>> Auditoriya: Xeyr təsadüfi giriş.
>> DAVID MALAN: No təsadüfi giriş.
Amma kimin umurunda?
Random access çekici səs deyil.
>> Auditoriya: [işitilemez]
DAVID MALAN: Exactly.
Siz istəyirsinizsə müəyyən bir alqoritm
və mənə həqiqətən təklif edək Xüsusilə ikili axtarış, olan
biz bir bit istifadə etdiyiniz biridir Siz təsadüfi çıxışı yoxdur, əgər,
Siz sadə hesab edə bilməz orta element kimi tapmaq
və ona doğru jumping.
Siz əvəzinə ilk başlamaq üçün element və xətti sol axtarış
sağ tapmaq istəyirsinizsə orta və ya hər hansı digər element.
>> Auditoriya: Bu yəqin ki, daha çox yaddaş tutur.
>> DAVID MALAN: daha çox yaddaş edir.
Harada əlavə edir yaddaş gələn başa?
>> Auditoriya: [işitilemez]
DAVID MALAN: Exactly.
Burada bu halda, biz idi integers üçün bir bağlı siyahı
və hələ biz misli edirik yaddaş həcmi
biz də bu göstəricilərinə saxlamaqla lazımdır.
Kimi bir böyük İndi az Sizin structs böyük almaq
və bir sıra saxlanılması edirik lakin bəlkə bir tələbə və ya digər obyekt.
Amma nöqtə əlbəttə qalır.
Və belə bir sıra əməliyyatları bağlı siyahıları çağırıldı
n xətti böyük O idi.
Taxılması və ya axtarış kimi Things və ya halda bir element silinməsi
çox sonunda oldu Bu sıralanır və ya deyil olub siyahısı.
>> Bəzən uğurlu almaq və bilər bu əməliyyatlar belə aşağı həddi
değilseniz də daimi vaxt ola bilər həmişə ilk element baxaraq,
məsələn.
Amma nəticədə, biz vəd müqəddəs grail nail olmaq üçün
data strukturları, və ya bəzi uyğunlaşdırılması onların,
daimi vaxt yolu ilə.
Biz elementləri tapmaq və ya elementləri əlavə edə bilərsiniz və ya bir siyahıdan elementləri aradan qaldırılması?
Biz kifayət qədər tezliklə görəcəksiniz.
Və bir çıxır Biz istəyirik mexanizmlərinin
Bu gün istifadə başlamaq niyyətindədir, p illik istifadə, beş set
həqiqətən olduqca tanış edir.
Məsələn, bu dəstə əgər imtahan kitab, hər hansı
tələbə ilk var bu və soyadı adı,
Mən onlara ala bir imtahan sonunda,
və onlar bütün olduqca istəyirik təsadüfi qaydada çox,
və biz çeşidlənməsi haqqında getmək istəyirəm Bu imtahanları belə ki, bir dəfə pilləli
yalnız bir çox asan və sürətli onları geri əl
əlifba sırası ilə şagirdlərə.
Sizin instinktlərdən nə olardı bu kimi imtahanları bir qalaq üçün?
>> Yaxşı, siz mənim kimi değilseniz, siz Bu m olduğunu görmək bilər,
mən növ bu qoymaq gedirəm Bu mənim masa və ya mərtəbə tapa əgər
Mən hər şeyi yayılması alıram yazaraq və ya array, həqiqətən
Mən orada Ms bütün qoymaq bilər.
Oh.
Burada A. Mən güc var burada kimi qoydu.
Oh.
Burada gedirəm başqa A. var burada qoymaq.
Burada Z. Burada başqa M. Və belə Mən bu kimi hemoroid edilməsi başlamaq bilər.
Və sonra bəlkə mən sonra getmək istədiyiniz və sort çox nitpicky-ly sort
fərdi hemoroid.
Amma nöqtə görünür bilər Mən əlli edirəm ki, giriş at
və mən bəzi hesablanmışdır edəcək giriş əsasında qərar.
Bu A ilə başlayır, orada qoyun.
A-dan Z ilə başlayır varsa, üzərində qoymaq arasında var, və hər şey.
>> Belə ki, bu ki, bir texnikadır ümumiyyətlə hashing-- H-A-S-H-- kimi tanınan
olan ümumiyyətlə kimi görülməsi deməkdir giriş və hesablamaq üçün daxil etmədən istifadə edərək
dəyəri, ümumiyyətlə sayı, və ki, sayı saxlama daxil indeksi
konteyner, bir sıra kimi.
Belə ki, başqa sözlə, mən bir ola bilər hash funksiyası, mən baş nə kimi,
Mən kimsə görmək ki A ilə başlayır edən adı,
Mən xəritəyə gedirəm mənim baş sıfır.
Mən Z kimsə görmək əgər, mən deyiləm başım 25 xəritəsi gedir
və sonra daxil qoymaq sonuncu ən qalaq.
>> İndi, əgər mənim beyin deyil düşünmək lakin bir C proqram, nə nömrələri bilər
Siz eyni nəticə əldə etmək üçün etibar?
Başqa sözlə, əgər ASCII xarakter idi
necə müəyyən edirsiniz nə bucket qoymaq?
Siz yəqin ki, istəmirəm bucket 65, onu qoymaq
orada kimi olacaq heç bir yaxşı səbəbdən.
Harada A qoymaq istəyirəm onun ASCII dəyəri baxımından?
Harada onun ASCII üçün nə etmək istəyirəm dəyəri asan bucket ilə gəlmək
qoymaq?
>> Auditoriya: Minus A.
>> DAVID MALAN: Bəli.
Belə ki, minus A və ya mənfi xüsusi 65 bu əgər
kapital A. Or 98 əgər bir kiçik bir var.
Və belə ki, çox, bizə imkan verir sadəcə və çox arithmetically,
kimi bir vedrə bir şey qoymaq.
Belə ki, biz, həqiqətən, nə çıxır Bu həmçinin belə sınavlar ilə.
>> Belə ki, siz dairəvi geri bilər sizin qapağında tədris fellow adı.
Və TF-nin adları təşkil edildi əlifba sırası ilə Bu sütun,
yaxşı, iman və ya, zaman hamımız 80 plus
sinifə, digər gecə birlikdə var Bizim grading prosesi son addım
böyük daxil sınavlar hash edir [Işitilemez] at mərtəbə kosmik
və hər kəsin sınavlar qoymaq onların TF tam qaydada
qapağında adları, çünki sonra bizim üçün çox asandır
istifadə edərək xətti ilə axtarış axtarış və ya dərrakə bir növ
bir TF tapmaq üçün onun və ya Onun tələbələrin viktorina.
>> Hashing Belə ki, bu fikir siz görəcəksiniz ki,
olduqca güclü, həqiqətən, olduqca adi və çox intuitiv,
çox bəlkə bölmək kimi fəth həftə sıfır idi.
Hackathon Mən sürətli irəli bir neçə il əvvəl.
Bu Zamyla və bir neçə idi digər heyət təbrik tələbələr
Onlar da gəlib kimi.
Və biz qatlama bütün dəstə idi adı tags ilə masalar.
Və biz adı tags təşkil etmişdi ilə orada kimi
və orada Zs.
Və belə TFS biri çox ağıllı təlimatları bu yazdı
Bu gün üçün.
Və dövr bu həftə 12 bütün mükəmməl mənada və hər kəsə
nə bilirdi.
Amma zaman siz var Eyni şəkildə sıraya,
Siz həyata edirik bir hash eyni anlayışı.
Belə ki, bir az rəsmiləşdirilməsi bildirin.
Burada bir sıra edir.
Bu bir az cəlb edir geniş yalnız vizual, təsvir etmək,
biz strings qoymaq bilər ki, bu kimi bir şey.
Bu array edir aydın ölçüsü 26 cəmi.
Və şey adlanır masa özbaşına.
Amma bu yalnız bir rəssamın icra edir bir hash table ola bilər nə.
>> Belə ki, bir hash table, indi gedir yüksək səviyyəli data strukturu olacaq.
Günün sonunda biz sizə ki, görmək haqqında olduğunuz
bir hash masa, həyata bilər çox check-line kimi
çox bu kimi bir Hackathon at masa imtahan kitab çeşidlənməsi üçün istifadə.
Amma bir hash masa Bu yüksək səviyyəli sort
bir sıra istifadə edə bilər ki, konsepsiya , başlıq onu həyata keçirmək üçün altında
və ya uzunluğu siyahısını istifadə, və ya hətta bilər bəlkə bəzi digər məlumatlar strukturları.
İndi ki, theme-- alaraq var Bu fundamental maddələr bəzi
bir sıra və bu bina kimi uzunluğu siyahısı indi blok
və biz inşa edə bilərsiniz nə görən bu üst, maddələr kimi
bir resept, daha çox və daha çox maraqlı və faydalı yekun nəticələri.
>> Bu hash masa ilə belə biz bunu həyata bilər
yaddaş pictorially bu kimi, lakin necə həqiqətən kodlu bilər?
Bəli, bəlkə sadəcə olaraq bu.
Bütün caps QABİLİYYƏTİ, yalnız əgər Məsələn 26 üçün bəzi constant--,
Bu alphabet-- 26 məktublar üçün Mən dəyişən masa zəng edə bilər,
və mən gedirəm ki, iddia edə bilər orada, və ya simli char ulduz qoydu.
Belə ki, kimi sadə deyil, bu kimi bir hash masa həyata keçirmək istəyirik.
Və hələ, bu, həqiqətən yalnız bir sıra edir.
Ancaq yenə də, bir hash masa nə biz will indi
yalnız bir mücərrəd data type zəng üst bir konseptual layering sort
daha dünyəvi bir şey İndi bir sıra istəyirəm.
>> İndi biz getmək yoxdur problemlərin həlli haqqında?
Bəli, əvvəllər mən lüks idi burada kifayət qədər masa yer olan
Mən qoymaq bilər ki, sınavlar yerdə Mən istəyirdim.
Belə ki, kimi burada getmək bilər.
Zs burada getmək bilər.
Ms burada getmək bilər.
Və sonra mən bəzi əlavə yer var idi.
Amma bu bir fırıldaqçı sol bir az İndi bu masa, çünki mən, həqiqətən,
bir sıra kimi fikir, yalnız Bəzi sabit ölçüsü olacaq.
>> Belə ki, texniki, mən çəkmək əgər başqa şagirdin viktorina qədər
və bu şəxs, oh bax adı da A ilə başlayır
I növ orada qoymaq istəyirəm.
Amma tezliklə əgər, orada qoymaq kimi Bu cədvəldə həqiqətən bir sıra təmsil,
Mən əsas və ya clobbering gedirəm kim bu tələbə viktorina edir.
Right?
Bu bir sıra deyil, yalnız bir şey edə bilərsiniz Bu hüceyrələri və ya elementlərin hər getmək.
Və mən növ var seçin və seçmək üçün.
>> İndi əvvəllər I növ cheated və bu və ya etdim
yalnız cür dizilir bir-birinə yuxarıda onlara.
Amma ki, kodu uçmaq niyyətində deyil.
Mən harada qoymaq bilər Onun adı ikinci tələbə
Mən bütün bu əgər A mövcud masa yer?
Mən üç yuva və istifadə etdiyiniz Yalnız bir neçə başqaları var kimi görünür.
Siz nə edə bilər?
Auditoriya: [işitilemez]
DAVID MALAN: Bəli.
Bəlkə yalnız sadə saxlamaq imkan verir.
Right?
Mən bunu qoymaq istədiyiniz uyğun deyil.
Mən onu qoymaq gedirəm texniki B getmək harada.
İndi, əlbəttə, mən başlayan alıram bir küncə özümü boya.
Mən bir tələbə almaq Onun adı əslində B,
İndi B bir az köçürülüb olacaq irəli kimi, yep, baş verə bilər
bu bir B əgər, indi burada getmək üçün var.
>> Və bu çox tez problemli ola bilər
lakin bu texnika həqiqətən var xətti probing kimi istinad edilir,
qovuşdurmağımız yalnız hesab sizin array xətti boyunca olmalıdır.
Və yalnız cür sonda ya Hər bir mövcud element yoxlamaq
mövcud spot axtarır.
Və tezliklə tapmaq kimi bir, siz orada onu buraxın.
>> İndi qiymət indi ödənilir Bu həlli üçün nə edir?
Biz sabit ölçüsü array var, Mən adları daxil zaman
onu, ən azı ilkin nə durub çalışan zaman
tələbələrin qoyulması üçün sağ buketler sınavlar?
Nə Big O?
>> Auditoriya: n.
DAVID MALAN: Mən n böyük O eşitdim.
Doğru deyil.
Amma biz ayrı dolaşmaq lazımdır niyə yalnız bir anda.
Başqa nə ola bilər?
>> Auditoriya: [işitilemez]
DAVID MALAN: Və mənə vizual bunu bildirin.
Belə ki, bu məktub S. güman
>> Auditoriya: Bu, bir var.
DAVID MALAN: Bu biridir.
Right?
Bu array olan biz təsadüfi giriş var deməkdir.
Və biz bu hesab sıfır və bu kimi 25 kimi,
və biz həyata, oh, burada mənim giriş S var,
Mən, əlbəttə, çevirə bilərsiniz S, bir ASCII xarakter,
müvafiq sıra sıfır və 25 arasında
və sonra dərhal Bu məxsusdur yerləşir qoymaq.
>> Amma əlbəttə, tezliklə mən almaq kimi adı olan ikinci şəxs A və ya B və ya C
nəhayət, Mən istifadə etdiyiniz əgər xətti, mənim həlli kimi yoxlamağa
çalışan zaman Ən pis halda durub
həqiqətən nə daxil qalmaq gedir?
Və mən burada eşitmisiniz düzgün erkən.
Auditoriya: [işitilemez]
DAVID MALAN: Belə ki, həqiqətən bir n Siz kifayət qədər böyük data dəsti var.
Belə ki, bir tərəfdən, əgər Sizin array kifayət qədər böyük deyil
və sizin data, kifayət qədər seyrək Bu gözəl daimi vaxt almaq.
Amma tezliklə başlamaq kimi daha çox elementləri almaq,
və yalnız statistik almaq hərfi ilə daha çox insanlar
A onların adı və ya məktub B, potensial bilər
bir şey daha xətti daxil qalmaq.
Belə ki, kifayət qədər mükəmməl deyil.
Belə ki, biz daha yaxşı bilər?
>> Yaxşı, nə oldu bizim həll zaman biz əvvəl
daha çox dinamizm var istəyirəm bir sıra kimi bir şey icazə?
Auditoriya: [işitilemez]
DAVID MALAN: biz nə təqdim etməyib?
Bəli.
Belə ki, bir bağlı siyahı.
Yaxşı, bir bağlı nə görmək edək siyahısı əvəzinə bizim üçün edə bilər.
Yaxşı, mənə biz təklif edək aşağıdakı kimi şəkil çəkmək.
İndi bu fərqli Məsələn şəkil
müxtəlif mətn, həqiqətən, həqiqətən ölçüsü 31 bir sıra istifadə edir.
Bu müəllif sadəcə strings hash qərar
şəxsin adları əsasında deyil, lakin onların doğum günlerinin əsaslanır.
Asılı olmayaraq ayın, onlar fiqurlu Bir ayın ilk anadan edirsinizsə
və ya bir ay 31, müəllif ki, dəyəri əsasında hash edəcək,
bir az həyata adları yaymaq kimi yalnız 26 ləkələr imkan bilər daha çox.
Və bəlkə bir az daha vahid var əlifba hərfləri ilə gedən daha,
çünki, əlbəttə yəqin ki, var adları ilə dünyada daha çox insanın
əlbəttə çox A ilə start Əlifba digər məktublar.
Belə ki, bəlkə, bu bir az daha vahid, fərz
vahid paylanması Bir ay boyunca körpələr.
>> Lakin, əlbəttə, bu hələ təkmil deyil.
Right?
Biz toqquşma qarşılaşdıqda.
Bu çox insanlar data strukturu hələ
ən azı eyni doğum olan Siz ay asılı olmayaraq istəyirik.
Lakin müəllif nə görmüşdür?
Biz bir sıra var kimi Bəli, görünür şaquli tərtib sol tərəfində,
lakin yalnız bir rəssamın icra edir.
Fərq etməz hansı istiqamətdə bir sıra çəkmək, o, hələ bir sıra var.
Bu yəqin bir sıra nədir?
>> Auditoriya: Əlaqəli siyahısı.
>> DAVID MALAN: Bəli.
Bir var kimi görünür bağlı siyahı array.
Belə ki, yenə növ bu nöqtəyə İndi bu data strukturları istifadə
daha çox maddələr kimi maraqlı həllər,
Siz tamamilə bir edə bilər fundamental, bir sıra kimi,
və daha çox bir şey almaq bir bağlı siyahı kimi maraqlı
və hətta daha onları birləşdirmək daha maraqlı data strukturu.
Və həqiqətən, bu çox olardı bir hash masa adlanır,
qovuşdurmağımız array edir həqiqətən hash table,
lakin hash table var zəncirlər, belə ki, danışmaq
ki, inkişaf edə bilər və ya əsasında shrink elementlərin sayı əlavə etmək istəyirəm.
>> İndi buna görə, nə indi vaxt çalışan?
Mən kimsə daxil etmək istəyirsinizsə, 31 oktyabr kimin ad,
o Ü getmək edir?
Bütün hüquqlar.
Bu 31 deyir çox alt.
Və mükəmməl.
Ki, daimi vaxt idi.
Amma biz başqa kimsə nə tapmaq əgər kimin ad günü, görək ki,
Oktyabr, noyabr, dekabr 31?
Harada o getmək üçün gedir?
Eyni şey.
Baxmayaraq iki addım.
Ki, baxmayaraq daimi deyil?
Bütün hüquqlar.
Hal-hazırda deyil.
Amma ümumi halda, biz əlavə daha çox insan,
probabilistically, gedirik daha çox toqquşma almaq üçün.
>> İndi bu bir az yaxşı texniki çünki
İndi mənim zəncirlər ola bilər ən pis halda necə uzun?
Mən bu daha çox daxil N insanları daxil edin inkişaf etmiş data strukturu, n insanlar,
ən pis halda n olacaq.
Niyə?
>> Auditoriya: Çünki əgər hər kəs eyni ad var,
onlar bir xətt olacaq.
DAVID MALAN: Perfect.
Bu, bir az göstərdi ola bilər lakin həqiqətən ən pis halda,
hər kəs eyni ad var, Siz giriş verilmiş,
Bir var olacaq kütləvi uzun zəncir.
Belə ki, siz bir zəng edə bilər hash table, lakin həqiqətən bu
yalnız kütləvi bağlı siyahı sərf kosmik bir çox.
Lakin ümumiyyətlə, biz güman əgər ən azı ad günü uniform-- var
və yəqin ki, deyil.
Mən qədər edilməsi alıram.
Amma biz güman əgər, üçün müzakirə naminə
Onlar sonra nəzəri, əgər ki, Bu şaquli təmsil edir
serialın, yaxşı sonra inşallah siz etdiyiniz var, bilirsiniz ki, zəncirlər almaq üçün gedir,
təxminən eyni uzunluğu olduğu hər bu ay bir gün edir.
>> Ay 31 gün var, əgər İndi, ki, həqiqətən, mənim çalışan zaman deməkdir
31-dən çox n böyük O olan xətti daha yaxşı hiss edir.
Amma biri idi bizim öhdəliklər bir neçə həftə
əvvəl ifadə gəlib zaman alqoritm çalışan zaman?
Yalnız yüksək order müddətli baxmaq.
Right?
31 mütləq faydalıdır.
Amma bu hələ n böyük O edir.
Amma mövzulardan biri problemi beş set
üçün olacaq tamamilə etiraf,
asimptotik, nəzəri Bu data strukturu
yalnız daha yaxşıdır bir kütləvi bağlı siyahısı.
Və həqiqətən, ən pis halda, bu hash table ki, daxil qalmaq bilər.
>> Lakin real dünyada, bizimlə insanlar öz Mac və ya PC və ya hər hansı ki,
və real dünya çalışan real dünya data software,
olan alqoritm üstünlük gedir?
Son addımlar və ya alır ki, bir n 31 addımlar bölünür edir ki, bir
məlumatların bir parça tapmaq və ya bəzi informasiya axtarmaq üçün?
Mən tamamilə 31 markalar demək real dünyada bir fərq.
Bu 31 dəfə daha sürətli edir.
Və biz insanlar əlbəttə var ki, təşəkkür olacaq.
>> Belə ki, ayrılığın həyata faktiki arasında
nəzəri şeylər haqqında danışır mütləq və asimptotik olan
biz gördük kimi dəyər var, lakin real dünyada,
yalnız edilməsi haqqında qayğı əgər ümumi giriş insan xoşbəxt,
Siz çox yaxşı qəbul etmək istəyirəm bilər Bəli, bu xətti, ki,
lakin 31 dəfə daha sürətli daha xətti ola bilər.
Və daha yaxşı hələ, biz yalnız yoxdur bir doğum kimi ixtiyari bir şey,
biz bir az sərf edə bilər daha çox vaxt və dərrakə
və biz edə bilər nə haqqında düşünmək, verilən şəxsin adı və bəlkə
Onların doğum o birləşdirmək maddələr bir şey anlamaq üçün
həqiqətən çox vahid və daha az jaggy,
bu şəkil daha danışmaq Hal-hazırda ola bilər göstərir.
Necə ki, biz kodu bu həyata bilər?
Yaxşı, mənə biz təklif edək yalnız biz bəzi sintaksis borc
İndiyədək bir neçə dəfə istifadə.
Və mən müəyyən gedirəm bir node, yenidən
yalnız bəzi ümumi anlayışdır bəzi data strukturunda üçün konteyner.
Mən təklif gedirəm bir simli var gedir.
Amma biz alaraq başlamaq olacaq İndi off təkərlər təlim olanlar.
>> No daha CS50 kitabxana həqiqətən, istədiyiniz halda
Sizin final üçün istifadə etmək gözəl olan layihə,
lakin indi biz geri çəkmək olacaq pərdə və yalnız bir char ulduz deyirlər.
Sözü Belə ki, orada olacaq sözügedən şəxsin adı.
İndi bir link var Burada növbəti node
Bu etdirir ki, qovşaqlarının hər
zəncirində, potensial, bir bağlı siyahı.
>> İndi necə bəyan etmək Bu hash table özü?
Mən bu bütün struktur bəyan edirsiniz?
Yaxşı, həqiqətən, çox mən bir pointer istifadə kimi siyahısı yalnız ilk element
əvvəl eyni mən yalnız demək olar Mən yalnız göstəricilər bir dəstə lazımdır
Bu bütün hash table həyata.
Mən bir sıra üçün gedirəm hash masa çağırıb masa.
Bu ölçüsü tutumu olacaq.
Ki, uyğun necə çox elementləri var.
Və bu həmin elementlərin hər array bir node ulduz olacaq.
Niyə?
Bəli, bu şəkil başına, Mən nə edirəm Bu hash masa kimi həyata
effektiv yalnız başlanğıcı biz şaquli tərtib etdik ki, bu array,
olan meydanların hər bir göstərici təmsil edir.
Olanlar slashes var ki, onların vasitəsilə yalnız null var.
Və olanlar var doğru gedir oxlar
faktiki qovşaqlarının üçün faktiki göstəricilər var, bir bağlı siyahı start bundan dolayı.
>> Belə ki, burada, sonra biz necə qüdrət bir hash table həyata ki,
ayrı-ayrı chaining həyata keçirir.
İndi biz daha yaxşı edə bilər?
Bütün hüquqlar Mən keçən dəfə vəd ki, biz daimi vaxt nail.
Mən cür sizə verdi Burada daimi vaxt,
lakin sonra həqiqətən, bildirib daimi vaxt hələ, çünki
ümumi asılı elementlərin sayı
Siz daxil giren edirik Bu data strukturu.
Amma biz bunu güman edirlər.
Mənə burada ekran geri getmək edək.
, Burada mənə də bu qədər layihə aydın olsun ekran, və mən bu görmüşük.
Mən adını daxil etmək istədiyini düşünək Daven mənim data strukturu.
>> Mən bir string daxil etmək istəyirəm Məlumat strukturu Daven.
Mən istifadə etməyin, əgər hash table, amma istifadə
daha çox bir şey ağac kimi bir ailə ağac, olduğu kimi
Siz bəzi kök var üst və sonra qovşaqlarının və yarpaqları
ki, aşağı və zahiri gedin.
, Sonra mən güman Daven nin daxil etmək istəyirəm
Hal-hazırda boş siyahısı nə.
Mən aşağıdakı gedirəm: Mən bu ailə bir node yaratmaq niyyətindədir
ağac kimi data strukturu görünür ki, bir az bu kimi, hər hansı
düzbucaqlı, deyək edib bu artıq 26 elementləri üçün.
Və hüceyrələrin hər Bu array gedir
əlifba məktub təmsil etmək üçün.
>> Xüsusilə, mən müalicə gedirəm Bu, A, sonra B, sonra C, onda D
bu burada.
Belə ki, bu səmərəli gedir məktub D. təmsil
Amma Daven nin bütün daxil Mən bir az daha nə etmək lazımdır adı.
Mən ilk belə danışmaq, hash gedirəm.
Mən ilk məktub baxmaq gedirəm da Daven açıq-aydın bir D olan,
və mən ayrılması gedirəm görünür ki, bir node
kimi böyük böyük düzbucaqlı Hələ bütün əlifbası uyğun kifayət qədər.
>> İndi D edilir.
İndi A. D-A-V-E-N məqsədidir.
Belə ki, indi mən gedirəm nə bu.
Kimi tezliklə Mən D bildiriş başladı heç bir göstərici var.
Bu anda zibil dəyərlər və ya null başlamaq bilər.
Amma mənə ilə davam edək bir ağac bina bu fikir.
Mənə bu başqa bir ayrılması bildirin bu 26 elementlər vardır ki qovşaqlarının.
>> Və nə bilirik?
Bu yaddaş yalnız bir node ki, əgər Mən struct istifadə edərək, malloc ilə yaradılmışdır
biz tezliklə görəcəksiniz kimi, Mən Hələ gedirəm
Mən ox çəkmək üçün gedirəm aşağı D təmsil edən şey
Bu yeni node.
Və ilk növbəti indi Daven adı məktub,
V-- D-A-V-- Mən irəli getmək üçün gedirəm və bu kimi başqa node,
vasitəsi, burada V elementləri olan biz misal whoops üçün çəkmək lazımdır.
Biz orada çəkmək olmaz.
Burada getmək olacaq.
>> Sonra biz olacaq Bu V. hesab
Və sonra aşağı burada biz index olacaq aşağı V biz E. hesab lazımdır nə daxil
Və sonra burada biz olacaq Burada bu qovşaqlarının biri getmək.
İndi biz cavab bir sual var.
Mən göstərir ki, elə etmək lazımdır biz simli Daven sonunda istəyirik.
Mən yalnız null tərk edə bilər.
>> Amma biz Daven nin nə varsa də tam adı, olan
biz Davenport bildirib etdiyiniz kimi, var?
Belə ki, Daven nə varsa əslində bir substring,
Bir daha uzun simli bir prefiks?
Biz yalnız daimi bilməz heç bir şey gedir demək
Çünki ola bilər, orada getmək Davenport kimi bir söz daxil heç vaxt
Bu data strukturu
>> Belə ki, biz nə əvəzinə Bu elementlərin hər müalicə
bəlkə iki olan onların içərisində elementləri.
Bir, həqiqətən, bir göstəricisidir Mən bunu etdik.
Bu qutuları hər belə yalnız bir mobil deyil.
Amma nə əgər top one-- alt birinin
Çünki, null olacaq Yalnız hələ heç bir Davenport var.
Nə üst bir bəzi xüsusi dəyəri?
Və bir az olacaq Bu ölçüsü çəkmək çətindir.
Amma bu yalnız bir onay işareti Güman.
Yoxlayın.
D-A-V-E-N simli Bu data strukturu.
>> Eyni zamanda, əgər mən daha çox yer var idi burada, mən P-O-R-T edə bilər
və mən node çek qoymaq bilər ki, çox sonunda məktub T var.
Belə ki, bu kütləvi deyil kompleks görünüşlü data strukturu.
Və mənim yazı əlbəttə kömək etmir.
Amma bir şey daxil etmək istəyirdi başqa, biz nə hesab.
Biz Davudu qoymaq istəyirdi, Biz, eyni məntiq, D-A-V izləmək istədiyiniz
lakin indi mən növbəti qeyd olardı element deyil E, lakin I D.
Belə ki, var olacaq Bu ağac daha qovşaqlarının.
Daha çox zəng malloc olacaq.
Amma bir etmək istəmirəm Bu şəkil tam mess.
Belə ki, əvəzinə bir baxaq ki, əvvəlcədən ifadə edilmişdir
dot deyil bu kimi, dot, nöqtələr, ancaq qısaldılmış Diziler.
Amma qovşaqlarının hər burada bu ağac qədər
Eyni şey təmsil bir sıra ölçüsü 26 Ray.
>> Yoxsa biz olmaq istəyirsinizsə həqiqətən müvafiq indi nə
kiminsə adı kimi əgər bir apostrof, edək
hər node həqiqətən var ki, güman bu 27 göstəriciləri, yalnız 26 kimi.
Belə ki, indi bir veri olacaq struktur trie T-R-I-E çağırıb.
Guya olan bir trie, bir ağac üçün tarixən bir ağıllı adı
ki, optimize axtarış, əlbəttə,
Bu trie belə bir I-E yazılır.
Amma bu trie tarixidir.
>> Belə bir trie, bu ağac kimi data bir ailə ağac kimi strukturu
ki, nəticədə kimi davranır.
Və burada bir yalnız bir nümunəsidir digər insanların adları dəstə.
Amma indi sual əl var nə
biz arguably daha tanıdaraq əldə mürəkkəb data strukturu və bir,
səmimi, yaddaş bir çox istifadə edir.
>> , Çünki baxmayaraq Hal-hazırda, mən yalnız deyiləm
D's göstərici istifadə və A V və Es və Ns, və
Mən yaddaş çox bir heck israf edirəm.
Amma bir resurs sərf harada, Mən geri bir əldə edirsiniz edirlər.
Mən daha çox yer sərf edirəm əgər Belə ki, yəqin ki, ümid var?
Mən nə az sərf edirəm ki?
Auditoriya: az vaxt.
DAVID MALAN: Time.
İndi nə ola bilər?
Yaxşı, durub nə vaxt, indi böyük O baxımından,
Daven kimi adı və ya Davenport və ya David?
Yaxşı, Daven beş addımlar idi.
Davenport doqquz addımlar olacaq, belə ki, bir neçə addımlar olardı.
David həmçinin beş addımlar olardı.
Belə ki, konkret var nömrələri, lakin, şübhəsiz ki var
Bu bir üst bound kiminsə adı uzunluğu.
Və həqiqətən, problemi Beş dəqiqləşdirilməsi dəstləri,
Biz təklif olacaq bir şey var ki,
40-bəzi-tək simvol var.
>> Real, heç bir var sonsuz uzun adı,
demək olan bir uzunluğu Ad və ya simli uzunluğu Biz güc
Dövlət müəyyən var strukturu arguably nədir?
Bu sabit deyil.
Right?
Bu kimi böyük bir sabit ola bilər 40-bir şey, lakin sabit deyil.
Və nə qədər heç bir asılılıq var digər adları Bu data strukturu var.
Başqa sözlə, mən əgər İndi daxil etmək istədi
Colton və ya Gabriel ya Rob ya Zamyla və ya Alison ya Belinda və ya hər hansı digər adları
Bu data daxil heyəti strukturu, çalışan vaxt
digər adları daxil bütün təsir da olacaq
necə bir çox digər elementləri ilə var artıq data strukturunda?
Bu deyil.
Right?
Biz səmərəli istifadə edirik, çünki Bu multi-qat hash table.
Və çalışan zaman Bu əməliyyatların hər hansı
sayı deyil asılıdır Bu data strukturu var ki elementləri
və ya nəticədə gedir Bu data strukturu olmaq,
lakin nə xüsusi uzunluğu?
>> Olan string , daxil edir olan
Bu asimptotik daimi bir time-- böyük Ç.
Və səmimi, yalnız Real dünya, bu
Daven adı alır daxil deməkdir beş addımlar, və ya Davenport doqquz kimi
addımlar, və ya David beş addımlar.
Bu olduqca darn kiçik çalışan dəfə var.
Və həqiqətən, bir çox var Yaxşı şey, xüsusilə
Bu cəmi asılı deyil orada elementlərin sayı.
Beləliklə, biz bu həyata bilər necə kodu strukturunun cür?
Bu bir az daha çox mürəkkəb, lakin hələ də var
yalnız bir proqram əsas bloklar.
Mən yenidən gedirəm Bizə node aşağıdakı kimi:
bool word-- adlanır və bu bir şey adlandırmaq olar.
Amma bool təmsil nə bir onay işareti kimi çəkdi.
Bəli.
Bu simli sonu Bu data strukturu.
>> Və, əlbəttə, node ulduz uşaq var istinad edilir.
Və həqiqətən, yalnız kimi bir ailə ağacı, siz
qovşaqlarının hesab edirəm off asma olunur
bəzi müəssisənin alt element uşaqlar üçün.
Və belə ki, uşaqlar gedir 27 bir sıra 27 biri ola
yalnız apostrof üçün olan.
Biz düzmək olacaq Xüsusi halda ki.
Belə ki, müəyyən ola bilər apostrophes ilə adları.
Bəlkə hətta tire olmalıdır orada getmək, lakin siz lazımdır
p set 5 yalnız qayğı görmək məktublar və apostrophes haqqında.
>> Və sonra necə təmsil edə Bu data strukturu özü?
Necə kök təmsil Bu trie, belə danışmaq?
Bəli, yalnız bir bağlı siyahısı ilə kimi ilk element bir göstərici lazımdır.
Bir trie ilə yalnız bir ehtiyac bu trie kök göstərici.
Və oradan hash bilər yol aşağı dərin və daha dərin
tərkibində hər node.
Belə ki, sadəcə bu can ilə biz struct təmsil edir.
>> İndi Oh sual Meanwhile--.
>> Auditoriya: bool söz nədir?
>> DAVID MALAN: Bool söz yalnız bu C təcəssüm
Mən təsvir nə Burada, bu qutusuna
Mən hər parçalanması başladı iki hissəyə serialın elementləri.
One növbəti node bir göstərici deyil.
Digər olmalıdır bir onay qutusu kimi bir şey
bir var, bəli demək burada bitir Daven söz,
Biz istəmirik Hal-, Dave da.
>> Dave bir olacaq baxmayaraq qanuni söz, o trie deyil
hələ.
Və D bir söz deyil.
Və D-A bir söz və ya bir ad deyil.
Bu onay işareti So yalnız sizin dəfə göstərir
Bu node təşkil edib simvol əvvəlki yolu
Siz daxil etdiyiniz həqiqətən bir string.
Belə ki, bütün bool var Bizim üçün edir.
>> Çalışır hər hansı digər suallar?
Bəli.
>> Auditoriya: üst-üstə düşür nədir?
Nə Dave və Daven varsa?
DAVID MALAN: Perfect.
Nə Dave və Daven varsa?
Biz daxil Belə ki, bir ləqəb demək David-- Dave-- D-A-V-E?
Bu, həqiqətən, super sadədir.
Beləliklə, biz yalnız dörd addımlar olacaq.
D-A-V-E. Mən nə var Mən dördüncü node hit bir dəfə?
Just yoxlamaq olacaq.
Biz artıq getmək iyi.
Done.
Dörd addımlar.
Asimptotik daimi vaxt.
Və indi biz də Dave qeyd etdik və Daven tərkibində strings var.
Belə bir problem.
Və necə varlığı hiss Daven onu etməyib
daha çox vaxt az və ya vaxt Dave və əksinə.
>> Beləliklə, biz indi başqa nə edə bilər?
Biz əvvəl bu məcaz istifadə etdiyiniz qablar bir şey təmsil.
Amma bu çıxır ki, bir qablar yığını əslində
başqa mücərrəd data nümayişkaranə yüksək səviyyəli data strukturu yazın
sonunda gün yalnız ki, bir sıra və ya bir bağlı siyahısı kimi
daha çox dünyəvi və ya bir şey.
Amma bir daha maraqlıdır konseptual anlayış.
Bu kimi bir yığın, Mather burada novları,
ümumiyyətlə deyilir yalnız bir yığın that--.
>> Və data strukturu bu növü iki operations-- var
bir adlı təkan üçün yığını bir şey əlavə,
başqa bir tray qoyulması kimi yığını üst geri.
Sizə deməkdir və sonra pop topmost tray off edir.
Amma bir yığın ki, haqqında əsas nə Bu maraqlı xüsusiyyəti var.
Yemekhane heyəti kimi növbəti yemək üçün qablar yenidən,
nə olacaq tələbələrə haqqında doğru
Bu data strukturu ilə qarşılıqlı?
Auditoriya: Onlar bir off pop olacaq.
DAVID MALAN: Onlar olacaq bir off, inşallah üst pop.
Əks halda yalnız cür axmaq var alt bütün yol getmək.
Right?
Bu data strukturu həqiqətən imkan vermir ən azı alt tray qamarlamaq üçün
asanlıqla.
Belə ki, bu maraqlı var Bir yığın əmlak
son maddə ilk biri olacaq.
Və kompüter alimləri zəng Bu ilk, həyata davam LIFO--.
Və həqiqətən var maraqlı applications.
Bu, mütləq bəzi kimi aydın deyil başqaları, lakin, həqiqətən, faydalı ola bilər
və bu, həqiqətən, həyata keçirilə bilər müxtəlif yollarla bir neçə.
>> Belə ki, bir, həqiqətən, qoy Mənə daxil dalış deyil.
Əvəzinə bunu edək.
Nin demək olar ki, var ki, bir baxaq eyni fikir, lakin bir az ədalətli var.
Right?
Bu fan oğlanlar biri edirsinizsə və ya həqiqətən Apple məhsulları sevir ki, qızlar
və 3:00 AM oyandı Bəzi mağaza sıralamaq üçün
son iPhone almaq üçün, bu kimi sıraya ola bilər.
>> İndi növbə çox qəsdən adlanır.
Var, çünki xətti bəzi ədalət.
Right?
Siz var əgər bu cür sucked ki Apple Store ilk var
lakin səmərəli bottommost var tray sonra Apple işçilərinin çünki
son şəxs pop edən həqiqətən xətti var.
Borular və sıralarında, baxmayaraq belə funksional onlar same-- cür edirik
yalnız bu toplanması resursların ki
orada var shrink-- inkişaf gedir və bu bu ədalət aspekt,
Real dünyada ən azı, burada əməliyyatları həyata
əsaslı fərqlidir.
Bir sıra A stack-- rather-- deyilir
iki əməliyyatları: n queue və d queue.
Yoxsa onlara zəng edə bilərsiniz hər hansı bir sayı.
Amma yalnız tutmaq istəyirəm bir əlavə edir ki, anlayışı
və bir nəticədə subtracting edir.
>> İndi başlıq altında, həm də yığını və bir sıra necə həyata keçirilə bilər?
Biz kodu daxil deyil çünki yüksək səviyyəli
fikir sort daha göz qabağındadır.
Mən demək, insanlar nə etməliyəm?
Mən Apple ilk şəxs deyiləm, Saxlamaq və bu ön qapı,
Mən burada durmaq gedirəm, bilirik.
Və növbəti şəxsin burada durmaq gedir.
Belə ki, nə data strukturu özü bir sıra verir?
>> Auditoriya: A queue.
DAVID MALAN: Bəli, bir sıra.
Sure.
Nə?
>> Auditoriya: A bağlı siyahı.
>> DAVID MALAN: A bağlıdır Siz həyata bilər edin.
Və əlaqəli siyahısı sonra, çünki gözəl fərqli olaraq uzun özbaşına inkişaf edə bilər
Bəzi sabit sayı olan mağaza insanların.
Amma bəlkə bir sabit sayı yerlərdə qanuni.
Yalnız 20 kimi varsa, çünki bəlkə ilk günündə iPhone
yalnız ölçüsü bir sıra lazımdır 20 ki növbə təmsil edən
Biz söhbət başlamaq dəfə yalnız indi demək olunur Bu yüksək səviyyəli problemlərin,
Siz həyata keçirə bilər yolları bir sıra.
Və yəqin ki, yalnız gedən var məkan və zamanda bir ticarət off ola
və ya yalnız öz kodu mürəkkəbliyi.
>> Bir yığın haqqında nə?
Yaxşı, bir yığın, biz də gördük yalnız bu qablar ola bilər.
Və bu bir sıra həyata bilər.
Lakin bəzi noktada, bir sıra istifadə əgər nə qablar nə olacaq
siz yazmaq çalışdığınız?
Bütün hüquqlar.
Siz yalnız olacaq qədər yüksək getmək mümkün.
Mən onlar Mather hesab həqiqətən açılışında recessed.
Belə ki, həqiqətən, demək olar ki, var Mather istifadə kimi
sabit ölçüsü bir sıra, yalnız, çünki
ki, açılış çox qablar uyğun xalq diz aşağı divar.
Və belə ki, ola bilər, bir sıra olduğu ifadə,
lakin biz, əlbəttə ki, həyata bilər ümumiyyətlə bir bağlı siyahısı ilə.
>> Yaxşı, nə başqa data strukturu haqqında?
Mənə burada vizual birini qoparmaq edək.
Necə burada bu barədə kimi bir şey?
Niyə üçün faydalı ola bilər bir trie, kimi bir şey zənn edən
biz bu çox geniş qovşaqlarının idi gördüm olan hər bir sıra var?
Amma biz bir şey daha nə əgər sadəcə, köhnə məktəb ailə ağac kimi,
kimin burada qovşaqlarının hər yalnız bir sıra saxlanılması.
Bunun əvəzinə bir adı və ya nəslindən yalnız bu kimi bir sıra saxlanılması.
>> Yaxşı, jargon biz istifadə data strukturları, həm də çalışır deyil
və ağaclar, bir trie, yenə olduğu yalnız onların qovşaqlarının Diziler biri,
hələ nə bilər sinif məktəbin istifadə
Bir ailə zaman ağac yarpaqları və kök
ağac və uşaqların valideyn və onların bacı.
Və biz bir ağac həyata bilər, Məsələn, kimi sadəcə bu kimi.
A ağac, bu bir node, biri kimi bir sıra var ki, bu dairələr,
Bu var niyyətində deyil bir pointer, lakin iki.
Və tezliklə əlavə kimi ikinci göstərici, siz
həqiqətən, indi sort edə bilərsiniz iki ölçülü məlumatların
yaddaş strukturları.
Iki ölçülü kimi Much array, siz
iki ölçülü cür var bağlı siyahıları lakin olanları
ki, bir model edin burada heç bir dövründən var.
Bu biri ilə həqiqətən canından burada və sonra grandparent yolu
bəzi valideynlər və uşaqlar və nəvəsi və böyük nəvəsi.
və s.
>> Lakin, çox bu barədə həqiqətən səliqəli nə yalnız kodu bir az ilə siz tease üçün,
olan geri recursion biraz geri, vasitəsi
özünü çağırır ki, bir funksiyası yazmaq.
Bu gözəl imkandır bir şey həyata
Recursion kimi, çünki bu hesab.
>> Bu ağac.
Mən necə bir az anal oldum Mən küçəyə integers qoydu.
Belə ki, bu xüsusi var bir ikili axtarış ağac konseptual mənada adı.
İndi biz ikili eşitdim siz axtarış, lakin bilər
Bu şey adı geri iş?
I necə model nədir bu ağac daxil integers daxil?
Bu ixtiyari deyil.
Bəzi model var.
Bəli.
>> Auditoriya: sol Kiçik olanları.
>> DAVID MALAN: Bəli.
Kiçik olanları sol var.
Böyük olanları sağ var.
Belə bir gerçək bir bəyanat ki, valideyn, onun sol uşaq daha böyükdür
Onun sağ uşaq daha lakin az.
Və tək ki, hətta bir deyil recursive şifahi definition
ki, müraciət edə bilər, çünki hər node eyni məntiq
və yalnız dibi həyata, baza halda əgər
olacaq, zaman bir hit yarpaq, belə ki, danışmaq
bir məzuniyyət daha heç bir övladı var olduğu.
>> İndi necə sayı 44 tapa bilərsiniz?
Siz hm kök başlamaq və deyərdim.
55 Mən getmək istəyirəm 44 deyil sağ və ya sol getmək istəyirsiniz?
Bəli, açıq-aydın sol getmək istəyirəm.
Və belə ki, yalnız telefon kimi Binar axtarış kitab nümunə
ümumiyyətlə.
Amma biz bunu həyata edirik İndi bir az daha dinamik
bir sıra imkan bilər daha.
Və əslində, siz baxmaq istəyirsinizsə kodu, ilk baxışda əmin olun.
Bu xətləri bütün dəstə kimi görünür.
Amma bu gözəl sadə.
Bir funksiyası həyata istəyirsinizsə, kimin məqsədi həyat deyilən axtarış
dəyəri axtarmaq üçün nə kimi n, bir tam,
və bir pointer qəbul edirik kökləri node bir göstərici,
daha ki, ağac olan Siz başqa hər şey edə bilərsiniz
necə straightforwardly qeyd Siz məntiq həyata keçirə bilər.
Ağac null əgər, Aydındır ki, bu yoxdur.
Yalnız yalan qayıtmaq edək.
Right?
Siz heç bir şey edirsinizsə, var heç bir şey yoxdur.
>> Else n az, əgər İndi n arrow n ağac arrow,
biz super təqdim geri qısa gün,
və yalnız de-istinad deməkdir pointer və n adlı sahəsində baxmaq.
Belə ki, orada getmək deməkdir n adlı sahəsində baxmaq.
Belə ki, n, əgər sunulur dəyəri, az ağaclar tam dəyərinin daha,
harada getmək istəyirsiniz?
Sol.
>> Belə ki, recursion bilərsiniz.
Mən doğru deyil returning-- deyiləm.
Yalan deyil.
Mən nə cavab qaytarılması alıram özümə zəng edir, keçən
lazımsız olan daha bir n, lakin indi az müxtəlif var?
Necə mən kiçik problem qəbul edirəm?
Mən ikinci keçən alıram dəlil, ağac deyil kök,
lakin bu halda sol uşaq.
Mən sol uşaq keçən alıram.
>> Eyni zamanda n daha böyük, əgər Hal-hazırda da arıyorum node,
Mən sağ tərəfdən axtarış.
Else, ağac, null deyil və Bu element sol deyil,
və, sağ deyil halda gözəl nədir?
Biz, həqiqətən də node gördük sual, və biz doğru qayıtmaq.
>> Beləliklə, biz yalnız səthi cızıqlanmış sonra İndi bu data strukturları bəzi.
Problem set beş sizə lazımdır hələ bundan sonra da bu araşdırmaq,
və sizin dizayn verilir bu barədə getmək necə seçim.
Mən bağlamaq istədiyiniz nə yalnız 30 ikinci iltifat edir
kənarda gələn həftə və gözləyir nə.
>> Biz təşəkkürlə begin-- kimi bilər yavaş-yavaş bizim keçid think--
C və aşağı dünya səviyyədə həyata ətraflı,
bir dünyada olan biz bilər başqası nəhayət ki, verilən
Bu data tətbiq bizim üçün strukturları,
və biz anlamaq üçün başlamaq lazımdır real dünya həyata deməkdir
web-based proqramları və saytları ümumiyyətlə
və də çox təhlükəsizlik biz yalnız var ki, təsiri
səthində danışıq başlayıb.
Burada bizi gözləyir nə gün gəlib.
>> [Video playback]
>> O, bir mesaj gəldi bütün öz protokol.
O, qəddar bir dünyaya gəldi firewall, uncaring yönlendirici,
və təhlükələr ölüm çox pis.
O, sürətli.
O, güclü var.
O, TCP / IP, və o ünvanınızı var.
"Net Warriors."
[END video playback]
DAVID MALAN: gələn həftə gəlir.
Biz sonra görəcəksiniz.
[Video playback]
-Və Indi "Deep Thoughts" Daven Farnham tərəfindən.
David həmişə başlayır ilə mühazirələr "Bütün hüququ."
Niyə "Burada həll bu həftə problem set "üçün
və ya "Biz A sizə bütün ötürür?"
[Gülür]
[END video playback]