[Powered by Google Translate] [Neni 6: Më pak komode] [Nate Hardison] [Universiteti i Harvardit] [Kjo është CS50.] [CS50.TV] Dakord. Mirë se vini në nenin 6. Këtë javë, ne do të jetë duke folur në lidhje me të dhënat e strukturave në nenin, kryesisht për shkak se problemi i kësaj jave i vendosur në spellr ka një bandë e tërë e eksplorimit të ndryshme të të dhënave strukturë. Ka një bandë e mënyra të ndryshme ju mund të shkoni me grupin e problemit, dhe strukturat më të dhënat që ju dini rreth, gjërat më të freskët që ju mund të bëni. 

Pra, le të ketë filluar. Së pari ne do të flasim për oxhaqet, rafte dhe radhë të dhënave struktura që ne jemi duke shkuar për të folur rreth. Oxhaqet dhe radhët e gjata janë me të vërtetë të dobishme kur ne fillojmë të flasim në lidhje me grafikët, të cilat ne nuk jemi duke shkuar për të bërë aq shumë për të drejtën tani. Por ata janë me të vërtetë mirë për të kuptuar një prej strukturave themelore të mëdha të dhënave të CS. Përshkrimi në specifikim të caktuar të problemit, nëse ju tërheq atë, flet për oxhaqet si e ngjashme me grumbull i tabaka ngrënie që ju keni në lokal në sallat e restorant ku, kur stafi ngrënie vjen dhe e vë në tabaka ngrënie jashtë, pasi ata kanë pastruar ata, ata rafte atyre një në krye të tjera. Dhe pastaj kur fëmijët vijnë në për të marrë ushqim, ata të tërheqë off tabaka, së pari një të lartë, atëherë një poshtë atë, atëherë një më poshtë se. Pra, në fakt, tabaka e parë që stafi ngrënie vënë poshtë është e fundit që merr hiqet. E fundit që stafi ngrënie vënë në është i pari që merr marrë jashtë për darkë. Në spec Set problemi, i cili ju mund të shkarkoni në qoftë se ju nuk e keni tashmë, ne flasim për modelimin e një strukturës dhënave rafte përdorur këtë lloj të struct. 

Kështu që ajo që ne kemi marrë këtu, kjo është e ngjashme me atë që u paraqit në leksion, përveç në leksionin e kemi paraqitur këtë me ints në krahasim me s char *. Kjo do të jetë një pirg që dyqanet çfarë? Daniel? Çfarë jemi ne ruajtjen në këtë rafte? [Daniel] Strings? Ne jemi ruajtjen >> vargjet në këtë rafte, pikërisht. Të gjithë ju duhet të keni në mënyrë që të krijojë një pirg është një grup të një kapaciteti të veçantë, e cila në këtë rast, kapaciteti do të jetë në të gjitha shkronja kapitale, sepse kjo është një konstante. Dhe pastaj përveç array, të gjithë ne kemi nevojë për të ndjekur është madhësia aktuale e array. Një gjë të theksohet këtu se është lloj i ftohtë është se ne jemi duke krijuar strukturën e bërë pirg të dhënave në krye të një strukture të dhënave, array. Ka mënyra të ndryshme për të zbatuar oxhaqet. Ne nuk do të bëjë atë mjaft ende, por shpresojmë se pas duke bërë lidhur listë-probleme, ju do të shihni se si ju lehtë mund të zbatojë një pirg në krye të një listë e lidhur si. Por tani për tani, ne do të rrinë në vargjeve. Pra, përsëri, të gjithë ne kemi nevojë është një grup dhe ne vetëm duhet për të gjetur madhësinë e vektorit. [Sam] Na vjen keq, pse është ajo që keni thënë rafte është në krye të strings? Për mua kjo duket sikur vargjet janë brenda rafte. [Hardison] Yeah. Ne jemi duke krijuar, ne jemi duke marrë strukturën e të dhënave tona array - kjo është një pyetje e madhe. Pra, pyetja është pse, për njerëzit që janë të shikuar këtë online, pse jemi duke thënë se rafte është në krye të strings, sepse këtu duket sikur vargjet janë brenda rafte? Cili është krejtësisht rast. Ajo që unë po i referohej ishte se ne kemi marrë një strukturë të dhënave array. Ne kemi marrë një rrjet të char * s, ky grup të strings, dhe ne jemi duke shkuar për të shtuar se në mënyrë për të krijuar strukturën e bërë pirg të dhënave. 

Pra, një pirg është pak më komplekse se një grup. Ne mund të përdorni një rrjet të ndërtuar një pirg. Pra, kjo është ajo ku ne themi se është ndërtuar rafte në krye të një grup. Gjithashtu, siç thashë më herët, ne mund të ndërtojmë një pirg në krye të një listë të lidhura. Në vend të përdorimit të një rrjet për të mbajtur elementet tona, Ne mund të përdorni një listë të lidhur për të mbajtur elementet tona dhe për të ndërtuar rafte rreth se. Le të ecin nëpër një çift të shembujve, duke kërkuar në një kod, të parë se çfarë është në të vërtetë ndodh këtu. Në të majtë, unë kam hedhur poshtë atë që struct pirg do të duket si në kujtesë në qoftë se kapaciteti janë përcaktuar të jenë katër #. Ne kemi marrë katër element array tonë char *. Ne kemi marrë vargjet [0], vargjet [1], vargjet [2], strings [3], dhe pastaj atë hapësirë ​​fundit për numër të plotë tonë madhësisë. A ka kjo kuptim? Rregull. Kjo është ajo që ndodh në qoftë se ajo që unë bëj në të djathtë, cili do të jetë kodi im, është që vetëm të deklarojë një struct, një struct bërë pirg quajtur s. Kjo është ajo që kemi marrë. Ajo parashtron këtë gjurmë në kujtesën. Pyetja e parë këtu është ajo që janë përmbajtjet e kësaj struct rafte? Tani për tani ata janë asgjë, por ata nuk janë krejtësisht asgjë. Ata janë ky lloj i mbeturinave. Ne nuk kemi asnjë ide se çfarë është në to. Kur ne të deklarojë s rafte, ne jemi vetëm duke hedhur poshtë që në krye të kujtesës. Kjo është lloj i si deklarimit int dhe jo Initializing atë. Ju nuk e dini se çfarë është në atje. Ju mund të lexoni se çfarë është në atje, por kjo nuk mund të jetë super e dobishme. Një gjë që ju doni të kujtohet gjithmonë për të bërë është nisja çfarëdo duhet të initialized. Në këtë rast, ne do të nisja madhësinë që të jetë zero, për shkak se do të kthehet të jetë shumë e rëndësishme për ne. Ne mund të shkoni përpara dhe të nisja të gjitha pointers, të gjitha s char *, të jetë disa vlera e kuptueshme, ndoshta null. Por kjo nuk është plotësisht e domosdoshme që ne të bëjmë atë. 

Tani, dy operacionet kryesore në oxhaqet janë? Çdokush mend nga leksioni ajo që ju bëni me oxhaqet? Po? [Stella] Nxitjen dhe popping? Pikërisht >>. Nxitjen dhe popping janë dy operacionet kryesore në oxhaqet. Dhe çfarë do të bëjë shtytje? Ajo vë >> diçka mbi krye i rafte, dhe pastaj popping merr atë. [Hardison] Pikërisht. Pra, shtyn shtyn diçka në krye të rafte. Është si të stafit ngrënie vënë një tabaka ngrënie poshtë në banak. Dhe popping është duke marrë një tabaka ngrënie jashtë të rafte. Le të ecin nëpër një çift të shembujve të asaj që ndodh kur ne shtyjë gjërat në rafte. Nëse ne do të shtyjë string 'hello' onto rafte tonë, kjo është ajo që diagram ynë do të duken si tani. Shih se çfarë ndodh? Ne e shtyu në elementin e parë të strings array tonë dhe ne ngritur akuzë tonë permasa të jetë 1. Pra, nëse ne shikojmë në dallimin në mes të dy slides, këtu ishte 0, këtu është para shtytje. Këtu është pas shtytje. Para shtytje, pas shtytje. Dhe tani ne kemi një element në rafte tonë. Kjo është vargu "hello", dhe kjo është ajo. Çdo gjë tjetër në grup, në vargjet array tonë, është ende mbeturina. Ne nuk kemi nisur atë. Le të thonë se ne shtytje tjetër varg mbi rafte tonë. Ne jemi duke shkuar për të shtyrë "botën" në këtë kohë. Kështu që ju mund të shihni "bota" këtu shkon në krye të "hello", dhe numërimin madhësia shkon deri në 2. Tani ne mund të shtyjë "CS50", dhe që do të shkojnë në krye përsëri. Nëse ne do të shkojmë përsëri, ju mund të shihni se si ne jemi duke shtyrë gjërat në krye të rafte. Dhe tani ne kemi marrë të pop. Kur ne popped off diçka e rafte, çfarë ka ndodhur? Çdokush shihni ndryshim? Kjo është goxha delikate. [Student] size. >> Yeah, madhësia ndryshuar. 

Çfarë tjetër do të keni pritet të ndryshojë? [Student] Të vargjet, too. E drejta >>. Vargjet shumë. Ajo rezulton se, kur ju jeni duke bërë atë në këtë mënyrë, sepse ne nuk jemi kopjimi elementet në rafte tonë, ne fakt nuk kemi të bëjmë asgjë, ne mund të përdorni vetëm madhësinë për të mbajtur gjurmët e numrit të gjërave në grup tonë kështu që kur ne të pop përsëri, përsëri ne vetëm pakësim madhësinë tonë deri në 1. Nuk ka nevojë që në fakt shkojnë në dhe të prishësh diçka. Lloji i shokuar. Ajo rezulton se ne zakonisht vetëm lënë gjërat vetëm për shkak se ajo është më pak punë për ne për të bërë. Nëse ne nuk kemi për të shkuar mbrapa dhe prishësh diçka, atëherë pse ta bëjë këtë? Pra, kur ne dy pop off rafte, të gjitha që nuk është pakësim përmasa disa herë. Dhe përsëri, kjo është vetëm për shkak se ne nuk jemi kopjimi gjëra në rafte tonë. Po? Të shkojnë përpara. [Student, pakuptueshëm] >> Dhe atëherë ajo që ndodh kur ju shtyjnë diçka përsëri? Kur ju shtyjnë diçka përsëri, ku e bën atë të shkojnë? Ku e bën atë të shkojë, Basil? Into >> strings [1]? E drejta >>. Pse nuk e bën atë të shkojnë në vargjet [3]? [Basil] Për shkak se harruan që nuk kishte asgjë në vargjet [1] dhe [2]? [Hardison] Pikërisht. Rafte tonë, në thelb, "harroi" se ajo ishte mbajtur për asgjë në vargjet e [1] ose strings [2], kështu që kur ne shtytje "Woot", ai thjesht e vë atë në elementin në të strings [1]. A ka ndonjë pyetje se si kjo punon, në një nivel bazë? [Sam] Pra, kjo nuk është në asnjë mënyrë dinamike, në aspektin e shumës apo në aspektin e madhësisë së rafte? [Hardison] Pikërisht. Kjo është - pika ishte se kjo nuk ishte një pirg dinamike growning. Kjo është një pirg që mund të mbajë, më së shumti, katër s char *, në shumicën e katër gjëra. Nëse ne do të përpiqemi dhe të shtyjë një gjë e pestë, çfarë mendoni se duhet të ndodhë? [Studentët, pakuptueshëm] [Hardison] Pikërisht. Ka një numër të gjërave që mund të ndodhë. Kjo ndoshta mund të seg fajin, në varësi të asaj që ne kemi qenë në - pikërisht si ne u zbatimin e mbrapa fund-. Ajo mund të prishësh. Ajo mund të ketë që del nga shtrati tampon që kemi biseduar rreth në klasë. Çfarë do të jetë gjëja më e qartë që mund të jetë overwritten në qoftë se ne u përpoq që të shtyjë një gjë shtesë për rafte tonë? Pra, ju përmendët një tampon del nga shtrati. Çfarë mund të jetë ajo që do të marrë me shkrim mbi ose shkeli në nëse ne mbush aksidentalisht duke u përpjekur për të nxitur një gjë shtesë? [Daniel, i pakuptueshëm] mundshme >>. Por fillimisht, çfarë mund të ndodhë? Çfarë ndodh nëse ne u përpoq që të shtyjë një gjë të katërt? Kjo mund të prishësh madhësinë, të paktën me këtë diagram kujtesës që ne kemi marrë. 

Në specifikimin e caktuar e problemit, e cila është ajo që ne jemi duke shkuar për të zbatuar sot, ajo që ne duam të bëjmë është vetëm të kthimit të rreme. Metoda e jonë shtytje do të kthehen një vlerë boolean, dhe se vlera boolean do të jetë e vërtetë në qoftë shtytje pason dhe të rreme, nëse ne nuk mund të shtyjë asgjë më shumë, sepse rafte është e plotë. Le të ecin nëpër një grimë të vogël e atë kod të drejtë tani. Këtu është funksioni ynë shtytje. Funksioni ynë shtytje për një pirg do të marrë në vargun për të vënë në rafte. Ajo do të kthehet e vërtetë, nëse vargu është shtyrë me sukses më ndryshe rafte dhe të rreme. Çdo sugjerime se çfarë mund të jetë një gjë e mirë e parë që bëni këtu? [Sam] Nëse madhësia e barabartë me kapacitetin e pastaj do të ktheheni të rreme? [Hardison] Bingo. Nice job. Nëse madhësia është kapaciteti, ne do të kthehen rreme. Ne nuk mund të vënë asgjë më shumë në rafte tonë. Përndryshe, ne duam të vënë diçka në krye të rafte. Çfarë është "në krye të rafte," fillimisht? [Daniel] Size 0? Size >> 0. Çfarë është në krye të rafte, pasi ka një gjë në rafte? Missy, ju e dini? [Missy] Një. Size >> është një, pikërisht. Ju mbani duke shtuar në madhësi, dhe çdo herë ju jeni vënë në element të ri në madhësinë e indeksit në rrjet. Ne mund të bëjë atë me këtë lloj të një astar-, në qoftë se ka kuptim. Pra, ne kemi marrë strings koleksion tonë, ne jemi duke shkuar për të hyrë në indeksin e madhësisë, dhe ne jemi vetëm duke shkuar për të ruajtur tonë char * në atje. Vini re se si nuk ka kopjimi string ndodh në këtu, nuk alokimi dinamike e kujtesës? Dhe pastaj Missy solli atë që ne tani kemi për të bërë, sepse ne kemi ruajtur string në vendin e duhur në grup, dhe ajo tha se kemi pasur të ardhura madhësinë nga një në mënyrë që ne jemi të gatshëm për shtytje tjetër. Pra, ne mund ta bëjmë këtë me s.size + +. Në këtë pikë, ne kemi shtyrë në grup tonë. Cila është gjëja e fundit që ne duhet të bëjmë? [Student] Kthimi i vërtetë. Kthehu >> vërtetë. Pra, kjo është shumë e thjeshtë, një kod shumë e thjeshtë. Jo shumë. Pasi të keni mbështjellë kokën tuaj rreth si rafte punon, kjo është shumë e thjeshtë për t'u zbatuar. 

Tani, pjesa tjetër e kjo është popping një varg off e rafte. Unë jam duke shkuar për të dhënë you guys disa kohë për të punuar në këtë pak pak. Është pothuajse në thelb e kundërta e asaj që ne kemi bërë këtu në shtytje. Ajo që unë kam bërë është në fakt - oops. Unë kam booted deri një aplikim gjatë këtu, dhe në aplikim, Unë e kam tërhequr problemi vendosur 5 specifikim. Nëse ne zoom në këtu, ne mund të shohim Unë jam në cdn.cs50.net/2012/fall/psets/pset5.pdf. A keni djema shkarkuar këtë kod që është vendosur këtu, section6.zip? Dakord. Nëse ju nuk e keni bërë këtë, bëjë këtë tani, me të vërtetë shpejt. Unë do të bëj atë në dritaren time terminal. Unë në fakt e bëri atë deri këtu. Po. Po, Sam? >> Unë kam një pyetje në lidhje me pse ju thoni s.string 's kllapa të madhësisë = rr? Çfarë është rr? Është që përcaktohet diku para, ose - Oh, në rr char *? [Hardison] Po, pikërisht. Kjo ishte argumenti. >> Oh, në rregull. Më vjen keq. [Hardison] Ne jemi duke specifikuar vargun për të nxitur in Pyetja tjetër që mund të dalë se nuk ka të vërtetë të flasim për këtu ishte kemi marrë për të dhënë se kemi pasur këtë ndryshore të quajtur s që ishte në fushëveprimin dhe të arritshëm për ne. Ne e mori për të dhënë se s ishte kjo struct rafte. Pra, duke kërkuar mbrapa në këtë kod shtytje, ju mund të shihni se ne jemi duke bërë gjëra me këtë varg që u miratua në por pastaj të gjithë një e papritur, ne jemi duke hyrë s.size, si, ku ka ardhur nga s? Në kodit që ne jemi duke shkuar për të shikojmë në arkiv seksionin dhe pastaj gjëra që ju do të jetë bërë në problemin tuaj përcakton, ne kemi bërë pirg tonë struct një ndryshore globale kështu që ne mund të kenë qasje në atë në të gjitha funksionet tona të ndryshme pa pasur në dorë të kalojë atë rreth dhe të kalojë atë me referencë, të bëjë të gjitha llojet e stuff se ndaj saj. Ne jemi vetëm cheating pak, në qoftë se ju do të, për të bërë gjëra të nicer. Dhe kjo është diçka që ne jemi duke bërë këtu, sepse kjo është për argëtim, është më e lehtë. Shpesh, ju do të shihni njerëzit të bëjnë këtë nëse ata kanë një të madh strukturën e të dhënave që është duke u operuar në kuadër të programit të tyre. 

Le të kthehemi mbi të pajisjes. A të gjithë sukses merrni section6.zip? Gjithkush unzip atë duke përdorur section6.zip unzip? Nëse ju shkoni në seksionin 6 directory - aah, në të gjithë vendin - dhe ju rendisni çfarë është këtu, ju shihni se ju keni marrë tre fotografi të ndryshme. c. Ju keni marrë një radhë, një SLL, e cila është e lidhur në formë individuale, dhe një listë të rafte. Nëse keni hapur deri stack.c, ju mund të shihni se ne kemi marrë këtë struct përcaktuar për ne, the struct saktë që ne vetëm të biseduar për në slides. Ne kemi marrë ndryshore tonë globale për të rafte, ne kemi marrë funksionin tonë shtytje, dhe pastaj ne kemi marrë funksionin tonë pop. Unë do të vënë kodin për shtyjë back up on the slide këtu, por ajo që unë do të doja që ju djema të bëni është që, në të mirë të aftësisë suaj, shkoni dhe të zbatojë funksionin pop. Një herë ju keni zbatuar atë, ju mund të përpilojë këtë me të bërë pirg, dhe pastaj të drejtuar ekzekutueshme rezultate rafte, dhe se do të kandidojë gjithë këtij kodi provë këtu poshtë se është në kryesore. Dhe kryesore kujdeset për të vërtetë duke bërë shtytje dhe pop thirrjet dhe duke u siguruar se çdo gjë shkon nëpër të gjithë të drejtë. Ajo gjithashtu initializes madhësinë e rafte të drejtë këtu kështu që ju nuk duhet të shqetësohen për Initializing këtë. Ju mund të supozojmë se kjo është initialized duhur nga koha që ju të hyni në atë funksion pop. Bën që të bëjnë kuptim? Pra, këtu ne do të shkojmë. Ka Kodi shtytje. Unë do të ju jap djema 5 ose 10 minuta. Dhe nëse keni ndonjë pyetje në ndërkohë, ndërsa ju jeni coding, ju lutem pyesni ata me zë të lartë. Pra, nëse ju merrni në një pikë kyçe, thjesht pyesni. Më lejoni të dinë, le të të gjithë të tjerët e dinë. Të punojë me fqinjin tuaj shumë. [Daniel] Ne jemi vetëm zbatimin e pop tani? Vetëm >> pop. Megjithëse ju mund të kopjoni zbatimin e shtytje në qoftë se ju dëshironi në mënyrë që testimi do të punojnë. Për shkak se ajo është e vështirë për të provuar gjëra të hyrë në - ose, është e vështirë për të provuar gjëra popping nga një pirg nëse nuk ka asgjë në rafte për të filluar me. 

Çfarë është pop dashur të kthehen? Elementi nga krye të rafte. Ajo është menduar për të marrë off element krye të rafte dhe pastaj pakësim madhësinë e rafte, dhe tani ju keni humbur elementin në krye. Dhe pastaj ju kthehen element në krye. [Student, pakuptueshëm] [Hardison] Pra, çfarë ndodh në qoftë se ju bëni këtë? [Student, pakuptueshëm] Çfarë përfundon ndodh është që ju jeni me siguri të hyrë ose një element që nuk është initialized ende, kështu që llogaritja juaj ku elementi i fundit është është off. Pra këtu, nëse ju njoftim, në shtytje, ne jemi duke hyrë në vargjet në elementin s.size sepse kjo është një indeks të ri. Kjo është top i ri i rafte. Ndërsa në pop, s.size do të jetë hapësira e ardhshme, hapësira që është në krye të të gjitha elementeve në rafte tuaj. Pra, top-më element nuk është në s.size, por më tepër, ajo është nën atë. 

Gjë tjetër për të bërë, kur ju - në pop, është që ju keni për pakësim madhësinë. Nëse ju kujtohet përsëri në diagramin tonë të vogël të drejtë këtu, me të vërtetë, e vetmja gjë që pamë ndodh kur kemi thirrur pop ishte se këtë madhësi rënë, së pari për 2, pastaj në 1. Atëherë kur kemi shtyrë një element të ri në, ajo do të shkojë në në vend të duhur. [Basil] Nëse s.size është 2, atëherë nuk do të shkojnë në elementin 2, dhe pastaj ju do të dëshironi të pop atë element off? Pra, nëse kemi shkuar në - >> Pra, le të shohim në këtë përsëri. Nëse kjo është rafte tonë në këtë pikë dhe ne e quajmë pop, në të cilën indeksi është më i lartë element? [Basil] Në 2, por ajo do të pop 3. E drejta >>. Pra, kjo është ajo ku madhësia tonë është 3, por ne duam të pop elementin në indeksin 2. Është kjo lloj tipik i shtyrë nga një që ju keni me zero indeksimin e vargjeve. Pra, ju nuk doni të pop elementin e tretë, por elementi i tretë nuk është në indeks 3. Dhe arsyeja që ne nuk kemi për të bërë këtë 1 minus, kur ne jemi duke kërkuar është për shkak të drejtë tani, ju vëreni se top-më element, në qoftë se ne do të shtyjë diçka tjetër mbi rafte në këtë pikë, Ne do të duan të shtyjë atë në indeks 3. Dhe kjo ndodh pikërisht kështu që madhësia dhe indekset vijë deri kur ju jeni duke kërkuar. 

Kush e mori një zbatim të punës rafte? Ju keni marrë një pirg të punës një. A keni pop punuar akoma? [Daniel] Po. Unë mendoj kështu. Programi >> është drejtimin dhe jo seg përgënjeshtrojnë, ajo shtypjen jashtë? E bën atë të shtypura nga "suksesi" kur ju drejtuar atë? Po. Bëni rafte, e drejtuar atë, nëse ajo printon nga "suksesin" dhe nuk shkojnë bum, atëherë të gjitha është e mirë. Dakord. Le të shkojnë mbi të aparatit të vërtetë shpejt, dhe ne do të ecin nëpër këtë. Nëse ne shikojmë se çfarë po ndodh këtu me pop, Daniel, çfarë ishte gjëja e parë që ju bëri? [Daniel] Nëse s.size është më e madhe se 0. [Hardison] Okay. Dhe pse e keni bërë këtë? [Daniel] Për të bërë të sigurtë se nuk ishte diçka brenda rafte. [Hardison] Drejta. Ju dëshironi për të provuar për të siguruar që s.size është më i madh se 0; ndryshe, çfarë ju doni të keni ndodhë? [Daniel] null Kthehuni? Kthehu >> null, pikërisht. Pra, nëse s.size është më e madhe se 0. Atëherë çfarë do të shkojmë për të bërë? Çfarë bëjmë ne nëse nuk rafte është bosh? [Stella] Ju pakësim madhësinë? Ju pakësim >> madhësinë, në rregull. Pra, si e keni bërë këtë? S.size >>--. [Hardison] Madhe. Dhe pastaj çfarë keni bërë? [Stella] Dhe atëherë kam thënë kthimi s.string [s.size]. [Hardison] Madhe. Përndryshe ju kthehen null. Po, Sam? [Sam] Pse nuk ka nevojë të jetë s.size + 1? [Hardison] Plus 1? Po >>. Got >> atë. [Sam] Mendova se për shkak se ju jeni duke marrë 1 nga, atëherë ju do të jeni të kthimit jo atë që ata kanë kërkuar për të. [Hardison] Dhe kjo ishte vetëm ajo që ne ishim duke folur në lidhje me këtë çështje të gjithë 0 indekseve. Pra, nëse ne zoom prapa gjatë këtu. Nëse ne shikojmë në këtë djalë të drejtë këtu, ju mund të shihni se kur ne pop, ne jemi popping elementin në indeksin 2. 

Pra, ne të ulur madhësinë tonë të parë, atëherë madhësia tonë përputhet me indeksin tonë. Nëse ne nuk pakësim madhësinë parë, atëherë ne duhet të bëjmë madhësinë -1 dhe pastaj pakësim. Madhe. Të gjithë të mirë? Çdo pyetje në këtë? Ka një numër mënyrash të ndryshme për të shkruar këtë si. Në fakt, ne mund të bëjmë diçka edhe - ne mund të bëjmë një një avion i linjës-. Ne mund të bëjmë një kthim të një-line. Pra, ne mund të vërtetë pakësim përpara se ne të kthehen duke bërë atë. Pra, duke the - para s.size. Kjo e bën të vijë me të vërtetë të dendura. Ku dallimi në mes të madhësisë - dhe s. S.size-- është se kjo postfix - ata e quajnë atë postfix sepse - vjen pas s.size-- do të thotë se s.size është vlerësuar për qëllime të gjetur indeksin e ashtu siç është aktualisht, kur kjo linjë është ekzekutuar, dhe pastaj kjo - ndodhë pas linjës merr ekzekutuar. Pas elementi në s.size indeksi është në disponim. Dhe kjo nuk është ajo që ne duam, sepse ne duam që pakësim të ndodhë parë. Othewise, ne jemi duke shkuar për të hyrë në rrjet, në mënyrë efektive, jashtë caqeve. Ne jemi duke shkuar për të hyrë në elementin mbi atë që ne të vërtetë duan për të hyrë. Yeah, Sam? A është e shpejtë >> ose përdorin RAM më pak për të bërë në një linjë apo jo? [Hardison] Sinqerisht, me të vërtetë varet. [Sam, i pakuptueshëm] >> Yeah, kjo varet. Ju mund të bëni truket përpiluesit për të marrë përpiluesit që të njohin se, zakonisht, unë imagjinohet. 

Pra, ne kemi përmendur pak në lidhje me këtë stuff optimization përpiluesit që ju mund të bëni në hartimin, dhe kjo është lloj gjë që një përpilues mund të jetë në gjendje të kuptoj, si oh, hej, ndoshta unë mund ta bëjë këtë të gjitha në një operacion, në krahasim me ngarkimin e ndryshueshme me permasa në nga RAM, decrementing atë, ruajtjen atë nga mbrapa, dhe pastaj ngarkuar atë përsëri në përsëri të procesit vazhdimin e këtij operacioni. Por zakonisht, jo, kjo nuk është gjë e tillë që do të bëjë programin tuaj në mënyrë të konsiderueshme më të shpejtë. Ndonjë pyetje më shumë në oxhaqet? 

Pra, shtyjnë dhe popping. Në qoftë se ju djema doni të provoni edicionin e hacker, atë që ne kemi bërë në edicionin e hacker është zhdukur në fakt dhe e bëri këtë rafte të rritet në mënyrë dinamike. Sfida nuk është kryesisht deri këtu në funksion shtytje, të kuptoj se si për të bërë që të rritet array si ju mbani shtyjnë elemente gjithnjë e më shumë për të rafte. Kjo nuk është në fakt Kodi shumë shtesë. Vetëm një thirrje për të - ju duhet të mbani mend për të marrë thirrjet për malloc në atje duhet, dhe pastaj të kuptoj se kur ju jeni duke shkuar për të thirrur realloc. Kjo është një sfidë fun në qoftë se ju jeni të interesuar. 

Por, për momentin, le të lëvizë, dhe le të flasim për radhët e gjata. Lëviz nëpër këtu. Radhë të është një vëlla i ngushtë i rafte. Pra, në rafte, gjërat që janë vënë në fundit ishin gjërat e para që pastaj të shikohet. Ne kemi marrë këtë të fundit në, së pari jashtë, apo LIFO, urdhërimin. Ndërsa në radhë, si ju do të presim nga kur ju jeni duke qëndruar në vijë, personi i parë për të marrë në përputhje, gjëja e parë për të marrë në radhë, është gjëja e parë që merr marrë nga radhë. Radhët janë përdorur edhe shpesh kur ne jemi që kanë të bëjnë me grafikët, si kemi biseduar për një kohë të shkurtër me oxhaqet, dhe radhët e gjata janë të dobishëm edhe për një bandë e gjëra të tjera. Një gjë që vjen deri shpesh është duke u përpjekur për të ruajtur, për shembull, një listë të renditura nga elementet. Dhe ju mund ta bëjë këtë me një grup. Ju mund të mbajë një listë të renditura të gjërave në një grup, por ku se merr ndërlikuar është atëherë ju gjithmonë keni për të gjetur vendi i duhur për të futur gjë tjetër. Pra, nëse ju keni një rrjet të numrave, 1 deri 10, dhe pastaj ju doni të zgjeruar që të gjitha numrat 1 deri 100, dhe ju jeni duke marrë këto numra në mënyrë të rastit dhe duke u përpjekur për të mbajtur gjithçka renditura si ju shkoni nëpër, ju deri në fund që të bëjë një shumë të zhvendosur. Me lloje të caktuara të radhëve dhe llojeve të caktuara të strukturave të të dhënave themelore, ju mund të mbani atë të vërtetë mjaft e thjeshtë. Ju nuk keni për të shtuar diçka dhe pastaj të riorganizojë gjithë gjë çdo kohë. As nuk keni për të bërë një shumë të zhvendosur nga elementet e brendshme rreth. Kur ne shikojmë në një radhë, ju shihni se - edhe në queue.c në kodin seksionin - the struct që ne kemi dhënë ty është me të vërtetë e ngjashme me struct që ju dha për një pirg. 

Ka një përjashtim për këtë, dhe se një përjashtim është se ne kemi këtë numër të plotë shtesë të quajtur kreu, dhe kreu këtu është për të mbajtur gjurmët e kreut të radhë, ose elementi i parë në radhë. Me një pirg, ne ishim në gjendje të mbajnë gjurmët e elementit se ne ishim gati për të tërhequr, ose në krye të rafte, duke përdorur vetëm madhësinë, ndërsa me radhë, ne jemi që të merren me skajet e kundërta. Ne jemi duke u përpjekur për të gjëra në litar në fund, por pastaj kthehen gjërat nga e para. Mënyrë efektive, me kokë, ne kemi indeksin e fillimit të radhë, dhe madhësia na jep indeksin e fund të rreshtit kështu që ne mund të marrim gjërat nga koka dhe shtoni gjëra në të bisht. Kurse me rafte, ne ishim vetëm ndonjëherë kanë të bëjnë me pjesën e sipërme të rafte. Ne kurrë nuk kishte për të hyrë në pjesën e poshtme të rafte. Ne vetëm shtuar gjëra në krye dhe mori gjërat off krye kështu që ne nuk duhet të këtë fushë ekstra brenda struct tonë. Bën që në përgjithësi ka kuptim? Dakord. Po, Charlotte? [Charlotte, pakuptueshëm] [Hardison] Kjo është një pyetje e madhe, dhe kjo ishte ajo që erdhi deri në leksion. Ndoshta duke ecur nëpër disa shembuj do të ilustrojnë pse ne nuk duam të përdorni vargjet [0] si kreu i radhës. 

Pra, imagjinoni që ne kemi radhën tonë, ne jemi duke shkuar për të thirrur atë radhë. Në fillim, kur ne kemi instantiated vetëm atë, kur ne kemi deklaruar vetëm atë, ne nuk kemi nisur asgjë. Kjo është e gjitha mbeturinave. Pra, natyrisht ne duam të sigurohemi që ne inicializoj si madhësia dhe fusha kokë të jetë 0, diçka arsyeshme. Ne gjithashtu mund të shkoni përpara dhe të pavlefshme nga elementet në radhë tonë. Dhe për të bërë këtë të arsyeshme diagram, vëreni se tani queue ynë mund të mbajë vetëm tre elemente; whereas rafte tonë mund të mbajë katër, radhë tonë mund të mbajë vetëm tre. Dhe kjo është vetëm për të bërë arsyeshme diagram. Gjëja e parë që ndodh këtu është se ne enqueue vargun "hi". Dhe ashtu si ne e bëmë me rafte, asgjë tmerrësisht të ndryshme këtu, ne vargun hedhin më në vargjet [0] dhe rritje madhësinë tonë nga 1. Ne enqueue "bye", kjo merr të vënë në. Pra, kjo duket si një pirg për pjesën më të madhe. Ne filloi këtu, element të ri, element i ri, madhësia e mban duke shkuar deri. Çfarë ndodh në këtë moment, kur ne duam të dequeue diçka? Kur ne duam të dequeue, e cila është elementi që ne duam të dequeue? [Basil] Strings [0]. Zero >>. Saktësisht e drejtë, Vasili. Ne duam që të heqin qafe e vargut të parë, kjo një, "hi". Pra, çfarë ishte gjëja tjetër që ndryshoi? Njoftim kur ne popped off diçka e rafte, ne vetëm ndryshuar madhësinë, por këtu, ne kemi marrë një disa gjëra që ndryshimi. Jo vetëm që e bën ndryshimin e madhësisë, por ndryshimet në kokë. Kjo është kthim prapa në pikën e mëhershme Charlotte: pse nuk kemi kete kokën si? A ka kuptim tani, Charlotte? Kind >> i. [Hardison] Lloji i? Pra, çfarë ndodhi kur ne dequeued? Çfarë ka bërë kreu se tani është interesante? [Charlotte] Oh, sepse ajo ndryshoi - rregull. Të kuptoj. Sepse kreu - ku kreu është duke treguar ndryshime në aspektin e lokacionit. Ajo nuk është më një zero gjithmonë indeksi. Po >>, pikërisht. Çfarë ndodhi ishte nëse dequeueing elementin e lartë është bërë dhe ne nuk kemi këtë fushë kokë sepse ne ishin gjithmonë duke e quajtur këtë varg në 0 indeksin kreu i radhës tonë, atëherë ne do të duhet të zhvendoset në pjesën tjetër të radhës poshtë. Ne do të duhet të zhvendoset "bye" nga nga vargjet [1] me vargjet [0]. Dhe vargjet [2] deri në vargjet [1]. Dhe ne do të duhet për të bërë këtë për të gjithë listën e elementeve, array tërë elementeve. Dhe kur ne jemi duke e bërë këtë me një grup, që merr me të vërtetë i kushtueshëm. Pra këtu, kjo nuk është një punë e madhe. Ne vetëm kemi tre elemente në grup tonë. Por në qoftë se kemi pasur një radhë prej një mijë elementeve ose një milion elemente, dhe pastaj të gjithë një e papritur, ne të fillojnë të bëjnë një bandë e dequeue thirrje të gjitha në një lak, gjërat janë me të vërtetë duke shkuar për të ngadalësuar si ajo kalon gjithçka poshtë vazhdimisht. Ju e dini, zhvendoset nga 1, zhvendosje nga 1 ndryshim, me 1, zhvendosje nga 1. Në vend të kësaj, ne e përdorim këtë kokë, ne e quajmë atë një "tregues", edhe pse kjo nuk është me të vërtetë një akrep në kuptimin e ngushtë, por nuk është një lloj treguesi. Kjo nuk është një int * ose * char apo diçka të tillë. Por ajo është vënë, ose duke treguar kokën e radhës tonë. Po? 

[Student] Si dequeue di për vetëm pop jashtë çdo gjë që është në krye? [Hardison] Si nuk dequeue di se si të pop jashtë çdo gjë që është në krye? E drejta >>, yeah. Çka >> ajo duke kërkuar në çdo gjë është vetëm fusha kokë është e vendosur për të. Pra, në këtë rastin e parë, nëse ne shikojmë drejtë këtu, kreu ynë është 0, 0 indeksi. E drejta >>. [Hardison] Pra, ai vetëm i thotë në rregull, mirë, elementi në indeksin 0, string "hi", është elementi në krye të radhës tonë. Pra, ne jemi duke shkuar për dequeue atë djalë. Dhe kjo do të jetë element që merr kthyer në telefonuesi. Po, Saad? Kështu >> kreu në thelb përcakton - ku ju do të jeni Indeksi atë? Kjo është fillimi i saj? Po >>. Mirë >>. [Hardison] Kjo është bërë fillim i ri për grup tonë. Kështu që kur ju dequeue diçka, të gjithë ju duhet të bëni është të hyni në elementin në indeks q.head, dhe që do të jetë element që ju doni të dequeue. Ju gjithashtu duhet të pakësim madhësinë. Ne do të shohim në një grimë ku gjërat marrin pak e ndërlikuar me këtë. Ne dequeue, dhe tani, në qoftë se ne enqueue përsëri, ku nuk kemi enqueue? Ku ka element tjetër shkojnë në radhë tonë? Thonë se ne duam të enqueue string "CS". Në të cilën indeksi do të shkojë? [Studentët] Spangot [2]. Dy >>. Pse 2 dhe jo 0? [Basil] Sepse tani koka është 1, kështu që është si në fillim të listës? [Hardison] Drejta. Dhe çfarë tregon në fund të listës? Çfarë ishin ne duke përdorur për të treguar fundin e radhës tonë? Kreu është kreu i queue tonë, fillimi i radhës tonë. Çfarë është fundi i radhës tonë? [Studentët] Madhësi. Size >>, pikërisht. Pra, elementet tona të reja të shkojë në në madhësi, dhe elementët që kemi marrë off vijnë jashtë në krye. Kur ne enqueue element tjetër, ne jemi vënë atë në në madhësi. [Student] Para se të vendosni se në pse, madhësia ishte 1, e drejtë? [Hardison] Drejta. Pra, nuk është krejt në madhësi. + Madhësia nuk, 1, por kreu +. Sepse ne u zhvendos gjithçka nga shuma kokë. Kështu që këtu, tani ne kemi marrë një radhë të madhësisë 1 që fillon në indeksin 1. Bishti është indeksi 2. Po? 

[Student] Çfarë ndodh kur ju dequeue strings [0], si dhe lojëra elektronike strings 'në kujtesë vetëm merrni zbrazur, në thelb, apo harruar thjesht? [Hardison] Yeah. Në këtë kuptim, ne jemi vetëm duke harruar ato. Në qoftë se ne u ruajtjen kopjet e tyre për - shumë të dhëna strukturat shpesh do të ruajë kopjet e tyre të elementeve në mënyrë që personi i cili udhëheq me strukturën e të dhënave nuk ka për t'u shqetësuar rreth ku të gjitha këto pointers janë duke shkuar. Struktura e të dhënave mban më për gjithçka, mban në të gjitha kopjet, për t'u siguruar që gjithçka vazhdon të përshtatshme. Megjithatë, në këtë rast, këto struktura të dhënave vetëm, për thjeshtësi, nuk janë bërë kopje të çdo gjë që ne jemi ruajtjen në to. [Student] Pra, kjo është një grup i vazhdueshëm i -? Po >>. Nëse ne shikojmë prapa në atë që ishte përkufizimi i kësaj strukture, ajo është. Kjo është vetëm një array standarde si ju kam parë, një grup i char * s. Bën që -? >> Yeah, unë isha vetëm pyesin në qoftë se ju do të përfundimisht të drejtuar nga e kujtesës, në një masë të caktuar, në qoftë se ju keni të gjitha këto vende bosh në rrjet tuaj? [Hardison] Yeah, kjo është një pikë e mirë. 

Nëse ne shikojmë se çfarë ka ndodhur tani në këtë pikë, ne kemi mbushur radhën tonë, duket si. Por ne nuk kemi plotësuar të vërtetë deri radhën tonë sepse ne kemi një radhë që është madhësia 2, por ajo fillon në indeksin e 1, sepse kjo është ajo ku pointer tonë kokë është. Si ju janë duke thënë, se elementi në vargjet [0], në indeksin e 0, nuk është me të vërtetë atje. Kjo nuk është në radhë tonë më. Ne thjesht nuk u mërzit për të shkuar në dhe të prishësh atë kur ne dequeued atë. Pra, edhe pse duket sikur ne kemi dalë jashtë kujtesës, ne me të vërtetë nuk kanë. Kjo spot është në dispozicion për ne për t'u përdorur. Sjellja e përshtatshme, në qoftë se ne do të përpiqemi dhe të parë diçka dequeue si "bye", që do të pop bye off. Tani queue tonë fillon në indeksin 2 dhe është i madhësisë 1. Dhe tani, nëse ne përpiqemi dhe enqueue diçka përsëri, të themi 50, 50 duhet të shkojë në këtë vend në indeks 0 për shkak se ajo është ende në dispozicion për ne. Po, Saad? [Saad] A që të ndodhë automatikisht? [Hardison] Kjo nuk ndodh mjaft automatikisht. Ju duhet të bëni matematikë për ta bërë atë punë, por në thelb ajo që ne kemi bërë është që ne kemi përfundoi vetëm rreth. [Saad] Dhe është në rregull në qoftë se kjo ka një vrimë në mes të saj? [Hardison] Kjo është në qoftë se ne mund të bëjë matematikë të punojnë si duhet. 

Dhe kjo rezulton se kjo nuk është e vërtetë se e vështirë për të bërë me operatorin mod. Pra, ashtu si ne e bëmë me Cezarin dhe sende crypto, duke përdorur mod, ne mund të merrni gjëra të përfundojë rreth dhe do të mbajë përreth dhe rreth e rreth me radhë tonë, mbajtur treguesin që kreu lëvizin përreth. Vini re se madhësia është gjithmonë duke respektuar numrin e elementeve të vërtetë brenda radhë. Dhe kjo është vetëm tregues koka që mban çiklizmit përmes. Nëse ne shikojmë se çfarë ka ndodhur këtu, në qoftë se ne të kthehemi në fillim, dhe ju vetëm shikojnë se çfarë ndodh në kokë kur ne enqueue diçka, asgjë nuk ka ndodhur në kokë. Kur ne enqueued diçka tjetër, asgjë nuk ka ndodhur në kokë. Më shpejt që ne dequeued diçka, kreu shkon deri nga një. Ne enqueued diçka, asgjë nuk ndodh në kokë. Kur ne dequeue diçka, të gjithë një e papritur kreu merr incremented. Kur ne enqueue diçka, asgjë nuk ndodh në kokë. 

Çfarë do të ndodhë në këtë pikë në qoftë se ne do të dequeue diçka përsëri? Çdo mendime? Çfarë do të ndodhë në kokë? Çfarë duhet të ndodhë në kokë në qoftë se ne do të dequeue diçka tjetër? Kreu tani është në indeksin 2, që do të thotë se koka e radhë është vargjet [2]. [Student] Cili kthen 0? Ajo duhet të >> kthehet në 0. Ajo duhet të përfundojë prapa përreth, pikërisht. Deri tani, çdo herë kemi quajtur dequeue, ne kemi qenë duke shtuar një në kokë, shtoni një në kokë, shtoni një në kokë, shtoni një në kokë. Sa më shpejt që pointer kreu merr në indeksin e fundit në grup tonë, atëherë ne kemi për të përfunduar atë rreth në fillim, të shkojnë prapa në 0. [Charlotte] Çfarë përcakton kapacitetin e radhës në një pirg? [Hardison] Në këtë rast, ne kemi qenë vetëm duke përdorur një konstante definuar #. Mirë >>. [Hardison] Në dosjen aktuale. C, ju mund të shkoni në dhe pleh me atë pak dhe të bëjë atë sa më i madh ose sa pak si ju dëshironi. [Charlotte] Pra, kur ju jeni duke e bërë atë një radhë, si ju të bëjë kompjuteri e di sa i madh ju doni rafte të jetë? [Hardison] Kjo është një pyetje e madhe. Ka disa mënyra. Njëra është që të përcaktojë vetëm atë front dhe thonë se kjo do të jetë një radhë që ka 4 elementë ose elemente të 50 ose 10.000. Mënyra tjetër është të bëjë atë folks botim janë bërë hacker dhe për të krijuar funksione të deshiroja queue tuaj të rriten në mënyrë dinamike, si të merrni më shumë gjëra shtoi in 

[Charlotte] Pra, për të shkuar me opsionin e parë, çfarë ju përdorni sintaksë për të të treguar se çfarë programi është madhësia e radhës? [Hardison] Ah. Pra, le të marrë nga kjo. Unë jam ende në stack.c këtu, kështu që unë jam vetëm do të shkoni deri në majë këtu. Ju mund të shihni këtë të drejtë këtu? Kjo është # define kapacitet 10. Dhe kjo është pothuajse e saktë të njëjtën sintaksë që ne kemi për radhë. Përveç në radhë, ne kemi marrë këtë fushë ekstra struct këtu. [Charlotte] Oh, mendova se kapaciteti do të thotë aftësinë për vargun. [Hardison] Ah. Kjo >> është gjatësia maksimale e fjalës. Got >> atë. Po. Kapaciteti këtu - kjo është një pikë e madhe. Dhe kjo është diçka që është e ndërlikuar sepse ajo që ne kemi këtu është deklaruar një grup i char * s. Një grup i pointers. Ky është një grup i karaktere. Kjo është ndoshta ajo që keni parë kur ju keni qenë duke deklaruar mbulesë tuaja për dosjen e I / O, kur ju keni qenë duke krijuar vargje dorë në rafte. Megjithatë, ajo që ne kemi marrë këtu është një grup i char * s. Pra, kjo është një grup i pointers. Në fakt, në qoftë se ne zoom nga mbrapa dhe ne shikojmë se çfarë po ndodh këtu në prezantim, ju shihni se elementet aktuale, të dhënat karakter nuk është ruajtur në rrjet vetë. Çfarë është ruajtur brenda array tonë këtu janë pointers për të dhënat e karakterit. Rregull. Pra, ne kemi parë se si madhësia e radhës është vetëm si me rafte, madhësia gjithmonë respekton numrin e elementeve aktualisht në radhë. Pas marrjes enqueues 2, madhësia është 2. Pasi bën një dequeue madhësisë është tani 1. Pas marrjes tjetër enqueue madhësia është kthyer deri në 2. Pra, madhësia definitely respekton numrin e elementeve në radhë, dhe pastaj kreu vetëm mban çiklizmit. Ajo shkon nga 0-1-2, 0-1-2, 0-1-2. Dhe çdo herë që ne e quajmë dequeue, tregues kreu merr incremented për indeksin e ardhshëm. Dhe në qoftë se koka është gati të shkojë gjatë, ajo kthehet rreth për të sythe 0. Pra, me këtë, ne mund të shkruani funksionin dequeue. Dhe ne jemi duke shkuar për të lënë funksionin enqueue për ju djema për të zbatuar në vend. 

Kur ne dequeue një element nga radhë tonë, çfarë ishte gjëja e parë që bëri kur ne Danieli filloi të shkruajë funksionin pop për oxhaqet? Më lejoni të dëgjojë nga dikush i cili nuk ka folur ende. Le të shohim, Saad, a ju kujtohet se çfarë bëri Daniel si gjëja e parë kur ai shkroi pop? [Saad] Nuk ishte, ai ishte - >> Ai testuar për diçka. [Saad] Nëse madhësia është më e madhe se 0. Pikërisht >>. Dhe çfarë ishte se testimi për të? [Saad] Kjo ishte testuar për të parë nëse ka ndonjë gjë brenda array. [Hardison] Yeah. Saktësisht. Pra, ju nuk mund të pop asgjë nga rafte nëse është e zbrazët. Gjithashtu, ju nuk mund të dequeue asgjë nga një radhë nëse është e zbrazët. Çfarë është gjëja e parë që ne duhet të bëjmë në funksion tonë dequeue këtu, mendoni ju? [Saad] Nëse madhësia është më e madhe se 0? Po >>. Në këtë rast, unë kam testuar në fakt vetëm për të parë nëse ajo është 0. Në qoftë se kjo është 0, ne mund të kthehen null. Por logjika e saktë të njëjtën. Dhe le të vazhdojmë me këtë. Nëse madhësia nuk është 0, ku është element që ne duam të dequeue? [Saad] Në krye? Pikërisht >>. Ne vetëm mund të tërhiqet nga elementin e parë në radhë tonë duke hyrë në elementin në kokë. Asgjë çmendur. Pas kësaj, çfarë duhet të bëjmë? Çfarë duhet të ndodhë? Cila ishte gjëja tjetër që kemi biseduar rreth në dequeue? Dy gjëra duhet të ndodhin, sepse radhë ynë ka ndryshuar. [Daniel] zvogëluar madhësinë. Ne kemi >> për të zvogëluar madhësinë, dhe për të rritur kokën? Saktësisht. Për të rritur kokën, ne nuk mund vetëm verbërisht rrisin kokën, mos harroni. Ne nuk mund të bëjmë vetëm queue.head + +. Ne duhet të përfshijë edhe këtë mod nga kapaciteti. Dhe pse nuk kemi mod nga kapaciteti, Stella? [Stella] Për shkak se ajo ka për të përfunduar rreth. Pikërisht >>. Ne mod nga kapaciteti, sepse ai ka për të përfunduar përsëri rreth të 0. Deri tani, në këtë pikë, ne mund të bëjmë atë që tha Daniel. Ne mund pakësim madhësinë. Dhe atëherë ne vetëm mund të kthehen element që ishte në krye të rreshtit. Ajo duket lloj i gunga në fillim. Ju mund të keni një pyetje. Na vjen keq? 

[Sam] Pse e parë në krye të radhës? Ku do që të shkojnë? [Hardison] Ajo vjen nga linja e katërt nga fundi. Pasi kemi provuar për të siguruar që queue ynë nuk është i zbrazët, Ne tërhiqet nga * char parë, ne të tërhiqet nga elementi që është ulur në indeksin kokë e array tonë, të strings tonë, >> array dhe thirrjen që parë? [Hardison] Dhe ne e quajmë atë më parë. Po. Vetëm për të ndjekur deri në atë, pse mendoni ju se ne kishim për të bërë këtë? [Sam] Secili parë është vetëm kthimi q.strings [q.head]? Po >>. Sepse >> ne jemi duke bërë këtë ndryshim të q.head me funksionin mod, dhe nuk ka mënyrë për të bërë që brenda vijës kthimit gjithashtu. [Hardison] Pikërisht. Ju jeni në vend. Sam krejtësisht vend në. Arsyeja na u desh të largohen nga elementin e parë në radhë tonë dhe ruajtur atë në një variabël është për shkak se këtë linjë, ku kishim q.head vetëm, ka operatori mod aty nuk është diçka që ne mund të bëjmë dhe e kanë atë të hyjë në fuqi në kokë pa - në një linjë. Pra, ne në fakt duhet të tërhiqet nga elementin e parë, pastaj të rregulluar kokën, rregulluar madhësinë, dhe pastaj të kthehen element që u larguan jashtë. Dhe kjo është diçka që ne do të shohim të dalë më vonë me Listat e lidhura, si ne të luajnë rreth me ta. Shpesh kur ju jeni liruar ose asgjësimin e listave të lidhur ju duhet të mbani mend element tjetër, tregues tjetër i një liste të lidhur para depozitimin e një aktuale. Sepse përndryshe ju hedhin larg informacionin e asaj që ka mbetur në listë. Tani, në qoftë se ju shkoni në aplikim tuaj, ju hapur deri queue.c--x nga kjo. Pra, nëse unë i hapur deri queue.c, më lejoni të zoom në këtu, ju do të shihni se ju keni një fotografi të ngjashme-looking. Ngjashëm-looking file për atë që kemi pasur më parë me stack.c. Ne kemi marrë struct tonë për të përcaktuar radhën ashtu siç e pamë në slides. 

Ne kemi funksionin tonë enqueue e cila është për ju për të bërë. Dhe ne kemi funksionin dequeue këtu. Funksioni dequeue në dosjen e pazbatuar, por unë do të vënë atë përsëri deri në PowerPoint në mënyrë që ju mund të shtypni në atë, në qoftë se ju dëshironi. Pra, për 5 minuta e ardhshme apo më shumë, ju djema të punojnë në enqueue e cila është pothuajse e kundërta e dequeue. Ju nuk keni për të rregulluar kokën kur ju jeni enqueueing, por çfarë ju duhet për të rregulluar? Size. Kështu që kur ju enqueue, kreu qëndron i paprekur, madhësia merr ndryshuar. Por ajo ka marrë një pak - ju do të duhet të luajnë rreth me këtë mod të kuptoj se pikërisht ajo që indeksi elementi i ri duhet të futet në. Kështu që unë do të ju jap djema pak, vendos dequeue mbrapa deri në rrëshqitje, dhe si ju djema keni pyetje, bërtasin ata jashtë në mënyrë që ne të mund të të gjithë flasin rreth tyre si një grup. Gjithashtu, me madhësi që ju don 't - kur ju të rregulluar madhësinë, ju mund gjithmonë vetëm - ju keni për të mod madhësinë ndonjëherë? [Daniel] nr >> Ju nuk keni për të mod madhësinë, të drejtë. Sepse madhësia gjithmonë do të, nëse you're - duke supozuar që ju jeni menaxhimin e gjëra të përshtatshme, madhësia gjithmonë do të jetë në mes 0 dhe 3. Ku keni për mod, kur ju jeni duke bërë enqueue? [Student] Vetëm për kokë. Vetëm >> për kokë, pikërisht. Dhe pse nuk ju keni për të mod fare në enqueue? Kur është një situatë në të cilën ju do të keni për mod? [Student] Nëse ju keni gjëra në hapësirat, si në hapësirat 1 dhe 2, dhe pastaj ju nevojitet të shtoni diçka në 0. [Hardison] Po, pikërisht. Pra, nëse kursori juaj është e kreu në fund, ose në qoftë se madhësia tuaj plus koka juaj është e madhe, ose më mirë, do të përfundojë rreth radhë. 

Pra, në këtë situatë që ne kemi marrë deri këtu në rrëshqitje të drejtë tani, në qoftë se unë dua të enqueue diçka të drejtë tani, ne duam të enqueue diçka në indeksin 0. Pra, nëse ju shikoni në ku 50 shkon, dhe unë e quaj enqueue 50, ajo shkon atje poshtë në pjesën e poshtme. Ajo shkon në 0 indeksit. Ajo zëvendëson 'hi' që u dequeued tashmë. [Daniel] A nuk kujdeset që në dequeue tashmë? Pse e bën atë të bëjë asgjë me kokë në enqueue? [Hardison] Oh, kështu që ju nuk jeni modifikuar kokën, sorry. Por ju duhet të përdorni operatorin mod kur ju jeni të hyrë elementi që ju doni të enqueue kur ju jeni të hyrë element tjetër në radhë tuaj. [Basil] Unë nuk e ka bërë këtë, dhe kam marrë "sukses" në atje. [Daniel] Oh, unë e kuptoj se çfarë ju jeni duke thënë. [Hardison] Pra, ju didn't - ju vetëm e bëri në q.size? [Basil] Yeah. Unë thjesht ndryshuar anët, unë nuk kam bërë asgjë me kokë. [Hardison] Ju nuk mund të vërtetë kanë për të rivendosur kokën të jetë çdo gjë, por kur indeksi në grup strings, ju në të vërtetë duhet të shkoni përpara dhe të llogaritur ku elementi tjetër është, sepse lidh me thupra rafte, element tjetër në rafte tuaj ka qenë gjithmonë në indeksit korresponduese të madhësisë. Nëse ne shikojmë prapa deri në funksion shtytje tonë rafte, ne mund gjithmonë bie në elementin tonë të ri të drejtë në madhësinë e indeksit. Kurse me radhë, ne nuk mund ta bëjë këtë sepse në qoftë se ne jemi në këtë situatë, në qoftë se ne enqueued 50 vargu ynë i ri do të shkojë drejtë në vargjet [1] që ne nuk duam të bëjmë. Ne duam të kemi string ri të shkojnë në indeksin 0. 

Dikush bën - po? [Student] Unë kam një pyetje, por kjo nuk është e lidhur me të vërtetë. Çfarë do të thotë kur dikush e quan thjesht diçka si treguesin pred? Çfarë është që emri të shkurtër për të? Unë e di se është vetëm një emër. [Hardison] akrep pred? Le të shohim. Në çfarë konteksti? [Student] Kjo ishte për të futur. Unë mund të ju pyes më vonë në qoftë se ju doni sepse ajo nuk është e lidhur me të vërtetë, por unë vetëm - [Hardison] Nga kodin e Davidit insert nga leksioni? Ne mund të tërheqë atë dhe të flasin për këtë. Ne do të flasim për këtë më tej, pasi ne kemi marrë për listat e lidhura. 

Pra, le të vërtetë shpejt shikojmë se çfarë funksioni enqueue duket si. Cila ishte gjëja e parë që njerëzit u përpoq të bëjë në përputhje tuaj enqueue? Në këtë radhë? Ngjashme me atë që keni bërë për të rafte shtyjnë. Çfarë keni bërë, Stella? [Stella, pakuptueshëm] [Hardison] Pikërisht. Në qoftë se (== q.size KAPACITETIT) - Unë kam nevojë për të vënë formatimin e teksteve e mia në vendin e duhur - të kthehen rreme. Zoom në një pak. Rregull. Tani ajo është gjëja tjetër që ne kishim për të bërë? Ashtu si me rafte, dhe futur në vendin e duhur. Dhe kështu ajo ishte vendi i duhur për të futur këtë? Me rafte ajo ishte madhësinë indeksi, me këtë nuk është mjaft që. [Daniel] Unë kam q.head--ose - q.strings >>? >> Yeah. q.strings [q.head + q.size mod KAPACITETEVE]? [Hardison] Ne ndoshta do të duan të vënë kllapa rreth kësaj kështu që ne jemi duke marrë përparësi e duhur dhe kështu që është cleart për të gjithë. Dhe të vendosur që të barabartë? Për >> rr? Për >> rr. Madhe. Dhe tani çfarë është gjëja e fundit që ne duhet të bëjmë? Ashtu si ne e bëmë në rafte. Rritja >> madhësinë? Rritja >> madhësinë. Boom. Dhe pastaj, pasi që kodi starter sapo u kthye rreme by default, ne duam të ndryshojmë këtë të vërtetë në qoftë se të gjitha shkon nëpër dhe të gjitha shkon mirë. Dakord. Kjo është një shumë e informacionit për seksion. Ne nuk jemi mjaft të gjatë. Ne duam të flasim me të vërtetë shpejt për formë individuale-lidhura listat. Unë do të vënë këtë deri kështu që ne mund të kthehemi në atë më vonë. Por le të kthehemi në prezantimin tonë për vetëm disa më të slides. Pra enqueue është TODO, tani ne kemi bërë atë. 

Tani le të marrin një vështrim në formë individuale-lidhura listat. Ne biseduam në lidhje me këto pak më shumë në leksion. Sa nga ju djema pa demo ku kemi pasur njerëz awkwardly treguar çdo numra të tjerë dhe mbajtja? Unë isha në >> këtë. Çfarë >> mendoni ju djema? Bëri atë, shpresojmë qartësojmë këto pak pak? Me një listë, rezulton se të merremi me këtë lloj që ne jemi duke shkuar për të thirrur një nyje. Kurse me radhë dhe rafte kemi pasur structs se ne do të thërrasë radhë në rafte, kemi pasur këto radhë të ri në lloje të rafte, këtu është një listë me të vërtetë bërë vetëm nga një bandë e nyjave. Në të njëjtën mënyrë që vargjet janë vetëm një bandë e karaktere gjitha rreshtuar pranë njëri-tjetrit. Një listë e lidhur është vetëm një nyjë nyjë dhe një tjetër dhe një tjetër dhe një tjetër nyje nyje. Dhe në vend se goditja e të gjitha nyjet bashku dhe ruajtjen e tyre pranë njëri tjetrit të gjitha të drejtë tjetër për njëri-tjetrin në kujtesë, pasur këtë tregues tjetër na lejon për të ruajtur nyjet kudo, në mënyrë të rastësishme. Dhe pastaj lloj teli ata të gjithë së bashku për pikë nga njëri tjetri. 

Dhe çfarë ishte përparësi e madhe se kjo kishte mbi një grup? Mbi gjithçka ruajtjen pranë njëri tjetrit mbërthyer vetëm pranë njëri-tjetrit? Ju kujtohet? Po? Ndarja >> Dinamik kujtesës? Ndarja >> Dinamik kujtesës në çfarë kuptimi? [Student] Në se ju mund të mbani duke e bërë atë më të mëdha dhe ju nuk keni për të lëvizur rrjet tuaj të tërë? [Hardison] Pikërisht. Pra, me një grup, kur të doni për të vënë një element të ri në mes të tij, ju duhet të zhvendoset gjithçka për të bërë hapësirë. Dhe si kemi biseduar rreth me radhë, kjo është arsyeja pse ne kemi mbajtur atë treguesin kokë, kështu që ne nuk jemi vazhdimisht i ndryshueshëm gjëra. Për shkak se merr shtrenjtë nëse ju keni një koleksion të madh dhe ju jeni vazhdimisht duke bërë këto insertions të rastit. Ndërsa me një listë, të gjithë ju duhet të bëni është të hedhin atë në një nyje të re, rregulluar pointers, dhe ju jeni bërë. Çfarë sucks në lidhje me këtë? Përveç faktit se ajo nuk është aq e lehtë për të punuar me të si një grup? Po? [Daniel] E pra, unë mendoj se është shumë e vështirë për të hyrë në një element të veçantë në listën e lidhur? [Hardison] Ju nuk mund të hidhen në një element arbitrare në mes të listës suaj të lidhura. Si mund të ju duhet të bëni atë vend? >> Ju duhet të hap nëpër gjithë gjë. [Hardison] Yeah. Ju duhet të kalojnë nëpër një në një kohë, një në një kohë. Kjo është një i madh - kjo është një dhimbje. Çfarë është tjetër - ka tjetër Rënie për këtë. [Basil] Ju nuk mund të shkojnë përpara dhe prapa? Ju duhet të shkoni një drejtim? [Hardison] Yeah. Pra, si nuk kemi zgjidhur që, ndonjëherë? [Basil] dyfish-lidhur listave? Pikërisht >>. Nuk janë listat dyfish-lidhura. Ka edhe - keq? 

[Sam] A është kjo e njëjtë si duke përdorur gjë pred se - Unë vetëm kujtua, nuk është se çfarë gjë e pred është për? Nuk është se në mes dyfish dhe veçmas? Vështrim [Hardison] Le-së në çfarë saktësisht ai kishte bërë. Pra, këtu ne do të shkojmë. Ja kodi lista. Këtu kemi predptr, këtu. A është kjo ajo që ju jeni duke folur për? Pra, kjo ishte - ai është liruar një listë dhe ai është duke u përpjekur për të ruajtur një tregues për atë. Kjo nuk është dyfish, veçmas të lidhura-listat. Ne mund të flasim më shumë për këtë më vonë pasi që kjo po flet për çlirimin e listës dhe unë dua të tregoj disa sende të tjera të parë. por kjo është vetëm - kjo është kujtuar vlerën e PTR [Student] Oh, kjo është akrep atë paraprake? Po >>. Kështu që ne mund të, atëherë rritja ptr vetë para se atëherë lirë atë predptr është. Sepse ne nuk mund të ptr lirë dhe pastaj të telefononi ptr ptr = ardhshme, apo jo? Kjo do të jetë e keqe. Pra, le të shohim, përsëri në këtë djalë. 

Gjëja tjetër e keqe për listat është se ndërsa me një grup ne vetëm kemi të gjitha elementet e vetë bërë pirg pranë njëri-tjetrit, ketu ne gjithashtu kemi futur këtë tregues. Pra, ka një copë shtesë e kujtesës që ne jemi duke pasur nevojë të përdorin për çdo element që ne jemi ruajtjen në listën tonë. Ne kemi marrë fleksibilitet, por ajo vjen me një kosto. Ajo vjen me këtë kosto kohore, dhe ajo vjen me këtë kosto e kujtesës shumë. Koha në kuptimin që ne tani duhet të kalojnë nëpër çdo element në rrjet për të gjetur një në indeksin e 10, ose që do të kishte qenë indeksi i 10 në një grup. 

Vetëm me të vërtetë shpejt, kur ne diagram nga këto lista, në mënyrë tipike ne të mbajtur në të kokës së lista ose akrep parë të lista dhe vini re se kjo është një tregues i vërtetë. Është vetëm 4 bytes. Kjo nuk është një nyje aktuale vetë. Kështu që ju shihni se ai nuk ka asnjë vlerë int në të, nuk ka tregues tjetër në të. Kjo është fjalë për fjalë vetëm një tregues. Ajo do të tregojnë për diçka që është një struct aktuale nyje. [Sam] Një tregues quhet nyje? Kjo është >> - nr. Ky është një tregues për diçka të tipit nyje. Ajo është një akrep tek një struct node. >> Oh, në rregull. Diagrami në kodin e majtë, në të djathtë. Ne mund të vënë atë në, null cila është një mënyrë e mirë për të filluar. Kur ju diagram atë, ose ju shkruani atë si null ose ju vënë një linjë nëpër atë si kjo. 

Një nga mënyrat më të lehta për të punuar me listat, dhe ne ju kërkojmë të bëjë të dyja prepend dhe append për të parë dallimet në mes të dy, por prepending është padyshim më e lehtë. Kur ju prepend, kjo është ajo ku ju - kur ju prepend (7), ju shkoni dhe krijoni struct nyjës dhe keni vendosur që të tregojnë për të parë atë, sepse tani, pasi ne paraprire atë, ajo do të jetë në fillim të listës. Nëse ne prepend (3), që krijon një nyje, por tani vjen para 3 7. Pra, ne jemi në thelb të shtyrë gjërat në listën tonë. Tani, ju mund të shihni se prepend, nganjëherë njerëzit e quajnë atë shtytje, sepse ju jeni të shtyrë një element të ri në listën tuaj. Është gjithashtu e lehtë për të fshini në frontin e një liste. Në mënyrë që njerëzit shpesh do të thërrasë atë pop. Dhe në këtë mënyrë, ju mund të matem një pirg duke përdorur një listë e lidhur. Uh. Na vjen keq, tani ne jemi duke hyrë në Append. Pra, këtu kemi paraprire (7), tani ne prepend (3). Nëse ne paraprire diçka tjetër mbi këtë listë, nëse ne paraprire (4), atëherë ne do të kemi 4 dhe pastaj 3 dhe pastaj 7. Pra, atëherë ne mund të pop dhe për të hequr 4, hiqni 3, hiqni 7. Shpesh mënyra më intuitive për të menduar për këtë është me Append. Kështu që unë kam diagrammed se çfarë do të duken si me append këtu. Këtu, bashkangjitur (7) nuk duket ndryshe sepse nuk është vetëm një element në listë. Dhe bashkëngjitur (3) vë atë në fund. Ndoshta ju mund të shihni të drejtë tani mashtrim me Append është se pasi ne vetëm e di se ku fillimi i listës është, që t'i shtojë një listë ju duhet të ecin gjatë gjithë rrugës nëpër lista të marrë në fund, ndalet, pastaj të ndërtuar nyje tuaj dhe gjithçka bie poshtë. Wire të gjitha stuff up. Pra, me prepend, si ne ashtu grabitur nëpërmjet kjo me të vërtetë shpejt, kur ju prepend në një listë, kjo është mjaft e thjeshtë. 

Ju bëni nyje tuaj të re, të përfshijë disa alokimin dinamik kujtesës. Pra, këtu ne jemi duke bërë një struct nyje duke përdorur malloc. Pra malloc ne jemi duke përdorur për shkak se do të vënë mënjanë kujtesë për ne për më vonë sepse ne nuk duam që ky - ne duam që ky memorie të vazhdojnë për një kohë të gjatë. Dhe ne të merrni një tregues për hapësirë ​​në kujtesë se ne alokuar vetëm. Ne përdorim madhësinë e nyjeve, ne nuk përmbledhur fushat. Ne nuk gjenerojnë dorë numrin e bytes, në vend të kësaj ne i përdorim sizeof kështu që ne e dimë se ne jemi duke marrë numrin e duhur të bytes. Ne jemi të sigurt për të provuar se thirrja jonë malloc sukses. Kjo është diçka që ju doni të bëni në përgjithësi. Në makinat moderne, drejtimin jashtë kujtesës nuk është diçka që është e lehtë nëse ju jeni caktimin e një ton të gjëra dhe duke e bërë një listë të madhe, por në qoftë se ju jeni ndërtimin e gjëra për të, të themi, si një iPhone apo Android, ju nuk keni burime të kufizuara kujtesës, veçanërisht nëse ju jeni duke bërë diçka të fortë. Kështu që është e mirë për të marrë në praktikë. 

Vini re se unë kam përdorur një çift funksione të ndryshme këtu që e keni parë që janë lloj i ri. Pra fprintf është vetëm si printf përveç argumentit të tij të parë është lumë për të cilën ju doni të shtypura. Në këtë rast, ne duam të shtypura në vargun standarde gabim cili është i ndryshëm nga outstream standarde. By default ajo tregon deri në të njëjtin vend. Ajo gjithashtu kopje nga të terminalit, por ju mund të - përdorur ato komandat keni mësuar rreth, teknikat redirection keni mësuar në lidhje në video e Tommy për të vendosur Problem 4, ju mund të drejtojë atë në fusha të ndryshme, pastaj të dalë, të drejtë këtu, daljet e programit tuaj. Kjo është në thelb si të kthyer nga kryesore, përveç ne përdorim dalje sepse këtu kthimi nuk do të bëjë asgjë. Ne nuk jemi në kryesore, kështu që nuk do të kthehen të dalë nga programi si ne duam. Kështu që ne përdorim funksionin e daljes dhe t'i jepte një kod gabimi. Atëherë këtu ne kemi vendosur këtë fushë nyjen ri vlerë, fushën e tij i të jetë e barabartë për të i, dhe pastaj ne tela atë. Ne kemi vendosur treguesin tjetër nyjen ri për pikë për të parë, dhe pastaj i parë tani do të tregojnë për nyjen e re. Këto linja e parë të kodit, ne jemi në fakt ndërtimin e nyjen re. Jo e fundit dy linjat e këtij funksioni, por ato para. Ju në fakt mund të tërhiqet nga funksioni në një, në një funksion të ndihmës. Kjo është shpesh ajo që unë bëj është, unë të tërheqë atë në një funksion, Unë e quaj atë diçka si nyje të ndërtuar, dhe që mban funksionin prepend shumë e vogël, kjo është vetëm 3 rreshta atëherë. Unë bëj një telefonatë për të ndërtuar funksionin tim nyjeve, dhe atëherë unë gjithçka tela lart. 

Gjëja e fundit që unë dua të ju tregojë, dhe unë do të ju lejojnë të bëni append dhe të gjitha atë në tuaj, është si të iterate mbi një listë. Ka një bandë e mënyra të ndryshme për të iterate mbi një listë. Në këtë rast, ne do të gjeni gjatësinë e një liste. Pra, ne të fillojmë me gjatësi = 0. Kjo është shumë e ngjashme me shkrim strlen për një varg. Kjo është ajo që unë dua të ju tregojë, kjo për lak të drejtë këtu. Ajo duket kinda shokuar, kjo nuk është e zakonshme int i = 0, i <çfarëdo, i + +. Në vend të kësaj ajo Initializing n tonë ndryshueshme të jetë fillimi i listës. Dhe pastaj, ndërsa ndryshueshme tonë iterator nuk është null, ne do të mbajë. Kjo është për shkak se, sipas Konventës, fundi i listës sonë do të jetë i pavlefshëm. Dhe pastaj në rritje, në vend se duke bërë + +, ekuivalente lidhur listën e + + është n = n-> ardhshëm. 

Unë do të le ju plotësoni në boshllëqet këtu, sepse ne jemi jashtë kohës. Por mbani në mend këtë si ju punoni në psets tuaj spellr. Listat e lidhura, nëse ju jeni duke zbatuar një tabelë hash, patjetër do të vijë në shumë të volitshëm. Dhe duke pasur këtë idiomë për looping mbi gjërat do të bëjë jetën shumë më e lehtë, me shpresë. Çfarëdo pyetjeje, shpejt? [Sam] Do ju dërgojë jashtë SLL kompletuar dhe Sc? [Hardison] Yeah. Unë do të dërgoj nga slides përfunduar dhe rafte përfunduar SLL dhe queue.cs. [CS50.TV]