數據結構(04)_數組類的實現

C++中支持原生數組，但由于原生數組的天然缺陷（不能獲取長度信息、越界訪問不會報錯...），我們有必要來開發自己的數組類，從而解決這些問題。
數組類的繼承關系如圖：

1.數組類的實現_1

1.1.抽象類模板Array

需求分析：
1、由于線性表，不能作為數組直接使用，我們需要自己實現一個數組類來代替原生數組。
2、解決原生數組越界訪問不會報錯的問題
3、提供數組的長度信息

1.2.Array設計要點：

• 抽象類模本,存儲空間的位置和大小由子類指定。
• 重載數組操作符，并判斷訪問下標是否越界（合法）
• 提供數組長度信息的抽象訪問函數
• 提供數組對象間的復制操作（通過重載拷貝構造函數和賦值操作符完成）

  template < typename T >
  class Array : public Object
  {
  protected:
  T *m_array;
  public:
  T& operator [] (int index)
  T operator [] (int index) const
  bool get(int index, const T& e)
  bool set(int index, const T& e)
  virtual int length(void) = 0;
  };

  1.3. Array的實現

template < typename T >
class Array : public Object
{
protected:
    T *m_array;
public:
    T& operator [] (int index)
    {
        if( (index>=0) && (index<length()) )
        {
            return m_array[index];
        }
        else
        {
            THROW_EXCEPTION(IndexOutOfBoundsException, "array index out of range...");
        }
    }

    T operator [] (int index) const
    {
        return const_cast<Array<T>&>(*this)[index];
    }

    bool get(int index, const T& e)
    {
        bool ret = (index>=0) && (index<length());

        if( ret )
        {
            e = m_array[index];
        }

        return ret;
    }

    bool set(int index, const T& e)
    {
        bool ret = (index>=0) && (index<length);

        if( ret )
        {
            m_array[index] = e;
        }

        return ret;
    }

    virtual int length(void) = 0;
};

1.4.StaticArray設計要點

設計要點：

• 封裝原生數組;
• 使用模板參數決定數組大小
• 實現函數返回數組長度
• 拷貝構造和賦值重載

  template < typename T, int N >
  class StaticArray : public Array<T>   
  protected:
  T m_space[N];
  public:
  StaticArray()
  // 提供拷貝構造喊賦值重載函數，實現數組的拷貝
  StaticArray(const StaticArray<T, N>& obj)
  T& operator = (const StaticArray<T, N>& obj)
  int length(void)
  };

  1.5. StaticArray的實現

template <typename T, int N>
class StaticArray : public Array<T>
{
protected:
    T m_space[N];
public:
    StaticArray()
    {
        this->m_array = m_space;
    }

    StaticArray(const StaticArray<T, N>& obj)
    {
        this->m_array = m_space;

        for(int i=0; i<length();i++)   // 數組元素拷貝
        {
            m_space[i] = obj.m_space[i];
        }
    }

    T& operator ==(const StaticArray<T, N>& obj)
    {
        if(this != &obj)
        {
            this->m_array = m_space;

            for(int i=0; i<length();i++)
            {
                m_space[i] = obj.m_space[i];
            }
        }
    }

    int length(void)
    {
        return N;
    }
};

2.數組類的實現_2

2.1.DynamicArray設計要點

設計要點：類模板

• 動態確定內部數組空間的大小
• 實現函數返回數組的長度
• 拷貝構造和賦值操作

  template < typename T >
  class DynamicArray : public Array<T>
  {
  protected:
  int m_length;
  public:
  DynamicArray(int length)
  DynamicArray(const DynamicArray<T>& obj)
  DynamicArray<T>& operator = (const DynamicArray<T>& obj)
  void resize(int length)
  ~DynamicArray()
  };

  2.2.DynamicArray代碼優化

  DynamicArray類中的函數實現存在重復的邏輯，可以進行代碼優化。
  重復代碼邏輯的抽象：
  — init 函數中實現對象構造時的初始化操作
  — copy 函數負責從堆空間中申請內存，并執行拷貝構造操作
  — updata 將指定的堆空間作為內部存儲數組使用

  2.3. DynamicArray實現

template <typename T>
class DynamicList : public SeqList<T>
{

protected:
    int m_capacity;
public:
    DynamicList(int capacity)
    {
        this->m_array = new T[capacity];
        if(this->m_array != NULL)
        {
            this->m_length = 0;
            this->m_capacity = capacity;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException,"No memory to create DynamicList object ...");
        }
    }

    int capacity()const
    {
        return m_capacity;
    }

    void resize(int capacity)
    {
        if(capacity != m_capacity)
        {
            T* array = new T[capacity];
            if(array != NULL)
            {
                int length = (this->m_length < capacity ? this->m_length : capacity);
                for(int i=0;i<length;i++)
                {
                    array[i] = this->m_array[i];
                }

                T* temp = this->m_array;
                this->m_array = array;
                this->m_length = length;
                this->m_capacity = capacity;
                delete[] temp;
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryException,"No memory to create DynamicList object ...");
            }
        }
    }

    ~DynamicList()
    {
        delete[] this->m_array;
    }
};

總結：

• StaticArray通過封裝原生數組的方式，實現數組類
• DynamicArray動態申請堆空間，使得數組長度動態可變
• 數組對象能夠代替原生數組，并且使用上更安全
• 代碼優化時項目開發必不可少的環節