• 数据结构实战开发教程（四）线性表的链式存储结构、单链表的具体实现、单链表的遍历与优化、典型问题分析（Bugfix）

    二十一、线性表的链式存储结构

    1、线性表的链式存储结构

    顺序存储结构线性表的最大问题是：插入和删除需要移动大量的元素！如何解决？

            

    2、链式存储的定义

    为了表示每个数据元素与其直接后继元素之间的逻辑关系；

    数据元素除了存储本身的信息外，还需要存储其直接后继的信息。

            

    3、链式存储逻辑结构

    • 基于链式存储结构的线性表中，每个结点都包含数据域和指针域
      • 数据域：存储数据元素本身
      • 指针域：存储相邻结点的地址

            

    4、专业术语的统一

    • 顺序表
      • 基于顺序存储结构的线性表
    • 链表
      • 基于链式存储机构的线性表
        • 单链表：每个结点只包含直接后继的地址信息
        • 循环链表：单链表中的最后一个结点的直接后继为第一个结点
        • 双向链表：单链表中的结点包含直接前驱和后继的地址信息

    5、链表中的基本概念

    • 头结点
      • 链表中的辅助结点，包含指向第一个数据元素的指针
    • 数据结点
      • 链表中代表数据元素的结点，表现形式为：（数据元素，地址）
    • 尾结点
      • 链表中的最后一个数据结点，包含的地址信息为空

    6、单链表中的结点定义

            

    7、单链表中的内部结构

            

            头结点在单链表中的意义是：辅助数据元素的定位，方便插入和删除操作；因此，头结点不存储实际的数据元素

    8、在目标位置处插入数据元素

            1. 从头结点开始，通过current指针定位到目标位置

            2. 从堆空间申请新的Node结点

            3. 执行操作：

            

    9、在目标位置处删除数据元素             

            1. 从头结点开始，通过current指针定位到目标位置

            2. 使用toDel指针指向需要删除的结点

            3. 执行操作：

            

            

    10、编程实验：图解插入与删除

    11、小结

    • 链表中的数据元素在物理内存中无相邻关系
    • 链表中的结点都包含数据域和指针域
    • 头结点用于辅助数据元素的定位，方便插入和删除操作
    • 插入和删除操作需要保证链表的完整性

    二十二、单链表的具体实现

    1、课程目标

    完成链式存储结构线性表的实现

    2、LinkList设计要点

    • 类模板，通过头结点访问后继结点
    • 定义内部结点类型Node，用于描述数据域和指针域
    • 实现线性表的关键操作（增，删，查，等）

    3、LinkList的定义

            

    4、编程实验：链表的实现

    LinkList.h

    5、问题

    头结点是否存在隐患？实现代码是否需要优化？

    6、头结点的隐患

    7、代码优化

    insert , remove , get , set 等操作都涉及元素定位。

    8、编程实验：链表的优化

    LinkList.h

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

    9、小结

    • 通过类模板实现链表，包含头结点成员和长度成员
    • 定义结点类型，并通过堆中的结点对象构成链式存储
    • 为了避免构造错误的隐患，头结点类型需要重定义（内存布局必须一致，都要继承object）
    • 代码优化是编码完成后必不可少的环节

    二十三、顺序表和单链表的对比分析

    1、问题

    如何判断某个数据元素是否存在于线性表中？

    2、遗失的操作 - find

    • 可以为线性表（List）增加一个查找操作
    • int find(const T& e) const;
      • 参数：
        • 待查找的数据元素
      • 返回值：
        • >= 0：数据元素在线性表中第一次出现的位置
        • -1：数据元素不存在

    3、数据元素查找示例

            

    4、编程实验：查找操作

            List.h

    ① 实际开发时，建议每个自定义类都继承object父类，避免编译错误。

    ② find函数需要比对两个元素是否相同，当比对元素为类时，需要重载==和!=操作符。

    5、时间复杂度对比分析

            

    6、有趣的问题

    顺序表的整体时间复杂度比单链表要低，

    那么单链表还有使用价值吗？

    7、效率的深度分析

    • 实际工程开发中，时间复杂度只是效率的一个参考指标
      • 对于内置基础类型，顺序表和单链表的效率不相上下
      • 对于自定义类类型，顺序表在效率上低于单链表
    • 插入和删除
      • 顺序表：涉及大量数据对象的复制操作
      • 单链表：只涉及指针操作，效率与数据对象无关
    • 数据访问
      • 顺序表：随机访问，可直接定位数据对象
      • 单链表：顺序访问，必须从头访问数据对象，无法直接定位

    8、工程开发中的选择

    • 顺序表
      • 数据元素的类型相对简单，不涉及深拷贝
      • 数据元素相对稳定，访问操作远多于插入和删除操作
    • 单链表
      • 数据元素的类型相对复杂，复制操作相对耗时
      • 数据元素不稳定，需要经常插入和删除，访问操作较少

    9、小结

    • 线性表中元素的查找依赖于相等比较操作符（ == ）
    • 顺序表适用于访问需求量较大的场合（随机访问）
    • 单链表适用于数据元素频繁插入删除的场合（顺序访问）
    • 当数据类型相对简单时，顺序表和单链表的效率不相上下

    二十四、单链表的遍历与优化

    1、问题

    如何遍历单链表中的每一个数据元素？

    2、当前单链表的遍历方法

            

    • O(n)    O(n^2)
    • 遗憾的事实
      • 不能以线性的时间复杂度完成单链表的遍历
    • 新的需求
      • 为单链表提供新的方法，在线性时间内完成遍历

    3、设计思路（游标）

    • 在单链表的内部定义一个游标(Node* m_current)
    • 遍历开始前将游标指向位置为0的数据元素
    • 获取游标指向的数据元素
    • 通过结点中的next 指针移动游标

    4、设计思路（游标）

    提供一组遍历相关的函数，以线性的时间复杂度遍历链表。

            

    5、遍历函数原型设计

    • bool move(int i, int step = 1);  目标位置  每次移动几个结点
    • bool end();
    • T current();
    • bool next();

    6、编程实验：单链表的遍历

    LinkList.h

    7、单链表内部的一次封装

    8、编程实验：内部的封装

    LinkList.h

    9、问题

    封装create 和destroy 函数的意义是什么?

    封装结点的申请和删除操作更有利于增强扩展性。

    10、小结

    • 单链表的遍历需要在线性时间内完成
    • 在单链表内部定义游标变量，通过游标变量提高效率
    • 遍历相关的成员函数是相互依赖，相互配合的关系
    • 封装结点的申请和删除操作更有利于增强扩展性

    二十五、静态单链表的实现

    1、讨论中。。。

            

    2、单链表的一个缺陷

    • 触发条件
      • 长时间使用单链表对象频繁增加和删除数据元素
    • 可能的结果
      • 堆空间产生大量的内存碎片，导致系统运行缓慢

    3、新的线性表

    • 设计思路：
      • 在“单链表”的内部增加一片预留的空间，所有的Node对象都在这片空间中动态创建和动态销毁。

            

    4、静态单链表的继承层次结构

    5、静态单链表的实现思路

    • 通过模板定义静态单链表类(StaticLinkList)
    • 在类中定义固定大小的空间(unsigned char [])
    • 重写create和destroy函数，改变内存的分配和归还方式
    • 在Node类中重载operator new，用于在指定内存上创建对象

    6、编程实验：静态单链表的实现

    StaticLinkList.h

    1. #ifndef STATICLINKLIST_H_
    2. #define STATICLINKLIST_H_
    3. /*******************************************************************************
    4.  *                              Include _Files                                  *
    5.  *******************************************************************************/
    6. #include "LinkList.h"
    7. /*******************************************************************************
    8.  *                             Type Definition                                 *
    9.  *******************************************************************************/
    10. namespace DTLib
    11. {
    12.  
    13. template< typename T, int N >
    14. class StaticLinkList : public LinkList<T>
    15. {
    16. protected:
    17.     typedef typename LinkList<T>::Node Node;                    // 使用typename的原因：编译器无法辨识标识符究竟是什么（是一个类型还是一个成员名称(静态数据成员或者静态函数)）
    18.                                                                 
    19.     struct SNode : public Node                                  // 结点的定义
    20.     {
    21.         void* operator new(unsigned int size, void* loc)        // 重载new操作符 
    22.         {
    23.             (void)size;                                         // 消除 size没有使用的警告
    24.             return loc;
    25.         }
    26.         /*
    27.             placement new 是重载operator new 的一个标准、全局的版本，它不能够被自定义的版本代替
    28.             placement new的执行忽略了size_t参数，只返还第二个参数。其结果是允许用户把一个对象放到一个特定的地方，达到调用构造函数的效果。
    29.             括 号里的参数ptr是一个指针，它指向一个内存缓冲器，placement new将在这个缓冲器上分配一个对象。Placement new的返回值是这 个被构造对象的地址(比如括号中的传递参数)。
    30.             placement new主要适用于：在对时间要求非常高的应用程序中，因为这些程序分配的时间是确定 的；长时间运行而不被打断的程序；以及执行一个垃圾收集器 (garbage collector)。
    31.         */
    32.     };
    33.  
    34.     unsigned char m_space[sizeof(SNode) * N];                   // N个空间单元
    35.     int m_used[N];                                              // 标记空间单元使用情况
    36.  
    37. /**********************************************************************
    38. * Function:        create()
    39. * Description:      在指定内存中创建新结点
    40. * Input:            
    41. * Output:           
    42. * Return:           Node                返回新结点的地址
    43. * Others:           
    44. * Modify   Date     Version    Author      Modification
    45. * ------------------------------------------------------------
    46. *       2022/03/18    1.0                         Create        
    47. **********************************************************************/
    48.     Node* create()
    49.     {
    50.         SNode* ret = NULL;
    51.  
    52.         for(int i=0; i<N; i++)                                  // 遍历各个空间
    53.         {
    54.             if( !m_used[i] )                                    // 如果没有被使用
    55.             {
    56.                 ret = reinterpret_cast<SNode*>(m_space) + i;    // 获取到对应的内存单元
    57.                 ret = new(ret)SNode() ;                         // 调用SNode类的构造函数
    58.                 m_used[i] = 1;                                  // 标记当前的内存单元已使用
    59.                 break;
    60.             }
    61.         }
    62.  
    63.         return ret;
    64.     }
    65.  
    66. /**********************************************************************
    67. * Function:        destroy()
    68. * Description:      在指定内存中删除结点
    69. * Input:            pn                  欲删除结点的地址
    70. * Output:           
    71. * Return:           
    72. * Others:           
    73. * Modify   Date     Version    Author      Modification
    74. * ------------------------------------------------------------
    75. *       2022/03/18    1.0                         Create        
    76. **********************************************************************/
    77.     void destroy(Node* pn)
    78.     {
    79.         SNode* space = reinterpret_cast<SNode*>(m_space);
    80.         SNode* psn = dynamic_cast<SNode*>(pn);
    81.  
    82.         for(int i=0; i<N; i++)
    83.         {
    84.             if( psn == (space + i) )
    85.             {
    86.                 m_used[i] = 0;                                  // 该空间单元使用情况为 可用
    87.                 psn->~SNode();                                  // 调用析构函数，这里需要使用的是子类的析构函数，故需要对pn进行一个强制类型转换成子类对象
    88.                 break;
    89.             }
    90.         }
    91.     }
    92. public:
    93.     // 构造函数
    94.     StaticLinkList()
    95.     {
    96.         for(int i=0; i<N; i++)
    97.         {
    98.             m_used[i] = 0;
    99.         }
    100.     }
    101.  
    102.     // 获取空间单元个数
    103.     int capacity()
    104.     {
    105.         return N;
    106.     }
    107.  
    108.     // 析构函数
    109.     ~StaticLinkList()
    110.     {
    111.         this->m_header.next = NULL;                             // 头结点标记为 空
    112.     }
    113. };
    114.  
    115. }
    116.  
    117. #endif // STATICLINKLIST_H_

    7、Q&A

    LinkList中封装create和destroy函数的意义是什么？

    为静态单链表( StaticLinkList )的实现做准备。

    StaticLinkList 与 LinkList的不同仅在于链表结点内存分配上的不同；

    因此，将仅有的不同封装于父类和子类的虚函数中。

    8、小结

    • 顺序表与单链表相结合后衍生出静态单链表
    • 静态单链表是LinkList的子类，拥有单链表的所有操作
    • 静态单链表在预留的空间中创建结点对象
    • 静态单链表适合于频繁增删数据元素的场合（最大元素个数固定）

    二十六、典型问题分析（Bugfix）

    1、ISSUE 1

    • 创建异常对象时的空指针问题

    • 需要判断_message是否为空(strdup默认入参不为空)

    2、ISSUE2

    • LinkList 中的数据元素删除

    • List.remove在释放类内存时，析构函数抛出异常后，链表依然长度为3。
      • 为了防止元素为类时，析构函数抛出异常，无法保证链表的安全性。
        • 在释放内存之前，即调用析构函数之前，调整链表长度。

    3、ISSUE 3

    • LinkList 中遍历操作与删除操作的混合使用

    • 当删除某个结点之前，需判断游标是否也指向该结点。若是，则将游标指向下一个结点。

    4、ISSUE 4

    • StaticLinkList中数据元素删除时的效率问题

    5、ISSUE 5

    • StaticLinkList是否需要提供析构函数？

    • 问题描述：StaticLinkList继承于LinkList，在未定义析构函数时，会依次调用 子类析构函数、父类析构函数，在父类析构函数中会调用clear函数，

    clear函数中调用了destroy函数，destroy函数调用了delete函数释放内存，而StaticLinkList使用的不是堆空间，所以会导致问题。

    • 解决方案：在StaticLinkList创建析构函数直接调用父类的clear函数，此时由于构造函数和析构函数，不支持多态，所以会调用子类中的destroy函数。

    6、ISSUE 6

    • DTLib是否有必要增加多维数组类？
      • 多维数组的本质：数组的数组！

    7、实践经验

    是软件就有bug，因此需要不停的迭代升级，解决问题。库是一种特殊的软件产品，也会存在各种bug，也需要迭代升级，解决问题。

  • 相关阅读:
    Blazor技术开发了一个访客管理系统
    java：枚举类
    【无标题】
    css点击文字（非按钮) 能自动改变颜色。
    通过融合UGV的地图信息和IMU的惯性测量数据，实现对车辆精确位置和运动状态的估计和跟踪研究（Matlab代码实现）
    Linux 下 chmod 777 修改权限
    使用 PyTorch Edge Delegate 加速移动设备端的 PyTorch 模型
    eBPF学习笔记（一）—— eBPF介绍&内核编译
    通信原理_2 确定信号分析
    [Linux入门]---Linux项目自动化构建工具-make/Makefile
  • 原文地址：https://blog.csdn.net/qq_38426928/article/details/125464856