[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. 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]