數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)第一二章習(xí)題答案-資料下載頁(yè)
2025-06-19 23:50本頁(yè)面
【正文】 = q。 }}（8）設(shè)計(jì)一個(gè)算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同 ）。void delete(LinkList amp。L, int mink, int maxk) { p=Lnext。 //首元結(jié)點(diǎn) while (p amp。amp。 pdata=mink) { pre=p。 p=pnext。 } //查找第一個(gè)值mink的結(jié)點(diǎn) if (p) { while (p amp。amp。 pdatamaxk) p=pnext。 // 查找第一個(gè)值 ≥maxk 的結(jié)點(diǎn) q=prenext。 prenext=p。 // 修改指針 while (q!=p) { s=qnext。 delete q。 q=s。 } // 釋放結(jié)點(diǎn)空間 }//if}（9）已知p指向雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data、prior、next三個(gè)域，寫出算法change(p),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。知道雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，與前驅(qū)交換涉及到四個(gè)結(jié)點(diǎn)（p結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn)）六條鏈。void Exchange（LinkedList p）∥p是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。{q=pllink； qllinkrlink=p； ∥p的前驅(qū)的前驅(qū)之后繼為p pllink=qllink； ∥p的前驅(qū)指向其前驅(qū)的前驅(qū)。 qrlink=prlink； ∥p的前驅(qū)的后繼為p的后繼。 qllink=p； ∥p與其前驅(qū)交換 prlinkllink=q； ∥p的后繼的前驅(qū)指向原p的前驅(qū) prlink=q； ∥p的后繼指向其原來的前驅(qū)}∥算法exchange結(jié)束。（10）已知長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。[題目分析] 在順序存儲(chǔ)的線性表上刪除元素，通常要涉及到一系列元素的移動(dòng)（刪第i個(gè)元素，第i+1至第n個(gè)元素要依次前移）。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對(duì)位置不變。因此可以考慮設(shè)頭尾兩個(gè)指針（i=1，j=n），從兩端向中間移動(dòng)，凡遇到值item的數(shù)據(jù)元素時(shí)，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。void Delete（ElemType A[ ]，int n）∥A是有n個(gè)元素的一維數(shù)組，本算法刪除A中所有值為item的元素。{i=1；j=n；∥設(shè)置數(shù)組低、高端指針（下標(biāo)）。 while（ij） {while（ij amp。amp。 A[i]!=item）i++； ∥若值不為item，左移指針。 if（ij）while（ij amp。amp。 A[j]==item）j；∥若右端元素值為item，指針左移 if（ij）A[i++]=A[j]； }[算法討論] 因元素只掃描一趟，算法時(shí)間復(fù)雜度為O（n）。刪除元素未使用其它輔助空間，最后線性表中的元素個(gè)數(shù)是j。
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1