目录 9.7.2区间堆的插入 ，。，,，。，·4,.··”，·”·”卡 359 9.73除最小元··.· 360 974区间难的初始化，··。·，·。，。，····，····。·，···· 361 9.75区间堆操作的复杂度，·，·····.············· 61 59.7.6区间外在找 361 98参考文献利和选读材料。··。，。···。·············· 363 第10章高效二叉查找树 3 $10.1最优二义杏找树 366 S10.2AVL树. s10.3红-黑树 384 510.31定义 384 510.3.2红-黑树的表示 386 610.3.3红-黑树的个找 386 510.3.4红-黑树的插入 386 510.3.5红-黑树的别除 389 510.3.6红-黑树的合开 g 510.3.7红-树的分裂··. 391 s10.4 Splay树. 393 s10.4.1自底向上Splay树 394 s10.4.2自项向卜Splay树 398 510.5参考文献和选读材料 403 第11章多路查找树 405 5111m-路找树。·· 405 5111.1定义和性质 405 51112m-路杏找树的找.，。，··，·。 406 611.2B-树 407 511.2.1定义和性质. 407 511.2.2B-树中数据元素的个数 408 511.2.3B-树的插入 409 511.2.4B-树的删除 412 s11.3B+-树.··，···· 419 51131定义. 419 11.3.2B+树的查找 420 511.3.3B+-树的插入 420 611.3.4B+-树的刑除 422 11.4参考文献和选读材料············ 426
录 XV 359 360 361 361 361 363 366 366 373 384 384 386 386 386 389 389 391 393 394 398 茌03 405 405 405 406 407 Z107 408 409 412 419 茌19 420 420 422 426 § 9.7· 2 lx问 堆 的 插 入 ,. . § 9.7.3 删 除 最 小 元 。 . .。 . , § 9.7.4 l× 问 堆 的 初 始 化 。 . , m.7,5 区 间 堆 操 作 的 复杂度 . § 9.7,6 区 问 外 伶 找 .。 . . . ψ 。8 参 考文献 和 选渎材 料 . . 。 第 10章 高 效 二 叉 查找树 § 10.1 最 优 工 义 含 找 树 . . . , § 10.2 AVL树 . . 。 . . . . § 1o.3 红 -黑 树 . . . . . · . § 10· 3· 1 定 义 . . . 。 . · § 10.3,2 红 -黑 树 的 农 示 ,. . § 10.3.3 红 -黑 树 的 今 找 . . § 10.3· 4 红 -黑 树 F向 插 入 . 。 , § 10.3.5 红 -黑 树 f向 删 除 . ,. § 10· 3· 6 红 -黑 树 的 合 并 . . § 10.3· 7 红 -黑 树 的 分 裂 . . § 10.茌 splay树 ,.。 .· · · · · · · · §10· 4· 1 臼 底 向 l二 Splay树 . 。 §10,4· 2 亡 J∫ 贞 向 卜 Splay树 . , §10.5 参 考文献和选渎材料 . . . 第 11章 多 路查找树 § 11.1 〃 -路 合 找 树 . . . . . , § 11.1,1 定 义 和 性 质 . 。 . . § 11.1· 2 ″ -路 合 找 树 的 含 找 . 。 § 11.2 B-树 ,. . . . . · . . § 11,2.1 定 义 和 性 质 . . . §11.2·2 B-树 中数据元紊的个 数 § 11· 2· 3 B-树 的 插 入 ,. . . § 11· 2· 4 B-树 的 删 除 . ,. . § 11.3 B+-树 .,。 。 .· · · · · · · · · · § 113.1 定 义 . . . ,. · § 11.3.2 B+-树 的 合 找 。 . . 。 § 11.3.3 B+-树 的 插 入 。 . 。 , § 11.3· 4 B+-树 f向 删 |馀 . . . §11。 茌 参 考 文献和 选读材 料 .
xvi 目录 第12章数字查找结构 427 S12.1数字查找树 8121.1定义 427 1212个找、插入、除.，.，. 2 sl2.2二路Trie树'Patricia树 428 512.2.1 路Trie树.， 428 612.2.2乐缩二路Trie树 29 s12.2.3 Patricia树. 4 612.3多路Trie树 434 6123.1定义 。4。 434 s12.3.2Trie树的布找 3 S1233取样策略 812.3.4Trie树的石入 439 123.5Trie树的别除 439 12.3.6变长关键字 440 s12.3.7Tie树的高度 440 81238问需求Jt结'i相 0 12.3.9在找前缀及其应用， 43 8123.10k宿Trie树 444 s12.3.11设skip域的l缩Trie树 446 S12.3.12设边标i记的k缩Trie树 446 S12.3.13 压缩Tre树的空间需求 449 s12.4后级树 450 512.41你见过基因串吗 450 S12.4.2斤缀树数据结构 450 12.4.3.！：在子中！（后缀树的找） 453 612.4.4后餐树的妙川 454 512.5Tie树与互连网的包转发 455 512.5.1P路由 455 s12.5.21-bit Trie树. 56 612.5,3村定步长Trie树 4 512.5.4不定步长Trie树 459 612.6参老文献利和选读料 461 索引
XV1 第 1z章 数 字查找结构 § 12.1 数 字 佥 找 树 . . . . . . . · § 12.1.1 定 义 ,. ,. ,. · . · . · § 12.1.2 众 找 、 插 入 、 删 除 。 . ,. · · §12.2工 路 Trie树 丨J Patricia树 . 。 . ,。 § 12,2.1 璐 Trie树 . ,. ,. · . § 12。 ⒉ 2 压 缩 工 路 Trie树 . . 。 . 。 , § 12.2,3 Patrkia树 . . . . . . · § 12.3 多 路 Trie树 . . . . · . · . § 12.3.1 定 义 . 。 . ,. · . · . · § 12.3.2 Trie树 的 伶 找 . . . . . . § 12.3,3 取 样 策 略 . . . . . . · § 12.3,4Trie树 的 插 入 。 . 。 . . · · § 12.3.5Trie树 的 删 除 . . . . ,. § 12,3.6 变 长 关 键 字 . . . . . · § 12.3.7Trie树 的 高 度 . . . . . . §12.3.8 空 间需求 ∴j其 它纬点纬构 . §12.3.9 今 找前缀及其应∫Ⅱ . . ,. § 12.3.10 丿 【 缩 Trie树 . ,. ,。 . · · §123.11 设 酞 ip域 的 丿{|缩 Trie树 . . §12.3.12 设 边 标 记 n勹 丿【 缩 Trie树 . . §12.3.13 丿 【 缩 Trie树 的 空 问 需 求 . . § 12.砼 后 缀 树 。 . . .,. .,. · · . . § 12.4.1 你 见 过 基 l,xl申 吗 。 . . . § 12,4.2 后 缀 树 数 据 结 构 . . . . . §12.4,3。 今!今 !今 :F串 !(后 缀树的今找 ) § 12.茌 .4 丿 f亏 缀 树 的 妙 用 . . . . . , § 12,5 Trie树 与 互 迕 网 的 包 转 发 . . . . § 12.5.1 IP路 由 . . . . . . · § 12.5.2 ⒈ bit Trie树 . . . 。 . . § 12,5.3 H定 步 长 Trk树 ,. 。 ,. . · § 12,5.茌 不 定 步 KTrie树 . . . . , §12.6 参 考文献和选读材料 ,. . . . . 索 引 录 427 427 427 427 428 428 429 429 434 砼34 茌36 437 439 439 4茌0 4茌0 440 4茌3 444 茌46 446 茌茌9 450 450 450 453 454 455 455 茌56 茌57 459 461 463
第1章基本概念 S1.1概观：系统生命周期 本书读者应几备扎实的结构化程序设计技能。要获得这些技能，读者通常应学过程序设 计基础一类课程。这类课程的培养目标就是传授结构化程序设计技能，但课程强调的是语言 本身的语法形式语句使用规则，学生在这个阶段通常只能编写很简单的程序，解决的闷题 不州说也是很简单的。这类简单问题，一般而言，只要接选用程序设计语言提供的某语句 也许就能完成求解，例如，用数组存储数据，市利川wh11。循环语句，可能就足以解决这 阶段的许多问题了。 本书要指导读者向前迈一人步，人幅度提高编程能力，因为以后编写的程序，其规模要 人很多，功能也要复杂得多。不用说，编写规模庞人而复杂的程序，不但需要更强有力的日 具，还一定需要更高级的编程技术。我们希望在随后的学习过程，读者应扎实学握数据的抽 象思维方法，同时必须熟练学握算法的规范声明、算法的性能分析、算法的性能评价等诸多 技能。设置本章的日的就是要详细论述这些内容。此外，递山程序设计方法同样至关平要 读者也必须熟练学提，因此也是本章讨论的内容，但论述得较为简明而且篇幅不很人。我们 提请读名注意，如果读者以前对递)程序设计基础术给予足够重视，了解流于肤浅，那么必 须仔细研读这方面内容，以后一定会深感人有益处。然而，在讨论各种几与各项技术之前， 我们必须强调，编程可不仅仪是写程序代码，即写完一条条程序语句就万事人占了。马与之截 然相反，优秀的程序员有完全不同的观点。程序设计的首要问题，成该是肖先把人规模程序 系统分解成许许多多自成体系且相对独立的组成部件，然后再为各部分之间存在的相互调 用，定义严格的调用格式。从系统观点米看形式各异的程序开发过程，实际上每种开发过程 都有其生命周期，生命周期依次由需求、分析、设计、编码、验证诸多阶段构成。对于各阶段 的论述，尽管可以分门别类，独立讨论，但各个阶段之间同时还会存在相当紧密的功能重叠 '与互相关联，为其划分时间顺序可以说仅仅是原始而粗略的。在选读材料与参考文献一肯 我们列出了·一些文献资料，供读名更加深入地了解系统的生命周期以及各阶段的详细含义。 ()需求阶段所有人规模程序设计项日，都是从确定规范声明开始，规范声明明确定义了 项日的目标。需求用米描述程序员必须获得的信息，即，给定的条件（输入）应该是什 么，生成的结果（输出）应该是什么。一般而，刚开始的时候，规范声明往往粗略 粗糙，随后的求精过程成不断完善有关输入、输出的描述，直到包括全部细节，涵盖所 有情形。 (2)分析阶段仔细列出需求之后，就可以开始分析阶段的上作了。本阶段先把问题分解成 规模适中且便于处理的各个部分。分析方法可以分为两类，一类是自底向上，一类是口 顶向卜。白底向上一类方法已遗槟弃，这类方法采用的策咯不考虑结构信息，一开就 侧重编写代码的细节，显得杂乱无章。如果该类方法不幸被选用，而且程序员义缺乏人 局观，那么最后的程序会成为相互之间松散连接义支离破碎的片段，这样，错误极可能 蔓延不止，扩散到各处。打个比方，自底向上一类方法很像只用一个蓝图建各式房 根本不计房茶的功能和用途，而把所有房：都看成由墙体、左项、水暖管道组成的宋板 1
第 1章 基 本概念 §1.1 概 观 :系 统 生 命 周 期 本书读者应具备扎实的结构化稆序设计技能。耍获得这些技能,读 者通常应学过稆序设 计基础一类课程。这类课稆的培养 日标就足传授结构化程序设计技能,但 课程强调的是语言 本身的语法形式与语句使用规则,学 生在这个阶段通常只能编写很简单的程序,解 决的问题 不用说也是很简单的。这类简单问题,一 股而 ∴,。1要血接选用稆序设计语 亩捉供的某语句 也许就能完成求解,例 如,用 数纽存储数据,再 利川 wh±1e循 环语句,可 能就足 以解决这一 阶段的许多问题了。 本 {氵要指 导读者向前迈一人步,人 幅度提高编下V能 力,囚 为以后编写的程序,其 规模要 人很多,功 能也耍复杂得多。不用说,编 写规模庞人而复杂的程序,不 但需耍更强有力的 I∶ 具,还 一定需要更高级的编秽技术。我们希望在随后的学习过稆,读 者应扎实掌握数据的抽 象思维方法,同 时必须熟练掌握算法的规范芦明、算法的性能分析、第法的性能评价等诸多 技能。设置本章的 目的就是要详细论述这些 内容。此外,递 归l不V序 设计方法同样至关重要, 读者也必须熟练掌握,F,xl此也足本章讨论的内容,但 论述得较为简明而 日.篇幅不很入。我们 提请读者注意,如 呆读者以前对递少l稆序设计基础未给予足够亘视,了 解流 于肤浅,那 么必 须仔细研读这方面内容,以 后一定会深感人有溢处。然而,在 讨论各种 l∶具与各项技术之前, 我们必须强调,编 稆可不仅仅足写稆序代码,即 写完一条条稆序语句就万莩人 占了。LJ乏截 然相反,优 秀的稆序员有完仝不同的观点。稆厅设计的 肖要问题,应 该足首先把入规模稆序 系统分解成许许多多 fl成 体系 H^相 对独立的组成部件,然 后再为各部分之间存在的相互调 用,定 义严格的调川格式。从系统观点来看形式各异r向稆序开发过稆,实 际上每种开发过程 都有其Ft∶命周期,土 命周期依次由需求、分析、设计、编码、验证诸 多阶段构成。对 ∫各阶段 的论述,尽 管可 以分门别类,独 立讨论,但 符个阶段之间同时还会存在相当紧密的功能丑叠 、互相关联,为 其划分时问顺序可以说仅仅足原始而粗略的。存i选读材料 Ιj参 考文献一节, 我们列出了工些文献资料,供 读者更加深入地了解系统的生命周J切以及各阶段的详细含义。 (1)需 求阶段 所有人规模稆序设计项 日,都 足从确定规范卢明开始,规 范声明明确定义了 项 日的目标。需求用来描述程序员必须获得的信息,即 ,给 定的条件 (输 入)应 该楚什 么,生 成的结呆 (输 出)应 该是什么。一股而 占,刚 开始的时候,规 范声明往往粗略且 粗糙,随 后的求精过稆应不断完善有关输入、输出的描述,直 到包括全部细△,涵 斋所 有情形。 (2)分 析阶段 仔细列出需求之后,就 可 以开始分析阶段的 li作了。本阶段先把问题分解成 规模适中Ⅱ^便于处理的各个部分。分析方法可以分为两类,一 类足 白底 向上 ,一 类是 臼 顶 向 卜。白底 向上一类方法 己遭摈弃,这 类方法采用的策略不考虑纬构信息,一 开始就 侧重编写代码的细节,显 得杂膏L无章。如呆该类方法不莘被选川,而 Ⅱ程序员义缺之大 局观,那 么最后的程序会成为相互之间松散迕接义支离破碎的片段,这 样,错 误极可能 蔓延不 |卜,扩 散到各处。打个比方,臼 底向 L一 类方法很像只用 一个蓝图建各式房Ⅳ, 根本不计房犀的功能和用途,而 把所有房厣都吞成由墙体、厣顶、水暖管道细成的笊板
第1章基本概念 建筑对象。这种做法实际上忽略了房宗的使州特性和居住特性，可以说完个缺乏全局考 悲。血然根本没人愿意住进这样建成的房：，还是有许多序员，特别是新手犁序员， 却相信山己无需规划也可以编制出既优秀还不会出错的程子。 与白底向上一类方法不同，山项向卜法一开始：就要水先确定程序的指定口标，并 利用该阶段所得成果，将程序分解成易丁管理的组成成份。白顶向下方法会生成大量框 图(diagrams),用于随后阶段，即系统设计阶段的设计依据。分析阶段根据问题种类的 特点往往会提出多种候选方案，以后通过研究、比较，最后筛选出最佳方案。 (③)设计阶段该阶段延续分析阶段的：作。设计人员从两方面进一步研究系统，这时，不 但要考察程序所需的数据对象，还要考察针对数据对象而设置的各种樑作。前一一种考察 的结果是创建抽象数据类刊：后一种考察的结果史侧重算法的规范声明和算法的设计 策略。以制订高校教学计划为例，这时，典型的数据对象应包括诸如学生、课程、教授 等等：而典型的操作很可能包括在一种或多种数据对象之上完成插入、剩除、查找等功 能，特定的操作应包括向已开课程组成的集合之中插入新课程，还应包括作询某教授的 上讲课程。 抽象数据类型和算法的规范六明与实现语言无关，因此细程的实现细节可以推迟。 尽管日前必须确定每种数据对象所需的信息，不过这时却可以暂时忽略编写代码所需 的实现细节。例如，假定已经确定了学生数据对象要包合姓名、补会保险号码、专业 电话号码，但这时尚未决定学生清单究竞该如何实现。到了后续章节，我)会了解到 实现学生清单实际上有多种数据结构可供挑选，例如，我们可以从数组、链表，树三种 数据结构中按照需要米选择。设计阶段把实现细节尽量推迟有两方面好处，其一，可以 为选实现语言的种类留有余地，其二，可以留给我充足的时间去选抒蚊高效的实现 语。 (4)求精与编写代码阶段到这一阶段，我」首先选择数据对象的（存储）表示，其次要实现 各种操作的算法。上述先后次序很乎要，因为算法的效率取决数据对象的表示。也就 是说，在确定数据表示之前，假如要考悲算法，那么算法应该与数据对象尤关。 通常，进行到日前阶段，我们多半会发现日前完成的系统设计并不是最的。一种 可能是，我们这时得知，其他人也做过类似项门，而他们的方案比我们的方案更优越 分一种可能足，连我山已也觉得现行方案欠佳，换一种设计方案也诈可以更好。无论 如何，如果原米的设计方案足够好，那么上吸收其它优点并难事，可以比作锦上添花 实际上，避免过早地涉及编码细节，正是已经预计到这些情况都有可能出现，并事先做 好了准备。如果现行万案不可行，就必须把全部方案推倒米，由丁这时没有过沉重 的包袱，所以，至少我」再提出新的设计方案，其代价就不至丁过人，时间也不会花费 太多，而且出错的可能也许史少了，因此，无论如何，即使要推倒重米，从代价方面米 考思，对我价门多少也是个安做。 (5⑤)正确性验证阶段本阶段作有3方面内容，包括：①证明程序正确，②用合适的输入 数据测试程序，③改正错误。这3方面内容业己经过深入、细致的研究，实施方法很多， 本书显然不可能做全面彻底地讨论，所以，我！列出如卜要点，并做一些简述
(3) 第 1章 基本概念 建筑对象。这种做法实际 ll忽略了房岸的使川特性和居住特性,可 以说完仑缺乏全局考 虑。虽然根本没人愿意住进这样建成的叻丿彳;,仁!还足亻l^许多稆序员,特 别足新手稆序员, 却相信 山己尢需规划也 HT以编制出既优秀还不会出锴的稆序。 Lj臼底向上一类方法不丨司,rJ顶 向 卜方法 一斤始就要 扌先确定程序的指定 目标,并 利用该阶段所得成呆,将 稆序分解成易 J1管理的组成成份。白顶向 卜方法会生成人蚩框 图 (山agrams),用 于随后阶段,即 系统 设计阶段的设计依据。分析阶段根据 问题种类的 特点往往会提出多种候选方案,以 后通过研究、比较,最 后筛选出最住方案。 设计阶段 该阶段延续分析阶段的 I∶作。设计人员从两方面进一步研究系统,这 时,不 但耍考察程序所需的数据对象,还 要考察针对数据对象而设置的各种操作。前 一种考察 的结呆足创建抽象数据类型;后 一种考察的纬呆更侧重算法的规范声明和算法的设计 策略。以制订高校教学计划为例,这 时,典 型F向数据对象应包括诸如学生、课程 、教授 竿竿;而 典型的操作很可能包括在一种或多种数据对象之上完成插入、删除、众找等功 能,特 定的操作应包括向己开课稆组成的集合之中插入新课程,还 应包括 r丫洵某教授的 主讲课程。 抽象数据类型和算法的规范声明Ij实现语 高无关,lkl此编稆的实现细节可以推迟。 尽管 冂前必须确定每种数据对象所需的信息,不 过这时却可以暂时忽略编写代码所需 的实现细节。例如,假 定已经确定 了学生数据对象要包含姓名、社会保险 号码 、专业、 电活号F-s,但这时尚木决定学生清单究竞该如们实现。到了后续章节,我 们会 了解到, 实现I生 清单实际上有多种数据结构可供挑选,例 如,我 们可以从数组、链表,树 二种 数据结构中按照需要来选择。设计阶段把实现细节尽量推迟仃两方面好处,其 一,可 以 为选择实现语 宀的种类留有余地,其 工,可 以留给我们充足的时间去选抒最高效的实现 语 宀 ^。 求精与编写代码阶段 到这一阶段,我 们 肖先选择数据对象的 (存储)表 示,其 次耍实现 各种操作的算法。上述先后次序很 咀要,|川为算法 r向效率取决 J=数据对象的表示。也就 足说,在 确定数据表示之前,假 如耍考虑算法,那 么算法应该JJ数据对象无关。 通常,进 行到 日前阶段,我 们多半会发现 日前完成的系统设计并不是最好的。一种 可能足,我 们这时得知,其 他人也做过类似项 冂,而 他们的方案比我们的方案更优越 ; 另 一种可怠邕足,迕 我们 臼己也觉得现行方案欠仕,换 一种设计方案也许可以更好。无论 如何,如 呆原来的设计方案足够好,那 么去吸收其它优点并叫|∶难芋,可 以比作锦上添花。 实际上 ,避 免过早地涉及编码细 Ij,止足已经顶计到这些情况都有可能出现,并 芋先做 好 了准备。如呆现行方案不可行,就 必须把全部方案推倒重来,由 ∫这时没有过 「沉重 的包袱,所 以,至 少我们再捉出新的设计方案,其 代价就不至 J=过人,时 问也不会花费 太多,而 且出错的可能也许史少了。「kl此,无 论如何,即 使要推倒重来,从 代价方面来 考虑,对 我们多少也足个安慰。 ⑶ 正确性验证阶段 本阶段 l∶作有 3方 面 内容,包 括:① 证明稆序正确,② 用合适的输入 数据测试程序,③ 改正错误。这 3方 面 内容业 已经过深入、细致的研究,实 施方法很多, 本书显然不可能做全面彻底地讨论,所 以,我 们列出如 卜耍点,并 做 一些简述。 (茌)
51.2指针和动态存储分配 。正确性证明：，的正确件正明数2调明类以之处，而以采用数学止明 方法。然而，用数学方法证明程序的正确，不但耗时，面H对人规模程了设计项口 也不话用。由「饮件顶目的开发有限，一股面，要为所有，予都给完企的 数学证明并不现实。因而，选并那些已知：是止确的算法，自然能人人减少出错机会 本书介绍的人多数算法，其止确性证明都是通过形式证明完成的，因而是实用的， 也是可常的。所以，我要说，这些算法全都是程序员武器车中的利器 ·测试由于算法马与特定语言无关，内而，证明序的正确性可以早于编写代码阶 段：然而，完成测试作必须用到能多实际达行的代码，还必须使用真实的测试数 据集。选取测试数据集的时候切记要递慎，数据集应覆盖各种情形。新手最易犯的 错误是：认为程序只要无诒法错误就一定是正确的，显然，这样的想当然口然人错 特错了。假如选取测试数据马马虎虎，比如只州一组数据去测试而根本不计其余 之后必将遗患无穷。合格的测试数据集应检个代码的所有片段，使尤一遗，全部 都应得到验证。举例米说，对于aw1tch语句，测试数据必须检作所有caae语句。 测试的第一个日标是程序的正确性，这无凝至关重要，然而，程序的运行时间 也同样重要。正确的程序，如果运行缓慢，仍无价值。本的算法人多都有运行时 间的理论估计，并给出了推导过程。对达行时间仪涉及某段关键代码的情形，则 成侧重该段代码的运行时间分析，本章同样也讨论这类部估计问题。 ·纠错：如果一切进展顺利，正确性证明与测试结宋会界定错误代码。读者车记 纠错的难易程度取决于早斯设计阶段'编代码阶段选择的决策。对于规模庞人、 功能复杂的程序，假如忽视文档的编制和整理，加上代码又纠缠不清，象一意人 利细面条，那就必然会成为程序贝的恶梦，这是确定无疑的。去调试这样的程序， 次纠错极可能又会引入其它多处新错。之然相反，如果程序文档完整，模块 白成体系，而日相互参数周用关系青斯，那么出式作将深易得多，这也出价定 无疑的。因该说，如果可以去调试一个又一个独立的模块，之后再把它们合成为完 整的系统，那么调试1作显然将史加容易了。 S1.2指针和动态存储分配 512.1指针 指针是C语言的基本概念，C语言中指什无处不在实阿：上，每种数据类型T,都有相 应的指向T的指针类型。指针类型变量存放的值，实网：上就是内存地址：。指针类型有两个敏 基本的操作： 立取地址操作 *去引用（间接引用）操作 给定如下声明语句： int i,pi 我们知道1是整型变量，而p1是指向整数的指针。如果令：
§】。2指 针和动态存储分配 3 ●正确性证明: 程 序的正确性证 明 ∫j数 r严订「叮J仃 类似之处,|川 雨ji刂以采川数学证明 方法。然而,用 数学方法证明不V忄 的止确,不 亻:↓耗时,i两且对人规枝程序设计项 口 也不适用。由1·软件项 日的开发时闸有限,一 股丨nj广l,要 为所有稆序都给出完仝的 数学证明并不现实。囚而,选 择那些 己知足止确的箅法,臼 然能人人减少出错机会。 本 |)介绍的人多数算法,其 正确性证明都足通过形式证明完成的,xl而 是实用的, 也是可靠的。所以,我 们要说,这 些箅法全都足稆序 员武器库屮的利器。 ·测试: 由 Tˉ算法与特定语亩无关,|川而,证 明稆序的止确性可 以甲 1·编t亏代码阶 段 ;然 而,完 成测试 l∶作必须用到能够实际运行的代码,还 必须使川萁实的测试数 据集。选取测试数据集的时候切记要谨慎,数 据集应覆盖各种情形。新手最易犯的 错误是:认 为稆序只要无语法借误就一定足止确的,显 然,这 样的想当然 臼然人错 特错 了。假如选取测试数据马 吗虎虎,比 如只川 一细数据 ±·测试而根本不计其余, 之后必将遗患无穷。合格的测试数据集应检 今代码的所有片段,使 尢一遗湘,仝 部 都应得到验证。举例来说,对 ]1臼W土△ch讠亻丨句,测 试数据必须检今所有 cage语 句。 测试的第一个 冂标是稆序的止确性,这 尢疑至关亘要,然 而,不V序 的运行时闸 也同样重要。正确的稆序,如 呆运行缓J浸,仍 无价伯。本 |氵的算法人多都仃运行时 间的理论估计,并 给出了推导过稆。对 J1运行时闸仅涉及某段关键代码的惜形,则 应侧重该段代码的运行时问分析,本 带同样也讨论这 类丿,刂部估汁问题。 ·纠错: 如 呆 一切进展顺利,Ⅱ∶确性证明 Ij测 试纣i宋会界定错误代码。渎者丿“`牢 记, 纠错的难易程度取决 J1早期设计阶段 lj编t了代flI阶段选择的决策。对 J·规模庞入、 功能复杂的稆序,假 如忽视文档的编制和整理,加 上代码 义纠缠不清,象 一盘意人 利细面条,那 就必然会成为稆序员的恶梦,这 足确定尢疑f向。去调试这样的稆序, 一次纠错极可能义会引入其它 多处新错。Jj之截然卞H反 ,如 呆稆丿r文 档完整,模 块 白成体系,而 且相互问参数凋川关系清晰,那 么凋试 卜作将容易得多,这 出是确定 无疑的。囚该说,如 呆可以去凋试 一个义一个独 止的模块,之 后再把它们合成为完 整的系统,那 么调试 l∶作显然将 吏加容易了。 §1.2 指 针和动态存储分配 § 1.2.1 指 针 指针是 C语 言的基本概念,C语 占中指针 尢处不住c实 际上,每 种数据类Ⅱ刂T,都 有本H 应的指向 T的 指针类型。指针类型变甘存放的值,实 际 上就足内存地山|∶。指针类Ⅱ刂有两个鼓 基本的操作: &取 地址操作 ★去引用 (间接引用)操 作 给定如 卜声明语句: 我们知道 土是整型变量,而 p土足指向整数的指针。如呆令: