[Mūzikas atskaņošanai] SPEAKER 1: Nu labi. Ikviens laipni atpakaļ uz sadaļu. Es ceru, ka jūs visi ir veiksmīgi atguvusies no jūsu viktorīnas no pagājušajā nedēļā. Es zinu, tas ir mazliet traks reizēm. Kā jau teicu iepriekš, ja jūs esat ietvaros standarta novirze, nav īsti jāuztraucas par to, jo īpaši par mazāk ērtu sadaļā. Tas ir par to, kur jums vajadzētu būt. Ja jums bija liels, tad lieliski. Kudos uz jums. Un, ja jums justies kā jums ir nepieciešams, mazliet vairāk palīdzēt, lūdzu justies brīvi, lai sasniegtu ārā uz kādu no TFS. Mēs visi esam šeit, lai palīdzētu. 

Tieši tāpēc mēs mācām. Tas ir iemesls, kāpēc es esmu šeit, katru pirmdienu, lai jūs puiši un pie amata stundas ceturtdienās. Tāpēc, lūdzu, justies brīvi let me know ja jūs esat noraizējies par neko vai arī, ja tur ir kaut kas uz viktorīnas kas jums tiešām vēlētos, lai risinātu. 

Tātad darba kārtība šodien ir visu par datu struktūras. Daži no tiem ir tikai būs tikai lai iegūtu Jums iepazīties ar tiem. Jūs nedrīkstat kādreiz īstenot viņiem šajā klasē. Daži no tiem jums būs, piemēram, jūsu Speller PSET. 

Jums ir jūsu izvēle starp hash tabulas un valstīs. Tāpēc mēs noteikti iet pār tiem. Tas būs noteikti vairāk veida augsta līmeņa sadaļā šodien, lai gan, tāpēc, ka tur ir daudz no viņiem, un, ja mēs gājām uz īstenošanas detaļām par visiem šiem, mēs nebūtu pat tikt cauri saistīti saraksti un varbūt mazliet hash tabulu. 

Tā sedz ar mani. Mēs nebrauksim darīt tik daudz kodēšanas šoreiz. Ja jums ir kādi jautājumi par to vai arī jūs vēlaties, lai redzētu to īsteno vai mēģināt to pats, Es noteikti ieteiktu gatavojas study.cs50.net, kas ir piemēri visi no tiem. Tā būs mana powerpoints ar piezīmēm, ka mēs mēdz izmantot, kā arī daži programmēšana vingrinājumi, jo īpaši attiecībā uz lietām tāpat saistītas sarakstiem un bināro koki skursteņi un nianses. Tik nedaudz vairāk augsta līmeņa, kas varētu būt jauki jums puiši. 

Tātad ar to, mēs sāktu. Un arī, yes-- viktorīnas. Es domāju, ka lielākā daļa no jums, kas ir mans sadaļa ir jūsu viktorīnas, bet ikviens nāk vai kādu iemeslu dēļ jums nav, viņi ir tepat priekšā. 

Tā saistīta sarakstus. Es zinu, šāda iet atpakaļ pirms jūsu viktorīnas. Tas bija pirms nedēļas ka mēs uzzinājām par to. Bet šajā gadījumā, mēs vienkārši iet mazliet dziļāk. 

Tad kāpēc mēs varbūt izvēlēties saistīts saraksts pa masīvu? Kas atšķir tos? Jā? 

Mērķauditorija: Jūs varat paplašināt saistīts uzskaitīt pret masīvs ir noteikta izmēra. SPEAKER 1: Labais. Masīvs ir noteikts izmērs savukārt saistīts saraksts ir mainīgs lielums. Tātad, ja mēs nezinām, cik daudz mēs gribam, lai uzglabātu, saistīts saraksts dod mums liels veids, kā to darīt, jo mēs varam vienkārši pievienot uz citu mezglu un pievienot uz cits mezgls un pievienot uz citu mezglu. Bet to, kas varētu būt kompromiss? Vai kāds atceras kompromisu starp masīvu un saistīti saraksti? Mmhmm? 

Mērķauditorija: Jums ir iet cauri visiem ceļu pa saistīts saraksts atrast elementu sarakstā. Masīvā, varat vienkārši atrast elementu. 

SPEAKER 1: Labais. Tātad ar arrays-- 

Mērķauditorija: [dzirdams]. 

SPEAKER 1: Ar blokiem, mēs esam ko sauc brīvpiekļuves. Nozīmē, ka, ja mēs gribam to, kas ir kādreiz piektais punkts saraksta vai piektais punkts mūsu masīvs, mēs varam vienkārši paķert to. Ja tas ir saistīts saraksts, mums ir atkārtot cauri, vai ne? Tātad piekļūstot elements masīvs ir nemainīgs laiks, savukārt ar saistīts saraksts tas visticamāk, būs lineārais laiks, jo varbūt Mūsu elements ir visu ceļu beigās. Mums ir meklēt caur visu. Tātad ar visiem šiem datiem struktūras mēs ejam lai tērēt nedaudz vairāk laika, kādi ir plusi un negatīvi. Ja iespējams, mēs vēlamies izmantojiet vienu pār otru? Un tas ir sava veida lielāks lieta atņemt. 

Tāpēc mēs esam šeit definīcija mezglā. Tas ir tāpat kā viens elements mūsu saistīts saraksts, labi? Tātad mēs visi esam pazīstami ar mūsu typedef statņi, ko mēs devāmies pār pārskatā pēdējo reizi. Tas bija galvenokārt tikai radot cits datu tips, ko mēs varētu izmantot. 

Un šajā gadījumā, tas ir daži mezgla kas notiks dažas skaitlim. Un tad, kas ir otrā daļa šeit? Ikviens? 

Mērķauditorija: [dzirdams]. 

SPEAKER 1: Jā. Tas ir rādītājs, uz nākamo mezglu. Tātad tas faktiski ir jābūt šeit. Tas ir rādītājs tipa mezglu uz nākamo lieta. Un tas, ko viņi ietver mūsu mezglā. Atdzist. 

Viss ir labi, tāpēc ar meklēšanu, kā mēs bijām vienkārši sakot, pirms puses, ja jūs esat iet meklēt, izmantojot, Jums ir faktiski atkārtot caur savu saistīts saraksts. Tātad, ja mēs meklējam skaitu 9, mēs varētu sākt mūsu galvas un ka mums norāda sākumā mūsu saistīts saraksts, labi? Un mēs sakām, OK, vai tas mezgls ietver numuru 9? Nē? 

Visas tiesības, dodieties uz nākamo. Sekot to. Vai tas satur numuru 9? Nē. Sekojiet nākamo. 

Tāpēc mums ir faktiski atkārtot caur mūsu saistīts saraksts. Mēs nevaram vienkārši doties tieši uz vietu, kur 9 ir. Un, ja jūs puiši tiešām vēlaties redzēt kādu pseido-koda tur augšā. Mums ir daži meklēšanas funkciju šeit kas ņem in-- ko tas veic ar? Ko jūs domājat? Tik viegli vienu. Kas tas ir? Mērķauditorija: [dzirdams]. SPEAKER 1: skaits, mēs meklējam. Taisnība? Un kas būtu tas atbilst? Tas ir rādītājs, lai? 

Mērķauditorija: mezglā. 

SPEAKER 1: mezgla sarakstam ka mēs meklējam, vai ne? Tāpēc mums ir daži mezgli ir rādītājs šeit. Tas ir punkts, kas notiek, lai faktiski atkārtot, izmantojot mūsu sarakstā. Mēs, kas tas ir vienāds uzskaitīt tāpēc, ka tas ir tikai nosakot to vienāds ar sākuma mūsu saistīts saraksts. 

Un, lai gan tas nav NULL, bet mums vēl ir lietas, kas mūsu sarakstā, pārbaudiet, lai redzētu, ka mezgls ir skaitlis mēs meklējam. Atgriezties taisnība. Pretējā gadījumā, atjaunina to, labi? 

Ja tas ir NULL, mēs izietu mūsu kamēr cilpa un atgriezties viltus jo tas nozīmē, ka mēs esam nav atradis. Vai visi get to, kā tas darbojas? OK. 

Tātad ar ievietošanas, jūs ir trīs dažādos veidos. Jūs varat prepend, jūs varat pievienot un jūs varat ievietot asorti. Šajā gadījumā, mēs esam gatavojas darīt prepend. Vai kāds zina, kā tos trīs lietas var atšķirties? 

Tātad prepend nozīmē, ka jūs varat ievietot tā priekšā savu sarakstu. Tā, ka tas nozīmētu, ka nav svarīgi, kādas ir jūsu mezgls ir, vienalga kāda vērtība ir, jūs gatavojas nodot to tepat priekšā, OK? Tas būs pirmais elements savu sarakstu. 

Ja jūs pievienot to, tas notiek lai dotos uz atpakaļ savu sarakstu. Un ievietot asorti nozīmē, ka jūs esat ielikšu faktiski uz to vietu kur tas saglabā savu saistīts saraksts sakārtots. Atkal, kā jūs izmantojat tiem, un, kad lietojat viņiem būs atkarīgs no jūsu gadījumu. Ja tas nav nepieciešams sakārtots, prepend mēdz lai būtu, ko lielākā daļa cilvēku izmantot, jo jums nav ir iet cauri visam sarakstam atrast beigām pievienot to, vai ne? Jūs varat tikai stick to tiesības. 

Tātad mums būs jāiet cauri ievietošanas 1 tieši tagad. Tātad viena lieta, ko es esmu gatavojas ļoti ieteiktu šo PSET ir izdarīt lietas, kā vienmēr. Tas ir ļoti svarīgi, ka jūs atjaunināt Jūsu norādes pareizā secībā jo, ja jūs atjaunināt tos nedaudz bojātas, jūs gatavojas galu galā zaudēt daļu no sava saraksta. 

Tā, piemēram, šajā gadījumā, mēs stāsta galvu tikai punkts 1. Ja mēs vienkārši darīt nesaglabājot šo 1, mums nav ne jausmas, ko 1 jānorāda tagad tāpēc, ka mēs esam zaudējuši, ko galva norādīja uz. Tik viena lieta atcerēties kad jūs darāt prepend ir, lai saglabātu to, ko galvas norāda uz pirmo, Tad pārdalīt to, un pēc tam atjaunināt kas savu jauno mezglu vajadzētu norādīt uz. Šajā gadījumā, tas ir viens no veidiem, kā to darīt. 

Tātad, ja mēs būtu darījuši to šādā veidā kur mēs tikko no jauna galvu, mēs zaudējam būtībā OUR visu sarakstu, vai ne? Viens veids, kā to izdarīt, ir, lai būtu 1 punktu, lai nākamais, un tad ir galvas punktu 1. Vai jūs varat darīt kaut kas līdzīgs pagaidu uzglabāšana, ko es runāju par. 

Bet no jauna piešķirot Jūsu norādes pareizā secībā būs ļoti, ļoti svarīgi, lai šajā PSET. Pretējā gadījumā jūs nāksies hash tabulas vai izmēģināt, kas ir tikai būs tikai daļa no vārdiem, kas jums vēlas, un tad you're-- mmhmm? Mērķauditorija: Kāds bija īslaicīga uzglabāšanas lieta, ko jūs runājāt par? SPEAKER 1: pagaidu uzglabāšanu. Tātad būtībā cits veids, kā jūs varētu to izdarīt ir saglabāt galvu kaut ko, piemēram, uzglabāt to pagaidu mainīgo. Piešķirt to 1 un tad atjaunot 1. punktam lai kāds galvu izmanto, lai norādītu uz. Šis veids ir acīmredzami vairāk elegants, jo jums nav nepieciešama pagaidu vērtību, bet tikai piedāvāt vēl viens veids, kā to izdarīt. Un mēs faktiski darīt ir daži kods to. Tātad saistīta sarakstu, mēs tiešām ir daži kodu. Tātad ievietot šeit, tas ir prepending. Tātad šī ievada to galvas. 

Tātad pirmā lieta, jums ir nepieciešams izveidot jaunu mezglu, protams, un pārbaudiet NULL. Vienmēr ir labi. Un tad jums ir nepieciešams piešķirt vērtības. Ikreiz, kad jūs izveidot jaunu mezglu, jums nezinu, kas tas ir, norādot uz nākamo, lai jūs vēlaties, lai sāktu to null. Ja tas galu galā norāda uz kaut ko cits, tas izpaužas no jauna, un tas ir labi. Ja tā ir pirmā lieta, sarakstā, tai ir norādīt uz NULL, jo tas ir gals saraksta. 

Tātad, lai ievietotu to, mēs redzam šeit mēs tiek piešķirot nākamo vērtību mūsu mezglā lai būtu kāds galva, kas ir tas, ko mums bija šeit. Tas ir tas, ko mēs tikko izdarījām. Un tad mēs esam piešķirot galvu punktam mūsu jaunajā mezglā, jo atceros, jaunais ir daži rādītājs uz mezglu, un tas ir tieši tas, ko galva ir. Tieši tāpēc mēs ir šī bultiņas accessor. Forši? Mmhmm? 

Mērķauditorija: Vai mums ir sāktu jaunu Next null, pirmkārt, vai arī mēs varam vienkārši sāktu to uz galvas? 

SPEAKER 1: Jauns nākamais jābūt NULL, lai sāktu jo jūs nezināt kur tas būs. Arī tas ir sava veida vienkārši patīk paradigmu. Jūs noteikti tas ir vienāds ar NULL tikai, lai pelnītu Pārliecinieties, ka visi jūsu bāzes ir iekļauti Pirms jūs to darāt, ka jebkuru pārcelšanu citā amatā jūs vienmēr garantēts, ka tā būs ir vērsta uz noteiktu vērtību pret kā garbage vērtību. Tāpēc, ka, jā, mēs piešķirt Jaunais nākamā automātiski, bet tas ir vairāk, tāpat kā laba prakse, lai sāktu to Šādā veidā un pēc tam atkārtoti piešķirt. 

Labi, tāpēc divkārt saistīti sarakstus tagad. Ko mēs domājam? Kas ir atšķirīgs ar divkārt saistīta sarakstus? 

Tātad mūsu saistīti sarakstos, mēs varam pārvietot tikai vienā virzienā, labi? Mums ir tikai blakus. Mēs varam iet tikai uz priekšu. 

Ar divkārt saistīta sarakstā mēs varam arī pārvietot atpakaļ. Tāpēc mums ir ne tikai numurs, ko mēs gribam, lai uzglabātu, mums ir, ja tas norāda uz nākamo un kur mēs tikko nāca no. Tātad tas ļauj daži labāk šķērsošana. 

Tāpēc divkārt saistīti mezglus, ļoti līdzīgs, vai ne? Tikai tagad atšķirība ir mums ir nākamais un iepriekšējais. Tā ir vienīgā atšķirība. 

Tātad, ja mēs būtu prepend vai append-- mums nav nekādu kods šo augšu here-- bet, ja tu būtu, lai mēģinātu ievietojiet to, ka svarīga lieta ir nepieciešams veikt pārliecināts, ka jūs esat piešķirot gan savu iepriekšējo un Jūsu Nākamais rādītājs pareizi. Tātad šajā gadījumā, jūs varētu ne tikai inicializēt blakus, Jūs inicializēt iepriekšējo. Ja mēs esam pie galvas saraksta, mēs tas ne tikai padarīs galvu vienāds jaunu, bet mūsu jaunais iepriekšējā vajadzētu norāda uz galvas, vai ne? 

Tas ir vienīgā atšķirība. Un, ja jūs vēlaties vairāk praksi ar tos ar saistītiem sarakstiem, ar ievietojot dzēšanu, ar ieliktni stājas asorti sarakstā, lūdzu, pārbaudiet study.cs50.net. Tur ķekars lielu vingrinājumi. Es ļoti ieteiktu to. Novēlu mums bija laiks iet caur tiem bet tur ir daudz datu struktūras tikt cauri. 

Labi, tā hash tabulas. Tas ir iespējams, visvairāk noderīga bit savu PSET šeit, jo jūs esat būs Īstenojot vienu no šiem, vai mēģināt. Man tiešām patīk hash tabulas. Viņi diezgan vēss. 

Tātad, būtībā, ko notiek, ir hash tabulu ir tad, kad mums tiešām ir nepieciešams ātri ievietošana, dzēšana, un lookup. Tās ir lietas, ko mēs esam prioritāti ar hash tabulā. Viņi var iegūt diezgan liels, bet kā mēs redzēsim ar mēģinājumiem, ir lietas, kas ir daudz lielāks. 

Bet būtībā, visi hash tabula ir jaukšanas funkcija kas stāsta jums, kas spainis likt katram no jūsu datiem, katru no jūsu elementu. Vienkāršs veids, kā domāt par hash tabulas ir tas, ka tā ir tikai spaiņi lietas, tiesības? Tātad, ja jums ir šķirošanas lietas ar tāpat kā pirmajam burtam savu vārdu, tas ir veids kā hash tabulu. 

Tātad, ja es būtu grupai jūs puiši ir grupās, kurš vārds sākas ar vairāk nekā šeit, vai kādam citam, ir dzimšanas diena ir janvārī, februārī, martā, kāds, kas ir efektīvi radot hash tabulu. Tas ir tikai radot spaiņus, ka Jūs kārtot elementus lai jūs varētu atrast tos vieglāk. Tātad šādā veidā, kad man ir nepieciešams lai atrastu vienu no jums, Man nav meklēt caur katru no jūsu vārdiem. Es varu būt, piemēram, ak, es zinu, ka Danielle dzimšanas diena ir in-- AUDITORIJA: --April. SPEAKER 1: Aprīlis. Tāpēc es izskatos manā aprīlis spainis, un ar jebkuru luck, viņa būs tikai viens tur un mans laiks bija konstanti šajā ziņā, tā kā, ja man ir jāskatās cauri visai ķekars cilvēku, tas gatavojas veikt daudz ilgāk. Tātad hash tabulas ir tiešām tikai spaiņos. Vienkāršs veids, kā domāt par tiem. 

Tik ļoti svarīga lieta par hash tabulu ir hash funkcija. Tātad lietas, es tikai runāju par, piemēram, Jūsu pirmais burts no jūsu vārds vai jūsu dzimšanas dienas mēnesis, tās ir idejas, kas patiešām korelē ar hash funkciju. Tas ir tikai veids, kā izlemt, kas spainis jūs elements tērēta, OK? Tātad šo PSET, jūs varat meklēt diezgan daudz jebkuru hash funkciju vēlaties. 

Nav jābūt savu. Ir daži patiešām atdzist tie, kas tur, ka darīt visādas trakas math. Un, ja jūs vēlaties, lai jūsu Pareizrakstība super ātri, Es noteikti izskatās vienā no tiem. 

Bet ir arī vienkārši tie, piemēram, compute no vārdiem, piemēram, summa katrs burts ir vairākas. Aprēķināt summu. Kas nosaka spaini. Viņi arī ir viegli tiem, kas ir tāpat kā visi ir šeit, visu B ir šeit. Kāds no tiem. 

Būtībā, tas tikai stāsta jums, kas masīvs indekss jūsu stihija vajadzētu iedziļināties. Vienkārši izlemjot bucket-- tas viss hash funkcija. Tātad šeit mums ir piemērs, kas ir tikai pirmais burts virknes ka man bija tikai runā par. 

Tātad jums ir kāda hash, kas ir tikai pirmais burts no jūsu stīgu mīnus A, kas sniegs jums dažus skaitlis no 0 līdz 25. Un ko jūs vēlaties darīt, ir pārliecinieties, ka tas ir izmēru jūsu hash table-- cik spaiņi tur ir. Ar daudziem no šiem hash funkcijas, viņi būs atgriežas vērtības, kas varētu būt tālu virs skaita spaiņos ka jūs faktiski ir Jūsu hash tabulu, tāpēc jums ir nepieciešams, lai Noteikti un mod tiem. Pretējā gadījumā tas būs teikt, Ak, tas būtu spainis 5000 bet jums ir tikai 30 spaiņi jūsu hash tabulā. Un, protams, mēs visi zinām, ka ir gatavojas rezultātā daži crazy kļūdas. Tāpēc pārliecinieties, lai mod ar izmērs jūsu hash tabulu. Atdzist. Tik sadursmes. Vai visi labi līdz šim? Mmhmm? 

Mērķauditorija: Kāpēc tas tā atgriezt tik milzīgu vērtību? 

SPEAKER 1: Atkarībā no algoritma ka jūsu hash funkcija izmanto. Dažas no tām darīs traks pavairošana. Un tas viss ir par iegūt vienmērīgs, tāpēc tie daži patiešām trakas lietas dažreiz. Tas ir viss. Kaut kas cits? OK. 

Tik sadursmes. Būtībā, kā jau teicu iepriekš, kas labākajā gadījumā, jebkurš spainis es ieskatos ir nāksies viena lieta, tāpēc man nav skatīties vispār, vai ne? Es nu zinu, tas ir tur, vai tas ir nav, un tas, ko mēs patiešām vēlamies. Bet, ja mums ir desmitiem tūkstošu datu punkti un mazāk par šo numuru kausu, mēs esam nāksies sadursmes kur galu galā kaut kas nāksies nonākt spainis, kas jau ir elements. 

Tātad jautājums ir, ko mums darīt šādā gadījumā? Ko mēs darām? Mums jau ir kaut kas tur? Vai mēs vienkārši mest to ārā? 

Nē. Mums ir, lai saglabātu gan no tiem. Tātad tā, ka mēs parasti darīt, ir tas, ko? Kas ir datu struktūra mēs tikko runājām? Mērķauditorija: Saistīts saraksts. SPEAKER 1: saistīts saraksts. Tātad tagad, tā vietā, lai katrs no šiem spaiņi tikai ar vienu elementu, tas notiek, lai saturētu saistīts saraksts elementi, kas tika sajaukts tajā. Labi, tomēr ikviens veida saņemt šo ideju? Tāpēc, ka mēs nevarētu būt masīvs jo mēs nezinām, cik daudzas lietas gribam būt tur. Saistīts saraksts ļauj mums ir tikai precīzu skaitu, kas tiek sajaukts vērā, ka spainis, vai ne? 

Tik lineāra zondēšana ir būtībā tas idea-- tas ir viens veids, kā tikt galā ar sadursmes. Ko jūs varat darīt, ir tad, ja tas lieta, ogu tika sajaukts uz 1 un mums jau ir kaut kas tur, jūs vienkārši saglabāt iet uz leju, līdz Jūs atradīsiet slotā. Tas ir viens veids, kā rīkoties ar to. Otrs veids, kā rīkoties tas ir ar to, ko mēs tikko called-- saistīta saraksts sauc virknes intervāli. 

Tātad šī ideja darbojas, ja Jūsu hash tabulu jūs domājat ir daudz lielāks, nekā Jūsu datu kopums vai ja jums vēlaties, lai mēģinātu samazināt Ķēžu līdz brīdim, kad tas ir absolūti nepieciešams. Tātad viena lieta ir lineāra zondēšana, protams, nozīmē ka jūsu hash funkciju nav gluži tik noderīgs tāpēc, ka jūs gatavojas galu galā, izmantojot Jūsu hash funkciju, nokļūšanai uz punktu, Jūs Linear zonde uz leju, lai kaut kur tas ir pieejams. Bet tagad, protams, kaut kas cits, kas nonāks tur, jūs nāksies meklēt vēl tālāk uz leju. 

Un tur ir daudz vairāk meklēšana izdevumi, kas tērēta ievadot elements Jūsu hash tabulā tagad, vai ne? Un tagad, kad jūs iet un mēģināt atrast ogu atkal, jūs gatavojas hash to, un tas notiek, lai pateikt, oh, meklēt spainī 1, un tas nebūs spainis 1, lai jūs esat nāksies traversa ar pārējo tiem. Tātad, tas ir dažkārt noder, bet vairumā gadījumu, mēs ejam, lai teikt, ka virknes intervāli ir tas, ko jūs vēlaties darīt. 

Tātad, mēs runājām par to agrāk. Man mazliet priekšā sevi. Bet virknes intervāli ir būtībā, ka katrs spainis jūsu hash tabulas ir tikai saistīts saraksts. 

Tātad vēl viens veids, vai vairāk tehniska veids, kā domāt par hash tabulas ir, ka tas ir tikai masīvs savienoto sarakstiem, kas kad jūs esat rakstiski savu vārdnīcu un jūs mēģināt ielādēt to, domāt par to, kā masīvs saistītas sarakstu būs daudz vieglāk lai jūs varētu sākt darbību. 

Mērķauditorija: Tātad hash tabulu ir iepriekš noteikta izmēra, kā [dzirdams] spaiņos? 

SPEAKER 1: Labais. Tātad, tas ir noteiktu skaitu spaiņi, ka jūs determine-- ko jūs guys vajadzētu justies brīvi spēlēt ar. Tas var būt diezgan vēss lai redzētu, kas notiek kā jūs mainītu savu segmentu skaitu. Bet jā, tā ir noteikts skaits spaiņiem. Kas ļauj jums fit, kā daudzi elementi, kā jums nepieciešams tas ir atsevišķs ķēžu rādītāju, kur jums ir saistīti sarakstus katrā spainī. Tas nozīmē, ka jūsu hash tabulu būs tieši izmērs ka jums to vajag būt, vai ne? Tas ir viss punkts saistītas sarakstus. Atdzist. 

Tātad visi OK tur? Labi. Ah. Kas tikko notika? Tiešām tagad. Uzminiet, kāds ir nogalināšanu mani. 

Labi, mēs ejam, lai iedziļināties stīs, kas ir nedaudz traks. Man patīk hash tabulas. Es domāju, ka viņi tiešām forši. Mēģina ir cool, too. 

Lai vai kāds atcerēties to izmēģināt ir? Jums būtu devusies vairāk tā īsi lekciju? Vai atceraties veida, kā tas darbojas? Mērķauditorija: Es esmu tikai māj ka mēs iet pār to. SPEAKER 1: Mēs iet pār to. Labi, mēs patiešām gatavojas iet pār to tagad ir tas, ko mēs esam sakot. 

Mērķauditorija: Tas ir par izguves koku. 

SPEAKER 1: Jā. Tas ir izguves koks. Awesome. Tik viena lieta, lai paziņojuma šeit ir tas, ka mēs meklē atsevišķas rakstzīmes šeit, vai ne? 

Tātad, pirms ar mūsu hash funkciju, mēs Tika meklē vārdiem kopumā, un tagad mēs meklējam vairāk pie rakstzīmēm, vai ne? Tāpēc mums ir Maxwell nekā šeit un Mendel. Tātad būtībā try-- veids, kā domāt par šo ir tas, ka katrs līmenis šeit ir masīvs burtiem. Tātad šī ir jūsu saknes mezglu šeit, vai ne? Tas ir visas rakstzīmes alfabēts sākumam katru vārdu. 

Un ko jūs vēlaties darīt, ir teiksim, OK, mums ir dažas M vārdu. Mēs ejam meklēt Maxwell, tāpēc mēs ejam uz M. Un M punktiem veselu cits masīvs, kur katrs Vārds, kamēr pastāv ir vārds, kas ir kā otro burtu, tik ilgi, kamēr tur ir vārds, kas ir B, kā otro burtu, tas būs rādītājs dodas uz kādu nākamo masīvs. 

Tur, iespējams, nav vārds, MP kaut, tāpēc pie P pozīciju šajā masīvs, tas būtu vienkārši NULL. Tā varētu teikt, OK, nav vārdu kas ir M, kam seko P, OK? Tātad, ja mēs domājam par to, katru viena no šīm mazajām lietām faktiski ir viens no šiem lieli bloki no A līdz Z. Tātad, kas varētu būt viens no lietām tas ir sava veida atmaksas izmēģināt? 

Mērķauditorija: atmiņas daudz. 

SPEAKER 1: Tas ir ton atmiņas, vai ne? Katrs no šiem blokiem šeit pārstāv 26 vietas, 26 elementu masīvu. Tāpēc mēģina nokļūt neticami telpa smags. 

Bet tie ir ļoti ātri. Tik neticami ātri, bet tiešām telpu neefektīva. Veida ir izdomāt no kuriem viens jūs vēlaties. Tie ir patiešām foršs jūsu PSET, bet tie aizņem daudz atmiņas, lai jūs tirdzniecības off. Yeah? 

Mērķauditorija: Vai būtu iespējams izveidot izmēģināt un pēc tam kad jums ir visas dati to, ka jūs need-- Es nezinu, ja tas būtu lietderīgi. Man bija atbrīvojoties no visiem NULL rakstzīmes, bet pēc tam jūs nevarētu indeksēt them-- 

SPEAKER 1: Jums joprojām ir nepieciešams. 

Mērķauditorija: - tāpat katru reizi. SPEAKER 1: Jā. Jums ir nepieciešams NULL rakstzīmes ļaut jūs zināt, ja tur nav vārdu tur. Ben jums bija kaut ko vēlaties? OK. Labi, tāpēc mēs ejam iet mazliet vairāk tehniskajā detalizēti aiz mēģināt un strādāt ar piemēru. 

Labi, tāpēc tas ir viens un tas pats. Tā kā saistītajā sarakstā, mūsu galvenais veida of-- kas ir vārds es gribu? - piemēram, celtniecības bloku bija mezglā. In izmēģināt, mums ir arī mezglu, bet tas ir noteikts savādāk. 

Tātad mums ir dažas bool ka atspoguļo to, vai vārda patiešām pastāv šajā vietā, un pēc tam mums ir dažas masīvs here-- vai, pareizāk sakot, tas ir rādītājs uz masīvs 27 rakstzīmes. Un tas ir, šajā gadījumā, šī 27-- Es esmu pārliecināts, ka jums visiem ir, piemēram, pagaidiet, ir 26 burti alfabētā. Kāpēc mums ir 27? 

Tātad, atkarībā no kā jūs to īstenotu, tas ir no PSET kas atļauta apostrofus. Tātad, tāpēc papildus vienu. Jūs arī ir dažās gadījumi null terminatora tiek iekļauts kā viens no rakstzīmes, ka tas ir jāļauj, un tas, kā viņi pārbauda to redzēt, ja tas ir vārda beigām. Ja jūs interesē, izbraukšana Kaspars video study.cs50, kā arī Wikipedia ir dažas labas resursus tur. 

Bet mēs esam gatavojas iet cauri tikai veida par to, kā jūs varētu strādāt caur mēģināt ja jūs esat dota vienu. Tātad mums ir super vienkāršs vienu šeit ir vārdi "sikspārnis" un "Zoom" tiem. Un, kā mēs redzam šeit, tas maz vietas šeit pārstāv mūsu bool ka saka, jā, tas ir vārds. Un tad tas ir mūsu bloki no burtiem, vai ne? 

Tātad mēs gatavojamies iet cauri meklējot "sikspārnis" šajā mēģināt. Tātad sākas augšā, vai ne? Un mēs zinām, ka b atbilst otrais indekss, otrais elements šajā masīvā, jo a un b. Tātad aptuveni otrais. 

Un tā saka, OK, atdzesē, izriet, ka uz nākamais masīvs, jo, ja mēs atceramies, tā nav, ka katrs no šiem faktiski satur elementu. Katrs no šiem blokiem satur rādītāju, vai ne? Tā ir būtiska atšķirība, lai padarītu. 

Es zinu, tas ir gatavojas be-- mēģina ir tiešām grūti iegūt par pirmo reizi, pat tad, ja tas ir otro vai trešo reizi un tas joprojām ir sava veida no šķietams grūti, Es apsolu, ja jums iet skatīties īsa atkal rīt, tas būs iespējams veikt daudz lielāka jēga. Tas aizņem daudz sagremot. Es joprojām reizēm esmu piemēram, pagaidiet, kas ir mēģināt? Kā es varu izmantot šo? 

Tātad, mēs ir b šajā gadījumā, kas ir mūsu otrais rādītājs. Ja mums būtu, teiksim, c vai d vai jebkurš cits burts, mums ir nepieciešams, lai karti, ka atpakaļ uz indeksu Mūsu masīva ka atbilst. Lai mēs varētu veikt, piemēram, rchar un mēs vienkārši atņemt off kartēt to no 0 līdz 25. Ikviens labs kā mēs map mūsu rakstzīmes? OK. 

Tātad mēs ejam uz otru, un mēs redzēt, ka, jā, tas nav NULL. Mēs varam pāriet uz šo nākamo masīva. Tātad mēs ejam uz šo nākamo masīva šeit. 

Un mēs sakām, OK, tagad mēs ir nepieciešams, lai redzētu, vai ir šeit. Ir null vai to dara reāli virzīties uz priekšu? Tātad faktiski pārceļas nosūtīt šajā masīvā. Un mēs sakām, OK, t ir mūsu pēdējais burts. Tātad mēs ejam uz t pie indeksa. Un tad mēs virzāmies uz priekšu tāpēc, ka tur ir vēl viens. Un tas viens būtībā saka, ka, jā, tā saka, ka ir vārds here-- ka, ja jums sekot šo ceļš, jūs esat ieradušies pie vārda, ko mēs zinām, ir "bat." Jā? 

Mērķauditorija: Vai tas ir standarts, lai būtu, ka kā indekss 0 un pēc tam ir sava veida pie 1 vai ir beigās? 

SPEAKER 1: Nē. Tātad, ja mēs atskatāmies uz mūsu deklarācija šeit, tas ir loģiska, tāpēc tas ir savs elements jūsu mezglā. Tātad, tas nav daļa no masīva. Atdzist. Tātad, kad mēs beidzam vārdu, un mēs esam šajā masīvs, ko mēs vēlamies darīt ir do čeku par tas vārds. Un šajā gadījumā tā varētu atgriezties jā. 

Tātad uz šo piezīmi, mēs zinām, ka "Zoo" - Mēs zinām, kā cilvēki, kas "zoo" ir vārds, tiesības? Bet mēģināt šeit būtu saka, nē, tas nav. Un tas būtu teikt, ka tāpēc, ka mēs nav noteikusi to kā vārdu šeit. Pat ja mēs varam traversa līdz šim masīva, tas izmēģināt teiktu, ka nē, zoo nav jūsu vārdnīcā tāpēc, ka mums nav izraudzīta to kā tādu. 

Tik viens veids, kā to izdarīt that-- Ak, piedodiet, tas viens. Tātad, šajā gadījumā, "zoo" nav vārdu, bet tas ir mūsu mēģināt. Bet šo vienu, teiksim, mēs gribam to ieviest vārdu "pirts", kas notiek ir mēs sekojam through-- B, A, t. Mēs esam šajā masīvā, un mēs ejam meklēt h. 

Šajā gadījumā, kad mēs apskatīt rādītāja pie h, tas norādot uz null, OK? Tātad, ja vien tas ir skaidri norādot uz citu masīvu, jūs pieņemt, ka visas norādes Šajā masīvā ir norāda null. Tātad, šajā gadījumā, h norādot null tāpēc mēs nevaram darīt neko, lai tā būtu arī atgriezīsies false, "vannas" nav šeit. Tāpēc tagad mēs esam patiesībā gatavojas iet cauri Kā mēs tiešām teikt ka "zoo" ir mūsu mēģināt. Kā mēs ievietot "Zoo" mūsu mēģināt? Tātad, tādā pašā veidā, ka mēs sākās ar mūsu saistīts saraksts, sākam pie saknes. Ja šaubāties, sākas sakne šīm lietām. 

Un mēs sakām, OK, z. z pastāv šajā, un tā dara. Tātad jūs pārvietojas uz savu nākamo masīvs, OK? Un tad uz nākamo, mēs sakām, OK, tas o pastāv? Tā dara. Tas vēlreiz. 

Un tā uz mūsu nākamo, mēs jau teicām, OK, "zoo" jau pastāv šeit. Viss, kas mums jādara, ir noteikts šī vienlīdzīgā uz true, ka tur ir vārds tur. Ja tu būtu jāievēro visu līdz pirms šī brīža, tas ir vārds, tāpēc vienkārši iestatīt tā vienāds ar tādu. Jā? 

Mērķauditorija: Tātad tas, ka nozīmē, ka "ba" ir vārds arī? 

SPEAKER 1: Nē. Tātad šajā gadījumā, "ba", mēs iegūtu šeit, mēs varētu teikt, ir tas vārds, un tas joprojām nebūs. OK? Mmhmm? 

Mērķauditorija: Tātad, kad jums tas ir vārds, un jūs sakāt: jā, tad tas būs doties uz m? 

SPEAKER 1: Tātad tas ir jādara with-- jūs iekraušana to. Jūs sakāt "zoo" ir vārds. Kad jūs doties uz check-- tāpat, ka jūs vēlaties teikt, nozīmē "zoo" pastāv šajā vārdnīcā? Jūs tikai gatavojas meklēt "zoo" un pēc tam pārbaudiet, lai redzētu, vai tas ir vārds. Jūs nekad gatavojas pārvietot līdz m, jo ​​tas nav to, ko jūs meklējat. 

Tātad, ja mēs tiešām vēlējāmies pievienot "vanna" šajā izmēģināt, mēs varētu darīt to pašu kā mēs to darījām ar "zooloģisko dārzu," izņemot, mēs redzam, ka tad, kad mēs mēģināt nokļūt h, tas neeksistē. Tātad, jūs varat domāt par to kā mēģinot pievienot jaunu mezglu uz saistīta sarakstā, lai mēs būtu nepieciešams, lai pievienotu citu viens no šiem blokiem, piemēram, tā. Un tad tas, ko mēs darām, ir, mēs vienkārši noteikt h Šī masīva norādot uz šo elementu. 

Un tad to, kas mēs vēlamies darīt šeit? Pievienot tas ir vienāds ar taisnība jo tas ir vārds. Atdzist. Es zinu. Mēģina nav visvairāk aizraujošu. Ticiet man, es zinu. 

Tik viena lieta saprast ar mēģina, Es teicu, viņi ir ļoti efektīva. Tātad, mēs esam redzējuši viņi aizņem ton vietas. Viņi veida mulsinoši. Tātad, kāpēc mēs kādreiz izmantot šos? Mēs izmantojam šo viedokli, jo viņi neticami efektīvs. 

Tātad, ja jūs kādreiz meklējat up vārdu, jums ir tikai ko ierobežo garumu vārda. Tātad, ja jūs meklējat vārds, kas ir garums pieci, jūs tikai kādreiz nāksies veikt ne vairāk kā piecus salīdzinājumiem, OK? Tāpēc tas padara to būtībā nemainīgs. Tāpat ievietošanas un lookup ir nemainīgi laiks. 

Tātad, ja jūs nekad nevar saņemt kaut pastāvīgā laikā, tas ir tik labi, kā tas izpaužas. Jūs nevarat saņemt labāk nekā konstante laiks šīm lietām. Tātad, kas ir viens no milzīgs plusiem mēģina. 

Bet tas ir daudz vietas. Tātad jums veida ir jāizlemj kas ir vairāk svarīgi, lai jums. Un šodienas datoriem, telpa, kas mēģināt var aizņemt varbūt neietekmē Jums, ka daudz, bet varbūt jums ir darīšana ar kaut ko ka ir daudz, daudz vairāk lietas, un mēģināt vienkārši nav saprātīgi. Jā? 

Mērķauditorija: Pagaidiet, tāpēc jums ir 26 burti katru vienu? 

SPEAKER 1: Mmhmm. Jā, jums ir 26. Jums ir dažas ir vārds, marķieri, un pēc tam Jums ir 26 norādes katrā vienu. Un viņi point-- 

Mērķauditorija: Un katrs 26, viņi katrs ir 26? 

SPEAKER 1: Jā. Un tas ir iemesls, kāpēc, kā jūs varat redzēt, tas izplešas diezgan strauji. Labi. Tāpēc mēs esam gatavojas nokļūt kokiem, kas Es jūtos kā ir vieglāk un, iespējams, būs būt jauka mazliet atelpu No mēģina tur. Tik cerams, lielākā daļa no jums esmu redzējis koku pirms tam. Nepatīk diezgan tiem ārpus, ko es nezinu, ja kāds gāja ārā nesen. Es devos ābolu pacelt šīs nedēļas nogalē, un ak mans Dievs, tas bija skaisti. Es nezināju lapas varētu izskatīties, ka diezgan. 

Tātad tas ir tikai koks, labi? Tas ir tikai daži mezgla, un tas norāda uz ķekars citiem mezgliem. Kā jūs redzēt šeit, tas ir sava veida atkārtotu tēmu. Mezglus norādot mezgliem ir sava veida būtība daudzu datu struktūras. Tas vienkārši ir atkarīgs, kā mēs tos norāda uz otru un kā mēs traversa caur tiem un kā mēs ievietot lietas, kas nosaka to atšķirīgās īpašības. 

Tāpēc tikai daži terminoloģiju, kas es esmu, ko izmanto pirms tam. Tā sakne ir viss, kas ir pašā augšā. tas ir, ja mēs vienmēr sākas. Jūs varat domāt par to kā galvas arī. Bet kokiem, mums ir tendence atsaukties uz to kā saknes. 

Jebkas apakšā here-- pie ļoti, ļoti bottom-- tiek uzskatīti lapas. Tā tas iet kopā ar viss koks lieta, vai ne? Lapas ir malās savu koku. 

Un tad mums ir arī pāris termini runāt par punktiem attiecībā viens ar otru. Tātad mums ir vecāks, bērni, un brāļi un māsas. Tātad, šajā gadījumā, 3 ir vecāks par 5, 6, un 7. Tāpēc vecākiem ir kāds ir viens solis augstāk kāds tu esi atsaucoties uz, tik vienkārši kā ģimenes koku. Cerams, tas viss nedaudz nedaudz vairāk intuitīvi nekā valstīs. 

Brāļi un māsas ir kāds, kas ir un tas pats mātesuzņēmums, vai ne? Viņi šeit pašā līmenī. Un tad, kā es biju sakot, bērni ir tikai viss, kas ir viens solis tālāk mezgls jautājumu, OK? Atdzist. Tātad bināro koku. Var kāds briesmas minējums par vienu no raksturlielumi bināro koku? 

Mērķauditorija: Max divas lapas. 

SPEAKER 1: Labais. Tātad max divām lapām. Tātad pirms šo vienu, mums bija šo vienu ka bija trīs, bet bināro koku, Jums ir max divu bērni uz vienu no vecākiem, vai ne? Tur ir cita interesanta īpašība. Vai kāds zina, ka? Bināro koku. 

Tātad bināro koku būs viss par the-- šis nav sorted-- bet gan sakārtoti bināro koku, viss pa labi ir lielāks nekā vecākiem, un viss pa kreisi ir mazāks nekā vecākiem. Un tas ir viktorīna Jautājums agrāk, tāpēc labi zināt. Tātad kā mēs definējam to, atkal, mums ir vēl viens mezglā. Tas izskatās ļoti līdzīgs tam, ko? Divkārt 

Mērķauditorija: Saistīts saraksti 

SPEAKER 1: dubultā saistīts saraksts, labi? Tātad, ja mēs aizstāt šo ar iepriekšējo un nākamo, tas būtu divkārt saistīts saraksts. Taču šajā gadījumā, mēs faktiski ir pa kreisi un pa labi, un tas arī viss. Pretējā gadījumā, tas ir tieši tas pats. Mums joprojām ir elements jūs meklējat, un jūs vienkārši ir divas norādes gatavojas kāds ir nākamais. Jā, tāpēc bināro meklēšanas koku. Ja mēs pamanām, visu uz tieši šeit ir lielāks than-- vai viss uzreiz lai tieši šeit ir lielāks nekā, viss šeit ir mazāks nekā. 

Tātad, ja mēs būtu jāmeklē, to vajadzētu izskatīties ļoti tuvu bināro meklēšanu šeit, vai ne? Izņemot, nevis meklē pusi masīva, mēs esam tikai apskatot vai nu pa kreisi sānu vai labajā pusē no koka. Tātad, tas kļūst mazliet vienkāršāku, es domāju. 

Tātad, ja jūsu sakne ir NULL, protams, tas ir tikai viltus. Un, ja tas ir tur, protams, tā ir taisnība. Ja tas ir mazāk, nekā, mēs meklējam pa kreisi. Ja tas ir lielāks nekā, mēs meklētu tiesības. Tas ir tieši tāpat kā bināro meklēšanu, tikai atšķirīgs datu struktūra ka mēs izmantojam. Tā vietā, lai masīva, tas ir tikai bināro koku. 

Labi, skursteņi. Un arī, izskatās, ka mēs varētu būt mazliet laika. Ja mēs to darām, es esmu laimīgs, lai dotos uz kādu no to vēlreiz. Labi, tāpēc skursteņi. Vai kāds atceras, ko stacks-- jebkuri kaudze īpašības? 

Labi, tāpēc lielākā daļa no mums, es domāju, ēst pusdienas halls-- tik daudz, cik mēs negribētu. Bet, protams, jūs varat iedomāties kaudze burtiski tāpat kā kaudze paplātes vai kaudze lietas. Un, kas ir svarīgi apzināties, ka tā ir something-- īpašība ka mēs to saucam pēc-- ir LIFO. Vai kāds zina, ko tas nozīmē? Mmhmm? 

Mērķauditorija: pēdējais iekšā, pirmais ārā. 

SPEAKER 1: Tiesības, pēdējais iekšā, pirmais ārā. Tātad, ja mēs zinām, ja mēs esam kraušanas lietas augšu, vieglākais lieta paķert off-- un varbūt vienīgais, ko mēs varam paķert off ja mūsu steks ir liels enough-- ir tas, ka top elements. Tātad, kāds tika likts uz last-- kā mēs redzam šeit, kāds bija uzstājām par lielāko recently-- ir būs pirmais lieta, ka mēs pop off, OK? 

Tātad, kas mums šeit ir cits typedef struktūrai. Tas ir patiešām vienkārši patīk crash kurss datu struktūra, tāpēc tur ir daudz izmet pie jums puiši. Es zinu. Tātad vēl viens struktūrai. Yay struktūrām. 

Un šajā gadījumā, tas ir sava rādītājs masīvs, kas ir dažas iespējas. Tātad šis ir mūsu kaudze Šeit, tāpat kā mūsu faktisko masīvs kas ir saimniecības mūsu elementus. Un tad šeit mums ir dažas izmēru. 

Un parasti, jūs vēlaties, lai saglabātu izsekot, cik liels jūsu kaudze ir jo tas, ko tā gatavojas atļaut Jums jādara, ir, ja jūs zināt izmēru, tas ļauj teikt, Labi, es esmu ar jaudu? Vai es varu pievienot kaut ko vairāk? Un tas arī stāsta jums kur top jūsu kaudze ir, lai jūs zināt, ko jūs faktiski var pacelties. Un tas ir patiešām gatavojas būt nedaudz vairāk skaidrs šeit. 

Tātad push, viena lieta, ja jums kādreiz īstenot push, kā man bija tikai saku, Jūsu kaudze ir ierobežots izmērs, vai ne? Mūsu masīvs bija dažas spējas. Tas ir masīvs. Tas ir fiksēts lielums, tāpēc mums ir nepieciešams, lai pārliecināties, ka mēs esam ne liekot vairāk mūsu masīvs, nekā mēs faktiski ir vietas. 

Tātad, ja jūs veidojat push funkcija, pirmā lieta, jums jādara, ir teikt, OK, man ir vieta manā kaudze? Jo, ja man nav, piedodiet, Es nevaru saglabāt savu elementu. Ja es daru, tad jūs vēlaties, lai saglabātu tā augšpusē skursteņa, vai ne? 

Un tas ir iemesls, kāpēc mēs esam sekot mūsu izmēra. Ja mums nav sekot līdzi mūsu lieluma, mēs nezinām, kur likt to. Mēs nezinām, cik daudzas lietas ir mūsu masīvā jau. Tāpat kā acīmredzot ir veidi ka varbūt jūs varētu darīt to. Jūs varētu sāktu visu null un pēc tam pārbaudīt jaunāko NULL, bet daudz vieglāk lieta ir tikai teikt, OK, sekot izmēra. Tāpat kā es zinu, man ir četri elementi manā masīvs, tāpēc nākamā lieta ka mēs likts uz, mēs esam gatavojas glabāt pie indeksu 4. Un tad, protams, tas nozīmē, ka Jūs esat veiksmīgi uzstāja kaut ko uz jūsu kaudze, jūs vēlas, lai palielinātu izmēru tā, ka jūs zināt, kur jūs esat tik ka jūs varat push vairāk lietas, par. 

Tātad, ja mēs cenšamies, lai pop kaut off kaudze, kādi varētu būt pirmā lieta ka mēs vēlamies, lai pārbaudītu? Jūs mēģināt veikt kaut pie jūsu kaudze. Vai esat pārliecināts, ka tur ir kaut kas jūsu kaudze? Nē. Tātad, ko, iespējams, mēs vēlamies, lai pārbaudītu? 

Mērķauditorija: [dzirdams]. SPEAKER 1: Pārbaudiet izmēru? Izmērs. Tāpēc mēs vēlamies, lai pārbaudītu, lai redzētu, vai Mūsu izmērs ir lielāks par 0, OK? Un, ja tā ir, tad mēs vēlamies, lai samazinātu Mūsu izmērs pa 0 un tad atpakaļ to. Kāpēc? 

Pirmajā one mēs stumšanu, mēs uzstāja, ka uz izmēru un atjaunināti izmēru. Šajā gadījumā, mēs decrementing izmēru un tad ņemot to nost, noplūkšanas to no mūsu masīva. Kāpēc mēs varētu darīt? Tātad, ja man ir viena lieta, par manu steku, kāds būtu mans izmērs šajā brīdī? 1. 

Un kur ir elements 1 uzglabāti? Kādā indekss? AUDITORIJA: 0. SPEAKER 1: 0. Tātad, šajā gadījumā, mēs vienmēr vajag veikt sure-- nevis atpakaļ lielums mīnus 1, jo mēs zinu, ka mūsu elements būs jāuzglabā 1 mazāk neatkarīgi no mūsu izmērs ir, šis tikai rūpējas par to. Tas ir nedaudz vairāk elegants veids. Un mēs vienkārši Samazināt OUR lielumu un pēc tam atgriezties izmēru. Mmhmm? 

Mērķauditorija: Es domāju, tikai kopumā, kāpēc varētu šo datu struktūra būt izdevīga? 

SPEAKER 1: Tas ir atkarīgs no jūsu konteksta. Tātad daži no teorijas, ja jūs strādājat with-- Labi, ļaujiet man redzēt, ja ir izdevīga viena kas ir izdevīgi vairāk nekā ārpus PV. Ar skursteņi, jebkurā laikā jums ir nepieciešams sekot kaut kas ir pavisam nesen pievienotā ir tad, kad jūs gatavojas vēlaties izmantot kaudze. 

Un es nevaru iedomāties preces piemērs, ka tieši tagad. Bet kad jaunākais lieta ir ļoti svarīgi, lai jūs, tas ir tad, kad kaudze būs noderīga. Es cenšos domāt, ja tur ir labs par to. Ja es domāju par labu piemēru nākamo 20 minūtes, es noteikti pateikt. 

Bet kopumā, ja tur ir kaut kas, kā jau teicu visvairāk, kur lielākā daļa nesen ir vissvarīgākais, kas ir kur kaudze sāk spēlēt. Bet rindas ir sava veida pretējo. Un visi mazie suņi. Vai tas nav liels, labi? Es jūtu, ka vajadzētu vienkārši ir zaķa video tiesības vidū sadaļa jums puiši jo tas ir intensīva sadaļa. 

Tā rinda. Būtībā rinda ir kā līniju. Jūs guys Es esmu pārliecināts, ka šī izmantošana ikdienā, tāpat kā mūsu ēdamzāles. Tāpēc mums ir jāiet un saņemt mūsu paplātes, es esmu pārliecināts, ka jums ir jāgaida rindā zvēliens vai saņemtu savu pārtiku. 

Tātad atšķirība šeit ir tas, ka tas ir FIFO. Tātad, ja LIFO pēdējais bija pirmais out, FIFO ir pirmais iekšā, pirmais ārā. Tātad, tas ir, ja kāds jūs nodot gada pirmais ir jūsu svarīgākais. Tātad, ja jūs gaidīja tādā line-- var tevi iedomājieties, ja jūs devās uz iet saņemt jaunu iPhone un tas bija kaudze, kurā pēdējais cilvēks rindā dabūja to, pirmkārt, cilvēki nogalināt viens otru. 

Tātad FIFO, mēs visi ļoti labi pārzina ar reālajā pasaulē šeit un tas viss ir saistīts ar faktiski veida atjaunošanās visu šo līniju un rindu struktūru. Tādējādi, kaut arī ar steku, mums ir push un pop. Ar rindā, mēs esam Enqueue un dequeue. Tātad Enqueue būtībā nozīmē ielieciet to uz muguras, un dequeue līdzekļiem veikt off no priekšpuses. Tātad mūsu datu struktūra ir mazliet vairāk sarežģī. Mums ir arī otra lieta, lai sekotu. 

Tātad bez galvas, tas Tieši kaudze, vai ne? Tas ir struktūra ir tāda pati kā skursteni. Vienīgais, kas atšķiras tagad mēs ir šī galva, kas tas, ko jūs domājat gatavojas sekot? 

Mērķauditorija: Pirmais. 

SPEAKER 1: labi, Pirmā lieta, ko mēs ieliekam. Mūsu rindā vadītājs. Kurš ir pirmais pēc kārtas. Viss ir labi, tāpēc, ja mēs Enqueue. Atkal, ar jebkuru no šīs datu struktūras, jo mums ir darīšana ar masīvu, mums ir nepieciešams, lai pārbaudītu, ja mums ir telpa. 

Tas ir veids kā mani stāsta jūs guys, ja atverat failu, jums ir nepieciešams, lai pārbaudītu null. Ar kādu no šiem skursteņi un rindas, jums ir nepieciešams lai redzētu, vai tur ir vietas, jo mēs esam nodarbojas ar fiksētu izmēru masīvs, kā mēs redzam here-- 0, 1 visi līdz 5. Tātad, ko mēs darām šajā gadījumā ir pārbaude lai redzētu, vai mums vēl ir vietas. Vai mūsu lielums ir mazāks par jaudu? 

Ja tā, tad mums ir nepieciešams, lai saglabātu to astes un mēs atjaunināt savu izmēru. Tātad, ko varētu aste būt šajā gadījumā? Tas nav skaidri uzrakstīts. Kā mēs uzglabāt to? Ko būtu aste būt? 

Tāpēc pieņemsim iet cauri šim piemēram. Tātad šī ir masīvs izmēru 6, vai ne? Un mums ir tiesības tagad, mūsu izmērs ir 5. Un, kad mēs ieliekam to, tas notiek iedziļināties piektajā indeksā, vai ne? Tātad uzglabāt pie astes. 

Vēl viens veids, kā rakstīt asti būtu vienkārši mūsu masīvs pie indeksa lielumu, vai ne? Tas ir lielums 5. Nākamā lieta, gatavojas doties uz 5. Forši? OK. Tas izpaužas nedaudz sarežģītāka kad mēs sākam messing ar galvu. Jā? 

Mērķauditorija: Vai tas nozīmē, ka mēs būtu paziņoja, masīvu, kas bija pieci elementi garš un Tad mēs pievienojam uz to? 

SPEAKER 1: Nē. Tātad šajā gadījumā, tas ir kaudze. Tas būtu jādeklarē kā masīva izmēru 6. Un, šajā gadījumā, mēs vienkārši ir viena telpa pa kreisi. 

Labi, tā viena lieta ir šajā gadījumā, ja mūsu galva ir 0, tad mēs vienkārši var pievienot to izmēru. Bet tā kļūst nedaudz sarežģītāks jo patiesībā, tie nav slide par to, tāpēc es esmu gatavojas izdarīt vienu, jo tas nav gluži tik vienkārši, kad jums sāk atbrīvoties no lietām. Tādējādi, kaut arī ar steku Jums tikai kādreiz ir jāuztraucas par to izmērs ir ja jūs pievienojat kaut ko, ar rindā jums arī nepieciešams, lai Pārliecinieties, ka jūsu galva ir jāatskaitās, jo cool lieta par rindām ir tas, ka, ja jūs neesat pie jaudu, Jūs faktiski var padarīt to wrap apkārt. 

Labi, tāpēc viens thing-- oh, tas ir briesmīgi krīts. Viena lieta, kas jāapsver, ir tas gadījums. Mēs vienkārši darīt pieci. Labi, tāpēc mēs ejam saka galva ir šeit. Tas ir 0, 1, 2, 3, 4. 

Galva ir tur, un lūdzu, ir lietas, kas viņiem. Un mēs vēlamies, lai pievienotu kaut ko, vai ne? Tātad lieta, ka mums ir zina, ir tas, ka galva ir vienmēr gatavojas pārvietot šo ceļu, un tad cilpa atpakaļ ap, OK? 

Tāpēc šī rinda ir vieta, vai ne? Tā ir vieta, kas jau pašā sākumā, sava veida pretstatu to. Tātad, kas mums jādara, ir mums nepieciešams, lai aprēķinātu asti. Ja jūs zināt, ka jūsu galva nav pārvietots, asti ir tikai jūsu masīvs at indekss izmēru. 

Bet patiesībā, ja jūs izmantojat rindā, tava galva, iespējams, tiek atjaunināts. Tātad, kas jums jādara, ir faktiski aprēķināt asti. Tātad, ko mēs darām, ir šī formula šeit, ko es esmu gatavojas let jums puiši padomāt, un Tad mēs runājam par to. Tātad, tas ir spēja. 

Tātad šis būs patiešām dot jums veids, kā to izdarīt. Jo šajā gadījumā, ko? Mūsu galvenais ir 1, mūsu izmērs ir 4. Ja mēs mod, ka līdz 5, mēs 0, kas ir, ja mums vajadzētu ievadi. 

Tātad, tad nākamajā gadījumā, ja mēs to izdarītu, mēs sakām, OK, pieņemsim dequeue kaut ko. Mēs dequeue šo. Ņemam šo elementu, vai ne? 

Un tagad mūsu galvenais ir vērsta šeit un mēs vēlamies pievienot cita lieta. Šis ir būtībā atpakaļ mūsu līnijas, vai ne? Rindas var wrap ap masīvs. Tas ir viens no galvenajām atšķirībām. Skursteņi, jūs nevarat izdarīt. 

Ar rindām, varat jo viss, ka jautājumus ir tas, ka jūs zināt, ko nesen tika pievienots. Jo viss tiks pievienots šis pa kreisi virzienā, šajā gadījumā, un tad wrap apkārt, jūs varat turpināt liekot jaunus elementus priekšā masīva tāpēc, ka tas nav īsti priekšpuse masīva vairs. Jūs varat domāt par sākuma masīvs, kā, kur jūsu galva patiesībā ir. 

Tātad šī formula ir, kā jūs varat aprēķināt savu asti. Vai tas ir jēga? OK. Labi, dequeue, un pēc tam jums puiši ir 10 minūtes uzdot man jebkurus precizēt jautājumus Jūs vēlaties, jo es zinu, tas ir traki. 

Visi pa labi, lai tajā pašā way-- Es nezinu, ja jūs guys pamanījuši, bet CS ir par modeļiem. Lietas ir diezgan daudz Tas pats, tikai ar sīkiem tweaks. Tātad pats šeit. Mums ir nepieciešams, lai pārbaudītu, lai redzētu, vai mēs patiešām ir kaut kas mūsu rindā, vai ne? Saka, OK, ir mūsu izmērs ir lielāks par 0? Atdzist. 

Ja mēs to darām, tad mēs virzāmies savu galvu, kas ir tas, ko es tikko demonstrēja šeit. Mēs atjaunināt mūsu galvu par vienu vairāk. Un tad mēs Samazināt mūsu izmērs un atgriezties elementu. 

Tur ir daudz konkrētāks kodu study.cs50.net, un es ļoti ieteiktu iet caur to, ja jums ir laiks, pat ja tas ir tikai pseido-kodu. Un, ja jūs puiši vēlas runāt caur kas ar mani viens pret vienu, lūdzu, ļaujiet man zināt. Es gribētu būt laimīgs. Datu struktūras, ja Jūs lietojat CS 124, jūs zinu, ka datu struktūras iegūt ļoti jautri, un tas ir tikai sākums. 

Tāpēc es zinu, tas ir grūti. Tas ir OK. Mēs cīnāmies. Es joprojām darīt. Tāpēc nav jāuztraucas pārāk daudz par to. 

Bet tas ir būtībā jūsu crash kursu datu struktūras. Es zinu, tas ir daudz. Vai ir kaut kas, ko mēs gribētu iet atkal? Jebkas, mēs vēlamies runāt cauri? Jā? 

Mērķauditorija: Šajā Piemēram, tāpēc jaunais astes ir 0 pār to? SPEAKER 1: Jā. AUDITORIJA: OK. Tātad iet cauri, jūs ir 1 plus 4 or-- 

SPEAKER 1: Tātad jūs sakot, ja mēs gribam iet darīt atkal? AUDITORIJA: Jā. Tātad, ja jums ir norādītas out-- kur ir Jūs aprēķinot asti no in that? 

SPEAKER 1: Tātad asti bija in-- es mainīja šo. Tātad šajā piemērā šeit, tas bija masīvs mēs meklējam, OK? Tāpēc mums ir lietas 1, 2, 3 un 4. Tātad, mēs ir mūsu galva ir vienāds ar 1, pie šis punkts, un mūsu lielums ir vienāds ar 4 šajā brīdī, vai ne? 

Jūs visi piekrīt, ka tas ir? Tātad mēs galvu plus izmēru, kas dod mums 5, un tad mēs mod ar 5. Mēs saņemam 0, kas stāsta mums, ka 0 ir kur ir mūsu astes, kur mums ir vieta. 

Mērķauditorija: Kas ir vāciņš? 

SPEAKER 1: jauda. Piedodiet. Tāpēc, ka ir izmēru jūsu masīvs. Jā? 

Mērķauditorija: [dzirdams] pirms mēs atgriežamies elementu? 

SPEAKER 1: Tātad mēs virzāmies galvu vai atgriešanās brīdi? Tātad, ja mēs virzāmies uz vienu, Samazināt izmēru? Turēt uz. Es noteikti aizmirsu citu. Nekad prātā. Nav vēl formula. Jā, jūs vēlaties, lai atgrieztos galvu un tad pārvietot to atpakaļ. 

Mērķauditorija: OK, jo šajā punkts, galva bija 0, un tad jūs vēlaties, lai atgrieztos indekss 0 un pēc tam veikt galvas 1? 

SPEAKER 1: Labais. Es domāju, ka tur ir cita formula veida, kā šis. Man nav to uz augšu manu galvu kā Es nevēlos, lai dotu jums nepareizu vienu. Bet es domāju, ka tas ir pilnīgi pamatota, teiksim, OK, uzglabāt šo element-- neatkarīgi galva elements is-- Samazināt savu lielums, pārvietot savu galvu vairāk, un atgriešanās kāds šis elements. Tas ir ļoti lietderīga. OK. Man šķiet, ka tas nav tāpat most-- jūs neesat gatavojas staigāt ārā no šejienes piemēram, jā, es zinu, mēģina. Man to visu. Tas ir OK. Es apsolu. Bet datu struktūras ir kaut kas tas aizņem daudz laika, lai pierastu pie. Iespējams, viens no vissmagāk lietas, es domāju, ka, veicot. 

Tātad, tas noteikti notiek atkārtošanās un meklē at-- I nav īsti zināt, kas saistītas sarakstus līdz brīdim, kad man bija pārāk daudz ar tiem, tādā pašā veidā, ka es nesapratu tiešām saprastu norādes līdz brīdim, kad man bija mācīt diviem gadi un darīt savu psets ar to. Tas aizņem daudz atkārtošanu un laiku. Un galu galā, tas būs sava veida klikšķi. 

Bet pa to laiku, ja jums ir sava veida par augsta līmeņa izpratni par to, tie dara, to plusi un cons-- kas ir tas, ko mēs patiešām mēdz uzsvērt, īpaši intro kursā. Tāpat kā, kāpēc mēs izmantojam izmēģināt vairāk masīva? Tāpat kā, kādi ir pozitīvi un negatīvi katras no tiem? 

Un izpratne kompromisus starp katru no šīm konstrukcijām ir tas, kas ir daudz vairāk svarīgi, tieši tagad. Tur var būt viens traks jautājums vai divi, kas ir gatavojas lūgt jums, lai īstenotu push vai īstenot pop vai Enqueue un dequeue. Bet lielākā daļa, kam, ka augstākā līmeņa izpratne un vairāk ar intuitīvu izpratni ir svarīgāka nekā patiesībā to var īstenot. 

Tas lūdzu būt ļoti laba, ja jums visiem varētu iet ārā un iet īstenot izmēģināt, bet mēs saprotam, ka tas nav obligāti visvairāk saprātīgu lieta tieši tagad. Bet jūs varat jūsu PSET, ja vēlaties lai, un tad jūs saņemsiet praksi, un tad varbūt jūs īsti saprast. Jā? 

Mērķauditorija: Labi, tā, kādi ir mēs domājām, lai izmantotu šajā PSET? Vai man ir nepieciešams, lai izmantotu kādu no viņiem? SPEAKER 1: Jā. Tātad jums ir jūsu izvēle. Es domāju, šajā gadījumā, mēs varam runāt par PSET mazliet jo es skrēja caur tiem. Tātad jūsu PSET, jums ir jūsu izvēle mēģinājumiem vai hash tabulu. Daži cilvēki mēģinās un izmantot BLOOM filtrus, bet tie tehniski nav pareizi. Sakarā ar to varbūtības raksturs, tie dod viltus reizēm. Viņi forši ieskatīties, though. Ļoti ieteiktu meklē pie viņiem vismaz. Bet jums ir jūsu izvēle starp hash tabulu un izmēģināt. Un kas notiek, lai būtu kur jūs ielādēt savā vārdnīcā. 

Un jums būs jāizvēlas Jūsu hash funkciju, jums vajadzēs izvēlēties, cik daudz kausi jums ir, un tas būs atšķirīgs. Piemēram, ja jums ir vairāk kausi, varbūt tas būs darboties ātrāk. Bet varbūt jūs izšķērdēt vietas, ka veids, lai gan daudz. Jums ir skaitlis tas. Mmhmm? 

Mērķauditorija: Jūs teicāt, pirms tam mēs varam izmantot citas hash funkcijas, ka mums nav izveidot jaucējfunkciju? 

SPEAKER 1: Jā, labi. Tik burtiski jūsu hash funkciju, piemēram, google "jaukšanas funkcija" un meklēt dažas atdzist tiem. Jums nav gaidāma būvēt Jūsu pašu hash funkcijas. Cilvēki pavada tēzes par šīm lietām. 

Tāpēc nav jāuztraucas par ēkas savu. Atrast vienu tiešsaistē, lai sāktu ar. Dažas no tām jums ir manipulēt mazliet lai pārliecinātos, ka atgriešanās veidi sakrīt un plauktiņš, tāpēc sākumā, Es ieteiktu izmantot kaut ko ļoti viegli, ka varbūt tikai hashes uz pirmo burtu. Un tad, kad jums ir šī darba, iekļaujot vēsākas jaucējfunkciju. Mmhmm? 

Mērķauditorija: Vai mēģināt būt vai efektīvi, bet tikai grūtāk, like-- 

SPEAKER 1: Tātad izmēģināt, es domāju, ir intuitīvi grūti īstenot bet ir ļoti ātri. Tomēr, aizņem vairāk vietas. Atkal, jūs varat optimizēt gan no tiem, kas dažādi veidi un ir veidi, kuri paredzēti, lai Mērķauditorija: Kā mēs šķiro par šo? Vai tas matter-- 

SPEAKER 1: Tātad jūs šķiro normālu ceļu. Jūs esat būs jāšķiro uz dizainu. Neatkarīgi no tā, kā jūs darāt, jūs vēlaties pārliecinieties, ka tas ir tik elegants, kā tas var būt un tik efektīva, kā tas var būt. Bet, ja jūs izvēlaties izmēģināt vai hašišu galds, kamēr tas darbojas, mēs esam apmierināti ar to. Un, ja jūs izmantojat kaut kas hashes uz pirmo burtu, tas ir jauki, piemēram, varbūt, piemēram, dizaina ziņā. Mēs arī sasniedzot punkts šajā semester-- Es nezinu, ja jums puiši noticed-- ja jūs esat PSET pakāpes samazināsies mazliet jo dizaina un plauktiņš, tas ir perfekti labi. Tas kļūst līdz vietai, kur jūsu programmas kļūst sarežģītāka. Ir vairāk vietas Jūs varat uzlabot. 

Tātad, tas ir pilnīgi normāli. Tas nav, ka tu esi dara sliktāk par savu PSET. Tas ir tikai mēs to grūtāk par jums tagad. Tātad ikvienam ir sajūta to. Es tikai šķiro visus savus psets. Es zinu, visi ir sajūta to. 

Tāpēc nav jābūt noraizējies par to. Un, ja jums ir kādi jautājumi par iepriekšējas psets vai veidi, kā jūs varat uzlabot, Mēģinu un komentēt īpašais vietām, bet dažreiz tas ir par vēlu un man nogurst. Vai ir kādas citas lietas par datu struktūras? Es esmu pārliecināts, ka jūs puiši nav īsti gribam runāt par tām vairs, bet, ja ir, es esmu laimīgs, lai iet pār tām, kā arī kaut ko No lekciju šis pagātnes nedēļā vai pagājušajā nedēļā. 

Es zinu, pagājušajā nedēļā bija viss pārskatīšana, tāpēc mums var būt izlaidis pār kādu pārskatīšanu no lekciju. Jebkādi citi jautājumi, es varu atbildēt? Labi, labi. Nu, jūs puiši izkļūt 15 minūtes agrāk. 

Es ceru, ka tas bija daļēji lietderīgi vismaz un es redzēt jūs puiši nākamnedēļ, vai ceturtdiena darba laiks. Vai ir pieprasījumi uzkodas nākamajā nedēļā, tā ir lieta? Tāpēc, ka es aizmirsu konfektes šodien. Un es atvedu konfektes pēdējā nedēļa, bet tas bija Columbus diena, tāpēc tur bija kā seši cilvēki, kuri bija četri maisus konfektes sev. Es varu dot starbursts atkal, ja jums patīk. Starbursts? Labi, izklausās labi. Ir lieliska diena, puiši.