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

数据结构之利用单链表实现集合的交并运算

程序员文章站 2022-07-15 16:50:38
...
/*
*Copyright© 中国地质大学(武汉) 信息工程学院
*All right reserved.
*
*文件名称:linkedList.h
*摘    要:利用单链表实现集合的交并运算
*
*当前版本:1.0
*作       者:邵玉胜
*完成日期:2018-12-27
*/


#ifndef LINKLIST_H_
#define LINKLIST_H_
#include<iostream>
//定义节点结构体
template<class T>
struct LinkedNode
{
	LinkedNode<T>* _pNext;                        //指向下一个元素的指针
	T _tData;                                     //节点中的数据
	LinkedNode(LinkedNode<T>* ptr = nullptr) {    //构造函数,仅初始化指针
		_pNext = ptr;
	}

	LinkedNode(T data, LinkedNode<T>* ptr = nullptr) {    //构造函数,仅初始化指针
		_tData = data;
		_pNext = ptr;
	}
};

template<class T>
class LinkedList
{
private:
	LinkedNode<T>* _pFirst;                   //头节点指针
	LinkedNode<T>* _pRear;                    //尾节点指针
	int _iCountOfList;                        //节点数量

public:
	LinkedList();                                   //构造函数
	~LinkedList();									//析构函数
	bool IsEmpty();									//判断链表空否
	void MakeEmpty();                               //置空
	int Size() const;                               //获取节点数量
	void PutElement(const T data);					//向链表中增加数据
	int DelElement(const T data);                   //在链表中删除指定的节点,返回删除的数量
	bool GetElement(const int index, T& data);		//获取下标为index的数据
	void LocateElement(const T data, int& index);   //获取链表中第一个数据为data的位置,没有找到就返回-1
	void UnionList(const LinkedList<T>& lst);       //求两个链表的并集,并集的结果直接体现在本对象中
	void IntersectionList(const LinkedList<T>& lst);//求两个链表的交集,交集的结果直接体现在本对象中
	void PurgeList(LinkedList<T>& lst);             //将链表中重复的元素删掉,相同值只保留一个,结果保存至参数链表中
};

//默认构造函数
template<class T>
LinkedList<T>::LinkedList() {
	_pFirst = _pRear = new LinkedNode<T>();        //头节点与尾节点都指向同一个无数据,下一节点指针为空的节点
	_iCountOfList = 0;                             //节点个数初始化为0
	if (_pFirst == nullptr) {                      //内存分配错误!
		std::cerr << "数据内存分配错误,结束程序!" << std::endl;
		exit(0);
	}
	std::cout << "LinkedList的构造函数被调用!\n";
}


//析构函数
template<class T>
LinkedList<T>::~LinkedList() {
	MakeEmpty();
	std::cout << "LinkedList的析构函数被调用!\n";
}


//判断链表空否
template<class T>
bool LinkedList<T>::IsEmpty() {
	if (this->_iCountOfList == 0)                   //如果节点数量为0,表就为空
		return true;
	return false;
}  

//置空
template<class T>
void LinkedList<T>::MakeEmpty() {
	LinkedNode<T>* pDel = nullptr;                //定义临时节点指针,用于删除
	while (this->_pFirst->_pNext != nullptr) {    //循环释放各个节点的空间
		pDel = this->_pFirst->_pNext;             //头节点指向下一节点
		this->_pFirst->_pNext = pDel->_pNext;     //头节点后移
		delete pDel;                              //删除节点
	}
}

//获取节点数量
template<class T>
int LinkedList<T>::Size() const {
	return this->_iCountOfList;
}

//向链表中增加数据,,默认在链尾添加
template<class T>
void LinkedList<T>::PutElement(const T data) {
	//先利用参数data创建节点
	LinkedNode<T>* pCur = new LinkedNode<T>(data);
	if (pCur == nullptr) {
		std::cerr << "内存分配错误!\n";
		exit(-1);
	}
	//增加数据采用从尾节点增加
	this->_pRear->_pNext = pCur;
	this->_pRear = pCur;
	
	++this->_iCountOfList;                         //节点数量加1
}

//在链表中删除指定的节点,删除所有数值等于data的节点
template<class T>
int LinkedList<T>::DelElement(const T data) {
	if (this->IsEmpty() == true)                         //空表,直接返回false
		return 0;
	LinkedNode<T>* pCur = this->_pFirst;                 //指向头节点
	int count = 0;
	while (pCur != this->_pRear) {                       //循环遍历链表,删除节点值等于data的数据
		if (pCur->_pNext->_tData == data) {              //节点值等于参数给定的值
			LinkedNode<T>* pDel = pCur->_pNext;          //建立临时指针指向要删除的节点,方便释放内存
			pCur->_pNext = pCur->_pNext->_pNext;
			delete pDel;                                 //删除节点
			--this->_iCountOfList;                       //节点数递减
			++count;
		}else
			pCur = pCur->_pNext;
	}
	return count;
}                  

//获取下标为index的数据,下标从0开始
template<class T>
bool LinkedList<T>::GetElement(const int index, T& data) {
	if (index < 0 || index >= this->_iCountOfList)             //下标超限,其中包含了链表为空的判断
		return false;
	LinkedNode<T>* pCur = this->_pFirst->_pNext;               //利用一个临时指针指向首节点
	int count = 0;
	while (count < index) {                                    //遍历至下标为index的节点
		pCur = pCur->_pNext;
		++count;
	}
	data = pCur->_tData;                                       //将下标为index的节点的数据赋值给返回参数
	return true;
} 

//获取链表中第一个数据为data的位置,没有找到就返回-1
template<class T>
void LinkedList<T>::LocateElement(const T data, int& index) {
	LinkedNode<T>* pCur = this->_pFirst->_pNext;                //先用一个结点指针指向首节点
	int count = 0;
	while (pCur != nullptr) {                                   //循环遍历整个链表
		if (pCur->_tData == data) {                             //找到data,返回参数赋值
			index = count;
			return;
		}                               
		pCur = pCur->_pNext;
		++count;
	}
	index = -1;                                                 //链表中没有数据,返回参数赋-1
	return;
}


//求两个链表的并集,并集的结果直接体现在本对象中
//思路是依此取出参数链表中的节点数据,判断本链表中是否
//存在数据相同的节点,如果存在就不插入
//因为没有声明实现拷贝函数,所以此处的参数直接使用的是引用,不然报错
//此函数适用于纯集合,非纯的先用PurgeList转化
template<class T>
void LinkedList<T>::UnionList(const LinkedList<T>& lst) {
	LinkedNode<T>* pCur_lst = lst._pFirst->_pNext;
	while (pCur_lst != nullptr) {                                 //循环遍历整个参数表
		T tData_lst = pCur_lst->_tData;                           //获取当前节点数据
		int index;                                                
		this->LocateElement(tData_lst, index);                    //获取参数节点值在本对象链表中的位置
		if (index == -1)                                          //如果在本对象链表中没有找到相同的结点值
			this->PutElement(tData_lst);                          //就执行增加命令
		pCur_lst = pCur_lst->_pNext;
	}
	return;
}

//求两个链表的交集,交集的结果直接体现在本对象中
//同样该函数也是适用于纯集合(集合中没有相同元素)
//既然是求集合,那么对元素的位置没有要求,这个时候
//就对列表中元素进行排序,这样有利于运算
template<class T>
void LinkedList<T>::IntersectionList(const LinkedList<T>& lst) {
	LinkedNode<T>* pCur = lst._pFirst->_pNext;
	while (pCur != nullptr) {
		T tData = pCur->_tData;
		int iIndex;
		this->LocateElement(tData, iIndex);            //在本对象链表中寻找数值等于tData的节点
		if (iIndex < 0)                                //在本对象的链表中没有找到该值
			this->PutElement(tData);                   //就在本对象中添加该节点
		pCur = pCur->_pNext;
	}
}

//求本对象不重复的元素结果保存在参数链表中
template<class T>
void LinkedList<T>::PurgeList(LinkedList<T>& lst) {
	if (lst.IsEmpty() == false)                          //如果参数链表部位空,先置空
		lst.MakeEmpty();
	LinkedNode<T>* pCur = this->_pFirst->_pNext;       //指向首节点
	while (pCur != nullptr) {
		T tData = pCur->_tData;
		int index;
		lst.LocateElement(tData, index);               //在参数链表中没有找到相关元素,就加入元素
		if (index < 0)
			lst.PutElement(tData);
		pCur = pCur->_pNext;
	}
	return;
}
#endif // !LINKLIST_H_