数据的存储结构

--数据元素及其关系在计算机存储器内的表示
数据的存储结构是逻辑结构用计算机语言的实现

数据的存储结构的主要方法

  • 顺序存储方法
  • 链式存储方法
  • 索引存储方法
  • 散列存储方法(哈希存储)
    顺序存储方法表示
    a1 - a2 -a3 -a4 -a5 -a6
    结点间的逻辑关系由存储单元的邻接关系来体现
    链式存储表示方法
    a0 -a1 -a2-a3-a4
    结点间的逻辑关系通过由附加的指针字段来进行表示

数据的逻辑结构与数据的存储结构之间的关系

  • 同一种逻辑结构可以映像成不同的存储结构

  • 数据的存储结构一定要正确反映出数据元素之间的逻辑关系

    抽象数据类型

    是指一个数学模型以及定义在该模型上的一组操作
    抽象数据类型可以用三元组来进行表示
    DSP 其中 D是数据对象 S是D上的关系集 P是D的基本操作集
    抽象数据类型
    数据对象 数据对象的定义
    数据关系 数据关系的定义
    基本运算 基本运算的定义

    算法

    解决某一特定问题而采取的具体方法和步骤
    特征

  • 输入 有0个或多个输入

  • 输出 有一个或多个输出

  • 确定性 每步定义都是确切 无歧义的

  • 有穷性 算法应在执行有穷步后结束

  • 有效性 算法中的每一步都具有可行性

描述

一个算法可以用自然语言 数学语言 图形及其程序设计语言来描述
算法和程序
算法是独立于具体的计算机与具体的程序设计语言
程序是利用具体的计算机语言来描述算法
算法分析 就是衡量算法质量的优劣
算法分析的目的就是在于改进算法
算法分析主要三个方面考虑

  • 执行算法所耗费的时间 时间性能
  • 执行算法所耗费的存储空间 空间性能
  • 算法应易于理解 易于编码
  • 易于调试等等
    算法的时空性能分析
    时间复杂度