字符串 (String).ppt

字符串(String)
字符串是 n (  0 ) 个字符的有限序列,
记作 S : “”
其中,S 是串名字
“”是串值
ci 是串中字符
n 是串的长度。
例如, S = “Kaili College”
一,定长顺序存储表示
定义:用一组地址连续的存储单元存储串值序列。
类型定义:
#define MAXSTRLEN 100 //最大串长
Typedef unsigned char SString[MAXSTRLEN+1];//下标为0的数组单元存放串的长度
1,串的联接
串联接操作,当注意:可能存在超长“截断”操作。
新串的产生可能有3种情况:
S1[0]+S2[0] ≤MAXSTRLEN,结果正确
S1[0]+S2[0] ≥MAXSTRLEN,S2部分截断
S1[0] =MAXSTRLEN,S2全部截断
Status Concat(SString &T,SString S1,SString S2)
{//T返回由S1和S2联接成的新串。若未被截断,则返回TRUE,否则返回FALSE。
if(S1[0] + S2[0] <= MAXSTRLEN ){//未截断
T[1…S1[0]] = S1[1…S1[0]];//将串S1的各元赋值到T
T[S1[0] + 1… S2[0]] = S2[1…S2[0]];//将串S2的各元
//接到T中
T[0] = S1[0] +S2[0];//联结后T的长度
uncut = TRUE;
}
else if(S1[0] < MAXSTRLEN){//S2被部分截断
T[1…S1[0]] = S1[1…S1[0]];
T[S1[0] +1…(MAXSTRLEN-S1[0])] = S2[1…(MAXSTRLEN-S1[0])];
T[0] = MAXSTRLEN;
uncut = FALSE;
}
else{ //S2完全被截断
T[0…MAXSTRLEN] = S1[0…MAXSTRLEN];
uncut = FALSE;
}
return uncut;
}
2,求子串( 即复制子串)
Status SubString(SString &Sub,SString S,int pos,int len)
{//Sub 返回串S的第pos个字符起长为len的子串,
//1≤pos≤Strlength(s)且0 < len≤Strlength(s)-pos+1
if(pos < 1 || pos > S[0] || len >S[0] –pos+1) return ERROR;
Sub[1…len] = S[pos…(pos + len -1)];
Sub[0] = len;
reurn ok;
}
3,求子串位置(即子串定位或模式匹配)
int Index(SString S,SString T,int pos)
{ // 从pos位置开始查找,返回串T在主串S中的位置
// T非空,1≤pos≤Strlength(s) 。
i = pos; j = 1;
while(i <= S[0] && j <=T[0]){
if(S[i] == T[j]) {++i;++j;}
else { i = i –j +2; j = 1;}
}
if(j > T[0]) return i-T[0];//返回串T在主串S中的位置
else return 0;
}
定义:以一组地址连续的存储单元存放串值序列,地址空间是动态分配的。
类型定义:
Typedef struct{
char *ch; //非空串,则按串长分配存储空间,否则ch为NULL
int length; //串长
}
二,堆分配存储表示
const int maxLen = 128;
class String {
int curLen; //串的当前长度
char *ch; //串的存储数组
public:
String ( const String& ob );
String ( const char * init );
String ( );
~String ( ) { delete [ ] ch; }
字符串抽象数据类型和类定义(面向对象方法)
int Length ( ) const { return curLen; }
//求当前串*this的实际长度
String &operator ( ) ( int pos, int len );
//取*this从pos开始len个字符组成的子串
int operator == ( const String &ob )
{ return strcmp (ch, ob.