数据结构的基本概念

  • 数据

    信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合

    例如：整数、实数、字符串

  • 数据元素

    数据的基本单位，通常作为一个整体进行考虑和处理

    例如：一本书的目录信息

  • 数据项/数据域

    构成数据元素的不可分割的最小单位

    例如：书目信息的每一项

  • 数据对象

    性质相同的数据元素的集合，是数据的一个子集

    例如，整数数据对象是集合 N = {0, ±1, ±2, ……}

  • 数据类型

    一个值的集合和定义在此集合上的一组操作的总称

    分为：

    1）原子类型：其值不可再分的数据类型

    2）结构类型：其值可以再分解为若干成分（分量）的数据类型

    3）抽象数据类型：抽象数据组织及与之相关的操作

  • 抽象数据类型 ADT (Abstract Data Type)

    可以看作一些数据对象以及附加在这些数据对象上的操作的集合

    重在对功能的描述而不关心具体的实现

  • 数据结构

    相互之间存在一种或多种特定关系的数据元素的集合

    二元组 (D, S) 表示：D 是数据元素的有限集，S 是 D 上关系的有限集

    三要素：逻辑结构、存储结构/物理结构/映像、数据的运算

  • 逻辑结构

    数据元素之间的逻辑关系

严蔚敏：由于高级程序设计语言中的数组类型也有随机存取的特性，因此通常都用数组来描述数据结构中的顺序存储结构

  • 存储结构/物理结构

    数据结构在计算机中的表示（映像）

    包括：数据元素的表示、关系的表示

    分为：

    1. 顺序存储

      逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现

      优点：可随机存取；存储密度大，每个元素占用最少的存储空间

      缺点：只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片；增删元素不方便

    2. 链式存储

      借助指示元素地址的指针来表示元素之间的逻辑关系

      优点：不会出现碎片现象，能充分利用所有存储单元；增删元素方便

      缺点：每个元素因存储指针而占用额外的存储空间；只能顺序存取

    3. 索引存储

      在存储元素信息的同时，还建立附加的索引表

      优点：检索速度快

      缺点：附加的索引表额外占用空间；增删元素也要修改索引表，因而会花费较多的时间

    4. 散列存储/哈希存储

      根据元素的关键字直接计算出该元素的存储地址

      散列是算法，散列存储方法本质上是顺序存储方法的拓展，散列表本质上是顺序表的拓展

      优点：检索、增加和删除结点的操作都很快

      缺点：可能出现冲突，而解决冲突会增加时间和空间开销

  • 数据的逻辑结构独立于其存储结构 √

    数据的存储结构独立于其逻辑结构 ×

    数据的存储结构是逻辑结构在计算机上的映射

  • 逻辑结构 vs 数据结构

    逻辑结构：有序表

    数据结构：顺序表（线性表的顺序存储）、单链表（线性表的链式存储）、循环队列（环状顺序队列）

    可根据 是否可以使用多种存储结构进行存储 进行区分

  • 数据的运算

    包括：运算的定义、实现

    运算的定义针对逻辑结构，指出运算的功能；运算的实现针对存储结构，指出运算的具体操作步骤

  • 随机访问 vs 顺序访问

    随机访问/直接访问：访问某记录所需的时间与该记录所在的位置无关

    顺序访问：按记录的逻辑顺序进行读、写操作的存取

    访问 = 存取 = 读 + 写

    随机访问，random access，翻译为“随意访问”感觉更贴切一点

算法和算法评价

  • 算法 Algorithm

    对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作

    由基本运算及规定的运算顺序所构成的完整的解题步骤

    按照要求设计好的有限确切的计算序列

  • 算法特性

    有穷性：有限步、每一步有限时间

    确定性：每一步有确定定义，无二义性，相同输入只能得到相同的输出

    可行性：算法中描述的所有操作可通过已实现的基本操作/纸笔进行有限次运算后完成

    输入：0 或多个

    输出：1 或多个

  • “好”的算法——算法设计目标

    正确性、可读性、健壮性、高效率、低存储量

  • 算法效率的度量

    1. 语句频度

      该语句在算法中被重复执行的次数

      算法中所有语句的频度之和记为 $T(n)$，其中 $n$ 为该算法问题的规模

    2. 时间复杂度

      主要分析 $T(n)$ 的数量级

      算法中基本运算（最深层循环内的语句）的频度与 $T(n)$ 同数量级，因此通常采用算法中基本运算的频度 $f(n)$ 来分析算法的时间复杂度，因此算法的时间复杂度记为 $T(n)=O(f(n))$

      算法的时间复杂度不仅依赖于问题的规模 $n$，也取决于待输入数据的性质，因此就有了最坏、最好、平均时间复杂度

      一般总是考虑最坏时间复杂度

    3. 空间复杂度：算法消耗的存储空间，记 $S(n)=O(g(n))$

      存储空间：除本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储为实现算法所需的一些信息的辅助空间

      原地工作：算法所需的辅助空间为常量，即 $O(1)$