本书是普通高等教育“十一五”国家级规划教材。全书共10章，内容包括：数据结构的概念，几种基本的线性结构（如线性表），栈和队列，串，几种非线性结构（如多维数组和广义表），树，图，常用的数据处理技术（如排序），查找，文件的存储结构和组织方法等。在每章中都收集了难度各异的习题和例题，全书采用C语言作为算法描述语言，并有详细的注释，书中全部程序均上机验证并调试通过，同时给出部分程序的运行结果。各章中的“简单应用举例”，既是本章算法的综合应用，也可作为本章实训内容和课程设计的综合练习，全书有很强的实用性和可操作性。本书可以作为全日制高等学校计算机应用专业、微电子和信息工程专业、计算机信息管理和经济信息管理类等专业普通本科学生的专业基础课教材，也可以作为上述专业高职高专学生的参考教材，还可以作为计算机等级考试的参考书，供广大从事计算机应用工作的管理人员和技术人员学习参考。

田鲁怀，女，硕士学位，副教授职称。于1982年获中国石油大学（原华东石油学院）采油工程专业学士学位和1996年获上海大学（原上海工业大学）计算机应用专业硕士学位；先后在大学、高专学校和高职技术学院任教，分别于1989年和1996年获讲师和副教授职称。从1984年起，一直从事计算机专业的教学和科研工作。先后主讲了《数据结构》、《PASCAL语言程序设计》、《C语言程序设计》、《数据库原理及其应用》、《管理信息系统》等课程。现已退休。

目 录第1章 概论11.1 概述11.2 数据结构的基本概念41.2.1 数据结构的基本术语41.2.2 数据的逻辑结构61.2.3 数据的存储结构81.3 算法性能分析与度量121.3.1 算法和算法的描述方法121.3.2 算法的特性141.3.3 算法设计的要求141.3.4 算法时间复杂度的分析与度量151.3.5 算法存储空间的分析与度量19本章小结19习题120第2章 线性表232.1 线性表的定义及基本运算232.1.1 线性表的定义232.1.2 线性表的基本运算242.2 线性表的顺序存储结构及其运算252.2.1 线性表的顺序存储结构252.2.2 顺序表上的基本运算262.2.3 顺序表上插入和删除运算的时间分析302.2.4 顺序表的优点和缺点312.3 线性表的链接存储结构及其运算312.3.1 单链表312.3.2 单链表上的基本运算322.3.3 单链表上查找、插入和删除运算的时间分析402.3.4 循环链表402.3.5 双向链表432.4 顺序表和链表的比较462.5 线性表的简单应用举例47本章小结62习题263第3章 栈和队列663.1 栈的基本概念663.2 栈的存储结构673.2.1 栈的顺序存储结构673.2.2 栈的链接存储结构683.2.3 栈的两种存储结构的比较693.2.4 多个顺序栈共享一个数组的存储空间693.3 栈的基本运算703.3.1 顺序存储结构上顺序栈的运算实现713.3.2 链接存储结构上链栈的运算实现723.4 栈的简单应用举例733.4.1 栈在递归过程中的作用733.4.2 栈的几个简单应用实例763.5 队列的基本概念813.6 队列的存储结构823.6.1 队列的顺序存储结构823.6.2 顺序存储的循环队列843.6.3 队列的链接存储结构853.7 队列的基本运算863.7.1 顺序存储结构上顺序队列的运算实现863.7.2 顺序存储结构上循环队列的运算实现873.7.3 链接存储结构上链队列的运算实现893.8 队列的简单应用举例91本章小结97习题398第4章 串1004.1 串的基本概念1004.2 串的存储结构1014.2.1 串的顺序存储结构1014.2.2 串的链接存储结构1034.3 串的基本运算及实现1054.3.1 串的基本运算1054.3.2 顺序串上基本运算的实现1064.3.3 链串上基本运算的实现1084.4 串的模式匹配运算1124.4.1 BF模式匹配算法1124.4.2 BM模式匹配算法1154.4.3 KMP模式匹配算法1174.5 串的简单应用举例124本章小结131习题4131第5章 数组和广义表1335.1 数组的概念和存储1335.1.1 数组的概念1335.1.2 数组的存储结构1345.2 特殊矩阵的压缩存储1375.2.1 对称矩阵的压缩存储1375.2.2 三角矩阵的压缩存储1385.2.3 对角矩阵的压缩存储1395.3 稀疏矩阵的压缩存储1415.3.1 稀疏矩阵的三元组表示1415.3.2 稀疏矩阵的十字链表表示1485.3.3 稀疏矩阵的简单应用举例1525.4 广义表1575.4.1 广义表的基本概念1575.4.2 广义表的链接存储结构1585.4.3 广义表的基本运算1615.4.4 广义表的简单应用举例166本章小结167习题5168第6章 树1706.1 树的基本概念1706.1.1 树的定义1706.1.2 树的基本术语1726.2 二叉树1746.2.1 二叉树的概念1746.2.2 二叉树的基本性质1766.2.3 二叉树的存储结构1776.3 二叉树的运算1806.3.1 二叉树的遍历1806.3.2 二叉树的建立1856.3.3 二叉树的其他运算举例1876.4 线索二叉树1926.4.1 线索二叉树的概念1926.4.2 二叉树的中序线索化1936.4.3 线索二叉树的遍历和插入运算1956.5 树和森林1986.5.1 树的存储结构1986.5.2 树和森林与二叉树的转换2016.5.3 树的遍历2056.5.4 森林的遍历2066.6 哈夫曼树及其应用2076.6.1 哈夫曼树的基本概念2076.6.2 哈夫曼树的构造及实现2086.6.3 哈夫曼编码2116.6.4 哈夫曼译码2156.6.5 哈夫曼树在编码问题中的完整程序216本章小结218习题6219第7章 图2227.1 图的基本概念2227.1.1 图的实际背景2227.1.2 图的定义2237.1.3 图的基本术语2247.2 图的存储结构2277.2.1 邻接矩阵表示法2277.2.2 邻接表表示法2317.3 图的遍历2347.3.1 连通图的深度优先搜索遍历2357.3.2 连通图的广度优先搜索遍历2377.3.3 非连通图的遍历2407.3.4 连通图和非连通图的建立与遍历运算实例2417.4 生成树和最小生成树2437.4.1 生成树和最小生成树的概念2447.4.2 Kruskal算法2457.4.3 Prim算法2487.5 最短路径2507.5.1 最短路径的概念2507.5.2 单源最短路径2527.5.3 所有顶点对之间的最短路径2557.6 AOV网和拓扑排序2607.6.1 AOV网和拓扑排序的概念2607.6.2 拓扑排序算法2617.7 AOE网和关键路径2657.7.1 AOE网和关键路径的概念2657.7.2 关键路径的确定2677.8 图的简单应用举例269本章小结277习题7278第8章 排序2818.1 排序的基本概念2818.2 插入排序2848.2.1 直接插入排序2848.2.2 希尔排序2868.3 交换排序2888.3.1 冒泡排序2888.3.2 快速排序2918.4 选择排序2948.4.1 直接选择排序2948.4.2 堆排序2958.5 归并排序3028.5.1 两个相邻有序表的一次归并过程3038.5.2 一趟归并排序过程3038.5.3 二路归并排序3048.6 各种内排序方法的比较和选择3058.6.1 各种内排序方法的总结3058.6.2 各种内排序方法的比较3058.6.3 排序方法的选择3068.7 排序的简单应用举例307本章小结311习题8312第9章 查找3159.1 查找的基本概念3159.2 线性表的查找3169.2.1 顺序查找3169.2.2 二分查找3179.2.3 分块查找3209.3 树表的查找3239.3.1 二叉排序树3239.3.2 平衡的二叉排序树3309.3.3 B-树3359.4 散列表的查找3429.4.1 散列表的概念3429.4.2 散列函数的构造方法3449.4.3 处理冲突的方法3479.4.4 散列表的运算3519.4.5 散列表的查找及分析3559.5 查找的简单应用举例357本章小结362习题9363第10章 文件36510.1 文件的基本概念36510.2 顺序文件36710.3 索引文件36810.4 索引顺序文件37010.4.1 ISAM文件37010.4.2 VSAM文件37310.5 散列文件37510.6 多关键字文件37610.6.1 多重表文件37610.6.2 倒排文件377本章小结378习题10379参考文献380