《数据结构第四章串》由会员分享，可在线阅读，更多相关《数据结构第四章串（22页珍藏版）》请在金锄头文库上搜索。
1、第4章 串,4.1 串的基本概念 4.2 串的基本运算和存储结构 4.3 串的模式匹配算法,4.1 串的基本概念,串是由多个或零个字符组成的有限序列 ，记作S = “a1a2a3an” (n=0)其中，S是串名字， “a1a2a3an”是串值ai是串中字符，n是串的长度，表示串中字符的数目。,空串：长度为零的串称为空串 记作 “ ”,子串：串中任意个连续的字符组成的子序列,主串：包含子串的串。,字符在串中的位置：字符在序列中的序号,子串在串中的位置：子串的第一个字符在主串中的位置,4.2 串的基本运算和存储结构,4.2.1 串的基本运算4.2.2 串的存储结构,1.顺序存储,每个串预先分配一个
2、固定长度的存储区域。Char smaxsize;,实际串长可在所分配的固定长度区域内变动在串值后加入”0”表示结束，此时串长为隐含值,用定长数组描述：#define maxsize 32Typedef sturct char chmaxsize;int curlen; seqstring;,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 maxsize-1,2.链接存储,Typedef struct linknode char data;struct linknode *next; linkstring;linkstring *s;,注：存储密度,3.索引存储
3、,带长度的名字表带末指针的名字表带特征位的名字表带位移量的名字表,带长度的名字表,Typedef sturct char namemaxsize;int length;char *stadr; lnode;,例：S1=“abcdefg”S2=“bcd”,带末指针的名字表,Typedef sturct char namemaxsize;char *stadr,*enadr; enode;,带特征位的名字表,Typedef sturct char namemaxsize;int tag;union char *stadr;char value4;uval; tagnode;,带位移量的名字表,Ty
4、pedef sturct char namemaxsize;char *stadr,*enadr;int offset1,offset2; onode;,串的基本运算,串赋值：,例：S=“abc”S1=SS=“”,串联接：strcat(ST1,ST2),例：ST1=“abc”ST2=“efg”strcat(ST1,ST2)则 ST1=“abcdefg”,求串长：strlen(S),例：ST1=“abc”则 strlen(ST1)=3strlen(“”)=0,求子串：substr(S,i,j),1=0 例：substr(“abcd”,2,2)=“bc”substr(“abcd”,3,3)=“cd
5、”,串比较：strcmp(S,T),串插入：insert(S1,i,S2),S1=“ABCD” insert(S1,2,”abc”) 则 S1=“ABabcCD”,strcmp(“this”,”there”)0 strcmp(“the”,”there”)=pos-1;-i)S.chi+T.length=S.chi;for (i=0; i=T.length-1;i+)S.chpos-1+i=T.chi;S.length+=T.length; return OK; ,Status StrAssign(HString &S,char *chars) 生成一个值等于chars的串S, int i,j;
6、 char *c;for (i=0,c=chars;*c;+i,+c);if (!i) S.ch=NULL; S.length=0;else if (!(S.ch=(char *)malloc(i * sizeof(char)exit(OVERFLOW);for (j=0;j=i-1;j+)S.chj=charsj;S.length=i;return OK; ,int StrLength(HString S) 求串的长度,return S.length; ,int StrCompare(HString S,HString T) 比较两个串，若相等返回0,int i;for (i=0;iS.le
7、ngth ,Status Concat(HString &S,HString S1,HString S2) 用S返回由S1和S2联接而成的新串, int j;if (!(S.ch = (char*)malloc(S1.length+S2.length)*sizeof(char)exit(OVERFLOW);for (j=0;j=S1.length-1;j+) S.chj=S1.chj;S.length=S1.length+S2.length;for (j=0;j=S2.length-1;j+)S.chS1.length+j=S2.chj;return OK; ,Status SubString
8、(HString &Sub,HString S,int pos,int len) 用Sub返回串S的第pos个字符开始长度为len的子串,if (posS.length | lenS.length-pos+1)return ERROR;if (!len) Sub.ch=NULL; Sub.length=0;else Sub.ch=(char *)malloc(len*sizeof(char);for (int j=0;j=len-1;j+)Sub.chj=S.chpos-1+j;Sub.length=len;return OK; ,Status ClearString(HString &S)
9、将S清为空串,if (S.ch) free(S.ch); S.ch=NULL;S.length=0;return OK; ,4.3 串的模式匹配算法,定义 在串中寻找子串（第一个字符）在串中的位置,术语 在模式匹配中，子串称为模式，串称为目标。,示例 目标 S : “Beijing”模式 P : “jin”匹配结果 = 4,穷举（朴素）模式匹配,设S=s0,s1,sn-1(目标)P=p0,p1,pm-1(模式),i为指向S中字符的指针，j为指向P中字符的指针,匹配失败：sipj时， (si-j si-1)=(p0 pj-1),回溯： i=i-j+1 ; j=0,第1趟 S a b b a b aP a b a i=2, j=2,第2趟 S a b b a b aP a b a i=1, j=0,第3趟 S a b b a b aP a b a i=2, j=0,第4趟 S a b b a b aP a b a i=5, j=2 ,穷举的模式匹配过程,模式匹配算法,int index(S,T) seqstring *s,*t; int i=0,j=0;while (icurlen) ,
