/// @file exam_x_x_cpp.cpp/// @brief 测试动态数组模板实现#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include "DynamicArrays.h"void fnTest_CDynamicArrays(); ///< 测试动态数组//----------------------------------------------------------------------// 动态数组类测试代码//----------------------------------------------------------------------int main(int argc, char* argv[], char* envp[]){	fnTest_CDynamicArrays();		printf("hello dynamic arrays\n");	return 0;}void fnTest_CDynamicArrays(){    bool bValid = false;	CDynamicArrays
         
           DynAry; int iTmp = 0; /// 没有数据的情况 printf("\n----------\n"); printf("DynAry.isEmpty() = %d\n", DynAry.isEmpty()); DynAry.printData(); printf("DynAry.isEmpty() = %d\n", DynAry.isEmpty()); /// 有数据的情况,没有数据时, 插入一个数据 printf("\n----------\n"); DynAry.insert(0, 0x1); DynAry.addTail(0x2); DynAry.addTail(0x3); DynAry.addTail(0x4); DynAry.addTail(0x5); DynAry.addTail(0x6); DynAry.addTail(0x7); DynAry.addTail(0x8); DynAry.printData(); // 9data printf("\n----------\n"); DynAry.insert(8, 0x9); DynAry.printData(); // 10data printf("\n----------\n"); DynAry.addTail(0x10); DynAry.printData(); iTmp = DynAry.prev(DynAry[7], bValid); if (bValid) { printf("DynAry.prev(DynAry[7], bValid) = %d\n", iTmp); } iTmp = DynAry.next(DynAry[3], bValid); if (bValid) { printf("DynAry.next(DynAry[3], bValid) = %d\n", iTmp); } // nodata printf("\n----------\n"); printf("DynAry.isEmpty() = %d\n", DynAry.isEmpty()); DynAry.clear(); printf("DynAry.isEmpty() = %d\n", DynAry.isEmpty()); // re add 1data printf("\n----------\n"); DynAry.addTail(0x11); DynAry.printData(); printf("DynAry.isEmpty() = %d\n", DynAry.isEmpty());}
         
        
       
      
     
    

线性表类模板实现

/// @file DynamicArrays.h/// @brief 动态数组模板实现#ifndef DYNAMIC_ARRAYS_H_#define DYNAMIC_ARRAYS_H_#ifndef IN#define IN#endif // #ifndef IN#ifndef OUT#define OUT#endif // #ifndef OUT/**动态数组是线性表结构的一种线性表是数据结构中最常用的一种线性表特点	线性存储, 有首元素,尾元素,表长	允许有空表	首元素没有前驱,只有唯一后继	尾元素只有唯一前驱,没有后继	非首尾元素,只有唯一前驱和唯一后继		线性表抽象后的方法	初始化表	求表长	拿元素	求前驱	求后继	插入	删除	是否为空	清空表线性表基本数据	表长	数据指针*///----------------------------------------------------------------------// 动态数组类定义//----------------------------------------------------------------------template
    
     class CDynamicArrays{public:	CDynamicArrays();	virtual ~CDynamicArrays();/// 线性表类方法/**线性表抽象后的方法	初始化表 ///< 用类初始化表代替	求表长 ///< size_t getElementCount();	拿元素 ///< T& operator [](size_t nIndex);	求前驱 ///< T& prev(T&);	求后继 ///< T& next(T&);	插入 ///< bool insert(size_t nIndex, int data);	删除 ///< bool clear();	是否为空 ///< bool IsEmpty();	清空表 ///< bool clear();*/size_t getElementCount() const; ///< 求表长T& operator [](size_t nIndex); ///< 拿元素bool isEmpty(); ///< 是否为空bool clear(); ///< 清空表T& prev(IN const T& now, OUT bool& bValid) const; ///< 求前驱T& next(IN const T& now, OUT bool& bValid) const; ///< 求后继bool insert(size_t nIndex, T data); ///< 插入数据bool addTail(T data); ///< 在末尾添加void printData(); ///< 打印数据, 用于调试private:	bool findData(IN const T& now, OUT size_t& nIndexNow) const; ///< 查找一个引用的索引	bool IsIndexValid(size_t nIndex) const; ///< 索引是否有效	/// 根据现有的数据数量, 当需要换一个更大的空间时,	/// 空间的增长率是不同的	size_t getNewElementGrowUpStep() const; ///< 求新数据增长的步长	T* copyData(T* dest, const T* src, size_t nCount);private:	size_t m_nElementCounter; ///< 元素个数	size_t m_nElementCounterMax; ///< 动态数组现有空间能容纳的元素最大个数	T* m_pData; ///< 数据指针	T m_InValidData; ///< 无效数据, 用于返回[]的无效情况};//----------------------------------------------------------------------// 动态数组类实现//----------------------------------------------------------------------template
     
      CDynamicArrays
      
       ::CDynamicArrays(): m_nElementCounter(0), m_nElementCounterMax(m_nElementCounter), m_pData(NULL), m_InValidData((T)-1){    /// 时间复杂度 O(1)}template
       
        CDynamicArrays
        
         ::~CDynamicArrays(){    /// 时间复杂度 O(1)    if (NULL != m_pData)    {        delete [] m_pData;        m_pData = NULL;    }}template
         
          bool CDynamicArrays
          
           ::IsIndexValid(size_t nIndex) const{ /// 时间复杂度 O(1) bool isInValid = ((0 == getElementCount()) || (nIndex > (getElementCount() - 1)) || (NULL == m_pData)); return !isInValid;}template
           
            size_t CDynamicArrays
            
             ::getElementCount() const{ /// 时间复杂度 O(1) return m_nElementCounter;}template
             
              T& CDynamicArrays
              
               ::operator [](size_t nIndex){ /// 时间复杂度 O(1) if (!IsIndexValid(nIndex)) { m_InValidData = (T)-1; ///< 重新赋值, 防止被改写后再用 return m_InValidData; } return m_pData[nIndex];}template
               
                bool CDynamicArrays
                
                 ::isEmpty(){ /// 时间复杂度 O(1) return ((0 == getElementCount()) && (NULL == m_pData));}template
                 
                  bool CDynamicArrays
                  
                   ::clear(){ /// 时间复杂度 O(1) if (isEmpty()) { return false; } m_InValidData = (T)-1; m_nElementCounter = 0; if (NULL != m_pData) { delete []m_pData; m_pData = NULL; } return true;}template
                   
                    bool CDynamicArrays
                    
                     ::findData(IN const T& now, OUT size_t& nIndexNow) const{ /// 时间复杂度 O(n) bool bFind = false; size_t nIndex = 0; nIndexNow = 0; for (nIndex = 0; nIndex < getElementCount(); nIndex++) { if (&now == (m_pData + nIndex)) { nIndexNow = nIndex; bFind = true; break; } } return bFind;}template
                     
                      T& CDynamicArrays
                      
                       ::prev(IN const T& now, OUT bool& bValid) const{ /// 时间复杂度 O(1) bool bFind = false; size_t nIndex = 0; bValid = findData(now, nIndex); if (bValid) { bValid = IsIndexValid(nIndex - 1); return (bValid ? m_pData[nIndex - 1] : (T&)m_InValidData); } else { return (T&)m_InValidData; }}template
                       
                        T& CDynamicArrays
                        
                         ::next(IN const T& now, OUT bool& bValid) const{ /// 时间复杂度 O(1) bool bFind = false; size_t nIndex = 0; bValid = findData(now, nIndex); if (bValid) { bValid = IsIndexValid(nIndex + 1); return (bValid ? m_pData[nIndex + 1] : (T&)m_InValidData); } else { return (T&)m_InValidData; }}template
                         
                          bool CDynamicArrays
                          
                           ::insert(size_t nIndex, T data){ /// 时间复杂度 O(n) bool bOk = false; T* pData = NULL; size_t nElementCounterMax = 0; if (nIndex > getElementCount()) { return false; } do { if ((0 == getElementCount()) || (m_nElementCounterMax == getElementCount())) { /// 再插入一个数据就越界了, 需要建立新空间 nElementCounterMax += getNewElementGrowUpStep(); pData = new T[nElementCounterMax]; assert(NULL != pData); if (NULL == pData) { printf("bp2\n"); break; } /// 空间分配成功 m_nElementCounterMax = nElementCounterMax; /// 拷贝现有数据到新空间 if ((NULL != m_pData) && (0 != getElementCount())) { /// 旧空间不足的情况 m_pData = copyData(pData, m_pData, getElementCount()); } else { /// 初次分配空间的情况 m_pData = pData; } } m_nElementCounter++; bOk = true; /// 将数据向后整理挪一个元素, 空出当前元素位置 copyData(m_pData + nIndex + 1, m_pData + nIndex, getElementCount() - nIndex); /// 在现有空间中插入数据 m_pData[nIndex] = data; } while (0); return bOk;}template
                           
                            bool CDynamicArrays
                            
                             ::addTail(T data){ /// 时间复杂度 O(n) return insert(getElementCount(), data);}template
                             
                              T* CDynamicArrays
                              
                               ::copyData(T* dest, const T* src, size_t nCount){ /// 时间复杂度 O(n) size_t nIndex = 0; assert(NULL != dest); assert(NULL != src); assert(0 != nCount); /// 为了防止元素为类, 需要一个一个拷贝 if ((NULL != dest) && (NULL != src) && (0 != nCount)) { /// 考虑覆盖的问题 if (src > dest) { for (nIndex = 0; nIndex < nCount; nIndex++) { dest[nIndex] = src[nIndex]; } } else { for (nIndex = nCount - 1; nIndex >= 0; nIndex--) { dest[nIndex] = src[nIndex]; if (0 == nIndex) { break; } } } } return dest;}template
                               
                                void CDynamicArrays
                                
                                 ::printData(){ /// 时间复杂度 O(n) size_t nIndex = 0; printf("[0x%X/0x%X/0x%X]\n", getElementCount(), m_nElementCounterMax, m_InValidData); printf("[0x%X] ", m_pData); for (nIndex = 0; nIndex < getElementCount(); nIndex++) { printf("0x%X ", m_pData[nIndex]); } printf("\n");}/// 特例 : CDynamicArrays
                                 
                                  ::printData()template<>void CDynamicArrays
                                  
                                   ::printData(){ /// 时间复杂度 O(n) size_t nIndex = 0; printf("[0x%X/0x%X/0x%X]\n", getElementCount(), m_nElementCounterMax, m_InValidData); printf("[0x%X] ", m_pData); for (nIndex = 0; nIndex < getElementCount(); nIndex++) { printf("%f ", m_pData[nIndex]); } printf("\n");}/// 特例 : CDynamicArrays
                                   
                                    ::printData()template<>void CDynamicArrays
                                    
                                     ::printData(){ /// 时间复杂度 O(n) size_t nIndex = 0; printf("[0x%X/0x%X/0x%X]\n", getElementCount(), m_nElementCounterMax, m_InValidData); printf("[0x%X] ", m_pData); for (nIndex = 0; nIndex < getElementCount(); nIndex++) { printf("%f ", m_pData[nIndex]); } printf("\n");}template
                                     
                                      size_t CDynamicArrays
                                      
                                       ::getNewElementGrowUpStep() const{ /// 时间复杂度 O(1) size_t nGrowUpStep = 1; size_t nElementCnt = getElementCount(); if (nElementCnt <= 0) { nGrowUpStep = 8; } else if (nElementCnt <= 256) { nGrowUpStep = 16; } else { /// 1/8的现有元素个数, M$的做法 nGrowUpStep = (getElementCount() - (getElementCount() % 8)) / 8; } return nGrowUpStep;}#endif // #ifndef DYNAMIC_ARRAYS_H_