数据结构 绪论

---

数据结构基本概念

考纲内容

$\qquad$算法时间复杂度和空间复杂度的分析与计算

注意

$\qquad$重点关注算法的时间复杂度和空间复杂度的分析与计算，以及算法的效率分析。

1.1 数据结构的基本概念

1.1.1 基本概念与术语

• 数据 ： 数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
• 数据元素 ： 是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。数据项是构成数据元素的不可分割的最小单位。
• 数据对象 ： 是性质相同的数据元素的集合，是数据的一个子集。
• 数据类型 ： 是一个值的集合以及定义在此集合上的一组操作的总称
  1. 原子类型：不可再分的基本类型，如整型、实型、字符型等
  2. 结构类型：由若干个类型组合而成，是可以再分的，如结构体等
  3. 抽象数据类型（ADT）： 抽象数据组织以及与之相关的操作。ps: ADT用数学化语言定义逻辑结构，和具体实现无关。其描述了数据的逻辑结构和抽象预算，形成了一个完整的数据结构定义。
• 数据结构 ： 是相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的关系成为结构。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。
  1. 逻辑结构：数据元素之间的逻辑关系
  2. 存储结构：数据结构在计算机中的表示（又称物理结构）
  3. 数据的运算：对数据元素可以施加的操作
• $\qquad$数据的逻辑结构和物理结构密不可分，一个算法的设计取决于数据的逻辑结构，而算法的实现依赖于数据的存储结构

1.1.2 数据结构三要素

1.1.2.1逻辑结构

$\qquad$指数据元素间的逻辑关系，即从逻辑关系上描述数据。与数据的存储无关，是独立于计算机的。逻辑结构可以分为线性结构和非线性结构。

• 线性结构 ： 数据元素之间存在一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性结构包括：线性表、栈、队列、串。
• 非线性结构 ： 数据元素之间存在仅同属一个集合（集合）一对多（树）或多对多（图）的关系。非线性结构包括：树、图、集合等。

1.1.2.2存储结构（物理结构）

• 指数据结构在计算机中的表示（又称物理结构、映像）。包括数据元素的表示和关系的表示。数据的存储结构是由计算机语言实现的逻辑结构，依赖于计算机语言（有些语言不支持某些存储结构）。主要有：顺序存储、链式存储、索引存储、散列存储。
• 1. 顺序存储 ： 逻辑上将相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系由存储单元的邻接关系体现。
     $\qquad$优点： 实现随机存取，每个元素占用最少的存储空间，存储密度大。
     $\qquad$缺点： 只能使用相邻的一整块存储单元，容易产生较多的外部碎片，插入和删除操作需要移动大量元素。
• 2. 链式存储 ： 不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针表示元素间的逻辑关系。
     $\qquad$优点： 插入和删除操作方便，不需要移动元素，不会产生外部碎片，充分利用所有存储单元。
     $\qquad$缺点： 不能随机存取，只能顺序存取，每个元素需要额外的空间存储指针，存储密度小。
• 3. 索引存储 ： 在存储元素的信息同时，建立附加的索引表。索引表中的每项成为索引项，索引项一般形式为（关键字，地址）。
     $\qquad$优点： 便于元素的查找，可以快速定位元素。
     $\qquad$缺点： 增加了索引表的存储空间，降低了存储密度，增加了插入和删除操作的时间开销（此时需要修改索引表）。
• 4. 散列储存： 根据元素的关键字直接计算出该元素的存储地址，不需要进行比较和移动。又称哈希（Hash）存储
     $\qquad$优点： 检索、增加、删除结点的操作都很快。
     $\qquad$缺点： 散列函数若不合适，会出现元素存储单元的冲突，解决冲突会增加时间的空间开销。

1.1.2.3数据的运算

$\qquad$施加在数据上的运算包括运算的定义和实现。运算的定义针对逻辑结构，指出运算的功能（这个运算要做什么）。运算的实现针对存储结构，指出运算的具体操作步骤。

1.1.3 注意事项

$\qquad$注意区分存储结构和逻辑结构
$\qquad$不同逻辑结构，用不同的存储结构实现，运算实现和运算效率不同
$\qquad$不同的数据结构，逻辑结构和存储结构不一定不同
$\qquad$eg: 二叉树和二叉排序树，逻辑结构相同，但运算定义不同

1.1.4 易错点

1. $\qquad$ ADT可以定义一个完整的数据结构 - ADT用数学化语言定义逻辑结构，和具体实现无关。其描述了数据的逻辑结构和抽象运算，用三元组表示<D,S,P>(D是数据对象、S是关系集、P是对D的基本操作集)，形成了一个完整的数据结构定义。
2. $\qquad$ 逻辑结构一般说的是 栈、队列、二叉树、串这些比较抽象的结构，而物理结构一般会对其具体构造给出更具象的描述，比如： 循环队列（顺序存储）、链表（链式存储）、哈希表（散列存储）

1.2 算法

1.2.1 算法的基本概念

• 算法 ：是对特定问题求解步骤的一种描述，是指令的有限序列，并且每条指令表示一个或多个操作。

• 五大重要特性 ：

  • （1） 有穷性： 算法必须能在执行有限个步骤之后终止，并且每个步骤都可在有限时间内完成。
  • （2） 确定性： 算法中的每条指令必须有确切的含义，对于相同的输入只会得出相同的输出，不会出现二义性。
  • （3） 可行性： 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
  • （4） 输入： 一个算法有零个或多个输入，这些输入取自某个特定的对象的集合。
  • （5） 输出： 一个算法有一个或多个输出，这些输出是同输入有着某种特定关系的量。

• 一个好的算法设计的要求 ：

  • （1） 正确性： 算法应能正确地解决指定的问题。
  • （2） 可读性： 算法应具有良好的可读性，便于阅读、理解和交流。
  • （3） 健壮性： 算法对非法输入数据能做出相关处理，而不是产生异常或莫名其妙的结果。
  • （4） 高效率与低存储量需求： 算法应占用尽可能少的资源，即时间和空间。 效率指算法执行的时间，存储量指算法执行时所需要的最大存储空间。两者与问题规模有关

1.2.2 算法效率的度量

$\qquad$ 通过时间复杂度和空间复杂度来描述

1. 时间复杂度：
   $\qquad$ 一个算法的时间复杂度T(n)反映了程序运行从开始到结束所需要的时间。把算法中基本操作重复执行的次数作为算法的时间复杂度。T(n) = O(f(n))

$\qquad$加法规则： $T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$

$\qquad$乘法规则： $T(n)=T_1(n)*T_2(n)=O(f(n))+O(g(n))=O(f(n)*g(n))$
$\qquad$常见时间复杂度：$O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

2. 空间复杂度
   $\qquad$ 空间复杂度S(n)定义为该算法所消耗的存储空间，是问题规模n的函数。分析目标是算法所需的辅助空间，不包括输入输出数据和程序本身所占用的空间。若辅助空间为常数，则称算法原地工作，空间复杂度为O(1)。

1.2.3 注意事项

$\qquad$算法的时间复杂度表其执行时间与问题规模n的关系，空间复杂度表示其所需的辅助空间与问题规模n的关系。 执行时间、辅助空间 ！= 问题规模，问题规模 = n

---