} } }

    数据布局专题四——双向轮回链表

    添加时间:2013-5-14 点击量:

    文章目次:



    01. 博文简介:


    02. 概念:


    03. 示例图:


    04. 优毛病:


    05. 代码解析:


    06. 运行景象:


    07. 题记: 



    一:概念


    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的随便率性一个结点开端,都可以很便利地接见它的前驱结点和后继结点,一般我们都机关双向轮回表,STL中实现了双链表轮回表


    二:示例图


     


    三:链表的优毛病


    链表大一个毛病,就是查找一个元素,必须全部链表遍历,也可以看出这种数据布局便于插入或者删除一个接点。


    四:代码解析


    1、获取节点信息



     1 /
    
    2 按照地位获取相对应的节点信息
    3 size_t 是一个无符号的类型,断定调用该函数时入参必然是正数,
    4 如许的请求也提示我们在写函数时,应当避免把如许函数露出给客户
    5 不知道为什么linux很多api函数都有size_t类型的入参(经由过程调试,传入负数会导致严重的bug),
    6 有知道的伴侣,请辅佐分享下
    7 /
    8 DLNode<T> GetElemP(size_t i) const{
    9 int j = 0;
    10 DLNode<T> p = head;
    11
    12 do{
    13 p = p->next;
    14 j++;
    15 }while(p != head && j < i);
    16
    17 return p;
    18 }
    19
    20 /
    21 按照元素获取对应的节点信息
    22 /
    23 DLNode<T> GetElemE(const T &e) const{
    24 DLNode<T> p = head->next;
    25
    26 while(p != head && e != p->data){
    27 p = p->next;
    28 }
    29
    30 return p;
    31 }


    2、插入节点


     插入过程如下图:



     代码解析如下:



     1 /
    
    2 在指定的地位插入节点
    3 /
    4 void Insert(size_t i,const T &e){
    5 //获取指定的地位节点
    6 DLNode<T> p = GetElemP(i);
    7 //插入新节点
    8 Insert(p,e);
    9 }
    10 /
    11 在指定的指针节点插入新的节点
    12 /
    13 void Insert(DLNode<T> p,const T &e){
    14 //创建一个新的节点
    15 DLNode<T> q = new DLNode<T>(e);
    16 //设置新节点的向后的指针域(指向图中2节点)
    17 q->next = p->next;
    18 //设置新节点的向前的指针域(指向图中1节点)
    19 q->prev = p;
    20
    21 //设置插入节点的后继节点的向前指针域(图中3节点的上一个节点指针域指向新节点2)
    22 p->next->prev = q;
    23 //设置插入节点的向后的指针域(指向新节点2)
    24 p->next = q;
    25 }
    26 /
    27 从头结点的地位插入新的节点
    28 /
    29 void AddHead(const T &e){
    30 Insert(head,e);
    31 }
    32 /
    33 从第一个节点的地位插入新的节点
    34 /
    35 void Insert(const T &e){
    36 Insert(1,e);
    37 }


    3、删除节点


    删除节点如下图,可以从图中看到,删除节点仅仅改变前驱和后继节点相干的指针域,这个就是为什么数据删除高手还可以找回来原因;



    代码解析如下:



     1 /
    
    2 按照元素内容删除对应的节点
    3 /
    4 void Delete(const T &e){
    5 //按照元素内容获取对应的节点
    6 DLNode<T> p = GetElemE(e);
    7 //更多关于auto_ptr常识,请浏览memory里auto_ptr源码
    8 std::auto_ptr<DLNode<T> > new_ptr(p);
    9 //设置删除节点后继节点向前的指针域为删除节点向前指针域
    10 p->next->prev = p->prev;
    11 //设置删除节点前驱节点向后的指针域为删除节点向后指针域
    12 p->prev->next = p->next;
    13 }


    4、遍历节点,在stl源码中有很是强大遍历神器(iterator),把泛型的常识应用到极致,感激的伴侣可以读读源码 



     1 /
    
    2 遍历双向链表
    3 /
    4 void Traverse(){
    5 //指向第一个节点信息
    6 DLNode<T> p = head->next;
    7
    8 //若是节点向后指针域便是头结点,默示链表已经遍历完成
    9 while(p != head){
    10 std::cout<<p is value = <<p->data;
    11 std::cout<<<<std::endl;
    12 p = p->next;
    13 }
    14 }


    5、清空链表



     1 /
    
    2 清空全部链表节点
    3 /
    4 void Clear(){
    5 //获取第一个节点信息
    6 DLNode<T> p = head->next;
    7
    8 //若是节点向后指针域便是头结点,默示链表已经被清空
    9 while(p != head && p != 0){
    10 //更多关于auto_ptr常识,请浏览memory里auto_ptr源码
    11 std::auto_ptr<DLNode<T> > new_ptr(p);
    12 std::cout<<p;
    13 std::cout<<std::endl;
    14 //履行后继节点
    15 p = p->next;
    16 }
    17 //恢复出厂原状,向前和向后的指针域都指向本身,构成双向链表
    18 head->next = head->prev = head;
    19 }


    6、是否为空和策画链表长度



    /
    
    断定链表是否为空
    /
    bool Empty(){
    return head->next = head;
    }

    /
    策画链表的长度
    /
    int Length(){

    int i = 0;
    DLNode
    <T> p = head->next;

    //若是节点向后指针域便是头结点,链表遍历完成,
    while(p != head){
    //履行后继节点
    p = p->next;
    //累计链表节点长度
    i++;
    }

    return i;
    }


    7、测试代码



     1 void test(){
    
    2 std::cout<<----------- begin------------<<std::endl;
    3 forint i = 1; i <= 5; ++i){
    4 Insert(i);
    5 }
    6 AddHead(6);
    7 AddHead(7);
    8 Traverse();
    9 std::cout<<----------- end------------<<std::endl;
    10
    11 std::cout<<frist list length=<<Length()<<std::endl;
    12
    13 std::cout<<----------- begin----------<<std::endl;
    14 Delete(2);
    15 std::cout<<----------- end----------<<std::endl;
    16
    17 std::cout<<second list length=<<Length()<<std::endl;
    18
    19 std::cout<<-----------traversal of the elemetns begin----------<<std::endl;
    20
    21 Traverse();
    22 Clear();
    23 Delete(1);
    24 Clear();
    25 std::cout<<third list length=<<Length()<<std::endl;
    26 }


    8、运行成果


     


    9、完全代码




      1 /
    
    2 DLinkList.h
    3
    4 Created on: 2012-10-13
    5 Author: hs
    6 /
    7
    8 #ifndef DLINKLIST_H_
    9 #define DLINKLIST_H_
    10 #include core/node/DLNode.h
    11
    12 template<class T>
    13 class DLinkList {
    14 private:
    15 DLNode<T> head;//头结点
    16 /
    17 按照地位获取相对应的节点信息
    18 size_t 是一个无符号的类型,断定调用该函数时入参必然是正数,
    19 如许的请求也提示我们在写函数时,应当避免把如许函数露出给客户
    20 不知道为什么linux很多api函数都有size_t类型的入参(经由过程调试,传入负数会导致严重的bug),
    21 有知道的伴侣,请辅佐分享下
    22 /
    23 DLNode<T> GetElemP(size_t i) const{
    24 int j = 0;
    25 DLNode<T> p = head;
    26
    27 do{
    28 p = p->next;
    29 j++;
    30 }while(p != head && j < i);
    31
    32 return p;
    33 }
    34
    35 /
    36 按照元素获取对应的节点信息
    37 /
    38 DLNode<T> GetElemE(const T &e) const{
    39 DLNode<T> p = head->next;
    40
    41 while(p != head && e != p->data){
    42 p = p->next;
    43 }
    44
    45 return p;
    46 }
    47 /
    48 在指定的地位插入节点
    49 /
    50 void Insert(size_t i,const T &e){
    51 //获取指定的地位节点
    52 DLNode<T> p = GetElemP(i);
    53 //插入新节点
    54 Insert(p,e);
    55 }
    56 /
    57 在指定的指针节点插入新的节点
    58 /
    59 void Insert(DLNode<T> p,const T &e){
    60 //创建一个新的节点
    61 DLNode<T> q = new DLNode<T>(e);
    62 //设置新节点的向后的指针域(指向图中2节点)
    63 q->next = p->next;
    64 //设置新节点的向前的指针域(指向图中1节点)
    65 q->prev = p;
    66
    67 //设置插入节点的后继节点的向前指针域(图中3节点的上一个节点指针域指向新节点2)
    68 p->next->prev = q;
    69 //设置插入节点的向后的指针域(指向新节点2)
    70 p->next = q;
    71 }
    72
    73 public:
    74 /
    75 机关函数,初始化头结点(向前和向后都指向本身,构成双向链表)
    76 /
    77 DLinkList():head(new DLNode<T>(0)){
    78 head->next = head;
    79 head->prev = head;
    80 }
    81
    82 /
    83 析构函数,开释所有新创建的节点
    84 /
    85 ~DLinkList(){
    86 Clear();
    87 }
    88 /
    89 清空全部链表节点
    90 /
    91 void Clear(){
    92 //获取第一个节点信息
    93 DLNode<T> p = head->next;
    94
    95 //若是节点向后指针域便是头结点,默示链表已经被清空
    96 while(p != head && p != 0){
    97 //更多关于auto_ptr常识,请浏览memory里auto_ptr源码
    98 std::auto_ptr<DLNode<T> > new_ptr(p);
    99 std::cout<<p;
    100 std::cout<<std::endl;
    101 //履行后继节点
    102 p = p->next;
    103 }
    104 //恢复出厂原状,向前和向后的指针域都指向本身,构成双向链表
    105 head->next = head->prev = head;
    106 }
    107 /
    108 断定链表是否为空
    109 /
    110 bool Empty(){
    111 return head->next = head;
    112 }
    113
    114 /
    115 策画链表的长度
    116 /
    117 int Length(){
    118
    119 int i = 0;
    120 DLNode<T> p = head->next;
    121
    122 //若是节点向后指针域便是头结点,链表遍历完成,
    123 while(p != head){
    124 //履行后继节点
    125 p = p->next;
    126 //累计链表节点长度
    127 i++;
    128 }
    129
    130 return i;
    131 }
    132 /
    133 从头结点插入新的元素
    134 /
    135 void AddHead(const T &e){
    136 Insert(head,e);
    137 }
    138 /
    139 从第一个地位插入新的节点
    140 /
    141 void Insert(const T &e){
    142 Insert(1,e);
    143 }
    144
    145 /
    146 按照元素内容删除对应的节点
    147 /
    148 void Delete(const T &e){
    149 //按照元素内容获取对应的节点
    150 DLNode<T> p = GetElemE(e);
    151 //更多关于auto_ptr常识,请浏览memory里auto_ptr源码
    152 std::auto_ptr<DLNode<T> > new_ptr(p);
    153 //设置删除节点后继节点向前的指针域为删除节点向前指针域
    154 p->next->prev = p->prev;
    155 //设置删除节点前驱节点向后的指针域为删除节点向后指针域
    156 p->prev->next = p->next;
    157 }
    158
    159 /
    160 遍历双向链表
    161 /
    162 void Traverse(){
    163 //指向第一个节点信息
    164 DLNode<T> p = head->next;
    165
    166 //若是节点向后指针域便是头结点,默示链表已经遍历完成
    167 while(p != head){
    168 std::cout<<p is value = <<p->data;
    169 std::cout<<<<std::endl;
    170 p = p->next;
    171 }
    172 }
    173
    174 void test(){
    175 std::cout<<----------- begin------------<<std::endl;
    176 forint i = 1; i <= 5; ++i){
    177 Insert(i);
    178 }
    179 AddHead(6);
    180 AddHead(7);
    181 Traverse();
    182 std::cout<<----------- end------------<<std::endl;
    183
    184 std::cout<<frist list length=<<Length()<<std::endl;
    185
    186 std::cout<<----------- begin----------<<std::endl;
    187 Delete(7);
    188 std::cout<<----------- end----------<<std::endl;
    189
    190 std::cout<<second list length=<<Length()<<std::endl;
    191
    192 std::cout<<-----------traversal of the elemetns begin----------<<std::endl;
    193
    194 Traverse();
    195 Clear();
    196 Delete(1);
    197 Clear();
    198 std::cout<<third list length=<<Length()<<std::endl;
    199 }
    200 };
    201
    202 #endif / DLINKLIST_H_ /


    View Code

    五:景象


    1、运行景象:Ubuntu 10.04 LTS+VMware8.0.4+gcc4.4.3


    2、开辟对象:Eclipse+make


    六:题记


    1、上方的代码不免有bug,若是你发明代码写的有题目,请你辅佐指出,让我们一路进步,让代码变的更摩登和更结实;


    2、我本身妙手动写上方代码,离不开郝斌、高一凡、侯捷、严蔚敏等教员的册本和视频领导,在这里感激他们;


    3、激劝本身能对峙把更多半据布局方面的常识写出来,让本身把握更深切,也趁便假充下小牛


     


    所有随风而逝的都属于昨天的,所有历经风雨留下来的才是面向未来的。—— 玛格丽特·米切尔 《飘》
    分享到: