‘6.5树与等价问题………………………………………… 139 66赫夫曼树及其应用…………………………………………144 66.1最优二叉树(赫夫曼树)……………………………………144 6.6.2赫夫曼编码………………………………………146 67回溯法与树的遍历………………………………………149 6.8树的计数 中,甲4甲“甲4p中;pp,.;中;;;;+4中中;中.;;;日·,;;.. 第7章图… 7.1图的定义和术语………………………………………………156 7.2图的存储结构…… ·甲卓·甲 160 7.2.1数组表示法… 中······*:4‘···中“· …161 7,22邻接表………………………… ……………163 723字链表………………………………………………164 724邻接多重表………………………………………………166 73图的遍历………………………………………………………………167 7.3.1深度优先搜索……………………………………………168 73.2广度优先搜索…………………………………………169 7.4图的连通性问题………70 7.4.1无向图的连通分量和生成树……………… 170 74.2有向图的强连通分量 172 74.3最小生成树………………………………………173 744关节点和重连通分量……………………………………176 75有向无环图及其应用…………………………………………………179 7.5.1拓扑排序…………………………………………………180 7.52关键路径 ………………………………183 7.6最短路径…………………………………………………………186 76.1从某个源点到其余各顶点的最短路径……………………………187 76.2每一对顶点之间的最短路径………………………………190 第8章动态存储管理 ,中·p甲中中中甲●中中中;:中,中日,日号+日号中甲;中,中中,章 8.1概述 8.2可利用空间表及分配方法……195 8.3边界标识法 ………………………………………198 831可利用空间表的结构………………………………………198 832分配算法………………………………………………19 83.3回收算法… ………………………201 8.4伙伴系统 目,甲非 …………………………………203 4.1可利用空间表的结构……………… 电,甲垂中看●香 …………203 84.2分配算法……………………………………………204 84.3回收算法…
85无用单元收集…… 86存储紧缩……………………………………………………212 第9章查找…………………………………………………………………………214 91静态查找表…………………………………………………………216 91.1顺序表的查找……………………………… 216 912有序表的查找 218 91.3静态树表的查找………………………………………22 914素引顺序表的查找………………………………………………225 92动态查找表 甲春q,F中4、P中、审看4中非甲香中中;香甲中·,中垂中甲非由,中申,中、·中中·中·,甲中,事 921二叉排序树和平衡二叉树 ………………227 922B.树和B树………………………………………………238 923键树…………………………………………………247 93哈希表…… 931什么是哈希表 香号E甲号q甲,中甲 932哈希函数的构造方法 中导·卓 933处理冲突的方法………………………… 934哈希表的查找及其分析………… ………………258 第10章内部排序…… 香目+t,昏+中日+中、P.中、甲 ………………263 10.1概述…… 102插入排序…………………25 1021直接插入排序 ……………………………265 10.22其它插入排序…… ……………………………………266 10.23希尔排序…………………………………………271 10.3快速排序 ……………………………………273 104选择排序 277 1041简单选择排序…… 77 10.4.2树形选择排序………………………………………………278 10.43堆排序…………………………………………278 105归并排序 甲 283 10.6基数排序 丶s;b4;+·↓年·中:4中中;中··中··v··v:.号.中 10.61多关键字的排序… 中,+中· 10.6.2链式基数排序…………286 10.7各种内部排序方法的比较讨论…………………………………….289 第Ⅱ1章外部排序…………………………………………………293 111外存信息的存取…………………………………………… 112外部排序的方法 95 1.3多路平衡归并的实现………………………197 114置换选择排序 中;中“、·;;·;;日,·中·日;···中·身·4中 Ⅵ
11.5最佳归并树……… 第12章文件 ·,a中,中、中,中;;“中a中,中v l21有关文件的基本概念…… 122顺序文件……………………………………………308 123索引文件…………………………………………311 124ISAM文件和VSAM文件…… 313 12.4.1ISAM文件………………………………………………313 124.2ⅤSAM文件………………………………………… 316 12.5直接存取文件(散列文件)……………………317 126多关键字文件………………………………………………………319 12.6.1多重表文件…………………………………………319 126.2倒排文件……… ··带 ……………………………320 附录A名词索引…………………………………………………322 附录B函数索引………………………………………… 参考书目…………………………………
第1章绪论 自1946年第一台计算机问世以来计算机产业的飞速发展已远远超出人们对它的预 料在某些生产线上,甚至几秒钟就能生产出一台微型计算机,产量猛增价格低廉,这就 使得它的应用范围迅速扩展。如今,计算机已深人到人类社会的各个领城。计算机的应 用已不再局限于科学计算,而更多地用于控制、管理及数据处理等非数值计算的处理工 作。与此相应,计算机加工处理的对象由纯粹的数值发展到字符表格和图象等各种具有 定结构的数据这就给程序设计带来一些新的问题。为了编写出一个“好”的程序,必须 分析待处理的对象的特性以及各处理对象之间存在的关系。这就是“数据结构这门学科 形成和发展的背景。 11什么是数据结构 般来说,用计算机解决一个具体问题时,大致需要经过下列几个步骤:首先要从具 体问题抽象出一个适当的数学模型,然后设计一个解此数学模型的算法最后编出程序、 进行测试调整直至得到最终解答。寻求数学模型的实质是分析问题从中提取操作的对 象并找出这些操作对象之间含有的关系,然后用数学的语言加以描述。例如求解梁架 结构中应力的数学模型为线性方程组;预报人口增长情况的数学棋型为微分方程。然而, 更多的非数值计算问题无法用数学方程加以描述。下面请看三个例子。 例11图书馆的书目检索系统自动化问题。当你想借阅一本参考书但不知道书库 中是否有的时候;或者,当你想找某一方面的参考书而不知图书馆内有哪些这方面的书 时你都需要到图书馆去查阅图书目录卡片。在图书馆内有各种名目的卡片:有按书名编 排的、有按作者编排的还有按分类编排的,等等。若利用计算机实现自动检索,则计算机 处理的对象便是这些目录卡片上的书目信息。列在一张卡片上的一本书的书目信息可由 登录号、书名作者名分类号、出版单位和出版时间等若干项组成,每一本书都有唯一的 个登录号但不同的书目之间可能有相同的书名或者有相同的作者名或者有相问的分 类号。由此在书目自动检索系统中可以建立一张按登录号顺序排列的书目文件和三张 分别按书名、作者名和分类号顺序排列的索引表如图11所示。由这四张表构成的文件 便是书目自动检索的数学模型计算机的主要操作便是按照某个特定要求(如给定书名) 对书日文件进行查询。诸如此类的还有查号系统自动化、仓库账目管理等。在这类文档 管理的数学模型中计算机处理的对象之间通常存在着的是一种最简单的线性关系,这类 数学模型可称谓线性的数据结构。 例12计算机和人对奕问题。计算机之所以能和人对奕是因为有人将对奕的策略 事先已存入计算机。由于对奕的过程是在一定规则下随机进行的,所以为使计算机能灵 活对奕就必须对对奕过程中所有可能发生的情况以及相应的对策都考虑周全,并且,一个
l高等数学|樊映川 002理论力学}罗远祥」I1 00高等数学华罗庾S01 04线性代数栾汝书 高等数学|0000 樊块川01,… 002, 理论力学 902 华罗庚003 线性代数01,… 栾汝书104 图L.1图书目录文件示例 “好”"的棋手在对奕时不仅要看棋盘当时的状态,还应能预测棋局发展的趋势,甚至最后结 局。因此在对奕问题中,计算机操作的对象是对奕过程中可能出现的棋盘状态——一称为 格局。例如图1.2(8)所示为井字棋0的一个格局而格局之间的关系是由比赛规则决定 的通常,这个关系不是线性的,因为从一个棋盘格局可以派生出几个格局,例如从图 12(a)所示的格局可以派生出五个格局,如图12(b)所示而从每一个新的格局又可派 生出四个可能出现的格局。因此若将从对奕开始到结束的过程中所有可能出现的格局 都画在一张图上,则可得到一棵倒长的“树”。“树根”是对奕开始之前的棋盘格局,而所有 的“叶子就是可能出现的结局对奕的过程就是从树根沿树又到某个叶子的过程。“树” 可以是某些非数值计算问题的数学模型它也是一种数据结构。 ###薜 图1.2井字棋对奕“树” (a)棋盘格局示例;(b)对奕树的局部。 例13多叉路口交通灯的管理问题。通常在十字交叉路口只需设红绿两色的交 通灯便可保持正常的交通秩序,而在多叉路口需设几种颜色的交通灯才能既使车辆相互 之间不碰撞,又能达到车辆的最大流通。假设有一个如图13(a)所示的五叉路口,其中C ①#字棋由两人对奕。棋盘为3X3的方格当一方的三个模子占同一行或同一列或同一对角线时便为胜