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

/*

*Copyright? 中国地质大学（武汉） 信息工程学院

*All right reserved.

*

*文件名称：linkedList.h

*摘 要：利用单链表实现集合的交并运算

*

*当前版本：1.0

*作 者：邵玉胜

*完成日期：2018-12-27

*/

#ifndef LINKLIST_H_

#define LINKLIST_H_

#include

//定义节点结构体

template

struct LinkedNode

{

LinkedNode* _pNext; //指向下一个元素的指针

T _tData; //节点中的数据

LinkedNode(LinkedNode* ptr = nullptr) { //构造函数，仅初始化指针

_pNext = ptr;

}

LinkedNode(T data,LinkedNode* ptr = nullptr) { //构造函数，仅初始化指针

_tData = data;

_pNext = ptr;

}

};

template

class LinkedList

{

private:

LinkedNode* _pFirst; //头节点指针

LinkedNode* _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& lst); //求两个链表的并集，并集的结果直接体现在本对象中

void IntersectionList(const LinkedList& lst);//求两个链表的交集，交集的结果直接体现在本对象中

void PurgeList(LinkedList& lst); //将链表中重复的元素删掉，相同值只保留一个，结果保存至参数链表中

};

//默认构造函数

template

LinkedList::LinkedList() {

_pFirst = _pRear = new LinkedNode(); //头节点与尾节点都指向同一个无数据，下一节点指针为空的节点

_iCountOfList = 0; //节点个数初始化为0

if (_pFirst == nullptr) { //内存分配错误！

std::cerr << "数据内存分配错误,结束程序！" << std::endl;

exit(0);

}

std::cout << "LinkedList的构造函数被调用！n";

}

//析构函数

template

LinkedList::~LinkedList() {

MakeEmpty();

std::cout << "LinkedList的析构函数被调用!n";

}

//判断链表空否

template

bool LinkedList::IsEmpty() {

if (this->_iCountOfList == 0) //如果节点数量为0，表就为空

return true;

return false;

}

//置空

template

void LinkedList::MakeEmpty() {

LinkedNode* pDel = nullptr; //定义临时节点指针,用于删除

while (this->_pFirst->_pNext != nullptr) { //循环释放各个节点的空间

pDel = this->_pFirst->_pNext; //头节点指向下一节点

this->_pFirst->_pNext = pDel->_pNext; //头节点后移

delete pDel; //删除节点

}

}

//获取节点数量

template

int LinkedList::Size() const {

return this->_iCountOfList;

}

//向链表中增加数据,，默认在链尾添加

template

void LinkedList::PutElement(const T data) {

//先利用参数data创建节点

LinkedNode* pCur = new LinkedNode(data);

if (pCur == nullptr) {

std::cerr << "内存分配错误！n";

exit(-1);

}

//增加数据采用从尾节点增加

this->_pRear->_pNext = pCur;

this->_pRear = pCur;

++this->_iCountOfList; //节点数量加1

}

//在链表中删除指定的节点,删除所有数值等于data的节点

template

int LinkedList::DelElement(const T data) {

if (this->IsEmpty() == true) //空表，直接返回false

return 0;

LinkedNode* pCur = this->_pFirst; //指向头节点

int count = 0;

while (pCur != this->_pRear) { //循环遍历链表，删除节点值等于data的数据

if (pCur->_pNext->_tData == data) { //节点值等于参数给定的值

LinkedNode* pDel = pCur->_pNext; //建立临时指针指向要删除的节点，方便释放内存

pCur->_pNext = pCur->_pNext->_pNext;

delete pDel; //删除节点

--this->_iCountOfList; //节点数递减

++count;

}else

pCur = pCur->_pNext;

}

return count;

}

//获取下标为index的数据,下标从0开始

template

bool LinkedList::GetElement(const int index,T& data) {

if (index < 0 || index >= this->_iCountOfList) //下标超限，其中包含了链表为空的判断

return false;

LinkedNode* pCur = this->_pFirst->_pNext; //利用一个临时指针指向首节点

int count = 0;

while (count < index) { //遍历至下标为index的节点

pCur = pCur->_pNext;

++count;

}

data = pCur->_tData; //将下标为index的节点的数据赋值给返回参数

return true;

}

//获取链表中第一个数据为data的位置,没有找到就返回-1

template

void LinkedList::LocateElement(const T data,int& index) {

LinkedNode* 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

void LinkedList::UnionList(const LinkedList& lst) {

LinkedNode* 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

void LinkedList::IntersectionList(const LinkedList& lst) {

LinkedNode* 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

void LinkedList::PurgeList(LinkedList& lst) {

if (lst.IsEmpty() == false) //如果参数链表部位空，先置空

lst.MakeEmpty();

LinkedNode* 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_

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!