删除一堆数据中重复数据的两种方法(单链表与线性表)c++

前言

  第一次写博客,问题虽然简单,但是我写的很认真的,《删除一堆数据中重复数据的两种方法(单链表与线性表)c++》,尽量将自己的思路写的清晰,大神若路过请不要见笑(还望多多指点),真诚的希望我写的东西能帮助到一些

人,有问题或错误都可以提,让我们共同进步!《删除一堆数据中重复数据的两种方法(单链表与线性表)c++》

1.问题概述

  在一堆数据中可能存在重复的数据,请将重复项删除,只留下独一无二的值。

  例如:1,2,2,6,2,2,6,9,6    

  删除后:1,2,6,9

2.思路分析

关于这道题,看似简单,一开始感觉用两个for循环,将当前数据与其之后的数据一一比较,相同则删除,再遍历完所有数据后就大功告成了。想法倒挺美,实现起来就蒙圈了,主要问题是如何依次按照顺序把相同的删除,不同的保留。

一般人的想法会先想到用for循环先赋值要检验的数,再去判断,这样会导致无法删除在不同数后的重复数;正确的思路是用两个标记标记它,一个标记在母数处(在该轮遍历中不动),另一个标记判断这个母数后面的子数是否与其重复,若是则删除,否则往后移一个位置。 

 

 

 

《删除一堆数据中重复数据的两种方法(单链表与线性表)c++》

 

 

 

3.代码实现

 3.1 单链表方法

#include<iostream>
using namespace std;
struct node
{
	int data;
	node *next;
};
int main()
{
	int num[9]={1,2,2,6,2,2,6,9,6};
	node *head=new node;//生成头结点
	node *end=head;//定义一个尾指针
	/*使用尾插法读入数据,建立单链表*/
	for(int i=0;i<9;++i)
	{
		node *p=new node;
		p->data=num[i];
		end->next=p;
		end=p;
	}
	end->next=0;//尾指针不要忘记指向NULL
	/*删除重复数据的核心算法*/
	node *p,*q,*r;//*p用来遍历单链表,*q用来遍历当前检验数据的后面数据,*r用来暂时保留将要被删的数据
	p=head->next;
	for(p=head->next;p!=0;p=p->next)
	{
		q=p;
		while(q->next)
		{
			if(q->next->data==p->data)
			{
				r=q->next;
				q->next=r->next;
				delete r;
			}
			else
				q=q->next;
		}
	}
	for(node *q=head->next;q!=0;q=q->next)
		cout<<q->data;	
}

3.2  线性表方法

#include<iostream>
using namespace std;
void remove(int num[],int n)
{
	for(int i=0;i<n;++i)//遍历数组
	{
		int j=i;
		while(j<n)
		{
			if(num[j+1]==num[i])//先判断,再操作
			{
				for(int x=j+1;x<n;++x)
					num[x]=num[x+1];//被删数后全部数据前移一位
				n--;//删一位数,就将数组大小减1
			}
			else
				j++;
		}
	}
	for(int i=0;i<n;++i)
		cout<<num[i];
}
int main()
{
	int num[9]={1,2,2,6,2,2,6,9,6};
	remove(num,9);
}

 

4. 两种方法效率分析

  指针的方法用了两个for循环,删除操作是常数时间O(1),所以时间复杂度为O(n^2);数组的方法要差一些,遍历查找也用了两个for循环,可是删除操作是将数组整体移动一位,所以时间复杂度为O(n^3)。

5. 补充

《删除一堆数据中重复数据的两种方法(单链表与线性表)c++》

    原文作者:波力海带
    原文地址: https://blog.csdn.net/qq_37373250/article/details/78634858
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞