>> HOPARLÖR 1: Bütün sağ, biz geri edir.
CS50 xoş gəlmisiniz.
Bu həftə yeddi sonu.
Belə ki, son dəfə xatırlayıram, biz başladı biraz daha mürəkkəb baxaraq
məlumat strukturlar.
İndiyə qədər bu yana, biz bütün həqiqətən idi bizim sərəncamında bu, bir sıra idi.
>> Amma biz serialın imtina kimi deyil, əvvəl bütün maraqlı, hansı həqiqətən
Əslində, bəzi nə edilir Bu sadə məlumatların müsbət
strukturu indiyə qədər?
Bu yaxşı nədir?
İndiyə qədər gördük kimi?
Nə var?
Heç bir şey.
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Nə o?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Sabit ölçüsü.
OK, belə ki, niyə sabit ölçüsü olsa yaxşıdır?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: OK, belə ki, səmərəli var bir ayrılması bilər ki, mənada
kosmik sabit məbləğ, hansı inşallah dəqiq çox
yer istədiyiniz kimi.
Belə ki, tamamilə bir plus ola bilər.
>> Bir sıra digər up tərəfi nədir?
Bəli?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Bütün - üzr?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: yaddaş Bütün qutuları və ya bir-birinə yanında.
Və faydalı var - niyə?
Bu çox doğru.
Amma necə ki, həqiqət istifadə edə bilər?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Məhz, biz takip edə bilərsiniz hər şey yalnız bilerek olduğu
bir yəni ünvanı, yerləşdiyi ünvan yaddaş ki yığın ilk byte.
Və ya simli halda, ilk ünvanı
ki, simli ildə karakter.
Və orada, biz tapa bilərsiniz simli sonunda.
Biz ikinci element ki, tapa bilərsiniz Üçüncü element, və s.
>> Və izah belə xülya yolu xüsusiyyət Diziler bizə ki,
rasgele erişim.
Yalnız kvadrat mötərizə istifadə edərək, notation və bir sıra, siz atlayabilir
serialın müəyyən bir element daimi vaxt, böyük O
bir, belə danışmaq.
>> Lakin bəzi downsides olub.
Bir sıra çox asanlıqla nə deyil?
Bu yaxşı nə deyil?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Nə o?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: ölçüsü genişləndirilməsi.
Ki, serialın downsides ki nə dəqiq əks
upsides var.
Belə ki, downsides biri bir sabit ölçüsü var.
Beləliklə, siz, həqiqətən, inkişaf edə bilməz.
Siz böyük bir yığın təkrar bölüşdürə bilər yaddaş, sonra köhnə elementləri hərəkət
yeni massivinə.
Və sonra pulsuz köhnə dizi, Məsələn, malloc və ya oxşar istifadə edərək,
realloc adlı funksiyası olan reallocates yaddaş.
>> Realloc bir kənara kimi, sizə vermək çalışır serialın yanında olduğunu yaddaş
Əgər siz artıq var.
Amma bu şeyi hərəkət edə bilər cəmi ətrafında.
Amma qısa ki, sağ, bahalı?
Çünki siz yaddaş bir yığın varsa Bu ölçüsü, ancaq həqiqətən bir istəyirəm
Bu ölçüsü, və qorumaq istəyirsinizsə orijinal elementləri var
təxminən xətti vaxt çıxarmaq prosesi ki, nə lazımdır
yeni köhnə array.
Və reallıq əməliyyat istiyor təkrar sistemi və
yenə yaddaş böyük chunks başlaya bilər eləcə də bir müddət başa.
Belə ki, xeyir-dua və lənət, həm də var , faktı ört-basdır bu seriallarda
sabit ölçüsü var.
Amma biz əvəzinə bir şey təqdim əgər bu kimi hansı bir bağlı deyilən
siyahısı, biz bir neçə upsides almaq və bir neçə burada downsides həmçinin.
>> Bir bağlı siyahı sadəcə bir məlumat belə strukturu C structs təşkil
bir struct, geri, yalnız olduğu halda, bir və ya daha spesifik üçün konteyner
dəyişənlərin növləri.
Bu halda, nə məlumat növləri etmək ki, struct daxilində görünür ki,
Sonuncu dəfə biz bir node deyilən?
Bu düzbucaqlı hər bir node edir.
Və kiçik düzbucaqlı hər onun daxilində bir məlumat növüdür.
Biz nə növ demək idi Onlar bazar ertəsi idi?
Bəli?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: A dəyişən və bir pointer, və ya Daha konkret desək, bir int, n,
və altındakı bir göstərici.
O həm də, 32 bit olmaq nə Bu CS50 kimi kompüter üzrə ən
Appliance və onlar etdiyiniz belə ölçüsü bərabər etmişdir.
>> Yaxşı pointer istifadə yəqin üçün necə?
Diziler zaman niyə indi bu arrow əlavə belə gözəl və təmiz və sadə?
Göstərici üçün nə edir bizə bu qovşaqlarının hər?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Eynilə elə.
Harada belirten oldu növbəti biridir.
Beləliklə, mən növ ilə analogiya istifadə və düzmək üçün bir mövzu istifadə
birlikdə bu qovşaqlarının Mövzu.
Və biz yapýyorsun dəqiq nə var göstəricilərinə çünki bu hər
yaddaş chunks ola bilər və ya bitişik, geri geri geri
RAM daxilində, çünki hər zaman malloc deyərək zəng, mənə kifayət qədər vermək
Yeni node üçün bytes, bu güc Burada olmaq və ya burada ola bilər.
Burada ola bilər.
Siz yalnız bilmirəm.
>> Amma ünvanlarda göstəricilərinə istifadə o qovşaqlarının, siz stitch onlara bilər
birlikdə vizual görünür ki, bir yol bu şeyi, hətta əgər bir siyahı kimi
bütün bir və ya həyata yayılmışdır Sizin iki və ya RAM sizin dörd qiqabayt
öz kompüter daxilində.
>> , Sonra, İşin mənfi tərəfi odur Belə ki, bir bağlı siyahı nədir?
Biz istəyirik qiymət nedir yəqin ödəyən?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: daha çox yer, sağ?
Biz bu halda, məbləği iki dəfə etdik kosmik biz getdi sonra, çünki
hər biri üçün hər node üçün 32 bit olan int, indi biz 64 bit çünki
eləcə də bir göstərici ətrafında saxlamaq.
Daha çox səmərəliliyi almaq struct əgər Bu sadə şey böyükdür.
Həqiqətən daxilində bir tələbə varsa olan strings bir neçə üçün
adı və ev, bəlkə bir şəxsiyyət nömrəsi, cəmi bəlkə bəzi digər sahələrdə.
>> Böyük bir kifayət qədər struct varsa, onda bəlkə göstərici dəyəri
belə böyük.
Bu bir künc işin bir az biz belə bir sadə primitiv saxlanılması edirik
bağlı siyahı daxilində.
Amma baxımından eynidir.
Siz mütləq daha çox sərf edirik yaddaş, lakin siz əldə etdiyiniz
rahatlıq.
İndi bir element əlavə etmək istəyirsinizsə Çünki Bu siyahının başında,
Yeni node ayırmaq lazımdır.
Və mən yalnız yeniləmə var yalnız hərəkət birtəhər oxlar
ətrafında bir göstəricilərinə.
>> Mən bir şey əlavə etmək istəyirsinizsə siyahısının orta, mən yoxdur
Biz nə kimi kənara hər kəs təkan Bizim könüllüləri ilə həftə keçmiş olan
bir sıra təmsil.
Mən yalnız bir yeni node ayrılması bilər sonra yalnız okları qeyd
müxtəlif istiqamətlərdə deyil, çünki faktiki qalmaq üçün
Mən tərtib etdiyiniz kimi yaddaş əsl xətt burada ekranda bu.
>> Və sonra nəhayət, siz əlavə etmək istəyirsinizsə siyahının sonunda bir şey, bu,
daha asan.
Bu, ixtiyari notation növ edir lakin 34-nin pointer, bir tahmin edir.
Ən çox onun göstərici dəyəri nədir köhnə kimi ehtimal tərtib sort
orada məktəb antenna?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Bu, yəqin ki null var.
And olsun ki, bir müəllif null nümayəndəliyi.
Çünki siz tamamilə Və null var bilmək lazımdır bir bağlı sonunda
siyahısı aşağıdakı saxlamaq deyə, və Bu oxlar aşağıdakı və aşağıdakı
bəzi zibil dəyəri.
Belə null yoxdur ki, demek edəcək 34 saylı hüququ daha çox qovşaqlarının,
bu halda.
>> Belə ki, biz həyata keçirə bilər ki, təklif kod bu node.
Və biz bu cür gördüm syntax əvvəl.
Typedef yalnız yeni növü müəyyən bizə kimi bizə sinonimi verir
string char * idi.
Bu halda, bu, bizə vermək olacaq stenoqrafiya notation ki struct node
yerine kimi yazıla bilər bir çox təmiz olan node.
Az ayrıntılı bir çox var.
>> Bir node daxilində yəqin bir int edir adlı n, sonra struct node *
olan biz istədik dəqiq nə deməkdir oxlar başqa bir pointer demək
eyni data tipli node.
Və mən, biz həyata keçirmişik ki, təklif Bu kimi axtarış funksiyası olan
İlk baxışdan görünə bilər bir az kompleksi.
Lakin bu kontekstdə baxaq.
>> Mənə burada cihaz üzərində gidelim.
Mənə zəng bir fayl açmaq edək siyahısı sıfır dot h.
Və yalnız müəyyən biz ehtiva yalnız bu məlumat üçün bir an əvvəl gördüm
növü node çağırıb.
Beləliklə, biz bir dot h fayla gətirdik.
>> Və bir kənara, hətta bu, sanki görmək haqqında olduğunu proqramı
bütün ki, kompleks, həqiqətən var bir proqram yazarkən konvensiya
çəkmək üçün, data növləri kimi şeylər qoymaq bəzən daxili sizin sabitləri
header fayl və mütləq ildə C fayl, əlbəttə zaman
proqramları daha böyük və daha böyük almaq, belə ki, üçün, həm də baxmaq harada olduğunu bilirsinizmi
bəzi hallarda sənədlərin və ya bu kimi əsasları, üçün
bir növü müəyyən.
>> İndi siyahısı sıfır dot açmaq edin c, bir neçə şey qeyd.
Bu ən çox bir neçə mövzu faylları daxildir olan biz əvvəl gördüm.
O, öz header file daxildir.
>> Və bir kənara kimi, buna görə ikiqat var burada quotes, kimi bucaq fərqli
xətt üzərində Mötərizədə ki, Mən orada qeyd etdik?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Bəli belə bir yerli fayl var.
Burada öz yerli faylı Belə ki, əgər line 15, məsələn, istifadə
ikiqat quotes əvəzinə ki, açılı mötərizələrin.
>> İndi bu maraqlı növüdür.
Mən qlobal elan etdik Qeyd edək ki, line 18 Bu proqram dəyişən
ilk adlanan bu olan fikir ilk göstərici olacaq
Mənim bağlı siyahısında node və mən var Mən var, çünki null başlatılmış
faktiki ayrılmayıb hələ yalnız qovşaqlarının.
>> Beləliklə, bu nə biz, pictorially, təmsil şəkil kimi bir an əvvəl gördüm
uzaq ki pointer tərəfdən buraxdı.
Belə ki, indi ki, pointer ox yoxdur.
Bu yerine null edir.
Amma bu necə olacaq təmsil İlk faktiki ünvanı
Bu siyahıda node.
Mən bir qlobal həyata etdik Bütün bu, görəcəksiniz kimi, çünki
proqram həyatda həyata etmez mənim üçün bağlıdır siyahısı.
>> İndi mən burada bir neçə prototipləri var.
Mən kimi xüsusiyyətləri həyata keçirilməsinə qərar silinməsi, durub, axtarış və
traversal -
The arasında son yalnız olan gəzmək siyahısı, onun elementlərinin çap.
İndi burada mənim əsas gündəlik var.
Və biz çox vaxt sərf deyil Bu ildən bu yana ümid, sort edir
indi köhnə papaq.
>> Mən, aşağıdakı etmək gidiyorum istifadəçi əməkdaşlıq edir.
Bir Belə ki, çap gidiyorum Bu menyu həyata.
Və mən bu biçimlendirilmiş etdik cleanly mən biləcəyi kimi.
Deməkdir bir istifadəçi növləri, əgər onlar bir şey silmək istəyirəm.
Deməkdir iki istifadəçi ki, əgər onlar bir şey əlavə etmək istəyirəm.
Və s.
Mən təklif gidiyorum sonra bir komanda üçün.
Və sonra GetInt istifadə gedirəm.
>> Beləliklə, bu, həqiqətən sadə menuing edir yalnız yazın olduğu interface
bir bir sıra mapping bu əmrləri.
İndi gözəl təmiz açarı var yandırın olacaq ki, bəyanat
istifadəçi kimi daxil yazılmış hər hansı
Onlar bir tipli varsa, mən lazımdır silmək zəng və pozub.
Onlar iki tipli varsa, mən lazımdır daxil zəng və pozub.
>> İndi hər gətirdik BİLDİRİŞ eyni xətt üzərində bu.
Bu yalnız bir üslub qərardır.
Adətən biz bir şey gördüm bunu bəyənir.
Amma yalnız, səmimi, mənim proqram qərar daha oxunaqlı baxdı, çünki
ona yalnız dörd hallarda olmuşdur yalnız bu kimi siyahısı.
Stil tamamilə qanuni istifadə.
Mən bu belə uzun etmək gidiyorum istifadəçi sıfır tipli deyil, I
qərar onlar çıxmaq istəyirik demək olacaq.
>> Belə ki, indi Ben nə hiss burada gedir.
Mən yəqin siyahısına pulsuz gedirəm.
Bir an ki, lakin daha çox.
Ilk bu proqram run edək.
Mənə böyük bir terminal edək pəncərə, nöqtə çizgi siyahısı 0.
Buna davam və daxil etmək üçün gidiyorum yazaraq iki, indi 50 kimi sayı və
siz siyahısına indi 50 görəcəksiniz.
Və mətn yalnız biraz kaydırılmış.
Belə ki, indi siyahısını ehtiva fark sayı 50.
>> Iki alaraq başqa insert nə edək.
Biri kimi sayının yazın edək.
Siyahısı artıq 50 izlədi biridir.
Bu yalnız bir mətn nümayəndəliyi belə siyahısı.
Və nin kimi daha bir sayı daxil bildirin inşallah olan sayı 42,
çünki ortada sonuna qədər davam xüsusi növ bu proqram
bu edər onları elementləri.
Belə ki, orada biz var.
Ki, ola bilər Super sadə proqram tamamilə bir sıra istifadə, lakin
bir bağlı siyahısını istifadə edərək, üçün baş yalnız mən dinamik bilər
böyümək və bu shrink.
>> Belə ki, axtarış bir nəzər edək mən komanda üç run, mən axtarmaq istəyirsinizsə
sayı 43, demək üçün.
Və heç bir şey yəqin edib, Mən heç bir cavab geri var, çünki.
Belə ki, daha bu nə edək.
Axtar.
50 və ya daha çox axtarış üçün edək axtarış 42, bir gözəl var
az incə mənası.
Və mən orada həyatın mənasını tapdı.
Əgər bilmirsinizsə sayı 42, istinad, Google.
Bütün hüquqlar.
Belə ki, nə mənə bu proqram görüb?
Bu, yalnız mənə beləliklə əlavə etmək üçün izin verilen elementləri üçün uzaq və axtarış.
>> , Sonra, sürətli irəli edək biz nəzər funksiyası
bazar ertəsi iltifat kimi.
Bu funksiya Belə ki, mən, axtarış iddia birinci siyahıda bir element
bir, istifadəçi isteyen və sonra zəng Faktiki int almaq üçün GetInt
sizin üçün axtarış istəyirik.
>> Sonra bu bildiriş.
Mən müvəqqəti dəyişən yaratmaq üçün gidiyorum line 188. pointer çağırıb -
Ptr -
bir şey çağırıb bilər.
Və bir node bir göstərici var Mən orada node * bildirib.
Və mən ona bərabər olmalıdır başlatılıyor alıram ilk mən səmərəli var ki,
barmaq, belə ki, çox haqqında danışmaq siyahısının ilk element.
Burada mənim sağ Ptr Ben Belə ki, əgər Eyni şey işarə ilk
da işarə edir.
>> Belə ki, indi geri kodunu, Bundan sonra nə olacaq -
iterating bu ümumi bir paradiqma edir bir kimi bir quruluş üzərində
bağlı siyahısı.
Mən isə aşağıdakı gidiyorum pointer Belə null bərabər deyil isə
mənim barmaq bir null da işarə deyil dəyəri, pointer arrow n n bərabərdir varsa.
Biz n ilk görəcəksiniz nə hər GetInts Yığdığınız istifadəçi burada çağırırıq.
>> Və göstərici arrow n nə deməkdir?
Burada şəkil geri Yaxşı, əgər Mən işarə barmağı varsa
doqquz də olan ilk node arrow mahiyyətcə ki, getmək deməkdir
node və yeri N dəyəri qamarlamaq Bu halda, data sahəsində n çağırıb.
>> Bir kənara kimi - və biz bu neçə gördüm həftə öncə kimsə xahiş zaman -
Bu sintaksis yeni, lakin deyil bizə səlahiyyətlər verir ki,
artıq yox idi.
Istifadə ekvivalent bu söz nə idi dot notation və ulduz bir neçə
həftə bundan əvvəl biz geri soyulmuş zaman bu bir az vaxtından əvvəl qat?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Məhz, bu ulduz idi, sonra bu, ulduz dot n oldu
burada parantez, hansı görünür, Açığı, mən bir çox hesab edirəm ki,
oxumaq daha çox sirli.
Lakin ulduz pointer, həmişə olduğu kimi, vasitələri var gedin.
Və sonra nə məlumat var, istəyirik alan daxil olmaq istəyirsiniz?
Yaxşı siz daxil olmaq üçün dot notation istifadə bir structs data sahəsində, mən
xüsusi n istəyirik.
>> Açığı, mən bu iddia edirəm oxumaq yalnız çətindir.
Bu harada yadda çətindir parantez ki, getmək yoxdur
ulduz və bütün.
Belə ki, dünyanın bəzi sintaktik qəbul şəkər, belə danışmaq.
Söyləyən Bir sexy yol, bu ekvivalent və
bəlkə də daha asan.
Pointer həqiqətən bir göstərici olarsa, arrow notation vasitəsilə getmək və tapmaq
bu halda sahə n çağırıb.
>> Mən bunu tapmaq Belə ki, mən nə görürsünüz.
Mən sadəcə çap I, i tapdı ki, int üçün dəyəri sayede.
I növ üçün yalnız bir ikinci yatmaq zəng üçün ekranda fasilə şeyi
istifadəçi udmaq üçün ikinci vermək Ne oldu.
Və sonra pozub.
Əks halda, mən nə etməliyəm?
Mən bərabər pointer güncelleyin Növbəti göstərici arrow.
>> Belə ki, yalnız aydın olmaq, bu getmək deməkdir , mənim köhnə məktəb notation orada istifadə edərək.
Bu yalnız nə getmək deməkdir Belə ki, Siz çox olaraq, hansı işarə edirik
Birinci halda mən işarə alıram edir bu doqquz ilə struct.
Belə ki, orada getdi etdik.
Və sonra dot notation deməkdir növbəti dəyəri almaq.
>> Amma dəyər, bu tərtib edir, baxmayaraq ki, bir dar kimi, yalnız bir sıra deyil.
Bu rəqəmli ünvan var.
Olub, kod bu bir xətt Belə ki, , bu kimi yazılı daha sirli
yol, və ya bu kimi, bir az daha intuitiv şəkildə, yalnız mənim əl hərəkət deməkdir
növbəti bir ilk node ki, sonra və sonra növbəti bir və
bir sonrakı və s.
>> Beləliklə, biz digər dayanmaq olmaz daxil edin və silin uygulamalarındaki
və traversal, ilk iki olan kifayət qədər cəlb edir.
Və mən onu almaq üçün çox asandır edirəm şifahi bunu zaman itirdi.
Amma biz burada edə bilərsiniz müəyyən etmək üçün cəhd necə
yaxşı vizual bunu.
Mən təklif edirəm ki, əgər biz bu dilinə elementləri əlavə etmək istəyirəm
Mövcud siyahısı, hansı beş elementlər vardır -
9, 17, 22, 26 və 33 -
Mən bu həyata keçirəcəyik, əgər kodu, mən getmək necə nəzərə almaq lazımdır
Bunu haqqında.
>> Və mən körpə addımlar təklif edir Bu halda demək vasitəsi, nə
mümkün ssenariləri ki, ümumi qarşılaşa bilər?
Bağlantılı üçün daxil həyata keçirilərkən siyahısı, bu, yalnız olmaq olur
ölçüsü beş xüsusi nümunəsidir.
Əgər bir rəqəm daxil etmək istəyirəm yaxşı, əgər bir nömrəli demək istəyirəm və
harada, sorted asayişin qorunması açıq-aydın bir ehtiyac sayı yoxdur
bu nümunə getmək?
Əvvəlinə kimi.
>> Amma maraqlı nə var Bu daxil bir əlavə etmək istəyirsinizsə,
siyahısı, nə xüsusi pointer lazımdır yəqin aydınlıq olmalıdır?
Birinci.
Beləliklə, mən bu ilk halda, iddia edirəm biz, hesab edə bilərsiniz ki,
da daxil cəlb ssenari siyahının başında.
>> Hətta bir qədər asan və ya bəlkə yoluq-yoluq edək asan halda, nisbətən danışan.
Mən əlavə etmək istəyirəm Güman sorted üçün sayı 35.
Bu açıq-aydın orada məxsusdur.
Yaxşı göstərici açıq-aydın gedir ki, ssenari yenilənir lazımdır?
34-nin göstərici null deyil çevrilir lakin struct yerləşdiyi ünvan
sayı 35 olan.
Belə ki, bu halda iki var.
Belə ki, artıq mən quantizing növ Ben Mən burada nə qədər çalışır.
>> Və nəhayət, açıq-aydın ortada olduğu Həqiqətən, ortasında, əgər mən istəyirəm
gedir ki, 23 kimi bir şey daxil 23 və 26 arasında, lakin
indi hər şeyi bir az daha çox almaq cəlb çünki nə
göstəricilərinə dəyişdirilə lazımdır?
22 açıq-aydın dəyişdirilə lazımdır Belə ki, O, artıq 26-qeyd bilməz.
O, yeni node qeyd etmək lazımdır ki, Mən zəng ayrılması lazımdır
malloc və ya bir ekvivalent.
>> Amma sonra mən də ki, yeni node, 23 ehtiyac Bu halda, onun pointer var
kimə də işarə?
26.
Və bir olmalıdır gedir Burada əməliyyatlar üçün.
Çünki mən ağılsızlıq bunu, mən əgər əvvəlində misal başlamaq üçün
siyahısı və mənim qol 23 daxil etməkdir.
Və mən bunu aid edir, yoxlamaq Burada doqquz yaxın?
No
Bu 17 növbəti, burada məxsusdur mu?
No
O, 22 yanındakı burada məxsusdur mu?
Bəli.
>> İndi mən burada axmaq Ben əgər deyil, Bu vasitəsilə düşüncə, mən güc
23 Yeni node ayırırlar.
Mən göstərici yeniləmə bilər node işarə edərək, 22 çağırıb
bu yeni node edir.
Və sonra yeniləmə nə var Yeni node in göstərici olacaq?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Eynilə elə.
26 işarə edərək.
Mən artıq verməmişdir Amma əgər dammit 22-nin göstərici bu oğlan da qeyd və
İndi yetimlər, istirahət siyahı, belə danışmaq.
Burada əməliyyatların Belə sifarişi əhəmiyyətli olacaq.
>> Bunu etmək üçün, mən oğurlamaq bilər , altı könüllü deyirlər.
Və biz bunu edə bilərsiniz Bakalým vizual əvəzinə kod müdrik.
Və biz bir sevimli stress var Bu gün sizin üçün top.
OK, haqqında bir, iki, də Geri - orada sonunda.
Siz də üç, dörd, sonunda uşaqlar.
Və beş, altı.
Əmin olun.
Beş və altı.
Bütün hüquqlar və biz gələcəyik! Siz uşaqlar üçün növbəti dəfə.
Bütün hüquqlar qədər gəlib.
>> Bütün sağ, burada ilk istəyirik yana, Siz yöndəmsiz bir olmaq istəyirəm
Burada Google şüşə?
Bütün sağ, belə, OK, Cam, bir video qeyd edin.
OK, siz getmək iyi.
>> Bütün sağ, belə ki, uşaqlar üzərində gəlmək bilər Burada əvvəlcədən hazırlamışıq
bir ədəd.
Bütün sağ, burada gəlib.
Və niyə bir az getmirlər daha yol.
Və nin görək, adınız nədir, Google Glass ilə?
>> TƏLƏBƏ: Ben.
>> HOPARLÖR 1: Ben?
OK, Ben, siz sözün birinci olacaq.
Beləliklə, biz göndərmək olacaq səhnə sonuna.
Bütün sağ, və adı?
>> TƏLƏBƏ: Jason.
>> HOPARLÖR 1: Jason, OK will sayı doqquz ola bilər.
Siz Ben o yolla istəyirəm əgər.
>> TƏLƏBƏ: Jill.
>> HOPARLÖR 1: Jill, siz olacaq 17, I daha çox işlər etsəniz
ağıllı, mən var ki, digər sonunda başladı.
Bilirsiniz ki, yol getmək.
22.
Və siz?
>> TƏLƏBƏ: Mary.
>> HOPARLÖR 1: Mary, siz 22 olacaq.
Və adı?
>> TƏLƏBƏ: Chris.
>> HOPARLÖR 1: Chris, siz 26 olacaq.
Və sonra son.
>> TƏLƏBƏ: Diana.
>> HOPARLÖR 1: Diana, siz 34 olacaq.
Belə ki, burada gəlib.
>> Bütün sağ, belə sıralanır təkmilləşdirilməsi artıq sifariş.
Və nin irəli getmək və bunu bildirin belə ki, biz, həqiqətən bilər -
Ben siz axtarır yalnız cür istəyirik həyata heç bir yerdə orada daxil.
OK, belə ki, in irəli getmək və bu təsvir edək Mən çox istəyirəm, silah istifadə edərək, dəqiq,
neler.
Belə ki, davam və özünüzü ver ayaq və ya aranızdakı iki.
Və bir tərəfdən ilə davam və qeyd sizə kim işarə edilməlidir
bu əsaslanır.
Siz null əgər və yalnız qeyd düz aşağı mərtəbə.
OK, belə yaxşı.
>> Belə ki, indi biz bir bağlı siyahı var və mənə bildirin Mən rolunu oynamaq lazımdır ki, təklif
Ptr, mən narahat deyil ətrafında bu balans.
Və sonra - kimsə axmaq Konvensiyası - istədiyiniz bu bir zəng edə bilərsiniz -
sələfi göstərici proqnozu pointer -
yalnız biz verdi ləqəb var mənim sol tərəfdən Örnek kodu.
Saxlanılması olacaq ki, digər tərəfdən olan olan takip
ssenari aşağıdakı.
>> Belə ki, ilk, mən off dərmək istəyirəm, güman daxil olduğunu ilk nümunəsi, demək
20 siyahısına daxil.
Beləliklə, mən kimsə lazımdır gidiyorum bizim üçün sayı 20 etdirir.
Beləliklə, mən malloc kimsə lazımdır tamaşaçı.
Up Hadi.
Sizin adınız nədir?
>> TƏLƏBƏ: Brian.
>> HOPARLÖR 1: Brian, bütün sağ, belə ki, 20 olan node olmalıdır.
Bütün sağ, burada gəlib.
Və təbii ki, burada Brian aid edir?
Belə ki, ortasında - faktiki olaraq, bir dəqiqə gözləyin.
Biz üçün bu həyata edirik.
Biz bir çox çətindir bu edirik Bu ilk olmalıdır edir.
OK, biz pulsuz Brian olacaq və beş realloc Brian.
>> OK, belə ki, indi biz daxil istəyirik Beş Brian.
Belə ki, yanında buraya gəlib Yalnız bir an Ben.
Və ehtimalla deyə bilərsiniz Bu hekayə gedir yerləşir.
Lakin edək haqqında diqqətlə düşünmək əməliyyatları üçün.
Və məhz bu vizual var sıralamaq olacaq ki,
ki, örnek kod ilə.
Belə ki, burada mən Ptr əvvəlcə işarə var deyil per se Ben,, lakin hər hansı bir at
O, ehtiva dəyəri bu halda deyil - adınız yenidən var?
>> TƏLƏBƏ: Jason.
>> HOPARLÖR 1: Jason, Ben və mən də belə Hal-hazırda Jason da işarə.
Belə ki, indi müəyyən etmək üçün var, Brian Ü aid edir?
Tək şey Beləliklə, mən etmək imkanı var İndi onun n data item edir.
Buna görə yoxlamaq gidiyorum Jason daha Brian az?
Cavab doğrudur.
>> Beləliklə, nə indi, nə etmək lazımdır düzgün qaydada?
Mən neçə göstəricilərinə güncellemeniz lazımdır Bu hekayə cəmi?
Mənim əl hələ də işarə edir Harada Jason, və əl - Əgər istəyirsinizsə
növ kimi sizin əl qoymaq, mən bir sual işarəsi bilmirəm.
OK, yaxşı.
>> Bütün sağ, siz belə bir neçə namizəd.
Ben yaxud I və ya Brian ya Jason Ya başqa və ya hər kəs, hansı
göstəricilərinə dəyişdirmək lazımdır?
Necə ümumi bir çox?
>> OK, belə ki, iki.
Mənim göstərici həqiqətən artıq etməz Mən yalnız müvəqqəti Ben çünki.
Belə ki, ehtimalla, bu iki uşaqlar var Ben və Brian də.
Beləliklə, biz yeniləmə ki, mənə təklif edək Ben, ildən ilk var.
Bu siyahıda ilk element indi Brian olacaq.
Brian belə Ben nöqtə.
OK, indi nə?
>> Kim da qeyd edilir?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: OK belə Brian var Jason da qeyd etmək.
Amma pointer izini itirmiş?
Jason harada mən bilirsinizmi?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Ben çünki mən, nə müvəqqəti göstərici.
Və ehtimalla, mən dəyişməyib Yeni node da qeyd etmək.
Beləliklə, biz sadəcə Brian nöqtəsi ola bilər kim mən də işarə edirəm.
Və biz tamamlayın.
Belə halda biri də durub siyahı əvvəli.
Iki əsas addım var idi.
Bir, biz Ben yeniləmək üçün var, və sonra biz də Brian yeniləmək lazımdır.
Və sonra mən narahat yoxdur geri qalan vasitəsilə traipsing
Biz artıq aşkar siyahısı, çünki onun O məxsus yer, çünki
ilk element sol.
>> Bütün sağ, belə olduqca sadə.
Biz demək olar ki, etdiyiniz kimi, əslində, hiss Bu çox mürəkkəb edir.
Belə ki, indi sonunda yoluq-yoluq bildirin siyahısı, və harada görmək
mürəkkəbliyi başlayır.
Tamaşaçı Belə ki, indi, mən alloc.
Hər kəs 55 oynamaq istəyirsiniz?
Bütün sağ, mən ilk əl gördüm.
Up Hadi.
Bəli.
Sizin adınız nədir?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Habata.
OK qədər gəlib.
Siz sayı 55 olacaq.
Beləliklə, siz, əlbəttə, məxsusdur siyahının sonunda.
Elə mənimlə simulyasiya replay imkan yalnız bir an Ptr olan.
Beləliklə, mən ilk qeyd etmək gidiyorum Ben-da işarə edir nə.
Biz indi Brian da işarə edirik də.
Belə ki, 55-dən az beş deyil.
Belə ki, I özümü yeniləmək üçün gidiyorum Brian növbəti göstərici işarə edən
İndi əlbəttə Jason edir.
55 belə az doqquz deyil Mən Ptr yeniləmək üçün gedirəm.
Mən Ptr yeniləmək üçün gidiyorum Mən Ptr yeniləmək üçün gedir.
Və mən gedirəm - hmm, ne adınız yenidən?
>> TƏLƏBƏ: Diana.
>> HOPARLÖR 1: Diana işarə edir, əlbəttə, onun sol əli ilə null edir.
Beləliklə, harada Habata əslində yoxdur aydın məxsusdur?
Sola, burada.
Belə ki, necə mən burada onun qoymaq üçün bilmirəm Mən qədər berbat sonra hesab edirəm.
Nə Ptr incəsənət Çünki vaxt bu an?
Null.
Belə olsa da, vizual, biz açıq-aydın bütün bunlar bax
burada səhnəyə uşaqlar.
Mən əvvəlki track saxlanılır deyil etdik Siyahıda şəxs.
Mən işarə barmağı yoxdur Bu halda, node sayı 34.
>> Elə həqiqətən bu artıq başlamaq bildirin.
Belə ki, indi mən, həqiqətən lazımdır ikinci yerli dəyişən.
Və bu siz görürsünüz nə faktiki nümunə C kodu kimi mən getmək harada,
Mən qeyd etmək mənim sağ yeniləmə zaman Jason, bununla mən geridə Brian tərk
daha mənim sol tərəfdən istifadə edərək başlamaq Mən harada getmək kimi ki, yeniləmə
Bu siyahıda vasitəsilə -
daha yöndəmsiz I nəzərdə dən indi burada vizual -
Mən almaq üçün gidiyorum siyahısı sonu.
>> Bu tərəfdən olduqca ki, hələ null edir göstərmək üçün başqa faydasız
Mən siyahının sonunda aydın Ben amma indi ən azı mən bu var
sələfi göstərici Belə ki, burada işarə indi nə əllər və nə göstəricilərinə lazımdır
aydınlıq olmalıdır?
Kimin tərəfdən istəyirsiniz ilk reconfigure?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: OK, Diana belə.
Harada qeyd etmək istəyirəm At Diana sol pointer?
55, güman ki, belə biz daxil etdik.
Və harada 55 pointer getmək lazımdır?
Down, null etdirir.
Və mənim əlləri, bu nöqtədə deyil Onlar yalnız, çünki Fərq
müvəqqəti dəyişənlər.
Belə ki, indi biz tamamlayın.
>> Belə ki, əlavə var mürəkkəbliyi - və ki, həyata ki, çətin deyil
lakin biz etmək üçün orta dəyişən lazımdır əmin mən sağa hərəkət əvvəl
əl, mən sol dəyəri yeniləmək tərəfdən proqnozu bu halda pointer, belə ki,
Mən arxada göstərici var ki, Mən harada takip.
İndi bir kənara kimi, bu düşünür istəyirsinizsə bu kimi vasitəsilə bu hiss bir
saxlamaq üçün az annoying bu sol tərəfdən baxın.
>> Nə başqa bir həll ki, Bu problemin olub?
Veri yeniden tasarlarken var, əgər biz danışıqlar strukturu
İndi vasitəsilə?
Bu yalnız cür bir az hiss edin kimi, iki göstəricilərinə malik annoying
başqa edən siyahısını bilər gedir ideal dünyada, saxlamışlar
biz lazımdır ki, informasiya?
Bəli?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Eynilə elə.
Sağ belə maraqlı həqiqətən var bir fikir rüşeymləri.
Və əvvəlki göstərici bu fikir, əvvəlki element də işarə.
Mən yalnız təcəssüm ki, əgər siyahısını özü daxilində?
Və görüntüləmək üçün çətin olacaq Bu, bütün kağız olmadan
yerə düşür.
Lakin bu uşaqlar də istifadə edirlər ki, əllərini bir əvvəlki var
bununla pointer və sonrakı göstərici biz ikiqat arayacaðým nə həyata
bağlı siyahısı.
Ki, mənə geri növ imkan verir daha asanlıqla mənə olmadan,
proqramçı saxlamaq üçün olan əl Track -
həqiqətən əl -
Mən əvvəllər olmuşdu harada Siyahıda.
Belə ki, etməyəcək.
Ki, çünki Biz bu sadə davam edəcəyik iki dəfə kimi bir qiymətə gəlib gedir
ki göstəricilərinə üçün çox yer, Bir ikinci istəyirsinizsə.
Amma bu, doğrudan da yaygın data strukturu kimi tanınan
ikiqat siyahısı bağlıdır.
>> Burada son misal etmək və qoymaq edək onların həyatlarının həyata bu uşaqlar.
Malloc 20 belə.
Orada koridorda qədər Hadi.
Bütün sağ, adınız nədir?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Pardon?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Demeron?
OK qədər gəlib.
20 olmalıdır.
Siz açıq-aydın edir 17 və 22 arasında məxsusdur.
Belə ki, mənə dərs bildirin.
Mən göstərici başlamaq üçün gidiyorum Brian da işarə.
Mən sol əl üçün gidiyorum Mən hərəkət kimi yalnız Brian yeniləmə
Jason, yoxlanılması doqquz 20-dən az edir?
No
17 20-dən azdır?
No
22 20-dən azdır?
Bəli.
Beləliklə, nə göstəricilərinə və ya əlləri dəyişdirmək lazımdır onlar indi işarə edirik?
>> Beləliklə, biz 20 işarə 17 edə bilərsiniz.
Belə ki, gözəl.
Biz qeyd etmək istəyirik Sizin pointer indi?
22.
22 Harada və yenə, thanks bilirik mənim müvəqqəti göstərici üçün.
Beləliklə, biz OK orada istəyirik.
Belə ki, çünki bu müvəqqəti saxlama Mən hər kəs olduğu takip saxlanılır etdik.
İndi siz vizual yerləşir daxil edə bilərsiniz Siz məxsusdur və indi 1, 2, 3, ehtiyac
4, 5, 6, 7, 8, 9 stress top, və alqışlarla bir dəyirmi
Bu uşaqlar, biz bilər.
Qəşəng edilir.
>> [Alqış]
>> HOPARLÖR 1: Yaxşı.
Və ədəd saxlaya bilər mementos kimi kağız.
>> Bütün sağ, belə ki, bir çox var mənə etibar asan ilə vasitəsilə gəzmək
faktiki kodu ilə daha insanlar.
Amma nə bir an tapa bilərsiniz İndi ki, eyni - oh, təşəkkür edirəm.
Təşəkkür edirik -
siz eyni məlumat tapa bilərsiniz ki, strukturu, bir bağlı siyahı əslində bilər
daha bir bina blok kimi istifadə edilə müasir data strukturlar.
>> Və burada da mövzu dərk edir ki, biz tamamilə daha təqdim etdik
yerinə mürəkkəbliyi Bu alqoritm.
Durub, və biz onun vasitəsilə gedib, silinməsi və axtarış, bir az
bu daha mürəkkəb bir sıra idi.
Amma biz bir dinamizm qazanmaq.
Biz adaptiv data structure almaq.
>> Ancaq yenə də, bəzi olan bir qiymət ödəmək əlavə mürəkkəbliyi, həm də
bunu həyata keçirir.
Və biz rasgele erişim imtina edirik.
Və vicdanlı olmaq, bəzi gözəl mövcud deyil slide təmiz Mən sizə verə bilər ki,
burada deyir niyə bağlıdır siyahısı bir sıra daha yaxşıdır.
Və onu buraxın.
Mövzusunda, hətta indi reoccurring Çünki daha belə önümüzdəki həftə edir
mütləq yoxdur ki, doğru cavab.
>> Biz ayrı-ayrı ox niyə bu problem kümeleri üçün dizayn.
Bu, çox kontekstində həssas olacaq Bu məlumatdan istifadə etmək istəyirəm olub
strukturu və ya bir və olacaq baxımından sizə məsələ nə asılıdır
resursları və mürəkkəblik.
>> Amma mənə təklif edək ki, ideal data strukturu, müqəddəs grail olacağını
daimi vaxt ki, bir şey, asılı olmayaraq, çox şeylər necə
bu, daxili, gözəl ola bilməz ki, bir halda data structure cavab döndü
daimi vaxt.
Bəli.
Bu söz üçün böyük lüğət edir.
Və ya heç bu söz deyil.
Yoxsa, hər hansı bu cür problem.
Yaxşı görək biz ən azı əgər ki, doğru bir addım atmaq.
>> Mənə bir yeni məlumatlar strukturu təklif edək ki, müxtəlif şeylər üçün istifadə edilə bilər,
Bu halda bir hash masa çağırıb.
Və belə ki, biz salan geri həqiqətən istəyirik bir bu halda dizi,, və
qədər özbaşına, bu tərtib etdik bir növ ilə bir sıra kimi hash table
iki ölçülü Array -
daha doğrusu bir iki burada təsvir var ölçülü Array - ancaq bu yalnız
Belə ölçüsü 26 bir sıra ki, əgər biz serialın masa, masa bracket zəng
sıfır üst düzbucaqlı edir.
Cədvəl bracket 25 düzbucaqlı edir alt.
Bu Mən data çəkmək bilər necə Mən saxlamaq istədiyiniz strukturu
insanların adları.
>> Belə ki, məsələn, mən də cəlb edəcək burada hava haqqında bütün şey, əgər mən
İndi gedirəm bu array var idi, bir hash masa zəng və bu, yenə
yeri sıfır.
Burada yeri, bir, və s.
Mən bu məlumatdan istifadə etmək istəyirəm ki, iddia strukturu, müzakirə naminə,
insanların adları saxlamaq üçün, Alice və Bob və Charlie və digər bu kimi adlar.
Belə ki, başlanğıclar kimi indi bu hesab Bir lüğət, demək ki,
sözləri çox.
Onlar adları nə Burada nümunə.
Və bu, bəlkə də, bütün çox ilgili edir biz, bir yazım checker həyata
problem üçün altı müəyyən edə bilər.
>> Biz ümumi ölçüsü 26 bir sıra var Belə ki, əgər Bu 25-ci yeri, belə ki,
alt və mən Alice olduğunu iddia lüğətini ilk sözü
Mən RAM daxil istəyirəm ki, adları, Bu data strukturu, harada var
belirten instinktlərdən ki, Alice adı bu sıra getmək lazımdır?
>> Biz 26 variantları var.
Biz öz qoymaq istəyirik harada?
Biz bracket sıfır onun istəyirsiniz mi?
Alice üçün, ki, sıfır zəng edək.
Və b biri olacaq və C iki olacaq.
Beləliklə, biz yazmaq olacaq Burada Alice adı up.
Sonra Bob onun daxil edin adı burada gedəcək.
Charlie burada gedəcək.
Və s down vasitəsilə Bu data quruluşu.
>> Bu gözəl data strukturu.
Niyə?
Quyunun çalışan zaman nə bu bir insan adı daxil
İndi data structure?
Bu cədvəldə həyata keçirilir olduğunu nəzərə alaraq, həqiqətən, bir sıra kimi.
Yaxşı daimi vaxt var.
Bu, bir qaydası var.
Niyə?
>> Yaxşı necə müəyyən edirsiniz Alice aid olduğu?
Siz onun adı olan məktub baxmaq?
İlk.
Bir string varsa və siz orada əldə edə bilərsiniz yalnız simli baxaraq
bracket sıfır.
Ki, simli zeroth xarakteri belə.
Bu çox asandır.
Biz gizli ki, etdi təyin həftə əvvəl.
Və sonra bir dəfə ki, Alice bilirik məktub kapital, biz çıxmaq bilər
65 və ya kapital A özü, off ki, sıfır verir.
Beləliklə, biz indi Alice məxsusdur bilirik ki, yeri sıfır.
>> Bu data göstərici verilir strukturu, bir növ, nə qədər görür
o yeri tapmaq üçün mənə almaq bir sıra sıfıra?
Yalnız bir addım, doğru daimi vaxt təsadüfi giriş çünki biz
Təklif olunan bir sıra bir xüsusiyyət idi.
Belə ki, qısa, figuring nə indeksi ALICE adını, olan deyil
Bu halda, A, və ya edək yalnız həll sıfır olduğu B biridir və C ki,
iki ki, figuring daimi dəfə.
Mən yalnız onun ilk məktub baxmalıyıq sıfır olduğu figuring bir
array də daimi dəfə.
Belə ki, texniki var İndi iki addımlar kimi.
Amma hələ də daimi deyil.
Beləliklə, biz bir böyük O zəng ki, biz var Bu cədvəl daxil Alice daxil
daimi vaxt.
>> Amma əlbəttə, mən olan alıram burada sadəlövh, sağ?
Nə sinif bir Aaron var əgər?
Və ya Alicia?
Və ya hər hansı digər adları ilə başlayan A. Biz qoymaq üçün gedir
həmin şəxs, sağ?
Mən demək, hazırda yalnız üç var masa insanlar, belə ki, bəlkə biz
yer Aaron qoymalıdır sıfır bir iki üç.
>> Sağ, burada A qoymaq bilər.
Lakin sonra, biz daxil David əlavə etmək üçün cəhd edin Bu siyahıda, David nereye gidiyor?
İndi bizim sistem qırılma başlayır aşağı, sağ?
İndi David burada bitir Çünki Aaron burada əslində əgər.
Malik və artıq bu bütün fikir bizə verir ki, təmiz data structure
daimi vaxt insertions artıq Mən çünki daimi vaxt,
yoxlamaq, oh, damnit, kimsə artıq var Alice in yerdə.
>> Mənə Bu data qalan sonda edək strukturu, qoymaq üçün bir ləkə axtarır
Harunun adı kimi kimsə.
Və buna görə də başlayır ki, xətti vaxt.
Bundan əlavə, indi tapmaq istəyirsinizsə, Bu data tərkibində Harun və siz
yoxlamaq və Harunun adı burada deyil.
İdeal halda, yalnız Harunun deyərdim deyil data strukturunda.
Amma əgər üçün otaq edilməsi başlamaq Harun bir D olmalı idi
və ya E, siz, ən pis halda, yoxlamaq üçün olan bütün məlumat strukturu,
bir şey daxil devolves bu halda masanın ölçüsü xətti.
>> Bütün sağ Belə ki, mən bu düzeltmek lazımdır.
Burada problem var idi ki, Bu array 26 elementləri.
Mənə dəyişdirmək edək.
Whoops.
Daha çox olan, belə ki, mənə dəyişdirmək imkan cəmi ölçüsü 26, alt qeyd
index n mənfi 1 dəyişdirmək üçün gedir.
26 insanların üçün aydın çox kiçik deyil adları, çünki minlərlə var
Dünyanın adları, ədalətli edək 100 və ya 1000 və ya 10,000 edir.
Ədalətli bir çox yer ayırmağa edək.
>> Yaxşı mütləq azaltmaq deyil ki, iki olmayacaq ehtimalı
adları ilə insanlar ilə başlayan və belə ki, siz qoymaq üçün cəhd gedirdi
hələ yeri sıfır adları.
Onlar hələ toqquşmaq olacaq olan biz hələ qoymaq üçün bir həll lazımdır deməkdir
Alice və Harunun və Alicia və digər A başqa yerdə ilə başlayan adlar.
Amma bu nə qədər problem var?
Ehtimalı nədir ki, bir məlumatları toqquşma var
bu kimi strukturu?
>> Yaxşı, mənə bildirin - biz geri gəlmək lazımdır Burada sual.
Və necə ola bilər baxmaq ilk həll edir.
Məni bura bu təklifi qoparmaq edək.
Biz yalnız təsvir bir alqoritmi belədir xətti adlı bir Heuristic
Siz daxil cəhd əgər vasitəsi probing Bu data burada bir şey
bir hash masa adlanan strukturu, və heç bir otaq var var
həqiqətən data structure sonda yoxlanılması, bu mümkündür?
Bu mövcud bu mümkün mü?
Bu mövcud?
Və nəhayət olduqda, siz daxil siz ilk nəzərdə ki, adı
başqa yerdə ki, yer.
Amma pis halda, yalnız spot məlumatların çox aşağı ola bilər
strukturu, serialın çox sonunda.
>> Belə ki, xətti, ən pis halda, probing, xətti alqoritm daxil devolves yerləşir
Aaron, keçən daxil edilməlidir olur Bu data strukturu, o, güc
Bu ilk yeri ilə toqquşmaq, lakin sonra çox sonunda pis luck ilə başa.
Beləliklə, bu daimi deyil bizim üçün vaxt müqəddəs grail.
Daxil elementlərinin Bu yanaşma nəzərə məlumat strukturu hash çağırıb
masa daimi dəfə görünmür ən azı ümumi halda.
Bu xətti bir şey qalmaq bilər.
>> Biz toqquşma həll Yaxşı, əgər qədər fərqli?
Belə ki, burada daha təcrübəli var hələ nə müraciət
bir hash masa çağırıb.
Və hash ilə bir kənara, nə kimi Hesab edirəm ki, index demək
Mən əvvəllər edilir.
Etmək üçün hash bir şey ola bilər bir verb kimi düşündüm.
>> Əgər hash Alice bir adı var Belə ki, bir hash funksiyası, belə danışmaq,
bir sıra qaytarmalıdır.
O da məxsusdur Bu halda əgər sıfır o da aiddir, əgər yeri sıfır, bir
yeri bir, və s.
Belə ki, mənim hash funksiyası belə uzaq olub super sadə, yalnız baxaraq
Birinin adı ilk məktubu.
Amma hash funksiyası kimi görür input data bir parça, bir
simli, bir int, nə.
Və adətən bir sıra spits.
Və ki sayı olduğu məlumatlar element data structure məxsusdur
bir hash masa kimi burada bilinir.
>> Belə ki, yalnız daxilən, bu, az fərqli kontekstində.
Bu əslində bir nümunə istinad cəlb ad günü olduğu
kimi bir çox ola bilər Ay 31 gün.
Lakin bu şəxs nə qərar verdiniz bir toqquşma halında nə?
Context indi bir toqquşma olmayan adları, lakin ad günləri toqquşma,
iki nəfər eyni ad varsa Məsələn oktyabr 2-ci.
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Bəli, belə ki, burada biz bağlı siyahılarının yararlanarak.
Belə ki, fərqli bir az görünür biz əvvəllər cəlb edir.
Amma biz bir sıra üçün görünür sol tərəfində.
Bu heç, bir index var xüsusi səbəb.
Amma hələ bir sıra var.
Bu göstəricilər bir sıra var.
Və hər bir bu elementlərin hər biri Bu dairələr və ya slashes - Bu çizgi
təmsil null - bu hər göstəricilərinə yəqin işarə edir
nə data structure?
A bağlıdır siyahısı.
>> Belə ki, indi biz imkanı var bizim proqram ağır kodu
Tablonun ölçüsü.
Bu halda, biz heç vaxt olduğunu bilirik bir ay çox 31 gün.
Belə ağır 31 kimi bir dəyəri coding Bu kontekstdə müvafiq.
Adları kontekstində, ağır kodlaşdırma 26 əsassız deyil insanların
adları yalnız, məsələn, ilə başlamaq Z. vasitəsilə cəlb əlifbası
>> Biz ki, data onları bütün CRAM bilər strukturu belə uzun biz zaman kimi
toqquşma, biz burada adları qoymaq deyil, yerine bu hüceyrələr hesab
deyil strings özləri, lakin kimi Məsələn, Alice göstəricilərinə.
Və sonra Alice başqa bir pointer ola bilər ilə başlayan başqa adı
A. Və Bob həqiqətən burada üzərində gedir.
>> Və başlanğıc başqa bir ad var, əgər B ilə, o burada bitər.
Və belə bu elementlərin hər birindən biz bu nəzərdə əgər masa iki,
az daha ağıllı -
gəlib -
Biz bu bir az daha nəzərdə əgər ağılla, indi bir adaptiv data çevrilir
heç bir ağır limit var olduğu quruluşu, Siz əlavə edə bilərsiniz neçə elementləri
onu Əgər çünki bir toqquşma ki, gözəl.
Yalnız irəli getmək və ona əlavə biz idi bir az əvvəl gördüyüm
bir bağlı siyahı kimi tanınır.
>> Yaxşı, yalnız bir an nin fasilə edək.
Bir toqquşma ehtimalı nədir ilk növbədə?
Sağ, bəlkə artıq, bəlkə düşünür alıram Mən bu problem Engineering artıq Ben
nə bilirlər?
Bəli, mən özbaşına ilə gəlmək olar kimi mənim baş üst off nümunələri
Allison və Harun, lakin əslində, vahid paylanması verilmişdir
bəzi təsadüfi insertions ki, giriş, məlumat strukturu, həqiqətən nə
bir toqquşma ehtimalının?
Yaxşı çıxır, bu, həqiqətən var super yüksək.
Bu mənə ümumiləşdirmək edək problem bu deyil.
>> Belə n bir otaqda CS50 tələbələr, var ehtimal ki, ən azı
otaqda iki tələbə eyni ad var?
Belə ki, nə var. bir neçə Hund -
Burada bir neçə 200, 300 nəfər Bu gün evdə yüz nəfər.
Siz nə özümüzü soruşmaq istəyirdi Belə ki, əgər iki nəfər ehtimalı
eyni ad günü olan bu otaqda, biz bu anlamaq bilər.
Və mən iki var həqiqətən iddia eyni ad günü insanlar.
>> Məsələn, hər kəs edir Bu gün ad günü var?
Dünən?
Sabah?
Gedirəm kimi bütün hüququ, belə ki, hiss daha bu 363 və ya bunu etmək
dəfə həqiqətən anlamaq üçün biz bir toqquşma var.
Və ya biz yalnız riyazi bunu edə bilər daha maraqsız çox
bunu.
Və aşağıdakı təklif edirik.
>> Ona görə də mən, biz model ola bilər ki, təklif Əyalətin iki nəfər ehtimalı
1 ehtimalı eyni ad günü olan heç bir mənfi ehtimalı
eyni ad.
Belə ki, bu almaq üçün və bu yalnız edir üçün Bu yazı xülya yolu,
oda ilk şəxs, o, mümkün hər hansı bir ola bilər
ad günləri, ildə 365 gün hərfinin şəxslər üçün üzr ilə
Fevral 29 doğum günüdür.
>> Belə ki, bu otaq ilk adam pulsuz Ad günləri hər hansı bir sayı üçün
həyata 365 imkanlarının ki, biz, 365 ilə 365 ayırmış edəcəyik
olan biridir.
Oda növbəti şəxs, əgər məqsəd bir toqquşma qarşısını almaq üçün, yalnız
necə onun ad günü var çox müxtəlif mümkün gün?
364.
Belə ki, bu ifadə ikinci dövr mahiyyətcə bizim üçün ki, riyaziyyat bunu
bir mümkün günü çıxarılaraq.
Və sonra növbəti gün, növbəti gün, aşağı ümumi sayına Növbəti gün
oda insanların.
>> Və biz sonra nəzərə alsaq, onda nə olmayan hər kəs ehtimalı
unikal ad günləri, lakin yenə 1 minus ki, biz əldə ifadə
çox fancifully bilər bu kimi görünür.
Amma daha maraqlı var vizual baxmaq.
Bu x-ox üzrə olduğu bir chart edir oda insanların sayı,
Ad günləri sayı.
Y-ox üzrə ehtimalı bir vuruşma, iki nəfər
eyni ad günü olan.
>> Bu əyri olan paket edir ki, siz 40 kimi almaq kimi tezliklə
tələbələr, siz 90% ehtimal da hazır combinatorically iki
insanların və ya daha çox olan eyni ad.
Və sonra bu 58 adam kimi almaq bir şans iki təxminən 100%
oda insanlar üçün gedir eyni ad var olsa belə,
365 və ya 366 mümkün buketler və otaqda yalnız 58 nəfər.
Yalnız statistik siz güman etdiyiniz , toqquşma almaq qısa
Bu müzakirə motive.
Biz burada xülya almaq, hətta ki, əgər Bu zəncirlər olan başlamaq, biz hələ istəyirik
toqquşma edəcəyik.
>> Sualına begs Belə ki, nə edir insertions ve silme bunu dəyəri
bu kimi bir veri strukturu?
Yaxşı mənə təklif edək -
və mənə üzərində ekrana geri gidelim burada - biz elementlərinin N əgər
siyahısı, biz daxil çalışdığınız əgər n elementləri, və biz
neçə ümumi buketler?
Gəlin 31 cəmi buketler Cavab Ad günləri halda.
Bir maksimum uzunluğu nədir potensial bu zəncirlər?
>> Daha mümkün 31 varsa müəyyən bir ayda ad günü.
Və biz yalnız hər kəs clumping edirik -
əslində bir axmaq nümunə var.
Əvəzinə 26 etmək edək.
Həqiqətən adları adam var Belə ki, əgər bununla verilməsi, Z vasitəsilə başlamaq
Bizi 26 imkanları.
Və biz kimi bir veri strukturu istifadə etdiyiniz biz qovuşdurmağımız biz yalnız gördüm bir,
göstəricilərinə bir sıra, o cümlədən hər bir burada bir bağlı siyahısına bal
ilk siyahısı hər kəs adı Alice ilə.
İkinci siyahı hər ilə başlayaraq, A ilə başlayan ad
B, və s.
>> Hər ehtimal uzunluğu nədir həmin siyahıların biz gözəl təmiz fərz əgər
A-dan Z vasitəsilə adları bölüşdürülməsi bütün data structure arasında?
Veri strukturu n insanlar var onlar qəşəng istəyirsinizsə, 26 bölünür
bütün üzərində yayılmışdır data structure.
Belə ki, bu hər birinin uzunluğu zəncirlər 26 bölünür n.
Lakin böyük O notation ki, nədir?
Həqiqətən nədir?
Belə ki, sağ, həqiqətən yalnız n var?
Biz keçmişdə deyib sonra Çünki, uf siz 26 bölmək ki.
Bəli, əslində daha sürətli edir.
Lakin nəzəriyyəsi, o, əsaslı deyil bütün sürətli.
>> Belə ki, biz bütün ki, çox ola görünmüyor yaxın bu müqəddəs grail üçün.
Əslində, bu, yalnız xətti dəfə.
Heck, bu nöqtədə, nə biz bunu yalnız bir böyük bağlı siyahısını istifadə edin?
Niyə biz bir böyük istifadə etməyin adları saxlamaq üçün array
otaqda hər kəs?
Yaxşı, bir şey hələ də var bir hash masa haqqında çekici?
Çekici bir şey hələ də məlumat strukturu haqqında
bu kimi görünür?
Bu.
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: yalnız hüququ və yenə əgər xətti vaxt alqoritm və
xətti vaxt data strukturu, nə deyil yalnız böyük hər kəsin adı saxlamaq
dizi, və ya böyük bağlı siyahıda?
Və belə çox çətindir CS edilməsi dayandırmaq bu olmalıdır çox?
Hətta bu barədə çekici nədir Mən onu cızıqlanmış baxmayaraq?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Insertions deyil?
Artıq bahalı.
Belə ki, insertions potensial hələ ola bilər , daimi vaxt ola bile data
struktur, bu kimi bir sıra görünür göstəricilər də işarə edir hər biri
potensial bağlı siyahısı.
Necə sabit nail adları vaxtı durub?
Sağ, qarşısında qalmaq?
>> Biz bir dizayn qol qurban edin əvvəllər, biz saxlamaq istəyirdi yerləşir
hər kəsin adı, məsələn, sorted, və ya səhnədə ədəd bütün sıralanır
biz ki, güman çeşidlənməmiş bağlı siyahısı.
Bu, yalnız, bizə bir-iki addım xərcləri Ben və Brian halda olduğu kimi
əvvəllər bir element əlavə etmək üçün siyahının başında.
Biz bütün çeşidlənməsi haqqında qayğı yoxdur Belə ki, əgər ilə başlayan adlar A və ya bütün
B ilə başlayan adlar, biz hələ də bilər daimi vaxt durub nail olmaq.
İndi Alice ya Bob və ya hər hansı bir ad ararken ümumiyyətlə hələ nədir?
Bu 26 bölünür n böyük O, var hər kəs bərabər olduğu ideal halda
paylanmış, kimi bir çox A var olduğu Z-nin, yəqin olan var
qeyri-real.
Amma hələ xətti var.
>> Amma burada, biz nöqtəsinə geri gəlmək olan asimptotik notation və
nəzəri doğrudur.
Lakin real dünyada, əgər mən iddia mənim proqram 26 dəfə bir şey edə bilərsiniz
olan proqram sizin, çox daha sürətli istifadə tercih edir?
Sizin və ya mina, hansı 26 dəfə sürətli?
Real, onun şəxs 26 dəfə daha sürətli, hətta nəzəri cəhətdən əgər
bizim alqoritmlər eyni çalışır vaxt çalışan asimptotik.
>> Mənə bir fərqli təklif edək cəmi həlli.
Və bu fikrinizi əsəcək deyilsə, biz data strukturların bitti.
Beləliklə, bu bir trie deyil -
bir axmaq adı cür.
Bu söz alımları gəlir və çünki trie, t-r-i-e, yazıldığına
Əlbəttə axtarış trie kimi səslənir.
Amma bu tarixi sözü trie edir.
>> Belə bir trie, həqiqətən ağac bir növ edir və bu da ki, söz bir oyun var.
Və çox görmək bilməz, baxmayaraq ki, Bu vizual ilə bir trie bir
ağac ilə bir ailə ağac kimi, strukturlaşdırılmış üst və çox bir əcdad
nəvəsi və böyük nəvəsi kimi alt yaradır.
Amma trie hər node bir sıra edir.
Və bir sıra var - və Haydi bir an oversimplify - Bu bir
dizi, bu halda, ölçüsü 26, harada hər node yenidən ölçüsü bir sıra edir
26 olduğu ildə zeroth element array A təmsil və son
hər belə element array Z. təmsil
>> Buna görə, sonra təklif Bu data bir trie kimi tanınan quruluşu, ola bilər
sözləri saxlamaq üçün də istifadə olunur.
Biz saxlamaq necə bir an əvvəl gördüm sözlər, və ya bu halda adlar və biz
, biz nömrələri saxlaya bilərsiniz necə daha əvvəl gördüm ancaq adları və ya strings diqqət əgər
Burada maraqlı nə görürsünüz.
Mən ad Maxwell olduğunu iddia Bu data strukturu daxilində.
Harada Maxwell görürsünüz?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Sol.
Belə Bu data maraqlı nə var strukturu deyil, mağaza daha
string M-A-X-W-E-L-L backslash sıfır, bütün contiguously, yerine nə
izləyir.
Bu data strukturu kimi bir trie varsa, olan qovşaqlarının hər birinin yenidən bir sıra edir
və Maxwell saxlamaq istəyirəm ki, siz ilk index və o qədər kök-nin sözlə,
, topmost node danışmaq sağ, belə yer M, at
təxminən ortasına.
Və oradan, bir edin bir uşaq qovşağına pointer, belə danışmaq.
Belə ki, ailə ağacının mənada, Siz aşağı bunu edin.
Və başqa bir node sizə rəhbərlik olan orada sol haqqında
yalnız bir sıra.
>> Və sonra, Maksvell saxlamaq istəyirsinizsə, Əgər təmsil göstərici tapmaq
A, burada bu biridir.
Sonra növbəti node gedin.
Və xəbərdarlıq - bu nə şəkil Agentliyi bir az aldatma -
Bu node kiçik super baxmaq.
Amma bu hüququ Y və Z. edir Bu, yalnız müəllif kesilir etmişdir oldu
şəkil ki, həqiqətən, şeyi görürük.
Əks halda bu şəkil natarazcasına geniş olardı.
Sonra yeri X daxil Belə ki, indi indeksi, Sonra sonra W, sonra E, L, L. var
bu marağı?
>> Yaxşı, biz yeni bu cür kullanıyorsanız bir simli saxlamaq üçün necə götürmək
data structure, hələ lazımdır mahiyyətcə məlumatlara off yoxlamaq
Bir sözlə, burada bitir quruluşu.
Başqa sözlə, bu qovşaqlarının hər birtəhər unutmayın ki, biz
həqiqətən sonra bu göstəricilər bütün və bir az tərk edir
Bu burada altındakı çörək qırıntı M-A-X-W-E-L-L göstərir strukturu
həqiqətən Bu data quruluşu.
>> Beləliklə, biz aşağıdakı kimi bunu bilər.
Biz yalnız şəkil qovşaqlarının hər gördüm bir, ölçüsü 27 bir sıra var.
P altı müəyyən çünki, indi 27 var Biz, həqiqətən, bir Apostrof verəcəyik
biz O'Reilly kimi adları ola bilər apostrophes və s.
Amma eyni fikir.
Ki, həmin elementlərin hər biri bir struct üçün array bal
node, belə ki, yalnız bir node.
Belə ki, bu çox xatırladan Bizim bağlı siyahısı.
>> Və sonra bir Boolean var, I will söz zəng olan yalnız olacaq
Bir sözlə, bu bitir doğru əgər ağac ilə node.
Bu səmərəli az təmsil üçbucaq biz bir an əvvəl gördüm.
Bir söz ki, node başa çatır Belə ki, əgər ağac, söz sahəsində, doğru olacaq
olan konseptual off yoxlanılması, və ya biz bəli var, bu üçbucaq rəsm edirik
burada söz.
>> Belə ki, bu trie edir.
İndi isə sual nə onun çalışan?
O n böyük o?
Başqa bir şey mi?
Yaxşı, siz Bu data adları N əgər strukturu, Maxwell yalnız biri olan
onlara da çalışan zaman nə daxil və ya Maxwell tapmaq?
Çalışan zaman nədir Maxwell olunsa?
N başqa adlar varsa artıq cədvəldə?
Bəli?
>> TƏLƏBƏ: [işitilemez].
>> HOPARLÖR 1: Bəli, uzunluğu var adı, sağ?
M-a-x-w-e-l-l Belə ki, bu kimi hiss Belə ki, alqoritm yeddi böyük Ey edir.
İndi, əlbəttə, adı uzunluğu dəyişir.
Bəlkə bir qısa adı var.
Bəlkə uzun adı var.
Bəs burada əsas var ki, bir sabit bir sayı var.
Və bəlkə, həqiqətən daimi deyil Allah, real, əgər bir
lüğət, bəzi limit yəqin ki, yoxdur bir hərflərin sayı
məxsusi ölkədə şəxsin adı.
>> Və biz güman edə bilər dəyər və daimidir.
Mən bunu nə bilmirəm.
Yəqin ki, daha böyük var biz bunu hesab edirəm.
Bəzi künc həmişə var, çünki dəli uzun adı ilə halda.
Belə ki, İT k deyirik, lakin o, hələ də var daimi ehtimalla, hər çünki
ən azı bir dünyada, adını ölkənin ki, uzunluğu və ya
qısa, buna görə də daimi deyil.
Amma biz bildirib etdiyiniz zaman böyük bir şey deyil Sabit dəyər O, nə ki,
həqiqətən ekvivalent?
Bu həqiqətən eyni şey daimi zaman deyib.
>> İndi aldadıcı cür haklýsýn?
Biz bəzi nəzəriyyəsi yararlanarak cür istəyirik burada yaxşı, k üçün deyil ki,
həqiqətən, yalnız bir sifariş və bu daimi vaxt var.
Amma bu, həqiqətən.
Burada əsas fikir Çünki biz bu artıq adları N əgər
data structure, biz insert Maxwell, bu bizə edir zaman məbləği
təsirə məruz qalan bütün at Maxwell daxil necə bir çox digər insanlar tərəfindən
veri strukturu var?
Olmaq görünmür.
Mən bu bir milyard elementləri olsaydı sonra trie və Maxwell olunur daxil
o bütün təsir?
No
Və bu gün göstərilən hər hansı fərqli var biz, bu günə qədər gördüm strukturları
Sizin alqoritm çalışan zaman nə qədər tamamilə müstəqil
heyəti və ya artıq deyil ki, data strukturunda.
>> Bu imkan və belə artıq deyil p set altı imkan verəcək
yenə öz həyata cəlb 150,000 oxu İmla kontrolü,
sözlər, nə yaxşı ki, saxlamaq üçün mütləq aydın deyil.
Və mən tapmaq talib etdik baxmayaraq müqəddəs grail, mən bunu
bir trie olduğunu iddia.
Əslində, bir hash table çox yaxşı bilər daha səmərəli olduğunu sübut edir.
Ancaq o yalnız var -
ki, yalnız dizayn qərarlardan biri Bunu etmək olacaq.
>> Lakin yekun bir-qoy 50 və ya belə saniyə yalan nə bir peek almaq
irəli həftə növbəti və biz keçid kənarda Bu skript satırı
şeyi web dünya C proqramları əgər əsaslanır və PHP kimi dil və
JavaScript və internet özü, Siz etdiyiniz HTTP kimi protokolları,
il göydən hər əksəriyyəti və çap
gün, bəlkə, və ya görüldü.
Və biz soymaq geri başlarsınız nə qat internet edir.
Və kodu nedir ki, yatan bugünkü alətlər.
Bu teaser belə 50 saniyə.
Mən sizə Çəkisi Warriors verir.
>> [Video playback]
>> O, bir mesaj gəldi.
Protokol bütün öz ilə.
O, qəddar firewall dünya gəldi əhəmiyyət verməz yönlendirici və təhlükələr uzaq
ölümdən betər.
O, sürətli.
O, güclü var.
O Tcpip var.
O ünvanı var.
Net döyüşçülər.
>> [END video playback]
>> HOPARLÖR 1: Bu necə internet Gələn həftə kimi işləməlidir.