溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

C++實現(xiàn)動態(tài)數(shù)組功能

發(fā)布時間：2020-10-19 00:11:52 來源：腳本之家 閱讀：174 作者：fall_foliage 欄目：編程語言

數(shù)組

數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)內(nèi)存空間，來存儲一組具有相同數(shù)據(jù)類型數(shù)據(jù)。

1.線性表：數(shù)據(jù)存儲像一條線一樣的結(jié)構(gòu)，每個線性表上的數(shù)據(jù)最多只有前和后的兩個方向，如數(shù)組、鏈表、隊列、棧等都是這種結(jié)構(gòu)，所以實現(xiàn)的數(shù)組的動態(tài)操作，其他結(jié)構(gòu)也可輕易的類似實現(xiàn)。更重要的是，在這之后看源碼就可大大降低難度。（博主自己看的是STL源碼剖析）
2.非線性表：如二叉樹、堆、圖等。
3連續(xù)內(nèi)存空間和相同數(shù)據(jù)類型：當數(shù)組作插入、刪除操作時，為了保證數(shù)據(jù)的連續(xù)性，往往需要做大量的數(shù)據(jù)搬移工作，效率很低。

動態(tài)數(shù)組功能實現(xiàn)

1.數(shù)組初始化

考慮到擴容時數(shù)據(jù)搬移可能會發(fā)生的內(nèi)存泄露，博主這里采用兩只手的原則，即設(shè)定一個內(nèi)存標志位 ItemsFlag 。當 ItemsFlag = 0，using preitems；當 ItemsFlag = 1，using items。下文擴容部分有具體實現(xiàn)。默認數(shù)組容量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.析構(gòu)函數(shù)

釋放內(nèi)存。

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

3.檢查下標

檢查要操作的下標是否在數(shù)組容量范圍內(nèi)。

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.獲取元素數(shù)目和容量、判斷數(shù)組空和滿

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

5.取索引對應(yīng)值、按索引修改值、打印輸出、是否包含某值

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.查找某值下標、刪除某值

查找某值的下標時，要考慮到該值在數(shù)組中是否重復(fù)，所以博主用了一個結(jié)構(gòu)體 findArrIndex 來存儲該值重復(fù)的次數(shù)和對應(yīng)的下標。

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.擴容

添加數(shù)據(jù)操作時需判斷數(shù)組容量是否足夠，若不夠需考慮擴容。

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;
 }
}

8.添加數(shù)據(jù)：數(shù)組添加數(shù)據(jù)包括按索引下標插值、數(shù)組頭插值、數(shù)組尾插值。實質(zhì)上后兩種都可以通過調(diào)用按索引下標插值函數(shù)實現(xiàn)。前文也提到過，數(shù)組添加操作中復(fù)雜的是大量的數(shù)據(jù)搬移工作：將某個元素按索引下標插入到數(shù)組第k個位置，需要將k ~ n部分的元素向后搬移一位，然后插入元素，更新元素數(shù)目。若插入到數(shù)組尾，時間復(fù)雜度O(1)；插入到數(shù)組頭，時間復(fù)雜度O(n)；插入的平均時間復(fù)雜度為（1+2+…+n）/n = O(n)。
另外，還有一個優(yōu)化問題：若數(shù)組是無序數(shù)組，則插入時不需要搬移數(shù)據(jù)：若將某個元素插入到數(shù)組第k個位置，首先將該位置的元素移動到數(shù)組末尾，然后將待插入元素插入到第k個位置，時間復(fù)雜度O(1)。

template<class T>
void GenericArray<T>::add(int index, T elem)
{
 if (isFull())
 {
 cout << "Array is full!" << '\n';
 renewCapacity();
 }
 if (checkIndex(index))
 if(!itemsFlag)
 {
  for (int i = counts; i > index; i--)
  preitems[i] = preitems[i - 1];
  preitems[index] = elem;
 }
 else
 {
  for (int i = counts; i > index; i--)
  items[i] = items[i - 1];
  items[index] = elem;
 }
 counts++;
 return;
}

template<class T>
void GenericArray<T>::addFirst(T elem)
{
 add(0, elem);
}

template<class T>
void GenericArray<T>::addLast(T elem)
{
 add(counts, elem);
}

9.刪除數(shù)據(jù)：數(shù)組刪除數(shù)據(jù)包括按索引下標刪除、數(shù)組頭刪除、數(shù)組尾刪除。實質(zhì)上后兩種都可以通過調(diào)用按索引下標刪除函數(shù)實現(xiàn)。與前文類似，數(shù)組刪除操作中復(fù)雜的也是大量的數(shù)據(jù)搬移工作：按索引下標將某個元素刪除，需要將k+1 ~ n部分的元素向前搬移一位，更新元素數(shù)目。若刪除數(shù)組尾，直接元素數(shù)目減一即可，時間復(fù)雜度O(1)；刪除數(shù)組頭，時間復(fù)雜度O(n)；刪除的平均時間復(fù)雜度（1+2+…+n）/n = O(n)。
另外，有一個優(yōu)化問題：如果想多次刪除數(shù)組中的值，可以先對要刪除的值做好標記，做完標記后一次刪除，這樣就大大減少了搬移的次數(shù)。

template<class T>
T GenericArray<T>::remove(int index)
{
 if (!isEmpty())
 { 
 if (checkIndex(index))
 {
  if (!itemsFlag)
  {
  T temp = preitems[index];
  for (int i = index+1; i < counts; i++)
   preitems[i - 1] = preitems[i];
  counts--;
  return temp;
  }
  else
  {
  T temp = items[index];
  for (int i = index + 1; i < counts; i++)
   items[i - 1] = items[i];
  counts--;
  return temp;
  }
 }
 }
 else
 {
 cout << "Array is empty!" << '\n';
 return -1;
 }
}
template<class T>
T GenericArray<T>::removeFirst()
{
 return remove(0);
}
template<class T>
T GenericArray<T>::removeLast()
{
 return remove(counts - 1);
}

好啦，基本上就這么多了。

最后總結(jié)一下，多看源碼還是很重要的。

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習有所幫助，也希望大家多多支持億速云。

向AI問一下細節(jié)

免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手