数据结构基础(C语言版)(第2版) 内容简介

简介本书是*经典数据结构教材的*新版本，国内外大多数的同类教材都是以本书为蓝本编写而来的。本书用c作为描述语言，全面而生动地介绍了数据结构的有关知识，如数组、栈、队列、链表、树和图，以及构成所有软件基础的排序散列技术。此外，本书还介绍了各种高级或特殊数据结构，如优先级队列、高效二叉查找树、多路查找树等。本书对大多数算法都给出了计算时间在*优、*差情形下的复杂度分析。本书不仅可以作为计算机及相关专业本科生“数据结构”课程的教材，也可以作为研究生**学年的“高等数据结构”课程的教材，同时，本书所介绍的各种算法的c语言实现，对有关专业人员也具有很好的参考价值。

数据结构基础(C语言版)(第2版) 本书特色

《数据结构基础(C语言版)(第2版)》不仅可以作为计算机及相关专业本科生“数据结构”课程的教材，也可以作为研究生**学年的“高等数据结构”课程的教材，同时，《数据结构基础(C语言版)(第2版)》所介绍的各种算法的C语言实现，对有关专业人员也具有很好的参考价值。

数据结构基础(C语言版)(第2版) 目录

第1章 基本概念1.1 概观：系统生命周期1.2 指针和动态存储分配1.2.1 指针1.2.2 动态存储分配1.2.3 指针隐患1.3 算法形式规范1.3.1 综论1.3.2 递归算法1.4 数据抽象1.5 性能分析1.5.1 空间复杂度1.5.2 时间复杂度1.5.3 渐近记号(O，Q，)1.5.4 实际复杂度1.6 性能度量1.6.1 定时1.6.2 生成测试数据1.7 参考文献和选读材料第2章 数组和结构2.1 数组2.1.1 数组的抽象数据类型2.1.2 c语言的数组2.2 数组的动态存储分配2.2.1 一维数组2.2.2 二维数组2.3 结构体和联合体2.3.1 结构体2.3.2 联合体2.3.3 结构的内部实现2.3.4 自引用结构2.4 多项式2.4.1 多项式的抽象数据类型2.4.2 多项式的表示2.4.3 多项式加法2.5 稀疏矩阵2.5.1 稀疏矩阵的抽象数据类型2.5.2 稀疏矩阵的表示2.5.3 矩阵转置2.5.4 矩阵相乘2.6 多维数组的表示2.7 字符串2.7.1 字符串的抽象数据类型2.7.2C语言的字符串2.7.3 模式匹配2.8 参考文献和选读材料2.9 补充习题第3章 栈与队列3.1 栈3.2 动态栈3.3 队列3.4 动态循环队列3.5 迷宫问题3.6 表达式求值3.6.1 表达式3.6.2 后缀表达式求值3.6.3 中缀表达式转换成后缀表达式3.7 多重栈与多重队列3.8 补充习题第4章 链表4.1 单向链表4.2 用C语言表示单向链表4.3 链式栈与链式队列4.4 多项式4.4.1 多项式表示4.4.2 多项式加法4.4.3 销毁多项式4.4.4 循环链表与多项式4.4.5 小结4.5 其它链表操作4.5.1 单向链表操作4.5.2 循环链表操作4.6 等价类4.7 稀疏矩阵4.7.1 稀疏矩阵表示4.7.2 输入稀疏矩阵4.7.3 输出稀疏矩阵4.7.4 销毁稀疏矩阵4.8 双向链表第5章 树5.1 引论5.1.1 术语5.1.2 树的表示5.2 二叉树5.2.1 二叉树的抽象数据类型5.2.2 二叉树的性质5.2.3 二叉树的表示5.3 遍历二叉树5.3.1 中序遍历5.3.2 先序遍历5.3.3 后序遍历5.3.4 非递归(循环)中序遍历5.3.5 层序遍历5.3.6 不设栈遍历二叉树5.4 其它二叉树操作5.4.1 复制二叉树5.4.2 判断两个二叉树全等5.4.3 可满足性问题5.5 线索二叉树5.5.1 线索5.5.2 中序遍历线索二叉树5.5.3 线索二叉树插入结点5.6 堆5.6.1 优先级队列5.6.2 大根堆定义5.6.3 大根堆插入操作5.6.4 大根堆删除操作5.7 二叉查找树5.7.1 定义5.7.2 二叉查找树的查找5.7.3 二叉查找树的插入5.7.4 二叉查找树的删除5.7.5 二叉查找树的合并与分裂5.7.6 二叉查找树的高度5.8 选拔树5.8.1 引子5.8.2 优胜树5.8.3 淘汰树5.9 森林5.9.1 森林转换为二叉树5.9.2 遍历森林5.10 不相交集合的表示5.10.1 引子5.10.2 合并与查找操作5.10.3 划分等价类5.11 二叉树的计数5.11.1 不同态二叉树5.11.2 栈置换5.11.3 矩阵乘法5.11.4 不同二叉树的数目5.12 参考文献和选读材料第6章 图6.1 图的抽象数据类型6.1.1 引子6.1.2 图的定义和术语6.1.3 图的表示6.2 图的基本操作6.2.1 深度优先搜索6.2.2 广度优先搜索6.2.3 连通分量6.2.4 生成树6.2.5 重连通分量6.3 *小代价生成树6.3.1 Kruskal算法6.3.2 Prim算法6.3.3 SoUin算法6.4 *短路径和迁移闭包6.4.1 单源点至所有其它节点：边权值非负6.4.2 单源点至所有其它节点：边权值正负无限制

数据结构基础(C语言版)(第2版) 节选

《数据结构基础(C语言版)(第2版)》是*经典数据结构教材的*新版本，国内外大多数的同类教材都是以《数据结构基础(C语言版)(第2版)》为蓝本编写而来的。《数据结构基础(C语言版)(第2版)》用C作为描述语言，全面而生动地介绍了数据结构的有关知识，如数组、栈、队列、链表、树和图，以及构成所有软件基础的排序散列技术。此外，《数据结构基础(C语言版)(第2版)》还介绍了各种高级或特殊数据结构，如优先级队列、高效二叉查找树、多路查找树等。《数据结构基础(C语言版)(第2版)》对大多数算法都给出了计算时间在*优、*差情形下的复杂度分析。

数据结构基础(C语言版)(第2版) 作者简介

Ellis Horowitz，是南加州大学计算机与电子工程系的教授。Horowitz博士已编著了10多本教材，并发表了大量学术论文。
Sartaj Sahni是佛罗里达大学计算机与信息科学系的杰出教授和讲座教授。Sahni博士已发表300多篇学术研究论文，编著了15本教材。
Susan Anderson-Freed是伊利诺伊卫斯理大学计算机教授。她的研究领域是数据库管理系统、Web设计与开发。她毕业于诺伯特大学，并在印第安纳大学获得硕士和博士学位，以及在Bradley大学获得计算机理学地硕士学位。她从1977年起就供职于伊利诺伊卫斯理大学。