数据结构与算法（C++语言版）.pdf

普通高等教育“十一五”国家级规划教材 华南理工大学精品课程教材 高等学校计算机基础及应用教材 数据结构与算法（C+语言版）肖南峰 赵 洁 等编 Publishing House of Electronics Industry 北京BEIJING II 内 容 简 介 本书为普通高等教育“十一五”国家级规划教材。全书共分 15 章，主要内容包括：绪论、线性表、栈和队列、串、多维数组和广义表、树和二叉树、图、查找、内部排序、文件组织和外排序、贪婪算法、分而治之算法、动态规划、回溯、分枝定界法。在前 10章中，对相应的数据结构的 ADT 描述、存储结构、基本操作、综合算法做了全面深入的阐述，每章的最后都对该章的基本内容、学习要点、具体要求、重点和难点进行了归纳和总结。在第 1115 章中，列举了几个应用多种数据结构进行综合性算法设计的典型例子。另外，作者在参考了近年来许多的国内外教材之后，选编了大量精心设计的习题。本书每章的学习内容翔实，算法和例题典型，而且给出了对应的 VC+6.0 源程序。本书免费提供电子课件。本书不仅可作为计算机学科各专业学生的教材，也适合作为广大工程技术人员和自学考试人员的参考书。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据 数据结构与算法：C+语言版/肖南峰，赵洁等编.北京：电子工业出版社，2009.5 高等学校计算机基础及应用教材 ISBN 978-7-121-08301-3.数 .肖赵 .数据结构高等学校教材算法分析高等学校教材C 语言程序设计高等学校教材 .TP311.12 TP312 中国版本图书馆 CIP 数据核字（2009）第 021494 号 责任编辑：冉 哲 印 刷：装 订：出版发行：电子工业出版社 北京市海淀区万寿路 173 信箱 邮编：100036 开 本：7871092 1/16 印张：19.75 字数：488 千字 印 次：2009 年 5 月第 1 次印刷 印 数：2 0 0 9 册 定价：2 9.8 0 元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系。联系及邮购电话：（010）88254888。质量投诉请发邮件至 ，盗版侵权举报请发邮件至 。服务热线：（010）88258888。III 前 言“数据结构”是计算机学科各个专业的一门重要的专业基础课程。本课程主要讲授数据的逻辑结构、存储结构、基本运算、运算实现、算法设计、算法分析、算法评价等方面的内容，使学生对线性表、栈、队列、串、数组、树及二叉树、无向图和有向图、静态及动态查找表、文件等各种数据结构有深刻的理解，对各种常见的排序方法与算法有深入的了解。在此基础上，还要求学生系统地掌握在不同的存储结构上利用上述数据结构进行综合性算法设计的方法和技巧。因此，它是一门理论性和实践性都很强的课程。根据作者多年的教学实践发现，学生对于数据结构的应用，特别是在做算法设计习题和编程上机实习这两个环节上都不同程度地存在着一定的困难。为了帮助学生更好地掌握该课程的知识，提高算法设计和动手编程的能力，急需为计算机学科各专业开设的“数据结构”课程编写一本基础扎实、知识面广、适应性强的教材。为此，在华南理工大学精品课程建设基金的资助下，我们编写了这本数据结构与算法（C+语言版）教材，主要目的就是加强基础、拓宽知识面、增强适应性，以便使学生能够更深入地理解教材内容，开拓思想，培养并掌握良好的算法设计与程序实现的技能，以及解决实际问题的能力。本书为普通高等教育“十一五”国家级规划教材。本书共分 15 章，主要内容包括：绪论、线性表、栈和队列、串、多维数组和广义表、树和二叉树、图、查找、内部排序、文件组织和外排序、贪婪算法、分而治之算法、动态规划、回溯、分枝定界法。在前 10 章中，对相应的数据结构的 ADT 描述、存储结构、基本操作、综合算法做了全面深入的阐述，每章的最后都对该章的基本内容、学习要点、具体要求、重点难点进行归纳和总结。在第 1115 章中，列举了几个应用多种数据结构进行综合性算法设计的典型例子。另外，作者在参考了近年来许多的国内外教材之后，选编了大量精心设计的习题。本书每章的学习内容翔实，算法和例题典型，而且给出了对应的 VC+6.0 源程序。本书提供免费电子课件。本书不仅可作为计算机学科各专业学生的教材，也适合作为广大工程技术人员和自学考试人员的参考书。肖南峰教授、黄敏讲师和张芩讲师编写了第 110 章并选编了全部习题，赵洁讲师编写了第 1115 章及所有的 Visual C+6.0 源程序，吕建明讲师校对了部分章节的习题。在本教材的编写过程中，华南理工大学“数据结构”精品课程课题组和“智能计算机科研团队”的多位教师提出了许多的宝贵意见，我们在此向他们表示衷心的感谢。另外，还要感谢华南理工大学精品课程建设基金的支持。由于作者水平有限，教材中难免会存在错误，因此热忱地欢迎广大读者提出批评和意见。编 者 2009 年 3 月 于华南理工大学 IV 作 者 简 介 肖南峰博士，男，1962 年 11 月生，华南理工大学计算机科学与工程学院教授，博士生导师。1982 年 7 月毕业于华中工学院（现为华中科技大学）自动控制与计算机工程系，获工学学士学位；1989 年 1 月毕业于东北工学院（现为东北大学），获工学硕士学位；2001 年 6 月毕业于日本横浜国立大学，获工学博士学位。2001 年 9 月至 2002 年 9 月在澳大利亚 Deakin 大学从事科学研究。他作为主持人先后完成了 2项国家自然科学基金项目、2 项广东省自然科学基金重点项目，1 项教育部留学回国人员科研启动基金项目，以及由广东省教育厅和华南理工大学等资助的 20 多项教学与科研课题，在国内外发表学术论文 120 多篇，其中被三大索引收录近 50 篇，出版专著和教材 5 部，申请或获得发明及实用新型专利 5 项，软件版权 10 项。他一直在教学一线从事“数据结构”等课程的教学，已先后为近 20 届计算机专业、计算机辅修专业、电类联合班、继续教育学院和网络学院的本科生讲授过“数据结构”、“高级程序设计语言”等课程，积累了丰富的教学经验。V 目 录 第 1 章 绪论1 1.1 什么是数据结构1 1.1.1 基本概念1 1.1.2 数据结构的内涵1 1.1.3 数据类型和抽象数据类型 3 1.2 算法和算法分析4 1.2.1 算法的描述 4 1.2.2 算法设计的要求4 1.2.3 算法分析4 本章总结7 习题 18 第 2 章 线性表12 2.1 线性表的类型定义12 2.1.1 基本概念12 2.1.2 抽象数据类型描述12 2.1.3 线性表抽象类13 2.1.4 异常类 NoMem 和 OutOfBounds14 2.2 线性表的顺序存储结构15 2.2.1 基本概念15 2.2.2 基本操作16 2.3 线性表的链式存储结构21 2.3.1 线性链表21 2.3.2 循环链表29 2.3.3 双向链表29 2.3.4 顺序表和链表的比较32 2.4 线性表的应用多项式相加与 Josephus 问题 32 2.4.1 多项式表示 32 2.4.2 多项式相加 35 本章总结37 习题 238 第 3 章 栈与队列43 3.1 栈43 3.1.1 栈的定义43 3.1.2 栈的抽象类 44 3.1.3 栈的顺序存储结构44 3.1.4 栈的链式存储结构46 VI 3.2 栈的应用举例47 3.3 栈与递归51 3.4 队列51 3.4.1 队列的定义 51 3.4.2 队列的顺序存储结构53 3.4.3 队列的链式存储结构58 本章总结60 习题 361 第 4 章 串64 4.1 串的逻辑结构64 4.1.1 基本概念64 4.1.2 串的大小比较66 4.2 串的存储结构66 4.3 串函数与串的类定义67 4.3.1 常用的 C+串函数67 4.3.2 串的类定义 68 4.4 串模式匹配 70 4.4.1 简单串模式匹配算法71 4.4.2 无回溯的匹配算法71 4.5 串的应用文本编辑73 本章总结74 习题 474 第 5 章 多维数组与广义表76 5.1 数组76 5.1.1 数组的定义 76 5.1.2 C+的数组77 5.1.3 数组的存储结构与寻址问题 77 5.2 类 Array1D80 5.3 矩阵的压缩存储82 5.3.1 特殊矩阵83 5.3.2 稀疏矩阵85 5.4 十字链表89 5.4.1 存储方式89 5.4.2 十字链表对象90 5.4.3 基本操作的实现91 5.4.4 十字链表相加法*93 5.5 广义表95 5.5.1 广义表的定义95 5.5.2 广义表的抽象数据类型定义 96 5.5.3 广义表的存储结构97 VII 本章总结100 习题 5101 第 6 章 树与二叉树103 6.1 树的相关概念103 6.1.1 树的递归定义和逻辑表示法 103 6.1.2 树的基本术语103 6.1.3 树的抽象类型定义104 6.2 树的存储结构与遍历105 6.2.1 树的存储结构105 6.2.2 树与森林的遍历108 6.3 二叉树109 6.3.1 二叉树的定义109 6.3.2 二叉树的性质 111 6.4 二叉树的存储结构 112 6.4.1 顺序存储结构 112 6.4.2 链式存储结构 113 6.5 二叉树对象模型 114 6.5.1 二叉树结点对象 114 6.5.2 二叉树对象 115 6.6 二叉树的遍历与线索化 118 6.6.1 二叉树的遍历 118 6.6.2 二叉树的线索化123 6.6.3 二叉树与森林的转换126 6.7 哈夫曼树及其应用128 6.7.1 哈夫曼树128 6.7.2 哈夫曼编码 129 本章总结133 习题 6134 第 7 章 图137 7.1 图的定义和术语137 7.2 图的对象抽象模型141 7.2.1 图结点对象抽象模型141 7.2.2 图的边对象抽象模型141 7.2.3 图对象抽象模型142 7.3 图的存储结构143 7.3.1 邻接矩阵143 7.3.2 邻接表148 7.3.3 十字链表（有向图）153 7.3.4 邻接多重表（无向图）155 7.4 图的遍历156 VIII 7.4.1 深度优先遍历156 7.4.2 广度优先遍历161 7.5 图的连通性问题163 7.5.1 图的连通分量163 7.5.2 生成树及生成森林164 7.6 有向无环图及其应用167 7.6.1 有向无环图 167 7.6.2 AOV 网与拓扑排序168 7.6.3 AOE 网与关键路径171 本章总结176 习题 7176 第 8 章 查找179 8.1 查找表的相关概念179 8.1.1 基本概念179 8.1.2 类型说明179 8.2 静态查找表 180 8.2.1 概述180 8.2.2 顺序表的查找180 8.2.3 有序表的查找182 8.2.4 索引顺序表的查找183 8.3 动态查找表 186 8.3.1 概述186 8.3.2 二叉排序树 186 8.3.3 平衡二叉树 191 8.3.4 B树和 B+树193 8.4 哈希表198 8.4.1 哈希表的定义198 8.4.2 哈希函数的构造198 8.4.3 处理冲突的方法200 8.4.4 哈希表的查找及其分析204 本章总结205 习题 8206 第 9 章 内部排序208 9.1 排序的基本概念208 9.2 插入排序209 9.2.1 直接插入排序209 9.2.2 折半插入排序 211 9.2.3 2 路插入排序 211 9.2.4 表插入排序 212 9.2.5 希尔排序214 IX 9.3 交换排序215 9.3.1 冒泡排序215 9.3.2 快速排序216 9.4 选择排序218 9.4.1 简单选择排序218 9.4.2 堆排序219 9.5 归并排序224 9.6 基数