栈

栈(stack)是一个项的有序集合，添加项和移除项都发生在同一端，这个端称为“顶”，另一端称为“底”。后添加的项会被首先移除，这种排序原则称为后进先出(LIFO)。

栈操作

  1. stack()：创建一个新的空栈
  2. stack.is_empty()：判断是否为空
  3. stack.push(item)：元素入栈
  4. stack.peek()：元素出栈(不删除栈顶元素)
  5. stack.size()：栈的大小
  6. stack.pop()：元素出栈(删除栈顶元素)

Python实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# python list实现栈
class Stack():
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def peek(self):
        if self.isEmpty():
            return "The stack is empty!"
        else:
            return self.items[-1]

    def size(self):
        return len(self.items)

    def pop(self):
        if self.isEmpty():
            return "The stack is empty!"
        else:
            return self.items.pop()

队列

队列(queue)是一系列有顺序的元素的集合，新元素的加入在队列的“队尾”(rear)，元素的移除发生在队列的“队首”(front)。这种排序原则叫做先进先出(FIFO)。

队列操作

  1. queue.queue()：创建一个空队列
  2. queue.enqueue(item)：添加元素到队尾
  3. queue.dequeue()：从队首移除元素
  4. queue.isEmpty()：判断队列是否为空
  5. queue.size()：队列大小

Python实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# python list实现队列
class Queue():
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        if self.isEmpty():
            return "The queue is empty!"
        else:
            return self.items.pop()

    def size(self):
        return len(self.items)

双端队列

双端队列(deque, double-ended queue)也是一系列元素的有序集合，其两端分别称为队首(front)和队尾(rear)。元素可以从两端插入，也可以从两端删除，兼具栈和队列的所有功能。

双端队列操作

  1. Deque()：创建双端队列
  2. addFront(item)：在队首插入元素
  3. addRear(item)：在队尾插入元素
  4. rmFront()：从队首移除元素
  5. rmRear()：从队尾移除元素
  6. isEmpty()：判断双端队列是否为空
  7. size()：返回双端队列的大小

Python list实现双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Deque():
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addFront(self, item):
        self.items.append(item)

    def addRear(self, item):
        self.items.insert(0, item)

    def rmFront(self):
        if self.isEmpty():
            return "The deque is empty!"
        else:
            return self.items.pop()

    def rmRear(self):
        if self.isEmpty():
            return "The deque is empty!"
        else:
            return self.items.pop(0)

    def size(self):
        return len(self.items)

无序列表

无序列表由一个节点集合组成，每个节点采用显式引用链接到下一个节点。

无序列表操作

  1. unorderedList()
  2. add()
  3. remove()
  4. search()
  5. isEmpty()
  6. size()
  7. append()
  8. index(item)
  9. insert(pos, item)
  10. pop()
  11. pop(pos)
    无序列表实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    # python实现无序列表

    # Node 类
    class Node():
        def __init__(self, element):
            self.data = element
            self.next = None

        def getData(self):
            return self.data

        def getNext(self):
            return self.next

        def setData(self, newelement):
            self.data = newelement

        def setNext(self, newnext):
            self.next = newnext

    # 无序列表类
    class unorderedList():
        # unorderedList要保持对列表头一个节点的引用
        def __init__(self):
            self.head = None
        # 判断无序列是否为空，即列表头是否指向None
        def isEmpty(self):
            return self.head == None
        # 添加add()方法
        def add(self, item):
            newNode = Node(item)
            newNode.setNext(self.head)
            self.head = newNode

        # 添加size()方法，此过程需要遍历无序列表
        def size(self):
            current = self.head
            count = 0
            while current != None:
                count += 1
                current = current.getNext()
            return count

        # 添加search方法
        def search(self, item):
            current = self.head
            found = False
            while current != None and not found:
                if current.getData() == item:
                    found = True
                else:
                    current = current.getNext()
            return found

        # 添加remove()方法
        def remove(self, item):
            if not self.search(item):
                return "The unorderedList don't contain this item!"
            previous = None
            current = self.head
            found = False
            while not found:
                if current.getData() == item:
                    found = True
                else:
                    previous = current
                    current = current.getNext()
            # 要删除的节点为第一个节点
            if previous == None:
                self.head = current.getNext()
            else:
                previous.setNext(current.getNext())

        # 添加append()方法
        def append(self, item):
            newNode = Node(item)
            if self.head == None:
                newNode.setNext(self.head)
                self.head = newNode
            else:
                previous = None
                current = self.head
                while current != None:
                    previous = current
                    current = current.getNext()
                previous.setNext(newNode)

        # 添加index()方法
        def index(self, item):
            current = self.head
            count = -1
            while current != None:
                count += 1
                if current.getData() == item:
                    return count
                current = current.getNext()

        # 添加pop()方法
        def pop(self):
            previous = None
            current = self.head
            while current != None:
                previous = current
                current = current.getNext()
            previous.setNext(None)
            return previous.data

        # 添加insert()方法
        def insert(self, pos, item):
            newNode = Node(item)
            previous = None
            current = self.head
            for i in range(pos):
                previous = current
                current = current.getNext()

            # in case of pos = 0
            if previous == None:
                newNode.setNext(self.head)
                self.head = newNode
            else:
                previous.setNext(newNode)
                newNode.setNext(current)

        # traverse the unorderedList
        def println(self):
            current = self.head
            lists = []
            while current != None:
                lists.append(current.data)
                current = current.getNext()
            print(lists)

有序列表

有序列表中元素是按照从小到大顺序排列的。当我们考虑有序列表时，我们应该可以注意到isEmpty和size方法的实现和无序列表 相同，因为它们只处理列表中节点的数量而不考虑节点的实际值。需要改变的是index，remove，search和add，因为有序列表的有序性，当我们搜索到的节点值大于target时，即表示当前值不存在。

有序列表操作

  1. orderedList()
  2. add()
  3. remove()
  4. search()
  5. isEmpty()
  6. size()
  7. index(item)
  8. pop()
  9. pop(pos)

python实现有序列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
# python实现有序列表

# Node 类
class Node():
    def __init__(self, element):
        self.data = element
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, newelement):
        self.data = newelement

    def setNext(self, newnext):
        self.next = newnext

# 无序列表类
class orderedList():
    # unorderedList要保持对列表头一个节点的引用
    def __init__(self):
        self.head = None
    # 判断链表是否为空，即列表头是否指向None
    def isEmpty(self):
        return self.head == None
    # 添加add()方法
    def add(self, item):
        previous = None
        current = self.head
        stop = False
        while current != None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()
        newNode = Node(item)
        if previous == None:
            newNode.setNext(self.head)
            self.head = newNode
        else:
            newNode.setNext(current)
            previous.setNext(newNode)


    # 添加size()方法，此过程需要遍历链表
    def size(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count

    # 添加search方法
    def search(self, item):
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.getNext()
        return found

    # 添加remove()方法
    def remove(self, item):
        if not self.search(item):
            return "The unorderedList don't contain this item!"
        previous = None
        current = self.head
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        # 要删除的节点为第一个节点
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())


    # 添加index()方法
    def index(self, item):
        current = self.head
        count = -1
        while current != None:
            count += 1
            if current.getData() == item:
                return count
            current = current.getNext()
        return None

    # 添加pop()方法
    def pop(self):
        previous = None
        current = self.head
        while current != None:
            previous = current
            current = current.getNext()
        previous.setNext(None)
        return previous.data

    # 添加insert()方法
    def insert(self, pos, item):
        newNode = Node(item)
        previous = None
        current = self.head
        for i in range(pos):
            previous = current
            current = current.getNext()

        # in case of pos = 0
        if previous == None:
            newNode.setNext(self.head)
            self.head = newNode
        else:
            previous.setNext(newNode)
            newNode.setNext(current)

    # traverse the unorderedList
    def println(self):
        current = self.head
        lists = []
        while current != None:
            lists.append(current.data)
            current = current.getNext()
        print(lists)

链表的分析：
当分析链表方法的复杂度时，我们应该考虑它们是否需要遍历链表。考虑一个有 n 个节点的链 表，isEmpty 方法复杂度是 O（1），因为它只需要检查链表的头指针是否为 None。对于方法 size， 则总需要 n 个步骤，因为除了遍历整个链表以外，没有办法知道链表的节点数。因此，size 方法的复 杂度是 O（n）。无序列表的 add 方法的复杂度是 O（1），因为我们永远只需要在链表的头部简单 地添加一个新的节点。但是，search、remove 和在有序列表中的 add 方法，需要遍历。尽管在平均 情况下，它们可能只需要遍历一半的节点，但这些方法的复杂度都是 O(n)，因为在最糟糕的情况下 需要遍历整个链表。
你可能还注意到，这些方法的实现性能与 Python 的内置列表 list 不同，这表明 Python 中的 list 不是这么实现的。实际上，Python 中的列表的实现是基于数组的。

递归

递归是一种解决问题的方法，它把一个问题分解为越来越小的子问题，直到问题的规模小到 可以被很简单直接解决。而递归函数就是一种调用自身的函数。

递归求和

1
2
3
4
5
6
7
8
9
10
11
# 列表递归求和方法一
def listSum(lst):
    if len(lst) == 1:
        return lst[0]
    else:
        return lst[0] + listSum(lst[1:])

# 列表递归求和方法二
def iterSum(arr):
    head, *tails = arr
    return head + iterSum(tails) if tails else head

递归三大定律

  • 递归算法必须要递归地调用自己
  • 递归算法必须有一个基本结束条件
  • 递归算法必须改变自己的状态并向基本结束条件靠近
    1
    2
    3
    4
    5
    6
    7
    # 递归转换整数到字符串
    def to_str(n, str):
        convert_str = '0123456789ABCDEF'
        if n < base:
            return convert_str[n]
        else:
            return to_str(n//base, base) + convert_str[n%base]
1
2
3
4
5
6
# 写一个函数，接受一个字符串作为参数，并返回一个反向的新字符串。
def reverse(s):
    if len(s) == 1:
        return s
    else:
        return reverse(s[1:]) + s[0]

总结： 递归的逻辑就是利用优美的程序把问题分解为更小更简单的子问题来解决。

谢尔宾斯基三角形

汉诺塔问题

动态规划

搜索

在Python中,有一个非常简单的方法来判别特定项是否在列表中。我们使用in这个运算符。但为了说明这些搜索算法的工作原理以及它们相互比较时的优劣之分，我们还是自己实现这些算法。

无序列表的顺序搜索

1
2
3
4
5
6
7
8
9
def sequentialSearch(alist, item):
    pos = 0
    found = False
    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos += 1
    return found

有序列表的顺序搜索

1
2
3
4
5
6
7
8
9
10
11
12
def orderedSequentialSearch(alist, item):
    pos = 0
    found = False
    stop = False
    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        elif alist[pos] > item:
            stop = True
        else:
            pos += 1
    return found

二分法搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 二分法搜索返回True或False
def binarySearch(alist, item):
    head  = 0
    tail = len(alist) - 1
    found = False
    while head <= tail and not found:
        mid = (head + tail)//2
        if alist[mid] == item:
            found = True
        elif alist[mid] < item:
            head = mid + 1
        else:
            tail = mid - 1
    return found
1
2
3
4
5
6
7
8
9
10
11
12
13
# 二分法搜索返回index
def binarySearch2(alist, item):
    head = 0
    tail = len(alist) - 1
    while head <= tail:
        mid = (head + tail)//2
        if alist[mid] == item:
            return mid
        elif alist[mid] < item:
            head = mid + 1
        else:
            tail = mid - 1
    return "The item '{}' is not found!".format(item)
1
2
3
4
5
6
7
8
9
10
11
12
# 二分法递归搜索，返回True或False
def binarySearch3(alist, item):
    if len(alist) == 0:
        return "The item '{}' is not found!".format(item)
    else:
        mid = len(alist)//2
        if alist[mid] == item:
            return True
        elif alist[mid] < item:
            return binarySearch3(alist[mid+1:], item)
        else:
            return binarySearch3(alist[:mid], item)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 二分法递归搜索，返回index
def binarySearch3(alist, item, head, tail):
    '''
    因为返回值是index，所以每次递归传回的列表必须是原列表，
    这样才能保证index是在原列表中的index，而不是每次递归
    缩小的列表的index
    '''
    if head > tail:
        return "The item '{}' is not found!".format(item)
    else:
        mid = (head + tail)//2
        if alist[mid] == item:
            return True
        elif alist[mid] < item:
            return binarySearch3(alist, item, mid+1, tail)
        else:
            return binarySearch3(alist, item, head, mid-1)

散列表

散列表是一种数据的集合，其中的每个数据都通过某种特定的方式进行存储以方面日后的查找。基于它的搜索算法的时间复杂度为O(1)。散列表的每一个位置叫做槽，能够存放一个数据项，并以从0开始递增的整数命名。例如， 第一个槽记为0，下一个记为1，再下一个记为2，并以此类推。在初始条件下，散列表中是没有任何数据的，即每个槽都是空的。某个数据项与在散列表中存储它的槽之间的映射叫做散列函数。一般地，我们把槽被占据的比例叫做负载因子，两个甚至多个数据需要存储在同一个槽中，这种情况被称为冲突。

散列函数

对于一组给定的数据项，如果一个散列函数可以将每一个数据项都映射到不同的槽中，那么这样的散列函数叫做完美散列函数。一种实现完美散列函数的方法就是扩大散列表的尺寸，直到所有可能的数据项变化范围都被散列表所包含。这一方法保证了每一个数据项都有一个不同的槽。尽管这个方法对于少量数据是可行的，但是当它面对大量可能的数据项时显得捉襟见肘。
我们的目标是创建一个能够将冲突的数量降到最小，计算方便，并且最终将数据项分配到散 列表中的散列函数。有几种普通的方法去扩展求余方法：

  • 折叠法：首先将数据分成相同长度的片段（最后一个片段长度可能不等）。接着将这些片段相加，再求余得到其散列值。
  • 平方取中法：我们首先将数据取平方，然后取平方数的某一部分，然后再进行求余运算。
    我们也可以为非数字的数据项，例如字符串创建散列表，’cat’可以看做一个连续的ASCII数值。
    1
    2
    3
    4
    5
    6
    # 用ASCII数值散列一个字符串
    def hash(astring, tablesize):
        sum = 0
        for i in range(len(astring)):
            sum = sum + ord(astring[i])
        return sum%tablesize

当我们用散列函数纪录散列值的时候，颠倒的字母构成的单词会得到相同的散列值。为了纠正这一情况，我们可以将字母的位置作为权重因子。

1
2
3
4
5
6
# 用ASCII数值*权重散列一个字符串
def hash(astring, tablesize):
    sum = 0
    for i in range(len(astring)):
        sum = sum + ord(astring[i])*(i+1)
    return sum%tablesize

冲突

当两个数据散列到相同的槽，我们必须用一种系统化的方法将第二个数据放到散列表里。这个过程叫做冲突解决。

  • 一种解决冲突的方法就是搜索散列表并寻找另一个空的槽来存放这个有冲突的数据。一种简单的方法就是从发生冲突的位置开始顺序向下开始寻找，直到我们遇到第一个空的槽。注意到我们可能需要回到第一个槽（循环）来实现覆盖整个散列表。这种冲突解决方法叫做开放地址，它试图在散列表中去寻找下一个空的槽。通过系统地向后搜索每一个槽，我们将这种实现开放地址的技术叫做线性探测。
  • 线性探测法的一个缺点是产生集中的趋势：数据会在表中聚集。这意味着如果对于同一散列值产生了许多冲突时，周边的一系列槽都将会被线性探测填充。这将会对正在被填入的新数据产生影响。一种解决集中问题的方法是扩展线性探测技术，我们不再按顺序一个一个地寻找新槽，而是跳过一些槽，这样能更加平均地分配出现冲突的数据，进而潜在地减少集中问题出现的次数。下图展示了同样的数据项如何通过“+3”线性探测的方法解决冲突的。“+3”表示一旦一个冲突出现，我们将每次跳过两个槽来寻找下一个新的空槽。
  • 另一种线性探测方法叫做二次探测法。我们不是每次在冲突中选择跳过固定个数的槽，而是使用一个再散列函数使每次跳过槽的数量会依次增加1,3,5,7,9，以此类推。这意味着如果原槽为第h个，那么再散列时访问的槽为第h+1，h+4，h+9，h+16个，以此类推。换言之，二次探测法使用一个连续的完全平方数数列作为它的跳跃值。图11显示了我们的例子在运用二次探测法时的 填充结果。
  • 另一个解决冲突的替代方法是允许每一个槽都能填充一串而不是一个数据（称作链）。链能允许多个数据填在散列表中的同一个位置上。当冲突发生时，数据还是填在本应该位于的槽中。 随着一个槽中填入的数据的增多，搜索的难度也就随之增加。下图显示了数据在用数据链方法填入散列表的结果。

实现映射的抽象数据类型

字典是Python中最有用的数据类型之一。字典是一个可以储存键-值对的关联数据类型。键是用来查找和它相关联的值的。通常把这个想法称作映射。映射的抽象数据类型定义如下：它以一个键与一个值之间关联的无序集合作为结构。映射中的键都是独特的，以保证和值之间的一一对应关系。

映射的相关操作：

  1. Map():产生一个新的空映射
  2. put():往映射中添加键-值对。如果密钥已经存在，那么将旧的数据值置换为新的。
  3. get(key):给定一个 key 值，返回关联的数据，若不存在，返回None。
  4. del:从映射中删除一个密钥-数据值对，声明形式为del map[key]。
  5. len():返回映射中的存储密钥-数据值对的个数。
  6. in:表述为key in map，如果给定的键在map中返回True，否则返回False。

python实现映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# 创建哈希表类
class Hashtable():
    def __init__(self):
        self.size = 11
        # 定义两个列表分别存储键和值
        self.slots = [None]*self.size
        self.data = [None]*self.size

    # 定义put()方法
    def put(self, key, data):
        hashvalue = self.hashFunc(key, len(self.slots)) # hashvalue为计算出的一个整数，此处相当于列表的下标
        if  self.slots[hashvalue] == None: # 创建新的键值对
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        else:
            if self.slots[hashvalue] == key: # 该键的位置没有被rehash过，重新赋予键新值
                print('***', hashvalue, self.slots[hashvalue], key)
                self.data[hashvalue] = data
            else: # 该键的位置被rehash过，重新赋予键新值
                nextslot = self.rehash(hashvalue, len(self.slots))
                while self.slots[nextslot] != None and self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot, len(self.slots))
                if self.slots[nextslot] == None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = data
                else:
                    self.data[nextslot] = data

    # 定义hashFunc()方法
    def hashFunc(self, key, size):
        return key%size

    # 定义rehash()方法
    def rehash(self, oldvalue, size):
        return (oldvalue + 1)%size

    # 定义get()方法
    def get(self, key):
        initslot = self.hashFunc(key, len(self.slots))
        data = None
        stop = False
        found = False
        pos = initslot
        while self.slots[pos] != None and not found and not stop:
            if self.slots[pos] == key:
                found = True
                data = self.data[pos]
            else:
                pos = self.rehash(pos, len(self.slots))
                if pos == initslot: # 循环到开始处，表示没有搜索到
                    stop = True
        return data

    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, data):
        self.put(key, data)

持续更新中…