# 队列(Queue)是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。 进行插入的一端称为队尾(rear)，插入动作称为进队或入队 进行删除的一端称为队头(front)，删除动作称为出队 队列的性质：先进先出(First-in, First-out) # 双向队列：队列的两端都允许进行进队和出队操作。
队列能否简单用列表实现？为什么？ 初步设想：列表+两个下标指针 创建一个列表和两个变量，front变量指向队首，rear变量指向队尾。初始时，front和rear都为0。 进队操作：元素写到li[rear]的位置，rear自增1。 出队操作：返回li[front]的元素，front自减1。
队列的实现原理——环形队列
# 环形队列：当队尾指针front == Maxsize + 1时，再前进一个位置就自动到0。 # 实现方式：求余数运算 队首指针前进1：front = (front + 1) % MaxSize 队尾指针前进1：rear = (rear + 1) % MaxSize 队空条件：rear == front 队满条件：(rear + 1) % MaxSize == front代码实现
from collections import deque maze = [ [1,1,1,1,1,1,1,1,1,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,0,0,1,1,0,0,1], [1,0,1,1,1,0,0,0,0,1], [1,0,0,0,1,0,0,0,0,1], [1,0,1,0,0,0,1,0,0,1], [1,0,1,1,1,0,1,1,0,1], [1,1,0,0,0,0,0,0,0,1], [1,1,1,1,1,1,1,1,1,1] ] dirs = [ lambda x,y:(x, y+1), lambda x,y:(x+1, y), lambda x,y:(x, y-1), lambda x, y: (x - 1, y) ] # 广度优先 def solve_maze_with_queue(x1,y1,x2,y2): q=deque() q.append((x1,y1,-1)) maze[x1][y1]=2 path=[] while len(q)>0: cur_node=q.popleft() path.append(cur_node) if cur_node[:2]==(x2,y2): # for i,v in enumerate(path): # print(i,v) real_path=[] i = len(path)-1 while i>=0: real_path.append(path[i][:2]) i= path[i][2] real_path.reverse() print(real_path) return True for d in dirs: next_x,next_y=d(cur_node[0],cur_node[1]) if maze[next_x][next_y]==0: q.append((next_x,next_y,len(path)-1)) maze[next_x][next_y]=2 else: print('没有通路') return False solve_maze_with_queue(1,1,8,8)建立链表
链表的遍历
头插法
class Node: def __init__(self, data=None): self.data = data self.next = None # 头插法 带头结点的链表，head.next每次指向的都是刚刚插入的数据，得到的链表是倒序的，如果想插入到第一个数据，需要循环到最后，麻烦 def create_linklist(li): head = Node(None) # 创建一个空的链表 for val in li: p = Node(val) # 创建一个节点p p.next = head.next # 将p.next指向head.next head.next = p # 再将p节点连到头的后边（head.next指向p节点），不写上一步的话，就找不到p节点之前的数据了 return head # 头节点代表着链表 def traverse_linklist(head): # 链表的遍历 p = head.next while p: print(p.data) p = p.next head = create_linklist([1,2,3,4,5]) traverse_linklist(head) # 执行结果[5,4,3,2,1]尾插法：
class Node: def __init__(self, data=None): self.data = data self.next = None def create_linklist_tail(li): head = Node(None) tail = head # 最开始，尾巴等于头 for val in li: p = Node(val) tail.next = p # 虚拟一个尾部，将尾部的下一个元素指向新节点p tail = p # 更新tail return head def traverse_linklist(head): # 链表的遍历 p = head.next while p: print(p.data) p = p.next head = create_linklist_tail([1,2,3,4,5]) traverse_linklist(head) # 执行结果[1,2,3,4,5]链表节点的插入和删除
# 插入： p.next = curNode.next curNode.next = p # 删除： p = curNode.next curNode.next = curNode.next.next del p插入前图示：
插入后图示
双链表
双链表中每个节点有两个指针：一个指向后面节点、一个指向前面节点。
节点定义：
class BiNode: def __init__(self,data): self.data=data self.next=None self.prior=None双链表插入代码
class BiNode: def __init__(self,data): self.data=data self.next=None self.prior=None def create_bilinklist(li): # 头插法 head=BiNode(None) tail=BiNode(None) head.next=tail # 初始情况 tail.prior=head for val in li: p=BiNode(val) p.next=head.next head.next.prior=p head.next=p p.prior=head return head # 也可以返回tail def create_bilinklist_tail(li): # 尾插法 head=BiNode(None) tail=BiNode(None) head.next=tail # 初始情况 tail.prior=head for val in li: p=BiNode(val) p.next=tail p.prior=tail.prior tail.prior.next=p tail.prior=p return head # 也可以返回tail def traverse_linklist(head): # 链表的遍历 p = head.next while p: print(p.data) p = p.next head = create_bilinklist([1,2,3,4,5]) # 头插法 traverse_linklist(head) # [5,4,3,2,1] head = create_bilinklist([1,2,3,4,5]) # 尾插法 traverse_linklist(head) # [1,2,3,4,5] 双链表节点的插入和删除 # 插入： p.next = curNode.next curNode.next.prior = p p.prior = curNode curNode.next = p # 删除： p = curNode.next curNode.next = p.next p.next.prior = curNode del p插入前图示
插入后图示
链表-复杂度分析 """ 列表与链表 按元素值查找 都是O(n) 按下标查找 列表 O(1) 链表 O(n) 在某元素后插入 列表 O(n) 链表 O(1) 删除某元素 列表 O(n) 链表 O(1) 链表在插入和删除的操作上明显快于顺序表 链表的内存可以更灵活的分配(空间不够，加一个即可，不用完全连续。next就可以找到) 试利用链表重新实现栈和队列 链表这种链式存储的数据结构对树和图的结构有很大的启发性 """ 哈希表 哈希表一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作： insert(key, value)：插入键值对(key,value), # 只有键，就是集合 get(key)：如果存在键为key的键值对则返回其value，否则返回空值 delete(key)：删除键为key的键值对 直接寻址表 # 当关键字的全域U比较小时，直接寻址是一种简单而有效的方法。 # 直接寻址技术缺点： 当域U很大时，需要消耗大量内存，很不实际 如果域U很大而实际出现的key很少，则大量空间被浪费 无法处理关键字不是数字的情况 哈希：给一个东西，算出来一个值 直接寻址表：key为k的元素放到k位置上 改进直接寻址表：哈希（Hashing） 构建大小为m的寻址表T key为k的元素放到h(k)位置上 h(k)是一个函数，其将域U映射到表T[0,1,...,m-1] 哈希表 哈希表（Hash Table，又称为散列表）， 是一种线性表的存储结构。 哈希表由一个直接寻址表和一个哈希函数组成。 哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标。 简单哈希函数： 除法哈希：h(k) = k mod m 乘法哈希：h(k) = floor(m(kA mod 1)) 0<A<1 假设有一个长度为7的数组，哈希函数h(k)=k mod 7。元素集合{14,22,3,5}的存储方式如下图。 哈希冲突 """ 由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现两个不同元素映射到同一个位置上的情况，这种情况叫做哈希冲突。 比如：h(k)=k mod 7, h(0)=h(7)=h(14)=... """ 解决哈希冲突——开放寻址法 开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值。 线性探查：如果位置i被占用，则探查i+1, i+2,……, # 装载因子：假如是2/3，不够的话，就动态扩张 # 存在问题：有可能大量的数在一起（空位存在一起，也就是余数相同的数比较多） # 在https://visualgo.net/en/hashtable里面演示 二次探查：如果位置i被占用，则探查i+1的平方,i-1的平方,i+2的平方,i-2的平方,…… 二度哈希：有n个哈希函数，当使用第1个哈希函数h1发生冲突时，则尝试使用h2,h3,…… 解决哈希冲突——拉链法 拉链法：哈希表每个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。 # 要控制装载因子，可以大于1 哈希表在Python中的应用 # 字典与集合都是通过哈希表来实现的。 在Python中的字典： a = {'name': 'xiaoming', 'age': 18, 'gender': 'Man'} # 键不是数字解决方法：计算机存储都是二进制，把二进制转化为相应的整数即可 使用哈希表存储字典，通过哈希函数将字典的键映射为下标。 假设h(‘name’) = 3, h(‘age’) = 1, h(‘gender’) = 4， 则哈希表存储为[None, 18, None, ’xiaoming’, ‘Man’]存二叉树的链式储：将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接。
节点定义：
from collections import deque class BiTreeNode: # 节点的定义 def __init__(self, data): self.data = data self.lchild = None self.rchild = None a = BiTreeNode('A') b = BiTreeNode('B') c = BiTreeNode('C') d = BiTreeNode('D') e = BiTreeNode('E') f = BiTreeNode('F') g = BiTreeNode('G') e.lchild = a e.rchild = g a.rchild = c c.lchild = b c.rchild = d g.rchild = f root = e 二叉树的遍历 前序遍历：# 深度优先，从上到下，从左到右，按照进栈的顺序输出（中间，左边，右边） EACBDGF 前序定根E 中序遍历：# 按照出栈的顺序输出（左边，中间，右边） ABCDEGF 中序定左右ABCD GF 后序遍历：# （按照左，右，中间的顺序输出，右孩子完了再输出） BDCAFGE 层次遍历：# 广度优先遍历 EAGCFBD代码实现
def pre_order(root): # 前序遍历，深度优先，类似于栈（递归和栈是对应的） if root: print("%s" % root.data, end='') pre_order(root.lchild) pre_order(root.rchild) def in_order(root): # 中序遍历 if root: in_order(root.lchild) print("%s" % root.data, end='') in_order(root.rchild) def post_order(root): if root: post_order(root.lchild) post_order(root.rchild) print("%s" % root.data, end='') def level_order(root): # 广度优先遍历 q = deque() q.append(root) while len(q) > 0: p = q.popleft() print(p.data, end='') if p.lchild: q.append(p.lchild) if p.rchild: q.append(p.rchild) level_order(root)二叉搜索树——插入操作
class BiTreeNode: def __init__(self, data): self.data = data self.lchild = None self.rchild = None class BST: def __init__(self, li=None): self.root = None if li: self.root = self.insert(li[0]) for val in li[1:]: self.insert(self.root, val) def insert(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) break else: if p.rchild: p = p.rchild else: p.rchild = BiTreeNode(val) break def query_no_rec(val): p = self.root while p: if p.data == val: return True elif p.data > val: p = p.lchild else: p = p.rchild return False def in_order(self, root): if root: self.in_order(root.lchild) print(root.data, end=',') self.in_order(root.rchild) tree = BST() for i in [1, 5, 9, 8, 7, 6, 4, 3, 2]: tree.insert_no_rec(i) tree.in_order(tree.root) # print(tree.query_no_rec(12))二叉搜索树——删除操作
三种情况 # 1.叶子节点 直接删除 # 2.只有一个孩子 将此节点的父亲与孩子连接，然后删除该节点。 # 3.有两个孩子 将其右子树的最小节点（该节点最多有一个右孩子）删除，并替换当前节点。代码实现
import random 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, root, val): if root is None: root = BiTreeNode(val) elif val < root.data: root.lchild = self.insert(root.lchild, val) root.lchild.parent = root elif val > root.data: root.rchild = self.insert(root.rchild, val) root.rchild.parent = root return root 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 break elif val > p.data: if p.rchild: p = p.rchild else: p.rchild = BiTreeNode(val) p.rchild.parent = p break else: return def query(self, root, val): if not root: return None if root.data == val: return root elif root.data > val: return self.query(root.lchild, val) else: return self.query(root.rchild, val) def query_no_rec(self, val): p = self.root while p: if p.data == val: return p elif p.data > val: p = p.lchild else: p = p.rchild return None def in_order(self, root): if root: self.in_order(root.lchild) print(root.data, end=',') self.in_order(root.rchild) def pre_order(self, root): if root: print(root.data, end=',') self.pre_order(root.lchild) self.pre_order(root.rchild) def _remove_node_1(self, node): if not node.parent: # 根节点 self.root = None elif node == node.parent.lchild: # 是父亲的左孩子 node.parent.lchild = None else: # 是父亲的右孩子 node.parent.rchild = None def _remove_node_21(self, node): if not node.parent: # 根节点 self.root = node.rchild self.root.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 def _remove_node_22(self, node): if not node.parent: # 根节点 self.root = node.lchild self.root.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 def delete(self, val): if self.root: # 不是空树 node = self.query_no_rec(val) if not node: # 如果不存在该节点 return False if not node.lchild and not node.rchild: # 1.叶子节点 self._remove_node_1(node) elif not node.lchild: # 2.1 只有一个右孩子 self._remove_node_21(node) elif not node.rchild: # 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 # 删除该节点 if min_node.rchild: self._remove_node_21(min_node) else: self._remove_node_1(min_node) # li = [7,0,3,8,6,2,9,4,1,5] # tree = BST(li) # # tree.delete(7) # tree.delete(0) # # # tree.in_order(tree.root) #print(tree.query_no_rec(12))二叉搜索树的效率
平均情况下，二叉搜索树进行搜索的时间复杂度为O(nlogn)。 最坏情况下，二叉搜索树可能非常偏斜。 解决方案： 随机化插入 AVL树AVL树——插入操作
插入一个节点可能会破坏AVL树的平衡，可以通过旋转操作来进行修正。 插入一个节点后，只有从插入节点到根节点的路径上的节点的平衡可能被改变。我们需要找出第一个破坏了平衡条件的节点，称之为K。K的两颗子树的高度差2。 不平衡的出现可能有4种情况1.不平衡是由于对K的右孩子的右子树插入导致的：左旋
2.不平衡是由于对K的左孩子的左子树插入导致的：右旋
3.不平衡是由于对K的右孩子的左子树插入导致的：右旋-左旋
4.不平衡是由于对K的左孩子的右子树插入导致的：左旋-右旋
代码实现
from bst import BST, BiTreeNode class AVLNode(BiTreeNode): def __init__(self, data): 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 # 更新bf if c.bf == 0: p.bf = 1 c.bf = -1 else: p.bf = 0 c.bf = 0 return c def rotate_right(self, p, c): s2 = c.rchild p.lchild = s2 if s2: s2.parent = p c.rchild = p p.parent = c # update bf if c.bf == 0: p.bf = -1 c.bf = 1 else: p.bf = 0 c.bf = 0 return c 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: # g.bf == 1 p.bf = -1 c.bf = 0 elif g.bf == 0: p.bf = 0 c.bf = 0 else: # g.bf == -1 p.bf = 0 c.bf = 1 g.bf = 0 return g def rotate_left_right(self, p, c): g = c.rchild s3 = g.lchild c.rchild = s3 if s3: s3.parent = c g.lchild = c c.parent = g s2 = g.rchild p.lchild = s2 if s2: s2.parent = p g.rchild = p p.parent = g # 更新 bf if g.bf < 0: # g.bf == 1 p.bf = 1 c.bf = 0 elif g.bf == 0: p.bf = 0 c.bf = 0 else: # g.bf == -1 p.bf = 0 c.bf = -1 g.bf = 0 return g def insert_no_rec(self, val): p = self.root if not p: self.root = AVLNode(val) return while True: if val < p.data: if p.lchild: p = p.lchild else: p.lchild = AVLNode(val) p.lchild.parent = p node = p.lchild break elif val > p.data: if p.rchild: p = p.rchild else: p.rchild = AVLNode(val) p.rchild.parent = p node = p.rchild break else: return # 更新bf while node.parent: if node.parent.lchild == node: # 左孩子 if node.parent.bf < 0: # node.parent.bf=-2 左边深 g = node.parent.parent if node.bf > 0: n = self.rotate_left_right(node.parent, node) else: n = self.rotate_right(node.parent, node) elif node.parent.bf > 0: node.parent.bf = 0 break else: node.parent.bf = -1 node = node.parent continue else: # 右孩子 if node.parent.bf > 0: # node.parent.bf=2 右边深 g = node.parent.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 = 0 break else: node.parent.bf = 1 node = node.parent continue # 旋转结束后 # 连接旋转后的子树的根和原来的树 n.parent = g if g: if node.parent == g.lchild: g.lchild = n else: g.rchild = n break else: self.root = n break tree = AVLTree([7,3,5,4,2,8,6,9,1]) tree.pre_order(tree.root) print("") tree.in_order(tree.root)
123
转载于:https://www.cnblogs.com/daofaziran/p/10371228.html
相关资源：微软等数据结构 算法面试100题全部答案集锦