[Mūzikas atskaņošanai]
>> DAVID Malan: Tas ir CS50.
Un tas ir gan sākums un end-- tāpat literally-- gandrīz beigām
Nedēļas seši.
>> Es domāju, ka man dalīties Mazliet jautru faktu.
Esmu velk to uz augšu no pagājušā semestra datu kopa.
Jūs varat atgādināt, ka mēs lūdzam jūs uz katru p komplekts forma, ja esat noskatījos internetā
vai arī, ja esat apmeklējis personīgi.
Un šeit ir dati.
Tātad šodien bija ļoti prognozējama.
Bet mēs vēlējāmies pavadīt mazliet laika ar jums tomēr.
Vai kāds vēlētos minējumus, kāpēc šis diagramma ir tik jaggy, uz augšu uz leju, uz augšu uz leju,
tik konsekventi?
Ko katrs no virsotnēm un siles pārstāv?
>> Mērķauditorija: [dzirdams]
DAVID Malan: Patiesi.
Un vēl Saistošs, nedod Dievs, mēs tur vienu lekciju piektdienā
sākumā semestra, ka tas, ko mēs redzam notikt.
Tātad šodien, mēs baudām mazliet vairāk par datu struktūras.
Un, lai dotu jums vairāk cieta garīgās modelis problēmām pēc pieciem,
kas tagad ir ārā.
Pārrakstīšanās, kur, mēs rokas jums teksta failu daži 100,000
plus angļu vārdus, un jūs nāksies
izdomāt, kā gudri ielādēt tos atmiņā, RAM, izmantojot dažus datus
struktūra jūsu izvēles.
>> Tagad viens no šādiem datu struktūra varētu būt, bet, iespējams, nevajadzētu būt,
Vienkāršota saistīts saraksts, kuru mēs iepazīstinājām pēdējo reizi.
Un saistīts saraksts bija vismaz viena priekšrocība pār masīva.
Kas ir viena priekšrocība saistīts saraksts varbūt?
>> AUDITORIJA: ievietošana.
>> DAVID Malan: ievietošana.
Ko jūs ar to domājat?
>> AUDITORIJA: Anywhere kopā saraksts [nedzirdama].
>> DAVID Malan: Labi.
Tātad jūs varat ievietot elementu, kur vien vēlaties vidū saraksta
bez shuffle neko, ko mēs secināja, mūsu šķirošanā
diskusijas, nav vienmēr ir laba lieta,
jo ir nepieciešams laiks, lai faktiski pārvietotos visiem šiem cilvēkiem pa kreisi vai pa labi.
Un tā ar saistīta sarakstu, jūs varat vienkārši piešķirt ar malloc, jaunu mezglu,
un pēc tam atjaunināt pāris pointers-- divi, trīs operācijas max--
un mēs esam spējīgi slots kādu jebkur stāšanās sarakstā.
>> Kas vēl bija izdevīgi par saistītajā sarakstā?
Yeah?
>> Mērķauditorija: [dzirdams]
DAVID Malan: Perfect.
Perfekta.
Tas ir patiešām dinamisks.
Un ka jūs neesat izdarījuši, iepriekš, uz kādu fiksētu lielumu
rieciens atmiņas, kā jūs varētu būt līdz ar masīvu, augšupvērsti kura
ir tas, ka jūs varat piešķirt mezglu tikai pieprasījums tādējādi izmantojot tikai tik daudz vietas
kā jums tiešām ir nepieciešams.
Pretstatā ar masīvu, jūs varētu nejauši piešķirt pārāk maz.
Un tad tas ir tikai gatavojas būt sāpes kaklā
pārdalīt jaunu lielāku masīvs, kopēt viss vairāk, atbrīvot veco masīvs,
un tad pāriet par jūsu biznesu.
Vai vēl ļaunāk, jūs varētu piešķirt ceļu vairāk atmiņas nekā jums tiešām ir nepieciešams,
un tāpēc jums nāksies ļoti mazapdzīvotos masīvs, lai runāt.
>> Tātad saistīts saraksts dod jums šos priekšrocības dinamisma un elastības
ar ievietošanas un svītrojumiem.
Bet, protams, ir jābūt cena, ko maksā.
Patiesībā, viena no tēmām izpētīts ar viktorīnu nulles
bija pāris no kompromisiem mēs esam redzējuši līdz šim.
Tātad, kāda ir cena, kas samaksāta vai negatīvie saistītajā sarakstā?
Yeah.
>> Mērķauditorija: Nav brīvpiekļuves.
>> DAVID Malan: Nav brīvpiekļuves.
Bet kurš rūpējas?
Brīvpiekļuves neizklausās pārliecinoši.
>> Mērķauditorija: [dzirdams]
DAVID Malan: Tieši tā.
Ja jūs vēlaties, lai būtu noteiktu algorithm--
un ļaujiet man tiešām ierosinās bināro meklēšanu it īpaši, kas
ir viens, mēs esam izmanto diezgan bit-- Ja jums nav izlases piekļuves,
Jūs nevarat darīt, ka vienkāršu aritmētiku atrast līdzīgi vidējā elementa
un lekt tiesības uz to.
Jums tā vietā ir jāsāk pie pirmā elements, un lineāri meklēt no kreisās
uz labo pusi, ja jūs vēlaties, lai atrastu vidējā vai jebkurš cits elements.
>> Mērķauditorija: Tas, iespējams, aizņem vairāk atmiņas.
>> DAVID Malan: Stājas vairāk atmiņas.
Kur ir tas, ka papildu izmaksas nāk no atmiņas?
>> Mērķauditorija: [dzirdams]
DAVID Malan: Tieši tā.
Tādā gadījumā šeit, mums bija saistīts saraksts veseliem skaitļiem,
un tomēr mēs esam divkāršojies atmiņas apjomu,
mums vajag, ko arī uzglabājot šīs norādes.
Tagad mazāk liels darījumu, kā Jūsu structs get lielāks
un jūs uzglabātu nevis numuru, bet varbūt students vai kādu citu objektu.
Bet jautājums, protams, paliek.
Un tā vairākas darbībām uz saistītiem sarakstiem tika saukta
bija lielais O N- lineāra.
Lietas, piemēram, ievietošanas vai meklēšanas vai dzēšanu, ja elementu
gadījās būt pašās beigās sarakstu, vai tas ir sakārtoti vai ne.
>> Dažreiz jūs varētu saņemt laimīgs un tā apakšējā robeža par šīm darbībām
varētu būt arī nemainīgs laiku, ja jūs esat vienmēr meklē pirmo elementu,
piemēram.
Bet galu galā, mēs apsolījām lai sasniegtu Svētais Grāls
datu struktūras, vai tuvinot to,
veidā pastāvīgu laiku.
Vai mēs varam atrast elementus vai pievienot elementus vai noņemt elementus no saraksta?
Mēs redzēsim pavisam drīz.
Un izrādās, ka viens mehānismu, mēs esam
gatavojas sākt lietot jau šodien, Gada izmantošana p noteikti pieci,
faktiski ir diezgan pazīstams.
Piemēram, ja tas ir ķekars no eksāmenu grāmatas, katrs no kuriem
ir studentu pirmā vārds un uzvārds, par to,
un es tos paceltu no beigās eksāmenu,
un viņi visi ir diezgan daudz nejaušā secībā,
un mēs gribam, lai iet par šķirošanas šie eksāmeni tā, ka pēc tam, kad šķirotas
tas ir tikai daudz vieglāk un ātrāk nodot tos atpakaļ ārā
studentiem alfabēta.
Kādi būtu jūsu instinkti būs par kaudzi eksāmeniem kā šis?
>> Nu, ja jūs, piemēram, man, jūs var redzēt, ka tas ir m,
tāpēc es esmu gatavojas veida nodot to vērā, ja šī ir mana galda vai manu grīdas kur
Es esmu izplatās lietas out-- vai manu masīvs really--
Es varētu nodot visas MS tur.
Oh.
Lūk A. Tāpēc es varētu ielieciet As nekā šeit.
Oh.
Lūk, vēl viens A. Es eju likt, ka vairāk nekā šeit.
Lūk Z. Šeit ir vēl viens M. Un tā Es varētu sākt pelnīt kaudzēm, kā šis.
Un tad varbūt es gribētu iet vēlāk un kārtot ļoti nitpicky-ly kārtošanas
individuālie pāļi.
Bet jautājums ir es varētu meklēt pie ieejas, ka es esmu roku
un es varētu veikt dažas aprēķināts lēmumu, pamatojoties uz šo ieguldījumu.
Ja tas sākas ar, ielieciet to tur.
Ja tas sākas ar Z, ielieciet to vairāk tur, un viss pa vidu.
>> Tātad tas ir paņēmiens, kas ir parasti sauc par hashing-- H-A-S-H--
kas parasti nozīmē, ņemot par ievadi, un, izmantojot šo ieguldījumu, lai aprēķinātu
vērtība, parasti skaitlis, un ka skaits ir indekss par glabāšanā
konteineru, tāpat kā masīvs.
Tātad citiem vārdiem sakot, es varētu būt hash funkcija, kā es to daru manā galvā,
ka, ja es redzu, kāds ir vārds, kas sākas ar A,
Es esmu gatavojas karti, ka līdz nullei manā galvā.
Un, ja es redzu kādu ar Z, es esmu dodas uz karti, kas līdz 25 manā galvā
un pēc tam nodot, ka pēdējais visvairāk kaudzes.
>> Tagad, ja jūs domājat par to nav manas smadzenes bet C programmu, kas varētu numuri
Jūs paļauties uz, lai sasniegtu to pašu rezultātu?
Citiem vārdiem sakot, ja jums bija ASCII rakstzīmju A,
kā jūs noteikt ko spainis likt to?
Jūs, iespējams, nevēlaties ieliec spaini 65, kas
būtu kā tur nesaprotamu iemeslu dēļ.
Ja jūs vēlaties, lai izveidotu attiecībā uz tās ASCII vērtība?
Ja jūs vēlaties darīt, lai tās ASCII vērtība nākt klajā ar gudrāku kausu
nodot to?
>> AUDITORIJA: Mīnus A.
>> DAVID Malan: Jā.
Tātad mīnus vai mīnus īpaši 65, ja tas ir
kapitāla A. Vai 98, ja tas ir mazie burti.
Un lai ļautu mums, ir ļoti vienkārši un ļoti aritmētiski,
likts kaut spainī, piemēram, ka.
Tātad izrādās, mēs faktiski darīt Tas, kā arī pat ar viktorīnas.
>> Lai jūs varētu atgādināt jums riņķoja savu mācīšana Fellow vārds uz vāka.
Un tika organizētas TF ir nosaukumi šajās slejās pēc alfabēta,
labi, ticiet vai ne, kad visi 80 plus mums
sanāca kopā citiem nakts pakāpē, pēdējais solis mūsu šķirošanas procesā
ir hash viktorīnas uz lielas telpu grīdas pie [dzirdams]
un likt ikviena viktorīnas out tieši to TF Rīkojuma
vārdi vāka, jo tad tas ir daudz vieglāk mums
meklēt, izmantojot šim, izmantojot lineāru meklēt vai sava veida gudrība
par TF, lai atrastu viņa vai viņas studentu viktorīnas.
>> Tātad šī ideja sajaukšanai ka jūs redzēsiet, ir
diezgan spēcīgs, faktiski ir diezgan parasts un ļoti intuitīvu,
līdzīgi varbūt sadalīt un Iekarot bija nedēļā nulles.
Es ātri uz priekšu, lai hackathon pirms pāris gadiem.
Tas bija Zamyla un pāris pārējie darbinieki apsveikuma studenti
jo tie nāca.
Un mums bija visu ķekars salocīšanu galdi tur ar nosaukumu atzīmēm.
Un mums bija nosaukums tagus organizēja ar patīk, jo vairāk nekā tur
un Zs tur.
Un tāpēc viens no TFS ļoti gudri rakstīja to kā instrukciju
par dienu.
Un 12. nedēļā semestra šā visi, kas perfektu sajūtu un visiem
zināja, ko darīt.
Bet jebkurā laikā jūs esat ievietots rindā tādā pašā veidā,
jūs īstenojot pats jēdziens hash.
Tāpēc pieņemsim formalizēt tas mazliet.
Šeit ir masīvs.
Tas ir izstrādāts, lai būtu nedaudz plata tikai attēlot vizuāli,
ka mēs varētu nodot stīgas kaut kas līdzīgs šim.
Un tas ir masīvs acīmredzami izmērs 26 kopā.
Un lieta tiek saukta galda patvaļīgi.
Taču tas ir tikai mākslinieka pārsūtīšanu par to hash tabulu varētu būt.
>> Tātad hash tabulu, tagad gatavojas būt augstāka līmeņa datu struktūras.
Beigās dienas mēs esam par to, lai pārliecinātos, ka jums
var īstenot hash tabulu, kurā ir daudz, piemēram check-in line
pie hackathon daudz kā šis tabula izmanto šķirošanas eksāmenu grāmatas.
Bet hash tabula ir kārtot šo augsto līmeni
jēdziens, kas varētu izmantot masīvu zem motora pārsegs, lai to īstenotu,
vai tas varētu izmantot garuma sarakstu, vai pat varbūt daži citi datu struktūras.
Un tagad tas ir theme-- ņemšana dažas no šīm galvenajām sastāvdaļām
piemēram, masīvu un šīs ēkas bloķēt tagad garuma saraksta
un redzēt to, ko vēl mēs varam veidot uz augšu no tiem, piemēram, sastāvdaļas
uz recepti, padarot vairāk un vairāk interesantas un noderīgas galīgie rezultāti.
>> Tātad ar hash tabulu mēs varētu īstenot
atmiņā gleznieciski kā šis, bet cik tas varētu tiešām būt kodēti uz augšu?
Nu, varbūt, jo vienkārši tas ir.
Ja jauda visos cepures, ir tikai daži constant-- piemēram 26,
26 burti alphabet-- Es varētu piezvanīt savai mainīgo galda,
un es varētu apgalvot, ka es esmu gatavojas likts char zvaigznes tur, vai auklas.
Tāpēc tas ir tik vienkārši, kā tas, ja jūs vēlamies īstenot hash tabulu.
Un tomēr, tas ir patiešām vienkārši masīvs.
Bet atkal, hash Tagad tabula ir tas, ko mēs
zvaniet abstrakts datu tips, kas ir tikai veida konceptuāla layering uz augšu
kaut ko vairāk ikdienišķa Tagad patīk masīvs.
>> Tagad, kā mēs iet par problēmu risināšanai?
Nu, agrāk man bija greznība no pietiekoši galda telpa šeit
lai es varētu likt viktorīnas jebkur es gribēju.
Tātad, kā varētu iet šeit.
Zs varētu iet šeit.
Ms varētu iet šeit.
Un tad man bija dažas papildu telpas.
Bet tas ir mazliet apkrāptu tiesības tagad, jo šajā tabulā, ja es patiešām
domāja par to, kā masīvu, ir tikai būs par kādu fiksētu izmēru.
>> Tātad tehniski, ja es pull up cita studenta viktorīnas
un redzēt, ak, šis personas vārds sākas ar A pārāk,
Es veida gribu likt to tur.
Bet tiklīdz man to tur, ja šī tabula tiešām ir masīvs,
Es esmu būs svarīgi vai clobbering kurš šī studenta viktorīna ir.
Taisnība?
Ja tas ir masīvs, tikai viena lieta, var iet uz katru no šīm šūnām vai elementu.
Un tāpēc es veida ir atlasīt un izvēlēties.
>> Tagad agrāk es veida cheated un izdarīja tā, vai I
tikko veida kaudzē tos virs otra.
Bet tas nav gatavojas lidot kodu.
Tātad, kur es varētu likt otrais students, kura vārds
ir, ja visi man bija tas pieejami galda telpa?
Un es esmu, ko izmanto trīs slots un to izskatās, ka tur ir tikai daži citi.
Ko jūs varētu darīt?
Mērķauditorija: [dzirdams]
DAVID Malan: Jā.
Varbūt pieņemsim tikai glabā to vienkārši.
Taisnība?
Tas neiederas, kur es gribu, lai to.
Tāpēc es esmu gatavojas nodot to tehniski kur B varētu iet.
Tagad, protams, es esmu sāk gleznot sevi stūrī.
Ja es nokļūt studentam kura vārds ir faktiski B,
Tagad B tiks pārcelts nedaudz priekšu, kā varētu notikt, yep,
ja tas ir B, tagad tas ir iet šeit.
>> Un tā tas ļoti ātri varētu kļūt problemātiska,
bet tas ir paņēmiens, kas faktiski ir minēta kā lineāra zondēšana,
kurā jūs tikai apsvērt savu masīvs būt pa līniju.
Un jūs vienkārši veida zonde vai pārbauda katru pieejamo elementu
meklē pieejams uz vietas.
Un, tiklīdz jūs atradīsiet viens, jūs piliens to tur.
>> Tagad cena ir samaksāta tagad šo risinājumu ir tas, ko?
Mums ir fiksēta izmēra masīvs, un, kad es ievietot vārdus
uz to, vismaz sākumā, kas ir darba laiks ievietošanas
liekot studentiem " viktorīnas Labajā spaiņiem?
Big O, ko?
>> AUDITORIJA: n.
DAVID Malan: Es dzirdēju Big O n.
Nav taisnība.
Bet mēs kaitināt intervālu kāpēc tikai brīdi.
Kas vēl tas varētu būt?
>> Mērķauditorija: [dzirdams]
DAVID Malan: Un ļaujiet man darīt to vizuāli.
Tātad pieņemsim, ka šī ir vēstule S.
>> Mērķauditorija: Tas ir viens.
DAVID Malan: Tas ir viens.
Taisnība?
Tas ir masīvs, kas nozīmē, ka mums ir brīva piekļuve.
Un, ja mēs domājam par to kā nulle, un tas, kā 25,
un mēs saprotam, ka, ak, šeit ir mana ieejas S,
Es, protams, var pārvērst S, ASCII raksturs,
ar attiecīgu skaitu no nulles līdz 25
un tad uzreiz nodot to, ja tā pieder.
>> Bet, protams, tiklīdz es nokļūt Otrs cilvēks, kurš vārds ir vai B vai C
galu galā, ja es esmu, ko izmanto lineārs zondēšana kā manu risinājumu,
darba laiks ievietošana sliktākajā gadījumā
ir faktiski gatavojas pāriet uz ko?
Un es to dzirdu to šeit pareizi sākumā.
Mērķauditorija: [dzirdams]
DAVID Malan: Tātad tas ir n patiešām reiz Jums ir pietiekami lielu datu kopu.
Tātad, no vienas puses, ja Jūsu masīvs ir pietiekami liels
un jūsu dati ir maz pietiekami, jūs saņemt šo skaisto pastāvīgu laiku.
Bet, tiklīdz jūs sākat arvien vairāk un vairāk elementu,
un tikai statistiski jums vairāk cilvēku ar burtu
Kā to vārds vai burts B, tas var potenciāli
pāriet uz kaut ko vairāk lineāra.
Tāpēc ne gluži ideāls.
Lai mēs varētu darīt labāk?
>> Nu, kāda bija mūsu risinājums, pirms kad mēs
vēlas, lai būtu vairāk nekā dinamiku kaut kā masīva atļauts?
Mērķauditorija: [dzirdams]
DAVID Malan: Ko mēs ieviest?
Yeah.
Tātad saistīts saraksts.
Nu, pieņemsim redzēt, kas saistīta sarakstu varētu darīt mums vietā.
Nu, ļaujiet man ierosinu izdarīt attēlu šādi.
Tagad tas ir atšķirīgs bilde no piemēru
no cita teksta, faktiski, ka ir faktiski izmantojot masīvu izmēru 31.
Un šis autors vienkārši nolēma hash virknes
nevis pamatojoties uz personas vārdu, bet, pamatojoties uz to birthdates.
Neatkarīgi no mēneša, viņi skatīja Ja jūs esat dzimis no pirmā mēneša
vai 31. mēnesi, autors būs hash, pamatojoties uz šo vērtību,
lai izplatītu vārdus out mazliet vairāk nekā tikai 26 punkti varētu pieļaut.
Un varbūt tas ir nedaudz vairāk vienota nekā iet ar alfabēta burtiem,
jo, protams, tur ir iespējams vairāk cilvēku pasaulē ar vārdiem
ka sākt ar nekā noteikti daži citi alfabēta burti.
Tāpēc varbūt tas ir nedaudz vienotāka, pieņemot
vienota izplatīšanas zīdaiņu visā mēnesī.
>> Bet, protams, tas joprojām ir nepilnīgs.
Taisnība?
Mēs esam, kam sadursmes.
Vairāki cilvēki šo datu struktūra joprojām
ar tādu pašu dzimšanas vismaz jūs esat neatkarīgi no mēneša.
Bet ko ir autors darījis?
Nu, izskatās, ka mums ir masīvs kreisajā pusē novilkta vertikāli,
bet tas ir tikai mākslinieka atveidojumu.
Tas nav svarīgi, kādā virzienā jūs izdarīt masīvs, tas joprojām ir masīvs.
Kas tas ir masīvs acīmredzot?
>> Mērķauditorija: Saistīts saraksts.
>> DAVID Malan: Jā.
Izskatās, ka tas ir masīvs saistīts saraksts.
Tātad vēlreiz, lai šī viedokļa veida Izmantot šo datu struktūras tagad
kā sastāvdaļas uz vairāk interesanti risinājumi,
Jūs varat veikt absolūti būtisks, tāpat kā masīvs,
un tad kaut ko vairāk interesanti kā saistīts saraksts
un pat apvienot tos pat interesantāku datu struktūra.
Un tiešām, tas arī būtu saukt hash tabulu,
kuru masīvs ir tiešām hash tabulu,
bet hash tabulu ir ķēdes, tā sakot,
kas var augt vai sarukšana, pamatojoties uz elementu skaits vēlaties ievietot.
>> Tagad, attiecīgi, kas ir darbības laiks tagad?
Ja es gribu, lai ievietotu kādu kuru dzimšanas diena ir 31. oktobris,
kur viņš vai viņa iet?
Labi.
Tajā pašā apakšā, kur ir teikts 31.
Un tas ir lieliski.
Tas bija nemainīgs laiks.
Bet ko tad, ja mēs atrast kādu citu kuru dzimšanas diena ir, pieņemsim redzēt,
Oktobris, novembris, decembris 31?
Ja viņš vai viņa gatavojas doties?
Pats.
Divi solis gan.
Tas ir nemainīgs, lai gan nav tā?
Labi.
Šobrīd tas ir.
Tomēr vispārējā gadījumā, jo vairāk cilvēku, mēs pievienot,
probabilistically, mēs ejam lai iegūtu vairāk un vairāk sadursmes.
>> Tagad tas ir maz labāk, jo tehniski
tagad mana ķēdes varētu būt sliktākajā gadījumā, cik ilgi?
Ja es ievietot n cilvēkus šo vairāk sarežģītu datu struktūru, n cilvēki,
sliktākajā gadījumā tas būs n.
Kāpēc?
>> Mērķauditorija: Jo, ja visi ir tāda pati dzimšanas,
viņi būs viena rinda.
DAVID Malan: Perfect.
Tas varētu būt nedaudz izdomāts, bet patiesi sliktākajā gadījumā,
ja visi ir tāda pati dzimšanas diena, ņemot vērā ieejas jums ir,
jūs nāksies masveidā garu ķēdi.
Un tā, jūs varētu to sauc par hash tabulu, bet patiesībā tas ir
tikai masveida saistīts saraksts ar visai daudz izšķērdēta telpu.
Bet vispār, ja mēs pieņemam, ka vismaz dzimšanas dienas ir uniform--
un tas, iespējams, nav.
Es esmu padarot šo augšu.
Bet, ja mēs pieņemam, lai labad diskusijas
ka tie ir, tad teorētiski, ja tas ir vertikāla pārstāvība
masīva, labi, tad, cerams, jūs esat gatavojas saņemt ķēdes, kas ir, jūs zināt,
aptuveni vienāda garuma, kur katrs no tie veido mēneša dienu.
>> Tagad, ja tur ir 31 dienas mēnesī, tas nozīmē, ka mana darba laika patiešām
ir liels O n bija 31, kas jūtas labāk nekā lineāra.
Bet to, kas bija viens no mūsu saistības pāris nedēļām
atpakaļ, kad tas nonāca pie izteikšanu darba laiks algoritmu?
Tikai tikai apskatīt lielo pasūtījumu termiņā.
Taisnība?
31 noteikti ir noderīga.
Bet tas joprojām ir liels O n.
Bet viena no tēmām problemātisko noteikti pieci
būs uz atzīst, ka absolūti,
asimptotiski, teorētiski šo datu struktūra
nav labāka nekā tikai viens masveida saistīts saraksts.
Un tiešām, sliktākajā gadījumā, tas hash tabulu var pāriet uz to.
>> Bet reālajā pasaulē, ar mums cilvēki ka pašu Mac vai PC, vai kāds
un darbojas reālajā pasaulē programmatūras reālās pasaules datiem,
kas algoritms jūs plānojat dot priekšroku?
Viens, ka notiek gala pasākumus vai viens, kas ņem n dalot ar 31 soļiem
atrast kādu gabals datu vai uzmeklēt kādu informāciju?
Es domāju, absolūti 31 marku atšķirība reālajā pasaulē.
Tas ir 31 reizes ātrāk.
Un mēs, cilvēki, protams, gatavojas novērtējam.
>> Tātad realizēt dihotomiju tur starp faktiski
runājam par lietām teorētiski un asimptotiski kas noteikti
ir vērtība, kā mēs esam redzējuši, bet reālajā pasaulē,
ja jums rūp tikai veicot Cilvēka priecīgi par vispārīgiem ieguldījumiem,
jūs varētu ļoti labi vēlēties pieņemt Fakts, ka, jā, tas ir lineāra,
bet tas ir 31 reizes ātrāks nekā lineāra varētu būt.
Un vēl labāk, mēs ne tikai ir darīt kaut patvaļīgu kā dzimšanas datumu,
mēs varētu tērēt nedaudz vairāk laika un gudrība
un domāt par to, ko mēs varētu darīt, ņemot vērā personas vārds un varbūt
viņu dzimšanas datums apvienot tos, sastāvdaļas izdomāt kaut ko
kas ir patiesi daudz vienota un mazāk jaggy,
lai runāt par šo bildi Pašlaik liecina tas varētu būt.
Kā mēs varētu īstenot šo kodu?
Nu, ļaujiet man ierosinu vienkārši aizņemties kādu sintakse mēs esam
izmanto pāris reizes līdz šim.
Un es esmu gatavojas, lai definētu mezglu, kas atkal
ir vispārējs termins, tikai daži konteiners kādu datu struktūra.
Es esmu gatavojas ierosināt string notiek tur.
Bet mēs esam gatavojas sākt lietot tiem mācību riteņiem off tagad.
>> Ne vairāk CS50 bibliotēka tiešām, ja jūs vēlaties
izmantot to savā finālā projekts, kas ir labi,
bet tagad mēs esam gatavojas pull atpakaļ aizkaru un saka, ka tas ir tikai char zvaigzne.
Tātad vārds tur būs personas vārds jautājumā.
Un tagad man ir saite šeit uz nākamo mezglu
tā, ka šie ir katrs no mezgliem
ķēdē, iespējams, no saistītajā sarakstā.
>> Un tagad, kā es varu paziņot hash pati tabula?
Kā es varu atzīt šo visu struktūru?
Nu, tiešām, daudz, piemēram, es izmantoti rādītāju uz tikai uz saraksta pirmo elementu
pirms, tāpat es varu tikai teikt Man tikai vajag ķekars norādes
lai īstenotu šo visu hash tabulu.
Es esmu nāksies masīvs aicināja tabula hash tabulu.
Tas būs no lieluma jaudu.
Tas, cik daudz elementu var ietilpt tajā.
Un katrs no šiem elementiem šajā masīvs būs mezglu zvaigzne.
Kāpēc?
Nu, par šo attēlu, ko es esmu Īstenojot hash tabulu kā
efektīvi sākums ir tikai šis masīvs, ka mēs esam izdarīt vertikāli,
Katrā no kuru kvadrātu pārstāv rādītāju.
Ka tie, kas ir slīpsvītras caur tiem ir tikai null.
Un tie, kas ir bultas iet uz labo pusi
ir faktiskas norādes uz faktiskajiem mezgliem, ergo sākumu saistītajā sarakstā.
>> Tātad šeit, tad ir, kā mēs varētu īstenot hash tabulu, kas
īsteno atsevišķu Ķēžu.
Tagad mēs varam darīt labāk?
Visas tiesības Es apsolīju pēdējo reizi mēs varētu panākt pastāvīgu laiku.
Un es veida deva jums nemainīgs laika šeit,
bet tad teica, ka nav īsti nemainīgs laiks, jo tas joprojām ir
atkarīgs no kopējā elementu skaits
jūs ievadot stājas datu struktūra.
Bet pieņemsim, ka mēs to darījām.
Ļaujiet man iet atpakaļ uz ekrāna vairāk nekā šeit.
Ļaujiet man arī projicēt šo šeit, skaidra ekrāns, un domāju, ka es to izdarīja.
Pieņemsim, ka es gribēju, lai ievietotu vārdu Daven jo manā datu struktūra.
>> Tāpēc es gribu, lai ievietotu virkni Daven uz datu struktūru.
Ko darīt, ja man nav lietot hash tabulu, bet es izmantoju
kaut kas ir vairāk kokveida kā ģimenes koks, kur
Jums ir dažas saknes pie top un tad mezgli un lapas
ka iet uz leju un uz āru.
Pieņemsim, ka tad, ka es vēlaties ievietot Daven s
par to, kas šobrīd ir tukšs saraksts.
Es esmu gatavojas darīt sekojošo: Es esmu notiek, lai izveidotu mezglu šīs saimes
kokveida datu struktūra, kas izskatās nedaudz, piemēram, tas, katrs no kuriem
taisnstūri ir, teiksim, Tagad 26 elementu tajā.
Un katrs no šūnām šajā masīvā gatavojas
pārstāvēt vēstuli ar alfabētu.
>> Konkrēti, es esmu gatavojas, lai ārstētu Tas ir, tad B, tad C, tad D,
šo vienu šeit.
Tātad, tas notiek, lai efektīvi pārstāv vēstuli D.
Bet, lai ievietotu visu Daven s nosaukt man jādara mazliet vairāk.
Tāpēc es esmu pirmo reizi gatavojas hash, lai runāt.
Es esmu gatavojas apskatīt pirmo burtu in Daven s, kas ir acīmredzami D,
un es esmu gatavojas piešķirt mezgls, kas izskatās
tāpat this-- lielu taisnstūri liels pietiekami, lai ietilptu visu alfabētu.
>> Tagad D tiek darīts.
Tagad A. D-A-V-E-N ir mērķis.
Tāpēc tagad, ko es esmu gatavojas darīt, ir tas.
Tiklīdz es sāku D paziņojumu tur nav rādītājs tur.
Tas ir atkritumu vērtības brīdī, vai es varētu inicializēt to null.
Bet ļaujiet man saglabāt notiek ar šī ideja veidot koku.
Ļaujiet man piešķirt vēl vienu no šiem mezglus, kas ir 26 elementi tajā.
>> Un jūs zināt, ko?
Ja tas ir tikai mezglā atmiņā, ka Es radīju ar malloc, izmantojot struct
kā mēs drīz redzēt, Es esmu gatavojas darīt this--
Es esmu gatavojas izdarīt bultiņu no lieta, kas pārstāvēja D uz leju
uz šo jauno mezglu.
Un tagad, pirmkārt nākamais burts Daven vārda,
V-- D--V-- es esmu gatavojas iet uz priekšu un izdarīt vēl vienu mezglu, piemēram, tas,
saskaņā ar kuru, tad V elementi šeit, kas mēs izdarīt par instance-- whoops.
Mēs nevarēsim izdarīt tur.
Tas notiek, lai iet šeit.
>> Tad mēs ejam uzskatām, ka tas ir V.
Un tad noteikti šeit mēs ejam indeksēt leju no V uz to, ko mēs uzskatām E.
Un tad no šeit mēs ejam aiziet ir viens no šiem mezgliem šeit.
Un tagad mums ir jautājums, lai atbildētu.
Man vajag, lai kaut kā norādīt, ka mēs beigās string Daven.
Lai es varētu vienkārši atstāt to null.
>> Bet ko tad, ja mums ir Daven s pilns nosaukums ir arī, kas
ir, kā mēs jau teicām, Davenport?
Tātad, ko tad Daven ir faktiski apakšvirkni,
priedēklis daudz ilgāku string?
Mēs varam ne tikai neatgriezeniski saka, nekas notiek
iet uz turieni, jo mēs varētu nekad ievietotu vārdu, piemēram, Davenport
šajā datu struktūra
>> Tātad, ko mēs varētu darīt tā vietā, ir izturamies pret katru no šiem elementiem
kā varbūt ar divām elementi iekšpusē no tiem.
Viens no tiem ir rādītājs, protams, kā es esmu darījis.
Tātad, katrs no šiem kastes ir ne tikai viena šūna.
Bet ko tad, ja top one-- apakšā vienu s
būs nulle, jo nav Davenport tikai yet.
Ko darīt, ja top viens Ir dažas īpašas vērtība?
Un tas būs nedaudz grūti izdarīt tā šo lielumu.
Bet pieņemsim, ka tas ir tikai atzīme.
Pārbaudīt.
D-A-V-E-N ir virkne šajā datu struktūra.
>> Tikmēr, ja man būtu vairāk vietas šeit, es varētu darīt P-O-R-T,
un es varētu likt pārbaudi mezglā kas ir burtu T pašās beigās.
Tātad tas ir ievērojami sarežģīts izskata datu struktūra.
Un mans rokraksts protams, nepalīdz.
Bet, ja es gribēju, lai ievietotu kaut ko cits, jāapsver, ko mēs varētu darīt.
Ja mēs vēlējāmies, lai Dāvids, mēs gribētu ievērot to pašu loģiku, D-A-V,
bet tagad es gribētu norādīt uz nākamo elements, nevis no E, bet no I līdz D
Tātad tur būs vairāk mezgliem šajā kokā.
Mēs ejam, lai būtu zvanu malloc vairāk.
Bet es nevēlos, lai padarītu pilnīgs haoss no šo attēlu.
Tātad, pieņemsim, nevis apskatīt vienu kas ir bijis iepriekš formulēti
kā šis ar ne dot, dot, punkti, bet tikai saīsinātus bloki.
Bet katrs no mezgliem Šajā koku šeit
pārstāv to pašu thing-- masīvs Ray izmēru 26.
>> Vai, ja mēs gribam būt īsti pareizi tagad, ko
ja kāds ir nosaukums, apostrofs, pieņemsim
pieņemu, ka katrs mezgls patiesībā ir tāpat kā 27 indeksu tajā, ne tikai 26.
Tātad tagad tas būs dati struktūru sauc trie-- T-R-I-E.
Trie, kas ir it vēsturiski gudrs nosaukums koku
kas ir optimizēta atgūšana, kas, protams,
ir uzrakstīti ar I-E, lai tas ir trie.
Bet tas ir vēsture TRIE.
>> Tātad trie tas kokveida dati struktūra, piemēram, ģimenes koks
kas galu galā uzvedas tāpat.
Un šeit ir tikai vēl viens piemērs viss ķekars citu cilvēku vārdiem.
Bet jautājums tagad pie rokas ir tas, kas ir
ieguvām ieviešot apstrīdami vairāk sarežģīta datu struktūra, un viens,
atklāti sakot, kas izmanto daudz atmiņas.
>> Jo, pat ja, brīdī, es esmu tikai
izmantojot D's rādītāju un Un V un Es un Ns,
Es esmu izšķērdēt heck atmiņas partijas.
Bet kur es pavadu viens resurss, Man ir tendence darīt iegūt atpakaļ citu.
Tātad, ja es esmu izdevumu vairāk vietas, to, kas ir iespējams, cerība?
Ka es esmu tērē mazāk, ko?
Mērķauditorija: Mazāk laika.
DAVID Malan: Laiks.
Tagad, kāpēc varētu būt?
Nu, kas ir ievietošanas laiks, runājot par lielo O tagad,
ar nosaukumu, piemēram, Daven vai Davenport vai Dāvids?
Nu, Daven bija pieci soļi.
Davenport būs deviņi posmi, lai tā būtu vēl dažus soļus.
David būtu pieci soļi, kā arī.
Tātad tie ir konkrēti skaitļi, bet, protams, tur ir
augšējo robežu uz garums kāda vārda.
Un tiešām, problēmā komplekti piecu specifikāciju,
mēs esam gatavojas ierosināt ka tas ir kaut kas
kas ir 40-dažas-nepāra zīmes.
>> Reāli, neviens nav bezgalīgi garš nosaukums,
kas ir teikt, ka garums vārdu vai garums string mēs varētu
ir pārliecināts stāvoklis struktūra ir apstrīdami, ko?
Tas ir nemainīgs.
Taisnība?
Tas varētu būt liels konstante, piemēram, 40-kaut ko, bet tas ir nemainīgs.
Un tas nav atkarība, cik citi vārdi ir šajā datu struktūrā.
Citiem vārdiem sakot, ja es gribēju tagad ievietot
Colton vai Gabriel vai Rob vai Zamyla vai Alison vai Belinda, vai kādi citi nosaukumi
no darbiniekiem, uz šo datu struktūra, ir darbības laiks
ievietojot citiem nosaukumiem būs vispār triecienu
pēc tā, cik daudziem citiem elementiem ir kas jau datu struktūru?
Tas nav.
Taisnība?
Tāpēc, ka mēs esam efektīvi izmantot šis daudzslāņu hash tabulu.
Un darbības laiks jebkura no šīm darbībām
ir atkarīga ne uz skaitu elementus, kas ar datu struktūru
vai kuras ir beidzot gatavojas būt datu struktūru,
bet no garuma, ko tieši?
>> Stīgu ir ievietota, kas tas padara
šis asimptotiski konstante LAIKU_ lielais O viens.
Un godīgi sakot, tikai reālajā pasaulē, šis
nozīmē, ievietojot Daven vārds notiek piemēram, pieci soļi, vai Davenport deviņi
pakāpieni, vai Deivids pieci soļi.
Tas ir diezgan darn mazie gaitas reizes.
Un, protams, tas ir ļoti laba lieta, it īpaši, ja
tas nav atkarīgs no kopējā apjoma vairāki elementi tur.
Tātad, kā mēs varētu īstenot šo veida struktūras kodu?
Tas ir nedaudz vairāk sarežģīts, bet tomēr tas ir
tikai piemērošana pamatelementiem.
Es esmu gatavojas pārskatīt mums mezgla šādi:
bool sauc word-- un tas varētu saukt jebko.
Bet bool pārstāv ko es vērsa kā atzīmi.
Jā.
Tas ir beigu virknes šajā datu struktūra.
>> Un, protams, mezglu zvaigzne tur ir kas attiecas uz bērniem.
Un, protams, tāpat kā ciltskoku, jūs
apsvērtu mezglus kas ir piekārtiem off
no apakšas kāda vecāka elements ir bērni.
Un tā bērni gatavojas būt masīvs 27., 27. viens
tikai pastāvēt apostrofam.
Mēs ejam, lai kārtotu īpašu gadījumu šī.
Tātad jūs varat būt pārliecināti, vārdus ar apostrofu.
Varbūt pat domu vajadzētu iet tur, bet jūs
redzēt p komplektā 5 mēs tikai aprūpes par vēstuļu un apostrofu.
>> Un tad kā jūs pārstāvēt pati datu struktūra?
Kā jūs pārstāvat saknes Šīs TRIE, lai runāt?
Nu, tāpat kā ar saistīta sarakstu, jūs nepieciešams rādītāju uz pirmo elementu.
Ar TRIE jūs vienkārši nepieciešams viens rādītāju uz pamatā šo TRIE.
Un no turienes jūs varat hash savu ceļu uz leju, dziļāk un dziļāk
uz katru citu mezglu struktūrā.
Tik vienkārši ar to var mēs pārstāvam šo struct.
>> Tagad Meanwhile-- Ak, jautājumu.
>> Mērķauditorija: Kas ir bool vārdu?
>> DAVID Malan: Bool vārds ir tikai šo C iemiesojums
no tā, ko es aprakstīju Šajā ailē šeit, kad
Es sāku sadalot katra Array s elementi divās daļās.
Viens no tiem ir rādītājs uz nākamo mezglu.
Citi ir jābūt kaut kas līdzīgs rūtiņu
teikt jā, tur ir Vārds Daven ka beidzas šeit,
jo mēs negribam, brīdī, Dave.
>> Pat ja Dave būs likumīga vārdu, viņš nevis TRIE
vēl.
Un D ir ne vārds.
Un D-nav vārds vai nosaukums.
Tātad atzīmes norāda tikai vienu reizi jums
skāra šis mezgls ir iepriekšējais ceļš rakstzīmju
faktiski virkne, kas jūs esat ievietots.
Tā ka viss ir bool tur dara mums.
>> Jebkādi citi jautājumi, par mēģinājumiem?
Yeah.
>> Mērķauditorija: Kas ir pārklājas?
Ko darīt, ja jums ir Dave un Daven?
DAVID Malan: Perfect.
Ko darīt, ja jums ir Dave un Daven?
Tātad, ja mēs ievietotu, teiksim segvārdu, par David-- Dave-- D-A-V-E?
Tas ir tiešām super vienkārši.
Tātad, mēs esam tikai gatavojas veikt četrus soļus.
D-A-V-E. Un ko man ir darīt, kad es hit, ka ceturtais mezglu?
Tikai gatavojas pārbaudīt.
Mēs esam jau labi iet.
Darīts.
Četri soļi.
Constant laiks asimptotiski.
Un tagad mēs esam norādīja, ka gan Dave un Daven ir virknes struktūrā.
Tāpēc nav problēma.
Un paziņojums, kā klātbūtni no Daven nebija darīt to
veikt vairāk laika vai mazāk laiks Dave un otrādi.
>> Tātad, ko vēl mēs varam tagad darīt?
Mēs esam izmantojuši šo metaforu pirms paplātes, kas pārstāv kaut ko.
Bet izrādās, ka kaudze paplātes ir faktiski
norādāmais cita abstraktu datu type-- augstāka līmeņa datu struktūra
ka beigās diena ir tikai piemēram, masīvu vai saistītajā sarakstā
vai kaut kas vairāk ikdienišķa.
Bet tas ir interesantāk konceptuāls jēdziens.
Kaudze, piemēram, šo renes šeit Mather,
parasti sauc vienkārši that-- kaudze.
>> Un šāda veida datu struktūras Jums ir divas operations--
Jums ir viens sauc stimuls pievienojot kaut ko kaudze,
piemēram, liekot citu padevi atpakaļ uz augšu kaudze.
Un tad pop, kas nozīmē, ka jūs ņemt augšējais paplātes off.
Bet kas ir galvenais par kaudze ir tas, ka tas ir ieguvuši šo ziņkārīgs īpašība.
Kā ēdamzālē darbinieki ir pārkārtojot paplātes nākamo maltīti,
to, kas būs taisnība par to, kā skolēniem
mijiedarboties ar šo datu struktūru?
Mērķauditorija: Viņi gatavojas pop vienreizējs.
DAVID Malan: Viņi gatavojas pop vienreizējs, cerams top.
Pretējā gadījumā tas ir tikai sava veida stulba lai iet visu ceļu uz leju.
Taisnība?
Datu struktūra nav īsti ļaut jums greifers apakšējo paplāti vismaz
viegli.
Tātad tur ir šis ziņkārīgs īpašums, kaudze
ka pēdējais prece ir būs pirmais ārā.
Un datoru zinātnieki sauc tas LIFO-- pēdējais iekšā, pirmais ārā.
Un tas tiešām ir interesanti pieteikumi.
Tas ne vienmēr ir tik acīmredzama, kā daži citi, bet tā var, protams, būt noderīga,
un tā var, protams, ir jāīsteno pāris dažādos veidos.
>> Tik viens, un faktiski, ļaujiet man nav nodoties to.
Darīsim šo vietā.
Apskatīsim vienu, kas ir gandrīz pati ideja, bet tas ir nedaudz godīgāka.
Taisnība?
Ja jūs esat viens no šiem fanu zēnu vai meitenes, kas tiešām patīk Apple produktiem
un jūs pamodos pulksten 3:00 rindā kādā veikalā
lai saņemtu pašu jaunāko iPhone, jūs varētu būt ievietots rindā uz augšu, kā šis.
>> Tagad rinda ir ļoti apzināti nosaukts.
Tā ir līnija, jo tur ir daži godīgums uz to.
Taisnība?
Tā būtu sava veida iesūc, ja esat got tur pirmais pie Apple Store
bet jums ir efektīvi viszemākais paplāte jo Apple darbinieki tad
pop pēdējo personu, kas faktiski ieguva rindā.
Tātad skursteņi un rindas, lai gan funkcionāli viņi sava veida same--
tas ir tikai šī kolekcija resursu, kas ir
gatavojas augt un shrink-- tur šis taisnīguma aspekts uz to,
vismaz reālajā pasaulē, kur operācijas jūs izmantot
būtiski atšķiras.
Stack-- rinda rather-- ir teikt, ka
divas operācijas: n rindā un d rindā.
Vai jūs varat zvanīt viņiem kāds no lietas numurs.
Bet jūs vienkārši vēlaties, lai attēlotu Priekšstats, ka viens ir pievienojot
un viens galu galā atņemot.
>> Tagad zem motora pārsega, gan kaudze un rinda varētu īstenot kā?
Mēs neiešu kodā tas tāpēc, ka augstāka līmeņa
ideja ir sava veida vairāk acīmredzama.
Es domāju, ko darīt cilvēkiem darīt?
Ja es esmu pirmais cilvēks pie Apple Uzglabāt un tas ir priekšējās durvis,
jūs zināt, es esmu gatavojas stāvēt šeit.
Un nākamais personas gatavojas stāvēt šeit.
Tātad, kādi datu struktūra aizdod sevi rindā?
>> Mērķauditorija: rindā.
DAVID Malan: Nu, rindā.
Pārliecināts.
Kas vēl?
>> Mērķauditorija: saistīts saraksts.
>> DAVID Malan: saistīta uzskaitīt jūs varētu īstenot.
Un saistīts saraksts ir jauki, jo tad tā var pieaugt patvaļīgi ilgi pretstatā
lai ar kādu noteiktu skaitu cilvēku veikalā.
Bet varbūt noteikts skaits vietu ir likumīgs.
Jo, ja tie ir tikai, piemēram, 20 iPhone pirmajā dienā, varbūt
tie tikai nepieciešams masīvs izmēra 20 pārstāvēt šo rindā, kurā
tikai teikt, tagad, kad mēs sākam runāt par šīm augstāka līmeņa problēmas,
Jūs varat īstenot jebkurā vairākos veidos.
Un tur ir iespējams tikai gatavojas būt tirdzniecības off telpā un laikā
vai vienkārši savā kodu sarežģītību.
>> Kas par kaudze?
Nu, kaudze, mēs esam redzējuši pārāk varētu vienkārši šie paplātes.
Un jūs varētu īstenot šo masīvs.
Bet kādā brīdī, ja jūs izmantot masīvu, to, kas notiks ar paplātēm
jūs cenšaties nolikt?
Labi.
Jūs tikai gatavojas varēs iet tik augstu.
Un es domāju, ka Mather viņi faktiski padziļinājumā šajā atvēršanu.
Tik tiešām, tas ir gandrīz tāpat Mather izmanto
masīvs fiksētu lielumu, tāpēc, ka jūs varat tikai
fit tik daudz paplātes šajā atvēršana siena lejā cilvēku ceļgaliem.
Un tā tas varētu būt varētu būt masīva,
bet mēs, protams, var ieviest, ka vairāk parasti ar saistītajā sarakstā.
>> Nu, ko par citu datu struktūras?
Ļaujiet man uzvilkt vienu citu vizuālo šeit.
Kaut ko līdzīgu kā par šeit šo vienu?
Kāpēc tas varētu būt noderīgi, lai būtu ne kaut kā fancy kā TRIE, kas
mēs redzējām bija šīs ļoti plašas mezglus, katrs no kuriem ir masīvs?
Bet ko tad mēs darām kaut ko vairāk vienkārši, kā vecs skola ciltskoku,
Katrā no kura mezgli šeit ir tikai glabāšanai numuru.
Vietā nosaukumu vai pēcnācējs ir tikai uzglabāt vairākus kā šis.
>> Nu, žargons mēs izmantojam datu struktūras ir abi mēģina
un koki, kur trie, atkal, ir tikai viens, kura mezgli ir bloki,
joprojām ir tas, ko jūs varētu izmantot no pakāpē skolā
ja jūs veicāt ģimeni tree-- lapas un saknes
koku un bērniem mātes un to vecvecākus.
Un mēs varētu ieviest koku, piemēram, kā vienkārši kā šī.
Koks, ja to kā mezglu, viens no šajās aprindās, kurai ir vairāki,
tas nav nāksies viens rādītājs, bet divi.
Un, tiklīdz jūs pievienot Otrs rādītājs, jums
faktiski var tagad darīt kārtošanas divdimensiju datiem
struktūras atmiņā.
Daudz, piemēram, divdimensiju masīvs, jūs varat
ir sava veida no divdimensiju saistītie saraksti, bet tie,
kas seko modelis ja tur nav ciklus.
Tas ir patiesi koks ar vienu vecvecāks ceļu šeit, un tad
daži vecāki un bērni, un mazbērni un mazmazbērni.
un tā tālāk.
>> Bet to, kas ir patiešām veikls par šo pārāk, tikai ķircināt jums ar mazliet kodu,
atsaukums rekursijas no awhile atpakaļ, saskaņā ar kuru
Jums uzrakstīt funkciju, kas sevi sauc.
Tā ir skaista iespēja ieviest kaut ko
tāpat recursion, jo uzskata, ka tas.
>> Tas ir koks.
Un es esmu bijis nedaudz anālais ar to, kā Man veselos skaitļus uz ielas.
Tik daudz tā, ka tā ir īpaša name-- bināro meklēšanas koku.
Tagad mēs esam dzirdējuši par bināro meklēt, bet jūs varat
strādāt atpakaļ no šī lieta vārdu?
Kāds ir modelis, kā es ievietota veselos skaitļus šajā kokā?
Tas nav patvaļīgs.
Tur ir daži modelis.
Yeah.
>> Mērķauditorija: mazākie kreisajā pusē.
>> DAVID Malan: Jā.
Mazākie ir pa kreisi.
Lielāks tiem ir labajā pusē.
Tā, ka patiess apgalvojums ir vecāks ir lielāks par kreisajiem bērns,
bet mazāk nekā tās labajā bērnu.
Un tas vien ir pat rekursīvs verbālā definīcija
tāpēc, ka jūs varat pieteikties, ka Tāda pati loģika katram mezglā
un tas tikai dibeni out, gadījumu, ja jums
būs, kad jūs hit viens no lapas, tā sakot,
ja atvaļinājums nav bērnu tālāk.
>> Tagad, kā jūs varētu atrast numuru 44?
Jūs varētu sākt saknē un teikt, hm.
55 nav 44 Tāpēc es gribu iet tiesības vai es gribu, lai iet pa kreisi?
Nu, protams, jūs vēlaties, lai iet pa kreisi.
Un tā tas ir tāpat kā tālruni grāmata piemērs bināro meklēšanu
kopumā.
Bet mēs esam to īsteno Tagad nedaudz vairāk dinamiski
nekā masīvs varētu atļaut.
Un patiesībā, ja jūs vēlaties meklēt pie koda, pēc pirmā acu uzmetiena pārliecināts.
Izskatās, ka visu ķekars līnijas.
Bet tas ir skaisti vienkārši.
Ja jūs vēlaties, lai īstenotu funkciju aicināja meklēt kuras mērķis dzīvē
ir meklēt vērtību piemēram, n, vesels skaitlis,
un jūs esat izturējis kādā vienā pointer-- rādītāju uz mezgla saknes,
drīzāk, šī koka, no kura Jūs varat piekļūt visu citu,
paziņojums, kā vienkāršākā Jūs varat īstenot loģiku.
Ja koks ir nulle, protams, tas nav tur.
Pieņemsim tikai atgriezties viltus.
Taisnība?
Ja jūs puses, tas nekas, tur nekā nav.
>> Cits, ja n ir mazāks nekā koks arrow N- tagad arrow n,
atgādināt mēs iepazīstinājām super īsi otro dienu,
un tas tikai nozīmē, ka de-atsauci rādītāju un apskatīt lauka sauc n.
Tātad tas nozīmē, iet tur un apskatīt lauka sauc n.
Tātad, ja n, vērtību, jūs esat dota, ir mazāks par vērtību koku skaitlim,
kur jūs vēlaties doties?
Pa kreisi.
>> Tātad paziņojums rekursijas.
Es esmu returning-- nav taisnība.
Nav nepatiesa.
Es esmu atpakaļ neatkarīgi atbildi No sarunas ar sevi, iet
n atkal, kas ir lieks, bet to, kas ir nedaudz savādāka?
Kā man padarīt mazāku problēmu?
Es esmu iet tik otro argumentu, nevis saknes koku,
bet pa kreisi bērns šajā gadījumā.
Tāpēc es esmu iet kreisajā bērnam.
>> Tikmēr, ja n ir lielāks nekā mezglu Es esmu šobrīd meklē,
Es meklētu labajā pusē.
Cits, ja koks nav spēkā, un ja elements nav pa kreisi
un tas nav labi, kāda ir lieliski gadījums?
Mēs esam patiešām atraduši mezglu jautājums, un tāpēc mēs atgrieztos taisnība.
>> Tātad mēs esam tikai scratched virsmas Tagad daži no šiem datu struktūras.
Jo problēma noteikti pieci jums izpētīt šos vēl vairāk,
un jums tiks dota jūsu dizains izvēle, kā iet par to.
Ko es gribētu, lai izdarītu secinājumus par ir tikai 30 sekunžu teaser
par to, kas gaida nākamajā nedēļā un ārpus tās.
>> Kā mēs begin-- laimi jums varētu think-- mūsu pāreju lēni
no pasaules C un zemākā līmeņa īstenošanas detaļas,
uz pasauli, kurā mēs varam veikt, lai pašsaprotamu, ka kāds cits ir beidzot
īsteno šos datus konstrukcijas mums,
un mēs sāksim saprast reālā pasaule ir īstenot
tīmekļa programmas un mājas lapas plašāk
un arī ļoti drošība sekas, ka mēs esam tikai
sākuši saskrāpēt virsmu.
Te ir tas, kas mūs sagaida dienās nāk.
>> [VIDEO PLAYBACK]
>> -Viņš Nāca ar ziņu, ar protokolu, visu savu.
Viņš nāca pasaulē nežēlīga ugunsmūri, uncaring maršrutētāji,
un briesmas daudz ļaunāks par nāvi.
Viņš ir ātrs.
Viņš ir spēcīga.
Viņš ir TCP / IP, un viņš dabūja savu adresi.
"Warriors of Net."
[END VIDEO PLAYBACK]
DAVID Malan: Coming nākamnedēļ.
Mēs redzēsim jūs tam.
[VIDEO PLAYBACK]
-Un Tagad, "Deep Domas" ko Daven Farnham.
-David Vienmēr sākas lekcijas ar "viss ir labi."
Kāpēc ne, "Lūk risinājums līdz šīs nedēļas problēmu kopumu "
vai "Mēs dodam jums visiem?"
[Smejas]
[END VIDEO PLAYBACK]