数据结构与算法

第1章Java语言的面向对象编程

1．1Java入门

1．1．1变量声明

1．1．2运算符

1．1．3选择语句

1．1．4循环语句

1．1．5异常处理

1．2Java面向对象编程

1．2．1封装

1．2．2抽象数据类型

1．2．3继承

1．2．4多态性

1．3输入和输出

1．4Java和指针

1．5java．util中的向量

1．6数据结构和面向对象编程

1．7示例学习：随机存取文件

1．8习题

1．9编程作业

参考文献

第2章复杂性分析

2．1计算复杂性和渐近复杂性

2．2大O表示法

2．3大O表示法的性质

2．4和表示法

2．5可能出现的问题

2．6复杂性示例

2．7寻找渐近复杂性：示例

2．8最好的、平均的和最坏的情况

2．9补偿复杂性

2．10习题

参考文献

第3章链表

3．1单向链表

3．1．1插入

3．1．2删除

3．1．3查找

3．2双向链表

3．3循环链表

3．4跳转表

3．5自组织表

3．6稀疏表

3．7用java．util的链表

3．8小结

3．9示例学习：图书馆管理

3．10习题

3．11编程作业

参考文献

第4章堆栈和队列

4．1堆栈4．2队列

4．3优先级队列

4．4示例学习：逃离迷宫

4．5习题

4．6编程作业

参考文献

第5章递归

5．1递归定义

5．2方法调用和递归实现

5．3剖析一个递归调用

5．4尾递归

5．5非尾递归

5．6间接递归

5．7嵌套递归

5．8过分递归

5．9回溯

5．10小结

5．11示例学习：一个递归下降解释器

5．12习题

5．13编程作业

参考文献

第6章二叉树

6．1树、二叉树和折半查找树

6．2实现二叉树

6．3搜索折半查找树

6．4树的遍历

6．4．1广度优先遍历

6．4．2深度优先遍历

6．4．3无堆栈深度优先遍历

6．5插入

6．6删除

6．6．1归并删除法

6.6.2拷贝删除法

6．7树的平衡，

6．7．1DSW算法

6．7．2AVL树

6．8自适应树

6．8．1自调整树

6．8．2扩展

6．9堆

6．9．1堆作为优先级队列

6．9．2以堆形式组织数组

6．10波兰表示法和表示树

6．11示例学习：计算单词频率

6．12习题

6．13编程作业

参考文献

第7章多分树

7．1B树家族

7．1．1B树7．1．2B树

7．1．3B树

7．1．4前缀B树

7．1．5比特树

7．1．6R树

7．1．72-4树

7．1．8java．util中的集合

7．1．9java．util中的映像

7．2线索

7．3小结

7．4示例学习：拼写检查程序

7．5习题

7．6编程作业

参考文献

第8章图

8．1图的表示法

8．2图的遍历

8．3最短路径

8．4环路检测

8．5生成树

8．5．1Boruvka算法

8．5．2Kruskal算法

8．5．3Jarnik-Prim算法

8．5．4Dijkstra算法

8．6连通性

8．6．1无向图的连通性

8．6．2有向图的连通性

8．7拓扑排序

8．8网络

8．8．1最大流

8．8．2最小代价的最大流量

8．9匹配

8．9．1分配问题

8．9．2非二部图中的匹配

8．10欧拉图和哈密顿图

8．10．1欧拉图

8．10．2哈密顿图

8．11示例学习：典型代表问题

8．12习题

8．13编程作业

参考文献

第9章排序

9．1元素排序算法

9．1．1插入排序

9．1．2选择排序

9．1．3起泡排序

9．2决策树

9．3高效排序算法

9．3．1希尔排序

9．3．2堆排序9．3．3快速排序

9．3．4归并排序

9．3．5基数排序

9．4java．util中的排序

9．5小结

9．6示例学习：多项式加法

9．7习题

9．8编程作业

参考文献

第10章散列

10．1散列函数

10．1．1除法

10．1．2折叠法

10．1．3平方取中散列函数

10．1．4提取方法

10．1．5基数变换

10．2冲突解决

10．2．1开放地址法

10．2．2链

10．2．3桶地址法

10．3删除

10．4理想散列函数

10．4．1Cichelli方法

10．4．2FHCD算法，

10．5可扩展文件的散列函数

10．5．1可扩展散列

10．5．2线性散列

10．6java．util中的散列

10．7示例学习

10．8习题

10．9编程作业

参考文献

第11章数据压缩

11．1数据压缩的条件

11．2霍夫曼编码

11．3Shannon-Fano码

11．4运行长度编码

11．5Ziv-Lempel编码

11．6示例学习：结合运行长度编码的霍夫曼方法

11．7习题

11．8编程作业

参考文献

第12章存储管理

12．1连续适应方法

12．2非连续适应方法

12．3无用单元收集

12．3．1标记与清除算法

12．3．2拷贝方法

12．3．3增量式无用单元收集

12．4小结12．5示例学习：内置无用单元收集器

12．6习题

12．7编程作业

参考文献

附录A大O的计算

人名索引

名词索引