数据结构

ADT抽象数据类型

• 有两个重要特征：

1. 数据抽象：用ADT描述程序处理的实体时，强调的是器本质的特征，其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）
2. 数据封装： 将实体的外部特征和其内部实现细节分离，并且对外部用户隐藏起内部实现细节。

例如 抽象数据类型复数的定义：
ADT Complex:
数据对象：D = {e1, e2 | e1, e2 ∈ RealSet }
数据关系：R1 = {<e1, e2> | e1是复数的实数部分, | e2 是复数的虚数部分}

• 抽象数据类型的描述方法：
  • 抽象数据类型可用（D，S，P)三元组表示：其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

算法和算法的衡量

1. 算法：

• 算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要的特性：①有穷性 ② 确定性 ③ 可行性 ④ 有输入 ⑤ 有输出
  1). 有穷性：对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；
  2). 确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下算法都只有一条执行路径；
  3). 可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；
  4). 有输入：作为算法加工对象的量值，通常提现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；
  5). 有输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。

2. 算法设计的原则

• 在设计算法时，通常应考虑达到以下目标：①正确性 ②可读性 ③健壮性 ④高效率与低存储量需求
  1). 正确性：
  首先，算法应当满足以特定的“规格说明”方式给出的需求。
  其次，对算法是否“正确”的理解可以有以下四个层次：
  a. 程序中不含语法错误；
  b. 程序对与几组输入数据能够得出满足要求的结果；
  c. 程序对于精心选择的、典型、苛刻且带有刁难性的机组输入数据能够得出满足要求的结果；
  d. 程序对于一切合法的输入数据都能得出满足要求的结果；
  通常以第c层意义的正确性作为衡量一个算法是否合格的标准。
  2). 可读性：算法主要是为了人的阅读与交流，其次才是计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；
  3). 健壮性：当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
  4). 高效率与低存储量需求：通常，效率指的是算法执行的时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。

3. 算法效率的衡量方法和准则
   通常有两种衡量算法效率的方法：1. 事后统计法：缺点：①必须执行程序 ②其他因素掩盖算法本质。2. 事前估计分析法。

• 和算法执行时间相关的因素：1. 算法选用的策略 2. 问题的规模 3. 编写程序的语言 4. 编译程序产生的机器代码的质量 5. 计算机执行指令的速度