数据结构之线性表—高效删除重复元素

C++ 少儿编程 1084浏览 0评论

      刚刚学完数据结构之线性表中关于顺序表和单链表的知识,我们知道顺序表中存储数据的结构是一个数组,对于数组来说,在尾部插入、删除元素是比较高效的,但是如果在中间或者开头插入、删除元素,就会涉及数据的搬移,效率较低。

      我们看看下面的作业题目:

数据结构之线性表---高效删除重复元素

由于数组已经排序,所以重复的元素一定连在一起,找出它们并不难,但如果毎找到一个重复元素就立即删除它,就是在数组中间进行删除操作,需要进行数据搬移操作。而且题目要求我们原地修改,也就是说不能用辅助数组。

其实,对于数组相关的算法问题,有一个通用的技巧:要尽量避免在中间删除元素,那我就想办法把这个元素换到最后去

这样的话,最终待删除的元素都拖在数组尾部,按照这个思路呢,又可以衍生出解决类似需求的通用方式:双指针技巧。具体一点说,应该是快慢指针。

我们让慢指针slow走左后面,快指针fast走在前面探路,找到一个不重复的元素就告诉slow并让slow前进一步。

这样当fast指针遍历完整个数组后,数组[0..slow]就是不重复元素,之后的所有元素都是重复元素

算法执行的过程:

数据结构之线性表---高效删除重复元素

我们的线性顺序表是这样的:

数据结构之线性表---高效删除重复元素

C语言源码:

数据结构之线性表---高效删除重复元素

扩展一下,现在是针对一个有序链表去重呢?算法思路和数组是一样的,只要把数组赋值操作变成操作指针:

数据结构之线性表---高效删除重复元素

带头结点的单链表是这样的:

数据结构之线性表---高效删除重复元素

以下是带头结点的单链表算法源码:

数据结构之线性表---高效删除重复元素

 

转自公众号:
南昌青少年编程

您必须 登录 才能发表评论!