Python数据结构与算法-栈和递归函数

水深无声 2022-05-21 02:10 155阅读 0赞

### 1.栈 ###

#coding=gbk
    #栈的常用操作
    # Stack()    建立一个空的栈对象
    # push()     把一个元素添加到栈的最顶层
    # pop()      删除栈最顶层的元素，并返回这个元素
    # peek()     返回最顶层的元素，并不删除它
    # isEmpty()  判断栈是否为空
    # size()     返回栈中元素的个数
    
    #使用Python中的列表进行对栈的实现
    class Stack():
        '''对栈进行模拟'''
        def __init__(self):
            self.values = []
        def push(self, value):
            self.values.append(value)
        def pop(self):
            return self.values.pop()
        def peek(self):
            if not self.isEmpty():
                return self.values[len(self.values)-1]
        def isEmpty(self):
            return len(self.values) == 0
        def size(self):
            return len(self.values)
        def print_all(self):
            print(self.values)
    s= Stack()
    print(s.isEmpty())      #True 代表栈为空 
    s.push(12)
    s.push(13)
    print(s.isEmpty())      #False
    print(s.peek())         #13
    print(s.size())     #2
    print(s.pop())      #13
    print(s.peek()) #12
    s.push('hello')
    s.push('this')
    s.push('world')
    s.print_all()           #[12, 'hello', 'this', 'world']
    print(s.size())

### 2.递归函数 ###

如果在一种数据结构的某个或某几个部分具有与整体同样的结构，称为递归。

阶乘递归函数实现：

def fact(n):
        if n == 0:
            return 1
        else:
            return n * fact(n-1)
    print(fact(3))  # 6

![70][]

![70 1][]

传统方法实现递归：

def fact1(n):
        result = 1
        for i in range(1, n+1):
            result *= i 
        return result 
    print(fact1(3))   # 6

其他例子：

def age(n):
        if n == 1:
            return 18
        else:
            re = age(n-1) + 2
            
            print('递归返回的值：%d'%re)
        print('递归的值：%d'%n)
        return re
    print(age(5))   # 26
    # 递归返回的值：20
    # 递归的值：2
    # 递归返回的值：22
    # 递归的值：3
    # 递归返回的值：24
    # 递归的值：4
    # 递归返回的值：26
    # 递归的值：5
    # 26

例子2：

#coding=gbk
    def recursion(n):
        print(n)
        if n/2 > 1:
            re = recursion(n/2) # 此处没有return语句， 但是递归进行回溯的时候，还是会进行该语句，进行打印操作
            print('返回值', re)
        print('上层递归值',n)
        return n    # 返回函数中的recursion进行递归，一步步返回溢出的 n值。栈结构。
    print(recursion(10))
    # 10
    # 5.0
    # 2.5
    # 1.25
    # 上层递归值 1.25
    # 返回值 1.25
    # 上层递归值 2.5
    # 返回值 2.5
    # 上层递归值 5.0
    # 返回值 5.0
    # 上层递归值 10
    # 10
    
    print('test recursion2 start ----')
    def recursion2(n):
        print(n)
        if n/2 < 1:
            re = recursion2(n/2)
            print('返回值：',re)
        else:
            print('上层递归值：',n)
            return n
    recursion2(10)
    print('test recursion2 end----')
    # test recursion2 start ----
    # 10
    # 上层递归值： 10
    # test recursion2 end----

使用递归函数解决背包问题： 从 6个物品中选择 若干个，使得总重量为weight

def knap_rec(weight, wlist, n):
        if weight == 0:
            return True
        if weight < 0 or (weight > 0 and n < 1):    # weigh小于0了，则无解。weight还有重量，但是没种类了，也还是无解
            return False
        if knap_rec(weight - wlist[n-1], wlist, n-1):   #如果选择最后一件物品都有解。则减少重量，也减少种类
            print('Item ' + str(n) + ':' + str(wlist[n-1]))
            return True
        if knap_rec(weight, wlist, n-1):    #如果不选择最后一件物品仍然有解。针对同样重量当物品种类减1的子问题仍有解，则有解
            return True
        else:
            return False
    weight = 20
    wlist = [2, 8, 10, 12, 15, 6]
    n = 6
    print(knap_rec(weight, wlist, n))
    # Item 1:2
    # Item 4:12
    # Item 6:6
    # True

--------------------

![20200423151245826.PNG][]

[70]: /images/20220521/cb8316cad81544bbb618825f9d252664.png
[70 1]: /images/20220521/5e7db7cbc24d4a8cab2837f3b4e501c6.png
[20200423151245826.PNG]: /images/20220521/91fd7617b01f4c38bde5883070b523c6.png