郭煒信息科學(xué)技術(shù)學(xué)院1

微博：/guoweiofpku

學(xué)會(huì)程序和算法，走遍天下都不怕!實(shí)用Python程序設(shè)計(jì)Python組合數(shù)據(jù)類型(二)

字典和集合

信息科學(xué)技術(shù)學(xué)院2信息科學(xué)技術(shù)學(xué)院郭煒

字典的基本概念泰國(guó)普吉島字典字典的每個(gè)元素是由“鍵：值”兩部分組成，可以根據(jù)“鍵”進(jìn)行快速查找格式：d={key1:value1,key2:value2......}字典元素的值是可賦值的，因此也是指針?biāo)性氐逆I都不相同鍵必須是不可變的數(shù)據(jù)類型，比如字符串、整數(shù)、小數(shù)、元組。一個(gè)元組如果包含可變數(shù)據(jù)類型，也不能作為字典的鍵列表、集合、字典等可變的數(shù)據(jù)類型，不可作為字典元素的鍵。4字典dt={'Jack':18,'Mike':19,128:37,(1,2):[4,5]}print(dt['Jack']) #>>18 鍵為'Jack'的元素值是18print(dt[128]) #>>37鍵為128的元素值是37print(dt[(1,2)])#>>[4,5]print(dt['c']) #不存在鍵為'c'的元素，產(chǎn)生異常，導(dǎo)致運(yùn)行時(shí)錯(cuò)誤dt['Mike']='ok'#將鍵為'Mike'的元素的值改為'ok'5字典dt['School']="Pku"

#添加鍵為'School'的元素，其值為'Pku'print(dt)#>>{128:37,(1,2):[4,5],'Jack':18,'Mike':'ok','School’:'Pku'}del

dt['Mike'] #刪除鍵為'Mike'的元素print(dt)#>>{128:37,(1,2):[4,5],'Jack':18,'School':'Pku'}scope={} #空字典scope['a']=3 #添加元素'a':3scope['b']=4 #添加元素'b':46字典print(scope) #>>{'a':3,'b':4}print('b'inscope)#>>True 判斷是否有元素鍵為'b'scope['k']=scope.get('k',0)+1#get(key,v):如果鍵key存在，則返回鍵為key的元素的值，否則返回vprint(scope['k']) #>>1scope['k']=scope.get('k',0)+1print(scope['k']) #>>27字典的鍵不可重復(fù)字典的鍵不可重復(fù)，指的是字典的鍵的內(nèi)容不能一樣a=(1,2,3)b=(1,2,3) d={a:60,b:70,(1,2,3):80,(1,2,3):50}#d中實(shí)際上只有一個(gè)元素print(d[a]) #>>50print(d[b]) #>>50print(d[(1,2,3)]) #>>50forxind.keys():

print(x) #此循環(huán)只輸出一個(gè)(1,2,3)8下面哪條語(yǔ)句是不正確的dt={'jack':[1,2],100:(4,6)}{'jack':20,18:30}[18]=31{'jack':20,18:30}[100]=31dt={[1,2]:3,'jack':4}ABCD提交單選題1分字典的構(gòu)造10items=[('name','Gumby'),('age',42)]

d=dict(items)

print(d)

#>>{'name':'Gumby','age':42}

d=dict(name='Gumby',age=42,height=1.76)

print(d)

#>>{'height':1.76,'name':'Gumby','age':42}信息科學(xué)技術(shù)學(xué)院郭煒

字典相關(guān)函數(shù)冰島索爾黑馬冰川字典的函數(shù)clear() 清空字典keys() 取字典的鍵的序列items() 取字典的元素的序列，可用于遍歷字典values() 取字典的值序列pop(x) 刪除鍵為x的元素，如果不存在，產(chǎn)生異常

上述"序列"，不是

list,tuple或setcopy() 淺拷貝get(k,v) 如果有元素鍵為k，則返回該元素的值，如果沒有，則返回v12字典的函數(shù)d={'name':'Gumby','age':42,'GPA':3.5}if'age'ind.keys():print(d['age']) #>>42forxind.items():

#>>('GPA',3.5),('age',42),('name','Gumby'),print(x,end=",")forxind.items():#>>GPA,age,name,print(x[0],end=",")forxind.items():#>>3.5,42,Gumby,print(x[1],end=",")fork,vind.items():#>>GPA3.5,age42,nameGumby,print(k,v,end=",")forxind.keys():#>>GPA,age,name,print(x,end=",")13字典的函數(shù)forxind.values():#>>3.5,42,Gumby,print(x,end=",")x={'username':'admin',1978:[1,2,3]}y=x.copy()y['username']='mlh'y[1978].remove(2) #刪除元素2print(y)#>>{'username':'mlh',1978:[1,3]}print(x)#>>{'username':'admin',1978:[1,3]}x.pop('username') #刪除鍵為'username'的元素print(x) #>>{1978:[1,3]}d.clear()print(d)#>>{}14字典的深拷貝importcopyx={'username':'admin','machines':['foo','bar','baz']}y=copy.deepcopy(x)y['username']='mlh'y['machines'].remove('bar')print(y)print(x)=>{'username':'mlh','machines':['foo','baz']}{'username':'admin','machines':['foo','bar','baz']}15遍歷字典itemsx={'username':'admin','machines':['foo','bar','baz'],'Age':15}foriinx.items():print(i[0])print(i[1])遍歷字典時(shí)，在python3.5及以前，順序不確定。在python3.6及以后，順序同元素加入字典的順序16信息科學(xué)技術(shù)學(xué)院郭煒

字典例題冰島黃金瀑布字典例題：統(tǒng)計(jì)單詞頻率輸入若干行，每行一個(gè)單詞。輸出按單詞出現(xiàn)次數(shù)從高到低打出所有單詞。次數(shù)相同的，按照字典序從小到大排18輸入樣例aboutsendaboutme輸出樣例2about1me1senddt={}whileTrue:try:wd=input()ifwdindt:#如果有元素鍵為wddt[wd]+=1else:dt[wd]=1#加入鍵為wd的元素，其值是1except:break#輸入結(jié)束后的input()引發(fā)異常，跳到這里，再跳出循環(huán)result=[]forxindt.items():result.append(x)#x是個(gè)元組，x[0]是單詞，x[1]是出現(xiàn)次數(shù)result.sort(key=lambdax:(-x[1],x[0]))forxinresult:print(x[1],x[0])19字典例題：統(tǒng)計(jì)單詞頻率ifwdindt:dt[wd]+=1else:dt[wd]=1也可改寫為：dt[wd]=dt.get(wd,0)+1#若在dt里有鍵為wd的元素，則get返回其值，否則返回020信息科學(xué)技術(shù)學(xué)院郭煒集合本溪洋湖溝集合(set)的概念和特點(diǎn)集合(set)的概念同數(shù)學(xué)上的集合:

元素類型可以不同。不會(huì)有重復(fù)元素?？梢栽鰟h元素。整數(shù)、小數(shù)、復(fù)數(shù)、字符串、元組都可以作為集合的元素。但是列表、字典和集合等可變的數(shù)據(jù)類型不可作為集合的元素。一個(gè)元組如果包含可變數(shù)據(jù)類型，也不能作為集合的元素集合的作用是快速判斷某個(gè)東西是否在一堆東西里面(用in)。22集合的構(gòu)造a

=set() #空集合print(a) #>>set()a={1,2,2,"ok",(1,3)}#自動(dòng)去重print(a) #>>{2,1,'ok',(1,3)}b=(3,4)c=(3,4)a=set((1,2,"ok",2,b,c))forxina:#>>ok12(3,4)print(x,end="")a=set("abc") #>>字符串轉(zhuǎn)集合print(a) #>>{'b','c','a'}a=set({1:2,'ok':3,(3,4):4})print(a)#>>{1,'ok',(3,4)}只取鍵print(a[2]) #錯(cuò)誤，集合元素沒有順序，不能用下標(biāo)訪問23集合常用函數(shù)add(x) 添加元素x。如果x已經(jīng)存在，則不添加clear() 清空集合copy() 返回自身的淺拷貝remove(x) 刪除元素x。如果不存在元素x，則引發(fā)異常update(x) 將序列x中的元素加入到集合24集合運(yùn)算a,b是集合：xina x是否在集合a中a|b 求a和b的并a&b 求a和b的交a–b 求a和b的差，即在a中而不在b中的元素a^b 求a和b的對(duì)稱差，等價(jià)于(a|b)–(a&b)25集合運(yùn)算a,b是集合：a==b a是否元素和b一樣a!=b a是否元素和b不一樣a<=b a是否是b的子集(a有的元素，b都有)a<b a是否是b的真子集(a有的元素，b都有，且b還包含a中沒有的元素)a>=b b是否是a的子集a>b b是否是a的真子集26集合示例程序a=set([]) #a是空集合b=set([])a.add(1) #添加元素1a.update([2,3,4]) #將列表元素添加進(jìn)ab.update(['ok',2,3,100])print(a) #>>{1,2,3,4}print(b) #>>{2,3,100,'ok'}print(a|b) #>>{1,2,3,4,100,'ok'}求并print(a&b) #>>{2,3}求交print(a-b) #>>{1,4}求差a-=b #在a中刪除b中有的元素print(a) #>>{1,4}27集合示例程序a^={3,4,544} #對(duì)稱差

print(a) #>>{544,1,3}a.update("take")print(a) #>>{544,1,3,'e','k','t','a'}print(544ina) #>>Truea.remove(544) #刪除元素，若元素不存在，會(huì)出錯(cuò)print(a) #>>{1,3,'a','k','t','e'}a={1,2,3}b={2,3}print(a>b) #>>Trueb是a的真子集print(a>=b) #>>Trueb是a的子集print(b<a) #>>Trueb是a的真子集28集合例題輸入一些單詞，統(tǒng)計(jì)不重復(fù)的單詞一共有多少個(gè)。輸入樣例:abouttakeaboutzootake輸出樣例：329集合例題words=set([])whileTrue:try:wd=input()ifnotwdinwords:words.add(wd)except:breakprint(len(words))用列表做，比用集合慢很多很多！單詞達(dá)到10萬(wàn)，就會(huì)非常明顯。30信息科學(xué)技術(shù)學(xué)院郭煒

自定義數(shù)據(jù)類型冰島雷克雅未克需求用元組或列表表示某種事物，不夠方便student=["張三",20001807,3.4,"1988-01-24"]不容易記得student[i]到底對(duì)應(yīng)哪個(gè)屬性用“類”來表示一種事物class類名:

def

__init__(self,參數(shù)1,參數(shù)2......):

self.屬性1=參數(shù)1

self.屬性2=參數(shù)2 ......類的用法classStudent: #定義Student類

def__init__(self,n,i,g,b):#一定要有self=n#添加了名為name的屬性

self.id=i

#添加了名為id的屬性

self.gpa=g

self.birthDate=bstudent1=Student("Jack",1877,3.4,"1988-01-02")#生成student1對(duì)象print(,student1.id,student1.gpa,student1.birthDate)#>>Jack18773.41988-01-02="BigJack" #修改對(duì)象屬性print()

#>>BigJackstudent2=Student("BigJack",1877,3.4,"1988-01-02")print(student1==student2) #>>False等價(jià)于student1isstudent2#要比較兩個(gè)對(duì)象內(nèi)容是否相等，需要自己寫個(gè)函數(shù)逐個(gè)比較兩者每個(gè)屬性!!!類的用法students=[student1,Student("Mary",1876,3.4,"1988-12-02"),Student("Tom",1782,3.8,"1988-11-02"),Student("Jane",1762,3.1,"1989-04-02")]students.sort(key=lambdax:(-x.gpa,x.id))forxinstudents:print(,x.id,x.gpa,x.birthDate)students.sort()#runtimeerror,因?qū)ο蟛荒鼙容^大小排序后的輸出:Tom17823.81988-11-02Mary18763.41988-12-02BigJack18773.41988-01-02Jane17623.11989-04-02對(duì)象的拷貝要在對(duì)象間進(jìn)行復(fù)制，編寫一個(gè)copy函數(shù)比較方便classpoint:

def__init__(self,x,y):

self.x,self.y=x,y

def

copy(self):returnpoint(self.x,self.y)a=point(3,4)b=a.copy()程序或算法的

時(shí)間復(fù)雜度信息科學(xué)技術(shù)學(xué)院美國(guó)加州1號(hào)公路程序或算法的時(shí)間復(fù)雜度一個(gè)程序或算法的時(shí)間效率，也稱“時(shí)間復(fù)雜度”，有時(shí)簡(jiǎn)稱“復(fù)雜度”38程序或算法的時(shí)間復(fù)雜度一個(gè)程序或算法的時(shí)間效率，也稱“時(shí)間復(fù)雜度”，有時(shí)簡(jiǎn)稱“復(fù)雜度”復(fù)雜度常用大的字母O和小寫字母n來表示，比如O(n),O(n2)等。n代表問題的規(guī)模39程序或算法的時(shí)間復(fù)雜度一個(gè)程序或算法的時(shí)間效率，也稱“時(shí)間復(fù)雜度”，有時(shí)簡(jiǎn)稱“復(fù)雜度”復(fù)雜度常用大的字母O和小寫字母n來表示，比如O(n),O(n2)等。n代表問題的規(guī)模。O(X）就表示解決問題的時(shí)間和X成正比關(guān)系時(shí)間復(fù)雜度是用算法運(yùn)行過程中，某種時(shí)間固定的操作需要被執(zhí)行的次數(shù)和n的關(guān)系來度量的。在無序數(shù)列中查找某個(gè)數(shù)，復(fù)雜度是O(n)40程序或算法的時(shí)間復(fù)雜度一個(gè)程序或算法的時(shí)間效率，也稱“時(shí)間復(fù)雜度”，有時(shí)簡(jiǎn)稱“復(fù)雜度”復(fù)雜度常用大的字母O和小寫字母n來表示，比如O(n),O(n2)等。n代表問題的規(guī)模，O(X）就表示解決問題的時(shí)間和X成正比關(guān)系時(shí)間復(fù)雜度是用算法運(yùn)行過程中，某種時(shí)間固定的操作需要被執(zhí)行的次數(shù)和n的關(guān)系來度量的。在無序數(shù)列中查找某個(gè)數(shù)，復(fù)雜度是O(n)計(jì)算復(fù)雜度的時(shí)候，只統(tǒng)計(jì)執(zhí)行次數(shù)最多的(n足夠大時(shí))那種固定操作的次數(shù)。比如某個(gè)算法需要執(zhí)行加法n2次，除法10000n次，那么就記其復(fù)雜度是O(n2)的。41程序或算法的時(shí)間復(fù)雜度如果復(fù)雜度是多個(gè)n的函數(shù)之和，則只關(guān)心隨n的增長(zhǎng)增長(zhǎng)得最快的那個(gè)函數(shù) O(n3+n2)=>O(n3) O(2n+n3)=>O(2n) O(n!+3n)=>O(n!)42程序或算法的時(shí)間復(fù)雜度如果復(fù)雜度是多個(gè)n的函數(shù)之和，則只關(guān)心隨n的增長(zhǎng)增長(zhǎng)得最快的那個(gè)函數(shù) O(n3+n2)=>O(n3) O(2n+n3)=>O(2n) O(n!+3n)=>O(n!)常數(shù)復(fù)雜度：O(1)時(shí)間(操作次數(shù))和問題的規(guī)模無關(guān)對(duì)數(shù)復(fù)雜度：O(log(n))線性復(fù)雜度：O(n)多項(xiàng)式復(fù)雜度：O(nk)指數(shù)復(fù)雜度：O(an)階乘復(fù)雜度：O(n!)43程序或算法的時(shí)間復(fù)雜度列表（數(shù)組）根據(jù)下標(biāo)訪問元素 O(1)在排好序的數(shù)組中求最大值（最小值) O(1)在無序數(shù)列中查找某個(gè)數(shù)(順序查找)

O(n)插入排序、選擇排序等笨排序方法 O(n2)歸并排序和快速排序O(n*log(n))二分查找O(log(n))44冒泡排序45defbubbleSort(a,key=lambdax:x): n=len(a) foriinrange(1,n):#無序部分終點(diǎn)下標(biāo)是n-i forjinrange(n-i):#此循環(huán)做一輪排序

ifkey(a[j+1])<key(a[j]): a[j+1],a[j]=a[j],a[j+1]對(duì)列表[7,12,5,9,4,8]進(jìn)行冒泡排序的過程如下。每做一輪排序，有序部分就多一個(gè)元素：初始狀態(tài)： [7,12,5,9,4,8]第1輪后： [7,5,9,4,8,12]第2輪后： [5,7,4,8,9,12]第3輪后： [5,4,7,8,9,12]第4輪后： [4,5,7,8,9,12]第5輪后： [4,5,7,8,9,12]in用于列表和用于字典、集合的區(qū)別ainb若b是列表，字符串或元組，則該操作時(shí)間復(fù)雜度O(n)，即時(shí)間和b的元素個(gè)數(shù)成正比若b是字典或集合，則該操作時(shí)間復(fù)雜度O(1)，即時(shí)間基本就是常數(shù)，和b