十一、Python简单数据结构应用（之… · 高中生学编程--Python学习

## 十、Python语言中简单数据结构的应用（之一） ----From a high schoolstudent's view to learn Python 关键字： python 列表堆栈数据结构递归调用函数组合问题后缀表达式前缀表达式逆波兰表达式运算符优先级本篇我们将简单介绍一下数据结构中的堆栈(stack)，以及在Python中利用堆栈所实现的一些应用。一、堆栈介绍堆栈是一个后进先出(LIFO)的数据结构，其工作方式就像往弹夹里面填子弹，在填好子弹之后，如果你要取出一颗子弹，那么你去除的这颗子弹一定是你最后填进去的，如果将子弹全部取出，那最后取出的那颗子弹一定是你最先填进去的那颗。把子弹当成我们程序中操作的元素，那么弹夹就是一个堆栈的模型了。在栈上"push"元素是个常用术语，意思是把一个对象添加到堆栈中；反之，要删除一个元素,你可以把它"pop"出堆栈。此外，还有”empty”来判断堆栈是否为空状态。很明显，使用Python中的List非常容易实现堆栈的模型，我们先复习一下List中有哪些内置的方法，在terminal窗口输入： dir(list) ['__add__', '__class__','__contains__', '__delattr__', '__delitem__', '__delslice__','__doc__', '__eq__', '__format__', '__ge__', '__getattribute__','__getitem__', '__getslice__', '__gt__', '__hash__', '__iadd__','__imul__', '__init__', '__iter__', '__le__', '__len__', '__lt__','__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__','__repr__', '__reversed__', '__rmul__', '__setattr__','__setitem__', '__setslice__', '__sizeof__', '__str__','__subclasshook__', 'append', 'count', 'extend', 'index', 'insert','pop', 'remove', 'reverse', 'sort'] 内容很多，介绍一些常用的： s[i] = x item i of s is replaced byx s[i:j] = t slice of s from i to j isreplaced by the contents of the iterable t del s[i:j] same as s[i:j] = [] s[i:j:k] = t the elements of s[i:j:k] arereplaced by those of t del s[i:j:k] removes the elements ofs[i:j:k] from the list s.append(x) same as s[len(s):len(s)] =[x] s.extend(x) same as s[len(s):len(s)] =x s.count(x) return number of i‘s for whichs[i] == x s.index(x[, i[, j]]) return smallest k such thats[k] == x and i <= k < j s.insert(i, x) same as s[i:i] = [x] s.pop([i]) same as x = s[i]; del s[i];return x s.remove(x) same as dels[s.index(x)] s.reverse() reverses the items of s inplace s.sort([cmp[, key[,reverse]]]) sort the items of s inplace 我们使用List的append()来实现堆栈的push，使用pop()不带参数的情况来实现堆栈的pop，使用len(list)==0来实现empty。举例： stack=[] len(stack)==0 True stack.append('1') stack.append('2') for a in '3456789': stack.append(a) ... stack ['1', '2', '3', '4', '5', '6','7', '8', '9'] stack.pop() '9' stack ['1', '2', '3', '4', '5', '6','7', '8'] len(stack)==0 False 二、如何使用堆栈来模拟递归函数调用看下面的程序，还是一个组合问题的程序： <table cellspacing="0" cellpadding="0" style="border-collapse: collapse"><tbody><tr><td valign="top" style="width: 25.1px; height: 528.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 2.2px 1.0px 1.0px; border-color: #000000 #50a299 #000000 #000000">1234567891011121314151617181920212223242526272829303132</td><td valign="top" style="width: 376.9px; height: 528.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 1.0px 1.0px 2.2px; border-color: #000000 #000000 #000000 #50a299">def comb(iterable, r,order=1): pool = tuple(iterable) if order != 1: pool =list(pool) pool.reverse() pool =tuple(pool) comb=[] n = len(pool) if r > n: returncomb indices = range(r) def subcomb(N, m, n, B): i=1 whileTrue: if i == m-n+2: break indices[N-n] = i+B ifn-1>0: subcomb(N, m-i, n-1, B+i) else: comb.append(tuple(pool[k-1] for k inindices)) i += 1 subcomb(r,n,r,0) return comb print "\ncomb-----"comb1=comb(tuple('123456'),4)for e in comb1: printeprint len(comb1) </td></tr></tbody></table> 这个程序就不像之前一句一句的详细介绍了，因为使用的方法和之前的没有根本的变化，简单说明如下： - 函数和之前相比，增加了一个参数，并且使用1作为缺省参数值，当该参数不为1时，我们将按照列表中元素的倒序来列出组合 - 递归函数为subcomb()，请注意，这个函数的定义和调用都在函数comb()中，这也是一种合法的方式 - 递归函数subcomb(N, m, n,B)实现的方式和前一篇介绍的稍有不同，前一篇是从后往前开始列出组合结果的，而这个是从前往后来列的，所以在参数中还额外的加了一个B用来表示递归子序列的起始位置；参数N表示最终组合中元素的个数，m、n分别表示当前所求的元素个数和组合中元素个数，递归调用时，m、n、B会变化程序的运行结果： comb----- ('1', '2', '3', '4') ('1', '2', '3', '5') ('1', '2', '3', '6') ('1', '2', '4', '5') ('1', '2', '4', '6') ('1', '2', '5', '6') ('1', '3', '4', '5') ('1', '3', '4', '6') ('1', '3', '5', '6') ('1', '4', '5', '6') ('2', '3', '4', '5') ('2', '3', '4', '6') ('2', '3', '5', '6') ('2', '4', '5', '6') ('3', '4', '5', '6') 15 介绍这个程序不是主要目的，主要的目的是想说明，递归是可以通过使用堆栈来模拟的，而且最终运行的结果也一模一样。先看程序： <table cellspacing="0" cellpadding="0" style="border-collapse: collapse"><tbody><tr><td valign="top" style="width: 25.1px; height: 592.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 2.2px 1.0px 1.0px; border-color: #000000 #50a299 #000000 #000000">123456789101112131415161718192021222324252627282930313233343536 </td><td valign="top" style="width: 376.9px; height: 592.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 1.0px 1.0px 2.2px; border-color: #000000 #000000 #000000 #50a299">def combusestack(iterable, r,order=1): pool = tuple(iterable) if order != 1: pool =list(pool) pool.reverse() pool =tuple(pool) comb=[] nc = len(pool) if r > nc: returncomb indices = range(r) stack=[] res=[-1,-1,-1,-1] m, n, B, i = nc, r, 0,1 while True: while i ==m-n+2: if len(stack) ==0: return comb (m,n,B,i)=stack.pop() i+=1 indices[r-n] = i+B ifn-1>0: res=[m, n, B, i] stack.append(res) m, n, B, i = m-i, n-1, B+i,1 continue else: comb.append(tuple(pool[k-1]for k in indices)) i +=1 print "comb usestack-----"comb1=combusestack(tuple('123456'),4)for e in comb1: printeprint len(comb1)</td></tr></tbody></table> 运行结果： comb use stack----- ('1', '2', '3', '4') ('1', '2', '3', '5') ('1', '2', '3', '6') ('1', '2', '4', '5') ('1', '2', '4', '6') ('1', '2', '5', '6') ('1', '3', '4', '5') ('1', '3', '4', '6') ('1', '3', '5', '6') ('1', '4', '5', '6') ('2', '3', '4', '5') ('2', '3', '4', '6') ('2', '3', '5', '6') ('2', '4', '5', '6') ('3', '4', '5', '6') 15 这个程序使用一个List来模拟堆栈，进入堆栈中的元素，也是一个List，我们在原来递归函数进行递归调用的地方，将函数的其中3个参数(N除外，因为在过程中不会改变)以及循环变量i，push到堆栈中，在原来函数结束的地方，在堆栈中pop一个List出来，直到堆栈空为止。在程序中也出现了一些比较奇特的语句，如line21、line27。这个程序的目的只是为了验证，递归调用可以通过堆栈来模拟函数调用，变换为非递归的函数；其实这个程序可读性不是很高，而且在line21由于堆栈的弹出，会改变循环变量i的值，在调试程序和理解程序方面会带来困惑。三、堆栈的简单应用举例介绍两个例子，一是利用堆栈的特性，反转字符串，另一是利用堆栈，检查表达式中的（）是否匹配。堆栈所具有的这种后进先出(LIFO)协议的特性，它可以作为一个通用的办法用于反转数据序列。例如，如果按照1，2，3的顺序把值压入一个堆栈，那么从堆栈中将它们弹出时的顺序为3，2，1。看下面字符窜反转的例子： <table cellspacing="0" cellpadding="0" style="border-collapse: collapse"><tbody><tr><td valign="top" style="width: 25.1px; height: 208.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 2.2px 1.0px 1.0px; border-color: #000000 #50a299 #000000 #000000">123456789101112 </td><td valign="top" style="width: 377.4px; height: 208.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 1.0px 1.0px 2.2px; border-color: #000000 #000000 #000000 #50a299">defrev(s): stack =[] n =len(s) if n==0: returnNone for c in s:stack.append(c) revstr ='' whilelen(stack)>0 : revstr += stack.pop() returnrevstr printrev('123456789')printrev('') </td></tr></tbody></table> 运行结果如下： 987654321 None 下面是关于检查括号是否匹配的例子文字说明的部分摘录于<<DataStructures and Algorithms in Python>> In the following application, we considerarithmetic expressions that may contain various pairs of groupingsymbols, such as • Parentheses: “(” and “)” • Braces: “{”and “}” • Brackets: “[” and “]” Each opening symbol must match itscorresponding closing symbol. For example, a left bracket, “[,”must match a corresponding right bracket, “],” as in the expression[(5+x)-(y+z)]. The following examples further illustrate thisconcept: • Correct: ()(()){([()])} • Correct: ((()(()){([()])})) • Incorrect:)(()){([()])} • Incorrect: ({[])} - Incorrect: ( 程序如下： <table cellspacing="0" cellpadding="0" style="border-collapse: collapse"><tbody><tr><td valign="top" style="width: 25.1px; height: 336.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 2.2px 1.0px 1.0px; border-color: #000000 #50a299 #000000 #000000">1234567891011121314151617181920 </td><td valign="top" style="width: 377.4px; height: 336.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 1.0px 1.0px 2.2px; border-color: #000000 #000000 #000000 #50a299">defis_matched(expr): """Return True if all delimiters are properlymatch; False otherwise.""" lefty = '({[' righty = ')}]' S = [] for c in expr: if c inlefty: S.append(c) elif c inrighty: if len(S) ==0: return False if righty.index(c) !=lefty.index(S.pop()): return False return len(S) == 0 printis_matched('[(5+x)-(y+z)]')printis_matched('{(5+x)-(y+z)]')printis_matched('[(5+x)-(y+z))') </td></tr></tbody></table> 运行结果分别显示为：True False False 做一些说明：我们仍然使用List来模拟堆栈，所以push和empty的形式和真正的堆栈有差异。程序的流程大致是这样： for循环扫描表达式，如果遇到的字符是’({[‘中的任一个，则将该字符压入堆栈；否则如果字符是’)}]’中的任一个，程序先判断当前堆栈是否为空，为空则返回错误，然后判断符号是否匹配，line13的语句就是检查是否匹配，这是本程序中唯一比较难的语句。我的更多文章： - [Python程序调试的一些体会](http://blog.sina.com.cn/s/blog_d6cca93e0101ewc9.html)(2013-10-06 22:57:35) - [十四、Python编程计算24点（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101euxx.html)(2013-10-03 22:18:28) - [十三、Python编程计算24点（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101eukc.html)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含图片") (2013-10-02 22:15:46) - [十二、Python简单数据结构应用（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101euk8.html)(2013-10-02 22:10:41) - [十、Python编程解决组合问题（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101entc.html)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含图片") (2013-09-21 23:37:27) - [九、Python编程解决组合问题（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ent7.html)(2013-09-21 23:32:54) - [八、Python的函数编程（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwj.html)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含视频") (2013-09-20 23:09:39) - [七、Python的函数编程（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwg.html)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含视频") (2013-09-20 23:09:10) - [一、Python语言的入门](http://blog.sina.com.cn/s/blog_d6cca93e0101ebw4.html)(2013-09-08 09:16:19) - [高中生如何学编程](http://blog.sina.com.cn/s/blog_d6cca93e0101e8fn.html)(2013-09-02 19:26:01)