[資料結構] 使用 C 語言:串列走訪 (List Traversal)

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

    前言

    本文探討兩個和串列走訪相關的議題,一個是迭代器 (iterator),一個是和串列走訪相關的高階函式 (higher-order function)。這兩個議題不是典型資料結構教材會提到的主題,如果覺得目前用不到先略過也無妨。

    迭代器 (Iterator)

    串列的迭代器的抽象資料結構

    迭代器 (iterator) 是在不暴露資料結構內部的前提下走訪該資料結構的公開方法。對資料結構實作者而言,藉由實作迭代器可以隱藏實作細節;對資料結構使用者來說,不用知道資料結構的內部實作也可以走訪該結構;對雙方來說,是雙羸的局面。

    迭代器的抽象資料結構有顯性和隱性兩種。以下是顯性的迭代器:

    L is a list.
    I is an iterator.
    
    sub Start(L): I
    sub Next(I): I
    sub End(I): bool
    sub Value(I): data
    

    顯性的迭代器會回傳代表迭代器的變數 I。使用範例如下:

    for I <- Start(L); not End(I); I <- Next(I) do
        data <- value(I)
        Do something on data
    end for
    

    隱性迭代器的抽象資料結構如下:

    L is a list.
    
    sub Start(L): bool
    sub Next(L): bool
    sub End(L): bool
    sub Value(L): data
    

    和顯性迭代器不同,這時候不會有額外的變數。使用範例如下:

    if Start(L) then
        while not End(L) do
            data <- value(L)
            Do something on data
            Next(L)
        end while
    end if
    

    實作迭代器

    要實作外部迭代器可參考以下虛擬碼:

    I belongs to Node type.
    
    sub Start(L):
        assert L != null
        
        I <- L->head
        return I
    
    sub Next(I):
        if I == null then
            return null
        end if
        
        I <- I->next
        
        return I
    
    sub End(I):
        check whether I == null
    
    sub Value(I):
        assert I != null
    
        return I->data
    

    在隱性迭代器中,迭代器 I 會變成串列 L 的內部屬性,實作方式則大同小異,此處不列出。以下是等效的 C 語言外部迭代器程式碼:

    Node * list_start(const List *self)
    {
        assert(self);
    
        // Init an iterator.
        Node *iter = self->head;
    
        return iter;
    }
    
    Node * list_next(Node *self)
    {
        if (!self) {
            return NULL;
        }
    
        self = self->next;
    
        return self;
    }
    
    bool list_end(Node *self)
    {
        return self == NULL;
    }
    

    和串列走訪相關的高階函式 (Higher-Order Function)

    串列相關高階函式的抽象資料結構

    L, K are lists.
    
    // User-defined function objects.
    cmp <- fn(a, b): bool
    filter <- fn(a): bool
    mapper <- fn(a): result 
    reducer <- fn(a, b): result
    
    // ADT w/o side effects.
    sub Any(L, filter): bool
    sub All(L, filter): bool
    sub Find(L, filter): (result, bool)
    sub Select(L, filter): K
    sub Sort(L, cmp): K
    sub Map(L, mapper): K
    sub Reduce(L, reducer): result
    
    // Alternative ADT w/ side effects.
    sub SelectMut(L, filter): void
    sub SortMut(L, cmp): void
    sub MapMut(L, mapper): void
    
    • Any(L, filter)
    • All(L, filter)
    • Find(L, filter)
    • Select(L, filter)
    • SelectMut(L, filter)
    • Sort(L, cmp)
    • SortMut(L, cmp)
    • Map(L, mapper)
    • MapMut(L, mapper)
    • Reduce(L, reducer)

    基本上,帶有高階函式風格的串列走訪函式都可寫成 traverse(list, action) 的形式,我們只要預先寫好 traverse 的部分,使用者可隨需求自行填入 action 來搭配 traverse 以操作 list

    在這類函式中,有兩種風格,一種是無副作用 (side effect) 的,一種是有副作用的。前者不會改變原有的串列,而會回傳新的串列,後者則會直接修改原有的串列。兩種風格各有優劣,讀者可自行選擇喜好的方式。

    有些進階的程式設計教材會考慮多執行緒的情境,這種實作較有用,但會讓實作更複雜,本文暫不考慮這種情境。

    Any:確認串列中至少有一個元素符合條件

    Any 的虛擬碼如下:

    sub Any(L, filter):
        assert L != null
        
        curr <- L->head
        while curr != null do
            if filter(curr->data) then
                return true
            end if
            
            curr <- curr->next
        end while
        
        return false
    

    只要串列 L 中有符合 filter 的元素,就回傳 true 中止函式,若所有元素皆不符合則回傳 false。其 C 語言實作如下:

    typedef bool (*filterFn) (int);
    
    bool list_any(const List *self, filterFn filter)
    {
        assert(self);
    
        Node *curr = self->head;
    
        if (!curr) {
            return false;
        }
    
        while (curr) {
            if (filter(curr->data)) {
                return true;
            }
    
            curr = curr->next;
        }
    
        return false;
    }
    

    All:確認串列中所有元素皆符合條件

    All 的虛擬碼如下:

    sub All(L, filter):
        assert L != null
        
        curr <- L->head
        while curr != null do
            if not filter(curr->data) then
                return false
            end if
        
            curr <- curr->next
        end while
        
        return true
    

    只要串列 L 有不符合 filter 的元素,就回傳 false 中止函式,若所有元素皆符合則回傳 true。其 C 語言實作如下:

    typedef bool (*filterFn) (int);
    
    bool list_all(const List *self, filterFn filter)
    {
        assert(self);
    
        Node *curr = self->head;
    
        if (!curr) {
            return false;
        }
    
        while (curr) {
            if (!filter(curr->data)) {
                return false;
            }
    
            curr = curr->next;
        }
    
        return true;
    }
    

    Find:從串列中根據特定條件找出元素

    Find 的虛擬碼如下:

    sub Find(L, filter):
        assert L != null
        
        curr <- L->head
        i <- 0
        while curr != null do
            if filter(curr->data) then
                return (i, true)
            end if
            
            curr <- curr->next
            i <- i + 1
        end while
        
        return (0, false)
    

    在我們這個演算法中,若有符合條件 filter 的元素,會直接回傳 data 並中止函式,若所有元素皆不符合條件,則回傳空值。如果想要得到所有符合條件的元素,請參考下一節的 Select 函式。

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

    typedef bool (*filterFn) (int);
    
    bool list_find(const List *self, filterFn filter, size_t *out)
    {
        assert(!list_is_empty(self));
    
        Node *curr = self->head;
        size_t i = 0;
        while (curr) {
            if (filter(curr->data)) {
                *out = i;
                return true;
            }
    
            curr = curr->next;
            i++;
        }
    
        *out = 0;
        return false;
    }
    

    Select:從串列中取得所有符合條件的元素

    以下是 Select 的虛擬碼:

    sub Select(L, filter):
        assert L != null
        
        K <- a new empty list.
        curr <- L->head
        while curr != null do
            if filter(curr->data) then
                Push(K, curr->data)
            end
            
            curr <- curr->next
        end while
        
        return K
    

    由於此函式會回傳多個元素,我們要設計回傳的方式。一般來說,有兩種方法;一種是做一個新串列,將符合條件的元素放入該串列後回傳;另一種是將函式做成迭代器;前者會簡單一些,這裡展示第一種做法。

    以下是等效的 C 程式實作:

    typedef bool (*filterFn) (int);
    
    bool list_select_mut(List **self, filterFn filter)
    {
        assert(*self);
    
        List *out = list_new();
        if (!out) {
            return false;
        }
    
        Node *curr = (*self)->head;
        while (curr) {
            if (filter(curr->data)) {
                if (!list_push(out, curr->data)) {
                    list_free(out);
    
                    return false;
                }
            }
    
            curr = curr->next;
        }
    
        list_free(*self);
        *self = out;
    
        return true;
    }
    

    Sort:根據特定條件對串列排序

    本節採用插入排序法 (insertion);但因內部為串列,故採新增串列的方式來實作,在空間開銷上較大。以下是 Sort 的虛擬碼:

    sub Sort(L, filter):   
        K <- a new empty list
        
        if L->head == null
            return K
        end if
        
        curr <- L->head
        Push(K, curr->data)
        curr <- curr->next
        
        while curr != null do
            InsertBy(K, curr->data, filter)
    
            curr <- curr->next
        end while
        
        return K
    

    這個程式的關鍵在 InsertBy(L, value, predicate) 函式,下文會說明。以下是等效的 C 語言程式碼:

    typedef bool (*predicateFn) (int, int);
    
    List * list_sort(const List *self, predicateFn filter)
    {
        assert(self);
    
        if (list_is_empty(self)) {
            return NULL;
        }
    
        List *out = list_new();
        if (!out) {
            return out;
        }
    
        Node *curr = self->head;
        list_push(out, curr->data);
        curr = curr->next;
    
        while (curr) {
            list_insert_by(out, curr->data, filter);
    
            curr = curr->next;
        }
    
        return out;
    }
    

    InsertBy(L, value, predicate) 本身就是有序串列的插入元素的過程,但我們將節點關係拉到外部,變成參數。以下是其程式碼:

    sub InsertBy(L, value, predicate): void
        node <- Node(value)
        
        if IsEmpty(L) then
            L.head <- node
            L.tail <- node
            L.size += 1
            return
        end if
        
        if L.head == L.tail then
            if predicate(value, L.head.data) then
                node.next <- L.head
                L.head.prev <- node
                L.head <- node
            else
                L.tail.next <- node
                node.prev <- L.tail
                L.tail <- node
            end if
            
            L.size += 1
            return
        end if
        
        p <- null
        q <- L.head
        while q.next != null do
            if predicate(value, q.data) then
                if p == null then
                    node.next <- L.head
                    L.head.prev <- node
                    L.head <- node
                else
                    p.next <- node
                    node.prev <- p
                    
                    q.prev <- node
                    node.next <- q
                end if
                
                break
            end if
            
            p <- q
            q <- q.next
        end while
        
        if q == L.tail then
            L.tail.next <- node
            node.prev <- L.tail
            L.tail <- node
        end if
        
        L.size += 1
    

    當串列為空時,直接放入元素即可。

    當串列僅存有單一元素時,會依情境放入串列的頭端或尾端,由於會影響頭 (或尾) 端指標所指向的元素,需分開處理。

    走訪串列的方式為使用兩個指標來走訪,一個指標指向目標節點,另一個指標指向前一個節點。

    當串列有多個元素時,需再細分如下:

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

    當放入串列的頭 (或尾) 端時,會影響串列頭 (或尾) 端指標指向的節點,故需獨立出來處理。以下是等效的 C 語言程式碼:

    typedef bool (*predicateFn) (int, int);
    
    bool list_insert_by(List *self, int value, predicateFn predicate)
    {
        assert(self);
    
        Node *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 (predicate(value, self->head->data)) {
                node->next = self->head;
                self->head->prev = node;
                self->head = node;
            }
            else {
                self->tail->next = node;
                node->prev = self->tail;
                self->tail = node;
            }
    
            self->size++;
            return true;
        }
    
        Node *p = NULL;
        Node *q = self->head;
        while (q->next) {
            if (predicate(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) {
            self->tail->next = node;
            node->prev = self->tail;
            self->tail = node;
        }
    
        self->size++;
    
        return true;
    }
    

    Map:走訪串列並根據特定條件修改元素

    以下是 Map 的虛擬碼:

    sub Map(L, mapper):
        assert L != null
        
        K <- a new empty list
        curr <- L->head
        while curr != null do
            Push(K, mapper(curr->data))
            
            curr <- curr->next
        end while
        
        return K
    

    在本節中,我們另生成新串列,若要改成直接修改現有串列也可以。以下是等效的 C 語言程式碼:

    typedef int (*mapFn) (int);
    
    bool list_map(List **self, mapFn mapper)
    {
        assert(*self);
    
        List *result = list_new();
        if (!result) {
            return false;
        }
    
        Node *p = (*self)->head;
        while (p) {
            if (!list_push(result, mapper(p->data))) {
                list_free(result);
                result = NULL;
                return false;
            }
    
            p = p->next;
        }
    
        list_free(*self);
        *self = result;
    
        return true;
    }
    

    Reduce:將串列所有元素根據特定條件合併

    以下是 Reduce 的虛擬碼:

    sub Reduce(L, reducer):
        assert not IsEmpty(L)
        
        curr <- L->head
        a <- curr->data
        curr <- curr->next // Iterate one step.
        
        while curr != null do
            a <- reducer(a, curr->data)
            
            curr <- curr->next
        end while
        
        return a
    

    若串列只有一個元素時,while 迴圈不會運轉,函式仍是相容的。以下是等效的 C 語言程式碼:

    typedef int (*reduceFn) (int, int);
    
    int list_reduce(const List *self, reduceFn reducer)
    {
        assert(!list_is_empty(self));
    
        Node *curr = self->head;
        int a = curr->data;
        curr = curr->next;
    
        while (curr) {
            a = reducer(a, curr->data);
    
            curr = curr->next;
        }
    
        return a;
    }
    

    Function Chaining:簡潔而緊湊的函數式程式

    由於我們實作的語言是 C,無法寫得很簡潔,像下例使用 Ruby 做 function chaining 的語法就無法達成:

    # Ruby excerpt.
    # Chaining higher-order functions.
    
    (1..10)
        .select { |n| n % 2 != 0 }
        .map { |n| n * n }
        .reduce { |a, b| a + b } \
            == (1 * 1 + 3 * 3 + 5 * 5 + 7 * 7 + 9 * 9) \
                or raise "Wrong result"
    

    對等的 C 程式碼會 verbose 得多,因為兩者設計的理念不同,無法混為一談。

    在演算法上的效率

    以下是各個高階函式的效率:

    • Any(L, filter)O(n)
    • All(L, filter)O(n)
    • Find(L, filter)O(n)
    • Select(L, filter)O(n)
    • Sort(L, cmp)O(n^2)
    • Map(L, mapper)O(n)
    • Reduce(L, reducer)O(n)

    由於高階函式皆需走訪整個串列,效率至少為 O(n)。高階函式的功能在於其功能性而非程式效率。

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