[数据结构与算法]python数据结构与算法

一 评判程序（算法）的优劣方法-时间复杂度

二 数据结构的概念

stmt参数：表示要进行测试的代码块语句
setup：运行代码块语句时所需的设置，比如从别的模块import

from timeit import Timer

def test01():
    ls = []
    for i in range(1000):
        ls.append(i)
    return ls

def test02():
    ls = []
    for i in range(1000):
        ls += [i]
    return ls

def test03():
    ls = []
    return [i for i in range(1000)]

def test04():
    ls = list(range(1000))
    return ls

if __name__ == "__main__":
    timer = Timer('test01()','from __main__ import test01')
    t1 = timer.timeit(1000)
    print(t1)
    timer = Timer('test02()', 'from __main__ import test02')
    t2 = timer.timeit(1000)
    print(t2)
    timer = Timer('test03()', 'from __main__ import test03')
    t3 = timer.timeit(1000)
    print(t3)
    timer = Timer('test04()', 'from __main__ import test04')
    t4 = timer.timeit(1000)
    print(t4)

三 栈

3.1 栈的概念

3.2 将列表封装为一个栈

将列表的第0元素位置定义为栈底；将列表的第-1个元素的位置定义为栈顶

四 队列

4.1 队列的概念

4.2 将列表封装为一个队列

结题思路：
	由于是用队列来实现，而队列的特性是先进先出，即删除的元素一定是在队头位置的元素，所以我们约定让手里有山芋的孩子永远排在对头；
	当有山芋的孩子将山芋传递给下一个孩子时，这个孩子被临时删除出队列，然后重新入队列排到了队尾；拿到山芋的孩子排到了对头；
	到7秒时，永久删除对头的孩子，剩下的孩子排成一个新队列继续玩，直到剩下最后一个孩子为止。

class Queue():
    def __init__(self):
        self.ls = []
    def enqueue(self, item):
        self.ls.insert(0, item)

    def dequeue(self):
        return self.ls.pop()

    def isEmpty(self):
        return self.ls == []

    def size(self):
        return len(self.ls)

kids = ['A','B','C','D','E','F']
queue = Queue()
for kid in kids:
    queue.enqueue(kid)  # A在队头；F在队尾

while(queue.size()>1):
    for i in range(6):
        kid = queue.dequeue()
        queue.enqueue(kid)
    queue.dequeue()
print("获胜的是：%s"%queue.dequeue())

五 双端队列

5.1 双端队列的概念

5.2 将列表封装为一个双端队列

class Deque():
    def __init__(self):
        self.items = []
    def addFront(self,item):
        self.items.insert(0,item)
    def addRear(self,item):
        self.items.append(item)
    def removeFront(self):
        return  self.items.pop(0)
    def removeRear(self):
        return self.items.pop()
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

5.3 双端队列应用案例：回文检查

回文是一个字符串，读取首尾相同的字符，如madam

def isHuiWen(str1):
    q = Deque()
    for i in str1:
        q.addFront(i)
    res = True
    while(q.size()>1):
        if(q.removeFront() != q.removeRear()):
            res = False
            break
    return res

六 用两根队列实现一个栈

6.1 解题思路

6.2 代码

class Queue():
    def __init__(self):
        self.items=[]
    def enqueue(self,item):
        self.items.append(item)
    def dequeue(self):
        return self.items.pop(0)
    def travel(self):
        for item in self.items:
            print(item)
    def size(self):
        return len(self.items)


alist = [1,2,3,4,5]
q1 = Queue()
q2 = Queue()
for i in alist:
    q1.enqueue(i)

while q1.size() > 0:
    # 将q1中n-1个元素放入q2
    while q1.size() > 1:
        q2.enqueue(q1.dequeue())
    print(q1.dequeue())  # 栈弹出最后一个元素

    q1,q2 = q2,q1

七 顺序表

7.1 顺序表的概念

7.2 单数据类型顺序表的内存图

6.3 多数据类型顺序表的内存图

八 链表

8.1 链表的概念

1. 顺序表的弊端：顺序表的结构需要预先知道数据的大小来申请连续的内存空间，而在扩充时又需要进行数据迁移；
2. 相对于顺序表，链表结构可以充分利用计算机的内存空间，实现灵活的内存动态管理，且进行扩充时不需要进行数据迁移；
3. 链表是一种常见的基础数据结构，是一种线性表，但不想顺序表一样连续存储数据，而是每一个节点里存放下一个节点的地址

8.2 链表的代码实现

# 节点
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None

# 节点
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None

class Link():
    def __init__(self):
        self.__head = None
    def add (self, item):
        #新建一个节点
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        #新建一个节点
        node = Node(item)
        if self.__head == None:
            self.__head = node
        else:
            cursor = self.__head
            while(cursor):
                prev = cursor
                cursor = cursor.next
            prev.next = node

    def insert(self, pos, item):
        # 新建一个节点
        node = Node(item)
        cursor = self.__head
        for i in range(pos):
            prev = cursor
            cursor = cursor.next
        prev.next = node
        node.next = cursor

    def travel(self):
        cursor = self.__head
        while(cursor):
            print(cursor.item)
            cursor = cursor.next

    def isEmpty(self):
        return self.__head == None

    def length(self):
        cursor = self.__head
        num = 0
        while(cursor):
            num+=1
            cursor = cursor.next
        return num

    def search(self, item):
        find = False
        cursor = self.__head
        while (cursor):
            if cursor.item == item:
                find = True
                break
            cursor = cursor.next
        return find

    def remove(self,item):
        cursor = self.__head
        if cursor.item == item: #要删除的是第一个节点
            self.__head = cursor.next
        else:
            while cursor:
                if cursor.item == item:
                    prev.next = cursor.next
                    del cursor
                    break
                prev = cursor
                cursor = cursor.next

8.3 链表的逆序

    def reverse(self):
        cursor = self.__head
        prev = None
        next_node = cursor.next
        while cursor:
            cursor.next = prev
            prev = cursor
            cursor = next_node
            if cursor:
                next_node = cursor.next
        self.__head = prev

九 二叉树

9.1 概念

9.2 二叉树代码实现

class Node:
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None

class Tree:
    def __init__(self):
        self.root = None

    def addNode(self,item):
        node = Node(item)
        # 如果要插入的节点是二叉树的第一个节点
        if self.root == None:
            self.root = node
            return
        # 如果要插入的节点不是二叉树的第一个节点
        cursor = self.root
        q = [cursor]

        while 1:
            check_node = q.pop(0)
            # 检查被检查节点的左节点是不是None。如果是就把新节点插入；如果不是则把左节点放入q列表待检查
            if check_node.left == None:
                check_node.left = node
                return
            else:
                q.append(check_node.left)
            # 检查被检查节点的右节点是不是None。如果是就把新节点插入；如果不是则把右节点放入q列表待检查
            if check_node.right == None:
                check_node.right = node
                return
            else:
                q.append(check_node.right)

    def travel(self):
        cursor = self.root
        q = [cursor]
        while q:
            check_node = q.pop(0)
            print(check_node.item)
            if check_node.left == None:
                pass
            else:
                q.append(check_node.left)
            if  check_node.right == None:
                pass
            else:
                q.append(check_node.right)

9.3 二叉树的遍历

9.3.1 广度优先遍历

一层一层对节点遍历

    def travel(self):
        cursor = self.root
        q = [cursor]
        while q:
            check_node = q.pop(0)
            print(check_node.item)
            if check_node.left == None:
                pass
            else:
                q.append(check_node.left)
            if  check_node.right == None:
                pass
            else:
                q.append(check_node.right)

9.3.2 深度优先遍历

9.3.2.1 三种深度遍历类型

1. 前序（子树中先遍历根）：根左右
2. 中序（子树中第二遍历根）：左根右
3. 后序（子树中最后遍历根）：左右根

9.3.2.2 深度遍历思路

二叉树中每一个节点都是某个子树的根节点，因此先以第一个子树写遍历的函数（根作为形参），然后在函数中将左、右节点作为新子树的根节点递归调用函数（左、右节点作为形参）

9.3.2.3 三种深度遍历代码实现

    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)

9.3.3 排序二叉树

9.3.3.1 排序二叉树概念

1. 利用二叉树可以对一个乱序数组排序；
2. 需要先将乱序数组中的元素依次插入二叉树，插入时要遵从一个准测：第一个元素作为二叉树的根；后序插入的元素如果比根节点小则插入根节点的左侧；如果比根节点大则插入根节点的右侧；
3. 对遵从上面准测插入的二叉树进行深度优先中序遍历后就是有序数组

9.3.3.2 排序二叉树插入数据思路

1. 使用一个cur游标作为当前节点，开始时cur指向二叉树的根；
2. 判断要插入的元素的值比根（目前cur就是根）的值大还是小；
3. 如果比根小，则是向左节点插入，先判断根（目前cur是根）的左节点(cur.left)是不是空None，如果是空则直接插入cur的左节点，然后return结束；如果不是空None则将cur的指向偏移到cur.left,等待之后和cur节点的左节点再做比较；
4. 如果比根大，则是向右节点插入，先判断根（目前cur是根）的右节点(cur.right)是不是空None，如果是空则直接插入cur的右节点，然后return结束；如果不是空None则将cur的指向偏移到cur.right,等待之后和cur节点的右节点再做比较；
5. 在第3步和第4步中已经把当前节点cur做了偏移，用一个while循环把步骤3和4包起来循环执行直到找到插入位置return为止

9.3.3.3 排序二叉树代码实现

class Node:
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None

class SortTree:
    def __init__(self):
        self.root = None

    def addNode(self,item):
        node = Node(item)
        cur = self.root
        # 当要加入的节点是二叉树第一个节点时
        if(self.root == None):
            self.root = node
            return
        # 当要加入的节点不是二叉树第一个节点时
        while cur:
            ## 如果要加入的节点值小于根节点的值，则插入左节点
            if(node.item < cur.item):
                if(cur.left == None):
                    cur.left = node
                    return
                else:
                    cur = cur.left

            ## 如果要加入的节点值大于根节点的值，则插入右节点
            elif (node.item > cur.item):
                if(cur.right == None):
                    cur.right = node
                    return
                else:
                    cur = cur.right


    def middle(self,root):  #中序遍历   左根右
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)



tree = SortTree()
alist = [3,8,5,7,6,2,9,4,1]
for i in alist:
    tree.addNode(i)
tree.middle(tree.root)

十 二分查找法

10.1 概念

二分查找法一定是基于有序集合的查找；

10.2 代码

普通方法

alist = [1,2,3,4,5,6,7,8,9,10]
def find(lst, item):
    find = False
    first = 0;
    last = len(lst)-1

    while first<=last:
        middle = (first+last)//2
        if lst[middle]>item:
            last = middle-1
        elif lst[middle]<item:
            first=middle+1
        else:
            find = True
            break
    return find

递归法

alist = [1,2,3,4,5,6,7,8]
def find(lst, item, first=0, last=None):
    if last == None:
        last = len(lst)-1
    if first > last:
        return -1
    else:
        middle = (first + last) // 2
        if lst[middle] == item:
            return middle
        elif lst[middle]>item:
            return find(lst, item, first, middle-1)
        else:
            return find(lst, item, middle+1, last)

十一 排序算法

11.1 冒泡排序

11.1.1 原理

列表元素两两相比，每次比较大的值向后移动

11.1.2 分步实现代码

1. 第一步：第一轮排序，将最大值冒泡到列表的最后位置

alist = [3,8,5,7,6]
def sort(alist):
    for index in range(len(alist)-1):
        if alist[index] > alist[index+1]:
            alist[index], alist[index+1] = alist[index+1], alist[index]
    return alist

print(sort(alist))

2. 第二步：一共需要n-1轮这样的冒泡才能排序完

alist = [3,8,5,7,6]
def sort(alist):
    for turn in range(len(alist)-1):
        for index in range(len(alist)-turn-1):
            if alist[index] > alist[index+1]:
                alist[index], alist[index+1] = alist[index+1], alist[index]
    return alist

print(sort(alist))

11.2 选择排序

11.2.1 原理

先假设第0个位置上的元素就是最大值（max_index=0）；两两元素相比，哪个位置的元素大就将max_index改为那个位置的index；等所有元素都比较完后，将max_index位置那个元素和最后的元素换位置，即将最大值放到最后了

11.2.2 分步实现代码

1. 第一步：第一轮排序，将最大值max_index上的元素和最后位置的元素交换位置

alist = [3,8,5,7,6]
def sort(alist):
    max_index = 0
    for index in range(1,len(alist)):
        if alist[index] > alist[max_index]:
            max_index = index
    alist[max_index], alist[len(alist)-1] = alist[len(alist)-1], alist[max_index]
    return alist

print(sort(alist))

2. 第二步：一共需要n-1轮这样的位置交换才能排序完

alist = [3,8,5,7,6]
def sort(alist):
    for turn in range(len(alist)-1):
        max_index = 0
        for index in range(1,len(alist)-turn):
            if alist[index] > alist[max_index]:
                max_index = index
        alist[max_index], alist[len(alist)-1-turn] = alist[len(alist)-1-turn], alist[max_index]
    return alist

print(sort(alist))

11.3 插入排序（一种特殊形式的希尔排序）

11.3.1 概念和解题思路

11.3.2 分步实现代码

1. 第一步：有序集合中只有一个元素，乱序集合中第一个元素和有序集合中唯一的一个元素比较完就行了

alist = [3,8,5,7,6]

# 将第一个元素3作为有序子集合，后面的8,5,7,6作为无序子集合
# i是有序集合中元素的个数，也是无序集合中第一个元素8在原始数组中的下标（alist[i]=8）;而alist[i-1]=3是有序集合中最后一个元素在原始数组中的下标
i = 1
if alist[i] < alist[i-1]:   # 如果乱序子集中第一个元素8小于有序子集中最后一个元素3，则交换位置
    alist[i], alist[i-1] = alist[i-1], alist[i]
else: # 如果乱序子集合中第一个元素8大于等于有序子集中最后一个元素3，则什么也不做
    pass
i+=1  # i要加1，让有序子集变成2个元素，乱序集合第一个元素变为alist[2]

2. 第二步：有序集合中有两个元素，乱序集合中第一个元素需要和有序集合中两个元素都比较一次

alist = [3,8,5,7,6]
i = 2
while i > 0:
    if alist[i] < alist[i-1]:   # 如果乱序子集中第一个元素5小于有序子集中最后一个元素8，则交换位置
        alist[i], alist[i-1] = alist[i-1], alist[i]
        i -= 1 # i回退1是因为现在有序集合中的元素已经不是一个了，而是两个，所以和有序集合中最后一个元素比较完还要和前面的元素比较
    else: # 如果乱序子集合中第一个元素5大于等于有序子集中最后一个元素8，则退出循环
        break

3. 第三步：有序集合中有三个元素，乱序集合中第一个元素需要和有序集合中三个元素都比较一次
   i = 3

4. 第四步：有序集合中有四个元素，乱序集合中第一个元素需要和有序集合中四个元素都比较一次
   i = 4

5. 第五步：有序集合中有五个元素，乱序集合中第一个元素需要和有序集合中五个元素都比较一次
   i = 5

6. 第六步：将前五步合并成最后的代码

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

11.4 希尔排序

11.4.1 概念和解题思路

希尔排序是插入排序的一种。也叫缩小增量排序，是直接插入排序算法的一种更高效的改进版本，该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个增量（gap）的元素组成）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下效率是最高的，因此希尔排序在时间效率比直接插入排序有较大提高

gap是增量值；也是拆分出来的子数组的个数

11.4.2 分步实现代码

def sort(alist):
    gap = len(alist) // 2
    #将插入排序当做增量为1的希尔排序
    for i 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

def sort(alist):
    gap = len(alist) // 2
    #将增量设置成gap
    for i 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

#继续缩小增量
def sort(alist):
    gap = len(alist) // 2
    while gap >= 1:
        #将增量设置成gap
        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

11.5 快速排序

11.5.1 解题思路和分步实现步骤

1. 指定一个基数（乱序中的第一个数据），将乱序中比基数小的放在基数的左侧；比基数大的放在基数的右侧, 要实现这一步需要分以下步骤实现
   1.1 . 指定low为乱序中第一个元素的下标0；指定high为乱序中最后一个元素的下标len(list)-1

alist = [6,1,2,7,9,3,4,5,10,8]
def sort(alist):
    # 基数
    mid = alist[0]
    low = 0
    high = len(alist)-1

1.2 . 比较规则是：

先偏移high；
偏移high或low时，当发生复制时改为偏移low或high；
直到low和high重回时，将mid的值放入重合的位置。此时就实现了mid左边的数都比他小，右边的数都比他大

先从右开始偏移high的位置，如果high位置的元素比mid6大那么high位置上的元素不用交换，并且将high向左偏移一个位置指向10的位置

然后继续用high位置上的值10和mid6比较，如果10大，那么high位置上的元素不用交换，并且将high向左偏移一个位置指向5的位置

然后继续用high位置上的值5和mid6比较，如果5比mid6小，那么high位置上的元素复制到mid的位置上，并且停止偏移high，转而开始偏移low

low位置上的5比mid6小，所以low位置上的5不用动，直接将low向右偏移一位到1

low位置上的1比mid6小，所以low位置上的1不用动，直接将low向右偏移一位到2

low位置上的2比mid6小，所以low位置上的2不用动，直接将low向右偏移一位到7

low位置上的7比mid6大，所以需要将low位置上的7复制到high指向的位置，并且停止偏移low，转而偏移high

high位置上的7比mid6大，所以7不用动，将high向左偏移到4

high位置上的4比mid6小，所以需要将4复制到low的位置，并且停止偏移high，转而偏移low

low位置上的4比mid6小，所以不用移动4，直接将low的位置向右移动到指向9

low位置上的9比mid6大，所以将9复制到high的位置，并且停止偏移low，转而偏移high

high位置上的9比mid6大，所以9不动，直接将high向左偏移到指向3的位置

high位置上的3比mid6小，所以将3复制到low的位置，并且停止偏移high，转而偏移low

low位置上的3比mid6小，所以3不用动，直接将low向右偏移到指向3，这时low和high重合

一旦low和high重回，将mid6放入这个位置。此时mid6的左侧元素都比6小；右侧元素都比6大

1.3 这步代码实现

alist = [6,1,2,7,9,3,4,5,10,8]
def sort(alist):
    # 基数
    mid = alist[0]
    low = 0
    high = len(alist)-1

    while low < high:
        # 偏移high
        while low < high:
            if alist[high] > mid:
                # 向左偏移high
                high -= 1
            else:
                alist[low] = alist[high]
                break

        # 偏移low
        while low < high:
            if alist[low] < mid:
                low += 1
            else:
                alist[high] = alist[low]
                break
        if low == high:
            alist[low] = mid
            break
    return alist

2. 用递归将基数左侧乱序序列和右侧乱序序列执行上面的步骤，直到之后的基数左侧只有一个元素，右侧只有一个元素为止

def sort(alist,start,end):
    low = start
    high = end
    #递归结束的条件
    if low > high:
        return
    #基准：最左侧的数值
    mid = alist[low]
    #low和high的关系只能是小于，当等于的时候就要填充mid了
    while low < high:
        while low < high:
            if alist[high] > mid:
                high -= 1
            else:
                alist[low] = alist[high]
                break
        while low < high:
            if alist[low] < mid:
                low += 1
            else:
                alist[high] = alist[low]
                break
        
        #当low和high重复的时候，将mid填充
        if low == high:
            alist[low] = mid #or alist[high] = mid  
            break
    #执行左侧序列
    sort(alist,start,high-1)
    #执行右侧序列
    sort(alist,low+1,end)
    
    return alist