数据结构与算法（Python语言实现）课件全套 郭炜 1. 绪论、2. Python 知识巩固与提高- -20. 贪心算法

信息科学技术学院数据结构与算法

(Python描述)课程信息教材数据结构与算法（Python语言实现）郭炜编著清华大学出版社另有Java语言实现，C/C++语言实现两本，均已经由清华大学出版社出版绪论信息科学技术学院3算法信息科学技术学院

郭炜瑞士马特洪峰什么是算法算法是对计算过程的描述，是为了解决某个问题而设计的有限长操作序列算法具有以下特性：有穷性：一个算法必须可以用有穷条指令描述，且必须在执行有穷次操作后终止。每次操作都必须在有穷时间内完成。算法终止后必须给出所处理问题的解或宣告问题无解。确定性：一个算法,对于相同的输入，无论运行多少次，总是得到相同的输出。也可以说只要算法运行前的初始条件相同，那么算法运行的结果也相同。5什么是算法算法是对计算过程的描述，是为了解决某个问题而设计的有限长操作序列算法具有以下特性：可行性：算法中的指令（或描述语句）含义明确无歧义，且可以被机械化地自动执行。输入/输出：输入指的是描述算法所处理的问题的数据，输出指的是描述该问题的答案的数据。算法可以不需要输入。但是没有输出的算法是没有意义的。6常用的算法思想枚举法：对所有可能的解进行逐个验证，直到发现真正的解。二分法：对于有些问题，将所有可能解排序，通过对位于解的查找区间中点的解进行一次验证，就可以找到解或缩小查找区间到原来的一半，这样就能很快找到解或宣告无解。贪心法：在寻找解的过程中，每一步都只选取眼前最优的做法，不考虑后续影响。并不适用于所有需要求最优解的问题。7常用的算法思想递归法和分治法：为解决问题，可以先采取一步行动，剩下的问题就变成和原问题形式相同、但是规模更小的问题，这样就可以用递归解决。或者，将原问题分解为几个和原问题形式相同、但是规模更小的子问题，子问题都解决，原问题也就解决，这就叫分治。分治往往用递归实现8常用的算法思想深度优先搜索、回溯和分支限界法：在许多问题中，搜索解的过程，可以抽象为在迷宫中找出口。走迷宫的一个策略就是能往前走就往前走，这就叫深度优先；走不动了就回退到上一个岔路口选没走过的岔道继续走，这就叫回溯。有的情况下有办法预判一个岔道走下去肯定没前途，于是就不会走它，这就叫分支限界法。回溯和分支限界都是深度优先搜索过程中使用的手段9常用的算法思想广度优先搜索法：解决问题，可能需要采取多步行动，每步行动都有不同选择。先把第一步能采取的所有选择都试一遍，看看问题有没有解决。如果没有，再把采取两步行动的所有方案都试一遍，看看问题有没有解决......这样当问题解决时，采取的步数一定是最少的10常用的算法思想动态规划法：单纯采用深度优先搜索的办法，可能会导致大量重复计算，即相同的子问题被计算多次，这往往导致计算量指数增长。在搜索过程中将求得的子问题的解保存下来，避免重复计算，用空间换时间，这就是动态规划的思想11程序或算法的

时间复杂度信息科学技术学院美国加州1号公路程序或算法的时间复杂度一个程序或算法的时间效率，也称“时间复杂度”，有时简称“复杂度”复杂度常用大的字母O和小写字母n来表示，比如O(n),O(n2)等。n代表问题的规模，O(X）就表示解决问题的时间和X成正比关系(粗略理解）时间复杂度是用算法运行过程中，某种时间固定的操作需要被执行的次数和n的关系来度量的。在无序数列中查找某个数，复杂度是O(n)13程序或算法的时间复杂度计算复杂度的时候，只统计执行次数最多的(n足够大时)那种固定操作(称为基本操作)的次数。比如某个算法需要执行加法n2次，除法10000n次，那么就记其复杂度是O(n2)的。14程序或算法的时间复杂度求非空列表a的最大值defMax(a):maxV=a[0]forxina:#基本操作:取x的值ifmaxV<x:#基本操作:比较maxV=xreturnmaxV复杂度O(n)15程序或算法的时间复杂度在没有重复元素的整数数组a中找出两个数，使其和为整数mdeffindPair(a,m):#本函数也适合a中元素有重复的情况

n=len(a)foriinrange(n-1):forjinrange(i+1,n):ifa[i]+a[j]==m:returna[i],a[j]returnNone基本操作:

取j的值，和第5行看i的值、看j的值，看m的值、看a[i]、看[j]、算a[i]+a[j],以及用"=="进行比较......16程序或算法的时间复杂度在没有重复元素的整数数组a中找出两个数，使其和为整数mdeffindPair(a,m):#本函数也适合a中元素有重复的情况

n=len(a)foriinrange(n-1):forjinrange(i+1,n):ifa[i]+a[j]==m:returna[i],a[j]returnNone基本操作执行次数：(n-1)+(n-2)+......+2+1=n2/2–n/2程序复杂度为O(n2)17程序或算法的时间复杂度如果复杂度是多个n的函数之和，则只关心随n的增长增长得最快的那个函数 O(n3+n2)=>O(n3) O(2n+n3)=>O(2n) O(n!+3n)=>O(n!)18程序或算法的时间复杂度常数复杂度：O(1)时间(操作次数)和问题的规模无关对数复杂度：O(log(n))线性复杂度：O(n)多项式复杂度：O(nk)指数复杂度：O(an)阶乘复杂度：O(n!)19程序或算法的时间复杂度在无序数列中查找某个数(顺序查找)

O(n)插入排序、选择排序等笨排序方法O(n2)快速排序O(n×log(n))二分查找O(log(n))20Python中一些操作的时间复杂度总结O(1)复杂度的常见操作1)根据下标访问列表、字符串、元组中的元素2)在集合、字典中增删元素3)调用列表的append函数在列表末尾添加元素，以及用pop()函数删除列表末尾元素4)用in判断元素是否在集合中或某关键字是否在字典中5)以关键字为下标访问字典中的元素的值6)用len函数求列表、元组、集合、字典的元素个数21Python中一些操作的时间复杂度总结O(n)复杂度的常见操作1)用in判断元素是否在字符串、元组、列表中2)用insert在列表中插入元素3)用remove或del删除列表中的元素4)用字符串、元组或列表的find、rfind、index等函数做顺序查找5)用字符串、元组或列表的count函数计算元素出现次数6)用max,min函数求列表、元组的最大值，最小值7)列表和元组加法：O(n)或O(m+n)a=a+b,a+=b复杂度各不相同8)列表元组字符串切片a[x:y:z]22Python中一些操作的时间复杂度总结O(nlog(n))复杂度的常见操作Python自带排序sort,sortedO(log(n))复杂度的常见操作在排好序的列表或元组上进行二分查找（初始的查找区间是整个元组或列表，每次和查找区间中点比较大小，并缩小查找区间到原来的一半。类似于查英语词典）有序就会找得快！Pyhon并不自带二分查找函数23in用于列表和用于字典、集合的区别ainb若b是列表，字符串或元组，则该操作时间复杂度O(n)，即时间和b的元素个数成正比若b是字典或集合，则该操作时间复杂度O(1)，即时间基本就是常数，和b里元素个数无关因此集合用于需要经常判断某个东西是不是在一堆东西里的情况此种场合用列表替代集合，容易导致超时!!!!24最坏复杂度、平均复杂度、最好复杂度算法的复杂度有最好情况下复杂度、最坏情况下的复杂度和平均复杂度之分，虽然许多情况下最坏复杂度和平均复杂度恰好相同。快速排序为例，一般情况下待排序序列杂乱无章，这种情况下快速排序的复杂度就是平均复杂度O(n×log(n))，但是在待排序的序列处于基本有序或基本逆序的最坏情况下，其复杂度会变成O(n2)。25写程序要有复杂度意识低效率的写法：lst=map(int,input().split())print(max(lst)*max(lst))#输出列表最大值的平方26写程序要有复杂度意识低效率的写法：lst=map(int,input().split())print(max(lst)*max(lst))#输出列表最大值的平方正常的写法：lst=map(int,input().split())a

=

max(lst)print(a*a)27写程序要有复杂度意识求斐波那契数列第n项递推写法：deffib(n):#求斐波那契数列第n项

a1=a2=1foriinrange(n-2):a1,a2=a2,a1+a2returna2复杂度：O(n)28写程序要有复杂度意识求斐波那契数列第n项递归写法：deffib(n):ifn<=2:return1returnfib(n-1)+fib(n-2)复杂度：？29写程序要有复杂度意识求斐波那契数列第n项递归写法：deffib(n):ifn<=2:return1returnfib(n-1)+fib(n-2)复杂度：O(1.618n)因为存在大量重复计算30数据结构信息科学技术学院美国加州1号公路什么是数据结构数据结构(datastructure)就是数据的组织和存储形式。描述一个数据结构，需要指出其逻辑结构、存储结构和可进行的操作。将数据的单位称作“元素”或“结点”。数据结构描述的就是结点之间的关系。32数据的逻辑结构从逻辑上描述结点之间的关系，和数据的存储方式无关。集合结构：结点之间没有什么关系，只是属于同一集合。如set。线性结构：除了最靠前的结点，每个结点有唯一前驱结点；除了最靠后的结点，每个结点有唯一后继结点。如list。33数据的逻辑结构树结构：有且仅有一个结点称为“根结点”，其没有前驱(父结点)；有若干个结点称为“叶结点”，没有后继(子结点)；其它结点有唯一前驱，有1个或多个后继。如家谱图结构：每个结点都可以有任意多个前驱和后继，两个结点还可以互为前驱后继。如铁路网，车站是结点。

34数据的逻辑结构35数据的存储结构数据在物理存储器上存储的方式，大部分情况下指的是数据在内存中存储的方式。顺序结构：结点在内存中连续存放，所有结点占据一片连续的内存空间。如list。链接结构：结点在内存中可不连续存放，每个结点中存有指针指向其前驱结点和/或后继结点。如链表，树。36数据的存储结构数据在物理存储器上存储的方式，大部分情况下指的是数据在内存中存储的方式。索引结构：将结点的关键字信息（比如学生的学号）拿出来单独存储，并且为每个关键字x配一个指针指向关键字为x的结点，这样便于按照关键字查找到相应的结点。散列结构：设置散列函数，散列函数以结点的关键字为参数，算出一个结点的存储位置。37数据的存储结构数据的逻辑结构和存储结构无关一种逻辑结构的数据，可以用不同的存储结构来存储。树结构、图结构可以用链接结构存储，也可以用顺序结构存储线性结构可以用顺序结构存储，也可以用链接结构存储。38数据结构上的操作建立（初始化)插入结点删除结点查找结点求结点前驱或结点后继。

如在线性表、树和图上进行随机访问。即“找第i个结点”，如顺序表。掌握一个数据结构，不但要了解其逻辑结构、存储结构，以及其上进行的各种操作，还需要知道每种操作的时间复杂度。39郭炜信息科学技术学院数据结构与算法

(Python描述)课程信息教材数据结构与算法（Python语言实现）郭炜编著清华大学出版社另有Java语言实现，C/C++语言实现两本，均已经由清华大学出版社出版Python知识巩固与提高信息科学技术学院42Python变量的

指针本质信息科学技术学院

郭炜瑞士马特洪峰一道题目下面程序的输出结果是：defswap(x,y): x,y=y,x x[0],y[0]=y[0],x[0]a=[1,2,3]b=[4,5,6]swap(a,b)print(a)44A)[1,2,3]

B)[4,5,6]

C)[1,5,6]

D)[4,2,3]

一道题目下面程序的输出结果是：defswap(x,y): x,y=y,x x[0],y[0]=y[0],x[0]a=[1,2,3]b=[4,5,6]swap(a,b)print(a)45A)[1,2,3]

B)[4,5,6]

C)[1,5,6]

D)[4,2,3]

又一道题目下面程序的输出结果是：a=[[0]]*2+[[0]]*2print(a) #输出[[0],[0],[0],[0]]a[0][0]=5print(a) 46A)[[5],[0],[0],[0]]B)[[5],[5],[5],[5]]

C)[[5],[5],[0],[0]]D)[[5],[0],[5],[0]]

又一道题目下面程序的输出结果是：a=[[0]]*2+[[0]]*2print(a) #输出[[0],[0],[0],[0]]a[0][0]=5print(a) 47A)[[5],[0],[0],[0]]B)[[5],[5],[5],[5]]

C)[[5],[5],[0],[0]]D)[[5],[0],[5],[0]]

Python中的变量都是指针Python中所有可赋值的东西，即可以出现在

赋值号"="左边的东西，都是指针指针即代表内存单元的地址将指针称作“箭头",更容易理解。所有变量都是箭头，指向内存某处对变量进行赋值的本质，就是让该变量（箭头）指向某个地方48493a4b对变量进行赋值，意味着将变量指向某处Python中的变量都是指针a=3b=4Python中的变量都是指针用一个变量对另一个变量赋值意味着让

两个变量指向同一个地方503a4ba=bis运算符和==的区别aisb为True说a和b指向同一个地方a==b为True说明a和b指向的地方放的的东西相同，但是a和b不一定指向相同的地方a=b会使得a和b指向同一个地方513is运算符和==的区别xisy表示x和y是否指向同一个地方x==y表示x和y的内容是否相同a=[1,2,3,4]b=[1,2,3,4]print(a==b)#>>Trueprint(aisb)#>>False52a[1,2,3,4]b[1,2,3,4]is运算符和==的区别xisy表示x和y是否指向同一个地方x==y表示x和y的内容是否相同a=[1,2,3,4]b=[1,2,3,4]print(a==b)#>>Trueprint(aisb)#>>Falsec=aprint(a==c)#>>Trueprint(aisc)#>>True53a[1,2,3,4]b[1,2,3,4]cis运算符和==的区别a[2]="ok"print(c)#>>[1,2,'ok',4]因为a和c指向同一个地方，所以修改a[2]，c[2]也变。a[2]和c[2]是同一个东西54a[1,2,'ok',4]b[1,2,3,4]cis运算符和==的区别对int,float,complex,str,tuple类型的变量a和b，只需关注a==b是否成立，一般不需要关注aisb是否成立。因这些数据本身都不会更改，不会产生a指向的东西改了b指向的东西也跟着变的情况对list,dict,set类型的变量a和b，a==b和aisb的结果都需要关注。因这些数据本身会改变。改变了a指向的内容，说不定b指向的内容也变了。55列表元素的指针本质列表的元素也可以赋值，因此也是指针56a=[1,2,3,4]b=[1,2,3,4]a[,,,]b[,,,]准确的效果：1234a[0],a[1]....b[0],b[1].....都是指针列表元素的指针本质列表的元素也可以赋值，因此也是指针57a=[1,2,3,4]b=[1,2,3,4]a[,,,]b[,,,]准确的效果：1234执行b[0],b[2]=9,4后9列表元素的指针本质列表的元素也可以赋值，因此也是指针58a

=b=[]a.append(1)print(b) #>>[1]a=[[0]]*3#a中的3个元素都指向同一张列表[0]a[0].append(1)print(a)#>>[[0,1],[0,1],[0,1]]元组元素的指针本质元组的元素虽然不可赋值，但也是指针59a=[1,2,3,4]b=(100,a)a[0]=1000print(b) #>>(100,[1000,2,3,4])函数参数的传递信息科学技术学院

郭炜京都金阁寺函数参数的传递函数参数传递方式都是传值，即形参是实际参数的一个拷贝。函数参数也是指针。形参和实参指向同一个地方。对形参赋值（让其指向别处）不会影响实参。defSwap(x,y):tmp=xx=yy=tmpa=4b=5Swap(a,b)print(a,b) #>>4,5614a5bxytmp=x刚执行完tmp函数参数的传递函数参数传递方式都是传值，即形参是实际参数的一个拷贝。函数参数也是指针。形参和实参指向同一个地方。对形参赋值（让其指向别处）不会影响实参。defSwap(x,y):tmp=xx=yy=tmpa=4b=5Swap(a,b)print(a,b) #>>4,5624a5bxyy=tmp执行后tmp函数参数的传递但是如果函数执行过程中，改变了形参所指向的地方的内容，则实参所指向的地方内容也会被改变。defSwap(x,y):tmp=x[0]x[0]=y[0]#若x,y是列表，则x[0],y[0],tmp都是指针y[0]=tmpa=[4,5] b=[6,7]Swap(a,b)#进入函数后，x和a指向相同地方，y和b指向相同地方print(a,b) #>>[6,5][4,7]63函数参数的传递进入Swap函数执行完tmp=x[0]时64a[,]b[,]4567xya[,]b[,]4567xySwap函数执行完时：tmptmpPython中的函数信息科学技术学院内蒙古浑善达克沙地global变量和nonlocal变量'global'关键字用于声明变量是在所有函数外部定义的变量。'nonlocal'变量用于声明变量是在函数的外围函数定义的变量：k1,k2=1,2deff():n1,n2=10,20defg():nonlocaln1globalk1k1*=10n1*=10print(k2,n2)#>>220g()print(k1,n1) #>>10100f()高阶函数函数可以赋值给变量，也可以作为函数的参数和返回值。如果一个函数能接收函数作为参数，或其返回值是函数，这样的函数就称为高阶函数。defsquare(x):returnx*xdefinc(x):returnx+1defcombine(f,g,x):returnf(g(x))print(combine(square,inc,4))#>>25print(combine(inc,square,4))#>>17defcombineFunctions(f,g):

returnlambdax:f(g(x))print(combineFunctions(square,inc)(4))#>>25闭包闭包：带自由变量的函数deffunc(x):defg(y):

nonlocalx#有了此行，才能在g中对x赋值

x+=1returnx+yreturngf=func(10) #f是一个闭包，其自由变量x初值是10print(f(4)) #>>15print(f(5)) #>>17g=func(20) #g是一个闭包，其自由变量x初值是20print(g(4)) #>>25print(g(5)) #>>27函数参数的默认值函数允许有些参数有默认值，即调用的时候如果不给出这些参数，这些参数的值就自动取默认值。deff(a,b=1,op=lambdax,y:x+y):print(a,b,op(a,b))f(0) #>>011f(1,100) #>>1100101f(2,20,lambdax,y:x*y) #>>22040生成器(generator)yield关键字用来定义生成器（Generator），可以当return使用，从函数里返回一个值使用了yield的函数被称为生成器函数。当函数被调用的时候，并不执行函数，而是返回一个生成器(generator)如果X是一个生成器函数被调用时的返回值（生成器)，则foriinX:print(i)

会依次打印X中yield语句返回的结果，直到函数X再也不会执行到yield语句70生成器deftest_yield():#调用则返回迭代器yield1yield2yield(1,2)forxintest_yield(): print(x)输出:12(1,2)71生成器使用yield实现斐波那契数列：deffib(n):#生成器函数–用于求斐波那契数列前n项

a,b,counter=0,1,0whilecounter<=n:yieldaa,b=b,a+bcounter+=1forxinfib(10): print(x,end=",")720

1

1

2

3

5

8

13

21

34

55

生成器的一个优点就是它不要求事先准备好整个迭代过程中所有的元素。生成器仅仅在迭代至某个元素时才计算该元素，而在这之前或之后，元素可以不存在或者被销毁。这个特点使得它特别适合用于遍历一些巨大的或是无限的集合，比如几个G的文件，或是斐波那契数列等等。这个特点被称为延迟计算或惰性求值(Lazyevaluation)。Python中的类信息科学技术学院内蒙古浑善达克沙地类的定义class类名: def__init__(self,参数1,参数2......):#构造函数 self.属性1=参数1 self.属性2=参数2 ...... def成员函数1(self,参数1,参数2......): ...... def成员函数2(self,参数1,参数2......): ...... ...... def成员函数n(self,参数1,参数2......): .....

类和对象的概念类概括了一种事物的特点，包括属性和方法(成员函数）对象是通过类定义的变量，一个对象就是一个类的实例Python中所有的变量，以及小数、复数、字符串、元组、列表、集合、字典等组合数据类型的常量，都是对象，函数也是对象整型变量所属的类是int，小数所属于的类是float,字符串所属于的类是str，列表所属的类是list....类和对象示例classrectangle:def__init__(self,w,h):self.w,self.h=w,hdefarea(self):returnself.w*self.hdefperimeter(self):return2*(self.w+self.h)defmain():w,h=map(int,input().split())#假设输入23rect=rectangle(w,h)#rect是对象用构造函数初始化print(rect.area(),rect.perimeter())#>>610rect.w,rect.h=10,20print(rect.area(),rect.perimeter())#>>20060rect2=rectangle(2,3)print(rect2.area(),rect2.perimeter())

#>>610main()对象的比较默认情况下，自定义类的对象a和b，只能用==比较，且a==b等价于aisb所有类都有__eq__方法。x==y等价于x.__eq__(y)，若x.__eq__(y)无定义，则等价于y.__eq__(x) print(24.5.__eq__(24.5))#>>True默认情况下，自定义类的__lt__、__gt__、__le__、__ge__方法都被设置成了None，通过重写__eq__和这些成员函数，可以让==含义变化，以及对象可以用<,>,<=,>=进行比较对象的比较classpoint:def__init__(self,x,y=0):self.x,self.y=x,ydef__eq__(self,other):returnself.x==other.xandself.y==other.ydef__lt__(self,other): #使得两个point对象可以用<进行比较

ifself.x==other.x:returnself.y<other.yelse:returnself.x<other.xa,b=point(1,2),point(1,2)print(a==b) #>>Trueprint(a!=b) #>>Falseprint(a<point(0,1)) #>>Falseprint(a<point(1,3)) #>>True对象的比较lst=[a,point(-2,3),point(7,8),point(5,9),point(5,0)]lst.sort()forpinlst:#>>-23,12,50,59,78,print(p.x,p.y,end=",")对象的比较改写__eq__使得对象不可比较classA:def__init__(self,x):self.x=xA.__eq__=None a,b=A(3),A(4)print(a==b) #runtimeerror对象的拷贝要在对象间进行复制，编写一个copy函数比较方便classpoint:def__init__(self,x,y):self.x,self.y=x,ydefcopy(self):returnpoint(self.x,self.y)a=point(3,4)b=a.copy()继承和派生Python所有类,包括自定义类，均派生自object类，因而自动继承object类的方法classA:deffunc(x):passprint(dir(A)) #列出类A的方法对象作为字典的键或集合的元素默认情况下，自定义类的对象，可以作为集合元素或字典的键，被作为集合元素或字典键的，是对象的id，因此意义不大classA:def__init__(self,x):self.x=xa,b=A(5),A(5)#两个A(5)不是同一个，因此a和b的id不同dt={a:20,A(5):30,b:40}#三个元素的键id不同，因此在不同槽里print(len(dt),dt[a],dt[b])#>>32040print(dt[A(5)])#runtimeerror对象作为字典的键或集合的元素集合和字典都是哈希表,可哈希的类的对象才可以作为集合的元素或者字典的键一个类，有__hash__方法，即为可哈希。自定义类的默认__hash__方法根据对象id算哈希值，哈希值是个整数__hash__函数返回值相同的两个对象a,b，若a==b成立，则只能保留一个(字典的键类似处理）；若不成立，可以都保留。如果为自定义类重写__eq__方法，则其__hash__方法会被Python自动变成None，其变成不可哈希。也可以同时重写__eq__和__hash__对象作为字典的键或集合的元素类的__hash__方法示例x=23.1print(x.__hash__(),23.1.__hash__())#>>230584300921372695230584300921372695x=23print((23).__hash__(),x.__hash__(),hash(23))#>>232323x=(1,2)print(x.__hash__(),(1,2).__hash__(),hash(x))#>>371308163193441065637130816319344106563713081631934410656x="ok"print(x.__hash__(),"ok".__hash__())#>>-423760875654480603-423760875654480603对象作为字典的键或集合的元素为自定义类重写__eq__和__hash__方法，可以做到用对象的值作为集合元素或字典的键classA:def__init__(self,x):self.x=xdef__eq__(self,other):ifisinstance(other,A):#判断other是不是类A的对象

returnself.x==other.xelifisinstance(other,int):#如果other是整数

returnself.x==otherelse:returnFalsedef__hash__(self):returnself.x对象作为字典的键或集合的元素a=A(3)print(3==a)#>>Trueb=A(3)d={A(5):10,A(3):20,a:30}print(len(d),d[a],d[b],d[3])#>>2303030迭代器如果一个类实现了__next__()方法和__iter__()方法，并且__iter__()方法返回对象自身，则该类的对象就称为“迭代器”(iterator)。迭代器对象通常用于存储一些元素，一般__next__()方法会用来返回对象中的下一个元素。迭代器Python的for循环其实是用while实现foriina:

语句组真实实现：it=iter(a)#等价于it=a.__iter__()whileTrue:try:i=next(it)#等价于i=it.__next__()

语句组

exceptStopIteration:breakiter,next都是Python库函数迭代器迭代器示例classMyRange: def__init__(self,n): self.idx=0 self.n=n def__iter__(self): returnself#返回对象自身

def__next__(self): ifself.idx<self.n: val=self.idx self.idx+=1 returnval else: raiseStopIteration()#引发异常迭代器迭代器示例foriinMyRange(5):#>>0,1,2,3,4,print(i,end=",")print([iforiinMyRange(5)])#>>[0,1,2,3,4]x=MyRange(4)foriinx:#>>0,1,2,3, print(i,end=",")foriinx:#>>无输出

print(i,end=",")#本句不会被执行类的一些特殊方法对对象x调用的方法等价的操作x.__len__()len(x)，一般用于求x的长度x.__str__()str(x),将x转换成字符串x.__contains__(y)yinx，用于判断y在不在x里面x.__getitem__(index)x[index]根据下标访问x的元素，下标未必是整数x.__setitem__(index,item)x[index]=item类的一些特殊方法classTaggedList:#元素带标签的列表 def__init__(self,data,tags): #要求data是个列表或元组，tags是个字符串列表或元组。tags须和data一样长

self._data=data[:]#成员变量以下划线打头则不易见 self._tags=tags[:] self._tagIdx={}#该字典用于根据标签检索对应的下标

foriinrange(len(tags)): self._tagIdx[tags[i]]=i#标签tags[i]对应下标i def__len__(self): returnlen(self._data) def__str__(self): result="" foriinrange(len(self._data)): result+=\ self._tags[i]+":"+str(self._data[i])+"," returnresult类的一些特殊方法 def__contains__(self,x): returnxinself._data def__getitem__(self,index): ifisinstance(index,int):#下标index是整数

returnself._data[index] elifisinstance(index,str):#下标index是字符串

returnself._data[self._tagIdx[index]] else:#下标index不是整数也不是字符串，则主动引发异常

raiseException("wrongkeytype") def__setitem__(self,index,item): ifisinstance(index,int): self._data[index]=item else: self._data[self._tagIdx[index]]=item类的一些特殊方法a=TaggedList([70,80,90,100],["语文","数学","英语","物理"])print(len(a),78ina,80ina)#>>4FalseTrueprint(str(a))#>>语文:70,数学:80,英语:90,物理:100,print(a[0],a['数学'])#>>7080标签也可以作为下标访问元素a[1]=a['物理']=85print(a)#>>语文:70,数学:85,英语:90,物理:85,郭炜信息科学技术学院数据结构与算法

(Python描述)课程信息教材数据结构与算法（Python语言实现）郭炜编著清华大学出版社另有Java语言实现，C/C++语言实现两本，均已经由清华大学出版社出版二分算法信息科学技术学院98二分查找信息科学技术学院甘肃张掖平山湖大峡谷二分查找A心里想一个1-1000之间的数，B来猜，可以问问题，A只能回答是或否。怎么猜才能问的问题次数最少？是1吗？是2吗？.......是999吗？平均要问500次大于500吗？大于750吗？大于625吗？......每次缩小猜测范围到上次的一半，只需要10次100写一个函数BinarySeach，在从小到大排序的列表a里查找元素p,如果找到，则返回元素下标，如果找不到，则返回None。要求复杂度O(log(n))defbinarySearch(a,p,key=lambdax:x):L,R=0,len(a)-1#查找区间的左右端点，区间含右端点

whileL<=R:#如果查找区间不为空就继续查找

mid=L+(R-L)//2#取查找区间正中元素的下标

ifkey(p)<key(a[mid]):R=mid-1#设置新的查找区间的右端点

elifkey(a[mid])<key(p):L=mid+1#设置新的查找区间的左端点

else:returnmidreturnNone复杂度O(log(n))101二分查找函数写一个函数BinarySeach，在从小到大排序的列表a里查找元素p,如果找到，则返回元素下标，如果找不到，则返回None。要求复杂度O(log(n))a=[9,12,27,33,33,41,80]#a有序print(binarySearch(a,33))#>>3print(binarySearch(a,57))#>>Nonea.sort(key=lambdax:x%10)#按个位数从小到大排序print(a)#>>[80,41,12,33,33,27,9]print(binarySearch(a,57,key=lambdax:x%10))#>>5102二分查找函数写一个函数lowerBound，在从小到大排序的列表a里查找比给定元素p小的，下标最大的元素。找到则返回其下标，找不到则返回NonedeflowerBound(a,p,key=lambdax:x):#复杂度O(log(n))，找小于p的最靠右元素的下标

L,R=0,len(a)-1result=NonewhileL<=R:mid=L+(R-L)//2ifkey(a[mid])<key(p):L=mid+1result=mid else:R=mid-1returnresult103二分查找函数写一个函数lowerBound，在从小到大排序的列表a里查找比给定元素p小的，下标最大的元素。找到则返回其下标，找不到则返回Nonea=[9,12,27,33,33,41,80]print(lowerBound(a,33))#>>2print(lowerBound(a,50))#>>5print(lowerBound(a,0))#>>Nonea.sort(key=lambdax:x%10)print(a)#>>[80,41,12,33,33,27,9]print(lowerBound(a,28,key=lambdax:x%10))#>>5print(lowerBound(a,13,key=lambdax:x%10))#>>2104二分查找函数查找区间起点L,终点R，循环不可写成：whileL<R: ......应该是whileL<=R:设置查找区间新端点时，新端点一定要比原区间中点大或者小，不要等于原中点。105二分查找注意事项信息科学技术学院祁连山风光例题

Aggressivecows

Aggressivecows

107农夫John建造了一座很长的畜栏，它包括N(2≤N≤100,000)个隔间，这些小隔间的位置为x0,...,xN-1(0≤xi≤1,000,000,000,均为整数,各不相同).John的C(2≤C≤N)头牛每头分到一个隔间。牛都希望互相离得远点省得互相打扰。怎样才能使最近的两头牛之间的距离尽可能的大，这个最大距离是多少呢？Aggressivecows108解法1：先得到排序后的隔间坐标x0,...,xN-1从1,000,000,000/(C-1)到1依次尝试这个“最大的最近距离”D，找到的第一个可行的就是答案。尝试D是否可行的方法：1)第1头牛放在x02)若第k头牛放在xi，则找到xi+1到xN-1中第一个坐标位于[xi+D,XN-1]中的Xj

,第k+1头牛放在Xj。找不到这样的Xj,则D不可行若所有牛都能放下，则D即答案

Aggressivecows

109解法1：先得到排序后的隔间坐标x0,...,xN-1从1,000,000,000/(C-1)到1依次尝试这个“最大的最近距离”D，找到的第一个可行的就是答案。尝试D是否可行的方法：1)第1头牛放在x02)若第k头牛放在xi，则找到xi+1到xN-1中第一个坐标位于[xi+D,XN-1]中的Xj

,第k+1头牛放在Xj。找不到这样的Xj,则D不可行若所有牛都能放下，则D即答案复杂度1,000,000,000/(C-1)*N，即1,000,000,000,超时!

Aggressivecows

110解法2：先得到排序后的隔间坐标x0,...,xN-1在[L,R]内用二分法尝试“最大最近距离”D=(L+R)/2(L,R初值为[1,1,000,000,000/(C-1)]若D可行，则记住该D，然后在新[L,R]中继续尝试(新L=D+1)若D不可行，则在新[L,R]中继续尝试(新R=D-1)复杂度log(1,000,000,000/(C-1))*NN,C=map(int,input().split())x=[]#隔间的坐标序列foriinrange(N): x.append(int(input()))x.sort()defvalid(d):#判断最大最近距离d是否可行

prevPos=x[0]#上一头牛的位置

totalDone=1#已经安排好的牛的数目

foriinrange(1,N): ifx[i]-prevPos>=d: prevPos=x[i]#将下一头牛放在x[i] totalDone+=1 iftotalDone==C: returnTrue returnFalse

解题程序

L,R=1,1000000000//(C-1)+1best=0whileL<=R: D=L+(R-L)//2 ifvalid(D): best=D L=D+1 else: R=D-1print(best)

解题程序

二分法寻找最优答案的核心思想113如果一个假设的答案成立，那就跳着试一个更优的假设答案看行不行；如果一个假设的答案不成立,那就跳着试一个更差的假设答案看行不行。必须每次验证假设答案，都可以把假设答案所在的区间缩小为上次的一半。前提：单调性。一个假设答案不成立，则比它更优的假设答案肯定都不成立。郭炜信息科学技术学院数据结构与算法

(Python描述)课程信息教材数据结构与算法（Python语言实现）郭炜编著清华大学出版社另有Java语言实现，C/C++语言实现两本，均已经由清华大学出版社出版线性表116线性表线性表是一个元素构成的序列该序列有唯一的头元素和尾元素，除了头元素外，每个元素都有唯一的前驱元素，除了尾元素外，每个元素都有唯一的后继元素线性表中的元素属于相同的数据类型，即每个元素所占的空间必须相同。依据存储方式不同分为顺序表和链表两种顺序表信息科学技术学院河北草原天路顺序表即Python的列表，以及其它语言中的数组元素在内存中连续存放每个元素都有唯一序号(下标），且根据序号访问（包括读取和修改）元素的时间复杂度是O(1)的---随机访问下标为i的元素前驱下标为i-1，后继下标为i+1序号操作含义时间复杂度1init(n)生成一个n个元素的顺序表，元素值随机O(1)2init(a0,a1,....an)生成元素为a0,a1,....an的顺序表O(n)3length()求表中元素个数O(1)4append(x)在表的尾部添加一个元素xO(1)5pop()删除表尾元素O(1)6get(i)返回下标为i的元素O(1)7set(i,x)将下标为i的元素设置为xO(1)8find(x)查找元素x在表中的位置O(n)9insert(i,x)在下标i处插入元素xO(n)10remove(i)删除下标为i的元素O(n)顺序表支持的操作顺序表的append的O(1)复杂度的实现总是分配多于实际元素个数的空间(容量大于元素个数）元素个数小于容量时，append操作复杂度O(1)元素个数等于容量时，append导致重新分配空间，且要拷贝原有元素到新空间，复杂度O(n)顺序表的append的O(1)复杂度的实现重新分配空间时，新容量为旧容量的k倍(k>1且固定)，可确保append操作的平均复杂度是O(1)。Python的list取k=1.2左右

链表概述信息科学技术学院宁夏中卫沙坡头链表元素在内存中并非连续存放，元素之间通过指针链接每个结点除了元素，还有next指针，指向后继不支持随机访问。访问第i个元素，复杂度为O(n)已经找到插入或删除位置的情况下，插入和删除元素的复杂度O(1),且不需要复制或移动结点有多种形式：

单链表

循环单链表

双向链表

循环双向链表单链表信息科学技术学院张掖冰沟丹霞单链表classLinkList: classNode:#表结点 def__init__(self,data,next=None): self.data,self.next=data,next def__init__(self): self.head=self.tail=None self.size=0单链表 defprintList(self):#打印全部结点 ptr=self.head whileptrisnotNone: print(ptr.data,end=",") ptr=ptr.next单链表插入元素 definsert(self,p,data):#在结点p后面插入元素

nd=LinkList.Node(data,None) ifself.tailisp:#新增的结点是新表尾

self.tail=nd nd.next=p.next p.next=nd self.size+=1单链表插入元素(1)执行nd=Node(data,None)新建结点nd单链表插入元素(2)执行nd.next=p.next单链表插入元素(3)执行p.next=nd，完成插入单链表删除元素删除p后面的元素(1)初始状态，将要删除'a'结点单链表删除元素删除p后面的元素(2)执行p.next=p.next.next，完成删除单链表删除元素 defdelete(self,p):#删除p后面的结点

ifself.tailisp.next: self.tail=p p.next=p.next.next self.size-=1

#结点空间会被Python自动回收判断变量是否为None，应写pisNone,pisnotNone最好不要写p==None,p!=None单链表 defpopFront(self):#删除前端元素 ifself.headisNone: raise\ Exception("PoppingfrontforEmptylinklist.") else: self.head=self.head.next self.size-=1 ifself.size==0: self.head=self.tail=None defpushBack(self,data):#在尾部添加元素 ifself.size==0: self.pushFront(data) else: self.insert(self.tail,data)单链表 defpushFront(self,data):#在链表前端插入一个元素data nd=LinkList.Node(data,self.head) self.head=nd self.size+=1 ifself.tailisNone: self.tail=nd单链表 defclear(self): self.head=self.tail=None self.size=0 def__iter__(self): self.ptr=self.head returnself def__next__(self): ifself.ptrisNone: raiseStopIteration()#引发异常

else: data=self.ptr.data self.ptr=self.ptr.next returndata单链表linkLst=LinkList()linkLst.pushFront(0)linkLst.pushFront(1)foriinrange(2,5): linkLst.pushBack(i)forxinlinkLst: #>>1,0,2,3,4, print(x,end=",")上述实现方式没有实现“隐藏”，不是很好的实现方式带头结点的单链表带头结点的空单链表为避免链表为空是做特殊处理，可以为链表增加一个空闲头结点带头结点的非空单链表带头结点的单链表构造函数：classLinkList: def__init__(self): self.head=self.tail=LinkList.Node(None,None) self.size=0为避免链表为空是做特殊处理，可以为链表增加一个空闲头结点循环单链表'a'1813tailsizetailsize空表tail.next即头结点循环单链表在表首或表尾添加元素，以及删除表首元素，复杂度都是O(1)的。双向链表信息科学技术学院张掖平山湖大峡谷双向链表(双链表）每个结点有next指针指向后继，有prev指针指向前驱带头结点的双向链表classDoubleLinkList: class_Node: def__init__(self,data,prev=None,next=None): self.data,self.prev,self.next=data,prev,next双向链表插入结点在结点p后面插入新结点nd(1)执行nd=Node(data,None,None)新建结点nd双向链表插入结点在结点p后面插入新结点nd(2)执行nd.prev,nd.next=p,p.next双向链表插入结点在结点p后面插入新结点nd

(3)执行p.next.prev=nd双向链表插入结点在结点p后面插入新结点nd

(4)执行p.next=nd，插入完成双向链表删除结点删除结点p(1)初始状态，将要删除'a'结点双向链表删除结点删除结点p(2)执行p.prev.next=p.next双向链表删除结点删除结点p(3)执行p.nex.prev=p.prev,完成删除双向链表实现classDoubleLinkList: class_Node: def__init__(self,data,prev=None,next=None): self.data,self.prev,self.next=data,prev,next class_Iterator: def__init__(self,p): self.ptr=p defgetData(self): returnself.ptr.data defsetData(self,data): self.ptr.data=data def__next__(self): self.ptr=self.ptr.next ifself.ptrisNone: returnNone else: returnDoubleLinkList._Iterator(self.ptr)双向链表实现 defprev(self): self.ptr=self.ptr.prev returnDoubleLinkList._Iterator(self.ptr) def__init__(self): self._head=self._tail=\ DoubleLinkList._Node(None,None,None) self._size=0 def_insert(self,p,data): nd=DoubleLinkList._Node(data,p,p.next) ifself._tailisp:#新增的结点是新表尾

self._tail=nd ifp.next: p.next.prev=nd p.next=nd self._size+=1双向链表实现 def_delete(self,p):#删除结点p ifself._size==0orpisself._head: raiseException("Illegaldeleting.") else: p.prev.next=p.next ifp.next:#如果p有后继

p.next.prev=p.prev ifself._tailisp: self._tail=p.prev self._size-=1 defclear(self): self._tail=self._head self._head.next=self._head.prev=None self.size=0 defbegin(self): returnDoubleLinkList._Iterator(self._head.next) defend(self): returnNone双向链表实现 definsert(self,i,data):#在迭代器i指向的结点后面插入元素

self._insert(i.ptr,data) defdelete(self,i):#删除迭代器i指向的结点

self._delete(i.ptr) defpushFront(self,data):#在链表前端插入一个元素

self._insert(self._head,data) defpopFront(self): self._delete(self._head.next) defpushBack(self,data): self._insert(self._tail,data) defpopBack(self): self._delete(self._tail) def__iter__(self):