数据结构

章节摘录

插图：本章的补充读物建议如下：文献[8]把数据结构原理和算法分析技术有机结合在一起，系统介绍了基本的数据结构、算法分析技术以及排序和检索的各种方法，并简要介绍了较高级的数据结构和可计算性理论的一般知识。文献[9]对算法分析所涉及的、几乎取自每一数学分支的数学计算（或技术）进行了全面、深入的讨论；精辟介绍了各种经典算法，对算法复杂性进行了严格分析，透彻阐明了算法正确性证明的方法；给出了数据结构概念的严密定义；彻底厘清了数据结构的历史、文献和发展脉络。文献[9]无疑是数据结构和算法方面的一部最权威、内容最丰富的经典著作。文献[10]提出了一种对算法进行分类的新方法，基于该方法介绍了一些经典的算法设计技术，给出了算法效率分析的框架和分析方法。文献[11]系统地介绍了基本数据结构以及算法设计的方法、技术和应用实例。文献[12]从算法设计与算法分析的基本概念和方法入手，介绍了常用、经典的算法设计技术，给出每种技术的特征、应用背景和应用实例，并详细分析了每个算法的复杂性。文献[13]介绍了基本数据结构，将算法设计与分析结合在一起，重点讨论了算法的设计策略、下界理论、NP难题和NP完全问题、近似算法和并行算法等。文献[14]对计算机算法、算法设计策略进行了全面、深入的介绍，采用大量的插图说明算法的工作过程，每一个算法都给出了其运行时间的详细分析，分析过程既保持了数学的严谨性，又易于理解。

前言

数据结构与算法紧密相关。算法是求解问题的步骤，它必须是确定的（无歧义）、可行的、有限的。此外，它可以有零个或多个输入，但必须有输出。注意不要将算法和计算机程序等同起来，后者可作为描述前者的手段之一。除了使用算法描述语言描述算法之外，还可用流程图、形式语言、程序设计语言，甚至自然语言等对算法进行描述。但不管怎么样，“算法是贯穿在所有计算机程序设计中的一个基本概念”（D. E. Knuth，1997）、“算法是计算机科学的灵魂”（Umesh Vazirani，2008）等观点，却是计算机界众多学者所认同的。算法学是系统研究算法的一门科学。通常，它主要包括算法设计、算法正确性证明及算法分析三个部分。算法设计是创建算法的过程，它研究良好的创建方法以及算法与数据结构之间的关系和作用；算法或其关键步骤正确性证明的基本途径是数学归纳法；算法时间复杂性分析是算法分析的重要内容之一。在算法的时间复杂性分析方面，有时只得到复杂性的阶是不够的，要给出更精确的分析结果，还要知道复杂性的阶前面的系数。自20世纪60年代初开始，计算机越发频繁地用于解决一些非数值分析问题。解决这些问题主要使用计算机的逻辑判断能力而非其算术运算能力。当然，“非数值分析”实际上是关于这一研究领域的一个极其负面的称谓，最好应有一个正面的名称。“信息处理”太过宽泛，而“程序设计技术”又显得过窄，称其为“计算机算法分析”似乎恰当一些。

内容概要

刘大有，吉林大学教授、博士生导师。国家基金委专家评审组成员，吉林省计算机学会理事长，中国人工智能学会常务理事，知识工程与分布智能专委会副主任，中国计算机学会人工智能与模式识别专委会副主任。1997-2008年曾任国务院学位委员会学科评议组成员。在知识工程.专家系统、分布智能.智能体，时空推理和数据挖掘等方面取得了系统的创造性成果.为提高我国智能推理与智能系统等方面的研究与应用水平做出了突出贡献承担国家和省部级项目50余项，出版著作9部，发表论文390余篇，三大检索270余篇；获国家科技进步奖2项、省部级科技进步奖9项；获国家教学成果二等奖1项、省教学成果一等奖2项、国家精品课程和国家级教学团队称号；并获国务院特殊津贴，省突出贡献专家，首批和二批省管优秀专家.一、二批省高级专家等荣誉。

书籍目录

第一章 绪论
  1.1 为什么要学习数据结构
  1.2 数据结构概念
    1.2.1 数据的逻辑结构
    1.2.2 数据的存储结构
    1.2.3 对数据结构的操作
    1.2.4 数据结构示例
  1.3 算法
    1.3.1 算法及其特性
    1.3.2 算法的描述
    1.3.3 算法的评价准则
  1.4 算法的正确性证明
  1.5 算法分析基础
    1.5.1 算法时间复杂性的分析方法
    1.5.2 复杂性函数的渐近表示
    1.5.3 算法时间与空间分析
    1.5.4 计算复杂性和算法的效率
  小结
  参考文献与推荐读物
  习题
第二章 线性表、堆栈和队列
  2.1 线性表的定义和基本操作
  2.2 线性表的顺序存储结构
  2.3 线性表的链接存储结构
    2.3.1 单链表
    2.3.2 循环链表
    2.3.3 双向链表
  2.4 复杂性分析
  2.5 堆栈
    2.5.1 堆栈的定义和基本操作
    2.5.2 顺序栈
    2.5.3 链式栈
    2.5.4 顺序栈与链式栈的比较
    2.5.5 堆栈应用——括号匹配
  2.6 队列
    2.6.1 队列的定义和基本操作
    2.6.2 顺序队列
    2.6.3 链式队列
    2.6.4 顺序队列与链式队列的比较
    2.6.5 队列与堆栈的扩展
  小结
  参考文献与推荐读物
  习题
第三章 数组和字符串
  3.1 数组
    3.1.1 数组的存储和寻址
    3.1.2 一维数组类
  3.2 矩阵
    3.2.1 矩阵类
    3.2.2 特殊矩阵
    3.2.3 三元组表
    3.2.4 十字链表
  3.3 字符串
    3.3.1 字符串的定义与字符串类
    3.3.2 模式匹配算法
  小结
  参考文献与推荐读物
  习题
第四章 树
  4.1 树的基本概念
    4.1.1 树的定义
    4.1.2 树的相关术语
  4.2 二叉树
    4.2.1 二叉树定义和主要性质
    4.2.2 二叉树顺序存储
    4.2.3 二叉树链接存储
    4.2.4 二叉树遍历
    4.2.5 创建二叉树
    4.2.6 复制二叉树
  4.3 线索二叉树
    4.3.1 线索二叉树定义
    4.3.2 线索二叉树存储
    4.3.3 线索二叉树基本算法
  4.4 树和森林
    4.4.1 树与二叉树的转换
    4.4.2 树的顺序存储
    4.4.3 树的链接存储
    4.4.4 树和森林的遍历
  4.5 压缩与哈夫曼树
    4.5.1 文件编码
    4.5.2 扩充二叉树
    4.5.3 哈夫曼树和哈夫曼编码
  4.6 应用
    4.6.1 表达式求值
    4.6.2 分类与决策树
  小结
  参考文献与推荐读物
  习题
第五章 图
  5.1 图的基本概念
  5.2 图的存储结构与类定义
    5.2.1 存储结构
    5.2.2 Graph类
  5.3 图的遍历算法
    5.3.1 深度优先遍历
    5.3.2 广度优先遍历
  5.4 拓扑排序
  5.5 关键路径
  5.6 最短路径问题
    5.6.1 无权最短路径问题
    5.6.2 正权最短路径问题
    5.6.3 每对顶点之间的最短路径
  5.7 最小支撑树
    5.7.1 普里姆算法
    5.7.2 克鲁斯卡尔算法
  5.8 图的应用
    5.8.1 可及性与Wahall算法
    5.8.2 连通分量
    5.8.3 图在网络分析和信息检索中的应用
  小结
  参考文献与推荐读物
  习题
第六章 递归
  6.1 递归的定义
  6.2 基本递归过程
  6.3 递归过程实现与堆栈
  6.4 递归法求解问题
    6.4.1 委员会问题
    6.4.2 回溯
  6.5 递归的效率
  小结
  参考文献与推荐读物
  习题
第七章 排序
  7.1 排序问题的基本概念
  7.2 插入排序
    7.2.1 直接插入排序
    7.2.2 Shell排序
  7.3 交换排序
    7.3.1 冒泡排序
    7.3.2 快速排序
  7.4 选择排序
    7.4.1 直接选择排序
    7.4.2 堆排序
  7.5 合并排序
  7.6 基于关键词比较的排序算法分析
    7.6.1 平方阶排序算法及改进算法
    7.6.2 线性对数阶排序算法
    7.6.3 分治排序的一般方法
    7.6.4 基于关键词比较的排序算法下界
  7.7 分布排序
    7.7.1 基数分布
    7.7.2 值分布
  7.8 外排序
    7.8.1 外存储器
    7.8.2 磁带排序
    7.8.3 磁盘排序
  小结
  参考文献与推荐读物
  习题
第八章 查找
  8.1 顺序查找
    8.1.1 无序表的顺序查找
    8.1.2 有序表的顺序查找
  8.2 基于关键词比较的查找
    8.2.1 对半查找
    8.2.2 一致对半查找
    8.2.3 斐波那契查找
    8.2.4 插值查找
  8.3 二叉查找树
    8.3.1 基本概念和性质
    8.3.2 查找、插入和删除
    8.3.3 平均情况时间分析
  8.4 最优二叉查找树
    8.4.1 访问频率
    8.4.2 最优二叉查找树
    8.4.3 近似最优树的构造
  8.5 平衡树
    8.5.1 高度平衡树
    8.5.2 重量平衡树
  8.6 红黑树
    8.6.1 红黑树的性质
    8.6.2 旋转
    8.6.3 插入
    8.6.4 删除
  8.7 B树及其变形树
    8.7.1 多又树
    8.7.2 B树
    8.7.3 B树变形树
  8.8 数字查找
    8.8.1 检索结构查找
    8.8.2 数字树查找
  8.9 散列
    8.9.1 散列函数
    8.9.2 冲突调节
    8.9.3 删除
    8.9.4 重量平衡树的应用——按位置查找
  小结
  参考文献与推荐读物
  习题
第九章 内存管理
  9.1 概述
  9.2 均匀大小记录的分配和回收算法
    9.2.1 记录分配算法
    9.2.2 访问计数器法
    9.2.3 废料收集方法
  9.3 不同大小记录的分配和回收算法
    9.3.1 查找分配策略
    9.3.2 边界标识法
    9.3.3 压缩分配
  9.4 伙伴系统
    9.4.1 伙伴系统概述
    9.4.2 分配记录和释放记录算法
  小结
  参考文献与推荐读物
  习题
第10章 文件
  10.1 文件的基本概念
    10.1.1 文件及其分类
    10.1.2 文件的逻辑结构与存储结构
  10.2 顺序文件
    10.2.1 顺序无序文件
    10.2.2 顺序有序文件
    10.2.3 增补文件
  10.3 散列文件
    10.3.1 散列文件
    10.3.2 可扩充的散列文件
  10.4 索引文件
    10.4.1 动态索引结构和静态索引结构
    10.4.2 ISAM文件
    10.4.3 VSAM文件
  10.5 多关键字文件
    10.5.1 多重链表文件
    10.5.2 倒排文件
  小结
  参考文献与推荐读物
  习题
第11章 随机数
  11.1 生成随机数
    11.1.1 均匀分布随机数
    11.1.2 其他分布随机数
  11.2 随机数检验
    11.2.1 一般检验方法
    11.2.2 经验检验方法
  11.3 随机排列与随机组合
    11.3.1 随机排列
    11.3.2 随机组合
  11.4 应用
    11.4.1 随机算法
    11.4.2 使用随机数的快速排序算法
  小结
  参考文献与推荐读物
  习题
附录
  附录1 各章算法的C++实现
  附录2 习题参考答案或解题思路

编辑推荐

《数据结构(第2版)》特色：·采用两种语言描述算法《数据结构(第2版)》正文采用算法描述语言ADL描述算法。附录提供算法的C++实现。这样做有利于读者将注意力聚焦于数据结构与算法的关键部分．弥补了用C++语言描述算法既占用较多篇幅，又涉及较多程序设计细节的不足。·强调“数据结构的严格性”《数据结构(第2版)》对典型算法或给出时间复杂性分析或分析结果，特别对时间复杂性阶相同的相关算法，既给出算法复杂性的阶，又给出阶前面的系数；对某些算法，给出其关键问题(或步骤)的正确性证明。注重分析与证明的严格性。·突出启发式教学与因材施教《数据结构(第2版)》对一些较难的知识点设计了启发式教学案例。在相关算法的衔接处，阐明后续算法形成的思想及其主要特点；在展开算法描述之前，给出算法关键思想的刻画；在每章结尾处。给出相关算法的比较。此外，对习题给出了难度级别，对较难习题给出了分级提示。·配套教学资源丰富《数据结构(第2版)》提供配套的电子讲稿、全书ADL算法的C++程序、较难习题答案的C++代码及相关的测试和运行支持程序(可从中国高校计算机课程网上下载)，可供读者自学和上机使用。

作者简介

《数据结构(第2版)》是国家精品课程“数据结构”的研究成果之一，是面向21世纪课程教材和普通高等教育“十一五”国家级规划教材。《数据结构(第2版)》系统介绍了数据结构的概念、原理与技术，主要内容包括绪论，基本数据结构，排序、查找与内存管理，相关工具和文件等。其中，第一章绪论主要对算法描述语言（ADL）、算法书写规范、数据结构与算法基本概念、算法分析基础和算法正确性证明等进行了介绍；第二至五章是基本数据结构部分，主要涉及线性表、堆栈和队列，数组和字符串，树与二叉树，图结构等内容；第七至九章从算法的视角讨论了排序、查找和内存管理等方面的内容，给出了若干典型算法的描述、时间复杂性分析和相关算法的比较等；第六章和十一章分别对递归和随机数两种主要工具进行了讲解，其中随机数是数据结构的新内容；文件这种复杂的数据结构则在第十章中阐明。

《数据结构(第2版)》的附录主要包括书中ADL算法的C++程序、一些基本数据结构的C++类实现以及习题答案或解题思路。《数据结构(第2版)》配套教学资源中包括电子教案、ADL算法的C++程序、较难习题答案的C++代码以及相关的测试和运行支持程序，可供读者自学和上机使用。

《数据结构(第2版)》可作为高等学校计算机相关专业的教材和教学参考书，也可供相关专业的工程技术人员参考使用。

图书封面

---

 数据结构下载

---