C語言中動态數組的作用,C++實作動态數組功能

數組

數組是一種線性表資料結構。它用一組連續記憶體空間，來存儲一組具有相同資料類型資料。

1.線性表：資料存儲像一條線一樣的結構，每個線性表上的資料最多隻有前和後的兩個方向，如數組、連結清單、隊列、棧等都是這種結構，是以實作的數組的動态操作，其他結構也可輕易的類似實作。更重要的是，在這之後看源碼就可大大降低難度。(部落客自己看的是STL源碼剖析)

2.非線性表：如二叉樹、堆、圖等。

3連續記憶體空間和相同資料類型：當數組作插入、删除操作時，為了保證資料的連續性，往往需要做大量的資料搬移工作，效率很低。

動态數組功能實作

1.數組初始化

考慮到擴容時資料搬移可能會發生的記憶體洩露，部落客這裡采用兩隻手的原則，即設定一個記憶體标志位 ItemsFlag 。當 ItemsFlag = 0，using preitems；當 ItemsFlag = 1，using items。下文擴容部分有具體實作。預設數組容量10。

enum { MAX = 10 };

explicit GenericArray(int ss = MAX);

template

GenericArray::GenericArray(int ss) : capacity(ss),counts(0)

{

itemsFlag = 0;

preitems = new T[capacity];

items = nullptr;

}

2.析構函數

釋放記憶體。

template

GenericArray::~GenericArray()

{

if (preitems != nullptr)

delete[]preitems;

if (items != nullptr)

delete[]items;

}

3.檢查下标

檢查要操作的下标是否在數組容量範圍内。

template

bool GenericArray::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

T GenericArray::get(int index)

{

if (!itemsFlag)

return preitems[index];

else

return items[index];

}

void GenericArray::set(int index, T elem)

{

if(checkIndex(index))

{

if (!itemsFlag)

preitems[index] = elem;

else

items[index] = elem;

return;

}

}

template

void GenericArray::printArray()const

{

for (int i = 0; i < counts; i++)

if (!itemsFlag)

cout << preitems[i] << '\t';

else

cout << items[i] << '\t';

cout << '\n';

return;

}

template

bool GenericArray::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

void GenericArray::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

void GenericArray::removeElement(findArrIndex *ps)

{

for (int i = ps->numIndex; i > 0; i--)

remove((ps->findIndex)[i - 1]);

delete[](ps->findIndex);

}

template

void GenericArray::set(int index, T elem)

{

if(checkIndex(index))

{

if (!itemsFlag)

preitems[index] = elem;

else

items[index] = elem;

return;

}

}

7.擴容

添加資料操作時需判斷數組容量是否足夠，若不夠需考慮擴容。

template

void GenericArray::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

*(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

*(preitems + i) = *(items + i);

delete[]items;

items = nullptr;

}

}

8.添加資料：數組添加資料包括按索引下标插值、數組頭插值、數組尾插值。實質上後兩種都可以通過調用按索引下标插值函數實作。前文也提到過，數組添加操作中複雜的是大量的資料搬移工作：将某個元素按索引下标插入到數組第k個位置，需要将k ~ n部分的元素向後搬移一位，然後插入元素，更新元素數目。若插入到數組尾，時間複雜度O(1)；插入到數組頭，時間複雜度O(n)；插入的平均時間複雜度為(1+2+…+n)/n = O(n)。

另外，還有一個優化問題：若數組是無序數組，則插入時不需要搬移資料：若将某個元素插入到數組第k個位置，首先将該位置的元素移動到數組末尾，然後将待插入元素插入到第k個位置，時間複雜度O(1)。

template

void GenericArray::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

void GenericArray::addFirst(T elem)

{

add(0, elem);

}

template

void GenericArray::addLast(T elem)

{

add(counts, elem);

}

9.删除資料：數組删除資料包括按索引下标删除、數組頭删除、數組尾删除。實質上後兩種都可以通過調用按索引下标删除函數實作。與前文類似，數組删除操作中複雜的也是大量的資料搬移工作：按索引下标将某個元素删除，需要将k+1 ~ n部分的元素向前搬移一位，更新元素數目。若删除數組尾，直接元素數目減一即可，時間複雜度O(1)；删除數組頭，時間複雜度O(n)；删除的平均時間複雜度(1+2+…+n)/n = O(n)。

另外，有一個優化問題：如果想多次删除數組中的值，可以先對要删除的值做好标記，做完标記後一次删除，這樣就大大減少了搬移的次數。

template

T GenericArray::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

T GenericArray::removeFirst()

{

return remove(0);

}

template

T GenericArray::removeLast()

{

return remove(counts - 1);

}

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

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

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