当前位置:C++技术网 > 资讯 > 数据结构作业之删除单链表中重复的元素(未排序)

数据结构作业之删除单链表中重复的元素(未排序)

更新时间:2016-05-14 23:17:26浏览次数:1+次

    这是一道IT公司的面试算法题。不得不说,老师让我们做这个,是有点难!

    题目:给出一单链表,删除其中重复的元素。(在这里,我自己添加一个要求:要求不经过排序,直接在原来的单链表上进行删除操作)。为什么?很简单,因为STL封装了单链表容器,其中封装了很多的便利函数方法,算法等能够调用,简单地解决问题。就是不知道有没有封装unique,erase,remove三个算法。个人觉得应该有,那样的话,就更简单了。

先看看原理图:

对于实现算法:

void shanchucaozuo(LinkList  H)
{
	LinkList p,q,r;
	p=H->next;
	while (p)
	{
		q=p->next;
		r=p;
		while(q)
		{
			if (q->data==p->data)
			{
				r->next=q->next;
				free(q);
				q=r->next;
			}
			else
			{
				r=r->next;
				q=q->next;
			}
		}
		p=p->next;
	}

	printf("删除单链表重复的元素后的链表:\n");
	print(H);
        return ;
}
遍历的思路是将p结点的位置不变,而r,q结点则是往后遍历,直到末尾处。r结点的作用就是保存q结点的前继结点,也就是说,r始终在q结点的前面一个节点处。以便,当我们进行删除操作时,能够保证删除的节点的前继结点与其后继结点能够连接起来。
第二种方法:、

算法实现:
void shanchucaozuo(LinkList  H)
{
        p=H->next;
	if(p==NULL)
		return ;
	while (p->next)
	{
		q=p;
		while (q->next)
		{
			if(q->next->data==p->data)
			{
				r=q->next;
				q->next=r->next;
				free(r);
			}
			else
			{
				q=q->next;
			}
		}
		p=p->next;
	}
	printf("删除单链表重复的元素后的链表:\n");
	print(H);
	return ;
}
这个算法的思路呢保存q,r,p三个结点的起始位置是一样的。然后保持p不变,继而移动r,p。注意哦,q的位置在哪的时候就是应该删除重复元素的时候?就是再重复的元素的前面结点处。因为,我们是以q->next来判断的。
这两种是比较普遍的算法思路。其实利用散列表应该也能解决这个问题。