奥赛经典高级教程系列：信息学奥林匹克教程数据结构篇

　　为了进一步推广、普及计算机技术，提高竞赛水平，在原来编写的一套《信息学奥林匹克教程》（基础篇·提高篇·语言篇）的基础了，我们又编写了这本《数据结构篇》。《数据结构篇》主要帮助学生全面地掌握数据结构知识与应用技巧，相对于其他数据结构书不同之处就在于增加了一些针对性的例题和习题，着眼点是提高数据结构的应用方法与技巧，是一本具有实战意义的教材。从逻辑角度看，数据可归结为三种基本结构：线性结构、树结构和图结构；从存储角度看，数据可归结为四种基本结构：顺序结构、链接结构、索引结构和散列结构。每一种逻辑结构可根据不同需要采用不同的存储结构，或者不同的存储结构的组合。数据的逻辑结构和存储结构确定后，再结合指定运算的算法，就容易利用一种程序设计语言编写出程序。通过数据结构的学习，能够大大提高程序设计能力和水平。《数据结构篇》是为广大信息学爱好者学习数据结构而精心编著的一本教材。本书内容比较全面，着重于实用与实战，在算法分析上简明扼要，细致清晰，便于自学。全书共分十章：第一章为概论，它为学习以后的各章做准备；第二章至第五章为线性结构；第六章和第七章分别为树结构和图结构，分别讨论了每一种逻辑结构所对应的存储结构和相应的算法；第八章和第九章分别为查找与排序，它包含了数据处理中主要使用的几种查找和内排序方法；最后一章为读者提供了检测知识的模拟试题及解答。

　　向期中，长郡中学特级教师，湖南省计算机学会理事，国际金牌教练，国家教育部计算机课程咨询委员会委员。对中小学计算机教育事业有一种执着的追求，参加工作20年来，一直以“当一流教师，办一流教育，出一流人才”为自己的工作目标，对中小学计算机教学和青少年信息学奥林匹克竞赛的辅导倾注了全部热情和心血。在信息学奥林匹克竞赛培训中把“先做人，后成才”的育人理念贯穿到整个奥赛培训的始终，学生在愉快的学习中取得了一个个辉煌的成绩：在近几年的信息学奥林匹克竞赛中，辅导的学生有100多人获湖南省一等奖，11人次进入国家集训队，3人进入国家代表队，3人获国际金牌。撰写了《信息学（计算机）国际奥林匹克Turbo Pas—cal 6.0》等十多部信息学专著。多次荣获园丁奖和全国优秀辅导员称号，还先后获得全国中小学计算机教育先进工作者、湖南省优秀教师和全国信息学奥林匹克竞赛高级指导教师等荣誉称号。

1 概论
1.1 基本术语
1.2 算法描述
1.3 算法评价
1.4 Pascal语言中的数据类型
1.5 小结
习题一
2 线性表
2.1 线性表的定义和顺序存储
2.2 线性表的运算
2.3 线性链表及链接存储
2.4 线性表的应用举例
2.5 小结
习题二
3 栈和队列
3.1 栈
3.2 栈的应用举例
3.3 队列
3.4 队列的应用举例
3.5 链接的栈和队列
3.6 小结
习题三
4 串
4.1 串的基本概念
4.2 串的定义
4.3 串的实现及基本运算
4.4 串的应用
4.5 小结
习题四
5 数组、特殊矩阵和广义表
5.1 多维数组
5.2 稀疏矩阵
5.3 特殊矩阵的压缩存储
5.4 广义表
5.5 小结
习题五
6 树
6.1 树的概念
6.2 二叉树
6.3 二叉树的运算
6.4 二叉搜索树
6.5 哈夫曼树
6.6 树的存储结构和运算
6.7 树、森林和二叉树的转换
6.8 最近公共祖先
6.9 树状数组
6.10 并查集
6.11 树的应用举例
6.12 小结
习题六
7 图
　 7.1 图的概念
　 7.2 图的基本术语
　 7.3 图的存储结构
　 7.4 图的遍历
　 7.5 图的生成树与最小生成树
　 7.6 最短路径
　 7.7 拓扑排序
　 7.8 关键路径
　 7.9 图的应用举例
　 7.10 小结
　 习题七
8 查找
8.1 查找的基本概念
8.2 顺序表查找
8.3 索引查找
8.4 散列查找
8.5 树表查找
8.6 查找的应用举例
8.7 小结
习题八
9 排序
10 模拟试题
习题参考答案