[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.