什么时数据结构？
数据结构是指相互之间存在着一种或者多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。
比如：列表、集合与字典都是一种数据结构。
还是那句话：程序=数据机构+算法
数据结构的分类：
数据结构按照其逻辑结构可分为线性结构、数结构、图结构
线性结构：数据结构中的元素存在一对一的相互关系
树结构：数据结构中的元素存在一对多的相互关系
图结构：数据结构中的元素存在多对多相互关系
列表：在其它编程语言中称为‘数组’，是一种基本的数据结构类型。
它使用顺序存储。
栈：
栈是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。
栈的特点：后进先出。
栈的概念：
栈顶
栈底
栈的基本操作：
进栈：push
出栈：pop
取栈顶：gettop
例子：
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("[{()[]}{}{}")
队列：
队列是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。
进行插入的一端称为队尾，插入动作称为进队或入队。
进行删除的一端称为对头，删除动作称为出队。
队列的性质：先进先出。
双向队列的性质：队列的两端都允许进行进队和出队操作。
环形队列：
环形队列的概念：
迷宫问题：
两种方法：
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): """ 方法一 :param x1: :param y1: :param x2: :param y2: :return: """ stack = [] stack.append((x1,y1))#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 #把放入的元素设置为2 while len(queue) > 0: cur_node = queue.popleft()#把元素从左边放出来 path.append(cur_node)#把这个放到path里面 if cur_node[0] == x2 and cur_node[1] == y2: #到了终点，我们用回溯找路径 print(path) 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_maze(1,1,8,8)
链表：
建立链表：
头插入法和尾插入法：
一般的插入和删除方法：
双链表：
列表与链表的时间复杂度：
按元素值查找 O(N)
按小标查找O(N)
在某元素后插入O(1)
删除某元素O(1)
哈希冲突：
解决这个问题：
方法一：
方法二：
二叉树：
根据根节点的先后顺序分前中后序遍历。
创建二叉树：
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) 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='') 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) pre_order(root) print("") in_order(root) print("") post_order(root) print("") level_order(root)
贪心算法：(找零钱)
# greedy algorithm money = [100,50,20,5,1] def change_money(x): change = [0,0,0,0,0] for i,m in enumerate(money): change[i] = x // money[i] x = x % money[i] if x > 0: print("还剩%s" % x) return change print(change_money(356.2))
斐波那切数列：
def fib(n): f = [1,1] for i in range(2, n+1): f.append(f[-1]+f[-2]) print(f) return f[n] fib(5)
动态规划里面的最长上升子序列：
def LIS(x): F = [0 for _ in range(len(x))] p = [-1 for _ in range(len(x))] # 初始化 F[0] = 1 p[0] = -1 for k in range(1, len(F)): max_loc = -1 max_num = 0 # 内层循环表示F[0:k]里所有小于x[k]的对应位置的F[i]的最大值 for i in range(0, k): if x[i] < x[k]: if F[i] > max_num: max_loc = i max_num = F[i] F[k] = max_num + 1 p[k] = max_loc max_i = 0 for i in range(1,len(F)): if F[i] > F[max_i]: max_i = i lis = [] i = max_i while i >= 0: lis.append(x[i]) i = p[i] lis.reverse() return lis print(LIS([9,7,2,8,3,5,2]))
最大子序列：(不要求连着)
def LCS(x, y): F = [[0 for _ in range(len(y)+1)] for _ in range(len(x)+1)] p = [[0 for _ in range(len(y)+1)] for _ in range(len(x)+1)] for i in range(1, len(x)+1): p[i][0] = 2 for j in range(1, len(y)+1): p[0][j] = 1 # 0 斜向 1 横向 j-1 2竖向 i-1 for i in range(1, len(x)+1): for j in range(1, len(y)+1): if x[i-1] == y[j-1]: F[i][j] = F[i-1][j-1]+1 p[i][j] = 0 else: #F[i][j] = max(F[i-1][j], F[i][j-1]) if F[i-1][j] > F[i][j-1]: F[i][j] = F[i-1][j] p[i][j] = 2 else: F[i][j] = F[i][j-1] p[i][j] = 1 lcs = [] i = len(x) j = len(y) while i > 0 or j > 0: if p[i][j] == 0: lcs.append(x[i-1]) i -= 1 j -= 1 elif p[i][j] == 1: j -= 1 else: i -= 1 lcs.reverse() return lcs #return F[i][j] print(LCS("ABBCBDE", "DBBCDB"))
最长公共子序列：(要求连着)
def LCSS(x, y): F = [[0 for _ in range(len(y)+1)] for _ in range(len(x)+1)] p = [[0 for _ in range(len(y)+1)] for _ in range(len(x)+1)] # 0 不匹配 1匹配 for i in range(1, len(x)+1): for j in range(1, len(y)+1): if x[i-1] == y[j-1]: F[i][j] = F[i-1][j-1]+1 p[i][j] = 1 else: F[i][j] = 0 p[i][j] = 0 max_val = 0 max_i = 0 max_j = 0 for i in range(1, len(x)+1): for j in range(1, len(y)+1): if F[i][j] > max_val: max_val = F[i][j] max_i = i max_j = j #tracback lcss = [] i = max_i j = max_j while p[i][j] == 1: lcss.append(x[i-1]) i -= 1 j -= 1 lcss.reverse() return lcss print(LCSS("ABBCBDE", "DBBCDB"))