[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.