单链表的应用--删除有序表中重复的元素

单链表的应用--删除有序表中重复的元素

  删除有序表中重复的元素，利用前文写好的链表的框架，在链表类中补充linkListDelDup方法。

对单链表排序

一、问题分析二、代码分析

1.链表类linkList2.链表方法linkListDelDup 三、测试代码

1.主函数2.输出结果 四、源代码获取（免积分）

一、问题分析

  给你一个有序链表,删除其重复元素并输出结果。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

二、代码分析 1.链表类linkList

  在链表类中声明linkListDelDup方法。

template 
class linkList{
	public:
		linkList();//构造函数 
		~linkList();//析构函数 
		void Insert(int i ,ElemType x);//插入函数 
		void PrintList();//打印所有元素  
		int Length();//获取链表长度
		ElemType Get(int i) ;//按位查找，返回第i个元素的值
		int Locate(ElemType x) ;//按值查找，返回x在单链表中的位置
		ElemType Delete(int i) ;//删除第i个元素 
		void linkListDelDup();
	private:
		Node* first; //头指针 
}; 

2.链表方法linkListDelDup

  这是链表的基本 *** 作。由于链表是有序的，所以可以从头开始遍历，然后跳过重复元素。实现代码如下：

template 
void linkList::linkListDelDup()
{
	Node* p=first->next;
	
	if(p==NULL)
	{
		return;
	}
	
	while(p->next!=NULL)
	{
		
		if(p->data==p->next->data)
		{
			Node* s=p->next;//跳过并删除这个重复元素 
			p->next=s->next; //指向下一个元素用以判断是否重复 
			delete s; 
		}
		else
		{
			p=p->next; //元素不重复， 继续遍历 
		}	
	}
}

三、测试代码 1.主函数

#include 
#include "linkList.h"
#include "linkList.cpp" 

using namespace std;

int  main() {
	linkList L;
	
	L.Insert(1,1);
	L.Insert(2,1);
	L.Insert(3,3);
	L.Insert(4,4);
	L.Insert(5,4);	
	L.Insert(6,5);	
	
	cout<<"原先链表数据:" < 
2.输出结果 
原先链表数据:
1 1 3 4 4 5
删除重复元素之后的链表元素:
1 3 4 5
 
四、源代码获取（免积分） 
删除有序表中重复的元素
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714437.html