[Powered by Google Translate] In programmering, moet ons dikwels lyste van waardes te verteenwoordig,
soos die name van studente in 'n artikel
of hul tellings op die jongste quiz.
>> In die C-taal, verklaar skikkings kan gebruik word
lyste te stoor.
Dit is maklik om die elemente van 'n lys op te noem wat in ons omstreken
in 'n skikking gestoor, en as jy nodig het om toegang te verkry tot
of verander die ith lys element
vir 'n paar arbitrêre indeks Ek,
wat gedoen kan word in konstante tyd,
maar skikkings nadele ook.
>> Wanneer ons hulle verklaar, is ons verplig om te sê
aan die voorkant hoe groot hulle is,
dit is, hoeveel elemente hulle kan stoor
en hoe groot hierdie elemente is, wat bepaal word deur hul soort.
Byvoorbeeld, int arr (10)
10 items kan stoor
wat is die grootte van 'n int.
>> Ons kan nie 'n skikking se grootte verander na die verklaring.
Ons het 'n nuwe skikking te maak as ons wil meer elemente te stoor.
Die rede waarom hierdie beperking bestaan, is dat ons
program slaan die hele reeks
as 'n aangrensende stuk van die geheue.
Sê dit is die buffer waar ons in ons skikking gestoor.
Daar is dalk ander veranderlikes
geleë reg langs die skikking
in die geheue, so ons kan nie
maak net die skikking groter.
>> Soms het ons wil die skikking se vinnige data toegang spoed om handel te dryf
vir 'n bietjie meer buigsaamheid.
Gee die geskakelde lys, 'n ander basiese data struktuur
jy dalk nie so vertroud met.
Op 'n hoë vlak,
'n geskakelde lys stoor data in 'n reeks van nodes
wat met mekaar verbind is met skakels,
vandaar die naam "geskakelde lys."
Soos ons sal sien, is hierdie verskil in die ontwerp
lei tot verskillende voordele en nadele
as 'n skikking.
>> Hier is 'n paar C-kode vir 'n baie eenvoudige geskakelde lys van heelgetalle.
Jy kan sien dat ons elke node verteenwoordig
in die lys as 'n struct wat bevat 2 dinge,
'n heelgetal te slaan genaamd "val"
en 'n skakel na die volgende nodus in die lys
wat ons verteenwoordig, as 'n wyser 'langs. "
Hierdie manier kan ons hou die hele lys
met net 'n enkele wyser aan die 1ste node,
en dan kan ons die volgende wenke volg
na die 2de node,
na die 3de node,
na die 4de node,
en so aan, totdat ons aan die einde van die lys.
>> Jy mag dalk in staat wees om 1 voordeel dit het om te sien
oor die statiese verskeidenheid struktuur - met 'n geskakelde lys,
ons hoef nie 'n groot stuk van die geheue heeltemal.
Die 1ste node van die lys kan lewe op hierdie plek in die geheue,
en die 2de node kon al die pad hier.
Ons kan kry om al die nodusse maak nie saak waar hulle is in die geheue,
omdat begin op die 1ste node, elke node se volgende wyser
vertel ons presies waar om volgende te gaan.
>> Daarbenewens, het ons nie om te sê aan die voorkant
hoe groot 'n geskakelde lys sal die manier waarop ons met statiese skikkings,
want ons kan hou nodes op 'n lys voeg
so lank as wat daar is ruimte iewers in die geheue vir 'n nuwe nodes.
Daarom, geskakelde lyste is maklik om dinamiese grootte.
Sê, later in die program wat ons moet meer nodes te voeg
in ons lys.
'N nuwe node in ons lys in te voeg op die vlieg,
al wat ons hoef te doen, is geheue toeken vir daardie node,
plons in die data waarde,
en plaas dit dan waar ons wil deur die aanpassing van die toepaslike verwysings.
>> Byvoorbeeld, as ons wou 'n node te plaas tussen
die 2de en 3de nodes van die lys,
ons wil nie hê die 2de of 3de nodes te skuif.
Sê dat ons is die invoeging van die rooi node.
Al wat ons wil hê om dit te doen is die nuwe node se volgende wyser
om te wys op die 3de node
en dan ReWire die 2de node se volgende wyser
om te verwys na ons nuwe node.
Dus, kan ons die grootte van ons lyste op die vlieg
sedert ons rekenaar nie staatmaak op indeksering,
maar eerder op 'n skakel met wenke om hulle te slaan.
>> Egter 'n nadeel van geskakelde lyste
is dat, in teenstelling met 'n statiese skikking,
die rekenaar kan nie net spring na die middel van die lys.
Sedert die rekenaar het elke node te besoek in die geskakelde lys
te kry na die volgende een,
dit gaan langer neem om 'n spesifieke node te vind
as wat dit sou in 'n skikking.
Die hele lys te verken neem tyd eweredig
die lengte van die lys,
of O (n) in asimptotiese notasie.
Op die gemiddelde, die bereik van enige node
ook neem tyd eweredig aan n.
>> Nou, laat ons eintlik skryf 'n paar kode
wat werk met geskakelde lyste.
Kom ons sê ons wil 'n geskakelde lys van heelgetalle.
Ons kan 'n node verteenwoordig weer in ons lys
as 'n struct met 2 velde,
'n heelgetal waarde genoem "val"
en 'n volgende wyser na die volgende node van die lys.
Wel, lyk eenvoudig genoeg.
>> Kom ons sê ons wil 'n funksie te skryf
wat deurkruis die lys en druk die
waarde gestoor in die laaste node van die lys.
Wel, dit beteken dat ons sal moet al die nodusse in die lys te verken
die laaste een te vind, maar omdat ons nie toe te voeg
of verwyder enigiets, doen ons nie wil verander
die interne struktuur van die volgende wenke in die lys.
>> So, sal ons 'n wyser spesifiek nodig het vir traversal
wat ons noem "kruiper.
Dit sal deur al die elemente van die lys kruip
deur die ketting van die volgende wenke.
Al wat ons het gestoor is 'n wyser na die 1ste node,
of "kop" van die lys.
Hoof punte na die 1ste node.
Dit is van die tipe pointer-tot-node.
>> Die werklike 1ste node in die lys te kry,
ons moet dereference hierdie pointer,
maar voordat ons dit kan dereference, ons nodig het om te kyk
indien die wyser is null eerste.
As dit is null, die lys is leeg,
en ons moet die druk van 'n boodskap dat, omdat die lys is leeg,
Daar is geen verlede node.
Maar, laat ons sê dat die lys nie is leeg.
As dit is nie, dan moet ons kruip deur die hele lys
totdat ons kry om te die laaste knoop van die lys,
en hoe kan ons sê as ons kyk na die laaste nodus in die lys?
>> Wel, as 'n node se volgende wyser is van nul,
ons weet ons is aan die einde
sedert die laaste volgende wyser sou geen volgende nodus in die lys te wys.
Dit is goeie praktyk om altyd die laaste node se volgende wyser geïnisialiseer aan nul
'n gestandaardiseerde eiendom wat waarskuwings wanneer ons die einde van die lys bereik het.
>> So, as kruiper → volgende is null,
onthou dat die pyltjie sintaksis is 'n kortpad vir ontwysing
'n wyser na 'n struct, dan toegang tot
sy volgende veld gelykstaande aan die ongemaklike:
(* Kruiper). Volgende.
Sodra ons het gevind die laaste knoop,
ons wil kruiper → val te druk,
die waarde in die huidige node
wat ons weet is die laaste een.
Andersins, as ons nog nie by die laaste nodus in die lys,
ons het om aan te beweeg na die volgende nodus in die lys
en kyk of dit is die laaste een.
Om dit te doen, het ons net ons kruiper pointer
om te verwys na die huidige node se waarde,
dit is die volgende nodus in die lys.
Dit word gedoen deur die oprigting
kruiper = kruiper → volgende.
Dan sal ons hierdie proses herhaal, met 'n lus byvoorbeeld,
totdat ons vind die laaste knoop.
So, byvoorbeeld, indien kruiper wys aan kop,
ons kruiper te wys aan kruiper → volgende,
wat dieselfde is as die volgende gebied van die 1ste node.
So, nou is ons kruiper verwys na die 2de node,
en weer, ons herhaal dit met 'n lus,
totdat ons die laaste knoop gevind het, dit is,
waar die node se volgende wyser wys aan nul.
En daar het ons dit,
het ons gevind die laaste nodus in die lys, en die waarde daarvan te druk,
gebruik ons ​​net kruiper → val.
>> Dwarsbalke is nie so sleg nie, maar wat oor die invoeging van?
Kom ons sê ons wil 'n heelgetal in die 4de posisie in te voeg
in 'n heelgetal lys.
Dit is tussen die huidige 3de en 4de nodes.
Weereens, ons het die lys om net te verken
kry die 3de element, die een wat ons invoeging na.
Dus, het ons weer 'n kruiper wyser om die lys te verken,
seker as ons kop null,
en as dit nie, wys ons kruiper wyser op die kop node.
So, ons is op die 1ste element.
Ons het 2 meer elemente om te gaan vorentoe voordat ons kan plaas,
sodat ons dit kan gebruik om 'n for-lus
int i = 1; i <3; i + +
en in elke iterasie van die lus,
bevorder ons kruiper wyser deur 1 node
deur te kyk as die huidige node se volgende veld, is van nul,
en as dit nie, ons kruiper wyser beweeg na die volgende node
deur dit gelyk is aan die huidige node se volgende wyser.
So, aangesien ons vir lus sê om dit te doen
twee keer,
het ons bereik die 3de node,
en sodra ons kruiper wyser het die knoop bereik nadat
wat ons wil ons nuwe heelgetal te voeg,
hoe ons eintlik nie die invoeging?
>> Wel, ons nuwe heelgetal word ingevoeg in die lys
as deel van sy eie node struct,
want dit is regtig 'n reeks van nodes.
So, kom ons maak 'n nuwe wyser node
genoem "new_node,
en sit dit om te verwys na geheue wat ons nou ken
op die hoop vir die knoop self,
en hoeveel geheue moet ons ken?
Wel, die grootte van 'n node,
en ons wil sy val veld te stel aan die heelgetal wat ons wil voeg.
Kom ons sê, 6.
Nou, die node bevat ons heelgetalwaarde.
Dit is ook 'n goeie praktyk om die nuwe node se volgende veld te inisialiseer
om te wys aan nul,
maar wat nou?
>> Ons het die interne struktuur van die lys te verander
en die volgende verwysings in die lys se bestaande
3de en 4de nodes.
Sedert die volgende wenke bepaal die volgorde van die lys,
en omdat ons die invoeging van ons nuwe node
reg in die middel van die lys,
dit kan 'n bietjie lastig.
Dit is omdat, onthou, ons rekenaar
weet net die plek van die nodusse in die lys
as gevolg van die volgende wenke gestoor in die vorige nodes.
Dus, as ons ooit verlore spoor van enige van hierdie plekke,
sê deur die verandering van een van die volgende wenke in ons lys,
byvoorbeeld, sê ons verander
die 3de node se volgende veld
om te verwys na 'n node hier.
Ons sal uit van geluk, want ons wil nie
'n idee waar die res van die lys te vind,
en dit is natuurlik regtig sleg is.
So, ons moet baie versigtig oor die volgorde
wat ons manipuleer ons volgende wenke tydens die invoeging.
>> So, om dit te vereenvoudig, laat ons sê dat
ons eerste 4 nodes
A, B, C, en D is geroep, met die pyle wat die ketting van verwysings
wat die nodusse verbind.
So, moet ons ons nuwe node te voeg
tussen nodes C en D.
Dit is van kritieke belang om dit te doen in die korrekte volgorde, en ek sal jou wys hoekom.
>> Kom ons kyk op die verkeerde manier om dit eers te doen.
Hey, ons weet dat die nuwe node het om reg te kom na C,
so laat ons stel C se volgende wyser
om te wys te new_node.
Alle reg, lyk okay, ons het net eenvoudig te voltooi nou deur
die maak van die nuwe node se volgende wyser punt D
Maar wag, hoe kan ons dit doen?
Die enigste ding wat ons kan vertel waar D was,
is die volgende wyser voorheen gestoor in C,
maar ons het net oorgeskryf dat wyser
om te verwys na die nuwe node,
sodat ons nie meer 'n clue waar D is in die geheue,
en ons het die res van die lys verloor.
Glad nie goed nie.
>> So, hoe doen ons dit reg?
Eerstens, wys die nuwe node se volgende wyser by D.
Nou, beide die nuwe node's en C's volgende verwysings
wys na dieselfde node, D,
maar dit is goed.
Nou kan ons wys C se volgende wyser op die nuwe node.
So, ons het dit gedoen sonder om enige data te verloor.
In die kode, C is die huidige node
dat die traversal pointer kruiper wys,
en D word verteenwoordig deur die node uitgewys deur die huidige node se volgende veld,
of rusperbande → volgende.
So, moet ons eers die nuwe node se volgende wyser
te wys aan kruiper → volgende,
op dieselfde manier het ons gesê new_node se volgende wyser
verwys na D in die illustrasie.
Dan kan ons stel die huidige node se volgende wyser
na ons nuwe node,
net soos ons het om te wag tot punt C new_node in die tekening.
Nou is alles in orde, en ons het nie verloor nie
hou van enige data, en ons was in staat om net
hou ons nuwe node in die middel van die lys
sonder om die hele ding te herbou of selfs verskuiwing enige elemente
die manier waarop ons sou gehad het om met 'n vaste-lengte skikking.
>> So, geskakelde lyste is 'n basiese, maar belangrike, dinamiese data struktuur
wat beide voordele en nadele
in vergelyking met skikkings en ander data strukture,
en so dikwels die geval in die rekenaar wetenskap,
Dit is belangrik om te weet wanneer om elke instrument te gebruik,
sodat jy kan kies die regte gereedskap vir die regte werk.
>> Vir meer oefening, probeer skryf funksies te
verwyder nodes van 'n geskakelde lys -
onthou om versigtig te wees oor die volgorde waarin jy herrangskik
jou volgende wenke om seker te maak dat jy nie 'n stuk van jou lys verloor -
of 'n funksie om die nodusse in 'n geskakelde lys te tel,
of 'n prettige, die einde van al die nodusse in 'n geskakelde lys om te keer.
>> My naam is Jackson STEINKAMP, dit is CS50.