十一、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)