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