[MÜZİK OYUN]
DAVID J. MALAN: Pekala.
Bu CS50 olduğunu.
Bu hafta beş devam ve biz bazı iyi haberler ve kötü haberlerim var.
Çok iyi bir haber olduğunu CS50 olduğunu Bu Cuma başlattı.
Bize katılmak isterseniz, Burada her zamanki URL baş.
Hatta daha iyi bir haber, herhangi bir ders Bu 13 Pazartesi geliyor.
Biraz daha az iyi haber, Quiz sıfır önümüzdeki Çarşamba.
Daha fazla detay olabilir Burada bu URL adresinde bulunamadı.
Ve önümüzdeki birkaç gün içinde Biz boşlukları doldurarak olacak
oda getirmedi biz aittir olacağı.
Daha iyi haberler var olacak ki Bir ders çapında yorum olacak
oturumu bu geliyor Akşam Pazartesi.
Elbette en Bizi izlemeye devam edin konumu ve detaylar için web sitesi.
Bu halde Kesitler, tatil, aynı zamanda buluşacak.
En iyi haber, bir sonraki Cuma ders.
Yani bu bir gelenek olduğunu biz ders başına sahiptir.
Sadece-- şaşırtıcı olacak.
Sen gibi şeyler göreceksiniz Sabit zamanlı veri yapıları
ve hash tabloları ve ağaçlar ve çalışır.
Ve biz doğum günü sorunları hakkında konuşacağım.
Şeyler bir sürü Bir sonraki Cuma bekliyor.
TAMAM MI.
Her neyse.
>> Bu yüzden oldum hatırlamak ne bu resim üzerinde duruluyor
bizim bilgisayarın belleğinin içinde.
Yani bellek veya RAM nerede programlar Onları koşarken var.
Eğer bir çift tıklarsanız simge bazı programı çalıştırmak için
ya da çift tıklayın Bazı dosyayı açmak için simgesini,
Bu sabit yüklenen oluyor sürücü veya katı hal sürücüsü
RAM, Random Access Memory, içine kapanana kadar o yaşıyor
dizüstü kapağı, kapatır veya programdan çıkın.
>> Şimdi bu bellek, bir hangi muhtemelen
1 gigabayt bu gün, 2 gigabayt, hatta çok daha fazla,
genellikle ortaya koydu belirli bir program için
dikdörtgen Bu tür kavramsal model
Biz alt yığını var sayede ve üstündeki diğer şeyler bir demet.
çok üstünde bir şey Bu resimde gördüm
daha önce ama asla hakkında konuştuk olarak adlandırılan kısa bölümdür.
Metin segmenti sadece bir fantezi yoludur sıfırları ve olanları söyleyerek bu
Gerçek derlenmiş programı oluşturmak.
>> Peki ne zaman çift tıklayın Mac veya PC Microsoft Word,
Eğer nokta çalıştırdığınızda veya bir üzerinde Mario çizgi Terminal penceresinde Linux bilgisayar,
oluşturan sıfır ve olanlar Word veya Mario geçici olarak depolandığı
sözde bilgisayarınızın RAM içinde Belirli bir program için metin parçası.
Gider Aşağıda başlatıldı ve başlatılmamış verileri.
Bu global değişkenler gibi şeyler, Biz birçok kullanılmaz olduğuna göre,
ama vesileyle biz ettik Küresel değişkenler vardı
veya statik dizeleri tanımlanan sert "merhaba" gibi kelimeler kodlanmıştır
kullanıcıdan alınan olmadığını senin programına sabit kodlanmıştır.
>> Şimdi, aşağı alt biz Sözde yığını.
Ve yığın, bugüne kadar, biz oldum amaçları ne tür kullanarak?
Yığın ne için kullanılır oldu?
Evet?
>> İZLEYİCİ: Fonksiyonlar.
>> DAVID J. MALAN: fonksiyonlar için?
Fonksiyonlar için hangi anlamda?
>> İZLEYİCİ: Bir işlevini çağırdığınızda, argümanlar yığının üzerine kopyalandı.
>> DAVID J. MALAN: Kesinlikle.
Eğer bir işlev çağrısı zaman, argümanlar yığının üzerine kopyalandı.
Yani herhangi bir X veya Y en en ya da A veya B en en Eğer bir işlev geçen olduğunuzu
geçici konur Sözde yığını,
Sadece Annenberg biri gibi yemekhane tepsileri ve ayrıca şeyler
Yerel değişkenler gibi.
Eğer foo işlevi ya da takas işlevi, yerel değişkenler var,
temp gibi, bu iki yığını üzerinde sonuna kadar.
Şimdi, biz hakkında çok fazla konuşmak olmaz Onları, ancak bu ortam değişkenleri
altındaki bir süre önce ne gördüm Ben klavyeden bir gün futzing oldu
ve ben bir şeyler erişen başladı argv 100 veya argv 1000 gibi,
Sadece öğelerin-- unutuyorum Numaraları ancak
Bana tarafından erişilebilir olması gerekiyordu.
Biz bazı görmeye başladı Ekranda korkak sembolleri.
Bu sözde edildi ortam değişkenleri
küresel ayarları gibi benim Program ya da benim bilgisayar, değil
Son ilgisi Konuştuğumuz hata,
Shellshock bu oldu Epeyce bilgisayar başına bela.
>> Şimdi son olarak, bugünün odak biz sonuçta öbek üzerinde olacak.
Bu belleğin bir başka yığınıdır.
Ve temelde bütün bu Bellek aynı şeyler.
Aynı donanım var.
Biz tür sadece konum Farklı kümeleri tedavi
Farklı amaçlar için bayt.
yığın da nereye olacak Eğer talep değişkenleri ve bellek
işletim sisteminden geçici olarak depolanır.
>> Ama bir problem tür var Burada, resim anlaşılacağı gibi.
Biz tür iki tane hakkında gemileri çarpışmak.
Eğer daha fazla kullanmak gibi çünkü bugün gördüğümüz yığının, gibi
itibaren, Eğer daha fazla kullanmak gibi Yığın, kesinlikle kötü şeyler olabilir.
Ve gerçekten de, biz o neden olabilir kasıtlı veya kasıtsız.
Geçen çekişme Yani Zaman bu program oldu,
herhangi bir fonksiyonel hizmet etmedi hangi göstermek için başka amacı
nasıl bir kötü adam aslında alabilir gibi Birinin programında hataların avantajı
ve hatta bir bir program veya devralmaya Tüm bilgisayar sistemi veya sunucu.
Yani sadece bakışta kısaca, seni altındaki bu main fark
Komut satırında alır argv göre argümanlar.
Ve bir fonksiyon f bir çağrı var, aslında isimsiz bir fonksiyonu olarak adlandırılır
f ve argv geçen var [1].
At >> Yani ne olursa olsun kelime kullanıcı türleri Bu programın adından sonra istemi,
ve daha sonra bu keyfi işlevi kadar üst, f, bir dize alır, AKA karakter *,
tartışmak başladık gibi, ve sadece "bar" diyor.
Ama biz bir şey diyebiliriz.
Ve o zaman içinde, beyan f, karakter dizisinin
12 tür karakterler C- çağırdı.
>> Şimdi, hikaye ben anlatıyordum Bir an önce, nerede bellekte
c, ya da bu 12 vardır sonuna kadar gidiyor karekter olmalı?
Sadece temiz olması için.
Evet?
>> İZLEYİCİ: yığını üzerinde.
>> DAVID J. MALAN: yığını üzerinde.
Yani c yerel bir değişkendir.
Biz 12 karakter veya 12 bayt için soruyorsun.
Bu sonuna kadar gidiyoruz Sözde yığını üzerinde.
Şimdi nihayet bu diğer işlevi Bu, aslında oldukça yararlıdır
ama biz gerçekten kullanılan ettik kendimizi, strncopy.
Bu, dize kopyasını anlamına gelir ama sadece harf, n karakterleri n tane.
Yani n karakter olacak c içine bardan kopyalandı.
Ve kaç?
çubuğunun uzunluğu.
Bu yüzden, diğer bir deyişle, bu bir satır, strncopy,
kopyalamak için gidiyor etkin bir c için bar.
>> Şimdi, sadece tür tahmin Bu hikayenin ahlaki,
ne burada potansiyel sorunlu?
Biz uzunluğu kontrol ediyoruz olsa çubuğunun ve strncopy içine geçen,
ne gut sen anlatıyor hala bu program hakkında kırıldı?
Evet?
>> İZLEYİCİ: içermez null karakteri için oda.
DAVID J. MALAN: içermez null karakteri için oda.
Potansiyel olarak, farklı Geçtiğimiz uygulama bile yok
sahip bir artı 1 olarak çok daha O null karakteri ağırlayacak.
Ama daha da kötüsü var.
Başka ne yapmamız için başarısız?
Evet?
>> İZLEYİCİ: [Duyulmaz]
DAVID J. MALAN: Mükemmel.
Biz zor oldukça keyfi 12 kodlu ettik.
Bu çok fazla değil Sorun, ama aslında
biz bile olmadığını kontrol değiliz çubuğunun uzunluğu, en az 12 olan
bu durumda olacak belleğe koymak için güvenli
biz tahsis ettik denilen c.
Nitekim, bar gibi eğer Uzun 20 karakter,
Bu fonksiyon kopyalama gibi görünüyor Böylece c içine bar, 20 karakter
En az 8 byte alarak olması gerektiğini söyledi.
Burada ima var.
>> Yani kısa, kırık programda.
Büyük bir anlaşma gibi değil.
Belki bir segment hataya olsun.
Biz tüm programlarda hata yaşadım.
Hepimiz hata olabilir Şu anda programlarda.
Ama ima ne?
Peki, burada bir uzaklaştırdınız-sürüm var Benim bilgisayarın belleğinden bu resmi.
Bu benim yığının altına.
Ve gerçekten de, çok altında ne olduğunu denilen ana rutin yığını, fantezi yolu
o ana söyleyerek.
Fonksiyonu olarak adlandırılır kim Böylece Bahsettiğimiz f.
Yani bu yığının alt olduğunu.
İade adresi yeni bir şey.
Her zaman, orada oldu hep resimde olmuştur.
Biz buna dikkat çekti sadece asla.
Çıkıyor, çünkü c çalışır yoludur bir fonksiyonun bir başka çağırdığında o,
Sadece bu da değil argümanlar yapmak Fonksiyon yığını üzerine itti olsun,
sadece işlevi yerel yapmak değişkenler yığını itti olsun,
bir şey geri dönüş adresi olarak adlandırılır Ayrıca yığının üzerine koymak olur.
Özellikle, ana aramalar foo eğer, ana en bellekte kendi adres, öküz bir şey,
etkin bir yığının üzerine koymak alır Böylece f bunu yürütme yapılır zaman
Metinde geri atlamak için nerede biliyor çalıştırmaya devam etmek için segment.
>> Kavramsal buradayız Yani, main, daha sonra f çağrılır.
F biliyor nasıl kim geri el kontrolü?
Peki, bu küçük Burada kırmızı kırıntı,
dönüş adresi olarak adlandırılan, sadece kontroller, bu dönüş adresi nedir?
Ah, beni buraya geri ana atlamak verelim.
Ve bu biraz var Bir tefrit,
sıfır ve olanlar nedeniyle main için teknik olarak
Burada teknoloji segmentinde kadar.
Ama bu fikir. f Sadece ne bilmek zorunda
Nerede kontrol sonuçta geri gider.
>> Ama yol bilgisayarları Uzun şeyler koydu
Yerel değişkenler gibi ve argümanlar bu gibi.
Bu resmin üst Yani mavi yüzden tüm f yığın çerçevesi
belleğin o f Özellikle kullanıyor.
Dolayısıyla buna göre, fark bar Bu resimde olduğunu.
Bar argümanı oldu.
Ve biz iddia argümanlar bu fonksiyonlar yığını itti olsun.
Ve C, tabii ki, Ayrıca bu resimde.
>> Ve sadece işaretler amaçlar için, sol üst köşesindeki fark
braket 0 c ne olurdu ve sonra biraz sağa aşağı
c dirseği 11 olduğunu.
Yani diğer bir deyişle, hayal edebilirsiniz bayt bir ızgara var olduğunu
Orada, bunlardan birincisi Sol üst, alt hangi
Bu 12 bayt sonuncusu.
>> Ama şimdi ileri sarmak için deneyin.
Ne geçerse ne hakkında olduğunu c daha uzun olan bir dize bar?
Ve biz eğer kontrol değil gerçekten uzun 12'den var.
Bu resmin hangi bölümü gidiyor bayt 0, 1, 2, 3 ile yazılır olsun,
dot dot dot, 11, ve sonra Kötü, 12, 19 ile 13?
Ne, burada ne olacak Eğer sipariş gelen sonucuna eğer
Bu c dirsek 0 üstte c dirsek 11 aşağı tür
Doğru mu?
Evet?
>> İZLEYİCİ: Peki, o gidiyor char * çubuğunu üzerine yazmak.
>> DAVID J. MALAN: Evet, bu gibi görünüyor Eğer char * çubuğunu üzerine gidiyoruz.
Ve daha da kötüsü, sen gerçekten uzun gönderirseniz dize, hatta ne üzerine olabilir?
dönüş adresi.
Hangi yine sadece gibi Programı nerede anlatmak için kırıntı
ne zaman f dönmek için çağrıldığını yapılır.
>> Kötü adamlar genellikle yapmak Peki Onlar bir program rastlamak eğer olduğunu
onlar olup olmadığını merak olduğunuzu Böyle bir şekilde işletilebilir, hatalı
o alabilir Bu hata avantajı,
genelde alamadım Bu ilk seferde doğru.
Onlar sadece, örneğin, gönderme işlemini başlatmak, Programınızın içine rastgele dizeleri,
Klavyenin olsun, ya açıkçası onlar muhtemelen
küçük bir program yazmak, sadece otomatik dizeleri oluşturmak,
ve tarafından programa beceriyor başlamak Farklı girdilerin sürü gönderme
Farklı uzunluklarda.
>> En kısa sürede program çöker gibi, Bu inanılmaz bir şey.
O he anlamına gelir, çünkü ya da o keşfetti
Ne gerçekten muhtemelen bir hata olduğunu.
Ve sonra onlar daha akıllı alabilirsiniz ve başlangıç ​​daha dar odaklama
Bu hata yararlanmak için nasıl.
Özellikle, ne o olabilir yapmak merhaba, iyi durumda, gönderilir.
Hayır büyük dağıtmak.
Bu yeterince kısa olan bir dize var.
Ama ne o gönderirse, ve biz bunu gibi genelleme edeceğiz
Saldırı sıfır yüzden code-- ve bu olanları şeyler
rm-rf gibi, her şeyi kaldırmak Sabit diskten ya da spam göndermek
ya da bir şekilde makineyi saldırı?
>> Bunların her biri Yani eğer harfler bir, sadece, temsil
kavramsal, saldırı, saldırı, saldırı, saldırı, bazı kötü kod
başkası yazdı, ama o kişi yeterince akıllı ise
sadece tüm içerir Bu rm-RFS değil, aynı zamanda
onun son birkaç bayt karşılık gelen bir sayı olmak
adresine onun veya kendi saldırı kodu
o sadece geçti isteminde bunu sağlayarak,
Eğer etkili bir bilgisayarı kandırmak olabilir f yürütme bittiğinde fark içine,
oh, beni atlamak için zamanı geri dönüş kırmızı adresine.
Ama o şekilde çünkü Bu geri dönüş adresi çakışan
Kendi numarası ile, ve onlar kadar zekisin
Bu yapılandırılmış olması sayı senin gibi, başvurmak için
Süper üst görmek Orada sol köşesi,
Bilgisayar yıllarda gerçek adresi onların saldırı bazı kod bellek,
Bir kötü adam bilgisayar kandırmak olabilir kendi kod yürütme içine.
>> Ve bu kod, yine her şey olabilir.
Genel olarak adlandırılır sadece bir kabuk kodu,
öyle değil diyerek bir yolu rm-rf gibi basit genel bir şey.
Bu, aslında Bash gibi bir şey var ya da gerçek bir program onu ​​verir
ya da onu programatik kontrol yürütmek için Onlar istediğiniz başka bir şey.
Yani kısacası, bu bütün Basit gerçeğinden kaynaklanmaktadır
katılan bu hata kontrol değil senin dizinin sınırları.
Ve bu arada, çünkü bilgisayarlar eseri olduğunu onlar
gelen yığını kullanmak etkin bir şekilde, kavramsal olarak,
up alt, ama sonra elemanlar Eğer, yukarıdan aşağı büyümek yığına itin
Bu inanılmaz sorunlu.
Şimdi, bu geçici bir çözüm yolları vardır.
Ve açıkçası, dilleri vardır hangi Bu sorunu gidermek için.
Java, örneğin, bağışıklık Bu özel konuya.
Onlar işaretçiler vermeyin çünkü.
Onlar vermeyin doğrudan bellek adresleri.
Elimizdeki bu güçle Yani bellekte şey dokunmak
Biz kuşkusuz, büyük bir risk, gelir istiyorum.
>> Yani bir göz tutmak.
Açıkçası, varsa, ay veya yıllar zaman, gelecek
Bazı sömürü hakkında okuyun Bir program veya bir sunucu,
Hiç bir şey bir ipucu görürseniz Bir tampon taşması saldırısı gibi,
veya yığın taşması başka türüdür saldırı, ruhu benzer,
Web sitesi en ilham kadar Eğer biliyorsanız, isim,
hepsi sadece bahsediyor Bazı karakter boyutunu taşan
Dizi ya da daha genel bir dizi.
Bu daha sonra herhangi bir soru,?
Evde denemeyin yok.
>> Tamam.
Yani malloc bugüne kadar bizim yeni olmuştur Biz bellek ayırabilir ki arkadaş
biz mutlaka içinde bilmiyoruz bu yüzden biz yok istediğiniz ilerlemek
içine sert kod bizim 12 benzeri bir program numaraları.
Kullanıcı bize ne kadar söyler kez o girişine istediği veri,
biz bu kadar bellek malloc edebilirsiniz.
>> Yani için, çıkıyor malloc biz bunu kullanıyorum ölçüde,
açıkça son kez, ve sonra Siz bunu kullanıyorum
için bilmeden getString için Birkaç hafta MALLOC belleğinin her
Sözde yığın gelir.
Bu, örneğin, bu yüzden getString olan dinamik bellek tahsis edebilirsiniz
sen bilmeden önceden yazdığınız olacak,
Bu belleğe geri bir işaretçi sizi el, ve bu bellek sizindir tutmak hala,
Hatta döner getString sonra.
Çünkü hatırlama sonra tüm Yığın sürekli yukarı ve aşağı gidiyor
yukarı ve aşağı.
Ve kısa sürede gider aşağı, herhangi bir bellek anlamına gelir
kullanılan bu fonksiyon gerekir başkası tarafından kullanılmamalıdır.
Şimdi çöp değerleri var.
>> Ama yığın burada olduğunu.
Ve malloc olduğunu hakkında güzel ne malloc burada bellek ayırır,
ne için, gömülü değil yığını tarafından büyük bir bölümü,.
Ve böylece herhangi bir işlev erişebilirsiniz malloc'd edilmiş belleği
Hatta getString gibi bir işlev tarafından, Hatta sonra iade edilir.
>> Şimdi, malloc converse ücretsizdir.
Ve gerçekten de, kural size benimseyerek başlamak gerekir
herhangi herhangi malloc kullanmak her zaman olduğu Kendinizi, sonunda, serbest kullanmanız gerekir
Aynı işaretçi.
Biz yazılı olan tüm bu zaman buggy, birçok nedenden dolayı adamcağız kodu.
Ama biri olmuştur CS50 kütüphanesi kullanarak hangi
kendisi kasıtlı olduğunu buggy, bu bellek sızdırıyor.
Eğer getString aradım her zaman Son birkaç hafta içinde
Biz işletme soruyorsun Sistem, Linux, bellek.
Ve bir kez geri verilen asla.
Ve bu değildir, , iyi bir şey pratik.
>> Ve Valgrind, bir PSET 4 tanıtılan araçlar,
size yardımcı tüm ilgili Şimdi böyle hata bulmak.
Ama neyse ki PSET 4 için sana ihtiyacım yok CS50 kitaplık veya GetString kullanımı.
Yani hafıza ile ilgili herhangi bir hata vardır sonuçta kendi olacak.
>> Yani malloc sadece daha fazla Bu amaç için uygun.
Biz aslında şimdi çözebilir temelde farklı sorunlar,
ve temelde daha sorunları çözmek etkin bir hafta Zero'nun vaadi başına.
Şimdiye kadar bu seksi olduğunu veri yapısı biz aldık.
Ve veri yapısı ile sadece demek kavramsallaştırma bir bellek yolu
Sadece söyleyerek ötesinde bir şekilde, bu bir karakter olduğunu, bir int.
Birlikte küme şeyler başlayabilirsiniz.
>> Peki, bir dizi bu gibi görünüyordu.
Ve yaklaşık bir anahtar ne oldu dizi size vermesidir
back-to-back topakları Bellek, her biri
aynı tip olacak, int, int, int, int, ya da karakter, karakter, karakter,
karakter.
Ama bir kaç olumsuz yanları var.
Bu, örneğin, bir boyut altı bir dizi.
Eğer altı ile bu dizi doldurmak varsayalım sayıları ve daha sonra, herhangi bir nedenle,
Kullanıcı vermek istiyor Eğer yedinci sayısı.
Nereye koymak mı?
Eğer varsa >> çözüm nedir yığını üzerinde bir dizi yarattı,
Örneğin, sadece hafta Biz tanıttı iki gösterim,
içinde bir dizi köşeli parantez içinde?
Peki, altı var Bu kutulara numaralar.
Içgüdülerin ne olurdu?
Nereye koymak istersiniz?
>> İZLEYİCİ: [Duyulmaz]
>> DAVID J. MALAN: Üzgünüm?
>> İZLEYİCİ: ucunda koyun.
>> DAVID J. MALAN: ucunda koyun.
Yani sadece sağ üzerinde, Bu kutunun dışında.
Hangi güzel, ama o olur Bunu yapamam çıkıyor.
Sormadınız ettik Çünkü eğer bellek bu parça için,
Bu bir tesadüf olabilir diğer bazı değişken tarafından kullanılıyor
tamamen.
Biz koydu bu yüzden bir hafta geri düşünün veya Zamyla ve Davin ve Gabe isimleri dışında
bellekte.
Onlar kelimenin tam anlamıyla arka arkaya arkaya.
Bu yüzden mutlaka olamaz Bu ne 's güven
Burada beni kullanmak için kullanılabilir.
>> Peki başka ne olabilir?
Peki, bir kez gerçekleştirilmesi boyut yedi bir dizi gerekir
Eğer sadece bir yaratabileceği büyüklüğü yedi dizi daha sonra kullanmak
Bir döngü veya bir while döngüsü için, Yeni diziye kopyalamak,
ve sonra bir şekilde sadece kurtulmak Bu dizi ya da sadece kullanmayı bırakın.
Ama bu özellikle verimli değil.
Kısacası, diziler izin vermeyin dinamik yeniden boyutlandırmak.
>> Olsun bir yandan Yani şaşırtıcı rasgele erişim.
O izin Çünkü bize şeyler yapmak böl ve yönet gibi,
biz ettik hepsi ikili arama, Burada ekranda konuştuk.
Ama bir köşeye kendin boya.
En kısa sürede size vurmak gibi senin dizinin sonu,
Eğer çok yapmak zorunda pahalı bir işlemdir
veya kod bir sürü bilgileri Şimdi bu sorunla başa çıkmak için.
>> Bunun yerine biz ne vardı bir şey bir liste olarak adlandırılan,
veya belirli bir listeyi bağlı?
Ne olursa yerine sahip dikdörtgenler, geri geri geri
Biz biraz bırakın dikdörtgenler var Bunların arasında kıpırdatmak oda biraz?
Olsa bile Ve ben bu boğuldum resim veya bu resmi adapte
Metinlerin birinden burada geri olmak geri gerçekte, çok düzenli geri,
Bu dikdörtgenler biri buraya bellekte olabilir.
Bunlardan biri burada olabilir.
Bunlardan biri, burada olabilir Burada ve benzeri üzerinde.
>> Ama ne çekti ise, Bu durumda, oklar
her nasılsa bu bağlantı olduğunu Birlikte dikdörtgenler?
Nitekim, biz bir teknik gördüm Bir ok vücut bulma.
Ne son olarak kullanmış gün ki, kaputun altında,
Bir ok temsili?
Bir gösterici, değil mi?
>> Peki ne varsa, yerine Sadece sayıları saklamak,
gibi 9, 17, 22, 26, 34, Ne biz saklandığı takdirde
Sadece bir sayı değil bir işaretçi Her tür numaranın yanındaki?
Yani o kadar bir iplik olacak gibi kumaş sürü ile iğne,
nasılsa bağlama şeyler Birlikte, benzer olabilir
işaretçiler olarak biz Burada oklarla enkarne,
tür birlikte örgü Bu bireysel dikdörtgenler
etkin bir şekilde işaretçi kullanarak Her numaranın yanındaki o
Bu, bazı sonraki sayıya işaret da, bazı sonraki sayı işaret?
Bu yüzden, diğer bir deyişle, hangi biz aslında isteseydi
Böyle bir şey uygulamak?
Peki ne yazık ki, bu dikdörtgenler, 9 ile en az bir, 17, 22 ile,
ve benzeri, bu artık Tek sayılar ile güzel kareler.
alt, dikdörtgen 9'un altında, örneğin,
neyi temsil gerekir Bir gösterici, 32 bit olmak.
Şimdi, ben henüz herhangi bir veri türü farkında değilim C ki size sadece bir int verir
ama bir işaretçi tamamen.
İstersek >> Peki çözüm ne Bu bizim kendi cevap icat?
Evet?
>> İZLEYİCİ: [Duyulmaz]
>> DAVID J. MALAN: Bu nedir?
>> İZLEYİCİ: Yeni yapı.
>> DAVID J. MALAN: Evet, öyleyse neden yeni bir yapı oluşturmak değil,
veya C, bir yapı içinde?
Biz, eğer kısaca, daha önce yapılar gördüm Biz öğrenci yapısı ile ele nerede
Bu gibi bir adı ve bir ev vardı kim.
PSET 3 koparma bir bütün kullanılan structs-- GRect ve GOvals demet
Stanford için oluşturulan Birlikte küme bilgiler.
Peki biz bu aynı fikri alırsak anahtar kelimeler "typedef" ve "yapı"
ve daha sonra bazı öğrenci özgü şeyler, ve aşağıdaki içine bu gelişmeye:
TypeDef yapı node-- ve düğüm sadece çok genel bilgisayar bilimi
Bir veri yapısı içinde bir şey için terim, bir veri yapısı içinde bir kap.
Ben iddia Bir düğüm sahip oluyor Tamamen basit bir int n,
ve daha sonra cryptically biraz, Bu ikinci hat, struct düğümü * yanında.
Ama daha az teknik açıdan, ikinci çizgi nedir
küme parantezi içindeki kod?
Evet?
>> İZLEYİCİ: [Duyulmaz]
David J. MALAN A başka bir düğüme işaretçisi.
Yani kuşkusuz, biraz şifreli sözdizimi.
Ama tam anlamıyla okursanız, yanındaki bir değişken adıdır.
Veri türü nedir?
Bu, bu sefer biraz ayrıntılı var ancak * struct düğümün var.
Biz bir şey yıldızı gördüm Her zaman, o bu veri türü için bir işaretçi demektir.
Yani önümüzdeki görünüşte bir olduğunu Bir yapı düğüme işaretçisi.
>> Şimdi, bir yapı düğümü nedir?
Peki, o bkz fark sağ üst aynı kelimeler.
Ve gerçekten de, aynı zamanda kelime görmek Buraya sol alt "düğüm".
Ve bu aslında sadece bir kolaylık.
Öğrenci tanımda sadece bir kez kelime "öğrenci" var.
Ve bu bir öğrenci, çünkü var Nesne özüne değildi.
Bir öğrencinin içinde bir şey var Bu başka bir öğrenciye işaret gerekiyor,
persay.
Bu tür olurdu Gerçek dünyada garip.
>> Ancak bir düğüm ile ilişkili Liste, bir düğüm istiyoruz
benzer bir nesneye referans olması.
Ve işte değişikliği değil fark sadece ne küme parantezi içinde var.
Ama biz "düğüm" kelimesini ekleyin üst hem de
alt eklemeden yerine "öğrenci."
Ve bu sadece bir teknik detay böylece, yine, veri yapısı
, özüne olabilen bir şekilde düğüm gibi bir başka düğüme işaret edebilir.
>> Peki bu sonuçta ne Bizim için anlamı olacak?
Eh, bir, bu şeyler içinde Bizim düğümün içeriği olduğunu.
Buraya bu şey, Sağ üst, sadece böyledir
Bu, yine, biz kendimize başvurabilirsiniz.
Ve sonra dıştaki şeyler, düğüm yeni bir terim olduğu halde,
belki de, hala var öğrenci ve ne gibi aynı
SPL kaputun altında idi.
>> Şimdi başlamak istedim Yani eğer Bu bağlantılı liste uygulanması,
nasıl tercüme olabilir Böyle bir şey kodlamak için?
Peki, sadece bir görelim Bir programın örnek,
aslında bir bağlantılı liste kullanır.
Bugünün dağıtım kodu arasında Liste Sıfır adında bir program.
Ben bu çalıştırırsanız Ve ben bir süper yarattı Basit GUI, Grafik Kullanıcı Arayüzü,
ama gerçekten sadece printf oluyor.
Ve şimdi kendime bir kaç menü verdik options-- Sil, Ekle, Arama,
ve Traverse.
Ve çıkın.
Bunlar sadece ortak işlemler bir bağlantı listesi olarak bilinen veri yapısı.
>> Şimdi, gidiyor Sil Listeden bir numarayı silmek.
Ekle eklemek için gidiyor listeye bir numara.
Arama bakmak için gidiyor Listede numarası.
Ve travers sadece bir fantezi yoludur söyleyerek, listede yürümek,
çıktısını, ama o kadar.
Hiçbir şekilde değiştirmeyin.
>> Peki bunu deneyelim.
En go ahead ve tip 2 edelim.
Ve sonra ben gidiyorum numara eklemek, 9 söylüyorlar.
Girin.
Ve şimdi benim programı sadece bir demek programlanmış, liste şimdi 9.
Şimdi, ben önde gidersem ve Tekrar takın yapmak, izin
Beni go ahead ve uzaklaştırmak ve 17 yazın.
Şimdi benim liste daha sonra, 17 9.
Ben tekrar takın yaparsanız, en atlayın edelim.
Yerine 22, resim başına biz ettik Burada bakarak, bana atlayabilirsiniz izin
ve yanındaki 26 yerleştirin.
Yani 26 yazın gidiyorum.
beklediğim gibi listesidir.
Ama şimdi, sadece bu kod görmek için Esnek olacak, şimdi bana izin
tip 22, burada en azından kavramsal, biz eğer
Bu gerçekten hangi sıralanır tutulması Şu anda başka bir amaç olacak,
17 ve 26 arasında gitmeli.
Yani Enter tuşuna basın.
Nitekim, bu işleri.
Ve şimdi beni eklemek izin son resim, 34 başına.
>> Tamam.
Yani şimdi benim için şart izin Sil ve Traverse ve Arama yapmak,
Aslında işe.
Ben Ara çalıştırabilirim Aslında, diyelim Enter, sayı 22 arayın.
Bu 22 bulundu.
Yani bu ne Program Listesi Sıfır yapar.
>> Ama aslında ne oluyor o Bu uygular?
Peki, ilk ben, ve gerçekten olabilir Ben bir dosya list0.h denilen, var.
Ve bu var bir yerde çizgi, typedef struct düğüm,
Sonra ben, benim küme parantezi var int n, ve Sonra tanımı neydi struct--?
Struct düğüm yanındaki.
Bu yüzden yıldız ihtiyacımız var.
Şimdi teknik olarak biz içine almak Burada çizim alışkanlığı.
Sen ders kitaplarını görebilirsiniz ve Online başvurular var bunu.
Bu işlevsel eşdeğerdir.
Aslında, bu biraz daha tipiktir.
Ama ben ne ile tutarlı olacak Geçen zaman yaptım ve bunu.
Ve sonra son olarak, ben bunu yapmak için gidiyorum.
>> Bir başlık dosyasında Yani bir yerde, list0.h içinde
Bugün bu yapı tanımı, ve belki diğer bazı şeyler.
Bu arada list0c içinde var bir kaç şey olacak.
Ama biz gidiyoruz sadece başlatmak ve bu bitirmek değil.
List0.h Ben istiyorum bir dosya Benim C dosyasına dahil etmek.
Ve sonra bazı noktada ben değilim ana, int var geçersiz olacak.
Ve sonra ben gidiyorum Yapılacaklar bazı burada var.
Ben de bir var gidiyorum prototip, boşluk, arama, int gibi,
n, hayatta kimin amacı Bir eleman aramak için.
Ve sonra buraya ben iddia Bugünün kod geçersiz, arama, int, n,
noktalı virgül ancak açık kaşlı.
Ve şimdi ben bir şekilde aramak istiyorum Bu listede bir öğe için.
Ama biz yeterince yok Henüz ekranda bilgiler.
Ben aslında var listesini kendisi temsil etmektedir.
Yani bir şekilde biz uygulamak Bir programda bir bağlantılı liste
Ben tür şeyler yapmak istiyorum edilir Burada listesini bağlantılı beyan ederim.
Basitlik için, ben yapacağım Bu hatta genel biz olsa, küresel
Bu çok yapmamalısınız.
Ama bu örnek basitleştirecek.
Yani beyan etmek istiyorum Burada bir bağlantılı liste kadar.
Şimdi, ben bunu nasıl yapabilirim?
>> İşte bir bağlantılı liste resmi var.
Ve ben gerçekten yok nasıl şu anda biliyorum
Ben temsil hakkında gitmek için gidiyorum Sadece biriyle o kadar çok şey
bellekte değişken.
Ama geri bir an düşünüyorum.
Biz aldık Bütün bu zaman dizeleri, daha sonra hangi biz
diziler olarak ortaya karakterler, daha sonra, biz
Sadece bir işaretçi olarak ortaya İlk karaktere
karakter dizisi olarak Bu boş sonlandırılmış oluyor.
Bu mantıkla, ve bu So düşüncelerinizi tohumlama resim tür,
biz aslında ne yazmak gerekir bizim Kod bağlantılı liste temsil etmek?
Ne kadar bu bilgilerin ihtiyacımız var C kodu yakalamak için, sen söylerdin?
Evet?
>> İZLEYİCİ: Biz bir düğüme bir işaretçi gerekir.
DAVID J. MALAN: Bir düğüme bir işaretçi.
Özellikle, düğüm, sizin olur içgüdüleri bir işaretçi tutmak olacak?
>> İZLEYİCİ: İlk düğüm.
>> DAVID J. MALAN: Evet, Muhtemelen sadece ilk.
Ve, birinci fark düğüm başka bir şekildir.
Bu yapı sadece yarısı büyüklüğünde, çünkü gerçekten sadece bir işaretçi var.
Yani gerçekten neler yapabileceğini beyan olduğunu bağlantılı liste * tipi düğümün olmak.
Ve Sadece ilk diyelim ve null olarak başlatılamadı.
Yani boş, yine geliyor ise Burada resmin içine.
Sadece boş özel gibi kullanılan getString gibi şeyler için dönüş değeri
ve malloc, boş da sıfır işaretçi, bir işaretçi eksikliği,
eğer sen.
Sadece bir şey henüz burada demektir.
Şimdi ilk ben oldum olabilir Bu şey denir.
Ben "liste" denilen olabilirdi veya diğer şeylerin herhangi bir sayı.
Ama böylece "ilk" olarak arıyorum Bu resim ile o çizgiler kadar.
Yani sadece bir dize gibi temsil edilebilir İlk bayt adresi ile,
yani bir bağlantılı liste yapabilirsiniz.
Ve biz diğer verileri görürsünüz yapıları temsil
Sadece bir işaretçi ile, 32-bit ok, işaret
yapısında ilk düğümde.
>> Ama şimdi bir sorunu tahmin edelim.
Ben sadece hatırlayarak ediyorsam Benim programda adresiniz
Birinci düğüm, birinci Bu veri yapısı içinde dikdörtgen,
vardı daha hakkında dava olmak ne Benim listesinin geri kalanı uygulanması?
Gidiyor bir anahtar detay nedir Bu aslında çalışır sağlamak için?
Ve I "gerçekten çalışıyor" çok bir dize gibi, demek,
bize ilk karakter gidelim saniye Davin adına,
üçüncü için Dördüncü, sonuna kadar,
Biz sonunda olduğunuzda nasıl biliyoruz Şöyle bir bağlantılı liste?
Ne zaman boş olduğunu.
Ve ben bu tür temsil ettik Bir elektrik mühendisi kudret gibi,
Küçük topraklama ile sembolü, türlü.
Ama bu sadece bu durumda null anlamına gelir.
Bunu herhangi bir sayı çizebilirsiniz yolları, ama bu yazar
Burada bu sembolü kullanmaya oldu.
Biz çekimi konum olarak >> Çok uzun Birlikte bu düğümlerin hepsi,
Sadece nerede hatırlayarak Birincisi, bu nedenle uzun
biz özel bir sembol koymak gibi Listedeki son düğüm
Bu çünkü biz, null adlı kullanacağız Elimizdeki mevcut ne varsa,
Bu liste tamamlandı.
Ve ben bile sadece size bir işaretçi vermek İlk eleman, sen, programcı,
Kesinlikle geri kalanını erişebilirsiniz.
Ama senin kafasında let biraz dolaşmak,
Zaten değilseniz Oldukça ne wandered--
çalışma süresi olacak Bu listede bir şey bulmak?
O Kahretsin, n büyük Ey var, hangi adalet, kötü değil.
Ama doğrusaldır.
Biz ne özelliği vazgeçmiş Daha fazla hareket ettirerek dizilerin
dinamik Bu resim doğru Birlikte dokunmuş veya düğümleri bağlantılı?
Biz rastgele erişimi verdik.
Bir dizi yüzünden güzel matematiksel herşey
geri geri geri geri.
Hatta bu resim olsa güzel görünüyor, ve hatta
bu düğümlerin gibi görünüyor olsa da güzel gerçekte, aralıklı edilir
Onlar her yerde olabilir.
OX1, Ox50, Ox123, Ox99 şu düğümleri herhangi bir yerde olabilir.
Malloc bellek ayrılamadı yok çünkü yığından, ama her yerde yığın.
Sen mutlaka bu olduğunu bilmiyorum Geri olacak geri geri.
Ve gerçeklik en çok bu resim oldukça bu güzel olacak değil.
>> Bu yüzden biraz almak için gidiyor Bu işlevi uygulamak için çalışıyoruz.
Yani şimdi arama uygulamak verelim.
Ve biz tür görürsünüz Bunu yapmanın akıllıca yoludur.
Ben bir arama fonksiyonu olduğumu Yani eğer ve Ben bir değişken, tamsayı n verilen ediyorum
bakmak için, bilmem gerekiyor içine bakarak yeni sözdizimi
olan bir yapının n bulmak için işaret etti.
O yüzden bu yapalım.
>> Bu yüzden ilk ben gidiyorum önde ve * düğüm beyan ederim.
Ve ben onu aramak için gidiyorum Sadece kongre tarafından gösterici.
Ve ben ilk onu başlatmak için gidiyorum.
Ve şimdi ben bunu yapabilirsiniz şekillerde bir dizi.
Ama ortak bir yaklaşım almaya gidiyorum.
Işaretçi eşit olmasa da null, ve bu geçerli sözdizimi.
Ve sadece bu yüzden, aşağıdakileri yapmanız anlamına gelir Uzun hiçbir şey işaret değil gibi.
Ne yapmak istiyorsun?
>> Gösterici nokta n, bana geri gelsin Buna, equals-- ne eşittir?
Ne değer ben arıyorum?
geçirilen fiili n.
Yani burada bir başka özellik var C ve birçok dilde.
Hatta yapı denilen düğümün olsa Bir değer n, tamamen meşru vardır
Ayrıca yerel bir argüman var veya değişken n denir.
Hatta biz, birlikte Çünkü İnsan gözü, ayırt edebilir
bu n muhtemelen olduğu Bu n farklıdır.
Sözdizimi farklı olduğundan.
Bir nokta ve bir işaretçi var, Bu bir ise böyle bir şey vardır.
Yani bu Tamam.
Aynı şeyler onları aramak için Tamam.
Bunu bulmak yoksa >> ben değilim bir şey yapmak istiyorum gidiyor
gibi biz n bulundu duyurdu.
Ve biz o kadar bırakacağım Yorum veya pseudocode kodu.
Else ve burada ilginç kısmı, ne
Ben Geçerli düğümün eğer yapmak istiyorsun Ben umurumda n içeren değil?
Nasıl aşağıdaki elde edebilirim?
Eğer benim parmak an PTR olduğunu ve var
ne işaret İlk, işaret edilir
Benim parmak hareket nasıl kodundaki sonraki düğüme?
Peki, biz konum kırıntı ne Bu durumda takip edecek?
HEDEF KİTLE: [duyulamaz].
DAVID J. MALAN: Evet, bu yüzden yanında.
Ben geri dönmek Yani benim Burada kod, gerçekten, ben değilim
, işaretçi devam edin ve diyecek ki bu sadece geçici bir değişken-- olduğunu
Bir garip isim, ptr, ancak Sadece temp-- gibi
Ben işaretçi ayarlamak için gidiyorum ne olursa olsun işaretçi bu-- eşit
ve yine, bu bir olacak yanında moment-- nokta için biraz buggy.
Diğer bir deyişle, ben almaya gidiyorum benim Bu düğümün işaret ediyor parmak
Burada ve ben seni biliyorum, demek için gidiyorum Ne, sonraki alana bir göz atın
ve parmağınızı hareket ettirin ne olursa olsun işaret ediyor.
Ve bu gidiyor , tekrar, tekrar tekrar.
Ama benim parmak yapar hiç bir şey yapıyor durdurmak?
En kısa sürede ne kod tekmeler hattı gibi?
HEDEF KİTLE: [Duyulmaz]
DAVID J. MALAN: Eğer nokta ise işaretçi null eşit değildir.
Bir noktada benim parmak At boş işaret olacak
ve ben fark gidiyorum bu listenin sonu.
Şimdi, bu biraz basitlik beyaz yalan.
Bu çıkıyor ki olsa bile biz sadece bu nokta gösterim öğrendim
yapılar için, işaretleyici bir yapı değildir.
ptr nedir?
Sadece daha nitpicky olmak.
Bir düğüme bir işaretçi var.
Bu bir düğüm kendisi değil.
Ben burada hiçbir yıldız olsaydı, işaretçi absolutely-- bir düğüm var.
Bu hafta biri gibi Bir değişkenin beyanı,
Hatta kelime "düğüm" yeni olmasına rağmen.
>> Ama biz tanıtmak en kısa sürede bir Yıldız, şimdi bir düğüme bir işaretçi var.
Ve ne yazık ki kullanamazsınız bir işaretçi için nokta notasyonu.
Sen ok kullanmak zorunda notasyonu, hangi çarpıcı,
İlk kez herhangi bir parça sözdizimi sezgisel görünüyor.
Bu anlamıyla, bir ok gibi görünüyor.
Ve böylece iyi bir şey.
Ve buraya tam anlamıyla Bir ok gibi görünüyor.
Yani ben değil la-- düşünüyorum Ben ötürü-- fazla işlemekle düşünüyorum ben
son yeni parça olduğunu düşünüyorum sözdizimi görmek için gidiyoruz.
Ve şükür ki, gerçekten de var Biraz daha sezgisel.
>> Şimdi, o sizin için kim eski yol tercih olabilir,
Hala nokta gösterimini kullanabilirsiniz.
Ama Pazartesi yıllara göre konuşma, biz ilk
Bu gidip, oraya gitmek gerekir adres, ve sonra alanına erişmek.
Yani bu da doğrudur.
Ve açıkçası, bu bir daha bilgiçlik küçük.
Kelimenin tam anlamıyla söylüyorsun, inceleyebilirsiniz işaretçi ve oraya gitmek.
Sonra .n kapmak, alan n çağırdı.
Ama açıkçası, hiç kimse istiyor yazın veya bu okumak için.
Ve böylece dünya icat ok gösterimi, hangi
aynı, eşdeğer sadece sözdizimsel şeker var.
Bu söyleyerek Yani süslü bir şekilde iyi görünüyor, ya da basit görünüyor.
>> Peki şimdi başka bir şey yapacağım.
Ben ettik kez "mola" demek için gidiyorum o yüzden onu aramaya tutmayız bulundu.
Ama bu özü olan Bir arama fonksiyonu.
Ama içinde, çok daha kolay sonunda, kod üzerinden yürümek değil.
Bu gerçekten resmi uygulamasıdır Bugünün dağıtım kodunda arama.
Ben bu ekleme değil söylemek cesaret yürümek özellikle eğlenceli
görsel, ne de olsa, silme Günün sonunda olsa
onlar oldukça aşağı kaynatın Basit sezgisel tarama.
>> Yani bu yapalım.
Burada mizah beni olacak, ben yaptım stres topları bir demet getirmek.
Ben sayıların bir demet getirdi.
Ve biz sadece bir kaç gönüllü alabilir 9, 17, 20, 22, 29 ve 34 temsil etmek?
Yani aslında herkes kim burada bugün.
Yani, bir, iki, üç oldu Dört, beş, altı kişi.
Ve ben hayır, bakın go-- istendi ettik Arkada bir ellerini yükseltir.
Yeterli, bir, iki, üç, dört, five-- bana altı balance-- yük verelim.
Tamam, altı yukarı gel.
Biz diğer insanları gerekir.
Biz ekstra stres topları getirdi.
Ve eğer yapabilirsen, için Sadece bir an, çizgi
kendinizi yukarı sadece Burada bu resimdeki gibi.
>> Tamam.
Senin adın ne, bakalım?
>> İZLEYİCİ: Andrew.
>> DAVID J. MALAN: Andrew, Eğer sayı 9 vardır.
Tanıştığımıza memnun oldum.
Hadi bakalım.
HEDEF KİTLE: Jen.
DAVID J. MALAN: Jen.
David.
Sayı 17.
Evet?
>> İZLEYİCİ: Ben Julia değilim.
>> DAVID J. MALAN: Julia, David.
Sayı 20.
HEDEF KİTLE: Hıristiyan.
DAVID J. MALAN: Hıristiyan, David.
Sayı 22.
Ve?
>> İZLEYİCİ: JP.
DAVID J. MALAN: JP.
Sayı 29.
Yani Uh oh go ahead ve in-- olsun.
Uh oh.
Yanında Olmak.
20.
Herkes bir işaretleyici var mı?
HEDEF KİTLE: Ben bir Sharpie var.
DAVID J. MALAN: Bir Sharpie var?
TAMAM MI.
Ve herkes bir parça kağıt var mı?
Ders kaydedin.
Hadi.
HEDEF KİTLE: Biz onu var.
DAVID J. MALAN: Biz onu var?
Pekala, teşekkür ederim.
İşte başlıyoruz.
Bu sizden miydi?
Sen sadece bir gün kurtardı.
Yani 29.
Tamam.
Ben 29 yanlış yazılmış, ama Tamam.
Devam et.
Pekala, sana vereceğim kalem geri an.
Yani biz burada bu millet var.
Diğer bir atalım.
Gabe, oynamak istiyorum Burada ilk unsur?
Biz gelin sizi gerekir Bu güzel millet.
Yani 9, 17, 20, 22, sıralama 29, ve sonra 34.
Birini kaybetmek mi?
Ben bir 34 var.
Nerede isteyen did-- Tamam, 34 olmak?
Tamam, 34, yukarı gel.
Pekala, bu olacak doruk değer.
Adınız ne?
>> İZLEYİCİ: Peter.
>> DAVID J. MALAN: Peter yukarı gel.
Pekâlâ, burada bir düğümlerin sürü.
Eğer çocuklar her temsil Bu dikdörtgenler biri.
Ve Gabe, biraz garip dışarı adam, ilki temsil etmektedir.
Yani onun işaretçi biraz daha küçüktür herkesten daha ekranda.
Ve bu durumda, hesabınızla her sol eller, aşağı işaret ya gidiyor
böylece bu yüzden, boş temsil Sadece bir işaretçi bulunmaması,
ya da işaret edilecek gidiyor senin yanında bir düğüm at.
>> Peki şimdi sen süslüyor eğer resim gibi kendinizi
Burada, go ahead ve nokta Gabe'e, birbirlerine
özelde işaret etti sayı 9 listesini temsil etmek.
Tamam, ve sayı 34, sol el Sadece zemin işaret edilmelidir.
>> Tamam, bu yüzden bu bağlantılı liste.
Yani bu söz konusu senaryodur.
Ve gerçekten de, bu temsili sorunların bir sınıf
Eğer kodu ile çözmeye çalışın diye.
Sen sonuçta eklemek istiyorum listeye yeni bir unsur.
Bu durumda, biz gidiyoruz numara 55 takarak deneyin.
Ama orada oluyor Farklı durumlar dikkate.
Ve gerçekten de, bu bir olacak büyük resmi burada paketler, bir
Farklı durumlar nelerdir.
Koşulları varsa veya farklı nelerdir Programınız olabilir dalları?
>> Peki, numarası için çalışıyoruz Biz 55 olmak artık biliyoruz eklemek,
ama bilmiyordum peşin, ben daresay
en az üç düşer olası durumlar.
Nerede yeni bir unsur olabilir?
HEDEF KİTLE: Ve son veya orta.
David J. MALAN: sonunda, içinde orta veya başında.
Yani en azından orada iddia Üç problemler çözmek gerekiyor.
En belki de ne seçeyim belki basit
bir, nerede yeni eleman başlangıçta aittir.
Yani oldukça kodu gidiyorum gibi sadece yazdı, hangi arama.
Ve ben, ptr için gidiyorum hangi Ben, benim parmak ile burada temsil edeceğiz
her zaman olduğu gibi.
>> Ve, ne değeri hatırlıyorum biz ptr başlatılamadı mi?
Bu yüzden başlangıçta null onu başlatıldı.
Ama sonra biz bir kez ne yaptın arama fonksiyonu içinde vardı?
Biz, birinci eşit set Bunu yaparken anlamına gelmez ki.
Ben ilk eşit ptr ayarlarsanız, ne elimi gerçekten işaret olmalı?
Sağ.
Gabe ve ben gidiyoruz Yani eğer Burada eşit değerler için,
Biz 9 numarada hem noktaya gerekir.
>> Yani bu bizim hikayenin başlangıcı oldu.
Ve şimdi bu, sadece basittir olsa bile sözdizimi yeni.
Kavramsal olarak bu sadece doğrusal arama motorudur.
9 eşit 55 mi?
Ya da daha doğrusu, en az 9 diyelim.
Ben çalışıyorum, çünkü 55 koymak nereye anlamaya.
9 daha az, daha az 17, daha az 20 'den daha az 22, en az 29,
en az 34, no.
Yani şimdi halinde konum En az üç biri.
>> Ben buraya 55 eklemek istiyorsanız, ne Kod ihtiyacı hatları idam olsun?
Nasıl bu resmi yapar İnsanların değiştirmek gerekir?
Sol elimle ne yapmalıyım?
Bu, başlangıçta sıfır olmalıdır Ben listenin sonunda olduğum için.
Ve ne olması gerektiğini Burada Peter ile oldu?
Belli ki bana işaret edecek.
Yani en az iki satır var iddia bugünden örnek kod kod
bu uygulamaya gidiyor kuyruk 55 ekleme senaryo.
Ve birileri hop olabilir yukarı ve sadece 55 temsil?
Pekala, yeni 55 bulunmaktadır.
>> Peki şimdi ne gelecek olursa senaryo, birlikte geliyor
ve biz eklemek istiyorum başlayan veya bu listeye başkanı?
Ve adı, numarası 55 ne?
>> İZLEYİCİ: Jack.
>> DAVID J. MALAN: Jack?
Tamam, seninle tanışmak güzel.
Aramıza hoşgeldin.
Yani şimdi biz gidiyoruz , diyelim ki, sayı 5 yerleştirin.
İşte ikinci durumda bulunuyor Üç önce geldi.
Yani 5 başında aitse, Şimdi bunu öğrenmek nasıl görelim.
Ben ptr başlatmak Tekrar sayısı 9 işaretçi.
Ve ben 5 daha az 9, ah, anladım.
Yani bizim için bu resmi düzeltmek.
Kimin elleri, Gabe en ya David'in veya-- sayı 9'un adı ne?
>> İZLEYİCİ: Jen.
>> DAVID J. MALAN: Jen hands-- Bizim eller, hangi değiştirmeniz gerekir?
Tamam, bu yüzden Gabe şimdi ne işaret?
Bana.
Ben yeni bir düğüm duyuyorum.
Yani hareket sadece tür olacak Burada görsel olarak görmek için.
Ve bu arada ne olduğunu işaret mi?
Hala nerede işaret ediyorum.
Yani o kadar.
Kod düzeltmeleri Yani sadece gerçekten bir satır Bu özel konu, bu gibi görünüyor.
Pekala, bu yüzden iyi.
Ve birisi 5 için bir yer tutucudur olabilir?
Hadi gel.
Size yakın zaman alırsınız.
>> Pekâlâ, şimdi-- ve Bir kenara, adları
Ben sağ açık söz yapmıyorum Şimdi, Sonr gösterici, selefi işaretçisi
ve yeni işaretçi, işte Sadece isimleri verilen
işaretçileri örnek kod veya tür etrafında işaret ediyor ellerim.
Adınız ne?
>> İZLEYİCİ: Christine.
>> DAVID J. MALAN: Christine.
Aramıza hoşgeldin.
Pekala, o yüzden şimdi düşünelim biraz daha can sıkıcı senaryo,
Ben eklemek istiyorum sayede Bu içine 26 gibi bir şey.
20?
Ne?
Bunlar bu kalem var iyi bir şey mudur.
Pekala, 20.
Birisi başka bir parça alabilir Eğer Kağıt, sadece tamam case-- olarak, hazır.
Ah, ilginç.
Peki bu bir örnektir Bir ders hata.
Tamam bu yüzden adınız neydi?
HEDEF KİTLE: Julia.
DAVID J. MALAN: Julia, pop olabilir dışarı ve taklit asla vardı?
Tamam, bu asla olmadı.
Teşekkür ederim.
Bu yüzden eklemek istediğinizi varsayalım Bu bağlantılı listeye Julia.
O sayısı 20'dir.
Ve tabii ki o var En ait olacak
begin-- henüz hiçbir şeye işaret etmemektedir.
Yani eliniz tür olabilir aşağı null veya bazı çöp değeri.
En hızlı hikaye anlatayım.
Ben 5 numarada bu kez işaret ediyorum.
Sonra 9 edin.
Sonra 17 kontrol edin.
Sonra 22 kontrol edin.
Ve ben, ooh, Julia fark 22 önce gitmek gerekiyor.
Peki ne gerekiyor?
Kimin elleri değiştirmek gerekir?
Julia, maden, veya-- Adın neydi?
>> İZLEYİCİ: Hıristiyan.
>> DAVID J. MALAN: Hristiyan veya?
>> İZLEYİCİ: Andy.
>> DAVID J. MALAN: Andy.
Hıristiyan ya da Andy?
Andy işaret etmek gerekiyor?
Julia.
Tamam.
Yani Andy, Julia işaret etmek istiyorsun?
Ama bir dakika bekleyin.
Şimdiye kadar Hikayede, Ben bir tür kulüpler
anlamda yükü, bu işaretçisi var şey
Liste boyunca hareket.
Biz Andy için bir isim var, ama olabilir Andy diye bir değişken var.
Elimizdeki sadece diğer değişkendir Önce, Gabe'e temsil kim.
>> Peki bu neden dolayısıyla aslında kadarıyla biz bu gerekli değildir ettik.
Ama şimdi ekranda var beklenen işaretçi yine söz.
Yani beni daha açık olalım.
Bu gösterici ise, ben daha iyi oldu Biraz daha zeki olsun
Benim yineleme hakkında.
Eğer benim burada geçiyor sakıncası yoksa Yine, burada işaret, burada işaret.
Ama bana beklenen işaretçi atalım, selefi işaretçi, işte
tür işaret eleman Ben sadece oldu.
Yani burada gittiğinizde, şimdi Benim sol el güncellemeleri.
Burada benim sol güncellemeleri gittiğinizde.
Ve şimdi ben bir işaretçi sadece var Julia sonra gider unsuru,
Ben hala bir işaretçi var Andy önce elemanı.
Yani, aslında, erişimi kırıntıları, eğer sen,
Gerekli işaretçileri tüm.
>> Ben de işaret ediyorum eğer öyleyse Andy ve ben de işaret ediyorum
kimin elleri Hıristiyan, at Şimdi başka bir yerde işaret edilmelidir?
Andy Yani şimdi Julia işaret edebilir.
Julia şimdi Hıristiyan işaret edebilir.
O kopyalayabilirsiniz Çünkü benim Sağ elin işaretçi.
Ve bu etkili bir koyar buraya bu yerine.
Yani kısacası, hatta bu olsa sonsuza dek tür bizi alıyor
Aslında güncellemek için bir Listeyi bağlantılı, fark
operasyonlar olduğunu Nispeten basit.
Bu, iki, bir üç var: sonuçta kod satırları.
Ama o etrafına sarılmış muhtemelen kod satırları
mantık biraz o etkili bir olduğunu sorusunu, biz sorar?
Biz başındayız, orta veya son?
>> Şimdi, şüphesiz başka vardır biz uygulamak olabilir operasyonlar.
Ve burada bu resimler sadece tasvir ne sadece insanlar ile yaptım.
Ne kaldırılması hakkında?
Ben istiyorsanız, örneğin, Numarayı kaldırmak 34 veya 55,
Ben, kod aynı tür sahip olabilir ama bir ya da iki adım gerekir gidiyorum.
Ne yeni Çünkü?
Ben sonunda birini kaldırırsanız, numarası gibi 55 ve 34,
ne de ben bunu olarak değiştirmek zorunda?
Ben evict-- etmek zorunda Adın neydi?
>> İZLEYİCİ: Jack.
>> DAVID J. MALAN: Jack.
Ben, evict-- ücretsiz Jack sadece var yani tam anlamıyla en azından ücretsiz Jack arayın, ya da
Orada gösterici de, ama şimdi Ne Peter ile değiştirmek gerekiyor?
Eli iyi aşağı işaret başlayın.
En kısa sürede ben ücretsiz çağrı olarak Çünkü Jack, Peter hala Jack işaret eğer
ve bu nedenle traversing devam listesi ve erişim bu işaretçi,
Bu bizim eski dostumuz segmentasyon var aslında tekme olabilir arıza.
Biz verdik Çünkü Jack bellek geri.
>> Siz orada kalabilirler beceriksizce sadece bir an için.
Biz sadece bir çift var, çünkü Nihai işlemler dikkate.
Listenin başını çıkarma, beginning-- ve bu kişinin veya
Biraz can sıkıcı.
Biz bilmek zorunda olduğundan Gabe tür özel bu programda yer almaktadır.
Çünkü gerçekten, kendi işaretçisi vardır.
O sadece, işaret ediliyor değil Burada hemen hemen herkes gibi.
>> Yani listenin baş olduğunda , kimin elleri şimdi değiştirmek gerekir kaldırıldı?
Adın neydi?
>> İZLEYİCİ: Christine.
>> DAVID J. MALAN: Berbatım isimleri, görünüşe göre.
Yani Christine ve Gabe, kimin elleri değiştirmeniz gerekir
Biz Christine kaldırmaya çalıştığınızda, resimden sayısı 5?
Tamam, bu yüzden Gabe yapalım.
Gabe noktasına gidiyor, muhtemelen, 9 numarada.
Ama bundan sonra ne yapmalıyım?
HEDEF KİTLE: Christine gerekir [duyulamaz] null.
DAVID J. MALAN: Tamam, biz muhtemelen gerekir make-- yerde "boş" duydum.
HEDEF KİTLE: Boş ve onu serbest.
DAVID J. MALAN: Ne null?
HEDEF KİTLE: Boş ve onu serbest.
DAVID J. MALAN: Boş ve onu serbest.
Yani bu çok kolay.
Ve şimdi sıralama olduğunu mükemmel aidiyet, orada ayakta.
Eğer oldum Çünkü Listeden ayrışmıştır.
Etkili oldum Listeden yetim.
Ve böylece biz daha şimdi ücretsiz çağrı vardı Christine bellek geri vermek.
Aksi takdirde her zaman biz Listeden bir düğüm silme
Biz listesini yapmak olabilir daha kısa, ama aslında azaltmadan
bellekte boyutu.
Ve böylece biz ekleyerek devam edersek ve ekleyerek, listeye şeyler ekleyerek,
Benim bilgisayar yavaşlayabilir ve yavaş yavaş ve,
Ben tükeniyor çünkü Bellek, aslında değilim bile
Christine'in bayt kullanarak bellek artık.
>> Yani sonunda diğer vardır elbette-- kaldırma senaryolar
orta kaldırılması sonunda, biz gördük.
Ama daha ilginç Şimdi sorun olduğunu
gidiş tam dikkate olmak çalışma süresi nedir.
Yani sadece siz tutabilirsiniz sizin kağıt parçaları Gabe, eğer
Eğer vererek sakıncası olmaz Herkes bir stres topu.
Bizim bağlı listeye çok teşekkür ederiz Burada gönüllü, eğer yapabilirsen.
>> [Alkış]
>> DAVID J. MALAN: Pekala.
Analitik Yani bir çift Daha sonra soruları, eğer olabilir.
Biz daha önce bu gösterim gördüm, Büyük Ç ve omega, üst sınır
ve alt sınırları Bazı algoritmanın çalışma süresi.
Yani sadece düşünelim bir kaç soru.
>> Bir, ve biz bunu dedi önce, çalışan ne
Bir için arama zamanı Büyük O bakımından listesi?
Ne çalışan bir üst sınır var bağlantılı liste arama zamanı
Burada bizim gönüllüler tarafından uygulandığı gibi?
Bu n büyük Ey, doğrusal değil.
En kötü durumda Çünkü elemanı 55 gibi,
nereye olmak için olabilir arıyor olabilir Jack, sonunda tüm yol oldu.
Ve ne yazık ki, bir dizi farklı Bu sefer fantezi alınamıyor.
Bizim insanların hepsi olsa da küçük elemanları, 5 sıralanır,
büyük elemanına kadar tüm yol, 55, genellikle iyi bir şey.
Ama bu varsayım ne artık yapmamızı sağlar?
HEDEF KİTLE: [Duyulmaz]
DAVID J. MALAN: Tekrar söyle?
HEDEF KİTLE: Rastgele erişim.
DAVID J. MALAN: Rastgele erişim.
Ve sırayla hiçbir elimizden anlamına gelir uzun, zayıf sıfır, sezgi kullanın
ikili kullanarak ve açıklık arama ve bölmek ve fethetmek.
Olsa bile Çünkü biz insanlar açıkça olabilir
Andy veya Hıristiyan olduğunu görmek kabaca listenin ortasında,
Biz sadece bir olarak biliyorum Listeyi kaymağını bilgisayar
başından itibaren.
Yani biz bu rastgele erişimi verdik.
>> N Yani büyük Ç şimdi üst olduğunu arama zamanında bağlı.
Ne bizim arama omega hakkında?
Alt sınır arıyor neler var Bu listedeki bazı numara için?
HEDEF KİTLE: [Duyulmaz]
DAVID J. MALAN: Tekrar söyle?
HEDEF KİTLE: Bir.
DAVID J. MALAN: Bir.
Yani zaman sabiti.
En iyi durumda, Christine gerçekten listenin başında.
Ve biz arıyoruz 5 numara, bu yüzden onu buldum.
Yani hayır büyük dağıtmak.
Ama olmak var Bu durumda listenin başında.
Gibi bir şey hakkında ne Sil?
Eğer bir eleman silmek için ne isterseniz?
Ne üst sınır ve alt sınır var Bağlantılı bir şey silinmesine ilişkin
Listeye?
HEDEF KİTLE: [Duyulmaz]
DAVID J. MALAN: Tekrar söyle?
HEDEF KİTLE: n.
David J. MALAN: n, sınır gerçekten üst.
En kötü durumda biz denemek için biz sadece yaptığımız gibi, Jack silmek için.
O sonunda tüm yol.
Sonsuza kadar bizi alır, ya da n adımlar onu bulmak için.
Yani bir üst sınır var.
Bu tabii, doğrusal değil.
Ve en iyi durumda çalışma süresi, ya da En iyi durumda, alt sınır
sürekli zaman olacaktır.
Belki silmeye çalıştığınızda Çünkü Christine ve biz sadece şanslı olsun
O başında bulunuyor.
Şimdi bir dakika bekleyin.
Gabe, başında da oldu ve biz de Gabe güncellemek zorunda kaldı.
Yani sadece bir adım değildi.
Yani gerçekten sabittir zaman, en iyi durumda,
küçük öğe kaldırmak için?
Iki olabilir olsa bu, bir kod üç, ya da hatta 100 hatları,
o aynı sayıda ise değil, bazı döngü içinde çizgiler,
ve boyutundan bağımsız olarak Listenin, kesinlikle.
Elemanı olarak silme Listenin başında,
biz uğraşmak zorunda bile Gabe, hala sabit zaman.
>> Yani bu gibi görünüyor geriye büyük bir adım.
Ve zaman ne bir atık eğer haftada bir ve haftada
Sıfır biz sadece vardı pseudocode kodu ama gerçek kod
Günlük bir şeyi uygulamak için Baz n, ya da günlük, daha doğrusu, n, baz 2,
kendi çalışma süresi açısından.
Yani halt biz başlatmak için neden isteyeyim Bağlantılı bir listesi gibi bir şey kullanarak?
Evet.
>> İZLEYİCİ: Yani ekleyebilirsiniz Diziye elemanları.
DAVID J. MALAN: Yani yapabilirsiniz diziye öğeler eklemek.
Ve bu da tematik olduğunu.
Ve biz görmeye devam edeceğiz Bu, bu ticaret-off, çok
gibi gördüğümüz bir birleştirme tür ticaret-off.
Biz gerçekten hızlandırmak olabilir daha doğrusu, arama veya sıralama,
biz biraz daha fazla yer harcamak ve Bir ek bellek yığın sahip
veya birleştirme sıralama için bir dizi.
Ama biz daha fazla harcama uzay, ama biz zamandan tasarruf.
Bu durumda, konum zaman vazgeçerek ama biz konum
esneklik kazanıyor, dinamizm eğer sen,
hangi belki olumlu bir özelliktir.
>> Biz de alanı harcıyoruz.
Hangi anlamda bir bağlantılı daha pahalı liste
Bir dizinin daha alan açısından?
Nereden fazladan boşluk geliyor?
Evet?
>> İZLEYİCİ: [duyulamaz] işaretçi.
>> DAVID J. MALAN: Evet, biz Ayrıca işaretçisi var.
Yani bu minorly can sıkıcı bir durum Bu artık değilim
Ben sadece bir int depolamak Bir int temsil etmek.
Ben bir int ve a depolama ediyorum Ayrıca 32 bit işaretçi.
Yani tam anlamıyla ikiye ediyorum alan miktarı dahil.
Yani bir trade-off, ama Bu int durumunda bulunuyor.
, Sen int depolamak değil varsayalım ancak bu dikdörtgenler her varsayalım
veya bunların insanlara her temsil eden Bir kelime, bir İngilizce kelime bu
Beş karakter, 10 olabilir karakterleri, hatta belki de daha fazlası.
Sonra sadece 32 daha fazla bit ekleyerek Büyük bir anlaşma daha az olabilir.
>> Ne Öğrencilerin her varsa gösteriye
vardı anlamıyla öğrenci yapılar olduğunu belki isimleri ve evler var ve
telefon numaraları ve Twitter işleme ve benzeri yer alır.
Yani her alanda biz başladık Geçen gün hakkında konuşurken,
gibi büyük bir anlaşma daha az Bizim düğümleri daha ilginç olsun
ve büyük, ha, ek bir harcama işaretçi sadece bunları birbirine bağlamak için.
Ama gerçekten, bu bir ticaret-off.
Ve gerçekten de, kodu daha karmaşık, gibi olacak
ile kaymağını tarafından bakın söz konusu bir örnek.
Ama ne olsaydı Burada bazı kutsal kasesi.
Biz bir adım atmak yoksa neler geriye ama büyük bir adım ileri
ve bir veri uygulamak bunun yapısı ile biz
Jack veya benzeri unsurları bulabilirsiniz Christine ya da başka elemanları
Gerçek sabit zamanda bu dizide?
Arama sabittir.
Sil sabittir.
Ekle sabittir.
Bu işlemlerin tamamı sabittir.
Bu bizim kutsal kasesi olacaktır.
Ve bu nerede biz dahaki sefere bulacaktır.
Sonra görüşürüz.