>> [Music kucheza]
DOUG LLOYD: zote haki.
Hivyo kama wewe tu kumaliza kwamba video katika orodha moja moja-zilizounganishwa pole
Mimi kushoto wewe mbali juu ya kidogo ya cliffhanger.
Lakini mimi nina furaha uko hapa kumaliza hadithi ya orodha doubly-wanaohusishwa.
>> Hivyo kama unakumbuka kutoka kuwa video, sisi aliyesema
kuhusu jinsi moja moja-zilizounganishwa orodha kufanya kuhudhuria uwezo wetu
kukabiliana na maelezo ambapo idadi ya vipengele
au idadi ya vitu katika orodha inaweza kukua au kuogopa.
Sasa tunaweza kukabiliana na kitu kama hicho, ambapo
sisi hakuweza kukabiliana nayo na arrays.
>> Lakini hawana wanakabiliwa na moja kiwango cha juu muhimu ambayo
ni kwamba pamoja na mmoja--wanaohusishwa orodha, tunaweza milele tu hoja
katika mwelekeo mmoja kupitia orodha.
Na hali halisi tu ambapo ambazo zinaweza kuwa tatizo
Ilikuwa wakati sisi walikuwa wakijaribu kufuta kipengele moja.
Na hatukuwa hata kujadili jinsi ya kufanya hivyo katika orodha moja moja-zilizounganishwa katika pseudocode.
Ni hakika doable, lakini inaweza kuwa kidogo ya Hassle.
Hivyo kama wewe mwenyewe kupata katika hali ambapo
wewe ni kujaribu kufuta mambo moja kutoka kwenye orodha
au ni kwenda inatakiwa kuwa wewe utakuwa kufuta
mambo moja kutoka orodha, unaweza kutaka
kufikiria kutumia mara mbili-wanaohusishwa orodha badala ya orodha moja moja-zilizounganishwa.
Kwa sababu orodha doubly-wanaohusishwa kuruhusu kwa hoja mbele na nyuma wote
kupitia orodha badala ya tu mbele kupitia list--
tu kwa kuongeza kipengele moja ya ziada kwa mfumo wetu ufafanuzi
kwa mara mbili-wanaohusishwa orodha nodi.
>> Tena, kama wewe si kwenda kwa kuwa kufuta vipengele moja
kutoka list-- kwa sababu sisi ni kuongeza uwanja wa ziada kwa mfumo wetu
ufafanuzi, nodes wenyewe kwa orodha doubly-wanaohusishwa
ni kwenda kuwa kubwa.
Wao ni kwenda kuchukua up ka zaidi ya kumbukumbu.
Na hivyo kama hii si kitu wewe ni kwenda haja ya kufanya,
unaweza kuamua ni si thamani biashara mbali
kwa kuwa na kutumia ziada ka ya kumbukumbu inahitajika
kwa orodha doubly-wanaohusishwa kama wewe si kwenda kuwa kufuta mambo moja.
Lakini wao uko pia baridi kwa mambo mengine pia.
>> Hivyo kama nilivyosema, sisi tu na kuongeza shamba moja ili mfumo wetu
definition-- wazo hili ya pointer Kabla.
Hivyo, pamoja na orodha moja moja-zilizounganishwa, sisi kuwa na thamani na ujao pointer,
hivyo orodha doubly-wanaohusishwa tu ana njia ya hoja nyuma pia.
>> Sasa katika moja moja-zilizounganishwa orodha ya video, sisi aliyesema
kuhusu hizi ni tano ya mambo kuu unahitaji kuwa
uwezo wa kufanya kazi na orodha wanaohusishwa.
Na kwa zaidi ya haya, ukweli kuwa ni orodha doubly-wanaohusishwa
ni kweli si kuruka kubwa.
Bado tunaweza kutafuta njia na tu kusonga mbele kuanzia mwanzo hadi mwisho.
Bado tunaweza kujenga nodi nje ya hewa nyembamba, pretty much njia hiyo hiyo.
Tunaweza kufuta orodha pretty njia ile ile pia.
Mambo tu kwamba ni subtly tofauti,
kweli, ni kuingiza nodes mpya katika orodha,
na tutaweza hatimaye majadiliano juu ya kufuta kipengele moja kutoka kwenye orodha pia.
Tena, pretty much wengine watatu, tuko
si kwenda kuzungumza kuhusu wao sasa hivi kwa sababu wao ni tu
tweaks madogo sana juu ya mawazo yaliyojadiliwa katika moja moja-zilizounganishwa orodha video.
>> Basi hebu kuingiza nodi mpya ndani ya orodha doubly-wanaohusishwa.
Kuongelea kufanya hivyo kwa mmoja--wanaohusishwa orodha kama vizuri,
lakini kuna michache ya ziada upatikanaji wa samaki na orodha doubly-wanaohusishwa.
Tuko [? kupita?] katika kichwa cha orodha hapa na baadhi thamani holela,
na tunataka kupata kichwa mpya ya orodha nje ya kazi hii.
Hiyo ni kwa nini kuirudisha nyota dllnode.
Hivyo hatua ni nini?
Wao ni, tena, ni sawa kwa moja moja-zilizounganishwa orodha
na kuongeza moja ya ziada.
Tunataka kutenga nafasi kwa mwezi nodi na kuangalia kwa kuhakikisha ni halali.
Tunataka kujaza kwamba nodi up kwa taarifa zozote sisi
wanataka kuweka ndani yake.
Jambo la mwisho tunahitaji do-- Jambo ziada tunahitaji kufanya, rather--
ni kurekebisha pointer Kabla ya kichwa na umri wa orodha.
Kumbuka kwamba kwa sababu orodha ya mara mbili-wanaohusishwa,
tunaweza kusonga mbele na backwards-- ambayo
maana yake ni kwamba kila node kweli anasema kwa nodes nyingine mbili badala ya moja tu.
Na hivyo tunahitaji kurekebisha kichwa zamani ya orodha
kwa kumweka nyuma kwa mkuu mpya wa orodha wanaohusishwa, ambayo ilikuwa ni kitu
hatukuwa na kufanya kabla.
Na kama kabla, sisi tu kurudi pointer kwa mkuu mpya wa orodha.
>> Hivyo hapa ni orodha.
Tunataka kuingiza 12 katika orodha hii.
Taarifa kwamba mchoro ni tofauti kidogo.
Kila nodi ina tatu fields-- data, na pointer Next katika nyekundu,
na pointer Kabla ya bluu.
Kitu huja kabla ya 15 nodi, hivyo pointer wake Kabla ni null.
Ni mwanzo wa orodha.
Kuna kitu kabla yake.
Na hakuna kitu huja baada ya 10 nodi, na hivyo ni Ifwatayo pointer ni null vilevile.
>> Basi hebu kuongeza 12 kwa orodha hii.
Tunahitaji [inaudible] nafasi kwa ajili ya nodi.
Sisi kuweka 12 ndani yake.
Na kisha tena, tunahitaji kuwa kweli makini kwa kuvunja minyororo.
Tunataka upya kuyatumia katika mpangilio sahihi.
Na wakati mwingine ambao unaweza mean kama tutaweza kuona hasa
na delete-- kwamba sisi kufanya kuwa na baadhi kutokuwa na maana kuyatumia, lakini hiyo ni sawa.
>> Basi je, tunataka kufanya kwanza?
Napenda kupendekeza mambo unapaswa pengine
kufanya ni kujaza kuyatumia ya 12 nodi kabla ya kugusa mtu yeyote mwingine.
Kwa hiyo kile ni 12 kwenda kwa uhakika na baada ya hapo?
15.
Nini huja kabla ya 12?
Chochote.
Sasa tumekuwa kujazwa maelezo ya ziada katika 12
hivyo ina Kabla, Next, na thamani.
>> Sasa tunaweza kuwa 15-- hii ya ziada hatua sisi walikuwa wanazungumza about-- sisi
unaweza kuwa na 15 hatua nyuma 12.
Na sasa tunaweza kusonga kichwa cha orodha wanaohusishwa na pia kuwa 12.
Hivyo ni pretty sawa na kile sisi walikuwa wakifanya na orodha moja moja-zilizounganishwa,
isipokuwa kwa hatua za ziada ya kuunganisha kichwa na umri wa orodha
nyuma kwa mkuu mpya wa orodha.
>> Sasa hebu hatimaye kufuta nodi kutoka orodha wanaohusishwa.
Hivyo hebu sema tuna baadhi ya kazi nyingine ambazo
ni kutafuta nodi sisi unataka kufuta naye ametupa pointer hasa
nodi kwamba tunataka kufuta.
Hatuwezi hata need-- kusema kichwa bado ni duniani alisema.
Hatuna haja ya kichwa hapa.
Wote kazi hii ni kufanya ni tumekuwa kupatikana pointer nodi sisi hasa
wanataka kujikwamua.
Hebu kujikwamua ni.
Ni rahisi sana kwa doubly-wanaohusishwa orodha.
First-- ni kweli michache tu mambo.
Sisi tu haja ya kurekebisha jirani nodes 'kuyatumia ili waweze ruka juu
nodi sisi unataka kufuta.
Na kisha tunaweza kufuta nodi.
Hivyo tena, tunakwenda tu kupitia hapa.
Tuna inaonekana aliamua kwamba tunataka kufuta nodi X.
Na tena, nini mimi nina kufanya here-- na way--
ni kesi ya jumla kwa nodi ulio katikati.
Kuna michache ya tahadhari za ziada kwamba wewe
haja ya kufikiria wakati wewe ni kufuta mwanzo wa orodha
au mwisho wa orodha.
Kuna michache ya pekee kona kesi ya kukabiliana na pale.
>> Hivyo hii kazi kwa kufuta nodi yoyote katikati ya moja list-- kwamba
ina pointer halali mbele na pointer halali nyuma,
halali Kabla na Next pointer.
Tena, kama wewe ni kufanya kazi na mwisho, wewe
haja ya kushughulikia wale kidogo tofauti,
na sisi siyo kwenda kwa majadiliano juu ya kwamba sasa.
Lakini pengine unaweza kufikiri nini mahitaji
kufanywa tu kwa kuangalia hii video.
>> Hivyo tumekuwa kutengwa X. X ni nodi tunataka kufuta kutoka kwenye orodha.
Tufanye nini?
Kwanza, tunahitaji upya nje kuyatumia.
Tunahitaji upya 9 ya karibu na ruka juu 13
na hatua kwa 10-- ambayo ni kile ambacho tumefanya tu.
Na sisi pia haja ya upya 10 wa awali
kwa uhakika na 9 badala ya akizungumzia 13.
>> Hivyo tena, hii ilikuwa mchoro kuanza na.
Hii ilikuwa ni mlolongo wetu.
Tunahitaji ruka juu 13, lakini tunahitaji pia kuhifadhi
uadilifu wa orodha.
Hatutaki kupoteza yoyote habari katika mwelekeo aidha.
Kwa hiyo, tunahitaji upya kuyatumia kwa uangalifu
hivyo hatuna kuvunja minyororo wakati wote.
>> Hivyo tunaweza kusema 9 Next pointer anazungumzia sehemu moja
kuwa kumi na tatu Next pointer anasema hivi sasa.
Kwa sababu tuko hatimaye atataka ruka juu 13.
Hivyo popote pointi 13 ijayo, wanataka tisa kwa uhakika kuna badala yake.
Hivyo hiyo ni kwamba.
Na kisha popote pointi 13 nyuma kwa, chochote huja kabla ya 13,
tunataka 10 kwa uhakika kwa kuwa badala ya 13.
Sasa angalia, kama wewe kufuata mishale, tunaweza kuacha 13
bila ya kweli ya kupoteza taarifa yoyote.
Tumekuwa naendelea uadilifu wa orodha, kusonga wote mbele na nyuma.
Na kisha tunaweza aina tu ya safi it up kidogo
kwa kuunganisha orodha pamoja.
Kwa hiyo sisi upya kuyatumia upande.
Na kisha sisi huru X nodi kwamba zilizomo 13,
na hatukuwa kuvunja minyororo.
Hivyo tulifanya vizuri.
>> Mwisho kumbuka hapa katika orodha wanaohusishwa.
Hivyo wote singly- na doubly-wanaohusishwa orodha, kama tumeona,
msaada kweli ufanisi kuingizwa na kufutwa kwa vipengele.
Unaweza pretty much kufanya hivyo kwa wakati mara kwa mara.
Je, sisi kufanya kufuta kipengele tu ya pili iliyopita?
Sisi wakiongozwa pointer moja.
Sisi wakiongozwa pointer mwingine.
Sisi huru X-- alichukua shughuli tatu.
Ni daima inachukua shughuli tatu kwa kufuta kwamba node-- kwa bure nodi.
>> Je, sisi kuingiza?
Naam, tuko tu siku zote bisho juu ya mwanzo
kama sisi ni kuingiza kwa ufanisi.
Kwa hiyo, tunahitaji rearrange-- kutegemea kama ni
singly- au mara mbili-wanaohusishwa orodha, tupate haja ya kufanya tatu
au shughuli nne max.
Lakini tena, mara nyingi ni tatu au nne.
Haijalishi jinsi wengi mambo ni katika orodha yetu,
mara nyingi ni watatu au wanne operations-- kama kufutwa daima
tatu au nne shughuli.
Ni wakati wa mara kwa mara.
Hivyo hiyo ni kubwa kweli kweli.
>> Na arrays, tunafanya kitu kama kuingizwa aina.
Pengine unakumbuka kwamba kuingizwa aina si mara kwa mara wakati algorithm.
Ni kweli pretty ghali.
Hivyo hii ni mengi zaidi kwa ajili ya kuingiza.
Lakini kama nilivyoeleza katika mmoja--wanaohusishwa orodha video,
sisi tumepewa upande wa chini hapa pia, sawa?
Tumekuwa kupoteza uwezo wa nasibu kupata vipengele.
Hatuwezi kusema, nataka kipengele namba nne au kipengele namba 10 ya orodha wanaohusishwa
njia ile ile ambayo tunaweza kufanya hivyo kwa safu
au tunaweza tu moja kwa moja ripoti ndani ya kipengele safu yetu.
>> Na hivyo kujaribu kupata kipengele katika list-- wanaohusishwa
kama kutafuta ni important-- Huenda sasa kuchukua muda linear.
Kama orodha anapata tena, ni inaweza kuchukua hatua moja zaidi
kwa kila kipengele moja katika orodha katika Ili kupata nini sisi ni kuangalia kwa.
Hivyo kuna awamu ya pili ya biashara.
Kuna kidogo ya wanaounga mkono na con kipengele hapa.
>> Na orodha doubly-wanaohusishwa si aina ya mwisho ya muundo wa data macho
kwamba tutaweza majadiliano juu, kuchukua jengo yote ya msingi
vitalu ya C kuweka pamoja.
Kwa sababu kwa kweli, tunaweza hata kufanya vizuri zaidi kuliko huu
kujenga muundo data kwamba unaweza kuwa na uwezo wa kutafuta njia ya
katika wakati mara kwa mara pia.
Lakini zaidi juu ya kwamba katika video nyingine.
>> Mimi nina Doug Lloyd.
Hii ni CS50.