高级数据结构——绪论

围绕什么是数据结构、基本概念和术语、抽象数据类型的表示和实现、算法和算法分析四个方面进行论述，提供架构。

绪论

• 数据结构的研究内容
  • 数据®逻辑结构‚®存储结构ƒ®运算
    • 数据是对客观世界的抽象反映 ‚数据集合各数据元素之间的固有关系 ƒ各数据元素在计算机中的存储关系，即数据结构在计算机中的表示（映像）
• 什么是数据结构
  • 众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容
  • 数据结构就是研究数据的逻辑结构和物理结构，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。
  • 用算法解决问题的步骤
    • 抽象出一个适当的数学模型 ‚设计一个解此数学模型的算法 ƒ用适当的程序设计语言编写出程序 „发现和排除在前几个阶段中产生的错误 问题分析®算法设计‚®程序设计ƒ®程序测试„
• 基本概念和术语
  • 数据
    • 是对信息（信息反映了客观事实），也就是客观事物的一种符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称（图像、声音等）。
  • 数据对象
    • 是性质相同的数据元素的集合。是数据的一个子集。
  • 数据结构
    • 是相互之间存在一种或多种特定关系的数据元素的集合。
  • 结构
    • 数据元素相互之间的关系，有四种基本结构
      • 集合
        • 结构中的数据元素除了“同属于一种类型”外，别无其他关系
      • 线性结构
        • 结构中的数据元素之间存在一对一的关系
      • 树型结构
        • 结构中的数据结构存在一对多的关系
      • 回状结构或网状结构
        • 结构间的数据元素之间存在多对多的关系
  • 数据元素之间所固有的相互关系称为数据的逻辑结构 数据结构子计算机中的表示（又称为映像）称为数据的物理结构，又称为存储结构。它包括数据元素的表示和关系的表示
  • 数据元素之间的关系在计算机中有两种不同的表示方法
    • 顺序表示--顺序存储结构：把逻辑上相邻的结点存储在相邻的存储单元里，结点之间的关系用存储单元的邻接关系来体现。（一般数组）
    • 非顺序表示--链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系
  • 数据结构被形式地定义为：数据结构是一个二元组
  • 算法的设计取决于逻辑结构，而算法的实现依赖于存储结构
  • 数据类型：是一个值的集合和定义在这个值表上的一组操作的总称
    • 数据类型决定： 1.数据占内存字节数 2.数据取值范围 3.其上可进行的操作
    • 原子类型：整型、实型、字符型、指针空类型 等等
    • 结构类型；数组、结构体、共用体 等等
  • 抽象数据类型：是数据类型的延伸。它定义了数据的逻辑结构以及在此结构上的一组算法。
• 抽象数据类型的表示和实现
  • 抽象数据类型是用户在固有数据类型基础上自己定义和实现的数据类型。抽象数据类型定义了一种新的数据元素集合和该集合上所允许的操作集合。一个含抽象数据类型的软件模块通常应包含定义、表示和实现。模块内部给出数据的表示和操作的细节，模块外部使用的只是抽象的数据和抽象的操作。
  • 抽象数据类型的形式化定义格式可以用一个三元组表示
  • 抽象数据类型带给算法设计的好处
    • 算法顶层设计与底层实现分离
    • 算法设计与数据结构设计隔开，允许数据结构自由选择
    • 数据模型和该模型哈撒给的运算统一在ADT中，便于空间和时间耗费折中
    • 用抽象数据类型表述的算法具有很好的可维护性
    • 算法自然呈现模块化
    • 为自顶向下逐步求精和模块化提供有效途径和工具
    • 算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析
  • 指针和引用
    • 引用是一种非常特殊的数据类型，是C++的一个特征，它不是定义一个新的变量，而是给一个已经定义的变量重新起一个别名。 C++系统不为引用类型变量分配内存空间，两者共用同一存储单元。 引用主要用于函数之间的数据传递。 指针是对象的地址，而引用时给对象的地址取一个别名。可以把它看作是一个常量指针。 引用定义的格式：<类型>&<引用名>=<已定义过的变量名>;
      • 注意：引用类型定义时必须初始化，也就是说，子啊创建一个引用时必须令它指向一个特定的合法的存储空间，并且在程序的运行过程中不能改变。
• 算法和算法分析
  • 算法：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
    • 有穷性：有穷步之后结束，每一步都在有穷时间内完成
    • 确定性：每一条指令必须有确切的含义，没有二义性
    • 可行性：算法中的操作都可用已经实现的基本操作有限次来实现
    • 输入：有零个或多个的输入
    • 输出：有一个或多个的输出，这些输出同输入有特定的关系
  • 算法设计的要求
    • 评价一个好的算法有以下标准
      • 正确性
      • 可读性
      • 健壮性
      • 算法效率
  • 算法效率的度量
    • 事先分析，事后测试
  • 算法时间关系
    • 多项式算法时间关系：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n²)<O(n³)
    • 指数时间的关系：O(2**n)<O(n!)<O(n**n)
  • 原地工作的算法：额外空间相对于输入数据量来说是常数