资源描述
,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,c语言字符串数组和特殊矩阵,c语言字符串数组和特殊矩阵c语言字符串数组和特殊矩阵 4.1 字符串 4.1.1 字符串的基本概念 字符串是由零个或多个字符构成的有限序列,一般可表示成如下形式:“c1 c2 ”(n0)串中所含字符的个数n称为字符串的长度;当n=0时,称字符串为空串。串中任意个连续的字符构成的子序列称为该串的子串,包含子串的串称为主串。通常称字符在字符串序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。例如:T=“STUDENT”,S=“UDEN”,则S是T的子串,S在T中出现的位置为3。,4.1 字符串 4.1.1 字符串的基本概念,字符串是由零个或多个字符构成的有限序列,一般可表示成如下形式:,“c,1,c,2,c,3,.c,n,”(n,0),串中所含字符的个数,n,称为字符串的长度;当,n=0,时,称字符串为空串。串中任意个连续的字符构成的子序列称为该串的子串,包含子串的串称为主串。通常称字符在字符串序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。例如:,T=“STUDENT”,,,S=“UDEN”,则,S,是,T,的子串,,S,在,T,中出现的位置为,3,。,两个字符串相等,当且仅当两个串的长度相等,并且各个对应位置的字符都相等。例如:T1=“REDROSE”T2=“RED ROSE”由于T1和T2的长度不相等,因此T1T2。若 T3=“STUDENT”T4=“STUDENS”虽然T3和T4的长度相等,但两者有些对应的字符不同,因而T3T4。值得一提的是,若S=“”,此时S由一个空格字符组成,其长度为1,它不等价于空串,因为空串的长度为0。,4.1.2 字符串类的定义,ADT string 数据对象D:由零个或多个字符型的数据元素构成的有限集合;数据关系R:|其中a,i,a,i+1,D,i=1,2,n-1 字符串的基本操作如下:,(,1,),Strcreate(S),(,2,),Strassign(S,T),(,3,),Strlength(S),(,4,),Strempty(S),(,5,),Strclear(S),(6)Strcompare(S,1,,S,2,),(,7,),Strconcat(S,1,,,S,2,),(,8,),Substring(S,i,len),(,9,),Index(P,T),(,10,),Strinsert(S,i,T),(,11,),Strdelete(S,i,len),(,12,),Replace(S,T,1,T,2,),(,13,),Strdestroy(S)ADT string,4.1.3 字符串的存储及其实现,1、串的顺序存储及其部分运算的实现串的顺序存储使用数组存放,具体类型定义如下:#define MAXSIZE 100 typedef struct char strMAXSIZE;int length;seqstring;,(1)插入运算strinsert(S,i,T),void strinsert(seqstring*S,int i,seqstring T)int k;if(iS-length+1|S-length+T.lengthMAXSIZE)printf(connot insertn“);else for(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)void strdelete(seqstring*S,int i,int len)int k;if(iS-length|i+len-1S-length)printf(“cannot deleten”);else for(k=i-1+len;klength;k+)S-strk-len=S-strk;S-length=S-length-len;S-strS-length=0;,(3)连接运算strconcat(S,1,S,2,),seqstring*strconcat(seqstring S1,seqstring S2)int i;seqstring*r;if (S1.length+S2.lengthMAXSIZE)printf(cannot concate);return(NULL);else r=(seqstring*)malloc(sizeof(seqstring);for(i=0;istri=S1.stri;for(i=0;istr S1.length+i=S2.stri;r-length=S1.length+S2.length;r-strr-length=0;return(r);,(4)求子串运算substring(S,i,len),seqstring*substring(seqstring S,int i,int len)int k;seqstring*r;if(iS.length|i+len-1S.length)printf(“errorn”);return(NULL);else r=(seqstring*)malloc(sizeof(seqstring);for(k=0;kstrk=S.stri-1+k;r-length=len;r-strr-length=0;return(r);,2 串的链接存储及其部分运算的实现 串的链接存储采用单链表的形式实现,其中每个结点的定义如下:typedef struct node char data;struct node*next;linkstrnode;typedef linkstrnode*linkstring;例如,串S=“abcde”,其链接存储结构如下图所示:,a,b,c,d,e,S,(1)创建字符串运算strcreate(S),void strcreate(linkstring*S)char ch;linkstrnode*p,*r;*S=NULL;r=NULL;while(ch=getchar()!=n)p=(linkstrnode*)malloc(sizeof(linkstrnode);p-data=ch;if(*S=NULL)*S=p;else r-next=p;r=p;/*r移向当前链接串的最后一个字符的位置*/if(r!=NULL)r-next=NULL;/*处理表尾结点指针域*/,(2)插入运算strinsert(S,i,T),void strinsert(linkstring*S,int i,linkstring T)int k;linkstring p,q;p=*S,k=1;while(p ,(3)删除运算strdelete(S,i,len),void strdelete(linkstring*S,int i,int len)int k;linkstring p,q,r;p=*S,q=null;k=1;/*用p查找S的第i个元素,q始终跟踪p的前驱*/while(p,else if(!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(S,1,S,2,)void strconcat(linkstring*S1,linkstring S2)linkstring p;if(!(*S1)*S1=S2;return;else if(S2)/*S1和S2均不为空串的情形*/p=*S1;/*用p查找S1的最后一个字符的位置*/while(p-next)p=p-next;p-next=S2;/*将串S2连接到S1之后*/,(5)求子串运算substring(S,i,len),linkstring substring(linkstring S,int i,int len)int k;linkstring p,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:t,1,t,2,t,m,t,n,模式p:p,1,p,2,p,m,如果t,1,=p,1,t,2,=p,2,.t,m,=p,m,,则模式匹配成功;否则,将p向右移动一个字符的位置,重新用p中的字符从头开始与t中相对应的字符依次比较,即:t,1,t,2,t,3,t,m,t,m+1,t,n,p,1,p,2,p,m-1,p,m,如此反复,直到匹配成功或者p已经移到使t中剩下的字符个数小于p的长度的位置,此时意味着模式匹配失败,表示t中没有子串与模式p相等,我们约定返回-1代表匹配失败。朴素模式匹配算法的具体实现如下:,int index(seqstring p,seqstring t)int i,j,succ;i=0;succ=0;/*succ为匹配成功的标志*/while(it.length-p.length+1),4.2.2 快速模式匹配算法(KMP算法),首先我们来分析下图所示的情况:t,0,t,1,t,2,t,k,t,k+1,t,k+2,t,r-2,t,r-1,t,r,.p,0,p,1,p,2,p,i-2,p,i-1,p,i.,(4-1)t,0,t,1,t,2,t,k,t,k+1,t,k+2,t,r-2,t,r-1,t,r,.p,0,p,1,p,i-2,p,i-1,p,i,(4-2),t,0,t,1,t,2,t,k,t,k+1,t,k+2,t,r-2,t,r-1,t,r,.,p,0,p,i-3,p,i-2,p,i-1,p,i,(,4-3,),(4-1)式表明此次匹配从p,0,与t,k,开始比较,当比较到p,i,与t,r,时出现不等情况,于是将模式右移一位,变成(4-2)所示的状态,若此次比较成功,则必有p,0,=t,k+1,,p,1,=t,k+2,,p,i-2,=t,r-1,,且p,i-1,p,i,;而根据(4-1)的比较结果有:p,1,=t,k+1,,p,2,=t,k+2,,p,i-1,=t,r-1,,因此有:p,0,=p,1,,p,1,=p,2,,p,i-2,=p,i-1,。这个性质说明在模式p中p,i,之前存在一个从p,0,开始长度为i-1的连续序列p,0,p,1,p,i-2,和以p,i-1,为结尾,长度同样为i-1的连续序列p,1,p,2,p,i-1,其值对应相等,即:p,0,p,1,p,2,p,i-2,p,i-1,p,i.,简记为:p,0,p,i-2,=p,1,p,i-1,称模式p中p,i,之前存在长度为i-1的真前缀和真后缀的匹配。,反之,若在(4-1)所示的状态下,模式p中p,i,之前存在长度为i-1的真前缀和真后缀的匹配,即p,0,p,i-2,=p,1,p,i-1,且p,i-1,p,i,;当p,i,与t,r,出现不等时,根据前面已比较的结果p,1,=t,k+1,,p,2,=t,k+2,,p,i-1,=t,r-1,,于是可得p,0,=t,k+1,,p,1,=t,k+2,,p,i-2,=t,r-1,,因此接下来只需从p,i-1,与t,r,开始继续后继对应字符的比较即可。再假设在(4-1)所示的状态下,模式右移一位成为状态(4-2)后,匹配仍然不成功,说明p,0,p,i-2,p,1,p,i-1,或p,i-1,=p,i,,于是模式再右移一位,成为状态(4-3),若此次匹配成功,仿照上述分析,必有:p,0,p,1,p,2,p,i-3,p,i-2,p,i-1,p,i.,即:p,0,p,i-3,=p,2,p,i-1,说明模式p中p,i,之前存在长度为i-2的真前缀和真后缀的匹配。由(4-3)表明,在(4-1)所示的状态下,若模式p中p,i,之前最长真前缀和真后缀匹配的长度为i-2,当p,i,与t,r,出现不等时,接下来只需从p,i-2,与t,r,开始继续后继对应字符的比较。考虑一般情况。,在进行模式匹配时,若模式p中p,i,之前最长真前缀和真后缀匹配的长度为j,当p,i,t,r,时,则下一步只需从p,j,与t,r,开始继续后继对应字符的比较,而不应该将模式一位一位地右移,也不应该反复从模式的开头进行比较。这样既不会失去任何匹配成功的机会,又极大地加快了匹配的速度。,根据上述分析,在模式匹配过程中,每当出现p,i,t,r,时,下一次与t,r,进行比较的p,j,和模式p中p,i,之前最长真前缀和真后缀匹配的长度密切相关;而模式p中p,i,之前最长真前缀和真后缀匹配的长度只取决于模式p的组成,与正文无关。于是我们可以针对模式p定义一个数组nextm,其中nexti表示当p,i,t,r,时,下一次将从p,nexti,与t,r,开始继续后继对应字符的比较。显然,nexti的值与模式p中p,i,之前最长真前缀和真后缀匹配的长度密切相关。下面考虑如何根据模式p的组成求数组next的值。我们规定:next0=-1这表明当p,0,t,r,时,将从p,-1,与t,r,开始继续后继对应字符的比较;然而p,-1,是不存在的,我们可以将这种情况理解成下一步将从p,0,与t,r+1,开始继续后继对应字符的比较。,以下假设next0,next1,nexti的值均已求出,现要求nexti+1的值。由于在求解nexti时已得到p,i,之前最长真前缀和真后缀匹配的长度,设其值为j,即:p,0,p,1,p,2,p,i-j,.p,j-1,p,j,p,i-2,p,i-1,p,i,p,i+1,如果此时进一步有p,j,=p,i,,则p,i+1,之前最长真前缀和真后缀匹配的长度就为j+1,且nexti+1=j+1;反之,若p,j,p,i,,注意到,求p,i+1,之前最长真前缀和真后缀匹配问题本质上仍然是一个模式匹配问题,只是在这里模式和正文都是同一个串p而已。因此当p,j,p,i,时,应该检查p,nextj,与p,i,是否相等;若相等,则nexti+1=nextj+1;如仍然不相等,则再取p,nextnextj,与p,i,进行比较,直至要将p,-1,与p,i,进行比较为止,此时nexti+1=0。,以下给出了根据模式p的组成求数组next值的算法:void getnext(seqstring p,int next)int i,j;next0=-1;i=0;j=-1;while(ip.length)if(j=-1|p.stri=p.strj)+i;+j;nexti=j;else j=nextj;for(i=0;ip.length;i+)printf(%d,nexti);,试求以下串的next数组值:,例1、a b a a b c a c,Next数组值:-1 0 0 1 1 2 0 1,例2、a b a b a a b a b,Next数组值:-1 0 0 1 2 3 1 2 3,KMP算法基本思想如下:假设以i和j分别指示正文t和模式p中正待比较的字符,令i、j的初值为0;若在匹配过程中t,i,=p,j,,则i与j分别加1;否则i不变,而j退到nextj的位置继续比较(即j=nextj);若相等,则指针各自增加1;否则j再退到下一个nextj值的位置,依此类推,直至下列两种可能,:(1),一种是j退到某个next(next.nextj)时,t,i,与p,j,字符比较相等,则i、j指针各自增加1 后继续进行比较;(2)一种是j退到-1(即模式的第一个字符“失配”),此时需将正文指针i向右滑动一个位置,即从正文 的下一个字符t,i+1,起和模式p重新从头开始比较。,KMP算法的具体实现如下:int kmp(seqstring t,seqstring p,int next)int i,j;i=0;j=0;while(i2)维数组,可以依据上述规律类推。,4.3.2 数组类的定义,ADT array 数据对象D:具有相同类型的数据元素构成的有序集合;数据关系R:对于n维数组,其每一个元素均位于n个向量中,每个元素最多具有n个前驱结点和n个后继结点;数组的基本操作如下:,(,1)Initarray(A,n,index1,index2,index n)(2)Destroyarray(A),(,3,),Value(A,index1,index2,index n,x),(,4,),Assign(A,e,index1,index2,index n)ADT array,4.3.3 数组的顺序存储及实现,由于数组是由有限的元素构成的有序集合,数组的大小和元素之间的关系一经确定,就不再发生变化,因此数组均采用顺序存储结构实现,它要求一片连续的存储空间存储。多维数组数据元素的顺序存储有两种方式:,按行优先存储,按列优先存储,例如:对于二维数组Amn:a,00,a,01,a,0(n-1),a,10,a,11,a,1(n-1),A=a,(m-1)0,a,(m-1)1,a,(m-1)(n-1),若将A按行优先存储,其存储顺序为:a,00,,a,01,,a,0(n-1),a,10,a,11,,.a,1(n-1),,a,(m-1)0,,a,(m-1)1,,a,(m-1)(n-1),;而按列优先存储,其顺序为:a,00,,a,10,,a,(m-1)0,a,01,a,11,.a,(m-1)1,,a,0(n-1),.a,1(n-1),,a,(m-1)(n-1),。,对于数组,一旦确定了它的维数和各维的长度,便可以为它分配存储空间;当规定了数组元素的存储次序后,便可根据给定的一组下标值求得相应数组元素的存储位置。现假设数组中每个元素占用L个存储单元,若考虑按行优先存储方式,则上述A数组中任何一个元素a,ij,的存储位置可以按以下公式确定:address(a,ij,)=address(a,00,)+(in+j)L 若考虑按列优先的存储方式,数组中任何一个元素a,ij,存储位置的地址计算公式为:address(a,ij,)=address(a,00,)+(jm+i)L,多维数组的存储也和二维数组一样,存在两种存储方式:按行优先和按列优先。但由于多维数组中数据元素间的关系较二维数组复杂,因此数据元素的地址计算公式也相对复杂些,但两者所采用的原理是相同的。考虑n维数组的情形:datatype Ab,1,b,2,b,n,;其中b,1,、b,2,、b,n,为数组每一维的长度。仍假设每个元素占用L个单元,则n维数组A中任何一个元素Aj,1,j,2,j,n,在按行优先存储方式下的地址计算公式为:address(Aj,1,j,2,j,n,)=address(A000)+(b,2,b,3,b,n,j,1,+b,3,b,4,b,n,j,2,+b,n,j,n-1,+j,n,)L上式可以简写为:address(Aj,1,j,2,j,n,)=address(A000)+c,1,*j,1,+c,2,*j,2,+c,n,*j,n,其中c,n,=L,c,i-1,=b,i,c,i,1index1=b2;A-index2=b3;elements=b1 b2 b3;A-base=(datatype*)malloc(elementssizeof(datatype);if (!(A-base)return(0);A-c0=b2 b3;A-c1=b3;A-c2=1;return(1);,2、,访问数组元素值的运算value(A,i1,i2,i3,x,)int value(array A,int i1,int i2,int i3;datatype*x)int off;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),int assign(array*A,datatype e,int i1,int i2,int i3)int off;if(i1=A-index0|i2=A-index1|i3=A-index2)return(0);/*,处理下标非法的情况,*/off=i1,A-c0+i,2,A-c1+i,3,A-c2;*(A-base+off)=e;/*,赋值,*/return(1);,4.4 特殊矩阵 本节主要研究对称矩阵、三角矩阵和带状矩阵的压缩存储。所谓压缩存储即为:多个相同值的结点只分配一个存储空间,值为零的结点不分配空间。,4.4.1 对称矩阵的压缩存储,如果矩阵的行数和列数相等,则称该矩阵为方阵。若nn阶的方阵A满足:a,ij,=a,ji,(0in-1,0jn-1)则称矩阵A为对称矩阵。在对称矩阵中,几乎有一半元素的值是对应相等的。如果将A中所有元素进行存储,那将会造成空间的浪费,且n值越大,浪费将越严重。,对于对称矩阵压缩存储时只需存储对角线以上或对角线以下的部分,未存储的部分可以利用元素之间的对称性来访问。现考虑只存储对称矩阵A对角线以下的部分(即下标满足ij的数组元素a,ij,):,a,00,a,10,a,11,A=a,20,a,21,a,22,a,(n-1)0,.,a,(n-1)(n-1),若采用按行优先的存储方式,A进行压缩存储后任何一个元素a,ij,的地址计算公式为:address(a,00,)+(i*(i+1)/2+j)L 当ijaddress(a,ij,)=address(a,00,)+(j*(j+1)/2+i)L 当i j,4.4.2 三角矩阵的压缩存储,1、下三角矩阵,a,00,0 0 0 a,10,a,11,0 .0 A=a,20,a,21,a,22,.0,a,(n-1)0,a,(n-1)(n-1),仍考虑采用按行优先方式,A中下三角部分的任何一个元素a,ij,(ij)压缩存储后的地址计算公式为:address(a,ij,)=address(a,00,)+(i*(i+1)/2+j)L 当ij与对称矩阵不同的是,当ij时,a,ij,的值为0,其没有对应的存储空间。,4.4.3 带状矩阵的压缩存储,对于nn阶方阵,若它的全部非零元素落在一个以主对角线为中心的带状区域中,这个带状区域包含主对角线下面及上面各b条对角线上的元素以及主对角线上的元素,那么称该方阵为半带宽为b的带状矩阵。带状矩阵的特点是:对于矩阵元素a,ij,,若i-jb或j-ib,即|i-j|b,则a,ij,=0。b,条对角线,b,条对角线 主对角线,例、,20 3 72 0 0 0,14 25 30 45 0 0,11 14 35 42 5 0,0 16 20 26 10 28,0 0 7 15 8 3,0 0 0 29 16 55,带状矩阵进行压缩存储时,只存储带状部分内部的元素,对于带状区域以外的元素,即|i-j|b的a,ij,,均不分配存储空间。为了方便起见,我们规定按如下方法进行存储:除第一行和最后一行外,每行都分配2b+1个元素的空间,将带状区域中的元素存储于((2b+1)n-2b)L个存储单元之中,其中L为每个元素占用空间的大小。仍考虑采用按行优先的存储方式,于是可以得到带状区域中任何一个元素a,ij,的地址计算公式为:address(a,ij,)=address(a,00,)+(i,(2b+1)-b)+(j-i+b),L =address(a,00,)+(i,(2b+1)+j-i),L (当|i-j|b时),address(a,34,)=1+(3,(2,2+1)+4-3),1=17,4.5 稀疏矩阵 如果一个矩阵中很多元素的值为零,即零元素的个数远远大于非零元素的个数时,称该矩阵为稀疏矩阵。4.5.1 稀疏矩阵类的定义 ADT spmatrix 数据对象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)ADT spmatrix,4.5.2 稀疏矩阵的顺序存储及其实现,稀疏矩阵的顺序存储方法包括:三元组表示法、带辅助行向量的二元组表示法和伪地址表示法,其中以三元组表示法最常用,故在此主要介绍稀疏矩阵的三元组表示。在三元组表示法中,稀疏矩阵的每个非零元素可以采用如下形式表示:(i,j,value)其中i表示非零元素所在的行号,j表示非零元素所在的列号,value表示非零元素的值。采用三元组表示法表示一个稀疏矩阵时,首先将它的每一个非零元素表示成上述的三元组形式,然后按行号递增的次序、同一行的非零元素按列号递增的次序将所有非零元素的三元组表示存放到一片连续的存储单元中即可。,以下是稀疏矩阵A,76,及其对应的三元组表示。B 0 1 2 0 7 6 7 0 0 5 0 1 0,1 0 2 -5 0 0 0 2 0 0 2 0 4 1 3 0 0 0 0 0 3 1 3 2 0 0 0 0 0 0 4 2 0 3 12 0 0 0 0 0 5 4 0 12 0 0 0 0 0 4 6 5 5 4 0 0 21 0 0 0 7 6 2 21,稀疏矩阵A A的三元组表示,稀疏矩阵A及其对应的三元组表示矩阵B的数据类型定义如下:,typedef struct int data100100;/*存放稀疏矩阵的二 维数组*/int m,n;/*分别存放稀疏矩阵 的行数和列数*/matrix;typedef int spmatrix1003;,/*稀疏矩阵对应的三元组表示的类型*/,1、产生稀疏矩阵三元组表示的算法void compressmatrix(matrix A,spmatrix B)int i,j,k=1;for(i=0;iA.m;i+)for(j=0;j0)for(i=0;in;i+)xi=0;for(i=1;i=t;i+)xBi1=xBi1+1;/*统计B中每一列非零元素的个数*/*求矩阵C中每一行非零元素三元组的起始位置*/y0=1;for(i=1;in;i+)yi=yi-1+xi-1;,for(i=1;irow=m;p-col=n;s=mn?m:n;for(i=1;itag.next=p;p-row=p-col=0;p-down=p-right=p;hs-tag.next=h0;,for(i=1;irow=r;p-col=c;p-tag.val=v;q=hr;while(q-right!=hr,2、稀疏矩阵十字链表的查找算法int locatespmatrix(headspmatrix h,int x,int*rowx,int*colx)spmatrix p,q;p=h0-tag.next;while(p!=h0)q=p-right;while(p!=q)if(q-tag.val=x)*rowx=q-row;*colx=q-col;return(1);q=q-right;p=p-tag.next;/*准备进入下一行查找*/return(0);,谢谢,
展开阅读全文