[MUSIC ifa]
DAVID J. MALAN: Bütün hüququ.
Bu CS50 edir.
Bu həftə beş davam edir və biz yaxşı xəbər və pis xəbər var.
Belə ki, yaxşı xəbər CS50 edir bu cümə başlayır.
Siz bizə qoşulmaq istəyirsinizsə, Burada adi URL rəhbərlik.
Hətta daha yaxşı xəbərlər, heç bir mühazirə Bu 13 Bazar ertəsi gəlir.
Az daha yaxşı xəbərlər, viktorina sıfır növbəti Çərşənbə edir.
Daha ətraflı ola bilər burada bu URL tapılmadı.
Və növbəti bir neçə gün ərzində biz blankların doldurulması olacaq
otaqlar ilə bağlı biz ayırdıq ki.
Daha yaxşı xəbərlər var lazımdır ki, kurs-geniş nəzərdən
sessiya bu gələn Axşam Bazar ertəsi.
Kurs nin Köklənən qalmaq yeri və ətraflı məlumat üçün haqqinda.
Bir olsa Bölmə, bayram, həmçinin görüşəcək.
Ən yaxşı xəbərlər, növbəti cümə mühazirə.
Belə ki, bu ənənə biz proqramı hər var.
Yalnız var Bu gözəl olacaq.
Siz kimi şeylər görəcəksiniz daimi vaxt data strukturları
və hash masalar və ağac və çalışır.
Və biz ad problemləri haqqında danışmaq lazımdır.
Məhsulları A bütün dəstə növbəti cümə gözləyir.
OK.
Afərin.
>> Beləliklə, biz etdik ki, xatırlayıram nə bu şəkil diqqət
bizim kompüter yaddaş daxilində.
Belə ki, yaddaş və ya RAM yerləşir proqramları Siz onlara etdiyiniz zaman mövcuddur.
Bir cüt basın icon bir proqram run
və ya cüt basın bir fayl açmaq üçün icon,
Sizin ağır yüklü olub sürücü və ya bərk dövlət sürücü
RAM, Random Access Memory, harada güc off gedir qədər yaşayır,
laptop qapaq bağlayıb və ya proqram çıxmaq.
>> İndi yaddaş, və siz yəqin ki,
1 gigabyte bu gün, 2 qiqabayt, və ya hətta daha çox,
ümumiyyətlə qoydu bir proqram üçün
düzbucaqlı bu cür konseptual model
biz altındakı yığını var qovuşdurmağımız və üst digər məhsullarının bir dəstə.
Çox üst şey bu şəkil gördüm
əvvəl heç danışdıq sözdə mətn seqment deyil.
Mətn seqment yalnız bir xülya yoludur adet sıfır və olanları deyərək ki,
faktiki tərtib proqram daxildir.
>> Belə ki, siz cüt basın Mac və ya PC Microsoft Word,
Siz dot çalıştırdığınızda və ya Mario zərbə Sizin terminal pəncərə Linux kompüter,
bəstələmək ki, adet sıfır və olanları Word və ya Mario müvəqqəti saxlanılır
sözdə sizin kompüter RAM xüsusi bir proqram üçün mətn seqment.
Ki, gedir Aşağıda başlatılmış və uninitialized data.
Bu qlobal dəyişənlər kimi stuff deyil, biz bir çox istifadə etdik ki,
lakin münasibətilə biz qlobal dəyişənlər var idi
və ya statik strings müəyyən ki, ağır "salam" kimi sözlər kodlu
istifadəçi qəbul deyil ki, ki, proqram ağır kodlu olunur.
>> İndi aşağı altındakı biz sözdə yığını var.
Və yığını, bu günə qədər biz oldum məqsədləri nə cür istifadə?
Yığını nə üçün istifadə edilmişdir?
Bəli?
>> Auditoriya: funksiyaları.
>> DAVID J. MALAN: funksiyaları üçün?
Funksiyaları üçün nə mənada?
>> Auditoriya: siz bir funksiyası zəng zaman, dəlilləri yığını üzərinə kopyalanır.
>> DAVID J. MALAN: Exactly.
Bir funksiyası zəng zaman, onun dəlilləri yığını üzərinə kopyalanır.
Belə ki, hər hansı bir X və ya Y və ya A və ya B-nin bir funksiyası keçən edirik ki,
müvəqqəti qoyulur sözdə yığını,
yalnız Annenberg biri kimi yemekhane qablar, və də hər şeyi
yerli dəyişənlərin kimi.
Əgər foo funksiyası və ya svop funksiyası yerli dəyişənlər var,
temp kimi, bu iki yığını başa.
İndi biz çox danışmaq olmaz onlara, lakin bu mühit dəyişənlər
altındakı biz bir müddət əvvəl gördüm Mən klaviatura bir gün futzing edilib
və Mən hər şeyi daxil başladı argv 100 və ya argv 1000 kimi,
yalnız elementləri Unuda Bu numbers-- lakin
mənim əldə etmək üçün nəzərdə deyil.
Biz bəzi görən başladı ekranda funky rəmzləri.
Həmin qondarma idi mühit dəyişənlər
qlobal parametrləri kimi mənim proqram və ya mənim kompüter, üçün
son olmayan biz müzakirə bug,
Shellshock ki, oldu bir neçə kompüter başına bəla.
>> İndi nəhayət, bu gün diqqət mərkəzində biz sonda yığın olacaq.
Bu yaddaş bir yığın edir.
Və əsaslı bütün bu yaddaş eyni stuff deyil.
Bu eyni hardware var.
Biz sort yalnız edirik müxtəlif qruplar müalicə
müxtəlif məqsədlər üçün bayt.
Yığın də olduğu olacaq siz tələb dəyişənlərin və yaddaş
Əməliyyat sistemi müvəqqəti saxlanılır.
>> Amma bir problem növü var Burada, şəkil nəzərdə tutur kimi.
Biz sort iki var haqqında gəmilərin toqquşmaq.
Daha çox və daha çox istifadə kimi çünki biz bu gün görürük yığını, və
irəli, siz daha çox istifadə kimi yığın, şübhəsiz ki, pis şeylər baş verə bilər.
Və həqiqətən, biz vadar edə bilər qəsdən və ya bilmədən.
Son cliffhanger belə vaxt bu proqram idi,
hər hansı bir funksional xidmət olmayan nümayiş başqa məqsədi
necə bir pis oğlan həqiqətən edə bilərsiniz kimi kiminsə proqram hataları üstünlüyü
və hətta bir proqram və ya üzərində bütün kompüter sistemi və ya server.
Belə ki, yalnız baxışda qısa, sizə altındakı əsas fərq
command line edir argv kimi dəlilləri.
Və bir funksiyası f zəng var, mahiyyətcə adsız funksiyası adlanır
f, və argv keçən [1].
>> Belə ki, ildə nə söz istifadəçi növləri Bu proqramın adına tez,
və sonra bu ixtiyari funksiyası top, f, simli, AKA char *
biz müzakirə başlayıb etdiyiniz kimi, və yalnız "bar." çağırır
Amma biz bir şey zəng edə bilər.
Və sonra daxili, elan f, simvol bir sıra
12 belə simvol ace çağırıb.
>> İndi, hekayə I izah edildi bir an əvvəl olduğu yaddaş
c, və ya o 12 var başa gedir Sandıqı?
Just aydın olmalıdır.
Bəli?
>> Auditoriya: yığını On.
>> DAVID J. MALAN: yığını On.
Belə ki, c yerli dəyişir.
Biz 12 chars və ya 12 bytes üçün xahiş edirik.
O qədər başa gedir sözdə yığını.
İndi nəhayət bu digər funksiyası ki, həqiqətən olduqca faydalı
lakin biz, həqiqətən, istifadə etdiyiniz özümüzü, strncopy.
Bu string surəti deməkdir, lakin yalnız məktublar, n simvol n.
Belə ki, n simvol olacaq c daxil bar kopyalanır.
Və nə qədər?
Bar uzunluğu.
Belə ki, başqa sözlə, ki, bir line, strncopy,
surəti gedir səmərəli c üçün bar.
>> İndi, yalnız cür tahmin Bu hekayə mənəvi,
nə burada potensial problemli?
Biz uzunluğu kontrol edirik baxmayaraq bar və strncopy onu keçən,
nə bağırsaq siz izah hələ bu proqram haqqında sınıq?
Bəli?
>> Auditoriya: daxil deyil null xarakter üçün otaq.
DAVID J. MALAN: daxil deyil null xarakter üçün otaq.
Potensial fərqli olaraq keçmiş təcrübə biz hətta deyil
bir plus 1 qədər ki, null xarakter yerləşdirmək.
Amma daha da pis deyil.
Başqa Biz nə uğursuz?
Bəli?
>> Auditoriya: [işitilemez]
DAVID J. MALAN: Perfect.
Biz ağır olduqca özbaşına 12 kodlu etdik.
Ki, çox deyil problem, lakin fakt
biz hətta əgər yoxlanılması deyilik ki, bar uzunluğu az 12
bu halda olacaq yaddaş onu qoymaq üçün təhlükəsiz
Biz təsis etdik ki, deyilən c.
Həqiqətən, bar kimi, əgər Uzun 20 simvol,
bu funksiya çıxarmaq üçün görünür Bununla c daxil bar, 20 simvol
ən azı 8 bayt alaraq Bu olmamalıdır.
Ki, burada dolayısı var.
>> Qısa, broken proqram,.
Böyük belə deyil.
Bəlkə bir seqmentasiya günah almaq.
Biz bütün proqramlar bugs etdik.
Biz bütün hataları ola bilər indi proqramlarında.
Lakin dolayısı nə var?
Yaxşı, burada bir zoomed-in versiyası var mənim kompüter yaddaş şəkil.
Bu, mənim yığını alt edir.
Və həqiqətən, çox altında var nə adlı valideyn gündəlik yığını, xülya yolu
ki, əsas deyərək.
Funksiyası adlanır kim ki söhbət edirik ki, f.
Belə ki, bu yığını alt edir.
Return ünvanı yeni bir şeydir.
O, həmişə, olub həmişə şəkil olmuşdur.
Biz buna diqqət adlanan heç vaxt.
Bu çıxır, çünki c işləri yoldur bir funksiyası başqa çağırır ki,
yalnız ki arqumentlər nə funksiyası yığını üzərinə sövq almaq,
yalnız funksiyası yerli yoxdur dəyişənlər yığını üzərinə sövq almaq,
bir şey return address adlı həmçinin yığını üzərinə qoymaq olur.
Xüsusilə, əsas zəngləri foo, əsas Agentliyi yaddaş öz ünvanı, öküz bir şey,
səmərəli yığını üzərinə qoymaq olur ki, f icra edilir zaman
mətn geri jump bilir həyata davam etmək üçün seqment.
>> Biz konseptual burada olduğunuz Belə ki, əsas, onda f adlı olur.
F bilir necə kim geri əl nəzarət?
Bəli, bu kiçik Burada qırmızı hier,
qaytarılması ünvan adlı, yalnız çek ki, return address nədir?
Oh, mənə burada əsas geri jump edək.
Və bir az var bir oversimplification,
Bu adet sıfır və olanları çünki əsas üçün texniki,
burada texnologiya seqmentində up.
Amma bu fikir var. f yalnız nə bilmək var
harada nəzarət nəticədə geri gedir.
>> Amma yol kompüter uzun şeyi qoydu
yerli dəyişənlərin kimi və arqumentlər bu kimi.
Bu şəkil üst Belə ki, mavi belə ki, bütün, f yığını çərçivəsində deyil
yaddaş ki, f xüsusi istifadə edir.
Belə ki, buna görə qeyd bar bu şəkil.
Bar onun dəlil idi.
Və biz iddia mübahisələr ki, funksiyaları yığını üzərinə sövq almaq.
Və c, əlbəttə, bu şəkil.
>> Və yalnız notational məqsədləri üçün, sol üst küncündə bildiriş
bracket 0 c nə olardı və sonra yüngül sol aşağı
c bracket 11.
Belə ki, başqa sözlə, siz təsəvvür edə bilərsiniz bayt grid var ki,
orada ilk olan sol üst, alt olan
Bu 12 bayt son deyil.
>> Amma indi irəli sürətli üçün cəhd edin.
Biz nə keçmək əgər nə haqqında c artıq ki, bir string bar?
Və biz əgər yoxlanılması deyilik həqiqətən artıq 12 daha var.
Bu şəkil hissəsi gedir bayt 0, 1, 2, 3 üzerine almaq,
dot dot dot, 11, və sonra pis, 12, 19 13?
Bundan əlavə, burada nə olacaq Siz sifariş nəticə çıxarmaq əgər
c bracket 0 üst edir və c bracket 11 aşağı sort edir
doğru?
Bəli?
>> Auditoriya: Bəli, bu gedir char * bar yazmaq.
>> DAVID J. MALAN: Bəli, bu kimi görünür Siz char * bar üzerine olacaq.
Və pis bir həqiqətən uzun göndərmək əgər simli, hətta nə üzerine bilər?
Qaytarılması ünvanı.
Hansı daha, yalnız bir kimi proqram yerləşir demək hier
zaman f geri adlanan edilir.
>> Belə ki, pis uşaqlar adətən nə Onlar bir proqram rast gəlmək əgər
Onlar olub maraqlı olduğunu belə bir şəkildə istismar, arabası
o bilər ki, ki, səhv üstünlüyü,
ümumiyyətlə onlar deyil Bu doğru ilk dəfə.
Onlar yalnız, məsələn, göndərilməsi başlamaq, Sizin proqram təsadüfi strings,
klaviatura olub, və ya səmimi onlar yəqin ki,
bir az proqram yazmaq yalnız avtomatik strings yaratmaq,
və proqram dolaşacağız Müxtəlif giriş çox göndərilməsi
müxtəlif uzunluqlu da.
>> Tez proqram qəzaları kimi, ki, bir gözəl şey var.
Bu o deməkdir və ya o aşkar etmişdir
hansı həqiqətən yəqin ki, bir səhv.
Və sonra onlar daha ağıllı əldə edə bilərsiniz və başlamaq daha dar diqqət
ki, səhv istifadə etmək necə.
Xüsusilə, nə o bilər nə hello, ən yaxşı halda, göndər.
No böyük.
Bu kifayət qədər qısa bir simli var.
Amma nə o göndərir əgər, və biz bunu kimi ümumiləşdirmək lazımdır
hücum sıfır belə kod və olanları şeyi
rm-rf kimi, hər şey aradan qaldırılması sabit və ya spam göndərmək
və ya birtəhər maşın hücum?
>> Bu hər Belə ki, əgər məktublar A yalnız təmsil
konseptual, hücum, hücum, hücum, hücum, bəzi pis kodu
başqası yazdı ki, ancaq həmin şəxs kifayət qədər ağıllı deyil,
yalnız bütün daxil o rm-RFS, həm də
onun son bir neçə bayt uyğun ki, bir sıra ola
ünvanına onun və ya öz hücum kodu
o yalnız keçdi tez onu verərək,
Siz səmərəli kompüter bezemek bilər f icra edilir zaman hiss daxil,
oh, mənə tullanmaq üçün vaxt var geri qırmızı qaytarılması ünvan üçün.
Amma o elə, çünki ki, geri ünvan overlapped
öz sayı ilə, və onlar kifayət qədər ağıllı olduğunuz
yapılandırılmış var sıra sizin kimi, istinad
super üst görəcəksiniz orada sol küncündə,
kompüter-ci ildə faktiki ünvanı hücum kodu bəzi yaddaş,
pis oğlan kompüter bezemek bilər öz kodu icra daxil.
>> Və code yenə, bir şey ola bilər.
Bu, ümumiyyətlə deyirlər yalnız olan shell kodu,
bu deyil ki, bir yol rm-rf kimi sadə ümumiyyətlə bir şey.
Bu, həqiqətən Bash kimi bir şey var və ya faktiki proqramında onu verir ki,
və ya onun proqram nəzarət icra onlar istəyirəm ki, başqa bir şey.
Belə ki, qısa, bu, bütün sadə fakt irəli gəlir
məşğul bu səhv yoxlanılması deyil ki, Sizin serialın sərhədləri.
Və yolu çünki kompüter iş ki, onlar
olan yığını istifadə səmərəli, konseptual,
up alt, lakin sonra elementləri Siz üst aşağı inkişaf yığını üzərinə basmaq
Bu olduqca problemlidir.
İndi, bu keçici yollar var.
Və səmimi, dil var olan bu keçici.
Java, məsələn, immun edir bu mövzuda.
Onlar göstəricilərinə vermir, çünki.
Onlar vermir birbaşa yaddaş ünvanları.
Biz bu gücü ilə belə yaddaş bir şey toxunmaq
Biz etiraf, böyük risk, gəlir istəyirəm.
>> Belə ki, bir göz saxlamaq.
Səmimi, əgər ay və ya il zaman gəlib
bəzi istismar haqqında oxumaq proqramın və ya server,
Əgər bir şey bir işarə görürsünüzsə bufer daşqın hücum kimi,
və ya yığın daşqın bir növü hücum, ruhda oxşar,
veb nin ruhlandırır qədər Siz bunu əgər, adını,
bütün yalnız söhbət bir xarakter ölçüsü coşğun
array və ya daha çox, ümumiyyətlə, bəzi array.
Bu sonra hər hansı bir sualınız,?
Evdə cəhd etməyin.
>> Bütün hüquqlar.
Belə ki, malloc günə qədər yeni olmuşdur biz yaddaş ayıra bilər ki dost
biz mütləq bilmirəm ki, biz belə biz istəmirik ki, inkişaf
daxil ağır kodu bizim 12 kimi proqram nömrələri.
Istifadəçi bizə nə qədər izah edir o daxil istəyir data,
biz çox yaddaş malloc bilər.
>> Belə ki, malloc bu üçün çıxır biz istifadə etdik dərəcədə,
aydın son dəfə və sonra Siz uşaqlar istifadə edilmişdir
üçün bilməyərək GetString bir neçə həftə, malloc yaddaş bütün
qondarma yığın gəlir.
Və bu, məsələn, niyə GetString edir dinamik yaddaş ayrılması bilər
Siz etdiyiniz nə bilmədən əvvəlcədən yazın gedir,
ki, yaddaş geri bir pointer Sizə təqdim, və yaddaş sizin saxlamaq üçün hələ,
hətta yekunları GetString sonra.
Çünki geri sonra bütün ki, yığını daim yuxarı və aşağı gedir
yuxarı və aşağı.
Və tezliklə gedir kimi aşağı, hər hansı bir yaddaş deməkdir
istifadə bu funksiya olmalıdır başqa hər kəs tərəfindən istifadə edilə bilməz.
İndi zibil dəyərlər var.
>> Amma yığın burada deyil.
Və malloc ki, haqqında gözəl nə var malloc burada yaddaş ayırır zaman,
Bu üçün, təsir deyil yığını ən hissəsi.
Və hər hansı bir funksiyası əldə edə bilərsiniz malloc'd edilmişdir ki, yaddaş,
hətta GetString kimi bir funksiyası ilə, hətta sonra qaytarılır.
>> İndi, malloc converse pulsuz.
Və həqiqətən, qayda siz qəbul başlamaq lazımdır
hər hansı bir hər hansı bir, malloc istifadə hər zaman Özünüz, nəhayət, pulsuz istifadə etməlidir
həmin göstərici.
Biz yazılı edilmişdir Bütün bu vaxt buggy, bir çox səbəblərə görə arabası kodu.
Amma biri olmuşdur Bu CS50 kitabxana istifadə edən
özü qəsdən edir buggy, bu yaddaş sızıntıları.
Siz GetString adlı etdik istənilən vaxt Son bir neçə həftə ərzində
Biz əməliyyat xahiş edirik sistemi, Linux, yaddaş üçün.
Və bir dəfə geri heç vaxt.
Və bu deyil, , yaxşı bir şey təcrübə.
>> Və Valgrind, biri Pset 4 təqdim tools,
sizə yardım haqqında bütün İndi kimi hataları tapa bilərsiniz.
Lakin təşəkkürlə Pset 4 ehtiyac yoxdur Bu CS50 kitabxana və ya GetString istifadə etmək.
Belə ki, yaddaş ilə bağlı hər hansı bir hatalar var nəticədə öz olacaq.
>> Belə ki, malloc yalnız daha çox Bu məqsədlə rahat.
Biz, həqiqətən, indi həll edə bilər əsaslı fərqli problemlər,
və əsaslı daha problemləri həll səmərəli həftə sıfır vədi kimi.
Belə ki, bu, seksual edir data strukturu biz etdik.
And data strukturu tərəfindən yalnız demək konsepsiyalarının yaddaş yolu
yalnız deyərək kənara çıxan bir şəkildə, bu bir char, bir int edir.
Biz birlikdə klaster şeyi başlaya bilərsiniz.
>> Belə ki, bir sıra bu kimi baxdı.
Və haqqında bir əsas nə idi array verir ki,
geri-to-geri chunks yaddaş, hər hansı
eyni tipli olacaq, int, int, int, int, və ya char, char, char,
char.
Amma bir neçə downsides var.
Bu misal üçün, ölçüsü altı bir sıra.
Siz altı ilə bu array doldurun düşünək nömrələri və sonra, nə səbəblərə görə,
istifadəçi vermək istəyir Bir yeddinci nömrəsi.
Harada qoymaq bilərəm?
>> Əgər siz həll nədir yığını bir sıra yaradılmış,
Məsələn, yalnız həftə ilə biz təqdim ki, iki notation,
daxilində bir sıra kvadrat mötərizə?
Yaxşı, siz altı var bu qutuları nömrələri.
Sizin instinktlərdən nə ola bilər?
Harada siz onu qoymaq istəyirsiniz?
>> Auditoriya: [işitilemez]
>> DAVID J. MALAN: Bağışlayın?
>> Auditoriya: sonunda qoyun.
>> DAVID J. MALAN: The sonunda qoyun.
Belə ki, yalnız sağ üzərində, Bu qutusuna kənarda.
Hansı gözəl ola bilər, lakin olardı siz bunu edə bilərsiniz çıxır.
Xahiş etdik, çünki yaddaş bu yığın,
Bu təsadüf ola bilər bəzi digər dəyişən istifadə olunur
cəmi.
Biz qoydu zaman belə bir həftə geri düşünün və ya ZAMYLA və Davin və Gabe adları həyata
yaddaş.
Onlar sözün idi geri geri geri.
Beləliklə, biz mütləq bilməz ki, nə var etibar
burada mənə istifadə üçün mövcuddur.
>> Beləliklə, siz başqa nə ola bilər?
Yaxşı, bir dəfə həyata , ölçüsü yeddi bir sıra lazımdır
Yalnız bir yarada bilər ölçüsü yeddi array sonra istifadə
bir loop və ya bir müddət loop üçün, Yeni array daxil surəti,
və sonra elə yalnız qurtarmaq Bu array və ya yalnız istifadə dayandırmaq.
Amma ki, xüsusilə səmərəli deyil.
Bir sözlə, seriallarda imkan vermir dinamik boyutlandır.
>> Belə ki, bir tərəfdən siz almaq gözəl olan təsadüfi giriş.
Bu imkan verir, çünki us şeyi parçala və fəth kimi,
Biz bütün olan ikili axtarış, burada ekran haqqında danışdı.
Amma bir küncə özünüzü boya.
Kimi tezliklə hit Sizin serialın sonu,
Bir çox nə var bahalı əməliyyat
və kodu bir dəstə yazmaq İndi bu problem ilə məşğul.
>> Belə ki, əvəzinə biz nə bir şey bir siyahısını adlı,
və ya müəyyən bir siyahısını bağlıdır?
Nə əvəzinə olan düzbucaqlı, geri geri geri geri
biz bir az tərk ki, düzbucaqlı var Onların arasında rahat durmamak otaq bit?
Baxmayaraq və bu tərtib etdik şəkil və ya bu şəkil uyğunlaşdırılmış
mətnlərin biri burada geri olmaq geri əslində, çox nizamlı geri,
o düzbucaqlı biri burada yaddaş ola bilər.
Onlardan biri burada ola bilər.
Onlardan biri, burada ola bilər Burada, və s üzərində.
>> Amma biz çəkdi nə varsa bu halda, oxlar
elə bu keçid birlikdə düzbucaqlı?
Həqiqətən, biz texniki gördüm Ox təcəssüm.
Nə biz son istifadə gün, başlıq altında,
Ox nümayəndəsi?
A pointer, sağ?
>> Bəs əgər, əvəzinə yalnız nömrələri saxlanılması,
kimi 9, 17, 22, 26, 34, nə biz saxlanılır əgər
yalnız bir sıra deyil, bir pointer Hər bir belə nömrəsinin yanında?
Belə ki, çox bir mövzu istəyirəm parça bir dəstə vasitəsilə iynə,
elə tying şeyi birlikdə, eyni edə bilərsiniz
göstəricilər kimi biz burada oxlar incarnated,
cür birlikdə toxunuşlu bu fərdi düzbucaqlı
səmərəli bir pointer istifadə edərək, hər bir nömrə yanında olan
ki, bir növbəti sayı göstərir , öz növbəsində, bəzi növbəti sayı göstərir?
Belə ki, başqa sözlə, nə Biz, həqiqətən, istəyirdi
bu kimi bir şey həyata?
Yaxşı təəssüf ki, bu düzbucaqlı, 9 ilə ən azı bir, 17, 22,
və s, bu artıq bir ədəd ilə gözəl meydanların.
Alt, düzbucaqlı 9 aşağıda, məsələn,
nə təmsil olmalıdır bir pointer, 32 bit.
İndi hələ hər hansı bir veri növü xəbərdar deyiləm C ki, siz yalnız bir int verir
lakin bir göstərici cəmi.
>> Biz istəyirik ki, əgər həll nə Bu bizim öz cavab icad?
Bəli?
>> Auditoriya: [işitilemez]
>> DAVID J. MALAN: Bu nədir?
>> Auditoriya: New quruluşu.
>> DAVID J. MALAN: Bəli, niyə belə biz yeni bir quruluş yaratmaq deyil,
və ya C, bir struct?
Biz, əgər qısa əvvəl structs gördüm biz tələbə quruluşu ilə məşğul olduğu
bu kimi bir ad və bir ev idi.
Pset 3 breakout bir bütün istifadə structs-- GRect və GOvals dəstə
Stanford üçün yaradılmışdır ki, birlikdə cluster məlumat.
Belə ki, nə biz bu ideya əgər Açar sözlər "typedef" və "struct,"
və sonra bəzi tələbə xüsusi stuff, və aşağıdakı bu inkişaf:
typedef struct node və node edir bir çox ümumi informatika
bir data strukturu bir şey müddətli, data strukturunda bir konteyner.
Mən iddia A node üçün gedir tamamilə sadə bir int n,
və daha çox cryptically bir az, bu ikinci xətti, struct node * Növbəti.
Amma az texniki şərtlərlə, ikinci line nə
qıvrım aşırma daxilində kod?
Bəli?
>> Auditoriya: [işitilemez]
DAVID J. MALAN: A başqa node göstərici.
Belə ki, etiraf, bir az sirli syntax.
Amma sözün oxumaq əgər, növbəti dəyişən adı.
Onun data növü nədir?
Bu, bu dəfə bir az verbose var lakin bu * növü struct node var.
Biz bir şey ulduz gördüm hər hansı bir zaman ki, ki, data növü bir göstərici var deməkdir.
Belə ki, növbəti yəqin edir bir struct node göstərici.
>> İndi, bir struct node nədir?
Bəli, siz o görmək bildiriş sağ üst eyni sözləri.
Və həqiqətən, siz də sözü Aşağı burada alt sol "node".
Və bu, həqiqətən, yalnız bir rahatlığı var.
Bizim tələbə müəyyən edək ki, yalnız bir dəfə sözü "tələbə" var.
Və bir tələbə, çünki obyekt öz-özünə sened deyildi.
Tələbə daxilində heç bir şey yoxdur ki, bir tələbə üçün qeyd etmək lazımdır,
persay.
Ki, sort olacaq real dünyada qəribə.
>> Amma bir node ilə bağlı siyahısı, biz bir node istəyirəm
oxşar obyekt sened olmaq.
Və belə ki, burada dəyişiklik deyil fark yalnız nə qıvrım aşırma daxilində.
Amma biz "node" sözü əlavə üst habelə
altına əlavə əvəzinə "tələbə".
Və bu yalnız bir texniki detal belə ki, yenidən sizin data strukturu
, öz-özünə sened ola bilər ki, node başqa cür node qeyd edə bilərsiniz.
>> Belə ki, bu son nəticədə nə bizim üçün demək gedir?
Yaxşı, bir, bu stuff daxili bizim node məzmunu edir.
Burada bu şey, top sağ, yalnız belə
ki, yenə biz özümüz müraciət edə bilərsiniz.
Və sonra outermost stuff, node yeni bir müddətli olsa,
bəlkə, hələ var tələbə və nə kimi eyni
SPL başlıq altında idi.
>> Beləliklə, biz indi başlamaq istəyirdi bu bağlı siyahı həyata keçirilməsi,
biz necə tərcümə bilər bu kimi bir şey kod?
Yaxşı, yalnız bir görək bir proqram nümunəsi
həqiqətən bağlı siyahısını istifadə edir.
Bugünkü distribution kodu arasında List Zero adlı bir proqramdır.
Mən bu run əgər və mən bir super yaradılmışdır sadə GUI, qrafik istifadəçi interfeys,
lakin bu, həqiqətən, yalnız printf edir.
Və indi özümü bir neçə menyu təqdim etdik Seçimlər Sil, Insert, Axtarış,
və Traverse.
Və çıxın.
Bu yalnız ümumi əməliyyatlar bir link siyahısı kimi tanınan data strukturu.
>> İndi gedir sil siyahıdan nömrəni silmək.
Daxil əlavə olacaq Siyahıya nömrəsi.
Axtar baxmaq niyyətindədir Siyahıda sayı.
Və traverse bir xülya yoludur deyərək, siyahıda vasitəsilə gəzmək,
çap, lakin bu.
Hər hansı bir şəkildə dəyişiklik yoxdur.
>> Belə ki, bu cəhd edək.
Nin irəli getmək və 2 yazın edək.
Və sonra mən gedirəm sayı daxil, 9 deyirlər.
Daxil edin.
İndi mənim proqram yalnız demək proqramlaşdırılmış siyahısı indi 9.
İndi mən irəli getmək əgər və daha daxil yoxdur, qoy
Mənə irəli getmək və həyata zoom və 17 yazın.
İndi mənim siyahısı sonra, 17 9.
Mən yenə daxil əgər, birinə keçmək bildirin.
Əvəzində 22, şəkil kimi biz Burada baxaraq, mənə irəli jump edək
və növbəti 26 daxil edin.
Mən 26 yazın gedirəm.
I gözləmək kimi siyahısı.
Amma indi, yalnız bu kodu görmek üçün çevik olacaq, indi mənə bildirin
tipli 22 azı konseptual, biz əgər
Bu, həqiqətən olan sıralanır saxlanılması indi başqa qol olacaq,
17 və 26 arasında getməlidir.
Mən Enter düyməsini basın.
Həqiqətən ki, işləyir.
Və indi mənə daxil edək son şəkil 34 per.
>> Bütün hüquqlar.
Belə ki, indi üçün mənə müəyyən edək Sil və Traverse və axtarış edə,
əslində iş.
Mən Axtarış run əgər Əslində, edək daxil edin, sayı 22 üçün axtarış.
Bu 22 tapıldı.
Belə ki, nə bu proqram siyahısı Zero yoxdur.
>> Amma əslində nə gedir ki, bu həyata keçirir?
Bəli, ilk mən, həqiqətən bilər Bir fayl list0.h adlı, var.
Və bu var, haradasa line, typedef struct node,
sonra mən qıvrım aşırma var n int və sonra müəyyən nə struct--?
Struct node növbəti.
Beləliklə, biz ulduz lazımdır.
İndi texniki biz nəzərə almaq burada rəsm vərdiş.
Siz dərsliklər görmək bilər və online istinadlar var bunu.
Bu funksional ekvivalent deyil.
Əslində, bu bir az daha səciyyəvidir.
Amma nə uyğun olacaq Biz keçən dəfə idi və bunu.
Və sonra nəhayət, mən bunu gedirəm.
>> Bir header fayl So haradasa, list0.h da
Bu gün struct müəyyən edir, və bəlkə bəzi digər stuff.
Eyni zamanda list0c var, bir neçə şey olacaq.
Amma biz olacaq yalnız başlamaq və bitirmək deyil.
List0.h istəyirəm fayl Mənim C fayl daxil.
Və sonra bir nöqtədə mən deyiləm əsas, int ləğv etmək niyyətindədir.
Və sonra mən gedirəm to-do bəzi burada var.
Mən də gedirəm prototip, etibarsız, axtarış, int kimi,
n, həyat onun məqsədi bir element axtarmaq üçün.
Və sonra aşağı burada mən iddia bugünkü kodu, etibarsız, axtarış, int, n,
Heç bir nöqtəli vergül açıq qıvrım aşırma.
İndi mən birtəhər axtarış etmək istəyirsinizsə Bu siyahıda bir element üçün.
Amma biz kifayət qədər yoxdur hələ ekranda məlumat.
Mən, həqiqətən, siyahısını özü təmsil etmişdir.
Belə bir yolu biz həyata bilər bir proqram bir bağlı siyahı
I növ bir şey istəyirəm kimi burada siyahısını bağlıdır deyəcəyəm.
Sadəlik üçün, mən gedirəm Bu hətta ümumi biz baxmayaraq, qlobal
Bu çox lazım deyil.
Lakin bu nümunə sadələşdirmək olacaq.
Mən bəyan etmək istəyirəm Burada bir bağlı siyahı up.
İndi, mən necə edə bilərik?
>> Burada bir bağlı siyahı şəkil var.
Mən, həqiqətən, yoxdur necə bu anda bilirsinizmi
Mən haqqında getmək üçün gedirəm yalnız biri ilə çox şey
yaddaş dəyişən.
Amma geri bir an düşünürəm.
Biz etdik bütün bu vaxt strings, sonra biz
Diziler olması aşkar simvol, sonra biz
yalnız bir göstərici ortaya ilk xarakteri
simvol bir sıra ki, null ləğv edir.
Ki məntiq, və bu ilə fikir əkin şəkil cür,
biz, həqiqətən, nə yazmaq lazımdır bizim kodu bir bağlı siyahı təmsil?
Nə qədər bu informasiya biz lazımdır C kodu tutmaq, siz deyəcəksiniz?
Bəli?
>> Auditoriya: Biz bir node bir göstərici lazımdır.
DAVID J. MALAN: a node bir göstərici.
Xüsusilə, olan node sizin ki instinktlərdən bir pointer saxlamaq üçün olacaq?
>> Auditoriya: İlk node.
>> DAVID J. MALAN: Bəli, yəqin ki, yalnız ilk.
Və ilk bildiriş node müxtəlif formalı edir.
Bu struct yalnız yarısı ölçüsü var, çünki həqiqətən yalnız bir göstərici var.
Beləliklə, siz həqiqətən edə bilərsiniz nə bəyan edir bir bağlı siyahı * node olmaq.
Və yalnız ilk zəng edək və null başlamaq.
Belə ki, null, yenə gəlir burada şəkil.
Yalnız null xüsusi kimi istifadə olunur GetString kimi şeylər üçün qaytarılması dəyəri
və malloc, null də sıfır pointer, bir göstərici olmaması,
Siz.
Bu, yalnız heç bir şey hələ burada deməkdir.
İndi ilk mən var bilər bu bir şey deyilən.
I "siyahısı" adlı ola bilər və ya başqa şeylər hər hansı bir sayı.
Amma ki, "ilk" zəng alıram bu şəkil ilə xətləri up.
Belə ki, yalnız bir string kimi təmsil oluna bilər ilk byte ünvanı ilə,
belə bir bağlı siyahı bilərsiniz.
Və biz digər məlumatlar görəcəksiniz strukturları təmsil olunacaq
yalnız bir göstərici ilə, 32-bit arrow işarə
strukturunda ilk node.
>> Amma indi bir problem tahmin imkan verir.
Mən yalnız xatırlayaraq alıram əgər mənim proqram ünvanını
ilk node, ilk Bu data strukturu düzbucaqlı,
daha yaxşı idi əlaqədar işi ola nə Mənim siyahısı istirahət həyata keçirilməsi?
Olacaq ki, əsas ətraflı nədir Bu həqiqətən işləyir təmin etmək üçün?
Və mən "həqiqətən işləyir" çox bir string kimi demək,
us ilk xarakter getmək imkan verir ikinci Davin adı,
üçüncü etmək, dördüncü, çox sonuna,
biz sonunda olduğunuzda biz bilirik nə bu kimi görünür ki, bir bağlı siyahı?
Zaman null var.
Və mən bu cür təmsil etdik elektrik mühəndisi gücü kimi,
kiçik torpaqlama ilə simvolu növ.
Amma yalnız bu halda null deməkdir.
Siz hər hansı bir sayı cəlb edə bilər yolları, lakin bu müəllif
Burada bu simvolu istifadə etmək oldu.
>> Biz stringing etdiyiniz kimi Belə ki, uzun birlikdə bu qovşaqlarının bütün,
yalnız xatırlayaraq ilk, belə uzun
biz xüsusi simvolu qoymaq kimi Siyahıda son node,
ki, çünki biz null istifadə edəcəyik Bizə mövcud nə biz,
Bu siyahı tam deyil.
Və hətta mən yalnız əgər bir pointer vermək ilk element, siz proqramçı,
əlbəttə ki, istirahət edə bilərsiniz.
Amma ağıl edək bir az gezmek,
onlar artıq değilseniz olduqca nə wandered--
çalışan zaman olacaq Bu siyahıda bir şey tapmaq?
Lənətləmək, bu n böyük O, olan ədalət, pis deyil.
Amma bu xətti var.
Biz nə xüsusiyyət verilir daha hərəkət serialların
dinamik bu şəkil doğru birlikdə toxunmuş və ya qovşaqlarının bağlıdır?
Biz təsadüfi giriş imtina etdik.
Bir sıra çünki gözəl riyazi hər şey
geri geri geri geri.
Hətta bu şəkil olsa yaraşıqlı görünür, və hətta
Bu qovşaqlarının kimi görünür olsa qəşəng əslində, ayrı dağıtılır
onlar hər yerdə ola bilər.
OX1, Ox50, ox123, Ox99, bu qovşaqlarının hər yerdə ola bilər.
Malloc yaddaş ayrılması çünki yığın, ancaq hər hansı yığın.
Siz mütləq bu ki, bilmirəm geri olacaq geri geri.
Və reallıq nin bu şəkil olduqca bu olduqca olacaq deyil.
>> Belə ki, bir az almaq olacaq Bu funksiyanı həyata çalışır.
Belə ki, indi axtarış həyata bildirin.
Və biz bir cür görəcəksiniz bunu ağıllı yol.
Mən bir axtarış funksiyası am əgər Belə ki, Mən bir dəyişən, tam n verilən edirəm
axtarmaq üçün, mən bilmək lazımdır içərisində axtarır üçün yeni sintaksis
ki, bir quruluşu , n tapmaq üçün işarə etdi.
Belə ki, bunu edək.
>> Belə ki, ilk mən getmək üçün gedirəm irəli və * node elan.
Mən zəng etmək üçün gedirəm yalnız konvensiya pointer.
Mən ilk onu başlamaq üçün gedirəm.
İndi mən bunu edə bilərsiniz yollarla bir sıra.
Amma ortaq yanaşma gedirəm.
Pointer bərabər deyil isə null ki, qüvvədə olan sintaksis var.
Və yalnız belə, aşağıdakı deməkdir uzun heç işarə deyilik kimi.
Mən nə istəyirəm?
>> Pointer dot n, mənə geri gəlsin ki, bərabərdir nə bərabərdir?
Nə dəyəri I axtarır am?
Keçdi ki, faktiki n.
Belə ki, burada başqa bir xüsusiyyət var C və çox dil.
Hətta struktur adlanır node baxmayaraq dəyəri n, tamamilə qanuni var
Həmçinin yerli arqument var və ya dəyişən n çağırıb.
Hətta biz, çünki insan gözü, ayırd edə
Bu n güman edir ki, Bu n fərqli.
Sintaksis müxtəlif çünki.
Siz bir nöqtə və bir göstərici var, bu bir halbuki belə şey var.
Belə ki, bu yaxşıdır.
Ki, eyni şeyi onlara zəng etmək üçün OK.
>> Mən sizə bu tapa bilərəm, mən deyiləm bir şey etmək istəyirəm olacaq
kimi biz n aşkar ki, elan edir.
Və biz kimi tərk edəcəyik şərh və ya pseudocode kodu.
Else, burada var maraqlı hissəsi, nə
Mən cari node əgər bunu etmək istəyirəm Mən qayğı n olan deyil?
Necə aşağıdakı nail edirsiniz?
Əgər mənim barmaq an Ptr və bu
nə işarə ilk işarə edir
Mən barmaq hərəkət necə kod növbəti node?
Bəli, biz istəyirik hier nə Bu halda izləmək üçün gedir?
Auditoriya: [işitilemez].
DAVID J. MALAN: Bəli, belə gələcək.
Mən geri getmək əgər Belə ki, mənim Burada kodu, həqiqətən, Mən
, göstərici irəli getmək və demək niyyətində olan bu yalnız müvəqqəti dəyişən deyil
bir qəribə adı, Ptr, lakin yalnız temp-- kimi
Mən göstərici müəyyən gedirəm nə pointer That bərabər
və yenə bu olacaq növbəti bir anda nöqtə az arabası.
Başqa sözlə, mən gedirəm mənim Bu node işarə barmaq
burada və mən bilirəm, demək gedirəm nə növbəti sahəsində bir nəzər
və barmaq hərəkət nə bu işarə.
Və bu gedir , təkrar, təkrar təkrar.
Amma zaman mənim barmaq edir heç bir şey bunu dayandırmaq?
Kimi tezliklə hansı kodu kicks line kimi?
Auditoriya: [işitilemez]
DAVID J. MALAN: Əgər point isə pointer null bərabər deyil.
Bir nöqtədə mənim barmaq nin null işarə olacaq
və mən həyata gedirəm bu siyahının sonu var.
İndi, bu bir az Sadəlik üçün ağ yalan.
Belə çıxır ki, baxmayaraq ki, biz yalnız bu dot notation öyrənildi
strukturları üçün, pointer bir struct deyil.
Ptr nədir?
Just daha nitpicky olacaq.
Bu node bir göstərici var.
Bu node özü deyil.
Mən burada heç bir ulduz olsaydı, pointer absolutely-- bir node var.
Bu həftə bir kimi dəyişən elan,
hətta "node" yeni olsa.
>> Amma biz təqdim kimi tezliklə star, indi bir node bir göstərici var.
Və təəssüf ki, siz istifadə edə bilərsiniz bir göstərici üçün dot notation.
Siz arrow istifadə etmək notation olan, şəfəqli,
ilk dəfə hər hansı bir parça sintaksis intuitiv görünür.
Bu sözün bir ox kimi görünür.
Və belə ki, yaxşı bir şey.
Və burada sözün ox kimi görünür.
Belə ki, mən nə la-- hesab Mən burada çox törətməkdə edirəm mən
son yeni parça hesab sintaksis biz görmək olacaq.
Və təşəkkürlə, bu, həqiqətən var bir az daha asan.
>> İndi sizin üçün olan köhnə yol üstünlük bilər,
siz hələ də dot notation istifadə edə bilərsiniz.
Amma ertəsi nin başına söhbət, biz ilk
ki, gedin, orada getmək lazımdır müraciət, və sonra sahəyə daxil.
Belə ki, bu da doğru deyil.
Və səmimi, bu, daha xırdaçı az.
Siz sözün deyərək edirik, dereference göstərici və orada getmək.
Sonra n qamarlamaq sahəsində n çağırıb.
Amma səmimi, heç bir istəyir yazın və ya bu oxumaq.
Və belə ki, dünya icad arrow notation olan
, eyni bərabərdir, yalnız sintaktik şəkər var.
Bu deyərək belə bir xülya yolu daha yaxşı görünür, və ya sadə görünür.
>> Belə ki, indi mən başqa bir şey etmək üçün gedirəm.
Mən var bir dəfə "fasilə" demək gedirəm Bu mən onu axtarır saxlamaq yoxdur tapdı.
Amma bu mahiyyət daşıyır axtarış funksiyası.
Amma bu, bir çox asandır end, kodu vasitəsilə gəzmək deyil.
Bu, həqiqətən, formal həyata keçirilməsi bugünkü distribution kodu axtarış.
Mən insert deyil demək cəsarət vasitəsilə gəzmək üçün xüsusilə əyləncə
vizual, nə də hətta, silmək Günün sonunda olsa
Onlar kifayət qədər aşağı qaynatmaq sadə heuristics.
>> Belə ki, bunu edək.
Burada yumor mənə lazımdır, mən etdim stress top bir dəstə gətirir.
Mən ədəd bir dəstə gətirdi.
Və biz yalnız bir neçə könüllü ala bilər 9, 17, 20, 22, 29 və 34 təmsil?
Belə ki, mahiyyətcə hər kəs olan gün burada var.
Ki, bir, iki, üç oldu dörd, beş, altı nəfər.
Və mən heç görmək go-- xahiş etdik geri bir əllərini qaldırır.
OK, bir, iki, üç, dörd, five-- oxşar altı balance-- yük bildirin.
OK, altı qədər gəlib.
Biz digər insanlar lazımdır.
Biz əlavə stress top gətirdi.
Və siz əgər, üçün yalnız bir an, line
Özünüzü up yalnız burada bu şəkil kimi.
>> Bütün hüquqlar.
Sizin adınız nədir Baxaq?
>> Auditoriya: Andrew.
>> DAVID J. MALAN: Andrew, Siz sayı 9 var.
Görüşmək Nice.
Burada getmək.
Auditoriya: Jen.
DAVID J. MALAN: Jen.
David.
Sayı 17.
Bəli?
>> Auditoriya: Mən Julia edirəm.
>> DAVID J. MALAN: Julia, David.
Sayı 20.
Auditoriya: Christian.
DAVID J. MALAN: Christian, David.
22 nömrəli.
Və?
>> Auditoriya: JP.
DAVID J. MALAN: JP.
29.
Belə ki, oh Uh irəli getmək və in-- almaq.
Oh Uh.
Adi.
20.
Hər kəs bir marker var?
Auditoriya: Mən bir Sharpie var.
DAVID J. MALAN: Siz Sharpie var?
OK.
Və hər kəs bir parça kağız var?
Məruzə edin.
Hadi.
Auditoriya: Biz bunu var.
DAVID J. MALAN: Biz bunu var?
Bütün sağ, təşəkkür edirəm.
Burada biz gedin.
Bu sizin idi?
Siz yalnız gün saxlanılır.
Belə ki, 29.
Bütün hüquqlar.
Mən 29 yanlış, lakin OK.
Durmayın.
Bütün hüquqlar, mən sizə vermək lazımdır Sizin qələm geri anda.
Beləliklə, biz burada bu millət var.
Digər bir var edək.
Gabe, siz oynamaq istəyirəm Burada ilk element?
Biz qeyd etmək lazımdır Bu gözəl insanlar da.
Belə ki, 9, 17, 20, 22, sort 29, sonra 34.
Biz kimsə itirmək mi?
Mən 34 var.
Harada istəyən did-- OK, 34 olacaq?
OK, 34, qədər gəlib.
Bütün hüquqlar, bu olacaq orgasm dəyər.
Sizin adınız nədir?
>> Auditoriya: Peter.
>> DAVID J. MALAN: Peter qədər gəlib.
Bütün hüquqlar, belə ki, burada bir qovşaqlarının bütün dəstə.
Sizlərin hər təmsil Bu düzbucaqlı biri.
Və Gabe, az tək həyata insan, ilk təmsil edir.
Belə ki, onun göstərici bir az kiçik hər kəs çox ekranda.
Və bu halda, sizin hər sol əlləri aşağı qeyd ya gedir
bununla belə, null təmsil yalnız bir göstərici olmaması,
və ya bu işarə olacaq siz yanında bir node.
>> Belə ki, indi siz bəzəmək əgər şəkil kimi özünüzü
Burada, irəli getmək və point Gabe ilə, bir-birinə
xüsusilə işarə edən sayı 9 siyahısını təmsil etmək.
OK, və sayı 34, sol əl yalnız mərtəbəsində işarə etmək lazımdır.
>> OK, belə ki, bu bağlı siyahı deyil.
Belə ki, bu məsələdə ssenarisidir.
Və həqiqətən, bu nümayəndəsi problemlərin sinif
Siz kodu ilə həll etmək üçün cəhd edə bilər ki,.
Siz nəticədə daxil etmək istəyirəm siyahısına yeni element.
Bu halda, biz olacaq sayı 55 daxil edin.
Amma var olacaq müxtəlif hallarda hesab.
Və həqiqətən, bu bir olacaq böyük şəkil burada takeaways deyil,
müxtəlif hallarda nə.
Şərtlər və ya müxtəlif hansılardır proqram ola bilər ki, filial?
>> Yaxşı, sayı çalışdığınız biz 55 olmaq indi bilirik ki insert,
lakin Bildiyiniz olmasaydı əvvəlcədən, I daresay
ən azı üç düşür mümkün hallar.
Bir yeni element ola bilər?
Auditoriya: Və son və ya orta.
DAVID J. MALAN: sonunda da orta, və ya başında.
Mən ən azı var təsdiq üç problem həll etmək lazımdır.
Bəlkə nə seçmək edək arguably sadə
bir, burada yeni element başında məxsusdur.
Mən olduqca kod gedirəm kimi mən yalnız yazdığı, axtarış.
Mən, Ptr üçün gedirəm olan Mən barmaq ilə burada təmsil edəcəyik
adi kimi.
>> Və nə dəyəri xatırlayıram biz Ptr başlamaq idi?
Belə ki, biz əvvəlcə null üçün başlatılmış.
Amma sonra biz biz bir dəfə nə etdi bizim axtarış funksiyası daxilində idi?
Biz, ilk bərabər müəyyən bunu demək deyil.
Mən ilk bərabər Ptr müəyyən varsa, nə Mənim əl həqiqətən işarə olmalıdır?
Right.
Gabe və gedir, əgər belə Burada bərabər dəyərlər olmaq,
biz 9 nömrədə iki nöqtəyə lazımdır.
>> Belə ki, bu, bizim hekayə başlanğıcı idi.
İndi bu, yalnız sadə deyil baxmayaraq sintaksis yeni.
Konseptual bu, yalnız xətti axtarış edir.
9 bərabər 55 edir?
Daha doğrusu, 9 az deyək.
Mən çalışıram, çünki 55 qoymaq üçün harada şekillendirmek.
9 az az 17, az 20-dən az, 22-dən az 29,
az 34, no.
Belə ki, indi biz halda etdiyiniz ən azı üç bir.
>> Mən burada 55 əlavə etmək istəyirsinizsə, sizə nə kodu ehtiyac xətləri həyata almaq?
Necə bu şəkil yoxdur insanlar dəyişdirmək lazımdır?
Mən sol əli ilə nə etməliyəm?
Bu, ilkin null olmalıdır Mən siyahıda sonunda Ben çünki.
Və nə etməlidir Burada Peter, bu idi?
O, açıq-aydın mənə qeyd edəcək.
Mən ən azı iki xətləri var təsdiq Bu gündən etibarən örnek kod kodu
bu həyata olacaq quyruq 55 əlavə ssenari.
Mən kimsə hop ola bilər və yalnız 55 təmsil edir?
Bütün hüquqlar, yeni 55.
>> Belə ki, indi nə növbəti əgər ssenari, birlikdə gəlir
və biz də daxil etmək istəyirəm başlayan və ya bu siyahıdan rəhbəri?
Və adı, nömrəsi 55 nə var?
>> Auditoriya: Jack.
>> DAVID J. MALAN: Jack?
OK, siz cavab gözəl.
Xaricdə xoş gəlmisiniz.
Belə ki, indi biz gedirik demək, sayı 5 daxil edin.
Burada ikinci halda üç, biz əvvəl gündəmə gəldi.
Belə ki, 5 əvvəlində məxsusdur, biz ki, tapmaq necə edək.
Mən Ptr başlamaq daha sayı 9 pointer.
Mən 5-dən az 9, oh, həyata keçirilir.
Belə ki, bizim üçün bu şəkil düzeltmek.
Kimin əlləri, Gabe və ya David Agentliyi or-- sayı 9 adı nədir?
>> Auditoriya: Jen.
>> DAVID J. MALAN: Jen əlləri bizim əlimizdə hansı dəyişdirmək lazımdır?
OK, belə ki, Gabe indi nə işarə?
Mənə.
Mən yeni node edirəm.
Mən hərəkət yalnız cür lazımdır Burada əyani görmək üçün.
Və eyni zamanda nə mən ki, qeyd edirsiniz?
Hələ də mən işarə edirəm.
Belə ki, var.
Kodu düzeltmelerini Belə ki, yalnız həqiqətən bir xətt Bu məsələ, görünür.
Bütün hüquqlar, belə ki, yaxşı.
Və kimsə 5 üçün tutucu ola bilər?
Qədər Hadi.
Biz sizə növbəti dəfə almaq lazımdır.
>> Bütün hüquqlar, belə now-- və Bir kənara, adları kimi
Mən sağ açıq qeyd edən deyiləm indi proqnozu pointer, sələfi pointer
və yeni pointer ki, var yalnız adları verilir
göstəricilər üçün nümunə kodu və ya cür ətrafında işarə ki, mənim əlləri.
Sizin adınız nədir?
>> Auditoriya: Christine.
>> DAVID J. MALAN: Christine.
Xaricdə xoş gəlmisiniz.
Bütün hüquqlar, belə ki, indi hesab edək bir az daha annoying ssenari,
Mən daxil etmək istəyirəm vasitəsi Bu daxil 26 kimi bir şey.
20?
Nə?
Bizim bu qələm yaxşı şey are--.
Bütün sağ, 20.
Kimsə bir parça almaq bilər kağız yalnız bütün sağ iki halda da, hazır.
Oh, maraqlı.
Yaxşı bu bir nümunə mühazirə səhv.
OK, belə ki, adı daha nə var?
Auditoriya: Julia.
DAVID J. MALAN: Julia, siz pop bilər həyata və iddia heç vaxt var idi?
OK, bu baş heç vaxt.
Təşəkkür edirəm.
Beləliklə, biz daxil istəyirəm Güman Bu bağlı siyahı Julia.
O, sayı 20-dir.
Və əlbəttə o var Bu da aid olacaq
begin-- hələ bir şey qeyd etmir.
Belə ki, əl cür ola bilər aşağı null ya bəzi zibil dəyəri.
Nin tez hekayə izah edək.
Mən sayı 5 bu dəfə işarə edirəm.
Sonra 9 yoxlayın.
Sonra 17 yoxlayın.
Sonra 22 yoxlayın.
Mən, ooh, Julia həyata 22 əvvəl getmək lazımdır.
Belə ki, nə baş verməlidir?
Kimin əlləri dəyişdirmək lazımdır?
Julia, mina, or-- adı yenə nə var?
>> Auditoriya: Christian.
>> DAVID J. MALAN: Christian ya?
>> Auditoriya: Andy.
>> DAVID J. MALAN: Andy.
Christian ya Andy?
Andy da qeyd etmək lazımdır?
Julia.
Bütün hüquqlar.
Belə ki, Andy, siz Julia da qeyd etmək istəyirsiniz?
Amma bir dəqiqə gözləyin.
Bu günə qədər hekayə, Mən bir sort deyiləm
mənada məsul ki, pointer olan şey
siyahısına vasitəsilə hərəkət.
Biz Andy üçün bir ad var, lakin bilər Andy adlı dəyişən var.
Biz yalnız digər dəyişən ilk Gabe təmsil edən.
>> Belə ki, bu niyə beləliklə əslində qədər biz bu lazım deyil etdik.
Amma indi ekranda var pred göstərici daha qeyd.
Mənə daha aydın olsun.
Bu göstərici, mən daha yaxşı idi bir az daha ağıllı almaq
Mənim iteration haqqında.
Siz mənim burada keçir ağla deyil yenə burada işarə, burada işarə.
Amma mənə bir pred göstərici edək, sələfi göstərici ki, var
cür işarə element Mən yalnız idi.
Mən burada getmək zaman, indi Mənim sol yenilikləri.
Mən burada sol yenilikləri getmək zaman.
Və indi mən bir pointer yalnız var Julia sonra gedir ki, element,
Mən hələ bir göstərici var Andy əvvəl element.
Belə ki, mahiyyətcə, imkanı var Haritaları, Siz,
zəruri göstəricilər bütün.
>> Mən işarə edirəm əgər belə Andy və mən də işarə edirəm
kimin əlində Xaçpərəst, at indi başqa bir yerdə qeyd edilməlidir?
Andy Belə ki, indi Julia da qeyd edə bilərsiniz.
Julia indi Xaçpərəst qeyd edə bilərsiniz.
O surəti bilər, çünki mənim sağ əl pointer.
Ki, səmərəli sizde geri burada bu yerə.
Belə ki, qısa, hətta bu olsa əbədi cür bizi görür
həqiqətən güncellemek üçün bir siyahısını əlaqəli həyata
Bu əməliyyatlar nisbətən sadədir.
Bu, iki, bir, üç nəticədə kodu xətləri.
Lakin həmin sarılı ehtimalla kodu xətləri
məntiq bir az səmərəli sualına Biz burada soruşur?
Biz başında, orta və ya son?
>> İndi, əlbəttə, bəzi digər var biz həyata bilər əməliyyatları.
Və burada bu şəkillər yalnız təsvir nə biz yalnız insanlar idi.
Nə aradan qaldırılması haqqında?
Mən istəyirəm əgər, məsələn, sayı aradan qaldırılması 34 və ya 55,
Mən kodu eyni cür ola bilər amma bir və ya iki addımlar lazımdır gedirəm.
Yeni nə var, çünki?
Mən sonunda kimsə aradan qaldırılması, sayı kimi 55 sonra 34,
nə də mən bunu kimi dəyişdirmək üçün var?
Mən evict-- deyil var adı yenə nə var?
>> Auditoriya: Jack.
>> DAVID J. MALAN: Jack.
I, evict-- pulsuz Jack yalnız var belə sözün ən azı pulsuz Jack zəng və ya
orada pointer çox, lakin indi Peterlə nə ilə dəyişmək lazımdır?
Onun əl daha aşağı işarə başlayın.
Tezliklə mən pulsuz zəng, çünki Jack, Peter hələ Jack işarə əgər
Mən də traversing saxlamaq siyahısı və giriş bu göstərici,
ki, zaman bizim köhnə dost seqmentasiya var həqiqətən salmaq bilər günah.
Biz təqdim etdik, çünki Jack yaddaş geri.
>> Siz orada qalmaq bilər yöndəmsiz yalnız bir an üçün.
Biz yalnız bir neçə var final əməliyyatları hesab.
Siyahısına rəhbəri aradan qaldırılması, Bu beginning-- və bu, bir və ya
bir az annoying.
Biz bilirik ki, çünki Gabe cür xüsusi bu proqram var.
Çünki həqiqətən, o, öz göstərici var.
O, yalnız qeyd olan deyil Burada demək olar ki, hər kəs kimi.
>> Belə ki, siyahıda başçısı zaman , kimin əlində indi dəyişdirmək lazımdır qaldırıldı?
Adı yenə nədir?
>> Auditoriya: Christine.
>> DAVID J. MALAN: Mən dəhşətli deyiləm adlar da yəqin.
Belə ki, Christine və Gabe, kimin əlində dəyişdirmək lazımdır
biz Christine aradan qaldırılması üçün cəhd zaman, şəkil sayı 5?
OK, belə ki, Gabe edək.
Gabe qeyd edəcək, ehtimalla, sayı 9.
Lakin sonrakı nə lazımdır?
Auditoriya: Christine olmalıdır [Işitilemez] null ola bilər.
DAVID J. MALAN: OK, biz yəqin ki, olmalıdır make-- Mən haradasa "null" eşitdim.
Auditoriya: Null və onun pulsuz.
DAVID J. MALAN: nə null?
Auditoriya: Null və onun pulsuz.
DAVID J. MALAN: Null və onun pulsuz.
Belə ki, bu çox asandır.
Və indi sort edirik ki mükəmməl mənsub yoxdur duran.
Siz oldum, çünki siyahıdan decoupled.
Siz səmərəli oldum siyahıdan yetim.
Və belə ki, biz indi daha yaxşı pulsuz zəng etdi Christine yaddaş geri vermək.
Əks halda biz hər dəfə Siyahıdan bir node silmək
biz siyahısına edilməsi ola bilər qısa, lakin həqiqətən azalmır
yaddaş ölçüsü.
Və belə ki, biz əlavə saxlamaq əgər əlavə, siyahıda şeyi əlavə,
mənim kompüter yavaş əldə edə bilər və yavaş və yavaş,
Mən həyata çalışan edirəm, çünki yaddaş, mən, həqiqətən deyiləm, hətta
Christine bayt istifadə yaddaş artıq.
>> Belə ki, sonunda digər var kursu aradan qaldırılması ssenariləri,
orta, aradan qaldırılması sonunda, kimi gördük.
Amma daha maraqlı problem indi
gedir dəqiq hesab olmaq çalışan zaman nə.
Belə ki, yalnız saxlamaq bilərsiniz kağız parçaları, Gabe, əgər,
verilməsi ağla deyil hər kəs bir stress topu.
Bizim bağlı siyahı çox təşəkkür edirəm Burada könüllü, siz bilər.
>> [Alqış]
>> DAVID J. MALAN: Bütün hüququ.
Analitik belə bir neçə sonra sual, Mən əgər.
Biz əvvəl bu notation gördüm, big O və omega, yuxarı həddi
və aşağı həddi bir alqoritm çalışan zaman.
Belə ki, yalnız hesab edək suallar bir neçə.
>> One, və biz bunu etdi əvvəl, çalışan nə
bir üçün axtarış vaxtı böyük O baxımından siyahısı?
Nə çalışan bir üst bound var bir bağlı siyahı axtarış vaxt
burada könüllülər tərəfindən həyata kimi?
Bu n böyük O, xətti var.
, Ən pis halda, çünki Bu element, 55 kimi,
Biz burada ola bilər axtarır bilər Jack, sonunda bütün yolu idi.
Və təəssüf ki, bir sıra fərqli biz bu dəfə xülya almaq bilməz.
Ekibimizden bütün baxmayaraq Kiçik elementləri, 5 sıralanır,
böyük element qədər bütün yol, 55, adətən yaxşı bir şey.
Amma ki, ehtimal nə artıq bizə imkan?
Auditoriya: [işitilemez]
DAVID J. MALAN: Yenə deyirəm?
Auditoriya: Random access.
DAVID J. MALAN: Random access.
Və öz növbəsində ki, heç biz deməkdir artıq zəif adet sıfır, intuisiya istifadə
ikili istifadə və aşkarlıq axtarış və bölmək və fəth.
Çünki baxmayaraq biz insanlar açıq-aydın ola bilər
Andy və ya xristian idi ki təxminən siyahısı ortasında,
biz yalnız kimi bilirik ki, siyahısını skimming kompüter
əvvəldən.
Belə ki, təsadüfi giriş imtina etdik.
>> N belə böyük O indi yuxarı axtarış vaxt bound.
Nə bizim axtarış omega haqqında?
Aşağı bound axtarış Neler Bu siyahıda bir sıra üçün?
Auditoriya: [işitilemez]
DAVID J. MALAN: Yenə deyirəm?
Auditoriya: One.
DAVID J. MALAN: One.
Belə ki, daimi vaxt.
Ən yaxşı halda, Christine edir həqiqətən siyahısının başında.
Və biz aradığınız sayı 5, belə ki, biz onu tapdım.
Belə ki, heç bir böyük.
Lakin o olmaq var bu halda siyahı başlayan.
Kimi bir şey haqqında nə sil?
Bir element silmək üçün nə istəyirsinizsə?
Nə üst bound və aşağı bound var bağlı bir şey silinməsi haqqında
siyahısı?
Auditoriya: [işitilemez]
DAVID J. MALAN: Yenə deyirəm?
Auditoriya: n.
DAVID J. MALAN: n bound həqiqətən üst.
Ən pis halda, biz cəhd çünki biz yalnız kimi, Jack silmək üçün.
O, sonunda bütün yolu var.
Əbədi bizə edir, və ya n addımlar onu tapmaq üçün.
Belə ki, bir üst bound var.
Əmin, xətti var.
Və ən yaxşı halda zaman çalışan, və ya ən yaxşı halda aşağı həddi
daimi vaxt olacaq.
Bəlkə biz silmək üçün cəhd çünki Christine, və biz yalnız uğurlu almaq
o başında var.
İndi bir dəqiqə gözləyin.
Gabe, başında idi və biz də Gabe yeniləmə idi.
Belə ki, yalnız bir addım idi.
Belə ki, həqiqətən sabit deyil zaman, ən yaxşı halda,
kiçik element aradan qaldırılması üçün necə?
Iki ola bilər, baxmayaraq ki,, deyil kodu üç, və ya hətta 100 xətləri,
Bu eyni sıra əgər bəzi loop xətləri,
və ölçüsü müstəqil siyahısı, tamamilə.
Element at silmə Bu siyahının başında,
biz ilə məşğul olsa belə Gabe, hələ daimi dəfə.
>> Belə ki, bu kimi görünür geri kütləvi addım.
Və hansı bir tullantı , əgər həftə bir və həftə
sıfır biz yalnız idi pseudocode kodu ancaq faktiki kodu
log ki, bir şey həyata baza n, və ya giriş, daha doğrusu, n, baza 2,
onun çalışan zaman baxımından.
Belə ki, heck, biz başlamaq istəyirəm ki, niyə bir bağlı siyahısı kimi bir şey istifadə?
Bəli.
>> Auditoriya: Belə ki, əlavə edə bilərsiniz array elementləri.
DAVID J. MALAN: Belə ki, siz array elementləri əlavə edin.
Və bu çox tematik edir.
Və biz görməyə davam edəcəyik bu, ticarət-off çox
kimi biz gördük bir birləşmə növ ilə ticarət-off.
Biz, həqiqətən, sürətləndirmək bilər daha doğrusu, axtarış və ya çeşidlənməsi,
biz bir az daha çox yer sərf əgər bir yaddaş əlavə yığın var
və ya birləşmə sort üçün bir sıra.
Amma biz daha çox sərf space, lakin biz zaman edin.
Bu halda, biz istəyirik vaxt imtina lakin biz istəyirik
rahatlıq əldə, dinamizm Siz,
olan arguably müsbət xüsusiyyətidir.
>> Biz də yer sərf edirik.
Hansı mənada bir bağlıdır daha bahalı siyahısı
bir sıra daha məkan baxımından?
Harada əlavə yer gələn?
Bəli?
>> Auditoriya: [işitilemez] pointer.
>> DAVID J. MALAN: Bəli, biz də göstərici var.
Belə ki, bu minorly annoying edir ki artıq am
Mən yalnız bir int saxlanılması bir int təmsil etmək.
Mən bir int və saxlanılması alıram də 32 bit olan göstərici.
Mən sözün misli edirəm kosmik məbləği cəlb.
Belə ki, ticarət-off var, lakin ki, int halda var.
Siz int saxlanılması deyilik Tutaq ki, lakin bu düzbucaqlı hər güman
və ya bu insanlar hər təmsil olunub bir söz, İngilis söz
beş simvol, 10 ola bilər simvol, bəlkə də daha çox.
Sonra 32 daha bit əlavə bir böyük az ola bilər.
>> Nə tələbələrin hər əgər nümayişdə
idi sanki tələbə structs ki bəlkə adları və ev var
telefon nömrələri və Twitter emal və kimi.
Belə ki, bütün sahələrində biz başladıq digər gün söhbət,
kimi bir böyük daha az bizim qovşaqlarının daha maraqlı almaq
və böyük, eh, əlavə sərf etmək pointer yalnız onlara birlikdə link.
Amma həqiqətən, ticarət-off var.
And olsun ki, kodu daha mürəkkəb, kimi lazımdır
vasitəsilə skimming baxın xüsusi nümunəsidir.
Amma nə varmış burada bəzi müqəddəs grail.
Biz bir addım, yoxsa nə geri lakin kütləvi addım
və məlumatların həyata strukturu vasitəsilə biz
Jack və ya kimi elementləri tapa bilərsiniz Christine və ya hər hansı digər elementləri
doğru daimi vaxt bu serialın?
Axtar daimi deyil.
Sil sabit deyil.
Daxil daimi deyil.
Bütün bu əməliyyatların daimi var.
Yəni bizim müqəddəs grail olardı.
Ki, burada biz növbəti dəfə aparacaqlar.
Sonra baxın.