# 《数据结构——Python语言描述》
这本书的解说步骤非常细致，作为高校的教程是非常合适的，不过缺少相关的练习平台和细致的源码实现会比较吃力。接下来的一年多的时间里，我都会跟数据结构和算法死磕到底，争取开源一本全面的Python数据结构读本，加油鸭！！
阅读：2020年8月2日
耗时：3小时31分
# 第1章 绪论
数据结构是相互之间存在一种或多种特定关系的数据元素的集合，通常包括数据的逻辑结构和存储结构两个层次，逻辑结构是从具体问题抽象出来的数学模型，是从逻辑关系上描述数据，并不涉及数据在计算机中的存储。
逻辑结构：
- 集合
- 线性结构
- 树形结构
- 图、网状结构
存储结构：
- 顺序存储结构
- 链式存储结构
- 索引存储结构
- 哈希、散列存储结构
抽象数据类型：
ADT抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}
算法是对待特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
- 有穷性
- 确定性
- 可行性
- 输入
- 输出
# 第2章 线性表
线性表是由若干个具有相同特性的数据元素组成的有限序列。
- 线性表中的元素个数一定是有限的
- 线性表中的所有元素具有相同的性质
- 线性表中除表头元素以外，其他所有元素都有唯一的直接先驱元素
- 线性表中除表尾元素以外，其他所有元素都有唯一的直接后继元素
顺序表
链表：单链表、循环单链表、双链表、循环双链表
每个结点可分为数据域和指针域两个部分，数据域可用于存储数据元素，指针域可用于存储下一结点的地址。
# 第3章 栈、队列和递归
栈是一种只能在一端进行操作的线性表，它最大的特点是进行数据操作时必须遵循“后进先出”(Last In FirstOut, LIFO)的原则。
队列：与栈一样，队列也是一种特殊的线性表，不同的是，队列在进行数据操作时必须遵循“先进先出”（Firstin Firstout, FIFO）的原则，这一特点决定了队列的基本操作需要在其两端进行。
递归：在程序设计中，我们把某一过程或函数调用自身称为递归。若该过程或函数直接调用自身，称为直接递归；否则均称为间接递归。
递归算法的优点是结构简单、逻辑清晰，并且易于阅读；而其缺点是效率低下，所需的内存空间较多，优化十分困难。那么递归算法适用于解决什么样的问题呢？一般来说，对于某一问题，至少要满足一下3个条件才可以在计算机中使用递归来求解。
- 待解决问题可以被分解为规模更小但和原问题有着相同解法的子问题。
- 子问题的个数必须是有限的，相应地，递归调用的次数也必须是有限的。
- 子问题是可解的，即必须存在递归出口。
# 第4章 串、数组和广义表
BF算法和KMP算法
# 第5章 树、二叉树和森林
非线性结构：是指在该结构重通常存在一个数据元素，有两个或两个以上的直接先驱（或直接后继）元素。
树的遍历：
- 先序遍历：访问根节点、按照从左到右的顺序先序遍历根节点的每一棵子树
- 后序遍历：按照从左到右的顺序后序遍历根节点的每一棵子树、访问根节点
- 层次遍历：从根节点开始，按节点所在的层次从小到大、同一层从左到右的次序访问树中的每一个节点
二叉树遍历：
- 先序遍历
- 中序遍历
- 后序遍历
- 层次遍历
先序遍历的非递归算法
计算中缀表达式的值
森林是由若干棵树组成的集合。
哈夫曼树、最优二叉树
# 第6章 图
- 无向图
- 有向图
- 完全图
简单路径：给定一条路径，若该路径对应的序列中的顶点不重复出现，则称该路径为简单路径。
回环：若某一路径中的第一个顶点和最后一个顶点相同，则称该路径为回环。
简单回环：在某一回路中，若除第一个顶点和最后一个顶点外，其余顶点均不重复，则称该回路为简单回路。
强连通图：在有向图中，若对于任意两个顶点v和v1，都存在从v1到v的路径，则称这样的有向图为强连通图。
最小生成树：通常把各边带权的连通图称为连同网，在某一连通网的所有生成树中，对每一棵生成树的各边权值求和，并找出权值之和最小的生成树，这一生成树被称为该连通网的最小生成树。
图的遍历：
- 深度优先遍历
- 广度优先遍历
由于通常情况下图的邻接表并不是唯一的，因此广度优先遍历图时各顶点被访问的顺序可能不同。
Prim算法和kruskal算法
最短路径：Dijkstra和Floyd算法
拓扑排序
# 第7章 查找
- 顺序查找
- 折半查找
- 索引查找
- 平衡二叉树查找：要么是空树，要么满足每个节点的左子树和右子树的深度之差的绝对值不超过1，每个节点的左子树和右子树均是一棵平衡二叉树。
- B-树查找
- 哈希表查找
# 第8章 内排序
内排序：整个排序过程完全在内存中进行。
外排序：因数据量过大需要借助外部存储设备才能完成的排序。
待排序的存储方式：
- 顺序存储
- 链式存储
- 地址存储
插入排序
折半插入排序
希尔排序
表插入排序
交换排序
- 冒泡排序
- 快速排序
选择排序
- 简单选择排序
- 树形选择排序
- 堆排序
归并排序
基数排序
# 第9章 外排序
多路平衡归并、败者树和最佳归并树。