[Powered by Google Translate] Programazioa, sarritan behar dugu balioen zerrendak irudikatzeko,
hala nola, ikasleen izenak atal bat
edo beren azken quiz partiturak.
>> C hizkuntzan, deklaratu array erabil daiteke
zerrendak gordetzeko.
Erraza da zerrenda batean elementu aipa
array batean gordetzen dira, eta sartzeko behar duzu bada
aldatzeko edo zerrendako elementua Ith
indize batzuk arbitrarioak I,
denbora etengabe egin ahal izango da,
baina array desabantailak ere.
>> Horietako aldarrikatzen dugu, esan behar dugu ari
aurrean nola big dute gora,
hau da, zenbat elementu gorde ahal izango dute
eta nola big elementu horiek dira, zein bere motaren arabera zehaztuko da.
Esate baterako, int ARR (10)
10 elementuak gorde ditzake
int baten tamaina dira.
>> Aitorpena egin ondoren, ezin dugu array baten tamaina aldatu.
Array berri bat egin behar dugu, nahi dugu, elementu gehiago gorde nahi izanez gero.
Muga hori existitzen arrazoia da gure
programa osoa array gordetzen
alboko zatia memoria gisa.
Say honetan buffer non gordetzen gure array da.
Beste aldagai batzuk ere izan liteke
dago eskubidea hurrengo array
memoria, eta, beraz, ezin dugu
besterik ez egin array handiagoa.
>> Batzuetan array azkar datuak sartzeko abiadura merkataritza genuke
apur bat gehiago malgutasuna.
Idatzi zerrenda lotuta, beste oinarrizko datu-egitura
agian ez duzu ezagutzen.
Maila altua,
lotuta zerrenda bat gordetzen datuak nodoen sekuentzia
diren loturak, elkarren artean lotuta
hortik datorkio izena 'lotuta zerrenda.'
Ikusi dugu, diseinu aldea
abantailak eta desabantailak ezberdinak eramango gaitu
array bat baino.
>> Hona hemen batzuk C osoko zenbakien oso erraza lotuta zerrenda kodea.
Nodo bakoitzean irudikatzen dugun dezakezu
struct 2 gauza bat biltzen dituen zerrendan,
zenbaki oso bat gordetzeko deitu 'val'
eta hurrengo nodo zerrenda esteka
izeneko erakuslea dugu 'next'.
Horrela, zerrenda osoa jarraitzeko aukera izango dugu
1go nodoaren erakuslea bakar bat,
eta, ondoren, hurrengo erakusleak jarraitu ahal izango dugu
2 nodo
3 nodo
4 nodo
eta, beraz, zerrendaren bukaera arte iritsi.
>> 1 abantaila hau ikusteko ahal izango duzu
array egitura estatikoak baino gehiago lotuta zerrenda batekin,
ez dugu behar memoria zati handi bat elkarrekin.
Zerrendako 1. Nodo memorian leku hau bizi izan,
eta 2 nodo hemen modu guztiak izan daitezke.
Gaitezke nodo guztiak ez du axola non memoria dira,
1ean nodo hasita, nodo bakoitzean hurrengo erakuslea delako
kontatzen digu zehazki non hurrengo joan.
>> Horrez gain, ez dugu esan nahi aurrean
nola big lotuta zerrenda bat array estatiko egin dugu izango da,
nodo zerrenda bat gehitzen jarraituko dugu
betiere, espazio gisa da nodo berriak memoria nonbait.
Beraz, zerrendak lotutako erraza dinamikoki tamainaz aldatu dira.
Esan, geroago programa nodo gehiago gehitu behar dugu
gure zerrendan sartu.
Nodo berria sartu hegan gure zerrendan sartu da, eta
nodo horren memoria esleitu egin behar dugu,
plop datuak balioa,
eta, ondoren, ipini non nahi erakusleak egokiak egokituz dugu.
>> Esate baterako, artean nodo bat jarri nahi izan dugu
zerrenda nodo 2 eta 3,
ez genuke, 2 edo 3. nodo mugitzeko.
Esan nodoa gorria txertatzen ari gara.
Guztiak genuke berria nodo hurrengo erakuslea
3 nodo batetara
eta, ondoren, rewire hurrengo 2 nodo erakuslea
gure nodo batetara.
Beraz, gure zerrendak tamainaz aldatu ahal izango dugu hegan
gure ordenagailuan ez baitu indexatzeko oinarritzen,
baizik eta erakusleak erabiliz gorde estekatzeko.
>> Hala eta guztiz ere, desabantaila bat lotuta zerrendak
dago, array estatiko bat bezala,
ordenagailua ezin zerrendaren erdian joango da.
Ordenagailua nodo bakoitzean bisita lotuta zerrenda geroztik
hurrengo bat lortzeko,
gehiago tardatuko nodo bat aurkitu du
array bat egiten baino.
Zerrenda osoa denbora proportzionala zeharkatuko
zerrendaren luzera,
edo O (n) notazioa asymptotic.
Batez beste, nodo edozein iritsi
ere denbora n proportzionala.
>> Orain, benetan idatzi kodea batzuk
zerrendak lotuta lan egiten duen.
Demagun zenbaki osoen zerrenda bat lotuta nahi dugu.
Nodo bat irudikatu ahal izango ditugu, gure zerrendan berriro
2 eremu eta egitura gisa,
'val' izeneko osoko balioa
eta hurrengo zerrendako hurrengo nodo erakuslea.
Beno, badirudi simple nahikoa.
>> Demagun funtzio bat idatzi nahi dugu
zeharkatzen zerrenda eta grabatuak out
zerrendaren azken nodo balioa gordetzen da.
Beno, horrek esan nahi du zerrendan nodo guztiak zeharkatzeko behar dugu
azkena, baina ari gara, ez baita gehituz
edo ezer ezabatu, ez dugu nahi aldatu
zerrendako hurrengo erakusleak barne egitura.
>> Beraz, erakusle bat behar dugu zehazki traversal
horrek deitu dugu 'arakatzaileak.
Zerrendako elementu guztiak arakatu bidez izango da
erakusleak hurrengo kate jarraituz.
Guztiak gordetzen dugu 1go nodoaren erakuslea da,
edo 'burua' zerrendan.
Head 1go nodo puntu.
Mota erakuslea-to-nodoa da.
>> Benetako nodo zerrenda 1ean,
dute dereference erakuslea honetan
baina dereference aurretik, egiaztatu behar dugu
erakuslea da null bada, lehen aldiz.
Da null bada, zerrenda hutsik dago.
inprimatu eta mezu bat behar dugu, zerrenda hutsik dagoelako,
azken nodoa ez dago.
Baina, demagun zerrenda ez dago hutsik.
Ez bada, eta, ondoren, zerrenda osoa bitartez arakatu behar dugu
zerrendako azken nodo dugu arte,
eta nola ari gara azken nodo zerrendan begiratuz gero esango dugu?
>> Beno, Nodo baten erakuslea da hurrengo null bada,
Oraindik amaieran badakigu
azken erakusleak zerrendako hurrengo nodo seinalatzen ez dute hurrengo geroztik litzateke.
Praktika onak, beti egon da azken nodoaren erakuslea hurrengo hasieratu to null
normalizatua jabetza abisatzen dugu zerrendaren bukaeran iritsi denean.
>> Beraz, crawler → hurrengo null bada,
gogoan izan arrow sintaxia dereferencing lasterbide bat da
egitura erakuslea, eta sartzeko
bere hurrengo eremuan awkward, baliokideak:
(* Crawler). Hurrengo.
Behin aurkitu dugu azken nodoak,
crawler → val inprimatu nahi dugu,
nodo uneko balioa
ezagutzen dugun azkena da.
Bestela, oraindik Oraindik ez badugu zerrendako azken nodo
zerrendako hurrengo nodo mugitzeko dugu
eta egiaztatu azkena.
Horretarako, ezarri besterik ez dugu gure arakatzaileak erakuslea
hurrengo uneko nodoaren balioa seinalatu,
hau da, zerrendako hurrengo nodo.
Hori ezartzeko egindako
crawler = crawler → hurrengo.
Ondoren, prozesu hau errepikatu dugu, esate baterako, begizta bat,
aurkituko dugu azken nodo arte.
Horrela, esate baterako, crawler zen buruan apuntatzen bada,
crawler dugu crawler → hurrengo seinalatu
1. nodo hurrengo eremuan bera da.
Beraz, orain, gure arakatzaileak 2 nodo seinalatuz,
eta, berriro ere, errepikatu dugu begizta
azken nodo aurkitu dugu arte, hau da,
non nodoaren erakuslea da hurrengo null seinalatuz.
Eta hor egon behar dugu,
azken nodo zerrendan aurkitu dugu, eta bere balioa inprimatu
erabili besterik ez dugu crawler → val.
>> Traversing ez da hain txarra, baina zer txertatu buruz?
Lets 4 posizioan zenbaki oso bat sartu esan nahi dugu
osoko zerrendan.
Nodoen artean 3 eta 4 uneko da.
Berriz ere, zerrenda zeharkatuko besterik ez dugu
3 elementu txertatzen ari gara ondoren.
Beraz, arakatzaileak erakuslea bat sortu dugu berriro zerrendan zeharkatzeko,
egiaztatu da gure burua erakuslea null bada,
eta ez bada, gure arakatzaileak burua nodoaren erakuslea.
Beraz, 1go elementu Oraindik dugu.
Aurrera joateko 2 gehiago sartu ahal izango dugu aurretik elementu ditugu,
beraz, erabili ahal izango dugu, begizta
int i = 1; i <3; i + +
eta begizta-iterazio bakoitzerako,
aurrera, gure arakatzaileak erakuslea 1 nodoa aurrera
hurrengo uneko nodoaren eremua null egiaztatzen bada,
eta ez bada, gure arakatzaileak erakuslea mugitu hurrengo nodo
hurrengo uneko nodoaren erakuslea berdintasuna ezarriz.
Beraz, gure loop dio horretarako geroztik
birritan,
3 nodo lortu dugu,
eta behin, gure arakatzaileak erakuslea erdietsi nodoaren ondoren
gure berri osokoa txertatu nahi dugu,
nola egin ez dugu sartzen?
>> Beno, gure berri osokoa zerrendan sartu du
bere, nodo propioa struct-zati gisa,
hau da, benetan geroztik nodoen sekuentzia bat.
Beraz, dezagun erakuslea nodo berria egin
izeneko 'new_node,'
eta ezarri memoria seinalatu dugun esleitu
nodo bera zeure
eta zenbat memoria esleitu behar dugu?
Beno, nodo baten tamaina,
eta bere val eremuan sartu nahi dugun osoko ezarri nahi dugu.
Demagun, 6.
Orain, nodoak gure osoko balioa dauka.
Ona da, halaber, praktika berriak nodo hurrengo eremuan hasieratu
null seinalatu,
baina orain zer?
>> Zerrendan barne egitura aldatu behar dugu
eta hurrengo zerrendan dagoen erakusleak
Nodo 3an eta 4an.
Hurrengo erakusleak zerrendako ordena zehaztu geroztik,
ari gara eta gure berriak nodo geroztik txertatu
zerrendaren erdian sartu,
pixka bat delikatua izan daiteke.
Hau da, izan ere, gogoratu, gure ordenagailuan
nodo kokalekua daki zerrendan
erakusleak hurrengo nodo aurreko gordetako delako.
Beraz, inoiz ez dugu edozein kokaleku horietan pista galdu ezkero,
gure zerrendan hurrengo erakusle bat aldatuz esan,
Adibidez, esaten dugu aldatu
hurrengo 3 nodo eremuan
nodo batzuk hemen seinalatu.
Zorte genuke, ez genuke delako
edozein ideia non aurkitu zerrendako gainerako
eta hori, jakina, oso txarra da.
Beraz, benetan ordena buruz kontuz ibili behar dugu
gure hurrengo erakusleak manipulatzeko txertatzeko zehar.
>> Beraz, hori errazteko, demagun
gure lehen 4 nodo
deitzen dira A, B, C, eta D, erakusleak kate geziak
nodo lotzen.
Beraz, gure nodo berria sartu behar dugu
C eta D. nodoen arteko
Kritikoa ordena egokian egin behar da, eta erakutsi dut zergatik.
>> Dezagun modu oker egin lehen begiratu.
Hey, nodo berri du eskubidea etorri C ondoren badakigu,
beraz, dezagun ezarri C hurrengo erakuslea
to new_node seinalatu.
Eskubidea guztiak, badirudi ados, besterik ez dugu amaitzeko orain
D berria nodoaren erakuslea hurrengo puntua egiteko,
baina itxaronaldia, nola egin dezaket dugu hori?
Gauza bakarra ezin izan digute non D izan zen,
izan zen hurrengo erakuslea aurretik C gordetzen dira,
baina besterik ez dugu erakuslea hori rewrote
nodo berria seinalatu,
beraz, ez dute jada arrastoren edozein non D memoria da,
eta zerrendako gainerako galdu dugu.
Batere ona.
>> Beraz, nola ez eskubide hori egiten dugu?
Lehenik eta behin, berri nodo D. erakuslea hurrengo
Orain, bai nodo eta C hurrengo erakusleak
nodoa berean, D seinalatuz,
baina fina.
Orain C erakuslea nodo berria hurrengo seinalatu ahal izango dugu.
Beraz, hau egin dugu daturik galdu gabe.
Kodea, C uneko nodoaren
traversal erakuslea crawler hori seinalatuz,
eta D Nabarmendu uneko nodoaren eremuan hurrengo nodo irudikatzen
edo crawler → hurrengo.
Beraz, lehen aldiz ezarri dugu berria nodo hurrengo erakuslea
crawler → hurrengo seinalatu,
Era berean new_node hurrengo erakuslea esan genuen
D seinalatu agertzen.
Ondoren, hurrengo uneko nodoaren erakuslea ezarri ahal izango dugu
gure berri nodo
C seinalatu marrazkia new_node bezala itxaron egin behar izan dugu.
Orain guztia ordena da, eta ez dugu galtzen
datuen jarraipena, eta ahal izateko besterik ez ginen
makila gure berri nodo zerrendaren erdian
gauza osoa berreraikitzen edo, are gehiago, elementu edozein aldatzearen gabe
bidea izan nahi dugu izan finkoko-luzera array bat.
>> Beraz, zerrendak lotutako oinarrizko, baina garrantzitsua, datu dinamikorik egitura
dituzten abantailak eta desabantailak
array-ak eta beste datu egiturak aldean,
eta informatika kasuan izan ohi da,
garrantzitsua da jakin nahi denean erabili ahal izateko tresna bakoitzaren,
beraz, eskuineko lan tresna egokia hautatu ahal izango duzu.
>> Praktika gehiago nahi izanez gero, saiatu funtzioak idatziz
lotuta zerrenda nodoak ezabatu
gogoratzen duzu zein ordenatan berrantolatzeko buruz kontuz
zure erakusleak hurrengo zatia zure zerrenda bat galtzen ez duzula ziurtatzeko
edo funtzio bat nodo zenbatzea lotuta zerrenda,
edo fun bat, lotuta zerrenda batean nodo guztien ordena alderantzikatzeko.
>> Nire izena Jackson Steinkamp da, hau CS50 da.