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

1、.v2 6编程指南中文版 数据结构Navigation indexmodules|next|previous|Python v2.6.5 documentation?The Python Tutorial?5.Data Structures数据构造?This chapter describes some things you've learned about already in more detail,and adds some new things as well.本章将更加详细的介绍一些你已经理解的东西，另外我们还会添加一些新的东西。5.1.More on Lists List的

2、更多细节?The list data type has some more methods.Here are all of the methods of list objects：List数据类型还有其他的一些方法。如下是List的所有方法：list.appendxAdd an item to the end of the list；equivalent to alena：=x.list.extendLExtend the list by appending all the items in the given list；equivalent to alena：=L.list.inserti,

3、xInsert an item at agiven position.The first argument is the index of the element before which to insert,so a.insert0,xinserts at the front of the list,and a.insertlena,xis equivalent to a.appendx.list.removexRemove the first item from the list whose value is x.It is an error if there is no such ite

4、m.list.popiRemove the item at the given position in the list,and return it.If no index is specified,a.popremoves 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 positi

5、on.You will see this notation frequently in the Python Library Reference.list.indexxReturn the index in the list of the first item whose value is x.It is an error if there is no such item.list.countxReturn the number of times xappears in the list.list.sortSort the items of the list,in place.list.rev

6、erseReverse 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.count333,a.count66.25,a.count'x'2 10 a.insert2,-1a.append333a66.25,333,-1,333,1,1234.5,333a.index3331 a.remove333a66.25,-1,333,1,1234.5,333a.reversea33

7、3,1234.5,1,333,-1,66.25a.sorta-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 retrie

8、ve an item from the top of the stack,use popwithout an explicit index.For example：list的方法可以让List很轻易的变成一个堆栈来使用，而堆栈的特点就是最后一个被添加的数字最先被返回"last-in,first-out"。在堆栈的顶部添加一个元素，使用append方法，返回堆栈顶部的元素，使用没有显式指定索引的pop方法：stack=3,4,5stack.append6stack.append7stack3,4,5,6,7stack.pop7 stack3,4,5,6stack.pop6 s

9、tack.pop5 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 ins

10、erts or pops from the beginning of alist is slowbecause 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 desi

11、gned 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 qu

12、eue.popleft#The first to arrive now leaves'Eric'queue.popleft#The second to arrive now leaves'John'queue#Remaining queue in order of arrival deque'Michael','Terry','Graham'5.1.3.Functional Programming Tools功能性编程工具?There are three built-in functions that are ve

13、ry useful when used with lists：filter,map,and reduce.有三个内置的函数在同list一起使用的时候非常有用：filter,map,and reduce。filterfunction,sequencereturns asequence consisting of those items from the sequence for which functionitemis true.If sequence is astring or tuple,the result will be of the same type；otherwise,it is

14、always alist.For example,to compute some primes：filterfunction,sequence返回序列中functionitem测试为真的所有元素的列表。假设sequence是一个string或者tuple，会返回和它一样的类型，否那么返回一个list。def fx：return x%2！=0 and x%3！=0.filterf,range2,255,7,11,13,17,19,23mapfunction,sequencecalls functionitemfor each of the sequence's items and ret

15、urns alist of the return values.For example,to compute some cubes：mapfunction,sequence对队列中的每个元素调用functionitem函数，并且返回函数所有返回值的列表。比方，计算一些立方数：def cubex：return x*x*x.mapcube,range1,111,8,27,64,125,216,343,512,729,1000More than one sequence may be passed；the function must then have as many arguments as th

16、ere are sequences and is called with the corresponding item from each sequenceor None if some sequence is shorter than another.For example：可以传入多个队列；不过函数必须也要有和序列数or None if some sequence is shorter than another一样的形参数，每个队列对应一个形参。如下：seq=range8def addx,y：return x+y.mapadd,seq,seq0,2,4,6,8,10,12,14reduce

17、function,sequencereturns 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：reducefunction,sequence返回二参数函数function在元素上的值，其中，函数首先计算前两个元素的值，再将返

18、回值与第三个元素计算，依次计算得到最后结果。比方，如下例子计算1到10的和：def addx,y：return x+y.reduceadd,range1,1155If there's 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 thi

19、s 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 sumseq：.de

20、f addx,y：return x+y.return reduceadd,seq,0.sumrange1,1155 sum0Don't use this example's definition of sum：since summing numbers is such acommon need,a built-in function sumsequenceis already provided,and works exactly like this.不要使用例子中sum的定义：因为求和函数很常用，所以一个内建的sumsequence的已经被提供。New in version 2

21、.3.5.1.4.List Comprehensions?List comprehensions provide aconcise way to create lists without resorting to use of map,filterand/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

22、 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。li

23、st采用这种构造的定义通常比List的建立过程要直观得多。每一个list comprehension由一个表达式，以及表达式后的一个for从句，然后0个或者多个for或者if从句组成。假设表达式想要表达为一个tuple，必须用括号括起来。freshfruit='banana','loganberry','passion fruit'weapon.stripfor weapon in freshfruit'banana','loganberry','passion fruit'vec=2,4,63*x

24、 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 File"stdin",line 1,in?x,x*2 for xin vecSyntaxError：invalid syntaxx,x*2for xin vec2,4,4,16,6,36vec1=2,4,6vec2=4,3,-9x*y for xin vec1 for yin vec2

25、8,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 rangelenvec18,12,-54List comprehensions are much more flexible than mapand can be applied to complex expressions and nested functions：List comprehensions比起map来说适应性更好，而且可以应用到复杂的表达式和内嵌函数：strround355/113.0,i

26、for iin range1,6'3.1','3.14','3.142','3.1416','3.14159'5.1.5.Nested List Comprehensions内嵌List Comprehensions?If you've got the stomach for it,list comprehensions can be nested.They are apowerful tool but like all powerful tools they need to be used careful

27、ly,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 column

28、s,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.为

29、了消除嵌套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 zipfunction would do agreat job for this use case：在真实

30、世界中，你应该更多的使用内建函数，而不是复杂的流程语句。zip函数在这种情况下起了很大的作用：zip*mat1,4,7,2,5,8,3,6,9See 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 stateme

31、nt.This differs from the popmethod which returns avalue.The del statement can also be used to remove slices from alist or clear the entire listwhich we did earlier by assignment of an empty list to the slice.For example：这里提供了一种给出索引而不是值对List中元素进展删除的方法：del语句。与返回一个值的pop方法不同。del语句也可以用于删除List中的一个切片甚至是整个l

32、ist早些章节里面我们提到的将一个空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 errorat least until another value is assigned to it.We'll find other use

33、s 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 typessee Sequence Types-str,unicode,list,tuple,buffer,xrange.Since Py

34、thon 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

35、of anumber of values separated by commas,for instance：Tuple由逗号分开的一组值组成，比方：t=12345,54321,'hello！'t012345 t12345,54321,'hello！'#Tuples may be nested：.u=t,1,2,3,4,5u12345,54321,'hello！',1,2,3,4,5As you see,on output tuples are always enclosed in parentheses,so that nested tuples

36、 are interpreted correctly；they may be input with or without surrounding parentheses,although often parentheses are necessary anywayif the tuple is part of alarger expression.如你所见，在输出是，tuple总是被括号括起来，这样，嵌套的tuple也可以被正确的解释；在输入时，可以使用或者不适用括号，不过括号一般情况下都是必须的比方tuple是一个很大的表达式中的一部分。Tuples have many uses.For e

37、xample：x,ycoordinate pairs,employee records from adatabase,etc.Tuples,like strings,are immutable：it is not possible to assign to the individual items of atupleyou can simulate much of the same effect with slicing and concatenation,though.It is also possible to create tuples which contain mutable obj

38、ects,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

39、 an empty pair of parentheses；a tuple with one item is constructed by following avalue with acommait is not sufficient to enclose asingle value in parentheses.Ugly,but effective.For example：一个比较特殊的问题是在创立一个只有0个或者1个元素的tuple：为了符合这种创立，语法上会额外多出一些怪异的东西。空tuple使用一堆空的括号来创立；一个元素的tuple采用元素后加一个逗号仅仅在用括号将单个元素括起来时

40、不够的的形式进展创立。虽然很丑陋，不过可以用起来了。比方：empty=singleton='hello',#-note trailing comma lenempty0 lensingleton1 singleton'hello',The statement t=12345,54321,'hello！'is an example of tuple packing：the values 12345,54321 and'hello！'are packed together in atuple.The reverse operation

41、 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 hav

42、e 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 s

43、et 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

44、对象还支持像结合、穿插、比照和对称比照等操作。Here is abrief demonstration：以下是一个简单的例子：basket='apple','orange','apple','pear','orange','banana'fruit=setbasket#create aset without duplicates fruit set'orange','pear','apple','banana''orange&#

45、39;in fruit#fast membership testing True'crabgrass'in 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

46、9;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','

47、;z','l'5.5.Dictionaries?Another useful data type built into Python is the dictionarysee Mapping Types-dict.Dictionaries are sometimes found in other languages as"associative memories"or"associative arrays".Unlike sequences,which are indexed by arange of numbers,dictio

48、naries 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 can't use lists as keys,si

49、nce lists can be modified in place using index assignments,slice assignments,or methods like appendand extend.另外一个非常有用的内建类型是dictionary参见Mapping Types-dict。在其他语言里面，字典通常作为关联内存或者关联数组出现。与序列被一个范围内的数字索引不同，字典使用keys进展索引，key可以是任意的不可变类型；字符串和数字通常作为key。tuple也可以作为key，假设它的元素都是字符串、数字或者tuple；假设一个tuple直接或者间接的含有一个可变的

50、元素，那么不可以作为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 uniquewithin one dictionary.A pair of braces creates an empty dictionary：.Placing acomma-separated list of key：value p

51、airs 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

52、 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对

53、。假设你用一个已经存在的键存储某个值，该键之前的值将被去除。假设采用一个不存在的键取值将引起错误。The keysmethod of adictionary object returns alist of all the keys used in the dictionary,in arbitrary orderif you want it sorted,just apply the sortmethod to the list of keys.To check whether asingle key is in the dictionary,use the in keyword.keys方法

54、以任意顺序假设你想进展排序，只需要使用sort对键列表进展排序返回字典对象中所有的键列表。确认某个键是否在字典中存在，使用in关键字。Here is asmall example using adictionary：如下是一个使用字典的小例子：tel='jack'：4098,'sape'：4139tel'guido'=4127 tel'sape'：4139,'guido'：4127,'jack'：4098tel'jack'4098 del tel'sape'tel&#

55、39;irv'=4127 tel'guido'：4127,'irv'：4127,'jack'：4098tel.keys'guido','irv','jack''guido'in tel TrueThe dictconstructor builds dictionaries directly from lists of key-value pairs stored as tuples.When the pairs form apattern,list comprehension

56、s 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'：4127dictx,x*2for xin2,4,6#use alist comp

57、rehension2：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 dictconstructor.在本指南的后续章节中，我们讲学习更好的为dict构造函数提供key-value对的Generator Expressions。When the keys are simple strings,it is sometimes easier

58、to specify pairs using keyword arguments：当键的类型为字符串时，可以更容易的指定关键字参数：dictsape=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 iteri

59、temsmethod.在对字典进展循环访问的时候，使用iteritems可以同时返回键和对应的值。knights='gallahad'：'the pure','robin'：'the brave'for 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

60、 same time using the enumeratefunction.在对序列进展循环访问的时候，使用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 zipfunction.在对两个或者多个序列进展循环访问的时候，可以使用zip进展配对。questions='name','quest','favorite color'answers='lancelot','the holy grail','blue'for q,a i