计算机数据结构讲义
目 录
第一章 线性表 5
1.1 线性表的逻辑结构. 5
1.2 线性表的顺序存储结构 8
1.3 线性表的链式存储结构 12
小结：顺序表和链表的比较 . 18
本章小结. 19
本章同步练习. 19
历年真题解析. 25
第二章 栈、队列、数组. 30
2.1 栈的类型定义. 30
2.2 栈的应用举例. 30
2.3 栈类型的实现. 34
2.4 队列的类型定义. 35
2.5 队列类型的实现. 36
2.7 数组的顺序表示和实现. 39
2.8 矩阵的压缩存储. 39
本章小结. 40
本章同步练习. 41
历年真题解析. 44
第三章 树和二叉树 46
3.1 树的类型定义. 46
3.2 二叉树的类型定义. 47
3.3 二叉树的存储结构. 50
3.4 二叉树的遍历 51
3.5 线索二叉树. 61
3.6 树和森林的表示方法. 64
3.7 树和森林的遍历. 68
3.8 哈夫曼树与哈夫曼编码. 70
本章小结. 71
本章同步练习. 72
本章真题解析. 74
第四章 图 78
4.1 图的有关定义 78
4.2 图的存储表示. 80
4.3 图的遍历 82
4.4 (连通网的)最小生成树. 85
4.5 拓扑排序 88
4.6 关键路径 89
本章小结. 92
本章同步练习. 92
历年真题解析. 95
第五章 查找 98
5.1 静态查找表. 98
5.2 动态查找树表. 101
5.3 散列表 109
一、散列表是什么？ . 109
二、构造散列函数的方法 . 110
三、处理冲突的方法 . 111
四、散列表的查找 . 112
五、散列表的删除操作 . 113
六、散列表也可以用来构造静态查找表。 . 113
本章要点. 113
本章同步练习. 113
本章真题解析. 116
第6章 排序 119
6.1 排序的基本概念. 119
6.2 插入类排序. 119
6.2.1 直接插入排序 . 119
6.2.2 折半插入排序 . 121
6.2.3 希尔排序. 121
6.3 交换类排序法. 121
6.3.1 冒泡排序（相邻比序法） . 122
6.3.2 快速排序. 122
6.4 选择类排序法. 124
6.4.1 简单选择排序 . 124
6.4.2 堆排序. 124
本章小结. 129
本章同步练习. 129