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