第八章 抽象数据类型与子程序

1.抽象数据类型：属性（数据和操作）明确地与特点地实现分离的容器。

• 数据结构：一种抽象数据类型中的复合数据域的实现。

• 容器：存放和其他操作其他对象的对象。

  2.栈

• 栈和队列是抽象复合结构，二者常被同时提及，因为它们的行为完全不同，一定是因为一些历史原因。
  • 栈是一种复合结构，只能从一端访问栈中的元素。可以在第一个位置插入元素，也可以删除第一个元素。这种设计模拟了日常生活中的很多事情。会计师称它为LIFO，即后进先出（Last In First Out）的缩写。

  • 把栈比作自助餐厅的餐具架，使它插入和删除操作有了个惯用语，插入操作叫做Push(推进)，删除操作叫做Pop（弹出）。栈没有长度属性，所有没有返回栈中项目个数的操作。

    3.队列

    -队列也是种抽象结构，队列的项目从一端入，从另一端出。会计师称之为FIFO,即先进先出(Fast In First Out)的缩写。插入操作在队列的rear（尾部）进行，删除操作在对列的front（头部）进行。
• 与栈一样，插入操作没有任何约束，整个FIFL行为都体现在删除操作上。无相关术语。Enqueue,Enque,Enq,Enter和Insert都可以表示插入操作。Dequeue，Deque，Deq和Remove都可以表示删除操作。

• 下面的算法读入数据后按照输入顺序进行输出。
  WHILE(more data)
  Read value
  Enque(myQueue,value)
  WHILE(NOT IsEmpty(myQueue))
  Deque(myQueue,value)
  Write value

  3列表

• 列表有三个特征属性：项目是同构的，项目是线性的，列表是变长的。
  • 线性：每一个项目除了第一个都有一个独特的组成部分在它之前，除了最后一个也都有一个独特的组成部分部分在它之后。
  • 不要把列表误认为是数组，数组是内嵌结构，列表是抽象结构。
  • 列表也可以被形象化为链式结构，链式结构以节点的概率为基础。

  • 补充：链式结构：一个将数据项和找到下一个位置的信息保存到同一容器的实现方法。
    下面这段算法从文件中读取值，将值放到列表中，之后输出列表。
    WHILE(more data)
    Read value
    Insert(myList,value)
    Reset(myList)
    Write"liteme in the list are"
    WHILE（Moreltems(myList))
    GetNext（myList,nextltem)
    Write nextltem,"

    4树

    -像列表，栈和队列这样的抽象结构本质上都是线性的，只模拟了一种数据关系。列表中的项目一个接着一个，栈和队列中的项目从时间来说也是一个挨着一个的。更复杂的关系需要更复杂的结构来表示
    这种分层体系结构叫做树。在计算领域，我们所说的通常是二叉树，即每个节点最多有两个子节点的树。

    二叉树

• 二叉树是一种抽象结构，其中每个节点可以有两个后继节点，叫做子女。每个子女又可以仍然是二叉树的节点，因此也可以有俩个子节点，以此类推，就形成了树的分支结构。树的头部是一个起始节点，叫做根，它不是任何节点的子女。
  • 二叉树：具有唯一起始节点的抽象复合型结构，其中每个节点可以有两个子女节点，根节点和每个节点之间都有且只有一条路径。
  • 根：树中唯一的开始节点。

  • 叶节点：没有子女的树节点。

    二叉检索树。

• 二叉检索树就像已经排序的列表，节点间存在语义排序。

• 二叉检索树具有二叉树的形状属性，还具有语义属性来刻画树中节点上的值，即任何节点都有大于它的左子树中的所有节点的值，并且要小于它的右子树中的所有节点的值。

  在二叉检索树中搜索

• 如果current指向一个节点，那么info(current)指的就是这个节点中的用户数据，left指向的是current的左子树的根节点，right指向的是current的右子树的根节点。
  IsThere(tree,item)
  IF(tree is null)
  RETURN TURE
  ELSE
  IF(Item equals info(tree))
  RETURN TURE
  ELSE
  IF(Item<info(tree))
  IsThere(left(tree),item)
  ELSE
  IsThere(right(tree),item)

  构造二叉检索树

  IF(tree is null)
  Put item in tree
  ELSE
  IF (item<info(tree))
  Insert(left(tree),item)
  ELSE
  Insert(right(tree),item)

  输出二叉检索树中的数据

  要输出根的值，必须先输出它的左子树中的所有值。右子树也如此。

  其他操作

  IF（tree)
  RETURN 0
  ELSE
  RETURN Length(left(tree))+Lenghth(right(tree))+1

  5.图

• 图：一组节点和一组把节点相互连接起来的边构成的数据结构。
• 顶点：图中的节点。
• 边（弧）：表示图中两个节点的连接的顶点对。
• 无向图：其中的边没有方向的图。

• 有向图：其中的边是从一个顶点指向另一个顶点的图。

  6.创建图

• 创建一个表格需要以下操作：
  • 在表格中添加一个点
  • 在表格中添加一条边

  • 在表格中添加一个权值

    7.图算法

    三个问题
• 我能否搭乘喜爱的航线从城市x前往城市y？
• 我怎样用最少的停顿从城市x前往城市y？

• 从城市x到城市y最短的航程是什么？
  这三个问题的答案包括了深度优先搜索，广度优先搜索和单源最短路搜索。

  深度优先搜索

  Set found to FALSE
  Push(myStack,startVertex)
  WHILE(NOT Isempty(myStack)AND NOT found)
  Pop(myStack,tempVertex)
  IF(tempVertex,equals endVertex)
  Write endVertex
  Set found to TRUE
  ELSE IF (tempVertex not visuted)
  Write tempVertex
  Push all unvisited vertices adjacent with tempVertex
  Mark tempVertex as visited
  IF(found)
  Write"Path has been printed"
  ELSE
  Write"Path does not exist"

  广度优先搜索

  Set found to FALSE
  Enque(myQueue,startVertex)
  WHILE(NOT IsEmpty(myQueue)AND NOT found)
  Deque(myQueue,tempVertex)
  IF(tempVertex equals endVertex)
  Write endVertex
  Set found to TRUE
  ELSE IF (tempVertex not visited)
  Write tempVertex
  Enque all unvisited vertices with tempVertex
  Mark tempVertex as visited
  IF(found)
  Write"Path has been printed"
  ELSE
  Write"path does not exist"

  单源最短路搜索

  最小行程次数的航线并不意味着是最短的总距离。

  8.子程序

• 如果一个子程序需要传递信息，调用单元将会把值发送给子程序来使用。
  Setx to m*sin(t)
  Set to abs(z)
  假设已经检验过这些算法中的抽象数据类型的容量：
  WHILE(more data)
  Read value
  Insert(myList,value)
  Reset(myList)
  Write"Itens in the list are"
  WHILE(Moreltems(myList))
  GetNext(myList,nextltem)
  Write nextltem,""

  参数传递

• 参数列表：程序中两部分之间的通信机制。
• 形参：列在子程序名后的括号中的标识符。

• 实参：子程序调用中列在括号中的标识符。
  //Subprogram definition
  Set list.values(list.length-1) to definition
  Set list.length to list.length+1

Insert(myList,value) //Calling statement

值参与引用参数

• 值参：由调用单元传入实参的副本的形参。

• 引用参数：由调用单元传入实参的地址的形参。
  Set temp to item2
  Set item2 to item1
  Set item1 to temp
  getlength(list)
  RETURN list.length
  IsThere(list,item)
  Set position to 0
  WHILE(position<list.length AND list,values(position)!=item)
  Set position to position+1
  RETURN position<list.length
  IsThere是一个有返回值的子程序，该例子为布尔类型的返回值。

  第九章 面向对象设计与高级程序设计语言

  1。面向对象方法

  面向对象

  在面向对象的思想中，数据和处理数据的算法绑定在一起，因此，每个对象负责自己处理。面向对象设计（OOD)的抵触概念是类和对象。
  
• 对象：在问题背景中相关的事物或实体。
• 对象类或类：一组具有相似的属性和行为的对象描述。
• 域：类中的特定项，可以是数据或子程序。

• 方法：定义了类的一种行为的特定算法。

  设计方法

  我们提出的分解过程有四个阶段
• ==集体讨论（头脑风暴==）是确定问题中的类的第一个阶段。
• ==过滤==这个阶段中，将回顾集体讨论阶段确定的类。过滤阶段保留下来的类将在下一个阶段仔细研究。
• ==场景阶段==将确定每个类的行为。称类的行为为责任。
• 最后是==责任算法阶段==，将为列出所有类的责任编写算法。
• 集体讨论：在面向对象的问题求解背景中，集体讨论是一种集体行为，为的是生成某个特定问题要用到的候选类的列表。
• 过滤：集体讨论会生成一份暂时的类列表。该阶段确定问题解决方案中的核心类。
• 场景:这个阶段的目标是给每个类分配责任。最终责任将被实现为子程序。
  责任的类型有两种，即类自身必须知道什么和类必须能够做什么。类把它的数据封装起来，使得一个类的对象不能直接访问另一个类中的 数据。
• 封装：把数据和动作集中在一起，是数据和动作的逻辑属性与它们的实现细节分离。
• 责任算法：最终必须为责任编写算法。由于在面向对象的设计观念中，重点是数据而不是动作，，所以执行责任的算法一般相当短。动作责任复杂一些，通常涉及计算，。因此，自顶向下设计算法的方法通常也适用于设计动作的算法。

• 总结：自顶向下的设计方法重点在于把输入转化成输出的过程，结果将生成任务的体系结构。面向对象设计的重点是要转换的数据对象，结果生成的对象是对象的体系结构。

  一个计算机示例

  -P290——P292

  2.翻译过程

  编译器：把用高级语言编写的程序翻译成机器码的程序

  任何计算机只要具有一种高级语言的编译器，就能运行用这种语言编写的程序。想要在多种类型的机器上使用一种高级语言，就要具备这种语言的多个编译器。

  解释器：输入用高级语言编写的程序，指导计算机执行每个语句指定的动作的程序

• 程序，用于翻译和执行语句序列。与汇编器和编译器只是输出机器码且机器码再单独执行不同的是，解释器在翻译过语句之后会立即执行这个语句。可以把解释器看作理解编写程序所使用的语言的模拟器或虚拟机。
  
• 第二代高级语句可以分为两种，一种是要编译的，一种是要解释的。FORTRAN.COBOL和ALGOL是要编译的语言，Lisp，SONBOL4和APL是要解释的语言。
• Java于1996年面世，可移植性为其最重要的特性。为了达到最佳可移植性，Java被编译成一种标准机器语言——字节码。

  • 字节码：编译Java源代码使用的标准机器语言

    3.程序设计语言的范形

    什么是范形？《美国传统词典》对范形的定义有两条与计算相关，即“用作模式或模型的实体”和“一组假设，概念，值和实践，构成了共享它们的聚合体观察现实的方式，尤其适用于精神学科。”

    命令式类型

    具有顺序执行指令的特征，变量的使用代表了内存地址，而使用赋值语言则改变这些变量的值。
• 面向过程的范型
  面向过程编程是一种命令式模型，在这里语句被分组为子程序。一个程序是子程序分层子构成的，每一层执行整个问题求解的一个必要的特定任务。伪代码示例描述了这种模型。

• 面向对象的范型
  面向对象视角是与对象交互的一种方式。每个对象负责执行它自己的动作。在面对过程的范型中，数据被认为是被动并且被程序所操控的。在面向对象的范型中，数据对象是活跃的。对象和操作对象的代码绑定在一起，使得每个对象负责控制自己的操作。Java和Python是两种新式的面向对象编程语言。
  C++和Java是命令式语言，但就它们的范型而已又是混合的。

  声明式范型

  声明式范型是一个描述结果的模型，但是完成结果的过程则不被描述。在这种范型中有两种基本模型：函数式和逻辑式。

  函数式模型

  基于函数的属性概念。计算通过对函数求值来实现，而问题求解通过函数调用来实现。因此基本的原理是函数的求值，而不是变量和赋值语句。

  逻辑式编程

  逻辑编程基于象征逻辑的原则。这个模型包括了一系列关于对象的事实和一系列关于对象间关系的规则。
  PROLOG是1970年早法国研发的第三代逻辑编程语言。一个PROLOG程序包含三中语句：一种声明了对象及对象之间关系的事实，一种定义了对象及对象之间的关系规则，第三种询问对象及对象之间关系的问题。
  如，定义关于宠物和主人的事实
  owns(mary.bo).
  owns（ann.kitty).
  owns(bob.riley).
  owns(susy.charlia).
  当你有一个由事实构成的数据库时，PROLOG允许你向数据库询问问题。如：
  ?-owns(mary.bo)
  ?-owns(bo.mary)
  ?-owns(susy.bo)
  PROLOG对第一个回答yes，第二个回答no，第三个回答no。
  在PROLOG系统中，常量以小写字母开头，变量以大写字母开头。事实上，我们以一个常量代替一个变量来询问事实真相。
  ?-owns(ann.Cat).
  ?-owns(Name.charlie).

  4.高级程序设计语言的功能性

  两种伪代码结构——选择和重复是命令式语言的标志。
  首先，我们回顾布尔表达式的概念，它是高级语言用于进行选择的结构。

  布尔表达式

  布尔表达式是一个标识符序列，标识之间由相容的运算符分隔，求得的值是true或false。一个布尔表达式可以说：
  
• 一个布尔变量
• 一个算术表达式加一个关系运算符，再加一个算术表达式

• 一个布尔表达式加一个布尔运算符，再加一个布尔表达式
  关系运算符是比较两个值的运算符。下表总结了六种关系运算符以及各种高级语言用于表示它们的符号。

数据归类

强类型化：每个变量都有一个类型，只有这种类型的值才能存储到该变量中。
数据类型：一组值以及能够应用于这种类型的值的基本操作集合的说明。

• 数据类型
  数据是表示信息的物理符号。
• 整数
  表示一个整数值的范围，范围由表示数值的字节数决定。
• 实数
  表示特定精度的数的范围，与整数数据类型一样，范围由表示实数的字节数决定。
• 字符
  表示ASCII字符集包括英文字符，是Unicode的子集。
• 布尔型
  
• 只有两个值——true和false。
  程序如下P197
• 字符串
  一个字符序列，在某些语言中这个序列被看作一个数据值。
• 声明
  把变量，动作或语言中的其他实体与标识符关联起来的语句，使用程序可以通过名字引用这些项目。
• 保留字
  一种语言中具有特殊意义的字，不能用它作为标识符。

• 区分大小写
  大写字母和小写字母被看作是不同的，两个拼写方法相同但大小写形式不同的标识符被看作是两个不同的标识符。

  输入/输出结构

  P199

  控制结构

  确定程序中的其他指令的执行顺序的指令。
  详见P200-P203
• 嵌套逻辑
  在任何个、控制语句中被执行或跳过的语句可以是简单的语句或块（一组语句），对于这些语句没有任何限制。选择语句可以在循环结构中被嵌套，循环结构可以在选择语句中被嵌套。

• 异步处理
  异步：不与计算机中的其他操作同事发生，换句话说，与计算机的动作不同步。

  5.面向对象语言的功能性

  封装

• 封装：实施信息屏蔽的语言特性。
• 对象类或类（问题求解阶段）：属性和行为相似的一组对象的说明
• 对象（问题求解阶段）：与问题背景相关的事物或实体
• 对象（实现阶段）：类的一个实例

• 类（实现阶段）：对象的模式

  类

  P205-P206
  实例化：创建类的对象

  继承

  类获取其他类的属性（数据域和方法）的机制。

  多态

  一种语言的继承体系结构中具有两个同名方法且能够根据对象应用合适的方法的能力。

  6.过程设计与面向对象设计的区别

• 在面向对象的设计中，列表数据结构和子程序需要在类中绑定在一起

public class List
//Class variables
values[]
lengteh
//Class methods
public Boolean Is There(item)
Set position to 0
WHILE(position < length AND values [position]!=item)
Set position to position+1
RETURN position<length
public Delete(item)
Set position to 1
WHILE(values[position]!=item)
Set position to position + 1
Set length to length - 1
//Rest of class operations

• 方法的代码需要直接可以访问到类变量，而用户的代码则不可以。类需要被分别翻译，并且想使用该类的程序需要在程序中包含它。

List list = new List()
WHILE(more values)
Read aValue
IF(NOT list.IsThere(aValue)
list.insert(aValue)
Write"input value to delete or "Quit" to quit "
IF(list.IsThere(aValue))
list.Delete(aValue)

• 在面向过程的版本中，列表被呈现为传递给子程序的记录，以便子程序可以对其操作，操作它的数据结构和子程序是用户程序的一部分在面向对象的版本中，类对象的实现通过封装实现对用户的隐藏