本文是基于k神的Hello 算法的读书笔记,请支持实体书。
https://www.hello-algo.com/chapter_paperbook/
线性数据结构
数组、链表、栈、队列、哈希表
非线性数据结构
树、堆、图
连续与离散
所有数据结构都是基于数组、链表或二者的组合实现的。
基本数据类型
基本数据类型是 CPU 可以直接进行运算的类型
- 整形:int
- 浮点型:float
- 字符串:char
- 布尔型:bool
数字编码
数字是以补码的形式存储在计算机中的,首先回顾下三者的定义
- 原码:最高位是符号位,0是正,其余位表示数字的值
- 反码:正数的反码与原码相同,负数是除符号位外取反
- 补码:正数的补码与原码相同,负数的补码是在其反码的补码的基础上加一
负数的原码不能直接计算,所以引入了反码。为了解决原码和反码的0的歧义问题,引入了补码。
在计算机中运算时,最终以补码进行运算。
字符编码
计算机中用字符编码建立起二进制数和字符串的一一对应关系。
ASCII:最早出现,只能表示英文,使用一个字节
GBK:表示中文,需要2个字节
Unicode:为了收录所有语言的不同字符而出现,生僻字甚至使用3或4个字节
UTF-8:为了解决Unicode的内存浪费问题,还有一个优点是通用性最高
UTF-16:用来存储中文比较高效
数组
数组是一种线性的数据结构。
数组的初始化、访问、插入、遍历。这是python中列表的基础内容。略。
数组的优点
- 空间效率高
- 支持随机访问
- 缓存局部性
数组的缺点
- 插入与删除效率低
- 长度不可变
- 空间浪费
列表
列表本质上是数组,它是长度可变的数组。
链表
链表linked list是一种线性的数据结构,链表的数据存储在内存中是不连续的
链表的组成单位是是一个节点[node]对象,包含值和指向下一个节点的引用
class ListNode:
"""链表节点类"""
def __init__(self, val: int):
self.val: int = val # 节点值
self.next: Optional[ListNode] = None # 指向下一节点的引用
链表的初始化
# 初始化链表 1 -> 3 -> 2 -> 5 -> 4
# 初始化各个节点
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# 构建引用指向
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
插入节点
def insert(n0: ListNode, P: ListNode):
"""在链表的节点 n0 之后插入节点 P"""
n1 = n0.next
P.next = n1
n0.next = P
删除节点
def remove(n0: ListNode):
"""删除链表的节点 n0 之后的首个节点"""
if not n0.next:
return
# n0 -> P -> n1
P = n0.next
n1 = P.next
n0.next = n1
访问节点
访问指定index的节点
def access(head: ListNode, index: int) -> ListNode | None:
"""访问链表中索引为 index 的节点"""
for _ in range(index):
if not head:
return None
head = head.next
return head
查找指定节点
查找指定节点的index
def find(head: ListNode, target: int) -> int:
"""在链表中查找值为 target 的首个节点"""
index = 0
while head:
if head.val == target:
return index
head = head.next
index += 1
return -1
链表的类型
单向链表
环形链表
双向链表
链表VS数组
表 4-1 数组与链表的效率对比
数组 | 链表 | |
---|---|---|
存储方式 | 连续内存空间 | 离散内存空间 |
缓存局部性 | 友好 | 不友好 |
容量扩展 | 长度不可变 | 可灵活扩展 |
内存效率 | 占用内存少、浪费部分空间 | 占用内存多 |
访问元素 | O(1) | O(n) |
添加元素 | O(n) | O(1) |
删除元素 | O(n) | O(1) |