在题目中有序表也就是数组,下面是一个由小到大排列起来的数组,其中含有某些重复的元素。现在,我们的目的是把数组中重复的元素删除掉。
为了方便,考虑设置两个指针变量分别为i和j,从左到右依次进行遍历。假如i记录要留下的元素的个数;j记录所有访问到的元素个数。i始终落后于j,也就是i<=j。这样把后面的元素赋值给前面的元素,L.data[i]=L.date[j]就不会产生重复值的元素,从而达到删除所有重复元素的目的。
具体的代码算法如下:
bool DeleteSame(SeqList &L) {
if(L.length == 0) return false; //出口条件放在第一句,程序执行的更快,代码简洁明了
int i,j;// i 访问到要留下的元素,j访问到全部的元素
for(i = 0,j = 1;j < L.length;j )
if(L.data[i] != L.data[j]) // 查找下一个与上个元素值不同的元素
L.data[ i] = L.data[j]; //找到后。则将元素前移
L.length = i 1;// i是数组下标,从0开始,要反映数组的长度要加1,下标与长度相差1的关系
return true;
}
程序中j问什么要从1始执行,这是因为不管0号元素与1号元素是否相同,0号元素始终要留下的,而删除重复值的元素要从1号元素起。
当程序进入for循环体中的if语句,先进行第一个元素1和第二个元素2进行比较,如果发现两个数不相同,也就是两个值不重复,那么这两个数都可以留下。默认的情况下,第一个元素是要留下的。
当执行到L.data[ i] = L.data[j]语句时, i从0自动变成了1,此时j也是1。这样L.data[1] = L.data[1],从而让2号元素也留下了。由于1号元素与2号元素是不相等的,两个元素都留下了。在这个for循环中j要遍历到末尾,语句结束的条件是j等于线性表的长度,才跳出for循环语句。
当再执行for语句,此时j ,j由原来的位置1变成了位置2,i还是原来的位置1。这时比较两个位置上的数,发现2与2是相等的,这样没有进入if语句中,就无法赋值,无法进行数据的保存。i还是保持在1位置,j 就变成了3位置,相当于把第二位置的2删掉了。
当再次for循环体中,执行if语句发现1号位置的2与3号位置的3的值不重复,进入循环体中,i先自加1,变成2位置,这样就把j的3号位置的数字3赋值给2号位置,此时2号位置存入了元素3数字。
这样依次遍历下去,i<=j,始终将后面的元素赋值给前面,从而避免了重复值。
,