[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.