数据结构
2010-6
厦门大学出版社
石曼银 编
239
“数据结构”是计算机程序设计的重要理论基础，它不仅是计算机专业的核心课程，也是其他理工专业的热门选修课。在计算机的应用领域中，数据结构有着广泛的应用。 本书是作者根据自己的教学经验总结，为高职高专计算机专业学生编写的教材。作者在教学过程中发现，大多数学生在初学数据结构时，容易误解算法与程序之间的关系，经常会把书中的算法当作程序直接在编译器上进行运行测试。为了解决这个问题，本书采用C语言作为数据结构和算法的描述语言，并且对关键的算法都安排了完整的C语言程序供学生上机实习参考，程序均在VC编译器下编译运行。书中给出的每一个算法都是完整的，只要添加上主函数，程序即可运行，主函数的添加可以模仿书中给出的完整程序。 高职高专类院校面向应用，注重实践，本书力求做到选材精练，叙述简洁，通俗易懂，尽量避免抽象理论的介绍和复杂公式的推导。对各种数据结构均从实际出发，通过对实例的分析，使学生理解数据结构的基本概念。 考虑到专升本和其他考试的需要，在每章后面附有适量的习题。习题中编排了较多的选择题和填空题，并配有习题答案，方便学生自学参考。 本书共分9章，第1章介绍了数据结构的基本概念和算法分析的初步知识；第2章到第5章介绍了线性表、栈和队列、串、数组和广义表等线性结构的基本概念及常用算法的实现；第6章和第7章介绍了非线性结构的树、二叉树、图等数据结构的存储结构和不同存储结构上的一些操作的实现；第8章介绍了各种查找表及查找方法；第9章介绍了各种排序算法。本书计划学时为80学时左右，其中上机实习为35学时左右。 本书第1、5、6、7章由石曼银编写，第2、3、4章由张启宁编写，第8、9章由李志亮编写，全书由石曼银统一编排定稿。
数据结构(C语言描述)》是作者根据自己的教学经验总结，为高职高专计算机专业学生编写的教材。作者在教学过程中发现，大多数学生在初学数据结构时，容易误解算法与程序之间的关系，经常会把书中的算法当作程序直接在编译器上进行运行测试。为了解决这个问题，《数据结构(C语言描述)》采用C语言作为数据结构和算法的描述语言，并且对关键的算法都安排了完整的C语言程序供学生上机实习参考，程序均在VC编译器下编译运行。书中给出的每一个算法都是完整的，只要添加上主函数，程序即可运行，主函数的添加可以模仿书中给出的完整程序。
前言第1章 绪论1.1 什么是数据结构1.2 数据结构的重要性1.3 基本概念和术语1.3.1 基本术语1.3.2 数据的逻辑结构1.3.3 数据的存储结构1.3.4 数据的运算与实现1.4 抽象数据类型1.5 算法与算法分析1.5.1 问题、算法和程序1.5.2 算法设计的要求1.5.3 算法分析本章小结练习题第2章 线性表2.1 线性表的基本概念2.1.1 线性表的自然语言定义2.1.2 线性表的ADT定义2.2 线性表的顺序存储结构及其运算2.2.1 顺序表的存储结构2.2.2 顺序表的基本操作2.2.3 顺序表的特点2.3 线性表的链式存储结构及其运算2.3.1 单链表的存储结构2.3.2 单链表的基本运算2.3.3 循环链表(Circular Linked List)2.3.4 双向链表(Double Linked List)2.3.5 线性表链式存储结构的特点2.4 线性表的应用举例2.5 上机实验2.5.1 实验目的2.5.2 实验内容本章小结练习题第3章 栈和队列3.1 栈的基本概念3.1.1 栈的自然语言定义3.1.2 栈的ADT定义3.2 栈的顺序存储结构及其运算3.2.1 栈的顺序存储结构3.2.2 顺序栈的基本操作3.3 栈的链式存储结构及其运算3.3.1 栈的链式存储结构3.3.2 链栈的基本操作3.4 栈的应用举例3.5 队列3.5.1 队列的自然语言定义3.5.2 队列的ADT定义3.6 队列的顺序存储结构及其运算3.6.1 队列的顺序存储结构3.6.2 循环队列3.6.3 循环队列的基本操作3.7 队列的链式存储结构及其运算3.7.1 队列的链式存储结构3.7.2 链队列的基本操作3.8 队列的应用举例3.9 上机实验3.9.1 实验目的3.9.2 实验内容本章小结练习题第4章 串4.1 串的基本概念4.1.1 串的自然语言定义4.1.2 串的ADT定义4.2 串的顺序存储结构及其运算4.2.1 串的顺序定长存储结构4.2.2 顺序串的基本操作4.3 串的堆分配存储结构及其运算4.3.1 串的堆分配存储结构4.3.2 串的堆分配存储结构的基本操作4.4 串的链式存储结构4.5 串的应用举例4.6 上机实验4.6.1 实验目的4.6.2 实验内容本章小结练习题第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.4 上机实验5.4.1 实验目的5.4.2 实验内容本章小结练习题第6章 树6.1 树的基本概念6.1.1 树的自然语言定义6.1.2 树的ADT定义6.1.3 树的表示方法6.1.4 树的基本术语6.2 树的存储结构6.2.1 树的顺序存储结构6.2.2 树的链式存储结构6.3 二叉树6.3.二叉树的定义6.3.2 二叉树的性质6.3.3 二叉树的存储结构6.3.4 二叉树的遍历6.3.5 线索二叉树6.3.6 二叉树的应用6.4 树、森林与二叉树之间的转换6.4.1 树、森林转换为二叉树6.4.2 二叉树转换为树、森林6.4.3 树和森林的遍历6.5 哈夫曼树6.5.1 哈夫曼树的基本概念6.5.2 构造哈夫曼树6.5.3 哈夫曼树的应用6.6 上机实验6.6.1 实验目的6.6.2 实验内容本章小结练习题第7章 图7.1 图的基本概念7.1.1 图的定义7.1.2 图的基本术语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.5.1 某个源点到其他各顶点的最短路径7.5.2 每对顶点之间的最短路径7.6 有向无环图及其应用……第8章 查找第9章 排序参考答案参考文献
数据类型是指程序设计语言中各变量可取的数据种类。例如在FORTRAN语言中，变量的数据类型有整型、实型和复数型；在c语言中，数据类型有基本类型和构造类型两种，其中基本类型有整型、浮点型、字符型等，构造类型有数组、结构体、联合、指针、枚举型、自定义等。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。 在分析一些复杂的情况或处理复杂的事物时，我们一般采用抽象思维的方法，即舍去复杂系统中非本质的成分，只对其中一些本质的可以反映系统重要特性的东西归纳提炼出来，设计出系统的模型，然后深入研究这些模型，得出一般的规律性的东西，解决实际问题。这种抽象思维的方法同样适用于软件系统的设计和研究。在复杂的软件系统设计中，对所包括的数据和操作进行抽象分析，从而更有效地进行软件系统的设计，将数据抽象和运算抽象紧密地结合在一起就构成抽象数据类型的概念。 抽象数据类型（Abstract Data Type，ADT）是指用以下方式构造出来的数据类型，定义一个数据逻辑模型（数学模型），以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。换句话说，不论它的内部结构如何变化，只要它的数学特性不变，都不影响它的外部使用。 抽象数据类型的概念并不是全新的概念，它实际上是我们熟悉的基本数据类型概念的引申和发展。由计算机高级程序设计语言可知，基本数据类型已隐含着数据模型和定义在该模型上的运算的统一，只是没有形成抽象数据类型的概念而已。如整型就是整数值模型与加、减、乘、除、取模等几种运算的统一体。
