[資料結構] 使用 C 語言：實作動態陣列 (Dynamic Array)

動態陣列的抽象資料結構

動態陣列 (dynamic array) 和鏈結串列 (linked list) 的抽象資料結構大抵上相同：

A is a dynamic array.

sub IsEmpty(A): bool
sub PeakFront(A): data
sub PeakRear(A): data
sub At(A, index): data
sub SetAt(A, index, data): void
sub Push(A, data): void
sub Shift(A, data): void
sub Pop(A): data
sub Unshift(A): data
sub InsertAt(A, index, data): void
sub RemoveAt(A, index): data

以下是動態陣列中和狀態相關的行為：

IsEmpty(A)：確認陣列是否為空
Size(A)：得知陣列的大小
PeakFront(A)：檢視陣列頭端的元素
PeakRear(A)：檢視陣列尾端的元素
At(A, index)：檢視陣列中任意位置的元素
SetAt(A, index, data)：設置陣列中任意位置的元素

在這些公開行為中，除了 SetAt 會改變動態陣列內部的狀態外，其他的行為都只是查詢用，不會改變動態陣列的狀態。

以下是操作動態陣列的方法：

Push(A, data)：從陣列尾端放入元素
Shift(A, data)：從陣列頭端放入元素
Pop(A)：從陣列尾端取出元素
Unshift(A)：從陣列頭端取出元素
InsertAt(A, index, data)：從陣列中任意位置放入元素
RemoveAt(A, index)：從陣列中任意位置取出元素

相對來說，這些方法就會改變動態陣列的狀態。

如果讀者把串列和動態陣列的抽象資料結構拿來比較，會發現陣列和串列的差異不在其外在行為，而在其內部實作。因實作方式的差異會造成兩者在行為上的效率有別。

宣告動態陣列類別

以下是動態陣列的類別宣告：

class Array
    size <- 0
    capacity <- n
    head <- 0
    tail <- 0
    elements <- an array which initial size == capacity

除了存放資料的陣列 elements 本身外，還會有四個屬性。和陣列大小相關的有陣列當下的大小 size 及陣列的最大容量 capacity；和陣列頭尾位置有關的則有 head (頭端) 和 tail (尾端)。

陣列在擴展容量時，不會只擴展一個元素，這樣比較沒有效率。常見的做法是在增加元素時偵測是否需要擴增最大容量，若需要擴容，則擴增一倍容量。所以需要 size 和 capacity 兩個值來記錄陣列的當下大小和最大容量。

為了增加陣列的效率，我們會採用環狀陣列。故 head 和 tail 不會固定在相同的位置，而會隨著陣列操作移動。這些端點的移動會隱藏在陣列內部，外部不需手動處理這些端點實際的位置。下文會討論環狀陣列的操作過程。

以下是等效的 C 程式碼：

typedef struct array_t array_t;

struct array_t {
    size_t size;
    size_t capacity;
    size_t head;
    size_t tail;
    int *elements;
};

由於 C 語言的陣列不會儲存陣列長度，故我們要在物件中另存陣列長度和容量的資訊。如果讀者使用 Java 等語言練習資料結構的話，就不需要這個動作。

動態陣列的建構函式

以下是 C 語言的動態陣列建構函式：

array_t * array_new(void)
{
    array_t *arr = malloc(sizeof(array_t));
    if (!arr)
        return arr;

    arr->size = 0;
    arr->capacity = 2;
    arr->head = 0;
    arr->tail = 0;

    arr->elements = malloc(arr->capacity * sizeof(int));
    if (!(arr->elements)) {
        array_delete(arr);
        arr = NULL;
        return arr;
    }

    return arr;
}

arr->capacity 的起始值只要大於等於 2 即可，一般會設成 16 或 32，在少量元素操作時才不會頻繁搬移元素。此處故意設為 2 是為了測試擴展容量是否出問題。由於我們是用陣列儲存資料，arr->head 和 arr->tail 不是指標，而是索引值。

上述建構函式會建立空陣列，這算是比較傳統的做法。我們也可以讓陣列使用者預先填值，如下例：

array_t *arr = array_init(5, 3, 4, 5, 6, 7);

在這個建構函式中，第一個參數代表陣列長度，第二個以後的參數代表實際填入陣列的值。array_init 用到 C 語言的不定參數，範例如下：

array_t * array_init(size_t size, int value, ...)
{
    array_t *arr = malloc(sizeof(array_t));
    if (!arr)
        return arr;

    // Create a new empty array.
    arr->size = 0;
    arr->capacity = 2;
    arr->head = 0;
    arr->tail = 0;

    arr->elements = malloc(arr->capacity * sizeof(int));
    if (!(arr->elements)) {
        array_delete(arr);
        arr = NULL;
        return arr;
    }

    // Fill the first element.
    arr->elements[arr->head] = value;
    arr->size++;

    // Start `args`, the paramater list.
    va_list args;
    va_start(args, value);

    // Fill more elements.
    for (size_t i = 1; i < size; i++) {
        // Expand the array if needed.
        if (i + 1 > arr->capacity) {
            arr->capacity <<= 1;

            int *old_arr = arr->elements;
            int *new_arr = malloc(arr->capacity * sizeof(int));
            if (!new_arr) {
                array_delete(arr);
                arr = NULL;
                va_end(args);
                return arr;
            }

            int i = arr->head;
            int j = arr->head;
            size_t s = 0;
            while (s < arr->size) {
                new_arr[j] = old_arr[i];

                i = (i + 1) % arr->size;
                j = (j + 1) % arr->capacity;
                s++;
            }

            arr->elements = new_arr;
            free(old_arr);
        }

        // Relocate the tail of the array.
        arr->tail = (arr->head + (arr->size - 1) + 1) % arr->capacity;
        // Fill some element.
        arr->elements[arr->tail] = va_arg(args, int);
        arr->size++;
    }

    // Free `args`
    va_end(args);

    return arr;
}

使用不定參數時需引入，這是標準函式庫的一部分。一般使用方式是以三個巨集相互搭配：

va_start：設置參數清單
va_arg：取得參數值
va_end：結束參數清單

使用方式請看本範例。

另外，我們在這裡實作擴充陣列的程式，後文會介紹細節，此處不重覆。

動態陣列的解構函式

以下是 C 語言的動態陣列解構函式：

void array_delete(void *self)
{
    if (!self)
        return;

    free(((array_t *) self)->elements);
    free(self);
}

先釋放內部的陣列後再釋放物件本身即可。

檢查陣列是否為空

以下虛擬碼檢查陣列是否為空：

sub IsEmpty(A): bool
    return A.size == 0

由於我們的物件中存有陣列大小的資訊，直接檢查陣列大小 A.size 是否為 0 即可。以下是等效的 C 程式：

bool array_is_empty(const array_t *self)
{
    assert(self);

    return self->size <= 0;
}

檢視陣列頭端的元素

以下是檢查陣列頭端元素的虛擬碼：

sub PeekFront(A): data
    assert not IsEmpty(A)

    return A.elements[A.head]

要先排除陣列為空的情形，之後以 A.head 為索引從 A.elements 取索引即可。以下是等效的 C 程式：

int array_peak_front(const array_t *self)
{
    assert(!array_is_empty(self));

    return self->elements[self->head];
}

檢視陣列尾端的元素

以下是檢查陣列尾端元素的虛擬碼：

sub PeekRear(A): data
    assert not IsEmpty(A)

    return A.elements[A.tail]

要先排除陣列為空的情形。接著，以 A.tail 為索引對 A.elements 取值即可。以下是等效的 C 程式：

int array_peak_rear(const array_t *self)
{
    assert(!array_is_empty(self));

    return self->elements[self->tail];
}

檢視陣列中任意位置的元素

以下是檢視陣列中任意位置的元素的虛擬碼：

sub At(A, index): data
    assert not IsEmpty(A)
    assert 0 <= index < Size(A)

    return A.elements[index]

要先確認陣列不為空及索引值 index 合法，之後直接以 index 對 A.elements 取值即可。以下是等效的 C 程式：

int array_at(const array_t *self, size_t index)
{
    assert(self);
    assert(index < array_size(self));

    size_t i = (self->head + index) % self->capacity;
    return self->elements[i];
}

由於型別 size_t 一定大於等於 0，故只需檢查索引值 index 的上限。

由於我們在內部使用環狀陣列，在使用索引值時要進行相對應的轉換。轉換方式是將索引值 index 重新以 self->head 為基準點平移，之後以 self->capacity 為容量進行環狀移動即可。

修改陣列中任意位置的元素

以下是修改陣列中任意位置元素的虛擬碼：

sub SetAt(A, index, data): void
    assert not IsEmpty(A)
    assert 0 <= index < Size(A)

    A.elements[index] <- data

要先確認陣列不為空及索引值 index 合法，之後以索引 index 取得 A.elements 所在的元素，將其值修改為 data。以下是等效的 C 程式碼：

void array_set_at(array_t *self, size_t index, int value)
{
    assert(self);
    assert(index < array_size(self));

    size_t i = (self->head + index) % self->capacity;
    self->elements[i] = value;
}

同樣要以前一節所提的方式對索引值做平移後才能使用。

從陣列尾端插入元素

以下是從陣列尾端插入元素的虛擬碼：

sub Push(A, data): void
    Expand(A)

    if A.size > 0 then
        A.tail <- (A.tail + 1) % A.capacity
    end if

    A.elements[A.tail] <- data
    A.size++

一開始要先偵測是否需要擴展容量，在容量擴展後才進行下一步動作。下文會談到 Expand(A) 部分的實作方式。

當陣列大小為 0 時，頭端 A.head 和尾端 A.tail 會指向同一個位置；反之，則需移動 A.tail 以免覆寫到其他元素。由於本陣列為環狀陣列，我們要對 A.tail 平移，之後再以 A.tail 為索引修改元素。以下是等效的 C 語言實作：

bool array_push(array_t *self, int value)
{
    assert(self);

    if (!array_expand(self)) {
        return false;
    }

    if (array_size(self) > 0) {
        self->tail = (self->tail + 1) % self->capacity;
    }

    self->elements[self->tail] = value;
    self->size++;

    return true;
}

在這段程式碼中，我們先略過 array_expand 函式，也就是 Expand(A) 部分的虛擬碼。這是因為這段程式碼比較長，而且在數個函式中會共用，故我們將其分離出來。這段虛擬碼稍微長一些，我們會講解：

sub Expand(A): void
    if A.size < A.capacity then
        return
    end if

    A.capacity <- A.capacity * 2

    old_arr <- A.elements
    new_arr <- A new array which initial size == A.capacity

    i <- A.head
    j <- A.head
    s <- 0
    while s < A.size do
        new_arr[j] <- old_arr[i]

        i <- (i + 1) % A.size
        j <- (j + 1) % A.capacity
        s <- s + 1
    end while

    A.elements <- new_arr
    A.tail <- (A.head + A.size - 1) % A.capacity
    delete old_arr

若 A.size 小於 A.capacity，表示不需擴展容量，直接結束此函式即可。

擴展容量的方式是建立新陣列後，將舊陣列上的元素逐一拷貝到新元素上，將 A.elements 指向新陣列，最後釋放掉舊陣列即可。在這裡我們使用環狀陣列的手法來逐一填值，需注意新陣列和舊陣列的大小相異。最後要修正 A.tail 的位置。

以下是等效的 C 程式碼：

static bool array_expand(array_t *self)
{
    if (self->size < self->capacity)
        return true;

    self->capacity <<= 1;
    int *old_arr = self->elements;
    int *new_arr = malloc(self->capacity * sizeof(int));
    if (!new_arr)
        return false;

    size_t i = self->head;
    size_t j = self->head;
    size_t s = 0;
    while (s < self->size) {
        new_arr[j] = old_arr[i];

        i = (i + 1) % self->size;
        j = (j + 1) % self->capacity;
        s++;
    }

    self->elements = new_arr;
    self->tail = (self->head + self->size - 1) % self->capacity;
    free(old_arr);

    return true;
}

從陣列頭端插入元素

以下是從陣列頭端插入元素的虛擬碼：

sub Unshift(A, data): void
    Expand(A)

    if A.size > 0 then
        A.head <- A.head == 0 ? A.capacity - 1 : A.head - 1
    end if

    A.elements[A.head] <- data
    A.size += 1

一開始先視需求擴展容量，再進行下一步動作。擴展容量的程式碼我們已經展示過，此處不重覆。

我們想做的動作是放入元素，但對 A.head 來說，卻是倒退一步，需注意方向。以下是等效的 C 程式：

bool array_unshift(array_t *self, int value)
{
    assert(self);

    if (!array_expand(self)) {
        return false;
    }

    if (array_size(self) > 0) {
        self->head = self->head == 0 ? self->capacity - 1 : self->head - 1;
    }

    self->elements[self->head] = value;
    self->size++;

    return true;
}

從陣列尾端移出元素

以下是從陣列尾端移出元素的虛擬碼：

sub Pop(A): result
    result <- A.elements[A.tail]

    A.tail <- A.tail == 0 ? A.capacity - 1 : A.tail - 1

    A.size -= 1

    return result

我們在移出元素時，A.tail 的方向是倒退，需注意兩者的方向。

在本範例程式中，我們沒有縮減陣列的大小，讀者可以自行嘗試實作看看。建議的方式是當陣列大小 (size) 小於陣列容量 (capacity) 的一半時，將陣列容量減少一半；但最小容量不低於 16 或 32，以免因頻繁搬移造成效能下降。

以下是等效的 C 語言實作：

int array_pop(array_t *self)
{
    assert(!array_is_empty(self));

    int result = self->elements[self->tail];

    self->tail = self->tail == 0 ? self->capacity - 1 : self->tail - 1;
    self->size--;

    return result;
}

從陣列頭端移出元素

以下是從陣列頭端移出元素的虛擬碼：

sub Shift(A): result
    result <- A.elements[A.head]

    A.head <- (A.head + 1) % A.size
    A.size -= 1

    return result

要注意移出元素時，A.head 的方向是前移。同前一節，讀者可自行嘗試縮減陣列。

以下是等效的 C 程式碼：

int array_shift(array_t *self)
{
    assert(!array_is_empty(self));

    int result = self->elements[self->head];

    self->head = (self->head + 1) % self->capacity;
    self->size--;

    return result;
}

從陣列中任一位置放入元素

從陣列中任一位置放入元素時，需分幾個情境：

原先陣列為空
從陣列尾端加入新元素
陣列不需擴展
陣列需擴展

之後還在再依陣列頭端及尾端的相對位置進行不同的處理。本節的虛擬碼較長，請耐心閱讀，可搭配下文說明來看：

sub InsertAt(A, index, data): void
    assert 0 <= index <= A.size

    if index == A.size then
        Push(A, data)
        return
    end if

    if A.size == 0 then
        A.elements[A.head] <- data
        A.size += 1
        return
    end if

    _index <- (A.head + index) % A.capacity

    if A.size + 1 < A.capacity then
        i <- A.tail
        s <- 0
        while s < A.size do
            if A.head <= A.tail or _index <= A.tail then
                if _index <= i then
                    A.elements[(i+1) % A.capacity] <- A.elements[i]
                end if

                if _index == i then
                    A.elements[i] <- data
                    break
                end if
            else if A.head <= _index then
                if i <= A.tail or _index <= i then
                    A.elements[(i+1) % A.capacity] <- A.elements[i]
                end if

                if _index == i then
                    A.elements[i] <- data
                    break
                end if
            end if

            i <- i == 0 ? i.size - 1 : i - 1
            s += 1
        end while

        A.size += 1

        A.tail <- (A.tail + 1) % A.capacity
    else
        A.capacity <- A.capacity * 2
        old_arr <- A.elements
        new_arr <- a new array which initial size == A.capacity

        i <- A.tail
        j <- A.size - 1
        k <- (A.head + index) % A.size
        s <- 0
        while s < A.size do
            if A.head <= A.tail or _index <= A.tail then
                if _index <= i then
                    new_arr[(j+1) % A.capacity] <- old_arr[i]

                    if i == _index then
                        new_arr[j] <- data
                    end if
                else
                    new_arr[j] <- old_arr[i]
                end if
            else if A.head <= _index then
                if i <= A.tail or _index <= i then
                    new_arr[(j+1) % A.capacity] <- old_arr[i]
                    if i == _index then
                        new_arr[j] <- data
                    end if
                else
                    new_arr[j] <- old_arr[i]
                end if
            end if

            i <- i == 0 ? A.size - 1 : i - 1
            j <- j == 0 ? A.capacity - 1 : j - 1
            s += 1
        end

        A.elements <- new_arr
        delete old_arr

        A.head <- 0
        A.size <- (A.size - 1) + 1
    end

    A.size += 1

一開始要先確認索引值 index 的合法性。若陣列為零，index 必為零，反之，index 介於零和陣列大小之間。此處的 index 會比索引上限 size - 1 多 1，因為我們允許陣列使用者從陣列尾端推入元素。

若陣列大小為零，能放的位置只有一個，直接將該元素放入即可。

若要從陣列尾端放入元素，直接重用 array_push 的程式即可，此處不重覆該部分實作。

由於我們採環狀陣列，要先將 index 平移成 _index 後再使用。由於本節採用邊搬邊插入元素的方式，所以沒有使用先前的 Expand(A) 代碼。這樣可以避免搬移兩次所造成的效能耗損。

搬移的方式是從尾端逐一走訪元素至頭端，在到達索引值 (含) 前將當下的元素往後搬移一格。在搬移時，要先區分是否需擴展容量，然後再細分為數種情形：

頭端和尾端方向正常
頭端和尾端方向相反
- 索引值位於尾端左側
- 索引值位於頭端右側

總共有六種情境，所以程式碼會比較長。

當不需擴展容量時，逐一搬移元素直到索引值所在的位置即可；根據索引值和頭、尾端旳相對關係，可再細分為三種。請讀者自行閱讀虛擬碼。

當有擴展容量時，逐一搬移元素直到索引值所在的位置即可；同樣地，根據索引值和頭、尾端的相對關係，可再細分為三種。我們在搬移的同時，順便歸零頭、尾端所在的位置，這樣反而比較容易確認頭尾端最後的位置。

以下是等效的 C 程式碼：

bool array_insert_at(array_t *self, size_t index, int value)
{
    assert(self);
    assert(index <= array_size(self));

    if (index == array_size(self))
        return array_push(self, value);

    size_t _index = (self->head + index) % self->capacity;

    if (array_size(self) == 0) {
        self->elements[_index] = value;
        self->size++;
        return true;
    }

    if (self->size < self->capacity) {
        size_t i = self->tail;
        size_t s = 0;
        size_t temp;
        while (s < array_size(self)) {
            if (self->head <= self->tail || _index <= self->tail) {
                if (_index <= i) {
                    temp = (i + 1) % self->capacity;
                    self->elements[temp] = self->elements[i];
                }

                if (_index == i) {
                    self->elements[i] = value;
                    break; 
                }
            }
            else if (self->head <= _index) {
                if (i <= self->tail || i >= _index) {
                    temp = (i + 1) % self->capacity;
                    self->elements[temp] = self->elements[i]; 
                }

                if (i == _index) {
                    self->elements[i] = value;
                    break;
                }
            }

            i = i == 0 ? self->capacity - 1 : i - 1;
            s++;
        }

        self->tail = (self->tail + 1) % self->capacity;
    }
    else {
        self->capacity <<= 1;
        int *old_arr = self->elements;
        int *new_arr = malloc(self->capacity * sizeof(int));
        if (!new_arr)
            return false;

        size_t i = self->tail;
        size_t j = self->size - 1;
        size_t s = 0;
        size_t temp;
        while (s < array_size(self)) {
            if (self->head <= self->tail || _index <= self->tail) {
                if (_index <= i) {
                    temp = (j + 1) % self->capacity;
                    new_arr[temp] = old_arr[i];

                    if (i == _index) {
                        new_arr[j] = value;
                    }
                }
                else {
                    new_arr[j] = old_arr[i];
                }
            }
            else if (self->head <= _index) {
                if (i <= self->tail || _index <= i) {
                    temp = (j + 1) % self->capacity;
                    new_arr[temp] = old_arr[i];

                    if (i == _index) {
                        new_arr[j] = value;
                    }
                }
                else {
                    new_arr[j] = old_arr[i];
                }
            }

            i = i == 0 ? self->size - 1 : i - 1;
            j = j == 0 ? self->capacity - 1 : j - 1;
            s++;
        }

        self->elements = new_arr;
        free(old_arr);

        self->head = 0;
        self->tail = (self->size - 1) + 1;
    }

    self->size++;

    return true;
}

從陣列中任意位置取出元素

以下是從陣列中移出元素的虛擬碼：

sub RemoveAt(A, index): result
    assert not IsEmpty(A)
    assert 0 <= index < A.size

    _index <- (A.head + index) % A.capacity
    result <- A.elements[_index]

    if A.size == 1 then
        A.tail <- A.tail == 0 ? A.size - 1 : A.tail - 1
        A.size -= 1
        return result
    end if

    i <- A.head
    s <- 0
    while s < A.size do
        if A.head <= A.tail then
            if _index <= i then
                A.elements[(i+1) % A.capacity] <- A.elements[i]
            end if
        else
            if _index <= A.tail then
                if _index <= 1 and i <= A.tail then
                    A.elements[(i+1) % A.capacity] <- A.elements[i]
                end if
            else
                if i <= A.tail or _index <= i then
                    A.elements[(i+1) % A.capacity] <- A.elements[i]
                end if
            end if
        end if

        i <- (i + 1) % A.capacity
        s += 1
    end while

    A.tail <- A.tail == 0 ? A.capacity - 1 : A.tail - 1
    A.size -= 1

    return result

搬移時，從頭端逐一走訪元素至尾端，在索引值所在點開始逐一將後一個元素的值覆寫到當下的位置。要依據索引值和頭、尾端相對位置分為三種情境。請讀者自行閱讀虛擬碼，以了解搬移的細節。

以下是等效的 C 程式碼：

int array_remove_at(array_t *self, size_t index)
{
    assert(!array_is_empty(self));
    assert(index < array_size(self));

    size_t _index = (self->head + index) % self->capacity;
    int result = self->elements[_index];

    if (array_size(self) == 1) {
        self->tail = self->tail == 0 ? self->size - 1 : self->tail - 1;
        self->size--;
        return result;
    }

    size_t i = self->head;
    size_t s = 0;
    size_t temp;
    while (s < array_size(self)) {
        if (self->head <= self->tail) {
            if (_index <= i) {
                temp = (i + 1) % self->capacity;
                self->elements[i] = self->elements[temp];
            }
        }
        else {
            if (_index <= self->tail) {
                if (_index <= i && i <= self->tail) {
                    temp = (i + 1) % self->capacity;
                    self->elements[i] = self->elements[temp];
                }
            }
            else {
                if (i <= self->tail || _index <= i) {
                    temp = (i + 1) % self->capacity;
                    self->elements[i] = self->elements[temp];
                }
            }
        }

        i = (i + 1) % self->capacity;
        s++;
    }

    self->tail = self->tail == 0 ? self->capacity - 1 : self->tail - 1;
    self->size--;

    return result;
}

演算法上的效率

動態陣列中和狀態相關的行為的效率：

IsEmpty(A)：O(1)
Size(A)：O(1)
PeakFront(A)：O(1)
PeakRear(A)：O(1)
At(A, index)：O(1)
SetAt(A, index, data)：O(1)

以下是操作動態陣列的方法：

Push(A, data)：amortized O(1)
Shift(A, data)：amortized O(1)
Pop(A)：O(1)
Unshift(A)：O(1)
InsertAt(A, index, data)：O(n)
RemoveAt(A, index)：O(n)

動態陣列比起鏈結串列的優點，在於隨機存取的效率較好 (O(1) 比 O(n))，若元素搬動不頻繁，使用動態陣列會比鏈結串列佳。

關於作者

身為資訊領域碩士，位元詩人 (ByteBard) 認為開發應用程式的目的是為社會帶來價值。如果在這個過程中該軟體能成為永續經營的項目，那就是開發者和使用者雙贏的局面。

位元詩人喜歡用開源技術來解決各式各樣的問題，但必要時對專有技術也不排斥。閒暇之餘，位元詩人將所學寫成文章，放在這個網站上和大家分享。