[cpp]: 双向链表的实现

[cpp]:  双向链表的实现

一、思路或者原理

　　1、双向链表的实现思路：

　　　　1.1、链节（data class）：【链节data】是组成【链条chains】的基本单元，【链节data】用于存储数据。

　　　　　　1.1.1、链节内的数据成员：从当前【链节data】指向前一个【链节data】的指针（前向指针）；从当前【链节data】指向后一个【链节data】的指针（后向指针）；数据存储（保存数据）

　　　　　　1.1.2、链节内的基本操作：【链节data】的赋值；

　　　　1.2、实现双向链表（chains class）：

　　　　　　1.2.1、【链表chains】的基本操作：创建【链节data】并赋值；在两个【链节data】之间建立连接关系；删除【链节data】；遍历【链表chains】

　　　　　　1.2.2、【链表chains】基本数据对象：first（指向【链表chains】的第一个【链节data】）；  last（指向【链表chains】的最后一个【链节data】）；

　　　　　　1.2.3、（析构函数~chain()）删除【链节data】。

二、程序代码

  1 #include <iostream>
  2 
  3 
  4 //  unit of chains
  5 class data
  6 {
  7 public:
  8 
  9     data() = delete ;
 10 
 11     ~data()
 12     {
 13         std::cout << "[~data]#\t" << --data::dsize << std::endl ;
 14     }
 15     data(int e):val(e)
 16     { 
 17         data::dsize++ ;
 18     }
 19 
 20     //  double chains
 21     data *pre = nullptr;
 22     data *next = nullptr;
 23 
 24     //  element of data
 25     int val = 0;
 26 
 27     //  count object of 'data' type
 28     static unsigned int dsize ;
 29 };
 30 
 31 //  initialize count of object of 'data' type
 32 unsigned int data::dsize = 0 ;
 33 
 34 
 35 //  chain_of_data
 36 class chains
 37 {
 38 private:
 39 
 40     //  head pointer of object of chain_data 'type'
 41     data *first = nullptr ;
 42 
 43     //  tail pointer of object of chain_data 'type'
 44     data *last = nullptr ;
 45 
 46 public:
 47 
 48     //  initialize object of 'chains' type.
 49     //  initialize first element of 'data' type.
 50     chains(int e) 
 51     {
 52         if ( first == nullptr  &&  last == nullptr )
 53         {
 54             data *node = new data(e) ;
 55             node->pre = nullptr ;
 56             first = node ;
 57             last = node ;
 58         }
 59     }
 60 
 61     ~chains()
 62     {
 63         for ( ; first != nullptr ;   )
 64         {
 65             data *keep = first ->next ;
 66             delete first ;
 67             first = keep;
 68             std::cout << "[~chains]#\t work over. " << std::endl ;
 69         }
 70     }
 71 
 72     //  set element of 'data' type.
 73     void set_chains(int e)
 74     {
 75         if ( first != nullptr  &&  last != nullptr )
 76         {
 77             data *keep_current = last ;
 78             data *node = new data(e) ;
 79             keep_current->next = node ;
 80             node->pre = keep_current ;
 81             node->next = nullptr ;
 82             last = node ;
 83         }
 84     }
 85 
 86     //  loop chains from begin to end.
 87     void loop_front_chains()
 88     {
 89         data *loop = nullptr ;
 90         if ( first != nullptr )
 91         {
 92             loop = first ;
 93             for ( ;  loop != nullptr ;  loop = loop->next )
 94             {
 95                 std::cout << "[loop_front]#\t" << loop->val << std::endl ;
 96             }
 97         }
 98     }
 99 
100     //  loop chains from end to begin.
101     void loop_back_chains()
102     {
103         data *loop = nullptr ;
104         if ( last != nullptr )
105         {
106             loop = last ;
107             for ( ;  loop != nullptr ;  loop = loop->pre )
108             {
109                 std::cout << "[loop_back]#\t" << loop->val << std::endl ;
110             }
111         }
112     }
113 };
114 
115 
116 int main()
117 {
118     chains g(0) ;
119     g.set_chains(1);
120     g.set_chains(2);
121     g.set_chains(3);
122     g.set_chains(4);
123     g.loop_front_chains() ;
124     g.loop_back_chains();
125 }

三、运行结果

 1 [loop_front]#    0
 2 [loop_front]#    1
 3 [loop_front]#    2
 4 [loop_front]#    3
 5 [loop_front]#    4
 6 [loop_back]#    4
 7 [loop_back]#    3
 8 [loop_back]#    2
 9 [loop_back]#    1
10 [loop_back]#    0
11 [~data]#    4
12 [~chains]#     work over. 
13 [~data]#    3
14 [~chains]#     work over. 
15 [~data]#    2
16 [~chains]#     work over. 
17 [~data]#    1
18 [~chains]#     work over. 
19 [~data]#    0
20 [~chains]#     work over.

四、参考资料：

　　1、　　数据结构、算法与应用（c++语言描述）edition 2  -- {作者：sartaj sahni；译者：王立柱，刘志宏； 出版社：机械工业出版社； 版次：2020.10，第1版第13次印刷 }