-
要求
（1）对数据结构这么课学了哪些知识有个清楚的认知；
（2）掌握目录结构，能复述出来每个知识点下都有哪些内容。
如下图所示，可自行制作思维导图，针对自己薄弱的地方进行复习。
-
绪论
-
相关术语
-
绪论中会介绍数据结构的一些基本概念，要对数据模型有基本的了解。
数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。
数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。
数据对象（Data Object）或数据元素类（Data Element Class）是具有相同性质的数据元素的集合。
在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类），数据元素是数据元素类的一个实例。例如，在交通咨询系统的交通网中，所有的顶点是一个数据元素类，顶点A 和顶点B 各自代表一个城市，是该数据元素类中的两个实例，其数据元素的值分别为A 和B。
数据结构研究的三个方面
（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
（3）对各种数据结构进行的运算。
数据的逻辑结构和存储结构是密不可分的两个方面，一个算法设计取决于所选定的逻辑结构，而算法实现依赖于所采用的存储结构。
数据的逻辑结构
数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据的逻辑结构分线性结构和非线性结构。
数据的存储结构
存储结构是指数据结构在计算机中的表示，又称为映像，也叫物理结构。它包括元素的表示和关系的表示。数据的存储结构依赖于计算机，数据的存储结构主要有：顺序存储、链式存储、索引存储、散列存储。
数据的运算
施加在数据上的运算包括运算的定义与实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现针对存储结构的，指出运算的具体操作步骤。
-
算法及评价
算法是什么？
算法是对特定问题求解步骤的描述，它是指令的有限序列，其中每条指令表示一个或多个操作。算法要求能够对一定规范的输入，在有限时间内获得所要求的输出，因此一个算法也经常被封装为一个函数，用来实现特定的功能。
算法优劣的衡量标准：不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法具有五个特性：有穷性、确切性、输入、输出、可行性。
一个算法有0个或多个输入。一个算法有一个或多个输出，没有输出的算法是毫无意义的。
算法的衡量：
算法原地工作指算法所需的辅助空间未常量，即O(1)。
例题
例1：下面程序的时间复杂度是？
x = 2;while(x < n/2){x = 2*x;}答案：O(log2N)每执行一次x以二倍往上增长，注意 x < n/2与 x < n 一个量级。
含有二分的思想在里面，二分即倍数增长或倍数下降后重新赋值。因此复杂度为logn。
只要含有二分的思想就有logN。
例2：请给出下面程序的时间复杂度？
int fact(int n){if(n <= 1) return 1;return n * fact(n-1);}求阶乘的递归函数，一共执行了n次的量级，故时间复杂度为O(N)。
例3：下列程序的时间复杂度为？
count = 0;for(k = 1; k <=n; k*=2){for(j = 1; j<=n; j++){coun++;}}分析下count++的执行次数在什么量级上，答案为：O(N*logN)。
例4：下列程序的时间复杂度为？
答案：
这个不是二分的思想，幂次增长。
