数据结构算法不仅有用,更应该是每个程序员必须掌握的基本功 学习数据结构算法,可以大大拓宽我们的思维模式。掌握了数据结构与算法,我们看待问题的深度、解决问题的角度会大有不同,对于个人逻辑思维的提升,也是质的飞跃

数据结构

数据结构的定义： 数据在计算机中的存储方式， 比如列表，数组，元组，字符串等，程序= 数据结构+算法

栈

1. 定义： 只在一段进行插入和删除操作的列表

2. 特点：后进先出

3. 栈的概念： 栈底、栈顶

4. 栈的操作：

   进栈：append

   出栈：pop

   取栈顶：gettop

5. 实现栈

   1. python

      class Stack:
          
          def __init__(self):
      
              self.stack = []
          def push(self, item):
              return self.stack.append(item)
      
          def pop(self):
              return self.stack.pop()
      
          def gettop(self):
              return self.stack[-1]
      
      	def is_empty(self):
              return len(self.stack) == 0
      
      

   2. go

      后续补充
      

6. 用栈实现数据的逆置

   # 将["aaaa", "bbbbb", "ccccc"] 逆置
   def resverse(data:list):
   	s = stack()    # stack 为上面代码实现的栈
       for d in data:
       	s.append(d)
       output = []
       while not s.is_empty():
       	output.append(s.pop())
       return output
   
   

7. 用栈实现括号和html的标记

   ---
   title: gallery
   date: 2020-10-05 12:00:00
   type: "gallery"
   layout: "gallery"
   ---
   # 括号匹配
   # 假定给定的字符串中包含以下几种括号，(), [], [], 每个括号必须与其相对应的结束符号匹配
   def is_matched(expr):
       left = "([{"
       right = ")]}"
       s = Stack()
       for c in expr:
           if c in left:
               s.push(c)
           elif c in right:
               if not s.is_empty():
                   return False
               if right.index(c) != left.index(s.pop()):
                   return False
       return s.is_empty()
   
   # html标记
   
   def is_mathced_html(expr):
       
       # TODO 后续补充
       
       pass
   
   

队列

队列的定义：

• 队列是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除
• 插入的一端称为队尾，插入叫做入队
• 删除的一端叫做对头，删除动作叫做出队
• 队列性质：先进先出（参考排队买东西，先到的先买）
• 双向队列：队列两端都允许进行进队和出队操作

队列的实现

单个数组可可以实现，但是效率低下。循环使用数组来实现队列

为了开发一种健壮的队列实现方法，我们让队列的前端趋向于右端，并且让队列内的元素在底层数组的尾部“循环”，假定底层数组的长度固顶为固定值N，他比实际队列中元素的数量大。新的元素在当前队列的尾部利用入队列操作进入队列，逐步将元素从队列的前端进面插入索引为N-1的位置，接着是0的位置，接下来是索引为1的位置。循环插入

实现这种循环的方法并不困难，当从队列中删除一个元素并欲更新前面的索引时，我怕可以使用算式f=(f+1)%N进行计算。

取模操作时处理一个循环数组的理想操作

class Queue():
        DEFAULT_CAPACITY = 10
    def __init__(self):
        self._data = [None]*Queue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

    def len(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        return
        if self.is_empty():
            raise Empty("QUEUE IS EMPTY")
        return self._data[self._front]
    
    def get(self):
        """
        1. 判断是否为空
        2. 取出对头的元素
        3. 维护首位的下标
        4. 数量-1
        """
        if self.is_empty():
            raise Empty("queue is empty")

        answer = self._data[self._front]

        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data)
        self._size -= 1
        return answer

    def put(self, item):
        """
        1. 判断是否满了, 如果满了要进行扩容
        2.判断队尾的位置， 将元素加入队尾
        3. size +1
        """
        if self._size == len(self._data):
            self._resize(2*len(self._data))

        end_index = (self._front + self._size) % len(self._data)
        self._data[end_index] = item

        self._size += 1
        if self._size == len(self._data):
            self_resize(2*len(self._data))


            

2. python 中使用队列

   from queue import Queue
   
   q = Queue()
   q.put()
   q.get()
   q.queue   # 输出队列中的所有元素
   
   

队列主要用在多个进程叫数据共享，实现业务解耦，提高效率

生产这将数据放进队列， 消费者从队列中获取数据

队列与列表的区别是，列表中的数据虽然也是排列的，但是列表中的数据被取走后还会保留，而队列中的数据取走后将不会被保留

链表

python 模拟设计链表

class Node:
	"""
	单个node对象
	"""
	def __init__(self, element, next=None):
		self._element = element
		self._next = next
l = Node(1, Node(2, Node(3, Node(4))))

python 用链表实现栈

# 待补充

单项列表的反转python

# Node 为上面实现的类

数组

数组的定义

• 1.所谓数组，就是相同数据类型的元素按一定顺序排列的集合
• 2.在Java等其他语言中并不是所有的数据都能存储到数组中，只有相同类型的数据才可以一起存储到数组中。
• 3.因为数组在存储数据时是按顺序存储的，存储数据的内存也是连续的，所以他的特点就是寻址读取数据比较容易，插入和删除比较困难。

python 中list与数组的比较

• python中的list是python的内置数据类型，list中的数据类不必相同的，而数组（array）的中的类型必须全部相同。
• 2.在list中的数据类型保存的是数据的存放的地址，简单的说就是指针，并非数据
• 3.否则这样保存一个list就太麻烦了，例如list1=[1,2,3,'a']需要4个指针和四个数据，增加了存储和消耗cpu。

字典

• 注：字典类型是Python中最常用的数据类型之一，它是一个键值对的集合，字典通过键来索引，关联到相对的值，理论上它的查询复杂度是 O(1)

哈希表 (hash tables)

• 哈希表（也叫散列表），根据键值对(Key-value)而直接进行访问的数据结构。
• 它通过把key和value映射到表中一个位置来访问记录，这种查询速度非常快，更新也快。
• 而这个映射函数叫做哈希函数，存放值的数组叫做哈希表。
• 通过把每个对象的关键字k作为自变量，通过一个哈希函数h(k)，将k映射到下标h(k)处，并将此对象存储在这个位置。

具体操作过程

• 1.数据添加：
  • 把key通过哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余
  • 取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
• 2.数据查询：再次使用哈希函数将key转换为对应的数组下标，并定位到数组的位置获取value。

解决hash冲突

• 链地址法
• 再哈希法
• 建立公共溢出区
• 开放定址法

树

树的特性

• 一棵树中的任意两个结点有且仅有唯一的一条路径连通；
• 一棵树如果有n个结点，则它一定有n−1条边；
• 在一棵树中加一条边将会构成一个回路。

二叉树

• 二叉树是一种特殊的树，二叉树的特点是每个结点最多有两个儿子。
• 二叉树使用范围最广，一颗多叉树也可以转化为二叉树

满二叉树

• 二叉树中每个内部节点都有两个儿子，满二叉树所有的叶节点都有相同的深度。
• 满二叉树是一棵深度为h且有2h−1个结点的二叉树。

完全二叉树

• 若设二叉树的高度为h，除了第h层外，其他层的结点数都达到最大个数，第h层从右向左连续 缺若干个结点，则为完全二叉树。

树的特点

• 如果一棵完全二叉树的父节点编号为K,则其左儿子的编号是2K,右儿子的结点编号为2K+1
• 已知完全二叉树的总节点数为n求叶子节点个数：
  • 当n为奇数时：（n+1）/2
  • 当n为偶数时 : （n）/2
• 已知完全二叉树的总节点数为n求父节点个数：为：n/2
• 已知完全二叉树的总节点数为n求叶子节点为2的父节点个数：
  • 当n为奇数时：n/2
  • 当n为偶数时 : n/2-1
• 如果一棵完全二叉树有N个结点，那么这棵二叉树的深度为【log2（N+1）log2（N+1）】（向上取整）

二叉树的基本操作

• 前序遍历（先根，再左，最后右）
• 中序遍历（先左，再根，最后右）
• 后序遍历（先左，再右，最后根）
• 层次遍历（说不清）

前序遍历

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

      return self.pre_order(root, [])

  def pre_order(self, root, ret=[]):
      queue = [root]
      if root is None:
          return ret
      ret.append(root.val)
      self.pre_order(root.left, ret)
      self.pre_order(root.right, ret)
      return ret

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      ret, stack = [], []
      cur = root
      while cur or stack:
          while cur:
              ret.append(cur.val)
              stack.append(cur)
              cur = cur.left
          cur = stack.pop()
          cur = cur.right
      return ret

// Make sure to add code blocks to your code group

中序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      return self.mid_order(root, [])
  
  def mid_order(self, root, ret=[]):
      if not root:
          return ret
      
      self.mid_order(root.left, ret)
      ret.append(root.val)
      self.mid_order(root.right, ret)
      return ret

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      """
      中序遍历： 左---> 中---> 右
      如果有左子树，将左子树入栈，同时root的指针直到左子树
      """
      if not root:
          return []
      ret, stack = [], []
      cur = root
      while stack or cur:
          while cur:
              stack.append(cur)
              cur = cur.left
          cur = stack.pop()
          ret.append(cur.val)
          cur = cur.right
      return ret

// Make sure to add code blocks to your code group

后序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      """
      递归法
      """
      return self.after_order(root, [])
  
  def after_order(self, root, ret=[]):
      if not root:
          return ret
      
      self.after_order(root.left, ret)
      self.after_order(root.right, ret)
      ret.append(root.val)
      return ret

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      """
      迭代法
      """
      if not root:
          return []
      ret, stack = [], []
      cur = root
      while stack or cur:
          while cur:
              ret.append(cur.val)
              stack.append(cur)
              cur = cur.right
          cur = stack.pop()
          cur = cur.left

      return ret[::-1]

// Make sure to add code blocks to your code group

层序遍历

• 按照层级遍历的方法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
      """
      层序遍历
      """
      if not root:
          return []
      ret = list()
      queue = collections.deque([root])
      while queue:
          vals = list()
          for _ in range(len(queue)):
              cur = queue.popleft()
              vals.append(cur.val)
              if cur.left:
                  queue.append(cur.left)
              if cur.right:
                  queue.append(cur.right)
          ret.append(vals)
      return ret

// Make sure to add code blocks to your code group

前中后、广度优先遍历

• 树的深度优先遍历其实就是前面的三种遍历：前序遍历、中序遍历、后序遍历
• 树的广度优先遍历和层序遍历相似

// Make sure to add code blocks to your code group

class Node:
    """
    定义根节点
    """

    def __init__(self, elem, lchild=None, rchild=None):

        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild



class BinaryTree:

    def __init__(self):
        self.root = None



    def add(self, elem):

        node = Node(elem)

        if self.root is None:
            self.root = node
            return

        # 如果根节点不为None， 判断左右节点
        queue = [self.root]
        print(queue)
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)


    def bread_order(self):

        if self.root is None:
            return []

        queue = [self.root]
        ret = []
        while queue:
            cur_node = queue.pop()
            ret.append(cur_node.elem)

            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)

            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

        return ret


    def pre_order(self, root, ret=[]):

        queue = [self.root]
        if root is None:
            return ret

        #cur_node = queue.pop()
        ret.append(root.elem)

        self.pre_order(root.lchild, ret)
        self.pre_order(root.rchild, ret)
        return ret
    def mid_order(self, root, ret=[]):
        if root is None:
            return ret

        self.mid_order(root.lchild, ret)
        ret.append(root.elem)
        self.mid_order(root.rchild, ret)

        return ret



    def after_order(self, root, ret=[]):

        if root is None:
            return ret

        self.after_order(root.lchild, ret)
        self.after_order(root.rchild, ret)
        ret.append(root.elem)
        return ret


if __name__ == "__main__":

    b_tree = BinaryTree()
    b_tree.add("A")
    b_tree.add("B")
    b_tree.add("c")
    #print(b_tree.bread_order())
    print(b_tree.pre_order(b_tree.root))
    print(b_tree.mid_order(b_tree.root))
    print(b_tree.after_order(b_tree.root)

B+/-Tree

B-Tree

• 每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。
• 两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。
• 以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

'''模拟查找关键字29的过程：'''
# 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
# 比较关键字29在区间（17,35），找到磁盘块1的指针P2。
# 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
# 比较关键字29在区间（26,30），找到磁盘块3的指针P2。
# 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
# 在磁盘块8中的关键字列表中找到关键字29。

B+Tree

• B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构`。
• B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值
• 而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小
• 当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。
• 在B+Tree中，所有根节点只存储 键和指针，只有叶子节点才存放数据`

mysql索引的底层实现

• InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节
• 也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（这里的K取值为〖10〗^3）。
• 也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。
• 说明：
  • 实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。
  • mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

二分查找

def binary_search(li, target):
    low = 0
    high = len(li) -1
    
    while low < high:
        
        
    	mid = (low+high) / 2
        
        if li[mid] == target:
            return True
        if li[mid] < target:
            high = mid -1
        else:
            low = mid +1
    return False
    
    

基础算法

简单排序

前三中是很low的排序算法

冒泡排序

def bubble_sort(li):
    """
    总结：
    对于一个有i个数字的序列，完成排序需要i-1轮， 如果每轮记为i， 第j轮需要i-j次，需要两层循环，内循环几轮比较次数，外循环控制比较轮数
    """
    for i in range(len(li)-1):
        is_exchang = False
        for j in range(len(li)-i-1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                is_exchange = True
        if not is_exchange:
            break
    return li

# 时间复杂度o(n*2)
# 空间复杂度o(1)

选择排序

def select_sort(li):
    """
    总结：每一次从未序列中寻找最小元素，放在已排序序列的起始位置， 然后在未排序序列中寻找最小元素放在已排序序列的尾端
    
    """
    for i in range(len(li)-1):

        min_index = i
        for j in range(i+1, len(li)):
            if li[min_index] > li[j]:
                min_index = j
        li[i], li[min_index] = li[min_index], li[i]
    return li


# 时间复杂度o(n*2)
# 空间复杂度o(1)

插入排序

def insert_sort(li):
	"""
	每次取未排序序列的元素，在已排序序列中寻找合适位置插入
	"""
    for i in range(1, len(li)-1):

        for j in range(i, 0, -1):
            if li[j] < li[j-1]:
                li[j], li[j-1] = li[j-1], li[j]
    return li

# 时间复杂度o(n*2)
# 空间复杂度o(1)

快排

def quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)    # mid返回的是上一个用来排序那个数的下标
        quick_sort(data, left, mid - 1)
        quick_sort(data, mid + 1,right)

# 每执行一次partition函数都可以实现将某个数左边都比这个数小 右边都比这个数大
def partition(data, left, right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:     # 从右向左找小于tmp的数放到左边空位置
            right -= 1
        data[left] = data[right]                       # 将右边小于tmp值得数放到左边空位置
        while left < right and data[left] <= tmp:      # 从左向右找到大于tmp的值放到右边空位置
            left += 1
        data[right] = data[left]                       # 将右边大于tmp值得数放到右边空位置
    data[left] = tmp
    return left
# 时间复杂度0(nlogn)
# 最坏时间复杂度O（N**2）
# 空间复杂度o(1)
   

归并排序

def merge(left, right):
	"""
	对两个有序的列表进行合并
	"""
    ll = rr = 0
    result = []

    while ll < len(left) and rr < len(right):
        if left[ll] < right[rr]:
            result.append(left[ll])
            ll += 1
        else:
            result.append(right[rr])
            rr += 1
    result += left[ll:]
    result += right[rr:]
    return result

def merge_sort(data):

    if len(data) <=1:
        return data
    middle = len(data) // 2    # 从中间划分
    left = merge_sort(data[:middle])  # 将左侧列表进行排序
    right = merge_sort(data[middle:])  # 将右侧列表进行排序

    return merge(left, right)  # 归并

稳定排序和不稳定排序

稳定排序有：插入排序 (opens new window)、冒泡排序、归并排序、基数排序

不稳定排序有：选择排序 (opens new window)、快速排序、希尔排序、堆排序

首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前