数据结构教程

　　本书特色：◆内容组织上层次分明，结构清晰。内容叙述深入浅出，表述严谨。强调实验动手能力的提高，每章给出与内容相一致的上机实验题。与本书配套的《数据结构教程学习指导》和《数据结构教程上机实验指导》两书，构成一个完整的教学系列。◆本系列中所有程序均在VisualC++6．0环境下调试通过。本教程和相关学习指导的编写得到武汉大学教务部“数据结构综合教学改革”和“数据结构精品课程建设”教学项目的支持，是集体课程组许多教师多年来数据结构课程教学研究和教学改革经验和成果于一体。◆书中精编了大量的实例，这些实例体现了良好的程序设计风格。本书介绍了数据结构的基本知识和各种数据结构的具体应用。全书分为14章，主要内容包括数据结构的基本概念、线性表、栈和队列、串、数组和稀疏矩阵、递归算法、树和二叉树、广义表、图、各种查找算法的实现、排序算法的实现，文件结构以及采用面向对象方法描述算法等。本书突出上机实习内容，第1～13章给出大量的上机实验题，供读者选用。书中精编了大量的实例，这些实例体现了求解问题的方法和良好的程序设计风格。本书适合作为高等院校计算机及其相关专业的本科生教材，也可作为软件技术人员的参考用书。

暂缺《数据结构教程》作者简介

目    录
第1章  绪论 11.1  数据结构的讨论范畴 11.2  数据结构的发展概况 31.3  数据结构的相关概念 51.3.1  基本概念和术语 51.3.2  数据结构 61.3.3  数据类型和抽象数据类型 101.4  数据结构的算法描述 121.4.1  算法 121.4.2  算法的描述 131.5  数据结构的算法分析 171.5.1  算法效率的度量 171.5.2  算法的空间需求 191.6  习题 20第2章  线性表 232.1  线性表的类型定义 232.1.1  线性表的定义 242.1.2  线性表的抽象数据类型 242.2  线性表的顺序表示与实现 272.2.1  线性表的顺序存储表示 282.2.2  顺序表中基本操作的实现 282.2.3  顺序存储结构小结 342.2.4  应用举例 352.3  线性表的链式表示与实现 382.3.1  线性表的链式存储表示 392.3.2  单链表中基本操作的实现 392.3.3  循环链表 442.3.4  双向链表 442.3.5  静态链表 472.3.6  链式存储结构小结 482.3.7  应用举例 482.4  顺序表示与链式表示比较 532.4.1  基于空间的考虑 532.4.2  基于时间的考虑 542.4.3  基于语言的考虑 542.5  习题 54第3章  栈和队列 583.1  栈 583.1.1  栈的定义 583.1.2  栈的抽象数据类型 593.1.3  栈的顺序存储表示与实现 603.1.4  栈的链式存储表示与实现 633.1.5  应用举例 643.2  队列 733.2.1  队列的定义 733.2.2  队列的抽象数据类型 733.2.3  队列的顺序存储表示与实现 743.2.4  队列的链式存储表示与实现 783.2.5  应用举例 803.3  习题 83第4章  串 854.1  串的类型定义 854.1.1  串的定义 854.1.2  串的抽象数据类型 864.2  串的存储表示与实现 884.2.1  定长顺序存储表示 884.2.2  堆分配存储表示 914.2.3  块链存储表示 954.2.4  应用举例 964.3  串的模式匹配 974.3.1  串的模式匹配BF算法 974.3.2  串的模式匹配KMP算法 994.4  习题 103第5章  多维数组与广义表 1055.1  多维数组 1055.1.1  数组的定义 1055.1.2  数组的抽象数据类型 1065.1.3  数组的顺序存储表示和实现 1075.1.4  应用举例 1105.2  矩阵的压缩存储 1115.2.1  特殊矩阵 1125.2.2  稀疏矩阵 1145.2.3  应用举例 1245.3  广义表 1285.3.1  广义表的定义 1285.3.2  广义表的抽象数据类型 1295.3.3  广义表的链式存储表示与实现 1305.3.4  应用举例 1385.4  习题 142第6章  二叉树与树 1446.1  二叉树 1446.1.1  二叉树的定义 1446.1.2  二叉树的基本术语 1456.1.3  二叉树的抽象数据类型 1476.1.4  二叉树的基本性质 1486.1.5  二叉树的存储表示 1506.2  遍历二叉树 1536.2.1  遍历二叉树的定义 1546.2.2  遍历二叉树的递归算法 1556.2.3  遍历二叉树的非递归算法 1566.2.4  基于遍历操作的其他算法 1626.2.5  应用举例 1636.3  线索二叉树 1686.3.1  线索二叉树的引出 1686.3.2  线索二叉树的定义 169
6.3.3  线索二叉树的存储表示与实现 1706.3.4  应用举例 1766.4  树和森林 1776.4.1  树和森林的定义 1776.4.2  树的抽象数据类型 1786.4.3  树的存储表示 1796.4.4  树和森林与二叉树的转换 1836.4.5  树和森林的遍历 1876.4.6  应用举例 1896.5  Huffman树及其应用 1976.5.1  Huffman树的定义 1976.5.2  Huffman算法 1996.5.3  Huffman树的存储表示与实现 2006.5.4  Huffman编码 2016.5.5  Huffman编码的存储表示与实现 2026.5.6  应用举例 2036.6  习题 205第7章  图 2107.1  图的类型定义 2107.1.1  图的定义 2107.1.2  图的基本术语 2107.1.3  图的抽象数据类型 2147.1.4  应用举例 2157.2  图的存储表示与实现 2167.2.1  邻接矩阵表示法 2167.2.2  邻接表表示法 2197.2.3  十字链表表示法 2227.2.4  邻接多重表表示法 2247.1.5  应用举例 2267.3  图的遍历 2277.3.1  深度优先搜索遍历图 2277.3.2  广度优先搜索遍历图 2287.3.3  应用举例 2297.4  最小生成树 230
7.4.1  生成树 2307.4.2  最小生成树 2317.4.3  应用举例 2377.5  最短路径 2387.5.1  求某个源点到其他顶点的最段路径 2397.5.2  求每一对顶点之间的最短路径 2427.5.3  应用举例 2447.6  拓扑排序 2457.6.1  AOV网 2457.6.2  拓扑排序 2477.6.3  应用举例 2497.7  关键路径 2507.7.1  AOE 网 2507.7.2  关键路径的概念 2517.7.3  求关键路径的算法实现 2527.7.4  应用举例 2547.8  习题 255第8章  查找表 2608.1  静态查找表 2628.1.1  静态查找表的抽象数据类型 2628.1.2  静态查找表的顺序存储表示 2628.1.3  顺序查找 2628.1.4  折半查找 2638.1.5  分块查找 2658.1.6  应用举例 2678.2  动态查找表 2688.2.1  动态查找的抽象数据类型 2688.2.2  动态查找表的存储表示 2698.2.3  二叉排序树 2698.2.4  平衡二叉树 2748.2.5  B-树和B+树 2808.2.6  键树 2888.2.7  应用举例 2928.3  哈希表 2988.3.1  哈希表的定义 2998.3.2  哈希函数的构造方法 3008.3.3  处理冲突的方法 3038.3.4  哈希表的查找和分析 3058.3.5  应用举例 3088.4  习题 310第9章  内部排序 3149.1  插入排序法 3159.1.1  直接插入排序 3159.1.2  希尔排序 3179.1.3  应用举例 3189.2  交换排序法 3199.2.1  冒泡排序 3199.2.2  快速排序 3209.2.3  应用举例 3239.3  选择排序法 3239.3.1  直接选择排序 3249.3.2  堆排序 3259.3.3  应用举例 3319.4  归并排序法 3319.4.1  两个有序序列的归并 3319.4.2  2-路归并排序 3329.4.3  应用举例 3339.5  基数排序法 3339.5.1  多关键字排序 3339.5.2  链式基数排序 3359.5.3  应用举例 3399.6  各种内部排序法的比较 3409.7  习题 341第10章  外部排序 34410.1  外存储设备简介 34410.1.1  磁带信息的存取 34410.1.2  磁盘信息的存取 34510.1.3  光盘信息的存取 34610.2  磁带文件归并排序 34710.2.1  平衡归并排序 34710.2.2  多步归并排序 34810.2.3  应用举例 35310.3  磁盘文件归并排序 35610.3.1  初始归并段的生成 35610.3.2  置换选择排序法 35710.3.3  应用举例 35810.4  最佳归并树 35910.4.1  最佳归并树的定义 35910.4.2  最佳归并树的设计 36110.4.3  应用举例 36210.5  习题 362第11章  文件 36411.1  基本概念 36411.1.1  文件的概念 36411.1.2  文件的分类 36511.1.3  文件的逻辑结构 36511.1.4  文件的物理结构 36611.2  顺序文件 36611.2.1  顺序文件的查找 36711.2.2  顺序文件的修改 36711.2.3  顺序文件的特点 36811.3  索引文件 36811.3.1  索引文件的分类 36811.3.2  索引文件的存储 36911.3.3  索引文件的操作 36911.3.4  利用查找表建立 多级索引 370
11.4  ISAM和VSAM文件 37111.4.1  ISAM 文件 37111.4.2  VSAM 文件 37411.5  哈希文件 37611.5.1  哈希文件的操作 37711.5.2  哈希文件的特点 37811.6  多关键字文件 37811.6.1  多重表文件 37811.6.2  倒排文件 38011.7  应用举例 38111.8  习题 384第12章  数据结构程序设计方法 38612.1  从问题到程序的求解过程 38612.1.1  建立数据结构模型设计 抽象数据类型 38612.1.2  算法设计 38712.1.3  实现抽象数据类型 38812.1.4  编制程序代码并进行 静态测试和动态调试 38912.2  程序的规范说明 39112.3  应用举例 392附录A  部分习题答案 402参考书目 409