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