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

2025-01-22 技术教程

单链表演示图：

单链表结构体：

structNode{Node(constDataType&d)//节点的构造函数:_data(d),_next(NULL){}DataType_data;//数据structNode*_next;//指向下一个节点的指针};

带头结点和尾节点的单链表：

多一个Tail指针的好处就是很方便可以找到链表尾部，方便在尾部插入一个元素什么的。

下面我们用类来实现单链表：

classSList{friendostream&operator<<(ostream&os,constSList&s);//输出运算符重载(友元)public:SList()//构造函数:_head(NULL),_tail(NULL){}SList(constSList&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;deletedel;}_tail=NULL;_head=NULL;}SList&operator=(SLists)//赋值运算符重载{swap(_head,s._head);swap(_tail,s._tail);return*this;}

单链表最基本的四个函数：

voidSList::PushBack(constDataType&d)//尾插{Node*newNode=newNode(d);//构建一个新的节点if(_head==NULL){_head=newNode;_tail=newNode;}else{_tail->_next=newNode;_tail=newNode;}}voidSList::PushFront(constDataType&d)//头插{Node*newNode=newNode(d);if(_head==NULL){_head=newNode;_tail=newNode;}else{newNode->_next=_head;_head=newNode;}}voidSList::PopBack()//尾删{if(_head==NULL)return;elseif(_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;}}voidSList::PopFront()//头删{if(_head==NULL)return;elseif(_head==_tail){delete_tail;_tail=NULL;_head=NULL;}else{Node*del=_head;_head=_head->_next;deletedel;}}

给一个数据，若找到该节点则返回该节点，没找到则返回NULL

Node*SList::Find(constDataType&d){Node*cur=_head;while(cur!=NULL){if(cur->_data==d)returncur;cur=cur->_next;}returnNULL;}

给定一个节点，在该节点后插入一个新的节点

voidSList::Insert(Node*pos,constDataType&d){Node*newNode=newNode(d);if(pos==_tail)//若给定的节点是尾节点，此处可以直接调用尾插{_tail->_next=newNode;_tail=newNode;}else{newNode->_next=pos->_next;pos->_next=newNode;}}

链表的逆序：此处用三个指针来实现

voidSList::Reverse(){Node*p1=NULL;Node*p2=_head;Node*newhead=NULL;while(p2){p1=p2;p2=p2->_next;p1->_next=newhead;newhead=p1;}_head=newhead;}

链表的排序：采用冒泡排序

voidSList::Sort(){Node*cur=_head;Node*end=NULL;while(cur!=end){while(cur->_next!=end){if(cur->_data>cur->_next->_data){DataTypetmp=cur->_data;cur->_data=cur->_next->_data;cur->_next->_data=tmp;}cur=cur->_next;}end=cur;cur=_head;}}

删除某个节点（给定一个数据，删除数据与之相等的第一个节点）

voidSList::Remove(constDataType&d){Node*cur=_head;while(cur!=NULL){if(cur->_data==d){Node*del=cur->_next;DataTypetmp=cur->_data;cur->_data=cur->_next->_data;cur->_next->_data=tmp;cur->_next=cur->_next->_next;deletedel;return;}cur=cur->_next;}}

删除某些节点（给定一个数据，删除数据与之相等的每一个节点）

voidSList::RemoveAll(constDataType&d){Node*cur=_head;while(cur!=NULL){if(cur->_data==d){Node*del=cur->_next;DataTypetmp=cur->_data;cur->_data=cur->_next->_data;cur->_next->_data=tmp;cur->_next=cur->_next->_next;deletedel;}cur=cur->_next;}return;}

删除非尾节点

voidSList::EarseNotTail(Node*pos){Node*del=pos;Node*cur=_head;while(cur->_next!=pos)//找到该节点的前一个节点{cur=cur->_next;}cur->_next=pos->_next;//让它的_next指向要删除节点的_nextdeletedel;}

找到中间节点

Node*SList::FindMinNode()//快慢指针问题{//两个指针都指向头结点Node*cur=_head;//快的一次走两步，慢的一次走一步Node*fast=cur;//当快指针走到尾的时候，慢指针指向中间节点Node*slow=cur;while(fast){fast=fast->_next->_next;slow=slow->_next;}returnslow;}

删除倒数第K个节点

voidSList::DelKNode(intk){Node*cur=_head;inti=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;deletep1;}

检测是否带环

//检测是否带环intSList::CheckCycle(constSList&s)//快慢指针问题{Node*fast=_head;Node*slow=_head;while(slow){if(slow==fast){return1;}fast=fast->_next->_next;slow=slow->_next;}return0;}

获取环的入口点

Node*SList::GetCycleEoryNode(){Node*cur=_head;while(cur){if(cur==_tail){returncur;}cur=cur->_next;}returnNULL;}

判断是否相交

intSList::CheckCross(SList&l1,SList&l2){intcount1=l1.LengthOfList(l1);intcount2=l2.LengthOfList(l2);if(count1>count2){Node*cur=l1._head;while(cur){if(l2._tail==cur)return1;cur=cur->_next;}}else{Node*cur=l2._head;while(cur){if(l1._tail==cur)return1;cur=cur->_next;}}return0;}

合并两个链表

求两个链表的交点

Node*SList::GetLinkCross(SList&l1,SList&l2){intcount1=l1.LengthOfList(l1);intcount2=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)returncur1;else{cur1=cur1->_next;cur2=cur2->_next;}}}else{Node*cur1=l1._head;Node*cur2=l2._head;while(cur1){if(cur2->_next==cur1->_next)returncur1;else{cur1=cur1->_next;cur2=cur2->_next;}}}returnNULL;}

求链表长度

int SList::LengthOfList(const SList& s)

{

int length = 0;

Node *cur = _head;

while (cur)

{

length++;

cur = cur->_next;

}

return length;

}