微山做网站,苏州网站怎么做,网络安全工程师工作内容,网站备案密码重置申请表一、什么是双向链表
1、定义
双向链表也叫双链表#xff0c;是链表的一种#xff0c;它的每个数据结点中都有两个指针#xff0c;分别指向直接后继和直接前驱。所以#xff0c;从双向链表中的任意一个结点开始#xff0c;都可以很方便地访问它的前驱结点和后继结点。
双…一、什么是双向链表
1、定义
双向链表也叫双链表是链表的一种它的每个数据结点中都有两个指针分别指向直接后继和直接前驱。所以从双向链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。
双向链表的结构如图图片来源于网络
2、时空复杂度
双向链表的空间复杂度是 O ( n ) O(n) O(n) 的其时间复杂度如下
操作时间复杂度遍历 O ( n ) O(n) O(n)访问指定节点 O ( 1 ) O(1) O(1)删除指定编号节点 O ( n ) O(n) O(n)删除指定位置节点 O ( 1 ) O(1) O(1)在指定编号的节点后插入节点 O ( n ) O(n) O(n)在指定位置的节点后插入节点 O ( 1 ) O(1) O(1)查询前驱、后继 O ( 1 ) O(1) O(1)修改指定编号节点的值 O ( n ) O(n) O(n)修改指定位置节点的值 O ( 1 ) O(1) O(1)交换两个 list 容器 O ( 1 ) O(1) O(1)
二、双向链表的基本操作
1. 定义双向链表节点
每个节点有三个值
val存储每个节点的权值last指向每个节点的前面的第一个节点next指向每个节点的后面的第一个节点
代码如下
templatetypename T
struct ListNode{T value;ListNodeT* last;ListNodeT* next;ListNode():value(0){lastNULL,nextNULL;}ListNode(const T x):value(x){lastNULL,nextNULL;}~ListNode(){value0;delete last;delete next;}
};2. 创建双向链表类
类里面包含两个节点和一个变量
headnode头节点初始时前驱后继均为空值为 − 1 -1 −1endnode尾节点初始时前驱后继均为空值为 − 1 -1 −1listsize记录双向链表的节点个数不包含头尾节点
代码如下
templatetypename T
class list{private:unsigned listsize;ListNodeT* headnode;ListNodeT* endnode;
};3. 初始化双向链表类
共有四种初始化方式
list类型名 a;此时创建一个空的双向链表list类型名 a(n);此时创建一个大小为 n n n 的双向链表并将所有点的初始值赋为 0 0 0list类型名 a(n,m)此时创建一个大小为 n n n 的双向链表并将所有点的初始值赋为 m m mlist类型名 a{a1,a2,a3,...,an};此时创建一个大小为 n n n 的双向链表并将第 i i i 个节点的初始值赋为 a i a_i ai
第一种初始化方式代码如下
list():listsize(0){headnodenew ListNodeT(-1);endnodenew ListNodeT(-1);
}第二种初始化方式代码如下
list(const int size_t):listsize(size_t) {headnodenew ListNodeT(-1);endnodenew ListNodeT(-1);ListNodeT* nowheadnode;for(int i0;ilistsize;i){ListNodeT* newnodenew ListNodeT(0);endnode-lastnewnode;newnode-nextendnode;newnode-lastnow;now-nextnewnode;nownow-next;}
}第三种初始化方式代码如下
list(const int size_t,const int val
):listsize(size_t){headnodenew ListNodeT(-1);endnodenew ListNodeT(-1);ListNodeT* nowheadnode;for(int i0;ilistsize;i){ListNodeT* newnodenew ListNodeT(val);endnode-lastnewnode;newnode-nextendnode;newnode-lastnow;now-nextnewnode;nownow-next;}
}第四种初始化方式代码如下
typedef std::initializer_listT lisval;
list(lisval vals){listsize0;headnodenew ListNodeT(-1);endnodenew ListNodeT(-1);ListNodeT* nowheadnode;for(auto val:vals){ListNodeT* newnodenew ListNodeT(val);endnode-lastnewnode;newnode-nextendnode;newnode-lastnow;now-nextnewnode;nownow-next; listsize;}
}3. 一些基础的函数
这些函数是除了加点删点之外最常见的几个函数。 size()获取链表的大小返回一个 unsigned 值表示当前链表中普通节点非头尾节点的个数。 代码如下 unsigned size() const {return listsize;
}empty()返回当前链表是否为空如果是返回 true否则返回 false。 代码如下 bool empty() const {return listsize0;
}begin()返回第一个普通节点。 代码如下 ListNodeT* begin(
) const {return headnode-next;
}end()返回尾指针。 代码如下 ListNodeT* end(
) const {return endnode;
}rbegin()返回最后一个普通节点。 代码如下 ListNodeT* rbegin(
) const {return endnode-last;
}rend()返回头指针。 代码如下 ListNodeT* rend(
) const {return headnode;
}front()返回第一个普通节点的值。 代码如下 T front() const {return begin()-value;
}back()返回最后一个普通节点的值。 代码如下 T back() const {return rbegin()-value;
}print()遍历并输出链表中每个普通节点的值结尾换行。 代码如下 void print(
) const {if(empty()) return;ListNodeT* nowheadnode-next;while(now-next!NULL){printf(%d ,now-value);nownow-next;} putchar(\n);
}swap(list类型名 b)交换两个 list 容器实际上是交换头尾指针和 l i s t s i z e listsize listsize。 代码如下 void swap(listT b){ListNodeT* temp;tempheadnode;headnodeb.headnode;b.headnodetemp;tempendnode;endnodeb.endnode;b.endnodetemp;unsigned size_tlistsize;listsizeb.listsize;b.listsizesize_t;
}5. 插入节点
共四种方法代码如下
void push_back(const T val
){ listsize;if(endnode-lastNULL){ListNodeT* newnodenew ListNodeT(val);endnode-lastnewnode;newnode-nextendnode;headnode-nextnewnode;newnode-lastheadnode;return;}ListNodeT* preendnode-last;ListNodeT* newnodenew ListNodeT(val);pre-nextnewnode;newnode-lastpre;newnode-nextendnode;endnode-lastnewnode;
}void push_front(const T val
){ listsize;if(headnode-nextNULL){ListNodeT* newnodenew ListNodeT(val);endnode-lastnewnode;newnode-nextendnode;headnode-nextnewnode;newnode-lastheadnode;return;}ListNodeT* sufheadnode-next;ListNodeT* newnodenew ListNodeT(val);headnode-nextnewnode;newnode-lastheadnode;newnode-nextsuf;suf-lastnewnode;
}void insert(const T pos,const T val
){ int nowpos0;if(pos0){push_front(val);listsize; return;} else if(poslistsize){push_back(val);listsize; return;}ListNodeT* nowheadnode-next;while(now-next!NULL){nowpos;if(nowpospos){ListNodeT* newnodenew ListNodeT(val);ListNodeT* sufnow-next;newnode-nextsuf;suf-lastnewnode;newnode-lastnow;now-nextnewnode;listsize; return;}nownow-next;}
}void insert(ListNodeT* now,const T val
){if(nowendnode){push_back(val); return;}ListNodeT* newnodenew ListNodeT(val);ListNodeT* sufnow-next;newnode-nextsuf;suf-lastnewnode;newnode-lastnow;now-nextnewnode;listsize; return;
}6. 修改指定位置的值
两种方法代码如下
void reassign(const T pos,const T val
){if(poslistsize) return;if(empty()||!pos) return;ListNodeT* nowheadnode-next;int nowpos0;while(now-next!NULL){nowpos;if(nowpospos){now-valueval;return;} nownow-next;}
}void reassign(ListNodeT* now,const int val
) const {now-valueval;
}7.删除节点
和插入一样共有四种代码如下
void pop_back(){if(empty()) return;ListNodeT* nowendnode-last;ListNodeT* prenow-last;if(preheadnode){endnode-lastNULL;headnode-lastNULL;--listsize; return;}endnode-lastpre;pre-nextendnode;--listsize;
}void pop_front(){if(empty()) return;ListNodeT* nowheadnode-next;ListNodeT* sufnow-next;if(sufendnode){endnode-lastNULL;headnode-lastNULL;--listsize; return;}headnode-nextsuf;suf-lastheadnode;--listsize;
}void erase(const int pos
) {if(poslistsize) return;if(empty()||!pos) return;ListNodeT* nowheadnode-next;int nowpos0;while(now!endnode){nowpos;if(nowpospos){ListNodeT* prenow-last;ListNodeT* sufnow-next;if(preheadnode||sufendnode){endnode-lastNULL;headnode-nextNULL;delete now;--listsize; return;}pre-nextsuf;suf-lastpre;delete now;--listsize; return;}nownow-next;}
}void erase(ListNodeT* now
){ if(nowheadnode) return;if(nowendnode) return;if(empty()) return;ListNodeT* prenow-last;ListNodeT* sufnow-next;if(preheadnode||sufendnode){endnode-lastNULL;headnode-lastNULL;--listsize; return;}pre-nextsuf;suf-lastpre;--listsize; return;
}8. 注销双向链表类
遍历一遍然后将每个节点都删除就可以了。
代码如下
~list(){ListNodeT* nowheadnode-next;while(now!NULL){ListNodeT* nxtnow-next;delete now;nownxt;} delete headnode; listsize0;
}三、完整代码
我知道你们只看这个
码风丑陋不喜勿喷
#includestdio.h
#includestdlib.h
#includeinitializer_list
namespace STL{templatetypename Tstruct ListNode{T value;ListNodeT* last;ListNodeT* next;ListNode():value({}){lastNULL,nextNULL;}ListNode(const T x):value(x){lastNULL,nextNULL;}~ListNode(){// value{};lastNULL;nextNULL;}};templatetypename Tclass list{private:unsigned listsize;ListNodeT* headnode;ListNodeT* endnode;public:list():listsize(0){headnodenew ListNodeT(T({-1}));endnodenew ListNodeT(T({-1}));}list(const int size_t):listsize(size_t) {headnodenew ListNodeT(-1);endnodenew ListNodeT(-1);ListNodeT* nowheadnode;for(int i0;ilistsize;i){ListNodeT* newnodenew ListNodeT(0);endnode-lastnewnode;newnode-nextendnode;newnode-lastnow;now-nextnewnode;nownow-next;}}list(const int size_t,const int val):listsize(size_t){headnodenew ListNodeT(-1);endnodenew ListNodeT(-1);ListNodeT* nowheadnode;for(int i0;ilistsize;i){ListNodeT* newnodenew ListNodeT(val);endnode-lastnewnode;newnode-nextendnode;newnode-lastnow;now-nextnewnode;nownow-next;}}typedef std::initializer_listT lisval;list(lisval vals){listsize0;headnodenew ListNodeT(-1);endnodenew ListNodeT(-1);ListNodeT* nowheadnode;for(auto val:vals){ListNodeT* newnodenew ListNodeT(val);endnode-lastnewnode;newnode-nextendnode;newnode-lastnow;now-nextnewnode;nownow-next; listsize;}}unsigned size() const {return listsize;}bool empty() const {return listsize0;}ListNodeT* begin() const {return headnode-next;}ListNodeT* end() const {return endnode;}ListNodeT* rbegin() const {return endnode-last;}ListNodeT* rend() const {return headnode;}T front() const {return begin()-value;}T back() const {return rbegin()-value;}void print() const {if(empty()) return;ListNodeT* nowheadnode-next;while(now-next!NULL){printf(%lld ,now-value);nownow-next;} putchar(\n);}void push_back(const T val){ listsize;if(endnode-lastNULL){ListNodeT* newnodenew ListNodeT(val);endnode-lastnewnode;newnode-nextendnode;headnode-nextnewnode;newnode-lastheadnode;return;}ListNodeT* preendnode-last;ListNodeT* newnodenew ListNodeT(val);pre-nextnewnode;newnode-lastpre;newnode-nextendnode;endnode-lastnewnode;}void push_front(const T val){ listsize;if(headnode-nextNULL){ListNodeT* newnodenew ListNodeT(val);endnode-lastnewnode;newnode-nextendnode;headnode-nextnewnode;newnode-lastheadnode;return;}ListNodeT* sufheadnode-next;ListNodeT* newnodenew ListNodeT(val);headnode-nextnewnode;newnode-lastheadnode;newnode-nextsuf;suf-lastnewnode;}void insert(const T pos,const T val){ int nowpos0;if(pos0){push_front(val);listsize; return;} else if(poslistsize){push_back(val);listsize; return;}ListNodeT* nowheadnode-next;while(now-next!NULL){nowpos;if(nowpospos){ListNodeT* newnodenew ListNodeT(val);ListNodeT* sufnow-next;newnode-nextsuf;suf-lastnewnode;newnode-lastnow;now-nextnewnode;listsize; return;}nownow-next;}}void insert(ListNodeT* now,const T val){if(nowendnode){push_back(val); return;}ListNodeT* newnodenew ListNodeT(val);ListNodeT* sufnow-next;newnode-nextsuf;suf-lastnewnode;newnode-lastnow;now-nextnewnode;listsize; return;}void reassign(const T pos,const T val){if(poslistsize) return;if(empty()||!pos) return;ListNodeT* nowheadnode-next;int nowpos0;while(now-next!NULL){nowpos;if(nowpospos){now-valueval;return;} nownow-next;}}void reassign(ListNodeT* now,const int val) const {now-valueval;}void pop_back(){if(empty()) return;ListNodeT* nowendnode-last;ListNodeT* prenow-last;if(preheadnode){endnode-lastNULL;headnode-nextNULL;delete now;--listsize; return;}endnode-lastpre;pre-nextendnode;delete now;--listsize;}void pop_front(){if(empty()) return;ListNodeT* nowheadnode-next;ListNodeT* sufnow-next;if(sufendnode){endnode-lastNULL;headnode-nextNULL;delete now;--listsize; return;}headnode-nextsuf;suf-lastheadnode;delete now;--listsize;}void erase(const int pos) {if(poslistsize) return;if(empty()||!pos) return;ListNodeT* nowheadnode-next;int nowpos0;while(now!endnode){nowpos;if(nowpospos){ListNodeT* prenow-last;ListNodeT* sufnow-next;if(preheadnode||sufendnode){endnode-lastNULL;headnode-nextNULL;delete now;--listsize; return;}pre-nextsuf;suf-lastpre;delete now;--listsize; return;}nownow-next;}}void erase(ListNodeT* now){ if(nowheadnode) return;if(nowendnode) return;if(empty()) return;ListNodeT* prenow-last;ListNodeT* sufnow-next;if(preheadnode||sufendnode){endnode-lastNULL;headnode-lastNULL;delete now;--listsize; return;}pre-nextsuf;suf-lastpre;delete now;--listsize; return;}void swap(listT b){ListNodeT* temp;tempheadnode;headnodeb.headnode;b.headnodetemp;tempendnode;endnodeb.endnode;b.endnodetemp;unsigned size_tlistsize;listsizeb.listsize;b.listsizesize_t;}~list(){ListNodeT* nowheadnode-next;while(now!NULL){ListNodeT* nxtnow-next;delete now;nownxt;} delete headnode;listsize0;}};
}
using STL::list;signed main(){system(pause);
}给个赞再走吧
