第讲数据库.ppt

位置来表示。
例如：a,b,c,d为如下的4个串：
a=‘BEI’,b=‘JING’
c=‘BEIJING’,d=‘BEIJING’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,commander,4,3)
求得sub=man；
SubString(sub,commander,1,9)
求得sub=commander；
SubString(sub,commander,9,1)
求得sub=r；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清为空串。在上述抽象数据类型定义的13种操作中，
串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等五种操作构成串类型的最小操作子集。
即：这些操作不可能利用其他串操作来实现，
反之，其他串操作（除串清除ClearString和串
销毁DestroyString外）可在这个最小操作子
集上实现。例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。intIndex(StringS,StringT,intpos){
//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个
这样的子串在S中的位置，否则返回0
if(pos>0){
n=StrLength(S);m=StrLength(T);i=pos;
while(i<=n-m+1){
SubString(sub,S,i,m);
if(StrCompare(sub,T)!=0)++i;
elsereturni;
}//while
}//if
return0;//S中不存在与T相等的子串
}//Index又如串的置换函数：串的逻辑结构和线性表极为相似，区别
仅在于串的数据对象约束为字符集。在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。一、串的定长顺序存储表示#defineMAXSTRLEN255
//用户可在255以内定义最大串长
typedefunsignedcharSstring
[MAXSTRLEN+1];
//0号单元存放串的长度按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”。StatusConcat(SStringS1,SStringS2,SString&T){
//用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE，否则FALSE。

returnuncut;
}//Concat通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。
C语言中的串以一个空字符为结束符，
串长是一个隐含值。St