> 串的链式存储方式（块链） 存在节点大小问题 Const CHUNKSIZE =80: typedef struct Chunk char ch[CHUNKSIZE]; struct Chunk next; Chunk; typedef struct{ Chunk *head,*tail; int curlen; Lstring; ypb@ustc.edu.cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 ➢ 串的链式存储方式（块链） 存在节点大小问题 Const CHUNKSIZE =80; typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk * next; }Chunk; typedef struct { Chunk *head, *tail; int curlen; }Lstring;
Relplacestring实现* char *replacestring(char *s,char *oldstr,char*newstr){ char *pl=s,*p2,tmpfield[MAX LEN]; int nlen=0.ilen: while((p2=strstr(p1,oldstr))!=NULL){ ilen=p2-pl; memcpy(tmpfield+nlen,pl,ilen); memcpy(tmpfield+nlen+ilen,newstr,strlen(newstr)); nlen+=ilen+strlen(newstr); p1=p2+strlen(oldstr); //while if(p1!=s) { memcpy(tmpfield+nlen,pl,strlen(p1)); nlen+=strlen(pl); memmove(s,tmpfield,nlen); s[nlen]=\0'; }llif }/∥replacestring ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 char *replacestring(char *s,char *oldstr, char* newstr){ char *p1=s,*p2,tmpfield[MAX_LEN]; int nlen=0,ilen; while((p2=strstr(p1,oldstr))!=NULL){ ilen=p2-p1; memcpy(tmpfield+nlen,p1,ilen); memcpy(tmpfield+nlen+ilen,newstr,strlen(newstr)); nlen+=ilen+strlen(newstr); p1=p2+strlen(oldstr); } //while if(p1!=s) { memcpy(tmpfield+nlen,p1,strlen(p1)); nlen+=strlen(p1); memmove(s,tmpfield,nlen); s[nlen]=‘\0’; } //if } // replacestring Relplacestring实现*
4.3串的应用 正文编辑 正文编辑通过页表和行表来维护正文串。 页表中每一项给出页号和该页的起始行号 行表中每一项给出行号、起始地址和该行子串的 长度 ·当插入和删除字符时需要修改行表中该行的长度， 若超出预先分配的存储空间，还需要重新分配 当插入和删除一行时对行表也进行插入和删除； 若删除的是一页的首行，则要求修改页表中相应 的起始行号 当删除一页时仅仅需要修改页表 ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 4.3串的应用—— 正文编辑 • 正文编辑通过页表和行表来维护正文串。 • 页表中每一项给出页号和该页的起始行号 • 行表中每一项给出行号、起始地址和该行子串的 长度 • 当插入和删除字符时需要修改行表中该行的长度， 若超出预先分配的存储空间，还需要重新分配 • 当插入和删除一行时对行表也进行插入和删除； 若删除的是一页的首行，则要求修改页表中相应 的起始行号 • 当删除一页时仅仅需要修改页表
4.4模式匹配 >BF算法 int find BF(char*S,char*P,int start)算法4.6 i=start;j=0; while (S[i]!=10&&P[j]=0) if(S=P[]){i+j+;} else {i=i-j+1;j=0; if P[j]=0 return (i-j); else return-1; 例：S="ababcabcacbab”T=abcac”返▣值=5 - 算法复杂度：O(m×n)与首字母在$中的出现概率有关 ypb@ustc.edu.cn 9 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 4.4模式匹配 ➢ BF算法 int find_BF (char *S,char *P,int start) 算法4.6 { i = start; j = 0; while ( S[i] != '\0' && P[j] != '\0' ) if ( S[i] == P[j] ) {i++;j ++;} else { i =i-j+1; j = 0; } if ( P[j] == '\0' ) return (i-j); else return -1; } – 例：S＝ “ababcabcacbab” T=“abcac” 返回值＝5 – 算法复杂度：O(m×n) 与首字母在S中的出现概率有关
i=1 i=0 i=6 a b c a b c a b c d a b c a b c a b c d a b c a bc d a b c a b c d j01 j=6 S[1]=P[1]I=P[0] P[3.5]=P[0.2] (b) (a) S[0.5]=P[0.5] =3 i=6 a b c a b c a b c d a b c a b c a b c d a b c a b c d a b c a b c d j=0 J≈3↑ S[3.5]=P[3.5] 当=6失配时，可以 (c) =P[0.2] (d) 推论：只需i=6和j=3 继续比较 ypb@ustc.edu.cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学 a b c a b c a b c d a b c a b c d i=6 j=6 (a) a b c a b c a b c d a b c a b c d i=1 j=0 (b) a b c a b c a b c d a b c a b c d i=3 j=0 (c) a b c a b c a b c d a b c a b c d i=6 j=3 (d) S[1]=P[1]!=P[0] P[3..5]=P[0..2] S[0..5]=P[0..5] S[3..5]=P[3..5] =P[0..2] 当i=6失配时，可以 推论：只需i=6和j=3 继续比较 i=0 j=0