计算机算法——设计与分析导论中文翻译.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：1.59M 资料格式：pdf 举报版权申诉

qinyuehong-9989522-4744302542924526721.pdf-第1页.png

第1页 / 共209页

qinyuehong-9989522-4744302542924526721.pdf-第2页.png

第2页 / 共209页

qinyuehong-9989522-4744302542924526721.pdf-第3页.png

第3页 / 共209页

qinyuehong-9989522-4744302542924526721.pdf-第4页.png

第4页 / 共209页

qinyuehong-9989522-4744302542924526721.pdf-第5页.png

第5页 / 共209页

qinyuehong-9989522-4744302542924526721.pdf-第6页.png

第6页 / 共209页

qinyuehong-9989522-4744302542924526721.pdf-第7页.png

第7页 / 共209页

qinyuehong-9989522-4744302542924526721.pdf-第8页.png

第8页 / 共209页

前言

第一章分析算法和问题：原理与例子

1.1概述

1.2Java作为算法描述语言

1.2.1一个可用的Java子集

1.2.2组织者类

1.2.3基于Java的伪代码约定

1.3数学知识

1.3.1集合、元组和关系

元组和叉积

关系和函数

1.3.2代数和微积分工具

Floor和Ceiling函数

对数

排列

概率

级数与求和

单调递增函数和凸函数

利用积分求和

不等式运算

1.3.3逻辑元素

量词

否定量词命题、反例

逆否命题（contrapositives）

反证法

推理规则

1.4分析算法和问题

1.4.1正确性

1.4.2所做工作的量

1.4.3平均和最坏分析

1.4.4空间使用

1.4.5简明性

1.4.6最优性

1.4.7低限和问题复杂度

1.4.8实现和编程

1.5简单函数的渐进增长率

1.5.1渐近阶的定义和符号

1.5.2渐进阶的重要性

1.5.3ΟΩ和Θ的属性

1.5.4渐进阶的和

1.6在有序数组中查找

1.6.1一些解决方法

1.6.2二分查找的最坏情况分析

1.6.3平均情况分析

1.6.4优化

第二章数据抽象和基本数据结构

2.1概述

2.2ADT规格和设计技术

2.2.1ADT设计规范

WhatGoesintoanADT

2.2.2ADT设计技术

2.3基本ADT－列表和树

2.3.1递归ADT

2.3.2表ADT

部分重建和非破坏性操作（NondestructiveOperations）

2.3.3二叉树ADT

二叉树的定义和基本属性

二叉树的遍历

2.3.4树ADT

2.3.5In-treeADT

2.4堆栈和队列

2.4.1堆栈ADT

2.4.2队列ADT

2.5动态集ADT

2.5.1优先级队列ADT

2.5.2联合－查找ADT（Disjoint集合）

2.5.3字典ADT

第三章递归与归纳

3.1概述

3.2递归过程

3.2.1活动帧框架和递归过程调用

3.2.2递归的提示－Method99

3.2.3递归过程的包装器

3.3什么是证明?

定理或命题的格式

双列证明格式

3.4归纳证明

3.4.1归纳证明的模式

归纳模式的变体

3.4.2归纳证明一个递归过程

3.5证明过程的正确性

3.5.1定义和术语

3.5.2基本控制结构

3.5.3单赋值范例

转换没有循环的过程

3.5.4带循环过程

3.5.5正确性证明作为调试工具

3.5.6递归过程的终止

3.5.7二分查找的正确性

3.6递归等式

普通递归等式

3.7递归树

3.7.1分而治之，一般情况

3.7.2ChipandConquer，或者BeConquered

*3.7.3为什么递归树能工作

第四章排序

4.1概述

4.2插入排序

4.2.1策略

4.2.2算法和分析

最坏情况复杂度

平均行为

空间

4.2.3特定排序算法的行为低限

4.3分而治之

4.4快速排序

4.4.1快速排序的策略

4.4.2Partition子例程

4.4.3快速排序的分析

最坏情况

平均行为

*更精确的平均行为

空间使用

4.4.4基本快速排序算法的改进

选择枢轴

可选的Partiton策略

小集合排序

堆栈空间优化

结合使用这些改进手段

Remarks

4.5归并有序序列

4.5.1最坏情况

4.5.2归并的优化

4.5.3空间使用

4.6归并排序

归并分析

*更精确的归并排序分析

4.7基于比较的排序的低限

4.7.1排序算法的判定树

4.7.2最坏情况的低限

4.7.3平均行为的低限

4.8堆排序

4.8.1堆

4.8.2堆排序的策略

4.8.3修正堆

4.8.4构造堆

正确性

最坏情况分析

4.8.5堆的实现和堆排序

堆排序分析

4.8.6加速堆排序

分析

4.9四种排序算法的比较

4.10Shell排序

4.10.1算法

4.10.2分析和注意事项

4.11基数排序

4.11.1使用关键字的属性

桶排序有多块

4.11.2基数排序

分析与注意事项

第五章Selection和AdversaryArguments

5.1概述

5.1.1Selection问题

5.1.2低限

5.1.3虚拟对手AdversaryArguments

5.1.4竞标赛

5.2查找max和min

5.3查找次大的关键字

5.3.1概述

5.3.2竞标赛方法

5.3.3AnAdversaryLowe-BoundArgument

5.3.4查找max和secondLargest竞标赛方法的实现

5.4Selection问题

5.4.1一个分而治之接近

5.5查找median的低限

5.6DesigningAgainstanAdversary

第六章动态集&查找

6.1概述

6.2数组翻倍

6.3平摊（Amortized）时间分析

6.4红黑树

ProperlyDrawn树

空树作为external节点

6.4.1二叉查找树

6.4.2二叉树的旋转

6.4.3红黑树的定义

6.4.4红黑树的大小和深度

6.4.5红黑树中插入

6.5哈希

6.5.1封闭地址哈希

6.5.2开放地址哈希

6.5.3哈希函数

6.6动态等价关系和联合查找程序

6.6.1动态等价关系

6.6.2一些浅显的实现

6.6.3联合－查找程序

6.6.4WeightedUnion

6.6.5路径压缩

wUnion和cFind的兼容性

*6.6.6wUnion和cFind的分析

6.6.7应用

6.7优先级队列withaDecreaseKeyOperation

6.7.1TheDecreaseKeyOperation

第七章图和图的遍历

7.1概述

7.2定义和表示

7.2.1一些例子

7.2.2基本的图定义

7.2.3图的表示和数据结构

邻接矩阵

邻接表数组

7.3图的遍历

7.3.1深度优先查找

7.3.2广度优先查找

7.3.3深度优先查找和广度优先查找的比较

7.4有向图的深度优先查找

7.4.1深度优先查找和递归

7.4.2使用深度优先查找连通分量

7.5有向图的强连通分支

7.6无向图的深度优先查找

7.7无向图的二连通分支

7.7.1关节顶点和二连通分支

第八章图的最优化问题和贪婪算法

8.1概述

8.2Prim最小生成树算法

8.2.1最小生出树的定义和例子

8.2.2算法的概况

8.2.3最小生出树的属性

8.2.4Prim’sMST算法的正确性

8.2.5用优先权队列有效的管理边缘

初步分析

8.2.6实现

8.2.7分析（时间和空间）

8.2.8ThePairingForestInterface

8.2.9低限

8.3单源最短路径

8.3.1最短路径的属性

8.3.2Dijkstra’s最短路径算法

8.3.3实现

分析

8.4Kruskal’s最小生成树算法

8.4.1算法

8.4.2分析

第九章传递闭包、任意两点的最短路径

9.1概述

9.2二元关系的传递闭包

9.2.1定义和背景

9.3传递闭包的Warshall’s算法

9.4图的任意两点的最短路径

9.5通过矩阵操作计算传递闭包

第十章动态规划

10.1概述

10.2子问题图和他们的的遍历

10.3矩阵的乘法顺序问题

10.3.1矩阵乘法顺序问题

10.3.2贪婪的尝试

10.3.3动态规划的解决方案

10.4构造最优二叉树

10.5

第十一章串匹配

11.1概述

11.2直接的解决方案

11.3Knuth-Morris-Pratt算法

11.4Boyer-Moore算法

11.5近似串匹配

第十二章多项式和矩阵

12.1概述

12.2计算多项式函数的值

12.2.1算法

12.3矢量和矩阵乘法

12.4快速傅立叶变换和卷积

12.4.1快速傅立叶变换

12.4.2卷积

12.4.3附录：复数和单位根RootsofUnity

第十三章NP完全问题

13.1概述

13.2P和NP

13.2.1决策问题

13.2.2一些简单的问题

13.2.3P类

13.2.4NP类

13.2.5输入的规模

13.3NP完全问题

13.3.1多项式约简PolynomialReductions

13.3.2一些已知的NP完全问题

13.3.3什么使得问题困难？

13.3.4优化问题和决策问题

13.4近似算法

13.5装箱

13.5.1

13.5.2其他启发

13.6背包

13.7图的着色

13.7.1一些基础技术

13.7.2近似图着色是困难的

13.7.3Wigderson’s图着色算法

13.8TSP旅行商问题

13.8.1贪婪策略

13.8.2最近邻居策略

13.9.3最短连接策略

13.8.4TSP的近似算法有多好？

13.9DNA计算

13.9.2DNA背景

13.9.3Adleman的有向图和DNA算法

13.9.4分析和评估

第十四章并行算法

14.1概述

14.2并行，PRAM和其他模型

14.2.1PRAM

14.2.2其他模型

14.3一些简单的PRAM算法

14.3.1二分扇入技术

14.4处理写冲突

14.4.1nbits上的布尔or

14.4.2一个在常数时间查找最大值的算法

14.5归并和排序

14.5.1并行归并

14.5.2排序

14.6查找连同分量

14.6.1策略和技术

14.6.2算法

14.6.3算法的PRAM实现

14.6.4分析

14.7加n个整数的底限

计算机算法－设计与分析导论 Sara Baase Allen Van Gelder 译者：sttony.dark 前言第一章分析算法和问题：原理与例子 1.11.11.1 概述概述概述说一个问题是算法可解的（非正式的），意味着可以编写一个计算机程序，如果我们允许这个程序有足够的运行时间和存储空间，这个程序可以为任何输入处理出一个正确的结果。在 20 世纪 30 年代，计算机出现之前，数学家们就已经积极的定型和研究算法的概念。算法被解释成（非正式的）一套清楚的简单指令，按照这套指令可以解决某个问题和计算某个函数。多种形式的计算模型是设计和研究出来的。早期这个领域工作的重点叫可计算理论，其主要是描述或总结那些可算法解决问题的特征，以及指出那些问题是不能算法解决的。由阿兰. 图灵建立的一个重要的否定结论是：证明“停机问题”（halting problem）是不可解决的。停机问题是说：能否判断一个任意给出的算法（或计算机程序）在给定输入的情况下是否最终停止（也就是说是否进入死循环）。这个问题不能用计算机程序解决。尽管可计算理论对于计算机科学是明显和基础的本质，但是判断一个问题是否在理论上可以在计算机上解决的知识还不足以告诉在实际中是否也可以。例如，可以写出一个完美的国际象棋程序。这并不是一件很困难的事情；棋子在棋盘上的摆放方式是有限的，在一定的规则下棋局总会在有限步之后结束。程序可以考虑计算机可能走的每一步，对手对这一步所有可能的响应，再考虑如何应对对手这一步…… 一直到每一种可能的走法到达结束。既然知道了每一步的最后结果，计算机就可以选择一个最好的。考虑棋子在棋盘上合理的排列（这比步数要少的多），估计就超过 1050。检查所有可能结果的程序需要运行几千年，如此程度的程序不能运行。实际应用中大量的问题都是可解决的——就是说可以为他们写出程序——但是对一个实用的程序来说时间和存储空间的要求是十分重要的。一个实际程序明确的时间空间要求是很重要的。因此，他们变成了计算机科学中一个分支的主题，叫计算复杂性。本书并不包含这一分支，这一分支关心一套正式、有些抽象的关于可计算函数复杂性的理论。（解决一个问题等价于根据一套输入计算出函数的输出。）度量复杂性的公理已经公式化了；他们是如此的基础和一般以致一个程序执行指令的条数和需要存储空间的 bit 数都可以作为复杂性度量。使用这些公理，我们可以证明任意一个复杂问题的存在，以及问题没有最好的程序。 - 1 -

（Using these axioms, we can prove the existence of arbitrarily complex problems and of problems for which there is no best program.）本书中学习的计算复杂性分支只关心分析特殊问题和特殊算法。本书打算帮助读者建立一份解决通用问题的经典算法的清单，分析算法、问题的一些一般性的设计技术、工具和指导方针，以及证明正确性的方法。我们将呈现、学习和分析计算机程序中常用的解决各种问题的算法。我们将分析算法执行所需的时间，我们也分析算法执行所需要的空间。在描述各种问题的算法的时候，我们将看到几种经常被证明很有用的算法技术。因此我们暂停一下谈一谈一些一般性的技术，比如分而治之（divide-and-conquer）、贪婪算法（ greedy algorithms）、深度优先搜索（depth-first search）和动态编程（dynamic programming）。我们也将学习问题本生的复杂性，就是不管用什么算法解决问题所需固有的时间和空间。我们将学习分类 NP 完全问题——目前还没有找到这类问题的有效算法——并试图用一些试探的方法找到有用的结果。我们也将说明用 DNA 代替电子计算机来向解决这类问题接近。最后，我们将介绍并行计算机算法的主题。在下面的一节中我们将给出算法描述语言的大概，回顾一些本书用到的背景知识和工具，并展示在分析算法中涉及的主要概念。 1.21.21.2 JavaJavaJava 作为算法描述语言作为算法描述语言作为算法描述语言通过平衡多种条件之后，我们选择 Java 作为算法描述语言。算法必须易读。我们想将注意力放在一个算法的策略和技术上，而不是编译器关心的申明和语法细节。语言必须支持数据抽象和问题分解，这样才能够简单清楚的表示一个算法的思想。语言必须提供一种实际的实现（即已经了编译器，原文 The language should provide a practical pathway to implementation.）。他必须在大部分平台上可用而且提供程序开发的支持。实际的实现和运行一个算法能增强学生的理解，不能陷入与编译器、调试器失败的战斗中。最后因为本书是教算法的，不是程序设计，能轻易的将算法转换成读者使用的各种语言必须是合理的要求，特殊语言特性必须减到最少。在我们要求的许多方面 Java 表现的很好，尽管我们没有宣称他是理想的。他支持自然的数据抽象。Java 是类型安全的，这意味着一种类型的对象不能在需要另一种对象的操作中 boolean 使用；不允许任意类型之间的转换（叫"cast"）。他有显式的 boolean boolean 类型，所以如果程序员混淆了"="（赋值运算符）和"= =" （比较运算符），编译器可以发现这个错误。 Java 不允许指针操作，这些要求通常是含糊不清错误的源头；事实上编译器向程序员隐藏了指针，而在幕后自动处理。在运行期，Java 检查越界的数组下标，检查其他由含糊不清错误引起的矛盾。他执行垃圾收集器，这意味着自动回收不在引用的对象；这大大减轻了程序员管理空间的负担。 Java 的缺点是：他有许多和 C 一样的简洁、含糊的语法特征。对象结构可能导致时间和空间上的低效。许多 Java 构造需要比其他语言大的多的冗余，比如 C。尽管 Java 有许多特殊的特性，本书展示的算法避免使用他们，只对语言独立的部分感兴趣。事实上，算法中许多步骤都是易读的伪代码。这一节描述了我们在这本书中使用的 Java 的一个小子集，以及用于增加算法可读性的伪代码约定。附录 A 中给出了运行 Java 程序需要的其他的实现细节，但是这些细节对理解主要内容没有关系。 - 2 -

1.2.1 1.2.1 1.2.1 Java 一个可用的 Java Java 子集完全熟悉 Java 对于理解本书中的算法并不重要。本节给出了本书出现的 Java 特性的一个大概，主要是为那些想亲自实现算法的读者准备的。这里，我们指出使用的 Java 的 OO 特性，但是尽量避免以使文字得到完全的语言独立性；这主要对熟悉其他 OO 语言（比如 C++）而不是完全熟悉 Java 的读者有好处。附录 A 中有一个简单的 Java 程序。许多书深入讲解 Java 语言。有丰富 Java 经验的读者肯定会注意到许多例子中都没有使用 Java 的优秀特性。但是，算法后面的概念不需要任何特殊的特性，而且我们希望这些概念可以容易的被领悟，并使用各种语言，所以我们将他留给读者，一旦读者领悟了这些概念，就可以用他们喜欢的语言实现。熟悉 C 语法的读者将会意识到 Java 的语法有许多相似的地方：块由大括号分隔，"{"和 " }"；数组的索引在方括号"[" 和"]"中。和 C 和 C++一样，二维数组实际上是一个元素是一维数组的一维数组，所以存取二维数组需要两重 [ ] 就像" matrix[i][j]" 。运算符 "= =" " ! =" "< =" 和"> =" 是数学关系运算符的关键字。在文中使用的伪代码中使用的是数学符号。文中使用 "++" 和"--" 运算符来增加和减少，但是决不会将他们嵌入到其他表达式中。这里也有从 C 借用的运算符 "+=" "- =" "* =" "/ =" 。例如 p+=q ; /*p=p+q */ y-=x ; // y=y-x 就像在例子中一样，注释从 "// " 到行结尾，或是从 " /* " 到" */ "，和 C++一样。 Java 的函数头也和 C 一样。函数头在函数名字后的括号中指定了参数的类型特征；在函数名字之前指定了返回类型。返回类型和参数类型的组合叫函数的完全类型特征也叫原型。因此 intintint getMin(PriorityQ pq) 告诉我们 getMin 接收一个类型（或类）为 PriorityQ 的参数，返回类型 int。 char 、char char short 、short short 、intintint long 、long long boolean Java 只有很少的原始类型，其他所有类型都叫 classes。原始类型是逻辑（boolean boolean ）和数字类型（bytebytebyte ）类型。所有的 Java 类（非原始类型）都是引用类。在底层，在类中申明的变量都是“指针”；他们的值都是地址。类的实例叫对象。申明一个变量不会创建对象。通常用"newnewnew "运算符来创建对象，"new"返回新对象的一个引用。 double 和 double double float 、float float 对象的数据域按 OO 术语叫实例域。二元的点运算符用来存取对象的实例域。例 1.1 创建和存取一个 Java 对象在这个例子，让我们假设数据信息遵循下面的嵌套逻辑结构：  year  number  isLeap  month  day - 3 -

这里使用非正式的术语，year 是由布尔属性 isLeap 和整数属性 number 构成的组合属性，而 month 和 day 只是简单的整数属性。为了反映这个嵌套结构，我们必须在 Java 中定义两个类，一个表示整个数据，另一个表示 year 域。假设我们为这两个类分别取名 Date 和 Year。接下来我们要申明 number 和 isLeap 作为 Year 类的实例域，申明 year、month、day 为 Date 类的实例域。除此之外，我们最好将 Year 定义为 Date 的内部类。语法如图 1.1。 Date class class class { public public public public public public public public public public public public Year year; intintint intintint static static static month; day; class class class { Year public public public public public public number; intintint boolean boolean boolean isLeap; } } 图 1.1 带一个内部类 Year 的类 Date 的 Java 语法 public 不带 public public 关键字，实例域就不能在 Date 和 Year 外面访问；为了 public 简单，我们在这里使用 public public 。申明内部类，Year 带 static 修饰符的原因是，因为我们可以单独创建 Year 的实例而不与任何特定 Date 对象相关联。本书中所有的内部类都将是 static。假定我们创建了一个由 dueDate 变量引用的 Date 对象。为了存取对象中的 year 实例域，使用.运算符，如"dueDate . year"。如果一个实例域在类中（与之对应的是在原始类型中），要再接一个. 来存取他的实例域，如"dueDate .year. isLeap" 。赋值语句仅仅拷贝类对象的引用或地址；不拷贝实例域。例如，" noticDate = dueDate" 导致变量 noticDate 指向了变量 dueDate 指向的同一对象。因此下面的代码很可能是逻辑错误： noticDate = dueDate; noticDate .day = dueData .day -7 ; 参见 1.2.2 节，对这个问题有另外的讨论。 Java 中的控制语句 ififif , elseelseelse , whilewhilewhile , forforfor 和 break 和他们在 C（和 C++）中的意义相同，本书中将用到。存在许多其他的控制语句，但不用他们。while 和 for 的语法是 whilewhilewhile forforfor （继续条件）body （初始化；继续条件；增量）body ananan boole 这里“初始化”和“增量”都是简单语句（不带{ }），“body”是任意语句， “继续条件”是 boole boole break 表达式。break break ，但本 switch 循环中跳出（当然也包括 switch switch 语句导致立即从最近的 forforfor 或 whilewhilewhile - 4 -

switch 书不使用 switch switch ）。 Object Java 是单根继承，其根是 Object Object extends 。当申明一个新类时，他可以从原来的类中 extends extends ，新类就成了继承树种以前定义类的派生类。文中我们将不建立这样的体系，为了尽可能的保持语言独立性；但是在附录 A 中给出了一些例子。如果新类没有申明为从任何类 extend， Object 默认的他从 Object Object extend。学习算法不需要复杂的类体系。在 OO 术语里对象的操作叫方法；但是我们将限制自己只使用静态方法，他们都是简单的过程和函数。在我们的术语中，过程是一个可以取名字、可以被调用的计算步骤序列（带参数的）；函数则是一个可以向调用者返回值的过程。在 Java 中不返回值的过程申明返回类型为 voidvoidvoid ；这一点和 C 和 C++一样。Java 术语 static意味着这个方法可以被任何对象和合适类型的对象（对象类型是它的类）所调用，只要依照方法的类型特征就行（经常被称作原型）。一个静态方法与任何特定对象都无关。静态方法的行为就像其他程序设计语言中的函数和过程一样。但是，他们的名字必须跟在类名字的后面，例如"List . first(x) " 指以参数 x 调用在类 List 中定义的 first 方法。默认情况下 Java 中的实例域是私有的，这意味着他们仅能被定义在类中的方法（函数和过程）所存取。这和抽象数据类型（ADT）的设计主题是一致的，即对象只能由定义在 ADT 中的方法所存取。实现这些 ADT 操作（或是静态方法，或是函数、过程）的代码存在与类中，知道这些私有的实例域和其类型。默认情况下方法也是私有的，但一般指定为 "public" ，所以定义在其他类中的方法可以调用他们。但是，一些只能由类中其他方法调用的底层方法可能也是私有的。 ADT 的客户（client）（调用 ADT 的函数、过程）在 ADT“生存”以外的类中实现，所以他们只能存取 ADT 类的 public 部分。私有数据的维护叫做封装或信息隐藏。实例域在对象的生存期之内保存赋给他的值，直到后来又赋给他别的值。这里我们可以看到将实例域指定为私有的优点。一个共有的实例域可以被整个程序的任意一段代码赋成任意一个值。一个私有的实例域就只能通过 ADT 类中为此目的而设计的方法所赋值。这个方法可以进行其他计算，并测试赋给他的值是否和 ADT 要求的一致，是否和其他实例域一致。一个新对象通过语句"newnewnew classname( )"创建，例如： Date dueDate = newnewnew Date 这条语句导致 Java 调用 Date 类的默认构造函数。构造函数保留一个新对象所占的存储空间，返回一个新对象的引用（很可能是地址）用于存取对象。新对象的实例域没有初始化。 Java语言提示：程序员可以为类定义一个额外的构造函数，构造函数可以初始化各种实例域，执行其他计算。我们感兴趣的是语言独立性，文中将不使用这样的构造函数，所以忽略其细节。 Java 中的数组申明和 C/C++中不太一样，他们的特征也明显不同。Java 语法申明一个整 x 型数组（非常明确，申明了一个类型为“整型数组”的变量）是 " intintint [ ]"。这条语句不初始化 x ，下面这条语句才初始化 [ ] x "，而 C 使用 " iii ntntnt x = newnewnew intintint [howMany] ; 这里 howMany 可以是一个常量也可以是一个变量，他的值指示了数组的长度。申明一个类的数组是一样的。申明和初始化可以，通常都是合到一条语句中： [ ] x = newnewnew intintint intintint Date [ ] dates = newnewnew [howMany]; Date [howMany ]; - 5 -

当这些语句初始化 x 和 dates ，保留数组的存储空间时，只能以默认值初始化元素，这未必有用。因为在单个元素使用之前可能需要单独的值（很可能使用 newnewnew 运算符）。在 Date 类外初始化的语法 Date( ); dates[0] = newnewnew dates[0]. month = 1 ; dates[0]. day =1 ; dates[0]. year = newnewnew dates[0]. year. number =2000; true dates[0]. year. isLeap =true true ， Data.Year( ); 注意，域名字跟在指定数组元素的索引之后。在第二条 newnewnew 语句中，内部类名字，Year，被外部类 Date 所限定，因为这条语句在类 Date 的外面。就像前面提到的，Java 程序员可以写一个带参数的构造函数以初始化一个构造好的新对象，但是本文为了语言独立性不使用这样的构造函数。一旦用 newnewnew 的方法，x . length。实例域length 是 newnewnew 语句初始化了 x 数组，x 引用的数组长度就不能改变了。Java 提供查询长度语句自动附加到数组对象上的，可以被 x 所存取。有效的元素索引是从 0 到（x.length －1）。如果程序试图存取一个越界的元素，Java 将 [ n+1] 停止程序（抛出异常）。我们经常希望索引从 1 到 n，因此常常初始化数组为 " newnewnew " 。 intintint Java 允许重载和覆盖方法。一个重载方法是说，有多个带不同参数的定义，但是有相同的返回值。许多算术操作是重载的。覆盖则是在类体系中多次定义了有同样参数类型的同一方法，Java 采用在类体系中最接近的定义。（还是为了和其他语言兼容，而且这个特性对于理解算法也不是决定性的，我们避免使用这个特性，读者可以去阅读 Java 语言的书。）在不同类中可能使用相同名字的方法，但是这不是覆盖，因为在类外面方法时，必须使用类名（对象名）来限制。在后面的例子将看的更清楚。对于熟悉 C++的读者，必须指出 Java 不允许程序员重载运算符。本文在伪代码中使用 String 这样的运算符来增加可读性（例如，x < y 这里 x 和 y 都是非数值类，比如 String String ）。但是，如果你定义一个类，开发一个实际的 Java 程序，你就必须写一个有名字的函数（比如 less （）），调用他来比较你的类。 1.2.2 1.2.2 1.2.2 组织者类我们创造术语组织者类，这不是标准的 Java 术语，他指一种只是为了将多个实例域组织到一起的简单的类。组织者类实现类似 C 的结构、Pascal 或 Modula 记录的规则；类似的东西存在于 Lisp、ML 和其他大部分程序设计语言中。组织者类和 ADT 的目的正好相反；他们只是简单的组织数据，不限制数据的存取，也不为数据提供任何定制的方法。习惯于在其他类中定义组织者类；由于这个原因，在 Java 术语中组织者类叫内部类。一个组织者类仅有一个方法，叫 copy。既然 Java 中的变量都是对象的引用，赋值语句仅拷贝引用，而不是对象的实例域，就像我们在例 1.1 中看到的。如果这些变量在一个叫 Date 的组织者类中定义，我们可以使用语句 noticDate = Date. copy( dueDate ); noticDate .day = dueDate .day -7 ; - 6 -

来拷贝 dueDate 对象的实例域到 noticDate 所引用的新对象中，之后修改的只是 noticDate 的 day 域。定义 1.1 组织者类的拷贝函数组织者类将实例域赋值到一个新对象的 copy 函数（方法）的一般规则如下（例子中假设对象 d 被拷贝到新对象 d2）： 1. 如果实例域（year）是其他的组织者类，copy 方法将调用该类的 copy 方法，如 d2.year = Year. copy(d . year )。 2. 如果实例域（day）不是其他组织者类，使用一般的赋值，如同 d2 .day = d.day。完整的例子在图 1.2 中给出。 Date class class class { public public public public public public public public public public public public { Year year; intintint month; intintint day; static static static class class class Year number; intintint boolean boolean boolean static static static isLeap; Year copy(Year y) public public public public public public public public public { Year y2 =newnewnew Year( ); y2. number = y. number; y2. isLeap = y. isLeap; return return return y2; } } public public public { static static static Date copy(Date d) Date d2 =new Date( ); d2. year = Year. copy ( d . year); d2. month = d.month; d2. day = d. day; return return return d2; } public public public static static static intintint defaultCentury; } 图 1.21.21.2 带内部组织者类 Year 的组织者类 Date 程序员必须保证在定义组织者类时不能发生循环引用，否则 copy 函数将陷入递归不能结束。当然，组织者类中新对象可以由一般方法创建： Date someDate = newnewnew Date ( ) - 7 -

Java语言提示：Java 提供一种一层对象的机制，不需要写出每一条赋值语句，clone 方法，但是他不能自动处理像 Date 这种嵌套结构；你仍然要写出处理这种情况的代码。附录 A 给出了一个 copy1level 函数的一般性代码。 public 一个组织者类包含唯一一个 public public static 实例域。如果 static static 关键字也出现在域的申明中，该域不与任何实际对象相关，关键在于他不是一个全局变量了。典型组织者类例 1.21.21.2 在图 1.2 中，为例 1.1 的类增加了 copy 函数，所以他们有成为组织者类的资格。就像我们看到的，copy 的定义是机械的，而且单调的。在后面的例子中将省略实现的细节。为了更加完整，我们包含了全局变量 defaultCentury，而一般情况组织者类是不包含全局变量的。总结，我们创造了术语组织者类，他指那些只是简单将实例域组织起来，为他们定义一个拷贝函数的类 1.2.3 1.2.3 1.2.3 Java 基于 Java Java 的伪代码约定本书中的大多数算法使用了基于 Java 的更易读的伪代码，而不是严格的 Java。使用了下面的约定（除了在附录 A 中的以外）。 1. 省略了块分隔符（"{" 和"}"）。块边界用缩进指出。 static 2. 方法（函数或过程）申明中省略了 static static tictictic （偶尔会有 Java 内建的非静态方法；特别是 s. length( ) 用来获得字符串的长度。）关键字 static 会出现在需要实例域和内部类的地方。关键字。本文中申明的所有方法都是 stastasta 3. 在调用方法（函数或过程）前面省略了类名字。例如 x = cons( z, x) ，用完整的 Java 语法需要写成 x= IntList. cons ( z, x) （IntList 类在 2.3.2 节中描述）。无论什么时候静态方法在其定义的类之外调用都必须加上类名字前缀。 public 4. 省略存取控制的关键字 public public protecte 和 protecte protecte 关的文件都放在一个目录下，省去了处理可见的麻烦。 private 、 private private 。将所有与一个 Java 程序相 5. 经常使用使用数学关系运算符  , , 来代替他们的关键字版本。关系运算符用在意 6. String 义明确的地方，比如 String String Java 保留的和 Java 标准部分的关键字都以黑体： intintint 码语句和程序变量字体不变。伪代码语句的字体也不变。，即使在 Java 中是非法的。 String 、String String 。注释用斜体。代当我们特别指出这是 Java 语言时会偶尔离开这些约定。 1.31.31.3 数学知识数学知识数学知识本书中我们使用各种数学概念、工具和技术。大多数你应该熟悉了，可能会有少部分是新的。本节一一列举他们，为你提供一个参考，也是一个回顾。设计较深的证明在第三章。 - 8 -

分享到：

赞收藏

资料库

计算机算法——设计与分析导论中文翻译.pdf

相关推荐

课程资源

热门标签

最新资料