人民邮政出版社：《数据结构》课程教学资源（PPT课件）第4章 字符串、数组和特殊矩阵

第4章字符串、数组 和特殊矩阵 >字符串 >字符串的模式匹配 >数组 >特殊矩阵 >稀疏矩阵

第4章 字符串、数组 和特殊矩阵 ➢字符串 ➢ 字符串的模式匹配 ➢稀疏矩阵 ➢ 数组 ➢ 特殊矩阵

41字符串 411字符串的基本概念 字符串是由零个或多个字符构成的有限序列, 般可表示成如下形式 1203…n cn”(m≥0) 串中所含字符的个数m称为字符串的长度;当n=0时, 称字符串为空串。 串中任意个连续的字符构成的子序列称为该串 的子串,包含子串的串称为主串。通常称字符在字 符串序列中的序号为该字符在串中的位置。子串在 主串中的位置以子串的第一个字符在主串中的位置 来表示。例如:T= STUDENT”,S=UDEN,则S 是T的子串,S在T中出现的位置为3

4 .1 字符串 4.1.1 字符串的基本概念 字符串是由零个或多个字符构成的有限序列， 一般可表示成如下形式： “ c1 c2 c3….cn ” (n≥0) 串中所含字符的个数n称为字符串的长度；当n=0时， 称字符串为空串。 串中任意个连续的字符构成的子序列称为该串 的子串，包含子串的串称为主串。通常称字符在字 符串序列中的序号为该字符在串中的位置。子串在 主串中的位置以子串的第一个字符在主串中的位置 来表示。例如：T =“STUDENT” ，S=“UDEN” , 则S 是T的子串，S在T中出现的位置为3

两个字符串相等,当且仅当两个串的长度相等 并且各个对应位置的字符都相等。例如 T1=REDROSE T2ERED ROSES 由于T1和T2的长度不相等,因此T1≠T2。 若 T3=STUDENT T4=STUDENS 虽然T3和T4的长度相等,但两者有些对应的字符不 同,因而T3≠T4。 值得一提的是,若S=“”,此时S由一个空格字 符组成,其长度为1,它不等价于空串,因为空串的 长度为0

两个字符串相等，当且仅当两个串的长度相等， 并且各个对应位置的字符都相等。例如： T1=“REDROSE” T2=“RED ROSE” 由于T1和T2的长度不相等，因此T1≠T2。 若 T3=“STUDENT” T4=“STUDENS” 虽然T3和T4的长度相等，但两者有些对应的字符不 同，因而T3≠T4。 值得一提的是，若S=“ ”，此时S由一个空格字 符组成，其长度为1，它不等价于空串，因为空串的 长度为0

412字符串类的定义 ADT string t 数据对象D:由零个或多个字符型的数据元素构成 的有限集合 数据关系R:{1其中aiai+∈D 1 字符串的基本操作如下: (1)Strcreate(S) (2)Strassign(S,T) (3) Strength(S) (4) Strempty(s)

4.1.2 字符串类的定义 ADT string { 数据对象D：由零个或多个字符型的数据元素构成 的有限集合； 数据关系R：{|其中ai , ai+1D, i=1,2,……n-1 } 字符串的基本操作如下： （1） Strcreate (S) （2） Strassign(S, T) （3） Strlength(S) （4） Strempty(S)

(5) Strclear(S) (6)Strcompare(S, s2) (7) Strconcat(,, S,) (8) Substring(S, i, len) (9) Index(P,t) (10) Strinsert(, i, T) (11) Strdelete(s, i, len) (12) Replace(S, T,, T2) (13) Strdestroy(S) J ADT String

（5） Strclear(S) （6）Strcompare(S1，S2 ) （7） Strconcat(S1，S2 ) （8） Substring(S, i, len) （9） Index(P,T) （10） Strinsert(S, i, T) （11） Strdelete(S,i,len) （12） Replace(S, T1 , T2 ) （13） Strdestroy(S) } ADT string

413字符串的存储及其实现 1、串的顺序存储及其部分运算的实现 串的顺序存储使用数组存放,具体类型定义如下: #define maXsize 100 typedef struct char str[MaXsizel: int length 3 setstring;

4.1.3 字符串的存储及其实现 1、串的顺序存储及其部分运算的实现 串的顺序存储使用数组存放，具体类型定义如下： #define MAXSIZE 100 typedef struct { char str[MAXSIZE]; int length ; } seqstring;

(1)插入运算 strinsert(s,iT) void strinsert(seqstring *S, int i, seqstring T) i int k if (iS->length+1 s->length Tlength>MAXSIZE printf(" connot insertIn); else for(k=S->length-l; k>=i-1; k--) S->str Tlength+k=S->str(k; for (k=0; kstri+k-1FTstr[k >length= s->length Tlength S->strIS->length =10

（1）插入运算strinsert(S,i,T) void strinsert(seqstring *S, int i , seqstring T) { int k; if (iS->length+1 || S->length + T.length>MAXSIZE) printf("connot insert\n“); else { for(k=S->length-1;k>=i-1;k--) S->str[T.length+k]=S->str[k]; for (k=0;kstr[i+k-1]=T.str[k]; S->length= S->length + T.length; S->str[S->length]=‘\0’; } }

(2)删除运算 strdelete( s|en) void strdelete(segstring *S, int i,int len) i int k if (iS->lengthl i+len-1>S->length) printf( cannot delete\n"); else for (k=i+len-l; klength; k++) S->str[k-len]= S->str[kl S->length =S->length-len S->str[S->length]=t0

（2）删除运算strdelete(S,i,len) void strdelete(seqstring *S,int i,int len) { int k ; if (iS->length||i+len-1>S->length) printf(“ cannot delete\n”); else { for(k=i+len-1; klength;k++) S->str[k-len]= S->str[k]; S->length=S->length-len; S->str[S->length]=‘\0’; } }

(3)连接运算 strconcat(S1S seqstring strconcat(seqstring sl, seqstring $2) int i; segstril Ing sk if(sIlength+S2,length>MAXSIZE i printf("cannot concat); return NULL) else &r(seqstring* )malloc(sizeof(seqstring); for(i=0; Kstr= SIstri for (i=0; istrI s1length+i]= S2 stril: r->length= SI length+ S2. length; r->strIr->length =10; return (r:

（3）连接运算strconcat(S1 ,S2 ) seqstring * strconcat(seqstring S1,seqstring S2) { int i; seqstring *r; if (S1.length+S2.length>MAXSIZE) { printf("cannot concate"); return(NULL);} else { r=(seqstring*)malloc (sizeof(seqstring)); for (i=0; istr[i]= S1.str[i]; for (i=0; istr[ S1.length+i]= S2.str[i]; r->length= S1.length+ S2.length; r->str[r->length]='\0'; } return (r); }

(4)求子串运算 ubstring(s, i, len) seqstring * substring(seqstring s, int i, int len i int k; seqstring if(i S length‖i+len-l>S. length i printf( errorIn"); return nUll) ese i r(seqstring*) malloc(sizeof(seqstring)); for(k=0; kstr[k=Sstri+k-1; r->length=len r->strlr->length]=0; return(r);

（4）求子串运算substring(S,i,len) seqstring *substring(seqstring S,int i, int len) { int k; seqstring *r; if (iS.length || i+len-1>S.length) { printf(“error\n”); return(NULL);} else { r=(seqstring*) malloc (sizeof(seqstring)); for(k=0;kstr[k]= S.str[i+k-1]; r->length=len; r->str[r->length]='\0'; } return(r); }