目录Contents 第1章绪论1 1.1什么是数据结构1 1.1.1数据结构的定义1 1.1.2学习数据结构的意义4 1.2基本概念和术语5 1.2.1数据与数据元素5 1.2.2数据的逻辑结构与存储结构5 1.2.3数据运算6 1.2.4数据类型与抽象数据类型7 1.3算法和算法描述语言8 1.4算法分析9 1.4.1算法评价9 1.4.2算法性能分析与度量13 本章小结18 习题18 第2章线性表22 2.1案例导引22 2.2线性表的逻辑结构24 2.2.1线性表的定义24 2.2.2线性表的基本操作24 2.3线性表的顺序存储及运算实现25 2.3.1顺序表25 2.3.2顺序表上基本运算的实现27 2.4顺序表应用举例31 2.5线性表的链式存储和运算实现33 2.5.1单链表33 2.5.2单链表基本运算的实现352.5.3循环链表40 2.5.4双向链表40 2.5.5静态链表42 2.6单链表应用举例43 2.7顺序表和链表的比较55 2.8案例分析与实现46 本章小结56 习题57 ◆数据结构(C语言版)(第2版·微课版)目录第3章栈和队列61 3.1案例导引61 3.2栈63 3.2.1栈的定义及基本操作63 3.2.2栈的顺序存储及操作实现64 3.2.3栈的链式存储及操作实现67 3.3栈的应用举例70 3.4递归82 3.4.1递归定义82 3.4.2递归和栈的关系83 3.4.3递归算法实例84 3.5队列87 3.5.1队列的定义及基本操作87 3.5.2队列的顺序存储实现及操作实现88 3.5.3队列的链式存储实现及操作实现92 3.6队列应用举例95 3.7案例分析与实现97 本章小结101 习题101 第4章串105 4.1案例导引105 4.2串及其基本运算106 4.2.1串的基本概念106 4.2.2串的基本运算107 4.3串的顺序存储及基本运算108 4.3.1串的定长顺序存储109 4.3.2定长顺序串的基本运算109 4.4模式匹配111 4.4.1简单的模式匹配算法111 4.4.2KMP算法113 4.5串的堆存储结构118 4.5.1动态堆存储118 4.5.2静态堆存储121 4.6串的链式存储结构124 4.7案例分析与实现125 本章小结131 习题132 第5章数组和广义表135 5.1案例导引135 5.2数组139 5.2.1数组的定义139 5.2.2数组的内存映像139 5.3特殊矩阵的压缩存储140 5.3.1对称矩阵140 5.3.2三角矩阵141 5.3.3稀疏矩阵141 5.4广义表147 5.4.1广义表的定义147 5.4.2广义表的存储148 5.4.3广义表基本操作的实现148 5.5案例分析与实现154 本章小结156 习题156 第6章树和二叉树160 6.1案例导引160 6.2树的基本概念162 6.2.1树的定义及其表示162 6.2.2基本术语163 6.3二叉树164 6.3.1二叉树的定义164 6.3.2二叉树的性质165 6.3.3二叉树的存储结构167 6.4遍历二叉树168 6.4.1先序遍历169 6.4.2中序遍历171 6.4.3后序遍历172 6.4.4按层次遍历二叉树175 6.4.5遍历算法的应用举例175 6.5线索二叉树178 6.5.1线索的概念178 6.5.2线索的算法实现180 6.5.3线索二叉树上的运算182 6.6树与森林184 6.6.1树的存储结构184 6.6.2树、森林和二叉树的转换186 6.6.3树和森林的遍历189 6.7哈夫曼树190 6.7.1基本术语191 6.7.2哈夫曼树的建立191 6.8案例分析与实现197 本章小结205 习题205 第7章图210 7.1案例导引210 7.2图的基本概念213 7.2.1图的定义和术语213 7.2.2图的基本操作217 7.3图的存储结构217 7.3.1邻接矩阵218 7.3.2邻接表219 7.3.3十字链表221 7.3.4邻接多重表223 7.4图的遍历224 7.4.1深度优先搜索225 7.4.2广度优先搜索226 7.4.3应用图的遍历判定图的连通性228 7.4.4图的遍历的其他应用229 7.5最小生成树239 7.5.1生成树及生成森林239 7.5.2最小生成树的概念240 7.5.3构造最小生成树的Prim算法241 7.5.4构造最小生成树的Kruskal算法243 7.6最短路径245 7.6.1从一个源点到其他各点的最短路径245 7.6.2每一对顶点之间的最短路径249 7.7有向无环图及其应用251 7.7.1有向无环图的概念251 7.7.2AOV网与拓扑排序252 7.7.3AOE图与关键路径256 7.8案例分析与实现261 本章小结265 习题266 第8章查找270 8.1案例导引270 8.2基本概念271 8.3线性表的查找272 8.3.1顺序查找272 8.3.2折半查找273 8.3.3分块查找275 8.4树表查找276 8.4.1二叉排序树277 8.4.2平衡二叉树282 8.4.3平衡二叉树的建立289 8.4.4B树和B+树293 8.5哈希表查找297 8.5.1哈希表与哈希方法297 8.5.2常用的哈希方法298 8.5.3处理冲突的方法299 8.5.4哈希表的操作302 8.5.5哈希表查找及其分析303 8.6案例分析与实现304 本章小结312 习题312 第9章排序316 9.1案例导引316 9.2插入排序319 9.2.1直接插入排序319 9.2.2折半插入排序321 9.2.3希尔排序322 9.3交换排序324 9.3.1冒泡排序324 9.3.2快速排序326 9.4选择排序329 9.4.1简单选择排序329 9.4.2堆排序331 9.5归并排序334 9.6基数排序336 9.6.1多关键码排序336 9.6.2链式基数排序337 9.7案例分析与实现340 本章小结348 习题349 第10章数据结构综合应用352 10.1各种结构类型之间的关系概述352 10.2二叉树与分治策略355 10.3图的遍历及其应用360 本章小结370 习题370 参考文献372