>> [MÜZİK OYUN]
>> Doug LLOYD: Tamam, bu kadar Elbette bu husus,
Biz C. temelleri çok kapalı var Biz, değişkenler, diziler hakkında çok şey biliyorum
işaretçileri, bütün bu iyi şeyler.
Bunlar her çeşit inşa edilmiştir de, temel olarak görmek
ama biz doğru, daha yapabilirim?
Bazı şeyleri birleştirebilirsiniz Birlikte ilginç şekillerde.
>> Ve o yüzden başlayalım, öyle yapalım C bizi ne verir dışarı şube,
ve kendi veri oluşturmaya başlayabilirsiniz Bu binayı kullanan yapılar
Birlikte bir şeyler yapmak blokları kullanışlı, gerçekten değerli.
Bunu yapabiliriz bir yoludur koleksiyonları hakkında konuşmak için.
Yani bugüne kadar verinin bir tür yaşadım koleksiyonları temsil yapı
değerlerini, benzer değerlere seviyorum.
Bu bir dizi olurdu.
Biz tamsayılar koleksiyonları var ya böylece karakterler ve koleksiyonları.
>> Yapılar da veri sıralama vardır bilgi toplamak için yapı,
ancak değerler gibi toplamak için değil.
Genellikle farklı veri türleri karışımları Birlikte tek bir kutu içinde.
Ama kendisi değil Birlikte zincir için kullanılan
ya da birlikte benzer bağlamak Bir dizi gibi öğeler.
Diziler için büyük eleman aramak, ancak geri çağırma
çok zor olduğunu bir diziye eklemek için,
biz ekleyerek sürece Bu dizinin çok uç.
>> Ve en iyi örnek ben Bunun için ekleme türüdür.
Eğer videomuzu hatırlayacak olursak Ekleme tür üzerinde,
bir sürü orada oldu gider sahip yer
elemanları pick up ve bunları kaydırmaya bir şey sığdırmak için yolumdan
senin dizinin ortasına.
Diziler ayrıca başka muzdarip Sorun, hangi inflexibility olduğunu.
Biz bir diziyi bildirmek zaman biz ona bir tane vurulmaz.
Biz istiyoruz, demek olsun Bu birçok unsurlar.
100 olabilir, bu olabilir 1000 olmak, bu olabilir
x kullanıcının bir sayıdır x, Bir isteminde veya komut bize verdi
çizgi.
>> Ama biz sadece bu az bir vurulmaz, biz Aslında, daha sonra ah demek alamadım
101 ihtiyaç ya da ben x artı 20 gerekiyordu.
Çok geç, biz zaten ilan ettik Dizi ve biz 101 veya almak istiyorsanız x
artı 20, biz bildirmek zorunda tamamen farklı bir dizi,
dizinin bütün elemanları kopyalamak üzerinde, ve sonra biz yeterli.
Ve biz yine yanlış ise ne, ne biz aslında 102 veya x artı 40 gerekirse,
Biz yine bunu yapmak zorunda.
Yani çok katı olduğunu verilerimizi yeniden boyutlandırma,
ama birlikte bazı birleştirince biz zaten ettik temelleri
işaretçiler ve yapıları hakkında öğrendim, Özellikle dinamik bellek kullanarak
malloc ile tahsis, biz Birlikte bu parçaları koyabilirsiniz
Yeni verilerin structure-- a oluşturmak için tek başına biz ifade edebileceği üzere- listesi bağlantılı
bu bizi büyümeye olanak ve değerlerin bir koleksiyon küçültmek
ve biz herhangi bir israf alanı olmayacaktır.
>> Yani yine, biz bu fikri diyoruz, Bu kavram, bir bağlantılı liste.
Özel olarak, bu video we ' tek başına bağlantılı liste hakkında konuşurken,
ve daha sonra başka bir video biz konuşacağız yaklaşık iki kat bağlantılı listeler, hangi
Burada tema sadece bir çeşididir.
Ancak tek tek bağlantılı liste düğüm oluşur,
düğümleri sadece soyut bir varlık term-- ben arıyorum bir şey var
Bu bir çeşit yapısı, temelde, ben?
Sadece bunu bir node-- ve bu arayacağım düğüm iki üyesi, ya da iki alan vardır.
Genellikle, bir veri vardır tamsayı, bir karakter şamandıra,
ya da başka bir veri türü olabilir Bir tür def ile tanımlanır ettik.
Ve bir gösterici içerir aynı türden başka bir düğüm.
>> Bu yüzden içinde iki şey var Bu düğüm, veri ve bir işaretçi
başka bir düğüme.
Ve görselleştirmek başlatırsanız Bu, bunu düşünmek olabilir
düğümlerin bir zincir gibi olduğunu birbirine bağlanır.
Biz ilk düğüm var, o verilerinizi ve bir işaretçi içerir
içeren ikinci düğüme için Veri ve üçüncü düğüme bir işaretçi.
Ve böylece biz onu diyoruz yüzden bağlantılı liste, onlar birbirine bağlı ediyoruz.
>> Bu özel ne yapar? düğüm yapısı benziyor?
Peki, sen bizim video hatırlayacak olursak tipi def ile özel türleri tanımlayarak,
Biz structure-- tanımlayabilir ve Böyle bir yapıyı tanımlamak yazın.
yapı sllist tyepdef ve ben keyfi burada kelime değerini kullanarak
Gerçekten herhangi bir veri türünü gösterir.
Sen, bir tamsayı veya şamandıra üzerinde geçebileceği Eğer istersen olabilir.
Sadece sınırlı değil tamsayı, ya da böyle bir şey.
Yani değeri sadece keyfi Daha sonra veri türü ve bir işaretçi
aynı türden başka bir düğüme.
>> Şimdi, küçük bir sorun var Burada bir yapıya tanımlama ile
ne zaman kendi kendine referanslı yapısıdır.
Ben geçici olması Benim yapısı için isim.
Gün I sonunda bunu açıkça aramak istediğiniz
sll düğümü, sonuçta yeni benim tipim tanımının parçası isim,
ama sll düğümünü kullanamazsınız Bu ortasında.
Sebebi, ben değil Bir tür olarak adlandırılan sll düğümü oluşturdu
Burada bu son noktayı girene kadar.
Bu noktaya kadar, ben olmak zorunda Başka bir yolu, bu veri türü başvurmak için.
>> Ve bu bir kendini başvuru veri türü.
Bu, bir veri türü s Bir veri içeren bir yapı,
ve başka bir işaretçi Aynı tip yapısı.
Yani başvurmak gerekiyor Bu veri türü, en azından geçici olarak,
bu yüzden bir geçici vererek yapı sllist adı
Beni sonra bir istediğini söylüyorsun sağlar Başka bir yapı sllist için işaretçisi,
bir yapı sllist yıldızı ve daha sonra Ben tanımını tamamladıktan sonra,
Ben şimdi bu tür bir sll düğüm çağırabilirsiniz.
>> Orada olduğunu görmek yüzden de bu Burada geçici bir isim,
ama burada kalıcı bir isim.
Bazen görebilirsiniz yapısının tanımlar,
örneğin, söz konusu değildir Kendi kendine tutarlılığına, bu
Burada belirleyici isim yok.
Sadece, typedef struct söyleyebilirim küme ayracı açın ve bunu tanımlamak.
Sen Ama eğer yapı kendini tutarlılığına, bu biri olarak,
Bir belirtmeniz gerekir Geçici türü adı.
Ama sonuçta, şimdi Bunu yaptık,
biz sadece başvurabilirsiniz Bu düğümler, bu birimler,
amaçlar için sll düğümleri olarak Bu videonun geri kalanı.
>> Pekala, biz nasıl biliyoruz Bağlantılı bir liste düğümü oluşturmak.
Biz tanımlamak için biliyorum Bağlantılı liste düğümü.
Şimdi, biz başlatmak için gidiyoruz eğer bilgi toplamak için bunları kullanarak,
operasyonların bir çift var, biz anlamak ve çalışmak gerekiyor.
Biz nasıl oluşturulacağını bilmek gerekir ince hava dışarı bağlantılı liste.
Hiçbir liste zaten var ise, biz bir başlamak istiyorum.
Bu yüzden gerekiyor Bağlantılı bir liste oluşturmak için,
Biz muhtemelen aramanıza gerek Bağlantı listesi üzerinden
Aradığımız bir unsur bulmak için.
Biz eklemek gerekiyor listeye yeni şeyler,
Bizim liste büyümek mümkün olmak istiyorum.
Ve aynı şekilde, biz mümkün istiyorum Bizim listeden şeyleri silmek için,
Bizim liste küçültmek için mümkün olmak istiyorum.
Ve sonunda bizim programları, özellikle
biz olduğumuzu hatırlayacak olursak dinamik bellek ayırma
genellikle bu listeleri oluşturmak için, biz bu belleğin tüm serbest istiyorum
biz onunla çalışıyoruz bittiğinde.
Ve böylece biz silmek gerekiyor birinde bütün bağlantılı liste baskın başarısız.
Öyleyse üzerinden gidelim Bu operasyonların bazıları
ve biz onları görselleştirmek nasıl, Özellikle pseudocode kodunu konuşuyor.
Yani biz bir oluşturmak istiyorum Listeyi bağlantılı, bu yüzden belki biz
bir fonksiyon tanımlamak istediğiniz Bu prototip ile.
sll düğüm yıldızı, oluşturmak ve ben geçiyorum tek argüman, bazı keyfi veri
Bazı keyfi veri türünün yeniden yazın.
Ama bu fonksiyonu gerektiğini returning-- ediyorum Bir tek başlarına kadar, bana bir işaretçi döndürür
bağlantılı liste düğümü.
Yine, oluşturmak için çalışıyoruz ince hava dışarı bağlantılı liste,
bu yüzden bir işaretçi gerek Ben bittim bu liste.
>> Yani burada yer alan adımlar nelerdir?
Eh, ben ilk şey değilim yapacak dinamik olduğunu
yeni bir düğüm için yer tahsis eder.
Yine, biz ince dışına yaratıyorsunuz hava, bu yüzden biz bunun için malloc alana ihtiyacımız var.
Ve tabii ki, hemen Biz malloc sonra,
biz her zaman emin olmak için kontrol edin bizim pointer-- geri boş alamadım.
Biz denemek Çünkü eğer ve Bir null işaretçi deferense,
Biz acı gidiyoruz segfault ve bunu istemiyoruz.
>> Sonra alanı doldurmak istiyoruz, Biz değer alanını başlatmak istiyor
ve bir sonraki alana başlatılamadı.
Ve sonra biz sonunda kadar aşağıdaki amaçlara istiyorum İstediğimiz indicates-- fonksiyon prototipi
Bir sll düğüme bir işaretçi dönmek için.
Peki bu görsel gibi görünmesi?
Peki, ilk biz dinamik gidiyoruz Yeni sll düğümü için yer tahsis
bu yüzden de bu malloc-- görsel bir temsili
düğümün sadece oluşturdu.
Ve biz emin olmak için kontrol edin Bu, bu durumda null-- değil
resim olmazdı o boş olsaydı çoktan,
biz bellek tükendi olurdu bu yüzden oraya gitmek için iyi bir konum.
Yani şimdi biz C adıma konum, düğümleri değer alanını başlatmak.
Peki, bu fonksiyon dayalı Ben burada kullanıyorum çağrı
Ben 6'da geçmek istiyorum gibi görünüyor bu yüzden değer alanında 6 olacak.
Şimdi, bir sonraki alan başlatılamadı.
Peki orada yapacağım, hiçbir şey doğru, yanındaki var,
Bu listede tek şeydir.
Yani listedeki bir sonraki şey ne?
>> Bu doğru bir şey, işaret olmamalıdır.
Hiçbir şey bu kadar ne başka orada var biz bildiğimiz kavramı nothing-- var
hiçbir şey göstericiler?
Belki istediğimiz olmalı Orada bir null işaretçi koymak,
ve ben null adlı temsil edeceğiz , tıpkı kırmızı bir kutu işaretçisi
daha ileri gidemem.
Daha sonra biraz göreceğiniz gibi, biz sonunda zincirleri olacak
okların bağlanan Birlikte bu düğümler,
ama sen vurduğunuzda Kırmızı kutu, yani boş değil
biz herhangi bir daha gidemez Bu listenin sonu.
>> Ve son olarak, biz sadece istiyoruz Bu düğüme bir işaretçi döndürür.
Bu yüzden yeni arayacağım, ve yeni döndürür
bu nedenle de kullanılabilir ne olursa olsun işlevi yarattı.
Yani oraya gidiyoruz, biz bir tek başına oluşturduk havadan bağlantılı liste düğümü,
ve şimdi biz birlikte çalışabilir bir listesi var.
>> Şimdi, zaten biz diyelim Büyük bir zincir var,
ve biz de bir şeyler bulmak istiyorum.
Ve biz gidiyor bir işlev istiyorum , doğru ya da yanlış dönüş bağlı olarak
Bir değer bu listede olup olmadığını gör.
Bir fonksiyon prototipi, ya da Bu fonksiyon için beyanname,
bu-- bulmak bool gibi görünebilir, ve belki o zaman iki argüman geçmek istiyorum.
>> İlk, bir göstericidir Bağlantılı listenin ilk elemanı.
Bu olacak bir şey aslında Her zaman takip etmek istiyorsanız,
ve aslında bir şey olabileceğini Hatta genel değişken koymak.
Bir liste oluşturmak sonra, her zaman sen,
Çok takip etmek istiyorum listenin ilk elemanı.
Tüm diğer başvurabilirsiniz Bu şekilde Sadece zincir takip ederek elemanları,
işaretçiler tutmak zorunda kalmadan her elemana bozulmamış.
Sadece ilk kaydını tutmak gerekir tek hepsi bir arada zincirleme eğer.
>> Ve sonra ikinci şey Biz yine de geçiyoruz
keyfi some-- olduğunu ne olursa olsun veri türü we '
Orada arıyor içindedir Umarım listedeki düğümlerden biri.
Peki adımlar nelerdir?
Peki, bunu ilk şey Biz enine işaretçi oluşturmak
Listeler kafasına işaret.
Peki, neden, biz zaten yapacağız Listeler başında bir işaretçi,
Neden biz sadece etrafında o bir hareket etmiyor?
Eh, ben sadece dediğim gibi, Bizim için gerçekten çok önemli
Her zaman takip etmek Listede ilk unsur.
Ve böylece aslında iyi Bunun bir kopyasını oluşturmak için,
ve böylece biz asla hareket etmek kullanan Yanlışlıkla uzaklaşın, ya da her zaman biz
bazı noktada bir işaretçi Sağ listesinin ilk öğe üzerinde.
Yani bir oluşturmak için iyidir biz taşımak için kullanabilirsiniz ikincisi.
>> Sonra biz sadece olmadığını karşılaştırmak bu düğüm at değer alanı
o ise biz arıyoruz ve konum budur değil, biz sadece bir sonraki düğüme hareket.
Ve biz bunu yapmaya devam aşırı ve aşırı ve aşırı,
biz ya bulana kadar eleman, ya da biz vurmak
null-- biz sonuna ulaştınız ve listenin orada değildir.
Bu umarım bir zili gerekir Size tıpkı doğrusal arama,
Biz sadece bunu kopyalayan konum Bir tek başına bağlantılı liste yapısı
Bunun yerine bunu yapmak için bir dizi kullanarak.
>> Yani burada bir örnek Bir tek başına bağlantılı liste.
Bu, bir oluşmaktadır Beş düğümleri ve biz var
başkanına bir işaretçi Liste denir listesi.
Yapmak istediğimiz ilk şey Yine, bu kastetmek işaretçisi oluşturun.
Bu yüzden şimdi iki işaretçiler var Aynı şey bu nokta.
>> Şimdi, burada da fark ben yapmadım trav için herhangi bir yer malloc gerekiyor.
Ben trav malloc eşittir söylemedi bir şey, o düğüm zaten var
bellekte bu alan zaten var.
Yani aslında yapıyorum hepsi Bunun için başka bir işaretçi yaratıyor.
Ben ek mallocing değilim uzay, şimdi iki işaretçiler var
aynı şey işaret.
>> Yani 2 Ben arıyorum nedir?
Şey, hayır, bunun yerine ben bir sonrakine geçmek için gidiyor.
Böylece temelde söyleyebilirim trav yanındaki trav eşittir.
Ben hayır, aradığım şey 3 olduğunu.
Yani gitmeye devam yoluyla, sonunda kadar
Ben ne arıyorum olan 6 olsun işlev çağrısı dayalı için
Ben de var üstünde Orada, ve bu yüzden bitti.
>> Şimdi, eleman ne olmadığımı arıyorum, listede yok
Hala işe gidiyor?
Eh, liste fark Burada, ustaca farklı
ve bu var başka bir şey Bağlantılı listeleri önemli,
Eğer korumak zorunda değilsiniz Onları belirli bir sırayla.
İstersen, can ama Zaten fark etmiş olabilir
Biz takip değiliz Biz ne sayıda elemanı altındadır.
>> Ve bu bir ticaret tür olduğunu biz diziler ayetleri bağlantılı liste ile sahip
biz yok edilir Artık rasgele erişim.
Biz sadece ben istiyorum diyemem 0 öğeye gitmek için,
ya da benim dizi 6 elemanı, ki ben bir dizide yapabilirsiniz.
Ben gitmek istiyorum diyemem 0 unsur, ya da 6 eleman,
ya da benim bağlantılı liste 25 element, onlarla ilgili hiçbir indeks var.
Ve bu yüzden gerçekten önemli değil Biz sipariş listemize korumak durumunda.
Size isterseniz Kesinlikle olabilir ama orada
onlar gerek hiçbir neden herhangi bir sırayla korunmuş.
Yani yine deneyelim ve Bu listede 6 bulabilirsiniz.
Peki, biz başlayacak başlayarak biz, 6 bulmuyorum
ve sonra biz bulma devam 6, biz sonunda burada elde edene kadar.
Düğüme Yani şu anda trav noktaları 8 ihtiva eden, ve altı tane değildir.
>> Yani bir sonraki adım olacaktır Bir sonraki işaretçi gitmek için,
böylece trav yanındaki trav eşittir söylüyorlar.
Peki, trav sonraki belirtilir Orada kırmızı kutu, null.
Yani başka hiçbir yerde yok bu yüzden bu noktada gidin ve
biz ulaştık sonucuna varabiliriz bağlantılı liste sonu,
ve 6 orada değil.
Ve bu iade edileceği Bu durumda yanlış.
>> Tamam, nasıl bir yeni ekleyebilirim Bağlantılı liste halinde düğüm?
Yani biz oluşturmak mümkün oldum hiçbir yerden bir bağlantılı liste,
ama muhtemelen istiyoruz bir zincir oluşturmak olup
farklı listelerin bir demet oluşturmak.
Biz bir listesi var istiyorum bunun düğüm bir grup var
Tek bir düğüm ile listelerin bir demet.
Yani biz sadece Create kullanmaya devam edemez işlevi şimdi, daha önce tanımlanmış biz
Bir eklemek istiyorum zaten var listesi.
>> Bu durumda Yani, biz gidiyoruz iki argüman geçmek,
Bu başkanına işaretçi Biz eklemek istediğiniz listeyi bağlantılı.
Bu kadar neden Yine, işte Önemli hep biz o
Çünkü, bunun takip Gerçekten tek yolu var
Bütün liste başvurmak zorunda İlk elemana bir işaretçi tarafından.
Yani biz bir geçmek istiyorum Bu ilk elemana işaretçisi,
ve ne olursa olsun değer biz listeye eklemek istiyorum.
Ve sonunda bu işlev bir işaretçi geri gidiyor
Bağlantılı bir listenin yeni başkanı.
>> Burada yer alan adımlar nelerdir?
Peki, sadece oluşturmak olduğu gibi, Biz dinamik tahsis gerekir
yeni bir düğüm için yer ve olmak için kontrol emin olun biz bellek tüketmemek, yine
Biz malloc kullanarak çünkü.
Sonra doldurmak istiyoruz ve düğüm eklemek
yani numara koymak, ne olursa olsun val düğümün içine vardır.
Biz düğüm eklemek istediğiniz bağlantılı liste başında.
>> Bir sebebi var ben Bunu yapmak istiyorum ve bu
bir saniye alarak değer olabilir Burada videoyu duraklatmak için,
ve ben neden isteyeyim düşünmek Bağlantılı başında eklemek
listesi.
Yine, daha önce bahsettiğim Gerçekten değil bu
biz herhangi bunu korumak matter eğer Sipariş, belki bir ipucu.
Ve biz ne olacağını gördüm wanted aşağıdaki amaçlara ya da sadece bir saniyeden
önce biz ne zaman gittiğini arama yoluyla size
ne olabilir görebiliyordu Biz çalışıyoruz eğer olur
listenin sonunda eklemek için.
Biz yok çünkü Listenin sonuna işaretçisi.
>> Yani nedeni isteyeyim başında eklemek için,
Ben hemen yapabilirim çünkü.
Ben başında bir işaretçi var ve Biz ikinci bir görsel Bu görürsünüz.
Ama sonunda eklemek istiyorsanız, Ben, başında başlatmak zorunda
tüm yol travers son ve sonra tack.
Yani demek istiyorum listenin sonunda ekleyerek
n bir o olacak işletme, geri dönüyor
Bizim tartışma hesaplama karmaşıklığı.
Bu n operasyon, bir o olmak istiyorum Liste daha büyük ve daha büyük var gibi
ve daha büyük, daha olacaksın ve bir şey çakmak daha zor
sonunda üzerinde.
Ama her zaman gerçekten çok kolay başında bir şey tack,
Eğer başında hep sensin.
>> Ve biz yine bu görsel görürsünüz.
Ve sonra biz bir kez, bitti kez Biz yeni bir düğüm eklenir ettik
Biz bizim işaretçi dönmek istiyorum Bağlantılı bir listenin yeni başkanı, hangi
biz ekliyorsanız beri başlayarak aslında olacak
biz sadece oluşturduğunuz düğüme bir işaretçi.
Hadi bu görselleştirmek edelim Çünkü o yardım edeceğiz düşünüyorum.
>> Yani burada bizim liste, bu oluşur Dört element, bir düğüm, 15 içeren
hangi bir düğüme işaret , 9 ihtiva eder
13 içeren bir düğüme işaret, hangi içeren bir düğüme işaret
Null adlı vardır 10, sonraki işaretçi olarak işaretçi
böylece listenin sonuna geldik.
Yani biz bir eklemek istediğiniz değeri 12 ile yeni bir düğüm
Bu başında Liste, biz ne yapacağız?
Peki, ilk biz uzay malloc düğüm, ve sonra biz orada 12 koyun.
>> Yani şimdi biz ulaştık bir Karar noktası, değil mi?
Biz bir çift var göstericiler biz-ebil
biz ilk hangisinin hareket etmelidir hareket?
Biz 12 noktaya yapmalıyım list-- yeni başkanı
ya afedersiniz, biz 12 yapmak gerekir Listenin eski başkanı işaret?
Ya da söylemek gerekir Listede 12 de başlar.
Bir ayrım var Orada, ve biz bakacağız
hem bir saniye içinde ne de.
>> Ama bu yol açar kenar çubuğu için büyük bir konu,
ki bu biridir bağlantılı listeler ile trickiest şeyler
işaretçiler düzenlemek için bir Doğru sırayla.
Eğer sıra dışı şeyler taşırsanız, Yanlışlıkla sona erebilir
Listenin kalan orphaning.
Ve burada bir örnek.
Öyleyse fikri ile gidelim of-- Evet, biz sadece 12 yarattık.
Biz 12 olacak biliyorum Listenin yeni başkanı,
ve bu yüzden neden biz sadece hareket etmiyor Liste işaretçi orada işaret etmek.
>> Tamam, bu yüzden iyi.
Peki şimdi nereye 12 sonraki noktayı nedir?
Ben görsel olarak görebiliriz demek o 15'e işaret edeceğini,
İnsanlarda olduğu gibi bu bizim için gerçekten açıktır.
Nasıl bilgisayar biliyor?
Biz bir şey yok Artık 15 işaret, değil mi?
>> Biz 15 başvurmak için herhangi bir yeteneği kaybettik.
Yeni ok sonraki eşittir diyemeyiz bir şey, orada hiçbir şey yok.
Aslında, artık ettik Listenin geri kalanı
Bunu yaparken, biz ettik Yanlışlıkla zinciri kırıldı.
Ve biz kesinlikle bunu yapmak istemiyorum.
>> O yüzden geri dönüp tekrar deneyelim.
Belki doğru olanı yapmak için 12'nin bir sonraki işaretçi ayarlamak için
İlk listenin eski başkanı, o zaman listeyi üzerinde taşıyabilirsiniz.
Ve aslında, yani Doğru sipariş biz o
Biz olduğunuzda izlemeniz gerekir tek başına bağlantılı liste ile çalışıyor.
Biz her zaman bağlanmak istediğiniz listeye yeni bir unsur,
Biz bu tür çekmeden önce değişen önemli bir adım
nerede bağlantılı liste başıdır.
Yine, böyle bir temel şey, biz bunun izini kaybetmek istemiyorum.
>> Yani biz emin olmak istiyorum Her şey, bir arada zincirleme
biz bu işaretçiyi taşımak önce.
Ve böylece bu doğru bir düzen olacaktı, hangi listeye 12 bağlayacak,
Daha sonra liste 12 başladığını söylüyorlar.
Biz liste 12 başlar sözü ise ve Daha sonra, listeye 12 bağlanmaya çalıştı
biz zaten ne gördüm.
Biz yanlışlıkla listesini kaybedersiniz.
>> Tamam, bir şey daha hakkında konuşmak için.
Ne kurtulmak istiyorsanız Bütün bir defada listeyi bağlantılı?
Yine, mallocing konum Bütün bu alan, ve bu yüzden
İşimiz bitince onu serbest gerekir.
Yani şimdi silmek istiyor Tüm bağlantılı liste.
Peki, ne yapmak istiyorsun?
>> Biz boş gösterici ulaştınız, biz Aksi takdirde, sadece silin durdurmak istiyorum
ardından listenin geri kalanı ve beni serbest.
Listenin geri kalanını Sil ve sonra geçerli düğümü ücretsiz.
Gibi geliyor ne yapar, Ne tekniği konuştuk var
yaklaşık önceden gibi o ses nedir?
Daha sonra, herkesi Sil geri gelip beni silin.
>> Bu yineleme, biz yaptık Biraz daha küçük bir sorun,
Biz herkesi silmek söylüyorsun Başka, daha sonra beni silebilirsiniz.
Ve daha yolda, o düğüm herkesi silmek, diyecekler.
Ama sonunda biz alırsınız Liste boşsa nokta,
ve bu bizim temel durum var.
>> Yani bu bir göz atalım, ve bu işe nasıl.
Yani burada bizim liste, bu aynı şey biz sadece konuşuyorduk listesi
ve adımlar var.
Metnin bir sürü burada var ama umarım görselleştirme yardımcı olacaktır.
>> Yani biz have-- ve ben de çekti Bizim yığın kare resimde yukarı
Çağrı yığınları bizim video, ve umarım tüm bu
Birlikte neler gösterecek.
Yani burada bizim pseudocode kodu.
Biz bir null ulaşırsanız pointer, aksi halde, dur
Listenin geri kalanını silin Daha sonra şimdiki düğümü ücretsiz.
Yani şimdi, list-- Biz konum gösterici
geçen 12 puan yok.
12 bir boş gösterici değil, bu yüzden sen Listenin geri kalanını silmek için gidiyoruz.
>> Ne siliyor Bizi geri kalanı katılan?
Peki, bu yapmak anlamına gelir diyerek, yok etmeye çağrı
15 O başlangıcıdır Biz yok etmek isteyen listenin geri kalanı.
Ve böylece arama yok 12 beklemeye tür olduğunu.
O bekliyor, orada donmuş işini bitirmek için, 15 yok etmek diyoruz.
>> Peki, 15 bir boş gösterici değildir ve bu yüzden söylemek için gidiyor, tamam,
Evet, listenin geri kalanını silin.
Listenin geri kalanı başlar 9'da ve böylece biz sadece edeceğiz
Tüm silene kadar beklemeniz şeyler, sonra geri gelip beni silin.
Peki 9 iyi demek oluyor, Ben, bir boş gösterici değilim
yani buradan geri kalanını listesini silin.
Ve böylece denemek ve 13 yok.
13, ben boş gösterici değilim diyor Aynı şey, kova geçer.
10, 10 boş gösterici değil bir null işaretçi içerir,
ama 10 değil kendisi olduğunu boş hemen işaretçisi,
ve bu yüzden çok kova geçer.
>> Ve şimdi, orada puan listesi Gerçekten some-- işaret eder
Ben görüntüde daha fazla yer olsaydı, bazı rasgele alana işaret eder
Ne olduğunu bilmiyorum.
Gerçi boş gösterici var, liste kelimenin tam anlamıyla şimdi boş değerler var ayarlanır.
Bu doğru kırmızı kutu içinde işaret ediyor.
Biz bu yüzden, bir null işaretçi ulaştı biz durdurmak, ve biz bitirdik.
>> Ve böylece mor çerçeve de şimdi-- olduğunu Aktif çerçeve var stack-- üst,
ama bitti.
Biz boş gösterici ulaştınız, durun.
Biz bir şey yapmıyoruz biz Bir null işaretçi özgür olamaz,
biz herhangi malloc vermedi Uzay ve bu yüzden bitirdiniz.
Bu işlev çerçeve Yani tahrip ve biz bir
Biz kaldığımız yerden resume-- biz pick up Bir sonraki en yüksek biri ile kapalı olan
Burada bu koyu mavi çerçevedir.
Yani biz bıraktığı yerden devam.
Biz geri kalanı silindi liste zaten, şimdi biz konum
Geçerli düğüm serbest olacak.
Yani şimdi biz şimdi bu düğüm ücretsiz ve olabilir fonksiyonun sonuna ulaştınız.
Ve böylece fonksiyon çerçeve, tahrip ve biz açık mavi bir pick up.
>> Yani ben zaten done-- ettik dedi ki-- Listenin geri kalanını silme yani
Geçerli düğüm ücretsiz.
Ve şimdi sarı çerçeve geri yığının en üstüne.
Gördüğünüz gibi Ve böylece, biz şimdi sen Sağ taraftan Listeyi yok sola.
>> Ne olsa da, ne olurdu Biz şeyleri yanlış bir şekilde yapmış olsaydı?
Sadece biz çalıştığımızda gibi bir öğe eklemek için.
Biz eğer zincir, berbat eğer biz işaretçileri bağlamak vermedi
doğru sırayla, biz ise Sadece ilk elemanını serbest,
biz sadece serbest eğer Listenin başkanı, şimdi biz
başvurmak için hiçbir yolu yoktur Listenin geri kalanı.
Ve böylece biz olurdu yetim herşey,
Biz ne olurdu Bir bellek sızıntısı denir.
Bizim video hatırlayacak olursak dinamik bellek tahsisi,
Bu çok iyi bir şey değil.
>> Yani orada, dedi Birkaç işlemler şunlardır
biz çalışmaya kullanmanız gerekir etkili listeyi bağlantılı.
Ve sen, ben bir ihmal fark etmişsinizdir Bağlantılı tek bir eleman silme
listesi.
Ben yaptım sebebi Aslında bir tür olmasıdır
silme hakkında düşünmek zor Bir tek başına tek bir eleman
bağlantılı liste.
Biz üzerine atlamak gerekiyor listede, bir şey hangi
Biz point-- biz almak anlamına gelir Bu node-- silmek istiyor
ama sipariş biz öylesine yapmak herhangi bir bilgi kaybetmek yok,
Bu bağlamanız gerekir Buraya buraya düğüm.
>> Bu yüzden muhtemelen yanlış yaptım görsel açıdan.
Yani biz başında konum bizim Liste, biz ile işlem konum
Bu düğüm silmek istiyorum.
Biz sadece silerseniz Biz zinciri kırdım.
Burada bu düğüm her şey anlamına gelir,
o burada üzerinde zincirini içerir.
>> Yani biz aslında yapmamız gereken Bu noktaya aldıktan sonra,
biz bir geri adım gerekiyor ve bir Bu düğümün bu düğümü üzerinde bağlantı,
bu yüzden o silebilirsiniz Ortadaki.
Ama tek başına bağlantılı listeler yok Bize geriye doğru gitmek için bir yol sağlar.
Yani biz ya tutmak gerekir İki işaretçiler ve bunları taşımak
kapalı adımın tür arkasında biri Diğer gidiyoruz, ya da bir noktaya olsun
ve daha sonra başka bir işaretçi aracılığıyla gönderebilirsiniz.
Ve sen, bunu gördüğünüz gibi biraz dağınık alabilirsiniz.
Neyse ki, biz var başka bir yolu olduğunu çözmek için,
biz iki kat bağlantılı listeleri hakkında konuşmak.
>> Ben Doug Lloyd değilim, bu CS50 olduğunu.