• 数据结构实战开发教程（三）线性表的本质和操作、顺序存储结构的抽象实现、顺序存储线性表的分析、数组类的创建

    十四、线性表的本质和操作

    1、生活中的智慧

    幼儿园老师总会让小朋友以同样的排队秩序出行。

    2、线性表(List)的表现形式

    • 零个或多个数据元素组成的集合
    • 数据元素在位置上是有序排列的
    • 数据元素的个数是有限的
    • 数据元素的类型必须相同

    3、线性表(List)的抽象定义

            

    4、线性表(List)的性质

            

    5、思考题

    • 下面的关系中可以用线性表描述的是
      • 班级中同学的友谊关系 (X一对多)
      • 公司中的上下级关系 (X一对多)
      • 冬天图书馆用物品排队占座 (X数据类型不同)

            

    6、问题

            线性表只是一个单纯的概念吗？如何在程序中描述和使用一个线性表？

    7、线性表的一些常用操作

    • 将元素插入线性表
    • 将元素从线性表中删除
    • 获取目标位置处元素的值
    • 设置目标位置处元素的值
    • 获取线性表的长度
    • 清空线性表

    8、线性表在程序中表现为一种特殊的数据类型

            

    9、编程实验：线性表抽象类的创建

    List.h

    1. #ifndef LIST_H_
    2. #define LIST_H_
    3. /*******************************************************************************
    4.  *                              Include Files                                  *
    5.  *******************************************************************************/
    6. #include "Object.h"
    7. /*******************************************************************************
    8.  *                             Type Definition                                 *
    9.  *******************************************************************************/
    10. namespace DTLib
    11. {
    12.  
    13. template < typename T >
    14. class List : public Object
    15. {
    16. protected:
    17.     List(const List<T>&);                           // 拷贝构造函数             对于容器类型的类，可以考虑禁用拷贝构造和赋值操作。
    18.     List<T>& operator= (const List<T>&);            // 赋值操作符重载函数        对于容器类型的类，可以考虑禁用拷贝构造和赋值操作。
    19. public:
    20.     List() { }                                      // 构造函数
    21.     virtual bool insert(const T& e) = 0;            // 在线性表尾部插入e
    22.     virtual bool insert(int i, const T& e) = 0;     // 在i处插入e
    23.     virtual bool remove(int i) = 0;                 // 删除第i个元素
    24.     virtual bool set(int i, const T& e) = 0;        // 设置第i个元素为e
    25.     virtual bool get(int i, T& e) const = 0;        // 获取第i个元素为e
    26.     virtual int find(const T& e) const = 0;         // 查找指定的元素
    27.     virtual int length() const = 0;                 // 返回当前有效值的数量
    28.     virtual void clear() = 0;                       // 清空链表
    29.  
    30.     List<T>& self()
    31.     {
    32.         return *this;
    33.     }
    34. };
    35.  
    36. }
    37.  
    38.  
    39. #endif // LIST_H_

    10、小结

    • 线性表是数据元素的有序并且有限的集合
    • 线性表中的数据元素必须是类型相同的
    • 线性表可用于描述排队关系的问题
    • 线性表在程序中表现为一种特殊的数据类型
    • 线性表在C++中表现为一个抽象类

    十五、线性表的顺序存储结构

    1、顺序存储的定义

    线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表中的数据元素。

            

    2、设计思路

    • 可以用一维数组来实现顺序存储结构
      • 存储空间：T*m_array;
      • 当前长度：int m_length;

            

    3、顺序存储结构的元素获取操作

    • 判断目标位置是否合法
    • 将目标位置作为数组下标获取元素

            

    4、编程实验：图解元素获取

            通过数组下标获取元素

     

    5、顺序存储结构的元素插入操作

            1. 判断目标位置是否合法

            2. 将目标位置之后的所有元素后移一个位置

            3. 将新元素插入目标位置

            4. 线性表长度加1

    6、顺序存储结构的元素插入示例

            

    7、编程实验：图解元素插入

            线性表长度+1 ===> 会不会越界；

            插入的位置是否合理(不能插入的位置前后都没数据)

    8、顺序存储结构的元素删除操作

    1. 判断目标位置是否合法

    2. 将目标位置后的所有元素前移一个位置

    3. 线生表长度减1

    9、顺序存储结构的元素删除示例

            

    10、编程实验：图解元素删除

            删除的位置是否合理(不能删除的位置没数据)

     

    11、实战预告

    To be continued …

    十六、顺序存储结构的抽象实现

    1、课程目标

    完成顺序存储结构线性表的抽象实现

    2、SeqList设计要点

    • 抽象类模板，存储空间的位置和大小由子类完成
    • 实现顺序存储结构线性表的关键操作（增，删，查，等）
    • 提供数组操作符，方便快速获取元素

            

    3、编程实验：顺序存储线性表

    SeqList.h

    1. #ifndef SEQLIST_H_
    2. #define SEQLIST_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 SeqList : public List<T>
    16. {
    17. protected:
    18.     T* m_array;                                         // 数组地址
    19.     int m_length;                                       // 当前线性表长度
    20. public:
    21. /**********************************************************************
    22. * Function:        insert()
    23. * Description:      在i位置，插入e 
    24. * Input:            i                   待插入的位置
    25. *                   e                   待插入的数据
    26. * Output:           
    27. * Return:           bool                是否插入成功
    28. * Others:           O(n+5) => O(n)
    29. * Modify   Date     Version    Author      Modification
    30. * ------------------------------------------------------------
    31. *       2022/03/10    1.0                         Create        
    32. **********************************************************************/
    33.     bool insert(int i, const T& e)
    34.     {
    35.         bool ret = ((0 <= i) && (i <= m_length));       // i的合法性 (不能插入的位置前后都没数据)
    36.  
    37.         ret = ret && (m_length < capacity());           // 线性表长度未越界
    38.  
    39.         if( ret )
    40.         {
    41.             for(int p=m_length-1; p>=i; p--)            // 将目标位置之后的所有元素后移一个位置
    42.             {
    43.                 m_array[p + 1] = m_array[p];
    44.             }
    45.  
    46.             m_array[i] = e;                             // 将新数据填入目标位置
    47.  
    48.             m_length++;                                 // 线性表长度+1
    49.         }
    50.  
    51.         return ret;                            
    52.     }
    53.  
    54. /**********************************************************************
    55. * Function:        insert()
    56. * Description:      在线性表尾部，插入e 
    57. * Input:            e                   待插入的数据
    58. * Output:           
    59. * Return:           bool                是否插入成功
    60. * Others:           O(n)
    61. * Modify   Date     Version    Author      Modification
    62. * ------------------------------------------------------------
    63. *       2022/03/10    1.0                         Create        
    64. **********************************************************************/
    65.     bool insert(const T& e)         
    66.     {
    67.         return insert(m_length, e);
    68.     }
    69.  
    70. /**********************************************************************
    71. * Function:        remove()
    72. * Description:      删除i位置的元素
    73. * Input:            i                   待删除的位置
    74. * Output:           
    75. * Return:           bool                是否删除成功
    76. * Others:           O(n)
    77. * Modify   Date     Version    Author      Modification
    78. * ------------------------------------------------------------
    79. *       2022/03/10    1.0                         Create        
    80. **********************************************************************/
    81.     bool remove(int i)
    82.     {
    83.         bool ret = ((0 <= i) && (i < m_length));            // i的合法性
    84.  
    85.         if( ret )
    86.         {
    87.             for(int p=i; p<m_length-1; p++)                 // 将目标位置后的所有元素前移一个位置
    88.             {
    89.                 m_array[p] = m_array[p+1];
    90.             }
    91.  
    92.             m_length--;                                     // 线性表长度-1
    93.         }
    94.  
    95.         return ret;
    96.     }
    97. /**********************************************************************
    98. * Function:        set()
    99. * Description:      更新i位置的元素
    100. * Input:            i                   待更新的位置
    101. *                   e                   待更新的数据
    102. * Output:           
    103. * Return:           bool                是否更新成功
    104. * Others:           
    105. * Modify   Date     Version    Author      Modification
    106. * ------------------------------------------------------------
    107. *       2022/03/10    1.0                         Create        
    108. **********************************************************************/
    109.     bool set(int i, const T& e)
    110.     {
    111.         bool ret = ((0 <= i) && (i < m_length));            // i的合法性
    112.  
    113.         if( ret )
    114.         {
    115.             m_array[i] = e;                                 // 更新数据
    116.         }
    117.  
    118.         return ret;
    119.     }
    120.  
    121. /**********************************************************************
    122. * Function:        get()
    123. * Description:      获取i位置的元素
    124. * Input:            i                   待获取的位置
    125. * Output:           e                   获取的元素
    126. * Return:           bool                是否获取成功
    127. * Others:           O(n)
    128. * Modify   Date     Version    Author      Modification
    129. * ------------------------------------------------------------
    130. *       2022/03/10    1.0                         Create        
    131. **********************************************************************/
    132.     bool get(int i, T& e) const
    133.     {
    134.         bool ret = ((0 <= i) && (i < m_length));            // i的合法性
    135.  
    136.         if( ret )
    137.         {
    138.             e = m_array[i];                                 // 获取数据
    139.         }
    140.  
    141.         return ret;
    142.     }
    143.  
    144. /**********************************************************************
    145. * Function:        find()
    146. * Description:      查找指定的元素
    147. * Input:            i                   待寻找的元素
    148. * Output:           
    149. * Return:           int                 元素的位置
    150. * Others:           O(n)
    151. * Modify   Date     Version    Author      Modification
    152. * ------------------------------------------------------------
    153. *       2022/03/10    1.0                         Create        
    154. **********************************************************************/
    155.     int find(const T& e) const
    156.     {
    157.         int ret = -1;
    158.  
    159.         for(int i=0; i<m_length; i++)                       // 遍历寻找
    160.         {
    161.             if( m_array[i] == e )
    162.             {
    163.                 ret = i;
    164.                 break;
    165.             }
    166.         }
    167.  
    168.         return ret;
    169.     }
    170.  
    171. /**********************************************************************
    172. * Function:        length()
    173. * Description:      返回当前线性表的所用数量
    174. * Input:            
    175. * Output:           
    176. * Return:           int                 当前线性表的所用数量
    177. * Others:           
    178. * Modify   Date     Version    Author      Modification
    179. * ------------------------------------------------------------
    180. *       2022/03/10    1.0                         Create        
    181. **********************************************************************/
    182.     int length() const
    183.     {
    184.         return m_length;
    185.     }
    186.  
    187. /**********************************************************************
    188. * Function:        clear()
    189. * Description:      清空链表
    190. * Input:            
    191. * Output:           
    192. * Return:           
    193. * Others:           
    194. * Modify   Date     Version    Author      Modification
    195. * ------------------------------------------------------------
    196. *       2022/03/10    1.0                         Create        
    197. **********************************************************************/
    198.     void clear()
    199.     {
    200.         m_length = 0;
    201.     }
    202.  
    203. /**********************************************************************
    204. * Function:        operator[]()
    205. * Description:      []操作符重构函数
    206. * Input:            i                   待返回的元素位置
    207. * Output:           
    208. * Return:           T                   元素的值
    209. * Others:           数组访问方式
    210. * Modify   Date     Version    Author      Modification
    211. * ------------------------------------------------------------
    212. *       2022/03/10    1.0                         Create        
    213. **********************************************************************/
    214.     T& operator[] (int i)
    215.     {
    216.         if( (0 <= i) && (i < m_length) )                    // i的合法性
    217.         {
    218.             return m_array[i];
    219.         }
    220.         else
    221.         {
    222.             THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid ...");
    223.         }
    224.     }
    225. /**********************************************************************
    226. * Function:        operator[]()
    227. * Description:      []操作符重构函数（const类型的对象使用）
    228. * Input:            i                   待返回的元素位置
    229. * Output:           
    230. * Return:           T                   元素的值
    231. * Others:           该函数调用了上一个[]操作符重构函数
    232. * Modify   Date     Version    Author      Modification
    233. * ------------------------------------------------------------
    234. *       2022/03/10    1.0                         Create        
    235. **********************************************************************/
    236.     T operator[] (int i) const
    237.     {
    238.         return (const_cast<SeqList<T>&>(*this))[i];
    239.     }
    240.  
    241. /**********************************************************************
    242. * Function:        capacity()
    243. * Description:      顺序存储空间的容量
    244. * Input:            
    245. * Output:           
    246. * Return:           int                 顺序存储空间的容量
    247. * Others:           纯虚函数
    248. * Modify   Date     Version    Author      Modification
    249. * ------------------------------------------------------------
    250. *       2022/03/10    1.0                         Create        
    251. **********************************************************************/
    252.     virtual int capacity() const = 0;
    253. };
    254.  
    255.  
    256. }
    257.  
    258. #endif // SEQLIST_H_

    4、To be continued ...

    十七、StaticList 和 DynamicList

    1、课程目标

    • 完成StaticList类的具体实现
    • 完成DynamicList类的具体实现

    2、StaticList 设计要点

    • 类模板
      • 使用原生数组作为顺序存储空间
      • 使用模板参数决定数组大小

    ·

    3、编程实验：StaticList的实现

    StaticList.h

    1. #ifndef STATICLIST_H_
    2. #define STATICLIST_H_
    3. /*******************************************************************************
    4.  *                              Include _Files                                  *
    5.  *******************************************************************************/
    6. #include "SeqList.h"
    7. /*******************************************************************************
    8.  *                             Type Definition                                 *
    9.  *******************************************************************************/
    10. namespace DTLib
    11. {
    12.  
    13. template < typename T, int N >
    14. class StaticList : public SeqList<T>
    15. {
    16. protected:
    17.     T m_space[N];                       // 元素总数量
    18. public:
    19.     StaticList()                        // 构造函数 - 指定父类成员的具体值
    20.     {
    21.         this->m_array = m_space;        // 初始化元素总数量
    22.         this->m_length = 0;             // 初始化当前线性表长度
    23.     }
    24.  
    25.     int capacity() const                // 获取元素总数量
    26.     {
    27.         return N;
    28.     }
    29. };
    30.  
    31.  
    32. }
    33.  
    34. #endif // STATICLIST_H_

    4、DynamicList设计要点

    • 类模板
      • 申请连续堆空间作为顺序存储空间
      • 动态设置顺序存储空间的大小
      • 保证重置顺序存储空间时的异常安全性
    • 函数异常安全的概念
      • 不泄漏任何资源
      • 不允许破坏数据
    • 函数异常安全的基本保证
      • 如果异常被抛出
        • 对象内的任何成员仍然能保持有效状态
        • 没有数据的破坏及资源泄漏

            

    5、编程实验：DynamicList的实现

    DynamicList.h

    1. #ifndef DYNAMICLIST_H_
    2. #define DYNAMICLIST_H_
    3. /*******************************************************************************
    4.  *                              Include _Files                                  *
    5.  *******************************************************************************/
    6. #include "SeqList.h"
    7. #include "Exception.h"
    8. /*******************************************************************************
    9.  *                             Type Definition                                 *
    10.  *******************************************************************************/
    11. namespace DTLib
    12. {
    13.  
    14. template < typename T >
    15. class DynamicList : public SeqList<T>
    16. {
    17. protected:
    18.     int m_capacity;                                             // 元素总数量
    19. public:
    20. /**********************************************************************
    21. * Function:        DynamicList()
    22. * Description:     构造函数
    23. * Table Accessed: 
    24. * Table Updated:  
    25. * Input:            capacity            元素总数量
    26. * Output:           
    27. * Return:          
    28. * Others:           
    29. * Modify   Date     Version    Author      Modification
    30. * ------------------------------------------------------------
    31. *       2022/03/10    1.0                         Create        
    32. **********************************************************************/
    33.     DynamicList(int capacity)                                   // 构造函数 - 申请空间
    34.     {
    35.         this->m_array = new T[capacity];                        // 申请堆空间
    36.  
    37.         if( this->m_array != NULL )
    38.         {
    39.             this->m_length = 0;                                 // 初始化当前线性表长度
    40.             this->m_capacity = capacity;                        // 初始化元素总数量
    41.         }
    42.         else
    43.         {
    44.             THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create DynamicList object ...");
    45.         }
    46.     }
    47. /**********************************************************************
    48. * Function:        capacity()
    49. * Description:     返回元素总数量
    50. * Table Accessed: 
    51. * Table Updated:  
    52. * Input:            
    53. * Output:           
    54. * Return:           int                 返回 元素总数量
    55. * Others:           
    56. * Modify   Date     Version    Author      Modification
    57. * ------------------------------------------------------------
    58. *       2022/03/10    1.0                         Create        
    59. **********************************************************************/
    60.     int capacity() const
    61.     {
    62.         return m_capacity;
    63.     }
    64.  
    65. /**********************************************************************
    66. * Function:        resize()
    67. * Description:     重新设置元素数量
    68. * Table Accessed: 
    69. * Table Updated:  
    70. * Input:            capacity            新元素总数量
    71. * Output:           
    72. * Return:          
    73. * Others:           
    74. * Modify   Date     Version    Author      Modification
    75. * ------------------------------------------------------------
    76. *       2022/03/10    1.0                         Create        
    77. **********************************************************************/
    78.     void resize(int capacity)
    79.     {
    80.         if( capacity != m_capacity )
    81.         {
    82.             T* array = new T[capacity];                                         // 重新申请一块符合大小的堆空间
    83.  
    84.             if( array != NULL )                                                 // 成功申请
    85.             {
    86.                 int length = (this->m_length < capacity ? this->m_length : capacity); // 获取当前元素的数量
    87.  
    88.                 for(int i=0; i<length; i++)                                     // 将length个元素复制到新申请的堆空间中
    89.                 {
    90.                     array[i] = this->m_array[i];                                /* 此可能发生异常，动态链表依然可用，但是会发生内存泄漏。且无法避免。*/
    91.                 }                                                               /* T是一个泛型类型，赋值操作符可能被重载，并且重载的实现出现的异常，上层修改即可*/
    92.                 
    93.                 T* temp = this->m_array;                                        /* 此处不直接释放堆空间，防止此处抛出异常，保障动态链表异常安全性 */
    94.  
    95.                 this->m_array = array;                                          // 更新 顺序存储空间
    96.                 this->m_length = length;                                        // 更新 当前线性表长度
    97.                 this->m_capacity = capacity;                                    // 更新 返回元素总数量
    98.  
    99.                 delete[] temp;                                                  // 删除原来的堆空间
    100.             }
    101.             else
    102.             {
    103.                 THROW_EXCEPTION(NoEnoughMemoryException, "No memory to resize DynamicList object ...");
    104.             }
    105.         }
    106.     }
    107. /**********************************************************************
    108. * Function:        ~DynamicList()
    109. * Description:     析构函数
    110. * Table Accessed: 
    111. * Table Updated:  
    112. * Input:            
    113. * Output:           
    114. * Return:          
    115. * Others:           释放堆内存空间
    116. * Modify   Date     Version    Author      Modification
    117. * ------------------------------------------------------------
    118. *       2022/03/10    1.0                         Create        
    119. **********************************************************************/
    120.     ~DynamicList()
    121.     {
    122.         delete[] this->m_array;
    123.     }
    124. };
    125.  
    126.  
    127. }
    128.  
    129. #endif // DYNAMICLIST_H_

    6、问题

    是否可以将DynamicList 作为StaticList的子类实现？

    7、小结

    • StaticList 通过模板参数定义顺序存储空间
    • DynamicList 通过动态内存申请定义顺序存储空间
    • DynamicList 支持动态重置顺序存储空间的大小
    • DynamicList 中的resize()函数实现需要保证异常安全

    十八、顺序存储线性表的分析

    1、效率分析

            

    2、问题

            长度相同的两个SeqList，插入和删除操作的平均耗时是否相同？

                    要具体问题具体分析。

    3、编程实验：SeqList效率分析

    • T为int和String时，字符串的拷贝更耗时。
    • 由于数据类型的不同，赋值操作的效率和耗时不同。取决于线性表里存储的数据类型。
    • 不能单纯只看时间复杂度O，只是参考指标，不是绝对指标，要根据实际情况分析。
    • 基于顺序存储结构的线性表不适合使用类类型的对象作为数据元素存储。

    4、下面的代码正确吗？为什么？

            

            

    拷贝使得两个对象指向同一份堆空间，导致同一个堆空间被两次。

    5、分析

    对于容器类型的类，可以考虑禁用拷贝构造和赋值操作。

            

    6、编程实验：代码优化

            禁用拷贝构造和赋值操作。

    7、下面的代码正确吗？为什么？不正确

    线性表必须先插入元素，才能使用操作符[]访问元素。

    8、问题分析

            顺序存储结构线性表提供了数组操作符重载，通过重载能够快捷方便的获取目标位置处的数据元素，在具体的使用形式上类似数组，但是由于本质不同，不能代替数组使用。

    9、实战预告：数组类开发

    10、小结

    • 顺序存储线性表的插入和删除操作存在重大效率隐患(不适合使用类类型的对象作为数据元素存储)
    • 线性表作为容器类，应该避免拷贝构造和拷贝赋值
    • 顺序存储线性表可能被当成数组误用
    • 工程开发中可以考虑使用数组类代替原生数组使用

    十九、数组类的创建（上）

    1、课程目标

    • 完成Array类的具体实现
    • 完成StaticArray类的具体实现

    2、需求分析

    • 创建数组类代替原生数组的使用
      • 数组类包含长度信息
      • 数组类能够主动发现越界访问

    3、Array设计要点

    • 抽象类模板，存储空间的位置和大小由子类完成
    • 重载数组操作符，判断访问下标是否合法
    • 提供数组长度的抽象访问函数
    • 提供数组对象间的复制操作

    4、Array类的声明

            

    5、编程实验：数组抽象类实现

    Array.h

    1. #ifndef ARRAY_H_
    2. #define ARRAY_H_
    3. /*******************************************************************************
    4.  *                              Include Files                                  *
    5.  *******************************************************************************/
    6. #include "Object.h"
    7. #include "Exception.h"
    8. /*******************************************************************************
    9.  *                             Type Definition                                 *
    10.  *******************************************************************************/
    11. namespace DTLib
    12. {
    13.  
    14. template < typename T >
    15. class Array : public Object
    16. {
    17. protected:
    18.     T* m_array;
    19. public:
    20. /**********************************************************************
    21. * Function:        set()
    22. * Description:      设置数组下标为i的元素值为e
    23. * Input:            i                   下标为i
    24. *                   e                   元素值为e
    25. * Output:           
    26. * Return:           bool                返回是否成功
    27. * Others:           与原生数组差异：预防下标越界
    28. * Modify   Date     Version    Author      Modification
    29. * ------------------------------------------------------------
    30. *       2022/03/10    1.0                         Create        
    31. **********************************************************************/
    32.     virtual bool set(int i, const T& e)
    33.     {
    34.         bool ret = ((0 <= i) && (i < length()));
    35.  
    36.         if( ret )
    37.         {
    38.             m_array[i] = e;
    39.         }
    40.  
    41.         return ret;
    42.     }
    43.  
    44. /**********************************************************************
    45. * Function:        get()
    46. * Description:      获取数组下标为i的元素值
    47. * Input:            i                   下标为i
    48. *                   e                   元素值为e
    49. * Return:           bool                返回是否成功
    50. * Others:           与原生数组差异：预防下标越界
    51. * Modify   Date     Version    Author      Modification
    52. * ------------------------------------------------------------
    53. *       2022/03/10    1.0                         Create        
    54. **********************************************************************/
    55.     virtual bool get(int i, T& e) const
    56.     {
    57.         bool ret = ((0 <= i) && (i < length()));
    58.  
    59.         if( ret )
    60.         {
    61.             e = m_array[i];
    62.         }
    63.  
    64.         return ret;
    65.     }
    66.  
    67. /**********************************************************************
    68. * Function:        operator[]()
    69. * Description:      []操作符重载函数
    70. * Input:            i                   数组下标i的元素
    71. * Output:           
    72. * Return:           T                   返回元素的值
    73. * Others:           下标越界，抛出异常
    74. * Modify   Date     Version    Author      Modification
    75. * ------------------------------------------------------------
    76. *       2022/03/10    1.0                         Create        
    77. **********************************************************************/
    78.     virtual T& operator[] (int i)
    79.     {
    80.         if((0 <= i) && (i < length()))
    81.         {
    82.             return m_array[i];
    83.         }
    84.         else
    85.         {
    86.             THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid ...");
    87.         }
    88.     }
    89.  
    90. /**********************************************************************
    91. * Function:        operator[]()
    92. * Description:      []操作符重载函数(传入const)
    93. * Input:            i                   数组下标i的元素
    94. * Output:           
    95. * Return:           T                   返回元素的值
    96. * Others:           下标越界，抛出异常
    97. * Modify   Date     Version    Author      Modification
    98. * ------------------------------------------------------------
    99. *       2022/03/10    1.0                         Create        
    100. **********************************************************************/
    101.     virtual T operator[] (int i) const
    102.     {
    103.         return (const_cast<Array<T>&>(*this))[i];
    104.     }
    105.  
    106. /**********************************************************************
    107. * Function:        array()
    108. * Description:      返回数组的地址
    109. * Input:            
    110. * Output:           
    111. * Return:           T                   返回数组的地址
    112. * Others:           
    113. * Modify   Date     Version    Author      Modification
    114. * ------------------------------------------------------------
    115. *       2022/03/10    1.0                         Create        
    116. **********************************************************************/
    117.     T* array() const
    118.     {
    119.         return m_array;
    120.     }
    121.  
    122.     Array<T>& self()
    123.     {
    124.         return *this;
    125.     }
    126.  
    127.     virtual int length() const = 0;
    128. };
    129.  
    130. }
    131.  
    132. #endif // ARRAY_H_

    6、StaticArray设计要点

    • 类模板
      • 封装原生数组
      • 使用模板参数决定数组大小
      • 实现函数返回数组长度
      • 拷贝构造和赋值操作

    7、StaticArray类的声明

            

    8、编程实验：静态数组类的实现

    StaticArray.h

    1. #ifndef STATICARRAY_H_
    2. #define STATICARRAY_H_
    3. /*******************************************************************************
    4.  *                              Include Files                                  *
    5.  *******************************************************************************/
    6. #include "Array.h"
    7. /*******************************************************************************
    8.  *                             Type Definition                                 *
    9.  *******************************************************************************/
    10. namespace DTLib
    11. {
    12.  
    13. template < typename T, int N >
    14. class StaticArray : public Array<T>
    15. {
    16. protected:
    17.     T m_space[N];
    18. public:
    19.     StaticArray()                                               // 构造函数
    20.     {
    21.         this->m_array = m_space;                                // 初始化父类成员
    22.     }
    23.  
    24.     StaticArray(const StaticArray<T, N>& obj)                   // 拷贝构造函数
    25.     {
    26.         this->m_array = m_space;                                // 初始化父类成员
    27.  
    28.         for(int i=0; i<N; i++)                                  // 循环赋值
    29.         {
    30.             m_space[i] = obj.m_space[i];
    31.         }
    32.     }
    33.  
    34.     StaticArray<T, N>& operator= (const StaticArray<T, N>& obj) // 赋值构造函数
    35.     {
    36.         if( this != &obj )                                      // 不允许自赋值
    37.         {
    38.             for(int i=0; i<N; i++)                              // 循环赋值
    39.             {
    40.                 m_space[i] = obj.m_space[i];
    41.             }
    42.         }
    43.  
    44.         return *this;                                           // 返回当前类的指针，代表允许连续赋值
    45.     }
    46.  
    47.     int length() const                                          // 返回数组的成员数量
    48.     {
    49.         return N;
    50.     }
    51. };
    52.  
    53.  
    54. }
    55.  
    56. #endif // STATICARRAY_H_

    9、实战预告

    To be continued …

    二十、数组类的创建（下）

    1、课程目标

    完成DynamicArray 类的具体实现

    2、DynamicArray设计要点

    • 类模板
      • 动态确定内部数组空间的大小
      • 实现函数返回数组长度
      • 拷贝构造和赋值操作

    3、DynamicArray类的声明

            

    4、编程实验：动态数组的实现

    5、问题

    DynamicArray类中的函数实现存在重复的逻辑，如何进行代码优化？

    6、重复代码逻辑的抽象

    • init
      • 对象构造时的初始化操作
    • copy
      • 在堆空间中申请新的内存，并执行拷贝操作
    • update
      • 将指定的堆空间作为内部存储数组使用

    7、编程实验：动态数组的优化

    DynamicArray.h

    1. #ifndef DYNAMICARRAY_H_
    2. #define DYNAMICARRAY_H_
    3. /*******************************************************************************
    4.  *                              Include _Files                                  *
    5.  *******************************************************************************/
    6. #include "Array.h"
    7. #include "Exception.h"
    8. /*******************************************************************************
    9.  *                             Type Definition                                 *
    10.  *******************************************************************************/
    11. namespace DTLib
    12. {
    13.  
    14. template < typename T >
    15. class DynamicArray : public Array<T>
    16. {
    17. protected:
    18.     int m_length;
    19.  
    20. /**********************************************************************
    21. * Function:        copy()
    22. * Description:      动态调整数组大小
    23. * Input:            array               数组类地址
    24. *                   len                 原数组成员数量
    25. *                   newLen              新数组成员数量
    26. * Output:           
    27. * Return:           bool                返回数组类地址
    28. * Others:           O(n)
    29. * Modify   Date     Version    Author      Modification
    30. * ------------------------------------------------------------
    31. *       2022/03/10    1.0                         Create        
    32. **********************************************************************/
    33.     T* copy(T* array, int len, int newLen)
    34.     {
    35.         T* ret = new T[newLen];
    36.  
    37.         if( ret != NULL )
    38.         {
    39.             int size = (len < newLen) ? len : newLen;   // 取数组成员数量小的，进行数组拷贝
    40.  
    41.             for(int i=0; i<size; i++)
    42.             {
    43.                 ret[i] = array[i];
    44.             }
    45.         }
    46.  
    47.         return ret;
    48.     }
    49.  
    50. /**********************************************************************
    51. * Function:        update()
    52. * Description:      动态调整后更新
    53. * Input:            array               数组类地址
    54. *                   length              数组元素数量
    55. * Output:           
    56. * Return:           
    57. * Others:           
    58. * Modify   Date     Version    Author      Modification
    59. * ------------------------------------------------------------
    60. *       2022/03/10    1.0                         Create        
    61. **********************************************************************/
    62.     void update(T* array, int length)
    63.     {
    64.         if( array != NULL )
    65.         {
    66.             T* temp = this->m_array;                    /* 此处不直接释放堆空间，防止此处抛出异常，保障动态数组异常安全性 */
    67.  
    68.             this->m_array = array;                      // 更新数组地址
    69.             this->m_length = length;                    // 更新数组元素数量
    70.  
    71.             delete[] temp;
    72.         }
    73.         else
    74.         {
    75.             THROW_EXCEPTION(NoEnoughMemoryException, "No memory to update DynamicArray object ...");
    76.         }
    77.     }
    78.  
    79. /**********************************************************************
    80. * Function:        init()
    81. * Description:      初始化数组大小
    82. * Input:            array               数组类地址
    83. *                   length              数组元素数量
    84. * Output:           
    85. * Return:           
    86. * Others:           
    87. * Modify   Date     Version    Author      Modification
    88. * ------------------------------------------------------------
    89. *       2022/03/10    1.0                         Create        
    90. **********************************************************************/
    91.     void init(T* array, int length)
    92.     {
    93.         if( array != NULL )
    94.         {
    95.             this->m_array = array;                      // 初始化数组地址
    96.             this->m_length = length;                    // 初始化数组元素数量
    97.         }
    98.         else
    99.         {
    100.             THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create DynamicArray object ...");
    101.         }
    102.     }
    103.  
    104. public:
    105. /**********************************************************************
    106. * Function:        DynamicArray()
    107. * Description:      构造函数 - 创建数组
    108. * Input:            length              数组元素数量
    109. * Output:           
    110. * Return:           
    111. * Others:           
    112. * Modify   Date     Version    Author      Modification
    113. * ------------------------------------------------------------
    114. *       2022/03/10    1.0                         Create        
    115. **********************************************************************/
    116.     DynamicArray(int length = 0)
    117.     {
    118.         init(new T[length], length);
    119.     }
    120.  
    121. /**********************************************************************
    122. * Function:        DynamicArray()
    123. * Description:      拷贝构造函数
    124. * Input:            obj                 待拷贝的数组类
    125. * Output:           
    126. * Return:           
    127. * Others:           先创建拷贝数组类(copy)，再初始化数组地址和数组元素数量(init)
    128. * Modify   Date     Version    Author      Modification
    129. * ------------------------------------------------------------
    130. *       2022/03/10    1.0                         Create        
    131. **********************************************************************/
    132.     DynamicArray(const DynamicArray<T>& obj)
    133.     {
    134.         init(copy(obj.m_array, obj.m_length, obj.m_length), obj.m_length);
    135.     }
    136.  
    137. /**********************************************************************
    138. * Function:        operator=()
    139. * Description:      赋值构造函数
    140. * Input:            obj                 待拷贝的数组类
    141. * Output:           
    142. * Return:           
    143. * Others:           先创建拷贝数组类(copy)，再更新数组地址和数组元素数量(update)
    144. * Modify   Date     Version    Author      Modification
    145. * ------------------------------------------------------------
    146. *       2022/03/10    1.0                         Create        
    147. **********************************************************************/
    148.     DynamicArray<T>& operator= (const DynamicArray<T>& obj)
    149.     {
    150.         if( this != &obj )                                  // 禁止自赋值
    151.         {
    152.             update(copy(obj.m_array, obj.m_length, obj.m_length), obj.m_length);
    153.         }
    154.  
    155.         return *this;
    156.     }
    157.  
    158. /**********************************************************************
    159. * Function:        length()
    160. * Description:      返回数组元素数量
    161. * Input:            
    162. * Output:           
    163. * Return:           返回数组元素数量
    164. * Others:           
    165. * Modify   Date     Version    Author      Modification
    166. * ------------------------------------------------------------
    167. *       2022/03/10    1.0                         Create        
    168. **********************************************************************/
    169.     int length() const
    170.     {
    171.         return m_length;
    172.     }
    173.  
    174. /**********************************************************************
    175. * Function:        resize()
    176. * Description:      重新分配数组的元素数量
    177. * Input:            length              重新分配的数组元素数量
    178. * Output:           
    179. * Return:           
    180. * Others:           先创建拷贝数组类(copy)，再更新数组地址和数组元素数量(update)
    181. * Modify   Date     Version    Author      Modification
    182. * ------------------------------------------------------------
    183. *       2022/03/10    1.0                         Create        
    184. **********************************************************************/
    185.     virtual void resize(int length)
    186.     {
    187.         if( length != m_length )
    188.         {
    189.             update(copy(this->m_array, m_length, length), length);
    190.         }
    191.     }
    192.  
    193. /**********************************************************************
    194. * Function:        ~DynamicArray()
    195. * Description:      析构函数
    196. * Input:            
    197. * Output:           
    198. * Return:           
    199. * Others:           释放数组的堆空间
    200. * Modify   Date     Version    Author      Modification
    201. * ------------------------------------------------------------
    202. *       2022/03/10    1.0                         Create        
    203. **********************************************************************/
    204.     ~DynamicArray()
    205.     {
    206.         delete[] this->m_array;
    207.     }
    208. };
    209.  
    210.  
    211. }
    212.  
    213. #endif // DYNAMICARRAY_H_

    8、小结

    • StaticArray通过封装原生数组的方式实现数组类
    • DynamicArray动态申请堆空间，使得数组长度动态可变
    • 数组对象能够代替原生数组，并且使用上更安全
    • 代码优化是项目开发过程中不可或缺的环节

  • 相关阅读:
    [附源码]SSM计算机毕业设计8号体育用品销售及转卖系统JAVA
    pandas数据类型之Series
    Vue 源码解读（6）—— 实例方法
    爱上开源之DockerUI-如何实现Web端的Xshell终端模拟器
    Python使用turtle绘制简单图形
    使用Next.js和web3auth来创建DApps
    java计算机毕业设计高校网上报销系统源码+mysql数据库+系统+lw文档+部署
    Netty（三）- NIO三大组件之Channel
    一本通1057；简单计算器（2）
    线程是如何实现的？
  • 原文地址：https://blog.csdn.net/qq_38426928/article/details/125464524