阅读裘宗燕老师的《数据结构与算法:python语言描述》的课件所记笔记

一、stack&queue概述

1.stack&queue

  • 保存数据元素的容器,元素存入,查看元素,弹出元素(取得元素的同时将其从容器中删除)
  • 用于在计算过程中临时性地保存元素
  • 常用于生成数据和使用之间的缓冲,称为缓冲存储或缓存
  • stack和queue存入操作只需保证元素存入和将来取出的顺序,不需记录或保证存入的元素与容器已有元素之间的任何关系
  • 任何时候访问或删除的元素都默认地唯一确定。只有新的存入或弹出操作可能改变下次的默认元素

2.stack&queue的区别

  • stack是保证缓存元素的后进先出(LIFO)的结构
  • 队列是保证缓存元素的先进先出(FIFO)结构

3.实现与应用

  • stack&queue的特点完全是抽象的逻辑,对于实现没有约束
  • 可以利用元素的排列顺序表示他们的先来后到,即用线性表作为它们的实现结构
  • 使用环境

    1.计算过程分为一些顺序进行的步骤
    2.执行中会不断产生一些后面可能需要的中间数据
    3.数据不能立即使用,但必须保存以备后面使用
    4.需要保存的数据的项数不能事先确定

二、stack

1.概念

  • 栈,有些地方称为堆栈,是一种容器,可存入数据元素、访问元素、删除元素。没有位置概念
  • 保证任何时候可以访问、删除的元素都是此前最后存入的那个元素。确定了一种默认的访问顺序

2.基本操作

  • 创建空栈
  • 判断栈是否为空(可能还需判断满),is_empty()
  • 向栈中插入(通常称推入/压入)一个元素,push(...)
  • 从栈中删除(弹出)一个元素,空栈弹出报错,pop()
  • 取当前元素的值(并不删除),top()

3.特性及实现考虑

  • 可以实现为只在一端插入和删除的表
    • 因此有人把栈称为后进先出表(LIFO)
    • 进行插入或删除操作的一端称为栈顶,另一端称为栈底
  • 用线性表实现时,考虑效率最高的那一端作为栈顶
    • 采用连续表,在后端插入删除都是O(1)操作
    • 采用链接表,前端插入删除都是O(1)操作
  • 实现前,定义一个异常类(python内部异常是一组类,都是Exception的子类,可以继承已有异常类来定义自己的异常类)
    # 栈下溢(空栈访问)
    class StackUnderflow(ValueError):
    pass

4.连续表实现

  • 问题
    • 简单连续表,可能出现栈满
    • 动态连续表,置换策略问题以及分期付款式的O(1)复杂性
  • python list的操作特性使得其可以作为栈使用
    • 建立空栈,对应创建一个[],判断空栈对应判断空表
    • 由于list采用动态连续表技术,因此不会出现栈满
    • 压入元素应在表尾端进行,对应append()
    • 弹出操作也应在尾端,对应pop()
    • 由于是动态连线表,压入操作具有分期付款式的O(1)复杂性,其它操作都是O(1)操作
a.程序实现,利用list
class Sstack():
    def __init__(self):
        self.elems = []
    def isEmpty(self):
        return self.elems == []
    def top(self):
        if self.elems == []:
            raise StackUnderflow
        return self.elems[len(self.elems)-1]
    def pop(self):
        if self.elems == []:
            raise StackUnderflow
        return self.elems.pop()
    def push(self, e):
        self.elems.append(e)
b.程序实现,用链接技术
class LStack():
    def __init__(self):
        self.top = None
    def isEmpty(self):
        return self.top is None
    def top(self):
        if self.top is None:
            raise StackUnderflow
        return self.top.elem
    def pop(self):
        if self.top is None:
            raise StackUnderflow
        e = self.top.elem
        self.top = self.top.next
        return e
    def push(self, e):
        self.top = LNode(e, self.top)

5.栈的应用

  • 栈是算法和程序里最常用的辅助结构,基本用途基于两个方面:
    • 作为算法或程序里的辅助存储结构
    • 利用后进先出的特点,可以得到特定的存储和取用顺序
  • 最简单的应用实例,可以用于颠倒一组元素的顺序
    • 将一组元素全部存入后取出,得到反序的序列
    • 通过不同的存入取出操作序列,可以得到不同的元素序列
a.括号配对问题

括号有圆括号、方括号、花括号,每种还分开括号与闭括号,括号里面的片段可能相互嵌套

  • 配对原则:
    • 遇到的闭括号应匹配与其最近尚未匹配的开括号
    • 由于多种或多次的可能嵌套,因此需要保存开括号
    • 由于嵌套,需要逐对匹配,后面的闭括号应与更前的匹配
    • 可以删除匹配的括号,为后面的匹配做好准备
  • 问题描述:
    • 顺序检查正文里的每个字符
    • 遇到开括号时将其压入到一个栈,其它字符跳过
    • 遇到闭括号时弹出栈顶元素与之匹配,若匹配则继续,若不匹配则检查以失败结束
程序实现:
def check_pares(text):
    pares = "()[]{}"
    open_pares = "([{"
    opposite = {")":"(", "]":"[", "}":"{"}
    def paretheses(text):...

    st = SStack()

    for pr,i in parethese(text):
        if pr in open_pares:
            st.push(pr)
        elif st.pop() != opposite[pr]:
            print("Unmatching is found at", i, "for", pr)
            return False
    print("All paretheses are correctly matched.")
    return True
  • 括号生成器定义为局部函数
    def paretheses(text):
    i, text_len = 0, len(text)
    while True:
        while i < text_len and text[i] not in pares:
            i += 1 
        if i >= text_len:
            return
        yield text[i], i
        i += 1
X检查python或c程序里的括号
  • 需要跳过注释和字符串,待补充
b.表达式的表示、计算和变换
  • 表达式种类:
    • 中缀表达式:运算符在运算对象中间,需要括号还有优先级
    • 前缀表达式:运算符在运算对象前面
    • 后缀表达式:运算符在运算对象后面
  • 后缀表达式分析:
    • 要处理的是算术表达式
    • 运算对象是浮点数形式表示的数
    • 运算符只有“+”、“-”、“*”、“/”,都是二元运算符
  • 计算过程分析:
    • 遇到运算对象需要记录以备后面使用
    • 遇到运算符,取得前面遇到的几个运算对象或已做运算得到的结果,实施计算并记录结果
    • 通过以上分析,显然应该使用栈作为缓存结构
后缀表达式求值程序实现:
def suf_exp_evaluator(exp):
    operator = "+-*/"
    st = ESStack()
    for x in exp:
        if not x in operator:
            st.push(x)
        if st.depth() < 2:
            raise SynaxError("Short of operand(s).")
        b = st.pop()
        a = st.pop()
        if x == "+":
            c = a + b
        elif x == "-":
            c = a - b
        elif x == "*":
            c = a * b
        elif x == "/":
            if b == 0:
                raise ZeroDivisionError
            c = a / b
        else: pass
        st.push(c)
    if st.depth() == 1:
        return st.pop()
    raise SynaxError("Extra operand(s).")

# 给栈增加一个检查栈深度的方法
class ESStack(SStack):
    def depth(self):
        return len(self.elems)

# 将表达式转化为项的表,line.split()
def suffix_exp_evaluator(line):
    return suf_exp_evaluator(line.split())

# 定义一个交互式的驱动函数
def stuffix_exp_calculator():
    while True:
        try:
            line = input("Stuffix Expression: ")
            if line == "end":
                return
            res = suffix_exp_evaluator(line)
            print(res)
        except Exception as ex:
            print("Error:", type(ex), ex.args)
c.中缀表达式转换为后缀表达式
  • 若本次运算符的优先级不高于上次,则先输出上次的运算符,然后记录本次运算符。
  • 遇到左括号时记录,遇到右括号时,反向输出所记录的运算符,因为括号里的运算优先于括号外,然后由于记录的运算符顺序肯定是从低到高,因此反向输出(即后进先出)
  • 最后可能剩下一些记录的运算符,也应反向输出
中缀转换为后缀程序实现:
priority = {"(":1, "+":3, "-":3. "*":5, "/":5}
infix_operators = "+-*/()"

def trans_infix_stuffix(line):
    st = SStack(); llen = len(line); exp = []
    for x in tokens(line):
        if x not in infix_operators:
            exp.append(x)
        elif st.isEmpty or x == "(":
            st.push(x)
        elif x == ")":
            while is not st.isEmpty and st.top() != "(":
                exp.append(st.top())
            if st.isEmpty():
                raise SynaxError("Missing \'(\'.")
            st.pop()
        else:
            while not st.isEmpty and priority[x] < priority[st.top()]:
                exp.append[st.pop()]
            st.push(x)
    while not st.isEmpty():
        if st.top() == "(":
            raise SynaxError("Extra \'(\' in expressing.")
        exp.append(st.pop())
    return exp

def tokens(line): # 表达式生成
    i, llen = 0, len(line)
    while i < llen:
        while line[i].isspace():
            i += 1
        if i >= llen: break
        if line[i] in infix_operators:
            yield line[i]
            i += 1
            continue
        j = i+1
        while (j < llen and not line[j].isspace() and
                line[j] not in infix_operators):
            if ((line[j] == 'e' or line[j] == 'E')
                and j+1 < llen and lin[j+1] == '-'):
                j += 1
            j += 1
        yield line[i:j]
        i = j

def test_trans_infix_suffix(s): # 测试辅助函数
    print(s)
    print(trans_infix_suffix(s))
    print("Value:", suf_exp_evaluator(trans_infix_suffix(s)))
d.栈与递归
  • 如果一个定义或结构(如python函数,数据结构)中的某个或几个部分具有与整体同样的结构,则称其为递归定义或递归结构
  • 递归定义中的递归部分必须比整体简单,这样最后才能有终结点(称为递归定义的出口);递归结构中也必须存在由非递归的基本结构构成的部分。否则就是无限递归。
  • 例如:
    • 递归定义的python函数(通过调用自身完成)
    • 结点链构成的单链表(非空时,去掉一个结点还是同样结构)
    • 简单表达式:
      • 常数、变量是表达式
      • 若e1,e2是表达式,op是运算符,则e1 op e2,op e2,(e1)也是表达式
    • 阶乘函数 n!:
      def fact(n):
      if n == 0:
      return 1
      else:
      return n * fact(n - 1)
e.递归算法与函数调用
  • 问题:在递归函数执行中将会递归调用自己,而且还可能继续这样递归调用。这种过程在计算机上如何实现?
  • 考虑上述的递归定义函数fact
    • 要得到fact(6)的结果,需知道fact(5)
    • 计算fact(6)时n取值6,计算fact(5)是n取值5,如此循环
    • 而计算出fact(5)的值还要乘以6得到fact(6)的值,说明递归调用时要记录n的值
    • 需要记录的数据量与递归次数成线性关系,不能定义几个整型变量保存数据
  • 支持递归的实现需要一个栈(运行栈),实现递归函数时
    • 每个具体的递归调用都有一些局部信息需要保存,语言的实现在运行栈上为函数的这次调用建立一个帧,其中保存相关信息
    • 函数执行总以栈顶帧作为当前帧,所有局部变量都在这里有体现
    • 进入下次递归调用时,将为它建立一个新帧
    • 从递归调用返回时,上层取得函数调用的结果,并弹出已经结束的调用对应的帧,然后回到上一层执行时的状态
  • 实现过程分析:
    def fact(n)
    if n == 0:
        return 1
    else:
        return n * fact(n-1)
函数调用
  • 程序里函数调用是按先后调用先返回的规则进行
  • 支持函数调用的进行,语言实现需要做一些内部动作
    • 在进入新函数前保存一些信息,退出函数时恢复调用前状态并继续
  • 上述两部分动作分别称为函数调用的前序和后序动作
  • 调用的前序动作:
    • 为被调用函数的局部变量分配存储区
    • 将所有实参和返回地址存入函数帧
    • 将控制转到被调用函数入口
  • 调用的后序动作:
    • 将被调用函数的计算结果存入指定位置
    • 释放被调用函数的存储区
    • 按以前保存的返回地址将控制转回调用函数

  • 递归定义的函数每次递归函数调用,都将自动执行上述动作,若要转为非递归,需要自己做这些事情,用一个栈保存使用的中间信息
  • 考虑阶乘函数的非递归形式:
    def norec_fact(n):
    res = 1
    st = SStack()
    while n > 0:
        st.push(n)
        n -= 1
    while not st.isEmpty():
        res *= st.pop()
    return res
递归与非递归
  • 可以证明:任何递归定义的函数,都可以通过引入一个栈保存中间结果,翻译为一个非递归过程。任何一个包含循环的程序都可翻译为一个不包含循环的递归程序

6.应用:背包问题

  • 假设knap(W,n)表示n件物品相对于W的背包问题,s表示n件物品的集合
  • 重点:对每一种重量的物体要么选择要么不选择
    • 若选择wn,则knap(W-wn,n-1)的解就是knap(W,n)的解
    • 若不选择wn,则knap(W,n-1)的解就是knap(W,n)的解
  • 情况分析:
    • 当W = 0;True
    • 当w < 0;False
    • 当w > 0, n < 1;False
    • 当s > 0, n >= 1; knap(W,n-1)或knap(W-wn,n-1)
a.程序实现:
def knap_rec(weight, wlist, n):
    if weight == 0:
        return True
    elif weight < 0:
        return Flase
    elif weight > 0 and n < 1:
        return Flase
    elif knap_rec(weight-wlist[n-1], wlist, n-1):
        print("Item" + str(n) + ":",wlist[n-1])
        return True
    elif knap_rec(weight, wlist, n-1):
        return True
    else:
        return Flase
最后由 oucb 编辑于2016年05月24日 14:08