数据结构考研分类复习真题 第二章 答案[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若题目要求元素间相对顺序不变请参见本章三填空题的算法

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