数据结构与算法

1.算法的五大特性：

- 1.输入：具有0个或1个输入、
- 2.输出：至少有一个或多个输出、
- 3.有穷性、
- 4.确定性：每一步都有确定含义，无二义性、5.可行性：每一步都是可行的

2.对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分

• 和属于同一量级，，它们的效率差不多，都为
• 这个时间复杂度可以称为

3.最坏时间复杂度

• 最优时间复杂度、最坏时间复杂度、平均时间复杂度
• 最优时间复杂度的价值并不是很大，没有提供什么有用的信息，反应比较乐观理想，没有参考价值。
• 我们经常关注的均是最坏复杂度

***4.时间复杂度的基本计算规则：[一个时间的基本单位就为1]

• 基本操作：只有常数项，认为其时间复杂度为O(1)
• 顺序结构：时间复杂度按加法进行计算
• 循环结构：时间复杂度按乘法进行计算
• 分支结构：时间复杂度**取最大值
• 判断判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略
• 在没有特殊说明时，我们所分析的算法时间复杂度都是指****

*****5.常见时间复杂度关系：

****6.所消耗的时间从小到大:

常见时间复杂度：

7.python 内置类型性能分析

• timeit模块
  • class timeit.Timer(stmt='pass',setup='pass',timer=<time function>)
  • Timer是测量小段代码执行速度的类。
  • stmt参数是要测试的代码语句（statment）；
  • setup参数是运行代码时需要的设置；
  • timer参数是一个定时器函数，与平台有关。

对于一个列表：a,b为列表
1.insert a.insert(0,10) 在指定位置插入数据,insert从头加数据
2.append a.append(10) 加在列表尾部
3.range list(range(0,10))
4.extend a.extend([2,3])
5.+ a+b

顺序表

顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。

顺序表的基本形式:

顺序表的结构：

一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。
顺序表的两种形式：

一般再python中是分离式结构。

链表

链表，将元素存放在通过链接构造起来的一系列存储块中。

单向链表：

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。

• 节点实现

  class SingleNode(object):
    """单链表的结点"""
    def __init__(self,item):
        # _item存放数据元素
        self.item = item
        # _next是下一个节点的标识
        self.next = None

• 单链表实现

  # 模拟单链表的行为
  class singleLink():
    def __init__(self):
        self.head = None
  
    # 链表是否为空
    def is_empty(self):
        if self.head is None:
            return True
        return False
  
    # 链表长度
    def length(self):
        # 创建指针，把指针指向第一个元素
        cur = self.head
  
        # 创建变量，从0开始计数
        count = 0
  
        while cur != None:
            count += 1
            cur = cur.next
  
        return count
    # 遍历整个链表,把链表的所有元素打印出来
    def travel(self):
        cur = self.head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next
        print()
  
    # 链表头部添加元素
    def add(self,item):
        node = Node(item)
        node.next = self.head
        self.head = node
  
    # 链表尾部添加元素
    def append(self,item):
        node = Node(item)
  
        if self.is_empty():
            self.head = node
        else:
            # 创建指针，指向第一个节点
            cur = self.head
            # 获取链表的最后一个元素，循环整个链表。当当前节点的next指向是None，就表示最后一个节点
            while cur.next != None:
                cur = cur.next
            cur.next = node
  
    # 指定位置添加元素
    def insert(self, pos, item):
        # pos如果小于等于0，就直接在头部加
        node = Node(item)
        if pos <= 0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            cur = self.head
            count = 0
            while count < (pos - 1):
                cur = cur.next
                count += 1
            node.next = cur.next
            cur.next = node
  
    # 删除节点  [1,2,3].remove(2)
    def remove(self, item):
        if self.is_empty():
            return []
  
        cur = self.head
        pre = None
  
        while cur.elem != item:
            pre = cur
            cur = cur.next
            if cur == None:
                return
  
        if pre == None:
            self.head = cur.next
        else:
            pre.next = cur.next
  
    # 查找节点是否存在
    def search(self,item):
        """链表查找节点是否存在，并返回True或者False"""
        cur = self._head
        while cur != None:
            if cur.item == item:
                return True
            cur = cur.next
        return False
  if __name__ == '__main__':
    link = singleLink()
    print(link.length())
    link.add(1)
    link.travel()
    link.remove(10)
    link.travel()
  
    link.append(10)
    link.append(20)
    link.travel()
    print(link.length())
    link.append(30)
    link.append(40)
    link.travel()
    print(link.length())
    link.add(99)
    link.add(200)
    link.travel()
    link.insert(3, 300)
    link.travel()
    link.insert(0, 12)
    link.travel()
    link.insert(20, 33)
    link.travel()
    link.remove(300)
    link.travel()
    link.remove(12)
    link.travel()
    link.remove(33)
    link.travel()
  
    link.search(33)

单向循环列表

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。

双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

栈

后进先出
可以用顺序表，也可以用链表实现。
栈可以实现：

• Stack() 创建一个新的空栈
• push(item) 添加一个新的元素item到栈顶
• pop() 弹出栈顶元素
• peek() 返回栈顶元素
• is_empty() 判断栈是否为空
• size() 返回栈的元素个数

队列

队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作.

只允许在一段进行插入操作，另一端进行删除操作的线性表。
同栈一样，队列也可以用顺序表或者链表实现。

队列可以实现：

• Queue() 创建一个空的队列
• enqueue(item) 往队列中添加一个item元素
• dequeue() 从队列头部删除一个元素
• is_empty() 判断一个队列是否为空
• size() 返回队列的大小

排序

转载自：https://www.cnblogs.com/Mufasa/p/10527387.html
十大经典排序：

十大经典排序的复杂度：

1.冒泡排序：

• 思想:对每个元素进行循环,依次和相邻的元素进行对比,有需要的话交换位子
  

  lst = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44]
  for i in range(0, len(lst)):
    for j in range(0, len(lst)-1-i):
        if lst[j] < lst[j+1]:
            lst[j], lst[j+1] = lst[j+1], lst[j]
  print(lst)

2.快速排序

• 【选取一个基准值，小数在左大数在在右】
• 思想:先选择一个基准值,每个元素与其进行比较,比它大的放右边，小的放左边。然后基准值固定，再以相同的逻辑对左右两边的进行排序。
  

  def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    else:
        a = lst.pop()
        llst = []
        rlst = []
        for i in range(0, len(lst)):
            if lst[i] < a:
                llst.append(lst[i])
            else:
                rlst.append(lst[i])
        return quick_sort(llst)+[a]+quick_sort(rlst)
  if __name__ == '__main__':
    lst = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44]
    print(quick_sort(lst))

3.选择排序

• 思想:从待排序的数组中选择最小的和当前的进行比较,判断是否要交换位子
  

  lst = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44]
  for i in range(0, len(lst)-1):
    for j in range(i+1, len(lst)):
        if lst[i] > lst[j]:
            lst[i], lst[j] = lst[j], lst[i]
  print(lst)

4.插入排序

• 思想:默认已经排好了顺序,从第二个开始依次与前面的进行比较.找到合适的位置进行插入.
  

  lst = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] 
  #方法一
  for i in range(1, len(lst)):
    while i > 0 and lst[i] < lst[i-1]:
        lst[i-1], lst[i] = lst[i], lst[i-1]
        i -= 1
  #方法二
  for i in range(0, len(lst)):
    for j in range(i, 0, -1):
        if lst[j] < lst[j - 1]:
            lst[j], lst[j - 1] = lst[j - 1], lst[j]
  print(lst)

5.希尔排序

6.归并排序

7.堆排序

8.计数排序

9.桶排序

10.基数排序

搜索

常见方法：顺序查找、二分法查找、二叉树查找、哈希查找

二分法查找：又称折半查找，

• 优点：查找速度快，平均性能好。

• 缺点：要求待查表为有序表，排好序的

  def digui(lst, elem):
    if len(lst) == 0:
        return False
  
    mid = len(lst)//2
    if elem == lst[mid]:
        return True
    elif elem < lst[mid]:
        return digui(lst[:mid], elem)
    elif elem > lst[mid]:
        return digui(lst[mid+1:], elem)
    else:
        return False
  lst = [2, 3, 34, 45, 56, 67, 77]
  print(digui(lst,0))

  二叉树

1.树

• 节点的度：一个节点含有的字数的个数叫该节点的度
• 树的度：一棵树中，最大的节点的度称为该树的度
• 叶子节点或终端节点：度为0的节点
• 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
• 孩子节点或子节点：一个节点含有的字数的根节点称为该节点的子节点
• 兄弟节点：具有相同 父节点的节点互称为兄弟节点
• 节点的层次：从根开始定义起，根的第一层，根的子节点为第二次，以此类推，
• 树的高度或深度：树中节点的最大层次
• 堂兄弟节点：父节点在同一层的节点互为堂兄弟
• 节点的祖先：从根到该节点所经分支上所有的节点
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙
• 森林：由m（m>0）棵互不相交的树的集合称为森林

2.树的种类：

• 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
• 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
  • 二叉树：每个节点最多含有两个子树的树称为二叉树；

    二叉树是每个节点最多两个子节点

    • 完全二叉树
      
    • 满二叉树：每层都挂满了节点
      
    • 排序二叉树/二叉搜索树/二叉查找树
      
    • 平衡二叉树
  • 霍夫曼树：（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
  • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

    3.树的存储和表示：

  • 二叉树通常以链式存储
  • 顺序存储
    
  • 链式存储
    
• 常见的应用场景：

1.xml，html等，那么编写这些东西的解析器的时候，不可避免用到树
2.路由协议就是使用了树的算法
3.mysql数据库索引
4.文件系统的目录结构
5.所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构

二叉树的遍历

• 深度优先遍历
  -深度优先一般用递归
  • 先序遍历：根节点>左子树>右子树
  • 中序遍历：左子树>根节点>右子树
  • 后续遍历：左子树>右子树>根节点
• 广度优先遍历
  • 广度优先一般用队列
  • 从树的root开始，从上到下，从左到右遍历整个树的节点