数据结构（C语言版）（第2版） (严蔚敏 李冬梅 吴伟民)（Z-Library）

📄 File Format: PDF

💾 File Size: 29.2 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

定价：49.80元 本／书／特／色 本书在选材与编排上，贴近当前普通高等院校“数据结构”课 程的现状和发展趋势，符合最新研究生考试大纲，内容难度适 度，突出实用性和应用性。全书共 8章，内容包括绪论，线性 表，栈和队列，串、数组和广义表，树和二叉树，图，查找和 排序。全书采用类C语言作为数据结构和算法的描述语言。 本书可作为普通高等院校计算机和信息技术相关专业“数据结 构”课程的教材，也可供从事计算机工程与应用工作的科技工 作者参考。 用书教师扫码下载 本书配套资源 教材服务热线：010-81055256 反馈／投稿／推荐信箱：315@ptpress.com.cn 人邮教育服务与资源下载社区：www.ryjiaoyu.com 高 等 学 校 计 算 机 专 业 核 心 课 名 师 精 品 系 列 教 材 数 据 结 构 双 色 版┃ 附 微 课 视 频 （C 语 言 版 第2 版 ） 书中所有算法提供动画演示微课视频，将复杂的算法具体化 C语言实现书中全部算法 提供多媒体课件，源代码，32、48、64多学时教学大纲，并配套习题与实验教材 DATA STRUCTURES IN C (2ND EDITION) 数据结构 （C语言版 第 2版） 双色版 |附微课视频 严蔚敏 李冬梅 吴伟民 编著 高等学校计算机专业核心课 名师精品 系列教材 “十二五”普通高等教育本科国家级规划教材 数 据 结 构 （C 语 言 版 ） （ 第2 版 ） 绪 论 线性表 栈和队列 串、数组和广义表 树和二叉树 图 查找 排序 本教材的结构框图 封面设计：董志桢 李冬梅 北京林业大学教授，博士生导师，现 任北京林业大学信息学院计算机软件 教研室主任。北京林业大学教学名师， 长期从事“数据结构”和“编译原理” 的一线教学。近年来，以第 1完成人 获得多项教学奖励，包括全国高校计 算机课件大赛一等奖、北京高校“优 质本科教材课件”、北京林业大学优 秀教学成果一等奖、北京林业大学优 秀教学论文一等奖、北京林业大学优 秀教案一等奖等。 严蔚敏 清华大学计算机系教授，长期从事数 据结构教学和教材建设，编著的《数 据结构》教材曾获“第二届普通高等 学校优秀教材全国特等奖”和“1996 年度国家科学技术进步奖三等奖”。 作者：严蔚敏 李冬梅 吴伟民 书号：978-7-115-57666-8 作者：汤小丹 王红玲 姜华 汤子瀛 书号：978-7-115-56115-2 作者：王庆先 顾小丰 王丽杰 书号：978-7-115-56642-3 作者：谭志虎 书号：978-7-115-55801-5 作者：谢钧 谢希仁 书号：978-7-115-57680-4 作者：陈志泊  书号：978-7-115-57710-8 FM57666（高校计算机专业核心课名师精品）数据结构（C语言版 第2版）（双色版 附微课视频）.indd 1-5 21/12/27 上午11:01

📄 Page 2

DATA STRUCTURES IN C (2ND EDITION) 人 民 邮 电 出 版 社 北 京 数据结构 （C语言版 第 2版） 双色版 |附微课视频 严蔚敏 李冬梅 吴伟民 编著 “十二五”普通高等教育本科国家级规划教材 高等学校计算机专业核心课 名师精品 系列教材 FM57666（高校计算机专业核心课名师精品）数据结构（C语言版 第2版）（双色版 附微课视频）.indd 6 21/12/27 上午11:01

📄 Page 3

内 容 提 要 本书在选材与编排上，贴近当前普通高等院校“数据结构”课程的现状和发展趋势，符合最新的 全国研究生考试计算机统考大纲，内容难度适度，突出实用性和应用性。全书共 8 章，内容包括绪论， 线性表，栈和队列，串、数组和广义表，树和二叉树，图，查找和排序。全书采用类 C 语言作为数据 结构和算法的描述语言。 本书可作为普通高等院校计算机和信息技术相关专业“数据结构”课程的教材，也可供从事计算 机工程与应用工作的科技工作者参考。  编 著 严蔚敏 李冬梅 吴伟民 责任编辑 刘 博 责任印制 王 郁 马振武  人民邮电出版社出版发行 北京市丰台区成寿寺路 11 号 邮编 100164 电子邮件 315@ptpress.com.cn 网址 https://www.ptpress.com.cn 三河市中晟雅豪印务有限公司印刷  开本：7871092 1/16 印张：17 2022 年 1 月第 2 版 字数：447 千字 2022 年 1 月河北第 1 次印刷 定价：49.80 元 读者服务热线：(010)81055256 印装质量热线：(010)81055316 反盗版热线：(010)81055315 广告经营许可证：京东市监广登字 20170147 号

📄 Page 4

《数据结构（C语言版）》第1版自出版以来，深受广大读者欢迎，被百余所学校选为 “数据结构”课程的教材，并被评为“‘十二五’普通高等教育本科国家级规划教材”。 为了更好地满足广大高等院校的学生对数据结构知识学习的需要，编者结合近几年的教学 改革实践、科研项目以及广大读者的反馈意见，并参考了大量文献资料，对教材进行了仔 细的修订。这次修订的主要内容如下。 （1）采用“案例驱动”的编写模式。书中结合实际应用，将各章按照“案例引入—数 据结构及其操作—案例分析与实现”的案例驱动思路来展开。每章使用一个有趣的“问题 案例”开头，由该案例逐步引入新的数据结构，然后给出该数据结构的存储表示及各种基 本操作的实现，之后进一步分析此案例，最终利用该数据结构来实现此案例。这样，学生 便能体会到从问题求解到程序设计的转换过程，深刻理解数据结构在程序设计中的作用。 （2）算法讲解更加细致。学生学习数据结构最大的困难是不能将用文字表述的算法思 想转换成程序。新教材中对每个算法思想进行详细阐述，将用文字描述的算法步骤与用类 C语言表述的算法描述一一对应。尤其是对于有循环结构的算法，本书在算法步骤的描述中 利用缩进的格式清晰地体现出了循环的执行过程。因为本书中的算法是由浅到深的，所以 学生通过学习这些算法，在不知不觉中便逐步提高了将自然语言描述的算法转化为高级语 言描述的程序的能力，真正提高了算法设计与算法实现的能力。 （3）优化教材内容。参考计算机专业最新的全国统考考研大纲，本书增加了大纲近两 年新增的考点内容，如分块查找、外部排序等，有助于考研学生复习备考使用。 本书共8章内容，其中第1章为绪论，综述数据、数据结构和抽象数据类型等基本概 念；第2章至第6章从抽象数据类型的角度，分别讨论线性表、栈、队列、串、数组、广义 表、树和二叉树以及图等基本类型的数据结构及其应用；第7章和第8章分别讨论查找和排 序，除了介绍各种实现方法之外，还着重从时间上进行定性或定量的分析和比较。本书突 出了抽象数据类型的概念，对每一种数据结构，都分别给出相应的抽象数据类型规范说明 和实现方法。 全书采用类C语言作为数据结构和算法的描述语言，在对数据的存储结构和算法进行描 述时，尽量考虑C语言的特色，同时兼顾数据结构和算法的可读性。学生在实际上机操作 时，可以很容易地将本书中的数据结构和算法转换成C或C++程序。 为方便教师教学和学生学习，本书还提供了PPT教学课件、习题答案、源代码、教学大 纲、实验指导，以及算法的Flash动态演示。读者可从人邮教育社区（www.ryjiaoyu.com）上 免费下载。 针对“数据结构”这门课中难以理解的算法，本书专门提供了微课视频进行演示和讲 序一第2版前言F O R E W O R D

📄 Page 5

解，读者可直接使用手机扫描“算法”旁边的二维码，观看视频。 在本书的编写过程中，北京林业大学信息学院的钟复之、陈忠富、金鑫、王岩琪、梅 莎、赵九晗、张盛福、闫楚依、纪芳、赵培雯等同学参加了有关程序的调试工作和文字校 对工作，李华颖、林怡、张琪、周纪文、苏翔、王玢玥、姚佳璐等同学参加了算法的Flash 动态演示制作工作，在此表示衷心的感谢！ 因编者水平有限，书中错误在所难免，恳请批评指正。 编　者 2021年10月 第2版前言 F O R E W O R D

📄 Page 6

序一目录C O N T E N T S 第 1章  绪论  1 1.1　数据结构的研究内容 1 1.2　数据结构的基本概念和术语 3 1.2.1　数据、数据元素、数据项和        数据对象  3 1.2.2　数据结构  4 1.2.3　数据类型和抽象数据类型  6 1.3　抽象数据类型的表示与实现 7 1.4　算法和算法分析 10 1.4.1　算法的定义及特性  10 1.4.2　评价算法优劣的基本标准  11 1.4.3　算法的时间复杂度  11 1.4.4　算法的空间复杂度  14 1.5　小结 15 习题 16 第 2章  线性表  18 2.1　线性表的定义和特点 18 2.2　案例引入 19 2.3　线性表的类型定义 21 2.4　线性表的顺序表示和实现 22 2.4.1　线性表的顺序表示   22 2.4.2　顺序表中基本操作的实现  24 2.5　线性表的链式表示和实现 28 2.5.1　单链表的定义和表示   28 2.5.2　单链表基本操作的实现   31 2.5.3　循环链表  37 2.5.4　双向链表  37 2.6　顺序表和链表的比较 39 2.6.1　空间性能的比较  39 2.6.2　时间性能的比较  39 2.7　线性表的应用 40 2.7.1　线性表的合并  40 2.7.2　有序表的合并   41 2.8　案例分析与实现 43 2.9　小结 48 习题 49 第 3章  栈和队列  52 3.1　栈和队列的定义和特点 52 3.1.1　栈的定义和特点  52 3.1.2　队列的定义和特点  53 3.2　案例引入 53 3.3　栈的表示和操作的实现 54 3.3.1　栈的类型定义  54 3.3.2　顺序栈的表示和实现  55 3.3.3　链栈的表示和实现  57 3.4　栈与递归 59 3.4.1　采用递归算法解决的问题  59 3.4.2　递归过程与递归工作栈  63 3.4.3　递归算法的效率分析  65 3.4.4　利用栈将递归转换为非递归        的方法  66 3.5　队列的表示和操作的实现 67 3.5.1　队列的类型定义  67 3.5.2　循环队列——队列的顺序        表示和实现  67 3.5.3　链队列——队列的链式表示        和实现  71 3.6　案例分析与实现 73 3.7　小结 80

📄 Page 7

C O N T E N T S 5.5.1　遍历二叉树  116 5.5.2　线索二叉树  122 5.6　树和森林 127 5.6.1　树的存储结构  127 5.6.2　森林与二叉树的转换  129 5.6.3　树和森林的遍历  130 5.7　哈夫曼树及其应用 131 5.7.1　哈夫曼树的基本概念  131 5.7.2　哈夫曼树的构造算法  132 5.7.3　哈夫曼编码  134 5.8　案例分析与实现 137 5.9　小结 139 习题 140 第 6章  图  143 6.1　图的定义和基本术语 143 6.1.1　图的定义   143 6.1.2　图的基本术语   144 6.2　案例引入 145 6.3　图的类型定义 146 6.4　图的存储结构 147 6.4.1　邻接矩阵  148 6.4.2　邻接表   150 6.4.3　十字链表  152 6.4.4　邻接多重表  153 6.5　图的遍历 155 6.5.1　深度优先搜索   155 6.5.2　广度优先搜索   157 6.6　图的应用 159 6.6.1　最小生成树   159 6.6.2　最短路径   164 6.6.3　拓扑排序   170 序一目录 习题 81 第 4章  串、数组和广义表  84 4.1　串的定义 84 4.2　案例引入 85 4.3　串的类型定义、存储结构及其 运算 86 4.3.1　串的抽象类型定义  86 4.3.2　串的存储结构   87 4.3.3　串的模式匹配算法  88 4.4　数组 94 4.4.1　数组的类型定义   94 4.4.2　数组的顺序存储   96 4.4.3　特殊矩阵的压缩存储   97 4.5　广义表 98 4.5.1　广义表的定义  98 4.5.2　广义表的存储结构   100 4.6　案例分析与实现 101 4.7　小结 103 习题 103 第 5章  树和二叉树  106 5.1　树和二叉树的定义 106 5.1.1　树的定义  106 5.1.2　树的基本术语  107 5.1.3　二叉树的定义  108 5.2　案例引入 108 5.3　树和二叉树的抽象数据类型定义 110 5.4　二叉树的性质和存储结构 113 5.4.1　二叉树的性质  113 5.4.2　二叉树的存储结构  114 5.5　遍历二叉树和线索二叉树 116

📄 Page 8

C O N T E N T S 序一目录 6.6.4　关键路径   173 6.7　案例分析与实现 178 6.8　小结 180 习题 181 第 7章  查找  185 7.1　查找的基本概念 185 7.2　线性表的查找 186 7.2.1　顺序查找  186 7.2.2　折半查找  187 7.2.3　分块查找  190 7.3　树表的查找 192 7.3.1　二叉排序树  192 7.3.2　平衡二叉树  199 7.3.3　B-树  203 7.3.4　B+ 树  211 7.4　散列表的查找 213 7.4.1　散列表的基本概念  213 7.4.2　散列函数的构造方法  214 7.4.3　处理冲突的方法  216 7.4.4　散列表的查找  218 7.5　小结 221 习题 223 第 8章  排序  227 8.1　基本概念和排序方法概述 227 8.1.1　排序的基本概念  227 8.1.2　内部排序方法的分类  228 8.1.3　待排序记录的存储方式  229 8.1.4　排序算法效率的评价指标 229 8.2　插入排序 229 8.2.1　直接插入排序  230 8.2.2　折半插入排序  231 8.2.3　希尔排序  232 8.3　交换排序 234 8.3.1　冒泡排序  234 8.3.2　快速排序  236 8.4　选择排序 239 8.4.1　简单选择排序  239 8.4.2　树形选择排序  241 8.4.3　堆排序  242 8.5　归并排序 247 8.6　基数排序 249 8.6.1　多关键字的排序   249 8.6.2　链式基数排序   249 8.7　外部排序 252 8.7.1　外部排序的基本方法  253 8.7.2　多路平衡归并的实现  254 8.7.3　置换-选择排序  255 8.7.4　最佳归并树  259 8.8　小结 260 习题 261 参考文献  264

📄 Page 9

(This page has no text content)

📄 Page 10

早期的计算机主要用于数值计算，而现在的计算机主要用于非数值计算，包括对字 符、表格和图像等具有一定结构的数据进行处理。这些数据内容存在着某种联系，只有分 清楚数据的内在联系，合理地组织数据，才能对它们进行有效的处理，设计出高效的算 法。如何合理地组织数据、高效地处理数据，这就是“数据结构”主要研究的问题。本章 简要介绍有关数据结构的基本概念和算法分析方法。 1.1　数据结构的研究内容 计算机用于数值计算时，一般要经过如下几个步骤：首先从具体问题中抽象出数学模型， 然后设计一个用于此数学模型的算法，最后编写程序，进行测试、调试，直到解决问题。在此 过程中寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关 系，然后用数学语言加以描述，即建立相应的数学方程。例如，用计算机进行全球天气预报 时，就需要求解一组球面坐标系下的二阶椭圆偏微分方程；预测人口增长情况的数学模型为常 微分方程。求解这些数学方程的算法属于计算数学研究的范畴，如高斯消元法、差分法、有限 元法等算法。数据结构主要研究非数值计算问题，非数值计算问题无法用数学方程建立数学模 型，下面通过三个实例加以说明。 【例1.1】　学生学籍管理系统。 高等院校教务处使用计算机对全校的学生学籍进行统一管理。学生的基本信息，包括学生 的学号、姓名、性别、籍贯、专业等，如表1.1所示。每个学生的基本情况按照不同的顺序号， 依次存放在“学生基本信息表”中，教务处可以根据需要在这张表中进行查找。每个学生的基 本信息记录按顺序号排列，形成了学生基本信息记录的线性序列，呈线性关系。 表 1.1　学生基本信息表 学号 姓名 性别 籍贯 专业 060214201 杨阳 男 安徽 计算机科学与技术 060214202 薛林 男 福建 计算机科学与技术 060214215 王诗萌 女 吉林 计算机科学与技术 060214216 冯子晗 女 山东 计算机科学与技术 绪论 第1章

📄 Page 11

2 数 据 结 构 （C 语 言 版 ） （ 第2 版 ） — — 双 色 版 诸如此类的线性表结构还有图书馆的书目管理系统、库存管理系统等。在这类问题中，计算机 处理的对象是各种表，元素之间存在简单一对一的线性关系，因此这类问题的数学模型就是各种线 性表，施加于对象上的操作有查找、插入和删除等。这类数学模型称为“线性”的数据结构。 【例1.2】　人机对弈问题。 计算机之所以能和人对弈是因为已经将对弈的策略在计算机中存储好。由于对弈的过程是 在一定规则下随机进行的，所以，为使计算机能灵活对弈，就必须把对弈过程中所有可能发生 的情况及相应的对策都加以考虑。以简单的井字棋为例，初始状态是一个空的棋盘格局。对弈 开始后，每下一步棋，则构成一个新的棋盘格局，且相对于上一个棋盘格局的可能选择可以有 多种形式，因而整个对弈过程就如同图1.1所示的“一棵倒长的树”。在这棵“树”中，从初始 状态（根）到某一最终格局（叶子）的一条路径，就是一次具体的对弈过程。 人机对弈问题的数学模型就是用树结构表示棋盘和棋子等，算法是博弈的规则和策略。诸 如此类的树结构还有计算机的文件系统、一个单位的组织机构等。在这类问题中，计算机处理 的对象是树结构，元素之间存在一对多的层次关系，施加于对象上的操作有查找、插入和删除 等。这类数学模型称为“树”的数据结构。 【例1.3】　最短路径问题。 从城市A到城市B有多条线路，但每条线路所需的交通费不同，那么，如何选择一条线路， 使得从城市A到城市B所需的交通费最少呢？解决的方法是，把这类问题抽象为图的最短路径问 题。如图1.2所示，图中的顶点代表城市，有向边代表两个城市之间的通路，边上的权值代表两 个城市之间的交通费。求解A到B所需的最少交通费，就是要在有向图中A点（源点）到达B点 （终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。  　　　　　　　　 图1.1　井字棋的对弈树　　　　　　　　　　　 　　　                         图1.2　最短路径问题

📄 Page 12

3 第 1 章  绪 论 最短路径问题的数学模型就是图结构，算法是求解两点之间的最短路径。诸如此类的图结 构还有网络工程图和网络通信图等。在这类问题中，元素之间存在多对多的网状关系，施加于 对象上的操作依然有查找、插入和删除等。这类数学模型称为“图”的数据结构。 从上面3个实例可以看出，非数值计算问题的数学模型不再是数学方程，而是诸如线性表、 树和图的数据结构。因此，简单地说，数据结构是一门研究非数值计算程序设计中的操作对 象，以及这些对象之间的关系和操作的学科。 20世纪60年代初期，“数据结构”有关的内容散见于操作系统、编译原理等课程中。1968 年，“数据结构”作为一门独立的课程被列入美国一些大学计算机科学系的教学计划。同年， 著名计算机科学家唐纳德·克努特（D.E.Knuth）教授发表了《计算机程序设计艺术》第一卷 《基本算法》。这是第一本较系统地阐述“数据结构”基本内容的著作。之后，随着大型程序 和大规模文件系统的出现，结构化程序设计成为程序设计方法学的主要研究方向，人们普遍认 为程序设计的实质就是为所处理的问题选择一种好的数据结构，并在此结构基础上施加一种好 的算法，著名科学家沃斯（Wirth）教授的《算法+数据结构=程序》正是这种观点的集中体现。 目前，数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及 计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研 究有着密切的关系，无论是编译程序还是操作系统都涉及数据元素在存储器中的分配问题。在 研究信息检索时也必须考虑如何组织数据，以使查找和存取数据元素更为方便。因此，可以认 为，数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程。 有关“数据结构”的研究仍不断发展，一方面，面向各专门领域中特殊问题的数据结构正 在研究和发展；另一方面，从抽象数据类型的观点来讨论数据结构，已成为一种新的趋势，越 来越被人们所重视。 1.2　数据结构的基本概念和术语 下列概念和术语将在后文中多次出现，本节先对这些概念和术语给出确定的含义。 1.2.1　数据、数据元素、数据项和数据对象 数据（Data）是客观事物的符号表示，是所有能输入计算机中并被计算机程序处理的符号 的总称。如数学计算中用到的整数和实数，文本编辑中用到的字符串，多媒体程序处理的图 形、图像、声音及动画等通过特殊编码定义后的数据。 数据元素（Data Element）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处 理。在有些情况下，数据元素也称为元素、记录等。数据元素用于完整地描述一个对象，如前 一节示例中的一名学生记录，树中棋盘的一个格局（状态），以及图中的一个顶点等。 数据项（Data Item）是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学 生基本信息表中的学号、姓名、性别等都是数据项。 数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。例如：整数 数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’,‘a’,‘b’,…,‘z’}， 学生基本信息表也可以是一个数据对象。由此可以看出，不论数据元素集合是无限集（如整数 集），或是有限集（如字母字符集），还是由多个数据项组成的复合数据元素（如学生表）的 集合，只要集合内元素的性质均相同，都可称之为一个数据对象。

📄 Page 13

4 数 据 结 构 （C 语 言 版 ） （ 第2 版 ） — — 双 色 版 1.2.2　数据结构 数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。换句 话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 数据结构包括逻辑结构和存储结构两个层次。 1．逻辑结构 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因 此，数据的逻辑结构可以看作从具体问题中抽象出来的数学模型。 数据的逻辑结构有两个要素：一是数据元素；二是关系。数据元素的含义如前所述，关系 是指数据元素间的逻辑关系。根据数据元素之间关系的不同特性，数据的逻辑结构通常有4类基 本逻辑结构，如图 1.3所示。它们的复杂程度依次递进。 图1.3　4类基本逻辑结构 下面4种结构中所举的示例是以某班级学生作为数据对象（数据元素是学生的学籍档案记 录），来分别考察数据元素之间的关系。 （1）集合结构 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否 为班级成员，只需将班级看作一个集合结构。 （2）线性结构 数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序 进行排列，将组成一个线性结构。 （3）树结构 数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位 组长管理多名组员，从而构成树结构。 （4）图结构或网状结构 数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以 是朋友，从而构成图结构或网状结构。 其中集合结构、树结构和图结构或网状结构都属于非线性结构。 线性结构包括线性表（典型的线性结构，如例1.1中的学生基本信息表）、栈和队列（具有 特殊限制的线性表，数据操作只能在表的一端或两端进行）、字符串（也是特殊的线性表，其 特殊性表现在它的数据元素仅由一个字符组成）、数组（是线性表的推广，它的数据元素是一

📄 Page 14

5 第 1 章  绪 论 个线性表）、广义表（也是线性表的推广，它的数据元素是一个线性表，但不同构，即或者是 单元素，或者是线性表）。非线性结构包括树结构[分为树（具有多个分支的层次结构）和二叉 树（具有两个分支的层次结构）]、图结构[分为有向图（一种图结构，边是顶点的有序对）和无 向图（另一种图结构，边是顶点的无序对）]和集合结构。这几种逻辑结构可以用一个层次图描 述，如图1.4所示。 图1.4　逻辑结构层次图 2．存储结构 数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。把数据对象存储 到计算机时，通常要求既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系，数据 元素在计算机内用一个节点来表示。数据元素在计算机中有两种基本的存储结构，分别是顺序 存储结构和链式存储结构。 （1）顺序存储结构 顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系的，通常 借助程序设计语言的数组类型来描述。 对于前面的“学生基本信息表”，假定每个节点（学生记录）占用50个存储单元，数据从0 号单元开始由低地址向高地址方向存储，对应的顺序存储结构如表1.2所示。 表 1.2　顺序存储结构 地址 学号 姓名 性别 籍贯 专业 0 060214201 杨阳 男 安徽 计算机科学与技术 50 060214202 薛林 男 福建 计算机科学与技术 100 060214215 王诗萌 女 吉林 计算机科学与技术 150 060214216 冯子晗 女 山东 计算机科学与技术 （2）链式存储结构 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无须 占用一整块存储空间。但为了表示节点之间的关系，需要给每个节点附加指针字段，用于存放 后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。 假定给前面的“学生基本信息表”中的每个节点附加一个“下一个节点地址”，即后继指针 字段，用于存放后继节点的首地址，则可得到如表 1.3 所示的链式存储结构。从表中可以看出， 每个节点占用两个连续的存储单元，一个存放节点的信息，另一个存放后继节点的首地址。

📄 Page 15

6 数 据 结 构 （C 语 言 版 ） （ 第2 版 ） — — 双 色 版 表 1.3　链式存储结构 地址 学号 姓名 性别 籍贯 专业 后继节点的首地址 0 060214201 杨阳 男 安徽 计算机科学与技术 100 50 060214216 冯子晗 女 山东 计算机科学与技术 ^ 100 060214202 薛林 男 福建 计算机科学与技术 150 150 060214215 王诗萌 女 吉林 计算机科学与技术 50 为了更清楚地反映链式存储结构，可采用更直观的图来表示，如“学生基本信息表”的链 式存储结构可用如图1.5所示的方式表示。 图1.5　链式存储结构示意 1.2.3　数据类型和抽象数据类型 1．数据类型 数据类型（Data Type）是高级程序设计语言中的一个基本概念，前面提到过顺序存储结构 可以借助程序设计语言的数组类型来描述，链式存储结构可以借助指针类型来描述，所以数据 类型和数据结构的概念密切相关。 一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了 数据的取值范围、存储方式以及允许进行的运算，数据类型是一个值的集合和定义在这个值集 上的一组操作的总称。例如，C语言中的整型变量，其值集为某个区间上的整数（区间大小依赖 于不同的机器），定义在其上的操作为加、减、乘、除和取模等算术运算；而实型变量也有自 己的取值范围和相应运算，比如取模运算是不能用于实型变量的。程序设计语言允许用户直接 使用的数据类型由具体语言决定，数据类型反映了程序设计语言的数据描述和处理能力。C语 言除了提供整型、实型、字符型等基本类型数据外，还允许用户自定义各种类型数据，例如数 组、结构体和指针等。 2．抽象数据类型 抽象就是抽取出实际问题的本质。在计算机中使用二进制数来表示数据，在汇编语言中则 可给出各种数据的十进制表示，它们是二进制数据的抽象，使用者在编程时可以直接使用，不 必考虑实现细节。高级语言则给出更高一级的数据抽象，出现了数据类型，如整型、实型、字 符型等，可以进一步利用这些类型构造出线性表、栈、队列、树、图等复杂的抽象数据类型。 抽象数据类型（Abstract Data Type，ADT）一般指由用户定义的、表示应用问题的数学模 型，以及定义在这个模型上的一组操作的总称，具体包括3个部分：数据对象、数据对象上关系 的集合以及对数据对象的基本操作的集合。

📄 Page 16

7 第 1 章  绪 论 抽象数据类型的定义格式如下： ADT 抽象数据类型名{ 　 数据对象 ：〈数据对象的定义〉 　 数据关系 ：〈数据关系的定义〉 　 基本操作 ：〈基本操作的定义〉 }ADT 抽象数据类型名 其中，数据对象和数据关系的定义采用数学符号和自然语言描述，基本操作的定义格式为： 基本操作名（参数表） 　 初始条件 ：〈初始条件描述〉 　 操作结果 ：〈操作结果描述〉 基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以“&”打头，除可提供 输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条 件，若初始条件为空，则省略。“操作结果”说明了操作正常完成之后，数据结构的变化状况 和应返回的结果。 1.3　抽象数据类型的表示与实现 运用抽象数据类型描述数据结构，有助于在设计软件系统时，不必首先考虑其中包含的数 据对象，以及操作在不同处理器中的表示和实现细节，而是在构成软件系统的每个相对独立的 模块上定义一组数据和相应的操作，把这些数据的表示和操作细节留在模块内部解决，在更高 的层次上进行软件的分析和设计，从而提高软件的整体性能和利用率。 抽象数据类型的概念与面向对象方法的思想是一致的。抽象数据类型独立于具体实现，将 数据和操作封装在一起，使得用户程序只能通过抽象数据类型定义的某些操作来访问其中的数 据，从而实现了信息隐藏。在C++中，我们可以用类的声明表示抽象数据类型，用类的实现来 实现抽象数据类型。因此，C++中实现的类相当于数据的存储结构及其在存储结构上实现的对 数据的操作。 抽象数据类型和类的概念实际上反映了程序或软件设计的两层抽象：抽象数据类型相当于 在概念层（或称为抽象层）上描述问题，而类相当于在实现层上描述问题。此外，C++中的类 只是一个由用户定义的普通类型，可用它来定义变量（称为对象或类的实例）。因此，在C++ 中，最终是通过操作对象来解决实际问题的，所以我们可将该层次看作应用层。例如，main程 序就可看做是用户的应用程序。 由此可以看出，最终表示和实现抽象数据类型，最好用面向对象的方法，比如用C++语言 的类描述比较方便、有效，但本课程大多在大学低年级开设，用C语言的描述方法更符合学生的 实际情况。另外，由于实际问题千变万化，数据模型和算法也形形色色，因此抽象数据类型的 设计和实现，就不可能像基本数据类型那样规范和一劳永逸。本书所讨论的数据结构及其算法 主要是面向读者的，故采用介于伪码和C语言之间的类C语言作为描述工具。这使得数据结构与 算法的描述与讨论简明清晰，不拘泥于C语言的细节，又容易转换成C或C++程序。 本书采用的类C语言精选了C语言的一个核心子集，同时做了若干扩充修改，增强了语言的 描述功能，以下对其做简要说明。 （1）预定义常量及类型： //函数结果状态代码 #define OK 1 #define ERROR 0

📄 Page 17

8 数 据 结 构 （C 语 言 版 ） （ 第2 版 ） — — 双 色 版 #define OVERFLOW -2 //Status是函数返回值类型，其值是函数结果状态代码。 typedef int Status; （2）数据结构的表示（存储结构）用类型定义（typedef）描述；数据元素类型约定为 ElemType，由用户在使用该数据类型时自行定义。 （3）基本操作的算法都用如下格式的函数来描述： 函数类型 函数名（函数参数表） { 　//算法说明 　语句序列 }//函数名 当函数返回值为函数结果状态代码时，函数定义为Status类型。为了便于描述算法，除了值 调用方式外，增加了C++语言引用调用的参数传递方式。在形参表中，以“&”打头的参数即为 引用参数。传递引用给函数与传递指针的效果是一样的，形参变化实参也发生变化，但引用使 用起来比指针更加方便、高效。 （4）内存的动态分配与释放。 使用new和delete动态分配和释放内存空间： 分配空间　指针变量=new数据类型; 释放空间　delete指针变量; （5）赋值语句： 简单赋值 变量名 = 表达式; 串联赋值 变量名1 = 变量名2 = ... = 变量名n = 表达式; 成组赋值 (变量名1, ..., 变量名n) = (表达式1, ..., 表达式n); 结构赋值　结构名1 = 结构名2; 　　　　 结构名 = (值1, 值2, ..., 值n); 条件赋值 变量名 = 条件表达式 ? 表达式T：表达式F; 交换赋值 变量名1 <-->变量名2; （6）选择语句： 条件语句1 if (表达式) 语句; 条件语句2 if (表达式) 语句; 　　　　 else 语句; 开关语句 switch (表达式) 　　　　　　 {　 　　　　　　　 case 值1: 语句序列1 ;break; 　　　　　　　 case 值2: 语句序列2 ;break; 　　　　　　　 … 　　　　　　　 case 值n: 语句序列n;break; 　　　　　　　 default: 语句序列n+1; 　　　　　　 }　 （7）循环语句： for语句　　　　 for (表达式1; 条件; 表达式2) 语句; while语句　　　while (条件) 语句; do-while语句　 do {

📄 Page 18

9 第 1 章  绪 论 　　　　　　　　　　语句序列; 　　　　　　　　　　} while (条件); （8）结束语句： 函数结束语句　　return 表达式; 　　　　　　　 return; 　　　　　　　　case或循环结束语句 break; 　　　　　　　　异常结束语句 exit (异常代码); （9）输入输出语句使用C++流式输入输出的形式： 输入语句 　　cin>>变量1>>…>>变量n; 输出语句 　　cout<<表达式1<<…<<表达式n; （10）基本函数： 求最大值　　Max (表达式1,…,表达式n) 求最小值　　Min (表达式1,…,表达式n) 下面以复数为例，给出一个完整的抽象数据类型的定义、表示和实现。 （1）定义部分： ADT Complex { 　 数据对象 ：D={e1,e2|e1,e2∈R,R是实数集} 　 数据关系 ：S={<e1,e2>|e1是复数的实部，e2 是复数的虚部} 　 基本操作 ： 　　 Creat(&C,x,y) 　　　 操作结果 ：构造复数C，其实部和虚部分别被赋予参数x和y的值。 　　 GetReal(C) 　　　 初始条件 ：复数C已存在。 　　　 操作结果 ：返回复数C的实部值。 　　 GetImag(C) 　　　 初始条件 ：复数C已存在。 　　　 操作结果 ：返回复数C的虚部值。 　　 Add(C1,C2) 　　　 初始条件 ：C1，C2是复数。 　　　 操作结果 ：返回两个复数C1和C2的和。 　　 Sub(C1,C2) 　　　 初始条件 ：C1，C2是复数。 　　　 操作结果 ：返回两个复数C1和C2的差。 } ADT Complex 在后文中，每定义一个新的数据结构，都先用这种定义方式给出其抽象数据类型的定义， 对于数据结构的表示方法，则根据不同的存储结构相应给出，同时用类C语言给出主要操作的实 现方法。下面为了让读者对抽象数据类型有一个完整、正确的理解，给出复数的存储表示和相 应操作的具体实现过程。 （2）表示部分： typedef struct //复数类型 {　 　 float Realpart;　 //实部 　 float Imagepart; //虚部 }Complex; （3）实现部分： void Create( &Complex C, float x, float y)

📄 Page 19

10 数 据 结 构 （C 语 言 版 ） （ 第2 版 ） — — 双 色 版 {//构造一个复数 　C.Realpart=x; 　C.Imagepart=y; } float GetReal(Complex C) {//取复数C=x+yi的实部 　return C.Realpart; } float GetImag(Complex C) {//取复数C=x+yi的虚部 　return C.Imagepart; } Complex Add(Complex C1, Complex C2) { //求两个复数C1和C2的和sum 　Complex sum; 　sum.Realpart=C1.Realpart+C2.Realpart; 　sum.Imagepart=C1.Imagepart+C2.Imagepart; 　return sum; } Complex Sub(Complex C1, Complex C2) { //求两个复数C1和C2的差difference 　Complex difference; 　difference.Realpart=C1.Realpart-C2.Realpart; 　difference.Imagepart=C1.Imagepart-C2.Imagepart; 　return difference; } 这样定义之后，就可以在主程序中通过调用Create函数构造一个复数，调用Add或Sub函数 实现复数的加法或减法运算，从而使用户可以像使用整数类型那样使用复数类型了。通过上述 实例，读者可以对抽象数据类型的概念有更加深刻的理解。 1.4　算法和算法分析 数据结构与算法之间存在着本质联系。在涉及某一类型数据结构时，总要涉及其上施加 的运算。而只有通过对所定义运算的研究，才能清楚理解数据结构的定义和作用。在涉及运算 时，总要联系到该算法处理的对象和结果涉及的数据。“数据结构”中会有大量的算法问题， 因为算法联系着数据在计算过程中的组织方式，为了描述如何实现某种操作，常常需要设计算 法，因而算法是研究数据结构的重要途径。 1.4.1　算法的定义及特性 算法（Algorithm）是为了解决某类问题而规定的一个有限长的操作序列。 一个算法必须满足以下5个重要特性。 （1）有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内 完成。 （2）确定性。对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义 性，算法的执行者或阅读者都能明确其含义及如何执行。 （3）可行性。算法中的所有操作都可以通过将已经实现的基本操作运算执行有限次来实现。

📄 Page 20

11 第 1 章  绪 论 （4）输入。一个算法有0个或多个输入。当用函数描述算法时，输入往往是通过形参表示 的，在它们被调用时，从主调函数获得输入值。 （5）输出。一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出 的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。 1.4.2　评价算法优劣的基本标准 一个算法的优劣应该从以下几方面来评价。 （1）正确性。在合理的数据输入下，好的算法能够在有限的运行时间内得到正确的结果。 （2）可读性。一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。 可读性强的算法有助于人们对算法的理解，而难懂的算法容易隐藏错误，且难于调试和修改。 （3）健壮性。当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而 不会产生一些莫名其妙的输出结果。 （4）高效性。高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率 高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度 量。时间复杂度和空间复杂度是衡量算法的两个主要指标。 1.4.3　算法的时间复杂度 算法效率分析的目的是看算法实际是否可行，并在同一问题存在多个算法时，可进行时间 和空间性能上的比较，以便从中挑选出较优算法。 衡量算法效率的方法主要有两类：事后统计法和事前分析估算法。事后统计法需要先将算 法实现，然后测算其时间和空间开销。这种方法的缺陷很显然，一是必须把算法转换成可执行 的程序，二是时空开销的测算结果依赖于计算机的软硬件等环境因素，这容易掩盖算法本身的 优劣。所以我们通常采用事前分析估算法，通过计算算法的渐近复杂度来衡量算法的效率。 1．问题规模和语句频度 不考虑计算机的软硬件等环境因素，影响算法时间代价的最主要因素是问题规模。问题 规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示。问题规模n 对不同的问题含义不同，例如，在排序运算中n为参加排序的记录数，在矩阵运算中n为矩阵 的阶数，在多项式运算中n为多项式的项数，在集合运算中n为集合中元素的个数，在树的有 关运算中n为树的节点个数，在图的有关运算中n为图的顶点数或边数。显然，n越大算法的 执行时间越长。 一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条 语句的重复执行次数和执行一次所需时间的乘积。 一条语句的重复执行次数称作语句频度（Frequency Count）。 由于语句的执行要由源程序经编译程序翻译成目标代码，目标代码经装配再执行，因此语 句执行一次实际所需的具体时间是与机器的软、硬件环境（如机器速度、编译程序质量等）密 切相关的。所以，所谓的算法分析并非精确统计算法实际执行所需时间，而是针对算法中语句 的执行次数做出估计，从中得到算法执行时间的信息。 设每条语句执行一次所需的时间均是单位时间，则一个算法的执行时间可用该算法中所有 语句频度之和来度量。