what 数据结构?
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成
简单来说, 数据结构就是设计数据以何种方式组织并存储在计算机中
比如: 列表集合与字典等都是一种数据结构
N.Wirth: 程序 = 数据结构 + 算法
数据结构按照其逻辑结构可分为线性结构树结构图结构
线性结构: 数据结构中的元素存在一对一的相互关系
树结构: 数据结构中的元素存在一对多的相互关系
图结构: 数据结构中的元素存在多对多的相互关系
列表
在其他编程语言中称为数组, 是一种基本的数据结构类型
栈
栈 (Stack) 是一个数据集合, 可以理解为只能在一端进行插入或删除操作的列表
栈的特点: 后进先出(last-in, first-out)
栈的概念: 栈顶 栈底
栈的基本操作:
进栈(压栈):push
出栈: pop
取栈顶: gettop
栈的 Python 实现
不需要自己定义, 使用列表结构即可
进栈函数: append
出栈函数: pop
查看栈顶函数: li[-1]
栈的应用括号匹配问题
括号匹配问题:
给一个字符串, 其中包含小括号中括号大括号, 求该字符串中的括号是否匹配
例如:
()()[]{} 匹配
([{()}]) 匹配
[]( 不匹配
[(]) 不匹配
- def brace_match(s):
- stack = []
- match = {):(, ]:[, }:{}
- match2 = {(:), [:], {:}}
- for ch in s:
- if ch in {(, [, {}:
- stack.append(ch)
- elif len(stack) == 0:
- print("缺少 %s" % match[ch])
- return False
- elif stack[-1] == match[ch]:
- stack.pop()
- else:
- print("括号不匹配")
- return False
- if len(stack) > 0:
- print("缺少 %s" % (match2[stack[-1]]))
- return False
- return True
- brace_match("[{()[]}{}{}")
- View Code
队列
队列 (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
创建队列: queue = deque(li)
进队: append
出队: popleft
双向队列队首进队: appendleft
双向队列队尾进队: pop
栈的应用迷宫问题
给一个二维列表, 表示迷宫 (0 表示通道, 1 表示围墙) 给出算法, 求一条走出迷宫的路径
- 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]
- ]
解决思路
在一个迷宫节点 (x,y) 上, 可以进行四个方向的探查: maze[x-1][y], maze[x+1][y], maze[x][y-1], maze[x][y+1]
思路: 从一个节点开始, 任意找下一个能走的点, 当找不到能走的点时, 退回上一个点寻找是否有其他方向的点
方法: 创建一个空栈, 首先将入口位置进栈当栈不空时循环: 获取栈顶元素, 寻找下一个可走的相邻方块, 如果找不到可走的相邻方块, 说明当前位置是死胡同, 进行回溯(就是讲当前位置出栈, 看前面的点是否还有别的出路)
- 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-1,y), #上
- lambda x,y:(x,y+1), #右
- lambda x,y:(x+1,y), #下
- lambda x,y:(x,y-1), #左
- ]
- def solve_maze(x1, y1, x2, y2):
- stack = []
- stack.append((x1,y1))
- maze[x1][y1] = 2
- while len(stack) > 0: # 当栈不空循环
- cur_node = stack[-1]
- if cur_node == (x2,y2): #到达终点
- for p in stack:
- print(p)
- return True
- for dir in dirs:
- next_node = dir(*cur_node)
- if maze[next_node[0]][next_node[1]] == 0: #找到一个能走的方向
- stack.append(next_node)
- maze[next_node[0]][next_node[1]] = 2 # 2 表示已经走过的点
- break
- else: #如果一个方向也找不到
- stack.pop()
- else:
- print("无路可走")
- return False
- def solve_maze2(x1,y1,x2,y2):
- queue = deque()
- path = [] # 记录出队之后的节点
- queue.append((x1,y1,-1))
- maze[x1][y1] = 2
- while len(queue) > 0:
- cur_node = queue.popleft()
- path.append(cur_node)
- if cur_node[0] == x2 and cur_node[1] == y2: #到终点
- real_path = []
- x,y,i = path[-1]
- real_path.append((x,y))
- while i >= 0:
- node = path[i]
- real_path.append(node[0:2])
- i = node[2]
- real_path.reverse()
- for p in real_path:
- print(p)
- return True
- for dir in dirs:
- next_node = dir(cur_node[0], cur_node[1])
- if maze[next_node[0]][next_node[1]] == 0:
- queue.append((next_node[0], next_node[1], len(path)-1))
- maze[next_node[0]][next_node[1]] = 2 # 标记为已经走过
- else:
- print("无路可走")
- return False
- solve_maze2(1,1,8,8)
- View Code
队列的应用迷宫问题
思路: 从一个节点开始, 寻找所有下面能继续走的点继续寻找, 直到找到出口
方法: 创建一个空队列, 将起点位置进队在队列不为空时循环: 出队一次如果当前位置为出口, 则结束算法; 否则找出当前方块的 4 个相邻方块中可走的方块, 全部进队
链表
链表中每一个元素都是一个对象, 每个对象称为一个节点, 包含有数据域 key 和指向下一个节点的指针 next 通过各个节点之间的相互连接, 最终串联成一个链表
- class Node(object):
- def __init__(self, item):
- self.item = item
- self.next = None
- class Node:
- def __init__(self, data):
- self.data = data
- self.next = None
- # 头插法
- def create_linklist(li):
- head = None
- for num in li:
- node = Node(num)
- node.next = head
- head = node
- return head
- # 尾插法
- def create_linklist_tail(li):
- head = None
- if not li:
- return head
- head = Node(li[0])
- tail = head
- for num in li[1:]:
- node = Node(num)
- tail.next = node
- tail = node
- return head
- def print_linklist(head):
- node = head
- while node:
- print(node.data)
- node = node.next
- linklist = create_linklist_tail([1,2,3,4])
- print_linklist(linklist)
- View Code
遍历链表:
链表节点的插入和删除
插入:
- p.next = curNode.next
- curNode.next = p
删除:
- p = curNode.next
- curNode.next = curNode.next.next
- del p
双链表
双链表中每个节点有两个指针: 一个指向后面节点一个指向前面节点
- class Node(object):
- def __init__(self, item=None):
- self.item = item
- self.next = None
- self.prior = None
- View Code
双链表节点的插入和删除
插入:
- 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
哈希表
哈希表 (Hash Table, 又称为散列表), 是一种线性表的存储结构哈希表由一个顺序表(数组) 和一个哈希函数组成哈希函数 h(k)将元素 k 作为自变量, 返回元素的存储下标
简单哈希函数:
除法哈希: h(k) = k mod m
乘法哈希: h(k) = floor(m(kA mod 1)) 0<A<1
假设有一个长度为 7 的数组, 哈希函数 h(k)=k%7 元素集合 {14,22,3,5} 的存储方式如下图
哈希冲突
由于哈希表的大小是有限的, 而要存储的值的总数量是无限的, 因此对于任何哈希函数, 都会出现两个不同元素映射到同一个位置上的情况, 这种情况叫做哈希冲突 比如 h(k)=k%7, h(0)=h(7)=h(14)=...
解决哈希冲突开放寻址法
开放寻址法: 如果哈希函数返回的位置已经有值, 则可以向后探查新的位置来存储这个值
线性探查: 如果位置 i 被占用, 则探查 i+1, i+2,
二次探查: 如果位置 i 被占用, 则探查 i+12,i-12,i+22,i-22,
二度哈希: 有 n 个哈希函数, 当使用第 1 个哈希函数 h1 发生冲突时, 则尝试使用 h2,h3,
解决哈希冲突拉链法
拉链法: 哈希表每个位置都连接一个链表, 当冲突发生时, 冲突的元素将被加到该位置链表的最后
哈希表在 Python 中的应用
字典与集合都是通过哈希表来实现的
在 Python 中的字典: a = {name: ctz, age: 18, gender: Man}
使用哈希表存储字典, 通过哈希函数将字典的键映射为下标假设 h(name) = 3, h(age) = 1, h(gender) = 4, 则哈希表存储为[None, 18, None, ctz, Man]
在字典键值对数量不多的情况下, 几乎不会发生哈希冲突, 此时查找一个元素的时间复杂度为 O(1)
二叉树
树是一种数据结构 比如: 目录结构
树是一种可以递归定义的数据结构 树是由 n 个节点组成的集合:
如果 n=0, 那这是一棵空树;
如果 n>0, 那存在 1 个节点作为树的根节点, 其他节点可以分为 m 个集合, 每个集合本身又是一棵树
一些概念
根节点
叶子节点
树的深度(高度)
树的度
孩子节点 / 父节点
子树
二叉树: 度不超过 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
二叉树的遍历: 前序遍历 中序遍历 后序遍历 层次遍历
- 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
- # 前序遍历
- def pre_order(root):
- if root:
- print(root.data, end=)
- pre_order(root.lchild)
- pre_order(root.rchild)
- #EACBDGF
- # 中序遍历
- def in_order(root):
- if root:
- in_order(root.lchild)#a
- print(root.data, end=)
- in_order(root.rchild)
- #ABCDEGF
- # 后序遍历
- def post_order(root):
- if root:
- post_order(root.lchild)
- post_order(root.rchild)
- print(root.data, end=)
- #BDCAFGE
- def level_order(root):
- 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)
- #EAGCFBD
- pre_order(root)
- print("")
- in_order(root)
- print("")
- post_order(root)
- print("")
- level_order(root)
- EACBDGF
- ABCDEGF
- BDCAFGE
- EAGCFBD
- View Code
二叉搜索树
二叉搜索树是一颗二叉树且满足性质: 设 x 是二叉树的一个节点如果 y 是 x 左子树的一个节点, 那么 y.key x.key; 如果 y 是 x 右子树的一个节点, 那么 y.key x.key.
AVL 树: AVL 树是一棵自平衡的二叉搜索树
AVL 树具有以下性质:
根的左右子树的高度之差的绝对值不能超过 1
根的左右子树都是平衡二叉树
AVL 的实现方式: 旋转
B 树(B-Tree):B 树是一棵自平衡的多路搜索树常用于数据库的索引
来源: http://www.bubuko.com/infodetail-2486580.html