數(shù)據(jù)結(jié)構(gòu)第2章典型例題解析-文庫(kù)吧在線文庫(kù)
【正文】 儲(chǔ)方式最節(jié)省時(shí)間。A． 內(nèi)存地址 B．?dāng)?shù)組下標(biāo) C．下一元素地址 D．左、右孩子地址【分析】靜態(tài)鏈表采用的是鏈?zhǔn)椒绞酱鎯?chǔ)線性表，以數(shù)組方式存儲(chǔ)鏈表的數(shù)據(jù)，指針域存儲(chǔ)的是該結(jié)點(diǎn)邏輯上的后繼結(jié)點(diǎn)的相對(duì)地址（即在數(shù)組中的下標(biāo)），也稱為靜態(tài)指針?！敬鸢浮緾11．線性表（a1,a2,…,an）以鏈接方式存儲(chǔ)時(shí)，訪問第i個(gè)位置元素的時(shí)間復(fù)雜性為 。 sprior=p。 snext=pnext。在選項(xiàng)A、B和C中均是先執(zhí)行操作pnext=s，就是修改了結(jié)點(diǎn)p的后繼結(jié)點(diǎn)s，然后再執(zhí)行操作pnextprior=s，因此，無法使得結(jié)點(diǎn)s為結(jié)點(diǎn)p的原后繼結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，這樣的賦值會(huì)使s結(jié)點(diǎn)為其自身的前驅(qū)。 snext=p?！痉治觥恳?yàn)轫樞虮碓趦?nèi)存是用地址連續(xù)的空間存儲(chǔ)的，設(shè)a1的存儲(chǔ)地址為L(zhǎng)oc(a1)，每個(gè)數(shù)據(jù)元素占d個(gè)存儲(chǔ)地址，則第i個(gè)數(shù)據(jù)元素的地址為：Loc(ai)=Loc(a１)+(i1)d 1≤i≤n這就是說只要知道順序表首地址和每個(gè)數(shù)據(jù)元素所占地址單元的個(gè)數(shù)就可求出第i個(gè)數(shù)據(jù)元素的地址來，這也是順序表具有按數(shù)據(jù)元素的序號(hào)隨機(jī)存取的特點(diǎn)?！痉治觥看驩記法表示時(shí)間漸近復(fù)雜度，是指一個(gè)算法中的時(shí)間耗費(fèi)，往往是問題規(guī)模n的函數(shù)T(n)，當(dāng)n趨向于無窮大時(shí)，T(n)的數(shù)量級(jí)稱為算法的時(shí)間漸近復(fù)雜度。所以，它存取表中第i個(gè)元素的時(shí)間與i無關(guān)。圖211 第1題圖sprior=pprior。sprior=pprior。jn。 Lnext){ q=L。返回的L指向原鏈表的第二個(gè)結(jié)點(diǎn)。頭指針的作用是用來唯一標(biāo)識(shí)一個(gè)單鏈表。試寫一算法，將x插入到線性表的適當(dāng)位置上，以保持線性表的有序性。A[i]x){ //邊找位置邊移動(dòng) A[i+1]=A[i]?！痉治觥坷醚h(huán)單鏈表的特點(diǎn)，通過s指針可循環(huán)找到其前驅(qū)結(jié)點(diǎn)p及p的前驅(qū)結(jié)點(diǎn)q，然后可刪除結(jié)點(diǎn)p?！痉治觥拷患傅氖莾蓚€(gè)單鏈表的元素值相同的結(jié)點(diǎn)的集合，為了操作方便，先讓單鏈表C帶有一個(gè)頭結(jié)點(diǎn)，最后將其刪除掉。amp。 } else q=qnext。【算法】LinkList delete(LinkList L,int min,int max){ //設(shè)L為帶頭結(jié)點(diǎn)的循環(huán)鏈表 LNode *p,*q,*s,*k。 //p 指向第一個(gè)值不大于min的結(jié)點(diǎn) while (snext!=p){ //刪除*s 的后繼至* p的前驅(qū)之間的結(jié)點(diǎn) k=snext。 cur_b=Init_List()。next。next=NULL。next=temp。amp。編寫一個(gè)算法，將一個(gè)頭結(jié)點(diǎn)指針為a的單鏈表A分解為兩個(gè)單鏈表A和B，其頭結(jié)點(diǎn)指針分別為a和b，使得A鏈表中含有原鏈表A中序號(hào)為奇數(shù)的元素（頭結(jié)點(diǎn)緊接的下一個(gè)元素為第1個(gè)元素），而B鏈表中含有原鏈表A中序號(hào)為偶數(shù)的元素，且保持原來的相對(duì)順序。 p=pnext。 return r。 rnext=s。 r=C。 p=pnext。 return 1。 if (*num==arrsize1) return 0。時(shí)間復(fù)雜度為O(1)；若結(jié)點(diǎn)p無后繼結(jié)點(diǎn)，則不可以實(shí)現(xiàn)。如鏈表H，鏈表L等，表示鏈表中第一個(gè)結(jié)點(diǎn)的地址存放在H和L中。 pnext=Q。故算法功能是刪除一維數(shù)組中多余的值相同的元素。2．已知線性表非遞減有序，存儲(chǔ)于一個(gè)一維數(shù)組A[0..n1] 中（表長(zhǎng)為n，設(shè)為全局量），下面算法的功能是什么？void del(DataType A[]){ int i,j?！倍荒転椤皃priornext=s?！敬鸢浮空_10．取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)。其存儲(chǔ)空間不發(fā)生變化，而其內(nèi)容可以發(fā)生變化?！敬鸢浮垮e(cuò)誤4．線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的?！敬鸢浮緾二
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1