《数据结构教程（第4版）》是2013年清华大学出版社出版的图书，作者是李春葆。
本书在前3版的基础上，根据教育部新的考研大纲和大量读者来信提出的要求进行了修订。本书内容包括绪论、线性表、栈和队列、串、递归、数组和广义表、树和二叉树、图、查找、内排序、外排序和文件，还给出了6个综合实验题、实验报告格式、引用型参数的说明、顺序表和顺序栈以及顺序队列使用指针引用型参数的说明、书中部分算法清单、全国计算机专业数据结构2011年联考大纲。本书适合高等院校计算机及相关专业本科生和研究生使用。
目录
- 第1章绪论
- 1.1什么是数据结构
- 1.1.1数据结构的定义
- 1.1.2逻辑结构类型
- 1.1.3存储结构类型 [1]
- 1.1.4数据类型和数据结构
- 1.2算法及其描述
- 1.2.1什么是算法
- 1.2.2算法描述
- 1.3算法分析
- 1.3.1算法设计的目标
- 1.3.2算法效率分析
- 1.3.3算法存储空间分析
- 1.4数据结构+算法=程序
- 1.4.1程序和数据结构
- 1.4.2算法和程序
- 1.4.3算法和数据结构
- 1.4.4数据结构的发展
- 本章小结
- 练习题1
- 上机实验题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.5有序表
- 2.5.1有序表的抽象数据类型描述
- 2.5.2有序表的存储结构及其基本运算算法
- 2.5.3有序表的归并算法
- 2.5.4有序表的应用
- 本章小结
- 练习题2
- 上机实验题2
- 第3章栈和队列
- 3.1栈
- 3.1.1栈的定义
- 3.1.2栈的顺序存储结构及其基本运算的实现
- 3.1.3栈的链式存储结构及其基本运算的实现
- 3.1.4栈的应用
- 3.2队列
- 3.2.1队列的定义
- 3.2.2队列的顺序存储结构及其基本运算的实现
- 3.2.3队列的链式存储结构及其基本运算的实现
- 3.2.4队列的应用
- 3.2.5双端队列
- 本章小结
- 练习题3
- 上机实验题3
- 第4章串
- 4.1串的基本概念
- 4.2串的存储结构
- 4.2.1串的顺序存储结构——顺序串
- 4.2.2串的链式存储结构——链串
- 4.3串的模式匹配
- 4.3.1Brute?Force算法
- 4.3.2KMP算法
- 本章小结
- 练习题4
- 上机实验题4
- 第5章递归
- 5.1什么是递归
- 5.1.1递归的定义
- 5.1.2何时使用递归
- 5.1.3递归模型
- 5.1.4递归与数学归纳法
- 5.2递归调用的实现原理
- 5.3递归算法的设计
- 5.3.1递归算法设计的步骤
- 5.3.2递归数据结构的递归算法设计
- 5.3.3递归求解方法的递归算法设计
- 本章小结
- 练习题5
- 上机实验题5
- 第6章数组和广义表
- 6.1数组
- 6.1.1数组的基本概念
- 6.1.2数组的存储结构
- 6.1.3特殊矩阵的压缩存储
- 6.2稀疏矩阵
- 6.2.1稀疏矩阵的三元组表示
- 6.2.2稀疏矩阵的十字链表表示
- 6.3广义表
- 6.3.1广义表的定义
- 6.3.2广义表的存储结构
- 6.3.3广义表的运算
- 本章小结
- 练习题6
- 上机实验题6
- 第7章树和二叉树
- 7.1树的基本概念
- 7.1.1树的定义
- 7.1.2树的逻辑表示方法
- 7.1.3树的基本术语
- 7.1.4树的性质
- 7.1.5树的基本运算
- 7.1.6树的存储结构
- 7.2二叉树的基本概念
- 7.2.1二叉树的定义
- 7.2.2二叉树的性质
- 7.2.3二叉树与树、森林之间的转换
- 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.5.3二叉树遍历非递归算法
- 7.5.4层次遍历算法
- 7.6二叉树的构造
- 7.7线索二叉树
- 7.7.1线索二叉树的概念
- 7.7.2线索化二叉树
- 7.7.3遍历线索化二叉树
- 7.8哈夫曼树
- 7.8.1哈夫曼树概述
- 7.8.2哈夫曼树的构造算法
- 7.8.3哈夫曼编码
- 7.9用并查集求解等价问题
- 7.9.1什么叫并查集
- 7.9.2并查集的算法实现
- 本章小结
- 练习题7
- 上机实验题7
- 第8章图
- 8.1图的基本概念
- 8.1.1图的定义
- 8.1.2图的基本术语
- 8.2图的存储结构
- 8.2.1邻接矩阵存储方法
- 8.2.2邻接表存储方法
- 8.3图的遍历
- 8.3.1图的遍历的概念
- 8.3.2深度优先遍历
- 8.3.3广度优先遍历
- 8.3.4非连通图的遍历
- 8.3.5图遍历算法的应用
- 8.4生成树和最小生成树
- 8.4.1生成树的概念
- 8.4.2无向图的连通分量和生成树
- 8.4.3普里姆算法
- 8.4.4克鲁斯卡尔算法
- 8.5最短路径
- 8.5.1路径的概念
- 8.5.2从一个顶点到其余各顶点的最短路径
- 8.5.3每对顶点之间的最短路径
- 8.6拓扑排序
- 8.7AOE网与关键路径
- 本章小结
- 练习题8
- 上机实验题8
- 第9章查找
- 9.1查找的基本概念
- 9.2线性表的查找
- 9.2.1顺序查找
- 9.2.2折半查找
- 9.2.3索引存储结构和分块查找
- 9.3树表的查找
- 9.3.1二叉排序树
- 9.3.2平衡二叉树
- 9.3.3B-树
- 9.3.4B+树
- 9.4哈希表查找
- 9.4.1哈希表的基本概念
- 9.4.2哈希函数构造方法
- 9.4.3哈希冲突解决方法
- 9.4.4哈希表上的运算
- 本章小结
- 练习题9
- 上机实验题9
- 第10章内排序
- 10.1排序的基本概念
- 10.2插入排序
- 10.2.1直接插入排序
- 10.2.2折半插入排序
- 10.2.3希尔排序
- 10.3交换排序
- 10.3.1冒泡排序
- 10.3.2快速排序
- 10.4选择排序
- 10.4.1直接选择排序
- 10.4.2堆排序
- 10.5归并排序
- 10.6基数排序
- 10.7各种内排序方法的比较和选择
- 本章小结
- 练习题10
- 上机实验题10
- 第11章外排序
- 11.1外排序概述
- 11.2磁盘排序
- 11.2.1生成初始归并段
- 11.2.2多路平衡归并
- 11.2.3最佳归并树
- 11.3磁带排序
- 11.3.1多路平衡归并排序
- 11.3.2多阶段归并排序
- 本章小结
- 练习题11
- 上机实验题11
- 第12章文件
- 12.1文件的基本概念
- 12.1.1什么是文件
- 12.1.2文件的逻辑结构及操作
- 12.1.3文件的存储结构
- 12.2顺序文件
- 12.3索引文件
- 12.3.1ISAM文件
- 12.3.2VSAM文件
- 12.4哈希文件
- 12.5多关键字文件
- 12.5.1多重表文件
- 12.5.2倒排文件
- 本章小结
- 练习题12
- 上机实验题12
- 第13章采用面向对象的方法描述算法
- 13.1面向对象的概念
- 13.2用C++描述面向对象的程序
- 13.2.1类
- 13.2.2类对象
- 13.2.3构造函数和析构函数
- 13.2.4派生类
- 13.3用C++描述数据结构算法
- 13.3.1顺序表类
- 13.3.2链栈类
- 13.3.3二叉树类
- 附录A综合实验题
- 综合实验题1链表综合算法设计
- 综合实验题2求复杂表达式的值
- 综合实验题3用二叉树实现家谱的相关运算
- 综合实验题4求无向图中满足约束条件的路径
- 综合实验题5分析二分查找成功时的平均查找长度
- 综合实验题6求各种排序算法的执行时间
- 附录B实验报告格式
- 附录C引用型参数的说明
- 附录D顺序表、顺序栈和顺序队列使用指针引用型参数的说明
- 附录E书中部分算法清单
- 附录F全国计算机专业数据结构2012年联考大纲
- 参考文献
