每日分享

Good judgment comes from experience, and a lot of that comes from bad judgment.

好的判断力来自经验，而其中很多也来自坏的判断力。

小闫语录：

一个人的成长来自于摸爬滚打、跌跌撞撞。敢于试错，这是一个不断完善自身的过程，是为将来做铺垫的过程。二十多岁的年纪，一无所有，失败后最坏的结果无非是重新回到一无所有。那么你还怕什么？这本身就是对你有利的一场赌局，看你敢不敢上了。

python技术面试题(十六)--数据结构与算法

本文的一些例子是大开脑洞的结果，肯定有不严谨的地方，大家理解意思即可，毕竟小编不是圣人。

1.链表

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

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

举个栗子：4个小伙伴（B是A的朋友，C是B的朋友，D是C的朋友。是挺尴尬哈.......）去电影院买票，正好有四个连座，他们很开心，然后很自然的A挨着B，B挨着C....就这么坐了，愉快的看了场『霸王别姬』。这就是顺序表。

第二天，又想看电影了，但是很不凑巧，只剩下几个散座了，他们商量了一下，还是买了吧，毕竟『飞驰人生』挺好看的，然后他们就拿着票分开坐了。由于前面提到的尴尬关系，A手机里有B的联系方式，B手机里有C的联系方式.....虽然没挨着，但是他们都有朋友的联系方式，知道朋友在哪里坐着。这就是链表。

链表呢，又分为了单向链表、双向链表、单向循环链表。我们下面看看它们分别是什么样子的。

1.1单向链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。就像我们上面的那个甜栗子，4个尴尬的朋友分开坐的那种情况，如果A手机里有B的手机号，但是B手机里没有A的，B手机里有C的手机号，但是C没有B的....也就是只有从A开始，他们才能找到所有人，这就是单向链表。

表元素域elem用来存放具体的数据。

链接域next用来存放下一个节点的位置（python中的标识）。也就是例子中存放他们的联系方式的手机。

变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

1.1.1单向链表的操作

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

1.1.2链表和顺序表的对比

链表的优点就是，四个小伙伴即使没有连座了，也能看上电影，对于存储空间的使用相对灵活。但是缺点也显而易见，那就是他们想联系别人，需要用手机存朋友的手机号，而保存手机号浪费了手机的内存（16G的手机伤不起啊）。链表增加了结点的指针域，空间开销大一丢丢。而且，如果他们连着坐，想找谁直接就找到了，而分开坐的话，不能随机找，只能从A开始一个接一个的找。链表失去了顺序表随机读取的优点。

1.2双向链表

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

看到单向链表例子的时候，你一定心里想：这四个傻缺，A手机存B的手机号，B怎么就不存A的？也许听到了你骂他们吧。现在B也存了A的手机号，C也存了B的手机号，D也存了C的手机号。

咱们现在屡屡哈，有点乱。现在那四个小伙伴是这么个状态：A和B互为盆友，B和C互为盆友，C和D互为盆友，盆友之间彼此都存了对方的手机号（A、B、C、D是4个人，没错.....）。他们又没买到连座的票，然后就分开坐了，现在他们的状态就是双向链表。

1.2.1双向链表的操作

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

1.3单向循环链表

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

还是那4个小伙伴，都是『表面兄弟』。B删了A的手机号（B心里想：浪费我16G华为手机的内存，你能联系到我不就好了吗？）；C也这么想，删除了B的手机号；巧了，D也把C的手机号删了。回到了单向链表的状态（A有B的联系方式，B有C的联系方式，C有D的联系方式）。都看了这么多场电影了，D看上了A（是个甜甜的妹子），然后D要了A的手机号，保存了下来，哈哈哈哈，活该B单身，还删小姑娘的手机号（笑出了猪一般可爱的声音.....）。

现在他们的状态就是单向循环链表了。

2.二叉树

二叉树大家一定都不陌生，就是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。下面的这样子就是二叉树。

为什么我的公众号文章里很少插图。有人说全是干货，有人说文字表达能力强，有人说是怕读者眼晕.......其实吧.....我只是懒得画图......这张图还是从未知网页download下来的。

二叉树的性质

性质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)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

2.1 广度、深度的计算

import queue
class Node:
    def __init__(self,value=None,left=None,right=None):
        self.value=value
        self.left=left
        self.right=right
def treeDepth(tree):
    if tree==None:
        return 0
    leftDepth=treeDepth(tree.left)
    rightDepth=treeDepth(tree.right)
    if leftDepth>rightDepth:
        return leftDepth+1
    if rightDepth>=leftDepth:
        return rightDepth+1
def treeWidth(tree):
    curwidth=1
    maxwidth=0
    q=queue.Queue()
    q.put(tree)
    while not q.empty():
        n=curwidth
        for i in range(n):
            tmp=q.get()
            curwidth-=1
            if tmp.left:
                q.put(tmp.left)
                curwidth+=1
            if tmp.right:
                q.put(tmp.right)
                curwidth+=1
        if curwidth>maxwidth:
            maxwidth=curwidth
    return maxwidth
if __name__=='__main__':
    root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
    depth=treeDepth(root)
    width=treeWidth(root)
    print('depth:',depth)
    print('width:',width)

2.2 二叉树的遍历

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有节点的访问称为遍历（traversal）。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。

2.2.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.2.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)

3.栈

栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。就好像咱们在Redis中的列表， lpush操作放进去元素，最后 lrange取的时候变成了倒序。忘了？没关系，给你讲小故事啊。

如果是在北京，一定体验过早晚高峰，挤地铁的痛苦吧？那个酸爽。有时，好不容易到站了，要下车，硬生生又被挤上了车！！！！告诉你们个秘密，我上地铁，从来都是靠着门口侧边的栏杆，因为我怕下不去车，哈哈哈哈哈。跑偏了，这不是介绍生活小妙招，是要讲栈。

举一个不严谨的例子，地铁的一节车厢每到一站只开一个门，这就是栈。大家都挤上去了，下车的时候一定是最后上的那个先下（不管你到没到站）。

3.1栈的操作

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