1. 数据结构基本知识

数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

2. 数据结构基本功能

  • 如何插入一条新数据项
  • 如何寻找某一特定项
  • 如何删除某一特定项
  • 如何迭代的访问各个数据，以便进行显示或其他操作。

3. 常用的数据结构

数据结构 优点 缺点
数组 插入块 查找慢，删除慢，只能存储单一元素
有序数组 比无序数组查询快 插入慢，删除慢，大小固定，只能存储单一元素
栈 提供后进先出的存取方式 存取其他项很慢
队列 提供先进先出的存取方式 存取其他项很慢
链表 插入快，删除快 查找慢
二叉树 如果树是平衡的，则查找，插入，删除都很快 删除算法复杂
红黑树 查找，删除，插入都很快，树总是平衡的，算法复杂 算法复杂
2-3-4 树 查找，删除，插入都很快，树总是平衡的，类似的树对磁盘存储有效 算法复杂
哈希表 如果关键字已知，则存取非常快 删除慢，如果不知道关键字存取慢，对存储空间使用不充分
堆 插入，删除快，对最大数据项存取快 对其他数据项存取慢
图 对现实世界建模 有些算法慢且复杂