青少年信息学(计算机)奥林匹克竞赛培训教程系列丛书是由从事青少年信息学奥林匹克竞赛教育多年、具有丰富竞赛辅导和教学经验的一线教师共同精心编著而成的。
《数据结构与程序实现》是这套丛书的第二册。全书共分6章,第1章介绍了数据结构与算法的概念,第2章至第6章分别讲述了线性表、栈和队列、数组、矩阵和串、树、图的基本概念,存储结构,基本运算与程序实现以及它们的应用。为了使学生尽快了解、掌握竞赛的内容和范围,我们特意从近年来国际、国内信息学奥林匹克竞赛中精选了若干试题,在各章(第1章除外)中增加了“典型试题分析”的内容。对这些试题,应用本章所讲内容完全可以解决。
本书深入浅出,思路清晰,不仅能帮助刚刚迈进信息学奥林匹克竞赛大门的选手掌握数据结构与算法的基本知识,更能从启迪思维、开发智力的角度引导他们如何使用计算机来分析问题和解决问题。
本书既可以作为全国信息学奥林匹克竞赛的培训教材和自学用书,也可以作为ACM大学生程序设计竞赛及大专院校相关专业教师和学生的参考教材。
为方便读者,我们对每章提供的典型算法、例题、习题均给出了参考程序,使用者可在西安电子科技大学出版社网站http://www

第1章 数据结构与算法的概念
自从1946年世界上**台计算机诞生以来,计算机科学与技术的飞速发展和广泛应用远远超出了人们的预料。如今,计算机已渗透到现代社会的各行各业及方方面面,并在一定程度上改变了人类的活动方式和思维习惯。与此同时,计算机处理的对象也从单纯的数值数据发展到各种不同形式的数据,如字符、表格、声音、图像等。与纯粹的数值数据不同,非数值数据往往带有一定的“结构”,即数据之间的关联,它是数据所代表的客观对象之间相互联系的对应物。计算机在存储与处理这类数据时,也必须同时存储和处理这些“结构”,只有这样才能在计算机中完整地再现客观世界,进而实现用计算机来进行控制或管理。如何合理、有效地组织和存储这些信息,以支持高速的计算机信息处理,这是计算机科学研究的**之一。研究各种数据及其相互之间的关系、研究如何有效地存储数据、研究如何设计出性能良好的数据处理程序等,这些都是“数据结构”课程所要讨论的主要内容。因此,数据结构与算法不仅是计算机科学与技术学科的基础,也是计算机科学与技术学科永恒的主题。
……

第1章 数据结构与算法的概念
1.1 数据结构的概念
1.1.1 数据、数据元素与数据类型
1.1.2 数据结构的概念
1.1.3 抽象数据类型
1.2 算法的概念和描述
1.2.1 算法的概念
1.2.2 算法的描述
1.3 算法的时间复杂度和空间复杂度
1.3.1 算法的评价
1.3.2 算法的时间复杂度
1.3.3 算法的空间复杂度
习题1
第2章 线性表
2.1 线性表的概念和运算
2.1.1 线性表的概念
2.1.2 线性表的运算
2.2 顺序表
2.2.1 顺序表的概念
2.2.2 顺序表中基本运算的实现
2.3 链表
2.3.1 链表的基本结构
2.3.2 线性链表的操作
2.3.3 循环链表
2.3.4 双向链表
2.3.5 线性表存储方法的比较
2.4 广义表
2.4.1 广义表的概念和基本运算
2.4.2 广义表的存���表示与算法实现
2.4.3 广义表的应用
2.5 典型试题分析
习题2
第3章 栈和队列
3.1 栈
3.1.1 栈的概念
3.1.2 顺序栈
3.1.3 链接栈
3.1.4 栈的应用举例
3.2 队列
3.2.1 队列的概念
3.2.2 顺序队列
3.2.3 链接队列
3.2.4 循环队列
3.2.5 队列的应用举例
3.3 典型试题分析
习题3
第4章 数组、矩阵和串
4.1 数组的存储结构
4.1.1 一维数组的存储结构
4.1.2 二维数组的存储结构
4.1.3 n维数组的存储结构
4.2 矩阵的压缩存储
4.2.1 特殊矩阵的压缩存储
4.2.2 稀疏矩阵的压缩存储
4.3 串
4.3.1 串的基本概念
4.3.2 串的基本操作
4.3.3 串的存储结构
4.3.4 模式匹配
4.4 典型试题分析
习题4
第5章 树
5.1 树
5.1.1 树的定义及表示
5.1.2 树的常用术语
5.1.3 树的基本运算
5.1.4 树的存储结构
5.1.5 树的遍历
5.2 二叉树
5.2.1 二叉树的定义
5.2.2 二叉树的几种基本形态
5.2.3 二叉树的基本性质
5.2.4 二叉树的存储结构
5.2.5 二叉树的生成算法与遍历
5.2.6 二叉树的基本运算与实现
5.2.7 二叉树的算法举例
5.3 树、森林与二叉树的转换
5.4 线索二叉树
5.4.1 线索二叉树的概念
5.4.2 以中序线索链表为存储结构的中序遍历
5.4.3 以中序线索链表为存储结构的逆中序遍历
5.4.4 线索链表的生成
5.4.5 线索二叉树的操作实现
5.5 二叉树的应用
5.5.1 二叉排序树
5.5.2 哈夫曼树
5.6 典型试题分析
习题5
第6章 图
6.1 图的基本概念
6.1.1 图的定义
6.1.2 图的常用术语
6.1.3 图的基本操作
6.2 图的存储结构
6.2.1 邻接矩阵
6.2.2 邻接表与逆邻接表
6.2.3 邻接多重表
6.3 图的遍历
6.3.1 深度优先遍历
6.3.2 广度优先遍历
6.3.3 图的遍历的简单应用
6.4 无向连通图的*小生成树
6.4.1 *小生成树的概念
6.4.2 Prim算法
6.4.3 Kruskal算法
6.5 图的*短路径
6.5.1 单源*短路径
6.5.2 所有顶点对之间的*短路径
6.6 有向无环图及其应用
6.6.1 有向无环图的概念
6.6.2 AOV网与拓扑排序
6.6.3 AOE网与关键路径
6.7 典型试题分析
习题6
参考文献