数据结构&快排&动态规划

什么是数据结构

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。

简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。
比如，在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))