[Powered by Google Translate] [Java 6, vazhdoi] [David J. Malan] [Universiteti i Harvardit] [Kjo është CS50.] [CS50.TV] Kjo është CS50 dhe ky është fundi i javës 6. Pra CS50x, një nga kurset e para të Harvardit e përfshira në iniciativë EDX vërtetë debutuar këtë të hënë e kaluar. Nëse ju do të donte për të marrë një paraqitje e shkurtër e asaj që të tjerëve në internet tani janë në vijim së bashku me të, ju mund të shkojnë në x.cs50.net. Kjo do të ju përcjellim në vendin e duhur në edx.org, i cili ishte vendi ku ky dhe kurse të tjera nga MIT dhe Berkeley tani jetojnë. Ju do të keni për të nënshkruar për një llogari, ju do të gjeni se materiali është kryesisht i njëjtë si ju kam pasur këtë semestër, megjithëse disa javë vonuar, si ne të merrni gjithçka gati. Por ajo që nxënësit në CS50x tani do të shihni është një ndërfaqe mjaft si ky. Kjo, për shembull, është Zamyla udhëheq walkthrough për të vendosur problemin 0. Pas logging in për edx.org, një student CS50x sheh llojet e gjërave të ju do të presin për të parë në një kurs: leksion për të hënën, Ligjërata për të mërkurën, pantallona të shkurtra të ndryshme, vendos problem, walkthroughs, PDF. Përveç kësaj, siç e shihni këtu, përkthimet e makinës i transkripteve anglisht në kinezisht, japonisht, spanjisht, italisht, dhe një bandë e tërë e gjuhëve të tjera që me siguri do të jetë e pakryer si ne roll ato programuar duke përdorur diçka që quhet një API, ose programimi aplikimit interface, nga Google që na lejon të konvertohet anglisht në këto gjuhë tjera. Por në sajë të shpirtit të mrekullueshme e disa qindra-plus vullnetarë, njerëz të rastit në internet që kanë ofruar mirësi për të marrë të përfshirë në këtë projekt, ne do të gradualisht të përmirësuar cilësinë e këtyre përkthimeve duke pasur njerëzit të korrigjuar gabimet që kompjuterat tanë kanë bërë. Pra, ajo rezulton ne kishim një nxënës pak më shumë shfaqen të hënën se ne prisnim fillimisht. Në fakt, tani CS50x ka 100.000 njerëz në vijim së bashku në shtëpi. Pra, të kuptojnë se janë të gjitha pjesë e kësaj klase inauguruese e bërë këtë kurs në shkenca kompjuterike Arsimi në përgjithësi, më gjerësisht, të arritshme. Dhe realiteti është tani, me disa nga këto kurse masive online, ata të gjithë të fillojnë me këto numra shumë të larta, si ne duket se kanë bërë këtu. Por qëllimi, në fund të fundit, për CS50x është me të vërtetë për të marrë sa më shumë njerëz për të vijë të përfundojë sa të jetë e mundur. Me dashje, CS50x do të ofrohen nga ky e hëna e kaluar të gjithë rrugën nëpër 15 prill 2013, në mënyrë që folks të cilët kanë angazhime të shkollës gjetkë, , puna e familjes, konfliktet e tjera dhe si, kanë pak më shumë fleksibilitet me të cilat të zhyten në këtë kurs, të cilat, mjafton që të them, është mjaft ambicioze bëhet vetëm nëse gjatë vetëm tre muaj gjatë një semestri zakonshme. Por këta studentë do të trajtimin e grupe të njëjtat probleme, duke e parë të njëjtën përmbajtje, pasur qasje në pantallona të njëjta dhe të ngjashme. Pra, të kuptojnë se ne jemi të gjithë të vërtetë në këtë së bashku. Dhe një nga qëllimet fund të CS50x nuk është vetëm për të marrë sa më shumë folks në vijën e finishit dhe për t'u dhënë atyre këtë kuptim newfound e shkencës kompjuterike dhe programimit, por edhe të kenë ata e kanë këtë përvojë të përbashkët. Një nga karakteristikat përcaktuese të 50 në kampus, ne shpresojmë, ka qenë ky lloj i përvojës komunale, për mirë apo për keq, ndonjëherë, por që këta njerëz të kthehet në të majtë dhe në të djathtë, dhe orarit të punës dhe hackathon dhe drejtë. Është pak e vështirë për të bërë që në person me folks online, por CS50x do të përfundojë në prill me parë ndonjëherë Expo CS50, cili do të jetë një përshtatje online idenë tonë të panairit ku këto mijëra e studentëve të gjithë do të ftohen të dorëzojnë një 1 - deri 2-minutëshe video, ose një screencast e projektit të tyre përfundimtar ose video prej tyre mbanin përshëndetje dhe duke folur në lidhje me projektin e tyre dhe demoing atë, shumë si paraardhësit tuaj kanë bërë këtu në kampus në panair, kështu që deri në fund të semestrit së, shpresa është që të kemi një ekspozitë globale e projekteve të nxënësve CS50x 'përfundimtare, ashtu si ajo që ju pret këtu në këtë dhjetor kampus. Pra, më shumë se në muajt që do të vijnë. Me 100.000 studentë, megjithatë, vjen nevoja për një AK pak më shumë. Duke pasur parasysh se ju djema janë gjurmët flakëron këtu dhe duke marrë CS50 disa javë më parë për lirimin e këtij materiali ndaj folks në EDX, realizuar ne do të duan që të përfshijë sa më shumë prej studentëve tona të jetë e mundur në këtë nismë, edhe gjatë semestrit si dhe këtë dimër dhe kjo pranverë që vjen. Pra, nëse ju do të donte për të marrë të përfshirë në CS50x, veçanërisht bashkuar në të CS50x diskutuar, versioni EDX e CS50 diskutuar, që shumë prej jush kanë qenë duke përdorur në kampus, bordi internet buletini, ju lutem mos kokën në atë URL, le të na tregoni se kush jeni, sepse ne do të duan për të ndërtuar një ekip të studentëve dhe stafit dhe Fakulteti njësoj në kampus të cilët janë thjesht duke luajtur së bashku dhe për të ndihmuar jashtë. Dhe kur ata shohin një pyetje që është e njohur për ta, keni dëgjuar një student raportimit disa bug diku atje në ndonjë vend në internet, dhe që unaza një zile sepse ju gjithashtu kishte të njëjtën çështje që në tuaj d-sallë disa kohë më parë, shpresojmë se atëherë ju mund të bie në dhe të ndajnë përvojën tuaj. Pra ju lutem mos marrim pjesë në qoftë se ju do të donte. Kurse shkenca kompjuterike në Harvard kanë një grimë e një tradite, CS50 në mesin e tyre, për të pasur disa veshje, disa rroba, të cilat ju mund të veshin me krenari në fund të semestrit, duke thënë mjaft krenari që keni mbaruar CS50 dhe mori CS50 dhe si, dhe ne gjithmonë përpiqemi për të përfshirë studentët në këtë proces sa më shumë të jetë e mundur, ku ne ftojmë, rreth kësaj kohe të semestrit, studentët të paraqesin planet duke përdorur Photoshop, ose çfarëdo mjet i zgjedhur ju dëshironi të përdorni në qoftë se ju jeni një projektuesi, të paraqesin planet për të T-shirts dhe sweatshirts dhe cadra dhe Bandanas pak për qentë ne tani kemi dhe si. Dhe çdo gjë është pastaj - fituesit për çdo vit janë të ekspozuara pas në faqen e internetit Kursi së në store.cs50.net. Gjithçka është shitur me kosto atje, por në faqen e internetit vetëm shkon vetë dhe lejon njerëzit të zgjedhin ngjyrat dhe harton që ata donin. Kështu që unë mendova që ne vetëm do të ndajnë disa nga planet e vitit të kaluar që ishin në faqen e internetit përveç kësaj një këtu, e cila është një traditë vjetore. "Çdo ditë unë jam seg Faultn" ishte një prej parashtrimeve të vitit të kaluar, e cila është ende në dispozicion atje për alumni. Ne kemi pasur këtë, "CS50, themeluar 1989." Një nga Bowdens tona, Rob, ishte shumë popullor në vitin e kaluar. "Ekipi Bowden" ka lindur, ky dizajn është paraqitur, në mesin e shitësit të lartë. Si ishte kjo një këtu. Shumë njerëz kishin "Ethet" Bowden sipas shkrimet shitjes. Kuptojnë se që tani mund të jetë dizajni juaj atje, deri në internet. Më shumë detaje për këtë në problemin e ardhshëm vendos për të ardhur. Një mjet shumë: ju keni pasur disa ekspozimit dhe shpresojmë se tani disa duart-në përvojën me GDB, që është, sigurisht, një Rregullues dhe ju lejon të manipuluar programi juaj në një nivel mjaft të ulët, duke bërë atë që llojet e gjëra? Çfarë do të ju lejojnë të bëni Gdb? Po? Jepni diçka. [Student përgjigje, pakuptueshëm] Mirë. Hapi në funksion, kështu që ju nuk duhet të shkruani vetëm të drejtuar dhe kanë goditje program përmes tërësinë e saj, shtypjen gjëra të prodhimit standard. Përkundrazi, ju mund të hap nëpër atë rresht pas rreshti, ose shtypja e ardhshme për të shkuar vijë nga rresht pas rreshti, ose hap të zhyten në një funksion, zakonisht ai që ju ka shkruajtur. Çfarë tjetër do të ju lejojnë të bëni Gdb? Po? [Student përgjigje, pakuptueshëm] Print variablave. Pra, nëse ju doni të bëni një analizë e vetvetes pak brenda programit tuaj pa pasur nevojë të përdorë për të shkruar deklaratat printf në të gjithë vendin, vetëm ju mund të shtypura një ndryshore ose të shfaqë një ndryshore. Çfarë tjetër mund të bëni me një Rregullues si gdb? [Student përgjigje, pakuptueshëm] Saktësisht. Ju mund të vendosni breakpoints, ju mund të them ekzekutimin pushim në funksion kryesor ose funksion foo. Ju mund të them ekzekutimin pushim në linjë 123. Dhe pikat e ndalimit janë një teknikë të vërtetë të fuqishme sepse në qoftë se ju keni një ndjenjë të përgjithshme se ku problemi juaj ndoshta është, ju nuk keni për të humbur kohën shkelën nëpër tërësinë e programit. Ju mund të thelb të kërcejnë drejtë atje dhe pastaj të fillojë typing - shkelën nëpër atë me hap ose tjetër, ose si. Por kapur me diçka si gdb është se ajo ndihmon ju, njeriu, gjeni problemet tuaja dhe për të gjetur mete tuaja. Kjo nuk do të gjejnë ata aq shumë për ju. Pra, ne kemi prezantuar style50 tjetër ditë, e cila është një linjë komande mjet i shkurtër që përpiqet të stilizoj kodin tuaj pak më të pastër se ju, e njeriut, mund të ketë bërë. Por kjo, gjithashtu, është në të vërtetë vetëm një gjë estetike. Por kjo rezulton se ka ky mjet tjetër i quajtur Shprehje që është pak më misterioze për t'u përdorur. Prodhimi i saj është atrociously fshehtë në shikim të parë. Por kjo është mrekullisht e dobishme, sidomos tani që ne jemi në pjesën e mandatit ku ju jeni duke filluar të përdorin malloc dhe alokimin dinamik kujtesës. Gjërat mund të shkojnë me të vërtetë, me të vërtetë keq shpejt. Sepse në qoftë se ju harroni të liruar kujtesën tuaj, ose ju dereference disa tregues NULL, ose ju dereference disa tregues plehrash, çka zakonisht është simptomë se rezultatet? Seg faj. Dhe ju të merrni këtë skedë bazë të numrit të disa kilobytes ose megabajt që përfaqëson gjendjen e kujtesës programit tuaj kur ajo u rrëzua, por në fund të fundit programi juaj seg gabimet, fajin segmentimit, që do të thotë diçka e keqe ka ndodhur pothuajse gjithmonë e lidhur për një gabim kujtesës të lidhura që keni bërë diku. Pra Shprehje ju ndihmon të gjeni gjëra të tilla si kjo. Kjo është një mjet që ju drejtuar, si gdb, pasi ju keni hartuar programin tuaj, por në vend se të drejtuar programin tuaj direkt, ju drejtuar Shprehje dhe ju të kalojë në atë programin tuaj, ashtu si ju bëni me GDB. Tani, përdorimi, për të marrë llojin më të mirë të prodhimit, është pak më të gjatë, në mënyrë të drejtë ka në majë të ekranit që ju do të shihni Shprehje-V. "-V" pothuajse universalisht të thotë fjalëshumë kur ju jeni duke përdorur programe në një kompjuter Linux. Pra, kjo do të thotë më shumë të dhëna nxjerr nga goja se sa ju mund nga default. "- Rrjedhje-check = të plotë." Kjo është vetëm duke thënë kontroll për të gjitha rrjedhjet e kujtesës mundshme, Gabimet që unë mund të ketë bërë. Kjo, gjithashtu, është një paradigmë të përbashkët me programet Linux. Në përgjithësi, në qoftë se ju keni një argument command line që është një "switch", që është menduar për të ndryshuar sjelljen e programit, dhe kjo është një letër të vetme, kjo është v-, por nëse kjo është ndezur, vetëm me hartimin e programues, është një fjalë të plotë apo seri të fjalëve, linja e komandës argumenti fillon me -. Këto janë vetëm konventa e njeriut, por ju do të shihni ato gjithnjë e më shumë. Dhe pastaj, në fund, "a.out" është emri arbitrar për programin në këtë shembull të veçantë. Dhe këtu e disa output përfaqësues. Para se të shohim se çka mund të them, më lejoni të shkoj në një copë të kodit gjatë këtu. Dhe më lejoni të lëvizë këtë nga rruga, që vijnë së shpejti, dhe le të marrin një vështrim në memory.c, i cili është ky shembull të shkurtër këtu. Pra, në këtë program, më lejoni të zoom në në funksionet dhe pyetjet. Ne kemi një funksion kryesor që e quan një funksion, F, dhe pastaj ajo do të vazhdojë të bëjë f, në anglisht pak më teknik? Çfarë ka f vazhdoj të bëj? Si në lidhje unë do të fillojë me linjë të 20, dhe vendndodhjen ylli nuk ka rëndësi, por unë vetëm do të jetë në përputhje me këtu leksion fundit. Çfarë është linjë e 20 për ne? Në anën e majtë. Ne do të thyejnë atë poshtë më tej. Int * x: çfarë do që të bëj? Rregull. Është deklaruar një tregues, dhe tani le të jetë edhe më e teknike. Çfarë do të thotë kjo, shumë konkretisht, të deklarojë një akrep? Dikush tjetër? Po? [Student përgjigje, pakuptueshëm] Shume larg. Pra, ju jeni duke e lexuar në anën e djathtë të shenjës të barabartë. Le të përqëndrohet vetëm në të majtë, vetëm në int * x. Kjo do të thotë "shpallë" një tregues, por tani le të zhyten më thellë në për këtë përkufizim. Çfarë bën që konkretisht, teknikisht do të thotë? Po? [Student përgjigje, pakuptueshëm] Rregull. Është duke u përgatitur për të ruajtur një adresë në kujtesë. Mirë. Dhe le të marrin këtë hap më tej, por është deklaruar një ndryshore, x, që është 32 bit. Dhe unë e di se është 32 bit sepse -? Kjo nuk është për shkak se ajo është një int, sepse kjo është një tregues në këtë rast. Rastësi që kjo është një dhe e njëjtë me një int, por fakti se nuk ka yll do të thotë kjo është një tregues dhe në aplikim, si me shumë kompjuterë, por jo të gjitha, janë pointers 32 bit. Në hardware më moderne si të Macs fundit, PC e fundit, ju mund të keni 64-bit pointers, por në aplikim, këto gjëra janë 32 bit. Pra, ne do të standartizuar për këtë. Më konkretisht, historia shkon si vijon: Ne "deklarojnë" një tregues, çfarë do të thotë kjo? Ne kemi përgatitur për të ruajtur një adresë memorie. Çfarë do të thotë kjo? Ne krijimin e një ndryshore x quhet që merr 32 bit se së shpejti do të ruajtur adresën e një numër të plotë. Dhe kjo është ndoshta po aq të saktë sa ne mund të merrni. Kjo është në rregull duke shkuar përpara për të lehtësuar botën dhe vetëm thonë deklarojë një tregues të quajtur x. Shpallë një tregues, por kuptojnë dhe të kuptojnë se çfarë po ndodh në të vërtetë edhe në vetëm këto karaktere pak. Tani, kjo është pothuajse një pak më e lehtë, edhe pse kjo është një shprehje më të gjatë. Pra, çfarë është kjo bën, që e theksoi tani: "malloc (10 * sizeof (int));" Po? [Student përgjigje, pakuptueshëm] Mirë. Dhe unë do të marrë atë atje. Është caktimin një copë e kujtesës për dhjetë integers. Dhe tani le të zhyten në pak më thellë, ajo e ndarjes së një copë e kujtesës për dhjetë integers. Çfarë është malloc pastaj kthehen? Adresa e asaj copë, ose më konkretisht, adresën e bajt parë të asaj copë. Si atëherë jam unë, programues, që të dini se ku mbaron copë e kujtesës? Unë e di se është e afërt. Malloc, sipas definicionit, do të ju jap një copë puqet e kujtesës. Asnjë boshllëqe në të. Ju keni qasje në çdo bajt në atë copë, për të kthyer prapa për të mbështetur, por si mund ta di se ku në fund të këtij copë e kujtesës është? Kur ju përdorni malloc? [Student përgjigje, pakuptueshëm] Mirë. Ju nuk e bëni. Ju duhet të mbani mend. Unë duhet të mbani mend që kam përdorur vlerën 10, dhe unë as nuk duket se kanë bërë që këtu. Por përgjegjësia është krejtësisht mbi mua. Strlen, të cilat ne kemi bërë pak për të varur nga strings, punon vetëm për shkak të kësaj konvente për të pasur \ 0 ose ky karakter të veçantë nul, Nul, në fund të vargut. Kjo nuk do të mbajë për vetëm chunks arbitrare të kujtesës. Është e deri tek ju. Pra linjës 20, atëherë, ndan një copë e kujtesës që mund të ruajë dhjetë integers, dhe ai ruan adresën e bajt parë e asaj copë e kujtesës në x ndryshueshme quajtur. Ergo, e cila është një akrep. Pra linjës 21, për fat të keq, ishte një gabim. Por së pari, çfarë është ajo duke bërë? Është thënë dyqan në vendin 10, 0 indeksuara, nga copë e kujtesës quajtur x 0 vlera. Pra njoftim disa gjëra janë në vazhdim e sipër. Edhe pse x është një akrep, kujtohet nga disa javë më parë që ju ende mund të përdorni array-style parantezë simbol katror. Sepse kjo është në të vërtetë të shkurtër të dorës simbol për aritmetike akrep më të fshehtë-looking. ku ne do të bëjmë diçka si kjo: Merrni x adresave, lëvizin 10 spote mbi, pastaj shkoni atje për çfarëdo adresë është e ruajtur në atë vend. Por sinqerisht, kjo është vetëm për të lexuar egër dhe për të marrë të rehatshme me. Pra bota zakonisht përdor kllapa katrore vetëm për shkak se ajo është aq më shumë e njeriut-miqësore për të lexuar. Por kjo është ajo që është me të vërtetë ndodh nën kapuç; x është një adresë jo, një grup, në vetvete. Pra, kjo është ruajtjen 0 në vendin 10 në x. Pse është kjo e keqe? Po? [Student përgjigje, pakuptueshëm] Pikërisht. Ne vetëm dhjetë ints ndarë, por ne numërimin nga 0, kur programimit në C, kështu që ju keni qasje në 0 10 1 2 3 4 5 6 7 8 9, por jo. Pra, ose programi do të defektit seg ose ajo nuk është. Por ne vërtetë nuk e di, kjo është lloj i një sjellje nondeterministic. Me të vërtetë varet nga ajo nëse ne të merrni me fat. Në qoftë se kjo rezulton se sistemi operativ nuk ka mend në qoftë se unë e përdor atë bajt shtesë, edhe pse ajo nuk ka dhënë atë për mua, programi im nuk mund të rrëzimit. Është papërpunuara, është buggy, por ju nuk mund të shihni se simptomë, ose ju mund të shihni atë vetëm një herë në një kohë. Por realiteti është se bug është, në fakt, nuk ka. Dhe kjo është me të vërtetë problematike në qoftë se ju keni shkruar një program që ju dëshironi që të jetë i saktë, se ju keni shitur programin që njerëzit janë duke përdorur që çdo herë në një kohë punon sepse, sigurisht, kjo nuk është e mirë. Në fakt, në qoftë se ju keni një telefon Android apo një iPhone dhe ju të shkarkoni Apps këto ditë, në qoftë se ju keni pasur ndonjëherë një app lë vetëm, të gjithë një e papritur ajo zhduket, kjo është pothuajse gjithmonë rezultat i disa çështje kujtesës të lidhura, ku programues dehur dhe dereferenced një tregues se ai ose ajo nuk duhet të ketë, dhe rezultati i iOS ose Android është vetëm për të vrarë program krejt më tepër se sjellja e rrezikut të papërcaktuar ose disa lloj kompromisi sigurisë. Ka një bug të tjera në këtë program përveç kësaj një të tillë. Çka kam dehur deri në këtë program? Unë nuk e kam praktikuar atë që unë kam predikuar. Po? [Student përgjigje, pakuptueshëm] Mirë. Unë nuk e kanë liruar e kujtesës. Pra, rregulli i gishtit tani duhet të jetë në çdo kohë që ju e quani malloc, ju duhet të telefononi falas kur ju jeni bërë duke përdorur atë memorie. Tani, kur unë do të të duan për të liruar këtë memorie? Ndoshta, duke supozuar kjo linjë e parë ishte e saktë, unë do të duan për të bërë atë këtu. Sepse unë nuk mund të, për shembull, të bëjë atë këtu. Pse? Vetëm jashtë fushëveprimit. Pra, edhe pse ne jemi duke folur për pointers, kjo është një javë 2 apo 3 çështje, ku x është vetëm në kuadër brenda të formatimin e teksteve kaçurrel ku ajo u shpall. Pra, ju patjetër nuk mund të lirë atë atje. Shansi im i vetëm për të liruar atë është afërsisht pas vijës 21. Ky është një program mjaft të thjeshtë, ajo ishte mjaft e lehtë një herë ju lloj i mbështjellë mendjen tuaj rreth çfarë programi është duke bërë, ku gabimet ishin. Dhe edhe në qoftë se ju nuk e shihni atë në të parë, shpresojmë se ajo është pak e qartë tani që këto gabime janë goxha të lehtë zgjidhur dhe e bëri të lehtë. Por kur një program është më shumë se 12 rreshta të gjatë, kjo është 50 rreshta të gjatë, 100 rreshta të gjatë, duke ecur përmes linjës tuaj kod pas rreshti, duke menduar se nëpërmjet saj logjikisht, është e mundur, por nuk është veçanërisht e bukur për të bërë, vazhdimisht në kërkim të mete, dhe kjo është gjithashtu e vështirë për të bërë, dhe kjo është arsyeja pse një mjet si Shprehje ekziston. Më lejoni të shkoj përpara dhe të bëjë këtë: më lejoni të hapur dritaren time terminali, dhe më lejoni të drejtuar jo vetëm kujtesë, sepse kujtesës duket të jetë mirë. Unë jam marrë me fat. Shkuarja në atë bajt shtesë në fund të array nuk duket të jetë shumë problematike. Por le mua, megjithatë, të bëjë një kontroll mendje e shëndoshë, që thjesht do të thotë për të kontrolluar nëse janë apo jo kjo është e vërtetë e saktë. Pra, le ta bëjmë Shprehje-v - rrjedhje-check = plot, dhe pastaj emrin e programit në këtë rast është e kujtesës, jo a.out. Pra më lejoni të shkoj përpara dhe të bëjë këtë. Hit Enter. Dashur Perëndia. Kjo është prodhimin e saj, dhe kjo është ajo që unë alluded më parë. Por, në qoftë se ju mësoni për të lexuar nëpër të gjitha të pakuptimta këtu, shumica e kjo është vetëm prodhimi diagnostike që nuk është se interesante. Çka syri yt me të vërtetë dëshiron të jetë në kërkim për të është çdo përmendje e gabimit apo të pavlefshme. Fjalët që sugjerojnë probleme. Dhe me të vërtetë, le të shohim se çfarë po ndodh këtu poshtë gabuar. Unë kam një përmbledhje e disa lloj, "në përdorim në dalje:. Bytes 40 blloqe në 1" Unë nuk jam me të vërtetë i sigurt se çfarë është një bllok, por 40 bytes të vërtetë ndjehet si unë mund të kuptoj se ku po vijnë nga. 40 bytes. Pse janë 40 bytes në përdorim në dalje? Dhe më konkretisht, nëse lëvizni poshtë këtu, pse kam humbur 40 bytes patjetër? Po? [Student përgjigje, pakuptueshëm] Perfect. Po, pikërisht. Ka qenë dhjetë integers, dhe secili prej tyre është madhësia e 4, ose 32 bit, kështu që unë kam humbur pikërisht 40 bytes, sepse, si ju propozuar, unë nuk kam quajtur pa pagesë. Kjo është një bug, dhe tani le të shohim poshtë një pak më tej dhe të shohim më tej për këtë, "Pavlefshme shkruaj e madhësisë 4." Tani çfarë është kjo? Kjo adresë është shprehur se çfarë simbol bazë, me sa duket? Kjo është hexadecimal, dhe çdo herë që ju të shihni një numër të filluar me 0x, kjo do të thotë heksadecimal, që ne e bëmë në mënyrë mbrapa në, unë mendoj se, seksioni pset 0 së pyetjeve, e cila ishte vetëm për të bërë një ushtrim warmup, konvertimin decimal në binar të magji dhe kështu me radhë. Hexadecimal, vetëm nga Konventa e njeriut, është përdorur zakonisht për të përfaqësuar pointers ose, më në përgjithësi, i drejtohet. Është vetëm një konventë, sepse kjo është pak më e lehtë për të lexuar, kjo është pak më kompakte se diçka si decimal, dhe binar është e padobishme për njerëzit më të përdorur. Deri tani çfarë do të thotë kjo? E pra, duket se nuk është një shkruaj pavlefshme e madhësisë 4 on line 21 të memory.c. Pra, le të kthehemi në linjë 21, dhe në të vërtetë, këtu është se shkruaj pavlefshme. Pra Shprehje nuk do të plotësisht të mbajë dorën time dhe më tregoni se çfarë është fix, por ajo është zbulimin që unë jam duke bërë një shkruani pavlefshme. Unë jam prekja 4 bytes që unë nuk duhet të jetë, dhe me sa duket kjo është për shkak se, si ju vuri në dukje, unë jam duke bërë [10] në vend të [9] maksimalisht ose [0] apo diçka në mes. Me Shprehje, të kuptojë çdo kohë që ju jeni tani një program me shkrim që përdor pointers dhe përdor memorie, dhe malloc më konkretisht, patjetër merrni në zakonin e running këtë kohë por shumë lehtë kopjohet dhe të ngjit komandën e Shprehje për të parë nëse ka disa gabime në atje. Dhe kjo do të jetë e madhe çdo herë që ju shihni e prodhimit, por vetëm me anë të analizimit të vizualisht gjithë prodhimit dhe të shohim nëse ju shihni përmend e gabimeve ose paralajmërime ose pavlefshme ose humbur. Çdo fjalë që të tingëllojë si ju dehur deri diku. Pra, të kuptojnë se është një mjet i ri në veglën tuaj. Tani të hënën, kemi pasur një bandë e tërë e folks të vijnë deri këtu dhe përfaqësojnë idenë e një listë e lidhur. Dhe ne kemi prezantuar listën e lidhur si një zgjidhje për atë problem? Po? [Student përgjigje, pakuptueshëm] Mirë. Vargjeve nuk mund të ketë memorie shtuar për ta. Nëse ju akordojë një rrjet të madhësisë 10, që është e gjitha që ju merrni. Ju mund të telefononi një funksion si realloc nëse ju fillimisht e quajti malloc, dhe që mund të përpiquni të rritet array nëse nuk ka hapësirë ​​në drejtim të përfundimit të saj që askush tjetër nuk është duke përdorur, dhe nëse nuk është, ai thjesht do të gjeni ju një copë të madhe diku tjetër. Por pastaj ajo do të kopje të të gjitha atyre bytes në rrjet të ri. Kjo tingëllon si një zgjidhje shumë të saktë. Pse është kjo e shëmtuar? Unë do të thotë ajo punon, njerëzit kanë zgjidhur këtë problem. Pse ne kemi nevojë për të zgjidhur atë në hënën me listat e lidhura? Po? [Student përgjigje, pakuptueshëm] Ajo mund të marrë një kohë të gjatë. Në fakt, çdo kohë që ju jeni duke bërë thirrje malloc ose realloc ose calloc, e cila është ende një tjetër, çdo herë që, Programi, po flasim për sistemin operativ, ju kanë tendencë për të ngadalësuar programin poshtë. Dhe në qoftë se ju jeni duke bërë këto llojet e gjërave në sythe, ju jeni me të vërtetë ngadalësuar gjëra poshtë. Ju nuk do të vini re këtë për të thjeshtë të "Hello World" programe të tipit, por në programe shumë të mëdha, duke i kërkuar të sistemit operativ përsëri dhe përsëri për kujtesën ose duke i dhënë atë përsëri dhe përsëri tenton të mos jetë një gjë e mirë. Plus, kjo është vetëm lloj i intelektualisht - kjo është një humbje e plotë e kohës. Pse ndajë më shumë memorie dhe më shumë, rrezikun e kopjimit gjithçka në grup të ri, në qoftë se ju keni një alternativë që ju lejon të kujtesës vetëm sa më shumë që ju duhet të vërtetë? Kështu që nuk ka pluses dhe minuses në këtu. Një nga pluses tani është se ne kemi dinamizëm. Nuk ka rëndësi ku chunks e kujtesës janë se janë të lirë, Unë vetëm mund të lloj të krijuar këto crumbs bukë nëpërmjet pointers të vargut të tërë listën time të lidhur së bashku. Por kam paguani të paktën një çmim. Çfarë duhet të heqin dorë në fitimin e listave të lidhura? Po? [Student përgjigje, pakuptueshëm] Mirë. Ju duhet më shumë memorie. Tani kam nevojë për hapësirë ​​për këto pointers, dhe në rastin e kësaj liste super të thjeshtë lidhur që është vetëm duke u përpjekur për të ruajtur integers, të cilat janë 4 bytes, ne kemi mbajtur duke thënë se mirë, një akrep është 4 bytes, kështu që tani unë kam dyfishuar fjalë për fjalë Shuma e kujtesës Unë kam nevojë vetëm për të ruajtur këtë listë. Por përsëri, kjo është një tradeoff vazhdueshme në shkenca kompjuterike mes kohës dhe hapësirës dhe, zhvillimit përpjekje dhe burime të tjera. Çfarë është një tjetër downside për të përdorur një listë e lidhur? Po? [Student përgjigje, pakuptueshëm] Mirë. Jo aq e lehtë për qasje. Ne nuk mund të levave Javën 0 parimet si përça dhe sundo. Dhe më konkretisht, kërko binar. Sepse edhe pse ne njerëzit mund të shihni se ku përafërsisht mes të kësaj liste është, kompjuter vetëm e di se kjo listë e lidhur fillon në adresën quajtur parë. Dhe kjo është 0x123 ose diçka të tillë. Dhe e vetmja mënyrë programi mund të gjeni element mesme është që në fakt të kërkuar listën e tërë. Dhe madje edhe atëherë, ai ka për të kërkuar fjalë për fjalë krejt Listen sepse edhe pasi të keni arritur elementin e mesme duke ndjekur pointers, ju, programi, nuk kanë asnjë ide se sa kohë kjo listë është, potencialisht, derisa ju goditi në fund të saj, dhe si nuk e dini programatikisht se ju jeni në fund të një liste të lidhur? Ka një tregues të veçantë NULL, kështu që përsëri, një konventë. Në vend se të përdorin këtë tregues, ne definitivisht nuk dua që ajo të jetë disa vlera plehrash duke treguar off fazë diku, ne duam që ajo të jetë me dorë poshtë, NULL, kështu që ne kemi këtë Terminus në këtë strukturë të dhënave kështu që ne e dimë se ku mbaron. Çfarë ndodh nëse ne duam të manipuluar këtë? Ne e bëmë më të madhe të këtij vizualisht, dhe me njerëzit, por ajo në qoftë se ne duam të bëjmë një shtënie? Pra, lista origjinale ishte 9, 17, 20, 22, 29, 34. Çfarë ndodh nëse ne të kërkuar për të, atëherë hapësirë ​​malloc për numrin 55, një nyje për të, dhe pastaj ne duam të futur në listën e 55 ashtu siç bëmë të hënën? Si e bëjmë këtë? E pra, Anita erdhi dhe ajo ecte në thelb të listës. Ajo filloi në elementin e parë, pastaj tjetër, tjetër, tjetër, tjetër, tjetër. Në fund goditi majtë të dorës të gjithë rrugën poshtë dhe realizuar oh, kjo është NULL. Pra, çfarë manipulimi tregues të nevojshme për të bërë? Personi që ishte në fund të fundit, numri 34, të nevojshme dora e tij e majtë ngritur për pikë në 55, 55 e nevojshme krahun e tyre të majtë duke treguar deri në jetë të re NULL Terminator. Bërë. Goxha e lehtë për të futur në një listë 55 renditura. Dhe si mund të duket kjo? Më lejoni të shkoj përpara dhe të hapin disa shembuj kodin këtu. Unë do të hapur deri Gedit, dhe më lejoni të hapur dy fotografi të parë. Njëra është list1.h, dhe më lejoni të kujtoj vetëm se kjo ishte copë e kodit që kemi përdorur për të përfaqësuar një nyje. Një nyjë ka si një int n quajtur dhe një tregues tjetër që quhet vetëm pikë për gjë tjetër në listë. Kjo është tani në një skedar. H. Pse? Nuk është kjo konventë, dhe ne nuk kemi marrë përfituar nga ky një sasi të madhe veten, por personi i cili shkroi funksionet printf dhe të tjera dha si një dhuratë për botën e të gjitha këtyre funksioneve duke shkruar një skedar të quajtur stdio.h. Dhe pastaj nuk ka string, dhe pastaj ka map.h, dhe ka të gjitha këto fotografi h që ju mund të keni parë ose të përdoren gjatë afatit shkruar nga njerëzit e tjerë. Zakonisht në ato. Fotografi h janë të vetmet gjëra të tilla si typedefs ose deklaratat e llojeve me porosi apo deklaratave të kosntanta. Ju nuk vënë Implementimi Funksionet 'në fotografi header. Ju vënë, në vend, vetëm prototypes e tyre. Ju vënë gjërat që ju doni të ndajnë me botën çfarë ata kanë nevojë në mënyrë që të hartojë kodin e tyre. Pra, vetëm për të marrë në këtë zakon, ne kemi vendosur për të bërë të njëjtën gjë. Nuk është shumë në list1.h, por ne kemi vënë diçka që mund të jetë me interes për njerëzit në botë që doni të përdorni të lidhur implementimin tonë list. Tani, në list1.c, unë nuk do të kalojnë nëpër këtë gjë të gjithë sepse kjo është pak e gjatë, ky program, por le të kandidojë atë të vërtetë më shpejt në ftim. Më lejoni të përpilojnë Lista1, më lejoni atëherë të drejtuar Lista1, dhe atë që ju do të shihni është ne kemi një program të thjeshtë simuluar pak këtu që do të më lejoni të shtoni dhe hiqni numrat në një listë. Pra më lejoni të shkoj përpara dhe të shtypni 3 për 3 menu option. Unë dua të futur numrin - le të bëjë numri i parë, i cili ishte 9, dhe tani unë jam i tha lista është tani 9. Më lejoni të shkojnë përpara dhe të bëjë një tjetër shtënie, kështu që unë goditi menu option 3. Çfarë numri dua të futur? 17. Enter. Dhe unë do të bëj vetëm një më shumë. Më lejoni të futur numrin 22. Kështu që ne kemi fillimet e listës lidhur që kemi pasur në formë diapozitivësh një moment më parë. Si është kjo futje në të vërtetë ndodh? Në të vërtetë, 22 është tani në fund të listës. Pra, histori kemi thënë në skenë të hënën dhe recapped vetëm tani duhet të jetë në fakt ndodh në kod. Le të marrin një sy. Më lejoni të lëvizni poshtë në këtë file. Ne do të komentoj mbi disa prej funksioneve, por ne do të shkojnë poshtë për të, të themi, funksioni insert. Le të shohim se si ne do të shkojmë për të futur një nyje të re në këtë listë e lidhur. Ku është lista e deklaruar? E pra, le të shkoni të gjithë rrugën deri në majë, dhe vini re se lista ime e lidhur në thelb është shpallur si një tregues të vetëm që është fillimisht NULL. Kështu që unë jam duke përdorur një ndryshore globale këtu, të cilat në përgjithësi ne kemi predikuar kundër sepse ai e bën kodin tuaj një çrregullt pak për të ruajtur, kjo është lloj i dembel, zakonisht, por kjo nuk është dembel dhe nuk është e gabuar dhe kjo nuk është e keqe në qoftë se qëllimi i vetëm programi juaj në jetë është që të simulojnë një listë të lidhura. E cila është pikërisht ajo që ne jemi duke bërë. Pra, në vend se të deklarojë këtë në kryesore dhe pastaj duhet të kalojë atë për çdo funksion ne kemi shkruar në këtë program, ne vend realizuar oh, le të vetëm të bëjë atë globale sepse tërë qëllimi i këtij programi është të tregojë një dhe vetëm një listë e lidhur. Kështu që ndihet në rregull. Këtu janë prototipa e mi, dhe ne nuk do të kalojnë nëpër të gjitha këto, por kam shkruar një funksion të fshini, një gjeni funksion, një funksion insert, dhe një funksion kundërvënie. Por le të kthehemi tani poshtë në funksion futur dhe shikoni se si ky punon këtu. Insert është në linjë - këtu ne do të shkojmë. Fut. Pra, ajo nuk ka marrë ndonjë argumente, sepse ne jemi duke shkuar për të kërkuar brenda përdoruesit e këtij funksioni për numrin që ata duan për të futur. Por së pari, ne kemi përgatitur për t'i dhënë atyre një hapësirë. Kjo është lloj i të kopjoni dhe ngjisni nga shembull tjetër. Në këtë rast, ne kemi qenë të ndarjes së një int, këtë herë ne jemi caktimin e një nyje. Unë vërtetë nuk e mbani mend se sa bytes një nyje është, por kjo është në rregull. Sizeof mund të kuptoj se për mua. Dhe pse jam unë duke kontrolluar for null 120 në linjë? Çfarë mund të shkojnë keq në linjë 119? Po? [Student përgjigje, pakuptueshëm] Mirë. Vetëm mund të jetë rasti që unë kam kërkuar për memorie shumë apo diçka të gabuar dhe sistemi operativ nuk ka bytes mjaftueshme për të dhënë mua, kështu që sinjalizon sa më shumë duke u kthyer NULL, dhe në qoftë se unë nuk shikoni për atë dhe unë vetëm verbërisht të vazhdojë të përdorë adresën kthye, ajo mund të jetë NULL. Kjo mund të jetë disa vlera të panjohura, nuk është një gjë e mirë nëse unë - në fakt nuk do të jetë një vlerë të panjohur. Kjo mund të jetë NULL, kështu që unë nuk dua të abuzimit atë dhe rrezikojnë dereferencing atë. Nëse kjo ndodh, unë vetëm të kthehet dhe ne do të pretendojë si unë nuk e kam marrë përsëri ndonjë memorie në të gjitha. Përndryshe, unë them përdoruesit të më jepni një numër për të futur, unë e quaj të vjetër GetInt tonë mik, dhe pastaj kjo ishte Sintaksa e re ne kemi prezantuar të hënën. 'Newptr-> n' do të thotë të marrë adresën që ju janë dhënë nga malloc e cila përfaqëson bajt e parë të një objekti të ri nyjen, dhe pastaj të shkojnë në fushën e quajtur n. Një pyetje pak Trivia: Kjo është ekuivalente me atë vijë më të fshehtë të kodit? Si tjetër mund ta ketë shkruar këtë? Dëshironi të marrë një goditje me thikë? [Student përgjigje, pakuptueshëm] Mirë. Duke përdorur. N, por kjo nuk është aq e thjeshtë si kjo. Çfarë së pari duhet të bëni? [Student përgjigje, pakuptueshëm] Mirë. Unë kam nevojë për të bërë * newptr.n. Pra, kjo është thënë treguesin e re është padyshim një adresë. Pse? Sepse ajo u kthye nga malloc. Newptr * duke thënë se "të shkuar atje", dhe pastaj një herë ju jeni atje, atëherë ju mund të përdorni më të njohur., n por kjo vetëm duket pak e shëmtuar, sidomos nëse ne njerëzit do të barazim pointers me shigjeta gjithë kohës, bota ka standardizuar në këtë simbol shigjete, e cila e bën të njëjtën gjë. Pra, ju vetëm përdorni simbol -> kur gjë në të majtë është një akrep. Përndryshe, në qoftë se ajo është një struct aktuale, përdorni. N. Dhe pastaj kjo: Pse nisja newptr-> ardhshme për NULL? Ne nuk duam një dorë e majtë varur jashtë e në fund të fazës së. Ne duam të treguar drejt poshtë, që do të thotë në fund të kësaj liste mund të jetë potencialisht në këtë nyje, kështu që ne më mirë të sigurt se është NULL. Dhe, në përgjithësi, Initializing variablave tuaj ose anëtarët e të dhënave tuaja dhe structs diçka është vetëm praktikë e mirë. Vetëm lënë mbeturina ekzistojnë dhe vazhdojnë të ekzistojnë në përgjithësi ju merr në telashe në qoftë se ju harroni të bëni diçka më vonë. Ja disa raste. Kjo, përsëri, është funksioni insert, dhe gjëja e parë që unë kontrolloni për të është nëse ndryshueshme quhet parë, se ndryshueshme globale është NULL, që do të thotë nuk ka asnjë listë të lidhura. Ne nuk kemi futur ndonjë numër, kështu që është i parëndësishëm për të futur këtë numër e tanishme në listë, sepse kjo i takon vetëm në fillim të listës. Pra, kjo ishte kur Anita ishte vetëm duke qëndruar deri këtu vetëm, duke pretenduar askush tjetër nuk ishte deri këtu në skenë deri ne ndarë një nyje, atëherë ajo mund të ngrejë dorën e saj për herë të parë, në qoftë se të gjithë të tjerët kishin ardhur deri në fazën e pas saj të hënën. Tani këtu, kjo është një kontroll pak ku unë duhet të them, nëse vlera nyjen ri i n është e ardhshëm, që do të thotë të shkojnë në struct që është duke u vuri në duke newptr, kështu që këtu ne jemi, shkoni atje. Pastaj arrow është thënë merrni fushë tjetër, dhe pastaj = është thënë vënë atë vlerë ka? Vlera që ishte në të parë, atë vlerë ka qenë në vend të parë? Parë ishte vënë në këtë nyje, kështu që do të thotë kjo tani duhet të tregojnë në këtë nyje. Me fjalë të tjera, ajo duket megjithëse një rrëmujë qesharake me dorëshkrimit tim, çfarë është një ide e thjeshtë e vetëm lëvizin këto shigjeta përreth përkthehet në kodin me vetëm një astar këtë. Shitore atë që është e para në fushën e ardhshme dhe pastaj përditësimin atë që në fakt është parë. Le të shkojnë përpara dhe të shpejtë përpara përmes disa të kësaj, dhe të kërkoni vetëm në këtë futje bisht tani për tani. Mendoj unë shkoj në pikën ku unë të gjeni se fusha e ardhshme e disa nyjeve është NULL. Dhe në këtë pikë në histori, një detaj që unë jam Glossing mbi është se unë kam futur një tjetër tregues deri këtu në linjë 142, akrep paraardhësit. Në thelb, në këtë moment në histori, pasi lista e merr gjatë, Unë lloj i duhet të ecin me dy gishta sepse nëse unë shkoj shumë larg, kujtohet në një listë të vetme-gjatësi, ju nuk mund të shkoni prapa. Pra, kjo ide e predptr është gishti im majtë, dhe newptr - nuk newptr. Një tjetër tregues që është këtu është gishti im tjetër, dhe unë jam vetëm lloj ecin në listë. Kjo është arsyeja pse që ekziston. Por le të marrim parasysh vetëm një nga rastet më të thjeshta këtu. Nëse fushë tjetër që akrep është NULL, çfarë është implikimi logjik? Nëse jeni duke traversing këtë listë dhe ju goditi një tregues NULL? Ju jeni në fund të listës, dhe kështu kodi që pastaj append këtë element të një shtesë është lloj i intuitiv do të marrë atë nyje të cilit është NULL pointer tjetër, kështu që kjo është aktualisht NULL, dhe për të ndryshuar atë, edhe pse, të jetë adresa e nyjeve të reja. Pra, ne jemi vetëm duke tërhequr në kodin arrow që tërhoqi në skenë duke ngritur dorën e majtë dikujt. Dhe rasti që unë do të tundë duart e mia në për tani, vetëm për shkak se unë mendoj se është e lehtë për të marrë humbur kur ne bëjmë atë në këtë lloj të mjedisit, është kontrolluar për futje në mes të listës së. Por vetëm intuitive, ajo që duhet të ndodhë në qoftë se ju doni të kuptoj se ku disa numri i takon në mes është që ju nuk duhet të ecin atë me më shumë se një gisht, më shumë se një akrep, kuptoj se ku ajo i takon duke kontrolluar është elementi Një aktuale, dhe sapo ju të gjeni atë vend, atëherë ju duhet të bëni këtë lloj të lojës shell ku ju lëvizin nëpër pointers shumë kujdes. Dhe kjo përgjigje, në qoftë se ju do të donte për arsye përmes kësaj në shtëpi në tuaj, boils poshtë vetëm për këto dy rreshta të kodit, por renditja e këtyre linjave është super i rëndësishëm. Sepse në qoftë se ju bie dorën e dikujt dhe për të rritur dikush tjetër është në mënyrë të gabuar, përsëri, ju mund të përfundojë orphaning listën. Për të përmbledhur shumë konceptualisht, futja në bisht është relativisht e thjeshtë. Futja në krye është gjithashtu relativisht i drejtpërdrejtë, por ju duhet për të rinovuar një treguesin e shumta këtë kohë të shtrydh numrin 5 në listën këtu, dhe pastaj futje në mes përfshin edhe më shumë përpjekje, me shumë kujdes futur numrin 20 në vendin e tij të saktë, cila është ndërmjet 17 dhe 22. Kështu që ju duhet të bëni diçka si duhet e re 20 pikë nyje të 22, dhe pastaj, akrep i cili nyje ka nevojë të përmirësohet fundit? Kjo është 17, që në fakt futur atë. Pra, përsëri, unë do të shtyjë kodin aktual për atë zbatimit të veçantë. Në shikim të parë, kjo është pak e madhe, por kjo është me të vërtetë vetëm një lak pafund që është looping, looping, looping, looping, dhe thyerjen sa më shpejt që ju goditi treguesin NULL, në të cilën pikë ju mund të bëni futjen e nevojshme. Kjo, pra, është përfaqësuesi i lidhur futje lista kodin. Kjo ishte një lloj shumë, dhe ajo ndjehet si e kemi zgjidhur një problem, por ne kemi prezantuar një të tërë të tjera. Sinqerisht, ne kemi shpenzuar të gjithë kohën këtë on Big O dhe Ω dhe drejtimin kohë, duke u përpjekur për të zgjidhur problemet më shpejt, dhe këtu ne jemi duke marrë një hap të madh prapa, ai ndjen. Dhe akoma, në qoftë se qëllimi është për të ruajtur të dhënat, ajo ndihet si Grail Shenjtë, siç kemi thënë të hënën, do të jetë me të vërtetë për të ruajtur gjërat menjëherë. Në fakt, mendoj se kemi bërë listën vënë mënjanë për të lidhur një moment dhe ne vend paraqiti idenë e një tavolinë. Dhe le të vetëm të mendojnë për një tavolinë për një moment si një grup. Ky grup dhe ky rast këtu ka disa elemente, 26 25, përmes 0 dhe mendoj se ju nevojitet një copë e magazinimit për emrat: Alice dhe Bob dhe Charlie dhe si. Dhe keni nevojë për disa strukturën e të dhënave për të ruajtur ato emra. E pra, ju mund të përdorni diçka si një listë të lidhur dhe ju mund të ecin në listën futur Alice para Bob Bob dhe Charlie pas dhe kështu me radhë. Dhe, në fakt, në qoftë se ju doni të shihni kodin si kjo si një mënjanë, e di se në list2.h, ne bëjmë pikërisht këtë. Ne nuk do të shkojnë përmes këtij kodi, por kjo është një variant i shembullin e parë që paraqet një struct tjetër ne kemi parë më parë, student i quajtur dhe pastaj atë që në të vërtetë ruan në listën e lidhur është një tregues për një strukturë të studentëve më tepër se një numër i plotë thjeshtë pak, n. Pra, të kuptojnë se ka kodi atje që përfshin strings aktuale, por në qoftë se qëllimi në dorë me të vërtetë tani është për të adresuar problemin e efikasitetit, nuk do të jetë mirë në qoftë se ne jemi duke i dhënë një objekt quajtur Alice, ne duam të vënë atë në vendin e duhur në strukturën e të dhënave, ai ndjehet si ajo do të jetë me të vërtetë e bukur për të vetëm të vënë Alice, cilit Emri fillon me A, në vend të parë. Dhe Bob, cilit Emri fillon me B, në vend të dytë. Me një grup, ose le të fillojnë duke e quajtur atë një tavolinë, një tavolinë hash në atë, ne mund të bëjmë pikërisht këtë. Nëse ne jemi të dhënë një emër si Alice, një varg si Alice, ku ju vendosni një-l-i-c-E? Ne kemi nevojë për një hueristic. Ne kemi nevojë për një funksion për të marrë disa të dhëna si Alice dhe të kthehet një përgjigje, "Vendos Alice në këtë vend." Dhe ky funksion, kjo kuti e zezë, do të quhet një funksion hash. Një funksion hash është diçka që merr një kontribut, si "Alice", dhe kthimit për ju, në mënyrë tipike, vendndodhja numerike në disa struktura të dhënave, ku Alice takon. Në këtë rast, funksioni ynë hash duhet të jetë relativisht e thjeshtë. Funksioni ynë hash duhet të them, nëse ju janë dhënë "Alice", i cili karakteri duhet të cilët brengoseni? I pari. Kështu që unë shoh në [0], dhe pastaj unë them, nëse [0] karakter është Një, kthehen numrin 0. Nëse kjo është B, kthehen 1. Nëse është e C, 2 të kthehen, dhe kështu me radhë. Të gjitha 0 indeksi, dhe që do të më lejoni të futur Alice dhe pastaj BOB dhe pastaj Charlie dhe kështu me radhë në këtë strukturë të dhëna. Por ka një problem. Çfarë ndodh nëse Anita vjen së bashku përsëri? Ku nuk kemi vënë Anit? Emri i saj, gjithashtu, fillon me shkronjën A, dhe ai ndjehet si ne kemi bërë një rrëmujë edhe më të mëdha të këtij problemi. Ne tani e kemi futje të menjëhershme, futje e vazhdueshme koha, në strukturën e të dhënave jo keq rast-lineare, por çfarë mund të bëjmë me Anita në këtë rast? Cilat janë dy opsione, me të vërtetë? Po? [Student përgjigje, pakuptueshëm] Mirë, kështu që ne mund të kemi një tjetër dimension. Kjo është e mirë. Kështu që ne mund të ndërtojmë gjëra në 3D si kemi biseduar për gojë të hënën. Ne mund të shtoni një tjetër qasje këtu, por mendoj se jo, unë jam duke u përpjekur për të mbajtur këtë të thjeshtë. Qëllimi këtu është që të gjithë të kenë qasje të menjëhershme konstante në kohë, kështu që është shtuar kompleksitetin shumë. Cilat janë opsionet e tjera, kur duke u përpjekur për të futur në këtë Anita strukturën e të dhënave? Po? [Student përgjigje, pakuptueshëm] Mirë. Kështu që ne mund të lëvizin të gjithë të tjerët poshtë, si Charlie nudges poshtë Bob dhe Alice, dhe pastaj ne kemi vënë Anit, ku ajo me të vërtetë dëshiron të jetë. Sigurisht, tani, ka një efekt anësor i kësaj. Kjo strukturë dhënave është ndoshta e dobishme jo sepse ne duam të futur njerëzit herë por për shkak se ne duam të kontrolloni nëse ata janë atje më vonë në qoftë se ne duam të shtypura nga të gjitha emrat në strukturën e të dhënave. Ne jemi duke shkuar për të bërë diçka me këto të dhëna eventualisht. Kështu që tani ne kemi lloj të dehur mbi Alice, i cili nuk është më, ku ajo është menduar të jetë. As Bob, as nuk është Charlie. Pra, ndoshta kjo nuk është e tillë një ide e mirë. Por në të vërtetë, kjo është një opsion. Ne mund të zhvendoset të gjithë poshtë, apo dreq, Anita erdhi vonë në lojë, pse nuk kemi vetëm vënë Anit nuk është këtu, nuk është këtu, nuk është këtu, le të vetëm vënë atë pak më e ulët në listë. Por pastaj ky problem fillon të zhvilloheshin përsëri. Ju mund të jetë në gjendje për të gjetur çast Alice, bazuar në emrin e saj të parë. Dhe Bob në çast, dhe Charlie. Por pastaj ju shikoni për Anita, dhe ju shihni, hmm, Alice është në rrugë të drejtë. E pra, më lejoni të kontrolloni më poshtë Alice. Bob nuk është Anita. Charlie nuk është Anita. Oh, nuk është Anita. Dhe në qoftë se ju vazhdoni që stërviten e logjikës të gjithë rrugën, çfarë është keq rasti Ora drejtimin e gjetjes ose futur Anit në këtë strukturë të dhëna të reja? Kjo është O (n), apo jo? Sepse në rastin më të keq, nuk është Alice, Bob, Charlie. . . të gjithë rrugën poshtë për dikë të quajtur "Y", kështu që nuk është vetëm një vend i mbetur. Fatmirësisht, ne nuk kemi një të quajtur "Z", kështu që ne kemi vënë Anit në fund shumë. Ne nuk kemi zgjidhur atë problem të vërtetë. Pra, ndoshta ne kemi nevojë për të prezantuar këtë dimension të tretë. Dhe kjo rezulton, në qoftë se ne do të prezantoj këtë dimension të tretë, ne nuk mund ta bëjë këtë të përkryer, por Grail Shenjtë do të bëhet konstante në kohë futje dhe insertions dinamike në mënyrë që ne nuk kemi të vështirë-kodi një grup të madhësisë 26. Ne mund të futni sa shumë emra si ne duam, por le të marrin 5-minutësh pushim tonë këtu dhe pastaj të bëjë atë siç duhet. Dakord. I vendosur deri goxha histori artificialisht atje duke zgjedhur Alice dhe pastaj BOB dhe pastaj Charlie dhe pastaj Anita, emri i të cilit ishte padyshim do të përplasen me Alice. Por pyetja ne përfundoi të hënën me të është se sa e mundshme është ajo që ju do të merrni këto lloje e perplasjeve? Me fjalë të tjera, në qoftë se ne të fillojnë të përdorin këtë strukturë tabelore, e cila është me të vërtetë vetëm një grup, në këtë rast 26 vende, çfarë nëse inputet tona janë të shpërndara në mënyrë uniforme në vend? Kjo nuk është artificialisht Alice dhe Bob dhe Charlie dhe Davidi dhe kështu me radhë alfabetike, kjo është shpërndarë uniformisht gjatë një anë Z. Ndoshta ne vetëm do të merrni me fat dhe ne nuk do të kemi dy Një ose të dy së ​​B me probabilitet shumë të lartë, por si dikush vuri në dukje, në qoftë se ne e pergjithshme ky problem dhe të mos bëjë 0-25 por, të themi, 0 deri 364 ose 65, shpesh numri i ditëve në një vit tipik, dhe i kërkoi pyetjen, "Çfarë është probabiliteti që dy prej nesh në këtë sallë kanë të njëjtën ditëlindje?" Vënë atë një mënyrë tjetër, çfarë është probabiliteti që dy prej nesh kanë një emër duke filluar me A? Lloj i pyetjes është i njëjtë, por kjo hapësirë ​​adresa, kjo hapësirë ​​kërko, është më e madhe në rastin e ditëlindje, sepse ne kemi ditë kaq shumë më shumë sesa në vitin e shkronjave në alfabet. Çfarë është mundësia e një përplasjeje? E pra, ne mund të mendoj për këtë duke parafytyruar se matematikë në drejtim të kundërt. Çfarë është probabiliteti i pa perplasjeve? E pra, kjo shprehje këtu thotë se çfarë është probabiliteti në qoftë se ka vetëm një person në këtë dhomë, se ata kanë një ditëlindje të veçantë? Kjo është 100%. Sepse në qoftë se ka vetëm një person në dhomë, tij ose ditëlindjen saj mund të jetë ndonjë prej 365 ditëve nga vit. Pra opsione 365/365 më jep një vlerë prej 1. Pra probabiliteti në fjalë për momentin është vetëm 1. Por në qoftë se ka një person të dytë në dhomë, çfarë është probabiliteti që ditëlindjen e tyre është e ndryshme? Nuk është vetëm 364 ditë të mundshme, duke injoruar vjet brishtë, për ditëlindjen e tyre të mos bien ndesh me persona të tjerë. Pra 364/365. Nëse një person i tretë vjen në, kjo është 363/365, dhe kështu me radhë. Pra, ne kemi mbajtur shumëzuar bashku këto fraksionet, të cilat janë duke u vogla dhe të vogla, të kuptoj se çfarë është probabiliteti që të gjithë prej nesh kanë ditëlindje të veçantë? Por atëherë ne mund të, natyrisht, vetëm të marrë atë përgjigje dhe rrokullisje atë rreth dhe të bëjë 1 minus të gjithë se, një shprehje që ne përfundimisht do të merrni nëse ju kujtohet e prapme të librave tuaja matematikë, kjo duket një diçka të vogël si kjo, e cila është shumë më e lehtë të interpretohet grafikisht. Dhe ky grafik këtu ka në boshtin x numrin e ditëlindje, ose numri i njerëzve me ditëlindje, dhe mbi boshtin y është probabiliteti i një ndeshje. Dhe kjo është ajo që është thënë se në qoftë se ju keni, le të themi, madje, le të zgjedhin diçka si 22, 23. Nëse ka 22 ose 23 njerëz në dhomë, probabiliteti që dy prej atyre shumë pak njerëz do të kenë të njëjtën ditëlindje është në të vërtetë të lartë super, combinatorially. 50% shanset që në një klasë prej vetëm 22 njerëz, një seminar, praktikisht, 2 prej këtyre njerëzve do të kenë të njëjtën ditëlindje. Sepse ka kaq shumë mënyra në të cilat ju mund të keni të njëjtën ditëlindje. Edhe më keq, në qoftë se ju shikoni në anën e djathtë të tabelës, nga koha që ju keni një klasë me 58 studentë në të, probabiliteti i 2 persona të paturit e një ditëlindjen është super, super të lartë, gati 100%. Tani, kjo është lloj i një fakti fun në lidhje me jetën reale. Por implikimet, tani, për strukturat e të dhënave dhe informacionit ruajtjen do të thotë se vetëm duke supozuar që ju keni një të bukur, të pastër, shpërndarjen uniforme të të dhënave dhe ju keni një koleksion të madh të mjaftueshme për të përshtaten një bandë e gjëra nuk do të thotë që ju jeni duke shkuar për të marrë njerëz në vende unike. Ju jeni do të ketë goditjet. Pra ky nocion i hashing, siç është quajtur, marrë një kontribut si "Alice" dhe fërkoni atë në një farë mënyre dhe pastaj marrjen mbrapa një përgjigje si 0 ose 1 ose 2. Getting back disa dalje nga këtë funksion është rrënuar nga ky probabilitet të goditjes. Pra, si mund të kemi trajtuar ato goditjet? E pra, në një rast, ne mund të marrim idenë që ishte sugjeruar. Ne vetëm mund të zhvendoset të gjithë poshtë, ose ndoshta, pak më thjesht, në vend se të gjithë veprim tjetër, le të vetëm të lëvizë Anit në fund të vend në dispozicion. Kështu nëse Alice është në 0, Bob është në 1, Charlie është në 2, ne vetëm do të vënë në vend Anit 3. Dhe kjo është një teknikë në strukturat e të dhënave të quajtur lineare probing. Lineare sepse ju jeni vetëm në këmbë këtë linjë, dhe ju jeni lloj i probing për spote në dispozicion në strukturën e të dhënave. Sigurisht, kjo bie në O (n). Nëse struktura të dhënave me të vërtetë të plotë, nuk ka 25 njerëz në atë tashmë, dhe pastaj Anita vjen së bashku, ajo përfundon deri në çfarë do të jetë lokacioni Z, dhe kjo është në rregull. Ajo ende i përshtatet, dhe ne mund të gjeni atë më vonë. Por kjo ishte në kundërshtim me qëllimin e shpejtimin gjërat. Pra, çfarë nëse ne vend futur këtë dimension të tretë? Kjo teknikë është quajtur përgjithësisht chaining të veçantë, ose të kenë zinxhirë. Dhe çfarë një tabelë hash tani është, kjo strukturë tabelore, Tabela e juaj është vetëm një grup i pointers. Por ajo që ata tregojnë për pointers është me mend se çfarë? Një listë e lidhur. Pra, çfarë nëse ne marrim më të mirë të të dyja këtyre botëve? Ne përdorim vargjeve për indekset fillestare në strukturën e të dhënave kështu që ne mund të shkojnë në çast [0] [1], [30] apo kështu me radhë, por në mënyrë që të kemi një fleksibilitet dhe ne mund të përshtatet Anit dhe Alice dhe Adami dhe ndonjë tjetër Një emër, ne vend le aksi tjetër të rritet në mënyrë arbitrare. Dhe ne fund, nga e hëna, kanë atë aftësi ekspresive me lista të lidhura. Ne mund të rritet një strukturë të dhënave në mënyrë arbitrare. Nga ana tjetër, ne mund të bëjë vetëm një koleksion i madh 2-dimensionale, por që do të jetë një situatë e tmerrshme nëse dikush prej rreshtave në një rrjet të 2-dimensionale nuk është mjaft e madhe për personin shtesë emri i të cilit ndodh për të filluar me A. Zoti na ruajt, ne kemi për të rialokuar një strukturë të madhe 2-dimensionale vetëm për shkak se ka kaq shumë njerëz të quajtur Një, sidomos kur ka kaq pak quajtur diçka Z. Është vetëm do të jetë një shumë e rrallë të dhënave struktura. Pra, kjo nuk është e përsosur me çdo mjet, por tani ne të paktën të ketë aftësinë për të gjetur çast ku Alice apo Anita takon, të paktën në drejtim të aksit vertikal, dhe pastaj ne vetëm duhet të vendosë se ku për të vënë Anit ose Alice në këtë listë e lidhur. Nëse ne nuk e kujdesit për klasifikim gjëra, se sa shpejt mund të kemi futur Alice në një strukturë si kjo? Është koha konstante. Ne indeksi në [0], dhe nëse ka askujt, Alice shkon në fillim të kësaj liste të lidhura. Por kjo nuk është një marrëveshje e madhe. Sepse në qoftë se Anita pastaj vjen së bashku numrin e disa hapave më vonë, kur nuk Anita takon? E pra, [0]. OOP. Alice është tashmë në atë listë të lidhura. Por nëse ne nuk e kujdesit për klasifikim këto emra, Ne vetëm mund të lëvizin Alice gjatë, insert Anita, por edhe se është koha konstante. Edhe në qoftë se ka Alice dhe Adami dhe të gjitha këto emra të tjerë Një, kjo nuk është me të vërtetë shtyrë ato fizikisht. Pse? Sepse ne vetëm e bëri këtu me lista të lidhura, i cili e di po keto nyjet janë anyway? Të gjithë ju duhet të bëni është të lëvizur crumbs bukë. Leviz shigjeta përreth, ju nuk keni për të lëvizur fizikisht të dhëna rreth. Pra, ne mund të futur Anit, në këtë rast, në çast. Ora konstante. Pra, ne kemi të vazhdueshme në kohë lookup, dhe konstante në kohë futjen e dikujt si Anita. Por lloji i thjeshtëzuar botën. Çfarë ndodh nëse ne duam më vonë për të gjetur Alice? Çfarë ndodh nëse ne duam më vonë për të gjetur Alice? Sa hapa është se do të marrë? [Student përgjigje, pakuptueshëm] Saktësisht. Numri i njerëzve para Alice në listën e lidhur. Pra, kjo nuk është mjaft e përsosur, për shkak se struktura e të dhënave tona, përsëri, ka këtë qasje vertikale dhe pastaj ajo ka këto lista ndërlidhura varur - në fakt, le të mos tërheqë atë një një grup. Ajo ka këto lista të lidhura varur jashtë të saj që duket një diçka të vogël si kjo. Por problemi është nëse Alice dhe Adami dhe të gjitha këto emra të tjerë Një përfundojnë gjithnjë e më shumë atje, gjetjen e dikush mund të përfundojnë duke marrë një bandë e hapa, bcause ju duhet të kaloj nëpër listën e të lidhur, cila është një operacion linear. Kështu vërtetë, pastaj, koha futje përfundimisht është O (n), ku n është numri i elementeve në lista. Ndarë nga, le arbitrarisht thirrje ajo m, ku m është numri i listave lidhura që ne kemi në këtë aks vertikal. Me fjalë të tjera, nëse ne me të vërtetë të marrë një shpërndarje uniforme të emrave, tërësisht joreale. Ka padyshim më i disa letra se të tjerët. Por në qoftë se ne supozojmë për një moment shpërndarjes uniforme, dhe ne kemi njerëz n total, dhe zinxhirët m totale në dispozicion për ne, atëherë gjatësia e secilit prej këtyre zinxhirëve mjaft thjesht do të jetë i përgjithshëm, n ndarë me numrin e zinxhirëve. Pra, n / m. Por këtu është ajo ku ne mund të jetë mbi të gjitha matematikisht zgjuar. m është një konstante, sepse ka një numër të caktuar të këtyre. Ju do të jeni për të deklaruar array tuaj në fillim, dhe ne nuk jemi duke ndryshuar boshtin vertikal. Nga përkufizimi, që qëndron fikse. Kjo është vetëm aksi horizontal, kështu që të flasin, që është ndryshuar. Pra teknikisht, kjo është një konstante. Deri tani, koha futje është O goxha shumë (n). Kështu që nuk mendojnë të gjithë se shumë më mirë. Por ajo që është e vërteta këtu? E pra, të gjithë këtë kohë, për disa javë, ne kemi qenë duke thënë O (n ²). O (n), 2 x n ², - N, ndahet nga 2. . . ech. Është vetëm ² n. Por tani, në këtë pjesë të semestrit, ne mund të fillojmë të flasim në lidhje me botën e vërtetë përsëri. Dhe n / m është absolutisht më shpejt se vetëm n vetëm. Nëse ju keni një mijë emra, dhe ju thyejnë ato deri në kova të shumta kështu që ju keni vetëm dhjetë emra në secilën prej këtyre zinxhirëve, absolutisht në kërkim dhjetë gjëra do të jetë më shpejt se një mijë gjëra. Dhe kështu një nga grupe probleme ardhshme do të sfidojnë ty të mendojnë për saktësisht se edhe pse, vërtet, asymptotically dhe matematikisht, kjo është ende vetëm lineare, që sucks në përgjithësi, kur duke u përpjekur për të gjetur gjëra. Në realitet, ajo do të jetë më e shpejtë se ajo për shkak të këtij pjesëtues. Dhe kështu që nuk është sërish do të jetë në këtë tregti-off dhe ky konflikt në mes teorisë dhe realitetit, dhe një nga pullat do të fillojë kthyer në këtë pikë në semestrin është më e realitetit si ne një lloj i përgatitur për në fund semster-së, si ne futur botën e programimit web, ku me të vërtetë, performanca është duke shkuar për të numëruar, sepse përdoruesit tuaj do të fillojnë të ndjehen dhe të vlerësojmë vendime të varfër të projektimit. Deri sa ju shkoni në lidhje me zbatimin e një linked - një tabelë hash me 31 elemente? Dhe shembulli i mëparshëm ishte rreth arbitrare ditëlindje. Nëse dikush ka një ditëlindje të janarit 1 ose 1 shkurt, ne do të vënë ato në këtë kovë. Në qoftë se kjo është më 2 janar, shkurt 2, 2 mars, ne do të vënë ato në këtë kovë. Kjo është arsyeja pse ajo ishte 31. Si mund të deklarojë një tabelë hash? Ajo mund të jetë shumë e thjeshtë, tavolinë nyje * është emri im arbitrar për atë, [31]. Kjo më jep 31 pointers në nyjet, dhe që lejon mua që të ketë 31 pointers në listat e lidhura edhe në qoftë se ato janë zinxhirët fillimisht NULL. Çfarë unë dua të vënë në qoftë se unë dua të ruajtur "Alice", "Bob", "Charlie"? E pra, ne kemi nevojë për të përfunduar këto gjëra në një strukturë sepse ne kemi nevojë për pikë për të Alice Bob, që të tregojnë për Charlie, dhe kështu me radhë. Ne nuk mund të ketë vetëm emrat vetëm, kështu që unë mund të krijojë një strukturë të re të quajtur nyja këtu. Çfarë është një nyje e vërtetë? Çfarë është një nyje në këtë listë të re lidhur? Gjëja e parë, i quajtur fjalë, është për emrin e personit. LENGTH, me sa duket, lidhet me gjatësinë maksimale e emrit të një njeriut, çfarëdo që është, 20, 30, 40 karaktere në rastet qoshe çmendur, dhe 1 është për çfarë? Është vetëm karakter ekstra NULL, \ 0. Pra, kjo është nyja dhënë "diçka" brenda në vetvete, por ajo gjithashtu deklaron një tregues tjetër i quajtur kështu që ne mund të Bob zinxhir Alice për Charlie dhe kështu me radhë. Mund të jetë NULL, por nuk duhet të jetë domosdoshmërisht. Çdo pyetje në lidhje me këto tabela hash? Po? [Student i kërkuar pyetje, pakuptueshëm] Një array - pyetje e mirë. Pse është kjo fjalë char në një rrjet sesa vetëm * char? Në këtë shembull disi arbitrare, unë nuk dua të duhet të përdorë tek malloc për secilin nga emrat origjinal. Unë të kërkuar për të deklaruar një sasi maksimale e kujtesës për vargun kështu që unë mund të kopjoni në strukturën Alice \ 0 dhe nuk duhet të merren me malloc dhe të lirë dhe si. Por unë mund të bëjë që në qoftë se unë të kërkuar për të qenë më të vetëdijshëm për përdorimin e hapësirës. Mirë pyetje. Pra, le të përpiqemi për të përgjithësuar larg nga kjo dhe të përqëndrohet pjesën e mbetur të sotme në strukturat e të dhënave në përgjithësi dhe probleme të tjera që ne mund të zgjidhin duke përdorur bazat e njëjta edhe pse strukturat e të dhënave vetë mund të ndryshojnë në veçoritë e tyre. Pra, ajo rezulton në shkenca kompjuterike, pemët janë shumë të zakonshme. Dhe ju mund të mendoni për një lloj pemë të si një pemë familjare, ku ka disa rrënjë, disa matriarch apo patriark, gjyshe apo gjysh ose më herët mbrapa, nën të cilat janë nëna dhe baba ose motra të ndryshme ose të ngjashme. Pra, një strukturë pemë ka nyje dhe ajo ka fëmijë, zakonisht 0 ose më tepër fëmijë për çdo nyje. Dhe disa nga zhargon që ju shihni në këtë foto këtu është ndonjë nga fëmijët pak ose grandkids në skajet të cilët nuk kanë shigjetat që burojnë prej tyre, ato janë të ashtuquajturat gjethe, dhe kushdo në brendësi është një nyje e brendshme, ju mund të telefononi atë asgjë përgjatë këtyre linjave. Por kjo strukturë është shumë e zakonshme. Kjo është pak arbitrare. Ne kemi një fëmijë në të majtë, ne kemi tre fëmijë në të djathtë, dy fëmijë në fund u largua. Kështu që ne mund të kemi të ndryshme të mesme pemë, por në qoftë se ne fillojmë të standartizuar gjëra, dhe ju mund të kujtojnë këtë nga video Patrikut në kërkim binar nga një të shkurtër mëparshme online, kërko binar nuk duhet të zbatohet me një grup ose copa e letrës në një dërrasë e zezë. Supozoni se ju të kërkuar për të ruajtur numrat tuaj në një strukturë më të sofistikuar të të dhënave. Ju mund të krijoni një pemë si kjo. Ju mund të keni një nyje deklaruar në C, dhe se nyja mund të ketë të paktën dy elemente brenda të saj. Njëra është numri që ju dëshironi për të ruajtur, dhe të tjera është - mirë, ne kemi nevojë për një më shumë. Të tjera është fëmijët e saj. Kështu që këtu është një tjetër strukturë të dhënave. Këtë herë, një nyje është përcaktuar si ruajtjen e një numri n dhe pastaj dy pointers, fëmijë të majtë dhe të djathtë fëmijës. Dhe ata nuk janë arbitrare. Çfarë është interesante në lidhje me këtë pemë? Çfarë është model në mënyrën se si ne kemi hedhur këtë, apo si Patrick vuri atë në video e tij? Kjo është lloj i qartë se ka disa klasifikim duke shkuar në këtu, por ajo është rregull të thjeshtë? Po? [Student përgjigje, pakuptueshëm] Përsosur. Nëse jeni në këtë shikim, ju shihni numrat e vogla në të majtë, Numrat e mëdha në të majtë, por kjo është e vërtetë për çdo nyje. Për çdo nyje, fëmija i tij të majtë më pak se ajo, dhe fëmija e tij të drejtë më të madhe se ajo. Çfarë kjo do të thotë tani është në qoftë se unë dua të kërkuar këtë strukturë të dhënave për të, thonë, numrin 44, Unë duhet të fillojë në rrënjë, sepse me të gjitha këto struktura më komplekse të dhënave tani, ne kemi vetëm një tregues për një gjë, fillimi. Dhe në këtë rast, është fillimi rrënjë. Kjo nuk është fundi majtë, kjo është rrënja e kësaj strukture. Kështu që unë shoh këtu është 55, dhe unë jam duke kërkuar për 44. Cilin drejtim dua të shkoj? E pra, unë dua të shkoj në të majtë, sepse padyshim, në të djathtë do të jetë shumë i madh. Pra njoftim këtu, ju jeni lloj i konceptualisht shëndoshë pemë në gjysmën e sepse ju kurrë nuk do të jeni poshtë në anën e djathtë. Pra, tani unë po shkoj nga 55 në 33. Është shumë e vogël e një numri. Unë jam duke kërkuar për 44, por tani unë e di nëse është e 44 në këtë pema, unë mund të shkoni padyshim në të djathtë. Pra, përsëri, unë jam tëharrje pemë në gjysmë. Është shumë e shumë identike konceptualisht në librin e telefonit. Kjo është identike me atë që ne e bëmë me letrat në dërrasë e zezë, por kjo është një strukturë më të sofistikuar që na lejon të bëjë në fakt kjo përça dhe sundo nga hartimin e algorithm, dhe në fakt, traversing një strukturë të tillë - uh. Traversing një strukturë të tillë, ku vetëm "të shkojnë në këtë mënyrë apo të shkojë në këtë mënyrë," do të thotë të gjithë kodin që se Bent mendjen tuaj në fillim, kur zbatimin e saj në nenin ose në këmbë nëpër atë në shtëpi, për kërkimin binar, duke përdorur recursion apo përsëritje, kjo është një dhimbje në qafë. Gjej elementin e mesme, pastaj të bëjë arrestimi tuaj lart ose poshtë. Ka një bukuri për këtë, sepse ne tani mund të përdorni recursion përsëri, por shumë më pastër. Në të vërtetë, në qoftë se ju jeni në numrin 55 dhe ju doni të gjeni 44, ju shkoni la në këtë rast, atëherë çfarë do të bëni? Ju drejtuar algorithm saktë të njëjtën. Ju kontrolloni vlerën e nyjeve, atëherë ju shkoni majtas ose djathtas. Pastaj ju shikoni vlerën e nyjeve, shkoni majtas ose djathtas. Kjo është e përshtatshme të përkryer për recursion. Pra, edhe pse në të kaluarën ne kemi bërë disa shembuj mjaft arbitrare të bëjnë recursion që nuk duhet të jetë gjithkund rekursive, me STUCTURES të dhënave, sidomos pemë, kjo është një aplikim i përsosur i kësaj ideje të marrë një problem, pakësuar atë, dhe pastaj zgjidhjen e njejta, por më të vogla, programin. Pra, ka një tjetër strukturë e të dhënave që ne mund të futur. Ky i fundit është i dizajnuar në shikim të parë duken të fshehtë, por kjo është e mahnitshme. Kështu kjo është një strukturë të dhënave i quajtur një trie, trie, e cila është e trashëguar nga rikthim fjalë, e cila nuk është e theksuar ri-provoni-Val, por kjo është ajo që bota e quan këto gjëra. Përpiqet. T-r-i-e. Kjo është një strukturë pemë e disa lloj, por secili prej nyjeve në një trie duket të jetë ajo? Dhe kjo është pak mashtruese, sepse kjo është lloj i shkurtuar. Por kjo duket si çdo nyje në këtë trie është në fakt një grup. Dhe, edhe pse autori i këtij diagram nuk ka treguar atë, në këtë rast, ky trie është një strukturë e të dhënave qëllimi i të cilit në jetë është për të ruajtur fjalët si A-l-i-c-E ose B-o-B. Dhe mënyra në të cilën ky dyqane të dhënat e Alice dhe Bob dhe Charlie dhe Anita dhe kështu me radhë është ajo përdor një rrjet ku për të ruajtur Alice në një trie, ne të fillojë në nyje rrënjë që duket si një grup, dhe kjo është e shkruar në simbol stenografi. Autori harruar abcdefg, sepse nuk ka pasur emra me këtë. Ata vetëm treguan M dhe P dhe T, por në këtë rast, le të largohen nga Alice dhe Bob dhe Charlie me disa emra që janë këtu. Maxwell është në të vërtetë në këtë diagram. Pra, si e bëri autorin dyqan M-a-x-w-e-l-l? Ai ose ajo filloi në nyjen rrënjë, dhe shkoi për të [M], kështu përafërsisht 13, lokacioni 13 në grup. Pastaj nga atje, ka një tregues. Një tregues tjetër që çon në rrjet. Nga atje autor të indeksuara në atë grup në vendin A, si përshkruar aty në të majtë të lartë, dhe pastaj ai ose ajo e ndjekur atë tregues për një tjetër grup, dhe shkoi në treguesin e lokacionit në X. Pastaj në tjetër e lokacionit array W, E, L, L, dhe kështu me radhë, dhe më në fund, le të vërtetë të përpiqet për të vënë një foto për këtë. Çfarë bën një vështrim nyje si në kodin? Një nyjë në një trie përmban një koleksion të pointers në nyjet më shumë. Por ka gjithashtu mori të jetë një lloj të vlerës boolean, të paktën në këtë zbatim. Unë të ndodhë për të thirrur atë is_word. Pse? Sepse kur ju jeni futur Maxwell, ju nuk jeni futur asgjë në këtë strukturë të dhëna. Ju nuk jeni i shkrimit M. Ju nuk jeni të shkruar X. Të gjithë ju jeni bërë është pas pointers. Tregues që përfaqëson M, atëherë tregues që përfaqëson një, atëherë treguesin që përfaqëson X, atëherë W, E, L, L, por çfarë ju duhet të bëni në fund është lloj i shkoni, shikoni, kam arritur në këtë vend. Nuk ishte një fjalë që përfundon këtu në strukturën e të dhënave. Pra, çfarë është një trie është e mbushur me të vërtetë me autor dhe zgjodhi për të përfaqësuar këto terminuses me trekëndëshat pak. Kjo thjesht do të thotë se fakti ky trekëndësh është këtu, kjo vlerë e vërtetë boolean thotë në qoftë se ju shkoni prapa në pemë, që do të thotë një fjalë të quajtur Maxwell është në këtë. Por foo fjala, për shembull, nuk është në pemë, sepse në qoftë se unë të fillojë në nyjen rrënjë deri këtu në majë, Nuk ka asnjë tregues f, asnjë akrep o, nuk o akrep. Foo nuk është një emër në këtë fjalor. Por nga kontrast, Turing, T-U-r-I-N-g. Përsëri, unë nuk t ruajtur ose U ose R ose I ose n ose g. Por unë e bëri dyqan në këtë strukturë të dhënave një vlerë rruga e vërtetë këtu poshtë në këtë nyje - në pemë duke vendosur këtë vlerë boolean të is_word të vërtetë. Kështu që një trie është lloj i kësaj strukture meta shumë interesant, ku ju nuk jeni me të vërtetë ruajtjen fjalët veten për këtë lloj fjalori. Për të qenë të qartë, ju jeni vetëm ruajtjen po ose jo, nuk është një fjalë që përfundon këtu. Tani çfarë është implikimi? Nëse keni 150.000 fjalë në një fjalor që ju jeni duke u përpjekur për të ruajtur në kujtesë duke përdorur diçka si një listë e lidhur, ju do të keni 150,000 nyjet në listën tuaj të lidhura. Dhe gjetjen e një prej atyre fjalëve alfabetike mund të marrë kohë O (n). Ora lineare. Por në rastin këtu të trie, çfarë është koha për të gjetur drejtimin e një fjalë? Kjo rezulton nga bukuria këtu është se edhe në qoftë se ju keni tashmë 149.999 fjalë në këtë fjalor, zbatohet si me këtë strukturë të dhënave, sa kohë nuk është marrë për të gjetur ose futur një person më shumë në atë, si Alice, Alice? E pra, kjo është vetëm 5, ndoshta 6 hapat për karakterin zvarritës. Sepse prani e emrave të tjerë në strukturën e nuk ka marrë në mënyrë të futur Alice. Për më tepër, duke gjetur Alice sapo ka 150.000 fjalë në këtë fjalor nuk ka marrë në rrugën tuaj për të gjetur Alice në të gjitha, sepse Alice është. . . . . këtu, sepse kam gjetur një vlerë boolean. Dhe në qoftë se nuk ka asnjë boolean vërtetë, atëherë nuk është Alice në këtë strukturë të dhënave të fjalëve. Me fjalë të tjera, koha për të gjetur drejtimin e gjëra dhe të futur gjëra të reja në këtë Struktura e të dhënave është trie O - kjo nuk është n. Sepse prani e 150.000 njerëzve nuk ka efekt mbi Alice, ajo duket. Pra, le të thërrasë atë k, ku k është gjatësia maksimale e një fjale në gjuhën angleze e cila është zakonisht jo më shumë se 20-diçka karaktere. Pra, k është një konstante. Pra, Grail Shenjtë ne duket se kanë gjetur tani është që të një kohë trie, konstante për fut, për Lookups, për grisjeve. Sepse numri i gjërave tashmë në strukturën, të cilat nuk janë edhe fizikisht atje. Përsëri, ata janë vetëm lloj të kontrolluar off, po ose jo, nuk ka asnjë ndikim në kohën e saj të ardhshëm running. Por ka mori të jetë një kapur, përndryshe ne nuk do të kemi humbur aq shumë kohë në të gjitha këto struktura të dhënave të tjera vetëm për të marrë në fund të një të fshehtë që është e mahnitshme. Pra, çfarë çmimi jemi duke paguar për të arritur këtë madhështinë këtu? Hapësirë. Kjo gjë është masiv. Dhe arsyeja që autori nuk e paraqesin atë këtu, vërejmë se të gjitha këto gjëra që duken si vargjeve, ai nuk ka nxjerrë pjesën tjetër të pemës, pjesa tjetër e trie, sepse ata janë jo vetëm të rëndësishme për historinë. Por të gjitha këto nyje janë super të gjerë, dhe çdo nyje në pemë merr 26 ose në fakt, mund të jetë 27 karaktere, sepse në këtë rast unë isha duke përfshirë edhe hapësirën për apostrof kështu që ne mund të kemi fjalët apostrophized. Në këtë rast, këto janë vargjeve të gjerë. Pra, edhe pse ata nuk janë picutured, kjo merr një sasi masive të RAM. Që mund të jetë mirë, especilly në hardware modern, por kjo është tradeoff. Ne kemi marrë më pak kohë duke shpenzuar më shumë hapësirë. Pra, ku është e gjithë kjo shkon? E pra, le të bëjmë - le të shohim këtu. Le të bëjmë një kërcim për këtë djalë këtu. Besoni atë apo jo, fun sa më shumë që C ka qenë për një kohë tani, ne jemi duke arritur pikën në semestrin kur është koha për kalimin në gjërat më moderne. Gjërat në një nivel më të lartë. Dhe, edhe pse për pak javëve të ardhshme ne do të vazhdojnë të zhyt veten në botën e pointers dhe menaxhimit të memories për të marrë atë rehati me të cilat ne mund pastaj të ndërtuar në, loja fund është në fund të fundit për të futur, për ironi jo, kjo gjuhë. Ne do të shpenzojnë, si 10 minuta duke folur në lidhje me HTML. All HTML është është një gjuhë markup, dhe atë që një gjuhë markup është është këto seri kllapa hapura dhe të mbyllura kllapa që thonë se "e bëjnë këtë të guximshme ' "Bëni këtë italik 'bërë këtë qendër." Kjo nuk është e gjitha që intelektualisht interesante, por kjo është super e dobishme. Dhe kjo është me siguri gjithëpranishëm këto ditë. Por ajo që është e fuqishme në lidhje me botën e HTML, dhe web programim më në përgjithësi, është duke ndërtuar gjëra dinamike, shkruar kodin në gjuhë si PHP ose Python Ruby ose ose Java ose C #. Vërtet, çfarëdo gjuhën tuaj të zgjedhur është, dhe gjenerimin e HTML dinamike. Gjenerimi diçka që quhet CSS dinamike. Fletët Cascading stilin, e cila është edhe për estetikë. Dhe kështu, edhe pse, sot, në qoftë se unë të shkoni në faqen e internetit si një farë e Google.com njohur, dhe unë shkoj për të parë, zhvillues, View Source, e cila ndoshta ju keni bërë më parë, por do të shikoni burimin, kjo stuff ndoshta duket goxha fshehtë. Por kjo është kodi themelor që zbaton Google.com. Në fund para. Dhe në fakt e gjithë kjo është me gëzof estetikë stuff. Kjo është CSS deri këtu. Nëse unë mbaj Scroll poshtë ne do të merrni disa sende ngjyra-koduar. Kjo është HTML. Kodi i Google-it duket si një rrëmujë, por në qoftë se unë në fakt të hapur një dritare tjetër, ne mund të shohim disa strukturën për këtë. Nëse unë të hapur këtë ide, vëreni këtu, kjo është pak më i lexueshëm. Ne jemi duke shkuar për të parë para se të gjatë këtë tag, [fjala] është një tag, HTML, kreu, trupit, div, script, zona teksti, span, në qendër, div. Dhe kjo është edhe lloj i fshehtë i bukur në shikim të parë, por të gjithë këtë rrëmujë ndjek modele të caktuara, dhe modelet repeatable, kështu që sapo të marrë bazat poshtë, ju do të jetë në gjendje të shkruani kodin si kjo dhe pastaj manipuluar kodin si kjo duke përdorur edhe një gjuhë tjetër, të quajtur JavaScript. Dhe JavaScript është një gjuhë që shkon në brendësi të një shfletues sot që kemi përdorur në kurset e Harvardit, për mjet pazar natyrisht që Google përdor harta të ju jap një bandë e tërë e dinamizmit, Facebook ju jep për të treguar përditësime statusit çastit, Twitter përdor atë për të treguar ju tweets në çast. E gjithë kjo, ne do të fillojnë të zhyt veten in Por për të arritur atje, ne duhet të kuptojmë një diçka të vogël në lidhje me internet. Ky klip këtu është vetëm një minutë të gjatë, dhe le të supozojmë tani për tani kjo është, në fakt, se si Interneti punon si një ngacmues për atë që është në lidhje që do të vijnë. Unë ju jap "Warriors e Net." [♫ muzikë Slow kor ♫] [Transmetuesi Mashkull] Ai erdhi me një mesazh. Me një protokoll të gjitha të tij. [♫ muzikë Faster elektronike ♫] Ai erdhi në një botë të ftohtë firewalls, uncaring routers, dhe rreziqe shumë më keq se vdekja. Ai është i shpejtë. Ai është i fortë. Ai është TCP / IP, dhe ai e mori adresën tuaj. Luftëtarët e Net. [Malan] Javën e ardhshme, atëherë. Internet. Programimit web. Kjo është CS50. [CS50.TV]