线性表--单链表(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;
}
以后会有改进版奉上,希望大家多多支持
本文名称:线性表--单链表(C++)
文章网址:http://scyanting.com/article/ggjooi.html