串的抽象数据类型的定义.ppt

4.1串的抽象数据类型的定义4.1串的抽象数据类型的定义如下：
基本操作：SubString(&Sub,S,pos,len)
StrAssign(&T,chars)

初始条件：chars是字符串常量。

操作结果：把chars赋为T的值。
DestroyString(&S)

初始条件：串S存在。

操作结果：串S被销毁。
StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回true，否则返回false。StrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若ST，则返回值0；若ST，则返回值0。StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。SubString(&Sub,S,pos,len)

初始条件：

操作结果：
用Sub返回串S的第pos个字符起
长度为len的子串。例如：
SubString(sub,commander,4,3)SubString(sub,commander,4,7)
sub=?Index(S,T,pos)初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。假设S=abcaabcaaabc,T=bcaReplace(&S,T,V)初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。例如：StrInsert(&S,pos,T)初始条件：串S和T存在，
1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前
插入串T。StrDelete(&S,pos,len)初始条件：串S存在
1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。串赋值StrAssign、串比较StrCompare、
求串长StrLength、串联接Concat以及
求子串SubString等五种操作构成串类型的最小操作子集。例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。intIndex(StringS,StringT,intpos){
//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，
//则返回第一个这样的子串在S中的位置，否则返回0
if(pos>0){

}//if
return0;//S中不存在与T相等的子串
}//Index又如串的置换函数：voidreplace(String&S,StringT,StringV){

}串的逻辑结构和线性表极为相似，区别
仅在于串的数据对象约束为字符集。在程序设计语言中，串只是
作为输入或输出的常量出现，则只
需存储此串的串值，即字符序列即
可。但在多数非数值处理的程序中，
串也以变量的形式出现。一、串的定长顺序存储表示#defineMAXSTRLEN255
//用户可在255以内定义最大串长
typedefunsignedcharSString
[MAXSTRLEN+1];
//0号单元存放串的长度按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”StatusConcat(SStringS1,SStringS2,SString&T){
//用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE，否则FALSE。

returnuncut;
}//Concattypedefstruct{
char*ch;
//若是非空串，则按串实用长度分配
//存储区，否则ch为NULL
intlength;//串长度
}HString;通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。
C语言中的串以一个空字符为结束符，串长是一个隐含值。StatusConcat(HString&T,HStringS1,HStringS2){
//用T返回由S1和S2联接而成的新串
if(T.ch)delete(T.ch);//释放旧空间
if(!(T.ch=newchar[S1.length+S2.length]))
exit(OVERFLOW);
T.ch[0..S1.length-1]=S1.ch