>> [Mūzikas atskaņošanai]
>> ANDI PENG: Aicinām 6 nedēļu sadaļā.
Mēs atkāpies no mūsu standarta sadaļa laiks otrdien
Pēcpusdienā uz šo skaisto svētdienas rītā.
Paldies ikvienam, kas pievienojās man šodien, bet nopietni,
kārta aplausi.
>> Tas ir diezgan liels pūles.
Es gandrīz nav pat darīt to up laikā, bet tas bija OK.
Tāpēc es zinu, ka jūs visi tikko veikts to viktorīnas.
Pirmkārt, laipni aicināti Otra puse no tā.
>> Otrkārt, mēs runājam par to.
Mēs runājam par viktorīnas.
Mēs runājam par to, kā jūs darāt šajā klasē.
Jums būs labi.
Man ir jūsu viktorīnas tu beigās šeit,
Tātad, ja jūs guys vēlaties veikt apskatīt to, pilnīgi naudas sodu.
>> Tik ātri, pirms mēs sākam, tad darba kārtība šodien ir šāds.
Kā jūs varat redzēt, mēs esam būtībā ātra šaušana
cauri visai ķekars datu struktūras tiešām, tiešām, tiešām ātri.
Tā kā, piemēram, tas nevar būt super interaktīvs šodien.
Tas būs vienkārši man veida kliegšana lietas, kas jums, un, ja es sajaukt jums,
ja es esmu pārāk ātri, ļaujiet man zināt.
Viņi vienkārši dažādus datus struktūras, un kā daļa
Jūsu PSET par šo nākamajā nedēļā, jūs
tiks lūgts, lai īstenotu vienu no tām, varbūt divas no them-- diviem no tiem
Jūsu PSET.
Labi, tāpēc es esmu tikai gatavojas sākt ar dažiem paziņojumiem.
Mēs iet pār skursteņi un rindas vairāk in dziļums, nekā tas, ko mēs darījām pirms viktorīnas.
Mēs iet pār saistīta uzskaitīt atkal, atkal,
padziļināti, nekā to mums bija pirms viktorīnas.
Un tad mēs runājam par hash galdi, koki un mēģina, kas
visi ir diezgan nepieciešams jūsu PSET.
Un tad mēs iet pār daži noderīgi padomi pset5.
>> Labi, tā viktorīna 0.
Vidējā bija 58%.
Tas bija ļoti zems, un tāpēc jums puiši visi darīja ļoti, ļoti labi saskaņā
ar to.
>> Diezgan daudz, īkšķis ir, ja tu esi ietvaros standartnovirzi vidējo
jo īpaši tāpēc mēs esam mazāk comfy sadaļa, tu esi pilnīgi naudas sodu.
Jūs esat uz pareizā ceļa.
Dzīve ir laba.
>> Es zinu, tas ir biedējošu domāt, ka Man, piemēram, 40% par šo viktorīnu.
Es esmu gatavojas neveiksmei šajā klasē.
Es apsolu jums, jūs neesat gatavojas neveiksmei klasi.
Tu esi pilnīgi naudas sodu.
>> Attiecībā uz tiem no jums, kas ieguva vairāk vidējais, iespaidīgs, iespaidīgs,
piemēram, nopietni labi darīts.
Man ir viņiem ar mani.
Jūtieties brīvi nākt malējos beigās nodaļā.
Let me know, ja Jums ir kāds jautājumi, jautājumi ar tiem.
Ja mēs pievienot savu rezultātu nepareizi, dodiet mums zināt.
>> Labi, tā pset5, tas ir patiešām dīvaini nedēļa Yale tādā ziņā
ka mūsu PSET ir saistīts Trešdienu pusdienlaikā ieskaitot
vēlu dienu, tāpēc tas ir patiesībā Teorētiski dēļ otrdien plkst.
Droši vien neviens pabeigts pie otrdien plkst.
Tas ir pilnīgi naudas sodu.
Mēs ejam, lai būtu darba laiku šovakar kā arī pirmdien naktī.
Un visi no sadaļām šonedēļ faktiski pārvērtās darbnīcām,
lai justies brīvi, lai pop jebkurš sadaļā jūs vēlaties,
un tie būs sava veida mini-PSET darbnīcas palīdzību par to.
Tā kā, piemēram, tas ir tikai daļa kur mēs esam mācību materiālu.
Visas pārējās sadaļas tiks koncentrējoties tikai uz palīdzību par PSET.
Yeah?
>> Mērķauditorija: Kur ir darba laiks?
>> ANDI PENG: Darba laiks tonight-- oh, labs jautājums.
Es domāju, ka darba laiks šovakar ir Teal vai Commons.
Ja jūs pārbaudīt tiešsaistes CS50 un doties uz darba laika,
ir jābūt grafiks, kas stāsta jums, kur visi no tiem ir.
>> Es zinu, nu šovakar vai rīt ir krīklis,
un es domāju, ka mēs varētu būt koptelpas par otras naktī.
ES neesmu pārliecināts.
Labs jautājums.
Pārbaudiet uz CS50.
>> Cool, kādi jautājumi par grafiku tamlīdzīgi trīs dienas nākamais?
Es apsolu jums puiši, piemēram, David teica, tas ir augšā kalnā.
Jūs guys ir gandrīz tur.
Tikai trīs vairāk dienas.
Nokļūt tur, un tad mēs visi nāk uz leju.
Mums būs jauka CS-free pārtraukuma.
Mēs būsim atpakaļ.
Mēs ienirt tīmeklī programmēšana un attīstība,
lietas, kas ir ļoti jautri, salīdzinot ar dažām citām psets.
Un tas būs chill, un mums būs daudz jautrības.
Mums būs vairāk konfektes.
Atvainojiet saldumiņu.
Es aizmirsu konfektes.
Tas bija raupja rīts.
Tātad jums puiši ir gandrīz tur, un es esmu patiesi lepns par jums puiši.
>> Labi, tā skursteņi.
Kurš mīlēja jautājumu par Jack un viņa drēbes uz viktorīnu?
Neviens?
Labi, tas ir jauki.
>> Tātad būtībā, kā jūs varat bilde Jack, šis puisis šeit,
mīl veikt apģērbu no augšējās,
un viņš liek to atpakaļ uz kaudze pēc viņš ir darīts.
Tātad šādā veidā, viņš nekad šķiet, kļūst
uz dibenā kaudze viņa apģērbu.
Tātad šāda veida apraksta pamata datu struktūra
par to, kā kaudze tiek īstenots.
>> Būtībā, domāt par kaudze kā jebkurš kaudze objektu
kur jūs nodot lietas uz augšu, un tad jūs pop tos no augšas.
Tātad LIFO ir akronīms mums patīk lai use-- pēdējais iekšā, pirmais ārā.
Un tā ilgs, lai augšpusē kaudze ir pirmais, kas nāk ārā.
Un tā abi termini mēs vēlētos saistīt
ar to sauc par push un pop.
Kad jūs push kaut uz kaudze, un jūs pop to atpakaļ uz augšu.
>> Un tāpēc es domāju, tas ir sava veida abstrakts jēdziens tiem no jums,
kuri vēlas redzēt, piemēram, faktisko īstenošanu šis
reālajā pasaulē.
Cik daudzi no jums ir uzrakstījis eseju varbūt, piemēram, stundu pirms tas bija saistīts,
un jūs nejauši svītrots milzīgs rieciens no tā, piemēram, nejauši?
Un tad ko darīt kontrole mēs izmantojam, lai nodot to atpakaļ?
Control-Z, jā?
Kontrole-Z, tā daudzums reizes ka Control-Z ir izglāba man dzīvību,
izglāba manu ass, katru reizi kas ir īstenota ar skursteņiem.
>> Būtībā visa informācija tas ir jūsu Word dokumentu,
tas izpaužas uzstājām un popped pēc vēlēšanās.
Un tā būtībā, kad jūs izdzēst kaut ko, jūs pop to atpakaļ uz augšu.
Un tad, ja jums to vajag atpakaļ, jūs push to, kas ir tas, ko Control-C dara.
Un tā reālā pasaule funkcija par to, kā vienkāršas datu struktūras
var palīdzēt ar savu ikdienas dzīvi.
>> Tātad struct ir tā, ka mēs faktiski izveidot kaudze.
Mēs tipa definēt struct, un pēc tam Mēs to saucam kaudze apakšā.
Un ietvaros kaudze, mums ir divi parametri
ka mēs varam būtībā manipulēt, tāpēc mums ir char zvaigžņu stīgas jaudu.
>> Viss, kas tā dara rada masīvs
ka mēs varam saglabāt, ko vien vēlaties ko mēs varam noteikt savas spējas.
Ietilpība ir tikai max summa preces mēs varam nodot šajā masīvā.
int izmērs ir skaitītājs, kas uztur izsekot, cik daudz preces ir šobrīd
kaudze.
Tātad, tad mēs varam sekot līdzi, A, gan cik liels faktiskais kaudze ir,
un, B, cik daudz no šī kaudze mēs piepildīta, jo mēs nevēlamies
pārplūdes par to, kas mūsu kapacitāte ir.
>> Tā, piemēram, šī jaukā Jautājums bija par savu viktorīnā.
Būtībā kā mēs push uz augšu grēdas.
Diezgan vienkārši.
Ja paskatās uz to, mēs staigāt pa šo.
Ja [dzirdams] size-- atcerieties, kad jūs
vēlas piekļūt jebkurš parametrs ietvaros struct,
jums nosaukumu struct.parameter.
>> Šajā gadījumā, s ir nosaukums mūsu kaudze.
Mēs vēlamies, lai piekļūtu izmēru par to, lai mēs to s.size.
Tik ilgi, kamēr tās izmēri ir ne vienāda ar jaudu vai tik ilgi,
jo tas ir mazāk nekā jauda, nu varētu strādāt šeit.
>> Jūs vēlaties, lai piekļūtu iekšpusi Jūsu kaudze, tā s.strings,
un jūs gatavojas nodot, ka jaunu numuru ka jūs vēlaties ievietot tur.
Pieņemsim tikai teikt, mēs vēlamies, lai ievietot int n uz steku,
mēs varētu darīt s.strings, kronšteini, s.size vienāds n.
Tāpēc, ka izmērs ir, ja mēs Pašlaik kaudze
ja mēs spēsim virzīt tā tālāk, mēs vienkārši piekļūt
kur lielums ir, tad Pašreizējais pilnība kaudze,
un mēs push int n uz to.
Un tad mēs gribam, lai pārliecinātos, ka mēs arī palielināšanai lielumu n,
lai mēs varētu sekot mēs esam pievieno papildu lieta kaudze.
Tagad mums ir lielāka izmēra.
Vai tas šeit jēgas everybody, cik loģiski tas darbojas?
Tā bija sava veida ātri.
Mērķauditorija: Vai jūs varat iet pa tad s.stringss.strings [s.size] vēlreiz?
ANDI PENG: Protams, lai to, ko dara s.size šobrīd dod mums?
Mērķauditorija: Tas ir pašreizējais izmērs.
ANDI PENG: Tieši tā, tāpēc pašreizējais rādītājs, ka mūsu izmērs ir,
un tāpēc mēs vēlamies likt jaunu skaitlim ka mēs gribam ievietot s.size.
Vai tas ir jēga?
Jo s.strings, viss, kas ir ir nosaukums masīva.
Viss, kas ir, ir piekļūstot masīvs mūsu struct,
un tāpēc, ja mēs gribam, lai izvietot n minētajā indeksā,
mēs varam tikai piekļūt izmantojot kronšteini s.size.
Cool.
>> Labi, pop, es pseudocode to ārā lai jūs puiši, bet līdzīgu koncepciju.
Vai tas ir jēga?
Ja izmērs ir lielāks par nulli, tad jūs
zinu, ka jūs vēlaties veikt kaut ko out jo, ja izmērs nav
lielāks par nulli, tad jūs nav nekā kaudze.
>> Tātad jūs tikai vēlaties izpildīt šis kods, tas var tikai
pop, ja ir kaut kas, lai pop.
Tātad, ja izmērs ir lielāks par 0, mēs mīnus izmērs.
Mēs Samazināt izmēru un pēc tam atgriezties kāds ir iekšā to, jo
ar popping, mēs vēlamies kāds tiek glabāti piekļuve
indeksā no augšējās.
Viss jēga?
Ja es jūs guys rakstīt šo, Vai jūs puiši varētu rakstīt to ārā?
Labi, jūs guys var spēlēt aptuveni ar to.
Neraizējieties, ja Jums nav iegūt to.
Mums nav laika, lai kods tas, kas šodien, jo mēs esam
ieguvuši daudz šo struktūru iet cauri, bet būtībā
pseudocode, ļoti, ļoti līdzīgs virzīt.
Vienkārši sekojiet līdzi loģiku.
Pārliecinieties, ka jūs piekļūt visiem iezīmes jūsu struct pareizi.
Yeah?
>> Mērķauditorija: Vai šie slaidi un Tas viss ir jau šodien-ish?
ANDI PENG: Vienmēr, yep.
Es esmu gatavojas izmēģināt likt šo augšu, piemēram, stundu pēc.
Es e-pastu Dāvidu, David centīsies ielieciet to uz augšu, piemēram, stundu pēc šo.
>> Labi, tā tad mēs pāriet uz šo otru lovely datu struktūra sauc rindā.
Kā jūs guys var redzēt šeit A rinda, par Lielbritānijas starp mums,
viss tas ir ir līnija.
Tātad pretēji tam, ko Jūs domājat, ka kaudze ir,
rinda ir tieši tas, loģiski jūs domājat, ka tas ir.
Tas notika pēc noteikumiem par FIFO, kas ir pirmais iekšā, pirmais ārā.
Ja jūs esat pirmais viena līnija, tu esi
pirmais, kas nāk no līnijas.
>> Tātad, ko mēs vēlētos, lai izsauktu šo ir dequeueing un enqueueing.
Ja mēs vēlamies pievienot kaut ko mūsu rindā, mēs ierindod.
Ja mēs vēlamies, lai dequeue, vai veikt kaut prom, mēs dequeue.
>> Tā pati sajūta, ka mēs esam sava veida radot fiksēta izmēra elementus, kas mums
var uzglabāt dažu lietas, bet mēs varam arī
mainīt, ja mēs esam ievietojot parametri iekšpusē no tiem
pamatojoties uz to tipa funkcionalitāti mēs gribam.
Tātad skursteņi, mēs vēlējāmies pēdējais viens, N, ka pirmais ārā.
Rindas ir, mēs gribam, pirmā lieta, lai būtu pirmā lieta out.
>> Tātad uz struct tipa noteikt, kā jūs varat redzēt,
tas ir mazliet atšķirīgs no tā, ko bija kaudze
jo ne tikai mums ir, lai saglabātu trase, kur lielums šobrīd ir,
mēs arī vēlamies, lai sekotu galvas kā arī kur mēs šobrīd esam.
Tāpēc es domāju, ka tas ir vieglāk ja es izdarīt šo augšu.
Tātad, pieņemsim iedomāties, mēs esam ieguvuši rindā, tāpēc pieņemsim, ka galva ir tepat.
No līnijas vadītājs, pieņemsim tikai teikt, ka tas šobrīd tur,
un mēs vēlamies, lai ievietotu kaut rindā.
Es esmu dodas uz zvanu izmēru būtībā ir tas pats, astes,
beigas kur jūsu rinda ir.
Pieņemsim tikai teikt izmērs ir tepat.
>> Tā kā var reāli ievietot kaut stājas rindā?
Ko indekss mēs vēlamies ievietot kur mēs vēlamies ievietot.
Ja tas ir sākums jūsu rindā un tas ir beigas tā
vai lielums no tā, kur mēs vēlaties pievienot nākamo objektu?
>> Mērķauditorija: [dzirdams]
ANDI PENG: Tieši tā, jūs vēlaties pievienot tā atkarībā esat uzrakstījis to.
Vai nu tas ir tukšs, vai tas ir tukšs.
Tātad jūs vēlaties, lai pievienotu to, iespējams, šeit, jo ja izmērs is--
ja tie visi ir pilns, jūs vēlaties pievienot to tieši šeit, vai ne?
>> Un tā tas ir, bet ļoti, ļoti vienkāršs, ne gluži vienmēr ir pareizs
jo galvenā atšķirība starp rindā un kaudze
ir tā, ka rinda var faktiski manipulēt
tā, ka galvas izmaiņas atkarībā no tā, kur jūs vēlaties
sākums jūsu kija sākt.
Un kā rezultātā, savu asti ir arī mainīsies.
Un tā to apskatīt šis kods tieši tagad.
Kā jūs guys uzdeva arī izrakstīt uz viktorīnu, Enqueue.
Varbūt mēs runājam caur kāpēc atbilde bija, kas tas bija.
>> Es nevarēju gluži fit šo līniju par vienu, bet būtībā šis gabals koda
būtu vienā līnijā.
Pavadīt, piemēram, 30 sekundes.
Veikt apskatīt, un redzēt, kāpēc tas ir tā, ka tas ir.
>> Ļoti, ļoti līdzīga struktūrai, ļoti, ļoti līdzīga struktūra kā iepriekšējais
kaudze izņemot varbūt viena līnija kodu.
Un ka vienā rindā kodu nosaka funkcionalitāti.
Un tas tiešām diferencē rinda no skursteņiem.
>> Ikviens vēlas pieņemt stab izskaidrot, kāpēc jūs esat
saņēmu šo sarežģīto lieta šeit?
Mēs redzam atgriešanos mūsu brīnišķīgs draugs modulis.
Kā jūs guys drīz nāks atzīt programmēšanā,
gandrīz jebkurā laikā jums ir nepieciešams kaut ko wrap ap kaut ko,
modulis būs veids, kā to izdarīt.
Tātad, zinot, ka tas kāds vēlas mēģināt izskaidrot šo rindiņu kodu?
Jā, visas atbildes akceptēts un laipni.
Mērķauditorija: Vai jūs runājat ar mani?
ANDI PENG: Jā.
Mērķauditorija: Ak, nē sorry.
ANDI PENG: Labi, tāpēc pieņemsim staigāt pa šo kodu.
Tātad, ja jūs mēģināt pievienot kaut uz rindā,
jaukā gadījumā, ja galva notiek būt tieši šeit, tas ir ļoti viegli mums
tikai iet uz beigām ievietot kaut ko, vai ne?
Bet viss punkts rindā ir ka galva faktiski var dinamiski
mainīties atkarībā no tā, kur mēs gribu sākums mūsu taustiņu, lai būtu,
un kā tāda, astes ir arī mainīsies.
>> Un tā iedomāties, ka šis nebija rindā, bet gan tas bija rinda.
Pieņemsim, ka galva ir tepat.
Teiksim mūsu rinda izskatījās šādi.
Ja mēs vēlējāmies novirzīt kur sākums līnijas ir,
teiksim mēs pārvietoti galvu Tādā veidā un izmēri šeit.
>> Tagad mēs vēlamies pievienot kaut ko šī rinda, bet, kā jūs guys var redzēt,
tas nav tik vienkārši, kā tikai pievienot visu, kas pēc izmēra
jo tad mēs izsīkšanai robežas mūsu faktiskās masīva.
Kur mēs gribam patiešām pievienot šeit.
Tas ir skaistums rindā ir tas, ka pie mums, tas vizuāli
izskatās, ka līnija iet kā šis, bet, kad saglabāti datu struktūras,
Viņi to kā, piemēram, ciklu.
Tā veida wraps ap uz priekšu, tādā pašā veidā
ka līnija var arī wrap apkārt atkarībā kur jums
gribu rindas sākumā būt.
Un tāpēc, ja mēs ņemam skatīties uz leju šeit, pieņemsim
teikt, mēs vēlējāmies, lai izveidotu funkcija sauc Enqueue.
Mēs vēlējāmies, lai pievienotu int n vērā, ka q.
Ja q.size q-- mēs saucam, ka mūsu datiem structure-- ja mūsu queue.size nav
vienāda ar jaudu vai ja tas ir mazāk nekā jauda,
q.strings ir masīvs mūsu q.
Mēs ejam, lai uzstādītu kas vienāds ar q.heads,
kas ir tepat, plus q.size modulis ar jaudu, kas
aplauzt mums atpakaļ šeit apkārt.
>> Tātad šajā piemērā, indeksa no galvas ir 1, vai ne?
No lieluma indekss ir 0, 1, 2, 3, 4.
Tātad, mēs varam darīt 1 plus 4 modulis ar mūsu spējas, kas ir 5.
Ko tas dod mums?
Kas ir indekss, kas nāk no šī?
>> Mērķauditorija: 0.
>> ANDI PENG: 0, kas notiek, ir tepat,
un tāpēc mēs vēlamies, lai varētu ievietot tieši šeit.
Un tā šis vienādojums šeit veida par vienkārši darbojas ar jebkuru numuru
atkarībā no tā, kur jūsu galvas un jūsu izmērs ir.
Ja jūs zināt, ko tie lietas ir, jūs zināt
tieši tur, kur vēlaties ievietot kāds ir pēc jūsu rindā.
Vai tas ir jēga, lai visiem?
>> Es zinu veida smadzenēm teaser jo īpaši tāpēc šis
nāca seku jūsu viktorīnas.
Bet, cerams, visi tagad var saprast
kāpēc šis risinājums vai šis funkcija ir tā, ka tā ir.
Ikviens mazliet skaidrs par šo?
LABI.
>> Un tā nu, ja jums gribēja dequeue, šis
ir, ja mūsu galva būtu novirzot jo, ja mēs būtu dequeue,
mēs neņemiet nost beigas q.
Mēs vēlamies pacelties galvas, vai ne?
Tātad, kā rezultātā vadītājs gatavojas mainīt, un tas ir iemesls, kāpēc, kad jūs ierindod,
tev sekot kur jūsu galvas un jūsu izmērs
ir, lai varētu ievietot pareizajā stāvoklī.
>> Un tad, kad jūs dequeue, Es arī pseudocode to ārā.
Jūtieties brīvi, ja vēlaties mēģināt kodēšanas šo out.
Jūs vēlaties, lai pārvietotu galvu, labi?
Ja es gribēju dequeue, I varētu pārvietot galvu.
Tas būtu galva.
>> Un mūsu pašreizējais izmērs būtu atņemt, jo mēs vairs
ir četri elementi masīva.
Mums ir tikai trīs, un tad mēs gribam atgriezties kāds tika saglabāta iekšā
no galvas, jo mēs vēlamies, lai šī vērtība, kas tik ļoti līdzīgs kaudze.
Tikai jūs lietojat no citā vietā,
un jums ir pārdalīt savu rādītāju uz citu vietu, kā rezultātā.
Loģiski, visi seko?
Liels.
>> Labi, tāpēc mēs esam gatavojas runāt mazliet dziļāk par saistītiem sarakstiem
jo tie būs ļoti, ļoti vērtīgs Jums gaitā šīs nedēļas
psets.
Saistītās saraksti, kā jūs puiši var atcerēties, visi viņi ir
Ir mezgli, kas ir mezgli dažu vērtības gan vērtības un rādītājs
kas ir saistīti kopā šie norādes.
Un tā struktūrai par to, kā mēs izveidot mezglu šeit ir mums
ir int n, kas ir neatkarīgi vērtība veikala vai string n
vai kāds jūs vēlaties to sauc, tad char zvaigzne n.
Struct mezglā zvaigzne, kas ir rādītājs ka jūs vēlaties, lai būtu katrā mezglā,
Jums nāksies ka rādītājs norāda uz nākamo.
Jums ir galva par saistītu sarakstu, kas ir
gatavojas norādīt uz pārējo vērtībām tā tālāk, un tā tālāk
kamēr jūs beidzot beigs.
Un tas pēdējais mezgls ir tikai gatavojas nav rādītājs.
Tas notiek, lai norādītu uz null, un tas ir tad, kad
jūs zināt, jūs esat hit beigas jūsu saistīts saraksta
ir tad, kad jūsu pēdējā rādītājs nenorāda uz neko.
>> Tāpēc mēs esam gatavojas iet mazliet vairāk dziļums par to, kā viens, iespējams, varētu
meklēt saistīts sarakstu.
Atcerieties, kādi ir daži no trūkumi, kas saistīti saraksti
verses masīvu par meklējumiem.
Masīvs jūs varat bināro meklēšanu, bet kāpēc tu nevari darīt, ka saistītajā sarakstā?
>> Mērķauditorija: Tāpēc, ka viņi visi ir saistīti, bet jums nav gluži zināt, kur
[Dzirdams].
>> ANDI PENG: Jā, tieši tāpēc atcerieties ka mirdzums masīva
bija tas, ka mums bija brīvpiekļuves atmiņa, kur
ja es gribēju vērtību no indeksa seši, es varētu vienkārši pateikt indekss sešas,
dod man šo vērtību.
Un tas ir tāpēc, ka bloki ir sakārtoti in pieguļošajā telpā atmiņas
vienā vietā, bet veida saistītu sarakstu
ir nejauši mijas visapkārt, un vienīgais veids, kā jūs varat atrast vienu
ir ar rādītāju, kas stāsta jums adrese, kur, ka nākamajā mezgls ir.
>> Un tā kā rezultātā, vienīgais veids meklēt, izmantojot saistītu sarakstu
ir lineārs meklēšanu.
Jo man nav precīzi zināt, kur 12th vērtība saistīta sarakstā ir,
Man ir, lai šķērsotu veselumu Minētās saistīts saraksta vienu
ar vienu no galvas uz pirmo mezglu, ar otro mezglu, uz trešo mezglu,
galam, līdz es beidzot nokļūt kur šis mezgls es meklēju ir.
Un tā šajā ziņā, meklēt uz saistītā sarakstā vienmēr n.
Tas vienmēr n.
Tas vienmēr ir lineārā laika.
>> Un tā kods, kurā mēs īstenotu šo, un tas
ir mazliet jauna jums puiši, jo jūs puiši nav īsti runājuši par vai kādreiz
redzējis norādes Kā pārlūkot norādes,
tāpēc mēs staigāt pa Tas ir ļoti, ļoti lēni.
Tātad bool meklēt, pa labi, Iedomāsimies mēs gribam
lai izveidotu funkciju sauc meklēšana, kas atgriež patiess
ja jums atrast vērtību iekšpusē saistīts sarakstā, un tas atgriežas viltus citādi.
Mezglu zvaigzne saraksts ir Pašlaik tikai rādītājs
uz pirmo punktu savā saistīts sarakstā.
int n ir vērtība, ka jūs esat meklē šajā sarakstā.
>> Tātad mezgls zvaigzne rādītājs ir vienāds ar sarakstu.
Tas nozīmē, ka mēs esam nosakot un radot rādītāju
uz šo pirmo mezglu iekšpusē saraksta.
Ikvienam ar mani?
Tātad, ja mēs iet atpakaļ šeit, es būtu
inicializēts rādītāju, kas norāda uz vadītājs kāds šis saraksts ir.
>> Un tad, kad jums uz leju šeit, kamēr rādītājs nav vienāds null,
tā ka ir cilpa, kurā mēs esam būs pēc tam šķērso
pārējie mūsu sarakstā, jo to, ko notiek, ja rādītājs ir vienāds null?
Mēs zinām, ka mēs have--
>> Mērķauditorija: [dzirdams]
>> ANDI PENG: Tieši tā, tāpēc mēs zinām, ka mēs esam sasnieguši saraksta, vai ne?
Ja jūs iet atpakaļ šeit, katrs mezgls būtu vērsta uz citu mezglu
un tā tālāk, un tā tālāk līdz jūs hit beidzot
aste jūsu saistīta saraksta kas ir rādītājs, ka tikai
neliecina visur, izņemot nē.
Un lai jūs būtībā zināt, ka Jūsu saraksts joprojām ir tur augšā
līdz rādītājs nav vienāds null jo, kad tas ir vienāds null,
jūs zināt, ka tur ir ne vairāk sīkumi.
>> Tā, ka ir cilpa, kurā mēs esam nāksies faktisko meklēšanu.
Un, ja pointer-- jūs redzat šāda veida bultiņas funkcijas tur?
Tātad, ja rādītāja punktiem līdz n, ja rādītājs pie n ir vienāds vienāds N,
lai tas nozīmē, ka tad, ja rādītājs, ka tu esi
meklē uz beigās katrs mezgls ir faktiski vienāds ar vērtību
jūs meklējat, tad Jūs vēlaties, lai atgrieztos taisnība.
Vārdu sakot, ja jūs esat ar mezglu, kas ir vērtība, ka jūs meklējat,
jūs zināt, ka jūs esat bijis spējīgs veiksmīgi meklēt.
>> Pretējā gadījumā jūs vēlaties iestatīt Jūsu rādītājs uz nākamo mezglu.
Tas ir tas, ko tas līnija šeit dara.
Pointer vienāds rādītāju nākamo.
Ikviens redzēt, kā tas strādā?
>> Un būtībā jūs gatavojas vienkārši traversa visu attiecīgā saraksta
atiestatīt savu rādītāju katru reizi līdz jūs beidzot hit saraksta beigās.
Un jūs zināt, ka nav vairāk mezglus meklēt, izmantojot,
un tad jūs varat atgriezties viltus jo jūs zināt, ka, ak, labi,
ja es esmu bijusi iespēja meklēt caur kopumā saraksta.
Ja šajā piemērā, ja es gribēju meklēt vērtību 10,
un es sāku pie galvas, un Es meklēju visu ceļu uz leju,
un es beidzot saņēmu to, kas rādītājs, kas norāda uz null,
Es zinu, ka, crap, es domāju, 10 nav Šis saraksts, jo es nevarēju atrast.
Un Es beigās saraksta.
Un tādā gadījumā jūs zināt Es esmu gatavojas atgriezties viltus.
>> Pieņemsim, ka mērcēt par mazliet.
Tas būs diezgan svarīgi, lai jūsu PSET.
No tā loģika ir ļoti vienkārša, varbūt sintaktiski tikai to īsteno.
Jūs puiši vēlas, lai pārliecināts, ka jūs saprotat.
Cool.
>> Labi, tā kā mēs būtu Ievietojot mezglus, pa labi,
par sarakstā, jo atceros kādi ir kāda no ieguvumiem
, kam ir saistīts sarakstu versus masīvs ziņā uzglabāšanas?
>> Mērķauditorija: Tas ir dinamisks, tāpēc ir vieglāk, kuri paredzēti,
>> ANDI PENG: Tieši tā, tāpēc tas ir dinamisks, kas
nozīmē, ka tas var paplašināt un sarauties atkarībā no lietotāja vajadzībām.
Un tā, šajā ziņā mums nav vajadzīga tērēt nevajadzīgu atmiņu, jo I
ja es nezinu, cik daudz vērtības es gribu uz veikalu, tas nav jēgas par mani
izveidot masīvu, jo ja es gribu saglabāt 10 vērtības
un es izveidot masīvu 1000, kas ir daudz izšķērdēta atmiņas, kas atvēlēts.
Tieši tāpēc mēs vēlamies izmantot saistīta saraksts, lai varētu dinamiski
mainīt vai sarauties mūsu izmēru.
>> Un tā, kas padara ievietošanu mazliet sarežģītāka.
Tā kā mēs nevaram nejauši piekļūt elementus tā, ka mēs no masīva.
Ja es gribu, lai ievietotu elements uz septīto indeksu,
Es vienkārši var ievietot to uz septīto indeksā.
Uz saistīta sarakstā, tā nav diezgan strādāt tikpat viegli,
un tāpēc, ja mēs vēlējāmies, lai ievietotu viens šeit saistītajā sarakstā,
vizuāli, tas ir ļoti viegli redzēt.
Mēs vienkārši vēlamies, lai ievietotu to turpat, pa labi sākumā saraksta,
uzreiz pēc galvas.
>> Taču veids, kādā mums ir pārdalīt tad norādes ir nedaudz spirālveida
vai, loģiski, tas ir jēga, bet Jūs vēlaties pārliecināties, ka jums ir tas
līdz galam uz leju, jo pēdējā lieta, ko vēlaties
ir pārdalīt rādītāju tā, ka mēs darām šeit.
Ja jums dereference Pointer no galvas līdz 1,
tad visi pēkšņi pārējā jūsu saistīts saraksta
tiek zaudēti, jo jums nav faktiski izveidoja pagaidu neko.
Tas ir norādīja uz 2.
Ja jūs pārdalīt rādītāju, tad pārējā savu sarakstu ir pilnīgi zaudēta.
Tātad jūs vēlaties būt ļoti, ļoti uzmanīgiem šeit
vispirms Uzdot rādītājs no Kāds jums
vēlas ievietot kur jūs vēlaties, un tad jūs
var dereference pārējo savu sarakstu.
>> Tātad tas attiecas uz kur jūs cenšaties ievietot.
Ja vēlaties ievietot pie galvu, ja jūs vēlaties, lai atbildētu šeit,
ja jūs vēlaties, lai ievietotu tajā beigas, labi, beigas es
domāju, jūs vienkārši nav rādītājs, bet tu
vēlaties pārliecināties, ka jums nav zaudēt pārējo savu sarakstu.
Jūs vienmēr vēlaties pārliecināties savu jauno mezgls ir vērsta
uz ko jūs vēlas ievietot,
un tad jūs varat pievienot ķēžu on.
Ikvienam skaidrs?
>> Tas būs viena no reālām problēmām.
Viens no galvenajiem jautājumiem Jums nāksies uz jūsu PSET
ir tas, ka jūs gatavojas izmēģināt, lai izveidotu saistītais sarakstu un ievietot lietas
bet tad tikai zaudēt pārējā jūsu saistīta saraksta.
Un jūs esat būs, piemēram, es nezinu, kāpēc tas notiek?
Un tas ir sāpes iet cauri un meklēt visas savas norādes.
>> Un es garantija jums par šo PSET, rakstīšanas un zīmēšanas šos mezglus out
būs ļoti, ļoti noderīga.
Tātad jūs varat pilnībā izsekot no tā, kur visi jūsu norādes ir,
kas notiek nepareizi, kur visi jūsu mezgli ir,
to, kas jums jādara, lai piekļūtu vai ievietot vai dzēst vai kādu no tiem.
Ikviens labi ar to?
Cool.
>> Tātad, ja mēs vēlējāmies apskatīt kodu?
Ak, es nezinu, vai mēs var redzēt the-- OK, lai
augšpusē galā tas ir, ir funkcija nosaukts kurtuve, kur mēs gribam
ievietot int n uz saistīts sarakstā.
Mēs ejam, lai iet caur šo.
Tas ir daudz kodu, daudz jaunu sintaksi.
Mēs būsim OK.
>> Tātad augšā, kad Mēs vēlamies, lai radītu kaut ko
Ko mums darīt, it īpaši, ja jums gribu to nedrīkst glabāt uz skursteņa
bet kaudzes?
Mēs ejam uz malloc, vai ne?
Tātad mēs spēsim izveidot rādītāju.
Mezglā, rādītājs, jauni Vienāds malloc izmēru mezglu
jo mēs gribam, ka mezglā jāizveido.
Mēs vēlamies summu Atmiņas ka mezgls aizņem
plāno piešķirt par izveide jaunu mezglu.
>> Un tad mēs ejam, lai pārbaudītu to redzēt, ja jaunie vienlīdzīgi vienāds null.
Atcerieties, ko mēs teicām?
Lai ko jūs malloc, Ko ir jūs vienmēr darīt?
Jums vienmēr pārbaudiet, lai redzētu vai vai nav kas ir nulle.
>> Piemēram, ja darba sistēma bija pilnīgi pilna,
ja jums bija ne vairāk atmiņu viss un jūs mēģināt malloc,
tas varētu atgriezties null jums.
Un tā, ja jūs mēģināt to izmantot kad tas tika norādot uz null,
Jūs neesat gatavojas spējīgs piekļūt šai informācijai.
Un tā kā tādu, mēs vēlējāmies, lai pārliecināts, ka ikreiz, kad esat mallocing,
jūs vienmēr pārbaudi, lai noskaidrotu, vai ka atmiņa dota jums ir nulle.
Un, ja tā nav, tad mēs varam virzīties uz ar pārējo mūsu kodu.
>> Tātad mēs ejam sāktu jaunu mezglu.
Mēs darīsim jaunu n ir vienāds ar n.
Un tad mēs esam gatavojas darīt noteikt jaunu rādītāju par jauno
uz nulli, jo tieši tagad mums nav gribu kaut ko, lai tā norādītu uz.
Mums nav ne jausmas, kur tas gatavojas nodot jums,
un tad, ja mēs gribam, lai ievietojiet to pie galvas,
tad mēs varam pārdalīt rādītājs uz galvas.
Vai visi sekot loģikai no tā, kur tas notiek?
>> Visi mēs darām, ir izveidot jaunu mezglu, nosakot rādītāju null,
un pēc tam no jauna piešķirot tas uz galvas, ja mēs
zinu, ka mēs gribam, lai ievietotu to pie galvas.
Un tad galva gatavojas norāda uz šī jaunā mezglā.
Ikvienam OK ar šo?
>> Tātad, tas ir divpakāpju process.
Tev Vispirms piešķiriet ko jūs veidojat.
Uzlikt šo rādītāju uz atsauces, un tad jūs
var veida izlietota pirmais rādītājs
un norādīt to uz jauno mezglu.
Lai kur jūs vēlaties, lai to ievietotu, ka loģika gatavojas rīkot taisnība.
>> Tas ir veids, piemēram, piešķirot pagaidu mainīgie.
Atcerieties, ka jūs esat ieguvuši lai pārliecinātos, ka jums
nezaudē līdzi, ja jūs pārnešana.
Jūs vēlaties pārliecināties, ka jums ir pagaidu mainīgo šāda veida uztur
izsekot, kur šī lieta tiek uzglabāti tā, ka jūs
nezaudē nekādu vērtību laikā līdzīgu messing aptuveni ar to.
>> Labi, tā kods būs šeit.
Jūs guys ieskatieties pēc iedaļas.
Tas būs tur.
>> Tāpēc es domāju, kā tas Tas atšķiras, ja mēs vēlējāmies
ievietot vidū vai beigās?
Vai kāds ir ideja par to, kas ir pseudocode kā loģisku atsauce
ka mēs varētu veikt, ja mēs vēlējāmies lai ievietotu to vidū?
Tātad, ja mēs vēlējāmies, lai ievietotu to pie galva, viss, kas mums jādara, ir izveidot jaunu mezglu.
Mēs noteikti rādītāju minētā jaunu mezglu, lai neatkarīgi no galvas,
un tad mēs noteikti galvu uz jauno mezglu, vai ne?
Ja mēs vēlējāmies, lai ievietotu to vidū no saraksta, kas būtu mums jādara?
>> Mērķauditorija: Tas vēl būtu būt līdzīgs process
līdzīgu piešķirot rādītāju un tad piešķirot šo rādītāju,
bet mēs būtu, lai atrastu tur.
>> ANDI PENG: Tieši tā, lai tieši tas pats process, izņemot tevi
ir, lai atrastu, kur tieši jūs vēlaties, ka jaunais rādītājs iedziļināties,
Tātad, ja es gribu ievietot vidū saistīta list-- OK,
pieņemsim, ka ir mūsu saistīts saraksts.
Ja mēs gribam, lai ievietotu to tieši šeit, mēs spēsim izveidot jaunu mezglu.
Mēs ejam, lai malloc.
Mēs ejam, lai izveidotu jaunu mezglu.
Mēs ejam, lai piešķirtu rādītājs šajā mezglā šeit.
>> Bet problēma, kas atšķiras no kur galva ir
ir tā, ka mēs zinājām, tieši kur galva ir.
Tas bija labi pie pirmā, vai ne?
Bet šeit mēs esam ieguvuši, lai sekotu par to, kur mēs esam ievietošanas.
Ja mēs ievietojot mūsu mezglu šeit, mēs esam ieguvuši
lai pārliecinātos, ka viens iepriekšējā uz šo mezglu
ir viens, ka reassigns rādītāju.
Tātad jums ir sava veida sekot divām lietām.
Ja jums sekot līdzi, kur tas mezgls pašlaik tiek ievietošanas.
Jums ir arī izsekot, kur iepriekšējais mezglā, ka jūs meklējat pie
bija arī tur.
Ikviens labi ar to?
LABI.
>> Kā par ievietojot beigām?
Ja es gribēju, lai to pievienotu here-- ja es gribēju lai pievienotu jaunu mezgla līdz beigām saraksta,
kā varētu man iet par darot, ka?
Mērķauditorija: Tātad šobrīd, tad pēdējais norādīja uz null.
ANDI PENG: Jā.
Tieši tā, tāpēc tas viens Pašlaik tiek norādīts zināt,
un tāpēc es domāju, ka šajā ziņā, tas ir ļoti viegli pievienot līdz beigām saraksta.
Viss, kas Jums jādara, ir noteikt to vienāds ar spēku, tad uzplaukums.
Turpat, ļoti viegli.
Ļoti vienkārši.
>> Ļoti līdzīgs galvu, bet loģiski tevi
vēlaties pārliecināties, ka pasākumi Jūs lietojat uz darot kādu no šo,
jūs pēc līdzi.
Tas ir ļoti viegli, jo pa vidu Jūsu kodu, nokļuvuši uz,
Ak, es esam ieguvuši tik daudz norādes.
Es nezinu, kur kaut kas ir vērsta uz.
Es pat nezinu, kas mezgls es esmu par.
Kas notiek?
>> Atpūsties, nomierināties, veikt dziļu elpu.
Izdarīt savu saistīts sarakstu.
Ja jūs sakāt, es zinu, kur tieši Man vajag, lai ievietotu to vērā
un es zinu, kā tieši to pārdalīt manu norādes, daudz, daudz vieglāk attēlu
out-- daudz, daudz vieglāk nav pazust bugs jūsu kodu.
Ikvienam OK ar šo?
LABI.
>> Tāpēc es domāju, koncepciju, ka mēs neesam tiešām runāja par agrāk tagad,
un es domāju, jūs, iespējams, nebūs sastopas daudz yet--
tas ir sava veida uzlabotas concept-- ir tā, ka mums tiešām ir dati
struktūra sauc divkārt saistīts sarakstu.
Tātad, kā jūs guys var redzēt, viss, ko mēs darām, ir radīt
faktisko vērtību, papildus rādītājs par katru no mūsu mezgliem
kas arī norāda uz iepriekšējo mezglu.
Tātad ne tikai mums ir mūsu mezglus norāda uz nākamo.
Viņi arī norāda uz iepriekšējo.
Es esmu gatavojas ignorēt šos divus tiesības tagad.
>> Tātad jums ir ķēdes kas var pārvietoties abos virzienos,
un tad tas ir mazliet vieglāk loģiski sekot līdzi.
Tāpat kā šeit, tā vietā, lai sekotu, oh, es
ir jāzina, ka šis mezgls ir viens, ka man ir pārdalīt,
Es varu tikai iet šeit un tikai pull iepriekšējā.
Tad es zinu, kur tieši tas ir, un tad jūs
nav traversa kopums saistītajā sarakstā.
Tas ir mazliet vieglāk.
>> Bet, kā, piemēram, jums ir divkārt summu norādes,
tas ir dubultā atmiņas apjomu.
Tas ir daudz norādes, lai sekotu.
Tas ir mazliet sarežģītāka, bet tas ir mazliet vairāk lietotājam draudzīgu atkarībā
par to, ko jūs mēģināt paveikt.
>> Tātad šāda veida datu struktūra pilnīgi pastāv,
un struktūra ir ļoti, ļoti vienkāršs izņemot visi jūs, kam ir,
nevis tikai rādītāju uz nākamo, jums ir arī rādītāju uz iepriekšējo.
Tas ir viss, atšķirība bija.
Ikviens labi ar to?
Cool.
>> Labi, tāpēc tagad es esmu lai tiešām tērēt iespējams
piemēram, 15 līdz 20 minūtes vai kupola no pārējā reizi sadaļā
runājot par hash tabulas.
Cik daudzi no jums, puiši lasījis pset5 spec?
Labi, labi.
Tas ir lielāks nekā 50% no normāli.
Ir labi.
>> Tātad, kā jūs guys redzēs, tu esi izaicinājums pset5
būs īstenot vārdnīca kur jūs ielādēt vairāk nekā 140,000 vārdus
ka mēs jums un pareizrakstības pārbaude tā pret visu tekstu.
Mēs jums izlases gabalus literatūru.
Mēs jums Odyssey.
Mēs jums Iliāda.
Mēs jums Austin Powers.
>> Un jūsu uzdevums būs pareizrakstības pārbaude
katru vārdu visu Šo vārdnīcu
būtībā ar mūsu pareizrakstības pārbaudītājs.
Un tāpēc tur ir dažas detaļas izveidot šo PSET,
Vispirms jūs vēlaties būt spējīgs reāli ielādēt
visi vārdi savā vārdnīcu, un tad jūs
vēlas, lai varētu pareizrakstības pārbaude visi no tiem.
Un tā kā tāda, jūs gatavojas pieprasīt datu struktūra, kas var izdarīt ātri
un efektīvi un dinamiski.
>> Tāpēc es domāju, ka visvieglāk veids, kā to darīt, jums
iespējams izveidot masīvu, labi?
Vieglākais veids, uzglabāšanas ir jums var izveidot masīvu 140000 vārdiem
un vienkārši novietot tos visus tur un tad šķērso tos ar bināro meklēšanu
vai izvēles vai not-- žēl, ka ir šķirošana.
Jūs varat šķirot tos un pēc tam tos traversa ar bināro meklēšanu vai vienkārši lineāro meklēšanu
un tikai pēdējie vārdi, bet aizņem lielu atmiņas apjomu,
un tas nav ļoti efektīva.
>> Un tāpēc mēs esam gatavojas sākt runājam par veidiem, kā padarīt
Mūsu darba laiks efektīvāku.
Un mūsu mērķis ir iegūt konstante laiks, kad
tas ir gandrīz kā masīvu, kur Jums ir momentānā piekļuvi.
Ja es gribēju, lai meklētu kaut ko, Es gribu, lai varētu vienkārši,
boom, atrast to tieši, un izvelciet to ārā.
Un tā struktūru, kurā mēs būsim kļūst ļoti tuvu
lai varētu piekļūt konstante laiks, šis Svētais Grāls
programmēšanā no konstante laiks tiek saukts par hash tabulu.
Un tā Dāvids iepriekš minēja [Dzirdams] mazliet lekciju,
bet mēs ejam, lai patiešām nirt dziļi šajā nedēļā
par kādu, kas ir par kā hash tabulu darbi.
>> Tātad tā, ka hash galda darbi, piemēram,
ja es gribēju, lai saglabātu ķekars vārdiem, ķekars vārdiem angļu valodā,
Es teorētiski varētu likt banānu, ābolu, kivi, mango, pāris,
un melones visi uz tikai masīvu.
Viņi visi varētu iederēties un būtu atrast.
Tas lūdzu būt sava veida sāpes pārlūkot un pieejamību,
bet vieglāk veids, kā to izdarīt, ir ka mēs varam radīt faktiski struktūra
sauc hash tabulu, kur mēs hash.
Mums ir visas mūsu atslēgas caur hash funkciju, vienādojums,
kas pārvērš tos visus daži vērtība veida
ka tad mēs varam glabāt uz būtībā masīvs saistīta saraksta.
>> Un tāpēc šeit, ja mēs vēlējāmies uzglabāt angļu vārdiem,
mēs varētu potenciāli vienkārši, man nav zināt, savukārt visus pirmos burtus
uz kādu no vairākiem veida.
Un tā, piemēram, ja es gribēju A būt sinonīms apple--
vai ar indeksu no 0, un B būt sinonīms ar 1,
mēs varam būt 26 ieraksti ka var vienkārši uzglabāt
visi burti no alfabēts, ka mēs sāksim ar.
Un tad mēs varam būt apple pie indeksa 0.
Mēs varam būt banānu pie indeksa 1, melones pie indeksa 2,
un tā tālāk, un tā tālāk.
Un tā, ja es gribēju, lai meklētu mans hash tabulu un piekļuves ābolu,
Es zinu, ābolu sākas ar A, un es zinu, tieši
ka tai ir jābūt, un hash Tabulā indekss 0 tāpēc,
par funkciju iepriekš piešķirts.
>> Tāpēc es nezinu, mēs esam lietotāja programma, kurā
Jums būs jāmaksā ar arbitrarily-- nav patvaļīgi,
ar mēģina pārdomāti domā par labu vienādojumu
lai varētu izplatīties no visas savas vērtības
tādā veidā, tās var viegli piekļūt tas vēlāk ar, piemēram, vienādojumu
ka jums, sevi, zināt.
Tātad tādā ziņā, ja es gribēju doties uz mango, es zinu, ak, tas sākas ar m.
Ir jābūt indeksā 12.
Man nav, lai meklētu caur jebko.
Es zinu exactly-- es varētu tikai iet uz indekss 12. un izvelciet kas ārā.
>> Ikvienam skaidrs, par to, kā hash tabulu funkcija darbojas?
Tas ir sava veida tikai sarežģītāku masīvs.
Tas ir viss, tas ir.
LABI.
>> Tāpēc es domāju, mēs uzskriet šis jautājums par to, kas
notiek, ja jums ir vairākas lietas kas dod jums to pašu indeksu?
Tā teikt, mūsu funkcijas, visu to darīju bija veikt šo pirmo burtu
un pārvērst kas stājas attiecīgais 0 līdz 25 indekss.
Tas ir pilnīgi naudas sodu, ja jums ir tikai viens no katra.
Bet otrais sākat kam ir vairāk, tu esi
nāksies ko sauc sadursme.
>> Tātad, ja es mēģinātu ievietot apglabāt uz hash Tabulā, kas jau ir banānu par to,
to, kas notiks, kad jūs mēģināt ievietot kas?
Sliktas lietas, jo banāns jau pastāv ietvaros indeksā
ka jūs vēlaties, lai saglabātu to.
Berry veida ir līdzīgs, ah, ko man darīt?
Es nezinu, kur iet.
Kā es varu atrisināt šo?
>> Un tā jūs guys būs sava veida redzēt mēs šo delikāta lieta
kur mēs varam veida faktiski izveidot saistīts sarakstu mūsu masīvi.
Un tā vieglākais veids domāt par to,
viss hash tabulā ir masīvs saistītas sarakstus.
Un tā, šajā ziņā, jums ir Šī skaisti masīvs norādes,
un tad katrs rādītājs ir šī vērtība, šajā rādītājā,
faktiski var norādīt uz citām lietām.
Un tāpēc jums ir visi šie atsevišķa ķēdes nāk nost no viena lielā masīva.
>> Un tāpēc šeit, ja es gribēju ievietot ogu,
Es zinu, OK, es esmu gatavojas ievade tas caur manu hash funkciju.
Es esmu gatavojas, lai galu galā ar indeksu 1, un tad es esmu gatavojas, lai varētu būt
tikai mazāks apakškopa šis milzu 140000-vārdu vārdnīca.
Un tad es varu tikai skatīties ar 1/26 no tā.
>> Un tā, tad es varu tikai ievietot ogu vai nu pirms, vai pēc banānu
šajā gadījumā?
Pēc, vai ne?
Un tā jūs gatavojas vēlaties ievietot šo mezglu pēc banānu,
un tāpēc jūs gatavojas ievietot pie astes minētā saistīts sarakstā.
Es esmu gatavojas doties atpakaļ ar šo iepriekšējo slaidu,
Tātad jūs guys var redzēt, kā hash funkcija darbojas.
>> Tātad hash funkcija ir šis vienādojums ka jūs strādājat veida jūsu ieguldījumu
cauri, lai iegūtu visus indekss jūs vēlaties piešķirt to uz.
Un tā, šajā piemērā, viss, ko mēs vēlējāmies darīt bija veikt pirmo burtu,
savukārt, ka uz indeksu, tad mēs var uzglabāt, ka mūsu hash funkciju.
Visi mēs darām šeit ir, mēs esam pārvēršot pirmo burtu.
Tātad keykey [0], ir tikai pirmais burts no kāda stīgu mēs esam, kam,
mēs garāmejot.
Mēs esam konvertējot ka uz augšējo, un mēs atņemot ar lielajiem A,
lai visi, kas dara dod mums vairākas
kurā mēs varam hash savas vērtības uz.
>> Un tad mēs spēsim atgriezties hash moduli izmēru.
Esi ļoti, ļoti uzmanīgiem jo, teorētiski, šeit
Jūsu hash vērtība varētu būt bezgalīgs.
Tā varētu tikai iet tālāk un tālāk un tālāk.
Tā varētu būt daži patiešām, patiešām liela vērtība,
bet tāpēc, ka jūsu hash tabulu, kas esat izveidojis tikai ir 26 indeksu,
Jūs vēlaties pārliecināties, vai jūsu modulusing lai jūs
nav run-- tas ir tas pats lieta kā savu queue--
tā, ka jums nav palaist off apakšā jūsu hash funkciju.
>> Jūs vēlaties, lai wrap to atpakaļ ap vienādi [nedzirdama], ja
jums bija, piemēram, ļoti, ļoti liels vēstuli, jums
nevēlējās, ka, lai ieskriet pie beigām.
Pats šeit, jūs vēlaties, lai pārliecinātos tas nav palaist off beigām iesaiņošana
ap uz augšu tabulā.
Tātad tas ir tikai ļoti vienkārši hash funkciju.
Viss, kas bija, bija jāņem pirmais vēstule kāda mūsu ieejas bija
un pārvērst kas stājas indekss, kas mēs varētu likt mūsu hash tabulu.
>> Jā, un tā kā es teicu iepriekš, tā, ka mēs atrisināt sadursmes
mūsu hash tabulas, kam, Ko mēs saucam, ķēžu.
Tātad, ja jūs mēģināt ievietot vairākus vārdus, kas sākas ar vienu un to pašu,
Jums nāksies vienu hash vērtību.
Avokado un ābolu, ja esat palaist to caur mūsu hash funkciju,
gatavojas sniegt jums tas pats numurs, skaits 0.
Un tā kā mēs atrisināt, kas ir ka mēs varam faktiski veida saistīt tos
kopā ar saistītiem sarakstiem.
>> Un tā šajā ziņā, jūs guys var redzēt veida
par to, kā datu struktūras, kas mēs esam bijuši nosakot iepriekš
kā rozīņu saistīta saraksta veida no var sanākt kopā vienā.
Un tad jūs varat izveidot tālu efektīvāku datu struktūras
ka var rīkoties lielākas summas dati, kas dinamiski mainīt atkarībā
no jūsu vajadzībām.
Ikvienam skaidrs?
Ikvienam veida skaidrs par to, kas notiek šeit?
>> Ja es gribēju insert-- ko ir auglis, kas sākas ar, es nezinu,
B, izņemot ogu, banānu.
>> Mērķauditorija: Blackberry.
>> ANDI PENG: Blackberry, kazenes.
Kur kazenes aiziet šeit?
Nu, mēs faktiski neesam sakārtoti Tas vēl, bet teorētiski
ja mēs vēlējāmies, lai šis alfabētiskā secībā,
kur vajadzētu kazenes doties?
>> Mērķauditorija: [dzirdams]
>> ANDI PENG: Tieši tā, pēc šeit, vai ne?
Bet tā kā tas ir ļoti grūti reorder-- Es domāju, tas ir atkarīgs no jums puiši.
Jūs guys var pilnīgi īstenot neatkarīgi vēlaties.
Efektīvāka kā to izdarīt, varbūt
būtu sakārtot savu saistīta uzskaitīt uz alfabētiskā secībā,
un tad, kad jūs esat Ievietojot lietas, jūs vēlaties
jābūt pārliecinātiem, lai ievietotu tos uz alfabēta
tā, ka tad, kad jūs esat mēģināt meklēt tos,
Jums nav, lai šķērsotu visu.
Jūs zināt, kur tieši tas ir, un tas ir vieglāk.
>> Bet, ja jūs veida ir lietas mijas nejauši,
jūs joprojām nāksies lai šķērsotu to anyways.
Un tāpēc, ja es gribēju tikai ievietot kazenes šeit
un es gribēju, lai meklētu tā, es zinu, ak, kazenes
jāsāk ar indeksu 1, tāpēc es zināt uzreiz tikai meklēt pēc 1.
Un tad es varu veida traversa saistīts sarakstu
kamēr man uz Blackberry, un then-- yeah?
>> Mērķauditorija: Ja jūs mēģināt create-- Es domāju, piemēram, tas ir ļoti vienkāršs hash
funkcija.
Un, ja mēs vēlējāmies darīt vairāki slāņi, ka, piemēram,
Labi, mēs vēlamies, lai atdalītu vērā tāpat kā visiem alfabēta burtiem
un tad atkal patīk citu komplektu no alfabēta burtiem iekšienē ka,
mēs liekot kā hash galda ietvaros hash tabulu,
vai kā funkcija funkcija?
Vai ir that--
>> ANDI PENG: Tātad jūsu hash function-- savu hash tabulu
var būt tik liela, kā jūs to vēlaties.
Tātad šajā ziņā, es domāju, tas bija ļoti viegli, ļoti
vienkārši man tikai sava balstīta uz vēstulēm pirmo vārdu.
Un tā tur ir tikai 26 iespējas.
Es varu tikai iegūt 26 opcijas 0 līdz 25, jo tie var tikai
sākt no A līdz Z. Bet, ja jūs vēlētos pievienot, iespējams, vairāk sarežģītību
vai ātrāks palaist laiku, lai jūsu hash tabulu, jūs absolūti
var darīt visu veidu lietas.
Jūs varat izveidot savu vienādojums, kas dod jums
vairāk sadalījums jūsu vārdus, tad, kad jūs meklēt,
tas būs ātrāk.
>> Tas ir pilnībā atkarīgs no jums puiši kā jūs vēlaties, lai īstenotu to.
Domājiet par to kā tikai spaiņos.
Ja es gribēju, lai būtu 26 spaiņi, es eju
kārtot lietas šajās spaiņiem.
Bet es esmu nāksies ķekars sīkumi katrā spainis,
Tātad, ja jūs vēlaties, lai padarītu to ātrāku un efektīvāku,
man ir simts kausi.
>> Bet tad jums ir izdomāt veids, kā sakārtot lietas tā, ka tie ir
pareizi spainī viņiem vajadzētu būt.
Bet tad, kad jūs faktiski vēlaties apskatīt šo kausu,
tas ir daudz ātrāk, jo tur ir mazāk sīkumi katrā spainī.
Un tā, jā, tas ir patiesībā triks, lai jūs guys pset5
ir tas, ka jūs būsiet apstrīdēja tikai radītu
kāds ir visefektīvākais funkciju jūs varat iedomāties, ka
spēj uzglabāt un pārbaudīt šīs vērtības.
>> Pilnībā atkarīgs no jums puiši tomēr vēlaties to darīt,
bet tas ir patiešām labs punkts.
Ka veida loģika jums gribu sākt domāt par
ir labi, kāpēc ne es padarīt kausi.
Un tad man ir meklēt mazāk lietas, un tad varbūt es
ir atšķirīgs jaucējfunkciju.
>> Jā, tur ir daudz veidi, kā to izdarīt PSET, daži ir ātrāk nekā citi.
Es esmu pilnīgi gatavojas tikai redzēt, kā ātrs bija ātrākais jums puiši būs
varēs saņemt savu funkciju uz darbu.
OK, visi labi uz ķēžu indeksu aprēķināšanas un hash tabulas?
Tas patiesībā tāpat ir ļoti vienkāršs koncepciju, ja jūs domājat par to.
Viss, kas ir, ir kāds, kas atdala Jūsu izejvielas urnās,
šķirojot tos, un pēc tam meklējot saraksti, ka tur ir saistīts ar.
>> Cool.
Labi, tagad mums ir cita veida Datu struktūra, kas sauc koks.
Iesim tālāk un runāt par mēģinājumiem kas ir ievērojami atšķiras,
bet tās pašas kategorijas.
Būtībā, viss koks ir vietā organizēt datu lineārā veidā
ka hash tabulu does-- tevi zinu, tas ir got top un augšupēju
un tad jūs veida saistīt nost no it-- a koks ir top, kas jūs zvanāt sakni,
un tad tas ir lapas viss ap to.
>> Un tā viss, kas jums šeit ir tikai top mezglā
kas norāda uz citiem mezgliem, ka punkti vairāk punktiem, un tā tālāk un tā tālāk.
Un tāpēc jums vienkārši ir sadalīšanas filiāles.
Tas ir tikai atšķirīgs veids, kā organizēt dati, un tāpēc mēs to saucam koks,
jūs guys just-- tas ir tikai modelēts, lai izskatās kā koks.
Tieši tāpēc mēs to saucam koki.
>> Hash tabula izskatās tabulā.
Koku tikai izskatās kā koks.
Viss tas ir, ir atsevišķs veids, kā organizēt mezglus
atkarībā no tā, kādas ir jūsu vajadzības.
>> Tātad jums ir saknes un tad jums ir lapas.
Tā, ka mēs varam īpaši Padomā par to ir bināro koku,
binārs koks ir tikai īpaša veida koks
kur katrs mezgls tikai punkti lai, pie max, divi citi mezgli.
Un tāpēc šeit jums ir atšķirīgs simetrija ciltskokā
kas padara to vieglāk veida meklēt pie kādas vērtības jūs esat, jo tad jūs
ir vienmēr pa kreiso vai labo.
Tur nekad kā kreisās trešdaļu no kreiso vai ceturtais no kreisās puses.
Tas ir tikai jums ir pa kreisi un tiesības un jūs varat meklēt kādu no šiem diviem.
Un tad kāpēc tas ir noderīgs?
Tā, ka tas ir noderīgi ir, ja jūs meklējat
meklēt, izmantojot vērtības, vai ne?
Nevis īstenošanas bināro meklēt kļūdas masīvs,
ja jūs vēlaties, lai varētu ievietot mezglu un atņemt mezglu pēc vēlēšanās un arī
saglabāt meklēšanu jaudas bināro meklēšanu.
Tātad šādā veidā, mēs esam sava veida tricking-- atceros, kad mēs
teica saistīti saraksti nevaru bināro meklēšanu?
Mēs esam veida izveidojot datu struktūra ka triku, ka par darba.
>> Un tāpēc, ka saistīti saraksti ir lineāra, tie tikai saistīt viens pēc otra.
Mēs varam veida ir citāda veida norādes
kas norāda uz dažādu mezglu kas var palīdzēt mums ar meklēšanu.
Un tāpēc šeit, ja es gribēju ir bināro meklēšanas koku,
Es zinu, ka mans vidū ja 55.
Es esmu tikai gatavojas, lai radītu, ka kā manu vidū, kā mana saknes,
un tad es esmu nāksies vērtībām spin off no tā.
>> Tātad šeit, ja es esmu gatavojas, lai meklētu vērtība 66, es var sākt 55.
Tas ir 66 lielāks par 55?
Jā, tas ir, tāpēc es zinu, es mus meklēt i n tiesības rādītājs par šo koku.
Es eju uz 77.
OK, ir 66 mazāks par vai lielāks par 77?
Tas ir mazāk, nekā, lai jūs zināt, ak, ka ir jābūt kreisi mezglā.
>> Un tāpēc šeit mēs esam sava veida konservēšana visas lielas lietas par blokiem
tā, piemēram, dinamisko izmēru maiņas objektu, kas ir
iespēja ievietot un dzēst pēc vēlēšanās, neraizējoties par fiksētā
daudz vietas.
Mēs joprojām saglabāt visus šie brīnišķīgi lietas
bet arī spēja saglabāt log un meklēt laiku bināro meklēšanu
ka mēs bijām tikai iepriekš iespēja iegūt frāzi.
>> Cool datu struktūra, sava veida sarežģīti īstenot, mezglu.
Kā jūs varat redzēt, viss, ir struct mezglā
ir tas, ka jums ir pa kreisi un tiesības rādītājs.
Tas ir viss, tas ir.
Tātad, nevis tikai kam ir X vai iepriekšējais.
Jums ir pa kreisi vai pa labi, un tad Jūs varat veida saistīt tos kopā
tomēr jums tā izvēlēties.
>> Labi, mēs esam patiesībā notiek lietojiet tikai dažas minūtes.
Tātad mēs ejam, lai atgrieztos šeit.
Kā es iepriekš teicu, Es veida paskaidroja
loģiku, kā mēs varētu meklēt caur šo.
Mēs ejam, lai mēģinātu pseudocoding šo, lai redzētu
ja mēs varam veida piemēro pati loģika bināro meklēšanu
uz cita veida datu struktūra.
Ja jūs guys vēlaties veikt, piemēram, pāris minūtes, lai tikai domāt par to.
LABI.
Labi, es esmu gatavojas faktiski tikai dod jums the-- nē,
mēs runājam par pseudocode pirmās.
Tātad vai kāds vēlaties dot stab pie kāda
pirmā lieta, ko vēlaties darīt, ja jūs, sākot out meklēšana ir?
Ja mēs meklējam vērtība no 66, kas ir
pirmā lieta, ko mēs vēlamies darīt, ja mēs vēlamies, lai bināro meklēt šo koku?
>> Mērķauditorija: Jūs vēlaties, lai izskatās labi un skatīties pa kreisi un redzēt [dzirdams]
lielāks skaits.
>> ANDI PENG: Jā, tieši tā.
Tātad jūs gatavojas apskatīt jūsu saknes.
Ir daudz veidu, jūs varat zvanīt tā, jūsu mātes mezglu cilvēki saka.
Es gribētu teikt, saknes, jo tas ir tāpat kā ar koka saknēm.
Jūs esat gatavojas apskatīt saknes mezgla, un jūs esat
gatavojas redzēt, ir 66 lielāks nekā vai mazāk nekā 55.
Un, ja tas ir lielāks nekā, labi, tas ir lielāka nekā, ja mēs gribam, lai izskatās?
Ja mēs vēlamies, lai meklētu tagad, vai ne?
Mēs vēlamies, lai meklētu Labajā pusē no šo koku.
>> Tātad mums ir, ērti A rādītājs, kas norāda uz labo pusi.
Un tā, tad mēs varam noteikt mūsu jauno sakne būt 77.
Mēs varam tikai iet, lai kur rādītājs ir vērsta.
Nu, ak, šeit mēs sākam pie 77, un mēs varam tikai
izdarītu rekursīvi atkal un atkal.
Tādā veidā, jūs veida no ir funkcija.
Jums ir veids, kā meklēt, kas jums var tikai atkārtot atkal un atkal un atkal,
atkarībā no tā, kur jūs vēlaties meklēt kamēr jūs beidzot nokļūt ar vērtību
ka jūs meklējat.
Jēga?
>> Es esmu par, lai parādītu jums faktiskais kodu, un tas ir daudz kodu.
Nav nepieciešams, lai ķēms.
Mēs runājam caur to.
>> Patiesībā, nē.
Tas bija tikai pseudocode.
Labi, ka bija tikai pseudocode, kas ir mazliet komplekss,
bet tas ir pilnīgi naudas sodu.
Ikvienam pēc kopā šeit?
Ja saknes ir nulle, atgriešanās nepatiess, jo tas nozīmē, ka
Jums pat nav neko tur.
>> Ja saknes n ir vērtība, tādēļ, ja tas notiek, ir viens jūs meklējat,
tad jūs gatavojas atgriezties true jo jūs zināt, ka jums atrast to.
Bet, ja vērtība ir mazāka nekā sakne n, tu esi
dodas meklēt kreiso bērns vai kreiso lapu,
ko jūs vēlaties, lai izsauktu to.
Un, ja vērtība ir lielāka nekā saknes, jūs gatavojas meklēt pareizo koku,
tad vienkārši palaist funkciju izmantojot meklēšanas vēlreiz.
>> Un, ja sakne ir nulle, ka nozīmē, ka jūs esat sasnieguši?
Tas nozīmē, ka jums ir ne Vairāk lapas, lai meklētu,
tad jūs zināt, ak, es uzminēt tas nav šeit
jo, kad es esmu paskatījos caur viss, un tas nav šeit,
tas tikai varētu būt šeit.
>> Vai tas ir jēga, lai visiem?
Tātad, tas ir tāpat kā bināro meklēšanu konservēšana spējas saistītas sarakstus.
Atdzesē, un tāpēc otrais tips Datu struktūras jūs puiši
var mēģināt īstenošanas jūsu PSET, Jums tikai jāizvēlas vienu metodi.
Bet varbūt alternatīva metode hash tabulā ir tas, ko mēs saucam trie.
>> Viss trie ir ir īpaša veida koks, kas
ir vērtības, kas iet uz citām vērtībām.
Tāpēc tā vietā, bināro koks tajā nozīmē, ka tikai viens
lieta var norādīt uz diviem, jūs varat būt viena lieta norāda uz daudzām, daudzām lietām.
Jūs būtībā ir masīvi iekšpusē, kas jūs glabājat
norādes, kas norāda uz citām masīvi.
>> Tātad mezgla, kā mēs definētu trie
mēs vēlamies, lai būtu Būla, c vārdu, vai ne?
Tātad mezgls ir Būla piemēram, patiess vai nepatiess,
vispirms pie galvas ka masīvs, ir šis vārds?
Otrkārt, jūs vēlaties, lai būtu norādes lai neatkarīgi pārējie no viņiem ir.
Mazliet komplekss, nedaudz abstrakts, bet Es paskaidrošu, ko tas viss nozīmē.
>> Tātad šeit, augšā, ja jums ir masīvs deklarēta jau,
mezglu, kur jums ir Būla vērtība glabājas pie priekšpusē
kas stāsta jums tas ir vārds?
Vai tas nav vārdu?
Un tad jums ir pārējā jūsu masīvs, ka
faktiski uzglabā visus iespējas, ko tas varētu būt.
Tātad, piemēram, piemēram, augšpusē esat
Pirmā lieta, kas saka patiess vai nepatiesa, jā vai nē, tas ir vārds.
>> Un tad jums ir no 0 līdz 26 burti, ka jūs varat uzglabāt.
Ja es gribēju, lai meklētu šeit par nūja, es iet uz augšu
un es meklēt B. Es uzskatu B manā masīvs, un tāpēc es zinu, OK, ir B vārdu?
B nav vārdu, lai tādējādi Man ir jātur meklēšanu.
Es aiziet no B, un es ceru uz rādītājs, ka B norāda uz
un es redzu vēl vienu masīvu informācijas, pats struktūra, kas mums bija pirms tam.
>> Un here-- oh, nākamais vēstuli [dzirdams] ir A.
Tātad mēs skatāmies šajā masīvā.
Mēs atrast astoto vērtību, un tad mēs skatāmies, lai redzētu, ak,
hey, ir tas, ka vārdu, ir B-A vārdu?
Tas nav vārds.
Mēs esam ieguvuši, lai saglabātu meklējat.
>> Un tā, tad mēs skatāmies uz to, kur rādītājs ir A,
un tas norāda uz citā veidā kas mums ir vairāk vērtību uzglabā.
Un galu galā, mēs nokļūt B-A-T, kas ir vārds.
Un tā nākamreiz paskatās, jūs gatavojas
ir, ka pārbaude, jā, Šī Būla funkcija ir taisnība.
Un tā šajā ziņā mēs esam sava veida , kam ir koks ar masīviem.
>> Tātad jūs varat veida meklēt leju.
Nevis sajaukšanai funkciju un piešķirot vērtības, kas saistītas sarakstā,
Jūs varat vienkārši īstenot pētniecības trie kas meklē downwords.
Tiešām, tiešām sarežģīti sīkumi.
Nav viegli domāt par to, jo es esmu kā spļaut tik daudz datu struktūras out
pie jums, bet tas visiem veida saprast, kā darbojas loģika šo?
>> OK, atdzesē.
Tā B-A-T, un pēc tam jūs gatavojas meklēt.
Nākamreiz, kad ejam lai redzētu, ak, hey, tā ir taisnība,
Tāpēc es zinu, tas ir vārds.
>> Pats par zoo.
Tātad, šeit ir lieta tieši tagad, ja mēs vēlējās, lai meklētu zoo, tieši tagad,
Pašlaik zoo nav vārds mūsu vārdnīcā
jo, kā jūs guys var redzēt, Pirmkārt, ka mums ir Būla
return true ir beigās zoom.
Mums ir Z-O-O-M.
>> Un tāpēc šeit, mums nav tiešām ir vārds, zoo, mūsu vārdnīcā
jo šī rūtiņa nav atzīmēta.
Tātad dators nav zina, ka zoo ir vārds
jo tā, ka mēs esam uzglabāt to, tikai zoom šeit
patiesībā ir Būla vērtība kas ir bijis ieslēgts taisnība.
Tātad, ja mēs gribam, lai ievietotu Vārds, zoo, mūsu vārdnīcā,
Kā mēs iet par darot, ka?
Kas mums jādara, lai pārliecinātos, ka mūsu dators zina, ka Z-O-O ir vārds
un nav pirmais vārds ir Z-O-O-M?
>> Mērķauditorija: [dzirdams]
>> ANDI PENG: Tieši tā, mēs vēlaties pārliecināties, ka tas
šeit, lai Būla vērtība ir pārbauda off, ka tā ir taisnība.
Z-O-O, tad mēs ejam, lai pārbaudītu, ka, lai mēs precīzi zinātu, hey, zoo ir vārds.
Es esmu gatavojas pateikt dators, kas tas ir vārds tik
ka tad, kad dators pārbaudes, tā zina, ka zoodārzs ir vārds.
>> Jo atcerēties visus šos datus konstrukcijas, tas ir ļoti viegli mums
teikt, ak, bat ir vārds.
Zoo ir vārds.
Zoom ir vārds.
Bet, ja jūs veidot to, dators nav ne jausmas.
>> Tātad jums ir pateikt to tieši kurā brīdī tas ir vārds?
Kurā brīdī tas nav vārdu?
Un kurā brīdī es varu nepieciešams meklēt lietas,
un kurā brīdī man jāiet tālāk?
Ikvienam skaidrs, ka?
Cool.
>> Un tā tad nāk problēma Kā mēs
iet par kaut ko ievietojot tas tiešām nav tur?
Tātad pieņemsim tikai teikt, ka mēs vēlamies, lai ievietotu vārds, vanna, mūsu TRIE.
Kā jūs guys var redzēt, piemēram, šobrīd viss, kas mums ir tagad, ir B-A-T,
un šī jaunā datu struktūra tur bija pinte ka
norādīja uz nulli, jo mēs pieņemam ka, ak, tur nav vārdu pēc B-A-T,
Kāpēc mums ir nepieciešams, lai saglabātu ņemot lietas pēc tam T.
>> Bet problēma rodas, ja mēs jums vēlas, lai ir vārds, kas nāk pēc tam, kad
T s.
Ja jums ir vanna, tu esi gatavojas vēlaties H tiesības.
Un tā kā mēs esam gatavojas darīt, ir mēs spēsim izveidot atsevišķu mezglu.
Mēs esam ne piešķirt neatkarīgi no summas atmiņas par šo jauno masīva,
un mēs spēsim pārdalīt norādes.
>> Mēs ejam, lai piešķirtu H, Pirmkārt, tas null,
mēs spēsim atbrīvoties.
Mēs ejam, lai būtu punkts H leju.
Ja mēs redzam H, mēs to gribam doties kaut kur citur.
>> Jo šeit, mēs varam pēc tam pārbaudīt off jā.
Ja mēs hit H pēc T, oh, tad mēs zinām, ka tas ir vārds.
Būla gatavojas atgriezties true.
Ikvienam skaidrs, par to, kā tas notika?
LABI.
>> Tātad, būtībā, visas šīs datu struktūras
ka mēs esam izgājuši vairāk nekā šodien, es esmu gājusi pār viņiem tiešām, tiešām ātri
un nevis uz daudz detaļa, un tas ir OK.
Kad sākat messing ar to, jūs būsiet
sekotu, kur visas norādes ir,
to, kas notiek jūsu datu struktūras, un tā tālāk.
Tie būs ļoti noderīga, un tas ir atkarīgs no jums
puiši, lai pilnīgi noskaidrotu, kā Jūs vēlaties, lai īstenotu lietas.
>> Un tā pset4, no 5-- oh, tas ir nepareizi.
Pset5 ir pārrakstīšanās.
Kā jau teicu iepriekš, jūs gatavojas, tiklīdz atkal, lejupielādēt avota kodu no mums.
Tur būs trīs galvenās lietas jums tiks lejupielādi.
Jūs lejupielādēt vārdnīcas, ņēmējiem, un teksti.
>> Visas šīs lietas ir ir nu vārdnīcas vārdi
ka mēs vēlamies, lai jūs, lai pārbaudītu vai tests informācijas
ka mēs vēlamies, lai jūs pareizrakstības pārbaudi.
Un tā vārdnīcas mēs dodam jūs dodaties
lai dotu jums faktisko vārdus, ka mēs vēlamies Jums saglabāt kaut kā tādā veidā, kas ir
efektīvāka nekā masīva.
Un tad teksti ir būs tas, ko mēs esam
kurā jums pareizrakstības pārbaude, lai pārliecinātos, visi vārdi ir reālas vārdi.
>> Un tā trīs bloki programmas, kas mēs jums
sauc par dictionary.c, dictionary.h, un speller.c.
Un tā viss dictionary.c tas ir ko jūs esat aicināti, lai īstenotu.
Tas slodzes vārdus.
Tas pareizrakstības pārbauda tos, un tas padara pārliecināts ka viss ir ievietota pareizi.
>> diction.h ir tikai bibliotēkas fails kas deklarē visas šīs funkcijas.
Un speller.c, mēs ejam, lai dotu jums.
Jums nav nepieciešams mainīt kādu no tā.
Viss speller.c tas ir pieņemt, ka, slodzes tā, pārbauda ātrumu no tā,
testi kritēriju, piemēram, cik ātri jūs varat darīt lietas.
>> Tas ir Pareizrakstības.
Vienkārši nav sajaukt ar to, bet padarīt pārliecināts, ka jūs saprotat, ko tas dara.
Mēs izmantojam funkciju sauc getrusage ka testi veiktspēju jūsu pareizrakstības
pārbaudītājs.
Visiem tas ir būtībā metodei laiks visam jūsu vārdnīcā,
tāpēc pārliecinieties, ka jūs to saprotat.
Esiet uzmanīgi, lai nav haoss ar to, vai cits lietas nedarbosies pareizi.
>> Un lielākā daļa šo problēmu ir jūs puiši tiešām mainīt dictionary.c.
Mēs ejam, lai dotu jums 140,000 vārdi vārdnīcu.
Mēs ejam, lai dotu jums tekstu fails, kas ir šos vārdus,
un mēs vēlamies, lai jūs varētu organizēt tos hash tabulas vai TRIE
jo, kad mēs lūdzam jūs izskaidrot check-- iedomājieties, ja jūs esat pareizrakstības
pārbaudot, piemēram, Homēra Odisejā.
Tas ir tāpat kā šo milzīgo, milzīgs testu.
>> Iedomājieties, ja katru vārds jums nācās meklēt
izmantojot masīvu 140000 vērtībām.
Tas veikt uz visiem laikiem jūsu mašīna palaist.
Tieši tāpēc mēs vēlamies organizēt mūsu datus efektīvāku datu struktūras
piemēram, hash tabulu vai TRIE.
Un tad jūs guys var kind par to, kad jūs meklēt piekļuve
lietas vieglāk un ātrāk.
>> Un tāpēc jābūt uzmanīgiem, lai atrisinātu sadursmes.
Jūs esat gatavojas iegūt ķekars no vārdiem, kas sākas ar A
Jūs esat gatavojas iegūt ķekars vārdus kas sākas ar B. Līdz ar jums
puiši kā jūs vēlaties, lai to atrisinātu.
Varbūt tur ir vairāk efektīva hash funkcija
nekā tikai pirmo burtu kaut kas, un tā tas ir atkarīgs no jums
guys veida darīt, ko vien vēlaties.
>> Varbūt jūs vēlaties pievienot visi burti kopā.
Varbūt jūs vēlaties, lai patīk darīt dīvainas lietas atskaitīties skaitu vēstuļu,
neatkarīgi.
Līdz jums, puiši, kā jūs vēlaties to darīt.
Ja jūs vēlaties darīt hash tabulu, ja jums gribu izmēģināt trie, pilnībā atkarīgs no jums.
Es brīdinu jūs pirms laika, ka trie parasti ir nedaudz sarežģītāk
tikai tāpēc, ka tur ir daudz vairāk norādes sekot.
Bet pilnībā atkarīgs no jums puiši.
Tas ir daudz efektīvāk vairumā gadījumu.
Jūs vēlaties, lai tiešām varētu saglabāt līdzi visiem jūsu norādes.
Tāpat kā darīt to pašu ka man bija darīt šeit.
Kad jūs mēģināt ievietot vērtības uz hash tabulu vai dzēst,
pārliecinieties, ka esat tiešām sekotu
no tā, kur viss ir tāpēc, ka tas ir patiešām viegli, ja es esmu
mēģinot ievietot, piemēram, vārda, Endijs.
Pieņemsim tikai teikt, ka ir reāls vārds, vārds, Andy,
par milzu sarakstā A vārdiem.
>> Ja es tikai notikt pārdalīt rādītājs nepareizi, Ups,
tur iet visus ar pārējie manas saistīta saraksta.
Tagad vienīgais vārds I ir, ir Andy, un tagad
visiem citiem vārdiem vārdnīca ir pazuduši.
Un lai jūs vēlaties, lai pārliecinātos, ka jūs sekot līdzi visiem jūsu norādes
vai arī jūs esat gatavojas saņemt milzīgas problēmas jūsu kodu.
Izdarīt lietas rūpīgi soli pa solim.
Tas padara to daudz vieglāk iedomāties.
>> Un visbeidzot, jūs vēlaties, lai varētu pārbaudīt savu veiktspēju jūsu programmas
uz lielā kuģa.
Ja jūs puiši aizņemt apskatīt CS50 tieši tagad,
mēs esam tas, ko sauc par lielo valde.
Tas ir rezultāts lapa no visstraujāk Pareizrakstības pārbaude reizes pāri visiem CS50
tieši tagad, es domāju, ka, piemēram, 10 top reizes es domāju, ka astoņas no tām ir personāls.
Mēs patiešām vēlamies, lai jūs guys pārspēt mūs.
>> Visi no mums centās īstenot ātrākais kods, cik vien iespējams.
Mēs vēlamies, lai jūs guys, lai mēģinātu apstrīdēt mums un ieviest ātrāk nekā mums visiem
var.
Un tā tas ir patiešām pirmā reize, kad mēs esam
lūdz jūs guys darīt PSET, ka jūs tiešām var darīt jebkādā metodi
tu gribi.
>> Es vienmēr saku, tas ir vairāk līdzinās uz reālās dzīves risinājumu, vai ne?
Es saku, hey, man ir nepieciešams, lai jūs to izdarītu.
Veidot programmu, kas tas par mani.
Vai tas tomēr vēlaties.
Es tikai zinu, ka es gribu, lai ātri.
Tas ir jūsu uzdevums, lai šīs nedēļas laikā.
Jūs guys, mēs ejam lai dotu jums uzdevumu.
Mēs ejam, lai dotu jums izaicinājumu.
Un tad tas ir atkarīgs no jums, puiši pilnīgi vienkārši izrēķināt
kas ir ātrākais un visvairāk efektīvs veids, kā īstenot šo.
Yeah?
>> Mērķauditorija: Vai mēs atļauts, ja vēlējās, lai pētniecības ātrākus veidus
darīt hash tabulas online, mēs varam darīt kas un citē kāds cits kods?
ANDI PENG: Jā, pilnīgi naudas sodu.
Tātad, ja jūs guys lasīt spec, tur ir līnija
spec, kas saka, jūs guys ir pilnīgi bez maksas, lai pētniecības hash
funkcijas par to, kas ir daži no ātrāk hash funkcijas
vadīt lietas cauri, kā Kamēr jūs citēt šo kodu.
Tātad daži cilvēki jau ir sapratu, ātrus veidus
darīt pareizrakstības pārbaudītājus, ātrās veidi, kā uzglabāt informāciju.
Pilnībā atkarīgs no jums puiši, ja jums vēlas vienkārši pieņemt, ka, labi?
Pārliecinieties, ka jūs citējot.
Problēma šeit patiešām ka mēs cenšamies, lai pārbaudītu
ir pārliecināties, ka jūs zināt savu ceļu apkārt norādes.
Cik jūs īstenošanā faktiskais hash funkcija
un nāk klajā ar līdzīgu matemātika, lai to izdarītu,
jūs guys var pētīt neatkarīgi metodes online jūs guys vēlaties.
Yeah?
>> Mērķauditorija: Vai mēs varam minēt tikai izmantojot [dzirdams]?
>> ANDI PENG: Jā.
Jūs varat vienkārši, savā komentārā, Jūs varat minēt, piemēram, oh,
ņemts no Yada, yada, yada, hash funkciju.
Kāds ir kādi jautājumi?
Mēs faktiski breezed caur sadaļā šodien.
Es būšu šeit, lai atbildēt uz jautājumiem, kā arī.
>> Tāpat, kā jau teicu, birojs stundas šovakar un rīt.
Spec šonedēļ ir faktiski super viegli un super īss, lai lasītu.
Es ieteiktu ņemot apskatīt, vienkārši izlasīt kopumā no tā.
>> Un Zamyla faktiski pastaigas Jūs caur katru no funkcijām
Jums ir nepieciešams, lai īstenotu, un tāpēc tas ir ļoti, ļoti skaidrs, kā to darīt visu.
Tikai, lai pārliecinātos, ka jūs esat sekotu norādes.
Tas ir ļoti sarežģīts PSET.
>> Tas nav izaicinājums, jo, piemēram, oh, jēdzieni ir tik daudz vairāk
grūti, vai arī jums ir iemācīties tik daudz jauna sintakse veids
ka jūs par pēdējo PSET.
Tas PSET ir grūti, jo tur ir tik daudz norādes,
un tad tas ir ļoti, ļoti viegli, kad Jums ir bug savu kodu nevarēs
lai atrastu, kur tas ir bug.
>> Un tā ir pilnīga un izdvest ticība tevi puiši, lai varētu pārspēt mūsu [nedzirdama]
rakstību.
Es tiešām neesmu nevienu rakstisku raktuves vēl, bet es esmu par to rakstīt raktuvē.
Tāpēc, kamēr jūs esat rakstiski yours, es būšu rakstot mine.
Es esmu gatavojas, lai mēģinātu padarīt raktuves ātrāk nekā jums.
Mēs redzēsim, kurš ir ātrākais vienu.
>> Un jā, es redzēt visus jūs puiši šeit otrdien.
Es darbosies veida, piemēram, PSET darbnīcā.
Visi no sekcijām šis nedēļa ir PSET darbnīcas,
tāpēc jums puiši ir daudz iespējas palīdzību, darba laika, kā vienmēr,
un es tiešām ceru uz lasījums visiem jūsu puiši "kodu.
Man ir viktorīnas šeit, ja jums puiši vēlas nākt saņemtu tiem.
Tas ir viss.