第1章绪论 1
1.1什么是数据结构 1
目 录 1
1.1.1数据结构的定义 2
1.1.2数据结构类型 3
1.1.3数据结构和数据类型 4
1.2算法及其描述 5
1.2.1什么是算法 5
1.2.2算法描述 6
1.3算法分析 6
1.3.1时间复杂度 6
1.3.2空间复杂度 8
1.3.3算法分析实例 8
1.4本章小结 9
习题 9
2.1线性表及其逻辑结构 12
2.1.1线性表的定义 12
第2章线性表 12
2.1.2线性表的操作 13
2.2线性表的顺序存储结构 14
2.2.1线性表的顺序存储——顺序表 14
2.2.2顺序表基本操作的实现 15
2.2.3顺序表的应用举例 17
2.3线性表的链式存储 18
2.3.1线性表的链式存储——链表 18
2.3.2单链表基本操作的实现 19
2.4单向循环链表 24
2.5双向循环链表 25
2.5.1双向链表 25
2.5.2双向循环链表 25
2.6一元多项式的存储和运算 26
2.7单链表应用举例 29
2.8本章小结 30
习题 31
3.1 栈 33
3.1.1栈的定义和基本运算 33
第3章栈和队列 33
3.1.2栈的顺序存储及其基本操作的实现 34
3.1.3栈的链式存储及其基本操作的实现 37
3.1.4栈的应用举例 38
3.2队列 41
3.2.1队列的定义及运算 41
3.2.2队列的顺序存储及其基本操作的实现 42
3.2.3队列的链式存储及其基本操作的实现 45
3.3本章小结 46
习题 47
第4章串 49
4.1串及其操作 49
4.1.1串的逻辑结构 49
4.1.2串的基本运算 50
4.2串的存储结构 50
4.2.1顺序存储结构及其运算 51
4.2.2链式存储结构及基本运算的实现 52
4.3.1 BF（Brute-Force）算法 56
4.3串的模式匹配运算 56
4.3.2无回溯的模式匹配（KMP）算法 57
4.4本章小结 58
习题 59
第5章数组和广义表 61
5.1数组 61
5.1.1数组的定义 61
5.1.2数组的顺序存储结构 62
5.1.3数组的基本操作的实现 63
5.2.2稀疏矩阵的顺序存储结构及基本算法 64
5.2稀疏矩阵 64
5.2.1稀疏矩阵的定义 64
5.2.3稀疏矩阵的链式存储结构及基本算法 66
5.3广义表 69
5.3.1广义表的定义 69
5.3.2广义表存储结构 70
5.3.3广义表的基本操作 71
5.4本章小结 73
习题 73
6.1.1树的定义 75
第6章树 75
6.1树的定义和基本操作 75
6.1.2树的基本术语 76
6.1.3树的基本操作 77
6.2二叉树 77
6.2.1 二叉树的定义及其基本操作 77
6.2.2二叉树的重要性质 78
6.2.3二叉树的存储结构 80
6.3遍历二叉树 83
6.3.1二叉树遍历的递归算法 84
6.3.2二叉树遍历的非递归算法 86
6.4树和森林 87
6.4.1树的存储结构 87
6.4.2树与二叉树的转换 89
6.4.3森林与二叉树的转换图 90
6.5树的应用 91
6.5.1二叉排序树 91
6.5.2 合夫曼树 96
6.6本章小结 98
习题 99
第7章图 102
7.1图的基本概念 102
7.1.1图的定义 103
7.1.2图的基本术语 103
7.2图的存储结构 105
7.2.1邻接矩阵 105
7.2.2邻接表 106
7.3图的遍历 107
7.3.1深度优先遍历 108
7.3.2 广度优先遍历 110
7.4生成树 112
7.4.1概念 112
7.4.2最小生成树 112
7.5最短路径 117
7.5.1求某源点到其余各顶点的最短路径 117
7.5.2每对顶点之间的最短路径 119
7.6.1顶点活动网（AOV网） 120
7.6拓扑排序 120
7.6.2拓扑排序 121
7.7本章小结 123
习题 124
第8章排序 127
8.1插入排序 127
8.1.1直接插入排序 127
8.1.2希尔排序 128
8.2.1冒泡排序 129
8.2交换排序 129
8.2.2快速排序 130
8.3选择排序 132
8.4归并排序 133
8.5本章小结 135
习题 136
第9章查找 138
9.1线性表查找 138
9.1.1顺序查找 138
9.1.2折半查找 139
9.1.3分块查找 140
9.2哈希表查找 141
9.2.1哈希表定义 141
9.2.2哈希函数的构造 141
9.2.3哈希冲突解决办法 142
9.3本章小结 143
习题 144
10.1顺序表及其运算 146
第10章实验内容与上机指导 146
10.2链表及其运算 147
10.3栈的运算 151
10.4队列的运算 153
10.5串的运算 156
10.6二叉树的应用 157
10.7图的存储与遍历 161
10.8排序 165
10.9查找 167
主要参考文献 172