Question

已知线性表A的长度为n，并且采用顺序存储结构。写一算法，删除线性表中所有值为x的元素。

Answer 1

【答案】：(1)数据结构
采用顺序表的定义。
(2)思路
为了减少移动次数，可以采用快速检索的思想，用两个变量i，j记录顺序表中被处理的两端元素的下标，开始时i=0，j=n-1，边检索第i个元素边增加i，直到找到一个元素值等于x，再边检索第j个元素边减少j，直到找到一个元素值不等于x，把下标为j的元素移到下标为i的位置后重复上述过程，直到i≥j。另用一变量count记录删除了多少个元素。
(3)算法
void delx_seq(PSeqListP,DataType x){
/*删除顺序表中所有值为x的元素，新顺序表可能不保持原有顺序*/
int i=0,j=p-＞n-1,count=0;
/*i定位于顺序表开始处，j定位于顺序表最后*/
while(i＜j){
if(p-＞element[i]==x){ /*找到了一个要删除的元素*/
while((p-＞element[j]==x)&&(i!=j)){
/*从后往前找不会被删除的元素，当f，u，相等时退出循环，count记录从后往前找的过程中遇到了多少个要删的元素*/
j--；
count++：
}
if(i==j){
P-＞n=p-＞n-count-1;
return;
}
else{
p-＞element[i]=p-＞element[j];
count++;
j--;
}
}
i++;
}
P-＞n=p-＞n-count;
if(p-＞element[i]==x)p-＞n--;
}
(4)代价分析
该算法访问顺序表中每个元素各一次，时间代价为O(n)。这个算法使用了一点技巧，使得在中间删除元素时，避免了最后一串元素的移动。但是，它破坏了原来线性表中元素之间的顺序关系。
如果需要保持原来的顺序应该怎样做?这里提供一种可行的思路：从前向后遍历表，如果元素值不等于x，则继续向后；如果元素值等于x，则寻找其后第一个不等于x的元素，将这两个元素互换。具体算法请读者自己实现。