數(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)容，希望對大家的學習有所幫助，也希望大家多多支持VEVB武林網(wǎng)。
新聞熱點
疑難解答
