集合框架

数据结构基本概念

任何一个算法的涉及取决于算法的数据结构，而算法的实现依赖于采用的存储结构。

数据类型一个值的集合和定义在这个值集上的一组操作的总称。

数据结构的概念不仅仅局限于高级语言，每个处理器（）都提供了一种原子类型和结构类型。

数据类型的目的：

• 解释计算机内存种信息含义的一种手段，能够让用户更好的理解计算机种的信息。
• 实现信息的隐蔽，将用户不必了解的细节封装在类型种。

​ 抽象数据类型（ADT）：是指一个数据模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于他的逻辑特性，而与其在计算机内部如何表示和实现无关，即无论它内部结构如何变化，只要它的数学特性不变，都不影响外部使用。

​ 抽象数据类型和数据类型实质上是一个概念。各个计算机上都拥有的整数类型是一个抽象数据类型，经他们在不同处理器上的实现方式不同，但由于其定义的数学特性相同，在用户看来都是相同的，抽象的意义在于数据类型的数学抽象特性。

​ 另一方面，抽象数据类型的范畴更广，她不再局限于处理器种已经定义并实现的数据类型（固有数据类型），还包括用户扩展的数据类型。

​ 一个软件系统应定义在数据之上，而不是定义在操作之上。即在构成软件系统的每个相对独立的模块上，定义一组数据和施予这些数据上的一组操作，并在这些模块内部给出这些数据的内部表示及其操作的细节，而在模块的外部使用的只是抽象的数据和抽象的操作。显然，所定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的服用层度越高。

​ 一个报告抽象数据类型的软件模块通常包含定义、表示和实现三部分。

​ 抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成，若按器值域的不同特性，可分为三部分：

• 原子类型

• 固定聚合类型：值的数量固定

• 可变聚合类型：指的数量可变

  后两种可统称为结构类型。

​ 抽象数据类型可用下面三元组来表示（D，S，P），D是数据对象，S是D上的关系集，P是对D的基本操作集。相比于数据结构，多了一个P。

​ 书中定义的抽象数据类型格式：

​ ADT 抽象数据类型名{

​ 数据对象：<数据对象的定义>

​ 数据关系：<数据关系的i定义>

​ 基本操作：<基本操作的定义>

​ }

基本操作的定义格式：

​ 基本操作名（参数表）

​ 初始条件：<初始条件描述>

​ 操作结果：<操作结果描述>

基本操作由两种参数，（这里从书中走出来，结合java的概念），基本数据类型和引用数据类型。其中引用数据类型除了可以作为参数外，还可以作为返回值。

在方法种，计算数据来源：参数列表，域（静态域和实例域），魔法值，外界数据（数据库，网络）

​ 返回结果：引用参数，异常，返回值，外界（数据库，网络），域（静态与和实例域）

初始条件：描述了操作之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应的出错信息。

操作结果：正操操作之后，数据结构的变化情况和应返回的结果。若初始条件为空，则省略之。

正操的操作一般包括：

​ 增：数据的初始化

​ 删：消除数据

​ 改：更新数据的值

​ 查：根据不同条件获取对应的数据

​ 判断：判断数据的状态

在抽象数据类型定义种：数据对象的类型可以是不固定的，但是无论对于何种数据类型，数据关系是不变的，基本操作是一样的，即具有相同的数学特性，这种数据类型不同，数据关系和基本操作可变的抽象数据类型成为多形数据结构。我们在高级语言种讨论的大多都是多形数据结构。

算法的基本概念

算法是对特定问题求解步骤的一种描述。他是指令的有限序列，一个指令可以是一个或多个操作。

算法的特性：

• 输入
• 确定性
• 可行性
• 有穷性
• 输出

算法的要求：

• ​ 正确性：算法应当满足具体问题的需求。一个大型问题的需求，要以特定的规格说明方式给出，而一个实习问题或练习题，则没有那么严格，目前多数是用自然语言描述需求的，它至少要包括对于输入，输出和加工处理等的明无歧义的描述。涉及和选择算法应当能正确的满足这种需求。否则，算法的正确性的衡量准则就不存在了。

  ​ 正确的含义：

  1. 无语法错误。
  2. 程序对于几组输入数据能够得出满足规格说明要求的结果。
  3. 程序对于精心选择的，苛刻而刁难的几组输入数据能够的出满足规格说明要求的结果。
  4. 程序对于一切合法的输入都能得到满足规格说明要求的结果

  显然，达到d层意义下的正确性是极为困难的，所有不同输入数据的数量大的惊人，逐一验证的方法是不现实的。对于大型软件需要专业测试，而一般情况下，通常以c层意义的正确性作为衡量一个程序是否严格的标准。

• 可读性，优秀的可读性对于扩展维护非常重要

• 健壮性：当输入的数据非法时，算法也能适当的做出反应或进行处理，而不会产生莫名其妙的输出结果。并且，处理错误的方法应该是返回一个表示错误或错误性值的值，而不是打印错误信息或异常并终止程序运行，以便在更高抽象层次上进行处理。

  • 高效率和低存储量需求。同属的来说，效率指的是执行时间，对于一个问题如果由多个算法可以进行解决，执行时间段的算法效率高。存储量需求指的是算法执行过程种需要的最大存储空间，这两则都与问题的规模有关。

算法效率的衡量：

• 事后统计法：精确，但是sb
• 事前分析估算的方法，一个高级语言编写的程序在计算机上执行所消耗的时间取决于：
  1. 算法选用何种策略
  2. 问题的规模
  3. 书写程序的语言
  4. 编写程序所产生的机器代码的质量
  5. 机器执行命令的速度

​ 显然，对于不同的原因，不同编译程序，不同的计算机，同一种算法运行的时间不同，效率也不相同。这表明，用绝对的时间单位衡量算法的效率是不合适的。撇开这些于计算机软硬件相关的因素，一个特定的算法原型工作量的大小只依赖于问题的规模（通常用整数量n表示），换句话所，他是问题规模n的函数。

​ 一个算法是由控制结构（顺序，选择和循环3种）和原操作（固有操作类型的操作）构成，算法的效率取决于这两者的综合效果。为了比较同一问题的不同算法，通常的做法是，从算法种选择一种对于所选择的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复次数作为算法的时间量度。

​ 一般来说，算法种基本操作的重复次数是问题规模n的某个函数f(n)，算法的时间量度 T(n) = O(f(n))

它表示随时间规模n的增大，算法执行时间的增长率和f(n)的增长率相同。称作算法的时间渐进复杂度，简称时间复杂度。

​ 显然，被称作问题的基本操作的原操作是重复执行次数和算法的执行时间成正比的原操作，多数情况下他是最内层循环内的语句的原操作，他的执行次数和包含他的语句的频度相同。语句的频度指的是该语句重复执行的次数。

​ 由于算法的复杂度考虑的只是对于问题规模n的增长率，在难以精确计算基本操作的执行次数的情况下，只需求出它关于n的增长率或阶即可。

​ 有时，算法种基本操作的执行次数还随问题的输入集不同而不同。例如排序问题，输入数据的有序性就会影响算法执行的时间。而输入数据的有序性是无法把控的，那么算法的平均时间复杂度也就难以确定。所以，一般采用算法最坏情况下的时间复杂度。

算法的存储空间需求

​ 即空间复杂度。S(n) = O(f(n))

​ n为问题的规模，一个上机执行的程序除了需要存储空间来寄存本身所用的指令、常数、变量和输入数据以外，也需要对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。

​ 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间，否则要考虑输入本身所需空间（和输入数据的表示形式有关）。

​ 若额外空间对于输入数据来说是常说，则称此算法为原地工作。