開源技術教學文件網 實作動態陣列 (Dynamic Array)

最後修改日期為 NOV 26, 2019

動態陣列的抽象資料結構

動態陣列 (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 (尾端)。

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

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

以下是等效的 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->headarr->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;
}

使用不定參數時需引入 <stdarg.h>,這是標準函式庫的一部分。一般使用方式是以三個巨集相互搭配:

  • 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 合法,之後直接以 indexA.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 - 11,因為我們允許陣列使用者從陣列尾端推入元素。

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

若要從陣列尾端放入元素,直接重用 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)),若元素搬動不頻繁,使用動態陣列會比鏈結串列佳。

分享本文
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Yahoo
追蹤本站
Facebook Facebook Twitter