C++實(shí)現(xiàn)動(dòng)態(tài)數(shù)組功能
數(shù)組
數(shù)組是一種線(xiàn)性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)內(nèi)存空間，來(lái)存儲(chǔ)一組具有相同數(shù)據(jù)類(lèi)型數(shù)據(jù)。
1.線(xiàn)性表：數(shù)據(jù)存儲(chǔ)像一條線(xiàn)一樣的結(jié)構(gòu)，每個(gè)線(xiàn)性表上的數(shù)據(jù)最多只有前和后的兩個(gè)方向，如數(shù)組、鏈表、隊(duì)列、棧等都是這種結(jié)構(gòu)，所以實(shí)現(xiàn)的數(shù)組的動(dòng)態(tài)操作，其他結(jié)構(gòu)也可輕易的類(lèi)似實(shí)現(xiàn)。更重要的是，在這之后看源碼就可大大降低難度。（博主自己看的是STL源碼剖析）
2.非線(xiàn)性表：如二叉樹(shù)、堆、圖等。
3連續(xù)內(nèi)存空間和相同數(shù)據(jù)類(lèi)型：當(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ù)組空和滿(mǎn)
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)。與前文類(lèi)似，數(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í)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
本篇文章是對(duì)c++中求數(shù)組中最長(zhǎng)遞增子序列的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
基于c++強(qiáng)制類(lèi)型轉(zhuǎn)換的(總結(jié))詳解
本篇文章對(duì)C++中的強(qiáng)制類(lèi)型轉(zhuǎn)換進(jìn)行了詳細(xì)的分析介紹。需要的朋友參考下2013-05-05
C,語(yǔ)言常用的排序方法有很多種。比如說(shuō)冒泡排序,直接交換排序,直接選擇排序,直接插入排序,二分插入排序,快速排序,歸并排序等等,下面這篇文章主要給大家介紹了關(guān)于c語(yǔ)言實(shí)現(xiàn)幾種常用的排序算法,需要的朋友可以參考下2021-06-06
由static_cast和dynamic_cast到C++對(duì)象占用內(nèi)存的全面分析
下面小編就為大家?guī)?lái)一篇由static_cast和dynamic_cast到C++對(duì)象占用內(nèi)存的全面分析。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-01-01
可能是全網(wǎng)最詳細(xì)的Qt連接MySQL數(shù)據(jù)庫(kù)教程
QT眾所周知是一個(gè)開(kāi)源的,以C++為底層的可視化工具庫(kù),下面這篇文章主要給大家介紹了關(guān)于最詳細(xì)的Qt連接MySQL數(shù)據(jù)庫(kù)教程的相關(guān)資料,文中通過(guò)圖文介紹的非常詳細(xì),需要的朋友可以參考下2023-04-04
C++ win系統(tǒng)如何用MinGW編譯Boost庫(kù)
這篇文章主要介紹了C++ win系統(tǒng)如何用MinGW編譯Boost庫(kù)問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-12-12
以下是對(duì)c++中new和delete的用法進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過(guò)來(lái)參考下2013-09-09
本文將利用C語(yǔ)言編寫(xiě)一個(gè)n字棋游戲，和井字棋一樣，不過(guò)這個(gè)游戲你可以自定義棋盤(pán)的大小。文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以嘗試一下2022-05-05
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易通訊錄實(shí)例
大家好，本篇文章主要講的是C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易通訊錄實(shí)例，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話(huà)記得收藏一下2022-02-02
C++ 模擬實(shí)現(xiàn)list(迭代器)實(shí)現(xiàn)代碼
這篇文章主要介紹了C++ 模擬實(shí)現(xiàn)list(迭代器)實(shí)現(xiàn)代碼的相關(guān)資料,需要的朋友可以參考下2017-05-05