[Powered by Google Translate] I programmering, vi ofte nødt til at repræsentere lister over værdier,
såsom navne på studerende i et afsnit
eller deres scoringer på det seneste quiz.
>> I C-sprog, erklæres arrays kan anvendes
at lagre lister.
Det er nemt at opregne de elementer i en liste
gemt i et array, og hvis du har brug for at få adgang
eller ændre den i'te listeelement
for en vilkårlig indeks I,
der kan gøres i konstant tid,
men arrays har ulemper, også.
>> Når vi erklære dem, er vi forpligtet til at sige
op foran hvor store de er,
det vil sige, hvor mange elementer, de kan gemme
og hvor store disse elementer, som bestemmes af deres type.
For eksempel, int arr (10)
kan gemme 10 varer
der er på størrelse med en int.
>> Vi kan ikke ændre et array størrelse efter erklæring.
Vi er nødt til at lave et nyt array, hvis vi ønsker at gemme flere elementer.
Grunden denne begrænsning eksisterer, er, at vores
programmet lagrer hele arrayet
som en sammenhængende luns af hukommelsen.
Sige dette er den buffer, hvor vi gemt i vores array.
Der kan være andre variabler
beliggende lige ud til arrayet
i hukommelsen, så vi kan ikke
bare gøre array større.
>> Nogle gange er vi gerne vil handle arrayet hurtige dataadgang hastighed
for lidt mere fleksibilitet.
Indtast den linkede liste, en anden grundlæggende datastruktur
du måske ikke være så fortrolige med.
På et højt niveau,
en sammenkædet liste lagrer data i en sekvens af knudepunkter
som er forbundet til hinanden med links,
deraf navnet 'linkede liste.'
Som vi vil se, denne forskel i design
fører til forskellige fordele og ulemper
end et array.
>> Her er nogle C-kode for en meget simpel hægtet liste af heltal.
Du kan se, at vi har repræsenteret hver node
på listen som en struct, der indeholder 2 ting,
et heltal til at gemme kaldes 'val'
og et link til den næste node i listen
som vi repræsenterer som en pegepind kaldes 'næste'.
På denne måde kan vi spore hele listen
med blot et enkelt pointer til 1. node,
og så kan vi følge de næste pointers
til 2. node,
til 3. node,
til 4. node,
og så videre, indtil vi kommer til slutningen af ​​listen.
>> Du vil måske være i stand til at se 1 fordel dette har
over den statiske array-struktur - med en linket liste,
vi har ikke brug for en stor luns af hukommelse helt.
Den 1. node af listen kunne leve på dette sted i hukommelsen,
og 2. knude kunne være helt herovre.
Vi kan komme til alle de noder, uanset hvor i hukommelsen de er,
fordi starter ved 1. knudepunkt, hver node næste pointer
fortæller os præcis, hvor de skal gå næste.
>> Derudover har vi ikke til at sige op foran
hvor stor en sammenkædet liste vil være den måde, vi gør med statiske arrays,
da vi kan holde tilføje noder til en liste
så længe der er plads et eller andet sted i hukommelsen for nye noder.
Derfor hægtede lister er nemme at ændre størrelsen dynamisk.
Sig, senere i det program, vi har brug for at tilføje flere noder
ind i vores liste.
Hvis du vil indsætte en ny node i vores liste på flue,
alt, hvad vi skal gøre, er tildele hukommelse til denne knude,
plumpet i dataværdi,
og derefter placere den hvor vi ønsker ved at justere de passende pointers.
>> For eksempel, hvis vi ønskede at anbringe en knude i mellem
2. og 3. knudepunkter i listen,
ville vi ikke nødt til at flytte den 2. eller 3. noder på alle.
Sig vi indsætte denne røde node.
Alt, hvad vi ville have at gøre, er at sætte den nye node næste pointer
at pege til 3. node
og derefter ReWire 2. knudepunkts næste pointerjustering
til at pege på vores nye node.
Så kan vi ændre størrelsen på vores liste på farten
da vores computer ikke er afhængig af indeksering,
men snarere på at knytte med pegepinde til at gemme dem.
>> En ulempe ved knyttet lister
er, at i modsætning til et statisk array,
computeren kan ikke bare hoppe til midten af ​​listen.
Da computeren har til at besøge hver node i den linkede liste
for at komme til det næste,
det vil tage længere tid at finde en bestemt node
end den ville i et array.
Til at krydse hele listen tager tid proportional
til længden af ​​listen,
eller O (n) i asymptotisk notation.
I gennemsnit nåede enhver node
også tager tid proportional med n..
>> Lad os nu faktisk skrive noget kode
der arbejder med hægtede lister.
Lad os sige, at vi ønsker en tilknyttet liste med heltal.
Vi kan repræsentere et knudepunkt i vores liste igen
som struct med 2 felter,
en heltalsværdi kaldet 'val'
og en næste markør til den næste node i listen.
Nå, synes simpelt nok.
>> Lad os sige at vi vil skrive en funktion
der gennemgår listen og udskriver den
lagret i det sidste emne på listen.
Tja, det betyder, at vi bliver nødt til at krydse alle knuder i listen
at finde den sidste, men da vi ikke har tilføjet
eller slette noget, vi ikke ønsker at ændre
den interne struktur i de næste markører på listen.
>> Så vil vi have en pointer specielt til traversal
som vi kalder "crawler".
Det vil kravle gennem alle elementer i listen
ved at følge kæden af ​​næste pointers.
Alt, hvad vi har gemt, er en pointer til 1. node,
eller 'hoved' på listen.
Head peger på 1. node.
Det er af typen pointer-to-node.
>> For at få den faktiske 1:e node i listen,
vi er nødt til at dereference denne pointer,
men før vi kan dereference det, er vi nødt til at kontrollere
hvis markøren er nul først.
Hvis det er nul, er tom,
og vi bør udskrive en besked, der, fordi listen er tom,
der er ingen sidste knudepunkt.
Men, lad os sige listen ikke er tom.
Hvis det ikke er, så bør vi kravler gennem hele listen
indtil vi kommer til det sidste emne på listen,
og hvordan kan vi fortælle, hvis vi ser på det sidste emne på listen?
>> Tja, hvis en node næste pointer er nul,
Vi ved, vi er i slutningen
siden sidste næste pointerjustering ville have nogen næste node i listen at pege på.
Det er god praksis altid at holde den sidste node næste pointer initialiseret til null
at have en standardiseret egenskab, som advarer os, når vi har nået slutningen af ​​listen.
>> Så hvis crawler → næste er null,
huske på, at pilen syntaksen er en genvej til dereferere
en pointer til en struct, så adgang
den næste felt svarende til den akavede:
(* Crawler). Næste.
Når vi har fundet den sidste node,
vi ønsker at udskrive crawler → val,
værdien i den aktuelle node
som vi ved er den sidste.
Ellers, hvis vi ikke er endnu på det sidste node i listen,
vi er nødt til at gå videre til den næste node i listen
og kontrollere, om det er den sidste.
For at gøre dette, har vi bare indstille vores webcrawler pointer
at pege på den aktuelle node næste værdi,
det vil sige den næste node i listen.
Dette gøres ved at sætte
crawler = crawler → næste.
Så kan vi gentage denne proces, med en løkke for eksempel
indtil vi finder den sidste node.
Så, for eksempel hvis crawler pegede på hovedet
vi satte crawler til at pege på crawler → næste,
hvilket er det samme som det næste felt i den 1. node.
Så nu er vores crawler peger til 2. node,
og igen vi gentage dette med en løkke,
indtil vi har fundet den sidste node, dvs
hvor knuden næste pointer peger til null.
Og der har vi det,
vi har fundet den sidste node i listen, og at udskrive dens værdi,
vi bare bruge crawler → val.
>> Gennemkører er ikke så slemt, men hvad med at indsætte?
Lad os sige, at vi ønsker at indsætte et heltal i den 4. plads
i et heltal liste.
Det er mellem de nuværende 3. og 4. noder.
Igen, vi er nødt til at krydse den liste bare til
komme til 3. element, den ene vi indsætte efter.
Så skaber vi en crawler pointer igen at krydse listen,
kontrollere, om vores hoved pointer er nul,
og hvis det ikke er, peger vores webcrawler pointer i spidsen node.
Så vi er på 1. element.
Vi er nødt til at gå fremad 2 flere elementer, før vi kan indsætte,
så vi kan bruge en for-løkke
int i = 1; i <3, jeg + +
og i hver iteration af løkken,
fremme vores webcrawler pointer frem med 1 node
ved at kontrollere, om den aktuelle node næste felt er nul,
og hvis det ikke er, skal du flytte vores webcrawler markøren til den næste node
ved at sætte det lig med den aktuelle node næste pointer.
Så da vores for løkke siger at gøre det
to gange,
vi har nået den 3. knude,
og når vores webcrawler pointer har nået node efter
som vi ønsker at indsætte vores nye heltal,
hvordan kan vi rent faktisk gør det indsættelse?
>> Nå, vores nye heltal skal indsættes i listen
som en del af sin egen node struct,
idet dette er virkelig en sekvens af knudepunkter.
Så lad os lave en ny pointer til knude
kaldes 'new_node'
og sæt den til at pege på hukommelse, som vi nu tildele
på heapen for knuden selv,
og hvor meget hukommelse har vi brug for at afsætte?
Nå, størrelsen af ​​et knudepunkt,
og vi ønsker at sætte sit val felt til heltal, vi ønsker at indsætte.
Lad os sige, 6.
Nu node indeholder vores heltalsværdi.
Det er også god praksis at initialisere den nye node næste felt
at pege på null,
men hvad nu?
>> Vi ændre den interne struktur af listen
og de næste pointers i listen eksisterende
3. og 4. knudepunkter.
Da de næste pointers bestemme rækkefølgen af ​​listen,
og da vi sætter vores nye knudepunkt
lige ind i midten af ​​listen,
det kan være en smule tricky.
Dette skyldes, husk, vores computer
kun kender placeringen af ​​knudepunkter i listen
på grund af de næste pointers lagret i de foregående knudepunkter.
Så hvis vi nogensinde mistet overblikket over nogen af ​​disse steder,
sige ved at ændre en af ​​de næste pejlemærker i vores liste,
for eksempel, siger vi ændret
3. knudepunkts næste felt
at pege på nogle node herovre.
Vi ville være ude af lykke, fordi vi ikke ville
har nogen idé om, hvor at finde resten af ​​listen,
og det er naturligvis virkelig dårlig.
Så vi er nødt til at være virkelig forsigtig med ordren
hvor vi manipulere vores næste pointers under indføring.
>> Så for at forenkle det, så lad os sige, at
vores første 4 noder
kaldes A, B, C og D, med pilene repræsenterer kæden af ​​pegepinde
der forbinder knudepunkter.
Så er vi nødt til at indsætte vores nye knudepunkt
i mellem knudepunkterne C og D.
Det er afgørende at gøre det i den rigtige rækkefølge, og jeg vil vise dig hvorfor.
>> Lad os se på den forkerte måde at gøre det først.
Hey, vi ved det nye knudepunkt skal komme lige efter C,
så lad os indstille C næste pointer
at pege på new_node.
Okay, virker okay, vi bare nødt til at slutte op nu ved
gør den nye knude næste pointer pege på D,
men vent, hvordan kan vi gøre det?
Det eneste, der kunne fortælle os, hvor D var,
blev den næste pointer tidligere lagret i C,
men vi bare omskrev denne pegepind
den peger på den nye knudepunkt,
så vi ikke længere har nogen anelse om, hvor D er i hukommelsen,
og vi har mistet resten af ​​listen.
Ikke god til alle.
>> Så hvordan vi gør det rigtigt?
Først peger det nye knudepunkt næste pointer på D.
Nu, både den nye node-og C'er næste pointers
peger på det samme knudepunkt, D,
men det er fint.
Nu kan vi pege C næste pointer på det nye knudepunkt.
Så vi har gjort dette uden at miste data.
I kode, er C den aktuelle node
at gennemkrydsning pointer crawler peger på,
og D er repræsenteret ved knudepunktet peges på af den aktuelle node næste felt,
eller crawler → næste.
Så vi startede det nye knudepunkt næste pointer
at pege på crawler → næste,
på samme måde, vi sagde new_node næste pointer bør
pege på D på illustrationen.
Derefter kan vi sætte den aktuelle node næste pointer
til vores nye knudepunkt,
ligesom vi måtte vente til punkt C til new_node på tegningen.
Nu alt er i orden, og vi ikke mister
styr på alle data, og vi var i stand til bare
holde vores nye knudepunkt i midten af ​​listen
uden at genopbygge det hele eller endda flytte eventuelle elementer
den måde, vi ville have haft til med en fast længde array.
>> Så hægtede lister er en grundlæggende, men vigtig, dynamisk datastruktur
som har både fordele og ulemper
sammenlignet med arrays og andre datastrukturer,
og som det ofte er tilfældet i datalogi,
Det er vigtigt at vide, hvornår du skal bruge hvert værktøj,
så du kan vælge det rigtige værktøj til det rigtige job.
>> For mere praksis, så prøv at skrive funktioner til
slette noder fra en sammenkædet liste -
husk at være forsigtig med den rækkefølge, som du omarrangere
Deres næste pointere at sikre, at du ikke mister en bid af din liste -
eller en funktion til at tælle knudepunkter i et sammenkædet liste,
eller en sjov en, at bytte om på rækkefølgen af ​​alle knudepunkter i en sammenkædet liste.
>> Mit navn er Jackson Steinkamp, ​​det er CS50.