Loading... # 数据结构概述 ## 基本概念 ### 数据，数据元素，数据对象 数据是客观事物的符号表示。数据元素是数据的基本单位，一个数据元素又可以由若干个数据项组成。包括两种：初等项不可分割；组合项，它又由若干个数据项组成。 数据对象是性质相同的数据元素的集合，是数据集合的一个子集。数据元素则是对象集合中的数据成员。 ### 数据结构 数据元素之间存在一种或多种特定的关系，这种关系称为结构。 Data Structure = (D, R) D为数据元素的有限集，R为数据对象中所有数据元素之间关系的有限集。 **一般表示** 1. 数据元素及数据元素之间的逻辑关系，也称为数据的逻辑结构； 2. 数据元素及数据元素之间的关系在计算机中的存储表示，也称为数据的存储结构或物理结构； 3. 数据的运算，即对数据施加的操作。 ## 数据结构分类 对于一个数据结构而言，每一个数据元素可以称为一个结点，数据结构中所包含的数据元素之间的关系就是结点之间的关系。 比如对关系<k, k'>，称k'是k的后继，k是k'的前驱，k和k'互为相邻结点。没有后继称为终端结点，没有前驱称为开始结点。 * 线性结构：一个结点最多只有一个前驱与后继。 * 非线性结构，树：一个结点最多只有一个前驱，而可以有多个后继。 * 非线性结构，图；对结点的前驱与后继数量不做限制。 存储方法： * 顺序存储：逻辑上相邻的结点存储在物理位置相邻的存储单元里。通常用数据描述 * 链接存储：结点之间的逻辑关系由附加的指针表示。 * 索引存储：在建立存储结点数据的同时还，建立附加的索引表。 * 散列存储：根据结点的关键字计算出该结点的存储地址，然后按存储地址存放该关键字对应的数据元素。 ## 数据类型 ### 基本类型与组合类型 ### 抽象数据类型 数据抽象是一种对数据和操作数据算法的抽象。数据抽象包括模块化和信息隐蔽两种抽象。 **抽象数据类型(Abstract Data Type, ADT)**是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及在逻辑结构上定义的操作。可用如下形式描述。 ``` ADT ADT_NAME { Data: /*数据说明*/ /*数据元素之间逻辑关系的描述*/ Operations: /*操作说明*/ Operation1 Input: /*对输入数据的说明*/ preconditions: /*执行操作前系统应该满足的状态*/ Process: /*对数据执行的操作*/ Output: /*对返回数据的说明*/ Postconditions: /*执行操作后系统的状态*/ Operation2 ... }/*ADT*/ ``` ## 算法和算法分析 ### 算法概念 通常人们将算法定义为一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算系列。算法应该具有以下特性： * 输入 * 输出 * 确定性 * 有穷性 * 可靠性 把一个问题的功能需求转变为一个算法，使用的方法是自顶向下，逐步求精的结构批程序设计方法。 ### 算法分析 * 正确性 * 可读性 * 健壮性 * **时间效率和存储占用量。** 用O表示复杂度，O定义：若T(n)和f(n)是定义在正整数集合上的两个函数，则$T(n)=O(f(n))$表示存在正的常数C和n0使得当$n \ge n_0$时都满足$0\le T(n) \le C \times f(n)$ (渐近)时间复杂度由$T(n) = O(f(n))$表示，而空间复杂度由$ S(n) = O(f(n))$ 表示 一般讨论最坏时间复杂度与最好时间复杂度 Last modification：January 5, 2023 © Allow specification reprint Like 如果觉得我的文章对你有用，请留下评论。