什么是数据结构
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。
比如，在Python中，列表，集合，字典都是一种数据结构。
数据结构的分类
数据结构按照其逻辑可分为线性结构，树结构，图结构
列表（数组）
在其他编程语言中被称为数组，是一种基本的数据结构类型
按下标查找： O1
按值查找：On
插入删除：On
栈
image.png
队列
image.png
树与二叉树
什么是树
树是由n(n>=1)个节点组成的一个具有层次关系的集合。它具有以下特点：
每个节点有零个或多个子节点；
没有父节点的节点被称为根节点；
每一个非根节点有且只有一个父节点；
image.png
树的结构
二叉树基本概念
二叉树是每个节点最多有两个字树的树结构。通常子树被称作‘左子树’和‘右子树’。二叉树被常用语二叉查找树和二叉堆。
二叉树的第i层至多有2(i-1)个结点；深度为k的二叉树至多有2k-1个结点。
一棵深度为k，且有2^k-1个节点的二叉树称之为** 满二叉树 **；
深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为** 完全二叉树 **
image.png
三种遍历方法:
前序遍历
中序遍历
后序遍历
代码实现：
class BiTreeNode(object):
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='') # EACBDGF
pre_order(root.lchild)
pre_order(root.rchild)
pre_order(root)
print('')
# 中序遍历
def in_order(root):
if root:
in_order(root.lchild)
print(root.data,end='') # ABCDEGF
in_order(root.rchild)
in_order(root) # ABCDEGF
print('')
# 后序遍历
def post_order(root):
if root:
post_order(root.lchild)
post_order(root.rchild)
print(root.data,end='')
post_order(root) #BDCAFGE
快速排序
image.png
快排的两个关键点
归位
递归
def partition(li,left,right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp:
right -= 1
li[left] = li[right]
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left]
li[left] = tmp
return left
def quick_sort(li,left,right):
if left < right:
mid = partition(li,left,right)
quick_sort(li,left,mid-1)
quick_sort(li,mid+1,right)
import random
li = list(range(10000))
random.shuffle(li)
quick_sort(li,0,len(li)-1)
print(li)
动态规划
1块，2块，5块，10块，组成10块钱 有多少方法？
def cal(l,sum):
li = [1] + [0]*sum
for i in l:
for j in range(i,sum+1):
li[j] += li[j-i]
print(li)
return li[sum]
print(cal([1,2,5,10],10))
