c++-实现双向链表

双向链表相比较于单向链表要删除节点的时候不需要一个一个遍历节点来找到它的前驱节点,它的节点里自带前驱节点。 Slist.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once typedef int DataType; struct ListNode { DataType _data; ListNode* _next;//存放下一个节点的地址 ListNode* _prev;
//存放上一个节点的地址
ListNode(const DataType x) :_data(x) , _next(NULL) , _prev(NULL) {} }; class List { typedef ListNode Node; public: List()//构造
:_head(NULL) , _tail(NULL) {} ~List()//析构
{ clear(); } List(const List&L)//拷贝构造
:_head(NULL) , _tail(NULL) { Node* cur = L._head; while (cur) { PushBack(cur->_data); cur = cur->_next; } } void Swap(List L) { swap(_head, L._head); swap(_tail, L._tail); } List& operator=(List L)//赋值运算符重载
{ Swap(L); return *this; } void clear() { Node* cur = _head; while (cur) { Node* tmp = cur; cur = cur->_next; delete tmp; } _head = _tail = NULL; } void PushBack(DataType x)//尾插
{ if (_head == NULL) { _head = _tail = new Node(x); } else { Node* tmp = new Node(x); _tail->_next = tmp; tmp->_prev = _tail; _tail = _tail->_next; } } void PushFront(DataType x)//头插
{ if (_head == NULL) { _head = _tail = new Node(x);//无节点时
} else { Node* tmp = new Node(x); //有节点
tmp->_next = _head; _head->_prev = tmp; _head = tmp; } } void PopBack()//尾删
{ if (_head == NULL)//无节点时
{ return; } else if (_head->_next == NULL)//一个节点
{ delete _head; _head = _tail = NULL; } else //多个节点
{ Node* tmp = _tail->_prev; delete _tail; _tail = tmp; _tail->_next=NULL; } } void PopFront()//头删
{ if (_head == NULL) { return; } else if (_head->_next == NULL) { _head = _tail = NULL; } else { Node* tmp = _head->_next; delete _head; _head = tmp; tmp->_prev = NULL; } } void Print() //打印
{ Node* cur = _head; while (cur) { cout << cur->_data << “ “; cur = cur->_next; } cout << endl; } Node* Find(DataType x) //查找
{ Node* cur = _head; while (cur) { if (cur->_data == x) { return cur; } cur = cur->_next; } return NULL; } void Insert(Node* pos, DataType x)//在节点前插入
{ assert(pos); if (pos == _head) { PushFront(x); //头结点前插入
return; } Node* tmp = new Node(x); Node* prev = pos->_prev; Node* next = pos; prev->_next = tmp; tmp->_prev = prev; tmp->_next=next; next->_prev=tmp;
/* if (pos == _head) { PushFront(x); return; } Node* tmp = new Node(x); pos->_prev->_next = tmp; tmp->_prev = pos->_prev; tmp->_next = pos; pos->_prev = tmp;/ } void Reverse() //链表的逆置 { /*Node\ begin = _head; Node* end = _tail; while (begin != end&&begin->_prev != end) { swap(begin->_data, end->_data); begin = begin->_next; end = end->_prev; }/ Node cur = _head; swap(_head, _tail); while (cur) { swap(cur->_next, cur->_prev); cur = cur->_prev; } } void Erase(Node* pos) //删除节点 { assert(pos); if (pos == _head)//删除头结点 { PopFront(); } else if (pos == _tail)//删除尾节点 { PopBack(); } else { Node* prev = pos->_prev; Node* next = pos->_next; prev->_next = next; next->_prev = prev; } } private: Node* _head;//头结点 Node* _tail; //尾节点 }; //测试尾插以及尾删 void test1() { List l1; l1.PushBack(1); l1.PushBack(2); l1.PushBack(3); l1.PushBack(4); l1.PushBack(5); l1.Print(); l1.PopBack(); l1.PopBack(); l1.PopBack(); l1.PopBack(); l1.PopBack(); l1.PopBack(); l1.Print(); } //测试头插以及头删 void test2() { List l1; l1.PushFront(1); l1.PushFront(2); l1.PushFront(3); l1.PushFront(4); l1.PushFront(5); l1.Print(); l1.PopFront(); l1.PopFront(); l1.PopFront(); l1.PopFront(); l1.PopFront(); l1.PopFront(); l1.Print(); } //测试查找以及在节点前插入 void test3() { List l1; l1.PushBack(1); l1.PushBack(2); l1.PushBack(3); l1.PushBack(4); l1.PushBack(5); ListNode* ret = l1.Find(1); /*if (ret == NULL) { cout << “找不到” << endl; } else { cout << ret->_data << endl; }*/

l1.Insert(ret, 0); l1.Insert(ret, 8); l1.Print(); } //删除节点以及链表逆置
void test4() { List l1; l1.PushBack(0); l1.PushBack(1); l1.PushBack(2); l1.PushBack(3); l1.PushBack(4); l1.PushBack(5); l1.Print(); ListNode* ret = l1.Find(0); l1.Erase(ret); l1.Print(); l1.Reverse(); l1.Print(); }
1
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<assert.h> using namespace std; #include”Slist.h” int main() { //test1(); //test2(); //test3(); test4(); return 0; }
  • 版权声明: 本博客所有文章,未经许可,任何单位及个人不得做营利性使用!转载请标明出处!如有侵权请联系作者。
  • Copyrights © 2015-2020 翟天野

请我喝杯咖啡吧~