1.数据结构和算法简介
-
程序
可以理解为：程序 = 数据结构 + 算法
-
概述/目的:
都可以提高程序的效率(性能) -
数据结构
指的是 存储, 组织数据的方式.
-
算法
指的是 为了解决实际业务问题而思考 思路和方法, 就叫: 算法.
2.算法的5大特性介绍
-
概述:
为了解决实际业务问题, 而考虑出来的方法和思路, 就叫: 算法.
算法具有独立性, 即: 它是解决问题的思路(思想)和方法, 不依赖于语言 -
5大特性
- 有输入, 需要传入1或者多个参数
- 有输出, 需要返回1个或者多个结果
- 有穷性, 执行一定次数循环后, 会自动终止, 不会死循环.
- 确定性, 每一步都有其具体的含义, 不会出现二义性.
- 可行性, 每一步都是可执行的, 且会在一定次数后结束.
问： 如何衡量算法的优劣？ 答案： 不能单纯的只依靠程序的执行时间， 因为程序执行时也会受到机器， 硬件， 其它软件的影响. 所以我们可以假定 计算机执行每个步骤的时间都是固定的, 只考虑算法的 执行步骤即可. 即: 算法的总执行时间 = 算法的总执行步骤 * 每个步骤执行的时间
3.时间复杂度介绍:
概述:
它可以反应1个算法的优劣, 它表示1个算法随着问题规模的变化而表现出来的趋势.
细节:
1. 如非特殊说明, 我们考虑时间复杂度都是考虑: 最坏时间复杂度, 它算是算法的一种保证.
2. 常见的时间复杂度, 效率从高到低分别是:
O(1) > O(logn) > O(n) > O(nlogn) > O(n²) > O(n³)
3. 空间复杂度(了解)指的是: 算法的运算过程中, 临时占用空间的大小, 也是用大O标记法标记的, 具体如下:
O(1) < O(logn) < O(n) < O(n²) < O(n³)
4. 扩展一个开发思想, 叫: 时空转换, 即: 拿时间 换 空间, 还是 拿空间 换 时间.
5. 程序 = 数据结构 + 算法
大O标记法:
忽略次要条件, 只考虑主要条件(随着问题规模变化而变化的内容), 就会得到: 大O标记法, 标记的效率.
例如, 如下的代码:
import time
# 需求: 已知 a + b + c = 1000, 且 a^2 + b^2 = c^2, 请求出 a, b, c可能得所有组合.
# 1. 获取开始时间.
start = time.time()
# 2. 具体的计算过程
# # 方式1: 穷举法实现, 241秒
# for a in range(1001):
# for b in range(1001):
# for c in range(1001):
# if a ** 2 + b ** 2 == c ** 2 and a + b + c == 1000:
# print(a, b, c)
# 方式2: 穷举法实现, 123秒
# for a in range(1001):
# for b in range(1001):
# for c in range(1001):
# if a + b + c == 1000 and a ** 2 + b ** 2 == c ** 2:
# print(a, b, c)
# 方式3: 代入法, 0.3秒
for a in range(1001):
for b in range(1001):
c = 1000 - a - b
if a ** 2 + b ** 2 == c ** 2:
print(a, b, c)
if a ** 2 + b ** 2 == c ** 2:
print(a, b, c)
# 3. 获取结束时间.
end = time.time()
# 4. 打印结果.
print(f"耗时: {end - start} 秒!")
4.数据结构
数据结构介绍:
概述:
数据结构 = 存储 和 组织数据的 方式.
分类:
线性结构
非线性结构
线性结构:
特点:
每个节点只能有1个子节点(后继节点) 和 1个父节点(前驱节点).
代表:
栈, 队列, 链表...
分类:
顺序表
链表
线性结构之顺序表介绍:
概述:
它属于线性结构的一种, 例如: 栈, 队列都属于顺序表.
特点:
所有元素在内存中以 连续的内存空间 来存储.
举例:
你们部门出去旅游, 共10个人, 开10个房间, 要求: 10个房间在同一层, 且是连续的房间.
根据存储数据的方式, 又分为:
一体式存储: 地址值 和 数据存储在一起.
分离式存储: 地址值 和 数据分开存储.
顺序表-扩容策略解释:
1. 每次扩容增加固定的条数目. 属于拿时间 换 空间.
2. 每次扩容容量翻倍. 属于拿空间 换 时间.
细节:
顺序表主要存储 数据区 和 信息区, 数据区和信息区在一起的叫: 一体式存储, 分开存储的叫: 分离式存储.
顺序表的增删操作:
方式1: 末尾增删. 时间复杂度: O(1)
方式2: 中间增删(非保序) 时间复杂度: O(1)
方式3: 中间增删(保序) 时间复杂度: O(n)
树状结构(Tree)介绍:
概述:
它属于数据结构之 非线性结构的一种, 父节点可以多个子节点(后继节点).
特点:
1. 有且只能有1个根节点.
2. 每个节点都可以有1个父节点及任意个子节点. 前提: 根节点除外.
3. 没有子节点的节点称之为: 叶子节点.
二叉树介绍:
概述:
每个节点最多只能有2个子节点.
分类:
完全二叉树: 除了最后1层, 其它层的节点都是满的.
满二叉树: 包括最后1层, 所有层的节点都是满的.
不完全二叉树: 某层(不仅仅是最后1层)的节点数量不满.
常用的二叉树:
平衡二叉树: 防止树退化成链表. 指的是: 任意节点的两颗子树的高度差不超过1.
排序二叉树: 主要是对元素排序的.
存储方式:
更推荐使用 链表的方式来存储, 每个节点由3部分组成, 分别是: 元素域(数值域), 左子树(地址域), 右子树(地址域)
针对于 多叉树的情况, 可以将其转成二叉树, 然后再来存储.
1.链表
链表是一种重要的线性数据结构，它不同于数组，以动态分配的方式存储数据。每个节点包含数据部分和指向下一个节点的指针，因此链表不需要连续的内存空间，可以方便地进行插入和删除操作。下面详细介绍链表的概念、类型、操作及其实现。
链表的基本概念
链表由一系列节点组成，每个节点包含两部分：
- 数据（data）： 存储节点的数据。
- 指针（next）： 存储指向下一个节点的引用。
链表的第一个节点称为头节点（head），最后一个节点的next指针指向None，表示链表结束。
链表的优势: 相比数组，链表在插入和删除操作上更加高效，尤其是在头部和尾部的操作。链表不需要连续的内存空间。
链表的劣势: 链表的查找效率较低，必须从头节点开始逐个遍历。此外，由于每个节点需要额外存储指针，链表的内存开销相对较高。
单向链表: 每个节点由 1个数值域和1个地址域组成, 且每个节点的地址域指向下个节点的地址. 最后1个节点的地址域为: None
单向循环链表: 每个节点由 1个数值域和1个地址域组成, 且每个节点的地址域指向下个节点的地址. 最后1个节点的地址域为: 第1个节点的地址
双向链表: 每个节点由 1个数值域和2个地址域组成, 且每个节点的地址域分别指向前1个节点的地址 和 后1个节点的地址.
第1个节点的(前)地址域为: None, 最后1个节点的(后)地址域为: None
双向循环链表:每个节点由 1个数值域和2个地址域组成, 且每个节点的地址域分别指向前1个节点的地址 和 后1个节点的地址.
第1个节点的(前)地址域为: 最后1个节点的地址, 最后1个节点的(后)地址域为: 第1个节点的地址.
链表的类型
-
单向链表（Singly Linked List）
- 每个节点只包含指向下一个节点的指针。
- 操作简单，但只能从头节点开始逐个遍历到末尾。
-
双向链表（Doubly Linked List）
- 每个节点包含两个指针：一个指向下一个节点，一个指向前一个节点。
- 这种结构使得可以双向遍历链表，插入和删除更加灵活。
-
循环链表（Circular Linked List）
- 链表中的最后一个节点的
next指针指向头节点，形成一个环。 - 循环链表可以是单向的或双向的，适合某些需要循环处理数据的场景。
- 链表中的最后一个节点的
-
带头节点和不带头节点的链表
- 带头节点：链表在第一个有效节点前有一个头节点，头节点不存储数据，但使操作更方便。
- 不带头节点：链表的第一个节点就是第一个数据节点。
链表的基本操作
- 创建链表 创建链表时需要初始化链表的头节点，通常可以通过一个类来实现。
-
插入节点
- 头插法：在链表头部插入节点。
- 尾插法：在链表尾部插入节点。
- 中间插入：在指定位置插入节点。
-
删除节点
- 头节点删除：删除头节点并将头指针指向下一个节点。
-
尾节点删除：删除尾节点，找到倒数第二个节点并将其
next指向None。 - 中间删除：删除链表中指定位置的节点。
- 查找节点 遍历链表，找到数据与目标匹配的节点。
- 遍历链表 从头节点开始，顺序访问链表中的每个节点，直到链表末尾（单向链表）或循环一周（循环链表）。
单向链表
# 定义链表的节点类
class Node:
def __init__(self, data):
# 节点包含两个属性：数据和指向下一个节点的指针
self.data = data # 存储节点的数据
self.next = None # 存储下一个节点的引用，初始为None
# 定义单向链表类
class SinglyLinkedList:
def __init__(self):
# 初始化链表时，链表为空，因此头节点设置为None
self.head = None
# 在链表头部插入节点
def insert_at_head(self, data):
# 创建新节点，将数据存储在节点中
new_node = Node(data)
# 新节点的next指针指向当前的头节点
new_node.next = self.head
# 更新头节点为新节点，表示链表的起点发生了改变
self.head = new_node
# 在链表尾部插入节点
def insert_at_end(self, data):
# 创建新节点，数据存储在节点中
new_node = Node(data)
# 先检查链表是否为空。如果链表为空，则直接将新节点作为头节点
if not self.head:
self.head = new_node
return
# 如果链表非空，遍历链表直到找到最后一个节点，将最后一个节点的next指针指向新节点
last_node = self.head
while last_node.next:
last_node = last_node.next
# 将最后一个节点的next指向新节点
last_node.next = new_node
# 删除具有特定数据的节点
def delete_node(self, key):
# 用临时变量指向头节点
temp = self.head
# 先检查头节点是否为要删除的节点。如果头节点就是要删除的节点
if temp and temp.data == key:
# 将头节点指向下一个节点（删除头节点）
self.head = temp.next
temp = None # 释放被删除节点的内存
return
# 否则，查找要删除的节点
prev = None # 保存当前节点的前一个节点
while temp and temp.data != key:
prev = temp
temp = temp.next
# 如果没有找到节点
if temp is None:
return
# 将前一个节点的next指向要删除节点的下一个节点
prev.next = temp.next
temp = None # 释放被删除节点的内存
# 指定位置 添加元素
def insert(self, pos, item):
if pos <= 0:
self.add(item)
elif pos >= self.length():
self.append(item)
else:
# 从头开始遍历
cur = self.head
# 初始位置为 0
count = 0
# 找到要插入 位置的前一个索引
while count < pos-1:
cur = cur.next
count += 1
# 此时已经找到
# 将新节点的next指针指向插入位置原来的下一个节点。然后，将前一个节点的next指针指向新节点。
new_node = SingleNode(item)
new_node.next = cur.next
cur.next = new_node
# 查找链表中是否存在特定数据
def search(self, key):
# 用临时变量指向头节点
current = self.head
# 遍历链表，查找节点数据是否等于key
while current:
if current.data == key:
return True # 找到数据，返回True
current = current.next # 移动到下一个节点
return False # 未找到数据，返回False
# 遍历并打印链表中的所有节点
def traverse(self):
# 用临时变量指向头节点
current = self.head
# 遍历链表，打印每个节点的数据
while current:
print(current.data, end=" -> ")
current = current.next
print("None") # 最后输出None表示链表结束
# 测试链表功能
linked_list = SinglyLinkedList()
# 插入节点到链表头部
linked_list.insert_at_head(3) # 链表：3 -> None
linked_list.insert_at_head(2) # 链表：2 -> 3 -> None
# 插入节点到链表尾部
linked_list.insert_at_end(4) # 链表：2 -> 3 -> 4 -> None
# 遍历链表
linked_list.traverse() # 输出: 2 -> 3 -> 4 -> None
# 删除节点
linked_list.delete_node(3) # 删除值为3的节点，链表变为：2 -> 4 -> None
# 遍历链表
linked_list.traverse() # 输出: 2 -> 4 -> None
# 搜索节点
print(linked_list.search(2)) # 输出: True
print(linked_list.search(3)) # 输出: False
双向链表
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert_at_head(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
new_node.prev = last_node
def delete_node(self, key):
temp = self.head
if temp and temp.data == key:
self.head = temp.next
if self.head:
self.head.prev = None
temp = None
return
while temp and temp.data != key:
temp = temp.next
if temp is None:
return
if temp.next:
temp.next.prev = temp.prev
if temp.prev:
temp.prev.next = temp.next
temp = None
def traverse(self):
current = self.head
while current:
print(current.data, end=" <-> ")
current = current.next
print("None")
# 测试
dll = DoublyLinkedList()
dll.insert_at_head(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.traverse() # 输出: 1 <-> 2 <-> 3 <-> None
dll.delete_node(2)
dll.traverse() # 输出: 1 <-> 3 <-> None
2.树状结构(Tree)介绍:
概述:
它属于数据结构之 非线性结构的一种, 父节点可以多个子节点(后继节点).
特点:
1. 有且只能有1个根节点.
2. 每个节点都可以有1个父节点及任意个子节点. 前提: 根节点除外.
3. 没有子节点的节点称之为: 叶子节点.
二叉树介绍:
概述:
每个节点最多只能有2个子节点.
分类:
完全二叉树: 除了最后1层, 其它层的节点都是满的.
满二叉树: 包括最后1层, 所有层的节点都是满的.
不完全二叉树: 某层(不仅仅是最后1层)的节点数量不满.
常用的二叉树:
平衡二叉树: 防止树退化成链表. 指的是: 任意节点的两颗子树的高度差不超过1.
排序二叉树: 主要是对元素排序的.
存储方式:
更推荐使用 链表的方式来存储, 每个节点由3部分组成, 分别是: 元素域(数值域), 左子树(地址域), 右子树(地址域)
针对于 多叉树的情况, 可以将其转成二叉树, 然后再来存储.
"""
# 案例: 自定义代码, 模拟树状结构.
# 1. 定义节点类.
class Node(object):
# 初始化属性
def __init__(self, item):
self.item = item # 数值域, 存储节点内容的
self.lchild = None # 节点的 左子树(的地址), left
self.rchild = None # 节点的 右子树(的地址), right
# 2. 创建 二叉树类.
class BinaryTree(object):
# 2.1 初始化属性
def __init__(self, root=None):
self.root = root # 充当根节点
# 2.2 定义add函数(), 表示往: 添加元素
def add(self, item):
# 1. 判断根节点是否存在, 如果不存在, 则该(新节点)就是 根节点.
if self.root is None:
self.root = Node(item)
return # 细节: 添加后, 本次添加动作完毕, 记得终止.
# 2. 走到这里, 说明根节点存在, 我们需要找到 "缺失的节点", 就是新节点要添加的位置.
# 创建1个队列, 用于记录已存在的节点.
queue = []
# 把根节点加到队列中.
queue.append(self.root)
# 3.循环遍历队列, 直至 把新元素添加到合适的位置.
while True:
# 4. 获取队列的第1个元素(如果首次操作, 则是在获取 根节点)
node = queue.pop(0)
# 5. 判断当前节点的左子树是否存在.
if node.lchild is None:
# 5.1 如果当前节点的 左子树不存在, 就把新节点添加到这里.
node.lchild = Node(item)
return # 细节: 添加后, 本次添加动作完毕, 记得终止.
else:
# 5.2 如果当前节点的 左子树存在, 就将其添加到队列中.
queue.append(node.lchild)
# 6. 判断当前节点的右子树是否存在.
if node.rchild is None:
# 6.1 如果当前节点的 右子树不存在, 就把新节点添加到这里.
node.rchild = Node(item)
return # 细节: 添加后, 本次添加动作完毕, 记得终止.
else:
# 6.2 如果当前节点的 右子树存在, 就将其添加到队列中.
queue.append(node.rchild)
# 2.3 定义 breadth_travel(), 表示: 广度优先遍历
def breadth_travel(self):
# 1. 判断根节点是否存在.
if self.root is None:
return # 根节点不存在, 结束遍历即可.
# 2. 走到这里, 根节点存在, 创建队列, 记录所有的节点.
queue = []
queue.append(self.root)
# 3. 只要队列中有内容, 就说明还有节点, 就继续循环.
while len(queue) > 0:
# 4. 获取队列的第1个元素.
node = queue.pop(0)
# 5. 打印该节点的内容.
print(node.item, end='\t')
# 6. 判断当前节点的左, 右子树是否存在, 存在就添加到队列中.
if node.lchild is not None:
queue.append(node.lchild)
if node.rchild is not None:
queue.append(node.rchild)
# 2.4 定义 preorder_travel(), 表示: 深度优先遍历之 先序(根左右)
def preorder_travel(self, root):
# 判断 根节点是否存在 存在则获取元素
if root is not None:
# 先序的顺序: 根 -> 左 -> 右
print(root.item, end=' ') # 根
# 递归方式, 获取 子左树的所有元素
self.preorder_travel(root.lchild)
# 递归方式, 获取 子右树的所有方式
self.preorder_travel(root.rchild)
# 2.5 定义 inorder_travel(), 表示: 深度优先遍历之 中序(左根右)
def inorder_travel(self, root):
if root is not None:
self.inorder_travel(root.lchild)
print(root.item, end=' ') # 根
self.inorder_travel(root.rchild)
# 2.6 定义 postorder_travel(), 表示: 深度优先遍历之 后序(左右根)
def postorder_travel(self, root):
if root is not None:
self.postorder_travel(root.lchild)
self.postorder_travel(root.rchild)
print(root.item, end=' ')
# 3. 定义 demo01_测试节点类和二叉树类()
def demo01_测试节点类和二叉树类():
# 3.1 创建节点对象.
node1 = Node('乔峰')
# 3.2 打印节点的 数值域 和 地址域
print(f'节点的地址: {node1}')
print(f'节点的内容: {node1.item}')
print(f'节点的左子树(地址): {node1.lchild}')
print(f'节点的右子树(地址): {node1.rchild}')
# 3.3 创建二叉树对象.
bt = BinaryTree()
print(f'根节点: {bt.root}') # None
print('-' * 21)
bt2 = BinaryTree(node1)
print(f'根节点: {bt2.root}')
print(f'根节点的内容: {bt2.root.item}')
print(f'根节点的左子树(地址): {bt2.root.lchild}')
print(f'根节点的右子树(地址): {bt2.root.rchild}')
# 4. 定义 demo02_演示队列的使用()
def demo02_演示队列的使用():
# 4.1 创建列表对象, "模拟"队列, 即: 先进先出.
queue = []
# 4.2 往队列中添加元素
queue.append('A')
queue.append('B')
queue.append('C')
# 4.3 打印队列的内容.
print(queue)
# 4.4 逐个获取队列中的内容, 模拟: 先进先出.
# pop()函数: 根据索引, 删除(弹出)列表中的元素, 并返回该元素.
print(queue.pop(0)) # ['A', 'B', 'C'] => ['B', 'C'], 返回: 'A'
print(queue.pop(0)) # ['B', 'C'] => ['C'], 返回: 'B'
print(queue.pop(0)) # ['C'] => [], 返回: 'C'
# 5. 定义 demo03_演示广度优先()
def demo03_演示广度优先():
# 1. 创建二叉树.
bt = BinaryTree()
# 2. 添加元素到二叉树中.
bt.add('A')
bt.add('B')
bt.add('C')
bt.add('D')
bt.add('E')
bt.add('F')
bt.add('G')
bt.add('H')
# 3. 广度优先的方式遍历.
bt.breadth_travel()
# 6. 定义demo04 演示深度优先遍历
def demo04_演示深度优先遍历():
# 1. 创建二叉树
bt = BinaryTree()
# 2. 添加元素到二叉树中
bt.add(1)
bt.add(2)
bt.add(