欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构与算法:线性表——删除重复元素

程序员文章站 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 }

 

碎碎念:本人学生,第一次写随笔,也不清楚下次会在什么时候写。如果有什么需要改进的地方,请务必提出来,我在此谢过。