《算法设计与分析基础》（Python语言描述） 课件 第2章常用的数据结构及其应用2

第2章工之利器—常用的数据结构及其应用2.1线性表—数组2.3字符串2.2线性表—链表2.4栈2.5队列2.6双端队列2.7优先队列2.8树和二叉树2.9图2.10并查集2.12哈希表2.11二叉排序树和平衡二叉树CONTENTS提纲1/572.9.1图基础1.图的定义2.9图G=(V，E)143012232(a)一个带权有向图G1(b)一个带权无向图G23385431210143521(c)一个不带权无向图G3012342/572.图的存储结构1）邻接矩阵1430122323/572）边数组n=4edges=[[0，1，2]，[0，2，4]，[1，2，2]，[2，3，3]，[3，0，1]]1430122324/573）邻接表用二维数组adj作为图的邻接表，对于不带权图，adj[i]表示顶点i的所有出边。adj=[[1，2，3]，[0，2，4]，[0，1，3]，[0，2，4]，[1，3]]012345/57对于带权图，每一条边用“[v，w]”表示，如adj[i]中包含该元素时表示有一条顶点i到顶点v的权为w的边。adj=[ [[1,1],[2,5],[3,1]] [[0,1],[2,3],5,2]] [[0,5],[1,3],[3,3],[4,4],[5,3] [[0,1],[2,3],[4,8]] [[2,4],[3,8],[5,1]] [[1,2],[2,3],[4,1]] ]33854312101435216/573.图的遍历1）深度优先遍历DFS序列：0，1，2，3，4，533854312101435217/572）广度优先遍历BFS序列：0，1，2，3，5，433854312101435218/57一个有n个顶点的连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只包含构成一棵树的n-1条边。一个带权连通图中权值和最小的生成树称为最小生成树。Prim算法。Kruskal算法。4.生成树和最小生成树9/57对于带权图中两个顶点之间的路径可能有多条，把带权路径长度最短的那条路径称为最短路径，其路径长度称为最短路径长度或者最短距离。Dijkstra算法。Floyd算法。5.最短路径10/57在一个有向图G中找一个拓扑序列的过程称为拓扑排序。如果一个有向图拓扑排序产生包含全部顶点的拓扑序列，则该图中不存在环，否则该图中一定存在环。6.拓扑排序11/572.9.2实战—课程表（LeetCode207★★）问题描述：n门课程（编号为0到n-1）的选修关系用prerequisites数组表示，其中每个元素[b，a]表示课程a是课程b的先修课程即a→b。判断是否可能完成所有课程的学习。

例如，n=2，prerequisites=[[1，0]]，表示共有2门课程，课程1的先修课程是课程0，这是可能的，结果为true。

要求设计如下方法：

def

canFinish(self,numCourses,prerequisites)

->

bool:12/57每门课程用一个顶点表示，两门课程之间的先修关系用一条有向边表示，这样构成一个有向图，用邻接表存储。需要注意的是prerequisites中的元素[b，a]对应的有向边为<a，b>。采用拓扑排序思路，用整数n累计拓扑序列中的元素个数，拓扑排序完毕，若n=numCourses则说明没有环，能够完成所有课程的学习，返回True，否则说明存在环，不能完成所有课程的学习，返回False。解13/571 class

Solution:2

def

canFinish(self,numCourses,prerequisites)

->

bool:3

indegree=[0]*numCourses;

#入度数组4

adj=[[]

for

i

in

range(0,numCourses)]

#邻接表5

for

e

in

prerequisites:

6

b,a=e[0],e[1]

#[b,a]表示a是b的先修课程7

adj[a].append(b)8

indegree[b]+=1

#存在边<a,b>，b的入度增1b,…

a[b,a]ab14/579

st=deque()

#定义一个栈st10

for

i

in

range(0,numCourses):

#入度为0的顶点i进栈11

if

indegree[i]==0:st.append(i)12

n=0

#累计拓扑序列的顶点个数13

while

st:14

i=st.popleft()

#出栈顶点i15

n+=116

for

j

in

adj[i]:

#找到i的所有邻接点j17

indegree[j]-=1

#顶点j的入度减少118

if

indegree[j]==0:st.append(j)

#入度为0的顶点j进栈19

return

n==numCourses上述程序提交结果为通过，运行时间为44ms，消耗空间为15.9MB。15/571.并查集的定义给定n个结点的集合U，结点编号为1～n，再给定一个等价关系R（满足自反性、对称性和传递性的关系称为等价关系。像图中顶点之间的连通性、亲戚关系等都是等价关系），由等价关系产生所有结点的一个划分，每个结点属于一个等价类，所有等价类是不相交的。R2.10并查集2.10.1并查集基础16/57基本运算①Init()：初始化。②Find(x)：查找x（x∈U）结点所属的等价类。③Union(x，y)：将x和y（x∈U，y∈U）所属的两个等价类合并。17/572.并查集的实现Axy并查集的基本存储结构self.parent=[0]*self.MAXN

#并查集存储结构self.rnk=[0]*self.MAXN

#存储结点的秩(近似于高度)18/571 def

Init(self,n):

#并查集初始化2

for

i

in

range(0,n):3

self.parent[i]=i4

self.rnk[i]=0i19/571 def

Find(self,x):

#递归算法：并查集中查找x结点的根结点2

if

x!=self.parent[x]:3

self.parent[x]=self.Find(self.parent[x])

#路径压缩4

return

self.parent[x]ABxABx查找中路径压缩CC20/571 def

Find(self,x):

#非递归算法：并查集中查找x结点的根结点2

rx=x3

while

self.parent[rx]!=rx:

#找到x的根rx4

rx=self.parent[rx]5

y=x6

while

y!=rx:

#路径压缩7

tmp=self.parent[y]8

self.parent[y]=rx9

y=tmp10

return

rx

#返回根ABxABx查找中路径压缩21/571 def

Union(self,x,y):

#并查集中x和y的两个集合的合并2

rx,ry=self.Find(x),self.Find(y)3

if

rx==ry:return

#x和y属于同一棵树时返回4

if

self.rnk[rx]<self.rnk[ry]:5

self.parent[rx]=ry

#rx结点作为ry的孩子6

else:7

if

self.rnk[rx]==self.rnk[ry]:

#秩相同，合并后rx的秩增18

self.rnk[rx]+=19

self.parent[ry]=rx

#ry结点作为rx的孩子22/572.10.2实战—省份数量（LeetCode547★★）问题描述：有n个城市，其中一些彼此相连，另一些没有相连。如果城市a与城市b直接相连，且城市b与城市c直接相连，那么城市a与城市c间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个n×n的矩阵isConnected，其中isConnected[i][j]=1表示第i个城市和第j个城市直接相连，而isConnected[i][j]=0

表示二者不直接相连。求矩阵中省份的数量。

例如，isConnected={{1，1，0}，{1，1，0}，{0，0，1}}，结果为2。

要求设计如下方法：

def

findCircleNum(self,

isConnected)

->

int:23/57城市之间的相连关系（含直接相连和间接相连）是一种等价关系（满足自反性、对称性和传递性）。采用并查集求解，按相连关系划分产生若干子集树，每棵子集树对应一个省份。首先初始化并查集（这里n个城市的编号为0～n-1），由于isConnected是对称矩阵，遍历其上三角部分，对于直接相连的城市对（i，j），调用并查集的合并运算Union(i，j)将i和j所在的子集树合并。最后求并查集中子集树棵数（即满足parent[i]=i的子集树棵数）ans，最后返回ans。解24/571 class

UFS(): #并查集类2

MAXN=20053

def

__init__(self):

4

self.parent=[0]*self.MAXN

#并查集存储结构5

self.rnk=[-1]*self.MAXN;

#存储结点的秩(近似于高度)6

def

Init(self,n):

#并查集初始化7

for

i

in

range(0,n):8

self.parent[i]=i9

self.rnk[i]=025/5710

def

Find(self,x):

#递归算法：并查集中查找x结点的根结点11

if

x!=self.parent[x]:12

self.parent[x]=self.Find(self.parent[x])

#路径压缩13

return

self.parent[x]ABxACxCB26/5714

def

Union(self,x,y):

#并查集中x和y的两个集合的合并15

rx,ry=self.Find(x),self.Find(y)16

if

rx==ry:

#x和y属于同一棵树时返回17

return18

if

self.rnk[rx]<self.rnk[ry]:19

self.parent[rx]=ry

#rx结点作为ry的孩子rxxryyrxxryyry的秩不变27/5720

else:21

if

self.rnk[rx]==self.rnk[ry]:

#秩相同，rx的秩增122

self.rnk[rx]+=1ryyrxxryyrxxrx的秩增128/5723

self.parent[ry]=rx

#ry结点作为rx的孩子24ryyrxxryyrxxrx的秩不变29/5725 class

Solution:26

def

findCircleNum(self,

isConnected)

->

int:27

n=len(isConnected)28

ufs=UFS() #定义并查集类对象ufs29

ufs.Init(n)30

for

i

in

range(0,n):

#读取矩阵上三角部分31

for

j

in

range(i+1,n):32

if

isConnected[i][j]==1:ufs.Union(i,j)33

ans=034

for

i

in

range(0,n):35

if

ufs.parent[i]==i:ans+=136

return

ans上述程序提交结果为通过，运行时间为48ms，消耗空间为15.4MB。30/572.11.1二叉排序树1.二叉排序树的定义2.11二叉排序树和平衡二叉树538167中序序列：135678

递增有序31/572.二叉排序树的插入和生成3.二叉排序树的删除4.二叉排序树的查找538167查找632/572.11.2平衡二叉树通过一些平衡规则和调整操作让一棵二叉排序树既保持BST性质又保证高度较小，即接近O(log2n)的高度，称为平衡二叉树。平衡二叉树：AVL树和红黑树。AVL树的平衡规则是树中每个结点的左、右子树的高度至多相差1。33/57红黑树中每个结点有一个表示颜色的标志，增加外部结点（通常用NIL表示），同时满足以下性质：

（1）每个结点的颜色为红色或者黑色。

（2）根结点的颜色为黑色。

（3）所有外部结点的颜色为黑色。

（4）如果一个结点是红色，则它的所有孩子结点为黑色。

（5）对于每个结点，从该结点出发的所有路径上包含相同个数的黑色结点。这里的路径特指从一个结点到其子孙结点中某个外部结点的路径。尽管红黑树并不是完全平衡二叉树，但接近于平衡状态即近似于平衡二叉树，其高度接近O(log2n)。2.11.3红黑树34/572.11.4Python中的有序类目前Python中没有提供类似于C++中set和map（均采用红黑树实现）的数据结构，但有一个第三方拓展库sortedcontainers，它是用pure-python实现的，内有SortedList（有序列表）、SortedDict（有序字典）和SortedSet（有序集合）等，默认按关键字递增排列。SortedList用于存储一个含重复元素的有序序列，采用平衡树实现，查找性能较好。其使用方式与列表类似。35/57tset.add(val)：添加新元素并排序。tset.update(iterable)：对添加的可迭代的所有元素排序。tset.clear()：移除所有元素。tset.discard(val)：移除一个值元素，如果元素不存在时不报错。时间复杂度为O(log2n)。tset.remove(val)：移除一个值元素，如果元素不存在则报错。时间复杂度为O(log2n)。例如定义一个空的有序列表tset：tset=SortedList()36/57tset.pop(i=-1)：移除一个指定下标i的元素，如果有序序列为空或者下标超限会报错。时间复杂度为O(log2n)。tset.bisect_left(val)：查找第一个大于等于val的索引。时间复杂度为O(log2n)。tset.bisect_right(val)：查找第一个大于val的索引。时间复杂度为O(log2n)。count(val)：返回有序列表中值val出现的次数。tset.index(val,start=None,Stop=None)：查找索引范围[start，stop）范围内第一次出现val的索引，如果val不存在则报错。时间复杂度为O(log2n)。37/572.11.5实战—前k个高频词（LeetCode692★★）问题描述：给一非空的单词列表words，返回前k个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

例如，words={"i"，"love"，"leetcode"，"i"，"love"，"coding"}，k=2，则返回结果是{"i"，"love"}，"i"和"love"为出现次数最多的两个单词，均为2次，但按字母顺序"i"在"love"之前。

要求设计如下方法：def

topKFrequent(self,

words,

k)

->

List[str]:38/57先定义一个一个SortedDict对象cntmap，以单词为关键字，遍历words得到每个单词的计数。再定义一个SortedDict对象ansmap，以计数为关键字，其值为该计数的单词列表（按字母顺序排列）。ansmap默认按计数递增排序，ansmap.key()[-1]是计数最大的元素。定义一个存放结果的ans列表，取出ansmap中前k个单词添加到ans中，最后返回ans。解39/571 from

sortedcontainers

import

SortedDict #引入SortedDict类2 class

Solution:3

def

topKFrequent(self,

words,

k)

->

List[str]:4

cntmap=SortedDict()5

for

i

in

range(0,len(words)):

#单词计数存放在cntmap中6

if

words[i]

in

cntmap:cntmap[words[i]]+=17

else:cntmap[words[i]]=1words={"i"，"love"，"leetcode"，"i"，"love"，"coding"}，k=2cntmap：("coding",1)("i",2)("leetcode",1)("love",2)40/578

ansmap=SortedDict()9

for

s

in

cntmap.keys():10

cnt=cntmap[s]

#获取s对应的计数11

if

cnt

in

ansmap:

#ansmap中存在该计数12

ss=ansmap[cnt]13

ss.append(s)14

ansmap[cnt]=ss15

else:

#ansmap中不存在该计数16

ss=[]

17

ss.append(s)18

ansmap[cnt]=sscntmap：("coding",1)("i",2)("leetcode",1)("love",2)ansmap:(2,["i","love"])(1,["coding","leetcode"])41/5719

ans=[]20

i=-1

#在ansmap中从后向前查找21

while

k>0:

#取前k个字符串存放在ans中22

cnt=ansmap.keys()[i]23

ss=ansmap[cnt]24

for

x

in

ss:25

if

k>0:ans.append(x);k-=126

else:break27

i-=128

return

ansansmap:(2,["i","llove"])(1,["coding","leetcode"])ans={"i"，"love"}k=242/57上述程序提交结果为通过，运行时间为44ms，消耗空间为15.6MB。43/572.12.1哈希表基础2.12哈希表哈希表是一种使用哈希函数将关键字映射到存储地址的数据结构。哈希函数h存储地址=h(key)n个元素（对象）m（m≥n）的连续内存单元44/571）直接定址法h(k)=k+c2）除留余数法h(k)=kmodp

（mod为求余运算，p≤m）构造哈希函数的方法45/57开放定址法拉链法哈希冲突解决方法46/572.12.2Python中的哈希表1.Python中的哈希集合Python中提供了集合类型，采用哈希表实现，集合中存放不可变类型数据，如字符串、数字或元组。集合是一个无序的不重复元素序列，其基本功能包括关系测试和消除重复元素。使用大括号{}或者set()函数创建集合，而创建一个空集合必须用set()而不是{}，因为{}是用来创建一个空字典。47/57集合s的主要操作如下。①len(s)：返回集合s中的元素个数。②eins，enotins：分别判定元素e是否在或者不在集合s中。③s.add(e)：向集合s中添加元素e。④s.clear()：移除集合s中的所有元素。⑤s.issubs(t)：判断集合s是否为集合t的子集。⑥s.remove(e)：移除集合s的元素e，如果元素e不存在，则会发生错误。⑦s.discard(e)：移除集合s的元素e，如果元素e不存在，不会发生错误。⑧s.difference(t)，ersection(t)和s.union(t)：分别返回集合s和t的差集、交集和并集。48/571 hset=set() #定义一个哈希集合hset2 hset.add(3) #插入33 hset.add(1) #插入24 hset.add(2) #插入25 print(1inhset) #输出:True6 hset.remove(1) #删除17 forxinhset: #输出:238 print(x,end='')9 print()49/572.Python中的哈希映射Python中提供的字典类型相当于哈希映射，也是采用哈希表实现。字典可存储任意类型对象，每个元素由key:value构成，其中key是键，value是对应的值，中间用逗号分隔，整个字典包括在花括号({})中，键必须是唯一的，但值则不必唯一。使用大括号{}或者dict()函数创建字典。50/57字典dict的主要操作如下：①len(dict)：返回字典dict中的元素个数。②dict[key]：返回字典dict中键key的值。③keyindict,keynotindict：分别判定键key在或者不在字典dict中。④dict.items()：以列表返回字典dict中可遍历的（键键,值）元组数组。⑤dict.keys()：以列表返回字典dict中所有的键。⑥dict.values()：以列表返回字典dict中的所有值。⑦pop(key[,default])：删除字典dict中键key所对应的值，返回值为被删除的值。key值必须给出，否则返回default值。51/571 hmap=dict() #定义一个哈希字典hmap2 hmap["Mary"]=3 #插入("Mary