[Glazbom] DAVID Malan: Ovo je CS50. A to je i početak i end-- kao literally-- gotovo do kraja u tjednu šest. 

Mislio sam da bih podijeliti Malo zabavna činjenica. Ja sam izvukao ovaj gore iz Podaci prošli semestar je postavljen. Možda se sjećate da smo vas pitati na svakom p set oblik, ako ste gledali na internetu ili ako ste sudjelovali u osobi. I ovdje je podataka. Tako je danas bio vrlo predvidljiv. No, željeli smo provesti malo vremena s vama svejedno. Bi li itko želio nagađati zašto je to graf je tako JAGGY, gore dolje, gore dolje, tako dosljedno? Što svaki od vrhova i korita predstavljaju? 

PUBLIKA: [nečujan] DAVID Malan: Doista. I više zabavno, ne daj Bože, držimo jedno predavanje u petak na početku semestra, to je ono što mi se dogodi. Tako je danas, možemo sudjelovati u malo Više o strukturama podataka. I da vam više čvrste mentalni model za probleme u pet, koji je sada van. Pravopisne pogreške, pri čemu, mi ćemo uručiti vam tekstualnu datoteku oko 100.000 plus engleski riječi i idete imati shvatiti kako se pametno ih učitati u memoriju, u RAM-a, koristeći neke podatke Struktura vašem izboru. 

Sada jedna takva struktura podataka mogla biti, ali vjerojatno ne bi trebalo biti, prilično jednostavna povezani popis, koje smo uveli posljednji put. A popis vezan je imao najmanje prednost u nizu. Što je jedna od prednosti Popis povezani vjerojatno? 

PUBLIKA: umetanje. 

DAVID Malan: umetanje. Što misliš pod tim? 

PUBLIKA: Svugdje zajedno Lista [nečujan]. 

DAVID Malan: Dobro. Dakle, možete umetnuti element gdje god Želite u sredini popisa bez dvoličnost ništa, što smo zaključili, u našem sortiranje rasprava, nije nužno dobra stvar, jer treba vremena da se zapravo premjestiti sve te ljude lijevo ili desno. I tako s popisa povezan, možete Samo izdvojiti s malloc, novi čvor, a zatim ažurirati par pointers-- dva, tri operacije max-- a mi smo u stanju utor nekoga u bilo gdje u popisu. 

Što drugo je prednost o popisu povezane? Da? 

PUBLIKA: [nečujan] DAVID Malan: Savršeno. Savršeno. To je stvarno dinamična. A da niste počinili, unaprijed, do neke fiksne veličine komad memorije, kao što bi da s nizom, naopako od kojih je da možete izdvojiti čvorova samo na Potražnja čime korištenjem samo što više prostora kao što je zapravo potrebno. Za razliku od niza, možda slučajno izdvojiti premalo. I onda to samo ide da se bol u vratu preraspodijeliti novi veći niz, kopirati sve više, osloboditi starog niz, a zatim premjestiti o svom poslovanju. Ili još gore, možda izdvojiti način više memorije nego što je zapravo potrebno, pa ti ćeš imati vrlo slabo naseljenom niz, da se tako izrazim. 

Dakle, popis povezani daje to Prednosti dinamičnosti i fleksibilnosti s umetanja i brisanja. Ali sigurno mora postojati cijena koja se plaća. U stvari, jedna od tema istražiti kviz nula bio par od ustupaka smo do sada vidjeli. Dakle, što je cijena koja se plaća ili negativni popisa povezane? Da. 

PUBLIKA: Nema izravnim pristupom. 

DAVID Malan: Nema izravnim pristupom. Ali koga briga? Izravnim pristupom ne zvuči primamljivo. 

PUBLIKA: [nečujan] DAVID Malan: Točno. Ako želite imati Sigurno algorithm-- i neka mi zapravo predlaže binarno pretraživanje osobito, što jedna smo koristi dosta bit-- Ako nemate slučajni pristup, ne možete učiniti tako jednostavno aritmetiku pronalaženja poput srednjeg elementa i skakanje pravo na njega. Umjesto toga moramo početi na prvi element i linearno traži od lijeva na desno, ako želite pronaći srednji ili bilo koji drugi element. 

PUBLIKA: Vjerojatno traje više memorije. 

DAVID Malan: Uzeti više memorije. Gdje je dodatna trošak dolaze iz memorije? 

PUBLIKA: [nečujan] DAVID Malan: Točno. U ovom slučaju ovdje, imali smo povezani popis za cijelih brojeva, a ipak smo udvostručenje količina memorije trebamo tako i spremanje tih savjeta. Sada manje velika stvar kao što je Vaši konstrukt dobiti veći a ti spremanje nije broj, ali možda student ili neki drugi objekt. No, stvar sigurno ostaje. I tako broj operacija na povezanim listama su pozvani bili su veliki O je n- linearno. Stvari poput umetanja ili traženja ili brisanja u slučaju elementa dogodilo se na samom kraju Popis li to razvrstani ili ne. 

Ponekad možda ćete dobiti sretan i pa niže granica na tim poslovima Također bi moglo biti konstantna vrijeme, ako ste Uvijek gleda na prvom elementu, na primjer. No, u konačnici, obećali smo kako bi se postigla sveti gral struktura podataka, ili neke njihove aproksimacija, putem stalne vremena. Možemo pronaći elemente ili dodati elemente ili ukloniti elemente iz popisa? Vidjet ćemo uskoro. I ispada da je jedan mehanizama smo mi će se početi koristiti danas, godišnja potrebna u p postaviti pet, je zapravo prilično poznato. Na primjer, ako je to hrpa ispitnih knjiga, od kojih je svaki ima student prvi ime i prezime na njemu, i ja ih pokupiti iz Na kraju ispita, i oni su svi prilično koliko u slučajnim redoslijedom, a mi želimo ići oko sortiranja ovi ispiti, tako da, kada ocjenjuju to je samo puno lakše i brže ih predati natrag za studente po abecedi. Što bi vaši instinkti se za hrpu ispita kao što je ovaj? 

Pa, ako ste poput mene, Možda vidim da je ovo m, pa ću se nekako staviti ovo u, ako je to moj stol ili moj kat gdje Ja sam širenja stvari out-- ili moj niz really-- Možda ću staviti sve Ms tamo. Oh. Evo A. Dakle, mogao bih staviti As ovamo. Oh. Evo još jedan A. idem staviti da je ovdje. Evo Z. Ovdje je još M. I tako Mogao bih početi zarađivati ​​hrpe kao što je ovaj. A onda možda bih ići kasnije i vrsta vrlo nitpicky-ly sortiranje pojedinačni piloti. No, poanta je da će izgledati na ulazu da sam ruku i ja bi neki izračunata Odluka se temelji na tom ulazu. Ako se polazi, stavi ga tamo. Ako se počne sa Z, stavi ga na tamo, i sve između. 

Dakle, ovo je tehnika koja je općenito poznat kao hashing-- H-A-S-H-- što obično znači da kao ulaz i koristiti taj ulaz izračunati vrijednost, općenito broj, i to broj je indeks u pohranu Spremnik, kao i niz. Dakle, drugim riječima, možda sam hash funkcija, kao što sam to u mojoj glavi, da ako vidim da netko je Naziv koji počinje sa A, Idem na kartu da je na nulu u mojoj glavi. A ako vidim nekoga sa Z, ja sam ide na kartu da je 25 u mojoj glavi a onda staviti da u Posljednji najviše gomila. 

Sada, ako mislite o tome nije moj mozak ali programske C, što su brojevi mogli se oslanjaju na postići taj isti rezultat? Drugim riječima, ako vas imao ASCII znakova A, kako ste utvrdili ono kanta da ga stavite u? Vi vjerojatno ne želite stavite ga u kantu 65, koji je bi bilo kao tamo bez dobrog razloga. Gdje želiš staviti u smislu njegovog ASCII vrijednosti? Gdje želiš učiniti svoje ASCII Vrijednost smisliti pametniji kantu da ga stavite u? 

PUBLIKA: Minus A. 

DAVID Malan: Da. Dakle, minus ili minus posebno 65, ako je to kapital A. Ili, ako 98 to je mala. I tako da bi nam omogućiti da, vrlo jednostavno i vrlo aritmetički, stavite nešto u kantu kao što je to. Tako ispada da zapravo učiniti to kao dobro, čak i sa kvizovima. 

Dakle, možda ćete se sjetiti što zaokružena svoje Ime demonstrator je na naslovnici. A organizirani su imena TF-a u ovim stupcima po abecednom redu, dobro, vjerovali ili ne, kada je sve 80 plus nas okupili neku večer u razred, posljednji korak u našoj procesa ocjenjivanja je razmotrili su kvizove na veliko prostor na katu [nečujan] i položiti svačije kvizova iz upravo u cilju njihove TF-ih imena na naslovnici, jer je onda je puno lakše za nas tražiti kroz tu pomoću linearne pretraživanja ili neka vrsta pameti za TF pronaći njegov ili kvizovi svojih studenata. 

Dakle, ova ideja raspršivanja da ćete vidjeti je vrlo moćna je zapravo prilično uobičajena i vrlo intuitivno, slično kao možda dijele i vladaj bio u tjednu nula. Ja brzo naprijed na hackathon Prije par godina. To je Zamyla i par drugi studenti osoblje pozdrav kao što su došli u. I imali smo hrpu sklopivi tablicama s oznakama naziva. I mi smo imali oznake s imenom organiziraju s kao i nad postoji i Zs tamo. I tako jedan od TFS vrlo pametno napisao je ovo kao upute za dan. A u 12. tjednu semestra ove sve napravio smisla i svima znao što učiniti. Ali kad god ste čekanju na isti način, ti si provedbi Isti pojam mljeveno meso. Tako ćemo se malo formalizirati. Ovdje je niz. To je nacrtana biti malo širok samo prikazati, vizualno, da bismo mogli staviti žice u nešto poput ovoga. A ovo polje je Jasno je veličine 26 ukupno. A što se zove Tablica proizvoljno. No, to je samo umjetnički izvedba onoga što hash tablicu može biti. 

Tako hash tablicu sada će biti viša razina struktura podataka. Na kraju dana smo o tome da se vidi da vas može provesti hash tablicu, koja je mnogo kao i prijave u skladu na hackathon mnogo kao što je ovaj Tablica koristi za sortiranje ispit knjige. No hash tablicu je oblik tog visokoj razini Koncept koji bi mogao iskoristiti niz ispod napa da ga provede, ili je mogao koristiti popis dužine, ili čak možda i neke druge strukture podataka. I sad kad je theme-- uzimanje neke od tih temeljnih sastojaka kao i niz ove zgrade blokirati sada popisa duljine i vidjeti što još možemo graditi na vrhu onih koji, poput sastojaka u receptu, što više i više zanimljive i korisne konačni rezultati. 

Dakle, s hash tablicu možemo ga provesti u spomen slikovito ovako, ali Kako bi mogli to zapravo biti kodirani gore? Pa, možda je jednostavno to. Ako KAPACITET u svim kape, samo je neki constant-- primjerice 26, 26 slova alphabet-- Možda ću nazvati svoju promjenjivu stol, i ja mogao tvrditi da ću staviti char zvijezde tamo, ili niza. Dakle, to je kao jednostavan kao ovaj ako žele provesti hash tablicu. Pa ipak, to je zapravo samo niz. Ali opet, mljeveno meso Tablica je sada ono što ćemo nazvati apstraktni tip podataka koji je upravo vrsta konceptualnog raslojavanje na vrhu nešto više mondene Sada se sviđa niz. 

Sada, kako ćemo ići o rješavanju problema? Pa, prije sam imao luksuz da ima dovoljno prostora tablice ovdje tako da sam mogao staviti kvizovi gdje sam htjela. Tako Kao što se moglo ići ovdje. Zs moglo ići ovdje. Gospođa može ići ovdje. A onda sam imao neki dodatni prostor. No, to je malo varati prava sada, jer ove tablice, ako sam stvarno razmišljao o njemu kao polje, samo je će biti od neke fiksne veličine. 

Dakle, tehnički, ako sam povući do drugog studenta kviz i vidjeti, oh, ta osoba je ime počinje sa A također, Nekako sam htio da ga tamo. No, čim sam ga stavio tamo, ako je ova tablica doista predstavlja niz, Ja ću biti preskakanja ili clobbering Tko ovu učenika kviz je. Pravo? Ako je ovo polje, samo jedna stvar može idu u svakoj od tih stanica ili elemente. I tako sam vrsta ima izabrati. 

Sada sam ranije vrsta varao i učinio ovo ili ja samo vrsta stog im jedan iznad drugog. No, to se neće letjeti u kodu. Pa gdje sam mogao staviti Drugi učenik čije ime je li sve što sam imala je to dostupni prostora tablice? I ja sam se tri utora i to Izgleda da postoji samo nekoliko drugih. Što možete učiniti? PUBLIKA: [nečujan] DAVID Malan: Da. Možda neka je samo ga zadržati jednostavan. Pravo? To se ne uklapa u kojoj želim da ga stavite. Tako ću ga staviti tehnički gdje B će ići. Sada, naravno, Počinjem kako bih se slikati u kut. Ako sam se studentu čije ime je zapravo B, Sada B će biti premještena malo prema naprijed, kao što bi se moglo dogoditi, yep, ako je to B, sada mora ići ovdje. 

I tako je to vrlo brzo mogla bi postati problematično, ali to je tehnika koja zapravo se naziva linearni sondiranja, gdje si samo uzeti u obzir svoje Niz se duž linije. A ti samo vrsta probe ili pregledati svaku dostupnu elementa u potrazi za dostupnom mjestu. I čim se nađete jedan, što ga ispustiti tamo. 

Sada, cijena se plaća sada za ovo rješenje je što? Imamo fiksnu veličinu niz, a kad sam umetnuti imena u njega, barem u početku, što je Vrijeme rada umetanja za stavljanje studente ' kvizovi na pravim kante? Big O što? 

PUBLIKA: n. DAVID Malan: Čuo sam veliki O n. Nije istina. Ali mi ćemo zafrkavati, osim Zato u samo trenutak. Što bi drugo moglo biti? 

PUBLIKA: [nečujan] DAVID Malan: I neka mi to učiniti vizualno. Dakle, pretpostavimo da je to pismo S. 

PUBLIKA: To je jedno. DAVID Malan: To je jedno. Pravo? To je niz, koji je znači imamo slučajni pristup. A ako mislimo o tome kao nula i to kao 25., a mi shvatili da, oh, ovdje je moj ulaz S, Ja sigurno mogu pretvoriti S ASCII karakter, u odgovarajućem broju između nule i 25 a zatim odmah stavi ga gdje mu je i mjesto. 

Ali, naravno, čim sam doći do Druga osoba koja je ime je ili B ili C na kraju, ako sam koristiti Linearni sondiranja kao moj rješenje, Vrijeme rada umetanja u najgorem slučaju zapravo će prenijeti na što? I doista sam ga čuo ovdje pravilno rano. PUBLIKA: [nečujan] DAVID Malan: Pa to je doista nakon nje Imate li dovoljno veliki skup podataka. Tako je, s jedne strane, ako Vaš Niz je dovoljno velika a vaši podaci oskudni dovoljno, dobili ovu lijepu stalnu vrijeme. No, čim počnete sve više i više elemenata, i samo statistički dobivate više ljudi sa slovom Njihovo ime ili pismo B, to bi potencijalno spadaju u nešto više ravnih. Dakle, nije baš idealno. Tako smo mogli učiniti bolje? 

Pa, što je naš Rješenje prije kad smo Želite imati veću dinamiku od nešto poput niz dopušteno? PUBLIKA: [nečujan] DAVID Malan: Što ćemo predstaviti? Da. Dakle, popis povezani. Pa, da vidimo što je povezano Popis bi mogao učiniti za nas, umjesto. Pa, neka mi predlažemo da smo nacrtati sliku kako slijedi. Sada je to drugačije Slika iz primjera iz drugog teksta, zapravo, da je zapravo koriste niz veličine 31. I ovaj autor jednostavno odlučio hash žice ne na temelju imena te osobe, ali na temelju njihovih birthdates. Bez obzira na mjesec, oni shvatili Ako ste rođeni na prvi mjesec dana ili 31. u mjesecu, autor hash će na temelju te vrijednosti, kako bi se proširila imena iz malo više od 26 točaka mogao dopustiti. A možda je to malo više ujednačena nego ide s znakovi abecede, jer naravno tu je vjerojatno više ljudi u svijetu s imenima da je početak s nego sigurno neka druga slova abecede. Dakle, možda je to malo više uniformu, uz pretpostavku ravnomjerniji beba preko mjesec dana. 

Ali, naravno, to je još uvijek nesavršena. Pravo? Imamo sudara. Više ljudi u to struktura podataka i dalje imaju istu rođenja barem ti si bez obzira na mjesec. No, ono što je autor učinio? Pa, izgleda da imamo niz Na lijevoj strani nacrtan vertikalno, ali to je samo umjetnički izvedba. Nije bitno u kojem smjeru ti nacrtati niz, to je još uvijek niz. Što je to niz naizgled? 

PUBLIKA: Vezana lista. 

DAVID Malan: Da. Izgleda kao da je niz povezanih popisa. Pa opet, u ovom trenutku od vrste korištenja ove strukture podataka sada kao sastojci u više zanimljivih rješenja, vi apsolutno može potrajati temeljno, kao niz, i onda se nešto više Zanimljivo poput popisa povezan pa čak ih kombinirati u čak zanimljivija struktura podataka. I doista, to također bi se zove hash tablicu, pri čemu je niz stvarno hash tablicu, ali to hash tablica ima lanci, da se tako izrazim, koja može rasti ili smanjiti na temelju broj elemenata koje želite umetnuti. 

Sada, u skladu s tim, što je trčanje vrijeme sada? Ako želim ubaciti nekoga čiji je rođendan je 31. listopada gdje se on ili ona ide? U redu. Na samom dnu gdje piše 31. I to je savršeno. To je konstanta vrijeme. Ali što ako nađemo nekog drugog čiji je rođendan, da vidimo, Listopad, studeni, 31. prosinca? Kada se on ili ona će otići? Ista stvar. Dva koraka ipak. To je konstanta, iako je ne? U redu. U ovom trenutku je to. No, u općem slučaju, više ljudi možemo dodati, probabilistically, idemo da se sve više i više sudara. 

Sada je to malo bolje, jer tehnički Sada moji lanci mogao biti u najgorem slučaju koliko dugo? Ako sam umetnuti n ljudi u ovom više sofisticirana struktura podataka, n ljudi, U najgorem slučaju to će biti n. Zašto? 

PUBLIKA: Jer ako svatko ima isti rođendan, oni će biti jedan redak. DAVID Malan: Savršeno. To bi moglo biti malo neprirodan, ali doista u najgorem slučaju, ako svatko ima isti rođendan, s obzirom na ulaza imate, ti ćeš imati masivno dugolančane. I tako, možete ga se nazvati hash tablicu, ali stvarno je Samo masivni povezani popis s Cijela puno izgubiti prostora. No, u cjelini, ako pretpostavimo da barem rođendana su uniform-- i to vjerojatno nije. Ja sam što to gore. Ali ako pretpostavimo, za Radi rasprave da su, potom u teoriji, ako je To je vertikalna zastupanje od polja, i onda se nadam da ste će dobiti lanaca koji su, znate, otprilike iste duljine, gdje je svaki od to predstavlja dan u mjesecu. 

Sada, ako postoji 31 ​​dana u mjesecu, to znači da moje vrijeme trčanja jako je velik O n preko 31, koji je osjeća bolje nego linearno. No, ono što je bio jedan od naših Obveze par tjedana Prije, kad god je došao na izražavanje Vrijeme rada algoritma? Dovoljno je samo pogledati u visokoj narudžbe roku. Pravo? 31 je svakako korisno. No, to je još uvijek velika O n. No, jedna od tema Problem je postaviti pet će biti priznati da apsolutno, asimptotski, teoretski ova struktura podataka nije bolje nego samo jedan masivan povezani popis. I doista, u najgorem slučaju, to hash tablicu mogli prenijeti u to. 

No, u stvarnom svijetu, s nama ljudima da vlastitim Macove ili računala ili bilo i prikazuju stvarni svijet softver na stvarnom svijetu podacima, algoritam koji ćete radije? Onaj koji vodi završne korake ili onaj koji traje n podijeljena 31 koraka pronaći neki komad podataka ili potražiti neke informacije? Mislim, apsolutno je 31 izvrši Razlika u stvarnom svijetu. To je 31 puta brže. A mi ljudi svakako će cijeniti to. 

Dakle, shvatili dihotomiju postoji između zapravo govori o stvarima teoretski i asimptotski što svakako ima vrijednost kao što smo vidjeli, ali u stvarnom svijetu, Ako vam je stalo samo što Ljudsko sretna za opće inputa, možda vrlo dobro žele prihvatiti Činjenica da, da, ovo je linearna, ali to je 31 puta brže nego linearno moglo biti. I još bolje, ne samo da učinite nešto proizvoljnog poput datuma rođenja, bismo mogli provesti malo više vremena i pameću i razmišljati o tome što bismo mogli učiniti, ime i možda neke osobe njihov datum rođenja kombinirati onima Sastojci shvatiti nešto to je doista više uniformu i manje JAGGY, takoreći od ove slike Trenutno sugerira da bi moglo biti. Kako bismo mogli provesti to u kodu? Pa, neka mi predlažemo da smo Samo posuditi neki sintaksu smo koristiti nekoliko puta do sada. A ja ću definirati čvor, što opet je generički naziv za samo neke Posuda za neke strukture podataka. Ja ću predložiti da niz ide tamo. Ali ćemo početi uzimati onima trening kotačima off sada. 

Nema više CS50 knjižnica stvarno, osim ako ne želite ga koristiti za svoje finale Projekt, koji je u redu, ali sada ćemo povući zavjese i reći to je samo char zvijezda. Dakle, riječ tamo će biti na ime osobe u pitanju. A sada imam vezu Ovdje na sljedeći čvor tako da to predstavlja svaki od čvorova u lancu, potencijalno, popisa povezane. 

I sad kako mogu proglasiti hash sama stol? Kako Izjavljujem cijelu ovu strukturu? Pa, zapravo, baš kao i sam se pokazivač samo na prvi element popisa Prije, slično mogu samo reći Samo mi treba hrpa pokazivača provesti cijeli ovaj hash tablicu. Ja ću imati niz pozvao stol za hash tablicu. To će biti od veličine kapaciteta. Tako su mnogi elementi mogu stati u nju. I svaki od tih elemenata u ovo Niz će biti čvor zvijezda. Zašto? Pa, po ovoj slici, ono što sam provedbi hash tablicu kao učinkovito je samo početak ovaj niz koji smo nacrtana okomito, od kojih svaki kvadrata predstavlja pokazivač. To one koje imaju kose crte kroz njih su samo null. A oni koji imaju Strelice idu u desno su stvarni upućuje na stvarnim čvorova, ergo početka popisa povezane. 

Dakle, ovdje je, dakle, kako bismo mogli implementirati hash tablicu koja provodi poseban ulančavanje. Sada možemo učiniti bolje? U redu sam obećao zadnji put bismo mogli postići stalnu vrijeme. A ja vrsta ti dao konstanta vrijeme ovdje, ali onda nije rekao stvarno vremenska konstanta, jer to je još uvijek ovisno o ukupnom broj elemenata ti si unosom u struktura podataka. No, pretpostavimo da je to učinio. Pusti me da se vratim na zaslonu ovamo. Dopustite mi također projiciraju to ovdje, jasno zaslon, a da bih to učinio. Pretpostavimo da sam htjela umetnuti ime Daven u u moju strukturu podataka. 

Dakle, želim umetnuti niz Daven u strukturu podataka. Što ako ne koristim hash tablicu, ali ja koristiti nešto što je više stabala nalik poput obiteljskog stabla, gdje je Imate li neki korijen u vrhu, a zatim čvorovi i lišće da ide prema dolje i prema van. Pretpostavimo onda da ja želite umetnuti Daven-a u ono što je trenutno prazna popis. Ja ću učiniti sljedeće: Ja sam će stvoriti čvor u ovoj obitelji stabla kao struktura podataka koja izgleda nešto kao što je ovaj, od kojih svaka pravokutnici je, recimo, za sada 26 elemenata u njemu. I svaka ćelija U tom nizu ide zastupati pismo jednog pisma. 

Naime, idem na liječenje To je, onda B, zatim C, zatim D, ovaj ovdje. Dakle, to će učinkovito predstavljaju slovo D. No, umetanje sve Daven-a ime moram učiniti nešto više. Pa ja sam prvi put ide na mljeveno meso, da se tako izrazim. Ja ću gledati na prvo slovo U Daven-a koji je očito D, a ja ću izdvojiti čvor koji izgleda kao this-- veliki pravokutnik veliki dovoljno da stane na cijelu abecedu. 

Sada D je učinio. Sada A. D--V-E-N je cilj. Pa sad što ću učiniti je to. Čim sam počeo D obavijest nema kazaljke nema. To je smeće vrijednosti u ovom trenutku, ili sam možda ga inicijalizirati na nulu. No, dopustite mi da ide s ta ideja o izgradnji stablo. Dopustite mi izdvojiti još jedan od njih čvorovi koji ima 26 elemenata u njoj. 

I znate što? Ako je to samo čvor u sjećanju da je Napravio sam s malloc, pomoću struct kao što ćemo uskoro vidjeti, Ja ću učiniti this-- Ja ću nacrtati strelicu stvar koja zastupa D prema dolje na ovaj novi čvor. I sada, prvi sljedeći Pismo u Daven ime, V-- D--V-- ću ići naprijed i privući još jedan čvor kao što je ovaj, pri čemu su V elementi ovdje, koji ćemo izvući za instance-- Ups. Nećemo povući tamo. To će ići ovdje. 

Onda ćemo smatram da je to V. A onda ovdje ćemo indeksa dolje iz V u ono što ćemo razmotriti E. A onda odavde ćemo nesposobnu jedan od tih čvorova ovdje. I sad imamo pitanje za odgovor. Moram nekako pokazuju da smo na kraju niza Daven. Dakle, samo sam mogao vratiti ga null. 

Ali što ako imamo Daven a ime i prezime i koji je, kao što smo rekli, Davenport? Pa što ako je Daven zapravo podniz, prefiks mnogo duži niz? Ne možemo baš stalno kažu ništa ne događa ići tamo, jer smo mogli Nikada umetanje riječi poput Davenport u ovu strukturu podataka 

Pa što bismo mogli učiniti umjesto toga je tretirati svaki od tih elemenata što možda ima dva elementi unutar njih. Jedan od njih je pokazivač, doista, kao što sam bio događaj. Dakle, svaki od tih kutija nije samo jedna stanica. Ali što ako je vrh one-- dno nečije će biti nula, jer nema Davenport samo još. Što ako jedan vrh je neka posebna vrijednost? I to će biti malo teško je to veličina izvući. Ali pretpostavljam da je to samo kvačica. Check. D--V-E-N je niz U toj strukturi podataka. 

U međuvremenu, ako sam imao više prostora ovdje, što sam mogao učiniti P-O-R-T, i ja mogao staviti oznaku u čvoru koja ima slovo T na samom kraju. Dakle, ovo je masivno Kompleks izgleda strukturu podataka. I moj rukopis Sigurno ne pomaže. Ali ako sam htio ubaciti nešto drugo, razmislite što ćemo učiniti. Ako smo htjeli staviti Davida u, bismo slijediti istu logiku, D-A-V, ali sada bih uputiti u iduće element ne iz E, ali od I. do D. Tako će biti više čvorovi u ovom stablu. Mi ćemo imati poziva malloc više. Ali ja ne želim napraviti potpuni nered ovu sliku. Tako ćemo umjesto da pogledate jedan koji je bio unaprijed formuliran kao što je ovaj sa ne dot, dot, točkice, ali samo skraćeni polja. No, svaki od čvorova U ovom stabla ovdje predstavlja istu stvar-- Niz Ray veličine 26. 

Ili, ako želimo biti stvarno pravi sad, što Ako nečije ime kao apostrof, neka je Pretpostavljamo da svaki čvor zapravo ima kao što je 27 indeksa u njemu, a ne samo 26. Dakle, ovo je sada će biti podaci Struktura naziva trie-- T-R-I-e. Trie, koji je navodno povijesno pametan ime za drvo koji je optimiziran za dohvat, što je, naravno, napisane s I-E pa to je Trie. Ali to je povijest Trie. 

Dakle Trie je ovo drvo poput podataka Struktura poput obiteljskog stabla koji u konačnici se ponaša kao da je. I ovdje je samo još jedan primjer cijela hrpa tuđih imena. No, pitanje je sad pri ruci je ono što imamo dobili smo uvođenjem nedvojbeno više složenoj strukturi podataka, i on, iskreno, koji koristi mnogo memorije. 

Jer iako, u ovom trenutku, ja sam samo korištenjem D's pokazivač i I V i Es i NS, Ja sam gubit ispitati kritički od puno memorije. Ali gdje sam provesti jedan resurs, Ja obično ne dobiti natrag drugog. Dakle, ako sam trošiti više prostora, što je vjerojatno nada? To ću trošiti manje što? PUBLIKA: Manje vremena. DAVID Malan: Vrijeme. Sad zašto bi to moglo biti? Pa, ono što je umetanje vrijeme, u smislu velikog O sada, naziva kao Daven ili Davenport ili David? Pa, Daven je pet koraka. Davenport će biti devet koraka, tako da će biti još nekoliko koraka. David bi biti pet koraka kao dobro. Dakle, to su konkretni brojeve, ali sigurno postoji gornja granica na duljina nečijeg imena. I doista, u problemu seta pet specifikacije, ćemo predložiti da je to nešto To je 40-neke-ak znakova. 

Realno, nitko nema beskonačno dugo ime, što će reći da je duljina ime ili duljina niza smo mogli ima sigurno stanje Struktura je nedvojbeno što? To je konstanta. Pravo? To bi moglo biti velika stalna poput 40-nešto, ali je konstantan. I to nema ovisnosti o tome koliko ostali su imena u ovoj strukturi podataka. Drugim riječima, ako sam htjela sada umetanje Colton ili Gabriel ili Rob ili Zamyla ili Alison ili Belinda, ili bilo koja druga imena od osoblja u ovoj podataka struktura, je trčanje vrijeme umetanja druga imena će biti uopće utjecali koliko mnogih drugih elemenata U strukturi podataka već? To nije. Pravo? Budući da smo učinkovito korištenje ovaj višeslojni hash tablicu. A vrijeme rada bilo koji od ovih operacija ne ovisi o broju Elementi koji su u strukturi podataka ili da na kraju ide da u strukturi podataka, ali na duljinu što posebno? 

Niz se umetnuta, koji ne čine ovo asimptotski stalna time-- veliki O jedne. I iskreno, samo u stvarnom svijetu, to znači umetanje Daven ime traje kao pet koraka, ili Davenport devet koraka, ili je David pet koraka. To je prilično prokleto malo vremena trčanje. I, doista, to je vrlo dobra stvar, pogotovo kad to ne ovisi o ukupno Broj elemenata u tamo. Pa kako bismo mogli provesti taj vrsta strukture u kodu? To je malo više kompleksna, ali još uvijek je Samo primjena osnovni građevni blokovi. Idem redefinirati nas čvor kako slijedi: bool nazvao word-- i to bi se moglo nazvati ništa. No bool predstavlja ono što sam nacrtao kao kvačicom. Da. To je kraj niza U toj strukturi podataka. 

I, naravno, čvor zvijezda tu se odnosi na djecu. I, doista, baš kao i obiteljsko stablo, što bi razmotriti čvorova koji su visi dna neke roditelja element biti djeca. I tako djeca će se niz 27, 27 jedan samo se za apostrof. Idemo sortiranje o posebnom slučaju tog. Tako možete imati sigurno Imena s apostrofe. Možda čak i crtica trebala ići tamo, ali ćete vidjeti u p setu 5 mi samo njegu o pismima i apostrofe. 

A onda kako se predstavljate Sama struktura podataka? Kako se predstavlja korijen ove Trie, da tako kažem? Pa, baš kao s popisa povezane, što potreban pokazivač na prvi element. Uz Trie trebate samo jedan pokazivač na korijen ove Trie. A od tamo možete hash svoj put prema dolje sve dublje i dublje na svaki drugi čvor u strukturi. Tako jednostavno s ovom kantom zastupamo tu struct. 

Sada Meanwhile-- Oh, pitanje. 

PUBLIKA: Što je bool riječ? 

DAVID Malan: Bool riječ upravo to C utjelovljenje onoga što sam opisao U ovoj kutiji ovdje, kada je Počela sam cijepanje svaki od niz elemenata je u dva dijela. Jedan je pokazivač na sljedeći čvor. Drugi mora biti nešto poput potvrdni okvir reći da, postoji Riječ Daven da se ovdje završava, zato što ne želimo, u ovom trenutku, Dave. 

Iako Dave će biti legitimna riječ, on nije u Trie još. A D Nije riječ. I D-nije riječ ili naziv. Tako je kvačicom ukazuje samo jednom vas hit ove čvor Prethodni put znakova zapravo niz koji ste umetnuli. Tako da je sve bool tu se radi za nas. 

Ima li još pitanja o pokušaja? Da. 

PUBLIKA: Što je preklapanja? Što ako imate Dave i Daven? DAVID Malan: Savršeno. Što ako imate Dave i Daven? Dakle, ako ćemo ubaciti, kažu nadimak, za David-- Dave-- D-A-V-E? To je zapravo super jednostavna. Tako smo samo će potrajati četiri koraka. D-E-V-. I što moram ne jednom sam pogodio taj četvrti čvor? Samo ću provjeriti. Već smo dobro ide. Gotovo. Četiri koraka. Konstantna vrijeme asimptotski. I sada smo pokazali da i Dave i Daven su žice u strukturi. Dakle, nije problem. I primijetiti kako prisutnost od Daven ne čine ga uzeti više vremena ili manje Vrijeme za Dave i obrnuto. 

Pa što još možemo sada učiniti? Koristili smo tu metaforu prije od ladica predstavlja nešto. No, ispada da snop ladica je zapravo demonstrativni drugog apstraktnog podataka type-- višu razinu strukturu podataka da je na kraju dana je samo kao polje ili popis povezan ili nešto više svjetovnim. No, to je još zanimljivije konceptualni pojam. Stog, kao što je to ladice ovdje u Mather, Nazivaju se Samo that-- hrpu. 

I u ovoj vrsti strukture podataka imate dva operations-- imate jedan zove poticaj za dodao nešto na stog, poput stavljanja još jednu ladicu natrag na vrhu dimnjaka. I onda pop, što vam znači uzeti vrhunski ladice off. No, ono što je ključno o stog je da to je dobio ovu neobičnu karakteristiku. Kao blagovaonice osoblja preraspodjela ladice za sljedeći obrok, što će biti Istina o tome kako studenata interakciju s ove strukture podataka? PUBLIKA: Oni će se pojaviti jedan off. DAVID Malan: Oni će pop One, nadamo se do vrha. Inače to je samo vrsta glupo ići sve do dna. Pravo? Struktura podataka zapravo ne dopuštaju da iskoristite dno ladice najmanje lako. Tako da je ovo zanima Objekt na stog da je posljednja stavka u je će biti prvi van. A računalni znanstvenici nazivaju to LIFO-- trajati u, prvi van. I to zapravo nema zanimljive aplikacije. To ne mora nužno biti tako očite kao što neki drugi, ali se može doista biti korisno, i to može, doista, biti proveden u nekoliko različitih načina. 

Tako je jedan, i zapravo, neka ja ne zaroniti u to. Idemo to učiniti umjesto. Pogledajmo jedan koji je gotovo ista ideja, ali to je malo ljepša. Pravo? Ako ste jedan od tih navijačkih dječaka ili djevojke koja stvarno voli Apple proizvode a vi se probudio u 3:00 da se postroje u nekom dućanu dobiti najnovije iPhone, Možda su se okupili kao što je ovaj. 

Sada je red vrlo namjerno zove. To je crta, jer postoji neke pravičnosti na njega. Pravo? To bi vrsta sisao, ako ste stigli prvi na Apple Store ali vi ste učinkovito najniži ladicu jer Apple zaposlenicima onda pop posljednju osobu koja zapravo je dobio u redu. Dakle, dimnjaka i redove, iako to funkcionalno oni vrsta u same-- to je samo ova zbirka sredstava koji je će rasti i shrink-- tu je to pravednost aspekt na njega, barem u stvarnom svijetu, gdje su poslovi vježbate bitno razlikuju. Stack-- red rather-- je rekao da su dvije operacije: n red i d red. Ili ih možete nazvati bilo koji broj stvari. Ali samo želite snimiti spoznaja da je netko dodao a jedan je u konačnici oduzimanjem. 

Sada ispod haube, i stog i red bi mogao biti proveden kako? Nećemo ulaziti u kodeksu Zato što viša razina Ideja je vrsta očitija. Mislim, što da i ljudi? Ako sam prva osoba na Apple Spremite i to je ulazna vrata, znaš, ja ću stajati ovdje. I sljedeća osoba je će stajati ovdje. I sljedeća osoba je će stajati ovdje. Pa što struktura podataka sama posuđuje na red? 

PUBLIKA: red. DAVID Malan: Pa, red. Naravno. Što još? 

PUBLIKA: Popis povezani. 

DAVID Malan: povezani popis bi mogao provesti. A popis vezan je lijepo, jer tada to može rasti proizvoljno dugo razliku da ima neki fiksni broj ljudi u trgovini. No, možda fiksni broj mjesta je legitimna. Jer ako su samo kao i 20 iPhonea prvog dana, možda što im je potrebno samo niz veličine 20 zastupati taj red čekanja, koji samo je sada reći nakon što počnemo govoriti o tim problemima višim razinama, možete ga provesti na bilo koji broj načina. I tu je vjerojatno samo ide biti trade off u prostoru i vremenu ili samo u svoj vlastiti kod složenosti. 

Što je stog? Pa, stog, vidjeli smo previše može biti samo ove ladice. A ti bi mogao provesti ovaj niz. No, u nekom trenutku ako koristite niz, što će se dogoditi s ladicama pokušavate staviti dolje? U redu. Vi ste samo ide na moći ići tako visoko. I mislim da je u Mather su zapravo uvučeni u taj otvor. Dakle, istina, to je gotovo kao Mather koristi niz fiksne veličine, jer možete samo stane toliko ladice u tom otvaranju u Zid dolje ljudi koljena. I tako bi moglo biti rekao je da se polje, ali smo svakako mogli provesti da općenitije s popisa povezane. 

Pa, što je s drugom strukturom podataka? Dopustite mi podići jedan drugi vizualni ovdje. Nešto kao što je o tome kako je ovaj ovdje? Zašto bi moglo biti korisno imati ne nešto kao fantazija kao Trie, koji smo vidjeli imali ove vrlo široke čvorova, svaki od kojih je u nizu? Ali što ako mi se nešto više jednostavno, kao stara škola obiteljskog stabla, svaki od čvorova čije ovdje je upravo spremate broj. Umjesto imena ili potomak je upravo spremate broj kao što je ovaj. 

Pa, žargonu koristimo u strukture podataka je oba pokušaja i drveće, gdje Trie, opet, Samo onaj čije čvorovi su nizovi, je još uvijek ono što bi moglo koristiti iz osnovnoj školi kada se obitelj tree-- listovi i korijen stabla i djecu roditelja i njihove braće i sestara. I možemo provesti stablo, na primjer, kao što je to jednostavno. Stabla, ako je to kao čvor, jedan od ti krugovi koji ima broj, to neće imati jedan pointer, nego dva. I čim ste dodali Drugi pokazivač, što zapravo može sada napraviti svojevrsni od dvodimenzionalni podataka strukture u memoriji. Slično kao dvodimenzionalni Niz, možete ima kakav dvodimenzionalne povezani popisi, ali one da slijede uzorak tamo gdje je nema ciklusa. To je doista stablo s jednim djed i baka put ovdje, a zatim neki roditelji i djeca i unuci i praunuci. i tako dalje. 

No, ono što je stvarno uredan o tome previše, samo da vas zafrkavati s malo koda, Opoziv rekurzija od neko vrijeme natrag, pri čemu što napisati funkciju koja se poziva. Ovo je lijepa prilika provesti nešto kao što rekurzije, jer smatram to. 

To je stablo. I ja sam bio malo analni s načinom Stavio sam se cijeli brojevi na ulicu. I to toliko da je posebna name-- binarno pretraživanje stablo. Sada smo čuli binarna traženje, ali može vas raditi unatrag od ova stvar imena? Što je uzorak kako sam umetnuli prirodnih brojeva u ovom stablu? To nije proizvoljna. Postoji neki obrazac. Da. 

PUBLIKA: Manji one na lijevoj strani. 

DAVID Malan: Da. Manji one su na lijevoj strani. Veće one su na desnoj strani. Takav da je istina izjava roditelj je veća od njegove lijeve dijete, ali manje od njegove desne djeteta. I to samo još rekurzivna verbalnog definicija jer možete podnijeti zahtjev da se Ista logika za svaki čvor i to samo dno out, osnovni scenarij, ako vas će, kada se zabio u lišće, da tako kažemo, gdje dopust nema djece i dalje. 

Sada kako možda ćete naći broj 44? Ti bi početi u korijenu i reći, hm. 55 nije 44 I ja želim ići pravo ili ne želim ići lijevo? Pa, očito želite ići lijevo. I to je baš kao i telefona Knjiga je primjer u binarnom potrazi općenito. No, mi smo ga provedbi Sada malo više dinamički nego niz mogao dopustiti. A u stvari, ako želite izgledati u kodu, na prvi pogled sigurno. To izgleda kao cijela hrpa linija. Ali, to je lijepo jednostavna. Ako želite provesti funkciju zove pretragu čija je svrha u životu je u potrazi za vrijednošću kao što je n cijeli broj, a vi ste prošli u jednom pointer-- pokazivač na čvoru korijena, a, tog stabla od kojih možete pristupiti sve ostalo, primijetiti kako se izravno možete provesti logiku. Ako stablo je null, očito da to ne postoji. Ajmo se vratiti false. Pravo? Ako ga predati ništa, nema ničega. 

Inače, ako je n manji od Stablo strelica n- sada strijela n, podsjetiti uveli smo super Kratko drugi dan, a to samo znači de-reference na pokazivač i pogledajte polju zvanom n. Dakle, to znači otići tamo i pogledajte polju zvanom n. Dakle, ako n, vrijednost koju si dao, manje od vrijednosti na cijeli broj stabala, gdje želiš ići? S lijeve strane. 

Dakle primijetiti rekurzija. Ja returning-- nije istina. Ne lažna. Ja sam se vraćaju bez obzira na odgovor je od poziva do sebe, prolazeći opet nje, što je suvišno, ali ono što je sada nešto drugačije? Kako sam ja problem što manja? Ja sam u prolazu, kao drugo argument, a ne korijen stabla, ali lijeva dijete u ovom slučaju. Tako sam prolazeći u lijevom dijete. 

U međuvremenu, ako je n veći od čvor Ja sam trenutno gledajući, Tražim desnoj strani. Inače, ako je stablo nije null, i Ako se element ne lijevo i to ne na desno, ono što je predivno slučaj? Mi zapravo našli čvor u pitanje, pa smo se vratili istinito. 

Dakle, upravo smo zagrebali površinu Sada neki od tih struktura podataka. U Problem postaviti pet vi ćete istražite to još dalje, a vi ćete dati svoj dizajn izbor kako to ide o tome. Ono što bih želio zaključiti na je samo drugi teaser 30 onoga što čeka sljedeći tjedan i izvan nje. 

Kao što smo begin-- srećom li možda think-- naš prijelaz polako iz svijeta C i niže detalji provedbe razini, u svijetu u kojem možemo uzeti zdravo za odobriti da netko drugi ima napokon provoditi ove podatke strukture za nas, pa ćemo početi razumjeti stvarni svijet sredstva za provedbu web-based programa i web općenitije a također je vrlo sigurnost implikacije da smo samo počeli ispočetka površinu. Evo što nas čeka U danima koji dolaze. 

[Video reprodukcije] 

-On Je došao s porukom, s protokolom sve svoje. Došao je na svijet okrutno firewall, usmjerivači, nemilosrdan i opasnosti daleko gore od smrti. On je brzo. On je jak. On je TCP / IP, a on je dobio svoju adresu. "Ratnici Mreže". [END reprodukciju videozapisa] DAVID Malan: Dolazi sljedeći tjedan. Mi ćemo vas vidjeti onda. [Video reprodukcije] -I Sada, "Deep Misli" po Daven Farnham. -David Uvijek počinje predavanja sa "sve u redu." Zašto ne, "Evo rješenje na ovotjednom skupu problema " ili "dajemo sve od tebe?" [Laughing] [END reprodukciju videozapisa]