今天的作业中有链表相关的题目,所以就顺手写了一个双向链表。在这里记录一下我写的链表吧。
(没什么好说的直接上代码吧)
代码实现
#include <iostream>
struct Node
{
int value;
Node* previous;
Node* next;
Node() :value(0), previous(nullptr), next(nullptr) { }
};
class MyList
{
private:
size_t SIZE;
Node* head;
Node* tail;
public:
/*构造、析构*/
MyList();
~MyList();
/*插入、删除*/
void insert(Node* node, int data);//在结点node后插入数据data
void insert_prev(Node* node, int data);//在结点node前插入数据data
void push_back(int data);//在最后加入节点
Node* erase(Node* node);//删除node结点
void pop_back();//删除最后一个节点
/*查找*/
Node* find(int data);//查找链表中数据为data的结点
Node* search(int ith);//查找链表中第ith个结点
/*链表信息*/
int size() { return SIZE; }
bool empty() { return SIZE == 0; }
Node* begin() { return head; }
Node* end() { return tail; }
/*其他*/
void display();
void clear();
};
/*****************************************************************
Function:MyList
Description:构造函数,主要是初始化size、实例化头结点、初始化
头指针head和尾指针tail。
*****************************************************************/
inline MyList::MyList()
{
SIZE = 0;
head = new Node();
tail = head;
}
/*****************************************************************
Function:~MyList
Description:析构函数,主要是释放链表的空间。
*****************************************************************/
inline MyList::~MyList()
{
while (SIZE > 0)
erase(tail);
delete head;
}
/*****************************************************************
Function:insert
Description:在node节点后插入值data。
*****************************************************************/
inline void MyList::insert(Node* node, int data)
{
if (node == nullptr)
return;
Node* tmp = new Node();
tmp->value = data;
if (node->next != nullptr)
{//如果node不为末节点就修改node后一个节点
tmp->next = node->next;
node->next->previous = tmp;
}
//处理node和tmp的关系
node->next = tmp;
tmp->previous = node;
//如果node是末节点,则将tail修改为tmp
if (node == tail)
tail = tmp;
SIZE++;
return;
}
/*****************************************************************
Function:insert_prev
Description:在node节点前插入值data。
*****************************************************************/
inline void MyList::insert_prev(Node* node, int data)
{
if (node == nullptr || node == head)
return;
Node* tmp = new Node();
tmp->value = data;
if (node->previous != nullptr)
{//如果node不为头节点就修改node前一个节点
tmp->previous = node->previous;
node->previous->next = tmp;
}
//处理node和tmp的关系
node->previous = tmp;
tmp->next = node;
SIZE++;
return;
}
/*****************************************************************
Function:push_back
Description:在链表最后面插入一个节点。
*****************************************************************/
inline void MyList::push_back(int data)
{
insert(tail, data);
return;
}
/*****************************************************************
Function:erase
Description:从链表中删除node节点,返回下一节点的指针。
*****************************************************************/
inline Node* MyList::erase(Node* node)
{
if (node == nullptr)
return tail;
Node* tmp = node->next;
//分三种情况,node为head,node为tail,以及node在中间
if (node == tail)
{
node->previous->next = nullptr;
tail = node->previous;
}
else
{
node->previous->next = node->next;
node->next->previous = node->previous;
}
//调整完node前后节点的关系即可删除node节点
delete node;
SIZE--;
return tmp;
}
/*****************************************************************
Function:puop_back
Description:删除链表最后一个节点。
*****************************************************************/
inline void MyList::pop_back()
{
if (SIZE == 0)
return;
erase(tail);
return;
}
/*****************************************************************
Function:find
Description:遍历查找值为data的节点。
*****************************************************************/
inline Node* MyList::find(int data)
{
Node* tmp = head->next;
while (tmp != nullptr)
{
if (tmp->value == data)
return tmp;
tmp = tmp->next;
}
return nullptr;
}
/*****************************************************************
Function:search
Description:遍历查找第ith个节点。
*****************************************************************/
inline Node* MyList::search(int ith)
{
if (ith > SIZE || ith < 1)
return nullptr;
Node* tmp = head;
for (int i = 0; i < ith; i++)
tmp = tmp->next;
return tmp;
}
/*****************************************************************
Function:display
Description:遍历输出链表。
*****************************************************************/
inline void MyList::display()
{
Node* tmp = head->next;
while (tmp != nullptr)
{
std::cout << tmp->value << " ";
tmp = tmp->next;
}
return;
}
/*****************************************************************
Function:clear
Description:清空链表。
*****************************************************************/
inline void MyList::clear()
{
while (SIZE > 0)
erase(tail);
return;
}
我简单地测试了一下似乎没什么问题。单向链表后面再补吧。
随便写写
在写双向链表的时候我遇到了一个error LNK2005,我把所有的函数都加上 inline 修饰词后就没事了。猜测可能是我写在两个cpp文件导致的。具体原因找到在写下来吧。(之前写模板类好像没出过这个问题)
这个错误似乎是重复定义了一些变量。我把函数声明和定义放在 .h 文件里面就不会了。