本文主要介绍数据结构中的一些基本知识，例如数据结构得划分、数据类型、算法等。 接下来的博客将详细介绍数据结构中的链表、栈和队列、树、查找、排序等算法。

数据结构

  1. 逻辑结构（算法设计）
  • 线性结构：线性表、栈、队列（一对一）
  • 非线性结构：树、图、集合（一对多、多对多）
  1. 存储结构（算法实现） 物理结构
  2. 数据的运算

数据元素是数据的基本单位。

数据类型

  1. 原子类型： （值不可再分）
  2. 结构类型： （值可在分）
  3. 抽象数据类型： （数据对象、数据关系、基本操作等）

线性结构

  1. 一般线性表
  2. 受限线性表 （栈、队列、串）
  3. 线性表推广 （数组、广义表）

有序表仅描述元素间的逻辑关系，属于逻辑结构。
二叉树和二叉排序树逻辑结构和存储结构相同，但数据运算不同。

算法

  1. 特性：
  • 有穷性
  • 确定性
  • 可行性
  • 输入（随便）
  • 输出（至少一个）
  1. 效率：
  • 时间复杂度：一般考虑最坏时间复杂度
  • 空间复杂度：原地工作指算法所需的辅助空间为常量，O(1)

大小关系：
O ( 1 ) &lt; O ( l o g 2 n ) &lt; O ( n ) &lt; O ( n l o g 2 n ) &lt; O ( n 2 ) &lt; O ( n 3 ) &lt; O ( 2 n ) &lt; O ( n ! ) &lt; O ( n n ) O(1)&lt;O(log_{2}^{n})&lt;O(n)&lt;O(nlog_{2}^{n})&lt;O(n^2)&lt;O(n^3)&lt;O(2^n)&lt;O(n!)&lt;O(n^n) O(1)<O(log2n​)<O(n)<O(nlog2n​)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)

整体内容如下：