(c语言版) 严蔚敏吴伟民编著 精华大学出版社
前言 数据结构”是计算机程序设计的重要理论技术基础,它不仅是计算机学 科的核心课程,而且已成为其他理工专业的热门选修课。本书是为“数据结 构”课程编写的教材,其内容选取符合教学大纲要求,并兼顾学科的广度和深 度,适用面广。 本书的第1章综述数据、数据结构和抽象数据类型等基本概念;第2章至 笫7章从抽象数据类型的角度,分别讨论线性表、栈、队列、串、数组、广义表、 树和二叉树以及图等基本类型的数据结构及其应用;第8章综合介绍操作系 统和编译程序中涉及的动态存储管理的基本技术;第9章至第11章讨论查找 和排序,除了介绍各种实现方法之外,并着重从时问上进行定性或定量的分析 和比较;第12章介绍常用的文件结构。用过(数据结构》(第二版)的读者容易 看出,本书内容和章节编排与1992年4月出版的《数据结构〉(第二版)基本一 致,但在本书中更突出了抽象数据类型的概念。对每一种数据结构,都分别给 出相应的抽象数据类型规范说明和实现方法 全书中采用类C语言作为数据结构和算法的描述语言,在对数据的存储 结构和算法进行描迷时,尽量考虑C语言的特色,如利用数组的动态分配实现 顺序存储结构等。虽然C语言不是抽象数据类型的理想描述工具,但鉴于目 前和近一、两年内,“面向对象程序设计”并非数据结构的先修课程,故本书未 直接采用类和对象等设施,而是从C语言中精选了一个核心子集,并增添 C++语言的引用调用参数传递方式等,构成了一个类C描述语言。它使本 书对各种抽象数据类型的定义和实现简明清晰,既不拘泥于C语言的细节, 又容易转换成能上机执行的C或C+十程序。 从课程性质上讲,数据结构”是一门专业牧术基础课。它的教学要求是 学会分析研究计算机加工的数据结构的特性,以便为应用涉及的数据选择适 当的逻辑结构、存储结构及其相应的算法,并初步掌握算法的时间分析和空间 分析的技术。另一方面,本课程的学习过程也是复杂程序设计的训练过程,要 求学生编写的程序结构清楚和正确易读,符合软件工程的规范。如果说高级 语言程序设计课程对学生进行了结构化程序设计(程序抽象)的初步训练的 话,那么数据结构课程就要培养他们的数据抽象能力。本书将用规范的数学 语言描述数据结构的定义,以突出其数学特性,同时,通过若干数据结构应用 实例,引导学生学了数据类型的使用,为今后学习面向对象的程序设计作一些
铺垫 本书可作为计算机类专业的本科或专科教材,也可以作为信息类相关专 业的选修教材,讲授学时可为S0至80。教师可根据学时、专业和学生的实际 情况,选讲或不讲目录页中带*的章节,甚至删去第5、8、和12章。本书 文字通俗、简明易懂、便于自学,也可供从辜计算机应用等工作的科技人员参 考。只需掌握程序设计基本技术便可学习本书。若具有离散数学和概率论的 知识,则对书中某些内容更易理解。如果将本书〈数据结构〉(C语言版)和《数 据结构》(第二版)作为关于数据结构及其算法的C和 Pascal程序设计的对照 教材,则有助于快速且深刻地掌握这两种语言 与本书配套的还有《数据结构题集)(C语言版),由清华大学出版社出版。 书中提供配套的习题和实习题,并可作为学习指导手册。 严蔚敏清华大学计算机技术与科学系 吴伟民华南师范大学计算机科学系 1996年7月
目录 第1章绪论…………………… 11什么是数据结构 12基本概念和术语 13抽象数据类型的表示与实现…………………………………………9 14算法和算法分析…… 1.4.1算法…………………………………………… 142算法设计的要求……………………………… 143算法效率的度量 ·,带中垂,非 ………………4 144算法的存储空间需求…………………………………17 第2章线性表……………………………………………………………………18 21线性表的类型定义……………………………………… 22线性表的顺序表示和实现……………………………………………21 23线性表的链式表示和实现…………………………………27 231线性链表 23.2循环链表 233双向链表……… 35 24一元多项式的表示及相加 第3章栈和队列 3.1栈… 311抽象数据类型栈的定义……………………………………44 312栈的表示和实现……………………………45 32栈的应用举例… 3.2.1数制转换………………………………………… 322括号匹配的检验……………………………… 323行编辑程序……… 3.24迷宫求解……… …………50 325表达式求值………………………………………52 33栈与递归的实现………… ·········甲···· 3.4队列 4,.中中中4·中·中·;p,中F中,,中丶甲声;,;·中,·,,中·中非,中中中·;辛4中、,; 58 3.4.1抽象数据类型队列的定义………………………………58 342链队列——队列的链式表示和实现………………………………60 343循环队列——队列的顺序表示和实现………………………63 3.5离散事件模拟…………………………………………………………65 Ⅲ
第4章串 ;··;;中·;中·P;;·:;44:.44;:;1;昏;号号;;4,日;日;;中4、4中、;4 41串类型的定义… ,曲目、甲专 4.2串的表示和实现 专●中··中、:,●;···;,非;专··?+,中.中,q中、加 42.1定长顺序存储表示…… ··,· 42.2堆分配存储表示 …………………………75 423串的块链存储表示……………………… 非,中,甲垂中布专中、垂中非垂 4.3串的模式匹配算法… 7yy 43.1求子串位置的定位函数Inex(s,T,pas)……………79 4.3.2模式匹配的一种改进算法……………………………………80 44串操作应用举例……………………………………………………………84 4.4.1文本编辑…………………… 442建立词索引表……………………………………………85 第5章数组和广义表…………………………………… 90 51数组的定义………………… 52数组的顺序表示和实现……………………………… 53矩阵的压缩存储… 看中带中·,中;;非中·中、;中;t中中·“·中,品中t·+中 5.3.1特殊矩阵 、4、,香“甲;·甲甲甲甲·P·非中、中。中·中垂中昏·4中 532稀疏矩阵……………………………6 54广义表的定义……………………………………………………106 55广义表的存储结构………………… ……109 5.6m元多项式的表示…………………………………………110 5.7广义表的递归算法…………………………………………………112 57.1求广义表的深度 113 57.2复制广义表 114 573.建立广义表的存储结构………………………………115 第6章树和二叉树………………………… 61树的定义和基本术语…………………………………………118 6.2二叉树…………………………………………………………………121 621二叉树的定义………121 622二叉树的性质…………………… 623二又树的存储结构………………………………………126 63遗历二叉树和线索二叉树……………………………………………128 631意历二叉树…… 128 632线索二叉树 韦争垂中·· +中、非;中专由 132 64树和森林…………………………………135 64.1树的存情结构……………………………………135 64.2森林与二叉树的转换………………………………137 64.3树和森林的遍历… 量P《4·t,;·;、中·甲 138 Ⅳ
‘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的方格当一方的三个模子占同一行或同一列或同一对角线时便为胜