出版说明 1
前言 1
第1章数据结构与程序 1
1.1数据结构在程序设计中的作用 1
目 录 1
1.2数据结构概述 2
1.2.1数据结构基本概念 2
1.3算法及其描述 3
1.3.1什么是算法 3
1.2.2数据结构分类 3
1.3.2算法的描述 4
1.3.3算法的复杂度 7
1.4 小结 7
1.5 实训 7
1.6习题 8
第2章线性表 10
2.1线性表的定义及运算 10
2.1.1线性表的定义 10
2.2.1顺序存储结构 11
2.1.2线性表的运算 11
2.2线性表的顺序存储及运算 11
2.2.2顺序存储结构下的运算 12
2.3线性表的链式存储及运算 14
2.3.1链式存储结构 14
2.3.2链式存储结构下的运算 15
2.4循环链表及双向链表 20
2.4.1循环链表 21
2.4.2双向链表 21
2.5线性表的应用 23
2.6小结 25
2.7 实训 26
2.8 习题 26
第3章数组与字符串 28
3.1数组的定义及存储 28
3.1.1数组的定义及运算 28
3.1.2数组的顺序存储结构 29
3.2矩阵的压缩存储 30
3.2.1特殊矩阵 30
3.2.2稀疏矩阵 33
3.3.1字符串的定义及运算 36
3.3.2字符串的存储结构 36
3.3字符串的存储及运算 36
3.3.3字符串运算的实现 37
3.4小结 38
3.5实训 38
3.6习题 38
4.1栈及其应用 40
4.1.1栈的定义及运算 40
第4章栈和队列 40
4.1.2栈的顺序存储结构 41
4.1.3栈的链式存储结构 44
4.1.4栈的应用 46
4.2队列及其应用 50
4.2.1队列的定义及运算 50
4.2.2队列的存储 51
4.2.3循环队列 56
4.2.4队列的应用 60
4.4实训 61
4.3小结 61
4.5习题 62
第5章查找技术 64
5.1基本概念 64
5.2线性表的查找 65
5.2.1顺序查找 65
5.2.2折半查找 67
5.2.3分块查找 70
5.3.1哈希表 72
5.3哈希表的查找 72
5.3.2哈希函数的构造方法 73
5.3.3处理冲突的方法 76
5.3.4哈希表的查找过程 78
5.4各种查找方法的比较 79
5.5查找算法举例 79
5.6小结 82
5.7实训 83
5.8习题 83
6.1基本概念 85
第6章排序技术 85
6.2插入排序 86
6.2.1直接插入排序 86
6.2.2折半插入排序 89
6.3交换排序 90
6.3.1冒泡排序 90
6.3.2快速排序 92
6.4选择排序 96
6.5归并排序 98
6.6各种内部排序算法的比较 99
6.7内部排序算法举例 100
6.8外部排序简介 103
6.9小结 103
6.10实训 104
6.11习题 104
第7章树形结构 106
7.1树的基本概念 106
7.1.1树的定义 106
7.1.2树的基本术语 107
7.2树的存储结构 108
7.2.1双亲表示法 108
7.2.2孩子表示法 109
7.2.3孩子兄弟表示法 110
7.3二叉树 110
7.3.1二叉树的定义和性质 110
7.3.2二叉树的存储结构 112
7.4二叉树的遍历 114
7.4.1二叉树的中根遍历 115
7.4.2二叉树的先根遍历 116
7.4.3二叉树的后根遍历 116
7.4.4二叉树操作实例 117
7.5线索树 119
7.5.1线索树的结构 119
7.5.2中根线索树的建立 120
7.5.3节点的检索 122
7.5.4节点的插入 123
7.6树、森林与二叉树的关系 125
7.7.1基本概念 126
7.7哈夫曼树及其应用 126
7.7.2哈夫曼树的构造 127
7.7.3哈夫曼编码 128
7.8二叉查找树 128
7.8.1二叉查找树的定义及其结构 129
7.8.2二叉查找树的建立 129
7.8.3在二叉查找树上进行查找 131
7.8.4在二叉查找树上删除节点 131
7.8.5二叉查找树的查找分析及评价 133
7.9.2堆的建立 134
7.9堆排序 134
7.9.1堆定义 134
7.9.3堆排序的实现 135
7.10小结 137
7.11实训 137
7.12习题 138
第8章图结构 141
8.1图的基本概念 141
8.2.1邻接矩阵 144
8.2图的存储结构 144
8.2.2邻接表 146
8.3图的遍历 148
8.3.1深度优先搜索 148
8.3.2广度优先搜索 150
8.4拓扑排序 153
8.4.1基本概念 154
8.4.2拓扑排序的实现 154
8.5.1从某一源点到其他各项点的最短路径 156
8.5最短路径 156
8.5.2图中任意两个顶点间的最短路径 158
8.6最小生成树 160
8.6.1基本概念 160
8.6.2普里姆算法 161
8.6.3克鲁斯卡尔算法 163
8.7关键路径 164
8.8 小结 166
8.9实训 167
8.10习题 167