数据结构与算法

第1章 绪论

1.1 数据结构简介

1.1.1 数据结构课程的内容

1.1.2 数据结构的基本概念和术语

1.2 抽象数据类型

1.3 算法的执行效率及其度量

1.3.1 算法

1.3.2 算法设计的要求

1.3.3 算法效率的度量

1.3.4 算法的存储空间需求

1.4 算法分析

1.4.1 算法设计与分析的重要性

1.4.2 一个简单的算法分析设计实例

习题

ACM/ICPC实战练习

第2章 线性结构

2.1 线性表

2.1.1 线性表的定义

2.1.2 线性表的抽象数据类型

2.1.3 线性表的存储结构

2.2 线性表的顺序存储及运算实现

2.2.1 顺序表

2.2.2 顺序表上基本运算的实现

2.2.3 顺序表应用举例

2.3 线性表的链式存储和运算实现

2.3.1 单链表

2.3.2 单链表上基本运算的实现

2.3.3 循环链表

2.3.4 双向链表

2.3.5 静态链表

2.3.6 单链表应用举例

2.3.7 线性表实现方法比较

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.6 数组

2.6.1 数组的定义

2.6.2 数组的顺序表示和实现

2.6.3 特殊矩阵的压缩存储

习题

ACM/ICPC实战练习

第3章 字符串

3.1 串类型定义

3.2 串的表示和实现

3.2.1 串的定长顺序存储结构及其基本运算实现

3.2.2 串的堆存储结构及其基本运算实现

3.2.3 串的链式存储结构及其基本运算实现

3.3 串的模式匹配算法

3.3.1 朴素匹配算法

3.3.2 KMP算法

3.3.3 基于KMP算法的应用举例

习题

ACM/ICPC实战练习

第4章 树和二叉树

4.1 树

4.1.1 树的定义和基本术语

4.1.2 树的抽象数据类型

4.1.3 树的存储结构

4.1.4 树的遍历

4.1.5 树的应用

4.2 二叉树

4.2.1 二叉树的定义

……

第5章 图论算法

第6章 内部排序

第7章 文件管理和外排序

第8章 检索与散列表

第9章 算法设计方法

参考文献

本书以数据结构基础和算法设计方法为知识单元，系统地介绍了数据结构与算法的基本知识及应用，简明扼要地阐释了计算机算法的设计与分析方法。本书的主要内容包括线性表、树、图等基础数据结构，同时也包括一些实用性较强的算法及高级数据结构，如并查集、伸展树等。以经典问题算法为例，书中分类介绍了算法设计方法以及查找与排序算法等。编者结合ACM国际大学生程序设计竞赛的需求，对各章节知识的灵活应用进行了详细的分析，用丰富的实例帮助读者由浅入深、快速地掌握算法设计的技巧，提升算法设计能力。本书的算法全部采用C语言描述，且在DevC++中测试通过，习题安排上注重能力培养和实战训练的需求。本书注重理论与实践相结合，内容深入浅出，可以作为高等院校计算机相关专业的教材或参考书，同时也可供ACM竞赛的兴趣爱好者和有关工程技术人员参考。