奥赛经典高级教程系列：信息学奥林匹克教程数据结构篇
点此进入淘宝搜索页搜索分类: 图书,中小学教辅,竞赛/奥赛,物理/化学/信息,
作者： 向期中编著
出 版 社： 湖南师大
出版时间： 2006-8-1字数：版次： 1页数： 357印刷时间：开本： 16开印次：纸张：I S B N ： 9787810815758包装： 平装内容简介
为了进一步推广、普及计算机技术，提高竞赛水平，在原来编写的一套《信息学奥林匹克教程》（基础篇提高篇语言篇）的基础了，我们又编写了这本《数据结构篇》。
《数据结构篇》主要帮助学生全面地掌握数据结构知识与应用技巧，相对于其他数据结构书不同之处就在于增加了一些针对性的例题和习题，着眼点是提高数据结构的应用方法与技巧，是一本具有实战意义的教材。
从逻辑角度看，数据可归结为三种基本结构：线性结构、树结构和图结构；从存储角度看，数据可归结为四种基本结构：顺序结构、链接结构、索引结构和散列结构。每一种逻辑结构可根据不同需要采用不同的存储结构，或者不同的存储结构的组合。数据的逻辑结构和存储结构确定后，再结合指定运算的算法，就容易利用一种程序设计语言编写出程序。通过数据结构的学习，能够大大提高程序设计能力和水平。
《数据结构篇》是为广大信息学爱好者学习数据结构而精心编著的一本教材。本书内容比较全面，着重于实用与实战，在算法分析上简明扼要，细致清晰，便于自学。全书共分十章：第一章为概论，它为学习以后的各章做准备；第二章至第五章为线性结构；第六章和第七章分别为树结构和图结构，分别讨论了每一种逻辑结构所对应的存储结构和相应的算法；第八章和第九章分别为查找与排序，它包含了数据处理中主要使用的几种查找和内排序方法；最后一章为读者提供了检测知识的模拟试题及解答。
作者简介
向期中，长郡中学特级教师，湖南省计算机学会理事，国际金牌教练，国家教育部计算机课程咨询委员会委员。对中小学计算机教育事业有一种执着的追求，参加工作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 模拟试题
习题参考答案
书摘插图
1 概论
自1946年美国第一台电子计算机问世以来，计算机科学和软硬件得到了飞速的发展，与此同时，计算机应用领域也从最初的科学计算逐步发展到人类活动的各个领域。现在，计算机处理的对象不仅是简单的数值或字符，而且是带有不同结构的各种数据：图像、声音等。因此，要设计出一个较好的程序，除了掌握所用的计算机语言外，还要研究各种数据结构的特性和数据之间存在的关系，这就是“数据结构”这门学科形成和发展的背景。
要搞好信息学竞赛，最基本的就是要掌握好程序设计，而程序设计是一门综合学科，与程序设计最密切的课程有数据结构、算法分析与设计和程序设计方法学等。著名的计算机科学家沃斯（N.Wfith）甚至提出了“算法+数据结构=程序”的著名论点，简明地概括了程序的组成。
数据是程序加工的原材料，它可能是数字、字符或由它们组成的字符串；它也可能是采样后的物理量，例如电压、电流等电信号通过模一数转换器（A/D）输出变成计算机可以接受的数字信息；或是从磁带、磁盘和光盘上读出的一串二进制数表示的数字、字符或图形的信息；或是调制解调器（Modem）上将电话声音信号转换成计算机可以接受的格式；或是通过键盘、磁盘文件输入到计算机的信息……简言之，数据是描述客观事物的数字、字符以及所有能输入到计算机、能被计算机进行处理的信息集合。也就是说，数据是符号的集合，是计算机要处理的信息集合。从本质上来说，数据是客观事物表示的一种抽象结果，而数据结构课程就是研究如何把客观世界要处理的信息逐层抽象成计算机可以接受的某种形式。
算法是解题的方法和步骤的精确描述，它是有穷处理的序列。
数据结构和算法有着密切的联系，数据结构是建立在算法的基础上，而选择什么样的数据结构对于程序设计来说，是至关重要的决策，它直接影响到程序的效率。选择一个合适的数据结构便很容易形成一个简洁有效的算法；否则，如果数据结构选择不好，除了影响程序开发速度之外，更重要的是影响设计出来的程序的运行效率。
……
