(本文未完待续)
目录
第1章 基本概念
1.1 算法
1.2 数学准备
1.2.1 数学归纳法
1.2.2 数、幂和对数
1.2.3 和与积
1.2.4 整数函数和初等数论
1.2.5 排列和阶乘
1.2.6 二项式系数
1.2.7 调和数
1.2.8 斐波那契数
1.2.9 生成函数
1.2.10 一个算法的分析
*1.2.11 渐近表示
*1.2.11.1 ○记号
*1.2.11.2 欧拉求和公式
*1.2.11.3 一些渐近计算
1.3 MIX
1.3.1 MIX的描述
1.3.2 MIX汇编语言
1.3.3 对排列的应用
1.4 某些基本的程序设计技术
1.4.1 子程序
1.4.2 共行程序
1.4.3 解释性程序
1.4.3.1 MIX模拟程序
*1.4.3.2 跟踪程序
1.4.4 输入和输出
1.4.5 历史和参考文献
第2章 信息结构
2.1 引论
2.2 线性表
2.2.1 堆栈、排队和双排队
2.2.2 顺序分配
2.2.3 链接分配
2.2.4 循环表
2.2.5 双重链接表
2.2.6 数组和正交表
2.3 树
2.3.1 遍历二叉树
2.3.2 树的二叉树表示
2.3.3 树的其它表示
2.3.4 树的基本数学性质
2.3.4.1 自由树
*2.3.4.2 有向树
*2.3.4.3 “无限性引理”
*2.3.4.4 树的枚举
2.3.4.5 通路长度
*2.3.4.6 历史和参考文献
2.3.5 列表和废料收集
2.4 多重链接结构
2.5 动态存储分配
2.6 历史和参考文献
习题答案
附录A 记号索引
附录B 数值数量表格
1. 基本常数(10进的)
2. 基本常数(8进的)
3. 调和数，贝努里数，斐波那契数
名词和姓名中英对照表
第1章 基本概念
1.1 算法
对于所有的计算机程序设计说来，算法的概念总是基本的，所以我们应当首先细心地分析这一概念。
“算法”(Algorithm)一词本身就是十分有趣的。初看起来，这词好像是某人打算要写的“对数”(Logarithm)一词但却把头四个字母写得前后颠倒了。这个词直到1957年之前在《韦氏新世界词典》(Webster's New World Dictionary)中还未出现，我们只能找到带有它的古代含意的较老形式的“算术”(Algorism)，指的是用阿拉伯数字进行算术运算的过程。在中世纪时，珠算家用算盘进行计算，而算术家用算术进行计算。中世纪之后，对这个词的起源已经拿不准了，早期的语言学家试图推断它的来历，认为它是从把algiros〔费力的〕+arithmos〔数字〕组合起来派生而成的，但另一些人则不同意这种说法，认为这个词是从“喀斯迪耳国王Algor”派生而来的。最后，数学史学者发现了算术“algorism”一词的真实起源：它来源于有名的《波斯教科书》(Persian textbook)的作者的名字阿布·贾法·穆哈默德·伊本·穆萨·阿科瓦里茨米(Abu Ja'far Mohammed ibn Musa alKhowarizml)(约公元825年)—从字面上看，是“Ja,far的父亲，Mohammed,Moses的儿子，Khowarizm的士人”。Khowarizm是今天苏联基发(ХИВА)市的小城镇。AlKhowarizml写了著名的书《复原和化简的规则》(Kitab al jabr w'al-muqabala)；另一个词，“algebra”(代数)，是从他的书的标题引出来的，尽管这本书实际上根本不是讲代数的。
逐渐地，“algorism”的形式和意义就变得面目全非了。如牛津英语词典所说明的，这个词是由于同arithmetic(算术)相混淆而形成的错误的造作。由algorism又变成algorithm。只要了解人们已经忘记了这个词原来派生的实况，就不难理解这种变化。一本早期的德文数学词典《大全数学辞典》(Vollstandiges Mathematisches Lexicon莱比锡，1747)，给出了Algorithmus(算法)一词的如下的定义：“在这个名称之下，组合了四种类型的算术计算的概念，即是，加法，减法，乘法和除法”。拉丁短语algorithmus infinitesimalis(无限小算法)，在当时就用来表示“莱布尼兹(Leibnitz)所发明的以无限小量进行计算的方法”。
1950年左右，algorithm一词经常地同欧几里得算法“Euclid's algorithm”联系在一起。这算法就是在欧几里得的《几何原本》(Euclid's Elements，第VII卷，命题i和ii)中所阐述的求两个数的最大公因子的过程。在这里给出欧几里得算法来，也将是有益的：
算法E(欧几里得算法)。给定两个正整数m和n，求它们的最大公因子，即能够同时整除m和n的最大的正整数。
E1.〔求余数〕以n除m并令r为所得余数(我们将有0≤r＜n)。
E2.〔余数为0？〕若r=0，算法结束；n即为答案。
E3.〔互换〕置m←n，n←r，并返回步骤E1。■
当然，欧几里得并非就是以这样的方式来给出他的算法的。上面的格式充分演示了在给出本书中所有的算法时贯穿全书的风格。
我们对所讨论的每一个算法，都给出了一个标识的字母(例如上边算法中的E)，并且用这个字母后面接上数字(例如E1，E2等等)来标识这个算法的步骤。书中各章分为编了号的节，在一节之内的算法仅用字母来标识；但当在其它节中引用这些算法时，则附以相应的节号。例如，我们现在是在第1.1节；在这一节中，欧几里得算法叫做算法E，而在后边的节引用它时，就记作算法1.1E。
一个算法的每一步(例如上边的步骤E1)以一个方括号中的一个短句开始，它尽可能简短地概括这一步的主要内容。这一短句通常也出现在一个与这个算法相对应的框图(例如图1)中。借助于框图，读者将有可能更直观地看出这个算法的流程。
图1 算法E的框图
在概括性的短句之后，是有待执行的某个动作或有待作出的某个判断的文字符号的叙述。偶而也有带圆括号的注释(例如，步骤E1的第二句)，它是关于这一步的说明性信息，通常指出变量的某些特征或这一步的当前目标，等等；带圆括号的注释并不影响属于这一算法的动作，而只是为了便于帮助读者理解。
(未完待续)
本文地址：http://com.8s8s.com/it/it35211.htm