数据结构基本概念

什么是数据结构

在计算机科学中,数据结构(data structure)是表示计算机中存储、组织数据的方式,逻辑结构和物理存储结构。

解决问题方法的效率:

  • 跟数据的组织方式有关
  • 跟空间的利用效率有关
  • 跟算法的巧妙程度有关

数据结构的基本功能

  • 如何插入一条新的数据项

  • 如何寻找某一特定的数据项

  • 如何删除某一特定的数据项

  • 如何迭代的访问各个数据项,以便进行显示或其他操作

抽象数据类型(ADT)

在编程语言中,常见的几个抽象数据类型如下:

  • 数组
  • 链表
  • 队列
  • 堆栈
  • 字符串

时间复杂度

常见的时间复杂度量级有:

常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)

空间复杂度

参考资料

抽象数据类型