面向对象C++数据结构

第一部分 基本数据结构

第1章 数组

1．1 容器类和迭代程序

1．2 处理简单数据类型数组

1．2．1 添加元素

1．2．2 读取元素

1．2．3 删除元素

1．2．4 查找元素

1．2．5 查找数组的大小

1．2．6 使用数组管理器

1．2．7 使用迭代类列出元素

1．3 处理对象数组

1．3．1 被管理的类

1．3．2 mix-in类

1．3．3 面向对象的数组管理器

1．3．4 对象数组管理器的使用方法

1．3．5 列出对象数组管理器的元素值

1．4 让类变得通用

1．4．1 模板的声明

1．4．2 使用模板

.1．5 小结

第2章 向量

2．1 处理简单数据类型的向量

2．2 管理对象的向量

2．3 小结

第3章 链表

3．1 基本链表操作

3．2 单链表

3．2．1 链表的mix-in类

3．2．2 单链表的节点类

3．2．3 链表管理器

3．2．4 使用链表管理器

3．3 双向链表

3．3．1 双向链表的节点

3．3．2 双向链表的链表管理器

3．3．3 实现多个迭代类

3．4 小结

第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 小结

第二部分 树

第5章 二叉树

5．1 二叉树的结构

5．2 应用程序

5．3 修改mix-in类

5．4 树管理器类

5．5 插入节点

5．6 查找节点

5．7 删除节点

5．8 树的遍历

5．8．1 遍历的类型

5．8．2 堆栈在树的遍历中的作用

5．8．3 编写和执行中序遍历

5．8．4 编写和执行先序遍历

5．9 使用比较函数

5．10 小结

第6章 avl树

6．1 avl树的操作

6．1．1 平衡因子

6．1．2 在修改avl树时保持平衡

6．1．3 添加／删除节点后的新严衡因子

6．1．4 计算右旋转后的新严衡因子

6．1．5 计算左旋转后的新平衡因子

6．2 avl树类

6．3 在avl树中添加节点

6．4 从avl树中删除节点

6．5 小结

第7章 b树

7．1 b树的概念

7．2 树的节点类

7．3 b树类

7．4 查找元素

7．5 插入元素

7．5．1 将元素插入到一个具有空间的节点

7．5．2 在一个满节点中插入元素

7．6 删除元素

7．6．1 从叶子节点中删除一个元素并留下足够的元素

7．6．2 从叶子节点中删除一个元素而且剩余的元素数量不足

7．6．3 从非叶子节点中删除元素

7．7 小结

第8章 二叉堆和优先级队列

8．1 二叉堆的特征

8．2 优先级队列类的声明

8．3 向量存储类

8．4 在优先级队列中插入元素

8．5 从优先级队列中删除元素

8．6 使用二叉堆排序

8．7 小结

第三部分 排序、访问和查找

第9章 排序和查找

9．1 已知内容

9．2 排序内容

9．3 测量排序算法的效率

9．4 排序例程的结构示例

9．5 冒泡排序

9．6 选择排序

9．7 插入排序

9．7．1 新数组的插入排序

9．7．2 现有数组的插入排序

9．8 希尔排序

9．9 快速排序

9．9．1 递归方式的快速排序

9．9．2 非递归的快速排序

9．10 归并排序

9．11 基数排序

9．12 二分法查找

9．13 小结

第10章 哈希表

10．1 哈希表的概念

10．1．1 冲突解决技术

10．1．2 创建哈希函数

10．1．3 哈希表的迭代

10．2 使用相邻元素解决冲突

10．2．1 添加元素

10．2．2 查找元素

10．2．3 列出元素

10．3 使用链表处理冲突

10．3．1 添加元素

10．3．2 查找元素

10．3．3 删除元素

10．3．4 列出元素

10．4 小结

第11章 字典

11．1 关联

11．2 dictionary类

11．3 列出字典的内容

11．4 小结

第四部分 应用示例

第12章 音像店

12．1 实体类

12．1．1 customer类

12．1．2 商品项日的层次结构

12．1．3 项目拷贝的层次结构

12．2 实用程序类

12．2．1 字符串

12．2．2 日期

12．2．3 菜单

12．3 数据结构的选择

12．3．1 向量类的改进

12．3．2 二叉树类的改进

12．4 在应用程序类内部操作数据结构

12．4．1 管理用户界面

12．4．2 文件i／o

12．4．3 添加对象

12．4．4 租用和归还拷贝

12．5 程序应该提供的其他功能

12．6 小结

第13章 小镇药房

13．1 实体类

13．1．1 drug类

13．1．2 customer类

13．1．3 script类

13．1．4 有关删除操作的说明

13．2 选择用于文件访问的数据结构

13．3 应用程序类

13．3．1 程序的启动和终止运行

13．3．2 run函数

13．3．3 构建索引

13．3．4 药物管理

13．3．5 管理患者

13．3．6 管理处方

13．4 小结

附录 模板