欢迎访问学兔兔,学习、交流 分享 !

返回首页 |

数据结构案例教程 C语言版 程海英 2020年版

收藏
  • 大小:157.41 MB
  • 语言:中文版
  • 格式: PDF文档
  • 阅读软件: Adobe Reader
资源简介
数据结构案例教程 C语言版
作者: 程海英
出版时间: 2020年版
内容简介
  数据结构是计算机和信息技术类等相关专业的一门重要的专业基础课程,数据结构及其处理算法是设计与实现系统软件和大型应用软件的重要基础,结合数据结构课程的现状和发展趋势,本教材具有难度适中、结构合理、应用性强的特点。
目录
第1 章 数据结构基础 .................................................................................... 1
1.1 数据结构的基本概念 .................................................................................................... 2
1.1.1 数据结构的研究内容 ......................................................................................... 2
1.1.2 基本概念和术语 ................................................................................................. 5
1.1.3 数据结构课程的内容 ......................................................................................... 8
1.2 数据类型和抽象数据类型 ............................................................................................ 9
1.2.1 数据类型 ............................................................................................................. 9
1.2.2 抽象数据类型 ..................................................................................................... 9
1.3 算法和算法分析 .......................................................................................................... 10
1.3.1 算法特性 ........................................................................................................... 11
1.3.2 算法描述 ........................................................................................................... 12
1.3.3 算法性能分析 ................................................................................................... 12
1.4 本章小结 ...................................................................................................................... 15
习题 ....................................................................................................................................... 16
编程实例 ............................................................................................................................... 18
第2 章 线性表 ............................................................................................. 19
2.1 线性表的定义 .............................................................................................................. 20
2.1.1 线性表的逻辑结构 ........................................................................................... 20
2.1.2 线性表的抽象数据类型 ................................................................................... 20
2.2 线性表的顺序存储及实现 .......................................................................................... 22
2.2.1 顺序表 ............................................................................................................... 22
2.2.2 顺序表的基本运算 ........................................................................................... 23
2.3 线性表的链式存储及实现 .......................................................................................... 28
vi | 数据结构案例教程(C 语言版)
2.3.1 单链表 ............................................................................................................... 29
2.3.2 单链表的基本运算 ........................................................................................... 30
2.3.3 循环链表 ........................................................................................................... 36
2.3.4 双向链表 ........................................................................................................... 37
2.3.5 静态链表 ........................................................................................................... 39
2.3.6 单链表应用举例 ............................................................................................... 40
2.4 顺序表与链表的比较 .................................................................................................. 43
2.5 本章小结 ...................................................................................................................... 44
习题 ....................................................................................................................................... 44
编程实例 ............................................................................................................................... 46
第3 章 栈和队列 ......................................................................................... 48
3.1 栈 .................................................................................................................................. 49
3.1.1 栈的定义 ........................................................................................................... 49
3.1.2 栈的表示和实现 ............................................................................................... 50
3.2 栈的应用 ...................................................................................................................... 55
3.2.1 数制转换问题 ................................................................................................... 56
3.2.2 括号匹配检验 ................................................................................................... 57
3.2.3 表达式求值 ....................................................................................................... 58
3.2.4 栈与递归 ........................................................................................................... 61
3.3 队列 .............................................................................................................................. 64
3.3.1 队列的定义 ....................................................................................................... 64
3.3.2 队列的表示和实现 ........................................................................................... 65
3.4 队列的应用 .................................................................................................................. 71
3.5 本章小结 ...................................................................................................................... 73
习题 ....................................................................................................................................... 74
编程实例 ............................................................................................................................... 75
第4 章 串 .................................................................................................... 79
4.1 串的定义和基本运算 .................................................................................................. 80
4.1.1 串的定义 ........................................................................................................... 80
4.1.2 串的基本操作 ................................................................................................... 81
4.2 串的存储结构 .............................................................................................................. 82
4.2.1 定长顺序存储 ................................................................................................... 82
4.2.2 堆存储 ............................................................................................................... 83
目 录 | vii
4.2.3 链式存储 ........................................................................................................... 85
4.3 串的运算实现 .............................................................................................................. 86
4.4 串的模式匹配 .............................................................................................................. 90
4.4.1 BF 算法 ............................................................................................................. 90
4.4.2 KMP 算法 ......................................................................................................... 92
4.5 本章小结 ...................................................................................................................... 95
习题 ....................................................................................................................................... 96
编程实例 ............................................................................................................................... 99
第5 章 数组和广义表 ................................................................................ 103
5.1 数组的定义及存储 .................................................................................................... 104
5.1.1 数组的定义 ..................................................................................................... 104
5.1.2 数组的基本操作 ............................................................................................. 105
5.1.3 数组的顺序存储 ............................................................................................. 105
5.2 特殊矩阵的压缩存储 ................................................................................................ 107
5.2.1 对称矩阵 ......................................................................................................... 108
5.2.2 三角矩阵 ......................................................................................................... 109
5.2.3 对角矩阵 ......................................................................................................... 110
5.3 稀疏矩阵 ..................................................................................................................... 111
5.3.1 稀疏矩阵的三元组表存储 .............................................................................. 111
5.3.2 稀疏矩阵的十字链表存储 ............................................................................. 115
5.4 广义表 ........................................................................................................................ 117
5.4.1 广义表的定义 ................................................................................................. 117
5.4.2 广义表的存储结构 ......................................................................................... 119
5.4.3 广义表的基本操作实现 ................................................................................. 121
5.5 本章小结 .................................................................................................................... 122
习题 ..................................................................................................................................... 123
编程实例 ............................................................................................................................. 124
第6 章 树和二叉树 .................................................................................... 127
6.1 树的定义与基本术语 ................................................................................................ 128
6.1.1 树的定义 ......................................................................................................... 128
6.1.2 树的基本术语 ................................................................................................. 131
6.2 二叉树 ........................................................................................................................ 131
6.2.1 二叉树的定义 ................................................................................................. 131
viii | 数据结构案例教程(C 语言版)
6.2.2 二叉树的性质 ................................................................................................. 134
6.2.3 二叉树的存储实现 ......................................................................................... 136
6.3 遍历二叉树 ................................................................................................................ 139
6.3.1 遍历二叉树的递归实现 ................................................................................. 139
6.3.2 遍历二叉树的非递归实现 ............................................................................. 141
6.3.3 遍历算法的应用 ............................................................................................. 145
6.4 线索二叉树 ................................................................................................................ 148
6.4.1 线索二叉树的基本概念 ................................................................................. 148
6.4.2 线索二叉树的运算实现 ................................................................................. 150
6.5 树和森林 .................................................................................................................... 153
6.5.1 树的存储结构 ................................................................................................. 153
6.5.2 树、森林与二叉树的转换 ............................................................................. 156
6.5.3 树和森林的遍历 ............................................................................................. 158
6.6 哈夫曼树及其应用 .................................................................................................... 159
6.6.1 哈夫曼树的基本概念 ..................................................................................... 159
6.6.2 构造哈夫曼树 ................................................................................................. 161
6.6.3 哈夫曼编码 ..................................................................................................... 163
6.7 本章小结 .................................................................................................................... 165
习题 ..................................................................................................................................... 166
编程实例 ............................................................................................................................. 168
第7 章 图 .................................................................................................. 172
7.1 图的定义与基本术语 ................................................................................................ 173
7.1.1 图的定义 ......................................................................................................... 173
7.1.2 基本术语 ......................................................................................................... 175
7.2 图的存储结构 ............................................................................................................ 177
7.2.1 邻接矩阵 ......................................................................................................... 177
7.2.2 邻接链表 ......................................................................................................... 179
7.2.3 十字链表 ......................................................................................................... 182
7.2.4 邻接多重表 ..................................................................................................... 183
7.3 图的遍历 .................................................................................................................... 184
7.3.1 深度优先搜索 ................................................................................................. 185
7.3.2 广度优先搜索 ................................................................................................. 187
7.4 图的应用 .................................................................................................................... 189
7.4.1 最小生成树 ..................................................................................................... 189
目 录 | ix
7.4.2 最短路径问题 ................................................................................................. 195
7.4.3 AOV 网与拓扑排序 ....................................................................................... 200
7.4.4 AOE 网与关键路径 ........................................................................................ 203
7.5 本章小结 .................................................................................................................... 208
习题 ..................................................................................................................................... 209
编程实例 ............................................................................................................................. 211
第8 章 查找 ............................................................................................... 216
8.1 查找的基本概念 ........................................................................................................ 217
8.2 线性表的查找 ............................................................................................................ 218
8.2.1 顺序查找 ......................................................................................................... 218
8.2.2 折半查找 ......................................................................................................... 219
8.2.3 分块查找 ......................................................................................................... 222
8.3 树表的查找 ................................................................................................................ 223
8.3.1 二叉排序树 ..................................................................................................... 223
8.3.2 平衡二叉树 ..................................................................................................... 229
8.3.3 B 树.................................................................................................................. 234
8.4 散列表的查找 ............................................................................................................ 241
8.4.1 散列表的基本概念 ......................................................................................... 241
8.4.2 散列函数的构造方法 ..................................................................................... 242
8.4.3 处理冲突的方法 ............................................................................................. 244
8.4.4 散列表的查找 ................................................................................................. 247
8.5 本章小结 .................................................................................................................... 248
习题 ..................................................................................................................................... 249
编程实例 ............................................................................................................................. 251
第9 章 排序 ............................................................................................... 254
9.1 排序的基本概念 ........................................................................................................ 255
9.1.1 什么是排序 ..................................................................................................... 255
9.1.2 排序的实现 ..................................................................................................... 256
9.2 插入排序 .................................................................................................................... 257
9.2.1 直接插入排序 ................................................................................................. 257
9.2.2 折半插入排序 ................................................................................................. 259
9.2.3 希尔排序 ......................................................................................................... 260
9.3 交换排序 .................................................................................................................... 261
x | 数据结构案例教程(C 语言版)
9.3.1 冒泡排序 ......................................................................................................... 261
9.3.2 快速排序 ......................................................................................................... 263
9.4 选择排序 .................................................................................................................... 266
9.4.1 简单选择排序 ................................................................................................. 266
9.4.2 堆排序 ............................................................................................................. 268
9.5 归并排序 .................................................................................................................... 273
9.6 基数排序 .................................................................................................................... 275
9.6.1 多关键字排序 ................................................................................................. 275
9.6.2 链式基数排序 ................................................................................................. 275
9.7 本章小结 .................................................................................................................... 279
习题 ..................................................................................................................................... 280
编程实例 ............................................................................................................................. 282
下载地址