[Powered by Google Translate] Bij het programmeren, we moeten vaak lijsten van waarden vertegenwoordigen,
zoals de namen van de studenten in een sectie
of hun scores op de laatste quiz.
>> In de taal C, verklaarde arrays kunnen worden gebruikt
lijsten te slaan.
Het is gemakkelijk om op te noemen de elementen van een lijst
opgeslagen in een array, en als je nodig hebt om toegang te krijgen
of wijzigen de i-de element in de lijst
enkele willekeurige index I,
gedaan kan worden in constante tijd,
maar arrays nadelen ook.
>> Toen we ze verklaren, zijn we verplicht om te zeggen
van te voren hoe groot ze zijn,
dat wil zeggen, hoeveel elementen ze slaan kunnen
en hoe groot deze elementen, die wordt bepaald door hun type.
Zo int arr (10)
kan 10 items
die de grootte van een int.
>> We kunnen een array grootte niet veranderen na aangifte.
We moeten een nieuwe array maken als we willen meer elementen op te slaan.
De reden bestaat deze beperking is dat onze
programma slaat de hele reeks
als een aaneengesloten stuk geheugen.
Zeggen dat dit de buffer waar we opgeslagen in ons aanbod.
Er kunnen andere variabelen
direct naast de array gelegen
in het geheugen, dus we kunnen niet
gewoon de array groter.
>> Soms willen we de array snelle toegang tot de gegevens snelheid handel
voor een beetje meer flexibiliteit.
Voer de gelinkte lijst, een andere fundamentele data structuur
u misschien niet zo vertrouwd zijn met.
Op een hoog niveau,
een gekoppelde lijst opgeslagen gegevens in een reeks knooppunten
die met elkaar verbonden met links,
vandaar de naam 'gelinkte lijst.'
Zoals we zullen zien, dit verschil in ontwerp
leidt tot verschillende voordelen en nadelen
dan een array.
>> Hier zijn een paar C-code voor een zeer eenvoudige gelinkte lijst van gehele getallen.
U kunt zien dat we elk knooppunt vertegenwoordigd
in de lijst als een struct die 2 dingen bevat,
een geheel getal op te slaan genaamd 'val'
en een link naar het volgende knooppunt in de lijst
die wij vertegenwoordigen als een pointer genaamd 'volgende'.
Op deze manier kunnen we volgen de hele lijst
met slechts een enkele verwijzing naar de 1e knooppunt,
en dan kunnen we volgen de volgende verwijzingen
de 2e knooppunt,
de 3e knooppunt,
de 4e knooppunt,
en zo verder, totdat we aan het einde van de lijst.
>> Je zou in staat zijn om een ​​voordeel heeft dit te zien
over de statische array structuur - met een gekoppelde lijst,
we niet helemaal behoefte aan een groot deel van het geheugen.
De 1e knooppunt van de lijst zou kunnen leven op deze plaats in het geheugen,
en de 2e knooppunt kan helemaal over hier te zijn.
We kunnen krijgen om alle knooppunten ongeacht waar in het geheugen ze zijn,
want vanaf de 1e node, elke node's volgende pointer
vertelt ons precies waar naar de volgende te gaan.
>> Bovendien hoeven we niet te zeggen van te voren
hoe groot een gekoppelde lijst zal de manier waarop we dat doen met statische arrays zijn,
want we kunnen blijven toevoegen knooppunten om een ​​lijst
zolang er ergens geheugenruimte voor nieuwe knooppunten.
Daarom gelinkte lijsten zijn makkelijk te dynamisch wijzigen.
Zeg, later in het programma moeten we meer knooppunten toe te voegen
aan onze lijst.
Om een ​​nieuw knooppunt te voegen aan onze lijst op de vlieg,
alles wat we hoeven te doen is geheugen toewijzen voor dat knooppunt,
plop in de gegevens waarde,
en plaats het waar we willen door het aanpassen van de betreffende aanwijzingen.
>> Bijvoorbeeld, als we een plaats tussen knooppunt
de 2e en 3e knooppunten van de lijst,
zouden we niet naar de 2e of 3e nodes bewegen.
Zeggen dat we deze rode knooppunt invoegen.
Alles wat we zouden moeten doen is de nieuwe node volgende pointer
om te wijzen op de 3e knooppunt
en dan opnieuw bedraden de 2e knooppunt volgende pointer
wijzen op nieuwe node.
Dus kunnen we de grootte van onze lijsten op de vlieg
omdat onze computer is niet afhankelijk van indexering,
maar eerder over het koppelen met behulp van pointers op te slaan.
>> Een nadeel van gekoppelde lijsten
is dat anders dan een statische array,
de computer kan niet alleen naar het midden van de lijst.
Omdat de computer moet elk knooppunt bezoeken in de gekoppelde lijst
om naar het volgende,
het gaat om langer duren om een ​​bepaald knooppunt vinden
dan zou in een array.
Om doorkruisen de hele lijst kost tijd evenredig
de lengte van de lijst,
of O (n) in asymptotische notatie.
Gemiddeld bereikt een knooppunt
ook tijd kost evenredig met n.
>> Laten we nu eigenlijk wat code schrijven
die werkt met gelinkte lijsten.
Laten we zeggen dat we willen een gelinkte lijst van gehele getallen.
We kunnen een knooppunt weer te vertegenwoordigen in onze lijst
als struct met twee velden,
een geheel getal genaamd 'val'
en een volgende pointer naar het volgende knooppunt van de lijst.
Nou, lijkt simpel genoeg.
>> Laten we zeggen dat we willen een functie te schrijven
die doorkruist de lijst en drukt de
waarde in het laatste knooppunt van de lijst.
Nou, dat betekent dat we moeten alle knooppunten in de lijst doorlopen
om de laatste een te vinden, maar omdat we niet toe te voegen
of iets te verwijderen, willen we niet veranderen
de interne structuur van de volgende verwijzingen in de lijst.
>> Dus zullen we specifiek behoefte aan een pointer voor traversal
die we zullen noemen 'crawler'.
Het zal kruipen door alle elementen van de lijst
door de keten van volgende verwijzingen.
Alles wat we hebben opgeslagen is een pointer naar de 1e knooppunt,
of 'hoofd' van de lijst.
Hoofd wijst op de 1e node.
Het is van het type pointer-naar-knooppunt.
>> Om de werkelijke 1e knooppunt in de lijst te krijgen,
we dereference deze verwijzing,
maar voordat we kunnen dereference, we moeten controleren
als de wijzer is null eerste.
Als het nul, is de lijst leeg is,
en we moeten printen een bericht dat, omdat de lijst leeg is,
er is geen laatste knooppunt.
Maar, laten we zeggen dat de lijst niet leeg is.
Als het niet, dan moeten we kruipen door de hele lijst
tot we bij de laatste knoop van de lijst,
en hoe kunnen we zien of we kijken naar het laatste knooppunt in de lijst?
>> Nou, als een knooppunt volgende pointer null,
we weten dat we aan het eind
sinds de laatste volgende pointer zou er geen volgende knooppunt in de lijst aan te wijzen.
Het is een goede gewoonte om altijd het laatste knooppunt volgende pointer geïnitialiseerd op nul
een gestandaardiseerde woning die ons waarschuwt als we aan het eind van de lijst te hebben.
>> Dus, als crawler → volgende is null,
vergeet niet dat de pijl syntax is een snelkoppeling voor dereferentie
een pointer naar een struct, dan de toegang tot
haar volgende veld gelijk aan het lastige:
(* Crawler). Volgende.
Zodra we hebben gevonden de laatste knoop,
we willen crawler → val af te drukken,
de waarde in het huidige knooppunt
waarvan we weten dat de laatste.
Anders, als we nog niet op het laatste knooppunt in de lijst,
we hebben om verder te gaan naar het volgende knooppunt in de lijst
en controleer of dat is de laatste.
Om dit te doen, we zetten onze crawler wijzer
wijzen op het huidige knooppunt volgende waarde,
dat wil zeggen het volgende knooppunt in de lijst.
Dit gebeurt door
crawler = crawler → volgende.
Dan herhalen we dit proces, met een lus bijvoorbeeld,
totdat we de laatste knoop.
Dus bijvoorbeeld als crawler wees het hoofd,
we crawler te wijzen op crawler → volgende,
die gelijk is aan het volgende veld van het eerste knooppunt.
Zo, nu onze crawler wijst naar de 2e knooppunt,
en, opnieuw, herhalen we dit met een lus,
totdat we de laatste knoop gevonden, dat wil zeggen,
waar de node volgende pointer wijst op null.
En daar hebben we het,
we hebben gevonden de laatste knooppunt in de lijst, en om de waarde af te drukken,
gebruiken we gewoon crawler → val.
>> Traverseren is niet zo erg, maar hoe zit het met het invoegen van?
Laten we zeggen dat we willen een geheel getal in te voegen in de 4e positie
in een geheel getal lijst.
Dat tussen de huidige 3e en 4e nodes.
Nogmaals, we de lijst doorlopen gewoon
naar de 3e element, degene die we het invoegen na.
Dus hebben we opnieuw een crawler pointer naar de lijst doorkruisen,
controleren of ons hoofd aanwijzer null,
en als het niet zo is, wijzen onze crawler pointer aan het hoofd node.
Dus, we zijn in het 1e element.
We moeten gaan voor 2 meer elementen voordat we kunnen invoegen,
dus we kunnen gebruik maken van een for-lus
int i = 1; i <3; i + +
en elke iteratie van de lus,
vooruit vooruit onze crawler pointer met 1 knoop
controleren of het huidige knooppunt volgende veld nul is,
en als het dat niet is, bewegen onze crawler aanwijzer naar het volgende knooppunt
door het gelijk aan naast de huidige knooppunt aanwijzer.
Dus, omdat onze lus zegt om dat te doen
tweemaal
we hebben bereikt de 3e knooppunt,
en zodra onze crawler pointer heeft bereikt het knooppunt na
die we willen onze nieuwe integer te voegen,
hoe kunnen we eigenlijk de plaatsen?
>> Nou, onze nieuwe integer moet worden ingevoegd in de lijst
als onderdeel van haar eigen knooppunt struct,
aangezien dit echt een reeks knooppunten.
Dus, laten we een nieuwe pointer te leveren aan knooppunt
genaamd 'new_node,'
en zet deze om te wijzen op het geheugen dat we nu kennen
op de hoop voor de knoop zelf,
en hoeveel geheugen hebben we nodig om toe te wijzen?
En de grootte van een knooppunt,
en we willen haar val veld is ingesteld op het gehele getal dat we willen invoegen.
Laten we zeggen, 6.
Nu, het knooppunt omvat ons geheel getal.
Het is ook een goede gewoonte om te initialiseren van de nieuwe node volgende veld
te wijzen op null,
maar wat nu?
>> We moeten de interne structuur van de lijst te wijzigen
en de volgende verwijzingen in de bestaande van de lijst
3e en 4e nodes.
Omdat de volgende verwijzingen bepalen de volgorde van de lijst,
en aangezien we het plaatsen van onze nieuwe knooppunt
recht in het midden van de lijst,
het kan een beetje lastig.
Dit is te onthouden, omdat,, onze computer
alleen weet waar knooppunten in de lijst
door de volgende verwijzingen opgeslagen in de vorige nodes.
Dus, als we ooit verloren spoor van een van deze locaties,
zeggen door het veranderen van een van de volgende verwijzingen in onze lijst,
bijvoorbeeld zeggen dat we veranderd
de 3e knooppunt volgende veld
om te wijzen op een aantal knooppunten hier.
We zouden pech, want we zouden niet
enig idee waar de rest van de lijst te vinden,
en dat is natuurlijk heel slecht.
Dus, we moeten echt voorzichtig zijn over de volgorde
waarin we manipuleren onze volgende aanwijzingen tijdens het inbrengen.
>> Dus, om dit te vereenvoudigen, laten we zeggen dat
onze eerste 4 knopen
genoemd A, B, C en D, met de pijlen die de keten van pointers
de knooppunten verbinden.
Dus, moeten we onze nieuwe knooppunt plaatst
tussen knooppunten C en D.
Het is essentieel om het te doen in de juiste volgorde, en ik zal je laten zien waarom.
>> Laten we eens kijken naar de verkeerde weg naar de eerste te doen.
Hey, we weten dat de nieuwe node heeft het recht te komen na C,
dus laten we stellen volgende pointer C's
te wijzen op new_node.
Oke, oke lijkt, we moeten nu af te maken door
het maken van de nieuwe node volgende pointer wijzen naar D,
maar wacht, hoe kunnen we dat doen?
Het enige dat ons kan vertellen waar D was,
werd de volgende pointer eerder opgeslagen in C,
maar we herschreven dat wijzer
verwijzen naar de nieuwe knooppunt
dus we hebben niet langer enig idee waar D is in het geheugen,
en we hebben verloren de rest van de lijst.
Helemaal niet goed.
>> Dus, hoe doen we dit recht?
Ten eerste, richt de nieuwe node volgende pointer bij D.
Nu zowel het nieuwe knooppunt C en de volgende verwijzingen
verwijzen naar dezelfde knooppunt D,
maar dat is prima.
Nu kunnen we wijzen volgende pointer C's op de nieuwe node.
Dus hebben we dit gedaan zonder gegevens te verliezen.
In code, C is het huidige knooppunt
dat de traversal wijzer crawler wordt verwezen,
en D wordt vertegenwoordigd door het knooppunt naar wijst naast het huidige knooppunt veld,
of rupsbanden → volgende.
Dus, we eerst de nieuwe node volgende pointer
om te wijzen op crawler → volgende,
op dezelfde manier waarop we zeiden volgende pointer new_node's moeten
wijzen op D in de afbeelding.
Dan kunnen we het huidige knooppunt van de volgende pointer
op onze nieuwe knooppunt,
net zoals we moesten wachten om C wijzen op new_node in de tekening.
Nu alles is in orde, en we hebben niet verliezen
bijhouden van alle gegevens, en we waren in staat om gewoon
blijven nieuwe knoop in het midden van de lijst
zonder de wederopbouw van de hele zaak, of zelfs verschuiven alle elementen
de manier waarop we zouden hebben gehad om met een vaste lengte array.
>> Dus, gelinkte lijsten zijn een eenvoudige, maar belangrijke, dynamische datastructuur
die zowel voor-en nadelen
vergelijking met arrays en andere datastructuren,
en zoals vaak het geval is in de informatica,
is het belangrijk om te weten wanneer elk instrument te gebruiken,
zodat u kunt kiezen het juiste gereedschap voor de juiste baan.
>> Voor meer oefening, proberen het schrijven van functies
knooppunten verwijderen uit een gekoppelde lijst -
vergeet niet om voorzichtig te zijn over de volgorde waarin u herschikken
uw volgende aanwijzingen om ervoor te zorgen dat je niet een stuk van uw lijst te verliezen -
of een functie aan de knooppunten tellen in een verbonden lijst,
of een leuke een, de volgorde van alle knooppunten in een gekoppelde lijst keren.
>> Mijn naam is Jackson Steinkamp, ​​dit is CS50.