>> [MUSIC PLAYING]
>> ANDI PENG: hissəsinin həftə 6 xoş gəlmisiniz.
Biz standart yoldan Çərşənbə axşamı bölmə vaxt
Bu sevimli bazar günü səhər günorta.
Hər kəs üçün təşəkkür edirik ki, bu gün, lakin ciddi mənə qoşulub
alqış dəyirmi.
>> Bu, olduqca böyük səy var.
Mən demək olar ki, hətta etməyib vaxt up, lakin OK idi.
Belə ki, Mən sizə ki, bütün bilirik yalnız viktorina etdik.
İlk növbədə, xoş gəlmisiniz ki, flip yan.
>> İkincisi, biz bu barədə danışacağıq.
Biz viktorina haqqında danışmaq lazımdır.
Biz haqqında danışmaq lazımdır Siz sinif edirik.
Siz gözəl olacaq.
Mən sizin viktorina üçün Burada sonunda,
Belə ki, uşaqlar almaq istəyirsinizsə a, ona tamamilə gözəl baxmaq.
>> Belə ki, tez biz başlamaq əvvəl aşağıdakı kimi bu gün üçün gündəmdə.
Gördüyünüz kimi, biz istəyirik əsasən sürətli atəş
data strukturları bütün dəstə vasitəsilə həqiqətən, həqiqətən, həqiqətən tez.
Kimi Belə ki, olmayacaq super interaktiv gün.
Bu, yalnız mənə cür qışqırır olacaq şeyi, və mən sizə çaşdırmaq əgər,
Mən çox sürətli gedirəm əgər Mənə bildirin.
Onlar yalnız müxtəlif data istəyirik strukturları və bir hissəsi kimi
bu sizin pset Qarşıdan gələn həftə, siz lazımdır
onlardan biri həyata keçirilməsi üçün tələb oluna, bəlkə onlara iki Odur iki
Sizin pset.
OK, belə ki, mən yalnız gedirəm Bəzi elanlar ilə başlayın.
Biz çıxarıcı borular və daha çox sıralarında artıq getmək lazımdır biz viktorina əvvəl nə çox dərinliyi.
Biz artıq getmək bağlı olacaq yenidən, bir daha sadalamaq
daha dərin daha nə biz viktorina əvvəl idi.
Və sonra biz hash haqqında danışmaq lazımdır masalar, ağac və çalışır olan
bütün pset üçün olduqca zəruridir.
Və sonra biz bir artıq getmək lazımdır pset5 üçün faydalı ipuçları.
>> OK, belə ki, viktorina 0.
orta 58% olmuşdur.
Bu, çox aşağı idi, belə ki, uşaqlar bütün olaraq çox, çox yaxşı idi
ki,.
>> Siz əgər olduqca çox, thumb qayda orta bir standart sapma ərzində
biz bir az istəyirik, xüsusilə, çünki rahat ikibölməli, siz tamamilə gözəl istəyirik.
Siz yolda istəyirik.
Həyat yaxşıdır.
>> Mən hesab edirəm ki, scary bilirik Mən bu viktorina 40% kimi var.
Bu sinif uğursuz gedirəm.
Mən sizə söz verirəm, siz deyilik sinif uğursuz olacaq.
Siz tamamilə gözəl istəyirik.
>> Artıq var olan sizin üçün orta, təsirli, təsirli,
kimi ciddi yaxşı.
Mən onlara var.
Onları almaq gəlmək üçün çekinmeyin bölümün sonunda.
Əgər varsa Mənə bildirin məsələlər, onlara suallar.
Biz hesab əlavə edin yanlış, bizə bildirin.
>> OK, pset5 ki, bu, həqiqətən deyil mənada Yale üçün qəribə həftə
Bizim pset görə ki, O cümlədən günorta saatlarında Çərşənbə
gec gün, belə ki, həqiqətən var günorta saatlarında çərşənbə axşamı nəzəri görə.
Yəqin ki, heç bir başa günorta saatlarında Çərşənbə axşamı.
Ki, tamamilə gözəl var.
Biz ofis saat olacaq gecə eləcə də bazar ertəsi gecə.
Və bölmələr bütün bu həftə olacaq həqiqətən seminarlar çevrilmişdir,
belə pop çekinmeyin Siz istədiyiniz hər hansı bir ikibölməli,
və onlar növ mini-pset olacaq ki, yardım üçün seminarlar.
Belə ki, kimi, bu, yalnız bölmə biz material tədris edirik.
Bütün digər bölmələr diqqət ediləcək yalnız pset üçün kömək.
Evet?
>> Auditoriya: Harada ofis saat var?
>> ANDI PENG: Office saat , oh yaxşı sual tonight--.
Mən hesab edirəm ki ofis saat gecə Teal ya Commons var.
Siz online CS50 yoxlamaq əgər və siz ofis saat getmək
cədvəli olmalıdır ki, Onların hamısı deyir.
>> Mən bu axşam ya bilirəm və ya sabah Qəhvəyi edir
və biz ola bilər edirəm digər gecə commons.
Əmin deyiləm.
Yaxşı sualdır.
CS50 haqqında yoxlayın.
>> Bağlı Cool, hər hansı bir sualınız üç gün kimi növbəti cədvəli?
Davud kimi uşaqlar söz bu təpənin üst etdi.
Siz uşaqlar demək olar ki, var.
Yalnız üç gün daha.
Orada almaq, sonra biz bütün aşağı gəlmək lazımdır.
Biz gözəl CS-free fasilə lazımdır.
Biz geri gəlmək lazımdır.
Biz web daxil dalış lazımdır proqramlaşdırma və inkişaf,
çox əyləncə var şeyi müqayisə digər psets bəzi.
Və soyuq olacaq və biz əyləncə çox olacaq.
Biz daha çox konfet lazımdır.
Konfet üçün üzr istəyirik.
Mən konfet unuttum.
Bu kobud səhər idi.
Belə ki, uşaqlar, demək olar ki, var və Mən sizə uşaqlar fəxr edirəm.
>> OK, belə ki, çıxarıcı borular.
Kim Jack barədə suala sevilən və viktorina onun geyim?
Heç kim?
OK, ki, gözəl.
>> Belə ki, mahiyyətcə bilərsiniz kimi şəkil Jack, burada bu oğlan,
geyim almaq üçün sevir yığını üst həyata,
və o, üzərinə geri qoyur o sonra yığını həyata.
Bu şəkildə Belə ki, o, heç vaxt əldə olunması görünür
alt Onun geyim yığın.
Belə ki, bu cür təsvir edir Əsas data structure
bir yığın həyata necə.
>> Əsasən, bir hesab obyektlərin hər hansı bir yığını kimi yığın
Siz üst üzərində şeyi qoymaq və harada sonra üst onları pop.
Belə ki LIFO biz kimi kisaltmasidir son, ilk use-- üçün.
Və belə üst davam yığını çıxır ilk biridir.
Və belə ki, iki şərtləri biz birləşmək istəyirəm
ki, push və pop adlanır.
Zaman üzərinə bir şey təkan dəstə, və geri onu açılır.
>> Və mən bu cür tapmaq sizin üçün abstrakt anlayış
Kim kimi görmək istəyirəm Bu faktiki həyata keçirilməsi
real dünyada.
Necə bir çox inşa yazıblar bəlkə bir saat kimi, səbəbiylə əvvəl
və təsadüfən bir böyük silinmiş təsadüfən kimi onun yığın?
Və sonra nə nəzarət yoxdur biz onu geri qoymaq üçün istifadə?
Control-Z, yeah?
Control-Z, belə ki, dəfə məbləği Control-Z mənim həyat xilas ki,
, hər zaman mənim ass xilas ki, bir yığını vasitəsilə həyata edir.
>> Əsasən bütün məlumat ki, sizin Word sənəd var
Bu basdı və iradəsi ilə atdı olur.
Və belə mahiyyətcə zaman sizə bir şey silmək, siz geri açılır.
Və sonra geri ehtiyac varsa, Control-C nə olan basın.
Və belə real dünya funksiyası qədər sadə data strukturu
Sizin gündəlik həyat kömək edə bilər.
>> Belə ki, bir struct yoldur ki, biz, həqiqətən, bir yığın yaratmaq.
Biz sonra struct müəyyən yazın, biz altındakı yığın zəng.
Və yığını çərçivəsində, biz iki parametrləri var
biz mahiyyətcə manipulyasiya edə bilər ki, belə ki, biz char star strings gücü var.
>> Bu edir Bütün bir sıra yaradır
biz istədiyiniz nə bilərsiniz ki, olan biz onun potensialının müəyyən edə bilər.
Capacity yalnız max məbləği mı maddələr, biz bu array daxil qoya bilər.
int ölçüsü saxlayır counter neçə maddələr track hazırda
yığını.
Belə ki, sonra biz, A, takip edə bilərsiniz faktiki yığını necə böyük,
və, B, necə yığını çox biz istəmirik, çünki biz dolu
Bizim gücü nə üzərində daşqın.
>> Məsələn, bu sevimli So sual viktorina idi.
Əsasən necə təkan yoxdur bir yığın üst üzərində.
Pretty sadə.
Siz baxmaq əgər, bu vasitəsilə gəzmək lazımdır.
[Işitilemez] size-- əgər zaman unutmayın,
hər hansı daxil olmaq istəyirəm bir struct ərzində parametri,
Siz struct.parameter adı yoxdur.
>> Bu halda, s yığını adı.
Biz ölçüsü daxil olmaq üçün istədiyiniz bu, belə ki, biz s.size yoxdur.
Ölçüsü deyil kimi uzun gücü və ya uzun bərabər
Bu gücü daha az kimi, ya burada işləmək olardı.
>> Əgər daxili daxil istəyirəm Sizin yığını, s.strings ki,
və bu yeni sayı qoymaq olacaq Orada daxil etmək istəyirəm ki,.
Yalnız istəyirik ki, deyirlər yığını üzərinə int n daxil,
biz s.strings edə bilər Mötərizədə, s.size n bərabərdir.
Ölçüsü harada Çünki biz Hal-hazırda yığını var
biz təkan olacaq əgər Bu, biz yalnız daxil olmaq
ölçüsü yerdə, yığını cari dolğunluq,
və biz bunu üzərinə int n basın.
Və sonra biz əmin etmək istəyirəm biz də n ölçüsü incrementing edirik
biz belə biz takip edə bilərsiniz yığını əlavə bir şey əlavə edib.
İndi biz daha ölçüsü var.
Burada mənada edir hamı necə məntiqi işləyir?
Bu cür gecikmədi.
Auditoriya: Siz artıq getmək bilər s.stringss.strings [s.size] yenidən?
ANDI PENG: Əlbəttə, belə nə bizə Hal-hazırda s.size?
Auditoriya: Bu cari ölçüsü var.
ANDI PENG: Məhz, belə ki, Bizim ölçüsü cari index,
və biz yeni tam qoymaq istəyirəm biz s.size daxil etmək istəyirəm ki,.
Ki, hissi edirmi?
S.strings, çünki bütün ki, edir serialın adı.
Bu bütün daxil deyil Bizim struct ərzində array,
və biz istəyirsinizsə ki, index daxil n yerləşdirmək,
biz yalnız gedə bilərsiniz istifadə Mötərizədə s.size.
Cool.
>> Bütün hüquqlar, pop, mən onu pseudocode Siz uşaqlar, lakin oxşar anlayış üçün.
Ki, hissi edirmi?
Ölçüsü böyük olduqda sonra sıfır, daha
Əgər bir şey etmək istəyirəm ki, bilirik həyata ölçüsü deyil, çünki
daha çox sıfır, sonra yığını heç bir şey yoxdur.
>> Belə ki, yalnız icra etmək istəyirəm bu kodu, yalnız edə bilərsiniz
pop bir şey varsa açılır.
Ölçüsü böyükdür Belə ki 0 daha çox, biz minus ölçüsü.
Biz ölçüsü azalma və sonra qayıtmaq çünki daxilində nə var
yaratma, istəyirik saxlanılır nə giriş
yığını üst index.
Hər şey mənada?
Mən əgər uşaqlar, bu yazmaq Siz uşaqlar yazmaq üçün edə bilər?
OK, uşaqlar ilə ətrafında oynaya bilər.
Heç bir narahatlıq onu almaq yoxsa.
Biz kod vaxt yoxdur Bu bu gün biz, çünki
bu strukturların bir çox var keçmək, lakin mahiyyətcə üçün
pseudocode, çox, çox oxşar təkan.
Yalnız məntiq boyunca edin.
Bütün daxil əmin olun doğru struct xüsusiyyətləri.
Evet?
>> Auditoriya: bu slaydlar və bu bütün şey bu gün-ish ola bilərmi?
ANDI PENG: Həmişə, yep.
Mən qoymaq üçün cəhd gedirəm Bu qədər sonra bir saat kimi.
Mən David e-poçt lazımdır, David üçün çalışacağıq Bundan sonra bir saat kimi onu qoymaq.
>> OK, belə ki, sonra biz bu digər hərəkət sevimli data structure bir sıra çağırıb.
Uşaqlar burada Gördüyünüz kimi, bir queue, aramızda Britaniya üçün,
bu bir xəttidir.
Belə ki, əksinə nə Bir yığın hesab edirəm
bir sıra dəqiq nə məntiqi olduğunu düşünürəm.
Bu FIFO qaydaları ilə təşkil edir Hansı İlk olaraq, First Out edir.
Siz ilk edirsinizsə line bir sen
birinci ki, xətti çıxır.
>> Beləliklə, biz bu zəng etmək istəyirəm nə dequeueing və enqueueing olunur.
Biz bir şey əlavə etmək istəyirsinizsə Bizim növbə, biz enqueue.
Biz istəyirsinizsə dequeue, və ya etmək bir şey üz, biz dequeue.
>> Biz növ istəyirik Belə ki, eyni mənada sabit ölçüsü elementlərinin yaradılması ki, biz
müəyyən bilərsiniz şeyi, lakin biz də edə bilərsiniz
biz yerləşdirilməsi olduğunuz dəyişiklik onların içərisində parametrləri
hansı növü əsasında funksionallıq istəyirik.
Çıxarıcı borular Belə ki, biz son istədi bir N birinci olmaq.
Queue biz ilk şey istəyirik həyata ilk şey olmalıdır.
>> Struct tipi So Gördüyünüz kimi, müəyyən,
bir az fərqli yığını idi nə
yalnız biz saxlamaq üçün var, çünki ölçüsü hazırda harada track,
biz də baş takip etmək istəyirəm eləcə də olduğu kimi, biz hazırda.
Beləliklə, mən daha asan hesab edirəm Mən bu qədər çəkmək əgər.
Belə ki, biz bir sıra var təsəvvür edək, belə başı sağ burada deyək.
line rəhbəri edək yalnız orada hazırda demək
və biz daxil etmək istəyirəm növbə daxil bir şey.
Mən mahiyyətcə ölçüsü zəng etmək üçün gedirəm quyruq eyni şey,
Sizin queue yerdə sonu.
Yalnız ölçüsü sağ burada deyirlər.
>> Belə ki, necə bir feasibly yoxdur bir sıra bir şey daxil?
Nə index biz yerləşdirmək istəyirəm biz daxil etmək istəyirəm.
Bu başlanğıcı Əgər sizin növbə və bu onun sonu
və ya onun ölçüsü, biz nə növbəti obyekt əlavə etmək istəyirsiniz?
>> Auditoriya: [işitilemez]
ANDI PENG: Məhz, əlavə etmək istədiyiniz asılı olaraq onu yazıblar.
Ya bu boş və ya boş.
Beləliklə, siz yəqin ki, əlavə etmək istəyirəm Çünki burada size is-- əgər
Bunların hamısı tam əgər, istədiyiniz sağ, burada əlavə etmək üçün?
>> Və belə ki, var, çox isə sadə deyil, kifayət qədər həmişə doğru
əsas fərq, çünki bir sıra və bir yığın arasında
ki, növbə edə bilərsiniz deyil həqiqətən manipulyasiya etmək
ki, baş dəyişikliklər Siz istədiyiniz asılı olaraq
Sizin replika başlanğıcı başlamaq üçün.
Və nəticə olaraq, sizin quyruq də dəyişiklik gedir.
Və belə bir nəzər İndi bu kodu.
Sizlərin də istəndi kimi enqueue, viktorina yazmaq.
Bəlkə biz niyə vasitəsilə danışmaq lazımdır cavab idi nə idi.
>> Mən, bir bu xətt uyğun bilmədi kod lakin mahiyyətcə bu parça
bir xətt olmalıdır.
30 saniyə kimi sərf edirlər.
Bir göz atın və nə görmək bu deyil bir yoldur.
>> Çox, çox oxşar struct, çox, çox əvvəlki kimi oxşar strukturu
bəlkə başqa stack kodu bir xətt.
Və kodu bir line ki, funksionallığı müəyyən edir.
Və həqiqətən fərqləndirir bir yığın bir sıra.
>> Hər kəs bir zərbə almaq istəyirəm Siz var niyə izah
burada bu mürəkkəb şey var?
Biz geri görmək bizim gözəl dost modulus.
Sizlərin tezliklə gələcək kimi proqramlaşdırma tanımaq,
demək olar ki, istədiyiniz zaman bir şey lazımdır bir şey ətrafında kesmek,
modulus bunu yol olacaq.
Belə ki, bilmədən, hər kəs istəyir kodu ki, xətt izah cəhd?
Bəli, bütün cavablar var qəbul və xoş.
Auditoriya: Siz mənə söhbət edirsiniz?
ANDI PENG: Bəli.
Auditoriya: Oh, heç bir sorry.
ANDI PENG: OK, belə ki, edək bu kod vasitəsilə gəzmək.
Belə ki, zaman çalışdığınız bir sıra üzərində bir şey əlavə,
baş olur ki, sevimli halda burada olmaq, bizim üçün çox asandır
yalnız sonuna qədər getmək doğru bir şey, daxil?
Amma bir sıra bütün nöqtəsidir edə həqiqətən dinamik rəhbəri
harada asılı olaraq dəyişə biz Bizim q başlanğıc olmaq istəyirəm,
və, quyruq kimi də dəyişiklik gedir.
>> Və bu idi ki, təsəvvür növbə deyil, bu quyruğu meydana gəldi.
Başı sağ burada deyirlər.
Bizim queue bu kimi baxdı deyirlər.
Biz burada keçmək istəyirdi xəttinin başlanğıcı edir
Biz baş keçdikdə deyək Bu şəkildə və ölçüləri.
>> İndi biz bir şey əlavə etmək istəyirəm Bu queue, ancaq uşaqlar Gördüyünüz kimi,
yalnız kimi sadə deyil ölçüsü sonra nə əlavə
sonra biz tökülmək, çünki bizim faktiki serialın həddi.
Biz, həqiqətən, əlavə etmək istədiyiniz burada.
Ki, bir sıra gözəllik var ki, vizual, bizim üçün
line bu kimi gedir kimi, görünür, lakin bir data strukturu saxlanılır zaman,
onlar dövrü kimi verir.
Bu cür ətrafında wraps ön eyni şəkildə etmək
xətti də kesmek olar ki, ətrafında harada asılı olaraq
olmaq Xəttin əvvəlində istəyirik.
Və belə ki, biz bir götürsək burada aşağı baxmaq, edək
bir yaratmaq istəyirdi demək funksiyası enqueue çağırıb.
Biz bu q daxil int n əlavə etmək istədi.
Q.size biz data ki, zəng edəcəyik Q əgər Bizim queue.size deyil, əgər strukturu
gücü və ya bərabər Bu, gücü az deyil
q.strings bizim q ərzində array edir.
Biz müəyyən olacaq ki q.heads bərabər,
olan burada, üstəgəl q.size gücü ilə modulus olan
Buralarda bizə geri kesmek.
>> Bu misal, index belə başının sağ, 1?
ölçüsü index 0, 1, 2, 3, 4.
Belə ki, biz 1 plus 4 modulus edə bilərsiniz 5 bizim gücü.
Nə bizə verir?
Index nədir bu çıxır?
>> Auditoriya: 0.
>> ANDI PENG: 0, hansı burada olmaq olur,
və biz etmək istəyirəm burada daxil daxil etmək üçün.
Və bu tənlik burada cür yalnız hər hansı bir nömrələri ilə işləyir
harada asılı olaraq baş və ölçüsü var.
Siz nə o bilirsinizsə hər şeyi bilirsiniz, var
dəqiq daxil etmək istədiyiniz nə növbə sonra.
Ki, hamıya mənada edirmi?
>> Mən beyin cür bilirik teaser, xüsusilə, çünki bu
Sizin viktorina sonra gəldi.
Lakin ümid hər kəs İndi başa düşmək olar
niyə bu həll və ya bu funksiyası bu yoldur.
Hər kəs bir az aydın?
OLDU.
>> Və indi, əgər bu dequeue istədi
bizim baş dəyişkən olacaq harada biz dequeue olsaydı, çünki
biz q sonunda off etmirlər.
Biz sağ, baş çıxarmaq istəyirsiniz?
Belə ki, nəticədə baş dəyişdirmək üçün gedir, Siz enqueue zaman niyə və ki,
Siz takip var harada baş və ölçüsü
daxil edə olmaq üçün düzgün mövqe.
>> Və belə ki, dequeue zaman, Mən də onu pseudocode.
Əgər siz çekinmeyin bu kodlaşdırma cəhd.
Siz sağ, baş hərəkət etmək istəyirsiniz?
Mən dequeue istəyirdi, mən baş üzərində hərəkət olardı.
Bu baş olardı.
>> Və cari ölçüsü olardı çıxmaq, çünki biz artıq
array dörd elementləri var.
Biz yalnız üç var və sonra biz istəyirik daxilində saxlanılır edilmişdir nə qayıtmaq
baş, biz bu almaq istəyirəm, çünki yığını çox oxşar dəyəri həyata.
Yalnız siz qəbul etdiyiniz fərqli bir yerdən,
və sizin pointer redesign var nəticəsində fərqli bir yerə.
Məntiqi, hər kəs edin?
Great.
>> OK, belə ki, biz bir az danışmaq olacaq bağlı siyahıları haqqında daha ətraflı
onlar çox, çox qiymətli olacaq, çünki Bu həftə ərzində sizin üçün
psets.
Əlaqəli siyahıları, kimi uşaqlar onlar bütün var, yadda bilər
müəyyən qovşaqlarının var qovşaqlarının var bir dəyəri və bir göstərici həm də dəyərləri
birlikdə bağlıdır bu göstəricilər tərəfindən.
Necə və belə struct Biz burada bir node biz yaratmaq
olan int n var nə bir mağaza və ya simli n dəyəri
və ya istədiyiniz hər hansı char star n, zəng.
Göstərici struct node ulduz, Hər bir node var etmək istəyirəm ki,
ki, olacaq növbəti qarşı pointer point.
Siz baş lazımdır bir bağlı siyahı
qalan qeyd etmək niyyətindədir s və s dəyərlər
Siz nəhayət sonuna çatmaq qədər.
Və bu son node yalnız bir göstərici yoxdur gedir.
Bu qeyd etmək olacaq null, və zaman var
siz hit etdik bilirik Sizin bağlı siyahı sonunda
zaman son göstərici bir şey işarə deyil.
>> Beləliklə, biz daha çox bir az getmək olacaq bağlı dərinliyi necə bir mümkün olardı
bir bağlı siyahısı axtarış.
Bəzi nə saxla bağlı siyahıları çatışmazlıqlar
Axtarışa bağlı bir sıra ayələri.
Bir sıra siz ikili axtarış, lakin niyə bir bağlı siyahı ki, edə bilməz?
>> Auditoriya: onlar bütün bağlı olduğunuz Çünki, lakin siz kifayət qədər harada bilmirəm
[Işitilemez].
>> ANDI PENG: Bəli, məhz belə xatırlayıram ki, bir sıra parıltı
biz idi ki idi əməli yaddaş harada
Mən index dəyər istəyirdi altı, mən yalnız index altı deyə bilər
mənə dəyər verir.
Diziler ayrılır, çünki ki, yaddaş bitişik məkanında
Bir yerdə, halbuki bağlı siyahıları cür
olan təsadüfi ətrafında bütün interspersed və yalnız yol tapa bilərsiniz
sizə deyir bir göstərici vasitəsilə ki, növbəti node olduğu ünvanı.
>> Və belə bir nəticə kimi, yeganə yolu bir bağlı siyahısını axtarış
xətti axtarış edir.
Mən dəqiq bilmirəm, çünki Bağlı siyahısında 12-ci dəyəri,
Mən tam axır var ki bağlı siyahı bir
ilk node rəhbəri bir-, ikinci node, üçüncü node,
Mən nəhayət almaq qədər bütün yol aşağı I arıyorum ki node olduğu üçün.
Və bu mənada, axtarış bir bağlı siyahı həmişə n edir.
O, həmişə n var.
Bu xətti vaxt həmişə var.
>> Və belə code hansı bu həyata, və bu
Sizin ildən uşaqlar üçün bir az yeni uşaqlar həqiqətən haqqında ya heç söhbət yoxdur
necə görüldü göstəricilərinə göstəricilər vasitəsilə axtarış,
belə ki, biz vasitəsilə gəzmək lazımdır bu, çox yavaş-yavaş.
Belə ki bool axtarış, sağ, Biz istəyirik təsəvvür edək
adlı funksiyası yaratmaq doğru qaytarır Axtarış
Siz bağlı daxili bir dəyər aşkar etdikdə siyahısı, və başqa yalan qaytarır.
Node star siyahısı Hal-hazırda yalnız pointer
Sizin bağlı siyahıda ilk maddə.
int n sen dəyəri var ki, siyahıda üçün axtarış.
>> Belə ki, node ulduz pointer siyahısı bərabərdir.
Yəni biz qəbulu edirik deməkdir və bir pointer yaratmaq
siyahı daxilində ilk node.
Mənimlə hər kəs?
Biz getmək idi əgər, belə ki, Geri burada, mən olardı
göstərir ki, bir göstərici başlatılmış baş nə ki, siyahısı.
>> Və sonra, burada bir dəfə pointer bərabər null deyil isə,
belə ki, biz olan loop deyil traversing sonra olacaq
nə çünki bizim siyahısı istirahət pointer null bərabərdir ne olur?
Biz yaxşıdır bilirik ki,
>> Auditoriya: [işitilemez]
>> ANDI PENG: Məhz, belə ki, biz bilirik ki, Biz sağ siyahısı sonunda əldə etdiyiniz?
Burada geri getmək əgər, hər bir node başqa node işarə etmək lazımdır
və s və s Siz nəhayət hit qədər
Sizin bağlı siyahı quyruq, olan bir göstərici var ki, yalnız
heç bir daha hər hansı digər qeyd etmir.
Və belə ki, əsasən bilirik ki, Sizin siyahısı hələ orada deyil
pointer bərabər deyil qədər null null bərabərdir dəfə, çünki,
Siz heç bir daha stuff var ki, bilirik.
>> Belə ki, biz istəyirik ki, loop deyil faktiki axtarış gedir.
Və göstərici görmək əgər orada arrow funksiyası belə?
Belə ki, pointer bal əgər n, əgər n bərabərdir N pointer,
o deməkdir ki, əgər ki, sen pointer
Hər sonunda üçün axtarış node dəyəri həqiqətən bərabərdir
sonra, aradığınız Əgər doğru qayıtmaq istəyirəm.
Belə ki, əsasən, bir node da əgər ki, , aradığınız dəyəri var
Siz olduğunuz bilirik ki, uğurla axtarış edə.
>> Əks halda, qurmaq istəyirəm növbəti node üçün göstərici.
Ki, burada xətt nə edir.
Pointer növbəti göstərici bərabərdir.
Ki, iş necə görmək hər kəs?
>> Və mahiyyətcə siz olacaq yalnız siyahı tam axır
Sizin göstərici hər zaman qədər sıfırlama nəticədə siyahısı sonunda edib.
Və heç bir var bilirik ki, daha qovşaqlarının, vasitəsilə axtarış
və sonra yalan ola bilər Bilirsiniz, çünki ki, yaxşı, oh,
Mən axtarış edə olduğunuz əgər siyahısı tam vasitəsilə.
Bu misalda, mən istəyirdi 10 dəyər axtarmaq üçün,
Mən baş başlamaq və Mən bütün yol aşağı axtarış
və mən nəhayət, bu var olan null göstərir ki, bir göstərici,
Mən deyil, crap, 10 tahmin bilirik ki, Bu siyahı Mən bunu tapa bilmədi, çünki.
Mən siyahısı sonunda edirəm.
Və bu halda Bildiyiniz Mən yalan qayıtmaq üçün gedirəm.
>> Ki, bir az islatmaq bildirin.
Bu olduqca olacaq Sizin pset üçün əhəmiyyətli.
Bunun məntiqi bəlkə də, çox sadədir syntactically yalnız həyata keçirir.
Siz uşaqlar etmək istəyirəm Siz anlamaq əmin olun.
Cool.
>> OK, belə ki, biz necə olacaq sağ, qovşaqlarının daxil,
siyahısına daxil çünki xatırlayıram nə faydaları hansılardır
bir bağlı siyahı qarşı olan saxlanması baxımından bir sıra?
>> Auditoriya: Bu dinamik, belə ki, asan to--
>> ANDI PENG: Məhz, belə ki, dinamik hansı
Bu genişləndirilməsi və shrink o deməkdir ki, istifadəçi ehtiyaclarından asılı olaraq.
Belə ki, bu mənada, biz lazım deyil lazımsız yaddaş sərf çünki
Mən istəyirəm necə çox dəyərləri bilmirsinizsə mağaza, bu, mənim üçün mənada etmir
bir sıra çünki yaratmaq Mən 10 dəyərlər saxlamaq istəyirsinizsə,
Mən 1000 bir sıra, o yaratmaq boşa yaddaş bir çox ayrılmış.
Biz bir bağlı istifadə etmək istəyirəm Buna görə siyahısı dinamik etmək
dəyişdirmək və ya ölçüsü shrink.
>> Və belə ki, durub edir bir az daha mürəkkəbdir.
Biz təsadüfi elementləri daxil ola bilər-ci ildən biz bir sıra olardı yol.
Mən bir element əlavə etmək istəyirsinizsə, yeddinci indeksi daxil,
Mən yalnız onu əlavə edə bilərsiniz yeddinci indeksi daxil.
Bir bağlı siyahı, bu deyil olduqca kimi asanlıqla iş,
və biz daxil etmək istəyirdi bağlı siyahısında burada bir,
vizual görmək çox asandır.
Biz yalnız orada əlavə etmək istəyirəm sağ siyahının başında,
sağ baş sonra.
>> Amma biz var olan yol redesign göstəricilərinə bir az convoluted olunur
və ya, məntiqi, bu mənada edir, lakin Siz var ki, əmin etmək istəyirəm
tamamilə çünki Siz istədiyiniz son şey
bir göstərici redesign edir biz burada edirik yol.
Siz dereference 1 baş göstərici,
sonra qəflətən The bütün Sizin bağlı siyahı qalan
Siz, həqiqətən, çünki itirilmiş müvəqqəti bir şey yaratmışdır.
Ki, 2 işarə edir.
Əgər göstərici, redesign əgər Sizin siyahısına qalan tamamilə məğlub edir.
Belə ki, olmaq istəyirəm Burada çox, çox diqqətli
ilk təyin etmək Siz nə olan göstərici
yerdə daxil istəyirəm Istədiyiniz və sonra
Sizin siyahısına qalan dereference bilərsiniz.
>> Belə ki, bu yerdə üçün müraciət Siz daxil çalışırıq.
Siz daxil etmək istəyirsinizsə rəhbəri, burada cavab istəyirsinizsə,
Siz daxil etmək istəyirsinizsə, end, yaxşı, son mən
tahmin yalnız ki heç bir göstərici var, lakin siz
siz deyil ki, əmin etmək istəyirəm Sizin siyahısına qalan itirirlər.
Siz həmişə əmin etmək istəyirəm Yeni node işarə edir
nə qarşı siz daxil etmək istəyirəm,
və sonra siz zəncirləmə əlavə edə bilərsiniz.
Hər kəs aydın?
>> Bu olacaq real məsələlərdən biri.
Ən böyük məsələlərdən biri Siz pset olacaq
yaratmaq üçün cəhd olacaq ki, bir bağlı siyahısı və insert şeyi
lakin sonra yalnız itirmək Sizin bağlı siyahı istirahət.
Və kimi olacaq, mən Bu baş niyə bilmirəm?
Və onun vasitəsilə getmək üçün bir ağrı var və göstəricilər bütün axtarış.
>> Və mən bu pset sizi təmin, bu qovşaqlarının yazılı və rəsm
çox, çox faydalı olacaq.
Belə ki, tamamilə takip edə bilərsiniz bütün göstəricilərinə harada,
nə yanlış gedir bütün qovşaqlarının olduğu,
Siz daxil olmaq üçün nə etmək lazımdır və ya daxil və ya silmək və ya onlara hər hansı bir.
Ki, yaxşı hər kəs?
Cool.
>> Biz kodu baxmaq istəyirdi Belə ki?
Oh, mən bilmirəm, əgər biz belə ki, the-- OK görə bilərsiniz
üst bu bir funksiyası var Biz istəyirik adına insert
bağlı siyahısına daxil int n daxil etmək üçün.
Biz bu vasitəsilə gəzmək olacaq.
Bu kodu bir çox yeni sintaksis bir çox var.
Biz OK olacaq.
>> Üst zaman qədər belə biz bir şey yaratmaq istəyirik
biz nə etmək lazımdır, xüsusilə də əgər Bu yığını saxlanılır deyil istəyirik
lakin yığın?
Biz hüququ, malloc getmək?
Beləliklə, biz bir pointer yaratmaq olacaq.
Node, pointer, yeni bərabər bir node ölçüsü malloc
biz istəyirik çünki node yaradılacaq.
Biz məbləği istəyirəm bir node tutur yaddaş
üçün ayrılmış olunacaq yeni node yaradılması.
>> Və sonra biz yoxlamaq olacaq Yeni bərabər null bərabərdir oldu.
Biz nə dedi saxla?
Malloc nə olursa olsun, siz, Siz həmişə nə etməliyik?
Siz həmişə görmək üçün yoxlamaq lazımdır və ya ki, null edir.
>> Məsələn, əgər əməliyyat Sistem tamamilə dolu idi
Siz heç bir daha çox yaddaş olsa bütün və malloc üçün cəhd edin,
Bu sizin üçün null qayıtmaq istəyirəm.
Və belə ki, istifadə etmək üçün cəhd əgər Bu null işarə zaman,
edə fikrində deyilik ki, məlumat əldə etmək.
Və belə ki, biz etmək istəyirdi zaman mallocing əmin,
Siz həmişə görmek üçün kontrol edirik Sizə verilən yaddaş null edir.
Bu deyil, onda biz hərəkət edə bilər bizim kodu istirahət ilə.
>> Belə ki, biz olacaq yeni node başlamaq.
Biz yeni n n bərabərdir nə olacaq.
Və sonra biz nə olacaq Yeni yeni göstərici müəyyən
null indi biz deyil, çünki Bu qeyd etmək üçün bir şey istəyirəm.
Biz heç bir fikrim burada var Bu, sizi olacaq
sonra biz istəyirsinizsə rəhbəri onu daxil,
sonra biz redesign bilər baş göstərici.
Hər kəs məntiq riayət etmir harada ki, baş verir?
>> Biz yapýyorsun bütün yeni yaradır node, null göstərici yaradılması,
və sonra reassigning bu baş üçün biz əgər
Biz rəhbəri onu əlavə etmək istəyirəm bilirik.
Və sonra başını gedir yeni node doğru qeyd.
Ki, OK hər kəs?
>> Belə ki, iki addım prosesi var.
Siz ilk təyin etmək var hər hansı yaradılması edirik.
Ki, göstərici müəyyən arayış, və sonra
bilərsiniz dereference cür ilk pointer
və yeni node doğru qeyd.
Siz daxil istədiyiniz yerdə, ki, məntiq doğru keçirəcək.
>> Bu təyin kimi növü var müvəqqəti dəyişənlərin.
Unutmayın, siz var əmin etmək ki, siz
Siz dəyişdirmə edirsinizsə izini itirmək yoxdur.
Siz var ki, əmin etmək istəyirəm cür saxlayır müvəqqəti dəyişən
olduğu şey track ki, saxlanılır, siz
Əlbəttə hər hansı bir dəyəri itirmək yoxdur bunun ilə ətrafında messing kimi.
>> OK, belə ki, kodu burada olacaq.
Siz uşaqlar bölmə sonra bir göz atın.
Bu olacaq.
>> Belə ki, nə necə tapmaq biz istəyirdi bu fərqli
orta və ya sonunda daxil etmək olar?
Hər kəs nə bir fikir yoxdur məntiqi istinad kimi pseudocode
biz istəyirdi alırıq ki, ortasında daxil?
Belə ki, əgər biz onu əlavə etmək istədi rəhbəri, biz bütün yeni node yaratmaq edir.
Biz ki, göstərici müəyyən nə baş yeni node,
və sonra baş müəyyən yeni node, sağ?
Biz ortasında daxil etmək istəyirdi siyahısı, biz nə olardı?
>> Auditoriya: Bu hələ ki oxşar proses
bir göstərici təyin kimi sonra ki, pointer təyin
Amma biz orada tapmaq lazımdır.
>> ANDI PENG: Məhz, məhz belə Siz istisna olmaqla, eyni proses
dəqiq tapmaq üçün var Yeni pointer getmək istəyirəm,
Mən daxil etmək istəyirsinizsə, belə ki, OK list-- bağlı orta,
ki bizim bağlı siyahı var deyirlər.
Biz burada əlavə etmək istəyirsinizsə, biz yeni node yaratmaq olacaq.
Biz malloc olacaq.
Biz yeni node yaratmaq olacaq.
Biz təyin etmək olacaq Burada bu node göstərici.
>> Amma problem fərqlənir rəhbəri olduğu yerdən
biz məhz bilirdi ki, burada rəhbəridir.
Bu doğru, ilk doğru idi?
Lakin burada biz takip var harada biz bunu daxil daxil edirik.
Biz daxil varsa bizim burada node, biz var
əmin olun ki, bu node əvvəlki
göstərici reassigns biridir.
Beləliklə cür var iki şeyi takip.
Siz bu track saxlamaq node hazırda daxil daxil edilir.
Siz həmçinin takip var baxırıq əvvəlki node
var idi.
Ki, yaxşı hər kəs?
OLDU.
>> Necə sonunda daxil haqqında?
Mən istəyirdim əgər mən burada əlavə etmək istəyirdi siyahısı sonuna bir yeni node əlavə etmək üçün,
Mən bunu haqqında necə getmək bilər?
Auditoriya: Belə hazırda, son bir-nın null işarə etdi.
ANDI PENG: Bəli.
Məhz, belə ki, bu bir Hal-hazırda bilmək qeyd olunur,
və mən bu mənada, bu, tapmaq siyahısı sonuna əlavə etmək üçün çox asandır.
Siz bütün müəyyən edilir null və sonra bumu bərabər.
Orada çox asan.
Çox sadə.
>> Çox oxşar baş, lakin məntiqi
addımlar ki, əmin etmək istəyirəm Əgər bu hər hansı etdiyini doğru almaq
Siz birlikdə aşağıdakı edirik.
Bu ortada, çox asandır Sizin kodu, yakalanmış almaq
oh, mən çox göstəricilərinə var.
Mən harada bilmirəm bir şey işarə edir.
Mən hətta Ben hansı node bilmirəm.
Nə baş verir?
>> Bir dərin nəfəs almaq, sakitləşmək, Relax.
Sizin bağlı siyahısını cəlb edir.
Desəniz, mən dəqiq bilmək Mən bu daxil etmək lazımdır
və mənim redesign dəqiq necə göstəricilər, çox, daha asan şəkil
yazaraq çox asan deyil Sizin kodu hataları itirilmiş almaq.
Ki, OK hər kəs?
OLDU.
>> Belə ki, biz bir anlayış tapmaq həqiqətən, indi əvvəl haqqında danışdı
və yəqin ki, siz tahmin çox yet-- qarşılaşa deyil
Bu inkişaf etmiş konsepsiyası növü var biz, həqiqətən, məlumatlar var ki,
strukturu ikiqat bağlı siyahı çağırıb.
Uşaqlar Gördüyünüz kimi, biz yapýyorsun bütün yaradır
faktiki dəyəri, əlavə Bizim qovşaqlarının hər pointer
ki, əvvəlki node göstərir.
Belə ki, yalnız bizim var qovşaqlarının növbəti bir qeyd.
Onlar həmçinin əvvəlki işarə edir.
İndi bu iki ignore gedirəm.
>> Belə ki, sonra bir zəncir var ki, həm yolları hərəkət edə bilər,
və sonra bir az daha asan var məntiqi boyunca riayət edin.
Burada kimi, yerinə oh, track saxlanılması, mən
bu node ki, bilmək lazımdır Mən redesign üçün bir,
Mən burada getmək və bilərsiniz yalnız əvvəlki çəkin.
Sonra mən dəqiq bilirəm ki, sonra
axır yoxdur bağlı siyahı bütövlükdə.
Bu bir az daha asandır.
>> Lakin belə kimi, ikiqat var göstəricilər məbləği,
yaddaş ikiqat məbləği.
Bu takip göstəricilər bir çox var.
Bu bir az daha mürəkkəb, lakin bu istifadəçi dostu olaraq bir az daha
Siz yerinə yetirmək üçün çalışırıq nə.
>> Belə ki, məlumatların bu tip strukturu tamamilə, mövcud
və strukturu çox, çox deyil Siz qarşılaşdıqda bütün başqa sadə,
əvəzinə növbəti yalnız bir göstərici, Siz həmçinin əvvəlki bir göstərici var.
Bütün fərq idi.
Ki, yaxşı hər kəs?
Cool.
>> Bütün hüquqlar, belə ki, indi mən həqiqətən, yəqin ki, sərf etmək
15 20 dəqiqə və ya toplu kimi bölməsində vaxt istirahət
hash masalar haqqında söhbət.
Necə uşaqlar çox pset5 spec oxumaq?
Bütün hüquqlar, yaxşı.
Bu adətən 50% daha yüksək var.
Yaxşıdır.
>> Sizlərin görəcəksiniz kimi, belə ki, Siz pset5 problem istəyirik
bir lüğət həyata olacaq Siz 140,000 sözləri üzərində yük harada
biz yazım çek sizə verir ki, bütün mətni qarşı bu.
Biz sizə təsadüfi verəcəyik ədəbiyyat ədəd.
Biz sizə Odyssey verəcəyik.
Biz sizə İliada verəcəyik.
Biz sizə Austin Powers verəcəyik.
>> Və problem çek yazım olacaq
bütün hər bir söz o lüğətlərin
mahiyyətcə bizim spell checker ilə.
Və belə bir neçə hissələri var Bu pset yaradılması,
ilk olmaq istəyirəm həqiqətən yüklemek üçün edə
bütün sözlər lüğət və sonra
etmək istəyirəm onların hamısı yoxlamaq sehr.
Və belə kimi, tələb olacaq bu sürətli edə bilər ki, bir data strukturu
və səmərəli və dinamik.
>> Belə ki, asan güman Bunu etmək üçün yol, sizə
yəqin ki, sağ, bir sıra yaratmaq olar?
saxlama en asan yol deyil 140,000 sözlər bir sıra yarada
və yalnız orada bütün yer və sonra ikili axtarış onları axır
və ya Marka və ya deyilik sorry ki, çeşidlənməsi edir.
Siz onları sort və sonra onları axır bilər ikili axtarış və ya sadəcə xətti axtarış
və yalnız son sözləri, lakin yaddaş böyük bir məbləği alır
və bu, çox səmərəli deyil.
>> Və belə ki, biz başlamaq olacaq edilməsi yolları haqqında söhbət
Bizim çalışan zaman daha səmərəli.
Və bizim məqsədimiz almaq üçün daimi vaxt harada
demək olar ki, serialların, kimi Siz ani girişi var.
Mən bir şey üçün axtarış istəyirdi, Mən yalnız etmək istəyirəm
boom, dəqiq tapmaq və onu çıxarmaq.
Və belə bir quruluş olan biz çox yaxın olmaq lazımdır
daimi daxil etmək üçün vaxt bu müqəddəs grail
davamlı proqramlaşdırma vaxt hash table adlanır.
Və belə David əvvəllər qeyd [Işitilemez] mühazirə bir az,
lakin biz, həqiqətən olacaq dərin bu həftə dive
bağlı olan bir parça necə bir hash table işləyir.
>> Yol Belə ki, bir hash masa işləri, məsələn,
Mən sözləri bir dəstə saxlamaq istəyirdi, bir İngilis dili sözlər dəstə,
Mən nəzəri qoymaq bilər banan, alma, kivi, mango, cüt,
və bütün yalnız bir sıra qovun.
Onlar bütün uyğun bilər tapmaq bilər.
Bu bir ağrı növü olarıq və çıxış vasitəsilə axtarış,
lakin bunu asan bir yoldur biz bir quruluş, həqiqətən, yaratmaq bilər ki,
biz hash bir hash table çağırıb.
Biz vasitəsilə düymələri bütün run bir hash funksiyası, bir tənlik,
ki, onları bütün çevrilir bir dəyər bir növ
sonra biz üzərində bilərsiniz ki, bağlı siyahı mahiyyətcə bir sıra.
>> Və belə ki, burada biz, istəyirdi İngilis dili sözlər saxlamaq üçün,
biz potensial yalnız bilər, mən deyil , bilirik bütün ilk hərflərini çevirmək
bir sıra bir növ.
Belə ki, məsələn, əgər mən istədim A apple-- sinonimi olmaq
və ya 0 indeksi ilə, və B, 1 sinonimi olmaq
biz 26 entries ola bilər yalnız bilərsiniz
hərflərinin bütün biz ilə başlamaq lazımdır əlifba.
Və sonra biz ola bilər 0 index da alma.
Biz index da banan ola bilər 1, 2 index da qovun,
və s və s.
Və beləliklə mən axtarmaq istəyirdi Mənim hash masa və giriş alma,
Mən alma ilə başlayır bilirik A, mən dəqiq bilirəm
Bu və hash lazımdır ki, index 0, çünki masa
funksiyası əvvəl təyin.
>> Bilmirəm Belə ki, biz var bir istifadəçi proqram harada
Siz ittiham olacaq özbaşına deyil arbitrarily--,
fikirli üçün çalışırıq ilə yaxşı tənliklər hesab
yaymaq etmək Sizin dəyərlərin bütün
bir şəkildə onlar asanlıqla əldə edə bilərsiniz sonra ilə bir tənlik kimi
Siz ki, özünüz, bilirik.
Mən getmək istəyirdi mənada belə mango, mən oh, bu m ilə başlayır, bilirik.
12 indeksi olmalıdır.
Mən bir şey vasitəsilə axtarış yoxdur.
Mən yalnız getmək bilər exactly-- bilirəm və 12 index ki çəkin.
>> Necə bir hər kəs aydın hash masa funksiyası işləyir?
Bu, yalnız daha mürəkkəb serialın növü var.
Ki, bütün var.
OLDU.
>> Belə ki, biz daxil tapmaq Bu məsələ nə
Bir neçə şey varsa olur ki, eyni index verir?
Belə ki, bütün, bu, bizim funksiyası demək ki ilk məktub almaq idi
və çevrilir 0 index 25 vasitəsilə müvafiq.
Ki, əgər tamamilə gözəl var yalnız hər biri var.
Amma ikinci başlamaq daha çox olan, sen
toqquşma adlanır nə üçün gedir.
>> Mən daxil etmək üçün cəhd əgər bir hash daxil basdırmaq So artıq bu banan var masa
nə zaman baş verəcək ki, daxil etmək üçün cəhd?
Pis şeylər çünki banana artıq kataloq daxilində mövcud
Siz onu saxlamaq üçün istəyirəm.
Berry cür mən nə etməliyəm, ah, kimi?
Mən getmək harada bilmirəm.
Mən bu necə həll edə bilərəm?
>> Və belə ki, uşaqlar olacaq cür Biz bu çətin şey görmək
biz cür həqiqətən bilərsiniz Bizim seriallarda bağlıdır siyahısını yaratmaq.
Və belə asan yol Bu barədə düşünmək,
bütün hash table bir bağlı siyahıları array.
Belə ki, o mənada ki, var göstəricilər bu gözəl array,
və sonra hər pointer da ki, dəyəri ki indeksi,
həqiqətən başqa şeylər qeyd edə bilərsiniz.
Və belə ki, bütün bu ayrı böyük bir serialın off gələn zəncir.
>> Və belə ki, burada mən əgər giləmeyvə əlavə etmək istədi,
Mən OK, mən daxil gedirəm, bilirik mənim hash funksiyası vasitəsilə.
Mən indeksi ilə başa gedirəm 1 və sonra mən malik olmaq gidiyorum
Bu yalnız kiçik bir alt nəhəng 140,000-söz lüğət.
Və sonra mən yalnız baxmaq olar ki, 1/26 vasitəsilə.
>> Və sonra mən yalnız əlavə edə bilərsiniz əvvəl və ya banan sonra da berry
bu halda?
Sonra, sağ?
Və belə ki, istədiyiniz olacaq banan sonra bu node daxil,
və siz daxil olacaq ki bağlı siyahı quyruq.
Mən geri getmək üçün gedirəm bu əvvəlki slayd,
Belə ki, uşaqlar necə görə bilərsiniz hash funksiyası işləyir.
>> Belə ki, hash funksiyası bu tənlik Siz daxil cür yayınlıyorsanız ki,
almaq üçün nə index vasitəsilə Siz doğru təyin etmək istəyirəm.
Belə ki, bu nümunə, bütün istədik etmək üçün, ilk məktub almaq idi
biz sonra bir index çevrilir Bizim hash funksiyası ki, bilərsiniz.
Biz burada yapýyorsun bütün biz istəyirik ilk məktub konvertasiya.
Belə ki, keykey [0], yalnız ilk məktub nə string biz qarşılaşdıqda,
biz keçən edirik.
Biz yuxarı ki, konvertasiya və edirik biz böyük A subtracting edirik
Bunu ki, bütün Bizə bir sıra verir
olan biz dəyərlər üzərində hash bilər.
>> Və sonra biz olacaq hash modulus SIZE qayıtmaq.
Çox, çox ehtiyatlı olun nəzəri, burada, çünki
Sizin hash dəyəri sonsuz ola bilər.
Bu, yalnız və və davam edə bilər.
Bu, həqiqətən bir ola bilər həqiqətən böyük dəyəri,
ancaq hash masa çünki yaratdığınız yalnız 26 göstəriciləri var,
Sizi əmin etmək istəyirəm sizin modulusing ki,
Bu eyni run-- deyil Sizin Sıraya kimi şey
belə ki, çıxmaq deyil ki, Sizin hash funksiyası alt.
>> Siz ətrafında geri paketi istəyirəm [Işitilemez] zaman eyni şəkildə
, bir çox kimi idi çox böyük məktub, siz
ki istəmədi yalnız son çıxmaq.
Burada eyni şey, əmin etmək istəyirəm Bu qucaqlayaraq son çıxmaq deyil
ətrafında masa üst.
Belə ki, bu, yalnız bir çox sadə hash funksiyası.
Etdi ki, bütün almaq birinci oldu nə bizim giriş məktub idi
və bir siyahısını çevrilir ki, biz hash masa qoymaq bilər.
>> Bəli, və mən əvvəl dediyim kimi biz toqquşma həll yolu
Bizim hash masalar olan, biz chaining, nə zəng.
Bir neçə əlavə etmək üçün cəhd edin, belə ki, eyni şey ilə başlamaq sözlər,
Bir hash dəyəri olacaq.
Avokado və alma, siz var əgər Bizim hash funksiyası vasitəsilə run,
vermək üçün gedir eyni sayda, 0 sayı.
Və belə şəkildə ki, həll Biz, həqiqətən, növ onlara keçid edə bilər ki,
birlikdə bağlı siyahıları vasitəsilə.
>> Və bu mənada, Sizlərin cür görə bilərsiniz
necə data strukturları ki, biz əvvəl qəbulu olduğunuz
bir üzüm bağlı siyahı növ kimi birinə araya gələ bilər.
Və sonra uzaq yarada daha səmərəli data strukturları
ki, böyük miqdarda idarə edə bilərsiniz data, dinamik olaraq boyutlandır
Sizin ehtiyacları.
Hər kəs aydın?
Aydın hər kəs cür burada nə var?
>> Mən insert-- istəyirdi əgər nə Bilmirəm ilə başlayır meyvə,
Giləmeyvə başqa B, banan.
>> Auditoriya: Blackberry.
>> ANDI PENG: Blackberry, blackberry.
Harada blackberry burada getmək edir?
Yaxşı, biz, həqiqətən, sıralanır deyil Bu hələ, lakin nəzəri
bu etmək istəyirdi əgər əlifba sırası ilə,
harada getmək BlackBerry lazımdır?
>> Auditoriya: [işitilemez]
>> ANDI PENG: Məhz, burada sonra, sağ?
Amma bu çox çətin ildən reorder-- Mən bu uşaqlar var danışarlar.
Siz uşaqlar tamamilə bilərsiniz Istədiyiniz hər hansı həyata keçirir.
daha səmərəli yol bəlkə bunu
Sizin bağlı düzmək olardı əlifba sırası daxil siyahısı,
və belə olduğunuzda şeyi daxil istədiyiniz
onlara əlavə etmək üçün əmin olmaq Əlifba sırası daxil
belə ki, sonra etdiyiniz zaman onları axtarmaq üçün çalışır,
hər şey axır yoxdur.
Siz dəqiq bilmək Bu və bu asandır.
>> Amma cür varsa şeyi, təsadüfi interspersed
Siz hələ olacaq zaten axır.
Və mən istəyirdi yalnız blackberry burada daxil
və mən üçün axtarış istəyirdi Bu, mən oh, bilirəm, böyürtkən
1 göstəricisi ilə başlamaq, mən olmalıdır dərhal yalnız 1-axtarış bilirik.
Və sonra mən növ edə bilərsiniz bağlı siyahı axır
BlackBerry almaq qədər, və yeah then--?
>> Auditoriya: create-- çalışdığınız Əgər Bu, çox sadə hash kimi hərhalda
funksiyası.
Və biz bunu istəyirdi kimi çox qat,
OK, biz daxil ayırmaq istəyirəm bütün əlifba məktublar kimi
və sonra bir set kimi ki, daxilində əlifba məktublar,
biz bir hash kimi qoyurlar bir hash masa ərzində masa,
və ya bir funksiyası ərzində funksiyası kimi?
Və ya that-- deyil
>> ANDI PENG: Sizin hash So Sizin hash masa funksiyası
siz istədiyiniz kimi böyük ola bilər.
Belə ki, bu mənada, mən düşündüm bu, çox, çox asan idi
Mənim üçün sadə yalnız sort based ilk sözü məktublar.
Və belə ki, yalnız 26 variantları var.
Mən yalnız 26 variantları əldə edə bilərsiniz 25 0, çünki onlar yalnız bilərsiniz
A Z. başlamaq Amma istəyirdi , bəlkə də, daha mürəkkəbliyi əlavə etmək
və ya daha sürətli vaxt run hash table, tamamilə
şeyi bütün növ edə bilərsiniz.
Siz öz edə bilərsiniz verir tənlik
daha distribution sizin sözlər, sonra axtarış zaman
daha sürətli olacaq.
>> Bu tamamilə uşaqlar var necə ki həyata keçirmək istəyirik.
Yalnız buketler kimi düşünün.
Mən istəyirdi 26 buketler, mən gedirəm
o buketler daxil şeyi düzmək üçün.
Amma bir dəstə üçün gedirəm hər bucket məhsullarının,
Siz etmək istəyirsinizsə, belə ki, daha sürətli və daha səmərəli,
Mənə bir yüz buketler edək.
>> Amma sonra bir anlamaq üçün onlar ki, yol hər şeyi sort
müvafiq bucket onlar olmalıdır.
Amma sonra zaman həqiqətən ki, bucket baxmaq istəyirəm,
var, çünki bir çox daha sürətli hər bucket az stuff.
Belə ki, Bəli, ki, həqiqətən var pset5 siz uşaqlar üçün oyun
Siz olacaq ki, yalnız yaratmaq üçün etiraz
ən səmərəli nə varsa Siz hesab edə bilər funksiyası
saxlamaq və bu dəyərləri kontrol edə.
>> Ümumilikdə uşaqlar üçün lakin siz bunu istəyirəm,
lakin həqiqətən yaxşı bir nöqtə var.
Bu məntiq cür haqqında düşünür başlamaq istəyirəm
yaxşı, niyə daha buketler yoxdur, var.
Və sonra mən axtarış az şey, və sonra bəlkə mən
fərqli bir hash funksiyası var.
>> Bəli, bunu yolları bir çox var pset, bəzi daha sürətli edir.
Mən tamamilə necə görmək üçün gedirəm sürətli sürətli uşaqlar olacaq idi
Sizin funksiyaları iş almaq mümkün.
OK, hər kəs yaxşı on chaining və hash masalar?
Bu, çox sadə kimi həqiqətən Bu barədə anlayışı düşünürəm.
Bu bütün ayıran nə Sizin giriş buketler daxil,
onların çeşidlənməsi və sonra axtarış ilə bağlı ki, siyahıları.
>> Cool.
Bütün hüquqlar, indi biz fərqli bir növ var data strukturu bir ağac deyirlər ki.
Üzrə gedək və çalışır haqqında danışmaq ki, aydın müxtəlif var
lakin eyni kateqoriyada.
Əsasən, bütün bir ağac əvəzinə xətti şəkildə məlumatları təşkil
bir hash table sizə does-- ki , bir top və bir alt var bilirik
və sonra cür pseudocode bir off keçid ağac, siz kök zəng edən bir top var
və sonra bütün ətrafında yarpaqları var.
>> Və belə ki, bütün burada var yalnız üst node edir
digər qovşaqlarının, xal xal daha qovşaqlarının, və s və s.
Və belə ki, yalnız parçalanması filialı var.
Bu təşkil yalnız bir müxtəlif yolu var məlumat və biz bir ağac zəng çünki,
Siz uşaqlar yalnız var izlersin bir ağac kimi baxmaq üçün modelləşdirilmişdir.
Biz ağac zəng görə.
>> Hash table bir masa kimi görünür.
A ağac yalnız bir ağac kimi görünür.
Bu bütün ayrı qovşaqlarının təşkili yolu
Sizin ehtiyaclarını nə asılı olaraq.
>> Belə ki, bir kök və sonra yarpaqları var.
yol ki, biz xüsusilə bilər Bu ikili ağac haqqında düşünmək,
ikili ağac yalnız bir deyil bir ağac xüsusi bir növü
hər bir node yalnız xal üçün, max, digər iki qovşaqlarının.
Və belə ki, burada fərqli var Sizin ağac simmetriya
ki, daha asan cür baxmaq edir dəyərlər nə sonra çünki var
həmişə bir sol və ya hüququ var.
Bir sol üçüncü kimi var heç olacaq sol və ya soldan dördüncü.
Bir sol və hüququ var, yalnız var və bu iki ya axtarış edə bilərsiniz.
Və belə ki, niyə bu faydalıdır?
bu yol Siz arıyorsanız faydalıdır
sağ, dəyərlərə vasitəsilə axtarış?
Əksinə ikili həyata daha bir səhv sıra axtarış
Siz qovşaqlarının daxil etmək istəyirdi və iradəsi ilə və həmçinin qovşaqlarının götürmek
axtarış qorumaq ikili axtarış imkanları.
Belə ki, bu şəkildə, biz növ istəyirik zaman xatırlayıram tricking--
bağlı siyahıları ikili axtarış bilməz dedi?
Biz belə bir data strukturu yaratmaq edirik tövsiyələr iş daxil ki.
>> Və çünki bağlı siyahıları, xətti var onlar yalnız bir-birinin ardınca keçid.
Biz növ ola bilər göstəricilərinə müxtəlif sort
müxtəlif qovşaqlarının işarə ki, axtarış kömək edə bilər.
Və belə ki, burada, mən istəyirdi bir ikili axtarış ağac,
Mən bilirəm mənim ortasında 55 əgər.
Mən yalnız yaratmaq gedirəm Mənim orta kimi, mənim kök kimi,
və sonra mən gedirəm dəyərləri off fırlatmaq.
>> Belə ki, burada, mən axtarmaq üçün gedirəm əgər 66 dəyəri, mən 55 başlaya bilərsiniz.
Bu 55-dən çox 66 böyük var?
Bəli, belə ki, mən axtarış Muş bilmək i n bu ağacın sağ göstərici.
Mən 77 gedin.
OK, az və ya 77-dən çox 66?
Oh, bu, az, belə ki, bilirsiniz, ki, sol node olmalıdır.
>> Və belə ki, burada biz növ qorunması edirik Diziler haqqında böyük şeyi,
belə dinamik boyutlandırma kimi obyektlərin, olan
daxil edin və iradəsi ilə silmək mümkün, sabit narahat olmadan
kosmik məbləği.
Biz hələ bütün qorumaq o gözəl şeylər
də qorumaq edə olarkən daxil və ikili axtarış dəfə axtarış
biz əvvəllər yalnız idi ki, Bir söz əldə edə.
>> Cool data strukturu cür mürəkkəb, node həyata keçirmək.
Siz onu bütün edə bilərsiniz kimi node struct edir
Bir sol var və düzgün göstərici.
Ki, bütün var.
Belə ki, deyil, yalnız çox bir x və ya əvvəlki olan.
Daha sonra sol və ya sağ, və var cür onları birlikdə keçid
Lakin belə download.
>> OK, biz, həqiqətən olacaq yalnız bir neçə dəqiqə.
Beləliklə, biz burada geri olacaq.
Mən əvvəllər dediyi kimi, I növ izah
Biz necə məntiqi Bu vasitəsilə axtarış edəcək.
Biz cəhd olacaq bu out pseudocoding görmək
biz növ müraciət edə bilər, əgər ikili axtarış eyni məntiq
data strukturu müxtəlif növü.
Sizlərin bir neçə kimi almaq istəyirsinizsə dəqiqədə yalnız bu barədə düşünmək.
OLDU.
Bütün sağ, mən gedirəm həqiqətən, yalnız heç bir the-- vermək,
Biz ilk pseudocode haqqında danışmaq lazımdır.
Belə ki, hər kəs istəyir bir zərbə vermək nə
zaman etmək istəyirəm ilk şey Siz axtarış başlanğıc etdiyiniz?
Biz arıyorsanız 66 dəyəri, nə
Biz əgər bunu istədiyiniz ilk şey bu ağac axtarış ikili istəyirsiniz?
>> Auditoriya: Siz sağ baxmaq istəyirəm və [işitilemez] Sol baxmaq və görmək
daha çox.
>> ANDI PENG: Bəli, dəqiq.
Belə ki, sizin kök baxmaq olacaq.
Siz zəng edə bilərsiniz yolları çox var bu, sizin valideyn node insanlar demək.
Çünki kök demək istəyirəm ki, ağac kökü kimi.
Siz baxmaq olacaq kök node və siz etdiyiniz
görmək olacaq 66 böyükdür daha az və ya 55.
Və bu yaxşı, bu, daha çox varsa daha çox, biz baxmaq istəyirsiniz?
Harada biz doğru, indi axtarış istəyirsiniz?
Biz axtarmaq istədiyiniz bu ağacın sağ yarım.
>> Belə ki, biz, rahat, bir sağ işarə göstərici.
Və sonra biz bilərsiniz yeni kök 77 olmalıdır.
Biz yalnız yerdə getmək bilər pointer işarə edir.
Yaxşı, oh, burada biz başlayaraq edirik 77, və biz yalnız bilərsiniz
recursively təkrar edirik.
Bu yolla, siz cür bir funksiyası var.
Siz ki, axtarış bir yol var yalnız və üzərində üzərində təkrar edə bilərsiniz,
siz baxmaq istədiyiniz asılı olaraq Siz nəhayət dəyəri almaq qədər
sizin üçün axtarış etdiyiniz.
Salam?
>> Mən sizə faktiki göstərmək haqqında Ben kodu, və kodu bir çox var.
Ehtiyac yoxdur qəribə.
Biz onun vasitəsilə danışmaq lazımdır.
>> Əslində, no.
Bu yalnız pseudocode idi.
OK, yalnız pseudocode idi olan bir az mürəkkəb,
lakin tamamilə gözəl var.
Burada hər kəs birlikdə aşağıdakı?
Kök null varsa, qaytarılması saxta deməkdir, çünki
Siz hətta orada heç bir şey yoxdur.
>> Kök n əgər belə dəyəri, əgər baxırıq biri olur,
sonra doğru geri olacaq Bilirsiniz, çünki siz onu tapdı.
Amma dəyəri az olduqda n kök çox, siz etdiyiniz
sol axtarış gedir uşaq və ya sol yarpağı,
Siz zəng etmək istəyirəm nə.
Və dəyəri kök daha böyük olduqda, sağ ağac axtarış olacaq,
sonra yalnız funksiyası run axtarış vasitəsilə yenidən.
>> Və kök, null olduğunu ki, əgər Siz son əldə etdik deməkdir?
Ki, heç bir var deməkdir daha yarpaqları axtarış,
sonra mən, oh, bilirik burada deyil tapmaq
Mən nəzərdən sonra, çünki və burada deyil bütün şey,
Bu yalnız burada ola bilər.
>> Ki, hamıya mənada edirmi?
Belə ki, qorunması ikili axtarış kimi bağlı siyahıları imkanları.
Cool, və ikinci növü data strukturu uşaqlar
Sizin pset həyata cəhd edə bilərsiniz, Yalnız bir metodu seçmək lazımdır.
Amma yəqin ki, alternativ metodu hash table bir trie zəng edir.
>> Bütün bir trie bir ağac xüsusi növü ki,
digər dəyərləri getmək dəyərləri var.
Belə ki, əvəzinə bir ikili olan mənada ağac yalnız bir ki,
şey iki qeyd edə bilərsiniz, siz ola bilər bir çox şey üçün bir şey point.
Siz mahiyyətcə Diziler var olan saxlamaq daxili
digər serialların qeyd göstəricilər.
>> Beləliklə, biz necə node bir trie müəyyən olardı
biz var istəyirəm Boolean, c söz, sağ?
Belə ki, node Boolean var , doğru və ya yalan kimi
başında ilk növbədə ki array, bu söz?
İkincisi, siz göstəricilərinə var istəyirəm nə üçün onlara qalan var.
A bit mürəkkəb, bir az mücərrəd, lakin Mən ki, bütün vasitələrdən izah edəcək.
>> Belə ki, burada, üst, əgər bir sıra artıq elan var,
Bir Boolean bir node ön saxlanılan dəyəri
ki, bu bir söz deyir?
Bu bir söz deyilmi?
Və sonra var Sizin array qalan ki,
həqiqətən mağazalar bütün Bu ola bilər nə imkanları.
Belə ki, məsələn, kimi üst var
doğru və ya deyir ki, ilk şey yalan, bəli və ya xeyr, bu söz.
>> Və sonra 26 vasitəsilə 0 var Siz bilərsiniz məktublar.
Mən burada axtarmaq istəyirdi yarasa, mən üst getmək
və mən B tapmaq B. axtarmaq mənim array və mən bilirəm, OK, B bir söz?
B beləliklə, bir söz deyil Mən axtarış saxlamaq lazımdır.
Mən B getmək və mən baxmaq B doğru işarə pointer
Mən, informasiya bir sıra görmək biz əvvəl idi, eyni strukturu.
>> Və oh növbəti burada [Işitilemez] məktub A.
Belə ki, sıra baxmaq.
Biz səkkizinci dəyər tapmaq, sonra biz, oh, bax
hey, bir sözlə ki, B-A bir söz?
Bu bir söz deyil.
Biz axtarır saxlamaq üçün var.
>> Və sonra biz burada baxmaq A bal pointer,
və başqa şəkildə işarə Hansı daha çox dəyər saxlanılır.
Və nəhayət, biz almaq Bir söz B-A-T.
Və belə növbəti dəfə Siz baxmaq, siz olacaq
Bəli, ki, çek üçün, Bu Boolean funksiyası doğrudur.
Və belə ki, mənada, biz gözləyirik diziler ilə bir ağac olan.
>> Beləliklə cür aşağı axtarış edə bilərsiniz.
Əksinə bir funksiyası hashing çox və bağlı siyahı ilə dəyərlər təyin,
yalnız bir həyata keçirə bilər downwords axtarış trie.
Həqiqətən, həqiqətən məhsulları mürəkkəb.
Mən kimi deyiləm, çünki düşünmək asan deyil bir çox data strukturları həyata spitting
sizə, lakin cür hər kəs yoxdur Bu məntiqi necə anlamaq?
>> Sərin, OK.
Belə ki, B-A-T, və sonra axtarış olacaq.
Siz davam olduğunuz növbəti dəfə oh, hey, bu doğru, bax,
Beləliklə, mən bu söz olmalıdır bilirik.
>> Zoo üçün eyni şey.
Belə ki, burada bir şey varsa, sağ indi biz İndi, zoo axtarmaq istədi,
Hal-hazırda zoo bir deyil Bizim lüğət söz
, çünki uşaqlar, Gördüyünüz kimi bir Boolean ilk yer
qayıtmaq doğru zoom sonunda.
Biz Z-O-O-M var.
>> Və belə ki, burada biz, həqiqətən, yoxdur Bizim lüğət söz, zoo,
Bu onay qutusu yoxlanılır deyil, çünki.
Belə ki, kompüter deyil zoo bir söz olduğunu bilirik
Çünki biz yol yalnız bir zoom burada saxlanılır
həqiqətən bir Boolean dəyəri var ki, doğrudur çevrildi edilmişdir.
Biz daxil etmək istəyirsinizsə Belə ki, söz, zoo bizim lüğət daxil,
biz bunu haqqında necə getmək olar?
Biz əmin etmək üçün nə etmək lazımdır nə bizim Kompüter Z-O-O bir söz bilir ki,
və ilk sözü Z-O-O-M?
>> Auditoriya: [işitilemez]
>> ANDI PENG: Məhz, biz Bu əmin etmək istəyirəm
Burada ki, Boolean dəyəri doğru off yoxlanılır.
Z-O-O, sonra biz yoxlamaq olacaq, belə ki, biz tam, hey, zoo bir söz bilirik.
Mən demək gedirəm bir söz belə kompüter
, zaman kompüter çek ki, Bu zoo bir söz olduğunu bilir.
>> Bütün bu məlumatları xatırlayıram çünki strukturları, bizim üçün çox asandır
oh, yarasa bir söz var, demək.
Zoo bir söz var.
Zoom bir söz var.
Amma siz bunu bina etdiyiniz zaman, kompüter heç bir fikir var.
>> Belə ki, dəqiq demək lazımdır nə nöqtədə bu söz?
Nə nöqtədə bir söz deyil?
Və nə nöqtədə nə şeyi axtarmaq lazımdır,
və nə nöqtədə mən növbəti getmək lazımdır?
Ki, aydın hər kəs?
Cool.
>> Və sonra gəlir problemi necə olardı
bir şey daxil haqqında getmək ki, faktiki olaraq deyil?
Belə ki, yalnız biz əlavə etmək istəyirəm deyək Bizim trie daxil söz, hamam.
Siz uşaqlar hazırda kimi Gördüyünüz kimi biz indi bütün, B-A-T
və bu yeni data strukturu bir ufak var idi ki,
biz güman, çünki null işarə oh, B-A-T sonra heç bir söz var ki,
niyə biz saxlamaq lazımdır ki, T. sonra hər şeyi olan
>> Biz sizə əgər Lakin problem yaranır sonra gəlir bir söz var istəyirəm
T.
Siz vanna varsa, istəyirik bir H istəyirik gedir.
Və belə ki, biz nə olacaq yoldur biz ayrı node yaratmaq olacaq.
Biz nə məbləği ayırmaq deyilik Bu yeni array üçün yaddaş,
və biz göstəricilərinə redesign olacaq.
>> Biz təyin etmək olacaq H, ilk növbədə, bu null,
biz xilas olacaq.
Biz olacaq H point aşağı.
Biz H görürsünüzsə, biz bunu istəyirik başqa bir yerdə getmək üçün.
>> Burada, biz sonra yes off kontrol edə bilərsiniz.
Biz T sonra H hit varsa, oh, sonra biz bu söz olduğunu bilirik.
Boolean doğru qayıtmaq üçün gedir.
Hər kəs ki, baş necə aydın?
OLDU.
>> Belə ki, mahiyyətcə, bütün Bu data strukturları
Bu gün üzərində getdi etdik ki, mən var həqiqətən, həqiqətən, tez onların üzərində getdi
və çox deyil üçün ətraflı və OK.
Siz messing başlamaq sonra O, sizə olacaq
harada takip saxlanılması bütün göstəricilər var
nə olur sizin data strukturları, Et Cetera.
Onlar çox faydalı olacaq və bu qədər var
uşaqlar tamamilə necə anlamaq üçün hər şeyi həyata keçirmək istəyirik.
>> Və belə pset4, bir 5 node oh, ki, səhvdir.
Pset5 imla hataları edir.
Mən əvvəl qeyd etdiyim kimi, bir dəfə olacaq yenə bizdən mənbə kodu download.
Üç əsas olmalıdır olacaq şeyi yüklənərkən olacaq.
Siz lüğətlər download lazımdır KERS, və mətnlər.
>> Bütün bu şeylər var ya sözləri lüğət
biz sizə check istədiyiniz ki, və ya informasiya test
biz sizə çek sehr etmək istəyirəm ki,.
Və belə lüğətlər biz gedir vermək
sizə istəyirik faktiki sözləri vermək Siz bir şəkildə elə saxlamaq üçün
bir sıra daha səmərəli.
Və sonra mətnlər var biz istəyirik nə olacaq
isteyen əmin olun sehr sözləri bütün real söz var.
>> Və belə üç blokları biz sizə verəcəyik proqramları
dictionary.c deyilir, dictionary.h və speller.c.
Və belə ki, bütün dictionary.c ki yoxdur nə həyata keçirilməsi üçün xahiş edirik.
Bu sözləri yükler.
Yoxlayır onları spell və bu əmin edir ki, hər şey düzgün daxil edilir.
>> diction.h yalnız bir kitabxana fayl ki, bütün bu funksiyaları bəyan edir.
Və speller.c, biz sizə vermək olacaq.
Siz hər hansı dəyişdirmək üçün ehtiyac yoxdur.
Bütün speller.c ki görür, yük ki, onun sürəti yoxlayır,
necə kimi benchmark test tez şeyə edirik.
>> Bu speller var.
Just ilə mess yoxdur, amma etmək Siz bunu nə başa düşürük.
Biz funksiyası adlanır getrusage istifadə Sizin yazım performansı sınayar
checker.
Bütün bu əsasən test edilir yoxdur Sizin lüğət hər şey zaman,
belə ki, onu anlamaq əmin olun.
Bu mess deyil ehtiyatlı olun və ya başqa şeyi düzgün çalışmaz.
>> Bu problem toplu üçün Siz uşaqlar həqiqətən dictionary.c dəyişdirmək üçün.
Biz sizə vermək olacaq Bir lüğət 140,000 sözlər.
Biz sizə bir mətn vermək olacaq Bu sözləri var fayl,
və biz təşkil edə olmaq istəyirəm bir hash masa və ya bir trie daxil onlara
biz oxumaq üçün xahiş zaman, çünki Siz yazım əgər təsəvvür yoxlamaq
Homer nin Odyssey kimi yoxlanılması.
Bu böyük, böyük test kimi.
>> Hər bir düşünün söz baxmaq idi
140,000 dəyərlər bir sıra vasitəsilə.
Ki, əbədi edəcək maşın çalıştırmak üçün.
Biz bizimdir bizim təşkil etmək istəyirik ki, daha səmərəli data strukturlarına data
Belə bir hash masa və ya bir trie kimi.
Və sonra uşaqlar cür edə bilərsiniz Siz giriş axtarmaq zaman
hər şeyi daha asan və daha tez.
>> Və belə toqquşma həll etmək üçün ehtiyatlı olun.
Siz bir dəstə almaq olacaq A. ilə start sözləri
Siz bir dəstə sözləri almaq olacaq Bu qədər B. ilə başlamaq
Istədiyiniz necə uşaqlar onu həll etmək.
Yəqin ki, daha çox var səmərəli hash funksiyası
yalnız ilk məktub bir şey, və ki, sizə var
uşaqlar cür istədiyiniz nə üçün.
>> Bəlkə əlavə etmək istədiyiniz birlikdə bütün məktublar.
Bəlkə qəribə şeylər kimi istəyirəm məktublar sayı hesab,
nə.
Siz istədiyiniz necə uşaqlar Up.
Siz əgər bir hash masa etmək istəyirsinizsə tamamilə size, bir trie cəhd etmək istəyirəm.
Mən vaxtından əvvəl sizi xəbərdar edəcək trie adətən bir az daha çətindir
bir çox var, çünki yalnız daha göstəricilərinə takip.
Amma tamamilə uşaqlar üçün.
Bu daha səmərəli əksər hallarda.
Siz, həqiqətən, davam edə olmaq istəyirəm Sizin göstəricilər bütün track.
Like eyni şey Mən burada bunu edir.
Zaman daxil çalışdığınız bir hash masa dəyərlər və ya silmək,
Siz etdiyiniz əmin olun həqiqətən takip saxlanılması
hər şey, çünki olduğu Mən deyiləm əgər həqiqətən asandır
sözü, Andy kimi daxil çalışır.
Yalnız bir deyirlər real söz, söz, andy,
A sözlər nəhəng siyahısına daxil.
>> Mən yalnız redesign nə varsa bir göstərici səhv oops,
tam orada gedir Mənim bağlı siyahı istirahət.
İndi yalnız söz I var andy və indi
digər sözləri bütün Lüğət itirmişdir.
Və belə ki, siz əmin etmək istəyirəm Sizin göstəricilər bütün takip
və ya başqa siz almaq olacaq Sizin kodu böyük problemləri.
Addım-addım diqqətlə şeyi cəlb edir.
Bu düşünmək bir çox asan edir.
>> Və nəhayət, siz etmək istəyirəm Proqram performans test
böyük board.
Sizlərin alsaq bir İndi CS50 baxmaq,
biz böyük board deyirlər nə var.
Bu sürətli hesab hesabatı CS50 bütün arasında yoxlanılması dəfə yazım
indi, mən 10 kimi üst hesab dəfə mən onlardan səkkiz heyəti hesab edirəm.
Biz, həqiqətən, uşaqlar bizi məğlub etmək istəyirik.
>> Hamımız həyata keçirilməsi üçün çalışdıqlarını mümkün qədər sürətli kodu.
Biz uşaqlar etiraz üçün cəhd etmək istəyirəm Bizə və hamımız daha sürətli həyata keçirilməsi
bilərsiniz.
Və bu həqiqətən biz istəyirik ilk dəfə
uşaqlar xahiş pset etmək ki, Siz, həqiqətən, nə metodu edə bilərsiniz
Sən istəyirsən.
>> Mən həmişə bu daha yaxın edir, demək real həyat həll, sağ?
Mən hey, mən bunu etmək lazımdır, deyirlər.
Mənim üçün bu ki, bir proqram qurmaq.
Lakin istədiyiniz bunu.
Mən yalnız oruc tutmaq istəyirəm ki, bilirik.
Bu həftə üçün problem var.
Siz uşaqlar, gedirik bir vəzifə vermək.
Biz sizə bir problem vermək olacaq.
Və sonra bu uşaqlar var tamamilə yalnız anlamaq üçün
qısa və ən nə səmərəli şəkildə bu həyata keçirmək.
Evet?
>> Auditoriya: Biz əgər icazə verilir Daha sürətli yolları tədqiqat istədi
Biz nə edə, online hash masalar etmək ki, başqasının kodu istinad?
ANDI PENG: Bəli, tamamilə gözəl.
Belə ki, uşaqlar oxumaq spec, bir xətt var
Siz uşaqlar deyir spec hash tədqiqat tamamilə pulsuzdur
nə bəzi funksiyaları tez hash funksiyaları
kimi vasitəsilə şeyi run ki, kodu istinad kimi uzun.
Belə ki, bəzi insanlar artıq sürətli yolları fiqurlu
sürətli ki, yazım dama edir məlumat saxlanılması yolları.
Ümumilikdə uşaqlar qədər əgər sağ, yalnız almaq istəyirsiniz?
Siz səbəb əmin olun.
problem burada həqiqətən Biz test çalışdığınız
Siz bilirsiniz ki, əmin edir yol ətrafında göstəricilər.
Kimi uzaq edə həyata kimi faktiki hash funksiyası
və kimi ilə gələn riyaziyyat bunu,
Sizlərin araşdırma nə üsulları online uşaqlar istəyirəm.
Evet?
>> Auditoriya: Biz yalnız göstərmək olar [Işitilemez] istifadə edərək?
>> ANDI PENG: Bəli.
Siz yalnız Sizin şərhiniz, Siz, oh, kimi göstərmək olar
Yada alınan yada, yada, hash funksiyası.
Hər hansı bir sualınız?
Biz, həqiqətən, breezed Bu gün bölmə vasitəsilə.
Mən burada olacaq eləcə də suallara cavab.
>> Həmçinin, dediyim kimi, ofis saat gecə və sabah.
Bu həftə əslində spec super asan və oxumaq üçün super qısa.
Mən yalnız bir nəzər alaraq gəlir ki, Bunun tam gəzib.
>> Və Zamyla həqiqətən siz dolaşır funksiyaları hər vasitəsilə
Siz həyata keçirilməsi üçün lazımdır, və bu hər şeyi necə çox aydın.
Just əmin sen etmək göstəricilərinə takip saxlanılması.
Bu, çox çətin pset edir.
>> Bu kimi, çünki çətin deyil oh, anlayışlar çox daha çox var
çətin, və ya öyrənmək lazımdır yol qədər yeni sintaksis
son pset üçün idi ki,.
Bu pset çətindir ki, bir çox göstəricilər var,
və sonra bir çox, çox asandır Siz edə sizin kodu bir səhv var
ki, səhv olduğu tapmaq üçün.
>> Və belə tam və sizə irad iman uşaqlar bizim [Işitilemez] döymək etmək
yazımlar.
Mən, həqiqətən, heç bir yazılı mina var hələ, amma mina yazmaq haqqında deyiləm.
Yazılı etdiyiniz zaman sizin, mən mina yazılı olacaq.
Mən etmək üçün cəhd gedirəm mina sürətli sizin daha.
Biz sürətli bir olan görəcəksiniz.
>> Və Bəli, mən bütün görəcəksiniz burada Çərşənbə axşamı günü uşaqlar.
Mən pset seminar kimi bir növ davam edəcək.
Bölmələr Bütün bu həftə, pset seminarlar
Belə ki, uşaqlar imkanları çox var yardım üçün, ofis saat həmişə olduğu kimi,
və mən, həqiqətən gözləyirik Sizin uşaqlar "bütün kodu oxu.
Mən burada əgər sınavlar qədər var uşaqlar bu almaq gəlmək istəyirəm.
Bu hamısıdır.