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

【分享本文】
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

    有序串列的抽象資料結構

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

    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)

    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email
    【追蹤新文章】
    Facebook Twitter Plurk