1、串的ADT定义及基本操作

ADT String{

数据对象D={ai I ai∈字符集，i=1,2,...,n,n≥0)

数据关系R={<ai．1,ai>I ai．1,ai∈D，i=2,...,n)

基本操作13个P71

} ADT String 

基本操作13个

串赋值  StrAssign(＆T,chars)

串复制  StrCopy(＆T,S)

判空串  StrEmpty  (S)

串比较  StrCompare  (S,T)

求串长  StrLength  (S)

串清空  ClearString  (＆S)

串联结  Concat  (＆T,S1,S2)

取子串  StrString

串匹配  Index  (S,T,pos)

串置换  Replace (＆S,pos,T)

串插入  StrInsert  (＆S,pos,T)

删子串  StrDelete  (＆S,pos,len)

串销毁  DesroySring  (＆S)

2、定位函数 Index(S, T, pos )的基本思想及实现。

算法思想  逐字符逐位比较S串和T串，不相等时向后移位继续比较，直至匹配，输出i，或到s尾终止。

int  Index (String S,String T,int pos ) {
   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 ;
         else  return i ;
       }∥while
    }∥if
   return 0 ;
} ∥index

3、串的定长顺序存储表示  

用定长数组。长出截断!(例，文件／人名8位)

定义ADT存储表示  maxstrlen=256   char[0.255]  0位放串长

#define MAXSTRLEN   255
typedef  unsigned char SString[MAXSTRLEN +1 ];

4、串的连接 Concat( &T, S1, S2 )

几种连接情况的讨论    s1 + s2 à T

① s1.len + s2.len≤maxstrlen

     s1, s2全部拼入T

② s1.len< maxstrlen    s1.len + s2.len > maxstrlen

     s1全部, s2 部分拼入T

③ s1.len= maxstrlen     T=S1

算法思想：分情况拼接串。 超长截断 

算法 4.2  P73

5、求取子串 SubString( &Sub, S, pos, len )

*pos、len的合理性
status SubString (SString &sub,SString S,int pos,int len) {
   if ( pos<1‖pos>S[0] ‖len<0‖len>S[0]-pos+1) 
        return ERROR ;
   sub[1..len]=S[pos..pos+len-1] ;
   sub[0]=len ;   return OK ;
 }∥SubString

6、串的堆分配存储表示  

用一组连续的存储单元存放。

typedef  struct {
char  *ch ;
int    length ;
}Hstring

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

这类串操作的实现算法为:先为新生成的串分配一个存储空间，然后进行串值的复制。

7、串插入 StrInsert( HString &S, int pos, Hstring T )算法

status StrInsert (HString &S, int pos,  HString T) {
   if ( pos<1‖pos>S.length)    return ERROR ;
   if (T.length) {
       if  (!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))))
           exit (OVERFLOW) ;
       for ( i =S.length-1; i >=pos-1 ; --i ) 
           S.ch[ i +T.length]=S.ch[ i ] ;
       S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];
       S.length+=T.length ;
      }
    return OK ;
  }∥StrInsert

8、堆上的其它6个操作

串复制 StrAssign ( HString  &T,  char  *chars )；原T如存在，释放，另存另分。

求串长 Strength ( HString  S )

串比较 StrCompare ( HString  S,  HString  T )

串清空 ClearString ( HString  &S )

串联接 Concat ( HString  &T,  HString  S1,  HString  S2 )原T如存在，释放，另分，拼S1, S2存入T的store区

取子串 SubString ( HString  S,  int  pos,  int  len )

例：汉字：字码 字模 字库 字号 字体……激光打印一字一K

五笔/全拼  16×16  32字节

9、串赋值 StrAssingn( HString &T, char  *chars )

status StrAssingn( HString &T,char  *chars ) {
   if  ( T.ch)   free ( T.ch ) ;
   for ( i =0, c=chars ; c ; ++ i , ++c ) ;    //求长度
   if  ( ! i )  { T.ch=NULL ; T.length=0 ;}
   else  {
      if  ( ! (T.ch=(char*)malloc( i *sizeof(char))))
            exit (OVERFLOW) ;
      T.ch[ 0.. i -1]=chars[0..i -1] ;
   }
   T.length= i ;
   return OK ;
 }∥StrInsert

来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=197

• 数据结构知识点总结（一）2018-09-10 21:33
• 学习数据数据结构的意义2018-08-18 09:05
• 数据结构知识点总结（四）2018-09-10 21:25
• 查找相关术语2018-09-03 22:44