第讲数据库ppt课件.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中的位置，否则返回0if(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}//ifreturn0;//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语言中的串以一个空字符为结束符，串长是一个隐含值。StatusConcat(HString&T,HStringS1,HStringS2){//用T返回由S1和S2联接而成的新