数据结构：用面向对象方法与C++描述

　　数据结构是计算机专业的核心课程，是从事计算机软件开发、应用人员应当必备的专业基础。随着计算机的日益普及，简单的数据结构知识已经下放到中学的计算机课程中，并已成为计算机软件考试的必考课程之一。本书是根据作者在北京清华大学及美国密西根州Grand Valley州立大学多年教学的经验，并参考了近年出版的多种国外大学数据结构和面向对象软件工程教科书编写的。内容包括：数组、链接表、栈和队列、递归、树与森林、图、堆与优先级队列、集合与搜索结构、排序、索引结构与散列等。 书中采用面向对象的观点讨论据结构技术、并以兼有面向过程和面向对象过程和面向对象双重特色的C++语言作为算法的描述工具、强化基本知识和基本能力的双基训练。全书条理清晰，通谷易懂，图文并茂，适于自学。本书适合作大专院校中计算机或软件专业的教材，也可供计算机软件人员和计算机用户阅读。

　　殷人昆，江苏省苏州市人，1980年获清华大学计算机软件工学硕士，日本国东京理科大学工学部访问学者。现任清华大学计算机系软件工程实验室主任，中国科学院研究生院远程教育部兼职教授，中央广播电视大学主讲教师，长期从事数据结构、软件工程和信息管理系统方面的教学与科研，已出版专著十余部，发表论文多篇。

    第1章 绪论
    1.1什么是数据结构
    1.2抽象数据类型及面向对象概念
    1.2.1数据类型
    1.2.2数据抽象与抽象数据类型
    1.2.3 面向对象的概念
    1.2.4 用于描述数据结构的语言
    1.3数据结构的抽象层次
    *1.4 用C＋＋描述面向对象程序
    1.4.1C＋＋的函数特征
    1.4.2C＋＋的数据声明
    1.4.3C＋＋的作用域
    1.4.4 C＋＋的类
    1.4.5C＋＋中的对象
    1.4.6C＋＋的输入输出
    1.4.7C＋＋中的函数
    1.4.8C＋＋中的参数传递
    1.4.9 C＋＋中的函数名重载和操作符重载
    1.4.10 C＋＋中的动态存储分配
    1.4.11友元（friend）函数
    1.4.12内联（inline）函数
    1.4.13 结构（struct）与类
    1.4.14 联合（Union）与类
    1.5算法定义
    1.6模板（template）
    1.7性能分析与度量
    1.7.1算法的性能标准
    1.7.2算法的后期测试
    1.7.3算法的事前估计
    1.7.4 空间复杂度度量
    1.7.5时间复杂度度量
    1.7.6时间复杂度的渐进表示法
    1.7.7渐进的空间复杂度
    习题
   第2章 数组
    2.1作为抽象数据类型的数组
    2.1.1在C＋＋中数组的定义和初始化
    2.1.2作为抽象数据类型的数组
    2.1.3数组的顺序存储方式
    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.4 稀疏矩阵
    2.4.1稀疏矩阵的抽象数据类型
    2.4.2稀疏矩阵的压缩表示
    2.4.3稀疏矩阵的转置
    2.4.4 稀疏矩阵相乘
    2.5字符串
    2.5.1字符串抽象数据类型和类定义
    2.5.2字符串操作的实现
    2.5.3字符串的模式匹配
    2.5.4模式匹配的改进算法——KMP（D.E.Knuth—J.H.Morris—V.R.Pratt）算法
    习题
   第3章 链表
    3.1单链表（SinglyLinkedList）
    3.1.1单链表的结构
    3.1.2单链表的类定义
    3.1.3单链表中的插入与删除
    3.1.4带表头结点的单链表
    3.1.5用模板定义的单链表类
    3.1.6单链表的游标（Iterator）类
    3.1.7静态链表
    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稀疏矩阵的建立
    3.5.3删除稀疏矩阵
    3.6C＋＋中的虚函数和动态联编
    3.6.1C＋＋中的继承（inheritance）
    3.6.2基类与派生类对象指针的转换
    3.6.3虚函数（virtualfunction）
    3.6.4 纯虚函数和抽象基类
    3.6.5多态性（polymorphism）和动态联编
    习题
   第4章 栈和队列
    4.1栈
    4.1.1栈的抽象数据类型
    4.1.2栈抽象数据类型的顺序存储表示与实现——顺序栈
    4.1.3栈抽象数据类型的链接存储表示——链式栈
    4.2表达式的计算
    4.2.1表达式
    4.2.2应用后缀表示计算表达式的值
    4.2.3中缀表达式转换为后缀表达式
    4.3队列
    4.3.1队列的抽象数据类型
    4.3.2队列的顺序存储表示——循环队列
    4.3.3队列的链接存储表示——链式队列
    4.3.4 队列的应用举例——打印二项展开式（a＋b）j的系数
    4.4优先级队列（PriorityQueue）
    4.4.1优先级队列的定义
    4.4.2优物级队列的存储表示和实现
    4.5事件驱动模拟
    习题
   第5章 递归
    5.1递归的概念
    5.2迷宫问题
    5.3递归过程与递归工作栈
    5.4利用栈实现的迷宫问题非递归解法
    5.5广义表
    5.5.1广义表的概念
    5.5.2广义表的表示及操作
    5.5.3广义表存储结构的实现
    5.5.4 广义表的访问算法
    5.5.5广义表的递归算法
    5.5.6三元多项式的表示
    习题
   第6章 树与森林
    6.1树和森林的概念
    6.1.1树的定义
    6.1.2树的术语
    6.1.3树的抽象数据类型
    6.2二叉树
    6.2.1二叉树的定义
    6.2.2二叉树的性质
    6.2.3二叉树的抽象数据类型
    6.3二叉树的表示
    6.3.1数组表示
    6.3.2链表存储表示
    6.4二叉树遍历
    6.4.1中序遍历
    6.4.2前序遍历
    6.4.3后序遍历
    6.4.4 应用二叉树遍历的事例
    6.4.5二叉树遍历的游标类
    6.4.6 不用栈的二叉树中序遍历算法
    6.5线索化二叉树
    6.5.1线索
    6.5.2中序线索化二叉树
    6.5.3前序与后序的线索化二叉树
    6.6 堆（Heap ）
    6.6.1堆的定义
    6.6.2堆的建立
    6.6.3堆的插入与删除
    6.7树与森林
    6.7.1树的存储表示
    6.7.2森林与二叉树的转换
    6.7.3树的遍历
    6.7.4 森林的遍历
    6.8二叉树的计数
    6.9 霍夫曼树
    6.9.1路径长度
    6.9.2霍夫曼树
    6.9.3霍夫曼编码
    习题
   第7章 集合与搜索
    7.1集合及其表示
    7.1.1集合基本概念
    7.1.2以集合为基础的抽象数据类型
    7.1.3用位向量实现集合抽象数据类型
    7.1.4 用有序链表实现集合的抽象数据类型
    7.2 等价类和并查集
    7.2.1等价关系与等价类
    7.2.2确定等价类的链表方法
    7.2.3并查集
    7.3静态搜索结构
    7.3.1搜索的概念
    7.3.2静态搜索结构
    7.3.3顺序搜索
    7.3.4 基于有序顺序表的折半搜索
    7.3.5基于有序顺序表的斐波那契搜索和插值搜索
    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.6AVL树
    7.6.1AVL树的定义
    7.6.2平衡化旋转
    7.6.3AVL树的插入和删除
    7.6.4AVL树的高度
    习题
   第8章 图
    8.1图的基本概念
    8.1.1图的基本概念
    8.1.2图的抽象数据类型
    8.2图的存储表示
    8.2.1邻接矩阵
    8.2.2 邻接表
    8.2.3邻接多重表
    8.3图的遍历与连通性
    8.3.1深度优先搜索
    8.3.2广度优先搜索
    8.3.3连通分量
    8.3.4 重连通分量
    8.4 最小生成树
    8.4.1克鲁斯卡尔（Kruskal）算法
    8.4.2普里姆（Prim）算法
    8.5最短路径
    8.5.1边上权值非负情形的单源最短路径问题
    8.5.2边上权值为任意值的单源最短路径问题
    8.5.3所有顶点之间的最短路径
    8.6 活动网络
    8.6.1用顶点表示活动的网络
    8.6.2用边表示活动的网络
    习题
   第9章 排序
    9.1概述
    9.2插入排序
    9.2.1直接插入排序
    9.2.2折半插入排序
    9.2.3链表插入排序
    9.2.4 希尔排序
    9.3交换排序
    9.3.1起泡排序
    9.3.2快速排序
    9.4 选择排序
    9.4.1直接选择排序
    9.4.2锦标赛排序
    9.4.3堆排序
    9.5归并排序
    9.5.1归并
    9.5.2迭代的归并排序算法
    9.5.3递归的表归并排序
    9.6基数排序
    9.6.1多关键码排序
    9.6.2链式基数排序
    9.7外排序
    9.7.1外排序的基本过程
    9.7.2k路平衡归并
    9.7.3初始归并段的生成
    9.7.4 并行操作的缓冲区处理
    9.7.5最佳归并树
    习题
   第10章 索引结构与散列
    10.1静态索引结构
    10.1.1线性索引
    10.1.2倒排表
    10.1.3m路静态搜索树
    10.2动态索引结构
    10.2.1动态的m路搜索树
    10.2.2B_树
    10.2.3B_树的插入
    10.2.4 B_树的删除
    10.2.5B＋树
    10.3Trie 树
    10.3.1Trie树的定义
    10.3.2Trie树的搜索
    10.3.3在Trie树上的插入和删除
    10.4散列
    10.4.1词典（Dictionary）的抽象数据类型
    10.4.2散列表与散列方法
    10.4.3散列函数
    10.4.4 处理溢出的闭散列方法
    10.4.5处理溢出的开散列方法——链地址法
    10.4.6散列表分析
    10.5可扩充散列
    10.5.1二叉Trie 树
    10.5.2将二叉Trie树转换为目录
    10.5.3插入与目录扩充
    10.5.4 删除与目录收缩
    10.5.5性能分析
    习题
   附录 实习要求与实习报告
   实习1栈和队列
   实习2串（内容：全屏幕文本编辑器）
   实习3树（内容：作业调度）
   实习4图（内容：某公园导游图）
   实习5查找、排序（内容：简单的职工管理系统）
   参考文献