数据结构与算法基础知识

发表于 分类于
数据结构与算法基础整合，讲解数组、链表、栈、队列、哈希等结构及其 Python 实现，并介绍递归、分治、排序与复杂度优化。

本文整合了数据结构与算法的基础知识体系，包括算法复杂度简介、常见的数据结构（如数组、链表、栈、队列），并提供了 Python 语言的实现与应用示例，最后介绍了一些优化复杂度的方法。

1. 简介

数据结构的存储方式

数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）。

数组 : 紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。由于是连续存储内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)

链表 : 元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题。如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

总结
数组
优点: 构建简单，根据下标（index）查询某个元素的时间复杂度 O(1)
缺点: 必须连续空间，查询元素是否存在要遍历整个数组 O(n), 删除和添加某个元素 O(n)

链表
优点: 灵活分配内存空间，删除，添加元素 O(1) (单链表：前提是前一个元素已知) (双链表：前提是前/后一个元素已知)
缺点: 读取元素要从链表头开始一个一个读取，查询第K 个元素 O(k)

应用场景

需要很多快速查询 : 数组
数据元素个数不确定, 需要经常添加删除 : 链表
数据元素确定，删除插入操作不多 : 数组

python 中的基本数据结构

str 是一种序列， 类似于 tuple

list 和 tuple 两种类型采用了顺序表的实现技术

tuple 是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与 list 的性质类似。

list 是一种采用分离式技术实现的动态顺序表，元素存储区满了就换一块更大的。

不过常见教材里那套”空表先分配 8 个槽位，满了换 4 倍大，超过 50000 这个阈值改为加一倍”只是抽象模型，跟 CPython 的实际行为对不上。CPython 的 list_resize 算的是 new_allocated = newsize + (newsize >> 3) + 6，再向下取整到 4 的倍数，也就是约 1.125 倍的过量分配——没有 4 倍，也没有 50000 这个阈值。空表的容量干脆就是 0：

1
2
import sys
sys.getsizeof([])  # 56, 只有表头, 一个元素槽位都没留

实测容量的变化节点（元素个数, 容量）是 (1,4) (5,8) (9,16) (17,24) (25,32) (33,40) (41,52) (53,64) (65,76)，1.125 的影子在后半段就看得很清楚了。

因子这么小也照样能保证 append 的均摊复杂度是 O(1)：关键在于增长是按比例的，扩容一次搬 n 个元素，换来的是与 n 成正比的一批空槽位，成本摊到这些槽位上就是常数；真正会退化成 O(n²) 的是每次只多给固定几个槽位的线性增长。

dict 和 set 都是通过 hash table 实现的，两者都用开放寻址法。但 set 有自己独立的实现（setobject.c），探测策略和内存布局跟 dict 都不一样——set 是”没有 value 的 dict”只是个方便理解的类比，不是实现上的事实。

特点

  1. dict 自 3.7 起保持插入顺序（3.6 已经是实现细节，3.7 写进语言规范）。它的布局被拆成了两块：一个紧凑的 entries 数组按插入顺序追加 (hash, key, value)，另一个 indices 数组做哈希槽、只存 entries 里的下标。这样哈希表变稀疏时浪费的只是下标数组，键值本身始终紧凑——顺序是这个”紧凑布局”顺手带来的结果。所以”dict 无序”是 3.6 之前的老结论了
  2. 操作的时间复杂度，插入、查找和删除都可以在O(1)的时间复杂度
  3. 键的限制，只有可 hash 的对象才能成为 dict 的 key 和 set 的 value。可 hash 的对象即 python中的不可变对象和自定义的对象。可变对象(list ,set , dict )是不能作为字典的键和set的值的。
  4. dict的内存花销大但是查询速度快。自定义的对象，或者python内部的对象都是dict包装的。（hash简单的来说即映射，映射之后，不可能是连续的存在内存空间中的，总有一些内存时空的，当发现内存空间中的”空” 不足时 ，便会触发扩容操作，以免引起hash冲突）

补充
数组的特点是：寻址容易，插入和删除困难；

而链表的特点是：寻址困难，插入和删除容易。

Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。hash就是找到一种数据内容和数据存放地址之间的映射关系。基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）

一个对象的哈希值如果在其生命周期内绝不改变，就被称为 可哈希 （它需要具有 __hash__() 方法），并可以同其他对象进行比较（它需要具有 __eq__() 方法）。可哈希对象必须具有相同的哈希值比较结果才会相同。

可哈希性使得对象能够作为字典键或集合成员使用，因为这些数据结构要在内部使用哈希值。

2. 基本数据结构

数组

数组将元素以一种不规则的顺序进行排列，在内存中是连续存放。数据可以通过索引值直接取得。

数组只需记录头部的第一个数据位置，然后累加空间位置即可。

数组的操作

新增

  1. 在 数组最后新增一个元素， 对原数据无影响。 插入时间复杂度 O(1)
  2. 在 数组中间某一个位置新增一个元素，会对插入后面的数据产生影响， 后面的元素位置要依次后挪一个位置 。 插入时间复杂度 O(n)

删除
1 .在 数组最后删除一个元素， 对原数据无影响。 删除时间复杂度 O(1)

  1. 在 数组中间某一个位置删除一个元素，会对删除后面的数据产生影响， 后面的元素位置要依次前挪一个位置 。 删除时间复杂度 O(n)

查找

  1. 基于位置，以索引查找 时间复杂度 O(1)
  2. 查找具体数值，eg： 查找元素为 9 是否出现过。 需要遍历 时间复杂度 O(n)

虽然 很多操作被封装， 但时间复杂度不会改变 （因为python 封装的 函数底层可能是 c，所以一般执行效率会高一点）

数组的长度是固定的，申请时就已在内存空间开辟了若干空间，扩容一般 有一定规则扩容

链表可以 用指针充分利用内存空间。数组想从分利用空间只能选择顺序存储，而且不插入删除数据。

线性表

线性表： n 个数据元素的有序排列，最常用的就是 链式表达

链表：存储的数据元素也叫结点，一个结点存储的就是一条数据记录。一般头指针指向第一个结点，最后一个结点的指针因为没有下一个节点，所以是个空指针

结点的结构包括两个部分:

  1. 具体的数据值
  2. 指向下一个结点的指针

单链表: 只能由上一个结点的 指针 指向下一个结点，反过来不行

循环链表: 将单链表的最后一个元素的指针指向第一个元素

双向链表： 新增一个结点的指针，除了有指向下一个元素的指针，也有指向上一个元素的指针

双向循环链表： 双向链表和循环链表 结合，将双向链表最后一个元素的指针指向第一个元素，第一个指针也指向最后一个元素

链表的增删查, p 为 当前结点，b 为下一个结点

  1. 新增：s 为待插入的结点， 只需要将s 的指针 指向 p的目标b ，p的指针指向s
1
2
s.next = p.next(即指向 b)
p.next = s （即指向 b）
  1. 删除： 只需要 将 p 的指针指向 下下个结点 （即b 指向的结点）
1
p.next = p.next.next
  1. 查找： 1.按位置序号来查找 2.按具体的数值查找

查询第 n 个元素： 从头开始，遍历到第 n 个元素

查询值为 x: 从头开始,判断结点的值是否为 x，直到把所有节点遍历完

链表优缺点：

优点: 新增和删除（但也会伴随着查找）

缺点：查找

链表: 数据元素个数不确定, 需要经常添加删除

数组: 数据元素个数确定，删除插入操作不多。 需要以位置查找

栈

栈是一种特殊的线性表，不同的地方体现在增和删操作。栈的数据结点必须后进先出

后进: 栈的数据新增只能在最后一个结点进行

先出: 栈的数据删除也只能在最后一个节点进行

栈降低了操作的灵活性，但处理一端的新增和删除数据的问题效率更高

表尾用来输入数据，通常叫做栈顶 （top）, 表头就是栈底（bottom）

栈的基本操作

  1. 新增：入栈 push

  2. 删除：出栈 pop

栈分为： 顺序栈，链栈

顺序栈：借助数组实现

链栈： 借助链表实现

顺序栈

一般会把数组的首元素存在栈底，最后一个元素放在栈顶，定义一个 top 指针来指示栈顶元素在 数组中的位置。只有一个元素，top =0。 top =-1 表示空栈。如果定义了最大容量 StackSize，则 top 必须小于 StackSize。

  1. 新增： 将元素放在栈顶，top +1
  2. 删除： 删除元素， top - 1
  3. 查找： 类似于线性表

链栈

栈顶放在单链表的头部，不需要头部指针。需要增加指向 栈顶的 top 指针。

  1. 新增： 新结点的指针指向 原栈顶，top指向新的结点
  2. 删除： 将 top 指针指向 顶元素的 next 指针
  3. 查找： 类似于线性表

栈： 限制版的线性表，先进后出，新增删除时间复杂度 O(1)，而查找 时间复杂度 O(n)

队列

队列也是一种特殊的线性表，不同的地方体现在增和删操作。队列的数据结点先进先出

先进: 队列的数据新增只能在最后一个结点进行

先出: 队列的数据删除只能在第一个节点进行

队列分为： 顺序队列，链队列

顺序队列：借助数组实现

链队列： 借助链表实现

一个队列 依赖队头（front） 和 队尾 （rear） 两个指针进行唯一确定

顺序队列

实现一个有 k 个元素的顺序队列，需要建立一个长度 比 k 大的数组，以便把所有的队列元素存储在数组中。

  1. 新增： 利用 rear 指针在队尾新增一个元素 O(1)
  2. 删除： 利用 front 指针删除 下标为 0 的元素，然后队列中所有元素都向前移动一个位置。 O(n) 时间复杂度高
  3. 删除： 通过移动指针的方式删除数据，不移动剩余元素。（会产生数组越界，需要开辟足够大的内存空间保证不会越界）
循环队列

上面的两种删除方法都不太好，可以通过循环队列 解决数据越界问题
（待补充）

链队列

单链表增加 front 和 rear 指针。 front 指针头结点。头结点不存储数据，只用来标识辅助。

  1. 新增： 将新结点 s 设置为队尾结点，然后 rear 指向 s.

  2. 删除： 找到头结点的后继，删除这个后继结点（头结点不存储数据），删除最后一个有效数据后，让rear 也指向头结点。

头结点存在意义： 防止 最后一个有效数据结点删除后， front 和 rear 指针变成野指针。

总结

  1. 循环队列： 可以确定队列长度的最大值

  2. 链式队列： 无法确定队列长度

队列类似于 排队买票场景，可以使用队列来处理相似问题

哈希

哈希表的设计采用了函数映射的思想，将记录的存储位置与记录的关键字关联起来。这样的设计方式，能够快速定位到想要查找的记录，而且不需要与表中存在的记录的关键字比较后再来进行查找

1
2
3
4
5
6
7
张一：155555555

张二：166666666

张三：177777777

张四：188888888

借助哈希表的思路，构建姓名到地址的映射函数“地址 = f (姓名)”。这样，我们就可以通过这个函数直接计算出”张四“的存储位置，在 O(1) 时间复杂度内就可以完成数据的查找

假如对上面的例子采用的 Hash 函数为，姓名的每个字的拼音开头大写字母的 ASCII 码之和。即：

1
2
3
4
5
6
7
address (张一) = ASCII (Z) + ASCII (Y) = 90 + 89 = 179；

address (张二) = ASCII (Z) + ASCII (E) = 90 + 69 = 159；

address (张三) = ASCII (Z) + ASCII (S) = 90 + 83 = 173；

address (张四) = ASCII (Z) + ASCII (S) = 90 + 83 = 173；

我们发现这个哈希函数存在一个非常致命的问题，那就是 f ( 张三) 和 f (张四) 都是 173。这种现象称作哈希冲突，是需要在设计哈希函数时进行规避的

从本质上来看，哈希冲突只能尽可能减少，不能完全避免。这是因为，输入数据的关键字是个开放集合。只要输入的数据量够多、分布够广，就完全有可能发生冲突的情况。因此，哈希表需要设计合理的哈希函数，并且对冲突有一套处理机制。

哈希表查找的细节过程是：对于给定的 key，通过哈希函数计算哈希地址 H (key)。

如果哈希地址对应的值为空，则查找不成功。

反之，则查找成功。

虽然哈希表查找的细节过程还比较麻烦，但因为一些高级语言的黑盒化处理，开发者并不需要实际去开发底层代码，只要调用相关的函数就可以了。

哈希表在我们平时的数据处理操作中有着很多独特的优点，不论哈希表中有多少数据，查找、插入、删除只需要接近常量的时间，即 O(1）的时间级

哈希表中的数据是没有顺序概念的，所以不能以一种固定的方式（比如从小到大）来遍历其中的元素。在数据处理顺序敏感的问题时，选择哈希表并不是个好的处理方法。同时，哈希表中的 key 是不允许重复的，在重复性非常高的数据中，哈希表也不是个好的选择

3. 基本数据结构python

SingleLinkList.py

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
class SingleNode:
    def __init__(self, item):
        self.item = item
        self.next = None

class SingleLinkList:
    def __init__(self):
        self._head = None

    def is_empty(self):
        return self._head == None

    def length(self):
        current = self._head
        count = 0
        while current != None:
            count += 1
            current = current.next
        return count

    def travel(self):
        current = self._head
        while current != None:
            print(current.item)
            current = current.next
        print("")

    def add(self, item):
        node = SingleNode(item)
        node.next = self._head
        self._head = node

    def append(self, item):
        node = SingleNode(item)
        if self.is_empty():
            self._head = node
        else:
            current = self._head
            while current.next != None:
                current = current.next
            current.next = node

    def insert(self, pos, item):
        if pos <=0:
            self.add(item)
        elif pos >(self.length() -1):
            self.append(item)

        else:
            node = SingleNode(item)
            count = 0
            pre = self._head
            while count < (pos-1):
                count += 1
                pre = pre.next
            node.next = pre.next
            pre.next = node

    def search(self,item):
        current = self._head
        while current != None:
            if current.item == item:
                return True
            current = current.next
        return False

    def remove(self, item):
        current = self._head
        pre = None
        while current != None:
            if current.item == item:
                if not pre:
                    self._head = current.next
                else:
                    pre.next = current.next
                break
            else:
                pre = current
                current = current.next



if __name__ == "__main__":
    ll = SingleLinkList()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    print("length:",ll.length())
    ll.travel()
    print(ll.search(3))
    print(ll.search(5))
    ll.remove(1)
    print("length:",ll.length())
    ll.travel()

list_stack.py

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

class Stack(object):
    """栈"""
    def __init__(self):
        self.items = []


    def is_empty(self):
        """判断是否为空"""
        return self.items == []

    def push(self, item):
        """加入元素"""
        self.items.append(item)

    def pop(self):
        """弹出元素"""
        return self.items.pop()  # 别漏了 return, 否则弹出的元素被丢掉, 只拿到 None

    def peek(self):
        """返回栈顶元素"""
        return self.items[len(self.items) - 1]

    def size(self):
        """返回栈的大小"""
        return len(self.items)

if __name__ == "__main__":

    def test():
        print(stack.size())
        print(stack.peek())
        stack.pop()

    stack = Stack()
    stack.push("hello")
    stack.push("world")
    stack.push("itcast")
    test()
    test()
    test()

list_queue.py

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
class Queue(object):
    """队列"""
    def __init__(self):
        self.items = []

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


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

    def dequeue(self):
        return self.items.pop()


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




if __name__ == "__main__":
    def test():
        print(q.size())
        print(q.dequeue())
    q = Queue()
    q.enqueue("hello")
    q.enqueue("world")
    q.enqueue("itcast")
    test()
    test()
    test()

list_Deque.py

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
class Deque(object):
    """双端队列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        """判断队列是否为空"""
        return self.items == []

    def add_front(self, item):
        """在队头添加元素"""
        return self.items.insert(0, item)


    def add_rear(self, item):
        """在队尾添加元素"""
        return self.items.append(item)

    def remove_front(self):
        """从队头删除元素"""
        return self.items.pop(0)


    def remove_rear(self):
        """从队尾删除元素"""
        return self.items.pop()


    def size(self):
        """返回队列大小"""
        return len(self.items)



if __name__ == "__main__":

    deque = Deque()
    print(deque.size())
    print(deque.is_empty())
    deque.add_front(1)
    deque.add_front(2)
    deque.add_rear(3)
    deque.add_rear(4)
    print(deque.size())

    deque.remove_front()
    print(deque.items)
    deque.remove_rear()
    print(deque.items)

4. 一般算法

递归

递归： 把大规模的问题转化为规模小的相同的子问题来解决。递归主体和 一个终止条件

因为大问题 和小问题 的解决方法往往是同一个方法，所以产生函数调用自身的情况。 一个终止条件 （防止产生无限递归）

分治

分治： 把大规模，高难度的问题转化为 若干个小规模，低难度的小问题，最后再将小问题的答案合并

数据有序，预期时间复杂度带有 logn。通过小问题的答案合并原问题的答案。 可以采用分治法

排序

排序： 让一组无序的数据变成有序的过程

排序最暴力的方法， 冒泡排序，选择排序，插入排序 O（n**2）

归并排序 O(nlogn)，需要开辟额外的空间 空间复杂度 O(N)
快速排序 平均 O(nlogn), 最坏的时间复杂度 O(n**2)

动态规划

（待补充）

5. 优化复杂度的方法简介

有关于优化复杂度

时间复杂度 ：与代码的结构有非常强的关系。
经验论：
顺序结构 O(1)
二分查找 O(logn)
for循环 O(n)
顺序for循环 O(n)+O(n) 也是 O(n)
嵌套for循环 O(n^2)

空间复杂度 ： 与代码中的数据结构的选择高度相关

优化的终极目标： 尽可能低的时间复杂度和空间复杂度，去完成一段代码的开发。 一般都 以空间换时间，因为时间是无价的
常见降低时间复杂度方法： 递归，二分，排序算法，动态规划等
降低空间复杂度核心思路： 能用低复杂度的数据结构， 就不用高复杂度的数据结构

日常尽量使用 内置方法，一般是最优的，但面试还是最好用基本数据结构实现

查最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a = [1, 2, 3, 4, 9, 8, 7, 6, 5, 5, 4, 5, 9]

def max_value1():
    max_value = max(a)  # 内置 max() 函数
    print(max_value)


def max_value2():
    max_value = float('-inf')  # float('-inf'), float('inf')  无穷小 与 无穷大
    for i in a:
        if i > max_value:
            max_value = i
    print(max_value)

max_value1()
max_value2()

程序优化的核心思路：

  1. 暴力解法
  2. 剔除无效操作
  3. 时空转换，设计合理数据结构，完成时间复杂度向空间复杂度转移

示例

剔除无效操作

时间复杂度 O(n**3) 降低为 O(n**2)

1,2,5 三种金额组成 100 元，有多少种组合

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
from timeit import Timer

### 暴力解法
def add100_1():
    sum = 0
    for i in range(0, 21):
        for j in range(0, 51):
            for k in range(0, 101):
                if 5*i + 2*j + k == 100:
                    sum += 1

### 剔除无效操作
def add100_2():
    sum = 0
    for i in range(0, 101):
        for j in range(0, 51):
            k = 100 - 1*i - 2*j
            if k == 0:
                sum += 1
            elif k > 0 and k % 5 ==0:
                sum += 1

### 进一步剔除无效操作， 随着 i 的增大， j 的循环次数会变小, 不过时间复杂度不变，扩展一下
def add100_3():
    sum = 0
    for i in range(0, 101):
        for j in range(0, (100 - i)//2 + 1):
            k = 100 - 1*i - 2*j
            if k == 0:
                sum += 1
            elif k > 0 and k % 5 ==0:
                sum += 1



t1 = Timer("add100_1()", "from __main__ import add100_1")
print("add100_1 cost ",t1.timeit(number=1000), "seconds")

t2 = Timer("add100_2()", "from __main__ import add100_2")
print("add100_2 cost ",t2.timeit(number=1000), "seconds")

t3 = Timer("add100_3()", "from __main__ import add100_3")
print("add100_3 cost ",t3.timeit(number=1000), "seconds")
'''
add100_1 cost  10.915886700000101 seconds
add100_2 cost  0.9650682000001325 seconds
add100_3 cost  0.5938704999998663 seconds
'''
时空转换

时间复杂度 O(n**2) 降低为 O(n)

输入数组 a = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7], 查找出现最多的数值， 输出 5。

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
### 嵌套 for 循环  O(n\*\*2)
from timeit import Timer


def test1():
    a = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7]
    max_index = -1
    time_max = 0
    for i in range(len(a)):
        time_tem = 0
        for j in range(len(a)):   # 第二层循环  所有的 元素 与 a[i] 匹配
            if a[i] == a[j]:
                time_tem +=1
        if time_tem > time_max:
            time_max = time_tem
            max_index = a[i]
    return (max_index, time_max)

### 使用字典结构，两个并行的 for 循环 O(n) + O(n) 还是  O(n)
def test2():
    a = [1, 2, 3, 4, 5, 5, 5, 6, 6, 7]
    b = dict()
    for i in range(len(a)):  # 以元素值为 key, 次数为 value 生成字段的 键值对
        if a[i] in b:
            b[a[i]] += 1
        else:
            b[a[i]] = 1
    v_max = 0
    k_max = 0
    for k, v in b.items():  # 查找最大的 value 以及对应的 key
        if v > v_max:
            v_max = v
            k_max = k
    return (k_max, v_max)




t1 = Timer("test1()", "from __main__ import test1")
print("test1 cost ",t1.timeit(number=1000), "seconds")

t2 = Timer("test2()", "from __main__ import test2")
print("test2 cost ",t2.timeit(number=1000), "seconds")

'''
test1 cost  0.012685200000305485 seconds
test2 cost  0.0039678000002822955 seconds
'''