本书以专业基础能力培养为目标，承续计算机程序设计基础课程，完全遵照教育部计算机科学与技术教学指导委员会关于《高等学校计算机专业人才专业能力构成与培养》的要求编写而成，旨在培养学生的基本计算思维能力，提高学生的算法设计和程序实现能力，并为学生提高系统开发能力打下良好的基础。全书共分10章，主要介绍了数据结构基本概念与基本知识、线性表及其基本操作、栈和队列、字符串、数组和广义表、树与二叉树的概念和应用、图、查找和排序。本书可以作为计算机科学与技术及相关专业本科生的教材，也可以作为计算机专业考研(硕士、工程硕士、博士)的复习教材，还可以供使用计算机进行系统开发的人员学习使用。

目录
前言
教学建议
第1章　绪论1
　1.1　数据结构的概念及分类1
　　1.1.1　为什么要学习数据结构1
　　1.1.2　与数据结构相关的基本术语2
　　1.1.3　数据结构的分类4
　　1.1.4　数据结构的存储结构6
　　1.1.5　定义在数据结构上的操作7
　1.2　使用C语言描述数据结构7
　　1.2.1　数据类型7
　　1.2.2　算法的控制结构8
　　1.2.3　算法的函数结构9
　　1.2.4　动态存储分配12
　　1.2.5　逻辑和关系运算的约定12
　　1.2.6　输入与输出13
　1.3　算法和算法设计13
　　1.3.1　算法的定义和特性13
　　1.3.2　算法的设计步骤14
　　1.3.3　算法设计的基本方法15
　1.4　算法分析与度量19
　　1.4.1　算法的评价标准19
　　1.4.2　算法的时间和空间复杂度度量20
　　1.4.3　算法的渐近分析23
　小结25
　习题25
第2章　线性表27
　2.1　概述27
　　2.1.1　线性表的定义和特点27
　　2.1.2　线性表的主要操作28
　2.2　顺序表29
　　2.2.1　顺序表的定义和特点29
　　2.2.2　顺序表的结构定义30
　　2.2.3　顺序表主要操作的实现31
　　2.2.4　顺序表主要操作的性能分析32
　　2.2.5　顺序表的应用举例33
　2.3　单链表34
　　2.3.1　单链表的定义和特点34
　　2.3.2　单链表的结构定义35
　　2.3.3　单链表中的插入与删除36
　　2.3.4　带头结点的单链表38
　　2.3.5　单链表的顺序访问与尾递归40
　　2.3.6　单链表的应用举例42
　　2.3.7　循环单链表44
　　2.3.8　双向链表47
　　2.3.9　静态链表51
　2.4　顺序表与单链表的比较52
　2.5　单链表的应用：一元多项式及其运算53
　　2.5.1　一元多项式的表示53
　　2.5.2　多项式的结构定义54
　　2.5.3　多项式的加法56
　　2.5.4　多项式的乘法57
　小结59
　习题59
第3章　栈和队列62
　3.1　栈62
　　3.1.1　栈的概念62
　　3.1.2　顺序栈63
　　3.1.3　链式栈67
　　3.1.4　栈的混洗69
　3.2　队列70
　　3.2.1　队列的概念71
　　3.2.2　循环队列72
　　3.2.3　链式队列75
　3.3　栈的应用77
　　3.3.1　数制转换77
　　3.3.2　括号匹配78
　　3.3.3　表达式的计算与优先级处理79
　　3.3.4　栈与递归的实现84
　3.4　队列的应用87
　　3.4.1　打印杨辉三角形与逐行处理87
　　3.4.2　电路布线与两点间的最短路径89
　3.5　在算法设计中使用递归91
　　3.5.1　汉诺塔问题与分治法91
　　3.5.2　迷宫问题与回溯法94
　3.6　双端队列96
　　3.6.1　双端队列的概念97
　　3.6.2　输入受限的双端队列97
　　3.6.3　输出受限的双端队列98
　　3.6.4　双端队列的存储表示98
　3.7　优先队列100
　　3.7.1　优先队列的概念100
　　3.7.2　优先队列的实现100
　小结101
　习题102
第4章　字符串105
　4.1　字符串的概念105
　　4.1.1　字符串的基本概念105
　　4.1.2　字符串的初始化和赋值106
　　4.1.3　C语言中有关字符串的库函数107
　　4.1.4　字符串的自定义操作108
　4.2　字符串的实现109
　　4.2.1　定长顺序存储表示109
　　4.2.2　堆分配存储表示110
　　4.2.3　块链存储表示112
　4.3　字符串的模式匹配113
　　4.3.1　BF模式匹配算法113
　　4.3.2　无回溯的KMP模式匹配算法114
　　4.3.3　BM模式匹配算法119
　小结121
　习题121
第5章　多维数组和广义表123
　5.1　数组123
　　5.1.1　一维数组123
　　5.1.2　多维数组125
　5.2　特殊矩阵126
　　5.2.1　对称矩阵的压缩存储127
　　5.2.2　三对角矩阵的压缩存储128
　　5.2.3　w对角矩阵的压缩存储129
　5.3　稀疏矩阵130
　　5.3.1　稀疏矩阵的概念130
　　5.3.2　稀疏矩阵的顺序存储表示130
　　5.3.3　稀疏矩阵的链接存储表示137
　5.4　广义表140
　　5.4.1　广义表的概念140
　　5.4.2　广义表的性质141
　　5.4.3　广义表的头尾表示法142
　　5.4.4　广义表的扩展线性链表表示145
　　5.4.5　广义表的层次表示法146
　　5.4.6　广义表的应用举例：三元多项式的表示148
　小结150
　习题151
第6章　树与二叉树153
　6.1　树的基本概念153
　　6.1.1　树的定义和术语153
　　6.1.2　树的基本操作155
　6.2　二叉树及其存储表示 156
　　6.2.1　二叉树的概念156
　　6.2.2　二叉树的性质157
　　6.2.3　二叉树的主要操作159
　　6.2.4　二叉树的顺序存储表示160
　　6.2.5　二叉树的链接存储表示161
　6.3　二叉树的遍历163
　　6.3.1　二叉树遍历的递归算法163
　　6.3.2　递归遍历算法的应用举例164
　　6.3.3　二叉树遍历的非递归算法167
　　6.3.4　利用队列实现二叉树的层次序遍历170
　　6.3.5　二叉树的计数171
　6.4　线索二叉树173
　　6.4.1　线索二叉树的概念173
　　6.4.2　线索二叉树的种类174
　　6.4.3　中序线索二叉树的建立和遍历174
　　6.4.4　先序与后序线索二叉树176
　6.5　树与森林178
　　6.5.1