數據結構考研分類復習真題 第二章 答案[53]

　　．[題目分析] 在順序存儲的線性表上刪除元素通常要涉及到一系列元素的移動(刪第i個元素第i+至第n個元素要依次前移)本題要求刪除線性表中所有值為item的數據元素並未要求元素間的相對位置不變因此可以考慮設頭尾兩個指針(i=j=n)從兩端向中間移動凡遇到值item的數據元素時直接將右端元素左移至值為item的數據元素位置

　　void  Delete(ElemType A[ ]int  n)∥A是有n個元素的一維數組本算法刪除A中所有值為item的元素
　　{i=;j=n;∥設置數組低高端指針(下標)
　　while(i<j)
　　{while(i<j && A[i]!=item)i++;∥若值不為item左移指針
　　if(i<j)while(i<j && A[j]==item)j;∥若右端元素值為item指針左移
　　if(i<j)A[i++]=A[j];
　　}

　　[算法討論] 因元素只掃描一趟算法時間復雜度為O(n)刪除元素未使用其它輔助空間最後線性表中的元素個數是j若題目要求元素間相對順序不變請參見本章三填空題的算法

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23320.html