数据结构与算法基础知识

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

1. 简介

数据结构的存储方式

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

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

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

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

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

应用场景

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

python 中的基本数据结构

str 是一种序列，类似于 tuple

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

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

list 是一种采用分离式技术实现的动态顺序表,建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大（目前的阀值为50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。

dict 和 set 都是通过 hash table 来实现的键值对数据结构, 实现上 set 是带空值相同的 dict。

特点

dict 中的数据是无序存放的
操作的时间复杂度，插入、查找和删除都可以在O(1)的时间复杂度
键的限制，只有可 hash 的对象才能成为 dict 的 key 和 set 的 value。可 hash 的对象即 python中的不可变对象和自定义的对象。可变对象(lits ,set , dict )是不能作为字典的键和st的值的。
dict的内存花销大但是查询速度快。自定义的对象，或者python内部的对象都是dict包装的。（hash简单的来说即映射，映射之后，不可能是连续的存在内存空间中的，总有一些内存时空的，当发现内存空间中的”空” 不足时，便会触发扩容操作，以免引起hash冲突）

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

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

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

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

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

2. 基本数据结构

数组

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

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

数组的操作

新增

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

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

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

查找

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

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

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

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

线性表

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

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

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

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

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

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

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

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

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

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

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

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

链表优缺点：

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

缺点：查找

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

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

栈

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

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

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

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

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

栈的基本操作

新增：入栈 push
删除：出栈 pop

栈分为：顺序栈，链栈

顺序栈：借助数组实现

链栈：借助链表实现

顺序栈

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

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

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

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

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

队列

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

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

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

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

顺序队列：借助数组实现

链队列：借助链表实现

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

顺序队列

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

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

越界：

循环队列

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

链队列

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

新增：将新结点 s 设置为队尾结点，然后 rear 指向 s.
删除：找到头结点的后继，删除这个后继结点（头结点不存储数据），删除最后一个有效数据后，让rear 也指向头结点。

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

总结

循环队列：可以确定队列长度的最大值
链式队列：无法确定队列长度

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

哈希

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

张一：155555555

张二：166666666

张三：177777777

张四：188888888

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

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

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

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


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):
        """弹出元素"""
        self.items.pop()

    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

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

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)

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

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

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

查最大值

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)

test1()
test2()

程序优化的核心思路：

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

示例

剔除无效操作

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

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

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。

### 嵌套 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
'''