• 要求

（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：下列程序的时间复杂度为？

     

答案：

  这个不是二分的思想，幂次增长。