天马行空

从有序顺序表中删除所有重复值的元素,使表中所有元素的值都不同

  • 2019-06-30 12:04:29
  • 218 次阅读
  • 稿源:天马行空

在题目中有序表也就是数组,下面是一个由小到大排列起来的数组,其中含有某些重复的元素。现在,我们的目的是把数组中重复的元素删除掉。

从有序顺序表中删除所有重复值的元素,使表中所有元素的值都不同

为了方便,考虑设置两个指针变量分别为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,始终将后面的元素赋值给前面,从而避免了重复值。

喜欢 0

文章评论 (0)

表情

大眼 可爱 大笑 坏笑 害羞 发怒 折磨 快哭了 大哭 白眼 晕 流汗 困 腼腆 惊讶 憨笑 色 得意 骷髅 囧 睡觉 眨眼 亲亲 疑问 闭嘴 难过 淡定 抗议 鄙视 猪头