绪论

数据结构的基本概念

基本概念和术语

数据

信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合

数据对象

具有相同性质的数据元素的集合，是数据的一个子集数据元素数据的基本单位，通常作为一个整体进行考虑和处理

数据项

构成数据元素的不可分割的最小单位

数据类型

数据结构的三要素

数据不是孤立的，他们存在着某种关系，这种相互关系我们叫做结构

数据结构是相互之间存在—种或多种特定关系的数据元素的集合

数据结构三要素：逻辑结构、物理结构、数据的运算

逻辑结构

分为：线性结构、非线性结构（集合、树形结构、图状结构）

与数据间的逻辑有关，与数据在计算机中如何存储无关

物理结构

也称存储结构

数据在计算机中的存储，包括数据元素在计算机中的存储、数据元素间关系的存储

分为：顺序存储、链式存储、索引存储、散列存储

数据的运算

运算（操作）包括运算的定义和实现，运算的定义针对逻辑结构，运算的实现针对存储结构

算法和算法评价

算法的基本概念

算法

对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。

算法的特性：有穷，可行，确定，输入，输出

算法效率的度量

好算法的标准

正确性算法应能够正确地解决求解问题

可读性算法应具有良好的可读性，以帮助人们理解

健壮性输入非法数据时，算法能适应的做出反应或进行处理

效率与存储量效率是指算法执行时间，存储量需求是指算法执行过程中所需最大存储空间

时间复杂度

语句频度

该条语句可能重复执行的次数

T(n)

所有语句的频度之和，其中n为问题的规模

时间复杂度

T(n)=O(f(n))，其中O表示T(n)与f(n)在\(n \rightarrow \infty\)时为同阶无穷大。即两者相同数量级。

最坏时间复杂度、最好时间复杂度、平均时间复杂度

加法规则：\(T(n)=T 1(n)+T 2(n)=O(f(n))+O(g(n))=O(\max (f(n), g(n))\)

乘法规则：\(T(n)=T 1(n) * T 2(n)=O(f(n)) * O(g(n))=O(f(n) * g(n))\)

通常采用基本运算频度（最深撑循环中语句执行次数）采分析算法时间复杂度

常见时间复杂度：

\(O(1)<O\left(\log _{2} n\right)<O(n)<O\left(n \log _{2} n\right)<O\left(n^{2}\right)<O\left(n^{3}\right)<O\left(2^{n}\right)<O(n !)<O\left(n^{n}\right)\)

空间复杂度

算法消耗的存储空间，记\(S(n)=O(g(n))\)

即，除本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储为实现算法所需的一些信息的辅助空阆。

算法原地工作时指算法所需辅助空间为常量，O（1）