数据结构

数据结构

逻辑结构分为：线性结构（一对一关系），树结构（一对多），图结构（多对多）

• 列表
  python 叫列表，其他语言叫数组，有些相似。本笔记基于 python
  线性存储
  数组与列表的不同
  1.数组元素类型相同
  2.数组长度固定

• 栈
  是限定仅在表尾（栈顶）进行插入和删除操作的线性表
  栈又称为 后进先出（Last In First Out） 的线性表，简称 LIFO 结构
  括号匹配问题

• 队列
  是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
  队列 是一种 先进先出（First In First Out） 的线性表
  环形队列
  队列的 python 内置实现
  双向队列
  实现读取文件后 5 行内容

• 栈和队列的应用——迷宫问题
  栈的实现
  思路:深度优先搜索
  队列的实现
  思路:广度优先搜索

• 链表
  创建链表
  插入和删除
  双链表
  小结：按元素值查找和按下标查找——线性表更优，插入和删除——链表更优

• 哈希表

  高效的做查找的数据结构
  直接寻址表
  哈希表：1.哈希冲突 2.开放寻址法（一般用线性探查） 3.拉链法！（连接链表）
  哈希函数
  应用：md5 算法（加密）

• 树

  树的实例——模拟文件系统

• 二叉树

  二叉树的遍历
  二叉搜索树
  概念
  平均情况：搜索的时间复杂度：O(lgn)
  最坏情况：偏科
  解决方案：1.随机化插入；2.AVL 树

• AVL 树 概念

  插入——旋转 4 种旋转情况：左左右，右右左，左右左右，右左右左
  代码——旋转实现
  代码——插入实现