数据结构+算法

算法

就是对问题进行处理且求解的一种实现思路或者思想。

什么是计算机科学？

首先明确的一点就是计算机科学不仅仅是对计算机的研究，虽然计算机在科学发展的过程中发挥了重大的作用，但是它只是一个工具，一个没有灵魂的工具而已。所谓的计算机科学实际上是对问题、解决问题以及解决问题的过程中产生产生的解决方案的研究。例如给定一个问题，计算机科学家的目标是开发一个算法来处理该问题，最终得到该问题的解、或者最优解。所以说计算机科学也可以被认为是对算法的研究。因此我们也可以感受到，所谓的算法就是对问题进行处理且求解的一种实现思路或者思想。

如何形象化的理解算法

一个常胜将军在作战之前都会进行战略的制定，目的是为了能够在最短的时间切成本消耗最低的情况下获取最终的胜利。如果将编码作为战场，则程序员就是这场战役的指挥官，你如何可以将你的程序可以在最短且消耗资源最小的情况下获取最终的执行结果呢？算法就是我们的策略！

意义

•  数据结构和算法思想的通用性异常的强大，在任何语言中都被使用，它们将会是我们编码生涯中伴随我们最长久利器（左膀右臂）。有一定经验的程序员最终拼的就是算法和数据结构
  
  
• 数据结构和算法思想也可以帮助我们拓展和历练编码的思维，可以让我们更好的融入到编程世界的角角落落。

什么是算法分析？

两组程序都是用来解决同一个问题的，但是两组程序看起来又各不相同，那么哪一组程序更好呢？

评判程序优劣的方法

•  消耗计算机资源和执行效率（无法直观）
• 计算算法执行的耗时（不推荐，因为会受机器和执行环境的影响）
• 时间复杂度（推荐）

时间复杂度

• 评判规则：量化算法执行的操作/执行步骤的数量
• 最重要的项：时间复杂度表达式中最有意义的项

 常见的时间复杂度：

• O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

数据结构

•  概念：对于数据（基本类型的数据（int,float,char））的组织方式就被称作为数据结构。数据结构解决的就是一组数据如何进行保存，保存形式是怎样的。
  
  
• 使用不同的形式组织数据，在基于查询时的时间复杂度是不一样的。因此认为算法是为了解决实际问题而设计的，数据结构是算法需要处理问题的载体。

 timeit模块(执行速度)

概念

• timeit模块：该模块可以用来测试一段python代码的执行速度/时长。
• Timer类：该类是timeit模块中专门用于测量python代码的执行速度/时长的。原型为：class timeit.Timer(stmt='pass',setup='pass')。
  
  • stmt参数：表示即将进行测试的代码块语句。
  • setup：运行代码块语句时所需要的设置。
  • timeit函数：timeit.Timer.timeit(number=100000),该函数返回代码块语句执行number次的平均耗时。

例子

from timeit import Timer
def test01():
    alist = []
    for i in range(1000):
        alist.append(i)
    return alist
def test02():
    alist = []
    for i in range(1000):
        alist.insert(0,i)
    return alist
def test03():
    alist = []
    for i in range(1000):
        alist += [i]
    return alist
def test04():
    alist = list(range(1000))
    return alist
if __name__ == '__main__':
    t1 = Timer('test01()','from __main__ import test01')
    print(t.timeit(1000))
    
    t2 = Timer('test02()','from __main__ import test02')
    print(t1.timeit(1000))
    
    t3 = Timer('test03()','from __main__ import test03')
    print(t1.timeit(1000))
    
    t4 = Timer('test04()','from __main__ import test04')
    print(t1.timeit(1000))

栈

特性

• 先进后出的数据结构
• 栈顶,栈尾

应用

每个 web 浏览器都有一个返回按钮。当你浏览网页时，这些网页被放置在一个栈中（实际是网页的网址）。你现在查看的网页在顶部，你第一个查看的网页在底部。如果按‘返回’按钮，将按相反的顺序浏览刚才的页面。

　　

方法

• Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。
• push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
• pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
• peek() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。
• isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。
• size() 返回栈中的 item 数量。不需要参数，并返回一个整数。

class Stack():
    def __init__(self):
        self.items = []
    def push(self,item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return len(self.items)-1
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.isEmpty())
print(stack.pop())
print(stack.pop())
print(stack.pop())

结果:
False
3
2
1

队列

特性

• 先进先出

应用

• 我们的计算机实验室有 30 台计算机与一台打印机联网。当学生想要打印时，他们的打印任务与正在等待的所有其他打印任务“一致”。第一个进入的任务是先完成。如果你是最后一个，你必须等待你前面的所有其他任务打印

方法

• Queue() 创建一个空的新队列。 它不需要参数，并返回一个空队列。
• enqueue(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。
• dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。
• isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。
• size() 返回队列中的项数。它不需要参数，并返回一个整数。

class Queue():
    def __init__(self):
        self.items = []
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

结果:
1
2
3

案例：烫手的山芋

• 烫手山芋游戏介绍：6个孩子围城一个圈，排列顺序孩子们自己指定。第一个孩子手里有一个烫手的山芋，需要在计时器计时1秒后将山芋传递给下一个孩子，依次类推。规则是，在计时器每计时7秒时，手里有山芋的孩子退出游戏。该游戏直到剩下一个孩子时结束，最后剩下的孩子获胜。请使用队列实现该游戏策略，排在第几个位置最终会获胜。

class Queue():
    def __init__(self):
        self.items = []
    def enqueue(self,item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def size(self):
        return len(self.items)
#初始化了六个孩子
kids = ['A','B','C','D','E','F']
#将六个孩子加入到队列中
q = Queue()
for kid in kids:
    q.enqueue(kid)
while q.size() > 1:
    #山芋传递的次数（6）是不变的，每次传递队列中孩子的占位会发生变化
    for i in range(6):
        kid = q.dequeue()
        q.enqueue(kid)
    q.dequeue()
print(q.dequeue())

双端队列

• 同同列相比，有两个头部和尾部。可以在双端进行数据的插入和删除，提供了单数据结构中栈和队列的特性
• Deque() 创建一个空的新 deque。它不需要参数，并返回空的 deque。
• addFront(item) 将一个新项添加到 deque 的首部。它需要 item 参数 并不返回任何内容。
• addRear(item) 将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。
• removeFront() 从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。
• removeRear() 从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。
• isEmpty() 测试 deque 是否为空。它不需要参数，并返回布尔值。
• size() 返回 deque 中的项数。它不需要参数，并返回一个整数。

class Deque():
    def __init__(self):
        self.items = []
    def addFont(self,item):
        self.items.insert(0,item)
    def addRear(self,item):
        self.items.append(item)
    def removeFont(self):
        return self.items.pop()
    def removeRear(self):
        return self.pop(0)

• 双端队列应用案例：回文检查
  • 回文是一个字符串，读取首尾相同的字符，例如，radar toot madam。

内存

计算机的作用

用来计算和存储二进制的数据

问题：计算机如何计算1+2

• 转换成二进制的数值
• 在计算机中开辟两块内存空间
• 将1和2存储到这两块内存空间中

变量的概念

• 变量就是引用。变量其实表示的就是计算机中的一块内存。
  • 严谨：变量起始就是内存地址
• 一块内存空间会有两个默认的属性：
  • 空间大小　　

    • bit：位
      byte：字节
      kb：1020字节
      mb
      gb
      tb

  • 内存地址
    • 作用:寻址
• 形象化理解内存（内存的大小和地址）
• 理解a=10的内存图（引用，指向）
  • 指向：如果变量或者引用存储了某块内存空间地址后，则该变量或者引用指向该块内存
• 不同数据占用内存空间的大小

顺序表

• 集合中存储的元素是有顺序的，顺序表的结构可以分为两种形式：单数据类型和多数据类型。
• python中的列表和元组就属于多数据类型的顺序表
• 单数据类型顺序表的内存图（内存连续开启）
• 多数据类型顺序表的内存图（内存非连续开辟）
• 顺序表的弊端：顺序表的结构需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁。

　　

链表

相对于顺序表，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理且进行扩充时不需要进行数据搬迁。

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

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

#构建节点这个数据结构
class Node():
    def __init__(self,item):
        self.item = item
        self.next = None
#构建链表
class Link():
    def __init__(self):
        #_head属性要永远指向第一个节点的地址，如果链表为空则指向None
        self._head = None
    def add(self,item):
        node = Node(item)
        node.next =  self._head
        self._head = node
    def travel(self):
        cur = self._head
        while cur:
            print(cur.item)
            #每次循环都要偏移cur
            cur = cur.next
    def isEmpty(self):
        return self._head == None
    
    def length(self):
        cur = self._head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count
    
    def append(self,item):
        node = Node(item)
        if self._head == None:
            self._head = node
            return
        cur = self._head #当前节点
        pre = None #当前节点的前一个节点
        while cur:
            pre = cur
            cur = cur.next
        pre.next = node
        
    def search(self,item):
        find = False
        cur = self._head
        while cur:
            if cur.item == item:
                find = True
                break
            cur = cur.next
        return find
    
    def insert(self,pos,item):
        node = Node(item)
        if pos == 0:
            self.add(item)
            return
        cur = self._head
        pre = None
        for i in range(pos):
            pre = cur
            cur = cur.next
        pre.next = node
        node.next = cur
        
    def remove(self,item):
        cur = self._head
        pre = None
        #单独处理删除第一个节点的情况
        if self._head.item == item:
            self._head = self._head.next
            return
        #找到即将被删除的节点
        while cur:
            if cur.item == item:#条件成立则cur就是要删除的节点
                #cur就是删除的节点，pre就是其前一个节点
                pre.next = cur.next
                return
            pre = cur
            cur = cur.next

link = Link()
 

顺序查找

• 当数据存储在诸如列表的集合中时，我们说这些数据具有线性或顺序关系。 每个数据元素都存储在相对于其他数据元素的位置。 由于这些索引值是有序的，我们可以按顺序访问它们。 这个过程产实现的搜索即为顺序查找。
• 顺序查找原理剖析：
  • 从列表中的第一个元素开始，我们按照基本的顺序排序，简单地从一个元素移动到另一个元素，直到找到我们正在寻找的元素或遍历完整个列表。如果我们遍历完整个列表，则说明正在搜索的元素不存在。　
• 代码实现：该函数需要一个列表和我们正在寻找的元素作为参数，并返回一个是否存在的布尔值。found 布尔变量初始化为 False，如果我们发现列表中的元素，则赋值为 True。　
• 有序列表：之前我们列表中的元素是随机放置的，因此在元素之间没有相对顺序。如果元素以某种方式排序，顺序查找会发生什么？我们能够在搜索技术中取得更好的效率吗？

二分查找

• 有序列表对于我们的实现搜索是很有用的。在顺序查找中，当我们与第一个元素进行比较时，如果第一个元素不是我们要查找的，则最多还有 n-1 个元素需要进行比较。 二分查找则是从中间元素开始，而不是按顺序查找列表。 如果该元素是我们正在寻找的元素，我们就完成了查找。 如果它不是，我们可以使用列表的有序性质来消除剩余元素的一半。如果我们正在查找的元素大于中间元素，就可以消除中间元素以及比中间元素小的一半元素。如果该元素在列表中，肯定在大的那半部分。然后我们可以用大的半部分重复该过程，继续从中间元素开始，将其与我们正在寻找的内容进行比较。

def search(alist,item):
    find = False
    start = 0
    end = len(alist)-1
    while start <= end and not find:
        #中间元素的下标
        mid_index = (start+end)//2
        #条件成立，则意味着查找的数在中间位置的右侧
        if alist[mid_index] < item:
            start = mid_index + 1
        elif alist[mid_index] > item:#条件成立，则意味着查找的数在中间位置的左侧
            end = mid_index - 1
        else:#等于：找到
            find = True
            
    return find

alist = [1,2,3,4,5,6,7,8,9,10]
find = search(alist,1)
print(find)

 二叉树

分类

• 普通二叉树
• 排序二叉树

 结构

• 根节点
• 左右叶子节点
• 子树：完整的子树和非完整的子树
  • 每一颗子树根节点可以作为另一颗子树的左右叶子节点
  • 每一个节点其实都可以作为一颗子树的根节点

普通二叉树实现(代码)

• 构建一颗空树
• 向树中插入节点
• 遍历二叉树

class Node():
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None
class Tree():
    def __init__(self):
        self.root = None
    def insert(self,item):
        node = Node(item)
        #插入第一个节点的情况
        if self.root == None:
            self.root = node
            return
        #向非空的树中插入一个新的节点
        cur = self.root
        queue = [cur]
        while True:
            leaf = queue.pop(0)
            if leaf.left == None:
                leaf.left = node
                break
            else:
                queue.append(leaf.left)
            if leaf.right == None:
                leaf.right = node
                break
            else:
                queue.append(leaf.right)
        #广度遍历
    def travel(self):
        cur = self.root
        queue = [cur]
        while queue:
            leaf = queue.pop(0)
            print(leaf.item)
            if leaf.left != None:
                queue.append(leaf.left)
            if leaf.right != None:
                queue.append(leaf.right)
tree = Tree()
alist = [1,2,3,4,5]
for a in alist:
　　tree.insert(a)
tree.travel()

# 结果:
1
2
3
4
5

二叉树的遍历

广度遍历

• 广度遍历：横向

深度遍历

• 深度遍历：纵向。一定是作用在每一颗子树中的
  • 前序遍历: 根左右
  • 中序遍历：左根右
  • 后序遍历：左右根

排序二叉树(代码)

•  准则：当向排序二叉树中插入节点的时候，让节点和树的根节点进行大小比较。比根节点大的节点需要插入到树的右侧，否则插入到树的左侧。

class Node():
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None
class SortTree():
    def __init__(self):
        self.root = None
    def insert(self,item):
        node = Node(item)
        if self.root == None:
            self.root = node
            return
        cur = self.root
        while True:
            #新节点往根节点的左侧插入
            if cur.item > item:
                if cur.left == None:
                    cur.left = node
                    return
                else:
                    cur = cur.left
            else:#新节点往根节点的右侧插入
                if cur.right == None:
                    cur.right = node
                    return
                else:
                    cur = cur.right          
    def forward(self,root):#根左右==》作用到每一颗子树中
        if root == None:
            return
        print(root.item)
        self.forward(root.left)
        self.forward(root.right)       
    def middle(self,root):
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)
        
    def back(self,root):
        if root == None:
            return
        self.back(root.left)
        self.back(root.right)
        print(root.item)

tree = SortTree()
tree.insert(3)
tree.insert(8)
tree.insert(5)
tree.insert(7)
tree.insert(6)
tree.insert(2)
tree.insert(1)
tree.middle(tree.root)

# 结果:
1
2
3
5
6
7
8

 排序算法

分类

• 冒泡
• 选择
• 插入
• 希尔
• 快排

冒泡排序

def bubbleSort(list):
    n = len(list)
    for j in range(0, n):
        for i in range(0, n-j-1):
            if list[i] > list[i+1]:
                list[i], list[i+1] = list[i+1], list[i]
    return list
if __name__ == '__main__':
    list = [23, 12, 1, 56, 34, 78, 1, 55, 4, 2, 66]
    print(bubbleSort(list))

 选择排序 

#第一步：将乱序序列中的最大值找出，和乱序中最后一个元素交换位置
def sort(alist):
    #假设第一个元素为最大值
    max_index = 0#一定是最大值的下标
    for i in range(len(alist)-1):#循环只是为了找出最大值的下标
        if alist[max_index] < alist[i+1]:
            max_index = i+1
    #将最大值和最后一个元素交换位置
    alist[max_index],alist[len(alist)-1] = alist[len(alist)-1],alist[max_index]
    return alist

#第二步：步骤一的操纵重复执行n-1次
def sort(alist):
    for j in range(len(alist)-1):
        #假设第一个元素为最大值
        max_index = 0#一定是最大值的下标
        for i in range(len(alist)-1-j):#循环只是为了找出最大值的下标
            if alist[max_index] < alist[i+1]:
                max_index = i+1
        #将最大值和最后一个元素交换位置
        alist[max_index],alist[len(alist)-1-j] = alist[len(alist)-1-j],alist[max_index]
    return alist

插入排序

• 将乱序的序列假设分成两部分
  • 有序集合
  • 无序集合
  • 将无序集合的每一个元素依次有序的插入到有序集合中 [6, 1,0.2,7,9,3,4,5,10,8] [1,6, 0.2,7,9,3,4,5,10,8] [0.2,1,6, 7,9,3,4,5,10,8]　

#第一步
i = 1 #i表示的为元素下标。i可以表示有序集合元素的个数。
#alist[i]:无序集合中的第一个元素
#alist[i-1]:有序集合中最后元素
if alist[i] < alist[i-1]:
    alist[i],alist[i-1] = alist[i-1],alist[i]

#第二步
i = 2 #i表示的为元素下标。i可以表示有序集合元素的个数。
#alist[i]:无序集合中的第一个元素
#alist[i-1]:有序集合中最后元素
while i > 0:
    if alist[i] < alist[i-1]:
        alist[i],alist[i-1] = alist[i-1],alist[i]
        i -= 1

#完整代码
def sort(alist):
    for i in range(1,len(alist)):
        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i],alist[i-1] = alist[i-1],alist[i]
                i -= 1
            else:
                break
    return alist

 希尔排序

 增量

•  初始值：元素个数整除2
• 增量值表示的分组的组数

def sort(alist):
    gap = len(alist)//2 #初始的增量值
    while gap > 0:#gap是可以等于1
        for i in range(gap,len(alist)):
            while i > 0:
                if alist[i] < alist[i-gap]:
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                    i -= gap
                else:
                    break
        gap //= 2
    return alist

 快排

思想

• 将列表中第一个元素设定为基准数字，赋值给mid变量，然后将整个列表中比基准小的数值放在基准的左侧，比基准到的数字放在基准右侧。然后将基准数字左右两侧的序列在根据此方法进行排放。
• 定义两个指针，low指向最左侧，high指向最右侧
• 然后对最右侧指针进行向左移动，移动法则是，如果指针指向的数值比基准小，则将指针指向的数字移动到基准数字原始的位置，否则继续移动指针。
• 如果最右侧指针指向的数值移动到基准位置时，开始移动最左侧指针，将其向右移动，如果该指针指向的数值大于基准则将该数值移动到最右侧指针指向的位置，然后停止移动。
• 如果左右侧指针重复则，将基准放入左右指针重复的位置，则基准左侧为比其小的数值，右侧为比其大的数值。

实现

•  设定一个基数mid，基数的初始值就是乱序序列中的第一个元素值
• 将除了基数剩下所有的数值跟基数做比较。比较之后需要达到的一个效果就是：
  • 基数左侧放置的都是比它小的数
  • 基数右侧放置的都是比它大的数　

def func(li,first,end):
    if first>=end:
        return
    left=first
    right=end
    mid=li[left]
    while left<right:
        while left<right and li[right]>= mid:
            right -= 1
        li[left]=li[right]
        while left<right and li[left]<mid:
            left += 1
        li[right]=li[left]
    li[left]=mid
    func(li,first,left-1)
    func(li,left+1,end)

if __name__ == '__main__':

    l=[6,5,4,3,2,1,11]
    func(l,0,len(l)-1)
    print(l)

 例题

 使用两个队列实现一个栈

#如何使用两个队列实现一个栈
q1 = Queue()
q2 = Queue()
alist = [1,2,3,4]
#将alist列表中的元素加入到队列q1中
for a in alist:
    q1.enqueue(a)
#核心代码
while q1.size() > 0:
    while q1.size() > 1:
        q2.enqueue(q1.dequeue())
    print(q1.dequeue())
    q1,q2 = q2,q1

链表的有序插入

    #有序插入
    def sortInsert(self,item):
        node = Node(item)
        #如果链表为空，则
        if self._head == None:
            self._head = node
            return
        cur = self._head
        pre = None
        #寻找合适的位置cur和pre中间的位置
        while cur:
            if cur.item > item:
                break
            pre = cur
            cur = cur.next
        #特殊情况的处理 （链表的头部作为合适的位置）
        if pre == None:
            self._head = node
            node.next = cur
            return
        
        pre.next = node
        node.next = cur

#链表的有序插入
link = Link()
alist = [3,8,5,7,6,2,1]
for a in alist:
    link.sortInsert(a)
link.travel()

链表的指向倒置

    def reverse(self):
        pre = self._head
        cur = pre.next
        
        pre.next = None
        
        _next = cur.next
        while _next:
            cur.next = pre
            pre = cur
            cur = _next
            _next = _next.next
        cur.next = pre
        self._head = cur

#链表的指向倒置
link = Link()
for i in range(1,6):
    link.append(i)
link.reverse()
link.travel()