数据结构(用面向对象方法与C++语言描述)第二版(本科教材)_PDF下载[74MB-百度云]殷人昆

内容简介

[

　　《数据结构：用面向对象方法与C++语言描述（第二版）》按照清华大学计算机系本科“数据结构”大纲的要求，从面向对象的概念、对象类设计的风格和数据结构的层次开始，从线性结构到非线性结构，从简单到复杂，深入地讨论了各种数据结构内在的逻辑关系及其在计算机中的实现方式和使用。此外，对常用的迭代、递归、回溯等算法设计技巧，搜索和排序算法等都做了详尽的描述，并引入了简单的算法分析。

]

第1章数据结构概论 1．1 数据结构的概念 1．1．1 数据结构举例 1．1．2 数据与数据结构 1．1．3 数据结构的分类 1．1．4 数据结构课程的内容 1．2 数据结构的抽象形式 1．2．1 数据类型 1．2．2 数据抽象与抽象数据类型 1．3 作为ADT的C++类 1．3．1 面向对象的概念 1．3．2 C++中的类 1．3．3 C++中的对象 1．3．4 C++的输入输出 1．3．5 C++中的函数 1．3．6 动态存储分配 1．3．7 C++中的继承 1．3．8 多态性 1．3．9 C++的模板 1．4 算法定义 1．5 算法性能分析与度量 1．5．1 算法的性能标准 1．5．2 算法的后期测试 1．5．3 算法的事前估计 1．5．4 算法的渐进分析 **1．5．5 *坏、*好和平均情况习题第2章线性表 2．1 线性表 2．1．1 线性表的概念 2．1．2 线性表的类定义 2．2 顺序表 2．2．1 顺序表的定义和特点 2．2．2 顺序表的类定义及其操作 2．2．3 顺序表的性能分析 2．2．4 顺序表的应用 2．3 单链表 2．3．1 单链表的概念 2．3．2 单链表的类定义 2．3．3 单链表中的插入与删除 2．3．4 带附加头结点的单链表 2．3．5 单链表的模板类 2．4 线性链表的其他变形 2．4．1 循环链表 2．4．2 双向链表 2．5 单链表的应用：多项式及其运算 **2．5．1 多项式的表示 **2．5．2 多项式的类定义 **2．5．3 多项式的加法 **2．5．4 多项式的乘法 2．6 静态链表习题第3章栈和队列 3．1 栈 3．1．1 栈的定义 3．1．2 顺序栈 3．1．3 链式栈 **3．1．4 栈的应用之一——括号匹配 **3．1．5 栈的应用之二——表达式的计算 3．2 栈与递归 3．2．1 递归的概念 3．2．2 递归过程与递归工作栈 **3．2．3 用回溯法求解迷宫问题 3．3 队列 3．3．1 队列的概念 3．3．2 循环队列 3．3．3 链式队列 3．3．4 队列应用举例：打印二项展开式（a+6）i的系数 **3．3．5 队列应用举例：电路布线 3．4 优先级队列 3．4．1 优先级队列的概念 **3．4．2 优先级队列的存储表示和实现 3．5 双端队列 3．5．1 双端队列的概念 3．5．2 双端队列的数组表示 3．5．3 双端队列的链表表示习题第4章数组、串与广义表 4．1 多维数组的概念与存储 4．1．1 多维数组的概念 4．1．2 多维数组的存储表示 4．2 特殊矩阵 4．2．1 对称矩阵的压缩存储 **4．2．2 三对角线／多对角线矩阵的压缩存储 4．3 稀疏矩阵 4．3．1 稀疏矩阵及其三元组数组表示 4．3．2 稀疏矩阵的转置 **4．3．3 稀疏矩阵的相加和相乘 **4．3．4 矩阵的正交链表表示 4．4 字符串 4．4．1 字符串的概念 4．4．2 C++有关字符串的库函数 4．4．3 字符串的实现 **4．4．4 字符串的自定义类 **4．4．5 字符串操作的实现 **4．4．6 字符串的模式匹配 **4．4．7 字符串的存储方法 4．5 广义表 4．5．1 广义表的定义与性质 4．5．2 广义表的表示 4．5．3 广义表存储结构的实现 **4．5．4 广义表的递归算法 **4．5．5 三元多项式的表示习题第5章树 5．1 树的基本概念 5．1．1 树的定义和术语 5．1．2 树的抽象数据类型 5．2 二叉树 5．2．1 二叉树的定义 5．2．2 二叉树的性质 5．2．3 二叉树的抽象数据类型 5．3 二叉树的存储表示 5．3．1 二叉树的数组存储表示 5．3．2 二叉树的链表存储表示 5．4 二叉树遍历及其应用 5．4．1 二叉树遍历的递归算法 5．4．2 二叉树遍历的应用 5．4．3 二叉树遍历的非递归算法 5．4．4 二叉树的计数 5．5 线索二叉树 5．5．1 线索 5．5．2 中序线索二叉树的建立和遍历 **5．5．3 中序线索二叉树的插入与删除 **5．5．4 前序与后序的线索化二叉树 5．6 树与森林 5．6．1 树的存储表示 5．6．2 森林与二叉树的转换 5．6．3 树与二叉树的转换 5．7 树与森林的遍历及其应用 5．7．1 树与森林的深度优先遍历 5．7．2 树和森林的广度优先遍历 **5．7．3 树遍历算法的应用 **5．7．4 其他基于遍历序列的几种存储表示 5．8 堆 5．8．1 *小堆和*大堆 5．8．2 堆的建立 5．8．3 堆的插入与删除 5．9 Huffman树及其应用 5．9．1 路径长度 5．9．2 Huffman树 **5．9．3 Huffman树的应用：*优判定树 5．9．4 Huffman树的应用：Huffman编码习题第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．4 跳表 6．4．1 跳表的概念 **6．4．2 跳表的类定义 **6．4．3 跳表的搜索、插入和删除 6．5 散列 6．5．1 散列表与散列方法 6．5．2 散列函数 6．5．3 处理冲突的闭散列方法 6．5．4 处理冲突的开散列方法 6．5．5 散列表分析习题 …… 第7章搜索结构第8章图第9章排序第10章文件、外部排序与搜索附录A 程序索引附录B 词汇索引参考文献