数值算法与非数值算法

　　本书分为数值算法和非数值算法两部分，介绍了数据结构、各种算法以及数学分析法与程序的概念、原理、相互关系和应用。数值算法部分包括多项式与线性代数方程组，矩阵与非线性方程，插值、逼近及其应用，数字信号处理，小波变换等内容。非数值算法部分包括线性表、栈、队列和串，树，图，排序、查找与文件操作，并行算法等内容。本书附录部分还介绍了电子商务系统中的加密算法、用于图像处理的并行计算机结构特征以及算法在数据压缩中的应用、COM原理和Web服务的标准与组织。本书可作为非计算机专业数据结构（及算法）等课程的本科生教材，也可作为相关专业的？芯可騇BA人员的参考书。前言人类数学能力的提高与采用的手段是分不开的，从远古时候的结绳计数到现在的电子计算器和计算机，每一步的前进都使人们深受鼓舞。计算机不仅发展了应用数学，使数学与其他学科结合得更加紧密，而且发展了数学本身。随着计算机技术的进步，人们越来越依赖计算机去完成复杂的计算任务。现在所使用的各种计算机都是根据冯·诺依曼计算机理论设计和制造的，该理论有三个要点：·计算机硬件系统由运算器、控制器、存储器和输入/输出设备等基本单元组成·计算机内部的运算指令和数据必须采用二进制数字（0或1）表示。·计算机在运行时必须先将事先编制好的程序和数据调入主存储器（即通常所说的内存），然后执行程序中所设置的全部指令。人们使用计算机，使计算机能够按照人类的意志进行工作，就需要与计算机交流信息。然而，计算机硬件只懂自己的指令系统，即只能直接执行用相应机器语言编写的代码程序。计算机语言就是人与计算机之间通信的语言。而程序是为了解决某一个特定问题用一种语言编写的指令序列。程序设计一般包括确定数据结构、确定算法、编码、调试程序、整理并写出文档资料等内容。著名的计算机科学家沃思（NikiklausWirth）提出的公式是：程序=数据结构+算法直观地说，数据是描述客观事物的数字、字母和符号，是计算机程序使用和加工的“原料”。算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的且是明确的，此运算顺序将在有限的次数下终止。计算机解题的过程实际上是在实施某种算法。因此，算法通常是指计算机算法（计算机算法不同于人工处理的算法）。一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称该问题是算法可解的。一个算法执行结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。计算机算法可以分为两大类：数值运算算法和非数值运算算法。数值运算的目的是求数值解，如求方程的根、求函数的定积分等都属于数值运算范围。非数值运算包括的范畴十分广泛，最常见的是用于事物管理领域。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。由于数值运算有现成的模型，可以运用数值分析的方法，因此对数值运算算法的研究比较深入，算法比较成熟。同时，对各种数值运算都有比较成熟的算法可供选用。人们常常把这些算法汇编成册（写成程序形式），或者将这些程序存放在磁盘或磁带上，供用户调用。例如，有的计算机软件系统提供“数学程序库”，使用起来十分方便。而非数值运算的种类繁多，要求各异，难以规范化，因此目前只对一些典型的非数值运算算法（如排序算法）进行了比较深入的研究。其他的非数值运算问题往往需要使用者参考已有的类似算法，重新设计解决特定问题的专门算法。算法不等于程序，也不等于计算方法。程序可以作为算法的一种描述，但程序通常还需考虑许多与方法和分析无关的细节问题，因为在编写程序时要受到计算机系统运行环境的限制。通常，程序设计的质量不可能优于算法的设计。从程序设计的角度看，一个程序应包括以下两方面的内容：·对数据的描述：在程序中要指定数据的类型和数据的组织形式，即数据结构（datastructure）。〖ZK）〗·对操作的描述：即操作步骤，也就是算法（algorithm）。实际上，一个程序除了数据结构和算法的影响外，还应当采用结构化的程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以说程序=算法+数据结构+程序设计方法+语言工具和环境也就是说，算法、数据结构、程序设计方法以及语言工具和环境四个方面共同构成了一个程序设计人员所应具备的基本素质。设计程序要综合地应用好这四个方面的知识。算法是灵魂，数据结构是加工？韵螅镅允枪ぞ撸喑绦枰捎煤鲜实姆椒āＫ惴ń饩觥白鍪裁础焙汀霸跹觥钡奈侍狻３绦蛑械牟僮饔锞洌导噬暇褪撬惴ǖ奶逑帧Ｒ嘈闯龊玫某绦颍搜《ê侠淼氖萁峁雇猓话憷此担丶牟街枋巧杓普范行У乃惴ǎ惴ǖ暮没到苯佑跋斐绦虻脑诵行省２涣私馑惴ň吞覆簧铣绦蛏杓啤Ｍ保萁峁怪猩晕⒏丛右恍┑乃惴ㄉ杓浦锌赡苡玫蕉嘀旨际鹾头椒ǎ缢惴ㄉ杓频墓顾挤椒ā⒍淞考傲幢怼⒘鞒掏技捌浔浠环椒ā⑺惴ū嗦搿⒌莨榧际酰约坝胩囟ㄎ侍庀喙氐募际醯取Ｄ骋换方谠擞貌缓茫蓟嵊跋斓剿惴ǖ恼迳杓啤＊？本书主要分为两部分。导言介绍了数据结构、算法与程序的基本概念及相互关系。第1～5章是本书的数值算法部分，其中包括：多项式与线性代数方程组，矩阵与非线性方程，插值、逼近及其应用，数字信号处理，小波算法。第6～9章是非数值算法部分，其中包括：线性表、栈、队和串，树，图，排序、查找与文件操作。第10章介绍并行算法，并初步展望了计算机科学中一个蓬勃发展的新兴学科。5个附录分别是：电子商务系统中的加密算法，用于图像处理的并行计算机结构特征，算法在数据压缩中的应用，COM原理和Web服务的标准与组织。与其他同类书籍相比，本书的特点具体体现在如下几个方面：·将算法知识、数据结构知识融于一体，本着务实和合理应用的原则，全部内容紧紧围绕算法实现这个核心和重点建立结构体系。·在叙述上避免复杂的数学推导，而在那些必需的关键之处，又能做到不省略中间步骤，给出全部的推导过程。·全书大多数章节内容都可自成体系（书中带“*”的内容可根据需要选用），以方便教学的取舍。·在术语的使用上尽量照顾不同层次、不同专业读者的需求。·以例题的方式提供了大量的可实际应用的算法模块。·鉴于算法最终要通过程序来实现，在附录中对算法及其实现的有关新技术的进展做了简要的介绍（如并行计算机体系、MS-COM组件标准和Web服务平台）。吉林大学徐一平教授、南开大学王津涛副教授参与了编写大纲的讨论；徐一平参与撰写了第1章和第3章；王津涛撰写了第4章和第6章；雷于生教授（华中科技大学）参与撰写了第7章和第8章；王学民副教授（天津大学）参与撰写了第8章和第9章；张彤副研究员（天津医科大学）参与撰写了第10章和附录D；夏寅贲（中国航空航天大学博士生）参与撰写了第3章和第7章；黄爱国讲师（天津对外经济贸易职业学院）除参与撰写了第2章、附录C和附录D外，还和周鑫一起对书中所涉及的算法逐一进行了斟定；其余部分为康晓东撰写，全书由康晓东统稿。许多人为此书的内容、评阅和出版贡献了他们的宝贵时间和精力。感激相关领域前辈学人们的工作，是他们的知识和研究成果充实了此书的内容（见参考文献）。感谢天津大学的师长们、南开大学的朋友们和天津医科大学的同事们对本书的关注与关怀，也正是他们的真知灼见减少了本书的纰漏。特别感谢电子工业出版社的熬然副社长、高平副总编辑和章海涛老师，也是正他们的努力才使得本书能早日与读者见面。特别感激西安交通大学张镇西教授、《世界医疗器械》编辑部李晓娴主编和迟寒雪副主编，感谢他/她们对编写本书的理解与支持。作者还特别感谢中国计算机学会教育委员会副主任、全国高等院校计算机基础教育研究会副会长、南开大学刘瑞挺教授的鼓励和指导，特别感谢中国工程院院士、原天津医科大学校长吴咸中教授的关心和扶持，感谢他们于百忙之中为本书赐序。最后，鉴于作者才疏学浅，书中肯定有值得商榷之处。诚恳地希望各位读者，各位研究和从事相关工作的学者专家提出宝贵意见。2002年8月定稿于南开大学教师公寓①①康晓东男，1964年生。主要研究方向：图像信号处理；多媒体信息集成。出版书籍多部，代表作有：《计算机在医疗方面的最新应用》（电子工业出版社）；《现代医学影像技术》（天津科技翻译出版公司）；《医学图像的数字化处理技术》（人民卫生出版社）；《网络多媒体技术与医学信息集成》（人民军医出版社）；《网络构建与网页设计》（人民邮电出版社）；《新编电学基础》（科学出版社）；《计算机程序设计》（中国海关出版社）；《网站规划与实施》（清华大学出版社）

暂缺《数值算法与非数值算法》作者简介

导言  1                  
 0.1  数据结构2                  
 0.1.1  数据的逻辑结构   2                  
 0.1.2  数据的物理结构   3                  
 0.2  算法   4                  
 0.2.1  算法的特征   4                  
 0.2.2  算法的描述与评价6                  
 0.2.3  并行算法8                  
 0.3  程序设计 9                    
 数值算法部分                    
 第1章  多项式与线性代数方程组   15                  
 1.1  多项式的概念与算法 15                  
 1.1.1  多项式的欧几里德算法 16                  
 1.1.2  多项式的剩余定理*.   18                  
 1.2  多项式的快速算法 20                    
 1.2.1 多项式求值的秦九韶方法 20                    
 1.2.2 具有系数预处理的多项式求值 21                    
 1.2.3    切比雪夫正交多项式   26                  
 1.3 线性代数方程组及其解法  31                    
 1.3.1  线性代数方程组的高斯消去法   32                    
 1.3.2  三对角线型和一般带型线性代数方程组的解法 36                  
 1.4  线性代数方程组的迭代解法 40                    
 第2章  矩阵与非线性方程    43                  
 2.1  共轭梯度法     43                  
 2.1.1  矩阵及其变换     43                  
 2.1.2  共轭梯度法 44                    
 2.2  矩阵相乘. 分解. 求逆和特征值计算 47                  
 2.2.1  矩阵相乘和分解 47                  
 2.2.2  求逆矩阵 55                    
 2.2.3  矩阵特征值计算 57                    
 2.3  非线性方程与方程组 64                    
 2.3.1  非线性方程 64                    
 2.3.2  非线性方程求根的简单迭代法 65                    
 2.3.3  牛顿法与插值法 68                    
 2.3.4  双点弦割法 69                    
 2.3.5  非线性方程组 70                    
 第3章  插值. 逼近及其应用   73                  
 3.1  常用插值方法 74                    
 3.1.1  拉格朗日插值 74                    
 3.1.2  埃特金(Aitken)插值 76                  
 3.1.3  阿克玛插值 77                    
 3.2  逼近与拟合 85                    
 3.2.1  逼近 85                    
 3.2.2  拟合 87                    
 3.3  数值积分 89                    
 3.3.1  梯形求积法 89                    
 3.3.2  用样条函数求积求微 93                  
 第4章  数字信号处理*   97                  
 4.1  FFT及其应用 97                    
 4.1.1  FFT变换 99                    
 4.1.2  卷积算法 105                    
 4.2  DFT及其应用* 109                    
 4.2.1  离散傅里叶变换109                  
 4.2.2  离散沃尔什变换 111                  
 4.2.3  离散余弦变换 117                  
 4.3  滤波算法与解托伯利兹算法 118                  
 4.3.1  滤波算法 119                  
 4.3.2  解托伯利兹算法 121                  
 第5章  小波算法及应用*125                    
 5.1  小波函数与小波变换 125                  
 5.1.1  从短时傅里叶变换到小波分析 126                  
 5.1.2  常用小波函数族 128                  
 5.1.3  小波变换 131                  
 5.2  多分辨分析与小波包分析 134                  
 5.2.1  多分辨分析 134                  
 5.2.2  小波包分析 140                  
 5.3  小波应用 142                    
 非数值算法部分                    
 第6章  线性表. 栈. 队和串   149                  
 6.1  线性表 149                    
 6.1.1  线性表的顺序存储结构与运算 149                  
 6.1.2  线性表的链式存储结构与运算 151                  
 6.1.3  循环链表 155                  
 6.2  栈. 队和串 163                    
 6.2.1  栈 163                    
 6.2.2  队 164                    
 6.2.3  串 166                    
 6.3  数组与广义表 175                    
 6.3.1 稀疏矩阵与十字链表* 176                    
 6.3.2  广义表 181                  
 第7章  树   182                    
 7.1  二叉树 183                    
 7.1.1  二叉树的定义和基本性质 183                  
 7.1.2  二叉树的存储结构 184                  
 7.2  递归. 遍历与线索树 185                  
 7.2.1  递归 185                  
 7.2.2  线索树 189                    
 7.2.3  树的二叉树插入和删除运算 192                  
 7.3  树的应用 196                    
 7.3.1  Huffman编码* 196                  
 7.3.2  堆与优先队列 199                  
 第8章  图   202                    
 8.1  图的表示法和存储结构 202                    
 8.1.1  图的表示法 202                    
 8.1.2  图的存储结构 203                  
 8.2  图的遍历 206                    
 8.2.1  深度优先搜索 207                    
 8.2.2  宽度优先搜索和求图的连通 208                  
 8.3  图的应用 210                    
 8.3.1  求图的生成树 210                    
 8.3.2  最短路径问题* 212                  
 第9章 排序. 查找与文件操作*  215                  
 9.1  排序 215                  
 9.1.1  基于比较的排序 215                  
 9.1.2  元组排序和公式分组排序 222                  
 9.2  查找 227                  
 9.2.1  基于元素间比较的查找 227                  
 9.2.2  使用数学公式进行查找 228                  
 9.3  文件操作 231                    
 9.3.1  集合操作 231                    
 9.3.2  文件操作 237                    
 第10章  并行算法初步*  246                  
 10.1  并行计算设计技术与模型 246                  
 10.1.1  并行算法设计的基本技术 246                  
 10.1.2  并行算法模型和理论 248                  
 10.2  并行数值算法 251                    
 10.2.1  并行求和算法 251                    
 10.2.2  SIMD上基于LDU分解的方程组求解算法    252                  
 10.3  并行非数值算法 254                  
 10.3.1  MIMDTC上的排序算法 254                  
 10.3.2  查找与匹配 255                  
 10.4  数据库的并行操作和连接 259                  
 10.4.1  数据库并行操作 259                  
 10.4.2  数据库的并行连接 263                  
 附录A  电子商务系统中的加密算法    265                  
 A.1  对称加密 266                  
 A.2  非对称加密 268                    
 A.3  数字签名与电子签名 269                    
 附录B  用于图像处理的并行计算机结构特征  273                    
 B.1  SIMD阵列结构 273                    
 B.2  流水线结构 275                  
 B.3  MIMD结构 276                  
 B.4  VLSI结构 281                    
 B.5  与图像技术相关的其他新型并行处理机 284                    
 附录C  算法在数据压缩中的应用   290                    
 C.1  有关数据压缩的概念 290                    
 C.2  统计编码 293                  
 C.3  预测编码 297                    
 C.4  变换编码 302                    
 附录D  COM组件标准及其扩展  308                  
 D.1  COM的原理与特性 308                  
 D.2  COM扩展 312                    
 D.3  关于COM+ 318                    
 附录E  Web服务原理   324                    
 E.1  Web服务框架体系 324                  
 E.2  Web服务的标准与组织 325