数据结构
2011-8
科学出版社
严丽丽 编
259
《数据结构》介绍了各种类型的数据结构，包括逻辑结构、物理结构和数据操作。力求以通俗易懂的讲解配以图示方法，使读者能对抽象的内容进一步理解。
?《数据结构》共分8章，叙述了几种不同数据结构和查找、排序技术，阐述了线性表、栈、队列、串、数组、二叉树、树、图等各种基本数据结构的概念；从物理角度讲解了每种逻辑结构的不同存储结构，以及相应操作的实现和结构特点分析；从算法的角度详细介绍了不同的排序和查找。
?《数据结构》内容翔实，图文并茂，各章后都有习题和实训题。实训代码均在turboc上调试通过，对理解数据结构有一定帮助。
?《数据结构》旨在为计算机及相关专业的应用型本科及高职高专学生教学使用，也可以作为从事计算机软件开发人员和自学人员的参考书。
第1章 概述??
1.1 什么是数据结构??
1.2 基本概念和术语??
1.3 算法描述和算法分析??
1.3.1 算法的概念??
1.3.2 算法设计的要求??
1.3.3 算法的描述??
1.3.4 算法性能的评价??
1.4 本课程学习指导??
1.5 本章小结??
1.6 习题??
第2章 线性表??
2.1 什么是线性表??
2.2 线性表的顺序存储结构及其算法??
2.2.1 线性表的顺序存储结构??
2.2.2 顺序表的运算??
2.2.3 顺序表应用——班级考勤统计??
2.3 线性表的链式存储结构??
2.3.1 动态内存分配及其管理??
2.3.2 线性链表??
2.3.3 循环链表??
2.3.4 双向链表??
2.3.5 静态链表??
2.4 线性链表的应用——一元多项式的表示及加法运算??
2.5 本章小结??
2.6 习题??
2.7 实训题??
实训一 学生基本信息??
实训二 线性链表的基本操作??
第3章 栈和队列??
3.1 栈??
3.1.1 栈的定义??
3.1.2 栈的存储结构及其基本运算??
3.1.3 栈的应用??
3.2 队列??
3.2.1 队列的定义??
3.2.2 队列的存储结构及其基本运算的实现??
3.2.3 队列的应用??
3.3 本章小结??
3.4 习题??
3.5 实训题??
实训一 表达式求值??
实训二 商品货架管理??
第4章 数组和字符串??
4.1 数组??
4.1.1 数组的定义和操作??
4.1.2 数组的顺序存储和访问??
4.1.3 数组的类型的实现??
4.1.4 特殊矩阵的压缩存储??
4.2 串??
4.2.1 字符串的基本操作??
4.2.2 定长字符串的实现??
4.2.3 可变长字符串的实现??
4.2.4 字符串的模式匹配??
4.2.5 字符串应用举例??
4.3 本章小结??
4.4 习题??
4.5 实训题??
实训一 字符串操作??
实训二 稀疏矩阵转置??
第5章 树??
5.1 树??
5.1.1 树的基本概念??
5.1.2 树的基本术语??
5.1.3 树的基本运算??
5.2 二叉树??
5.2.1 二叉树的概念??
5.2.2 二叉树的性质??
5.2.3 二叉树的存储结构??
5.2.4 遍历二叉树??
5.2.5 哈夫曼树和哈夫曼编码??
5.2.6 应用实例??
5.3 树和森林??
5.3.1 树的存储结构??
5.3.2 树、森林与二叉树的转换??
5.3.3 树和森林的遍历??
5.4 本章小结??
5.5 习题??
5.6 实训题??
实训 二叉树的应用??
第6章 图??
6.1 图的定义和基本术语??
6.1.1 图的定义??
6.1.2 图的基本术语??
6.2 图的存储结构??
6.2.1 邻接矩阵??
6.2.2 邻接表??
6.3 图的遍历??
6.3.1 深度优先搜索（dfs）??
6.3.2 广度优先搜索（bfs）??
6.4 图的应用??
6.4.1 最小生成树??
6.4.2 最短路径??
6.5 拓扑排序??
6.5.1 aov网??
6.5.2 拓扑排序??
6.6 本章小结??
6.7 习题??
6.8 实训题??
实训 图的存储和遍历??
第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.6.1 多关键字排序??
7.6.2 链式基数排序??
7.7 排序方法的比较??
7.8 本章小结??
7.9 习题??
7.10 实训题??
实训 排序算法的实现??
第8章 查找??
8.1 查找的基本概念??
8.2 基于线性表的查找方法??
8.2.1 顺序查找法??
8.2.2 折半查找法??
8.2.3 分块查找法——索引顺序查找??
8.3 树表查找法??
8.3.1 二叉排序树??
8.3.2 平衡二叉树??
8.4 哈希表查找??
8.4.1 哈希表与哈希查找??
8.4.2 构造哈希函数的方法??
8.4.3 处理冲突的方法??
8.4.4 哈希表的查找分析??
8.5 本章小结??
8.6 习题??
8.7 实训题??
实训 查找的实现??
附录??
参考文献?
6.存储结构 数据在计算机中的表示（又称映象）称为数据的物理结构，也叫存储结构。它是逻辑结构在计算机中的实现，包括数据元素的表示和关系的表示。数据元素的关系在计算机中有两种不等的不同的表示方法：顺序映象存储结构和非顺序映象。由此得到两种不同的存储结构：顺序存储结构和非顺序存储结构（也叫链式存储结构）。初学者要注意理解逻辑结构和物理结构的差异。逻辑结构表示数据元素之间的逻辑关系，是抽象的；而存储结构是逻辑结构在计算机中的实现，是面向计算机、面向现实世界的。在后面将要介绍的算法中可以看到，任何一个算法的设计都取决于所选定的数据逻辑结构，而算法的实现则依赖于所采用的存储结构。 7.操作集合 在结构上的操作是数据结构这门课程要研究的重要内容。数据结构是研究一类数据的表示及其相关运算的操作。一般来讲，数据的操作主要有以下几种。 ①添加在数据结构中指定的位置上新增数据元素。 ②删除删去数据结构中某个指定的数据元素。 ③修改改变数据结构中某个位置的数据元素值。 ④查询在数据结构中查找某个给定要求的数据元素。 ⑤排序对数据结构中的元素重新排列顺序，使数据元素按某种顺序排列。 8.数据类型 数据类型（Data Type）和数据结构关系非常密切，在早期的高级程序设计语言中，数据类型用以刻画操作对象（程序）的特性。在用高级语言编写的程序中，每个变量、常量和表达式都具有一个确定的数据类型。比如，C语言中的短整型（int）、字符型（char）等。类型显式或隐式地规定了程序执行期间变量或表达式所有可能的取值范围，以及在这些数据上所允许的操作。因此，学者们也将数据类型定义为一个值的集合和定义在这个集合之上的一组操作的总称。比如，在C语言中定义一个实型变量，则定义在其上的操作为加、减、乘、除等算术运算。 按照数据元素取值的不同特性，高级语言中一般都包括两种数据类型：原子类型和结构类型。原子类型的值是不可再分的，像c语言中的int类型、char类型、指针类型等；结构类型的值是由若干组成部分按某种结构组成的，可以再次分解，且各组成部分可以是原子类型，也可以是结构类型。 ……
《普通高等教育“十二五”重点规划教材·计算机系列：数据结构》重点规划，精心遴选；结构清晰，知识完整；示例丰富，易教易学；学以致用，注重能力。
