[Powered by Google Translate] Në programimin, ne shpesh duhet të paraqesin listat e vlerave,
të tilla si emrat e nxënësve në një seksion
ose rezultatet e tyre në quiz fundit.
>> Në gjuhën C, ka deklaruar vargjeve mund të përdoren
për të ruajtur listat.
Është e lehtë të numëroj elementet e një liste
ruhen në një grup, dhe nëse keni nevojë për të hyrë në
ose modifikojë elementin ith listës
për disa indeksin arbitrare unë,
që mund të bëhet në kohë të vazhdueshme,
por vargjeve kanë disavantazhe, too.
>> Kur ne deklarojnë ata, ne jemi duke kërkuar për të thënë
deri para sa e madhe ato janë,
që është, se sa elementet që mund të ruajë
dhe sa e madhe këto elemente janë, që përcaktohet nga lloji i tyre.
Për shembull, int arr (10)
mund të ruajë 10 artikuj
që janë madhësia e një int.
>> Ne nuk mund të ndryshojë madhësinë e një sërë pas shpalljes.
Ne kemi për të bërë një rrjet të ri, nëse duam të ruajtur më shumë elemente.
Arsyeja e kësaj është se ekziston kufizim tonë
Programi i ruan tërë array
si një copë puqur të kujtesës.
Thonë se kjo është tampon ku ne të ruhet në rrjet tonë.
Nuk mund të jetë variablave të tjera
e vendosur të drejtë tjetër në grup
në kujtesën, kështu që ne nuk mund të
vetëm të bëjë array mëdha.
>> Ndonjëherë ne do të donim për të tregtuar shpejtësi të shpejtë grup të dhënat e qasjes
për një fleksibilitet pak më shumë.
Të hyjë në listën e lidhur, një tjetër strukturë themelore të dhënave
ju nuk mund të jetë aq i njohur me të.
Në një nivel të lartë,
një listë e lidhur ruan të dhënat në një sekuencë të nyjave
që janë të lidhura me njëri-tjetrin me lidhje,
prandaj 'lista e lidhur. "emër
Siç do të shohim, ky ndryshim në dizajn
çon në avantazhet dhe disavantazhet ndryshme
se një grup.
>> Ja disa kodi C për një listë shumë të thjeshtë të lidhur integers.
Ju mund të shihni se ne kemi përfaqësuar çdo nyje
në listën si një struct e cila përmban 2 gjëra,
një numër të plotë për të ruajtur quajtur 'val'
dhe një lidhje me nyje e ardhshme në listë
që ne përfaqësojmë si një tregues të quajtur "tjetër."
Në këtë mënyrë, ne mund të gjetur të gjithë listën
me vetëm një të vetme treguesin në nyje 1,
dhe pastaj ne mund të ndiqni pointers ardhshme
në nyje 2,
tek nyjes 3,
në nyje 4,
dhe kështu me radhë, deri sa të kemi në fund të listës.
>> Ju mund të jetë në gjendje për të parë 1 përfituar kjo ka
mbi strukturën statike array - me një listë të lidhura,
ne nuk kemi nevojë për një copë të madhe të kujtesës krejt.
1 në nyje e listës mund të jetojnë në këtë vend në kujtesë,
dhe nyja 2 mund të jetë gjatë gjithë rrugës mbi këtu.
Ne mund të merrni të gjitha nyjet ska rëndësi se ku në kujtesën ata janë,
sepse duke filluar në nyje 1, treguesin e ardhshëm çdo nyje e
na tregon saktësisht se ku të shkojnë tjetër.
>> Përveç kësaj, ne nuk kemi për të thënë që në fillim
sa i madh një listë e lidhur do të jetë mënyra që ne bëjmë me të vargjeve statike,
që ne mund të vazhdojmë duke shtuar nyje në një listë
për aq kohë sa nuk ka hapësirë ​​diku në kujtesë për nyjet reja.
Prandaj, listat e lidhura janë të lehtë për të resize dinamike.
Thuaj, më vonë në program ne kemi nevojë për të shtuar nyje më shumë
në listën tonë.
Për të futur një nyje të re në listën tonë të fluturojnë,
të gjithë ne duhet të bëni është të siguroj kujtesë për atë nyje,
pllum në vlerën e të dhënave,
dhe pastaj të vendosni atë ku ne duam duke rregulluar pointers duhura.
>> Për shembull, në qoftë se kemi dashur të zhvillohet një nyje në mes
nyjet 2 dhe 3 të listës,
ne nuk do të duhet të lëvizin nyjet 2 apo 3 në të gjitha.
Thonë se ne jemi futur këtë nyje të kuqe.
Të gjithë ne do të duhet të bëni është vendosur treguesin tjetër nyjen ri
për pikë në nyjen 3
dhe pastaj rewire treguesin tjetër nyjen e 2
për pikë në nyje tonë të ri.
Pra, ne mund të resize listat tona të fluturojnë
që nga kompjuteri ynë nuk mbështetet në indeksim,
por më tepër për lidhjen duke përdorur pointers për të ruajtur ato.
>> Listat e megjithatë, një dëm të lidhur
është se, ndryshe nga një grup statike,
kompjuteri nuk mund të hidhen në mes të listës.
Që kompjuter ka për të vizituar çdo nyje në listën lidhur
për të shkuar në një tjetër,
ajo do të marrë më të gjatë për të gjetur një nyje të veçantë
se ajo do të në një rrjet.
Të kaloj gjithë listën merr kohë proporcional
në gjatësinë e lista,
ose O (n) në simbol asymptotic.
Në mesatare, duke arritur ndonjë nyje
gjithashtu merr kohë proporcionale me n.
>> Tani, le të vërtetë shkruani disa kodin
që punon me listat e lidhura.
Le të thonë se ne duam një listë e lidhur e integers.
Ne mund të përfaqësojnë një nyje në listën tonë përsëri
si një struct me 2 fusha,
një vlerë e plotë quajtur 'val'
dhe një tregues tjetër për nyjen e ardhshëm të listës.
E pra, duket mjaft e thjeshtë.
>> Le të thonë se ne duam të shkruani një funksion
e cila përshkon listës dhe printime nga
vlera ruhen në nyjen e fundit të listës.
E pra, që do të thotë që ne do të duhet të kaloj nëpër të gjitha nyjet në listë
për të gjetur një të fundit, por që ne nuk jemi duke shtuar
ose fshirjes asgjë, ne nuk duam të ndryshojmë
Struktura e brendshme e pointers ardhshme në listë.
>> Pra, ne do të duhet një tregues veçanërisht për traversal
të cilat ne do të thërrasë "servil".
Ajo do të zvarritem nëpër të gjitha elementet e listës
duke ndjekur zinxhirin e pointers ardhshme.
Të gjithë ne kemi ruajtur është një tregues për nyjen 1,
ose 'kokë' i lista.
Points kreu në nyjen 1.
Kjo është e tipit pointer-to-node.
>> Për të marrë aktuale nyje 1 në listë,
ne duhet të dereference këtë tregues,
por para se ne mund të dereference atë, ne duhet të kontrolloni
nëse kursori është i pavlefshëm parë.
Nëse kjo është null, lista është e zbrazët,
dhe ne duhet të shtypura nga një mesazh që, për shkak se lista është e zbrazët,
nuk ka nyje fundit.
Por, le të thonë se lista nuk është e zbrazët.
Nëse nuk është, atëherë ne duhet të zvarritem nëpër gjithë listën
deri sa të kemi në nyjen e fundit të listës,
dhe se si mund të them nëse ne jemi duke kërkuar në nyjen e fundit në listë?
>> E pra, në qoftë se një nyje tjetër tregues është null,
ne e dimë se ne jemi në fund
pasi treguesin fundit ardhshme nuk do të ketë nyje tjetër në listë për pikë për të.
Është praktikë e mirë që gjithmonë të mbajnë treguesin e ardhshëm nyja kaluar initialized to null
të ketë një pronë të standardizuar e cila na paralajmëron kur ne kemi arritur në fund të listës.
>> Pra, në qoftë servil → tjetër është null,
mos harroni se sintaksa shigjetë është një shkurtore për dereferencing
një tregues për një struct, pastaj qasja në
Fusha e saj e ardhshme ekuivalente të vështirë:
(* Servil). Ardhshëm.
Pasi ne kemi gjetur nyjen e fundit,
ne duam të shtypura servil → Val,
vlera në nyjen e tanishme
të cilën ne e dimë është e fundit.
Përndryshe, në qoftë se ne nuk jemi ende në nyjen e fundit në listë,
ne duhet të lëvizin për në nyjen e ardhshëm në listë
dhe kontrolloni nëse kjo është e fundit.
Për ta bërë këtë, ne vetëm vënë treguesin tonë servil
të tregojnë për vlerën e ardhshëm nyjen aktual,
që është, nyje tjetër në lista.
Kjo është bërë duke
servil servil = → ardhshëm.
Pastaj ne përsëris këtë proces, me një lak për shembull,
derisa kemi gjetur nyjen e fundit.
Kështu, për shembull, në qoftë servil u treguar kokë,
ne kemi vendosur servil për pikë në servil → ardhshëm,
e cila është e njëjtë si fusha e ardhshëm të nyjen 1.
Pra, tani servil jonë është vënë në nyjen 2,
dhe, përsëri, ne përsëris këtë me një lak,
deri sa ne kemi gjetur nyjen e fundit, që është,
ku treguesin e ardhshëm nyja është duke treguar null.
Dhe nuk kemi atë,
ne kemi gjetur nyja e fundit në listë, dhe për të shtypur vlerën e saj,
ne vetëm përdorni servil → Val.
>> Traversing nuk është aq e keqe, por çfarë lidhje futur?
Lejon të thonë se ne duam të futur një numër të plotë në pozitën e 4
në një listë integer.
Kjo është në mes të nyjeve aktuale të 3 dhe 4.
Përsëri, ne duhet të kaloj nëpër listën e vetëm për
marrë në elementin 3, në një ne jemi duke futur pas.
Pra, ne kemi krijuar një tregues servil përsëri të kaloj nëpër lista,
kontrolloni nëse akrep tonë kokë është i pavlefshëm,
dhe në qoftë se kjo nuk është, pikë treguesin tonë servil në nyjen qendrore.
Pra, ne jemi në elementin 1.
Ne duhet të shkojmë përpara 2 elemente më shumë para se ne mund të futni,
kështu që ne mund të përdorni një për lak
int i = 1; i <3; i + +
dhe në çdo ripërsëritje e lak,
avancimin treguesin tonë servil përpara nga 1 nyjë
duke kontrolluar nëse fusha e ardhshëm nyja aktual është i pavlefshëm,
dhe në qoftë se kjo nuk është, lëvizin kursorin tonë servil në nyjen e ardhshëm
duke vendosur atë të barabartë me treguesin e ardhshëm nyjen aktual.
Pra, pasi lak thotë tonë për të bërë këtë
dy herë,
ne kemi arritur nyjen 3,
dhe një herë treguesin jonë servil ka arritur nyjen pas
të cilat ne duam të futur tonë të ri numër i plotë,
si nuk kemi të vërtetë të bëjë të futur?
>> E pra, integer tonë të ri duhet të futet në listën e
si pjesë e struct vet nyjeve,
pasi kjo është me të vërtetë një sekuencë e nyjeve.
Pra, le të bëjë një tregues të ri për nyje
quajtur 'new_node,'
dhe e vendosi atë në pikë të kujtesës që ne tani ndajë
në grumbull për nyjen vetë,
dhe sa memorie nuk kemi nevojë të ndajë?
E pra, përmasat e një nyje,
dhe ne duam të vendosur fushën e tij val me numër të plotë që ne duam të futur.
Le të themi, 6.
Tani, nyja përmban vlerën tonë numer i plote.
Është gjithashtu një praktikë e mirë për të nisja fushë tjetër nyjen ri
për pikë të pavlefshëm,
por tani çfarë?
>> Ne kemi për të ndryshuar strukturën e brendshme të listës
dhe pointers ardhshme të përfshira në listën ekzistuese të
Nyjet 3 dhe 4.
Që pointers ardhshme përcaktuar rendin e listës,
dhe që ne jemi futur nyje tonë të re
drejtë në mes të listës,
ajo mund të jetë pak i ndërlikuar.
Kjo është për shkak se, mos harroni, kompjuteri ynë
vetëm e di vendndodhjen e nyjeve në listën
për shkak të pointers ardhshme depozituara në nyjet e mëparshme.
Pra, në qoftë se ne ndonjëherë humbur gjurmët e ndonjë nga këto vende,
thonë se duke ndryshuar një nga pointers ardhshme në listën tonë,
për shembull, thonë se ne e ndryshuam
Fusha tjetër nyjen e 3
të tregojnë për disa nyje mbi këtu.
Ne do të jetë e fat, sepse ne nuk do të
keni ndonjë ide se ku mund të gjeni pjesën tjetër të listës,
dhe kjo është padyshim me të vërtetë e keqe.
Pra, ne duhet të jetë me të vërtetë të kujdesshëm në lidhje me urdhër
në të cilën ne të manipuluar pointers tonë të ardhshëm gjatë futje.
>> Pra, për të lehtësuar këtë, le të themi se
para 4 nyjet tona
janë quajtur A, B, C, dhe D, me shigjeta përfaqësojnë zinxhirin e pointers
që lidhin nyjet.
Pra, ne kemi nevojë për të futur nyje tonë të re
në mes nyjet C dhe D.
Është e rëndësishme për të bërë atë në mënyrë të drejtë, dhe unë do t'ju tregoj pse.
>> Le të shikojmë në mënyrë të gabuar për ta bërë atë më parë.
Hej, ne e dimë se nyja e re duhet të vijë menjëherë pas C,
kështu që le të vendosur treguesin e ardhshëm C
për pikë në new_node.
Të gjithë të drejtë, duket në rregull, ne vetëm duhet të përfundojë deri tani nga
bërë tjetër pikë nyjen ri akrep në D,
Por prisni, si mund ta bëni këtë?
E vetmja gjë që mund të na tregoni se ku D ishte,
ishte tregues tjetër ruajtur më parë në C,
por ne thjesht rishkroi atë treguesin
për pikë në nyjen e re,
kështu që ne nuk kemi asnjë ide se ku D është në kujtesë,
dhe ne kemi humbur pjesën tjetër të listës.
Nuk është e mirë në të gjitha.
>> Pra, si nuk kemi të bëjmë këtë të drejtë?
Së pari, treguesin e ardhshëm nyja ri në D.
Tani, të dyja të reja nyje dhe e C pointers ardhshme
janë treguar në të njëjtën nyjë, D,
por kjo është në rregull.
Tani ne mund të nxjerr në treguesin e ardhshëm C në nyjen e re.
Pra, ne kemi bërë këtë pa humbur asnjë të dhënë.
Në kodin, C është nyja e tanishme
se treguesin traversal servil është treguar,
dhe D është përfaqësuara nga nyje vuri tek nga fushë tjetër nyjen aktual,
ose servil → ardhshëm.
Pra, ne kemi parë të vendosur treguesin tjetër nyjen ri
për pikë në servil → ardhshëm,
njëjtën mënyrë kemi thënë tregues tjetër new_node duhet
pikës tek D në ilustrim.
Pastaj, ne mund të vendosni treguesin tjetër nyjen aktual
me nyje tonë të re,
ashtu si ne është dashur të presin në pikën C të new_node në vizatim.
Tani çdo gjë është në rregull, dhe ne nuk kemi humbur
gjurmët e çdo të dhëne, dhe ne kemi qenë në gjendje të vetëm
rrinë nyje tonë të ri në mes të listës
pa rindërtimin e gjithë gjë, ose edhe kalimi elemente
mënyrë ne do të duhej të me një grup të caktuar gjatësi.
>> Pra, listat e lidhura janë një bazë, por të rëndësishme, dinamike struktura të dhënat
të cilat kanë të dy avantazhet dhe disavantazhet
në krahasim me vargjeve dhe të dhënat e tjera të strukturave,
dhe siç është shpesh rasti në shkenca kompjuterike,
është e rëndësishme të dini se kur do të përdorin çdo mjet,
kështu që ju mund të zgjidhni mjet i duhur për punën e duhur.
>> Për më shumë praktikë, do të përpiqen për të shkruar funksionet
fshini nyjet nga një listë e lidhur -
mos harroni të jenë të kujdesshëm në lidhje me mënyrë në të cilën ju korrigjoj
pointers tuaj të ardhshëm për të siguruar që ju nuk do ta humbasin një pjesë të listës suaj -
ose një funksion për të numëruar nyjet në një listë të lidhura,
ose një argëtim, për të ndryshuar rendin e të gjitha nyjet në një listë të lidhura.
>> Emri im është Steinkamp Jackson, kjo është CS50.