>> [MÜZİK OYUN]
>> ANDI PENG: bölümün 6. haftada hoş geldiniz.
Biz bizim standart sapma Salı bölüm süresi
bu güzel Pazar sabahı öğleden sonra.
Herkes için teşekkür ederiz o Bugün, fakat beni ciddiye katıldı
alkış yuvarlak.
>> Bu oldukça büyük bir çaba.
Neredeyse bile did not make it zaman içinde, ama Tamam oldu.
Bu yüzden sana bu hepimiz biliyoruz Sadece sınav için yaptık.
Her şeyden önce, hoş geldiniz Bunun flip tarafında.
>> İkincisi, biz bunun hakkında konuşacağım.
Biz sınav hakkında konuşacağım.
Biz nasıl bahsedeceğiz Sınıfta yapıyoruz.
İyi olacaksın.
Ben senin sınavlar için var Burada sonunda sen,
böylece siz almak istiyorsanız a, ona tamamen iyi bak.
>> Yani çabuk, başlamadan önce aşağıdaki gibi bugün gündem.
Gördüğünüz gibi, biz konum temelde hızlı pişirim
veri yapılarının bir sürü ile Gerçekten, gerçekten, gerçekten hızlı.
Gibi Yani, bu olmayacak Süper interaktif bugün.
Bu sadece bana biraz bağırarak olacak şeyler ve ben sizi şaşırtmak eğer,
Çok hızlı gidiyorsam, bana haber ver.
Onlar sadece çeşitli veri konum yapıları ve bir parçası olarak
Bu için pset arasında Yaklaşan hafta, olacak
Bunlardan birini uygulamak için istenir, Belki de, iki tanesi them-- iki
senin pset içinde.
Tamam, bu yüzden sadece gidiyorum Bazı duyurular ile başlar.
Biz yığınlar ve daha sıralarında üzerinden gidersiniz Biz sınav öncesi ne yaptığını daha derinlik.
Biz gidip bağlantılı olacak Yine, bir kez daha listelemek
daha derinlemesine daha fazla ne Biz sınav öncesi vardı.
Ve sonra karma bahsedeceğiz tablolar, ağaçlar ve çalışır, hangi
Tüm pset için oldukça gereklidir.
Ve sonra bazı üzerinden gidersiniz pset5 için yararlı ipuçları.
>> Tamam, bu nedenle sınav 0.
Ortalama% 58 idi.
Bu çok düşük ve bu yüzden hepiniz uygun çok iyi yaptı
Bununla.
>> Sen eğer Hemen hemen, başparmak kuralı olduğunu ortalamanın bir standart sapma olan
biz daha az konum beri özellikle rahat bölüm, tamamen iyiyiz.
Sen yoldasın.
Hayat güzeldir.
>> Ben o düşünmek korkutucu olduğunu biliyorum Ben bu quiz bir% 40 gibi aldım.
Ben bu sınıfı başarısız gidiyorum.
Sana söz veriyorum, sen değilsin sınıf başarısız olacak.
Tamamen iyisin.
>> Üzerinde var kim o sizin için Ortalama etkileyici, etkileyici,
gibi ciddi aferin.
Yanımda onları var.
Onları gelip çekinmeyin bölümün sonunda.
Eğer varsa bana bildirin konular, onlarla sorular.
Biz puanınızı kadar eklerseniz Yanlış, lütfen bize bildirin.
>> Tamam, pset5 yüzden, bu gerçekten anlamda Yale için garip bir hafta
Bizim pset bağlı olduğu Dahil olmak üzere öğle saatlerinde Çarşamba
Geç bir gün, bu yüzden aslında öğle saatlerinde Salı teorik nedeniyle.
Muhtemelen hiç kimse bitmiş öğle saatlerinde Salı günü de.
Bu tamamen iyi.
Biz ofis saatleri için gidiyoruz Bu gece aynı zamanda Pazartesi gecesi.
Ve tüm bölümleri bu hafta olacak aslında atölye haline,
bu yüzden pop çekinmeyin İstediğiniz bölüm,
ve onlar tür mini pset olacak Bu konuda yardım için atölyeler.
Böylece örneğin, bu tek bölümdür nerede malzeme öğretim ediyoruz.
Tüm diğer bölümler odaklama olacak münhasıran pset için yardımına.
Evet?
>> HEDEF KİTLE: Nerede çalışma saatleri nelerdir?
>> ANDI PENG: Ofis saatleri oh iyi bir soru geceden.
Bence çalışma saatleri gece Teal ya Commons altındadır.
Online CS50 kontrol edin ve ofis saatleri gitmek
Bir zamanlama olması gerektiğini Bunların hepsi size söyler.
>> Bu gece ya biliyorum ya da yarın teal olduğu
ve ben olabilir düşünüyorum Geçen gece için commons.
Emin değilim.
İyi soru.
CS50 kontrol edin.
>> Ilgili Serin, herhangi bir sorunuz Üç gün gibi gelecek için zamanlama?
Ben David gibi adamlar söz Bu tepenin üst olduğunu söyledi.
Sizler neredeyse vardır.
Sadece üç gün daha.
Oraya, ve sonra hepimiz aşağı geleceğiz.
Biz güzel bir CS-serbest mola olacak.
Tekrar hoş geldin.
Biz web dalmak programlama ve geliştirme,
çok eğlenceli şeyler karşılaştırıldığında Diğer psets bazı.
Ve bu soğuk olacak ve Biz eğlenceli olacak.
Biz daha fazla şeker gerekecek.
Şeker için özür dilerim.
Ben şeker unuttum.
Bu kaba bir sabah oldu.
Yani siz, neredeyse orada ve ben sizlerle gurur duyuyorum.
>> Tamam, bu yüzden yığınları.
Kim Jack ilgili soruyu sevdim ve sınavda onun giyim?
Hiç kimse?
Tamam sorun değil.
>> Yani aslında olabildiğince Resmi Jack, burada bu adam,
giysi almak için seviyor yığının en dışında,
ve o üzerine geri koyar kendisinden sonra yığını bitti.
Yani bu şekilde, o asla almak gibi görünüyor
tabanına Onun giyim yığını.
Yani bu tür açıklar temel veri yapısı
Bir yığın uygulanmaktadır nasıl.
>> Esasen, bir düşün nesnelerinin herhangi yığını olarak yığını
Eğer tepesine şeyler koymak, ve nerede sonra üst onları dışarı pop.
Yani LIFO biz gibi kısaltma Son In First Out use-- için.
Ve böylece üstüne de son Yığın çıkar ilk biridir.
Ve böylece iki terim Biz ilişkilendirmek istiyorum
Bununla push ve pop denir.
Ne zaman üzerine bir şeyler itmek yığını ve geri pop.
>> Ve bu yüzden bu bir tür olduğunu tahmin o sizin için soyut bir kavram
Kim bir gibi görmek istiyorum Bu gerçek uygulaması
Gerçek dünyada.
Kaçınız bir kompozisyon yazdım Belki bir saat gibi, nedeniyle önce
ve yanlışlıkla silinen büyük yanlışlıkla gibi o yığın?
Ve sonra ne kontrol yapmak Biz geri koymak için kullanabilirsiniz?
Kontrol-Z, tamam mı?
Kontrol-Z, bu kez miktarı Kontrol-Z hayatımı kurtardı ki,
Her zaman kıçımı kurtardı Bu bir yığın aracılığıyla uygulanmaktadır oluyor.
>> Esasen tüm bilgiler Bu, Word belgenizi üzerinde bulunuyor
o itti ve irade attı alır.
Ve böylece esasen zaman sizi bir şey silmek, yukarı geri pop.
Ve sonra tekrar ihtiyacınız varsa, size Control-C ne olduğu, itin.
Ve böylece gerçek dünya fonksiyonu ne kadar basit veri yapısının
günlük hayatınızda yardımcı olabilir.
>> Bu yüzden, bir yapı yoludur biz aslında bir yığın oluşturun.
Daha sonra struct tanımlamak yazın ve biz alt yığını diyoruz.
Ve yığınının içinde, iki parametre vardır
Biz esas olarak işleyebilirsiniz bu yüzden Char yıldız dizeleri kapasitesine sahiptir.
>> O yapıyor Tüm bu bir dizi yaratıyor
Biz ne istersen saklayabilir hangi biz onun kapasitesini belirleyebilir.
Kapasite sadece maksimum miktarı mı öğeleri bu diziye koyabilirsiniz.
int boyutu tutan counter Kaç öğelerin iz şu anda
yığınında.
Öyleyse biz, A, takip edebilirsiniz hem gerçek yığın ne kadar büyük,
ve A, B, nasıl yığının kadar biz istemiyoruz çünkü biz doldurdu
Bizim kapasitemiz ne üzerinde taşma.
>> Örneğin, bu güzel yüzden Soru senin sınav oldu.
Esasen nasıl itmek yapmak Bir yığının en üstüne.
Oldukça basit.
Bunu bakarsanız, Bu doğru yürüyeceğiz.
[Duyulamaz] size-- ise ne zaman, hatırlıyorum
Herhangi bir erişmek istiyorsanız bir yapı içinde parametre,
Eğer struct.parameter adını yapın.
>> Bu durumda, s Bizim yığının adı.
Biz boyutunu erişmek istiyorsanız o, bu yüzden s.size yapmak.
Boyutu değil Yani sürece kapasitesi ya da uzun eşit
o kapasitesinden daha az olduğu gibi, ya burada çalışacak.
>> Sen içini erişmek istiyorsanız destenizin, s.strings yüzden,
ve bu yeni numara koymak için gidiyoruz Orada eklemek istediğiniz.
Sadece biz isteyeceksiniz diyelim yığına int n takın,
biz s.strings yapabiliriz parantez, s.size n eşittir.
Boyut nerede Çünkü Şu anda, yığında
Biz itmek için gidiyoruz o, biz sadece erişim
boyutu her yerde, Yığının mevcut dolgunluk,
ve biz onun üzerine int n itin.
Ve sonra biz emin olmak istiyorum daha da, n boyutunu artırma konum
biz ettik ve bu yüzden takip edebilirsiniz yığına ekstra bir şey eklendi.
Şimdi daha büyük bir boyutu var.
Bu burada mantıklı mı Herkes, ne mantıksal çalışıyor?
Bu tür hızlı oldu.
HEDEF KİTLE: Eğer üzerine gidebilir miyim s.stringss.strings [s.size] Yine?
ANDI PENG: Tabii, yani ne yapar bize vermek şu anda s.size?
HEDEF KİTLE: Bu geçerli boyutu var.
ANDI PENG: Kesinlikle, bu yüzden bizim boyut olan akım indeksi,
ve bu yüzden yeni bir tamsayı koymak istiyorum Biz s.size eklemek istediğiniz.
bu mantıklı mı?
S.strings için, tüm bu olan dizinin adıdır.
O Tüm erişen olduğunu Bizim yapı içinde dizi,
ve bu yüzden isterseniz Bu dizine n koyun,
biz sadece erişebilirsiniz kullanarak parantez s.size.
Güzel.
>> Pekala, pop, ben onu pseudocode Sizinle, ancak benzer kavram için.
bu mantıklı mı?
Boyutu büyük olduğu takdirde Daha sonra sıfır, daha sen
Eğer bir şey almak istiyorum biliyor dışarı boyutu değil çünkü eğer
sıfırdan büyük, o zaman yığınında bir şey yok.
>> Yani sadece çalıştırmak istediğiniz Bu kod, sadece can
pop şey varsa pop.
Boyutu büyükse yüzden 0'dan, biz eksi boyutu.
Biz boyutunu azaltma ve daha sonra iade Çünkü bunun içinde ne olursa olsun
haşhaş, biz istiyoruz depolanır ne olursa olsun erişim
yığının üst endekste.
Her şey mantıklı?
Yaptığım Eğer siz, bu yazmak Siz bunu yazmak mümkün olurdu?
Tamam, siz onunla oynayabilir.
Endişeye gerek yok bunu alamadım eğer.
Biz kod zamanımız yok dışarı bugün ettik çünkü
Bu yapıların bir sürü var geçmesi, ama aslında için
pseudocode, çok, çok benzer itmek.
Sadece mantık birlikte izleyin.
Tüm erişen emin olun doğru yapı özellikleri.
Evet?
>> HEDEF KİTLE: Will bu slaytlar ve Bu her şeyi yukarı bugün-ish olacak?
ANDI PENG: Her zaman, evet.
Ben koymak için denemek için gidiyorum Bu kadar sonra bir saat gibi.
David'i e-posta göndereceğiz, David çalışacağız Bu bir saat sonra gibi koyun.
>> Tamam, öyleyse biz bu diğer taşınmak güzel veri yapısı bir kuyruk çağırdı.
Siz burada görebileceğiniz gibi, bir Kuyruk, aramızda İngilizler için,
o bütün bir çizgidir.
Yani aykırı Ne Eğer, bir yığın olduğunu düşünüyorum
bir sıra tam ne olduğunu mantıksal Ne olduğunu düşünüyorum.
Bu, FIFO kurallarına göre düzenlenen oluyor Hangi İlk olarak, Birinci Out.
İlk iseniz sıralı bir, sen
Bunlardan ilki çizgi çıkıyor.
>> Yani biz bu aramak için ne gibi dequeueing ve kuyruğa alınmasından olduğunu.
Biz bir şey eklemek istiyorsanız Bizim kuyruğa biz enqueue.
Biz isterseniz sıradan çıkarma, ya da almak bir şey uzakta, biz sıradan çıkarma.
>> Biz tür konum Yani aynı anlamda Sabit boyutlu unsurları oluştururken biz
Belirli saklayabilirsiniz şeyler, ama biz de can
biz yerleştirerek nereye değiştirmek bunların içinde parametreler
ne türüne göre işlevselliği, biz istiyoruz.
Yığınlar Böylece, son aranan biri, N ilki dışında olmak.
Kuyruk ilk şey istediğim dışarı ilk şey olması.
>> Yapı tipi Yani Gördüğünüz gibi, tanımlar,
o biraz farklı yığını neydi
Sadece biz tutmak zorunda değil, çünkü boyutu şu anda nerede parça,
biz de başın izlemek isteyen yanı sıra nerede biz şu anda.
Yani kolay olduğunu düşünüyorum Ben bu kadar çizerseniz.
Yani biz bir sıra var düşünelim, bu yüzden başı sağ burada diyelim.
Hat başı, haydi Sadece, orada şu anda söylemek
ve biz eklemek istediğiniz kuyruğuna bir şey.
Ben esasen boyutunu arayacağım kuyruk aynı şey,
senin kuyruk olduğu her yerde sonu.
Sadece boyutu tam burada diyelim.
>> Peki nasıl bir fizibil yok bir sıra içine bir şey eklemek?
Ne endeks biz yerleştirmek istiyoruz nereye eklemek istiyoruz.
Bu başlangıcı ise senin Sıraya ve bu onun sonu
ya da boyutu, nerede biz yapmak Bir sonraki nesne eklemek ister misin?
>> HEDEF KİTLE: [duyulamaz]
ANDI PENG: Kesinlikle, eklemek istediğiniz bağlı o bunu yazdım.
Ya bu boş ya da boş.
Yani muhtemelen eklemek istediğiniz Çünkü burada boyut o-- ise
Bunların hepsi doluysa, istediğiniz Doğru, burada eklemek için?
>> Ve böylece, çok, çok süre Basit, değil oldukça her zaman doğru
Ana fark nedeniyle Bir kuyruk ve bir yığın arasındaki
Bu kuyruk can olduğunu aslında manipüle edilebilir
Böylece kafa değişiklikleri İstediğiniz yere bağlı
senin işaretin başlangıcı başlatın.
Ve sonuç olarak, senin kuyruk Ayrıca değişecek.
Ve böylece bir göz atın Şu anda bu kodu.
Siz de istendi gibi enqueue, sınavda yazmak.
Belki biz neden konuşmak edeceğiz Cevap ne oldu oldu.
>> Oldukça, biri bu çizgiyi uygun olamazdı kod ama aslında bu parça
bir satırda olmalıdır.
30 saniye gibi harcayın.
Bir göz atın ve neden görmek işte bu yoldur.
>> Çok, çok benzer yapı, çok, çok Önceki benzer yapı
belki hariç yığını bir satır kod.
Ve bir satır kod olduğunu özelliğe belirler.
Ve gerçekten ayıran bir yığın bir kuyruk.
>> Herkes bir bıçak almak istiyorum Eğer ettik niye açıklayan
Burada bu karmaşık bir şey var mı?
Biz dönüşünü görmek için bizim harika arkadaşım modülü.
Siz yakında gelecek gibi programlama tanımak,
Neredeyse her zaman sen lüzum bir şey bir şey sarmak için,
modülü bunu yapmak için bir yol olacak.
Yani bilerek, kimse istemez kod bu hattı açıklayan denemek için?
Evet, bütün cevaplar Kabul ve hoş geldiniz.
HEDEF KİTLE: Benimle mi konuşuyorsun?
ANDI PENG: Evet.
HEDEF KİTLE: Oh, hayır üzgünüm.
ANDI PENG: Tamam, atalım Bu kod üzerinden yürümek.
Peki ne zaman çalışıyorsun bir sıra üzerine bir şey eklemek,
Kafa olur o güzel durumda Burada olmak, bu bizim için çok kolay
Sadece sonuna gitmek için Doğru bir şey eklemek?
Ama sıranın tüm noktasıdır Bu can aslında dinamik kafa
yere bağlı olarak değişiklik biz Bizim q başlangıcı olmak istiyorum,
ve, kuyruk gibi Ayrıca değişecek.
>> Ve böylece bu olmadığını hayal Sıraya değil, bu kuyruk oldu.
Kafası tam burada diyelim.
En bizim kuyruk bu gibi görünüyordu diyelim.
Nereye kaydırmak isteseydim hattın başlangıcı olan
en biz başını değiştirdi diyelim Bu şekilde ve burada boyutları.
>> Şimdi bir şey eklemek istiyorum Bu kuyruk, ama siz gördüğünüz gibi,
Sadece kadar basit değil boyutu sonra ne olursa olsun eklemek
o zaman tükendi çünkü Bizim asıl dizinin sınırları.
Biz gerçekten eklemek istediğiniz burada.
Bu bir kuyruğa güzelliği Bu görsel, bize olan
çizgi böyle gider gibi görünüyor ancak veri yapısında depolanan zaman
Onlar bir döngü gibi vermek.
Bu tür sarar ön aynı yolu
Bir satır da sarın ki etrafında her yerde sizi bağlı
olmak üzere satırın başına istiyoruz.
Ve böylece biz alırsak Buraya bak, diyelim
Biz yaratmak istedik ki Fonksiyon enqueue denir.
Biz o q içine int n eklemek istedim.
Q.size bizim veri olduğunu arayacağım q-- Eğer Bizim queue.size yapmazsa structure--
kapasite veya eğer eşit bu kapasitenin daha az var
q.strings bizim q içinde dizidir.
Biz ayarlamak için gidiyoruz Bu q.heads eşit,
Hangi burada, artı q.size kapasitesi ile modülü olan
Buralarda bize geri sarın.
>> Bu örnek, endekste Yani Başın sağ, 1 mi?
Boyutta endeksi 0, 1, 2, 3, 4'tür.
Yani biz 1 artı 4 modülü yapabilirsiniz 5 bizim kapasitesi.
Ne bizi veriyor?
Indeks nedir bu Bu çıkıyor?
>> HEDEF KİTLE: 0.
>> ANDI'nin PENG: 0, burada Burada olur,
ve bu yüzden mümkün olmak istiyorum Burada eklemek için.
Ve böylece bu denklem burada tür sadece herhangi bir numaraları ile çalışır
yere bağlı olarak sizin Baş ve boyutu vardır.
Ne o biliyorsanız şeyleri bilirsin vardır
Tam olarak eklemek istediğiniz yeri ne olursa olsun kuyrukta peşinde.
Bu herkese mantıklı mı?
>> Ben bir beyin tür biliyorum teaser yana özellikle bu
senin sınav sonrasında geldi.
Ama umarım herkes Şimdi anlayabiliyorum
Neden bu çözüm ya da bu fonksiyonu olan yoldur.
Herkes biraz bu konuda belirsiz?
TAMAM.
>> Ve şimdi, eğer Bu sıradan çıkarma istedi
Bizim baş kayması olacağını nerede Biz sıradan çıkarma olsaydı, çünkü
Biz q ucunu yapmayız.
Biz doğru, baş çıkarmak istiyor?
Bu nedenle sonuç olarak, kafa değişecek, Eğer enqueue zaman neden o olduğunu
Eğer takip etmek lazım nerede başınızı ve boyut
eklemek için muktedir olan doğru pozisyona.
>> Ve böylece sıradan çıkarma yaparken, Ben de bunu Pseudocode.
İstersen çekinmeyin Bu dışarı kodlama girişimi için.
Haklısınız, kafa taşımak istediğiniz?
Ben sıradan çıkarma isteseydim, ben kafa üzerinde hareket edeceklerdi.
Bu kafa olurdu.
>> Ve bizim geçerli boyutu olur çıkarma çünkü biz artık
Dizideki dört element var.
Biz sadece üç ve daha sonra istediğimiz içinde saklanır ne olursa olsun dönmek
Başın bu almak istiyorum çünkü yığına yüzden çok benzer değer dışarı.
Sadece alıyorsun başka bir yerden,
ve size işaretçi atamak zorunda Sonuç olarak farklı bir yere.
Mantıken, herkes takip edin?
Büyük.
>> Tamam, bu yüzden biz biraz konuşacağız bağlantılı listeler hakkında daha derinlemesine
Onlar çok değerli olacak çünkü Bu hafta en seyri sizin için
psets.
Bağlı listeler, olarak siz hepsi vardır, hatırlıyorum
Belirli bir düğüm olan düğümlerin Bir değer ve bir işaretçi hem değerleri
Bu birbirine bağlanmıştır Bu işaretçileri tarafından.
Nasıl Ve böylece yapı Burada bir düğüm biz oluşturmak
olan int n var ne olursa olsun Bir mağaza veya dize n değeri
veya istediğiniz ne olursa olsun karakter yıldız n, diyoruz.
Göstericidir Struct düğüm yıldızı, Her düğüm olmasını istiyorum,
Bunu zorunda gidiyoruz Bir sonraki doğru işaretçi noktası.
Sen başını olacak olan bir bağlantılı liste
geri kalanı için işaret edecek böylece ve benzeri değerler
sonunda sonuna ulaşana kadar.
Ve bu son düğümü adildir bir işaretçi yok olacak.
Bu işaret için gidiyor null, ve o zaman var
Eğer isabet biliyorum Bağlantılı listenin sonunda
zaman son işaretçi bir şey işaret etmiyor.
>> Bu yüzden daha fazla biraz gitmek için gidiyoruz ilgili derinliği nasıl bir olasılıkla olur
Bağlantılı bir liste arayın.
Bazı hatırla Bağlantılı listelerin sakıncaları
aramalar ile ilgili bir dizi ayet.
Bir dizi yapabilirsiniz ikili arama, ancak Neden bir bağlantılı listede bunu yapamam?
>> HEDEF KİTLE: hepsi bağlı Çünkü, ama oldukça nerede bilmiyorum
[Duyulamaz].
>> ANDI PENG: Evet, aynen öyle hatırlıyorum Bu bir dizi parlak
Biz olmasıydı rasgele erişim belleği nerede
Ben endeks değeri isteseydi Altı, ben sadece endeks altı söyleyebiliriz
Bana o değer vermek.
Diziler sıralanır çünkü Ve bu bir ardışık bellek alanda
tek bir yerde, oysa bağlantılı listeler tür
olan rastgele etrafında serpiştirilmiş ve tek yolu birini bulabilirsiniz
bildiren bir işaretçi aracılığıyla sonraki düğüm nerede adresi.
>> Böylece sonuç olarak, tek yolu Bağlantılı bir liste içinde arama yapmak için
doğrusal arama motorudur.
Ben tam olarak nerede olduğunu bilmiyorum çünkü Bağlantılı listede 12. değerdir
Ben bütününü hareket ettirmek zorunda Bu bağlantılı liste biri
ilk düğümü tırnağa tek, ikinci düğüme üçüncü düğüm,
Sonunda elde edene kadar tüm yol aşağı Ben arıyorum o düğüm olduğu için.
Ve böylece bu anlamda, arama Bağlantılı bir listede her zaman n.
Her zaman n var.
Lineer zaman içinde hep.
>> Ve böylece kod hangi Bunu uygulamak ve bu
Senin beri sizin için biraz yeni adamlar gerçekten hakkında ya da hiç konuşmadık
nasıl görülen göstericiler işaretçileri üzerinden arama,
bu yüzden doğru yürüyeceğiz Bu çok, çok yavaş.
Yani bool arama, sağ, en istediğimiz düşünelim
adında bir işlevi oluşturmak için true döndürür arama
bağlantılı içinde bir değer bulursa listelemek ve aksi takdirde false döndürür.
Düğüm yıldız listesi Şu anda sadece işaretçi
Bağlantılı listedeki ilk öğeye.
int n sen değerdir Bu listede arıyor.
>> Yani düğüm yıldızı işaretçi listesi eşittir.
Yani biz ayarı demektir ve bir işaretçi oluşturma
Listenin içinde ilk düğüme.
Benimle herkes?
Biz gitmek için olsaydı Yani Buraya, ben olurdu
işaret eden bir işaretçi başlatıldı Kafa ne olursa olsun o listesidir.
>> Ve sonra, buraya bir kez olsun işaretçi eşit boş değil ise,
böylece biz hangi döngü geçme sonradan olacak
çünkü ne bizim listesinin geri kalanı işaretçi boş eşittir ne olur?
Biz have-- biliyoruz
>> HEDEF KİTLE: [duyulamaz]
>> ANDI PENG: Kesinlikle, bu yüzden biz biliyoruz biz doğru listenin sonuna ulaştınız?
Buraya geri gitmek, her düğüm bir düğümden diğer işaret edilmelidir
ve benzeri ve benzeri sonunda vurmak kadar
Bağlantılı listenin kuyruk, hangi bir gösterici olduğunu sadece
Hiçbir dışında herhangi bir yerde işaret etmiyor.
Ve böylece temelde biliyor listenizi hala orada olduğunu
işaretçi eşit değildir kadar Boş null eşittir çünkü bir kez,
Eğer daha fazla şeyler olduğunu biliyorum.
>> Yani biz konum hangi döngü Gerçek aramayı zorunda olacak.
Ve pointer-- görmek yaparsanız Orada ok fonksiyonu bu tür?
Yani işaretçi noktaları eğer n, eğer n eşittir n at gösterici,
böylece anlamına eğer sen işaretçi
Her ucunda aramaya düğüm değeri aslında eşittir
Eğer, aradığınız true dönmek istiyorum.
Yani temelde, sen bir düğüm konum eğer , aradığınız değeri vardır
Eğer oldum biliyorum Başarıyla arama yapabilmek.
>> Aksi takdirde, ayarlamak istediğiniz Bir sonraki düğüme için işaretçi.
Burada bu hat yapıyor budur.
Pointer yanındaki işaretçi eşittir.
Bu çalışma nasıl herkes görüyor musun?
>> Ve esasen sen gidiyorsun sadece listenin tamamını travers
işaretçinizi her zaman kadar sıfırlama sonunda listenin sonuna çarptı.
Ve hiç olduğunu biliyoruz Daha fazla düğüm, arama yapmak
ve daha sonra sahte dönebilirsiniz Bildiğiniz çünkü, o kadar iyi, oh,
Ben aramak mümkün oldum eğer Listenin tamamı ile.
Bu örnekte, ben istedim 10 değerine bakmak için,
ve ben başında başlayacak ve Ben, tüm yol aşağı arama
ve ben sonunda bu var olan null işaret eden bir işaretçi,
Ben değil, bok, ben 10 sanırım biliyorum Bu liste onu bulamadım çünkü.
Ve ben listenin sonunda değilim.
Ve bu durumda bildiğiniz Ben return false gidiyorum.
>> Bu biraz için emmek edelim.
Bu güzel olacak senin pset için önemli.
Bunun mantığı, belki de çok basittir sözdizimsel sadece uygulanması.
Siz yapmak istiyorum anlamak emin olun.
Güzel.
>> Tamam, bu yüzden nasıl olurdu Doğru, düğümler ekleyerek,
bir liste halinde Çünkü hatırlıyorum Ne yararları nelerdir
bir bağlantılı liste karşı olan depolama açısından bir dizi?
>> HEDEF KİTLE: Dinamik değil, bu nedenle daha kolay aşağıdaki amaçlara
>> ANDI PENG: Kesinlikle, bu yüzden, dinamik var olan
genişletmek ve daraltmak anlamına gelir Kullanıcının ihtiyaçlarına bağlı.
Ve böylece, bu anlamda biz ihtiyacımız yok Gereksiz bellek atık çünkü ben
Ben istediğim kaç değer bilmiyorsanız saklamak için, bu benim için mantıklı değil
Bir dizi yüzünden oluşturmak için Ben 10 değerlerini depolamak istiyorsanız
ve ben 1000 bir dizi, işte oluşturmak boşa belleğin bir sürü ayrılan.
Biz bağlantılı kullanmak istiyorsanız bu yüzden Liste dinamik muktedir
değiştirmek veya boyutunu küçültmek.
>> Ve böylece ekleme yapar biraz daha karmaşık.
Biz rastgele unsurları erişemiyor yana Biz bir dizi cekti yolu.
Ben bir öğe eklemek istiyorsanız Yedinci dizine,
Ben sadece bunu ekleyebilirsiniz Yedinci dizine.
Bağlı listesinde, öyle değil oldukça kolay çalışmak,
ve bu yüzden eklemek istedim bağlantılı liste burada bir,
görsel, bunu görmek çok kolay.
Biz sadece, orada eklemek istiyorum Sağ listenin başında,
Sağ baş sonra.
>> Ama biz var olan yolu yeniden atamak için işaretçileri biraz kıvrık olan
ya da, mantıksal, o mantıklı ama Eğer buna sahip olduğundan emin olmak istiyorum
Tamamen aşağı çünkü istediğiniz son şey
bir işaretçi yeniden atamak için Burada yapıyoruz yolu.
Eğer inceleyebilirsiniz 1 tırnağa işaretçisi,
daha sonra aniden The tüm Bağlantılı listenin geri kalanı
Eğer aslında çünkü kaybolur Geçici bir şey oluşturulur.
Yani 2'ye işaret ediyor.
Eğer pointer, yeniden atarsanız Listenizdeki geri kalanı tamamen kaybolur.
Yani olmak istiyorum Burada çok dikkatli
İlk atama sizden ne olursa olsun işaretçi
her yerde içine eklemek istediğiniz İstediğiniz ve sonra seni
Listenizdeki geri kalanı inceleyebilirsiniz yapabilirsiniz.
>> Yani bu her yerde için de geçerli Eğer eklemek için çalışıyoruz.
En eklemek istiyorsanız Baş, burada cevap vermek istiyorsanız,
En eklemek istiyorsanız sonunda, iyi, bitiş I
Sanırım sadece olur Hiçbir işaretçi var, ama
Bunu yapmazsanız emin olmak istiyorum Listenizdeki geri kalanını kaybeder.
Her zaman emin olmak istiyorum Yeni düğüm işaret ediyor
ne olursa olsun doğru sen içine eklemek istediğiniz,
ve daha sonra üzerinde zincirleme ekleyebilirsiniz.
Herkes açık?
>> Bu olacak Gerçek konulardan biri.
En önemli konulardan biri Eğer pset üzerinde zorunda gidiyoruz
oluşturmak için denemek için gidiyoruz olduğunu bağlantılı liste ve insert şeyler
ama sonra sadece kaybetmek Bağlantılı listenin geri kalanı.
Ve sizin gibi olmak için gidiyoruz, ben Bu neden oluyor bilmiyorum?
Ve geçmesi için bir ağrı var ve işaretçileri tüm arayın.
>> Ve ben bu pset size garanti, Bu düğümler dışarı yazma ve çizim
çok, çok yararlı olacaktır.
Yani tamamen takip edebilirsiniz Tüm işaretçiler nerede,
ne yanlış gidiyor Tüm düğümler nerede,
erişmek için yapmanız gerekenleri veya eklemek veya silmek veya bunlardan herhangi.
Bu iyi Herkes?
Güzel.
>> Biz koduna bakmak istedim Yani?
Ah, bilmiyorum eğer bu yüzden, Şeyin Tamam görebilirsiniz
üstünde o bütün bir işlevdir İstediğimiz adlı insert
Bağlantılı listeye int n eklemek için.
Biz bu yürüyelim gidiyoruz.
Bu kod bir çok yeni sözdizimi bir çok şey.
Biz Tamam olacak.
>> Üst, ne zaman yukarı Yani biz bir şey yaratmak istiyoruz
biz yapmak için ne gerek, özellikle eğer o yığının üzerinde depolanmamalıdır vermek ister
ancak yığın?
Biz doğru bir malloc gidilir?
Yani biz bir işaretçi oluşturmak için gidiyoruz.
Düğüm, işaretçi, yeni eşittir Bir düğüm boyutunu Malloc
İstediğimiz çünkü düğüm oluşturulacak.
Biz miktarını istiyoruz Bir düğüm alır bellek
için tahsis edilecek yeni bir düğüm oluşturulması.
>> Ve sonra biz kontrol edeceğiz Yeni eşittir sıfır eşittir bakın.
Biz ne dediğini hatırlıyor musun?
Malloc Ne olursa olsun seni, Her zaman ne yapmalıyım?
Her zaman görmek için kontrol etmelisiniz olsun veya olmasın o null.
>> Örneğin, işletim Sistem, tamamen dolu
En fazla bellek olsaydı Tüm ve malloc deneyin,
Sizin için boş dönecekti.
Ve böylece bunu kullanmaya çalıştığınızda o null olarak işaret edildiğinde,
Eğer mümkün gitmiyorsun Bu bilgilere erişmek için.
Ve böylece gibi, biz yapmak istedim ne zaman mallocing yaptığınızdan emin olun,
her zaman görmek için kontrol ediyoruz size verilen bellek null.
O değilse, o zaman biz taşıyabilirsiniz Bizim kod geri kalanı ile.
>> Yani biz gidiyoruz yeni bir düğüm başlatılamıyor.
Yeni n n eşittir yapacağız.
Ve sonra biz yapacağız Yeni yeni işaretçi ayarlamak
null şu anda biz değil, çünkü o işaret etmek için bir şey istiyor.
Biz hiç bir fikrim var nereye bu koymak için gidiyor
ve sonra biz istiyorsanız başında takın,
o zaman biz atayabilirsiniz kafasına işaretçi.
Herkes mantığını takip eder nerede o oluyor?
>> Biz yapıyoruz Bütün yeni yaratıyor düğüm, null işaretçi ayarı
ve daha sonra yeniden atama o kafa biz eğer
Biz başında eklemek istediğini biliyorum.
Ve sonra baş gidiyor yeni düğümün doğru etmektedir.
O OK Herkes?
>> Yani iki aşamalı bir süreçtir.
İlk atamak lazım ne sen yaratıyorsun.
O işaretçi ayarla Sizi referans ve ardından
can dereference tür İlk işaretçi
ve yeni bir düğüm doğru gelin.
Eğer eklemek istediğiniz yerde, Bu mantık doğru tutmak için gidiyor.
>> Bu atama gibi tür Geçici değişkenler.
Unutmayın, var emin olmak için size o
Eğer takas eğer kaybetmeyecek yok.
Sen bir sahip olduğunuzdan emin olmak istiyorum tür tutar geçici değişken
nerede şeyin iz böylece saklanır sen
Elbette herhangi bir değer kaybetmek yok ve onunla düşünsen gibi.
>> Tamam, bu yüzden kod burada olacak.
Siz bölümünden sonra bir göz atın.
Orada olacak.
>> Yani nasıl yaptığını tahmin İstediğimiz bu farklılık
orta veya sonunda eklemek için?
Herkes ne bir fikir var mı Mantıksal referans olarak sözde kod
eğer biz istedi biz alacağını ortada eklemek için?
Yani eğer biz eklemek istedim Baş, yaptığımız tüm yeni bir düğüm oluşturmaktır.
Biz bunun işaretçisi ayarlayın ne olursa olsun kafasına yeni bir düğüm,
ve sonra biz baş ayarlayın Yeni düğüme, değil mi?
Biz ortada eklemek isteseydi Listenin, ne yapmamız gerekir?
>> HEDEF KİTLE: Hala olur Benzer bir süreç
bir işaretçi atama gibi ve Daha sonra, bu işaretçi atama
ama biz orada bulmak zorunda kalacak.
>> ANDI PENG: Kesinlikle, kesinlikle bu yüzden Senin dışında aynı işlem
tam olarak nerede bulmak zorunda sen yeni işaretçi içine gitmek istiyorum,
Ben eklemek istiyorsanız, bu yüzden Tamam list-- bağlantılı orta,
en bizim bağlantılı liste diyelim.
Biz burada eklemek istiyorsanız, Biz yeni bir düğüm oluşturmak için gidiyoruz.
Biz malloc gidiyoruz.
Biz yeni bir düğüm oluşturmak için gidiyoruz.
Biz atamak için gidiyoruz Burada bu düğümün işaretçi.
>> Ama sorun şu farklıdır başıdır yerden
biz biliyordu ki nerede başıdır.
Bu doğru, ilk haklıydı?
Ama burada biz takip etmek lazım nerede biz onu takmadan ediyoruz.
Biz takarken ise bizim Burada düğüm, elimizdeki
emin olmak için Bu düğüme bir önceki
işaretçi atar biridir.
Öyleyse ne tür var İki şeyi takip.
Nereye bu takip ederse Düğüm şu anda takmadan olduğunu.
Ayrıca takip etmek zorunda size aradığınız önceki düğüm
da oradaydı.
Bu iyi Herkes?
TAMAM.
>> Nasıl sonunda takmadan dersiniz?
Ben isteseydim ben burada-- eklemek isteseydi Bir listenin sonuna yeni bir düğüm eklemek için,
Bunu yapmayı nasıl gidebilir?
İZLEYİCİ: Böylece, şu anda Sonuncusu en null işaret etti.
ANDI PENG: Evet.
Kesinlikle, bu yüzden bu bir Şu anda bilmek sivri,
ve bu yüzden bu anlamda, bu, sanırım Bir listenin sonuna eklemek çok kolaydır.
Yapmanız gereken tek şey onu ayarlanır null olarak ve daha sonra patlaması eşit.
İşte orada, çok kolay.
Çok basit.
>> Çok benzer Seni baş, ancak mantıksal
adımlar emin olmak için Eğer bu birini yaparak doğru almak
Eğer birlikte aşağıdaki ediyoruz.
Bu ortada, çok kolay kodunuzu, üzerinde yakalanmak
oh, çok işaretçileri var.
Nerede olduğunu bilmiyorum şey işaret ediyor.
Ben bile olduğumu hangi düğümün bilmiyorum.
Nasıl gidiyor?
>> Derin bir nefes al, sakin ol, rahatla.
Bağlantılı listesini çizin.
Derseniz, ben tam olarak nerede biliyorum Ben içine bu eklemek gerekir
ve ben benim atamak nasıl biliyor işaretçileri, çok, çok daha kolay canlandırmaya
konrtol çok, çok daha kolay değil kodunuzu böcek kaybolmak.
O OK Herkes?
TAMAM.
>> Yani biz değil bir kavram tahmin Gerçekten, şimdi önce konuştuk
ve muhtemelen seni sanırım çok yet-- karşılaşır değil
bir ileri konsept-- tür biz aslında bir veriye sahip olduğunu
yapı iki kat bağlantılı liste çağırdı.
Siz gördüğünüz gibi, biz yapıyoruz bütün yaratır
Bir gerçek değer, extra Bizim düğümlerin her birinde işaretçi
bu da bir önceki birleşme noktasına işaret eder.
Yani sadece biz var düğümler bir sonraki işaret etmektedir.
Onlar da bir önceki etmektedir.
Şu anda bu iki görmezden gidiyorum.
>> Öyleyse bir zincir var Bu her iki yönde hareket edebilir,
ve o zaman biraz daha kolay mantıksal birlikte takip etmek.
Burada olduğu gibi, yerine oh, kayıtlarını tutmak, ben
Bu düğüm olduğunu bilmek zorunda Ben yeniden atamak zorunda kimse,
Ben sadece buraya gitmek ve olabilir Sadece önceki çekin.
Sonra tam olarak nerede biliyorum olduğunu ve o zaman
çapraz zorunda değilsiniz bağlantılı liste tamamı.
Biraz daha kolay.
>> Ama böyle, sen iki misli var işaretçileri miktarı,
bellek miktarı çift var.
Bu takip etmek işaretçiler bir sürü.
Biraz daha karmaşık, ama bu kullanıcı dostu bağlı olarak biraz daha
Eğer başarmak için çalışıyoruz ne.
>> Yani veri bu tür yapı tamamen mevcut
ve için yapı çok olduğunu Eğer yaşıyorsanız hepsi hariç, basit,
Bunun yerine bir sonraki için sadece bir işaretçi, Ayrıca daha önceki bir işaretçi var.
Hepsi fark var.
Bu iyi Herkes?
Güzel.
>> Pekala, şimdi ben Gerçekten muhtemelen harcamak
15 ila 20 dakika veya toplu gibi bölümünde zaman geri kalanı
karma tablo hakkında konuşuyor.
Nasıl çocuklar birçok pset5 spec okudum?
Tamam, iyi.
Normalde% 50 daha yüksek bulunuyor.
Tamam.
>> Siz göreceğiniz gibi Yani, Eğer pset5 içinde meydan konum
bir sözlük uygulamak olacaktır Eğer 140.000 kelime üzerinde yük nerede
biz ve Yazım Denetimi size vermek Metnin tamamı karşı o.
Size rasgele vereceğiz edebiyat parçalar.
Size Odyssey vereceğiz.
Size İlyada vereceğiz.
Size Austin Powers vereceğim.
>> Ve meydan imla denetimi olacak
Bütün her tek sözcük Bu sözlükler
esasen bizim yazım denetleyicisi ile.
Ve bu yüzden birkaç parça var Bu pset oluşturmak yerine,
ilk olmak istiyorum aslında yüklemek mümkün
içine tüm kelimeler senin sözlük, sonra sizi
edebilmek olmak istiyorum hepsi yazım denetimi.
Ve böylece gibi, size gereken gidiyoruz Bu hızlı yapabilirsiniz veri yapısı
ve verimli bir şekilde dinamik olarak.
>> Yani kolay herhalde Bunu yapmanın yolu, sizi
Muhtemelen, bir dizi yaratacak?
Depolama kolay yolu sensin 140.000 kelimelik bir dizi oluşturabilirsiniz
ve sadece orada hepsini koyun ve Daha sonra ikili arama onları çapraz
veya seçimler ya da Ben- üzgünüm sıralama ediyor.
Bunları sıralamak ve sonra onları geçebilir ikili arama ya da sadece doğrusal arama ile
ve sadece son sözleri, ancak bellek büyük miktarda alır
ve çok verimli değil.
>> Ve böylece biz başlatmak için gidiyoruz yapma yolları hakkında konuşurken
Bizim çalışma süresi daha verimli.
Ve hedefimiz almak için zaman sabiti nerede
neredeyse diziler, gibi Eğer anlık erişimi vardır.
Hiçbir şey aramak istedim, Ben sadece edebilmek olmak istiyorum
boom, tam olarak bulmak, ve dışarı çekin.
Ve böylece bir yapı olan biz çok yakın olma olacak
Sürekli erişmek mümkün Zaman, bu Holy Grail
sürekli programlanmasında zaman karma tablo denir.
Ve böylece Davut önce bahsedilen [Duyulamaz] derste biraz,
ama biz gerçekten gidiyoruz Derin bu hafta dalış
ilgili oluyor bir parça nasıl bir karma tablo çalışır.
>> Bu şekilde Böylece bir karma Tablo çalışmaları, örnek olarak,
Ben kelimelerin bir demet saklamak istedim, bir İngilizce sözcüklerin demet,
Ben teorik olarak koyabilirsiniz muz, elma, kivi, mango, çift,
ve hepsi sadece bir dizi üzerinde kavun.
Hepsi uygun olabilir ve bulmak olabilir.
Bu bir ağrı tür olurdu ve erişim yoluyla arama
ancak bunu yapmanın kolay yolu Biz bir yapı aslında yaratabilir
Biz karma karma tablo denir.
Biz aracılığıyla tuşları tüm koşmak bir karma işlevi, bir denklem,
Bu içine hepsini dönüyor Bir değerin çeşit
o zaman üzerine saklayabilir bağlantılı liste aslında bir dizi.
>> Ve işte biz, isteseydi İngilizce kelimeleri saklamak için,
Biz potansiyel sadece could, I do not biliyorum tüm ilk harflerini çevirmek
Bir sayının çeşit içine.
Ve böylece, örneğin, eğer istediğim Bir apple-- ile eşanlamlı olmak
ya da 0 indeksi ile ve B, 1 ile eşanlamlı olmak
Biz 26 girdileri olabilir bu sadece saklayabilirsiniz
harflerinin bütün biz başlayacağız alfabe.
Ve sonra biz olabilir 0 dizinindeki elma.
Biz dizinindeki muz olabilir 1, 2 endeksinde kavun,
ve benzerleri ve benzeri.
Ve böylece ben aramak istedim Benim karma tablo ve erişim elma,
Ben elma ile başlar biliyorum A, ve ben iyi biliyorum
olması ve karma gerektiğini endeksi 0 dolayı masa
fonksiyonun önceden atanmış.
>> Bilmiyorum Yani, biz Bir kullanıcı programı nerede
Eğer suçlanıyor olacak keyfi değil arbitrarily--,
düşünceli çalışan ile İyi denklemlerin düşünüyorum
yaymak mümkün senin tüm değerleri üzerinden
Bir şekilde kolayca erişebilirsiniz sonradan bir denklem gibi
Sen misin, kendiniz biliyorsunuz.
Ben gitmek istedim anlamda yüzden mango, oh, bu m ile başlar, biliyorum.
Bu 12 endeksi olmalıdır.
Ben herhangi bir şey ile aramak zorunda değilsiniz.
Ben sadece gidebiliriz tam olarak-- biliyorum ve 12 endeksi dışarı çekin.
>> Nasıl Herkes net hash tablo işlevi çalışır?
Bu sadece daha karmaşık bir dizi türüdür.
Yani hepsi bu.
TAMAM.
>> Yani biz koşmak tahmin Bu sorunu nasıl
Birden şeyler varsa olur bu sana aynı dizin verir?
Yani tüm o bizim işlevi söylemek yaptım ilk harfini almak oldu
ve bir o çevirmek içine 0 endeksi 25 ile ilgili.
Yani eğer tamamen iyi olduğunu sadece her birine sahip.
Fakat ikinci Başlamadan fazlasına sahip, sen
Bir çarpışma denen zorunda olacak.
>> Ben eklemeye çalışırsanız bir karma içine gömmek Yani zaten üzerinde muz vardır masa,
Ne zaman ne olacak Bunu eklemek deneyin?
Kötü şeyler nedeniyle muz zaten endeks içinde var
Eğer saklamak istediğiniz.
Berry tür ne yapmalıyım, ah, gibi?
Ben nereye gideceğimi bilmiyorum.
Bunu nasıl çözerim?
>> Ve böylece siz olacak tür Bu zor bir şey yaptığını görmek
nerede tür aslında can Bizim diziler bağlantılı liste oluşturmak.
Ve böylece en kolay yolu Bu düşünmek,
Tüm karma tablo bir bağlantılı listeler dizisi.
Ve böylece, bu anlamda, sahip işaretçiler bu güzel dizi
ve sonra her işaretçi olarak Bu değer, o endekste,
aslında başka şeyler işaret edebilir.
Ve böylece tüm bu ayrı olması büyük bir dizinin kapalı geliyor zincirleri.
>> Ve işte, ben eğer berry eklemek istedim
Tamam, ben giriş gidiyorum, biliyorum Benim karma fonksiyonu sayesinde.
Ben indeksi ile sonuna kadar gidiyorum 1, ve sonra var edebilmek için gidiyorum
Bu sadece küçük bir alt kümesi Dev 140.000 kelimelik sözlük.
Ve sonra ben sadece bakabilirsiniz Bunun 1/26 yoluyla.
>> Ve böylece o zaman sadece ekleyebilirsiniz önce veya sonra muz ya berry
bu durumda?
Sonra, değil mi?
Ve böylece istediğiniz gidiyoruz muz sonra bu düğüm eklemek,
ve böylece eklemek için gidiyoruz Bu bağlantılı listenin kuyruk.
Geri dönmek için gidiyorum Bu önceki slayda,
böylece siz nasıl görebilirsiniz hash fonksiyonu çalışır.
>> Yani hash fonksiyonu bu denklemi olduğu Eğer giriş tür çalışan olduğunuzu
almak için her türlü endeksi ile Eğer doğru atamak istediğiniz.
Ve böylece, bu örnekte, tüm istediğimiz yapmak, ilk harfini almak oldu
biz o zaman, bir dizin içine çevirmek Bizim hash fonksiyonu bu saklayabilirsiniz.
Burada yapıyoruz hepimiz olman ilk harfini dönüştürülüyor.
Yani keykey [0] sadece ilk harf ne olursa olsun dize biz yaşıyoruz,
Biz geçiyoruz.
Üst o dönüştürme ve konum Biz büyük A çıkarılarak ediyoruz
Bunu yaparken ki tüm bize bir numara veriyor
hangi biz değerlerimizi üzerine karma olabilir.
>> Ve sonra biz gidiyoruz karma modülü SIZE dönün.
Çok, çok dikkatli olun Teorik olarak, burada, çünkü
senin müzakere değeri sonsuz olabilir.
Bu sadece ve üzerinde ve gidebiliriz.
O, gerçekten bazı olabilir Gerçekten büyük bir değer,
ama hash tablosunda çünkü Oluşturduğunuz sadece 26 dizinleri vardır,
Eğer emin olmak sizin modulusing böylece
aynı şey run-- yok senin queue-- olarak bir şey
böylece kaçıp olmadığını senin hash fonksiyonu alt.
>> Etrafta geri sarmak istiyor [duyulamaz] ne zaman aynı şekilde
Eğer, bir çok gibi oldu Çok büyük harf, sen
o istemedi Sadece ucunu çalıştırın.
Burada Aynı şey, emin olmak istiyorum o sararak ucunu çalışmaz
etrafında tablonun üstüne.
Yani bu sadece bir çok Basit hash fonksiyonu.
Yaptığını Tüm çekmek ilk ne olursa olsun, bizim girdi mektup oldu
ve bir dizin içine edecek Biz bizim karma tabloya koymak olabilir.
>> Evet, ve bu yüzden, daha önce de söylediğim gibi Biz çarpışmalar çözmek yolu
Bizim karma tablo yaşıyorsanız, Biz zincirleme, ne diyoruz.
Birden eklemeye çalıştığınızda Yani eğer aynı şey ile başlayan kelimeler,
Bir karma değerini zorunda gidiyoruz.
Avokado ve elma, sen yasiyorsaniz Bizim hash fonksiyonu sayesinde çalıştırmak,
Size vermek için gidiyoruz aynı sayıda, 0 sayısıdır.
Ve böylece şekilde biz olduğunu çözmek biz aslında bir tür bunları bağlamak olabilir
birbirine bağlı listeleri üzerinden.
>> Ve böylece bu anlamda, Siz tür görebilirsiniz
arasında nasıl veri yapıları o Daha önce ayar oldum
Bir kuru üzüm bağlantılı liste tür gibi birine bir araya gelebilir.
Ve sonra çok oluşturabilirsiniz daha verimli veri yapıları
Bu büyük miktarlarda işleyebilir Veri, yani dinamik olarak yeniden boyutlandırma
sizin ihtiyaçlarınıza.
Herkes açık?
Net Herkes tür Burada ne üzerine?
>> Ben insert-- istiyorsa bir ne Bilmiyorum, ile başlar meyve,
Berry dışındaki B, muz.
>> HEDEF KİTLE: Böğürtlen.
>> ANDI PENG: Böğürtlen, böğürtlen.
Nereye böğürtlen burada gidiyor?
Peki, biz aslında sıralanmış değil Bu henüz, ama teorik olarak
Biz bu istedim eğer alfabetik sırayla,
nereye böğürtlen gerekir?
>> HEDEF KİTLE: [duyulamaz]
>> ANDI PENG: Kesinlikle, burada daha sonra, değil mi?
Ama çok zor çünkü reorder-- Ben size çocuklar kadar sanırım.
Siz tamamen can İstediğini uygulamak.
Daha verimli bir şekilde belki bunu
Bağlantılı sıralamak olacaktır alfabetik içine listesi,
ve böylece olduğunuzda şeyleri ekleyerek, istediğiniz
Onları eklemek emin olmak için alfabetik içine
böylece daha sonra olduğunuzda Onları aramak için çalışıyor,
Her şeyi hareket ettirmek zorunda değilsiniz.
Tam olarak nerede olduğunu bilmek o, ve daha kolay.
>> Ama ne tür varsa şeyler, rastgele serpiştirilmiş
Hala zorunda gidiyoruz Nasılsa geçiş için.
Ve bu yüzden istedim sadece böğürtlen burada eklemek
ve ben aramak istedim o, ben, oh biliyorum, böğürtlen
1 indeksi ile başlar, bu yüzden olmalı anında sadece 1 ile arama biliyorum.
Ve sonra ben tür can bağlantılı liste geçiş
Ben böğürtlen elde edene kadar, ve evet o zaman--?
>> HEDEF KİTLE: Eğer create-- çalışıyorsanız Bu çok basit bir karma gibi sanırım
işlevi.
Ve biz yapmak istedim Böyle bir çok katmanlı,
Tamam, biz ayırmak istiyoruz tüm alfabetik harflerle gibi
ve sonra tekrar başka bir set sevmeye Bu içinde alfabetik harflerin,
Biz bir karma gibi koyarak karma tablo içinde tablo,
veya bir işlev içinde bir işlev gibi?
Ya da ki- olduğunu
>> ANDI PENG: senin karma So senin karma tablo function--
siz istediğiniz kadar büyük olabilir.
Yani bu anlamda, diye düşündüm çok, çok kolay oldu
Benim için basit, sadece sıralama tabanlı etmek İlk kelimenin harfleri üzerinde.
Ve böylece sadece 26 seçenek var.
Ben sadece 26 seçenek alabilirsiniz 25 0 çünkü onlar sadece can
A Z'ye başlamak Ama sen isteseydin belki daha fazla karmaşıklık eklemek için
ya da daha hızlı çalışma süresi sizin hash tablosu, kesinlikle
her türlü şeyi yapabilirsiniz.
Kendi yapabilirsiniz size verir denklem
daha fazla dağıtım senin sözler, o zaman, arama yaparken
Daha hızlı olacak.
>> Tamamen size çocuklar kadar var bunu nasıl uygulamak istiyorum.
Sadece kovalar gibi düşün.
Ben isteseydim 26 kovalar, ben gidiyorum
Bu kova içine şeyleri sıralamak için.
Ama bir grup var gidiyorum Her kovada şeyler,
Bunu yapmak istiyorsanız bu yüzden daha hızlı ve daha verimli,
Bana yüz kova atalım.
>> Ama sonra bir bulmalıyız Onlar böylece yol şeyleri sıralamak için
Uygun kova da olmalıdır.
Ama sonra ne zaman aslında O kova bakmak istiyorum,
var çünkü çok hızlıdır Her kovada daha az şeyler.
Ve böylece, evet, bu aslında pset5 size çocuklar için hile
Eğer olacağım olduğunu Sadece oluşturmak için meydan
En verimli ne olursa olsun aklınıza gelebilecek işlevi olması
depolamak ve bu değerleri kontrol etmek mümkün.
>> Tamamen size çocuklar kadar Ancak bunu yapmak istiyorum,
ama bu gerçekten iyi bir nokta.
Bu mantık tür düşünmeye başlamak istiyorum
iyi, neden daha fazla kova yapmazlar vardır.
Ve sonra ben aramak zorunda daha az şeyler, sonra belki
farklı bir karma işlevi vardır.
>> Evet, bunu yapmak için pek çok yolu var pset, bazıları diğerlerinden daha hızlıdır.
Ben tamamen ne kadar görmek için gidiyorum Hızlı hızlı siz olacak oldu
senin işlevleri işe almak mümkün.
Tamam, herkes iyi on zincirleme ve hash tabloları?
Bu çok basit gibi aslında Bu konuda kavram düşünüyorsanız.
O Tüm ayıran ne olursa olsun senin girişleri kova içine,
Onları sıralama ve sonra arama Orada ilişkilendirilmiş olduğunu listeler.
>> Güzel.
Pekala, şimdi biz farklı bir sıralama var veri yapısının bir ağaç deniyor söyledi.
Devam edelim ve denemeden hakkında konuşmak bu, açık bir şekilde farklıdır
ama aynı kategorideki.
Esasen, bütün bir ağaç yerine ise lineer şekilde veri organize
Bir karma tablo size does-- olduğunu bu, bir üst ve bir alt var biliyorum
ve sonra ne tür dökersin-- bir kapalı bağlantı ağaç, sen kök diyoruz bir üst vardır
ve daha sonra tüm çevresinde yaprakları vardır.
>> Ve böylece tüm burada var sadece üst düğüm
diğer düğümlere, puan olduğunu işaret daha fazla düğümle ve benzeri ve benzeri.
Ve böylece sadece bölme şubeleri var.
Bu örgütlenme, sadece farklı bir yolu Veri ve biz bir ağaç diyoruz çünkü,
Siz bu sadece sadece- Bir ağaç gibi bakmak için dışarı modellenmiştir.
Biz ağaçların dememin sebebi bu.
>> Hash tablo, bir tablo gibi görünüyor.
Bir ağaç bir ağaç gibi görünüyor.
O Tüm ayrı düğümler organize yolu
İhtiyaçlarınız ne bağlı.
>> Yani bir kök var ve sonra yaprakları vardır.
Yol biz özellikle can Bir ikili ağaç düşünmek,
Bir ikili ağaç sadece bir Bir ağacın belirli bir tip
Nerede her düğüm sadece puan için, max, diğer iki düğüm.
Ve böylece burada farklı olması senin ağacında simetri
o kolay tür bakmak için yapar değerleri ne sonra size çünkü vardır
Her zaman sol ya da sağ var.
Bir sol üçte gibi Orada asla Sol veya soldan gelen dördüncü.
Size bir sol ve hakkına sahip sadece var ve o iki ya da arama yapabilirsiniz.
Ve böylece bu neden yararlıdır?
Bu olduğu yolu Eğer arıyorsanız yararlıdır
Doğru, değerler üzerinden aramak için?
Aksine ikili uygulanması daha Bir hata dizideki arama
Eğer düğümlerin eklemek mümkün olmak istedim ve at will ve ayrıca düğümleri götürmek
Aramayı korumak İkili arama kapasiteleri.
Yani bu şekilde, biz tür konum ne zaman hatırlamak tricking--
bağlı listeler ikili arama yapamaz dedi?
Biz tür bir veri yapısını oluştururken hileler çalışma içine o.
>> Ve böylece çünkü bağlı listeler, doğrusal onlar sadece birbiri ardına bağlantı.
Biz tür olabilir işaretçileri farklı sıralama
Farklı düğümlere o nokta Bu arama ile bize yardımcı olabilir.
Ve işte, eğer ben istedim İkili arama ağacı var,
Biliyorum benim orta olduğunu 55 ise.
Ben sadece oluşturmak için gidiyorum Benim orta olarak, benim root olarak,
ve sonra ben gidiyorum değerler bunun spin off.
>> Yani burada, ben aramak için gidiyorum 66 değeri, ben 55 başlayabilirsiniz.
Bu 55 den 66 büyük değil mi?
Evet öyle, bu yüzden ben arama mus biliyorum i n bu ağacın sağ işaretçi.
Ben 77 gidin.
Tamam daha az ya da 77 daha büyük 66 mi?
Ah, o daha az, bu yüzden bilirsin, Geriye kalan düğümü olmalıdır.
>> Ve işte biz tür koruyarak ediyoruz diziler hakkında harika şeyler tüm
böylece dinamik boyutlandırma gibi Nesnelerin, olduğu
takın ve irade silmek mümkün, Sabit konusunda endişelenmenize gerek kalmadan
alan miktarı.
Biz hala tüm korumak Bu harika şeyler
Ayrıca korumak mümkün olurken log ve ikili arama zamanını arama
Daha önce sadece edildi bir ifade almak mümkün.
>> Serin veri yapısı, tür Karmaşık, düğüm uygulamak.
Eğer tüm görebileceğiniz gibi düğümün yapıdır
Eğer bir sol olması ve doğru gösterici.
Yani hepsi bu.
Yani yerine sadece daha Bir x veya bir önceki sahip.
Daha sonra sola veya sağa ve var ne tür onları birbirine bağlayabilirsiniz
Ancak bunu seçin.
>> Tamam, biz aslında gidiyoruz Sadece birkaç dakika sürebilir.
Yani biz buraya gitmek için gidiyoruz.
Daha önce de söylediğim gibi, Tür açıkladı
biz nasıl arkasındaki mantık Bu arama olacaktır.
Biz denemek için gidiyoruz Bu out pseudocoding görmek için
biz tür uygulayabilirsiniz eğer İkili arama Aynı mantık
veri yapısının farklı bir tür.
Siz bir çift gibi almak istiyorsanız dakika sadece bu düşünmek.
TAMAM.
Pekala, ben gidiyorum Aslında sadece hayır Şeyin vermek,
Biz ilk pseudocode hakkında konuşacağız.
Yani herkes istiyor bir bıçak vermek ne
Ne zaman yapmak istediğim ilk şey Eğer arama dışarı başlıyoruz?
Biz arıyorsanız 66 değeri, ne
Biz eğer yapmak istediğim ilk şey Bu ağaç Arama ikili istiyor?
>> HEDEF KİTLE: Haklısınız bakmak istiyorum ve [duyulamaz] sol bakmak ve görmek
daha çok sayıda.
>> ANDI PENG: Evet, kesinlikle.
Yani kök bakmak için gidiyoruz.
Arayabileceğiniz birçok yolu var o, senin üst düğüm insanlar söylüyorlar.
Çünkü kök demek istiyorum o ağacın köküne benziyor.
Sen bakmak için gidiyoruz Kök düğüm, ve sen
göreceğiz 66 daha fazladır veya daha az 55.
Ve iyi, öyle, daha büyük olursa daha fazla, nereye bakmak istiyorsun?
Nereye doğru, şimdi aramak istiyorsunuz?
Biz aramak istediğiniz Bu ağacın sağ yarısı.
>> Yani biz var, uygun bir sağa işaret işaretçi.
Ve böylece o zaman ayarlayabilirsiniz Yeni kök 77 olmak.
Biz sadece yere gidebilirsiniz işaretçi işaret ediyor.
Peki, ah, işte başlıyoruz 77 at ve biz sadece can
ardışık tekrar tekrar bunu.
Bu şekilde, ne tür Bir işlevi var.
Sen bu arama bir yolu var Sadece ve tekrar üzerinde tekrarlayabilirsiniz,
Bakmak istediğiniz yere bağlı olarak sonunda değeri elde edene kadar
Aradığınız söyledi.
Mantıklı?
>> Sana gerçek göstermek üzere olduğum kod ve kod bir çok şey.
Gerek yok korkutmaya.
Biz bu kadar konuşacağız.
>> Aslında hayır.
Bu sadece pseudocode oldu.
Tamam, bu sadece pseudocode oldu hangi biraz karmaşık,
ama tamamen iyi.
Burada herkesi birlikte aşağıdaki?
Kök null ise, dönüş yanlış o yollarla çünkü
Hatta orada bir şey yok.
>> Kök n eğer öyleyse değeri ise o Eğer bakıyoruz biri olur,
o zaman gerçek dönmek için gidiyoruz Bildiğiniz çünkü bunu buldum.
Ama değer az ise n kök yerine, sen
sol arama gidiş çocuk veya sol yaprak,
onu aramak istediğiniz ne olursa olsun.
Ve değer kök büyükse, Doğru ağaç aramak için gidiyoruz,
sonra sadece işlevi çalıştırmak arama yoluyla tekrar.
>> Ve kök, null o ise Size sonuna ulaştınız demektir?
Yani hayır var demektir daha fazla yaprakları aramak için,
o zaman ben, oh, biliyorum Burası değil sanırım
Ben inceledim çünkü sonra ve burada değil her şey,
Sadece burada olmayabilir.
>> Bu herkese mantıklı mı?
Yani koruyarak ikili arama gibi bağlantılı listeler yetenekleri.
Serin ve böylece ikinci tip veri yapısı adamlar
senin pset üzerinde uygulama deneyebilirsiniz, Eğer sadece tek bir yöntemi seçmek zorundasınız.
Ama belki de alternatif bir yöntem için karma tablo bir trie diyoruz.
>> Tüm bir tray olan ağaç belirli bir tür olduğunu
diğer değerlere gitmek değerleri vardır.
Bunun yerine bir ikili olan anlamda ağaç tek olduğunu
şey iki işaret, sen olabilir pek çok şey için bir şey gelin.
Siz aslında diziler var hangi saklamak içinde
Diğer diziler işaret işaretçileri.
>> Peki biz nasıl düğüm Bir trie tanımlarsınız
Biz istiyorum olduğunu Boole, c kelime değil mi?
Yani düğüm Boolean olduğunu , doğru veya yanlış gibi
başında öncelikle Bu dizi, bu bir kelime?
İkincisi, işaretçiler sahip olmak istiyorum ne olursa olsun onları geri kalanı.
Biraz karmaşık, biraz soyut, ama Ne o bütün araçları açıklayacağız.
>> Yani burada, üstünde, eğer Bir dizi zaten ilan var,
Eğer bir Boole var bir düğüm ön depolanmış değeri
Bu, bu bir kelime söyler?
Bu bir kelime mi?
Ve sonra var senin dizinin geri kalanı o
aslında saklar tüm ne olabilir olanakları.
Bu nedenle, örneğin, gibi üstünde var
doğru ya da diyor ilk şey Yanlış, evet ya da hayır, bu bir kelimedir.
>> Ve sonra 26. boyunca 0 var saklayabilirsiniz harfler.
Burada arama isteseydim Yarasa, ben üstüne gitmek
ve ben de B buluyorum B. bakmak benim dizi ve böylece biliyorum, tamam, B bir kelimedir?
B yani böylece, bir kelime değil Ben araştırıcı tutmalısınız.
Ben B gidin ve ben bakmak B doğru işaret işaretçi
ve ben, bilgi başka bir dizi görmek Daha önce vardı aynı yapı.
>> Ve, oh sonraki var-- [duyulamaz] harfi A.
Yani biz bu dizide bak.
Biz sekizinci değeri bulmak, ve sonra, oh, görmek için bakmak
hey, bir kelime olduğunu, B-A bir kelimedir?
Bu bir kelime değildir.
Biz aramaya devam etmelisin.
>> Ve böylece o zaman nereye bakmak A puanlık işaretçi,
ve başka bir şekilde işaret hangi daha fazla değer saklanır var.
Ve sonunda, biz olsun Bir kelime B-A-T,.
Ve böylece bir dahaki sefere bak, sen gidiyorsun
evet, o çeki var, Bu Boole fonksiyonu doğrudur.
Ve böylece anlamda biz naziksiniz dizileri ile bir ağaç olan.
>> Öyleyse ne tür aşağı arama yapabilirsiniz.
Aksine bir işlev karma daha ve Bağlantılı liste değerleri atayarak,
Sadece bir uygulayabilirsiniz downwords arama tray.
Gerçekten, gerçekten bir şeyler karmaşık.
Ben gibiyim çünkü düşünmek kolay değil Pek çok veri yapılarını tükürme
Sana, ancak tür herkes yapar Bu mantığı nasıl çalıştığını anlamak?
>> Tamam iyi.
Bu nedenle B-A-T, ve sonra Aramak gidiyoruz.
Gittiğin dahaki sefere oh, hey, bu doğrudur, görmek,
Böylece bu bir kelime olmalı biliyorum.
>> Hayvanat bahçesi için aynı şey.
Yani burada bir şey varsa, şu an var biz Şu anda, hayvanat bahçesi aramak istedim,
Şu anda hayvanat bahçesi değil, bir Bizim kelimesinin sözlük
Çünkü siz, gördüğünüz gibi Biz bir Boole gereken ilk yer
dönmek gerçek zoom sonundadır.
Biz Z-O-O-M var.
>> Ve işte, biz aslında yok Bizim kelimesinin sözlük, hayvanat bahçesi,
Bu onay kutusu işaretli olmadığından.
Yani bilgisayar değil Hayvanat Bahçesi bir kelime olduğunu biliyorum
Çünkü biz ettik yolu Sadece yakınlaştırma burada, o saklanır
aslında bir Boolean değeri vardır Bu doğru döndü oldu.
Biz eklemek istiyorsanız Yani kelime, hayvanat bahçesi, bizim sözlüğümüze,
Biz bunu yaparken nasıl hakkında gitmek istiyorsunuz?
Emin olmak için yapmak zorunda ne bizim Bilgisayar Z-O-O bir kelime olduğunu biliyor
ve ilk kelime Z-O-O-M?
>> HEDEF KİTLE: [duyulamaz]
>> ANDI PENG: Kesinlikle, biz Bu emin olmak için
Burada, o Boolean değeri bu doğru bu kapalı kontrol etti.
Z-O-O, o zaman kontrol etmek gidiyoruz, bu yüzden tam olarak, hey, hayvanat bahçesi, bir kelime olduğunu biliyorum.
Ben söyleyeceğim o bir kelime öylesine var bilgisayar
, bilgisayar denetler olduğunu bu hayvanat bahçesi bir kelime olduğunu biliyor.
>> Tüm bu verileri hatırlayacak Çünkü yapılar, bizim için çok kolay
oh, yarasa bir kelime söylemek için.
Zoo kelime.
Yakınlaştırma bir kelime.
Ama bunu inşa ederken, Bilgisayar hiçbir fikri yok.
>> Yani tam olarak söylemek zorundayım hangi noktada bu kelime?
Hangi noktada bir kelime değil mi?
Ve hangi noktada ben yapmak şeyleri aramanıza gerek,
ve hangi noktada ben bir sonraki gitmek gerekir?
Bu açık Herkes?
Güzel.
>> Ve böylece o geliyor sorunu nasıl olur
bir şey ekleme hakkında gitmek orada aslında değil mi?
Yani sadece biz eklemek istediğiniz diyelim Bizim tray içine kelime, banyo,.
Size çocuklar şu anda gibi görebileceğiniz gibi Şu anda sahip olduğumuz tüm B-A-T
ve bu yeni veri yapısı bir bira bardağı var olduğunu
biz varsayalım, çünkü null işaret oh, B-A-T sonra hiçbir kelime yoktur ki,
Neden biz tutmak gerekiyor O T. sonra şeylere sahip
>> Size bunu Ama eğer sorun ortaya çıkar sonra gelen bir kelime istiyorum
T.
Eğer banyo varsa, sen H hakkı istemek için gidiyor.
Ve böylece biz bunu gidiyoruz yoludur biz ayrı bir düğüm oluşturmak için gidiyoruz.
Biz ne olursa olsun tutarı tahsis değiliz Bu yeni dizinin hafıza,
ve biz işaretçileri yeniden atamak için gidiyoruz.
>> Biz atamak için gidiyoruz H Her şeyden önce, bu null,
Biz kurtulmak için gidiyoruz.
Biz gidiyoruz H noktası aşağıya.
Biz H görürseniz, bunu istiyoruz Başka bir yere gitmek için.
>> Burada, biz o zaman evet kontrol edebilirsiniz.
Biz T sonra H vurursanız, oh, o zaman bu bir kelime olduğunu biliyoruz.
Boolean true dönmek için gidiyor.
Herkes bu oldu nasıl anlaşılır?
TAMAM.
>> Yani aslında, tüm Bu veri yapıları
bugün üzerinde gittin, ben ettik Gerçekten, gerçekten hızlı bir şekilde üzerlerine gitti
ve pek için detay ve Tamam.
Eğer karışıklık başladıktan sonra onunla, size olacak
nerede izleyebilmek tüm işaretçiler vardır
ne oluyor senin veri yapıları, vesaire.
Onlar, çok yararlı olacak ve size kalmış
adamlar tamamen anlamaya Bir şeyleri uygulamak istiyorum.
>> Ve böylece pset4, bir 5-- ah, o yanlış.
Pset5 imla hataları olduğunu.
Daha önce de söylediğim gibi, bir kez gidiyoruz Yine bizden kaynak kodunu indirin.
Üç ana Orada gidiyor şeyler indirirken olacak.
Sen, sözlükler indirebilirsiniz edeceğiz kers ve metinler.
>> Tüm bu şeyler vardır ya da kelime sözlükleri
biz kontrol etmek istediğiniz veya bilgi testi
biz imla denetimi istediğiniz.
Ve böylece sözlükler biz gidiyoruz vermek
Size istediğimiz gerçek kelimeleri vermek Eğer bu şekilde bir şekilde saklamak için
bir dizi daha etkilidir.
Ve sonra metinleri Biz ne konum olacak
soran emin olmak için kontrol büyü kelimelerin hepsi gerçek kelime vardır.
>> Ve bu nedenle üç blok size vereceğim programları
dictionary.c denir dictionary.h ve speller.c.
Ve böylece tüm dictionary.c olduğunu yapar Ne uygulamak için istenir.
Bu kelimeleri yükler.
Bu denetler onları büyü ve emin olur O her şeyin düzgün eklenir.
>> diction.h sadece bir kitaplık dosyası tüm bu fonksiyonları bildirir.
Ve speller.c, biz sana vereceğiz.
Bunu herhangi değiştirmeniz gerekmez.
Tüm speller.c olduğunu sürer, yüklerin, bunun hızını kontrol eder,
nasıl bir kriter testleri gibi hızlı bir şekilde şeyler yapmak mümkün olacaktır.
>> Bu bir yazım var.
Sadece onunla karışıklık yok, ama yapmak emin ne yaptığını anlıyorum.
Biz bir işlev olarak adlandırılan getrusage kullanan senin büyünün performansını test
denetleyicisi.
Tüm bu temelde test etmek olduğunu yapar Sözlüğünüzdeki her şeyin zamanı,
bu yüzden onu anlamak emin olun.
Onunla karışıklık için dikkatli olun ya da Başka şeyler düzgün çalışmaz.
>> Ve bu meydan toplu içindir Siz gerçekten dictionary.c değiştirmek için.
Size vermek için gidiyoruz Bir sözlükte 140,000 kelime.
Size bir metin vereceğiz bu kelimeleri içeren dosyadır,
ve biz organize edebilmek olmak istiyorum karma tablo veya bir tray içine onları
Biz büyü istiyoruz çünkü ne zaman Eğer büyü iseniz hayal check--
Homeros'un Odyssey gibi kontrol.
Bu çok büyük bir testi gibi.
>> Her düşünün sözcük bakmak zorunda kaldı
140.000 değerler dizisi aracılığıyla.
Bu sonsuza kadar sürer makineniz çalıştırmak için.
Nerede biz organize etmek istiyoruz yüzden daha verimli veri yapılarına veri
Böyle bir karma tablo veya bir tray olarak.
Ve sonra siz tür yapabilirsiniz Erişim arama ne zaman
işler daha kolay ve daha hızlı.
>> Ve böylece çarpışmalar çözmek için dikkatli olun.
Bir demet almak için gidiyoruz A ile bu başlangıç ​​kelimelerin
Bir demet kelime almak için gidiyoruz Bu sizin kadar B. ile başlar
İstediğiniz kadar adamlar bunu çözmek için.
Belki daha var verimli hash fonksiyonu
sadece ilk harfi daha bir şey, ve böylece size kalmış
adamlar tür istersen yapmak.
>> Belki Eklemek istediğiniz birlikte tüm harfler.
Belki tuhaf şeyler yapmak istiyorum istiyorum harflerin sayısını hesap,
Herneyse.
Yapmak istediğiniz nasıl çocuklar kadar.
Eğer eğer, bir karma tablo yapmak istiyorsanız Tamamen size kalmış, bir trie denemek istiyorum.
Ben vaktinden sizi uyaracaktır tray genellikle biraz daha zor
Bir çok şey var sırf Daha fazla işaretçileri takip etmek.
Ama tamamen Sizinle kadar.
Bu çok daha verimli olduğunu çoğu durumda.
Gerçekten devam edebilmek istiyorum senin işaretçileri tüm iz.
Gibi aynı şeyi yapmak Ben burada ne işi olduğunu.
Ne zaman eklemek için çalışıyoruz karma tabloya değerleri veya silmek,
sen emin olun Gerçekten takip
Her şey çünkü nerede o ben eğer gerçekten kolay
kelime, Andy gibi eklemeye çalışıyor.
Sadece bu diyelim Gerçek kelime, kelime, andy,
Bir kelime dev listesine.
>> Ben sadece yeniden atamak için ne bir işaretçi yanlış ayy,
bütününü gidiyor Benim bağlantılı liste geri kalanı.
Şimdi tek kelime ben var andy ve şimdi
başka bir deyişle tüm Sözlük kayboldu.
Ve bu yüzden size emin olmak senin işaretçileri tüm takip
ya da başka almak için gidiyoruz kodunuzu büyük sorunlar.
Adım adım dikkatlice şeyler çizin.
Bu düşünmek çok daha kolay hale getirir.
>> Ve son olarak, mümkün olmak istiyorum Programınızın sizin performansını test
Büyük gemide.
Siz alırsan bir Şu anda CS50 bakmak,
Biz büyük tahta ne denir var.
Bu hızlı puan levhasıdır CS50 tamamında denetimi kez yazım
Şu anda, ben 10 gibi üst düşünüyorum Zaman ben onlardan sekiz personel olduğunu düşünüyorum.
Biz gerçekten siz bizi yenmek istiyorlar.
>> Hepimiz uygulamaya çalışıyorlardı mümkün olduğunca hızlı kodu.
Biz sizler meydan denemek istiyorum Bize ve hepimiz daha hızlı uygulanması
can.
Ve böylece bu gerçekten Biz konum ilk kez
Sizi soran bir pset yapmak için bu Eğer gerçekten ne olursa olsun yönteminde yapabilirsiniz
İstediğiniz.
>> Ben her zaman bu daha yakındır demek gerçek hayatta çözüm, değil mi?
Hey, bunu yapmak gerekir, diyorum.
Benim için bunu yapar bir program oluşturun.
İstediğiniz ancak bunu.
Ben sadece oruç tutmak istediğini biliyorum.
İşte bu hafta için mücadeledir.
Siz, biz gidiyoruz Sana bir görev verecek.
Size bir meydan okuma vermek için gidiyoruz.
Ve o zaman çocuklar kadar var tamamen sadece anlamaya
en hızlı ve en ne verimli bir şekilde uygulamak için.
Evet?
>> HEDEF KİTLE: Biz eğer izin var Daha hızlı yollarını araştırma istedi
Yapabileceğimiz, çevrimiçi hash tabloları yapmak Bu ve başkasının kodunu alıntı?
ANDI PENG: Evet, tamamen iyi.
Yani siz okursanız spec, bir çizgi var
Eğer çocuklar diyor spec karma araştırma tamamen ücretsiz
ne bazı fonksiyonlar hızlı hash fonksiyonları
olarak aracılığıyla şeyler çalıştırmak için Eğer bu kodu alıntı sürece.
Yani bazı insanlar zaten Hızlı yolları anladım
hızlı bir büyü dama yapıyor bilgi depolama yolları.
Tamamen size çocuklar kadar eğer Doğru, sadece almak istiyorum?
Eğer gerekçe emin olun.
Meydan burada gerçekten Biz sınamak için çalışıyoruz olduğunu
Bildiğiniz emin olduğunu yolunuzu etrafında değineği.
Bildiğim kadarıyla sen uygulama olarak Gerçek hash fonksiyonu
ve benzeri ile geliyor Matematik yapmak,
Siz araştırma ne olursa olsun yöntemler çevrimiçi siz istiyoruz.
Evet?
>> HEDEF KİTLE: biz sadece alıntı miyiz [duyulamaz] kullanarak?
>> ANDI PENG: Evet.
You can sadece senin açıklamada, Eğer, oh gibi verebiliriz
YADA alınan, yada, yada, karma işlevi.
Herkes herhangi bir sorunuz var mı?
Biz aslında breezed Bugün bölümünden.
Ben burada olacak hem de sorulara cevap.
>> Ayrıca, dediğim gibi, ofis Saat gece ve yarın.
Bu hafta aslında spec Süper kolay ve okumak için süper kısa.
Ben sadece, bir göz alarak öneririm Bunun tamamı baştan sona okuyun.
>> Ve Zamyla aslında size yürür fonksiyonların her birinden
Eğer uygulamanız gerekir ve bu yüzden var Her şeyi nasıl çok net.
Sadece emin sen olmak için işaretçileri takip.
Bu çok zorlu bir pset olduğunu.
>> Bu gibi çünkü zorlu değil oh, kavramlar çok daha fazla olduğu
Zor ya da öğrenmek zorunda yol çok yeni sözdizimi
Geçen pset için yaptım.
Bu pset zordur, çünkü çok işaretçiler vardır,
ve o zamanlar çok, çok kolay değil muktedir kodunuzda bir hata var
Bu hata nerede olduğunu bulmak için.
>> Ve böylece tam ve sana mutlak inanç adamlar bizim [duyulamaz] yenmek mümkün
yazımlar.
Ben aslında herhangi bir yazılı mayın var Henüz değil, ama benim yazmak üzereyim.
Eğer yazıyoruz süre Yani senin, benim yazılı olacak.
Ben yapmak denemek için gidiyorum benimki seninkinden daha hızlı.
Biz hızlı bir kimin görürsünüz.
>> Ve evet, ben tüm göreceksiniz Burada Salı günü çocuklar.
Ben bir pset atölyesi gibi bir tür çalışacaktır.
Bölümlerin hepsi hafta, pset atölyeleri vardır
böylece siz fırsatlar çok var Yardım için, mesai saatleri her zaman olduğu gibi,
ve ben gerçekten bekliyoruz senin adamların 'tüm kod okuma.
Burada eğer sınavlar kadar var adamlar o olsun gelmek istiyorum.
Bu kadar.