[Powered by Google Translate] I programmering behöver vi ofta för att representera listor över värden,
såsom namnen på eleverna i ett avsnitt
eller deras poäng på den senaste frågesporten.
>> I C-språket, deklarerade arrayer kan användas
att lagra listor.
Det är lätt att räkna upp elementen i en lista
lagras i en array, och om du behöver komma åt
eller ändra den i: te listelement
för någon godtycklig index I,
som kan göras i konstant tid,
men arrayer har nackdelar också.
>> När vi förklarar dem, vi måste säga
på framsidan hur stora de är,
det vill säga hur många element som de kan lagra
och hur stor dessa element är, som bestäms av deras typ.
Till exempel, int arr (10)
kan lagra 10 poster
som är storleken på en int.
>> Vi kan inte ändra en rad storlek efter anmälan.
Vi måste göra en ny array om vi vill lagra fler element.
Anledningen till att denna begränsning finns är att vår
Programmet lagrar hela uppsättningen
som en sammanhängande bit av minne.
Säga att detta är den buffert där vi lagras i vår grupp.
Det kan finnas andra variabler
ligger intill matrisen
i minnet, så att vi inte kan
bara göra arrayen större.
>> Ibland vill vi handla arrayen snabba dataåtkomst hastighet
för lite mer flexibilitet.
Ange den länkade listan, en annan grundläggande datastruktur
du kanske inte så bekant med.
På en hög nivå,
en länkad lista lagrar data i en sekvens av noder
som är anslutna till varandra med länkar,
därav namnet "länkad lista".
Som vi ser, denna skillnad i design
leder till olika fördelar och nackdelar
än en matris.
>> Här är några C-kod för en länkad mycket enkel lista med heltal.
Du kan se att vi har representerade varje nod
i listan som en struct som innehåller 2 saker,
ett heltal för att lagra kallas "Val '
och en länk till nästa nod på listan
som vi representerar som en pekare som kallas "Nästa".
På detta sätt, kan vi spåra hela listan
med bara en enda pekare till den 1: a noden,
och då kan vi följa nästa pekare
till den 2: a noden,
till den 3: e noden,
till 4: e noden,
och så vidare, tills vi kommer till slutet av listan.
>> Du kanske kan se en fördel har detta
över den statiska matrisstruktur - med en länkad lista,
Vi behöver inte en stor bit av minnet helt och hållet.
Den 1: a noden i listan kunde leva på denna plats i minnet,
och 2nd noden kan vara ända hit.
Vi kan få till alla noder oavsett var i minnet de är,
eftersom start vid 1: a noden varje nod nästa pekare
berättar exakt vart man ska gå härnäst.
>> Dessutom behöver vi inte säga upp front
hur stor en länkad lista kommer att vara hur vi gör med statiska arrayer,
eftersom vi kan fortsätta att lägga noder i en lista
så länge det finns utrymme någonstans i minnet för nya noder.
Därför länkade listor är lätta att ändra storlek dynamiskt.
Säg, senare i programmet måste vi lägga till fler noder
i vår lista.
Om du vill infoga en ny nod i vår lista i farten,
allt vi behöver göra är att allokera minne för denna nod,
plopp i datavärdet,
och sedan placera den där vi vill genom att justera lämpliga pekare.
>> Till exempel, om vi ville placera en nod i mellan
den 2: a och 3: e noder i listan,
Vi skulle inte behöva flytta 2 eller 3 noder alls.
Säg att vi sätter denna röda nod.
Allt vi skulle behöva göra är att ställa den nya noden nästa pekare
att peka på noden 3:e
och sedan ReWire 2: a noden nästa pekare
att peka på vår nya noden.
Så kan vi ändra storleken våra listor på fluga
eftersom vår dator inte är beroende av indexering,
utan snarare på att koppla med pekare för att lagra dem.
>> Emellertid, en nackdel med länkade listor
är att, till skillnad från en statisk matris,
datorn kan inte bara hoppa till mitten av listan.
Eftersom datorn har att besöka varje nod i den länkade listan
för att komma till nästa,
det kommer att ta längre tid att hitta en viss nod
än den skulle i en array.
Att korsa hela listan tar tid proportionell
till längden av listan,
eller O (n) i asymptotisk notation.
I genomsnitt, når varje nod
också tar tid proportionell mot n..
>> Nu ska vi faktiskt skriva lite kod
som arbetar med länkade listor.
Låt oss säga att vi vill ha en länkad lista av heltal.
Vi kan representera en nod i vår lista igen
som en struktur med 2 fält,
ett heltal kallas "Val '
och en nästa pekare till nästa nod på listan.
Tja, det verkar enkelt nog.
>> Låt oss säga att vi vill skriva en funktion
som går igenom listan och skriver ut
värde som lagras i den sista noden i listan.
Tja, innebär att vi kommer att behöva korsa alla noder i listan
att hitta den sista, men eftersom vi inte lägger
eller ta bort något, vi vill inte ändra
den interna strukturen för nästa pekare i listan.
>> Så behöver vi en pekare speciellt för traversering
som vi kallar "sökrobot".
Det kommer att krypa igenom alla element i listan
genom att följa kedjan av nästa pekare.
Allt vi har lagrat en pekare till den 1: a noden,
eller "chef" i listan.
Head pekar på 1. Noden.
Det är av typen pekare-till-nod.
>> För att få den verkliga 1:e nod i listan,
vi dereference denna pekare,
men innan vi kan dereference det måste vi kontrollera
Om pekaren är null först.
Om det är noll, är listan tom,
och vi bör skriva ut ett budskap att eftersom listan är tom,
det finns ingen sista nod.
Men låt oss säga att listan inte är tom.
Om det inte, bör vi krypa igenom hela listan
tills vi kommer till den sista noden i listan,
och hur kan vi berätta om vi tittar på den sista noden i listan?
>> Tja, om en nod nästa pekare är null
Vi vet att vi är i slutet
sedan den senaste nästa pekare skulle ha någon nästa nod i listan för att peka på.
Det är en god vana att alltid hålla den sista noden nästa pekare initieras till null
att ha ett standardiserat egenskap som varnar oss när vi har nått slutet av listan.
>> Så om sökrobot → Nästa är null,
kom ihåg att pilen syntaxen är en genväg för att dereferencing
en pekare till en struktur, och sedan komma
nästa fält motsvarar besvärliga:
(* Larvfötter). Nästa.
När vi har hittat den sista noden,
Vi vill skriva ut sökrobot → val,
värdet i den aktuella noden
som vi vet är den sista.
Annars, om vi inte ännu på den sista noden i listan,
Vi måste gå vidare till nästa nod i listan
och kontrollera om det är den sista.
För att göra detta, satte vi bara vår sökrobot pekare
att peka på den aktuella noden nästa värde,
dvs, den nästa nod i listan.
Detta görs genom att ställa
sökrobot = sökrobot → Nästa.
Då vi upprepa denna process med en ögla till exempel,
tills vi hittar den sista noden.
Så, till exempel, om sökrobot pekade på huvudet,
Vi satt sökrobot peka på sökrobot → nästa,
som är densamma som nästa fält av den 1st noden.
Så, nu är vår sökrobot pekar på 2. Noden,
och, återigen, upprepar vi detta med en slinga,
tills vi har hittat den sista noden, är att
där noden nästa pekare pekar på null.
Och där har vi det,
Vi har hittat den sista noden i listan och skriva ut dess värde,
Vi använder bara larvfötter → val.
>> Tvärgående är inte så illa, men hur du sätter?
Låt oss säga att vi vill infoga ett heltal i den 4: e positionen
i ett heltal lista.
Det är mellan de nuvarande 3 och 4 noder.
Återigen måste vi korsa listan bara för att
få till den 3: e elementet, ett vi sätter efter.
Så skapar vi en sökrobot pekare igen korsa listan,
kontrollera om vår framvisaren är null
och om det inte pekar vår sökrobot pekare på huvudnoden.
Så vi är på 1: a elementet.
Vi måste gå framåt 2 fler element innan vi kan sätta in,
så att vi kan använda en for-slinga
int i = 1; i <3, jag + +
och i varje iteration av slingan,
öka vår sökrobot pekare fram 1 nod
genom att kontrollera om den aktuella noden nästa fält är noll,
och om det inte flyttar vår sökrobot pekare till nästa nod
genom att ställa det lika med den aktuella noden nästa pekare.
Så, eftersom vår för slinga säger att göra det
två gånger,
Vi har nått den 3: e noden,
och när vår sökrobot pekare har nått noden efter
som vi vill infoga vår nya heltal,
hur vi faktiskt göra sätta?
>> Tja, har vår nya heltal som skall införas i den förteckning
som en del av sin egen nod struct,
eftersom detta är verkligen en sekvens av noder.
Så, låt oss göra en ny pekare till noden
kallas new_node "
och ställa in den att peka på minnet att vi nu fördela
i stacken för själva noden,
och hur mycket minne behöver vi fördela?
Jo, storleken av en nod,
och vi vill sätta sin val fält till heltal som vi vill infoga.
Låt oss säga, 6.
Nu innehåller noden vår heltalsvärde.
Det är också bra att initiera den nya noden nästa fält
peka på null,
men nu vad?
>> Vi måste förändra den interna strukturen av listan
och nästa pekare som finns i listan befintliga
3 och 4 noder.
Eftersom nästa pekare bestämma i vilken ordning listan,
och eftersom vi sätter vår nya noden
rakt in i mitten av listan,
det kan vara lite knepigt.
Detta beror, kom ihåg, vår dator
endast känner placeringen av noder i listan
på grund av de nästa pekare lagrade i de tidigare noderna.
Så, om vi någonsin förlorat reda på någon av dessa platser,
säga genom att ändra en av de kommande pekare i vår lista,
till exempel, säger vi ändrat
den 3: e noden nästa fält
att peka på någon nod hit.
Vi skulle vara ute på tur, eftersom vi inte skulle
har någon aning om var att hitta resten av listan,
och det är naturligtvis riktigt illa.
Så måste vi vara riktigt försiktig om beställning
där vi manipulerar vår nästa pekare under införande.
>> Så, för att förenkla detta, låt oss säga att
vår första 4 noder
kallas A, B, C och D, med pilarna representerar kedjan av pekare
som ansluter noderna.
Så måste vi sätta vår nya noden
mellan noderna C och D.
Det är viktigt att göra det i rätt ordning, och jag ska visa dig varför.
>> Låt oss titta på fel sätt att göra det först.
Hej, vi vet den nya noden måste komma direkt efter C,
så låt oss ställa C: s nästa pekare
att peka på new_node.
Okej, verkar okej, vi bara avsluta nu genom
gör den nya noden nästa pekare pekar på D,
men vänta, hur kan vi göra det?
Det enda som skulle kunna tala om för oss där D var,
var nästa pekare lagrad tidigare i C,
men vi skrev bara att pekaren
att peka till den nya noden,
så vi inte längre har någon aning där D är i minnet,
och vi har förlorat resten av listan.
Inte bra alls.
>> Så, hur vi gör detta rätt?
Först pekar den nya noden nästa pekare vid D.
Nu, både den nya nodens och C: s nästa pekare
pekar på samma nod, D,
men det är bra.
Nu kan vi punkt C nästa pekare på den nya noden.
Så har vi gjort detta utan att förlora några data.
I kod, C är aktuella noden
att förflyttning pekaren sökrobot pekar på,
och D representeras av noden pekas på av den aktuella noden nästa fält,
eller larvfötter → Nästa.
Så ställer vi först den nya noden nästa pekare
att peka på sökrobot → nästa,
på samma sätt som vi sa new_node nästa pekare bör
peka till D i figuren.
Då kan vi ställa den aktuella noden nästa pekare
till vår nya noden,
precis som vi var tvungna att vänta till punkt C för att new_node på ritningen.
Nu allt är i ordning, och vi inte förlorar
reda på alla uppgifter, och vi kunde bara
hålla vår nya nod i mitten av listan
utan att bygga om hela eller ens flytta några element
det sätt vi skulle ha behövt en fast längd matris.
>> Så, länkade listor är en grundläggande, men viktiga, dynamiska datastruktur
som har både fördelar och nackdelar
jämfört med matriser och andra datastrukturer,
och som ofta är fallet i datavetenskap,
Det är viktigt att veta när du ska använda varje verktyg,
så att du kan välja rätt verktyg för rätt jobb.
>> För mer övning, försök att skriva funktioner
bort noder från en länkad lista -
kom ihåg att vara försiktig om i vilken ordning du ordna
ditt nästa pekare för att säkerställa att du inte förlorar en bit av din lista -
eller en funktion för att räkna noderna i en länkad lista,
eller en rolig en, för att kasta om ordningen av alla noder i en länkad lista.
>> Mitt namn är Jackson Steinkamp, ​​det här CS50.