signed

QiShunwang

“诚信为本、客户至上”

【王道数据结构】删除顺序表中所有值为x的元素

2021/3/21 8:38:54   来源:

对长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为x的元素

思路:

  1. 记录值为x元素的个数count
  2. 值不为x的元素,向前移动count个单位
  3. 顺序表长减去count

伪代码:

void DelX(SqList &L, ElmType x){
	int count = 0, i = 0;
	while(i < L.length){
		if(x == L.data[i])
			count++;
		else
			a[i-count] = a[i];
		i++;
	}
	L.length -= count;
}

c代码实现:

#include<stdio.h>
int DelX(int a[], int x, int len);
int main(){
    int a[10]={1,2,3,4,5,2,1,4,2,1}, i = 0;
    int length = DelX(a, 2, 10);
    for(; i < length; i++){
        printf("%d ", a[i]);
    }
    return 0;
}
int DelX(int a[], int x, int len){
    int count = 0;
    int i = 0;
    while(i < len){
        if(x == a[i])
            count++;
        else
            a[i-count] = a[i];
        i++;
    }
    return len - count;
}

注意只对值不为x的元素进行移动,因为只有这些元素是需要保留的
最后注意更新顺序表长度