绪论

1. 数据: 对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

2. 数据元素:数据的基本单位，是数据集合的个体，由若干个数据项组成。

3. 数据对象:是性质相同的数据元素的集合，是数据的一个子集。

4. 数据结构:指相互之间存在一种或多种特定关系的数据元素集合。形式化定义为一个二元组: Data structure=(D,s)其中：D为数据结构的有限集，S是D上的关系有限集。

5. 结构:数据元素相互之间的关系。

6. 逻辑结构: 数据元素之间抽象化的相互关系。(数据结构的抽象)

逻辑结构	逻辑结构描述
集合结构	结构中的数据元素之间除了同属与一个集合的关系外，无任何其它关系
线性结构	结构中的数据元素之间存在着一对一的线性关系
树形结构	结构中的数据元素之间存在这一对多的层次关系
图状结构	结构中的数据元素之间存在着多对多的任意关系

？由结构的定义可知:结构是数据元素相互之间的关系，但从树形结构可以看出，只有其中的一部分符合一对多的关系，剩下的一部分不符合该关系，但从相互性上看，为什么会出现不平衡?

逻辑结构	实例化
线性结构	线性表、栈、队、字符串、数组
非线性结构	树、图

1. 存储结构(物理结构): 是数据结构在计算机中的表示，是逻辑结构在计算机中的存储映射，是逻辑结构在计算机中的实现，它包括数据元素的表示和数据元素之间关系的表示。

存储结构	描述
顺序存储	顺序映像用元素在存储器中的相对位置表示数据元素之间的逻辑关系。对应的顺序存储结构中的数据元素存放地址是连续的
链式存储	非顺序映像借助指示元素存储地址的指针表示元素之间的逻辑关系。对应的链式存储结构中数据元素存放地址是否连续没有要求

一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

1. 数据类型(DT): 是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围(数据对象),以及该类型中可允许使用的一组运算(关系)。

2. 抽象数据类型(ADT): 指一个数学模型以及定义在数学模型上操作。包括数据对象、数据关系、基本操作。

算法和算法分析

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

2. 算法的五大特性: 包括基本特性:有穷性、确定性、可行性和其它特性:输入、输出。

3. 算法设计的4大特性:正确性、可读性、健壮性、效率和低存储需求。

4. 程序: 算法用某种程序设计语言的具体实现。可以不满足算法的”有穷性”这个性质。例如:操作系统。

5. 时间复杂度T(n): 根据算法写成的程序在执行时耗费时间的长度。与问题的规模有关。

6. 空间复杂度S(n): 根据算法写成的程序在执行时占用存储单元的长度。与数据的规模有关。可能会出现非正常中断。

7. 分析算法时间复杂的方法有两种:事后统计的方法和事前分析估算的放法(依赖于问题的规模)

8. 算法有两部分组成:原操作和控制结构。对于算法性能的比较。通常选取一种对于所研究问题是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。

常用时间复杂度的比较:

指数型的时间复杂度比较: