>> [Muzika]
>> DOUG Lloyd: OK, kështu që në kjo pikë në kurs,
ne kemi mbuluar shumë bazat e C. Ne e dimë shumë rreth variablave, vargjeve,
pointers, të gjitha gjëra të mira.
Ata janë ndërtuar të gjitha llojet e për të parë si bazat,
por ne mund të bëjmë më shumë, e drejtë?
Ne mund të kombinohen gjëra së bashku në mënyra interesante.
>> Dhe kështu që le të bëjë këtë, le të fillojë të zgjerohet nga çfarë C na jep,
dhe të fillojnë për të krijuar të dhënat tona Strukturat Duke përdorur këto ndërtesë
blloqe së bashku për të bërë diçka të vërtetë të vlefshme, e dobishme.
Një mënyrë ne mund të bëjmë këtë është për të folur për koleksioneve.
Pra, deri tani ne kemi pasur një lloj të të dhënave Struktura për përfaqësimin koleksione
i pëlqen vlerat, vlera të ngjashme.
Kjo do të jetë një grup.
Ne kemi koleksionet e numrave të plotë, ose koleksionet e karaktereve dhe kështu me radhë.
>> Strukturat janë gjithashtu lloj i të dhënave Struktura për mbledhjen e informacionit,
por kjo nuk është për të mbledhur si vlera.
Kjo zakonisht mixes lloje të ndryshme të të dhënave së bashku në brendësi të një kuti vetme.
Por kjo nuk është vetë përdoret për të zinxhirit bashku
ose të lidhë së bashku ngjashme sende, si një grup.
Vargjeve janë të mëdha për element të kërkoni, por risjell
kjo është shumë e vështirë për të futur në një grup,
nëse ne jemi futur në fund të kësaj grup.
>> Dhe shembulli më i mirë unë kam për këtë është futje lloj.
Nëse ju kujtohet video të tonë në futje lloji,
nuk ishte një shumë e shpenzim i përfshirë në kesh
për të marr elemente, dhe zhvendoset ato nga rruga të përshtaten diçka
në mes të vektorit tuaj.
Vargjeve gjithashtu vuajnë nga një tjetër problem, e cila është e papërkulshmëri.
Kur ne të deklarojë një grup, ne të merrni një e shtënë në të.
Ne kemi marrë për të thënë, unë dua Kjo shumë elemente.
Mund të jetë 100, ajo mund të jetë 1000, ajo mund
të jetë x, ku x është një numër që përdoruesi na dha në një shpejtë apo në komandën
linjë.
>> Por ne vetëm të marrë një e shtënë në të, ne nuk do të marrë për të pastaj thonë oh, në të vërtetë unë
nevojiten 101, ose unë e nevojshme x plus 20.
Shumë vonë, ne kemi deklaruar tashmë array, dhe në qoftë se ne duam që të merrni 101 ose x
plus 20, ne duhet të deklarojnë një grup krejtësisht të ndryshme,
kopje të të gjitha elementet e vektorit mbi, dhe pastaj ne kemi mjaft.
Dhe çka nëse ne jemi gabim përsëri, çfarë në qoftë se ne fakt duhet 102, ose 40 x plus,
ne duhet të bëjmë këtë përsëri.
Pra, ata janë shumë të papërkulur për ndryshuar të dhënat tona,
por në qoftë se ne të kombinohen së bashku disa nga bazat që ne kemi tashmë
mësuar në lidhje me pointers dhe strukturave, në veçanti duke përdorur kujtesën dinamike
ndarja me malloc, ne mund të vënë këto pjesë së bashku
Për të krijuar një të dhëna të reja structure-- A veçmas të lidhura listë ne mund say--
që na lejon të rritet dhe tkurret një koleksion të vlerave
dhe ne nuk do të ketë ndonjë hapësirë ​​tretur.
>> Pra, përsëri, ne e quajmë këtë ide, ky nocion, një listë e lidhur.
Në veçanti, në këtë video ne jemi duke folur në lidhje me listën e lidhur në formë individuale,
dhe pastaj një tjetër video ne do të flasim Listat gati dyfish të lidhura, të cilat
është vetëm një variacion mbi një temë këtu.
Por një listë e lidhur në formë individuale është i përbërë nga nyje,
nyje vetëm duke qenë një term-- abstrakt kjo është vetëm diçka që unë jam duke e quajtur
kjo është një lloj i Struktura, në thelb, unë jam?
Vetëm duke shkuar për të thirrur atë një node-- dhe kjo nyjë ka dy anëtarë, ose dy fusha.
Ajo ka të dhëna, zakonisht një numër i plotë, një noton karakter,
ose mund të jetë një lloj tjetër të dhënat e që e keni definuar me një def tipit.
Dhe ai përmban një tregues për tjetër nyje e të njëjtit lloj.
>> Pra, ne kemi dy gjëra brenda kjo nyje, të dhëna dhe një akrep
në një tjetër nyje.
Dhe në qoftë se ju filloni për të kujtoj kjo, ju mund të mendoni për atë
si një zinxhir nyjet që janë të lidhura së bashku.
Ne kemi nyjen e parë, atë përmban të dhëna, dhe një akrep
në nyjen e dytë, e cila përmban të dhënave, dhe një tregues për nyjen e tretë.
Dhe kështu kjo është arsyeja pse ne e quajmë atë një listë e lidhur, ata janë të lidhura së bashku.
>> Çfarë e bën këtë të veçantë Struktura nyje të duken si?
E pra, nëse ju kujtohet nga video tonë në përcaktimin e llojeve me porosi, me tip def,
ne mund të përcaktojë një structure-- dhe shkruani përcaktojë një strukturë si kjo.
tyepdef struct sllist, dhe atëherë unë jam duke përdorur vlerën fjalën këtu në mënyrë arbitrare
për të treguar çdo lloj të dhënave me të vërtetë.
Ju mund të kalojë në një numër të plotë ose noton, ju mund të ketë çdo gjë që ju dëshironi.
Kjo nuk është e kufizuar për vetëm integers, apo diçka të tillë.
Pra, vlera është vetëm një arbitrare llojin e të dhënave, dhe pastaj një akrep
në një nyje e llojit të njëjtë.
>> Tani, ka një kapur pak këtu me përcaktimin e një strukture
kur kjo është një strukturë referues vetë.
Unë duhet të ketë një të përkohshme përmendur për strukturën e mia.
Në fund të ditës së Parë qartë dëshironi të telefononi atë
nyje SLL, kjo është në fund të fundit i ri përmendur një pjesë të përkufizimit tim tipit,
por unë nuk mund të përdorë nyjen sll në mes të kësaj.
Arsyeja është, unë nuk kam krijoi një lloj të quajtur sll nyje
deri sa unë goditi këtë pikë të fundit këtu.
Deri në atë moment, unë duhet të ketë një tjetër mënyrë për të referuar në këtë lloj të të dhënave.
>> Dhe kjo është një vetë referues lloj të të dhënave.
Ajo, s një lloj të dhënave të një strukturë që përmban një të dhënat,
dhe një tregues për një tjetër Struktura e të njëjtit lloj.
Kështu që unë duhet të jetë në gjendje për t'iu referuar ky lloj të dhëna të paktën përkohësisht,
kështu duke i dhënë asaj një të përkohshme Emri i struct sllist
lejon mua që të pastaj thonë se unë dua një treguesin në një tjetër sllist struct,
një yll struct sllist, dhe pastaj pasi unë e kam përfunduar definicionin,
Unë tani mund të telefononi ky lloj një nyje SLL.
>> Pra, kjo është arsyeja pse ju të shihni se ka një emër i përkohshëm këtu,
por një emër i përhershëm këtu.
Ndonjëherë ju mund të shihni përkufizimet e strukturës,
për shembull, që nuk janë të referues vetë, që
nuk kanë një emër Specifier këtu.
Ajo do të them vetëm typedef e strukturës, hapur mbajtëse kaçurrel dhe pastaj të përcaktuar atë.
Por nëse ju jeni struct është vetë referues, pasi kjo është,
ju duhet të specifikoni një Emri llojin e përkohshme.
Por në fund të fundit, tani që ne kemi bërë këtë,
ne vetëm mund t'i referohet këto nyje, këto njësi,
si nyje SLL për qëllime e pjesës tjetër të kësaj video.
>> Të gjithë të drejtë, kështu që ne e dimë se si për të Krijo një listë nyje lidhur.
Ne e dimë se si për të përcaktuar një nyje e lidhur listë.
Tani, në qoftë se ne jemi duke shkuar për të filluar përdorimin e tyre për të mbledhur informacion,
ka një çift i operacioneve ne duhet të kuptojnë dhe të punojnë me të.
Ne duhet të dimë se si për të krijuar një listë e lidhur nga ajri hollë.
Nëse nuk ka asnjë listë tashmë, ne duam të fillojë një të tillë.
Pra, ne duhet të jenë në gjendje për të krijuar një listë të lidhur,
ne kemi nevojë për siguri të kërkuar nëpër lista Lidhje
për të gjetur një element ne jemi duke kërkuar për të.
Ne duhet të jenë në gjendje për të futur gjëra të reja në listë,
ne duam listën tonë për të të jetë në gjendje të rritet.
Dhe në mënyrë të ngjashme, ne duam të jetë në gjendje për të fshirë nga gjërat listën tonë,
ne duam listën tonë për të të jetë në gjendje për të tkurret.
Dhe në fund të tonë programe, veçanërisht
në qoftë se ju kujtohet se ne jemi dinamike ndarjen e kujtesës
për të ndërtuar këto lista në mënyrë tipike, ne duam të lirë të gjithë që kujtesës
kur ne jemi duke bërë punuar me të.
Dhe kështu që ne duhet të jetë në gjendje të fshini një tërë listë e lidhur në një dështojnë bie poshtë.
Pra, le të shkojnë nëpër disa nga këto operacione
dhe se si ne mund të parashikoj ato, duke folur në kodin pseudokod specifike.
Pra, ne duam të krijojmë një i lidhur listë, kështu që ndoshta ne
duan për të përcaktuar një funksion me këtë prototip.
SLL yll nyje, të krijojë, dhe unë jam duke kaluar në një argument, disa të dhëna arbitrare
shkruani përsëri, e disa arbitrare lloj të të dhënave.
Por unë jam returning-- këtë funksion duhet të kthehuni tek unë një tregues, në një formë individuale
i lidhur nyje listë.
Përsëri, ne jemi duke u përpjekur për të krijuar një listë e lidhur nga ajri i hollë,
kështu që kam nevojë për një tregues për se lista kur unë jam bërë.
>> Pra, çfarë janë hapat përfshirë këtu?
E pra, gjëja e parë që unë jam do të bëni është dinamike
ndajë hapësirë ​​për një nyje të re.
Përsëri, ne jemi duke krijuar atë nga të hollë ajrit, kështu që ne kemi nevojë për hapësirë ​​malloc për të.
Dhe sigurisht, menjëherë pasi ne malloc,
ne gjithmonë kontrolloni për t'u siguruar që tonë pointer-- nuk kemi marrë prapa null.
Sepse në qoftë se ne të përpiqemi dhe respekt një tregues null,
ne jemi duke shkuar për të vuajnë një segfault dhe ne nuk duam që.
>> Pastaj ne duam për të mbushur në këtë fushë, ne duam të nisja fushën e vlerës
dhe nisja fushën e ardhshme.
Dhe pastaj ne duam to-- përfundimisht si Funksioni prototip indicates-- ne duam
për t'u kthyer një tregues për një nyje sll.
Pra, çfarë e bëjnë këtë të duket si vizualisht?
E pra, së pari ne jemi duke shkuar për dinamike ndajë hapësirë ​​për një nyje të re SLL,
kështu që ne malloc-- që është një përfaqësim pamor
e nyjës ne vetëm krijuar.
Dhe ne kontrolloni për t'u siguruar kjo nuk është null-- në këtë rast,
fotografia nuk do të ketë treguar deri në qoftë se ajo ishte null,
ne do të kishim dalë jashtë kujtesës, kështu që ne jemi të mirë për të shkuar atje.
Deri tani ne jemi në të hap C, nisja fushën e vlerës nyjet.
E pra, në bazë të këtij funksioni më kërkojnë, unë jam duke përdorur këtu,
duket si unë dua të kalojë në 6, Kështu që unë do 6 në fushën e vlerës.
Tani, nisja fushën e ardhshme.
E pra, çfarë jam unë do të bëj atje, nuk ka asgjë tjetër, të drejtë,
kjo është e vetmja gjë në listë.
Pra, çfarë është gjëja tjetër në listë?
>> Ajo nuk duhet të tregojnë për ndonjë gjë, e drejtë.
Nuk ka asgjë tjetër atje, kështu që ajo që është koncepti ne e dimë se është nothing--
pointers për asgjë?
Ajo duhet të jetë ndoshta ne duam për të vënë një tregues null atje,
dhe unë do të përfaqësojë null treguesin si vetëm një kuti të kuqe,
ne nuk mund të shkojmë më tutje.
Siç do të shohim pak më vonë, ne do të kemi përfundimisht zinxhirët
e shigjeta lidh këto nyje së bashku,
por kur ju goditi kuti të kuqe, kjo është null,
ne nuk mund të shkojmë më tutje, ky është fundi i listës.
>> Dhe së fundi, ne vetëm duam të kthehet një tregues për këtë nyje.
Pra, ne do të thërrasë atë të ri, dhe do të kthehet të reja
kështu që mund të përdoret në çfarëdo funksioni krijoi atë.
Kështu që nuk kemi shkuar, Ne kemi krijuar një formë individuale lidhur Lista nyje nga ajri i hollë,
dhe tani ne kemi një listë që ne mund të punojnë me të.
>> Tani, le të thonë se ne tashmë kanë një zinxhir të madh,
dhe ne duam të gjeni diçka në të.
Dhe ne duam një funksion që është duke shkuar të kthehen vërtetë apo e rreme, në varësi
nëse një vlerë ekziston në atë listë.
Një prototip funksion, ose Deklarata për këtë funksion,
mund të duket si this-- bool gjeni, dhe atëherë ne duam të kalojë në dy argumente.
>> E para, është një tregues për elementi i parë i lista e lidhur.
Kjo është në fakt diçka që ju do të gjithmonë duan të mbajnë gjurmët e,
dhe në fakt mund të jetë diçka që edhe ju vënë në një ndryshore globale.
Pasi ta keni krijuar një listë, ju gjithmonë, gjithmonë
duan të mbajnë gjurmët e shumë elementi i parë i lista.
Në këtë mënyrë ju mund t'i referohet të gjitha të tjera Elementet nga vetëm pas zinxhir,
pa pasur nevojë për të mbajtur pointers paprekur për çdo element të vetëm.
Ju vetëm duhet të mbajnë gjurmët e parë një në qoftë se ata janë të lidhur me zinxhirë të gjithë së bashku.
>> Dhe pastaj gjëja e dytë ne jemi duke kaluar në një herë
është në mënyrë arbitrare some-- çfarëdo lloji të dhëna ne jemi
në kërkim të ka brenda shpresojmë se një nga nyjet në listë.
Pra, çfarë janë hapat?
E pra, gjëja e parë që ne bëjmë është ne kemi krijuar një akrep transversale
duke vënë në kokë listat.
E pra, pse nuk e bëjmë këtë, ne tashmë kanë një akrep në krye listave,
pse nuk kemi vetëm të lëvizë se një rreth?
E pra, si unë vetëm i tha, është vërtet e rëndësishme për ne
që gjithmonë të mbajnë gjurmët e të Elementi i parë në listë.
Dhe kështu është në fakt më mirë për të krijuar një kopje të kësaj,
dhe të përdorin që të lëvizë kështu që ne kurrë aksidentalisht largohen, ose ne gjithmonë
kanë një akrep në një pikë që është drejtë në elementin e parë të lista.
Pra, është më mirë për të krijuar një e dyta që ne i përdorim për të lëvizur.
>> Atëherë ne vetëm nëse krahasojmë fusha vlera në atë nyje
është ajo që ne jemi duke kërkuar për të, dhe në qoftë se është jo, ne vetëm të shkojë në nyjen e ardhshëm.
Dhe ne të vazhdojmë të bëjmë atë mbi dhe mbi dhe mbi,
derisa ne ose të gjejnë element, ose ne hit
null-- ne kemi arritur fundin e listës dhe kjo nuk është atje.
Kjo duhet të shpresojmë se të telefononi një zile për ju si kërko vetëm lineare,
ne jemi vetëm përsëritur atë në një strukturë listë e lidhur në formë individuale
në vend të duke përdorur një rrjet për të bërë atë.
>> Kështu që këtu është një shembull i një listë e lidhur në formë individuale.
Kjo përbëhet nga pesë nyjet, dhe ne kemi
një tregues për kokën e të Lista, e cila është quajtur listë.
Gjëja e parë që ne duam të bëjmë është përsëri, krijuar atë treguesin traversal.
Pra, ne kemi tani dy pointers që tregojnë për të njëjtën gjë.
>> Tani, vini re edhe këtu, unë nuk e bëri duhet të malloc ndonjë hapësirë ​​për trav.
Unë nuk them trav barabartë malloc diçka, që nyjen tashmë ekziston,
se hapësira në kujtesë tashmë ekziston.
Pra, të gjitha unë jam në të vërtetë duke bërë është duke krijuar një tjetër tregues për të.
Unë nuk jam mallocing një shtesë hapësirë, vetëm të ketë tani dy pointers
duke treguar të njëjtën gjë.
>> Pra, është 2 ajo që unë jam duke kërkuar për?
E pra, nuk ka, kështu që në vend të kësaj unë jam do të shkojë në një tjetër.
Pra, në thelb unë do të thoja, Trav barabartë trav ardhshëm.
Është 3 atë që unë jam duke kërkuar për të, nr.
Kështu që unë të vazhdojë të shkojë përmes, deri në fund
merrni për 6 cila është ajo që unë jam duke kërkuar për të bazuar në thirrjen e funksionit
Unë kam në krye atje, dhe kështu që unë jam bërë.
>> Tani, çfarë nëse elementi unë jam kërkoni nuk është në listë,
po ajo ende do të punojë?
Mirë, vini re se lista këtu është Subtly të ndryshme,
dhe kjo është një tjetër gjë që është i rëndësishëm me listat e lidhura,
ju nuk keni për të ruajtur ata në asnjë mënyrë të veçantë.
Ju mund të qoftë se ju doni, por ju mund të keni vënë re tashmë
se ne nuk jemi duke e mbajtur gjurmët e çfarë numri element ne jemi në.
>> Dhe kjo është lloj i një tregti që ne kanë me listë të lidhura vargjet vargjeve,
është ajo që ne nuk kemi qasje të rastit më.
Ne nuk mund të themi thjesht, unë dua për të shkuar në elementin 0TH,
ose elementi 6 e array tim, që unë mund të bëjë në një grup.
Unë nuk mund të them se unë dua të shkoj të Element 0, ose element 6,
ose elementi i 25-të listën time të lidhur, nuk ka indeks të lidhur me to.
Dhe kështu që nuk ka rëndësi në qoftë se ne e ruajmë listën tonë në rregull.
Në qoftë se ju doni të ju me siguri mund të, por ka
ka arsye pse ata duhet të të ruhen në çdo mënyrë.
Pra, përsëri, le të përpiqen dhe gjeni 6 në këtë listë.
E pra, ne të fillojë në nivel fillim, ne nuk gjejmë 6,
dhe atëherë ne nuk vazhdojmë gjetur 6, deri sa ne përfundimisht të marrë në këtu.
Në mënyrë të drejtë pikë tani Trav në nyjen permbajtur 8, dhe gjashtë nuk është në atje.
>> Pra, hapi tjetër do të jetë për të shkuar në treguesin e ardhshëm,
kështu thonë Trav barabartë trav ardhshëm.
E pra, trav tjetër, tregohet nga kutia e kuqe atje, është i pavlefshëm.
Pra, nuk ka askund tjetër për të shkojnë, dhe kështu në këtë pikë
mund të konstatojmë se ne kemi arritur në fund të listës të lidhura,
dhe 6 nuk është në atje.
Dhe kjo do të kthehet rreme në këtë rast.
>> OK, si nuk kemi futur një të ri Nyja në listën e lidhur?
Pra, ne kemi qenë në gjendje për të krijuar një listë e lidhur nga askund,
por ne ndoshta dëshironi të të ndërtuar një zinxhir dhe jo
të krijojë një bandë e listave të dallueshme.
Ne duam të kemi një listë që ka një bandë e nyjeve në të,
jo një bandë e listave me një nyje të vetme.
Pra, ne nuk mund të mbajnë vetëm duke përdorur Krijo Funksioni ne përcaktuar më herët, tani ne
doni të futur në një listë që tashmë ekziston.
>> Pra këtë rast, ne jemi duke shkuar për të kaluar në dy argumente,
tregues në kokë e që lidhur listë që doni të shtoni në.
Përsëri, kjo është arsyeja pse është kaq e rëndësishme që ne gjithmonë
mbajnë gjurmët e saj, sepse kjo është e vetmja mënyrë me të vërtetë
duhet të referohen tërë lista është vetëm nga një tregues të elementit të parë.
Pra, ne duam të kalojë në një treguesin për këtë elementin e parë,
dhe çdo gjë që vlera ne doni të shtoni në listën.
Dhe përfundimisht ky funksion do të kthehet një akrep
të kreut të ri të një listë të lidhura.
>> Cilat janë hapat e përfshira këtu?
E pra, ashtu si me të krijuar, ne kemi nevojë për dinamike ndajë
hapësirë ​​për një nyje të re, dhe kontrolloni për të bërë sigurt se ne nuk do të dalë jashtë kujtesës, përsëri,
sepse ne jemi duke përdorur malloc.
Atëherë ne duam të populloj dhe futur nyjen,
kështu që vënë numrin, çfarëdo val është, në nyje.
Ne duam të futur nyjen në fillimi i listës lidhur.
>> Ka një arsye që unë duan për të bërë këtë, dhe kjo
mund të jetë me vlerë duke marrë një të dytë për pauzë video të këtu,
dhe mendoj se pse unë do të duan të futur në fillim të një i lidhur
lista.
Përsëri, unë përmenda më parë se ajo nuk ka të vërtetë
rëndësi nëse ne e ruajmë atë në ndonjë mënyrë, kështu që ndoshta kjo është një e dhënë.
Dhe ju e panë se çfarë do të ndodhte nëse ne donte to-- ose nga vetëm një sekondë
më parë, kur ne ishim duke shkuar përmes kërkimit të
mund të shohin se çfarë mund të të ndodhë në qoftë se ne ishim duke u përpjekur
për të futur në fund të lista.
Sepse ne nuk kemi një tregues për fund te lista.
>> Pra, arsyeja që unë do të duan për të futur në fillim,
është për shkak se unë mund ta bëjë këtë menjëherë.
Unë kam një akrep në fillim, dhe ne do të shohim këtë në një vizuale në një të dytë.
Por në qoftë se unë dua të futur në fund, Unë duhet të fillojë në fillim,
përshkojnë gjithë rrugës për në fund, dhe pastaj tack atë.
Kështu që do të thotë se futur në fund të lista
do të bëhet një o të n operacion, duke shkuar prapa
në diskutimin tonë të Kompleksiteti kompjuterike.
Ajo do të bëhet një o e operimit n, ku si lista mori të madhe, dhe më të mëdha,
dhe më të mëdha, ajo do të bëhet gjithnjë e më e vështirë për litar diçka
më në fund.
Por është gjithmonë vërtetë e lehtë për litar diçka në në fillim,
ju jeni gjithmonë në fillim.
>> Dhe ne do të shohim një vizuale të këtë përsëri.
Dhe pastaj një herë ne jemi duke bërë, dikur ne kemi futur nyjen e re,
ne duam të kthehen treguesin tonë për kreu i ri i një liste të lidhura, të cilat
që ne jemi futur në nivel duke filluar, në të vërtetë do të jetë
një tregues për nyjen ne vetëm krijuar.
Le të kujtoj këtë, sepse unë mendoj se kjo do të ndihmojë.
>> Kështu që këtu është lista jonë, ajo përbëhet nga katër elemente, një nyje që përmban 15,
i cili tregon në një nyje permbajtur 9, e cila
tregon për një nyje përmban 13, e cila tregon për një nyje që përmban
10, e cila ka null akrep si tregues të saj të ardhshëm
kështu që është fundi i listës.
Pra, ne duam të futur një nyje e re me vlerën 12
në fillim të kësaj lista, çfarë bëjmë ne?
E pra, së pari ne malloc hapësirë ​​për nyje, dhe pastaj ne kemi vënë 12 në atje.
>> Deri tani ne kemi arritur në një Pika vendim, e drejtë?
Ne kemi një çift të pointers që ne mund të
veprim, i cili duhet të ecim së pari?
A duhet të bëjë 12 pikë për të kreu i ri i list--
ose më falni, duhet të bëjmë 12 tregojnë për kreun e vjetër të listës?
Ose duhet të themi se Lista e tani fillon në 12.
Ka një dallim atje, dhe ne do të shikojmë
se çfarë ndodh me të dyja në një të dytë.
>> Por kjo çon në një temë e madhe për sidebar,
cilës është që një nga gjëra të mprehtë me listat e lidhura
është për të rregulluar pointers në mënyrë korrekte.
Në qoftë se ju të lëvizur gjërat nga e rendit, ju mund të përfundojnë aksidentalisht
orphaning pjesën tjetër të listës.
Dhe këtu është një shembull i kësaj.
Pra, le të shkojë me idenë of-- mirë, ne kemi krijuar vetëm 12.
Ne e dimë se 12 do të jetë kreu i ri i listës,
dhe kështu që pse nuk kemi vetëm të lëvizë Lista tregues për pikë atje.
>> OK, kështu që kjo është e mirë.
Deri tani ku ka 12 pikë tjetër?
Unë do të thotë, vizualisht ne mund të shohim që do pikë në 15,
si njerëzit është e vërtetë e qartë për ne.
Si e kompjuterit e di?
Ne nuk kemi asgjë duke treguar për 15 më, e drejtë?
>> Ne kemi humbur çdo aftësinë për t'iu referuar 15.
Ne nuk mund të themi shigjetë e re është e barabartë e ardhshme diçka, nuk ka asgjë atje.
Në fakt, ne kemi jetimë pjesa tjetër e listës
duke bërë kështu, ne kemi thyer aksidentalisht zinxhir.
Dhe ne me siguri nuk duan ta bëjnë këtë.
>> Pra, le të kthehemi dhe të provoni këtë përsëri.
Ndoshta gjëja e drejtë për të bërë është për të vendosur 12 për treguesin e ardhshme
të kreut të vjetër të listës së parë, atëherë ne mund të lëvizin listën e gjatë.
Dhe në fakt, se është mënyrë korrekte se ne
duhet të ndiqni kur ne jemi duke punuar me listën e lidhur në formë individuale.
Ne gjithmonë duam të lidhë element i ri në listë,
para se të marrë këtë lloj të hap i rëndësishëm i ndryshimit
ku kreu i listës është lidhur.
Përsëri, kjo është një gjë e tillë themelor, ne nuk duan të humbasin gjurmët e saj.
>> Pra, ne duam të sigurohemi që çdo gjë është e lidhur me zinxhirë së bashku,
para se të lëvizin atë treguesin.
Dhe kështu kjo do të jetë mënyrë korrekte, e cila është për të lidhur 12 në listë,
pastaj thonë se lista fillon një 12.
Nëse ne tha se lista fillon në 12 dhe pastaj u përpoq për të lidhur 12 në listë,
ne kemi parë tashmë se çfarë ndodh.
Kemi humbur listën gabimisht.
>> OK, kështu që një gjë më shumë për të folur rreth.
Çfarë ndodh nëse ne duam që të shpëtoj të një të tërë lidhur me listë në të njëjtën kohë?
Përsëri, ne jemi mallocing gjithë kjo hapësirë, dhe kështu që ne
nevojë për të liruar atë, kur ne jemi duke bërë.
Pra, tani ne duam të fshini të gjithë listë e lidhur.
E pra, çfarë duam të bëjmë?
>> Në qoftë se ne kemi arritur treguesin null, ne duan për të ndaluar, ndryshe, vetëm fshini
pjesa tjetër e listës dhe pastaj të lirë më.
Fshij pjesën tjetër të listës, dhe pastaj pa nyjen aktual.
Çfarë e bën atë të tingëllojë si, çfarë teknikë kemi biseduar
për më herët A tingëllon kjo si?
Fshij gjithë të tjerët, atëherë të kthehen dhe të fshini mua.
>> Kjo është recursion, ne kemi bërë Problemi pak më të vogël,
ne jemi duke thënë të fshini të gjithë tjetër, atëherë ju mund të fshini mua.
Dhe më tej poshtë rrugës, që nyje do të thotë, fshini gjithë të tjerët.
Por në fund ne do të merrni të Pika ku lista është i pavlefshëm,
dhe kjo është rasti ynë bazë.
>> Pra, le të marrin një vështrim në këtë, dhe se si kjo mund të punojnë.
Kështu që këtu është lista jonë, kjo është e njëjta lista ne ishim vetëm duke folur për,
dhe ka hapat.
Nuk është një shumë e tekstit këtu, por shpresojmë se vizualizimi do të ndihmojë.
>> Pra, ne have-- dhe unë gjithashtu u tërhoq up korniza rafte tonë ilustrim
nga video tonë në oxhaqet e thirrjes, dhe shpresojmë se e gjithë kjo
së bashku do të ju tregojnë se çfarë po ndodh.
Kështu që këtu është kodi ynë pseudokod.
Nëse arrijmë një null akrep, të ndaluar, ndryshe,
fshini pjesën tjetër të listës, pastaj pa nyjen aktual.
Deri tani, list-- tregues se ne jemi
duke kaluar në të shkatërrojë pikë për 12.
12 nuk është një tregues i pavlefshëm, kështu që ne jemi do të fshini pjesën tjetër të listës.
>> Çfarë fshirjes pjesa tjetër prej nesh të përfshirë?
E pra, kjo do të thotë duke bërë një thirrje për të shkatërruar, duke thënë:
se 15 është fillimi i Pjesa tjetër e listës ne duam për të shkatërruar.
Dhe kështu thirrja për të shkatërruar 12 është lloj i në pritje.
Është ngrirë atje, duke pritur për thirrje për të shkatërruar 15, për të përfunduar punën e saj.
>> E pra, 15 nuk është një tregues i pavlefshëm, dhe kështu ajo do të thotë, të gjithë të drejtë,
mirë, fshini pjesën tjetër të listës.
Pjesa tjetër e listës fillon në 9, dhe kështu që ne do të vetëm
prisni deri sa ju të fshini të gjithë atë gjëra, pastaj të kthehen dhe të fshini mua.
E pra 9 do të them, mirë, Unë nuk jam një tregues null,
kështu fshini pjesa tjetër e listës nga këtu.
Dhe kështu që të përpiqet dhe të shkatërrojë 13.
13 thotë, unë nuk jam akrep null, njëjta gjë, ai kalon dollar.
10 nuk është tregues i pavlefshëm, 10 përmban një tregues null,
por 10 nuk është në vetvete një null treguesin e drejtë tani,
dhe kështu ai kalon dollar shumë.
>> Dhe tani lista pikë atje, atë me të vërtetë do të tregojnë për some--
në qoftë se kam pasur më shumë hapësirë ​​në imazhin, kjo do të tregojnë për një hapësirë ​​të rastit
që ne nuk e dimë se çfarë është ajo.
Kjo është tregues null pse, lista është fjalë për fjalë vendosur tani është vlera null.
Është vënë të drejtë brenda asaj kutie të kuqe.
Ne kemi arritur në një tregues null, kështu ne mund të ndalojë, dhe ne jemi duke bërë.
>> Dhe kështu kjo kornizë purpurt është now-- në nivel krye të stack-- që është kornizë aktiv,
por kjo është bërë.
Në qoftë se ne kemi arritur në një tregues null, të ndaluar.
Ne nuk bëjmë asgjë, ne nuk mund të lirë një tregues null,
ne nuk malloc asnjë hapësirë, dhe kështu që ne jemi duke bërë.
Pra, atë kornizë funksionit është shkatërruar, dhe ne
resume-- ne të vini deri ku kemi lënë off me një tjetër më të lartë, i cili
është kjo kornizë blu të errët këtu.
Pra, ne të marr të drejtë ku ne u ndërpre.
Ne fshihet pjesa tjetër e Lista e tashmë, kështu që tani ne jemi
duke shkuar për të liruar nyjet aktuale.
Deri tani ne mund të lirë këtë nyje, dhe tani ne kemi arritur në fund të funksionit.
Dhe kështu që kornizë funksion është shkatërruar, dhe ne të marr në një dritë blu.
>> Pra, ajo që unë kam tashmë says-- done-- fshirjes pjesën tjetër të listës, kështu që
pa nyjen aktual.
Dhe tani kornizë e verdhë është përsëri në krye të rafte.
Dhe kështu siç e shihni, ne jemi tani shkatërruar listën nga djathta në të majtë.
>> Çfarë do të kishte ndodhur, edhe pse, nëse do të kishim bërë gjëra rrugën e gabuar?
Ashtu si kur ne u përpoqëm për të shtuar një element.
Nëse ne messed up zinxhir, nëse ne nuk lidhë pointers
në mënyrë korrekte, në qoftë se ne vetëm liruar elementin e parë,
në qoftë se ne vetëm liroi kreu i listës, tani ne
nuk kanë asnjë mënyrë për t'iu referuar pjesa tjetër e listës.
Dhe kështu ne do të kemi çdo gjë jetimë,
ne do të kishte çfarë është quajtur një rrjedhje kujtim.
Nëse ju kujtohet nga video tonë në ndarjen e kujtesës dinamike,
kjo nuk është gjë shumë e mirë.
>> Pra, siç thashë, aty disa operacione
që ne duhet të përdorim për të punuar me listën e lidhura në mënyrë efektive.
Dhe ju mund të keni vënë re unë lënë jashtë një, fshirjes një element të vetëm nga një i lidhur
lista.
Arsyeja që unë e bëri atë është në fakt lloj i
ndërlikuar për të menduar rreth asaj se si për të fshirë një element i vetëm nga një formë individuale
listë e lidhur.
Ne duhet të jenë në gjendje të kaloni mbi diçka në listë, e cila
do të thotë ne kemi marrë për një ne point-- dëshironi të fshini këtë node--
por në mënyrë për ta bërë atë kështu që ne nuk humbasin ndonjë informacion,
ne kemi nevojë për të lidhur këtë nyje këtu, këtu.
>> Kështu që unë ndoshta e bëri atë gabim nga një perspektivë vizuale.
Pra, ne jemi në fillim të tonë lista, ne jemi duke vazhduar përmes,
ne duam të fshini këtë nyje.
Nëse ne vetëm fshini atë, ne kemi thyer zinxhir.
Kjo nyje e drejtë këtu i referohet çdo gjë tjetër,
ai përmban zinxhir nga këtu në jashtë.
>> Pra, ajo që ne duhet të bëjmë në fakt pasi ne të merrni në këtë pikë,
është që ne duhet të hap prapa një, dhe lidhë këtë nyje mbi këtë nyje,
kështu që ne pastaj mund të fshini një në mes.
Por listat lidhura veçmas nuk na ofrojnë një mënyrë për të shkuar prapa.
Pra, ne kemi nevojë për të mbajtur ose dy pointers, dhe ata lëvizin
lloj i hap jashtë, një prapa tjetrin si ne do të shkojmë, ose të marrë në një pikë
dhe pastaj të dërguar një tjetër treguesin përmes.
Dhe si ju mund të shihni atë, mund të merrni një helaq pak.
Për fat të mirë, ne kemi një tjetër mënyrë për të zgjidhur atë,
kur flasim për listat lidhura dyfish.
>> Unë jam Doug Lloyd, kjo është CS50.