Python中级-数据结构与算法分析.pdf

Python中级：数据结构与算法分析本手稿的目的是提供中文版的“数据结构(python语言版)”，参考：Problem solving with algorithms and data structures using python本手稿特点：语言追求易懂and简洁一有的时候我们读书读不懂只有两种可能，一是你本身没有到一 定水平，二就是作者语言表达能力不好。逻辑追求清晰and简单为了达到前两点，本文可能在许多处直接用编程语言：and,or,if,else,while,foo 等撰写。我们在读许多书的时候都有这样的感觉：看着厚，其实有用的就那么几句。所以有 人倾向于写cookbook，但是我们不打算写cookbook,因为再该介绍背景的地方一定要给 出背景才可以融会贯通。另外，本文可以用作“直接读英文原著”的过度图书，很多专业术语我们只使用英文，为 的是读者能强化记忆。第一章快速回顾python基础知识(-)数据操作A.基本数据类型：Int,Float基本操作运算：=,!=,and,or,not其他常用操作：1.Import math,math.sqrt()2.From decimal import Decimal,Decimal(2)#当 出现 long int Jong float错误时，这个很有用3.注意i+这种写法是错误的=i+=1B.复杂数据类型:list,string,tuple,set,dictionaryList常见操作示例：myList=1,bob,318,123,alice print myList 1,bob,318,123,alice print myList0 1 print myList1 bob print myListl 0 b myList1+love+myList4 bob love alice myListl*2+love +myList4,bobbob love alice bobM in myList True len(myList!5 myList0:2 1,bobList 常用方法：append(),sort(),sort(reverse=True),reverse(),del myListindex,index(),count().其中index。只能返回第一个匹配到的下标，所以它常结合其他命令使用，从而得到目标值所在的所有下标。For循环必须结合list使用,for item in myList:。如果需要设定步长，则需要使用range()函数：range(begin,end,step)for i in range(0,10,1):.print i 0123456789String常见操作示例：myString=DavidM 工myString0 D myStringQ:3 Dav mySt ring.split(V)Da,id myString*2,DavidDavid myString.upper(),DAVID myString.lower()david myString.center(10),David DNA=ATGCG AA CCB DNA,ATCfcGXtAAXtCC motif=DNA.split()motifATGCG,AA,CC如果不给split函数一个值的话，默认是s myString.Ijust(18),David myString.findCv)2 myString.rjust(10)DavidTuple不常用 我只见到在Django的url.py中，它的pattern转到url的code使用到了 tuple0所以，我们只需要认识tuple长什么样就行了：Tuple的声明是这样的 myTuple=nyTuple yourSet=set(3,puppy,Odoga)mySet.union(yourSet)set(True,2,3,dog,cat,puppy)mySet=set(2,3,True,dog,cat)mySet.difference(you rSet)dog in mySet set(True,2,cat)True mySub=set(2,3,dog)mySub.issubset(mySet)True mySub.difference(mySet)set()mySub.difference(mySet)=False mySub.difference(mySet)=set()|True mySet.intersection(yourSet)set(3,dog)mySet&yourSetset(3,dog)mySet|yourSetset(True,2,3,dog1,cat,puppy)mySet-yourSetset(True,2,cat)mySet ageDict=,bob:12,alice:22,relationship1:inLove ageDictMbob 12 len(ageDict)3 del ageDictrelationship len(ageDict)2 ageDict.has key(relationship)False ageDict.keys()bob,alice ageDict.values()12,22 ageDict.items()(bob,12),(alice,22)ageDict.get(12)ageDict.get(bob)12定义 function:def square(a,b):return a辜*b square(2,3)8定义class:class block:def insert(self,value):block.v=valuea=block()a.insert(2)a.v2P.S.在class里的每一个function都需要一个self作为input;构造器默认什么都不做，你也可以重写(override)这个function:init()class animal:继承(InheHtance)用法示例：.def jump(self):.print jump class human(animal):.def walk(self):.print walk a=animal()b=hu(nan()b.jump()jump b.walk()walk a.j ump()jump(二)控制操作For和if示例，冒泡排序：a=2,1,6,4,2,3 for i in range(len(a):for j in range(len(a)-l,i,-1):if aiaj:temp=aj aj=ail ai=temp a 1.2,2,3,4,6正则表达式与捕获变量:import re string=2008-4-3,m=re.search(d+)-(d)-(d).string)print m.groups()(2008,4,3)print in.group(l)2608 print m.group(2)4 print m.group(3)3传入参数：import sys,sys.argv1,sys.argv2反转 String:myString=11234,myString:-1while,if,else,time 函数示例：12345678910RTnTrnTfrom time import time start=tinie()i=0 while True:if itest.py(total time：2.64699983597 seconds第二章算法分析Python内置sort函数算法复杂度为O(nlogn),我们可以做出比他们效率还高的sort方法 第三章线性数据结构3.1 什么是线性数据结构？线性数据结构（linear structure）是n个数据元素的有序集合（collection）,它只有两 个端点（end）,这两个端点通常称为left,right或者top,bottom或者front,rear。什么是抽象数据结构（Abstract Data Type）?它是一种概念，用来描述数据元素的属 性（field）、成员方法（method）,并不关心这些属性和方法是怎么实现的。如堆栈，队列 都是ADT,他们都有insert等方法，但是他们既可以用数组实现，也可以用链表实现。线性结构属于ADT的一种。3.2 栈（Stack）栈这个ADT描述这样一种常见的数据组织形式：你用来放书的抽屉，你的书是一本压在一本上面的，如果你想放入一本书（push方法），你只能放在最上面的书上；反之，你想拿走一本书（pop方法），你只能拿走最上面的书；因此，如果你想要看最下面的一本书，你必须从最上面一个 一个的pop在写代码之前，我们需要先定义ADT（functional ADT definition）:L 抽象的stack包含方法 Push：在栈顶放入一个数据元素4 getTop：返回栈顶数据元素L pop：取出当前栈顶的数据元素，并返回该数据元素好，我们现在开始写代码，首先明确一点，凡是ADT都必然要以class的形式编写，它的 每一种方法都要以def某某：的形式编写，它的每一个属性都要在def_iZt_（）:中定义。所以，一个ADT代码的大致样子是这样的：1234567891011class stack:-3 def _init_(self):F 夜里定受属性def push(selfJvalue):-3 def getTop(sefl):returndef pop(self):我们现在知道，Python内置的list可以用下标来存取数据元素，所以我们可以预先定义一个list的长度（比如10）,这样它就有个两个端点：一个是下标为0的底点，在我们的栈ADT中，你是不可能对他直接操作的；一个是下标为9的顶点，在我们的栈ADT中，你可以对他直接操作：push,pop和getTopo最终代码：由于我们使用数组来实现栈ADT,所以我们每一次的push和pop,实际上实在对数据下标 进行操作，所以我们必须用一个变量存储数组的下标：这个就是栈顶的指针，它只指向栈顶 的数据元素。在之后，我们将看到要完成一个队列的coding,我们需要两个类似的指针。最基本的栈ADT连getTop都不需要，只需要push和pop就好了，getTop可以用先pop 再push实现；当然一个class里面装多少方法是有coder自己决定的，有些人可能觉得需 要一个getBottom的方法，或者加一些isFull等方法来防止异常错误出现。在编写一个项目时，你应该努力写出最简短最结构清楚的codeo3.2.1数学表达式的计算一个很重要的使用栈的应用就是数学表达式的计算，如：math=(13+12+(2+3)+0*2*3这种写法叫做中缀表达式，因为它符合：A+B的形式；它符合人类的计算习惯，但是如果 我们想让计算机也能计算这样的数学表达式，coding将很复杂，因此，人们开发了后缀表 达式：AB+的形式。例如：A+B*C写成后缀表达式的样子是ABC*+。如此，我们每次遇到 操作数A,B时，就将他们放入栈中，而我们每次读到操作符,都向前取出两个操作 数AB,然后将他俩进行计算，这样做知道读到最后一个操作符为止，就可以得到计算结果7o好了，现在的问题是，我们如何将中缀表达式转换成后缀表达式？如图，我们从左向右读取中缀表达式，当读到操作数时，直接output它，如A;接着，读到了操作符，将去其放入栈中，如*;然后，读到又一个操作数B,output它；接着我们读 到了+,由于+的优先级比*要低，因此我们需要先把上一个操作符取出来output,然后再把 新的操作符+放入栈中。再然后，又读到了 C,output它；然后读到了*,它比+优先级高，直接把他压入栈中，最后我们读到了 D,直接output;最后一个一个的取出栈中的操作符 OUtputo这个算法其实很普通，跟大多数算法一样，他就是先摸清楚规律，再把规律写成codeo数 据结构跟算法是相互影响的，没有良好的数据结构，算法会变得非常复杂。让我们总结一下需要写的方法：1.转换方法：toPostFix。他要实现中缀转后缀从左向右读取中缀表达式：判断：操作符还是操作数：操作数一直接output操作符一压入栈中：判断：该操作符的优先级如果小于栈顶操作符的优先级，则需要先pop()再push。否则直接压入栈中。判断：如果是“)，则一个一个pop(),直至!遇至式”为止。2.读取后缀表达式并计算的方法：doMath()从左向右读取后缀表达式：判断：操作符还是操作数：操作数-压入栈中操作符-取出栈顶头两个操作数然后计算，将结果再压入栈中Output栈顶值下面是代码示例，他创建了一个operation方法，用以在读后缀表达式时计算两个操作数;创建了一个stack类和一个expression类；后面在计算时，创建一个expression对象，将math表达式赋予该对象，然后使用对象方法toPostFix和doMathodef operation(a,b,oper):if open-=*:return float(a)*float(b)if open=+:return float(a)+float(b)if open=-:return float(a)-float(b)if open=：return float(a)/float(b)class stack:def _init_(self):self.size=20 self.list=0*self.size self.point=-1def push(selfJvalue):self.point+=1 self.listself.point=valuedef getTop(self):return self.listself.pointdef pop(self):topValue=self.listself.point self.point-1 return topValueclass expression:def _init_(self,exp):self.exp=exp.split()self.postFix=self.prec=self.prec*=3 self.prec/=3 self.prec+=2 self.prec-=2self.prec(=ldef toPostFix(self):opStack=stack()for item in self.exp:#code for(if item=(:opStack.push(item)#code for)elif item=):while opStack.getTop()!=(:self.postFix.append(opStack.pop()opStack.pop()#code for operator elif self.prec.has_key(item):if opStack.point=-1:opStack.push(item)elif self.precitem nath_expression.py 1312+23+02*3*+30.03.2.2 RNA二级结构识别这是我在处理RNAfold（RNA二级结构预测软件）结果时遇到的问题，我想要通过读取它 的result（也就是pair变量中的字符串）得到原RNA中哪些碱基（base）是配对的；其中 每一对（）就是一组配对的碱基，配对碱基与（）的下标相同。给出这样的input:RNA=TAGCGUC RNA中没旬T,这里只是为了结果容易识别 pair=（）.（）.表示非配对碱J求在该RNA中哪些碱基是配对碱基Code示例：算法思想很简单，就是把这两个字符串同时压入栈中，而一旦碰到“就pop（）class stack:省略，与上同RNA=TAGCGUC pair=().()RNA_stack=stack()pair_stack=stack()for i in range(len(RNA):if pairi=):state=pair_stack.pop()base=RNA_stack.pop()while state!=(:state=pair_stack.pop()base=RNA_stack.pop()print RNAi,:base state=pair_stack.getTop()base=RNA_stac k.getTop()else:RNA_stack.push(RNAi)pair_stack.push(pairi)：UsersAdministratorDesJRNAf old.py：A：G3.3 队歹(J(Queue)就像我们平时乘坐公交车排队一样，排在前面的人先上车，后来的只能排在最后面，不允许插队。队列ADT就是描述这样的一种数据组织形式。我们还是先定义队列ADT:Push():将数据元素放入队尾4-Pop():取出队首元素我们同样使用list来实现队列ADT,代码如下：12345678910111213141516RTSclass queue:def _init_(self):self.list=0*10 self.front=0self.rear=0A def push(self,value):self.listself.rear=value self.rear+=1A def pop(self):output=self.listself.front self.front+=1L return output注意我们使用了两个指针,front指向队首而rear指向队尾。这个code忽略了一个事实，那就是一旦队尾指针已经到达最大值，新加入的元素放入哪里呢？图48队尾赣关在我象末端的靖M所以，接下来我们引入循环队列的概念MAXSIZE-1队列的数据组成就像一个圆圈，表面上看没有头尾，一旦rear和front指向同一个数据时，表明该队列已满；想要放入一个元素，rear就向后移动一个位置；想要取出一个元素,front 也会向后移动一个位置。但是我们使用的是list，它毕竟是有下标的，rear指针一直向后走，走到list最大值时必须要回到【0】位置才能继续添加元素，如此可能会出现这样一个有趣 的现象：队尾的值要小于队首的值*4。从尾“攵后 q代码示例：class queue:def _init_(self):self.maxSize=5 self.list=0*self.maxSize self.front=0 self.rear=0def push(self,value):if self.rear=self.maxSize:self.rear=0self.listself.rear=value self.rear+=1def pop(self):output=self.listself.front self.front+=1 if self.front=self.maxSize:self.front=0 return output注意我们的代码并没有检查队列满时候的情况，而在实际情况时应该判断队列是否已满，如果已经满了，则不能继续插入数据，否则原队首数据将被覆盖。我不常用队列，因为它其实很像数组，也找不到它有什么重要的应用例子，许多书上写队列 的主要应用在于simulation,我对此也不是很了解。在树的层次遍历中，我们将再次提到队 列。除循环队列外，还有双端队列和优先级队列。3.4 链表(Linked list)class node:def _init_(selfdata):self.data=data self.next=None def insert(self,next):self.next=nextroot=node(None)a=node(2)b=node(3)c=node(4)root.insert(a)a.insert(b)b.insert(c)next=root.next while next!=None:print next.data next=next.next:!&liHuin is r ra r r c p 1 i J i”第四章树形结构构建树用node.data存放节点数据，用node.edge存放边的数据(可以是权重，标记)遍历树先序，中序，后序以及层次遍历的实现方法我们的遍历代码使用了 recursive的方法，与大多数遍历代码相似，有一点区别是是我 们的edge可以有很多条，因此我们用foEoop进行遍历，因此在中序遍历时有些复杂；层 次遍历要使用队列，先把root入列，然后每次遍历一个节点，就出列一个节点，然后把它 的children全部入列，用while loop直到队列为空。class queue:def _init_(self):self.maxSize=20 self.list=0*self.maxSize self.front=0 self.rear=0 self.size=0def push(self,value):if self.rear=self.maxSize:self.rear=0self.listself.rear=value self.rear+=1 self.size+=1def pop(self):output=self.listself.front self.front+=1 if self.front=self.maxSize:self.front=0 self.size-=1 return outputclass Node:def _init_(selfdata):self.data=data self.edge=def insert(self,node):self.edge.append(node)def preOrder(tree):#is done print tree.dataif tree!=None:for item in tree.edge:preOrder(item)def inOrder(tree):#is done if tree!=None:if tree.edge=:print tree.data flag=0#our tree is not a binary tree,#we use for loop to get each child,#yet the root value can only output once,#so we use a flag.for item in tree.edge:inOrder(item)if flag=0:print tree.data flag+=1def postOrder(tree):#is doneif tree!=None:for item in tree.edge:postOrder(item)print tree.data else:print tree.datadef levelOrder(root):tree=queue()#initial a empty queue tree.push(root)#en-queue while tree.size!=0:temp=tree.pop()print temp.data for item in temp.edge:tree.push(item)root=Node(3)a=Node(4)b=Node(5)c=Node(6)root.insert(a)root.insert(b)root.insert(c)d=Node(7)e=Node(8)f=Node(9)a.insert(d)d.insert(e)b.insert(f)#inOrder(root)#preOrder(root)#postOrder(root)levelOrder(root)我们构建的树是这个样子：（用dot语言编写）8第五章图