[Powered by Google Translate] Katika programu, sisi mara nyingi haja ya kuwakilisha orodha ya maadili,
kama vile majina ya wanafunzi katika sehemu
au alama zao juu ya chemsha bongo karibuni.
>> Katika lugha ya C, alitangaza arrays inaweza kutumika
kuhifadhi orodha.
Ni rahisi enumerate mambo ya orodha
kuhifadhiwa katika safu, na kama unahitaji kupata
au kurekebisha idh orodha ya kipengele
kwa baadhi index holela mimi,
ambayo yanaweza kufanyika katika muda wa mara kwa mara,
lakini arrays na hasara, pia.
>> Wakati sisi kutangaza yao, sisi ni required kusema
juu mbele jinsi kubwa wao ni,
kwamba ni, jinsi wengi vipengele kwani inaweza kuhifadhi
na jinsi kubwa haya mambo ni, ambayo ni kuamua na aina yao.
Kwa mfano, int arr (10)
unaweza kuhifadhi vitu 10
kwamba ni ukubwa wa int.
>> Hatuwezi kubadilisha ukubwa safu baada ya tamko.
Tuna kufanya safu mpya kama tunataka kuhifadhi vipengele zaidi.
sababu kiwango cha juu hii ni kwamba ipo wetu
mpango maduka safu nzima
kama chunk contiguous ya kumbukumbu.
Sema hii ni buffer ambapo sisi kuhifadhiwa katika safu yetu.
Kunaweza kuwa na vigezo vingine
iko haki ya karibu na safu
katika kumbukumbu, hivyo hatuwezi
tu kufanya safu kubwa.
>> Wakati mwingine tunatarajia biashara safu ya data haraka upatikanaji kasi
kwa kubadilika kidogo zaidi.
Weka orodha wanaohusishwa, mwingine msingi data muundo
unaweza kuwa kama ukoo na.
Katika ngazi ya juu,
orodha wanaohusishwa maduka data katika mlolongo wa nodi
kwamba ni kushikamana na kila mmoja kwa viungo,
hivyo jina 'wanaohusishwa orodha.'
Kama tutaweza kuona, tofauti hii katika kubuni
inaongoza kwa faida tofauti na hasara
kuliko safu.
>> Hapa ni baadhi ya kanuni C kwa orodha rahisi sana wanaohusishwa ya integers.
Unaweza kuona kwamba tuna kuwakilishwa kila nodi
katika orodha kama struct ambayo ina mambo 2,
integer kuhifadhi iitwayo 'Val'
na kiungo na nodi ijayo katika orodha
ambayo sisi kuwakilisha kama pointer iitwayo 'ijayo.'
Kwa njia hii, tunaweza kufuatilia orodha nzima
na tu pointer moja na nodi ya 1,
na kisha tunaweza kufuata kuyatumia ijayo
na nodi ya 2,
na nodi ya 3,
na nodi ya 4,
na kadhalika, mpaka sisi kupata mwisho wa orodha.
>> Unaweza kuwa na uwezo wa kuona 1 faida hii ina
juu ya muundo tuli safu - na orodha wanaohusishwa,
hatuhitaji chunk kubwa ya kumbukumbu kabisa.
Nodi 1 ya orodha anaweza kuishi katika eneo hili katika kumbukumbu,
na node ya 2 inaweza kuwa njia yote juu hapa.
Tunaweza kupata nodes wote bila kujali ambapo katika kumbukumbu wao,
kwa sababu kuanzia saa 1 nodi, kila nodi ya pointer ijayo
inatuambia hasa ambapo kwenda ijayo.
>> Zaidi ya hayo, hatuna kusema juu mbele
jinsi kubwa orodha wanaohusishwa itakuwa njia sisi kufanya na arrays tuli,
tangu tunaweza kuendelea kuongeza vitengo na orodha
muda mrefu kama kuna nafasi mahali fulani katika kumbukumbu kwa nodes mpya.
Kwa hiyo, orodha zilizounganishwa ni rahisi resize dynamically.
Sema, baadaye katika mpango tunahitaji kuongeza nodes zaidi
katika orodha yetu.
Insert nodi mpya katika orodha yetu juu ya kuruka,
wote sisi kufanya ni kutenga kumbukumbu kwa nodi kwamba,
plop katika thamani data,
na kisha kuiweka ambapo tunataka kwa kurekebisha kuyatumia mwafaka.
>> Kwa mfano, kama sisi akataka kuweka nodi katika kati ya
Nodes 2 na 3 ya orodha,
tunataka kuwa na hoja nodes 2 au 3 wakati wote.
Sema tuko inserting hii nodi nyekundu.
Wote tunatarajia kufanya ni kuweka nodi mpya ijayo pointer
kwa uhakika na nodi 3
na kisha rewire nodi 2 ijayo pointer
kwa uhakika na nodi wetu mpya.
Hivyo, tunaweza resize orodha yetu juu ya kuruka
tangu kompyuta yetu haina kutegemea Indexing,
lakini badala ya kuunganisha kwa kutumia kuyatumia na kuhifadhi yao.
>> Hata hivyo, hasara ya wanaohusishwa orodha
ni kwamba, tofauti na safu tuli,
kompyuta hawezi tu Rukia katikati ya orodha.
Tangu kompyuta ina kutembelea kila nodi katika orodha wanaohusishwa
kupata moja ijayo,
itakavyo kuchukua muda mrefu kupata nodi fulani
kuliko ingekuwa katika safu.
Ili traverse orodha nzima inachukua muda sawia
kwa urefu wa orodha,
au O (n) katika nukuu asymptotic.
Kwa wastani, na kufikia yoyote nodi
Pia inachukua muda sawia na n.
>> Sasa, hebu kweli kuandika baadhi ya kanuni
kwamba kazi na orodha zinazoungwa.
Hebu sema tunataka orodha ya wanaohusishwa integers.
Tunaweza kuwakilisha nodi katika orodha yetu tena
kama struct pamoja na mashamba ya 2,
thamani integer iitwayo 'Val'
na pointer ijayo na nodi ijayo ya orodha.
Naam, inaonekana rahisi kutosha.
>> Hebu sema tunataka kuandika kazi
ambayo yanapopita orodha prints na nje
thamani kuhifadhiwa katika nodi mwisho wa orodha.
Naam, hiyo ina maana sisi itabidi traverse nodes wote katika orodha
kupata moja ya mwisho, lakini tangu sisi siyo kuongeza
au kufuta chochote, hatutaki kubadili
muundo wa ndani ya kuyatumia ijayo katika orodha.
>> Hivyo, sisi itabidi pointer mahsusi kwa ajili ya traversal
ambayo tutaweza kuwaita 'crawler.'
Itakuwa kutambaa kupitia mambo yote ya orodha
kwa kufuata mlolongo wa kuyatumia ijayo.
Wote tuna kuhifadhiwa ni pointer nodi 1,
au 'kichwa' cha orodha.
Kichwa pointi na nodi ya 1.
Ni aina ya pointer-kwa-nodi.
>> Ili kupata halisi 1 nodi katika orodha,
tuna dereference hii pointer,
lakini kabla tunaweza dereference hiyo, tunahitaji kuangalia
ikiwa ni pointer null kwanza.
Kama ni null, orodha ni tupu,
na sisi lazima magazeti ujumbe kwamba, kwa sababu orodha ni tupu,
hakuna nodi mwisho.
Lakini, hebu sema orodha si tupu.
Kama siyo, basi tunapaswa kutambaa kupitia orodha nzima
mpaka sisi kupata nodi mwisho wa orodha,
na jinsi gani tunaweza kujua kama sisi ni kuangalia kwenye nodi mwisho katika orodha?
>> Naam, kama nodi ya pointer ijayo ni null,
tunajua tuko mwishoni
tangu mwisho pointer ijayo ingekuwa hakuna nodi ijayo katika orodha kwa uhakika na.
Ni vizuri mazoezi ya daima kuweka nodi mwisho ijayo pointer initialized kwa null
kuwa na mali sanifu ambayo alerts yetu wakati sisi Umefikia mwisho wa orodha.
>> Hivyo, kama crawler → ijayo ni null,
kukumbuka kwamba syntax mshale ni njia ya mkato kwa dereferencing
pointer struct, kisha kupata
uwanja wake ijayo sawa na Awkward:
(* Crawler) ijayo..
Mara sisi Nimepata nodi ya mwisho,
tunataka magazeti crawler → Val,
thamani katika nodi sasa
ambayo sisi kujua ni moja ya mwisho.
Vinginevyo, kama sisi ni bado nodi katika mwisho katika orodha,
tuna kuhamia kwenye nodi ijayo katika orodha
na kuangalia kama hiyo ni moja ya mwisho.
Ili kufanya hivyo, sisi tu kuweka crawler wetu pointer
kwa uhakika na thamani ya sasa ya nodi ijayo,
kwamba ni, nodi ijayo katika orodha.
Hii ni kufanyika kwa kuweka
crawler = crawler → ijayo.
Kisha sisi kurudia utaratibu huu, kwa kitanzi kwa mfano,
mpaka tunapata nodi mwisho.
Hivyo, kwa mfano, kama crawler alikuwa akizungumzia kichwa,
sisi kuweka crawler kwa uhakika na crawler → ijayo,
ambayo ni sawa na shamba ya pili ya nodi 1.
Hivyo, sasa crawler yetu ni akizungumzia nodi 2,
na tena, sisi kurudia hili na kitanzi,
mpaka tumekuwa kupatikana nodi ya mwisho, yaani,
ambapo nodi ya pointer ijayo ni akizungumzia null.
Na kuna sisi kuwa nayo,
tumekuwa kupatikana nodi mwisho katika orodha, na magazeti ya thamani yake,
sisi tu kutumia crawler → Val.
>> Traversing si mbaya, lakini nini kuhusu inserting?
Inakuwezesha kusema tunataka Insert integer katika nafasi 4
katika orodha integer.
Hiyo ni kati ya pingili sasa 3 na 4.
Tena, tuna traverse orodha tu kwa
kupata kipengele 3, moja baada ya sisi ni kuingiza.
Hivyo, sisi kujenga pointer crawler tena traverse orodha,
kuangalia kama kichwa wetu pointer ni null,
na kama si, elekezeni crawler wetu pointer nodi katika kichwa.
Hivyo, sisi ni saa ya kipengele 1.
Tuna kwenda mbele 2 vipengele zaidi kabla tunaweza kuingiza,
ili tuweze kutumia kwa kitanzi
int i = 1; i <3; i + +
na katika kila iteration ya kitanzi,
kuendeleza crawler wetu pointer mbele na nodi 1
kwa kuangalia kama nodi ya sasa ya uwanja ijayo ni null,
na kama si, hoja crawler wetu pointer nodi ijayo
kwa kuweka ni sawa na pointer nodi ya sasa ijayo.
Hivyo, tangu kitanzi yetu kwa kufanya anasema kwamba
mara mbili,
tumekuwa kufikiwa nodi 3,
na mara moja crawler wetu pointer umefikia nodi baada ya
ambayo tunataka Insert integer wetu mpya,
jinsi gani sisi kwa kweli inserting?
>> Naam, integer wetu mpya ina kuwa na kuingizwa katika orodha
kama sehemu ya struct yake mwenyewe nodi,
tangu hii ni kweli mlolongo wa mikutano ya nodi.
Hivyo, wacha kufanya pointer mpya na nodi
iitwayo 'new_node,'
na kuliweka kwa uhakika na kumbukumbu kwamba sisi sasa kutenga
juu ya magofu nodi yenyewe,
na kiasi gani kumbukumbu tunahitaji kutenga?
Naam, na ukubwa wa nodi,
na tunataka kuweka Val yake shamba kwa integer kwamba tunataka Insert.
Hebu sema, 6.
Sasa, nodi ina thamani yetu integer.
Ni vizuri pia mazoezi initialize nodi mpya ijayo shamba
na kumweka kwa null,
lakini sasa nini?
>> Sisi kuwa na mabadiliko ya muundo wa ndani wa orodha
na kuyatumia ijayo zilizomo katika orodha ya zilizopo
3 na 4 nodi.
Tangu kuyatumia ijayo kuamua utaratibu wa orodha,
na tangu tuko inserting nodi wetu mpya
haki ndani ya katikati ya orodha,
inaweza kuwa kidogo Tricky.
Hii ni kwa sababu, kumbuka, kompyuta yetu
tu anajua mahali ya nodes katika orodha
kwa sababu ya kuyatumia ijayo kuhifadhiwa katika nodes uliopita.
Hivyo, kama sisi milele waliopotea track ya yoyote ya maeneo haya,
kusema kwa kubadilisha moja ya kuyatumia ijayo katika orodha yetu,
kwa mfano, wanasema sisi iliyopita
Nodi 3 ijayo shamba
kwa uhakika na baadhi nodi zaidi ya hapa.
Tunatarajia kuwa nje ya bahati, kwa sababu sisi hakutaka
kuwa na wazo lolote ambapo kupata mapumziko ya orodha,
na kwamba ni wazi mbaya kweli kweli.
Hivyo, sisi kuwa makini juu ya kweli ili
ambayo sisi kuendesha yetu kuyatumia ijayo wakati wa kuingizwa.
>> Hivyo, ili kurahisisha hii, hebu kusema kwamba
4 wetu wa kwanza nodes
wanaitwa, B, C, na D, na mishale anayewakilisha mlolongo wa kuyatumia
kwamba kuungana nodi.
Hivyo, tunahitaji kuingiza nodi wetu mpya
katika kati ya pingili C na D.
Ni muhimu kufanya hivyo ili haki, na mimi nitakuonyesha nini.
>> Hebu tuangalie njia sahihi ya kufanya hivyo kwanza.
Hey, tunajua nodi mpya ina kuja haki baada ya C,
hivyo hebu kuweka C ijayo pointer
kwa uhakika na new_node.
Haki zote, inaonekana sawa, sisi tu kumaliza up sasa na
kufanya nodi mpya ijayo pointer uhakika na D,
lakini kusubiri, ni jinsi gani tunaweza kufanya hivyo?
Kitu pekee ambayo inaweza kutuambia ambapo D ilikuwa,
alikuwa pointer ijayo awali kuhifadhiwa katika C,
lakini sisi tu rewrote kwamba pointer
kwa uhakika na node mpya,
hivyo sisi hatuna tena kidokezo ambapo D ni katika kumbukumbu,
na tumekuwa waliopotea mapumziko ya orodha.
Si nzuri wakati wote.
>> Hivyo, jinsi gani sisi kufanya haki hii?
Kwanza, kumweka nodi mpya ijayo pointer katika D.
Sasa, wote wapya nodi na C ijayo kuyatumia
ni akizungumzia nodi huo, D,
lakini hiyo ni nzuri.
Sasa tunaweza kumweka C ijayo pointer kwenye nodi mpya.
Hivyo, tumefanya hii bila ya kupoteza data yoyote.
Katika kanuni, C ni nodi sasa
kwamba traversal pointer crawler ni akizungumzia,
na D ni kuwakilishwa na nodi alisema kwa karibu na shamba nodi ya sasa ijayo,
au crawler → ijayo.
Hivyo, sisi kwanza kuweka nodi mpya ijayo pointer
kwa uhakika na crawler → ijayo,
njia sawa sisi alisema new_node ya pointer ijayo lazima
uhakika na D katika kielelezo.
Kisha, tunaweza kuweka nodi ya sasa ijayo pointer
na nodi wetu mpya,
tu kama sisi alikuwa kusubiri kwa kumweka C kwa new_node katika kuchora.
Sasa kila kitu katika utaratibu, na sisi hawakuwa kupoteza
kufuatilia wa data yoyote, na tuliweza tu
fimbo nodi wetu mpya katikati ya orodha
bila kujenga jambo zima au hata shifting mambo yoyote
njia ya sisi wangalipata na safu fasta-urefu.
>> Hivyo, orodha zilizounganishwa ni ya msingi, lakini muhimu, nguvu data muundo
ambayo kuwa na faida zote mbili na hasara
ikilinganishwa na arrays na data nyingine miundo,
na kama ni mara nyingi kesi katika sayansi ya kompyuta,
ni muhimu kujua wakati wa matumizi ya kila chombo,
hivyo unaweza kuchukua chombo haki kwa haki ya kazi.
>> Kwa ajili ya mazoezi zaidi, jaribu kuandika kazi kwa
kufuta nodes kutoka orodha wanaohusishwa -
kumbuka kuwa makini kuhusu utaratibu ambao upya
kuyatumia yako ijayo ili kuhakikisha kuwa wewe si kupoteza chunk ya orodha yako -
au kazi ya kuhesabu nodes katika orodha wanaohusishwa,
au moja ya kujifurahisha, ili kuondokana na utaratibu wa wote wa nodi katika orodha zinazoungwa.
>> Jina langu ni Jackson STEINKAMP, hii ni CS50.