[MUSIC Playing] DAVID J. Malan: Në rregull. Kjo është CS50. Kjo është javë pesë vazhdoi, dhe ne të ketë një lajm të mirë dhe një lajm i keq. Pra, një lajm i mirë është se CS50 nis të premten. Nëse ju do të donte të bashkohen me ne, shkojnë në URL e zakonshme këtu. Lajme edhe më të mirë, asnjë leksion kjo vjen e hënë 13. Pak më pak lajme më të mirë, quiz zero është të mërkurën e ardhshme. Më shumë detaje mund të jetë gjenden në këtë URL këtu. Dhe gjatë ditëve të ardhshme çift ne do të plotësojë vendet bosh në lidhje me dhomat se ne do të kemi të rezervuara. Lajm i mirë është se nuk do të të jetë një përmbledhje kurs të gjerë Sesioni kjo vjen Të hënën në mbrëmje. Stay tuned për kurs të Faqja e internetit për vendndodhjen dhe detaje. Seksione, edhe pse ajo është një pushime, do të takohet edhe si. Lajmi më i mirë, leksion të premten tjetër. Pra, kjo është një traditë që kanë, si për planin mësimor. Just-- ajo do të jetë e mahnitshme. Ju do të shihni gjëra të tilla si strukturat e të dhënave kohë konstante dhe tavolina hash dhe pemë dhe mundohet. Dhe ne do të flasim për problemet ditëlindjen. Një bandë e tërë e gjëra pret të premten tjetër. OK. Gjithsesi. Pra, kujtoj se ne kemi qenë duke u fokusuar në këtë foto të asaj që është brenda e kujtesës e kompjuterit tonë. Pra kujtesës ose RAM është ku programet ekzistojnë ndërkohë që jeni drejtimin e tyre. Nëse ju klikoni dy herë një ikonë për të drejtuar ndonjë program ose klikoni dy herë një icon për të hapur disa fotografi, është e ngarkuar nga hard juaj makinë apo makinë të ngurta shtet në RAM, Random Access Memory, ku ajo jeton deri sa pushteti shkon jashtë, kapak laptop mbyllet, ose ju lë programin. Tani se kujtesa, e të cilat ju ndoshta keni 1 Gigabyte këto ditë, 2 gigabajt, apo edhe shumë më tepër, është hedhur në përgjithësi nga për një program të caktuar në këtë lloj drejtkëndëshe Modeli konceptual ku ne kemi rafte në fund dhe një bandë e sende të tjera në krye. Gjë në krye ne kemi parë në këtë foto më parë, por kurrë nuk ka folur për është e ashtuquajtura segment tekst. Segment Tekst është vetëm një mënyrë e sofistikuar i thënë zero dhe ato që kompozoj programin tuaj aktual hartuar. Pra, kur ju klikoni dy herë Microsoft Word për Mac apo PC, ose kur ju drejtuar dot çaj Mario në një Kompjuter Linux në dritaren tuaj terminalit, zero dhe ato që përbëjnë Fjala apo Mario ruhen përkohësisht në RAM kompjuterit tuaj në të ashtuquajturin segment tekst për një program të veçantë. Më poshtë se shkon initialized dhe të dhënat uninitialized. Kjo është stuff like variablave globale, se ne nuk e kam përdorur shumë, por në disa raste ne kemi kishte variablave globale ose statike përcaktuar vargjet që është fjalë të tilla si "hello" vështirë koduar që nuk janë marrë në nga përdoruesit që janë të vështirë-koduar në programin tuaj. Tani, poshtë në pjesën e poshtme ne kanë të ashtuquajturin rafte. Dhe rafte, deri tani, ne kemi qenë duke përdorur për atë që llojet e qëllime? Çfarë është është përdorur rafte për? Po? Audienca: Funksionet. DAVID J. Malan: Për funksionet? Në atë kuptim për funksione? Audienca: Kur ju telefononi një funksion, Argumentet janë të kopjohen në rafte. DAVID J. Malan: Pikërisht. Kur ju telefononi një funksion, e saj Argumentet janë të kopjohen në rafte. Kështu që çdo X-së apo Y apo A apo B-së që ju jeni duke kaluar në një funksion janë vënë përkohësisht në ashtu-quajtur rafte, ashtu si një nga Annenberg tabaka sallë ngrënie, dhe gjithashtu gjërat si variabla lokale. Nëse funksioni juaj foo ose swap tuaj Funksioni kanë variablave lokale, si temp, ata të dy përfundojnë në rafte. Tani, ne nuk do të flasim shumë për ata, por këto mjedisit të ndryshueshëm në fund ne pamë një kohë më parë, kur Unë u futzing në tastierë një ditë dhe kam filluar qasjen gjëra si argv 100 ose argv 1000, vetëm elements-- harroj numbers-- por që nuk është dashur të arrihen nga mua. Ne kemi filluar duke parë disa simbolet shokuar në ekran. Ata ishin të ashtuquajturit mjedisit të ndryshueshëm si parametrat globale për tim program ose për kompjuterin tim, e jo pa lidhje të fundit bug që kemi diskutuar, Shellshock, që ka qenë rëndojnë mjaft disa kompjutera. Tani së fundi, në fokusin e sotme ne në fund të fundit do të jetë në grumbull. Ky është një tjetër copë e kujtesës. Dhe në thelb e gjithë kjo memorie është e njëjtë stuff. Është e njëjta hardware. Ne jemi vetëm lloj i trajtimin e grupimeve të ndryshme i bytes për qëllime të ndryshme. Tog është gjithashtu do të jetë aty ku Variablat dhe kujtesës që ju kërkojnë nga sistemi operativ është ruajtur përkohësisht. Por nuk është lloj i një problemi këtu, si foto nënkupton. Ne kemi dy lloj anije për të përplasen. Për shkak se si ju përdorni më shumë dhe më shumë i rafte, dhe si ne e shohim sot tutje, si ju përdorni më shumë dhe më shumë nga grumbull, me siguri gjëra të këqija mund të ndodhë. Dhe me të vërtetë, ne mund të shkaktoj që me qëllim apo pa qëllim. Pra, të cliffhanger fundit Ora ishte ky program, të cilat nuk i ke shërbyer çdo funksional Qëllimi tjetër se sa për të demonstruar se si ju si një djalë i keq në fakt mund të marrë Përparësia e mete në programin e dikujt dhe të marrë përsipër një program apo edhe një sistem i tërë kompjuter ose server. Pra, vetëm për shikim shkurtimisht, ju njoftim se kryesor në pjesën e poshtme merr në command line argumente, sipas argv. Dhe kjo ka një thirrje për një funksion f, në thelb një funksion të panjohur të quajtur f, dhe është duke kaluar në argv [1]. Pra, pavarësisht fjala lloje përdorues në në shpejtë pas emrit të këtij programit, dhe pastaj ky funksion arbitrare deri lartë, f, merr në një varg, AKA char *, si ne kemi filluar për të diskutuar, dhe vetëm ajo e quan atë "bar." Por ne mund ta quajmë atë gjë. Dhe atëherë ajo deklaron, brenda i f, një grup të karaktereve quajtur c-- 12 karaktere të tilla. Tani, nga histori unë u thënë një moment më parë, ku në kujtesë është c, apo janë ato 12 karaktere do të përfundojë? Vetëm të jetë i qartë. Po? Audienca: Në rafte. DAVID J. Malan: Në rafte. Pra, c është një variabël lokale. Ne jemi duke kërkuar për 12 karaktere ose 12 bytes. Ata do të përfundojë deri në të ashtu-quajtur rafte. Tani më në fund është ky funksion tjetër kjo është në fakt shumë e dobishme, por ne nuk e kam përdorur me të vërtetë ajo veten, strncopy. Kjo do të thotë kopje string, por vetëm n letra, karaktere n. Pra karaktere n do të jetë e kopjuar nga bar në c. Dhe sa? Gjatësia e bar. Pra, me fjalë të tjera, që një linjë, strncopy, do të kopje efektive bar në të c. Tani, vetëm për të lloj të parashikojnë Morali i kësaj historie, ajo është potencialisht problematike këtu? Edhe pse ne jemi duke kontrolluar gjatësinë e bar dhe duke kaluar atë në strncopy, çfarë është gut juaj thënë ju është ende thyer në lidhje me këtë program? Po? Audienca: A nuk përfshijnë vend për karakterin null. DAVID J. Malan: A nuk përfshijnë vend për karakterin null. Potencialisht, ndryshe nga në praktika e kaluar ne nuk bëjmë edhe kanë aq shumë si një plus 1 në strehojë këtë karakter null. Por kjo është edhe më keq se kaq. Çfarë tjetër jemi duke dështuar për të bërë? Po? Audienca: [padëgjueshme] DAVID J. Malan: Perfect. Ne e kemi koduar vështirë 12 goxha arbitrare. Kjo nuk është aq shumë problem, por fakti që ne nuk jemi edhe të kontrolluar nëse gjatësia e bar është më pak se 12, në të cilin rast ajo do të jetë e të sigurt për të vënë atë në kujtesën quajtur c se ne kemi ndarë. Në të vërtetë, në qoftë se bar është si 20 karaktere të gjatë, ky funksion duket të jetë kopjuar 20 karaktere nga bar në c, duke marrë të paktën 8 bajt se ajo nuk duhet të jetë. Kjo është implikimi këtu. Pra, në të shkurtër programin, thyer. Nuk është e tillë një punë e madhe. Ndoshta ju merrni një defekt segmentimit. Ne kemi të gjithë e kishin të mete në programet. Ne të gjithë mund të ketë mete në programet e drejtë tani. Por çfarë është implikimi? E pra, këtu është një version zoomed-në e se foto e kujtesë të kompjuterit tim. Kjo është në fund të rafte tim. Dhe me të vërtetë, në fund fare është ajo që është quajtur rafte prind rutinë, mënyrë e sofistikuar i thënë që është kryesore. Kështu që kushdo që quhet funksioni f që ne jemi duke folur rreth. Pra, kjo është në fund të rafte. Adresa e kthimit është diçka e re. Ka qenë gjithmonë atje, qenë gjithmonë në atë foto. Ne vetëm kurrë nuk tërhoqi vëmendjen për të. Për shkak se ajo rezulton mënyra c punon është se kur një funksion e quan një tjetër, jo vetëm që argumentet të cilat funksion të shtyrë mbi rafte, jo vetëm që lokal funksion të variabla të shtyrë mbi rafte, diçka që quhet një adresë e kthimit gjithashtu merr vënë mbi rafte. Në mënyrë të veçantë, nëse thirrjet kryesore foo, e kryesore Adresa e vet në kujtesën, kau diçka, në mënyrë efektive merr vënë mbi rafte kështu që kur f është bërë ekzekutimin e tij e di se ku të hidhen përsëri në në tekst segment në mënyrë që të vazhdojë ekzekutimin. Pra, nëse ne jemi këtu konceptualisht, në kryesore, atëherë f merr quajtur. Si e f di kush për kontrollin e dorës prapa? E pra, kjo pak Breadcrumb në të kuqe këtu, quajtur adresa e kthimit, ajo vetëm kontrolle, çfarë është që adresa e kthimit? Oh, më lejoni të hidhen përsëri në kryesore këtu. Dhe kjo është pak i një oversimplification, sepse e zero dhe ato për kryesore janë teknikisht deri këtu në segmentin e teknologjisë. Por kjo është ideja. f vetëm duhet të dini se çfarë për ku kontrolli në fund të fundit shkon prapa. Por mënyra kompjutera kanë hedhur gjatë gjëra si variabla lokale dhe Argumentet është si kjo. Pra, në krye të kësaj foto në blu është kornizë rafte për f, kështu që të gjithë e kujtesës që f në mënyrë specifike është duke përdorur. Pra në përputhje me rrethanat, vërejmë se bar është në këtë foto. Bar ishte argumenti i tij. Dhe ne pohoi se argumentet për Funksionet të shtyrë mbi rafte. Dhe c, sigurisht, është e edhe në këtë foto. Dhe vetëm për qëllime notational, njoftim në qoshe të lartë e majtë është se çfarë do të jetë c kllapa 0 dhe pastaj pak më poshtë në të djathtë është c kllapa 11. Pra, me fjalë të tjera, ju mund të imagjinoni se ka një rrjet prej bytes aty, parë e cila është të lartë të majtë, e poshtme e cila është i fundit i këtyre 12 bytes. Por tani të përpiqet të agjërojë përpara. Ajo që është gati të ndodhë në qoftë se ne të kalojë në një bar varg që është më shumë se c? Dhe ne nuk jemi duke kontrolluar nëse kjo është me të vërtetë më shumë se 12. Cila pjesë e kësaj tabloje do të marrë overwritten nga bajt 0, 1, 2, 3, dot dot dot, 11, dhe pastaj keq, 12, 13 deri 19? Çfarë do të ndodhë këtu, në qoftë se ju të konkludoj nga urdhërimin që c grupim 0 është në krye dhe c kllapa 11 është lloj i poshtë të drejtë? Po? Audienca: E pra, ajo do të prishësh char * bar. DAVID J. Malan: Po, ajo duket si ju jeni do të prishësh char * bar. Dhe më keq, në qoftë se ju dërgoni në një të vërtetë të gjatë string, ju mund të prishësh edhe ajo? Adresa e kthimit. Cili përsëri, është vetëm si një Breadcrumb për të të treguar programin ku për të shkuar përsëri në kur f është bërë duke u thirrur. Pra, çfarë liq në mënyrë tipike të bëjë është nëse ata vijnë të gjithë një program se ata janë kurioz se a është shfrytëzueshëm, buggy në mënyrë të tillë se ai ose ajo mund të marrë Avantazhi i kësaj bug, në përgjithësi ata nuk e marrin kjo e drejtë herë të parë. Ata vetëm të fillojë dërgimin e, për shembull, vargjet rastit në programin tuaj, nëse në tastierë, ose sinqerisht ata ndoshta shkruani një program të vogël për vetëm automatikisht gjenerojnë vargjet, dhe të fillojnë banging në programin tuaj duke dërguar në shumë inpute të ndryshme në gjatesite e ndryshme. Sa më shpejt që crashes tuaj të programit, kjo është një gjë e mahnitshme. Për shkak se kjo do të thotë se ai ose ajo ka zbuluar ajo është ndoshta me të vërtetë një bug. Dhe pastaj ata mund të merrni më të zgjuar dhe të fillojnë duke u fokusuar më të ngushtë se si për të shfrytëzuar këtë bug. Në veçanti, atë që ai ose ajo mund bëni është të dërgoni, në rastin më të mirë, përshëndetje. Nuk ka punë e madhe. Është një varg që është mjaft e shkurtër. Por, çka nëse ai ose ajo dërgon, dhe ne do të përgjithësojmë atë si, Sulmi code-- kështu zero dhe ato që bëjnë gjëra të si rm-RF, që hiqni çdo gjë nga hard drive ose të dërguar spam ose disi sulmojnë makinë? Pra, në qoftë se secili prej këtyre Letrat A vetëm përfaqëson, konceptualisht, sulm, sulm, sulm, sulm, disa kodi i keq që dikush tjetër ka shkruar, por nëse ai person është mjaft i zgjuar për të jo vetëm të përfshijë të gjithë prej atyre rm-rfs, por edhe kanë pak bytes tij ose të saj të fundit të jetë një numër që korrespondon në adresën e tij ose Kodi vet e saj sulm se ai ose ajo kaloi në vetëm duke siguruar atë me të shpejtë, ju në mënyrë efektive mund të gënjejnë kompjuterin në vërejtur kur f është bërë ekzekutimin, oh, është koha për mua që të hidhen përsëri në adresën e kuqe e kthimit. Por për shkak se ai ose ajo ka disi përkime atë adresë e kthimit me numrin e tyre, dhe ata janë mjaft të zgjuar që kanë konfiguruar që numër për të referuar, si ju shihni në super krye qoshe majtë atje, adresa aktuale në kompjuter-së kujtimi i disa prej kodin e tyre sulmit, një djalë i keq mund të gënjejnë kompjuterin në ekzekutimin kodin e tij ose të saj. Dhe që kodi, përsëri, mund të jetë çdo gjë. Është quajtur përgjithësisht kodi predhë, e cila është vetëm një mënyrë për të thënë se kjo nuk është përgjithësisht diçka e thjeshtë si rm-RF. Është në fakt diçka si Bash, apo një program i vërtetë që i jep atij ose kontrollin e saj programatike për të ekzekutuar çdo gjë tjetër që ata duan të. Pra me pak fjalë, këtë të gjithë buron nga fakti i thjeshtë se ky bug përfshirë jo kontrolluar kufijtë e array tuaj. Dhe për shkak të rrugës kompjutera puna është se ata përdorin rafte nga mënyrë efektive, konceptualisht, fund më lart, por pastaj elementet ju shtyjnë mbi rafte të rritet lartë poshtë, kjo është tepër problematike. Tani, ka mënyra për të punuar rreth kësaj. Dhe sinqerisht, ka gjuhë me të cilën për të punuar rreth kësaj. Java është imun, për shembull, për këtë çështje të veçantë. Për shkak se ata nuk ju japin pointers. Ata nuk ju japin Adresat direkte kujtesës. Pra, me këtë fuqi që kemi për të prekur asgjë në kujtesë duam të vijë, pa dyshim, rrezik i madh. Kështu që të mbajë një sy jashtë. Nëse, sinqerisht, në muajt apo vitet që vijnë, në çdo kohë ju lexuar në lidhje me disa shfrytëzimit e një programi ose një server, nëse ju shihni ndonjëherë një aluzion e diçka si një sulm tampon del nga shtrati, ose rafte del nga shtrati është një lloj tjetër i sulmit, të ngjashme në frymë, më shumë të frymëzon website-së emrin, në qoftë se ju e dini atë, kjo është e gjitha duke folur për vetëm tejmbushur madhësinë e një karakter grup ose disa array në përgjithësi. Çfarëdo pyetjeje, atëherë, në këtë? Mos provoni këtë në shtëpi. Të gjithë të drejtë. Deri malloc deri më tani ka qenë e tonë të re mik në të cilat ne mund të siguroj kujtesë se ne nuk e dimë me domosdo në të avancuar se ne duam kështu që ne nuk kemi të kodit të vështirë në tonë Numrat program si 12. Pasi përdoruesi na tregon se sa shumë të dhënat që ai apo ajo dëshiron të dhëna, ne mund të malloc atë shumë memorie. Pra malloc ajo rezulton, që të mase ne kemi qenë duke e përdorur atë, në mënyrë të qartë për herë të fundit, dhe pastaj ju djema janë duke e përdorur atë për getstring unknowingly për disa javë, të gjitha të kujtesës malloc-së vjen nga i ashtuquajturi grumbull. Dhe kjo është arsyeja pse getstring, për shembull, mund të kujtesës dinamike pa e ditur se çfarë ju jeni të do të shkruani më parë, ju dorëzojnë një tregues për atë kujtim, dhe se kujtesa është ende e juaja për të mbajtur, edhe pas getstring kthimit. Sepse kujtojnë pas të gjitha që rafte është vazhdimisht duke shkuar lart e poshtë, lart e poshtë. Dhe, sa më shpejt që ajo shkon poshtë, që do të thotë asnjë kujtim këtë funksion e përdorur duhet nuk do të përdoret nga dikush tjetër. Është vlerat mbeturinash tani. Por tog është këtu. Dhe çfarë është e mirë për malloc është se kur malloc ndan memorie deri këtu, nuk është ndikuar, për Pjesa më, nga rafte. Dhe kështu çdo funksion mund të hyni kujtesës që është malloc'd, edhe nga një funksion si getstring, edhe pasi ajo është kthyer. Tani, bisedoj e malloc është falas. Dhe me të vërtetë, rregull ju duhet të fillojë miratimin është çdo, çdo, çdo herë që ju përdorni malloc ju duhet të përdorni të lirë veten, përfundimisht, në të njëjtën akrep. E gjithë kjo kohë ne kemi qenë të shkruar buggy, kodin buggy, për shumë arsye. Por një nga të cilat ka qenë e përdorur bibliotekën CS50, e cila vetvete është qëllimisht buggy, ajo rrjedhjet e kujtesës. Çdo herë që e kam quajtur getstring gjatë disa javëve të fundit ne jemi duke i kërkuar operative sistem, Linux, për kujtesën. Dhe ju kurrë nuk kanë dhënë një herë atë. Dhe kjo nuk është, në praktikë, një gjë e mirë. Dhe Valgrind, një nga mjete futur në Pset 4, është e gjitha për të ndihmuar ju tani gjeni mete si kjo. Por, fatmirësisht për Pset 4 ju nuk keni nevojë për të përdorur bibliotekën CS50 ose getstring. Kështu që çdo të mete që lidhen me kujtesën janë në fund të fundit do të jenë tuajat. Pra malloc është më shumë se vetëm i përshtatshëm për këtë qëllim. Ne mund të vërtetë tani zgjidhin probleme krejtësisht të ndryshme, dhe krejtësisht të zgjidhur problemet më të në mënyrë efektive si për premtimin javë zero-së. Deri tani kjo është sexiest Struktura e të dhënave ne kemi pasur. Dhe nga struktura e të dhënave unë vetëm do të thotë një mënyrë e konceptualizimit kujtesës në një mënyrë që shkon përtej vetëm duke thënë, kjo është një int, kjo është një char. Ne mund të fillojë të gjëra grumbull së bashku. Pra, një grup dukej si kjo. Dhe çfarë ishte kyç në lidhje me një array është se ajo ju jep back-to-back chunks e memorie, secila prej të cilave do të jetë e të njëjtit lloj, int, int, int, int, ose char, char, char, char. Por ka disa dobësi. Kjo për shembull, është një grup të madhësisë së gjashtë. Supozoni se ju plotësoni këtë grup me gjashtë numra dhe pastaj, për çfarëdo arsye, Përdorues juaj dëshiron të japë ju një numër shtatë. Ku e keni vënë atë? Çfarë është zgjidhja, nëse ju keni krijuar një rrjet në rafte, për shembull, vetëm me të javës dy simbol që ne kemi prezantuar, i kllapa katrore me një numër brenda? E pra, ju keni marrë gjashtë Numrat në këto kuti. Çfarë do të jetë instinktet tuaja? Ku do të doni të vënë atë? Audienca: [padëgjueshme] DAVID J. Malan: Na vjen keq? Audienca: Vendoseni atë në fund. DAVID J. Malan: Vendoseni atë në fund. Pra, vetëm mbi të drejtën, jashtë këtij kuti. Cili do të ishte mirë, por ajo rezulton nga ju nuk mund ta bëjë këtë. Sepse në qoftë se ju nuk e keni kërkuar për këtë copë e kujtesës, ajo mund të jetë rastësisht se ky është duke u përdorur nga disa variabla të tjerë krejt. Mendoni përsëri një javë apo më shumë kur kemi hedhur nga emrat Zamyla dhe Davin dhe Gabe-së në kujtesën. Ata ishin fjalë për fjalë të kthyer prapa në shpinë. Pra, ne nuk mund domosdoshmërisht besojnë se çdo gjë-së këtu është në dispozicion për mua që të përdorni. Pra, çfarë tjetër mund të bëni? E pra, një herë e kuptuar ju nevojë për një rrjet të madhësisë shtatë, ju mund të krijojë vetëm një grup të madhësisë shtatë atëherë përdorni një për lak ose një lak, ndërsa, kopje atë në grup të ri, dhe pastaj disi vetëm të shpëtoj prej ky grup ose vetëm të ndaluar duke e përdorur atë. Por kjo nuk është veçanërisht e efektshme. Me pak fjalë, vargjeve nuk e le ju dinamike resize. Pra, në njërën anë ju merrni e gjallë, e cila është e mahnitshme. Për shkak se ajo na lejon të bëjmë gjëra të si përça dhe sundo, kërko binar, të cilat ne kemi biseduar rreth në ekran këtu. Por ju përshkruaj veten në një qoshe. Sa më shpejt që ju goditi fundi i array tuaj, ju duhet të bëni një shumë të operacion të shtrenjtë ose shkruaj një bandë e tërë e kodit për tani merren me këtë problem. Pra, çfarë nëse në vend të kësaj ne kishim diçka që quhet një listë, ose një listë e lidhur në mënyrë të veçantë? Çka nëse në vend që rectangles të kthyer prapa për të mbështetur, ne kemi rectangles që lënë pak bit e dhoma luaj në mes tyre? Dhe, edhe pse unë e kam tërhequr këtë foto apo përshtatur këtë foto nga një prej teksteve këtu për të kthehet në të kthyer prapa shumë të rregullt, në të vërtetë, një nga ato rectangles mund të jetë deri këtu në kujtesë. Një prej tyre mund të jetë deri këtu. Një prej tyre mund të jetë deri këtu, mbi këtu, dhe kështu me radhë. Por, çfarë nëse ne tërhoqi, në këtë rast, shigjeta që në njëfarë mënyre lidhjen e këtyre rectangles së bashku? Në të vërtetë, ne kemi parë një teknik mishërimi i një shigjetë. Çfarë kemi përdorur në të fundit ditë që, nën kapuç, është përfaqësues i një shigjetë? Një akrep, e drejtë? Pra, çfarë nëse, në vend të vetëm ruajtjen numrat, si 9, 17, 22, 26, 34, çfarë nëse ne nuk ruhen vetëm një numër, por një akrep pranë çdo numër të tillë? Kështu që shumë si ju do të thread një gjilpërë përmes një bandë e tërë e rrobave, gjërat disi i lidhur së bashku, në mënyrë të ngjashme mund të ne me pointers, si misheruar nga shigjeta këtu, lloj endje së bashku këto rectangles individuale duke në mënyrë efektive duke përdorur një tregues pranë çdo numër që vë në një numër tjetër, që thekson, nga ana tjetër, disa numri i ardhshëm? Pra, me fjalë të tjera, ajo që në qoftë se ne të vërtetë të kërkuar për të zbatuar diçka si kjo? E pra për fat të keq, këto rectangles, Të paktën një me 9, 17, 22, dhe kështu me radhë, këto nuk janë më të Sheshet e bukur me numra të vetme. Fund, drejtkëndësh më poshtë 9, për shembull, përfaqëson atë që duhet të jetë një tregues, 32 bit. Tani, unë nuk jam ende në dijeni të ndonjë lloji të dhënave në C që ju jep jo vetëm një int por një akrep krejt. Pra, çfarë është zgjidhje nëse duam të shpikë përgjigjen tonë ndaj kësaj? Po? Audienca: [padëgjueshme] DAVID J. Malan: Çfarë është ajo? Audienca: Struktura e re. DAVID J. Malan: Yeah, kështu që pse të nuk kemi krijuar një strukturë të re, ose në C, strukturë? Ne e kemi parë structs më parë, në qoftë se një kohë të shkurtër, ku kemi marrë me një strukturë të studentëve si ky, i cili kishte një emër dhe një shtëpi. Në Pset 3 Breakout keni përdorur një e tërë bandë e GRect structs-- dhe GOvals që Stanford krijuar për të Informacioni grumbull së bashku. Pra, çfarë nëse kemi marrë këtë ide të njëjtë të fjalë kyçe "typedef" dhe "struct," dhe pastaj disa sende nxënës specifike, dhe ky zhvillohet në vijim: typedef struct node-- dhe nyje është vetëm një shkencë shumë e përgjithshme kompjuterike Termi për diçka në një strukturë të të dhënave, një enë në një strukturë të dhënave. Një nyjë Unë pretendojnë do të ketë një n int, tërësisht i hapur, dhe pastaj pak më shumë cryptically, kjo linjë e dytë, nyje struct * tjetër. Por, në terma më pak teknike, çfarë është kjo linjë e dytë e kodit brenda formatimin e teksteve kaçurrel? Po? Audienca: [padëgjueshme] DAVID J. Malan: Një tregues për një tjetër nyje. Pra pa dyshim, sintaksës pak i fshehtë. Por në qoftë se ju lexoni atë fjalë për fjalë, tjetër është emri i një ndryshore. Cili është lloji i saj të dhënat? Kjo është një fjalëshumë pak këtë herë, por kjo është e tipit struct nyje *. Çdo herë që ne kemi parë diçka yll, që do të thotë se është një tregues për atë lloj të të dhënave. Pra, tjetër është me sa duket një tregues për një nyje struct. Tani, ajo që është një nyje struct? E pra, vini re e shihni ato njëjtat fjalë në krye të drejtë. Dhe me të vërtetë, ju të shihni fjalën "Nyje" këtu poshtë në pjesën e poshtme të majtë. Dhe kjo është në fakt vetëm një lehtësi. Vini re se në përkufizimin tonë të studentëve ka fjala "studenti" vetëm një herë. Dhe kjo është për shkak se një student objekti nuk ishte vetë-referues. Nuk ka asgjë në brendësi të një studenti që ka nevojë për pikë në një tjetër student, persay. Kjo do të jetë lloj i pazakontë në botën e vërtetë. Por, me një nyje në një lidhje lista, ne duam një nyje të jetë referues në një objekt të ngjashme. Dhe kështu njoftim ndryshimi këtu nuk është vetëm atë që është brenda formatimin e teksteve kaçurrel. Por ne e shtuar fjalën "nyje" në majë si dhe duke shtuar atë të poshtme në vend të "studenti". Dhe kjo është vetëm një detaj teknik kështu që, përsëri, strukturë e të dhënave tuaja mund të jenë të vetë-referues, në mënyrë që një nyje mund të tregojnë për një tjetër nyje të tillë. Pra, çfarë është kjo në fund të fundit do të thotë për ne? E pra, e, kjo stuff brenda është përmbajtja e nyje tonë. Kjo gjë deri këtu, e drejtë të lartë, është vetëm aq që, përsëri, ne mund të referohen veten. Dhe pastaj sende outermost, edhe pse nyje është një term i ri, ndoshta, është ende njëjtë si nxënës dhe çfarë ishte nën kapuç në SPL. Pra, nëse ne tani kërkuar për të filluar zbatimin e kësaj liste të lidhur, se si mund që ne të përkthehet diçka si kjo për kodin? E pra, le të shohim vetëm një shembull i një programi që në fakt përdor një listë e lidhur. Ndër kodin e sotme të shpërndarjes është një program i quajtur Lista Zero. Dhe në qoftë se unë të drejtuar këtë unë krijuar një super GUI e thjeshtë, Graphical User Interface, por është e vërtetë vetëm printf. Dhe tani unë kam dhënë vetes një menu pak options-- Fshij, Insert, Search, dhe kundërvënie. Dhe Quit. Këto janë vetëm operacionet e përbashkëta në një Struktura e të dhënave e njohur si një listë link. Tani, Fshij do të të fshirë një numër nga lista. Fut do të shtojë një numër në listë. Kërkimi do të shikojmë për numrin në listë. Dhe Kundërvënie është vetëm një mënyrë e sofistikuar për të thënë, të ecin nëpër lista, print it out, por kjo është ajo. Mos e ndryshoni atë në asnjë mënyrë. Pra, le të provoni këtë. Le të shkojnë përpara dhe të tipit 2. Dhe atëherë unë jam duke shkuar për të futur numrin, thonë 9. Shkruani. Dhe tani programi im është vetëm programuar për të thënë, lista është tani 9. Tani, kur të shkoj përpara dhe të e Fut përsëri, le shkoj përpara dhe zoom jashtë dhe shkruani në 17. Tani lista ime është 9, pastaj 17. Nëse unë bëj futur përsëri, le të kaloni një të tillë. Në vend të 22, si për foto ne kemi qenë në kërkim në këtu, më lejoni të kërcejnë përpara dhe futur 26 të ardhshëm. Kështu që unë jam duke shkuar për të tipit 26. Lista është si unë pres. Por tani, vetëm për të parë nëse këtë kod do të jetë fleksibël, më lejoni tani type 22, e cila të paktën konceptualisht, në qoftë se ne jemi mbajtur këtë renditura, e cila është me të vërtetë do të jetë një tjetër objektiv të drejtë tani, duhet të shkojnë në mes të 17 dhe 26. Kështu që unë hit Enter. Në të vërtetë, që punon. Dhe kështu që tani më lejoni të futur fundit, per foto, 34. Të gjithë të drejtë. Kështu që tani për tani më lejoni të përcaktojnë se Delete dhe kundërvënie dhe Kërkimi bëjë, në fakt, të punuar. Në fakt, në qoftë se unë do të kandidojë Kërko, le të kërkoni për numrin 22, Enter. Ajo gjeti 22. Pra, kjo është ajo që kjo Programi Lista Zero bën. Por çfarë është në të vërtetë ndodh në që zbaton kjo? E pra, së pari unë mund të ketë, dhe në të vërtetë Unë kam një skedar të quajtur list0.h. Dhe diku në atje është ky line, typedef, nyje struct, atëherë unë kam formatimin e teksteve e mia kaçurrel, int n, dhe pastaj struct-- çfarë ishte përkufizimi? Nyje struct tjetër. Pra, ne kemi nevojë për yllin. Tani teknikisht të marrim në zakon i tërhequr këtu. Ju mund të shihni tekstet dhe Referencat ne linje bëjë atë atje. Është funksionalisht ekuivalente. Në fakt, kjo është pak më tipike. Por unë do të jetë në përputhje me atë që ne e bëmë për herë të fundit dhe të bëjë këtë. Dhe pastaj së fundi, unë jam duke shkuar për të bërë këtë. Pra, në një header fotografi diku, në list0.h sot është ky përkufizim struct, dhe ndoshta disa sende të tjera. Ndërkohë në list0c ka do të jetë disa gjëra. Por ne jemi duke shkuar për të vetëm fillojnë dhe nuk mbarojnë këtë. List0.h është një fotografi që unë dua të përfshijë në dosjen time C. Dhe pastaj në një pikë unë jam do të ketë int, kryesor, të pavlefshme. Dhe atëherë unë jam duke shkuar për të kanë disa për-bërë është këtu. Unë jam gjithashtu do të ketë një prototip, si pavlefshëm, kërkimi, int, n, qëllimi i të cilit në jetë është për të kërkuar për një element. Dhe pastaj këtu kam të drejtë në Kodi i sotëm, i pavlefshëm, kërko, int, n, asnjë presje por formatimin e teksteve të hapur kaçurrel. Dhe tani unë dua të disi të kërkuar për një element në këtë listë. Por ne nuk kemi mjaft Informacioni në ekran ende. Unë nuk e kanë në të vërtetë përfaqësuar listë vetë. Pra, një mënyrë që ne mund të zbatojë një listë të lidhura në një program po unë lloj i duan të bëjnë diçka si deklarojë lidhur listën deri këtu. Për thjeshtësi, unë jam duke shkuar për të bërë ky globale, edhe pse në ne përgjithshme nuk duhet ta bëjë këtë shumë. Por kjo do të thjeshtojë këtë shembull. Kështu që unë dua të deklaroj një listë të lidhura deri këtu. Tani, se si mund të bëj se? Ja foto e një listë të lidhura. Dhe unë nuk e bëj të vërtetë e di se në këtë moment se si Unë jam duke shkuar për të shkuar në lidhje me përfaqësimin e kaq shumë gjëra me vetëm një ndryshueshme në kujtesën. Por mendoj se përsëri një moment. E gjithë kjo kohë ne kemi pasur vargjet, të cilat ne pastaj shpallur të jetë vargjeve të karaktere, të cilat ne pastaj zbuluar të jetë vetëm një akrep të karakterit të parë në një grup të karaktereve që është ndërprerë null. Pra, nga kjo logjikë, dhe me këtë lloj foto e mbjellëse mendimet tuaja, çfarë duhet ne fakt shkruani në tonë Kodi për të përfaqësuar një listë e lidhur? Sa i këtij informacioni nuk kemi nevojë për të kapur në kodin e C, do të thoni? Po? Audienca: Ne kemi nevojë për një tregues për një nyje. DAVID J. Malan: Një tregues për një nyje. Në mënyrë të veçantë, e cila do nyje tuaj Instinktet jetë për të mbajtur një tregues për të? Audienca: nyja e parë. DAVID J. Malan: Po, ndoshta vetëm i pari. Dhe vini re, i pari Nyja është një formë të ndryshme. Është vetëm gjysma e madhësisë së struct, sepse kjo është në të vërtetë vetëm një akrep. Pra, çfarë ju mund të vërtetë të bëni është të deklarojë një listë të lidhura të jenë të tipit nyje *. Dhe le të vetëm e quajti atë më parë dhe nisja atë të null. Pra null, përsëri, është duke ardhur në foto këtu. Jo vetëm që është përdorur null si si një të veçantë Vlera e kthyer për gjëra të tilla si getstring dhe malloc, null është gjithashtu zero akrep, mungesa e një akrep, nëse ju do. Ajo thjesht do të thotë asgjë nuk është ende këtu. Tani së pari, unë mund të kemi e quajti këtë gjë. Unë mund të ketë e quajti atë "lista" ose ndonjë numër të gjëra të tjera. Por unë jam duke e quajtur atë "e parë" në mënyrë që Linjat atë me këtë foto. Pra, ashtu si një varg mund të përfaqësohen me adresën e bajt saj të parë, kështu që mund një listë e lidhur. Dhe ne do të shohim të dhëna të tjera struktura të përfaqësohet me vetëm një akrep, një shigjetë 32-bit, duke treguar në nyjen e parë në strukturën. Por tani le të presin një problem. Nëse unë jam vetëm duke kujtuar në programin tim të adresave i nyjës së parë, i pari drejtkëndësh në këtë strukturë të të dhënave, ajo që më mirë e kishte të jetë rasti për Zbatimi i pjesës tjetër të listës sime? Çfarë është një detaj i rëndësishëm që do për të siguruar këtë të vërtetë punon? Dhe nga "të vërtetë punon" Unë do të thotë, shumë si një varg, na lejon të shkojnë nga karakteri i parë në emër Davin ndaj të dytë, të tretë, për të katërt, deri në fund, si mund ta dimë kur jemi në fund nga një listë e lidhur që duket si kjo? Kur është null. Dhe unë e kam përfaqësuar këtë lloj të si si një fuqinë inxhinier elektrik, me argumentim pak simbol, në terezi. Por kjo vetëm do të thotë null në këtë rast. Ju mund të tërheqë atë çdo numër mënyra, por ky autor ndodhur për të përdorur këtë simbol këtu. Për sa kohë që ne jemi stringing të gjitha këto nyje bashku, vetëm duke kujtuar se ku e para është, aq e gjatë si ne kemi vënë një simbol të veçantë në nyje shumë të fundit në listë, dhe ne do të përdorim null, sepse kjo është atë që kemi në dispozicion për ne, kjo listë është e plotë. Dhe edhe në qoftë se unë vetëm të ju jap një tregues për elementi i parë, ju, programues, me siguri mund të hyni në pjesën tjetër të saj. Por le të le mendjen tuaj bredhin pak, në qoftë se ata nuk janë tashmë të mjaft wandered-- çfarë është do të jetë hera e drejtimin e gjetur ndonjë gjë në këtë listë? Damn ajo, kjo është O e madhe e n, i cili nuk është i keq, ne paanësisë. Por është linear. Ne kemi hequr dorë atë tipar i vargjeve duke lëvizur më shumë drejt këtë foto e dinamik endura së bashku apo nyje të lidhura? Ne kemi hequr dorë qasje të rastit. Një grup është e mirë për shkak se gjithçka matematikisht është kthyer prapa për të kthyer prapa. Edhe pse këtë foto duket goxha, dhe madje edhe edhe pse kjo duket si këto nyje janë Spaced bukur larg, në realitet ata mund të jenë kudo. OX1, Ox50, Ox123, Ox99, këto nyje mund të jetë kudo. Sepse malloc bën kujtesës nga plehrat, por kudo në grumbull. Ju nuk domosdoshmërisht e di se është e do të jetë për të kthyer prapa në shpinë. Dhe kështu kjo foto në realitet të nuk do të jetë mjaft e kjo goxha. Pra, ajo do të marrë një grimë e punojnë për të zbatuar këtë funksion. Pra, le të zbatojë kërkim tani. Dhe ne do të shohim lloj a mënyrë e zgjuar për të bërë këtë. Pra, nëse unë jam një funksion kërko dhe Unë jam duke dhënë një ndryshueshme, numër i plotë n për të kërkuar, unë duhet të dini Sintaksa e re për kërkim brenda e një strukture që është vuri në dukje, për të gjetur n. Pra, le ta bëjmë këtë. Pra, së pari unë jam duke shkuar për të shkuar përpara dhe të deklarojë një nyje *. Dhe unë jam duke shkuar për të thirrur atë akrep, vetëm nga konventa. Dhe unë jam duke shkuar për të nisja atë të parë. Dhe tani unë mund ta bëjë këtë në një numër mënyrash. Por unë jam duke shkuar për të marrë një qasje të përbashkët. Ndërsa akrep nuk është e barabartë me null, dhe kjo është sintaksë e vlefshme. Dhe ai thjesht do të thotë të bëjë të mëposhtme, në mënyrë kohë sa ju nuk jeni duke treguar asgjë. Çfarë doni të bëni? Nëse akrep dot n, më lejoni të kthehem për të që, equals-- barabartë çfarë? Çfarë vlera jam duke kërkuar për? N aktuale që u miratua në. Kështu që këtu është një tjetër tipar i C dhe shumë gjuhë. Edhe pse struktura të quajtur nyja ka një n vlerën, krejtësisht legjitime të kemi gjithashtu një argument lokale ose të ndryshueshme quajtur n. Sepse edhe ne, me sytë e njeriut, mund të dallojë se ky n është me sa duket ndryshëm nga kjo n. Për shkak se sintaksa është e ndryshme. Ju keni marrë një pikë dhe një tregues, ndërsa ky nuk ka gjë të tillë. Pra, kjo është në rregull. Kjo është në rregull për të thirrur ata të njëjtat gjëra. Nëse unë do ti gjeni këtë, unë jam i do të duan të bëjnë diçka si të njoftuar se ne kemi gjetur n. Dhe ne do të iki se si një komentoni ose kod pseudokod. Tjetër, dhe këtu është Pjesa interesante, çfarë bëj që unë dua të bëj në qoftë se nyja e tanishme nuk përmban n që unë intereson? Si mund të arrihet në vijim? Nëse gishtin tim në moment është PTR, dhe kjo është duke treguar në çfarëdo parë është vënë në, si mund të lëvizë gishtin tim për nyjen e ardhshëm në kod? E pra, çfarë është Breadcrumb ne jemi duke shkuar për të ndjekur në këtë rast? Audienca: [padëgjueshme]. DAVID J. Malan: Po, kështu e ardhshme. Pra, nëse unë kthehem në tim Kodi këtu, në të vërtetë, unë jam do të shkojnë përpara dhe të thonë treguesin, i cili është vetëm një variable-- përkohshme është një emër të çuditshëm, ptr, por kjo është vetëm si temp-- Unë jam duke shkuar për të vendosur treguesin barabartë me çfarëdo is-- akrep dhe përsëri, kjo do të jetë një pak buggy për një pikë moment-- ardhshëm. Me fjalë të tjera, unë jam duke shkuar për të marrë tim Gishti që është duke treguar në këtë nyje këtu dhe unë jam duke shkuar për të thënë, ju e dini atë, të marrë një sy në fushën e ardhshme dhe lëvizin gishtin tuaj për të çfarëdo qoftë ajo është duke treguar. Dhe kjo do të përsëritur, të përsëritur, të përsëritur. Por kur bën gishtin tim ndaluar duke bërë asgjë në të gjitha? Sa më shpejt që ajo linjë e kodit në shkelma? Audienca: [padëgjueshme] DAVID J. Malan: Nëse pikë ndërsa tregues nuk është e barabartë me null. Në një moment gisht My do të jetë duke treguar null dhe unë jam duke shkuar për të realizuar që është fundi i kësaj liste. Tani, kjo është pak gënjeshtër e bardhë për thjeshtësi. Ajo rezulton se edhe pse ne vetëm mësuar këtë dot simbol për strukturat, akrep nuk është një struct. ptr është ajo? Vetëm të jenë më nitpicky. Është një tregues për një nyje. Kjo nuk është një nyje në vetvete. Nëse unë nuk kishte asnjë yll këtu, akrep absolutely-- kjo është një nyje. Kjo është si një javë Deklarata e një ndryshore, edhe pse fjala "nyja" është e re. Por sa më shpejt që ne të futur një yll, kjo është tani një tregues për një nyje. Dhe për fat të keq ju nuk mund të përdorni dot simbol për një akrep. Ju duhet të përdorni arrow simbol, i cili, habitshme, është hera e parë çdo pjesë i sintaksës duket intuitive. Kjo fjalë për fjalë duket si një shigjetë. Dhe kështu kjo është një gjë e mirë. Dhe këtu fjalë për fjalë duket si një shigjetë. Kështu që unë mendoj se është la-- unë nuk bëj mendoni se unë jam mbi-kryerjen here-- I mendoj se kjo është pjesa e fundit e re i sintaksës ne jemi duke shkuar për të parë. Dhe fatmirësisht, është e vërtetë pak më shumë intuitiv. Tani, për ato prej jush që mund të preferojnë rrugën e vjetër, ju ende mund të përdorni dot simbol. Por si për sesionin e së hënës bisedë, kemi parë nevojë për të shkuar atje, shkoni në se adresuar, dhe pastaj të hyrë në fushë. Pra, kjo është edhe e saktë. Dhe sinqerisht, ky është një pak më shumë pedant. Ju jeni fjalë për fjalë duke thënë, dereference tregues dhe shkoni atje. Pastaj kap .n, fushë e quajtur n. Por sinqerisht, askush nuk dëshiron të shkruani apo lexoni këtë. Dhe kështu bota shpikur simbol shigjeta, të cilat është ekuivalent, identike, kjo është vetëm sheqeri sintaktik. Pra, një mënyrë e sofistikuar për të thënë këtë duket më mirë, ose të duket e thjeshtë. Deri tani unë jam duke shkuar për të bërë një gjë tjetër. Unë jam duke shkuar për të thënë "pushim" edhe unë kam gjetur atë kështu që unë nuk e mbaj në kërkim për të. Por kjo është esencë e një funksion kërkimi. Por kjo është një shumë më e lehtë, në fund, për të mos ecin nëpër kodit. Kjo është me të vërtetë zbatimi formal e kërkimit në kodin e sotme të shpërndarjes. Unë guxoj të them se nuk është futur veçanërisht e bukur për të ecur nëpër me sy, as nuk është fshirë, madje edhe megjithëse në fund të ditës ata avulloj në mënyrë të drejtë heuristics thjeshtë. Pra, le ta bëjmë këtë. Nëse ju do humor këtu, kam bërë të sjellë një bandë e topa stresit. I sollën një bandë të numrave. Dhe mund të marrim vetëm disa vullnetarë të përfaqësojë 9, 17, 20, 22, 29, dhe 34? Pra, në thelb të gjithë që është sot këtu. Kjo ishte një, dy, tre, katër, pesë, gjashtë njerëz. Dhe unë kam qenë i kërkuar për të go-- të parë, nuk ka një në pjesën e pasme ngre duart e tyre. OK, një, dy, tre, katër, five-- lejoni të ngarkesës balance-- gjashtë. OK, ju gjashtë vijnë më lart. Ne do të duhet njerëzit e tjerë. Ne sjellë topa stresit shtesë. Dhe në qoftë se ju mund të, për vetëm një moment, linjë veten deri vetëm si kjo foto këtu. Të gjithë të drejtë. Le të shohim, si e ke emrin? Audienca: Andrew. DAVID J. Malan: Andrew, ju jeni numër 9. Gëzohem që u njohëm. Këtu ju shkoni. Audienca: Jen. DAVID J. Malan: Jen. David. Numri 17. Po? Audienca: Jam Julia. DAVID J. Malan: Julia, David. Numri 20. Audienca: krishterë. DAVID J. Malan: krishterë, David. Numri 22. Dhe? Audienca: JP. DAVID J. Malan: JP. Numri 29. Kështu që të shkojnë përpara dhe për të marrë in-- Uh oh. Uh oh. Koha e pritjes. 20. A ka dikush një shënues? Audienca: Unë kam marrë një sharpie. DAVID J. Malan: Ju mori një sharpie? OK. Dhe ka njeri të ketë një copë letër? Ruaj leksion. Hajde. Audienca: Ne kemi marrë atë. DAVID J. Malan: Ne e mori atë? Në rregull, ju faleminderit. Këtu ne do të shkojmë. A ishte kjo nga ju? Ju vetëm ruajtur ditë. Pra 29. Të gjithë të drejtë. Unë misspelled 29, por OK. Shkoni përpara. Në rregull, unë do të ju jap stilolaps tuaj mbrapa çast. Pra, ne kemi këto folks këtu. Le të ketë një tjetër. Gabe, nuk ju duan të luajnë elementi i parë këtu? Ne do të duhet të ju për pikë në këto folks gjobë. Pra 9, 17, 20, 22, lloj e 29, dhe pastaj 34. A e kemi humbur dikë? Unë kam një 34. Ku did-- OK, i cili dëshiron të jetë 34? OK, eja lart, 34. Në rregull, kjo do të jetë edhe vlerë kulm. Si e keni emrin? Audienca: Peter. DAVID J. Malan: Peter, hajde lart. Të gjithë të drejtë, kështu që këtu është një tërë bandë e nyjeve. Secili nga ju djema përfaqëson njëra nga këto drejtkëndëshe. Dhe Gabe, pak e çuditshme njeri jashtë, paraqet parë. Pra, akrep i tij është pak më e vogël në ekran se të gjithë të tjerët. Dhe në këtë rast, secili prej tuaj të majtë Duart do të ose pikë poshtë, duke përfaqësuar null, kështu vetëm mungesa e një akrep, ose ajo do të jetë duke treguar në një nyje tjetër për ju. Deri tani, nëse ju zbukuro veten si foto këtu, të shkojnë përpara dhe pikë në njëri-tjetrin, me Gabe në veçanti duke treguar në numër 9 të përfaqësuar listën. OK, dhe numrin 34, dorën tuaj të majtë duhet vetëm të vënë në dysheme. OK, kështu që kjo është lista e lidhur. Pra, kjo është skenari në fjalë. Dhe në të vërtetë, kjo është përfaqësues e një klasë të problemeve që ju mund të përpiqet për të zgjidhur me kodin. Ju dëshironi për të në fund të fundit futur një element i ri në listë. Në këtë rast, ne do të provoni futur numrin 55. Por nuk do të jetë raste të ndryshme të marrin në konsideratë. Dhe në të vërtetë, kjo do të jetë një i madh-foto takeaways këtu, është, cilat janë raste të ndryshme. Cilat janë të ndryshme nëse kushteve ose Degët që programi juaj mund të kenë? E pra, numri që ju jeni duke u përpjekur për të insert, të cilat ne e dimë tani që të jetë 55, por në qoftë se ju nuk e dini paraprakisht, unë guxoj të them bie në të paktën tre situatat e mundshme. Ku mund të jetë një element i ri? Audienca: Dhe në fund apo të mesme. DAVID J. Malan: Në fund, në mesme, ose në fillim. Kështu që unë pretendojnë se ka të paktën Tre probleme ne kemi nevojë për të zgjidhur. Le të zgjedhin atë që është ndoshta ndoshta më e thjeshtë një, ku elementi ri takon në fillim. Kështu që unë jam do të ketë kodin mjaft si të kërkoni, të cilën unë vetëm shkroi. Dhe unë jam duke shkuar të ketë PTR, e cila Unë do të përfaqësoj këtu me gishtin tim, si zakonisht. Dhe mbani mend, se çfarë vlerë nuk e kemi nisja ptr të? Pra, ne e firmosur atë null fillimisht. Por atëherë çfarë bëri që ne të bëjmë një herë ne ishin brenda funksionin tonë të kërkimit? Ne kemi vendosur të barabartë me parë, e cila nuk do të thotë duke bërë këtë. Nëse unë vënë PTR barabartë për të parë, se çfarë duhet dora ime të vërtetë të jetë duke treguar? Drejta. Pra, nëse Gabe dhe unë do të jenë vlera të barabarta këtu, ne kemi nevojë për të dy pikë në numrin 9. Pra, ky ishte fillimi i historisë sonë. Dhe tani kjo është vetëm i hapur, edhe pse Sintaksa është e re. Konceptualisht kjo është vetëm kërkimi linear. 55 është e barabartë me 9? Ose më mirë, le të thonë se më pak se 9. Sepse unë jam duke u përpjekur për të kuptoj se ku për të vënë 55. Më pak se 9, më pak se 17, me pak se 20, me pak se 22, me pak se 29, më pak se 34, nr. Deri tani ne jemi në rast një nga të paktën tre. Nëse unë dua të futur 55 mbi këtu, çfarë rreshta të kodit duhet të merrni ekzekutuar? Si e bën këtë foto të njerëzit kanë nevojë për të ndryshuar? Çfarë duhet të bëj me dorën time të majtë? Kjo duhet të jetë null fillimisht, sepse I vjen ne fund te lista. Dhe çfarë duhet të ndodhë këtu me Pjetrin, ishte ajo? Ai është padyshim do të tregojnë për mua. Kështu që unë pretendojnë se ka të paktën dy linja i kodit në kodin mostër nga sot që do të zbatojë këtë Skenari i shtuar 55 në bisht. Dhe mund të ketë dikush hop dhe vetëm përfaqësojnë 55? Në rregull, ti je 55 të reja. Pra, tani çka nëse e ardhshme Skenari vjen së bashku, dhe ne duam të futur në filluar ose kreu i kësaj liste? Dhe si e ke emrin, numrin 55? Audienca: Jack. DAVID J. Malan: Jack? OK, nice to meet you. Mirësevini në fluturake. Deri tani ne jemi duke shkuar për të futur, të themi, numrin 5. Këtu është rasti i dytë i tre kemi ardhur me para. Pra, nëse 5 i takon në fillim, le të shohim se si ne të gjeni se nga. Unë nisja PTR tim tregues për numrin 9 përsëri. Dhe e kuptova, oh, 5 është më pak se 9. Pra, të rregulluar këtë fotografi për ne. Duart e të cilit, Gabe apo David or-- si e ke emrin numër 9-së? Audienca: Jen. DAVID J. Malan: hands-- Jen e cila e duarve tona duhet të ndryshojë? OK, kështu që Gabe tregon në çfarë tani? Në mua. Unë jam nyja e re. Kështu që unë vetëm do lloj lëvizje këtu për të parë atë me sy. Dhe ndërkohë çfarë mund të theksoj se? Ende ku unë jam treguar. Pra, kjo është ajo. Pra, vetëm të vërtetë një linjë e kodit fixes kjo çështje të veçantë, ajo do të duket. Në rregull, kështu që është e mirë. Dhe mund dikush të jetë një placeholder për 5? Eja lart. Ne do të merrni ju herën tjetër. Në rregull, kështu now-- dhe Si një mënjanë, emrat Unë nuk jam duke të kujtuar të qartë të së drejtës së tani, akrep pred, akrep paraardhësi dhe tregues i ri, që është vetëm emrat dhënë në kodin mostër me pointers ose duart e mia që është lloj duke treguar përreth. Si e keni emrin? Audienca: Christine. DAVID J. Malan: Christine. Mirësevini në fluturake. Në rregull, kështu që le të konsiderojnë tani një skenar pak më të bezdisshëm, ku unë dua të futur diçka si 26 në këtë. 20? Çfarë? Këto are-- gjë të mirë që ne kemi këtë stilolaps. Të gjithë të drejtë, 20. Nëse dikush mund të marrë një copë e letër gati, vetëm në case-- të gjithë të drejtë. Oh, interesante. E pra ky është një shembull e një bug leksion. OK kështu që çfarë është emri juaj përsëri? Audienca: Julia. DAVID J. Malan: Julia, mund të ju pop jashtë dhe të pretendojë keni qenë kurrë atje? OK, kjo nuk ndodhi kurrë. Ju faleminderit. Pra, mendoj që ne duam të futur Julia në këtë listë e lidhur. Ajo është numri 20. Dhe sigurisht që ajo është do të bëjë pjesë në begin-- nuk pikë në çdo gjë ende. Pra, dora jote mund të lloj të jetë poshtë null ose disa vlera e mbeturinave. Le të tregojnë historinë shpejtë. Unë jam duke treguar në numrin 5 këtë kohë. Pastaj unë kontrolloni 9. Pastaj unë kontrolloni 17. Pastaj unë kontrolloni 22. Dhe Unë të kuptojë, Ooh, Julia ka nevojë për të shkuar përpara 22. Pra, çfarë duhet të ndodhë? Duart e kujt duhet të ndryshojë? Julia-së, minave, or-- çfarë është emri juaj përsëri? Audienca: krishterë. DAVID J. Malan: krishterë apo? Audienca: Andy. DAVID J. Malan: Andy. Krishterë apo Andy? Andy ka nevojë për pikë në? Julia. Të gjithë të drejtë. Pra Andy, nuk ju duan të tregojnë në Julia? Por prisni një minutë. Në histori deri më tani, Unë jam lloj i një përgjegjës, në kuptimin që akrep është gjë që është lëviz nëpër lista. Ne mund të kemi një emër për Andy, por nuk ka ndryshore të quajtur Andy. I vetmi variabël tjetër që kemi është i parë, i cili është përfaqësuar nga Gabe. Pra, kjo është në fakt arsyeja pse në këtë mënyrë tani ne nuk kemi nevojë për këtë. Por tani në ekran ka përmend përsëri i pointer pred. Pra më lejoni të jetë më i qartë. Nëse kjo është akrep, kam pasur më të mirë merrni pak më inteligjent për përsëritje tim. Nëse ju nuk e mendjes duke e mia nëpër këtu përsëri, duke theksuar këtu, duke treguar këtu. Por më lejoni të ketë një tregues pred, akrep paraardhësi, që është lloj i vënë në element Unë kam qenë vetëm në. Kështu që kur të shkoj këtu, tani përditësime mia majtë. Kur të shkoj këtu përditësimet e mia majtë. Dhe tani unë kam jo vetëm një tregues për element që shkon pas Julia, Unë ende kanë një tregues për Andy, elementi më parë. Pra, ju keni qasje, në thelb, breadcrumbs, nëse do, të gjitha pointers nevojshme. Pra, nëse unë jam duke treguar Andy dhe unë jam gjithashtu duke në të krishterë, duart e të cilit tani duhet cekur diku tjetër? Pra Andy tani mund të nxjerr në Julia. Julia tani mund të tregojnë në të krishterë. Për shkak se ajo mund të kopjoni tim tregues të djathtë-së. Dhe që në mënyrë efektive ju vë kthehen në këtë vend këtu. Pra me pak fjalë, edhe pse kjo është duke na lloj përgjithmonë që në fakt të rinovuar një listë të lidhura, të realizuar se operacionet janë relativisht të thjeshta. Është e një, dy, tre rreshta të kodit në fund të fundit. Por përfundoi rreth atyre rreshta të kodit me sa duket është pak e logjikës që në mënyrë efektive pyet pyetjen, ku jemi ne? A jemi në fillim, mesme, ose në fund? Tani, ka sigurisht disa të tjera Operacionet ne mund të zbatojë. Dhe këto foto këtu vetëm të përshkruaj ajo që ne vetëm e bëri me njerëzit. Po në lidhje me heqjen? Nëse unë dua të, për shembull, hequr numrin 34 ose 55, Unë mund të ketë të njëjtin lloj të kodit, por unë jam duke shkuar për të duhet një ose dy hapa. Për shkak se çfarë ka të re? Nëse unë hiqni dikë në fund, si numër 55 dhe pastaj 34, ajo gjithashtu duhet të ndryshojë si bëj unë këtë? Unë kam për të nuk evict-- çfarë është emri juaj përsëri? Audienca: Jack. DAVID J. Malan: Jack. Unë kam për të, jo vetëm evict-- Jack pa pagesë, kështu që fjalë për fjalë e quajnë Jack të lirë, ose të paktën akrep atje, por tani çfarë duhet të ndryshojë me Pjetrin? Dora e tij më mirë të fillojë duke treguar poshtë. Sepse sa më shpejt që unë e quaj të lirë në Jack, nëse Pjetrit ende duke treguar Jack dhe unë për këtë arsye të mbajtur traversing lista dhe qasje kjo akrep, kjo është kur segmentimi ynë i vjetër shoku faji mund të vërtetë të fillojë në. Sepse ne kemi dhënë prapa kujtesës për Jack. Ju mund të qëndrojnë atje fundore për vetëm një moment. Sepse ne kemi vetëm një çift operacionet e fundit të marrin në konsideratë. Heqja kreun e listës, ose beginning-- dhe kjo të pak i bezdisshëm. Sepse ne duhet të dimë se Gabe është lloj i veçantë në këtë program. Sepse në të vërtetë, ai e ka treguesin e vet. Ai nuk është vetëm duke u vuri në, si është pothuajse të gjithë të tjerët këtu. Pra, kur kreu i listës është hequr, duart e të cilit duhet të ndryshojë tani? Si e keni emrin përsëri? Audienca: Christine. DAVID J. Malan: Unë jam e tmerrshme në emra, me sa duket. Pra, Christine dhe Gabe, duart e të cilit duhet të ndryshojë kur ne përpiqemi për të hequr Christine, Numri 5, nga foto? OK, kështu që le të bëjë Gabe. Gabe do të vinte, me sa duket, me numër 9. Por çfarë tjetër duhet të ndodhë? Audienca: Christine duhet të jetë null [e padëgjueshme]. DAVID J. Malan: OK, ne duhet ndoshta make-- dëgjova "null" diku. Audienca: Null dhe të lirë të saj. DAVID J. Malan: NULL çfarë? Audienca: Null dhe të lirë të saj. DAVID J. Malan: Null dhe të lirë të saj. Pra, kjo është shumë e lehtë. Dhe kjo është e përsosur që ju jeni tani lloj të qëndruar aty, nuk i përkasin. Për shkak se ju keni qenë tërhiqet nga lista. Ju keni qenë në mënyrë efektive jetimë nga lista. Dhe kështu që ne kishim më mirë telefononi falas tani në Christine për të dhënë atë kujtesën mbrapa. Përndryshe çdo herë ne fshirë një nyje nga lista ne të bërë lista shkurtër, por në fakt nuk rënie madhësia në kujtesën. Dhe kështu që në qoftë se do të vazhdojmë duke shtuar dhe duke shtuar, duke shtuar gjëra në listë, kompjuteri im mund të merrni më ngadalë dhe të ngadalshme dhe të ngadalshëm, sepse unë jam running nga memorie, edhe në qoftë se unë nuk jam në të vërtetë duke përdorur bytes Christine së e kujtesës më. Pra, në fund ka të tjera skenare, e largimit course-- në mes, heqjen në fund, siç e pamë. Por më interesante Sfida tani është do të jetë për të marrë parasysh pikërisht atë kohë running është. Pra, jo vetëm që mund të mbani tuaj copa letre, në qoftë se, Gabe, ju nuk do mend duke i dhënë të gjithë një top stresit. Thank you so much për listën tonë lidhur i vullnetarëve këtu, në qoftë se ju mund. [Duartrokitje] DAVID J. Malan: Në rregull. Pra disa analitike Pyetjet Pastaj, nëse unë mund të. Ne e kemi parë këtë simbol më parë, O i madh dhe omega, kufijtë e sipërme dhe kufijtë më të ulët në running kohë të disa algorithm. Pra, le të marrin në konsideratë vetëm disa pyetje. Një, dhe kemi thënë atë para, çfarë është running kohë e kërkimit të një Lista në aspektin e O e madhe? Çfarë është një kufi i sipërm për drejtimin Koha e kërkuar një listë të lidhur të zbatuar nga vullnetarët tanë këtu? Është O i madh i n, lineare. Sepse në rastin më të keq, element, si 55, ne mund të jetë në kërkim për të mund të jetë aty ku Jack ishte, të gjitha rrugën në fund. Dhe për fat të keq, ndryshe nga një grup ne nuk mund të merrni dashuroj këtë kohë. Edhe pse të gjithë njerëzit tanë të ishin të renditura nga elemente të vogla, 5, të gjithë rrugën deri në elementin më të madh, 55, që është zakonisht një gjë e mirë. Por ajo që e bën këtë supozim nuk na lejojnë të bëjmë? Audienca: [padëgjueshme] DAVID J. Malan: Thuaj përsëri? Audienca: qasje të rastësishme. DAVID J. Malan: qasje të rastësishme. Dhe nga ana tjetër kjo do të thotë që ne mund të asnjë përdorin më zero dobët, intuitë, dhe spikatshmëri e përdorimit binare kërkoni dhe të ndajnë dhe të pushtuar. Sepse edhe pse ne njerëzit mund të qartë shohim se Andy apo krishterë ishin afërsisht në mes të listës, ne vetëm e di se si një kompjuter nga skimming listën nga fillimi. Pra, ne kemi hequr dorë atë qasje të rastit. O aq i madh i n tani është e sipërme detyruar në kohën tonë të kërkimit. Po në lidhje me omega e kërkimin tonë? Çfarë është më e ulët lidhur në kërkim për një numër në këtë listë? Audienca: [padëgjueshme] DAVID J. Malan: Thuaj përsëri? Audienca: Një. DAVID J. Malan: Një. Ora Pra konstante. Në rastin më të mirë, Christine është vërtetë në fillim të lista. Dhe ne jemi duke kërkuar për Numri 5, kështu që ne e gjeti atë. Pra, nuk ka punë e madhe. Por ajo e mori për të të jetë në fillimi i listës në këtë rast. Çka në lidhje me diçka si Fshij? Çka në qoftë se ju dëshironi të fshini një element? Çfarë është sipërme të lidhura dhe të ulët të lidhur më fshirjes diçka nga një i lidhur lista? Audienca: [padëgjueshme] DAVID J. Malan: Thuaj përsëri? Audienca: n. DAVID J. Malan: n është vërtetë sipërme të lidhura. Sepse në rastin më të keq ne përpiqemi të fshini Jack, si ne vetëm e bëri. Ai është gjithë rrugën në fund. Na merr përgjithmonë, ose n hapa për të gjetur atë. Pra, kjo është një kufi i sipërm. Kjo është linear, i sigurt. Dhe rasti më i mirë kohë në punë, ose caqet më të ulët në rastin më të mirë do të jetë kohë konstante. Sepse ndoshta ne përpiqemi të fshini Christine, dhe ne vetëm të merrni me fat ajo është në fillim. Tani prit një minutë. Gabe ishte gjithashtu në fillim, dhe ne gjithashtu kishte për të rinovuar Gabe. Kështu që nuk ishte vetëm një hap. Pra, është me të vërtetë konstante kohë, në rastin më të mirë, për të hequr elementin më të vogël? Kjo është, edhe pse kjo mund të jetë dy, tre, apo edhe 100 rreshta të kodit, në qoftë se është numri i njëjtë i linjat, jo në ndonjë lak, dhe i pavarur i madhësisë i listës, absolutisht. Fshirjes element në fillimi i listës, edhe në qoftë se ne duhet të merren me Gabe, është ende koha konstante. Pra, kjo duket si një hap i madh prapa. Dhe çfarë një humbje kohe në qoftë se, në një javë dhe javë zero kemi pasur jo vetëm Kodi pseudokod por kodin aktual të zbatojë diçka që është log Baza n, ose hyni, në vend, i n, bazë 2, në drejtim të kohës së vet running. Pra, pse dreq do të duam të fillojë duke përdorur diçka si një listë e lidhur? Po. Audienca: Pra, ju mund të shtoni elementet në rrjet. DAVID J. Malan: Pra, ju mund të të shtoni elemente të vektorit. Dhe kjo shumë është tematike. Dhe ne do të vazhdojmë të shohim kjo, kjo tregti-off, shumë si ne kemi parë një tregtisë-off me merge lloj. Ne me të vërtetë mund të përshpejtojë kërkoni ose klasifikim, në vend, në qoftë se ne kemi shpenzuar një hapësirë ​​pak më shumë dhe të kanë një copë shtesë e një kujtim apo një grup për merge lloj. Por ne kemi shpenzuar më shumë hapësirë, por ne të kursyer kohë. Në këtë rast, ne jemi duke i dhënë kohën, por ne jemi duke fituar fleksibilitet, Dinamizmi në qoftë se ju do, e cila është ndoshta një tipar pozitiv. Ne gjithashtu jemi të shpenzimeve hapësirë. Në çfarë kuptimi është një i lidhur listë më të shtrenjtë në drejtim të hapësirës se një grup? Ku është hapësirë ​​shtesë që vijnë nga? Po? Audienca: [padëgjueshme] akrep. DAVID J. Malan: Po, ne gjithashtu kanë treguesin. Pra, kjo është minorly bezdisshëm në se jam më Unë ruajtjen vetëm një int për të përfaqësuar një int. Unë jam ruajtjen një int dhe një tregues, e cila eshte gjithashtu 32 bit. Kështu që unë jam fjalë për fjalë dyfishuar shuma e hapësirës përfshirë. Pra, kjo është një tregti-off, por kjo është në rastin e int. Supozoni se ju nuk jeni ruajtjen int, por mendoj secili prej këtyre rectangles ose secila prej këtyre njerëzve është përfaqësuar një fjalë, një fjalë angleze që mund të jetë pesë karaktere, 10 karaktere, ndoshta edhe më shumë. Pastaj duke shtuar vetëm 32 më shumë bit mund të jetë më pak e një punë e madhe. Po në qoftë se secili prej nxënësve në demonstratë ishin fjalë për fjalë structs studentore që kanë emrat dhe shtëpitë dhe ndoshta numrat e telefonit dhe Twitter trajton dhe si. Pra të gjitha fushat kemi filluar duke folur për ditën tjetër, shumë më pak e një punë e madhe si nyjet tona të merrni më interesante dhe e madhe për të shpenzuar, eh, një shtesë tregues vetëm për të lidhur ato së bashku. Por në të vërtetë, kjo është një tregti-off. Dhe me të vërtetë, kodi është më komplekse, si ju do të shohin nga skimming përmes që shembulli të veçantë. Por çka nëse ka pasur disa Grail shenjtë këtu. Po në qoftë se ne nuk do të marrë një hap prapa, por një hap i madh përpara dhe të zbatojë një të dhënave Struktura nëpërmjet të cilat ne mund të gjeni elemente si Jack apo Christine ose ndonjë elemente të tjera në këtë grup në kohë reale të vazhdueshme? Kërkimi është konstante. Fshij është konstante. Fut është konstante. Të gjitha këto operacione janë konstante. Kjo do të ishte Grail jonë e shenjtë. Dhe kjo është ajo ku ne do të marr herën tjetër. Shihemi pastaj.