CLRS10 基本数据结构

2017-05-16 | 阅读：次

介绍

本章讨论如何通过使用指针的简单数据结构来表示动态集合。这里介绍栈、队列、链表和有根树。

10.1 栈和队列

栈: LIFO

STACK-EMPTY(S)
    return S.top == 0

PUSH(S, x)
    S.top += 1
    S[S.top] = x

POP(S)
    if STACK-EMPTY(S)
        error "underflow"
    else S.top -= 1
        return S[S.top + 1]

队列: FIFO

ENQUEUE(Q, x)
    Q[Q.tail] = x
    if Q.tail == Q.length
        Q.tail = 1
    else Q.tail += 1

DEQUEUE(Q)
    x = Q[Q.head]
    if Q.head = Q.length
        Q.head = 1
    else Q.head += 1
    return x

练习 10.1-1 Using Figure 10.1 as a model, illustrate the result of each operation in the sequence PUSH(S, 4), PUSH(S, 1), PUSH(S, 3), POP(S), PUSH(S, 8), and POP(S) on an initially empty stack S stored in array S[1…6].

1 2 3 4 5 6

4
4 1
4 1 3
4 1
4 1 8
4 1

练习 10.1-2 Explain how to implement two stacks in one array A[1…n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

一个从第一个元素往后，另一个从最后一个元素往前

练习 10.1-3 Using Figure 10.2 as a model, illustrate the result of each operation in the sequence ENQUEUE(Q, 4), ENQUEUE(Q, 1), ENQUEUE(Q, 3), DEQUEUE(Q), ENQUEUE(Q, 8), and DEQUEUE(Q) on an initially empty queue Q stored in array Q[1…6].

1 2 3 4 5 6

4 
4 1
4 1 3
  1 3
  1 3 8
    3 8

练习 10.1-4 Rewrite ENQUEUE and DEQUEUE to detect underflow and overflow of a queue.

ENQUEUE(Q, x)
    Q[Q.tail] = x
    if Q.tail == Q.length
        if Q.head == 1
            error "Queue overflow"
        Q.tail = 1
    else
        if Q.head == Q.tail + 1
           error "Queue overflow"  
        Q.tail += 1

DEQUEUE(Q)
    if Q.head == Q.tail
        error "Queue underflow"
    x = Q[Q.head]
    if Q.head = Q.length
        Q.head = 1
    else Q.head += 1
    return x

练习 10.1-5 Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double-ended queue) allows insertion and deletion at both ends. Write four O(1)-time procedures to insert elements into and delete elements from both ends of a deque constructed from an array.

class Deque:
    
    def __init__(self, size):
        self.N = 0
        self.head = 0
        self.tail = size - 1
        self.array = [0] * size
        self.size = size

    def addFirst(self, item):
        self.array[self.head] = item
        self.N += 1
        self.head = (self.head + 1) % self.size

    def addLast(self, item):
        self.array[self.tail] = item
        self.N += 1
        self.tail = (self.tail-1)%self.size

    def removeFirst(self):
        self.N -= 1
        self.head = (self.head-1) % self.size
        v = self.array[self.head]
        return v

    def removeLast(self):
        self.N -= 1
        self.tail = (self.tail+1) % self.size
        v = self.array[self.tail]
        return v

    def seeAll(self):
        print self.head, self.tail, self.n
        print self.array

练习 10.1-6 Show how to implement a queue using two stacks. Analyze the running time of the queue operations.

这道题以后再leetcode还会遇到。

练习 10.1-7 Show how to implement a stack using two queues. Analyze the running time of the stack operations.

同上。

链表

LIST-SEARCH(L, k)
    x = L.head
    while x != NIL and x.key != k
        x = x.next
    return x

LIST-INSERT(L, x)
    x.next = L.head
    if L.head != NIL
        L.head.prev = x
    L.head = x
    x.prev = NIL

LIST-DELETE(L, x)
    if x.prev != NIL
        x.prev.next = x.next
    else L.head = x.next
    if x.next != NIL
        x.next.prev = x.prev

用哨兵来简化边界条件的处理(circular, doubly linked list with a sentinel)

LIST-SEARCH'(L, k)
    x = L.nil.next
    while x != x.nil and x.key != k
        x = x.next
    return x

LIST-DELETE'(L, x)
    x.prev.next = x.next
    x.next.prev = x.prev

LIST-INSERT'(L, x)
    x.next = L.nil.next
    L.nil.next.prev = x
    L.nil.next = x
    x.rev = L.nil

是用哨兵的好处是使代码简洁，而非提升效率。(可以减低常数因子)
我们应当慎用哨兵。假如有许多个很短的链表他们的哨兵所占用的额外存储空间会造成严重的存储浪费。

练习 10.2-1 Can the dynamic-set operation INSERT be implemented on a singly linked list in O(1) time? How about DELETE?

插入可以，删除要先遍历找到元素。

LIST-INSERT(L, x)
    x.next = L.head
    L.head = x

LIST-DELETE(L, k)
    left = L
    right = L.next
    while right != NIL and right.key != k
        left = left.next
        right = right.next
    if right
        left.next = right.next

练习 10.2-2 Implement a stack using a singly linked list L. The operations PUSH and POP should still take O(1) time.

PUSH(L, x)
    x.next = L.head
    L.head = x

POP(L, x)
    L.head = x.next

练习 10.2-3 Implement a queue by a singly linked list L. The operations ENQUEUE and DEQUEUE should still take O(1) time.

L.head指向链表中第一个元素, L.tail指向最后一个

ENQUEUE(L, x)
    L.tail.next = x
    L.tail = x

DEQUEUE(L, x)
    x.next = L.head.next
    L.head = x

练习 10.2-4 As written, each loop iteration in the LIST-SEARC′ procedure requires two tests: one for x ≠ nil[L] and one for key[x] ≠ k. Show how to eliminate the test for x ≠ nil[L] in each iteration.

可以加一个哨兵，它的key是k

LIST-SEARCH'(L, k)
    L.nil.key = k
    x = L.nil.next
    while (x.key != k)
        x = x.next
    if x == L.nil
        return NIL
    return x

练习 10.2-5 Implement the dictionary operations INSERT, DELETE, and SEARCH using singly linked, circular lists. What are the running times of your procedures?

O(1), O(1), O(n)

练习 10.2-6 The dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and it returns a set S = S1 U S2 consisting of all the elements of S1 and S2. The sets S1 and S2 are usually destroyed by the operation. Show how to support UNION in O(1) time using a suitable list data structure.

链表，直接将第二个连接至第一个上。

练习 10.2-7 Give a Θ(n)-time nonrecursive procedure that reverses a singly linked list of n elements. The procedure should use no more than constant storage beyond that needed for the list itself.

用循环来做

练习 10.2-8 Explain how to implement doubly linked lists using only one pointer value np[x] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define np[x] to be np[x] = next[x] XOR prev[x], the k-bit “exclusive-or” of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in O(1) time.

一个元素XOR两次之后会得到1,所以要得到前一个元素就要XOR(np, next),要得到后一个元素XOR(np, prev)

10.3 指针和对象的实现

对象的多数组表示: 对每个属性使用一个数组表示，可以来表示一组有相同属性的对象。
对象的单数组表示：一个对象占用一段连续的子数组，每个属性对应特定的偏移量。它允许不同长度的对象存储在同一数组中。
对象的分配与释放

ALLOCATE-OBJECT()
    if free == NIL
        error "out of space"
    else x = free
        free = x.next
        return x

FREE-OBJECT(x)
    x.next = free
    free = x

练习10.3-1 Draw a picture of the sequence[13, 4, 8, 19, 5, 11]stored as a doubly linked list using the multiple-array representation. Do the same for the single-array representation.

arr:    1   2   3   4   5   6   7   8   9  10  11  12  13 
key:        13  4       8   19      5      11
next:       3   5       6   8       10     /
prev:       /   2       3   5       6      8  

arr:    1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
        13  /   3   4   2   5   8   3   6  19  5   8   5   6   10  11  8   /

练习10.3-2 Write the procedures ALLOCATE-OBJECT and FREE-OBJECT for a homogeneous collection of objects implemented by the single-array representation.

实现和多数组表示是差不多的

练习10.3-3 Why don’t we need to set or reset the prev fields of objects in the implementation of the ALLOCATE-OBJECT and FREE-OBJECT procedures?

因为并不关心前一个元素是什么，只获取后一个就行了。

练习10.3-4 It is often desirable to keep all elements of a doubly linked list compact in storage, using, for example, the first m index locations in the multiple-array representation. (This is the case in a paged, virtual-memory computing environment.) Explain how the procedures ALLOCATE>- OBJECT and FREE-OBJECT can be implemented so that the representation is compact. Assume that there are no pointers to elements of the linked list outside the list itself. (Hint: Use the array implementation of a stack.)

ALLOCATE: 选取free_list的head
FREE: 不直接变成free_list的head,而是插入free_list的恰当位置。

练习10.3-5 Let L be a doubly linked list of length m stored in arrays key, prev, and next of length n. Suppose that these arrays are managed by ALLOCATE-OBJECT and FREE-OBJECT procedures that keep a doubly linked free list F. Suppose further that of the n items, exactly m are on list L and n-m are on the free list. Write a procedure COMPACTIFY-LIST(L, F) that, given the list L and the free list F, moves the items in L so that they occupy array positions 1, 2,…, m and adjusts the free list F so that it remains correct, occupying array positions m + 1, m + 2,…, n. The running time of your procedure should be Θ(n), and it should use only a constant amount of extra space. Give a careful argument for the correctness of your procedure.

就跟partition一样交换，用两个指针，一个从前往后，一个从后往前，直到相遇

10.4 有根树的表示

每个结点都有一个关键字key, 然后有几个指向其他结点的指针
用左孩子右兄弟法(left-child, right-sibling)可以表示孩子数任意的树:每个结点饱含父结点指针p，和两个指针。x.left-child指向结点x最左边的孩子结点，x.right-sibling指向x右侧相邻的兄弟节点。
也可以用其它方法表示有根树，哪种方法最优取决于具体应用。
练习10.4-1 Draw the binary tree rooted at index 6 that is represented by the following fields.

看表画图= =

练习10.4-2 Write an O(n)-time recursive procedure that, given an n-node binary tree, prints out the key of each node in the tree.

INORDER-WALK(root)
    if root is NIL: return
    INORDER-WALK(root.left)
    print(root.key)
    INORDER-WALK(root.left)

练习10.4-3 Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node in the tree. Use a stack as an auxiliary data structure

NONRECURSIVE-WALK(root)
    S = [root]
    while S
        last = S[-1]
        if last is NIL: continue
        print(last.key)
        S.pop()
        S += [S.left, S.right]

练习10.4-4 Write an O(n)-time procedure that prints all the keys of an arbitrary rooted tree with n nodes, where the tree is stored using the left-child, right-sibling representation.

WALK(root)
    if root is NIL: return
    print(root.key)
    WALK(root.left-child)
    WALK(root.right-sibling)

练习10.4-5 Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node. Use no more than constant extra * 练习10.4-5space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.

按正常顺序遍历，然后始终让old比now慢一步。

now, old = root, null
while now != null:
    print(now.key)
    if now is leaf:
        now, old = now.parent, now
    else:
        if old == now.right:
            now, old = now.parent, now
        if old == now.left:
            now, old = now.right, now
        if old == now.parent:
            now, old = now.left, now

练习10.4-6 The left-child, right-sibling representation of an arbitrary rooted tree uses three pointers in each node: left-child, right-sibling, and parent. From any node, its parent can be reached and identified in constant time and all its children can be reached and identified in time linear in the number of children. Show how to use only two pointers and one boolean value in each node so that the parent of a node or all of its children can be reached and identified in time linear in the number of children.

每个结点的布尔值表示该结点是否是最后一个孩子，如果是的话，next指向parent，否则next指向下一个兄弟节点。

思考题

10-1 链表间的比较

                        未排序单链表  已排序单链表  未排序双向链表  已排序双向链表
SEARCH(L, k)                O(n)          O(n)           O(n)             O(n)
INSERT(L, x)                O(1)          O(n)           O(1)             O(n)
DELETE(L, x)                O(n)          O(n)           O(1)             O(1)
SUCCESSOR(L, x)             O(n)          O(1)           O(n)             O(1)
PREDECESSOR(L, x)           O(n)          O(n)           O(n)             O(1)
MINIMUM(L)                  O(n)          O(1)           O(n)             O(1)
MAXIMUM(L)                  O(n)          O(n)           O(n)             O(1)

10-2 利用链表实现可合并堆

For unsorted linked list:
    
    MAKE-HEAP()                      # O(1)
        return MAKE-LINKEd-LIST()

    INSERT(A, x)                     # O(1)
        LIST-INSERT(A, x)

    MINIMUM(A)                       # O(n)
        return LIST-MINIMUM(A)     

    EXTRACT-MIN(A)                   # O(n)
        x = LIST-MINIMUM(A)
        LIST-DELETE(A, x)
        return x

    UNION(A, B)                      # O(n)
        A.last.next = B.first

For sorted linked list:

    MAKE-HEAP()                      # O(1)
        return MAKE-LINKEd-LIST()

    INSERT(A, x)                     # O(n)
        LIST-INSERT(A, x)

    MINIMUM(A)                       # O(1)
        return LIST-MINIMUM(A)     

    EXTRACT-MIN(A)                   # O(1)
        x = LIST-MINIMUM(A)
        LIST-DELETE(A, x)
        return x

    UNION(A, B)                      # O(n), use algorithm like merge.
        A.last.next = B.first

感觉相交和不相交造成不了什么太大区别……或许是我想错了