全书共分8章, 围绕线性表、栈、队列、串、矩阵、广义表、树、二叉树、图等常用的数据结构, 介绍了基本概念、逻辑结构、存储结构、操作运算以及实现算法、案例应用; 还介绍了多种常用的查找算法和排序算法, 并对各种算法的性能进行分析。

　　前言
　　数据结构在计算机科学中是一门综合性的专业基础课，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。目前比较权威的数据结构教材大多是考研指定教材，难度比较大，不太适合应用型本科、三本及专科学生使用。为此，我们编写了这本教材，通过引入大量案例，将复杂的理论问题直观化，案例驱动式教学，更有利于这个层次的学生接受。
　　我们基于多年的丰富的教学经验及素材积累，精心编写此书，目的是让初学者能循序渐进地掌握各种数据结构及操作，力求透彻、全面、易学、易用，充分调动学生的学习积极性。书中使用C语言定义各种数据结构、描述算法。本书对每种数据结构和算法的剖析都遵循由浅入深的原则，并配以实用的案例和图示，配有相应的C语言源代码，适合具有C语言基础的数据结构初学者。
　　全书共分8章，对于常用的数据结构，如线性表、栈、队列、串、矩阵、广义表、树、二叉树、图等进行深入讲解，使读者能够全面地理解基本概念、逻辑结构、存储结构、操作运算、实现算法以及案例应用，进而利用比较法讲解各种查找和排序的方法，并对各种算法的性能进行分析，以便在不同的应用场合选取合适的方法。
　　本书由梁海英博士和王凤领教授任主编，谭晓东、巫湘林、张波和胡元闯任副主编，全书由贺州学院梁海英教授统稿。在本书编写过程中，得到了所在学院的同事的热心帮助和支持，参加本书内容编写、程序调试、课件制作、习题收集、答案制作、内容审校等工作的老师有赵方珍、罗兰花、李立信、千文、黄华升、陈冠萍、袁淑丹等，在此向他们表示衷心的感谢！
　　由于水平有限，书中难免存在不妥之处，敬请读者谅解，并提出宝贵意见。我们的电话是010-62796045，信箱是huchenhao@263.net。
　　本书对应的电子课件、习题答案和源代码可以到http://www.tupwk.com.cn网站下载。
　　编者
　　2017年5月

目录
第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