数据结构
2001-2
西安电子科技大学出版社
朱战立
333
数据结构是计算机等专业必修的核心课程。《新世纪计算机类本科规划教材：数据结构：使用C++语言（第2版）》是为高等院校开设该课程精心编著的教材。本书以面向对象观点讨论各种数据结构的设计和应用问题，用C++语言描述和实现了20多个类的设计和典型应用问题的程序设计。本书讨论的典型数据结构包括：线性表、堆栈、队列、数组、串、树、二叉树和图。本书讨论的典型算法问题包括：递归、排序和查找。本书介绍的典型存储结构包括：顺序存储结构、链式存储结构、间接地址和仿真指针。
第1章 C++面向对象程序设计要点 1.1 程序的结构 1.2 函数 1.2.1 函数的参数 1.2.2 函数的返回类型 1.2.3 函数名重载 1.3 类 1.3.1 类的存取权限 1.3.2 构造函数和析构函数 1.3.3 运算符重载 1.3.4 友元 1.3.5 分辨符 1.3.6 内联函数 1.3.7 默认值 1.3.8 多态性和虚函数 1.3.9 纯虚函数和抽象类 1.3.10 派生类继承方式 1.3.11 结构体 1.3.12 对象 1.4 抽象类型和模板 1.4.1 抽象类型 1.4.2 模板 1.5 输入输出1.6 动态申请和动态释放内存 1.7 面向对象程序设计方法 习题一 第2章 面向对象程序设计和算法性能分析 2.1 抽象数据类型 2.1.1 数据结构的基本概念 2.1.2 数据类型和抽象数据类型 2.1.3 模块化软件设计的优点 2.2 类和对象 2.2.1 类 2.2.2 对象 2.3 算法 2.3.1 算法的性质和设计目标 2.3.2 算法的时间效率 2.3.3 算法的符号命名、书写格式和注释格式 习题二 第3章 顺序存储结构的线性表、堆栈和队列 3.1 顺序存储结构 3.2 线性表和顺序表 3.2.1 顺序表类的定义 3.2.2 顺序表类的实现 3.2.3 顺序表上插入、删除算法的效率分析 3.2.4 顺序表的应用 3.3 堆栈和顺序堆栈 3.3.1 顺序堆栈类的定义和实现 *3.3.2 顺序堆栈应用——表达式计算3.4 队列和顺序队列 3.4.1 顺序循环队列 3.4.2 顺序循环队列类的设计 3.4.3 顺序循环队列的应用*3.5 优先级队列和顺序优先级队列 3.5.1 顺序优先级队列类设计 3.5.2 顺序优先级队列应用 3.6 顺序存储结构的特点 习题三 第4章 链式存储结构的线性表、堆栈和队列4.1 链式存储结构4.2 单链表4.2.1 结点类的设计4.2.2 单链表类的设计4.2.3 单链表类的应用4.3 单循环链表4.3.1 单循环链表类的设计4.3.2 单循环链表类的应用4.4 双向循环链表4.4.1 双向循环链表概念4.4.2 双向循环链表类的设计4.5 链式堆栈4.5.1 链式堆栈类的设计4.5.2 链式堆栈类的应用4.6 链式队列4.7 链式存储结构的特点习题四第5章 数组和串5.1 数组5.1.1 C++的数组5.1.2 安全数组类的设计5.2 间接地址5.3 特殊矩阵的压缩存储5.3.1 矩阵的定义和操作5.3.2 对称矩阵的压缩存储5.3.3 上三角矩阵压缩存储类5.4 稀疏矩阵的压缩存储5.4.1 稀疏矩阵的三元组表5.4.2 稀疏矩阵的三元组顺序表类5.4.3 稀疏矩阵的三元组链表5.5 串5.5.1 串的定义、存储结构和操作5.5.2 C++的串5.5.3 串类的设计5.5.4 模式匹配的Brute—F0rce算法*5.5.5 模式匹配的KMP算法习题五第6章 递归6.1 递归的概念6.2 递归算法的设计6.3 递归过程和递归工作栈*6.4 递归算法的效率分析*6.5 转化递归算法为非递归算法6.5.1 尾递归和单向递归的消除6.5.2 模拟系统的运行时栈消除递归6.6 回溯法习题六第7章 树和二叉树7.1 仿真指针7.2 树7.2.1 树的定义7.2.2 树的表示方法7.2.3 树的基本操作7.2.4 树的遍历操作7.2.5 树的存储结构7.2.6 树类7.3 二叉树7.3.1 二叉树的定义7.3.2 二叉树的性质7.3.3 二叉树的操作7.3.4 二叉树的遍历7.3.5 二叉树的存储结构7.3.6 树和二叉树的转换7.4 链式存储结构的二叉树设计7.4.1 二叉树结点类7.4.2 二叉树的遍历7.4.3 二叉树遍历的应用7.4.4 应用示例7.4.5 二叉树类7.5 二叉树遍历游标类7.5.1 二叉树中序遍历游标类*7.5.2 二叉树前序遍历游标类*7.5.3 二叉树层序遍历游标类7.6 线索二叉树7.6.1 线索二叉树的存储结构7.6.2 线索二叉树类7.6.3 中序线索二叉树类7.7 堆7.7.1 堆的定义7.7.2 最小堆类7.7.3 最小堆类的测试7.8 哈夫曼树7.8.1 路径长度和哈夫曼树7.8.2 哈夫曼编码*7.8.3 哈夫曼编码问题数据结构设计*7.8.4 哈夫曼编码问题算法设计习题七第8章 图8.1 图的基本概念和基本操作8.1.1 图的基本概念8.1.2 图的基本操作8.2 邻接矩阵存储结构的图类8.2.1 图的邻接矩阵存储结构8.2.2 邻接矩阵表示的图类8.2.3 邻接矩阵图类的深度优先搜索遍历8.2.4 邻接矩阵图类的广度优先搜索遍历8.2.5 非连通图和连通分量8.2.6 邻接矩阵图类的测试8.3 邻接表存储结构图类8.3.1 图的邻接表存储结构8.3.2 邻接表存储结构的图类8.3.3 邻接表存储结构图类的测试8.4 图的其他存储结构8.4.1 逆邻接表8.4.2 十字链表8.4.3 邻接多重表8.5 最小生成树8.5.1 最小生成树的基本概念8.5.2 普里姆算法8.5.3 克鲁斯卡尔算法8.6 最短路径8.6.1 最短路径的基本概念8.6.2 从一个结点到其余各结点的最短路径*8.6.3 每对结点之间的最短路径习题八第9章 排序9.1 排序的基本概念9.2 插入排序”9.2.1 直接插入排序9.2.2 希尔排序9.3 选择排序9.3.1 直接选择排序9.3.2 堆排序9.4 交换排序9.4.1 冒泡排序9.4.2 快速排序9.5 归并排序9.6 基数排序9.7 性能比较习题九第10章 查找10.1 查找的基本概念10.2 顺序表查找10.2.1 无序顺序表查找10.2.2 有序顺序表查找10.3 索引表查找10.3.1 索引表10.3.2 倒排索引表10.4 树表查找l0.4.1 二叉排序树10.4.2 平衡二叉树10.4.3 B树10.5 哈希表查找10.5.1 哈希表的基本概念10.5.2 哈希函数构造方法10.5.3 哈希冲突解决方法10.5.4 哈希表类习题十参考文献
随着作者对数据结构教材内容理解的进一步深入和编写教材水平的提高，以及几年来使用本教材的授课实践，作者朱战立认为有必要重新修订本教材。本次修订的《新世纪计算机类本科规划教材：数据结构：使用C++语言（第2版）》内容主要包括以下几个方面：对部分章节内容进行了重新编排组织；对全书的文字进行了仔细推敲，改写了原先叙述不恰当或不完善的地方；使用了更为规范的数据结构术语，并为方便读者学习，重要术语的定义处以黑体字形式给出；按统一的工程格式重新调试和书写了全部算法；修改完善或重新设计了各章的应用举例；补充了一些习题。
