c语言-第4章字符串、数组和特殊矩阵.ppt

第4章字符串、数组和特殊矩阵,字符串,字符串的模式匹配,稀疏矩阵,数组,特殊矩阵,4.1字符串4.1.1字符串的基本概念字符串是由零个或多个字符构成的有限序列，一般可表示成如下形式：“”(n0)串中所含字符的个数n称为字符串的长度；当n=0时，称字符串为空串。串中任意个连续的字符构成的子序列称为该串的子串，包含子串的串称为主串。通常称字符在字符串序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。例如：T=“STUDENT”，S=“UDEN”,则S是T的子串，S在T中出现的位置为3。,两个字符串相等，当且仅当两个串的长度相等，并且各个对应位置的字符都相等。例如：T1=“REDROSE”T2=“REDROSE”由于T1和T2的长度不相等，因此T1T2。若T3=“STUDENT”T4=“STUDENS”虽然T3和T4的长度相等，但两者有些对应的字符不同，因而T3T4。值得一提的是，若S=“”，此时S由一个空格字符组成，其长度为1，它不等价于空串，因为空串的长度为0。,4.1.2字符串类的定义ADTstring数据对象D：由零个或多个字符型的数据元素构成的有限集合；数据关系R：|其中ai,ai+1D,i=1,2,n-1字符串的基本操作如下：（1）Strcreate(S)（2）Strassign(S,T)（3）Strlength(S)（4）Strempty(S),（5）Strclear(S)（6）Strcompare(S1，S2)（7）Strconcat(S1，S2)（8）Substring(S,i,len)（9）Index(P,T)（10）Strinsert(S,i,T)（11）Strdelete(S,i,len)（12）Replace(S,T1,T2)（13）Strdestroy(S)ADTstring,4.1.3字符串的存储及其实现1、串的顺序存储及其部分运算的实现串的顺序存储使用数组存放，具体类型定义如下：#defineMAXSIZE100typedefstructcharstrMAXSIZE;intlength;seqstring;,（1）插入运算strinsert(S,i,T)voidstrinsert(seqstring*S,inti,seqstringT)intk;if(iS-length+1|S-length+T.lengthMAXSIZE)printf(connotinsertn“);elsefor(k=S-length-1;k=i-1;k-)S-strT.length+k=S-strk;for(k=0;kstri-1+k=T.strk;S-length=S-length+T.length;S-strS-length=0;,（2）删除运算strdelete(S,i,len)voidstrdelete(seqstring*S,inti,intlen)intk;if(iS-length|i+len-1S-length)printf(“cannotdeleten”);elsefor(k=i-1+len;klength;k+)S-strk-len=S-strk;S-length=S-length-len;S-strS-length=0;,（3）连接运算strconcat(S1,S2)seqstring*strconcat(seqstringS1,seqstringS2)inti;seqstring*r;if(S1.length+S2.lengthMAXSIZE)printf(cannotconcate);return(NULL);elser=(seqstring*)malloc(sizeof(seqstring);for(i=0;istri=S1.stri;for(i=0;istrS1.length+i=S2.stri;r-length=S1.length+S2.length;r-strr-length=0;return(r);,（4）求子串运算substring(S,i,len)seqstring*substring(seqstringS,inti,intlen)intk;seqstring*r;if(iS.length|i+len-1S.length)printf(“errorn”);return(NULL);elser=(seqstring*)malloc(sizeof(seqstring);for(k=0;kstrk=S.stri-1+k;r-length=len;r-strr-length=0;return(r);,2串的链接存储及其部分运算的实现串的链接存储采用单链表的形式实现，其中每个结点的定义如下：typedefstructnodechardata;structnode*next;linkstrnode;typedeflinkstrnode*linkstring;例如，串S=“abcde”，其链接存储结构如下图所示：,a,b,c,d,e,S,（1）创建字符串运算strcreate(S)voidstrcreate(linkstring*S)charch;linkstrnode*p,*r;*S=NULL;r=NULL;while(ch=getchar()!=n)p=(linkstrnode*)malloc(sizeof(linkstrnode);p-data=ch;if(*S=NULL)*S=p;elser-next=p;r=p;/*r移向当前链接串的最后一个字符的位置*/if(r!=NULL)r-next=NULL;/*处理表尾结点指针域*/,（2）插入运算strinsert(S,i,T)voidstrinsert(linkstring*S,inti,linkstringT)intk;linkstringp,q;p=*S,k=1;while(p,（3）删除运算strdelete(S,i,len)voidstrdelete(linkstring*S,inti,intlen)intk;linkstringp,q,r;p=*S,q=null;k=1;/*用p查找S的第i个元素，q始终跟踪p的前驱*/while(p,elseif(!q)r=*S;*S=p-next;/*被删除的子串位于S的最前面*/else/*被删除的子串位于的中间或最后*/r=q-next;q-next=p-next;p-next=null;while(r!=null)p=r;r=r-next;free(p);,（4）连接运算strconcat(S1,S2)voidstrconcat(linkstring*S1,linkstringS2)linkstringp;if(!(*S1)*S1=S2;return;elseif(S2)/*S1和S2均不为空串的情形*/p=*S1;/*用p查找S1的最后一个字符的位置*/while(p-next)p=p-next;p-next=S2;/*将串S2连接到S1之后*/,（5）求子串运算substring(S,i,len)linkstringsubstring(linkstringS,inti,intlen)intk;linkstringp,q,r,t;p=S,k=1;/*用p查找S中的第i个字符*/while(p,k=1;q=r;/*用q始终指向子串的最后一个字符的位置*/while(p-next/*处理子串的尾部*/,4.2字符串的模式匹配寻找字符串p在字符串t中首次出现的起始位置称为字符串的模式匹配，其中称p为模式(pattern），t为正文(text)，t的长度远远大于p的长度。4.2.1朴素的模式匹配算法朴素模式匹配算法的基本思想是：用p中的每个字符去与t中的字符一一比较：正文t：t1t2tmtn模式p：p1p2pm如果t1=p1,t2=p2,.tm=pm，则模式匹配成功；否则,将p向右移动一个字符的位置，重新用p中的字符从头开始与t中相对应的字符依次比较，即：t1t2t3tmtm+1tnp1p2pm-1pm如此反复，直到匹配成功或者p已经移到使t中剩下的字符个数小于p的长度的位置，此时意味着模式匹配失败，表示t中没有子串与模式p相等，我们约定返回-1代表匹配失败。朴素模式匹配算法的具体实现如下：,intindex(seqstringp,seqstringt)inti,j,succ;i=0;succ=0;/*succ为匹配成功的标志*/while(it.length-p.length+1),4.2.2快速模式匹配算法（KMP算法）首先我们来分析下图所示的情况：t0t1t2tktk+1tk+2tr-2tr-1tr.p0p1p2pi-2pi-1pi.（4-1）t0t1t2tktk+1tk+2tr-2tr-1tr.p0p1pi-2pi-1pi（4-2）t0t1t2tktk+1tk+2tr-2tr-1tr.p0pi-3pi-2pi-1pi（4-3）,(4-1)式表明此次匹配从p0与tk开始比较，当比较到pi与tr时出现不等情况，于是将模式右移一位，变成(4-2)所示的状态，若此次比较成功，则必有p0=tk+1，p1=tk+2，pi-2=tr-1，且pi-1pi；而根据(4-1)的比较结果有：p1=tk+1，p2=tk+2，pi-1=tr-1，因此有：p0=p1，p1=p2，pi-2=pi-1。这个性质说明在模式p中pi之前存在一个从p0开始长度为i-1的连续序列p0p1pi-2和以pi-1为结尾，长度同样为i-1的连续序列p1p2pi-1其值对应相等，即：p0p1p2pi-2pi-1pi.简记为：p0pi-2=p1pi-1称模式p中pi之前存在长度为i-1的真前缀和真后缀的匹配。,反之，若在(4-1)所示的状态下，模式p中pi之前存在长度为i-1的真前缀和真后缀的匹配，即p0pi-2=p1pi-1且pi-1pi；当pi与tr出现不等时，根据前面已比较的结果p1=tk+1，p2=tk+2，pi-1=tr-1，于是可得p0=tk+1，p1=tk+2，pi-2=tr-1，因此接下来只需从pi-1与tr开始继续后继对应字符的比较即可。再假设在(4-1)所示的状态下，模式右移一位成为状态(4-2)后，匹配仍然不成功，说明p0pi-2p1pi-1或pi-1=pi，于是模式再右移一位，成为状态(4-3)，若此次匹配成功，仿照上述分析，必有：p0p1p2pi-3pi-2pi-1pi.,即：p0pi-3=p2pi-1说明模式p中pi之前存在长度为i-2的真前缀和真后缀的匹配。由(4-3)表明，在(4-1)所示的状态下，若模式p中pi之前最长真前缀和真后缀匹配的长度为i-2，当pi与tr出现不等时，接下来只需从pi-2与tr开始继续后继对应字符的比较。考虑一般情况。在进行模式匹配时，若模式p中pi之前最长真前缀和真后缀匹配的长度为j，当pitr时，则下一步只需从pj与tr开始继续后继对应字符的比较,而不应该将模式一位一位地右移，也不应该反复从模式的开头进行比较。这样既不会失去任何匹配成功的机会，又极大地加快了匹配的速度。,根据上述分析，在模式匹配过程中，每当出现pitr时，下一次与tr进行比较的pj和模式p中pi之前最长真前缀和真后缀匹配的长度密切相关；而模式p中pi之前最长真前缀和真后缀匹配的长度只取决于模式p的组成，与正文无关。于是我们可以针对模式p定义一个数组nextm，其中nexti表示当pitr时，下一次将从pnexti与tr开始继续后继对应字符的比较。显然，nexti的值与模式p中pi之前最长真前缀和真后缀匹配的长度密切相关。下面考虑如何根据模式p的组成求数组next的值。我们规定：next0=-1这表明当p0tr时，将从p-1与tr开始继续后继对应字符的比较；然而p-1是不存在的，我们可以将这种情况理解成下一步将从p0与tr+1开始继续后继对应字符的比较。,以下假设next0，next1，nexti的值均已求出，现要求nexti+1的值。由于在求解nexti时已得到pi之前最长真前缀和真后缀匹配的长度，设其值为j，即：p0p1p2pi-j.pj-1pjpi-2pi-1pipi+1如果此时进一步有pj=pi，则pi+1之前最长真前缀和真后缀匹配的长度就为j+1，且nexti+1=j+1;反之，若pjpi，注意到，求pi+1之前最长真前缀和真后缀匹配问题本质上仍然是一个模式匹配问题，只是在这里模式和正文都是同一个串p而已。因此当pjpi时，应该检查pnextj与pi是否相等；若相等，则nexti+1=nextj+1；如仍然不相等，则再取pnextnextj与pi进行比较，直至要将p-1与pi进行比较为止，此时nexti+1=0。,以下给出了根据模式p的组成求数组next值的算法：voidgetnext(seqstringp,intnext)inti,j;next0=-1;i=0;j=-1;while(ip.length)if(j=-1|p.stri=p.strj)+i;+j;nexti=j;elsej=nextj;for(i=0;iindex2=b3;elements=b1b2b3;A-base=(datatype*)malloc(elementssizeof(datatype);if(!(A-base)return(0);A-c0=b2b3;A-c1=b3;A-c2=1;return(1);,2、访问数组元素值的运算value(A,i1,i2,i3,x)intvalue(arrayA,inti1,inti2,inti3;datatype*x)intoff;if(i1=A.index0|i2=A.index1|i3=A.index2)return(0);/*处理下标非法的情况*/off=i1A.c0+i2A.c1+i3A.c2;*x=*(A.base+off);/*赋值*/return(1);,3、数组元素的赋值运算assign(A,e,i1,i2,i3)intassign(array*A,datatypee,inti1,inti2,inti3)intoff;if(i1=A-index0|i2=A-index1|i3=A-index2)return(0);/*处理下标非法的情况*/off=i1A-c0+i2A-c1+i3A-c2;*(A-base+off)=e;/*赋值*/return(1);,4.4特殊矩阵本节主要研究对称矩阵、三角矩阵和带状矩阵的压缩存储。所谓压缩存储即为：多个相同值的结点只分配一个存储空间，值为零的结点不分配空间。4.4.1对称矩阵的压缩存储如果矩阵的行数和列数相等，则称该矩阵为方阵。若nn阶的方阵A满足：aij=aji(0in-1,0jn-1)则称矩阵A为对称矩阵。在对称矩阵中，几乎有一半元素的值是对应相等的。如果将A中所有元素进行存储，那将会造成空间的浪费，且n值越大，浪费将越严重。,对于对称矩阵压缩存储时只需存储对角线以上或对角线以下的部分，未存储的部分可以利用元素之间的对称性来访问。现考虑只存储对称矩阵A对角线以下的部分（即下标满足ij的数组元素aij）：a00a10a11A=a20a21a22a(n-1)0.a(n-1)(n-1)若采用按行优先的存储方式，A进行压缩存储后任何一个元素aij的地址计算公式为：address(a00)+(i*(i+1)/2+j)L当ijaddress(aij)=address(a00)+(j*(j+1)/2+i)L当ib或j-ib，即|i-j|b，则aij=0。b条对角线b条对角线主对角线,例、2037200014253045001114354250016202610280071583000291655,带状矩阵进行压缩存储时，只存储带状部分内部的元素，对于带状区域以外的元素，即|i-j|b的aij，均不分配存储空间。为了方便起见，我们规定按如下方法进行存储：除第一行和最后一行外，每行都分配2b+1个元素的空间，将带状区域中的元素存储于（(2b+1)n-2b）L个存储单元之中，其中L为每个元素占用空间的大小。仍考虑采用按行优先的存储方式，于是可以得到带状区域中任何一个元素aij的地址计算公式为：address(aij)=address(a00)+(i(2b+1)-b)+(j-i+b)L=address(a00)+(i(2b+1)+j-i)L(当|i-j|b时),address(a34)=1+（3(22+1)+4-3)1=17,4.5稀疏矩阵如果一个矩阵中很多元素的值为零，即零元素的个数远远大于非零元素的个数时，称该矩阵为稀疏矩阵。4.5.1稀疏矩阵类的定义ADTspmatrix数据对象D：具有相同类型的数据元素构成的有限集合；数据关系R：D中的每个元素均位于2个向量中，每个元素最多具有2个前驱结点和2个后继结点，且D中零元素的个数远远大于非零元素的个数；稀疏矩阵的基本运算如下：（1）Createspmatrix(A),（2）compressmatrix(A,B)（3）Destroyspmatrix(A)（4）Printspmatrix(A)（5）Copyspmatrix(A,B)（6）Addspmatrix(A,B,C)（7）Subspmatrix(A,B,C)（8）Multspmatrix(A,B,C)（9）Transpmatrix(B,C)（10）locatespmatrix(A,x,rowx,colx)ADTspmatrix,4.5.2稀疏矩阵的顺序存储及其实现稀疏矩阵的顺序存储方法包括：三元组表示法、带辅助行向量的二元组表示法和伪地址表示法，其中以三元组表示法最常用，故在此主要介绍稀疏矩阵的三元组表示。在三元组表示法中，稀疏矩阵的每个非零元素可以采用如下形式表示：(i,j,value)其中i表示非零元素所在的行号，j表示非零元素所在的列号，