数据结构-第4章-串、数组和广义表课件

北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,李冬梅,第,4,章 串、数组和广义表,Office:,西配楼,304,（软件教研室）,Email:lidongmei,北京林业大学信息学院李冬梅 第4章 串、数组和广义表Off,2024年8月9日,北京林业大学信息学院,可表示为,：（,a,1,a,2,a,n,）,线性结构,第,2,章 线性表,第,3,章 栈和队列,第,4,章 串、数组和广义表,2023年8月21日,2024年8月9日,北京林业大学信息学院,串比较，,strcmp(char s1,char s2),串复制，,strcpy(char to,char from),串连接，,strcat(char to,char from),求串长，,strlen(char s),调用标准库函数,#include,补充：,C,语言中常用的串运算,2023年8月21日,2024年8月9日,北京林业大学信息学院,第,4,章串、数组和广义表,4.1,串,4.2,数组,4.3,广义表,教学内容,2023年8月21日,2024年8月9日,北京林业大学信息学院,1.,掌握串的存储方法，理解串的两种模式匹配算法,；,2.,明确数组和广义表这两种数据结构的特点，掌握数组存储时地址计算方法，了解几种特殊矩阵的压缩存储方法。,教学目标,1.,了解串的存储方法，理解串的两种模式匹配算法，重点掌握,BF,算法,。,2.,明确数组和广义表这两种数据结构的特点，掌握,数组地址计算方法,，了解几种特殊矩阵的压缩存储方法。,3.,掌握广义表的定义、性质及其,GetHead,和,GetTail,的操作,。,2023年8月21日,2024年8月9日,北京林业大学信息学院,4.1,串的定义,串,(String)-,零个或多个字符组成的有限序列,串名,串值,串长,n,空串,n=0,2023年8月21日,2024年8月9日,北京林业大学信息学院,a=,BEI,b=,JING,c=,BEIJING,d=,BEI JING,子串,字符位置,主串,子串位置,串相等,空格串,2023年8月21日,北京林业大学信息学院,4.2,案例引入,案例,4.1,：病毒感染检测,研究者将人的,DNA,和病毒,DNA,均表示成由一些字母组成的字符串序列。,然后检测某种病毒,DNA,序列是否在患者的,DNA,序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染。,例如，假设病毒的,DNA,序列为,baa,，患者,1,的,DNA,序列为,aaabbba,，则感染，患者,2,的,DNA,序列为,babbba,，则未感染。,（注意，人的,DNA,序列是线性的，而病毒的,DNA,序列是环状的,),北京林业大学信息学院4.2 案例引入案例4.1：病毒感染检,北京林业大学信息学院,北京林业大学信息学院,北京林业大学信息学院,4.3,串的类型定义、存储结构及运算,数据对象,:,数据关系,:,基本操作,:,(1)StrAssign(&T,chars)/,串赋值,(2)StrCompare(S,T)/,串比较,(3)StrLength(S)/,求串长,(4)Concat(&T,S1,S2)/,串联,ADT String,北京林业大学信息学院4.3 串的类型定义、存储结构及运算数据,2024年8月9日,北京林业大学信息学院,(5)SubString(&Sub,S,pos,len)/,求子串,(6)StrCopy(&T,S)/,串拷贝,(7)StrEmpty(S)/,串判空,(8)ClearString(&S)/,清空串,(9),Index(S,T,pos),/,子串的位置,(11)Replace(&S,T,V)/,串替换,(12)StrInsert(&S,pos,T)/,子串插入,(12)StrDelete(&S,pos,len)/,子串删除,(13)DestroyString(&S)/,串销毁,ADT String,2023年8月21日,2024年8月9日,北京林业大学信息学院,顺序存储,链式存储,串的存储结构,2023年8月21日,北京林业大学信息学院,typedef struct,char*ch;/,若串非空,则按串长分配存储区,/,否则,ch,为,NULL,int length;/,串长度,HString;,顺序存储表示,北京林业大学信息学院typedef struct顺序存储表,北京林业大学信息学院,链式存储表示,北京林业大学信息学院链式存储表示,2024年8月9日,北京林业大学信息学院,#define CHUNKSIZE 80 /,可由用户定义的块大小,typedef struct Chunk,char chCHUNKSIZE;,struct Chunk*next;,Chunk;,typedef struct,Chunk*head,*tail;/,串的头指针和尾指针,int curlen;/,串的当前长度,LString,;,链式存储表示,2023年8月21日,2024年8月9日,北京林业大学信息学院,可将多个字符存放在一个结点中，以克服其缺点,优点：操作方便,缺点：存储密度较低,实际分配的存储位,串值所占的存储位,存储密度,=,链式存储表示,2023年8月21日,2024年8月9日,北京林业大学信息学院,算法目的：,BF,算法,（又称古典的、经典的、朴素的、穷举的）,KMP,算法（特点：速度快）,算法种类：,确定主串中所含子串第一次出现的位置（定位）,即如何实现教材,P72 Index(S,T,pos),函数,串的模式匹配算法,2023年8月21日,北京林业大学信息学院,S :a b a b c a b c a c b a b,T :a b c,i,j,S :a b a b c a b c a c b a b,T :a b c,S :a b a b c a b c a c b a b,T :a b c,i,指针回溯,BF,算法设计思想,北京林业大学信息学院S :a b a b c a b c,北京林业大学信息学院,将主串的第,pos,个字符和模式的第一个字符比较，,若,相等,，继续逐个比较后续字符；,若,不等,，从主串的下一字符起，重新与模式的第一个字符比较。,直到主串的一个连续子串字符序列与模式相等。返回值为,S,中与,T,匹配的子序列,第一个字符的序号,，即匹配成功。,否则，匹配失败，返回值,0,BF,算法设计思想,Index(S,T,pos),北京林业大学信息学院直到主串的一个连续子串字符序列与模式相等,北京林业大学信息学院,int Index(Sstring S,Sstring T,int pos),i=pos;j=1;,while(i=S 0&j T 0)return i,T0;,else return 0;,BF,算法描述（算法,4.1,）,北京林业大学信息学院int Index(Sstring S,北京林业大学信息学院,若,n,为主串长度，,m,为子串长度，最坏情况是,BF,算法时间复杂度,主串前面,n-m,个位置都部分匹配到子串的最后一位，即这,n-m,位各比较了,m,次,最后,m,位也各比较了,1,次,总次数为：,(n-m)*m+m,(n-m+1)*m,若,mn,，则算法复杂度,O(n*m),例：,S=,0000000001,，,T=,0001,，,pos=1,北京林业大学信息学院若n为主串长度，m为子串长度，最坏情况是,2024年8月9日,北京林业大学信息学院,KMP,（,Knuth,Morris Pratt,）算法,www-cs-faculty.stanford.edu/knuth/,计算机程序设计艺术 第1卷 基本算法,计算机程序设计艺术 第2卷 半数值算法,计算机程序设计艺术 第3卷 排序与查找,2023年8月21日,北京林业大学信息学院,利用已经,部分匹配,的结果而加快模式串的滑动速度？,且主串,S,的指针,i,不必回溯,！可提速到,O(n+m),！,S=a b a b c a b c a c b a b,T=,a b c a c,S=,a b,a b c a,b,c a c b a b,T=,a b c a,c,S=,a b,a b c a,b c a c,b a b,T=,a,b c a c,i,i,i,k,k,a,b,a,a,b,c,k,i,i,KMP,算法设计思想,北京林业大学信息学院利用已经部分匹配的结果而加快模式串的滑动,因,p,1,p,2,s,2,=p,2,必有,s,2,p,1,又因,p,1,=p,3,s,3,=p,3,所以必有,s,3,=p,1,。因此,第二次匹配可直接从,i=4,j=2,开始。,北京林业大学信息学院,因p1p2,s2=p2,必有s2p1,又因p1=p3,s,改进：,每趟匹配过程中出现字符比较不等时，不回溯主指针,i,，利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离，继续进行比较。,北京林业大学信息学院,改进：每趟匹配过程中出现字符比较不等时，不回溯主指针i，利用,s,1,s,2,s,3,s,i-j+1,s,i-j+2,s,i-2,s,i-1,s,i,s,i+1,p,1,p,2,p,j-2,p,j-1,p,j,p,j+1,p,1,p,k-1,p,k,p,k+1,“p,1,p,2,p,k-1,”=“s,i-k+1,s,i-k+2,s,i-1,”,“p,j-k+1,p,j-k+2,p,j-1,”=“s,i-k+1,s,i-k+2,s,i-1,”,（,部分匹配,）,“,p,1,p,2,p,k-1,”=“p,j-k+1,p,j-k+2,p,j-1,”(,真子串,）,北京林业大学信息学院,s1 s2 s3si-j+1 si-j+2si-2 si,max k|1kj,且“,p,1,p,k-1,”=“p,j-k+1,p,j-1,”,当此集合非空时,0,当,j=1,时,1,其他情况,nextj=,为此,定义,nextj,函数，表明当模式中第,j,个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。,北京林业大学信息学院,nextj=为此,定义nextj函数，表明当模式,int Index_KMP(SString S,SString T,int pos),i=pos,j=1;,while(iS0&jT0)return i-T0;/*,匹配成功*,/,else return 0;/*,返回不匹配标志*,/,北京林业大学信息学院,int Index_KMP(SString S,SStri,如何求,next,函数值,1.next1=0;,表明主串从下一字符,s,i+1,起和模式串重新开始匹配。,i=i+1;j=1;,2.,设,nextj=k,，则,nextj+1=?,若,p,k,=p,j,，则有“,p,1,p,k-1,p,k,”=“p,j-k+1,p,j-1,p,j,”,，如果在,j+1,发生不匹配，说明,nextj+1=k+1=nextj+1,。,若,p,k,p,j,，可把求,next,值问题看成是一个模式匹配问,题，整个模式串既是主串，又是子串。,北京林业大学信息学院,如何求next函数值北京林业大学信息学院,p,1,p,2,p,j-k+1,p,j-1,p,j,p,j+1,nextj=k,p,1,p,k-1,p,k,p,k+1,nextk=k,p,1,p,k,p,k,+1,nextk,=k,”,p,1,p,k,p,k,+1,nextk,=k,若,p,k,=p,j,，则有“,p,1,p,k,”=“p,j-k+1,p,j,”,，,nextj+1=k+1=nextk+1=nextnextj+1.,若,p,k”,=p,j,，则有“,p,1,p,k”,”=“p,j-k”+1,p,j,”,，,nextj+1=k”+1=nextk+1=nextnextk+1.,nextj+1=1.,北京林业大学信息学院,p1 p2pj-k+1pj-1 pj pj+1,j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17,模式串,a b c a a b b c a b c a a b d a b,0,nextj,1,1,1,2,2,3,1,1,2,3,4,5,6,7,1,2,北京林业大学信息学院,j 1 2 3 4 5,void get_next(SString T,int&next),i=1;next1=0;j=0;,while(iT0),if(j=0|Ti=Tj),+i;+j;,nexti=j;,else,j=nextj;,北京林业大学信息学院,void get_next(SString T,int&,KMP,算法的时间复杂度,设主串,s,的长度为,n,模式串,t,长度为,m,在,KMP,算法中求,next,数组的时间复杂度为,O(m),在后面的匹配中因主串,s,的下标不减即不回溯,比较次数可记为,n,所以,KMP,算法总的时间复杂度为,O(n+m),。,北京林业大学信息学院,KMP算法的时间复杂度 北京林业大学信息学院,next,函数的改进,j 1 2 3 4 5,模式,a a a a b,nextj 0 1 2 3 4,nextvalj 0 0 0 0 4,a a a b a a a a b,a a a a,a a a,a a,a,a a a a b,i=5;j=1,i=4,j=4,j=3,j=1,j=2,nextj=k,，而,p,j,=p,k,，则 主串中,s,i,和,p,j,不等时，不需再和,p,k,进行比较，而直接和,p,nextk,进行比较。,北京林业大学信息学院,next函数的改进 j 1 2 3 4 5,j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17,模式串,a b c a a b b c a b c a a b d a b,nextj 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2,0,nextvalj,1,1,0,2,1,3,1,0,1,1,0,2,1,7,0,1,北京林业大学信息学院,j 1 2 3 4 5,void get_nextval(SString T,int&nextval),i=1;nextval1=0;j=0;,while(i 0,a,i,=0,a+i*l,a,北京林业大学信息学院一维数组35 27 49,北京林业大学信息学院,二维数组,北京林业大学信息学院二维数组,北京林业大学信息学院,以行序为主序,C,PASCAL,数组的顺序存储,北京林业大学信息学院以行序为主序C,PASCAL数组的顺序,北京林业大学信息学院,以列序为主序,FORTRAN,北京,北京林业大学信息学院,anm,设数组开始存放位置,LOC(0,0)=,a,LOC(,j,k,)=,a,+,j,*,m,+,k,二维数组的行序优先表示,北京,北京林业大学信息学院,三维数组,按页,/,行,/,列存放，页优先的顺序存储,北京林业大学信息学院三维数组按页/行/列存放，页优先的,北京林业大学信息学院,am1m2 m3,各维元素个数为,m,1,m,2,m,3,下标为,i,1,i,2,i,3,的数组元素的存储位置：,LOC(,i,1,i,2,i,3,)=,a,+,i,1,*,m,2,*,m,3,+i,2,*m,3,+i,3,前,i,1,页总,元素个数,第,i,1,页的,前,i,2,行,总元素个数,第,i,2,行前,i,3,列,元素个数,三维数组,北京林业大学信息学院am1m2 m3 各维元素个,北京林业大学信息学院,各维元素个数为,m,1,m,2,m,3,m,n,下标为,i,1,i,2,i,3,i,n,的数组元素的存储位置：,n,维数组,北京林业大学信息学院 各维元素个数为 m1,m2,m3,北京林业大学信息学院,n,维数组,北京林业大学信息学院n维数组,北京林业大学信息学院,设有一个二维数组,A,m,n,按行优先,顺序存储,，假设,A,00,存放位置在,644,(10),，,A,22,存放位置在,676,(10),，每个元素占一个空间，问,A,33,(10),存放在什么位置？脚注,(10),表示用,10,进制表示。,设数组元素,Aij,存放在起始地址为,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.,练习,北京林业大学信息学院设有一个二维数组Amn按行优先顺,北京林业大学信息学院,设有二维数组,A10,20,，其每个元素占两个字节，,A,00,存储地址为,100,，若,按行优先,顺序存储，则元素,A6,6,的存储地址为,，,按列优先,顺序存储，元素,A6,6,的存储地址为,。,练习,352,232,(6*20+6)*2+100=352,(6*10+6)*2+100=232,北京林业大学信息学院设有二维数组A10,20，其每个元素,北京林业大学信息学院,1.,什么是压缩存储？,若多个数据元素的,值都相同,，则只分配一个元素值的存储空间，且零元素不占存储空间。,2.,什么样的矩阵能够压缩？,一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。,3.,什么叫稀疏矩阵？,矩阵中非零元素的个数较少（一般小于,5%,）,特殊矩阵的压缩存储,北京林业大学信息学院1.什么是压缩存储？特殊矩阵的压缩存储,1.,对称矩阵,特点,在,n,n,的矩阵,a,中，满足如下性质：,a,ij,=a,ji,(1 i,j n),存储方法,只存储下,(,或者上,),三角,(,包括主对角线,),的数据元素。共占用,n(n+1)/2,个元素空间。,k=i(i-1)/2+j,当,i,j,j(j-1)/2+i,当,ij,n(n+1)/2+1 ij,C,C,上三角矩阵,下三角矩阵,北京林业大学信息学院,2.三角矩阵特点 对角线以下(或者以上)的数据元素(,3.,对角矩阵（带状矩阵）,特点,在,n,n,的方阵中，非零元素集中在主对角线及其两侧共,L(,奇数,),条对角线的带状区域内,L,对角矩阵。,存储方法,以对角线的顺序存储,8 2 3,0 0 0,4 2 0 3,0 0,5 7 7 6 8,0,0,9 6 9 1 5,0 0,6 1 4 2,0 0 0,2 8 3,五对角矩阵,3 3 8 5,2 0 6 1 2,8 2 7 9 4 3,4 7 6 1 8,5 9 6 2,s-2.2;1.6,-2,-1,0,1,2,1 2 3 4 5 6,i1=i-j,j1=j,|i-j|,(L-1)/2,k 1 n*L,sa,k=(i1+2)*n+j1=(i-j+2)*n+j,|i-j|,(L-1)/2,北京林业大学信息学院,3.对角矩阵（带状矩阵）特点 在nn的方阵中，非零元,只存储带状区内的元素,除首行和末行，按每行,L,个元素，共,(n-2)L+(L+1),个元素。,sa1.(n-1)L+1,k=(i-1)L+1+(j-i)|i-j|,(L-1)/2,8 2 3,0 0 0,4 2 0 3,0 0,5 7 7 6 8,0,0,9 6 9 1 5,0 0,6 1 4 2,0 0 0,2 8 3,8 2 3 4 2 0 3 5 7,7 6 8 9 6 9 1 5 6 1,4 2 2 8 3,sa,k,1 2 3 4 5 6 7 8 9 10,11 12 13 14 15 16 17 18 19 20,21 22 23 24 25 26,北京林业大学信息学院,只存储带状区内的元素8 2 3 4 2 0,稀疏矩阵,特点,大多数元素为零。,常用存储方法,只,记录每一非零元素,(i,j,a,ij,),节省空间，但丧失随机存取功能,顺序存储：三元组表,链式存储：十字,(,正交,),链表,15,0 0,22,0,-15,0,11,3,0 0 0,0 0 0,-6,0 0,0 0 0 0 0 0,91,0 0 0 0 0,0 0,28,0 0 0,6,6,北京林业大学信息学院,稀疏矩阵特点 大多数元素为零。66北京林业大学信息学,北京林业大学信息学院,4.5,广义表,广义表（列表）：,n,(,0,),个表元素组成的有限序列,，,记作,LS,=(,a,0,a,1,a,2,a,n,-1,),LS,是表名，,a,i,是表元素，它可以是表,(,称为,子表,),，可以是数据元素,(,称为,原子,),。,n,为表的长度。,n,=0,的广义表为空表。,北京,北京林业大学信息学院,线性表的成分都是结构上不可分的单元素,广义表的成分可以是单元素，也可以是有结构的表,线性表是一种特殊的广义表,广义表不一定是线性表，也不一定是线性结构,广义表与线性表的区别？,北京林业大学信息学院线性表的成分都是结构上不可分的单元素广义,北京林业大学信息学院,广义表的基本运算,（,1,）求表头,GetHead(L),：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表,（,2,）求表尾,GetTail(L),：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表,北京林业大学信息学院广义表的基本运算（1）求表头GetHea,北京林业大学信息学院,练习,A=(),GetHead,和,GetTail,均无定义,A=(a,b),GetHead,(A)=a,GetTail,(A)=(b),A=(a),GetHead,(A)=a,GetT,ail(A)=(),A=(a),GetHead,(A)=(a),GetTail,(A)=(),GetHead,(,GetTail,(,Get,Head(,GetTail,(,GetTail,(A),A=(a,b,(c,d),(e,(f,g),d,北京林业大学信息学院练习A=()GetHe,北京林业大学信息学院,有次序性,有长度,有深度,可递归,可共享,一个直接前驱和一个直接后继,表中元素个数,表中括号的重数,自己可以作为自己的子表,可以为其他广义表所共享,广义表的特点,北京林业大学信息学院有次序性一个直接前驱和一个直接后继广义表,北京林业大学信息学院,E=(a,E)=(a,(a,E)=,(a,(a,(a,.),，,E,为递归表,1,）,A=(),2,）,B=(e),3,）,C=(a,(b,c,d),4,）,D=(A,B,C),5,）,E=(a,E),n=0,，,因为,A,是空表,n=1,，表中元素,e,是原子,n=2,，,a,为原子，,(b,c,d),为子表,n=3,，,3,个元素都是子表,n=2,，,a,为原子，,E,为子表,D=(A,B,C)=(),(e),(a,(b,c,d),，,共享表,练习：求下列广义表的长度,北京林业大学信息学院E=(a,E)=(a,(a,E)=(,北京林业大学信息学院,4.6,案例分析与实现,案例,4.1,：病毒感染检测,【,案例分析,】,因为患者的,DNA,和病毒,DNA,均是由一些字母组成的字符串序列，要检测某种病毒,DNA,序列是否在患者的,DNA,序列中出现过，实际上就是字符串的模式匹配问题。,可以利用,BF,算法，也可以利用更高效的,KMP,算法。,但与一般的模式匹配问题不同的是，此案例中病毒的,DNA,序列是环状的。,这样需要对传统的,BF,算法或,KMP,算法进行改进。,北京林业大学信息学院4.6 案例分析与实现案例4.1：病毒,北京林业大学信息学院,【,案例实现,】,对于每一个待检测的任务，假设病毒,DNA,序列的长度是,m,，,因为病毒,DNA,序列是环状的，为了线性取到每个可行的长度为,m,的模式串，可将存储病毒,DNA,序列的字符串长度扩大为,2,m,，将病毒,DNA,序列连续存储两次。,然后循环,m,次，依次取得每个长度为,m,的环状字符串，将此字符串作为模式串，将人的,DNA,序列作为主串，调用,BF,算法进行模式匹配。,只要匹配成功，即可中止循环，表明该人感染了对应的病毒；否则，循环,m,次结束循环时，可通过,BF,算法的返回值判断该人是否感染了对应的病毒。,北京林业大学信息学院【案例实现】,北京林业大学信息学院,【,算法步骤,】,从文件中读取待检测的任务数,num,。,根据,num,个数依次检测每对病毒,DNA,和人的,DNA,是否匹配，循环,num,次，执行以下操作：,从文件中分别读取一对病毒,DNA,序列和人的,DNA,序列；,设置标志性变量,flag,，用来标识是否匹配成功，初始为,0,，表示未匹配；,病毒,DNA,序列的长度是,m,，将存储病毒,DNA,序列的字符串长度扩大为,2,m,，将病毒,DNA,序列连续存储两次；,循环,m,次，重复执行以下操作：,依次取得每个长度为,m,的病毒,DNA,环状字符串；,将此字符串作为模式串，将人的,DNA,序列作为主串，调用,BF,算法进行模式匹配，将匹配结果返回赋值给,flag,；,若,flag,非,0,，表示匹配成功，中止循环，表明该人感染了对应的病毒。,退出循环时，判断,flag,的值，若,flag,非,0,，输出“,YES,”，否则，输出“,NO,”。,北京林业大学信息学院【算法步骤】,北京林业大学信息学院,1.,了解串的存储方法，理解串的两种模式匹配算法，重点掌握,BF,算法,。,2.,明确数组和广义表这两种数据结构的特点，掌握,数组地址计算方法,，了解几种特殊矩阵的压缩存储方法。,3.,掌握广义表的定义、性质及其,GetHead,和,GetTail,的操作,。,小结,北京林业大学信息学院1.了解串的存储方法，理解串的两种模式,