【在主画面加入捷径】
       
【选择语系】
繁中 简中

[数据结构] 使用 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)

    【赞助商连结】