数据结构是高等学校计算机及其相关专业的核心课程，是计算机程序设计的基础。本书按照“像外行一样思考，像专家一样实践”的解决问题的思维方法，列举大量实际或工程案例，从具体问题中引出抽象概念，运用类比、图形化描述等各种方式，对经典数据结构内容做深入浅出的介绍。在介绍数据结构和算法的基本概念和算法分析方法的基础之上，从软件开发的角度，通过应用背景或知识背景介绍、数据分析、函数设计、算法设计、测试调试等环节，分别对顺序表、链表、栈、队列、串、数组、树、图等基本类型的数据结构进行了分析和讨论；介绍数据的典型操作方法，如数据排序方法和查找方法；介绍常见的如递归法、分治法、动态规划、贪心法等经典算法。

周幸妮，西安电子科技大学副教授，长期从事“数据结构”、“C程序设计语言”等课程的教学工作，著有《C程序设计》等教材。

第1章 绪论11.1 从编程说起11.2 程序要处理的数据51.3 数据结构的引入111.4 数据结构的基本概念131.4.1 数据结构基本术语131.4.2 数据结构的三个要素131.5 如何设计算法161.5.1 算法的定义及表示方法161.5.2 算法设计与函数设计的关系171.5.3 软件设计描述方法181.5.4 算法设计的一般步骤191.6 如何评价算法的优劣211.6.1 算法的设计要求211.6.2 算法效率的度量方法221.7 算法性能的事前分析方法231.7.1 问题的规模与算法的策略231.7.2 算法效率的上限与下限251.7.3 渐进的上限——算法的时间 复杂度281.7.4 算法时间复杂度的综合讨论291.7.5 算法的空间效率分析方法331.8 算法性能综合考量371.9 本章小结38习题38第2章 结点逻辑关系为线性的结构——线性表412.1 从逻辑结构角度看线性表412.1.1 实际问题中的线性关系412.1.2 线性表的逻辑结构422.2 线性表的存储结构方法之一——顺序表432.2.1 顺序表的存储结构设计432.2.2 顺序表的运算462.2.3 顺序存储结构的讨论532.3 线性表的存储结构方法之二——链表532.3.1 单链表的存储562.3.2 单链表的运算602.3.3 单链表的讨论782.3.4 循环链表782.3.5 双向链表812.3.6 链表小结862.4 线性表的应用举例872.4.1 逆序输出单链表结点值872.4.2 一元多项式的相加882.5 顺序表和链表的比较952.6 本章小结96习题97第3章 运算受限的线性表——栈和队列1003.1 栈——按照先入后出的方式管理的线性表1003.1.1 栈处理模式的引入1003.1.2 栈的逻辑结构1043.1.3 栈的存储结构设计1063.1.4 栈的操作1073.1.5 各种栈结构的比较1233.1.6 栈的应用举例1233.2 队列——按照先入先出方式管理的线性表1323.2.1 队列处理模式的引入1333.2.2 队列的逻辑结构1363.2.3 队列的顺序存储结构1373.2.4 顺序队列的基本操作1483.2.5 队列的链式存储结构1523.2.6 链队列的基本操作1533.2.7 各种队列结构的比较1603.2.8 队列的应用举例1613.3 本章小结171习题172第4章 内容特殊的线性表——多维数组与字符串1754.1 多维数组1754.1.1 数组的概念1754.1.2 数组的存储结构1774.2 矩阵的压缩存储1814.2.1 对称矩阵的压缩存储1824.2.2 三角矩阵的压缩存储1834.2.3 对角矩阵的压缩存储1834.2.4 稀疏矩阵的压缩存储1854.3 字符串1894.3.1 字符串的定义1894.3.2 字符串的存储结构1904.3.3 字符串的查找——模式匹配1954.4 本章小结211习题213第5章 结点逻辑关系分层次的非线性结构——树2165.1 实际问题中的树2165.2 树的逻辑结构2195.2.1 树的定义和基本术语2195.2.2 树的操作定义2225.3 树的存储结构2225.3.1 树的连续存储方式2235.3.2 树的链式存储方式2245.4 二叉树的逻辑结构2265.4.1 二叉树的概念2295.4.2 二叉树的基本性质2305.4.3 二叉树的操作定义2315.5 二叉树的存储结构及实现2315.5.1 二叉树的顺序结构2325.5.2 二叉树的链式存储 结构——二叉链表2355.5.3 建立动态二叉链表2365.6 二叉树结点的查找 问题——树的遍历2405.6.1 树的广度优先遍历2425.6.2 树的深度优先遍历2445.6.3 树的遍历的应用2555.7 树的应用2595.7.1 表达式树2595.7.2 线索二叉树2605.7.3 哈夫曼树及哈夫曼编码2655.8 广义表2785.8.1 广义表的定义2795.8.2 广义表的存储2815.8.3 广义表的基本运算2875.9 本章小结293习题295第6章 结点逻辑关系任意的非线性结构——图2996.1 实际问题中的图及抽象2996.2 图的逻辑结构3046.2.1 图的定义和基本术语3046.2.2 图的操作定义3076.3 图的存储结构及实现3086.3.1 图的数组表示法1—— 邻接矩阵3086.3.2 图的数组表示法2—— 边集数组3106.3.3 图的链表表示法1——邻接表3116.3.4 图的链表表示法2—— 十字链表3166.3.5 图的链表表示法3——邻接多重表3176.3.6 图各种存储结构的归结比较3196.4 图的基本操作3206.4.1 邻接矩阵的操作3206.4.2 邻接表的操作3226.5 图的顶点查找问题——图的遍历3286.5.1 图的广度优先遍历BFS3296.5.2 图的深度优先遍历DFS3346.5.3 图的遍历小结3406.6 图的经典应用——图中的树问题3406.6.1 生成树3426.6.2 最小生成树MST3436.6.3 求最小生成树算法1——Prim 算法3446.6.4 求最小生成树算法2——Kruskal算法3496.6.5 生成树算法小结3566.7 图的经典应用——最短路径问题3576.7.1 最短路径问题的引入3576.7.2 单源最短路径算法——Dijkstra算法3596.7.3 各顶点对间最短路径算法——Floyd算法3646.7.4 最短路径问题小结3696.8 图的经典应用——活动顶点与活动边的问题3706.8.1 图的活动顶点排序问题的引入3706.8.2 AOV网与拓扑排序——活动顶点排序问题3736.8.3 AOE网与关键路径——活动边最长问题3786.8.4 活动顶点与活动边问题小结3906.9 本章小结390习题391第7章 数据的处理方法——排序技术3977.1 概述3977.1.1 排序的基本概念3977.1.2 排序算法的分类3997.2 插入排序3997.2.1 直接插入排序3997.2.2 希尔排序4027.3 交换排序4047.3.1 冒泡排序4047.3.2 快速排序4067.4 选择排序4097.4.1 简单选择排序4107.4.2 堆排序4117.5 归并排序4157.6 分配排序4187.6.1 桶排序4187.6.2 基数排序4217.7 各种排序算法的比较4247.8 本章小结427习题428第8章 数据的处理——索引与查找技术4318.1 索引的基本概念4338.1.1 索引的定义4338.1.2 索引的逻辑特征4348.1.3 索引的主要操作4358.2 线性索引技术4358.2.1 稠密索引4358.2.2 分块索引4368.2.3 多重表4378.2.4 倒排表4398.3 树形索引4418.3.1 二叉排序树4418.3.2 B树4488.4 查找概述4528.4.1 查找的基本概念4528.4.2 查找算法的性能4538.5 线性表的查找技术4538.5.1 顺序查找4538.5.2 有序表查找4548.5.3 索引查找4598.6 树表的查找技术4618.6.1 二叉排序树4618.6.2 B树4628.6.3 在非数值有序表上的查找——字典树4628.7 散列表的查找技术4648.7.1 散列概述4658.7.2 散列函数的设计4678.7.3 处理冲突的方法4698.7.4 散列查找的性能分析4738.8 本章小结474习题476第9章 经典算法4799.1 递归算法4799.1.1 递归的概念及要素4799.1.2 递归的应用场景4819.1.3 递归的计算机实现4829.1.4 递归方法特点分析4839.1.5 递归算法实例4859.1.6 递归小结4879.2 分治算法4879.2.1 分治是什么4879.2.2 分治法的适用条件4889.2.3 分治问题的类型4889.2.4 分治法小结4909.3 动态规划4919.3.1 什么是动态规划4919.3.2 动态规划的解题方法4939.3.3 动态规划解题实例4959.3.4 动态规划小结5009.4 贪心算法5019.4.1 贪心算法是什么5019.