1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [MÜZİK OYUN] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> David MALAN Bu CS50 olup. 5 00:00:14,010 --> 00:00:18,090 Ve bu başlangıç ​​ve hem gerçekten-- neredeyse sonu gibi end-- 6 00:00:18,090 --> 00:00:18,825 Haftanın altı. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Ben paylaşmak düşündüm eğlenceli aslında biraz. 9 00:00:22,640 --> 00:00:25,370 Ben bir bu kadar çekti ettik Geçtiğimiz dönemlik veri seti. 10 00:00:25,370 --> 00:00:29,710 Sen her sizi sormak Hatırlayacağınız p seti formu online izledim eğer 11 00:00:29,710 --> 00:00:31,580 veya bizzat katıldı ettik. 12 00:00:31,580 --> 00:00:33,020 Ve burada veridir. 13 00:00:33,020 --> 00:00:34,710 Yani bugün çok öngörülebilir. 14 00:00:34,710 --> 00:00:37,126 Ama biz biraz harcamak istedim zaman sizinle yine. 15 00:00:37,126 --> 00:00:40,599 Herkes neden bu varsayım ister misiniz grafik, yukarı aşağı, yukarı aşağı, yani çentikli olan 16 00:00:40,599 --> 00:00:41,265 bu yüzden sürekli? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Ne zirveleri her do ve olukları temsil? 19 00:00:45,130 --> 00:00:46,005 >> İZLEYİCİ: [Duyulmaz] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID MALAN: Gerçekten. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Ve daha eğlenceli, tanrı korusun, Biz Cuma günü bir ders tutun 24 00:00:55,480 --> 00:00:58,960 dönem başında, biz ne bkz ne. 25 00:00:58,960 --> 00:01:03,430 Yani bugün, biraz paylaşmak veri yapıları hakkında daha fazla. 26 00:01:03,430 --> 00:01:06,660 Ve sana bir katı fazlasını vermek beşte sorunlar için zihinsel modeli, 27 00:01:06,660 --> 00:01:07,450 hangi şimdi dışarı. 28 00:01:07,450 --> 00:01:10,817 Yazım olup, burada, yaparız Size bir metin dosyası el 100.000 29 00:01:10,817 --> 00:01:12,650 artı İngilizce kelime ve Eğer zorunda gidiyoruz 30 00:01:12,650 --> 00:01:17,770 akıllıca bunları yüklemek için nasıl anlamaya belleğe, RAM'e, bazı verileri kullanarak 31 00:01:17,770 --> 00:01:19,330 Seçtiğiniz yapısı. 32 00:01:19,330 --> 00:01:22,470 >> Şimdi böyle bir veri yapısı olabilir olmamalıdır muhtemelen, fakat 33 00:01:22,470 --> 00:01:25,630 Oldukça basit bağlantılı liste, hangi biz son kez tanıttı. 34 00:01:25,630 --> 00:01:29,220 Ve bir bağlantılı liste, en azından vardı Bir dizi üzerinde bir avantaj. 35 00:01:29,220 --> 00:01:32,096 Bir avantajı neler var belki bir bağlantılı liste? 36 00:01:32,096 --> 00:01:32,950 >> İZLEYİCİ: Ekleme. 37 00:01:32,950 --> 00:01:33,908 >> DAVID MALAN: Ekleme. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Bununla ne demek istiyorsun? 40 00:01:35,196 --> 00:01:37,872 >> İZLEYİCİ: Anywhere birlikte Liste [duyulamaz]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID MALAN: İyi. 42 00:01:38,770 --> 00:01:42,090 Yani bir eleman yerde ekleyebilirsiniz Listenin ortasında istiyorum 43 00:01:42,090 --> 00:01:45,490 bir şey karıştırmak zorunda kalmadan, hangi bizim sıralama içinde, sonucuna 44 00:01:45,490 --> 00:01:47,630 tartışmalar, değil mutlaka iyi bir şey, 45 00:01:47,630 --> 00:01:51,200 o zaman alır, çünkü aslında taşımak için Bu insanların hepsi sola veya sağa. 46 00:01:51,200 --> 00:01:55,540 Ve böylece bir bağlantılı liste ile yapabilirsiniz Sadece malloc ile tahsis, yeni bir düğüm, 47 00:01:55,540 --> 00:01:58,385 ve daha sonra birkaç güncelleme pointers-- iki, üç operasyon max-- 48 00:01:58,385 --> 00:02:01,480 ve biz birini yuvası edebiliyoruz Bir liste halinde her yerde de. 49 00:02:01,480 --> 00:02:03,550 Başka >> Ne avantajlı oldu Bağlantılı bir listesiyle ilgili? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Evet? 52 00:02:05,659 --> 00:02:06,534 >> İZLEYİCİ: [Duyulmaz] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID MALAN: Mükemmel. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Mükemmel. 57 00:02:11,090 --> 00:02:12,070 Gerçekten dinamik var. 58 00:02:12,070 --> 00:02:15,100 Ve işlemekten değil ki, peşin, bazı sabit boyutu 59 00:02:15,100 --> 00:02:18,750 bellek yığın, gibi olurdu Bir dizi ile, yukarı doğru olan 60 00:02:18,750 --> 00:02:22,455 Eğer yalnızca düğümleri tahsis olmasıdır talep ve böylece sadece kadar alanı kullanarak 61 00:02:22,455 --> 00:02:23,330 Aslında ihtiyacınız olan. 62 00:02:23,330 --> 00:02:26,830 Bir dizi aksine, sen olabilir yanlışlıkla çok az ayrılamadı. 63 00:02:26,830 --> 00:02:28,871 Ve o zaman sadece gidiyor boyun bir ağrı olması 64 00:02:28,871 --> 00:02:32,440 Yeni büyük dizi tahsis etmek, kopyalamak Her şey üzerinde, eski dizi ücretsiz 65 00:02:32,440 --> 00:02:33,990 ve daha sonra işiniz hareket. 66 00:02:33,990 --> 00:02:37,479 Ya da daha kötüsü, sen yol tahsis olabilir aslında ihtiyacınız olandan daha fazla bellek, 67 00:02:37,479 --> 00:02:40,520 ve böylece bir çok için gidiyoruz tabiri caizse, dizi seyrek nüfuslu. 68 00:02:40,520 --> 00:02:44,350 >> Yani bir bağlantılı liste bu size verir dinamizm ve esneklik avantajları 69 00:02:44,350 --> 00:02:46,080 eklemeler ve silmeler ile. 70 00:02:46,080 --> 00:02:48,000 Ama kesinlikle ödenen bir bedel var olmalıdır. 71 00:02:48,000 --> 00:02:50,000 Temalar Aslında, bir sınav sıfır keşfedilmeyi 72 00:02:50,000 --> 00:02:52,430 oldu dengeler bir çift Biz bugüne kadar gördük. 73 00:02:52,430 --> 00:02:56,161 Yani a ödenen fiyat ya da ne var Bağlantılı bir liste olumsuz? 74 00:02:56,161 --> 00:02:56,660 Evet. 75 00:02:56,660 --> 00:02:57,560 >> İZLEYİCİ: Hayır rasgele erişim. 76 00:02:57,560 --> 00:02:58,809 >> DAVID MALAN: Hayır rasgele erişim. 77 00:02:58,809 --> 00:02:59,540 Ama kimin umurunda? 78 00:02:59,540 --> 00:03:01,546 Rastgele erişim zorlayıcı gelmiyor. 79 00:03:01,546 --> 00:03:02,421 >> İZLEYİCİ: [Duyulmaz] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID MALAN: Kesinlikle. 82 00:03:05,740 --> 00:03:07,580 Eğer sahip olmak istiyorsanız, Belirli bir algorithm-- 83 00:03:07,580 --> 00:03:10,170 ve ben aslında teklif izin Özellikle ikili arama, hangi 84 00:03:10,170 --> 00:03:12,600 biz oldukça Kişilik Sokak kullandım biridir Eğer rasgele erişim yoksa, 85 00:03:12,600 --> 00:03:15,516 Eğer bu basit aritmetik yapamaz Orta eleman bulma gibi 86 00:03:15,516 --> 00:03:16,530 ve sağ atlama. 87 00:03:16,530 --> 00:03:20,239 Bunun yerine ilk başta başlamak zorunda eleman ve doğrusal soldan arama 88 00:03:20,239 --> 00:03:22,780 sağa bulmak istiyorsanız orta veya diğer herhangi bir unsuru. 89 00:03:22,780 --> 00:03:24,410 >> İZLEYİCİ: Muhtemelen daha fazla bellek alır. 90 00:03:24,410 --> 00:03:25,040 >> DAVID MALAN: daha fazla bellek Alır. 91 00:03:25,040 --> 00:03:27,464 Nerede ek bir bellekte gelen maliyet? 92 00:03:27,464 --> 00:03:28,339 >> İZLEYİCİ: [Duyulmaz] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID MALAN: Kesinlikle. 95 00:03:33,440 --> 00:03:35,679 Burada bu durumda, biz tamsayılar için bir bağlantılı liste, 96 00:03:35,679 --> 00:03:37,470 ve henüz biz iki katına ediyoruz bellek miktarı 97 00:03:37,470 --> 00:03:39,680 biz de bu işaretçileri saklayarak gerekir. 98 00:03:39,680 --> 00:03:42,090 Gibi büyük bir anlaşma Şimdi daha az senin yapılar büyük olsun 99 00:03:42,090 --> 00:03:45,320 ve bir numara depolamak ama belki bir öğrenci ya da başka bir nesne. 100 00:03:45,320 --> 00:03:46,880 Ama nokta kesinlikle kalır. 101 00:03:46,880 --> 00:03:49,421 Ve böylece operasyonların bir dizi bağlantılı listelerde çağrıldı 102 00:03:49,421 --> 00:03:50,570 n- doğrusal büyük O idi. 103 00:03:50,570 --> 00:03:54,730 Ekleme veya arama gibi şeyler veya davanın bir eleman olarak silme 104 00:03:54,730 --> 00:03:57,720 en sonunda olması oldu bu sıralama dışı olup olmadığı listesi. 105 00:03:57,720 --> 00:04:01,167 >> Bazen şanslı olsun ve olabilir Bu operasyonlar öylesine alt sınır 106 00:04:01,167 --> 00:04:04,250 sen eğer aynı zamanda sabit zaman olabilir her zaman ilk elemanı bakarak, 107 00:04:04,250 --> 00:04:05,070 örneğin. 108 00:04:05,070 --> 00:04:09,360 Ama sonuçta, biz söz Holy Grail ulaşmak için 109 00:04:09,360 --> 00:04:12,630 Veri yapıları ya da Bazı yaklaşım bunların, 110 00:04:12,630 --> 00:04:14,290 zaman sabiti, bu arada. 111 00:04:14,290 --> 00:04:17,579 Biz öğeleri bulmak veya öğeleri ekleyebilir miyim veya bir listeden öğeleri kaldırmak? 112 00:04:17,579 --> 00:04:19,059 Biz çok yakında göreceğiz. 113 00:04:19,059 --> 00:04:21,100 Ve o bir dışarı çıkıyor Biz konum mekanizmaların 114 00:04:21,100 --> 00:04:23,464 Bugün kullanmaya başlayacak, p yıllık kullanım, beş set 115 00:04:23,464 --> 00:04:24,630 aslında oldukça tanıdık. 116 00:04:24,630 --> 00:04:27,430 Örneğin, bu bir demet halinde sınav kitapların, her biri 117 00:04:27,430 --> 00:04:29,660 Bir öğrencinin ilk sahiptir Üzerinde son ismi, 118 00:04:29,660 --> 00:04:31,820 ve ben onları pick up Bir sınav sonunda, 119 00:04:31,820 --> 00:04:33,746 ve hepsi güzelsin rastgele bir sırayla çok, 120 00:04:33,746 --> 00:04:36,370 ve biz sıralama hakkında gitmek istiyorum Bu sınavlar böylece bir kez derecelendirildi 121 00:04:36,370 --> 00:04:38,661 sadece çok daha kolay ve hızlı onları geri el 122 00:04:38,661 --> 00:04:40,030 alfabetik öğrencilere. 123 00:04:40,030 --> 00:04:42,770 Içgüdülerin ne olurdu Bu gibi sınavlardan bir yığın için? 124 00:04:42,770 --> 00:04:45,019 >> Peki, siz de benim gibi iseniz, Bu m olduğunu görebilirsiniz, 125 00:04:45,019 --> 00:04:48,505 bu yüzden, çeşit içine bu koymak için gidiyorum Bu benim tablo veya benim zemin ise 126 00:04:48,505 --> 00:04:50,650 Ben bir şeyler yayılıyor ediyorum Şunları bir konrtol ya da benim dizi gerçekten-- 127 00:04:50,650 --> 00:04:52,210 Ben orada Ms tüm koymak olabilir. 128 00:04:52,210 --> 00:04:52,710 Ah. 129 00:04:52,710 --> 00:04:55,020 İşte bir A. yüzden belki var Burada As koydu. 130 00:04:55,020 --> 00:04:55,520 Ah. 131 00:04:55,520 --> 00:04:57,980 İşte ben gidiyorum başka A. var buraya koymak için. 132 00:04:57,980 --> 00:05:02,490 İşte Z. İşte başka M. Ve böyledir Ben böyle yığınları yapmaya başlamak olabilir. 133 00:05:02,490 --> 00:05:06,620 Ve sonra belki daha sonra gitmek istiyorum ve çeşit çok nitpicky-ly sıralama 134 00:05:06,620 --> 00:05:07,710 Bireysel kazıklar. 135 00:05:07,710 --> 00:05:11,300 Ama gelin ben bakmak ederim Ben teslim olduğum girişindeki 136 00:05:11,300 --> 00:05:14,016 ve bazı hesaplanır yapacak O girişine göre karar. 137 00:05:14,016 --> 00:05:15,640 O A ile başlıyorsa, oraya koydum. 138 00:05:15,640 --> 00:05:18,980 O Z ile başlıyorsa, bunu üzerine koymak arasında var, ve her şeyi. 139 00:05:18,980 --> 00:05:22,730 >> Yani bu var bir tekniktir Genellikle hashing-- lH-A-S-H- olarak bilinen 140 00:05:22,730 --> 00:05:26,550 hangi genelde almak demektir giriş ve hesaplamak için bu girişi kullanarak 141 00:05:26,550 --> 00:05:30,940 değeri, genel olarak çok sayıda, ve numara depolama içine indeks 142 00:05:30,940 --> 00:05:32,260 konteyner, bir dizi gibi. 143 00:05:32,260 --> 00:05:35,490 Bu yüzden, diğer bir deyişle, bir olabilir hash fonksiyonu, kafamda gibi, 144 00:05:35,490 --> 00:05:37,940 Birisi bu görürsem o A ile başlayan isim, 145 00:05:37,940 --> 00:05:40,190 Ben o haritaya gidiyorum kafamda sıfıra. 146 00:05:40,190 --> 00:05:44,160 Ben Z birini görürsen, ben değilim Kafamın içinde 25 bu haritaya gidiyor 147 00:05:44,160 --> 00:05:46,220 ve sonra içine koymak son, en kazık. 148 00:05:46,220 --> 00:05:50,990 >> Şimdi, eğer beynim değil düşünmek ama bir C programı, ne numaralar olabilir 149 00:05:50,990 --> 00:05:53,170 Eğer aynı sonucu elde etmek güveniyor? 150 00:05:53,170 --> 00:05:55,594 Diğer bir deyişle, eğer ASCII karakter A vardı 151 00:05:55,594 --> 00:05:57,510 nasıl belirliyorsunuz ne kepçe koymak için? 152 00:05:57,510 --> 00:05:59,801 Muhtemelen istemiyorum kova 65, içine koymak 153 00:05:59,801 --> 00:06:01,840 Orada gibi olurdu iyi bir neden için. 154 00:06:01,840 --> 00:06:04,320 Nereye A koymak istiyorum ASCII değeri açısından? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Nereye onun ASCII yapmak istiyorsun değer bir akıllı kova ile gelip 157 00:06:08,920 --> 00:06:09,480 koymak için? 158 00:06:09,480 --> 00:06:10,206 >> İZLEYİCİ: Eksi A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID MALAN: Evet. 160 00:06:10,956 --> 00:06:13,190 Yani eksi A veya eksi özellikle 65 o ise 161 00:06:13,190 --> 00:06:18,240 sermaye A. Veya 98 ise Bir küçük bir var. 162 00:06:18,240 --> 00:06:21,300 Ve böylece çok bize sağlayacak basit ve çok aritmetik, 163 00:06:21,300 --> 00:06:23,260 Böyle bir kovaya bir şey koymak. 164 00:06:23,260 --> 00:06:26,010 Yani biz aslında yapmak çıkıyor Bu aynı zamanda, hatta sınavlar ile. 165 00:06:26,010 --> 00:06:29,051 Hatırlayacağınız olabilir Yani >> Eğer çember senin kapaktaki öğretim arkadaşın adı. 166 00:06:29,051 --> 00:06:32,270 Ve TF isimleri düzenlendi alfabetik bu sütunlara, 167 00:06:32,270 --> 00:06:34,400 iyi, ister inanın ister inanmayın, zaman hepimiz 80 artı 168 00:06:34,400 --> 00:06:37,800 , sınıfa geçen gece birlikte var Bizim derecelendirme sürecinde son adım 169 00:06:37,800 --> 00:06:41,830 Büyük bir içine sınavlar karma için [duyulamaz] zemine uzay 170 00:06:41,830 --> 00:06:45,110 ve herkesin sınavlar düzenlemek için kendi TF yılların tam sırayla 171 00:06:45,110 --> 00:06:47,700 kapaktaki isimler, çünkü o zaman bizim için çok daha kolay 172 00:06:47,700 --> 00:06:51,290 Bu kullanarak doğrusal arama için arama veya zeka çeşit 173 00:06:51,290 --> 00:06:54,050 TF bulmak için onun veya Onun Öğrencilerin sınavlar. 174 00:06:54,050 --> 00:06:56,060 Karma bir >> Yani bu fikir sen görürsünüz 175 00:06:56,060 --> 00:07:00,520 Oldukça güçlü aslında güzel sıradan ve çok sezgisel, 176 00:07:00,520 --> 00:07:03,000 çok belki bölmek gibi ve fethet haftada sıfır oldu. 177 00:07:03,000 --> 00:07:05,250 Hackathon ben hızlı ileri Birkaç yıl önce. 178 00:07:05,250 --> 00:07:08,040 Bu Zamyla ve bir çift oldu diğer personel tebrik öğrencileri 179 00:07:08,040 --> 00:07:09,030 onlar geldi. 180 00:07:09,030 --> 00:07:12,680 Ve biz katlama bir sürü vardı isim etiketleri ile orada tablolar. 181 00:07:12,680 --> 00:07:15,380 Ve biz isim etiketleri düzenledi Orada üzerinde As gibi 182 00:07:15,380 --> 00:07:16,690 ve orada Zs. 183 00:07:16,690 --> 00:07:20,350 Ve böylece TFs biri çok akıllıca Talimatlar olarak bu yazdı 184 00:07:20,350 --> 00:07:21,030 gün. 185 00:07:21,030 --> 00:07:24,480 Ve dönem bu hafta 12 tüm mükemmel mantıklı ve herkes yaptı 186 00:07:24,480 --> 00:07:25,310 ne yapacağını biliyordu. 187 00:07:25,310 --> 00:07:27,900 Ama her zaman size ettik Aynı şekilde sıraya, 188 00:07:27,900 --> 00:07:30,272 Eğer uygulama konum Bir karma aynı kavramı. 189 00:07:30,272 --> 00:07:31,730 Yani bu biraz resmileştirmek verelim. 190 00:07:31,730 --> 00:07:32,890 İşte bir dizidir. 191 00:07:32,890 --> 00:07:36,820 Biraz olmak üzere çizilmiş Geniş sadece görsel, tasvir, 192 00:07:36,820 --> 00:07:38,920 Biz dizeleri koymak olabilir Böyle bir şey. 193 00:07:38,920 --> 00:07:41,970 Ve bu dizi açıkça boyutu 26 toplam. 194 00:07:41,970 --> 00:07:43,935 Ve bir şey denir masa keyfi. 195 00:07:43,935 --> 00:07:48,930 Ama bu sadece bir sanatçının yorumuyla olduğu Bir karma tablo ne olabileceğini. 196 00:07:48,930 --> 00:07:52,799 >> Yani bir karma tablo şimdi gidiyor Bir üst düzey veri yapısı. 197 00:07:52,799 --> 00:07:54,840 Günün sonunda Size görmek üzereyiz 198 00:07:54,840 --> 00:07:58,700 Bir karma tablo, uygulamaya hangi çok check-in hattı gibi 199 00:07:58,700 --> 00:08:02,059 çok böyle bir hackathon de masa sınav kitapları sıralamak için kullanılır. 200 00:08:02,059 --> 00:08:03,850 Ama karma tablo Bu yüksek seviyede sıralama 201 00:08:03,850 --> 00:08:08,250 Bir dizi kullanabilirsiniz kavramı , davlumbaz bunu uygulamak için altında 202 00:08:08,250 --> 00:08:11,890 ya da bir uzunluk listesini kullanmak, hatta olabilir belki bazı diğer veri yapıları. 203 00:08:11,890 --> 00:08:15,590 Ve şimdi bu theme-- alma var Bu temel bileşenlerin bazıları 204 00:08:15,590 --> 00:08:18,310 Bir dizi ve bu bina gibi uzunluğu listesinin hemen bloke 205 00:08:18,310 --> 00:08:21,740 ve biz inşa edebilirsiniz başka ne görmeye Bunların üstüne, maddeler gibi 206 00:08:21,740 --> 00:08:26,550 Bir tarifi içine, daha yapım ilginç ve kullanışlı nihai sonuçlar. 207 00:08:26,550 --> 00:08:28,680 >> Karma tablo ile Böylece Biz bunu uygulamak olabilir 208 00:08:28,680 --> 00:08:32,540 bellekte resimsel bu gibi ama nasıl aslında yukarı kodlanmış olabilir? 209 00:08:32,540 --> 00:08:33,789 Peki, belki de basitçe budur. 210 00:08:33,789 --> 00:08:38,270 Tüm kapaklar KAPASİTE, sadece ise Örneğin 26 için bir constant--, 211 00:08:38,270 --> 00:08:42,030 alphabet-- 26 harfler için Benim değişken tablo diyebilirsiniz, 212 00:08:42,030 --> 00:08:45,630 ve ben gidiyorum iddia olabilir Orada, ya da dize karakter yıldız koymak. 213 00:08:45,630 --> 00:08:49,880 Yani o kadar basit olmadığını, bu gibi Bir hash tablosu uygulamak istiyorum. 214 00:08:49,880 --> 00:08:51,490 Ve yine, bu gerçekten sadece bir dizidir. 215 00:08:51,490 --> 00:08:53,198 Fakat yine de, bir karma tablo ne olacak şimdi 216 00:08:53,198 --> 00:08:57,470 Sadece bu soyut bir veri türü çağrı üstüne bir kavramsal tabakaların tür 217 00:08:57,470 --> 00:09:00,780 daha dünyevi bir şey Şimdi bir dizi gibi. 218 00:09:00,780 --> 00:09:02,960 >> Şimdi, nasıl gidiyoruz yapmak sorunlarının çözümü hakkında? 219 00:09:02,960 --> 00:09:06,980 Peki, daha önce ben lüks vardı burada yeterli tablo alanı olan 220 00:09:06,980 --> 00:09:09,460 Ben koymak böylece sınavlar yerde ben istedim. 221 00:09:09,460 --> 00:09:10,620 Yani şöyle burada gidebilir. 222 00:09:10,620 --> 00:09:12,100 Zs buraya gidebilir. 223 00:09:12,100 --> 00:09:13,230 Ms buraya gidebilir. 224 00:09:13,230 --> 00:09:14,740 Ve sonra bazı ekstra boşluk vardı. 225 00:09:14,740 --> 00:09:18,740 Ama bu bir hile hakkının bir parçasıdır Şimdi bu tabloda, çünkü ben eğer gerçekten 226 00:09:18,740 --> 00:09:22,720 bir dizi olarak bunu düşündüm, sadece bir Bazı sabit boyutta olacak. 227 00:09:22,720 --> 00:09:25,380 >> Yani teknik olarak, ben çekerseniz Başka bir öğrencinin sınav kadar 228 00:09:25,380 --> 00:09:28,490 ve bu kişinin, oh, bakın isim, çok bir A ile başlar 229 00:09:28,490 --> 00:09:30,980 Ben tür oraya koymak istiyorum. 230 00:09:30,980 --> 00:09:34,740 Ama en kısa sürede ben eğer, orada dediği gibi Bu tabloyu gerçekten bir dizi temsil, 231 00:09:34,740 --> 00:09:37,840 Ben geçersiz kılma veya clobbering için gidiyorum kim bu öğrencinin sınav olduğunu. 232 00:09:37,840 --> 00:09:38,340 Doğru? 233 00:09:38,340 --> 00:09:41,972 Bu bir dizi ise, tek bir şey olabilir Bu hücrelerin ya da elemanların her gidin. 234 00:09:41,972 --> 00:09:43,680 Ve bu yüzden bir tür var almak ve seçin. 235 00:09:43,680 --> 00:09:45,735 >> Şimdi önce ben tür hile ve bu veya ben yaptım 236 00:09:45,735 --> 00:09:47,526 sadece tür yığılmış Her diğerinin üzerinde onları. 237 00:09:47,526 --> 00:09:49,170 Ama bu kodda uçmak için gitmiyor. 238 00:09:49,170 --> 00:09:52,260 Yani nerede koyabilirsiniz Adını, ikinci öğrenci 239 00:09:52,260 --> 00:09:54,964 Ben vardı bu ise A Mevcut tablo alanı? 240 00:09:54,964 --> 00:09:57,880 Ve ben üç yuva ve kullandım Sadece bir kaç diğerleri var gibi görünüyor. 241 00:09:57,880 --> 00:09:58,959 Ne yapabilirdi? 242 00:09:58,959 --> 00:09:59,834 HEDEF KİTLE: [Duyulmaz] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID MALAN: Evet. 245 00:10:01,315 --> 00:10:02,370 Belki Sadece basit tutalım. 246 00:10:02,370 --> 00:10:02,660 Doğru? 247 00:10:02,660 --> 00:10:04,243 Ben koymak istiyorum nerede uymuyor. 248 00:10:04,243 --> 00:10:07,450 Yani koymak için gidiyorum teknik bir B gitmek istiyorum nereye. 249 00:10:07,450 --> 00:10:09,932 Şimdi, tabii, ben başlıyorum Bir köşeye kendimi boyamak için. 250 00:10:09,932 --> 00:10:11,890 Ben bir öğrenci alırsanız Adını aslında B, 251 00:10:11,890 --> 00:10:14,840 Şimdi B biraz hareket olacak ileri, gibi, evet, ne olabilir 252 00:10:14,840 --> 00:10:17,530 Bu bir B ise, şimdi buraya gitmek zorunda. 253 00:10:17,530 --> 00:10:20,180 >> Ve böylece bu çok hızlı bir şekilde , sorunlu hale gelebilir 254 00:10:20,180 --> 00:10:23,850 ama bir teknik, bu aslında doğrusal tarama olarak adlandırılır, 255 00:10:23,850 --> 00:10:26,650 bu sayede sadece düşünün sizin Dizi hattı boyunca olmak. 256 00:10:26,650 --> 00:10:29,680 Ve sen sadece tür soruşturma veya Her mevcut elemanı kontrol 257 00:10:29,680 --> 00:10:31,360 kullanılabilir bir yer arayan. 258 00:10:31,360 --> 00:10:34,010 Ve en kısa sürede bulmak gibi bir, sen orada bırakın. 259 00:10:34,010 --> 00:10:38,390 >> Şimdi, fiyat şimdi ödenmekte Bu çözüm için ne olduğunu? 260 00:10:38,390 --> 00:10:41,300 Biz sabit bir boyut dizi var, ve ben isimleri eklediğinizde 261 00:10:41,300 --> 00:10:44,059 içine, en azından başlangıçta, ne sokma çalışma süresi 262 00:10:44,059 --> 00:10:46,350 öğrencilerin 'koymak için Doğru kovalarda sınavlar? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Neyin Büyük O? 265 00:10:50,002 --> 00:10:51,147 >> İZLEYİCİ: n. 266 00:10:51,147 --> 00:10:52,480 DAVID MALAN: Ben n büyük O duydum. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Doğru değil. 269 00:10:54,300 --> 00:10:56,490 Ama biz ayrı alay edeceğiz neden sadece bir an. 270 00:10:56,490 --> 00:10:57,702 Başka ne olabilir? 271 00:10:57,702 --> 00:10:58,755 >> İZLEYİCİ: [Duyulmaz] 272 00:10:58,755 --> 00:11:00,380 DAVID MALAN: Ve bana görsel yapalım. 273 00:11:00,380 --> 00:11:04,720 Yani bu mektup S. olduğunu varsayalım 274 00:11:04,720 --> 00:11:05,604 >> İZLEYİCİ: Bu biri. 275 00:11:05,604 --> 00:11:06,520 DAVID MALAN: Bu biri. 276 00:11:06,520 --> 00:11:06,710 Doğru? 277 00:11:06,710 --> 00:11:08,950 Bu dizi, olduğu rastgele erişim anlamına gelir. 278 00:11:08,950 --> 00:11:11,790 Ve biz bu düşünüyorsanız sıfır ve bu gibi 25 olarak, 279 00:11:11,790 --> 00:11:13,800 ve biz farkında, oh, burada benim girişi S var, 280 00:11:13,800 --> 00:11:16,350 Ben kesinlikle dönüştürebilirsiniz S ASCII karakter, 281 00:11:16,350 --> 00:11:18,540 karşılık gelen bir sayıya sıfır ile 25 arasında 282 00:11:18,540 --> 00:11:20,910 ve hemen ait olduğu yere koymak. 283 00:11:20,910 --> 00:11:26,120 >> Ama tabii, en kısa sürede ben almak gibi isim, ikinci bir kişi A veya B veya C 284 00:11:26,120 --> 00:11:29,300 Sonunda, ben kullandım, eğer lineer, benim çözüm olarak sondalama 285 00:11:29,300 --> 00:11:31,360 çalışma süresi En kötü durumda ekleme 286 00:11:31,360 --> 00:11:33,120 aslında ne içine intikal edecek? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Ve ben burada duydunuz doğru erken. 289 00:11:36,045 --> 00:11:36,920 HEDEF KİTLE: [Duyulmaz] 290 00:11:36,920 --> 00:11:41,620 DAVID MALAN: Yani gerçekten bir kez n Eğer yeterince büyük bir veri seti var. 291 00:11:41,620 --> 00:11:44,410 Böylece, bir yandan, eğer senin dizi yeterince büyük 292 00:11:44,410 --> 00:11:48,287 ve verileriniz size yeterince seyrek Bu güzel sabit zaman olsun. 293 00:11:48,287 --> 00:11:50,620 Ama en kısa sürede başlatmak gibi Daha fazla ve daha fazla eleman alma, 294 00:11:50,620 --> 00:11:53,200 ve sadece istatistiksel olsun harfi ile daha fazla kişi 295 00:11:53,200 --> 00:11:56,030 Bir şekilde kendi adını veya mektup B, potansiyel olabilir 296 00:11:56,030 --> 00:11:57,900 bir şey daha doğrusal dönüşebilir. 297 00:11:57,900 --> 00:11:59,640 Yani oldukça mükemmel değil. 298 00:11:59,640 --> 00:12:00,690 Yani biz daha iyi yapabileceğini? 299 00:12:00,690 --> 00:12:03,210 >> Peki, ne oldu bizim çözüm ne zaman biz önce 300 00:12:03,210 --> 00:12:06,820 daha fazla dinamizm istiyorum Bir dizi gibi bir şey izin? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 HEDEF KİTLE: [Duyulmaz] 303 00:12:08,960 --> 00:12:10,030 DAVID MALAN: Ne tanıtmak mı? 304 00:12:10,030 --> 00:12:10,530 Evet. 305 00:12:10,530 --> 00:12:11,430 Yani bir bağlantılı liste. 306 00:12:11,430 --> 00:12:14,430 Peki, bir bağlantılı ne görelim Liste yerine bizim için yapabilir. 307 00:12:14,430 --> 00:12:17,630 Peki, beni bu biz teklif edelim aşağıdaki gibi resim çizmek. 308 00:12:17,630 --> 00:12:19,620 Şimdi bu farklı Örneğin gelen görüntü 309 00:12:19,620 --> 00:12:24,750 Farklı bir metin, aslında, o aslında boyutu 31 bir dizi kullanıyor. 310 00:12:24,750 --> 00:12:28,220 Ve bu yazar sadece dizeleri hash karar 311 00:12:28,220 --> 00:12:32,430 kişinin adlarına göre değil, ama onların doğum tarihleri ​​esas. 312 00:12:32,430 --> 00:12:35,680 Bağımsız olarak ayın, bu biçim Bir ayın ilk doğan eğer 313 00:12:35,680 --> 00:12:39,580 veya ayın 31., yazar Bu değere göre karma olacak, 314 00:12:39,580 --> 00:12:44,154 biraz dışarı isimleri yaymak amacıyla sadece 26 noktalar izin verebilir daha fazla. 315 00:12:44,154 --> 00:12:47,320 Ve belki de biraz daha üniforma var alfabetik harflerle giderek daha, 316 00:12:47,320 --> 00:12:50,236 Çünkü elbette muhtemelen orada isimler ile dünyanın daha fazla kişi 317 00:12:50,236 --> 00:12:54,020 Kesinlikle daha bir o başlangıç alfabenin diğer bazı harfler. 318 00:12:54,020 --> 00:12:56,380 Yani belki bu biraz daha homojen, varsayarak 319 00:12:56,380 --> 00:12:58,640 düzgün bir dağılım Bir ay boyunca bebeklerin. 320 00:12:58,640 --> 00:12:59,990 >> Ama, tabii, bu hala eksik olduğunu. 321 00:12:59,990 --> 00:13:00,370 Doğru? 322 00:13:00,370 --> 00:13:01,370 Biz çarpışmalar yapıyoruz. 323 00:13:01,370 --> 00:13:04,680 Bu Çoklu insanlar veri yapısı halen 324 00:13:04,680 --> 00:13:08,432 en azından aynı doğum sahip Eğer ayın bakılmaksızın konum. 325 00:13:08,432 --> 00:13:09,640 Ama yazar ne yapmış? 326 00:13:09,640 --> 00:13:13,427 Biz bir dizi var gibi Eh, o görünüyor dikey çizilmiş sol tarafta, 327 00:13:13,427 --> 00:13:15,010 ama bu sadece bir sanatçının sunumu var. 328 00:13:15,010 --> 00:13:18,009 It does not matter ne yönde size Bir dizi çizmek, yine bir dizi var. 329 00:13:18,009 --> 00:13:20,225 Bu görünüşte bir dizi nedir? 330 00:13:20,225 --> 00:13:21,500 >> İZLEYİCİ: Bağlantılı listesi. 331 00:13:21,500 --> 00:13:21,650 >> DAVID MALAN: Evet. 332 00:13:21,650 --> 00:13:23,490 Bir var gibi görünüyor bağlantılı liste dizisi. 333 00:13:23,490 --> 00:13:26,490 Yani yine, tür bu noktaya Şimdi bu veri yapılarını kullanarak 334 00:13:26,490 --> 00:13:28,550 daha fazla madde olarak ilginç çözeltiler, 335 00:13:28,550 --> 00:13:30,862 kesinlikle bir alabilir Temel, bir dizi gibi, 336 00:13:30,862 --> 00:13:33,320 ve daha sonra bir şey almak Bağlantılı bir listesi gibi ilginç 337 00:13:33,320 --> 00:13:36,660 ve hatta daha da içine bunları birleştirmek daha ilginç veri yapısı. 338 00:13:36,660 --> 00:13:39,630 Ve gerçekten de, bu çok olur Bir karma tablo denir, 339 00:13:39,630 --> 00:13:42,610 böylece dizi Gerçekten hash tablosu, 340 00:13:42,610 --> 00:13:45,600 ama bu karma tablo var zincirler, bu yüzden, konuşmak 341 00:13:45,600 --> 00:13:50,220 Bu büyüyebilir veya dayalı küçültmek elemanlarının sayısı Eklemek istediğiniz. 342 00:13:50,220 --> 00:13:52,990 >> Şimdi buna göre, ne Şimdi çalışma süresi? 343 00:13:52,990 --> 00:13:58,030 Birini eklemek istiyorsanız 31 Ekim kimin doğum günü, 344 00:13:58,030 --> 00:13:59,040 Nerede o gidiyor? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Tamam. 347 00:14:01,030 --> 00:14:02,819 O 31 diyor çok altında. 348 00:14:02,819 --> 00:14:03,610 Ve bu mükemmel. 349 00:14:03,610 --> 00:14:05,060 O zaman sabiti oldu. 350 00:14:05,060 --> 00:14:08,760 Ama biz başka birini ne bulursanız kimin doğum günü, bakalım edilir, 351 00:14:08,760 --> 00:14:10,950 Ekim, Kasım, Aralık 31? 352 00:14:10,950 --> 00:14:12,790 Nerede o gidecek? 353 00:14:12,790 --> 00:14:13,290 Aynı şey. 354 00:14:13,290 --> 00:14:13,970 Olsa İki adım. 355 00:14:13,970 --> 00:14:15,303 Yani olsa sabit değil mi? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Tamam. 358 00:14:16,860 --> 00:14:17,840 Şu anda öyle. 359 00:14:17,840 --> 00:14:20,570 Ancak genel durumda, Biz eklemek daha fazla insan, 360 00:14:20,570 --> 00:14:23,790 olasılıksal, biz gidiyoruz daha çarpışmalar alır. 361 00:14:23,790 --> 00:14:26,820 >> Şimdi bu biraz iyi teknik Çünkü 362 00:14:26,820 --> 00:14:34,580 Şimdi benim zincirler olabilir En kötü durumda ne kadar? 363 00:14:34,580 --> 00:14:38,890 Ben bunu daha içine n insanları eklerseniz gelişmiş veri yapısı, n insanlar, 364 00:14:38,890 --> 00:14:41,080 En kötü durumda o n olacak. 365 00:14:41,080 --> 00:14:41,815 Neden? 366 00:14:41,815 --> 00:14:43,332 >> İZLEYİCİ: Çünkü eğer herkes Aynı doğum günü var, 367 00:14:43,332 --> 00:14:44,545 onlar tek satır olması için gidiyoruz. 368 00:14:44,545 --> 00:14:45,420 DAVID MALAN: Mükemmel. 369 00:14:45,420 --> 00:14:47,480 Bu, biraz yapmacık olabilir ama gerçekten kötü durumda, 370 00:14:47,480 --> 00:14:50,117 herkes aynı doğum günü varsa, Eğer sahip girdiler verilen, 371 00:14:50,117 --> 00:14:51,950 Eğer bir için gidiyoruz kitlesel uzun zincirli. 372 00:14:51,950 --> 00:14:54,241 Ve böylece, bunu bir çağrı olabilir tablo hash, ama gerçekten var 373 00:14:54,241 --> 00:14:56,810 sadece büyük bir bağlantılı liste israf alanı bir sürü. 374 00:14:56,810 --> 00:15:00,460 Ama genel olarak, biz varsayalım eğer en az doğum uniform-- olan 375 00:15:00,460 --> 00:15:01,750 ve muhtemelen değildir. 376 00:15:01,750 --> 00:15:02,587 Ben o kadar yapıyorum. 377 00:15:02,587 --> 00:15:04,420 Ama biz varsayalım eğer, için tartışma hatır 378 00:15:04,420 --> 00:15:07,717 Onlar, daha sonra teorik olarak, eğer olduklarını bu dikey temsilidir 379 00:15:07,717 --> 00:15:11,050 dizinin, iyi o zaman umarım sen vardır, bilirsin zincirleri almak için gidiyoruz, 380 00:15:11,050 --> 00:15:15,880 hemen hemen aynı uzunlukta burada her bir Bu ayın bir gününü temsil eder. 381 00:15:15,880 --> 00:15:19,930 >> Ayda 31 gün var Şimdi eğer, O gerçekten benim çalışma süresi anlamına gelir 382 00:15:19,930 --> 00:15:25,230 31 üzerinde n büyük O, olduğu Doğrusal daha iyi hissediyor. 383 00:15:25,230 --> 00:15:27,950 Ama biri ne bizim taahhütler birkaç hafta 384 00:15:27,950 --> 00:15:31,145 önce bu ifade için geldi zaman Bir algoritmanın çalışma süresi? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Sadece sadece yüksek mertebeden dönem bakmak. 387 00:15:35,190 --> 00:15:35,690 Doğru? 388 00:15:35,690 --> 00:15:37,400 31 kesinlikle yararlıdır. 389 00:15:37,400 --> 00:15:39,610 Ama bu yine de n büyük O'dur. 390 00:15:39,610 --> 00:15:41,730 Ama temalardan birini sorunu beş set 391 00:15:41,730 --> 00:15:43,950 için olacak Kesinlikle kabul, 392 00:15:43,950 --> 00:15:47,320 asimptotik, teorik Bu veri yapısı 393 00:15:47,320 --> 00:15:50,470 Sadece daha iyidir bir büyük bağlantılı liste. 394 00:15:50,470 --> 00:15:53,550 Ve gerçekten de, en kötü durumda, bu karma tablo bu içine intikal olabilir. 395 00:15:53,550 --> 00:15:57,620 >> Ama gerçek dünyada, bize insanlar Kendi Mac veya PC veya ne olursa olsun 396 00:15:57,620 --> 00:16:01,240 ve gerçek dünya çalıştıran gerçek dünya verileri yazılım, 397 00:16:01,240 --> 00:16:03,260 hangi algoritmanın tercih edeceksin? 398 00:16:03,260 --> 00:16:09,180 son adımlar ya götüren bir n 31 adımda bölünmesiyle alır bir 399 00:16:09,180 --> 00:16:12,900 bazı veri parçası bulmak için veya bazı bilgileri aramak için? 400 00:16:12,900 --> 00:16:16,580 Ben kesinlikle 31 yapar demek Gerçek dünyada bir fark. 401 00:16:16,580 --> 00:16:18,540 Bu 31 kat daha hızlıdır. 402 00:16:18,540 --> 00:16:20,880 Ve biz insanlar kesinlikle vardır takdir gidiyor. 403 00:16:20,880 --> 00:16:23,004 >> Yani ikilemi fark Orada aslında arası 404 00:16:23,004 --> 00:16:25,920 teorik şeyler hakkında konuşmaya Kesinlikle ve asimtotik hangi 405 00:16:25,920 --> 00:16:28,760 Gördüğümüz gibi bir değere sahiptir, ama gerçek dünyada, 406 00:16:28,760 --> 00:16:32,930 Sadece yapma hakkında bakım Genel girişler için insan mutlu, 407 00:16:32,930 --> 00:16:36,010 Eğer çok iyi kabul etmek isteyebilirsiniz Evet ise, bu doğrusal, aslında, 408 00:16:36,010 --> 00:16:38,360 ancak 31 kat daha hızlı olduğunu daha doğrusal olabilir. 409 00:16:38,360 --> 00:16:41,610 Ve daha iyisi, biz sadece gerekmez Bir doğum tarihi gibi keyfi bir şey yapmak, 410 00:16:41,610 --> 00:16:44,030 biz biraz harcayabilirsiniz daha fazla zaman ve akıllılık 411 00:16:44,030 --> 00:16:47,140 ve biz ne yapacağını düşünmek, Verilen bir kişinin ismi ve belki 412 00:16:47,140 --> 00:16:50,130 kendi doğum olanlar birleştirmek için maddeler şey anlamaya 413 00:16:50,130 --> 00:16:52,720 Bu gerçekten daha üniforma ve az çentikli, 414 00:16:52,720 --> 00:16:56,250 bu nedenle bu resim daha konuşmak Şu anda bu olabilir göstermektedir. 415 00:16:56,250 --> 00:16:57,750 Nasıl kodu bu uygulamak? 416 00:16:57,750 --> 00:17:00,280 Peki, beni bu biz teklif edelim sadece biz ettik bazı sözdizimi ödünç 417 00:17:00,280 --> 00:17:01,799 Bugüne kadar bir kaç kez kullanılır. 418 00:17:01,799 --> 00:17:03,590 Ve ben tanımlamak için gidiyorum Bir düğüm, bu durum, yine 419 00:17:03,590 --> 00:17:06,812 sadece bazı için genel bir terimdir bir veri yapısı için kap. 420 00:17:06,812 --> 00:17:09,020 Bunu teklif edeceğim bir dize orada oluyor. 421 00:17:09,020 --> 00:17:11,369 Ama biz çekmeye başlamak için gidiyoruz Şimdi kapalı tekerlekleri eğitim bu. 422 00:17:11,369 --> 00:17:13,230 >> Daha fazla CS50 kütüphanesi Gerçekten, istediğiniz sürece 423 00:17:13,230 --> 00:17:15,230 senin finali için kullanmak ince proje, 424 00:17:15,230 --> 00:17:18,569 ama şimdi biz geri çekmek için gidiyoruz perde ve sadece bir karakter yıldızı olduğunu söylüyorlar. 425 00:17:18,569 --> 00:17:22,069 Kelime Yani orada olacak Söz konusu kişinin adı. 426 00:17:22,069 --> 00:17:25,079 Ve şimdi ben bir bağlantı var Burada bir sonraki düğüme 427 00:17:25,079 --> 00:17:28,170 Bu temsil etmesi için, düğümlerin her biri 428 00:17:28,170 --> 00:17:30,950 zincir içinde, potansiyel olarak, Bağlantılı bir liste. 429 00:17:30,950 --> 00:17:34,090 >> Ve şimdi nasıl beyan yapmak karma tablo kendisi? 430 00:17:34,090 --> 00:17:36,660 Nasıl bütün bu yapıyı beyan edersiniz? 431 00:17:36,660 --> 00:17:40,960 Peki, gerçekten, çok ben bir gösterici eskisi gibi Bir listenin sadece ilk elemanına 432 00:17:40,960 --> 00:17:44,510 önce, benzer sadece söyleyebiliriz Ben sadece işaretçiler bir demet gerekir 433 00:17:44,510 --> 00:17:46,270 Bütün bu hash tablosu uygulamak için. 434 00:17:46,270 --> 00:17:49,484 Ben bir dizi var gidiyorum karma tablo için çağrıda tablo. 435 00:17:49,484 --> 00:17:50,900 Bu boyut kapasitesinin olacak. 436 00:17:50,900 --> 00:17:52,525 Yani o sığabilecek kaç unsurlar var. 437 00:17:52,525 --> 00:17:56,180 Ve bu unsurların her biri Dizi düğüm yıldızı olacak. 438 00:17:56,180 --> 00:17:56,810 Neden? 439 00:17:56,810 --> 00:18:00,160 Peki, bu resim başına, ben ne olduğumu karma tablo olarak uygulanması 440 00:18:00,160 --> 00:18:04,330 etkin bir de başlangıcı sadece bir Biz dikey boğuldum bu dizi, 441 00:18:04,330 --> 00:18:06,820 olan kareler her Bir işaretçi temsil eder. 442 00:18:06,820 --> 00:18:09,170 Olanlar bu eğik çizgi var ki Bunların içinden sadece null. 443 00:18:09,170 --> 00:18:11,410 Ve olanlar bu var sağa gidiyor oklar 444 00:18:11,410 --> 00:18:16,140 Gerçek düğümler gerçek işaretçiler, Bir bağlantılı liste başlangıcını ergo. 445 00:18:16,140 --> 00:18:19,050 >> Yani burada, daha sonra, nasıl olabilir olduğunu bir karma tablo uygulamak 446 00:18:19,050 --> 00:18:21,580 Ayrı zincirleme uygular. 447 00:18:21,580 --> 00:18:22,840 Şimdi daha iyi yapabiliriz? 448 00:18:22,840 --> 00:18:25,632 Pekala ben son kez söz ki Biz sürekli zaman elde edebiliriz. 449 00:18:25,632 --> 00:18:27,381 Ve ben tür size verdi Burada zaman sabiti, 450 00:18:27,381 --> 00:18:29,850 ama sonra gerçekten dedi zaman sabiti hala çünkü 451 00:18:29,850 --> 00:18:31,890 toplam bağımlı elemanların sayısı 452 00:18:31,890 --> 00:18:34,500 Eğer içine giren konum veri yapısı. 453 00:18:34,500 --> 00:18:35,980 Ama biz bu yaptığımız varsayalım. 454 00:18:35,980 --> 00:18:39,550 Beni buraya ekrana geri dönelim. 455 00:18:39,550 --> 00:18:44,520 Beni de burada bu kadar proje net Let Ekran ve ben bunu herhalde. 456 00:18:44,520 --> 00:18:49,300 Adını eklemek istedim varsayalım Daven benim veri yapısı içine. 457 00:18:49,300 --> 00:18:52,100 >> Yani bir dize eklemek istiyorum Veri yapısı içine DAV. 458 00:18:52,100 --> 00:18:54,370 Ne bir kullanmak istemiyorsanız tablo hash, ama ben kullanmak 459 00:18:54,370 --> 00:18:56,980 Dahası şey ağaç gibi Bir aile ağacı gibi 460 00:18:56,980 --> 00:18:59,670 Eğer bazı kök var Üst ve sonra düğümleri ve yaprakları 461 00:18:59,670 --> 00:19:01,440 Bu aşağı ve dışa doğru gidin. 462 00:19:01,440 --> 00:19:04,450 , O ben varsayalım Daven en eklemek istiyorum 463 00:19:04,450 --> 00:19:06,430 Şu anda boş bir liste ne içine. 464 00:19:06,430 --> 00:19:09,780 Ben aşağıdaki yapmak için gidiyorum: Ben Bu ailede bir düğüm oluşturmak için gidiyor 465 00:19:09,780 --> 00:19:15,170 ağaç gibi veri yapısı görünüyor Biraz böyle, her biri 466 00:19:15,170 --> 00:19:19,640 dikdörtgenler, diyelim etti içinde hemen 26 elemanları. 467 00:19:19,640 --> 00:19:21,650 Ve hücrelerin her Bu dizide gidiyor 468 00:19:21,650 --> 00:19:23,470 Bir alfabenin mektubu temsil etmek. 469 00:19:23,470 --> 00:19:28,190 >> Özellikle, tedavi için gidiyorum bu, A, daha sonra B, sonra C, sonra D 470 00:19:28,190 --> 00:19:29,310 Burada bu. 471 00:19:29,310 --> 00:19:32,940 Yani bu etkili oluyor yazmak D. temsil 472 00:19:32,940 --> 00:19:36,040 Ama Daven en tüm eklemek için Ben biraz daha yapmamız gerekiyor isim. 473 00:19:36,040 --> 00:19:37,840 Bu yüzden ilk tabiri caizse, karma gidiyorum. 474 00:19:37,840 --> 00:19:41,049 Ben ilk harfi bakmak için gidiyorum içinde Daven en Açıkçası D olan, 475 00:19:41,049 --> 00:19:42,840 ve ben ayırmaya gidiyorum görünen bir düğüm 476 00:19:42,840 --> 00:19:45,570 gibi büyük bir büyük bir dikdörtgen bu-- Tüm alfabeyi sığacak kadar. 477 00:19:45,570 --> 00:19:47,140 >> Şimdi Ge yapılır. 478 00:19:47,140 --> 00:19:49,720 Şimdi A. D-A-V-E-N hedeftir. 479 00:19:49,720 --> 00:19:51,220 Yani şimdi ben yapacağım bu ne. 480 00:19:51,220 --> 00:19:54,027 En kısa sürede D bildirimi başladı Orada hiçbir işaretçi yok. 481 00:19:54,027 --> 00:19:56,860 Bu, şu anda çöp değerleri var ya da ben null başlatılamıyor olabilir. 482 00:19:56,860 --> 00:19:59,630 Ama ben ile devam edelim Bir ağaç bina bu fikir. 483 00:19:59,630 --> 00:20:04,260 Bana bu başka birini tahsis edelim İçinde 26 elemana sahiptir düğümleri. 484 00:20:04,260 --> 00:20:05,150 >> Ve biliyor musun? 485 00:20:05,150 --> 00:20:09,130 Bu bellekte sadece bir düğüm ise bu Bir yapı kullanılarak malloc'dan ile oluşturulan 486 00:20:09,130 --> 00:20:11,240 yakında göreceğimiz gibi, Ben bu-- yapacağım 487 00:20:11,240 --> 00:20:14,450 Ben bir ok çizmek için gidiyorum Aşağı D temsil şey 488 00:20:14,450 --> 00:20:15,860 Bu yeni düğümün. 489 00:20:15,860 --> 00:20:19,240 Ve ilk sonraki şimdi Daven adına mektup, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- ben önde gitmek için gidiyorum ve bu gibi başka bir düğüm çizmek, 491 00:20:24,150 --> 00:20:30,150 bu sayede, burada V elemanı, Biz instance-- hoppala için çekersiniz. 492 00:20:30,150 --> 00:20:31,020 Biz orada çizmek olmaz. 493 00:20:31,020 --> 00:20:31,936 Burada gidecek. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Sonra biz gidiyoruz Bu V. olarak düşünün 496 00:20:35,712 --> 00:20:44,920 Ve sonra buraya biz indeksi gidiyoruz aşağı V biz E. düşünün ne yapacaksınız içine 497 00:20:44,920 --> 00:20:50,100 Ve sonra buradan biz gidiyoruz Burada bu düğümlerin birine sahip gidin. 498 00:20:50,100 --> 00:20:52,930 Ve şimdi cevaplamak için bir sorum var. 499 00:20:52,930 --> 00:20:57,840 Bunu belirtmek bir şekilde gerek Biz dize Daven sonunda konum. 500 00:20:57,840 --> 00:20:59,490 Yani sadece boş bırakabilir. 501 00:20:59,490 --> 00:21:02,670 >> Ama biz Daven en ne varsa Ayrıca tam adı, hangi 502 00:21:02,670 --> 00:21:04,280 biz Davenport söylediğim gibi, değil mi? 503 00:21:04,280 --> 00:21:06,970 Böylece DAV ne ise Aslında bir alt, 504 00:21:06,970 --> 00:21:08,960 çok daha uzun bir dize bir önek? 505 00:21:08,960 --> 00:21:11,450 Biz sadece kalıcı olamaz hiçbir şey gidiyor demek 506 00:21:11,450 --> 00:21:14,410 Çünkü biz olabilir, oraya gitmek için Davenport gibi bir kelime eklemek asla 507 00:21:14,410 --> 00:21:15,840 Bu veri yapısı içine 508 00:21:15,840 --> 00:21:19,560 >> Peki neler yapabileceğini yerine ise Bu unsurların her biri tedavi 509 00:21:19,560 --> 00:21:22,170 belki iki sahip bunların içinde elemanları. 510 00:21:22,170 --> 00:21:24,810 Bir, gerçekten, bir gösterici ben yapıyorum. 511 00:21:24,810 --> 00:21:27,100 Bu kutuların her Yani Sadece bir hücre. 512 00:21:27,100 --> 00:21:29,855 Ama ne olursa üst Şehre alt kişinin 513 00:21:29,855 --> 00:21:32,230 Çünkü, boş olacak henüz hiçbir Davenport yoktur. 514 00:21:32,230 --> 00:21:34,197 Ne olursa üst bir Bazı özel değer? 515 00:21:34,197 --> 00:21:36,530 Ve biraz olacak Bu boyutta çizmek zor. 516 00:21:36,530 --> 00:21:38,130 Ama bu sadece bir onay işareti olduğunu varsayalım. 517 00:21:38,130 --> 00:21:38,920 Kontrol edin. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N dizedir Bu veri yapısı içinde. 519 00:21:44,230 --> 00:21:48,350 >> Bu arada, ben olsaydı daha fazla alan Burada, ben, P-O-R-T yapabileceği 520 00:21:48,350 --> 00:21:52,650 ve ben düğüm onay koyabilirsiniz Bu çok sonunda harfi T sahiptir. 521 00:21:52,650 --> 00:21:55,460 Yani bu bir kitlesel bir Karmaşık görünümlü veri yapısı. 522 00:21:55,460 --> 00:21:57,210 Ve benim el yazısı kesinlikle yardımcı olmuyor. 523 00:21:57,210 --> 00:22:00,043 Ama bir şey eklemek istedim Başka, biz ne yapacağını düşünün. 524 00:22:00,043 --> 00:22:03,370 Biz David koymak istedim, biz aynı mantığı, D-A-V takip ediyorum 525 00:22:03,370 --> 00:22:08,802 ama şimdi bir sonraki işaret ediyorum eleman değil E, ancak I'den D. 526 00:22:08,802 --> 00:22:10,760 Yani orada oluyor Bu ağacın daha fazla düğüm. 527 00:22:10,760 --> 00:22:12,325 Biz daha fazla arama malloc zorunda gidiyoruz. 528 00:22:12,325 --> 00:22:14,700 Ama ben yapmak istemiyorum Bu resmin tam bir karışıklık. 529 00:22:14,700 --> 00:22:17,710 Yani bunun yerine bir bakalım Bu-ön formüle oldu 530 00:22:17,710 --> 00:22:21,810 nokta değil bu böyle, nokta, noktalar, ama sadece kısaltılmış diziler. 531 00:22:21,810 --> 00:22:23,950 Ama düğümlerin her Burada bu ağaç up 532 00:22:23,950 --> 00:22:26,700 Aynı şey-- temsil Bir dizi boyutu 26 Ray. 533 00:22:26,700 --> 00:22:28,860 >> Ya biz olmak istiyorsanız Gerçekten doğru şimdi, ne 534 00:22:28,860 --> 00:22:30,790 Birinin adı olarak eğer bir kesme işareti, diyelim 535 00:22:30,790 --> 00:22:35,560 Her düğüm aslında olduğunu varsayalım İçinde 27 endeksleri, sadece 26 gibi. 536 00:22:35,560 --> 00:22:42,020 Yani bu artık bir veri olacak yapı trie-- T R-l-E olarak adlandırılan. 537 00:22:42,020 --> 00:22:46,120 Sözde bir tray, Bir ağaç için tarihsel bir akıllı isim 538 00:22:46,120 --> 00:22:49,040 Bunun için optimize alımı, hangi elbette, 539 00:22:49,040 --> 00:22:50,870 bu tray yüzden I-E ile yazıldığından. 540 00:22:50,870 --> 00:22:52,710 Ama bu trayın tarihidir. 541 00:22:52,710 --> 00:22:55,860 >> Yani tray bu ağaç gibi veri Bir aile ağacı gibi yapı 542 00:22:55,860 --> 00:22:57,510 sonuçta böyle davranır. 543 00:22:57,510 --> 00:23:00,890 Ve burada bir sadece başka bir örnek diğer insanların isimleri sürü. 544 00:23:00,890 --> 00:23:03,540 Ama şimdi soru eldeki ne var 545 00:23:03,540 --> 00:23:08,070 Biz belki bir daha getirerek kazandı karmaşık veri yapısı, ve bir, 546 00:23:08,070 --> 00:23:09,870 açıkçası, bu çok fazla bellek kullanır. 547 00:23:09,870 --> 00:23:11,703 >> Halde olduğundan, Şu anda, ben sadece kulüpler 548 00:23:11,703 --> 00:23:15,050 D'nin işaretçi kullanarak ve A V ve Es ve Ns, ve 549 00:23:15,050 --> 00:23:16,700 Ben bellek çok bir halt israf ediyorum. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Ama bir kaynak harcamak nerede, Ben geri başka kazanmak yapmak eğilimindedir. 552 00:23:22,660 --> 00:23:26,020 Ben daha fazla yer harcıyorum Yani eğer Muhtemelen umut ne? 553 00:23:26,020 --> 00:23:27,407 Ben ne az harcama ediyorum? 554 00:23:27,407 --> 00:23:28,240 HEDEF KİTLE: Az zaman. 555 00:23:28,240 --> 00:23:28,990 DAVID MALAN: Zaman. 556 00:23:28,990 --> 00:23:30,320 Şimdi neden olabilir? 557 00:23:30,320 --> 00:23:33,880 Peki, ekleme nedir Zaman, hemen büyük O açısından, 558 00:23:33,880 --> 00:23:37,660 Daven gibi bir isim veya Davenport veya David? 559 00:23:37,660 --> 00:23:39,340 Peki, Daven beş adım oldu. 560 00:23:39,340 --> 00:23:42,350 Davenport dokuz adımlar olacaktır, bu yüzden bir kaç adım daha olacaktır. 561 00:23:42,350 --> 00:23:44,250 David de beş adım olacaktır. 562 00:23:44,250 --> 00:23:47,230 Yani bu somut sayılar, ama kesinlikle var 563 00:23:47,230 --> 00:23:49,550 bir üst sınır Birinin adının uzunluğu. 564 00:23:49,550 --> 00:23:52,240 Ve gerçekten de, sorun Beş şartname setleri, 565 00:23:52,240 --> 00:23:54,050 Önerdiğimiz gidiyoruz bir şey olduğunu 566 00:23:54,050 --> 00:23:55,470 Bu 40-bazı küsur karakterler var. 567 00:23:55,470 --> 00:23:58,180 >> Gerçekçi, kimse sahip sonsuz uzun isim, 568 00:23:58,180 --> 00:24:01,542 demek olan bir uzunluğu isim veya bir dize uzunluğu biz olabilir 569 00:24:01,542 --> 00:24:03,750 Devlet belirli var yapı tartışmasız ne olduğunu? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Bu sabit değil. 572 00:24:06,250 --> 00:24:06,430 Doğru? 573 00:24:06,430 --> 00:24:09,310 Bu gibi büyük bir sabit olabilir 40-bir şey, ama sabittir. 574 00:24:09,310 --> 00:24:13,752 Ve kaç hiçbir bağımlılık vardır Diğer isimler bu veri yapısı vardır. 575 00:24:13,752 --> 00:24:15,460 Diğer bir deyişle, eğer ben Şimdi eklemek istedim 576 00:24:15,460 --> 00:24:20,540 Colton veya Gabriel ya da Rob ya Zamyla veya Alison ve Belinda ya da başka bir isim 577 00:24:20,540 --> 00:24:23,940 Bu veri içine personelinden yapısı, çalışma süresi olan 578 00:24:23,940 --> 00:24:26,750 diğer isimleri ekleyerek Etkilenen tüm en olacak 579 00:24:26,750 --> 00:24:30,220 kaç diğer elemanları tarafından olan Zaten veri yapısı içinde? 580 00:24:30,220 --> 00:24:31,040 Öyle değil. 581 00:24:31,040 --> 00:24:31,540 Doğru? 582 00:24:31,540 --> 00:24:36,150 Biz etkili kullanarak Çünkü Bu çok katmanlı karma tablo. 583 00:24:36,150 --> 00:24:38,280 Ve çalışma süresi Bu işlemlerin herhangi birini 584 00:24:38,280 --> 00:24:41,510 sayısına bağımlı değildir veri yapısı içinde olan unsurlar 585 00:24:41,510 --> 00:24:43,090 veya sonunda gidiyor veri yapısı içinde olması, 586 00:24:43,090 --> 00:24:44,714 ama ne özellikle uzunluğuna? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Dize olmak , takılı yapmak yok ki 589 00:24:49,200 --> 00:24:52,580 Bu asimptotik sabit birinin seferinde-- büyük Ç. 590 00:24:52,580 --> 00:24:54,720 Ve açıkçası, sadece Gerçek dünya, bu 591 00:24:54,720 --> 00:24:58,380 Daven adı alır takmadan demektir Beş adımda, ya da Davenport dokuz gibi 592 00:24:58,380 --> 00:25:00,100 adımlar, ya da David beş adım. 593 00:25:00,100 --> 00:25:03,071 Bu oldukça lanetlemek küçük çalışma süreleri var. 594 00:25:03,071 --> 00:25:05,320 Ve, gerçekten de, bu çok var iyi bir şey, özellikle 595 00:25:05,320 --> 00:25:08,126 toplamda bağımlı değil Orada elemanların sayısı. 596 00:25:08,126 --> 00:25:10,500 Bu yüzden bu uygulamaya nasıl kod yapısının tür? 597 00:25:10,500 --> 00:25:12,900 Biraz daha var Karmaşık, ama yine de var 598 00:25:12,900 --> 00:25:15,050 sadece bir uygulama temel yapı taşları. 599 00:25:15,050 --> 00:25:17,830 Ben yeniden tanımlamak için gidiyorum Bize düğüm şöyle: 600 00:25:17,830 --> 00:25:21,100 bool word-- denir ve bu bir şey denilebilir. 601 00:25:21,100 --> 00:25:23,970 Ama bool temsil ne bir onay işareti olarak çekti. 602 00:25:23,970 --> 00:25:24,490 Evet. 603 00:25:24,490 --> 00:25:26,720 Bu dize sonu Bu veri yapısı içinde. 604 00:25:26,720 --> 00:25:30,702 >> Ve, elbette, düğüm yıldızı çocuklara orada atıfta olduğunu. 605 00:25:30,702 --> 00:25:32,410 Ve, gerçekten de, tıpkı Bir aile ağacı, sen 606 00:25:32,410 --> 00:25:34,370 düğümleri düşünün Bu asılı olan 607 00:25:34,370 --> 00:25:36,920 Bazı ebeveyn alt eleman çocukları olmak. 608 00:25:36,920 --> 00:25:40,510 Ve böylece çocuklar gidiyor 27 dizisi, 27 biri 609 00:25:40,510 --> 00:25:41,680 Sadece kesme işareti için olmak. 610 00:25:41,680 --> 00:25:43,390 Biz sıralamak için gidiyoruz özel bir durum bunun. 611 00:25:43,390 --> 00:25:45,400 Yani belli olabilir kesme ile isimleri. 612 00:25:45,400 --> 00:25:47,399 Belki de tire gerektiği oraya, ama sen olacak 613 00:25:47,399 --> 00:25:50,330 p seti 5 sadece bakım görmek harfler ve kesme konusunda. 614 00:25:50,330 --> 00:25:52,990 >> Ve sonra nasıl temsil ediyorlar veri yapısı kendisi? 615 00:25:52,990 --> 00:25:56,454 Nasıl kök temsil ediyor Bu trayın, tabiri caizse? 616 00:25:56,454 --> 00:25:59,620 Peki, sadece, bir bağlantılı liste ile mi İlk elemana bir işaretçi gerekir. 617 00:25:59,620 --> 00:26:04,270 Bir tray ile sadece bir ihtiyaç Bu trayın köküne işaretçisi. 618 00:26:04,270 --> 00:26:07,290 Ve oradan karma yapabilirsiniz yolunuzu aşağı derin ve daha derin 619 00:26:07,290 --> 00:26:10,460 yapısında her düğümün. 620 00:26:10,460 --> 00:26:13,440 Yani sadece bu can ile biz o yapı temsil eder. 621 00:26:13,440 --> 00:26:15,877 >> Şimdi, Ah soru Meanwhile--. 622 00:26:15,877 --> 00:26:17,220 >> İZLEYİCİ: bool kelime nedir? 623 00:26:17,220 --> 00:26:20,490 >> DAVID MALAN: Bool kelime Sadece bu C enkarnasyon 624 00:26:20,490 --> 00:26:22,920 Ben tarif ne Burada, bu kutuda 625 00:26:22,920 --> 00:26:26,000 Ben her yarma başladı İki parçaya dizinin elemanları. 626 00:26:26,000 --> 00:26:27,600 Bir sonraki düğüme bir göstericidir. 627 00:26:27,600 --> 00:26:30,280 Diğer olmak zorunda Bir onay kutusu gibi bir şey 628 00:26:30,280 --> 00:26:33,770 Bir var, evet demek için burada biter DAV kelime, 629 00:26:33,770 --> 00:26:35,610 Biz istemiyoruz, çünkü Şu, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Dave olacak olsa meşru bir kelime, o traya içinde değil 631 00:26:39,320 --> 00:26:39,830 Henüz. 632 00:26:39,830 --> 00:26:40,950 Ve D bir kelime değildir. 633 00:26:40,950 --> 00:26:42,770 Ve D-A bir kelime ya da bir isim değil. 634 00:26:42,770 --> 00:26:45,020 Onay işareti Yani sadece size bir kez gösterir 635 00:26:45,020 --> 00:26:48,190 Bu düğüm vurmak Karakter önceki yol 636 00:26:48,190 --> 00:26:50,700 Eklediğiniz aslında bir dize. 637 00:26:50,700 --> 00:26:53,660 Böylece tüm bool var Bizim için orada yapıyor. 638 00:26:53,660 --> 00:26:55,500 >> Denemeden üzerinde herhangi bir başka soru? 639 00:26:55,500 --> 00:26:56,215 Evet. 640 00:26:56,215 --> 00:26:58,035 >> İZLEYİCİ: örtüşme nedir? 641 00:26:58,035 --> 00:26:59,945 Ne bir Dave ve Daven varsa? 642 00:26:59,945 --> 00:27:00,820 DAVID MALAN: Mükemmel. 643 00:27:00,820 --> 00:27:02,580 Ne bir Dave ve Daven varsa? 644 00:27:02,580 --> 00:27:06,240 Biz eklemek Yani, bir takma ad söylüyorlar alakaları Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Bu aslında süper basit. 647 00:27:08,700 --> 00:27:10,325 Yani biz sadece dört adımlar atmaya gidiyoruz. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. Ve ben ne var Ben dördüncü düğümü vurdu kez yapmak? 650 00:27:15,847 --> 00:27:16,680 Sadece kontrol edecek. 651 00:27:16,680 --> 00:27:18,000 Biz zaten gitmek için iyi bir konum. 652 00:27:18,000 --> 00:27:18,840 Bitti. 653 00:27:18,840 --> 00:27:19,750 Dört adım. 654 00:27:19,750 --> 00:27:21,590 Asimptotik zaman sabiti. 655 00:27:21,590 --> 00:27:26,300 Ve şimdi biz hem Dave belitmişsin ve Daven yapısında dizeleri vardır. 656 00:27:26,300 --> 00:27:27,710 Yani bir sorun değil. 657 00:27:27,710 --> 00:27:30,200 Ve nasıl varlığını fark Daven ve bunu yapmadı 658 00:27:30,200 --> 00:27:34,750 daha fazla zaman ya da daha az zaman alır Zaman Dave ve tersi. 659 00:27:34,750 --> 00:27:36,000 >> Peki şimdi başka ne yapabiliriz? 660 00:27:36,000 --> 00:27:40,680 Biz önce bu metafor kullandım tepsiler şey temsil. 661 00:27:40,680 --> 00:27:43,380 Ama bu çıkıyor bir tepsilerin yığını aslında 662 00:27:43,380 --> 00:27:47,187 Başka bir soyut veri demonstratif daha yüksek bir seviyeye veri yapısı type-- 663 00:27:47,187 --> 00:27:49,770 sonunda gün sadece olduğunu Bir dizi ya da bir bağlantılı liste gibi 664 00:27:49,770 --> 00:27:50,970 daha sıradan falan. 665 00:27:50,970 --> 00:27:53,270 Ama daha ilginç kavramsal kavramı. 666 00:27:53,270 --> 00:27:56,440 Bu gibi bir yığın, Mather burada tepsileri, 667 00:27:56,440 --> 00:27:58,750 genel olarak adlandırılır Sadece bir yığın ki-. 668 00:27:58,750 --> 00:28:02,540 >> Ve veri yapısı bu tip İki operations-- var 669 00:28:02,540 --> 00:28:05,880 Eğer bir adlandırılan itme için var yığına bir şey ekleyerek, 670 00:28:05,880 --> 00:28:08,320 Başka bir tepsi koyarak gibi yığının üstüne geri. 671 00:28:08,320 --> 00:28:11,350 Sizi anlamına gelir Ve sonra, pop üstteki tepsi off almak. 672 00:28:11,350 --> 00:28:16,210 Ama yığını olduğunu hakkında önemli ne Bu meraklı özelliği var. 673 00:28:16,210 --> 00:28:19,560 Yemekhane personeli gibidir Bir sonraki yemek için tepsileri yeniden düzenleyerek, 674 00:28:19,560 --> 00:28:21,380 ne olacak Öğrencilere hakkında doğru 675 00:28:21,380 --> 00:28:22,856 Bu veri yapısı ile etkileşim? 676 00:28:22,856 --> 00:28:24,480 HEDEF KİTLE: Onlar bir kapalı pop gidiyoruz. 677 00:28:24,480 --> 00:28:26,550 DAVID MALAN: Onlar için gidiyoruz bir kapalı, umarım üst pop. 678 00:28:26,550 --> 00:28:28,910 Aksi takdirde sadece tür aptal alt tüm yol gitmek. 679 00:28:28,910 --> 00:28:29,070 Doğru? 680 00:28:29,070 --> 00:28:31,620 veri yapısı gerçekten izin vermez En azından alt tepsiyi kapmak için 681 00:28:31,620 --> 00:28:32,520 Kolayca. 682 00:28:32,520 --> 00:28:35,040 Yani bu meraklı var Bir yığın özellik 683 00:28:35,040 --> 00:28:39,730 son öğe olduğunu İlki üzerinden olacak. 684 00:28:39,730 --> 00:28:43,400 Ve bilgisayar bilim adamları çağrı Bu ilk dışarı son LIFO--. 685 00:28:43,400 --> 00:28:45,540 Ve aslında var ilginç uygulamalar. 686 00:28:45,540 --> 00:28:50,090 Mutlaka bazı kadar belirgin değil diğerleri, ama bu, gerçekten yararlı olabilir 687 00:28:50,090 --> 00:28:54,040 ve bu, gerçekten, uygulanabilir farklı şekillerde bir çift. 688 00:28:54,040 --> 00:28:58,550 >> Yani biri ve aslında, let bana bu dalmak değil. 689 00:28:58,550 --> 00:28:59,860 Onun yerine bu yapalım. 690 00:28:59,860 --> 00:29:03,700 Neredeyse olduğunu bir bakalım Aynı fikir, ama biraz daha adil olduğunu. 691 00:29:03,700 --> 00:29:04,200 Doğru? 692 00:29:04,200 --> 00:29:07,560 Bu fan erkek biri iseniz veya Gerçekten Apple ürünlerini seven kızlar 693 00:29:07,560 --> 00:29:10,130 ve 03:00 uyandım Bazı mağazada hizaya 694 00:29:10,130 --> 00:29:14,150 en son iPhone almak için, Böyle sıraya olabilir. 695 00:29:14,150 --> 00:29:15,800 >> Şimdi sıra çok kasıtlı olarak adlandırılır. 696 00:29:15,800 --> 00:29:18,190 Var çünkü bir çizgi var Bunun için bazı adalet. 697 00:29:18,190 --> 00:29:18,690 Doğru? 698 00:29:18,690 --> 00:29:21,690 Eğer ettik eğer bu tür emdi olur Apple Store'da ilk var 699 00:29:21,690 --> 00:29:25,700 ama etkili alttaki vardır Tepsi sonra Apple çalışanları için 700 00:29:25,700 --> 00:29:28,189 son kişi kim pop Aslında çizgi var. 701 00:29:28,189 --> 00:29:31,230 Yığınlar ve kuyruklar, olsa Yani işlevsel onlar same-- tür konum 702 00:29:31,230 --> 00:29:33,105 Sadece bu koleksiyonu kaynak de bu 703 00:29:33,105 --> 00:29:36,210 Orada var shrink-- büyümeye gidiyor ve buna, bu eşitlik yönü 704 00:29:36,210 --> 00:29:39,634 gerçek dünyada en azından nerede işlemleri egzersiz 705 00:29:39,634 --> 00:29:40,800 temelde farklıdır. 706 00:29:40,800 --> 00:29:43,360 Bir kuyruk bir stack-- rather-- olduğu söylenir 707 00:29:43,360 --> 00:29:45,320 İki operasyon: n kuyruk d kuyruğu. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Yoksa onları arayabilirsiniz şeyler herhangi bir sayı. 710 00:29:48,090 --> 00:29:50,770 Ama sadece yakalamak istiyorum bir ekleme olduğu düşüncesi 711 00:29:50,770 --> 00:29:53,230 ve bir sonuçta çıkartmaktır. 712 00:29:53,230 --> 00:29:58,840 >> Şimdi kaputun altında, hem yığın ve bir kuyruk nasıl uygulanabilir? 713 00:29:58,840 --> 00:30:01,390 Biz koduna gitmeyecek çünkü daha yüksek düzeyde 714 00:30:01,390 --> 00:30:03,387 Fikir çeşit daha açıktır. 715 00:30:03,387 --> 00:30:04,470 Yani, insanlar ne yapmalıyım? 716 00:30:04,470 --> 00:30:07,030 Ben Apple ilk kişiyim ise Mağaza ve bu ön kapı, 717 00:30:07,030 --> 00:30:08,130 Eğer ben burada durmak gidiyorum, biliyorum. 718 00:30:08,130 --> 00:30:09,750 Ve bir sonraki kişinin Burada durmak olacak. 719 00:30:09,750 --> 00:30:11,500 Ve bir sonraki kişinin Burada durmak olacak. 720 00:30:11,500 --> 00:30:13,792 Peki ne veri yapısı kendisi kuyruğa ödünç? 721 00:30:13,792 --> 00:30:14,542 >> İZLEYİCİ: Bir kuyruk. 722 00:30:14,542 --> 00:30:15,667 DAVID MALAN: Peki, bir kuyruk. 723 00:30:15,667 --> 00:30:16,390 Tabii. 724 00:30:16,390 --> 00:30:16,920 Başka ne? 725 00:30:16,920 --> 00:30:17,600 >> İZLEYİCİ: Bir bağlantılı liste. 726 00:30:17,600 --> 00:30:18,990 >> David MALAN: Bağlantılı Eğer uygulamak listesi. 727 00:30:18,990 --> 00:30:22,500 Ve bir bağlantılı liste daha sonra da güzel aksine uzun keyfi büyüyebilir 728 00:30:22,500 --> 00:30:24,880 Bazı sabit sayıda olması için mağaza insanların. 729 00:30:24,880 --> 00:30:27,030 Ama belki bir sabit numara yerlerde meşrudur. 730 00:30:27,030 --> 00:30:30,350 Onlar sadece 20 gibi varsa Çünkü belki ilk gününde iPhone'lar 731 00:30:30,350 --> 00:30:33,930 onlar sadece boyutu bir dizi gerekir 20 O kuyruğunu temsil hangi 732 00:30:33,930 --> 00:30:37,070 Biz konuşurken başladığınızda ancak şimdi söylemek olduğunu Bu üst düzey sorunlar hakkında, 733 00:30:37,070 --> 00:30:38,890 bunu uygulayabilirsiniz yollardan herhangi bir sayıda. 734 00:30:38,890 --> 00:30:42,030 Ve muhtemelen sadece gidiş var uzay ve zaman içinde bir ticaret kapalı 735 00:30:42,030 --> 00:30:43,950 ya da sadece kendi kod karmaşıklığı. 736 00:30:43,950 --> 00:30:45,380 >> Bir yığın ne? 737 00:30:45,380 --> 00:30:48,190 Peki, bir yığın, biz de gördük Sadece bu tepsiler olabilir. 738 00:30:48,190 --> 00:30:50,007 Ve bu bir dizi uygulamaya başladı. 739 00:30:50,007 --> 00:30:53,090 Fakat bazı noktada, bir dizi kullanırsanız ne tepsilere ne olacak 740 00:30:53,090 --> 00:30:54,173 aşağı koymak için çalışıyoruz? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Tamam. 743 00:30:55,670 --> 00:30:57,490 Sadece gidiyoruz çok yüksek gitmek mümkün. 744 00:30:57,490 --> 00:31:00,156 Ve onlar konum Mather düşünüyorum Aslında bu açılış gömme. 745 00:31:00,156 --> 00:31:01,950 Yani aslında, neredeyse var Mather kullanıyor gibi 746 00:31:01,950 --> 00:31:03,783 sabit boyutlu bir dizi Sadece can çünkü 747 00:31:03,783 --> 00:31:08,302 o açılışta çok tepsileri uygun insanların dizlerinin altına kadar duvar. 748 00:31:08,302 --> 00:31:10,010 Ve böylece olabilir Bir dizi olduğu söyleniyor, 749 00:31:10,010 --> 00:31:14,300 ama biz kesinlikle uygulamak daha genel bir bağlantılı liste ile. 750 00:31:14,300 --> 00:31:16,390 >> Peki, ne başka bir veri yapısı hakkında? 751 00:31:16,390 --> 00:31:18,760 Beni burada görsel diğeri yukarı çekin bakalım. 752 00:31:18,760 --> 00:31:24,710 Nasıl burada bu biri hakkında böyle bir şey? 753 00:31:24,710 --> 00:31:28,920 Neden değil olması yararlı olabilir bir tray, gibi bir şey fantezi hangi 754 00:31:28,920 --> 00:31:32,370 Biz bu çok geniş düğümler vardı gördüm bunların her biri, bir dizi içinde mi? 755 00:31:32,370 --> 00:31:35,740 Ama biz bir şey daha ne yaparsanız sadece, eski bir okul aile ağacı gibi, 756 00:31:35,740 --> 00:31:38,110 kimin burada düğümler her Sadece bir numara depolamak. 757 00:31:38,110 --> 00:31:42,180 Bunun yerine bir ad veya bir torunu Sadece böyle bir numara depolamak. 758 00:31:42,180 --> 00:31:45,250 >> Peki, jargon biz kullanmak veri yapıları hem çalışır olduğunu 759 00:31:45,250 --> 00:31:49,510 ve ağaçlar, bir tray, yine, burada Sadece kimin düğümleri diziler bir, 760 00:31:49,510 --> 00:31:51,680 hala ne olabilir İlkokuldan kullanmak 761 00:31:51,680 --> 00:31:53,860 Bir aile yaptığı zaman tree-- yaprakları ve kök 762 00:31:53,860 --> 00:31:57,250 ağaç ve çocuklarının ebeveyn ve bunların kardeşleri. 763 00:31:57,250 --> 00:32:03,670 Ve biz bir ağaç uygulayabilir, Örneğin, basitçe bu kadar. 764 00:32:03,670 --> 00:32:07,420 Bir ağaç, o takdirde bir düğüm, biri olarak bir numarası vardır bu çevreler, 765 00:32:07,420 --> 00:32:09,947 o olacak değil bir gösterici, ancak iki. 766 00:32:09,947 --> 00:32:11,780 Ve en kısa sürede eklemek gibi İkinci işaretçi, sen 767 00:32:11,780 --> 00:32:13,905 Aslında şimdi sıralama yapabilirsiniz İki boyutlu verilerin 768 00:32:13,905 --> 00:32:14,780 bellekte yapılar. 769 00:32:14,780 --> 00:32:16,660 Iki boyutlu gibi çok Dizi yapabilirsiniz 770 00:32:16,660 --> 00:32:18,904 İki-boyutlu tür var Bağlantılı listeler ama olanlar 771 00:32:18,904 --> 00:32:20,820 bir model takip nerede olursa döngüleri var. 772 00:32:20,820 --> 00:32:24,487 Bu biriyle gerçekten bir ağaç var Burada ve daha sonra büyükbaba yol kadar 773 00:32:24,487 --> 00:32:27,320 Bazı ebeveynler ve çocuklar ve torunları ve torunlarının torunları. 774 00:32:27,320 --> 00:32:28,370 ve benzeri yer alır. 775 00:32:28,370 --> 00:32:32,390 >> Ama çok bu konuda gerçekten temiz ne, Sadece kod biraz sizi kızdırmak için, 776 00:32:32,390 --> 00:32:35,370 dan geri çağırma yineleme süre geri, böylece 777 00:32:35,370 --> 00:32:38,220 Eğer kendisini çağıran bir fonksiyon yazın. 778 00:32:38,220 --> 00:32:41,140 Bu güzel bir fırsat bir şey uygulamak için 779 00:32:41,140 --> 00:32:42,920 yineleme gibi, çünkü bu düşünün. 780 00:32:42,920 --> 00:32:43,860 >> Bu bir ağaçtır. 781 00:32:43,860 --> 00:32:48,040 Ve ben nasıl küçük bir anal oldum Ben sokağa tamsayılar koydu. 782 00:32:48,040 --> 00:32:51,020 Öyle ki özel bir var İkili arama ağacı aşkına--. 783 00:32:51,020 --> 00:32:53,460 Şimdi ikili duydum Seni aramak, ancak can 784 00:32:53,460 --> 00:32:55,180 Bu şeyin adından geriye çalışır? 785 00:32:55,180 --> 00:32:59,280 I nasıl desen nedir Bu ağaca tamsayılar takılı? 786 00:32:59,280 --> 00:33:00,696 Bu keyfi değil. 787 00:33:00,696 --> 00:33:01,570 Bazı desen var. 788 00:33:01,570 --> 00:33:02,090 Evet. 789 00:33:02,090 --> 00:33:03,370 >> İZLEYİCİ: soldaki küçük olanlar. 790 00:33:03,370 --> 00:33:03,690 >> DAVID MALAN: Evet. 791 00:33:03,690 --> 00:33:05,062 Küçük olanlar solda. 792 00:33:05,062 --> 00:33:06,270 Büyük olanlar sağda. 793 00:33:06,270 --> 00:33:12,940 Böyle bir gerçek ifadesi olduğunu bir ebeveyn, sol çocuğun daha büyüktür 794 00:33:12,940 --> 00:33:14,850 sağ çocuğun daha ama daha az. 795 00:33:14,850 --> 00:33:17,750 Ve yalnız o bile olduğunu özyineli sözlü tanım 796 00:33:17,750 --> 00:33:20,500 Bunu uygulayabilirsiniz çünkü Her düğümün aynı mantık 797 00:33:20,500 --> 00:33:23,080 ve sadece dipleri dışarı, bir taban durumda eğer 798 00:33:23,080 --> 00:33:25,740 olacak, ne zaman birini vurdu Yaprakları, bu yüzden, konuşmak 799 00:33:25,740 --> 00:33:28,580 Bir izin daha hiçbir çocuk babasıdır yerde. 800 00:33:28,580 --> 00:33:30,614 >> Şimdi nasıl numarayı 44 bulabilir? 801 00:33:30,614 --> 00:33:32,280 Sen, hm kökünde başlayacak ve söyleyebilirim. 802 00:33:32,280 --> 00:33:35,690 55 Bu yüzden gitmek istiyorsun 44 değil sağa veya sola gitmek Ben istiyorsun? 803 00:33:35,690 --> 00:33:37,190 Peki, açıkçası sol gitmek istiyorum. 804 00:33:37,190 --> 00:33:40,060 Ve böylece sadece telefon gibi İkili arama kitap örneği 805 00:33:40,060 --> 00:33:41,099 daha genel olarak. 806 00:33:41,099 --> 00:33:43,390 Ama biz bunu uygulamak ediyoruz Şimdi biraz daha dinamik 807 00:33:43,390 --> 00:33:45,339 Bir dizi izin verebilir daha. 808 00:33:45,339 --> 00:33:48,130 Ve aslında, bakmak isterseniz kodu, ilk bakışta emin olun. 809 00:33:48,130 --> 00:33:49,671 Bu satırları bir sürü gibi görünüyor. 810 00:33:49,671 --> 00:33:51,220 Ama güzel basit. 811 00:33:51,220 --> 00:33:54,490 Eğer bir işlevi uygulamak istiyorsanız Amacı hayatında denilen arama 812 00:33:54,490 --> 00:33:57,290 Bir değer aramak için gibi, n bir tamsayıdır, 813 00:33:57,290 --> 00:34:01,756 ve bir işaretçi olarak kabul ediyoruz köklerin düğüme bir işaretçi, 814 00:34:01,756 --> 00:34:04,380 yerine, bu ağacın hangi Eğer, her şeyi erişebilirsiniz 815 00:34:04,380 --> 00:34:08,850 nasıl delikanlı fark Eğer mantık uygulayabilirsiniz. 816 00:34:08,850 --> 00:34:10,880 Ağaç null ise, Açıkçası orada değil. 817 00:34:10,880 --> 00:34:11,880 Sadece yanlış dönelim. 818 00:34:11,880 --> 00:34:12,000 Doğru? 819 00:34:12,000 --> 00:34:14,040 Bunu hiçbir el varsa, Orada hiçbir şey yok. 820 00:34:14,040 --> 00:34:17,900 >> Başka n daha az ise Şimdi n ok n- ağaç ok, 821 00:34:17,900 --> 00:34:20,670 Biz süper tanıttı hatırlamak kısaca Geçen gün, 822 00:34:20,670 --> 00:34:25,100 ve bu sadece de başvuru anlamına gelir işaretçi ve n adlandırılan alana bakın. 823 00:34:25,100 --> 00:34:27,690 Yani oraya gitmek ve anlamı n adlandırılan alana bakmak. 824 00:34:27,690 --> 00:34:33,810 Yani n ise, size verilen konum değeri, az ağaçlar tamsayı değerden, 825 00:34:33,810 --> 00:34:35,449 nereye gitmek istiyorsun? 826 00:34:35,449 --> 00:34:36,389 Sola. 827 00:34:36,389 --> 00:34:37,780 >> Yani özyinelemeyi dikkat edin. 828 00:34:37,780 --> 00:34:39,860 Ben gerçek returning-- ediyorum. 829 00:34:39,860 --> 00:34:40,989 Sahte değil. 830 00:34:40,989 --> 00:34:45,670 Ben ne olursa olsun cevap dönen ediyorum kendime bir çağrı dan, geçen 831 00:34:45,670 --> 00:34:50,100 gereksiz yine n, ama şimdi biraz farklı ne? 832 00:34:50,100 --> 00:34:51,989 Nasıl küçük bir sorun yapıyorum? 833 00:34:51,989 --> 00:34:54,920 Ben ikinci olarak geçirerek argüman, ağacın kök değil, 834 00:34:54,920 --> 00:34:59,616 ancak bu durumda, sol alt. 835 00:34:59,616 --> 00:35:00,990 Yani sol çocukta geçiyorum. 836 00:35:00,990 --> 00:35:04,720 >> Bu arada, n daha büyük ise, Şu anda bakıyorum düğüm, 837 00:35:04,720 --> 00:35:06,690 Ben sağ tarafını arayın. 838 00:35:06,690 --> 00:35:10,880 Else, ağaç, boş değilse ve eleman sola değilse 839 00:35:10,880 --> 00:35:13,240 ve sağa değil vaka harika nedir? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Biz aslında düğüm buldum Soru ve bu yüzden doğru döndürür. 842 00:35:18,440 --> 00:35:21,490 >> Yani biz sadece yüzeyi çizik var Şimdi bu veri yapılarının bazı. 843 00:35:21,490 --> 00:35:24,370 Sorun beş set size olacak Yine başka bu keşfetmek, 844 00:35:24,370 --> 00:35:27,250 ve tasarım verilecektir olacak Bu konuda nasıl bir seçim. 845 00:35:27,250 --> 00:35:30,250 Ben sonuçlandırmak istiyorum Ne sadece 30 saniye teaser 846 00:35:30,250 --> 00:35:32,080 ötesinde önümüzdeki hafta ve bekliyor ne. 847 00:35:32,080 --> 00:35:35,390 >> Biz minnetle begin-- olarak, olabilir yavaş yavaş geçiş bence-- 848 00:35:35,390 --> 00:35:38,680 C ve alt dünyasından seviye uygulama detayları, 849 00:35:38,680 --> 00:35:42,090 Bir dünya ki biz alabilir başkası nihayet sahip olduğu verilen 850 00:35:42,090 --> 00:35:44,010 Bu veriler uygulanan Bizim için yapılar, 851 00:35:44,010 --> 00:35:47,570 ve biz anlamak için başlayacağız gerçek dünya uygulama anlamına gelir 852 00:35:47,570 --> 00:35:50,560 Web-tabanlı programlar ve web siteleri daha genel 853 00:35:50,560 --> 00:35:52,910 ve ayrıca çok güvenlik biz sadece ettik etkileri 854 00:35:52,910 --> 00:35:54,850 yuzeysel başladı. 855 00:35:54,850 --> 00:35:57,320 İşte bizi bekliyor ne gün gelecek. 856 00:35:57,320 --> 00:36:00,480 >> [VİDEO OYNATMA] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -O, Bir mesajla geldi Tüm kendi bir protokol ile. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 O zalim bir dünyaya geldim güvenlik duvarları, yönlendiriciler uncaring, 861 00:36:30,894 --> 00:36:33,368 ve tehlikeler ölümden çok daha kötü. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 O hızlı. 864 00:36:36,236 --> 00:36:37,980 O güçlü. 865 00:36:37,980 --> 00:36:42,830 O, TCP / IP, ve o sizin adresinizi var. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Net Warriors." 868 00:36:48,074 --> 00:36:49,660 [SON VİDEO OYNATMA] 869 00:36:49,660 --> 00:36:50,910 DAVID MALAN: önümüzdeki hafta geliyor. 870 00:36:50,910 --> 00:36:51,880 Size daha sonra göreceğiz. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [VİDEO OYNATMA] 873 00:36:56,060 --> 00:36:59,240 -Ve Şimdi, "Derin Düşünceler" DAV Farnham tarafından. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Hep başlar ile dersler "Tüm hakkı." 876 00:37:05,820 --> 00:37:08,750 Neden, "İşte çözüm Bu haftaki sorunu kümesi " 877 00:37:08,750 --> 00:37:12,180 ya da "Biz A hepiniz veriyorsun?" 878 00:37:12,180 --> 00:37:13,380 [Gülüyor] 879 00:37:13,380 --> 00:37:15,530 [SON VİDEO OYNATMA]