第10章-基础数据结构

动态集合上的操作： - SEARCH(S, k)：查询， - INSERT(S, x)：插入 - DELETE(S, x)：删除 - MINMUM(S)：查询最小元素的指针 - MAXMUM(S)：查询最大元素的指针 - PREDECESSOR(S, x)：查询x前一个元素的指针

栈和队列

• 栈：假设用\(S[1,2,3,...n]\)表示一个可容纳n个元素的栈

  • 先进后出（FILO）

  • 插入操作称作：PUSH, 删除操作称作POP

    def STRACK_EMPTY(S):
        if S.top == 0:
            return True
        else:
            return False
        
    def PUSH(S, x):
        if S.top == n:
            raise "栈上溢（overflow）"
        S.top++
        S[S.top] = x
    
    def POP(S):
        if STRACK_EMPTY(S):
            raise "栈下溢(underflow)"
        else:
        	S.top--
        return S[S.top+1]

• 队列：

  • 先进先出（FIFO）

  • 插入操作称作：ENQUEUE，删除称作：DEQUEUE

    def ENQUEUE(Q, x):
        Q[Q.tail] = x
        if Q.tail == Q.length:
            Q.tail = 1
        else:
            Q.tail++
            
     def DEQUEUE(Q):
        x = Q[Q.head]
        if Q.head == Q.length:
            Q.head = 1
        else:
            Q.head++
        return x

链表

与数组不同的是，链表的顺序是由各个对象里的指针决定的。

# 搜索

def LIST_SEARCH(L, k):
    x = L.head
    while x != None && x.key != k:
        x = x.next
    return x

指针和对象的实现

有根树的表示

练习

思考题