【数据结构】c++实现链表【第三篇】
本帖最后由 仿佛_一念成佛 于 2024-4-25 16:22 编辑# C++实现链表类，重载运算符，友元..【第三篇】
Hello 大家好。我又来了。距离上次的模仿Vector过去好像也有几个星期了。一直没写下一篇。其实是懒得写哈哈，每天都不知道在忙什么但是就是没有时间写。今天静下心了写这一篇。
链表其实我在两个星期前就写完了，但是正如我上面所说的，懒得写下一篇哈哈。
现在我正在写数据结构大课里面的二叉树，这一篇的话得要看我什么时候不懒了才会写了哈哈。不过现在先来写这个链表吧！
---
话有点多，但是咱们开干！
这一次于前两篇不同的是这次我们要在一个头文件中声明三个类然后再源文件中实现三个类具体的功能。
首先第一个类是 **节点类** 其名为**TNodoCalendario**，表示一个在链表中日期的一个节点。
**TListaPos** 这个类说实话我没懂是干什么的，但是作业就是这么要求的，我猜想就是用来获取下一个节点的类吧！它里面的成员也确实是这么个要求
**TListaCalendario** 此类至关重要了，因为这就是我们的链表，我们需靠它和我们的**TNODOCalendario**进行链表的操作，其中包括但不限于查找，删除，插入等等。
首先来介绍第一个类（节点）
## TNodoCalendario
它的公有和私有成员分别为以下函数
### 私有
其中TCalendario c 为最基本的日期类，也是咱们大夏的基层。我已经在数据结构【第一篇】中实现。有兴趣的可以去看一下。
另外TNodoCalendario *siguiente 是一个指针类。表示下一个节点。它和我们的类同名，因为这样才可以进入到下一个节点
```
TCalendario c;
TNodoCalendario *siguiente;
```
### 公有
这里没有什么可以说的，都是实现一个类最基本也是进行赋值操作的基本函数了，分别是构造，深拷贝，析构和赋值函数
```
TNodoCalendario();
TNodoCalendario(const TNodoCalendario &);
~TNodoCalendario();
TNodoCalendario &operator=(const TNodoCalendario &);
```
## TNodoCalendario 实现
#### 构造函数
构造函数需要对私有成员变量进行初始化，那么在这里呢，我分别对我的两个私有变量进行了初始化。
首先是一个赋值。这里的赋值操作是一个深拷贝，其实现方式在第一篇文章中
对于另外一个私有变量咱们进行空指针初始化，防止野指针。
```
TNodoCalendario::TNodoCalendario()
{
c = TCalendario();
siguiente = nullptr;
}
```
#### 深拷贝函数
这里我好像只是进行了浅拷贝，单纯的对私有变量进行了个简单的赋值，但是无碍大事。不过如果在未来出现了无法预料的问题，那么此处会是一处出现问题的地方
```
TNodoCalendario::TNodoCalendario(const TNodoCalendario &t)
{
c = t.c;
siguiente = t.siguiente;
}
```
#### 析构函数
对于析构函数我们需要知道的是，析构函数会在一个对象销毁的时候自动调用或者我们也可以手动调用。当时在写这个其他函数的时候忘了const对象也是可以调用析构函数的，卡了好久才发现。
那么此处也就是进行了空指针赋值和调用TCalendario的析构函数。在第一篇中已经实现了这个。慢慢可以看见的是，对于后面的楼层，地基是非常重要的。地基不稳，大夏也会崩塌
```
TNodoCalendario::~TNodoCalendario()
{
this->siguiente = NULL;
this->c.~TCalendario();
}
```
#### 赋值重载
那么这里也和前面的实现方式一样，首先要判断是不是对两个一样的对象进行赋值，如是，那么直接返回。如不是，首先要对当前对象进行析构调用，因为接下来要用传进来的参数进行赋值，如果不先调用析构函数的话，指针会指向传入的地址，这也就不是重载赋值了，这就是一个浅拷贝
```
TNodoCalendario &TNodoCalendario::operator=(const TNodoCalendario &t)
{
if (this == &t)
{
return *this;
}
(*this).~TNodoCalendario();
c = t.c;
siguiente = t.siguiente;
return *this;
}
```
那么到这里第一个类的基本成员都编写完毕了，需要注意的是，类和类之间如果想要访问各自的私有成员的话，必须添加类为友元，其声明方式为friend。要在头文件中就进行声明。
## TListaPos实现
#### 私有成员
```
TNodoCalendario *pos;
```
这个类说实话我没太明白是干什么的，但是要求就是这么要求的。只能写上去啦哈哈
#### 构造函数
对私有变量进行空指针初始化
```
TListaPos::TListaPos() : pos(nullptr) {}
```
#### 深拷贝
深拷贝，就是得要开辟一个新的空间来存储。不然的话就是浅拷贝。
在下方代码可以看见注释，当进行了简单的赋值后，就是个浅拷贝。为什么呢？因为没有开辟一块新的内存来存储，两个指针指向同一块空间，当其中一个指针修改了其内容后，另外一个指针也会改变。而这不是我们想要的，我们想要的是其中一个指针进行修改的时候不应该映像到另一个指针。
那么为了达到这个目的，要先new一个出来，然后对其的私有变量进行赋值，这样子才是正确的
```
TListaPos::TListaPos(const TListaPos &t)
{
// error here when copy constructor
// this->pos = t.pos;
// no error
this->pos = new TNodoCalendario();
this->pos->c = t.pos->c;
this->pos->siguiente = t.pos->siguiente;
}
```
#### 析构函数
因为只有一个私有变量，只需要重新赋值为空指针防止异常就好了
```
TListaPos::~TListaPos()
{
this->pos = nullptr;
}
```
#### 赋值重载
和前面的实现大同小异，不多讲
```
TListaPos &TListaPos::operator=(const TListaPos &tl)
{
if (this == &tl)
{
return *this;
}
this->~TListaPos();
this->pos = tl.pos;
return *this;
}
```
#### 等号运算符重载
这个函数是用来判断两个对象是否相等的，如果相等的话返回true，否则返回false。类中只有一个私有变量，所以只需要判断这个私有变量是否相等就好了
```
bool TListaPos::operator==(const TListaPos &tl) const
{
if (this->pos == tl.pos)
{
return true;
}
return false;
}
```
#### 不等号运算符重载
```
bool TListaPos::operator!=(const TListaPos &tl) const
{
if (this->pos != tl.pos)
{
return true;
}
return false;
}
```
#### 获取下一个节点
这个函数是用来获取下一个节点的，因为这个类的私有变量是一个指针，所以我们可以通过这个指针来获取下一个节点。
首先要生面一个临时的对象，然后将当前对象的指针赋值给临时对象的指针，然后判断当前对象的指针是否为空，如果不为空的话，那么就将临时对象的指针指向当前对象的指针的下一个节点，然后返回这个临时对象。
要知道c++是面对对象语言。因此可以在调用的时候无限调用，这样子就会一直获取下一个节点，但是如果下一个节点是空的话，那么就会出现异常，所以在这里要进行判断，如果下一个节点是空的话，那么就返回一个空的对象
```
TListaPos TListaPos::Siguiente() const
{
TListaPos temp;
TNodoCalendario *temp_node = this->pos;
if (temp_node == nullptr) // evitar problema de segmentation fault de que llamar varias veces a siguiente
{
return temp;
}
if (this->pos->siguiente != nullptr)
{
temp.pos = this->pos->siguiente;
}
return temp;
}
```
#### 判断当前节点是否为空
这个函数是用来判断当前节点是否为空的，如果为空的话，那么就返回true，否则返回false。因为私有变量是一个指针，所以只需要判断这个指针是否为空就好了
```
bool TListaPos::EsVacia() const
{
if (this->pos == nullptr)
{
return true;
}
return false;
}
```
#### 友元重载输出运算符
作业要求的输出格式，大家看看就好了
```
ostream &operator<<(ostream &os, const TListaCalendario &tl)
{
os << "<";
TListaPos temp = tl.Primera();
while (!temp.EsVacia())
{
os << tl.Obtener(temp);
temp = temp.Siguiente();
if (!temp.EsVacia())
{
os << " ";
}
}
os << ">";
return os;
}
```
到这里为止我们已经完成了第二个类的实现，接下来就是最重要的链表类的实现了
## TListaCalendario 链表
这个类是我们的链表类，我们需要通过这个类来进行链表的操作，包括但不限于查找，删除，插入等等。
首先声明的是这个类的私有成员，这个私有成员是一个指针，指向链表的头节点
```
TNodoCalendario *primero;
```
然后就是这个类的构造函数，析构函数，深拷贝函数和赋值函数等等其他的函数
大家慢慢看，我就不多说了
#### 构造函数
因为私有变量是一个指针，所以要进行空指针初始化
```
TListaCalendario::TListaCalendario()
{
primero = nullptr;
}
```
#### 深拷贝函数
这里当时写的时候理了好久，因为没有对深拷贝理解透彻，导致了内存泄漏，所以在这里要注意，对于指针的深拷贝，要先new一个出来，然后对其进行赋值，这样子才是正确的。因为这个类是一个链表，那么传入的参数也是一个链表，所以要对传入的链表进行遍历，然后将每一个节点都插入到新的链表中。
其中我用到的Insertar函数，这个是在待会的插入函数中实现的。
实现过程为，首先声明一个临时的指针，然后将传入的链表的头节点赋值给这个临时指针，然后进行遍历，将每一个节点都插入到新的链表中，最后返回这个新的链表。当然这里不用delete掉这个临时指针，因为这个指针是在函数内部声明的，函数结束后会自动释放内存
```
TListaCalendario::TListaCalendario(const TListaCalendario &tl)
{
this->primero = nullptr;
TNodoCalendario *temp = tl.primero;
while (temp != nullptr)
{
this->Insertar(temp->c);
temp = temp->siguiente;
}
delete temp;
}
```
#### 析构函数
说实话析构函数不应该这么写的，应该先判断是否为空，然后再进行删除操作，但是我这里是直接删除了，偷了一下懒。正常要先判断是否为空，然后再进行删除操作，再然后将指针赋值为空指针
```
TListaCalendario::~TListaCalendario()
{
delete this->primero;
this->primero = nullptr;
}
```
#### 赋值函数
和深拷贝差不多，不过返回值是一个引用，因为我们要对当前对象进行赋值操作，所以要返回一个引用，这样子才能对当前对象进行赋值操作。这里也用到了Insertar函数，这个函数是在待会的插入函数中实现的。
```
TListaCalendario &TListaCalendario::operator=(const TListaCalendario &tl)
{
if (this == &tl)
{
return *this;
}
this->~TListaCalendario();
TNodoCalendario *temp = tl.primero;
while (temp != nullptr)
{
this->Insertar(temp->c);
temp = temp->siguiente;
}
delete temp;
return *this;
}
```
#### 等于运算符重载
这个函数是用来判断两个对象是否相等的，如果相等的话返回true，否则返回false。
从这里开始就需要用到TListaPos这个类了，因为我们要对链表进行遍历，那么就需要一个指针来指向当前节点，然后进行遍历，判断每一个节点是否相等，如果有一个不相等的话，那么就返回false，否则返回true。
不过在那之前，只要两个链表的长度不一样，那么就可以直接返回false了，因为长度不一样的话，那么就不可能相等了。
那么这里实现具体的方式为，使用Primera函数来获取第一个节点，然后使用Siguiente函数来获取下一个节点，然后使用Obtener函数来获取当前节点的值，然后进行比较，如果有一个不相等的话，那么就返回false，否则返回true。在此期间用while循环来进行遍历，直到遍历完所有的节点
```
bool TListaCalendario::operator==(const TListaCalendario &tl) const
{
// comprobar la longitud
if (this->Longitud() != tl.Longitud())
{
return false;
}
TListaPos temp1 = this->Primera();
TListaPos temp2 = tl.Primera();
while (!temp1.EsVacia() && !temp2.EsVacia())
{
if (this->Obtener(temp1) != tl.Obtener(temp2))
{
return false;
}
temp1 = temp1.Siguiente();
temp2 = temp2.Siguiente();
}
return true;
}
```
#### + 运算符重载
这个函数是用来将两个链表进行合并的，返回一个新的链表。这个函数的实现方式为，首先声明一个新的链表，然后将当前链表的头节点赋值给这个新的链表，然后进行遍历，将传入的链表的每一个节点都插入到新的链表中，最后返回这个新的链表。
这里也用到Insertar函数。然后有一点要注意的是，这里的传入参数是一个const的引用，因为我们不需要对传入的参数进行修改，所以要加上const，然后返回值是一个新的链表，所以要返回一个新的链表，这样子才能返回一个新的链表。
另外用TListaCalendario类中的primero变量来进行遍历，这样子就可以遍历到最后一个节点，然后将最后一个节点的下一个节点赋值为空指针，这样子就可以避免野指针了。
要理解这个操作首先要理解什么是链表。
在我看来，链表就是一个一个的节点，每一个节点都有一个指针指向下一个节点，那么我们要遍历这个链表的话，就要从头节点开始，然后一个一个的往下遍历，直到最后一个节点。
要怎么知道最后一个节点呢？那就是最后一个节点的下一个节点的指针肯定就是空指针，
另外这个重载最主要的功能就是将两个链表进行合并，那么就要将传入的链表的每一个节点都插入到新的链表中，这样子就可以将两个链表合并成一个新的链表了。
```
TListaCalendario TListaCalendario::operator+(const TListaCalendario &tl) const
{
TListaCalendario result(*this);
TNodoCalendario *temp = tl.primero;
while (temp != nullptr)
{
result.Insertar(temp->c);
temp = temp->siguiente;
}
delete temp;
return result;
}
```
#### - 运算符重载
这个函数是用来将两个链表进行差集操作的，返回一个新的链表。这个函数的实现方式为，首先声明一个新的链表，然后将当前链表的头节点赋值给这个新的链表，然后进行遍历，将传入的链表的每一个节点都删除掉，最后返回这个新的链表。
这里用到Borrar函数。待会会实现，先看这里。
和上面的+运算符重载一样的操作，不过插入变成了删除，这样子就可以将两个链表进行差集操作了
```
TListaCalendario TListaCalendario::operator-(const TListaCalendario &tl) const
{
TListaCalendario result(*this);
TNodoCalendario *temp = tl.primero;
while (temp != nullptr)
{
result.Borrar(temp->c);
temp = temp->siguiente;
}
delete temp;
return result;
}
```
#### 插入
插入函数有一点长，但是不难
然后要判断当前链表是否为空，如果为空的话，那么就直接插入到头节点，然后返回true。
另外还要判断当前节点应该插入到哪里
如果当前节点小于头节点的话，那么就插入到头节点，然后返回true。
如果插入是在最后的话，那么就插入到最后，然后返回true。
如果插入在中间的话，这里就需要用到小于运算符重载了，这个函数是用来判断两个节点的大小的，如果当前节点小于传入的节点的话，那么就返回true，否则返回false。小于运算符的实现方式再在第一篇中有过提交。
有点复杂，不过就是插入到头，中，尾三个地方，然后返回true，如果插入失败的话，那么就返回false
传入的参数是一个日期类，因为我们要插入的是一个日期类。在第一篇中已经实现了这个类，有兴趣的可以去看一下
```
bool TListaCalendario::Insertar(const TCalendario &tc)
{
TNodoCalendario *temp = primero;
/*comprobar siexiste el elemento en la lista or no*/
while (temp != nullptr)
{
if (temp->c == tc)
{
return false;
}
temp = temp->siguiente;
}
delete temp;
TNodoCalendario *new_node = new TNodoCalendario();
new_node->c = tc;
// si la esta esta vacia
if (primero == nullptr)
{
this->primero = new_node;
return true;
}
// si el nodo debe de ir al principio
if (tc < this->primero->c)
{
new_node->siguiente = primero;
primero = new_node;
return true;
}
// nodo en medio o al final
TNodoCalendario *before_node = primero;
TNodoCalendario *now_node = primero->siguiente;
while (now_node != nullptr && !(tc < now_node->c))
{
before_node = now_node;
now_node = now_node->siguiente;
}
before_node->siguiente = new_node;
new_node->siguiente = now_node;
return true;
}
```
#### 删除函数 （传入参数为一个日期类）
删除首先就要判断的是当前链表是否为空，如果为空的话，那么就直接返回false，因为没有东西可以删除。
如果当前需要删除的节点在头节点的话，那么就直接删除头节点，然后返回true。
另外就是在中和尾的情况，这里就需要用到等于运算符重载了，这个函数是用来判断两个节点是否相等的，如果相等的话返回true（删除成功），否则返回false。等于运算符的实现方式再在第一篇中有过提交。
```
bool TListaCalendario::Borrar(const TCalendario &tc)
{
TNodoCalendario *temp = this->primero;
TNodoCalendario *temp_delete = nullptr;
// check if is first node
if (temp != nullptr && tc == temp->c)
{
temp_delete = temp;
this->primero = temp->siguiente;
delete temp_delete;
return true;
}
while (temp != nullptr && temp->siguiente != nullptr)
{
if (tc == temp->siguiente->c)
{
temp_delete = temp->siguiente;
temp->siguiente = temp->siguiente->siguiente;
delete temp_delete;
return true;
}
temp = temp->siguiente;
}
return false;
}
```
#### 删除函数 （传入参数为一个TListaPos类）
这个函数好像有一个坑，但是我找不到问题出现在哪里，不过向我这么写的话也是可以的。
首先要判断的是当前TlistaPost是否为空，如果为空的话，那么就直接返回false。用到了EsVacia函数，这个函数是用来判断当前节点是否为空的，如果为空的话，那么就返回true，否则返回false。
另外如果不为空，就进行删除操作，首先指针指向当前节点的日期，然后调用删除函数，将当前节点的日期删除，然后返回true。
因为删除函数我们已经实现，就是上面的那个删除函数，所以这里可以进行删除的操作。在返回true前，要进行一个析构操作，这个操作是用来释放内存的，如果不进行析构操作的话，那么就会出现内存泄漏，这里导致了我一下午查找bug，最后才发现是这里的问题。
不过我也不知道为什么会出现这个问题。
此问题出现的时机为，当要删除一个已经删除的了TlistPos后会出现一个segmentation fault。当我使用debug模式的时候又不会出现，程序会运行到结束，没有错误，真是奇怪。希望又大神可以帮我解答一下这个问题为什么会出现这个问题
```
bool TListaCalendario::Borrar(const TListaPos &tl)
{
// // 这里好像是个错误
if (tl.EsVacia())
{
return false;
}
TCalendario tc = tl.pos->c;
if (!tl.EsVacia())
{
if (this->Borrar(tc))
{
tl.~TListaPos(); // muy importante este linea
// este destructor es para liberar la memoria de la posición borrada. Si no lo hace, al hacer la operacion de borrar varias veces la misma posición, se va a producir un error de segmentación.
return true;
}
return false;
}
return false;
}
```
#### 删除函数（传入参数为一个日期）
第三个删除操作的重载，这里传入的参数为三个整数，分别是年月日，这个函数的实现方式和上面的删除函数一样，只是传入的参数不一样而已，其他的都一样
```
bool TListaCalendario::Borrar(const int day, const int month, const int year)
{
TNodoCalendario *temp = this->primero;
TNodoCalendario *temp_delete = nullptr;
// copy constructor to asign Tcalendario
TCalendario tc(day, month, year, nullptr);
/*
obtener nodo hasta la fecha pasada, luego asignar this
*/
while (temp != nullptr)
{
if (temp->c < tc)
{
temp_delete = temp;
}
temp = temp->siguiente;
}
// cout << "tempd: "<< temp_delete->c << endl;
if (temp_delete != nullptr)
{
this->primero = temp_delete->siguiente;
return true;
}
return false;
}
```
#### 判断当前节点是否为空
对当前私有变量的指针进行判断，如果为空的话，那么就返回true，否则返回false
```
bool TListaCalendario::EsVacia() const
{
if (this->primero == nullptr)
{
return true;
}
return false;
}
```
#### 获取节点日期
传入参数为一个TListaPos类，这个函数是用来获取当前节点的日期的，首先要判断当前节点是否为空，如果为空的话，那么就返回一个空的日期类，否则返回当前节点的日期
```
TCalendario TListaCalendario::Obtener(const TListaPos &tl) const
{
TCalendario c;
if (tl.pos != nullptr)
{
c = tl.pos->c;
}
return c;
}
```
#### 查找函数
这个函数是用来查找当前链表中是否存在这个节点的，如果存在的话，那么就返回true，否则返回false。实现方式为，首先声明一个临时的指针，然后将当前链表的头节点赋值给这个临时指针，然后进行遍历，判断每一个节点是否等于传入的参数，如果有一个等于的话，那么就返回true，否则返回false。
传入参数为一个日期类。
```
bool TListaCalendario::Buscar(const TCalendario &tc) const
{
TNodoCalendario *temp = new TNodoCalendario();
while (temp != nullptr)
{
if (temp->c == tc)
{
return true;
}
temp = temp->siguiente;
}
delete temp;
return false;
}
```
#### 获取长度，头节点，尾节点函数
这三个函数是用来获取当前链表的长度，头节点和尾节点的，实现方式为，首先声明一个整型变量，然后将当前链表的头节点赋值给一个临时的指针，然后进行遍历，每遍历一个节点，那么就将这个整型变量加一，最后返回这个整型变量。
```
int TListaCalendario::Longitud() const
{
int size = 0;
TNodoCalendario *temp = primero;
while (temp != nullptr)
{
size++;
temp = temp->siguiente;
}
delete temp;
return size;
}
// // Devuelve la primera posición en la lista
TListaPos TListaCalendario::Primera() const
{
TListaPos first;
first.pos = this->primero;
return first;
}
// // Devuelve la última posición en la lista
TListaPos TListaCalendario::Ultima() const
{
TListaPos result;
if (primero == nullptr)
{
return result;
}
TNodoCalendario *temp = primero;
while (temp->siguiente != nullptr)
{
temp = temp->siguiente;
}
result.pos = temp;
return result;
}
```
#### 其他函数
作业的其他要求，大家看看就好了
```
TListaCalendario TListaCalendario::SumarSubl(const int I_L1, const int F_L1, TListaCalendario &L2, const int I_L2, const int F_L2)
{
TListaCalendario result;
TListaCalendario *temp_L1 = new TListaCalendario(*this);
TListaCalendario *temp_L2 = new TListaCalendario(L2);
result = temp_L1->ExtraerRango(I_L1, F_L1) + temp_L2->ExtraerRango(I_L2, F_L2);
delete temp_L1;
delete temp_L2;
return result;
}
TListaCalendario TListaCalendario::ExtraerRango(int n1, const int n2)
{
TListaCalendario result; // Lista para almacenar el rango extraído
TNodoCalendario *temp = this->primero; // variable temporal para recorrer la lista
TListaCalendario *temp2 = new TListaCalendario(*this); // copia de la lista original
int count = 1; // count para contar la posición actual
if (n1 > n2)
{
return result; // lista vacia
}
if (n1 < 0)
{
n1 = count;
}
/*
idea: Se obtiene hasta nodo de n1, hay que tener en cuenta tambien que no sobrepase de temp(segmentation fault). Obtenido n1, ahora utilizo mismo proceso que ante hasta n2. Inserto nodo desde rango n1 y n2. Finaliza cuando temp es nullptr y count = n2
*/
// hasta el rango den1
while (temp != nullptr && count < n1)
{
temp = temp->siguiente;
count++;
}
// desde rango n1 hasta n2
while (temp != nullptr && count <= n2)
{
result.Insertar(temp->c);
temp = temp->siguiente;
count++;
}
// Brrar todos nodos de la lista original
this->~TListaCalendario();
// asignar la lista original con la copia de la lista original menos el rango extraido
*this = *temp2 - result;
delete temp;
return result;
}
``` 不要求线程安全了，好歹上个template啊:lol 感谢楼主的讲解，学到了很多 感谢分享，后续会有更新其他数据结构的代码吗，比如二叉树啥的 TheKen 发表于 2024-4-28 08:47
感谢分享，后续会有更新其他数据结构的代码吗，比如二叉树啥的
下一篇就是二叉树然后下下一篇是平衡二叉树 {:1_893:}感谢分享 感谢分享，现在学习中。 写的非常好，由浅入深，举的例子也很容易理解，正在学习中，感谢！
页:
[1]