第04章_字符串.ppt

第4章字符串、数组和特殊矩阵
字符串
字符串的模式匹配
稀疏矩阵
数组
特殊矩阵
4 .1 字符串 字符串的基本概念 字符串是由零个或多个字符构成的有限序列,一般可表示成如下形式: “c1 c2 c3….cn”(n≥0)串中所含字符的个数n称为字符串的长度;当n=0时,称字符串为空串。 串中任意个连续的字符构成的子序列称为该串的子串,包含子串的串称为主串。通常称字符在字符串序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。例如:T =“STUDENT”,S=“UDEN”, 则S是T的子串,S在T中出现的位置为3。
两个字符串相等,当且仅当两个串的长度相等,并且各个对应位置的字符都相等。例如: T1=“REDROSE” T2=“RED ROSE”由于T1和T2的长度不相等,因此T1≠T2。若 T3=“STUDENT” T4=“STUDENS”虽然T3和T4的长度相等,但两者有些对应的字符不同,因而T3≠T4。 值得一提的是,若S=“”,此时S由一个空格字符组成,其长度为1,它不等价于空串,因为空串的长度为0。
字符串类的定义ADT string { 数据对象D:由零个或多个字符型的数据元素构成 的有限集合; 数据关系R:{<ai, ai+1>|其中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)pare(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
字符串的存储及其实现1、串的顺序存储及其部分运算的实现串的顺序存储使用数组存放,具体类型定义如下: #define MAXSIZE 100 typedef struct { char str[MAXSIZE]; int length ;  } seqstring;
(1)插入运算strinsert(S,i,T)void strinsert(seqstring *S, int i , seqstring T){ int k; if (i<1 || i>S->length+1 || S->length + >MAXSIZE)  printf("connot insert\n“); else { for(k=S->length-1;k>=i-1;k--)  S->str[+k]=S->str[k]; for (k=0;k<;k++)  S->str[i+k-1]=[k];  S->length= S->length + ; S->str[S->length]=‘\0’;  } }
(2)删除运算strdelete(S,i,len)void strdelete(seqstring *S,int i,int len) { int k ; if (i<1 || i>S->length||i+len-1>S->length)  printf(“ cannot delete\n”); else { for(k=i+len-1; k<S->length;k++)  S->str[k-len]= S->str[k]; S->length=S->length-len; S->str[S->length]=‘\0’;  } }
(3)连接运算strconcat(S1,S2)seqstring * strconcat(seqstring S1,seqstring S2) { int i; seqstring *r; if (+>MAXSIZE)  { printf("cannot concate"); return(NULL);} else { r=(seqstring*)malloc (sizeof(seqstring));  for (i=0; i<;i++) r->str[i]= [i]; for