[Powered by Google Translate] I programmering, vi ofte behov for å representere lister over verdier,
slik som navn på elevene i en del
eller deres score på den siste quiz.
>> I C-språk, erklærte arrayer kan brukes
for å lagre lister.
Det er lett å oppsummere elementene i en liste
lagret i en matrise, og hvis du trenger tilgang til
eller endre ed listeelement
for noen vilkårlig indeks I,
som kan gjøres i konstant tid,
men arrays har ulemper også.
>> Når vi erklære dem, er vi forpliktet til å si
opp foran hvor store de er,
det vil si hvor mange elementer de kan lagre
og hvor store disse elementene er, som bestemmes av type.
For eksempel, int arr (10)
kan lagre 10 varer
som er på størrelse med en int.
>> Vi kan ikke endre en rekke størrelse etter erklæringen.
Vi må lage en ny rekke hvis vi ønsker å lagre flere elementer.
Grunnen denne begrensningen eksisterer er at vår
Programmet lagrer hel rekke
som en sammenhengende del av minnet.
Si dette er den buffer der vi lagret i array vår.
Det kan være andre variabler
ligger rett ved siden av tabellen
i minnet, slik at vi ikke kan
bare gjøre array større.
>> Noen ganger vi ønsker å handle array rask datatilgang hastighet
for litt mer fleksibilitet.
Skriv inn lenket liste, en annen grunnleggende datastruktur
du kanskje ikke være så kjent med.
På et høyt nivå,
en lenket liste lagrer data i en sekvens av noder
som er koblet til hverandre med koblinger,
derav navnet "lenket liste.
Som vi vil se, denne forskjellen i design
fører til forskjellige fordeler og ulemper
enn en matrise.
>> Her er noen C-kode for en veldig enkel lenket liste av heltall.
Du kan se at vi har representert hver node
i listen som en struct som inneholder to ting,
et heltall for å lagre kalt 'val'
og en link til neste node i listen
som vi representerer som en peker som heter "neste".
På denne måten kan vi spore hele listen
med bare en enkelt peker til første node,
og så kan vi følge de neste pekere
til 2. node,
til 3. node,
til 4. node,
og så videre, helt til vi kommer til slutten av listen.
>> Du kan være i stand til å se en fordel dette har
over statisk array struktur - med en lenket liste,
Vi trenger ikke en stor del av minnet helt.
Den første noden i listen kunne leve på dette stedet i minnet,
og andre node kan være hele veien hit.
Vi kan få til alle nodene uansett hvor i minnet er de,
fordi starter på første node, hver node neste pekeren
forteller oss nøyaktig hvor du skal gå neste.
>> I tillegg har vi ikke å si opp foran
hvor stor en lenket liste vil være måten vi gjør med statiske arrays,
siden vi kan fortsette å legge noder i en liste
så lenge det er plass et sted i minnet for nye noder.
Derfor lenkede lister er lett å endre størrelsen dynamisk.
Si, senere i programmet må vi legge til flere noder
til listen vår.
Å sette inn en ny node i vår liste på sparket,
alt vi trenger å gjøre er å allokere minne for den noden,
plop i dataverdi,
og deretter plassere den der vi ønsker ved å justere de nødvendige pekere.
>> For eksempel, hvis vi ønsket å plassere en node i mellom
2. og 3. noder i listen,
vi ville ikke ha å flytte andre eller tredje noder i det hele tatt.
Si at vi setter denne røde noden.
Alt vi måtte gjøre er å sette den nye nodens neste pekeren
å peke på den tredje node
og deretter ReWire andre nodens neste pekeren
å peke på vår nye node.
Så kan vi endre størrelsen våre lister på fly
siden vår datamaskin ikke stole på indeksering,
men heller på å knytte bruke pekere til å lagre dem.
>> Imidlertid, en ulempe med koblede lister
er at, i motsetning til en statisk array,
maskinen kan ikke bare hoppe til midten av listen.
Siden maskinen har å besøke hver node i lenket liste
å komme til neste,
det kommer til å ta lengre tid å finne en bestemt node
enn det ville i en matrise.
Å traversere hele listen tar tid proporsjonal
til lengden av listen,
eller O (n) i asymptotisk notasjon.
I gjennomsnitt, nå noen node
også tar tid proporsjonal med n.
>> Nå, la oss faktisk skrive noen kode
som fungerer med koblede lister.
La oss si at vi en lenket liste av heltall.
Vi kan representere en node i vår liste igjen
som en struct med 2 felt,
et heltall kalles 'val'
og en neste pekeren til neste node i listen.
Vel, synes enkel nok.
>> La oss si vi ønsker å skrive en funksjon
som gjennomgår listen og skriver ut
som er lagret i den siste noden i listen.
Vel, det betyr at vi må traversere alle nodene i listen
å finne den siste, men siden vi ikke legger
eller slette noe, ønsker vi ikke å endre
den interne strukturen av de neste pekere i listen.
>> Så trenger vi en peker spesielt for traversering
som vi kaller 'crawler.
Den kryper gjennom alle elementene i listen
ved å følge kjeden av neste pekere.
Alt vi har lagret er en peker til første node,
eller "hodet" på listen.
Hodet peker til første node.
Det er av typen pointer-til-node.
>> For å få den faktiske første node i listen,
vi må dereferanse denne pekeren,
men før vi kan dereferanse det, må vi sjekke
hvis pekeren er null først.
Hvis det er null, er listen tom,
og vi bør skrive ut en melding om at, fordi listen er tom,
det er ingen siste noden.
Men, la oss si at listen er ikke tom.
Hvis det ikke er det, så vi bør gjennomgå hele listen
før vi kommer til den siste noden i listen,
og hvordan kan vi vite at vi ser på den siste noden i listen?
>> Vel, hvis en node neste pekeren er null,
Vi vet at vi på slutten
siden siste neste pekeren ville ha noe neste node i listen for å vise til.
Det er god praksis å alltid holde den siste noden neste pekeren initialisert til null
å ha en standardisert egenskap som varsler oss når vi har nådd slutten av listen.
>> Så hvis crawler → neste er null,
husk at pilen syntaksen er en snarvei for dereferencing
en peker til en struct, deretter tilgang
dens neste felt tilsvarer klosset:
(* Crawler). Neste.
Når vi har funnet den siste noden,
Vi vil skrive ut crawler → val,
verdien i gjeldende node
som vi vet er den siste.
Ellers, hvis vi er ennå ikke i siste node i listen,
vi må gå videre til neste node i listen
og sjekk om det er den siste.
For å gjøre dette, vi bare sette vår crawler pekeren
å peke på gjeldende node neste verdi,
det vil si den neste node i listen.
Dette gjøres ved å sette
crawler = crawler → neste.
Så vi gjentar denne prosessen, med en løkke for eksempel,
til vi finner den siste noden.
Så, for eksempel, hvis crawler pekte på hodet,
vi satt crawler til å peke på crawler → neste,
som er det samme som det neste feltet i første noden.
Så nå søkeroboten peker til andre node,
og, igjen, gjentar vi dette med en løkke,
før vi har funnet den siste noden, er at
hvor noden neste pekeren peker til null.
Og der har vi det,
vi har funnet den siste noden i listen, og til å skrive ut sin verdi,
vi bare bruke crawler → val.
>> Traversering er ikke så ille, men hva med å sette inn?
La oss si at vi ønsker å sette et heltall i fjerde posisjon
i et heltall liste.
Som er mellom dagens tredje og fjerde noder.
Igjen har vi å traversere listen bare for å
komme til tredje element, den vi setter etter.
Så lager vi en crawler peker igjen for å traversere listen,
sjekk om vårt hode pekeren er null,
og hvis det ikke er det, peke søkeroboten pekeren på hodet node.
Så er vi på første element.
Vi må gå frem to flere elementer før vi kan sette inn,
slik at vi kan bruke en for loop
int i = 1; i <3; i + +
og i hver iterasjon av loopen,
fremme søkeroboten pekeren framover ved en node
ved å sjekke om den nåværende node neste feltet er null,
og hvis det ikke er det, flytter søkeroboten pekeren til neste node
ved å sette den lik gjeldende node neste pekeren.
Så, siden vår for loop sier å gjøre det
to ganger,
Vi har nådd tredje node,
og når søkeroboten indikatoren har nådd node etter
som vi ønsker å sette vår nye heltall,
hvordan gjør vi faktisk gjør innsetting?
>> Vel, har vår nye heltall som skal settes inn i listen
som en del av sin egen node struct,
siden dette er virkelig en sekvens av noder.
Så, la oss lage en ny pekepinn på node
kalt "new_node, '
og sett den til å peke til minne om at vi nå bevilger
på haugen for noden selv,
og hvor mye minne trenger vi å fordele?
Vel, på størrelse med en node,
og vi ønsker å sette sitt val feltet til heltall som vi vil sette inn.
La oss si, 6.
Nå inneholder noden vårt heltallsverdi.
Det er også lurt å starte den nye nodens neste felt
å peke på null,
men hva nå?
>> Vi må endre interne strukturen listen
og de neste pekere finnes i listen eksisterende
3. og 4. noder.
Siden de neste pekere bestemme rekkefølgen av listen,
og siden vi sette vår nye node
rett inn i midten av listen,
det kan være litt vanskelig.
Dette er fordi, husk, vår datamaskin
vet bare plasseringen av noder i listen
grunn av de neste pekere lagret i tidligere noder.
Så, hvis vi noen gang mistet oversikten over noen av disse stedene,
si ved å endre en av de neste pekere i vår liste,
for eksempel, sier vi endret
3. nodens neste felt
å peke på noen node over her.
Vi vil være ute av lykken, fordi vi ikke ville
har noen anelse om hvor du finner resten av listen,
og det er åpenbart veldig dårlig.
Så må vi være veldig forsiktig med rekkefølgen
der vi manipulere våre neste pekere under innsetting.
>> Så, for å forenkle dette, la oss si at
våre 4 første noder
kalles A, B, C og D, med pilene representerer kjeden av pekere
som kobler nodene.
Så må vi sette inn vår nye node
i mellom noder C og D.
Det er viktig å gjøre det i riktig rekkefølge, og jeg vil vise deg hvorfor.
>> La oss se på feil måte å gjøre det først.
Hei, vi vet den nye noden må komme rett etter C,
så la oss sette C neste pekeren
å peke på new_node.
Greit, virker greit, vi må bare gjøre ferdig nå ved
gjør den nye nodens neste pekeren peker til D,
men vent, hvordan kan vi gjøre det?
Det eneste som kunne fortelle oss hvor D var,
var neste pekeren tidligere lagret i C,
men vi omskrev at pekeren
å peke på den nye noden,
så vi ikke lenger har noen anelse hvor D er i minnet,
og vi har mistet resten av listen.
Ikke bra i det hele tatt.
>> Så, hvordan vi gjør dette riktig?
Først peker den nye nodens neste peker på D.
Nå, både den nye nodens og C er neste pekere
peker til samme node, D,
men det er fint.
Nå kan vi peke C neste pekeren på den nye noden.
Så har vi gjort dette uten å miste data.
I kode, er C gjeldende node
at traversering pekeren crawler peker til,
og D er representert ved noden pekes til av gjeldende nodens neste felt,
eller crawler → neste.
Så vi først sette den nye nodens neste pekeren
å peke på crawler → neste,
på samme måte som vi sa new_node neste pekeren skal
peke på D i illustrasjonen.
Deretter kan vi sette gjeldende node neste pekeren
til vår nye node,
akkurat som vi måtte vente til punkt C til new_node i tegningen.
Nå er alt er i orden, og vi tapte ikke
spore av data, og vi var i stand til å bare
stokk vår nye node i midten av listen
uten å gjenoppbygge det hele eller skiftende noen elementer
måten vi ville ha hatt til med en fast lengde array.
>> Så, koblede lister er en grunnleggende, men viktig, dynamisk datastruktur
som har både fordeler og ulemper
sammenlignet matriser og andre datastrukturer,
og som ofte er tilfellet i informatikk,
det er viktig å vite når du skal bruke hvert verktøy,
slik at du kan velge riktig verktøy til rett jobb.
>> For mer praksis, kan du prøve å skrive funksjoner
slette noder fra en lenket liste -
Husk å være forsiktig om i hvilken rekkefølge du omorganisere
de neste pekere for å sikre at du ikke mister en del av listen -
eller en funksjon for å telle nodene i en lenket liste,
eller en morsom en, for å snu rekkefølgen på alle nodene i en lenket liste.
>> Mitt navn er Jackson Steinkamp, ​​er dette CS50.