欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實現動態(tài)數組功能

 更新時間:2018年11月22日 09:09:56   作者:fall_foliage  
這篇文章主要為大家詳細介紹了C++實現動態(tài)數組功能,具有一定的參考價值,感興趣的小伙伴們可以參考一下

數組

數組是一種線性表數據結構。它用一組連續(xù)內存空間,來存儲一組具有相同數據類型數據。

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

動態(tài)數組功能實現

1.數組初始化

考慮到擴容時數據搬移可能會發(fā)生的內存泄露,博主這里采用兩只手的原則,即設定一個內存標志位 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;
 }
}

8.添加數據:數組添加數據包括按索引下標插值、數組頭插值、數組尾插值。實質上后兩種都可以通過調用按索引下標插值函數實現。前文也提到過,數組添加操作中復雜的是大量的數據搬移工作:將某個元素按索引下標插入到數組第k個位置,需要將k ~ n部分的元素向后搬移一位,然后插入元素,更新元素數目。若插入到數組尾,時間復雜度O(1);插入到數組頭,時間復雜度O(n);插入的平均時間復雜度為(1+2+…+n)/n = O(n)。
另外,還有一個優(yōu)化問題:若數組是無序數組,則插入時不需要搬移數據:若將某個元素插入到數組第k個位置,首先將該位置的元素移動到數組末尾,然后將待插入元素插入到第k個位置,時間復雜度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.刪除數據:數組刪除數據包括按索引下標刪除、數組頭刪除、數組尾刪除。實質上后兩種都可以通過調用按索引下標刪除函數實現。與前文類似,數組刪除操作中復雜的也是大量的數據搬移工作:按索引下標將某個元素刪除,需要將k+1 ~ n部分的元素向前搬移一位,更新元素數目。若刪除數組尾,直接元素數目減一即可,時間復雜度O(1);刪除數組頭,時間復雜度O(n);刪除的平均時間復雜度(1+2+…+n)/n = O(n)。
另外,有一個優(yōu)化問題:如果想多次刪除數組中的值,可以先對要刪除的值做好標記,做完標記后一次刪除,這樣就大大減少了搬移的次數。

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

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

最后總結一下,多看源碼還是很重要的。

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。

相關文章

  • 求數組中最長遞增子序列的解決方法

    求數組中最長遞增子序列的解決方法

    本篇文章是對c++中求數組中最長遞增子序列的方法進行了詳細的分析介紹,需要的朋友參考下
    2013-05-05
  • 基于c++強制類型轉換的(總結)詳解

    基于c++強制類型轉換的(總結)詳解

    本篇文章對C++中的強制類型轉換進行了詳細的分析介紹。需要的朋友參考下
    2013-05-05
  • c語言實現的幾種常用排序算法

    c語言實現的幾種常用排序算法

    C,語言常用的排序方法有很多種。比如說冒泡排序,直接交換排序,直接選擇排序,直接插入排序,二分插入排序,快速排序,歸并排序等等,下面這篇文章主要給大家介紹了關于c語言實現幾種常用的排序算法,需要的朋友可以參考下
    2021-06-06
  • 由static_cast和dynamic_cast到C++對象占用內存的全面分析

    由static_cast和dynamic_cast到C++對象占用內存的全面分析

    下面小編就為大家?guī)硪黄蓅tatic_cast和dynamic_cast到C++對象占用內存的全面分析。小編覺得挺不錯的,現在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-01-01
  • 可能是全網最詳細的Qt連接MySQL數據庫教程

    可能是全網最詳細的Qt連接MySQL數據庫教程

    QT眾所周知是一個開源的,以C++為底層的可視化工具庫,下面這篇文章主要給大家介紹了關于最詳細的Qt連接MySQL數據庫教程的相關資料,文中通過圖文介紹的非常詳細,需要的朋友可以參考下
    2023-04-04
  • C++ win系統如何用MinGW編譯Boost庫

    C++ win系統如何用MinGW編譯Boost庫

    這篇文章主要介紹了C++ win系統如何用MinGW編譯Boost庫問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-12-12
  • 淺析c++中new和delete的用法

    淺析c++中new和delete的用法

    以下是對c++中new和delete的用法進行了詳細的分析介紹,需要的朋友可以過來參考下
    2013-09-09
  • 利用C語言實現n字棋游戲

    利用C語言實現n字棋游戲

    本文將利用C語言編寫一個n字棋游戲,和井字棋一樣,不過這個游戲你可以自定義棋盤的大小。文中的示例代碼講解詳細,感興趣的小伙伴可以嘗試一下
    2022-05-05
  • C語言實現簡易通訊錄實例

    C語言實現簡易通訊錄實例

    大家好,本篇文章主要講的是C語言實現簡易通訊錄實例,感興趣的同學趕快來看一看吧,對你有幫助的話記得收藏一下
    2022-02-02
  • C++ 模擬實現list(迭代器)實現代碼

    C++ 模擬實現list(迭代器)實現代碼

    這篇文章主要介紹了C++ 模擬實現list(迭代器)實現代碼的相關資料,需要的朋友可以參考下
    2017-05-05

最新評論