《数据结构知识点总结》计算机考研复试应届生求职刷题必备.docxVIP

数据结构知识点总结 要求： （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：下列程序的时间复杂度为？ 答案： 这个不是二分的思想，幂次增长。 线性表 定义 线性表是具有相同数据类型的N（N=0）个元素的有限序列，其中N为表长，当N=0时线性表是一张空表。 线性表的逻辑特征：每个非空的线性表都有一个表头元素和表尾元素，中间的每个元素有且仅有一个直接前驱，有且仅有一个直接后继。 线性表是一种逻辑结构，表示元素之间一对一相邻的关系。顺序表（数组）和链表是指存储结构，两者属于不同的层面。 线性表的基本操作 基本操作的实现取决于采用哪种存储结构，存储结构不同，算法实现也不同，比如底层采用数据实现和链表实现，对应的代码不一样，但在上层实现算法逻辑时不关心底层具体实现，上述方法名可以直接作为伪代码使用。 线性表的顺序表示 顺序表定义 # define MaxSize 50 // 定义线性表的最大长度 typedef int ElemType; typedef struct{ ElemType data[MaxSize] ; // 顺序表的元素 int length