http://www.tianjun.ml/essays/58
（6）一起用python之基础篇——数据结构
Posted on: 2014-08-27 19:58
Posted in : 一起用python,
(撰写中。。。呃，写着写着，发觉其实原书写得很系统，一环扣一环，我这样子抽出来一点点地分析反而打乱了原有的结构。我这里写的，大致看下就好，不多说了，反正如果学习Python和数据结构的话，这本书非常非常推荐！）
写在前面
本来，这部分计划在几个月前就完成的，无奈这中间忙其它事去了，断断续续地写了一点点。现在刚好闲下来了，争取正式在实验室开始干活之前把这部分写完。加油~
依照以往学习编程语言的经验，在熟悉了语言的基本语法和标准库的应用后，需要进一步深入到底层基本数据结构。一方面深入理解python中常用的数据类型是怎么实现的，另一方面通过自己实现这些基本数据结构来掌握python中类的写法。 于是我大致找了一下python下数据结构方面的书，对比后发现Data Structures and Algorithms in Python这本书灰常好。其优点在于，非常适合本人的学习路线（粗略熟悉了python的使用，但是缺乏深入了解），而且本书的前面几章提供了很好的过渡。此外，对于各种类型的数据结构，作者都提供了完整的实现，可以说是学习的典范。当然，要说不足之处，就是最后图论部分内容稍微简略了一些。不过，考虑到本书已经七百多页，这部分从简是有道理的。个人觉得本书更侧重于数据结构部分，如果你只是想学习怎样用python实现基本的算法，可以参考这本书Python Algorithms - Mastering Basic Algorithms in the Python Language,胡家威同学写了个系列的，很值得一看http://hujiaweibujidao.github.io/python/。
导读
以下内容可以看做是Data Structures and Algorithms in Python这本书的导读。我会指出各章节中的一些亮点和核心内容。
Ch1 Python 基础知识
这部分对Python的基本语法做了一个简单的描述，主要目的是让本书的读者在一个相同的起跑线上，方便后面的内容展开。
Ch2 面向对象编程
首先谈到了面向对象的设计模式，然后以一个例子讲解了Python中如何定义一个类，以及类与类之间的继承关系。最后介绍了Python中类内的变量管理。
Ch3 算法分析基础
这部分几乎是算法书必备的内容。介绍如何分析算法的复杂度。
Ch4 递归
在开始讲数据结构之前，作者先介绍了一下递归的思想，个人感觉这个章节的安排稍微有些唐突，不过，也算是为后面做铺垫吧。作者对于递归的分类很有启发意义。
Ch5 基于Array的序列
忘掉Python下常用的list等等数据结构吧，作者先从最最基础的ctypes下的array结构开始构造类似于list的动态序列数据类型。这将为大家理解list类型奠定良好基础。C语言基础很好的话理解起来会很快。
Ch6 栈、队列与双向队列
作者从ADT（Abstract Data Type）出发，在前面实现的基于Array的序列基础上，实现了栈、队列、双向队列这三种数据结构。
Ch7 链表
该部分将前面已经实现的三种数据结构糅合在一起，在介绍了链表后，通过链表来实现上一章提到的集中数据结构。
Ch8 树
从树，再到二叉树，然后深入其中，借用Array序列和链表来实现树这个类。最后介绍了遍历树的简单算法。
Ch9 优先队列
同样，这部分先是介绍了优先队列后，分别用有序列表和无序列表实现了优先队列。然后由此引出了堆。再根据优先队列中的排序问题分别分析了选择排序、插入排序以及堆排序。
Ch10 Map、哈希表以及跳表
这部分内容的重点是介绍了Hash的思想。此外作者跳出Python下常用的字典类型，对Map进行了不同的分类并实现。
Ch11 搜索树
这部分内容主要围绕平衡树展开，介绍了AVL、红黑树等等。
Ch12 排序与选择
尽管前面已经提到了集中排序算法，这里作者补充了并排、快排以及桶排序等等算法并做了比较。
Ch13 文本处理
该部分主要是字符串查找的优化，重点分析了动态问题编程的思想。该部分还介绍了trie树（字典树）
Ch14 图
该部分虽然简短，但覆盖面广，包含了图的结构、图的遍历、最短路径以及最小生成树等等。需要参考其他书作为补充。
Ch15 内存管理与B树
介绍了Python中内存管理体系（内存分配，垃圾回收，缓存机制等等），并介绍了B树。