第1章绪论1
1.1学习数据结构的意义1
1.1.1引言1
1.1.2数据结构研究什么2
1.2数据结构的基本概念3
1.3算法及其描述4
1.3.1算法的概念和特性4
1.3.2算法设计的要求5
1.3.3算法的分析5
1.4小结7
1.5习题7
第2章线性表9
2.1线性表的定义及运算9
2.1.1线性表的定义9
2.1.2线性表的基本运算10
2.2顺序线性表11
2.2.1顺序存储的定义11
2.2.2顺序线性表的基本运算12
2.3线性表的链式存储结构14
2.3.1线性表链式存储结构的定义14
2.3.2单链表的定义15
2.3.3线性表链式存储结构代码描述15
2.3.4单链表的基本运算16
2.3.5单链表的创建20
2.4循环链表和双向链表22
2.4.1循环链表22
2.4.2双向链表23
2.5实训24
实训1随机生成5个数放入顺序表中,实现插入
和删除操作24实训2创建5个节点的单链表,随机生成5个数并放入单链表中,
实现插入和删除操作27
2.6小结33
2.7习题33
第3章栈和队列34
3.1栈的定义和基本运算34
3.1.1栈的定义34
3.1.2栈的基本运算35
3.2顺序栈35
3.2.1顺序栈存储的定义35
3.2.2顺序栈的基本运算36
3.3链栈39
3.3.1链栈的定义39
3.3.2链栈的基本运算39
3.4队列的定义和基本运算42
3.4.1队列的定义42
3.4.2队列的基本运算42
3.5顺序队列42
3.5.1顺序队列的存储结构42
3.5.2顺序队列的基本运算45
3.6链式队列49
3.6.1链式队列的存储结构49
3.6.2链式队列的基本运算50
3.7实训52
实训1顺序共享栈的简单实现52
实训2链式队列分队的简单实现54
3.8小结57
3.9习题57
第4章字符串59
4.1字符串的定义和基本运算59
4.1.1字符串的定义59
4.1.2字符串的基本运算60
4.2串的线性存储结构和基本运算的实现60
4.2.1串的赋值运算61
4.2.2求串的长度61
4.2.3判断两个串是否相等61
4.2.4求子串61
4.2.5串值的连接62
4.2.6插入子串62
4.2.7删除子串63
4.3串的模式匹配算法63
4.3.1BruteForce算法的设计思路63
4.3.2BruteForce算法的实现过程66
4.3.3BruteForce算法的时间复杂度66
4.4实训练习和掌握BruteForce算法66
4.5小结69
4.6习题69
第5章数组与矩阵71
5.1数组的基本概念71
5.1.1数组的定义71
5.1.2一维数组72
5.1.3二维数组72
5.1.4多维数组73
5.1.5数组的顺序存储结构73
5.2特殊矩阵的压缩存储74
5.2.1对称矩阵74
5.2.2三角矩阵75
5.2.3对角矩阵76
5.3稀疏矩阵76
5.3.1三元组顺序存储表77
5.3.2稀疏矩阵的赋值运算77
5.3.3稀疏矩阵的转置运算78
5.3.4稀疏矩阵的加法运算79
5.4实训二维数组的相加81
5.5小结84
5.6习题85
第6章树87
6.1树的相关知识87
6.1.1树的基本概念87
6.1.2树的表示方法88
6.1.3树的常用术语89
6.2树的基本操作90
6.3树的存储结构90
6.3.1双亲表示法90
6.3.2孩子表示法91
6.3.3孩子兄弟表示法93
6.4二叉树的定义和基本操作94
6.4.1二叉树的定义94
6.4.2二叉树的基本操作94
6.4.3二叉树的性质95
6.4.4二叉树的顺序存储结构96
6.4.5二叉树的链表存储结构98
6.5二叉树的遍历98
6.5.1二叉树的先根遍历方法99
6.5.2二叉树的中根遍历方法101
6.5.3二叉树的后根遍历方法102
6.5.4遍历序列与二叉树的结构103
6.6创建二叉树105
6.6.1用顺序存储方式创建二叉树105
6.6.2用链表方式创建二叉树106
6.7树、森林与二叉树的转换108
6.7.1一般树转换为二叉树108
6.7.2二叉树还原为一般树109
6.7.3森林转换为二叉树110
6.7.4二叉树还原为森林110
6.7.5树与森林的遍历111
6.8二叉树的应用——哈夫曼树111
6.8.1哈夫曼树的定义112
6.8.2哈夫曼树的构造113
6.8.3哈夫曼算法的实现114
6.8.4哈夫曼树的应用116
6.9实训创建二叉树并遍历117
6.10小结121
6.11习题121
第7章图123
7.1图的基本概念123
7.1.1图的定义123
7.1.2图的基本术语124
7.2图的存储结构126
7.2.1邻接矩阵的概念126
7.2.2建立图的邻接矩阵127
7.2.3邻接表128
7.3图的遍历131
7.3.1连通图的深度优先搜索132
7.3.2连通图的广度优先搜索133
7.3.3非连通图的遍历135
7.4最小生成树135
7.4.1生成树及最小生成树135
7.4.2普里姆算法136
7.4.3克鲁斯卡尔算法139
7.5最短路径140
7.5.1迪杰斯特拉算法141
7.5.2弗洛伊德(Floyd)算法147
7.6拓扑排序152
7.7实训邻接矩阵与遍历算法153
7.8小结162
7.9习题162
第8章查找164
8.1查找的相关定义164
8.2顺序查找算法164
8.2.1顺序查找描述165
8.2.2数据结构定义165
8.2.3典型算法与分析165
8.3折半查找算法166
8.3.1折半查找描述166
8.3.2折半查找分析166
8.3.3数据结构定义167
8.3.4典型算法与分析167
8.4分块查找168
8.4.1分块查找描述168
8.4.2分块查找分析169
8.4.3数据结构定义169
8.4.4典型算法与分析169
8.5二叉排序树查找169
8.5.1二叉排序树描述169
8.5.2二叉排序树分析170
8.5.3数据结构定义173
8.5.4典型算法与分析173
8.6哈希表查找173
8.6.1哈希表查找描述173
8.6.2哈希表查找分析174
8.6.3数据结构定义177
8.6.4典型算法与分析177
8.7实训应用各种查找算法178
8.8小结181
8.9习题181
第9章排序184
9.1插入排序184
9.1.1直接插入排序184
9.1.2希尔排序187
9.2交换排序188
9.2.1冒泡排序188
9.2.2快速排序189
9.3选择排序191
9.3.1直接选择排序191
9.3.2堆排序192
9.3.3归并排序198
9.4基数排序200
9.4.1多关键字排序200
9.4.2基数排序方法200
9.5实训实现不同的排序算法202
9.6小结210
9.7习题211
附录对应章节的Java代码215
习题答案258
参考文献271