[Powered by Google Translate] [Java 6] [David J. Malan] [Universiteti i Harvardit] [Kjo është CS50.] [CS50.TV] 

Kjo është CS50, dhe ky është fillimi i javës 6, kështu që një çift i veglave të reja janë tani në dispozicion për ju për të përfituar nga, e para e cila është quajtur CS50 Style. Shanset janë në qoftë se ju jeni si mua apo ndonjë prej shokëve të mësimdhënies, ju ndoshta keni parë një program të cilit stil duket një diçka të vogël si kjo. Ndoshta ju filloni prerë disa qoshet vonë gjatë natës, ose ju do të merren me atë më vonë, dhe pastaj një ose TF CA vjen mbi gjatë orarit të punës. Atëherë kjo është e vështirë për ne për të lexuar. E pra, ky kod është syntactically saktë, dhe ajo do të hartojë, dhe kjo vërtetë do të kandidojë. Por kjo nuk është aspak një 5 për stilin. 

Por tani, në qoftë se ne do të shkojmë në këtë directory këtu- dhe të vëreni se unë kam conditions2.c- dhe unë të drejtuar këtë komandë të re, style50, në këtë conditions2.c fotografi, Enter, vini re se kjo është informuar mua se ai ka qenë i stilizuar. Gedit vënë re se skeda është ndryshuar në disk, dhe në qoftë se unë klikoni ringarkoni, të gjitha problemet tuaja janë të automatizuar tani. [Duartrokitje] Kjo është një nga gjërat që kemi bërë këtë fundjavë. Të kuptojë se kjo është e papërsosur, sepse ka disa kodi se ai thjesht nuk do të jetë në gjendje të stilizoj të përkryer, por të realizuar këtë është tani një mjet që ju mund të përfitojnë nga në qoftë se vetëm për të ndreq disa prej teksteve më të errantly vendosur kaçurrel dhe si. 

Por më bindës tani është CS50 Kontrollo. Me CS50 kontrolloni, ju në fakt mund të kryejnë testet e njëjta saktësisë në kodin tuaj se miqtë mësimore janë në gjendje për të. Kjo është një linjë komande të shërbimeve që vjen tani në aplikim sa më shpejt që ju të bëni një update50 si per pset 4 specifikimet, dhe ta përdorni atë në thelb si kjo. Ju drejtuar check50 komandës. Pastaj ju të kalojë në një argument command line, ose më në përgjithësi njihet si një switch ose një flamur. Në përgjithësi, gjërat që kanë hyphens janë quajtur një kaloni në një program command line, ashtu-c specifikon kontrollet që ju dëshironi për të kandiduar. 

Testet që ju dëshironi për të kandiduar janë të identifikohet në mënyrë unike nga ky varg, 2012/pset4/resize. Me fjalë të tjera, kjo është vetëm një varg arbitrar, por unike që ne i përdorim për të identifikuar teste unike 4 pset e korrektësi. Dhe pastaj ju specifikoni një listë të ndara hapësirë ​​e dosjeve që ju doni të ngarkoni të CS50 Kontrollo për analizë. Për shembull, nëse unë shkoj në zgjidhjen e mia këtu për resize.c- më lejoni të hapur një terminal të madh dritare dhe unë të shkojnë përpara dhe të drejtuar, le të themi check50-c 2012/pset4/resize, dhe pastaj të shkojnë përpara dhe të përcaktojë emrat e dosjeve, resize.c, dhe pastaj goditi Enter, ajo fasha, Ngarkimet ajo, ajo kontrollon, dhe unë vetëm ka dështuar një bandë e tërë e testeve. Një në të kuqe në të majtë të lartë dhe thotë se resize.c PKM ekzistojnë. Kjo ishte test. Kjo ishte pyetja e kemi kërkuar. Dhe kjo është e pakënaqur, sepse përgjigja ishte e rreme. Teksti i bardhë poshtë ai thotë se pritet bmp.h të ekzistojë, dhe se është thjesht faji im. Kam harruar të ngarkoni atë, kështu që unë duhet të ngarkoni fotografi të dy, resize.c dhe bmp.h. Por tani të gjithë e vërejnë analizat e tjera janë në të verdhë për shkak se ata nuk kanë drejtuar, dhe kështu fytyra smiley është vertikale, sepse ai është i lumtur as as i trishtuar, por ne kemi për të korrigjuar këtë çështje në të kuqe para se ato kontrolle të tjera do të kandidojë. 

Më lejoni të rregullojmë këtë. Më lejoni të zoom jashtë dhe kjo përsëritje, këtë herë me bmp.h edhe në rreshtin e komandave, Enter, dhe tani nëse të gjitha shkon mirë, ajo do të kontrolluar dhe pastaj të kthehen një rezultat i-mbajnë frymën tuaj- të gjitha jeshile, që do të thotë unë jam duke bërë me të vërtetë mirë në pset 4 deri më tani. Ju mund ta shikoni dhe konkludoj nga teksti përshkrues këtu pikërisht ajo që është ne testuar. Ne testuar parë nuk ekzistojnë fotografi? Ne pastaj testuar bën përpilojnë resize.c? Pastaj ne nuk e testuar atë ndrysho një 1x1-pixel BMP, kur n, faktori resize, është 1. Tani, në qoftë se ju nuk kanë idenë se çfarë është n, ju do të sapo ju të zhyten në pset 4, por që thjesht është një mendje e shëndoshë kontrolloni për t'u siguruar që ju nuk jeni duke ndryshuar një imazh në të gjitha nëse faktori resize është 1. Nëse, nga ana tjetër, ajo madhësinë e një pixel në një PKM 1x1 1x1 2x2 pixel me korrekte kur n është 2, atëherë në mënyrë të ngjashme, minave formon përputhje me rrethanat. 

Me pak fjalë, kjo është menduar për të, një, të marrë kalimit gishtat nga ekuacioni të drejtë para se të dorëzojnë pset tuaj. Ju do të dini saktësisht se çfarë TF juaj së shpejti do të dini kur ju shkoni në lidhje me dorëzimin e disa nga këto grupe problemesh, dhe motivimi pedagogjike është me të vërtetë për të vënë mundësi në frontin e ju në mënyrë që kur ju e dini a priori se ka bugs në kodin tuaj dhe teste që nuk janë duke kaluar, ju mund të vënë në më shumë kohë efektive deri përpara për të zgjidhur këto probleme në vend se të humbni pikë, të merrni reagime nga TF tuaj, dhe pastaj të shkojnë, "Ahh," si unë duhet të ketë realizuar artistikisht se jashtë. Tani të paktën ka një mjet për t'ju ndihmuar të gjeni se. Kjo nuk do të vinte në dukje ku bug është, por ajo do të ju them çfarë është simptomatike e saj. 

Tani e kuptojnë se testet nuk janë domosdoshmërisht shteruese. Vetëm për shkak se ju të merrni një ekran të plotë të gjelbër fytyrat smiley nuk do të thotë kodi juaj është e përkryer, por kjo do të thotë se ajo ka kaluar teste të caktuara të përshkruara nga spec. Ndonjëherë ne nuk do të lëshojë çeqe. Për shembull, roman policor, një nga aspektet e pset 4, është lloj zhgënjyese, nëse ju japim përgjigje si për atë që është, dhe ka një numër mënyrash për të zbuluar kush është personi në atë zhurmë e kuqe. Spekulim gjithmonë do të specifikojë në të ardhmen për pset vazhdim 5 ajo kontrollon ekzistojnë për ju. Ju do të vëreni se kjo URL e bardhë në pjesën e poshtme. Tani për tani, kjo është vetëm prodhimi diagnostike. Nëse ju vizitoni këtë URL, ju do të merrni një bandë e tërë e çmendur, mesazhe të fshehta se ju jeni të mirëpritur për të parë përmes, por kjo është kryesisht për stafin kështu që ne mund të diagnostikojnë dhe debug mete në check50 vetë. 

Pa zhurmë, le të shkojë në të ku ne u ndërpre. CS50 bibliotekë morëm për të dhënë për disa javë, por pastaj javën e kaluar, kemi filluar lëkurë përsëri një nga shtresat e saj. Ne kemi filluar duke lënë mënjanë vargun në favor të asaj që në vend? [Studentët] Char. * Char, e cila ka qenë një char * gjithë këtë kohë, por tani ne nuk duhet të pretendojë se kjo është një e vërtetë të dhënave string lloji. Përkundrazi, kjo është një sinonim i terezi për * char, dhe një vargu është një sekuencë e karaktereve, kështu që pse nuk ka kuptim për të përfaqësuar vargjet si char * S? Çfarë bën një * char përfaqësojnë në kuadër të këtij koncepti të një varg? Po. >> [Student] Karakteri i parë. Mirë, karakteri i parë, por jo mjaft karakteri i parë. Kjo është e-Studentet [] Adresa. Mirë, adresa e karakter e parë. Të gjitha që është e nevojshme për të përfaqësuar një varg në kujtesën e një kompjuteri është vetëm adresa unike e bajt saj të parë. Ti as nuk duhet të dinë se sa kohë është sepse si mund të kuptoj se nga dinamike? [Student] Gjatësia String. Ju mund të telefononi gjatësinë varg, të shkëlqyer, por si e bën punën length string? Çfarë e bën atë të bëjë? Po. [Student] Do të mbajë deri sa ju të merrni karakterin null. Po, pikërisht, ajo vetëm iterates me një për lak, ndërsa loop, çfarëdo nga * në fund, dhe fundi është përfaqësuara nga \ 0, e ashtuquajtura karakter nul, nul, nuk duhet të ngatërrohet me null, e cila është një akrep, i cili do të dalë në bisedë përsëri sot. 

Ne peeled përsëri një shtresë e GetInt, dhe pastaj ne mori një vështrim në getString, dhe kujtojnë se të dyja këto funksione, apo me të vërtetë, GetString, ishte duke përdorur një funksion të caktuar që në fakt analizimi, që është, lexuar apo analizuar, input të përdoruesit. Dhe çfarë ishte se funksioni i ri? Scanf ose sscanf. Ajo në fakt vjen në një shije të ndryshme. Ka scanf, ka sscanf, ka fscanf. Për tani, megjithatë, le të përqëndrohet në një më të lehtë të ilustruar, dhe më lejoni të shkoj përpara dhe të hapur deri në aplikim një fotografi si kjo, scanf1.c. Ky është një program super të thjeshtë, por që bën diçka që ne kurrë nuk kam bërë pa ndihmën e bibliotekës CS50. Kjo merr një int nga një përdorues. Si funksionon kjo gjë? E pra, në përputhje 16 atje, vini re se ne deklarojë një int x quajtur, dhe në këtë moment në histori, çfarë është vlera e x? [Përgjigja e padëgjueshme Student] [David M.] E drejta, kush e di, disa vlera mbeturinat potencialisht, kështu që në 17, ne vetëm tregoni përdorues më jepni një numër, ju lutem, dhe hap 18 është vendi ku ajo merr interesante. Scanf duket për të marrë hua një ide nga printf në atë që përdor këto kode format në thonjëza. % D është sigurisht një numër decimal. Por pse jam unë duke kaluar në & X në vend të vetëm x? Ish është e saktë. Po. [Përgjigja e padëgjueshme Student] Pikërisht, në qoftë se qëllimi i këtij programi, si GetInt funksion vetë, është për të marrë një int nga përdorues që unë mund të kalojë funksione të gjithë variablat që unë dua, por në qoftë se unë nuk e kalojnë duke iu referuar ose adresën ose nga treguesin, të gjitha sinonime për qëllime sotme, pastaj se funksioni nuk ka aftësinë për të ndryshuar përmbajtjen e atij variabli. Kjo do të kalojë në një kopje të vetëm si në versionin buggy të swap-it se ne kemi biseduar për disa herë tani. 

Por në vend, duke bërë dhe x, unë jam vërtetë kalon në çfarë? [Student] Adresa. >> Adresën e x. Është si tërhequr një hartë për funksionin quajtur scanf dhe duke thënë këtu, këto janë drejtime në një copë të kujtesës në kompjuter që ju mund të shkoni të ruajë disa integer in Në mënyrë që sscanf tani bëni që atë operatori, ajo pjesë e sintaksës është ajo do të duhet të përdorin edhe pse ne nuk mund ta shohim atë, sepse dikush tjetër ka shkruar këtë funksion? Me fjalë të tjera - çfarë është ajo? [Student] X lexuar. Nuk do të jetë disa lexim, por vetëm në lidhje me x këtu. Nëse scanf është duke u kaluar adresën e x, syntactically, çfarë operatori është i detyruar të ekzistojë diku brenda e zbatimit scanf në mënyrë që scanf në fakt mund të shkruani një numër 2 në atë adresë? Yeah, kështu që *. Kujtojnë se * është operatori ynë dereference, i cili në thelb do të thotë të shkojnë atje. 

Pasi të keni dorëzuar një adresë, siç është rasti këtu, scanf është ndoshta, nëse ne fakt shikuar përreth saj burimor kod- është duke bërë * x ose e barabartë me të vërtetë të shkuar në atë adresë dhe të vënë disa vlera atje. Tani, si për mënyrën se si scanf merr input nga tastiera, ne do të tundë duart tona për sot. Vetëm të supozojmë se sistemi operativ lejon sscanf për të folur në tastierën e përdoruesit, por në këtë pikë tani në linjë 19, kur ne thjesht të shtypura nga x, ajo duket të jetë rasti scanf se ka vënë në një int x. Kjo është pikërisht se si scanf punon, dhe kujtojnë javën e kaluar kjo është pikërisht se si getString dhe GetInt dhe familja e saj e tjera të funksioneve përfundimisht punon, megjithëse me grindje të lehtë si sscanf, që do të thotë të skanoni një varg në vend të tastierës. Por le të marrin një vështrim në një grindje të vogël të kësaj. Në scanf2, unë në fakt dehur. Çfarë është e gabuar dhe unë do të fsheh koment që shpjegon sa- çfarë është e gabuar me këtë program, version 2? Të jetë aq teknike të jetë e mundur këtë kohë. Ajo duket goxha e mirë. Është prerë bukur, por- rregull, si për le të krasitësh atë poshtë për pyetje të shkurtra? Line 16. Çfarë është duke bërë linjës 16 në anglisht të saktë, por teknike? Getting pak vështirë. Po, Michael. [Student] Është vënë në shkronjën e parë të një varg. 

Mirë, afër. Më lejoni të shkulje se pak pak. Treguar në letrën e parë të një varg, ju jeni deklaruar një tampon ndryshueshme quajtur që do të pikës tek adresën parë të një vargut, ose më mirë, që do të tregojë në mënyrë më specifike në një char. Njoftim kjo nuk është në të vërtetë vënë kudo, sepse nuk ka asnjë operator detyrë. Nuk ka asnjë shenjë të barabartë, kështu që të gjithë ne jemi duke bërë është alokimin e quajtur buffer ndryshueshme. Ajo ndodh të jetë 32 bit sepse kjo është një tregues, dhe përmbajtjen e tampon duket përfundimisht do të përmbajë një adresë të një char, por tani për tani, çfarë përmban tampon? Vetëm disa fals, kush e di, disa vlera plehrash, sepse ne nuk kemi nisur në mënyrë eksplicite atë, kështu që ne nuk duhet të supozojmë asgjë. Mirë, kështu që tani është 17-linja çfarë do të vijë 17 të bëni? Ndoshta kjo do të ngrohtë këtë ide. Ajo printon një varg, apo jo? Ajo printon String ju lutem. 

Linja 18 është lloj i njohur tashmë në atë që ne vetëm pashë një grindje të kësaj por me një kod tjetër format, kështu që në linjë 18, ne jemi duke thënë scanf këtu është adresa e një copë e kujtesës. Unë dua që ju të telefononi në një varg, kuptohet nga% s, por problemi është se ne nuk kemi bërë disa gjëra këtu. Çfarë është një nga problemet? [Student] Ajo është duke u përpjekur për të dereference një tregues null. Mirë, pointers ose thjesht ndryshe null panjohur. Ju jeni dorëzimin scanf një adresë, por ju vetëm tha se një moment më parë se kjo është adresa disa vlera mbeturina sepse ne fakt nuk caktojë atë për asgjë, dhe kështu ju jeni duke thënë scanf efektive shkoni vënë një varg ketu, por ne nuk e dimë se ku këtu ende është, kështu që ne nuk kemi ndarë në fakt kujtesë për. Për më tepër, ajo gjithashtu nuk jeni edhe i thënë scanf? Supozoni se kjo ishte një copë e kujtesës, dhe kjo nuk ishte një vlerë e mbeturinave, por ju nuk jeni akoma thënë scanf diçka të rëndësishme. [Student] Ku ai në fakt është simbol. Simbol, kështu që në këtë rast, kjo është në rregull. Sepse tampon është deklaruar tashmë si një tregues me copë * e sintaksës, ne nuk kemi nevojë për të përdorur ampersand sepse ajo është tashmë një adresë, por unë mendoj se kam dëgjuar këtu. [Student] Sa e madhe është ajo? Mirë, ne nuk jemi duke u thënë sa e madhe kjo scanf tampon është, që do të thotë edhe në qoftë se tampon ishin një tregues, ne jemi duke thënë scanf, vënë një varg ketu, por këtu mund të jetë 2 bytes, ajo mund të jetë 10 bytes, ajo mund të jetë një megabyte. Scanf ka asnjë ide, dhe për shkak se kjo është një copë e kujtesës me sa duket, kjo nuk është një varg ende. Kjo është vetëm një varg herë që ju shkruani karakteret dhe një \ 0 deri në atë copë të kujtesës. Tani ajo është vetëm disa copë e kujtesës. Scanf nuk do të dinë se kur do të ndalet me shkrim në atë adresë. 

Nëse ju kujtohet disa shembuj në të kaluarën, ku kam shtypur rastësisht në tastierë duke u përpjekur për të fryhen një tampon, dhe kemi biseduar të premten rreth pikërisht këtë. Nëse një kundërshtar disi injekton në programin tuaj një fjalë shumë më të madhe ose fjali ose fraza atëherë keni qenë duke pritur ju mund muar një copë e kujtesës, e cila mund të ketë pasoja të këqija, si të marrë përsipër të gjithë programin e vetë. Ne kemi nevojë për të rregulluar këtë disi. Më lejoni të zoom jashtë dhe të shkojë në versionin 3 të këtij programi. Kjo është një pak më të mirë. Në këtë version, të vini re ndryshimin. Në linjë 16, unë jam përsëri shpalljen e një tampon ndryshueshme quajtur, por çfarë është ajo tani? Është një grup prej 16 karaktere. Kjo është e mirë, sepse kjo do të thotë unë mund të them tani scanf këtu është një copë aktuale e kujtesës. Ju mund të pothuajse të mendoj për vargjeve si pointers tani, edhe pse ata nuk janë në të vërtetë ekuivalente. Ata do të sillen ndryshe në kontekste të ndryshme. Por kjo është sigurisht rasti që tampon është referenca 16 chars puqur, sepse kjo është ajo që një grup është dhe ka qenë për disa javë tani. 

Ja, unë jam i thënë scanf këtu është një copë e kujtesës. Këtë herë, ajo është në fakt një copë e kujtesës, por pse është ky program ende shfrytëzueshëm? Çfarë është e gabuar ende? Unë e kam thënë më jepni 16 bytes por- [Student] Çka nëse ata të shkruani më shumë se 16? Pikërisht, çfarë nëse përdoruesi lloje në 17 shkronja ose karakteret 1700? Në fakt, le të shohim nëse ne nuk mund të udhëtim mbi këtë gabim tani. Është më mirë, por nuk është i përsosur. Më lejoni të shkojnë përpara dhe të bëjë të kandidojë scanf3 për të hartuar këtë program. Më lejoni të drejtuar scanf3, String ju lutem: hello, dhe ne duket të jetë në rregull. Më lejoni të provoni pak e një të gjatë, hello there. Mirë, le të mos hello there si jeni sot, Enter. Getting lloj fat këtu, le të thonë hello si jeni atje. Damn atë. Mirë, kështu që kemi marrë me fat. Le të shohim nëse ne nuk mund ta rregullojmë këtë. Jo, ajo nuk do të më lejoni të kopje. Le të provoni këtë përsëri. Të gjithë të drejtë, të dalë nga. Ne do të shohim se sa kohë unë mund të pretendojë të përqëndrohet, ndërsa ende duke bërë këtë. Damn atë. Kjo është mjaft e përshtatshme, në të vërtetë. Nuk shkojmë. Pika bërë. 

Kjo, edhe pse ai gjithashtu e turpshme është, ajo është gjithashtu një nga burimet e konfuzionit të madh kur shkrim programe që kanë të mete, sepse ata manifestohen vetëm një herë në një kohë ndonjëherë. Realiteti është se edhe në qoftë se kodi juaj është prishur plotësisht, ajo mund të jetë vetëm thyer plotësisht një herë në një kohë sepse ndonjëherë, në thelb ajo që ndodh është se ndan të sistemit operativ një kujtim pak më shumë se ju në të vërtetë nevojë për çfarëdo arsye, dhe kështu askush tjetër është duke përdorur kujtesën tuaj menjëherë pas copë prej 16 karaktereve, kështu që nëse ju shkoni në 17, 18, 19, çfarëdo qoftë, kjo nuk është e tillë një punë e madhe. Tani, kompjuter, edhe nëse ajo nuk ka përplasje në atë pikë, eventualisht mund të përdorni numrin byte 17 ose 18 ose 19 për diçka tjetër, në të cilën pikë të dhënat tuaja që ju vënë atje, edhe pse tepër e gjatë, do të marrë potencialisht overwritten nga ndonjë funksion tjetër. Kjo nuk është domosdoshmërisht do të mbetet i paprekur, por kjo jo domosdoshmërisht do të shkaktojë një defekt seg. Por në këtë rast, unë më në fund dhënë karaktere të mjaftueshme që unë në thelb tejkaluar segment time të kujtesës, dhe bam, sistemi operativ i tha: "Na vjen keq, kjo nuk është e mirë, faji segmentimit." 

Dhe tani le të shohim nëse ajo mbetet këtu në time directory- vëreni se unë kam këtë fotografi këtu, core. Vini re se kjo është quajtur përsëri një hale thelbësore. Kjo është në thelb një file që përmban përmbajtjen e kujtesës programit tuaj në pikën në të cilën ai rrëzua, dhe vetëm për të provoni një shembull pak këtu më lejoni të shkoj në këtu dhe të drejtuar mbi gdb scanf3 dhe pastaj specifikoni një argument të tretë të quajtur thelbësore, dhe vini re këtu se në qoftë se unë lista kodin, ne do të jetë në gjendje si zakonisht me gdb për të filluar duke ecur nëpër këtë program, dhe unë mund të kandidojë atë dhe sa më shpejt që unë goditi-si me komandë hap në GDB- sa më shpejt që unë goditi linjë potencialisht buggy pas shtypni në një varg të madh, Unë do të jetë në gjendje që në fakt identifikojnë atë këtu. Më shumë për këtë, edhe pse, në seksionin në drejtim të deponive kryesore dhe si mënyrë që ju në fakt mund të thes rreth në brendësi të deponisë kryesore dhe shiko në atë linjë programi dështoi ju. Ndonjë pyetje atëherë mbi pointers dhe në adresat? Sepse sot e tutje, ne do të fillojë të marrë për të dhënë se këto gjëra ekzistojnë dhe ne e dimë saktësisht se çfarë janë ata. Po. 

[Student] Si të vijë ju nuk keni për të vënë një simbol tjetër për pjesën- Mirë pyetje. Si të vijë unë nuk kanë për të vënë një simbol tjetër për grup karakter si unë e bëri më parë me shumicën e shembujve tanë? Përgjigja e shkurtër është vargjeve janë pak të veçantë. Ju mund të pothuajse të mendoj se një tampon si të vërtetë të qenit një adresë, dhe kjo ndodh pikërisht kështu që të jetë rasti që sheshi simbol kllapa është një lehtësi në mënyrë që ne mund të shkojnë në kllapa 0 kllapa, 1, 2 kllapa, pa pasur nevojë për të përdorur simbol *. Kjo është pak e një gënjeshtër e bardhë, sepse vargjeve dhe pointers janë, në fakt, një pak të ndryshme, por ata mund të shpesh, por jo gjithmonë të përdoret interchangeably. Me pak fjalë, kur një funksion është duke pritur një tregues për një copë e kujtesës, ju mund ta kalojë atë një adresë që është kthyer nga malloc, dhe ne do të shohim malloc përsëri para se të gjatë, ose ju mund të kalojë atë emrin e një sërë. Ju nuk keni për të bërë simbol me vargjeve, sepse ata janë tashmë thelb si adresat. Kjo është një përjashtim. Kllapa katrore bëjnë ato të veçantë. 

Ju mund të vendosni një simbol tjetër për tampon? Jo në këtë rast. Kjo nuk do të punojë, sepse, përsëri, në këtë rast këndi ku vargjeve nuk janë mjaft të vërtetë adresat. Por ndoshta ne do të vijnë përsëri në se para se të gjatë me shembuj të tjerë. Le të përpiqen për të zgjidhur një problem këtu. Ne kemi një strukturë të dhënave që ne kemi qenë duke përdorur për disa kohë e njohur si një grup. Rasti në pikën, kjo është ajo që ne vetëm kishte. Por kanë disa vargjeve upsides dhe dobësi. Vargjeve janë pse e bukur? Çfarë është një gjë që ju pëlqen, deri në atë masë që ju pëlqen vargjeve-rreth vargjeve? Çfarë është e përshtatshme për ta? Çfarë është bindëse? Pse ne kemi prezantuar ato në vendin e parë? Po. [Student] Ata mund të ruajë një shumë të të dhënave, dhe ju nuk duhet të përdorni një gjë të tërë. Ju mund të përdorni një seksion. Mirë, me një koleksion që ju mund të ruajë një shumë të të dhënave, dhe ju nuk domosdoshmërisht duhet të përdorin të gjitha e saj, kështu që ju mund overallocate, i cili mund të jetë i përshtatshëm në qoftë se ju nuk e dini paraprakisht se sa diçka për të presin. 

GetString është një shembull i përkryer. GetString, shkruar nga ne, nuk ka asnjë ide se sa chars të presin, mënyrë fakti që ne mund të ndajnë chunks e kujtesës puqur është e mirë. Vargjeve të zgjidhur një problem ne pamë një javë më parë tani ku kodi juaj fillon të bie në diçka shumë të dobët projektuar. Kujtojnë se kam krijuar një strukturë studentore quajtur David, dhe pastaj që ishte në të vërtetë një alternativë, edhe pse, për të pasur një emër ndryshueshme quajtur dhe një ndryshore tjetër të quajtur, unë mendoj, shtëpi, dhe një tjetër ndryshueshme quajtur ID, sepse në këtë histori unë atëherë të kërkuar për të futur diçka tjetër si Rob në program, kështu që atëherë kam vendosur prisni një minutë, Unë kam nevojë për të riemërtoni këto ndryshore. Le të thërrasë mine name1, ID1, house1. Le të thërrasë të Rob name2, house2, ID2. Por atëherë, pritni një minutë, ajo që për Tommy? Pastaj kemi pasur tre variablave më shumë. Ne kemi prezantuar dikë tjetër, katër grupe të variablave. Bota filloi të marrë çrregullt shumë shpejt, kështu që ne kemi prezantuar structs, dhe çfarë është bindëse në lidhje me një struct? Çfarë bën një struct C të ju lejojnë të bëni? Është me të vërtetë vështirë sot. Çfarë? >> [Përgjigja padëgjueshme Student] Yeah, konkretisht, typedef ju lejon të krijoni një lloj të ri të dhënave, dhe struct, struct fjalen, ju lejon të encapsulate copë lidhje konceptuale e të dhënave së bashku dhe pas kësaj ata e quajnë diçka si një student. 

Kjo ishte e mirë, sepse tani ne mund të modelojnë lloj shumë më të qëndrueshme konceptualisht nocioni i një studenti në një variabël në vend se në mënyrë arbitrare ka një për një varg, një për një ID, dhe kështu me radhë. Vargjeve janë të bukur, sepse ata na lejojnë për të filluar pastrimin kodin tonë. Por çfarë është një downside tani e një grup? Çfarë nuk mund të bëni ju? Po. [Student] Ju duhet të dini se sa e madhe është. Ju duhet të dini se sa e madhe është, kështu që kjo është lloj i një dhimbje. Ata prej jush me përvojë programimit paraprake e di se në shumë gjuhë, si Java, ju mund të kërkoni një copë e kujtesës, veçanërisht një grup, sa i madh je ti, me një gjatësi, pronës, në mënyrë që të flasin, dhe kjo është me të vërtetë i përshtatshëm. Në C, ju nuk mund të telefononi edhe strlen në një grup gjenerike sepse strlen, si fjala nënkupton, është vetëm për vargjet, dhe ju mund të kuptoj se gjatësinë e një varg për shkak të kësaj konvente njeriut të paturit e një \ 0, por një koleksion, më përgjithësisht, është vetëm një copë e kujtesës. Në qoftë se kjo është një grup i ints, nuk do të jetë një karakter të veçantë në fund duke pritur për ju. Ju duhet të mbani mend gjatësinë e një sërë. Një tjetër dobësitë e një sërë ngriti kokën e saj në getString vetë. Çfarë është një tjetër dobësitë e një grup? Zotëri, vetëm ju dhe mua sot. [Përgjigja e padëgjueshme Studenti] >> Kjo është ajo? Është shpallur në rafte. Mirë, deklaroi në rafte. Pse nuk ju pëlqen kjo? [Student] Për shkak se ajo merr ripërdoren. Ajo merr ripërdoren. Mirë, në qoftë se ju përdorni një rrjet të kujtesës, ju nuk mund, për shembull, ta kthejë atë, sepse kjo është në rafte. Mirë, kjo është një disavantazh. Dhe si për një tjetër me një grup? Sapo ju të caktojë atë, ju jeni lloj i dehur nëse keni nevojë për më shumë hapësirë se ajo ka array. 

Pastaj ne kemi prezantuar,, malloc kujtojnë, e cila na dha mundësinë për të alokuar dinamike kujtesës. Por çfarë nëse ne u përpoq një botë krejt të ndryshme? Çfarë ndodh nëse ne të kërkuar për të zgjidhur disa nga këto probleme kështu që ne vend-im stilolaps ka rënë në gjumë këtu- çka nëse ne në vend të kërkuar për të në thelb të krijuar një botë që nuk është më si kjo? Ky është një grup, dhe, natyrisht, ky lloj i përkeqësohet pasi ne goditi fundin e array, dhe unë tani nuk kanë hapësirë ​​për një tjetër numër i plotë ose në një tjetër karakter. Çfarë ndodh nëse ne lloj preemptively thonë mirë, pse nuk kemi të pushojnë kjo kërkesë që të gjitha këto chunks e kujtesës të jetë i afërt për të kthyer prapa, dhe pse jo, kur kam nevojë për një int ose një char, vetëm më jep hapësirë ​​për një prej tyre? Dhe kur kam nevojë për një tjetër, më jepni një tjetër hapësirë, dhe kur kam nevojë për një tjetër, më jep mua një hapësirë. Avantazhi i cili tani është se nëse dikush tjetër merr memorie gjatë këtu, ndonjë gjë e madhe. Unë do të marrë këtë copë shtesë e kujtesës këtu dhe pastaj kjo. 

Tani, këtu Kapur vetëm është se kjo pothuajse ndjehet si kam një bandë e tërë e variablave të ndryshme. Kjo ndjehet si pesë variablave të ndryshme potencialisht. Por çfarë nëse ne vjedhin një ide nga vargjet ku ne disi lidhin këto gjëra së bashku konceptualisht, dhe çfarë nëse unë e bëri këtë? Kjo është shigjetë e mia shumë të dobët tërhequr. Por mendoj se secili prej këtyre chunks të memories vuri në dukje tjetër, dhe ky djalë, i cili nuk ka asnjë vëlla në të drejtën e tij, nuk ka shigjetë të tillë. Kjo është në fakt ajo që quhet një listë e lidhur. Kjo është një strukturë e re të dhënat që na lejon të akordojë një copë e kujtesës, pastaj një tjetër, pastaj një tjetër, pastaj një tjetër, çdo herë që ne duam gjatë një programi, dhe ne kujtojmë se ata janë të gjithë disi të lidhura nga fjalë për fjalë chaining ata së bashku, dhe ne e bëmë që pictorially këtu me një shigjetë. Por në kod, çfarë do të jetë mekanizmi nëpërmjet të cilit ju mund të lidheni disi, pothuajse si Scratch, një copë në një copë? Ne mund të përdorim një tregues, apo jo? Sepse me të vërtetë arrow qe po ndodh nga sheshi lartë të majtë, ky djalë këtu për këtë, mund të përmbajë brenda këtij sheshi jo vetëm disa ints, jo vetëm disa char, por ajo në qoftë se unë në fakt ndahen një hapësirë ​​pak ekstra kështu që tani, secili prej chunks e mia të kujtesës, edhe pse kjo do të kushtojë mua, tani duket pak më shumë drejtkëndëshe, ku një nga chunks e kujtesës është përdorur për një numër, si numri 1, dhe pastaj, nëse ky djalë ruan numrin 2, kjo copë tjetër e kujtesës është përdorur për një shigjetë, ose më konkretisht, një akrep. Dhe mendoj unë ruajtur numrin 3 mbi këtu, ndërsa unë të përdorni këtë për pikë në atë djalë, dhe tani ky djalë, le të supozojmë se unë vetëm dua tre chunks të tilla të kujtesës. Unë do të tërheqë një vijë përmes se, duke treguar null. Nuk ka asnjë karakter shtesë. 

Në të vërtetë, kjo është se si ne mund të shkoni në lidhje me zbatimin e diçka që quhet një listë e lidhur. Një listë e lidhur është një strukturë e re të dhënave, dhe kjo është një hap drejt Strukturat shumë njohës të dhënave që fillojnë për të zgjidhur problemet përgjatë vijave të Facebook-lloj problemesh dhe Google tipit problemet ku ju keni të dhëna të mëdha grupe, dhe kjo nuk shkurton atë për të ruajtur gjithçka pranë njëri tjetrit dhe të përdorin diçka si kërkim linear apo edhe diçka si kërkim binar. Ju dëshironi herë edhe më të mirë running. Në fakt, një nga Grails Shenjta ne do të flasim më vonë këtë javë, ose e ardhshme është një algoritmi të cilit drejtimin Ora është konstante. Me fjalë të tjera, ajo gjithmonë merr të njëjtën sasi kohe pa marrë parasysh sa i madh është kontributi, dhe se me të vërtetë do të jetë bindëse, edhe më shumë se sa diçka logaritmike. Çfarë është kjo në ekran këtu? Secili prej rectangles është pikërisht ajo që unë thjesht tërhoqi me dorë. Por gjëja gjithë rrugës në të majtë është një variabël e veçantë. Ajo do të jetë një tregues të vetme, sepse një Gotcha me një listë e lidhur, pasi këto gjëra janë të thirrur, është që ju keni për të ul receptorin e telefonit në një fund të listës të lidhura. 

Ashtu si me një varg, ju duhet të dini adresën e char parë. Marrëveshja njëjtë për listat e lidhura. Ju duhet të dini adresën e copë e parë e kujtesës sepse nga atje, ju mund të arrijnë çdo njëri tjetër. Dobësitë. Çfarë çmimi jemi duke paguar për këtë shkathtësi të paturit e një dinamike konsiderueshëm të dhënat e strukturës se në qoftë se ne ndonjëherë nevojë për më shumë memorie, gjobë, vetëm një pjesë të ndajë më shumë dhe të nxjerrë një tregues nga e vjetër në bisht të ri të listës? Po. [Student] Ajo merr hapësirë ​​rreth dy herë më shumë. Ajo merr dy herë më shumë hapësirë, kështu që është padyshim një downside, dhe ne kemi parë këtë tradeoff para mes kohës dhe hapësirës dhe fleksibilitet ku deri tani, ne nuk kemi nevojë për 32 bit për secilin prej këtyre numrave. Ne me të vërtetë nevojë për 64, 32 dhe për numrin 32 për treguesin. Por hej, kam 2 gigabajt të RAM. Shtimi i një tjetër 32 bit këtu dhe këtu nuk duket se i madh i një marrëveshje. Por, për grupe të mëdha të të dhënave, kjo definitivisht shton deri në dy herë më shumë fjalë për fjalë. Çfarë është një tjetër downside tani, ose çfarë funksion do të heqim dorë, nëse ne përfaqësojmë listat e gjëra me një listë të lidhura dhe jo një grup? [Student] Ju nuk mund të kaloj nëpër atë prapa. Ju nuk mund të kaloj nëpër atë prapa, kështu që ju jeni lloj i dehur nëse ju jeni duke ecur nga e majta në të djathtë duke përdorur një për lak ose një lak, ndërsa dhe pastaj ju kuptojnë, "Oh, unë dua të kthehem në fillim të listës." Ju nuk mund të për shkak se këto pointers shkojnë vetëm nga e majta në të djathtë si shigjetat tregojnë. 

Tani, ju mund të mbani mend fillimin e listës me një ndryshore tjetër, por kjo është një kompleksiteti të mbani në mend. Një grup, pa marrë parasysh se sa larg ju shkoni, ju mund gjithmonë të bëjë minus, minus, minus, minus dhe të kthehemi prej nga keni ardhur. Çfarë është një tjetër downside këtu? Po. [Pyetja padëgjueshme Student] Ju mund të, kështu që ju keni në fakt propozoi vetëm një strukturë të të dhënave që quhet një listë e lidhur dyfish, dhe në të vërtetë, ju do të shtoni një tjetër tregues për secilin nga këto rectangles që shkon në drejtim tjetër, me kokë e të cilit është tani ju mund të kaloj mbrapa dhe me radhë, Dobësitë e cila është tani ju jeni duke përdorur tri herë si kujtim sa kemi përdorur për të dhe gjithashtu duke shtuar kompleksitetit në drejtim të kodit ju duhet të shkruani për të marrë atë të drejtë. Por këto janë të gjitha ndoshta tradeoffs shumë të arsyeshme, nëse kthimi është më e rëndësishme. Po. [Student] Ju gjithashtu nuk mund të ketë një listë 2D lidhura. Mirë, ju nuk mund të vërtetë kanë një listë 2D lidhur. Ju mund të. Kjo nuk është aq e lehtë sa një grup. Si një grup, ju bëni kllapa hapur, simboli i mbyllur, simboli i hapur, i mbyllur, kllapa dhe ju merrni një strukturë 2-dimensionale. Ju mund të zbatojë një listë të 2-dimensionale të lidhur në qoftë se ju bëni shtesë si ju propozoi-një tregues tretë për secilën nga këto gjëra, dhe në qoftë se ju mendoni për një tjetër listë të vijnë në ju stil 3D nga ekrani për të gjithë ne, e cila është vetëm një zinxhir i disa lloj. Ne mund ta bëjë këtë, por kjo nuk është aq e thjeshtë sa shtypja kllapa e hapur, kllapa katrore. Po. [Pyetja padëgjueshme Student] Mirë, kështu që kjo është një rreng vërtetë. 

Këto algoritme që ne kemi pined gjatë, si oh, kërkimin binar, ju mund të kërkoni një rrjet të numrave në bord apo një libër telefoni në mënyrë shumë më shpejt në qoftë se ju përdorni përça dhe sundo dhe një algorithm kërko binar, por kërko binar kërkuar dy supozime. Një, se të dhënat u renditura. Tani, ne mund të supozohet ta mbajmë këtë renditura, kështu që ndoshta kjo nuk është një shqetësim, por kërko binar edhe supozohet se keni pasur qasje të rastit në listën e numrave, dhe një sërë ju lejon të keni qasje të rastit, dhe me qasje të rastit, Unë do të thotë në qoftë se ju jeni të dhënë një koleksion, sa kohë nuk është marrë ju për të marrë në kllapa 0? Një operacion, ju vetëm përdorni [0] dhe ju jeni të drejtë atje. Sa hapa nuk është marrë për të marrë në vend të 10? Një hap, ju thjesht shkoni në [10] dhe ju jeni atje. Nga ana tjetër, si mund të shkoj në numër të plotë 10 në listën e lidhur? Ju duhet të fillojë në fillim, sepse ju jeni vetëm duke kujtuar fillimi i një liste të lidhura, ashtu si një varg po kujtohet nga char adresën e saj të parë, dhe për të gjetur se int 10 ose që karakteri 10 në një varg, ju duhet të kërkoni të gjithë gjë damn. 

Përsëri, ne nuk jemi zgjidhjen të gjitha problemet tona. Ne jemi duke futur të reja, por me të vërtetë varet nga ajo që ju jeni duke u përpjekur për të hartuar për të. Në kushtet e zbatimit të kësaj, ne mund të huazoni një ide nga ajo strukture studentore. Sintaksa është shumë e ngjashme, me përjashtim tani, ideja është pak më abstrakte se shtëpi dhe emrin dhe ID. Por unë propozoj që ne mund të kemi një strukturë të dhënave në C që quhet nyje, si fjala e fundit në rrëshqitje sugjeron, brendësi të një nyje, dhe nje nyje është vetëm një enë gjenerik në shkencën kompjuterike. Është tërhequr zakonisht si një rreth ose një katror apo drejtkëndësh siç kemi bërë. Dhe në këtë strukturë të dhënave, ne kemi një int, N, kështu që është numri që unë dua për të ruajtur. Por çfarë është kjo linjë e dytë, struct * nyja e ardhshme? Pse është kjo e saktë, apo çfarë roli e bën këtë lojë gjë, edhe pse kjo është pak fshehtë në shikim të parë? Po. [Përgjigja e padëgjueshme Student] Pikërisht, kështu renditjes * e plaçkës se kjo është një tregues i disa lloj. Emri i këtij treguesi është arbitrare tjetër, por ne mund të kemi quajtur atë gjë ne duam, por çfarë e bën këtë pikë tregues për? [Student] Një nyje. >> Pikërisht, kjo tregon për një nyje të tillë. 

Tani, kjo është lloj i një kuriozitet të C. Kujtojnë se C është lexuar nga një përpilues krye e deri në fund, e majta në të djathtë, që do të thotë nëse-kjo është pak e ndryshme nga ajo që ne e bëmë me student. Kur ne definuar një student, ne fakt nuk e vënë një fjalë atje. Ajo thjesht tha typedef. Pastaj kemi pasur int, id emrin string string, shtëpi, dhe pastaj nxënësi në fund të struct. Kjo deklaratë është pak më ndryshe, sepse, përsëri, përpiluesit C është pak memec. Është vetëm do të lexoni krye e deri në fund, kështu që nëse ajo arrin të vijë 2 here ku tjetër është shpallur dhe ajo e sheh, oh, këtu është një ndryshore të quajtur ardhshëm. Kjo është një tregues për një nyje struct. Përpiluesit do të kuptojnë se çfarë është një nyje struct? Unë kurrë nuk kam dëgjuar për këtë gjë përpara, sepse nyja fjala nuk mund të duket ndryshe deri në fund, kështu që nuk është kjo tepricë. Ju keni për të thënë nyje struct këtu, të cilat ju mund pastaj të shkurtojë më vonë në sajë të typedef poshtë këtu, por kjo është për shkak se ne jemi referenca strukturën vetë brenda të strukturës. Kjo është një Gotcha atje. 

Disa probleme interesante do të lindin. Ne kemi marrë një listë të numrave. Si nuk kemi futur në të? Si nuk kemi kërkoni atë? Si nuk kemi fshini prej saj? Sidomos tani që ne kemi për të menaxhuar të gjitha këto pointers. Keni menduar pointers ishin lloj i mendje-bending kur ju kishte njëri prej tyre vetëm duke u përpjekur për të lexuar një int të. Tani ne kemi për të manipuluar me vlerë një listë të tërë së. Pse nuk kemi marrë 5-minutësh pushim tonë këtu, dhe pastaj ne do të sjellë disa folks deri në skenë për të bërë pikërisht këtë. 

C është e bukur shumë më tepër kur është vepruar jashtë. Kush do të vërtetë donte të jetë i pari? Mirë, eja lart. Ju jeni parë. Kush do të donte të jetë 9? Mirë, 9. Si rreth 9? 17? Një klikë pak këtu. 22 dhe 26 në atë rreshtin e parë. Dhe pastaj si për dikë atje duke u vuri në. Ju jeni 34. Mirë, 34 vjeç, të vijë në dorë. Së pari është atje. Mirë, të gjithë katër të ju djema. Dhe kush nuk themi për 9? Kush është 9 ynë? Që me të vërtetë dëshiron të jetë 9? Të gjithë të drejtë, vijnë në, të jetë 9. Këtu ne do të shkojmë. 34, ne do të takohemi atje. Pjesa e parë është të bëjë vetë duket si kjo. 26, 22, 17, mirë. Nëse ju mund të qëndrojë jashtë në anën, sepse ne jemi duke shkuar për malloc ju në një moment. 

Mirë, mirë. Mirë, i shkëlqyer, kështu që le të kërkojë disa pyetje këtu. Dhe në fakt, çfarë është emri juaj? >> Anita. Anita, në rregull, eja këtu. Anita do të na ndihmojë lloj të zgjidhur një pyetje mjaft të thjeshtë në fillim, e cila është se si ju të gjeni nëse ose jo një vlerë është në listë? Tani, vini re se pari, e përfaqësuar këtu nga Lucas, është pak më ndryshe, dhe kështu copë letër e tij është qëllimisht anash sepse ajo nuk është mjaft e gjatë dhe nuk merr deri sa copa shumë, edhe pse teknikisht ai ka të njëjtën madhësi të letrës vetëm ndërrohen. Por ai është pak më ndryshe në se ai është vetëm 32 bit për një akrep, dhe të gjithë këta njerëz janë 64 bit, gjysma e të cilave është numri, gjysma e të cilave është një akrep. Por tregues nuk është përshkruar, kështu që nëse ju djema mund disi awkwardly përdorin dorën tuaj të majtë për pikë në personin tjetër për ju. Dhe ju jeni numri 34. Çfarë është emri juaj? Ari. Ari, kështu që në fakt, të mbajë letër në dorën tënde të djathtë, dhe dora e majtë shkon drejt poshtë. Ju përfaqësoni null në të majtë. 

Tani fotografia jonë njerëzore është shumë e qëndrueshme. Kjo është në fakt si pointers punojnë. Dhe në qoftë se ju mund të mbledh lëmsh ​​pak në këtë mënyrë kështu që unë nuk jam në rrugën tuaj. Anita këtu, të gjetur me numrin 22, por të marrë një pengesë e jo njerëzit e mbajnë deri në copa letre, por kjo është një listë, dhe ju vetëm duhet të fillojë me Lucas sepse ai është fjalë për fjalë pointer parë. Supozoni se ju vetë jeni një akrep, dhe kështu edhe ju keni mundësinë për pikë në diçka. Pse nuk ju filloni duke vënë pikërisht ajo Lucas është vënë në? Mirë, dhe më lejoni të miratojnë këtë, mbi këtu. Vetëm për hir të diskutimit, më lejoni të tërheqë një faqe bosh këtu. Si mund të shkruhet emri juaj? >> Anita. Mirë, Anita. Le të thonë nyje * anita = Lucas. E pra, ne nuk duhet të telefononi ju Lucas. Ne duhet të telefononi ju më së pari. Pse është kjo në fakt në përputhje me realitetin këtu? Një, i parë tashmë ekziston. Parë ka qenë i ndarë sa duket diku deri këtu. Nyja * parë, dhe ajo është ndarë një listë disi. Unë nuk e di se si ka ndodhur. Kjo ka ndodhur para se të klasës filluar. Kjo listë e lidhur e njerëzve ka qenë i krijuar. Dhe tani në këtë moment në histori, kjo është e gjitha ndodh në Facebook me sa duket më vonë- në këtë pikë në histori, Anita ka qenë initialized të jetë e barabartë për të parë, e cila nuk do të thotë se pikat në Anita Lucas. Përkundrazi, ajo tregon se çfarë tregon ai në sepse e njëjta adresë që është brenda 32 bit Lucas-së - 1, 2, 3 - tani është gjithashtu brenda 32 bit Anita - 1, 2, 3. 

Tani e gjejnë 22. Si do të shkojë për të bërë këtë? Çfarë është ajo? >> Pika për çdo gjë. Pikë të çfarëdo, kështu që të shkojnë përpara dhe të veprojë atë sa më mirë që mundeni këtu. Mirë, mirë, dhe tani ju jeni duke treguar, çfarë është emri juaj me 22? Ramon. >> Ramon, kështu Ramon po mban deri 22. Ju keni bërë tani një kontroll. A Ramon == 22, dhe nëse është kështu, për shembull, ne mund të kthehen vërtetë. Le mua-ndërsa këta njerëz qëndrojnë këtu disi awkwardly- më lejoni të bëj diçka shpejt si bool gjetur. Unë jam duke shkuar për të shkuar përpara dhe të thonë (nyje * listë, int n). Unë do të jetë e drejtë mbrapa me ju djema. Unë vetëm duhet të shkruani disa kodin. Dhe tani unë jam duke shkuar për të shkuar përpara dhe të bëjë këtë, Nyja * anita listën =. Dhe unë jam duke shkuar për të shkuar përpara dhe të thonë se ndërsa (anita! = NULL). 

Metafora këtu po bëhet pak shtrirë, por ndërsa (anita! = NULL), çfarë unë dua të bëj? Unë kam nevojë për disa mënyra të referuar integer që Anita është vënë në. Në të kaluarën, kur kemi pasur struktura, e cila është një nyje, kemi përdorur simbol dot, dhe ne do të themi diçka si anita.n, por problemi këtu është se Anita nuk është një struct në vetvete. Çfarë është ajo? Ajo është një akrep, kështu që me të vërtetë, në qoftë se ne duam që të përdorin këtë simbol dot- dhe kjo do të shikojmë qëllimisht pak fshehtë- ne duhet të bëjmë diçka si të shkoni në të majtë çfarëdo Anita është vënë në dhe pastaj të merrni në fushën e quajtur n. Anita është një tregues, por ajo që është * anita? Çfarë bëni ju të gjeni kur ju shkoni në atë Anita është vënë në? Një struct, një nyje, dhe një, nyje risjell, ka një fushë të quajtur N sepse ajo ka, kujtojmë, këto 2 fusha, të ardhshme dhe n, që ne pamë një moment më parë të drejtë këtu. 

Që në fakt imitojnë këtë kod, ne mund të bëjmë këtë dhe thonë se nëse ((* anita). == n n), n që unë jam duke kërkuar për të. Vini re se funksioni u miratua në numrin më intereson. Atëherë unë mund të shkoni përpara dhe të bëjë diçka si kthim të vërtetë. Tjetër, në qoftë se nuk është kështu, çfarë unë dua të bëj? Si mund të përkthehet në kodin atë Anita e bëri këtë intuitive duke ecur nëpër lista? Çfarë duhet të bëj deri këtu për të simuluar Anita marrë këtë hap në të majtë, që hap në të majtë? [Përgjigja e padëgjueshme Studenti] >> Çfarë është ajo? [Përgjigja e padëgjueshme Student] Mirë, nuk është një ide e keqe, por në të kaluarën, kur e kemi bërë këtë, ne kemi bërë anita + + sepse kjo do të shtojë numrin 1 të Anita, të cilat zakonisht do të tregojnë në personin tjetër, si Ramon, ose personi tjetër të tij, ose pranë tij personi poshtë vijës. Por kjo nuk është mjaft e mirë këtu, sepse ajo e bën këtë gjë të duket si në kujtesë? Jo se. Ne duhet të çaktivizoni këtë. Ajo duket si kjo në kujtesë, dhe edhe pse unë kam tërhequr 1 dhe 2 dhe 3 pranë njëri-tjetrit, nëse ne me të vërtetë të simulojnë këtë mund të ju djema-, ndërsa ende duke treguar në të njëjtit njerëz, disa prej jush mund të marrë një back rastit hap, disa prej jush një hap përpara rastit? 

Kjo rrëmujë është ende një listë e lidhur, por këta njerëz mund të jetë kudo në kujtesë, kështu anita + + nuk do të punojë pse? Çfarë është në të lokacionit anita + +? Kush e di. Kjo është disa vlera të tjera që vetëm kështu ndodh të jetë interposed në mesin e të gjitha këto nyje nga rastësia, sepse ne nuk jeni duke përdorur një rrjet. Ne alokuar secilën prej këtyre nyjeve individualisht. Mirë, në qoftë se ju djema mund të pastruar veten back up. Më lejoni të propozojë që në vend të anita + +, ne vend bëjmë Anita merr- edhe, pse nuk shkojmë në çfarëdo Anita është vënë në dhe pastaj të bëjë. tjetër? Me fjalë të tjera, ne do të shkojmë në Ramon, i cili e mban numrin 22, dhe pastaj. tjetër është sikur Anita do të kopjimit majtë treguesin e tij të dorës. Por ajo nuk do të shkojë më larg se Ramon sepse kemi gjetur 22. Por që do të jetë ideja. Tani, kjo është një zot-tmerrshme rrëmujë. Sinqerisht, askush nuk do të ndonjëherë të mbani mend këtë sintaksë, dhe kështu fatmirësisht, kjo është në fakt një pak qëllimshme-oh, ju në fakt nuk shohim se çfarë kam shkruar. Kjo do të jetë më bindëse në qoftë se ju mund. Voila! 

Prapa skenave, unë u zgjidhur problemin në këtë mënyrë. Anita, për të marrë këtë hap në të majtë, Së pari, ne do të shkojnë në adresën që Anita është vënë në dhe ku ajo do të gjeni jo vetëm n, të cilat ne vetëm kontrolluar për hir të së krahasim, por ju do të gjeni edhe më tej - në këtë rast, Dorën e majtë Ramon së treguar në nyjen e ardhshëm në listë. Por kjo është perëndia-mess tmerrshme për të cilën unë përmendur më herët, por ajo del C na lejon të thjeshtojë këtë. Në vend të shkrimit (* anita), ne mund të shkruani vetëm në vend anita-> n, dhe kjo është gjë e saktë të njëjtën funksionalisht, por kjo është një shumë më intuitive, dhe kjo është një shumë më tepër në përputhje me foto që ne kemi qenë të tërhequr të gjithë këtë kohë duke përdorur shigjetat. 

Së fundi, çfarë ne duhet të bëjmë në fund të këtij programi? Ka një linjë të kodit mbetur. Kthehu çfarë? Rreme, sepse nëse ne marrim me anë të tërë, ndërsa loop Anita dhe është, në fakt, null, që do të thotë ajo shkoi gjatë gjithë rrugës deri në fund të listës ku ajo ishte vënë në-çfarë është emri juaj përsëri? Dorën e majtë Ari. >> Ari, i cili është i pavlefshëm. Anita është tani null, dhe unë të kuptojë se ju jeni vetëm duke qëndruar këtu awkwardly në harresë sepse unë jam duke shkuar jashtë në një monolog këtu, por ne do të përfshijë përsëri në vetëm një moment. Anita është i pavlefshëm në atë moment në histori, kështu që lak, ndërsa përfundon, dhe ne duhet të kthehen false sepse në qoftë se ajo mori të gjitha rrugën në treguesin null Ari-së atëherë nuk kishte asnjë numër që ajo kërkoi në listë. Ne mund të pastruar këtë shumë, por kjo është një implementim mjaft të mirë, atëherë i një funksioni traversal, një gjeni funksion për një listë të lidhura. Është ende kërkimit lineare, por kjo nuk është aq e thjeshtë sa një akrep + + ose + + një variabël i sepse tani ne nuk mund të mendoj ku secili prej këtyre nyjeve janë në kujtesë. Ne duhet të vërtetë ndjekin gjurmët e breadcrumbs ose, më saktë, pointers, për të marrë nga një nyje në një tjetër. 

Tani le të provoni një tjetër. Anita, nuk ju duan të kthehen këtu? Pse nuk do të shkojmë përpara dhe të ndajë një person tjetër nga audienca? Malloc-çfarë është emri juaj? >> Rebecca. Rebecca. Rebecca ka qenë malloced nga publiku, dhe ajo është tani ruajtjen e numrit 55. Dhe qëllimi në dorë tani është për të futur Anita Rebecca në listën e lidhur këtu në vendin e vet të duhur. Ejani në më shumë këtu për një moment. Unë kam bërë diçka si kjo. Unë kam bërë * nyje. Dhe çfarë është emri juaj përsëri? Rebecca. >> Rebecca, në rregull. Rebecca merr malloc (sizeof (nyje)). Ashtu si kemi ndarë gjëra të tilla si studentët dhe gjësend në të kaluarën, ne kemi nevojë për madhësinë e nyjeve, kështu që tani Rebecca është vënë në çfarë? Rebecca ka dy fusha në brendësi të saj, njëra prej të cilave është 55. Le të bëjë atë, rebecca-> = 55. Por pastaj rebecca-> ardhshëm duhet të jetë-si e drejtë tani, dora e saj është lloj i kush e di? Është vënë në një vlerë mbeturinave, kështu që pse nuk bëni për masë të mirë ne të paktën të bëjë këtë në mënyrë që dora e majtë është tani në anën e saj. Tani Anita, të marrë atë nga këtu. Ju keni Rebecca që janë ndarë. Të shkojnë përpara dhe për të gjetur se ku duhet vënë Rebecca. Mirë, shumë i mirë. Mirë, mirë, dhe tani ne kemi nevojë për ju për të siguruar një grimë drejtim, kështu që ju keni arritur Ari. Dora e tij e majtë është null, por në mënyrë të qartë Rebeka i takon në të djathtë, Pra, si nuk kemi për të ndryshuar këtë listë lidhur në mënyrë për të futur Rebecca në vendin e duhur? Nëse ju mund të vërtetë të lëvizin duart e njerëzve lënë rreth si e nevojshme, ne do të rregullojmë problemin në këtë mënyrë. Mirë, mirë, dhe ndërkohë, dora e majtë Rebecca është tani nga ana e saj. 

Kjo ishte shumë e lehtë. Le të përpiqemi ndarjen e-we're bërë gati, 20. Mirë, eja lart. 20 është ndarë, kështu që më lejoni të shkoj përpara dhe të them përsëri këtu ne kemi bërë vetëm * Saad nyje. Ne kemi malloc (sizeof (nyje)). Ne pastaj të bëjë të njëjtën sintaksë e saktë si ne e bëmë më parë për 20, dhe unë do të bëj tjetër NULL =, dhe tani është në dorën Anita për të futur ju në listën e lidhur, në qoftë se ju mund të luajë këtë rol e saktë të njëjtën. Ekzekutuar. Mirë, mirë. Tani mendoni me kujdes para se të fillojnë të lëvizin duart e majtë përreth. Ju deri tani mori rolin më të vështirë sot. Duart e kujt duhet të zhvendoset parë? Mirë, prisni, unë jam dëgjuar disa nuk e. Nëse disa folks do të donte edukatë të ndihmuar në zgjidhjen e një situatë të vështirë këtu. Dora e të cilit e majtë duhet të përditësuar parë ndoshta? Po. [Student] e Saad. Mirë, e Saad, pse, pse? [Përgjigja e padëgjueshme Student] Mirë, sepse nëse ne lëvizim, çfarë është emri juaj? >> Marshall. Marshall, në qoftë se ne shkojmë dorën poshtë për të parë null, tani ne kemi mbetur jetimë fjalë katër persona në këtë listë sepse ai ishte e vetmja gjë e treguar në Ramon dhe të gjithë të majtë, kështu përditësimin se treguesin e parë ishte e keqe. Le të ndrequr këtë. Mirë, dhe tani të shkojnë përpara dhe të lëvizë dorën e majtë e duhur duke treguar në Ramon. Kjo ndihet pak të tepërta. Tani ka dy njerëz të vënë në Ramon, por kjo është në rregull sepse tani si tjetër nuk kemi update lista? Nga ana tjetër ajo që ka për të lëvizur? Shkëlqyer, tani nuk kemi humbur asnjë kujtim? Jo, në mënyrë të mirë, le të shohim nëse ne nuk mund ta thyejnë këtë herë më shumë. 

Mallocing për herë të fundit, numri 5. Të gjitha mënyra në shpinë, vijnë më poshtë. Është shumë emocionuese. [Duartrokitje] Çfarë është emri juaj? >> Ron. Ron, në rregull, ju jeni malloced si numër 5. Ne kemi vetëm ekzekutuar kodin që është pothuajse identike me këto me vetëm një emër tjetër. Shkëlqyer. Tani, Anita, fat i mirë futur numrin 5 në listën tani. Mirë, dhe? Shkëlqyer, kështu që kjo është me të vërtetë i tretë i tre raste gjithsej. Ne e parë kishte dikë në fund, Rebecca. Ne atëherë kishte dikë në mes. Tani ne kemi dikë në fillim, dhe në këtë shembull, ne tani duhej të rinovuar Lucas për herë të parë sepse elementi i parë në listë ka tani për pikë në një nyje të re, të cilët, nga ana tjetër, është treguar në numrin nyjeve 9. 

Ky ishte një demonstrim jashtëzakonisht i vështirë, unë jam i sigurt, kështu një raund i madh i duartrokitje për këta njerëz, nëse ju mund. Nicely done. Kjo është e gjitha. Ju mund të mbani copa tuaj të letrës, si një kujtim të vogël. Ajo rezulton se duke bërë këtë në kodin e nuk është mjaft aq e thjeshtë sa vetëm duke lëvizur duart përreth dhe duke treguar pointers në gjëra të ndryshme. Por të kuptojë se kur vjen koha për të zbatuar diçka si një listë e lidhur ose një variant i saj në qoftë se ju të përqëndrohet në të vërtetë këto themele bazë, kafshoj-size problemet që unë duhet të kuptoj se, është ky apo kjo dora dorës, të kuptojnë se çfarë është përndryshe një program mjaft komplekse mund, në fakt, të reduktohet në blloqe mjaft e thjeshtë e ndërtimit të tilla si kjo. 

Le të marrin gjërat në një drejtim më të sofistikuar ende. Ne tani e kemi idenë e listës lidhura. Ne gjithashtu kemi-në sajë të sugjerimin e pasme ka-një listë e lidhur dyfish, i cili duket pothuajse i njëjtë, por tani ne kemi dy pointers në brendësi të struct në vend të një, dhe ne ndoshta mund të quajmë këto pointers mëparshëm dhe të ardhshëm ose majtas ose djathtas, por ne, në fakt, kanë nevojë për dy prej tyre. Kodi do të jetë pak më shumë të përfshira. Anita do të duhej të bëjnë më shumë punë këtu në skenë. Por ne me siguri mund të zbatojë atë lloj të strukturës. Në kushtet e drejtimin kohë, pse, çfarë do të jetë hera e running Anita për të gjetur një numër n në një listë e lidhur tani? O ende e madhe n, kështu që ajo nuk është më e mirë se kërkim linear. Ne nuk mund të bëjmë kërkimin binar, edhe pse, përsëri. Pse ishte se rasti? Ju nuk mund të kërcejnë rreth. Edhe pse ne padyshim shohim të gjitha njerëzit në skenë, Anita dhe mund të ketë eyeballed atë dhe tha: "Ja, është mesi i listës," ajo nuk do të dinë se në qoftë se ajo ishte programi kompjuterik sepse e vetmja gjë që ajo kishte për të vendosur në gji për të në fillim të skenarit ishte Lucas, i cili ishte treguesi i parë. Ajo do domosdoshmërisht duhet të ndjekin këto lidhje, numëruar në rrugën e saj derisa ajo gjeti afërsisht mesi, dhe madje edhe atëherë, ajo nuk do të dinë se kur ajo është arritur mes përveç nëse ajo shkon gjithë rrugës deri në fund të kuptoj se sa shumë janë, pastaj backtracks, dhe se shumë do të jetë e vështirë nëse nuk keni pasur një listë e lidhur dyfish e disa lloj. 

Zgjidhjen e disa problemeve sot, por duke futur të tjerët. Po në lidhje me strukturën e të dhënave të ndryshme krejt? Kjo është një fotografi e tabaka në Mather House, dhe në këtë rast, ne kemi një strukturë të dhënave që ne kemi gjithashtu lloji i tashmë është duke folur rreth. Ne biseduam në lidhje me një pirg në kontekstin e kujtesës, dhe kjo është lloj i quajtur qëllimisht për shkak se një pirg në kushtet e kujtesës është efektivisht një strukturë të dhënave që ka më shumë gjëra dhe më shumë shtresa në krye të saj. Por gjëja më interesante në lidhje me një pirg, siç është rasti në realitet, është se kjo është një lloj i veçantë i të dhënave strukturë. Kjo është një strukturë e të dhënave ku elementi i parë në është elementi i fundit jashtë. Nëse ju jeni tabaka parë që do të vënë mbi rafte, ju jeni do të jetë fatkeqësisht tabaka e fundit që do të merren jashtë rafte, dhe kjo nuk është domosdoshmërisht një gjë e mirë. Në anën tjetër, ju mund të mendoni për atë mënyra të tjera përreth, e fundit në është nga e para. 

Tani, a ndonjë skenarë të vijnë në mendje kur të paturit e një pirg Struktura e të dhënave ku ju keni atë pronë e fundit në, së pari, është fakt bindës? Është se një gjë e mirë? Është se një gjë e keqe? Kjo është padyshim një gjë e keqe nëse tabaka nuk ishin të gjithë të njëjtë dhe ata ishin të gjithë ngjyrave të veçanta të ndryshme apo gjësend, dhe ngjyra është e gjitha që ju doni mënyra në fund. Sigurisht, ju nuk mund të merrni atë pa përpjekje të mëdha. Ju duhet të fillojë nga lart dhe të punojnë në rrugën tuaj poshtë. Në mënyrë të ngjashme, çfarë nëse ju keni qenë një nga këta djem tifoz që pret të gjithë natën duke u përpjekur për të marrë një iPhone dhe linjat e lart në një vend si ky? Nuk do të jetë mirë në qoftë se dyqan Apple ishin një pirg të dhënave strukturë? Yay? Jo? Kjo është vetëm e mirë për njerëzit që tregojnë deri në minutën e fundit të mundshme dhe pastaj merrni këputur, të njomë radhën. Dhe në fakt, fakti që unë u prirur në mënyrë që të thonë radhë është në të vërtetë konsistente me atë që ne do të quajmë këtë lloj të të dhënave strukturës, një në realitet, ku rendi ka rëndësi, dhe ju doni një të parë në të jetë e para nga në qoftë se vetëm për hir të drejtësisë njerëzore. Ne do të quajmë në përgjithësi të dhënat se një strukturë radhë. 

Ajo rezulton përveç listave të lidhura, ne mund të filloni duke përdorur këto ide të njëjta themelore dhe të fillojnë krijimin e llojeve të reja dhe të ndryshme të zgjidhjeve të problemeve. Për shembull, në rastin e një pirg, ne mund të përfaqësojë një pirg duke përdorur një strukturë të të dhënave si kjo, unë do të propozojë. Në këtë rast, unë kam deklaruar një struct, dhe unë kam thënë në brendësi të kësaj strukture është një grup i numrave dhe pastaj një madhësi të ndryshueshme të quajtur, dhe unë jam duke shkuar për të thirrur këtë gjë një pirg. Tani, pse e bën këtë të vërtetë punojnë? Në rastin e një pirg, unë mund të tërheqë këtë në mënyrë efektive në ekran si një grup. Këtu është rafte ime. Ata janë numra mi. Dhe ne do të tërheqë ata si kjo, kjo, kjo, kjo, kjo. Dhe atëherë unë kam disa të dhënave anëtar tjetër këtu, e cila quhet madhësia, kështu që kjo është madhësia, dhe kjo është numra, dhe kolektivisht, iPad gjithë këtu përfaqëson një strukturë rafte. Tani, by default, madhësia e ka marrë me sa duket për të nisur në 0, dhe çfarë është në brendësi të grup të numrave fillimisht kur kam parë caktojë një grup? Garbage. Kush e di? Dhe kjo nuk ka të vërtetë rëndësi. Ajo nuk ka rëndësi nëse kjo është 1, 2, 3, 4, 5, krejtësisht rastësisht nga fat i keq depozituara në strukturën time, sepse aq sa unë e di se madhësia e rafte është 0, atëherë unë e di programuar, nuk shohim ndonjë prej elementeve në array. Kjo nuk ka rëndësi se çfarë është atje. A nuk shikojnë ata, si do të jetë implikimi i madhësisë prej 0. 

Por mendoj tani unë po shkoj përpara dhe të futur diçka në rafte. Unë dua të futur numrin 5, kështu që kam vënë numrin 5 here, dhe pastaj çfarë kam vënë këtu poshtë? Tani unë në fakt do të vënë poshtë 1 për madhësinë, dhe tani rafte është e madhësisë 1. Çfarë ndodh nëse unë shkoj përpara dhe futni numrin, le të themi, 7 të ardhshëm? Kjo pastaj merr përditësuar për të 2, dhe pastaj ne do të bëjmë 9, dhe atëherë kjo merr përditësuar për të 3. Por karakteristikë interesante e këtij rafte tani është se Unë jam menduar për të hequr elementin i cili në qoftë se unë dua të pop diçka off rafte, kështu që të flasin? 9 do të jetë gjëja e parë për të shkuar. Si duhet të ndryshojë foto në qoftë se unë dua të pop një element jashtë rafte, shumë si një tabaka në Mather? Po. >> [Student] Madhësia Set në 2. Pikërisht, të gjitha unë bëj është vendosur në 2 madhësi, dhe çfarë të bëj me grup? Unë nuk kam të bëjë asgjë. Unë mund të, vetëm të jenë në anal, vënë një 0, ose a atje -1 apo diçka për të treguar se kjo nuk është një vlerë legit, por kjo nuk ka rëndësi, sepse Unë mund të regjistrojë jashtë array vetë se sa kohë është kështu që unë e di vetëm shikoni në dy elementet e para në këtë grup. Tani, nëse unë shkoj dhe shtoni numrin 8 në këtë grup, si e bën foto ndryshojë ardhshme? Kjo bëhet 8, dhe kjo bëhet 3. Unë jam një prerje qoshet pak këtu. Tani ne kemi 5, 7, 8, dhe ne jemi kthyer në një madhësi prej 3. Kjo është shumë e thjeshtë për t'u zbatuar, por kur do të shkojmë për keqardhje këtë vendim të projektimit? Kur gjërat fillojnë të shkojnë shumë, shumë i keq? Po. [Përgjigja e padëgjueshme Student] Kur ju dëshironi të ktheheni mbrapsh dhe të marrë elementin e parë që ju vënë in 

Kjo rezulton nga këtu, edhe pse një pirg është një koleksion nën kapuç, këto struktura të dhënave që kemi filluar duke folur rreth janë gjithashtu të njohur përgjithësisht si Strukturat abstrakte të dhënave ku si ata po zbatohet është krejtësisht përveç pikë. Një strukturë e të dhënave si një pirg është menduar për të shtuar mbështetjen e Operacionet si shtytje, e cila e shtyn një tabaka mbi rafte, dhe pop, e cila heq një element nga rafte, dhe kjo është ajo. Nëse ju do të shkarkoni kodin dikush tjetër që zbatohet tashmë kjo gjë të quajtur një pirg, që personi do të kishte shkruar vetëm dy funksione për ju, shtytje dhe pop, qëllimi i të cilit në jetë do të jetë për të bërë pikërisht këtë. Ju ose atë ose të saj të cilët zbatuar atë program do të kishte qenë tërësisht një për të vendosur se si për të zbatuar semantikë e shtyjnë dhe popping nën kapuç ose funksionalitetin e shtyjnë dhe popping. Dhe unë kam bërë një vendim disi dritëshkurtër këtu duke zbatuar pirg tim me këtë strukturë të dhënave të thjeshtë pse? Kur e bën këtë strukturë të dhënave pushim? Në çfarë pike mund të keni për të kthyer një gabim kur përdoruesi kërkon shtytje, për shembull? [Student] Nëse nuk ka shumë hapësirë. Pikërisht, në qoftë se nuk ka hapësirë ​​jo më shumë, në qoftë se unë kam tejkaluar kapacitetin, e cila është e gjitha shkronja kapitale, sepse ai sugjeron se kjo është një lloj konstante globale. E pra, atëherë unë jam vetëm do të duhet të them, "Më vjen keq, unë nuk mund të shtyjë një tjetër vlerë mbi rafte, "ashtu si në Mather. 

Në disa pika, ata do të goditur një pjesë të lartë të kabinetit të asaj pak. Nuk ka më shumë hapësirë ​​ose kapaciteti në rafte, në të cilën pikë ka disa lloj të gabimit. Ata kanë për të vënë elementin diku tjetër, tabaka diku tjetër, ose askund në të gjitha. Tani, me radhë, ne mund të zbatojë atë pak ndryshe. Një radhë është pak më ndryshe se në nën kapuç, ajo mund të zbatohet si një grup, por pse, në këtë rast, unë jam duke propozuar të kemi gjithashtu një element kokë përfaqëson kreun e listës, fronti i listës, personi i parë në përputhje në dyqan Apple, përveç në madhësi? Pse nuk kam nevojë për një pjesë shtesë e të dhënave këtu? Mendoni përsëri në atë numër është në qoftë se unë kam tërhequr atë si vijon. Supozoni se kjo është tani një radhë në vend të një pirg, diferenca është, vetëm si radhë të dyqan-Apple është e drejtë. Personi i parë në përputhje në fillim të listës, numër 5 në këtë rast, ai ose ajo do të jetë në dyqan le parë. Le ta bëjmë këtë. Le të supozojmë se kjo është gjendja e radhës sime në këtë moment në kohë, dhe tani dyqan Apple hap dhe personi i parë, numri 5, është udhëhequr në dyqan. Si mund ta ndryshoj foton tani që kam de-queued personin e parë në pjesën e përparme të linjës? Çfarë është ajo? >> [Student] Ndryshimi radhë. Ndrysho kokën, kështu 5 zhduket. Në realitet, kjo është sikur-sa më të mirë për të bërë këtë? Në realitet, kjo është sikur ky djalë zhduket. Çfarë do të bëjë numrin 7 në një dyqan aktuale? Ata do të marrin një hap të madh përpara. 

Por ajo që kemi ardhur për të vlerësojmë kur është fjala për vargjeve dhe lëviz gjërat përreth? Kjo është lloj i një humbje e kohës tuaj, apo jo? Pse ju duhet të jetë aq sa të keni anal personin e parë në fillim të linjës në fillim të fizikisht të copë e kujtesës? Kjo është krejtësisht e panevojshme. Pse? Çfarë mund të unë vetëm kujtoj vend? >> [Përgjigja padëgjueshme Student] Pikërisht, unë mund vetëm të kujtohet me këtë kokë shtesë dhënave anëtare se tani kreu i listës nuk është më 0, e cila ishte një moment më parë. Tani ajo është në të vërtetë numri 1. Në këtë mënyrë, unë të marrë një optimization lehtë. Vetëm për shkak se unë kam de-queued dikush nga përputhje në fillim të rreshtit në dyqan Apple nuk do të thotë të gjithë duhet të zhvendoset, e cila risjell është një operacion lineare. Unë mund të në vend të kalojnë kohën konstante vetëm dhe për të arritur më pas një përgjigje shumë më të shpejtë. Por çmimi unë jam duke paguar është ajo për të fituar atë punën shtesë dhe nuk ka për të zhvendosur të gjithë? Po. >> [Përgjigja e padëgjueshme Student] Mund të shtoni më shumë njerëz, mirë, se problemi është ortogonale për faktin se ne nuk jemi zhvendosur njerëzit përreth. Kjo është ende një grup, kështu që nëse ne nuk zhvendoset gjithë apo jo- oh, unë shoh atë që ju thotë, në rregull. Në fakt, unë jam dakord me atë që ju jeni duke thënë se në se ajo është pothuajse sikur ne jemi tani kurrë nuk do të përdorin fillimin e këtij grup më sepse në qoftë se unë heq 5, atëherë unë të hequr 7. Por unë vetëm vënë njerëzit në të djathtë. 

Ajo ndjehet si unë jam i humbur hapësirë, dhe përfundimisht radhë im disintegrates në asgjë në të gjitha, kështu që ne mund të ketë vetëm njerëz wraparound, dhe ne mund të mendojnë për këtë grup të vërtetë si një lloj strukture rrethore, por ne përdorim atë operatori në C për të bërë këtë lloj të wraparound? [Përgjigja e padëgjueshme Studenti] >> Operatori modulo. Ajo do të jetë një bezdisshëm pak për të menduar se si do të bëni këtë wraparound, por ne mund të bëjmë atë, dhe ne mund të fillojnë të vënë njerëzit në atë që përdoret për të jetë e përparme e linjës, por ne vetëm mos harroni me këtë variabël kokë që kreu aktual i linjës të vërtetë është. Çfarë ndodh nëse, në vend, në fund të fundit qëllimi ynë, megjithatë, ishte që të shikoni numrat, siç bëmë këtu në skenë me Anita, por ne të vërtetë duan të mirë të të gjitha këtyre botëve? Ne duam më shumë se sofistikimit array lejon sepse ne duam aftësinë për të dinamike rritet strukturën e të dhënave. Por ne nuk duam të duhet të mbështetet në diçka që ne dukje në leksionin e parë nuk ishte një algoritmi optimale, se e kërkimit lineare. Ajo rezulton se ju mund, në fakt, të arrijë ose të paktën afër në kohë të vazhdueshme, ku dikush si Anita, në qoftë se ajo konfiguron strukturën e saj të dhënave të mos jetë një listë e lidhur, të mos jetë një pirg jo, të jetë një radhë, mund, në faktin, dalë me një strukturë të dhënave që lejon të saj për të shikoni gjëra, edhe fjalët, jo vetëm numrat, në atë që ne do të thërrasë kohë konstante. 

Dhe në fakt, shikuar përpara, një nga psets në këtë klasë është pothuajse gjithmonë një zbatim i një spellchecker, ku ne ju jap përsëri disa fjalë 150.000 anglisht dhe qëllimi është që të ngarkesës ato në kujtesën dhe me shpejtësi të jetë në gjendje për t'iu përgjigjur pyetjeve të formularit po kjo fjalë shkruar drejt? Dhe kjo me të vërtetë do të thith qoftë se keni pasur për të iterate nëpër të gjitha 150.000 fjalë për të përgjigjem se. Por, në fakt, ne do të shohim se ne mund të bëjmë atë në kohë shumë, shumë të shpejtë. Dhe kjo do të përfshijë diçka implementues quajtur një tavolinë hash, dhe edhe pse në shikim të parë kjo gjë të quajtur një tabelë hash do të le të arritur këto kohët super të shpejtë përgjigje, rezulton se nuk është në fakt një problem. Kur vjen koha për të zbatuar këtë gjë të quajtur-përsëri, unë jam duke bërë atë përsëri. Unë jam i vetmi ketu. Kur vjen koha për të zbatuar këtë gjë të quajtur një tabelë hash, ne do të duhet të marrë një vendim. Sa e madhe duhet të jetë e vërtetë kjo gjë? Dhe kur ne fillojmë numrat futur në këtë tabelë hash, se si do të shkojmë për të ruajtur ato në një mënyrë të tillë që ne mund të merrni ato mbrapa sa më shpejt që kemi marrë ata në? Por ne do të shohim para se të gjatë që kjo pyetje të kur ditëlindjen të gjithëve është në klasë do të jetë mjaft i përshtatshëm. Ajo rezulton se në këtë dhomë, ne kemi marrë disa qindra njerëz, kështu që shanset që dy prej nesh kanë ditëlindjen njëjtë është ndoshta shumë e lartë. Çfarë nëse ka pasur vetëm 40 prej nesh në këtë dhomë? Cilat janë shanset e dy njerëzve që kanë të njëjtën ditëlindje? [Studentët] Mbi 50%. Po, mbi 50%. Në fakt, unë edhe solli një tabelë. Kjo rezulton nga, dhe kjo është me të vërtetë vetëm një vjedhës preview- në qoftë se ka vetëm 58 prej nesh në këtë sallë, probabiliteti i 2 prej nesh ka të njëjtën ditëlindje është jashtëzakonisht i lartë, pothuajse 100%, dhe kjo do të shkaktojë një bandë e tërë e lënduar për ne të mërkurën. 

Me tha se, le të shtyjë këtu. Ne do të shihemi të mërkurën. [Duartrokitje] [CS50.TV]