目录
链表
链表介绍
创建和遍历链表
链表节点插入和删除
双链表
链表总结——复杂度分析
哈希表(散列表)
哈希表介绍
哈希冲突
哈希表实现
哈希表应用
树
树
树的示例——模拟文件系统
二叉树
二叉树的链式存储
二叉树的遍历
二叉搜索树
插入
查询
删除
AVL树
旋转
插入
链表
链表介绍
链表是由一系列节点组成的元素集合，每个节点包含两部分，数据域item和指向下一个节点的指针next。通过节点之间的相互连接，最终串联成一个链表。
节点定义：
class Node(object):
def __init__(self, item):
self.item = item
self.next = None创建和遍历链表
头插法/尾插法
class Node:
def __init__(self, item):
self.item = item
self.next = None
# 创建链表（头插法）
def crweate_linklist_head(li):
head = Node(li[0])
for element in li[1:]:
node = Node(element)
node.next = head
head = node
return head
# 创建链表（尾插法）
def crweate_linklist_tail(li):
head = Node(li[0])
tail = head
for element in li[1:]:
node = Node(element)
tail.next = node
tail = node
return head
# 打印链表（遍历）
def print_linklist(lk):
while lk:
print(lk.item, end=',')
lk = lk.next
print()链表节点插入和删除
插入是创建一个节点，将该节点指向插入位置的下一个节点，上一个节点指向该节点。
删除是将上一个节点的next指向下一个节点。
双链表
双链表每个节点有两个指针：一个指向后一个节点，另一个指向前一个节点。
节点定义：
class Node(object):
def __init__(self, item=None):
self.item = item
self.next = None
self.prior = None链表总结——复杂度分析
- 按元素值查找：O(n)
- 按下标查找：O(n)
- 在某元素后插入：O(1)
- 删除某元素：O(1)
链表在插入和删除的操作上明显快于顺序表
链表的内存可以更灵活分配
链表这种链式存储的数据结构对树和图的结构有很大启发性
哈希表(散列表)
哈希表介绍
介绍：哈希表是一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作：
- insert(key, value)：插入键值对(key, value)
- get(key)：如果存在键为key的键值对，返回其valve，否则返回空值
- delete(key)：删除键为key的键值对
哈希表是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数构成。哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标。
哈希冲突
哈希冲突：由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现两个不同元素映射到同一个位置上的情况。
1.开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值。
- 线性探查：如果位置i被占用，则探查i+1, i+2......
- 二次探查：如果位置i被占用，则探查
- 二度哈希：有n个哈希函数，当使用第一个哈希函数h1发生冲突时，则尝试使用h2，h3......
2.拉链法：哈希表每个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。
常见哈希函数：
- 除法哈希法：h(k) = k % m
- 乘法哈希法：h(k) = floor(m*(A*key%1))
- 全域哈希法：
a,b = 1, 2, ...,p-1
哈希表实现
class LinkList:
# 定义节点类
class Node:
def __init__(self, item=None):
self.item = item # 节点的数据项
self.next = None # 指向下一个节点的指针
# 定义迭代器类
class LinkListIterator:
def __init__(self, node):
self.node = node # 当前节点
def __next__(self):
if self.node: # 如果当前节点存在
cur_node = self.node # 保存当前节点
self.node = cur_node.next # 将当前节点指向下一个节点
return cur_node.item # 返回当前节点的数据项
else:
raise StopIteration # 当遍历结束时抛出StopIteration异常
def __iter__(self):
return self # 返回迭代器自身
# 初始化链表
def __init__(self, iterable=None):
self.head = None # 头节点
self.tail = None # 尾节点
if iterable:
self.extend(iterable) # 如果传入可迭代对象，则调用extend方法进行扩展
# 在链表尾部添加节点
def append(self, obj):
s = LinkList.Node(obj) # 创建新节点
if not self.head: # 如果链表为空
self.head = s # 新节点作为头节点
self.tail = s # 新节点作为尾节点
else:
self.tail.next = s # 将新节点连接到当前尾节点后
self.tail = s # 更新尾节点为新节点
# 扩展链表
def extend(self, iterable):
for obj in iterable:
self.append(obj) # 逐个添加可迭代对象中的元素
# 查找元素是否在链表中
def find(self, obj):
for n in self: # 遍历链表中的每个节点
if n == obj: # 如果找到目标元素
return True # 返回True
else:
return False # 找不到目标元素时返回False
# 返回链表的迭代器
def __iter__(self):
return self.LinkListIterator(self.head)
# 返回链表的字符串表示
def __repr__(self):
return "<<" + ", ".join(map(str, self)) + ">>"
# 类似于集合的结构
class HashTable:
def __init__(self, size = 101):
self.size = size
self.T = [LinkList() for _ in range(self.size)] # 创建域
# 哈希函数
def h(self, k):
return k % self.size
# 插入
def insert(self, k):
i = self.h(k)
if self.find(k): # 如果有
print("Duplicated Insert.")
else:
self.T[i].append(k)
# 查找
def find(self, k):
i = self.h(k)
return self.T[i].find(k)
ht = HashTable()
for i in range(200):
ht.insert(i)
# print(",".join(map(str, ht.T)))
print(ht.find(203))哈希表应用
python的字典，集合都是哈希表
md5算法
树
树
介绍：树是一种数据结构
- 树是一种可以递归定义的数据结构
- 树是由n个结点组成的集合
- 如果n=0，那这是一棵空树
- 如果n>0，那存在一个结点作为树的根结点，其他结点可以分为m个集合，每个集合本身又是一棵树
一些概念：
- 根结点、叶子结点
- 树的深度/高度
- 树的度
- 孩子结点、父结点
- 子树
树的示例——模拟文件系统
# 节点
class Node:
def __init__(self, name, type = 'dir'):
self.name = name
self.type = type # 'dir' or 'file'
self.children = [] # 存儿子节点
self.parent = None # 指向父节点
def __repr__(self):
return self.name
# 树类
class FileSystemTree:
def __init__(self):
self.root = Node('/')
self.now = self.root
# 创建目录
def mkdir(self, name):
# name得是一个目录，以'/'结尾
if name[-1] != '/':
name += '/'
node = Node(name)
self.now.children.append(node)
node.parent = self.now
# 展示所有目录
def ls(self):
return self.now.children
# 切换目录
def cd(self, name):
# 只支持往下走一层
if name[-1] != '/':
name += '/'
if name == '../':
self.now = self.now.parent
return
for child in self.now.children:
if child.name == name:
self.now = child
return
raise ValueError("invalid dir")
tree = FileSystemTree()
tree.mkdir("var/")
tree.mkdir("bin/")
tree.mkdir("usr/")
print(tree.ls())
tree.cd("bin")
tree.mkdir("python")
print(tree.ls())
tree.cd("../")
print(tree.ls())
二叉树
二叉树就是度不超过2的树
- 每个结点最多有两个孩子结点
- 两个孩子结点被区分为左孩子结点和右孩子结点
完全二叉树
- 满二叉树：一个二叉树，如果一个层的节点数都达到最大值，则这个二叉树就是满二叉树
- 完全二叉树：叶子节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
二叉树的存储方式（表示方式）
- 链式存储方式
- 顺序存储方式（堆排序用这个）——用列表来存
- 父结点和左孩子结点的编号下标的关系
0-1 1-3 2-5 3-7 4-9
i -> 2i+1
- 父结点和右孩子结点的编号下标的关系
0-2 1-4 2-6 3-8 4-10
i -> 2i+2
之前学过线性存储，这里是链式存储
二叉树的链式存储
将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接。
节点定义：
class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None
self.rchild = None二叉树的遍历
二叉树的遍历方式：
- 前序遍历：如果不空，先访问根，再访问左子树，最后访问右子树。
- 中序遍历：如果不空，先访问左子树，再访问根，最后访问右子树。
- 后序遍历：如果不空，先访问左子树，再访问右子树，最后访问根。
- 层次遍历：一层一层访问。
# 前序遍历
def pre_order(root):
if root:
print(root.data, end=',')
pre_order(root.lchild)
pre_order(root.rchild)
# 中序遍历
def in_order(root):
if root:
in_order(root.lchild)
print(root.data, end=',')
in_order(root.rchild)
# 后序遍历
def post_order(root):
if root:
post_order(root.lchild)
post_order(root.rchild)
print(root.data, end=",")
# 层次遍历
from compileall import queue
def level_order():
queue = deque()
queue.append(root)
while len(queue) > 0: # 只要队不空
node = queue.popleft()
print(node.data, end=',')
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
二叉搜索树
是一颗二叉树，并且满足左子树的根比根小，右子树的根比根大。
二叉搜索树的操作：查询、插入、删除
二叉搜索树的效率：
- 平均情况下，二叉搜索树进行搜索的时间复杂度为O(logn)
- 最坏情况下，二叉搜索树可能非常偏斜
解决方案：
- 随机化插入
- AVL树
插入
两种方式：递归和非递归
class BiTreeNode:
def __init__(self, data):
self.data = data
self.lchild = None # 左孩子
self.rchild = None # 右孩子
self.parent = None
class BST:
def __init__(self, li=None):
self.root = None
if li:
for val in li:
self.insert_no_rec(val) # 根据列表构造树
# 插入(递归)
def insert(self, node, val):
if not node:
node = BiTreeNode(val)
elif val < node.data:
node.lchild = self.insert(node.lchild, val)
node.lchild.parent = node
elif val > node.data:
node.rchild = self.insert(node.lchild, val)
node.rchild.parent = node
return node
# 插入(非递归)
def insert_no_rec(self, val):
p = self.root
if not p: # 空树时
self.root = BiTreeNode(val)
return
while True:
if val < p.data:
if p.lchild:
p = p.lchild
else: # 左孩子不存在
p.lchild = BiTreeNode(val)
p.lchild.parent = p
return
elif val > p.data:
if p.rchild:
p = p.rchild
else:
p.rchild = BiTreeNode(val)
p.rchild.parent = p
return
else:
return查询
两种方式：递归和非递归
# 查询(递归)
def query(self, node, val):
if not node:
return None
if node.data < val:
return self.query(node.rchild, val)
elif node.data > val:
return self.query(node.lchild, val)
else:
return node
# 查询(非递归)
def query_no_rec(self, val):
p = self.root
while p:
if p.data < val:
p = p.rchild
elif p.data > val:
p = p.lchild
else:
return p
return None删除
三种情况：
- 叶子节点——直接删除
- 要删除的节点只有一个孩子——将此节点的父亲与孩子连接，然后删除该节点
- 要删除的节点有两个孩子——将其右子树的最小节点删除，并替换当前节点
# 情况1:node是叶子节点
def __remove_node_1(self, node):
if not node.parent: # 如果是根节点
self.root = None
elif node == node.parent.lchild: # node是它父亲的左孩子
node.parent.lchild = None
else: # 是右孩子
node.parent.rchild = None
# 情况2.1:node只有一个左孩子
def __remove_node_21(self, node):
if not node.parent: # 如果是根节点
self.root = node.lchild
node.lchild.parent = None
elif node == node.parent.lchild: # 是它父亲的左孩子
node.parent.lchild = node.lchild
node.lchild.parent = node.parent
else: # 是它父亲的右孩子
node.parent.rchild = node.lchild
node.lchild.parent = node.parent
# 情况2.2:node只有一个右孩子
def __remove_node_22(self, node):
if not node.parent:
self.root = node.rchild
node.rchild.parent = None
elif node == node.parent.lchild: # 是它父亲的左孩子
node.parent.lchild = node.rchild
node.rchild.parent = node.parent
else: # 是它父亲的右孩子
node.parent.rchild = node.rchild
node.rchild.parent = node.parent
# 情况3:左右节点都有
def delete(self, val):
if self.root: # 不是空树再删
node = self.query_no_rec(val)
if not node: # 如果node不存在
return False
if not node.lchild and not node.rchild: # 1删除叶子节点的情况
self.__remove_node_1(node)
elif not node.rchild: # 2.1只有一个左孩子
self.__remove_node_21(node)
elif not node.lchild: # 2.2只有一个右孩子
self.__remove_node_22(node)
else: # 3两个孩子都有
min_node = node.rchild
while min_node.lchild:
min_node = min_node.lchild
node.data = min_node.data
# 然后删除min_node
if min_node.rchild:
self.__remove_node_22(min_node)
else:
self.__remove_node_21(min_node)AVL树
AVL树：AVL树是一棵自平衡的二叉搜索树
AVL树具有以下性质：
- 根的左右子树的高度之差的绝对值不能超过1
- 根的左右子树都是平衡二叉树
旋转
旋转是修正出现不平衡的树的操作
这里的旋转是服务于插入的
插入一个节点后，只有从插入节点到根节点的路径上的节点的平衡可能被改变。我们需要找出第一个破坏了平衡条件的节点，称之为K——K的两棵子树的高度差2.
插入不平衡的出现可能有四种情况：
- 不平衡是由于对K的右孩子的右子树插入导致的：左旋
- 不平衡是由于对K的左孩子的左子树插入导致的：右旋
- 不平衡是由于对K的右孩子的左子树插入导致的：右旋-左旋
- 不平衡是由于对K的左孩子的右子树插入导致的：左旋-右旋
from bst import BiTreeNode, BST
class AVLNode(BiTreeNode): # 继承
def __init__(self):
BiTreeNode.__init__(self, data)
self.bf = 0
class AVLTree(BST):
def __init__(self, li=None):
BST.__init__(self, li)
# 左旋
def rotate_left(self, p, c):
s2 = c.lchild
p.rchild = s2
if s2:
s2.parent = p
c.lchild = p
p.parent = c
p.bf = 0
c.bf = 0
# 右旋
def rotate_right(self, p, c):
s2 = c.rchild
p.lchild = s2
if s2:
s2.parent = p
c.rchild = p
p.parent = c
p.bf = 0
c.bf = 0
# 右旋左旋
def rotate_right_left(self, p, c):
g = c.lchild
s3 = g.rchild
c.lchild = s3
if s3:
s3.parent = c
g.rchild = c
c.parent = g
s2 = g.lchild
p.rchild = s2
if s2:
s2.parent = p
g.lchild = p
p.parent = g
# 更新bf
if g.bf > 0:
p.bf = -1
c.bf = 0
elif g.bf < 0:
p.bf = 0
c.bf = 1
else:
p.bf = 0
c.bf = 0
# 左旋右旋
def rotate_left_right(self, p, c):
g = c.rchild
s2 = g.lchild
c.rchild = s2
if s2:
s2.parent = c
g.lchild = c
c.parent = g
s3 = g.rchild
p.lchild = s3
if s3:
s3.parent = p
g.rchild = p
p.parent = g
# 更新bf
if g.bf < 0:
p.bf = 1
c.bf = 0
elif g.bf > 0:
p.bf = 0
c.bf = -1
else:
p.bf = 0
c.bf = 0插入
插入一个节点可能会破坏AVL树的平衡，可以通过旋转操作来进行修正。
def insert_no_rec(self, val): # 重新定义，覆盖原先的方法
# 第一步：和BST一样，先插入
p = self.root
if not p: # 空树时
self.root = BiTreeNode(val)
return
while True:
if val < p.data:
if p.lchild:
p = p.lchild
else: # 左孩子不存在
p.lchild = BiTreeNode(val)
p.lchild.parent = p
node = p.lchild # node存储的就是插入的节点
break
elif val > p.data:
if p.rchild:
p = p.rchild
else:
p.rchild = BiTreeNode(val)
p.rchild.parent = p
node = p.rchild
break
else: # val == p.data同样的元素只保留一个
return
# 第二步：更新balance factor
while node.parent: # 保证node.parent不空
if node.parent.lchild == node: # 传递是从左子树来的，左子树更沉了
# 更新node.parent 的 bf -= 1
if node.parent.bf < 0: # 原来node.parent.bf == -1，更新后变为-2
# 做旋转
# 看node哪边沉
g = node.parent.parent # 为了连接旋转之后的子树
x = node.parent # 旋转前的子树的根
if node.bf > 0:
n = self.rotate_left_right(node.parent, node)
else:
n = self.rotate_right(node.parent, node)
# 最后将n 和 g 连接起来
elif node.parent.bf > 0: # 原来node.parent.bf == 1, 更新后变成0
node.parent.bf = 0
break
else: # 原来node.parent.bf == 0, 更新后变成-1
node.parent.bf = -1
node = node.parent
continue
else: # 传递是从右子树来的，右子树更沉了
# 更新node.parent 的 bf += 1
if node.parent.bf > 0: # 原来node.parent.bf == 1，更新后变为2
# 做旋转
# 看node哪边沉
g = node.parent.parent # 为了连接旋转之后的子树
x = node.parent # 旋转前的子树的根
if node.bf < 0:
n = self.rotate_right_left(node.parent, node)
else:
n = self.rotate_left(node.parent, node)
# 记得连起来
elif node.parent.bf < 0: # 原来node.parent.bf == -1, 更新后变成0
node.parent.bf = 0
break
else: # 原来node.parent.bf == 0, 更新后变成1
node.parent.bf = 1
node = node.parent
continue
# 连接旋转后的子树
n.parent = g
if g: # 看g是否存在
if x == g.lchild:
g.lchild = n
else:
g.rchild = n
break
else:
self.root = n
break
代码自己手动敲一遍理解更深哦！
