今天把单向链表写了一下。(超了预计时间一个小时才写完QAQ)
在这里记录一下吧。
后面加了几个函数，为了加强对指针的理解。代码我还在测试，所以可能会有BUG。欢迎指正。
代码实现
#pragma once
#include <iostream>
using namespace std;
struct Node //链表的节点
{
int value;
Node* next;
Node(int n = 0) :value(n), next(nullptr) { }
};
class List
{
private:
int SIZE;
Node* head;
public:
/*构造、析构*/
List(); //构建一个单链表;
~List(); //销毁一个单链表;
/*链表信息*/
int size() { return SIZE; }
bool empty() { return SIZE == 0 ? true : false; }
Node* begin() { return head->next; }
/*查找*/
Node* find(int data); //查找节点
/*插入*/
void push_back(int data); //在尾部插入指定的元素
Node* insert(int i, int data); //在指定位置插入指定元素
Node* insert(Node* node, int data);
void push_front(int data); //在头部插入指定元素
/*删除*/
void pop_back(); //在尾部删除元素
void clear(); //删除所有数据
Node* erase(int data); //删除指定的数据
Node* erase(Node* node);
Node* remove(int ith);
void pop_front(); //在头部删除节点
/*其他*/
void traval(); //遍历线性表
void reverse(); //反转链表
bool IsCircle(); //检测链表中是否含有环
void merge(List a); //合并两个有序链表
Node* middle(); //寻找链表中间节点
};
/*****************************************************************
Function:List
Description：构造函数，主要是初始化size、实例化头指针head。
*****************************************************************/
inline List::List()
{
SIZE = 0;
head = new Node();
}
/*****************************************************************
Function:List
Description：析构函数，主要是释放链表的空间。
*****************************************************************/
inline List::~List()
{
Node* tmp = head->next;
while (SIZE > 0)
tmp = erase(tmp);
delete head;
}
/*****************************************************************
Function:find
Description：遍历查找值为data的节点。
*****************************************************************/
inline Node* List::find(int data)
{
Node* tmp = head->next;
while (tmp != nullptr)
{
if (tmp->value == data)
return tmp;
tmp = tmp->next;
}
return nullptr;
}
/*****************************************************************
Function:push_back
Description：在链表最后面插入一个节点。
*****************************************************************/
inline void List::push_back(int data)
{
Node* tmp = head;
while (tmp->next != nullptr)
tmp = tmp->next;
Node* add = new Node(data);
tmp->next = add;
SIZE++;
return;
}
/*****************************************************************
Function:insert
Description：在第i个节点后插入值data。
*****************************************************************/
inline Node* List::insert(int i, int data)
{
if (i > SIZE || i < 0)
return nullptr;
Node* tmp = head;
for (int j = 0; j < i; j++)
tmp = tmp->next;
Node* add = new Node(data);
add->next = tmp->next;
tmp->next = add;
SIZE++;
return add;
}
/*****************************************************************
Function:insert
Description：在node节点后插入值data。
*****************************************************************/
inline Node* List::insert(Node* node, int data)
{
if (node == nullptr)
return nullptr;
Node* add = new Node(data);
add->next = node->next;
node->next = add;
SIZE++;
return add;
}
/*****************************************************************
Function:push_front
Description：在最开始的节点前插入一个节点。
*****************************************************************/
inline void List::push_front(int data)
{
insert(head, data);
return;
}
/*****************************************************************
Function:pop_back
Description：删除最后一个节点。
*****************************************************************/
inline void List::pop_back()
{
if (SIZE == 0)
return;
Node* tmp = head->next;
while (tmp->next != nullptr)
tmp = tmp->next;
erase(tmp);
return;
}
/*****************************************************************
Function:clear
Description：清空链表。
*****************************************************************/
inline void List::clear()
{
Node* tmp = head->next;
while (SIZE > 0)
tmp = erase(tmp);
return;
}
/*****************************************************************
Function:erase
Description：删除指定的数据。
*****************************************************************/
inline Node* List::erase(int data)
{
return erase(find(data));
}
/*****************************************************************
Function:erase
Description：删除node节点的数据。
*****************************************************************/
inline Node* List::erase(Node* node)
{
if (node == nullptr)
return nullptr;
Node* prev = head;
while (prev != nullptr && prev->next != node)
prev = prev->next;
prev->next = node->next;
delete node;
SIZE--;
return prev->next == nullptr ? prev : prev->next;
}
/*****************************************************************
Function:remove
Description：删除第ith个数据。
*****************************************************************/
inline Node* List::remove(int ith)
{
if (ith > SIZE || ith <= 0)
return nullptr;
Node* tmp = head;
for (int i = 0; i < ith; i++)
tmp = tmp->next;
return erase(tmp);
}
/*****************************************************************
Function:pop_front
Description：删除第一个节点。
*****************************************************************/
inline void List::pop_front()
{
erase(head->next);
return;
}
/*****************************************************************
Function:traval
Description：遍历链表。
*****************************************************************/
inline void List::traval()
{
if (SIZE == 0)
return;
Node* tmp = head->next;
while (tmp != nullptr)
{
std::cout << tmp->value << " ";
tmp = tmp->next;
}
return;
}
/*****************************************************************
Function:reverse
Description：反转链表
*****************************************************************/
void List::reverse()
{
if (SIZE <= 1)
return;
//定义三个指针来遍历修改
Node* prev = nullptr;
Node* cur = head->next;
Node* nex = cur->next;
while (nex != nullptr)
{
cur->next = prev;
prev = cur;
cur = nex;
nex = nex->next;
}
cur->next = prev;
head->next = cur;
return;
}
/*****************************************************************
Function: IsCircle
Description：利用快慢指针判断链表中是否有环。若两个指针在链表中
相遇了，就说明链表中含有环。
*****************************************************************/
inline bool List::IsCircle()
{
Node* fast = head->next;
Node* slow = head->next;
while (fast != slow) //快慢指针相遇说明没有终点
{
if (fast->next == nullptr || fast->next->next == nullptr)
return false; //有终点一定没有环
fast = fast->next->next;
slow = slow->next;
}
return true;
}
/*****************************************************************
Function: merge
Description：合并两个有序链表
*****************************************************************/
inline void List::merge(List a)
{
List tmp = *this;
Node* p1 = tmp.head->next;
Node* p2 = a.head->next;
clear(); //清空，方便赋值
while (p1 != nullptr && p2 != nullptr)
{
if (p1->value < p2->value)
push_back(p1->value);
else
push_back(p2->value);
p1 = p1->next;
p2 = p2->next;
}
while (p1 != nullptr)
{
push_back(p1->value);
p1 = p1->next;
}
while (p2 != nullptr)
{
push_back(p2->value);
p2 = p2->next;
}
tmp.~List();
return;
}
/*****************************************************************
Function: middle
Description：利用快慢指针寻找中间节点
*****************************************************************/
inline Node * List::middle()
{
Node* fast = head->next;
Node* slow = head->next;
while (fast != nullptr)
{ //快指针到重点了，慢指针指向的就是中点
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
