数据结构

  • 数据结构的三要素：逻辑结构、存储(物理)结构、运算

数据的逻辑结构

  • 逻辑结构反映了事物的组成结构及事物之间的逻辑关系

  • 数据的逻辑结构可以用一个二元组B=(K,R)来表示。其中K是数据结点集合，R是数据之间的二元关系，其中对于<k,k’>∈R，我们称k’为k在关系R上的后继结点；k是k’在关系R上的前驱结点

结点的类型

  • 结点的数据类型可以是基本数据类型，也可以是复合数据类型

结构的分类

  • 用R的性质来刻画数据结构的特点，并进行分类

    1. 线性结构：r称为线性关系，也称为前驱关系。每一个结点最多只有一个前驱结点和一个后继结点。e.g.数组、链表、队列
    2. 树形结构：r称为层次关系。所有结点有且仅有一个前驱，但是后继的数目不加限制
    3. 图结构：结点的前驱和后继的数目不加任何约束

  • 数学上看，树形结构和图结构的基本区别是“每个结点是否仅仅从属于一个直接前驱”而线性结构和树形结构的基本区别是“每个结点是否仅有一个直接后继”

  • 自顶向下的逻辑结构分析设计方法：先明确数据结点，及其主要关系r，然后分析数据结点的数据类型。如果数据结点的逻辑结构比较复杂，那么把他作为下一个层次

数据的存储结构

  • 数据的存储结构所要解决的问题是各种逻辑结构在计算机中的物理存储表示，建立了一种逻辑结构到物理结构的映射

  • 计算机主存储器的特点：

    1. 空间相邻：提供了一种具有非负整数地址编码、存储空间相邻的单元集合
    2. 随机访问：具有按地址随机访问存储空间内任意单元的能力，访问不同地址所需的访问时间基本相同

  • 常用的基本存储映射方法有：顺序方法、链接方法、索引方法和散列方法

顺序方法

  • 结点按地址相邻关系顺序存储，地址相邻，节点间的逻辑关系用存储单元间的自然顺序关系表达。e.g.数组

  • 顺序存储结构也称紧凑存储结构，其紧凑型指存储空间除了存储数据本身之外，没有存储其他附加信息

链接方法

  • 链接方法是在结点的存储结构中附加指针域来存储结点间的逻辑结构

  • 连接中的数据结点由两部分组成：

    1. 数据域：结点本身的数据
    2. 指针：存放其后继结点的指针

  • 多个相关结点依次连接就会形成链锁

  • 链接方法的优点是增删容易，缺点是定位困难。多用作动态而非静态

索引方法

索引方法是顺序存储的一种推广，创建由一个Z映射到存储地址域D的索引函数Y:Z->D，把结点的整数索引值映射到结点的存储地址

  • 在数据结点长度不等的情况下，索引函数就不是线整数域性函数

  • 无需扫过整个文件，可以直接定位

散列方法

  • 散列方法是索引方法的延伸，散列法用散列函数进行索引值的计算，然后通过索引表求出结点的指针地址

  • 其主要思想是根据结点的关键码来确定其存储地址；利用一种散列函数的关系把关键码的值映射到存储空间的地址

抽象数据类型

  • 抽象数据类型(ADT)可以看做是定义了一组操作的一个抽象模型。其特点是将数据和操作封装在一起

  • 抽象数据类型可以用三元组表示：(D,R,P)

ADT抽象数据类型
{
数据对象D:<数据对象的定义>
数据关系R:<数据关系的定义>
基本操作P:<基本操作的定义>
} ADT抽象数据类型名

  • D和R而这定义了数据的模型，是对数据的抽象；P是对D的基本操作集，定义了该数据模型的功用

算法

  • 算法的性质：
    1. 通用性
    2. 有效性
    3. 确定性
    4. 有穷性

算法设计

  • 算法设计方法介绍：
    1. 穷举法：穷举法的问题具有以下特点：
      1. 对象应该是有限的，有明显的穷举范围
      2. 有穷举规则，可按照某种规则列举对象
      3. 一时找不出解决问题的更好途径
    2. 回溯法：也称试探法。当发现当前候选的解不可能是解的时候，就会退到上一步重新选择下一个候选解
    3. 分治法和递归法：将大问题分割成一些规模较小的子问题
    4. 贪心法和动态规划法

算法分析

  • 算法分析是对一个算法需要多少计算时间和存储空间做定量的分析

渐进分析方法

  • 计算函数时通常只考虑大的数据，而那些不能显著改变数量级的部分都可以忽略掉。这种方法成为渐进算法分析方法，简称渐进分析

大O表示法

  • 定义：如果存在正数c和N，使得任意的n>=N，都有f(n)<=cg(n)，则称f(n)在集合O(g(n))中，或简称f(n)是O(g(n))的

  • 大O表示法提供了一种表达函数增长率从上限的方法

大Ω表示法

  • 定义：如果存在正数c和N，使得任意的n>=N，都有f(n)>=cg(n)，则称f(n)在集合Ω(g(n))中，或简称f(n)是Ω(g(n))的

  • 大Ω表示法提供了一种表达函数增长率从下限的方法

大Θ表示法

  • 如果一个函数既在集合O(g(n))中，又在集合Ω(g(n))中，则称其为Θ(g(n))

渐进分析的实例

  • 基础操作的时间代价主要有：运算、赋值、比较等等

时间和空间的折衷

  • 时空资源折衷原理：对于同一个问题求解，一般会存在多种算法。而这下算法在时间和空间开销上的优劣往往会表现出“时空折衷”的性质。为了改善一个算法的时间开销，往往可以增大空间开销为代价；反之亦然