字符串与数组课件

1、第4章 字符串和数组第4章 字符串和数组一、字符串存储方式（1）一个由多个字符构成以零(0)结尾的线性表就是字符串。C语言中没有字符串数据类型。C语言中字符串被存储在字符型数组中，这个数组可以静态定义，也可动态分配。2堆存储：利用一块连续的内存来存放字符串的存储结构define MAXSIZE 100char str1MAXSIZE+1; /*静态定义的字符数组，可容纳最大字符串长度是MAXSIZE*/char *pstr=NULL; /*字符指针，将指向存放字符串的内存*/int len;scanf(“%d”,&len); /*获得字符串的长度*/pstr=(char *)malloc(le

2、n+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

3、中的下标值。这里字符串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(ch

4、ar *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)简单匹配算法

5、的最大问题是：每次匹配失败时，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处的自身最大重复子串的长度。6K值的真正含义：是子串T0.j-1自身重复子串T0.k-1的长度特点：有重复子串一、字符串*模式匹配的KMP算法(1)简单匹配算法的最大一、字符串*模式匹配的KMP算法(2)关键是next(j)

6、如何求解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串确定，就可

7、以计算出所有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最大重

8、复子串长度是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的值

9、都是k+1*/ j+; /*准备推算下一个next值*/ 9一、字符串*模式匹配的KMP算法(3)void Nex一、字符串*模式匹配的KMP算法(4)#define MAXSIZE 50int 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=nex

10、tj; /*匹配失败，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解疑1101234567next-10000123012345678910解疑1101234567next-1000012301234二、数组与矩阵数组的定义#define N 10#define M 20#define P 10

11、elemtype aN;/*定义了一个N个单元的一维数组*/假设a0的地址是Loc，elemtype数据类型的大小是S(字节)，那么数组单元ai的地址就是: Loc+iS。elemtype bMN;/*定义了一个MN个单元的二维数组*/假设b00的地址是Loc，那么数组单元bij的前面一共有i行（iN个）单元，外加j个单元，它的地址就是：Loc+(iN+j)S12二、数组与矩阵数组的定义#define N 1012二、数组与矩阵矩阵的压缩存储(1)1特殊矩阵之三角矩阵的压缩存储13三角矩阵Aij和数组Bk的关系：上三角矩阵：k=(N+(N-1)+(N-(i-1)+(j-i)=i(2N-i+1)

12、/2+j-I (ji)下三角矩阵：k=(1+2+3+i)+j=i(i+1)/2+j (ij)二、数组与矩阵矩阵的压缩存储(1)1特殊矩阵之三角矩阵二、数组与矩阵矩阵的压缩存储(2)2特殊矩阵之对称矩阵的压缩存储，按照三角矩阵的方式 N阶矩阵，存在Aij=Aji3特殊矩阵之带状矩阵的压缩存储N阶矩阵，只有主对角线和它的上下两条对角线上有数据，其他位置都是0或者某个固定常量。 k=(i3-1)+(j-(i-1)=2i+j14二、数组与矩阵矩阵的压缩存储(2)2特殊矩阵之对称矩阵二、数组与矩阵矩阵的压缩存储(3)4特殊矩阵之稀疏矩阵的压缩存储在一个MN的矩阵中，非零元素的个数是T，我们将 称为稀疏因

13、子。通常认为，当稀疏因子小于等于0.05时，这个矩阵就称为稀疏矩阵。稀疏矩阵的顺序存储#define MAXSIZE 500typedef struct int i,j; /*在矩阵中的位置下标*/ elemtype v; /*非零元素*/ TRIPLE;/*三元组*/typedef struct TRIPLE dataMAXSIZE; /*三元组数组*/ int rnum,cnum,sum; /*行数、列数、非零元素的个数*/ TRIPLEMATRIX;15二、数组与矩阵矩阵的压缩存储(3)4特殊矩阵之稀疏矩阵二、数组与矩阵矩阵的压缩存储(4)下面的算法创建一个顺序存储结构的稀疏矩阵：voi

14、d InputData(TRIPLEMATRIX *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; /*所有数据都输入完毕*/

15、else break; /*遇到非法输入*/ 16二、数组与矩阵矩阵的压缩存储(4)下面的算法创建一个顺序二、数组与矩阵矩阵的压缩存储(5)4特殊矩阵之稀疏矩阵的压缩存储稀疏矩阵的十字链表存储将所有同一行的非零元素按列序链接，所有同一列的非零元素按行序链接。这样，同一个三元组单元同时存在于行链和列链两个链表中。typedef struct crsnode_tag int i,j; elemtype v; /*三元组数据*/ struct crsnode_tag * right, * down; /*行链指针和列链指针，right指向同一行下一列非零元素，down指向同一列下一行非零元素*/ C

16、ROSSNODE,* 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;

17、/*根据行数和列数分配相应数量的行链和列链的表头结点*/ 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;

18、/*设置行数、列数和非零元素的个数*/ 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,&row,&col,&sum); /*获取行数、列数和非零元素个数*/ if(!InitCrossLinklist(m,row,col,sum)

19、/*初始化十字链表*/ printf(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二、数组与矩阵矩阵的压缩存储(7)2.建

20、立一个十字链表的二、数组与矩阵矩阵的压缩存储(8) /*开始按列序插入行链，读者应该很熟悉操作细节了*/ 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 inp

21、ut datan); break; /while20二、数组与矩阵矩阵的压缩存储(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

22、); /*释放行链和列链表头结点数组*/ 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中的数据存放到新的三元组数组中01234

23、5转置前转置后转置后（无序）二、数组与矩阵稀疏矩阵的转置(1)转置的含义：Ai练习： 书101页，练一练4.323练习：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将存放转置后的矩阵行非零

24、元素的存储起点*/ 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二、数组与矩阵稀疏矩阵的转置(2)TRIPLEMATRI二、数组与矩阵稀疏矩阵的转置(3) T.sum

25、=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二、数组与矩阵稀疏矩阵的

26、乘法(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

27、; /*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=&C-rheadi; while(pC-right!=NULL&pC-right-jright; if(pC-right!=NULL&pC-right-j=j) pC-right-v+=v; /*原行链中有(i,j,v)结点，执

28、行累加*/ 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=&C-cheadj; while(pC-down!=NULL&pC-down-idown; qC-down=pC-down; pC-down=qC; C-sum+; /*矩阵非零元素个

29、数增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=&C-rheadi; 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=&C-cheadi; while(p-down!=NULL) /*遍历列链，摘除零元素结点*/if(p-down-v=0) /*发现零元素结点，这时它已经从行链中被摘除了*/ q=p-down; p-down=q-down; fr