数据结构（Python+Java）（微课版）

本书在内容上着重阐述计算机中存储、组织数据的方式与计算机程序解决问题的步骤，同时对数据结构与算法中的典型案例进行讲解，在程序实现中使用Java与Python两种语言对照表述。本书共8章，第1章是数据结构与算法概论，主要介绍数据结构和算法的基本概念；第2、3章是线性表与栈和队列，这部分介绍简单的数据结构类型及操作算法；第4章是递归，这是数据结构中重要的操作算法；第5、6章是树与图，这部分介绍较为复杂的数据结构及操作算法；第7、8章是排序与查找，这部分主要介绍各种常见算法、优化存储结构的思想。 本书可作为应用型本科院校和职业院校计算机相关专业的教材，也可作为各类计算机培训机构的教材。

蒋理，男，汉族，1982年出生，江苏南京人，工学硕士，南京信息职业技术学院讲师。主要研究方向：大数据分析与可视化。长期从事软件技术专业教学与研究工作，参与完成4项教学研究项目，主持与参与完成课程建设2项，曾在省级教学能力比赛中获二等奖。主持与参与完成5项软件系统研发项目，在省级以上期刊发表论文11篇，申请软件著作权7项。指导学生在“中国软件杯”等专业比赛中数次获奖，还曾指导学生在“挑战杯”，“互联网+”等创新创业类比赛中获奖。

第 1章 数据结构与算法概论　1 1.1 问题求解　1 1.1.1 计算机解决问题的步骤　1 1.1.2 非数值数学模型　3 1.2 数据结构概述　5 1.2.1 数据结构的相关概念　5 1.2.2 抽象数据类型　7 1.3 算法概述　9 1.3.1 算法及其特性　9 1.3.2 算法设计的要求　10 1.3.3 算法描述方法　10 1.3.4 算法评价　10 本章小结　13 本章习题　13 第 2章 线性表　14 2.1 线性表的概念　14 2.2 线性表的顺序存储结构　15 2.2.1 顺序表的概念　15 2.2.2 顺序表的操作　15 2.3 线性表的链式存储结构　18 2.3.1 链表的概念　18 2.3.2 单向链表　19 2.3.3 双向链表　23 2.4 线性表特点与比较　27 2.4.1 线性表的特点　27 2.4.2 顺序表与链表的比较　27 2.4.3 单向链表与双向链表的比较　28 2.5 线性表的应用　28 2.5.1 多项式的合并　28 2.5.2 稀疏矩阵的表示　30 2.5.3 约瑟夫问题　32 本章小结　33 本章习题　34 第3章 栈和队列　35 3.1 栈　35 3.1.1 栈的定义与基本操作　35 3.1.2 栈的顺序存储结构与实现　36 3.1.3 栈的链式存储结构与实现　39 3.1.4 顺序栈和链栈的比较　41 3.1.5 栈的应用案例　41 3.2 队列　44 3.2.1 队列的定义与基本操作　44 3.2.2 队列的顺序存储结构与实现　45 3.2.3 队列的链式存储结构与实现　49 3.2.4 循环队列与链队列的比较　51 3.2.5 队列的应用案例　51 本章小结　55 本章习题　56 第4章 递归　57 4.1 递归定义　57 4.2 递归算法设计　57 4.3 消除递归　60 4.3.1 直接转换法　60 4.3.2 间接转换法　61 4.4 回溯法　62 4.5 递归的评价　65 本章小结　66 本章习题　66 第5章 树　68 5.1 树的概念　68 5.1.1 树的定义　68 5.1.2 树的相关概念　68 5.1.3 树的表示　69 5.2 二叉树　70 5.2.1 二叉树的概念　70 5.2.2 二叉树的性质　72 5.2.3 二叉树的存储　72 5.2.4 二叉树的遍历　74 5.3 树、森林与二叉树　76 5.3.1 树的存储　76 5.3.2 树与二叉树的转换　78 5.3.3 森林与二叉树的转换　79 5.3.4 树的遍历　80 5.4 哈夫曼树　81 5.4.1 哈夫曼树的相关概念　81 5.4.2 哈夫曼算法　84 5.4.3 哈夫曼编码　85 5.5 堆　86 5.5.1 堆的概念　86 5.5.2 堆的操作　87 5.5.3 堆的算法分析　92 本章小结　93 本章习题　93 第6章 图　95 6.1 图的概念　95 6.1.1 图的相关术语　95 6.1.2 图的存储结构　97 6.2 图的遍历　101 6.2.1 深度优先遍历　101 6.2.2 广度优先遍历　102 6.3 图的应用　104 6.3.1 最小生成树　104 6.3.2 拓扑排序问题　106 6.3.3 关键路径问题　109 6.3.4 最短路径问题　110 本章小结　118 本章习题　118 第7章 排序　120 7.1 排序的概念　120 7.2 插入排序　120 7.2.1 直接插入排序　120 7.2.2 希尔排序　122 7.3 交换排序　122 7.3.1 冒泡排序　122 7.3.2 快速排序　124 7.4 选择排序　125 7.4.1 简单选择排序　125 7.4.2 堆排序　127 7.5 归并排序　130 7.6 排序算法比较　131 本章小结　132 本章习题　132 第8章 查找　133 8.1 查找的概念　133 8.2 线性表查找　134 8.2.1 顺序查找　134 8.2.2 二分查找　135 8.2.3 分块查找　137 8.3 树表查找　138 8.3.1 二叉排序树的节点　139 8.3.2 二叉排序树的查找　139 8.3.3 二叉排序树的插入　140 8.3.4 二叉排序树的构造　141 8.3.5 二叉排序树的删除　143 8.4 散列表查找　144 8.4.1 散列查找　145 8.4.2 散列函数　145 8.4.3 冲突处理　147 8.4.4 查找性能分析　149 本章小结　150 本章习题　150