在平坦的算法路上懵逼地曲折前进（二）

说来也怪，我写了许多文章都带了（一），但是好多都没有（二），今天我就寻思着更新一波——在平坦的算法路上懵逼地曲折前进（二）

一、链表

就像个火车

（1）单向链表

class IntNode:
    def __init__(self, i, n):
        self.item = i
        self.next = n
        
class SLList:
    def __init__(self, x=None):
        self.__sentinel = IntNode(1, None)
        if x is None:
            self.__first = None
            self.__size = 0
        else:
            self.__sentinel.next = IntNode(x, None)
            self.__size = 1
        
    def add_first(self, x):
        original_first = self.__sentinel.next
        new_first = IntNode(x,  original_first)
        self.__sentinel.next = new_first
        self.__size += 1
        
    def add_last(self, x):
        p = self.__sentinel
        while p.next is not None:
            p = p.next
            
        p.next = IntNode(x, None)
        self.__size += 1
        
    def get_first(self):
        return self.__sentinel.next.item
    
    def size(self):
        return self.__size
    
l = SLList()
l.add_last(2)
l.get_first()

（2）双向链表

class IntNode:
    def __init__(self, i, n, p):
        self.item = i
        self.next = n
        self.prev = p
class DLList:
    def __init__(self, x=None):
        self.__sentinel = IntNode(1, None, None)
        self.__sentinel.next = self.__sentinel
        self.__sentinel.prev = self.__sentinel
        if x is None:
            self.__size = 0
        else:
            new_node = IntNode(x, self.__sentinel, self.__sentinel)
            self.__sentinel.next = new_node
            self.__sentinel.prev = new_node
            self.__size = 1
    def add_first(self, x):
        original_first = self.__sentinel.next
        new_first = IntNode(x,  original_first, self.__sentinel)
        original_prev = new_first
        self.__sentinel.next = new_first
        self.__size += 1
    def add_last(self, x):
        p = self.__sentinel
        while p.next is not None:
            p = p.next
        p.next = IntNode(x, None,  p.next)    
    def get_first(self):
        return self.__sentinel.next.item
    def size(self):
        return self.__size
l = DLList()
l.add_first(2)
l.add_last(4)

l.get_first()

（3）双守卫环形链表

class Node(object):
    def __init__(self, i, n = None, p = None):
        self.item = i
        self.next = n
        self.prev = p

class DLList():
    def __init__(self, x=None):
        self.__sentinel = Node(1, None, None)
        self.__back_sentinel = Node(1, self.__sentinel, self.__sentinel)
        self.__sentinel.next = self.__back_sentinel
        self.__sentinel.prev = self.__back_sentinel
        if x is not None:
            original_node = self.__sentinel.next
            new_node = Node(x, original_node, self.__back_sentinel)
            self.__sentinel.next = new_node
            self.__back_sentinel.prev = new_node
            self.__size = 1
        else:
            self.__size = 0
            
    def add_first(self, x):
        original_first = self.__sentinel.next
        new_first = Node(x , original_first, self.__sentinel)
        original_first.prev = new_first
        self.__sentinel.next = new_first
        self.__size += 1
        
    def get_first(self):
        return self.__sentinel.next.item
    
    def add_last(self, x):
        original_last = self.__back_sentinel.prev
        new_last = Node(x , original_last, self.__back_sentinel)
        original_last.next = new_last
        self.__back_sentinel.prev = new_last
        self.__size += 1
        
    def get_last(self):
        return self.__back_sentinel.prev.item
    
    def size(self):
        return self.__size
    
l = DLList()
l.add_first(2)
l.add_first(3)
l.add_last(4)

二、抽象数据类型

（1）栈结构

• push(x) 将x放在栈的顶端
• pop() 将栈最上面的元素拿走并取出得到它的值

class Stack():
    def __init__(self):
        self.__data = []
        
    def push(self, x):
        self.__data.append(x)
    
    def pop(self):
        return self.__data.pop()
    
s = Stack()
s.push(1)
s.push(2)
s.pop()

（2）集合

class Set(object):
    def __init__(self, data=[]):
        self.__data = data
        for item in data:
            if item not in self.__data:
                self.__data.append(item)
                
        def add(self, x):
            if x not in self._data:
                self.__data.append(x)
                
        def get_all(self):
            return self.__data

三、渐近分析

• 对于一组已经排好序的array，寻找重复数字

def dup1(A):
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            if A[i] == A[j]:
                return True
    return False

def dup2(A):
    for i in range(len(A) - 1):
        if A[i] == A[i + 1]:
            return True
    return False

operation	sym.count	count, N = 10000
range calls	1	1
len calls	1	1
i assignment	1~N-1	1-9999
equals(==)	1~N-1	1-9999
array accesses	2~2N-2	1-19998

Simplification Summary

• 1. Only consider the worst case
• 2. Pick a representative operation(a.k.a. the cost model).
• 3. Ignore lower order terms.
• 4. Ignore multiplicative constants.

def add(self, x):
        if x not in self._data:
            self.__data.append(x)

operation	#call	worst case	best case
not in	Θ(N)	Θ(N^2)	Θ(N)

class Set(object):
     def init(self, data=[]):
         self.__data = data
         for item in data:
             if item not in self.__data:
                 self.__data.append(item)

operation	#call	worst case	best case
not in	Θ(N)	Θ(N^2)	Θ(N)

下一讲：并查集抽象数据类型、二叉树搜索

Python算法编程

9