数据结构与算法:线性表——删除重复元素
程序员文章站
2022-04-14 22:32:55
线性表是一种随机存取的结构,和链表不同,链表顺序存取的结构。但是,线性表是一种顺序存储的结构,而链表是链式存储结构。两者都是线性的,但区别不同。 进入主题: 1.假如有一串数据元素,要求删除其中的重复元素。 首先想到的是用两层循环,第一层从第一个元素开始,第二层从第一层元素的下一个元素开始。 就是假 ......
线性表是一种随机存取的结构,和链表不同,链表顺序存取的结构。但是,线性表是一种顺序存储的结构,而链表是链式存储结构。两者都是线性的,但区别不同。
进入主题:
1.假如有一串数据元素,要求删除其中的重复元素。
首先想到的是用两层循环,第一层从第一个元素开始,第二层从第一层元素的下一个元素开始。
就是假如第一层是ai元素,则第二层就为ai+1元素。
函数实现:
1 void purge1(elemtype a[],int &n){//elemtype表示任意数据类型,以后不再说明//n为线性表的长度 2 3 int i=0,j; 4 5 while(i<n){ 6 7 j=i+1; 8 9 while(j<n){ 10 11 if(a[j]==a[i]) 12 13 deletelist(a,n,j+1);//具体函数实现最后给出 14 15 else 16 17 j++; 18 19 } 20 21 i++; 22 23 } 24 25 }
2.如果这些元素是按递增排列,且数据量很大的话,使用上面的算法就会造成时间上的浪费。
那要怎么优化呢?
函数实现:
1 void purge2(int *a, int &n) { 2 int i = 0, k = 0;//k是重复的次数 3 for (i = 0; i < n - 1; i++) 4 if (a[i] != a[i + 1]) 5 a[i-k+1] = a[i + 1]; 6 else 7 k++; 8 n = n - k; 9 }
经过小规模的测试没有发现问题。若有有问题可以提出。
经过两函数的分析,可以看出第一个函数使用的是两层循环,而第二个函数只使用了一层循环达到了效果。
避免了不必要的时间浪费。
附上deletelist函数:
1 void deletelist(int *a, int &n, int i) { 2 int j; 3 if (i<1 || i>n)//这条可以无视 4 cout << "超出范围!"; 5 for (j = i; j < n; j++) 6 a[j - 1] = a[j]; 7 n--; 8 }
碎碎念:本人学生,第一次写随笔,也不清楚下次会在什么时候写。如果有什么需要改进的地方,请务必提出来,我在此谢过。
上一篇: PHP实现单文件、多文件上传 封装 面向对象实现文件上传
下一篇: 救人要紧
推荐阅读
-
Python cookbook(数据结构与算法)找出序列中出现次数最多的元素算法示例
-
Python cookbook(数据结构与算法)从序列中移除重复项且保持元素间顺序不变的方法
-
Python cookbook(数据结构与算法)找到最大或最小的N个元素实现方法示例
-
Python cookbook(数据结构与算法)筛选及提取序列中元素的方法
-
Python cookbook(数据结构与算法)将名称映射到序列元素中的方法
-
数据结构与算法 力扣83.删除排序链表的重复元素
-
JavaScript实现删除数组重复元素的5种常用高效算法总结
-
JavaScript数据结构与算法之二叉树添加/删除节点操作示例
-
C++ 删除数组中重复元素的算法(map)
-
JavaScript数据结构与算法之检索算法示例【二分查找法、计算重复次数】