《数据结构实用教程》系统地介绍了各种常用的数据结构和排序、查找的各种算法;简述了各种数据结构内在的逻辑关系、存储表示、运算操作以及许多相关的操作算法;对用类C语言描述的各种算法进行了详细的注释和性能分析。书中列举了大量的例题,并对其解题思路、方法进行了分析。《数据结构实用教程》既注重原理又重视实践,配有大量的习题和一些思考题,并配套有习题参考答案以及课程配套实验(包括题目分析及参考程序);概念讲解清楚,逻辑推理严谨,通俗易懂,既便于教学,又适合自学。
《数据结构实用教程》可作为计算机类专业及信息类专业的教材,也可作为高等院校各类相关专业本科生、专科生及成人教育学习“教据结构”的教材,还可作为广大从事计算机软件与应用的工作人员、大专院校及社会上数据结构学习者的参考用书。
当今世界已进入了信息时代,计算机的应用也从传统的数值计算发展到非数值计算,并逐步深入到了各个领域。现代社会各行各业大量地使用计算机进行数据处理,电子通信、自动控制、信息处理、人工智能、管理和情报检索等各专业与计算机科学的联系日益密切,这就需要越来越多的人掌握计算机应用知识,以推动社会信息化进程。作为计算机软件设计技术的理论基础,“数据结构”不仅仅是计算机学科的核心课程,还应该是所有应用计算机技术的其他学科学生必须学习掌握的一门课程。
本书是根据全国高等教育“数据结构”课程教学大纲编写的教材,所选内容完全符合大纲的要求。全书共分10章,第1章综述了数据、数据结构、抽象数据类型及算法性能分析等基本概念;第2章至第7章分别讨论了线性表、栈、队列、串、多维数组、广义表、树以及图等基本的数据结构及其应用;第8章、第9章讨论了数据处理中广泛使用的排序和查找技术;第10章介绍外存储器上的数据结构,即文件的存储技术。
本书在内容表述上,参考了目前国外、国内几本比较流行的教材,并结合作者多年来从事“数据结构”、“算法设计与分析”以及“面向对象的程序设计”等课程的教学,以及编写出版多种有关“数据结构”教材和辅助教材的经验与体会,对本课程所涉及的主要知识进行了分析,介绍了一些新的观点和方法,并在各章中收集了大量的例题、习题,特别是实例分析和上机实验实训题解。这些实例与习题内容丰富,涉及面广,难易适当,给学习“数据结构”这门课程的读者以启发,可达到帮助学生掌握相关知识和开阔视野的目的,也将有利于培养学生分析问题、解决问题的动手能力。
本书在每一章的前面列出本章的学习目标和学习要点,以便读者学习时抓住重点。本书在内容安排上连贯有序、层次分明、循序渐进,力求表述严谨、语言精练、通俗易懂,既便于教学,又便于读者自学。
全书中算法和例题等都是采用类C语言或C语言描述的,特别是一些实例不需要修改或稍加修改就可以在VC环境下运行。为了增强算法的可读性,有些语句的后面使用了C++的注释说明符“//”,在这里提醒读者注意。
另外,在本书的附录中给出了各章习题的参考答案,这样有助于加深读者尤其是自学者对各种数据结构及其应用知识点的认识和理解。
本书由苏仕华、顾为兵、贾伯琪、刘勇编著。其中,顾为兵编写了第4、7、9章,贾伯琪编写了第3、5、8章,刘勇编写了思考题与习题、上机实验、习题参考答案、上机实验参考解答,苏仕华完成其他章节的编写及全书的统稿工作。在写作过程中,得到了中国科学技术大学计算机科学与技术学院黄刘生教授、信息科学技术学院刘振安教授的支持和帮助,中国科学技术大学信息科学技术学院刘勇博士、国防科学技术大学计算机学院陈怀义教授、南京大学计算机学院陈本林教授、北京理工大学软件学院院长陈朔鹰教授以及华中科技大学计算机学院卢炎生教授等对本书的编写提出了许多宝贵的意见和建议,在此表示衷心的感谢。另外,本书中还参考了大量的书籍和资料,作者在此一并致以诚挚的谢意。
由于作者水平有限,加之时间仓促,书中难免存在一些缺点和错误,殷切希望广大读者及同行们批评指正。
编者
2015年6月于合肥
总序
前言
第1章 概论
1.1 引言
1.2 基本概念和常用术语
1.3 算法的描述和分析
1.3.1 算法描述
1.3.2 算法分析
思考题
习题1
第2章 线性表
2.1 线性表的定义和基本运算
2.1.1 线性表的逻辑定义
2.1.2 线性表的基本运算
2.2 线性表的顺序存储和基本运算的实现
2.2.1 线性表的顺序存储
2.2.2 顺序表上基本运算的实现
2.3 线性表的链式存储结构
2.3.1 单链表(线性链表)
2.3.2 单链表上的基本运算
2.3.3 循环链表
2.3.4 双向循环链表
2.4 顺序表和链表的比较
思考题
习题2
上机实验
第3章 栈和队列
3.1 栈
3.1.1 栈的定义及其基本运算
3.1.2 栈的存储表示和实现
3.2 栈的应用举例
3.2.1 圆括号匹配的检验
3.2.2 字符串回文的判断
3.2.3 数制转换
3.2.4 栈与递归
3.3 队列
3.3.1 队列的定义及其运算
3.3.2 顺序循环队列
3.3.3 链队列
3.4 栈和队列的应用实例——表达式求值
3.4.1 中缀表达式到后缀表达式的转换
3.4.2 后缀表达式的计算
思考题
习题3
上机实验
第4章 串
4.1 串的定义及其运算
4.1.1 串的基本概念
4.1.2 串的基本运算
4.2 串的存储表示和操作的实现
4.2.1 串的顺序存储
4.2.2 串的链式存储
4.2.3 串运算的实现
4.3 串运算的应用举例
思考题
习题4
第5章 多维数组和广义表
5.1 多维数组及其运算
5.1.1 数组的顺序存储
5.1.2 数组运算举例
5.2 矩阵的压缩存储
5.2.1 特殊矩阵
5.2.2 稀疏矩阵
5.3 广义表
5.3.1 广义表的定义
5.3.2 广义表的运算
5.3.3 广义表的存储结构
思考题
习题5
第6章 树和二叉树
6.1 树的基本概念和术语
6.2 二叉树
6.2.1 二叉树的定义和性质
6.2.2 二叉树的存储结构
6.3 二叉树的运算
6.3.1 二叉树的生成
6.3.2 二叉树的遍历
6.3.3 二又树的应用举例
6.4 线索二叉树
6.4.1 二叉树的线索化
6.4.2 二叉线索链表上的运算
6.5 树和森林
6.5.1 树的存储结构
6.5.2 树、森林与二叉树的转换
6.5.3 树和森林的遍历
6.6 赫夫曼树及其应用
6.6.1 最优二叉树(赫夫曼树)
6.6.2 赫夫曼编码
思考题
习题6
上机实验
第7章 图
7.1 图的定义和基本术语
7.2 图的存储结构
7.2.1 邻接矩阵表示法
7.2.2 邻接表表示法
7.3 图的遍历
7.3.1 深度优先搜索
7.3.2 广度优先搜索
7.4 图的生成树和最小生成树
7.4.1 图的生成树
7.4.2 最小生成树
7.5 最短路径
7.6 拓扑排序
思考题
习题7
上机实验
第8章 排序
第9章 查找
第10章 文件
附录1 习题参考答案
附录2 上机实验参考解答
参考文献