字符串与数组课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 字符串和数组,第4章 字符串和数组,一、字符串,存储方式（,1,）,一个由多个字符构成以零,(0),结尾的线性表就是字符串。,C,语言中没有字符串数据类型。,C,语言中字符串被存储在字符型数组中，这个数组可以静态定义，也可动态分配。,2,堆存储：利用一块连续的内存来存放字符串的存储结构,define MAXSIZE 100,char str1MAXSIZE+1;,/*,静态定义的字符数组，可容纳最大字符串长度是,MAXSIZE*/,char *pstr=NULL;,/*,字符指针，将指向存放字符串的内存*,/,int len;,scanf(“%d”,/*,获得字符串的长度*,/,pstr=(char *)malloc(len+1);,/*,根据字符串的长度分配一块内存*,/,一、字符串存储方式（1）一个由多个字符构成以零(0,一、字符串,存储方式（,2,）,块链存储,typedef struct strnode,char *block;,/*,根据需要动态分配的内存，存放一段字符串*,/,int size;,/*block,所指内存的大小*,/,struct strnode *next;,/*,指向下一段字符串*,/,STRNODE,*STRNODEPTR,*BLOCKLINKSTR;,3,一、字符串存储方式（2）块链存储3,一、字符串,简单模式匹配,(1),【,任务描述,】,已知一字符串,S,和字符串,T,，请确定字符串,T,在,S,中的位置，即字符串,T,的首字母在字符串,S,中的下标值。这里字符串,S,被称为主串，,T,被称为子串，又称为模式串。通常情况下，,S,串的长度比,T,大。,【,算法思想,】,以,pos,作为,S,串的下标。设,T,串的长度是,lent,。,pos,从,0,开始从左向右扫描字符串,S,，检查以,Spos,为起点的长度为,lent,的子串是否与,T,串完全相同。,如果完全相同，则意味着匹配成功，返回,pos,值；,如果不同，说明匹配失败，需要将,pos,向后移动一个单元，继续检查以,Spos,为起点的长度为,lent,的子串是否与,T,串完全相同。,这样循环反复，直到匹配成功或者以,Spos,为起点的子串长度不够为止。,4,一、字符串简单模式匹配(1)【任务描述】已知一字符串S和,一、字符串,简单模式匹配,(2),int StrIndex(char *s,char *t),/*,返回,t,在,s,中的位置，找不到,t,，则返回,-1*/,int i,j;,int pos=0;,/*,匹配的起点*,/,while(1),i=pos;j=0;,while(si&tj&si=tj),/*,匹配循环*,/, i+;,j+;,if(tj=0)return pos;,/*,匹配成功*,/,else if(si=0) return -1;,/*,匹配到了主串的末尾还没有成功*,/,else pos+;,/*,匹配的起点向后移动一个单元，重新匹配*,/,/while(1),时间复杂度：,5,一、字符串简单模式匹配(2)int StrIndex(,一、字符串,*,模式匹配的,KMP,算法,(1),简单匹配算法的最大问题是：,每次匹配失败时，,S,串要回到,Spos+1,处，而,T,串要回到,T0,处，从头开始比较。,下面的例子蕴含着改进的空间,已知主串是：,aabcdabcdabceab,模式串是：,abcdabce“,KMP,算法的基本思想：,只要发现,SiTj,时，,i,保持不动，,j,跳到,k,处,(,滑动,T,串,),，直到,k,是,-1,时，,i,才向右移动,1,位。,k,被称为,j,的,next,值，即,k=next(j),。,j,跳到,k,处的条件是：,k,是,T,串在,j,处的自身最大重复子串的长度。,6,K,值的真正含义：,是子串,T0.j-1,自身重复子串,T0.k-1,的长度,特点：有重复子串,一、字符串*模式匹配的KMP算法(1)简单匹配算法的最大,一、字符串,*,模式匹配的,KMP,算法,(2),关键是,next(j),如何求解,next(j),表达的是,T,串自身的特征，与,S,串无关,next,函数的数学定义,next(j),函数值的求解算法,已知,k=next(j),，说明,T0.j-1,之间最大重复子串的长度是,k,。下面的循环可以求出,next(j+1),的值：,比较,Tj,和,Tk,，如果,Tj=Tk,，那么,T0.j,之间最大重复子串的长度就是,k+1,，也就是说,next(j+1)=k+1,，求值完毕；,如果,Tj Tk,，我们只能在,T0.k-1,内寻找最大重复子串。,T0.k-1,最大重复子串长度是,next(k),，这时设定,k=next(k),，也就是说，,k,回退到自己的,next,值处。我们再次比较,Tj,和,Tk,，即转到步骤。,7,因为,next,值只和,T,串内容有关，,一旦,T,串确定，就可以计算出所有,next,值，,并用一个数组保存，以供字符串匹配时使用。,一、字符串*模式匹配的KMP算法(2)关键是next(j,一、字符串,*,模式匹配的,KMP,算法,(2),关键是,next(j),如何求解,next(j),表达的是,T,串自身的特征，与,S,串无关,next,函数的数学定义,next(j),函数值的求解算法,已知,k=next(j),，说明,T0.j-1,之间最大重复子串的长度是,k,。下面的循环可以求出,next(j+1),的值：,比较,Tj,和,Tk,，如果,Tj=Tk,，那么,T0.j,之间最大重复子串的长度就是,k+1,，也就是说,next(j+1)=k+1,，求值完毕；,如果,Tj Tk,，我们只能在,T0.k-1,内寻找最大重复子串。,T0.k-1,最大重复子串长度是,next(k),，这时设定,k=next(k),，也就是说，,k,回退到自己的,next,值处。我们再次比较,Tj,和,Tk,，即转到步骤。,8,一、字符串*模式匹配的KMP算法(2) 关键是next,一、字符串,*,模式匹配的,KMP,算法,(3),void NextVal(char *T,int *next),/*,求模式串,T,各单元的,next,值*,/, int j,k,len;,next0=-1;,j=0;,len=strlen(T);,while(j=0&Tj!=Tk),k=nextk;,/*k,回退到自己的,next,值处，重复子串的长度变小*,/,nextj+1=k+1;,/*,无论是,k=-1,还是,Tj=Tk,nextj+1,的值都是,k+1*/,j+;,/*,准备推算下一个,next,值*,/,9,一、字符串*模式匹配的KMP算法(3)void Nex,一、字符串,*,模式匹配的,KMP,算法,(4),#define MAXSIZE 50,int nextMAXSIZE;,int StrIndexKMP(char *S, char *T),/*,返回,T,在,S,中的位置，查找失败，返回,-1*/, int i=0, j=0;,NextVal(T,next);,/*,计算,T,串的,next,值*,/,while(Si!=0&Tj!=0),/*,如果没到字符串末尾，就循环继续匹配*,/, if(Si=Tj),/*i,和,j,都向后移动一个单元*,/, i+; j+;,else, j=nextj;,/*,匹配失败，,j,滑动到自己的,next,值处*,/,if(j=-1),/*,说明滑动之前,j,已经是,0,，需要将,i,向后移动，同时置,j,为,0*/, i+; j=0; ,/else,/*,属于,while,语句*,/,if(Tj=0)return i-j;,/*,匹配成功，返回位置*,/,else return -1;,/*,查找失败*,/,10,一、字符串*模式匹配的KMP算法(4)#define M,解疑,11,0,1,2,3,4,5,6,7,next,-1,0,0,0,0,1,2,3,0,1,2,3,4,5,6,7,8,9,10,解疑1101234567next-1000012301234,二、数组与矩阵,数组的定义,#define N 10,#define M 20,#define P 10,elemtype aN;,/*,定义了一个,N,个单元的一维数组*,/,假设,a0,的地址是,Loc,，,elemtype,数据类型的大小是,S(,字节,),，那么数组单元,ai,的地址就是,:,Loc+iS,。,elemtype bMN;,/*,定义了一个,MN,个单元的二维数组*,/,假设,b00,的地址是,Loc,，那么数组单元,bij,的前面一共有,i,行（,iN,个）单元，外加,j,个单元，它的地址就是：,Loc+(iN+j)S,12,二、数组与矩阵数组的定义#define N 1012,二、数组与矩阵,矩阵的压缩存储,(1),1,特殊矩阵之,三角矩阵,的压缩存储,13,三角矩阵,Aij,和数组,Bk,的关系：,上三角矩阵：,k=(N+(N-1)+(N-(i-1)+(j-i)=i(2N-i+1)/2+j-I (ji),下三角矩阵：,k=(1+2+3+i)+j=i(i+1)/2+j (ij),二、数组与矩阵矩阵的压缩存储(1)1特殊矩阵之三角矩阵,二、数组与矩阵,矩阵的压缩存储,(2),2,特殊矩阵之,对称矩阵,的压缩存储，按照三角矩阵的方式,N,阶矩阵，存在,Aij=Aji,3,特殊矩阵之,带状矩阵,的压缩存储,N,阶矩阵，只有主对角线和它的上下两条对角线上有数据，其他位置都是,0,或者某个固定常量。,k=(i3-1)+(j-(i-1)=2i+j,14,二、数组与矩阵矩阵的压缩存储(2)2特殊矩阵之对称矩阵,二、数组与矩阵,矩阵的压缩存储,(3),4,特殊矩阵之,稀疏矩阵,的压缩存储,在一个,MN,的矩阵中，非零元素的个数是,T,，我们将 称为稀疏因子。通常认为，当稀疏因子小于等于,0.05,时，这个矩阵就称为稀疏矩阵。,稀疏矩阵的,顺序存储,#define MAXSIZE 500,typedef struct,int i,j;,/*,在矩阵中的位置下标*,/,elemtype v;,/*,非零元素*,/,TRIPLE;,/*,三元组*,/,typedef struct,TRIPLE dataMAXSIZE;,/*,三元组数组*,/,int rnum,cnum,sum;,/*,行数、列数、非零元素的个数*,/,TRIPLEMATRIX;,15,二、数组与矩阵矩阵的压缩存储(3)4特殊矩阵之稀疏矩阵,二、数组与矩阵,矩阵的压缩存储,(4),下面的算法创建一个顺序存储结构的稀疏矩阵：,void InputData(TRIPLEMATRIX *m), int count; TRIPLE t;,/*,开始输入稀疏矩阵的行数、列数和非零元素的个数*,/,scanf(%d,%d,%d,count=0;,while(1),scanf(%d,%d,%d,/*,获取三元组数据，要求按行序输入*,/,if(t.i=0&t.irnum&t.j=0&t.jcnum),/*,三元组数据合法*,/, m-datacount=t;,count+;,/*,计数器增,1*/,if(count=m-sum) break;,/*,所有数据都输入完毕*,/,else break;,/*,遇到非法输入*,/,16,二、数组与矩阵矩阵的压缩存储(4)下面的算法创建一个顺序,二、数组与矩阵,矩阵的压缩存储,(5),4,特殊矩阵之,稀疏矩阵,的压缩存储,稀疏矩阵的,十字链表存储,将所有同一行的非零元素按列序链接，所有同一列的非零元素按行序链接。这样，同一个三元组单元同时存在于行链和列链两个链表中。,typedef struct crsnode_tag,int i,j; elemtype v;,/*,三元组数据*,/,struct crsnode_tag * right, * down;,/*,行链指针和列链指针，,right,指向同一行下一列非零元素，,down,指向同一列下一行非零元素*,/,CROSSNODE,* CROSSNODEPTR;,/*,定义十字链表结点及其指针*,/,typedef struct,CROSSNODEPTR rhead,chead;,/*,指向行链数组和列链数组*,/,int rnum,cnum,sum;,/*,行数、列数、非零元素的个数*,/,CROSSLINKLIST;,17,二、数组与矩阵矩阵的压缩存储(5)4特殊矩阵之稀疏矩阵,二、数组与矩阵,矩阵的压缩存储,(6),1,初始化十字链表,int InitCrossLinklist(CROSSLINKLIST *m,int row,int col,int sum),/*,初始化一个十字链表，成功则返回,1,，否则返回,0*/,int i;,/*,根据行数和列数分配相应数量的行链和列链的表头结点*,/,m-rhead=(CROSSNODEPTR)malloc(row*sizeof(CROSSNODE);,m-chead=(CROSSNODEPTR)malloc(col*sizeof(CROSSNODE);,if(m-rhead=NULL|m-chead=NULL) return 0; /*,分配失败*,/,for(i=0;irheadi.right=NULL;,/*,将所有行链设为空链*,/,for(i=0;icheadi.down=NULL;,/*,将所有列链设为空链*,/,m-rnum=row; m-cnum=col; m-sum=sum;,/*,设置行数、列数和非零元素的个数*,/,return 1;,18,二、数组与矩阵矩阵的压缩存储(6)1初始化十字链表18,二、数组与矩阵,矩阵的压缩存储,(7),2.,建立一个十字链表的稀疏矩阵,void InputData(CROSSLINKLIST *m),/*,建立一个存储数据的十字链表*,/, int len,count; CROSSNODEPTR p,q; int i,j;,elemtype v; int row,col,sum;,scanf(%d,%d,%d,/*,获取行数、列数和非零元素个数*,/,if(!InitCrossLinklist(m,row,col,sum),/*,初始化十字链表*,/, printf(no enough memoryn); exit(0); ,count=0;,/*,计数器清零*,/,while(1), scanf(%d,%d,%d,/*,输入三元组数据*,/,if(i=0&irnum&j=0&jcnum),/*,三元组数据合法*,/, p=(CROSSNODEPTR)malloc(sizeof(CROSSNODE);,if(!p),/*,分配失败*,/,printf(no enough memoryn); return; ,p-i=i; p-j=j; p-v=v;,/*,设置三元组结点,p,的数据域*,/,19,二、数组与矩阵矩阵的压缩存储(7)2.建立一个十字链表的,二、数组与矩阵,矩阵的压缩存储,(8),/*,开始按列序插入行链，读者应该很熟悉操作细节了*,/,q=,while(q-right!=NULL&q-right-jright;,p-right=q-right; q-right=p;,/,在行链尾插入结点,p,/*,开始按行序插入列链*,/,q=,while(q-down!=NULL&q-down-idown;,p-down=q-down; q-down=p;,count+; if(count=m-sum)break;,/*,数据输入完毕*,/,else,/*,三元组数据非法*,/, printf(illegal input datan); break; ,/while,20,二、数组与矩阵矩阵的压缩存储(8) /*开始按列,二、数组与矩阵,矩阵的压缩存储,(9),3,销毁十字链表,void DestroyCrossLinklist(CROSSLINKLIST *m),/*,销毁一个十字链表*,/, CROSSNODEPTR p; int i;,for(i=0;irnum;i+),/*,沿着行链，释放链上所有的三元组结点*,/,while(m-rheadi.right!=NULL),p=m-rheadi.right;,m-rheadi.right=p-right;,free(p);,free(m-rhead); free(m-chead);,/*,释放行链和列链表头结点数组*,/,m-rhead=m-chead=NULL;,m-rnum=0; m-cnum=0; m-sum=0;,/*,其他成员设置成安全值*,/,21,二、数组与矩阵矩阵的压缩存储(9)3销毁十字链表21,二、数组与矩阵,稀疏矩阵的转置,(1),转置的含义：,Aij,和,Aji,交换位置，则,M*N,矩阵转置后变成,N*M,矩阵,三元组数组的转置算法,遍历三元组数组，记下这个稀疏矩阵中每列的非零元素个数，存储数组,count,推算出转置后矩阵的各三元组数据的正确的存储位置 ，存储位置存放在数组,rpos,中,再次遍历三元组数组，对每个数据单元进行转置，按照,rpos,中的数据存放到新的三元组数组中,0,1,2,3,4,5,转置前,转置后,转置后（无序）,二、数组与矩阵稀疏矩阵的转置(1)转置的含义：Ai,练习：,书,101,页，练一练,4.3,23,练习：23,二、数组与矩阵,稀疏矩阵的转置,(2),TRIPLEMATRIX TransposeMatrix(TRIPLEMATRIX m),/*,返回矩阵,m,的转置矩阵*,/,int *count,*rpos; TRIPLEMATRIX T; int k,i,r;,count=(int *)malloc(sizeof(int)*um);,/*counti,将存放矩阵,m,第,i,列非零元素的个数*,/,rpos=(int *)malloc(sizeof(int)*um);,/*rposi,将存放转置后的矩阵行非零元素的存储起点*,/,if(count=NULL|rpos=NULL), printf(no enough memoryn); return; ,for(i=0;ium;i+) counti=0;,/*,计数器清零*,/,for(i=0;im.sum;i+),/*,遍历三元组数组，记录各列非零元素的个数*,/,k=m.datai.j; countk+; ,rpos0=0;,/*,第,0,行的存储起点是,0*/,for(i=1;ium;i+),/*,计算各行非零元素的存储起点*,/,rposi=rposi-1+counti-1;,24,二、数组与矩阵稀疏矩阵的转置(2)TRIPLEMATRI,二、数组与矩阵,稀疏矩阵的转置,(3),T.sum=m.sum; T.rnum=um; T.cnum=m.rnum;,/*,行、列转置，非零元素总量不变*,/,for(i=0;im.sum;i+),k=m.datai.j;,r=rposk;,/*r,是转置后三元组数据的正确的存储位置*,/,T.datar.i=m.datai.j;,T.datar.j=m.datai.i;,T.datar.v=m.datai.v;,/*,三元组转置*,/,rposk+;,/*,存储起点增,1,，是下一个同一行三元组数据的存储位置*,/,free(count); free(rpos); return T;,25,二、数组与矩阵稀疏矩阵的转置(3) T.sum=m.s,二、数组与矩阵,稀疏矩阵的乘法,(1),矩阵相乘的含义,已知一个,MN,的矩阵,A,和,NP,的矩阵,B,，令,C=AB,，则,C,是一个,MP,的矩阵，并且：,二维数组的矩阵乘法,void MatrixMulti(int AMN,int BNP,int CMP), int i,j,k;,for(i=0;iM;i+),for(j=0;jP;j+), Cij=0;,/*,矩阵,C,的数据单元清零*,/,for(k=0;krnum,B-cnum,0);,/*,初始化矩阵,C,的十字链表*,/,for(i=0;irnum;i+),/*,遍历矩阵,A,的所有的行链*,/, p=A-rheadi.right;,while(p!=NULL),/*,找到非零元素结点,p,，某个,(i,j,v)*/,k=p-j;,/*k,是,Aij,的列号,j,也就是矩阵,B,的行号*,/,q=B-rheadk.right;,while(q!=NULL),/*,遍历矩阵,B,的第,k,行行链，找到所有非零元素结点,q*/, j=q-j;,v=p-v*q-v;,/*,计算,AikBkj*/,二、数组与矩阵稀疏矩阵的乘法(2)稀疏矩阵十字链表的矩阵,二、数组与矩阵,稀疏矩阵的乘法,(3),/*,试图将,(i,j,v),插入到矩阵,C,中*,/,pC=,while(pC-right!=NULL&pC-right-jright;,if(pC-right!=NULL&pC-right-j=j),pC-right-v+=v;,/*,原行链中有,(i,j,v),结点，执行累加*,/,else,/*,否则新生成结点,(i,j,v),结点,qC,，插入到,pC,的后面*,/, qC=(CROSSNODEPTR)malloc(sizeof(CROSSNODE);,if(qC=NULL) printf(no enough memoryn); return; ,qC-i=i; qC-j=j; qC-v=v;,qC-right=pC-right; pC-right=qC;,/*,再将结点,qC,插入到列链中*,/,pC=,while(pC-down!=NULL&pC-down-idown;,qC-down=pC-down; pC-down=qC;,C-sum+;,/*,矩阵非零元素个数增,1*/,/*,属于,else,语句 *,/,29,二、数组与矩阵稀疏矩阵的乘法(3) /*试图将(i,二、数组与矩阵,稀疏矩阵的乘法,(4),/*,寻找矩阵,B,第,k,行的下一个非零元素*,/,q=q-right;,/while(q),/*,寻找矩阵,A,第,i,行的下一个非零元素*,/,p=p-right;,/while(p),/for,/*,下面清除十字链表中的零元素结点*,/,for(i=0;irnum;i+),/*,检查所有的行链*,/, p=,while(p-right!=NULL),/*,遍历行链，摘除所有的零元素结点*,/, if(p-right-v=0),/*,发现零元素结点，从行链中摘除*,/,p-right=p-right-right;,else p=p-right;,/*,否则,p,向后移动*,/,30,二、数组与矩阵稀疏矩阵的乘法(4) /*寻找矩阵,二、数组与矩阵,稀疏矩阵的乘法,(5),for(i=0;icnum;i+),/*,检查所有的列链*,/,p=,while(p-down!=NULL),/*,遍历列链，摘除零元素结点*,/,if(p-down-v=0),/*,发现零元素结点，这时它已经从行链中被摘除了*,/,q=p-down;,p-down=q-down;,free(q);,/*,摘除结点并释放内存*,/,C-sum-;,/*,这时矩阵非零元素个数减,1*/,else p=p-down;,31,二、数组与矩阵稀疏矩阵的乘法(5)for(i=0;iC,导航图,(1),字符串和数组,字符串,数组与矩阵,简单模式匹配,KMP,算法,矩阵的,压缩存储,矩阵的转置,和乘法,三元组数组,的转置,十字链表的,矩阵乘法,特殊矩阵的,压缩存储,稀疏矩阵的,压缩存储,32,导航图(1)字符串和数组字符串数组与矩阵简单模式匹配KMP算,导航图,(2),字符串和数组,字符串,数组与矩阵,简单模式匹配,KMP,算法,矩阵的,压缩存储,矩阵的转置,和乘法,三元组数组,的转置,十字链表的,矩阵乘法,特殊矩阵的,压缩存储,稀疏矩阵的,压缩存储,33,导航图(2)字符串和数组字符串数组与矩阵简单模式匹配KMP算,导航图,(3),字符串和数组,字符串,数组与矩阵,简单模式匹配,KMP,算法,矩阵的,压缩存储,矩阵的转置,和乘法,三元组数组,的转置,十字链表的,矩阵乘法,特殊矩阵的,压缩存储,稀疏矩阵的,压缩存储,34,导航图(3)字符串和数组字符串数组与矩阵简单模式匹配KMP算,导航图,(4),字符串和数组,字符串,数组与矩阵,简单模式匹配,KMP,算法,矩阵的,压缩存储,矩阵的转置,和乘法,三元组数组,的转置,十字链表的,矩阵乘法,特殊矩阵的,压缩存储,稀疏矩阵的,压缩存储,35,导航图(4)字符串和数组字符串数组与矩阵简单模式匹配KMP算,导航图,(5),字符串和数组,字符串,数组与矩阵,简单模式匹配,KMP,算法,矩阵的,压缩存储,矩阵的转置,和乘法,三元组数组,的转置,十字链表的,矩阵乘法,特殊矩阵的,压缩存储,稀疏矩阵的,压缩存储,36,导航图(5)字符串和数组字符串数组与矩阵简单模式匹配KMP算,导航图,(6),字符串和数组,字符串,数组与矩阵,简单模式匹配,KMP,算法,矩阵的,压缩存储,矩阵的转置,和乘法,三元组数组,的转置,十字链表的,矩阵乘法,特殊矩阵的,压缩存储,稀疏矩阵的,压缩存储,37,导航图(6)字符串和数组字符串数组与矩阵简单模式匹配KMP算,导航图,(7),字符串和数组,字符串,数组与矩阵,简单模式匹配,KMP,算法,矩阵的,压缩存储,矩阵的转置,和乘法,三元组数组,的转置,十字链表的,矩阵乘法,特殊矩阵的,压缩存储,稀疏矩阵的,压缩存储,38,导航图(7)字符串和数组字符串数组与矩阵简单模式匹配KMP算,导航图,(8),字符串和数组,字符串,数组与矩阵,简单模式匹配,KMP,算法,矩阵的,压缩存储,矩阵的转置,和乘法,三元组数组,的转置,十字链表的,矩阵乘法,特殊矩阵的,压缩存储,稀疏矩阵的,压缩存储,39,导航图(8)字符串和数组字符串数组与矩阵简单模式匹配KMP算,