数据结构和算法

一、概念

1、算法：

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

2、算法的五大特性：

输入: 算法具有0个或多个输入
输出: 算法至少有1个或多个输出
有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
确定性：算法中的每一步都有确定的含义，不会出现二义性
可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成

3、怎么衡量算法效率？算法的复杂度

单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的！
算法的复杂度分为时间复杂度和空间复杂度。

用“大O记法”来表示算法的时间复杂度

时间复杂度：

假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度，记为T(n)

“大O记法”：

对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)<=c*g(n)，就说函数g是f的一个渐近函数（忽略常数），记为f(n)=O(g(n))。也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似。

理解：

对于算法进行特别具体的细致分析虽然很好，但在实践中的实际价值有限。对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如，可以认为3n2和100n2属于同一个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的效率“差不多”，都为n2级。

我们主要关注算法的最坏情况，亦即最坏时间复杂度，算法完成工作最多需要多少基本操作。

时间复杂度的几条基本计算规则：

基本操作，即只有常数项，认为其时间复杂度为O(1)

顺序结构，时间复杂度按加法进行计算

循环结构，时间复杂度按乘法进行计算

分支结构，时间复杂度取最大值

判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略

在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度

常见时间复杂度

执行次数函数举例	阶	非正式术语
12	O(1)	常数阶
2n+3	O(n)	线性阶
3n2+2n+1	O(n2)	平方阶
5log2n+20	O(logn)	对数阶
2n+3nlog2n+19	O(nlogn)	nlogn阶
6n3+2n2+3n+4	O(n3)	立方阶
2n	O(2n)	指数阶

所消耗的时间从小到大：

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

list内置操作的时间复杂度

dict内置操作的时间复杂度

算法所耗费的存储空间——空间复杂度

空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。

4、数据结构

数据结构指数据对象中数据元素之间的关系。

Python的内置数据结构：列表、元组、字典...

Python的扩展数据结构：如栈，队列 ...

5、算法和数据结构的关系

数据结构只是静态的描述了数据元素之间的关系。

高效的程序需要在数据结构的基础上设计和选择算法。

——算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体 。

6、抽象数据类型

指一个数学模型以及定义在此数学模型上的一组操作，即把数据类型和数据类型上的运算捆在一起，进行封装。

最常用的数据运算：插入、删除、修改、查找和排序。

二、线性表

一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。

线性表的两种实现模型：顺序表、链表。

（1）、顺序表

将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。

1、顺序表的形式

元素本身连续存储
元素外置外置存储

2、顺序表的结构

元素集合信息
表的整体情况的信息：容量、元素个数。

3、顺序表的实现

一体式结构 ：整体性强，易于管理；但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。

分离式结构 ：表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联

元素存储区替换：一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了；分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。

元素存储区扩充策略：

每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。

特点：节省空间，但是扩充操作频繁，操作次数多。
每次扩充容量加倍，如每次扩充增加一倍存储空间。

特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。

4、顺序表的操作

尾端加入删除元素，时间复杂度为O(1)
非保序的元素加入删除，时间复杂度为O(1)
保序的元素加入删除，时间复杂度为O(n)

5、Python中的顺序表

list: 一种采用分离式技术实现的动态顺序表
tuple

（2）、链表

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

将元素存放在通过链接构造起来的一系列存储块中。

1、单向链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

表元素域elem用来存放具体的数据。
链接域next用来存放下一个节点的位置（python中的标识）
变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

单链表的操作:

is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos, item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在

2、双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

双向链表操作:

is_empty() 链表是否为空
length() 链表长度
travel() 遍历链表
add(item) 链表头部添加
append(item) 链表尾部添加
insert(pos, item) 指定位置添加
remove(item) 删除节点
search(item) 查找节点是否存在

3、单向循环链表

单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。

单向循环链表操作:

is_empty() 判断链表是否为空
length() 返回链表的长度
travel() 遍历
add(item) 在头部添加一个节点
append(item) 在尾部添加一个节点
insert(pos, item) 在指定位置pos添加节点
remove(item) 删除一个节点
search(item) 查找节点是否存在

(3)链表与顺序表的对比

链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。

链表与顺序表的各种操作复杂度如下所示：

操作	链表	顺序表
访问元素	O(n)	O(1)
在头部插入/删除	O(1)	O(n)
在尾部插入/删除	O(n)	O(1)
在中间插入/删除	O(n)	O(n)

虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。

三、栈

栈（stack），是一种容器，可存入数据元素、访问元素、删除元素。任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

栈可以用顺序表实现，也可以用链表实现。

栈的操作：

Stack() 创建一个新的空栈
push(item) 添加一个新的元素item到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈的元素个数

四、队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

同栈一样，队列也可以用顺序表或者链表实现。

队列的操作：

Queue() 创建一个空的队列
enqueue(item) 往队列中添加一个item元素
dequeue() 从队列头部删除一个元素
is_empty() 判断一个队列是否为空
size() 返回队列的大小

五、双端队列

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

双端队列操作：

Deque() 创建一个空的双端队列
add_front(item) 从队头加入一个item元素
add_rear(item) 从队尾加入一个item元素
remove_front() 从队头删除一个item元素
remove_rear() 从队尾删除一个item元素
is_empty() 判断双端队列是否为空
size() 返回队列的大小

六、排序

排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定顺序进行排列的一种算法。

冒泡排序：O(n) - O(n2) 稳定

选择排序：O(n2) - O(n2) 不稳定

插入排序：O(n) - O(n2) 稳定

快速排序：：O(nlogn) -O(n2) 不稳定

希尔排序：？-O(n2) 不稳定

归并排序：O(nlogn) 稳定

常见排序算法效率比较：

七、搜索

搜索的几种常见方法：顺序查找、二分法查找、二叉树查找、哈希查找

二分法查找：

有点：比较次数少，查找速度快，平均性能好

缺点：要求待查表为有序表，且插入删除困难

适用：不经常变动而查找频繁的有序列表

最优时间复杂度：O(1)

最坏时间复杂度：O(logn)

八、树和树算法

树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。

（1）特点：

每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；

（2）概念：

节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
叶节点或终端节点：度为零的节点；
父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；
堂兄弟节点：父节点在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m（m>=0）棵互不相交的树的集合称为森林；

（3）种类：

无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；

有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；

二叉树：每个节点最多含有两个子树的树称为二叉树；
- 完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
- 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
- 排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）；
霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

（4）二叉树

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）

特性：

性质1: 在二叉树的第i层上至多有2^(i-1)个结点（i>0）

性质2: 深度为k的二叉树至多有2^k - 1个结点（k>0）

性质3: 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;

性质4:具有n个结点的完全二叉树的深度必为 log2(n+1)

性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

遍历：

深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。

1、深度优先遍历

对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。那么深度遍历有重要的三种方法。这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历（preorder），中序遍历（inorder）和后序遍历（postorder）。

先序遍历 在先序遍历中，我们先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树：根节点->左子树->右子树

def preorder(self, root):
      """递归实现先序遍历"""
      if root == None:
          return
      print root.elem
      self.preorder(root.lchild)
      self.preorder(root.rchild)

中序遍历 在中序遍历中，我们递归使用中序遍历访问左子树，然后访问根节点，最后再递归使用中序遍历访问右子树：左子树->根节点->右子树

def inorder(self, root):
      """递归实现中序遍历"""
      if root == None:
          return
      self.inorder(root.lchild)
      print root.elem
      self.inorder(root.rchild)

后序遍历 在后序遍历中，我们先递归使用后序遍历访问左子树和右子树，最后访问根节点 左子树->右子树->根节点

def postorder(self, root):
      """递归实现后续遍历"""
      if root == None:
          return
      self.postorder(root.lchild)
      self.postorder(root.rchild)
      print root.elem

2、广度优先遍历

从树的root开始，从上到下从从左到右遍历整个树的节点

def breadth_travel(self):
        """利用队列实现树的层次遍历"""
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print node.elem,
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)