第五章串和数组 51串的定义和操作 52串的表示和实现 53字符串应用 54字符串匹配算法 55数组 56数组的压缩 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 1 中国科学技术大学 第五章 串和数组 5.1 串的定义和操作 5.2 串的表示和实现 5.3 字符串应用 5.4 字符串匹配算法 5.5 数组 5.6 数组的压缩
5.1串的定义和操作 串定义 字符串,由零个或多个字符组成的有限序列。S 串的长度:n 空串:n=0, Null String 子串与主串,子串的位置(从0开始) 串的比较:最大相等前缀子序列 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 2 中国科学技术大学 5.1串的定义和操作 • 串定义 – 字符串，由零个或多个字符组成的有限序列。S ＝ “ a0a1 .....an-1 ” – 串的长度：n – 空串：n=0，Null String – 子串与主串，子串的位置（从0开始） – 串的比较：最大相等前缀子序列
串的基本操作 1)StrAssign(&T, chars) strcpy 2)StrCopy(&T,s strc 3)StrEmpty (s strlen(S==0 4)StrCompare(S,T) strcmp 5)StrEngth(s) rIen 6)Concat(&T, Sl, S2)strcat 7)Substring(&Sub, S, Pos, len)0<=pos<=Strlength(S)- 0<=len<=Strlength(S)-pos strncpy 8)Index(S, T, pos )0<=pos<=Strlength(S)-1strstr 9)Replace(&s,T,V 10)StrInsert(&s, pos, T)0<=pos<=Strlength(s 11)StrDelete(&s, pos,len)0<=pos<-StrLength(S)-len 12)Destroy String(&s) 最小操作子集 StrAssign、 StrCompare、 Strength、 Concat, Substring ypb@ustc.edu.cn 3 中国科学技术大学
ypb@ustc.edu.cn 3 中国科学技术大学 • 串的基本操作 1)StrAssign(&T,chars) strcpy 2) StrCopy(&T,S) strcpy 3) StrEmpty(S) strlen(S)==0 4) StrCompare(S,T) strcmp 5) StrLength(S) strlen 6) Concat(&T,S1,S2) strcat 7) Substring(&Sub,S,Pos,len) 0<=pos<=Strlength(S)-1 0<=len<=Strlength(S)-pos strncpy 8) Index（S，T，pos） 0<=pos<=Strlength(S)-1 strstr 9) Replace(&S,T,V) 10) StrInsert(&S,pos,T) 0<=pos<=Strlength(S) 11) StrDelete(&S,pos,len) 0<=pos<=StrLength(S)-len 12) DestroyString(&S) • 最小操作子集 StrAssign、StrCompare、StrLength、Concat，Substring
52串的表示和实现 52.1定长顺序存储表示 两种表示方法 下标为0的数组存放长度( pascal typedef unsigned char SStringIMAXSTLEN+1 在串值后面加0′结束(C语言) char str[10] 算法5 I void Concat sql( har tu, char Si[, char S2[p 注意】T必须足够长度,否则会溢出 STi452 void Concat Sq2 (SString T[1, SString S1[l, SString S2[D) 存储不同,实现不同! ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 4 中国科学技术大学 5.2串的表示和实现 5.2.1定长顺序存储表示 • 两种表示方法 – 下标为0的数组存放长度 (pascal) typedef unsigned char SString[MAXSTLEN+1] ; – 在串值后面加‘\0’结束 (C语言) char str[10]; 算法5.1 void Concat_Sq1(char T[],char S1[], char S2[]) 【注意】 T[]必须足够长度，否则会溢出 算法5.2 void Concat_Sq2(SString T[],SString S1[], SString S2[]) 存储不同，实现不同！
522堆分配存储表示 ·串变量的存储空间是在程序执行过程中动态分配 的,程序中出现的所有串变量可用的存储空间是 一个共享空间,称为“堆” 算法5.3求字符串长度 void strength(char *s) 算法5.4字符串比较 void StrCompare(char *S, char*T) 算法5.5求字符串字串 void SubString(char *Sub, char *S, int pos, int len) 用Sub返回S中pos位置开始长度为len的子串 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 5.2.2堆分配存储表示 • 串变量的存储空间是在程序执行过程中动态分配 的，程序中出现的所有串变量可用的存储空间是 一个共享空间，称为“堆” 。 算法5.3 求字符串长度 void StrLength(char *S) 算法5.4字符串比较 void StrCompare (char *S, char *T) 算法5.5求字符串字串 void SubString (char *Sub, char *S,int pos,int len) 用Sub返回S中pos位置开始长度为len的子串
G523块链存储表示 用链表来存储串。存在节点大小问题 Const CHUNKSIzE=80 typedef struct Chunk, char ch[ChUnKsizei struct Chunk x next 3 Chunk typedef struct i Chunk *head *tail nt curlen L string, 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; 5.2.3块链存储表示
③ Relplacestring实现 char * replacestring(char*s, char *oldstr char* newstr) char pl=s, p2, tmpfield MAX LENI int nlen=oilen while((p2=strstr(pl, oldstr ))!=NULL& ilen=p2-pI memcpy (tmpfield-+nlen,pl, ilen) memcpy(tmpfield-+nlen+ilen, newstr, strlen(newstr)); nlen+=ilen+strlen(newstr); pl=p2+strlen(oldstr) 1//while if(pl=s) i memcpy (tmpfield+nlen,pl, strlen(pl)) nlen+=strlen(p1) memmove(s, tmpfield nlen salen 3/if 3/ 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实现
③53字符串应用-正文编辑 正文编辑通过页表和行表来维护正文串。 页表中每一项给出页号和该页的起始行号 行表中每一项给出行号、起始地址和该行子串的 长度 当插入和删除字符时需要修改行表中该行的长度, 若超出预先分配的存储空间,还需要重新分配 当插入和删除一行时对行表也进行插入和删除; 若删除的是一页的首行,则要求修改页表中相应 的起始行号 当删除一页时仅仅需要修改页表 ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 5.3字符串应用--正文编辑 • 正文编辑通过页表和行表来维护正文串。 • 页表中每一项给出页号和该页的起始行号 • 行表中每一项给出行号、起始地址和该行子串的 长度 • 当插入和删除字符时需要修改行表中该行的长度， 若超出预先分配的存储空间，还需要重新分配 • 当插入和删除一行时对行表也进行插入和删除； 若删除的是一页的首行，则要求修改页表中相应 的起始行号 • 当删除一页时仅仅需要修改页表
③54正文匹配模式 算法56 int find bF(char*S,char*P, int start) start;j=0 while (s[]=\0&& Pll!= 0) f(S[=Pj]){++j++ else (i=i-j+1; j=0; 3 if (P[]==0)return(i-j else return -1 例:S=“ ababcabcacbab”T=“ abac”返回值=5 算法复杂度:O(mxn)与首字母在S中的出现概率有关 ypb@ustc.edu.cn 9 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 5.4正文匹配模式 • 算法5.6 int find_BF (char *S,char *P,int start) { 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中的出现概率有关
a bcabca bcd a b cabcab c b c abcd a bca bc d 0 P[3.5y=P[0.2] s[1-P[=P[O] S[0.5]=P[0.5] i=3 b c abc a bcd a bc a b a babed a b bc d 0 S[3.5}=P[3.5] 当i=6失配时,可以 (c) =P[0.2 推论:只需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