数据结构

第1章 绪 论１
1．1 数据结构１
1．1．1 学习数据结构的重要性１
1．1．2 什么是数据结构３
1．1．3 数据的逻辑结构５
1．1．4 数据的存储结构１０
1．1．5 数据的运算１２
1．2 算法１３
1．2．1 什么是算法１３
1．2．2 算法的描述１３
1．2．3 算法设计１６
1．2．4 算法设计要求１８
1．2．5 算法分析１８
1．3 程序、程序设计与程序设计方法学２０
1．3．1 程序２０
1．3．2 程序设计２０
1．3．3 程序设计方法学２１
1．4 计算思维与抽象数据类型２３
1．4．1 计算思维２４
1．4．2 计算机求解问题２５
1．4．3 抽象数据类型２６
1．4．4 数据类型、数据结构与抽象数据类型２８
1．5 课程设计相关知识２８
1．5．1 课程设计目的与内涵２９
1．5．2 课程设计步骤２９
1．5．3 课程设计报告规范３０
课后练习与课程设计３０
第二章 线性表３２
2．1 线性表ADT３２
2．2 顺序表３３
2．2．1 向量的顺序存储表示３４
2．2．2 向量运算３５
2．2．3 应用举例４０
2．2．4 不等长结点的索引表示——目录表４３
2．3 链表４３
2．3．1 指针与指针对象４３
2．3．2 单链表４６
2．3．3 线性表的两种存储比较５８
2．3．4 可利用空间表及其管理５８
2．4 线性表的其它链接存储表示６０
2．4．1 循环链表６０
2．4．2 双向链表６１
2．4．3 静态链表６３
2．5 课程设计相关内容与应用示例６６
2．5．1 算法设计中的基本方法６６
2．5．2 一元多项式相乘６７
课后练习与课程设计７１
第3章 栈和队列74
3．1 栈ADT74
3．2 顺序栈75
3．2．1 顺序栈的存储表示75
3．2．2 顺序栈基本运算的实现76
3．3 链接栈79
3．3．1 链接栈的存储表示79
3．3．2 链接栈基本运算的实现80
3．4 栈的应用举例80
3．4．1 数制转换81
3．4．2 表达式求值82
3．5 队列ADT86
3．6 顺序队列87
3．6．1 顺序队列的存储表示87
3．6．2 顺序队列基本运算的实现87
3．7 链接队列90
3．7．1 链接队列的存储表示90
3．7．2 链接队列基本运算的实现91
3．8 随机事件模拟93
3．9 课程设计相关内容与应用示例96
3．9．1 递归概念96
3．9．2 递归过程设计98
3．9．3 递归过程与非递归过程98
课后练习与课程设计100
第4章 几种特殊线性表104
4．1 串104
4．1．1 串的基本概念104
4．1．2 串ADT105
4．1．3 串的存储表示107
4．1．4 串运算的实现109
4．2 数组111
4．2．1 数组ADT111
4．2．2 数组的顺序存储表示112
4．3 矩阵113
4．3．1 对称矩阵的压缩存储114
4．3．2 对角矩阵的压缩存储114
4．3．3 稀疏矩阵的三元组顺序表存储表示116
4．3．4 稀疏矩阵的十字链表存储表示117
4．3．5 稀疏矩阵的转置运算118
4．3．6 稀疏矩阵的插入运算120
4．4 广义表121
4．4．1 广义表的基本概念121
4．4．2 广义表ADT122
4．4．3 广义表的存储表示123
4．4．4 多元多项式的存储表示125
4．5 课程设计相关知识与应用示例127
4．5．1 梵天塔问题127
4．5．2 再谈递归过程设计128
4．5．3 求广义表的深度129
课后练习与课程设计131
第5章 内排序１３３
5．1 排序的基本概念１３３
5．2 直接插入排序１３４
5．3 直接选择排序１３６
5．4 冒泡排序１３８
5．5 希尔排序１４１
5．6 快速排序１４３
5．7 归并排序１４８
5．7．1 排序文件的归并１４８
5．7．2 2-路归并排序１４９
5．8 基数排序１５１
5．9 各种排序方法的比较１５４
5．10 课程设计相关知识与应用示例１５７
5．10．1 自顶向下设计技术与方法１５７
5．10．2 逐步求精设计技术与方法１５７
5．10．3 积木游戏１５８
课后练习与课程设计１６０
第6章 树和二叉树163
6．1 树的基本概念163
6．2 树的存储结构165
6．2．1 树的标准形式存储结构166
6．2．2 树的逆形式存储结构167
6．2．3 树的扩充标准形式存储结构167
6．2．4 树的双亲数组存储结构168
6．2．5 树的孩子链表存储结构169
6．2．6 树的三重链表存储结构170
6．3 树的遍历和树的线性表示171
6．3．1 树的前序遍历171
6．3．2 树的后序遍历173
6．3．3 树的层次遍历174
6．3．4 树的线性表示176
6．4 二叉树177
6．4．1 二叉树定义和二叉树ADT177
6．4．2 二叉树的性质179
6．4．3 二叉树与树（或森林）之间的转换180
6．4．4 二叉树的存储表示183
6．5 二叉树遍历186
6．5．1 二叉树遍历187
6．5．2 由遍历序列构造二叉树197
6．5．3基于二叉树遍历操作的算法举例198
6．6 线索二叉树200
6．6．1 线索二叉树201
6．6．2 线索二叉树的利用202
6．6．3 二叉树的线索化205
6．7 哈夫曼树及其应用206
6．7．1 二叉树的路径长度和带权路径长度206
6．7．2 哈夫曼树和哈夫曼算法208
6．7．3 哈夫曼树的应用210
6．8 课程设计相关知识与应用示例216
6．8．1 结构化方法概述216
6．8．2 模块化设计技术与方法217
6．8．3 模块化应用示例218
课后练习与课程设计220
第七章 图223
7．1 图的基本概念223
7．2 图的存储结构227
7．2．1 邻接矩阵227
7．2．2 邻接表229
7．3 图的遍历231
7．3．1 深度优先搜索法232
7．3．2 广度优先搜索法233
7．3．3 求图的（强）连通分量235
7．4 生成树与最小生成树235
7．4．1 生成树概念235
7．4．2 最小生成树236
7．5 最短路径240
7．5．1 单源最短路径241
7．5．2 每一对顶点间的最短路径245
7．6 拓扑排序247
7．6．1 AOV网247
7．6．2 拓扑排序248
7．7 关键路径250
7．7．1 AOE网250
7．7．2 关键路径250
7．8 课程设计相关知识与应用示例254
7．8．1 递推算法254
7．8．2 分治法概述255
7．8．3 数字旋转方阵255
课后练习与课程设计258
第8章 查 找262
8．1 线性表查找262
8．1．1 顺序查找262
8．1．2 折半查找264
8．1．3 分块查找266
8．2 树型结构查找267
8．2．1 二叉排序树267
8．2．2 平衡查找树271
8．2．3 B树和B+树278
8．2．4 堆排序284
8．3 哈希表及其查找286
8．3．1 哈希表286
8．3．2 哈希函数构造方法287
8．3．3 解决冲突方法290
8．3．4 哈希表查找292
8．4 课程设计相关知识与应用示例294
8．4．1 动态规划法概述294
8．4．2 贪心法概述295
8．4．3 背包问题296
课后练习与课程设计298
第9章 文件与外部排序301
9．1 文件概述301
9．2 文件组织302
9．2．1 顺序文件302
9．2．2 索引文件303
9．2．3 哈希文件305
9．2．4 多关键字文件306
9．3 外部排序308
9．3．1 2-路平衡归并排序法308
9．3．2 多路平衡归并排序法310
9．3．3 置换-选择排序312
9．3．4 最优归并树316
9．4 课程设计相关知识与应用示例317
9．4．1 回溯法概述317
9．4．2 分支限界法概述319
9．4．3 数据结构课程设计示例321
课后练习与课程设计322
参考文献324