>> [CHWARAE CERDDORIAETH]
>> DOUG LLOYD: OK, hynny ar y pwynt hwn yn y cwrs,
rydym wedi cynnwys llawer o elfennau sylfaenol o C. Rydym yn gwybod llawer am newidynnau, araeau,
awgrymiadau, holl bethau da.
Mae'r rhai yn cael eu pob math o adeiladu i mewn i weld wrth i'r hanfodion,
ond gallwn wneud mwy, dde?
Gallwn gyfuno pethau at ei gilydd mewn ffyrdd diddorol.
>> Ac felly gadewch i ni wneud hynny, gadewch i ni ddechrau i gangen y tu allan yr hyn y C yn rhoi i ni,
a dechrau creu ein data eu hunain strwythurau ddefnyddio'r rhain adeilad
blociau at ei gilydd i wneud rhywbeth wirioneddol werthfawr, yn ddefnyddiol.
Un ffordd y gallwn wneud hyn yw i siarad am gasgliadau.
Hyd yn hyd yn hyn rydym wedi cael un math o ddata strwythur ar gyfer gynrychioli casgliadau
o hoffi werthoedd, gwerthoedd tebyg.
Byddai hynny yn arae.
Mae gennym gasgliadau o gyfanrifau, neu casgliadau o gymeriadau ac yn y blaen.
>> Strwythurau hefyd yn didoli o ddata strwythur ar gyfer casglu gwybodaeth,
ond nid yw'n ar gyfer casglu fel werthoedd.
Mae fel arfer yn cymysgu gwahanol fathau o ddata ynghyd tu mewn blwch sengl.
Ond nid yw ei hun a ddefnyddir i gadwyn gyda'i gilydd
neu gysylltu gyda'i gilydd tebyg eitemau, fel arae.
Araeau yn wych ar gyfer Elfen edrych i fyny, ond dwyn i gof
ei bod yn anodd iawn i fewnosod i mewn i amrywiaeth,
oni bai ein bod yn gosod ar yr union diwedd y rhesi.
>> Ac yr enghraifft orau gen i am hynny yw math fewnosod.
Os cofiwch ein fideo ar y math mewnosod,
roedd llawer o cost olygu yn
i godi elfennau, ac yn eu symud allan o'r ffordd i ffitio rhywbeth
i ganol eich arae.
Araeau hefyd yn dioddef o un arall broblem, sef anhyblygrwydd.
Pan fyddwn yn datgan arae, rydym yn cael un ergyd yn ei.
Rydym yn cael i ddweud, yr wyf am hyn yn llawer o elfennau.
A allai fod yn 100, y gallai fod yn 1,000, y gallai
fod x lle mae x yn rhif bod y defnyddiwr rhoi i ni mewn brydlon neu yn y gorchymyn
llinell.
>> Ond rydym yn unig yn cael un ergyd ar y sefyllfa, rydym yn peidiwch â mynd i wedyn yn dweud oh, mewn gwirionedd yr wyf yn
angen 101, neu yr wyf yn ei angen x plws 20.
Yn rhy hwyr, rydym eisoes wedi datgan y array, ac os ydym am gael 101 neu x
ynghyd â 20, mae'n rhaid i ni ddatgan amrywiaeth hollol wahanol,
gopïo'r holl elfennau y rhesi drosodd, ac yna mae gennym ddigon.
A beth os ydym yn anghywir eto, beth os ydym ei angen mewn gwirionedd 102, neu x ynghyd â 40,
mae'n rhaid i ni wneud hyn eto.
Fel eu bod yn anhyblyg iawn am newid maint ein data,
ond os ydym yn cyfuno ynghyd rai o'r elfennau sylfaenol yr ydym i wedi eisoes
dysgu am awgrymiadau a strwythurau, yn enwedig gan ddefnyddio cof deinamig
dyrannu â malloc, rydym yn Gall roi'r darnau hyn at ei gilydd
i greu data newydd structure-- a Rhestr gallem say-- cysylltu'n unigol
sy'n ein galluogi i dyfu a crebachu casgliad o werthoedd
ac ni fydd gennym unrhyw le gwastraffu.
>> Felly unwaith eto, rydym yn galw y syniad hwn, syniad hwn, rhestr cysylltiedig.
Yn benodol, yn y fideo hwn rydym yn siarad am rhestr gysylltiedig yn unigol,
ac yna fideo arall byddwn yn siarad rhestrau am cysylltu'n ddwbl, a oedd yn
yn unig yw amrywiad ar thema yma.
Ond mae rhestr cysylltiedig yn unigol yn cynnwys nodau,
nodau dim ond bod yn term-- haniaethol 'i' jyst yn rhywbeth rwy'n galw
mae hynny'n rhyw fath o strwythur, yn y bôn, rwy'n?
Jyst yn mynd i alw ei fod yn node-- ac mae hyn Mae nod dau aelod, neu ddau gae.
Mae ganddo data, fel arfer cyfanrif, fflôt cymeriad,
neu a allai fod rhyw fath ddata arall eich bod wedi diffiniedig gydag def fath.
Ac mae'n cynnwys pwyntydd i nod arall o'r un math.
>> Felly mae gennym ddau beth tu mewn nod hwn, data a pwyntydd
i nod arall.
Ac os byddwch yn dechrau i ddychmygu hyn, gallwch chi feddwl am y peth
fel cadwyn o nodau sy'n yn cael eu cysylltu gyda'i gilydd.
Mae gennym y nod cyntaf, mae'n yn cynnwys data, ac pwyntydd
i'r ail nod, sy'n cynnwys data, ac mae pwyntydd i'r trydydd nod.
Ac felly dyna pam yr ydym yn galw ei fod yn rhestr gysylltiedig, maent yn gysylltiedig â'i gilydd.
>> Beth mae hyn yn arbennig Strwythur nôd yn edrych?
Wel, os ydych yn cofio oddi wrth ein fideo ar diffinio mathau arfer, gyda'r math def,
gallwn ddiffinio structure-- a teipiwch diffinio strwythur fel hyn.
tyepdef sllist struct, ac yna rwy'n ddefnyddio gwerth gair yma fympwyol
i nodi unrhyw fath ddata mewn gwirionedd.
Gallech drosglwyddo cyfanrif neu fflôt, gallech gael beth bynnag y dymunwch.
Dyw hi ddim yn gyfyngedig i ddim ond cyfanrifau, neu unrhyw beth fel 'na.
Felly gwerth yn unig yw mympwyol math data, ac yna pwyntydd
i nod arall o'r un math.
>> Yn awr, mae ychydig o dal yma gyda diffinio strwythur
pan mae'n strwythur hunan cyfeiriadol.
Mae'n rhaid i mi gael dros dro enw ar gyfer fy strwythur.
Ar ddiwedd y dydd yr wyf yn yn glir am ei alw
nod SLL, dyna yn y pen draw y newydd enwi rhan o fy diffiniad math o,
ond ni allaf ddefnyddio nod SLL yng nghanol hyn.
Y rheswm fodolaeth, nid wyf wedi creu math a elwir yn nod SLL
nes i mi gyrraedd y pwynt olaf yma.
Hyd at y pwynt hwnnw, rhaid i mi gael ffordd arall i gyfeirio at y math hwn o ddata.
>> Ac mae hyn yn hunan Math data cyfeiriadol.
Mae'n; s math data o strwythur sy'n cynnwys data,
ac pwyntydd i un arall strwythur o'r un math.
Felly mae angen i mi fod yn gallu cyfeirio at math hwn o ddata o leiaf dros dro,
felly gan roi dros dro enw'r sllist struct
yn caniatáu i mi wedyn dweud fy mod eisiau pwyntydd i'r sllist struct arall,
seren sllist struct, ac yna ar ôl i mi gwblhau y diffiniad,
Gall Galwaf yn awr y math hwn yn nod SLL.
>> Felly dyna pam yr ydych yn gweld yna enw dros dro yma,
ond enw parhaol yma.
Weithiau, efallai y byddwch yn gweld diffiniadau o strwythur,
er enghraifft, nad ydynt yn hunan cyfeiriadol, bod
Nid oes rhaid i enw rhagnodwr yma.
Byddai 'I jyst yn dweud struct typedef, agor Brace cyrliog ac yna'n ei ddiffinio.
Ond os ydych chi'n struct yw hunan cyfeiriadol, gan fod hyn yn un yw,
mae angen i chi benodi Enw'r math dros dro.
Ond yn y pen draw, yn awr ein bod wedi gwneud hyn,
gallwn jyst gyfeirio at nodau hyn, yr unedau hyn,
fel nodau SLL at ddibenion o weddill y fideo.
>> Mae pob hawl, felly rydym yn gwybod sut i greu rhestr nôd cysylltiedig.
Rydym yn gwybod sut i ddiffinio cainc rhestr gysylltiedig.
Yn awr, os ydym yn mynd i ddechrau eu defnyddio i gasglu gwybodaeth,
mae yna un neu ddau o weithrediadau yr ydym yn Mae angen i ddeall a gweithio gyda hwy.
Mae angen inni wybod sut i greu rhestr cysylltiedig allan o awyr denau.
Os nad oes rhestr yn barod, rydym eisiau dechrau un.
Felly, mae angen i ni fod yn gallu i greu rhestr cysylltiedig,
mae angen yn ôl pob tebyg i chwilio drwy'r rhestr gyswllt
i ddod o hyd elfen rydym yn chwilio am.
Mae angen i ni fod yn gallu mewnosod pethau newydd i mewn i'r rhestr,
rydym am ein rhestr i allu tyfu.
Ac yn yr un modd, rydym am fod yn gallu i ddileu pethau oddi ar ein rhestr,
rydym am ein rhestr i allu grebachu.
Ac ar ddiwedd ein rhaglenni, yn enwedig
os ydych yn cofio ein bod dyrannu cof ddeinamig
i adeiladu rhestrau hyn yn nodweddiadol, rydym am i ryddhau hynny i gyd gof
pan fyddwn ni'n ei wneud yn gweithio ag ef.
Ac felly mae angen i ni fod yn gallu ddileu rhestr gysylltiedig cyfan mewn un yn methu plymio.
Felly gadewch i ni fynd drwy'r mae rhai o'r gweithrediadau hyn
a sut y byddwn yn eu delweddu, siarad mewn cod pseudocode benodol.
Felly rydym eisiau creu rhestr gysylltiedig, felly efallai yr ydym
eisiau i ddiffinio swyddogaeth gyda prototeip hwn.
SLL seren nôd, creu, a dwi'n pasio mewn un ddadl, rhywfaint o ddata mympwyol
deipio eto, o ryw fath data mympwyol.
Ond dw i'n returning-- swyddogaeth hon dylai dychwelyd i mi pwyntydd, i yn unigol
nod rhestr gysylltiedig.
Unwaith eto, rydym yn ceisio creu rhestr cysylltiedig allan o awyr denau,
felly mae angen pwyntydd i I y rhestr honno pan dwi'n ei wneud.
>> Felly beth yw'r camau dan sylw yma?
Wel, peth cyntaf dwi'n mynd i'w wneud yn ddynamig
neilltuo lle ar gyfer nod newydd.
Unwaith eto, rydym yn ei greu allan o denau aer, felly mae angen i ni lle malloc ar ei gyfer.
Ac wrth gwrs, yn union ar ôl i ni malloc,
rydym bob amser yn gwirio i wneud yn siŵr bod ein pointer-- doedden ni ddim yn mynd yn ôl null.
Oherwydd os ydym yn ceisio deference pwyntydd nwl,
rydyn ni'n mynd i ddioddef segfault ac nid ydym am hynny.
>> Yna, rydym yn awyddus i lenwi'r yn y maes, rydym am ymgychwyn y cae gwerth
ac ymgychwyn y cae nesaf.
Ac yna rydym am i'r canlynol-- yn y pen draw wrth i'r prototeip swyddogaeth indicates-- rydym am
i ddychwelyd pwyntydd at nod SLL.
Felly beth yn gwneud hyn yn edrych fel eu golwg?
Wel, yn gyntaf rydym yn mynd i ddeinamig neilltuo lle ar gyfer nod SLL newydd,
felly rydym malloc-- dyna cynrychiolaeth weledol
y nôd yr ydym newydd ei greu.
Ac rydym yn gwirio i wneud yn siŵr nid yw'n null-- yn yr achos hwn,
ni fyddai'r darlun yn cael Dangosir fyny os oedd null,
byddem wedi rhedeg allan o gof, felly rydym yn dda i fynd yno.
Felly nawr ein bod ar gamu C, ymgychwyn y maes nodau gwerth.
Wel, yn seiliedig ar swyddogaeth hon ffoniwch Im 'yn arfer fan hyn,
edrych fel yr wyf am eu trosglwyddo mewn 6, felly byddaf 6 yn y maes gwerth.
Yn awr, ymgychwyn y cae nesaf.
Wel, beth ydw i'n mynd i wneud yno, nid oes unrhyw beth nesaf, ar y dde,
dyma'r unig beth yn y rhestr.
Felly beth yw'r peth nesaf yn y rhestr?
>> Ni ddylai fod bwyntio at unrhyw beth, ar y dde.
Does dim byd arall yno, felly beth yw'r y cysyniad rydym yn gwybod am hynny'n nothing--
awgrymiadau i ddim?
Dylai fod yn efallai rydym eisiau i roi pwyntydd null yno,
a byddaf yn cynrychioli'r null pwyntydd fel dim ond blwch coch,
Ni allwn fynd ymhellach.
Fel y byddwn yn gweld ychydig yn nes ymlaen, bydd gennym yn y pen draw cadwyni
o saethau cysylltu nodau hyn at ei gilydd,
ond pan fyddwch yn cyrraedd y bocs coch, dyna null,
Ni allwn fynd ymhellach, dyna ddiwedd y rhestr.
>> Ac yn olaf, rydym yn unig eisiau dychwelyd pwyntydd i'r nod hwn.
Felly byddwn yn ei alw'n newydd, a bydd yn dychwelyd newydd
fel y gellir ei ddefnyddio mewn pa bynnag swyddogaeth greu.
Felly dyna ni, Rydym wedi creu yn unigol rhestr gysylltiedig nod allan o awyr denau,
ac erbyn hyn mae gennym restr y gallwn weithio gyda.
>> Yn awr, gadewch i ni ddweud ein bod eisoes cael cadwyn mawr,
ac rydym yn awyddus i ddod o hyd i rywbeth ynddo.
Ac rydym am swyddogaeth sy'n mynd i ddychwelyd yn wir neu'n anwir, yn dibynnu
ar p'un mae gwerth bodoli yn y rhestr honno.
Mae prototeip swyddogaeth, neu datganiad am y swyddogaeth honno,
Gallai edrych fel this-- Bool yn dod o hyd, a yna rydym am eu trosglwyddo mewn dau dadleuon.
>> Y cyntaf, yn pwyntydd i'r Elfen gyntaf y rhestr cysylltiedig.
Mae hyn mewn gwirionedd yn rhywbeth wnewch chi helpu bob amser yn awyddus i gadw golwg ar,
ac mewn gwirionedd gallai fod yn rhywbeth y chi hyd yn oed rhoi mewn newidyn byd-eang.
Ar ôl i chi greu rhestr, chi bob amser, bob amser yn
am gadw golwg ar yr union Elfen gyntaf y rhestr.
Os gwnewch hyn gallwch gyfeirio at yr holl arall elfennau at jyst yn dilyn y gadwyn,
heb orfod cadw awgrymiadau yn gyfan i bob elfen unigol.
Dim ond angen i chi gadw golwg ar y cyntaf un os maen nhw i gyd gadwyn gyda'i gilydd.
>> Ac yna yr ail beth rydym yn pasio i mewn eto
yn fympwyol some-- pa bynnag ddata Math rydym yn
chwilio am ceir tu mewn gobeithio, yn un o'r nodau yn y rhestr.
Felly beth yw'r camau?
Wel, y peth cyntaf yr ydym yn ei wneud yw rydym yn creu pwyntydd ardrawslin
pwyntio at y pen rhestrau.
Wel, pam yr ydym yn gwneud hynny, yr ydym eisoes fod â pwyntydd yn y pen rhestrau,
pam nad ydym yn dim ond symud bod un o gwmpas?
Wel, fel yr wyf newydd ei ddweud, mae'n bwysig iawn i ni
i bob amser yn cadw golwg ar y Elfen gyntaf yn y rhestr.
Ac felly mae'n mewn gwirionedd yn well i greu dyblyg o hynny,
ac yn defnyddio hynny i symud o gwmpas, felly ni fyddwn byth ddamweiniol yn symud i ffwrdd, neu byddwn bob amser yn
cael pwyntydd ar ryw adeg sy'n i'r dde ar elfen gyntaf y rhestr.
Felly mae'n well i greu ail un yr ydym yn eu defnyddio i symud.
>> Yna, rydym yn unig yn cymharu a yw maes gwerth ar y nod
yw'r hyn rydym yn chwilio am, ac os yw'n nid, rydym yn unig yn symud at y nod nesaf.
Ac rydym yn cadw gwneud hynny drosodd, a thros, a throsodd,
nes i ni naill ai yn dod o hyd yr elfen, neu yr ydym taro
null-- rydym wedi cyrraedd diwedd o'r rhestr ac nid yw yno.
Dylai hyn, gobeithio, ffonio gloch i chi chwilio llinellol fel dim ond,
rydym yn unig ddyblygu mewn strwythur rhestr gysylltiedig yn unigol
yn hytrach na defnyddio amrywiaeth i wneud hynny.
>> Felly dyma enghraifft o rhestr cysylltiedig yn unigol.
Mae hyn yn un yn cynnwys pum nodau, ac mae gennym
pwyntydd i ben y rhestr, a elwir yn rhestr.
Y peth cyntaf yr ydym am ei wneud yw unwaith eto, yn creu y pwyntydd llwybro.
Felly, mae gennym bellach ddau awgrymiadau y pwynt hwnnw at yr un peth.
>> Yn awr, yn sylwi yma hefyd, doeddwn i ddim rhaid i malloc unrhyw le ar gyfer Trav.
Doeddwn i ddim yn dweud Trav hafal malloc rhywbeth, y nod yn bodoli eisoes,
bod lle yn y cof sydd eisoes yn bodoli.
Felly, i gyd fy mod yn gwneud yn union yw creu pwyntydd arall iddo.
Dydw i ddim yn mallocing ychwanegol gofod, dim ond yn awr dau awgrymiadau
gan dynnu sylw at yr un peth.
>> Felly, mae 2 beth rwy'n chwilio amdano?
Wel, na, felly yn lle rwy'n mynd i symud i'r un nesaf.
Felly y bôn byddwn yn dweud, Trav hafal Trav nesaf.
Yw 3 yr hyn dwi'n chwilio am, dim.
Felly, yr wyf yn parhau i fynd trwy, tan yn y pen draw
cyrraedd 6 sef yr hyn yr wyf i'n edrych am yn seiliedig ar y swyddogaeth alwad
Mae gen i ar y brig yno, ac felly rwy'n ei wneud.
>> Yn awr, beth os yr elfen dwi'n Nid yw chwilio amdano yn y rhestr,
a yw'n dal i fynd i'r gwaith?
Wel, yn sylwi fod y rhestr dyma ychydig yn wahanol,
ac mae hyn yn beth arall sy'n bwysig gyda rhestrau cysylltiedig,
Nid oes rhaid i chi gadw hwy mewn unrhyw drefn benodol.
Gallwch os ydych yn dymuno, ond Efallai eich bod eisoes wedi sylwi
nad ydym yn cadw golwg ar pa elfen rhif yr ydym ar.
>> A dyna fath o un masnach yr ydym wedi gyda rhestr gysylltiedig penillion araeau,
a yw'n nad oes gennym hapgyrch anymore.
Ni allwn ond dweud, yr wyf am i fynd i'r elfen 0fed,
neu elfen 6ed fy array, yr wyf yn gallu ei wneud mewn arae.
Ni allaf ddweud fy mod i eisiau mynd i'r Elfen 0fed, neu'r 6ed elfen,
neu elfen 25ain o fy rhestr cysylltiedig, does dim mynegai gysylltiedig â hwy.
Ac felly nid yw'n wir bwys os ydym yn cadw ein rhestr mewn trefn.
Os ydych am i chi yn sicr yn gallu, ond mae
unrhyw reswm pam y mae angen iddynt yn cael eu cadw mewn unrhyw drefn.
Felly unwaith eto, gadewch i ni geisio a dod o hyd i 6 yn y rhestr hon.
Wel, rydym yn dechrau ar y dechrau, nid ydym yn dod o hyd i 6,
ac yna nid ydym yn parhau dod o hyd i 6, tan i ni yn y pen draw gyrraedd fan hyn.
Pwyntiau bellach Trav mor gywir i y nôd nad ydynt yn cynnwys 8, a chwech yw mewn 'na.
>> Felly byddai'r cam nesaf fydd i fynd i'r pwyntydd nesaf,
felly yn dweud Trav hafal Trav nesaf.
Wel, Trav nesaf, a ddangosir gan y blwch coch yno, yn null.
Felly does unman arall i fynd, ac yn y blaen ar hyn o bryd
gallwn ddod i'r casgliad ein bod ni wedi cyrraedd diwedd y rhestr cysylltiedig,
ac nid oedd 6 yw mewn 'na.
A byddai'n cael ei ddychwelyd ffug yn yr achos hwn.
>> OK, sut ydyn ni'n mewnosod newydd nod i mewn i'r rhestr gysylltiedig?
Felly, rydym wedi llwyddo i greu rhestr cysylltiedig tu allan i unman,
ond mae'n debyg ein bod yn awyddus i adeiladu cadwyn ac nid
creu criw o restrau gwahanol.
Rydym yn awyddus i gael un rhestr sy'n Mae criw o nodau ynddo,
Nid yw criw o restrau gyda nod sengl.
Felly, ni allwn jyst cadw defnyddio'r Creu swyddogaeth yr ydym diffinnir yn gynharach, yn awr rydym
eisiau i fewnosod i mewn i rhestr sydd eisoes yn bodoli.
>> Felly yr achos hwn, rydym yn mynd i basio mewn dwy ddadl,
pwyntydd i bennaeth y Rhestr yr ydym am ychwanegu at cysylltiedig.
Unwaith eto, dyna pam ei bod mor bwysig ein bod yn bob amser
cadw golwg ar hynny, oherwydd dyma'r unig ffordd yr ydym mewn gwirionedd
rhaid i gyfeirio at y rhestr gyfan yn dim ond gan pwyntydd i'r elfen gyntaf.
Felly rydym am eu trosglwyddo mewn pwyntydd i'r elfen gyntaf,
a beth bynnag gwerth yr ydym eisiau ychwanegu at y rhestr.
Ac yn y diwedd swyddogaeth hon yn mynd i ddychwelyd pwyntydd
i'r pennaeth newydd o restr cysylltiedig.
>> Beth yw'r camau dan sylw yma?
Wel, yn union fel gyda chreu, mae angen i ni ddyrannu ddeinamig
lle ar gyfer nod newydd, a gwirio i wneud yn sicr nid ydym yn rhedeg allan o gof, unwaith eto,
oherwydd ein bod yn defnyddio malloc.
Yna, rydym am i boblogi a rhowch y nod,
felly rhowch y rhif, beth bynnag Val yw, i mewn i'r nod.
Rydym am i fewnosod y nôd ar cychwyn y rhestr cysylltiedig.
>> Mae 'na reswm yr wyf yn am wneud hyn, ac mae'n
allai fod yn werth cymryd eiliad i oedi y fideo yma,
ac yn ystyried pam fyddwn i eisiau mewnosoder ar y dechrau o cysylltiedig
rhestr.
Unwaith eto, soniais yn gynharach nad yw'n wir
ots os ydym yn ei gadw mewn unrhyw gorchymyn, felly efallai dyna cliw.
A welsoch yr hyn a fyddai'n digwydd os byddwn yn eisiau canlynol-- neu o ddim ond ail
yn ôl pan oeddem yn mynd trwy chwilio yr ydych
Gallai weld beth allai yn digwydd os oeddem yn ceisio
i fewnosod ar ddiwedd y rhestr.
Oherwydd nad oes gennym Pointer at ddiwedd y rhestr.
>> Felly y rheswm y byddwn am i mewnosoder ar y dechrau,
yw oherwydd fy mod yn gallu ei wneud ar unwaith.
Mae gen i pwyntydd ar y dechrau, ac byddwn yn gweld hyn mewn golwg mewn eiliad.
Ond os ydw i am mewnosoder ar y diwedd, Mae'n rhaid i mi ddechrau ar y dechrau,
croesi yr holl ffordd at y diwedd, ac yna tac ymlaen.
Felly byddai hynny'n golygu y mewnosod ar ddiwedd y rhestr
Byddai dod yn o o n gweithredu, yn mynd yn ôl
at ein trafodaeth ar cymhlethdod cyfrifiadurol.
Byddai'n dod yn o o n llawdriniaeth, lle fel y rhestr mynd yn fwy, ac yn fwy,
a mwy, bydd yn dod yn fwy a fwy anodd i'w tac rhywbeth
ar ar y diwedd.
Ond mae'n hawdd iawn i bob amser tac rhywbeth ar ar y dechrau,
eich bod bob amser ar y dechrau.
>> A byddwn yn gweld gweledol o hyn eto.
Ac yna ar ôl i ni yn ei wneud, unwaith rydym wedi mewnosod y nôd newydd,
rydym am ddychwelyd i'n pwyntydd i y pennaeth newydd o restr cysylltiedig, a oedd yn
ers i ni yn mewnosod yn y dechrau, bydd mewn gwirionedd yn
pwyntydd i'r nod yr ydym newydd ei greu.
Gadewch i ddychmygu hyn, gan fy mod yn meddwl y bydd yn helpu.
>> Felly dyma ein rhestr, mae'n cynnwys pedair elfen, mae cainc sy'n cynnwys 15,
sy'n pwyntio at nod sy'n cynnwys 9, a oedd yn
yn pwyntio at nod sy'n cynnwys 13, sy'n pwyntio at nod sy'n cynnwys
10, sydd â'r null pwyntydd fel ei pwyntydd nesaf
felly dyna ddiwedd y rhestr.
Felly rydym am i fewnosod nod newydd gyda gwerth 12
ar ddechrau'r hwn rhestr, beth ydym yn ei wneud?
Wel, yn gyntaf rydym yn malloc lle ar gyfer y nod, ac yna rydym yn rhoi 12 i mewn 'na.
>> Felly nawr rydym wedi cyrraedd pwynt penderfyniad, dde?
Mae gennym un neu ddau o awgrymiadau y gallem
symud, pa un dylem symud yn gyntaf?
Dylem wneud 12 pwynt i y pennaeth newydd y list--
neu esgus i mi, dylem wneud 12 tynnu sylw at yr hen bennaeth y rhestr?
Neu a ddylem ddweud bod y rhestr yn awr yn dechrau am 12.
Mae 'na gwahaniaeth yno, a byddwn yn edrych
ar yr hyn sy'n digwydd gyda'r ddau mewn eiliad.
>> Ond mae hyn yn arwain at bwnc gwych ar gyfer sidebar,
sef bod un o'r pethau dyrys gyda rhestrau cysylltiedig
yw i drefnu'r awgrymiadau yn y drefn gywir.
Os byddwch yn symud pethau allan o drefn, gallwch yn y pen draw yn ddamweiniol
orphaning gweddill y rhestr.
A dyma enghraifft o hynny.
Felly gadewch i ni fynd â'r syniad o- yn dda, rydym newydd ei greu 12.
Rydym yn gwybod 12 yn mynd i fod y pennaeth newydd y rhestr,
ac felly pam nad ydym yn unig yn symud y rhestr pwyntydd i bwynt yno.
>> Iawn, felly dyna dda.
Felly nawr lle mae 12 pwynt nesaf?
Yr wyf yn golygu, yn weledol gallwn weld y bydd yn pwyntio i 15,
fel bodau dynol mae'n wirioneddol amlwg i ni.
Sut mae'r cyfrifiadur yn ei wybod?
Nid oes gennym unrhyw beth pwyntio at 15 anymore, dde?
>> Rydyn ni wedi colli unrhyw allu i gyfeirio at 15.
Ni allwn ddweud saeth newydd hafal nesaf rhywbeth, does dim byd yno.
Yn wir, rydym wedi amddifad gweddill y rhestr
trwy wneud hynny, rydym wedi ddamweiniol torri y gadwyn.
Ac rydym yn sicr ddim eisiau gwneud hynny.
>> Felly gadewch i ni fynd yn ôl a rhowch gynnig ar hyn eto.
Efallai y peth iawn i'w wneud yw gosod 12 oed pwyntydd nesaf
i'r hen bennaeth y rhestr yn gyntaf, Yna, gallwn symud y rhestr drosodd.
Ac yn wir, dyna'r drefn gywir ein bod yn
angen eu dilyn pan fyddwn ni'n gan weithio gyda rhestr cysylltiedig yn unigol.
Rydym bob amser yn awyddus i gysylltu'r Elfen newydd i mewn i'r rhestr,
cyn i ni gymryd y math hwnnw o gam pwysig o newid
lle mae'r pennaeth y rhestr cysylltiedig yn.
Unwaith eto, mae hynny'n beth mor sylfaenol, nid ydym am golli golwg ar ei.
>> Felly, rydym am wneud yn siŵr bod popeth yn cael ei gadwyn gyda'i gilydd,
cyn i ni symud y pwyntydd.
Ac felly byddai hyn yn y drefn gywir, sef er mwyn cysylltu 12 at y rhestr,
Yna, yn dweud bod y rhestr yn dechrau 12.
Os byddwn dywedodd y rhestr yn dechrau am 12 a Yna ceisiodd cysylltu 12 at y rhestr,
rydym wedi gweld yn barod beth sy'n digwydd.
Rydym yn colli y rhestr drwy gamgymeriad.
>> Iawn, felly un peth arall i siarad am.
Beth os ydym am gael gwared ar yn gyfan rhestr gysylltiedig ar unwaith?
Unwaith eto, rydym yn mallocing i gyd y gofod hwn, ac felly rydym yn
Mae angen i ryddhau pan fyddwn yn ei wneud.
Felly nawr rydym am ddileu'r y rhestr cysylltiedig cyfan.
Wel, beth ydym ni eisiau ei wneud?
>> Os byddwn wedi cyrraedd y pwyntydd null, rydym yn am roi'r gorau i, fel arall, jyst ddilea
gweddill y rhestr ac yna rhyddhau i mi.
Dileu gweddill y rhestr, ac yna rhyddhau'r nod ar hyn o bryd.
Beth mae hynny'n swnio fel, pa dechneg wedi buom yn siarad
am y gorffennol mae hynny'n swnio fel?
Dileu pawb arall, yna dod yn ôl a dileu mi.
>> Dyna recursion, rydym wedi gwneud y problem ychydig yn llai,
rydyn ni'n ei ddweud dileu pawb arall, yna gallwch ddileu mi.
Ac ymhellach i lawr y ffordd, y nod Bydd dweud, dileu pawb arall.
Ond yn y pen draw byddwn yn mynd i'r pwynt lle mae'r rhestr yn null,
a dyna ein achos sylfaenol.
>> Felly, gadewch i ni edrych ar hyn, a sut y gallai hyn weithio.
Felly dyma ein rhestr, 'i' yr un fath Rhestrwch yr oeddem yn unig yn siarad am,
ac mae y grisiau.
Mae llawer o destun yma, ond Gobeithio y bydd y delweddu helpu.
>> Felly rydym have-- ac rwyf hefyd yn tynnu ein darluniad fframiau stac
oddi wrth ein fideo ar staciau galwadau, a gobeithio hyn oll
at ei gilydd, bydd yn dangos i chi beth sy'n digwydd.
Felly dyma ein cod pseudocode.
Os byddwn yn cyrraedd null pwyntydd, stopio, fel arall,
dileu gweddill y rhestr, Yna, rhad ac am ddim y nod ar hyn o bryd.
Felly ar hyn o bryd, list-- pwyntydd ein bod
pasio mewn i ddinistrio pwynt i 12.
12 Nid yw pwyntydd null, felly rydym yn mynd i ddileu gweddill y rhestr.
>> Beth yw dileu'r gweddill ohonom gymryd rhan?
Wel, mae'n golygu gwneud galw i ddinistrio, gan ddweud
bod 15 yn cychwyn y gweddill y rhestr yr ydym am ei ddinistrio.
Ac felly yr alwad i ddinistrio 12 yn fath o am y tro.
Mae wedi rhewi yno, yn aros am y galw i ddinistrio 15, i orffen ei waith.
>> Wel, nid yw 15 yn pwyntydd nwl, ac felly mae'n mynd i ddweud, yn iawn,
yn dda, dileu gweddill y rhestr.
Mae gweddill y rhestr yn dechrau yn 9, ac felly rydym annhymerus unig
aros nes i chi ddileu bob un sy'n stwff, ac yna dod yn ôl a dileu mi.
Wel 9 yn mynd i ddweud, wel, Dydw i ddim yn pwyntydd null,
felly dileu'r gweddill y rhestr o fan hyn.
Ac felly ceisiwch a dinistrio 13.
13 yn dweud, dydw i ddim pwyntydd null, un peth, mae'n mynd y bwch.
10 Nid yw pwyntydd null, 10 yn cynnwys pwyntydd nwl,
ond nid ei hun yn 10 yw null pwyntydd ar hyn o bryd,
ac felly mae'n pasio y bwch hefyd.
>> Ac yn awr rhestru pwyntiau yno, mae'n Byddai 'n sylweddol pwynt i some--
os wyf wedi mwy o le yn y llun, byddai'n tynnu sylw at ychydig o le ar hap
nad ydym yn gwybod beth ydyw.
Mae'n y pwyntydd null fodd bynnag, mae'r rhestr yn llythrennol osod nawr mae'n gwerthoedd null.
Mae'n pwyntio i'r dde y tu mewn i'r bocs coch.
Rydym yn cyrraedd pwyntydd null, felly gallwn atal, ac rydym yn ei wneud.
>> Ac felly bod ffrâm porffor yn now-- yn y ben stack-- dyna'r ffrâm weithredol,
ond mae'n ei wneud.
Os ydym wedi cyrraedd pwyntydd null, rhoi'r gorau.
Nid ydym yn gwneud unrhyw beth, rydym yn Ni all ryddhau pwyntydd nwl,
doedden ni ddim yn malloc unrhyw gofod, ac felly rydym yn ei wneud.
Er mwyn i ffrâm swyddogaeth yn cael ei ddinistrio, ac yr ydym yn
resume-- rydym yn codi lle rydym yn gadael i ffwrdd gyda'r un uchaf nesaf, sy'n
a yw hyn yn ffrâm glas tywyll yma.
Felly, rydym yn codi yn iawn lle'r ydym yn gadael i ffwrdd.
Rydym yn dileu gweddill y rhestr yn barod, felly erbyn hyn rydym yn
mynd i ryddhau y nodau cyfredol.
Felly, erbyn hyn gallwn ryddhau nod hwn, ac yn awr rydym wedi cyrraedd diwedd y swyddogaeth.
Ac felly bod ffrâm swyddogaeth yn cael ei ddinistrio, ac yr ydym yn casglu yn yr un glas golau.
>> Felly mae'n says-- Rwyf eisoes wedi done-- dileu gweddill y rhestr, felly
rhad ac am ddim y nôd ar hyn o bryd.
Ac yn awr y ffrâm melyn yn yn ôl ar ben y pentwr.
Ac felly fel y gwelwch, rydym yn awr yn dinistrio'r rhestr o'r dde i'r chwith.
>> Beth fyddai wedi digwydd, fodd bynnag, os ydym wedi gwneud pethau y ffordd anghywir?
Yn union fel pan fyddwn yn ceisio i ychwanegu elfen.
Os byddwn yn cyboledig i fyny y gadwyn, os doedden ni ddim yn cysylltu'r awgrymiadau
yn y drefn gywir, os ydym dim ond rhyddhau yr elfen gyntaf,
os ydym yn unig rhyddhau y pennaeth y rhestr, yn awr rydym
yn cael unrhyw ffordd i gyfeirio at gweddill y rhestr.
Ac felly byddem wedi popeth amddifad,
byddem wedi cael yr hyn sydd Gelwir yn gollwng cof.
Os cofiwch oddi wrth ein fideo ar ddyraniad cof deinamig,
nid yw hynny'n beth da iawn.
>> Felly, fel y dywedais, mae sawl weithrediadau
bod angen i ni ei ddefnyddio i weithio gyda rhestr chysylltu'n effeithiol.
Ac efallai eich bod wedi sylwi fy mod hepgor un, dileu un elfen o cysylltiedig
rhestr.
Y rheswm yr wyf yn gwneud hynny a yw'n mewn gwirionedd fath o
anodd i feddwl am sut i ddileu elfen unigol o unigol
rhestr gysylltiedig.
Mae angen i ni fod yn gallu sgip dros rhywbeth yn y rhestr, a oedd yn
yn golygu ein bod yn cael i ni'n point-- am ddileu node-- hwn
ond er mwyn ei gwneud yn felly rydym peidiwch â cholli unrhyw wybodaeth,
mae angen i ni gysylltu hyn nod dros yma, yma.
>> Felly yr wyf yn ôl pob tebyg yn gwneud hynny yn anghywir o safbwynt gweledol.
Felly, rydym yn ar ddechrau ein rhestr, rydym yn bwrw ymlaen drwy,
rydym eisiau dileu nod hwn.
Os ydym yn unig ddileu, rydym wedi torri'r gadwyn.
Mae'r nôd yma yn cyfeirio at bopeth arall,
ei fod yn cynnwys y gadwyn o hyn ymlaen y tu allan.
>> Felly beth sydd angen i wneud mewn gwirionedd ar ôl i ni gyrraedd y pwynt,
yn rhaid i ni gymryd cam yn ôl un, a cysylltu nod hwn drosodd i nod hwn,
fel y gallwn ni wedyn ddileu yr un yn y canol.
Ond nid yw rhestrau cysylltiedig yn unigol yn ei wneud rhoi ffordd i fynd yn ôl.
Felly mae angen i naill ai cadw dau awgrymiadau, a'u symud
math o oddi ar gam, un y tu ôl i'r eraill wrth i ni fynd, neu gael hyd at bwynt
ac wedyn anfon pwyntydd arall drwodd.
Ac fel y gwelwch, mae'n yn gallu cael ychydig o anniben.
Yn ffodus, mae gennym ffordd arall i ddatrys hynny,
pan fyddwn yn sôn am restrau cysylltiedig ddwbl.
>> Rwy'n Doug Lloyd, mae hyn yn CS50.