1、第第4章章 字符串和数组字符串和数组一、字符串一、字符串存储方式（存储方式（1）一个由多个字符构成以零(0)结尾的线性表就是字符串。C语言中没有字符串数据类型。C语言中字符串被存储在字符型数组中，这个数组可以静态定义，也可动态分配。2 堆存储：利用一块连续的内存来存放字符串的存储结构堆存储：利用一块连续的内存来存放字符串的存储结构define MAXSIZE 100char str1MAXSIZE+1;/*静态定义的字符数组，可容纳最大字符串长度是MAXSIZE*/char*pstr=NULL;/*字符指针，将指向存放字符串的内存*/int len;scanf(“%d”,&len);/*获得字
2、符串的长度*/pstr=(char*)malloc(len+1);/*根据字符串的长度分配一块内存*/一、字符串一、字符串存储方式（存储方式（2）块链存储块链存储typedef struct strnode char*block;/*根据需要动态分配的内存，存放一段字符串*/int size;/*block所指内存的大小*/struct strnode*next;/*指向下一段字符串*/STRNODE,*STRNODEPTR,*BLOCKLINKSTR;My name is Yang Kaichengblock next3一、字符串一、字符串简单模式匹配简单模式匹配(1)【任务描述任务描述】已
3、知一字符串已知一字符串S S和字符串和字符串T T，请确定字符串，请确定字符串T T在在S S中的位置，即字符串中的位置，即字符串T T的首字母在字符串的首字母在字符串S S中的下标值。中的下标值。这里字符串这里字符串S S被称为主串，被称为主串，T T被称为子串，又称为模式串。被称为子串，又称为模式串。通常情况下，通常情况下，S S串的长度比串的长度比T T大。大。【算法思想算法思想】以以pospos作为作为S S串的下标。设串的下标。设T T串的长度是串的长度是lentlent。pospos从从0 0开始从左向右扫描字符串开始从左向右扫描字符串S S，检查以，检查以SposSpos为起点为
4、起点的长度为的长度为lentlent的子串是否与的子串是否与T T串完全相同。串完全相同。如果完全相同，则意味着匹配成功，返回如果完全相同，则意味着匹配成功，返回pospos值；值；如果不同，说明匹配失败，需要将如果不同，说明匹配失败，需要将pospos向后移动一个单元，继续向后移动一个单元，继续检查以检查以SposSpos为起点的长度为为起点的长度为lentlent的子串是否与的子串是否与T T串完全相同。串完全相同。这样循环反复，直到匹配成功或者以这样循环反复，直到匹配成功或者以SposSpos为起点的子串长度不够为起点的子串长度不够为止。为止。4一、字符串一、字符串简单模式匹配简单模式匹
5、配(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)时间复杂度：时间复杂度：)(mnO)(mnO5一、字符串一、字符串*模式匹配的模式匹配的KMP算法算法(1)简单匹配算法的
6、最大问题是：简单匹配算法的最大问题是：每次匹配失败时，每次匹配失败时，S串要回到串要回到Spos+1处，而处，而T串要回到串要回到T0处，从头开处，从头开始比较。始比较。下面的例子蕴含着改进的空间下面的例子蕴含着改进的空间已知主串是：已知主串是：aabcdabcdabceab模式串是：模式串是：abcdabce“KMP算法的基本思想：算法的基本思想：只要发现只要发现SiTjSiTj时，时，i i保持不动，保持不动，j j跳到跳到k k处处(滑动滑动T T串串)，直到，直到k k是是-1-1时，时，i i才向右移动才向右移动1 1位。位。k k被称为被称为j j的的nextnext值，即值，即k
7、=next(j)k=next(j)。j跳到跳到k处的条件是：处的条件是：k是是T串在串在j处的自身最大重复子串的长度。处的自身最大重复子串的长度。SaabcdabcdabceababcdabceTposijk jkjk i 大的重复子串大的重复子串6K值的真正含义：是子串T0.j-1自身重复子串T0.k-1的长度特点：有重复子串一、字符串一、字符串*模式匹配的模式匹配的KMP算法算法(2)关键是关键是next(j)如何求解如何求解 next(j)表达的是表达的是T串自身的特征，与串自身的特征，与S串无关串无关 next函数的数学定义函数的数学定义 next(j)函数值的求解算法函数值的求解算法
8、已知已知k=next(j)，说明，说明T0.j-1之间最大重复子串的长度是之间最大重复子串的长度是k。下面的循环。下面的循环可以求出可以求出next(j+1)的值：的值：比较比较TjTj和和TkTk，如果，如果Tj=TkTj=Tk，那么，那么T0.jT0.j之间最大重复子串的之间最大重复子串的长度就是长度就是k+1k+1，也就是说，也就是说next(j+1)=k+1next(j+1)=k+1，求值完毕；，求值完毕；如果如果Tj TkTj Tk，我们只能在，我们只能在T0.k-1T0.k-1内寻找最大重复子串。内寻找最大重复子串。T0.k-1T0.k-1最大重复子串长度是最大重复子串长度是nex
9、t(k)next(k)，这时设定，这时设定k=next(k)k=next(k)，也就是说，也就是说，k k回退到自己的回退到自己的nextnext值处。我们再次比较值处。我们再次比较TjTj和和TkTk，即转到步骤。，即转到步骤。其他情况当此集合不空时且01.1.01|01)(jkjTkTjkkMaxjjnext7因为因为next值只和值只和T串内容有关，串内容有关，一旦一旦T串确定，就可以计算出所有串确定，就可以计算出所有next值，值，并用一个数组保存，以供字符串匹配时使用。并用一个数组保存，以供字符串匹配时使用。一、字符串一、字符串*模式匹配的模式匹配的KMP算法算法(2)关键是关键是n
10、ext(j)如何求解如何求解 next(j)表达的是表达的是T串自身的特征，与串自身的特征，与S串无关串无关 next函数的数学定义函数的数学定义 next(j)函数值的求解算法函数值的求解算法已知已知k=next(j)，说明，说明T0.j-1之间最大重复子串的长度是之间最大重复子串的长度是k。下面的循环。下面的循环可以求出可以求出next(j+1)的值：的值：比较比较TjTj和和TkTk，如果，如果Tj=TkTj=Tk，那么，那么T0.jT0.j之间最大重复子串的之间最大重复子串的长度就是长度就是k+1k+1，也就是说，也就是说next(j+1)=k+1next(j+1)=k+1，求值完毕；
11、，求值完毕；如果如果Tj TkTj Tk，我们只能在，我们只能在T0.k-1T0.k-1内寻找最大重复子串。内寻找最大重复子串。T0.k-1T0.k-1最大重复子串长度是最大重复子串长度是next(k)next(k)，这时设定，这时设定k=next(k)k=next(k)，也就是说，也就是说，k k回退到自己的回退到自己的nextnext值处。我们再次比较值处。我们再次比较TjTj和和TkTk，即转到步骤。，即转到步骤。其他情况当此集合不空时且01.1.01|01)(jkjTkTjkkMaxjjnext8一、字符串一、字符串*模式匹配的模式匹配的KMP算法算法(3)void NextVal(c
12、har*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算法算法(4)#define MAXSIZE 50int nextMAXSIZE;int StrIndexKMP(char*S,char*T)/*返回T在S中的位置，查找失
13、败，返回-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解疑解疑11Saabcdabcdabceabab
14、cdabceTposijk01234567next-10000123012345678910二、数组与矩阵二、数组与矩阵数组的定义数组的定义#define N 10#define M 20#define P 10elemtype aN;/*定义了一个N个单元的一维数组*/假设假设a0的地址是的地址是Loc，elemtype数据类型的大小是数据类型的大小是S(字节字节)，那么数组单元，那么数组单元ai的地址就是的地址就是:Loc+iS。elemtype bMN;/*定义了一个MN个单元的二维数组*/假设假设b00的地址是的地址是Loc，那么数组单元，那么数组单元bij的前面一共有的前面一共有i行
15、（行（iN个）单个）单元，外加元，外加j个单元，它的地址就是：个单元，它的地址就是：Loc+(iN+j)S12二、数组与矩阵二、数组与矩阵矩阵的压缩存储矩阵的压缩存储(1)1特殊矩阵之特殊矩阵之三角矩阵三角矩阵的压缩存储的压缩存储111222111211100201000nnnnnAAAAAAAAAA111211102221201110000nnnnnAAAAAAAAAAn(n+1)/2-1An-1n-1A11A12A02A00A01A0n-1A13012上三角矩阵的压缩存储上三角矩阵的压缩存储下三角矩阵的压缩存储下三角矩阵的压缩存储An-1n-1A30A22A11A00A10A20A3101
16、23n(n+1)/2-1A21BB13三角矩阵三角矩阵Aij和数组和数组Bk的关系：的关系：u上三角矩阵：上三角矩阵：k=(N+(N-1)+(N-(i-1)+(j-i)=i(2N-i+1)/2+j-I (ji)u下三角矩阵：下三角矩阵：k=(1+2+3+i)+j=i(i+1)/2+j (ij)二、数组与矩阵二、数组与矩阵矩阵的压缩存储矩阵的压缩存储(2)2特殊矩阵之特殊矩阵之对称矩阵对称矩阵的压缩存储，按照三角矩阵的方式的压缩存储，按照三角矩阵的方式 N阶矩阵，存在阶矩阵，存在Aij=Aji3特殊矩阵之特殊矩阵之带状矩阵带状矩阵的压缩存储的压缩存储N阶矩阵，只有主对角线和它的上下两条对角线上有
17、数据，其他位置都是阶矩阵，只有主对角线和它的上下两条对角线上有数据，其他位置都是0或或者某个固定常量。者某个固定常量。k=(i3-1)+(j-(i-1)=2i+j1121343332232221121110010000nnnnAAAAAAAAAAAAA14二、数组与矩阵二、数组与矩阵矩阵的压缩存储矩阵的压缩存储(3)4特殊矩阵之特殊矩阵之稀疏矩阵稀疏矩阵的压缩存储的压缩存储在一个在一个MN的矩阵中，非零元素的个数是的矩阵中，非零元素的个数是T，我们将，我们将 称为稀疏因子。通常称为稀疏因子。通常认为，当稀疏因子小于等于认为，当稀疏因子小于等于0.05时，这个矩阵就称为稀疏矩阵。时，这个矩阵就称
18、为稀疏矩阵。稀疏矩阵的稀疏矩阵的顺序存储顺序存储#define MAXSIZE 500typedef struct int i,j;/*在矩阵中的位置下标*/elemtype v;/*非零元素*/TRIPLE;/*三元组*/typedef struct TRIPLE dataMAXSIZE;/*三元组数组*/int rnum,cnum,sum;/*行数、列数、非零元素的个数*/TRIPLEMATRIX;15二、数组与矩阵二、数组与矩阵矩阵的压缩存储矩阵的压缩存储(4)下面的算法创建一个顺序存储结构的稀疏矩阵：下面的算法创建一个顺序存储结构的稀疏矩阵：void InputData(TRIPLEM
19、ATRIX*m)int count;TRIPLE t;/*开始输入稀疏矩阵的行数、列数和非零元素的个数*/scanf(%d,%d,%d,&m-rnum,&m-cnum,&m-sum);count=0;while(1)scanf(%d,%d,%d,&t.i,&t.j,&t.v);/*获取三元组数据，要求按行序输入*/if(t.i=0&t.irnum&t.j=0&t.jcnum)/*三元组数据合法*/m-datacount=t;count+;/*计数器增1*/if(count=m-sum)break;/*所有数据都输入完毕*/else break;/*遇到非法输入*/16二、数组与矩阵二、数组与矩
20、阵矩阵的压缩存储矩阵的压缩存储(5)4特殊矩阵之特殊矩阵之稀疏矩阵稀疏矩阵的压缩存储的压缩存储稀疏矩阵的稀疏矩阵的十字链表存储十字链表存储将所有同一行的非零元素按列序链接，所有同一列的非零元素按行序链接。将所有同一行的非零元素按列序链接，所有同一列的非零元素按行序链接。这样，同一个三元组单元同时存在于行链和列链两个链表中。这样，同一个三元组单元同时存在于行链和列链两个链表中。typedef struct crsnode_tag int i,j;elemtype v;/*三元组数据*/struct crsnode_tag*right,*down;/*行链指针和列链指针，right指向同一行下一列
21、非零元素，down指向同一列下一行非零元素*/CROSSNODE,*CROSSNODEPTR;/*定义十字链表结点及其指针*/typedef struct CROSSNODEPTR rhead,chead;/*指向行链数组和列链数组*/int rnum,cnum,sum;/*行数、列数、非零元素的个数*/CROSSLINKLIST;17二、数组与矩阵二、数组与矩阵矩阵的压缩存储矩阵的压缩存储(6)1初始化十字链表初始化十字链表int InitCrossLinklist(CROSSLINKLIST*m,int row,int col,int sum)/*初始化一个十字链表，成功则返回1，否则返回
22、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;
23、/*设置行数、列数和非零元素的个数*/return 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,&row,&col,&sum);/*获取行数、列数和非零元素个数*/if(!InitCrossLinklist(m,row,col,sum)/*初始化十字链表*/p
24、rintf(no enough memoryn);exit(0);count=0;/*计数器清零*/while(1)scanf(%d,%d,%d,&i,&j,&v);/*输入三元组数据*/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二、数组与矩阵二、数组与矩阵矩阵的压缩存储矩阵的压缩存储(8)/*开始按列序插入行链，读者应该很
25、熟悉操作细节了*/q=&m-rheadi;while(q-right!=NULL&q-right-jright;p-right=q-right;q-right=p;/在行链尾插入结点p /*开始按行序插入列链*/q=&m-cheadj;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;/while20二、数组与矩阵二、数组与矩阵矩阵的压缩存储矩阵的压缩存储(9)3
26、销毁十字链表销毁十字链表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;/*其他成员设置
27、成安全值*/21二、数组与矩阵二、数组与矩阵稀疏矩阵的转置稀疏矩阵的转置(1)转置的含义：转置的含义：Aij和和Aji交换位置，交换位置，则则M*N矩阵转置后变成矩阵转置后变成N*M 矩阵矩阵三元组数组的转置算法三元组数组的转置算法遍历三元组数组，记下这个稀疏矩阵遍历三元组数组，记下这个稀疏矩阵中每列的非零元素个数，存储数组中每列的非零元素个数，存储数组countcount推算出转置后矩阵的各三元组数据的推算出转置后矩阵的各三元组数据的正确的存储位置正确的存储位置 ，存储位置存放在数，存储位置存放在数组组rposrpos中中再次遍历三元组数组，对每个数据单再次遍历三元组数组，对每个数据单元进行
28、转置，按照元进行转置，按照rposrpos中的数据存放到中的数据存放到新的三元组数组中新的三元组数组中2006009030512020000956012030012345转置前转置后转置后（无序）练习：书101页，练一练4.323二、数组与矩阵二、数组与矩阵稀疏矩阵的转置稀疏矩阵的转置(2)TRIPLEMATRIX TransposeMatrix(TRIPLEMATRIX m)/*返回矩阵m的转置矩阵*/int*count,*rpos;TRIPLEMATRIX T;int k,i,r;count=(int*)malloc(sizeof(int)*um);/*counti将存放矩阵m第i列非零元
29、素的个数*/rpos=(int*)malloc(sizeof(int)*um);/*rposi将存放转置后的矩阵行非零元素的存储起点*/if(count=NULL|rpos=NULL)printf(no enough memoryn);return;for(i=0;um;i+)counti=0;/*计数器清零*/for(i=0;im.sum;i+)/*遍历三元组数组，记录各列非零元素的个数*/k=m.datai.j;countk+;rpos0=0;/*第0行的存储起点是0*/for(i=1;um;i+)/*计算各行非零元素的存储起点*/rposi=rposi-1+counti-1;24二、数组
30、与矩阵二、数组与矩阵稀疏矩阵的转置稀疏矩阵的转置(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二、数组与矩阵二、数组与矩阵稀疏矩阵的乘法
31、稀疏矩阵的乘法(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;kN;k+)Cij+=Aik*Bkj;/*见矩阵乘法公式*/PjMijkBkiAjiCNk001026二、数组与矩阵二、数组与矩阵稀疏矩阵的乘法稀疏矩阵的乘法(2)例子：书10
32、5页，练一练4.4i=0ij否是p指向A第i行第一个非零元素结点p是NULL?否q指向B第k行第一个非零元素结点q是NULL?否j=q-j计算Aik*Bkjv=p-v*q-vCij是零？生成(i,j,v)结点，插入到矩阵C的十字链表中将v累加到Cij上是否q指向B第k行下一个非零元素结点是p指向A第i行下一个非零元素结点i+是清除C中的零元素结点二、数组与矩阵二、数组与矩阵稀疏矩阵的乘法稀疏矩阵的乘法(2)稀疏矩阵十字链表的矩阵乘法稀疏矩阵十字链表的矩阵乘法void MatrixMulti(CROSSLINKLIST*A,CROSSLINKLIST*B,CROSSLINKLIST*C)/*矩阵
33、C将是矩阵A乘以矩阵B的结果*/int i,j,k;elemtype v;CROSSNODEPTR p,q,pC,qC;InitCrossLinklist(C,A-rnum,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
34、;/*计算AikBkj*/二、数组与矩阵二、数组与矩阵稀疏矩阵的乘法稀疏矩阵的乘法(3)/*试图将(i,j,v)插入到矩阵C中*/pC=&C-rheadi;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);ret
35、urn;qC-i=i;qC-j=j;qC-v=v;qC-right=pC-right;pC-right=qC;/*再将结点qC插入到列链中*/pC=&C-cheadj;while(pC-down!=NULL&pC-down-idown;qC-down=pC-down;pC-down=qC;C-sum+;/*矩阵非零元素个数增1*/*属于else语句*/29二、数组与矩阵二、数组与矩阵稀疏矩阵的乘法稀疏矩阵的乘法(4)/*寻找矩阵B第k行的下一个非零元素*/q=q-right;/while(q)/*寻找矩阵A第i行的下一个非零元素*/p=p-right;/while(p)/for /*下面清除十
36、字链表中的零元素结点*/for(i=0;irnum;i+)/*检查所有的行链*/p=&C-rheadi;while(p-right!=NULL)/*遍历行链，摘除所有的零元素结点*/if(p-right-v=0)/*发现零元素结点，从行链中摘除*/p-right=p-right-right;else p=p-right;/*否则p向后移动*/30二、数组与矩阵二、数组与矩阵稀疏矩阵的乘法稀疏矩阵的乘法(5)for(i=0;icnum;i+)/*检查所有的列链*/p=&C-cheadi;while(p-down!=NULL)/*遍历列链，摘除零元素结点*/if(p-down-v=0)/*发现零元
37、素结点，这时它已经从行链中被摘除了*/q=p-down;p-down=q-down;free(q);/*摘除结点并释放内存*/C-sum-;/*这时矩阵非零元素个数减1*/else p=p-down;31导航图导航图(1)字符串和数组字符串和数组字符串字符串数组与矩阵数组与矩阵简单模式匹配简单模式匹配KMP算法算法矩阵的矩阵的压缩存储压缩存储矩阵的转置矩阵的转置和乘法和乘法三元组数组三元组数组的转置的转置十字链表的十字链表的矩阵乘法矩阵乘法特殊矩阵的特殊矩阵的压缩存储压缩存储稀疏矩阵的稀疏矩阵的压缩存储压缩存储32导航图导航图(2)字符串和数组字符串和数组字符串字符串数组与矩阵数组与矩阵简单模
38、式匹配简单模式匹配KMP算法算法矩阵的矩阵的压缩存储压缩存储矩阵的转置矩阵的转置和乘法和乘法三元组数组三元组数组的转置的转置十字链表的十字链表的矩阵乘法矩阵乘法特殊矩阵的特殊矩阵的压缩存储压缩存储稀疏矩阵的稀疏矩阵的压缩存储压缩存储33导航图导航图(3)字符串和数组字符串和数组字符串字符串数组与矩阵数组与矩阵简单模式匹配简单模式匹配KMP算法算法矩阵的矩阵的压缩存储压缩存储矩阵的转置矩阵的转置和乘法和乘法三元组数组三元组数组的转置的转置十字链表的十字链表的矩阵乘法矩阵乘法特殊矩阵的特殊矩阵的压缩存储压缩存储稀疏矩阵的稀疏矩阵的压缩存储压缩存储34导航图导航图(4)字符串和数组字符串和数组字符串
39、字符串数组与矩阵数组与矩阵简单模式匹配简单模式匹配KMP算法算法矩阵的矩阵的压缩存储压缩存储矩阵的转置矩阵的转置和乘法和乘法三元组数组三元组数组的转置的转置十字链表的十字链表的矩阵乘法矩阵乘法特殊矩阵的特殊矩阵的压缩存储压缩存储稀疏矩阵的稀疏矩阵的压缩存储压缩存储35导航图导航图(5)字符串和数组字符串和数组字符串字符串数组与矩阵数组与矩阵简单模式匹配简单模式匹配KMP算法算法矩阵的矩阵的压缩存储压缩存储矩阵的转置矩阵的转置和乘法和乘法三元组数组三元组数组的转置的转置十字链表的十字链表的矩阵乘法矩阵乘法特殊矩阵的特殊矩阵的压缩存储压缩存储稀疏矩阵的稀疏矩阵的压缩存储压缩存储36导航图导航图(6
40、)字符串和数组字符串和数组字符串字符串数组与矩阵数组与矩阵简单模式匹配简单模式匹配KMP算法算法矩阵的矩阵的压缩存储压缩存储矩阵的转置矩阵的转置和乘法和乘法三元组数组三元组数组的转置的转置十字链表的十字链表的矩阵乘法矩阵乘法特殊矩阵的特殊矩阵的压缩存储压缩存储稀疏矩阵的稀疏矩阵的压缩存储压缩存储37导航图导航图(7)字符串和数组字符串和数组字符串字符串数组与矩阵数组与矩阵简单模式匹配简单模式匹配KMP算法算法矩阵的矩阵的压缩存储压缩存储矩阵的转置矩阵的转置和乘法和乘法三元组数组三元组数组的转置的转置十字链表的十字链表的矩阵乘法矩阵乘法特殊矩阵的特殊矩阵的压缩存储压缩存储稀疏矩阵的稀疏矩阵的压缩存储压缩存储38导航图导航图(8)字符串和数组字符串和数组字符串字符串数组与矩阵数组与矩阵简单模式匹配简单模式匹配KMP算法算法矩阵的矩阵的压缩存储压缩存储矩阵的转置矩阵的转置和乘法和乘法三元组数组三元组数组的转置的转置十字链表的十字链表的矩阵乘法矩阵乘法特殊矩阵的特殊矩阵的压缩存储压缩存储稀疏矩阵的稀疏矩阵的压缩存储压缩存储39
