数据结构之利用单链表实现集合的交并运算
程序员文章站
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_