v26编程指南中文版数据结构.doc

v2 6编程指南中文版 数据结构Navigation indexmodules|next|previous|Python v2.6.5 documentation?The Python Tutorial?5.Data Structures数据结构?This chapter describes some things youve learned about already in more detail,and adds some new things as well.本章将更加详细的介绍一些你已经了解的东西，另外我们还会添加一些新的东西。5.1.More on Lists List的更多细节?The list data type has some more methods.Here are all of the methods of list objects：List数据类型还有其他的一些方法。如下是List的所有方法：list.append(x)Add an item to the end of the list；equivalent to alen(a)：=x.list.extend(L)Extend the list by appending all the items in the given list；equivalent to alen(a)：=L.list.insert(i,x)Insert an item at agiven position.The first argument is the index of the element before which to insert,so a.insert(0,x)inserts at the front of the list,and a.insert(len(a),x)is equivalent to a.append(x).list.remove(x)Remove the first item from the list whose value is x.It is an error if there is no such item.list.pop(i)Remove the item at the given position in the list,and return it.If no index is specified,a.pop()removes and returns the last item in the list.(The square brackets around the iin the method signature denote that the parameter is optional,not that you should type square brackets at that position.You will see this notation frequently in the Python Library Reference.)list.index(x)Return the index in the list of the first item whose value is x.It is an error if there is no such item.list.count(x)Return the number of times xappears in the list.list.sort()Sort the items of the list,in place.list.reverse()Reverse the elements of the list,in place.An example that uses most of the list methods：如下的例子用到了上述的大部分方法：a=66.25,333,333,1,1234.5print a.count(333),a.count(66.25),a.count(x)2 10 a.insert(2,-1)a.append(333)a66.25,333,-1,333,1,1234.5,333a.index(333)1 a.remove(333)a66.25,-1,333,1,1234.5,333a.reverse()a333,1234.5,1,333,-1,66.25a.sort()a-1,1,66.25,333,333,1234.55.1.1.Using Lists as Stacks将list作为堆栈使用?The list methods make it very easy to use alist as astack,where the last element added is the first element retrieved(last-in,first-out).To add an item to the top of the stack,use append().To retrieve an item from the top of the stack,use pop()without an explicit index.For example：list的方法可以让List很轻易的变成一个堆栈来使用，而堆栈的特点就是最后一个被添加的数字最先被返回(last-in,first-out)。在堆栈的顶部添加一个元素，使用append()方法，返回堆栈顶部的元素，使用没有显式指定索引的pop()方法：stack=3,4,5stack.append(6)stack.append(7)stack3,4,5,6,7stack.pop()7 stack3,4,5,6stack.pop()6 stack.pop()5 stack3,45.1.2.Using Lists as Queues将List当做队列?It is also possible to use alist as aqueue,where the first element added is the first element retrieved(first-in,first-out)；however,lists are not efficient for this purpose.While appends and pops from the end of list are fast,doing inserts or pops from the beginning of alist is slow(because all of the other elements have to be shifted by one).同样也可以将List作为队列使用，队列的特点是最先添加的数据最先返回(first-in,first-out)；不过，List对此来说并不高效。将一个元素从尾部添加或者取出非常快，但是在List的顶部添加或者取出就会变得较慢了(因为其他的元素都将产生移位)。To implement aqueue,use collections.deque which was designed to have fast appends and pops from both ends.For example：可以用collections.deque去实现一个队列，它恰恰是为了快速从两端添加或者取出数据的。比如：from collections import deque queue=deque(Eric,John,Michael)queue.append(Terry)#Terry arrives queue.append(Graham)#Graham arrives queue.popleft()#The first to arrive now leavesEricqueue.popleft()#The second to arrive now leavesJohnqueue#Remaining queue in order of arrival deque(Michael,Terry,Graham)5.1.3.Functional Programming Tools功能性编程工具?There are three built-in functions that are very useful when used with lists：filter(),map(),and reduce().有三个内置的函数在同list一起使用的时候非常有用：filter(),map(),and reduce()。filter(function,sequence)returns asequence consisting of those items from the sequence for which function(item)is true.If sequence is astring or tuple,the result will be of the same type；otherwise,it is always alist.For example,to compute some primes：filter(function,sequence)返回序列中function(item)测试为真的所有元素的列表。如果sequence是一个string或者tuple，会返回和它一样的类型，否则返回一个list。def f(x)：return x%2！=0 and x%3！=0.filter(f,range(2,25)5,7,11,13,17,19,23map(function,sequence)calls function(item)for each of the sequences items and returns alist of the return values.For example,to compute some cubes：map(function,sequence)对队列中的每个元素调用function(item)函数，并且返回函数所有返回值的列表。比如，计算一些立方数：def cube(x)：return x*x*x.map(cube,range(1,11)1,8,27,64,125,216,343,512,729,1000More than one sequence may be passed；the function must then have as many arguments as there are sequences and is called with the corresponding item from each sequence(or None if some sequence is shorter than another).For example：可以传入多个队列；不过函数必须也要有和序列数(or None if some sequence is shorter than another)一样的形参数，每个队列对应一个形参。如下：seq=range(8)def add(x,y)：return x+y.map(add,seq,seq)0,2,4,6,8,10,12,14reduce(function,sequence)returns asingle value constructed by calling the binary function function on the first two items of the sequence,then on the result and the next item,and so on.For example,to compute the sum of the numbers 1through 10：reduce(function,sequence)返回二参数函数function在元素上的值，其中，函数首先计算前两个元素的值，再将返回值与第三个元素计算，依次计算得到最后结果。比如，如下例子计算1到10的和：def add(x,y)：return x+y.reduce(add,range(1,11)55If theres only one item in the sequence,its value is returned；if the sequence is empty,an exception is raised.如果序列中仅有一个元素，该元素的值被返回；如果序列为空，则会抛出异常。A third argument can be passed to indicate the starting value.In this case the starting value is returned for an empty sequence,and the function is first applied to the starting value and the first sequence item,then to the result and the next item,and so on.For example,也可以传入第三个参数用以表示初始值。在这种情况下，如果序列为空，则返回该值，部位空的话，则最开始计算该值与第一个元素，然后他们的结果再和第二个数计算，等等。如下：def sum(seq)：.def add(x,y)：return x+y.return reduce(add,seq,0).sum(range(1,11)55 sum()0Dont use this examples definition of sum()：since summing numbers is such acommon need,a built-in function sum(sequence)is already provided,and works exactly like this.不要使用例子中sum()的定义：因为求和函数很常用，所以一个内建的sum(sequence)的已经被提供。New in version 2.3.5.1.4.List Comprehensions?List comprehensions provide aconcise way to create lists without resorting to use of map(),filter()and/or lambda.The resulting list definition tends often to be clearer than lists built using those constructs.Each list comprehension consists of an expression followed by afor clause,then zero or more for or if clauses.The result will be alist resulting from evaluating the expression in the context of the for and if clauses which follow it.If the expression would evaluate to atuple,it must be parenthesized.List comprehension提供了一种创建List的简便方式，该方式无需使用map()，filter()和/或者lambda。list采用这种结构的定义通常比List的建立过程要直观得多。每一个list comprehension由一个表达式，以及表达式后的一个for从句，然后0个或者多个for或者if从句组成。如果表达式想要表达为一个tuple，必须用括号括起来。freshfruit=banana,loganberry,passion fruitweapon.strip()for weapon in freshfruitbanana,loganberry,passion fruitvec=2,4,63*x for xin vec6,12,183*x for xin vec if x312,183*x for xin vec if x2x,x*2for xin vec2,4,4,16,6,36x,x*2 for xin vec#error-parens required for tuples Filestdin,line 1,in?x,x*2 for xin vecSyntaxError：invalid syntax(x,x*2)for xin vec(2,4),(4,16),(6,36)vec1=2,4,6vec2=4,3,-9x*y for xin vec1 for yin vec28,6,-18,16,12,-36,24,18,-54x+y for xin vec1 for yin vec26,5,-7,8,7,-5,10,9,-3vec1i*vec2ifor iin range(len(vec1)8,12,-54List comprehensions are much more flexible than map()and can be applied to complex expressions and nested functions：List comprehensions比起map()来说适应性更好，而且可以应用到复杂的表达式和内嵌函数：str(round(355/113.0,i)for iin range(1,6)3.1,3.14,3.142,3.1416,3.141595.1.5.Nested List Comprehensions内嵌List Comprehensions?If youve got the stomach for it,list comprehensions can be nested.They are apowerful tool but like all powerful tools they need to be used carefully,if at all.Consider the following example of a3x3 matrix held as alist containing three lists,one list per row：如果这很对你的胃口，(我想说)list comprehension还能够被嵌套。这是非常强大的工具，不过和许多其他强大工具一样，你也必须小心谨慎的使用。考虑如下的例子，一个内含3个List的list所表示的3x3的矩阵，每个子list表示一行：mat=.1,2,3,.4,5,6,.7,8,9,.Now,if you wanted to swap rows and columns,you could use alist comprehension：现在，如果你想交换行和列，你可以使用list comprehension：printrowifor row in matfor iin0,1,21,4,7,2,5,8,3,6,9Special care has to be taken for the nested list comprehension：对于内嵌的list comprehension你需要特别的留意：To avoid apprehension when nesting list comprehensions,read from right to left.为了消除嵌套list comprehensions的忧虑，(我们)从右到左阅读。A more verbose version of this snippet shows the flow explicitly：下面是一段关于上述代码流程的详细表达：for iin0,1,2：for row in mat：print rowi,printIn real world,you should prefer built-in functions to complex flow statements.The zip()function would do agreat job for this use case：在真实世界中，你应该更多的使用内建函数，而不是复杂的流程语句。zip()函数在这种情况下起了很大的作用：zip(*mat)(1,4,7),(2,5,8),(3,6,9)See Unpacking Argument Lists for details on the asterisk in this line.参阅Unpacking Argument Lists来获取更多关于本行中星号的细节。5.2.The del statement?There is away to remove an item from alist given its index instead of its value：the del statement.This differs from the pop()method which returns avalue.The del statement can also be used to remove slices from alist or clear the entire list(which we did earlier by assignment of an empty list to the slice).For example：这里提供了一种给出索引而不是值对List中元素进行删除的方法：del语句。与返回一个值的pop()方法不同。del语句也可以用于删除List中的一个切片甚至是整个list(早些章节里面我们提到的将一个空List赋值给切片)。比如：a=-1,1,66.25,333,333,1234.5del a0a1,66.25,333,333,1234.5del a2：4a1,66.25,1234.5del a：a del can also be used to delete entire variables：del亦可以用来删除整个变量：del aReferencing the name ahereafter is an error(at least until another value is assigned to it).Well find other uses for del later.在此以后(直到它被赋值为另一个值)引用名字a将产生错误。我们将在后面探索更多del的用法。5.3.Tuples and Sequences Tuples和序列?We saw that lists and strings have many common properties,such as indexing and slicing operations.They are two examples of sequence data types(see Sequence Types-str,unicode,list,tuple,buffer,xrange).Since Python is an evolving language,other sequence data types may be added.There is also another standard sequence data type：the tuple.我们可以看到，list与string有诸多相同的地方，比如索引和切片操作。如下有两个序列的数据结构(参阅Sequence Types-str,unicode,list,tuple,buffer,xrange)。因为Python是一门正在进化的语言，其他的序列数据结构也会被加入。一种标准的序列数据结构是tuple。A tuple consists of anumber of values separated by commas,for instance：Tuple由逗号分开的一组值组成，比如：t=12345,54321,hello！t012345 t(12345,54321,hello！)#Tuples may be nested：.u=t,(1,2,3,4,5)u(12345,54321,hello！),(1,2,3,4,5)As you see,on output tuples are always enclosed in parentheses,so that nested tuples are interpreted correctly；they may be input with or without surrounding parentheses,although often parentheses are necessary anyway(if the tuple is part of alarger expression).如你所见，在输出是，tuple总是被括号括起来，这样，嵌套的tuple也可以被正确的解释；在输入时，可以使用或者不适用括号，不过括号一般情况下都是必须的(比如tuple是一个很大的表达式中的一部分)。Tuples have many uses.For example：(x,y)coordinate pairs,employee records from adatabase,etc.Tuples,like strings,are immutable：it is not possible to assign to the individual items of atuple(you can simulate much of the same effect with slicing and concatenation,though).It is also possible to create tuples which contain mutable objects,such as lists.Tuple有多种用途。比如：(x,y)坐标对，数据库中的雇员表等等。Tuple与string一样，也是不可以被修改的：你不可以对tuple中的单个元素进行赋值(不过你可以使用切片以及一系列相关的操作来模拟这个效果)。也可以创建内含可变对象的元素，比如list。A special problem is the construction of tuples containing 0or 1items：the syntax has some extra quirks to accommodate these.Empty tuples are constructed by an empty pair of parentheses；a tuple with one item is constructed by following avalue with acomma(it is not sufficient to enclose asingle value in parentheses).Ugly,but effective.For example：一个比较特殊的问题是在创建一个只有0个或者1个元素的tuple：为了符合这种创建，语法上会额外多出一些怪异的东西。空tuple使用一堆空的括号来创建；一个元素的tuple采用元素后加一个逗号(仅仅在用括号将单个元素括起来时不够的)的形式进行创建。虽然很丑陋，不过可以用起来了。比如：empty=()singleton=hello,#-note trailing comma len(empty)0 len(singleton)1 singleton(hello,)The statement t=12345,54321,hello！is an example of tuple packing：the values 12345,54321 andhello！are packed together in atuple.The reverse operation is also possible：语句t=12345,54321,hello！是一个tuple packing的例子：12345,54321和hello！被打包到一个tuple中。逆向的操作也支持：x,y,z=tThis is called,appropriately enough,sequence unpacking and works for any sequence on the right-hand side.Sequence unpacking requires the list of variables on the left to have the same number of elements as the length of the sequence.Note that multiple assignment is really just acombination of tuple packing and sequence unpacking.这被称之为sequence unpacking，右边的序列为任意类型皆可。序列划分需要左边的变量数与右边的序列大小一致。值得一提的是，多重赋值实际上是tuple打包和分块的结合。5.4.Sets?Python also includes adata type for sets.A set is an unordered collection with no duplicate elements.Basic uses include membership testing and eliminating duplicate entries.Set objects also support mathematical operations like union,intersection,difference,and symmetric difference.Python也有一种sets的数据结构。set是一个未排序且元素唯一的集合。最基本的应用包括关系测试和忽略重复的入口。Set对象还支持像联合、交叉、对比和对称对比等操作。Here is abrief demonstration：以下是一个简单的例子：basket=apple,orange,apple,pear,orange,bananafruit=set(basket)#create aset without duplicates fruit set(orange,pear,apple,banana)orangein fruit#fast membership testing Truecrabgrassin fruit False#Demonstrate set operations on unique letters from two words.a=set(abracadabra)b=set(alacazam)a#unique letters in aset(a,r,b,c,d)a-b#letters in abut not in bset(r,d,b)a|b#letters in either aor bset(a,c,r,d,b,m,z,l)a&b#letters in both aand bset(a,c)ab#letters in aor bbut not both set(r,d,b,m,z,l)5.5.Dictionaries?Another useful data type built into Python is the dictionary(see Mapping Types-dict).Dictionaries are sometimes found in other languages asassociative memoriesorassociative arrays.Unlike sequences,which are indexed by arange of numbers,dictionaries are indexed by keys,which can be any immutable type；strings and numbers can always be keys.Tuples can be used as keys if they contain only strings,numbers,or tuples；if atuple contains any mutable object either directly or indirectly,it cannot be used as akey.You cant use lists as keys,since lists can be modified in place using index assignments,slice assignments,or methods like append()and extend().另外一个非常有用的内建类型是dictionary(参见Mapping Types-dict)。在其他语言里面，字典通常作为关联内存或者关联数组出现。与序列被一个范围内的数字索引不同，字典使用keys进行索引，key可以是任意的不可变类型；字符串和数字通常作为key。tuple也可以作为key，如果它的元素都是字符串、数字或者tuple；如果一个tuple直接或者间接的含有一个可变的元素，则不可以作为key。你不能使用list作为key，因为list可以使用索引、切片或者类似append()和extend()的方法进行修改。It is best to think of adictionary as an unordered set of key：value pairs,with the requirement that the keys are unique(within one dictionary).A pair of braces creates an empty dictionary：.Placing acomma-separated list of key：value pairs within the braces adds initial key：value pairs to the dictionary；this is also the way dictionaries are written on output.最好将字典想象为一个组未排序的key：value对，而且在一个字典中，每个key值唯一。一对花括号创建一个空的字典：。在其中放入一组用逗号分开的key：value对将初始化字典；这种方式也是字典打印的方式。The main operations on adictionary are storing avalue with some key and extracting the value given the key.It is also possible to delete akey：value pair with del.If you store using akey that is already in use,the old value associated with that key is forgotten.It is an error to extract avalue using anon-existent key.字典中最主要的方法是将一个值以某个键存入或者以某个键取出该值。也可以使用del删除某个key：value对。如果你用一个已经存在的键存储某个值，该键之前的值将被清除。如果采用一个不存在的键取值将引起错误。The keys()method of adictionary object returns alist of all the keys used in the dictionary,in arbitrary order(if you want it sorted,just apply the sort()method to the list of keys).To check whether asingle key is in the dictionary,use the in keyword.keys()方法以任意顺序(如果你想进行排序，只需要使用sort()对键列表进行排序)返回字典对象中所有的键列表。确认某个键是否在字典中存在，使用in关键字。Here is asmall example using adictionary：如下是一个使用字典的小例子：tel=jack：4098,sape：4139telguido=4127 telsape：4139,guido：4127,jack：4098teljack4098 del telsapetelirv=4127 telguido：4127,irv：4127,jack：4098tel.keys()guido,irv,jackguidoin tel TrueThe dict()constructor builds dictionaries directly from lists of key-value pairs stored as tuples.When the pairs form apattern,list comprehensions can compactly specify the key-value list.dict()构造函数直接从键-值列表中构件一个字典，其中键-值采用tuple的形式存放在列表中。当这些来自一个模式，list comprehension可以非常紧凑的指定一个key-value列表。dict(sape,4139),(guido,4127),(jack,4098)sape：4139,jack：4098,guido：4127dict(x,x*2)for xin(2,4,6)#use alist comprehension2：4,4：16,6：36Later in the tutorial,we will learn about Generator Expressions which are even better suited for the task of supplying key-values pairs to the dict()constructor.在本指南的后续章节中，我们讲学习更好的为dict()构造函数提供key-value对的Generator Expressions。When the keys are simple strings,it is sometimes easier to specify pairs using keyword arguments：当键的类型为字符串时，可以更容易的指定关键字参数：dict(sape=4139,guido=4127,jack=4098)sape：4139,jack：4098,guido：41275.6.Looping Techniques循环?When looping through dictionaries,the key and corresponding value can be retrieved at the same time using the iteritems()method.在对字典进行循环访问的时候，使用iteritems()可以同时返回键和对应的值。knights=gallahad：the pure,robin：the bravefor k,v in knights.iteritems()：.print k,v.gallahad the pure robin the braveWhen looping through asequence,the position index and corresponding value can be retrieved at the same time using the enumerate()function.在对序列进行循环访问的时候，使用enumerate()函数可以同时返回位置索引以及与之对应的值。for i,v in enumerate(tic,tac,toe)：.print i,v.0 tic 1tac 2toeTo loop over two or more sequences at the same time,the entries can be paired with the zip()function.在对两个或者多个序列进行循环访问的时候，可以使用zip()进行配对。questions=name,quest,favorite coloranswers=lancelot,the holy grail,bluefor q,a in zip(questions,answers)：.printWhat is your0?It is1.forma