简介

数据结构：线性结构和非线性结构，用来存储数据的方式

算法：就是解决问题的思路和方法，要有设计出好的数据结构才能更好用算法

特性：有输入、有输出、有穷性、确定性、可行性

时间复杂度

表示随着问题规模不断变化的主要趋势，衡量算法的优劣

大O标记法：将次要条件省掉，最终形成一个表达式

比如说：嵌套的3次for循环，最里面是if什么的，再打印，只看最外的3次循环，都是

1
2
n*n*n
时间复杂度T(n)=O(n^3)
1
2
3
for i in range(0,5):    O(1)                              如果是0，n       O(n)
  for j in range(0,n):  O(n)
    print(i)            O(1)* O(n)= O(n)                  最终就  O(n^2)

时间复杂度取最高次项，即最坏的复杂度

最优时间复杂度指的算法完成工作最少需要多少基本操作

1
2
3
4
5
6
7
| 执行次数函数举例    | 阶       | 非正式术语 |
|------------------|----------|------------|
| 12               | O(1)     | 常数阶     |
| 2n+3             | O(n)     | 线性阶     |
| 3n²+2n+1         | O(n²)    | 平方阶     |
| 5log₂n+20        | O(logn)  | 对数阶     |
| 6n³+2n²+3n+4     | O(n³)    | 立方阶     |

所消耗的时间从小到大:

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³)

时间复杂度越低，效率越高 O(1) 最高

备注：
O(logn)：二分法
O(nlogn)：一个for循环是n 另外一个for循环是二分法，组合在一起

空间复杂度

空间复杂度（S(n)）对算法在运行过程中临时占用存储空间大小，也可以用大O记法

O(1) < O(logn) < O(n) < O(n²) < O(n³)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for i in range(0, n):
    a = i                       # 这里的a一直被覆盖，没有开辟新的空间，所以空间复杂度:  O(1)
    print(a)

# 如果是列表，新增插入一直再开空间     空间复杂度: O(n)
list=[]
for i in range(1,n):
    list.append(i)

# 下面空间复杂度: O(n²)  矩阵  [[],[]]
list_1 = []
for i in range(0, n):
    list_2 = []
    for j in range(0, n):
        list_2.append(j)
    list_1.append(list_2)

存储结构

内存以字节为基本存储单位，每个存储空间有自己的地址，一个地址代表1个字节8bit

整形 4个字节 如10 占用4个字节 字符串1个

数据结构分类:

（1）线性结构 一个父节点 ，1个子节点

  • 顺序表 (栈, 队列) 适合查（时间复杂度O（1））和改

    一站式存储（列表同一类型） 数据区、信息区

    分离式存储（列表不同类型）

    链表 适合 增和删 没有索引 由节点组成，其中节点由 元素域（数值域） 和 地址域组成

    单向链表：节点由1个数值域和1个地址域组成，前边节点的地址域存储后续节点的地址，最后一个地址域为None

      自定义代码模拟链表

（2）非线性结构

  • 树
  • 图
  • …

1. 顺序表中如何增加元素？

  • a. 尾端加入元素，时间复杂度为 O(1)
  • b. 非保序的加入元素（不常见），时间复杂度为 O(1)
  • c. 保序的元素加入，时间复杂度为 O(n)

2. 顺序表中如何删除元素？

  • a. 删除表尾元素，时间复杂度为 O(1)
  • b. 非保序的元素删除（不常见），时间复杂度为 O(1)
  • c. 保序的元素删除，时间复杂度为 O(n)

自定义代码模拟链表，思路分析：

  1. 自定义 SingleNode 类，表示 节点类。
    • 属性：
      • item：数值域（元素域）
      • next：地址域（链接域）
  2. 自定义 SingleLinkedList 类，表示：链表
    • 属性：
      • head：表示头结点，指向第 1 个节点。
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
class SingleNode:
    """单链表的节点类"""
    def __init__(self, item):
        # 数值域：保存数据元素
        self.item = item
        # 地址域：指向下一个节点的引用，初始化为 None
        self.next = None


class SingleLinkedList:
    """单向链表类"""
    def __init__(self,node=None):
        # 头结点属性：初始时链表为空，head 指向 None
        self.head = node

    def is_empty(self):
        """判断头节点是否为空"""
        return self.head is None

    def length(self):
        """获取链表长度"""
        # cur 是游标（指针），用来遍历链表
        cur = self.head
        count = 0
        while cur is not None:
            count += 1
            # 将游标移动到下一个节点
            cur = cur.next
        return count

    def travel(self):
        """遍历整个链表并打印元素"""
        cur = self.head
        while cur is not None:
            print(cur.item, end=" ")
            cur = cur.next
        print("")  # 换行

    def add(self, item):
        """在链表头部添加元素 (头插法)"""
        node = SingleNode(item)
        # 1. 新节点的 next 指向原来的头结点
        node.next = self.head
        # 2. 将链表的 head 指向新节点
        self.head = node

    def append(self, item):
        """在链表尾部添加元素 (尾插法)"""
        node = SingleNode(item)
        # 如果链表为空，直接将 head 指向新节点
        if self.is_empty():
            self.head = node
        else:
            cur = self.head
            # 移动到链表的最后一个节点
            while cur.next is not None:
                cur = cur.next
            # 将最后一个节点的 next 指向新节点
            cur.next = node

    def insert(self, pos, item):
        """在指定位置 pos 添加元素"""
        # 如果指定位置在第一个位置之前，执行头部插入
        if pos <= 0:
            self.add(item)
        # 如果指定位置超过链表长度，执行尾部插入
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = SingleNode(item)
            count = 0
            pre = self.head
            # 移动到 pos 位置的前一个节点
            while count < (pos - 1):
                count += 1
                pre = pre.next
            # 1. 新节点指向 pos 位置的节点
            node.next = pre.next
            # 2. 前一个节点指向新节点
            pre.next = node

    def remove(self, item):
        """删除节点"""
        cur = self.head
        pre = None
        while cur is not None:
            # 找到了要删除的元素
            if cur.item == item:
                # 如果要删除的是头结点
                if cur == self.head:
                    self.head = cur.next
                else:
                    # 将前一个节点的 next 指向当前节点的下一个节点
                    pre.next = cur.next
                break
            else:
                # 继续向后遍历
                pre = cur
                cur = cur.next

    def search(self, item):
        """查找节点是否存在，存在返回 True，否则返回 False"""
        cur = self.head
        while cur is not None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

# --- 测试代码 ---
if __name__ == "__main__":
    # 测试节点创建
    node1 = SingleNode(10)
    print(f'节点1的数值域: {node1.item}')
    print(f'节点1的地址域: {node1.next}')
    print(f'node1对象: {node1}')
    print(f'node1类型: {type(node1)}')
    # 测试链表创建
    my_linkedlist = SingleLinkedList(node1)
    print(f'头节点为: {my_linkedlist.head}')
    print(f'头节点元素域: {my_linkedlist.head.item}')
    print(f'头节点地址域: {my_linkedlist.head.next}')

    node2 = SingleNode('赵云')
    single_linkedlist = SingleLinkedList(node2)
    print(single_linkedlist.is_empty())
    print(single_linkedlist.length())
    single_linkedlist.travel()

递归

即函数自己调用自己

核心要点：

1、必须有出口，否则造成死递归

2、调用次数不能过多，否则容易死递归

3、递归必须有规律

1
2
3
4
5
6
7
8
#阶层
def show(n):
  # 递归出口
  if n == 1:
    return 1
  # 递归规律
  return n * show(n-1)
print(show(5))

算法

排序算法：按照其中某个关键字的大小，递增或递减的排列起来操作

稳定性算法：相同元素的 相对位置 不改变

  • 不稳定的排序算法： 选择排序、快速排序、希尔排序、堆排序
  • 稳定的排序算法： 冒泡排序、插入排序、归并排序和基数排序

冒泡排序

相邻两两比较，前面的比后面大就交换

比如：5个人身高排序，第一轮两两比较就能知道最高的，第二轮，第二高，4轮就能排完

名字由来：最小元素会慢慢交换浮到数列的顶端。如二氧化碳的气泡

[5,3,4,7,2]

1、比较的总轮数 2、每轮比较的总次数 3、谁和谁比较

原理

相邻元素两两比较，大的往后走，这样第一轮比较完毕后，最大值就在最大索引处。重复此动作，直至排序完成。

流程（假设共 5 个元素）

第几轮(索引) 该轮比较的总次数 公式
第1轮(0) 4次 5−1−0=4
第2轮(1) 3次 5−1−1=3
第3轮(2) 2次 5−1−2=2
第4轮(3) 1次 5−1−3=1

要点

  1. 比较的总轮数：列表长度 - 1
  2. 每轮比较的总次数：列表长度 - 1 - 轮数的索引(从0开始)
  3. 谁和谁比较：索引 j 和 j + 1 位置的元素比较

时间复杂度

  • 最优：O(n)
  • 最坏：O(n²)

扩展

  • 外循环-1：减少比较次数、提高效率
  • 内循环-1：为了防止索引越界 内循环 -i：减少每轮的比较次数，提高效率

冒泡排序 = 稳定 排序算法 比如[3,2,7,6,6] 6 7 6 | 6 6 7 发现 6 6 的相对位置没有变化就是稳定的

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
# 默认版本
def dubble_sort(list):
    """冒泡排序"""
    for i in range(len(list) - 1):   #外循环，控制排序的轮数
        for j in range(len(list) - 1 - i):   #内循环，控制每轮排序的比较次数
            if list[j] > list[j + 1]:
                list[j], list[j + 1] = list[j + 1], list[j]

# 优化版本
def dubble_sort_optimize(list):
    """冒泡排序"""
    count=0
    for i in range(len(list) - 1):   #外循环，控制排序的轮数
        for j in range(len(list) - 1 - i):   #内循环，控制每轮排序的比较次数
            if list[j] > list[j + 1]:
                count+=1
                list[j], list[j + 1] = list[j + 1], list[j]
        print(f"第{i+1}轮数，交换次数为{count}")
        if count==0: # 如果某一轮没有交换，说明已经有序，直接跳出循环
            print("已经有序")
            break
if __name__ == "__main__":
    list = [5, 3, 4, 7, 2]
    list1=[1,2,3,4,5]
    dubble_sort_optimize(list1)
    print(list)

选择排序

不稳定 排序算法 5 3 5 7 2 第一轮交换2 3 5 7 5 本来是前5，交换后变后5，位置变化了，所以不稳定

待排序的数据元素中选最小或最大的一个元素，放序列的起始位置

  • 最优：O(n²)
  • 最坏：O(n²)

要点：

  1. 比较的总轮数。n - 1
  2. 每轮比较的总次数。i+1, n
  3. 谁和谁比较(交换)。i 和 min_index

第1轮(索引:0) 0 和 1,2,3,4比较 共4次
第2轮(索引:1) 1 和 2,3,4比较 共3次
第3轮(索引:2) 2 和 3,4比较 共2次
第4轮(索引:3) 3 和 4比较 共1次

[5, 3, 4, 7, 2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def selection_sort(arr):
    n = len(arr)
    for i in range(0,n-1):
      min_idx = i
      for j in range(i+1,n):
        if arr[j] < arr[min_idx]:
          min_idx = j
      if min_idx != i:
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

if __name__ == '__main__':
    arr = [5, 3, 4, 7, 2]
    print(selection_sort(arr))

插入排序

将一个数据插入到已经排好序的有序数据

默认第一个是有序的，其他默认无序

稳定排序

第几轮(索引) 该轮比较的总次数 公式(具体的谁和谁比较)
第1轮(1)： 1次 索引1和 0比较
第2轮(2)： 2次 索引2和1， 2和0比较
第3轮(3)： 3次 索引3和2， 3和1， 3和0比较
第4轮(4)： 4次 索引4和3， 4和2， 4和1， 4和0比较

时间复杂度

  • 最优：O(n)
  • 最坏：O(n²)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def insertion_sort(arr):
    n = len(arr)
    for i in range(1,n):     # i的值 1    2     3          4
      for j in range(i,0,-1):# j的值 1   2,1  3,2,1      4,3,2,1  包左不包右
        if arr[j] < arr[j-1]:
          arr[j], arr[j-1] = arr[j-1], arr[j]
        else:
          # 如果当前元素大于等于前一个元素，说明已经有序，不需要交换
          break
    return arr

if __name__ == '__main__':
    arr = [5, 3, 4, 7, 2]
    print(insertion_sort(arr))

快速排序

首先设置一个分界值，将数组分为左右两边

大于或等于的放分界值右边，小于的放左边

时间复杂度

  • 最优：O(nlogn)
  • 最坏：O(n²)
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
def quick_sort(arr, start, end):
    """
    快速排序
    :param arr: 待排序数组
    :param start: 起始索引 0
    :param end: 结束索引 len(arr)-1
    :return: 排序后的数组
    """
    if start >= end:
        return
    left = start
    right = end
    # 定义遍历mid: 假设列表起始值为分界值
    mid = arr[start]

    while left < right:
        # 把分界值右边比分界值小的元素放到左边
        while left < right and arr[right] >= mid:
            right -= 1
        arr[left]=arr[right]

        while left < right and arr[left] < mid:
            left += 1
        #说明arry[left]大于或等于mid，需要放到右边
        arr[right]=arr[left]
        #中介值放到正确位置
        arr[left]=mid

        #递归处理左边子数组
        quick_sort(arr, start, left-1)
        #递归处理右边子数组
        quick_sort(arr, left+1, end)

if __name__ == '__main__':

    my_list = [3, 2,  4, 1,5, 6, 7,  9, 8]
    quick_sort(my_list, 0, len(my_list)-1)
    print(my_list)

二分查找

属于查找类算法，相对效率比较高，时间复杂度 O(logn)

原理： 假设列表是升序 0 1 3 5 7 9 10

1、比较要查找的元素和列表的中值，如果一样就返回True，程序结束

2、如果要查找的元素比中值小，去前半段（中值前）查找

3、如果 要查找的元素 比中值大，去后半段（中值后）查找

4、重复上面操作，直到找完，如果找完了还是没有，就返回False

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
def binary_search_recursive(my_list, target):
  """
  二分查找递归版
  :param my_list: 有序列表
  :param target: 目标值
  :return: True在列表中/False不在
  """
  n = len(my_list)
  if n == 0:
    return False
  mid = n // 2
  if my_list[mid] == target:
    return True
  elif my_list[mid] > target:
    # 目标值在左半部分
    # 递归调用二分查找函数，传入左半部分的列表
    return binary_search_recursive(my_list[:mid], target)
  else:
    # 目标值在右半部分
    # 递归调用二分查找函数，传入右半部分的列表
    return binary_search_recursive(my_list[mid+1:], target)

def binary_search(my_list, target):
  """
  二分查找非递归版 定义start,end指针分别指向列表首尾索引
  :param my_list: 有序列表
  :param target: 目标值
  :return: True在列表中/False不在
  """
  start = 0
  end = len(my_list) - 1
  while start <= end:
    mid = (start + end) // 2
    # 比较 要查找的元素 和 中值
    if my_list[mid] == target:
      return True
    elif my_list[mid] > target:
      # 目标值在左半部分
      end = mid - 1
    else:
      # 目标值在右半部分
      start = mid + 1
  # 目标值不在列表中
  return False

if __name__ == '__main__':
    # 测试用例
    my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    print(binary_search(my_list, 6))

树

非线性结构

  • 节点的度：一个节点含有的子节点的个数称为该节点的度
  • 树的度：一棵树中，最大的节点的度称为树的度
  • 叶节点或终端节点：度为零的节点
  • 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
  • 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点
  • 兄弟节点：具有相同父节点的节点互称为兄弟节点
  • 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
  • 树的高度或深度：树中节点的最大层次
  • 堂兄弟节点：父节点在同一层的节点互为堂兄弟
  • 节点的祖先：从根到该节点所经分支上的所有节点
  • 子孙：以某节点为根的子树中任一节点都称为该节点的子孙
  • 森林：由m（m>=0）棵互不相交的树的集合称为森林

分类：

有序树：

无序树：

二叉树：

完全二叉树：最后一层不满，其他都是满

非完全二叉树：中间有断的

满二叉树：全满

平衡二叉树：任意节点的两个子树高度不超过1

广度优先遍历算法：一层一层按顺序

深度优先遍历：中序（中序遍历 左根右）、先序（前序遍历 根左右）、后序（后序遍历 左右根）

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
139
class Node:
  #节点包含元素域，以及左右子节点的指针
  def __init__(self, item):
    self.item = item
    self.left = None
    self.right = None

class BinaryTree:
  def __init__(self,node=None):
    self.root = node

  def add(self,item):
    new_node = Node(item)
    if self.root is None:
      self.root = new_node
      return
    #创建队列
    queue=[]
    queue.append(self.root)
    while True:
      node=queue.pop(0)
      #判断node是否有左右子节点
      if node.left is None:
        node.left=new_node
        return
      else:
        queue.append(node.left)
      if node.right is None:
        node.right=new_node
        return
      else:
        queue.append(node.right)

  def breadth_travel(self):
    if self.root is None:
      return
    queue=[]
    queue.append(self.root)
    while len(queue)>0:
      node=queue.pop(0)
      print(node.item,end=' ')
      # 判断node是否有左右子节点
      if node.left is not None:
        queue.append(node.left)
      if node.right is not None:
        queue.append(node.right)

  # 前序遍历 根左右
  def preorder(self,root):
    if root is None:
      return
    print(root.item,end=' ')
    self.preorder(root.left)
    self.preorder(root.right)

  # 中序遍历 左根右
  def inorder(self,root):
    if root is None:
      return
    self.inorder(root.left)
    print(root.item,end=' ')
    self.inorder(root.right)

  # 后序遍历 左右根
  def postorder(self,root):
    if root is None:
      return
    self.postorder(root.left)
    self.postorder(root.right)
    print(root.item,end=' ')

#测试函数
def demo_binary_tree():
  node1 = Node("A")
  print(node1.item)
  print(node1.left)
  print(node1.right)
  print('-'*20)
  bt=BinaryTree(node1)
  print(bt.root.item)

def demo_binary_tree2():
  #二叉树如下： 广度优先遍历结果A B C D E F G H I J ，一层一层遍历
  #      a
  #    b         c
  #  d    e    f    g
  #h  i j
  # 队列那种，先进先出，第一个A，然后去查左右子节点，有就入队，再pop[0]将A出队，
  # 继续判断B是否有左右子节点，有就入队，再pop[0]将B出队，
  # 继续判断C是否有左右子节点，有就入队，再pop[0]将C出队....
    bt=BinaryTree()
    bt.add("A")
    bt.add("B")
    bt.add("C")
    bt.add("D")
    bt.add("E")
    bt.add("F")
    bt.add("G")
    bt.add("H")
    bt.add("I")
    bt.add("J")
    bt.breadth_travel()

def demo_binary_tree3():
  #树结构如下
  #      0
  #    1         2
  #  3    4    5    6
  #7  8 9
  #先序遍历结果：0 1 3 7 8 4 9 2 5 6   根左右
  #中序遍历结果：7 3 8 1 9 4 0 5 2 6   左根右
  #后序遍历结果：7 8 3 9 4 1 5 6 2 0   左右根

    bt=BinaryTree()
    bt.add(0)
    bt.add(1)
    bt.add(2)
    bt.add(3)
    bt.add(4)
    bt.add(5)
    bt.add(6)
    bt.add(7)
    bt.add(8)
    bt.add(9)
    print('先序 根左右：',end=' ')
    bt.preorder(bt.root)
    print('-'*20)
    print('中序 左根右：',end=' ')
    bt.inorder(bt.root)
    print('-'*20)
    print('后序 左右根：',end=' ')
    bt.postorder(bt.root)
    print()

if __name__ == '__main__':
    # 测试用例
    # demo_binary_tree()
    # demo_binary_tree2()
    demo_binary_tree3()

二叉树遍历结果反推 二叉树结构

先序遍历结果：0 1 3 7 8 4 9 2 5 6 根左右
中序遍历结果：7 3 8 1 9 4 0 5 2 6 左根右

通过先序，确定根是0，再根据中序，0的位置，切分为左右树