数据结构(面向信息学竞赛)

数据结构(面向信息学竞赛)
分享
扫描下方二维码分享到微信
打开微信,点击右上角”+“,
使用”扫一扫“即可将网页分享到朋友圈。
作者:
出版社: 科学出版社
2021-08
版次: 1
ISBN: 9787030696519
定价: 59.00
装帧: 平装
开本: 16开
纸张: 胶版纸
页数: 247页
  • 《数据结构(面向信息学竞赛)》是为教育技术学专业“数据结构”课程编写的教材,《数据结构(面向信息学竞赛)》详细介绍了各类常用数据结构的概念、实现和应用,以及各种常见排序、查找和动态规划算法。同时,针对本专业学生就业后指导中学生信息学奥林匹克竞赛的实际需求,在各章节中加入了对应C++ STL的介绍,以及利用数据结构和算法知识解决信息学竞赛题目的内容。《数据结构(面向信息学竞赛)》使用C++语言作为代码实现语言。 目录 

    教育技术学专业主干课程系列教材总序 

    序 

    前言 

    第1章 概述 1 

    1.1 数据结构 2 

    1.1.1 数据与数据结构的定义 2 

    1.1.2 逻辑结构、物理结构和抽象数据类型 3 

    1.2 算法与算法分析 5 

    1.2.1 算法 5 

    1.2.2 算法的性质和判断算法优劣的标准 5 

    1.2.3 算法分析 7 

    1.3 全国青少年信息学奥林匹克联赛简介 10 

    1.4 C++ STL简介 11 

    习题 12 

    第2章 线性表 13 

    2.1 顺序表 13 

    2.1.1 顺序表的基本概念 13 

    2.1.2 顺序表的实现 14 

    2.1.3 顺序表操作的时间复杂度 19 

    2.2 C++ STL中顺序表的用法 19 

    2.3 信息学竞赛中顺序表的应用 21 

    2.4 单链表 26 

    2.4.1 链表的基本概念 26 

    2.4.2 链表的实现 28 

    2.4.3 链表操作的时间复杂度 32 

    2.5 循环链表、双向链表和静态链表 32 

    2.5.1 循环链表 32 

    2.5.2 双向链表 33 

    2.5.3 静态链表 35 

    2.6 C++ STL中链表的用法 36 

    2.7 信息学竞赛中链表的应用 37 

    习题 39 

    第3章 栈与队列 40 

    3.1 栈 40 

    3.1.1 栈的基本概念 40 

    3.1.2 顺序栈的实现 41 

    3.2 C++ STL中栈的用法 42 

    3.3 信息学竞赛中栈的应用 42 

    3.4 队列 48 

    3.4.1 队列的基本概念 48 

    3.4.2 链式队列的实现 51 

    3.5 C++ STL中队列的用法 52 

    3.5.1 队列queue的用法 52 

    3.5.2 优先级队列priority_queue的用法 52 

    3.6 信息学竞赛中队列的应用 54 

    习题 57 

    第4章 递归 59 

    4.1 基本概念与用法 59 

    4.1.1 递归的基本概念 59 

    4.1.2 递归的特点 61 

    4.2 递归与栈的关系 61 

    4.3 递归算法 63 

    4.3.1 穷举法 63 

    4.3.2 分治法 65 

    4.3.3 回溯法 70 

    4.4 信息学竞赛中递归的应用 74 

    习题 78 

    第5章 串 79 

    5.1 串的基本概念 79 

    5.2 串的存储结构 80 

    5.2.1 串的顺序存储 80 

    5.2.2 串的链式存储 85 

    5.3 串的模式匹配算法 85 

    5.3.1 Brute-Force算法 85 

    5.3.2 KMP算法 87 

    5.4 C++ STL中字符串的用法 91 

    5.4.1 string的头文件、定义与初始化 91 

    5.4.2 string的基本操作 91 

    5.5 信息学竞赛中字符串的应用 93 

    习题 95 

    第6章 树 97 

    6.1 树的基本概念 97 

    6.2 二叉树 98 

    6.2.1 二叉树的基本概念与性质 98 

    6.2.2 二叉树遍历 101 

    6.3 哈夫曼树 108 

    6.3.1 变长编码 108 

    6.3.2 哈夫曼树与哈夫曼编码 110 

    6.4 树与森林 115 

    6.4.1 树与森林的表示方法 115 

    6.4.2 等价类问题与并查集算法 118 

    6.5 信息学竞赛中树的应用 121 

    习题 123 

    第7章 图 125 

    7.1 图的基本概念 125 

    7.1.1 图的定义 125 

    7.1.2 图的基本术语 125 

    7.2 图的存储方法 127 

    7.2.1 邻接矩阵存储方法 127 

    7.2.2 邻接表存储方法 129 

    7.3 图的遍历 131 

    7.3.1 深度优先搜索遍历 131 

    7.3.2 广度优先搜索遍历 132 

    7.3.3 非连通图的遍历 133 

    7.4 *小生成树问题 134 

    7.4.1 生成树 134 

    7.4.2 *小生成树 135 

    7.4.3 普里姆算法 135 

    7.4.4 克鲁斯卡尔算法 139 

    7.5 *短路径问题 140 

    7.5.1 单源*短路径 140 

    7.5.2 任意两点间的*短路径 144 

    7.6 拓扑排序 147 

    7.7 信息学竞赛中图的应用 149 

    习题 154 

    第8章 排序 156 

    8.1 冒泡排序 156 

    8.1.1 冒泡排序算法 156 

    8.1.2 冒泡排序的时间复杂度 159 

    8.2 插入排序 159 

    8.2.1 插入排序算法 159 

    8.2.2 插入排序的时间复杂度 161 

    8.3 归并排序 161 

    8.3.1 归并排序算法 161 

    8.3.2 归并排序的时间复杂度 163 

    8.4 快速排序 165 

    8.4.1 快速排序算法 165 

    8.4.2 快速排序的时间复杂度 167 

    8.5 堆排序 170 

    8.5.1 堆的概念与建立堆的方法 170 

    8.5.2 堆排序算法 174 

    8.5.3 堆排序的时间复杂度 175 

    8.6 比较排序算法的实质 175 

    8.7 基数排序 177 

    8.7.1 线性时间排序算法 177 

    8.7.2 基数排序算法 178 

    8.7.3 链式基数排序算法 179 

    8.8 各种排序算法复杂度比较 181 

    8.9 C++ STL中排序算法的用法 182 

    8.9.1 几种常用的STL sort算法函数简介 182 

    8.9.2 sort函数使用方法 183 

    8.10 信息学竞赛中排序的应用 184 

    习题 188 

    第9章 查找 189 

    9.1 二分查找法 189 

    9.1.1 二分查找法的实现 189 

    9.1.2 C++ STL中二分查找的用法 191 

    9.2 哈希表 193 

    9.2.1 哈希函数 194 

    9.2.2 开放定址法 195 

    9.2.3 链地址法 198 

    9.2.4 哈希表的时间复杂度 199 

    9.2.5 C++ STL中哈希表的用法 201 

    9.3 查找树 203 

    9.3.1 二叉查找树 203 

    9.3.2 红黑树 210 

    9.3.3 C++ STL中二叉查找树的用法 217 

    9.4 信息学竞赛中查找的应用 219 

    习题 223 

    第10章 动态规划 225 

    10.1 动态规划基础 225 

    10.2 背包问题 230 

    10.3 区间动态规划 234 

    10.4 信息学竞赛中动态规划的应用 238 

    习题 244 

    习题参考答案或提示 245 

    参考文献 248
  • 内容简介:
    《数据结构(面向信息学竞赛)》是为教育技术学专业“数据结构”课程编写的教材,《数据结构(面向信息学竞赛)》详细介绍了各类常用数据结构的概念、实现和应用,以及各种常见排序、查找和动态规划算法。同时,针对本专业学生就业后指导中学生信息学奥林匹克竞赛的实际需求,在各章节中加入了对应C++ STL的介绍,以及利用数据结构和算法知识解决信息学竞赛题目的内容。《数据结构(面向信息学竞赛)》使用C++语言作为代码实现语言。
  • 目录:
    目录 

    教育技术学专业主干课程系列教材总序 

    序 

    前言 

    第1章 概述 1 

    1.1 数据结构 2 

    1.1.1 数据与数据结构的定义 2 

    1.1.2 逻辑结构、物理结构和抽象数据类型 3 

    1.2 算法与算法分析 5 

    1.2.1 算法 5 

    1.2.2 算法的性质和判断算法优劣的标准 5 

    1.2.3 算法分析 7 

    1.3 全国青少年信息学奥林匹克联赛简介 10 

    1.4 C++ STL简介 11 

    习题 12 

    第2章 线性表 13 

    2.1 顺序表 13 

    2.1.1 顺序表的基本概念 13 

    2.1.2 顺序表的实现 14 

    2.1.3 顺序表操作的时间复杂度 19 

    2.2 C++ STL中顺序表的用法 19 

    2.3 信息学竞赛中顺序表的应用 21 

    2.4 单链表 26 

    2.4.1 链表的基本概念 26 

    2.4.2 链表的实现 28 

    2.4.3 链表操作的时间复杂度 32 

    2.5 循环链表、双向链表和静态链表 32 

    2.5.1 循环链表 32 

    2.5.2 双向链表 33 

    2.5.3 静态链表 35 

    2.6 C++ STL中链表的用法 36 

    2.7 信息学竞赛中链表的应用 37 

    习题 39 

    第3章 栈与队列 40 

    3.1 栈 40 

    3.1.1 栈的基本概念 40 

    3.1.2 顺序栈的实现 41 

    3.2 C++ STL中栈的用法 42 

    3.3 信息学竞赛中栈的应用 42 

    3.4 队列 48 

    3.4.1 队列的基本概念 48 

    3.4.2 链式队列的实现 51 

    3.5 C++ STL中队列的用法 52 

    3.5.1 队列queue的用法 52 

    3.5.2 优先级队列priority_queue的用法 52 

    3.6 信息学竞赛中队列的应用 54 

    习题 57 

    第4章 递归 59 

    4.1 基本概念与用法 59 

    4.1.1 递归的基本概念 59 

    4.1.2 递归的特点 61 

    4.2 递归与栈的关系 61 

    4.3 递归算法 63 

    4.3.1 穷举法 63 

    4.3.2 分治法 65 

    4.3.3 回溯法 70 

    4.4 信息学竞赛中递归的应用 74 

    习题 78 

    第5章 串 79 

    5.1 串的基本概念 79 

    5.2 串的存储结构 80 

    5.2.1 串的顺序存储 80 

    5.2.2 串的链式存储 85 

    5.3 串的模式匹配算法 85 

    5.3.1 Brute-Force算法 85 

    5.3.2 KMP算法 87 

    5.4 C++ STL中字符串的用法 91 

    5.4.1 string的头文件、定义与初始化 91 

    5.4.2 string的基本操作 91 

    5.5 信息学竞赛中字符串的应用 93 

    习题 95 

    第6章 树 97 

    6.1 树的基本概念 97 

    6.2 二叉树 98 

    6.2.1 二叉树的基本概念与性质 98 

    6.2.2 二叉树遍历 101 

    6.3 哈夫曼树 108 

    6.3.1 变长编码 108 

    6.3.2 哈夫曼树与哈夫曼编码 110 

    6.4 树与森林 115 

    6.4.1 树与森林的表示方法 115 

    6.4.2 等价类问题与并查集算法 118 

    6.5 信息学竞赛中树的应用 121 

    习题 123 

    第7章 图 125 

    7.1 图的基本概念 125 

    7.1.1 图的定义 125 

    7.1.2 图的基本术语 125 

    7.2 图的存储方法 127 

    7.2.1 邻接矩阵存储方法 127 

    7.2.2 邻接表存储方法 129 

    7.3 图的遍历 131 

    7.3.1 深度优先搜索遍历 131 

    7.3.2 广度优先搜索遍历 132 

    7.3.3 非连通图的遍历 133 

    7.4 *小生成树问题 134 

    7.4.1 生成树 134 

    7.4.2 *小生成树 135 

    7.4.3 普里姆算法 135 

    7.4.4 克鲁斯卡尔算法 139 

    7.5 *短路径问题 140 

    7.5.1 单源*短路径 140 

    7.5.2 任意两点间的*短路径 144 

    7.6 拓扑排序 147 

    7.7 信息学竞赛中图的应用 149 

    习题 154 

    第8章 排序 156 

    8.1 冒泡排序 156 

    8.1.1 冒泡排序算法 156 

    8.1.2 冒泡排序的时间复杂度 159 

    8.2 插入排序 159 

    8.2.1 插入排序算法 159 

    8.2.2 插入排序的时间复杂度 161 

    8.3 归并排序 161 

    8.3.1 归并排序算法 161 

    8.3.2 归并排序的时间复杂度 163 

    8.4 快速排序 165 

    8.4.1 快速排序算法 165 

    8.4.2 快速排序的时间复杂度 167 

    8.5 堆排序 170 

    8.5.1 堆的概念与建立堆的方法 170 

    8.5.2 堆排序算法 174 

    8.5.3 堆排序的时间复杂度 175 

    8.6 比较排序算法的实质 175 

    8.7 基数排序 177 

    8.7.1 线性时间排序算法 177 

    8.7.2 基数排序算法 178 

    8.7.3 链式基数排序算法 179 

    8.8 各种排序算法复杂度比较 181 

    8.9 C++ STL中排序算法的用法 182 

    8.9.1 几种常用的STL sort算法函数简介 182 

    8.9.2 sort函数使用方法 183 

    8.10 信息学竞赛中排序的应用 184 

    习题 188 

    第9章 查找 189 

    9.1 二分查找法 189 

    9.1.1 二分查找法的实现 189 

    9.1.2 C++ STL中二分查找的用法 191 

    9.2 哈希表 193 

    9.2.1 哈希函数 194 

    9.2.2 开放定址法 195 

    9.2.3 链地址法 198 

    9.2.4 哈希表的时间复杂度 199 

    9.2.5 C++ STL中哈希表的用法 201 

    9.3 查找树 203 

    9.3.1 二叉查找树 203 

    9.3.2 红黑树 210 

    9.3.3 C++ STL中二叉查找树的用法 217 

    9.4 信息学竞赛中查找的应用 219 

    习题 223 

    第10章 动态规划 225 

    10.1 动态规划基础 225 

    10.2 背包问题 230 

    10.3 区间动态规划 234 

    10.4 信息学竞赛中动态规划的应用 238 

    习题 244 

    习题参考答案或提示 245 

    参考文献 248
查看详情
相关图书 / 更多
数据结构(面向信息学竞赛)
数据挖掘技术与应用
由育阳 著
数据结构(面向信息学竞赛)
数据结构(用面向对象方法与C++语言描述第3版清华大学计算机系列教材)
殷人昆 编
数据结构(面向信息学竞赛)
数据结构精深解读(2022)/计算机考研精深解读系列
研芝士计算机考研命题研究中心 编
数据结构(面向信息学竞赛)
数据安全法一本通(第八版)
法规应用研究中心
数据结构(面向信息学竞赛)
数据结构实验教程(微课版)
王彤;杨雷;鲍玉斌;张立立
数据结构(面向信息学竞赛)
数据挖掘在经济、社会中的作用
张维朋;徐颖;伍婵提
数据结构(面向信息学竞赛)
数据资产管理(初级融媒体版1+X数据资产管理职业技能等级证书配套教材)
钱晖、董海峰、纪明欣 编
数据结构(面向信息学竞赛)
数据库应用(MySQL)
田春尧、魏玉书 编
数据结构(面向信息学竞赛)
数据资源规划与管理实践
陈刚
数据结构(面向信息学竞赛)
数据库系统概念 (本科教学版·原书第7版)
[美]亚伯拉罕·西尔伯沙茨;[美]亨利·F. 科思;[印]S. 苏达尔尚
数据结构(面向信息学竞赛)
数据驱动分析技术在页岩油气藏中的应用
于荣泽 译
数据结构(面向信息学竞赛)
数据结构、算法及应用(第2版)
张宪超