西交《数据结构》faq（四）

西交《数据结构》FAQ（四）
第四章 串
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  本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986