[Powered by Google Translate] [Adran 6: Llai cyfforddus] [Nate Hardison] [Harvard University] [Mae hyn yn CS50.] [CS50.TV] Mae pob hawl. Croeso i adran 6. Yr wythnos hon, rydym yn mynd i fod yn siarad am strwythurau data yn adran, yn bennaf oherwydd bod problem yr wythnos hon gosod ar spellr yn criw cyfan o archwilio strwythur gwahanol data. Mae criw o wahanol ffyrdd y gallwch chi fynd â'r broblem a osodwyd, a'r strwythurau data po fwyaf y gwyddoch amdanynt, y pethau yn fwy oer gallwch ei wneud. 

Felly, gadewch i ni ddechrau arni. Yn gyntaf rydym yn mynd i siarad am pentyrrau, y data pentwr a ciw strwythurau ein bod ni'n mynd i siarad am. Staciau a ciwiau yn ddefnyddiol iawn wrth inni ddechrau sôn am graffiau, nad ydym yn mynd i wneud cymaint o ar hyn o bryd. Ond maent yn wirioneddol dda i ddeall un o'r mawr strwythurau data sylfaenol CS. Mae'r disgrifiad yn y set problem fanyleb, os ydych yn tynnu i fyny, yn siarad am staciau yn debyg i y pentwr o hambyrddau bwyta sydd gennych yn y caffi yn y neuaddau bwyta lle pan fydd y staff fwyta yn dod ac yn rhoi'r hambyrddau bwyta allan ar ôl ydyn nhw wedi glanhau nhw, byddant yn gwneud synnwyr iddynt un ar ben y llall. Ac yna pan fydd plant yn dod i mewn i gael bwyd, maent yn tynnu i ffwrdd yr hambyrddau, yn gyntaf yr un uchaf, yna yr un isod, yna yr un is na hynny. Felly, mewn gwirionedd, yr hambwrdd cyntaf y mae'r staff fwyta roi i lawr yw'r un olaf sy'n cael ei gymryd i ffwrdd. Yr un diwethaf fod y staff fwyta ei roi ar yr un cyntaf sy'n cael ei gymryd i ffwrdd ar gyfer cinio. Yn spec y broblem a osodwyd yn, y gallwch ei lawrlwytho os nad ydych wedi eisoes, fyddwn yn sôn am fodelu pentwr Strwythur data gan ddefnyddio math hwn o strwythur. 

Felly beth sydd gennym yma, mae hyn yn debyg i'r hyn a gyflwynwyd mewn darlithoedd, ac eithrio mewn darlith gwnaethom gyflwyno hyn gyda ints yn hytrach na * torgoch s. Mae hyn yn mynd i fod yn stac bod siopau beth? Daniel? Beth rydym yn cadw yn y stac? [Daniel] Strings? >> Rydym yn storio llinynnau yn y stac, yn union. Y cyfan sydd angen i chi eu cael er mwyn creu pentwr yn arae o allu arbennig, sydd yn yr achos hwn, gallu yn mynd i fod yn yr holl gapiau oherwydd ei fod yn gyson. Ac yna yn ychwanegol at yr amrywiaeth, y cyfan sydd angen i olrhain yw maint presennol y rhesi. Un peth i'w nodi yma bod fath o oer yw ein bod yn creu strwythur data pentyrru ar ben y llall, strwythur data y rhesi. Mae nifer o ffyrdd gwahanol i weithredu pentyrrau. Ni fyddwn yn gwneud hyn yn eithaf eto, ond gobeithio ar ôl gwneud y problemau cysylltiedig-rhestr, byddwch yn gweld sut y gallwch yn hawdd weithredu pentwr ar ben rhestr cysylltiedig yn ogystal. Ond am nawr, byddwn yn cadw at y arrays. Felly eto, y cyfan rydym ei angen yw amrywiaeth, ac mae'n rhaid i ni olrhain y maint y rhesi. [Sam] Mae'n ddrwg gennym, pam yr ydych wedi'i ddweud y pentwr ar ben y tannau? I mi mae'n ymddangos fel y tannau o fewn y pentwr. [Hardison] Yeah. Rydym yn creu, rydym yn cymryd ein casgliad data strwythur - mae hwnnw'n gwestiwn mawr. Felly, y cwestiwn yw pam, ar gyfer y bobl sy'n cael eu gwylio hon ar-lein, pam yr ydym yn dweud bod y pentwr ar ben y llinynnau, oherwydd dyma ei fod yn edrych fel y llinynnau yn y tu mewn i'r pentwr? Pa yn gwbl wir. Yr hyn yr oeddwn yn cyfeirio ato oedd ein bod wedi cael amrywiaeth strwythur data. Mae gennym amrywiaeth o torgoch * s, mae hyn yn amrywiaeth o linynnau, ac rydym yn mynd i ychwanegu at hynny er mwyn creu strwythur data pentyrru. 

Felly pentwr ychydig yn fwy cymhleth nag arae. Gallwn ddefnyddio amrywiaeth i adeiladu pentwr. Felly, dyna lle'r ydym yn dweud bod y pentwr yn cael ei hadeiladu ar ben arae. Yn yr un modd, fel y dywedais yn gynharach, gallwn adeiladu pentwr ar ben rhestr cysylltiedig. Yn hytrach na defnyddio amrywiaeth i gynnal ein elfennau, gallem ddefnyddio rhestr cysylltiedig i gynnal ein elfennau ac adeiladu ar y pentwr o gwmpas hynny. Gadewch i ni gerdded drwy un neu ddau o enghreifftiau, yn edrych ar rai cod, i weld beth sy'n digwydd mewn gwirionedd yma. Ar y chwith, rydw i wedi taflu i lawr yr hyn y byddai strwythur stac edrych fel yn y cof os allu cael eu diffinio # i fod yn bedwar. Rydym wedi cael ein pedair elfen amrywiaeth * torgoch. Rydym wedi cael llinynnau [0], llinynnau [1], llinynnau [2], llinynnau [3], ac yna y lle olaf ar gyfer ein gyfanrif maint. A yw hyn yn gwneud synnwyr? Iawn. Dyma beth sy'n digwydd os bydd yr hyn yr wyf yn ei wneud ar y dde, a fydd yn fy cod, ydy at jyst ddatgan strwythur, a strwythur eu pentyrru enw s. Dyma'r hyn yr ydym yn ei gael. Mae'n gosod yr ôl-troed yn y cof. Y cwestiwn cyntaf yma yw beth yw cynnwys y strwythur pentwr? Ar hyn o bryd maent yn dim byd, ond nid ydynt yn gwbl ddim. Maent yn y math hwn o garbage. Nid oes gennym unrhyw syniad beth sydd ynddynt. Pan fyddwn yn datgan s simnai, rydym yn taflu bod i lawr ar ben y cof. Mae'n fath o fel datgan int i ac nid ei ymgychwyn. Nid ydych yn gwybod beth sydd yno. Gallwch ddarllen beth sydd yno, ond ni allai fod yn ddefnyddiol super. Un peth y byddwch eisiau bob amser yn cofio ei wneud yw ymgychwyn hyn sydd angen ei ymgychwyn. Yn yr achos hwn, rydyn ni'n mynd i ymgychwyn y maint i fod yn sero, oherwydd mae hynny'n mynd i droi allan i fod yn bwysig iawn i ni. Gallem fynd yn ei flaen ac yn ymgychwyn holl arwyddion, yr holl s * torgoch, bod rhywfaint o werth ddealladwy, yn ôl pob tebyg null. Ond nid yw'n hollol angenrheidiol ein bod yn gwneud hynny. 

Yn awr, y ddau brif weithrediadau ar pentyrrau yn? Unrhyw un yn cofio o ddarlith yr hyn yr ydych yn ei wneud gyda chyrn? Ydw? [Stella] Gwthio a popping? >> Yn union. Gwthio a popping yw'r ddwy brif weithrediadau ar pentyrrau. A beth mae gwthio yn ei wneud? >> Mae'n rhoi rhywbeth ar y top y pentwr, ac yna popping yn mynd ag ef i ffwrdd. [Hardison] Yn union. Felly, gwthio gwthio rhywbeth ar ben y pentwr. Mae fel y staff fwyta rhoi hambwrdd bwyta i lawr ar y cownter. Ac popping yn cymryd hambwrdd fwyta oddi ar y pentwr. Gadewch i ni gerdded drwy ychydig o enghreifftiau o'r hyn sy'n digwydd pan fyddwn yn gwthio pethau i mewn i'r pentwr. Pe baem yn gwthio'r llinyn 'helo' ar ein simnai, mae hyn yn beth fyddai ein diagram yn edrych fel yn awr. Gweld beth sy'n digwydd? Rydym yn gwthio i mewn i'r elfen gyntaf ein llinynnau amrywiaeth ac rydym yn upped ein Cyfrif maint i fod yn 1. Felly, os ydym yn edrych ar y gwahaniaeth rhwng y ddau sleidiau, dyma oedd 0, dyma cyn y gwthio. Dyma ôl y gwthio. Cyn y gwthio, ar ôl y gwthio. Ac yn awr mae gennym un elfen yn ein pentwr. Mae'n y llinyn "helo", a dyna ni. Mae popeth arall yn y casgliad, yn ein llinynnau amrywiaeth, yn dal i garbage. Nid ydym wedi ymgychwyn hynny. Lets 'ddeud rydym yn gwthio llinyn arall ar ein pentwr. Rydym yn mynd i wthio "byd" ar hyn o bryd. Felly gallwch weld "byd" yma yn mynd ar ben o "helo", ac yn y cyfrif faint yn mynd i fyny i 2. Nawr gallwn wthio "CS50", a fe sy'n mynd ar ben eto. Os awn yn ôl, gallwch weld sut yr ydym yn gwthio pethau ar ben y pentwr. Ac yn awr rydym yn dod i pop. Pan fyddwn yn popped rhywbeth oddi ar y pentwr, beth ddigwyddodd? Unrhyw un weld y gwahaniaeth? Mae'n eithaf cynnil. [Myfyrwyr] Mae maint. >> Yeah, maint newid. 

Beth arall fyddech wedi disgwyl i newid? [Myfyrwyr] Mae'r llinynnau, hefyd. >> Iawn. Mae'r llinynnau hefyd. Mae'n troi allan bod pan fyddwch chi'n ei wneud yn y modd hwn, oherwydd nad ydym yn copïo elfennau yn ein stac, nid ydym mewn gwirionedd yn rhaid i chi wneud unrhyw beth; unig a fedrwn ddefnyddio maint i gadw golwg ar y nifer o bethau yn ein amrywiaeth felly pan fyddwn yn galw eto, eto rydym yn unig lleihau a ein maint i lawr i 1. Does dim angen i chi mewn gwirionedd yn mynd i mewn ac trosysgrifo unrhyw beth. Kind of ffynci. Mae'n troi allan bod yn nodweddiadol yn gadael pethau yn unig oherwydd ei fod yn llai o waith i ni ei wneud. Os nad oes raid i ni fynd yn ôl a trosysgrifo rhywbeth, yna pam ei wneud? Felly, pan fyddwn yn galw ddwywaith i ffwrdd o'r pentwr, y cyfan a wna hynny yw lleihau a maint cwpl o weithiau. Ac eto, dim ond oherwydd nad ydym yn copïo pethau yn ein pentwr. Ydw? Mynd yn ei flaen. [Myfyrwyr, annealladwy] >> Ac yna beth sy'n digwydd pan fyddwch yn gwthio rhywbeth eto? Pan fyddwch yn gwthio rhywbeth eto, ble mae'n mynd? I ble mae'n mynd, Basil? >> Into llinynnau [1]? >> Iawn. Pam nad yw'n mynd i mewn llinynnau [3]? [Basil] Oherwydd ei fod yn anghofio bod yna unrhyw beth yn llinynnau [1] a [2]? [Hardison] Yn union. Mae ein corn, yn y bôn, "anghofio" ei fod yn dal ar i unrhyw beth mewn llinynnau [1] neu linynnau [2], felly pan fyddwn yn gwthio "Woot", 'i jyst yn rhoi bod i elfen ar llinynnau [1]. A oes unrhyw gwestiynau ynglŷn â sut mae hyn yn gweithio, ar lefel sylfaenol? [Sam] Felly nid yw hyn yn ddeinamig mewn unrhyw ffordd, o ran y swm neu o ran maint y pentwr? [Hardison] Yn union. Mae hyn yn - y pwynt oedd nad oedd hyn yn pentwr ddynamig growning. Mae hwn yn stac gallu dal, ar y mwyaf, bedwar * torgoch s, ar y mwyaf pedwar peth. Pe baem yn ceisio gwthio beth pumed, beth ydych chi'n feddwl ddylai ddigwydd? [Myfyrwyr, annealladwy] [Hardison] Yn union. Mae yna nifer o bethau a allai ddigwydd. Gallai o bosibl SEG fai, yn dibynnu ar yr hyn a oedd - sut yn union yr oeddem yn gweithredu y cefn-diwedd. Gallai trosysgrifo. Gallai gael y gorlif byffer ein bod yn siarad am yn y dosbarth. Beth fyddai'r peth mwyaf amlwg a allai fod yn overwritten os ydym yn ceisio gwthio rhywbeth ychwanegol ar ein corn? Felly, soniasoch am gorlif byffer. Beth allai fod y peth a fyddai'n cael eu hysgrifennu dros neu stomped ar os ydym yn gorlifo ddamweiniol gan geisio gwthio rhywbeth ychwanegol? [Daniel, annealladwy] >> bosibl. Ond i ddechrau, beth allai ddigwydd? Beth os ydym yn ceisio gwthio beth 4? Gallai ysgrifennu dros y maint, o leiaf gyda'r diagram cof ein bod wedi cael. 

Yn y set problem fanyleb, sef yr hyn rydym yn mynd i fod yn gweithredu heddiw, hyn yr ydym am ei wneud yn unig yn dychwelyd ffug. Mae ein dull gwthio yn mynd i ddychwelyd gwerth boolean, a bydd y gwerth boolaidd yn wir os yw'r gwthio yn llwyddo a ffug os na allwn wthio unrhyw beth mwy oherwydd bod y pentwr yn llawn. Gadewch i ni gerdded drwy ychydig o'r cod ar hyn o bryd. Dyma ein swyddogaeth gwthio. Ein swyddogaeth wthio ar gyfer pentwr yn mynd i'w cymryd yn y llinyn i roi ar y corn. Mae'n mynd i ddychwelyd wir os yw'r llinyn ei wthio yn llwyddiannus ar y corn fel arall a ffug. Gall unrhyw awgrymiadau ar beth yn beth cyntaf da i'w wneud yma? [Sam] Os faint yn hafal i allu dychwelyd ffug? [Hardison] Bingo. Swydd Nice. Os yw'r maint yn gallu, rydym yn mynd i ddychwelyd ffug. Ni allwn roi unrhyw beth mwy yn ein pentwr. Fel arall, rydym yn awyddus i roi rhywbeth ar ben y pentwr. Beth yw "frig y pentwr," i ddechrau? [Daniel] Maint 0? >> Maint 0. Beth yw frig y pentwr ar ôl mae un peth yn y pentwr? Missy, ydych chi'n gwybod? [Missy] Un. Maint >> yn un, yn union. Byddwch yn parhau i ychwanegu at y maint, a phob tro y byddwch chi'n rhoi yn yr elfen newydd yn y maint mynegai yn y rhesi. Gallwn wneud hyn gyda'r math hynny o un-leinin, os yw hynny'n gwneud synnwyr. Felly, rydym wedi cael ein llinynnau amrywiaeth, rydym yn mynd i gael mynediad iddo ar y mynegai maint, ac rydym yn jyst yn mynd i gadw ein * torgoch i mewn 'na. Hysbysiad sut y mae 'dim copïo llinyn yn mynd ymlaen yn fan hyn, unrhyw ddyraniad deinamig o gof? Ac yna Missy fagu hyn yr ydym yn awr i wneud, oherwydd ein bod wedi cael eu storio y llinyn yn y lle priodol yn yr amrywiaeth, a dywedodd bod yn rhaid i gynnydd y maint gan un fel ein bod ni'n barod ar gyfer y gwthiad nesaf. Felly, gallwn wneud hynny gyda s.size + +. Ar y pwynt hwn, rydym wedi gwthio i mewn i'n casgliad. Beth yw'r peth olaf mae'n rhaid i ni ei wneud? [Myfyrwyr] Dychwelyd wir. >> Dychwelyd wir. Felly, mae'n eithaf syml, cod 'n bert syml. Ddim yn rhy fawr. Unwaith y byddwch wedi lapio eich pen o gwmpas sut y pentwr yn gweithio, mae hyn yn eithaf syml i'w gweithredu. 

Yn awr, y rhan nesaf o hyn yw popping llinyn oddi ar y pentwr. Rydw i'n mynd i roi i chi guys rhywfaint o amser i weithio ar y darn ychydig. Mae bron yn y bôn y gwrthwyneb o'r hyn yr ydym wedi ei wneud yma yn gwthio. Hyn yr wyf wedi ei wneud mewn gwirionedd - wps. Rydw i wedi booted i fyny teclyn dros yma, ac yn y peiriant, Rwyf wedi tynnu i fyny y broblem a osodwyd 5 Manyleb. Os byddwn yn chwyddo i mewn yma, gallwn weld fy mod yn cdn.cs50.net/2012/fall/psets/pset5.pdf. Ydych chi wedi guys llwytho i lawr y cod hwn sydd wedi lleoli yma, section6.zip? Mae pob hawl. Os nad ydych wedi gwneud hynny, wneud hynny ar hyn o bryd, yn gyflym iawn. 'N annhymerus' yn ei wneud yn fy ffenestr terfynell. Fi 'n weithredol yn gwneud i fyny yma. Yeah. Ie, Sam? >> Mae gen i gwestiwn ynghylch pam wnaethoch chi ei ddweud cromfachau s.string 's o faint = str? Beth yw str? A yw hyn a ddiffinnir yn rhywle o'r blaen, neu - oh, yn y str * torgoch? [Hardison] Ie, yn union. Dyna oedd y ddadl. >> O, iawn. Mae'n ddrwg gennym. [Hardison] Rydym yn nodi y llinyn i wthio i mewn Y cwestiwn arall a allai ddod i fyny nad ydym yn wir yn siarad am y fan hon oedd rydym yn cymryd yn ganiataol ein bod wedi newidyn hwn a elwir yn a oedd o ran cwmpas ac yn hygyrch i ni. Rydym yn cymryd yn ganiataol fod ef oedd y strwythur stac. Felly, edrych yn ôl ar y cod gwthio, gallwch weld ein bod ni'n gwneud pethau gyda'r llinyn a gafodd eu pasio yn ond yna yn sydyn, rydym yn cyrchu s.size, fel, lle oedd yn dod? Yn y cod ein bod ni'n mynd i edrych arno yn yr archif adran ac yna y pethau y byddwch chi'n ei wneud yn eich problem yn gosod, rydym wedi gwneud ein pentwr strwythur newidyn byd-eang fel y gallwn gael mynediad iddo yn ein holl swyddogaethau gwahanol heb orfod manually basio o gwmpas a phasio drwy gyfeirio, yn gwneud popeth y math o bethau iddo. Rydym yn unig yn twyllo ychydig bach, os ydych, er mwyn gwneud pethau brafiach. Ac mae hynny'n rhywbeth rydym yn ei wneud yma am ei fod am hwyl, mae'n haws. Yn aml, byddwch yn gweld pobl yn gwneud hyn os oes ganddynt un strwythur data mawr sy'n cael ei gweithredu ar o fewn eu rhaglen. 

Gadewch i ni fynd yn ôl dros i'r ddyfais. A oedd pawb yn llwyddiannus yn cael y section6.zip? Mae pawb yn unzip 'gan ddefnyddio section6.zip unzip? Os byddwch yn mynd i adran 6 cyfeiriadur - AAH, i gyd dros y lle - ac eich bod yn rhestru beth sydd yn fan hyn, byddwch yn gweld eich bod wedi Mae tair gwahanol. ffeiliau c. Rydych chi wedi cael ciw, yn SLL, sy'n unigol sy'n gysylltiedig â rhestr, ac pentwr. Os byddwch yn agor i fyny stack.c, gallwch weld bod gennym y strwythur diffiniedig i ni, y strwythur union yr ydym newydd sôn amdanynt yn y sleidiau. Rydym wedi cael ein newidyn byd-eang am y pentwr, rydym wedi cael ein swyddogaeth gwthio, ac yna rydym wedi cael ein swyddogaeth pop. 'N annhymerus' rhoi'r cod ar gyfer gwthio yn ôl i fyny ar y sleid yma, ond beth hoffwn i chi guys i chi ei wneud yw, hyd eithaf eich gallu, fynd ac yn gweithredu'r swyddogaeth pop. Unwaith y byddwch wedi ei rhoi ar waith, gallwch lunio gwneud hyn gyda simnai, ac yna rhedeg y gweithredadwy pentwr o ganlyniad, a fydd yn rhedeg yr holl cod hwn prawf i lawr yma dyna yn y prif. A phrif cymryd gofal mewn gwirionedd gwneud y gwthiad galwadau pop a a gwneud yn siŵr bod popeth yn mynd drwy bob hawl. Mae hefyd yn initializes maint pentwr dde yma felly nid oes rhaid i chi boeni am ymgychwyn hynny. Gallwch gymryd yn ganiataol ei fod yn briodol wedi'i ymgychwyn erbyn yr amser yr ydych yn cael mynediad iddo yn y swyddogaeth pop. Ydy hynny'n gwneud synnwyr? Felly, yma rydym yn mynd. Mae y cod gwthio. Byddaf yn rhoi i chi guys 5 neu 10 munud. Ac os oes gennych unrhyw gwestiynau yn y cyfamser tra eich bod yn codio, gofynnwch iddyn nhw yn uchel. Felly, os ydych yn cyrraedd pwynt glynu, dim ond gofyn. Gadewch i mi wybod, gadewch i bawb arall wybod. Gweithiwch gyda'ch cymydog hefyd. [Daniel] Rydym yn unig yn gweithredu pop ar hyn o bryd? >> Just pop. Er y gallwch gopïo gweithredu wthio os hoffech fel y bydd y profion yn gweithio. Oherwydd ei fod yn anodd i brofi pethau mynd i mewn i - neu, mae'n anodd i brofi pethau popping allan o bentwr os nad oes unrhyw beth yn y pentwr i ddechrau. 

Beth yw pop i fod i gael eu dychwelyd? Mae'r elfen o frig y pentwr. Mae i fod i gael yr elfen oddi ar ben y pentwr ac yna lleihau a maint y pentwr, ac yn awr ydych wedi colli'r elfen ar y top. Ac yna i chi ddychwelyd yr elfen ar y top. [Myfyrwyr, annealladwy] [Hardison] Felly beth sy'n digwydd os ydych yn gwneud hynny? [Myfyrwyr, annealladwy] Beth sy'n dod i ben i fyny digwydd yw eich bod yn ôl pob tebyg gael mynediad naill ai ddim yn elfen sydd wedi ei ymgychwyn eto, fel bod eich cyfrifiad o ble mae'r elfen olaf yn i ffwrdd. Felly yma, os ydych yn sylwi, yn gwthio, rydym yn cyrchu llinynnau ar yr elfen s.size oherwydd ei fod yn fynegai newydd. Mae'n brig newydd y pentwr. Tra yn pop, s.size yn mynd i fod y lle nesaf, y gofod sydd ar ben yr holl elfennau yn eich pentwr. Felly nid yw'r elfen uchaf-y rhan fwyaf ar s.size, ond yn hytrach, mae'n oddi tano. 

Y peth arall i'w wneud pan fyddwch yn - mewn pop, ei oes rhaid i chi lleihau a maint. Os ydych yn cofio yn ôl at ein diagram bach iawn yma, mewn gwirionedd, yr unig beth a welsom yn digwydd pan fyddwn yn galw pop oedd bod gostwng maint hwn, yn gyntaf i 2, ac yna i 1. Yna, pan fyddwn yn gwthio elfen newydd ar, bydd yn mynd ymlaen yn y fan a'r lle cywir. [Basil] Os yw'r s.size yw 2, ni fyddai yna mae'n mynd i'r elfen 2, ac yna byddech eisiau i pop yr elfen honno i ffwrdd? Felly, os ydym yn mynd i - >> Felly, gadewch i ni edrych ar hyn eto. Os yw hyn yn ein stac ar y pwynt hwn ac rydym yn galw pop, lle y mynegai yw'r elfen uchaf-y rhan fwyaf o? [Basil] Ar 2, ond mae'n mynd i pop 3. >> Iawn. Felly dyna lle mae ein maint yn 3, ond rydym am i pop yr elfen ar mynegai 2. Mae'n y math hwnnw nodweddiadol oddi ar gan un sydd gennych yn yr sero-mynegeio araeau. Felly, ydych chi eisiau i pop y drydedd elfen, ond nid yw'r drydedd elfen ar fynegai 3. A'r rheswm nad oes raid i ni wneud bod 1 minws pan fyddwn ni'n gwthio yw oherwydd ar hyn o bryd, byddwch yn sylwi bod yr elfen uchaf-y rhan fwyaf, pe baem yn gwthio rhywbeth arall ar y pentwr ar y pwynt hwn, byddem yn awyddus i wthio yn fynegai 3. Ac dim ond fel y digwydd bod y maint a'r mynegeion llinell i fyny pan fyddwch yn gwthio. 

Pwy sy'n cael gweithredu pentwr yn gweithio? Rydych chi wedi cael pentwr weithio un. A oes gennych pop yn gweithio eto? [Daniel] Ydw. Rwy'n credu hynny. >> Rhaglen yn rhedeg ac nid SEG ffawtio, mae'n argraffu? A yw'n argraffu "llwyddiant" pan fyddwch yn ei redeg? Yeah. Gwnewch stac, rhedeg, os bydd yn argraffu allan "llwyddiant" ac nid yw'n mynd ffyniant, yna i gyd yn dda. Mae pob hawl. Gadewch i ni fynd drosodd i'r offer yn gyflym iawn, a byddwn yn cerdded drwy hyn. Os ydym yn edrych ar yr hyn sy'n digwydd yma gyda pop, Daniel, beth oedd y peth cyntaf a wnaethoch? [Daniel] Os s.size yn fwy na 0. [Hardison] Iawn. A pham wnaethoch chi hynny? [Daniel] I wneud yn siwr bod rhywbeth y tu mewn i'r pentwr. [Hardison] Hawl. Byddwch am brofi i wneud yn siŵr bod s.size yn fwy na 0; fel arall, beth ydych chi eisiau bod wedi digwydd? [Daniel] null Dychwelyd? Null Dychwelyd >>, yn union. Felly, os s.size yn fwy na 0. Yna, beth ydyn ni'n mynd i'w wneud? Beth ydym ni'n ei wneud os nad yw'r pentwr yn wag? [Stella] Rydych lleihau a faint? >> Byddwch yn lleihau a maint, iawn. Felly, sut wnaethoch chi hynny? >> S.size--. [Hardison] Fawr. Ac yna beth wnaethoch chi? [Stella] Ac yna y dywedais s.string dychwelyd [s.size]. [Hardison] Fawr. Fel arall, byddwch yn dychwelyd null. Ie, Sam? [Sam] Pam nad yw angen iddo fod yn s.size + 1? [Hardison] Plus 1? >> Yeah. >> Got iddo. [Sam] Roeddwn i'n meddwl oherwydd eich bod yn cymryd 1 allan, yna rydych chi'n mynd i fod yn dychwelyd nad yw'r un y maent yn gofyn amdano. [Hardison] Ac mae hyn yn unig oedd hyn yr ydym yn sôn amdano gyda'r holl fater o 0 mynegai. Felly, os ydym yn chwyddo yn ôl dros yma. Os ydym yn edrych ar y boi iawn yma, gallwch weld bod pan fyddwn yn galw, rydym yn popping yr elfen yn mynegai 2. 

Felly, rydym yn lleihau ein maint yn gyntaf, yna mae ein maint yn cyfateb ein mynegai. Os nad ydym yn lleihau a maint yn gyntaf, yna mae'n rhaid i ni wneud maint -1 a wedyn lleihau a. Great. I gyd yn dda? Unrhyw gwestiynau am hyn? Mae yna nifer o ffyrdd gwahanol i ysgrifennu hyn yn ogystal. Yn wir, gallwn wneud rhywbeth hyd yn oed - gallwn wneud un-leinin. Gallwn wneud elw un llinell. Felly gallwn mewn gwirionedd yn lleihau a cyn i ni ddychwelyd drwy wneud hynny. Felly roi'r - cyn y s.size. Mae hynny'n gwneud y llinell mewn gwirionedd trwchus. Pan fydd y gwahaniaeth rhwng y -. Maint s a s.size-- yw bod hyn Postfix - maent yn ei alw Postfix oherwydd bod y - yn dod ar ôl y s.size-- yn golygu bod s.size yn cael ei werthuso at ddibenion ddod o hyd i'r mynegai fel y mae ar hyn o bryd pan fydd y llinell hon yn cael ei weithredu, ac yna mae hyn - sy'n digwydd ar ôl y llinell yn cael ei ddienyddio. Ar ôl yr elfen yn mynegai s.size ceir mynediad. Ac nid dyna'r hyn yr ydym ei eisiau, gan ein bod am i'r lleihau a ddigwydd gyntaf. Othewise, rydyn ni'n mynd i cael gafael ar y array, yn effeithiol, y tu allan i ffiniau. Rydym yn mynd i cael gafael ar y elfen uwchben yr un yr ydym mewn gwirionedd am gael mynediad. Yeah, Sam? >> Ydy hi'n gyflymach na defnyddio RAM llai i'w wneud yn un llinell neu beidio? [Hardison] Onest, mae'n wir yn dibynnu arnynt. [Sam, annealladwy] >> Yeah, mae'n dibynnu. Gallwch wneud triciau compiler i gael y compiler i gydnabod hynny, fel arfer, yr wyf yn dychmygu. 

Felly rydym wedi crybwyll ychydig am y optimization compiler pethau y gallwch ei wneud wrth lunio, a dyna'r math o beth y gallai casglwr yn gallu chyfrif i maes, fel oh, hey, efallai y gallaf wneud hyn i gyd mewn un gweithred, yn hytrach na llwytho y newidyn maint mewn o RAM, decrementing ei, ei storio yn ôl allan, ac yna llwytho yn ôl i mewn eto i brosesu gweddill y llawdriniaeth hon. Ond yn nodweddiadol, na, nid dyma'r math o beth mae hynny'n mynd i wneud eich rhaglen sylweddol gyflymach. Unrhyw gwestiynau mwy o wybodaeth am pentyrrau? 

Felly, gwthio a neidio. Os ydych chi guys am roi cynnig ar y rhifyn haciwr, hyn yr ydym wedi ei wneud yn y rhifyn haciwr yn cael mynd mewn gwirionedd a gwneud y pentwr tyfu yn ddeinamig. Mae'r her yno yn bennaf i fyny yma yn y swyddogaeth gwthio, at chyfrif i maes sut i wneud y casgliad yn tyfu â'ch bod yn cadw gwthio elfennau mwy a mwy ar y pentwr. Nid yw'n mewn gwirionedd yn rhy fawr cod ychwanegol. Dim ond galwad i - mae'n rhaid i chi gofio i gael y galwadau i'r malloc yno yn iawn, ac yna chyfrif i maes pan fyddwch chi'n mynd i alw realloc. Mae hynny'n her hwyl os oes gennych ddiddordeb. 

Ond am y tro, gadewch i ni symud ymlaen, a gadewch i ni siarad am ciwiau. Sgroliwch drwy yma. Mae'r ciw yn frawd neu chwaer agos y pentwr. Felly, yn y simnai, pethau a oedd yn rhoi diwethaf oedd y pethau cyntaf i wedyn yn cael eu hadalw. Rydym wedi cael yr olaf i mewn, cyntaf allan, neu LIFO, archebu. Tra yn y ciw, fel y byddech yn ei ddisgwyl o'r adeg pan fyddwch yn sefyll mewn llinell, y person cyntaf i fynd i mewn llinell, y peth cyntaf i fynd i mewn i'r ciw, yw'r peth cyntaf sy'n cael ei adfer gan y ciw. Ciwiau yn cael eu defnyddio'n aml hefyd pan fyddwn yn delio gyda graffiau, fel yr ydym yn siarad am yn gryno gyda staciau, a chiwiau hefyd yn ddefnyddiol ar gyfer criw o bethau eraill. Un peth sy'n dod i fyny yn aml yn ceisio cynnal, er enghraifft, rhestr datrys o elfennau. A allwch chi wneud hyn gydag amrywiaeth. Gallwch cadw rhestr datrys o bethau mewn amrywiaeth, ond lle sy'n cael anodd wedyn byddwch bob amser yn rhaid i chi ddod o hyd i y lle priodol i fewnosod y peth nesaf. Felly, os oes gennych amrywiaeth o rifau, 1 hyd at 10, ac yna rydych am ehangu hynny i bob un o'r rhifau 1 trwy 100, ac eich bod yn cael y rhifau hyn mewn trefn ar hap ac yn ceisio cadw popeth didoli wrth i chi fynd drwy, byddwch yn gorfod gwneud llawer o symud. Gyda rhai mathau o giwiau a rhai mathau o strwythurau data gwaelodol, gallwch chi mewn gwirionedd yn ei gadw'n weddol syml. Nid oes rhaid i chi ychwanegu rhywbeth ac yna ad-drefnu'r holl beth bob tro. Nid oes yn rhaid i chi wneud llawer o symud o'r elfennau mewnol o gwmpas. Pan fyddwn yn edrych ar ciw, byddwch yn gweld bod - hefyd yn queue.c yn y cod adran - y strwythur yr ydym wedi ei rhoi yn wir yn debyg i'r strwythur yr ydym yn rhoi i chi am pentwr. 

Mae un eithriad i hyn, a bod un eithriad yw ein bod yn cael y cyfanrif ychwanegol a elwir yn y pen, a'r pennaeth yma am gadw golwg ar y pennaeth y ciw, neu yr elfen gyntaf yn y ciw. Gyda stac, roeddem yn gallu cadw golwg ar yr elfen ein bod am i adfer, neu ben y pentwr, gan ddefnyddio dim ond y maint, tra gyda ciw, rydym yn gorfod delio â dod i ben gyferbyn. Rydym yn ceisio tac pethau ar ar y diwedd, ond yna'n dychwelyd pethau o'r tu blaen. Felly, yn effeithiol, gyda'r pennaeth, mae gennym y mynegai o ddechrau'r y ciw, a maint yn rhoi i ni y mynegai o ddiwedd y ciw fel y gallwn adfer pethau gan y pennaeth ac yn ychwanegu pethau ar y gynffon. Er bod y simnai, roeddem ond yn delio â ben y pentwr. Rydym byth yn gorfod cael gafael ar waelod y pentwr. Byddwn ond yn ychwanegu pethau at y brig ac yn cymryd pethau oddi ar y top felly nid oedd angen y maes ychwanegol y tu mewn i'n strwythur. Ydy hynny yn gyffredinol yn gwneud synnwyr? Mae pob hawl. Ie, Charlotte? [Charlotte, annealladwy] [Hardison] Dyna gwestiwn mawr, a dyna oedd un a ddaeth i fyny mewn darlith. Efallai bydd cerdded drwy ychydig o enghreifftiau yn dangos pam nid ydym am i ddefnyddio llinynnau [0] fel pennaeth y ciw. 

Felly dychmygwch ein bod wedi ein ciw, rydym yn mynd i alw ciw. Ar y dechrau, pan fyddwn wedi instantiated newydd ei, pan fyddwn wedi datgan yn unig, nid ydym wedi ymgychwyn unrhyw beth. Mae hyn i gyd garbage. Felly, wrth gwrs rydym am wneud yn siŵr ein bod yn ymgychwyn y maint a'r caeau pen i fod yn 0, rhywbeth rhesymol. Gallem hefyd yn mynd yn ei flaen ac yn null allan yr elfennau yn ein ciw. Ac i wneud hwn yn addas diagram, yn sylwi bod yn awr gall ein ciw ond yn dal tair elfen; tra gallai ein pentwr cynnal pedwar, gall ein ciw ond yn dal tri. A dim ond i wneud y ffit diagram. Y peth cyntaf sy'n digwydd yma yw ein enqueue y llinyn "hi". Ac yn union fel y buom gyda'r simnai, dim byd mawr yn wahanol yma, rydym yn taflu y llinyn ar o linynnau [0] a cynyddiad ein maint erbyn 1. Rydym yn enqueue "bye", mae'n cael ei roi ar. Felly, mae hyn yn edrych fel pentwr ar gyfer y rhan fwyaf. Rydym yn dechrau yma, elfen newydd, elfen newydd, maint yn cadw mynd i fyny. Beth sy'n digwydd ar yr adeg hon pan fyddwn eisiau dequeue rhywbeth? Pan ydym am dequeue, sef yr elfen yr ydym am ei dequeue? [Basil] Strings [0]. >> Zero. Yn union i'r dde, Basil. Rydym yn awyddus i gael gwared ar y llinyn cyntaf, mae hyn yn un, "hi". Felly beth oedd y peth arall sy'n newid? Hysbysiad pan fyddwn yn popped rhywbeth oddi ar y pentwr, rydym yn unig newid y maint, ond yma, rydym wedi cael un neu ddau o bethau sy'n newid. Nid yn unig y mae'r newid maint ond mae'r newidiadau pen. Mae hyn yn mynd yn ôl at Charlotte pwynt yn gynharach: pam y mae gennym y pennaeth yn ogystal? A yw'n gwneud synnwyr yn awr, Charlotte? Kind >> o. [Hardison] Math o? Felly beth ddigwyddodd pan fyddwn yn dequeued? Beth oedd y pennaeth yn gwneud hynny bellach yn ddiddorol? [Charlotte] O, oherwydd ei fod yn newid - iawn. Rwy'n gweld. Oherwydd bod y pen - lle mae'r pennaeth yn pwyntio at newidiadau o ran y lleoliad. Mae'n bellach yn wastad yr un mynegai sero. >> Yeah, yn union. Beth ddigwyddodd oedd, os dequeueing elfen uchel ei wneud ac nid oedd gennym y maes hwn pen oherwydd ein bod bob amser yn galw llinyn yma ar 0 mynegai y pennaeth ein ciw, yna byddai'n rhaid i ni symud gweddill y ciw i lawr. Byddai'n rhaid i ni symud "bye" o o dannau [1] i llinynnau [0]. A llinynnau [2] i lawr i llinynnau [1]. A byddai'n rhaid i ni wneud hyn ar gyfer y rhestr gyfan o elfennau, yr amrywiaeth cyfan o elfennau. A phan fyddwn ni'n gwneud hyn gydag amrywiaeth, sy'n mynd yn wirioneddol gostus. Felly yma, nid yw'n llawer fawr. Rydym yn unig wedi tair elfen yn ein casgliad. Ond pe bai gennym ciw o fil o elfennau neu miliwn o elfennau, ac yna yn sydyn, rydym yn dechrau gwneud criw o dequeue galw i gyd mewn dolen, pethau yn wir yn mynd i arafu i lawr gan ei fod yn symud popeth i lawr yn gyson. Rydych yn gwybod, symud o 1, newid erbyn 1, newid erbyn 1, newid erbyn 1. Yn hytrach, rydym yn defnyddio y pen hwn, rydym yn galw ei fod yn "pwyntydd" hyd yn oed er nad yw'n wir yn pwyntydd yn yr ystyr caeth; nid yw'n fath pwyntydd. Nid yw'n 'an * int neu * torgoch neu unrhyw beth fel' na. Ond mae'n pwyntio neu nodi y pennaeth ein ciw. Yeah? 

[Myfyrwyr] Sut mae dequeue gwybod i ychydig pop oddi ar beth bynnag sydd ar ben? [Hardison] Sut mae dequeue yn gwybod sut i pop oddi ar beth bynnag sydd wrth y pen? Hawl >>, yeah. >> Beth mae'n edrych arno yw dim ond beth bynnag y maes pennaeth yn cael ei osod i. Felly, yn yr achos cyntaf hwn, os edrychwn i'r dde yma, ein pen yw 0, 0 mynegai. >> Iawn. [Hardison] Felly, 'i jyst yn dweud iawn, yn dda, yr elfen yn mynegai 0, y llinyn "hi", yw'r elfen ar ben ein ciw. Felly, rydym yn mynd i dequeue y boi. A fydd yr elfen sy'n cael ei ddychwelyd i'r galwr. Ie, Saad? >> Felly, y pen yn y bôn yn gosod y - lle rydych chi'n mynd i mynegai iddo? Dyna ddechrau ohono? >> Yeah. >> Iawn. [Hardison] Mae hynny'n dod yn y dechrau newydd ar gyfer ein casgliad. Felly, pan fyddwch yn dequeue rhywbeth, y cyfan mae'n rhaid i chi ei wneud yw cael mynediad i'r elfen ar mynegai q.head, a bydd hynny'n elfen yr ydych am ei dequeue. Rhaid i chi hefyd lleihau a maint. Byddwn yn gweld mewn ychydig lle mae pethau yn cael ychydig yn anodd gyda hyn. Rydym yn dequeue, ac yn awr, os ydym enqueue eto, lle rydym yn enqueue? Ble mae'r elfen nesaf yn mynd yn ein ciw? Dywedwch ydym am enqueue y llinyn "CS". Bydd i ba mynegai y mae'n mynd? [Mae myfyrwyr yn] Strings [2]. >> Dau. Pam 2 ac nid 0? [Basil] Oherwydd yn awr y pennaeth yw 1, felly dyna fel y dechrau y rhestr? [Hardison] Hawl. A beth yn dynodi diwedd y rhestr? Beth oedd rydym yn ei defnyddio i ddynodi diwedd ein ciw? Y pennaeth yw'r pennaeth ein ciw, y dechrau ein ciw. Beth yw diwedd ein ciw? [Mae myfyrwyr yn] Maint. >> Maint, yn union. Felly mae ein elfennau newydd yn mynd i mewn ar faint, a'r elfennau yr ydym yn eu cymryd i ffwrdd yn dod oddi ar ben. Pan fyddwn yn enqueue i'r elfen nesaf, rydym yn ei roi i mewn yn maint. [Myfyrwyr] Cyn i chi roi hynny fodd bynnag, faint oedd 1, dde? [Hardison] Hawl. Felly, nid eithaf yn y maint. + Nid yw maint, +1, ond pen +. Oherwydd ein bod yn symud popeth gan y swm pen. Felly dyma, yn awr rydym wedi cael ciw o faint 1 sy'n dechrau ar fynegai 1. Mae'r gynffon yn fynegai 2. Ydw? 

[Myfyrwyr] Beth sy'n digwydd pan fyddwch yn dequeue llinynnau [0], ac y tannau 'slotiau mewn cof dim ond yn cael eu gwagio, yn y bôn, neu eu hanghofio yn unig? [Hardison] Yeah. Yn yr ystyr hwn, rydym yn unig yn anghofio nhw. Os ydym yn storio copïau ohonynt ar gyfer - Bydd strwythurau data llawer yn aml yn storio eu copïau eu hunain o'r elfennau fel na fydd y person sy'n rheoli'r strwythur data oes rhaid i chi boeni am ble holl awgrymiadau yn mynd. Mae'r strwythur data a gedwir ar bopeth, yn cynnal ar yr holl gopïau, i wneud yn siŵr bod popeth yn parhau yn briodol. Fodd bynnag, yn yr achos hwn, mae'r strwythurau data yn unig, er symlrwydd, nid ydynt yn gwneud copïau o unrhyw beth yr ydym yn storio ynddynt. [Myfyrwyr] Felly y mae y casgliad di-dor o -? >> Ydy. Os ydym yn edrych yn ôl ar yr hyn y diffiniad yn y strwythur hwn, mae'n. Dim ond amrywiaeth safonol fel chi wedi ei weld, amrywiaeth o * torgoch s. A yw hynny'n -? >> Yeah, yr oeddwn yn meddwl tybed os byddwch yn y pen draw yn rhedeg allan o gof, i ryw raddau, os oes gennych yr holl mannau gwag yn eich casgliad? [Hardison] Yeah, mae hynny'n bwynt da. 

Os ydym yn edrych ar yr hyn sydd wedi digwydd yn awr ar y pwynt hwn, rydym wedi llenwi ein ciw, mae'n edrych fel. Ond nid ydym wedi llenwi mewn gwirionedd i fyny ein ciw oherwydd bod gennym ciw sy'n maint 2, ond mae'n dechrau ar mynegai 1, oherwydd dyna lle mae ein pwyntydd pen. Fel yr oeddech yn dweud, yr elfen honno yn y llinynnau [0], ar mynegai 0 Nid yw yno mewn gwirionedd. Dyw hi ddim yn ein ciw anymore. Rydym nid yn unig yn trafferthu i fynd i mewn a ysgrifennu drosto pan fyddwn yn ei dequeued. Felly hyd yn oed er ei fod yn edrych fel ein bod wedi rhedeg allan o gof, nid ydym mewn gwirionedd. Y fan honno ar gael i ni eu defnyddio. Mae ymddygiad priodol, pe baem yn ceisio ac yn gyntaf dequeue rhywbeth fel "bye", a fyddai'n pop bye i ffwrdd. Nawr ein ciw yn dechrau ar mynegai 2 ac o faint 1. Ac yn awr os ydym yn ceisio ac yn enqueue rhywbeth eto, dyweder 50, Dylai 50 yn mynd yn y fan a'r lle yn mynegai 0 oherwydd ei fod yn dal i fod ar gael i ni. Ie, Saad? [Saad] yw hynny'n digwydd yn awtomatig? [Hardison] Nid yw'n digwydd yn eithaf awtomatig. Mae'n rhaid i chi wneud y math i wneud iddo weithio, ond yn ei hanfod yr hyn yr ydym wedi'i wneud yw ein bod wedi ei lapio yn unig o gwmpas. [Saad] A yw'n iawn os mae hyn yn cael twll yn y canol ohono? [Hardison] Mae'n os gallwn wneud y math gweithio allan yn iawn. 

Ac mae'n troi allan nad yw hynny mewn gwirionedd sy'n anodd i wneud gyda'r gweithredwr mod. Felly, yn union fel y gwnaethom gyda Cesar a'r pethau crypto, defnyddio mod, gallwn gael pethau i lapio o gwmpas ac yn dal i fynd o gwmpas ac o amgylch ac o gwmpas gyda ein ciw, gadw'r pwyntydd pen symud o gwmpas. Hysbysiad bod maint bob amser yn parchu y nifer o elfennau mewn gwirionedd o fewn y ciw. Ac mae'n dim ond y pwyntydd pen sy'n cadw seiclo drwy. Os ydym yn edrych ar beth ddigwyddodd yma, os ydym yn mynd yn ôl i'r dechrau, a 'ch jyst gwylio beth sy'n digwydd i'r pen pan fyddwn yn enqueue rhywbeth, ni ddigwyddodd dim i'r pen. Pan fyddwn yn enqueued rhywbeth arall, ni ddigwyddodd dim i'r pen. Gynted ag y byddwn dequeued rhywbeth, mae'r pennaeth yn mynd i fyny gan un. Rydym yn enqueued rhywbeth, dim byd yn digwydd i'r pen. Pan fyddwn yn dequeue rywbeth, yn sydyn y pennaeth yn cael ei cynyddran. Pan fyddwn yn enqueue rhywbeth, dim byd yn digwydd i'r pen. 

Beth fyddai'n digwydd ar y pwynt hwn pe baem yn dequeue rhywbeth eto? Unrhyw syniadau? Beth fyddai'n digwydd i'r pen? Beth ddylai ddigwydd i ben pe baem yn dequeue rhywbeth arall? Mae'r pennaeth ar hyn o bryd ar fynegai 2, sy'n golygu bod y pennaeth y ciw yw llinynnau [2]. [Myfyrwyr] Pa dychwelyd 0? >> Dylai ddychwelyd i 0. Dylai lapio yn ôl o gwmpas, yn union. Hyd yn hyn, bob tro y byddem ni'n ei alw dequeue, rydym wedi bod yn ychwanegu un at y pennaeth, ychwanegu un at y pennaeth, ychwanegu un at y pennaeth, ychwanegu un at y pennaeth. Cyn gynted ag y pwyntydd i'r pen yn cael at y mynegai ddiwethaf yn ein amrywiaeth, yna mae'n rhaid i lapio o gwmpas yn ôl i'r dechrau, ewch yn ôl i 0. [Charlotte] Beth sy'n pennu'r gallu y ciw mewn pentwr? [Hardison] Yn yr achos hwn, rydym wedi dim ond bod yn defnyddio cyson a ddiffinnir #. >> Iawn. [Hardison] Yn y gwir. Ffeil c, gallwch fynd i mewn a dail ag ef ychydig a'i gwneud mor fawr neu mor fach ag y dymunwch. [Charlotte] Felly pan fyddwch chi'n ei wneud yn ciw, sut ydych chi'n gwneud y cyfrifiadur yn gwybod pa mor fawr ydych am y pentwr i fod? [Hardison] Dyna gwestiwn mawr. Mae cwpl o ffyrdd. Un ydy at jyst diffinio o flaen llaw ac yn dweud hyn yn mynd i fod ciw sydd 4 elfen neu 50 elfen neu 10,000. Y ffordd arall yw gwneud yr hyn y Folks haciwr rhifyn yn ei wneud ac yn creu swyddogaethau i gael eich ciw yn tyfu yn ddeinamig wrth i bethau mwy yn cael ei llwytho i mewn 

[Charlotte] Felly, er mwyn mynd â'r opsiwn cyntaf, pa gystrawen ydych chi'n eu defnyddio i ddweud wrth y rhaglen beth yw maint y ciw? [Hardison] Ah. Felly, gadewch i ni gael allan o hyn. Rwy'n dal yn stack.c yma, felly Im 'jyst yn mynd i sgrolio i fyny at y top yma. Allwch chi weld yr hawl yma? Dyma'r # diffinio gallu 10. Ac mae hyn bron yr un gystrawen union sydd gennym ar gyfer ciw. Ac eithrio mewn ciw, rydym wedi cael y maes hwnnw strwythur ychwanegol yma. [Charlotte] O, yr wyf yn meddwl y gallu golygu y gallu ar gyfer y llinyn. [Hardison] Ah. >> Dyna 'i' uchafswm hyd y gair. >> Got iddo. Yeah. Mae'r gallu yma - mae hynny'n bwynt da. Ac mae hyn yn rhywbeth sy'n anodd oherwydd yr hyn yr ydym wedi datgan yma amrywiaeth o * torgoch s. Mae amrywiaeth o awgrymiadau. Mae hwn yn amrywiaeth o chars. Mae hyn yn debyg yr hyn yr ydych wedi gweld pan fyddwch wedi bod yn datgan eich byfferau ar gyfer ffeil I / O, pan fyddwch wedi bod yn creu llinynnau llaw ar y pentwr. Fodd bynnag, yr hyn sydd gennym yma amrywiaeth o torgoch * s. Felly mae'n amrywiaeth o awgrymiadau. Mewn gwirionedd, os ydym yn chwyddo yn ôl allan ac rydym yn edrych ar yr hyn sy'n mynd ymlaen yma yn y cyflwyniad, byddwch yn gweld bod yr elfennau gwirioneddol, mae'r data cymeriad nad yw'n cael ei storio o fewn y rhengoedd ei hun. Beth sy'n cael ei storio o fewn ein casgliad yma yn awgrymiadau ar gyfer data cymeriad. Iawn. Felly, rydym wedi gweld sut y mae maint y ciw yn union fel ag y pentwr, maint bob amser yn parchu nifer o elfennau ar hyn o bryd yn y ciw. Ar ôl gwneud 2 enqueues, y maint yw 2. Ar ôl gwneud dequeue y maint yn awr 1. Ar ôl gwneud un arall enqueue y maint yn ôl i fyny i 2. Felly mae'r maint yn bendant yn parchu nifer o elfennau yn y ciw, ac yna y pen yn unig yn cadw beicio. Mae'n mynd o 0-1-2, 0-1-2, 0-1-2. A phob tro y byddwn yn galw dequeue, y pwyntydd pen yn cael ei fyny ar y mynegai nesaf. Ac os bydd y pennaeth ar fin mynd dros, mae'n dolenni yn ôl o gwmpas i 0. Felly, gyda hynny, gallwn ysgrifennu'r swyddogaeth dequeue. Ac rydym yn mynd i adael y swyddogaeth enqueue i chi guys i weithredu yn lle hynny. 

Pan fyddwn yn dequeue elfen allan o'n ciw, beth oedd y peth cyntaf wnaeth Daniel pan ddechreuodd ysgrifennu'r swyddogaeth pop i pentyrrau? Gadewch i mi glywed gan rywun sydd heb siarad eto. Gadewch i ni weld, Saad, ydych chi'n cofio beth wnaeth Daniel fel y peth cyntaf pan ysgrifennodd pop? [Saad] Nid oedd, fe - >> Roedd profi am rywbeth. [Saad] Os faint yn fwy na 0. >> Yn union. A beth oedd y profion ar gyfer? [Saad] Dyna oedd yn profi i weld a oes unrhyw beth y tu mewn y rhesi. [Hardison] Yeah. Yn union. Felly, nad ydych yn gallu pop unrhyw beth allan o'r pentwr os yw'n wag. Yn yr un modd, ni allwch dequeue unrhyw beth o ciw os yw'n wag. Beth yw'r peth cyntaf y dylem ei wneud yn ein swyddogaeth dequeue yma, yn eich barn chi? [Saad] Os faint yn fwy na 0? >> Yeah. Yn yr achos hwn, rwyf wedi eu profi mewn gwirionedd dim ond i weld os yw'n 0. Os yw'n 0, gallwn ddychwelyd null. Ond rhesymeg union yr un. A gadewch i ni barhau gyda hyn. Os nad yw maint yw 0, ble mae'r elfen yr ydym am ei dequeue? [Saad] Yn y pen? >> Yn union. Gall Rydym yn unig dynnu allan yr elfen gyntaf yn ein ciw trwy fynd i'r elfen yn y pen. Dim byd crazy. Ar ôl hynny, beth ddylem ei wneud? Beth sy'n rhaid i hyn ddigwydd? Beth oedd y peth arall yr ydym yn sôn amdanynt yn dequeue? Mae dau yn rhaid i bethau ddigwydd, oherwydd ein ciw wedi newid. [Daniel] Lleihau maint. >> Mae'n rhaid i ni leihau faint, a chynyddu'r pen? Yn union. Cynyddu y pen, ni allwn yn unig yn cynyddu blindly y pen, cofiwch. Ni allwn wneud queue.head + +. Mae'n rhaid i ni hefyd yn cynnwys y mod gan y capasiti. A pham yr ydym yn mod gan y gallu, Stella? [Stella] Oherwydd ei fod wedi i lapio o gwmpas. >> Yn union. Rydym yn mod gan y gallu oherwydd ei fod wedi i lapio o gwmpas yn ôl i 0. Felly nawr, yn y fan hon, gallwn wneud yr hyn a ddywedodd Daniel. Gallwn lleihau a maint. Ac yna gallwn fynd yn ôl yr elfen a oedd ar frig y ciw. Mae'n edrych yn fath o gnarly ar y dechrau. Efallai y bydd gennych gwestiwn. Mae'n ddrwg gennym? 

[Sam] Pam yn gyntaf ar ben y ciw? Ble mae hynny'n mynd? [Hardison] Daw o'r bedwaredd linell o'r gwaelod. Ar ôl i ni profi i wneud yn siŵr nad yw ein ciw yn wag, rydym yn tynnu allan * torgoch yn gyntaf, rydym yn tynnu allan yr elfen sydd wedi eistedd ar y mynegai pen o'n amrywiaeth, ein llinynnau, >> amrywiaeth a galw yn gyntaf? [Hardison] Ac rydym yn galw yn gyntaf. Yeah. Dim ond i ddilyn i fyny ar hynny, pam ydych chi'n meddwl ein bod ni wedi gorfod gwneud hynny? [Sam] Mae pob cyntaf dim ond dychwelyd q.strings [q.head]? >> Yeah. >> Oherwydd ein bod yn gwneud hyn newid y q.head gyda'r swyddogaeth mod, ac nid oes ffordd o wneud hynny o fewn llinell dychwelyd hefyd. [Hardison] Yn union. Rydych yn fan a'r lle ar. Sam wedi llwyr gweld ar. Y rheswm rydym yn gorfod tynnu allan yr elfen gyntaf yn ein ciw ac yn ei storio mewn amrywiol oherwydd bod y llinell hon lle'r oeddem wedi q.head yn unig, does dim gweithredwr mod i mewn 'na mae hynny'n rhywbeth y gallwn ei wneud ac wedi dod i rym ar y pen heb - mewn un llinell. Felly, rydym mewn gwirionedd yn rhaid i ni dynnu allan yr elfen gyntaf, ac yna addasu y pen, addasu maint, ac yna dychwelyd yr elfen ein bod yn tynnu allan. Ac mae hyn yn rhywbeth y byddwn yn gweld yn dod i fyny yn ddiweddarach gyda rhestrau cysylltiedig, gan ein bod yn chwarae o gwmpas gyda nhw. Yn aml pan fyddwch chi'n rhyddhau neu waredu rhestrau cysylltiedig angen i chi gofio i'r elfen nesaf, y pwyntydd nesaf rhestr cysylltiedig cyn cael gwared o'r un bresennol. Oherwydd fel arall byddwch yn ei daflu y wybodaeth yr hyn sy'n weddill yn y rhestr. Yn awr, os byddwch yn mynd i eich offer, byddwch yn agor i fyny queue.c-x-allan o hyn. Felly, os wyf yn agor queue.c, gadewch i mi chwyddo i mewn yma, byddwch yn gweld bod gennych ffeil tebyg-edrych. Tebyg sy'n edrych ffeil i'r hyn oedd gennym yn gynharach gyda stack.c. Rydym wedi cael ein strwythur ar gyfer ciw a ddiffinnir yn union fel y gwelsom ar y sleidiau. 

Rydym wedi ein swyddogaeth enqueue sydd i chi ei wneud. Ac mae gennym y swyddogaeth dequeue yma. Mae'r swyddogaeth dequeue yn y ffeil yn cael ei heb ei weithredu, ond byddaf yn ei roi yn ôl i fyny ar y PowerPoint er mwyn i chi deipio i mewn, os hoffech. Felly, ar gyfer y 5 munud nesaf, neu felly, rydych guys gweithio ar enqueue sydd bron yn union y gwrthwyneb i dequeue. Nid oes rhaid i chi addasu pen pan fyddwch chi'n enqueueing, ond beth sydd gennych i'w addasu? Maint. Felly, pan fyddwch yn enqueue, mae'r pennaeth yn aros heb ei gyffwrdd, maint yn cael ei newid. Ond mae'n cymryd ychydig o - bydd yn rhaid i chi chwarae o gwmpas gyda'r mod i ffigur yn union beth mynegai dylai'r elfen newydd yn cael ei fewnosod yn. Felly, byddaf yn rhoi i chi guys ychydig, rhowch dequeue yn ôl i fyny ar y sleid, ac wrth i chi guys gennych gwestiynau, gweiddi nhw allan fel y gallwn i gyd yn siarad amdanynt fel grŵp. Hefyd, gyda maint rydych peidiwch - pan fyddwch yn newid y maint, gallwch bob amser yn unig - sydd gennych i mod maint erioed? [Daniel] Rhif >> Nid oes rhaid i mod maint, ar y dde. Gan y bydd y maint bob amser, os you're - gan dybio eich bod yn rheoli pethau yn briodol, bydd y maint bob amser fod rhwng 0 a 3. Ble mae'n rhaid i chi mod pan fyddwch yn gwneud enqueue? [Myfyrwyr] Dim ond ar gyfer y pennaeth. >> Dim ond ar gyfer y pennaeth, yn union. A pham yr ydych yn rhaid i mod o gwbl yn enqueue? Pryd mae sefyllfa lle byddai'n rhaid i chi mod? [Myfyrwyr] Os oes gennych pethau yn fannau, fel mewn mannau 1 a 2, ac yna roedd angen i chi ychwanegu rhywbeth ar 0. [Hardison] Yeah, yn union. Felly, os yw eich pwyntydd pen ar y diwedd un, neu os yw eich maint yn ogystal â'ch pen yn fwy, neu yn hytrach, yn mynd i lapio o amgylch y ciw. 

Felly, yn y sefyllfa yr ydym wedi mynd i fyny yma ar y sleid ar hyn o bryd, os ydw i eisiau enqueue rhywbeth yn iawn yn awr, rydym am i enqueue rhywbeth yn mynegai 0. Felly, os ydych yn edrych ar ble y 50 yn mynd, a galwaf enqueue 50, mae'n mynd i lawr yno ar y gwaelod. Mae'n mynd mewn 0 mynegai. Mae'n disodli'r 'hi' a dequeued eisoes. [Daniel] Peidiwch â ydych yn gofalu am hynny yn dequeue yn barod? Pam ei fod yn gwneud unrhyw beth gyda'r pennaeth enqueue? [Hardison] O, felly nid ydych yn addasu'r pennaeth, sori. Ond mae'n rhaid i chi ddefnyddio'r gweithredwr mod pan ydych yn cyrchu yr elfen eich bod am enqueue pan fyddwch yn cyrchu i'r elfen nesaf yn eich ciw. [Basil] Nid wyf yn gwneud hynny, ac fe ges i "llwyddiant" ar yno. [Daniel] O, yr wyf yn deall yr hyn rydych yn ei ddweud. [Hardison] Felly rydych didn't - rydych yn unig oedd yn q.size? [Basil] Yeah. Rwyf wedi newid dim ond ochr, doeddwn i ddim yn gwneud unrhyw beth gyda'r pennaeth. [Hardison] Nid oes mewn gwirionedd yn rhaid i chi ailosod y pen i fod yn unrhyw beth, ond pan fyddwch yn fynegai i'r casgliad llinynnau, chi mewn gwirionedd yn rhaid i chi fynd ymlaen a chyfrifo lle mae'r elfen nesaf, oherwydd withe y pentwr, yr elfen nesaf yn eich simnai oedd bob amser yn ar y mynegai sy'n cyfateb i'r maint. Os ydym yn edrych yn ôl i fyny ar ein gwthio pentwr swyddogaeth, gallem bob amser yn plunk yn ein elfen newydd i'r dde wrth maint mynegai. Er bod y ciw, ni allwn wneud hynny oherwydd os ydym yn y sefyllfa hon, os ydym enqueued byddai 50 ein llinyn newydd yn mynd i'r dde wrth dannau [1] nad ydym am ei wneud. Rydym yn awyddus i gael y llinyn newydd yn mynd yn mynegai 0. 

A oes gan unrhyw un - ie? [Myfyrwyr] Mae gen i gwestiwn, ond nid yw'n gysylltiedig mewn gwirionedd. Beth mae'n ei olygu pan fydd rhywun yn union yn galw rhywbeth fel pwyntydd pred? Beth yw enw byr ar gyfer? Rwy'n gwybod mai dim ond enw. [Hardison] pwyntydd Pred? Gadewch i ni weld. Ym mha gyd-destun? [Myfyrwyr] Roedd gyfer y mewnosodiad. Gallaf ofyn i chi yn nes ymlaen os ydych eisiau gan nad yw'n gysylltiedig mewn gwirionedd, ond yr wyf yn unig - [Hardison] O cod rhowch Dewi Sant o ddarlith? Gallwn dynnu bod i fyny a siarad am hynny. Byddwn yn siarad am hynny nesaf, pan gawn restrau cysylltiedig. 

Felly, gadewch i ni yn gyflym iawn yn edrych ar yr hyn y swyddogaeth enqueue yn edrych fel. Beth oedd y peth cyntaf y mae pobl yn ceisio ei wneud yn eich llinell enqueue? Into y ciw? Yn debyg i beth wnaethoch chi am pentwr gwthio. Beth wnaethoch chi ei wneud, Stella? [Stella, annealladwy] [Hardison] Yn union. Os (q.size == GALLU) - Angen i mi roi fy braces yn y lle cywir - dychwelyd ffug. Zoom mewn ychydig bach. Iawn. Nawr beth yw'r peth nesaf a oedd gennym i wneud? Union fel y pentwr, a'u gosod yn y lle iawn. Ac felly, beth oedd y lle iawn i fewnosod hynny? Gyda'r pentwr oedd maint y mynegai, gyda hyn nid yw'n hollol hynny. [Daniel] gennyf q.head--neu - q.strings >>? >> Yeah. q.strings [q.head + q.size mod GALLU]? [Hardison] Mae'n debyg eisiau rhoi cromfachau o gwmpas y fel ein bod ni'n cael y flaenoriaeth briodol ac felly dyna cleart i bawb. A gosod y gyfartal? >> I str? >> I str. Great. Ac yn awr beth yw'r peth olaf y mae'n rhaid i ni ei wneud? Yn union fel y gwnaethom yn y pentwr. >> Cynnyddu y maint? >> Cynnyddu y maint. Boom. Ac yna, gan fod y cod cychwynnol newydd ddychwelyd ffug yn ddiofyn, rydym am newid hyn yn wir os bydd popeth yn mynd drwyddo ac aiff popeth yn iawn. Mae pob hawl. Mae hynny'n llawer o wybodaeth ar gyfer adran. Nid ydym yn eithaf drosodd. Rydym eisiau siarad yn gyflym iawn am eu pennau eu hunain sy'n gysylltiedig â'r rhestrau. 'N annhymerus' roi hyn i fyny fel y gallwn fynd yn ôl ato yn nes ymlaen. Ond gadewch i ni fynd yn ôl at ein cyflwyniad i rai yn unig yn fwy sleidiau. Felly enqueue yn TODO, yn awr rydym wedi eu cyflawni. 

Nawr gadewch i ni edrych ar eu pennau eu hunain sy'n gysylltiedig â'r rhestrau. Rydym yn sôn am y rhain yn fwy o ychydig mewn darlith. Faint ohonoch guys weld y demo lle cawsom bobl lletchwith pwyntio i bob rhifau eraill a daliad? >> Roeddwn yn hynny. >> Beth wnaethoch chi guys meddwl? Yn gwneud hynny, gobeithio egluro'r hyn dipyn ychydig? Gyda rhestr, mae'n troi allan ein bod yn ymdrin â'r math hwn ein bod ni'n mynd i alw nod. Tra gyda'r ciw ac i'r stac cawsom structs y byddem yn galw ciw yn simnai, rydym yn cael y rhain ciw newydd mewn mathau stac, dyma restr yn wir yn gwneud dim ond cynnwys criw o nodau. Yn yr un ffordd ag y llinynnau yn unig yw criw o chars holl drefnu nesaf at ei gilydd. Mae rhestr cysylltiedig yn unig yw nod ac un arall nod ac un arall ac un arall nod nod. Ac yn hytrach na malu holl nodau at ei gilydd a'u storio contiguously iawn nesaf at ei gilydd mewn cof, cael y pwyntydd nesaf yn ein galluogi i storio nodau lle bynnag y bo, ar hap. Ac yna fath o wifren i gyd gyda'i gilydd i bwynt o un i'r llall. 

A beth oedd y fantais fawr bod hyn yn cael dros arae? Dros bopeth storio contiguously yn sownd yn unig nesaf at ei gilydd? Byddwch yn cofio? Yeah? >> Dyrannu cof Dynamic? >> Dyrannu cof Dynamic ym mha ystyr? [Myfyrwyr] Yn y gallwch gadw ei gwneud yn fwy ac nid oes rhaid i chi symud eich casgliad cyfan? [Hardison] Yn union. Felly, gydag amrywiaeth, pan fyddwch eisiau rhoi elfen newydd i mewn i ganol ohono, rhaid i chi symud popeth i wneud lle. Ac fel yr ydym yn sôn am y ciw, dyna pam rydym yn cadw'r pwyntydd pen, fel nad ydym yn gyson yn symud pethau. Oherwydd bod yn cael ddrud os oes gennych amrywiaeth mawr ac rydych yn gyson yn gwneud y mewnosodiadau ar hap. Tra â rhestr, y cyfan mae'n rhaid i chi ei wneud yw ei daflu ar nod newydd, addasu'r awgrymiadau, ac rydych yn ei wneud. Beth sucks am hyn? Ar wahân i'r ffaith nad yw mor hawdd i weithio gyda fel arae? Yeah? [Daniel] Wel, yr wyf yn dyfalu ei fod yn llawer anoddach i gael gafael ar elfen benodol yn y rhestr sy'n gysylltiedig? [Hardison] Allwch chi ddim neidio i elfen mympwyol yng nghanol eich rhestr cysylltiedig. Sut ydych yn rhaid i chi wneud hyn yn lle? >> Mae'n rhaid i chi gamu trwy'r peth cyfan. [Hardison] Yeah. Mae'n rhaid i chi fynd drwy un ar y tro, un ar y tro. Mae'n enfawr - mae'n boen. Beth y llall - mae gwendid arall i hyn. [Basil] Ni allwch fynd ymlaen ac yn ôl? Mae'n rhaid i chi fynd un cyfeiriad? [Hardison] Yeah. Felly sut rydym yn datrys hynny, weithiau? [Basil] ddwbl-cysylltiedig rhestrau? >> Yn union. Mae rhestrau ddwbl-gysylltiedig. Mae yna hefyd - sori? 

[Sam] A yw bod yr un peth â defnyddio'r peth pred hynny - Fi jyst yn cofio, nid yw bod yr hyn y peth pred yw? Onid yw bod rhwng ddwbl ac yn unigol? [Hardison] Gadewch i ni edrych ar beth yn union oedd yn ei wneud. Felly, yma rydym yn mynd. Dyma'r cod rhestr. Yma, mae gennym predptr, yma. A yw hyn yn beth rydych yn sôn amdanynt? Felly roedd hyn - ei fod yn rhyddhau rhestr ac mae o'n ceisio i storio pwyntydd iddo. Nid yw hyn yn ddwbl, yn unigol cysylltiedig-rhestrau. Gallwn siarad mwy am hyn yn ddiweddarach gan fod hyn yn sôn am ryddhau'r rhestr ac yr wyf am ddangos rhai pethau eraill yn gyntaf. ond mae'r un - mae'n cofio gwerth PTR [Myfyrwyr] O, mae'n pwyntydd blaenorol? >> Yeah. Er mwyn i ni wedyn cynyddiad ptr ei hun cyn i ni wedyn yn rhad ac am ddim beth yw predptr. Oherwydd na allwn ptr rhad ac am ddim ac yna galw ptr = ptr nesaf, dde? Byddai hynny'n ddrwg. Felly, gadewch i ni weld, yn ôl i'r guy. 

Y peth drwg eraill am restrau yw bod ond gydag amrywiaeth rydym yn unig yn cael yr holl elfennau eu hunain yn pentyrru nesaf at ei gilydd, yma rydym hefyd wedi cyflwyno hyn pwyntydd. Felly mae 'na darn ychwanegol o gof ein bod yn gorfod defnyddio ar gyfer pob elfen ein bod yn cadw yn ein rhestr. Rydym yn cael hyblygrwydd, ond mae'n dod ar gost. Mae'n dod â'r cost amser, ac mae'n dod gyda gost hon lawer o gof. Amser yn yr ystyr bod gennym yn awr i fynd drwy bob elfen yn yr amrywiaeth i ddod o hyd i'r un ar fynegai 10, neu y byddai wedi bod mynegai 10 yn arae. 

Dim ond yn gyflym iawn, pan fyddwn diagram allan rhestrau hyn, fel arfer rydym yn dal gafael ar ben y rhestr neu y pwyntydd cyntaf y rhestr ac yn nodi bod hyn yn wir pwyntydd. Mae'n dim ond 4 bytes. Nid yw'n 'an nod ei hun. Felly byddwch yn gweld nad oes ganddo werth int ynddo, dim pwyntydd nesaf ynddo. Mae'n llythrennol dim ond pwyntydd. Mae'n mynd i gyfeirio at rywbeth sydd yn strwythur nod go iawn. [Sam] Mae pwyntydd a elwir yn nod? >> Mae hyn yn - dim. Mae hyn yn rhoi syniad inni am rywbeth y nod fath. Mae'n rhoi syniad i strwythur nod. >> O, iawn. Diagram ar y chwith, y cod ar y dde. Gallwn osod i null, sy'n ffordd dda i ddechrau. Pan fyddwch yn diagram, i chi naill ai ysgrifennu fel null neu gallwch ei roi llinell trwyddo yn hoffi hynny. 

Un o'r ffyrdd hawsaf i weithio gyda rhestrau, ac rydym yn gofyn i chi yn y ddau prepend ac atodi, i weld y gwahaniaethau rhwng y ddau, ond Hoffech chi barhau? yn bendant yn haws. Pan fyddwch yn prepend, dyma lle rydych - pan fyddwch yn prepend (7), byddwch yn mynd a chreu'r strwythur nod ac eich bod yn gosod cyntaf i bwyntio ato, oherwydd yn awr, ers i ni ei prepended, mae'n mynd i fod ar ddechrau'r y rhestr. Os ydym prepend (3), sy'n creu un arall nod, ond erbyn hyn 3 yn dod cyn 7. Felly rydym yn ei hanfod yn gwthio pethau ar ein rhestr. Nawr, gallwch weld bod prepend, weithiau mae pobl yn ei alw'n gwthio, oherwydd eich bod yn gwthio elfen newydd ar eich rhestr. Mae hefyd yn hawdd i'w dileu ar flaen rhestr. Felly, bydd pobl yn aml yn galw y pop. Ac yn y modd hwnnw, gallwch chi ei efelychu pentwr ddefnyddio rhestr cysylltiedig. Wps. Mae'n ddrwg gennym, yn awr rydym yn mynd i atodi. Felly dyma ni prepended (7), yn awr rydym prepend (3). Os ydym prepended rhywbeth arall ar y rhestr hon, os ydym prepended (4), yna byddem wedi 4 ac yna 3 ac yna 7. Felly, yna gallem pop a chael gwared 4, Dileu 3, tynnu 7. Yn aml, mae'r ffordd fwy greddfol i feddwl am hyn yw gyda Atodi. Felly, yr wyf wedi diagrammed beth y byddai'n edrych yn debyg gyda atodi yma. Yma, sydd ynghlwm (7) nad yw'n edrych yn wahanol oherwydd dim ond un elfen yn y rhestr. Ac Ynghlwm (3) yn rhoi hynny ar y diwedd. Efallai y gallwch chi weld ar hyn o bryd y gamp gyda Atodi yw bod ers i ni dim ond yn gwybod lle mae'r ddechrau'r rhestr yw, i atodi i restr rhaid i chi gerdded yr holl ffordd trwy'r rhestr i gyrraedd y diwedd, stopio, yna adeiladu eich nod a phopeth plunk i lawr. Gwifren holl bethau i fyny. Felly, gyda prepend, wrth i ni jyst rhwygo drwy hyn yn gyflym iawn, pan fyddwch yn prepend i restr, mae'n weddol syml. 

Byddwch yn gwneud eich nod newydd, yn cynnwys rhywfaint o ddyraniad cof deinamig. Felly dyma rydym yn gwneud strwythur nod ddefnyddio malloc. Felly malloc ein bod yn defnyddio oherwydd bydd hynny'n neilltuo cof i ni ar gyfer yn ddiweddarach oherwydd nid ydym am hyn - rydym am i'r cof i barhau am amser hir. Ac rydym yn cael pwyntydd i'r lle er cof am ein bod wedi dyrannu yn unig. Rydym yn defnyddio maint y nod, nid ydym yn swm y caeau. Nid ydym yn cynhyrchu â llaw y nifer o bytes, yn lle hynny rydym yn defnyddio sizeof fel ein bod yn gwybod ein bod yn cael y nifer priodol o bytes. Rydym yn gwneud yn siwr i brofi bod ein galwad malloc llwyddo. Mae hyn yn rhywbeth rydych am ei wneud yn gyffredinol. Ar beiriannau modern, nid yw rhedeg allan o gof yn rhywbeth sy'n hawdd oni bai eich bod dyrannu tunnell o bethau a gwneud rhestr enfawr, ond os ydych yn adeiladu pethau am, dyweder, fel iPhone neu Android, oes gennych adnoddau cof cyfyngedig, yn enwedig os ydych chi'n gwneud rhywbeth dwys. Felly, mae'n beth da i fynd i mewn i waith. 

Hysbysu fy mod wedi defnyddio swyddogaethau chwpl gwahanol yma eich bod wedi gweld bod yn fath o newydd. Felly fprintf yn union fel printf ac eithrio ei ddadl gyntaf yn y nant yr ydych eisiau argraffu. Yn yr achos hwn, rydym am i argraffu i'r llinyn gwall safonol sy'n wahanol i'r outstream safonol. Yn ddiofyn mae'n dangos i fyny yn yr un lle. Mae hefyd yn argraffu allan i'r derfynfa, ond gallwch - defnyddio rhai gorchmynion i chi ddysgu am, y technegau ailgyfeirio rydych wedi dysgu amdanynt yn Tommy fideo am 4 set problem, gallwch gyfeirio ei i ardaloedd gwahanol, yna adael, dde yma, allanfeydd eich rhaglen. Ydyw yn y bôn yn hoffi dychwelyd o brif ac eithrio yn defnyddio allanfa oherwydd ni fydd yma dychwelyd yn gwneud unrhyw beth. Nid ydym yn yn y brif, felly dychwelyd yn gadael y rhaglen fel yr ydym ei eisiau. Felly, rydym yn defnyddio'r swyddogaeth ymadael a rhoi cod gwall. Yna dyma rydym yn gosod gwerth faes y nod newydd, ei maes i fod yn gyfartal i i, ac yna rydym yn gwifren i fyny. Rydym yn gosod pwyntydd y nod newydd nesaf i bwynt yn gyntaf, ac yna bydd cyntaf yn awr yn cyfeirio at y nod newydd. Mae'r llinellau cyntaf y cod, rydym yn adeiladu mewn gwirionedd yn y nod newydd. Nid y ddwy linell olaf o'r swyddogaeth hon, ond y rhai cyntaf. Gallwch dynnu allan mewn gwirionedd i mewn i swyddogaeth, i mewn i swyddogaeth cynorthwy-ydd. Dyna yn aml yn yr hyn rwy'n ei wneud yw, yr wyf dynnu allan i swyddogaeth, Wyf yn ei alw rhywbeth fel adeiladu nod, ac sy'n cadw'r swyddogaeth prepend eithaf bach, dim ond 3 llinell hynny. I wneud galwad i fy swyddogaeth nod adeiladu, ac yna popeth gwifren I fyny. 

Y peth olaf rwyf am i ddangos i chi, a byddaf yn gadael i chi wneud atodi a hynny i gyd ar eich pen eich hun, yw sut i ailadrodd dros rhestr. Mae criw o ffyrdd gwahanol i ailadrodd dros rhestr. Yn yr achos hwn, rydym yn mynd i ddod o hyd i hyd y rhestr. Felly, rydym yn dechrau gyda hyd = 0. Mae hyn yn debyg iawn i ysgrifennu strlen am llinyn. Dyma beth rwyf am i ddangos i chi, hyn ar gyfer dolen i'r dde yma. Mae'n edrych kinda ffynci, nid yw'n arferol i int = 0, i <beth bynnag, i + +. Yn hytrach, mae'n ein ymgychwyn n amrywiol i fod yn dechrau'r rhestr. Ac yna er nad yw ein amrywiol iterator yn null, byddwn yn cadw i fynd. Mae hyn oherwydd, yn ôl confensiwn, bydd y diwedd ein rhestr null. Ac yna i gynnydd, yn hytrach na gwneud + +, yr hyn sy'n cyfateb rhestr cysylltiedig o + + yw n = n-> nesaf. 

Byddaf yn gadael i chi lenwi'r bylchau yma oherwydd ein bod allan o amser. Ond yn cadw hyn mewn cof wrth i chi weithio ar eich psets spellr. Rhestrau cysylltiedig, os ydych yn gweithredu tabl hash, Bydd yn bendant yn dod yn handi iawn. A bydd cael y idiom gyfer dolennu dros bethau yn gwneud bywyd yn llawer haws, gobeithio. Unrhyw gwestiynau, yn gyflym? [Sam] A fyddwch yn anfon y SLL gwblhau ac sc? [Hardison] Yeah. 'N annhymerus' anfon sleidiau cwblhau a chorn SLL gwblhau a queue.cs. [CS50.TV]