• 数据结构实战开发教程（五）再论智能指针、循环链表的实现、双向链表的实现、双向循环链表的实现、Linux内核链表剖析

    二十七、再论智能指针（上）

    1、思考

    • 使用智能指针( SmartPointer )替换单链表( LinkList )中的原生指针是否可行？

    2、问题出在哪里？

    • SmartPointer的设计方案
      • 指针生命周期结束时主动释放堆空间
      • 一片堆空间最多只能由一个指针标识
      • 杜绝指针运算和指针比较

    3、新的设计方案

    是时候创建新的智能指针了！

    4、新的设计方案

    • Pointer是智能指针的抽象父类（模板）
      • 纯虚析构函数virtual ~Pointer() = 0;
      • 重载operator -> ()
      • 重载operator * ()

    5、编程实验：智能指针的新方案

    Pointer.h

    SmartPointer.h

    6、To be continued

    二十八、再论智能指针（下）

    1、完成SharedPointer类的具体实现

     

    2、SharedPointer设计要点

    • 类模板
      • 通过计数机制( ref )标识堆内存
        • 堆内存被指向时：ref++
        • 指针被置空时：ref--
        • ref == 0 时：释放堆内存

    3、计数机制原理剖析

    4、SharedPointer类的声明

    5、智能指针的比较

    由于SharedPointer支持多个对象同时指向一片堆空间；因此，必须支持比较操作！

    6、编程实验：智能指针的新成员

    SharedPointer.h

    1. #ifndef SHAREDPOINTER_H_
    2. #define SHAREDPOINTER_H_
    3. /*******************************************************************************
    4.  *                              Include _Files                                  *
    5.  *******************************************************************************/
    6. #include <cstdlib>
    7. #include "Pointer.h"
    8. #include "Exception.h"
    9. /*******************************************************************************
    10.  *                             Type Definition                                 *
    11.  *******************************************************************************/
    12. namespace DTLib
    13. {
    14.  
    15. template < typename T >
    16. class SharedPointer : public Pointer<T>
    17. {
    18. protected:
    19.     int* m_ref;                                                             // 计数机制成员指针
    20.  
    21.     // 获取当前的智能指针地址、计数变量地址、计数变量 +1
    22.     void assign(const SharedPointer<T>& obj)
    23.     {
    24.         this->m_ref = obj.m_ref;                                            // 获取共用的计数变量地址
    25.         this->m_pointer = obj.m_pointer;                                    // 获取共用的堆空间地址
    26.  
    27.         if( this->m_ref )
    28.         {
    29.             (*this->m_ref)++;                                               // 计数变量 +1
    30.         }
    31.     }
    32.  
    33. public:
    34.     // 构造函数
    35.     SharedPointer(T* p = NULL) : m_ref(NULL)
    36.     {
    37.         if( p )                                                             
    38.         {
    39.             this->m_ref = static_cast<int*>(std::malloc(sizeof(int)));      // 申请计数变量堆空间
    40.  
    41.             if( this->m_ref )
    42.             {
    43.                 *(this->m_ref) = 1;                                         // 计数变量 +1
    44.                 this->m_pointer = p;                                        // 获取p对应的堆空间
    45.             }
    46.             else
    47.             {
    48.                 THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create SharedPointer object ...");
    49.             }
    50.         }
    51.     }
    52.  
    53.     SharedPointer(const SharedPointer<T>& obj) : Pointer<T>(NULL)
    54.     {
    55.         assign(obj);                                                        // 获取当前的智能指针地址、计数变量地址、计数变量 +1
    56.     }
    57.  
    58.     SharedPointer<T>& operator= (const SharedPointer<T>& obj)
    59.     {
    60.         if( this != &obj )
    61.         {
    62.             clear();                                                        // 让当前的智能指针置空，计数变量 -1
    63.             assign(obj);                                                    // 获取当前的智能指针地址、计数变量地址、计数变量 +1
    64.         }
    65.  
    66.         return *this;
    67.     }
    68.  
    69.     // 让当前的智能指针置空，计数变量 -1
    70.     void clear()
    71.     {
    72.         T* toDel = this->m_pointer;
    73.         int* ref = this->m_ref;
    74.  
    75.         this->m_pointer = NULL;                                             // 智能指针指向的堆空间地址 置 NULL
    76.         this->m_ref = NULL;                                                 // 智能指针指向的计数变量地址 置 NULL
    77.  
    78.         if( ref )
    79.         {
    80.             (*ref)--;                                                       // 计数变量 -1
    81.  
    82.             if( *ref == 0 )                                                 // 计数变量为 0
    83.             {
    84.                 free(ref);                                                  // 释放共用的计数变量的堆空间
    85.  
    86.                 delete toDel;                                               // 释放共用的堆空间
    87.             }
    88.         }
    89.     }
    90.  
    91.     ~SharedPointer()
    92.     {
    93.         clear();                                                            // 让当前的智能指针置空，计数变量 -1
    94.     }
    95. };
    96.  
    97. // 支持比较操作  智能指针地址 <==> 智能指针地址 <==> 类对象地址
    98. template < typename T >
    99. static bool operator == (const T* l, const SharedPointer<T>& r)
    100. {
    101.     return (l == r.get());
    102. }
    103.  
    104. template < typename T >
    105. static bool operator != (const T* l, const SharedPointer<T>& r)
    106. {
    107.     return (l != r.get());
    108. }
    109.  
    110. template < typename T >
    111. static bool operator == (const SharedPointer<T>& l, const T* r)
    112. {
    113.     return (l.get() == r);
    114. }
    115.  
    116. template < typename T >
    117. static bool operator != (const SharedPointer<T>& l, const T* r)
    118. {
    119.     return (l.get() != r);
    120. }
    121.  
    122. template < typename T >
    123. static bool operator == (const SharedPointer<T>& l, const SharedPointer<T>& r)
    124. {
    125.     return (l.get() == r.get());
    126. }
    127.  
    128. template < typename T >
    129. static bool operator != (const SharedPointer<T>& l, const SharedPointer<T>& r)
    130. {
    131.     return !(l == r);
    132. }
    133. }
    134.  
    135. #endif // SHAREDPOINTER_H_

    7、智能指针的使用军规

    • 只能用来指向堆空间中的单个变量（对象）
    • 不同类型的智能指针对象不能混合使用
    • 不要使用delete释放智能指针指向的堆空间

    8、小结

    • SharedPointer最大程度的模拟了原生指针的行为
    • 计数机制确保多个智能指针合法的指向同一片堆空间
    • 智能指针只能用于指向堆空间中的内存
    • 不同类型的智能指针不要混合使用
    • 堆对象的生命周期由智能指针进行管理

    二十九、循环链表的实现

    1、什么是循环链表？

    • 概念上
      • 任意数据元素都有一个前驱和一个后继
      • 所有的数据元素的关系构成一个逻辑上的环
    • 实现上
      • 循环链表是一种特殊的单链表
      • 尾结点的指针域保存了首结点的地址

    2、循环链表的逻辑构成

    3、循环链表的继承层次结构

    4、循环链表的实现思路

    • 通过模板定义CircleList类，继承自LinkList类
    • 定义内部函数last_to_first()，用于将单链表首尾相连
    • 特殊处理：首元素的插入操作和删除操作
    • 重新实现：清空操作和遍历操作

    5、循环链表的实现要点

    • 插入位置为0时：
      • 头结点和尾结点均指向新结点
      • 新结点成为首结点插入链表
    • 删除位置为0时：
      • 头结点和尾结点指向位置为1的结点
      • 安全销毁首结点

    6、编程实验：循环链表的实现

    CircleList.h

    1. #ifndef CIRCLELIST_H_
    2. #define CIRCLELIST_H_
    3. /*******************************************************************************
    4.  *                              Include _Files                                  *
    5.  *******************************************************************************/
    6. #include "LinkList.h"
    7. /*******************************************************************************
    8.  *                             Type Definition                                 *
    9.  *******************************************************************************/
    10. namespace DTLib
    11. {
    12.  
    13. template < typename T >
    14. class CircleList : public LinkList<T>
    15. {
    16. protected:
    17.     typedef typename LinkList<T>::Node Node;                        // 使用typename的原因：编译器无法辨识标识符究竟是什么（是一个类型还是一个成员名称(静态数据成员或者静态函数)）
    18.  
    19.     int mod(int i) const                                            // 取余
    20.     {
    21.         return (this->m_length == 0) ? 0 : (i % this->m_length);
    22.     }
    23.  
    24.     Node* last() const                                              // 尾结点的指针
    25.     {
    26.         return this->position(this->m_length-1)->next;
    27.     }
    28.  
    29.     void last_to_first() const                                      // 将链表首尾相连
    30.     {
    31.         last()->next = this->m_header.next;                         // 尾结点指向首结点
    32.     }
    33.  
    34. public:
    35. /**********************************************************************
    36. * Function:        insert()
    37. * Description:      插入新结点(函数重载)
    38. * Input:            i                   在位置i插入新结点(默认插在最后)
    39. *                   e                   带插入结点的数据(value)
    40. * Output:           
    41. * Return:           bool                判断插入结点位置是否合法
    42. * Others:           异常                申请内存是否成功
    43. * Modify   Date     Version    Author      Modification
    44. * ------------------------------------------------------------
    45. *       2022/03/19    1.0                         Create        
    46. **********************************************************************/
    47.     bool insert(const T& e)
    48.     {
    49.         return insert(this->m_length, e);
    50.     }
    51.  
    52.     bool insert(int i, const T& e)
    53.     {
    54.         bool ret = true;
    55.  
    56.         i = i % (this->m_length + 1);                               // 取余 
    57.  
    58.         ret = LinkList<T>::insert(i, e);                            // 调用父类的插入函数
    59.  
    60.         if( ret && (i == 0) )                                       // 处理特殊情况(首结点)
    61.         {
    62.             last_to_first();                                        // 将链表首尾相连
    63.         }
    64.  
    65.         return ret;
    66.     }
    67.  
    68. /**********************************************************************
    69. * Function:        remove()
    70. * Description:      删除结点
    71. * Input:            i                   在位置i删除结点
    72. * Output:           
    73. * Return:           bool                判断删除结点位置是否合法
    74. * Others:           
    75. * Modify   Date     Version    Author      Modification
    76. * ------------------------------------------------------------
    77. *       2022/03/19    1.0                         Create        
    78. **********************************************************************/
    79.     bool remove(int i)
    80.     {
    81.         bool ret = true;
    82.  
    83.         i = mod(i);                                                 // 取余
    84.  
    85.         if( i == 0 )                                                // 处理特殊情况(首结点)
    86.         {
    87.             Node* toDel = this->m_header.next;                      // 获取首结点地址
    88.  
    89.             if( toDel != NULL )
    90.             {
    91.                 this->m_header.next = toDel->next;                  // 头结点指向 1 结点
    92.                 this->m_length--;                                   // 当前线性表长度 -1
    93.  
    94.                 if( this->m_length > 0 )                            // 当前结点不是最后一个结点
    95.                 {
    96.                     last_to_first();                                // 将链表首尾相连
    97.  
    98.                     if( this->m_current == toDel )                  // 判断游标是否指向 待删除结点的地址
    99.                     {
    100.                         this->m_current = toDel->next;              // 指向 待删除结点的下一个结点的地址
    101.                     }
    102.                 }
    103.                 else
    104.                 {
    105.                     this->m_header.next = NULL;                     // 头结点置 NULL
    106.                     this->m_current = NULL;                         // 当前结点置 NULL
    107.                 }
    108.  
    109.                 this->destroy(toDel);                               //  为了异常安全，最后销毁结点
    110.             }
    111.             else
    112.             {
    113.                 ret = false;
    114.             }
    115.         }
    116.         else
    117.         {
    118.             ret = LinkList<T>::remove(i);                           // 若不是特殊情况，调用父类函数实现
    119.         }
    120.  
    121.         return ret;
    122.     }
    123.  
    124. /**********************************************************************
    125. * Function:        set()
    126. * Description:      修改第i个结点的值
    127. * Input:            i                   待修改结点的位置
    128. * Output:           
    129. * Return:           bool                判断修改结点位置是否合法
    130. * Others:           O(n)
    131. * Modify   Date     Version    Author      Modification
    132. * ------------------------------------------------------------
    133. *       2022/03/19    1.0                         Create        
    134. **********************************************************************/
    135.     bool set(int i, const T& e)
    136.     {
    137.         return LinkList<T>::set(mod(i), e);
    138.     }
    139. /**********************************************************************
    140. * Function:        get()
    141. * Description:      获取第i个结点的值(函数重载)
    142. * Input:            i                   待获取结点的位置
    143. * Output:           
    144. * Return:           bool                判断获取结点位置是否合法
    145. * Others:           O(n)
    146. * Modify   Date     Version    Author      Modification
    147. * ------------------------------------------------------------
    148. *       2022/03/19    1.0                         Create        
    149. **********************************************************************/
    150.     T get(int i) const
    151.     {
    152.         return LinkList<T>::get(mod(i));
    153.     }
    154.  
    155.     bool get(int i, T& e) const
    156.     {
    157.         return LinkList<T>::get(mod(i), e);
    158.     }
    159.  
    160. /**********************************************************************
    161. * Function:        find()
    162. * Description:      查找指定元素的位置
    163. * Input:            e                   待查找结点的值(value)
    164. * Output:           
    165. * Return:           int                 返回结点的位置
    166. * Others:           O(n)
    167. * Modify   Date     Version    Author      Modification
    168. * ------------------------------------------------------------
    169. *       2022/03/19    1.0                         Create        
    170. **********************************************************************/
    171.     int find(const T& e) const
    172.     {
    173.         int ret = -1;
    174.         Node* slider = this->m_header.next;                         // 获取 0 元素的地址
    175.  
    176.         for(int i=0; i<this->m_length; i++)
    177.         {
    178.             if( slider->value == e )                                // 判断值是否相等
    179.             {
    180.                 ret = i;                                            // 获取位置
    181.                 break;
    182.             }
    183.  
    184.             slider = slider->next;                                  // 移动到下一个结点
    185.         }
    186.  
    187.         return ret;
    188.     }
    189.  
    190. /**********************************************************************
    191. * Function:        clear()
    192. * Description:      清空线性表
    193. * Input:            
    194. * Output:           
    195. * Return:           
    196. * Others:           O(n)
    197. * Modify   Date     Version    Author      Modification
    198. * ------------------------------------------------------------
    199. *       2022/03/19    1.0                         Create        
    200. **********************************************************************/
    201.     void clear()
    202.     {
    203.         while( this->m_length > 1 )
    204.         {
    205.             remove(1);                                              // 为了效率  remove(0)
    206.         }
    207.  
    208.         if( this->m_length == 1 )                                   // 处理特殊情况(只剩首结点)
    209.         {
    210.             Node* toDel = this->m_header.next;
    211.  
    212.             this->m_header.next = NULL;
    213.             this->m_length = 0;
    214.             this->m_current = NULL;
    215.  
    216.             this->destroy(toDel);
    217.         }
    218.     }
    219.  
    220. /**********************************************************************
    221. * Function:        move()
    222. * Description:      将游标定位到目标位置(i)
    223. * Input:            i                   移动到第i个元素
    224. *                   step                步进默认为 1
    225. * Output:           
    226. * Return:           bool                判断i位置是否合法
    227. * Others:           O(n)
    228. * Modify   Date     Version    Author      Modification
    229. * ------------------------------------------------------------
    230. *       2022/03/19    1.0                         Create        
    231. **********************************************************************/
    232.     bool move(int i, int step)                                      // 遍历所有元素
    233.     {
    234.         return LinkList<T>::move(mod(i), step);
    235.     }
    236.  
    237. /**********************************************************************
    238. * Function:        end()
    239. * Description:      游标是否到达尾部
    240. * Input:            
    241. * Output:           
    242. * Return:           bool                游标是否到达尾部
    243. * Others:           
    244. * Modify   Date     Version    Author      Modification
    245. * ------------------------------------------------------------
    246. *       2022/03/19    1.0                         Create        
    247. **********************************************************************/
    248.     bool end()
    249.     {
    250.         return (this->m_length == 0) || (this->m_current == NULL);
    251.     }
    252.  
    253. /**********************************************************************
    254. * Function:        ~LinkList()
    255. * Description:      析构函数  -  清空线性表
    256. * Input:            
    257. * Output:           
    258. * Return:           
    259. * Others:           O(n)
    260. * Modify   Date     Version    Author      Modification
    261. * ------------------------------------------------------------
    262. *       2022/03/19    1.0                         Create        
    263. **********************************************************************/
    264.     ~CircleList()
    265.     {
    266.         clear();
    267.     }
    268. };
    269.  
    270. }
    271.  
    272.  
    273. #endif // CIRCLELIST_H_

    7、循环链表的应用

    • 约瑟夫环问题

            

    8、编程实验：约瑟夫问题

    main.cpp

    1. #include <iostream>
    2. #include "./DTLib/CircleList.h"
    3.  
    4. using namespace std;
    5. using namespace DTLib;
    6.  
    7. void josephus(int n, int s, int m)
    8. {
    9.     CircleList<int> cl;
    10.  
    11.     for(int i=1; i<=n; i++)
    12.     {
    13.         cl.insert(i);
    14.     }
    15.  
    16.     cl.move(s-1,m-1);  //游标指向0处，步长2
    17.  
    18.     int i=0;
    19.  
    20.     while( cl.length() > 0 )
    21.     {
    22.         cl.next();
    23.  
    24.         cout << cl.current() <<endl;  //当前要自杀的
    25.  
    26.         int index=cl.find(cl.current());
    27.         cl.remove(index);
    28.     }
    29. }
    30.  
    31. int main()
    32. {
    33.     josephus(41,1,3);  //41个人，从1号开始数，数到第三个人开始自杀
    34.  
    35.     return 0;
    36. }

    9、小结

    • 循环链表是一种特殊的单链表
    • 尾结点的指针域保存了首结点的地址
    • 特殊处理首元素的插入操作和删除操作
    • 重新实现清空操作和遍历操作

     

    三十、双向链表的实现

    1、交流中

            

    2、单链表的另一个缺陷

    • 单向性
      • 只能从头结点开始高效访问链表中的数据元素
    • 缺陷
      • 如果需要逆向访问单链表中的数据元素将极其低效

            

    3、新的线性表

    • 设计思路：

    在“单链表”的结点中增加一个指针 pre ,用于指向当前结点的前驱结点。

            

    4、双向链表的继承层次结构

    5、DualLinkList的定义

    6、编程实验：双向链表的实现

    DualLinkList.h

    1. #ifndef DUALLINKLIST_H_
    2. #define DUALLINKLIST_H_
    3. /*******************************************************************************
    4.  *                              Include Files                                  *
    5.  *******************************************************************************/
    6. #include "List.h"
    7. #include "Exception.h"
    8. /*******************************************************************************
    9.  *                             Type Definition                                 *
    10.  *******************************************************************************/
    11. namespace DTLib
    12. {
    13.  
    14. template < typename T >
    15. class DualLinkList : public List<T>
    16. {
    17. protected:
    18.     struct Node : public Object
    19.     {
    20.         T value;                                                    // 数据域
    21.         Node* next;                                                 // 后继指针
    22.         Node* pre;                                                  // 前驱指针
    23.     };
    24.  
    25.     mutable struct : public Object                                  // mutable 突破const的限制而设置,永远处于可变的状态,即使在一个const函数中
    26.     {
    27.         char reserved[sizeof(T)];                                   // 为了与Node内存对齐，以便后续使用强制类型转换，继承于Object同理。
    28.         Node* next;                                                 // 指向首结点
    29.         Node* pre;                                                  // 内存对齐
    30.     } m_header;                                                     // 创建头结点  不直接用 Node m_header，因为T有可能是类，在类运行构造函数时，可能会抛出异常
    31.  
    32.     int m_length;                                                   // 当前线性表的长度
    33.  
    34.     int m_step;                                                     // 步进次数    遍历元素的时候使用 move(); end(); next(); current()
    35.     Node* m_current;                                                // 游标       遍历元素的时候使用 move(); end(); next(); current()
    36.  
    37. /**********************************************************************
    38. * Function:        position()
    39. * Description:      移动i次，返回第i-1个结点的地址
    40. * Input:            i                   数组类地址
    41. *                   m_header            头结点地址
    42. * Output:           
    43. * Return:           Node                返回第i-1个结点的地址
    44. * Others:           O(n)
    45. * Modify   Date     Version    Author      Modification
    46. * ------------------------------------------------------------
    47. *       2022/03/19    1.0                         Create        
    48. **********************************************************************/
    49.     Node* position(int i) const
    50.     {
    51.         Node* ret = reinterpret_cast<Node*>(&m_header);             // 头结点地址 - 强制类型转换
    52.  
    53.         for(int p=0; p<i; p++)                                      // 移动i次
    54.         {
    55.             ret = ret->next;
    56.         }
    57.  
    58.         return ret;
    59.     }
    60.  
    61. /**********************************************************************
    62. * Function:        create()
    63. * Description:      创建新结点(堆空间)
    64. * Input:            
    65. * Output:           
    66. * Return:           Node                返回新结点的地址
    67. * Others:           
    68. * Modify   Date     Version    Author      Modification
    69. * ------------------------------------------------------------
    70. *       2022/03/19    1.0                         Create        
    71. **********************************************************************/
    72.     virtual Node* create()
    73.     {
    74.         return new Node();
    75.     }
    76.  
    77. /**********************************************************************
    78. * Function:        destroy()
    79. * Description:      销毁结点(堆空间)
    80. * Input:            pn                  待销毁的结点
    81. * Output:           
    82. * Return:           
    83. * Others:           
    84. * Modify   Date     Version    Author      Modification
    85. * ------------------------------------------------------------
    86. *       2022/03/19    1.0                         Create        
    87. **********************************************************************/
    88.     virtual void destroy(Node* pn)
    89.     {
    90.         delete pn;
    91.     }
    92.  
    93. public:
    94. /**********************************************************************
    95. * Function:        DualLinkList()
    96. * Description:      构造函数 - 初始化参数
    97. * Input:            
    98. * Output:           
    99. * Return:           
    100. * Others:           
    101. * Modify   Date     Version    Author      Modification
    102. * ------------------------------------------------------------
    103. *       2022/03/19    1.0                         Create        
    104. **********************************************************************/
    105.     DualLinkList()
    106.     {
    107.         m_header.next = NULL;
    108.         m_header.pre = NULL;
    109.         m_length = 0;
    110.         m_step = 1;
    111.         m_current = NULL;
    112.     }
    113.  
    114. /**********************************************************************
    115. * Function:        insert()
    116. * Description:      插入新结点(函数重载)
    117. * Input:            i                   在位置i插入新结点(默认插在最后)
    118. *                   e                   带插入结点的数据(value)
    119. * Output:           
    120. * Return:           bool                判断插入结点位置是否合法
    121. * Others:           异常                申请内存是否成功
    122. * Modify   Date     Version    Author      Modification
    123. * ------------------------------------------------------------
    124. *       2022/03/19    1.0                         Create        
    125. **********************************************************************/
    126.     bool insert(const T& e)
    127.     {
    128.         return insert(m_length, e);                                 // 新结点插在最后
    129.     }
    130.  
    131.     bool insert(int i, const T& e)
    132.     {
    133.         bool ret = ((0 <= i) && (i <= m_length));                   // 位置i合法性校验
    134.  
    135.         if( ret )
    136.         {
    137.             Node* node = create();                                  // 创建新结点 - 申请内存
    138.  
    139.             if( node != NULL )
    140.             {
    141.                 Node* current = position(i);                        // 获取新结点前一个结点的地址
    142.                 Node* next = current->next;                         // 获取新结点后一个结点的地址
    143.  
    144.                 node->value = e;                                    // 新结点的数据域(value)赋值
    145.  
    146.                 node->next = next;                                  // 新结点后继指针赋值
    147.                 current->next = node;                               // 前一个结点后继指向新结点
    148.  
    149.                 if( current != reinterpret_cast<Node*>(&m_header) ) // 前一个结点不为头结点
    150.                 {
    151.                     node->pre = current;                            // 新结点前继指针赋值
    152.                 }
    153.                 else
    154.                 {
    155.                     node->pre = NULL;                               // 新结点前继指针置 0
    156.                 }
    157.  
    158.                 if( next != NULL )                                  // 后一个结点存在
    159.                 {
    160.                     next->pre = node;                               // 后一个结点的前继指针赋值
    161.                 }
    162.  
    163.                 m_length++;                                         // 当前线性表的长度 +1
    164.             }
    165.             else
    166.             {
    167.                 THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");
    168.             }
    169.         }
    170.  
    171.         return ret;
    172.     }
    173.  
    174. /**********************************************************************
    175. * Function:        remove()
    176. * Description:      删除结点
    177. * Input:            i                   在位置i删除结点
    178. * Output:           
    179. * Return:           bool                判断删除结点位置是否合法
    180. * Others:           O(n)
    181. * Modify   Date     Version    Author      Modification
    182. * ------------------------------------------------------------
    183. *       2022/03/19    1.0                         Create        
    184. **********************************************************************/
    185.     bool remove(int i)
    186.     {
    187.         bool ret = ((0 <= i) && (i < m_length));                    // 位置i合法性校验
    188.  
    189.         if( ret )
    190.         {
    191.             Node* current = position(i);                            // 获取待删除结点前一个结点的地址
    192.             Node* toDel = current->next;                            // 临时保存 待删除结点的地址
    193.             Node* next = toDel->next;                               // 获取待删除结点后一个结点的地址
    194.  
    195.             if( m_current == toDel )                                // 判断游标是否指向 待删除结点的地址
    196.             {
    197.                 m_current = next;                                   // 指向 待删除结点的下一个结点的地址
    198.             }
    199.  
    200.             current->next = next;                                   // 待删除结点的下一个结点的地址，赋值给待删除结点的前一个结点的next
    201.  
    202.             if( next != NULL )                                      // 待删除结点后还有结点
    203.             {
    204.                 next->pre = toDel->pre;                             // 待删除结点的前驱地址，赋值给下一个结点的前驱指针  
    205.             }
    206.  
    207.             m_length--;                                             // 当前线性表的长度 -1   为了防止元素为类时，析构函数抛出异常，无法保证链表的安全性
    208.  
    209.             destroy(toDel);                                         // 释放该结点所占得内存
    210.         }
    211.  
    212.         return ret;
    213.     }
    214.  
    215. /**********************************************************************
    216. * Function:        set()
    217. * Description:      修改第i个结点的值
    218. * Input:            i                   待修改结点的位置
    219. * Output:           
    220. * Return:           bool                判断修改结点位置是否合法
    221. * Others:           O(n)
    222. * Modify   Date     Version    Author      Modification
    223. * ------------------------------------------------------------
    224. *       2022/03/19    1.0                         Create        
    225. **********************************************************************/
    226.     bool set(int i, const T& e)
    227.     {
    228.         bool ret = ((0 <= i) && (i < m_length));            // 位置i合法性校验
    229.  
    230.         if( ret )
    231.         {
    232.             position(i)->next->value = e;                   // 待修改结点的前一个结点->next == 待修改的结点的地址
    233.         }
    234.  
    235.         return ret;
    236.     }
    237.  
    238. /**********************************************************************
    239. * Function:        get()
    240. * Description:      获取第i个结点的值(函数重载)
    241. * Input:            i                   待获取结点的位置
    242. * Output:           
    243. * Return:           bool                判断获取结点位置是否合法
    244. * Others:           O(n)
    245. * Modify   Date     Version    Author      Modification
    246. * ------------------------------------------------------------
    247. *       2022/03/19    1.0                         Create        
    248. **********************************************************************/
    249.     virtual T get(int i) const
    250.     {
    251.         T ret;
    252.  
    253.         if( get(i, ret) )
    254.         {
    255.             return ret;
    256.         }
    257.         else
    258.         {
    259.             THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element ...");
    260.         }
    261.  
    262.         return ret;
    263.     }
    264.  
    265.     bool get(int i, T& e) const
    266.     {
    267.         bool ret = ((0 <= i) && (i < m_length));            // 位置i合法性校验
    268.  
    269.         if( ret )
    270.         {
    271.             e = position(i)->next->value;                   // 待获取结点的前一个结点->next == 待获取的结点的地址
    272.         }
    273.  
    274.         return ret;
    275.     }
    276.  
    277. /**********************************************************************
    278. * Function:        find()
    279. * Description:      查找指定元素的位置
    280. * Input:            e                   待查找结点的值(value)
    281. * Output:           
    282. * Return:           int                 返回结点的位置
    283. * Others:           O(n)
    284. * Modify   Date     Version    Author      Modification
    285. * ------------------------------------------------------------
    286. *       2022/03/19    1.0                         Create        
    287. **********************************************************************/
    288.     int find(const T& e) const
    289.     {
    290.         int ret = -1;
    291.         int i = 0;
    292.         Node* node = m_header.next;                         // 获取 0 元素的地址
    293.  
    294.         while( node )
    295.         {
    296.             if( node->value == e )                          // 判断值是否相等
    297.             {
    298.                 ret = i;                                    // 获取位置
    299.                 break;
    300.             }
    301.             else
    302.             {
    303.                 node = node->next;                          // 移动到下一个结点
    304.                 i++;                                        // 位置 +1
    305.             }
    306.         }
    307.  
    308.         return ret;
    309.     }
    310.  
    311.  
    312. /**********************************************************************
    313. * Function:        length()
    314. * Description:      当前线性表的长度
    315. * Input:            
    316. * Output:           
    317. * Return:           int                 当前线性表的长度
    318. * Others:           O(1)
    319. * Modify   Date     Version    Author      Modification
    320. * ------------------------------------------------------------
    321. *       2022/03/19    1.0                         Create        
    322. **********************************************************************/
    323.     int length() const
    324.     {
    325.         return m_length;
    326.     }
    327.  
    328. /**********************************************************************
    329. * Function:        clear()
    330. * Description:      清空线性表
    331. * Input:            
    332. * Output:           
    333. * Return:           
    334. * Others:           O(n)
    335. * Modify   Date     Version    Author      Modification
    336. * ------------------------------------------------------------
    337. *       2022/03/19    1.0                         Create        
    338. **********************************************************************/
    339.     void clear()
    340.     {
    341.         while( m_length > 0 )                              // 循环删除首结点
    342.         {
    343.             remove(0);
    344.         }
    345.     }
    346.  
    347. /*
    348.     遍历所有元素  推荐使用方法
    349.         移动到0号元素   判断是否到尾部  移动到下一个结点
    350.     for (list.move(0); !list.end();list.next())
    351.     {
    352.         cout << list.current() << endl;
    353.     }
    354.         移动到尾元素   判断是否到首部  移动到上一个结点
    355.     for (list.move(list.length()-1); !list.end();list.pre())
    356.     {
    357.         cout << list.current() << endl;
    358.     }
    359. */
    360. /**********************************************************************
    361. * Function:        move()
    362. * Description:      将游标定位到目标位置(i)
    363. * Input:            i                   移动到第i个元素
    364. *                   step                步进默认为 1
    365. * Output:           
    366. * Return:           bool                判断i位置是否合法
    367. * Others:           
    368. * Modify   Date     Version    Author      Modification
    369. * ------------------------------------------------------------
    370. *       2022/03/19    1.0                         Create        
    371. **********************************************************************/
    372.     virtual bool move(int i, int step = 1)
    373.     {
    374.         bool ret = (0 <= i) && (i < m_length) && (step > 0);
    375.  
    376.         if( ret )
    377.         {
    378.             m_current = position(i)->next;                  // 目标位置的地址
    379.             m_step = step;
    380.         }
    381.  
    382.         return ret;
    383.     }
    384.  
    385. /**********************************************************************
    386. * Function:        end()
    387. * Description:      游标是否到达尾部
    388. * Input:            
    389. * Output:           
    390. * Return:           bool                游标是否到达尾部
    391. * Others:           
    392. * Modify   Date     Version    Author      Modification
    393. * ------------------------------------------------------------
    394. *       2022/03/19    1.0                         Create        
    395. **********************************************************************/
    396.     virtual bool end()
    397.     {
    398.         return (m_current == NULL);
    399.     }
    400.  
    401. /**********************************************************************
    402. * Function:        current()
    403. * Description:      获取游标所指向的数据元素
    404. * Input:            
    405. * Output:           
    406. * Return:           T                   游标所指向的数据元素
    407. * Others:           异常                游标已到尾部，无法获取到值
    408. * Modify   Date     Version    Author      Modification
    409. * ------------------------------------------------------------
    410. *       2022/03/19    1.0                         Create        
    411. **********************************************************************/
    412.     virtual T current()
    413.     {
    414.         if( !end() )                                        // 游标是否到达尾部
    415.         {
    416.             return m_current->value;
    417.         }
    418.         else
    419.         {
    420.             THROW_EXCEPTION(InvalidOperationException, "No value at current position ...");
    421.         }
    422.     }
    423.  
    424. /**********************************************************************
    425. * Function:        next()
    426. * Description:      向后移动游标 m_step次
    427. * Input:            
    428. * Output:           
    429. * Return:           bool                是否成功移动游标 m_step次
    430. * Others:           
    431. * Modify   Date     Version    Author      Modification
    432. * ------------------------------------------------------------
    433. *       2022/03/19    1.0                         Create        
    434. **********************************************************************/
    435.     virtual bool next()
    436.     {
    437.         int i = 0;
    438.  
    439.         while( (i < m_step) && !end() )                 // 移动次数是否为m_step && 游标是否到达尾部
    440.         {
    441.             m_current = m_current->next;                // 移动一次游标
    442.             i++;
    443.         }
    444.  
    445.         return (i == m_step);
    446.     }
    447.  
    448.  
    449. /**********************************************************************
    450. * Function:        pre()
    451. * Description:      向前移动游标 m_step次
    452. * Input:            
    453. * Output:           
    454. * Return:           bool                是否成功移动游标 m_step次
    455. * Others:           
    456. * Modify   Date     Version    Author      Modification
    457. * ------------------------------------------------------------
    458. *       2022/03/19    1.0                         Create        
    459. **********************************************************************/
    460.     virtual bool pre()
    461.     {
    462.         int i = 0;
    463.  
    464.         while( (i < m_step) && !end() )                 // 移动次数是否为m_step && 游标是否到达尾部
    465.         {
    466.             m_current = m_current->pre;                 // 移动一次游标
    467.             i++;
    468.         }
    469.  
    470.         return (i == m_step);
    471.     }
    472.  
    473. /**********************************************************************
    474. * Function:        ~DualLinkList()
    475. * Description:      析构函数  -  清空线性表
    476. * Input:            
    477. * Output:           
    478. * Return:           
    479. * Others:           O(n)
    480. * Modify   Date     Version    Author      Modification
    481. * ------------------------------------------------------------
    482. *       2022/03/19    1.0                         Create        
    483. **********************************************************************/
    484.     ~DualLinkList()
    485.     {
    486.         clear();
    487.     }
    488. };
    489.  
    490. }
    491.  
    492. #endif // DUALLINKLIST_H_

    7、小结

    • 双向链表是为了弥补单链表的缺陷而重新设计的
    • 在概念上，双向链表不是单链表，没有继承关系
    • 双向链表中的游标能够直接访问当前结点的前驱和后继
    • 双向链表是线性表概念的最终实现(更贴近理论上的线性表)

    8、深度思考

    • 有些设计，会让两者的呈现继承关系。没有对与错。考虑的不同。
    • 代码后期的维护性和软件产品的维护性。

    三十一、老生常谈的两个宏（Linux）

    1、Linux内核中常用的两个宏定义

    2、见招拆招 - 第一式：编译器做了什么？

    • offsetof用于计算TYPE结构体中MEMBER成员的偏移位置。

    • 编译器清楚的知道结构体成员变量的偏移位置
    • 通过结构体变量首地址与偏移量定位成员变量

    3、编程实验：offsetof 原理剖析

    1. #include <stdio.h>
    2.  
    3. #ifndef offsetof
    4. #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE*)0)->MEMBER)
    5. #endif
    6.  
    7.  
    8. struct ST
    9. {
    10.     int i;     // 0
    11.     int j;     // 4
    12.     char c;    // 8
    13. };
    14.  
    15. void func(struct ST* pst)
    16. {
    17.     int* pi = &(pst->i);    //  0
    18.     int* pj = &(pst->j);    //  4
    19.     char* pc = &(pst->c);   //  8
    20.  
    21.     printf("pst = %p\n", pst);
    22.     printf("pi = %p\n", pi);
    23.     printf("pj = %p\n", pj);
    24.     printf("pc = %p\n", pc);
    25. }
    26.  
    27. int main()
    28. {
    29.     struct ST s = {0};
    30.  
    31.     func(&s);
    32.     func(NULL);
    33.  
    34.     printf("offset i: %ld\n", offsetof(struct ST, i));
    35.     printf("offset j: %ld\n", offsetof(struct ST, j));
    36.     printf("offset c: %ld\n", offsetof(struct ST, c));
    37.  
    38.     return 0;
    39. }

    4、见招拆招 - 第二式：({})是何方神圣？

    • ({}) 是GNU C编译器的语法扩展
    • ({}) 与逗号表达式类似，结果为最后一个语句的值

    5、见招拆招 - 第三式：typeof是一个关键字吗？

    • typeof是GNU C编译器的特有关键字
    • typeof只在编译期生效，用于得到变量的类型

            

    6、见招拆招 - 第四式：最后的原理

    当已知pc和结构成员地址偏移量，求首地址。

    7、编程实验：container_of 原理剖析

    1. #include <stdio.h>
    2.  
    3. #ifndef offsetof
    4. #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE*)0)->MEMBER)
    5. #endif
    6.  
    7. #ifndef container_of
    8. #define container_of(ptr, type, member) ({		         \
    9.         const typeof(((type*)0)->member)* __mptr = (ptr);   \
    10.         (type*)((char*)__mptr - offsetof(type, member)); })
    11. #endif
    12.  
    13. #ifndef container_of_new
    14. #define container_of_new(ptr, type, member) ((type*)((char*)(ptr) - offsetof(type, member)))
    15. #endif
    16.  
    17.  
    18. struct ST
    19. {
    20.     int i;     // 0
    21.     int j;     // 4
    22.     char c;    // 8
    23. };
    24.  
    25. void method_1()
    26. {
    27.     int a = 0;
    28.     int b = 0;
    29.  
    30.     int r = (
    31.            a = 1,
    32.            b = 2,
    33.            a + b
    34.                 );
    35.  
    36.     printf("r = %d\n", r);
    37. }
    38.  
    39. void method_2()
    40. {
    41.     int r = ( {
    42.                   int a = 1;
    43.                   int b = 2;
    44.  
    45.                   a + b;
    46.               } );
    47.  
    48.     printf("r = %d\n", r);
    49. }
    50.  
    51. void type_of()
    52. {
    53.     int i = 100;
    54.     typeof(i) j = i;
    55.     const typeof(j)* p = &j;
    56.  
    57.     printf("sizeof(j) = %d\n", sizeof(j));
    58.     printf("j = %d\n", j);
    59.     printf("*p = %d\n", *p);
    60. }
    61.  
    62. int main()
    63. {
    64.  
    65.     // method_1();
    66.     // method_2();
    67.     // type_of();
    68.  
    69.     struct ST s = {0};
    70.     char* pc = &s.c;
    71.     int e = 0;
    72.     int* pe = &e;
    73.  
    74.     struct ST* pst = container_of(pc, struct ST, c);
    75.  
    76.     printf("&s = %p\n", &s);
    77.     printf("pst = %p\n", pst);
    78.  
    79.     return 0;
    80. }

    8、小结

    • 编译器清楚的知道结构体成员变量的偏移位置
    • ({ })与逗号表达式类似（但是可以定义新的局部变量），结果为最后一个语句的值
    • typeof只在编译期生效，用于得到变量的类型
    • container_of使用({})进行类型安全检查（逗号表达式中不可以定义变量）

     

    三十二、Linux内核链表剖析

    1、目标

    • 移植Linux内核链表，使其适用于非GNU编译器
    • 分析Linux内核中链表的基本实现

    2、Linux内核链表的位置及依赖

    • 位置
      • {linux-2.6.39}\\include\linux\list.h
    • 依赖
      • #include <linux/types.h>
      • #include <linux /stddef.h>
      • #include <linux/poison.h>
      • #include <linux/prefetch.h>

    3、移植时的注意事项

    • 清除文件间的依赖
      • 剥离依赖文件中与链表实现相关的代码
    • 清除平台相关代码（GNU C )
      • ({})
      •  typeof
      • _builtin_prefetch  (提高访问效率)  -  直接删除
      • static inline（支持同时使用）-  删除inline

    4、编程实验：Linux内核源码的移植

    list.h

    5、Linux内核链表的实现

    • 带头节点的双向循环链表，且头节点为表中成员
    • 头结点的next指针指向首结点
    • 头节点的prev指针指向尾结点

    6、Linux内核链表的结点定义

    7、使用struct list_head自定义链表结点

    8、编程实验：Linux内核链表初体验

    main.c

    9、Linux内核链表的插入操作

    • 在链表头部插入：list_add (new, head)
    • 在链表尾部插入：list_add_tail (new, head)

            

    10、Linux内核链表的删除操作

            

    11、Linux内核链表的遍历

    • 正向遍历：list_for_each(pos, head)
    • 逆向遍历：list_for_each_prev(pos, head)

    12、编程实验：Linux内核链表的使用

    main.c

    1. #include <stdio.h>
    2. #include "LinuxList.h"
    3.  
    4. void list_demo_1()
    5. {
    6.     struct Node
    7.     {
    8.         struct list_head head;
    9.         int value;
    10.     };
    11.  
    12.     struct Node l = {0};
    13.     struct list_head* list = (struct list_head*)&l;
    14.     struct list_head* slider = NULL;
    15.     int i = 0;
    16.  
    17.     INIT_LIST_HEAD(list);
    18.  
    19.     printf("Insert begin ...\n");
    20.  
    21.     for(i=0; i<5; i++)
    22.     {
    23.         struct Node* n = (struct Node*)malloc(sizeof(struct Node));
    24.  
    25.         n->value = i;
    26.  
    27.         list_add_tail((struct list_head*)n, list);
    28.     }
    29.  
    30.     list_for_each(slider, list)
    31.     {
    32.         printf("%d\n", ((struct Node*)slider)->value);
    33.     }
    34.  
    35.     printf("Insert end ...\n");
    36.  
    37.     printf("Delete begin ...\n");
    38.  
    39.     list_for_each(slider, list)
    40.     {
    41.         if( ((struct Node*)slider)->value == 3 )
    42.         {
    43.             list_del(slider);
    44.             free(slider);
    45.             break;
    46.         }
    47.     }
    48.  
    49.     list_for_each(slider, list)
    50.     {
    51.         printf("%d\n", ((struct Node*)slider)->value);
    52.     }
    53.  
    54.     printf("Delete end ...\n");
    55. }
    56.  
    57. void list_demo_2()
    58. {
    59.     struct Node
    60.     {
    61.         int value;
    62.         struct list_head head;
    63.     };
    64.  
    65.     struct Node l = {0};
    66.     struct list_head* list = &l.head;
    67.     struct list_head* slider = NULL;
    68.     int i = 0;
    69.  
    70.     INIT_LIST_HEAD(list);
    71.  
    72.     printf("Insert begin ...\n");
    73.  
    74.     for(i=0; i<5; i++)
    75.     {
    76.         struct Node* n = (struct Node*)malloc(sizeof(struct Node));
    77.  
    78.         n->value = i;
    79.  
    80.         list_add(&n->head, list);
    81.     }
    82.  
    83.     list_for_each(slider, list)
    84.     {
    85.         printf("%d\n", list_entry(slider, struct Node, head)->value);
    86.     }
    87.  
    88.     printf("Insert end ...\n");
    89.  
    90.  
    91.     printf("Delete begin ...\n");
    92.  
    93.     list_for_each(slider, list)
    94.     {
    95.         struct Node* n = list_entry(slider, struct Node, head);
    96.  
    97.         if( n->value == 3 )
    98.         {
    99.             list_del(slider);
    100.             free(n);
    101.             break;
    102.         }
    103.     }
    104.  
    105.     list_for_each(slider, list)
    106.     {
    107.         printf("%d\n", list_entry(slider, struct Node, head)->value);
    108.     }
    109.  
    110.     printf("Delete end ...\n");
    111. }
    112.  
    113. int main()
    114. {
    115.     // list_demo_1();
    116.     // list_demo_2();
    117.  
    118.     return 0;
    119. }

    13、小结

    • Linux内核链表移植时需要剔除依赖以及平台相关代码
    • Linux内核链表是带头节点的双向循环链表
    • 使用Linux内核链表时需要自定义链表结点
      • 将struct list_head 作为结点结构体的第一个成员或最后一个成员
      • struct list_head 作为最后一个成员时，需要使用list_entry宏
      • list_entry的定义中使用了container_of宏

     

    三十三、双向循环链表的实现

    1、目标

    • 使用Linux内核链表实现 DTLib中的双向循环链表
    • template < typename T > class DualCircleList;

    2、DTLib中双向循环链表的设计思路

    数据结点之间在逻辑上构成双向循环链表，头结点仅用于结点的定位。

    3、实现思路

    • 通过模板定义 DualCircleList类，继承自DualLinkList类
    • 在DualCircleList内部使用Linux内核链表进行实现
    • 使用struct list_head定义 DualCircleList的头结点
    • 特殊处理：循环遍历时忽略头结点

    4、实现要点

    • 通过list_head进行目标结点定位( position(i) )
    • 通过list_entry将list_head指针转换为目标结点指针
    • 通过list_for_each 实现int find(const T&e)函数
    • 遍历函数中的next()和pre()需要考虑跳过头结点

    5、编程实验：基于Linux内核链表的双向循环链表

    DualCircleList.h

    1. #ifndef DUALCIRCLELIST_H
    2. #define DUALCIRCLELIST_H
    3.  
    4. #include "LinuxList.h"
    5. #include "DualLinkList.h"
    6.  
    7.  
    8. namespace DTLib
    9. {
    10.  
    11. template < typename T >
    12. class DualCircleList : public DualLinkList<T>
    13. {
    14. protected:
    15.     struct Node : public Object                                     // 结点类型
    16.     {
    17.         list_head head;                                             // Linux内核链表结点的结构体成员
    18.         T value;                                                    // 数据域
    19.     };
    20.  
    21.     list_head m_header;                                             // 头结点
    22.     list_head* m_current;                                           // 游标 - 用于遍历
    23.  
    24. /**********************************************************************
    25. * Function:        position()
    26. * Description:      移动i次，返回第i-1个结点的地址
    27. * Input:            i                   数组类地址
    28. *                   m_header            头结点地址
    29. * Output:           
    30. * Return:           Node                返回第i-1个结点的地址
    31. * Others:           O(n)
    32. * Modify   Date     Version    Author      Modification
    33. * ------------------------------------------------------------
    34. *       2022/03/18    1.0                         Create        
    35. **********************************************************************/
    36.     list_head* position(int i) const
    37.     {
    38.         list_head* ret = const_cast<list_head*>(&m_header);         // 头结点地址 - 强制类型转换
    39.  
    40.         for(int p=0; p<i; p++)                                      // 移动i次游标
    41.         {
    42.             ret = ret->next;
    43.         }
    44.  
    45.         return ret;
    46.     }
    47. /**********************************************************************
    48. * Function:        mod()
    49. * Description:      取余
    50. * Input:            i                   数组类地址
    51. *                   m_header            头结点地址
    52. * Output:           
    53. * Return:           Node                返回第i-1个结点的地址
    54. * Others:           O(n)
    55. * Modify   Date     Version    Author      Modification
    56. * ------------------------------------------------------------
    57. *       2022/03/18    1.0                         Create        
    58. **********************************************************************/
    59.     int mod(int i) const
    60.     {
    61.         return (this->m_length == 0) ? 0 : (i % this->m_length);
    62.     }
    63.  
    64. public:
    65. /**********************************************************************
    66. * Function:        DualCircleList()
    67. * Description:      构造函数 - 初始化参数
    68. * Input:            
    69. * Output:           
    70. * Return:           
    71. * Others:           
    72. * Modify   Date     Version    Author      Modification
    73. * ------------------------------------------------------------
    74. *       2022/04/12    1.0                         Create        
    75. **********************************************************************/
    76.     DualCircleList()
    77.     {
    78.         this->m_length = 0;
    79.         this->m_step = 1;
    80.  
    81.         m_current = NULL;
    82.  
    83.         INIT_LIST_HEAD(&m_header);                                  // Linux链表头结点初始化
    84.     }
    85.  
    86. /**********************************************************************
    87. * Function:        insert()
    88. * Description:      插入新结点(函数重载)
    89. * Input:            i                   在位置i插入新结点(默认插在最后)
    90. *                   e                   带插入结点的数据(value)
    91. * Output:           
    92. * Return:           bool                判断插入结点位置是否合法
    93. * Others:           异常                申请内存是否成功
    94. * Modify   Date     Version    Author      Modification
    95. * ------------------------------------------------------------
    96. *       2022/03/18    1.0                         Create        
    97. **********************************************************************/
    98.     bool insert(const T& e)
    99.     {
    100.         return insert(this->m_length, e);
    101.     }
    102.  
    103.     bool insert(int i, const T& e)
    104.     {
    105.         bool ret = true;
    106.         Node* node = new Node();
    107.  
    108.         i = i % (this->m_length + 1);                               // 取余
    109.  
    110.         if( node != NULL )
    111.         {
    112.             node->value = e;
    113.  
    114.             list_add_tail(&node->head, position(i)->next);          
    115.  
    116.             this->m_length++;
    117.         }
    118.         else
    119.         {
    120.             THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");
    121.         }
    122.  
    123.         return ret;
    124.     }
    125.  
    126. /**********************************************************************
    127. * Function:        remove()
    128. * Description:      删除结点
    129. * Input:            i                   在位置i删除结点 
    130. * Output:           
    131. * Return:           bool                判断删除结点位置是否合法
    132. * Others:           O(n)
    133. * Modify   Date     Version    Author      Modification
    134. * ------------------------------------------------------------
    135. *       2022/03/18    1.0                         Create        
    136. **********************************************************************/
    137.     bool remove(int i)
    138.     {
    139.         bool ret = true;
    140.  
    141.         i = mod(i);
    142.  
    143.         ret = ((0 <= i) && (i < this->m_length));
    144.  
    145.         if( ret )
    146.         {
    147.             list_head* toDel = position(i)->next;
    148.  
    149.             if( m_current == toDel )
    150.             {
    151.                 m_current = toDel->next;
    152.             }
    153.  
    154.             list_del(toDel);
    155.  
    156.             this->m_length--;
    157.  
    158.             delete list_entry(toDel, Node, head);
    159.         }
    160.  
    161.         return ret;
    162.     }
    163.  
    164. /**********************************************************************
    165. * Function:        set()
    166. * Description:      修改第i个结点的值
    167. * Input:            i                   待修改结点的位置
    168. * Output:           
    169. * Return:           bool                判断修改结点位置是否合法
    170. * Others:           O(n)
    171. * Modify   Date     Version    Author      Modification
    172. * ------------------------------------------------------------
    173. *       2022/03/18    1.0                         Create        
    174. **********************************************************************/
    175.     bool set(int i, const T& e)
    176.     {
    177.         bool ret = true;
    178.  
    179.         i = mod(i);
    180.  
    181.         ret = ((0 <= i) && (i < this->m_length));
    182.  
    183.         if( ret )
    184.         {
    185.             list_entry(position(i)->next, Node, head)->value = e;
    186.         }
    187.  
    188.         return ret;
    189.     }
    190.  
    191. /**********************************************************************
    192. * Function:        get()
    193. * Description:      获取第i个结点的值(函数重载)
    194. * Input:            i                   待获取结点的位置
    195. * Output:           
    196. * Return:           bool                判断获取结点位置是否合法
    197. * Others:           O(n)
    198. * Modify   Date     Version    Author      Modification
    199. * ------------------------------------------------------------
    200. *       2022/03/18    1.0                         Create        
    201. **********************************************************************/
    202.     T get(int i) const
    203.     {
    204.         T ret;
    205.  
    206.         if( get(i, ret) )
    207.         {
    208.             return ret;
    209.         }
    210.         else
    211.         {
    212.             THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element ...");
    213.         }
    214.  
    215.         return ret;
    216.     }
    217.  
    218.     bool get(int i, T& e) const
    219.     {
    220.         bool ret = true;
    221.  
    222.         i = mod(i);
    223.  
    224.         ret = ((0 <= i) && (i < this->m_length));
    225.  
    226.         if( ret )
    227.         {
    228.             e = list_entry(position(i)->next, Node, head)->value;
    229.         }
    230.  
    231.         return ret;
    232.     }
    233.  
    234. /**********************************************************************
    235. * Function:        find()
    236. * Description:      查找指定元素的位置
    237. * Input:            e                   待查找结点的值(value)
    238. * Output:           
    239. * Return:           int                 返回结点的位置
    240. * Others:           O(n)
    241. * Modify   Date     Version    Author      Modification
    242. * ------------------------------------------------------------
    243. *       2022/03/18    1.0                         Create        
    244. **********************************************************************/
    245.     int find(const T& e) const
    246.     {
    247.         int ret = -1;
    248.         int i = 0;
    249.         list_head* slider = NULL;
    250.  
    251.         list_for_each(slider, &m_header)
    252.         {
    253.             if( list_entry(slider, Node, head)->value == e )
    254.             {
    255.                 ret = i;
    256.                 break;
    257.             }
    258.  
    259.             i++;
    260.         }
    261.  
    262.         return ret;
    263.     }
    264.  
    265. /**********************************************************************
    266. * Function:        length()
    267. * Description:      当前线性表的长度
    268. * Input:            
    269. * Output:           
    270. * Return:           int                 当前线性表的长度
    271. * Others:           O(1)
    272. * Modify   Date     Version    Author      Modification
    273. * ------------------------------------------------------------
    274. *       2022/03/18    1.0                         Create        
    275. **********************************************************************/
    276.     int length() const
    277.     {
    278.         return this->m_length;
    279.     }
    280.  
    281. /**********************************************************************
    282. * Function:        clear()
    283. * Description:      清空线性表
    284. * Input:            
    285. * Output:           
    286. * Return:           
    287. * Others:           O(n)
    288. * Modify   Date     Version    Author      Modification
    289. * ------------------------------------------------------------
    290. *       2022/03/18    1.0                         Create        
    291. **********************************************************************/
    292.     void clear()
    293.     {
    294.         while( this->m_length > 0 )
    295.         {
    296.             remove(0);
    297.         }
    298.     }
    299.  
    300. /*
    301.     遍历所有元素  推荐使用方法
    302.         移动到0号元素   判断是否到尾部  移动到下一个结点
    303.     for (list.move(0); !list.end();list.next())
    304.     {
    305.         cout << list.current() << endl;
    306.     }
    307. */
    308. /**********************************************************************
    309. * Function:        move()
    310. * Description:      将游标定位到目标位置(i)
    311. * Input:            i                   移动到第i个元素
    312. *                   step                步进默认为 1
    313. * Output:           
    314. * Return:           bool                判断i位置是否合法
    315. * Others:           
    316. * Modify   Date     Version    Author      Modification
    317. * ------------------------------------------------------------
    318. *       2022/03/18    1.0                         Create        
    319. **********************************************************************/
    320.     bool move(int i, int step = 1)
    321.     {
    322.         bool ret = (step > 0);
    323.  
    324.         i = mod(i);
    325.  
    326.         ret = ret && ((0 <= i) && (i < this->m_length));
    327.  
    328.         if( ret )
    329.         {
    330.             m_current = position(i)->next;
    331.  
    332.             this->m_step = step;
    333.         }
    334.  
    335.         return ret;
    336.     }
    337.  
    338. /**********************************************************************
    339. * Function:        end()
    340. * Description:      游标是否到达尾部
    341. * Input:            
    342. * Output:           
    343. * Return:           bool                游标是否到达尾部
    344. * Others:           
    345. * Modify   Date     Version    Author      Modification
    346. * ------------------------------------------------------------
    347. *       2022/03/18    1.0                         Create        
    348. **********************************************************************/
    349.     bool end()
    350.     {
    351.         return (m_current == NULL) || (this->m_length == 0);
    352.     }
    353.  
    354. /**********************************************************************
    355. * Function:        current()
    356. * Description:      获取游标所指向的数据元素
    357. * Input:            
    358. * Output:           
    359. * Return:           T                   游标所指向的数据元素
    360. * Others:           异常                游标已到尾部，无法获取到值
    361. * Modify   Date     Version    Author      Modification
    362. * ------------------------------------------------------------
    363. *       2022/03/18    1.0                         Create        
    364. **********************************************************************/
    365.     T current()
    366.     {
    367.         if( !end() )
    368.         {
    369.             return list_entry(m_current, Node, head)->value;
    370.         }
    371.         else
    372.         {
    373.             THROW_EXCEPTION(InvalidOperationException, "No value at current position ...");
    374.         }
    375.     }
    376.  
    377. /**********************************************************************
    378. * Function:        next()
    379. * Description:      移动游标 m_step次
    380. * Input:            
    381. * Output:           
    382. * Return:           bool                是否成功移动游标 m_step次
    383. * Others:           
    384. * Modify   Date     Version    Author      Modification
    385. * ------------------------------------------------------------
    386. *       2022/03/18    1.0                         Create        
    387. **********************************************************************/
    388.     bool next()
    389.     {
    390.         int i = 0;
    391.  
    392.         while( (i < this->m_step) && !end() )
    393.         {
    394.             if( m_current != &m_header )
    395.             {
    396.                 m_current = m_current->next;
    397.                 i++;
    398.             }
    399.             else
    400.             {
    401.                 m_current = m_current->next;
    402.             }
    403.         }
    404.  
    405.         if( m_current == &m_header )
    406.         {
    407.             m_current = m_current->next;
    408.         }
    409.  
    410.         return (i == this->m_step);
    411.     }
    412.  
    413. /**********************************************************************
    414. * Function:        pre()
    415. * Description:      向前移动游标 m_step次
    416. * Input:            
    417. * Output:           
    418. * Return:           bool                是否成功移动游标 m_step次
    419. * Others:           
    420. * Modify   Date     Version    Author      Modification
    421. * ------------------------------------------------------------
    422. *       2022/03/19    1.0                         Create        
    423. **********************************************************************/
    424.     bool pre()
    425.     {
    426.         int i = 0;
    427.  
    428.         while( (i < this->m_step) && !end() )
    429.         {
    430.             if( m_current != &m_header )
    431.             {
    432.                 m_current = m_current->prev;
    433.                 i++;
    434.             }
    435.             else
    436.             {
    437.                 m_current = m_current->prev;
    438.             }
    439.         }
    440.  
    441.         if( m_current == &m_header )
    442.         {
    443.             m_current = m_current->prev;
    444.         }
    445.  
    446.         return (i == this->m_step);
    447.     }
    448.  
    449. /**********************************************************************
    450. * Function:        ~DualLinkList()
    451. * Description:      析构函数  -  清空线性表
    452. * Input:            
    453. * Output:           
    454. * Return:           
    455. * Others:           O(n)
    456. * Modify   Date     Version    Author      Modification
    457. * ------------------------------------------------------------
    458. *       2022/03/19    1.0                         Create        
    459. **********************************************************************/
    460.     ~DualCircleList()
    461.     {
    462.         clear();
    463.     }
    464.  
    465. };
    466.  
    467. }
    468.  
    469. #endif // DUALCIRCLELIST_H

    6、小结

    • Linux内核链表是带头结点的双向循环链表
    • DualCircleList使用Linux内核链表进行内部实现
    • DualCircleList在循环遍历时需要跳过头结点
    • 将list_head指针转换为目标结点指针时，使用list_entry宏

    7、思考题

    下面代码中的pn1和pn2是否相等？为什么？

  • 相关阅读:
    python相关岗位面试题总结（五）（持续更新）
    GBase XDM API遍历记录集
    [OtterCTF 2018] 电子取证
    Qt Designer基础控件介绍
    今天告诉你界面控件DevExpress WinForms为何弃用经典视觉样式
    CCF CSP认证 历年题目自练Day37
    【Spring云原生系列】SpringBoot+Spring Cloud Stream：消息驱动架构（MDA）解析，实现异步处理与解耦合
    一篇带你搞定⭐《生产环境JVM日志配置》⭐
    HashMap -- 调研
    2022杭电多校第七场题解
  • 原文地址：https://blog.csdn.net/qq_38426928/article/details/125464961