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

來(lái)源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語(yǔ)言|點(diǎn)擊：次

數(shù)組

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

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

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

1.數(shù)組初始化

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

檢查要操作的下標(biāo)是否在數(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.獲取元素?cái)?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.取索引對(duì)應(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.查找某值下標(biāo)、刪除某值

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

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.擴(kuò)容

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

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ù)包括按索引下標(biāo)插值、數(shù)組頭插值、數(shù)組尾插值。實(shí)質(zhì)上后兩種都可以通過(guò)調(diào)用按索引下標(biāo)插值函數(shù)實(shí)現(xiàn)。前文也提到過(guò)，數(shù)組添加操作中復(fù)雜的是大量的數(shù)據(jù)搬移工作：將某個(gè)元素按索引下標(biāo)插入到數(shù)組第k個(gè)位置，需要將k ~ n部分的元素向后搬移一位，然后插入元素，更新元素?cái)?shù)目。若插入到數(shù)組尾，時(shí)間復(fù)雜度O(1)；插入到數(shù)組頭，時(shí)間復(fù)雜度O(n)；插入的平均時(shí)間復(fù)雜度為（1+2+…+n）/n = O(n)。
另外，還有一個(gè)優(yōu)化問(wèn)題：若數(shù)組是無(wú)序數(shù)組，則插入時(shí)不需要搬移數(shù)據(jù)：若將某個(gè)元素插入到數(shù)組第k個(gè)位置，首先將該位置的元素移動(dòng)到數(shù)組末尾，然后將待插入元素插入到第k個(gè)位置，時(shí)間復(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ù)包括按索引下標(biāo)刪除、數(shù)組頭刪除、數(shù)組尾刪除。實(shí)質(zhì)上后兩種都可以通過(guò)調(diào)用按索引下標(biāo)刪除函數(shù)實(shí)現(xiàn)。與前文類似，數(shù)組刪除操作中復(fù)雜的也是大量的數(shù)據(jù)搬移工作：按索引下標(biāo)將某個(gè)元素刪除，需要將k+1 ~ n部分的元素向前搬移一位，更新元素?cái)?shù)目。若刪除數(shù)組尾，直接元素?cái)?shù)目減一即可，時(shí)間復(fù)雜度O(1)；刪除數(shù)組頭，時(shí)間復(fù)雜度O(n)；刪除的平均時(shí)間復(fù)雜度（1+2+…+n）/n = O(n)。
另外，有一個(gè)優(yōu)化問(wèn)題：如果想多次刪除數(shù)組中的值，可以先對(duì)要?jiǎng)h除的值做好標(biāo)記，做完標(biāo)記后一次刪除，這樣就大大減少了搬移的次數(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é)一下，多看源碼還是很重要的。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持我們。

上一篇：C++中運(yùn)算符重載的規(guī)則語(yǔ)法實(shí)例

欄目：C語(yǔ)言

下一篇：關(guān)于C語(yǔ)言中E-R圖的詳解

本文標(biāo)題：C++實(shí)現(xiàn)動(dòng)態(tài)數(shù)組功能

本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/628.html

更多C語(yǔ)言

欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

C語(yǔ)言

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

您可能感興趣的文章

閱讀排行

本欄相關(guān)

隨機(jī)閱讀