线性表--单链表(C++)

单链表演示图：

单链表结构体：

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;

}

以后会有改进版奉上，希望大家多多支持