DS知识点总结

数据结构知识点汇总(考研C++版)

一、绪论

1.1 数据结构的基本概念

1.1.1 基本概念和术语

1、数据

​ 数据是信息的载体，所有输入到计算机识别的符号集合。

2、数据元素

​ 数据元素是数据的基本单位，一个数据元素可以由若干个数据项组成，例如：一个学生记录为一个数据元素。

3、数据对象

​ 数据对象是对于同类型的数据元素的集合，例如整数集、小数集合等。

4、数据类型

​ 数据集合是集合以及定义在该集合上的一组操作的统称，主要包含以下三种类型：

• 原子类型：(原子不可再分)值不可以再分的数据
• 结构类型：值可以再分成若干成分的数据类型
• 抽象数据类型：一种数学模型以及定义在该数学模型上的一组操作，他通常是对数据的某种抽象。

5、数据结构

​ 数据结构是相互作用存在的一种或者集中特定关系的数据元素的集合，数据结构主要包含三方面的内容：逻辑结构、存储(物理结构)、数据的运算。

1.1.2 数据结构三要素

1、数据的逻辑结构

​ 数据的逻辑结构独立于计算机的存储结构，主要包含线性结构和非线性结构，线性表是线性结构典型代表，集合、、树、图等都是非线性结构。数据的逻辑结构分类如下图所示：

​ 集合：结构中的元素除了“同属于一个集合”外，别无其他关系，如图所示：

​ 线性结构：结构中的元素只存在一对一的关系，如图所示：

​ 树形结构：结构中的元素存在一对多的关系，如图所示：

​ 网状结构(图状结构)：结构中的元素存在多对多的关系，如图所示：

2、数据的存储结构

​ 存储结构又称为物理结构，包含数据元素的表示以及元素的关系表示，主要存储结构包含顺序存储、链式存储、索引存储、散列存储。

• 顺序存储：顺序存放在内存临近的位置，元素之间的关系是由存储单元的相邻关系提现，优点是可以实现随机存取，缺点是外部碎片较多；

• 链式存储：逻辑上不相邻的元素也可以实现物理相邻，不要求逻辑相邻的元素物理也相邻，借助指示元素存储地址的指针来表示元素之间的关系，优点是不会出现碎片，可以充分利用所有的存储单元，缺点是每个元素需要额外的存储空间，且只能实现顺序存储；

• 索引存储：建立存储数据的信息时，同时需要建立额外的存储索引表来记录各个记录的地址，索引表的记录结构是：key关键字名称：value：关键字地址，优点是检索速度快，缺点是索引表需要占用额外的存储空间，另外增加和删除索引表的时候，也需要遍历整个索引表；

• 散列存储(哈希Hash存储)：通过存储元素的关键字来直接计算出存储单元的地址，优点是检索、增加、删除关键字的速度很快，缺点是查询的时候若哈希函数不好的话，会出现多次元素存储单元冲突，解决冲突会增加时间和空间开销；

  

1.2 算法和算法评价

1.2.1 算法的基本概念

​ 算法(Algorithm)是对某个特定问题的求解步骤一种描述，算法的五个重要特性：

1） 有穷性：算法必须在有限步骤内完成，且必须在有穷时间内完成；

2） 确定性：算法中的每个步骤都必须有确切的含义，同时相同的输入只能有一个输出；

3） 可行性：算法是可以通过现有的基本运算来完成；

4） 输入：算法可以有一个或者多个输入

5） 输出：算法可以有一个或者多个输出

描述完上述五个基本的算法特性，现说一下“好”算法的四个基本特性：

• 正确性：能够正确解决问题
• 健壮性：算法对于任何隔路的输入都能正确处理，不会报错
• 可读性
• 高效率、低存储

1.2.2 算法效率的度量

​ 1、时间复杂度

​ 在时间上算法语句被重复执行的次数称为频数，算法中所有的频数之和记为T(n)，时间复杂度主要是分析和T(n)的数量级，常见的算法时间复杂度：
$$O(1)<O({\log }_{2}n)<O(n)<O(n{\log }_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$
​ 2、空间复杂度

​ 算法执行过程需要存储的空间数量称为空间复杂度S(n)。

1.3 计算时间复杂度的方法及例题

1、时间复杂度的计算方法

• 循环体中的变量语句参与循环条件的判断

​ 首先找出执行次数t和循环变量之间的关系，接着解出执行次数和问题规模的关系式

int i = 1；
    while(i<=n)
        i=i*2

上述代码中循环体语句变量参与到了循环语句，接下来要找到循环体中的执行次数和问题规模n之间的关系，设执行此处为t,2的t次方<=问题规模n，反解出t<=log2n,故T(n)=O(log2n)

• 循环语句中的变量不参与循环条件的判断

可以采用数学归纳法，此类问题分为递归程序和非递归程序

​ 1)、递归程序使用公式进行递推，时间复杂度的分析如下：
$$T(n)=1+T(n-1)=1+1+T(n-2)=\cdots =n-1+T(1)$$
​ 2)、非递归则采用累计计算次数的方式

2、例题