DOUG LLOYD: Bütün sağ, sen bu baxımdan belə
yəqin ki, olduqca tanış seriallarda və bağlı siyahıları ilə
iki əsas olan data strukturları biz
dəstləri saxlamaq üçün haqqında danışdı oxşar data növləri data təşkil edib.
>> İndi biz danışmaq olacaq varyasyonları bir neçə haqqında
seriallarda və bağlı siyahıları.
Bu video biz gedirik çıxarıcı borular haqqında danışmaq.
Xüsusilə biz danışmaq olacaq haqqında bir data strukturu bir yığın çağırıb.
Əvvəlki müzakirələrdən geri göstəricilərinə və yaddaş haqqında
yığını də ki, yaddaş seqment üçün ad
statik elan harada bütün yaddaş yaddaş ki,
ad dəyişənlər, ad, və Cetera və funksiyası çərçivəsində həmçinin biz
zəng yığını çərçivəsində mövcuddur.
Belə ki, bu bir yığın data strukturu yaddaş bir yığın seqmenti.
OLDU.
>> Amma bir yığın nədir?
Belə ki, yalnız bir olduqca çox var strukturunun xüsusi növ
ki, bir mütəşəkkil şəkildə məlumat saxlayır.
Və iki çox var ümumi yolları həyata keçirilməsi üçün
iki data strukturları istifadə çıxarıcı borular biz artıq tanış olduğunu,
Diziler və bağlı siyahıları.
Nə bir yığın xüsusi edir biz informasiya qoymaq olan yol
yığını və yol biz daxil yığını informasiya aradan qaldırılması.
Baca ilə xüsusilə qayda yalnız ən çox
son əlavə element çıxarıla bilər.
>> Bu bir yığın var kimi belə bu barədə düşünürəm.
Biz məlumat payavurma edirik özü üst,
üst və yalnız bir şey xovlu çıxarıla bilər.
Biz altında şey aradan qaldırılması bilməz başqa hər şey olardı, çünki
dağılması və üzərində düşür.
Belə ki, biz, həqiqətən, bir yığın qururuq ki, biz sonra parça-parça aradan qaldırılması lazımdır.
Çünki bu, biz çox müraciət bir LIFO strukturu kimi bir yığını,
, ilk out davam.
LIFO, ilk həyata davam.
>> Belə ki, çünki bu məhdudiyyət üzrə məlumat əlavə edə bilərsiniz necə
və bir yığın çıxarılır, həqiqətən var yalnız iki şey biz bir yığın ilə edə bilərsiniz.
Biz olan təkan ola bilər biz əlavə etmək üçün istifadə müddəti
üst yeni element dəstə, ya yığını mövcud deyil
və biz sıfırdan yaratmaq edirik ilk növbədə yığını yaradılması
pushing olacaq.
Və sonra pop ki, CS sort var müddətli biz ən son aradan qaldırılması üçün istifadə
yığını üst element əlavə edib.
>> Beləliklə, biz həm baxmaq olacaq tətbiq, həm array əsaslanır
və bağlı siyahı əsaslanır.
Və biz olacaq based sıra ilə başlayın.
Belə ki, burada əsas ideyası nə array əsasında yığını data strukturu
kimi görünür.
Biz burada bir tipli müəyyən var.
Ki Inside biz iki üzvü var strukturunun və ya sahələri.
Biz bir sıra var.
Və yenə mən istifadə edirəm ixtiyari data type dəyəri.
>> Belə ki, bu, hər hansı bir veri növü ola bilər, int char və ya digər data
Siz əvvəllər yaradılmış yazın.
Beləliklə, biz size gücü bir sıra var.
Capacity bir funt, daimi müəyyən edilir bəlkə başqa bir yerdə bizim fayl.
Belə ki, bu artıq qeyd biz bounding olunur həyata keçirilməsi
özümüzü kimi adətən idi Diziler ilə işi,
biz dinamik ölçüsünü bilməz, burada müəyyən sayda var
elementləri maksimum ki, biz yığını qoymaq bilər.
Bu halda gücü elementləri var.
>> Biz də takip yığını üst.
Ən nədir element Bu yaxınlarda yığını əlavə?
Və belə ki, takip adlı dəyişən üst.
Və bütün bu birlikdə bükülmüş olur bir yığın adlı yeni data növü.
Və biz yaradılmış bir dəfə Bu yeni data type
biz bunu kimi müalicə edə bilər hər hansı digər data type.
Biz kimi, yığını s elan edə bilər biz int x, və ya char y edə bilər.
Və biz yığını demək zaman s, yaxşı nə olar
Biz bir sıra almaq edilir Yaddaş bizim üçün ayrılmış.
>> Bu halda gücü Mən yəqin karar
Mən var, çünki 10 növü yığını bir dəyişən
olan iki sahələri geri edir.
Bu halda bir sıra gedir integers bir sıra olmaq
kimi nümunələri ən haldır.
Başqa bir tam dəyişən üst saxlanılması bilən,
ən son əlavə yığını element.
Belə ki, bir yığın biz yalnız bu kimi görünür müəyyən edilmişdir.
Bu olan bir qutusu var 10 bir sıra nə
bu halda integers olacaq və yaşıl başqa tam dəyişən
yığını üst göstərir.
>> Üst qurmaq üçün yığını biz yalnız s.top deyirlər.
Yəni biz bir daxil necə bir quruluş geri sahəsində.
s.top səmərəli 0 bərabərdir Bizim yığını bu yoxdur.
Belə ki, yenə biz iki əməliyyatları indi edə bilərsiniz ki,.
Biz təkan bilər və biz pop bilər.
Nin təkan ilə başlamaq edək.
Yenə, yeni əlavə olunur basmaqla yığını üst element.
>> Belə ki, nə biz nə etmək lazımdır nə Bu array əsasında həyata keçirilməsi?
Yaxşı General-da push funksiyası gedir
bir qəbul etmək lazımdır yığını göstərici.
İndi ikinci almaq və bu barədə düşünürəm.
Niyə biz qəbul etmək istəyirəm ki, yığını bir göstərici?
Əvvəlki video Recall dəyişən həcmi və göstəricilər,
biz yalnız göndərdi əgər olur nə yığını bir parametri kimi deyil, nədir?
Həqiqətən orada nə qəbul edilə bilər?
Biz bir kopyasını yaratmaq edirik saxla biz bir funksiyası onu keçmək zaman
halda biz göstəricilərinə istifadə.
Və bu funksiya ehtiyaclarını təkan yığını bir pointer qəbul
biz, həqiqətən, dəyişən edirik ki, yığını biz dəyişdirmək niyyətindəyik.
>> başqa şey push yəqin ki, istəyir qəbul növü dəyər bir məlumat elementidir.
Bu halda, yenidən, bir tam ki, biz yığını üst əlavə olacaq.
Belə ki, biz iki parametrləri var.
Biz nə gedir İndi təkan daxilində edirsiniz?
Bəli, sadəcə, biz yalnız əlavə olacaq yığını üst olduğunu element
və sonra burada üst dəyişə yığını ki, üst dəyər nöqtə var edir.
Belə ki, bu nə bir funksiyası var push üçün bəyannamə
bir kimi baxmaq bilər array-based həyata keçirilməsi.
>> Yenə bu bir ağır və sürətli qayda deyil Bu dəyişdirmək və ola bilər ki,
Bu müxtəlif yollarla dəyişir.
Yəqin ki, s qlobal elan edilir.
Və belə ki, hətta ehtiyac yoxdur bir parametr kimi qəbul etmək.
Bu bir daha yalnız bir deyil push üçün ümumi halda.
Və müxtəlif var yolları onu həyata keçirmək üçün.
Lakin bu halda bizim push etmək niyyətindədir
iki dəlilləri, bir yığın bir göstərici və növü dəyərinin tam bir data element
bu halda.
>> Belə ki, biz, s elan s.top 0 bərabərdir bildirib.
İndi təkan imkan yığını üzərinə sayı 28.
Yaxşı ki, nə deməkdir?
Yaxşı hazırda yığını üst 0.
Və nə əsasən baş verəcək
biz sayı qalmaq olacaq Array yeri 0 daxil 28.
Pretty sadə, sağ ki, top idi və indi biz getmək iyi.
Və sonra biz nə dəyişdirmək lazımdır yığını üst olacaq.
Növbəti dəfə Belə ki, biz bir element təkan,
biz onu saxlamaq olacaq array yeri, yəqin ki, 0.
Biz yazmaq istəmirik biz orada nə qoymaq.
Və belə ki, biz yalnız üst 1 hərəkət edəcəyik.
Bu yəqin ki, hissi verir.
>> İndi biz bir element qoymaq istəyirsinizsə yığını üzərinə, biz 33 basmaq istəyirsiniz
Yaxşı indi biz yalnız 33 almaq olacaq və array yeri sıra qoyun
1 və sonra üst dəyişdirmək bizim array yeri sayı iki ola yığın.
Belə ki, növbəti dəfə əgər biz istəyirəm yığını üzərinə bir element təkan,
Bu array yeri 2 qoymaq olacaq.
Və ki, bir dəfə daha nə edək.
Biz çıxarıcı borular off 19 təkan lazımdır.
Biz array yeri 2 19 qoymaq lazımdır və yığını üst dəyişə
array yeri 3 olmaq növbəti dəfə biz əgər
biz getmək iyi təkan etmək lazımdır.
>> OK, belə ki, özetle basmaqla.
Nə yaratma haqqında?
Belə ki, yaratma sort basmaqla həmkarı.
Bu yığını verileri aradan qaldırılması necə.
Ümumiyyətlə pop ehtiyacları aşağıdakı etmək.
Bu bir pointer qəbul etmək lazımdır ümumi halda yenə yığın.
Bəzi digər halda bilər qlobal yığını elan,
bu halda siz onu keçmək üçün ehtiyac yoxdur çünki artıq bu çıxışı var
qlobal dəyişən kimi.
Amma başqa sonra biz nə üçün lazımdır?
Yaxşı incrementing edildi təkan yığını üst,
belə ki, biz yəqin ki, istəyirəm olacaq yığını üst azalma
pop, sağ?
Və sonra əlbəttə biz də istəyirəm olacaq
biz aradan qaldırılması dəyər qayıtmaq üçün.
Biz elementləri əlavə edirsinizsə, biz istəyirik sonra elementləri almaq üçün,
yəqin ki, həqiqətən biz Onlara belə ki, biz saxlamaq istəyirəm
yalnız onları silmeyin yığın və onlara heç bir şey yoxdur.
Ümumiyyətlə, biz əgər basmaqla və yaratma
bu saxlamaq istəyirəm bir mənalı şəkildə məlumat
və belə etmir mənada yalnız imtina.
Belə ki, bu funksiya olmalıdır yəqin ki, bizə bir dəyər qayıtmaq.
>> Belə ki, bu pop üçün nə bir xəbərdarlıq sol üst orada kimi baxmaq bilər.
Bu funksiya qaytarır tipli dəyər data.
Yenə biz istifadə etdik integers ərzində.
Və bir yığını kimi bir pointer qəbul onun yeganə arqument və ya yeganə parametr.
Belə ki, nə pop etmək niyyətindədir?
Biz indi istəyirəm deyirlər s off bir element pop.
Belə ki, bacalar son bildirib ki, unutmayın ilk, LIFO data strukturları, da.
Hansı element gedir yığını çıxarılmalıdır?
Siz 19 tahmin mi?
Doğru olardı, çünki.
19 əlavə son element idi biz elementləri basmaqla zaman yığın,
və belə ki, ilk olacaq xaric olur element.
Bu 28 bildirib kimi, və sonra biz bu üst 33 qoymaq
və biz üst 19 qoydu.
biz off bilər yalnız element 19.
>> İndi burada diaqram mən etdik nə sort array 19 silinir.
Bu, həqiqətən deyil biz nə olacaq.
Biz yalnız cür olacaq o yoxdur iddia.
Bu var hələ də var ki, yaddaş yeri,
lakin biz yalnız ignore olacaq yığını üst dəyişdirərək
2 3 olan.
Biz Belə ki indi təkan yığını üzərinə başqa element,
artıq 19 yazmaq olardı.
>> Amma heç problem ilə gedək yığını 19 silinməsi.
Biz yalnız yoxdur iddia edə bilər.
Yığını məqsədləri üçün əgər getdi biz 2 əvəzinə 3 olmaq üst dəyişir.
Bütün hüquqlar, bu olduqca çox idi.
Yəni biz nə etmək lazımdır bütün var bir element off pop.
Yenidən bunu edək.
Belə ki, burada qırmızı onu qeyd etdik biz başqa zəng edirik göstərir.
Biz eyni şey olacaq.
>> Belə ki, nə baş verəcək?
Bəli, biz saxlamaq olacaq X 33 və gedirik
1 yığını üst dəyişdirmək üçün.
Biz təkan indi olsaydı, belə ki, biz istəyirik yığını daxil element
İndi nə olacaq, nə baş verəcək
biz üzerine olacaq ki, array yeri sayı 1.
Sort qalmışdı ki, 33 Belə ki, ki, arxasında biz yalnız iddia
artıq yoxdur, biz yalnız olacaq onu döymək əvəzinə orada 40 qoymaq.
Və sonra, əlbəttə, biz təkan etdi ildən,
biz arttırmayı olacaq 1 2 dən yığını üst
belə ki, biz indi əlavə ki, başqa element bu lazımdır
array yeri sayı iki daxil.
>> İndi bağlı siyahıları bir var destesi həyata keçirilməsi üçün yol.
Və bu müəyyən əgər ekran, burada sizə tanış görünür
demək olar ki, görünür, çünki bu eyni, əslində,
Bu olduqca çox dəqiq deyil bir story bağlı siyahı kimi eyni,
Siz bizim müzakirə geri əgər story bir video siyahıları bağlıdır.
Burada yalnız məhdudiyyət , proqramçılar kimi bizim üçün
biz icazə deyilik daxil və ya təsadüfi silmək
story bağlı siyahı Daha əvvəl edə bilər.
Biz yalnız indi daxil edin və silə bilərsiniz ön və ya bağlı üst
siyahısı.
Bu, həqiqətən, yalnız var fərq olsa.
Bu başqa bir story bağlı siyahı var.
Bu, yalnız məhdudiyyət var özümüzü əvəz
proqramçılar kimi Bir yığın onu dəyişir.
>> Burada qayda həmişə qorumaq üçün bir bağlı siyahı rəhbəri göstərici.
Bu, əlbəttə, bir ümumiyyətlə ilk əhəmiyyətli qayda.
Story sizə siyahısını halda bağlı üçün yalnız baş bir pointer lazımdır
ki, var üçün zəncir müraciət edə
hər element üçün bağlı siyahı.
Amma xüsusilə var bir yığını ilə əhəmiyyətli.
Və belə ümumiyyətlə sen həqiqətən istəyirəm olacaq
Bu göstərici qlobal dəyişən olacaq.
Bu yəqin ki, olacaq daha asan yol.
Belə ki, təkan və pop analoqu nə var?
Right.
Belə ki, yenə basmaqla əlavə olunur yığını üçün yeni element.
Bir bağlı siyahı ki, biz olacaq deməkdir
biz istəyirik yeni node yaratmaq bağlı siyahısına daxil əlavə etmək üçün gedir,
və sonra ehtiyatlı adımları biz əvvəl qeyd etdik ki,
story bağlı siyahıları onu əlavə etmək zənciri pozmadan zəncir
və itirmək və ya hər hansı bir orphaning bağlı siyahı elementləri.
Və əsasən nə var Mətn az damcı var əks olunur.
Və bir nəzər salaq bir diaqram kimi at.
>> Belə ki, burada bizim bağlı siyahısı.
Bu eyni vaxtda dörd elementləri ehtiva edir.
Və daha çox mükəmməl burada var Dörd elementləri ehtiva yığın.
Və biz indi istəyirəm deyək Bu yığını üzərində yeni bir maddə basın.
Və biz yeni bir təkan istəyirəm kimin data dəyəri maddə 12-dir.
Yaxşı biz gedir nə?
Yaxşı ilk biz olacaq dinamik malloc yer,
yeni node üçün yer ayrılması.
Və əlbəttə dərhal sonra Biz həmişə malloc zəng
, null yoxlamaq üçün əmin olun Biz geri null var, əgər, çünki
Problemin bir növ var idi.
Biz bu null dereference istəmirəm pointer və ya bir seg günah dözəcəyik.
Bu yaxşı deyil.
Beləliklə, biz node malloced etdik.
Biz burada uğur idi etdik güman lazımdır.
Biz daxil 12 qoymaq olacaq ki node data sahəsində.
İndi xatırlayıram yoxdur bizim göstəricilərinə hansı belə ki, biz zəncir qırmaq deyil növbəti hərəkət?
Biz burada variantları bir neçə var, ancaq təhlükəsiz olacaq yalnız bir
göstərici növbəti xəbər müəyyən edir siyahı köhnə baş point
və ya tezliklə olacaq siyahısı köhnə baş.
İndi bütün ki, bizim elementləri birlikdə zəncirlənmiş ki,
biz yalnız qeyd etmək siyahısını hərəkət edə bilər Yeni yoxdur eyni yerə.
Və biz indi səmərəli sövq bir yığını qarşısında üzərinə yeni element.
>> Biz pop yalnız istəyirəm ilk element silin.
Və belə əsasən nə biz burada nə var
biz ikinci element tapmaq lazımdır.
Nəhayət ki, yeni olacaq Biz ilk bir silmək sonra rəhbərlik.
Belə ki, biz yalnız başlamaq lazımdır başlanğıcı, bir irəli hərəkət.
Biz bir bir gözləməyə var sonra biz irəli hazırda
biz təhlükəsiz birinci silə bilər və biz yalnız baş hərəkət edə bilər
nə qeyd etmək Bundan sonra ikinci dövr və
sonra ilk node silinmişdir.
>> Belə ki, yenə, nəzər alaraq bu bir diaqram kimi biz
İndi bir pop istəyirəm Bu yığını off element.
Beləliklə, biz nə etməliyəm?
Yaxşı ilk yaratmaq olacaq olacaq yeni bir pointer
rəhbəri kimi eyni spot qeyd etmək.
Biz onu bir mövqe hərəkət olacaq irəli Trav bərabər deyərək
Məsələn, növbəti Trav olan Trav pointer bir inkişaf edəcəyini
irəli mövqe.
İndi biz var ki, ilk element keçirilməsi
pointer çağırıb siyahısı, vasitəsilə adlı göstərici ilə ikinci element
Trav, biz təhlükəsiz ki silə bilərsiniz yığını ilk element
qalan itirmədən zəncirinin Çünki biz
müraciət üçün bir yol var İkinci element
yolu ilə irəli pointer Trav çağırıb.
>> Belə ki, indi ki, node azad edə bilər.
Biz siyahısı azad edə bilər.
Və sonra biz indi nə etmək lazımdır bütün edir eyni yerə nöqtəyə siyahısı hərəkət
ki Trav edir və biz geri sort istəyirik Biz 12 sövq əvvəl biz başladı
ilk növbədə, sağ.
Biz bu dəqiq deyil.
Biz bu dörd element yığını idi.
Biz beşinci əlavə edib.
Biz beşinci basdı element, və sonra
atdı ki, ən son geri off element əlavə edib.
>> Olduqca çox həqiqətən bütün çıxarıcı borular var.
Siz seriallarda kimi həyata keçirə bilər.
Siz bağlı siyahıları kimi həyata keçirə bilər.
Digər, əlbəttə, var yolları, eləcə də onların həyata keçirilməsi üçün.
Biz istifadə ki, əsasən səbəbi çıxarıcı borular, belə bir şəkildə məlumat saxlamaq üçün
ən son əlavə edib ki, element, biz istəyirik ilk şey
geri almaq istəyirəm olacaq.
Mən Doug Lloyd deyiləm, bu CS50 edir.