数据结构是一门钻研 非数值 计算程序设计中操作对象，以及这些对象之间的关系和操作的学科。
-
基本概念和术语：
- 数据：形容客观事物属性的数、字符以及能输出到计算机且能被计算机程序辨认和解决的符号的汇合。数据是计算机程序加工的原材料。
- 数据元素 ：数据的 根本单位，通常作为一个整体进行思考和解决，用于残缺的形容一个对象。如：一条学生记录。
- 数据项 ：组成数据元素的不可分割的 最小单位。如：学生记录中的姓名、学号、性别等。
- 数据对象：性质雷同的数据元素的汇合，数据的一个子集。
- 数据结构 ：相互之间存在着一种或多种特定关系的数据元素的汇合，包含逻辑构造、存储构造、数据的运算。 构造 就是指数据元 素之间的关系。
- 数据类型：一个值和定义在此汇合上的一组操作的总称。原子类型（其值不可再分）、构造类型（其值能够再分为若干重量）、抽象数据类型。
- 抽象数据类型：由用户定义、示意利用问题的数学模型，以及定义在模型上的一组基本操作的总称。数据对象、其关系的汇合、其基本操作的汇合。
-
逻辑构造和存储构造：
- 逻辑构造：指数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的。分为 线性构造 （线性表）和 非线性构造（汇合、树形构造、图状构造）。
- 存储构造：又称物理构造，指数据结构在计算机中的存储示意（映像），包含数据元素的示意和关系的示意，它依赖于计算机语言。存储构造次要有：顺序存储 、 链式存储、散列存储（Hash 存储）、索引存储。
- 数据的运算：包含运算的定义和实现。运算的定义是针对逻辑构造的，指出运算的性能；运算的实现是针对存储构造的，指出运算的根本操作步骤。
-
算法：
- 定义：是对特定问题求解步骤的形容，是指令的无限序列，每条指令示意一个或多个操作步骤。
-
五大个性：
- 有穷性：算法的步骤有穷，每一步的执行工夫有穷。
- 确定性：算法中每一条指令必须有确定的含意，不会产生二义性，对于雷同的输出只能有雷同的输入。
- 可行性：算法中的操作都能够通过曾经实现的根本运算执行无限次来实现。
- 输出：一个算法有零个或多个输出。
- 输入：一个算法有一个或多个输入。必须有输入。
-
四大规范：
- 正确性：能正确的解决问题。
- 可读性：首先是便于人们了解和互相交换，其次是机器的可执行性。难懂的算法易于暗藏谬误，难于调试和批改。
- 健壮性：输出非法数据时，算法能适当地做出正确反馈或进行相应解决，不会产生一些莫名其妙的输入后果。
- 高效性：工夫高效（算法设计正当，执行效率高，用工夫复杂度来度量）和空间高效（占用存储容量正当，用空间复杂度来度量）。
-
渐进工夫复杂度：T(n) = O(f(n))
- 采纳事先剖析估算法，不是预先统计法。
- 语句频度 T(n)是指该语句在算法中被反复执行的次数。问题规模 n 是指算法求解问题输入量的多少。
- 工夫复杂度取决于：问题规模和待输出数据的性质。
- 根本语句：反复执行次数和算法的执行工夫成正比的语句，个别是最深层循环内的语句。
- 个别思考最坏工夫复杂度，运行工夫不会比它更长，所以是上界。
- 均匀工夫复杂度：指输出实例以 等概率 呈现的状况，算法计算量的加权平均值。
- O(f(n))+O(g(n))= O(max(f，g))；O(f(n)) · O(g(n))= O(f · g)。
- O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
- 常量阶：算法的执行工夫是一个与问题规模 n 无关的常数，即便常数再大，算法的工夫复杂度都是 O(1)。线性阶、平方阶、立方阶、对数阶。
-
渐进空间复杂度：S(n) = O(f(n))
- 一个程序在执行时，除了须要存储空间来寄存自身所用的指令、常数、变量和输出数据之外，还须要一些对数据进行操作的辅助存储空间。
- 算法原地工作是指算法所须要的辅助空间为常量，即 O(1)。
- 同一个算法，实现语言的级别越高，执行效率越低。