第1章绪论1
1.1什么是数据结构1
1.2基本概念和
术语4
1.3抽象数据类型的表示与实现9
1.4算法和算法分析13
1.4.1算法13
1.4.2算法设计的要求13
1.4.3算法效率的度量14
1.4.4算法的存储空间需求17
第2章线性表18
2.1线性表的类型定义18
2.2线性表的顺序表示和实现21
2.3线性表的链式表示和实现27
2.3.1线性链表27
2.3.2循环链表35
2.3.3双向链表35
2.4一元多项式的表示及相加39
第3章栈和队列44
3.1栈44
3.1.1抽象数据类型栈的定义44
3.1.2栈的表示和实现45
3.2栈的应用举例48
3?2?1数制转换48
3?2?2括号匹配的检验49
3?2?3行编辑程序49
3?2?4迷宫求解50
3?2?5表达式求值52
**3.3栈与递归的实现54
3.4队列58
3.4.1抽象数据类型队列的定义58
3.4.2链队列——队列的链式表示和实现60
3.4.3循环队列——队列的顺序表示和实现63
**3.5离散事件模拟65
第4章串70
4.1串类型的定义70
4.2串的表示和实现72
4.2.1定长顺序存储表示73
4.2.2堆分配存储表示75
4?2?3串的块链存储表示78
**4?3串的模式匹配算法79
4.3.1求子串位置的定位函数Index(S,T,pos)79
4.3.2模式匹配的一种改进算法80
4.4串操作应用举例84
4.4.1文本编辑84
4.4.2建立词索引表86
第5章数组和广义表90
5.1数组的定义90
5.2数组的顺序表示和实现91
5.3矩阵的压缩存储95
5.3.1特殊矩阵95
5.3.2稀疏矩阵96
5.4广义表的定义106
5.5广义表的存储结构109
**5.6m元多项式的表示110
**5.7广义表的递归算法112
5.7.1求广义表的深度113
5.7.2复制广义表115.7.3建立广义表的存储结构115
第6章树和二叉树118
6.1树的定义和基本术语118
6.2二叉树121
6.2.1二叉树的定义121
6.2.2二叉树的性质123
6.2.3二叉树的存储结构126
6.3遍历二叉树和线索二叉树128
6.3.1遍历二叉树128
6.3.2线索二叉树132
6.4树和森林135
6.4.1树的存储结构135
6.4.2森林与二叉树的转换137
6.4.3树和森林的遍历138
**6.5树与等价问题139
6.6赫夫曼树及其应用144
6.6.1最优二叉树(赫夫曼树)144
