C++实现动态数组功能分享！

数组

数组是一种线性表数据结构。它用一组连续内存空间，来存储一组具有相同数据类型数据。

1.线性表：数据存储像一条线一样的结构，每个线性表上的数据最多只有前和后的两个方向，如数组、链表、队列、栈等都是这种结构，所以实现的数组的动态操作，其他结构也可轻易的类似实现。更重要的是，在这之后看源码就可大大降低难度。（博主自己看的是STL源码剖析）
2.非线性表：如二叉树、堆、图等。
3连续内存空间和相同数据类型：当数组作插入、删除操作时，为了保证数据的连续性，往往需要做大量的数据搬移工作，效率很低。

动态数组功能实现

1.数组初始化

考虑到扩容时数据搬移可能会发生的内存泄露，博主这里采用两只手的原则，即设定一个内存标志位 ItemsFlag 。当 ItemsFlag = 0，using preitems；当 ItemsFlag = 1，using items。下文扩容部分有具体实现。默认数组容量10。

  enum { MAX = 10 };  explicit GenericArray(int ss = MAX);  template<class T>  GenericArray<T>::GenericArray(int ss) : capacity(ss),counts(0)  {   itemsFlag = 0;   preitems = new T[capacity];   items = nullptr;  }

2.析构函数

释放内存。

  template<class T>  GenericArray<T>::~GenericArray()  {    if (preitems != nullptr)   delete[]preitems;    if (items != nullptr)   delete[]items;  }

3.检查下标

检查要操作的下标是否在数组容量范围内。

  template<class T>  bool GenericArray<T>::checkIndex(int index)  {   if (index < 0 || index >= capacity)   {    int cap = capacity - 1;    cout << "Out of the range! Please ensure the index be     in 0 ~ " << cap << 'n';    return false;   }   return true;  }

4.获取元素数目和容量、判断数组空和满

  int count()const { return counts; }  int getCapacity()const { return capacity; }  bool isEmpty()const { return counts == 0; }  bool isFull()const { return counts >= capacity; }

5.取索引对应值、按索引修改值、打印输出、是否包含某值

  template<class T>  T GenericArray<T>::get(int index)  {   if (!itemsFlag)   return preitems[index];   else   return items[index];  }  void GenericArray<T>::set(int index, T elem)  {   if(checkIndex(index))   {   if (!itemsFlag)   preitems[index] = elem;   else   items[index] = elem;   return;   }  }  template<class T>  void GenericArray<T>::printArray()const  {   for (int i = 0; i < counts; i++)   if (!itemsFlag)    cout << preitems[i] << 't';   else    cout << items[i] << 't';    cout << 'n';   return;  }  template<class T>  bool GenericArray<T>::contains(T arr)  {   for (int i = counts - 1; i >= 0; i--)   if (!itemsFlag)   {    if (arr == preitems[i])    return true;   }   else   {    if (arr == items[i])    return true;   }   return false;  }

6.查找某值下标、删除某值

查找某值的下标时，要考虑到该值在数组中是否重复，所以博主用了一个结构体 findArrIndex 来存储该值重复的次数和对应的下标。

  struct findArrIndex  {   int numIndex;   int *findIndex;  };  template<class T>  void GenericArray<T>::find(T arr, findArrIndex *ps)  {   ps->findIndex = new int[counts];   ps->numIndex = 0;   for (int i = 0, j = 0; i < counts; i++, j++)   if (!itemsFlag)   {    if (arr == preitems[i])    {    (ps->findIndex)[j] = i;    (*ps).numIndex++;    cout << i << 't';    }   }   else    if (arr == items[i])    {    (ps->findIndex)[j] = i;    (*ps).numIndex++;    cout << i << 't';    }   cout << 'n';   return;  }  template<class T>  void GenericArray<T>::removeElement(findArrIndex *ps)  {   for (int i = ps->numIndex; i > 0; i--)   remove((ps->findIndex)[i - 1]);   delete[](ps->findIndex);  }  template<class T>  void GenericArray<T>::set(int index, T elem)  {   if(checkIndex(index))   {   if (!itemsFlag)   preitems[index] = elem;   else   items[index] = elem;   return;   }  }

7.扩容

添加数据操作时需判断数组容量是否足够，若不够需考虑扩容。

  template<class T>  void GenericArray<T>::renewCapacity()  {   cout << "The array's capacity is small! Renew capacity.n";   if (capacity < 1000)   capacity = capacity << 1;   else   capacity = capacity >> 1 + capacity;   if (!itemsFlag)   {   itemsFlag = 1;   items = new T[capacity];   for (int i = 0; i<counts; i++)    *(items + i) = *(preitems + i);    //items[i]=proitems[i];   //cout << items << 'n';   //cout << preitems << 'n';   delete[]preitems;   preitems = nullptr;   }   else   {   itemsFlag = 0;   preitems = new T[capacity];   for (int i = 0; i<counts; i++)    *(preitems + i) = *(items + i);   delete[]items;   items = nullptr;   }  }

• 1
• 2
• 下一页