SPEAKER 1: Në rregull, kështu që kjo është CS50 Ky është fundi i javës pesë. Dhe kujtojnë se herën e fundit ne filluar duke kërkuar në të dhënat njohës Strukturat që filluan për të zgjidhur Problemet, që filluan për të futur probleme të reja, por çelësi për këtë ishte lloj i filetim që ne filloi të bëjë nga nyje në nyje. Pra, kjo sigurisht është një listë e lidhur në formë individuale. Dhe duke e lidhur në formë individuale, Unë do të thotë se ka vetëm një thread mes të secilit prej këtyre nyjeve. Rezulton se ju mund të bëni njohës gjëra të tilla si listat e lidhura dyfish ku ju keni një shigjetë duke shkuar në të dy drejtimet, e cila mund të ndihmojë me efikasitet të caktuara. Por kjo zgjidhur problemin? Çfarë problemi ka kjo zgjidh? Pse kemi kujdes të hënën? Pse, në teori, nuk kemi kujdes të hënën? Çfarë do të bëni? 

Audienca: Ne dinamike mund të resize atë. 

SPEAKER 1: OK, kështu që ne mund të dinamike resize atë. Të lumtë të dy prej jush. Kështu që ju mund dinamike resize këtë Struktura e të dhënave, ndërsa një grup, Recall, ju duhet të dini priori si hapësirë ​​sa të doni dhe në qoftë se keni nevojë për pak më shumë hapësirë, ju jeni lloj i nga fat. Ju duhet të krijoni një grup të tërë të re. Ju duhet të lëvizin të gjitha tuaj të dhënat nga njëri në tjetrin, përfundimisht të lirë array vjetër në qoftë se ju mund të, dhe pastaj do të vazhdojë. Të cilat vetëm ndjehet shumë i kushtueshëm dhe shumë joefikase, dhe në të vërtetë ajo mund të jetë. Por kjo nuk është e gjitha e mirë. Ne të paguajë një çmim, atë që ishte një nga çmimet më të dukshme ne paguajnë duke përdorur një listë e lidhur? 

Audienca: Ne duhet të përdorim hapësirë ​​të dyfishtë për secilën prej tyre. SPEAKER 1: Yeah, kështu që ne kemi nevojë të paktën dy herë më shumë hapësirë. Në fakt, kam kuptuar kjo foto e edhe pak mashtruese, sepse në IDE CS50, në një shumë të moderne kompjutera, një tregues apo një adresë Nuk është në fakt katër bytes. Është shumë shpesh këto ditë tetë bytes, të cilat nënkupton pjesën e poshtme më rectangles atje në realitet janë lloj i dy herë më i madh si ajo që unë kam vizatuar, që do të thotë se ju jeni duke përdorur tri herë si hapësirë ​​më shumë që ne mund të kemi ndryshe. Tani në të njëjtën kohë, ne jemi ende duke folur bytes, e drejtë? Ne nuk jemi domosdoshmërisht duke folur megabajt apo gigabajt, përveç rasteve kur këto të dhëna struktura të mëdha. 

Dhe kështu që sot ne të fillojnë të marrin në konsideratë se si ne mund të shqyrtojë të dhënat e më efikase nëse në fakt të dhënat merr të mëdha. Por le të përpiqemi të canonicalize operacionet e para që ju mund të bëni në këto llojet e strukturave të të dhënave. Pra, diçka si një i lidhur Lista përgjithësisht mbështet Operacionet pëlqen fshini, futur, dhe kërko. Dhe çfarë dua të them me këtë? Kjo thjesht do të thotë se zakonisht, në qoftë se njerëzit janë duke përdorur listën e të lidhura, ata ose dikush tjetër i ka zbatuar funksionon si fshini, insert, dhe kërkimit, kështu që ju mund të vërtetë të bëjë diçka dobishëm me strukturën dhënave. Pra, le të marrin një vështrim të shpejtë se si ne mund të zbatojë kod për një listë të lidhura si më poshtë. 

Pra, kjo është vetëm një kod C, as edhe një program i plotë se unë me të vërtetë rrahur shpejt lart. Kjo nuk është në internet në shpërndarjen Kodi, sepse ajo nuk do të të vërtetë të drejtuar. Por vini re unë kam vetëm me një koment tha: dot dot dot, ka diçka atje, dot Dot Dot, diçka atje. Dhe le të vetëm shikoni në çfarë pjesë lëng janë. Pra, në përputhje tre, kujtojnë se kjo është tani kemi propozuar deklaruar një nyje të fundit kohë, një nga ato objekte drejtkëndëshe. Ajo ka një int që ne do të thërrasë N, por ne mund ta quajmë atë gjë, dhe pastaj një yll nyje struct quajtur ardhshëm. Dhe vetëm të jetë i qartë, se dyti line, në përputhje gjashtë, çfarë është kjo? Çfarë është ajo bën për ne? Për shkak se ajo sigurisht duket më i fshehtë se variablave tonë të zakonshme. 

Audienca: Kjo e bën atë të lëvizë mbi një. 

SPEAKER 1: Kjo e bën atë të lëvizë mbi një. Dhe për të qenë më të saktë, ai do të ruajë adresën i nyjës që është menduar të jetë semantikisht tjetër për të, apo jo? Pra, kjo nuk do të domosdoshmërisht të lëvizur asgjë. Është vetëm do të ruajtur nje vlere, i cili është do të jetë adresa e disa nyjeve të tjera, dhe kjo është arsyeja pse ne kemi thënë struct yll nyje, ylli denoting një tregues apo një adresë. OK, kështu që tani, nëse ju supozojmë se ne kemi kjo N dispozicion për ne, dhe le të supozojmë se dikush tjetër e ka futur një bandë e tërë e numrave të plotë në një listë të lidhura. Dhe kjo listë e lidhur është vuri në dukje nga disa pika një listë të quajtur variabël që është kaluar në këtu si një parametër, Si mund të shkoj në lidhje me vijën 14 implementimin kërkim? Me fjalë të tjera, në qoftë se unë jam i zbatimit funksioni qëllimi i të cilit në jetë është që të marrë një int dhe pastaj fillimi i një liste të lidhura, që është një tregues në listën e lidhur. Ashtu si i pari, i cili unë mendoj Davidin ishte vullnetar jonë të hënën, ai ishte treguar në tërë i lidhur Lista aktuale e, kjo është sikur ne jemi duke kaluar Davidi në si argument tonë këtu. Si mund të shkoj për traversing këtë listë? E pra, ajo rezulton se edhe pse pointers janë relativisht të reja tani për ne, ne mund të bëjmë këtë relativisht drejpërdrejtë. 

Unë jam duke shkuar për të shkuar përpara dhe deklarojë një ndryshore të përkohshme që nga konventa është vetëm do të quhet tregues, ose PTR, por ju mund të telefononi atë çdo gjë që ju dëshironi. Dhe unë jam duke shkuar për të nisja ajo fillimit të lista. Kështu që ju mund të lloj të mendojnë për këtë si mua mësuesi ditë të tjera, lloj i vënë në dikë në mesin e njerëzve tanë si vullnetarë. Kështu që unë jam një ndryshore të përkohshme që është vetëm duke vënë në të njëjtën gjë se jonë me emrin rastësisht vullnetar Davidi u gjithashtu vënë në dukje. Tani ndërsa tregues është jo null, sepse risjell që null disa vlera të veçanta rojtar Në kufirin fundin e listës, kështu, ndërsa unë nuk jam duke treguar në terren si vullnetar tonë të fundit ishte, le të shkojë përpara dhe të bëjë të mëposhtme. Nëse pointer-- dhe tani unë lloj i dua të bëni atë që ne e bëmë me nxënësin structure-- nëse akrep dot ardhshëm equals-- më tepër, në qoftë se akrep dot N barabartë barabartë variabli N, The Argumenti që është miratuar në, atëherë unë dua të shkoj përpara dhe thonë kthim i vërtetë. Unë kam gjetur numrin N brenda të një nga nyjet e listën time të lidhur. Por dot nuk punon në këtë kontekst, sepse akrep, PTR, është me të vërtetë një tregues, një adresë, ne fakt mund mrekullisht përdorni në fund një pjesë të sintaksës se lloj i bën kuptim intuitiv dhe në fakt përdorni një shigjetë këtu, që do të thotë të shkojnë nga që adresa në numrin e plotë atje në. Pra, kjo është shumë e ngjashme në Fryma e dot operatori, por për shkak se nuk është një akrep akrep dhe jo një vetë struct aktuale, ne vetëm përdorni arrow. 

Pra, nëse nyja aktuale që unë, variabël i përkohshëm, jam duke treguar në nuk është N, çfarë unë dua të bëj? E pra, me vullnetarët e mia njeriut që kemi pasur këtu ditë të tjera, në qoftë se njeriu i parë ime nuk është një unë duan, dhe ndoshta e dyta njeriut nuk është ajo që unë dua, dhe i treti, unë nevojë për të mbajtur fizikisht në lëvizje. Ashtu si mund ta hap përmes një listë? Kur ne kishim një rrjet, ju vetëm e bëri si unë plus plus. Por në këtë rast, mjafton të bëjnë treguesin, merr, tregues, tjetër. Me fjalë të tjera, fusha e ardhshme është si të gjithë e duarve lënë që vullnetarët tona njerëzore të hënën ishin përdorur për pikë në një nyje të tjera. Ata ishin fqinj të tyre të ardhshëm. 

Pra, nëse unë dua të hap nëpër këtë listë, Unë nuk mund të bëj unë plus plus më, Unë në vend të kësaj duhet të them Unë, akrep, po shkon të barabartë çfarëdo fushë tjetër është, Fusha tjetër është, fusha tjetër është, pas të gjitha këtyre duarve lënë që kemi pasur në skenë duke treguar të disa vlerave të mëvonshme. Dhe në qoftë se unë të marrë me se e tërë përsëritje, dhe më në fund, unë goditi null mos pasur N gjetur ende, unë vetëm kthimit të rreme. Pra, përsëri, të gjitha që ne jemi duke bërë këtu, si për foto një moment më parë, ka filluar duke vënë në nivel fillimi i listës me sa duket. Dhe atëherë unë kontrolloj, është vlera Unë jam duke kërkuar për barabartë me nëntë? Nëse është kështu, unë kthehet e vërtetë dhe unë jam bërë. Nëse jo, unë rinovuar dorën time, AKA akrep, në pikën në vend të shigjetës së ardhshme, dhe atëherë vendndodhja arrow ardhshëm, dhe të ardhshëm. Unë jam thjesht duke ecur nëpër këtë rrjet. 

Pra, përsëri, i cili kujdeset? Ashtu si ajo që është kjo një përbërës për të? E pra, kujtoj se ne kemi prezantuar nocioni i një pirg, e cila është një e të dhënave abstrakte shkruani për aq sa është e nuk është një gjë C, kjo nuk është një gjë e CS50, kjo është një ide abstrakte, kjo ide e stacking gjëra në krye të njëri-tjetrit që mund të realizohet në bunches e mënyra të ndryshme. Dhe një mënyrë për të propozuar ishte me një grup, apo me një listë të lidhura. Dhe kjo rezulton se canonically, një rafte mbështet të paktën dy operacione. Dhe fjalë të lëvizje janë shtytje për shtytje diçka mbi rafte, si një tabaka të re në sallë ngrënie, ose pop, që do të thotë për të hequr larti tabaka nga rafte në ngrënie sallë, dhe pastaj ndoshta disa operacionet e tjera po ashtu. Pra, si mund të kemi të përcaktuar strukturën se ne jemi tani duke e quajtur një pirg? 

E pra, ne kemi të gjithë të parakusht Sintaksa në dispozicion në C. Unë them, më jepni një lloj përkufizim të një struct brenda një pirg, Unë do të thonë se është një grup, i një tërë bandë e numrave dhe pastaj madhësi. Pra, me fjalë të tjera, në qoftë se unë dua për të zbatuar këtë në kod, më lejoni të shkoj dhe vetëm lloji i të nxjerrë atë që kjo është duke thënë. Pra, kjo është duke thënë, më jepni një strukturë që e mori një grup, dhe unë nuk e di se çfarë kapaciteti është, kjo është me sa duket një konstante që unë kam përcaktuar diku tjetër, dhe kjo është në rregull. Por mendoj se është vetëm një, dy, tre, katër, pesë. Pra Kapaciteti është 5. Ky element brenda mia Struktura do të quhet numra. Dhe pastaj kam nevojë për një të tillë variabël tjetër me sa duket quajtur madhësi që fillimisht unë jam duke shkuar të parashikojë është nisur në zero. Nëse nuk ka asgjë në rafte, madhësia është zero, dhe kjo është vlera të plehrave në numër. Unë nuk kam asnjë ide se çfarë është në atje vetëm ende. 

Pra, nëse unë dua të shtyjë diçka mbi rafte, mendoj unë quaj shtytje funksion, dhe Unë them të shtyjë 50, si numri 50, ku do ju propozojmë I tërheq atë në këtë grup? Ka pesë përgjigje të ndryshme të mundshme. Ku ju doni të shtyjë numrin 50? Nëse qëllimi këtu, përsëri, e quajnë shtytje funksion, të kalojë në një argument e 50, ku mund ta vënë atë? Pesë possible-- shans 20% të guessing në mënyrë korrekte. Po? 

Audienca: Larg drejtë. 

SPEAKER 1: Far drejtë. Nuk është tani një shans 25% të guessing në mënyrë korrekte. Pra, që në fakt do të jetë mirë. Nga konventë, unë do të them me një grup, ne përgjithësi do të fillojë në të majtë, por ne mund sigurisht të fillojë në të djathtë. Pra, spoiler këtu do të jetë unë jam me siguri do të tërheqë atë në të majtë, ashtu si në një grup normale, ku Unë të fillojnë të shkojnë majta në të djathtë. Por në qoftë se ju mund të shfletoj aritmetike, gjobë. Kjo nuk është vetëm konvencionale. OK, unë duhet të bëjë një më shumë ndryshim pse. Tani që unë e kam shtyrë diçka mbi rafte, çfarë e ardhshme? 

Të gjithë të drejtë, unë kam për të ardhura madhësinë. Pra më lejoni të shkoj përpara dhe vetëm Përditëso kjo, e cila ishte zero. Dhe në vend që tani, unë jam duke shkuar për të vënë në vlerën e një. Dhe tani mendoj unë të shtyjë një tjetër Numri i mbi rafte, si 51. E pra, unë kam për të bërë një më shumë ndryshimi, e cila është deri në madhësi dy. Dhe pastaj mendoj unë të shtyjë një më shumë Numri i mbi rafte si 61, tani kam nevojë për të rinovuar madhësinë një më shumë kohë, dhe për të marrë vlerën 3 si madhësia. Dhe tani mendoj unë e quaj pop. Tani pop, nga konventa, nuk ka marrë një argument. Me një pirg, e tërë Pika e metaforës tray është se ju nuk keni liri për të shkuar të marrë atë tabaka, të gjithë ju mund të bëni është pop atë larti nga rafte, vetëm për shkak se. Kjo është ajo që kjo strukturë të dhëna bën. 

Pra, nga kjo logjikë, nëse unë thonë pop, çfarë vjen off? Pra, 61. Pra, çfarë është me të vërtetë kompjuteri do të bëni në kujtesë? Çfarë ka kodi im duhet të bëni? Çfarë do të propozojë ne të ndryshojë në ekran? Çfarë duhet të ndryshojë? Na vjen keq? Pra, ne të shpëtoj nga 61. Kështu që unë mund të patjetër të bëjë atë. Dhe unë mund të shpëtoj prej 61. Dhe pastaj çfarë tjetër ndryshimi duhet të ndodhë? Madhësia e ndoshta ka për të shkuar mbrapa në dy. Dhe kështu kjo është në rregull. Por prisni një minutë, madhësi një moment më parë ishte tre. Le të vetëm të bëjë një kontroll të shpejtë mendje e shëndoshë. Si e dimë se ne donte për të hequr qafe të 61? Sepse ne jemi duke popping. Dhe kështu që unë kam këtë madhësi të dytë të pronës. 

Prisni një minutë, unë jam të menduarit prapa në javën e dytë kur kemi filluar duke folur për vargjeve, ku kjo ishte vend zero, kjo ishte një vend, kjo ishte vend dy, kjo është vendndodhja tre, katër, kjo duket si Marrëdhënia në mes të madhësisë dhe elementi që unë dua për të hequr nga array duket të jetë vetëm çfarë? Madhësia minus një. Dhe kështu kjo është se si si njerëzit ne e dimë se 61 vjen e para. Si është kompjuteri do të di? Kur kodin tuaj, ku ju ndoshta doni të bëni një madhësi minus, kështu tre minus një është dy dhe që do të thotë që ne duam të heqin qafe e 61. Dhe pastaj ne vërtet mund të rinovuar madhësia kështu që madhësia tani shkon nga tre deri në vetëm dy. Dhe vetëm të jetë pedant, unë jam duke shkuar të propozojë që unë jam duke bërë, e drejtë? Ju propozuar intuitivisht korrekt unë duhet të heqin qafe e 61. Por nuk e kanë unë lloj i lloj i marrë shpëtoj prej 61? Unë e kam harruar në mënyrë efektive se kjo është në të vërtetë atje. Dhe mendoj se mbrapa për PSET4, në qoftë se ju keni lexuar artikulli për mjekësinë ligjore, PDF që kemi pasur ju djema lexuar, apo ju do të lexoni këtë javë për PSET4. Kujtojnë se kjo është në fakt përshtatshëm për e gjithë ideja e kompjuterit mjekësinë ligjore. Çfarë një kompjuter në përgjithësi nuk është ai thjesht harron aty ku diçka është, por kjo nuk do të shkojnë në dhe si përpiqen për të zeroja atë apo refuzo ato pjesë me zero dhe ato apo ndonjë model tjetër të rastit nëse ju vetë ta bërë këtë qëllimisht. Pra, intuita juaj ka qenë e drejtë, le të heqin qafe e 61. Por në realitet, ne nuk duhet të shqetësojë. Ne vetëm duhet të harrojmë se është atje duke ndryshuar madhësinë tonë. 

Tani ka një problem me këtë rafte. Nëse unë mbaj shtyjnë gjërat mbi rafte, çfarë është padyshim do të ndodhë në vetëm një kohë pak momente? Ne jemi duke shkuar për të drejtuar nga hapësira. Dhe çfarë bëjmë ne? Ne jemi lloj i dehur. Ky zbatim nuk do të le na resize array, sepse duke përdorur kjo sintaksë, në qoftë se ju mendoj se mbrapa në javën e dytë, një herë ju keni deklaruar madhësia e një grup, ne nuk kemi parë ende një mekanizëm ku ju mund të ndryshojë madhësinë e vektorit. Dhe me të vërtetë C nuk e ka atë funksion. Në qoftë se ju thoni Më jep pesë Nths, i thirrët ata numrat, kjo është e gjitha që ju jeni do të merrni atë. Pra, ne bëjmë tani si nga e hëna, kanë aftësia për të shprehur një zgjidhje edhe pse, ne vetëm duhet të shkulje përkufizimi i rafte tonë të mos jetë një grup i vështirë-koduar, por vetëm për të ruajtur një adresë. 

Tani pse është kjo? Tani ne vetëm duhet të jenë të kënaqur me fakti që kur programi im shkon, Unë jam me sa duket duke shkuar për të duhet të pyesni njerëzore, Sa numra nuk ju duan për të ruajtur? Pra, të dhëna duhet të vijë nga diku. Por një herë unë e di se numrin, atëherë unë mund vetëm përdorin atë që të funksionojë për të dhënë mua një copë e kujtesës? Unë mund të përdorin malloc. Dhe unë mund të them ndonjë numër të bytes Unë dua përsëri për këto Nths. Dhe të gjitha unë kam për të ruajtur në numrat ndryshueshme këtu brenda këtij struct duhet të jetë ajo? Çfarë në të vërtetë shkon në të numrat në këtë skenar? Po, një tregues për të parë byte e atij copë e kujtesës, ose më saktë, adresa nga të parët e këtyre bytes. Nuk ka rëndësi nëse është një byte ose një miliardë bytes, Unë vetëm duhet të kujdesen për të parë. Sepse ajo që garanton malloc dhe mi garanton sistemit operativ, është se copë e kujtesës I merrni, ajo do të jetë e afërt. Nuk do të jetë boshllëqe. Pra, nëse unë kam kërkuar për 50 bytes ose 1,000 bytes, ata të gjithë do të jenë të për të kthyer prapa në shpinë. Dhe për aq kohë sa unë kujtoj se sa i madh, sa shumë i kërkuar, të gjitha unë duhet të dini është adresa e parë e tillë. 

Deri tani ne kemi aftësinë në kod. Megjithëse, ajo do të na më shumë kohë për të shkruar këtë ide, ne tani mund të shpërndajnë atë kujtesën nga vetëm ruajtjen e një adresë tjetër atje në qoftë se ne duam një të madhe apo edhe të një copë të vogël të kujtesës. Kështu që këtu për një off tregtisë. Tani kemi marrë dinamizëm. Ne ende kemi contiguousness Unë jam duke pretenduar. Sepse malloc do të na japë një copë puqur e kujtesës. Por kjo do të jetë një dhimbje në qafa për ne, programues, që në fakt të kodit lart. Kjo është vetëm më shumë punë. Ne kemi nevojë për kodin ngjashme me atë që unë kam qenë banging jashtë vetëm një moment më parë. Shumë që mund të bëhet, por ajo shton kompleksitetin. Dhe kështu kohë zhvillues, programues Ora është edhe një burim që ne të mund të kenë nevojë për të shpenzuar disa kohë për të marrë tipare të reja. Dhe pastaj sigurisht ka një radhë. Ne nuk do të shkojë në këtë një në shumë detaje. Por kjo është shumë e ngjashme në shpirt. Unë mund të zbatojë një radhë, dhe operacionet e saj përkatëse, enqueue ose dequeue, si të shtoni ose hiqni, kjo është vetëm një mënyrë për njohës të thënë atë, enqueue ose dequeue, si më poshtë. Unë vetëm mund të jap vetes një e strukturës që përsëri ka një numër të array, që ka një madhësi përsëri, por pse nuk kam nevojë për tani të mbajnë gjurmët e para të një radhë? Unë nuk duhet të dini e përparme e rafte tim. E pra, në qoftë se unë sërish për një queue-- le të vetëm e vështirë kodin atë si ka si pesë integers në këtu potencialisht. Pra, kjo është zero, një, dy, tre, katër. Kjo do të jetë quajtur numra përsëri. Dhe kjo do të quhet madhësi. 

Pse nuk mjafton të ketë vetëm madhësi? E pra, le të shtyjë ato numra të njëjta në. Kështu që unë pushed-- unë enqueued, ose shtyrë. Tani unë do enqueue 50, dhe pastaj 51, dhe pastaj 61, dhe dot dot dot. Pra, kjo është enqueue. Unë enqueued 50, pastaj 51, pastaj 61. Dhe kjo duket identike në një pirg deri tani, përveç Unë kam nevojë për të bërë një ndryshim. Unë kam nevojë për të rinovuar këtë madhësi, kështu që unë shkoj nga zero në një të dy deri në tre tani. Si mund të dequeue? Çfarë ndodh me dequeue? Kush duhet të vijnë jashtë në këtë listë për herë të parë në qoftë se është vija në Apple Store? Pra, 50. Pra, kjo është lloj i komplikuar këtë herë. Ndërsa herën e fundit ai ishte super lehtë për të vetëm të bëjë një madhësi minus, Unë shkoj në fund të array tim në mënyrë efektive ku numrat janë, ajo heq 61. Por unë nuk dua për të hequr 61. Unë dua të të marrë 50, i cili ishte atje at 5:00 AM të vijë deri për iPhone i ri apo gjësend. Dhe kështu për të hequr qafe e 50, unë nuk mund vetëm të bëjë këtë, apo jo? Unë mund të kalojnë nga 50. Por ne vetëm thamë nuk duhet të jetë aq anal si për të heq nga ose fshehur të dhënat. Ne vetëm mund të harrojmë se ku është. 

Por në qoftë se unë të ndryshojë madhësinë e mia tani për dy, është ky informacion i mjaftueshëm të dinë se çfarë po ndodh në radhë time? Jo ne te vertete. Ashtu si madhësia ime është dy, por ku fillon radhë, veçanërisht në qoftë se unë ende kam ato numra të njëjta në kujtesë. 50, 51, 61. Kështu që unë duhet të mbani mend tani ku front është. Dhe kështu si unë propozuar deri atje, ne do të kemi quajtur vetëm Front n, fillestar i të cilit Vlera duhet të ketë qenë çfarë? Zero, vetëm fillimi i listës. Por tani përveç decrementing madhësia, ne vetëm rrisim front. Tani këtu është një tjetër problem. Pra, një herë unë do të mbajë. Supozoni se ky është numri i si 121, 124, dhe pastaj, dammit, Unë jam nga hapësira. Por prisni një minutë, unë nuk jam. Pra, në këtë pikë në histori, mendoj se madhësia është një, dy, tre, katër, kështu mendoj që Madhësia është katër, front është një, kështu 51 është në para. Unë dua të vënë një numër tjetër këtu, por, dammit, unë jam nga hapësira. Por unë nuk jam me të vërtetë, e drejtë? Ku mund të vërë pak Vlera shtesë, si 171? Po, unë mund vetëm lloj i kthehem atje, apo jo? Dhe pastaj kalojnë jashtë 50, apo vetëm prishësh atë me 171. Dhe në qoftë se ju jeni të pyesin se pse numrat tanë mori aq të rastësishme, këto janë marrë zakonisht kompjuter kurse shkenca në Harvard pas CS50. Por kjo ishte një optimization mirë, sepse tani unë nuk jam humbur hapësirë. Unë ende duhet të mbani mend sa e madhe kjo gjë është totale. Kjo është pesë totale. Sepse unë nuk dua të të fillojë overwriting 51. Kështu që tani unë jam ende jashtë hapësirës, kështu të njëjtin problem si më parë. Por ju mund të shihni se si tani në kodin tuaj, ju ndoshta duhet të shkruaj pak më shumë Kompleksiteti për të bërë që të ndodhë. Dhe në fakt, çfarë operator në C ndoshta lejon të ju magjike bëni kjo qarkore? Po operatori modulo, shenjë për qind. Pra, çfarë është lloj i ftohtë në lidhje me radhë, edhe pse ne të mbajë vizatim vargjeve si këto rreshta si të drejtë, në qoftë se ju lloj të mendojnë për këtë si curving rreth si një rreth, atëherë vetëm intuitive ai lloj i punon mendërisht Unë mendoj se një pak më të pastër. Ju ende do të duhet të zbatojë se modeli mendor në kod. Pra, nuk është se e vështirë, në fund të fundit, për të zbatuar, por ne ende humbasin size-- më mirë, aftësia për të resize, nëse ne e bëjmë këtë. 

Ne kemi për të hequr qafe grup, ne zëvendësuar me një tregues të vetme, dhe pastaj diku në kodin tim unë kam marrë Një telefonatë çfarë funksionojë në fakt krijojnë array quajtur numrat? Malloc, ose ndonjë të ngjashëm funksion, pikërisht. Çdo pyetje mbi oxhaqet apo rradhë. Po? Pyetje e mirë. Çfarë modulo do të përdorni këtu. Pra në përgjithësi, kur duke përdorur mod, ju do të bëni atë me madhësinë e Struktura e tërë e të dhënave. Pra, diçka si pesë apo kapacitet, nëse është konstante, është i përfshirë ndoshta. Por vetëm duke bërë modulo pesë ndoshta nuk është e mjaftueshme, sepse ne kemi nevojë të dimë të bëjmë ne përfundojë rreth këtu ose këtu ose këtu. Pra, ju jeni me siguri edhe do të duan të përfshijë madhësia e sendit, ose variabli para si. Pra, kjo është vetëm kjo relativisht e shprehje e thjeshtë aritmetike, por modulo do të jetë përbërës kyç. 

Film kaq të shkurtër, nëse ju do. Një animacion se disa folks në një universitet tjetër vënë së bashku se ne kemi përshtatur për këtë diskutim. Ajo përfshin Jack mësimi i faktet në lidhje me radhët e gjata dhe statistikat. 

FILM: Njëherë e një kohë, atje ishte një djalë i quajtur Jack. Kur ai erdhi për të bërë miq, Jack nuk kanë një aftësi. Kështu Jack shkoi për të biseduar me më djalë popullor ai e dinte. Ai shkoi në Lou dhe e pyeti: Çfarë të bëj? Lou pa se shoku i tij ishte me të vërtetë në gjendje të vështirë. E pra, ai filloi, vetëm shikoni se si ju jeni të veshur. A nuk keni ndonjë rroba me një vështrim të ndryshëm? Po, tha Jack. Unë i sigurt bëj. Ejani në shtëpinë time dhe Unë do të tregoj ato për ju. Kështu ata shkuan jashtë për Jack-së. Dhe Jack tregoi Lou kuti ku ai ruante të gjitha këmisha e tij, dhe pantallona e tij dhe çorape e tij. Lou tha: Unë shoh se ju keni të gjitha rrobat tuaja në një grumbull. Pse nuk ju vishni disa të tjerët herë në pak kohë? 

Jack tha, mirë, kur unë hequr rrobat dhe çorape, I larë ato dhe të vënë ato larg në kuti. Pastaj vjen e ardhshme në mëngjes, dhe lart unë hop. Unë shkoj në kuti dhe për të marrë rrobat e mia off krye. Lou kuptuan shpejt problemi me Jack. Ai e mbajti rroba, CD, dhe libra në rafte. Kur ai arriti për diçka për të lexuar ose të veshin, ai do të zgjedhin librin lartë ose të brendshme. Atëherë kur ai ishte bërë, ai do të vënë atë të drejtë përsëri. Kthehu ajo do të shkojë, në krye të rafte. Unë e di zgjidhje, tha një Loud triumfuese. Ju duhet të mësoni për të të fillojë duke përdorur një radhë. Lou mori rrobat e Jack dhe varur ato në dollap. Dhe kur ai kishte zbrazur kuti, ai vetëm flak atë. 

Pastaj ai tha: tani Jack, në fund të ditë, të vënë rrobat tuaja të majtë kur ju vënë ato larg. Pastaj nesër në mëngjes, kur ju shih kohë e mirë, të merrni rrobat tuaja në të djathtë, nga fund të linjës. A nuk e sheh? tha Lou. Ajo do të jetë aq e bukur. Ju do të veshin çdo gjë herë para se të veshin diçka të dy herë. Dhe me çdo gjë në rradhë në dollap e tij dhe raft, Jack filluar të ndihen mjaft i sigurt për veten e tij. Të gjitha në sajë të Lou dhe radhë e tij të mrekullueshme. SPEAKER 1: Të gjithë të drejtë, kjo është adorable. Pra, ajo që është me të vërtetë ndodh në nën kapuç tani? Se ne kemi pointers, se ne kemi malloc, se ne kemi aftësinë për të krijuar chunks e kujtesës për veten dinamike. Pra, kjo është një foto ne glimpsed vetëm ditë të tjera. Ne të vërtetë nuk banojnë në të, por kjo foto ka qenë duke shkuar në nën individualitet për disa javë tani. Dhe kështu kjo paraqet, vetëm një drejtkëndësh që ne i kemi tërhequr, memorie kompjuteri juaj. Dhe ndoshta kompjuteri juaj, ose CS50 ID, ka një Gigabyte e kujtesës ose RAM apo dy gigabajt apo katër. Kjo nuk ka rëndësi. Sistemi juaj operativ Windows apo Mac OS apo Linux, në thelb lejon programin tuaj të mendojnë se ajo ka qasje në tërësinë e memorie kompjuteri juaj, edhe pse ju mund të konkurrojnë programe të shumta në të njëjtën kohë. Pra, në realitet, kjo nuk ka të vërtetë punojnë. Por kjo është lloj i një iluzion dhënë për të gjitha programet tuaja. Pra, nëse keni pasur dy koncerte e RAM, kjo është se si kompjuteri mund të mendoj për atë. 

Tani rastësisht, një nga këto gjëra, njëra prej këtyre segmenteve të kujtesës, quhet një pirg. Dhe në të vërtetë në çdo kohë deri më tani në kodin shkrim që ju kanë quajtur një funksion, për shembull Main. Kujtojnë se çdo herë që unë kam memorie kompjuteri tërhequr së, Unë gjithmonë të tërheqë lloj i gjysma e një drejtkëndësh këtu dhe nuk e mërzit duke folur për atë që është më lart. Sepse kur kryesor është quajtur, unë pretendojnë që ju të merrni këtë copë e kujtesës që shkon poshtë këtu. Dhe në qoftë se kryesore e quajti një funksion si shkëmbim, shkëmbim dhe shkon këtu. Dhe kjo rezulton, se është ku është duke përfunduar. Në diçka të quajtur një pirg brenda kujtesën e kompjuterit tuaj. Tani në fund të ditës, kjo është vetëm trajton. Është si bajt zero, byte një, bajt 2 miliard. Por në qoftë se ju mendoni rreth saj si ky objekt drejtkëndëshe, të gjithë ne jemi duke bërë çdo herë ne e quajmë një funksion është layering një fetë të ri të kujtesës. Ne jemi duke i dhënë këtë funksion një fetë e kujtesës së vet për të punuar me të. 

Dhe kujtoj tani se kjo është e rëndësishme. Sepse në qoftë se ne kemi diçka si shkëmbim dhe dy variabla lokale si A dhe B dhe ne të ndryshojë këto vlera nga një dhe dy për të dy dhe një, kujtojnë se kur shkëmbim të kthehet, kjo është sikur ky fetë e kujtesës është zhdukur vetëm. Në realitet, ajo është ende e atje nga mjekësia ligjore. Dhe diçka është ende në të vërtetë atje. Por konceptualisht, është si të edhe pse kjo është zhdukur plotësisht. Dhe kështu kryesor nuk di ndonjë nga puna që është bërë në këtë funksion swap, nëse është e kaluar në të vërtetë në ato Argumentet nga akrep ose me referencë. Tani, zgjidhja themelore për këtë problem me shkëmbim po kalon gjërat në me adresë. Por kjo rezulton, gjithashtu, se çfarë është qenë duke shkuar në mbi atë pjesë e drejtkëndësh gjithë kjo kohë është ende nuk ka më shumë memorie deri atje. Dhe kur ju dinamike të siguroj kujtesë, nëse kjo është brenda e getString, e cila ne kemi qenë bërë për ju në CS50 bibliotekë, ose në qoftë se ju djema thërrasë malloc dhe të kërkojë sistemi operativ për një copë të kujtesës, kjo nuk vjen nga rafte. Ajo vjen nga një vend tjetër në kujtesën e kompjuterit tuaj që është quajtur grumbull. Dhe kjo nuk është ndryshe. Është e njëjta RAM. Është e njëjta kujtesës. Është vetëm RAM që është deri atje në vend të poshtë këtu. 

Dhe kështu çfarë do të thotë? E pra, në qoftë se kompjuteri juaj ka një sasi e caktuar e kujtesës dhe rafte është në rritje deri, kështu që për të folur, dhe tog, sipas në këtë shigjetë, po rritet poshtë. Me fjalë të tjera, çdo herë ju e quani malloc, ju jeni duke i dhënë një fetë e kujtesës nga lart, atëherë ndoshta pak më e ulët, atëherë pak më të ulët, çdo herë që ju e quani malloc, tog, është përdorimi, është lloj i në rritje, rritje afër dhe më afër për çfarë? Rafte. Pra, e bën këtë të duket si një ide e mirë? Unë do të thotë, kur kjo nuk është e vërtetë e qartë çfarë tjetër që ju mund të bëni nëse ju vetëm kanë një sasi e fundme e kujtesës. Por kjo është sigurisht e keqe. Këto dy shigjetat janë nga një përplasje kurs për njëri-tjetrin. 

Dhe kjo rezulton se djalë i keq, njerëzit që janë veçanërisht të mira me programimin, dhe duke u përpjekur të kollitem në kompjuterë, mund të shfrytëzojnë këtë realitet. Në fakt, le të konsiderojmë një copë të vogël. Pra, ky është një shembull ju mund të lexoni për më në detaje në Wikipedia. Ne do të ju pikë në nivel neni nëse kurioz. Por ka një sulm në përgjithësi i njohur si tampon del nga shtrati se ka ekzistuar për aq kohë sa njerëzit kanë pasur aftësinë për të manipuluar memorie kompjuteri, veçanërisht në C. Pra, ky është një program shumë arbitrare, por le të lexojnë atë nga poshte lart. Kryesor në yll argc char argv. Pra, kjo është një program që merr argumente command line. Dhe të gjithë kryesor ka me sa duket është thirrja një funksion, e quajti atë F për thjeshtësi. Dhe ai kalon në çfarë? Argv e një. Pra, ai kalon në F çfarëdo fjala është se përdoruesi shtypur në ftim pas fillimit Emri i programit në të gjitha. Aq shumë si Cezarit apo Vigenere, e cila ju mund të kujtojnë bërë me argv. 

Pra, çfarë është F? F merr në një varg si argument e tij të vetëm, AKA një yll char, njëjtë gjë, si një varg. Dhe ajo që quhet në mënyrë arbitrare bar në këtë shembull. Dhe pastaj char c 12, vetëm në kushtet e laik, ajo që është char c parantezë 12 duke bërë për ne? Çfarë të bëjë? Caktimin e kujtesës, veçanërisht 12 bytes për 12 karaktere. Pikërisht. Dhe pastaj vija e fundit, llokoçis dhe kopje, ju keni ndoshta nuk shihet. Kjo është një kopje varg funksioni qëllimi i të cilit në jetë është të kopjoni argumentin e tij të dytë në argumentin e saj të parë, por vetëm deri në një numër i caktuar i bytes. Pra, argumenti i tretë thotë: Sa bytes duhet të kopjoni? Gjatësia e bar, çfarëdo përdoruesi shtypur në. Dhe përmbajtjen e bar, atë varg, janë kopjuar në kujtesën vuri në në C. 

Pra, kjo duket lloj i trashë, dhe kjo është. Kjo është një shembull i ndërtuar, por kjo është përfaqësuese e një klase të vektorëve sulm, një mënyrë për të sulmuar një program. Të gjitha është e mirë dhe e mirë në qoftë se përdoruesi lloje në një fjalë që është 11 karaktere ose më pak, plus backslash zero. Çfarë ndodh nëse lloje përdorues në më shumë se 11 ose 12 ose 20 ose 50 karaktere? Çfarë është ky program do të bëni? Faji Potencialisht seg. Po shkon për të verbërisht kopje çdo gjë në bar deri në gjatësinë e saj, e cila është fjalë për fjalë çdo gjë në bar, në adresën e vuri në C. Por C vetëm i ka dhënë preemptively si 12 bytes. Por nuk ka asnjë kontroll shtesë. Nuk ka nëse kushte. Nuk ka gabim kontrolluar këtu. 

Dhe kështu ajo që ky program është do të bëni është vetëm verbërisht kopjoni një gjë në tjetrën. Dhe kështu që nëse ne tërheqim këtë si një foto, këtu është vetëm një copë të hapësirës kujtesës. Pra, vini re në fund, ne kanë bar lokal ndryshueshme. Kështu që pointer që po ndodh për të store-- më tepër këtë argument lokal që është duke shkuar për të ruajtur bar string. Dhe pastaj vini re vetëm sipër në një pirg, sepse çdo herë që ju kërkoni për kujtesën në rafte, ajo shkon pak mbi të në pikturë, njoftim se ne kemi marrë 12 bytes atje. Një e sipërm të majtë është C kllapa zero dhe një e drejtë fund është C kllapa 11. Kjo është vetëm se si kompjuterët duke shkuar për të hedhur atë jashtë. Pra, vetëm intuitive, nëse bar ka më shumë se 12 karaktere në total, duke përfshirë backslash zero, ku është 12 ose kllapa C 12 do të shkojnë? Ose më mirë ku është 12 karakter ose karakteri 13, karakteri njëqindtë shkuar të përfundojnë në foto? Mbi ose nën? 

E drejtë, sepse edhe pse rafte vetë rritet lart, një herë ju keni vënë gjëra në ajo, kjo për arsye të projektimit, vë kujtesën nga lart poshtë. Pra, nëse keni më shumë se 12 bytes, ju jeni do të fillojnë të prishësh bar. Tani që është një bug, por kjo është jo me të vërtetë një punë e madhe. Por kjo është një punë e madhe, sepse nuk ka më shumë gjëra në vazhdim e sipër në kujtesë. Kështu që këtu është se si ne mund vënë përshëndetje, të jetë i qartë. Nëse unë shtypur në përshëndetje në ftim. H-E-L-L-O backslash zero, mbaron brenda këto 12 bytes, dhe ne jemi super të sigurt. Gjithcka eshte mire. Por në qoftë se unë lloji diçka gjatë, potencialisht është do të na zvarrisë në hapësirë ​​bar. Por më keq akoma, ajo kthehet jashtë gjithë kësaj kohe, edhe pse ne kurrë nuk kam biseduar për ajo, rafte është përdorur për gjëra të tjera. Kjo nuk është vetëm ndryshoret lokale. 

C është një gjuhë nivel shumë të ulët. Dhe kjo lloj fshehurazi përdor rafte edhe për të kujtuar kur një Funksioni quhet, çfarë adresa është e funksionit të mëparshëm, kështu që mund të hidhen përsëri në atë funksion. Pra, kur thirrjet kryesore të bie në ujdi, në mesin e gjërat e shtyrë mbi rafte nuk janë vetëm këmbime ndryshoret lokale, ose argumentet e saj, gjithashtu shtyu fshehurazi mbi rafte si të përfaqësuar nga fetë e kuqe këtu, është adresa e kryesor fizikisht në kujtesën e kompjuterit tuaj, kështu që kur shkëmbim është bërë, kompjuteri e di se kam nevojë për të shkuar mbrapa në kryesore dhe të përfundojë ekzekutimin e funksionit kryesor. Pra, kjo është e rrezikshme tani, sepse në qoftë se lloje përdorues në edhe më shumë se përshëndetje, të tilla që input të përdoruesit clobbers ose overwrites atë pjesë të kuqe, logjikisht nëse kompjuteri-së vetëm duke shkuar për të marrë verbërisht se bytes në atë fetë e kuqe janë adresën në të cilën ai duhet të kthehet, çfarë nëse kundërshtari është mjaft i zgjuar apo fat të mjaftueshme për të vënë një sekuencë e bytes atje që duket si një adresë, por kjo është adresa e kodit se ai apo ajo dëshiron kompjuterin për të ekzekutuar në vend të kryesor? 

Me fjalë të tjera, në qoftë se ajo që përdorues është shtypur në prompt, nuk është vetëm diçka si i padëmshëm hello, por është e vërtetë kodin që është ekuivalent për të fshirë të gjitha dosjet e këtij përdoruesit? Ose email fjalëkalimin e tyre për mua? Ose të fillojnë prerjet e tyre tasteve, e drejtë? Nuk është një mënyrë, le të përcaktojnë sot, se ata mund të shkruani jo vetëm përshëndetje bota apo emrin e tyre, ata mund të në thelb kalojë në kod, zero dhe ato, që kompjuteri gabime për të dy kodit dhe një adresë. Pra, megjithëse disi abstrakte, në qoftë se lloje përdorues në kodin mjaftueshme kundërshtuese se ne do të përgjithësojmë këtu si A. Një është sulm apo kundërshtarë. Sende kështu që vetëm të këqija. Ne nuk e kujdesit në lidhje me Numrat apo zero, ose ato sot, të tilla që ju të përfundojë overwriting atë pjesë të kuqe, vini re se rend e bytes. O 835 C zero tetë zero. Dhe tani si artikull Wikipedia këtu ka propozuar, në qoftë se ju tani vërtetë të filloni etiketimin bytes në kompjuterit tuaj kujtesës, çfarë artikull Wikipedia është propozues është se, çfarë nëse adresa e atij bajt e sipërm të majtë është 80 C 0 3508. 

Me fjalë të tjera, në qoftë se djalë i keq është mjaft i zgjuar me kodin e tij ose të saj të vërtetë vënë një numër këtu se korrespondon me adresën e kodit ai ose ajo injektuar në kompjuter, ju mund të gënjejnë në kompjuter në bërë asgjë. Heqja fotografi, emailing gjëra, nuhatës trafikut tuaj, fjalë për fjalë çdo gjë mund të jetë injektuar në kompjuter. Dhe kështu një del nga shtrati tampon Sulmi në thelbin e vet është vetëm një budalla, budalla parësor i një grup që nuk kanë kontrolluar kufijtë e saj. Dhe kjo është ajo që është super i rrezikshëm dhe njëkohësisht super të fuqishme në C është se ne vërtet kemi Qasje për të kudo në kujtesën. Është e deri te ne, programuesit, që shkruani kodin origjinale për të kontrolluar kohëzgjatjen e mallkuar e ndonjë vargjeve që ne jemi duke manipuluar. Pra, të jetë i qartë, çfarë është fix? Nëse do të rrokulliset përsëri në këtë kodi, unë nuk duhet vetëm ndryshojë gjatësinë e bar, çfarë tjetër duhet të jenë të kontrolluar? Çfarë tjetër duhet të jetë bërë për të parandaluar këtë sulm krejtësisht? Unë nuk dua të them vetëm verbërisht që ju duhet të kopje sa më shumë bytes si është gjatësia e bar. Dua të them, kopjoni si shumë bytes siç janë në bar deri në të alokuar kujtesës, ose 12 maksimalisht. Kështu që kam nevojë për një lloj të në qoftë se gjendja që e bën të kontrolluar kohëzgjatjen e bar, por në qoftë se ajo tejkalon 12, ne kodin vetëm e vështirë 12 si distancë maksimale të mundshme. Ndryshe e ashtuquajtura tampon sulm del nga shtrati mund të ndodhë. Në fund të këtyre slides, në qoftë se ju jeni kurioz për të lexuar më shumë është artikull aktual origjinal në qoftë se ju dëshironi të marrë një sy. 

Por tani, në mesin e çmimeve paguar këtu ishte joefikasiteti. Kështu që ishte një i shpejtë vështrim në atë nivel të ulët Problemet mund të lindin tani që ne kanë qasje në kujtesë kompjuterit. Por një tjetër problem ne tashmë ngecur hënën ishte vetëm joefikasiteti nga një listë e lidhur. Ne jemi prapa në kohë lineare. Ne nuk kemi një rrjet të puthitur. Ne nuk kemi qasje të rastit. Ne nuk mund të përdorë katror simbol kllapa. Ne fjalë për fjalë duhet të përdorni një lak, ndërsa si ajo që kam shkruar një moment më parë. Por të hënën, kemi pohuar se ne mund të zvarriten përsëri në fushën e efikasitetit arritur diçka që është logaritmike ndoshta, ose më mirë akoma, ndoshta edhe diçka që është ashtuquajtura kohë konstante. Pra, si mund ta bëjmë atë duke përdorur këto të reja mjetet, këto adresa, këto pointers, dhe fillesë gjërat e vet tonë? E pra, mendoj se këtu, këto janë një bandë e numrave që ne duam për të ruajtur në një Struktura e të dhënave dhe të kërkimit në mënyrë efikase. Ne mund absolutisht rewind në javë dy, hedhin ato në një rrjet, dhe kërko ato duke përdorur search binar. Përça dhe sundo. Dhe në fakt ju ka shkruajtur Kërko binar në PSET3, ku ju zbatuar programin gjeni. Por ju e dini se çfarë. Nuk është lloj i një më të mënyrë e zgjuar për të bërë këtë. Kjo është pak më shumë sofistikuar dhe kjo ndoshta na lejon të shohim se pse binar Kërkimi është aq shumë më e shpejtë. Së pari, le të prezantoj nocioni i një peme. E cila edhe pse në Pemët realitet lloj i rritet si ky, në botën e kompjuterit shkenca ata lloj i rriten në rënie si një pemë familjare, ku ju duhet gjyshërit tuaj ose gjyshërit e madhe ose gjësend në krye, patriarkun dhe matriarch e familjes, vetëm një ashtuquajtura rrënjë, nyje, më poshtë të cilat janë fëmijët e saj, më poshtë të cilat janë fëmijët e saj, ose Pasardhësit e tij në përgjithësi. Dhe kushdo varur jashtë në fund të familjes pemë, përveç të qënit më i ri në familje, mund të jetë vetëm generically quajtur gjethet e pemës. 

Pra, kjo është vetëm një bandë e fjalëve dhe përkufizimet për diçka të quajtur një pemë në kompjuterin shkenca, ashtu si një pemë familjare. Por ka incarnations njohës e pemeve, njëri prej të cilëve është quajtur një pemë binare e kërkimit. Dhe ju mund të lloj i vë në lojë përveç asaj që kjo gjë e bën. E pra, kjo është binar në çfarë kuptimi? Ku ka binar ardhur nga këtu? Na vjen keq? Kjo nuk është aq shumë një ose ose. Kjo është më shumë se secili prej nyjeve nuk ka më shumë se dy fëmijë, siç e shohim këtu. Në përgjithësi, një tree-- dhe prindërit dhe gjyshërit mund të ketë sa më shumë fëmijë apo grandkids si ata në fakt duan, dhe kështu për shembull nuk kemi tre Fëmijët off se nyje djathtë, por në një pemë binare, një nyje ka zero, një, ose dy fëmijë maksimalisht. Dhe kjo është një pronë e bukur, sepse në qoftë se është e mbuluar nga dy, ne do të jetë në gjendje të të marrë një bazë të vogël log dy veprim ndodh këtu në fund të fundit. Pra, ne kemi diçka logaritmike. Por më shumë se në një moment. Kërko pemë do të thotë se numrat janë rregulluar tillë që fëmija e majtë të vlerë është më e madhe se rrënjës. Dhe fëmija e saj është e drejtë më të mëdha se rrënjë. Me fjalë të tjera, në qoftë se ju merrni ndonjë nga nyjet, qarqet në këtë foto, dhe shikon në të majtë të saj fëmijë dhe fëmija e saj e drejtë, e para duhet të jetë më pak se, e dyta duhet të jetë më i madh se. Pra, mendje e shëndoshë kontrolloni 55. Ajo ka lënë fëmijë është 33. Kjo është më pak se. 55, fëmija i saj e drejtë është 77. Kjo është më e madhe se. Dhe kjo është një përkufizim gjithkund rekursive. Ne mund të kontrolloni çdo një nga ato nyjet dhe i njëjti model do të mbajë. 

Pra, çfarë është e bukur në një Kërkimi pemë binare, është se një, ne mund të zbatojë atë me një struct, ashtu si kjo. Dhe, edhe pse ne jemi duke hedhur shumë strukturave në tuaj, ata janë disi intuitive tani shpresë. Sintaksa është ende misterioze e sigurt, por përmbajtja e një nyje në këtë context-- dhe do të vazhdojmë të përdorur fjalën nyje, nëse kjo është një drejtkëndësh në ekran ose një rreth, kjo është vetëm një enë të përgjithshme, në këtë rast të një pemë, si ai ne pamë, ne kemi nevojë për një numër të plotë në secilën prej nyjeve dhe pastaj kam nevojë për dy Pointers treguar për fëmijën e majtë dhe të djathtë të fëmijës, përkatësisht. Pra, kjo është se si ne mund zbatuar që në një struct. Dhe si mund ta zbatojë atë në kodin? E pra, le të marrin një shpejtë Shikojeni këtë shembull të vogël. Kjo nuk është funksionale, por unë kam kopjohet dhe të ngjit atë strukturë. Dhe në qoftë se funksioni im për një binar pemë Kërkimi quhet kërkimit, dhe kjo merr dy argumente, një numër të plotë n dhe një tregues në një nyje, kështu një tregues për pemë ose një tregues për rrënjët e një pemë, Si mund të shkoj në lidhje me kërkim për N? E pra, së pari, sepse unë jam i që kanë të bëjnë me pointers, Unë jam duke shkuar për të bërë një kontroll mendje e shëndoshë. Nëse barabartë pemë është e barabartë null, eshte N në këtë pemë apo jo në këtë pemë? Ajo nuk mund të jetë, e drejtë? Nëse unë jam e kaluara null, nuk ka asgjë atje. Unë mund edhe të vetëm verbërisht thonë kthimit të rreme. Në qoftë se ju më jepni asgjë, unë me siguri nuk mund të gjeni ndonjë N. numrin Pra, çfarë tjetër mund unë shikoni tani? Unë jam duke shkuar për të thënë edhe tjetër nëse n është më pak se çdo gjë që është në nyjen pemë që unë kam qenë dorëzuar vlerën N. Me fjalë të tjera, nëse numri unë jam kërkoni për, N, është më pak se nyjen që unë jam duke kërkuar në. Dhe nyja unë jam duke kërkuar në është quajtur dru, dhe kujtojnë nga shembulli i mëparshëm për të marrë në vlerën në një tregues, I përdorin arrow simbol. Pra, nëse N është më pak se pemë shigjetë N, unë dua të shkoj konceptualisht majtë. Si mund të shpreh kërkim lënë? Për të qenë të qartë, në qoftë se kjo është fotografia në fjalë, dhe unë kam kaluar se larti shigjetë që është vënë poshtë. Kjo është pema akrep ime. Unë jam vënë në rrënjë të pemës. Dhe unë jam duke kërkuar të themi, për numrin 44, në mënyrë arbitrare. Është 44 me pak se ose më i madh se 55 padyshim? Pra, kjo është më pak se. Dhe kështu kjo nëse kusht vlen. Pra konceptualisht, çfarë unë dua të kërko tjetër në qoftë se unë jam duke kërkuar për 44? Po? 

Pikërisht, unë dua të kërko fëmijën e majtë, ose nën-pema u largua nga kjo foto. Dhe në fakt, më lejoni përmes foto poshtë këtu për vetëm një moment, që nga Unë nuk mund ta heq këtë. Nëse unë të fillojë këtu në 55, dhe Unë e di se vlera 44 Unë jam duke kërkuar për të është që të e majta, kjo është lloj e si marramendës librin e telefonit në gjysma ose marramendës pemë në gjysmë. Unë nuk duhet të kujdesen për tërë kjo gjysma e pemës. Dhe akoma, interesant në aspektin e Struktura, kjo gjë mbi këtu se fillon me 33, që në vetvete është një pemë binare e kërkimit. Unë i thashë fjalën rekursive para sepse në të vërtetë kjo është një strukturë e të dhënave që sipas definicionit është rekursive. Ju mund të keni një pemë që është kjo i madh, por çdo njëri prej fëmijëve të saj përfaqëson një pemë vetëm një pak më të vogël. Në vend të saj të qënit gjysh ose gjyshe, tani ajo është vetëm nëna or-- unë nuk mund të mos say-- mom apo baba, që do të jetë i çuditshëm. Në vend të dy fëmijët atje do të jetë si vëlla e motër. Një brez i ri pemën familjare. Por strukturore, kjo është e njëjta ide. Dhe kjo rezulton unë kam një funksion me të cilën unë mund të kërkoni një kërkim binar pemë. Ajo quhet kërkimit. Unë të kërkuar për N në pemë shigjetë majtë përndryshe nëse n eshte me e madhe se vlera se unë jam aktualisht në. 55 në histori një moment më parë. Unë kam një funksion të quajtur kërkim që unë mund vetëm kalojë N kjo dhe Recursively kërko nën-pemë dhe vetëm kthimi çfarëdo që përgjigja. Tjetër unë kam marrë disa rastin përfundimtar bazë këtu. 

Çfarë është rasti i fundit? Tree është ose i pavlefshëm. Vlera Unë jam duke kërkuar për ose është pak se saj ose më e madhe se sa ose e barabartë me të. Dhe unë mund të them të barabartë të barabartë, por logjikisht kjo është ekuivalent me vetëm duke thënë tjetër këtu. Aq e vërtetë është se si unë të gjeni diçka. Kështu që shpresojmë se kjo është një edhe shembulli më bindëse se funksionit budallaqe sigma ne e bëmë një leksione pak prapa, ku ajo ishte po aq e lehtë për t'u përdorur një lak për të numëruar të gjithë numrat nga një të N. këtu me një strukturë të dhënave që në vetvete është Recursively përcaktuar dhe të tërhequr Recursively, tani ne kanë aftësinë për të shprehur veten në kodin që vetë është rekursive. Pra, kjo është e njëjta kod e saktë këtu. 

Pra, çfarë probleme të tjera mund të zgjidhim? Pra, një hap të shpejtë larg nga frutorë, për një moment të vetëm. Këtu është, të themi, flamurin gjerman. Dhe nuk ka mënyrë të qartë një model për këtë flamur. Dhe nuk ka shumë flamuj në botë që janë aq e thjeshtë sa kjo në aspektin të ngjyrave të tyre dhe modeleve. Por mendoj se ky është ruajtur si një GIF, ose nje JPEG, ose bitmap, ose nje ping, ndonjë file format grafik me të cilat ju jeni të njohur, disa prej të cilave ne jemi duke luajtur me në PSET4. Kjo nuk duket i vlefshëm për të ruajtur pixel e zezë, e zezë pixel, pixel e zezë, dot, dot, dot, një bandë e tërë e piksel zezë për scanline parë, ose rresht, pastaj një bandë e tërë e të njëjtën gjë, atëherë një bandë e tërë e njëjtë, dhe pastaj një tërë bandë e pixels kuqe, pixels kuqe, pixel e kuqe, pastaj një e tërë bandë e pixels verdhë, e verdhë, e drejtë? 

Ka joefikasiteti i tillë këtu. Si do të ju intuitive compress flamurin gjerman nëse zbaton atë si një skedar? Ashtu si çfarë informacioni ne nuk mund të mërzit ruajtjen në disk në mënyrë për të ulur madhësinë tonë skedarëve nga si një megabyte në një kilobyte, diçka më të vogla? Aty qëndron tepricë këtu të jetë i qartë? Çfarë mund të bëni? Po? Pikërisht. Pse nuk lejoni më mirë se mbaj mend ngjyra e çdo pixel mallkuar ashtu si ju jeni duke bërë në PSET4 me format file bitmap, pse nuk ju vetëm të përfaqësojë kolona pari nga e majta e pixels, për shembull një bandë e pixels zeza, një bandë e kuqe, dhe një bandë e verdhë, dhe pastaj vetëm disi shifroj Ideja e përsëritur këtë 100 herë ose të përsëritur këtë 1,000 herë? Ku 100 apo 1000 është vetëm një numër i plotë, kështu që ju mund të merrni larg me vetëm një numër të vetëm në vend të qindra ose mijëra pixel e tjera. Dhe me të vërtetë, kjo është se si ne mund të compress flamurin gjerman. Dhe Tani ajo që në lidhje me flamurin francez? Dhe një lloj i vogël ushtrim mendor, që flamuri mund të jetë i ngjeshur shumë në disk? Flamuri gjerman ose francez flamuri, nëse e marrim këtë qasje? Flamuri gjerman, sepse nuk ka më tepricë horizontale. Dhe me dashje, shumë skedar grafik Formatet vërtet punojnë si scan linjat horizontalisht. Ata mund të punojnë vertikalisht, vetëm njerëzimi vjet më parë vendosi që ne do të përgjithësisht mendojnë rresht gjëra nga rresht në vend të kolonës me kolonën. Pra, me të vërtetë, nëse ju keni qenë për të parë në dosjen Madhësia e një flamur gjerman dhe një francez flamurin, për sa kohë që rezoluta është e njëjta, të njëjtën gjerësi dhe lartësi, kjo këtu do të jetë më e madhe, sepse ju keni për të përsëritur veten tri herë. Ju duhet të specifikoni blu, të përsëritur veten, e bardhë, e përsëris veten, e kuqe, përsëris veten. Ju nuk mund të shkoni të gjithë mënyra në të djathtë. Dhe si një mënjanë, për të bërë qartë compression është kudo, nëse këto janë katër korniza nga një video-- ju mund të kujtojmë se një film ose video është përgjithësisht si 29 ose 30 korniza për sekondë. Është si një libër të vogël rrokullisje ku ju vetëm shikoni imazhit, imazhi, imazhi, imazhi, Imazhi vetëm super të shpejtë kështu që duket sikur aktorët në ekran janë duke lëvizur. Këtu është një bletë qullos në krye të një buqetë me lule. Dhe pse kjo mund të jetë lloj i vështirë për të parë në shikim të parë, e vetmja gjë që lëviz në ky film është bee. 

Çfarë është memec në lidhje me ruajtjen Video ngjeshur? Kjo është lloj i një humbje në dyqan video si katër imazhe pothuajse identike që ndryshojnë vetëm për aq sa ku bee është. Ju mund të hedhin larg më e atij informacioni dhe mos harroni vetëm, për shembull, korniza e parë dhe frame kaluar, korniza kryesore qoftë se ju keni dëgjuar ndonjëherë fjalën, dhe vetëm dyqan në mesme ku bee është. Dhe ju nuk keni për të ruajtur të gjithë të kuq, dhe blu, dhe Vlerat e gjelbër si edhe. Pra, kjo do të thotë vetëm se compression është kudo. Kjo është një teknikë që ne shpesh e përdorim ose të marrë për të dhënë këto ditë. 

Por si mund të ngjesh tekst? Si ju shkoni në lidhje me compressing tekst? E pra, secili nga personazhet në Ascii është një bajt, ose tetë bit. Dhe kjo është lloj i heshtur, e drejtë? Sepse ju ndoshta tipit A dhe E dhe I dhe O dhe U shumë më shpesh se si W ose Q apo Z, në varësi të gjuhës në të cilën ju jeni me shkrim me siguri. Dhe kështu që pse jemi duke përdorur tetë bit për çdo letër, duke përfshirë së paku letra popullore, e drejtë? Pse të mos i përdorin më pak bit për shkronjat super popullore, si E, gjërat që ju me mend për herë të parë në Wheel of Fortune, dhe përdorin më shumë bit për shkronjat më pak popullor? Përse? Sepse ne jemi vetëm do të përdorin ato më shpesh. 

E pra, ajo rezulton se ka pasur bërë përpjekje për të bërë këtë. Dhe në qoftë se ju kujtohet nga klasa shkollës ose shkollën e mesme, kodin Morse. Kodi Morse ka dots dhe dashes që mund të jetë transmetuar përgjatë një tel si Dashuri apo sinjalet e disa lloj. Por kodin Morse është një super të pastër. Kjo është lloj i një sistemi binar në që ju keni pika ose dashes. Por në qoftë se ju shihni, për shembull, dy pika. Ose në qoftë se ju mendoni përsëri për operatorin që shkon si bip, bip, bip, bip, duke goditur një shkas të vogël që transmeton një sinjal, në qoftë se ju, marrësi, merr dy pika, çfarë mesazhi keni marrë? Krejtësisht arbitrare. 

Unë? Unë? Ose çfarë? Për apo unë? Ndoshta ajo ishte vetëm dy e drejtë ë s? Pra, nuk ka ky problem i decodability me Morse Kodi, ku përveç nëse Personi i dërguar që ju mesazh në fakt pushimeve kështu që ju mund të lloj nga shohin ose dëgjojnë boshllëqet midis shkronjave, kjo nuk është e mjaftueshme vetëm për të dërgoni një rrjedhë e zero dhe ato, ose pika dhe dashes, sepse nuk ka paqartësi. E është një pikë e vetme, kështu që nëse ju shohim dy pika ose dëgjojnë dy pika, ndoshta është dy E-së apo ndoshta kjo është një I. Pra, ne kemi nevojë për një sistem që është një pak më të zgjuar se kaq. Pra, një njeri i quajtur Huffman vjet më parë doli me pikërisht këtë. Pra, ne jemi vetëm duke shkuar për të marrë një shikim të shpejtë se si pemët janë të përshtatshëm për këtë. Le të supozojmë se kjo është një Mesazhi budalla ju dëshironi të dërgoni, i përbërë nga vetëm A, B, C-së D's dhe E-së, por ka shumë tepricë këtu. Kjo nuk është menduar të jetë anglisht. Kjo nuk është e koduar. Është vetëm një mesazh budalla me shumë përsëritje. Pra, nëse ju në të vërtetë të mbështeteni nga të gjitha A-së, B-së, C-së, D's, dhe E-së, këtu është frekuenca. 20% e letrave janë A-së, 45% e letrave janë të E-së dhe tre frekuenca të tjera. Ne të numëruara deri atje me dorë dhe vetëm e bëri matematikë. 

Pra, rezulton se Huffman, disa kohë më parë, e kuptuan se, ju e dini çfarë, në qoftë se unë të fillojë ndërtimin e një pemë, apo pyll e pemëve, në qoftë se ju do të, si më poshtë, unë mund të bëjë në vijim. Unë jam duke shkuar për të dhënë një nyje për secilin nga letrat që i intereson dhe unë jam duke shkuar për të ruajtur brenda kësaj nyje frekuencat si një pikë lundrues vlerën, ose ju mund të përdorni atë një N, gjithashtu, por ne do të përdorim vetëm një noton këtu. Dhe algorithm që ai propozoi është se ju marrë këtë pyll të nyjeve të vetme pemë, pemë aq super të shkurtër, dhe ju filloni lidh ato me grupe të reja, prindërit e rinj, nëse ju do. Dhe ju bëni këtë duke zgjedhur dy frekuenca më të vogla në një kohë. Kështu që unë e mori 10% dhe 10%. Kam krijuar një nyje të re. Dhe unë e quaj nyjen ri 20%. 

Të cilat dy nyjet unë kombinoj tjetër? Kjo është pak i paqartë. Pra, ka disa raste qoshe për konsiderojnë, por për të mbajtur gjërat e bukur, Unë jam duke shkuar për të zgjedhur 20% - Unë tani injorojnë fëmijët. Unë jam duke shkuar për të zgjedhur 20% dhe 15% dhe të tërheqë dy tehe të reja. Dhe tani cilën dy nyjet mund logjikisht kombinohen? Ignore gjithë fëmijët, të gjithë të nipër e mbesa, vetëm shikoni në rrënjët tani. Të cilat dy nyje mund të lidhë së bashku? Pika dy dhe 0.35. Pra, më lejoni të nxjerrë dy tehe të reja. Dhe pastaj unë kam marrë vetëm një majtë. Kështu që këtu është një pemë. Dhe ajo është hartuar me qëllim të duken lloj i bukur, por vini re se edges kanë gjithashtu janë etiketuar zero dhe një. Pra, të gjitha skajet e majtë janë zero në mënyrë arbitrare, por në vazhdimësi. Të gjitha skajet e drejta janë ato. 

Dhe kështu ajo që Hoffman të propozuar është, në qoftë se ju doni për të përfaqësuar një B, në vend se të përfaqësojnë numrin 66 si një Ascii cila është tetë bit tërë, ju e dini se çfarë, vetëm dyqan model zero, zero, zero, zero, sepse kjo është rruga nga pema ime, pemë zotit Huffman-së, në fletë nga rrënja. Nëse ju doni për të ruajtur një E, nga ana tjetër, nuk dërgoni tetë bit që përfaqësojnë një E. Në vend të kësaj, dërgoni çfarë modeli i bit? Një. Dhe çfarë është e mirë për këtë është E kjo është letra më popullor, dhe ju jeni duke përdorur Kodi më të shkurtër për të. I ardhshëm më popullore Letra duket si ajo ishte A. Dhe kështu sa bit që ai të propozojë duke përdorur për këtë? Zero, një. 

Dhe për shkak se ajo është zbatuar si këtë pemë, tani për tani më lejoni të përcaktojnë ka nuk ka paqartësi si në Morse Kodi, sepse të gjithë e letra që ju intereson janë në fund të këtyre skajet. Pra, kjo është vetëm një Aplikimi i një pemë. Kjo is-- dhe unë do të valë dora ime kjo si ju mund të zbatojë këtë si një strukturë C. Ne vetëm duhet për të kombinuar një simbol, si një char, dhe frekuenca në majtë dhe të djathtë. Por le të shohim në dy shembujt e fundit që ju do të merrni mjaft të njohur me pas Quiz zero në problemin vendosur pesë. 

Pra, nuk është struktura e të dhënave i njohur si një tryezë hash. Dhe një tabelë hash është lloj i ftohet në atë që ka kova. Dhe mendoj që ka katër kova këtu, vetëm katër hapësira bosh. Këtu është një kuvertë të kartave, dhe këtu është klub, lopatë, klubi, diamante, klubi, diamante, klub, diamante, clubs-- kështu që kjo është e rastit. Zemra, hearts-- kështu që unë jam bucketizing gjitha inputeve këtu. Dhe një nevojë tabelë hash për të parë në kontributin tuaj, dhe pastaj të vënë atë në një farë zhvillohet bazuar në atë që ju shihni. Kjo është një algoritmi. Dhe unë isha duke përdorur një super algoritëm të thjeshtë vizuale. Pjesa më e vështirë e cila ishte kujtuar atë fotografitë ishin. Dhe pastaj nuk ka katër gjëra totale. 

Tani oxhaqet janë në rritje, e cila është një gjë e qëllimshme dizajn këtu. Por, çfarë tjetër mund të bëj? Pra, në fakt këtu kemi një bandë e librave të vjetër i provimeve të shkollës. Supozoni se një bandë e emrat e studentëve janë në këtu. Këtu është një tabelë e madhe hash. Në vend të katër kova, Unë kam, le të themi 26. Dhe ne nuk duam të shkuar të marrë hua 26 gjëra nga jashtë [? Annenberg?], Kështu që këtu është pesë që përfaqësojnë Një anë Z. Dhe në qoftë se unë shoh një student emri i të cilit fillon me A, Unë jam duke shkuar për të vënë tij ose quiz e saj atje. Nëse dikush fillon me C, atje, A-- në fakt, nuk dua të bëj atë. B shkon mbi këtu. Kështu që unë kam marrë A dhe B dhe C. Dhe Tani këtu është një tjetër Një studente. Por nëse kjo tabelë hash është realizuar me një grup, Unë jam lloj i dehur në këtë pikë, e drejtë? Unë lloj i duhet të vënë këtë diku. 

Pra, një mënyrë unë mund të zgjidhin këtë është, gjithë e drejtë, A është e zënë, B është e zënë, C është i zënë. Unë jam duke shkuar për të vënë atë në D. Pra, në së pari, unë kam qasje të rastit të menjëhershme secilit prej kova për nxënës. Por tani kjo është lloj i transferuar në diçka lineare, sepse në qoftë se unë dua të kërkoni për dikë emri i të cilit fillon me një, unë kontrolloni këtu. Por në qoftë se kjo nuk është një Studenti Unë jam duke kërkuar për, Unë lloj i duhet të fillojnë kontrollin kova, sepse ajo që kam bërë ishte lloj i linear hetim strukturën e të dhënave. Një mënyrë e trashë për të thënë vetëm shikoni për hapjen e parë në dispozicion, dhe të vënë si një plan B, kështu që të flasin, ose plan D në këtë rast, vlera e në atë vend në vend. Kjo është vetëm kështu që në qoftë se ju keni mori 26 vende dhe nuk ka studentë me Q emrin apo Z, ose diçka të tillë që, të paktën ju jeni duke përdorur hapësirë. 

Por ne kemi parë tashmë më shumë zgjidhje zgjuar këtu, apo jo? Çfarë do të bëni në vend në qoftë se ju keni një përplasje? Në qoftë se dy njerëz kanë emri i A, çfarë do kanë qenë të zgjuar ose më shumë zgjidhje intuitive se vetëm Duke vënë një ku D është menduar të jetë? Pse nuk mundem të shkojnë vetëm jashtë [? Annenberg?], si malloc, një tjetër nyje, e vënë atë këtu, dhe pastaj të vënë që një student këtu. Kështu që unë në thelb kam një lloj i një grup, ose ndoshta më shumë elegante si ne jemi duke filluar për të parë një listë e lidhur. 

Dhe kështu një tabelë hash është një strukturë që mund të duken vetëm si kjo, por më shumë cleverly, ju diçka që quhet chaining veçantë, ku një tabelë hash thjesht është një grup, secili prej Elementet cilës nuk është një numër, në vetvete është një listë e lidhur. Në mënyrë që ju të merrni qasje super të shpejtë të vendosë se ku të hash vlerën tuaj për të. Ashtu si me shembullin karta, Kam bërë vendime të super të shpejtë. Zemra shkon këtu, diamante shkon këtu. Same këtu, A shkon këtu, D shkon këtu, B shkon këtu. Pra, super të shpejtë look-ups, dhe në qoftë se ju ndodh që të kandidojë në një rast goditjet ku ju keni marrë, dy njerëz me të njëjtin emër, edhe atëherë ju vetëm të fillojnë të lidh ato së bashku. Dhe ndoshta ju mbani ato të renditura alfabetikisht, ndoshta ju nuk e bëni. Por të paktën tani kemi dinamizmin. Pra, në njërën anë kemi super të shpejtë kohë konstante, dhe lloj i kohës lineare i përfshirë në qoftë se këto lista të lidhura të fillojë të marrë një pak më të gjatë. 

Pra, ky lloj i një trashë, shaka vjet më geeky më parë. Në CS50 hack-a-thon, kur nxënësit kontrolloni në, disa TF ose CA çdo vit mendon se është qesharake për të vënë një shenjë si kjo, ku ai vetëm do të thotë në qoftë se emri juaj fillon me një A, shkojnë në këtë mënyrë. Në qoftë se emri juaj fillon me një B, shko this-- OK, kjo është qesharake ndoshta më vonë në semestër. Por ka një tjetër mënyrë për ta bërë këtë, too. Kthehuni në atë. 

Pra, nuk është kjo strukturë. Dhe kjo është e fundit ynë Struktura për sot, e cila është diçka që quhet një Trie. T-R-I-E, e cila për disa arsye është e shkurtër për rikthim, por ajo që quhet Trie. Pra, një Trie është një tjetër interesante amalgamë e një shumë prej këtyre ideve. Kjo është një pemë, që kemi parë më parë. Kjo nuk është një pemë binare e kërkimit. Kjo është një pemë me ndonjë numër të fëmijëve, por secili prej të fëmijëve në një Trie është një koleksion. Një grup i madhësisë, të themi, 26 ose ndoshta 27 në qoftë se ju doni të mbështetur emrat shkruar me vizë ose apostrofat në emrat e njerëzve. 

Dhe kështu kjo është një strukturë e të dhënave. Dhe në qoftë se ju shikoni nga lart deri në fund, si në qoftë se ju shikoni në nyjen e lartë atje, M, është duke treguar për gjë pari nga e majta atje, i cili është atëherë A, X, W, E, L, L. Kjo vetëm një strukturë të dhëna që në mënyrë arbitrare është ruajtjen emrat e njerëzve. Dhe Maxwell është ruajtur nga vetëm pas një rrugë e vektorit në grup në rrjet. Por ajo që është e mahnitshme rreth një Trie është se, ndërsa një listë të lidhura dhe madje një grup, më të mirë që kemi marrë ndonjëherë është Ora linear ose kohë logaritmike kërkim dikush lart. Në këtë strukturë të dhënave të një Trie, nëse Struktura e të dhënave im ka një emër në të dhe unë jam duke kërkuar për Maxwell, unë jam duke shkuar për të gjetur atë shumë shpejt. Unë vetëm shikoni për M-A-X-W-E-L-L. Nëse kjo strukturë të dhëna, nga ana tjetër, nëse N është një milion, në qoftë se ka një milion emra në këtë strukturë të të dhënave, Maxwell është ende do të jetë discoverable pas vetëm M-A-X-E-W-L-L hapa. Dhe David-- D-A-V-I-D hapa. Me fjalë të tjera, duke ndërtuar një strukturë e të dhënave që është mori të gjitha këto vargjeve, të cilat vetë mbështesin qasje të rastit, Unë mund të filloni të kërkoni deri të njerëzve emri duke përdorur një sasi të kohës që është proporcional me numrin jo i gjërave në strukturën e të dhënave, si një milion emra ekzistuese. Sasinë e kohës që duhet për mua për të gjetur M-A-X-E-W-L-L në këtë strukturë të dhënave është nuk proporcional me madhësia e strukturës së të dhënave, por gjatësia e emri. Dhe realisht emra ne jemi duke kërkuar deri kurrë nuk do të jetë i çmendur gjatë. Ndoshta dikush ka karakter 10 emri, 20 emër karakter. Është sigurisht fundme, e drejtë? Nuk është një njeri mbi tokë që ka emrin më të gjatë të jetë e mundur, por se emri është një konstante Gjatësia vlera, e drejtë? Ajo nuk ndryshon në asnjë kuptim. Pra, në këtë mënyrë, ne kemi arritur një strukturë të dhënave se është koha konstante look-up. Ajo ka marrë një numër hapash në varësi të gjatësisë së dhëna, por jo edhe numrin e emrit në strukturën e të dhënave. Pra, nëse ne dyfishojë numrin e emrave vitin e ardhshëm nga një miliard në dy miliardë, gjetje Maxwell do të marrë Numri i saktë të njëjtën e shtatë hapa për të gjetur atë. Dhe kështu që ne duket se kanë arritur Gral jonë e shenjtë për drejtimin e kohës. 

Pra, një çift i njoftimeve shpejtë. Quiz zero po afrohet. Më shumë se në faqen e internetit të kursit gjatë dy ditëve të ardhshme. Hënës lecture-- kjo është një festë këtu në Harvard të hënën. Kjo nuk është në New Haven, kështu që ne jemi duke marrë klasën për Haven re për leksion të hënën. Çdo gjë do të jetë filmuar dhe Transmetuar jetojnë si zakonisht, por le të përfundojë sot me një clip 30 dytë quajtur "Mendime thellë" nga Daven Farnham, e cila u frymëzua vitin e kaluar nga e shtuna "Mendimet e thellë" Night Live s nga Jack i dobishëm, i cili tani duhet të bëjë kuptim. 

FILM: Dhe tani, "Thellë Mendime "nga Daven Farnham. Tabelë Hash. 

SPEAKER 1: Në rregull, kjo është ajo tani për tani. Ne do të shihemi javën e ardhshme. 

DOUG: Për të parë atë në veprim. Pra, le të marrin një vështrim në atë të drejtë tani. Kështu që këtu, ne kemi një rrjet Unsorted. 

IAN: Doug, ju mund të shkoni përpara dhe restart kjo për vetëm një të dytë, ju lutem. Të gjithë të drejtë, kamerat janë kodrina, kështu veprim sa herë që ju jeni gati, Doug, OK? DOUG: Të gjithë të drejtë, kështu që ajo që ne kemi këtu është një koleksion Unsorted. Dhe unë e kam me ngjyrë të gjitha elementet kuqe për të treguar se ajo është, në fakt, Unsorted. Kështu kujtojnë se gjëja e parë që ne bëjmë është ne lloj gjysmën e majtë të vektorit. Pastaj ne lloj të drejtën gjysma e vektorit. Dhe ya-da, ya-da, ya-da, ne bashkojë ato së bashku. Dhe ne kemi një rrjet krejtësisht të renditura. Pra, kjo është se si të bashkohen lloj funksionon. 

IAN: Whoa, ee, ee, prerë, të prerë, të prerë, të prerë. Doug, ju nuk mund vetëm ya-da, ya-da, ya-da, në rrugën tuaj nëpërmjet merge lloj. 

DOUG: Unë vetëm e bëri. Kjo është në rregull. Ne jemi të mirë për të shkuar. Le të vetëm i mbajnë kodrina. Pra, gjithsesi, 

IAN: Ju keni për të shpjeguar atë më të plotë se kaq. Kjo nuk është vetëm e mjaftueshme. DOUG: Ian, ne nuk bëjmë duhet të kthehemi në një. Kjo është në rregull. Pra, gjithsesi, në qoftë se ne vazhdojmë me merge-- Ian, ne jemi në mes të xhirimeve. 

IAN: Unë e di. Dhe ne nuk mund vetëm ya-da, ya-da, ya-da, përmes procesit të tërë. Ju duhet të shpjegojë se si dy palët të bashkohen së bashku. 

DOUG: Por ne kemi tashmë shpjegoi se si dy sides-- 

IAN: Ju keni treguar vetëm ata një grup bashkojë. DOUG: Ata e dinë procesin. Ata janë në rregull. Ne kemi shkuar mbi të dhjetë herë. 

IAN: Ju vetëm skipped drejtë mbi të. Ne jemi duke shkuar prapa në një, ju nuk mund ti ya-da, da ya-mbi të. Të gjithë të drejtë, kthehet në një. 

DOUG: Më duhet të kthehem nëpër të gjitha slides? Perëndia im. Kjo është si herën e gjashtë, Ian. Kjo është në rregull. 

IAN: Në rregull. Jeni gati? I madh. Veprim.