数据结构（Python版）课件 第4章 串和数组

可表示为：（a1,a2,……,an）第2章线性表第3章栈和队列（操作受限）第4章串（内容受限）和数组线性结构线性结构了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。明确数组这种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。01OPTION02OPTIONtarget目标目录导航4.14.24.34.44.54.64.74.8串的定义案例引入串数组案例分析与实现精选习题解析AI协作实战Python标准库中的数组与字符串Contents串的定义串(String)----零个或多个字符组成的有限序列。串名串值串长n空串n=0a=‘BEI’,b=‘JING’c=‘BEIJING’d=‘BEIJING’子串字符位置主串子串位置串相等空格串串的定义a、b、c、d的长度分别为3、4、7、8；a和b都是c和d的子串；a在c和d中的位置都是1；b在c中的位置都是4，在d中的位置是5。目录导航4.14.24.34.44.54.64.74.8串的定义案例引入串数组案例分析与实现精选习题解析AI协作实战Python标准库中的数组与字符串Contents研究人员不断从苹果、桑树等树种中检测到新的双生病毒案例引入--病毒感染检测参考文献：SunS,RenY,WangD,etal.AgroupIWRKYtranscriptionfactorregulatesmulberrymosaicdwarf‐associatedvirus‐triggeredcelldeathinNicotianabenthamiana[J].MolecularPlantPathology,2022,23(2):237-253.病毒DNA序列：单链环状树种DNA序列：为链状案例引入--病毒感染检测利用专业知识解决林草领域应用问题。培养农林信息化研究能力、创新精神、生态文明理念、绿色环保意识。研究者将病毒DNA和植物的DNA均表示成由字母组成的字符串序列。检测某种病毒DNA序列是否在植物的DNA序列中出现过。出现过，已感染未出现，未感染。案例引入--病毒感染检测baa感染bbbbaa感染aaabbb未感染babbbabaa案例引入--病毒感染检测

存在存在未存在bbbbaaaaabbbbabbba子串：baa主串1主串2主串3案例引入--病毒感染检测案例引入--模式匹配算法存在时，返回子串的位置。不存在，返回0。--检测一个主串中是否存在一个给定的子串（模式）

病毒感染检测目录导航4.14.24.34.44.54.64.74.8串的定义案例引入串数组案例分析与实现精选习题解析AI协作实战Python标准库中的数组与字符串Contents串的存储结构链式存储顺序存储classSString:

#本章后面算法描述当中所用到的顺序存储的字符串都是从索引为1的数组分量开始存储的，索引为0的分量闲置不用

def__init__(self):self.ch=[None]*max_sizeself.length=0#串长度

顺序存储表示链式存储表示classSNode:

def__init__(self,data=None):

self.data=data

self.next=None

def__str__(self):

returnstr(self.data)classLString:

def__init__(self):

self.front=SNode()

self.rear=self.front#串的头指针和尾指针

链式存储表示优点：操作方便。缺点：存储密度较低。可将多个字符存放在一个结点中，以克服其缺点。实际分配的存储位串值所占的存储位存储密度=链式存储表示串的模式匹配算法算法目的：算法种类：AB确定主串中所含子串第一次出现的位置（定位）。BF算法（又称古典的、经典的、朴素的、穷举的）KMP算法（特点：速度快）S:ababcabcacbabT:abcijS:ababcabcacbab T:abcS:ababcabcacbabT:abci

指针回溯BF算法设计思想将主串的第pos个字符和模式的第一个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较。直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。BF算法设计思想index_bf(s,t,pos)否则，匹配失败，返回值0defindex_bf(s,t,pos):#返回模式t在主串s中第pos个字符之后s第一次出现的位置。若不存在，则返回0#其中，t非空，1≤pos≤s.lengthi=posj=1#初始化whilei<=s.lengthandj<=t.length:#两串均未比较到串尾ifs.ch[i]==t.ch[j]:i+=1j+=1#继续比较后继字符else:i=i-j+2j=1#指针后退，重新开始匹配ifj>t.length:returni-t.length#匹配成功else:return0#匹配失败BF算法描述（算法4.1）若n为主串长度，m为子串长度，最坏情况是BF算法时间复杂度主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次最后m位也各比较了1次总次数为：(n-m)*m+m＝(n-m+1)*m若m<<n，则算法复杂度O(n*m)例：S=‘aaaaaab’，T=‘aab’KMP（KnuthMorrisPratt）算法《计算机程序设计艺术第1卷基本算法》

《计算机程序设计艺术第2卷半数值算法》《计算机程序设计艺术第3卷排序与查找》《计算机程序设计艺术第4卷组合算法》BF缺陷：s的指针i回溯，已经被检索过的部分主串被重复检索。同时，t的指针j也会回溯到起始位置。babcadcbcbcdijstKMP算法KMP改进：如何避免指针i回溯。在BF中，指针i回溯的目的？不回溯可能会错过一些匹配。KMP算法设计思想bcaaadcbcaadijstbcaaadcbcaadijstKMP算法设计思想指针i不动？子串向右滑动，即找到j移动的位置，使得新的指针j之前的字符能够自动匹配。j应该移动到的位置k有什么特点？abababcabaijstbckdeKMP算法设计思想abababcabaijstbckde

而滑动之前已匹配过的字符能告诉我们什么信息呢？KMP算法设计思想主串的k-1位后缀与子串的k-1位前缀相同！

abababcabaijstbcde

KMP算法设计思想只需要比较子串的前后缀就可以了，无需主串！最长相同前缀和后缀KMP算法设计思想

abajtbc

KMP算法设计思想

max{k|1<k<j,且“p1…pk-1”=“pj-k+1…pj-1”}当此集合非空时

0当j=1时

1其他情况next[j]=为此,定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。KMP算法设计思想defindex_kmp(s,t,pos,next):#利用模式t的next函数求t在主串s中第pos个字符之后的位置的KMP算法#其中，t非空，1≤pos≤s.lengthi=posj=1whilei<=s.lengthandj<=t.length:#两个串均未比较到串尾ifj==0ors.ch[i]==t.ch[j]:i+=1j+=1#继续比较后续字符else:j=next[j]#模式向右移动ifj>t.length:returni-t.length#匹配成功else:return0#匹配失败KMP算法设计思想如何求next函数值next[1]=0;表明主串从下一字符si+1起和模式串重新开始匹配。i=i+1;j=1;设next[j]=k，则next[j+1]=?01OPTION①若pk=pj，则有“p1…pk-1pk”=“pj-k+1…pj-1pj”，如果在

j+1发生不匹配，说明next[j+1]=k+1=next[j]+1。②若pk≠pj，可把求next值问题看成是一个模式匹配问题，整个模式串既是主串，又是子串。02OPTIONKMP算法设计思想p1p2…pj-k+1…pj-1

pjpj+1next[j]=k‖‖≠

p1…pk-1

pk

pk+1next[k]=k’

p1……pk’pk’+1next[k’]=k”p1…pk’’pk’’+1next[k’’’]=k’’’

若pk’=pj，则有“p1…pk’”=“pj-k’+1…pj”，

next[j+1]=k’+1=next[k]+1=next[next[j]]+1.若pk”=pj

，则有“p1…pk””=“pj-k”+1…pj”，

next[j+1]=k”+1=next[k’]+1=next[next[k]]+1.next[j+1]=1.KMP算法设计思想j1234567891011121314151617模式串abcaabbcabcaabdab0next[j]

1112231123456712KMP算法设计思想defget_next(t):#求模式t的next函数值并将其存入数组nextnext=[0]*(t.length+1)i=1j=0whilei<t.length:ifj==0ort.ch[i]==t.ch[j]:i+=1j+=1next[i]=jelse:j=next[j]returnnext

KMP算法设计思想KMP算法的时间复杂度

设主串s的长度为n,模式串t长度为m,在KMP算法中求next数组的时间复杂度为O(m),在后面的匹配中因主串s的下标不减即不回溯,比较次数可记为n,所以KMP算法总的时间复杂度为O(n+m)。KMP算法设计思想next函数的改进j12345模式aa

a

abnext[j]01234nextval[j]00004aa

abaa

a

abaa

a

a

①aa

a

②aa

③aaa

a

ab

i=5;j=1i=4j=4j=3j=1j=2next[j]=k，而pj=pk，则主串中si和pj不等时，不需再和pk进行比较，而直接和pnext[k]进行比较。KMP算法设计思想j1234567891011121314151617模式串abcaabbcabcaabdabnext[j]011122311234567120nextval[j]1102131011021701KMP算法设计思想

defget_nextval(t):#求模式T的next函数修正值并将之存入数组nextvali=1j=0nextval=[0]*(t.length+1)whilei<t.length:ifj==0ort.ch[i]==t.ch[j]:i+=1j+=1ift.ch[i]!=t.ch[j]:

nextval[i]=jelse:j=nextval[j]returnnextval

KMP算法设计思想目录导航4.14.24.34.44.54.64.74.8串的定义案例引入串数组案例分析与实现精选习题解析AI协作实战Python标准库中的数组与字符串Contents本节所讨论的数组与高级语言中的数组区别：数组高级语言中的数组是顺序结构；而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。一维数组352749186054778341020123456789ll

l

l

l

l

l

l

l

l

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=LOC(i-1)+l=a+i*l,i>0a,i

=0

a+i*la二维数组以行序为主序C,PASCAL数组的顺序存储以列序为主序FORTRAN数组的顺序存储

a[n][m]设数组开始存放位置LOC(0,0)=a

LOC(j,k)=a+j*m+k二维数组的行序优先表示三维数组按页/行/列存放，页优先的顺序存储

①②③a[m1][m2][m3]各维元素个数为m1,m2,m3

下标为i1,i2,i3的数组元素的存储位置：

LOC(i1,i2,i3)=a+

i1*m2*m3+i2*m3+i3前i1页总元素个数第i1页的前i2行总元素个数第i2行前i3列元素个数三维数组各维元素个数为m1,m2,m3,…,mn下标为i1,i2,i3,…,in

的数组元素的存储位置：

n维数组n维数组设有一个二维数组A[m][n]按行优先顺序存储，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。设数组元素A[i][j]存放在起始地址为Loc(i,j)的存储单元中∵Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.∴n=(676-2-644)/2=15∴Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.练习设有二维数组A[10,20]，其每个元素占两个字节，A[0][0]存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为

，按列优先顺序存储，元素A[6,6]的存储地址为

。练习352232(6*20+6)*2+100=352(6*10+6)*2+100=232特殊矩阵的压缩存储12什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。什么样的矩阵能够压缩？一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）。3[特点]

在n×n的矩阵a中，满足如下性质：aij=aji(1≤i,j≤n)[存储方法]

只存储下(或者上)三角(包括主对角线)的数据元素

共占用n(n+1)/2个元素空间。

a11a21a22a31

aij(aji)ann

k1234n(n+1)/2saajiaij1.对称矩阵2.三角矩阵

上三角矩阵下三角矩阵(i-1)(2n-i+2)/2+j-i+1i≤ji(i-1)/2+ji≥jn(n+1)/2+1i>j

n(n+1)/2+1i<jCC上三角矩阵下三角矩阵k=k=[特点]

对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c。[存储方法]

重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素

空间：

sa[1..n(n+1)/2+1]。3.对角矩阵（带状矩阵）

823000

420300

577680096915006142000283五对角矩阵

338520612827943476185962s[-2..2;1..6]-2-1012123456i1=i-jj1=j|i-j|(L-1)/2k1n*Lsak=(i1+2)*n+j1=(i-j+2)*n+j|i-j|(L-1)/2[特点]

在n×n的方阵中，非零元素集中在主对角线及其两侧共L（奇数）

条对角线的带状区域内—L对角矩阵。[存储方法]以对角线的顺序存储

823000

420300

577680096915006142000283823420357768969156142283sak12345678910111213141516171819202122232425263.对角矩阵（带状矩阵）只存储带状区内的元素除首行和末行，按每行L个元素，共(n-2)L+(L+1)个元素。sa[1..(n-1)L+1]k=(i-1)L+1+(j-i)|i-j|(L-1)/2稀疏矩阵[特点]

大多数元素为零。顺序存储：三元组表链式存储：十字(正交)链表

[常用存储方法]

只记录每一非零元素(i,j,aij)节省空间，但丧失随机存取功能。1500220-15011

3000000-600000000

91

000000028000目录导航4.14.24.34.44.54.64.74.8串的定义案例引入串数组案例分析与实现精选习题解析AI协作实战Python标准库中的数组与字符串Contents病毒感染检测【案例分析】因为患者的DNA和病毒DNA均是由一些字母组成的字符

串序列，要检测某种病毒DNA序列是否在患者的DNA序

列中出现过，实际上就是字符串的模式匹配问题。可以利用BF算法，也可以利用更高效的KMP算法。但与一般的模式匹配问题不同的是，此案例中病毒的

DNA序列是环状的。这样需要对传统的BF算法或KMP算法进行改进。【案例实现】对于每一个待检测的任务，假设病毒DNA序列的长度是m，因为病毒DNA序列是环状的，为了线性取到每个可行的长度为m的模式串，可将存储病毒DNA序列的字符串长度扩大为2m，将病毒DNA序列连续存储两次。然后循环m次，依次取得每个长度为m的环状字符串，将此字符串作为模式串，将人的DNA序列作为主串，调用BF算法进行模式匹配。只要匹配成功，即可中止循环，表明该人感染了对应的病毒；否则，循环m次结束循环时，可通过BF算法的返回值判断该人是否感染了对应的病毒。病毒感染检测【算法步骤】①从文件中读取待检测的任务数num。②

根据num个数依次检测每对病毒DNA和人的DNA是否匹配，循环num次，执行以下操作：从文件中分别读取一对病毒DNA序列和人的DNA序列；设置标志性变量flag，用来标识是否匹配成功，初始为0

，表示未匹配；病毒DNA序列的长度是m，将存储病毒DNA序列的字符

串长度扩大为2m，将病毒DNA序列连续存储两次；病毒感染检测循环m次，重复执行以下操作：依次取得每个长度为m的病毒DNA环状字符串；将此字符串作为模式串，将人的DNA序列作为主串，

调用BF算法进行模式匹配，将匹配结果返回赋值给flag；若flag非0，表示匹配成功，中止循环，表明该人感染

了对应的病毒。退出循环时，判断flag的值，若flag非0，输出“YES”，

否则，输出“NO”。病毒感染检测目录导航4.14.24.34.44.54.64.74.8串的定义案例引入串数组案例分析与实现精选习题解析AI协作实战Python标准库中的数组与字符串Contents【算法练习题4.1】求字符出现的次数【问题描述】写一个算法，统计输入字符串中各个不同字符出现的次数，注意：本练习题中字符串中的合法字符为A～Z这26个字母和0～9这10个数字。【输入要求】输入总计1行。输入待统计合法字符出现次数的字符串。【输入样例】111HELLO【算法练习题4.1】求字符出现的次数【输出要求】输出总计多行。每一行为一个字符及其出现的次数，按照字符的美国信息交换标准代码（Americanstandardcodeforinformationinterchange，ASCII）值从小到大的顺序输出，格式为“字符：出现的次数”。【输出样例】1：3E：1H：1L：2O：1【算法练习题4.1】求字符出现的次数【问题分析】算法思想是：依次读取字符串中的每个字符，当遇到数字时，将相应数字的ASCII值减去数字0的ASCII值（48），并将得出的数值（0～9）作为该数字在num中的索引；当遇到字母时，将相应字母的ASCII值减去字母A的ASCII值（65），然后将结果加上10，并将得出的数值（10～35）作为该字母在num中的索引；当遇到其他字符时，不做任何处理，直至输入字符串结束。【算法练习题4.1】求字符出现的次数【算法步骤】①初始化一个长度为36的数组num，用于记录数字和字母出现的次数。②遍历输入字符串中的每个字符：●如果字符是数字（0～9），将其转换为对应的索引并在num数组中相应位置加1；●如果字符是字母（A～Z），将其转换为对应的索引并在num数组中相应位置加1。③遍历数字0～9，在每次循环中输出数字出现的次数。④遍历字母A～Z，在每次循环中输出字母出现的次数。【算法练习题4.1】求字符出现的次数【算法描述】defcount(ch):#统计输入字符串中数字和字母出现的个数num=[0]*36#初始化i=0whilei<len(ch):#依次读取字符进行判断if'0'<=ch[i]<='9':#数字j=ord(ch[i])-48num[j]+=1elif'A'<=ch[i]<='Z':#字母j=ord(ch[i])-65+10num[j]+=1i+=1i=0whilei<10:#输出数字出现的次数ifnum[i]!=0:print(i,"：",num[i])i+=1i=10whilei<36:#输出字母出现的次数ifnum[i]!=0:print(chr(i+55),"：",num[i])i+=1【算法练习题4.2】验证回文串【问题描述】给定一个字符串s，判断其是否为回文串，若是，返回True，否则，返回False。其中，回文串是指将字符串中所有大写字母转换为小写字母，并移除所有非字母数字字符之后，正读和反读相同的字符串，字母和数字都属于字母数字字符。【输入要求】输入总计1行。输入待判断是否为回文串的字符串。【输入样例】Aman,aplan,acanal:Panama【算法练习题4.2】验证回文串【输出要求】判断其是否为回文串，若是，返回True，否则，返回False。【输出样例】True【问题分析】【算法练习题4.2】验证回文串【算法步骤】①定义left和right两个指针，初始时left指向第一个字符，right指向最后一个字符。②遍历字符串s，当left<right时，循环执行以下操作：●若left所指字符为非字母数字字符，则将其向右移动一个字符，并循环执行此操作，直到left所指字符为字母数字字符；●若right所指字符为非字母数字字符，则将其向左移动一个字符，并循环执行此操作，直到right所指字符为字母数字字符；●若left和right所指字符转换为小写字母后不相同，则返回False；●若left和right所指字符转换为小写字母后相同，则将left向右移动一个字符，将right向左移动一个字符。③left≥right，遍历完字符串s，返回True。【算法练习题4.2】验证回文串【算法描述】defis_palindrome(s):#验证回文串left,right=0,len(s)-1whileleft<right:whileleft<rightandnots[left].isalnum():#left所指字符为非字母数字字符left+=1whileleft<rightandnots[right].isalnum():#right所指字符为非字母数字字符right-=1#转换为小写字母后比较ifleft<rightands[left].lower()!=s[right].lower():returnFalseleft+=1right-=1returnTrue目录导航4.14.24.34.44.54.64.74.8串的定义案例引入串数组案例分析与实现精选习题解析AI协作实战Python标准库中的数组与字符串ContentsAI潜在问题分析可借助“算法小精灵”对该程序进行潜在问题分析。将题目信息及程序提交至“算法小精灵”后，向其发起提问，通过“算法小精灵”AI辅助编程，养成良好的编程习惯和培养综合工程思维能力。AI程序优化方案目录导航4.14.24.34.44.54.64.74.8串的定义案例