c++双链表【构造函数、运算符重载、析构函数、增删查改及逆置等】

本文主要是介绍c++双链表【构造函数、运算符重载、析构函数、增删查改及逆置等】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

c++中的双向链表写法，主要实现（增删查改，链表逆置，构造函数，运算符重载，等）

建立头文件SList.h

#pragma oncetypedef int DataType;
class ListNode
{friend class List;//友元函数
public:ListNode(const DataType x):_data(x), _prev(NULL), _next(NULL){}
private:DataType _data;ListNode* _prev;ListNode* _next;
};
class List
{
public:List():_head(NULL), _tail(NULL){}//深拷贝List(const List& s):_head(NULL), _tail(NULL){ListNode* tmp = s._head;while (tmp){this->PushBack(tmp->_data);tmp = tmp->_next;}}//现代写法List& operator=(List& s){swap(_head, s._head);swap(_tail, s._tail);return *this;}
public:void Clear();void PrintList();void PushBack(DataType x);void PopBack();void PushFront(DataType x);void PopFront();void Insert(ListNode* pos, DataType x);void Erase(ListNode* pos);ListNode* Find(DataType x);//void Reverse();List Reverse();
private:ListNode* _head;ListNode* _tail;
};

各函数的实现

#include<iostream>
using namespace std;#include"List.h"
#include<assert.h>void List::Clear()//清除双链表
{ListNode* cur = _head;while (cur){ListNode* del = cur;cur = cur->_next;delete del;del = NULL;}
}void List::PrintList()//打印双链表
{ListNode* cur=_head;while (cur){cout << cur->_data << "->";cur = cur->_next;}cout << "NULL" << endl;
}void List::PushBack(DataType x)//尾插
{if (NULL == _head){_head = new ListNode(x);_tail = _head;}else{ListNode* tmp = new ListNode(x); _tail->_next = tmp;tmp->_prev = _tail;tmp->_next = NULL;_tail = tmp;}
}void List::PopBack()//尾删
{if (NULL == _head){cout << "List is empty!" << endl;}else if (_head == _tail){delete _head;_head = _tail = NULL;}else{//相比单链表方便找到尾节点的前一个节点ListNode* cur = _tail;_tail = cur->_prev;_tail->_next = NULL;delete cur;cur = NULL;}
}void List::PushFront(DataType x)//头插
{ListNode* tmp = _head;_head = new ListNode(x);_head->_prev = NULL;_head->_next = tmp;
}void List::PopFront()//头删
{if (NULL == _head){cout << "SList is empty!" << endl;}else if (NULL == _head->_next){delete _head;_head = NULL;}else{ListNode* tmp = _head->_next;delete _head;_head = tmp;tmp->_prev = NULL;}
}ListNode* List::Find(DataType x)//查找x
{ListNode* cur = _head;while (cur){if (x == cur->_data)return cur;cur = cur->_next;}return NULL;
}void List::Insert(ListNode* pos, DataType x)//指定位置处插入x
{assert(pos);if (NULL == pos->_next)List::PushBack(x);else if (_head == pos)List::PushFront(x);else{ListNode* cur = new ListNode(x);ListNode* prev = pos->_prev;prev->_next = cur;cur->_prev = prev;cur->_next = pos;pos->_prev = cur;}
}void List::Erase(ListNode* pos)//删除结点pos
{assert(pos);if (NULL == pos->_next)List::PopBack();else if (_head == pos)List::PopFront();else{ListNode* prev = pos->_prev;ListNode* next = pos->_next;next->_prev = prev;prev->_next = next;delete pos;pos = NULL;}
}
//逆置双链表
//通过两个指针，从两边向中间移动，交换所储蓄内容
//void List::Reverse()
//{
//	ListNode* begin = _head;
//	ListNode* end = _tail;
//	//奇数个节点时两个指针相等时结束循环；偶数个节点时两个指针发生交叉时结束循环
//	while (begin != end && begin->_prev != end)
//	{
//		swap(begin->_data, end->_data);
//		begin = begin->_next;
//		end = end->_prev;
//	}
//}//交换头尾指针，交换每个结点的前驱和后继
//void List::Reverse()
//{
//	swap(_head, _tail);
//	ListNode* cur = _head;
//	while (cur)
//	{
//		swap(cur->_prev,cur->_next);
//		cur = cur->_next;
//	}
//}//建立新链表，通过头插法实现
List List::Reverse()
{if (NULL == _head){cout << "SList is empty!" << endl;}else if(NULL != _head->_next){List NewList;ListNode* cur = _head->_next;ListNode* tmp = _head;//保存头指针，头插完后使其_next指针指向空while (cur){this->PushFront(cur->_data);cur = cur->_next;}tmp->_next = NULL;return NewList;}return *this;
}

本文出自 “Scen” 博客，请务必保留此出处http://10741357.blog.51cto.com/10731357/1748592

这篇关于c++双链表【构造函数、运算符重载、析构函数、增删查改及逆置等】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---