单链表演示图：
创新互联公司于2013年成立，先为五家渠等服务建站，五家渠等地企业，进行企业商务咨询服务。为五家渠企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
单链表结构体：
struct Node
{
Node(const DataType& d)//节点的构造函数
:_data(d)
,_next(NULL)
{}
DataType _data; //数据
struct Node *_next; //指向下一个节点的指针
};带头结点和尾节点的单链表：
多一个Tail指针的好处就是很方便可以找到链表尾部，方便在尾部插入一个元素什么的。
下面我们用类来实现单链表：
class SList
{
friend ostream& operator<<(ostream& os, const SList& s); //输出运算符重载(友元)
public:
SList() //构造函数
:_head(NULL)
,_tail(NULL)
{}
SList(const SList& s) //拷贝构造
:_head(NULL)
, _tail(NULL)
{
Node *cur = _head;
while (cur)
{
PushBack(cur->_data );
cur = cur->_next;
}
_tail = cur;
}
~SList() //析构函数
{
if (_head == NULL)
return;
Node *cur = _head;
if (cur != NULL)
{
Node *del = cur;
cur = cur->_next;
delete del;
}
_tail = NULL;
_head = NULL;
}
SList& operator=(SList s) //赋值运算符重载
{
swap(_head, s._head);
swap(_tail, s._tail);
return *this;
}单链表最基本的四个函数：
void SList::PushBack(const DataType& d) //尾插
{
Node *newNode = new Node(d); //构建一个新的节点
if (_head == NULL)
{
_head = newNode;
_tail = newNode;
}
else
{
_tail->_next = newNode;
_tail = newNode;
}
}
void SList::PushFront(const DataType& d) //头插
{
Node *newNode = new Node(d);
if (_head == NULL)
{
_head = newNode;
_tail = newNode;
}
else
{
newNode->_next = _head;
_head = newNode;
}
}
void SList::PopBack() //尾删
{
if (_head == NULL)
return;
else if (_head == _tail)
{
delete _tail;
_tail = NULL;
_head = NULL;
}
else
{
Node *cur = _head;
while (cur->_next != _tail)
{
cur = cur->_next;
}
delete _tail;
_tail = cur;
_tail->_next = NULL;
}
}
void SList::PopFront() //头删
{
if (_head == NULL)
return;
else if (_head == _tail)
{
delete _tail;
_tail = NULL;
_head = NULL;
}
else
{
Node *del = _head;
_head = _head->_next;
delete del;
}
}给一个数据，若找到该节点则返回该节点，没找到则返回NULL
Node* SList::Find(const DataType& d)
{
Node *cur = _head;
while (cur != NULL)
{
if (cur->_data == d)
return cur;
cur = cur->_next;
}
return NULL;
}给定一个节点，在该节点后插入一个新的节点
void SList::Insert(Node* pos, const DataType& d)
{
Node *newNode = new Node(d);
if (pos == _tail) //若给定的节点是尾节点，此处可以直接调用尾插
{
_tail->_next = newNode;
_tail = newNode;
}
else
{
newNode->_next = pos->_next;
pos->_next = newNode;
}
}链表的逆序：此处用三个指针来实现
void SList::Reverse()
{
Node *p1 = NULL;
Node *p2 = _head;
Node *newhead = NULL;
while (p2)
{
p1 = p2;
p2 = p2->_next;
p1->_next = newhead;
newhead = p1;
}
_head = newhead;
}链表的排序：采用冒泡排序
void SList::Sort()
{
Node *cur = _head;
Node *end = NULL;
while (cur != end)
{
while (cur->_next != end)
{
if (cur->_data > cur->_next->_data)
{
DataType tmp = cur->_data;
cur->_data = cur->_next->_data;
cur->_next->_data = tmp;
}
cur = cur->_next;
}
end = cur;
cur = _head;
}
}删除某个节点（给定一个数据，删除数据与之相等的第一个节点）
void SList::Remove(const DataType& d)
{
Node *cur = _head;
while (cur != NULL)
{
if (cur->_data == d)
{
Node *del = cur->_next;
DataType tmp = cur->_data;
cur->_data = cur->_next->_data;
cur->_next->_data = tmp;
cur->_next = cur->_next->_next;
delete del;
return;
}
cur = cur->_next;
}
}删除某些节点（给定一个数据，删除数据与之相等的每一个节点）
void SList::RemoveAll(const DataType& d)
{
Node *cur = _head;
while (cur != NULL)
{
if (cur->_data == d)
{
Node *del = cur->_next;
DataType tmp = cur->_data;
cur->_data = cur->_next->_data;
cur->_next->_data = tmp;
cur->_next = cur->_next->_next;
delete del;
}
cur = cur->_next;
}
return;
}删除非尾节点
void SList::EarseNotTail(Node *pos)
{
Node *del = pos;
Node *cur = _head;
while (cur->_next!=pos) //找到该节点的前一个节点
{
cur = cur->_next;
}
cur->_next = pos->_next; //让它的_next指向要删除节点的_next
delete del;
}找到中间节点
Node* SList::FindMinNode() //快慢指针问题
{ //两个指针都指向头结点
Node *cur = _head; //快的一次走两步，慢的一次走一步
Node *fast = cur; //当快指针走到尾的时候，慢指针指向中间节点
Node *slow = cur;
while (fast)
{
fast = fast->_next->_next;
slow = slow->_next;
}
return slow;
}删除倒数第K个节点
void SList::DelKNode(int k)
{
Node *cur = _head;
int i = k - 1;
while (i) //先让cur指向正数第K个节点
{
cur = cur->_next;
i = i - 1;;
}
Node *p1 = _head;
Node *tmp = NULL;
while (cur->_next ) //让一个指向头结点的指针和cur一起走
{
tmp = p1;
p1 = p1->_next;
cur = cur->_next; //当cur指向尾节点时，那个指针指向倒第K个节点
}
Node *del = p1;
tmp->_next = p1->_next ;
delete p1;
}检测是否带环
//检测是否带环
int SList::CheckCycle(const SList& s) //快慢指针问题
{
Node *fast = _head;
Node *slow = _head;
while (slow)
{
if (slow == fast)
{
return 1;
}
fast = fast->_next->_next;
slow = slow->_next;
}
return 0;
}获取环的入口点
Node* SList::GetCycleEoryNode()
{
Node *cur = _head;
while (cur)
{
if (cur == _tail)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}判断是否相交
int SList::CheckCross(SList& l1, SList& l2)
{
int count1 = l1.LengthOfList(l1);
int count2 = l2.LengthOfList(l2);
if (count1 > count2)
{
Node *cur = l1._head;
while (cur)
{
if (l2._tail == cur)
return 1;
cur = cur->_next;
}
}
else
{
Node *cur = l2._head;
while (cur)
{
if (l1._tail == cur)
return 1;
cur = cur->_next;
}
}
return 0;
}合并两个链表
int SList::CheckCross(SList& l1, SList& l2)
{
int count1 = l1.LengthOfList(l1);
int count2 = l2.LengthOfList(l2);
if (count1 > count2)
{
Node *cur = l1._head;
while (cur)
{
if (l2._tail == cur)
return 1;
cur = cur->_next;
}
}
else
{
Node *cur = l2._head;
while (cur)
{
if (l1._tail == cur)
return 1;
cur = cur->_next;
}
}
return 0;
}求两个链表的交点
Node* SList::GetLinkCross(SList& l1, SList& l2)
{
int count1 = l1.LengthOfList(l1);
int count2 = l2.LengthOfList(l2);
Node *cur1 = l1._head;
Node *cur2 = l2._head;
if (count1 > count2)
{
Node *cur1 = l1._head;
Node *cur2 = l2._head;
while (cur2)
{
if (cur2->_next == cur1->_next )
return cur1;
else
{
cur1 = cur1->_next;
cur2 = cur2->_next;
}
}
}
else
{
Node *cur1 = l1._head;
Node *cur2 = l2._head;
while (cur1)
{
if (cur2->_next == cur1->_next)
return cur1;
else
{
cur1 = cur1->_next;
cur2 = cur2->_next;
}
}
}
return NULL;
}求链表长度
int SList::LengthOfList(const SList& s)
{
int length = 0;
Node *cur = _head;
while (cur)
{
length++;
cur = cur->_next;
}
return length;
}
以后会有改进版奉上，希望大家多多支持
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
本文题目：线性表--单链表(C++)-创新互联
分享链接：
http://cdkjz.cn/article/cdjehc.html
