[資料結構] 使用 C 語言：實作有序串列 (Ordered List)

有序串列的抽象資料結構

有序串列是串列的變體，和一般串列主要的差異在於放入元素時會自動將元素排序。以下是有序串列的抽象資料結構：

L is a list.

sub IsEmpty(L): bool
sub PeekFront(L): result
sub PeekRear(L): result
sub At(L, index): result, 0 <= index < size
sub Pop(L): result
sub Shift(L): result
sub Add(L, value): void
sub RemoveAt(L, index): result

由上述資料結構可知有序串列的行為如下：

• IsEmpty(L)：檢查串列是否為空
• PeekFront(L)：檢視串列頭端的元素
• PeekRear(L)：檢視串列尾端的元素
• At(L, index)：視視串列任意位置的元素
• Pop(L)：從串列尾端取出元素
• Shift(L)：從串列頭端取出元素
• Add(L, value)：將元素放入串列
• RemoveAt(L, index)：從串列中任意位置取出元素

有序串列的特色在於檢視頭端 (或尾端) 時，可以快速取得極大 (或極小) 值，而不需走訪串列。另外，從串列頭端 (或尾端) 逐一取出元素時，剛好可以依序取得相對大 (或相對小) 的值。

若和一般的串列比較，可發現有序串列能用的操作較少，因為有序串列在設計上要保持元素間的相對關係，一般串列的部分操作會破壞這個相對關係，使有序串列失效，故在有序串列中會禁用這些操作。

宣告有序串列類別

宣告有序串列的類別如下：

class Node:
    data <- none
    next <- null
    prev <- null

class List:
    head <- null
    tail <- null
    filter <- a predicate function

類似於我們先前所實作的線性資料結構，會有內部節點 Node 和主類別 List。

在本範例中，我們另外儲存判斷節點值關係的函式 filter。一般的教材會把節點值的關係直接寫死在程式碼，這樣的程式碼重用性相對低。在本範例中，我們將節點關係以函式物件的方式參數化，讓使用者自行填入節點關係的部分，增進其重用性。

以下是等效的 C 程式：

typedef struct node node_t;

struct node {
    int data;
    node_t *prev;
    node_t *next;
};

typedef struct list list_t;

struct list {
    filter filter;
    size_t size;
    node_t *head;
    node_t *tail;
};

有序串列的建構函式

以下是 C 語言版本的有序串列建構函式：

typedef bool (*filter) (int a, int b);

list_t * list_new(filter fn)
{
    list_t *lt = malloc(sizeof(list_t));
    if (!lt) {
        return lt;
    }

    lt->filter = fn;
    lt->size = 0;
    lt->head = NULL;
    lt->tail = NULL;

    return lt;
}

在同一個物件中，節點間的關係應該是固定的，否則有序串列會失去其功效。因此，我們在建立串列時即儲存其節點關係。

有序串列的解構函式

以下是 C 語言的有序串列解構函式：

void list_delete(void *self)
{
    if (!self) {
        return;
    }

    node_t *curr = ((list_t *) self)->head;
    node_t *temp;
    while (curr) {
        temp = curr;
        curr = curr->next;
        free(temp);        
    }

    free(self);
}

同樣地，要先逐一釋放內部節點後再釋放串列物件本身。

檢查有序串列是否為空

以下是檢查有序串列是否為空的虛擬碼：

sub IsEmpty(L): bool
    assert not IsEmpty(L)

    return L.head == null

檢查頭端是否為空即可。以下是等效的 C 語言實作：

bool list_is_empty(list_t *self)
{
    assert(self);

    return self->head == NULL;
}

檢視有序串列頭端的元素

以下是檢查有序串列頭端的虛擬碼：

sub PeekFront(L): result
    assert not IsEmpty(L)

    return L.head.data

在確認串列不為空之後，回傳頭端的資料即可。由於有序串列的頭端代表極大 (或極小) 值，這個函式有一定的實用性。以下是等效的 C 程式碼：

int list_peek_front(list_t *self)
{
    assert(!list_is_empty(self));
    return self->head->data;
}

檢視有序串列尾端的元素

以下是檢視有序串列尾端的虛擬碼：

sub PeekRear(L): result
    assert not IsEmpty(L)

    return L.tail.data

確認串列不為空後回傳尾端的資料即可。由於有序串列的尾端代表極大 (或極小) 值，這個函式有一定的實用性。以下是等效的 C 程式碼：

int list_peek_rear(list_t *self)
{
    assert(!list_is_empty(self));
    return self->tail->data;
}

檢視有序串列中任意位置的元素

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

sub At(L, index): result
    assert not IsEmpty(L)
    assert 0 <= index < Size(L)

    p <- L.head
    i <- 0
    while p != null do
        if i == index then
            return p.data
        end if

        p <- p.next
        i += 1
    end while

    throw "There should be some value"

由於我們內部以鏈結串列實作，需逐一走訪元素直到特定位置為止。以下是等效的 C 程式碼：

bool list_at(list_t *self, size_t index, int *out)
{
    assert(self);
    assert(index < list_size(self));

    node_t* curr = self->head;
    size_t i = 0;
    while (curr) {
        if (i == index) {
            *out = curr->data;
            return true;
        }

        curr = curr->next;
        i++;
    }

    return false;
}

上述函式的使用方式如下：

// `lt` is a list.

int *out = malloc(sizeof(int));

if (list_at(lt, 3, out)) {
    // `out` is valid here.
}

// Free `out` later.

從有序串列頭端取出元素

以下是從有序串列的頭端取出元素的虛擬碼：

sub Shift(L): result
    assert not IsEmpty(L)

    result <- L.head.data

    if L.head == L.tail then
        L.head <- null
        L.tail <- null
    else
        p <- L.head
        L.head <- p.next
        delete p
    end if

    L.size -= 1

    return result

先確認串列不為空，之後根據串列元素的數量決定頭、尾端指標的處理方式。由於此項操作不會影響有序串列間元素的相對關係，是合法的操作。以下是等效的 C 程式碼：

int list_shift(list_t *self)
{
    assert(!list_is_empty(self));

    int popped = self->head->data;

    if (self->head == self->tail) {
        free(self->head);
        self->head = NULL;
        self->tail = NULL;
    }
    else {
        node_t *curr = self->head;
        self->head = curr->next;
        free(curr);
        self->head->prev = NULL;
    }

    self->size--;

    return popped;
}

從有序串列尾端取出元素

以下是從有序串列的尾端取出元素的虛擬碼：

sub Pop(L): result
    assert not IsEmpty(L)

    result <- L.tail.data

    if L.head == L.tail then
        delete L.tail
        L.head <- null
        L.tail <- null
    else
        p <- L.tail
        L.tail <- p.prev
        delete p
        L.tail.next <- null
    end if

    L.size -= 1

    return result

先確認串列不為空，之後根據串列元素的數量決定頭、尾端指標的處理方式。如同上一節，此項操作不會影響有序串列間元素的相對關係，是合法的操作。以下是等效的 C 程式碼：

int list_pop(list_t *self)
{
    assert(!list_is_empty(self));

    int popped = self->tail->data;

    if (self->head == self->tail) {
        free(self->tail);
        self->head = NULL;
        self->tail = NULL;
    }
    else {
        node_t *curr = self->tail;
        self->tail = curr->prev;
        free(curr);
        self->tail->next = NULL;
    }

    self->size--;

    return popped;
}

將元素放入有序串列

將元素放入有序串列時可分為以下數種情境：

• 串列為空
• 串列僅有單一元素
• 串列有多個元素

在本節中，我們用函數式風格來實作將元素放入有序串列的行為，這樣對重用程式碼有利。以下是其虛擬碼，略長，下文會再說明：

filter is a predicate function.

sub Add(L, value):
    assert L != null

    node <- node_t(value)

    if L.head == null then
        L.head <- node
        L.tail <- node

        L.size += 1

        return
    end if

    if L.head == L.tail then
        if L.filter(value, L.head.data) then
            node.next <- self.head
            self.head.next <- node
            self.head <- node
        else
            self.head.next <- node
            node.prev <- self.head
            self.tail <- node
        end if

        L.size += 1

        return
    end if

    p <- null
    q <- L.head
    while q.next != null do    
        if L.filter(value, q.data) then
            if p == null then
                node.next <- q
                self.head.prev <- node
                self.head <- q
            else
                p.next <- node
                node.prev <- p

                node.next <- q
                q.prev <- node
            end

            L.size += 1
            break
        end

        p <- q
        q <- q->next
    end while

    if q == L.tail then
        if L.filter(value, q.data) then
            p.next <- node
            node.prev <- p

            q.prev <- node
            node.next <- q
        else
            q.next <- node
            node.prev <- q
            q <- node
            L.tail <- q
        end if
    end if

    L.size += 1

在串列為空時，由於放入的位置是唯一的，直接放入元素即可。

在串列只有一個元素時，會因元素間的相對關係，決定新元素要放至頭端或尾端。由於會直接影響頭、尾端指標所指向的元素，故獨立出來處理。

當串列有多個元素時，逐一走訪串列，直到符合特定關係時放入元素。這時要再細分為三個情境：

• 放入串列頭端
• 放入串列尾端
• 放入串列中其他的位置

在放入串列頭 (或尾) 端時，會影響頭 (或尾) 端指標所指向的元素，故需獨立處理。以下是等效的 C 語言程式：

bool list_insert(list_t *self, int value)
{
    assert(self != NULL);

    node_t *node = node_new(value);
    if (!node) {
        return false;
    }

    if (!(self->head)) {
        self->head = node;
        self->tail = node;

        self->size++;

        return true;
    }

    if (self->head == self->tail) {
        if (self->filter(value, self->head->data)) {
            node->next = self->head;
            self->head->prev = node;
            self->head = node;
        }
        else {
            self->head->next = node;
            node->prev = self->head;
            self->tail = node;
        }

        self->size++;

        return true;
    }

    node_t *p = NULL;
    node_t *q = self->head;
    while (q->next) {
        if (self->filter(value, q->data)) {
            if (!p) {
                node->next = self->head;
                self->head->prev = node;
                self->head = node;
            }
            else {
                p->next = node;
                node->prev = p;

                q->prev = node;
                node->next = q;
            }

            break;
        }

        p = q;
        q = q->next;
    }

    if (q == self->tail) {
        if (self->filter(value, q->data)) {
            p->next = node;
            node->prev = p;

            q->prev = node;
            node->next = q;
        }
        else {
            self->tail->next = node;
            node->prev = self->tail;
            self->tail = node;
        }
    }

    self->size++;

    return true;
}

從有序串列中任意位置移出元素

從串列中移出元素時，需考慮以下情境：

• 串列值單一元素
• 串列有多個元素

後者需依移出串列的相對位置再細分，會於下文說明。以下是其虛擬碼：

sub RemoveAt(L, index): result
    assert not IsEmpty(L)

    if L.size == 1 then
        assert index == 0
    else
        assert 0 <= index < L.size
    end if

    if L.size == 1 then
        result <- L.head.data

        delete L.head
        L.head <- null
        L.tail <- null
        L.size -= 1

        return result
    end if

    p <- null
    q <- L.head
    i <- 0
    while q.next != null do
        if i == index then
            result <- q.data

            if p == null then
                L.head <- q.next
                delete q
                L.head.prev <- null
            else
                p.next <- q.next
                q.next.prev <- p
                delete q
            end if

            break
        end if

        p <- q
        q <- q.next
        i += 1
    end while

    if q == L.tail then
        result <- q.data
        L.tail <- q.prev
        delete q
        L.tail.next <- null
    end if

    L.size -= 1

    return result

當串列只有一個元素時，將該元素移出串列即可。

當串列有多個元素時，需再細分為以下情境：

• 從串列頭端移出元素
• 從串列尾端移出元素
• 從串列其他位置移出元素

牽涉到頭 (或尾) 端時，會影響頭 (或尾) 端指標所指向的元素，故需獨立處理。以下是等效的 C 程式碼：

int list_remove_at(list_t *self, size_t index)
{
    assert(!list_is_empty(self));

    if (list_size(self) == 1) {
        assert(index == 0);
    }
    else {
        assert(index < list_size(self));
    }

    if (list_size(self) == 1) {
        int result = self->head->data;

        free(self->head);
        self->head = NULL;
        self->tail = NULL;
        self->size--;

        return result;
    }

    int result;

    node_t *p = NULL;
    node_t *q = self->head;
    size_t i = 0;
    while (q->next) {
        if (i == index) {
            result = q->data;

            if (!p) {
                self->head = q->next;
                free(q);
                self->head->prev = NULL;
            }
            else {
                p->next = q->next;
                q->next->prev = p;
                free(q);
            }

            break;
        }

        p = q;
        q = q->next;
        i++;
    }

    if (q == self->tail) {
        result = q->data;
        self->tail = p;
        free(q);
        self->tail->next = NULL;
    }

    self->size--;

    return result;
}

在演算法上的效率

依據本範例的實作，其效率如下：

• IsEmpty(L): O(1)
• PeekFront(L): O(1)
• PeekRear(L): O(1)
• At(L, i): O(n)
• Pop(L)：O(1)
• Shift(L)：O(1)
• Add(L, value): O(n)
• RemoveAt(L, index)：O(n)

要注意 Add(L, value) 在單次執行時效率是 O(n)，但會有 n 個元素逐一插入，故在排序的觀點上，有序串列的效率仍是 O(n^2)。相對來說，有序串列的好處在取極大 (或極小) 值時，其效率為 O(1)。