数据结构与算法Python语言描述栈和队列课件.ppt

《数据结构与算法Python语言描述栈和队列课件.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法Python语言描述栈和队列课件.ppt（91页珍藏版）》请在三一办公上搜索。

1、4，栈和队列,栈和队列的概念数据的生成，缓存，使用和顺序栈的实现和问题栈应用实例栈与递归，递归和非递归队列的实现和问题队列应用实例搜索问题相关问题,概述,栈（stack）和队列（queue）是两种使用最广泛的数据结构，它们都是保存数据元素的容器，可以将元素存入其中，或者从中取出元素使用（查看，或弹出，即在取得元素的同时将其从容器里删除）容器是一大类能保存数据元素的数据结构，它们都保证存入的元素可以在将来取得，而被删除的元素不再存在于容器之中栈和队列主要用于在计算过程中临时性地保存元素这些元素是前面计算中发现或产生的中间数据，需要在后面使用如果产生的中间数据暂时不用或者用不完，但将来可能要用到，

2、就有必要临时保存起来栈和队列常用于生成和使用之间的缓冲，称为缓冲存储或缓存栈和队列的操作都比较简单最重要的就是存入元素和取出元素两个操作还可能有另外一些辅助操作，如创建，检查，判断空/满等,概述,中间数据的生成有早有晚，时间上有先后。在实际应用中，使用这些元素也可能需要按时间顺序。有两种最典型的顺序如下：按数据生成的顺序，后生成的数据需要先处理按数据生成的先后顺序处理，先生成的数据先处理如去银行办事，先到的应先得到服务，具体等待方式不重要，如直接排在一个等待队列上拿（顺序）号后等叫号，每次叫尚未服务的最早来的顾客在这两种情况下，访问（并可能删除）都按默认方式确定元素栈和队列就是支持按这两种顺序

3、使用元素的缓存数据结构栈和队列存入操作只需要保证元素存入和将来取出的顺序，不记录也不保证新存入元素与容器中已有元素之间的任何关系,概述,栈和队列保证元素存取之间的时间关系，特点是：栈是保证缓存元素后进先出（Last In First Out，LIFO）的结构队列是保证缓存元素的先进先出（先存者先用，First In First Out，FIFO）关系的结构对于栈和队列，任何时候，下次访问或删除的元素都默认地唯一确定。只有新的存入或删除（弹出）操作可能改变下次的默认元素栈和队列的性质完全是抽象的、逻辑的，对实现方式（如何实现相应时间顺序）并没有任何约束，任何能满足要求的技术均可使用最方便的技术是

4、利用元素的排列顺序表示其先来后到关系，也就是说，可以用线性表作为栈和队列的“实现结构”例如：把元素进入实现为表的后端插入，这样最老的元素总是最前面的元素（作为队列下次应访问和删除）最新的元素总是最后一个元素（作为栈下次应访问和删除）,概述,栈和队列是计算中使用最广的缓存结构，其使用环境可以总结如下：计算过程分为一些顺序进行的操作步骤执行的操作时会产生一些后面可能需要用的中间数据产生的某些数据无法立即用掉，需要保存起来以备后面使用需要保存的数据的项数不能事先确定这种情况下，通常就需要用一个栈或一个队列作为缓存栈和队列是许多重要算法的基础，后面有许多实例。栈和队列的性质和操作效率，也是许多算法设计

5、中的关键因素由于栈和队列在应用中的重要性，Python 的基本功能中包括了对栈的支持（可直接用 list），标准库提供了支持队列用途的结构下面分别讨论这两种结构的情况，包括性质和模型；实现和问题；一些应用；一些一般性问题,栈：概念,栈（stack），有的书籍里称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素。在这里没有位置的概念栈保证任何时刻可以访问、删除的元素都是在此之前最后存入的那个元素。因此确定了一种默认的访问顺序栈的基本操作是一个封闭集合（与表不同），通常包括：创建空栈判断栈是否为空（还可能需要判断满），is_empty()向栈中插入（通常称推入/压入，push）一个元素，pu

6、sh(.)从栈中删除（弹出，pop）一个元素，空栈弹出报错，pop()取当前（最新）元素的值（并不删除），top(),栈：特性和基本实现考虑,栈可以实现为（可以看作）只在一端插入和删除的表因此有人（有书籍中）把栈称为后进先出（LIFO）表进行插入或删除操作的一端称为栈顶，另一端称为栈底用线性表技术实现栈时，由于只需要在一端操作，自然应该利用实现最方便，而且能保证两个主要操作的效率最高的那一端采用连续表方式实现，在后端插入删除都是 O(1) 操作（!）采用链接表方式实现，在前端插入删除都是 O(1) 操作栈通常都采用这两种技术实现实现栈之前，先定义一个自己的异常类（Python 的内部异常是一组

7、类，都是 Exception 的子类，可以继承已有异常类定义自己的异常类）class StackUnderflow(ValueError): # 栈下溢（空栈访问） pass,栈：实现,采用连续表技术实现，也会遇到连续表的各种相关问题用简单连续表，还是采用动态连续表（分离式实现的连续表）？如果用简单连续表，就可能出现栈满的情况采用动态连续表，栈存储区满时可以换一块更大的存储区。这时又会出现置换策略问题，以及分期付款式的 O(1) 复杂性Python list 及其操作实际上提供了一种栈功能，可以作为栈使用建立空栈，对应于创建一个空表 ，判空栈对应于判空表由于 list 采用动态连续表技术（分离

8、式实现），作为栈的表不会满压入元素操作应在表尾端进行，对应于 lst.append(x)弹出操作也应在尾端进行，无参的 lst.pop() 默认弹出表尾元素由于采用动态连续表技术，压入操作具有分期付款式的 O(1) 复杂性，其他操作都是 O(1) 操作,栈：实现,为了概念清晰、操作名更易理解、排除不符合栈性质的其他操作，应该基于连续表定义一个栈类，用 list 作为其实现的基础class SStack(): # 基于顺序表技术实现的栈类 def _init_(self): # 用list对象 _elems存储栈中元素 self._elems = # 所有栈操作都映射到list操作 def is

9、_empty(self): return self._elems = def top(self): if self._elems = : raise StackUnderflow(in SStack.top() return self._elems-1 def push(self, elem): self._elems.append(elem) def pop(self): if self._elems = : raise StackUnderflow(in SStack.pop() return self._elems.pop(),栈：链接表实现,采用链接技术，可以借用 LNode 类实现一

10、个链接栈：class LStack (): # 基于链接表技术实现的栈类，用LNode作为结点 def _init_(self): self._top = None def is_empty(self): return self._top is None def top(self): if self._top is None: raise StackUnderflow(in LStack.top() return self._top.elem def push(self, elem): self._top = LNode(elem, self._top) def pop(self): if s

11、elf._top is None: raise StackUnderflow(in LStack.pop() p = self._top self._top = p.next return p.elem,栈的应用,栈是算法和程序里最常用的辅助结构，基本用途基于两方面：用栈可以很方便地保存和取用信息，因此常作为算法或程序里的辅助存储结构，临时保存信息，供后面的操作使用利用栈后进先出的特点，可以得到特定的存储和取用顺序许多实际运用结合了这两方面的特性作为最简单的应用实例，栈可用于颠倒一组元素的顺序将一组元素依次全部存入后取出，就能得到反序的序列通过不同的存入取出操作序列，可以得到不同的元素序列。但

12、请注意，这种做法不能得到任意的排列，结果序列有一定的规律性下面介绍栈的若干典型应用有些比较具体，是特殊的应用有些实例代表一大类应用，更具典型性,简单应用：括号配对问题,在许多正文中都有括号，特别是在表示程序、数学表达式的正文片段里。括号有正确配对问题。作为例子，考虑 Python 程序里的括号存在不同的括号：如圆括号、方括号和花括号每种括号都有开括号和闭括号，括号括起的片段可能相互嵌套，各种括号需要分别正确嵌套配对配对的原则遇到的闭括号应该匹配此前遇到的最近的尚未匹配的对应开括号由于多种/多次/可能嵌套，为检查配对，遇到的开括号必须保存由于括号可能嵌套，需要逐对匹配，闭括号应与前面最近的尚未有

13、匹配的开括号匹配，后面括号应与更前面次近的括号匹配可以删除匹配的括号，为后面的匹配做好准备后遇到并保存的开括号应该先删除，这就是后进先出，而且要按照出现顺序，显然应该/可以用一个栈保存开括号,简单应用：括号配对问题,问题处理的线索已经清楚了：顺序检查被处理正文（是一个字符串）里的一个个字符跳过无关字符遇到开括号时将其压入一个栈遇到闭括号时弹出栈顶元素与之匹配括号匹配则继续遇到不匹配时检查以失败结束下面考虑定义一个函数完成这个检查，其中先定义一些检查中需要使用的数据和变量,简单应用：括号配对问题,函数定义（很简单）：def check_pares(text): pares = () open_p

14、ares = ( opposite = ):(, :, : # 表示配对关系的字典 def paretheses(text): . # 括号生成器，定义见后 st = SStack() for pr, i in paretheses(text): # 对 text 里各括号和位置迭代 if pr in open_pares: # 开括号，压进栈并继续 st.push(pr) elif st.pop() != oppositepr: # 不匹配就是失败，退出 print(Unmatching is found at, i, for, pr) return False # else 是一次括号配对

15、成功，什么也不做，继续 print(All paretheses are correctly matched.) return True,简单应用：括号配对问题,括号生成器定义为（局部）函数def paretheses(text): i, text_len = 0, len(text) while True: while i = text_len: return yield texti, i i += 1生成器（回忆一下）：用 yield 语句产生结果可以用在需要迭代器的地方函数结束导致迭代结束,简单应用：括号配对问题,总结：这个函数利用了栈的性质，这是关键函数开始先准备好处理中需要用的数据。

16、虽然各种数据在程序里都只有一处使用，但这样定义使程序清晰易读，更易修改利用了 Python 丰富的数据结构和操作，如 in，not in 和字典等定义理一个独立的括号生成器函数，使代码功能清晰。例如，要检查实际 Python 程序里的括号，还需要考虑跳过程序里的注释和字符串等，修改括号生成规则时只需要修改这个函数请自己考虑和练习,表达式的表示、计算和变换,小学生就开始写表达式，先是算术表达式，后来是代数表达式对二元运算符，通常把它们写在两个运算对象中间，这种写法称为中缀表示，按中缀表示法写出的表达式称为中缀表达式中缀表示很难统一贯彻，一元和多元运算符很难用中缀表示代数表达式里的函数符号通常写在

17、运算对象前面，这种写法称为前缀表示。为界定函数参数的范围，通常用括号将它们括起可见，常见的表达式习惯表示是前缀表示和中缀表示的组合实际上，表达式并不一定采用这种习惯写法可以用纯粹的前缀表示，这样写出的表达式称为前缀表达式还有一种表达式写法称为后缀表示，其中运算符（函数）总写在它们的运算对象之后，这样写出的表达式称为后缀表达式。实际上，后缀表达式特别适合计算机处理前缀表达式也称为波兰表达式（由波兰数学家 J. Lukasiewicz 于1929提出），后缀表达式也称为逆波兰表达式,表达式的表示、计算和变换,首先假设每个运算符有确定的元数（运算对象个数），而且元数唯一写表达式时，最重要的问题是准确

18、描述计算的顺序中缀表达式的一个重要缺点是不能直接表示运算的顺序，需要借助于辅助性约定和/或辅助描述机制，实际情况：必须引进括号机制，表示括号里的运算先做（显式描述计算顺序）为减少总写括号的麻烦，还引进优先级概念，规定运算符的优先级（或优先级关系），高优先级运算符的结合性强，运算符相邻出现时，优先级高的运算先做还需规定相同优先级的运算符相邻出现时的计算顺序（结合性）与之对应的情况：在上述基本假定下，前缀表达式和后缀表达式都不需要括号，也不需要优先级，就能自然地描述任意复杂的计算顺序可见，中缀表达式的表达能力最弱中缀表达式增加了括号后，几种表达方式具有同等表达能力,表达式的表示、计算和变换,对比几

19、种不同表达式形式。下面三个算术表达式等价中缀：(3 - 5) * (6 + 17 * 4) / 3前缀：/ * - 3 5 + 6 * 17 4 3后缀：3 5 - 6 17 4 * + * 3 /三个表达式描述的是同一个计算过程下面先考虑后缀表达式的求值，假定被处理的是算术表达式其中的运算对象是浮点数形式表示的数运算符只有 +、-、*、/，都是二元运算符后面还要讨论不同表达式形式的转换（考虑中缀形式到后缀形式）研究相应的转换算法，以及中缀表达式的求值,后缀表达式的计算,考虑计算过程，设有函数 nextItem() 得到下一个运算对象或运算符：遇到运算对象，需要记录以备后面使用遇到运算符（或函

20、数名），需要根据其元数取得前面最近遇到的几个运算对象或已做运算得到的结果，实施计算并记录结果问题：应该用什么结构记录信息？看看计算过程的性质：需要记录的是已经掌握但还不能立即使用的中间结果遇到运算符时，要用的是此前最后记录的几个结果（根据元数）显然应该用栈作为缓存结构上面分析也说明了算法的基本结构实际程序就是把这个算法用 Python 的语言写出来,后缀表达式的计算,先考虑算法的框架假定 st 是栈，算法核心是个循环（逐个处理运算符或运算对象）：while 还有输入 : x = nextItem() if not is_operator(x): st.push(float(x) else: a

21、 = st.pop() # 第二个运算对象 b = st.pop() # 第一个运算对象 . . # 根据运算符 x 对 a 和 b 计算 . . # 计算结果压入栈这里写了几个辅助过程，其具体实现依赖于一些情况被求值的表达式从哪里获得表达式里的元素如何表示（下面假定用字符串）,后缀表达式的计算,假定从函数参数获得输入参数是一个字符串，内容是需要求值的后缀表达式表达式中不同的项之间有空格分隔为程序清晰，定义了一个包装过程：# 定义一个函数把表示表达式的字符串转化为项的表def suffix_exp_evaluator(line): return suf_exp_evaluator(line.s

22、plit()定义一个扩充的栈类，增加一个检查栈深度的方法：class ESStack(SStack): def depth(self): return len(self.elems)下面是核心求值过程的定义（与前面设计相比有一些小修改）由于函数的输入就是一个项的表,后缀表达式的计算,def suf_exp_evaluator(exp): operators = +-*/ st = ESStack() # 扩充功能的栈，可用 depth() 检查栈内元素个数 for x in exp: if not x in operators: st.push(float(x); continue # 不能转

23、换时自动引发异常 if st.depth() 2: raise SyntaxError(Short of operand(s).) a = st.pop() # 第二个运算对象 b = st.pop() # 第一个运算对象 if x = +: c = b + a elif x = -: c = b - a elif x = *: c = b * a elif x = /: c = b / a # 可能引发异常 ZeroDivisionError else: break # 不可能出现 else 分支的情况 st.push(c) if st.depth() = 1: return st.pop(

24、) raise SyntaxError(Extra operand(s).) # 运算对象个数不匹配,后缀表达式的计算,定义一个交互式的驱动函数（主函数）：def suffix_exp_calculator(): while True: try: line = input(Suffix Expression: ) if line = end: return res = suffix_exp_evaluator(line) print(res) except Exception as ex: print(Error:, type(ex), ex.args)注意：这里用一个 try 块捕捉用户使用

25、时的异常，保证我们的计算器不会因为用户输入错误而结束except Exception as ex 两个用途：Exception 表示捕捉所有异常保证交互继续；ex 将约束到所捕捉异常，使处理器能用相关信息,至此后缀表达式计算器的开发工作完成,中缀表达式到后缀表达式的转换,中缀表达式的情况比较复杂，直接求值比较复杂可以考虑首先将其转换为等价的后缀表达式，然后借用前面定义的后缀表达式求值器，完成计算考虑这里的情况，例如中缀：(3 - 5) * (6 + 17 * 4) / 3后缀：3 5 - 6 17 4 * + * 3 /分析情况：遇到运算对象应直接输出（因为运算符应该在它们的后面）需要考虑中缀

26、运算符的优先级，适时输出（输出运算符就是运算）遇到运算符时不能直接输出，只有下一运算符的优先级不高于本运算符时，才应该做本运算符要求的计算（输出本运算符）也就是说，读到运算符 o 时，需要用它与前一运算符 o 比较，如果 o 的优先级不高于 o，就做 o（输出 o），而后记住 o,中缀表达式到后缀表达式的转换,运行过程中需要记录遇到的一些运算符，可能记录多个，遇到新运算符时，需要与前面最后遇到的运算符比较，因此应该用一个栈。还要处理括号：遇到左括号时应该记录；遇右括号时反向逐个输出所记录运算符（排在后面的优先级肯定更高），直到左括号并将其抛弃最后可能剩下一些记录的运算符，应反向将其输出（排在后

27、面运算符，的优先级肯定更高）这里的几种情况都是后来的先用，只需要用一个运算符栈操作中需要特别注意检查栈空的情况准备操作中使用的数据：priority = (:1, +:3, -:3, *:5, /:5infix_operators = +-*/() # 把 (, ) 也看作运算符特殊处理priority 给每个运算符关联一个优先级。给 ( 一个很低的优先级，保证它不会被其他运算符强制弹出，只有对应的 ) 弹出它,中缀表达式到后缀表达式的转换,def trans_infix_suffix(line): st = SStack() exp = for x in tokens(line): # to

28、kens 是一个待定义的生成器 if x not in infix_operators: # 运算对象直接送出 exp.append(x) elif st.is_empty() or x = (: # 左括号进栈 st.push(x) elif x = ): # 处理右括号的分支 while not st.is_empty() and st.top() != (: exp.append(st.pop() if st.is_empty(): # 没找到左括号，就是不配对 raise SyntaxError(Missing (.) st.pop() # 弹出左括号，右括号也不进栈 else: #

29、处理栈中应计算的运算符，运算符都看作左结合 while (not st.is_empty() and priorityst.top() = priorityx): exp.append(st.pop() st.push(x) # 当前运算符进栈,中缀表达式到后缀表达式的转换,while not st.is_empty(): # 处理栈里剩下的运算符 if st.top() = (: # 如果还有左括号，就是不配对 raise SyntaxError(Extra (.) exp.append(st.pop() return exp为测试方便，定义一个专门用于测试的辅助函数：def test_tr

30、ans_infix_suffix(s): print(s) print(trans_infix_suffix(s) print(Value:, suf_exp_evaluator(trans_infix_suffix(s),中缀表达式到后缀表达式的转换,把生成表达式里各个项的工作定义为一个生成器：def tokens(line): i, llen = 0, len(line) while i llen: if linei.isspace(): i += 1; continue if linei in infix_operators: # 遇到运算符 yield linei; i += 1; c

31、ontinue j = i + 1 # 处理运算对象 while (j llen and not linej.isspace() and linej not in infix_operators): if (linej = e or linej = E) # 处理负指数 and j+1 llen and linej+1 = -): j += 1 j += 1 yield linei:j # 生成运算对象子串 i = j,这个计算器不能处理负号（负数）和一元运算符要完全地处理表达式，需要做语法分析。有关情况不进一步讨论存在较简单的处理方式，请考虑,中缀表达式的求值,中缀表达式的求值比后缀表达式复

32、杂，需要考虑运算符的优先级括号的作用根据读入中遇到的情况，确定完成各运算的时机运算时需要找到相应的运算对象从中缀形式到后缀形式的转换算法已经解决了前三个问题需要用一个运算符栈，在读入表达式的过程中比较运算符的优先级，并根据情况压入弹出生成后缀表达式需要输出运算符的时刻，就是执行运算的时刻（后缀表达式的性质，计算这种表达式时，遇到运算符就计算）根据后缀表达式的计算规则，每次执行运算时，相应的运算对象应该是最近遇到的数据，或最近计算得到的结果,中缀表达式的求值,计算中缀表达式，可以用一个栈保存运算对象和中间结果总结一下：求值中缀表达式，一种方法是用两个栈，其中一个保存运算符，另一个保存运算对象和中

33、间结果遇到运算对象时入栈遇到运算符时，根据情况考虑计算、入栈的问题如果需要计算，数据在运算对象栈里如果做了计算，结果还需要压入运算对象栈如果表达式读完了，运算符栈里剩下的运算符逐个弹出完成计算其他细节可以参考前一个例子（优先级处理，tokens 可以直接使用）这一问题作为本次课的一个练习,栈与递归,如果一个定义或者结构（如 Python 函数，数据结构）中的某个或某几个部分具有与整体同样的结构，则称其为递归定义或递归结构递归定义中的递归部分必须比整体简单，而且有非递归的分支（称为递归定义的出口），这样才可能终止；递归结构中必须存在非递归的基本结构部分。否则就是无限递归，不是良好定义例：递归定义

34、的 Python 函数（所完成工作的一部分通过调用自身完成）结点链构成的单链表（非空时，去掉一个结点后还是同样结构）例：简单表达式常数、变量是表达式；若 e1, e2 是表达式，op 为运算符，则 e1 op e2, op e1, (e1) 也是表达式,栈与递归,递归算法（和递归定义的函数）很有用，主要适用于要解决的问题、要计算的函数、或者要处理的数据具有递归性质的情况问题：在递归函数的执行中将会递归调用自己，而且还可能继续这样递归调用。这种过程在计算机上如何实现？,栈与递归,考虑递归定义的函数 factdef fact(n) : if n = 0: return 1 else: return

35、 n * fact(n-1)不难看到下面一些显然的情况（以 fact(6) 的计算为例）为得到 fact(6) 的结果，必须先算出 fact(5)在计算 fact(6) 时函数的参数 n 取值 6，而在递归调用计算 fact(5) 时，函数的参数 n 取值 5，如此下去递归调用计算出 fact(5) 的值之后还需乘以 6 以得到 fatc(6) 的值，这说明在递归调用 fact(5) 时 n 具有值 6 的情况需要记录（保存）需要这样记录的数据量与递归的次数成线性关系，无常量限制，因此不能用定义几个整型变量的方式保存,在递归调用中保存的数据，如 6, 5, .，后保存的将先使用后进先出的使用方

36、式和数据项数无明确限制，说明应该用一个栈支持递归函数的实现,栈与递归,看阶乘函数导致的递归计算def fact(n) : if n = 0: return 1 else: return n * fact(n-1)假定现在执行 fact(3)，与此有关的实际数据共有三项计算结果n 的值计算后回到的位置递归调用 fact(2)，fact(1) 和 fact(0) 的情况都一样,1,1,2,6,栈增长方向,栈与递归/函数调用,支持递归的实现需要一个栈（运行栈），实现递归函数时每个具体递归调用都有一些局部信息需要保存，语言的实现在运行栈上为函数的这次调用建立一个帧，其中保存有关信息函数执行总以栈顶帧作

37、为当前帧，所有局部变量都在这里有体现进入下次递归调用时，将为它建立一个新帧从递归调用返回时，上层取得函数调用的结果，并弹出已经结束的调用对应的帧，然后回到上一层执行时的状态所有递归程序的执行都是这种模式实际上，一般的函数调用和退出的方式也与此类似目前各种语言都按这种模式实现了一套支持函数调用和返回的机制，其中最重要的数据结构就是一个运行栈其中保存所有已经开始（被调用）执行但还没有结束的函数的局部信息（局部变量的值约束等）,栈与函数调用,程序里函数嵌套调用是按“后调用先返回”的规则进行这种规则符合栈的使用模式用栈可以自然地支持函数调用的实现,def main(): m = . n = . fir

38、st(m,n) # 位置1 ,支持函数调用的进行，语言实现需要做一些内部动作在进入新函数前保存一些信息，退出函数时恢复调用前状态并继续,栈与函数调用,这两部分动作分别称为函数调用的前序和后序动作调用的前序动作：为被调用函数的局部变量分配存储区（函数帧/活动记录/数据区）将所有实参和返回地址存入函数帧（实参形参的结合/传值）将控制转到被调用函数入口调用的后序动作（返回）：将被调用函数的计算结果存入指定位置；释放被调用函数的存储区；按以前保存的返回地址将控制转回调用函数递归定义的函数每次递归函数调用，都将自动执行这些动作要想把递归定义的函数变换成非递归的，就需要自己做这些事情，用一个栈保存使用的中

39、间信息,栈与函数调用,考虑阶乘函数的非递归形式，用自己定义的栈模拟系统的运行栈函数定义：def norec_fact (n): # 自己管理栈，模拟函数调用过程 res = 1 st = SStack(); while n 0: st.push(n) n -= 1 while not st.is_empty(): res *= st.pop() return res这里并没有严格地按规矩翻译，只保存了必要的信息。例如这里的计算结果没有进栈,递归过程和非递归过程,前面先给求阶乘的递归算法，而后给出了一个使用栈保存搜索的中间信息的非递归算法可以证明：任何递归定义的函数（程序），都可以通过引入一个栈

40、保存中间结果，翻译为一个非递归的过程。与此对应，任何一个包含循环的程序都可翻译为一个不包含循环的递归程序这两个翻译过程都可计算，可以写出完成这两种翻译的程序，把任何递归定义的函数翻译到完成同样工作的非递归的函数，或者把任何包含循环的程序翻译为不包含循环的递归程序阶乘的递归算法里只有一个递归调用，很容易翻译成非递归算法前面的翻译并没有采用通用的方法，而是根据自己对函数执行过程的分析，尽可能地做了些简化。这样写出的程序比较简单有关自动翻译的算法，这里不再介绍有兴趣的同学可以参考张乃孝老师的算法与数据结构，高教出版社 2002 年版，4.3.1 节，或北大信科学院的数据结构幻灯片,栈的应用：简单背包

41、问题,问题描述：背包里可放入重量为 W 的物品，现有 n 件物品的集合 S，其中物品的重量分别为 w1, w2, , wn。问能否从中选出若干件物品的重量之和正好是 W。若存在则称此背包问题有解，否则无解可以要求当存在解时给出一个解许多实际的货物安排，装车，剪裁材料等，都与这一问题类似问题的表示：设 W 0，n 0。用 knap(W, n) 表示 n 件物品相对于 W 的背包问题，如果它有解如果不选 wn，则 knap(W, n - 1) 的解就是 knap(W, n) 的解如果选 wn，则 knap(W - wn, n - 1) 的解 就是 knap(W, n) 的解问题有递归性质，n 件物

42、品的背包问题可归结到 n - 1 件物品的问题可能是对另一个总容量 W通过不断归结，最后可以归结到最简单的情况,简单背包问题,背包问题的递归定义：,这里的 True 表示有解；False 表示无解前三种情况可以直接知道有没有解后两种情况都是把原问题归结到规模较小的问题。这样归结下去，最终会达到前三种情况注意：每件物品有且仅有一件，用去了就没有了,简单背包问题,完全根据上面的递归定义，写出的递归函数定义如下：def knap_rec( weight, wlist, n ): if weight = 0: return True elif weight 0 and n 1): return Fal

43、se elif knap_rec(weight - wlistn-1, wlist, n-1): print(Item + str(n) + :, wlistn-1) return True elif knap_rec(weight, wlist, n-1): return True else: return False函数还产生了输出，列出所选的各物品的顺序号和重量,简单背包问题,对背包问题，有关算法里出现了两个递归调用def knap_rec( weight, wlist, n ): if . . elif knap_rec(weight - wlistn-1, wlist, n-1):

44、print(Item + str(n) + :, wlistn-1); return True elif knap_rec(weight, wlist, n-1): return True else: .按规范方式翻译得到的非递归函数定义比较长，这里不讨论了有兴趣的同学可以查阅张乃孝老师主编的算法与数据结构，高教出版社，2002 版，4.3.1 节，或者信息学院的数据结构幻灯片可以自己想想如何写出一个（简单些的）非递归算法（作为自由练习，可以在教学网的课程讨论组交流）在现在的计算机上，函数调用的效率比较高，一般情况下直接采用递归定义的函数就可以满足需要，不必考虑做出非递归的函数定义,队列（qu

45、eue）,队列（queue），或称为队，也是一种容器可存入数据元素、访问元素、删除元素这里也没有位置的概念。队列保证任何时刻可访问、删除的元素都是在此之前最早存入队列而至今未删除的那个元素队列确定了一种由存储顺序决定的访问顺序队列的基本操作也是一个封闭集合，通常包括：创建空队列判断队列是否为空（还可能需要判断满）将一个元素放入队列（常称为入队，enqueue）从队列中删除（常称为出队，dequeue）一个元素取当前（最老的）元素的值（并不删除）我们也可以为队列建立一个理论模型，从略,队列：特征,队列的特性：保证任何时刻访问或删除的元素的先进先出（FIFO）顺序是一种与“时间”有关的结构队列可看

46、作（可实现为）只在一端插入另一端访问和删除的表有些书籍里把队列称为先进先出（FIFO）表出队操作的一端称为队头入队操作的一端称为队尾,队列的链接表实现,用线性表的技术实现队列，就是利用元素位置的顺序表示入队的先后。先进先出需要在表的两端操作，实现起来比栈麻烦一些首先考虑用链接表的实现，为操作的效率，考虑带表尾指针的链接表这样才能保证入队/出队操作都能在 O(1) 时间完成如果没有表尾指针，入队就是 O(n) 操作，不好,队列的顺序表实现,现在考虑用顺序表技术实现队列假设用尾端插入实现 enqueue，出队操作应在表的首端进行为维护表中数据的完整性，出队操作取出首元素后，必须把它之后的元素逐个前

47、移，这样得到的是 O(n) 操作反过来实现：虽然从尾端弹出元素是 O(1) 操作，但首端插入也是 O(n) 操作。也出现了 O(n) 操作，同样很不理想考虑首元素出队后元素不前移，记住新队头位置。这一设计也有问题：反复入队出队，如果元素存储区固定，一定会在某次入队时出现队尾溢出表尾（表满）的情况出现这种溢出时，顺序表前部一般会留下一些空位这是“假溢出”，并不是真的用完了整个元素区如果元素存储区自动增长（如 list），首端将留下越来越大的空区。而且这片空区永远也用不到（完全浪费了）,队列的顺序表实现,简单实现方式有问题的示意图（设 q 是队列对象）：,实现方法不合适！,队列的顺序表实现,人们提

48、出了一种称为“环形队列”的技术，来解决这个问题,实现中的不变关系（不变式）：q.rear 是最后元素之后空位的下标q.head 是首元素的下标q.head, q.rear) 是队列中所有元素（看作按照环形排列）入队时，先存入，后移位,当 q.head = q.rear 时队列空队列满如何判断？条件不能与队列空判断相同,队列的顺序表实现,入队出队时的下标更新语句q.head = (q.head+1) % q.lenq.rear = (q.rear + 1) % q.len保证更新后的下标的值正确,存在其他设计。下面考虑：用 head 域记录队头元素位置， num 记录队中元素个数队尾空位在（q.

49、len 是表长）(q.head+q.elnum)%q.len基于这两个变量实现操作，就可以不留空置单元,队列的 list 实现,可以基于 Python 的 list 实现顺序表示的队列最简单的实现方法得到 O(1) 的 enqueue 和 O(n) 的dequeue由于 Python list 没提供检查元素存储区容量的机制，我们很难利用其自动扩充元素区的机制，但是可以自己做（看下面的做法）首先，队列可能由于空而无法 dequeue，自定义一个异常class QueueUnderflow(ValueError): passSQueue 类的基本考虑：用 SQueue 对象的一个 list 类型

50、的成分 _elems 存放队列元素用 _head 和 _num 记录首元素所在位置的下标和表中元素个数为能判断存储区满以便换一个表，需要记录表的长度，用 _len,数据不变式,这里的队列实现是一个比较复杂的问题要考虑一组操作和队列对象的一组成分，其中一些操作的执行可能改变一些对象成分的取值。问题：允许怎样的改变？如果一个操作有错或与其他操作不一致，就会破坏整个对象。可见，所有操作在成分修改方面必须有统一的原则，相互合作为保证对象的完整性，各操作的实现都必须遵循这些些原则为解决这类问题（一个数据结构的操作需相互协调，具有某种统一性），人们提出了“数据不变式”概念，它刻画“什么是一个完好的对象”数