数据结构

本书基于我们多年的教学经验，从实用的角度出发，对线性和非线性数据结构的顺序和链式存储及其操作进行了详细讲解。书中的每一章均配有实践练习及大量习题，实现了理论与实践相结合，让学生学以致用。本书免费提供电子课件、源程序及习题答案，全部案例均在Visual C++ 6.0环境中成功运行。
本书既可作为普通高校非计算机专业的计算机公共课教材、计算机类应用型本科及专科教材，也可作为计算机软件考试的很好教材。

第1章绪论1
1.1数据结构概述1
1.2常用术语和基本概念3
1.3数据类型6
1.3.1数据类型概述6
1.3.2抽象数据类型7
1.4算法和算法复杂度8
1.4.1算法的重要性9
1.4.2时间复杂度10
1.4.3空间复杂度12
1.5本章实战练习13
1.6本章小结15
1.7习题116
第2章线性表19
2.1线性表概述19
2.1.1线性表的定义及特点19
2.1.2线性表的抽象数据类型的定义20
2.2线性表的顺序存储及运算的实现21
2.2.1线性表的顺序存储21
2.2.2顺序表的基本操作22
2.3线性表的链式存储及运算的实现28
2.3.1单链表28
2.3.2循环链表37
2.3.3双向链表38
2.4本章实战练习41
2.4.1顺序表的常用操作41
2.4.2单链表的常用操作45
2.4.3通讯录管理47
2.5本章小结53
2.6习题254
第3章栈和队列59
3.1栈59
3.1.1栈的定义59
3.1.2栈的顺序存储与操作61
3.1.3栈的链式存储与操作65
3.2队列66
3.2.1队列的定义67
3.2.2队列的顺序存储与操作68
3.2.3队列的链式存储与操作71
3.3本章实战练习73
3.3.1top为指针且指向栈顶元素的下一个位置73
3.3.2top为整数且指向栈顶元素的下一个位置75
3.3.3栈的应用——数制转换77
3.3.4顺序队列的基本操作79
3.3.5循环队列设置不同队空与队满条件的解决方案82
3.3.6链队列的基本操作85
3.4本章小结88
3.5习题389
第4章串、数组、矩阵和广义表94
4.1串的定义95
4.1.1串的基本概念95
4.1.2串的抽象数据类型的定义96
4.2串的存储与操作97
4.2.1串的顺序存储与操作97
4.2.2串的链式存储与操作99
4.3数组100
4.3.1数组的定义100
4.3.2数组的顺序存储101
4.4矩阵的压缩存储102
4.4.1特殊矩阵的压缩存储102
4.4.2稀疏矩阵及其压缩存储105
4.5广义表111
4.5.1广义表的定义111
4.5.2广义表的存储结构及实现112
4.6本章实战练习114
4.6.1串的常见操作114
4.6.2串的基本操作及应用117
4.6.3数组应用——方阵126
4.6.4数组应用——稀疏矩阵126
4.7本章小结130
4.8习题4131
第5章树134
5.1树的概念134
5.1.1树的定义134
5.1.2树的基本术语135
5.2二叉树137
5.2.1二叉树的定义137
5.2.2二叉树的性质139
5.3二叉树的存储结构141
5.3.1二叉树的顺序存储141
5.3.2二叉树的链式存储与操作142
5.4二叉树的遍历145
5.4.1遍历算法145
5.4.2线索二叉树148
5.4.3遍历算法的应用举例152
5.5树与森林153
5.5.1树和森林的存储154
5.5.2二叉树、树和森林的转换157
5.5.3树和森林的遍历158
5.6哈夫曼树159
5.6.1哈夫曼树的定义159
5.6.2哈夫曼树的构造算法159
5.6.3哈夫曼编码161
5.7本章实战练习162
5.7.1二叉树的基本操作162
5.7.2线索二叉树的操作167
5.7.3树的应用——模拟资源管理器171
5.7.4哈夫曼树构造178
5.8本章小结180
5.9习题5180
第6章图189
6.1图的定义和基本术语189
6.1.1图的定义189
6.1.2图的基本术语190
6.2图的存储与操作194
6.2.1邻接矩阵194
6.2.2邻接表197
6.2.3十字链表200
6.3图的遍历201
6.3.1深度优先遍历算法202
6.3.2广度优先遍历算法204
6.4图与最小生成树206
6.4.1生成树和森林的算法206
6.4.2最小生成树208
6.5最短路径212
6.5.1单源点到其余各顶点的最短路径212
6.5.2任意源点之间的最短路径217
6.6AOV网与拓扑排序218
6.6.1AOV网219
6.6.2拓扑排序220
6.7AOE网与关键路径222
6.7.1AOE网222
6.7.2关键路径223
6.8本章实战练习226
6.8.1图的邻接矩阵操作226
6.8.2图的邻接表操作230
6.8.3利用邻接矩阵实现连通图的深度优先遍历234
6.8.4利用邻接表实现连通图的深度优先遍历237
6.8.5利用邻接矩阵实现连通图的广度优先遍历239
6.8.6利用邻接表实现连通图的广度优先遍历242
6.8.7普里姆最小生成树算法245
6.8.8迪杰斯特拉最短路径算法248
6.9本章小结251
6.10习题6251
第7章查找260
7.1查找的定义260
7.2静态查找算法262
7.2.1顺序查找262
7.2.2折半查找265
7.2.3分块查找268
7.3动态查找算法270
7.3.1二叉排序树270
7.3.2平衡二叉树275
7.4哈希表279
7.4.1哈希表的定义279
7.4.2哈希函数的构造280
7.4.3处理冲突的方法283
7.4.4哈希表的查找和性能285
7.5本章实战练习286
7.5.1顺序查找算法286
7.5.2折半查找算法287
7.5.3二叉排序树查找算法289
7.6本章小结291
7.7习题7292
第8章排序296
8.1排序的定义296
8.2插入排序算法297
8.2.1直接插入排序298
8.2.2折半插入排序299
8.2.3二路插入排序301
8.2.4表插入排序303
8.2.5希尔排序304
8.3交换排序算法305
8.3.1冒泡排序305
8.3.2快速排序306
8.4选择排序算法309
8.4.1直接选择排序309
8.4.2堆排序310
8.5归并排序算法314
8.6排序算法的比较316
8.7本章实战练习317
8.8本章小结322
8.9习题8323
参考文献327