本文共 4225 字，大约阅读时间需要 14 分钟。

​数组是一种线性表数据结构，除了第一个元素以外，集合中的每个数据元素均只有一个前驱，除了最后一个元素以外，集合中每个元素均只有一个后继，用一组连续的内存空间，来存储一组具有相同类型的数据。

数组采用连续的存储单元存放数据，所以数组一般不作插入和删除等操作，一旦建立了数组，则结构中的数据元素个数和元素间的关系就确定了，因此采用顺序存储结构表示数组。

数组是程序设计语言中比较基础但是却至关重要的数据结构，最大的优点是数组支持随机访问，根据下表随机访问的时间复杂度是O(1)。其实数据结构里边的线性表都是可以通过数组实现的，由于数组本身插入删除等操作效率会很低，所以线性表一般的实现都是采取基于链表方式或者散列存储方式。

数组一旦被定义，它的维数和维界就不再改变。因此除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。存储单元是一维的结构，而数组是个多维的结构，我们通常可以把二维数组理解为一维数组里边存放了一个一维数组，依此内推。

下边是一个数组类的C++不完整的简单实现：

CArray.hpp

#ifndef _CCArray_H_#define _CCArray_H_​#include
   
    ​using namespace std;​#define MAX_SIZE 512​template 
    
     class CArray{protected:  T *m_pData;    //指向数组数据的指针  unsigned int base;    //base为数组的起始下标  unsigned int length;    //length为数组的长度public:  CArray();    //构造函数  CArray(unsigned int, unsigned int = 0);    //数组构造函数  ~CArray();    //析构函数​  CArray(CArray const&);    //拷贝构造函数  CArray& operator = (CArray const&);    //重载等号操作符,用于一个数组给另外一个数组赋值​  T const& operator [] (unsigned int) const;    //重载中括号操作符，返回一个T数值常量，返回值不能被改变，在函数末尾加const表示this指针指向const  T& operator [] (unsigned int);    //重载中括号操作符，返回一个T数值常量，其返回值可以被改变​  T* data() const;    //返回数组数据的指针m_pData  unsigned int getBase() const;    //返回成员base  unsigned int getLength() const;    //返回成员length​  void setBase(unsigned int);    //设置成员变量base的数值  void setLength(unsigned int);    //设置成员变量length的数值​  void print();};​​//构造函数不含变量，只需要给对象的变量一个初始值,时间复杂度O(1)template 
     
      CArray
      
       ::CArray() :m_pData(new T[MAX_SIZE]),base(0),length(0){​}​//初始化数组，n为数组的长度，时间复杂度常量O(1)template 
       
        CArray
        
         ::CArray(unsigned int n, unsigned int m) : m_pData(new T[n]), base(m), length(n){}​//拷贝构造函数，将一个数组从赋值到另外一个数组,时间复杂度为O(n)template 
         
          CArray
          
           ::CArray(CArray
           
             const& CArray) : m_pData(new T[CArray.length]), base(CArray.base), length(CArray.length){ for (unsigned int i = 0; i < length; ++i) m_pData[i] = CArray.m_pData[i];}​​//析构函数，删除数组所占用的内存空间template 
            
             CArray
             
              ::~CArray(){ delete[] m_pData; m_pData = nullptr;}​template 
              
               T* CArray
               
                ::data() const{ return m_pData;}​template 
                
                 unsigned int CArray
                 
                  ::getBase() const{ return base;}​template 
                  
                   unsigned int CArray
                   
                    ::getLength() const{ return length;}​//这两个都为取下表操作符的重载，区别是第一个返回值不可以作为左值，第二个返回值可以作为左值,时间复杂度都为O(1)template 
                    
                     T const& CArray
                     
                      ::operator[] (unsigned int position) const{ unsigned int const offset = position - base; if (offset >= length) throw out_of_range("invalid position"); return m_pData[offset];}​template 
                      
                       T& CArray
                       
                        ::operator[] (unsigned int position){ unsigned int const offset = position - base; if (offset >= length) throw out_of_range("invalid position"); return m_pData[offset];}​template 
                        
                         void CArray
                         
                          ::setBase(unsigned int newBase){ base = newBase;}​template 
                          
                           void CArray
                           
                            ::setLength(unsigned int newLength){ T* const newm_pData = new T[newLength]; unsigned int const min = length < newLength ? length : newLength; for (unsigned int i = 0; i < min; ++i) newm_pData[i] = m_pData[i]; delete[] m_pData; m_pData = newm_pData; length = newLength;}​//重载赋值操作符，时间复杂度为O(n)template 
                            
                             CArray
                             
                              & CArray
                              
                               ::operator = (CArray
                               
                                 const& CArray){ if (this != &CArray) { delete[] m_pData; base = CArray.base; length = CArray.length; m_pData = new T[length]; for (unsigned int i = 0; i < length; ++i) m_pData[i] = CArray.m_pData[i]; } return this;}​template 
                                
                                 void CArray
                                 
                                  ::print(){ cout << "m_pData:"; for (unsigned int i = base; i < length; i++) { cout << m_pData[i] << " "; } cout << endl; cout << "length:" << length << endl; cout << "base:" << base << endl;}​​#endif // !_CCArray_H_​
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

main.cpp

#include "CArray.hpp"#include 
   
    using namespace std;int main(int argc, char** argv){  CArray
    
      CArray0 = CArray
     
      ();  CArray0.print();  cout << endl;​  CArray
      
        CArray1 = CArray
       
        (10);  CArray1.print();  cout << endl;​  CArray
        
          CArray2(CArray1); CArray2.print(); cout << endl; CArray2.~CArray();​ CArray
         
           CArray3(10); for (unsigned int i = CArray1.getBase(); i < CArray1.getLength() - CArray1.getBase(); i++) { CArray3.data()[i] = i; } CArray3.print(); cout << endl;​ CArray3.setBase(2); CArray3.print(); cout << endl;​ CArray3.setLength(7); CArray3.print();​ system("pause"); return 0;}
         
        
       
      
     
    
   

执行结果：

以上是我用C++对数组的简单实现，有不足的地方欢迎大家指正！

--|END|--

转载地址：http://jeiii.baihongyu.com/